2
$\begingroup$

If we have a polynomial lets say $0 + x + 12x^2 + 11x^3$ in $\mathbb{Z}_{13} / x^4 + 1$ (quotient ring over finite field). Then if we multiply that polynomial by $x^i \text{ for } i \in [0, \dots, r]$. Then rows start repeating after some number of rows.

For example, given width equal to $4$, then 9th row is the same as first row. What is the value of $r$ with respect to dimension of that first polynomial (or width of matrix)?

[ 0  1 12 11] --> x^0 * (0 + x + 12x^2 + 11x^3)
[ 2  0  1 12] --> x^1 * (0 + x + 12x^2 + 11x^3) = 2 + 0x + 1x^2 + 12x^3 <-- [ 2  0  1 12]
[ 1  2  0  1] --> x^2 * ...
[12  1  2  0] --> x^3 * ...
[ 0 12  1  2] --> x^4 * ...
[11  0 12  1] --> x^5 * ...
[12 11  0 12] --> x^6 * ...
[ 1 12 11  0] --> x^7 * ...
[ 0  1 12 11] --> x^8 * ... = first row!
$\endgroup$
  • $\begingroup$ Observation: you need both a bound on the coefficients (from the finite field) and a bound on the degree (from the ideal quotient). If either of these are lacking, the. There are examples such that the rows never repeat. In generality, this is a question about quotient rings over finite fields $\endgroup$ – Stella Biderman Feb 26 '17 at 3:49
3
$\begingroup$

The polynomials you mention live in $R = \Bbb Z_{13}[x]/(x^4+1)$ not in $\Bbb Z_{13}/(x^4+1)$. Now in the algebra $R$ of dimension $4$ the multiplication with $x$ can, as a linear operator, be represented by a matrix : $$M_x = \begin{pmatrix} 0 & 0 & 0 & -1 \\ 1 & 0& 0& 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 &0 \end{pmatrix} $$. This matrix expresses that the multiplcation with $x$ maps: $1 \mapsto x, x \mapsto x^2, x^2 \mapsto x^3, x^3 \mapsto x^4 = -1 $. It is easily verified that $M$ has order $8$.

$\endgroup$
3
$\begingroup$

Note that, as we are in a finite field , we have cancellation, so $ x^rf(x) = f(x) $ iff $ x^r = 1 $. So the point at which the sequence $ x^{\mathbb{Z}}f(x) $ repeats is independent of $f$; it is the multiplicative order of $x$.

If $ x \in F $, $F$ a finite field, we know $ \mathcal{o}(x) \mid |F|-1 $. But determining whether $x$ is a primitive root is already hard over $ \mathbb{Z}/(n) $, so I doubt you can do better at pinning down $ \mathcal{o}(x) $.

EDIT: OP has pointed out that the quotient ring given in the OP is not a finite field. But the above conclusions carry over with a few adjustments.

Let the quotient ring be $R[x]/(h(x))$. $R[x]$ is a UFD, so write $h(x)=x^ng(x)$ with $x, g(x)$ coprime. Then, by Bézout, $(x^n)+(g(x))=R[x]$, so, by Chinese Remainder Theorem, $R[x]/(h(x))\cong R[x]/(x^n)\times R[x]/(g(x))$. A cycle in the LHS will (of course) also lead to a cycle in the RHS too. $x^n$ is nilpotent in the first factor, so the action of "multiplication by x" cannot lead to a cycle there. Hence the canonical homorphism given by the CRT must take $f(x)$ to $(0, p(x))$ for some $p(x)\in R[x]/(g(x))$. In this ring, again by Bézout, x is a unit. So may cancel $x$.

We needn't have $ \mathcal{o}(x) \mid |R[x]/(h(x))|-1 $, but the spirit remains. Let $ R[x]/(g(x)) $ have $N$ units; then $ \mathcal{o}(x) \mid N $.

$\endgroup$
  • 1
    $\begingroup$ ${\bf Z}_{13}[x]/(x^4+1)$ is not a field. $x^4+1=(x^2+5)(x^2-5)$ is not irreducible. $\endgroup$ – Gerry Myerson Feb 26 '17 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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