🔢 mathematics

Algorithmic aspects of Newman polynomials and their divisors

本文通过分析已知的小马勒测度实例，研究哪些整系数多项式能整除纽曼多项式，识别出某些不能整除任何纽曼多项式的特定多项式（从而改进了潜在通用常数 $\sigma$ 的上界），并确定了在特定次数限制下勒默多项式能整除纽曼多项式的最高幂次。

原作者： Musbahu Idris, Jean-Marc Sac-Épée

发布于 2026-04-29

📖 1 分钟阅读🧠 深度阅读

原作者： Musbahu Idris, Jean-Marc Sac-Épée

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位大师级建筑师，正在使用一套非常特定的乐高积木。这些积木很特殊：它们只有两种颜色，白色（代表数字 1）和黑色（代表数字 0）。你只能用这两种颜色的积木搭建塔楼（多项式），且每座塔楼必须以白色积木开始并以白色积木结束。在数学世界中，这些被称为纽曼多项式。

本文的作者提出了一个根本性问题：是否每一种其他类型的数学“塔楼”都能被构建在这些特殊的黑白塔楼内部？

更具体地说，他们正在研究具有某种特定属性——即低马勒测度的“整数塔楼”（系数为整数的多项式）。可以将马勒测度想象为一种“大小”或“复杂度”评分。评分越低，塔楼就越“小”或越“简单”。

以下是他们旅程与发现的详细分解：

1. 核心问题

数学家们早已知道，如果你允许使用红色、白色和黑色的积木（即数字 -1、0 和 1），那么几乎任何微小、简单的整数塔楼都能在一座由这三种颜色构成的更大塔楼中找到。

但如果严格禁止使用红色积木呢？如果你只能使用白色和黑色积木，这条规则依然成立吗？每一个微小、简单的整数塔楼是否仍然能嵌入到一座黑白塔楼中？

2. 伟大的搜寻（"Known180"列表）

作者决定在一份包含 8,438 个已知“微小”塔楼（马勒测度小于 1.3）的巨大列表上测试这一假设。他们编写了一个计算机程序，充当探照灯。

方法：对于列表中的每一个微小塔楼，计算机尝试寻找一个“伙伴”塔楼（由整数构成），使得当两者相乘时，结果是一座完美的黑白纽曼塔楼。
约束：计算机被设定为，如果生成的塔楼变得过高（次数超过 1,000），则停止搜索。
结果：
- “正根”问题：首先，他们排除了任何拥有“正实根”的塔楼。想象一座在阳光一侧有弱点的塔楼；从数学上讲，这些塔楼永远无法嵌入纽曼塔楼中。
- 成功：对于几乎所有剩余的塔楼，计算机都找到了匹配项！这证明了，如果一座塔楼足够小（次数为 44 或更低）且不拥有那些“弱点”，它就可以被构建在纽曼塔楼内部。
- 谜团：列表中有三个顽固的塔楼，计算机在 1,000 次数的限制内未能找到匹配项。作者并未断言这些是不可能的，只是表示尚未为它们找到伙伴。

3. “黄金比例”之墙

长期以来有一种信念认为，“黄金比例”（约 1.618）是极限。其想法是：“如果你的塔楼小于黄金比例，它就能嵌入。”

作者（以及他们引用的其他人）证明这是错误的。他们发现了特定的塔楼，其大小小于黄金比例，但无法嵌入任何纽曼塔楼中，无论那座纽曼塔楼有多高。

新纪录：他们发现了一座 10 次塔楼，其大小约为1.419。这是迄今为止发现的最小的“不可能”塔楼。
推论：这将“安全极限”向下推移。如果存在一个魔法数字（让我们称之为 $\sigma$ ）能保证塔楼可以嵌入，那么该数字必须低于 1.419。

4. “双重麻烦”实验

在最后一节中，作者研究了一座著名的数学塔楼，称为莱默多项式。他们将其“翻转”（将 $x$ 替换为 $-x$ ），得到了一座新塔楼，我们称之为 $l(x)$ 。

他们问道：我们能构建一座能被 $l(x)$ 的平方（ $l(x)^2$ ）整除的纽曼塔楼吗？

结果：可以！他们利用计算机搜索构建了高达 150 次的纽曼塔楼，其中包含 $l(x)^2$ 作为因子。他们甚至为这些巨大的塔楼提供了蓝图（以十六进制代码形式）。

接着他们提出了下一个层次的问题：那么 $l(x)$ 的立方（ $l(x)^3$ ）呢？

结果：他们检查了高达 160 次的情况，但一无所获。没有任何该尺寸的纽曼塔楼能被 $l(x)^3$ 整除。这表明，虽然你可以嵌入这座著名塔楼的平方，但其立方可能根本无法嵌入（或者至少极难找到）。

总结

将这篇论文想象成一个关于将形状放入盒子的侦探故事：

盒子：纽曼多项式（仅包含 0 和 1）。
物体：具有微小“大小”（马勒测度）的整数多项式。
发现：大多数微小物体都能完美地放入盒子中。
例外：有少数特定物体，其大小看起来足以嵌入，但实际上却不行。作者发现了迄今为止最小的一个，证明了嵌入的“极限”比我们想象的更低。
额外收获：他们成功构建了包含特定复杂形状（莱默多项式的平方和立方版本）的巨型盒子，展示了这些 0 和 1 塔楼的灵活性。

论文得出结论：虽然我们已经解决了许多这类嵌入谜题，但仍有一些未解之谜，关于“什么可以嵌入”的终极“极限”的搜寻仍在继续。

以下是 M. Idris 和 J.-M. Sac-Epée 的论文《Newman 多项式及其因子的算法方面》的详细技术总结。

1. 问题陈述

本文探讨了代数数论中关于Newman 多项式（系数在 $\{0, 1\}$ 中且常数项为 1 的多项式）的一个基本问题。具体而言，它研究了整数系数多项式 $p(x)$ 在何种条件下能整除一个 Newman 多项式。

核心问题是：是否存在一个通用常数 $\sigma$ ，使得任何满足以下条件的整数多项式 $p(x)$ 必然整除一个 Newman 多项式：

无非负实根，且
Mahler 测度 $M(p) < \sigma$ 。

先前的工作表明，如果 $M(p) < 2$ ，则 $p(x)$ 能整除一个系数在 $\{-1, 0, 1\}$ 中的多项式。然而，将系数限制在 $\{0, 1\}$ 是一个更为严格的条件。虽然黄金比例（ $g \approx 1.618$ ）最初被认为是一个自然界限，但人们发现了 Mahler 测度约为 1.556 的反例。本文旨在细化这一界限，并确定具有较小 Mahler 测度的多项式的整除性质。

2. 方法论

作者结合使用混合整数线性规划（MILP）和算法认证来解决两个不同的问题：寻找 Newman 倍数以及证明此类倍数的不存在性。

A. 寻找 Newman 倍数（MILP 方法）

为了确定给定的多项式 $p(x)$ 是否整除一个 Newman 多项式，作者将问题表述为线性不等式组。

公式化：给定一个 $2d$ 次的首一多项式 $p(x)$ ，他们寻找一个多项式 $q(x)$ ，使得乘积 $N(x) = p(x)q(x)$ 的系数在 $\{0, 1\}$ 中。
约束：由于 $p$ 和 $q$ 的常数项均为 1，因此 $N$ 的常数项为 1。 $N(x)$ 的系数是 $q(x)$ 未知系数的线性组合。 $N(x)$ 的所有系数必须为 0 或 1 的条件，构成了一个带有整数未知数的线性不等式组。
实现：作者使用 Julia 语言，结合 JuMP 建模语言和 Gurobi 优化器实现了这一过程。他们搜索了结果 Newman 多项式次数不超过 1000 的解。

B. 不可整除性的认证（可达性方法）

为了证明一个多项式不整除任何 Newman 多项式，作者利用了 Hare 和 Mossinghoff 引入的一种算法方法。

原理：设 $\beta$ 为候选多项式的根。他们定义了一个集合 $N'(\beta, d)$ ，表示所有次数 $\le d$ 的 Newman 多项式 $F$ 在特定圆盘 $I'(\beta)$ 限制下的值 $F(\beta)$ 。
算法：该集合是递归构建的。如果该集合稳定（即 $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 多项式。

方法：他们求解了一个由欧几里得除法余数 $N(x) = g(x)H(x) + R(x)$ 导出的线性方程组，而不是不等式。条件 $g(x) | N(x)$ 要求 $R(x) = 0$ 。
优化：他们求解二进制系数 $a_i \in \{0, 1\}$ 以满足余数消失的条件。

3. 主要结果

A. 小 Mahler 测度多项式的整除性

作者分析了一个包含 8,438 个已知多项式的数据集，这些多项式的 Mahler 测度 $< 1.3$ 且次数 $\le 180$ （称为 Known180）。

发现：排除具有正实根的多项式后，该列表中除三个多项式外的所有多项式都被发现能整除一个次数 $\le 1000$ 的 Newman 多项式。
定理：每个次数 $\le 44$ 、 $M(p) < 1.3$ 、无非负实根且无分圆因子的整数系数多项式，都能整除一个 Newman 多项式。这是基于 Known180 在次数 44 以内是完备的这一事实。
未决案例：三个特定的多项式仍未解决（在次数 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$ 。
数据集：本文提供了一个包含 33 个认证示例（次数 8–12）的表格，这些示例的 Mahler 测度 $\le 1.556$ 且不整除任何 Newman 多项式。

C. 具有重根的 Newman 多项式

作者研究了能被 $l(x)^2$ 整除的 Newman 多项式（其中 $l(x)$ 是变换后的 Lehmer 多项式）。

结果：他们显式构造了能被 $l(x)^2$ 整除的 Newman 多项式，次数高达 150。
否定结果：他们证明了没有次数 $\le 160$ 的 Newman 多项式能被 $l(x)^3$ 整除。这扩展了 Mossinghoff 之前的验证（当时止步于次数 120）。
数据：本文提供了一个综合表格，以十六进制格式编码了这些多项式。

4. 意义与贡献

界限的细化：本文显著收紧了关于 Newman 倍数存在的理论界限，将已知的“禁止”Mahler 测度阈值从 $\approx 1.436$ 推低至 $\approx 1.419$ 。
算法框架：它展示了**混合整数线性规划（MILP）**在解决涉及受限系数多项式的数论问题中的有效性。该方法被证明具有足够的灵活性，既能处理不等式约束（寻找倍数），也能处理等式约束（消除余数）。
全面的数据：作者提供了完整的数据集（Known180 分析、认证的不可整除多项式以及构造的倍数），可供进一步研究使用，包括 GP/PARI 中的验证脚本。
开放问题的解决：这项工作证实，对于具有小 Mahler 测度的低次多项式（ $\le 44$ ），阻碍其整除 Newman 多项式的因素几乎完全是正实根的存在，仅有三个次要例外有待更高次数的搜索来确认。

5. 结论

本文得出结论，虽然通用常数 $\sigma$ 的存在性仍然是一个未决问题，但反例的搜索空间已被大幅缩小。作者建议，他们基于 MILP 的框架是未来研究 Borwein、Littlewood 和 Newman 多项式的有力工具，有可能进一步改进界限并发现具有受限系数的多项式的新结构性质。