cp's OEIS Frontend

A181107 Triangle read by rows: T(n,k) is the number of 2 X 2 matrices over Z(n) having determinant congruent to k mod n, 1 <= n, 0 <= k <= n-1.

%I A181107 #42 Jan 05 2025 19:51:39
%S A181107 1,10,6,33,24,24,88,48,72,48,145,120,120,120,120,330,144,240,198,240,
%T A181107 144,385,336,336,336,336,336,336,736,384,576,384,672,384,576,384,945,
%U A181107 648,648,864,648,648,864,648,648,1450,720,1200,720,1200,870,1200,720,1200,720
%N A181107 Triangle read by rows: T(n,k) is the number of 2 X 2 matrices over Z(n) having determinant congruent to k mod n, 1 <= n, 0 <= k <= n-1.
%C A181107 The n-th row is {T(n,0),T(n,1),...,T(n,n-1)}.
%C A181107 Let m denote the prime power p^e.
%C A181107 T(m,0) = A020478(m) = (p^(e+1) + p^e-1)*p^(2*e-1).
%C A181107 T(m,1) = A000056(m) = (p^2-1)*p^(3*e-2).
%C A181107 T(prime(n),1) = A127917(n).
%C A181107 Sum_{k=1..n-1} T(n,k) = A005353(n).
%C A181107 T(n,1) = n*A007434(n) for n>=1 because A000056(n) = n*Jordan_Function_J_2(n).
%C A181107 T(2^n,1) = A083233(n) = A164640(2n) for n>=1. Proof: a(n):=T(2^n,1); a(1)=6, a(n)=8*a(n-1); A083233(1)=6 and A083233(n) is a geometric series with ratio 8 (because of its g.f.), too; A164640 = {b(1)=1, b(2)=6, b(n)=8*b(n-2)}.
%C A181107 T(2^n,0) = A165148(n) for n>=0, because  2*T(2^n,0) = (3*2^n-1)*4^n.
%C A181107 T(2^e,2) = A003951(e) for 2 <= e. Proof: T(2^e,2) = 9*8^(e-1) is a series with ratio 8 and initial term 72, as A003951(2...inf) is.
%C A181107 Working with consecutive powers of a prime p, we need a definition (0 <= i < e):
%C A181107 N(p^e,i):=#{k: 0 < k < p^e, gcd(k,p^e) = p^i} = (p-1)*p^(e-1-i). We say that these k's belong to i (respect to p^e). Note that N(p^e,0) = EulerPhi(p^e), and if 0 < k < p^e then gcd(k,p^e) = gcd(k,p^(e+1)). Let T(p^e,[i]) denote the common value of T(p^e,k)'s, where k's belong to i (q.v.PROGRAM); for example, T(p^e,[0]) = T(p^e,1). The number of the 2 X 2 matrices over Z(p^e), T(p^e,0) + Sum_{i=0..e-1} T(p^e,[i])*N(p^e,i) = p^(4e) will be useful.
%C A181107 On the hexagon property: Let prime p be given and let T(p^e,[0]), T(p^e,[1]), T(p^e,[2]), ..., T(p^e,[e-2]), T(p^e,[e-1]) form the e-th row of a Pascal-like triangle, e>=1. Let denote X(r,s) an element of the triangle and its value T(p^r,[s]). Let positive integers a and b given, so that the entries A(m-a,n-b), B(m-a,n), C(m,n+a), D(m+b,n+a), E(m+b,n), F(m,n-b) of the triangle form a hexagon spaced around T(p^m,[n]); if a=b=1 then they surround it. If A*C*E = B*D*F, then we say that the triangle T(.,.) has the "hexagon property". (In the case of binomial coefficients X(r,s) = COMB(r,s), the "hexagon property" holds (see [Gupta]) and moreover gcd(A,C,E) = gcd(B,D,F) (see [Hitotumatu & Sato]).)
%C A181107 Corollary 2.2 in [Brent & McKay] says that, for the d X d matrices over Z(p^e), (mutatis mutandis) T_d(p^e,0) = K*(1-P(d+e-1)/P(e-1)) and T_d(p^e,[i]) = K*(q^e)*((1-q^d)/(1-q))*P(d+i-1)/P(i), where q=1/p, K=(p^e)^(d^2), P(t) = Product_{j=1..t} (1-q^j), P(0):=1. (For the case d=2, we have T(p^e,[i]) = (p+1)*(p^(i+1)-1)*p^(3*e-i-2).) Due to [Brent & McKay], it can be simply proved that for d X d matrices the "hexagon property" is true. The formulation implies an obvious generalization: For the entries A(r,u), B(r,v), C(s,w), D(t,w), E(t,v), F(s,u) of the T_d(.,.)-triangle, a hexagon-like property A*C*E = B*D*F holds. This is false in general for the COMB(.,.)-triangle.
%C A181107 Another (rotated-hexagon-like) property: for the entries A(m-b1,n), B(m-a1,n+c2), C(m+a2,n+c2), D(m+b2,n), E(m+a2,n-c1), F(m-a1,n-c1) of the T_d(.,.)-triangle, the property A*C*E = B*D*F holds, if and only if 2*(a1 + a2) = b1 + b2. This is also in general false for COMB(.,.)-triangle.
%H A181107 Erdos Pal, <a href="/A181107/b181107.txt">Rows n=1..100 of triangle, flattened</a>
%H A181107 Richard P. Brent and Brendan D. McKay, <a href="https://doi.org/10.1016/0012-365X(87)90117-8">Determinants and ranks of random matrices over Z_m</a>, Discrete Mathematics 66 (1987) pp. 35-49.
%H A181107 A. K. Gupta, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/12-1/gupta.pdf">Generalized hidden hexagon squares</a>, The Fibonacci Quarterly, Vol 12, Number 1, Feb.1974, pp. 45-46.
%H A181107 S. Hitotumatu, D. Sato, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/13-1/hitotumatu.pdf">Star of David theorem (I)</a>, The Fibonacci Quarterly, Vol 13, Number 1, Feb.1975, p. 70.
%F A181107 T(a*b,k) = T(a,(k mod a))*T(b,(k mod b)) if gcd(a,b) = 1.
%F A181107 Sum_{k=1..n-1, gcd(k,n)=1} T(n,k) = A000252(n). - _Andrew Howroyd_, Jul 16 2018
%e A181107 From _Andrew Howroyd_, Jul 16 2018: (Start)
%e A181107 Triangle begins:
%e A181107     1;
%e A181107    10,   6;
%e A181107    33,  24,  24;
%e A181107    88,  48,  72,  48;
%e A181107   145, 120, 120, 120, 120;
%e A181107   330, 144, 240, 198, 240, 144;
%e A181107   385, 336, 336, 336, 336, 336, 336;
%e A181107   736, 384, 576, 384, 672, 384, 576, 384;
%e A181107   945, 648, 648, 864, 648, 648, 864, 648, 648;
%e A181107   ... (End)
%o A181107 (Other) . (* computing T(p^e,k) ; p=prime, 1<=e, 0<=k<p^e, elementary approach *)
%o A181107 . (1) F := (p-1)*p^(e-1)
%o A181107 . (2) u := [ u(0),u(1),...,u(p^e-1) ] vector, where
%o A181107 . (21) u(0) := p^e + e*F, and
%o A181107 . (22) FOR x := 1 TO p^e-1
%o A181107 . (22) u(x) := (i+1)*F, where GCD(x,p^e)= p^i
%o A181107 . (22) ENDFOR
%o A181107 . (3) T(p^e,k):= ScalarProduct( u, kTimesCyclicRightShift(u) )
%o A181107 (PARI)
%o A181107 S(p,e)={my(u=vector(p^e)); my(t=(p-1)*p^(e-1)); u[1] = p^e + e*t; for(j=1, p^e-1, u[j+1] = t*(1+valuation(j, p))); vector(#u, k, sum(j=0, #u-1, u[j + 1]*u[(j+k-1) % #u + 1]))}
%o A181107 T(n)={my(f=factor(n), v=vector(n,i,1)); for(i=1, #f~, my(r=S(f[i,1], f[i,2])); for(j=0, #v-1, v[j + 1] *= r[j % #r + 1])); v}
%o A181107 for(n=1, 10, print(T(n))); \\ _Andrew Howroyd_, Jul 16 2018
%Y A181107 Column k=0 is A020478.
%Y A181107 Column k=1 is A000056.
%Y A181107 Row sums are A005353.
%Y A181107 Cf. A000252, A127917.
%K A181107 mult,nonn,tabl
%O A181107 1,2
%A A181107 _Erdos Pal_, Oct 03 2010
%E A181107 Terms a(24)-a(55) from b-file by _Andrew Howroyd_, Jul 16 2018