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$ と表記）にユークリッド互除法を適用して導かれる剰余系の表現を導入する。ユークリッド互除法は、$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$ を $p$ に関する $q$ の乗法逆元と設定することで、著者は優位対を数値半群 $\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{where } 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$ はフィボナッチ数）によって定義される。
     著者は、これにより $\#G(p, q) > c \log p$ （$c$ はある定数）が導かれると指摘している。

意義と主張
本論文は、二項包含・除外多項式のクラスに対するギャップセットの「完全な記述」を提供すると主張しており、特定のケース（例えば $q \equiv \pm 1 \pmod p$）または特定のギャップ（最大または第 2 最大）に限定されていた先行結果を一般化している。

主な意義は、多項式のギャップ問題を剰余系の線形置換の分析に帰着させる点にある。著者は、ユークリッド互除法に基づく剰余系の表現を導入し、これにより優位対の条件を「非常に明瞭」にする。本論文は、この表現は独立した興味を有し、他の分野での将来の応用可能性があると示唆しているが、具体的な応用例については特定していない。

結果は、二項サイクロトミック多項式および二項数値半群におけるギャップの理解を統合し、半群内の連続する要素間の距離の集合が、関連する線形置換の優位対の差の集合と同一であることを示している。また、この研究はこれらのギャップセットの複雑さを定量化し、最悪の場合（フィボナッチ入力）には法 $p$ に対して対数的に増加し、最良の場合には $p$ に対して線形に有界であることを示している。