Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
What about $0$? It is only in one half. –  Shahab Oct 12 '12 at 12:08
1  
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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