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

技术摘要：二元数值半群与二元容斥多项式的间隙

问题陈述
本文探讨了二元容斥多项式 $Q_{\{p,q\}}(x)$ 的“间隙集”的结构性质，以及关联的二元数值半群 $\langle p, q \rangle$ 中连续元素之间的距离。该多项式定义为：
$$Q_{\{p,q\}}(x) := \frac{(1-x^{pq})(1-x)}{(1-x^p)(1-x^q)}$$
其中 $p$ 和 $q$ 是互质整数，且 $q \ge p \ge 3$。当 $p$ 和 $q$ 为素数时，$Q_{\{p,q\}}$ 退化为分圆多项式 $\Phi_{pq}$。

多项式 $f$ 的间隙集 $G(f)$ 定义为连续非零系数指数之间的差值集合。先前的研究（例如 Hong 等人、Zhang、Cafure 和 Cesaratto）已在特定条件下（例如 $q \equiv \pm 1 \pmod p$）确立了 $\Phi_{pq}$ 的最大间隙的特定结果，但针对一般二元情况下的整个间隙集的完整描述仍是一个未解决的问题。本文还旨在刻画数值半群 $\langle p, q \rangle = \{ iq + jp \mid i, j \ge 0 \}$ 中连续元素之间所有可能距离的集合。

方法论
本文的核心技术贡献是对剩余系线性置换特定性质的分析。设 $p$ 为模数，$u$ 为与 $p$ 互质的整数。该置换由 $n \mapsto \langle un \rangle_p$ 给出，其中 $\langle x \rangle_p$ 表示 $x$ 模 $p$ 的最小非负剩余。

作者将满足 $a < b$ 的“主导对” $(a, b)$ 定义为满足以下两个不等式之一的对：

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$

为了分析这些对，本文引入了一种基于对 $p$ 和 $u$ 的乘法逆元（记为 $r_1$）应用欧几里得算法所得到的模 $p$ 剩余系表示。欧几里得算法通过 $r_{i-1} = Z_i r_i + r_{i+1}$ 生成序列 $(r_i)$ 和 $(Z_i)$。

作者构造了任意整数 $n \in [0, p)$ 的特定表示形式 $n = R(z) = \sum z_i (-1)^{i-1} r_i$，其中 $z$ 是受欧几里得算法参数约束的系数元组。该表示允许用系数 $z_i$ 显式地计算 $\langle un \rangle_p$。

主要贡献与结果

1. 主导对的刻画：
   本文证明了主导对的差值集合 $\{b-a\}$ 恰好是以下集合：
   $$D_\Delta(p, u) = \{ r_{i-1} - z r_i \mid 0 \le z \le Z_i - 1, \ 1 \le i \le t \}$$
   其中 $t$ 是欧几里得算法的步骤数。该结果将可能的差值基于欧几里得序列的索引 $i$ 划分为集合 $D_i$。

2. 数值半群的间隙集：
   通过将 $u$ 设为 $q$ 模 $p$ 的乘法逆元，作者将主导对与数值半群 $\langle p, q \rangle$ 联系起来。

   • 设 $S(p, q)$ 为 $[0, (p-1)(q-1)]$ 中可表示整数的集合，$N(p, q)$ 为不可表示整数的集合。
   • 连续可表示整数之间的距离集合 $S_\Delta(p, q) = \{ \ell_{j+1} - \ell_j \}$，以及连续不可表示整数之间的距离集合 $N_\Delta(p, q) = \{ n_{j+1} - n_j \}$，得到了完整描述。
   • 定理 1： 除非 $q = p+1$，否则 $S_\Delta(p, q) = N_\Delta(p, q)$；若 $q = p+1$，则 $S_\Delta(p, q) = N_\Delta(p, q) \cup \{2\}$。这两个集合均等于 $D_\Delta(p, x_1)$，其中 $x_1 \equiv q^{-1} \pmod p$。

3. 二元容斥多项式的间隙集：
   本文确立了多项式 $Q_{\{p,q\}}$ 的间隙对应于连续可表示或不可表示整数块的长度。具体而言，间隙集 $G(p, q)$ 由下式给出：
   $$G(p, q) = \{ \ell_{j+1} - \ell_j - 1 \mid \ell_{j+1} > \ell_j + 1 \}$$
   定理 2： 间隙集是集合 $G_i$ 的并集：
   $$G(p, q) = \bigcup_{i=1}^t G_i, \quad \text{其中 } G_i = \{ r_{i-1} - z r_i - 1 \mid 0 \le z \le Z_i - 1 \}$$
   （对于最后一个集合 $G_t$ 有轻微修正）。这提供了所有可能间隙的完整构造性描述。

4. 间隙数量的界限：
   定理 3： 本文提供了间隙集基数 $\#G(p, q)$ 的精确界限。

   • 上界：$\#G(p, q) \le p - 1$。
   • 下界：$\#G(p, q) \ge k$，其中 $k$ 由 $F_k < p \le F_{k+1}$ 定义（$F_k$ 为斐波那契数）。
     作者指出，这意味着对于某个常数 $c$，有 $\#G(p, q) > c \log p$。

意义与主张
本文声称提供了二元容斥多项式类间隙集的“完整描述”，推广了先前仅限于特定情况（如 $q \equiv \pm 1 \pmod p$）或特定间隙（最大或次大）的结果。

其主要意义在于将多项式间隙问题简化为对剩余系线性置换的分析。作者引入了一种基于欧几里得算法的剩余系表示，使得主导对的条件变得“相当清晰”。本文提出，这种表示具有独立的兴趣，并可能在其他领域有未来应用，尽管未具体说明。

这些结果统一了对二元分圆多项式和二元数值半群中间隙的理解，表明半群中连续元素之间的距离集合与关联线性置换中主导对的差值集合是相同的。该工作还量化了这些间隙集的复杂性，表明在最坏情况（斐波那契输入）下，不同间隙的数量随模数 $p$ 对数增长，而在最佳情况下受 $p$ 线性有界。