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

Technische Samenvatting: Gaten van Binaire Numerieke Semigruppen en van Binaire Inclusie-Exclusie Polynomen

Probleemstelling
Dit werk behandelt de structurele eigenschappen van de "gatenverzamelingen" van binaire inclusie-exclusie polynomen, aangeduid als $Q_{\{p,q\}}(x)$, en de afstanden tussen opeenvolgende elementen in de bijbehorende binaire numerieke semigrup $\langle p, q \rangle$. Het polynoom is gedefinieerd als:
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
waarbij $p$ en $q$ onderling ondeelbare gehele getallen zijn met $q \ge p \ge 3$. Wanneer $p$ en $q$ priemgetallen zijn, reduceert $Q_{\{p,q\}}$ tot het cyclotomische polynoom $\Phi_{pq}$.

De gatenverzameling $G(f)$ van een polynoom $f$ is gedefinieerd als de verzameling van verschillen tussen de exponenten van opeenvolgende niet-nul coëfficiënten. Eerder onderzoek (bijvoorbeeld Hong et al., Zhang, Cafure en Cesaratto) had specifieke resultaten vastgesteld voor de grootste gaten van $\Phi_{pq}$ onder bepaalde voorwaarden (bijvoorbeeld $q \equiv \pm 1 \pmod p$), maar een volledige beschrijving van de gehele gatenverzameling voor het algemene binaire geval bleef een open probleem. Het artikel streeft ook naar het karakteriseren van de verzameling van alle mogelijke afstanden tussen opeenvolgende elementen in de semigrup $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$.

Methodologie
De kern technische bijdrage van het artikel is de analyse van een specifieke eigenschap van lineaire permutaties van restklassenstelsels. Laat $p$ een modulus zijn en $u$ een geheel getal onderling ondeelbaar met $p$. De permutatie wordt gegeven door $n \mapsto \langle un \rangle_p$, waarbij $\langle x \rangle_p$ de kleinste niet-negatieve rest van $x$ modulo $p$ aanduidt.

De auteur definieert een "dominante paar" $(a, b)$ met $a < b$ als een paar dat voldoet aan een van de twee ongelijkheden:

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$

Om deze paren te analyseren, introduceert het artikel een representatie van het restklassenstelsel modulo $p$, afgeleid van het algoritme van Euclides toegepast op $p$ en de multiplicatieve inverse van $u$ (aangeduid als $r_1$). Het algoritme van Euclides genereert rijen $(r_i)$ en $(Z_i)$ via $r_{i-1} = Z_i r_i + r_{i+1}$.

De auteur construeert een specifieke representatie voor elk geheel getal $n \in [0, p)$ in de vorm $n = R(z) = \sum z_i (-1)^{i-1} r_i$, waarbij $z$ een tuple is van coëfficiënten die beperkt zijn door de parameters van het algoritme van Euclides. Deze representatie maakt het mogelijk om $\langle un \rangle_p$ expliciet te evalueren in termen van de coëfficiënten $z_i$.

Belangrijkste Bijdragen en Resultaten

1. Karakterisering van Dominante Paren:
   Het artikel bewijst dat de verzameling van verschillen $\{b-a\}$ voor dominante paren exact de verzameling is:
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   waarbij $t$ het aantal stappen in het algoritme van Euclides is. Dit resultaat partitioneert de mogelijke verschillen in verzamelingen $D_i$ gebaseerd op de index $i$ van de Euclidische rij.

2. Gatenverzamelingen van Numerieke Semigruppen:
   Door $u$ te stellen als de multiplicatieve inverse van $q$ modulo $p$, verbindt de auteur de dominante paren met de numerieke semigrup $\langle p, q \rangle$.

   • Laat $S(p, q)$ de verzameling zijn van representeerbare gehele getallen in $[0, (p-1)(q-1)]$ en $N(p, q)$ de verzameling van niet-representeerbare gehele getallen.
   • De verzameling van afstanden tussen opeenvolgende representeerbare gehele getallen, $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$, en de verzameling van afstanden tussen opeenvolgende niet-representeerbare gehele getallen, $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$, worden volledig beschreven.
   • Stelling 1: $S_\Delta(p, q) = N_\Delta(p, q)$ tenzij $q = p+1$, in welk geval $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$. Beide verzamelingen zijn gelijk aan $D_\Delta(p, x_1)$, waarbij $x_1 \equiv q^{-1} \pmod p$.

3. Gatenverzamelingen van Binaire Inclusie-Exclusie Polynomen:
   Het artikel stelt vast dat de gaten van het polynoom $Q_{\{p,q\}}$ overeenkomen met de lengtes van blokken van opeenvolgende representeerbare of niet-representeerbare gehele getallen. Specifiek wordt de gatenverzameling $G(p, q)$ gegeven door:
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   Stelling 2: De gatenverzameling is de vereniging van verzamelingen $G_i$:
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{waarbij } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (Met een lichte modificatie voor de laatste verzameling $G_t$). Dit biedt een volledige, constructieve beschrijving van alle mogelijke gaten.

4. Grenzen voor het Aantal Gaten:
   Stelling 3: Het artikel biedt scherpe grenzen voor de kardinaliteit van de gatenverzameling, $\#G(p, q)$.

   • Bovengrens: $\#G(p, q) \le p - 1$.
   • Ondergrens: $\#G(p, q) \ge k$, waarbij $k$ gedefinieerd is door $F_k < p \le F_{k+1}$ ($F_k$ zijnde de Fibonacci-getallen).
     De auteur merkt op dat dit impliceert dat $\#G(p, q) > c \log p$ voor een zekere constante $c$.

Betekenis en Beweringen
Het artikel claimt een "volledige beschrijving" te bieden van de gatenverzamelingen voor de klasse van binaire inclusie-exclusie polynomen, en generaliseert eerdere resultaten die beperkt waren tot specifieke gevallen (zoals $q \equiv \pm 1 \pmod p$) of specifieke gaten (grootste of op een na grootste).

De primaire betekenis ligt in de reductie van het polynoom-gatenprobleem tot de analyse van lineaire permutaties van restklassenstelsels. De auteur introduceert een representatie van het restklassenstelsel gebaseerd op het algoritme van Euclides die de voorwaarden voor dominante paren "vrijwel transparant" maakt. Het artikel postuleert dat deze representatie op zichzelf van belang is en toekomstige toepassingen kan hebben in andere gebieden, hoewel deze niet gespecificeerd worden.

De resultaten verenigen het begrip van gaten in binaire cyclotomische polynomen en binaire numerieke semigruppen, en tonen aan dat de verzameling van afstanden tussen opeenvolgende elementen in de semigrup identiek is aan de verzameling van verschillen in dominante paren van de bijbehorende lineaire permutatie. Het werk kwantificeert ook de complexiteit van deze gatenverzamelingen, en toont aan dat het aantal verschillende gaten logaritmisch groeit met de modulus $p$ in het slechtste geval (Fibonacci-inputs) en lineair begrensd is door $p$ in het beste geval.