A parity lemma of A. Irving

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 p be an odd prime number, let k\geq 1 be an integer and let h=(h_1,\ldots,h_k) be a k-tuple of elements of \mathbf{F}_p. For any subset I of \{1,\ldots, k\}, denote
h_I=\sum_{i\in I}{h_i},
and for any x\in\mathbf{F}_p, let
\nu_h(x)=|\{I\subset \{1,\ldots, k\}\,\mid\, h_I=x\}|
denote the multiplicity of x among the (h_I).
Then if none of the h_i is zero, there exists some x for which \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 \xi be a primitive p-th root of unity. We proceed by contraposition, hence assume that all multiplicities \nu_h(x) are even. Now consider the element
of the cyclotomic field K_p=\mathbf{Q}(\xi). By expanding and using the assumption we see that
N=\sum_{x\in\mathbf{F}_p} \nu_h(x)\xi^{x}\in 2\mathbf{Z}[\xi].
In particular, the norm (from K_p to \mathbf{Q}) of N is an even integer, but because p is odd, the norm of 1+\xi^{h_i} is known to be odd for all h_i\not=0. Hence some factor must have 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
\sum_{x\in \mathbf{F}_p} \nu_h(x)=2^k
is even. In particular, since p is odd, there is at least some x with \nu_h(x) even.

Now we argue by induction on k\geq 1. For k=1, the result is immediate: there are two potential sums 0 and h_1, and so if h_1\not=0, there is some odd multiplicity.

Now assume that k\geq 2 and that the result holds for all (k-1)-tuples. Let h be a k-tuple, with no h_i equal to zero, and which has all multiplicities \nu_h(x) even. We wish to derive a contradiction. For this, let j=(h_1,\ldots,h_{k-1}). For any x\in\mathbf{F}_p, we have
by counting separately those I with sum x which contain k or not.

Now take x such that \nu_j(x) is odd, which exists by induction. Our assumptions imply that \nu_j(x-h_k) is also odd. Then, iterating, we deduce that \nu_j(x-nh_k) is odd for all integers n\geq 0. But the map n\mapsto x-nh_k is surjective onto \mathbf{F}_p, since h_k is non-zero. Hence our assumption would imply that all multiplicities \nu_j(y) are odd, which we have seen is not the case… Hence we have a contradiction.

Published by


I am a professor of mathematics at ETH Zürich since 2008.

One thought on “A parity lemma of A. Irving”

  1. 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,


Leave a Reply to Eric Balandraud Cancel reply

Your email address will not be published. Required fields are marked *