discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geom ...

, the original orchard-planting problem (or the tree-planting problem) asks for the maximum number of 3-point lines attainable by 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 a specific number of

points A point is a small dot or the sharp tip of something. Point or points may refer to: Mathematics * Point (geometry), an entity that has a location in space or on a plane, but has no extent; more generally, an element of some abstract topologica ...

in the plane. There are also investigations into how many -point lines there can be. Hallard T. Croft and

Paul Erdős Paul Erdős ( ; 26March 191320September 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 discrete mathematics, g ...

proved

t_k > \frac,

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

\tfracn^2 - O(n)

in 1974. The first few values of are given in the following table .

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

\left\lfloor \binom \Big/ \binom \right\rfloor = \left\lfloor \frac \right\rfloor.

Using the fact that the number of 2-point lines is at least , this upper bound can be lowered to

\left\lfloor \frac \right\rfloor = \left\lfloor \frac - \frac \right\rfloor.

Lower bounds for are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of

\approx \tfracn^2

was given by

Sylvester Sylvester or Silvester is a name derived from the Latin adjective ''silvestris'' meaning "wooded" or "wild", which derives from the noun ''silva'' meaning "woodland". Classical Latin spells this with ''i''. In Classical Latin, ''y'' represented a ...

, who placed points on the cubic curve . This was improved to

\tfracn^2 - \tfracn + 1

in 1974 by , using a construction based on

Weierstrass's elliptic functions In mathematics, the Weierstrass elliptic functions are elliptic functions that take a particularly simple form. They are named for Karl Weierstrass. This class of functions is also referred to as ℘-functions and they are usually denoted by the s ...

. An elementary construction using

hypocycloid In geometry, a hypocycloid is a special plane curve generated by the trace of a fixed point on a small circle that rolls within a larger circle. As the radius of the larger circle is increased, the hypocycloid becomes more like the cycloid creat ...

s 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

\frac + 1 =  \fracn^2 - \fracn + 1

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:

\tfrac,

proved in the same paper and solving a 1951 problem posed independently by Gabriel Andrew Dirac and

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 ...

. 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. .

Notes

References

* . * . * . * . * *

External links

* {{MathWorld , title=Orchard-Planting Problem, urlname=Orchard-PlantingProblem, mode=cs2 Discrete geometry Euclidean plane geometry Mathematical problems Dot patterns