A327924 Square array read by ascending antidiagonals: T(m,n) is the number of non-isomorphic groups G such that G is the semidirect product of C_m and C_n, where C_m is a normal subgroup of G and C_n is a subgroup of G.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 3, 1, 2, 1, 1, 1, 4, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 3, 1, 2, 1, 1, 1, 4, 1, 3, 1, 4, 1, 2, 1, 2, 1, 1, 1

Offset: 1

Author

Jianing Song, Sep 30 2019

Keywords

• nonn
• tabl

Comments

The semidirect product of C_m and C_n has group representation G = , where r is any number such that r^n == 1 (mod m). Two groups G = and G' = are isomorphic if and only if there exists some k, gcd(k,n) = 1 such that r^k == s (mod m), in which case f(x^i*y^j) = x^i*y^(k*j) is an isomorphic mapping from G to G'.

Given m, T(m,n) only depends on the value of gcd(n,psi(m)), psi = A002322 (Carmichael lambda). So each row is periodic with period psi(m). See A327925 for an alternative version.

Every number k occurs in the table. By Dirichlet's theorem on arithmetic progressions, there exists a prime p such that p == 1 (mod 2^(k-1)), then T(p,2^(k-1)) = d(gcd(2^(k-1),p-1)) = k (see the formula below). For example, T(5,4) = 3, T(17,8) = 4, T(17,16) = 5, T(97,32) = 6, T(193,64) = 7, ...

Row m and Row m' are the same if and only if (Z/mZ)* = (Z/m'Z)*, where (Z/mZ)* is the multiplicative group of integers modulo m. The if part is clear; for the only if part, note that the two sequences {(number of x in (Z/mZ)* such that x^n = 1)}{n>=1} and {T(m,n)}{n>=1} determine each other, and the structure of a finite abelian group G is uniquely determined by the sequence {(number of x in G such that x^n = 1)}{n>=1}. - _Jianing Song, May 16 2022

Examples

			  m/n  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   1   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   3   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   4   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   5   1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3
   6   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   7   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
   8   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
   9   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  10   1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3  1  2  1  3
  11   1  2  1  2  2  2  1  2  1  4  1  2  1  2  2  2  1  2  1  4
  12   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
  13   1  2  2  3  1  4  1  3  2  2  1  6  1  2  2  3  1  4  1  3
  14   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  15   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
  16   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
  17   1  2  1  3  1  2  1  4  1  2  1  3  1  2  1  5  1  2  1  3
  18   1  2  2  2  1  4  1  2  2  2  1  4  1  2  2  2  1  4  1  2
  19   1  2  2  2  1  4  1  2  3  2  1  4  1  2  2  2  1  6  1  2
  20   1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6  1  4  1  6
Example shows that T(16,4) = 6: The semidirect product of C_16 and C_4 has group representation G = <x, y|x^16 = y^4 = 1, yxy^(-1) = x^r>, where r = 1, 3, 5, 7, 9, 11, 13, 15. Since 3^3 == 11 (mod 16), 5^3 == 13 (mod 16), <x, y|x^16 = y^4 = 1, yxy^(-1) = x^3> and <x, y|x^16 = y^4 = 1, yxy^(-1) = x^11> are isomorphic, <x, y|x^16 = y^4 = 1, yxy^(-1) = x^5> and <x, y|x^16 = y^4 = 1, yxy^(-1) = x^13> are isomorphic, giving a total of 6 non-isomorphic groups.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..5050 (the first 100 ascending diagonals)
• Math Overflow, When are two semidirect products of two cyclic groups isomorphic.
• Jianing Song, An equivalent formula.

Crossrefs

Cf. A327925, A002322, A000010, A000005.

Cf. also A060594, A060839, A073103, A319099, A319100, A319101, A247257.

Programs

PARI

numord(n,q) = my(v=divisors(q),r=znstar(n)[2]); sum(i=1,#v,prod(j=1,#r,gcd(v[i],r[j]))*moebius(q/v[i]))
T(m,n) = my(u=divisors(n)); sum(i=1,#u,numord(m,u[i])/eulerphi(u[i]))

Formula

T(m,n) = Sum_{d|n} (number of elements x such that ord(x,m) = d)/phi(d), where ord(x,m) is the multiplicative order of x modulo m, phi = A000010. There is a version to compute the terms more conveniently, see the links section. [Proof: let (Z/mZ)* denote the multiplicative group modulo m. For every d|n, the elements in (Z/mZ)* having order d are put into different equivalence classes, where each class is of the form {a^k: gcd(k,n)=1}. The size of each equivalence class is the number of different residues modulo d of the numbers that are coprime to n, which is phi(d). - Jianing Song, Sep 17 2022]

Equivalently, T(m,n) = Sum_{d|gcd(n,psi(m))} (number of elements x such that ord(x,m) = d)/phi(d). - Jianing Song, May 16 2022 [This is because the order of elements in (Z/mZ)* must divide psi(m). - Jianing Song, Sep 17 2022]

Let U(m,q) be the number of solutions to x^q == 1 (mod m):

T(m,1) = U(m,1) = 1;

T(m,2) = U(m,2) = A060594(m);

T(m,3) = (1/2)*U(m,3) + (1/2)*U(m,1) = (1/2)*A060839(m) + 1/2;

T(m,4) = (1/2)*U(m,4) + (1/2)*U(m,2) = (1/2)*A073103(m) + 1/2;

T(m,5) = (1/4)*U(m,5) + (3/4)*U(m,1) = (1/4)*A319099(m) + 3/4;

T(m,6) = (1/2)*U(m,6) + (1/2)*U(m,2) = (1/2)*A319100(m) + 1/2;

T(m,7) = (1/6)*U(m,7) + (5/6)*U(m,1) = (1/6)*A319101(m) + 5/6;

T(m,8) = (1/4)*U(m,8) + (1/4)*U(m,4) + (1/2)*U(m,2) = (1/4)*A247257(m) + (1/4)*A073103(m) + (1/2)*A060594(m);

T(m,9) = (1/6)*U(m,9) + (1/3)*U(m,3) + (1/2)*U(m,1);

T(m,10) = (1/4)*U(m,10) + (3/4)*U(m,2).

For odd primes p, T(p^e,n) = d(gcd(n,(p-1)*p^(e-1))), d = A000005; for e >= 3, T(2^e,n) = 2*(min{v2(n),e-2}+1) for even n and 1 for odd n, where v2 is the 2-adic valuation.