Gaps of Binary Numerical Semigroups and of Binary Inclusion-Exclusion Polynomials

Sintesi Tecnica: Lacune dei Semigruppi Numerici Binari e dei Polinomi di Inclusione-Esclusione Binari

Enunciato del Problema
Questo lavoro affronta le proprietà strutturali degli "insiemi di lacune" dei polinomi di inclusione-esclusione binari, indicati con $Q_{\{p,q\}}(x)$, e le distanze tra elementi consecutivi nel semigruppo numerico binario associato $\langle p, q \rangle$. Il polinomio è definito come:
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
dove $p$ e $q$ sono interi coprimi con $q \ge p \ge 3$. Quando $p$ e $q$ sono primi, $Q_{\{p,q\}}$ si riduce al polinomio ciclotomico $\Phi_{pq}$.

L'insieme di lacune $G(f)$ di un polinomio $f$ è definito come l'insieme delle differenze tra gli esponenti dei coefficienti non nulli consecutivi. Ricerche precedenti (ad esempio Hong et al., Zhang, Cafure e Cesaratto) avevano stabilito risultati specifici per le lacune massime di $\Phi_{pq}$ in determinate condizioni (ad esempio $q \equiv \pm 1 \pmod p$), ma una descrizione completa dell'intero insieme di lacune per il caso binario generale rimaneva un problema aperto. Il lavoro mira anche a caratterizzare l'insieme di tutte le possibili distanze tra elementi consecutivi nel semigruppo $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$.

Metodologia
Il contributo tecnico fondamentale del lavoro è l'analisi di una proprietà specifica delle permutazioni lineari dei sistemi residui. Sia $p$ un modulo e $u$ un intero coprimo a $p$. La permutazione è data da $n \mapsto \langle un \rangle_p$, dove $\langle x \rangle_p$ denota il residuo non negativo minimo di $x$ modulo $p$.

L'autore definisce una "coppia dominante" $(a, b)$ con $a < b$ come una coppia che soddisfa una delle due disuguaglianze:

1. $\max(\langle ua \rangle_p, \langle ub \rangle_p) < \min_{a < n < b} \langle un \rangle_p$
2. $\min(\langle ua \rangle_p, \langle ub \rangle_p) > \max_{a < n < b} \langle un \rangle_p$

Per analizzare queste coppie, il lavoro introduce una rappresentazione del sistema residuo modulo $p$ derivata dall'algoritmo euclideo applicato a $p$ e all'inverso moltiplicativo di $u$ (denotato $r_1$). L'algoritmo euclideo genera le sequenze $(r_i)$ e $(Z_i)$ tramite $r_{i-1} = Z_i r_i + r_{i+1}$.

L'autore costruisce una rappresentazione specifica per qualsiasi intero $n \in [0, p)$ nella forma $n = R(z) = \sum z_i (-1)^{i-1} r_i$, dove $z$ è una tupla di coefficienti vincolata dai parametri dell'algoritmo euclideo. Questa rappresentazione permette la valutazione esplicita di $\langle un \rangle_p$ in termini dei coefficienti $z_i$.

Contributi e Risultati Chiave

1. Caratterizzazione delle Coppie Dominanti:
   Il lavoro dimostra che l'insieme delle differenze $\{b-a\}$ per le coppie dominanti è esattamente l'insieme:
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   dove $t$ è il numero di passi nell'algoritmo euclideo. Questo risultato partiziona le possibili differenze in insiemi $D_i$ basati sull'indice $i$ della sequenza euclidea.

2. Insiemi di Lacune dei Semigruppi Numerici:
   Ponendo $u$ come l'inverso moltiplicativo di $q$ modulo $p$, l'autore collega le coppie dominanti al semigruppo numerico $\langle p, q \rangle$.

   • Sia $S(p, q)$ l'insieme degli interi rappresentabili in $[0, (p-1)(q-1)]$ e $N(p, q)$ l'insieme degli interi non rappresentabili.
   • L'insieme delle distanze tra interi rappresentabili consecutivi, $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$, e l'insieme delle distanze tra interi non rappresentabili consecutivi, $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$, sono completamente descritti.
   • Teorema 1: $S_\Delta(p, q) = N_\Delta(p, q)$ a meno che $q = p+1$, caso in cui $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$. Entrambi gli insiemi sono uguali a $D_\Delta(p, x_1)$, dove $x_1 \equiv q^{-1} \pmod p$.

3. Insiemi di Lacune dei Polinomi di Inclusione-Esclusione Binari:
   Il lavoro stabilisce che le lacune del polinomio $Q_{\{p,q\}}$ corrispondono alle lunghezze di blocchi di interi rappresentabili o non rappresentabili consecutivi. Nello specifico, l'insieme di lacune $G(p, q)$ è dato da:
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   Teorema 2: L'insieme di lacune è l'unione degli insiemi $G_i$:
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{dove } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (Con una leggera modifica per l'insieme finale $G_t$). Questo fornisce una descrizione completa e costruttiva di tutte le possibili lacune.

4. Limiti sul Numero di Lacune:
   Teorema 3: Il lavoro fornisce limiti stretti sulla cardinalità dell'insieme di lacune, $\#G(p, q)$.

   • Limite superiore: $\#G(p, q) \le p - 1$.
   • Limite inferiore: $\#G(p, q) \ge k$, dove $k$ è definito da $F_k < p \le F_{k+1}$ ($F_k$ essendo i numeri di Fibonacci).
     L'autore nota che ciò implica $\#G(p, q) > c \log p$ per una certa costante $c$.

Significato e Affermazioni
Il lavoro afferma di fornire una "descrizione completa" degli insiemi di lacune per la classe dei polinomi di inclusione-esclusione binari, generalizzando risultati precedenti limitati a casi specifici (come $q \equiv \pm 1 \pmod p$) o a lacune specifiche (massime o seconde massime).

Il significato primario risiede nella riduzione del problema delle lacune polinomiali all'analisi delle permutazioni lineari dei sistemi residui. L'autore introduce una rappresentazione del sistema residuo basata sull'algoritmo euclideo che rende le condizioni per le coppie dominanti "abbastanza trasparenti". Il lavoro ipotizza che questa rappresentazione sia di interesse indipendente e possa avere applicazioni future in altre aree, sebbene non ne specifichi di concrete.

I risultati unificano la comprensione delle lacune nei polinomi ciclotomici binari e nei semigruppi numerici binari, mostrando che l'insieme delle distanze tra elementi consecutivi nel semigruppo è identico all'insieme delle differenze nelle coppie dominanti della permutazione lineare associata. Il lavoro quantifica anche la complessità di questi insiemi di lacune, mostrando che il numero di lacune distinte cresce logaritmicamente con il modulo $p$ nel caso peggiore (input di Fibonacci) ed è limitato linearmente da $p$ nel caso migliore.