The Polynomial Method
The polynomial method is another basic combinatorial technique that occasionally works. One way to describe the method is as a way to translate a combinatorial statement into the vanishing of a certain polynomial modulo .
A demonstration of the method
Theorem: Every graph (or hypergraph) G with n vertices and 2n+1 edges contains a nontrivial subgraph H with all vertex-degrees divisible by 3.
(This is a theorem of Noga Alon, Shmuel Friedland, and me from 1984.)
Before the proof: If we want to get a subgraph with all vertex degrees even then we need n edges (or n+1 edges for hypergraphs). This has a simple linear algebra proof which also gives an efficient algorithm.
From-scratch proof sketch: Associate with every edge e of the graph a variable . Consider the two polynomials
P=
, and
Q=
If the theorem is false then P-Q=0, as polynomials over the field with three elements. This is impossible since P is a polynomial of degree 4n while Q is a polynomial which has a monomial of degree 4n+2 with nonzero coefficient.
The theorem follows more directly from a theorem of Chevalley-Warning and even more directly from a theorem of Olson, but the above proof serves best our purpose.
Remarks about the polynomial method:
1) The polynomial method has many applications but only in specific cases. It is not nearly as widely applicable as, say, the probabilistic method.
2) Good basic references: A. Blokhuis, Polynomials in finite geometries and combinatorics. In Keith Walker, editor, Surveys in Combinatorics, 1993, pages 35-52. Cambridge University Press, 1993.
Noga Alon, Combinatorial Nullstellensatz, Combinatorics, Probability and Computing 8 (1999), 7-29.
3) The polynomial method is related to the “linear algebra method” in combinatorics. Often, however, direct linear algebraic proofs lead to efficient algorithms while this is not known for applications of the polynomial method. For example, no polynomial algorithm to find the graph H in the above theorem is known, and there is a related complexity class introduced by Christos Papadimitrou . The polynomial method is closely related to arguments coming from the theory of error-correcting codes, and to arguments in TCS related to interactive proofs and PCP.
The modular EDP.
The following is an equivalent way to formulate the Erdős 1932 conjecture that the discrepancy for EDP is unbounded.
1) Consider the sequence as a sequence with
modulo
, where
is a prime that we can choose as large as we want.
2) Then every number modulo can be expressed as a sum of the sequence along a HAP modulo
.
Translating EDP (in this form) into a statement about polynomials modulo is cumbersome. But one thing we may have going for us is that it suggests a natural extension of EDP where the supposed-to-vanish polynomial is simpler.
Modular EDP Conjecture: Consider a sequence of non-zero numbers modulo p. Then if n is sufficiently large w.r.t. p, then every number can be expressed as a sum of the sequence along a HAP modulo p.
As in the original EDP we can consider general sequences or just multiplicative sequences.
The Polynomial identity required for the modular EDP
Here is the polynomial identity in n variables we need to prove over
when
grows to infinity with
as slow as we wish. For every
,
,
(*)
These polynomials are not familiar but they are related to generating functions which arise in permutation statistics. In particular, when we look at the product
and expand it to monomials, the coefficients have a combinatorial meaning in terms of permutations and inversions.
Given a permutation , and an integer
we can ask how many inversions are there between
and a smaller integer. This is a number between 1 and
.
The coefficient of in the above product is the number of permutations where there are
integers contributing j inversions. The proposed identity (*) may be expressed in terms of modular properties of such permutation statistics.
Challenge: Prove the modular EDP using the polynomial method.
What does the LDH tell us about the modular EDP?
It is especially easy to apply the large deviation heuristic to the modular version of EDP. Suppose we want to compute the probability that all HAP-sums miss the outcome .
Given , the probability that
is not
is
. So we are interested in the value of
with
. (Restricting our attention to multiplicative sequences will divide the exponents on both sides by
.) Solving this equation gives us
. The LDH heuristic comes with a firm prediction and a weak prediction. In this case the LDH gives
a) (Firm prediction) There are sequences violating the modular EDP when .
b) (Weak prediction) There are no such sequences when .
The firm prediction is correct by the logn discrepancy constructions for EDP and as a matter of fact the LDH itself gives an even stronger prediction of for
-sequences. By restricting our attention to
sequences we see that the weak prediction is incorrect and LDH for the modular EDP is blind to the special substructure of
sequences. Note that the firm conjecture is far from being known when we extend the modular EDP and replace all integers by a random subset of integers, or by square-free integers , or by SCJ-systems of integers etc.
September 5, 2012 at 7:37 am |
[…] EDP25 — third guest post by Gil Kalai « Gowers's Weblog […]
September 5, 2012 at 4:59 pm |
It might be interesting to search for long sequences of non-zero numbers mod 7 such that no sum along a HAP is equal to
mod 7. We have some very long
sequences with this property. If we allow the sequence to take the values
as well, does it help? Indeed, even the occasional
would allow us to jump from 2 to -2 or the other way. So the question I’m basically asking here is whether avoiding
mod 7 for arbitrary sequences of non-zero numbers mod 7, which in theory is strictly easier than avoiding
when the sequence has to be
-valued, is enough easier to allow us to find examples of length greater than 1124.
September 6, 2012 at 2:19 am
Dear Tim, I remember there was some experimental data on the modular EDP in the first rounds of discussion. (But I dont remember larger than 1124 numbers)
September 6, 2012 at 2:30 am
Here are two relevant comments from the oldere threads
https://gowers.wordpress.com/2010/03/02/edp10-a-new-and-very-promising-approach/#comment-6557
and
https://gowers.wordpress.com/2010/03/07/edp11-the-search-continues/#comment-6597
September 5, 2012 at 5:53 pm |
Thinking more naively about the modular problem, if one attempts to find a counterexample, then the way things will go wrong is if one can find a number
with factors
(and maybe others) such that the sums along the HAPs
are all distinct. So the points where things get difficult will be numbers with quite a lot of factors.
Another very minor remark is that if we are trying to prove the modular conjecture for a pair
, then we have to consider a set of HAPs that is linearly dependent, since otherwise we can choose the sums to be whatever we like just by solving some simultaneous equations. Of course, just having a few dependences around isn’t a problem, since we don’t have to make the sums equal to specific values — we just have to avoid some value. Nevertheless, it might be worth looking for interesting dependencies between HAPs (of course, I’m referring to characteristic functions of HAPs mod
).
September 5, 2012 at 6:02 pm |
Just for fun, here’s a greedy approach mod 7. I’m going to try to avoid the number 0 as a sum along any HAP, and at each stage I’ll choose the smallest number mod 7 that I can. (That is, my first choice will be 1, my second choice 2, etc. I’m not allowed to choose 0, not that I’d want to.) I’ll bunch it into groups of 7 numbers to make it easier to read
It starts 1,1,1,1,1,1,2; 1,1,1,1,1,2,2; 1,1,1,3,1,1,1; and then gets a bit tedious to work out by hand. It would be interesting to know how far a greedy approach like this can go. And if it’s allowed to do a small amount of backtracking, can it go much much further?
September 6, 2012 at 3:19 am
If I did this correctly, it looks like the limit without backtracking is length 47.
1, 1, 1, 1, 1, 1, 2; 1, 1, 1, 1, 1, 2, 2; 1, 1, 1, 3, 1, 1, 1
3, 1, 1, 1, 1, 1, 4; 1, 4, 1, 1, 1, 2, 2; 1, 1, 1, 1, 5, 1, 2
2, 1, 3, 1, 2
With backtracking after about 20 minutes it seems to be stuck at 298: http://paste.ubuntu.com/1188167/
September 6, 2012 at 3:39 am
The output was truncated in the above pastebin, it was actually 299: http://paste.ubuntu.com/1188186/
September 6, 2012 at 8:01 am
Thinking about it a little further, it seems quite likely that avoiding 0 is harder than avoiding a non-zero number. In particular, I don’t see how to convert a counterexample to EDP into a sequence mod
that avoids 0.
But actually that might make the avoiding-0 problem an interesting one (even if it doesn’t help with EDP). Here is the formal statement. Suppose we have a sequence
of integers mod
. Is there always a HAP along which the sum of the sequence is zero? If so, how long can the sequence be (as a function of
) before the zero sum is forced to appear?
September 6, 2012 at 9:27 am
Gil’s comment above with links to earlier comments in it got sent to the moderation queue so I have only just seen it. I now realize, after looking at the links, that I am playing catch-up a bit here. Anyhow, here’s another small thought about the avoiding-0 problem (though I think something similar can be said about avoiding a non-zero residue).
Let’s consider the following very general problem. You have a collection
of subsets of
and a prime
and you want to determine whether there exists a sequence
such that
for every
. We are interested in the case where
is large and
is the set of all HAPs in
.
When
the problem can be solved in polynomial time, since it is asking for every sum to equal 1, so all we have to do is solve some simultaneous equations. But for
we are looking at intersections of complements of subspaces that are not affine subspaces themselves. This is highly reminiscent of 3-SAT, so I would guess that it is an NP-complete problem. (In fact, my guess is that it is a known NP-complete problem — does anyone recognise it?)
That doesn’t mean we can’t solve the problem in the case where
is the set of HAPs, but it suggests that we will have to use the structure of that set in a very strong way, so that there is no question of being able to extract from the proof a general procedure for determining whether zero sums exist. The polynomial method seems not to be ruled out by this consideration, since we can hope to use the structure of HAPs to say strong things about coefficients that we would not be able to say about general set systems. What does seem to be ruled out is any kind of approach based on finding a solution to a set of linear equations — such as a clever decomposition of matrices.
September 8, 2012 at 9:56 am |
I’ve thought of a further strengthening of the strong modular conjecture. It could well be false, but if it’s true it might be a helpful approach to the conjecture.
To motivate it, let’s think about how one might go about proving the strong modular conjecture in an elementary way (rather than using the polynomial method — though I certainly think the polynomial method should be investigated too). One idea is to imagine trying to build a counterexample. Each time you get to a number, it will be contained in a certain number of HAPs (one for each factor), along which the sums of the sequence will be
, say. If you are trying to avoid the number
, that tells you that at this number you must not let your function equal
for any
.
Assuming the modular conjecture is true, this will presumably become harder and harder. That is, as you choose more and more of your sequence, you will find that you are facing more and more forbidden values. My suggested strengthening is that eventually you cannot avoid a point
such that as you run through its factors
the sums along the HAPs
take
different values. None of those values can be the forbidden value, so the sums take all the values except
. Therefore, if you choose a non-zero value for
, you can’t help one of the resulting HAP sums being
. Note that there is a slight resemblance between this and the colour-focusing proof of van der Waerden’s theorem.
This is a very much stronger statement than the modular conjecture itself, since for the modular conjecture all you need is to find
different HAPs with different sums: you don’t need them to be the HAPs that correspond to factors of some single number
. Because it is so much stronger, it seems sensible to begin by trying to find a simple counterexample. In the unlikely event that that turns out to be hard enough that there is a chance that the strengthening is true, one could hope for a proof strategy such as one has for van der Waerden’s theorem: one would devise a clever inductive hypothesis — something to do with there being many points with many forbidden values, but it is far from clear what the statement should be — and prove that as
got bigger and bigger you ruled out more and more until eventually you were forced to rule out everything.
September 8, 2012 at 10:04 am
Let me try to explain in a different way why it’s a strengthening, since I’m having slight doubts. Suppose that this conjecture is false. Does it allow us to build a counterexample to the strong modular conjecture? At first the answer might seem to be yes: you just keep on defining values and at each stage there are at most
forbidden values so you can pick a non-zero value that isn’t forbidden. But who says you can do that? If the very strong conjecture is false, all it gives you is two functions
and
such that none of the sums
takes the forbidden value. So you can change the value of
to avoid HAPs that end at
going wrong, but you can’t do that for all
simultaneously.
That reformulation in terms of two functions makes it clearer just how much of a strengthening it would be if the very strong conjecture turned out to be true.
September 8, 2012 at 11:23 am
Tim, can you please formulate the strengthening again.
September 8, 2012 at 11:48 am
OK, here are two (I think equivalent) versions.
1. For every prime
and every function
there exists
such that the sums
(where
runs over factors of
) take at least
distinct values.
2. For every prime
, every
and every pair of functions
there exists a HAP
such that
mod
.
September 8, 2012 at 3:26 pm
Actually, the equivalence doesn’t quite work. Let me prove what I can. If 1 holds and you have a pair of functions
, then choose
such that the sums
take at least
distinct values. What I’m missing here is the assumption that none of these values is the forbidden value. If I knew that too, then I’d be able to argue that since
, then there must exist
such that
does take the forbidden value. But I don’t have that assumption.
Maybe I want to replace 1 by what I originally intended, which is to say that there exists
such that the sums
take all
possible values. Of course, that trivially implies the strong modular conjecture, since one of those values is forbidden, but it is clearly a stronger statement, since there is nothing to stop any particular HAP taking any particular value. Let me call that statement number 3.
Let me see whether 2 and 3 are equivalent. If 3 holds, then you can’t choose a value for
, since that will force all
different sums and one of them will have to equal
. Conversely, if 3 doesn’t hold, then let
be such that for every
there are at most
distinct values of
as d ranges over the factors of
. Then let
be a value not taken and set
.
That doesn’t quite work because
might be zero. So after all that, let me formulate four questions, of which the last two are equivalent. The first two were given in the previous comment. The other two are these.
3. For every prime
and every function
there exists
such that the sums
take all
possible values as
ranges over the factors of
.
4. For every prime
, every
, every function
and every function
there exist
and
such that
mod
.
I think all four of them imply the strong modular conjecture. It is also trivial that 3 implies 1 and 4 implies 2.
September 8, 2012 at 3:36 pm
Another way of thinking about statement 3 is this. The strong modular conjecture says that you cannot avoid a HAP along which the sum is
. This conjecture says that even if the value you are avoiding is allowed to depend on the maximum element of the HAP, you still can’t avoid it. (The word “conjecture” is not very appropriate because I still think it might be too strong to be true.)
September 8, 2012 at 4:00 pm |
I’m now going to strengthen the modular conjecture so much that it will be a miracle if it is true. So — in the full expectation of spotting a counterexample within seconds of formulating the statement — here goes. I want to remove addition from the problem and preserve just one thing: that if you add a non-zero number mod
then what you get is different from what you had before.
What that tells you is that as you take partial sums along a HAP, you have a sequence such that no two consecutive values are the same. So let’s now take a two-variable function
with values in
the property that
for every
and
. Must there exist pairs
such that
and the values of
are all distinct?
The answer must surely be no. A first step towards finding a counterexample might be to try to find an example with the stronger property that
depends only on
. Hmm — but maybe that’s too strong. I have to go now but will think about this later.
September 8, 2012 at 6:43 pm
Oops — that was a bad conjecture, even for one that was probably going to be false. Just make
take one value if
is odd and another if it is even. Then the condition is satisfied and you only use up two values.
September 8, 2012 at 6:52 pm
Let
be a function that never takes the value zero and let
for every
. What properties of interest does
have? It’s difficult to formulate any that don’t involve addition in some way. For example, we know that if
is a factor of
then
, so the right-hand side has to be independent of
. But that involves addition and allows us to reconstruct
, so it doesn’t naturally lead to an interesting strengthening.
September 8, 2012 at 7:34 pm
Actually, that last observation does at least give rise to some condition that can be stated without reference to addition. Since
for any two factors
of
, it follows that
if and only if
. To phrase that differently, if
, then
if and only if
.
Unfortunately, that still doesn’t rule out the trivial example of colouring
according to the parity of
.
In general, I’m trying to find a strengthening of the strong modular conjecture that can be stated as a colouring problem. But I’m coming to the conclusion that such a strengthening doesn’t exist (or at least doesn’t exist without being either too complicated to be worth stating or else boringly and trivially false).
September 9, 2012 at 12:12 am |
Here’s a question that I thought was relevant until I tried to explain the relevance and failed. Now I just think it’s a question that is interesting if it doesn’t have too easy an answer. Let’s define a graph on the positive integers by joining
to
for any two positive integers
and
. Equivalently, we join
to
if
is the highest common factor of
and
. Is the chromatic number of this graph finite?
September 9, 2012 at 7:35 am
I think we can colour the numbers from
to
using
colours, by letting the colour of
(where
is odd) be
. Can this be improved?
September 9, 2012 at 7:58 am
… Well, it can certainly be improved for small
. For example, one can colour the numbers from 1 to 8 using three colours:
September 9, 2012 at 9:19 am
I think I see why the chromatic number must be infinite. If it is finite, say
, let
be such that
colours are needed to colour
. Then
colours must be needed to colour
. But this means we can’t colour
with any of those
colours, a contradiction.
September 9, 2012 at 2:50 pm
Nice. Let me explain why I briefly thought that an infinite chromatic number would imply EDP and why I was wrong. I’m doing that just in case something else can be done with this circle of ideas.
Suppose we have a function
. If
never takes zero values, then as you take partial sums along a HAP, you never have the same value twice in succession. That is, the partial sum up to
is never the same as the partial sum up to
. So we have a
-colouring of
such that no two integers of the form
and
have the same colour. Therefore if the chromatic number of that graph is infinite, we have a proof of the strong modular conjecture, and hence of EDP.
I’ve tried to present that argument in a way that will make it sound plausible if you read it quickly, but it is total nonsense. That’s because it confuses “partial sum up to
” with “partial sum up to
along the HAP of common difference
“. Those are two completely different things, and because they are different there is no argument.
An even stronger reason to be suspicious of the argument is that it proves a blatantly false fact: that for every function
you can find a HAP such that the partial sums along that HAP take the same value twice in succession somewhere. If
is constantly 1, then that is not the case.
Nevertheless, I feel as though the fact that the chromatic number is infinite might not be completely irrelevant — it tells us at least something about the structure of HAPs, and with a bound that is encouragingly large. (Not just encouragingly large, but rather amusing: something like
where there are
factorial signs, except that it’s slightly larger and a bit more complicated than that.) More to the point, the lower bound is large too.
September 9, 2012 at 3:07 pm
I’m just thinking aloud here, rather than making a serious suggestion, but here is a statement that would imply EDP: that if you colour
with finitely many colours, then you can find arbitrarily long monochromatic generalized HAPs (that is, sets of the form
).
That is so much stronger than van der Waerden’s theorem that it surely has to be false. But you’ve just proved it for progressions of length 2. If true, then it would imply the strong modular conjecture, since you’d just have to find a HAP where
took the same (non-zero) value
times in a row.
September 12, 2012 at 1:54 pm
So this the same as saying that for any fixed number of colours you can find a monochromatic generalized HAP of any length.
Unless I am missing some obvious obstruction that doesn’t sound unreasonable.
If it is false it would provide an interesting hypergraph, with each geneneralized HAP as an edge, with bounded chromatic number.
( I’m having a busy month but I am trying to catch up with the discussion so far )
September 12, 2012 at 2:07 pm
It is false — see the next few comments.
September 12, 2012 at 3:22 pm
Ah. That’s what happens when commenting before having time to read all the comments. But at least it provides an interesting hypergraph.
September 9, 2012 at 3:56 pm |
I’m going to try to settle the question I raised at the end of the replies to the previous comment. The question was this. Is it true that for every
and every
if you colour
with
colours then you can find a monochromatic arithmetic progression of the form
? It will be a miracle if the answer is yes, but since that would (if I haven’t made a silly mistake) imply EDP, it seems worth checking.
I probably ought to start by trying to find a counterexample, but instead I want to start by trying to generalize Alec’s proof for
in a van der Waerdenish way.
One thing we can use Alec’s argument to do is find, for any
, positive integers
such that the colours of the numbers
are the same as the colours of the numbers
. Does that help? It seems not to: for instance, the pair
does not appear consecutively along a HAP. It is somehow too additive.
For a colour-focusing argument, I want a whole lot of monochromatic pairs of the form
such that all the
are the same. Actually, that would be just for two colours, but let’s start with that. I have two colours and I want an AP of length 3. If I can find
such that … hmm, I don’t think this is working. I’ll think about counterexamples after all.
September 9, 2012 at 4:05 pm |
Let me consider colourings that depend only on the largest power of 2 that divides a number. Those can’t work (for progressions of length 3, that is), and here is the simple proof. Pick
such that numbers such that
is the highest power and numbers such that
is the highest power get the same colour. Then the generalized HAP
is monochromatic.
Ah, but the statement is false for progressions of length 4, and here’s the simple proof. Colour according to the parity of the power. Out of four consecutive integers, two are odd and one is an odd multiple of 2. Therefore, out of four integers
at least one will have an odd power of 2 as the highest that divides it and at least one will have an even power of 2.
September 9, 2012 at 4:13 pm
Although it wouldn’t have much to do with EDP, I feel a sort of moral obligation to sort out the case of progressions of length 3.
Ah — got it. Every number can be written in the form
or
. Let’s colour them according to which we get. Given numbers
, let’s suppose that
is of the form
. Then at least one of
is congruent to 1 mod 3 and at least one is congruent to 2 mod 3. When we multiply those by
, then they get different colours.
So the result is false even for two colours.
September 9, 2012 at 4:14 pm
It’s sort of interesting that if we make one of those colours 1 and the other -1 then we get one of our favourite low-discrepancy sequences. I spotted that only after I had finished writing the comment.
September 9, 2012 at 4:20 pm |
Now that I’ve done that it’s coming home to me just how crazy the statement was. If it had been true, it would have shown that for the normal EDP you must be able to find an arbitrarily long sequence of consecutive 1s or consecutive -1s along some HAP. But we know of sequences where that is false. What’s more, with those sequences one can’t improve matters in any way by passing to a generalized HAP — the discrepancy will still grow at most logarithmically.
September 9, 2012 at 5:25 pm |
Hmm, I’ve got a fairly convincing argument that no pure colouring argument of the kind I was looking for can possibly work. Roughly speaking, I wanted an argument that would work as follows. Given a function
that is never zero, we define
to be
. We then use very general properties of
, which we think of as a colouring, to argue that
for some
and
, which implies that
, a contradiction.
But if
is a prime less than
, then we can pick a function to
, take its partial sums along HAPs, and then just compose the resulting function with an injection from
into
. Just about the only property we had of
was that it avoided some value. Well, we’ve now got a function that avoids a value and has all the same sameness relations as a function that definitely exists.
Sorry not to be more precise about what is ruled out, but anyway I’m more or less convinced that EDP isn’t a Ramsey problem in disguise.
But that still leaves the possibility of a super-strong modular conjecture, where we show that for any function
there exist
HAPs all with the same maximal element such that the sums of
along them are all distinct.
September 10, 2012 at 9:05 pm |
One obvious remark is the following: For a hypergraph H on an underlying set A we can define the modular discrepancy
as the minimum p such that every everywhere non zero function
, every
can be expressed as a sum
for some edge S of H. So it can be of some interest to study it for simpler hypergraphs were the ordinary discrepancy is understood. It will also be interesting to find even simpler examples where the polynomial method is useful.
As Tim said we can consider other methods for this modular discrepancy versions. For example, if
is random then the nonzero values of
have uniform distribution. So we can try to understand how the distribution of non zero
deviate from uniform. Perhaps some Fourier ideas can work.
September 11, 2012 at 9:52 am
One remark in that direction is that the proof of Roth’s discrepancy theorem (that for every
-function defined on the first
integers you can find an AP on which the discrepancy is at least
) allows you to pick an AP of some fixed length close to
. It is clear that you can’t obtain a modular discrepancy theorem when all the sets have the same size, since the constant function 1 is a counterexample. It might be worth collecting other simple observations of this kind, to see if we can come up with a class of hypergraphs that are good candidates for a modular discrepancy theorem to hold.
September 11, 2012 at 10:05 am
It occurs to me that the example just mentioned is a special case of a much more general example. If you can find a nowhere zero linear functional
that is constant on your hypergraph (that is, a function that does not take zero values and has the same sum in every set in the hypergraph), then it provides a very strong counterexample. It also shows that the hypergraph is contained in an affine subspace of codimension 1. Maybe a good general type of condition to impose on the hypergraph is that it should be well distributed with respect to affine subspaces of codimension 1. This backs up Gil’s thought that Fourier ideas could work.
I’m not quite sure what I’m really saying here, however, since the Fourier conditions I can think of imply in a rather trivial way that the modular discrepancy is at least
. I suppose what would be interesting is a condition that does not depend on any particular prime
. In fact, that looks much better, since it means that if you find an affine subspace of codimension 1 that works for one prime
, there is no reason to suppose that it works for other primes.
To give a simple example of what I mean by the last remark, if all the sets in your hypergraph have odd cardinality, then the modular conjecture fails when
but it may well succeed for larger
. So we want Fourier conditions that are “robust”, in the sense that if you change the prime you don’t lose the condition.
September 11, 2012 at 11:45 am
When we talk about the modular conjecture it makes sense to assume that the hypergraph is closed under taking subsets.
Of course it is natural to ask if the modular discrepancy of AP’s is behaves like
. Perhaps one of the proofs for Roth’ddiscrepancy theorem can be extended?
September 11, 2012 at 2:04 pm
That sounds like a rather strong condition given that it fails to apply to interesting cases like APs or HAPs. But maybe one could ask for weaker conditions such as that for every set in the hypergraph it is possible to remove an element and get another set in the hypergraph. One could also ask for the hypergraph to be closed under intersections.
September 11, 2012 at 2:07 pm
Actually, perhaps I’ve misunderstood your remark, since the modular conjecture seems to me to be trivial if the hypergraph contains at least one reasonably large set and is closed under taking subsets: by the pigeonhole principle pick
elements where the value of the function is the same and then if the forbidden element is
, choose a subset of those
elements of size
, where
mod
.
September 11, 2012 at 3:10 pm
Sorry my remark made no sense.
September 11, 2012 at 5:32 pm
Another remark is that if you allow arbitrary arithmetic progressions, then the modular conjecture holds, though the argument I have in mind gives a rubbishy bound. The argument is that if
is large enough, then by Szemerédi’s theorem there is an arithmetic progression of length
on which the function is constant, and by choosing a subprogression of appropriate length you can make the sum whatever you like. It would be very interesting to see whether the correct bound is similar to the
bound for the conventional discrepancy theorem. The proof I understand (basically, a diagonal decomposition argument) doesn’t seem a promising candidate for modifying to handle the modular conjecture, since it proves the result for progressions of the same length.
September 11, 2012 at 5:42 pm
And a further remark is that the question is not completely uninteresting even for progressions of common difference 1. Of course, the modular conjecture is easily seen to be false for such progressions. However, it seems to be quite a strong condition on a sequence
that some value
(mod
) should be avoided by all sums of the form
. For instance, if we consider the set
of all sums of the form
and the set
of all sums of the form
, then
does not include
. That places quite strong conditions on
and
. There are many statements of a similar kind that one can make. Maybe it is possible to show somehow that these sorts of properties cannot hold simultaneously for lots of common differences.
September 12, 2012 at 2:22 pm |
I think it would be a very nice project, or perhaps I should call it sub-project, to try to prove the modular conjecture for arbitrary APs with a decent bound. And I’d be happy to start by considering the more symmetrical case where we define a function not on
but on the cyclic group
and we define an AP of length
to be a set of the form
mod
.
In the original problem, the reason you get high discrepancy is that you can express the
norm of your function efficiently in terms of products of AP-discrepancies. So if the
norm is large, then by averaging one of the products is large and therefore so is one of the discrepancies. Is there anything that could conceivably do the same job for the modular conjecture? We still get a nice representation of the identity matrix, but it’s not clear what can replace the averaging argument: if I know the sum of a whole lot of numbers mod
, it doesn’t tell me much about the original numbers.
Maybe one could somehow obtain a lot of different expressions relating sums along various APs and deduce from that that all values are represented.
September 12, 2012 at 3:10 pm |
Going back to Fourier analysis, how might that be made to work? In the abstract, if you’ve got a hypergraph
of subsets of
, then you might normally think of it as a 01-function defined on the cube
(taking the value 1 on characteristic functions of sets in
and 0 elsewhere). But we could think of it instead as being defined on
. That is, given a vector of length
with coordinates in
(strictly speaking, a function from
to
), if it happens to be the characteristic function of an AP mod
then it gets the value 1 and otherwise it gets the value 0.
Suppose now that
is much larger than
and that there is some function
and some
such that
doesn’t sum to
(mod
) on any
. Then if we average over all
characters that are constant on affine subspaces of the form
, we will find that at least one of those characters has a large inner product with (the characteristic function of)
.
Conversely, if
has no large Fourier coefficients, then for every non-zero function
you can find sets on which
sums to any value you choose mod
.
This is a much stronger conclusion than we can hope to prove, since it applies to all non-zero functions and not just to functions that never take the value zero. So what we will actually need to prove is something more like that while
will have at least some large Fourier coefficients (for example, if you consider the function that takes the value 1 in one place and zero everywhere else, then it takes the value 0 or 1 at every point in
, which will lead to large coefficients), these will tend to result from variables with a large influence. Maybe we can show that
has small Fourier coefficients at points with lots of non-zero values.
I need to try to be clearer what I mean. Every character on the group
will be of the form “take the inner product with the function
“, where
and
mod
. If
has lots of non-zero values (as opposed to only taking non-zero values), then maybe we can show that
has a small inner product with this character.
How could that be easier than the original problem? I don’t know that it could, but the hope would be that we could write down an expression that measures whether
has large Fourier coefficients for functions
with many non-zero entries (and this is quite reminiscent of expressions that people write down when studying Boolean functions and influence of variables) and interpret it as a condition on
that we then try to prove for the specific
that interests us — namely, the set of APs mod
.
September 13, 2012 at 9:38 am |
Here is a possible first step towards proving a modular conjecture for APs rather than HAPs. It is to attempt to prove that in the special case of
functions the distribution of sums along APs mod
tends to the uniform distribution. There is some choice about how to make that statement precise, but here is one version. For every
and every
there exist
such that for every
, if you choose a random AP
mod
of length between
and
(say by choosing the length randomly and then choosing the AP randomly of that length), then the distribution of
mod
is within
(in your favourite metric) of uniform.
Note that it is essential to vary the length, since otherwise the function
is a counterexample. However, it might be interesting to think about what the distribution can look like when the length is fixed. Maybe we could show that either it is uniform or it is close to constant (because, say,
is close to a constant function), and then argue that in the second case the constant varies linearly with the length of the AP. So let me ask another question. If
takes values
and is not approximately constant, can we then get a statement such as the one in the previous paragraph but for random APs of just one length
?
September 13, 2012 at 11:29 am |
A general philosophy that might be used to prove results of the kind suggested in the previous comment is this. Let
take many non-zero values and only values that are at most some constant
. Then if
and
are large enough (with
significantly larger than
), then the distribution of the sums
over all APs mod
of length
is similar to the distribution of the sums over all subsets of
of size
. In other words, once you’ve fixed the cardinality, making the further restriction that your set has to be an AP does not have much effect on the distribution.
It isn’t obvious that this philosophy is correct, so the first thing to do is perhaps to look for another obstruction besides cardinality.
Actually, I’ve seen a counterexample straight away. If the function
is periodic with some small period
(where I allow a little break when you get to
and start again), then there is a reasonably high probability that an AP doesn’t wrap around and has common difference a multiple of
. Hmm, no, that’s not true if
is large — it will almost certainly wrap around. OK, I’m not quite sure whether periodic functions (and similarly arithmetically structured functions) are a problem or not. If they are, then it might be possible to salvage the philosophy by talking about the distribution of mod
values rather than the distribution of
values.
OK, here’s an example. Suppose we take the function that’s 1 up to
and
from
onwards. Then a random AP of length
will almost always have common difference substantially greater than
, and when it does, the sum of the sequence along that AP will be bounded. (If
is odd, then there will be a tiny bias, but since
is a lot smaller than
, it is too tiny to affect anything.)
I didn’t say that very well. If the common difference is
and
lies between, say,
and
, then the sum along the AP won’t be more than about
. This happens most of the time. But if you pick a random subset of size
then you typically get a sum of around
. So the philosophy looks false if we talk about distributions of
values.
Actually, the same example shows that it’s false for mod
values as well. With probability
the sum along your mod-
AP of length
will have modulus at most
, so its value mod
will be between -4 and 4. That is certainly not the case for a random subset of size
.
In fact, the example is a counterexample to what I wanted to prove in the previous comment, since the sum is between -4 and 4 whatever the length
, as long as the common difference behaves itself.
That doesn’t quite kill things off, but it suggests that we might have to have a two-case argument, one for highly structured functions and one for quasirandom functions. A bit like another famous Roth theorem in fact.
September 14, 2012 at 10:59 am |
I now want to find a Fourier condition that will guarantee that sums over APs are approximately uniformly distributed. Ideally, I’d like the condition to be very weak. The kind of thing I would like to see is this.
1. If the function has a small amount of randomness, then the sums over APs of length
are approximately uniformly distributed.
2. If the function does not have a small amount of randomness, then there is a long AP on which it is approximately constant, and hence by averaging there is an AP of length
on which it is constant, which allows us to create any sum we like.
What could “a small amount of randomness” mean? Well, it reminds me of dual uniformity norms. Suppose we have a definition of quasirandomness (we might go for small Fourier coefficients, but I’ll leave that open). Then saying that a function is quasirandom is saying something like that it is “random everywhere”. But what if we just want it to be “random somewhere”. We can capture that by saying that the function correlates with a quasirandom function.
As an example, if you take a
function that is constant up to
and random from
to
, that is not quasirandom (because of the highly structured constant part) but it correlates very strongly with a random
function that agrees with it between
and
.
So one thing I’d like to be able to prove is that if you have a
function
that correlates with a quasirandom function, then the sums of
along APs are approximately uniformly distributed mod
. Of course, the statement has to be made precise, but it seems better to worry about that only after trying to prove it (so that the proof to some extent dictates the statement).
Experience suggests that not correlating with a quasirandom function (a.k.a. having a small dual norm) is a very strong property that is likely to lead to long APs where the function is constant. But it seems better to concentrate on stage 1 first.
September 14, 2012 at 11:08 am |
I want to get a feel for whether it’s actually true that a small amount of correlation with a quasirandom function causes the sums to be approximately uniformly distributed mod
. To do that, let’s consider the case where
is a random
function up to
and then arbitrary between
and
. Is it possible for the second part somehow to “compensate” for the randomness of the first part?
If I want sums along mod-
APs to be approximately uniformly distributed mod
, then I obviously need
to be significantly greater than
, since otherwise most APs of length
don’t intersect the first
elements of
, so if I make
1 between
and
, then most sums will be
mod
. So let’s assume that
is indeed quite a bit greater than
.
Actually, I realize that I have a more basic problem. How do I even show that the sums are approximately uniformly distributed when the entirety of
is quasirandom? (If it’s genuinely random then that’s OK, but we need to use quasirandomness.) I think this may require some offline calculation.
September 14, 2012 at 3:17 pm |
I now realize that I can say slightly more without the help of pen and paper (my ideal during polymath projects being not to use them at all but to write down all my thoughts, even if a significant percentage of them turn out to be a waste of time). Let
. How can we measure how uniformly distributed the sums of
are on sets in some hypergraph
? Here is a suggestion that turns out to involve polynomials, though not in quite the same way as in the polynomial method described by Gil in the post. (I haven’t thought enough about this to tell whether there is some connection — perhaps even a very close one.)
Let
. A natural way of encoding the sum
is as
, where
. Moreover, a good test of whether the values
are approximately uniformly distributed mod
as
ranges over some hypergraph
is to see whether the average
is small.
However, while that is a necessary condition for the sums to be approximately uniformly distributed, it is not sufficient. To get a sufficient condition, we should ask for more. We need the averages
to be small for every non-zero
(mod
), where
.
When
, we know that the average is 1, so we could try calculating something natural-seeming like the sum of the fourth powers of those averages and asking for it to be close to 1. I’ll try that in a new comment.
September 14, 2012 at 3:48 pm |
The quantity I want to calculate, or rather simplify, is
The fourth power of the expectation expands to
Bearing in mind that the product of the powers of
is
raised to the power the sum, we see that when we sum over
this expression vanishes except when
Unfortunately, that isn’t terribly helpful. Or at least, it doesn’t seem to be. In fact, I now see that I could have gone for second powers. And all I’d have got out at the end was that the values are well distributed if and only if you don’t get too many pairs
such that
, which is a simple fact that didn’t need Fourier analysis to be established.
But maybe what that is telling us is that we shouldn’t sum over
and simplify — since that is returning us to the original problem. Rather, we should think carefully about why we might expect sums of the form
to be small. That is, can we formulate properties of
that guarantee that they will be small? Of course, if we are fixing
, then we might as well write
instead. In fact, it’s not obvious that we need to insist that the values taken by the function are
th roots of unity. Perhaps the right question is this. Let
take values of modulus 1. Find conditions on
and the hypergraph
that ensure that
is small.
September 14, 2012 at 4:17 pm |
In the case where
consists of all arithmetic progressions of length
for some large
, I find this question quite puzzling. Consider, for example, what happens when
. (The puzzle will be that what I say will break down when
gets large and it will no longer be clear what happens.)
When
, we can define a function where the average is large as follows. For each
we randomly decide whether to set
to be
,
,
or
. If we now work out the expectation of
over all such
and over all arithmetic progressions
of length 4, we find that we obtain
, where
. This splits into
terms, of which two contribute
and the rest contribute close to zero. To cut a long story short, the fact that
means that the expectation of the product is not small, because quite a lot of the products are equal to 1.
Thus, for progressions of length 4 it is possible for a function with very small Fourier coefficients (as
is above) to give rise to a large average.
This argument can be generalized to larger
, but as
gets larger the size of the expectation gets smaller, so if
depends on
then we don’t have an example any more.
What this shows is that if we are going to prove that some kind of Fourier structure is necessary for the average to be large, the proof will have to break down when the length of the arithmetic progressions is small.
A second slightly puzzling feature of the problem is that if
is a random function from
to
subject to the restriction that it takes the values
, then for large
the sums
will be approximately uniformly distributed mod
, but the function
has non-trivial large Fourier coefficients. Thus, we very much need to use the fact that we are taking a product over a large set to “spread out” the function
.
September 14, 2012 at 4:41 pm |
Hmm, maybe I have an idea. Suppose we look at the average just for arithmetic progressions of length
and common difference 1. The first product is
. Let’s call that
. Then the next product is
. And the next one is
. And so on.
That didn’t quite work out as I hoped, so I’m not sure where I’m going with it. I’ll just make the remarks that one can do it for other common differences, and that if
is large then it is somehow more difficult for the products
to “conspire” to make the averages large. (I’m not sure why I say that, however.)
September 17, 2012 at 5:40 pm |
I feel the need to understand better what Fourier transforms of high-degree polynomials look like. That is, suppose that we have an expression of the form
. How can we rewrite it in terms of
?
I’ll do the obvious thing and consider just the monomial
. Let’s write
. Then
If
, then let’s write
for
and
for
, where
is the “obvious” ordering of the elements of
. (This makes sense for APs.) Then if all the sets
have size
, the polynomial becomes
. The only thing I can think of to do now is interchange summation to get
. In our case, all the
s are equal, so let’s look instead at the simpler expression
. So a useful thing to do will be to work out an expression for the last expectation — with luck it will pick out certain
s.
September 18, 2012 at 9:30 am |
Let
and let’s work out
, where
ranges over all APs mod
of length
. I now see that I haven’t made clear that
and that
.
We can rewrite our expectation as
which equals
which equals 1 if
and
mod
and 0 otherwise. So we’re summing
over all
that satisfy those two equations.
It’s not at all clear that that helps.
September 19, 2012 at 5:13 am |
I find it a little scary to talk Fourier about long sums of AP. Maybe we can get what we need by having certain psudorandomness for behavior of pairs of elements in HAPs or something like that?
September 19, 2012 at 9:09 am
I agree. I thought I’d better try it, and it was indeed scary. I think this is a great problem though. I am trying (so far without even the success that would deserve a comment on this thread) to think of some nice statement about APs that would be sufficient to imply the modular conjecture. I think I’ll collect the thoughts I have so far (mostly observations about approaches that can’t work, which at least have the merit of giving some clue about what a proof might look like) and write a post. Maybe some people will be interested to think about this problem, given that it isn’t known to be hard in the way that EDP is known to be hard.
September 19, 2012 at 2:06 pm
I have now written the post.
October 22, 2015 at 8:30 am |
[…] in our case) whose elements sum to 0 modulo p. We do not know what the situation is for EDP (see this post), and also for Roth’s theorem for general AP (see this post). Gowers introduced yet another […]