EDP27 — the modular version of Roth’s AP-discrepancy theorem

Recall from earlier posts Gil’s modular conjecture for HAPs. It states that if $n$ is large enough and $f$ is a function from $\{1,2,\dots,n\}$ to $\mathbb{Z}_p$ that never takes the value 0, then for every $a$ there exists a HAP $P$ such that $\sum_{x\in P}f(x)\equiv a$ mod $p$ . It is easy to see that this implies EDP, so it may well be very hard, or even false. However, one can hold out a little hope that, as with some strengthenings of statements, it is in fact easier, because it is in some way more symmetrical and fundamental. Given that, it makes good sense, as Gil has suggested, to try to prove modular versions of known discrepancy theorems, in the hope of developing general techniques that can then be tried out on the modular EDP conjecture.

A very obvious candidate for a discrepancy theorem that we could try to modularize is Roth’s theorem, which asserts that for any $\pm 1$ -valued function $f$ on $\{1,2,\dots,n\}$ there exists an arithmetic progression $P$ such that $|\sum_{x\in P}f(x)|\geq cn^{1/4}$ . That gives rise to the following problem.

Problem. Let $p$ be a prime. What is the smallest $n$ such that for every function $f:\{1,2,\dots,n\}\to\mathbb{Z}_p$ that never takes the value 0, every $a\in\mathbb{Z}_p$ can be expressed as $\sum_{x\in P}f(x)$ for some arithmetic progression $P$ ?

In this post I shall collect together a few simple observations about this question.

1. We can at least prove that such an $n$ exists. Indeed, by Szemerédi’s theorem, if $n$ is large enough then there is an arithmetic progression $P$ of length $p$ on which $f$ is constant. Since $f$ takes non-zero values and $p$ is prime, the sums along initial segments of $P$ run through all the numbers mod $p$ .

So the question is really asking whether the result can be proved with a reasonable bound for $n$ .

2. Roth’s discrepancy result tells us that if $n\geq Cp^4$ and $f$ takes only the values $\pm 1$ , then $f$ takes all values mod $p$ . That is because there is a progression $P$ such that $|\sum_{x\in P}f(x)|\geq p$ in $\mathbb{Z}$ , and by what one might call the discrete intermediate value theorem, it therefore takes all values in $\mathbb{Z}$ between 0 and $p$ or between $0$ and $-p$ . This is reasonably compelling evidence that the conjecture is true with a decent bound, but of course the intermediate-value-theorem argument breaks down completely when $f$ can take arbitrary non-zero values mod $p$ .

The known lower bounds for Roth’s discrepancy theorem for APs (which are equal to the upper bounds up to a constant) show that the best possible bound for the modular question is at least $cp^4$ .

3. To make the problem more symmetrical, and therefore potentially easier to handle, it might be a good idea to begin by tackling the following variant.

Problem. Let $p$ be a prime. What is the smallest $n$ such that for every function $f:\mathbb{Z}_n\to\mathbb{Z}_p$ that never takes the value 0, every $a\in\mathbb{Z}_p$ can be expressed as $\sum_{x\in P}f(x)$ for some arithmetic progression $P$ in $\mathbb{Z}_n$ ?

The big difference here is that arithmetic progressions are allowed to “wrap around”. That means that for every arithmetic progression $P$ and every $r$ coprime to $n$ (it might be convenient to insist that $n$ is prime), the sets $\{rx:x\in P\}$ and $\{x+r:x\in P\}$ are also progressions. I think the bounds in the integer case with $\pm 1$ functions show that the best bound one could hope for for this modified problem are $n\geq cp^2$ , but I need to check that.

3. One natural approach to proving that a function takes all values mod $p$ would be to attempt to show that it takes all values with approximately the same frequency. This would potentially allow us to bring in analytic tools. However, it is not in general true. For example, let $f$ be the function that is $-1$ up to $n/2$ and $1$ from $n/2$ to $n$ . Then a small calculation shows that if $P$ is a mod- $n$ AP of common difference $d$ , then $|\sum_{x\in P}f(x)|$ is never more than $Cn/|d|$ . I think $C$ can probably be taken to be 2, or maybe even 1. (By $|d|$ I mean the smallest modulus of any number congruent to $d$ mod $n$ .) Thus, for a positive proportion of common differences $d$ , the sums along APs of common difference $d$ never exceed $10$ , say, in modulus. If $p$ is large, this implies that the values of the sums $\sum_{x\in P}f(x)$ are very far from uniformly distributed, since they are concentrated around 0. On the other hand, $f$ is obviously not a counterexample to the conjecture (by which I mean the assertion that the modular statement holds with a good bound).

4. That observation does not rule out a proof that goes via showing that the values of sums along APs are approximately uniformly distributed, but it does demonstrate that in order to prove that, we would have to put some conditions on $f$ . That is, we would need a two-step argument along the following lines (reminiscent of proofs of Szemerédi’s theorem, though I would hope that this problem is easier).

(i) If $f$ is quasirandom, or at least “contains substantial quasirandomness”, then the values of $\sum_{x\in P}f(x)$ are approximately uniformly distributed mod $p$ .

(ii) If $f$ is not quasirandom, or better still “does not contain substantial quasirandomness”, then we can deduce in some other way (such as finding a long AP on which $f$ is constant, but that may be too much to ask) that the sums take all values.

5. The weaker the property we can get away with in (i), the better. However, in order to get started it would be good to find any quasirandomness property that implies that the values of $\sum_{x\in P}f(x)$ are approximately uniformly distributed.

6. One thing that needs deciding here is what we mean by a random progression $P$ . The simplest would be to fix some $m$ and pick random mod- $n$ APs of length $m$ . These don’t work for the modular conjecture in general, since the constant function $f(x)\equiv 1$ is a counterexample, but they might work for functions with a suitable quasirandomness property.

7. The fact that we can’t fix the length of the progressions shows that the modular conjecture differs in an important way from Roth’s discrepancy theorem, where fixing the length is not a problem (especially in the mod- $n$ version). This dampens any hopes one might start off with for adapting the proof of Roth’s discrepancy theorem to cope with the modular version. But that might in the end be a good thing, since the point of the modular conjecture is to introduce new techniques that can then be brought to bear on EDP.

8. When we are looking for a suitable quasirandomness property, it is tempting to turn to Fourier analysis. However, the following (modification of a standard) example is a bit troubling. Let $f$ be defined as follows. For each $x$ we randomly decide whether to set $f(x)$ equal to $\pm x^2$ or $\pm 3x^2$ mod $p$ (where $x$ is the residue between 0 and $n-1$ ). If we now choose a random mod- $n$ arithmetic progression $P=\{a,a+d,a+2d,a+3d\}$ of length 4, there is an absolute constant $\theta>0$ such that with probability at least $\theta$ $P$ does not wrap around, and $f(a)=a^2, f(a+d)=-3(a+d)^2, f(a+2d)=3(a+2d)^2$ , and $f(a+3d)=-(a+3d)^2$ . When this happens $\sum_{x\in P}f(x)=0$ . Therefore, the value 0 occurs much too often, but according to the natural Fourier definitions of quasirandomness (which we could get by looking at the function $\exp(2\pi if(x)/p)$ ) this function $f$ is highly quasirandom.

9. Of course, we are looking at much longer arithmetic progressions. However, it is difficult to think of proofs that work for long arithmetic progressions and fail for short ones. (It is mildly encouraging that at least the above source of examples seems to break down when the progressions become long — though that should be checked carefully.)

10. Hmm … just after writing that I thought of the following modified example. Instead of choosing randomly whether to set $f$ equal to $\pm x^2$ or $\pm 3x^2$ , let’s do it in the following highly deterministic way: if $x\equiv 0$ mod 4 we set $f(x)$ equal to $x^2$ , if $x\equiv 1$ mod 4 we set it equal to $-3x^2$ , if $x\equiv 2$ mod 4 we set it equal to $3x^2$ , and if $x\equiv 3$ mod 4 we set it equal to $-x^2$ . In addition, let’s suppose that $n$ is a multiple of $4p$ , since I seem to need that to make this example work. (Even if we can’t get rid of this restriction somehow, it will still show that a proof that worked for prime values of $n$ would have to make strong use of the fact that $n$ was not a multiple of $4p$ — and there would be many other examples of a similar kind that would lead to similar requirements — which would be quite a big restriction on what it could look like.)

Then if $m$ is a multiple of 4 and $P=\{a,a+d,\dots,a+(m-1)d\}$ is a random mod- $n$ AP of length $m$ , there is a probability 1/16 that $a\equiv 0$ and $d\equiv 1$ mod 4. (Note that because $4|n$ this makes sense independently of which residue we pick.) If that is the case, we can partition $P$ into APs $P_i$ of length 4 such that the sum of $f$ along each $P_i$ is zero. This shows that with probability at least 1/16 the sum $\sum_{x\in P}f(x)$ is 0 mod $p$ .

Is this function $f$ quasirandom? According to many definitions, yes, since although we split into cases in a highly structured way, the behaviour of each case of $f$ is highly quasirandom.

I mentioned above that there are many similar examples. To give just one illustration, we could take $n$ as a multiple of $5p$ and let $f$ take turns taking values $x^3$ , $-4x^3$ , $6x^3$ , $-4x^3$ and $x^3$ . Essentially the same argument would work, but now the probability would be $1/25$ . (Actually, I now see that the probabilities can be doubled in both cases, since $d\equiv -1$ works just as well as $d\equiv 1$ .)

I’ll leave it there. I’ve mentioned some proof strategies, and also discussed some difficulties with them. Does anyone have other proof strategies to suggest? I haven’t mentioned using the polynomial method, but that is an obvious thing to try to do: that is, write down a polynomial that vanishes identically only if the modular conjecture for APs is true, and try to prove that it vanishes identically. It is certainly worth looking into that, though it is a little discouraging that the conjecture is false for APs of any fixed length, since that would necessarily make the polynomials less symmetrical. If the above strategy seems the most promising (or should that be least unpromising?) then does anyone have any thoughts about quasirandomness properties that might do the job? (Gil mentioned something in a recent comment — it would be good to have that thought in more detail.)

I’ll end by saying that even if proving the modular conjecture for mod- $n$ APs ended up having nothing much to do with EDP, it is a very nice problem on its own, and could make an excellent spin-off Polymath project.

12 Responses to “EDP27 — the modular version of Roth’s AP-discrepancy theorem”

gowers Says:
September 19, 2012 at 11:23 pm | Reply
A thought about the last example (in point 10 in the post) that might perhaps be the basis for an appropriate definition of quasirandomness is that the example is set up in such a way that the sum $\sum_{x\in Q}f(x)$ is zero for many short progressions $Q$ . This helps to ensure that many longer progressions give rise to the same sums. For different reasons, many sums over short APs are zero in the example with lots of 1s and lots of -1s.

So perhaps what we want is not a quasirandomness property, but simply a property that says in some way or other that there are not too many short APs along which the sum is zero. It would still be helpful for this property to be as weak as possible, so that if it fails we can get as much structural information as possible about the function $f$ .

Note that the proportion of APs (of all lengths) along which the sum is zero is at least $p^{-1}$ . To see this, consider APs of common difference 1. For each $a$ let $n(a)$ be the number of $m$ such that $\sum_{x=0}^{m-1}f(x)=a$ . Then the number of pairs $(s,t)$ such that the sums $\sum_{x=0}^{s-1}f(x)$ and $\sum_{x=0}^{t-1}f(x)$ are both equal to $a$ is $n(a)^2$ . Therefore, the number of sums $\sum_{x=s}^{t-1}f(x)$ equal to zero is at least $\sum_an(a)^2$ . Since $\sum_an(a)=n$ and there are $p$ different values of $a$ , $\sum_an(a)^2\geq n^2/p$ , which is a proportion $1/p$ of all APs mod $n$ of common difference 1. Then one can do the same for the other common differences.
Gil Kalai Says:
September 20, 2012 at 2:15 am | Reply
Maybe, if f is not quasirandom then f is even less quasirandom on an AP?
Anthony Wang Says:
October 15, 2012 at 2:37 am | Reply
This seems like something someone might have tried already, but I don’t see it on the general strategies list, so here goes.

The strategy is to rephrase the question in terms of power series. Given a $\pm 1$ valued sequence $a_1,a_2,\cdots$ , we can associate a power series

$p(z) = a_1z+a_2z^2+\cdots$

which has radius of convergence 1.

The benefit of this approach is that we can use the following trick to remove the terms not divisible by some integer $n$ : let $\zeta=e^{2\pi i/n}$ be a primitive $n$ th root of unity. Then the function

$p_n(z)= \frac{1}{n} \sum_{i=0}^{n-1} p(\zeta^i z)$

removes all $a_i$ with $i$ not divisible by $n$ .

So the plan is to get a good understanding of which $p(z)$ will have bounded partial sums when $z=1$ , and then apply it to each of the functions $p_n(z)$ to get a better understanding of the problem.

As an example, if we are going to restrict to complex numbers, we should probably expect that $p_n(z)$ do not have any poles at 1. Then, we can check this for the sequence 1,-1,0,1,-1,0,… Its associated power series is

$p(z)=z-z^2+z^4-z^5+\cdots = \frac{z(1-z)}{1-z^3} = \frac{z}{(z-\omega)(z-\omega^2)}$ ,

where $\omega=e^{2\pi i/3}$ . Note that $p_n(z)$ will clearly not have a pole when $n$ is not divisible by 3. In the case when $3|n$ , it turns out that the poles ‘cancel’:

$p(\omega z)+p(\omega^2 z)=\frac{z(\omega+1)}{\omega(z-\omega)(\omega z-1)}$ ,

where we ended up taking out a $z-1$ from both the top and the bottom. We can then conclude that $p_n(z)$ will also not have any poles when $n$ is divisible by 3.

(Note: I am actually an undergrad at MIT taking complex analysis right now, so I don’t understand much of what you guys say (yet! hopefully I will someday). Sorry if you already knew this or it doesn’t help).
The Quantum Debate is Over! (and other Updates) | Combinatorics and more Says:
October 15, 2012 at 4:56 am | Reply
[…] posts on the Erdos Discrepancy Problem over Gowers’s blog (Here is the link to the last one EDP27). Tim contributed a large number of comments and it was interesting to follow his line of thought. […]
Liz Says:
October 18, 2012 at 1:46 pm | Reply
Hi there,

My name is Liz. I am a blogger at thefactortree.com – an adaptive/interactive online math learning curriculum. We focus on students from the pre-k to the 6th grade. I apologize for posting the info on here but I was unable to find the contact information for you.

I just came across your blog and thought you have some great content on here, so I wanted to reach out to you and see if you would be interested in checking out our site and providing us with some feedback? We’ve added new features, new blog content are currently working on revamping our site – the new version should be out by the end of the month. If you like our service (which is currently free to use- but not for long), would you be willing to write about it? Please let me know as that would be incredibly helpful for us. We are always looking to partner with other education online sources so we would very much appreciate your feedback – you also wrote about Educator.com. I hope to hear from you.

Regardless, thanks for writing and enjoy your day.

Thank you, Liz

We hope you check out our Facebook.com/FactorTree and Twitter.com/FactorTree pages to get to know us better.
Liz Says:
November 6, 2012 at 7:07 pm | Reply
Hi there, just checking in with you, I don’t know if you were hit by super storm Sandy but I hope you are doing well. If you have a minute or so, I hope you check out our site, thefactortree.com, and provide us with some feedback, that would be greatly appreciated. Thanks. -L
A.Czuron Says:
December 6, 2012 at 3:47 pm | Reply
Does HAP of length 1 are satisfactory?
For example if we have sequence x=(1,2,3,4) and we want to find r=4(mod 5), dose the answer is HAP= {x_4}?
Vedic Mathematics Says:
December 25, 2012 at 6:28 am | Reply
Nice solutions is given by author.
Thomas Says:
August 20, 2013 at 8:12 am | Reply
What happened to the revival? It has been almost a year, and no posts since then have been about EDP.
Terence Tao Says:
February 11, 2014 at 4:35 pm | Reply
There’s a new paper on the arXiv using SAT solvers to show that all sequences longer than 1160 have discrepancy greater than 2, and that this is best possible: http://arxiv.org/abs/1402.2184
- gowers Says:
  February 11, 2014 at 7:54 pm
  I was just in the middle of writing a brief post about it!
EDP Reflections and Celebrations | Combinatorics and more Says:
October 22, 2015 at 8:30 am | Reply
[…] the situation is for EDP (see this post), and also for Roth’s theorem for general AP (see this post). Gowers introduced yet another extension of discrepancy which again can be adapted to arbitrary […]