Prove equivalence of aperiodicity definitions

Question

Aperiodicity of a state i is defined in my notes as a state with period, gcd(${n: p_{ii}^n>0}$), of 1 - but we're given an apparently equivalent definition: A state within which for all sufficiently large n $p_{ii}^n>0$.

I can prove that the second implies the first (for then you can get back to i in both N and N+1 steps for some N so gcd is 1) but I can't figure out a straightforward derivation in the opposite direction. I've looked at a solution using Frobenius numbers which seems like a lot of work to prove the equivalence: is there any way to derive it a little more straightforwardly, even if it basically implicitly uses the concepts involved in Frobenius numbers proofs?

Answer 1

This is a purely arithmetic result. One is given a set of integers $D$, defined as $$D=\{n\geqslant1\mid p^n_{ii}\ne0\}$$ with greatest common divisor $1$, and one wants to show that $D$ contains every integer large enough.

Three steps in the proof.

• First, the greatest common divisor of $D$ is $1$ hence, by Bézout identity, there exists some $N\geqslant1$, some $d_k$ in $D$, and some integers $c_k,$ such that $$c_1d_1+\cdots+c_Nd_N=1$$ Separate the integers $c_k$ into the positive ones, renamed $a_k$, and the negative ones, renamed $-b_k$. This yields that $$a_1d_1+\cdots+a_md_m=1+b_1d_{m+1}+\cdots+b_{N-m}d_N$$

• Second, concatenating paths from $i$ to $i$, one sees that $D$ is stable by addition. Thus the integers $$d=b_1d_{m+1}+\cdots+b_{N-m}d_N$$ and $$d+1=a_1d_1+\cdots+a_md_m$$ are both in $D$.

• Now, the Euclidean division of every $n\geqslant d(d-1)$ by $d$ is $n=kd+r$ with $0\leqslant r\leqslant d-1\leqslant k$ hence $$n=kd+r(d+1)-rd=r(d+1)+(k-r)d$$ with $r$ and $k-r$ both nonnegative, which proves that $n$ belongs to $D$.

To conclude, $D$ contains every integer at least as large as $d(d-1)$.