Timeline for How to recognise that the polynomial method might work
Current License: CC BY-SA 3.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2021 at 22:21 | comment | added | nonuser | Hi, can you help me here with polynomial method (I'm not sure if it actually works). math.stackexchange.com/questions/4164782/… | |
| Oct 9, 2018 at 9:39 | comment | added | Ivan Meir | Which also trivially follows from the pigeon hole principle for a much smaller bound! | |
| Oct 9, 2018 at 9:29 | comment | added | Ivan Meir | ... of two disjoint subsets with equal sums if n>=p. | |
| Oct 9, 2018 at 9:25 | comment | added | Ivan Meir | Similarly by taking the degree to be (p-1)/2 you can prove the existence of two dish | |
| Oct 9, 2018 at 9:08 | comment | added | Ivan Meir | Late comment I know, but isn't this theorem just the Chevalley Warning theorem for solving forms over finite fields on taking the forms to be diagonal with degree p-1. In this case CW says we have a solution for n>2 (p-1) as required because x^(p-1) takes only 2 values, 0 and 1. This also gives an immediate generalisation to k vectors with condition n>k (p-1). The standard proof for CW shows that the number of solutions is divisible by p when the condition holds but uses a suitably constructed polynomial to do so, hence could be regarded as a precursor to the polynomial method itself. | |
| Oct 9, 2018 at 9:08 | comment | added | Ivan Meir | Sorry, trying again! | |
| Oct 9, 2018 at 8:59 | comment | added | Ivan Meir | Late comment but isn't this theorem just the Chevalley Warning theorem for solving forms over finite fields taking the forms to be diagonal with degree p-1. In this case CW says we have a solution for n>2 (p-1) whoch | |
| May 11, 2015 at 17:32 | comment | added | Anurag | @DylanThurston: I believe these are some crucial papers in this history of CN. Alon-Friedland-Kalai, Regular subgraphs of almost regular graphs (84); A-Tarsi, A nowhere zero point in linear mappings (88); A-Tarsi, Colorings and orientations of graphs (92). A-Furedi, Covering the cube by affine hyperplanes (93); A-Nathanson-Rusza, The polynomial method and restricted sums of congruence classes (96); and finally the paper titled Combinatorial Nullstellensatz by Alon from 1999. In the Alon-Furedi paper it is even mentioned that Hilbert's nullstellensatz can be used to solve the main problem. | |
| S May 9, 2015 at 3:13 | history | suggested | Anurag |
Added some more tags relevant to the question. Polynomial method has also been used in additive number theory.
|
|
| May 9, 2015 at 2:37 | review | Suggested edits | |||
| S May 9, 2015 at 3:13 | |||||
| May 6, 2015 at 17:56 | history | edited | Steven Landsburg | CC BY-SA 3.0 |
deleted 3 characters in body
|
| May 6, 2015 at 17:37 | answer | added | Anurag | timeline score: 10 | |
| Mar 28, 2015 at 14:09 | comment | added | Anurag | Here are some more examples of the polynomial method that may help in understanding when it can be used: - The blocking number of an affine space by Brouwer and Schrijver, JCT (A) (1978). - On the size of a blocking set in PG(2,p) by Blokhuis, Combinatorica (1994). - An easier proof of the maximal arcs conjecture by Simeon Ball and Aart Blokhuis, Proc. AMS (1998). And here's a book by Peter Sziklai on this topic: cs.elte.hu/~sziklai/polynom/poly08feb.pdf | |
| Jan 30, 2013 at 1:02 | comment | added | Günter Rote | @Qiaochu: The combinatorial Nullstellensatz does not imply the Schwartz-Zippel lemma. Ex. 9.1.1 in Tao and Vu's Additive Combinatorics does not ask to derive the Schwartz-Zippel from the CNS but merely to prove it by modifying the argument to the proof. (You have to turn the page ;-) see books.google.de/… | |
| Jan 30, 2013 at 0:52 | comment | added | Günter Rote | @Dylan: Schwartz-Zippel is a QUANTITATIVE statement, as opposed to the combinatorial Nullstellensatz, which is an EXISTENCE statement. When you read the proof in Schwartz' paper, you see that it implies that there are at least (|S1|-t1)(|S2|-t2)...(|Sn|-tn) nonzeros. (The t_i's are not the same as those in CNS; the assumptions on t_i's are not directly comparable; both conditions are subsumed by Michał Lasoń, A generalization of Combinatorial Nullstellensatz, The Electronic J. of Combinatorics (2010), Article no. #N32, 6 pp., mentioned in one of the answers, by "Seva". | |
| Oct 26, 2010 at 6:17 | answer | added | domotorp | timeline score: 3 | |
| Oct 25, 2010 at 17:29 | answer | added | Terry Tao | timeline score: 32 | |
| Oct 25, 2010 at 15:44 | answer | added | Seva | timeline score: 12 | |
| Oct 24, 2010 at 10:23 | answer | added | Fedor Petrov | timeline score: 10 | |
| Oct 23, 2010 at 22:42 | answer | added | Gjergji Zaimi | timeline score: 20 | |
| Oct 23, 2010 at 19:21 | comment | added | Dylan Thurston | After looking a little further, it seems like Alon's theorem is an improvement of the Schwartz-Zippel lemma, with a more precise statement about the individual degrees. | |
| Oct 23, 2010 at 19:19 | comment | added | Qiaochu Yuan | @Dylan: in fact it implies Schwartz-Zippel. This is exercise 9.1.1 in Tao and Vu's Additive Combinatorics, right after they introduce the combinatorial nullstellensatz. They remark that it is "particularly useful for obtaining lower bounds on the size of restricted sum sets and similar objects." | |
| Oct 23, 2010 at 18:09 | comment | added | gowers | @Gerhard Paseman: Yes, it's that way round, which is why Fermat's little theorem is helpful. I agree that it makes the use of the result harder to spot. @Dylan Thurston: I'm not sure, but I seem to remember he discovered it about fifteen years ago (plus or minus five perhaps) along with several nice applications. | |
| Oct 23, 2010 at 17:52 | comment | added | Dylan Thurston | The combinatorial nullstensatz is remarkably similar to the Schwartz-Zippel(-DeMillo-Lipton) lemma, whose history is summarized <a href="rjlipton.wordpress.com/2009/11/30/…> (by Lipton). What's the history of Alon's theorem? | |
| Oct 23, 2010 at 17:19 | comment | added | Gerhard Paseman | I was going to comment that syntactic similarity is one clue, then I noticed that one result says = 0 and another does not. Did you quote both results correctly? Gerhard "Ask Me About System Design" Paseman, 2010.10.23 | |
| Oct 23, 2010 at 17:12 | history | asked | gowers | CC BY-SA 2.5 |