MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


I know that $\mathrm{GL}(n,\mathbb{Z})$ has an element of order $m$ iff $\Phi(m)\leq n$, where $\Phi(m) = \varphi(m)$ if $p_1^{\alpha_1}\neq 2$ or $m=2$, $\Phi(m) = \varphi(m)-1$ if $p_1^{\alpha_1}= 2$ or $m\not=2$, and $\varphi$ is Euler totient.

From there I can show that the maximum order of a element of finite order in $\mathrm{GL}(n,\mathbb{Z})$, $f(n)$ statisfies $\displaystyle \lim_{n\to \infty} \frac{\ln f(n)}{\sqrt{n\ln n}} =1$.

Here is my question:

Can we find the asymptotic behavior of $f(n)$ (and not $\ln \bigl(f(n)\bigr)$)?

share|cite|improve this question
What's $p_1^{\alpha_1}$? My guess is that $p_1$ is the smallest prime dividing $m$ and $\alpha_1$ is its exponent. So $\Phi(m) = \phi(m) - 1$ if m is congruent to 2 mod 4, and $\Phi(m) = \phi(m)$ otherwise. – Michael Lugo Feb 12 '10 at 15:06
Yes Michael, this is correct $p_1$ is the smallest prime dividing $m$ and $\alpha_1$ is its exponent. – Portland Feb 12 '10 at 15:10
What is $\Phi(m)$ when $m$ is odd or a multiple of 4? Both branches of the definition seem to apply in these cases. And your result already is about asymptotic behaviour of $f(n)$. I suppose you want a better estimate? Can you indicate how good an estimate you need? – Harald Hanche-Olsen Feb 12 '10 at 15:23
He wants to estimate $f(n)$ to within a constant factor. The given estimate is much looser than that. – Greg Kuperberg Feb 12 '10 at 15:30
The symmetric group $S_n$ can be represented by the permutation matrices, so your $f(n)$ grows at least as fast as the maximal order $a(n)$ of a permutation of $n$ elements; it turns out that $\lim_{n \to \infty} \log a(n)/\sqrt{n \log n} = 1$ (see So another logical question is to ask how $a(n)$ and $f(n)$ are related. – Michael Lugo Feb 12 '10 at 19:11

See MR1655470 (99m:20111) on MathSciNet.

share|cite|improve this answer

From the fact you're citing, it looks like

$$ f(n) = \max \{ m : \Phi(m) \le n \}. $$

For example, $\Phi(30) = 7$ and $\Phi(m) \ge 11$ for all $m \ge 31$ (note that since $\phi(n) \ge \sqrt{n}$ we only need to check finitely many values!) -- so $f(7) = f(8) = f(9) = f(10) = 30$.

Now, consider the fact that $$ \lim \inf \phi(n) {\log \log n \over n} = e^{-\gamma} $$ which is equation (20) in this Mathworld article. Of course this holds if we replace $\phi$ by $\Phi$.

So $f(n)$ should grow like the inverse of the function $$ n \to {e^{-\gamma} n \over \log \log n} $$. It appears, then, that $f(n) \sim e^\gamma n \log \log n$ as $n \to \infty$.

Unfortunately this disagrees with your estimate. One of us is wrong somewhere.

EDIT: I believe my argument is basically right, but the original fact was stated incorrectly. From the paper of Levitt that Stanley pointed to, we should actually have

$$ \Phi( p_1^{\alpha_1} \cdots p_k^{\alpha_k}) = \phi(p_1^{\alpha_1}) + \cdots + \phi(p_k^{\alpha_k}) - [k \equiv 2 \mod 4] $$

and so $\Phi(x)$ is usually much smaller than $\phi(x)$ -- therefore $f$ grows much faster than I said it did.

share|cite|improve this answer
Thank you Michael, I think $\ln f(n) \sim \sqrt{n \ln n}$ is right, it appears in several articles, e.g. "On the Maximum Order of Torsion Elements in GL(n, Z) and Aut(Fn)" by Gilbert Levitt and Jean-Louis Nicolas – Portland Feb 12 '10 at 15:53
Are you sure the switch from $\phi$ to $\boldsymbol{\Phi}$ is justified? That sounds fishhy to me. – Ben Webster Feb 12 '10 at 16:04
$\phi(n)$ and $\Phi(n)$ only differ by at most 1, so $\phi(n) (\log \log n)/n$ and $\Phi(n) (\log \log n)/n$ differ by only a vanishing amount for large $n$. I think the problem with my argument is something more serious. – Michael Lugo Feb 12 '10 at 18:10

Your Answer


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.