Timeline for How to recognise that the polynomial method might work
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 3, 2020 at 18:58 | comment | added | VENKITESH | @Anurag, apologies for the late post. It might also be useful to note that the statement - any polynomial that vanishes on all points of a grid $S_1\times\cdots\times S_n$ except one must have degree at least $\sum |S_i|-1$ - also follows from a simple generalized Vandermonde determinant, as observed in this paper. | |
| Aug 3, 2015 at 17:51 | comment | added | Anurag | @FedorPetrov: only the prime case of Olson's theorem follows from Alon-Furedi hyperplane covering. Though that has been "fixed" recently by Clark et al. (and by Brink before that) by generalising another result of Alon-Furedi. See section 4 of arxiv.org/pdf/1404.7793v2.pdf. In fact many combinatorial results that follow from combinatorial nullstellensatz can alternately be seen as direct applications of this Alon-Furedi bound. | |
| Apr 13, 2015 at 21:47 | comment | added | Anurag | (contd ...) A particular case of this, where each $S_i = \mathbb{F}_q$, and you are looking at polynomials over $\mathbb{F}_q$ was already proved in this paper by Bruen, sciencedirect.com/science/article/pii/009731659290035S, by more or less similar arguments. | |
| Apr 13, 2015 at 21:45 | comment | added | Anurag | It's probably worthwhile to note that one can easily avoid CN in Example 3. Basically, you want to prove that any polynomial that vanishes on all points of a grid $S_1 \times \cdots \times S_n$ except one must have degree at least $\sum |S_i| - 1$. This can be proved by induction on $\sum |S_i| - 1$. For a particular case of this, see my solution here: artofproblemsolving.com/wiki/index.php/2007_IMO_Problems/…. (contd ...) | |
| Oct 25, 2010 at 8:08 | comment | added | Fedor Petrov | By the way, Olson's result is a special case of Alon-Furedi (which holds over nay field, in our case $\mathbb{F}_p$): all points of the cube $\{0,1\}^{2p−1}$ but origin can not be covered by $2p−2$ hyperplanes $\sum a_i x_i=m$, $\sum b_ix_i=m$, $m=1,2,\dots,p−1$. | |
| Oct 24, 2010 at 9:48 | comment | added | gowers | I have to disagree with your self-assessment there: I found the answer very interesting and helpful. And the fact that you've drawn attention to the Alon-Friedland-Kalai result (which I didn't know) makes it all the more so, since it suggests that understanding that example would be a good idea. | |
| Oct 23, 2010 at 22:42 | history | answered | Gjergji Zaimi | CC BY-SA 2.5 |