Media orden de un elemento en un grupo aditivo modulo $n$

Question

Estoy tratando de ganar algo de intuición aquí. Supongamos que tenemos el grupo de $\mathbb{Z}_{n}$ (con la operación adición módulo $n$). ¿Cuál es la mediana de la orden de un elemento de este grupo al $n$ es un escogido de forma aleatoria gran número? Me doy cuenta de que cuando $n$ es primo, la mediana de la orden será de $n$, debido a que todos los otros elementos que la identidad tiene el fin de $n$. También, hay valores especiales de $n$ que hacen que la mediana de orden muy pequeña en relación a $n$ (es decir $O(\log n)$)?

Si esto suena vago, aquí es más una explicación concreta a mi pregunta: Dado un número $n$, vamos a $\alpha(n)$ el valor de la mediana de la orden de todos los elementos del grupo $\mathbb{Z}_n$. Especiales existen valores de $n$ (es decir, $m!$ o $p^m$ primer $p$, o algo así) para que $\alpha(n)$ es muy pequeña en comparación con $n$? Lo que si $n$ es un escogido de forma aleatoria gran número? Lo que usted esperaría que el valor de $\alpha(n)$? Sería del orden de $n$?

Answer 1

El hecho clave, que es la pena comprobar usted mismo, es que no son exactamente $\phi(d)$ elementos de orden $d$ $\Bbb Z_n$ por cada $d$ dividiendo $n$. (Aquí, $\phi$ es la phi de Euler de la función.)

Esto nos permite decir mucho acerca de preguntas como esta. Por ejemplo, la orden es exactamente $\frac1n \sum_{d\mid n} d\phi(d)$, lo cual es claramente mayor que $\phi(n)$ (sólo el $d=n$ plazo solo es que los grandes); uno puede mostrar que esto significa el fin es también en la mayoría de las $\frac{\pi^2}6\phi(n)$.

Supongamos que $M$ es la mediana del orden de los elementos en $\Bbb Z_n$. A continuación, el número de elementos de orden en la mayoría de las $M$ al menos $n/2$; pero en el anterior, también en la mayoría de los $$ \sum_{d\le M} \phi(d) \sim \frac3{\pi^2} M^2 $$ por un clásico de resultados acerca de la summatory función de la phi de Euler de la función. Por lo tanto, debemos tener $$ M \gtrsim \sqrt{\frac{\pi^2}6n}; $$ en particular, $M=O(\log n)$ no es posible.

Tenga en cuenta que hay una gran cantidad de residuos en el argumento, porque es imposible que todos los números hasta el $\sqrt n$ brecha $n$. Así que definitivamente hay espacio para la mejora. Sospecho que la mediana de la orden no es $O(n^{1-\epsilon})$ cualquier $\epsilon>0$.

Por otro lado, si la mediana de la orden es $n/K$, entonces hay sólo $K$ posibles divisores de $n$ mayor que o igual a $n/K$, y el phi de Euler función a aplicar para cada divisor es en la mayoría de las $\phi(n)$ (desde $\phi(d) \mid \phi(n)$ al $d\mid n$). Por lo tanto el número de elementos de orden, al menos, $n/K$ es en la mayoría de las $K\phi(n)$, mientras que se debe tener al menos $n/2$. Por lo tanto, la mediana de la orden de $M=n/K$ también satisface $$ M \le 2\phi(n). $$ En particular, hay infinitamente muchos enteros $n$ tal que $M \lesssim 2e^{-\gamma}n/\log\log n$, por un clásico de resultados acerca de la máxima orden de $n/\phi(n)$ (aquí se $\gamma$ es la constante de Euler). Sospecho que esto es razonablemente cerca de la verdad - tal vez el derecho a un mínimo de orden para la mediana es algo como $n/(\log n)^A$ para algunas constantes $A$.

Uno de los más comentario: la mediana de la orden puede ser menor que $\phi(n)$ por un factor arbitrario. Si $n$ es el producto de todos los números primos entre $z$$z^{2/(1-2\epsilon)}$,$\phi(n)/n \sim \frac12-\epsilon$, lo que significa que la mediana de la orden es estrictamente menor que $n$; sin embargo, el mayor divisor adecuado de $n$$n/z$, por lo que la mediana de la orden es menor que $\phi(n)$ por un factor de casi $z/2$. De hecho, desde el $\log n \sim z^{2/(1-2\epsilon)}$ en esta construcción, esto da ejemplos en los que la mediana de la orden es en la mayoría de las $n/(\log n)^{1/2-\epsilon}$. (Y el $\epsilon$ podría hacerse fácilmente cuantitativa aquí.)