Finite subgroup of $Gl(n,\mathbb Z)$ and congruences - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T21:14:14Z http://mathoverflow.net/feeds/question/74370 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74370/finite-subgroup-of-gln-mathbb-z-and-congruences Finite subgroup of $Gl(n,\mathbb Z)$ and congruences Wox 2011-09-02T15:55:14Z 2011-09-10T01:04:26Z <p>Suppose we have an invertible matrix q in a finite subgroup $Q$ of $Gl(n,\mathbb Z)$, the group of all invertible integer matrices. Now I want to find all $x\; mod\; \mathbb Z^n$ for which</p> <p>$(q+q^2+q^3+...+q^m).x = 0\quad mod\; \mathbb Z^n$</p> <p>where $m$ is the order of $q$ in the finite subgroup $Q$ of $Gl(n,\mathbb Z)$ so that $q^m=1$. I tried using the Smith normal form so that</p> <p>$(q+q^2+q^3+...+q^m) = U.D.V$</p> <p>where $U,V$ in $Gl(n,\mathbb Z)$ and $D$ the Smith normal form, so we have to solve</p> <p>$D.V.x=0\quad mod\; \mathbb Z^n$</p> <p>Since $D.V$ is diagonal, $x$ must have rational components unless the diagonal element is zero. Now my question is, what is the maximal denominator of the components in $x$ ? So what is the maximal absolute value in $D.V$ ?I think this must be $m$, but I can't figure out why.</p> <p><strong>Edit:</strong> Let me clarify why I expect x to be rational with an upper bound on the denominator. Suppose G is a subgroup of the Euclidean Group with isometries (t,q) as elements (t: translational part, q: linear part). The subgroup T which contains all isometries in G with trivial linear part is a normal subgroup of G. Suppose now that T can be identified with a $\mathbb Z$-lattice in $\mathbb R^n$, then G/T is isomorph with a finite subgroup Q of $GL(n,\mathbb Z)$. Crystallographers call G a space group and Q a point group.</p> <p>There are only finite many conjugacy classes of finite subgroups in $GL(n,\mathbb Z)$, so there are only finite many point groups up to conjugacy in $GL(n,\mathbb Z)$. Now I want to understand why from this finite number of point groups, a finite number of (non-equivalent) space groups can be deduced. If we write G as the union of cosets of T</p> <p>$G=\bigcup_{i=1}^{|Q|}(t_{qi},q_{i})T$</p> <p>we see that (composition of two isometries and q belongs to exactly one coset)</p> <p>$t_{q_1.q_2}=t_{q_1}+q_1.t_{q_2} \quad mod\ \mathbb Z^n$</p> <p>So we know that $t_{q}$ is a real vector $0\leq t_{q}&lt;1$. Using the previous property we also find that (m order of q)</p> <p>$(t_{q},q)^{m}=(q^{1}\cdot t_{q}+\cdots+q^{m}\cdot t_{q},q^m)\in (0,id)T$</p> <p>$\Leftrightarrow (q^{1}+\cdots+q^{m})\cdot t_{q}=0\quad mod\ \mathbb{Z}^{n}$</p> <p>If an appropriate origin is chosen in Euclidean space, $t_{q}$ should be rational with maximal denominator $m$. Maybe investigating $(t_{q},q)^{m}$ is not the best way to find bounds on $t_{q}$?</p> http://mathoverflow.net/questions/74370/finite-subgroup-of-gln-mathbb-z-and-congruences/74404#74404 Answer by Ralph for Finite subgroup of $Gl(n,\mathbb Z)$ and congruences Ralph 2011-09-02T22:43:08Z 2011-09-04T13:01:24Z <p><strong>Edit:</strong> I couldn't resist my predilection for generalizations: Using darij grinberg's simplification, the proof below shows: </p> <p>Let $k$ be a field, $q \in GL_n(k)$ a matrix of finite exponent $m$ with char$(k) \nmid m$ and $M \subseteq k^n$. Futhermore, let $E$ be the eigenspace of $q$ corresponding to the eigenvalue $1$ and let $U \le k^n$ be the space spanned by the columns of $1-q$. Then the following is true for $A := 1+q+\dots + q^{m-1}$: </p> <blockquote> <ul> <li>$\lbrace x \in k^n \mid Ax \in M \rbrace = U + \frac{1}{m}(E \cap M)$</li> <li>$U$ and $(1/m)(E \cap M)$ intersect in $0$ iff $0 \in M$, otherwise the intersection is empty</li> <li>$A$ is diagonizable with diagonal $(m,...,m,0,...,0)$ where the number of m's equals $\dim E$</li> </ul> </blockquote> <hr> <p><em>(Older formulation)</em> </p> <p>Let $E \le \mathbb{C}^n$ be the eigenspace of $1$ of the matrix $q$ and let $U \le \mathbb{C}^n$ be the space spanned by the columns of $1-q$. </p> <p>Set $A := 1+q+\dots + q^{m-1}$ and $X:= \lbrace x \in \mathbb{C}^n \mid A\cdot x \in \mathbb{Z}^n \rbrace$ and $L := E \cap \mathbb{Z}^n$. </p> <p>Then the following holds: </p> <blockquote> <p>$X = U \oplus \frac{1}{m}L$.</p> </blockquote> <p><em>Proof</em>: Assume $\dim E = d$. Then $\dim U = \text{rank}(1-q) = n-d$. </p> <p>Since each $x \in E$ satisfies $Ax = mx$, $E$ contains eigenvectors from $A$ of the eigenvalue $m$. From $A \cdot (1-q) = 0$ it follows that $U$ consists of eigenvectors of $A$ of the eigenvalue $0$. Hence $E \cap U = 0$ and for dimensional reasons $$\mathbb{C}^n = U \oplus E.$$ Since $q$ has integral entries, it's possible to chosse a basis of $E$ in $\mathbb{Q}^n$ and by multiplying with a suitable integer it's also possible to choose a basis in $\mathbb{Z}^n$. Therefore $L = E \cap \mathbb{Z}^n$ is a lattice of rank $d$. Let $\lbrace e_1, \dots, e_d \rbrace$ be a basis of $L$. Let $x \in X$ and write $$x = u + \sum_i \alpha_i e_i \text{ with } \alpha_i \in \mathbb{C}.$$ Then $Ax = \sum_i m\alpha_i e_i \in \mathbb{Z}^n$ and $q(Ax) = Ax$. It follows $Ax \in E \cap \mathbb{Z}^n = L = \oplus_i \mathbb{Z}e_i$ and therefore $m\alpha_i \in \mathbb{Z}$. This shows $X \subseteq U \oplus (1/m)L$. The converse inclusion is obvious. <em>qed</em>. </p> <p><strong>Edit:</strong> Also note that the image of $A$ is given by $$Y := \lbrace Ax \mid x \in X \rbrace = L.$$</p> http://mathoverflow.net/questions/74370/finite-subgroup-of-gln-mathbb-z-and-congruences/74765#74765 Answer by Wox for Finite subgroup of $Gl(n,\mathbb Z)$ and congruences Wox 2011-09-07T15:56:07Z 2011-09-08T17:21:38Z <p><strong>Edit: This is a secondary question on how Ralph's solution can be simplified by choosing an appropriate origin in Euclidean space.</strong></p> <p>Ralph's solution to my original question, in the context of space groups, states that an isometry $(x,q)$ in a space group $G$ with linear part $q\in Q&lt; GL(Z^n)$, must have a translational part x for which </p> <p>$X_q=\lbrace x\in\mathbb R^n: (q^{1}+\cdots+q^{m})\cdot x\in \mathbb Z^n\rbrace =Col(q-1)+\frac{1}{m}(Null(q-1)\cap \mathbb Z^n)$</p> <p>Note first that from the composition of isometries we find that</p> <p>$(t_1,q_1)(t_2,q_2)=(t_1+q_1\cdot t_2,q_1\cdot q_2)$</p> <p>$\Leftrightarrow X_{q_{1}\cdot q_{2}}=X_{q_{1}}+(q_{1}-1)\cdot X_{q_{2}}$</p> <p>This means that we must only consider the $X_q$ for the generators of the finite group $Q&lt; GL(Z^n)$ (i.e. the point group).</p> <p>After a shift of origin in Euclidean space, i.e. an affine transformation $(v,1)$ with $v\in \mathbb R^n$, we can write that</p> <p>$X_q'=Col(q-1)+\frac{1}{m}(Null(q-1)\cap \mathbb Z^n)+(q-1)\cdot v$</p> <p>Since $(q-1)\cdot v\in Col(q-1)$, we can find for every $u\in Col(q-1)$ a vector $v\in \mathbb R^n$ for which $(q-1)\cdot v=-u$. Thus for a proper choice of origin we can write for a generator q</p> <p>$X_q=\frac{1}{m}(Null(q-1)\cap \mathbb Z^n)$</p> <p>so that $t_q = X_q\ mod\ \mathbb Z^n$ is a rational number with maximal denominator $|Q|$ (which is the maximal possible m). The question is now, can we find one $v\in \mathbb R^n$ so that this simplification can be done for all $X_q$? For this, the column spaces $Col(q-1)$ for generators q of Q should be linear independent. If we call $S$ the generating set of Q, then this can be expressed as</p> <p>$\forall q,p\in S: Col(q-1)\cap Col(p-1)=\lbrace 0 \rbrace$</p> <p>Is this true?</p> http://mathoverflow.net/questions/74370/finite-subgroup-of-gln-mathbb-z-and-congruences/75058#75058 Answer by Ralph for Finite subgroup of $Gl(n,\mathbb Z)$ and congruences Ralph 2011-09-10T01:04:26Z 2011-09-10T01:04:26Z <p>That's an answer/comment to the secondary question. </p> <p>I don't know, if the result can be derived from the finiteness of the matrix $q$ alone (it seems to me that you don't explore the fact that a space group consists of isometries). There is another point that makes me wonder: At the begining you are considering an isometry $(x,q)$ with $q \in GL(n,\mathbb{Z})$. But then $q \in GL(n,\mathbb{Z}) \cap O_n =P$, the group of permutation matrices with signed entries. Aren't there space groups, those rotational parts form larger groups than $P$ ? </p> <p>That said, I was looking in the internet and found a paper (<a href="http://www.unige.ch/math/folks/bucher/Affine/pdfAffine/BuserBieberbach.pdf" rel="nofollow">link</a>), having a proof (section 5) that is somewhat related to your approach in the Edit-part of the original question. </p> <p>The idea is roughly: Let $G$ be a space group with translation subgroup $T$ and let $L$ be the lattice correspnding to $T$. Choose a system of representatives $\lbrace q_1, ...,q_m \rbrace$ for $G/T$ and a basis $\lbrace b_1, ..., b_n \rbrace$ of $L$. Let $a_i$ be the translational part of $q_i$. By writing $a_i$ as linear combination of the $b_j$ it follows that $q_i$ can be choosen such that $|a_i| \le |b_1| + ... + |b_n| =: \alpha$ (Euklid-Norm). If $x_0 \in \mathbb{R}^n$ let $[x_0]$ denote translation by $x_0$. Then the following product can be expressed as </p> <p>$$q_i \circ q_j = [\sum_k l_{ijk}b_k] \circ q_{\eta(i,j)},\hspace{10pt} l_{ijk} \in \mathbb{Z},\quad \eta(i,j) \in \lbrace 1,...,m \rbrace \hspace{50pt} (\ast)$$ </p> <p>It's easy to see, that the group law of $G$ is uniquely determined by $(\ast)$. </p> <p>If $G'$ is another space group with $(G':T') = (G:T)$, repeat the same procedure and define a mapping $G \to G'$ by $q_i \to q'_i$, $b_j \to b_j'$. If $l_{ijk}' = l_{ijk}$ and $\eta(i,j)' = \eta(i,j)$ for all $i,j,k$, this is an isomorphism. Therefore there are only finitely many space groups $G$ for fixed $(G:T)$ (up to isomorphism), if it can be shown that there are only finitely many possible values for the $l_{ijk}$. </p> <p>If the rotational part of $q_i$ is the matrix $A_i \in O_n$, $(\ast)$ shows $$| \sum_k l_{ijk}b_k | = |a_i + A_ia_j-A_iA_j(A_{\eta(i,j)})^{-1} a_{\eta(i,j)}| \le |a_i| + |a_j| + |a_{\eta(i,j)}| \le 3\alpha$$</p> <p>Suppose $\lbrace b_1, ..., b_n\rbrace$ is an orthonormal base of $\mathbb{R}^n$. Then $\alpha = n$ and each $|l_{ijk}| \le 3n$ is bounded. Thus the result is shown in this case. In general, a similar estimate holds, but it's harder to establish (that's step 2 on page 144 that relies on lemmas 4.1, 4.2). </p> <p><strong>Remark:</strong> Using the theory of group extensions, the result follows easily from the finiteness of $H^2(Q; \mathbb{Z}^n)$ for finite groups $Q$. </p>