Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I came across an article regarding Arnold's Cat Map, and it briefly mentions the period of the transformations.

To add some detail, it considers the cat or whatever it may be on a pixel map that is $p$ pixels wide. Since it is a unit square, it has $p^2$ pixels. To identify each point, one can label each pixel by a Cartesian coordinate of the form $(m/p, n/p)$.

To throw it out there, Arnold's Cat map is defined in matrix notation as follows

$\Gamma(\begin{bmatrix}x \\y\end{bmatrix}) =\begin{bmatrix}1 & 1 \\1 & 2\end{bmatrix} \begin{bmatrix}x \\ y\end{bmatrix}mod \hspace{1mm}1$

Knowing the unique position of each pixel, one can find the period of the pixel map. If the point is rational, it will eventually return to its original position. However, each point may have a different period. So the period of the pixel map has to be a multiple of each point's period. To define that relationship, we let $\Pi(p)$ denote the least common multiple of the periods of all the pixel points in the map where $\Pi(p)$ is the smallest integer that is divisible by all of the periods.

The article I was reading was considering a pixel map with width $p=101$. However, it simple says $\Pi(101) = 25$. The only other detail it provides is that if $p=101$ then all the points have period $1, 5, or \hspace{1mm}25.$ That's all the detail I have.

There are a few exercises relating to this. For instance,

$\Pi(p) = 3p$ iff $p=2*5^k$ for $k=1,2,...$

Find $\Pi(250)$, $\Pi(25)$...

Basically, how could I calculate these periods? The article didn't provide any examples.

Any feedback is appreciated.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

The eigenvalues of $M=\left[\begin{matrix}1&1\\1&2\end{matrix}\right]$ are $\frac{3\pm \sqrt 5 }2$. Modulo a prime $p$, it depends on whether $5$ is a square modulo $p$. For example, with $p=101$, we have $45^2\equiv 5$, hence the eigenvalues are $\frac{3\pm 45}2$, that is $\equiv24$ and $\equiv 80$ (why?). One can calculate the period (under multiplication) of $24$ and $80$ and will find out that it is $25$ in both cases. It follows (or one quickly computes) that $M^{25}$ is congruent to the identity matrix $\pmod p$. The only nontrivial divisor of $25$ is $5$, but $M^5$ is not the identity, so not all points have period $5$ (though they can be found via the linear equation $M^5 x \equiv x\pmod p$).

Hints for the exercises: Consider the case $p=2\cdot 5^k$. Among others, you want to show that $M^{3p}\equiv E\pmod p$. Note that $M^5=\left[\begin{matrix}34&55\\55&89\end{matrix}\right]=5\left[\begin{matrix}7&11\\11&18\end{matrix}\right]-\left[\begin{matrix}1&0\\0&1\end{matrix}\right]$. By induction, we find $$M^{5^k}=5^k A_k+(-1)^kE$$ where $A_k$ is a symmetric matrix. Therefore, $M^{p/2}\equiv (-1)^kE\pmod {5^k}$, hence $M^p\equiv E\pmod {5^k}$. Now observe that also $M^5\equiv \left[\begin{matrix}0&1\\1&1\end{matrix}\right] \pmod 2$, hence by induction $M^{5^k}\equiv \left[\begin{matrix}e&1\\1&1-e\end{matrix}\right] \pmod 2$ with $e\in\{0,1\}$ and then $M^{3p}\equiv E\pmod 2$. Together with $M^{3p}\equiv E\pmod {5^k}$, this implies $M^{3p}\equiv E\pmod p$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.