Permutazioni che Minimizzano le Terne Collineari: Un Puzzle Matematico Affascinante

Ciao a tutti, appassionati di matematica e curiosi! Oggi voglio parlarvi di un problema che mi ha sempre affascinato, un rompicapo che mescola ordine, caos e geometria in un modo davvero intrigante. Immaginate di dover disporre dei punti su una griglia, ma con una regola ferrea: evitare il più possibile che tre di essi finiscano sulla stessa linea retta. Sembra un gioco, vero? Eppure, ci porta dritti nel cuore di questioni matematiche profonde.

Il Problema: Evitare le Linee Rette

Il problema classico, noto come “No-3-in-a-Line” di Dudeney, chiede quanti punti al massimo possiamo piazzare su una griglia (n times n) senza che tre di essi siano allineati. Non è affatto banale! Sappiamo che non possono essere più di (2n), ma trovare il numero esatto o anche solo un limite superiore stretto è ancora una sfida aperta.

Questo problema ha legami sorprendenti con altre aree, come il problema del triangolo di Heilbronn (trovare la disposizione di punti che massimizza l’area del triangolo più piccolo) e il problema di Kakeya sui campi finiti (trovare l’insieme più piccolo di punti che contiene una linea in ogni direzione).

Nel nostro caso specifico, ci concentriamo su una variante: prendiamo un “campo finito” (mathbb{F}_q), un insieme di numeri con (q) elementi (dove (q) è una potenza di un numero primo) in cui possiamo fare somme, sottrazioni, moltiplicazioni e divisioni come al solito. Consideriamo poi una permutazione (sigma) di questo campo, cioè una funzione che riordina gli elementi di (mathbb{F}_q) senza ripetizioni. Il “grafico” di questa permutazione è l’insieme di punti ((x, sigma(x))) nel piano affine (AG(q,2)) definito su (mathbb{F}_q).

La domanda cruciale è: quale permutazione (sigma) produce un grafico con il minor numero possibile di “terne collineari”? Una terna collineare è semplicemente un insieme di tre punti distinti del grafico che giacciono sulla stessa linea retta.

Alla Ricerca del Minimo: Un Numero Magico

Per anni, i matematici si sono interrogati su quale fosse questo numero minimo. Per i campi (mathbb{F}_q) dove (q) è una potenza di un primo dispari e (q > 2), una congettura proposta da Cooper e Solymosi nel 2009 suggeriva che il numero minimo di terne collineari fosse esattamente ((q-1)/2). Sembra un numero piccolo, quasi magico nella sua semplicità!

Ebbene, questa congettura è stata confermata! Grazie ai lavori di Li nel 2019, che si basano su risultati potenti di Blokhuis e Mazzocca riguardanti insiemi di punti particolari nella geometria proiettiva, ora sappiamo con certezza che ((q-1)/2) è il limite inferiore. Non si può fare di meglio!

L’Identikit delle Permutazioni Ottimali: Coniche e Trasformazioni

Ma quali sono queste permutazioni “speciali” che raggiungono il minimo? La bellezza sta nel fatto che non sono permutazioni qualsiasi. Per caratterizzarle, dobbiamo fare un salto nella geometria proiettiva (PG(2,q)). Mappando i punti del grafico della permutazione ((x, sigma(x))) in questo spazio proiettivo (come ([x:sigma(x):1])) e aggiungendo due punti “all’infinito” ([1:0:0] e [0:1:0]), otteniamo un insieme (Omega) di (q+2) punti.

Il risultato chiave di Blokhuis e Mazzocca ci dice che se questo insieme (Omega) corrisponde a una permutazione con il numero minimo di terne collineari, allora (Omega) deve essere una conica non degenere (come un’ellisse o un’iperbole nel mondo reale) a cui è stato aggiunto un punto esterno ad essa.

Tornando al nostro piano affine, questo significa che le permutazioni (sigma) che minimizzano le terne collineari non sono casuali, ma hanno una struttura algebrica ben definita. Sono quelle che, tolto al massimo un punto specifico (il punto “esterno” della costruzione proiettiva), corrispondono all’equazione di una conica della forma (cxy + dx + ey + f = 0). Manipolando questa equazione, scopriamo che queste permutazioni sono quasi tutte delle Trasformazioni Lineari Frazionarie Estese (ELFTP – Extended Linear Fractional Transformation Permutations). Hanno una forma del tipo:
[ sigma(x) = frac{alpha x + beta}{x + gamma} ]
per quasi tutti gli (x), con un valore specifico assegnato a (x = -gamma) (dove il denominatore si annullerebbe) per completare la permutazione. I parametri (alpha, beta, gamma) devono soddisfare (alpha gamma ne beta) per garantire che sia effettivamente una permutazione.

La Più Semplice di Tutte: Un Campione Lessicografico

Tra tutte le permutazioni ELFTP che raggiungono il minimo di ((q-1)/2) terne collineari, ce n’è una particolarmente “semplice” o, più formalmente, la più piccola secondo l’ordine lessicografico (cioè quella che inizia con i valori più piccoli possibili: (sigma(0)=0, sigma(1)=1, sigma(2)=2), ecc.). Cooper e Solymosi avevano congetturato quale fosse, e anche questa congettura è stata confermata nel lavoro discusso qui!

La permutazione “campionessa” lessicografica è definita così:

• (sigma(x) = x / (x-1)) se (x neq 1)
• (sigma(1) = 1) (che corrisponde al valore (alpha) della forma ELFTP con (alpha=1, beta=0, gamma=-1))

(Notate che per (x=0), (sigma(0) = 0/(-1) = 0)). Questa specifica permutazione è l’unica ELFTP che soddisfa (sigma(0)=0, sigma(1)=1, sigma(2)=2), garantendole il titolo di “lessicograficamente minima”.

Generalizzazioni e Connessioni: Piani Affini e Quadrati Latini

Una cosa interessante è che la dimostrazione del fatto che ogni permutazione su un campo finito di ordine dispari (q) deve avere almeno una terna collineare (anzi, almeno ((q-1)/2)) può essere generalizzata. Vale per qualsiasi “piano affine finito” di ordine dispari (q), non solo quelli standard (AG(q,2)) costruiti sui campi finiti. Un piano affine è una struttura geometrica con punti e linee che soddisfano certi assiomi di parallelismo. Una “permutazione generalizzata” in questo contesto è un insieme di (q) punti che interseca ogni linea di due famiglie parallele (“orizzontali” e “verticali”) esattamente una volta.

Si dimostra che ogni permutazione generalizzata in un piano affine di ordine dispari (q) ha almeno ((q+1)/2) coppie di punti sulla stessa linea di una data famiglia “obliqua”, il che implica, per il principio dei cassetti, che almeno una linea obliqua deve contenere almeno 3 punti della permutazione.

Questa proprietà ha una curiosa traduzione nel linguaggio dei Quadrati Latini Mutuamente Ortogonali (MOLs). Un insieme completo di MOLs di ordine (q) corrisponde a un piano affine. La proprietà delle terne collineari si traduce così: per ogni insieme completo di (q-1) MOLs di ordine dispari (q), esiste almeno un quadrato (M_j) e un simbolo (k) tale che (k) appare almeno 3 volte sulla diagonale principale di (M_j). Affascinante, no?

Territori Inesplorati e Domande Aperte

Ma la storia non finisce qui. Cosa succede se il piano affine non è quello “standard” derivato da un campo finito (cioè, se deriva da un piano proiettivo non-Desarguesiano)? Sappiamo che il limite inferiore ((q-1)/2) vale anche per questi piani più esotici? E quali sono i valori minimi effettivi?

Abbiamo fatto qualche calcolo per i piani di ordine 9 (il più piccolo ordine non primo per cui esistono piani non-Desarguesiani). Ce ne sono 7 non isomorfi. Per 6 di essi, il numero minimo di terne collineari (Psi(mathbb{A})) è risultato essere 4 (che è proprio ((9-1)/2)). Ma, sorprendentemente, per uno di essi (ottenuto cancellando una linea speciale dal “piano di Hall”), il minimo è 5! Questo suggerisce che la struttura fine del piano conta eccome!

Altre domande rimangono aperte:

• Qual è il numero minimo di terne collineari (Psi(n)) per una permutazione di (mathbb{Z}_n) quando (n) è un numero composto? Per quali (n) questo minimo è maggiore di zero?
• È vero che le permutazioni (generalizzate) che raggiungono il numero minimo di terne collineari non contengono mai quattro punti allineati (collineari)? Per il caso standard (AG(q,2)), sembra di sì, come conseguenza degli argomenti usati per trovare il minimo, ma in generale?

Come vedete, partire da un problema apparentemente semplice come disporre punti evitando linee ci ha portato in un viaggio attraverso campi finiti, geometrie proiettive, coniche, quadrati latini e questioni ancora irrisolte. La matematica è piena di queste connessioni sorprendenti e di misteri che aspettano solo di essere svelati. Chissà quali altre scoperte ci riserva lo studio di queste affascinanti permutazioni!

Fonte: Springer