Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We know that every group $G$ of order $n$ can be embedded into $\mathrm{GL}_n(\mathbb{Z})$, because

  • $G \hookrightarrow S_n$ (Cayley theorem)
  • $S_n\hookrightarrow \mathrm{GL}_n(\mathbb{Z})$ (via permutation matrices)

Furthermore we can show that $S_n \hookrightarrow \mathrm{GL}_{n-1}(\mathbb{Z})$, but we can't improve Cayley's theorem in general (i.e. we don't have $G \hookrightarrow S_{n-1}$).

For $n>2$, let $k(n)$ the smallest integer $k$ such that all groups of order $n$ can be embedded in $\mathrm{GL}_{k}(\mathbb{Z})$. We can show easily that $k(4)=2$, $k(5)=4$, $k(6)=2$. From the initial remark we have $k(n)\leqslant n-1$. Let $u_n=\frac{k(n)}{n}$. What can we say about $u_n$ ? It seems hard to fully determine $u_n$. For instance:

  • Can one extract a subsequence $u_{\varphi(n)}$, such that $\lim_{n\to \infty}u_{\varphi(n)} =1$?
  • Or even stronger: is there infinitely many $n$ such that $k(n)=n-1$?
  • What are the accumulation points of $u_n$?
  • etc
share|improve this question
    
A lower bound for $k$ is A152455 "the minimal integer $m$ such that there exists an $m\times m$ integer matrix of order $n$". It coincides with your $k(i)$ at least up to $6$. –  Henning Makholm Oct 8 '11 at 15:47
    
Another (probably completely random) observation is that A062170 "maximum value of factorials mod $n$" also coincides with your $k$ values and also appears to stay above A152455 for the dozen-or-so $n$s above 6 I checked. –  Henning Makholm Oct 8 '11 at 15:54
    
Minkowski considered the question of the largest finite subgroup of ${\rm GL}_n({\mathbf Z})$, which is related to your question. Do a web search on Minkowski and subgroup of GL(n,Z). –  KCd Oct 8 '11 at 17:03
    
KCd, thanks. I know this question by Minkowski, one form of which was solved by Feit in 1996. Not sure we can deduce answers to some of my questions though. –  Nathan Portland Oct 8 '11 at 17:43
    
How $S_n$ can be embedded in $GL(n-1,\mathbb{Z})$? can we take any field $F$ instead of $\mathbb{Z}$? –  Marshal Kurosh Oct 14 '11 at 5:28

2 Answers 2

up vote 4 down vote accepted

For n ≤ 100, k is exactly equal to oeis:A152455, and I think it would have been reasonable to conjecture it always holds, but it would have been quite wrong.

The group of order 144 with id 114 (an "almost double cover" of AGL(1,9), the unique non-split downward extension of AGL(1,9) by a normal subgroup of order 2) has minimum rational degree 16, but the cyclic group has minimum rational degree 14. Similarly, the almost double cover of AGL(1,25) has minimum rational degree 32 compared to the cyclic group of the same order with minimum rational degree 30; 2.AGL(1,49) has 64 instead of 60; 2.AGL(1,81) has 96 instead of 74; 2.AGL(1,121) has 128 instead of 124; 2.AGL(1,169) has 176 instead of 172. 2.AGL(1,9) has been checked carefully, the others need Schur indices checked, but I suspect the infinite family should follow from a single proof.

Certainly as in Derek Holt's answer, one can compute the minimum dimension of a faithful integral representation of a cyclic group as an additive version of the Euler phi function. That is, Derek's answer holds for prime powers as k( pe ) ≥ (p−1)pe−1, and using rational canonical form, shows that this lower bound for k is additive on relatively-prime prime powers.

Since this grows fairly quickly, it seems that it is also often an upper bound for the minimum dimension of a faithful integral representation of any group of order n. I just checked the character tables (with Schur indices) to verify the bound for n ≤ 143, but there is a group of order 144 that is a counterexample. There are no other counterexamples up to order n ≤ 200 (but another counterexample of order 1200).

There are some integers n such that every group of order n is cyclic, and so where we have exactly computed k, not just a lower bound. As Derek mentioned, taking n prime shows 1 is an accumulation point of un. Taking a product of i distinct primes such that no prime divides the Euler phi function of the rest, one gets an n with un ≈ (ip)/(pi) → 0, as i increases. In particular, 0 is an accumulation point of un as n varies over:

3,
3⋅5,
3⋅5⋅17,
3⋅5⋅17⋅23,
3⋅5⋅17⋅23⋅29,
3⋅5⋅17⋅23⋅29⋅53,
3⋅5⋅17⋅23⋅29⋅53⋅83,
3⋅5⋅17⋅23⋅29⋅53⋅83⋅89, …

with the last displayed value of n having 0.000000004 as its value of un.

share|improve this answer
    
Thanks a lot Jack. How do you know that "For n ≤ 100, k is exactly equal to oeis:A152455". It seems true for the few values I checked.What are "Schur indices"? –  Nathan Portland Oct 10 '11 at 0:34
    
@Nathan: I took the list of groups of order n, looked at their rational representations and found a faithful representation of degree less than or equal to that additive-euler-phi number. Schur indices measure the difference between having a representation whose traces are integral and having a representation whose matrix entries are integral. –  Jack Schmidt Oct 10 '11 at 2:11
    
Perhaps an even more obvious example is AGL(1,16) of order 3*5*16. The cyclic group of that order can be represented in degree 2+4+8=14, but the only non-linear character of AGL(1,16) has degree 15, so the minimal degree is 15. Similarly AGL(1,64) has degree 63 instead of 44; AGL(1,256) has degree 255 instead of 150. –  Jack Schmidt Oct 10 '11 at 7:44
    
Thanks again Jack. Some of this goes a bit beyond my current knowledge but that's perfect (because it seems "reachable") –  Nathan Portland Oct 13 '11 at 21:33
    
@Nathan: no problem. Feel free to ask questions, though midterms are going to make me a ghost next week. I would ignore my 2.AGL comments (AGL(1,2^n) is ok), since those are just first found, not best found. –  Jack Schmidt Oct 13 '11 at 22:15

If $n=p$ is prime, then $k(n)=n-1$. This follows from the fact that the minimal polynomial of a non-identity matrix of order $p$ must divide the cyclotomic polynomial $\Phi(p) = (x^p-1)/(x-1)$, which is irreducible over the integers.

share|improve this answer

Your Answer

 
discard

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.