I'm trying to gain some intuition here. Suppose we have the group $\mathbb{Z}_{n}$ (with the operation being addition modulo $n$). What is the median order of an element of this group when $n$ is a randomly chosen large number? I realize that when $n$ is prime, the median order will be $n$, because all elements other than the identity have order $n$. Also, are there any special values of $n$ that make the median order very small relative to $n$ (say $O(\log n)$)?

If this sounds vague, here is a more concrete explanation of my question: Given a number $n$, let $\alpha(n)$ denote the median order of all elements of the group $\mathbb{Z}_n$. Are there any special values of $n$ (say, $m!$ or $p^m$ for a prime $p$, or something like that) for which $\alpha(n)$ is very small compared to $n$? What if $n$ is a randomly chosen large number? What would you expect the value of $\alpha(n)$ to be? Would it be of the order of $n$?


The key fact, which is worth verifying yourself, is that there are exactly $\phi(d)$ elements of order $d$ in $\Bbb Z_n$ for every $d$ dividing $n$. (Here, $\phi$ is the Euler phi function.)

This allows us to say a lot about questions like this. For example, the mean order is exactly $\frac1n \sum_{d\mid n} d\phi(d)$, which is clearly greater than $\phi(n)$ (just the $d=n$ term alone is that big); one can show that this mean order is also at most $\frac{\pi^2}6\phi(n)$.

Suppose that $M$ is the median order of elements in $\Bbb Z_n$. Then the number of elements of order at most $M$ is at least $n/2$; but by the above, it's also at most $$ \sum_{d\le M} \phi(d) \sim \frac3{\pi^2} M^2 $$ by a classical result about the summatory function of the Euler phi function. Therefore we must have $$ M \gtrsim \sqrt{\frac{\pi^2}6n}; $$ in particular, $M=O(\log n)$ isn't possible.

Note that there's a lot of waste in that argument, because it's impossible for all the numbers up to $\sqrt n$ to divide $n$. So there's definitely room for improvement. I suspect that the median order is not $O(n^{1-\epsilon})$ for any $\epsilon>0$.

On the other hand, if the median order is $n/K$, then there are only $K$ possible divisors of $n$ greater than or equal to $n/K$, and the Euler phi function applied to each such divisor is at most $\phi(n)$ (since $\phi(d) \mid \phi(n)$ when $d\mid n$). Therefore the number of elements of order at least $n/K$ is at most $K\phi(n)$, while it must be at least $n/2$. Therefore the median order $M=n/K$ also satisfies $$ M \le 2\phi(n). $$ In particular, there are infinitely many integers $n$ such that $M \lesssim 2e^{-\gamma}n/\log\log n$, by a classical result about the maximal order of $n/\phi(n)$ (here $\gamma$ is Euler's constant). I suspect this is reasonably close to the truth - perhaps the right minimal order for the median is something like $n/(\log n)^A$ for some constant $A$.

One more comment: the median order can be smaller than $\phi(n)$ by an arbitrary factor. If $n$ is the product of all the primes between $z$ and $z^{2/(1-2\epsilon)}$, then $\phi(n)/n \sim \frac12-\epsilon$, which means that the median order is strictly smaller than $n$; however, the largest proper divisor of $n$ is $n/z$, so the median order is smaller than $\phi(n)$ by a factor of nearly $z/2$. In fact, since $\log n \sim z^{2/(1-2\epsilon)}$ in this construction, this gives examples where the median order is at most $n/(\log n)^{1/2-\epsilon}$. (And the $\epsilon$ could easily be made quantitative here.)


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.