On the Guy-Kelly Conjecture for the No-Three-In-Line Problem

Il presente articolo chiarisce un errore individuato da Gabor Ellmann nel 2004 nell'argomento euristico di Guy e Kelly sulla congettura del problema "no-three-in-line", fornendo i dettagli della correzione che porta a un nuovo limite superiore, la cui derivazione era stata recentemente presentata anche da Prellberg.

L'essenziale

Immagina di avere una griglia quadrata, come un enorme scacchiere, dove ogni casella contiene un punto. Se il lato della griglia è lungo $n$, hai un totale di $n^2$ punti.

Il "Problema del Non-Tre-in-Linea" è una sfida matematica divertente: qual è il numero massimo di punti che puoi scegliere su questa griglia senza che tre di essi si allineino perfettamente su una stessa linea retta?

Pensaci come a un gioco di "non fare tre in fila" su una scala gigantesca. Se scegli troppi punti, prima o poi ne troverai tre che formano una riga dritta (come tre pedine su una scacchiera o tre stelle allineate nel cielo).

La vecchia teoria (e il suo errore)

Fino a poco tempo fa, i matematici Guy e Kelly avevano fatto una "scommessa" basata su calcoli probabilistici. Immagina di lanciare dei dadi per scegliere i punti: loro pensavano che, man mano che la griglia diventava infinitamente grande, il numero massimo di punti che potevi scegliere fosse circa 2 volte la lunghezza del lato ($2n$).

Hanno usato una formula matematica complessa per stimare questa probabilità, un po' come un meteorologo che cerca di prevedere la pioggia guardando le nuvole. La loro formula diceva che la risposta era legata a un numero specifico (circa 2,08 volte $n$).

Il "bug" nel codice

Nel 2004, un matematico di nome Gabor Ellmann ha notato qualcosa di strano. Ha scoperto che Guy e Kelly avevano commesso un piccolo errore di calcolo, quasi come se avessero scritto una formula sbagliata in un foglio di Excel.

L'analogia della ricetta:
Immagina che Guy e Kelly stessero cercando di calcolare quanti biscotti si possono fare con un sacco di farina. Hanno usato una ricetta che diceva: "Se hai $n$ tazze di farina, puoi fare $2n$ biscotti". Ma quando hanno fatto i calcoli per vedere quanti biscotti potevano fare senza che si bruciassero (senza che tre punti si allineassero), hanno usato la quantità sbagliata di farina nei loro calcoli intermedi.

Invece di calcolare quanto spazio occupano $k \times n$ punti (dove $k$ è una variabile che cambia), hanno usato per sbaglio $2n$ (come se avessero fissato il numero di punti a due volte il lato della griglia) in un passaggio cruciale della formula. È come se avessero misurato la lunghezza di un tavolo usando un righello che era già stato piegato.

La correzione

Gabor Ellmann ha corretto questo errore. Quando Guy e Kelly hanno visto il calcolo corretto, hanno dovuto cambiare la loro "scommessa".

Il nuovo numero magico non è più circa 2,08, ma è $\pi / \sqrt{3}$, che è circa 1,81.

Quindi, la nuova teoria dice: "Non puoi mettere 2 punti per ogni riga della griglia. Il massimo che puoi mettere è circa 1,81 punti per ogni riga, altrimenti sei quasi sicuro di trovare tre punti allineati".

Perché è importante questo articolo?

L'autore di questo testo, Paul Voutier, scrive per dire: "Ehi, tutti sappiamo che c'è stato un errore e che la risposta è cambiata, ma nessuno ha mai scritto esattamente dove fosse l'errore e come si correggeva".

È come se tutti sapessero che un'auto ha un motore rumoroso, ma nessuno avesse mai aperto il cofano per mostrare quale vite era allentata. Voutier apre il cofano, mostra la vite allentata (l'errore nella formula a pagina 530 del vecchio articolo) e spiega come stringerla per far funzionare di nuovo il motore.

In sintesi

1. Il Gioco: Metti punti su una griglia senza farne allineare tre.
2. L'Errore: I vecchi calcoli dicevano che potevi mettere molti punti (circa 2 per riga), ma avevano sbagliato un passaggio matematico.
3. La Soluzione: Correggendo l'errore, il numero massimo di punti scende a circa 1,81 per riga.
4. Il Contributo: Questo articolo è importante perché spiega chiaramente e pubblicamente dove e come è stato fatto l'errore, chiarendo la confusione che durava da anni.

È una storia di come la matematica sia un lavoro di squadra: anche i grandi geni possono sbagliare un calcolo, ma grazie all'occhio attento di qualcuno (Ellmann) e alla pazienza di chi lo spiega (Voutier), la verità viene a galla.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del documento "ON THE GUY-KELLY CONJECTURE FOR THE NO-THREE-IN-LINE PROBLEM" di Paul M. Voutier, presentata in italiano.

1. Il Problema: Il Problema "No-Three-in-Line"

Il documento si concentra sul classico problema di geometria discreta noto come "No-Three-in-Line" (Nessuna tre allineate).

• Definizione: Sia $S_n$ l'insieme dei $n^2$ punti nel piano $\mathbb{R}^2$ con coordinate intere $(x, y)$ tali che $1 \le x, y < n$.
• Obiettivo: Determinare $f_n$, la dimensione massima di un sottoinsieme $T \subseteq S_n$ tale che nessun trio di punti in $T$ sia collineare.
• Stato attuale: È noto che $f_n \le 2n$ (per il principio dei cassetti). Per $n \le 64$, è stato dimostrato che $f_n = 2n$. Tuttavia, si ipotizza che per $n$ sufficientemente grande, $f_n$ sia strettamente minore di $2n$.

2. Metodologia e Argomento Euristiche

Il cuore del lavoro di Voutier è l'analisi e la correzione dell'argomentazione euristica presentata da Guy e Kelly nel 1968 (riferimento [3] nel testo originale) per stimare il comportamento asintotico di $f_n$.

L'approccio originale di Guy e Kelly si basa su un calcolo probabilistico:

1. Conteggio delle terne collineari: Calcolano il numero totale di terne di punti collineari in $S_n$, denotato come $t_n$, trovando che $t_n \sim \frac{3}{\pi^2} n^4 \log(n)$.
2. Probabilità di non allineamento: Calcolano la probabilità che tre punti scelti a caso non siano allineati, ottenendo $1 - \frac{18 \log(n)}{\pi^2 n^2}$.
3. Assunzione di indipendenza: Assumendo che gli eventi di non allineamento siano indipendenti, stimano la probabilità che un insieme di $kn$ punti non contenga tre punti allineati.
4. Stima del numero di soluzioni: Combinano il numero di modi per scegliere $kn$ punti con la probabilità calcolata sopra per stimare il numero totale di soluzioni valide.

3. Contributo Chiave: Identificazione e Correzione dell'Errore

Il contributo principale di Voutier è fornire i dettagli tecnici mancanti nella letteratura su un errore scoperto da Gabor Ellmann nel 2004 (e menzionato da Guy nel 2004), che ha portato a una revisione della congettura.

• La natura dell'errore: L'errore si trova specificamente a pagina 530, riga -4, dell'articolo originale di Guy e Kelly.
  • Errore originale: Guy e Kelly hanno utilizzato erroneamente $2n$(il limite superiore noto) al posto della variabile generica$kn$ nelle stime fattoriali necessarie per derivare la loro equazione (5).
  • Correzione: Sostituendo $2n$con$kn$nell'approssimazione di Stirling per i termini$(n^2)! / (n^2 - kn)!$e$(kn)!$, l'esponente dell'approssimazione cambia.
  • Dettaglio tecnico: Nell'equazione originale, il termine nell'esponente era $-2 + 3k^3/\pi^2$. La correzione corretta questo termine in $-k + 3k^3/\pi^2$.

4. Risultati e Nuova Congettura

La correzione dell'errore algebrico porta a una modifica sostanziale del valore asintotico stimato per $f_n$.

• Congettura Originale (Errata): Guy e Kelly avevano congetturato che $f_n \sim (2\pi^2/3)^{1/3} n$.
• Congettura Corretta: Applicando la correzione di Ellmann, il nuovo comportamento asintotico diventa:
  $$f_n \sim \left( \frac{\pi}{\sqrt{3}} \right) n \approx 1.813799 \, n$$
  Questo valore è significativamente inferiore al limite superiore banale di $2n$.

5. Significato e Contesto

• Ripristino della letteratura: Sebbene la correzione fosse nota a R.K. Guy e a Gabor Ellmann, e fosse menzionata brevemente sul sito web di A. Flammenkamp, non era mai stata pubblicata in dettaglio nella letteratura accademica formale prima di questo lavoro di Voutier.
• Conferma indipendente: Il documento nota che lavori molto recenti di Thomas Prellberg (2026) hanno derivato indipendentemente la stessa congettura corretta, confermando la validità della correzione.
• Criticità dell'assunzione di indipendenza: Voutier menziona anche che l'assunzione di indipendenza degli eventi (usata per derivare la formula probabilistica) è stata recentemente messa in discussione da alcuni ricercatori (es. Nathan Kaplan) e da evidenze empiriche su griglie simmetriche. Tuttavia, il lavoro di Voutier si concentra specificamente sulla correzione dell'errore algebrico interno all'argomentazione originale, indipendentemente dalla validità dell'assunzione probabilistica sottostante.

In sintesi, il paper di Voutier è un lavoro di "correzione tecnica" che chiarisce un errore di calcolo specifico in un classico risultato di geometria discreta, portando a una congettura più precisa sul limite superiore asintotico del problema "No-Three-in-Line".