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

Improve this question
$\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$
    – Michael Lugo
    Commented 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
    Commented 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$
    – Harald Hanche-Olsen
    Commented 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$
    – Michael Lugo
    Commented 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
    Commented Feb 12, 2010 at 20:02

2 Answers 2

Reset to default
5
$\begingroup$

See MR1655470 (99m:20111) on MathSciNet.

Improve this answer
$\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.

Improve this answer
$\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
    Commented 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 ♦
    Commented 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$
    – Michael Lugo
    Commented Feb 12, 2010 at 18:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .