quotient ring – Saad Quader

Let $p$ be a prime number. We know that $F_2=GF(2)=\{0,1\}$ . Let $F_2[x]$ be the ring the polynomials with indeterminate $x$ and coefficients in $F_2$ . The polynomial $(x^p-1) \in F_2[x]$ factors over $F_2$ as follows for various $p$ :

$x^3-1=(1+x) (1+x+x^2).$
$x^5-1=(1+x) (1+x+x^2+x^3+x^4).$
$x^7-1=(1+x) (1+x+x^3) (1+x^2+x^3).$
$x^{11}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}).$
$x^{13}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12}).$
$x^{17}-1=(1+x) (1+x^3+x^4+x^5+x^8) (1+x+x^2+x^4+x^6+x^7+x^8).$

None of the factors above can be factored anymore, hence they are irreducible over $F_2$ . Let us call $x+1$ the trivial factor since the root $x= 1$ already belongs to $F_2$ . But why do we have two nontrivial irreducible factors of $x^7-1$ , each of degree 3, whereas $x^{13}-1$ has only one non-trivial irreducible factor of degree 12? It appears that either there is only one nontrivial factor, or the degree of all nontrivial factors is the same. Why?

Continue reading “Why x^p-1 Factors over GF(2) the Way It Does” →

Let $f(X)=X^p-1 \in F_l[X]$ for a prime $p$ . We are interested in the structure of the ring $R=F_l[X]/(f)$ . Via the Chinese Remainder Theorem, this question is equivalent to finding a factorization of $f$ over $F_l$ . Suppose $f$ factors in $F_l$ as

$\displaystyle f(X) = (X-1) \prod_i^s{q_i(X)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

where each $q_i$ is an irreducible polynomial. What are the degrees of $q_1, \cdots, q_s$ ? What is $s$ ?

We claim that $R=F_l \oplus (F_{l^r})^s,$ where $r$ is the multiplicative order of $l$ mod $p$ .

This structure has been used in a beautifully instructive paper by Evra, Kowalski, and Lubotzky. (Yes, the one in Lubotzky-Philip-Sarnak.) In this paper, they have established connections among the Fourier transform, uncertainty principle, and dimension of ideals generated by polynomials in the ring $R$ above. We’ll talk about these connections in another post. The content of this post is Proposition 2.6(3) from their paper.

Continue reading “The Structure of a Quotient Ring modulo x^p-1” →