# Subgroups of $\Bbb Z_n$

Consider the cyclic group $\Bbb Z_n=\{1,2,\cdots n\}$ under addition modulo $n$ and for some non zero $a\in \{1,2,\cdots n-1\}$ let $\langle a\rangle=H\le \Bbb Z_n$ of order $q$. I wish to show that at most $\lceil q/2\rceil$ of the numbers in $H$ are in $\{1,2,\cdots \lceil n/2\rceil\}$ and the same holds for $\{\lceil n/2\rceil+1,\cdots n\}$.

Geometrically can I argue as follows: If $\Bbb Z_n$ is thought of as $n$th roots of unity lying on the unit circle then the points of $H$ starting from $1$ will be spaced by an angle of $2\pi/q$, i.e. will be equally spaced apart on the unit circle. So basically we have $q$ points equally spaced on a circle. Any diameter yields two segments each of which can contain at most $\lceil q/2\rceil$ of the points. A diameter contains $\lceil n/2 \rceil$ points of $\Bbb Z_n$.

I am not satisfied with the above argument (particularly the last two sentences). Can someone give a better proof?

Thanks.

-

Suppose that $\{1,\dots,\lceil n/2\rceil\}$ contains more than $\lceil q/2\rceil$ elements of $H$. Let $b_0<\ldots<b_{\lceil q/2\rceil}$ be elements of $H\cap\{1,\dots,\lceil n/2\rceil\}$. Then $b_{\lceil q/2\rceil}-b_0\le\lceil n/2\rceil-1$, so there is a $k<\lceil q/2\rceil$ such that $$b_{k+1}-b_k\le\frac{\lceil n/2\rceil-1}{\lceil q/2\rceil}\;.$$ If $2\mid q$, then $2\mid n$, and $$b_{k+1}-b_k\le\frac{n-2}q<\frac{n}q\;,$$ and if $2\not\mid q$, then $$b_{k+1}-b_k\le\frac2{q+1}\left(\left\lceil\frac{n}2\right\rceil-1\right)\le\frac2{q+1}\cdot\frac{n}2<\frac{n}q\;,$$ so in all cases we have some $k<\lceil q/2\rceil$ such that $b_{k+1}-b_k<\dfrac{n}q$.

There are integers $r$ and $s$ such that $b_k\equiv ra\pmod n$ and $b_{k+1}\equiv sa\pmod n$. But then $b_{k+1}-b_k\equiv(s-r)a\pmod n$, and therefore $b_{k+1}-b_k\in H$. But $q(b_{k+1}-b_k)<n$, so $b_{k+1}-b_k\notin H$. This contradiction shows that $\{1,\dots,\lceil n/2\rceil\}$ cannot contain more than $\lceil q/2\rceil$ of $H$, and a similar argument works for $\{\lceil n/2\rceil+1,\dots,n\}$.

-
Looks a lot more complicated than the answers Tobias and I gave. – Gerry Myerson Oct 12 '12 at 12:24
@Gerry: It is. But your answers are essentially just Shahab’s (perfectly nice) geometric argument in disguise, and since he wasn’t happy with that, I thought that I’d offer something significantly different. Besides, while it’s not nearly so elegant, I think that it offers a useful insight into why this is true. – Brian M. Scott Oct 12 '12 at 12:27

If $k\in H$ then also $-k\in H$, and if $k$ is in one of those two halves mentioned, then $-k$ is in the other. This gives you a map from the intersection of $H$ with one half to the intersection of $H$ with the other, which is a bijection, so the number of elements in each intersection is the same, so neither of them can have more than half as many elements as $H$.

-
What about $0$? It is only in one half. – Shahab Oct 12 '12 at 12:08
Yes, I guess my conclusion is not quite right, due to the way the roundings have been chosen, but the corrections are easy exercises. – Tobias Kildetoft Oct 12 '12 at 12:10

Pair each $b$ in $H$ with its additive inverse, $n-b$.

-
What shall I pair $0$ with? – Shahab Oct 12 '12 at 12:11
Doesn't matter, does it? You're only going for $[q/2]$, this pairing will get you that however you handle zero. – Gerry Myerson Oct 12 '12 at 12:23