Sunday, September 9, 2012

EDP25 — third guest post by Gil Kalai

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

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 x_e. Consider the two polynomials
P= \prod_{v \in V(G)} ((\sum_{e: v \in e}x^2_e)^2-1), and
Q=\prod_{e\in E(G)}(x_e^2-1)
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 x_1,x_2,\dots as a sequence with \pm 1 modulo p, where p is a prime that we can choose as large as we want.
2) Then every number modulo p can be expressed as a sum of the sequence along a HAP modulo p.
Translating EDP (in this form) into a statement about polynomials modulo p 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 x_1,x_2\dots ,x_n 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 x_1,x_2,\dots,x_n we need to prove over Z/pZ when p grows to infinity with n as slow as we wish. For every k, 0 \le k\le p,
(*) \prod_{i=1}^nx_i\prod \{(x_d+x_{2d}+\cdots+x_{id})-k~:~d,i:~di\le n\}~=~0
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
\prod_{i=1}^n(x_1+x_2+\dots+x_i)
and expand it to monomials, the coefficients have a combinatorial meaning in terms of permutations and inversions.
Given a permutation \pi (1),\pi (2),\dots,\pi (n), and an integer i,~1\le i\le n we can ask how many inversions are there between i and a smaller integer. This is a number between 1 and i-1.
The coefficient of x_1^{i_1}x_2^{i_2}\dots x_n^{i_n} in the above product is the number of permutations where there are i_j 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 y.
Given x_1+x_2+\dots +x_r \ne y, the probability that x_1+\dots+x_r+x_{r-1} is not y is 1-1/(p-1). So we are interested in the value of p with (1-1/(p-1))^{nlogn} = (p-1)^{-n}. (Restricting our attention to multiplicative sequences will divide the exponents on both sides by \log n.) Solving this equation gives us p=\log n \log\log n. 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 p> \log n\log\log n.
b) (Weak prediction) There are no such sequences when p<<\log n\log\log n.
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 \sqrt {\log n} for \pm1-sequences. By restricting our attention to \pm 1 sequences we see that the weak prediction is incorrect and LDH for the modular EDP is blind to the special substructure of \pm 1 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.



DIGITAL JUICE

No comments:

Post a Comment

Thank's!