The Sylvester–Gallai theorem in
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ...
states that every
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. ...
of points in the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
has a line that passes through exactly two of the points or a line that passes through all of them. It is named after
James Joseph Sylvester
James Joseph Sylvester (3 September 1814 – 15 March 1897) was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory, and combinatorics. He played a leadership r ...
, who posed it as a problem in 1893, and
Tibor Gallai, who published one of the first proofs of this theorem in 1944.
A line that contains exactly two of a set of points is known as an ''ordinary line''. Another way of stating the theorem is that every finite set of points that is not collinear has an ordinary line. According to a strengthening of the theorem, every finite point set (not all on one line) has at least a linear number of ordinary lines. An
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
can find an ordinary line in a set of
points in time
.
History
The Sylvester–Gallai theorem was posed as a problem by . suggests that Sylvester may have been motivated by a related phenomenon in
algebraic geometry
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrica ...
, in which the
inflection point
In differential calculus and differential geometry, an inflection point, point of inflection, flex, or inflection (British English: inflexion) is a point on a smooth plane curve at which the curvature changes sign. In particular, in the case o ...
s of a
cubic curve
In mathematics, a cubic plane curve is a plane algebraic curve defined by a cubic equation
:
applied to homogeneous coordinates for the projective plane; or the inhomogeneous version for the affine space determined by setting in such an eq ...
in the
complex projective plane form a
configuration
Configuration or configurations may refer to:
Computing
* Computer configuration or system configuration
* Configuration file, a software file used to configure the initial settings for a computer program
* Configurator, also known as choice board ...
of nine points and twelve lines (the
Hesse configuration
In geometry, the Hesse configuration, introduced by Colin Maclaurin and studied by , is a configuration of 9 points and 12 lines with three points per line and four lines through each point. It can be realized in the complex projective plane as ...
) in which each line determined by two of the points contains a third point. The Sylvester–Gallai theorem implies that it is impossible for all nine of these points to have real coordinates.
claimed to have a short proof of the Sylvester–Gallai theorem, but it was already noted to be incomplete at the time of publication. proved the theorem (and actually a slightly stronger result) in an equivalent formulation, its
projective dual. Unaware of Melchior's proof, again stated the conjecture, which was subsequently proved by
Tibor Gallai, and soon afterwards by other authors.
[; .]
In a 1951 review, Erdős called the result "Gallai's theorem", but it was already called the Sylvester–Gallai theorem in a 1954 review by
Leonard Blumenthal. It is one of many
mathematical topics named after Sylvester.
Equivalent versions
The question of the existence of an ordinary line can also be posed for points in the real
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that ...
RP
2 instead of the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
. The projective plane can be formed from the Euclidean plane by adding extra points "at infinity" where lines that are parallel in the Euclidean plane intersect each other, and by adding a single line "at infinity" containing all the added points. However, the additional points of the projective plane cannot help create non-Euclidean finite point sets with no ordinary line, as any finite point set in the projective plane can be transformed into a Euclidean point set with the same combinatorial pattern of point-line incidences. Therefore, any pattern of finitely many intersecting points and lines that exists in one of these two types of plane also exists in the other. Nevertheless, the projective viewpoint allows certain configurations to be described more easily. In particular, it allows the use of
projective duality
In geometry, a striking feature of projective planes is the symmetry of the roles played by points and lines in the definitions and theorems, and ( plane) duality is the formalization of this concept. There are two approaches to the subject of du ...
, in which the roles of points and lines in statements of projective geometry can be exchanged for each other. Under projective duality, the existence of an ordinary line for a set of non-collinear points in RP
2 is equivalent to the existence of an ''ordinary point'' in a nontrivial
arrangement
In music, an arrangement is a musical adaptation of an existing composition. Differences from the original composition may include reharmonization, melodic paraphrasing, orchestration, or formal development. Arranging differs from orchestr ...
of finitely many lines. An arrangement is said to be trivial when all its lines pass through a common point, and nontrivial otherwise; an ordinary point is a point that belongs to exactly two lines.
Arrangements of lines have a combinatorial structure closely connected to
zonohedra
In geometry, a zonohedron is a convex polyhedron that is centrally symmetric, every face of which is a polygon that is centrally symmetric (a zonogon). Any zonohedron may equivalently be described as the Minkowski sum of a set of line segments i ...
, polyhedra formed as the
Minkowski sum
In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set
: A + B = \.
Analogously, the Minkowski ...
of a finite set of
line segment
In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between i ...
s, called generators. In this connection, each pair of opposite faces of a zonohedron corresponds to a crossing point of an arrangement of lines in the projective plane, with one line for each generator. The number of sides of each face is twice the number of lines that cross in the arrangement. For instance, the
elongated dodecahedron
In geometry, the elongated dodecahedron, extended rhombic dodecahedron, rhombo-hexagonal dodecahedron or hexarhombic dodecahedron is a convex dodecahedron with 8 rhombic and 4 hexagonal faces. The hexagons can be made equilateral, or regular de ...
shown is a zonohedron with five generators, two pairs of opposite hexagon faces, and four pairs of opposite parallelogram faces.
In the corresponding five-line arrangement, two triples of lines cross (corresponding to the two pairs of opposite hexagons) and the remaining four pairs of lines cross at ordinary points (corresponding to the four pairs of opposite parallelograms). An equivalent statement of the Sylvester–Gallai theorem, in terms of zonohedra, is that every zonohedron has at least one parallelogram face (counting rectangles, rhombuses, and squares as special cases of parallelograms). More strongly, whenever sets of
points in the plane can be guaranteed to have at least
ordinary lines, zonohedra with
generators can be guaranteed to have at least
parallogram faces.
Proofs
The Sylvester–Gallai theorem has been proved in many different ways. Gallai's 1944 proof switches back and forth between Euclidean and projective geometry, in order to transform the points into an equivalent configuration in which an ordinary line can be found as a line of slope closest to zero; for details, see . The 1941 proof by Melchior uses projective duality to convert the problem into an equivalent question about arrangements of lines, which can be answered using
Euler's polyhedral formula. Another proof by
Leroy Milton Kelly shows by contradiction that the connecting line with the smallest nonzero distance to another point must be ordinary. And, following an earlier proof by Steinberg,
H. S. M. Coxeter
Harold Scott MacDonald "Donald" Coxeter, (9 February 1907 – 31 March 2003) was a British and later also Canadian geometer. He is regarded as one of the greatest geometers of the 20th century.
Biography
Coxeter was born in Kensington to ...
showed that the metric concepts of slope and distance appearing in Gallai's and Kelly's proofs are unnecessarily powerful, instead proving the theorem using only the axioms of
ordered geometry Ordered geometry is a form of geometry featuring the concept of intermediacy (or "betweenness") but, like projective geometry, omitting the basic notion of measurement. Ordered geometry is a fundamental geometry forming a common framework for affin ...
.
Kelly's proof
This proof is by
Leroy Milton Kelly. call it "simply the best" of the many proofs of this theorem.
Suppose that a finite set
of points is not all collinear. Define a connecting line to be a line that contains at least two points in the collection. By finiteness,
must have a point
and a connecting line
that are a positive distance apart but are closer than all other point-line pairs. Kelly proved that
is ordinary,
by contradiction.
Assume that
is not ordinary. Then it goes through at least three points of
. At least two of these are on the same side of
, the perpendicular projection of
on
. Call them
and
, with
being closest to
(and possibly coinciding with it). Draw the connecting line
passing through
and
, and the perpendicular from
to
on
. Then
is shorter than
. This follows from the fact that
and
are
similar triangles, one contained inside the another.
However, this contradicts the original definition of
and
as the point-line pair with the smallest positive distance. So the assumption that
is not ordinary cannot be true, QED.
Melchior's proof
In 1941 (thus, prior to Erdős publishing the question and Gallai's subsequent proof) Melchior showed that any nontrivial finite arrangement of lines in the projective plane has at least three ordinary points. By duality, this results also says that any finite nontrivial set of points on the plane has at least three ordinary lines.
Melchior observed that, for any graph
embedded in the real projective plane, the formula
must equal
, the
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space' ...
of the projective plane. Here
,
, and
are the number of vertices, edges, and faces of the graph, respectively. Any nontrivial line arrangement on the projective plane defines a graph in which each face is bounded by at least three edges, and each edge bounds two faces; so,
double counting gives the additional inequality
. Using this inequality to eliminate
from the Euler characteristic leads to the inequality
. But if every vertex in the arrangement were the crossing point of three or more lines, then the total number of edges would be at least
, contradicting this inequality. Therefore, some vertices must be the crossing point of only two lines, and as Melchior's more careful analysis shows, at least three ordinary vertices are needed in order to satisfy the inequality
.
As note, the same argument for the existence of an ordinary vertex was also given in 1944 by
Norman Steenrod
Norman Earl Steenrod (April 22, 1910October 14, 1971) was an American mathematician most widely known for his contributions to the field of algebraic topology.
Life
He was born in Dayton, Ohio, and educated at Miami University and University o ...
, who explicitly applied it to the dual ordinary line problem.
Melchior's inequality
By a similar argument, Melchior was able to prove a more general result. For every
, let
be the number of points to which
lines are incident. Then
:
or equivalently,
:
Axiomatics
writes of Kelly's proof that its use of Euclidean distance is unnecessarily powerful, "like using a sledge hammer to crack an almond". Instead, Coxeter gave another proof of the Sylvester–Gallai theorem within
ordered geometry Ordered geometry is a form of geometry featuring the concept of intermediacy (or "betweenness") but, like projective geometry, omitting the basic notion of measurement. Ordered geometry is a fundamental geometry forming a common framework for affin ...
, an axiomatization of geometry in terms of betweenness that includes not only Euclidean geometry but several other related geometries. Coxeter's proof is a variation of an earlier proof given by Steinberg in 1944. The problem of finding a minimal set of axioms needed to prove the theorem belongs to
reverse mathematics
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in cont ...
; see for a study of this question.
The usual statement of the Sylvester–Gallai theorem is not valid in
constructive analysis
In mathematics, constructive analysis is mathematical analysis done according to some principles of constructive mathematics.
This contrasts with ''classical analysis'', which (in this context) simply means analysis done according to the (more comm ...
, as it implies the
lesser limited principle of omniscience, a weakened form of the
law of excluded middle
In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontrad ...
that is rejected as an axiom of constructive mathematics. Nevertheless, it is possible to formulate a version of the Sylvester–Gallai theorem that is valid within the axioms of constructive analysis, and to adapt Kelly's proof of the theorem to be a valid proof under these axioms.
Finding an ordinary line
Kelly's proof of the existence of an ordinary line can be turned into an algorithm that finds an ordinary line by searching for the closest pair of a point and a line through two other points. report the time for this closest-pair search as
, based on a
brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solu ...
of all triples of points, but an algorithm to find the closest given point to each line through two given points, in time
, was given earlier by , as a subroutine for finding the minimum-area triangle determined by three of a given set of points. The same paper of also shows how to construct the dual arrangement of lines to the given points (as used in Melchior and Steenrod's proof) in the same time,
, from which it is possible to identify all ordinary vertices and all ordinary lines. first showed how to find a single ordinary line (not necessarily the one from Kelly's proof) in time
, and a simpler algorithm with the same time bound was described by .
The algorithm of is based on Coxeter's proof using ordered geometry. It performs the following steps:
#Choose a point
that is a
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...
of the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean spac ...
of the given points.
#Construct a line
that passes through
and otherwise stays outside of the convex hull.
#Sort the other given points by the angle they make with
, grouping together points that form the same angle.
#If any of the points is alone in its group, then return the ordinary line through that point and
.
#For each two consecutive groups of points, in the sorted sequence by their angles, form two lines, each of which passes through the closest point to
in one group and the farthest point from
in the other group.
#For each line
in the set of lines formed in this way, find the intersection point of
with
#Return the line
whose intersection point with
is the closest to
.
As the authors prove, the line returned by this algorithm must be ordinary. The proof is either by construction if it is returned by step 4, or by contradiction if it is returned by step 7: if the line returned in step 7 were not ordinary, then the authors prove that there would exist an ordinary line between one of its points and
, but this line should have already been found and returned in step 4.
The number of ordinary lines
While the Sylvester–Gallai theorem states that an arrangement of points, not all collinear, must determine an ordinary line, it does not say how many must be determined. Let
be the minimum number of ordinary lines determined over every set of
non-collinear points. Melchior's proof showed that
. raised the question of whether
approaches infinity with
. confirmed that it does by proving that
. conjectured that
, for all values of
, a conjecture that still stands . This is often referred to as the Dirac–Motzkin conjecture; see for example . proved that
.
Dirac's conjectured lower bound is asymptotically the best possible, as the even numbers
greater than four have a matching upper bound
. The construction, due to
Károly Böröczky, that achieves this bound consists of the vertices of a regular
-gon in the real
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that ...
and another
points (thus,
) on the line at infinity corresponding to each of the directions determined by pairs of vertices. Although there are
pairs of these points, they determine only
distinct directions. This arrangement has only
ordinary lines, the lines that connect a vertex
with the point at infinity collinear with the two neighbors of
. As with any finite configuration in the real projective plane, this construction can be perturbed so that all points are finite, without changing the number of ordinary lines.
For odd
, only two examples are known that match Dirac's lower bound conjecture, that is, with
One example, by , consists of the vertices, edge midpoints, and centroid of an equilateral triangle; these seven points determine only three ordinary lines. The
configuration
Configuration or configurations may refer to:
Computing
* Computer configuration or system configuration
* Configuration file, a software file used to configure the initial settings for a computer program
* Configurator, also known as choice board ...
in which these three ordinary lines are replaced by a single line cannot be realized in the Euclidean plane, but forms a finite
projective space
In mathematics, the concept of a projective space originated from the visual effect of perspective, where parallel lines seem to meet ''at infinity''. A projective space may thus be viewed as the extension of a Euclidean space, or, more generall ...
known as the
Fano plane
In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines ...
. Because of this connection, the Kelly–Moser example has also been called the non-Fano configuration.
The other counterexample, due to McKee,
[.] consists of two regular pentagons joined edge-to-edge together with the midpoint of the shared edge and four points on the line at infinity in the
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that ...
; these 13 points have among them 6 ordinary lines. Modifications of Böröczky's construction lead to sets of odd numbers of points with
ordinary lines.
proved that
except when
is seven. Asymptotically, this formula is already
of the proven
upper bound. The
case is an exception because otherwise the Kelly–Moser construction would be a counterexample; their construction shows that
. However, were the Csima–Sawyer bound valid for
, it would claim that
.
A closely related result is
Beck's theorem, stating a tradeoff between the number of lines with few points and the number of points on a single line.
Ben Green and
Terence Tao
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...
showed that for all sufficiently large point sets (that is,
for some suitable choice of
), the number of ordinary lines is indeed at least
. Furthermore, when
is
odd, the number of ordinary lines is at least
, for some constant
. Thus, the constructions of Böröczky for even and odd (discussed above) are best possible. Minimizing the number of ordinary lines is closely related to the
orchard-planting problem
In discrete geometry, the original orchard-planting problem asks for the maximum number of 3-point lines attainable by a configuration of a specific number of points in the plane. It is also called the tree-planting problem or simply the orchard ...
of maximizing the number of three-point lines, which Green and Tao also solved for all sufficiently large point sets.
The number of connecting lines
As
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
observed, the Sylvester–Gallai theorem immediately implies that any set of
points that are not collinear determines at least
different lines. This result is known as the
De Bruijn–Erdős theorem. As a base case, the result is clearly true for
. For any larger value of
, the result can be reduced from
points to
points, by deleting an ordinary line and one of the two points on it (taking care not to delete a point for which the remaining subset would lie on a single line). Thus, it follows by mathematical induction. The example of a near-pencil, a set of
collinear points together with one additional point that is not on the same line as the other points, shows that this bound is tight.
Generalizations
The Sylvester–Gallai theorem has been generalized to colored point sets in the Euclidean plane, and to systems of points and lines defined algebraically or by distances in a
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
. In general, these variations of the theorem consider only
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. ...
s of points, to avoid examples like the set of all points in the Euclidean plane, which does not have an ordinary line.
Colored points
A variation of Sylvester's problem, posed in the mid-1960s by
Ronald Graham
Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...
and popularized by
Donald J. Newman, considers finite planar sets of points (not all in a line) that are given two colors, and asks whether every such set has a line through two or more points that are all the same color. In the language of sets and
families of sets
Family (from la, familia) is a group of people related either by consanguinity (by recognized birth) or affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its members and of society. Idea ...
, an equivalent statement is that the family of the collinear subsets of a finite point set (not all on one line) cannot have
Property B. A proof of this variation was announced by
Theodore Motzkin
Theodore Samuel Motzkin (26 March 1908 – 15 December 1970) was an Israeli- American mathematician.
Biography
Motzkin's father Leo Motzkin, a Ukrainian Jew, went to Berlin at the age of thirteen to study mathematics. He pursued university stu ...
but never published; the first published proof was by .
Non-real coordinates
Just as the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
or
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that ...
can be defined by using
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every r ...
s for the coordinates of their points (
Cartesian coordinates
A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in ...
for the Euclidean plane and
homogeneous coordinates
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometry ...
for the projective plane), analogous abstract systems of points and lines can be defined by using other number systems as coordinates. The Sylvester–Gallai theorem does not hold for geometries defined in this way over
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s: for some finite geometries defined in this way, such as the
Fano plane
In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines ...
, the set of all points in the geometry has no ordinary lines.
The Sylvester–Gallai theorem also does not directly apply to geometries in which points have coordinates that are pairs of
complex numbers or
quaternion
In mathematics, the quaternion number system extends the complex numbers. Quaternions were first described by the Irish mathematician William Rowan Hamilton in 1843 and applied to mechanics in three-dimensional space. Hamilton defined a quate ...
s, but these geometries have more complicated analogues of the theorem. For instance, in the
complex projective plane there exists a
configuration
Configuration or configurations may refer to:
Computing
* Computer configuration or system configuration
* Configuration file, a software file used to configure the initial settings for a computer program
* Configurator, also known as choice board ...
of nine points,
Hesse's configuration (the inflection points of a cubic curve), in which every line is non-ordinary, violating the Sylvester–Gallai theorem. Such a configuration is known as a
Sylvester–Gallai configuration In geometry, a Sylvester–Gallai configuration consists of a finite subset of the points of a projective space with the property that the line through any two of the points in the subset also passes through at least one other point of the subset.
...
, and it cannot be realized by points and lines of the Euclidean plane. Another way of stating the Sylvester–Gallai theorem is that whenever the points of a Sylvester–Gallai configuration are embedded into a Euclidean space, preserving colinearities, the points must all lie on a single line, and the example of the Hesse configuration shows that this is false for the
complex projective plane. However, proved a complex-number analogue of the Sylvester–Gallai theorem: whenever the points of a Sylvester–Gallai configuration are embedded into a complex projective space, the points must all lie in a two-dimensional subspace. Equivalently, a set of points in three-dimensional complex space whose
affine hull
In mathematics, the affine hull or affine span of a set ''S'' in Euclidean space R''n'' is the smallest affine set containing ''S'', or equivalently, the intersection of all affine sets containing ''S''. Here, an ''affine set'' may be defined a ...
is the whole space must have an ordinary line, and in fact must have a linear number of ordinary lines. Similarly, showed that whenever a Sylvester–Gallai configuration is embedded into a space defined over the quaternions, its points must lie in a three-dimensional subspace.
Matroids
Every set of points in the Euclidean plane, and the lines connecting them, may be abstracted as the elements and flats of a rank-3
oriented matroid
An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary (i.e., non-oriented) matroid a ...
. The points and lines of geometries defined using other number systems than the real numbers also form
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being i ...
s, but not necessarily oriented matroids. In this context, the result of lower-bounding the number of ordinary lines can be generalized to oriented matroids: every rank-3 oriented matroid with
elements has at least
two-point lines, or equivalently every rank-3 matroid with fewer two-point lines must be non-orientable. A matroid without any two-point lines is called a
Sylvester matroid. Relatedly, the Kelly–Moser configuration with seven points and only three ordinary lines forms one of the
forbidden minors for
GF(4)-representable matroids.
[.]
Distance geometry
Another generalization of the Sylvester–Gallai theorem to arbitrary
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
s was conjectured by and proved by . In this generalization, a triple of points in a metric space is defined to be collinear when the
triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
This statement permits the inclusion of degenerate triangles, bu ...
for these points is an equality, and a line is defined from any pair of points by repeatedly including additional points that are collinear with points already added to the line, until no more such points can be added. The generalization of Chvátal and Chen states that every finite metric space has a line that contains either all points or exactly two of the points.
[; ; ]
Notes
References
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
External links
*
*
Proof presentationby
Terence Tao
Terence Chi-Shen Tao (; born 17 July 1975) is an Australian-American mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes ...
at the 2013 Minerva Lectures
{{DEFAULTSORT:Sylvester-Gallai theorem
Euclidean plane geometry
Theorems in discrete geometry
Matroid theory
Articles containing proofs