# Massive cancellations

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

• I think I can show all finite sets of algebraic numbers are tame. Would it be weird to post as an answer, because it doesn't answer this question? – Julian Rosen Nov 25 '14 at 3:53
• @Julian: it seems fine to post it. It doesn't directly answer the question but it rules out a potential class of answers. – Qiaochu Yuan Nov 25 '14 at 5:19

## 4 Answers

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.

• I think, A is supposed to be finite. – Gjergji Zaimi Nov 25 '14 at 3:18
• Indeed, my $A$ consists of two elements. – Piotr Achinger Nov 25 '14 at 3:19
• Oh, oops :). My brain thought it was too good to be true. – Gjergji Zaimi Nov 25 '14 at 3:21
• Thanks!! Like many great MO answers, embarrassingly obvious in retrospect, but it would've taken me quite a while. Let me see if I can leverage this to create an actual set of quantum gates able to produce doubly-exponentially-small acceptance probabilities. Meantime, I hereby scale back my ambitions to showing tameness for all finite sets of algebraic numbers, or other sets of numbers expressible in terms of "normal" operations like sines and cosines (rather than stacks of exponentials, as needed for this construction). – Scott Aaronson Nov 25 '14 at 3:43
• Yes, I agree it should be true for sets of algebraic numbers, but it seems like a very difficult problem in diophantine approximation. Can you deal with the case $A=\{a, b\}$ with $a$ rational and $b$ algebraic? – Piotr Achinger Nov 25 '14 at 3:48

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.

• Thanks so much, Julian! I'm trying to unpack this proof---can anyone suggest a good reference for reading about why the product formula holds for valuations, and why there are only finitely many valuations $v$ for which $|x|_v$ can exceed $1$? Also, for an algebraic number field, how many valuations are there in total---countably many? How do we even see that $\prod_v |x|_v$ is well-defined? (Sorry for asking such basic questions.) – Scott Aaronson Nov 26 '14 at 3:53
• There's relevant info in Cassels' Local Fields (10.1-2) and Neukirch's Algebraic Number Theory (III.1). You might also try Section 7 of Milne's algebraic number theory course notes (have a look at p. 97). A number field has countably many places (= valuations up to equivalence). For fixed $x$, $|x|_v=1$ for all but finitely many $v$, so the product is finite. – Julian Rosen Nov 26 '14 at 5:18
• There's one non-archimedean valuation for each prime ideal in the ring of integers $R$ (and hence countably many) plus at most $d$ archimedean valuations where $d$ is the degree of the field. The principal ideal $xR$ generated by an element $x$ factors (uniquely) into a finite product of prime ideals and a non-archimedean valuation is $\ne1$ only for primes appearing in this factorization. Thus $|x|_v\ne1$ for only finitely many $v$ and the product is well-defined. – Timothy Chow Nov 26 '14 at 13:59
• Note that for $K=\mathbb Q$, the archimedean valuation is just the usual absolute value, and the non-archimedean valuations are the $p$-adic norms. The product formula says that if, for each prime $p$, you pull out the highest power (possibly negative, for fractions) of $p$ dividing $x$, and multiply these together, then you get $|x|$. So the product formula is, in a sense, "equivalent" to the unique factorization theorem. For number fields you have to use prime ideals to get unique factorization, but it's all totally analogous. – Timothy Chow Nov 26 '14 at 14:23
• @Scott aaronson it's $r+c$, where $r$ is the number of real embedding sand $c$ is the number of complex embeddings. You have $r+2c=d$, where $d$ is the degree of the field. If your field is generated by one element, $d$ is the degree of the minimal polynomial and $r$ is the number of real roots. – Will Sawin Nov 26 '14 at 18:28

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.

• Thanks so much, Will -- this clarified things enormously! There was one step that wasn't obvious to me: why does the minimum eigenvalue of the matrix give a lower bound on the actual real valuation of the element? But I think I now see it: let $\alpha_1,\ldots,\alpha_k$ be the generators of the extension field; then $(1,1/\alpha_1,\ldots,1/\alpha_k)$ is always an eigenvector of the matrix corresponding to an element $v\in\mathbb{Q}[\alpha_1,\ldots,\alpha_k]$, and its associated eigenvalue is always $|v|$ (by calculation). – Scott Aaronson Nov 27 '14 at 1:55
• A small observation. By combining this argument with Piotr Achinger's construction, we get an elementary, self-contained proof that there exist transcendental numbers that can be explicitly constructed: namely, the same numbers that Liouville showed to be transcendental in his original proof -- en.wikipedia.org/wiki/…. Maybe this "ultimately" amounts to the same thing as Liouville's proof, but I think I prefer it to the proof on Wikipedia. – Scott Aaronson Nov 27 '14 at 3:28
• @ScottAaronson The way I think of it is that there's an eigen-linear form that sends the $\mathbb Q$-vector space $K$ to $K \subseteq \mathbb C$ by a linear map. It's easy to see that having an eigen-linear form with eigenvalue $\lambda$ implies an eigenvector with eigenvalue $\lambda$. – Will Sawin Nov 27 '14 at 3:33

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!

• Here is a remaining open question from the topic that I find interesting: Is e a tame number? – Greg Kuperberg Nov 27 '14 at 18:23