On the Frobenius Number and Genus of a Collection of Semigroups Generalizing Repunit Numerical Semigroups

Titolo del Lavoro

Numero di Frobenius e Genere di una Collezione di Semigruppi che Generalizzano i Semigruppi Numerici Repunit

1. Il Problema

Il lavoro si concentra sul problema di Frobenius per una specifica classe di semigruppi numerici. Dato un insieme di generatori $A = (a_1, a_2, \dots, a_n)$ di interi positivi con $\gcd(A)=1$, il problema consiste nel determinare:

• Il numero di Frobenius $F(A)$: il più grande intero che non può essere espresso come combinazione lineare non negativa degli elementi di $A$.
• Il genere $g(A)$: il numero di interi positivi che non appartengono al semigruppo $\langle A \rangle$.
• I numeri pseudo-Frobenius e il tipo del semigruppo.

Sebbene esista una formula chiusa per $n=2$ (formula di Sylvester), per $n \ge 3$ il problema è generalmente difficile e non ammette formule chiuse universali. Gli autori mirano a risolvere questo problema per una collezione generalizzata di semigruppi che include, come casi particolari, i semigruppi Repunit, Mersenne, Thabit, Proth e altri, permettendo anche che il parametro $d$ sia un intero negativo (una novità rispetto alla letteratura precedente).

2. Metodologia

Gli autori introducono una collezione generale di semigruppi, denominata Collection GCNS, definita da generatori della forma:
$$A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$$
dove le sequenze $B=(b_i)$ e $H=(h_i)$ seguono ricorrenze specifiche ($b_1=1, b_{i+1}=s_i b_i + 1$ e $h_i = u b_i + 1$).

La metodologia si basa su tre pilastri fondamentali:

1. Insiemi di Apéry e Minimizzazione:
   Utilizzando la teoria degli insiemi di Apéry, il numero di Frobenius e il genere sono ridotti al calcolo dei minimi elementi in classi di congruenza modulo $a$. Questo porta a definire un problema di minimizzazione ausiliario $O^H_B(M)$, che cerca di minimizzare una somma pesata di variabili soggette a un vincolo lineare.

2. Sequenze Ordinate e Algoritmo Greedy:
   Gli autori sfruttano il concetto di sequenza ordinata (orderly sequence). Dimostrano che, sotto certe condizioni sulle ricorrenze di $b_i$ (in particolare $s_i \ge s_{i-1}$), la sequenza $B$ è ordinata. Ciò implica che il problema di minimizzazione può essere risolto efficientemente utilizzando l'algoritmo greedy (che prende il maggior numero possibile dell'elemento più grande disponibile).

3. Analisi della Presentazione Greedy:
   Viene introdotta una "presentazione greedy" $X(r)$ per ogni resto $r$. Gli autori dimostrano che, sotto condizioni specifiche sui parametri ($ua + d + k - 2 \ge \sum s_i$ e $s_i \le u+1$), la funzione che mappa i resti ai valori nell'insieme di Apéry è monotona. Questo permette di identificare il massimo dell'insieme di Apéry (e quindi $F(A)$) semplicemente analizzando la presentazione greedy di $a-1$.

3. Contributi Chiave e Risultati

A. Formule Generali per la Collezione GCNS

Il risultato principale è il Teorema 2.12, che fornisce formule chiuse per $F(A)$ e $g(A)$ per la collezione generalizzata GCNS, a condizione che i parametri soddisfino determinate disuguaglianze.

• Formula di Frobenius: $F(A)$ è espresso in termini della somma degli elementi della presentazione greedy di $a-1$.
• Formula del Genere: $g(A)$ è calcolato sommando le somme degli elementi delle presentazioni greedy per tutti i resti da $1$a$a-1$.

B. Generalizzazione dei Semigruppi Repunit e Mersenne

Applicando i risultati generali al caso specifico in cui $b_i = \frac{b^i-1}{b-1}$, $u=b-1$, e $a = m\frac{b^n-1}{b-1}$, gli autori ottengono:

• Formule chiuse per i semigruppi Repunit generalizzati.
• Come caso particolare ($b=2, m=1, d=1$), recuperano le formule note per i semigruppi Mersenne (Corollari 3.2 e 3.3).
• Determinazione del tipo $t(A)$ e dell'insieme dei numeri pseudo-Frobenius $PF(A)$ per questa classe (Teorema 3.4).

C. Generalizzazione dei Semigruppi Thabit

Per il caso $b_i = 2^i - 1$, $u=1$, e $a = 3 \cdot 2^n - 1$, gli autori derivano formule per i semigruppi Thabit generalizzati (Teorema 4.1 e 4.4), fornendo esplicitamente $F(A)$, $g(A)$ e $PF(A)$.

D. Risoluzione Parziale del Problema Aperto per i Semigruppi Proth

Il lavoro affronta il Problema Aperto 1.3 relativo ai semigruppi Proth $P_m(n)$, generati da $\{m 2^{n+i} + 1\}$.

• Gli autori forniscono una caratterizzazione completa dell'insieme di Apéry per $P_m(n)$ (Teorema 5.2).
• Derivano formule per il numero di Frobenius e il genere in base alla presentazione greedy di $(2r+q)2^n$ (Teoremi 5.4 e 5.5).
• Poiché la struttura della presentazione greedy dipende dai valori specifici di $m$, non esiste un'unica formula polinomiale semplice per ogni $m$, ma gli autori forniscono un algoritmo e una tabella (Tabella 1) con formule esplicite per $m < 50$, risolvendo parzialmente il problema aperto.

E. Nuovi Semigruppi

La metodologia viene applicata per derivare nuove formule per una classe di semigruppi definita da $A = (a, 2a+d, \dots, 2^ka+(2^k-1)d)$ con $a = m(2^k-1) + 2^{k-1}-1$, un caso che sembra non essere stato trattato in letteratura con queste formule chiuse (Teorema 6.1).

4. Significato e Impatto

• Unificazione: Il lavoro offre un approccio unificato che generalizza e unifica risultati dispersi su diverse famiglie di semigruppi (Repunit, Mersenne, Thabit, Proth) sotto un'unica cornice teorica (Collection GCNS).
• Innovazione Tecnica: L'introduzione della possibilità di avere $d$ negativo estende la validità delle formule a casi precedentemente non coperti o più complessi.
• Efficienza Computazionale: L'uso dell'algoritmo greedy su sequenze ordinate semplifica drasticamente il calcolo di $F(A)$ e $g(A)$, trasformando un problema di ottimizzazione complessa in una procedura deterministica e veloce.
• Progresso su Problemi Aperti: La risoluzione parziale del problema di Frobenius per i semigruppi Proth per $m$ arbitrario (tramite la classificazione basata sulla presentazione greedy) rappresenta un significativo passo avanti rispetto alla letteratura esistente, che forniva risultati solo per casi specifici di $m$.

In sintesi, questo articolo fornisce strumenti potenti e formule chiuse per analizzare una vasta gamma di semigruppi numerici, risolvendo casi specifici noti e aprendo nuove direzioni per l'analisi di strutture combinatorie più complesse.