Avi Wigderson was in town and gave a beautiful talk about an extension of Sylvester-Gallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff.
Sylvester-Gallai
The Sylvester-Gallai Theorem: Let X be a finite set of n points in an eulidean space such that for every two distinct points
the line through
and
contains a third point
. Then all points in
are contained in a line.
I heard about this result when I took Benjy Weiss’s mathematics course for high-school students in 1970/1. a The Sylvester-Gallai theorem was the last question marked with (*) in the first week’s homework. In one of the next meetings Benjy listened carefully to our ideas on how to prove it and then explained to us why our attempts of proving it are doomed to fail: What we tried to do only relied on the very basic incidence axioms of Euclidean geometry but the Sylvester-Gallai theorem does not hold for finite projective planes. (Sylvester conjectured the result in 1893. The first proof was given by Mechior in 1940 and Gallai proved it in 1945.)
My MO question
Befor describing the new results let me mention my third ever MathOverflow question that was about potential extensions of the G-S theorem. The question was roughly this:
Suppose that V is an r dimensional variety embedded into n space so that if the intersection of every j-dimensional subspace with V is full dimensional then this intersection is “complicated”. Then
cannot be too large.
I will not reproduce the full question here but only a memorable remark made by Greg Kuperberg:
If you claimed that Gil is short for Gilvester (which is a real first name although rare), then you could say that any of your results is the “Gilvester Kalai theorem”. – Greg Kuperberg Nov 24 2009 at 5:13
The result by Barak, Dvir, Wigderson and Yehudayoff
Theorem: Let X be a finite set of n points in an Euclidean space such that for every point
the number of
such that the line through
and
contains another point of
is at least
. Then
Some remarks:
1) The proof: The first ingredient of the proof is a translation of the theorem into a question about ranks of matrices with a certain combinatorial structure. The next thing is to observe is that when the non zero entries of the matrix are 1’s the claim is simple. The second surprising ingredient of the proof is to use scaling in order to “tame” the entries of the matrix.
2) The context – locally correctable codes: A -query locally correctable
-code over a field
is a subspace of
so that, given any element
that disagrees with some
in at most
positions and an index
,
we can recover
with probability 3/4 by reading at most
coordinates of
. The theorem stated above imply that, for two queries, over the real numbers (and also over the complex numbers), such codes do not exist when
is large. Another context where the result is of interest is the hot area of sum product theorems and related questions in the geometry of incidences.
3) Some open problems: Is there a more detailed structure theorem for configurations of points satisfying the condition of the theorem? Can the result be improved to ? Can a similar result be proved on locally correctable codes with more than two queries? This also translates into an interesting Sylvester-Gallai type question but it will require, Avi said, new ideas.
From Avi: “Shubhangi Saraf recently solved the open problem – she proved that the dim of such fractional SG config O(1/\delta), so you can replace that open ‘?’ with a closed ‘!’ ”
!
As a substitute open problem what about this: If among any k points you can find two so that the line through then contain a third point (in the set) then the points lies on f(k) lines?
Melchior’s name is not spelled properly above. His proof of the Sylvester-Gallai Theorem is discussed in Branko Grunbaum’s monograph: Arrangements and Spreads, pg. 17.