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

Integer sequence

Define ''t''₃^orchard(''n'') to be the maximum number of 3-point lines attainable with a configuration of ''n'' points.
For an arbitrary number of points, ''n'', ''t''₃^orchard(''n'') was shown to be (1/6)''n''² − O(n) in 1974.

The first few values of ''t''₃^orchard(''n'') 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 ''n'' 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 6''n''/13 , this upper bound can be lowered to
:$\left\lfloor\frac\right\rfloor=\left\lfloor\frac-\frac\right\rfloor.$

Lower bounds for ''t''₃^orchard(''n'') are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of ~(1/8)''n''² was given by Sylvester, who placed ''n'' points on the cubic curve ''y'' = ''x''³. This was improved to 1/6)''n''² − (1/2)''n''nbsp;+ 1 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, ''n'' > ''n''₀, there are at most ( 'n''(''n'' - 3)/6 + 1) = 1/6)''n''² − (1/2)''n'' + 13-point lines which matches the lower bound established by Burr, Grünbaum and Sloane. Thus, for sufficiently large ''n,'' the exact value of ''t''₃^orchard(''n'') is known.

This is slightly better than the bound that would directly follow from their tight lower bound of ''n''/2 for the number of 2-point lines: 'n''(''n'' − 2)/6 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 ''n'' points lie in a projective plane defined over a finite field..

Notes

References

* .
* .
* .
* .
*
*

External links

* {{MathWorld , title=Orchard-Planting Problem, urlname=Orchard-PlantingProblem

Discrete geometry
Euclidean plane geometry
Mathematical problems
Dot patterns