# Embeddings of finite groups into $\mathrm{GL}_n(\mathbb{Z})$

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
• 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$. Oct 8, 2011 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. Oct 8, 2011 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, 2011 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. Oct 8, 2011 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}$? Oct 14, 2011 at 5:28

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.

• 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"? Oct 10, 2011 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. Oct 10, 2011 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. Oct 10, 2011 at 7:44
• Thanks again Jack. Some of this goes a bit beyond my current knowledge but that's perfect (because it seems "reachable") Oct 13, 2011 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. Oct 13, 2011 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.