login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)^(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.

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^(e-1)) if p == 3 (mod 4) and C_2 X ((p-1)*p^(e-1)) 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^(e-2)) if e >= 3, where the generators are [-1,0;0,1], [2^(n-1)+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_(n-1))) 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*(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) = 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*(p-1)*p^(e-1));

        if(p%4==3, r*=2*(p+1)*p^(e-1));

    );

    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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 5 21:00 EDT 2020. Contains 335473 sequences. (Running on oeis4.)