How many elements in $GF(p^m)$ such that it's a $k$-th power of some element and also can be represented as $f(\beta)$ over $GF(p)_{d}[x]$?

Question

Let $GF(q)$ be a finite field of order $q=p^m$, where $p$ is a prime number. Given an element $\beta \in GF(q)$ and the integers $k, d \in \mathbb{N}$, Let $$I_{k} = \{ x \in GF(q) \mid x = \alpha^k, \alpha \in GF(q) \}$$ and $$F_{d}(\beta) = \{ x \in GF(q) \mid \exists f \in GF(p)_{d-1}[x], f(0) = 1, x = \beta \cdot f(\beta)\}$$ where $$GF(p)_{d}[x] = \{ f \in GF(p)[x] \mid \mathrm{deg}(f)\leq d\}$$ How can we calcuate or estimate $|I_{k} \cap F_{d}(\beta)|$

Answer 1

Trying to say something non-trivial about a generic case of the edited version of the question. The old answer can be viewed in the edit history of this answer. Trust me, you aren't missing anything worthwhile :-)

---

Because the multiplicative group $GF(q)^*$ is cyclic of order $q-1$, a non-zero $x\in GF(q)$ is a $k$th power if and only if it is an $\ell$the power, where $\ell=\gcd(k,q-1)$. I will write everything using $\ell$ as a reminder, but you may want equally well think that $k\mid q-1$ when $\ell=k$.

The set $F_d(\beta)$ is the coset $\beta+V$, where $V$ is the $GF(p)$-span of the elements $\beta^2,\beta^3,\ldots,\beta^d$. In what I call the generic case the space $V$ has dimension $d-1$. If $\beta$ belongs to a subfield $GF(p^t), t<d-1$, then the space $V$ has a lower dimension (at most $t$). Those were not excluded and I may come back to that case later. Anyway, the set $F_d(\beta)$ has $p^{d-1}$ elements.

By the properties of cyclic groups, a random element of $GF(q)^*$ is an $\ell$th power with probability $1/\ell$, so we expect the intersection $I_k\cap F_d(\beta)$ to have approximately $p^{d-1}/\ell$ elements. Character sums form a relatively universal tool for estimating the accuracy of such estimates. In the present case we need both the additive characters (to get a handle on the additive subspace $V$) as well as the multiplicative characters of $GF(q)$ (to get a handle on the subset of $\ell$th powers).

Let $\operatorname{tr}:GF(q)\to GF(p)$ be the trace function, $\operatorname{tr}(x)=\sum_{i=0}^{m-1}x^{p^i}$. Let's denote the canonical additive character of $GF(q)$ by $\psi$, so $$ \psi(x):=e^{2\pi i \operatorname{tr}(x)/p}. $$ Let's denote $$ V^\perp=\{y\in GF(q)\mid tr(xy)=0\ \forall\,x\in V\}. $$ Because the trace-form is non-degenerate, $\dim_{GF(p)}V^{\perp}=m-(d-1).$ By the well-known properties of character sums we have, for all $x\in GF(q)$, $$ \sum_{y\in V^{\perp}}\psi(yx)= \begin{cases} p^{m-d+1},&\ \text{if $x\in V$, and}\\ 0,&\ \text{otherwise.} \end{cases} $$ Consequently $$ \sum_{y\in V^{\perp}}\psi(y[x-\beta])= \begin{cases} p^{m-d+1},&\ \text{if $x\in F_d(\beta)$, and}\\ 0,&\ \text{otherwise.} \end{cases} $$ We can use this as a test of membership in $F_d(\beta)$.

Similarly, let $\chi_1:GF(q)\to\Bbb{C}^*$ be a multiplicative character of order $\ell$ (so $\chi_1(GF(q)^*)=\mu_\ell$). Let $G$ be the group of characters generated by $\chi_1$, so $G\simeq C_\ell$. Let $\chi_0$ be the principal character (= the constant map to $1$). Again, a standard fact is that $$ \sum_{\chi\in G}\chi(x)=\begin{cases} \ell,&\ \text{if $x=z^\ell$ for some $z\in GF(q)^*$,}\\ 1,&\ \text{if $x=0$, assuming the convention $\chi_0(0)=1$ and $\chi(0)=0$, when $\chi\neq\chi_0$,}\\ 0,&\ \text{otherwise.} \end{cases} $$ This is our membership test in the set of $\ell$th powers.

In the generic case $0\notin F_d(\beta)$, and we can ignore any special treatment of $x=0$.

Putting all of the above together we get a formula for the size of the intersection in terms of character sums

$$ |I_k\cap F_d(\beta)|=\frac1{\ell\cdot p^{m-d+1}} \sum_{y\in V}\sum_{\chi\in G}\sum_{x\in GF(q)^*}\psi(y[x-\beta])\chi(x).\qquad(*) $$ Let's take a close look at the innermost sum $$ \sum_{x\in GF(q)^*}\psi(y[x-\beta])\chi(x)=\overline{\psi(y\beta)} \sum_{x\in GF(q)^*}\psi(yx)\chi(x). $$ The last sum is the well studied Gauss sum $S(y,\chi)=\sum_{x\in GF(q)^*}\psi(yx)\chi(x)$. We know that $$ S(y,\chi)= \begin{cases} q-1,&\ \text{when $y=0$ and $\chi=\chi_0$,}\\ -1,&\ \text{when $y\neq0$ and $\chi=\chi_0$,}\\ 0,&\ \text{when $y=0$ and $\chi\neq\chi_0$,}\\ \text{has absolute value $\sqrt q$},&\ \text{when $y\neq0$ and $\chi\neq\chi_0$.} \end{cases} $$ In the sum $(*)$ we identify the main term ($y=0,\chi=\chi_0$) of size $\approx p^{d-1}/\ell$, and crudely apply the triangle inequality to the rest of them. Observing that there are $(\ell-1)(|V^\perp|-1)$ terms of magnitude $\sqrt q$ and smaller terms, we arrive at the approximate bound $$ \left\vert|I_k\cap F_d(\beta)|-\frac{p^{d-1}}\ell\right\vert\le\sqrt q. $$ This gives something non-trivial only when $|V|=p^{d-1}<\sqrt q$, or when $d>m/2$.

---

The disappointing features of this estimate are

• One would expect the Gauss sums to have random phases, and hence that there should be a lot of cancellation in the error term. There are several relations that the Gauss sums related to different choices of $y$ satisfy. Yet, the factor $\overline{\psi(y\beta)}$ make it non-obvious how to proceed here.
• This bound works for an arbitrary subspace $V$ of dimension $d-1$ just the same. The special description of $F_d(\beta)$ is not used at all. In the generic case there is a recipe for the dual (w.r.t. the trace form) of the monomial basis $\{1,\beta,\ldots,\beta^{m-1}\}$. Exploiting that structure may open a route forward, but exploring that would take more time than I can put into this question at this time.