Values of rational functions in small subgroups of finite fields and the identity testing problem from powers
Pith reviewed 2026-05-25 09:21 UTC · model grok-4.3
The pith
Rational function images on low-dimensional affine subspaces of finite fields must lie in large multiplicative subgroups.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We give lower bounds on the size of the multiplicative groups containing rational function images of low-dimensional affine subspaces of a finite field F_{q^n} considered as a linear space over a subfield F_q. We apply this to the recently introduced algorithmic problem of identity testing of hidden polynomials f and g over a high degree extension of a finite field, given oracle access to f(x)^e and g(x)^e.
What carries the argument
Lower bounds on the size of multiplicative subgroups that must contain the image of a bounded-degree rational function on a low-dimensional affine subspace viewed over a subfield.
If this is right
- The subgroup-size bounds supply a criterion for deciding whether two hidden polynomials are equal using only oracles for their e-th powers.
- Identity testing becomes feasible once the guaranteed subgroup size exceeds a threshold depending on the extension degree and the exponent e.
- The same lower bounds apply to any algorithmic task that reduces to locating rational-function values inside small subgroups of finite-field multiplicative groups.
- The results give explicit quantitative control over how large the containing subgroup must be when dimension and degree are fixed.
Where Pith is reading between the lines
- The same subgroup lower bounds could be tested numerically for small fields and small dimensions to check sharpness.
- Extensions to rational functions of unbounded degree would require new techniques that the paper leaves open.
- The identity-testing application might combine with existing polynomial factoring algorithms over finite fields to handle larger exponents.
- Analogous statements for additive rather than multiplicative subgroups remain unexplored in the work.
Load-bearing premise
The rational functions have bounded degree and the affine subspaces have low dimension, allowing the group-size lower bounds to be derived from the field structure.
What would settle it
An explicit low-degree rational function and low-dimensional affine subspace whose image lies inside a multiplicative subgroup smaller than the stated lower bound would falsify the claim.
read the original abstract
Motivated by some algorithmic problems, we give lower bounds on the size of the multiplicative groups containing rational function images of low-dimensional affine subspaces of a finite field~$\mathbb{F}_{q^n}$ considered as a linear space over a subfield $\mathbb{F}_q$. We apply this to the recently introduced algorithmic problem of identity testing of "hidden" polynomials $f$ and $g$ over a high degree extension of a finite field, given oracle access to $f(x)^e$ and $g(x)^e$
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper derives lower bounds on the size of the smallest multiplicative subgroup of F_{q^n}^* that contains the image of a bounded-degree rational function evaluated on a low-dimensional affine subspace of F_{q^n} viewed as an F_q-vector space. These bounds are then applied to give an algorithm for identity testing of hidden polynomials f and g over a high-degree extension, given oracle access only to f(x)^e and g(x)^e.
Significance. If the bounds hold, the work supplies new quantitative control on value sets of rational functions in finite-field extensions that is directly usable for algorithmic problems. The explicit parameter regimes, the handling of poles and characteristic issues via standard character-sum estimates, and the direct reduction to the identity-testing application are strengths that make the results potentially useful beyond the immediate setting.
minor comments (2)
- §2, definition of the affine subspace: the dimension parameter k is introduced without an explicit statement of the regime k = o(n) or similar that is needed for the bound to be non-trivial; adding one sentence would improve readability.
- The transition from the group-size lower bound to the identity-testing algorithm in the final section assumes without comment that the exponent e is coprime to q-1; a short remark on this hypothesis would prevent reader confusion.
Simulated Author's Rebuttal
We thank the referee for the positive assessment of our work and the recommendation of minor revision. The report highlights the quantitative control on value sets and the direct reduction to the identity-testing application as strengths.
Circularity Check
No circularity; derivation uses standard field estimates
full rationale
The paper states lower bounds on subgroup sizes for rational function images over low-dimensional affine subspaces of F_{q^n}/F_q, derived from bounded degree, dimension, and standard value-set/character-sum estimates on the field-vector-space structure. The identity-testing application follows directly from these bounds. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the provided text or description; the central claims rest on explicit parameter regimes and field-theoretic arguments that do not reduce to the paper's own inputs by construction.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.