🔢 mathematics

A random polynomial with multiplicative coefficients is almost surely irreducible

Assuming the Riemann hypothesis for Dedekind zeta functions, the paper proves that a degree $d$ polynomial with random multiplicative $\pm1$ coefficients is almost surely irreducible over the integers, with the probability of reducibility bounded by $O(d^{-1/2+\varepsilon})$ .

Original authors: Péter P. Varjú, Max Wenqiang Xu

Published 2026-08-17

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Péter P. Varjú, Max Wenqiang Xu

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

The Great Polynomial Puzzle

Imagine you are an architect building a tower out of blocks. In the world of mathematics, these towers are called polynomials. They are expressions made of variables (like $x$ ) and numbers (called coefficients) stuck together with addition and multiplication. A simple tower might look like $x^2 + 3x + 2$ .

Now, imagine you have a magical set of instructions that tells you how to build these towers. Sometimes, the instructions are random: you flip a coin to decide if a number is positive or negative. Other times, the instructions are strict and follow a specific pattern, like a recipe that must be followed exactly.

Mathematicians have long been obsessed with a specific question: Are these towers "whole" or can they be taken apart? In math-speak, a polynomial is irreducible if it cannot be broken down into smaller, simpler polynomials multiplied together. It's like a solid, unbreakable brick. If it can be broken down, it's reducible, like a tower made of two smaller blocks glued together.

For decades, mathematicians have studied what happens when you build these towers with random ingredients. They found that if you pick numbers completely at random, your tower is almost always a solid, unbreakable brick. But what if the ingredients aren't completely random? What if they are connected to each other in a secret way? This is the mystery that Peter P. Varjú and Max Wenqiang Xu decided to solve. They looked at a special kind of tower where the numbers are linked by a rule called "multiplicative coefficients," and they asked: even with this secret connection, does the tower stay solid?

The Secret Code of Random Towers

In this paper, the authors explore a very specific type of random polynomial. Imagine you are building a polynomial of degree $d$ (which just means the highest power of $x$ is $d$ ). The coefficients are the numbers in front of the $x$ 's. Usually, you might pick these numbers by rolling a die or flipping a coin for each one, making them totally independent.

But in this study, the coefficients are not independent. They are linked by a "multiplicative" rule. Here is how the authors set up their game:

They start with the number 1.
For every prime number (like 2, 3, 5, 7, 11...), they flip a coin to decide if the coefficient for that prime is $+1$ or $-1$.
For any other number (like 6, which is $2 \times 3$ ), the coefficient is just the product of the coins flipped for its prime parts. So, if 2 got a $+1$ and 3 got a $-1$, then 6 gets a $-1$.

It's like a family tree where the traits of the children are determined entirely by the traits of their parents. The coefficient for a big number is just the "family secret" passed down from its smaller prime ancestors.

The authors wanted to know: If you build a polynomial using this family-tree rule, is it still likely to be an unbreakable, irreducible brick?

The Big Discovery

The answer, according to the paper, is a resounding yes.

The authors prove that if you build a polynomial of degree $d$ using these multiplicative coefficients, the chance that it is irreducible is incredibly high. Specifically, the probability that the polynomial is irreducible is at least $1 - C d^{-1/2+\varepsilon}$ .

Let's break that down in plain English:

As the degree $d$ gets bigger and bigger (making the tower taller), the chance of the tower being broken (reducible) gets smaller and smaller.
The formula $d^{-1/2+\varepsilon}$ means the "risk" of it breaking shrinks very fast, roughly like the inverse of the square root of the size of the tower.
The authors call this "almost surely irreducible." This means that while there is a tiny, non-zero chance the tower could break, that chance vanishes as the tower gets infinitely tall, making the probability of it being a single, solid piece approach 100%.

How They Solved the Mystery

To prove this, the authors had to be very clever because the coefficients are connected, which makes the math much harder than if they were just random.

They used a strategy that involves looking at the polynomial through a "mathematical microscope" called a finite field. Imagine taking your giant polynomial and looking at it not with all its huge numbers, but only looking at the remainders when you divide by a specific prime number (like 7). In this tiny world, the polynomial becomes much simpler.

The authors' main trick was to show that, in these tiny worlds, the polynomial behaves almost exactly like a truly random polynomial. They proved that the "roots" (the points where the polynomial equals zero) are spread out evenly, just like raindrops on a roof. If the roots are spread out evenly, it's a strong sign that the polynomial is irreducible.

However, there was a catch. Because the coefficients are linked, the usual math tools didn't work directly. The authors had to invent a new way to prove this "even spreading." They did this by:

Grouping the primes: They found many small, separate groups of prime numbers that acted like independent randomizers.
Using a famous theorem: They leaned on a result by Green and Tao (who proved that prime numbers contain long arithmetic patterns) to find enough of these groups to make their argument work.
Checking the "weird" cases: They had to be careful about a few special numbers (like 0, 1, and -1) where the randomness might fail. They showed that even for these tricky cases, the chance of the polynomial breaking apart is still very small.

The "What If" and the "Almost"

The paper is very careful about what it claims. They do not say this is true for every single polynomial. They say it is true with probability approaching 1 (or "almost surely") as the degree gets large, meaning the probability of failure is bounded by a specific, shrinking error term ( $C d^{-1/2+\varepsilon}$ ).

There is one big condition: Their proof relies on a famous, unproven idea in mathematics called the Riemann Hypothesis (specifically for Dedekind zeta functions). You can think of the Riemann Hypothesis as a "master key" that unlocks many doors in number theory. The authors assume this key works. If the key works, their proof is solid. If the key doesn't work, their proof might need to be rewritten, but the result is still believed to be true by most mathematicians.

They also mention a related problem involving "Fekete polynomials" (which use a different kind of pattern called the Legendre symbol). They show that their method works for those too, provided the range of numbers is large enough. This suggests their new method is a powerful tool that could help solve other puzzles about random patterns in math.

Why Should You Care?

You might wonder, "Who cares if a math tower breaks or not?"

Well, these polynomials aren't just abstract toys. They appear in cryptography (keeping your passwords safe), in the study of how numbers behave, and in understanding the deep structure of the universe of numbers. Proving that these "connected" random towers are usually solid gives mathematicians confidence that even when things are linked in complex ways, randomness still wins out in the end.

The authors didn't just guess; they built a rigorous, step-by-step argument that holds up under the weight of advanced mathematics. They showed that even with a secret family code linking the numbers together, the resulting polynomial is almost guaranteed to be a unique, unbreakable brick. And that, in the world of math, is a pretty cool discovery.

Technical Summary: A Random Polynomial with Multiplicative Coefficients is Almost Surely Irreducible

Problem Statement
The paper investigates the irreducibility of random polynomials in $\mathbb{Z}[x]$ where the coefficients are not independent, but rather form a multiplicative sequence. Specifically, the authors consider a sequence of random variables $\{X_n\}_{n \ge 1}$ taking values in $\{\pm 1\}$ (or $0$ for non-square-free integers in one model) defined by $X_1=1$ , $X_p$ being independent uniform $\pm 1$ variables for primes $p$ , and $X_n = X_{p_1} \cdots X_{p_k}$ for $n = p_1 \cdots p_k$ . The random polynomial is defined as $P_d(x) = \sum_{n=1}^d X_n x^n$ .

The central question is whether such polynomials are irreducible with high probability as the degree $d \to \infty$ . This setting differs from previous models where coefficients are independent (e.g., uniform on intervals or fixed distributions) or where coefficients are derived from random matrices. The dependence structure here, governed by the multiplicative property of the coefficients, presents a significant challenge to standard probabilistic methods.

Methodology
The proof strategy follows the framework established by Konyagin and refined by [9], which relates the number of irreducible factors of a polynomial to the expected number of its roots in finite fields $\mathbb{F}_q$ . The core logic relies on the Prime Ideal Theorem under the Riemann Hypothesis (RH) for Dedekind zeta functions:

Root Counting: If a polynomial $P$ is irreducible, it has on average 1 root in $\mathbb{F}_q$ for a random prime $q$ . If $P$ has multiple distinct irreducible factors, the number of roots increases. Conversely, if the expected number of roots is close to 1, the polynomial is likely a power of a single irreducible factor.
Equidistribution: To show the expected number of roots is close to 1, the authors must prove that for a random polynomial $P$ and a fixed $a \in \mathbb{F}_q$ , the value $P(a)$ is equidistributed in $\mathbb{F}_q$ .
Handling Dependence: Unlike previous works where coefficients were independent, the multiplicative dependence here prevents the use of standard Markov chain arguments (as used in [9] and [11]). The authors overcome this by:
- Conditioning: Conditioning on the values of coefficients $X_p$ for small primes $p < d/2$ . The remaining coefficients (associated with larger primes) become independent of the conditioned set and of each other.
- Arithmetic Progressions in Primes: The equidistribution argument requires summing over indices that form arithmetic progressions. Since the indices are primes, the authors utilize results from Green and Tao [15] and others [21, 23] to find many disjoint short arithmetic progressions within the set of primes in $[d/2, d]$ .
- Fourier Analysis: They estimate the Fourier coefficients of the random walk $Y = \sum X_i a^{i-1}$ to prove equidistribution for "non-exceptional" residues $a$ .
- Exceptional Residues: For residues where equidistribution might fail (e.g., roots of unity like $0, \pm 1$ ), they apply classical Littlewood-Offord type bounds (Proposition 3.6) to show the probability of vanishing is small ( $O(d^{-1/2+\varepsilon})$ ).
- Double Roots: To rule out the case where the polynomial is a proper power of an irreducible polynomial (which would also yield $\approx 1$ root but with multiplicity), the authors extend the equidistribution result to the pair $(P(a), P'(a))$ , showing that the expected number of double roots is negligible.

Key Contributions

Equidistribution under Multiplicative Dependence: The primary technical contribution is establishing the equidistribution of random polynomials with multiplicative coefficients in finite fields. This is achieved by adapting the argument of [9] to a setting without independent coefficients, utilizing the existence of arithmetic progressions in the primes to bypass the lack of a Markov chain structure.
Handling the "Proper Power" Case: The authors provide a method to distinguish between a polynomial being a single irreducible factor versus a proper power of one, by analyzing the joint distribution of the polynomial and its derivative.
Extension to Fekete-like Polynomials: The methodology is applied to a problem involving random Fekete polynomials $F_{d,f}(x) = \sum_{a=1}^d (\frac{a}{p}) x^a$ , where $p$ is a random prime in a range $(d, f(d)]$ .

Main Results
Assuming the Riemann Hypothesis for Dedekind zeta functions of all number fields, the paper proves:

Theorem 1.1: For the random polynomial $P_d(x)$ with multiplicative $\pm 1$ coefficients, the probability that $P_d(x)/x$ is irreducible over $\mathbb{Z}$ is at least $1 - C d^{-1/2+\varepsilon}$ for any $\varepsilon > 0$ .
- The authors note that in the square-free model, this bound is nearly sharp, as $x=1$ is a root with probability at least $C d^{-1/2-\varepsilon}$ .
Corollary 1.3: For the random polynomial $F_{d,f}(x)$ defined by Legendre symbols $(\frac{a}{p})$ where $p$ is a random prime in $(d, f(d)]$ , if $f(d) > 2^{2\pi(d)} d^4$ , then $F_{d,f}(x)/x$ is irreducible with probability $1 - C d^{-1/2+\varepsilon}$ .
- This result interpolates between the main theorem and the conjecture regarding Fekete polynomials (where $f(d) = d+1$ ).

Significance and Scope
The paper claims to solve a specific case of the irreducibility problem for dependent coefficients, a setting where previous independence-based methods fail. The result is conditional on the Riemann Hypothesis for Dedekind zeta functions, a standard assumption in analytic number theory for controlling error terms in prime ideal distributions.

The authors explicitly state that their bound is close to sharp for the square-free model due to the probability of $x=1$ being a root. They also acknowledge that for "exceptional" residues (like $x=1$ ), the error term in their main theorem arises from classical Littlewood-Offord bounds, and a more precise analysis of these specific cases might yield better estimates. The paper does not claim to resolve the conjecture for Fekete polynomials where the prime range is short ( $f(d) = d+1$ ), noting that the problem becomes harder as the randomness decreases, but it establishes a framework for analyzing such interpolating problems.