On the general no-three-in-line problem

Questo articolo estende il problema "no-three-in-line" a dimensioni $d \geq 3$, dimostrando che il numero di punti che possono essere posizionati su una griglia $n^d$ senza che tre di essi siano allineati soddisfa il limite inferiore $\gg n^{d-1}\sqrt[2d]{d}$.

L'essenziale

Immagina di avere una griglia gigante, come un tabellone da gioco o una scacchiera, ma invece di essere piatta (2D), può avere molte dimensioni: 3D, 4D, e così via. Su questa griglia, ogni incrocio è un punto.

Il problema che affronta questo articolo è un classico rompicapo matematico chiamato "No-Three-in-Line" (Nessuno-tre-in-linea). La domanda è semplice: qual è il numero massimo di punti che puoi mettere su questa griglia senza che tre di loro finiscano mai allineati su una stessa linea retta?

Se metti troppi punti, prima o poi ne troverai tre che formano una riga perfetta. L'autore, T. Agama, vuole sapere quanti punti possiamo mettere in sicurezza su griglie molto grandi e in molte dimensioni diverse.

Ecco come funziona la sua soluzione, spiegata con metafore semplici:

1. Il Trucco dello "Specchio Inverso" (La Compressione)

Immagina che la griglia sia una stanza piena di persone. Normalmente, se guardi da lontano, le persone vicine all'angolo sembrano tutte vicine tra loro.
L'autore usa un trucco matematico chiamato mappa di compressione. È come se avessi uno specchio magico che inverte le distanze:

• Chi è molto lontano dal centro viene spinto vicino al centro.
• Chi è molto vicino al centro viene spinto lontano.

È un po' come guardare un'immagine attraverso una lente d'ingrandimento che distorce tutto: i bordi si rimpiccioliscono e il centro si espande. Questo "ribaltamento" aiuta a riorganizzare i punti in modo che non si allineino più facilmente.

2. Le "Palline Magiche" (Le Sfere Indotte)

Una volta applicato questo trucco dello specchio, l'autore immagina di disegnare delle sfere (o palline) intorno ai punti.

• Non sono palline normali, ma palline "indotte" dalla distorsione dello specchio.
• La regola è: scegliamo solo i punti che si trovano esattamente sulla superficie di queste palline.

L'autore dimostra una cosa incredibile: se scegli i punti che stanno sulla "pelle" di queste palline speciali, è matematicamente impossibile che tre di loro finiscano allineati. È come se la forma della pallina costringesse i punti a stare in posizioni "strane" e disordinate, rendendo l'allineamento impossibile.

3. Il Conteggio (Quanti punti possiamo salvare?)

Ora, la domanda è: quanti di questi punti "salvi" possiamo trovare sulla nostra griglia gigante?

L'autore usa un metodo di conteggio intelligente:

• Immagina che la griglia sia un grande cubo fatto di piccoli cubetti.
• Le sue "palline magiche" attraversano questo cubo.
• I punti che ci interessano sono quelli che la pallina tocca mentre attraversa i cubetti della griglia.

Grazie alla sua formula, l'autore scopre che il numero di punti sicuri che possiamo mettere cresce molto velocemente. Se la griglia ha dimensione $n$ e $d$ dimensioni, il numero di punti sicuri è circa:
$$n^{d-1} \times (\text{qualcosa che dipende da } d)$$

In parole povere: su una griglia molto grande, possiamo mettere quasi tanti punti quanti ne starebbero su una "fetta" della griglia, senza mai creare una linea di tre.

Perché è importante?

Prima di questo lavoro, sapevamo la risposta per griglie piatte (2D) e per cubi (3D). Questo articolo estende la soluzione a qualsiasi numero di dimensioni (4D, 5D, 100D...).

È come se avessimo scoperto una regola universale per organizzare oggetti in spazi multidimensionali senza farli mai "allineare" in modo noioso. L'autore ci dice che, non importa quanto sia alta la dimensionalità dello spazio, c'è sempre un modo intelligente (usando questo "specchio inverso") per riempirlo di punti sicuri.

In sintesi:
L'autore ha inventato un modo per "piegare" lo spazio matematico (come un origami o uno specchio distorto) in modo che, quando scegliamo i punti sulla superficie di queste forme piegate, essi rifiutino automaticamente di mettersi in fila. Questo ci permette di riempire griglie enormi con un numero enorme di punti, risolvendo un vecchio rompicapo matematico per tutte le dimensioni possibili.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "ON THE GENERAL NO-THREE-IN-LINE PROBLEM" di T. Agama, redatta in italiano.

Titolo: Sul Problema Generale "Nessun Tre Allineati" (General No-Three-in-Line Problem)

Autore: T. Agama
Data: 13 Marzo 2026 (indicata nel manoscritto)
Classificazione: Geometria Discreta, Combinatoria Additiva.

---

1. Il Problema

Il paper affronta una generalizzazione in dimensioni superiori del classico "Problema Nessun Tre Allineati" (No-Three-in-Line Problem).

• Formulazione Classica: Data una griglia quadrata $n \times n$ (punti a coordinate intere da 1 a $n$), qual è il numero massimo di punti che si possono selezionare in modo che nessun trio di punti sia collineare?
• Stato dell'Arte:
  • Nel piano ($d=2$), il problema è ben studiato ma la crescita esatta della funzione è ancora oggetto di congetture (si sa che è $O(n)$, ma il coefficiente esatto è dibattuto).
  • In tre dimensioni ($d=3$), Pór e Wood hanno dimostrato che è possibile posizionare $\Theta(n^2)$ punti senza tre allineati.
• Obiettivo del Paper: Estendere questo risultato a dimensioni arbitrarie $d \ge 2$ e fornire un limite inferiore costruttivo esplicito per il numero massimo di punti in una griglia ipercubica $[n]^d = \{1, \dots, n\}^d$.

2. Metodologia e Strumenti Matematici

L'autore introduce un approccio geometrico-analitico basato su una nuova trasformazione chiamata mappa di compressione (compression map).

A. La Mappa di Compressone ($V_m$)

Definita per una scala $m \in (0, 1]$, la mappa agisce sulle coordinate di un punto $\vec{x} = (x_1, \dots, x_d)$ come segue:
$$V_m(\vec{x}) = \left( \frac{m}{x_1}, \frac{m}{x_2}, \dots, \frac{m}{x_d} \right)$$
Questa trasformazione inverte le coordinate rispetto a una scala fissa, spingendo i punti vicini all'origine lontano da essa e viceversa.

B. Statistiche Chiave

Per analizzare la geometria dei punti compressi, l'autore definisce due grandezze:

1. Massa ($M$): La somma delle coordinate inverse (scalate):
   $$M(V_m(\vec{x})) = \sum_{i=1}^d \frac{m}{x_i}$$
2. Gap di Compressione ($G$): Una misura della deviazione simmetrica tra un punto e la sua immagine riflessa/compressa:
   $$G \circ V_m(\vec{x}) = \left\| \vec{x} - V_m(\vec{x}) \right\| = \left\| \left( x_1 - \frac{m}{x_1}, \dots, x_d - \frac{m}{x_d} \right) \right\|$$

C. Le Sfere Indotte (Induced Balls)

Il cuore della costruzione è la definizione di una "sfera indotta" da un punto $\vec{x}$ sotto compressione. Una sfera $B$ è definita dall'ineguaglianza:
$$\left\| \vec{y} - \frac{1}{2}\left(\vec{x} + V_m(\vec{x})\right) \right\| < \frac{1}{2} G \circ V_m(\vec{x})$$
L'autore dimostra che:

• Esiste una proprietà di annidamento (nesting): sfere più piccole sono contenute in sfere più grandi se i loro gap di compressione sono ordinati correttamente.
• Esistono punti limite e punti interni all'interno di queste sfere.

D. Punti Ammissibili (Admissible Points)

Si definiscono "punti ammissibili" come i punti che giacciono esattamente sul bordo (superficie) della sfera indotta.

• Proprietà Fondamentale (Proposizione 3.15): Nessun trio di punti ammissibili sulla stessa sfera indotta è collineare. Questa è la proprietà geometrica chiave che risolve il problema combinatorio.

3. Risultati Principali

Il teorema principale (Teorema 4.1) stabilisce un limite inferiore per il numero di punti non collineari in una griglia $d$-dimensionale $n^d$.

Teorema: Per ogni dimensione $d \ge 2$, il numero di punti che possono essere posizionati nella griglia $n \times \dots \times n$ senza che tre siano allineati soddisfa il limite inferiore:
$$\gg n^{d-1} d^{1/(2d)}$$
dove la costante implicata è assoluta (indipendente da $n$).

Dettagli della Costruzione:

1. Si sceglie un punto $\vec{x}$ con coordinate sufficientemente grandi (fino a $n^d$) e si applica la compressione con scala $m = o(1)$ (che tende a 0 al crescere della dimensione o di $n$).
2. Si costruisce la sfera indotta da $\vec{x}$.
3. Si contano i punti reticolari (lattice points) che giacciono sulla superficie di questa sfera e che sono contenuti nella griglia $[n]^d$.
4. Grazie alla proprietà di non collinearità dei punti sul bordo della sfera, questi punti costituiscono una soluzione valida al problema.
5. L'analisi asintotica della densità locale di questi punti sulla "scheletro" $(d-1)$-dimensionale della scatola porta al termine $n^{d-1}$. Il fattore $d^{1/(2d)}$ emerge dalla dipendenza dimensionale del gap di compressione e dalla stima della massa.

Casi Particolari:

• Per $d=2$: Il risultato recupera un limite inferiore del tipo $\ge n \cdot C$ (coerente con la crescita lineare attesa nel piano).
• Per $d=3$: Si ottiene $\ge n^2 \cdot C$, estendendo il risultato noto di Pór e Wood con una costante esplicita dipendente da $d$.

4. Contributi Chiave e Significato

1. Generalizzazione Dimensionale: Il lavoro estende il fenomeno $\Theta(n^{d-1})$ (noto per $d=3$) a tutte le dimensioni $d \ge 2$, fornendo una formula unificata.
2. Costruttività: A differenza di molti risultati probabilistici o puramente esistenziali, la soluzione è costruttiva. I punti sono esplicitamente descritti come intersezioni tra una superficie geometrica specifica (la sfera indotta) e la griglia intera.
3. Nuovo Punto di Vista Geometrico: L'uso della mappa di compressione e delle statistiche associate (massa e gap) offre un meccanismo uniforme per generare configurazioni non collineari in qualsiasi dimensione, aggirando le difficoltà combinatorie dirette.
4. Stima Quantitativa: Il paper non si limita a dimostrare l'esistenza, ma fornisce una stima quantitativa esplicita del fattore moltiplicativo dipendente dalla dimensione ($d^{1/(2d)}$), sebbene l'autore noti che l'esponente su $d$ potrebbe non essere ottimale.

5. Conclusione

Il paper di T. Agama risolve una generalizzazione significativa del problema "nessun tre allineati" introducendo una tecnica geometrica basata sulla compressione reciproca. Dimostrando che è possibile selezionare almeno $O(n^{d-1} d^{1/(2d)})$ punti in una griglia $d$-dimensionale, l'autore collega la geometria discreta all'analisi asintotica, fornendo un metodo robusto per la costruzione di configurazioni estreme in spazi ad alta dimensione.