0
$\begingroup$

The permutation $\alpha : \mathbb Z_{11} \rightarrow \mathbb Z_{11}$ given by $\alpha(x)=4x^2-3x^7$ is a cycle? If it´s not a cycle then write it as a product of disjoint cycles.

  • 6
    Just compute starting from $0$, $\alpha(0) = 0$, $\alpha(1) = 1$, ...2012-03-27
  • 1
    As martini points out, $\alpha(0)=0$, not $1$. If $\alpha(x)$ was $1$ for all $x$, $\alpha$ wouldn't be a permutation at all.2012-03-27
  • 1
    How did you prove that $\alpha$ was a permutation? If you could show your workings it might be easier to see how to help you.2012-03-27
  • 0
    But why you got $[1]$ then? And if $\alpha$ is injective, it is impossible for all values to be $[1]$. And: How did you prove injectivity? For computing $\alpha(x)$ for all $x \in \mathbb Z_{11}$ I'd compute $x^2$ and $x^7$ first, I think.2012-03-27
  • 0
    I would suggest you comute all values individually, because this is the only way (that I know of) to write a permutation as a product of disjoint cycles. And even if it's not the only way, it's a very easy one.2012-03-27
  • 2
    The [answer by Srivatsan](http://math.stackexchange.com/a/65815/11619) to another question related to this same permutation settles your question as well. Several orbits are described there.2012-03-27
  • 0
    @Jyrki Ugh, I guess I should have done a site search first :(2012-03-27
  • 0
    @TMM: Nothing to worry about. I mean, this question does not exactly have the ring of a FAQ to it :-). You have my +1. Srivatsan doesn't write down the cycles explicitly, and in theory his answer leaves it open, whether the restriction of $\alpha$ on the QRs (or NQRs) is a cycle, or even the identity mapping.2012-03-28

1 Answers 1

4

Of course martini's comment is very true, as the easiest thing to do would just be computing $\alpha(x) \bmod 11$ for $x = 0, 1, \ldots, 10$, and seeing if we get a cycle. But let us try to be clever, and try to obtain the cycles without doing 'brute force' calculations. (Maybe it's too much, in which case you can just skip to the bottom...)


First, modulo $11$, by Euler's theorem we have that $x^{10} \equiv 1$ for $x \neq 0$, but also $x^5 = +1$ if $x$ is a quadratic residue, and $x^5 = -1$ if $x$ is a quadratic nonresidue in $\mathbb{Z}_{11}^{*}$. So:

$$\alpha(x) = 4x^2 - 3x^7 \equiv 4x^2 + 8x^7 = 4x^2(1 + 2x^5) \equiv 4x^2(1 + 2(\pm1))\equiv \begin{cases} x^2, & \text{if }x \in \square, \\ 7x^2, & \text{if } x \notin \square. \end{cases}$$

Since $7 \equiv -4 \bmod 11$ and $4 \in \square$ we have $7 \notin \square$, and since $7^2 \not\equiv 1 \bmod 11$ it follows that $7$ is a generator of $\mathbb{Z}_{11}^{*}$. And in terms of powers of $7$, the function $\alpha$ is simple:

$$\alpha(7^k) \equiv \begin{cases} 7^{2k} & \text{if } k \text{ even} \\ 7^{2k+1} & \text{if } k \text{ odd} \end{cases}$$

Also note that $7^{10 + k} \equiv 7^k$ by Euler, so we can reduce the exponents modulo $10$. So in terms of the generator $7$, we get the following cycles:

$$7^0 \to 7^0 \\ 7^1 \to 7^3 \to 7^7 \to 7^5 \to 7^{1} \\ 7^2 \to 7^4 \to 7^8 \to 7^6 \to 7^2 \\ 7^9 \to 7^9 \\ (0 \to 0)$$

To get actual numbers out of this we do need to do some calculations now. But notice that to obtain the result that we have two cycles of length $4$ and three cycles of length $1$, we arguably did not have to do any calculations. In any case, these cycles correspond to the following numbers.

$$1 \to 1 \\ 7 \to 2 \to 6 \to 10 \to 7 \\ 5 \to 3 \to 9 \to 4 \to 5 \\ 8 \to 8 \\ (0 \to 0)$$

So as a product of cycles, we get $(1)(7,2,6,10)(5,3,9,4)(8)(0)$.