Sylvester-Gallai type theorems for quadratic polynomials

Sylvester-Gallai type theorems for quadratic polynomials, Discrete Analysis 2020:13, 34 pp.

The Sylvester-Gallai theorem asserts that given $n$ points in a plane that are not contained in a line, then there must be some line that contains exactly two of the points. This result is one of the basic results of combinatorial geometry, with several proofs, and it has been strengthened and generalized in a number of different ways – see for example a paper published recently in this journal.

If we dualize the original theorem, we arrive at the statement that if $n$ lines in the plane do not all meet at a point, then there must be a point that is contained in exactly two of the lines. If we think of the lines as graphs of polynomials of degree 1, then we can ask whether there are higher-degree generalizations of the theorem. That is the theme of this paper, which proves a quadratic analogue of the theorem.

To understand the statement that the author proves, it is helpful to reformulate a little further the linear version. Observe first that the original, non-dualized version of the theorem works just as well if the points live in an arbitrary vector space. Indeed, given $n$ points in a space $V$, we can find a projection to a 2-dimensional subspace of $V$ such that the images of any three non-collinear points are non-collinear, and hence such that the collinearity relations are all the same. Therefore, if no line contains exactly two points in the original set, then no line contains exactly two points in the projected set, from which it follows that the points in the projected set all lie in a line, from which it follows (since we did not create any new collinear triples) that the points in the original set all lie in a line.

The above statement is an affine statement, but we can replace it by an equivalent linear statement, which is that if $x_1,\dots,x_n$ are non-zero vectors in a (real) vector space $V$ such that for any two of the vectors $x_i,x_j$ there is a third, $x_k$ that lies in their span, then there is a 2-dimensional subspace that contains all the vectors. (To see the equivalence, project the vectors from zero to a random affine subspace, and then belonging to a 2-dimensional subspace translates into collinearity.)

From this we can deduce that if $\mathcal L$ is a finite collection of linear polynomials in $n$ variables $x_1,\dots,x_n$, and if for any two polynomials $L_1,L_2$ from the collection there is a third polynomial $L_3$ from the collection such that $L_3(x_1,\dots,x_n)=0$ whenever $L_1(x_1,\dots,x_n)=L_2(x_1,\dots,x_n)=0$, then $\mathcal L$ is contained in a 2-dimensional subspace. Indeed, if the coefficients of $L_3$ are a linear combination of those of $L_1$ and $L_2$, then any solution of $L_1$ and $L_2$ is clearly a solution of $L_3$, and since the polynomials are linear, the converse is true as well.

The author generalizes this statement by replacing $\mathcal L$ with a finite collection $\mathcal Q$ of quadratic polynomials in $n$ variables (in fact over $\mathbb C$) which are assumed to be irreducible. The conclusion is now that the subspace generated by $\mathcal Q$ is of bounded dimension.

It is always interesting to prove non-trivial higher-degree generalizations of linear results, but that is far from the only, or even main, motivation for this paper, which comes from computational complexity. An important theme in that field is polynomial identity testing – you are given a formula for a multivariable polynomial, and you would like to determine (with an efficient algorithm) whether that polynomial is identically zero. (This is of course equivalent to the problem of testing whether two polynomials agree as functions.) More precisely, you are given an arithmetic circuit, which is a directed graph with $n$ input nodes and one output node, with each non-input node labelled with $+$ or $\times$). Another way of thinking about it is that you have a sequence of polynomials, starting with $x_1,\dots,x_n$, with each subsequent one obtained by adding or multiplying some of the earlier ones together.

It turns out that for certain special classes of arithmetic circuits, if they compute the zero polynomial, then one can obtain Sylvester-Gallai-type conditions concerning linear forms that are used to build it up. Applying the Sylvester-Gallai theorem one deduces that these linear forms live in a low-dimensional space, which allows one to apply an invertible linear transformation and obtain a polynomial in a bounded number of variables, for which identity testing is easy.

The circuits in question have depth 3 – this means that the longest directed path in the directed graph has at most three edges – as well as satisfying certain additional conditions. Significant additional difficulties arise if one increases the depth to 4, but there is an ambitious conjecture of Gupta, which is thought to be hard, that attempts to resolve them. He also formulated a sequence of related conjectures in the direction of his main conjecture, which are generalizations of the Sylvester-Gallai theorem. One of them is that the (dualized) Sylvester-Gallai theorem holds for polynomials of bounded degree. By proving the result for quadratic polynomials, this paper establishes the first non-trivial case of the conjecture.

The proof of the theorem is also very interesting, in that it brings tools from theoretical computer science to bear on a problem in combinatorial (and algebraic) geometry. Particularly striking is that in order to prove the result, the author makes significant use of a “robust” version of the linear theorem. In the original formulation it states that if we have a set $S$ of $n$ points for which we assume only that for each point $x$ in $S$ there are at least $\delta n$ other points $y$ in $S$ such that the line through $x$ and $y$ passes through at least one further point in $S$, then $S$ is contained in an $O(1/\delta)$-dimensional space. It seems that extending the results to higher-degree polynomials would require significant further ideas, but this is an important first step.