Critical-scale growth bounds for congruence-preserving functions over finite fields
Henry Zweiman
September 9, 2026
Abstract
Let . We prove that a function preserving congruences modulo every irreducible polynomial is a polynomial map if for every input of sufficiently large degree. This replaces the factor in the growth hypothesis of Bell and Nguyen by a positive constant times . The proof uses integer-valued Carlitz digit polynomials, multiplied by a squarefree primorial, in the auxiliary-polynomial method. The rationality step is Bell and Nguyen’s linear-growth theorem. For -linear functions we prove the sharp threshold for , and give a nonpolynomial example attaining it. We also give a Newton-coefficient formulation of the remaining sharp problem and an obstruction to a coefficient estimate using growth alone.
1. Results and their scope
Throughout, is a prime power, , and . We set . Write , including zero, and let be the set of monic irreducible polynomials in . We say that preserves prime congruences if
A polynomial map is the evaluation of one polynomial in on . Its coefficients need not belong to .
Bell and Nguyen [1, Theorem 1.4] proved polynomiality under for all sufficiently large . Their Section 4 asks whether the growth function can be enlarged; Question 4.1 proposes every fixed constant below the primorial threshold. Our first theorem addresses the enlargement of the growth scale.
Theorem 1.1.
Let be the least positive integer such that , and set
The constant in Theorem 1.1 is chosen for a transparent proof, rather than optimized. For the stated is, respectively, . Put
Then . The proposed sharp condition in [1, Question 4.1] is on every sufficiently large degree- shell, for some . Theorem 1.1 does not prove that full assertion.
Theorem 1.3.
Suppose is -linear and satisfies (1). If is not a polynomial map, then
This constant is sharp, even with the maximum over all inputs of degree in the numerator. Thus Bell–Nguyen Question 4.1 holds for -linear functions.
The interpolation polynomials below are classical. Wagner’s work [3,4] describes related coefficient divisibility for functions preserving all polynomial moduli, including prime powers. Here only (1) is assumed, and the squarefree factor replaces the least common multiple with prime powers. Li and Sha [2] study congruence-preserving maps between finite residue rings. We use the classical interpolation tools to obtain a growth theorem for arbitrary maps on the infinite ring .
2. Integral interpolation polynomials
Define
In particular and . These are the normalized linear Carlitz polynomials; see also [3, Section 2]. We give the needed elementary properties.
Lemma 2.1.
The polynomial is -linear, has -degree , and takes values in on . Moreover,
Proof.
The decomposition gives inductively
This proves linearity and the asserted -degree. The factors of are exactly all monic degree- polynomials, proving (5). For of degree , the number of those polynomials divisible by is if and zero otherwise. This proves (6).
For arbitrary , if there is nothing to prove. Otherwise, for every with , the map is onto and has fibers of size . Therefore . This holds at every prime, so . The triangular assertions follow from the definitions. If , every factor , , has degree , proving (8).
Lemma 2.2.
For ,
Proof.
The squarefree polynomial divides , proving the lower bound. If counts monic irreducibles of degree , then , whence . From , the error in replacing by is at most . Summing gives the final assertion.
For , write with . Set
The first expression is independent of appended zero digits; .
Lemma 2.3.
The polynomials , , are -valued and preserve prime congruences. Their -degrees are , so they are linearly independent over . Put . For ,
Proof.
Integrality follows from Lemma 2.1. If , every value of is divisible by . If , all the in (9) are -units. Thus and preserves congruences modulo . Also .
If a factor with has positive exponent, the value is zero. In every other case, Lemmas 2.1 and 2.2 give, with ,
Here the same strict bound for applies when .
3. The general growth theorem
We first recall the elementary vanishing principle underlying the Bell–Nguyen polynomial method [1, Lemma 2.1].
Lemma 3.1.
Suppose satisfies (1), vanishes on , and whenever . Then .
Proof.
If not, choose of least degree with . Then . For each prime of degree at most , the remainder of modulo has degree less than and hence has zero image. Condition (1) gives , contradicting its degree bound.
Proposition 3.2.
Under the hypotheses of Theorem 1.1, there is a nonzero such that for every .
Proof.
Take sufficiently large and put
We may require for every : the finitely many exceptions to (2) have bounded image degrees. Choose unknowns and form
Then is -valued and preserves prime congruences. Since , , , and , Lemma 2.3 gives
Thus requiring for these inputs imposes at most homogeneous linear equations over . The number of unknowns is strictly larger:
A nonzero solution exists. It represents a nonzero polynomial : for each power of , the have distinct -degrees, and are independent over .
For an input of degree , , the same calculation gives
The two -dependent summands are nonincreasing: for , . By Lemma 2.2 we have . Lemma 3.1 therefore gives .
Clear denominators in the relation from Proposition 3.2, and write
Necessarily , since a nonzero polynomial in cannot vanish on all of . There are constants such that
for every nonzero and every . If and , the term has strictly larger degree than every other term of , a contradiction. Enlarge to cover the finitely many roots of and obtain for .
Bell and Nguyen [1, Theorem 3.1] prove that a function satisfying (1) is a polynomial map if for some with . Apply that theorem with . Finally, minimality of gives , and hence .
The gain comes from (10): independent polynomials have value degrees on . Ordinary monomials of comparable -degree have value degrees of order . The rational denominators of the digit polynomials do not enter the value-height estimate, while the factor ensures the exact congruences needed for vanishing.
4. The sharp linear case
Every -linear has a unique locally finite expansion
Indeed, recursively set . Lemma 2.1 makes the coefficients integral. The resulting map agrees with on the basis , and for .
Proposition 4.1.
The function (14) preserves prime congruences if and only if for every .
Proof.
Fix of degree . For , is a -unit, so is a polynomial over . If for every , all higher terms vanish modulo , proving sufficiency.
Conversely, subtract from . The result modulo is a linear function on vanishing at the basis , and hence vanishing everywhere. Evaluating successively at and using proves for every . Apply this at all primes.
Lemma 4.2.
Write , , and . Then
Consequently,
Proof.
The recursion and (8) give . Since , induction proves (15). For the limiting assertion it suffices to consider a finite right side. Choose strictly larger than it, and then choose with such that eventually . The finitely many earlier have an upper bound . Equation (15) gives
for all large . Divide by and let decrease to the asserted bound. The identically zero map causes no exception with the convention .
If , Lemmas 2.2 and 4.2 give for all large . Proposition 4.1 forces there. Thus (14) is a finite polynomial.
For sharpness define
This map is well-defined, -linear, and preserves prime congruences. Put . For ,
because and for . For the same bound is at most : the sequence decreases for . At the term with has degree , and . Eventually it strictly dominates all other terms. Therefore for all sufficiently large . This gives the asserted sharp limit and proves nonpolynomiality, since a fixed polynomial map has value degrees at .
Wagner’s characterization [3, Theorem 3.2] for the stronger all-moduli condition uses
in place of . Proposition 4.1 is the squarefree counterpart. The boundary construction above and the degree estimate address the prime-congruence growth condition of [1].
5. Newton coefficients and the remaining threshold
Fix an ordering of . For the base- expansion , put . The first entries form and . Define
Proposition 5.1.
Every function has a unique locally finite expansion
It preserves prime congruences if and only if
There is no restriction on .
Proof.
For of degree , the denominator in (18) has valuation
Indeed, each aligned block of consecutive entries runs through every residue modulo . In the final incomplete block preceding , none has its residue: their differences from are nonzero and have degree less than . The numerator at any input has at least the same valuation. Thus all are -valued. Since and for , integral triangular recursion gives the expansion and uniqueness.
Fix of degree . Terms with have -unit denominators. If for , the other terms vanish pointwise modulo , proving sufficiency. Conversely, subtract the initial sum with . The resulting congruence-preserving function vanishes on the complete residue system , hence everywhere modulo . Successive evaluation at the remaining gives for . Taking all primes proves (19).
This statement concerns first powers of primes. It makes no assertion that the same ordering characterizes preservation of all prime powers; compare the local constructions in [2, Theorem 1.11].
The sharp general question is consequently a truncation problem: does (19), together with the strict subcritical bound on degree- inputs, force eventually? A finite expansion is equivalent to a polynomial map. The next example shows why value growth by itself cannot supply the needed coefficient margin.
Proposition 5.2.
Let be at and elsewhere. Its coefficients in (18) satisfy, for ,
Proof.
The leading coefficient of interpolation at gives
For , the numerator has degree . The denominator has degree . Subtraction gives the formula; Lemma 2.2 gives the limit.
The function fails (1), since and . It is an obstruction to an estimate using growth alone, not a counterexample to the sharp question. A proof at every constant below must use the congruences and the general coefficient transform together, or supply a different rigidity argument.
6. Verification and further directions
The proofs hold for every prime power and do not depend on finite computations. The accompanying exact-arithmetic checker tests both prime and extension fields. The digit-basis audit covers 8,570 literal values over , including integrality, degrees, and congruences. It also checks 56,320 instances of the height and propagation inequalities and 2,816 dimension inequalities. A separate audit covers the additive criterion, its boundary example, and the general Newton criterion with positive and negative examples.
The main remaining problem is the sharp arbitrary-function threshold. The integer-valued auxiliary family suggests optimizing its value-height profile and replacing the rectangular set of indices in (11) by a weighted set. Those changes do not by themselves prove the sharp constant. Theorems 1.1 and 1.3, and their coefficient formulations, constitute one growth-rigidity result rather than separate solutions to the full question.
References
[1] J. P. Bell and K. D. Nguyen, An analogue of Ruzsa’s conjecture for polynomials over finite fields, J. Combin. Theory Ser. A 178 (2021), 105337. doi:10.1016/j.jcta.2020.105337. Theorem and question numbering here refers to arXiv:1910.08255v1 (2019).
[2] X. Li and M. Sha, Congruence preserving functions in the residue class rings of polynomials over finite fields, Finite Fields Appl. 61 (2020), 101604. doi:10.1016/j.ffa.2019.101604; arXiv:1807.02379v2.
[3] C. G. Wagner, Linear pseudo-polynomials over , Arch. Math. 25 (1974), 385–390. Author’s copy.
[4] C. G. Wagner, Polynomials over with integral-valued differences, Arch. Math. 27 (1976), 495–501. Author’s copy.