``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).

  • 1
    $\begingroup$ Should that be "integral" in the first line? $\endgroup$ 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$
    – ARupinski
    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
    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$ Dec 13, 2012 at 1:47
  • 1
    $\begingroup$ Faint heart never won fair theorem. $\endgroup$ Dec 13, 2012 at 22:58

2 Answers 2


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) ...


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.