In the Universe of Equations, Virtually All Are Prime

Prime numbers get all the love. They’re the stars of countless popular stories, and they feature in the most celebrated open questions in mathematics. But there’s another mathematical phenomenon that’s almost as foundational, yet receives far less attention: prime equations.

These are equations — polynomial equations in particular — that can’t be divided by any other equations. Like prime numbers, they’re at the heart of a wide range of research areas in mathematics. For many particular problems, if you can understand something about the prime equations, you’ll find you’ve answered the question you actually set out to solve.

“When we have a question, we can reduce it to some knowledge about prime numbers,” said Lior Bary-Soroker of Tel Aviv University. “Exactly the same thing happens with polynomials.”

Just as with prime numbers, the most basic thing to know about prime equations is: How often do they occur? Over the last year mathematicians have made considerable progress on answering that question. In a paper posted at the end of October, Emmanuel Breuillard and Péter Varjú of the University of Cambridge proved that virtually all equations of a certain type are prime.

This means that unlike prime numbers, which are scarce, prime equations are abundant. The new paper solves a 25-year-old conjecture and has implications everywhere from online encryption to the mathematics of randomness.

More Ways to Fail

Many questions in mathematics boil down to questions about polynomial equations. These are the kinds of equations — like y = 2x − 3 and y = x² + 5x + 6 — that consist of variables raised to some power with coefficients in front.

These equations behave just like ordinary numbers in many respects: You can add, subtract, multiply and divide them. And as with numbers, it’s natural to ask which equations can be expressed as a product of two smaller equations.¹

When an equation cannot be divided into two smaller equations, mathematicians say that it’s irreducible. Mathematicians would like to know how often irreducible polynomial equations occur.

Trying to make statements about the frequency of irreducible polynomials among all possible polynomials — equations with any number of variables, raised to any power, with any coefficients — is hard. So mathematicians have attacked narrower versions of the question, by restricting the exponents (looking at polynomials with no variables raised higher than the fifth power, for example) or limiting the coefficients to a narrow range. In October 2017 Bary-Soroker and Gady Kozma, a mathematician at the Weizmann Institute of Science in Israel, proved that virtually all polynomials with a certain restricted range of coefficients are irreducible.

Breuillard and Varjú solved a slightly different problem. They considered polynomials of any length, with any exponents, and with any coefficients (the only restriction being that the list of possible coefficients is finite).

Breuillard and Varjú’s method gave them access to a much simpler problem. In 1993, Andrew Odlyzko, a mathematician now at the University of Minnesota, and Bjorn Poonen, now at the Massachusetts Institute of Technology, conjectured that as you consider increasingly complicated polynomials with the constraint that their coefficients must be either 0 or 1, equations that can be factored become vanishingly rare in the sea of “prime” polynomials. Odlyzko and Poonen’s conjecture, by restricting polynomials to just two coefficients, was an effort to gain a foothold in an overwhelming question.

“If you want to study something and you can’t prove a lot of things, it’s good to start with something simple,” Bary-Soroker said.

Their conjecture was also motivated by basic arithmetic. Prime numbers are common among the first 10 numbers but grow ever rarer after that. To be prime, a number needs to avoid being divisible by any whole number smaller than itself (save the number 1). As numbers get bigger, the list of numbers that could divide them grows longer — there are more ways primality can fail in big numbers than in small numbers.

With polynomials, a different dynamic is at work. In order for a polynomial to be factorable, its coefficients have to stand in just the right relationship with one another. The polynomial y = x² + 5x + 6 can be factored into (x + 3) × (x + 2) only because there happen to be two numbers (2 and 3) that you can add to make the second coefficient (5) and multiply to make the third coefficient (6). Polynomials with more terms have a more complicated set of demands that the coefficients must fulfill. Finding factors that satisfy all the coefficients become less likely as the number of coefficients grows.

“For a polynomial to be reducible you have to have a coincidence, some special relations among the coefficients,” Odlyzko said. “With a high-degree polynomial you have more relations that have to be satisfied.”

Random Walks

Breuillard and Varjú did not set out to study polynomial irreducibility. Instead, they were interested in the mathematics of a random walk. In this random walk, imagine yourself standing on a clock face, with the numbers 1 through 11 marked out at regular intervals. You start at the spot corresponding to 1 and flip a coin: Tails, you multiply the number you’re on by some other number you’ve chosen ahead of time, then advance to the corresponding spot on the circle. (In such clock or “modular” number systems, if the outcome is a number greater than 11, you just keep going around the clock until you’ve advanced the required number of spaces.) If the coin flip comes up heads, you multiply the number you’re on by your preselected number, add one, and advance to the corresponding spot.

Given these conditions, Breuillard and Varjú wanted to understand two things: How long will it take for you to visit every point on the circle? And how long will it take for you to visit every point approximately the same number of times?

These questions are known to mathematicians as the “mixing problem,” and they turn out to have something to do with polynomial irreducibility. Breuillard and Varjú recognized that the paths of a random walk can be described by a polynomial equation with 0 and 1 as coefficients. The “mixing time” of the random walk is closely related to whether or not most of the polynomials describing that random walk are irreducible.

“We observed that we could say something about the kinds of questions we wanted to understand if we knew whether these polynomials were irreducible,” Varjú said.

To test for irreducibility, Breuillard and Varjú adapted a technique developed in the 1980s that links irreducibility to number theory. They wanted to know how many solutions a given polynomial has in a given modular number system. Previous work had shown that the number of solutions a polynomial has reflects the number of factors. So if it has three solutions on average across modular number systems, it has three factors. Just one solution? Then one factor. And if a polynomial has just one factor, that means it’s irreducible.

Using this method, applied to modular number systems based on prime numbers, Breuillard and Varjú proved that as you consider larger and larger polynomials (with coefficients of 0 or 1), the proportion of polynomials that is irreducible gets closer and closer to 100 percent.

Their proof has a caveat. It depends on the truth of another conjecture: the Riemann hypothesis, the most important and daunting unsolved problem in mathematics. But the Riemann hypothesis is widely accepted, which buoys Breuillard and Varjú’s work.

Their result has wide-ranging implications. On a practical level, it’s good if not unexpected news for online encryption, since factorable polynomials could undermine a commonly used digital encryption scheme. Maybe more importantly, it’s a big step toward understanding the nature of these equations, which abound in life and math but are hard to characterize in totality.

“Previous estimates for the fraction of these polynomials [that are irreducible] were much weaker,” Odlyzko said. “Now these guys say practically all of them are irreducible.”