Small complete 3-term progression free sets in cyclic groups and vector spaces

Sintesi Tecnica: Insiemi Piccoli e Completi Privi di Progressioni a 3 Termini in Gruppi Ciclici e Spazi Vettoriali

Enunciato del Problema
Il saggio affronta il problema di determinare la dimensione minima di un insieme completo privo di progressioni aritmetiche a 3 termini (3-AP), in strutture algebriche specifiche, ovvero gruppi ciclici ($\mathbb{Z}_m$) e spazi vettoriali finiti ($\mathbb{F}_p^n$). Mentre la dimensione massima degli insiemi privi di 3-AP è un tema centrale nella combinatoria additiva (ad esempio, i teoremi di Roth, Croot-Lev-Pach, Ellenberg-Gijswijt), la dimensione minima di un insieme completo (un insieme che non può essere ampliato senza creare una 3-AP) rappresenta l'analogo dal lato inferiore. Un semplice argomento di conteggio stabilisce che l'ordine di grandezza per questa dimensione minima è almeno la radice quadrata della cardinalità della struttura. Gli autori indagano se questo limite inferiore sia stretto, affrontando problemi aperti riguardanti l'esistenza di tali insiemi con dimensione $O(\sqrt{|G|})$ nei gruppi ciclici e $p^{n/2}$ negli spazi vettoriali.

Metodologia
Gli autori impiegano una combinazione di costruzioni combinatorie esplicite, tecniche di riduzione modulare e geometria algebrica su campi finiti.

1. Gruppi Ciclici ($\mathbb{Z}_m$):

   • Proprietà più forte: Gli autori si concentrano su insiemi completi (2, -1)-evitanti. Un insieme $A$ è (2, -1)-evitante se $A \cap (2A \dot{-} A) = \emptyset$ (dove $2A \dot{-} A = \{2a - b : a, b \in A, a \neq b\}$). Un insieme è completo se $G = A \cup (2A \dot{-} A)$. Questa proprietà è più forte di essere un insieme completo privo di 3-AP, poiché costringe ogni punto esterno a essere un estremo di una progressione con estremi in $A$, piuttosto che permettere al punto esterno di essere un punto medio.
   • Insiemi R-completi: La costruzione si basa su insiemi "R-completi"—sottoinsiemi interi di $[0, R]$ che sono internamente (2, -1)-evitanti e saturano l'intervallo $[-R, 2R]$.
   • Costruzione delle cifre binarie: Utilizzando una costruzione generalizzata delle cifre binarie (Lemma 3.3), gli autori generano insiemi $P$ di dimensione $2^n$ che sono $S_n$-completi. Scegliendo accuratamente la sequenza di cifre $d_i$, assicurano che l'insieme risultante copra un ampio intervallo di moduli $m$.
   • Riduzione Modulare: Il Lemma 3.2 dimostra che un insieme $R$-completo in $\mathbb{Z}$ scende a un insieme completo (2, -1)-evitante in $\mathbb{Z}_m$ ogni volta che $2R < m \leq 3R + 1$.
   • Verifica Finita: Per piccoli moduli ($m < 81$) in cui la costruzione generale non è applicabile o dove potrebbero non esistere insiemi completi (2, -1)-evitanti, gli autori eseguono un enumerazione esaustiva per determinare le dimensioni minime esatte.

2. Spazi Vettoriali ($\mathbb{F}_p^n$):

   • Grafi Quadratici: La costruzione centrale utilizza i grafi di mappe quadratici omogenee $Q: U \to W$. Nello specifico, costruiscono insiemi della forma $A_Q = \{(u, Q(u)) : u \in U\}$.
   • Completezza Estremo-Punto Medio: Gli autori definiscono insiemi "completi estremo-punto medio", dove ogni punto esterno può essere rappresentato sia come un estremo ($x = 2a - b$) sia come un punto medio ($2x = c + d$) di una progressione formata da elementi in $A$. Questa proprietà è cruciale per la costruzione del prodotto.
   • Costruzione di Sottocampo: Costruiscono una mappa quadratica $Q(x, s) = x^2 - \delta s^2$ su un campo di estensione $E = \mathbb{F}_{p^{kL}}$ e un sottocampo $T = \mathbb{F}_{p^k}$, dove $\delta$ è un non-quadrato. Utilizzando somme di caratteri e il limite di Weil, dimostrano che questa mappa è suriettiva e ha un nucleo banale, producendo un insieme completo (2, -1)-evitante in una specifica dimensione $n_0 = k(2L+1)$.
   • Lemma del Prodotto: Per estendere il risultato a tutte le dimensioni $n$, utilizzano un lemma del prodotto (Lemma 4.2). Se $A$ è estremo-punto medio completo in un sottospazio e $B$ è privo di 3-AP completo nelle restanti coordinate, il loro prodotto $A \times B$ è privo di 3-AP completo nello spazio completo. Ciò consente di "completare" le dimensioni speciali con insiemi più piccoli per coprire dimensioni $n$ arbitrarie.

Contributi Chiave e Risultati

1. Gruppi Ciclici:

   • Teorema 1.2: Per ogni intero $m \geq 1$, esiste un insieme completo privo di 3-AP $A \subseteq \mathbb{Z}_m$ con dimensione $|A| < 2\sqrt{m}$.
   • Risultato più forte per $m$ grandi: Per $m \geq 81$, l'insieme costruito soddisfa la proprietà più forte di essere (2, -1)-evitante.
   • Piccoli Moduli: Il saggio fornisce una tabella di valori esatti per $a(3\text{-AP}, \mathbb{Z}_m)$ e $a(2, -1)(\mathbb{Z}_m)$ per $m \leq 80$, notando che gli insiemi completi (2, -1)-evitanti non esistono per certi piccoli moduli (ad esempio, $m \in \{2, 5, 6, 8, 17, 18, 19, 20\}$).

2. Spazi Vettoriali:

   • Teorema 1.3: Per ogni primo dispari fissato $p$ e $\epsilon > 0$, esiste una costante $C_{p,\epsilon}$ tale che per tutti $n \geq 1$:
     $$a(3\text{-AP}, \mathbb{F}_p^n) \leq C_{p,\epsilon} n^{1+\epsilon} p^{n/2} = p^{n/2 + o(n)}$$
   • Questo risultato risolve la variante degli spazi vettoriali nel senso che l'esponente di $p$ è esattamente $n/2$, corrispondendo al limite inferiore salvo un fattore sub-esponenziale.

Significatività e Rivendicazioni
Il saggio sostiene di risolvere due problemi aperti riguardanti la compatibilità del limite inferiore della radice quadrata per gli insiemi completi privi di progressioni:

• Gruppi Ciclici: Stabilisce che il limite inferiore è stretto fino a una costante assoluta (specificamente 2) per tutti i gruppi ciclici, e fornisce costruzioni esplicite per la proprietà più forte (2, -1)-evitante per $m \geq 81$.
• Spazi Vettoriali: Risolve la versione dell'esponente del problema per campi primi dispari fissi, mostrando che la dimensione minima è $p^{n/2 + o(n)}$. Ciò conferma che il banale argomento di conteggio è essenzialmente netto in termini di tasso di crescita esponenziale.

Gli autori notano che, sebbene il fattore costante nel risultato dei gruppi ciclici ($2$) sia superiore al target di $3/2$ suggerito nel loro lavoro precedente, la costruzione è deliberatamente limitata alla proprietà più forte (2, -1)-evitante. Suggeriscono che sfruttare la maggiore libertà della standard 3-AP-completezza (permettendo ai punti esterni di essere punti medi) potrebbe portare a costruzioni più piccole. Allo stesso modo, per gli spazi vettoriali, rimane aperto il quesito sulla presenza di una costante assoluta uniforme indipendente da $n$ e sull'esistenza di tali limiti per insiemi completi (2, -1)-evitanti in ogni dimensione. Il lavoro collega questi problemi di combinatoria additiva alla geometria finita, specificamente ai cappi completi (complete caps) e agli insiemi saturanti.