cp's OEIS Frontend

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

%I A182039 #49 Apr 20 2024 23:50:34
%S A182039 1,2,8,16,8,16,16,64,24,16,24,128,24,32,64,128,32,48,40,128,128,48,48,
%T A182039 512,40,48,72,256,56,128,64,256,192,64,128,384,72,80,192,512,80,256,
%U A182039 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
%N A182039 Order of the group O(2,Z_n); number of orthogonal 2 X 2 matrices over the ring Z/nZ.
%C A182039 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).
%C A182039 From _Jianing Song_, Nov 05 2019: (Start)
%C A182039 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).
%C A182039 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.
%C A182039 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].
%C A182039 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:
%C A182039 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.
%C A182039 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.
%C A182039 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).
%C A182039 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.
%C A182039 (End) [Comment partly rewritten by _Jianing Song_, Oct 09 2020]
%H A182039 Jianing Song, <a href="/A182039/b182039.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Joerg Arndt)
%F A182039 From _Jianing Song_, Nov 05 2019: (Start)
%F A182039 a(n) = A060968(n) * A060594(n).
%F A182039 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).
%F A182039 (End)
%e A182039 a(1) = 1 because 1 = 0 in the zero ring, so although there only exists the zero matrix, it still equals the unit matrix.
%e A182039 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.
%e A182039 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.
%t A182039 gg[n_]:=gg[n]=Flatten[Table[{{x,y},{z,t}},{x,n},{y,n},{t,n},{z,n}],3];
%t A182039 orto[1]=1;
%t A182039 orto[n_]:=orto[n]=Length@gg[n][[Select[Range[Length[gg[n]]],Mod[gg[n][[#]].Transpose[gg[n][[#]]],n]=={{1,0},{0,1}}&]]];
%t A182039 Table[Print[orto[n]];orto[n],{n,1,22}]
%o A182039 (PARI)
%o A182039 a(n)=
%o A182039 {
%o A182039     my(r=1, f=factor(n));
%o A182039     for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
%o A182039         if(p==2 && e==1, r*=2);
%o A182039         if(p==2 && e==2, r*=16);
%o A182039         if(p==2 && e>=3, r*=2^(e+3));
%o A182039         if(p%4==1, r*=2*(p-1)*p^(e-1));
%o A182039         if(p%4==3, r*=2*(p+1)*p^(e-1));
%o A182039     );
%o A182039     return(r);
%o A182039 }
%o A182039 \\ _Jianing Song_, Nov 05 2019
%Y A182039 Cf. A060968 (order of SO(2,Z_n)), A060594, A235863, A001221, A209411.
%K A182039 nonn,mult
%O A182039 1,2
%A A182039 _José María Grau Ribas_, Apr 07 2012
%E A182039 Terms beyond a(22) from _Joerg Arndt_, Apr 13 2012
%E A182039 a(1) changed to 1 by _Andrey Zabolotskiy_, Nov 13 2019