In his recent work on the divisor function in arithmetic progressions to smooth moduli, A. Irving proves the following rather amusing lemma (see Lemma 4.5 in his paper):
Lemma Let $latex p$ be an odd prime number, let $latex k\geq 1$ be an integer and let $latex h=(h_1,\ldots,h_k)$ be a $latex k$-tuple of elements of $latex \mathbf{F}_p$. For any subset $latex I$ of $latex \{1,\ldots, k\}$, denote
$latex h_I=\sum_{i\in I}{h_i},$
and for any $latex x\in\mathbf{F}_p$, let
$latex \nu_h(x)=|\{I\subset \{1,\ldots, k\}\,\mid\, h_I=x\}|$
denote the multiplicity of $latex x$ among the $latex (h_I)$.
Then if none of the $latex h_i$ is zero, there exists some $latex x$ for which $latex \nu_h(x)$ is odd.
I will explain two proofs of this result, first Irving’s, and then one that I came up with. I’m tempted to guess that there is also a proof using some graph theory, but I didn’t succeed in crafting one yet.
Irving’s proof. This is very elegant. Let $latex \xi$ be a primitive $latex p$-th root of unity. We proceed by contraposition, hence assume that all multiplicities $latex \nu_h(x)$ are even. Now consider the element
$latex N=\prod_{i=1}^k(1+\xi^{h_i})$
of the cyclotomic field $latex K_p=\mathbf{Q}(\xi)$. By expanding and using the assumption we see that
$latex N=\sum_{x\in\mathbf{F}_p} \nu_h(x)\xi^{x}\in 2\mathbf{Z}[\xi].$
In particular, the norm (from $latex K_p$ to $latex \mathbf{Q}$) of $latex N$ is an even integer, but because $latex p$ is odd, the norm of $latex 1+\xi^{h_i}$ is known to be odd for all $latex h_i\not=0$. Hence some factor must have $latex h_i=0$, as desired.
A second proof. When I heard of Irving’s Lemma, I didn’t have his paper at hand (or internet), so I tried to come up with a proof. Here’s the one I found, which is a bit longer but maybe easier to find by trial and error.
First we note that
$latex \sum_{x\in \mathbf{F}_p} \nu_h(x)=2^k$
is even. In particular, since $latex p$ is odd, there is at least some $latex x$ with $latex \nu_h(x)$ even.
Now we argue by induction on $latex k\geq 1$. For $latex k=1$, the result is immediate: there are two potential sums $latex 0$ and $latex h_1$, and so if $latex h_1\not=0$, there is some odd multiplicity.
Now assume that $latex k\geq 2$ and that the result holds for all $latex (k-1)$-tuples. Let $latex h$ be a $latex k$-tuple, with no $latex h_i$ equal to zero, and which has all multiplicities $latex \nu_h(x)$ even. We wish to derive a contradiction. For this, let $latex j=(h_1,\ldots,h_{k-1})$. For any $latex x\in\mathbf{F}_p$, we have
$latex \nu_h(x)=\nu_j(x)+\nu_j(x-h_k),$
by counting separately those $latex I$ with sum $latex x$ which contain $latex k$ or not.
Now take $latex x$ such that $latex \nu_j(x)$ is odd, which exists by induction. Our assumptions imply that $latex \nu_j(x-h_k)$ is also odd. Then, iterating, we deduce that $latex \nu_j(x-nh_k)$ is odd for all integers $latex n\geq 0$. But the map $latex n\mapsto x-nh_k$ is surjective onto $latex \mathbf{F}_p$, since $latex h_k$ is non-zero. Hence our assumption would imply that all multiplicities $latex \nu_j(y)$ are odd, which we have seen is not the case… Hence we have a contradiction.
