0,2

Nicolas, Corollary 1, p.4, cites Mandel and Simon, Lemma 4.1: let d be in N^*, then every d x d torsion matrix M satisfies M^((2*d^2)! + d) = M^d.

Abstract: The Matrix Torsion Problem (MTP) is: given a square matrix M with rational entries, decide whether two distinct powers of M are equal. It has been shown by Cassaigne and the author that the MTP reduces to the Matrix Power Problem (MPP) in polynomial time: given two square matrices A and B with rational entries, the MTP is to decide whether B is a power of A. Since the MPP is decidable in polynomial time, it is also the case of the MTP. However, the algorithm for MPP is highly nontrivial. The aim of this note is to present a simple, direct, polynomial-time algorithm for the MTP.

Francois Nicolas, A simple, polynomial-time algorithm for the matrix torsion problem

a(n) = (2*n^2)! + n = A000142(2*A000290(n)) + n = A000142(A001105(n)) + n.

a(0) = (2*0^2)! + 0 = 1.

a(1) = (2*1^2)! + 1 = 3.

a(2) = (2*2^2)! + 2 = 40322.

a(3) = (2*3^2)! + 3 = 6402373705728003.

a(4) = (2*4^2)! + 4 = 263130836933693530167218012160000004.

Cf. A000142, A000290, A001105.

Sequence in context: A086509 A068161 A116313 this_sequence A135760 A003541 A086829

Adjacent sequences: A140653 A140654 A140655 this_sequence A140657 A140658 A140659

easy,nonn

Jonathan Vos Post (jvospost3(AT)gmail.com), Jul 10 2008