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 ofamong the
.
Then if none of theis 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.
Dear professor Kowalski,
Thank you for this nice lemma, I am fond of this kind of results.
It seems to me (if I am not wrong) that the argument of the second proof holds
also whenever the problem is considered in any finite abelian group of odd cardinality,
working one coset after the other (and may be even in non abelian groups ?!).
I was wondering if the first proof does also hold ?
Best regards from Paris,
Eric