Thanks to Kyle Pratt for enlightening discussions leading to this post.
Recall the Burgess bound which states for any interval of size at least , one has
where is the Legendre symbol modulo .
Conjecture 1: For any , (1) holds for intervals, , of size .
Conjecture 1 is one way quantify that behaves like a random sign pattern. Indeed almost surely, (1) holds for a random –valued function from .
Character sums are central objects of study in analytic number theory and such a result would have wide applications. For instance, it would solve the Vinogradov least square problem. It would also have implications to sub–convexity bounds of –fucntions, using
For instance, summation by parts and (1) gives the sub–convexity bound
The key obstacle is the famous square root barrier. In coin flips, one can change of the outcomes without affecting the global statistics, for instance in the central limit theorem. Thus when applying global statistics to problems in short intervals, one naturally arise at a square root barrier for the size of the interval.
To this end, it is no surprise that the Polya–Vinogradov inequality, that is conjecture 1 with , was proved about forty years before the Burgess bound. The Polya–Vinogradov theorem can be proved using only the global statistics of , for instance for all ,
On the other hand, the Burgess bound breaks the square root barrier, so one needs additional ideas, which we now discuss. We first use for small . Then we use the multiplicativity of to amplify an interval of size to a set of size . Finally, we use completion and apply a global statistic of (Hasse-Weil bound). Without the amplification step, this method would not work. Let us sketch the proof.
By the near translation invariance of , one has
for all and . But by the multiplicativity of ,
Now the number of ways to write an integer as is roughly one on average on a set of size , so (2) is approximately
for some of size . Since is so large, we can now efficiently complete the sum after an application of Hölder’s inequality to arrive at
This may be bounded by the following global statistic. We remark in our case, there is a short proof using the polynomial method (the proof in the note is only for elliptic curves, but is easily generalized to our situation).
Lemma 1: Let be a polynomial which is not a multiple of a perfect square. Then
Another successful instance of breaking the square root barrier is in this paper of Hanson. One result he proved was for any ,
for arbitrary of size at least . He takes advantage of the additive structure of the problem as was pioneered in this paper of Chang using Freiman’s theorem from additive combinatorics. This has the same flavor as the Burgess bound in (1) as one replaces the very additively structured interval with a sumset. The main problem along these lines is the following
Conjecture 2: For any of size at least , there is a such that
This would have an application to sparse signal recovery. One can see Bourgain’s work and the references within for the dual problem, where multiplicative character is replaced by additive character and sumset is replaced by product set.
where is the characteristic function of -smooth numbers. Thus the sum in (1) (with ) is determined solely by the values of at rather small primes. Using smooth number estimates, this implies Conjecture 1 in the case .