|
| |
|
|
A327924
|
|
Square array read by ascending diagonals: 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.
|
|
4
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
The semidirect product of C_m and C_n has group representation G = <x, y|x^m = y^n = 1, yxy^(-1) = x^r>, where r is any number such that r^n == 1 (mod m). Two groups G = <x, y|x^m = y^n = 1, yxy^(-1) = x^r> and G' = <x, y|x^m = y^n = 1, yxy^(-1) = x^s> 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
|
|
|
LINKS
|
|
|
|
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,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.
|
|
|
EXAMPLE
|
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.
|
|
|
PROG
|
(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]))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
