果樹園の植え付け問題

離散幾何学における、元々の果樹園植え付け問題（または植樹問題）は、平面上の特定の数の点の配置によって達成可能な3 点直線の最大数を求めるものです。 k点直線がいくつあり得るかについての研究もあります。Hallard T. Croft とPaul Erdős はを証明しました 。 ここで、nは点の数、t _{k は}k点直線の数です。^{[1]彼らの構成には、} m > k のm点直線が いくつか含まれています。これらが許可されないかどうかを尋ねることもできます。 $${\displaystyle t_{k}>{\frac {cn^{2}}{k^{3}}},}$$

⁠ ⁠ を、${\displaystyle t_{3}^{\text{果樹園}}(n)}$n点の構成で達成可能な 3 点線の最大数として定義します。任意の数のn点に対して、⁠ ⁠ が${\displaystyle t_{3}^{\text{果樹園}}(n)}$1974 年に示されました 。 ${\displaystyle {\tfrac {1}{6}}n^{2}-O(n)}$

⁠ ⁠${\displaystyle t_{3}^{\text{orchard}}(n)}$の最初のいくつかの値は、次の表に示されています ( OEISのシーケンスA003035 )。

2本の直線は2つの異なる点を共有することはできないので、n個の点 によって決まる3点直線の数の自明な 上限は、 2点直線の数が少なくとも⁠ ⁠である という事実 （Csima & Sawyer 1993）を使用することで、この上限は次のように下げることができる。 $${\displaystyle \left\lfloor {\binom {n}{2}}{\Big /}{\binom {3}{2}}\right\rfloor =\left\lfloor {\frac {n^{2}-n}{6}}\right\rfloor .}$$${\displaystyle {\tfrac {6n}{13}}}$$${\displaystyle \left\lfloor {\frac {{\binom {n}{2}}-{\frac {6n}{13}}}{3}}\right\rfloor =\left\lfloor {\frac {n^{2}}{6}}-{\frac {25n}{78}}\right\rfloor .}$$

⁠ ⁠${\displaystyle t_{3}^{\text{orchard}}(n)}$の下限は、多数の 3 点直線による点の集合の構成によって与えられます。 の最も初期の二次下限は、3 次曲線y = x ³上にn個の点を置いたシルベスターによって与えられました。これは、1974 年にバー、グリューンバウム、スローン(1974) によって、ワイエルシュトラスの楕円関数 に基づく構成を使用してまで改良されました。ハイポサイクロイドを使用した基本的な構成は、Füredi & Palásti (1984) によって発見され、同じ下限を達成しました。 ${\displaystyle \approx {\tfrac {1}{8}}n^{2}}$${\displaystyle {\tfrac {1}{6}}n^{2}-{\tfrac {1}{2}}n+1}$

2013年9月、ベン・グリーンとテレンス・タオは、十分な大きさのすべての点集合n > n ₀に対して、最大で 3点直線が存在し、それがバー、グリューンバウム、スローンによって確立された下限と一致することを証明した論文を発表しました。^{[2]したがって、十分に大きい}nに対して、 ⁠ ⁠の正確な値はわかっています。 $${\displaystyle {\frac {n(n-3)}{6}}+1={\frac {1}{6}}n^{2}-{\frac {1}{2}}n+1}$$${\displaystyle t_{3}^{\text{orchard}}(n)}$

これは、 2 点直線の数に対する⁠ ⁠${\displaystyle {\tfrac {n}{2}}}$の厳しい下限から直接導かれる上限よりもわずかに優れています。これは、同じ論文で証明され、ガブリエル・アンドリュー・ディラックとセオドア・モツキンが独立に提起した 1951 年の問題を解いたものです 。 ${\displaystyle {\tfrac {n(n-2)}{6}},}$

果樹園の植え付け問題も有限体上で検討されています。この問題のバージョンでは、n個の点が有限体上に定義された射影平面上にあります。(Padmanabhan & Shukla 2020)。

• Brass, P.; Moser, WOJ; Pach, J. (2005)、離散幾何学における研究問題、Springer-Verlag、ISBN 0-387-23815-8。
• バール, 南オーストラリア州;グリュンバウム、B . ; NJA スローン(1974)、「果樹園の問題」、Geometriae Dedicata、2 (4): 397–424、doi :10.1007/BF00147569、S2CID  120906839。
• Csima, J.; Sawyer, E. (1993)、「6 n /13 個の通常の点が存在する」、離散および計算幾何学、9 (2): 187–202、doi : 10.1007/BF02189318。
• Füredi, Z. ; Palásti, I. (1984)、「多数の三角形による直線の配置」、アメリカ数学会紀要、92 (4): 561–566、doi :10.2307/2045427、JSTOR  2045427。
• グリーン、ベン;タオ、テレンス(2013)、「少数の通常線を定義する集合について」、離散および計算幾何学、50 (2): 409–468、arXiv : 1208.4714、doi :10.1007/s00454-013-9518-9、S2CID  15813230
• Padmanabhan, R.; Shukla, Alok (2020)、「有限体上の楕円曲線の果樹園」、有限体とその応用、68 (2): 101756、arXiv : 2003.07172、doi :10.1016/j.ffa.2020.101756、S2CID  212725631

• ワイスシュタイン、エリック W.、「果樹園植え付け問題」、MathWorld