Mathematicians Find Structure in Biased Polynomials

When you deposit a quarter and turn the crank on a gumball machine, the flavor you receive is basically random.

In math, sometimes a polynomial, like x² + y², works the same way. When you plug in numbers for x and y, the values the polynomial takes might be random. Other polynomials might favor particular outcomes, like a machine stocked with lots of grape gumballs and just a few cherry ones thrown in.

But which polynomials are biased, and which are not? And what could make a polynomial biased in the first place? Mathematicians are now closer to a complete answer. Several recent papers have teased out the relationship between structure and bias in polynomials more precisely than ever before.

“It’s really exciting to see these results and to see this new flurry of work,” said Shachar Lovett of the University of California, San Diego.

The new work characterizes the structure of a polynomial in terms of one of its defining characteristics: the extent to which it can be broken up into simpler parts. For example, the polynomial x² + xy can be rewritten as the product of two simpler polynomials: x(x + y). On the other hand, the polynomial xy + zw can’t be broken down this way.

(In this context, all polynomials are assumed to be homogeneous — meaning every term in the sum has the same degree, or total exponent — and the factors have to be homogeneous too. For example, x² + xy is homogeneous because x² and xy each have degree 2: the degree of x² is the exponent of x, and the degree of xy is the sum of the exponents of x and y, 1 + 1.)

This ability of a polynomial to be expressed in pieces is captured in a measurement known as rank. A low-rank polynomial can be broken into smaller components and has a lot of structure, like a wall that’s made of bricks. A high-rank polynomial has less structure and is more like a slab of concrete.

Intuitively, more structured (low-rank) polynomials should be less random and therefore more biased, and less structured (high-rank) polynomials should be more random and less biased. The new work makes this idea more precise by tightening the connection between the bias of a polynomial and the size of its rank.

“If your polynomial is biased as a function, then there’s a reason for that,” said Guy Moshkovitz of the City University of New York (Baruch College), one of the co-authors of the new work. “It’s because you can write it in a simple way. You can express it using a small number of ingredients.”

To measure bias, mathematicians need to consider the polynomial’s value for every possible input, which they can’t do in a number system with infinitely many values, like the real numbers. Instead, they use finite fields, or finite number systems, for the input and output values of the polynomials.

Finite fields come in many different sizes. For example, there is a finite field with just five numbers in it: 0, 1, 2, 3 and 4. In a finite field, addition and multiplication wrap around, like adding hours on a clock: Just as adding two hours to 11:00 makes it 1:00, plugging in x = 2 to the polynomial x³ gives you an output of 3, instead of 8.

Finite fields provide the right backdrop for studying the idea of bias. To calculate a polynomial’s bias with respect to a particular finite field, plug in every combination of numbers — which is possible because the number system is finite — and then measure how skewed the outputs are.

As an example, consider the polynomial x² + xy and the finite field with just two elements, 0 and 1. This polynomial has value 1 when x = 1 and y = 0, but it has value 0 for the other three possible combinations of x and y. In other words, this polynomial is biased toward a particular output.

In 2007, the mathematicians Ben Green and Terence Tao released one of the first results that showed a general relationship between bias and a kind of rank. They established that for polynomials evaluated over certain finite fields, the more biased a polynomial is, the lower its rank has to be. Green and Tao found an upper bound on the rank in terms of bias — a description of how the rank of a polynomial is limited by that polynomial’s amount of bias.

Green and Tao’s paper was important because it established a link between bias and rank. However, it didn’t show how closely the two properties are related. It was a bit like saying a highway has a speed limit that is something less than a million miles per hour. It helps to know that there’s some speed limit, but the number itself is not very useful.

“The bound that they got was kind of an atrocious bound,” Moshkovitz said. “It’s an insane function.”

In the last few years, mathematicians have been improving the bound connecting bias and rank. In February, two groups of mathematicians independently found near-perfect bounds for the simplest unsolved case: degree 3 homogeneous polynomials like x³ and xyz + yz² + w³.

One paper was by Karim Adiprasito of the University of Copenhagen and the Hebrew University of Jerusalem and David Kazhdan and Tamar Ziegler of Hebrew University. The other was by Alex Cohen, who at the time was an undergraduate at Yale University and is now a graduate student at the Massachusetts Institute of Technology, and Moshkovitz.

Both groups proved that for the degree 3 polynomials, rank is basically equivalent to another quantity called analytic rank that is completely determined by bias. That means that for degree 3 polynomials, bias and rank are about as closely tied as they could possibly be.

Around two weeks later, Cohen and Moshkovitz posted a preprint that showed that rank and analytic rank are essentially equivalent for polynomials of any degree, as long as the finite field the polynomial is evaluated over is big enough (meaning it contains enough numbers) compared to the analytic rank.

So for large enough fields, the new work proves that biased polynomials have low rank and that the two properties are closely connected.

“Their result is really interesting, and their proof is really nice,” said Luka Milićević of the Mathematical Institute of the Serbian Academy of Sciences and Arts, who proved an earlier improvement on Green and Tao’s bound.

The main caveat with the new work is the condition about the size of the finite field. For Cohen and Moshkovitz’s result to hold, the field size has to be much larger than the analytic rank. This limits how the result can be used. In some computer science applications, for example, researchers need to use the finite field with just two numbers in it.

The problem is worse in mathematical contexts that involve studying a collection of polynomials all at once. In that kind of setting, the size of the finite field needs to be especially large for Cohen and Moshkovitz’s result to hold. For now, this curtails the usefulness of their work in those areas.

“There’s still a lot more to do,” Ziegler said.

So far, no one has been able to prove Cohen and Moshkovitz’s result without the restriction on the field, but some mathematicians are looking for a way to do so.

“That’s a very tantalizing goal,” Moshkovitz said.

Correction: November 9, 2021
The original caption for the lead image mistakenly characterized the new proof, stating that it established that the more a polynomial can be broken into smaller pieces, the more biased the polynomial’s outputs are. The new proof actually establishes that the more biased a polynomial’s outputs are, the more it can be broken into smaller pieces.