11
$\begingroup$

Let $A$ be a square matrix with integer entries and let $m$ be a positive integer. From the pigeonhole principle it follows easily that the sequence $$I,A, A^2, A^3,\; \dots \pmod m$$ is eventually periodic, that is, there exist integers $s \geq 0$ and $t > 0$ such that $$(1) \quad A^{s + t + n} \equiv A^{s + n} \pmod m$$ for every integer $n \geq 0$. Here the reduction modulo $m$ of a matrix with integer entries is meant as the reduction modulo $m$ of each of the entries.

The minimum $s$ such that (1) holds is called the preperiod of $A$ and it is denoted by $s_A(m)$. From the Chinese remainder theorem it follows that $$s_A(m_1 m_2) = \max(s_A(m_1),s_A(m_2))$$ for all coprime positive integers $m_1, m_2$. Hence the computation of $s_A(m)$ is reduced to the case of $m$ being a prime power.

Questions:

(i) Is it true that, for each prime number $p$, there exist integers $a,b,c \geq 0$ such that $$s_A(p^k) = ak + b$$ for every integer $k > c$ ? Answer: No, mathematician123 provided the example $A = p^2 I$.

(ii) If not, what is the behavior of $s_A(p^k)$ for large $k$ ?

These seem pretty much natural questions, but unfortunately I was not able to find any answer in the literature.

If $\det(A)$ is not divisible by $p$, then $A$ is invertible modulo $p^k$, and this yields $s_A(p^k) = 0$ for every $k$. Hence the interesting case is when $\det(A)$ is divisible by $p$.

Improve this question
$\endgroup$
4
  • $\begingroup$ In your definition $s=0$ works always. Did you confuse $s$ and $t$ or should you impose $s>0$? $\endgroup$ Commented Apr 22 at 16:07
  • $\begingroup$ @ChrisWuthrich yeah there was a typo, I fixed it. Thx $\endgroup$ Commented Apr 22 at 16:13
  • 1
    $\begingroup$ $A = (p^2)$ gives $s_A(p^{2k - 1}) = s_A(p^{2k}) = k$. $\endgroup$ Commented Apr 22 at 22:18
  • $\begingroup$ @mathematician123 thanks. I added your example to the post. $\endgroup$ Commented Apr 23 at 8:33

2 Answers 2

Reset to default
7
$\begingroup$

Your conjecture for question i is incorrect. The matrix $A =\begin{pmatrix}2 & 1 \\ 0 & 2\end{pmatrix}$ is a counter example. We have that $A^n = \begin{pmatrix}2^n & n2^{n-1} \\ 0 & 2^n\end{pmatrix}$. Hence, we have that $$ s_A(2^k) = \begin{cases} k &\text{if $k$ is odd}\\ k+1 & \text{if $k$ is even.} \end{cases} $$

In general (your question ii), as Max Alekseyev said, the sequence $u_n := A^n_{i, j}$ forms a linear recurrence sequence, which for some (computable) $d \in \mathbb{N}$, polynomials $P_i \in \overline{\mathbb{Q}}[X]$ and characteristic roots $\lambda_i \in \overline{\mathbb{Q}}$ has the polynomial-exponential form $$ u_n = \sum_{i=1}^d P_i(n)\lambda_i^n $$ Then let $K$ be a number field containing all coefficients of the polynomials $P_i$ and the characteristic roots $\lambda_i$, and let $\frak{p}$ be a prime ideal above $p$ in the ring of integers of $K$. Then, we consider the characteristic roots $\lambda_i$ are in $\frak{p}$ and which are not in $\frak{p}$ separately. In the latter case, $P_i(n)\lambda_i^n$ is periodic modulo powers of $\frak{p}$ and thus do not influence the length of the preperiod. Thus, we are interested in $$ \max\Big\{n \in \mathbb{N} : \sum_{i=1, \lambda_i \in \frak{p}}^d P_i(n)\lambda_i^n \not\in\mathfrak{p}^k\Big\}. $$ As the $\lambda_i$ are in $\frak{p}$, this gives the bound Max Alekseyev provided above (being more careful with the ramification indices of the prime ideals give). The difficulty lies in the fact that the linear combination and polynomials can give unaccounted factors of $\frak{p}$ (which I constructed with the factor $\frac{n}{2}$ in front of the characteristic root $2^n$ in my counterexample).

The behavior for a single linear recurrence sequence can be a lot uglier than this. Take $u_n = (-4+7i)^n + (-4-7i)^n +2(8+i)^n+2(8-i)^n$, $p = 5$ and $\mathfrak{p} = (1+2i)$. Then $$ \max\Big\{n \in \mathbb{N} : \sum_{i=1, \lambda_i \in \frak{p}}^d ((2+3i)^n + 2(2-3i)^n)(1+2i)^n \not\in\mathfrak{p}^k\Big\} $$ depends heavily on the $\frak{p}$-valuation of $(2+3i)^n + 2(2-3i)^n$, which might get arbitrarily large (I have not verified this in this specific example).

However, in your your context, we are dealing with many linear recurrence sequences at the same time (as we are dealing with a matrix $A$), so the last kind of example might not be possible for an entire matrix.

Improve this answer
$\endgroup$
8
$\begingroup$

The powers of a matrix form a linear recurrence sequence (with characteristic polynomial equal the minimal polynomial of the matrix). Hence, the question essentially is about the periods of such sequences in rings $\mathbb Z/p^k\mathbb Z$. There are tons of literature on this topic. In particular, your questions may be answered in Chapter 3 (Linear Recurring Sequences Over Artinian and Finite Rings) in the monograph Linear recurring sequences over rings and modules but I did not check that.

ADDED. On a brief look, it seems that the following answer to (ii) is implied by Proposition 17.2: $$s_A(p^k) \leq k \cdot \mathop{\rm deg} \mathrm{minpoly}(A).$$

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ I appreciate the help and I'm checking the book - but this is a comment, not an answer $\endgroup$ Commented Apr 22 at 18:07
  • 3
    $\begingroup$ A pointer in a right direction can be an important first step, especially given that you could not find any literature. You are welcome to not accept my answer if you are not satisfied though. $\endgroup$ Commented Apr 22 at 19:16
  • 4
    $\begingroup$ For linear recurrences modulo $m$ (as M. Alekseyev pointed out your case is directly related to the minimal polynomial of the matrix) there is also the very nice paper by Reeds and Sloane, who devised a modulo $m$ version of the Berlekamp-Massey algorithm to determine the shortest shift register for a linear recurrence modulo $m.$ Equivalently, this yields the minimal degree characteristic polynomial generating the sequence. There is a link to the paper here: en.wikipedia.org/wiki/Reeds%E2%80%93Sloane_algorithm $\endgroup$ Commented Apr 23 at 5:59
  • $\begingroup$ @MaxAlekseyev regarding the upper bound from Prop 12.2: yeah this is compatible with something weaker that I was able to prove. However, it seems to me that Kurakin et al. do not provide a formula for the preperiod (or "defect" as they call it). $\endgroup$ Commented Apr 23 at 14:38
  • 2
    $\begingroup$ @LarryX: It may be the case that there is no simple formula. $\endgroup$ Commented Apr 24 at 0:42

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.