Recall from earlier posts Gil’s modular conjecture for HAPs. It states that if is large enough and
is a function from
to
that never takes the value 0, then for every
there exists a HAP
such that
mod
. 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 -valued function
on
there exists an arithmetic progression
such that
. That gives rise to the following problem.
Problem. Let be a prime. What is the smallest
such that for every function
that never takes the value 0, every
can be expressed as
for some arithmetic progression
?
In this post I shall collect together a few simple observations about this question.
1. We can at least prove that such an exists. Indeed, by Szemerédi’s theorem, if
is large enough then there is an arithmetic progression
of length
on which
is constant. Since
takes non-zero values and
is prime, the sums along initial segments of
run through all the numbers mod
.
So the question is really asking whether the result can be proved with a reasonable bound for .
2. Roth’s discrepancy result tells us that if and
takes only the values
, then
takes all values mod
. That is because there is a progression
such that
in
, and by what one might call the discrete intermediate value theorem, it therefore takes all values in
between 0 and
or between
and
. 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
can take arbitrary non-zero values mod
.
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 .
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 be a prime. What is the smallest
such that for every function
that never takes the value 0, every
can be expressed as
for some arithmetic progression
in
?
The big difference here is that arithmetic progressions are allowed to “wrap around”. That means that for every arithmetic progression and every
coprime to
(it might be convenient to insist that
is prime), the sets
and
are also progressions. I think the bounds in the integer case with
functions show that the best bound one could hope for for this modified problem are
, but I need to check that.
3. One natural approach to proving that a function takes all values mod 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
be the function that is
up to
and
from
to
. Then a small calculation shows that if
is a mod-
AP of common difference
, then
is never more than
. I think
can probably be taken to be 2, or maybe even 1. (By
I mean the smallest modulus of any number congruent to
mod
.) Thus, for a positive proportion of common differences
, the sums along APs of common difference
never exceed
, say, in modulus. If
is large, this implies that the values of the sums
are very far from uniformly distributed, since they are concentrated around 0. On the other hand,
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 . 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 is quasirandom, or at least “contains substantial quasirandomness”, then the values of
are approximately uniformly distributed mod
.
(ii) If 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
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 are approximately uniformly distributed.
6. One thing that needs deciding here is what we mean by a random progression . The simplest would be to fix some
and pick random mod-
APs of length
. These don’t work for the modular conjecture in general, since the constant function
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- 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 be defined as follows. For each
we randomly decide whether to set
equal to
or
mod
(where
is the residue between 0 and
). If we now choose a random mod-
arithmetic progression
of length 4, there is an absolute constant
such that with probability at least
does not wrap around, and
, and
. When this happens
. 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
) this function
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 equal to
or
, let’s do it in the following highly deterministic way: if
mod 4 we set
equal to
, if
mod 4 we set it equal to
, if
mod 4 we set it equal to
, and if
mod 4 we set it equal to
. In addition, let’s suppose that
is a multiple of
, 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
would have to make strong use of the fact that
was not a multiple of
— 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 is a multiple of 4 and
is a random mod-
AP of length
, there is a probability 1/16 that
and
mod 4. (Note that because
this makes sense independently of which residue we pick.) If that is the case, we can partition
into APs
of length 4 such that the sum of
along each
is zero. This shows that with probability at least 1/16 the sum
is 0 mod
.
Is this function quasirandom? According to many definitions, yes, since although we split into cases in a highly structured way, the behaviour of each case of
is highly quasirandom.
I mentioned above that there are many similar examples. To give just one illustration, we could take as a multiple of
and let
take turns taking values
,
,
,
and
. Essentially the same argument would work, but now the probability would be
. (Actually, I now see that the probabilities can be doubled in both cases, since
works just as well as
.)
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- 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.
September 19, 2012 at 11:23 pm |
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
is zero for many short progressions
. 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
.
Note that the proportion of APs (of all lengths) along which the sum is zero is at least
. To see this, consider APs of common difference 1. For each
let
be the number of
such that
. Then the number of pairs
such that the sums
and
are both equal to
is
. Therefore, the number of sums
equal to zero is at least
. Since
and there are
different values of
,
, which is a proportion
of all APs mod
of common difference 1. Then one can do the same for the other common differences.
September 20, 2012 at 2:15 am |
Maybe, if f is not quasirandom then f is even less quasirandom on an AP?
October 15, 2012 at 2:37 am |
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
valued sequence
, we can associate a power series
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
: let
be a primitive
th root of unity. Then the function
removes all
with
not divisible by
.
So the plan is to get a good understanding of which
will have bounded partial sums when
, and then apply it to each of the functions
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
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
where
. Note that
will clearly not have a pole when
is not divisible by 3. In the case when
, it turns out that the poles ‘cancel’:
where we ended up taking out a
from both the top and the bottom. We can then conclude that
will also not have any poles when
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).
October 15, 2012 at 4:56 am |
[…] 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. […]
October 18, 2012 at 1:46 pm |
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.
November 6, 2012 at 7:07 pm |
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
December 6, 2012 at 3:47 pm |
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}?
December 25, 2012 at 6:28 am |
Nice solutions is given by author.
August 20, 2013 at 8:12 am |
What happened to the revival? It has been almost a year, and no posts since then have been about EDP.
February 11, 2014 at 4:35 pm |
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
February 11, 2014 at 7:54 pm
I was just in the middle of writing a brief post about it!
October 22, 2015 at 8:30 am |
[…] 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 […]