Suppose we have an $n^2$ root of unity, $\omega$, and we are working modulo a prime $p$. I'm wondering if we can find values such that:
$$\omega^{n \cdot a+b} = x^a + y^b$$
for all $a$ and $b$.
Or, perhaps more easily,
$$\omega^{n \cdot a+b} = x^c + y^d$$
where $c$ and $d$ can each be one of any $n$ different values.
Essentially, I'm wondering if we can split $n^2$ different powers into a sum of $n$ different powers of two variables.
This should be a comment, because I am still asking for clarifications. But, it is a bit awkward to format it as one, so an answer it is.
The first variant is impossible. For if $a=b=0$ the right hand side is $2$, but in the left we have $1$ irrespective of choices of $\omega$, $p$, $x$ and $y$.
OTOH with the more relaxed variant we have solutions such as: $p=5$, $\omega=2$, a fourth root of unity, so $n=2$. Then $x=2$, $y=3$, $c\in\{1,3\}$, $d\in\{0,1\}$ works, because we get the following table
$$ \begin{array}{cccl} a&b&\omega^{na+b}&\quad x^c+y^d\\ \hline 0&0&1&=2^1+4^1\\ 0&1&2&=2^3+4^1\\ 1&0&4&=2^3+4^0\\ 1&1&3&=2^1+4^0. \end{array} $$ All the four combinations $x^c+y^d$ were used as prescribed. I don't know if this generalizes. This was simply the smallest case I tested, and there happened to be a solution. In general there may easily be some arithmetic obstructions to finding any solutions, but the set up of the latter formulation is relatively flexible.
Did I interpret it correctly? Is this the type of thing you are looking for?