🔢 mathematics

On polynomials of small range sum

This paper characterizes all non-constant polynomials over $\mathbb{F}_p$ with range sums equal to $p$ that have degree exactly $\frac{p-1}{2}$ for sufficiently large primes, thereby re-establishing the Lovász–Schrijver classification of sets with few determined directions using discrete Fourier analysis.

Original authors: Gergely Kiss, Ádám Markó, Zoltán Lóránt Nagy, Gábor Somlai

Published 2026-07-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gergely Kiss, Ádám Markó, Zoltán Lóránt Nagy, Gábor Somlai

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 magician working with a special deck of cards. This deck has exactly $p$ cards, where $p$ is a very large prime number (think of a number so big it has 10 digits, like 520,219,910). You have a magical machine—a polynomial—that takes every card from the deck, does some math, and spits out a new number.

Here's the catch: The machine must spit out numbers that, when you add them all up, equal exactly $p$ .

For a long time, mathematicians knew that if your machine wasn't just a boring, flat line (a constant number), it had to be quite complex. In fact, its "complexity score" (called the degree) had to be at least half of $p$ minus a tiny bit. But nobody knew exactly what these complex machines looked like. Were there a million different designs? Just one? A few?

The Big Discovery
In this paper, the authors act like detectives who finally cracked the case. They proved that if you have a machine with that specific complexity score (exactly $\frac{p-1}{2}$ ) and the total sum of its outputs is $p$ , there are only two possible designs for the machine (ignoring simple shifts or flips).

Think of it like finding the only two secret recipes that make a cake weigh exactly 1 kilogram, given that the cake must be baked in a specific, tricky oven.

The two recipes are:

The Simple One: A formula that looks like $x^{\frac{p-1}{2}} + 1$ .
The Big One: A formula that looks like $\frac{p+1}{2} \times (x^{\frac{p-1}{2}} + 1)$ .

The authors are 100% certain (mathematically proven) that for primes larger than 520,219,910, no other designs exist. If you try to build a machine with that complexity and that sum, you will inevitably end up with one of these two.

What They Ruled Out
The paper explicitly shuts the door on the idea that there are other "weird" machines hiding in the shadows.

They proved you can't have a machine with that specific complexity score that is a constant (unless it's the number 1, which is a boring special case).
They proved you can't have a machine with that complexity score that has a "leading coefficient" (the main number multiplying the big power) that is some random number in between 1 and $\frac{p-1}{2}$ . The main number must be either 1 or $\frac{p-1}{2}$ .
They ruled out the possibility that there are dozens of different shapes these machines could take. It's strictly a two-option menu.

The "Direction" Connection
Why does this matter? The paper connects this math puzzle to a problem about drawing lines on a grid. Imagine you have $p$ dots scattered on a piece of paper. You draw lines connecting every pair of dots. How many different angles (directions) do these lines point in?

Mathematicians have been trying to figure out the minimum number of directions these dots can create. The authors show that their discovery about the two special polynomial "recipes" proves a famous old result by Lovász and Schrijver.

They proved that if you have a set of $p$ dots that creates exactly $\frac{p+3}{2}$ directions (which is a very specific, low number), those dots must be arranged in a very specific, unique pattern (up to rotation and shifting). It's like saying, "If you arrange these $p$ dots to point in exactly this many directions, they must form this specific 'X' shape made of two lines crossing at the center."

How Sure Are They?
The authors are extremely confident, but they have to be careful with the size of the number $p$ .

Proven: They have a rigorous, step-by-step mathematical proof that works for any prime number $p$ larger than 520,219,910.
Suspected: They strongly believe (but haven't fully proven yet) that this result holds true even for much smaller primes. They think the huge number requirement is just a technical hurdle they had to jump over to make the proof work, not a real limit of the math itself.
The "Small" Primes: For smaller primes (like $p=47$ ), they managed to prove the result about the dots and directions using a different tool called "Fourier analysis," but the main proof about the polynomials relies on that huge number.

The Bottom Line
The paper solves a specific puzzle: "What do polynomials look like if their outputs sum to $p$ and they are just complex enough to be interesting?" The answer is: "Only two specific shapes." This discovery then unlocks a new, cleaner way to prove an old theorem about how dots can be arranged on a grid to create the fewest possible line directions.

The authors admit there are still open questions, like what happens if the sum is $2p$ or $3p$ instead of just $p$ , or if the prime number is small. But for the specific case of sum $p$ and large primes, the mystery is solved.

Technical Summary: On Polynomials of Small Range Sum

Problem Statement
The paper addresses a problem concerning polynomials over a finite field $\mathbb{F}_p$ (where $p$ is a prime). Specifically, it investigates the minimum degree of a polynomial $P \in \mathbb{F}_p[x]$ given a constraint on its "range sum." The range sum is defined as the sum of the values of the polynomial, where the values are interpreted as integers in the set $\{0, 1, \dots, p-1\}$ , taken over all elements of the field. That is, the condition is $\sum_{x \in \mathbb{F}_p} [P(x)] = p$ , where $[P(x)]$ denotes the integer representative of the field element.

Previous work (Kiss and Somlai [14]) established that if a non-constant polynomial satisfies this range sum condition, its degree must be at least $(p-1)/2$ . The central problem of this paper is to characterize all such polynomials that achieve this lower bound exactly, i.e., polynomials of degree $d = (p-1)/2$ satisfying the range sum condition.

Methodology
The authors employ a combination of finite field algebra, combinatorial number theory, and discrete Fourier analysis.

Algebraic Characterization of Roots: The authors first prove that any polynomial $P$ of degree $(p-1)/2$ with range sum $p$ is fully reducible and possesses distinct roots. They utilize Newton's identities and properties of power sums over finite fields to relate the roots of $P$ to the multiplicities of its values.
Legendre Symbol Analysis: A significant portion of the proof involves analyzing sums of Legendre symbols evaluated on translates of the set of roots and the set of values (with multiplicities). The authors derive identities linking the leading coefficient of $P$ , the roots, and the values.
Combinatorial Bounds on Intersections: To constrain the possible values of the leading coefficient, the authors utilize results regarding the intersection sizes of translates of quadratic residues. Specifically, they apply Lemma 2.4 (Szőnyi) and Lemma 2.6 to bound the number of elements $\gamma$ for which the sum of Legendre symbols $\sum \left(\frac{\alpha_i - \gamma}{p}\right)$ is large. This allows them to rule out most potential values for the leading coefficient for sufficiently large $p$ .
Discrete Fourier Analysis: In the second part of the paper, the authors apply the characterization of these polynomials to the "direction problem" in affine geometry. They use the Plancherel formula for the discrete Fourier transform of the characteristic function of a set $S \subset \text{AG}(2, p)$ . By analyzing the magnitude of Fourier coefficients corresponding to projection polynomials, they relate the number of determined directions to the specific forms of the polynomials identified in the first part.

Key Results

Characterization of Minimal Degree Polynomials (Theorem 1.2):
For a prime $p \ge 520219910$ , the authors prove that up to affine transformations ( $x \mapsto ax+b$ ), there are exactly two types of polynomials of degree $(p-1)/2$ with range sum $p$ :
1. $P(x) = \pm(x-a)^{(p-1)/2} + 1$
2. $P(x) = \frac{p+1}{2} \left( \pm(x-a)^{(p-1)/2} + 1 \right)$
  where $a \in \mathbb{F}_p$ . The paper notes that the assumption on the size of $p$ is likely technical and the result likely holds for smaller primes.
Re-establishment of Lovász-Schrijver Characterization (Theorem 1.4):
Using the above characterization and Fourier analysis, the paper provides a new proof for a theorem by Lovász and Schrijver [12]. For primes $p \ge 47$ satisfying the conditions of Theorem 1.2, there is a unique set (up to affine transformation) of cardinality $p$ in $\text{AG}(2, p)$ that determines exactly $(p+3)/2$ directions. This set is explicitly described as the union of two lines (identified with $\mathbb{F}_p$ ) intersecting at the origin, containing the quadratic residues (and the origin) on each line.

Significance and Claims
The paper claims to provide a complete characterization of polynomials with minimal degree and a specific range sum, resolving a question posed in previous literature regarding their uniqueness.

The primary significance lies in the application of this algebraic characterization to finite geometry. By linking the algebraic properties of projection polynomials to the number of directions determined by a set, the authors offer a new proof of the Lovász-Schrijver result. This approach bypasses some of the original geometric arguments, instead relying on the structural constraints of the polynomials derived via number-theoretic methods.

The authors explicitly state that their results re-establish the characterization of sets with few determined directions and provide an explicit description of the Lovász-Schrijver construction based on projection polynomials. They also highlight that the connection between the multiset of values and the degree of the polynomial is a natural general problem, referencing related work on specific cases (e.g., values restricted to $\{0, 1\}$ ).

Open Problems
The paper concludes by posing two open problems:

Stability: If a polynomial has range sum $p$ but is not an affine translate of the identified minimal degree polynomials, does its degree satisfy a stronger lower bound (e.g., $C \cdot (p-1)$ for $C > 1/2$ )?
Generalized Range Sums: For range sums equal to $k \cdot p$ (where $k > 1$ ), are the minimal degree polynomials necessarily affine translates of specific forms, or do they exhibit higher degrees for large $p$ ?

More like this