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. There are also investigations into how many -point lines there can be. Hallard T. Croft and Paul Erdős proved
where is the number of points and is the number of -point lines.
Their construction contains some -point lines, where. One can also ask the question if these are not allowed.

Integer sequence

Define to be the maximum number of 3-point lines attainable with a configuration of points.
For an arbitrary number of points, was shown to be in 1974.
The first few values of are given in the following table.
4567891011121314
12467101216192226

Upper and lower bounds

Since no two lines may share two distinct points, a trivial upper-bound for the number of 3-point lines determined by points is
Using the fact that the number of 2-point lines is at least, this upper bound can be lowered to
Lower bounds for are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of was given by Sylvester, who placed points on the cubic curve. This was improved to in 1974 by, using a construction based on Weierstrass's elliptic functions. An elementary construction using hypocycloids was found by achieving the same lower bound.
In September 2013, Ben Green and Terence Tao published a paper in which they prove that for all point sets of sufficient size,, there are at most
3-point lines which matches the lower bound established by Burr, Grünbaum and Sloane. Thus, for sufficiently large, the exact value of is known.
This is slightly better than the bound that would directly follow from their tight lower bound of for the number of 2-point lines: proved in the same paper and solving a 1951 problem posed independently by Gabriel Andrew Dirac and Theodore Motzkin.
Orchard-planting problem has also been considered over finite fields. In this version of the problem, the points lie in a projective plane defined over a finite field..