Problema del frutteto
# 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

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^2/k^3,$ 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.

## Sequenza di interi

Definendo $t_3^{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_3^{frutteto}(n)$ è pari a $(1/6)n^2$ − O(n), essendo O(n) la funzione O-grande.

Nella seguente tabella sono elencati i primi valori di $t_3^{frutteto}(n):$

| n | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| - | - | - | - | - | - | - | - | - | - | - | - |
| $t_3^{frutteto}(n)$ | 1 | 2 | 4 | 6 | 7 | 10 | 12 | 16 | 19 | 22 | 26 |

## Limiti superiore e inferiore

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, 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_3^{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^2$ ponendo n punti sulla curva cubica y = $x^3.$ Tale valore fu migliorato nel 1974 fino a $[(1/6)n^2$ − (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.

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_0,$ esistono al massimo ([n(n - 3)/6] + 1) = $[(1/6)n^2$ − (1/2)n] + 1 rette passanti da 3 punti, il che eguaglia il limite inferiore ricavato da Burr, Grünbaum e Sloane. 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.

