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

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.

EDP26 — three generalizations

This short post is designed as a possible way in to EDP for anyone who might be interested in participating but daunted by the idea of reading large amounts of material. One of the natural strategies for proving EDP is to try to formulate and prove stronger statements. At first that sounds paradoxical: isn’t it even harder to prove a stronger statement? But the answer to that question is often no. To give a slightly silly example, suppose you were asked to prove that for every there exists such that for every if is odd and has at least prime factors (counted with multiplicity), then mod , where is Euler’s totient function. You could make the problem easier by proving Euler’s theorem, that mod for every and every that is coprime to . You wouldn’t have as many hypotheses to use, but that’s good, since they can’t be used. Perhaps a better and more relevant example is when you generalize the class of numbers you are working with so as to allow a wider set of methods. For instance, suppose you want to prove that the largest possible product of three positive integers that add to 300 is at most . If you replace positive integers by positive reals, then you suddenly have available methods that you didn’t have before — for example, you could use compactness plus a lemma that says that if any two numbers are not equal then you can increase the product by replacing both of them by their average. (I’m not saying that’s the easiest proof — just that it’s a proof that you can’t do without first generalizing the statement.)

EDP25 — third guest post by Gil Kalai

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.