

A182039


Order of the group O(2,Z_n); number of orthogonal 2 X 2 matrices over the ring Z/nZ.


5



1, 2, 8, 16, 8, 16, 16, 64, 24, 16, 24, 128, 24, 32, 64, 128, 32, 48, 40, 128, 128, 48, 48, 512, 40, 48, 72, 256, 56, 128, 64, 256, 192, 64, 128, 384, 72, 80, 192, 512, 80, 256, 88, 384, 192, 96, 96, 1024, 112, 80, 256, 384, 104, 144, 192, 1024, 320, 112, 120, 1024, 120, 128, 384, 512, 192, 384, 136, 512, 384, 256, 144, 1536
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 O(2,Z_n) = Product_{i=1..k} O(2,Z_(p_i)^(ei)), 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.
In general, let R be any commutative ring with unity, O(m,R) be the group of m X m matrices A over R such that A*A^T = E and SO(m,R) be the group of m X m matrices A over R such that A*A^T = E and det(A) = 1, then O(m,R)/SO(m,R) = {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) = SO(2,Z_n) X {square roots of unity in (Z_n)*}. As a result:
If p is an odd prime, then O(2,Z_p^e) is isomorphic to C_2 X C_((p+1)*p^(e1)) if p == 3 (mod 4) and C_2 X ((p1)*p^(e1)) if p == 3 (mod 4), where the generators are [1,0;0,1] along with the generator of SO(2,Z_p^e) shown in A060968;
If p = 2, then O(2,Z_p^e) is isomorphic to C_2 if e = 1, C_2 X C_2 X C_4 if e = 2, C_2 X C_2 X C_2 X C_4 X C_(2^(e2)) if e >= 3, where the generators are [1,0;0,1], [2^(n1)+1,0;0,1] along with the generators of SO(2,Z_2^e) shown in A060968 if e >= 3.
The exponent of O(2,Z_n) (i.e., least e > 0 such that x^e = E for every x 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 is n is divisible by 8, omega = A001221.
The smallest n divisible by 8 such that rank(O(2,Z_n)) < rank(O(2,Z_(n+1))) is n = 1784: O(2,Z_1784) = C_2 X C_2 X C_2 X C_2 X C_2 X C_4 X C_224, while O(2,Z_1785) = C_2 X C_2 X C_2 X C_2 X C_4 X C_4 X C_8 X C_16. The smallest n divisible by 8 such that rank(O(2,Z_n)) < rank(O(2,Z_(n1))) is n = 256.
(End)


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)
a(n) = A060968(n) * A060594(n).
Multiplicative with a(2) = 1, a(4) = 16, a(2^e) = 2^(e+3) for e >= 3; a(p^e) = 2*(p1)*p^(e1) if p == 1 (mod 4), 2*(p+1)*p^(e1) 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) = C_2 X C_2 X C_2 X C_4 X C_4, 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*(p1)*p^(e1));
if(p%4==3, r*=2*(p+1)*p^(e1));
);
return(r);
}
\\ Jianing Song, Nov 05 2019


CROSSREFS

Cf. A060968 (order of SO(2,Z_n)), A060594, A235863, A001221, A209411.
Sequence in context: A167592 A094513 A110004 * A174882 A080095 A193219
Adjacent sequences: A182036 A182037 A182038 * A182040 A182041 A182042


KEYWORD

nonn,mult


AUTHOR

José María Grau Ribas, Apr 07 2012


EXTENSIONS

Terms beyond a(22) by Joerg Arndt, Apr 13 2012
a(1) changed to 1 by Andrey Zabolotskiy, Nov 13 2019


STATUS

approved



