Let $l=\min\{s\in \mathbb{N}|0\in s\cdot (\mathbb{F}_{p^n}^\times)^k\}$. Is any information known about this number already as a function of $k$? Any reference would be greatly appreciated!
3 Answers
Write $q=p^n$. You can replace $k$ by $gcd(k,q-1)$ and assume $k | (q-1)$. Now, trivially, $l=2$ if and only if $(-1)^{(q-1)/k} = 1$. If $l >2$, then $l=3$ if the Fermat curve has a point which, from the Weil bound, happens if $k < q^{1/4}$, approximately. For larger $k$ you may want to use techniques from additive combinatorics. Someone else may chip in on that.
Adding on to Felipe's answer, here is a nontrivial example (obviously you can take $k=p^n-1$) where we can make $\ell$ as large as we want if $k$ is very large (almost $p^n-1$). We can assume $k|p^n-1$ and write $d=(p^n-1)/k$.
If $d$ is prime, $d|p^n-1$ but $d\nmid p^m - 1$ for any $m<n$, and the cyclotomic polynomial $\Phi_d$ is irreducible mod $p$ (i.e. $p$ is a generator mod $d$) then $(F_{p^n}^\times)^k$ is just the set $1,x,x^2,\ldots,x^{d-1}$ where
$$ \Phi_d(x)=1+x+\cdots + x^{d-1} = 0 \pmod p $$
is the minimal polynomial of $x$ over $p$, and so we see that $\ell = \min(p,d)$ in this case since any smaller nontrivial linear combination would give a lower-degree polynomial vanishing at $x$.
Explicitly, we can achieve $\ell=p$ for any prime $p$ that is a generator of $F_d^\times$ for some larger prime $d>p$ (which is every $p$ if the Artin conjecture is true, does anyone know if the existence of a single such $d$ is much easier?). Just take the above example with $k=(p^{d-1}-1)/d$, $n=d-1$, and $\ell = p$.
It may also be helpful to search for "Waring's problem in finite fields". For a bound derived from discrete Fourier analysis, see https://dl.dropboxusercontent.com/u/27883775/math%20notes/analytic-nt.pdf