Let $F = GF(2^n)$. Let $P(x), Q(x) \in F[x]$ be such that $P(x)$ is a permutation, while $Q(x)$ is not a permutation.
For $\lambda \in F^*$ define the function $g_\lambda(x) = Tr(\lambda Q(x))$. Let $S$ denote the support of $Tr(P(x))$, and let $S_{i,\lambda}$ denote the set $\{x \in S : g_\lambda(x) = i\}$.
Problem:
Show that there exists $\lambda \in F^*$ such that $|S_{0,\lambda}| \neq |S_{1,\lambda}|$.
I have been puzzling over a more specific version of this for a little while (where $P(x)$ and $Q(x)$ are specific monomials), but I'm hoping that the only information that I'll ultimately need about $P(x)$ and $Q(x)$ is whether or not they are permutations. I've run a few small computations using various monomials and I have yet to find a case where $S_{0,\lambda}$ and $S_{1,\lambda}$ have the same size for all $\lambda$ (though, for each pair $P(x), Q(x)$ that I have used, they are equinumerous for certain values of $\lambda$, so it certainly isn't always true that $|S_{0,\lambda}| \neq |S_{1,\lambda}|$).
Any and all tips, hints, observations, suggestions, etc. will be quite welcome.
P.S. I thought it easiest to restrict to characteristic 2 for the time being.
Ok. Unless I made a mistake the good news are that this always holds. The bad news is that it holds even without the assumption that $Q$ is not a permutation. But we can also make the observation that if the restriction of $Q$ is not injective then the total imbalance increases. See below what exactly I mean by this.
Observe the following: the numbers $S_{i,\lambda}$ only depend on the values of $Q$ taken in the set $S$. So by changing the values of $Q$ outside of $S$ we can certainly turn it into a non-bijection without affecting the data.
On with a more precise calculation. I will use the (canonical) additive character $e:F\to\{+1,-1\}\subset\Bbb{C}$ heavily. We define $$ e(z)=(-1)^{tr(z)} $$ for all $z\in F$. Because the trace is additive, we have, for all $z_1,z_2\in F$ $$ e(z_1)\cdot e(z_2)=e(z_1+z_2). $$ A standard important property is the character sum $$ M(\lambda)=\sum_{z\in F}e(\lambda z)=\begin{cases}q,&\text{if $\lambda=0$},\\ 0,&\text{otherwise}.\end{cases}\qquad(*) $$ Here $q=2^n=|F|$.
We see that $x\in S$, iff $tr(P(x))=1$, iff $1-e(P(x))=2$, and similarly $1-e(P(x))=0$, iff $x\notin S$. Also, for all $x\in S$ we have $x\in S_{i,\lambda}$ if and only if $e(\lambda Q(x))=(-1)^i, i=0,1.$
Let us temporarily fix $\lambda\in F$. We see that we can write the difference $N(\lambda):=|S_{0,\lambda}|-|S_{1,\lambda}|$ as a character sum $$ N(\lambda)=\frac12\sum_{x\in F}[1-e(P(x))]e(\lambda Q(x)). $$ Squaring this gives (taking into account the rule $(*)$ in the last factor $$ N(\lambda)^2=\frac14\sum_{x\in F,y\in F}[1-e(P(x))][1-e(P(y)]e(\lambda Q(x)+\lambda Q(y)). $$ Let's sum these over all $\lambda\in F$ (I temporarily include $\lambda=0$). We get $$ \begin{aligned} \sum_{\lambda\in F}N(\lambda)^2&=\frac14\sum_{\lambda\in F,x\in F,y\in F}[1-e(P(x))][1-e(P(y)]e(\lambda Q(x)+\lambda Q(y))\\ &=\frac14\sum_{x\in F,y\in F}[1-e(P(x))][1-e(P(y)]\sum_{\lambda\in F}e([Q(x)+Q(y)]\lambda), \end{aligned} $$ where we changed the order of summation so that the $\lambda$-sum became the inner sum. The common factors not depending on $\lambda$ were moved outside this inner sum.
By $(*)$ the inner sum is $q$, if $Q(x)+Q(y)=0$, or (we are in characteristic two) if $Q(x)=Q(y)$, and zero otherwise. Promising, right? The equation $Q(x)=Q(y)$ will hold for more pairs, when $Q$ is not injective!
Anyway, $$ \sum_{\lambda\in F}N(\lambda)^2=\frac q4\sum_{x,y,Q(x)=Q(y)} [1-e(P(x))][1-e(P(y)]. $$ The constraint $Q(x)=Q(y)$ holds trivially, if $x=y$. Let's separate that part from the sum: $$ \sum_{\lambda\in F}N(\lambda)^2=\frac q4\sum_{x\in F}[1-e(P(x))]^2+ \frac q4\sum_{x\neq y, Q(x)=Q(y)}[1-e(P(x))][1-e(P(y))]. $$ Because $P$ is a permutation, we know that $1-e(P(x))=2$ for exactly $q/2$ choices of $x$. Namely those $\in S$. Otherwise $1-e(P(x))=0$, so this simplifies to $$ \sum_{\lambda\in F}N(\lambda)^2=\frac{q^2}2+\sum_{x\in S, y\in S, x\neq y, Q(x)=Q(y)}q. $$ Here the latter sum is always non-negative. Anyway, we have shown that $$ \sum_{\lambda\in F}N(\lambda)^2\ge q^2/2. $$ What about $\lambda=0$? We easily see that $N(0)=|S|=q/2$, so $N(0)^2=q^2/4.$ Therefore $$ \sum_{\lambda\in F,\lambda\neq0}N(\lambda)^2=\frac{q^2}4+\sum_{x\in S, y\in S, x\neq y, Q(x)=Q(y)}q>0. $$ Hence $N(\lambda)\neq0$ for some $\lambda\neq0$, which is exactly what you wanted to prove.
I would call the sum $\sum_{\lambda\in F^*}N(\lambda)^2$ the total imbalance, because every $\lambda$ such that $N(\lambda)\neq0$ contributes to this sum.
So we got a bit more precise information out of this. Hope this helps you with whatever you are working on. Note that in odd characteristic you need to tweak the above in many ways, but character sums and $(*)$ are a surprisingly powerful tool.