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).
Best Answer
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.