Source-linked AI summary
Bounds on polynomial approximations of the discrete logarithm function
Swastik Kopparty, Rishabh Kothary, Ashutosh Shankar
TL;DR
The paper studies how many inputs a low-degree polynomial can match exactly with the discrete logarithm over a prime field. It improves the univariate and bivariate bounds, using a connection to Reed–Solomon list decoding. The degree-one result also improves on the earlier Θ(√p) bound by a polynomial factor.
Problem
The paper asks for upper bounds on the number of exact agreement points between a low-degree polynomial and the discrete logarithm over a prime field.
Source: §1 · pp. 1–2Method
The proof connects polynomial agreement to Reed–Solomon list decoding and handles the failure of exact homomorphism by restricting attention to suitable subsets.
Source: §1 · p. 2, §6.1 · p. 14Results
The paper improves the univariate bound for every degree, including D > p/2, improves the degree-one bound by a polynomial factor, and reaches the analogous Johnson threshold for bivariate polynomials.
Source: §1 · pp. 2–3Takeaways & Limitations
The univariate agreement bound is tied to the Johnson agreement parameter from Reed–Solomon list decoding.
Source: §1 · p. 2Further improvements through the list-decoding approach would follow from improved Reed–Solomon list-decoding bounds with sublinear list size.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D p}.$$ We show two improvements: (1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas. (2) For $D = 1$, where both the above bounds are $O(\sqrt{p})$, we give an asymptotically improved upper bound of $O(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics. We also improve the [CS00] bounds on the number of points of the form $(x, dlog(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.
1 Introduction
The paper improves bounds on how often low-degree polynomials agree with the discrete logarithm over prime fields, building on a problem with no prior improvement over the Coppersmith–Shparlinski bound. It connects the univariate bounds to Reed–Solomon list decoding and also improves bounds for bivariate polynomials.
1 Introduction
- The paper frames the problem as bounding exact agreement points between a polynomial and discrete logarithm, continuing work that had not improved the prime-field bound for any D.The discrete logarithm’s role in cryptographic constructions motivates understanding its algebraic and combinatorial properties.Source: §1 · pp. 1–2
- The first result improves the univariate approximation bound for every degree D and remains nontrivial when D > p/2.The paper identifies the target scale as the Johnson agreement parameter for Reed–Solomon codes.Source: §1 · p. 2
- The univariate proof turns one good polynomial approximation into many same-degree approximations, then contradicts Reed–Solomon list-decodability.The first step uses the almost-homomorphism property of dlog; shifting arguments and Szemerédi’s theorem handle its failure to be exact.Source: §1 · p. 2
- Further improvements through this approach depend on improved Reed–Solomon list-decoding bounds with sublinear list size.The introduction also notes that existing bounds do not yet provide that improvement because their polynomial list sizes are large.Source: §1 · pp. 2–3
- For degree-one polynomials, the paper improves the Coppersmith–Shparlinski Θ(√p) bound by a polynomial factor.The proof uses the sum-product phenomenon and line-point incidence bounds in finite fields.Source: §1 · p. 3
- The bivariate approximation bound is improved to the analogous Johnson-bound threshold.This concerns the number of points on the discrete-log graph where a degree-at-most-D bivariate polynomial vanishes.Source: §1 · p. 3
2 Notation and preliminaries
The preliminaries set notation for the finite-field discrete logarithm and introduce the tools used later: Bézout’s theorem, the Johnson bound, arithmetic-progression results, and finite-field incidence estimates.
2 Notation and preliminaries
- The paper works over a prime field Fp, fixes a generator, and defines the discrete logarithm with respect to that generator.It uses N = p − 1 as shorthand.Source: §2 · p. 4
- Bézout’s theorem bounds the number of common zeros of coprime bivariate polynomials of degrees at most d and e by d · e.The preliminaries also define m · V as the m-fold sumset of V.Source: §2 · p. 4
2.1 Johnson bound
- The Johnson-bound setup controls the size of agreement sets for a list of codewords whose sets have limited pairwise intersections.The section presents a rearrangement of the standard bound in agreement-set terms.Source: §2.1 · p. 4
2.2 Theorems from additive combinatorics
- Sections 4 and 5 use arithmetic-progression-free set results, including Szeméredi’s theorem that sufficiently large sets of natural numbers contain long progressions; Section 6 invokes a line-point incidence bound.The cited passage identifies the estimate as Lewko [Lew26], but does not state its formula.Source: §2.2 · p. 5
3 Agreement sets and conjugates
The section constructs conjugates of bivariate polynomials and studies how their roots relate to the agreement set T(Q). For irreducible Q, that set cannot contain a long arithmetic progression.
3.1 Distinctness of Conjugates
- Conjugates Q_i,b(X,Y)=Q(g^iX,Y+i+b) serve as list elements for the proof.The construction is based on algebraic properties of the discrete logarithm function.Source: §3.1 · p. 5
- If α belongs to T(Q)_i,b, then the corresponding conjugate Q_i,b vanishes at (g^α,α).T(Q)_i,0 and T(Q)_i,1 separate indices according to whether α+i stays below N or wraps past N.Source: §3.1 · p. 6
- For nonzero Q of degree less than p depending on both variables, conjugates with different i and the same b are not scalar multiples.This distinctness holds for i,i′ in {0,…,N−1}.Source: §3.1 · p. 6
3.2 Structure of agreement set T(Q)
- For irreducible Q of degree D, T(Q) cannot contain an integer arithmetic progression of size D^2+2.Such a progression would yield D^2+1 common roots for Q and a conjugate; distinctness and Bézout’s theorem limit them to D^2.Source: §3.1 · p. 6, §3.2 · p. 7
4 Approximation by univariate polynomials
This section studies how often a low-degree univariate polynomial agrees with the discrete logarithm function. Its proof forms a list of transformed polynomials and applies the Johnson bound to their agreement sets.
4 Approximation by univariate polynomials
- The section counts locations α where f(g^α)=α, equivalently where f agrees with the discrete logarithm at g^α.The polynomial f is over F_p.Source: §4 · p. 8
- The proof forms agreement sets T_i for transformed polynomials and aims to apply the Johnson bound to that collection.It defines T_i=T(Q_i,0) and proceeds by cases.Source: §4 · p. 8
- For distinct indices, the transformed univariate polynomials are distinct and their agreement sets overlap in at most D locations.The overlap bound follows because their difference is a nonzero polynomial of degree at most D.Source: §4 · p. 8
5 Approximation by bivariate polynomials
This section studies where bivariate polynomials vanish on points of the form (g^α,α). Its proof factors the polynomial, controls intersections of transformed agreement sets, and invokes the Johnson bound.
5 Approximation by bivariate polynomials
- The section considers the locations where a bivariate polynomial Q satisfies Q(g^α,α)=0, recorded in T(Q).The theorem is stated for nonzero polynomials Q over F_p.Source: §5 · p. 10
- The proof factors Q into irreducible factors and selects a factor by an averaging argument before constructing transformed agreement sets.It then seeks to verify the hypotheses for applying the Johnson bound.Source: §5 · pp. 10–11
- For distinct transformed irreducible factors of degree d, the agreement sets intersect in at most d^2 points, enabling a Johnson-bound argument.The intersection bound uses their coprimality and Bézout’s theorem.Source: §5 · p. 11
6 Approximation by linear functions
For linear polynomials, the section proves an improved agreement bound by turning a large agreement set into a sum-product incidence contradiction. Its proof handles the discrete logarithm’s wrap-around by restricting to subsets where a homomorphism-like property holds.
6 Approximation by linear functions
- Theorem 6.1 bounds agreement for every polynomial of degree at most 1; the proof contradicts |S| ≥ c p^(1/2−ε) with ε = 1/10 for sufficiently large p.This yields the stated exponent 2/5 for the linear case.Source: §6 · p. 13, §6.2 · pp. 15, 17
6.1 Proof Overview
- The overview places triple sums of graph points on a line, then compares them with points formed from sums and products under an idealized logarithm homomorphism.The line contains at most p points; incidences with the constructed lines supply the contradiction.Source: §6.1 · pp. 13–14
6.2 Proof of Theorem 6.1
- Because wrap-around prevents an exact homomorphism, the proof partitions the agreement set into buckets where a restricted version of the property holds.The proof uses the k-fold sum-and-product operation U⋆k = {(u1 + ··· + uk, u1u2···uk)} to relate these subsets to sumsets.Source: §6.1 · p. 14, §6.2 · p. 14
- The proof constructs points from triples and lines from pairs in the projected agreement set, then uses their incidences to contradict the assumed large agreement size.The point set has size at most p, while the contradiction follows from the incidence bound for sufficiently large p.Source: §6.2 · pp. 16–17