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]$? 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)|$
 A: 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.

