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

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

Offset: 1

Author

José María Grau Ribas, Apr 07 2012

Keywords

• nonn
• mult

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]

Examples

			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.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000 (first 1000 terms from Joerg Arndt)

Crossrefs

Cf. A060968 (order of SO(2,Z_n)), A060594, A235863, A001221, A209411.

Programs

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}]

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

Formula

From Jianing Song, Nov 05 2019: (Start)

a(n) = A060968(n) * A060594(n).

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)

Extensions

Terms beyond a(22) from Joerg Arndt, Apr 13 2012

a(1) changed to 1 by Andrey Zabolotskiy, Nov 13 2019