Algorithmic aspects of Newman polynomials and their divisors

M. Idris および J.-M. Sac-Epée による論文「Newman 多項式とその約数のアルゴリズム的側面」の詳細な技術的要約を以下に示す。

1. 問題提起

本論文は、係数が $\{0, 1\}$ に属し定数項が 1 である多項式であるNewman 多項式に関する代数的整数論の根本的な問いに取り組んでいる。具体的には、整数係数多項式 $p(x)$ が Newman 多項式を割り切るための条件を調査する。

核心的な問いは、以下の 2 つの条件を満たすすべての整数係数多項式 $p(x)$ が Newman 多項式を割り切るような普遍的な定数 $\sigma$ が存在するかどうかである。

1. 非負の実数根を持たないこと、および
2. Mahler 測度 $M(p) < \sigma$ であること。

先行研究では、$M(p) < 2$ ならば $p(x)$ は係数が $\{-1, 0, 1\}$ に属する多項式を割り切ることが示されていた。しかし、係数を $\{0, 1\}$ に制限することははるかに厳格な条件である。当初、黄金比（$g \approx 1.618$）が自然な上限と考えられていたが、Mahler 測度が約 1.556 である反例が発見された。本論文は、この上限を精緻化し、小さな Mahler 測度を持つ多項式の割り切り性質を決定することを目的としている。

2. 手法

著者らは、Newman 倍数の発見と、そのような倍数の非存在の証明という 2 つの異なる課題を解決するために、混合整数線形計画法（MILP）とアルゴリズム的証明を組み合わせて用いている。

A. Newman 倍数の探索（MILP アプローチ）

与えられた多項式 $p(x)$ が Newman 多項式を割り切るかどうかを判定するため、著者らはこの問題を線形不等式の系として定式化する。

• 定式化: 次数 $2d$ のモニック多項式 $p(x)$ が与えられたとき、積 $N(x) = p(x)q(x)$ の係数が $\{0, 1\}$ に属するような多項式 $q(x)$ を探す。
• 制約条件: $p$ と $q$ の定数項が 1 であるため、$N$ の定数項も 1 となる。$N(x)$ の係数は $q(x)$ の未知の係数の線形結合である。$N(x)$ のすべての係数が 0 または 1 でなければならないという条件は、整数未知数を持つ線形不等式の系を生成する。
• 実装: 著者らはJulia言語で、JuMPモデリング言語とGurobi最適化ソルバーを用いてこれを実装した。結果として得られる Newman 多項式の次数が 1000 を超えない範囲で解を探索した。

B. 非割り切りの証明（到達可能性アプローチ）

ある多項式が Newman 多項式を一切割り切らないことを証明するために、著者らは Hare および Mossinghoff によって導入されたアルゴリズム的手法を利用する。

• 原理: 候補多項式の根を $\beta$ とする。次数 $\le d$ のすべての Newman 多項式 $F$ に対する値 $F(\beta)$ の集合を、特定の円盤 $I'(\beta)$ に制限したものを $N'(\beta, d)$ と定義する。
• アルゴリズム: この集合は再帰的に構築される。集合が安定化し（すなわち $N'(\beta, d+1) = N'(\beta, d)$）、かつこの集合内で 0 に到達しない場合、$\beta$ がいかなる Newman 多項式の根でもないことが証明される。したがって、$\beta$ の最小多項式は Newman 多項式を割り切らない。
• 実装: 相互検証を確保するため、Julia（Polynomials.jl および Nemo.jl を使用）とGP/PARIで独立して実装された。

C. 重根を持つ倍数の構成

著者らは MILP アプローチを適応させ、$l(x)^2$ で割り切れる Newman 多項式（ここで $l(x)$ は $x \to -x$ とした Lehmer 多項式）を探索した。

• 手法: 不等式の代わりに、Euclid 除法の剰余 $N(x) = g(x)H(x) + R(x)$ から導かれる線形方程式の系を解いた。$g(x) | N(x)$ という条件は $R(x) = 0$ を要求する。
• 最適化: 消滅する剰余条件を満たすために、二値係数 $a_i \in \{0, 1\}$ について解いた。

3. 主要な結果

A. 小さな Mahler 測度を持つ多項式の割り切り

著者らは、Mahler 測度が $< 1.3$ で次数が $\le 180$ である既知の 8,438 個の多項式（Known180 と呼ばれる）のデータセットを分析した。

• 発見: 正の実数根を持つ多項式を除き、このリストの3 つを除くすべての多項式が、次数 $\le 1000$ の Newman 多項式を割り切ることが判明した。
• 定理: 非負の実数根を持たず、円分因子を持たない、次数 $\le 44$ で $M(p) < 1.3$ であるすべての整数係数多項式は、Newman 多項式を割り切る。これは Known180 が次数 44 まで完全であるという事実に基づいている。
• 未解決のケース: 3 つの特定の多項式は未解決のまま（次数 1000 までの Newman 倍数が見つからなかった）であり、これらがより高次の Newman 多項式を割り切るかどうかは未だ不明である。

B. 普遍的定数 $\sigma$ の改善

証明手法を用いて、著者らは Newman 多項式を一切割り切らない新しい多項式を特定し、仮定される定数 $\sigma$ の上限を低下させた。

• 新しい上限: 彼らは次数 10 の多項式を発見した。
  $$x^{10} - x^8 - x^5 + x + 1$$
  その Mahler 測度は約 1.419404632 である。
• 意義: これは、以前の既知の最良の上限 $\approx 1.4366$（Drungilas ら、2023 年）およびそれ以前の上限 $\approx 1.556$（Hare & Mossinghoff）を改善するものである。もし定数 $\sigma$ が存在するならば、それは $\le 1.419404632$ でなければならない。
• データセット: 本論文は、Newman 多項式を一切割り切らない Mahler 測度 $\le 1.556$ の 33 個の証明済み例（次数 8–12）の表を提供している。

C. 重根を持つ Newman 多項式

著者らは $l(x)^2$ で割り切れる Newman 多項式（ここで $l(x)$ は変換された Lehmer 多項式）を調査した。

• 結果: 彼らは明示的に、次数最大150までの $l(x)^2$ で割り切れる Newman 多項式を構成した。
• 否定的結果: 彼らは、次数 $\le 160$ の Newman 多項式が $l(x)^3$ で割り切れないことを証明した。これは Mossinghoff の以前の検証（次数 120 まで）を拡張したものである。
• データ: 本論文は、16 進数形式で符号化されたこれらの多項式の包括的な表を提供している。

4. 意義と貢献

1. 上限の精緻化: 本論文は、Newman 倍数の存在に関する理論的限界を大幅に引き締め、既知の「禁止された」Mahler 測度の閾値を $\approx 1.436$ から $\approx 1.419$ まで低下させた。
2. アルゴリズム的枠組み: 制限係数多項式に関連する数論的問題を解決する際の**混合整数線形計画法（MILP）**の有効性を示した。この手法は、不等式制約（倍数の発見）と等式制約（剰余の消去）の両方を処理するのに十分な柔軟性を有していることが示された。
3. 包括的なデータ: 著者らは、さらなる研究のために利用可能な完全なデータセット（Known180 の分析、証明済み非割り切り数、構成された倍数）を提供し、GP/PARI での検証スクリプトも含んでいる。
4. 未解決問題の解決: この研究は、小さな Mahler 測度を持つ低次数多項式（$\le 44$）において、Newman 多項式を割り切れない障害は、正の実数根の存在がほぼ独占的に原因であることを確認した。ただし、より高次の探索を待っている 3 つの軽微な例外を除く。

5. 結論

本論文は、普遍的な定数 $\sigma$ の存在は未解決の問題であるが、反例の探索空間が劇的に狭められたと結論づけている。著者らは、MILP ベースの枠組みが Borwein 多項式、Littlewood 多項式、および Newman 多項式に関する将来の調査のための強力なツールであり、限界のさらなる改善や、制限係数を持つ多項式の新しい構造的性質の発見を可能にする可能性があると示唆している。