E. Kowalski's blog

A parity lemma of A. Irving

one comment

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
$N=\prod_{i=1}^k(1+\xi^{h_i})$
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
$\nu_h(x)=\nu_j(x)+\nu_j(x-h_k),$
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.

March 16th, 2015 at 12:31 pm

Posted in Exercise,Mathematics

Who proved the Peter-Weyl theorem for compact groups?

Tamas Hausel just asked me (because of my previous post on the paper of Peter and Weyl) how could Peter and Weyl have proved the “Peter-Weyl Theorem” for compact groups in 1926, not having Haar measure at their disposal? Indeed, Haar’s work is from 1933! The answer is easy to find, although I had completely overlooked the point when reading the paper: Peter and Weyl assume that their compact group is a compact Lie group, which allows them to discuss Haar measure using differential forms!

Peter-Weyl

So the question is: who first proved the full “Peter-Weyl” Theorem for all compact groups? Pontryaguin, in 1936, certainly does, without remarking that Peter-Weyl didn’t, possibly because it was clear to anyone that the argument would work as soon as an invariant measure was known to exist. But since there are “easier” proofs of the existence of Haar measure for compact groups than the general one for all locally-compact groups (using some kind of fixed-point argument), it is not inconceivable that someone (e.g., von Neumann) might have made the connection before.

In fact, there is an amusing mystery in connection with Pontryaguin’s paper and von Neumann: concerning Haar measure, he refers to a paper of von Neumann entitled Zum Haarschen Mass in topologischen Gruppen, and gives the helpful reference Compositio Math., Vol I, 1934. So we should be able to read this paper on Numdam? But no! The first volume of Compositio Mathematica there is from 1935; it is identified as Volume I, and there is no paper of von Neumann to be found…

[Update: as many people pointed out, the paper of von Neumann is indeed on Numdam, but appeared in 1935; I was tricked by the absence of 1934 on the Compositio archive and the author’s name being written J.V. Neumann (I had searched Numdam with “von Neumann” as author…)]

March 15th, 2015 at 8:03 pm

Posted in Mathematics

For those readers who understand spoken French (or simply appreciate the musicality of the language) and are interested in the history of mathematics, I warmly recommend listening to the recording of a recent programme of Radio France Internationale entitled “Pourquoi Bourbaki ?” In addition to the dialogue of Sophie Joubert with Michèle Audin and Antoine Chambert-Loir, one can hear some extracts of older émissions with L. Schwartz, A. Weil, H. Cartan, J. Dieudonné, for instance.

February 27th, 2015 at 7:31 pm

Аналитическая теория чисел

Thanks to the recent Russian translation of my book with Henryk Iwaniec, I can now at least read my own last name in Cyrillic; I wonder what the two extra letters really mean…

Analytic Number Theory in Russian

February 9th, 2015 at 9:06 pm

Posted in Language,Mathematics

An ideal hypothetical list

A few months ago, for purposes that will remain clouded in mystery for the moment, I had the occasion to compose an ideal list of rare books of various kinds, which do not necessarily exist.

Here is what I came up with:

(i) “The Elements of the Most Noble game of Whist; elucidated and discussed in all details”, by A. Bandersnatch, Duke Dimitri, N. Fujisaki, A. Grothendieck, Y. Grünfiddler, J. Hardy, Jr., B. Kilpatrick and an Anonymous Person.

(ii) “Vorlesungen über das Ikosaeder und die Auflösung der Gleichungen vom funften Grade”, by F. Klein; with barely legible annotations and initialed “HW” on the first page.

(iii) “Histoire Naturelle”, Volume XXXIII: Serpens, by George Louis Leclerc, Comte de Buffon, edition of 1798; initialed “A.K.” on the title page.

(iv) “Chansons populaires de Corse, Navarre et Outre-Quiévrain”, collected and commented by P. Lorenzini.

(v) “奥の細道” (Oku no Hosomichi), by Matsuo Bashò.

(vi) “On the care of the pig”, by R.T. Whiffle, KBE.

(vii) “La Chartreuse de Parme”, by Stendhal.

(viii) “Der tsoyberbarg”, by T. Mann; Yiddish translation by I.B. Singer of “Der Zauberberg”.

(ix) “Les problèmes d’un problème”, by P. Ménard; loose manuscript.

(x) Opera Omnia of L. Euler, volumes 1, 2, 7, 11, 13, 23, 24, 30, 56, 62, 64, 65 and 72.

(xi) “Discorsi sopra la seconda deca di Tito Livio”, by N. Macchiavelli.

(xii) “An account of the recent excavations of the Metropolitan Museum at Khróuton, in the vicinity of Uqbar”, by E.E. Bainville, OBE.

(xiii) Die Annalen der Physik, volumes 17, 18, 23 and 25.

(xiv) “Diccionaro y gramática de la lengua Tehuelve”, anonymous; attributed on the second page to “a Humble Jesuit of Rank”.

(xv) “Le roi cigale”, French translation by Jacques Mont–Hélène of an anonymous English romance.

(xvi) “Mémoires du Général Joseph Léopold Sigisbert Hugo”, by himself, with an Appendix containing the “Journal historique du blocus de Thionville en 1815, et des sièges de cette ville, Sierck et Rodemack en 1815”.

(xvii) “Le Comte Ory”, full orchestral score of the opera by G. Rossini with Libretto by E. Scribe and Charles-Gaspard Delestre-Poirson.

(xviii) “Absalom, Absalom”, by W. Faulkner; first edition, dedicated To R.C. on the second page.

(xix) “Ficciones”, by J-L. Borges, third edition with page 23 missing.

(xx) “Die Gottardbahn in kommerzieller Beziehung”, by G. Koller, W. Schmidlin, and G. Stoll.

(xxi) “The etchings of the Master Rembrandt van Rijn, faithfully reproduced in the original size”, anonymous.

(xxii) “The memoirs of General S.I. Kemidov”, by Himself.

(xxiii) “Catalogue raisonné des œuvres d’Anton Fiddler”, by W.B. Appel.

(xxiv) “Zazie dans le métro”, by R. Queneau.

(xxv) “The mystery of the green Penguin”, by E. Mount.

(xxvi) “Χοηφόροι” (The Libation Bearers), by Aeschylus; an edition printed in Amsterdam in 1648.

(xxvii) “The Saga of Harald the Unconsoled”, Anonymous, translated from the Old Norse by W.B. Appel.

(xxviii) “Uncle Fred in the Springtime”, by P.G. Wodehouse.

(xxix) “The Tempest”, by W. Shakespeare.

(xxx) “The 1926 Zürich International Checkers Tournament, containing all games transcribed and annotated according to a new system”, by S. Higgs.

(xxxi) “A day at the Oval”, by G.H. Hardy.

(xxxii) “Harmonices Mundi”, by J. Kepler, initialed I.N on the second page.

(xxxiii) “Stories of cats and gulls”, by G. Lagaffe.

(xxxiv) “Traité sur la possibilité d’une monarchie générale en Italie”, by N. Faria; loose handwritten manuscript on silk.

(xxxv) “Broke Down Engine”, 78 rpm LP record, interpreted by Blind Willie McTell.

(xxxvi) “Les plages de France, Belgique et Hollande”, by A. Unepierre.

(xxxvii) “La Légende du Cochon Voleur et de l’Oiseau Rageur”, traditional folktale, translated from the Arabic by P. Teilhard de Chardin.

(xxxviii) “Discours des Girondins”, collected and transcribed by a parliamentary committee under the auspices of the “Veuves de la révolution française”, published by Van-den-Broeck, Bruxelles in 1862.

January 29th, 2015 at 4:00 pm