OFFSET
1,2
COMMENTS
Number of matrices M = [a,b;c,d] with 0 <= a,b,c,d < n such that M*transpose(M) == [1,0;0,1] (mod n).
From Jianing Song, Nov 05 2019: (Start)
Elements in O(2,Z_n) are of the form [x,y;-ty,tx], where x^2+y^2 == 1 (mod n), t^2 == 1 (mod n). Proof: If n = Product_{i=1..k} (p_i)^(e_i), then it can be shown by the Chinese Remainder Theorem that O(2,Z_n) is isomorphic to Product_{i=1..k} O(2,Z_(p_i)^(e_i)), so we can just study the elements in O(2,Z_p^e).
Let M = [x,y;z,w] be such a matrix; according to the conditions we have x^2+y^2 == z^2+w^2 == 1 (mod p^e), x*z+y*w == 0 (mod p^e). Here at least one of x,y is coprime to p^e, otherwise x^2+y^2 cannot be congruent to 1 mod p^e. If gcd(x,p^e) = 1, let t = x^(-1)*w; if gcd(y,p^e) = 1, let t = -y^(-1)*z (if gcd(x,p^e) = gcd(y,p^e) = 1 then these two t's are the same), then M = [x,y;-ty,tx] with determinant t, so t^2 == 1 (mod p^e). Specially, the elements in SO(2,Z_n) are of the form [x,y;-y,x], as the determinant is restricted to 1 mod n. See also A060968.
Note that O(2,Z_n) is non-abelian when n > 2: [0,1;-1,0] * [-1,0;0,1] = [0,1;1,0], but [-1,0;0,1] * [0,1;-1,0] = [0,-1;-1,0].
In general, let R be any commutative ring with unity, O(m,R) be the group of m X m matrices M over R such that M*M^T = I and SO(m,R) be the group of m X m matrices M over R such that M*M^T = I and det(M) = 1, then O(m,R)/SO(m,R) is isomorphic to {square roots of unity in R*}, where R* is the multiplicative group of R. This is because if we define f(M) = det(M) for M in O(m,R), then f is a surjective homomorphism from O(m,R) to {square roots of unity in R*}, and SO(m,R) is its kernel. Here, O(2,Z_n) is the internal semiproduct of SO(2,Z_n) and {[a,0;0,1]: a^2 = 1}. As a result:
If p is an odd prime or p^e = 4, then O(2,Z_p^e) is the internal semiproduct of SO(2,Z_p^e) and {I, P}, where I = [1,0;0,1] and P = [-1,0;0,1]. For any M in SO(2,Z_p^e), we have P*M*P = M^(-1). For odd primes p, O(2,Z_p^e) is, in fact, isomorphic to the dihedral group D_(2*(p+1)*p^(e-1)) if p == 3 (mod 4) and D_(2*(p-1)*p^(e-1)) if p == 1 (mod 4), since SO(2,Z_p^e) is cyclic as discussed in A060968. O(2,Z_4) is isomorphic to D_8 X C_2.
If e >= 3, then O(2,Z_2^e) is the internal semiproduct of SO(2,Z_2^e) and {I, P, Q, P*Q}, where I = [1,0;0,1], P = [-1,0;0,1] and Q = [2^(e-1)+1,0;0,1]. For any M in SO(2,Z_2^e), we have P*M*P = M^(-1); Q*M*Q = M if the upper-right entry of M is even, (2^(e-1)+1)*M otherwise.
The exponent of O(2,Z_n) (i.e., least e > 0 such that M^e = I for every M in O(2,Z_n)) is given by A235863(n).
The rank of O(2,Z_n) (i.e., the minimum number of generators) is 2*omega(n) if n is odd, 2*omega(n)-1 if n is even but not divisible by 4, 2*omega(n)+1 if n is divisible by 4 but not by 8 and 2*omega(n)+3 if n is divisible by 8, omega = A001221.
(End) [Comment partly rewritten by Jianing Song, Oct 09 2020]
LINKS
Jianing Song, Table of n, a(n) for n = 1..10000 (first 1000 terms from Joerg Arndt)
FORMULA
From Jianing Song, Nov 05 2019: (Start)
Multiplicative with a(2) = 2, a(4) = 16, a(2^e) = 2^(e+3) for e >= 3; a(p^e) = 2*(p-1)*p^(e-1) if p == 1 (mod 4), 2*(p+1)*p^(e-1) if p == 3 (mod 4).
(End)
EXAMPLE
a(1) = 1 because 1 = 0 in the zero ring, so although there only exists the zero matrix, it still equals the unit matrix.
O(2,Z_6) = {[0,1;5,0], [0,1;1,0], [0,5;1,0], [0,5;5,0], [1,0;0,1], [1,0;0,5], [2,3;3,2], [2,3;3,4], [3,2;4,3], [3,2;2,3], [3,4;2,3], [3,4;4,3], [4,3;3,4], [4,3;3,2], [5,0;0,5], [5,0;0,1]}, so a(6) = 16.
For n = 16, SO(2,Z_16) is generated by [9,0;0,9], [0,1;-1,0], and [4,1;-1,4] (see Jianing Song link in A060968), so O(2,Z_16) is generated by [-1,0;0,1], [9,0;0,1], [9,0;0,9], [0,1;-1,0], and [4,1;-1,4], which gives O(2,Z_16) is isomorphic to the semiproduct of C_2 X C_4 X C_4 and C_2 X C_2, so a(16) = 128.
MATHEMATICA
gg[n_]:=gg[n]=Flatten[Table[{{x, y}, {z, t}}, {x, n}, {y, n}, {t, n}, {z, n}], 3];
orto[1]=1;
orto[n_]:=orto[n]=Length@gg[n][[Select[Range[Length[gg[n]]], Mod[gg[n][[#]].Transpose[gg[n][[#]]], n]=={{1, 0}, {0, 1}}&]]];
Table[Print[orto[n]]; orto[n], {n, 1, 22}]
PROG
(PARI)
a(n)=
{
my(r=1, f=factor(n));
for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
if(p==2 && e==1, r*=2);
if(p==2 && e==2, r*=16);
if(p==2 && e>=3, r*=2^(e+3));
if(p%4==1, r*=2*(p-1)*p^(e-1));
if(p%4==3, r*=2*(p+1)*p^(e-1));
);
return(r);
}
\\ Jianing Song, Nov 05 2019
CROSSREFS
KEYWORD
nonn,mult
AUTHOR
José María Grau Ribas, Apr 07 2012
EXTENSIONS
Terms beyond a(22) from Joerg Arndt, Apr 13 2012
a(1) changed to 1 by Andrey Zabolotskiy, Nov 13 2019
STATUS
approved