Massive cancellations

Question

Let $A=\{a_1,\ldots,a_k\}$ be a fixed, finite set of reals. Let $S_A(n)$ be the set of all reals that are expressible as the sum of at most $2^n$ terms, where each term is a product of at most $n$ numbers from $A$ (here each element of $A$ can be reused an unlimited number of times). Finally, let $d_A(n)$ be the minimum of $|x|$, over all nonzero $x\in S_A(n)$.

I'm interested in how quickly $d_A(n)$ can decrease as a function of $n$. Exponential decrease is easy to obtain (indeed, we have it whenever there's an $a\in A$ such that $|a|\lt 1$), but anything faster than that would require extremely finely-tuned cancellations, which continue to occur even as $n$ gets arbitrarily large. Thus, let's call $A$ tame if there exists a polynomial $p$ such that $d_A(n)\gt 1/\exp(p(n))$ for all $n$, and non-tame otherwise. Then here's my question:

Does there exist a non-tame $A$?

Note that I don't care much about the dependence on $k$ (holding fixed the approximate absolute values of the $a_i$'s), which might be triple-exponential or worse.

To illustrate, if $A$ is a set of rationals, then it's easy to show that $A$ is tame. By using known results about the so-called Sum-of-Square-Roots Problem (which rely on results about the minimum spacing between consecutive roots of polynomials, from algebraic geometry), I can also show that if $A$ is a set of square roots of rationals---or more generally, ratios of sums and differences of square roots of positive integers---then $A$ is tame.

More generally, I conjecture that every set of algebraic numbers is tame, and maybe this can even be shown similarly, but I haven't done so. But while thinking about this, it occurred to me that I don't have even a single example of a non-tame set---hence the question.

Meanwhile, I would also be interested in results showing, for example, that every $A$ consisting of sines and cosines of rational numbers is tame.

If anyone cares, the origin of this question is that, if every $A$ is tame, then it follows that given any $n^{O(1)}$-size quantum circuit over a fixed, finite set of gates (i.e., unitary transformations acting on $O(1)$ qubits at a time), the probability that the circuit outputs "Accept" is at least $1/\exp(n^{O(1)})$. Likewise, if all $A$'s that are subsets of some $S\subseteq\Re$ are tame, then the same result follows, but for quantum circuits over finite sets of gates where all the unitary matrix entries belong to $S$. (So for example, from the result mentioned above about square roots of rationals, we get that any quantum circuit composed of Hadamard and Toffoli gates satisfies this property.)

This issue, in turn, is relevant to making fully precise the definition of the complexity class PostBQP (quantum polynomial time with postselected measurements), which I invented in 2004. If all $A$'s are tame, then there's no problem with my 2004 definition; if some $A$'s are not tame, then the definition needs to be amended, to restrict the set of gates to ones like {Toffoli,Hadamard} that won't give rise to doubly-exponentially-small probabilities.

Update (Nov. 30): For those who are interested, I now have a blog post that discusses this MO question and where it came from (among several other things).

Answer 1

Let $a_n$ be an increasing sequence of positive integers which grows really fast, say $a_{n+1} > \exp(a_n)$. Take $A = \{10^{-1}, \sum 10^{-a_n}\}$. Then $d_A(a_n) \leq 2\cdot 10^{- a_{n+1}} \leq 2\cdot 10^{-\exp a_n}$, so $A$ cannot be tame.

EDIT. One could replace $1/10$ by some transcendental $0<x<1$ such that $\sum x^{-a_n}$ is transcendental as well. This gives an example of a non-tame $A$ consisting of transcendental elements.

Answer 2

Here's an argument that for $A$ a finite set of algebraic numbers, $d_A(n)$ decays at most exponentially.

Suppose $A$ is contained in some number field $K$. For $x\in K^\times$, there's a product formula $$ \prod_v |x|_v=1, $$ where $v$ runs over the valuations on $K$ and $|\cdot|_v$ is a suitably normalized absolute value. In order for some absolute value to be small, the product of the others must be large.

For fixed $A$, there is a finite set of places $P$ of $K$ such that $|x|_v\leq 1$ for all $x\in S_A(n)$ whenever $v\not\in P$ ($P$ consists of all the Archimedean places, and the non-Archimedean places dividing denominators of elements of $A$). It's not hard to see that for fixed $v$, $\max \{|x|_v:x\in S_A(n)\}$ grows at most exponentially in $n$.

In our case, $K$ is embedded in the real numbers. Let $v_0$ be the valuation coming from this embedding. Since the number of $v$ for which $|x|_v>1$ is bounded, we have \begin{gather} d_A(n)=\min \big\{|x|_{v_0}:x\in S_A(n)\backslash\{0\}\big\}=\min\left\{\prod_{v\neq v_0}|x|_v^{-1}\right\} \geq\min\left\{\prod_{v\in P\backslash\{v_0\}} |x|_v^{-1}\right\}. \end{gather} The right hand side decays at most exponentially, so the left hand side does too.

Answer 3

Embarrassingly, it turns out that Greg Kuperberg previously answered my question: see Theorem 2.11 of this paper. In particular, he proved that all sets of algebraic numbers of tame, and he also observed that there exist sets including non-algebraic numbers that are non-tame (though he didn't include that observation in his paper). Moreover, he did this for exactly the same reason why I was interested in it: namely, in order to fix an ambiguity in the definition of the complexity class PostBQP. The clincher is that he actually wrote to me to explain all this! But I didn't pay attention at the time, and then I forgot about it when the question came up later. My apologies to anyone else who spent time on this on the assumption that it hadn't already been answered. But at least I now really understand the answer!

Answer 4

You can do this without much number theory. View your field as a finite-dimensional vector space over $\mathbb Q$. Then every element acts linearly on the field, so it acts as some matrix with rational entries. The actual element you want to bound is an eigenvalue of this matrix.

We can lower bound it by lower bounding the determinant and upper bounding the other eigenvalues. Observe:

The entries grow at most exponentially, so the other eigenvalues grow at most exponentially. Because the number field is a field, the element is invertible, so the determinant is nonzero. The denominators of the entries grow at most exponentially, so the denominator of the determinant grows at most exponentially.

Then you get a lower bound on one eigenvalue by division and the fact that the numerator of the determinant must be at least $1$.

This is connected to the valuations proof as follows: the valuations at $\infty$ are just the absolute value of the eigenvalues, and the others are related to the powers of different primes dividing (denominators of ) entries of the matrix.