Prescribing digits in finite fields (Q1748133)

Consider the finite field \(\mathbb{F}_q\), where \(q=p^r\) with \(r\geq 2\) and \(p\) a prime number, and fix a basis \(\{e_1,\ldots, e_r\}\) of the vector space \(\mathbb{F}_q\) over \(\mathbb{F}_p\). Since every \(x\in \mathbb{F}_q\) has a unique representation \(x=\sum_{j=1}^r c_j e_j\) with \(c_1,\ldots, c_r\in \mathbb{F}_p\), then we may call \(c_j\) the \(j\)-th digit of \(x\). Results here deal with estimates on the number of field elements given that exactly \(k\) of the \(r\) digits are prescribed. More precisely, let \(P\in \mathbb{F}_q[X]\) be a polynomial of degree \(n\), where \(p\nmid n\), and let \(J\subseteq \{1,\ldots, r\}\) with \(|J|=k\) and \(\alpha=(\alpha_j)_{j\in J}\in (\mathbb{F}_p)^k\). Define \(\mathcal{F}_q(P,k,J,\alpha)\) to be the set of all \(x\in \mathbb{F}_q\) such that the \(j\)-th digit of \(P(x)\) equals \(\alpha_j\) for each \(j\in J\). Then (Theorem 1.1) \[ \left| \; |\mathcal{F}_q(P,k,J,\alpha)| - \frac{q}{p^k}\right| \leq \frac{p^{k}-1}{p^k}\, (n-1)\, \sqrt q\; . \] In particular (Corollary 1.2) for up to half of prescribed digits, an asymptotic result is obtained as \(p^r\to\infty\), where \[ |\mathcal{F}_{p^r}(P,k,J,\alpha)| = p^{r-k} \, (1+o(1)) \] uniformly over \(k\leq (\frac{1}{2}-\varepsilon) r\) for any \(\varepsilon >0\). Both Theorem 1.1 and Corollary 1.2 are developed further for the particular case \(P=aX^2\) (Theorem 1.3 and Corollaries 1.4, 1.5) as well as the case in which \(x\) is considered only among the primitive elements of \(\mathbb{F}_q^*\) (Theorem 1.6 and Corollary 1.8).