I’ve just uploaded to the arXiv my article “Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory“, submitted to the new journal “EMS surveys in the mathematical sciences“. This is the first draft of a survey article on the polynomial method – a technique in combinatorics and number theory for controlling a relevant set of points by comparing it with the zero set of a suitably chosen polynomial, and then using tools from algebraic geometry (e.g. Bezout’s theorem) on that zero set. As such, the method combines algebraic geometry with combinatorial geometry, and could be viewed as the philosophy of a combined field which I dub “algebraic combinatorial geometry”. There is also an important extension of this method when one is working overthe reals, in which methods from algebraic topology (e.g. the ham sandwich theorem and its generalisation to polynomials), and not just algebraic geometry, come into play also.

The polynomial method has been used independently many times in mathematics; for instance, it plays a key role in the proof of Baker’s theorem in transcendence theory, or Stepanov’s method in giving an elementary proof of the Riemann hypothesis for finite fields over curves; in combinatorics, the nullstellenatz of Alon is also another relatively early use of the polynomial method. More recently, it underlies Dvir’s proof of the Kakeya conjecture over finite fields and Guth and Katz’s near-complete solution to the Erdos distance problem in the plane, and can be used to give a short proof of the Szemeredi-Trotter theorem. One of the aims of this survey is to try to present all of these disparate applications of the polynomial method in a somewhat unified context; my hope is that there will eventually be a systematic foundation for algebraic combinatorial geometry which naturally contains all of these different instances the polynomial method (and also suggests new instances to explore); but the field is unfortunately not at that stage of maturity yet.

This is something of a first draft, so comments and suggestions are even more welcome than usual. (For instance, I have already had my attention drawn to some additional uses of the polynomial method in the literature that I was not previously aware of.)

### Like this:

Like Loading...

## 22 comments

Comments feed for this article

25 October, 2013 at 9:46 am

AnonymousReferences:

* [1], [4]–[5], [7]–[9], [11]–[16], [18], [21]–[23], [30]–[31], [39]–[44], [50]–[51], [53], [57]–[63], [65]–[66], [73]–[75], [78]: An n-dash instead of a hyphen in page range

* [25], [27], [36], [45], [48], [52], [64], [68], [70], []: The title should be in italic

* [6]: “T.Tao” –> “T. Tao”

* [6]: “ — .” –> “”, no. , —.”

* [7], [34]: Remove “p.p.”

* [13]: “R.Seidel” –> “R. Seidel”

* [13]: “Applications, – ” –> “Applications , no. , —.”

* [13], [57]: A full stop at the end of the reference

* [14]: “Universitt” –> “Universit{\”a}t”

* [16]: “Dias” –> “D.”

* [16]: “Soc. ” –> “Soc. ”

* [19]: “” –> —

* [19]: Is “” supposed to be there?

* [20]: “” –> “—”

* [33]: “” –> “”

* [36]: “Publications, ” –> “Publications ”

* [43]: The “Gza;” looks `wierd’

* [50]: “” –> “”

* [54]: “—” –> “”

* [56]: “Series A — .” –> “Series A ”, no. , —.”

* [57]: “Computing – ” –> “Computing ”, no. , —.”

* [74]: “ Soc. , .” –> “Soc. ,”

* [75]: “ pages –, ” –> “— ”

* [78]: “ pages –, ” –> “— ”

P.S. I’m not sure it is all correct and that I haven’t missed something.

[Thanks! It turns out there were a lot of junk characters in the bibliography which had messed things up, this will be cleaned up in the next revision of the ms. -T.]25 October, 2013 at 11:26 am

AnonymousOn another note: I normally put

\usepackage[bottom,hang,stable]{footmisc}

\setlength\footnotemargin{6pt}

In the preamble. This givesd a better formatting of the footnotes, I think.

25 October, 2013 at 12:11 pm

Anonymous* Section 1, l. 5–6: “overlays … on top”. Isn’t this superfluous? (English is not my native language.)

* P. 2, One line after the first emphasized math expression: “of coeﬃcients” –> “of the coeﬃcients”.

* P. 2, l. -3: Use “\colon” instead of “:” for maps. [Two times.]

* Footnote 3, l. -3: Use “\colon” instead of “:” for maps. [Two times.]

* P. 3, l. 9: Should be ?

* P. 5, l. -4: Have you used “\setminus” instead of a backslash? (The spacing indicates that you haven’t but I’m not entirely sure.)

* P. 6, l. 2: “see e.g.” –> “see, e.g.,”.

* Proof of Theorem 8, l. 2: Use “\setminus” instead of a backslash.

* P. 6, l. -5: Use “\setminus” instead of a backslash.

[Thanks, this will be corrected in the next revision of the ms. -T.]25 October, 2013 at 12:20 pm

AnonymousAn idea for typesetting maps is to define a macro, e.g.,

\newcommand*\map[3]{#1 \colon #2 \to #3}

and then use, say,

\map{P}{F^n}{F}

This gives consistency.

25 October, 2013 at 4:06 pm

AnonymousSection 2:

* P. 7, one line under (1): “” –> “”

* P. 9, Lemma 12, l. 3: “” –> “” or “”

* Section 2, l. -3: “two: see” –> “two; see”

P.S. In Section 4.6 of “Short Math Guide for ”, it is shown how to typeset different types of dots the correct way.

[Thanks, this will be corrected in the next revision of the MS- T.]19 November, 2013 at 4:07 am

AnonymousI just learned of “ ($i\textsuperscript{th}$)” (remember not to use “” ($i^\textsuperscript{th}$) —that gives double superscript); use this instead.

25 October, 2013 at 7:02 pm

AnonymousSection 3:

* P. 12, l. 12: “taht” –> “that”

Section 4:

* Proof of Theorem 17, l. -2: Reformulate this sentence to avoid the expression overlapping the margin

* Proof of Theorem 18, l. -3: Use “\setminus” instead of a backslash

* Theorem 19, l. 2: “integers, and” –> “integers and”

* Theorem 19, l. 2: “ respectively with” –> “`, respectively, with”

* Proof of Theorem 19, l. 5: “ respectively” –> “`, respectively”

* P. 16, l. 27: Use “\colon” instead of a colon

* Proof of Proposition 21, l. 6: “” –> “”

* P. 18, l. 9–10: “see e.g.” –> “see, e.g.,”

* Proof of Lemma 23, l. -5: “most (say)” –> “most, say, ”

* P. 19, l. 9: “see e.g.” –> “see, e.g.,”

* P. 19, l. 29 (displayed formula): Use “\setminus” instead of a backslash

P.S. As before, I’m not sure it is all correct.

[Thanks, these will be corrected in the next revision of the MS- T.]25 October, 2013 at 7:05 pm

Anonymousfinite fields over curves …

[Thanks, this will be corrected in the next revision of the MS- T.]25 October, 2013 at 7:35 pm

AnonymousIn Lemma 11 \sum_{p \in F^n} {n+p-1\choose n} —> \sum_{p \in F^n} {n+c_p-1\choose n}

[Thanks, this will be corrected in the next revision of the MS- T.]26 October, 2013 at 4:31 am

NGIt will be very nice to see some open problems/directions in your survey.

27 October, 2013 at 3:47 am

Felipe VolochHave you looked at S. Ball’s proof of the main conjecture for MDS codes over prime fields (J. Eur. Math. Soc., 14 (2012) 733–748. )?

28 October, 2013 at 12:22 pm

Terence TaoThanks for the link! It is an interesting variant of the polynomial method, being much more algebraic in nature than geometric (one creates various polynomials related to the initial combinatorial structure, by explicitly multiplying together various linear forms, and then performs some algebraic manipulations involving determinants until one arrives at a useful identity, namely that a product of various simple expressions is equal to zero mod p). I wonder if there is a more geometric motivation for Ball’s argument (which I found at http://www-ma4.upc.es/~simeon/jems-mds-conj-revised.pdf ), which would tie it more closely to the types of polynomial method applications in the survey.

28 October, 2013 at 3:08 pm

Felipe VolochBall’s argument has its origin in Segre’s lemma of tangents, which he used to show that an oval in a plane over a finite field of odd order is a conic.

29 October, 2013 at 7:28 am

Terence TaoThat’s a really nice argument (and I’m surprised I didn’t know about it before…). I’m sketching a proof of Segre’s theorem (extracted from the text of Ball and Weiner) here, mostly for my own benefit. The claim that is if F is a field of odd order q, and O is an oval (a set of q+1 points in the projective plane such that no three points are collinear), then O is a conic. The first observation is that for every point A on O, there is exactly one “tangent line” through A that does not meet any other point of O; the other q lines through A meet exactly one other point of O. Now, if O were a conic, and A,B,C were distinct points on O, then there would be a non-trivial algebraic constraint (depending on A,B,C) connecting the slopes of the lines l_A, l_B, l_C (because the space of conics is five-dimensional, so the space of conics passing through A,B,C is two-dimensional, whereas the space of slopes of l_A,l_B,l_C is three-dimensional if unconstrained). Call this constraint (*). Segre’s lemma of tangents is the assertion that the constraint (*) holds for any oval O. If A,B,C,D are four points in O, one can apply (*) to the triples (A,B,D), (A,C,D), and (B,C,D), and end up (after some linear algebra) constraining D (and l_D) in terms of A,B,C, l_A, l_B, l_C, which ends up placing D on a conic as required.

It remains to prove (*). For every point D on O not equal to A,B,C, the lines AD, BD, CD are concurrent; applying Ceva’s theorem, one obtains a constraint of the form f(AD) g(BD) h(CD) = 1. Multiplying this over all possible D, and comparing to the product of all possible values of f,g,h, one ends up with a constraint on f(l_A) g(l_B) h(l_C) which ends up being exactly (*) (as it must, since conics are ovals).

23 October, 2015 at 7:57 am

Anurag BishnoiDear Terence Tao,

On page 9 of the final published version of your survey, you have mentioned “See [5] for some of the recent developments associated to Segre’s theorem.”, but the reference [5] is to the notes of Ball and Weiner. Shouldn’t it be to the paper of Ball on MDS conjecture?

S. Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis. J. Eur. Math. Soc. 14(3) (2012), 733–748.

[The lecture notes of Ball and Weiner covers this result as well as other aspects of Segre’s theorem. -T.]16 November, 2013 at 9:10 am

About this blog and its author – Andreea's Blog[…] Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combi… (terrytao.wordpress.com) […]

25 November, 2013 at 1:22 am

The Combinatorial Nullstellensatz | Eventually Almost Everywhere[…] Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combi… (terrytao.wordpress.com) […]

7 May, 2014 at 8:57 am

Stickiness, graininess, planiness, and a sum-product approach to the Kakeya problem | What's new[…] Finally, in 2009, Dvir used route (a) and introduced the polynomial method (as discussed previously here) to completely settle the Kakeya conjecture in finite […]

7 July, 2014 at 2:20 am

The subspace theorem approach to Siegel’s theorem on integral points on curves via nonstandard analysis | What's new[…] now use a version of the polynomial method, to find some polynomials of controlled degree that vanish to high order on the “arm” […]

26 January, 2015 at 1:07 pm

Anurag BishnoiAnother example of the polynomial method that you might have missed: http://www-ma4.upc.es/~simeon/lacunary4.pdf

I am no expert on blocking sets and I haven’t gone through the full paper. So, you might want to get in touch with Simeon Ball for such applications of the polynomial method in finite geometry.

26 January, 2015 at 1:56 pm

Anurag BishnoiHere’s a survey on direction problems in finite affine spaces and the use of polynomial method to solve them: http://arxiv.org/abs/1409.6960

21 March, 2015 at 2:13 am

Anurag BishnoiProbably one of the oldest use of polynomial methods in incidence problems is in these papers “The blocking number of an affine space” by Brouwer and Schrijver (1978), and “Covering finite fields with cosets of subspaces” by R. E. Jamison (1977). In fact, one can prove Chevalley’s theorem from this result in the Brouwer-Schriver paper: Let $P$ be a polynomial with $P(0) \neq 0$ and $P(a) = 0$ for every other $a$ in $F^n$, then the degree of $P$ is at least $n(|F| – 1)$.