{"id":4558,"date":"2015-03-16T12:31:02","date_gmt":"2015-03-16T10:31:02","guid":{"rendered":"https:\/\/wpethzprd.ethz.ch\/kowalski\/?p=4558"},"modified":"2024-02-20T13:40:33","modified_gmt":"2024-02-20T11:40:33","slug":"a-parity-lemma-of-a-irving","status":"publish","type":"post","link":"https:\/\/blogs.ethz.ch\/kowalski\/2015\/03\/16\/a-parity-lemma-of-a-irving\/","title":{"rendered":"A parity lemma of A. Irving"},"content":{"rendered":"

In his recent work on the divisor function in arithmetic progressions to smooth moduli<\/a>, A. Irving proves the following rather amusing lemma (see Lemma 4.5 in his paper):<\/p>\n

\nLemma<\/b> 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
\n$latex h_I=\\sum_{i\\in I}{h_i},$
\nand for any $latex x\\in\\mathbf{F}_p$, let
\n$latex \\nu_h(x)=|\\{I\\subset \\{1,\\ldots, k\\}\\,\\mid\\, h_I=x\\}|$
\ndenote the multiplicity of $latex x$ among the $latex (h_I)$.
\nThen if none of the $latex h_i$ is zero, there exists some $latex x$ for which $latex \\nu_h(x)$ is odd<\/i>.\n<\/p><\/blockquote>\n

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.<\/p>\n

Irving’s proof.<\/b> 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
\n$latex N=\\prod_{i=1}^k(1+\\xi^{h_i})$
\nof the cyclotomic field $latex K_p=\\mathbf{Q}(\\xi)$. By expanding and using the assumption we see that
\n$latex N=\\sum_{x\\in\\mathbf{F}_p} \\nu_h(x)\\xi^{x}\\in 2\\mathbf{Z}[\\xi].$
\nIn 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.<\/p>\n

A second proof.<\/b> 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.<\/p>\n

First we note that
\n$latex \\sum_{x\\in \\mathbf{F}_p} \\nu_h(x)=2^k$
\nis even. In particular, since $latex p$ is odd, there is at least some $latex x$ with $latex \\nu_h(x)$ even<\/i>.<\/p>\n

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.<\/p>\n

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
\n$latex \\nu_h(x)=\\nu_j(x)+\\nu_j(x-h_k),$
\nby counting separately those $latex I$ with sum $latex x$ which contain $latex k$ or not.<\/p>\n

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<\/i>, which we have seen is not the case… Hence we have a contradiction.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 … Continue reading A parity lemma of A. Irving<\/span><\/a><\/p>\n","protected":false},"author":625,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1086,2],"tags":[],"class_list":["post-4558","post","type-post","status-publish","format-standard","hentry","category-exercise","category-blogroll"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/4558","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/users\/625"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/comments?post=4558"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/4558\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/media?parent=4558"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/categories?post=4558"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/tags?post=4558"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}