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

Technical Summary: Gaps of Binary Numerical Semigroups and of Binary Inclusion-Exclusion Polynomials

Problem Statement
This work addresses the structural properties of the "gapsets" of binary inclusion-exclusion polynomials, denoted $Q_{\{p,q\}}(x)$, and the distances between consecutive elements in the associated binary numerical semigroup $\langle p, q \rangle$. The polynomial is defined as:
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
where $p$ and $q$ are coprime integers with $q \ge p \ge 3$. When $p$ and $q$ are prime, $Q_{\{p,q\}}$ reduces to the cyclotomic polynomial $\Phi_{pq}$.

The gapset $G(f)$ of a polynomial $f$ is defined as the set of differences between the exponents of consecutive non-zero coefficients. Previous research (e.g., Hong et al., Zhang, Cafure and Cesaratto) had established specific results for the largest gaps of $\Phi_{pq}$ under certain conditions (e.g., $q \equiv \pm 1 \pmod p$), but a complete description of the entire gapset for the general binary case remained an open problem. The paper also seeks to characterize the set of all possible distances between consecutive elements in the semigroup $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$.

Methodology
The core technical contribution of the paper is the analysis of a specific property of linear permutations of residue systems. Let $p$ be a modulus and $u$ an integer coprime to $p$. The permutation is given by $n \mapsto \langle un \rangle_p$, where $\langle x \rangle_p$ denotes the least nonnegative residue of $x$ modulo $p$.

The author defines a "dominant pair" $(a, b)$ with $a < b$ as a pair satisfying one of two inequalities:

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$

To analyze these pairs, the paper introduces a representation of the residue system modulo $p$ derived from the Euclidean algorithm applied to $p$ and the multiplicative inverse of $u$ (denoted $r_1$). The Euclidean algorithm generates sequences $(r_i)$ and $(Z_i)$ via $r_{i-1} = Z_i r_i + r_{i+1}$.

The author constructs a specific representation for any integer $n \in [0, p)$ in the form $n = R(z) = \sum z_i (-1)^{i-1} r_i$, where $z$ is a tuple of coefficients constrained by the Euclidean algorithm parameters. This representation allows for the explicit evaluation of $\langle un \rangle_p$ in terms of the coefficients $z_i$.

Key Contributions and Results

1. Characterization of Dominant Pairs:
   The paper proves that the set of differences $\{b-a\}$ for dominant pairs is exactly the set:
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   where $t$ is the number of steps in the Euclidean algorithm. This result partitions the possible differences into sets $D_i$ based on the index $i$ of the Euclidean sequence.

2. Gapsets of Numerical Semigroups:
   By setting $u$ to be the multiplicative inverse of $q$ modulo $p$, the author connects the dominant pairs to the numerical semigroup $\langle p, q \rangle$.

   • Let $S(p, q)$ be the set of representable integers in $[0, (p-1)(q-1)]$ and $N(p, q)$ be the set of non-representable integers.
   • The set of distances between consecutive representable integers, $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$, and the set of distances between consecutive non-representable integers, $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$, are completely described.
   • Theorem 1: $S_\Delta(p, q) = N_\Delta(p, q)$ unless $q = p+1$, in which case $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$. Both sets are equal to $D_\Delta(p, x_1)$, where $x_1 \equiv q^{-1} \pmod p$.

3. Gapsets of Binary Inclusion-Exclusion Polynomials:
   The paper establishes that the gaps of the polynomial $Q_{\{p,q\}}$ correspond to the lengths of blocks of consecutive representable or non-representable integers. Specifically, the gapset $G(p, q)$ is given by:
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   Theorem 2: The gapset is the union of sets $G_i$:
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{where } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   (With a slight modification for the final set $G_t$). This provides a complete, constructive description of all possible gaps.

4. Bounds on the Number of Gaps:
   Theorem 3: The paper provides sharp bounds on the cardinality of the gapset, $\#G(p, q)$.

   • Upper bound: $\#G(p, q) \le p - 1$.
   • Lower bound: $\#G(p, q) \ge k$, where $k$ is defined by $F_k < p \le F_{k+1}$ ($F_k$ being the Fibonacci numbers).
     The author notes that this implies $\#G(p, q) > c \log p$ for some constant $c$.

Significance and Claims
The paper claims to provide a "complete description" of the gapsets for the class of binary inclusion-exclusion polynomials, generalizing previous results that were limited to specific cases (such as $q \equiv \pm 1 \pmod p$) or specific gaps (largest or second largest).

The primary significance lies in the reduction of the polynomial gap problem to the analysis of linear permutations of residue systems. The author introduces a representation of the residue system based on the Euclidean algorithm that renders the conditions for dominant pairs "quite transparent." The paper posits that this representation is of independent interest and may have future applications in other areas, though it does not specify them.

The results unify the understanding of gaps in binary cyclotomic polynomials and binary numerical semigroups, showing that the set of distances between consecutive elements in the semigroup is identical to the set of differences in dominant pairs of the associated linear permutation. The work also quantifies the complexity of these gapsets, showing that the number of distinct gaps grows logarithmically with the modulus $p$ in the worst case (Fibonacci inputs) and is bounded linearly by $p$ in the best case.