``everybody knows'' that an integral orthogonal matrix is a signed permutation matrix, so there are exactly $2^n n!$ such matrices in $O(n).$ Now, what if we ask for the enumeration of elements of $O(n$ with rational elements, where all the denominators are equal to $q$ (where $q$ is an arbitrary integer, though if the question is much easier for $q$ prime, that's fine too...)? I would suspect this has been studied... (one can ask the same question for arbitrary algebraic groups/number fields, of course).
$\begingroup$
$\endgroup$
10
asked Dec 13, 2012 at 0:54
-
1$\begingroup$ Should that be "integral" in the first line? $\endgroup$– Allen KnutsonCommented Dec 13, 2012 at 1:17
-
$\begingroup$ I would be surprised if there is as nice a closed as for $q=1$ form since this question is strongly related to finding the number of ways of writing $q^2$ as a sum of exactly $n$ integer squares; the functions describing these counts are not simple functions to describe. Furthermore, an easy enumeration would seem to be further hindered by the fact that these are not subgroups of $O(n)$ in general, only subsets except in a few special cases. But then again, maybe all these difficulties cancel out in some nice way. $\endgroup$– ARupinskiCommented Dec 13, 2012 at 1:30
-
$\begingroup$ Following Allen's comment, the rational orthogonal $2 \times 2$ matrices have a natural few-to-one correspondence with Pythagorean triples, and there are more than 8 of them. The power series enumerating $2 \times 2$ matrices with fixed denominator is the square of a Jacobi theta constant, and is a modular form of weight 1. $\endgroup$– S. Carnahan ♦Commented Dec 13, 2012 at 1:42
-
$\begingroup$ Except that for each orthogonal A, one gets many more representatives AB for each orthogonal B that has q=1. While finding sums of squares is important, I see enumerating tuples of orthogonal vectors given one fixed vector as the issue. If you have M such vectors, there wil be at most M choose n possibilities which will be cut way down through orthogonal relations. It would not surprise me if the choice for representatives A had cardinality O(M^sqrt(n)) asymptotically. Checking the combinatorics lierature on orthogonal designs may help. Gerhard "Then Again It Might Not" Paseman, 2012.12.12 $\endgroup$– Gerhard PasemanCommented Dec 13, 2012 at 1:47
-
1$\begingroup$ Faint heart never won fair theorem. $\endgroup$– Gerry MyersonCommented Dec 13, 2012 at 22:58
|
Show 5 more comments
2 Answers
$\begingroup$
$\endgroup$
Boris Venkov asked this question, once, in the coffea room of the Maths Department of the university of Geneva.
Here are some things that relate to the case $q=2^m$.
Let $I_n$ be the 'euclidean' $\mathbf Z$-module of rank $n$, and $A\mapsto G_n(A)$ the group it defines.
Let us write $a(n,m)$ for the number of matrices in $G_n(\mathbf Z[\frac{1}{2}])$ all of whose coordinates have $2$-valuation at least $-m$.
First note that $G_n(\mathbf Z[\frac{1}{2}])$ is finite for $n<5$.
In fact, one even has $G_n(\mathbf Z[\frac{1}{2}])=G_n(\mathbf Z)\simeq\mathbf Z/2^n\rtimes S_n$ for $n<4$ and $G_4(\mathbf Z[\frac{1}{2}])=Aut(D_4)=G_4(\mathbf Z)\rtimes \mathbf Z/3$, where $D_4$ denotes the sublattice of elements of even length in $I_4$. The $\mathbf Z/3$ is generated by
$$ \begin{bmatrix} -1/2 & 1/2 & 1/2 & 1/2\\\ -1/2 & 1/2 & -1/2 & -1/2\\\ -1/2 & -1/2 & 1/2 & -1/2\\\ -1/2 & -1/2 & -1/2 & 1/2 \end{bmatrix}$$
Thus in this case, you have $a(4,0)=384=2^7*3$ and $a(4,1)=1152=2^7*3^2$.
Next, note that $G_5(\mathbf Z[\frac{1}{2}])$ is an amalgamated sum : $A\star_C B$ with $A=G_5(\mathbf Z)$, $B=Aut(I_1)\times Aut(D_4)$ and $C=A\cap B\simeq \mathbf Z/2\times G_4(\mathbf Z)$.
This decomposition comes from the action of $G_5(\mathbf Z[\frac{1}{2}])$ on the Bruhat-Tits Building of $G_5(\mathbf Q_2)$ : a tree whose vertices are 5-valent and 3-valent.
The number $\frac{a(5,m)}{\vert G_5(\mathbf Z)\vert}$ counts the $5$-valent vertices that are at (combinatorial) distance less than $2m$ from a fixed one. Thus $\frac{a(5,m)}{\vert G_5(\mathbf Z)\vert}=10*\frac{8^m-1}{7}+1$.
Things are becoming more complicated in higher dimensions since the Bruhat-Tits building is not a tree anymore ($n\geq 6$) and the action of $G_n(\mathbf Z[\frac{1}{2}])$ on the vertices of a same type (say corresponding to unimodular lattices) is not transitive anymore ($n\geq 9$).
You may adapt the same method to obtain similar results for small values of $n$ and $q=p^m$ : the Bruhat-Tits building is a tree for $n=3$, the action of $G_3(\mathbf Z[\frac{1}{p}])$ is transitive on one type of vertices (but rarely on maximal simplices) ...
$\begingroup$
$\endgroup$
This is not a complete answer, but it's a start.
In the $2 \times 2$ case, the act of choosing the first column and clearing denominators describes a two-to-one map from orthogonal matrices to primitive vectors in the lattice $\mathbb{Z} \oplus \mathbb{Z}$. In particular, there are twice as many orthogonal matrices with denominator exactly $q^2$ as there are primitive vectors of length $q$, and there are twice as many orthogonal matrices with denominator dividing $q^2$ as there are vectors of length $q$. The latter quantity is enumerated by the theta function of the lattice, which is a modular form of weight 1, and its coefficients grow logarithmically.
In higher dimension, I guess the generating function comes from successively choosing vectors in orthogonal complements, so it should be at least related to modular forms.
answered Dec 13, 2012 at 4:23