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

Technische Zusammenfassung: Lücken von binären numerischen Halbgruppen und von binären Inklusions-Exklusions-Polynomen

Problemstellung
Diese Arbeit behandelt die strukturellen Eigenschaften der „Lückensets" (gapsets) von binären Inklusions-Exklusions-Polynomen, bezeichnet als $Q_{\{p,q\}}(x)$, sowie die Abstände zwischen aufeinanderfolgenden Elementen in der zugehörigen binären numerischen Halbgruppe $\langle p, q \rangle$. Das Polynom ist definiert als:
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
wobei $p$ und $q$ teilerfremde ganze Zahlen mit $q \ge p \ge 3$ sind. Wenn $p$ und $q$ Primzahlen sind, reduziert sich $Q_{\{p,q\}}$ auf das Kreisteilungspolynom $\Phi_{pq}$.

Das Lückenset $G(f)$ eines Polynoms $f$ ist definiert als die Menge der Differenzen zwischen den Exponenten aufeinanderfolgender nicht-verschwindender Koeffizienten. Vorherige Forschung (z. B. Hong et al., Zhang, Cafure und Cesaratto) hatte spezifische Ergebnisse für die größten Lücken von $\Phi_{pq}$ unter bestimmten Bedingungen (z. B. $q \equiv \pm 1 \pmod p$) etabliert, doch eine vollständige Beschreibung des gesamten Lückensets für den allgemeinen binären Fall blieb ein offenes Problem. Die Arbeit zielt zudem darauf ab, die Menge aller möglichen Abstände zwischen aufeinanderfolgenden Elementen in der Halbgruppe $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$ zu charakterisieren.

Methodik
Der wesentliche technische Beitrag der Arbeit ist die Analyse einer spezifischen Eigenschaft linearer Permutationen von Restklassensystemen. Sei $p$ ein Modul und $u$ eine zu $p$ teilerfremde ganze Zahl. Die Permutation ist gegeben durch $n \mapsto \langle un \rangle_p$, wobei $\langle x \rangle_p$ den kleinsten nichtnegativen Rest von $x$ modulo $p$ bezeichnet.

Der Autor definiert ein „dominantes Paar" $(a, b)$ mit $a < b$ als ein Paar, das eine der beiden Ungleichungen erfüllt:

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$

Zur Analyse dieser Paare führt die Arbeit eine Darstellung des Restklassensystems modulo $p$ ein, die vom Euklidischen Algorithmus abgeleitet ist, angewendet auf $p$ und das multiplikative Inverse von $u$ (bezeichnet als $r_1$). Der Euklidische Algorithmus erzeugt Sequenzen $(r_i)$ und $(Z_i)$ via $r_{i-1} = Z_i r_i + r_{i+1}$.

Der Autor konstruiert eine spezifische Darstellung für jede ganze Zahl $n \in [0, p)$ in der Form $n = R(z) = \sum z_i (-1)^{i-1} r_i$, wobei $z$ ein Tupel von Koeffizienten ist, das durch die Parameter des Euklidischen Algorithmus eingeschränkt ist. Diese Darstellung ermöglicht die explizite Auswertung von $\langle un \rangle_p$ in Abhängigkeit von den Koeffizienten $z_i$.

Hauptbeiträge und Ergebnisse

1. Charakterisierung dominanter Paare:
   Die Arbeit beweist, dass die Menge der Differenzen $\{b-a\}$ für dominante Paare genau die Menge ist:
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   wobei $t$ die Anzahl der Schritte im Euklidischen Algorithmus ist. Dieses Ergebnis partitioniert die möglichen Differenzen in Mengen $D_i$ basierend auf dem Index $i$ der Euklidischen Sequenz.

2. Lückensets numerischer Halbgruppen:
   Indem $u$ als das multiplikative Inverse von $q$ modulo $p$ gewählt wird, verbindet der Autor die dominanten Paare mit der numerischen Halbgruppe $\langle p, q \rangle$.

   • Sei $S(p, q)$ die Menge der darstellbaren ganzen Zahlen in $[0, (p-1)(q-1)]$ und $N(p, q)$ die Menge der nicht-darstellbaren ganzen Zahlen.
   • Die Menge der Abstände zwischen aufeinanderfolgenden darstellbaren ganzen Zahlen, $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$, und die Menge der Abstände zwischen aufeinanderfolgenden nicht-darstellbaren ganzen Zahlen, $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$, werden vollständig beschrieben.
   • Satz 1: $S_\Delta(p, q) = N_\Delta(p, q)$, es sei denn, $q = p+1$, in welchem Fall $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$. Beide Mengen sind gleich $D_\Delta(p, x_1)$, wobei $x_1 \equiv q^{-1} \pmod p$.

3. Lückensets binärer Inklusions-Exklusions-Polynome:
   Die Arbeit stellt fest, dass die Lücken des Polynoms $Q_{\{p,q\}}$ den Längen von Blöcken aufeinanderfolgender darstellbarer oder nicht-darstellbarer ganzer Zahlen entsprechen. Spezifisch ist das Lückenset $G(p, q)$ gegeben durch:
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   Satz 2: Das Lückenset ist die Vereinigung von Mengen $G_i$:
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{wobei } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (Mit einer leichten Modifikation für die letzte Menge $G_t$). Dies liefert eine vollständige, konstruktive Beschreibung aller möglichen Lücken.

4. Schranken für die Anzahl der Lücken:
   Satz 3: Die Arbeit liefert scharfe Schranken für die Kardinalität des Lückensets, $\#G(p, q)$.

   • Obere Schranke: $\#G(p, q) \le p - 1$.
   • Untere Schranke: $\#G(p, q) \ge k$, wobei $k$ durch $F_k < p \le F_{k+1}$ definiert ist ($F_k$ sind die Fibonacci-Zahlen).
     Der Autor stellt fest, dass dies impliziert, dass $\#G(p, q) > c \log p$ für eine Konstante $c$ gilt.

Bedeutung und Behauptungen
Die Arbeit behauptet, eine „vollständige Beschreibung" der Lückensets für die Klasse der binären Inklusions-Exklusions-Polynome zu liefern und verallgemeinert dabei vorherige Ergebnisse, die auf spezifische Fälle (wie $q \equiv \pm 1 \pmod p$) oder spezifische Lücken (größte oder zweitgrößte) beschränkt waren.

Die primäre Bedeutung liegt in der Reduktion des Polynom-Lückenproblems auf die Analyse linearer Permutationen von Restklassensystemen. Der Autor führt eine Darstellung des Restklassensystems basierend auf dem Euklidischen Algorithmus ein, die die Bedingungen für dominante Paare „ziemlich transparent" macht. Die Arbeit unterstellt, dass diese Darstellung von eigenständigem Interesse ist und zukünftige Anwendungen in anderen Bereichen haben könnte, ohne diese jedoch zu spezifizieren.

Die Ergebnisse vereinheitlichen das Verständnis von Lücken in binären Kreisteilungspolynomen und binären numerischen Halbgruppen und zeigen, dass die Menge der Abstände zwischen aufeinanderfolgenden Elementen in der Halbgruppe identisch mit der Menge der Differenzen in dominanten Paaren der zugehörigen linearen Permutation ist. Die Arbeit quantifiziert zudem die Komplexität dieser Lückensets und zeigt, dass die Anzahl der verschiedenen Lücken im Worst-Case (Fibonacci-Eingaben) logarithmisch mit dem Modul $p$ wächst und im Best-Case linear durch $p$ beschränkt ist.