1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ Looks a lot more complicated than the answers Tobias and I gave. $\endgroup$ – Gerry Myerson Oct 12 '12 at 12:24
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 12 '12 at 12:27
1
$\begingroup$

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

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

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.