Timeline for How to recognise that the polynomial method might work
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2015 at 20:19 | history | edited | Fedor Petrov | CC BY-SA 3.0 |
added 224 characters in body
|
| Oct 24, 2010 at 22:18 | comment | added | Fedor Petrov | In a sense, they are very similar. We assume a contrary and reformulate it as a system of algebraic equalities holding for free (independent) variables chosen from appropriate set. In case of Olson we know that all vectots $(\sum x_ia_i,\sum x_i b_i)$ belong to $\mathbb{F}_p^2\setminus (0,0)$ for $x_i\in \{0,1\}$. In case of Cauchy-Davenport we know that $x+y\in C$ for some $C$ of cardinality $|A|+|B|-2$ and $(x,y)\in A\times B$. Then we find one polynomial which respects all these conditions. It is a product of linear forms. Then we apply CN. | |
| Oct 24, 2010 at 16:21 | comment | added | gowers | As an exercise, I tried doing the Cauchy-Davenport theorem without looking up how it is done. At first I couldn't see what to do at all, but eventually, after some false starts, I realized that the polynomial $\prod_{c\in A+B}(x+y-c)$ and the sets A and B would contradict the combinatorial nullstellensatz if Cauchy-Davenport was false. Somehow this application feels very different from the Olson theorem application. | |
| Oct 24, 2010 at 10:23 | history | answered | Fedor Petrov | CC BY-SA 2.5 |