# Fractional Sylvester–Gallai theorems

^{a}Microsoft Research New England, Microsoft, 1 Memorial Drive, Cambridge, MA 02142;^{b}Department of Computer Science, Princeton University, 35 Olden Street, Princeton, NJ 08540;^{c}School of Mathematics, Institute for Advanced Studies, Einstein Drive, Princeton, NJ 08540; and^{d}Department of Mathematics, Technion—Israel Institute of Technology, Haifa 32000, Israel

See allHide authors and affiliations

Edited by Terence Chi-Shen Tao, University of California, Los Angeles, CA, and approved August 17, 2012 (received for review March 7, 2012)

## Abstract

We prove fractional analogs of the classical Sylvester–Gallai theorem. Our theorems translate local information about collinear triples in a set of points into global bounds on the dimension of the set. Specifically, we show that if for every points *v* in a finite set , there are at least δ|*V*| other points *u*∈*V* for which the line through *v*,*u* contains a third point in *V*, then the *V* resides in a (13/δ^{2})-dimensional affine subspace of . This result, which is one of several variants we study, is motivated by questions in theoretical computer science and, in particular, from the area of error correcting codes. Our proofs combine algebraic, analytic, and combinatorial arguments. A key ingredient is a new lower bound for the rank of *design* matrices, specified only by conditions on their zero/non-zero pattern.

In 1893 James Joseph Sylvester posed the following, well known problem (1): “Prove that it is not possible to arrange any finite number of real points so that a right line through every two of them shall pass through a third, unless they all lie in the same right line.” This beautiful problem was solved by Eberhard Melchior in 1940 (2), and, independently, by Tibor Gallai in 1944 in response to a question of Erdos (3). This statement is commonly known as the Sylvester–Gallai theorem.

It is convenient to restate this result using the notions of special and ordinary lines. A *special* line is a line that contains at least three points from the given set. Lines that contain exactly two points from the set are called *ordinary*.

(Sylvester–Gallai theorem). If *m* distinct points *v*_{1},…,*v*_{m} in are not collinear, then they define at least one ordinary line.

In its contrapositive form, the theorem says that if for every *i* ≠ *j* in [*m*] the line through *v*_{i},*v*_{j} passes through a third point *v*_{k}*∉*{*v*_{i},*v*_{j}}, then dim{*v*_{1},…,*v*_{m}} ≤ 1, where dim{*v*_{1},…,*v*_{m}} is the dimension of the smallest affine subspace containing the points. In this formulation, the theorem can be thought of as converting local information (on collinear triples) into a global bound on the dimension of the system.

In 1966 Jean-Pierre Serre (4) asked for a complex version of this theorem. The complex version was first proved by Leroy Milton Kelly (5) using deep results from algebraic geometry. An elementary proof was later found by Elkies et al. (6).

(Kelly’s theorem). If *m* distinct points in are not coplanar, then they define at least one ordinary line.

Both theorems are tight: In the real case, if all points are collinear (and there are at least three points) then no line passes through exactly two of them. In the complex plane, one can find noncollinear (but coplanar) configurations of points such that every line passing through two of them contains a third point.

This work studies scenarios in which the local geometric information is incomplete. We are no longer in a situation where *every* line is special, but are only guaranteed that, for every point, the special lines through this point cover some positive fraction of the set (later we will consider even more relaxed scenarios). To articulate this scenario we use the following definition: Call the points a δ-SG *configuration* if for every *i*∈[*n*] there exists at least δ*n* values of *j*∈[*n*] such that the line through *v*_{i},*v*_{j} contains a third point in the set. We provide the following bound over the complex numbers. Later (see *Other Fields*) we will generalize our results to any field of characteristic zero or of sufficiently large positive characteristic.

(Fractional SG theorem). For any δ > 0, the dimension of a δ-SG configuration over the complex numbers is at most 13/δ^{2}.

The upper bound on the dimension should be compared with the trivial lower bound of Ω(1/δ) that arises from a partition of the points into 1/δ generically positioned lines. Here, and for the rest of the paper, *O*(·) and Ω(·) are used to hide universal constants only.

One of the motivations for studying this problem is its connection to problems in theoretical computer science and coding theory. The problem of bounding the dimension of δ-SG configurations is closely related to locally correctable codes (LCCs). To read more about this connection, we refer the reader to ref. 7.

In section *Several Extensions*, using Theorem 3 and its proof, we derive the following additional results:

• An analog of Theorem 3 with lines replaced with higher dimensional flats (as in Hansen’s theorem).

• A fractional analog of the Motkin-Rabin theorem which is a two-color version of the Sylvester–Gallai theorem.

• A three-color “nonfractional” analog of the Motzkin–Rabin theorem (the proof, nevertheless, uses the “fractional” version in an essential way).

• Average-case versions of Theorem 3 in which we are only guaranteed that a quadratic number of pairs of points are on special lines and find a large subset of points that is low dimensional.

• Extensions of Theorem 3 to any field of characteristic zero of sufficiently large positive characteristic (as a function of

*n*).

## Methods: Rank of Design Matrices

The main ingredient in the proof of Theorem 3 is a general lower bound on the rank of matrices with certain zero/nonzero patterns. The connection between the two problems is not surprising, because both convert local combinatorial information into global algebraic information (i.e., rank/dimension bounds). The type of zero/nonzero patterns we consider are called designs:

(Design matrix). Let *A* be an *m* × *n* matrix over some field. For *i*∈[*m*] let *R*_{i}⊂[*n*] denote the set of indices of all nonzero entries in the *i*’th row of *A*. Similarly, let *C*_{j}⊂[*m*], *j*∈[*n*], denote the set of nonzero indices in the *j*’th column. We say that *A* is a (*q*,*k*,*t*)-design matrix if

For all

*i*∈[*m*], |*R*_{i}| ≤*q*.For all

*j*∈[*n*], |*C*_{j}|≥*k*.For all

*j*_{1}≠*j*_{2}∈[*n*], |*C*_{j1}∩*C*_{j2}| ≤*t*.

The zero/nonzero pattern of the columns of a design matrix, *C*_{1},…,*C*_{n}, form a design in that each set is large but the pairwise intersections are small. The following theorem gives a lower bound on the rank of design matrices and is proved in section *Bounds on the Rank of Design Matrices*.

(Rank bound for design matrices). For every complex matrix *A* with *n* columns that is a (*q*,*k*,*t*)-design,

To get a feeling of the parameters, consider an *m* × *n* matrix with *O*(1) nonzeros in each row, with Ω(*n*) nonzeros in each column and with *t* = *O*(1) pairwise intersections of columns; Theorem 5 tells us that such a matrix has almost full rank, *n* - *O*(1).

We begin, in section *Proof of the Fractional SG Theorem*, with the proof of Theorem 5. The main technical tool, Theorem 5 is proved in section *Bounds on the Rank of Design Matrices*. In section *Several Extensions* we consider various extensions to Theorem 3.

## Proof of the Fractional SG Theorem

The following lemma is an easy consequence of (8) and will be used in the proof below.

Let *r*≥3. Then there exists a set *T*⊂[*r*]^{3} of *r*^{2} - *r* triples that satisfies the following properties:

Each triple (

*t*_{1},*t*_{2},*t*_{3})∈*T*is of three distinct elements.For each

*i*∈[*r*] there are exactly 3(*r*- 1) triples in*T*containing*i*as an element.For every pair

*i*,*j*∈[*r*] of distinct elements there are at most six triples in*T*which contain both*i*and*j*as elements.

By [(8), Theorem 4] there exists a Latin square {*A*_{ij}}_{i,j∈[r]} with *A*_{ii} = *i* for all *i*∈[*r*]. Taking all triples of the form (*i*,*j*,*A*_{ij}) with *i* ≠ *j* proves the Lemma.

Let *V* be the *n* × *d* matrix whose *i*’th row is the vector *v*_{i}. Assume without loss of generality (w.l.o.g.) that *v*_{1} = 0. Thus dim{*v*_{1},…,*v*_{n}} = rank(*V*). We will first build an *m* × *n* matrix *A* that will satisfy *A*·*V* = 0. Then, we will argue that the rank of *A* is large because it is a design matrix. This argument will show that the rank of *V* is small.

Consider a special line *ℓ* which passes through three points *v*_{i},*v*_{j},*v*_{k}. This line gives a linear dependency among the three vectors *v*_{i},*v*_{j},*v*_{k}. In other words, this gives a vector *a* = (*a*_{1},…,*a*_{n}) which is nonzero only in the three coordinates *i*, *j*, *k* and such that *a*·*V* = 0. If *a* is not unique, choose an arbitrary vector *a* with these properties. Our strategy is to pick a family of collinear triples among the points in our configuration and to build the matrix *A* from rows corresponding to these triples in the above manner.

Let denote the set of all special lines in the configuration (i.e., all lines containing at least three points). For each let *V*_{ℓ} denote the set of points in the configuration which lie on the line *ℓ*. Then |*V*_{ℓ}|≥3 and we can assign to it a family of triples , given by Lemma 6 (we identify *V*_{ℓ} with [*r*], where *r* = |*V*_{ℓ}| in some arbitrary way). We now construct the matrix *A* by going over all lines and for each triple in *T*_{ℓ} adding as a row of A the vector with three nonzero coefficients *a* = (*a*_{1},…,*a*_{n}) described above (so that *a* is the linear dependency between the three points in the triple).

Because the matrix *A* satisfies *A*·*V* = 0 by construction, we only have to argue that *A* is a design matrix and bound its rank.

**Claim 7.** The matrix *A* is a (3, 3*k*, 6)-design matrix, where *k* = [δ*n*] - 1.

By construction, each row of *A* has exactly *three* nonzero entries. The number of nonzero entries in column *i* of *A* corresponds to the number of triples we used that contain the point *v*_{i}. These triples can come from all special lines containing *v*_{i}. Suppose there are *s* special lines containing *v*_{i} and let *r*_{1},…,*r*_{s} denote the number of points on each of those lines. Then, because the lines through *v*_{i} have only the point *v*_{i} in common, we have that . The properties of the families of triples *T*_{ℓ} guarantee that there are 3(*r*_{j} - 1) triples containing *v*_{i} coming from the *j*’th line. Therefore there are at least 3*k* triples in total containing *v*_{i}.

The size of the intersection of columns *i*_{1} and *i*_{2} is equal to the number of triples containing the points *v*_{i1}, *v*_{i2} that were used in the construction of *A*. These triples can only come from one special line (the line containing these two points) and so, by Lemma 6, there can be at most *six* of those.

Applying Theorem 5 we get that where the third inequality holds as δ*n*≥13 because otherwise the theorem trivially holds. This inequality implies that rank(*V*) < 13/δ^{2}, which completes the proof. For δ = 1, the calculation above yields rank(*V*) < 11.

## Bounds on the Rank of Design Matrices

In this section we prove Theorem 5. For a set of complex vectors we denote by rank(*V*) the dimension of the vector space spanned by elements of *V*. We denote the *ℓ*_{2}-norm of a vector *v* by ‖*v*‖. We denote by *I*_{n} the *n* × *n* identity matrix.

The starting point of the proof is the observation that, if the matrix entries are all in the set {0,1} then the proof is quite easy: simply consider the product *A*^{t}·*A* and observe that its diagonal elements are much larger than its off-diagonal elements. Such matrices, called *diagonal dominant matrices*, are known to have high rank and so *A* must have high rank as well (cf. Lemma 12 below). The choice of the set {0,1} is not important—as long as the ratios between different nonzero entries are bounded, the same proof strategy will work. We reduce to this case using a technique called *matrix scaling*.

[Matrix scaling] Let *A* be an *m* × *n* complex matrix. Let , be two complex vectors with all entries nonzero. We denote by **SC**(*A*,ρ,γ) the matrix obtained from *A* by multiplying the (*i*,*j*)’th element of *A* by ρ_{i}·γ_{j}. We say that two matrices *A*, *B* of the same dimensions are a scaling of each other if there exist nonzero vectors ρ, γ such that *B* = **SC**(*A*,ρ,γ). It is easy to check that this is an equivalence relation. We refer to the elements of the vector ρ as the row scaling coefficients and to the elements of γ as the column scaling coefficients. Notice that two matrices which are a scaling of each other have the same rank and the same pattern of zero and nonzero entries.

Matrix scaling originated in a paper of Sinkhorn R (9) and has been widely studied since (see ref. 10 for more background). The following is a special case of a theorem from (11) that gives sufficient conditions for finding a scaling of a matrix which has certain row and column sums.

(Property-*S*). Let *A* be an *m* × *n* matrix over some field. We say that *A* satisfies Property-*S* if for every zero submatrix of *A* of size *a* × *b* it holds that [1]

(Matrix scaling theorem, Theorem 3 in ref. 11). Let *A* be an *m* × *n* real matrix with nonnegative entries which satisfies Property-*S*. Then, for every *ϵ* > 0, there exists a scaling *A*^{′} of *A* such that the sum of each row of *A*^{′} is at most 1 + *ϵ* and the sum of each column of *A*^{′} is at least *m*/*n* - *ϵ*. Moreover, the scaling coefficients used to obtain *A*^{′} are all positive real numbers.

We will use the following easy corollary of this theorem obtained by applying it to the matrix whose elements are the squares of absolute values of *A*.

Let *A* = (*a*_{ij}) be an *m* × *n* complex matrix which satisfies Property-*S*. Then, for every *ϵ* > 0, there exists a scaling *A*^{′} of *A* such that for every *i*∈[*m*] and for every *j*∈[*n*]

We will also use a variant of a well known lemma (see for example ref. 12) which provides a bound on the rank of matrices whose diagonal entries are much larger than the off-diagonal ones.

Let *A* = (*a*_{ij}) be an *n* × *n* complex Hermitian matrix and let 0 < *ℓ* < *L* be integers. Suppose that *a*_{ii}≥*L* for all *i*∈[*n*] (the diagonal elements of a Hermitian matrix are real) and that |*a*_{ij}| ≤ *ℓ* for all *i* ≠ *j*. Then

We can assume w.l.o.g. that *a*_{ii} = *L* for all *i*. If not, then we can make the inequality into an equality by multiplying the *i*’th row and column by (*L*/*a*_{ii})^{1/2} < 1 without changing the rank or breaking the symmetry. Let *r* = rank(*A*) and let λ_{1},…,λ_{r} denote the nonzero eigenvalues of *A* (counting multiplicities). Because *A* is Hermitian we have that the λ_{i}’s are real. We have Rearranging we get the required bound. The second inequality in the statement of the lemma follows from the fact that 1/(1 + *x*)≥1 - *x* for all *x*.

To prove the theorem we will first find a scaling of *A* so that the norms (squared) of the columns are large and such that each entry is small. Our first step is to find an *nk* × *n* matrix *B* that will satisfy Property-*S* and will be composed from rows of *A* such that (s.t.) each row is repeated with multiplicity between 0 and *q*. Such a matrix can be constructed from *A* as follows: for each *i*∈[*n*] let *B*_{i} be a *k* × *n* submatrix of *A* with no zeros in the *i*’th column. Take *B* to be the *nk* × *n* matrix composed of all matrices *B*_{i}, *i*∈[*n*]. It is easy to check that *B* satisfies property-*S* and that each row of *A* appears in *B* at most *q* times.

Our next step is to obtain a scaling of *B* and, from it, a scaling of *A*. Fix some *ϵ* > 0 (which will later tend to zero). Applying Corollary 11 we get a scaling *B*^{′} of *B* such that the *ℓ*_{2}-norm of each row is at most and the *ℓ*_{2}-norm of each column is at least . We now obtain a scaling *A*^{′} of *A* as follows: The scaling of the columns are the same as for *B*^{′}. For the rows of *A* appearing in *B* we take the maximal scaling coefficient used for these rows in *B*^{′}, that is, if row *i* in *A* appears as rows *i*_{1},*i*_{2},…,*i*_{q′} in *B*, then the scaling coefficient of row *i* in *A*^{′} is the maximal scaling coefficient of rows *i*_{1},*i*_{2},…,*i*_{q′} in *B*^{′}. For rows *not* in *B*, we pick scaling coefficients so that their *ℓ*_{2} norm (in the final scaling) is equal to 1. It is easy to verify that the matrix *A*^{′} is a scaling of *A* such that each row has *ℓ*_{2}-norm at most and each column has *ℓ*_{2}-norm at least .

Next, consider the matrix *M* = (*A*^{′})^{∗}·*A*^{′}, where (*A*^{′})^{∗} is *A*^{′} transposed conjugate. Then *M* = (*m*_{ij}) is an *n* × *n* Hermitian matrix. The diagonal entries of *M* are exactly the squares of the *ℓ*_{2}-norm of the columns of *A*^{′}. Therefore, *m*_{ii}≥(*k* - *ϵ*)/*q* for all *i*∈[*n*]. The off-diagonal entries of *M* are the inner products of different columns of *A*^{′}. The intersection of the support of each pair of different columns is at most *t*. The norm of each row is at most . For every two real numbers α, β so that α^{2} + β^{2} ≤ 1 + *ϵ* we have |α·β| ≤ 1/2 + *ϵ*^{′}, where *ϵ*^{′} tends to zero as *ϵ* tends to zero. Therefore |*m*_{ij}| ≤ *t*·(1/2 + *ϵ*^{′}) for all *i* ≠ *j*∈[*n*]. Applying Lemma 12 we get that Because this inequality holds for all *ϵ* > 0 it holds also for *ϵ* = 0, which gives the required bound.

## Several Extensions

We now describe several extensions of the fractional Sylvester–Gallai theorem: two average-case versions, two high-dimensional fractional versions, a two-color fractional version, a three-color nonfractional version, and statements on other fields (than real and complex numbers).

### Average-Case Versions.

In this section we argue about the case where we only know that there are many collinear triples in a configuration. We start with the following average-case version in which there is *some* large family of collinear triples that satisfies some regularity condition (no pair is in too many triples). Below we will use this theorem to derive another average-case version in which we only assume that many pairs are on special lines. In both theorems the conclusion is only that there exists a large subset that lies in small dimension (which is clearly the strongest qualitative statement one can hope for in this setting).

(Average-case SG theorem Let). be a set of *m* distinct points. Let *T* be some set of (unordered) collinear triples in *V*. Suppose |*T*|≥α*m*^{2} and that every two points *v*,*v*^{′} in *V* appear in at most *c* triples in *T*, then there exists a subset *V*^{′}⊂*V* such that |*V*^{′}|≥α*m*/(2*c*) and dim(*V*^{′}) ≤ *O*(1/α^{2}).

Notice that the bound on the number of triples containing a fixed pair of points is necessary for the theorem to hold. If we remove this assumption than we could create a counter example by arranging the points so that *m*^{2/3} of them are on a line and the rest are placed so that every large subset of them spans the entire space (e.g., in general position). The proof will use the following hypergraph lemma.

Let *H* be a 3-regular hypergraph with vertex set [*m*] and α*m*^{2} edges of codegree at most *c* (i.e., for every *i* ≠ *j* in [*m*], the set {*i*,*j*} is contained in at most *c* edges). Then there is a subset *M*⊆[*m*] of size |*M*|≥α*m*/(2*c*) so that the minimal degree of the subgraph of *H* induced by *M* is at least α*m*/2.

We describe an iterative process to find *M*. We start with *M* = [*m*]. While there exists a vertex of degree less than α*m*/2, remove this vertex from *M* and remove all edges containing this vertex from *H*. Continuing in this fashion we conclude with a set *M* such that every point in *M* has degree at least α*m*/2. This process removed in total at most *m*·α*m*/2 edges and thus the new *H* still contains at least α*m*^{2}/2 edges. As the codegree is at most *c*, every vertex appears in at most *cm* edges. Thus, the size of *M* is of size at least α*m*/(2*c*).

We describe an iterative process to find *M*. We start with *M* = [*m*]. While there exists a vertex of degree less than α*m*/2, remove this vertex from *M* and remove all edges containing this vertex from *H*. Continuing in this fashion we conclude with a set *M* such that every point in *M* has degree at least α*m*/2. This process removed in total at most *m*·α*m*/2 edges and thus the new *H* still contains at least α*m*^{2}/2 edges. As the codegree is at most *c*, every vertex appears in at most *cm* edges. Thus, the size of *M* is of size at least α*m*/(2*c*).

The family of triples *T* defines a 3-regular hypergraph on *V* of codegree at most *c*. Lemma 14 thus implies that there is a subset *V*^{′}⊆*V* of size |*V*^{′}|≥α*m*/(2*c*) that is an (α/2)-SG configuration. By Theorem 3, *V*^{′} has dimension at most *O*(1/α^{2}).

We now state the second average-case variant of Sylvester–Gallai in which we assume that there are many pairs on special lines. Here there is no need for further assumption and the proof is by an easy reduction to Theorem 13.

(Average-case SG theorem—2nd variant). Let be a set of *m* distinct points. Suppose that there are at least β·*m*^{2} unordered pairs of points in *V* that lie on a special line (i.e., there is a third point collinear with them). Then there exists a subset *V*^{′}⊂*V* such that |*V*^{′}|≥(β/6)·*m* and dim(*V*^{′}) ≤ *O*(1/β^{2})

Let *ℓ*_{1},…,*ℓ*_{t} denote the special lines in the configuration *V*. Let *r*_{1},…,*r*_{t} be integers such that *ℓ*_{i} contains exactly *r*_{i}≥3 points from *V*. The assumption of the theorem implies that We now apply Lemma 6 on all *t* lines to find *t* sets of triples *T*_{1},….*T*_{t} such that each *T*_{i} contains triples of points from the line *ℓ*_{i}. We now have that each *T*_{i} contains exactly triples and that, in each *T*_{i}, two points appear in at most *six* triples. This last condition translates also to the union of the *T*_{i}’s because two lines intersect in at most one point. We thus see that the set satisfies the conditions of Theorem 13 with α = 2β and *c* = 6. We can thus conclude that there exists a subset *V*^{′}⊂*V* such that |*V*^{′}|≥(β/6)·*m* and dim(*V*^{′}) ≤ *O*(1/β^{2}) as was required.

### Fractional Hansen Theorems.

Hansen’s theorem (13) is a high-dimensional version of the SG theorem in which lines are replaced with higher dimensional flats. Let fl(*v*_{1},…,*v*_{k}) denote the affine span of *k* points, i.e., the points that can be written as linear combinations with coefficients that sum to one (fl for “flat”). We call *v*_{1},…,*v*_{k} *independent* if their flat is of dimension *k* - 1 (dimension means affine dimension), and say that *v*_{1},…,*v*_{k} are *dependent* otherwise. A *k*-*flat* is an affine subspace of dimension *k*. In the following *V* is a set of *n* distinct points in complex space . A *k*-flat is called *ordinary* if its intersection with *V* is contained in the union of a (*k* - 1)-flat and a single point. A *k*-flat is *elementary* if its intersection with *V* has exactly *k* + 1 points. Notice that for *k* = 1—the case of lines—the two notions of ordinary and elementary coincide.

For dimensions higher than one, there are two different definitions that generalize that of SG configuration. The first definition is based on ordinary *k*-flats. The second definition, which is less restricted than the first one, uses elementary *k*-flats (like in Hansen’s theorem).

The set *V* is a configuration if for every independent *v*_{1},…,*v*_{k}∈*V* there are at least δ*n* points *u*∈*V* s.t. either *u*∈fl(*v*_{1},…,*v*_{k}) or the *k*-flat fl(*v*_{1},…,*v*_{k},*u*) contains a point *w*∈*V* outside fl(*v*_{1},…,*v*_{k})∪{*u*}.

The set *V* is a δ-SG_{k} configuration if for every independent *v*_{1},…,*v*_{k}∈*V* there are at least δ*n* points *u*∈*V* s.t. either *u*∈fl(*v*_{1},…,*v*_{k}) or the *k*-flat fl(*v*_{1},…,*v*_{k},*u*) is not elementary.

Both definitions coincide with that of SG configuration when *k* = 1: Indeed, fl(*v*_{1}) = *v*_{1} and fl(*v*_{1},*u*) is the line through *v*_{1},*u*. Therefore, *u* is never in fl(*v*_{1}) and the line fl(*v*_{1},*u*) is not elementary if it contains at least one point *w∉*{*v*_{1},*u*}.

We prove two high-dimensional versions of the SG theorem, each corresponding to one of the definitions above. Both theorems hold over the complex numbers (as well as over the real numbers). To the best of our knowledge, no complex-numbers version of Hansen’s theorem was previously known.

Let *V* be a configuration. Then dim(*V*) ≤ *f*(δ,*k*) with *f*(δ,*k*) = *O*((*k*/δ)^{2}).

Let *V* be a δ-SG_{k} configuration. Then dim(*V*) ≤ *g*(δ,*k*) with *g*(δ,*k*) = 2^{Ck}/δ^{2}, with *C* > 1 a universal constant.

The proofs of the two theorems are below. Theorem 18 follows by an appropriate induction on the dimension, using the (one dimensional) robust SG theorem. Theorem 19 follows by reduction to Theorem 18.

Before proving the theorems we set some notation. Fix some point *v*_{0}∈*V*. By a *normalization* with respect to (w.r.t.) *v*_{0} we mean a mapping which first shifts all points by -*v*_{0} (so that *v*_{0} goes to zero), then picks a hyperplane *H* s.t. no point in *V* (after the shift) is parallel to *H* (i.e., has inner product zero with the orthogonal vector to *H*) and finally multiplies each point (other than zero) by a constant s.t. it is in *H*. Note that all points on a single line through *v*_{0} map to the same image under *N*. Observe also that for any such mapping *N* we have dim(*N*(*V*))≥ dim(*V*) - 1 because the shifting can decrease the dimension by at most one and the scaling part maintains the dimension. Another property which holds for *N* is:

**Claim 20.** For such a mapping *N* we have that *v*_{0},*v*_{1},…,*v*_{k} are dependent iff *N*(*v*_{1}),…,*N*(*v*_{k}) are dependent.

Because translation and scaling does not affect dependence, w.l.o.g. we assume that *v*_{0} = 0 and that the distance of the hyperplane *H* from zero is one. Let *h* be the unit vector orthogonal to *H*. For all *i*∈[*k*] we have . Assume that *v*_{0},*v*_{1},…,*v*_{k} are dependent, that is, w.l.o.g. for some *a*_{1},…,*a*_{k-1}. For all *i*∈[*k* - 1] define . Thus where , which means that *N*(*v*_{1}),…,*N*(*v*_{k}) are dependent. Because the map *a*_{i}↦*b*_{i} is invertible, the other direction of the claim holds as well.

We first prove the theorem for configurations.

The proof is by induction on *k*. For *k* = 1 we know *f*(δ,1) ≤ *c*δ^{-2} with *c* > 1 a universal constant. Suppose *k* > 1. We separate into two cases. The first case is when *V* is an (δ/(2*k*))-SG_{1} configuration and we are done using the bound on *k* = 1. In the other case there is some point *v*_{0}∈*V* s.t. the size of the set of points on special lines through *v*_{0} is at most δ*n*/(2*k*) (a line is special if it contains at least three points). Let *S* denote the set of points on special lines through *v*_{0}. Thus |*S*| < δ*n*/(2*k*). Let be a normalization w.r.t. *v*_{0}. Notice that for points *v∉S* the image *N*(*v*) determines *v*. Similarly, all points on some special line map to the same point via *N*.

Our goal is to show that *V*^{′} = *N*(*V* ∖ {*v*_{0}}) is a configuration (after eliminating multiplicities from *V*^{′}). This assertion will complete the proof because dim(*V*) ≤ dim(*V*^{′}) + 1. Indeed, if this assertion holds we have and by induction we have *f*(δ,*k*) ≤ 4*c*(*k*/δ)^{2}.

Fix to be *k* - 1 independent points (if no such tuple exists then *V*^{′} is trivially a configuration). Let *v*_{1},…,*v*_{k-1}∈*V* be points s.t. for *i*∈[*k* - 1]. Claim 20 implies that *v*_{0},*v*_{1},…,*v*_{k-1} are independent. Thus, there is a set *U*⊂*V* of size at least δ*n* s.t. for every *u*∈*U* either *u*∈fl(*v*_{0},*v*_{1},…,*v*_{k-1}) or the *k*-flat fl(*v*_{0},*v*_{1},…,*v*_{k-1},*u*) contains a point *w* outside fl(*v*_{0},*v*_{1},…,*v*_{k-1})∪{*u*}.

Let so that *N* is invertible on and Suppose and let *u*^{′} = *N*(*u*). By Claim 20 if *u*∈fl(*v*_{0},*v*_{1},…,*v*_{k-1}) then *u*^{′} is in . Otherwise, fl(*v*_{0},*v*_{1},…,*v*_{k-1},*u*) contains a point *w* outside fl(*v*_{0},*v*_{1},…,*v*_{k-1})∪{*u*}. Let *w*^{′} = *N*(*w*). We will show that *w*^{′} is (a) contained in the (*k* - 1)-flat and (b) is outside . Property (a) follows from Claim 20 because *v*_{0}, *v*_{1},…,*v*_{k-1}, *u*,*w* are dependent and so are also dependent. To show (b) observe first that by Claim 20 the points are independent (because *v*_{0},*v*_{1},…,*v*_{k-1},*u* are independent) and so *u*^{′} is not in . We also need to show that *w*^{′} ≠ *u*^{′} but this follows from the fact that *u* ≠ *w* and so *w*^{′} = *N*(*w*) ≠ *N*(*u*) = *u*^{′} because *N* is invertible on and . Since the proof is complete.

We can now prove the theorem for δ-SG_{k} configurations.

The proof follows by induction on *k* (the case *k* = 1 is given by Theorem 3). Suppose *k* > 1. Suppose that dim(*V*) > *g*(δ,*k*). We want to show that there exist *k* independent points *v*_{1},…,*v*_{k} s.t. for at least 1 - δ fraction of the points *w*∈*V* we have that *w* is not in fl(*v*_{1},…,*v*_{k}) and the flat fl(*v*_{1},…,*v*_{k},*w*) is elementary (i.e., does not contain any other point).

Let *k*^{′} = *g*(1,*k* - 1). By choice of *g* we have *g*(δ,*k*) > *f*(δ,*k*^{′} + 1) with *f* from Theorem 18. Thus, by Theorem 18, we can find *k*^{′} + 1 independent points *v*_{1},…,*v*_{k′+1} s.t. there is a set *U*⊂*V* of size at least (1 - δ)*n* s.t. for every *u*∈*U* we have that *u* is not in fl(*v*_{1},…,*v*_{k′+1}) and the (*k*^{′} + 1)-flat fl(*v*_{1},…,*v*_{k′+1},*u*) contains only one point, namely *u*, outside fl(*v*_{1},…,*v*_{k′+1}).

We now apply the inductive hypothesis on the set *V*∩fl(*v*_{1},…,*v*_{k′+1}) which has dimension at least *k*^{′} = *g*(1,*k* - 1). This application gives us *k* independent points that define an elementary (*k* - 1)-flat . Saying that *V* is not 1-SG_{k-1} is the same as saying that it contains an elementary (*k* - 1)-flat. Joining any of the points *u*∈*U* to gives us an elementary *k*-flat and so the theorem is proved.

### A Fractional Motzkin–Rabin Theorem.

The Motzkin–Rabin theorem is a two-color variant of the Sylvester–Gallai theorem. Here we prove a fractional version of it.

(δ-MR configuration). Let *V*_{1},*V*_{2} be two disjoint finite subsets of . Points in *V*_{1} are of color 1 and points in *V*_{2} are of color 2. A line is called *bichromatic* if it contains at least one point from each of the two colors. We say that *V*_{1},*V*_{2} are a δ-MR configuration if for every *i*∈[2] and for every point *p*∈*V*_{i}, the bichromatic lines through *p* contain at least δ|*V*_{i}| points from *V*_{i}.

Let be a δ-MR configuration. Then

We will call a line passing through exactly two points in *V*_{1} (respectively *V*_{2}) a *V*_{1}-ordinary (respectively *V*_{2}-ordinary) line. W.l.o.g. assume |*V*_{1}| ≤ |*V*_{2}|. We separate the proof into two cases:

Case I is when *V*_{2} is a (δ/2)-SG configuration. Then, by Theorem 3, dim(*V*_{2}) ≤ *O*(1/δ^{2}). If in addition dim(*V*_{1}) ≤ 13/(δ/2)^{2} then we are done. Otherwise, by Theorem 3, there exists a point *a*_{0}∈*V*_{1} such that there are at least (1 - δ/2)|*V*_{1}| *V*_{1}-ordinary lines through *a*_{0}. Let *a*_{1},…,*a*_{k} denote the points in *V*_{1} that belong to these lines with *k*≥(1 - δ/2)|*V*_{1}|. We now claim that *V*_{2}∪{*a*_{0}} spans all the points in *V*_{1}. This claim will suffice because, in this case, dim(*V*_{2}) ≤ *O*(1/δ^{2}). Let *a*∈*V*_{1}. Then, because *V*_{1},*V*_{2} is a δ-MR configuration, there are at least δ|*V*_{1}| points in *V*_{1} such that the line through them and *a* contains a point in *V*_{2}. One of these points must be among *a*_{1},…,*a*_{k}, say it is *a*_{1}. Because *a* is in the span of *V*_{2} and *a*_{1} and because *a*_{1} is in the span of *V*_{2} and *a*_{0} we are done.

Case II is when *V*_{2} is not a (δ/2)-SG configuration. In this case, there is a point *b*∈*V*_{2} such that there are at least (1 - δ/2)|*V*_{2}| *V*_{2}-ordinary lines through *b*. From this fact and from the δ-MR property, we get that |*V*_{1}|≥(δ/2)|*V*_{2}| (there are at least (δ/2)|*V*_{2}| *V*_{2}-ordinary lines through *b* that have an additional point from *V*_{1} on them). This fact implies that the union *V*_{1}∪*V*_{2} is a (δ^{2}/4)-SG configuration because δ|*V*_{i}|≥(δ^{2}/4)|*V*_{1}∪*V*_{2}|. and the result follows by applying Theorem 3.

### A Three-Color Variant.

Having the flexibility of arguing about δ-SG configurations is also handy in proving theorems where there is no partial information. We demonstrate this flexibility by proving a three-color analog of the Motzkin–Rabin theorem.

(3MR configuration). Let *V*_{1},*V*_{2},*V*_{3} be three pairwise disjoint finite subsets of , each of distinct points. We say that *V*_{1},*V*_{2},*V*_{3} is a 3MR-configuration if every line *ℓ* so that *ℓ*∩(*V*_{1}∪*V*_{2}∪*V*_{3}) has more than one point intersects at least two of the sets *V*_{1},*V*_{2},*V*_{3}.

Let *V*_{1},*V*_{2},*V*_{3} be a 3MR configuration and denote *V* = *V*_{1}∪*V*_{2}∪*V*_{3}. Then

Assume w.l.o.g. that *V*_{1} is not smaller than *V*_{2},*V*_{3}. Let α = 1/16. There are several cases to consider:

*V*_{1} *is an* α-SG *configuration*. By Theorem 3, the dimension of *V*_{1} is at most Consider the two sets each is a set of distinct points in . Assume w.l.o.g. that .

*is an* α-SG *configuration*. By Theorem 3, the dimension of is at most Fix a point *v*_{3} in . For every point *v* ≠ *v*_{3} in the line through *v*_{3},*v* contains a point from . Therefore,

*is not an* α-SG *configuration*. There is a point *v*_{2} in so that for of the points *v* ≠ *v*_{2} in the line through *v*_{2},*v* does not contain any other point from . If then the dimension of *V*_{1}∪*V*_{2} is at most *d*_{1} + 1 and we are done, as in the previous case. Otherwise, there is a point in .

We claim that in this case . Denote by *P*_{2} the *k* points *v* ≠ *v*_{2} in so that the line through *v*_{2},*v* does not contain any other point from . For every *v*∈*P*_{2} there is a point *V*_{1,3}(*v*) in *V*_{1}∪*V*_{3} that is on the line through *v*,*v*_{2} (the point *v*_{2} is fixed). There are two cases to consider. (*i*) The first case is that for at least *k*/2 of the points *v* in *P*_{2} we have . In this case clearly . (*ii*) The second case is that for at least *k*/2 of the points *v* in *P*_{2} we have . This fact means that these points *V*_{1,3}(*v*) are in span(*V*_{1}). Fix such a point *v*∈*P*_{2} [which is in span(*V*_{1},*v*_{2})]. The line through contains a point *v*^{′} from *V*_{1}∪*V*_{3}. The point *v*^{′} is not in span(*V*_{1}), as if it was then would be in span(*v*,*v*^{′})⊆span(*V*_{1},*v*_{2}). Therefore *v*^{′} is in . This fact also implies that .

Denote . So we can conclude that for every *v*^{′} in *V*^{′} the special lines through *v*^{′} contain at least |*V*^{′}|/8 of the points in *V*_{1}∪*V*_{2}∪*V*_{3}. As in the proof of Theorem 3, we can thus define a family of triples *T*, each triple of three distinct collinear points in *V*, so that each *v*^{′} in *V*^{′} belongs to at least |*V*^{′}|/8 triples in *T* and each two distinct *v*^{′},*v*^{′′} in *V*^{′} belong to at most *six* triples.

By a slight abuse of notation, we also denote by *V* the matrix with rows defined by the points in *V*. Let *V*_{1} be the submatrix of *V* with row defined by points in span(*V*_{1})∩*V* and *V*^{′} be the submatrix of *V* with row defined by points in *V*^{′}. Use the triples in *T* to construct a matrix *A* so that *A*·*V* = 0. Let *A*_{1} be the submatrix of *A* consisting of the columns that correspond to span(*V*_{1})∩*V* and *A*^{′} be the submatrix of *A* consisting of the columns that correspond to *V*^{′}. Therefore, *A*^{′}·*V*^{′} = -*A*_{1}·*V*_{1} which implies By the above discussion *A*^{′} is a (3,|*V*^{′}|/8,6)-design matrix and thus, by Theorem 5, has rank at least and so We can finally conclude that

*V*_{1} *is not an* α-SG *configuration*. There is a point *v*_{1} in *V*_{1} so that for at least |*V*_{1}|/2 of the points *v* ≠ *v*_{1} in *V*_{1} the line through *v*_{1},*v* does not contain any other point from *V*_{1}. Assume w.l.o.g. that |*V*_{2}|≥|*V*_{3}|. This fact implies that

|*V*_{3}| < |*V*_{2}|/16. In this case the configuration defined by *V*_{1}∪*V*_{2} is an α-SG configuration: Fix a point *v*_{1}∈*V*_{1} (a similar argument works for every *v*_{2}∈*V*_{2}). We need to show that there are many special lines through *v*_{1}. There are two options: Either (*i*) there are |*V*_{1}|/2 points in *V*_{1} with a third point from *V*_{1} on the line through , or (*ii*) there are |*V*_{1}|/2 points in *V*_{1} so that the line contains a third point from *V*_{2}∪*V*_{3}. If case (*i*) holds, the point *v*_{1} satisfies the required property. If case (*ii*) holds, because |*V*_{3}| < |*V*_{2}|/16|, for at least |*V*_{1}|/4 points , the line through contains a third point from *V*_{2}.

By Theorem 3, the dimension of *V*_{1}∪*V*_{2} is at most Fix a point *v*_{3} in *V*_{3}. For every point *v* ≠ *v*_{3} in *V*_{3} the line through *v*_{3},*v* contains a point from *V*_{1}∪*V*_{2}. Therefore,

|*V*_{3}|≥|*V*_{2}|/16. In this case *V* is an α-SG configuration because |*V*_{i}|≥α|*V*| for each *i*∈{1,2,3}. By Theorem 3, the dimension of *V* is thus at most *O*(1).

### Other Fields.

In this section we show that our results can be extended from the complex field to fields of characteristic zero, and even to fields with very large positive characteristic. The argument is quite generic and relies on Hilbert’s Nullstellensatz. We only discuss Theorem 5 because all other theorems follow from it over any field.

(*T*-matrix) Let *m*,*n* be integers and let *T*⊂[*m*] × [*n*]. We call an *m* × *n* matrix *A* a *T*-matrix if all entries of *A* with indices in *T* are nonzero and all entries with indices outside *T* are zero.

(Effective Hilbert’s Nullstellensatz ref. 14). Let be degree *d* polynomials with coefficients in {0,1} and let Suppose is another polynomial with coefficients in {0,1} which vanishes on *Z*. Then there exist positive integers *p*,*q* and polynomials such that Furthermore, one can bound *p* and the maximal absolute value of the coefficients of the *f*_{i}’s by an explicit function *H*_{0}(*d*,*t*,*s*).

Let *m*,*n*,*r* be integers and let *T*⊂[*m*] × [*n*]. Suppose that all complex *T*-matrices have rank at least *r*. Let be a field of either characteristic zero or of finite large enough characteristic *p* > *P*_{0}(*n*,*m*), where *P*_{0} is some explicit function of *n* and *m*. Then, the rank of all *T*-matrices over is at least *r*.

Let be the determinants of all *r* × *r* submatrices of an *m* × *n* matrix of variables *X* = (*x*_{ij}). The statement “all *T*-matrices have rank at least *r*” can be phrased as “if *x*_{ij} = 0 for all (*i*,*j*)*∉T* and *g*_{k}(*X*) = 0 for all *k*∈[*s*] then .” That is, if all entries outside *T* are zero and *X* has rank smaller than *r* then it must have at least one zero entry also inside *T*. From Nullstellensatz we know that there are integers α,λ > 0 and polynomials *f*_{1},…,*f*_{s} and *h*_{ij},(*i*,*j*)*∉T*, with integer coefficients such that [2]This identity implies the high rank of *T*-matrices also over any field in which α ≠ 0. Because we have a bound on α in terms of *n* and *m* the result follows.

Theorem 3 holds over any field of characteristic zero or of sufficiently large (as a function of the number of points) positive characteristic.

The meaning of “sufficiently large” in the corollary does not depend on *n*, the underlying dimension, via a random linear projection of the *m* points to an *m*-dimensional space (if *n* > *m*).

## Acknowledgments

We thank Moritz Hardt for many helpful conversations. We thank Jozsef Solymosi for helpful comments. B.B was at Princeton University during most of the research presented in this paper and was supported by NSF grants CNS-0627526, CCF-0426582 and CCF-0832797, and the Packard and Sloan fellowships. Z.D was partially supported by NSF grant CCF-0832797 and by the Packard fellowship. A.W was partially supported by NSF grants CCF-0832797 and DMS-0835373. A.Y was at the Institute for Advanced Study, Princeotn, during most of the research presented in this paper and was partially supported by NSF grants CCF-0832797 and DMS-0835373.

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. E-mail: zeev.dvir{at}gmail.com.

Author contributions: B.B., Z.D., A.W., and A.Y. performed research.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

## References

- ↵
- Sylvester JJ

- ↵
- Melchior E

- ↵
- ↵
- Serre SP

- ↵
- ↵
- ↵
- Barak B,
- Dvir Z,
- Yehudayoff A,
- Wigderson A

- ↵
- Hilton AJW

- ↵
- ↵
- ↵
- Rothblum U,
- Schneider H

- ↵
- ↵
- Hansen S

- ↵

## Citation Manager Formats

## Article Classifications

- Physical Sciences
- Mathematics