View source for Orchard-planting problem

{{short description|Geometry; how many 3-point lines can n points form}}
{{distinguish|Euclid's orchard}}
[[File:Orchard-planting problem.svg|thumb|An arrangement of nine points (related to the [[Pappus configuration]]) forming ten 3-point lines.]]

In [[discrete geometry]], the original '''orchard-planting problem''' (or the '''tree-planting problem''') asks for the maximum number of 3-point [[Line (geometry)|lines]] attainable by a [[Configuration (geometry)|configuration]] of a specific number of [[Point (geometry)|points]] in the [[euclidean plane|plane]]. There are also investigations into how many {{mvar|k}}-point lines there can be. Hallard T. Croft and [[Paul Erdős]] proved
<math display=block>t_k > \frac{cn^2}{k^3},</math> 
where {{mvar|n}} is the number of points and {{mvar|t<sub>k</sub>}} is the number of {{mvar|k}}-point lines.<ref>''The Handbook of Combinatorics'', edited by [[László Lovász]],  [[Ronald Graham (mathematician)|Ron Graham]], et al, in the chapter titled ''Extremal Problems in Combinatorial Geometry'' by [[Paul Erdős]] and [[George B. Purdy]].</ref> 
Their construction contains some {{mvar|m}}-point lines, where {{math|''m'' > ''k''}}. One can also ask the question if these are not allowed.

==Integer sequence==
Define {{tmath|t_3^\text{orchard}(n)}} to be the  maximum number of 3-point lines attainable with a configuration of {{mvar|n}} points. 
For an arbitrary number of {{mvar|n}} points, {{tmath|t_3^\text{orchard}(n)}} was shown to be  <math>\tfrac{1}{6}n^2 - O(n)</math> in 1974.

The first few values of {{tmath|t_3^\text{orchard}(n)}} are given in the following table {{OEIS|A003035}}.
{| class="wikitable"
|-
! {{mvar|n}}
! 4
! 5
! 6
! 7
! 8
! 9
! 10
! 11
! 12
! 13
! 14
|-
| {{tmath|t_3^\text{orchard}(n)}}
| 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 [[Triviality (mathematics)|trivial]] [[Upper and lower bounds|upper-bound]] for the number of 3-point lines determined by {{mvar|n}} points is
<math display=block>\left\lfloor \binom{n}{2} \Big/ \binom{3}{2} \right\rfloor = \left\lfloor \frac{n^2-n}{6} \right\rfloor.</math>
Using the fact that  [[Sylvester–Gallai theorem#The number of ordinary lines|the number of 2-point lines]] is at least {{tmath|\tfrac{6n}{13} }} {{harv|Csima|Sawyer|1993}}, this upper bound can be lowered to
<math display=block>\left\lfloor \frac{\binom{n}{2} - \frac{6n}{13}}{3} \right\rfloor = \left\lfloor \frac{n^2}{6} - \frac{25n}{78} \right\rfloor.</math>

Lower bounds for {{tmath|t_3^\text{orchard}(n)}} are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of <math>\approx \tfrac{1}{8}n^2</math> was given by [[James Joseph Sylvester|Sylvester]], who placed {{mvar|n}} points on the cubic curve {{math|1=''y'' = ''x''<sup>3</sup>}}.  This was improved to <math>\tfrac{1}{6}n^2 - \tfrac{1}{2}n + 1</math> in 1974 by {{harvs|author1-link=Stefan Burr|last1=Burr|author2-link=Branko Grünbaum|last2=Grünbaum|author3-link=Neil Sloane|last3=Sloane|year=1974|txt}}, using a construction based on [[Weierstrass's elliptic functions]].  An elementary construction using [[hypocycloid]]s was found by {{harvtxt|Füredi|Palásti|1984}} achieving the same lower bound.

In September 2013, [[Ben Joseph Green|Ben Green]] and [[Terence Tao]] published a paper in which they prove that for all point sets of sufficient size, {{math|''n'' &gt; ''n''<sub>0</sub>}}, there are at most 
<math display=block>\frac{n(n-3)}{6} + 1 =  \frac{1}{6}n^2 - \frac{1}{2}n + 1</math>
3-point lines which matches the lower bound established by Burr, Grünbaum and Sloane.<ref>{{harvtxt|Green|Tao|2013}}</ref> Thus, for sufficiently large {{mvar|n}}, the exact value of {{tmath|t_3^\text{orchard}(n)}} is known.

This is slightly better than the bound that would directly follow from their tight lower bound of {{tmath|\tfrac n 2}} for the number of [[Sylvester–Gallai theorem|2-point lines]]: <math>\tfrac{n(n-2)}{6},</math> 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 {{mvar|n}} points lie in a projective plane defined over a finite field. {{harv|Padmanabhan|Shukla|2020}}.

==Notes==
{{reflist}}

==References==
* {{citation|title=Research Problems in Discrete Geometry|last1=Brass|first1=P.|last2=Moser|first2=W. O. J.|last3=Pach|first3=J.|authorlink3=János Pach|publisher=Springer-Verlag|year=2005|isbn=0-387-23815-8}}.
* {{citation|title=The Orchard problem|last1=Burr|first1=S. A.|authorlink1=Stefan Burr|last2=Grünbaum|first2=B.|authorlink2=Branko Grünbaum|last3=Sloane|first3=N. J. A.|authorlink3=Neil Sloane|journal=[[Geometriae Dedicata]]|volume=2|issue=4|pages=397–424|year=1974|doi=10.1007/BF00147569|s2cid=120906839}}.
* {{citation| last1 = Csima | first1 = J. | last2 = Sawyer | first2 = E.| title = There exist 6''n''/13 ordinary points| journal = [[Discrete and Computational Geometry]]| year = 1993| volume = 9| issue = 2 | pages = 187–202| doi = 10.1007/BF02189318| doi-access = free}}.
* {{citation|title=Arrangements of lines with a large number of triangles|last1=Füredi|last2=Palásti|first1=Z.|first2=I.|author1-link=Zoltán Füredi|author2-link= Ilona Palásti |journal=[[Proceedings of the American Mathematical Society]]|volume=92|issue=4|pages=561–566|year=1984|jstor=2045427|doi=10.2307/2045427}}.
* {{citation |last1=Green|first1=Ben|author1-link=Ben Green (mathematician)|last2=Tao|first2=Terence|author2-link=Terence Tao|title=On sets defining few ordinary lines|journal = [[Discrete and Computational Geometry]]|year=2013|doi=    10.1007/s00454-013-9518-9|volume=50|issue=2|pages = 409–468|arxiv=1208.4714|s2cid=15813230}}
* {{citation |last1= Padmanabhan|first1= R.|last2= Shukla|first2=Alok| title=Orchards in elliptic curves over finite fields|journal = [[Finite Fields and Their Applications]]|year=2020|doi= 10.1016/j.ffa.2020.101756|volume=68|issue=2|pages = 101756|arxiv=2003.07172|s2cid= 212725631}}

==External links==
* {{MathWorld |title=Orchard-Planting Problem|urlname=Orchard-PlantingProblem|mode=cs2}}

[[Category:Discrete geometry]]
[[Category:Euclidean plane geometry]]
[[Category:Mathematical problems]]
[[Category:Dot patterns]]