Orchard-planting problem
In discrete geometry, the original orchard-planting problem (or the tree-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 k-point lines there can be. Hallard T. Croft and Paul Erdős proved
Integer sequence
Define to be the maximum number of 3-point lines attainable with a configuration of n points. For an arbitrary number of n points, was shown to be in 1974.
The first few values of are given in the following table (sequence A003035 in the OEIS).
n | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 4 | 6 | 7 | 10 | 12 | 16 | 19 | 22 | 26 |
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
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 n points on the cubic curve y = x3. This was improved to in 1974 by
In September 2013,
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 n points lie in a projective plane defined over a finite field.(Padmanabhan & Shukla 2020).
Notes
- Ron Graham, et al, in the chapter titled Extremal Problems in Combinatorial Geometry by Paul Erdős and George B. Purdy.
- ^ Green & Tao (2013)
References
- Brass, P.; Moser, W. O. J.; ISBN 0-387-23815-8.
- S2CID 120906839.
- Csima, J.; Sawyer, E. (1993), "There exist 6n/13 ordinary points", .
- JSTOR 2045427.
- S2CID 15813230
- Padmanabhan, R.; Shukla, Alok (2020), "Orchards in elliptic curves over finite fields", S2CID 212725631