Expansion properties of polynomials over finite fields

2024/03/06 by Nuno Arala, Arala, Nuno, Sam Chow +1 · 1 citation
Computer Science · #Coding theory and cryptography #Polynomial and algebraic computation #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2403.03732

Abstract

We establish expansion properties for suitably generic polynomials of degree d in d+1 variables over finite fields. In particular, we show that if P∈\mathbbF_q[x₁,…,x_d+1] is a polynomial of degree d coming from an explicit, Zariski dense set, and X₁,…,X_d+1⊆\mathbbF_q are suitably large, then |P(X₁,…,X_d+1)|=q-O(1). Our methods rely on a higher-degree extension of a result of Vinh on point--line incidences over a finite field.

Cited by

• Incidence theorems for multivariate polynomials over finite fields

Related

• Incidence geometry and polynomial expansion over finite fields
• Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets
• Sum-product estimates via directed expanders
• Combinatorial Nullstellensatz Approach to Polynomial Expanding
• Further bounds in the polynomial Szemerédi theorem over finite fields