Cancellation is a Pain
How to avoid the pain of estimating tough sums
Andrew Granville is a number theorist, who has written—besides his own terrific research—some beautiful expository papers, especially on analytic number theory.
Today Ken and I wish to talk about his survey paper earlier this year on the size of gaps between consecutive primes.
The paper in question is here. It is a discussion of the brilliant breakthrough work of Yitang Zhang, which almost solves the famous twin-prime conjecture. You probably know that Zhang proved that gaps between consecutive primes are infinitely often bounded by an absolute constant. His constant initially was huge, but using his and additional insights it is now at most and plans are known that might cut it to .
As Andrew says in his paper’s introduction:
To Yitang Zhang, for showing that one can, no matter what
We believe we need the same attitude to make progress on some of our “untouchable” problems. Perhaps there is some budding complexity theorist, who is making ends meet at a Subway™ sandwich shop, and while solving packing problems between rolls in real time is finding the insights that can unlock the door to some of our open problems. Could one of these be ready to fall?
- Is NP closed under complement?
- What is the power of polynomials?
- Can we at least prove SAT is not computable in linear time?
- And so on …
Throughout mathematics—especially number theory—computing the number of objects is of great importance. Sometimes we can count the exact number of objects. For example, it is long known that there are exactly labeled trees, thanks to Arthur Cayley.
The number of labeled planar graphs is another story—no exact formula is known. The current best estimate is an asymptotic one for the number of such graphs on vertices:
where and .
Thanks to a beautiful result of the late Larry Stockmeyer we know that estimating the number of objects from a large set may be hard, but is not too hard, in the sense of complexity theory. He showed that
Theorem 1 For any one can design an -time randomized algorithm that takes an NP-oracle , a predicate decidable in -time (where ) and an input and outputs a number such that with probability at least , the true number of such that holds is between and
The predicate is treated as a black box, though it needs to be evaluated in polynomial time in order for the algorithm to run in polynomial time. The algorithm has a non-random version that runs within the third level of the polynomial hierarchy.
We won’t state the following formally but Larry’s method can be extended to compute a sum
to within a multiplicative error without an NP-oracle, provided the map is computable in polynomial time, each , and the summands are not sparse and sufficiently regular. Simply think of , identify numbers with strings so that runs over , and define to hold if .
Larry’s method fails when a sum has both negative and positive terms; that is, when there is potential cancellation. Consider a sum
Even if the terms are restricted to be and , his method does not work. Rewrite the sum as
Then knowing and approximately does not yield a good approximation to the whole sum . We could have and where is a large term that cancels so that the sum is . So the cancellation could make the lower order sums and dominate.
This happens throughout mathematics, especially in number theory. It also happens in complexity theory, for example in the simulation of quantum computations. For every language in BQP there are Stockmeyer-style predicates and such that equals the number of Hadamard gates in poly-size quantum circuits recognizing whose acceptance amplitude is given by
Although the individual sums can be as high as their difference “miraculously” stays within , and the former is never less than the latter—no absolute value bars are needed on the difference. See this or the last main chapter of our quantum algorithms book for details. Larry’s algorithm can get you a approximation of both terms, but precisely because the difference stays so small, it does not help you approximate the probability. This failing is also why the algorithm doesn’t by itself place BQP within the hierarchy.
When Only Positivity is Needed
What struck Ken and me first is that the basic technique used by Yitang Zhang does not need to estimate a sum, only to prove that it is positive. This in turn is needed only to conclude that some term is positive. Thus the initial task is lazier than doing an estimate, though estimates come in later.
where is defined to be if is prime and is otherwise. Here runs from to and . If the term is positive then at least two of the elements and must be prime, which means that the gap between them is at most the fixed value . Doing this for infinitely many yields Zhang’s conclusion that infinitely many pairs of primes have gap at most . Can it really be this simple?
The strategy is to minimize , but it needs to provide a way to get a handle on the function. This needs forming the sum
where the are freely choosable non-negative real weights. The analysis needs the to be chosen so that for every prime there exists such that does not divide any of . This defines the ordered tuple as admissible and enters the territory of the famous conjecture by Godfrey Hardy and John Littlewood that there exist infinitely many such that are all prime. This has not been proven for any admissible tuple—of course the tuple gives the Twin Prime conjecture—but thanks to Zhang and successors we know it holds for for some .
The analysis also needs to decouple from the —originally there was a dependence which only enabled Goldston, Pintz, and Yíldírím to prove cases where the gaps grow relatively slowly. Andrew’s survey goes far into details of how the sum and its use of the function must be expanded into further sums using arithmetic progressions and the Möbius function in order for techniques of analysis to attack it. The need for estimation heightens the cancellation problem, which he emphasizes throughout his article. The issue is, as he states, of central importance in number theory:
The two sums … are not easy to evaluate: The use of the Möbius function leads to many terms being positive, and many negative, so that there is a lot of cancellation. There are several techniques in analytic number theory that allow one to get accurate estimates for such sums, two more analytic and the other more combinatorial. We will discuss them all.
As usual see his lovely article for further details. Our hope is that they could one day be used to help us with our cancellation problems.
I thought that we might look at two other strategies that can be used in complexity theory, and that might have some more general applications.
Ben Cousins and Santosh Vempala recently wrote an intricate paper involving integrals that compute volumes. At its heart however is a simple idea. This is represent a volume in the form
where is the hard quantity that we really want to compute. The trick is to select the other ‘s in a clever way so that each ratio is not hard to approximate. Yet the cancellation yields that
If is simple, and if we have another way to estimate , then we get an approximation for the hard to compute .
Let and where is a random function with expectation . Then we know that is equal to . Note that this does not need the values to be independent.
Can we use this idea to actually compute a tough sum? The sums we have in mind are inner products
where the vectors and are exponentially long but have useful properties. They might be succinct or might carry a promised condition such as we discussed in connection with an identity proved by Joseph Lagrange.
Both cases arise in problems of simulating quantum computations. Our hope is that the regularities in these cases enable one to restrict the ways in which cancellations can occur. A clever choice of dependence in the values then might interact with these restrictions. Well, at this point it is just an idea. Surveying things that boil down to this kind of idea could be another post, but for now we can invite you the readers to comment on your favorite examples.
Can we delineate methods for dealing with cancellations, also when we don’t need to estimate a sum closely but only prove it is positive?
[fixed omission of NP-oracle for Stockmeyer randomized counting]