# Maximum Order of elements in $GL(n,Z)$

Hi,

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)$)?

-
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 research.att.com/~njas/sequences/A000793). 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.

-

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.

-
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