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 be an odd prime number, let be an integer and let be a -tuple of elements of . For any subset of , denote
and for any , let
denote the multiplicity of among the .
Then if none of the is zero, there exists some for which 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 be a primitive -th root of unity. We proceed by contraposition, hence assume that all multiplicities are even. Now consider the element
of the cyclotomic field . By expanding and using the assumption we see that
In particular, the norm (from to ) of is an even integer, but because is odd, the norm of is known to be odd for all . Hence some factor must have , 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
is even. In particular, since is odd, there is at least some with even.
Now we argue by induction on . For , the result is immediate: there are two potential sums and , and so if , there is some odd multiplicity.
Now assume that and that the result holds for all -tuples. Let be a -tuple, with no equal to zero, and which has all multiplicities even. We wish to derive a contradiction. For this, let . For any , we have
by counting separately those with sum which contain or not.
Now take such that is odd, which exists by induction. Our assumptions imply that is also odd. Then, iterating, we deduce that is odd for all integers . But the map is surjective onto , since is non-zero. Hence our assumption would imply that all multiplicities are odd, which we have seen is not the case… Hence we have a contradiction.