9
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 12, 2010 at 15:06
  • $\begingroup$ Yes Michael, this is correct $p_1$ is the smallest prime dividing $m$ and $\alpha_1$ is its exponent. $\endgroup$
    – Portland
    Feb 12, 2010 at 15:10
  • $\begingroup$ 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? $\endgroup$ Feb 12, 2010 at 15:23
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 12, 2010 at 19:11
  • 1
    $\begingroup$ Obviously we have $f(n)\geqslant a(n)$. We can also show that $\lim_{n\to \infty}\frac{f(n)}{a(n)}= + \infty$ (that's not obvious at all). $\endgroup$
    – Portland
    Feb 12, 2010 at 20:02

2 Answers 2

5
$\begingroup$

See MR1655470 (99m:20111) on MathSciNet.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Portland
    Feb 12, 2010 at 15:53
  • $\begingroup$ Are you sure the switch from $\phi$ to $\boldsymbol{\Phi}$ is justified? That sounds fishhy to me. $\endgroup$
    – Ben Webster
    Feb 12, 2010 at 16:04
  • $\begingroup$ $\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. $\endgroup$ Feb 12, 2010 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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