Problema del frutteto

In matematica, e in particolare in geometria discreta, il problema del frutteto o, più propriamente, il problema di piantumazione del frutteto è un problema inerente, data una precisa configurazione di uno specifico numero di punti in un piano, il massimo numero di rette passanti per tre punti.

Storia modifica

Proposto per la prima volta nel 1867 in un numero del The Educational Times dal matematico inglese James Joseph Sylvester, il problema rappresenta un caso particolare di un problema più vasto che è stato poi derivato a partire proprio dal problema del frutteto, ossia quello di trovare, data una specifica configurazione di n punti su un piano, il numero massimo di rette passanti per k punti.

Per quest'ultimo problema, Hallard T. Croft e Paul Erdős hanno dimostrato che t_k > c n²/k³, dove n è il numero di punti e t_k è il numero di rette passanti per k punti. La costruzione realizzata da Croft e Erdős contiene anche alcune rette passanti per m punti, dove m è maggiore di k, che, in una trattazione rigorosa del problema, non dovrebbero essere contate.^[1]

Sequenza di interi modifica

Definendo t₃^frutteto(n) come il massimo numero possibile di rette che passano per 3 punti data una configurazione di n punti, nel 1974 è stato dimostrato che, per un numero qualunque di n, t₃^frutteto(n) è pari a (1/6)n² − O(n), essendo O(n) la funzione O-grande.^[2]

Nella seguente tabella sono elencati i primi valori di t₃^frutteto(n):^[3]

n	4	5	6	7	8	9	10	11	12	13	14
t₃^frutteto(n)	1	2	4	6	7	10	12	16	19	22	26

Limiti superiore e inferiore modifica

Poiché non esistono due rette che hanno due punti distinti in comune, un limite superiore banale del numero di rette passanti per tre punti in una configurazione di n punti è:

$\left\lfloor {\binom {n}{2}}{\Big /}{\binom {3}{2}}\right\rfloor =\left\lfloor {\frac {n^{2}-n}{6}}\right\rfloor .$

Considerando il fatto che il numero di rette passanti per due punti è almeno 6n/13,^[4] tale limite superiore può essere abbassato a:

$\left\lfloor {\frac {{\binom {n}{2}}-6n/13}{3}}\right\rfloor =\left\lfloor {\frac {n^{2}}{6}}-{\frac {25n}{78}}\right\rfloor .$

I limiti inferiori di t₃^frutteto(n) sono ottenuti da configurazioni di insiemi di punti con molte rette passanti per 3 punti distinti. Il già citato Sylvester determinò il limite inferiore di valore ~(1/8)n² ponendo n punti sulla curva cubica y = x³. Tale valore fu migliorato nel 1974 fino a [(1/6)n² − (1/2)n] + 1 dai matematici Burr, Grünbaum e Sloane, utilizzando una configurazione basata sulle funzioni ellittiche di Weierstrass. Dieci anni dopo, nel 1984, Füredi e Palásti trovarono lo stesso valore per il limite inferiore grazie a una configurazione più elementare realizzata utilizzando gli ipocicloidi.^[5]

Nel settembre 2013, Ben Green e Terence Tao hanno pubblicato un articolo contenente la dimostrazione che per tutti gli insiemi di punti di dimensione sufficientemente grande, n > n₀, esistono al massimo ([n(n - 3)/6] + 1) = [(1/6)n² − (1/2)n] + 1 rette passanti da 3 punti, il che eguaglia il limite inferiore ricavato da Burr, Grünbaum e Sloane.^[6] Tale risultato è leggermente migliore di quello che deriverebbe direttamente dal limite inferiore stretto, pari a n/2, trovato dai due matematici per il numero di rette passanti per due punti, ossia [n(n − 2)/6]; il sopraccitato valore di n/2 è stato dimostrato dai due nello stesso articolo risolvendo un problema posto nel 1951 indipendentemente da Gabriel Andrew Dirac e Theodore Motzkin.^[6]

Note modifica

^ Paul Erdős e George B. Purdy, Extremal problems in combinatorial geometry, in G. Luisa Bozzano, Jeffrey M. Lemm e Gerard Meurant (a cura di), Handbook of Combinatorics Volume 1, Elsevier, 1995, p. 823. URL consultato il 23 marzo 2021.
^ Stefan A. Burr, Branko Grünbaum e Neil J. A. Sloane, The Orchard problem, in Geometriae Dedicata, vol. 2, n. 4, 1974, pp. 397-424, DOI:10.1007/BF00147569.
^ (EN) Sequenza A003035, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
^ J. Csima e E. Sawyer, There exist 6n/13 ordinary points, in Discrete and Computational Geometry, vol. 9, 1993, pp. 187-202, DOI:10.1007/BF02189318.
^ Z. Füredi e I. Palásti, Arrangements of lines with a large number of triangles, in Proceedings of the American Mathematical Society, vol. 92, n. 4, 1984, pp. 561-566, DOI:10.2307/2045427, JSTOR 2045427.
^ ^a ^b Ben Green e Terence Tao, On sets defining few ordinary lines, in Discrete and Computational Geometry, vol. 50, n. 2, 2013, pp. 409-468, DOI:10.1007/s00454-013-9518-9, arXiv:1208.4714.

Collegamenti esterni modifica

(EN) Eric W. Weisstein, Problema del frutteto, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] Paul Erdős e George B. Purdy, Extremal problems in combinatorial geometry, in G. Luisa Bozzano, Jeffrey M. Lemm e Gerard Meurant (a cura di), Handbook of Combinatorics Volume 1, Elsevier, 1995, p. 823. URL consultato il 23 marzo 2021.

[burr-2] Stefan A. Burr, Branko Grünbaum e Neil J. A. Sloane, The Orchard problem, in Geometriae Dedicata, vol. 2, n. 4, 1974, pp. 397-424, DOI:10.1007/BF00147569.

[3] (EN) Sequenza A003035, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.

[4] J. Csima e E. Sawyer, There exist 6n/13 ordinary points, in Discrete and Computational Geometry, vol. 9, 1993, pp. 187-202, DOI:10.1007/BF02189318.

[5] Z. Füredi e I. Palásti, Arrangements of lines with a large number of triangles, in Proceedings of the American Mathematical Society, vol. 92, n. 4, 1984, pp. 561-566, DOI:10.2307/2045427, JSTOR 2045427.

[tao-6] Ben Green e Terence Tao, On sets defining few ordinary lines, in Discrete and Computational Geometry, vol. 50, n. 2, 2013, pp. 409-468, DOI:10.1007/s00454-013-9518-9, arXiv:1208.4714.

[1]

[2]

[3]

[4]

[5]

[6]