🔢 mathematics

Algorithmic aspects of Newman polynomials and their divisors

This paper investigates which integer polynomials divide Newman polynomials by analyzing known low-Mahler-measure examples, identifying specific polynomials that divide none (thereby improving the upper bound for a potential universal constant $\sigma$ ), and determining the maximum power of Lehmer's polynomial that can divide a Newman polynomial within specific degree limits.

Original authors: Musbahu Idris, Jean-Marc Sac-Épée

Published 2026-04-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Musbahu Idris, Jean-Marc Sac-Épée

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master builder working with a very specific set of Lego bricks. These bricks are special: they only come in two colors, White (representing the number 1) and Black (representing the number 0). You can only build towers (polynomials) using these two colors, and every tower must start and end with a White brick. In the mathematical world, these are called Newman polynomials.

The authors of this paper are asking a fundamental question: Can every other type of mathematical "tower" be built inside one of these special White-and-Black towers?

More specifically, they are looking at "integer towers" (polynomials with whole number coefficients) that have a certain property called a low Mahler measure. Think of the Mahler measure as a "size" or "complexity" score. The lower the score, the "smaller" or "simpler" the tower is.

Here is a breakdown of their journey and discoveries:

1. The Big Question

Mathematicians already knew that if you allow your bricks to be Red, White, and Black (numbers -1, 0, and 1), then almost any small, simple integer tower can be found inside a bigger tower made of those three colors.

But what if you are strictly forbidden from using Red bricks? What if you can only use White and Black? Does the rule still hold? Can every small, simple integer tower still fit inside a White-and-Black tower?

2. The Great Search (The "Known180" List)

The authors decided to test this on a massive list of 8,438 known "small" towers (those with a Mahler measure less than 1.3). They wrote a computer program to act as a searchlight.

The Method: For every small tower on the list, the computer tried to find a "partner" tower (made of integers) such that when you multiply them together, the result is a perfect White-and-Black Newman tower.
The Constraint: The computer was told to stop looking if the resulting tower got too tall (degree higher than 1,000).
The Results:
- The "Positive Root" Problem: First, they threw out any tower that had a "positive real root." Imagine a tower that has a weak spot on the sunny side; mathematically, these can never fit inside a Newman tower.
- The Success: For almost every remaining tower, the computer found a match! It proved that if a tower is small enough (degree 44 or less) and doesn't have those "weak spots," it can be built inside a Newman tower.
- The Mystery: There were three stubborn towers on the list where the computer couldn't find a match within the 1,000-degree limit. The authors didn't say these are impossible, just that they haven't found a partner for them yet.

3. The "Golden Ratio" Wall

There was a long-standing belief that the "Golden Ratio" (about 1.618) was the limit. The idea was: "If your tower is smaller than the Golden Ratio, it fits."

The authors (and others they cite) proved this was wrong. They found specific towers that are smaller than the Golden Ratio but cannot fit inside any Newman tower, no matter how tall the Newman tower gets.

The New Record: They found a 10th-degree tower with a size of about 1.419. This is the smallest "impossible" tower found so far.
The Implication: This pushes the "safety limit" down. If there is a magic number (let's call it $\sigma$ ) that guarantees a tower will fit, that number must be lower than 1.419.

4. The "Double Trouble" Experiment

In the final section, the authors looked at a famous mathematical tower called Lehmer's polynomial. They flipped it inside out (substituting $x$ with $-x$ ) to get a new tower, let's call it $l(x)$ .

They asked: Can we build a Newman tower that is divisible by $l(x)$ squared ( $l(x)^2$ )?

The Result: Yes! They used their computer search to build Newman towers up to degree 150 that contain $l(x)^2$ as a factor. They even provided the blueprints (in a code called hexadecimal) for these massive towers.

Then they asked the next level: What about $l(x)$ cubed ( $l(x)^3$ )?

The Result: They checked up to degree 160 and found nothing. No Newman tower of that size could be divided by $l(x)^3$ . This suggests that while you can fit the square of this famous tower, the cube might be impossible to fit at all (or at least, it's incredibly hard to find).

Summary

Think of this paper as a detective story about fitting shapes into a box:

The Box: Newman polynomials (only 0s and 1s).
The Objects: Integer polynomials with small "sizes" (Mahler measure).
The Discovery: Most small objects fit perfectly inside the box.
The Exception: There are a few specific objects that are small enough to look like they should fit, but they don't. The authors found the smallest one yet, proving the "limit" for fitting is lower than we thought.
The Bonus: They successfully built giant boxes that contain specific complex shapes (squared and cubed versions of Lehmer's polynomial), showing just how flexible these 0-and-1 towers can be.

The paper concludes that while we have solved many of these fitting puzzles, a few remain unsolved, and the search for the ultimate "limit" of what can fit continues.

1. Problem Statement

The paper addresses the fundamental question in algebraic number theory regarding Newman polynomials (polynomials with coefficients in $\{0, 1\}$ and a constant term of 1). Specifically, it investigates the conditions under which an integer-coefficient polynomial $p(x)$ divides a Newman polynomial.

The core inquiry is whether there exists a universal constant $\sigma$ such that any integer polynomial $p(x)$ with:

No non-negative real roots, and
Mahler measure $M(p) < \sigma$ ,
necessarily divides a Newman polynomial.

Previous work established that if $M(p) < 2$ , $p(x)$ divides a polynomial with coefficients in $\{-1, 0, 1\}$ . However, restricting coefficients to $\{0, 1\}$ is a much stricter condition. While the Golden Ratio ( $g \approx 1.618$ ) was initially thought to be a natural bound, counterexamples with Mahler measures around 1.556 were found. The paper aims to refine this bound and determine the divisibility properties of polynomials with small Mahler measures.

2. Methodology

The authors employ a combination of Mixed-Integer Linear Programming (MILP) and algorithmic certification to solve two distinct problems: finding Newman multiples and certifying the non-existence of such multiples.

A. Search for Newman Multiples (MILP Approach)

To determine if a given polynomial $p(x)$ divides a Newman polynomial, the authors formulate the problem as a system of linear inequalities.

Formulation: Given a monic polynomial $p(x)$ of degree $2d$ , they seek a polynomial $q(x)$ such that the product $N(x) = p(x)q(x)$ has coefficients in $\{0, 1\}$ .
Constraints: Since the constant terms of $p$ and $q$ are 1, the constant term of $N$ is 1. The coefficients of $N(x)$ are linear combinations of the unknown coefficients of $q(x)$ . The condition that all coefficients of $N(x)$ must be 0 or 1 creates a system of linear inequalities with integer unknowns.
Implementation: The authors implemented this in Julia using the JuMP modeling language and the Gurobi optimizer. They searched for solutions where the degree of the resulting Newman polynomial did not exceed 1000.

B. Certification of Non-Divisibility (Reachability Approach)

To prove that a polynomial divides no Newman polynomial, the authors utilize an algorithmic method introduced by Hare and Mossinghoff.

Principle: Let $\beta$ be a root of the candidate polynomial. They define a set $N'(\beta, d)$ representing the values $F(\beta)$ for all Newman polynomials $F$ of degree $\le d$ , restricted to a specific disk $I'(\beta)$ .
Algorithm: The set is built recursively. If the set stabilizes (i.e., $N'(\beta, d+1) = N'(\beta, d)$ ) and $0$ is never reached within this set, it is proven that $\beta$ is not a root of any Newman polynomial. Consequently, the minimal polynomial of $\beta$ divides no Newman polynomial.
Implementation: This was implemented independently in Julia (using Polynomials.jl and Nemo.jl) and GP/PARI to ensure cross-verification.

C. Construction of Multiples with Repeated Roots

The authors adapted the MILP approach to find Newman polynomials divisible by $l(x)^2$ , where $l(x)$ is Lehmer's polynomial with $x \to -x$ .

Method: Instead of inequalities, they solved a system of linear equations derived from the Euclidean division remainder $N(x) = g(x)H(x) + R(x)$ . The condition $g(x) | N(x)$ requires $R(x) = 0$ .
Optimization: They solved for binary coefficients $a_i \in \{0, 1\}$ to satisfy the vanishing remainder conditions.

3. Key Results

A. Divisibility of Small Mahler Measure Polynomials

The authors analyzed a dataset of 8,438 known polynomials with Mahler measure $< 1.3$ and degree $\le 180$ (known as Known180).

Finding: Excluding polynomials with positive real roots, all but three polynomials in this list were found to divide a Newman polynomial of degree $\le 1000$ .
Theorem: Every integer-coefficient polynomial of degree $\le 44$ with $M(p) < 1.3$ , no non-negative real roots, and no cyclotomic factors, divides a Newman polynomial. This is based on the fact that Known180 is complete up to degree 44.
Unresolved Cases: Three specific polynomials remain unresolved (no Newman multiple found up to degree 1000), leaving open the question of whether they divide Newman polynomials of higher degrees.

B. Improvement of the Universal Constant $\sigma$

Using the certification method, the authors identified new polynomials that do not divide any Newman polynomial, thereby lowering the upper bound for the hypothetical constant $\sigma$ .

New Bound: They discovered a degree-10 polynomial:
$x^{10} - x^8 - x^5 + x + 1$
with a Mahler measure of approximately 1.419404632.
Significance: This improves upon the previous best known upper bound of $\approx 1.4366$ (Drungilas et al., 2023) and the earlier bound of $\approx 1.556$ (Hare & Mossinghoff). If a constant $\sigma$ exists, it must be $\le 1.419404632$ .
Dataset: The paper provides a table of 33 certified examples (degrees 8–12) with Mahler measures $\le 1.556$ that do not divide any Newman polynomial.

C. Newman Polynomials with Repeated Roots

The authors investigated Newman polynomials divisible by $l(x)^2$ (where $l(x)$ is the transformed Lehmer polynomial).

Results: They explicitly constructed Newman polynomials divisible by $l(x)^2$ with degrees up to 150.
Negative Result: They proved that no Newman polynomial of degree $\le 160$ is divisible by $l(x)^3$ . This extends Mossinghoff's previous verification (which stopped at degree 120).
Data: The paper provides a comprehensive table of these polynomials encoded in hexadecimal format.

4. Significance and Contributions

Refinement of Bounds: The paper significantly tightens the theoretical bounds regarding the existence of Newman multiples, pushing the known "forbidden" Mahler measure threshold down from $\approx 1.436$ to $\approx 1.419$ .
Algorithmic Framework: It demonstrates the efficacy of Mixed-Integer Linear Programming (MILP) in solving number-theoretic problems involving restricted coefficient polynomials. The method is shown to be flexible enough to handle both inequality constraints (finding multiples) and equality constraints (cancelling remainders).
Comprehensive Data: The authors provide a complete dataset (Known180 analysis, certified non-divisors, and constructed multiples) available for further research, including verification scripts in GP/PARI.
Resolution of Open Questions: The work confirms that for low-degree polynomials ( $\le 44$ ) with small Mahler measure, the obstruction to dividing a Newman polynomial is almost exclusively the presence of positive real roots, with only three minor exceptions pending higher-degree searches.

5. Conclusion

The paper concludes that while the existence of a universal constant $\sigma$ remains an open question, the search space for counterexamples has been drastically narrowed. The authors suggest that their MILP-based framework is a powerful tool for future investigations into Borwein, Littlewood, and Newman polynomials, potentially allowing for further improvements in bounds and the discovery of new structural properties of polynomials with restricted coefficients.