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
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.
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.