The greedy 3-sumfree sequence $S_{1,g,g+1}$

Sintesi Tecnica: La sequenza greedy 3-sumfree $S_{1,g,g+1}$

Enunciato del Problema
Il saggio affronta la caratterizzazione della sequenza greedy 3-sumfree $S_{x,y,z}$, definita come la sequenza crescente di interi positivi che inizia con $x, y, z$, dove ogni termine successivo è il minimo intero maggiore del precedente che non può essere espresso come somma di tre termini precedenti distinti. Nello specifico, gli autori investigano la sequenza $S_{1,g,g+1}$ per ogni intero $g \ge 2$. Sebbene Bosma et al. [1] avessero precedentemente stabilito descrizioni esplicite per casi specifici piccoli ($g=2, 3, 4$) utilizzando il dimostratore automatico di teoremi Walnut e avessero congetturato una formula uniforme per tutti i $g \ge 2$, una prova generale rimaneva aperta.

Metodologia
Gli autori utilizzano un argomento diretto di somma di intervalli (interval-sumset) anziché fare affidamento sulla dimostrazione automatica dei teoremi. La metodologia procede come segue:

1. Definizione dell'Insieme Candidato ($A_g$): Il saggio definisce un insieme specifico $A_g$ basato sull'aritmetica modulare. Sia $m = 10g + 3$, $e = 2g + 1$ e $f = 6g + 1$. L'insieme $A_g$ consiste nei termini iniziali $\{1, e, f\}$ e in una unione di intervalli periodici $I_k$ e $J_k$ per $k \ge 0$, definiti come:

   • $I_k = km + [g, 2g]$
   • $J_k = km + [6g + 2, 7g + 1]$
     L'insieme $A_g$ è costruito per essere l'unione di questi componenti disgiunti.

2. Riduzione a Due Proposizioni: La prova che $S_{1,g,g+1} = A_g$ è ridotta alla verifica di due proprietà riguardanti la natura "forzata" degli interi (un intero è forzato se è la somma di tre elementi distinti del set):

   • Proposizione 2: Ogni intero $n > g + 1$ che non appartiene ad $A_g$ è forzato (ovvero, può essere scritto come somma di tre elementi distinti di $A_g$).
   • Proposizione 3: Nessun elemento all'interno di $A_g$ è forzato (ovvero, nessun elemento di $A_g$ può essere scritto come somma di tre elementi distinti di $A_g$).

3. Aritmetica degli Intervalli: Il nucleo della prova consiste nel calcolare le somme degli intervalli (sumsets). Utilizzando identità elementari per i sumset degli intervalli (ad esempio, $b_3[u, v] = [3u+3, 3v-3]$), gli autori dimostrano che i vuoti in $A_g$ sono esattamente coperti da somme di tre elementi distinti da $A_g$, mentre le somme di tre elementi di $A_g$ cadono sempre nel complemento di $A_g$ (specificamente, un pattern complementare periodico $C$).

4. Verifica Induttiva: Gli autori utilizzano l'induzione su $n$ per mostre che la regola greedy ammette esattamente gli elementi di $A_g$. Se $n \notin A_g$, esso è forzato da elementi minori di $n$ (che sono nella sequenza per ipotesi induttiva), quindi viene escluso. Se $n \in A_g$, esso non è forzato da elementi minori di $n$, quindi viene ammesso.

Risultati Chiave
Il saggio stabilisce il Teorema 1, che fornisce una caratterizzazione esatta della sequenza $S_{1,g,g+1}$ per tutti i $g \ge 2$:
Un intero $z$ appartiene a $S_{1,g,g+1}$ se e solo se:
$$z \in \{1, 2g + 1, 6g + 1\} \quad \text{oppure} \quad z \pmod{10g + 3} \in [g, 2g] \cup [6g + 2, 7g + 1].$$

Il saggio dettaglia ulteriormente la struttura della sequenza:

• Termini Iniziali: La sequenza inizia con $1, g, g+1, \dots, 2g, 2g+1, 6g+1$.
• Periodicità Eventuale: Dopo i primi $g+4$ termini, la sequenza diventa periodica modulo $m = 10g + 3$.
• Struttura del Periodo: Il blocco ripetitivo ha una lunghezza di $2g + 1$ e consiste nei residui:
  $$6g + 2, 6g + 3, \dots, 7g + 1, g, g + 1, \dots, 2g.$$

Significato e Rivendicazioni
Il saggio sostiene di fornire una dimostrazione diretta della congettura formulata da Bosma, Bruin, Fokkink, Grube, Reuijl e Tromp [1]. Sebbene la congettura sia stata precedentemente verificata meccanicamente per $2 \le g \le 10$, questo lavoro estende il risultato a tutti gli interi $g \ge 2$ attraverso mezzi analitici. Gli autori dichiarano esplicitamente che il loro approccio fornisce una "dimostrazione diretta" utilizzando argomenti di somma di intervalli, contrapponendosi ai metodi computazionali utilizzati nel lavoro precedente. Il saggio fornisce inoltre una descrizione completa della periodicità eventuale, includendo sia il pre-periodo che il blocco ripetitivo, risolvendo interamente la struttura della sequenza.