Let $F$ be an $n-$degree extension of $\mathbb{F}_q$ and let $f(x)\in F[x]$. Let $$g(x)=\sum_{i=0}^{n-1}a_if(x)^{q^i}$$ with $a_i\in F$. Let $\alpha\in F$ be a root of $g$, prove that $\alpha$ is a root of $f$.
I'm studying an algorithm called ZZ for solving certain systems of polynomial equations over $GF(k)$, and the validity of this algorithm depends on this claim. Moreover, the $a_i$ are allowed later to be terms of the form $x^{q^j}$ with $j=0,...,n-1$, and the result is still true. Any suggestion?
This is false as stated. For a counterexample consider the simple case of $f(x)=x$ and $a_0=a_1=\cdots=a_{n-1}=1.$ Then we have $$ g(x)=x+x^q+x^{q^2}+\cdots+x^{q^{n-1}}=tr^F_E(x), $$ which is the trace function from the field $F=\Bbb{F}_{q^n}$ to the subfield $E=\Bbb{F}_q$. More precisely, the restriction of the polynomial function $g$ to $F$ is the trace.
The trace function is a surjective $E$-linear function from $F$ to $E$, so by rank-nullity theorem there are $q^{n-1}$ elements $y\in F$ such that $g(y)=0$. OTOH $x=0$ is the only zero in $F$ of the polynomial $f(x)=x$.