論文「Splitting sums of binary polynomials」の技術的サマリー

1. 概要

本論文は、整数論における古典的な問題（2 のべき乗の和に関する問題）を、多項式環 $\mathbb{F}_2[x]$（係数が 0, 1 の二元多項式）の文脈に置き換えて研究したものである。著者 Luis H. Gallardo は、集合内の任意の 2 元の和がすべて「分裂する（split）」、すなわち $x^k(x+1)^\ell$ の形（$k, \ell$ は非負整数、かつ両方とも 0 ではない）になるような多項式の集合の最大サイズを決定した。

主な結論として、$m=5$ が最小の整数であり、5 つの異なる二元多項式の集合において、すべての異なる 2 元の和が $x^k(x+1)^\ell$ の形になることは不可能であることを証明した。

2. 問題設定と背景

整数論からの動機

整数論において、異なる整数 $a, b$ の和が 2 のべき乗になる例（例：$3+5=8$）は存在する。さらに、3 つの整数 $a, b, c$ において、すべてのペアの和が 2 のべき乗になる例も存在する（例：$-1, 3, 5$）。しかし、M. S. Smith は、4 つの整数 $\{a, b, c, d\}$ において、すべてのペアの和（6 通り）が 2 のべき乗になるような集合は存在しないことを示した。

多項式へのアナロジー

本論文では、以下の対応関係に基づいて問題を定式化している：

• 整数 $n$ $\longleftrightarrow$ 多項式 $A(x) \in \mathbb{F}_2[x]$
• 整数の加法 $\longleftrightarrow$ $\mathbb{F}_2$ 上の多項式加法（$1+1=0$）
• 整数の 2 のべき乗 $2^k$ $\longleftrightarrow$ 多項式 $x^k(x+1)^\ell$

ここで、$x$ と $x+1$ は $\mathbb{F}_2[x]$ における次数最小の既約多項式であり、整数における最小の素数 2 に相当する。
問題: $m$ 個の異なる二元多項式の集合 $S_m$ において、任意の異なる 2 要素の和が $x^k(x+1)^\ell$ の形になるような $m$ の最大値は何か？

3. 手法とツール

証明には、$\mathbb{F}_2[x]$ における多項式の性質と、いくつかの補題が用いられている。

主要な定義と性質

• 約数和関数 $\sigma(A)$: $A \in \mathbb{F}_2[x]$ のすべての約数（1 と $A$ 自身を含む）の和。
• メルセンヌ多項式: $A = x^a(x+1)^b + 1$ の形を持つ多項式。
• 分裂多項式: $x^k(x+1)^\ell$ の形を持つ多項式。

使用された補題

1. Lemma 5: 既約多項式 $P$ に対して、$1 + P + \dots + P^{2n} = Q^m$ となる場合、$m$ は 0 または 1 である。
2. Lemma 6: 方程式 $(x+1)^A + x^B = x^C$ を満たす非負整数 $A, B, C$ の解は、$A=2^s, B=0, C=2^s$ または $A=2^s, B=2^s, C=0$ のみである。
3. Lemma 9 (中心的な補題): 3 つの分裂多項式の和 $x^A(x+1)^B + x^C(x+1)^D = x^E(x+1)^F$ が成り立つ場合、指数間に特定の制約（最小の指数が $D$ であり、$B-D = E-A = 2^s$ となるなど）が存在することを示す。これは、分裂多項式の集合が Sidon 集合（すべてのペアの和が異なる）ではないことを示唆している。

4. 主要な結果

定理 1 (3 要素の場合)

$a, b, c \in \mathbb{F}_2[x]$ の任意のペアの和が分裂多項式である場合、それらの構造は厳密に制限される。
具体的には、$x$ と $x+1$ を入れ替えることで、以下のような関係が成り立つことが示された：
$$\begin{aligned} b &= a + x^{a_1}(x+1)^{b_2+2s} \\ c &= a + x^{a_1+2s}(x+1)^{b_2} \end{aligned}$$
ここで $s$ は非負整数。この結果は、3 要素の集合が存在可能であることを示している。

定理 2 (4 要素以上の場合)

(i) 4 要素の場合:
$a, b, c, d \in \mathbb{F}_2[x]$ のすべてのペアの和が分裂多項式である場合、その構造は以下の 2 つのパターンのいずれかに限定される（$x$ と $x+1$ の入れ替えを除く）：

1. $b = a + (x+1)^{2t}T(1,3)$, $c = a + (x+1)^{2t-1}T(1,3)$, $d = a + T(1,3)$
2. $b = a + (x^{2t_1}+1)T(1,3)$, $c = a + (x^{2t_1}+x^{2t_1-1})T(1,3)$, $d = a + x^{2t_1}T(1,3)$
   ここで $T(1,3) = x^{a_1}(x+1)^{b_3}$ である。
   この結果は、4 要素の集合が存在可能であることを示している。

(ii) 5 要素以上の場合:
$m > 4$ に対して、すべての異なるペアの和が分裂多項式となるような $m$ 個の異なる二元多項式の集合は存在しない。
特に、$m=5$ の場合、次数が 9 以下の多項式についてコンピュータ検証を行い、解がないことを確認した。さらに、理論的な分析（16 のケースの検討）により、一般の $m=5$ に対しても解が存在しないことを証明している。

5. 証明の構成

1. ケース分析: 4 要素の集合 $\{a, b, c, d\}$ において、各ペアの和が $x^{a_i}(x+1)^{b_i}$ となる指数の大小関係に基づき、16 のケースに分類する。
2. 矛盾の導出:
   • 定理 1 の結果を適用し、指数間の関係式（$2^s$ の差など）を導出する。
   • これらの関係式を組み合わせることで、$s = s-1$ のような矛盾が生じるケースを特定する。
   • 16 のケースのうち、2 つのケースのみが矛盾なく成立し、それ以外はすべて矛盾することが示された。
3. 5 要素への拡張: 4 要素の構造が非常に制限されているため、5 番目の要素を追加しようとすると、既存の 4 要素の構造と矛盾が生じることを示す。計算機（GP-PARI）を用いて、$m=5$ の場合の全 64 のケースが、矛盾する 14 のケースのいずれかに含まれることを確認した。

6. 意義と結論

• 理論的貢献: 整数論における「2 のべき乗の和」の問題を、$\mathbb{F}_2[x]$ における「$x^k(x+1)^\ell$ の和」の問題として定式化し、完全な解決（$m=4$ は可能、$m=5$ は不可能）を与えた。
• 手法の革新: 純粋な計算機探索ではなく、多項式の代数的性質（特に指数に関する指数方程式の解の構造）を深く分析することで、有限な計算で一般論を証明した点に特徴がある。
• 限界の明確化: この問題が純粋な計算機的手法では解決が困難（あるいは不可能）であることを示唆しており、代数的な洞察の重要性を浮き彫りにした。

本論文は、有限体上の多項式環における加法的組合せ論の問題に対して、エレガントかつ厳密な解答を提供したものである。