# Basic irreducible polynomial

I'm studying cyclic codes over a ring $R$. It is well known that a cyclic code over $R$ of length $n$ is an ideal of $R\left[ x \right]/\left( {{x^n} - 1} \right)$. Hence the factorization of ${{x^n} - 1}$ into irreducible factors over $R$ is important. We know that any irreducible polynomial over the subring is also irreducible over the ring. For instance, let $R = {F_2}\left[ u \right]/(u^3)$ and so ${F_2}$ is a subring of $R$. Clearly, ${x^7} - 1 = \left( {x - 1} \right)\left( {{x^3} + x + 1} \right)\left( {{x^3} + {x^2} + 1} \right)$ over $F_2$. By above, each factor of ${x^7} - 1$ is irreducible over $R = {F_2}\left[ u \right]/(u^3)$. Then, the factorization of ${x^7} - 1$ into irreducible factors over $R = {F_2}\left[ u \right]/(u^3)$ must be same over $F_2$. In each paper I look, I see that let ${x^n} - 1 = {f_1} \ldots {f_r}$, where ${f_i}$ is basic irreducible polynomial. Why do we need the basic irreducible polynomial over $R$ to factor $x^n-1$?

• It is not true in general that a polynomial irreducible over a subring would be irreducible over a bigger ring. For example $x^2+x+1$ is irreducible over $\Bbb{F}_2$ but is not so over $\Bbb{F}_4$. What does hold (and also seems to be important in your case) is that a polynomial irreducible over a quotient ring is so over the original ring. The idea is that any factorization over the original ring gives a factorization over the quotient ring via the natural projection. Jun 25, 2014 at 9:20
• But it is equally possible for an irreducible polynomial to become reducible when you project to a quotient ring. Your implications go the wrong way. Yet in the special case of adjoining nilpotent elements a number of things can be deduced by local arguments such as Hensel lifting. That seems to be the theme in your context. Jun 25, 2014 at 9:26
• But basic irreducibles come to the fore when you classify cyclic codes. An irreducible factor over $F_2$ can be lifted to an irreducible polynomial over the bigger ring in many ways. In this context it is important to pick the one that remains a factor of $x^n-1$. And THAT is important in the coding theory context. The case I'm familiar with is $R=\Bbb{Z}_4$, but I would expect the same to hold in general. If I can think of a toy example, I will write it as an answer. Jun 25, 2014 at 9:32
• Thanks for your useful answer, Jyrki Lahtonen. As you say, it is not true in general that any irreducible polynomial over the subring is also irreducible over the ring. However, for the rings such as ${F_q}\left[ u \right]/(u^s)$ it is true(it is said in all related papers). Hence, the factorization of $x^n-1$ over $F_q$ must be same over ${F_q}\left[ u \right]/(u^s)$. So, what I can't understand is why ${f_i}$'s must be basic irreducible. Jun 25, 2014 at 10:12
• Yeah, in your case you get $F_q$ as both a subring and a quotient ring, so it is a special case. Jun 25, 2014 at 10:48

Polynomial irreducible over subring $\implies$ polynomial irreducible over $R$

is not true, it's the wrong direction.

For a counterexample, consider $R = \mathbb F_4$ and the subring $S = \mathbb F_2$. The polynomial $X^2 + X + 1$ is irreducible over $S$, but not over $R$.

Summary: The basic irreducibles appear naturally when classifying cyclic codes of this form. They generate exactly those cyclic codes that are also free $R$-modules. The other cyclic codes have a bit "mixed" structure.

In the special case under consideration we can view $\Bbb{F}_q$ either as a subring of $R=\Bbb{F}_q[u]/\langle u^s\rangle$ via the natural imbedding $\Bbb{F}_q\to\Bbb{F}_q[u]$ or as a quotient ring as $\Bbb{F}_q=R/uR$. Thus an irreducible polynomial over $\Bbb{F}_q$ remains irreducible over $R$.

We don't get all the irreducible polynomials in $R[x]$ in this way. We have the natural projection $\pi:R[x]\to\Bbb{F}_q[x]$ gotten by reducing the coefficients modulo $u$. Call any monic polynomial $f$ in $R[x]$ a lift of $\pi(f)$. Now if $\pi(f)$ is irreducible over $\Bbb{F}_q$, then $f$ is clearly also irreducible. So all the lifts of an irreducible polynomial are irreducible.

As an example consider the simplest case $q=2$, $s=2$, when $R=\Bbb{F}_2[u]/\langle u^2\rangle$ is a ring of four elements. The polynomial $f_1(x)=x^3+x+1$ is irreducible in $\Bbb{F}_2[x]$. So it is irreducible also in $R[x]$. But any other (monic) lift, such as $f_2(x)=x^3+ux^2+x+1$, is also irreducible.

When studying cyclic codes over rings like this we need to be careful in selecting the "correct" lift. The basic irreducibles are the ones that are factors of $x^n-1$ in $R[x]$ as well as in $\Bbb{F}_q[x]$. The first alphabet ring studied in this way was $\Bbb{Z}_4$ (see the seminal paper Hammons et al, The $\Bbb{Z}_4$-linearity of Kerdock, Preparata, Goethals, and related codes, IEEE Transactions on Information Theory, vol. 40(2), 1994 and anything citing it). In that case this problem was, not difficult, but not trivial either, because in that setting we have no way of using $\Bbb{F}_2$ as a subring of $\Bbb{Z}_4$. If you are interested, see my earlier answer or another earlier answer by yours truly for examples of how the "correct" lifting of $x^3+x+1$ as a factor of $x^7-1$ over $\Bbb{Z}_4$ or $\Bbb{Z}_8$ can be found.

But over your ring $R$ there is no problem in finding the "correct" lifting (correct = basic = a factor of the polynomial $x^n-1$), because the field is also a subring of $R$. I suspect that the terminology has stuck partly because (AFAIK) rings like $R$ entered the coding theory scene after the $\Bbb{Z}_4$-based well of good problems dried up. Anyway, the do play a role in your problem. We are studying ideals of the ring $R[x]/\langle x^n-1\rangle$, so it is only natural that factors of $x^n-1$ play a special role. As an example let us consider the ideals of $R_7:=R[x]/\langle x^7-1\rangle$ generated by the two lifts $f_1$ and $f_2$ above.

Let's first do $f_1(x)=x^3+x+1$. Because $$x^7-1=(x-1)(x^3+x^2+1)f_1(x)$$ we see that the ideal $I_1$ generated by the coset of $f_1$ in $R_7$ is the free $R$-module of rank $4$ spanned by the cosets of $f_1,xf_1,x^2f_1$ and $x^3f_1$. This is because any polynomial $g(x)\in R[x]$ can be uniquely written in the form $$g(x)=q(x)(x-1)(x^3+x^2+1)+r(x),$$ where $q(x)\in R[x]$ and $r(x)\in R[x]$ is of degree $<4$. Therefore the cyclic code $I_1$ has $4^4$ elements.

The other lift $f_2(x)$ is trickier to handle. Let's denote the ideal it generates by $I_2(\subset R_7)$. Because $f_1$ and $f_2$ are equal modulo $uR$, the images of the ideals $I_1$ and $I_2$ in the quotient ring $\Bbb{F}_2[x]/\langle x^7-1\rangle$ are equal. Extending the natural projection to this case we can succinctly state this as $\pi(I_1)=\pi(I_2)$. Note that we also have that $f_1^2=f_2^2$. Because $x^7-1$ has no repeated factors this implies that $f_1^2$ and $f_1$ generate the same ideal. Therefore $I_1\subseteq I_2$.

However, we also have the codeword \begin{aligned} (x-1)(x^3+x^2+1)f_2(x)&=(x-1)(x^3+x^2+1)f_1(x)+(x-1)(x^3+x^2+1)ux^2\\ &=ux^2(x-1)(x^3+x^2+1)\in I_2. \end{aligned} Because $x^2\cdot x^5=1$ in $R_7$, we get that $w=u(x-1)(x^3+x^2+1)\in I_2$ as well. My point is that the codeword $w$ is not in $I_1$. This is annihilated by $u$, but by the free $R$-module stucture of $I_1$ we see that its subset $$I_1\cap uR_7=\{w\in I_1\mid uw=0\}$$ is spanned (as a vector space over $\Bbb{F}_2$) by $uf_1, uxf_1, ux^2f_1$ and $ux^3f_1$. From the theory of cyclic codes over $\Bbb{F}_2$ we easily get that $$uR_7=(I_1\cap uR_7)\oplus uR_7w.$$ This is basically because $x^3+x+1$ and $(x-1)(x^3+x^2+1)$ are complementary factors of $x^7-1$. Thus we can conclude first that $w\notin I_1$, and that actually we have $$I_2=I_1\oplus uR_7w.$$ In general what probably happens (I haven't looked at papers on this closely, but I think I have a strong intuition here for having played with the $\Bbb{Z}_4$-stuff myself) is that, depending on the variant of the lift you get this extra bit, if your polynomial is not "basic". Here I was sure of getting all of $uR_7$ by design, because I modified $f_1$ by adding the term $ux^2$, where $x^2$ is a unit in $R_7$.

When you extend to $s>2$ you probably get more layers all according to whether the lifts have $u^t$- terms with $1<t<s$.