# Algorithmic approach to enumerating ideals in $\Bbb Z[x]/(m, f(x))$

I'm studying for my algebra quals this fall and keep encountering problems like the following:

List all the ideals of $\mathbb{Z}[x]/(16, x^3)$.

or

List all the primes of $\mathbb{Z}[x]/(35, x^2 - 2)$.

for example. Looking at the answers, there seem to be a few strategies one (who is well-versed in ring theory) can use. What I would like to know is if there is an algorithmic approach to problems like this? I don't need pseudo-code, but rather a checklist for how to solve a problem like

Enumerate the ideals of $\mathbb{Z}[x]/(m,f(x))$.

First observe that $\mathbb{Z}[x]/(m,f(x)) \cong \mathbb{Z}/(m)[x]/(f(x))$. Decompose $m$ into prime factors, say $m=p_1^{k_1} \cdot \dotsc \cdot p_n^{k_n}$. The Chinese Remainder Theorem (and some simple facts that polynomial rings, products and quotients commute for commutative rings) tells us that $\mathbb{Z}/(m)[x]/(f(x)) \cong \prod_{i=1}^{n} \mathbb{Z}/(p_i^{k_i})[x]/(f(x))$. Ideals in a product of finitely many rings are easy to describe, they are just products of ideals in the individual rings. Thus, we may always assume that $m$ is a prime power. If $m$ is a prime, then $\mathbb{Z}/(m)[x]$ is a PID, hence the ideals of $\mathbb{Z}/(m)[x]/(f(x))$ correspond to the divisors of $f(x)$. This is the easy case.

For example, $\mathbb{Z}[x]/(35,x^2-2) \cong \mathbb{F}_5[x]/(x^2-2) \times \mathbb{F}_7[x]/(x^2-2)$. Now, $x^2-2$ is irreducible over $\mathbb{F}_5$, hence the first factor is a field, and has exactly two ideals. But $x^2-2=(x-3)(x-4)$ in $\mathbb{F}_7[x]$, hence the second factor is a product of two fields, hence has exactly four ideals. It follows that $\mathbb{Z}[x]/(35,x^2-2)$ has exactly eight ideals. By an investigation of the proofs you can write them down explicitly (I will leave this to the reader).

The hard part is then $m$ is a prime power. Right now I don't know how to attack $\mathbb{Z}/16[x]/(x^3)$ directly, so let's start with a simpler example, say $\mathbb{Z}/4[x]/(x^2)$. In order to find the ideals of a ring $R$, we can look at those containing a given element $r$, corresponding to ideals of the quotient ring $R/(r)$, which is easier to analyse. Then we may iterate this procedure. In our case, every element has the form $a+bx$ for some $a,b \in \mathbb{Z}/4$, and we compute with the rule $x^2=0$.

If $a$ is a unit, then also $a+bx$ is a unit. So we only have to consider the cases $a=0,2$. Assume first that $a=0$. The cases $b=0$ and $b=1,3$ are boring and give the ideals $(0)$ and $(x)$. Then we have the case $b=2$. Ideals containing $2x$ correspond to ideals of $\mathbb{Z}/4[x]/(x^2,2x)$. They can be classified, see below. If $a=2$, then every ideal containing $2+bx$ also contains $(2+bx)x=2x$. So again we end up with an ideal of $\mathbb{Z}/4[x]/(x^2,2x)$.

So what about $\mathbb{Z}/4[x]/(x^2,2x)$? Again take some element, say $a+bx$, wlog $b=0,1$ (warning: these differ from the above $a,b$), anbd wlog non-zero and a non-unit. If $b=0$, then we have the cases $a=2$, and ideals containing $2$ correspond to ideals of $\mathbb{F}_2[x]/(x^2)$, so that we are again in the simple case. If $b=1$, then ideals containing $a+x$ correspond to ideals of $\mathbb{Z}/(4,a^2,2a)$, which are easy to describe. They correspond to divisors of $\mathrm{gcd}(4,a^2,2a)$, and you can just go through the cases $a=0,1,2$.

Again all these correspondences are quite explicit, and it is a good exercise to make a list out of it containing all the ideals of $\mathbb{Z}/4[x]/(x^2)$, specified by generators. In general, I think one can try to find a list of ideals of $\mathbb{Z}/p^n[x]/(x^m)$ using a double induction. Actually the method above is very closely related to the game of rings.

• Thank you! This is very clarifying. – tghyde May 3 '13 at 20:39

One approach would be to learn about some of the ideals of $\Bbb Z[x]$ first, and then determine which ones contain the ideal in question, so that you can conclude they are ideals by correspondence.

There are several solutions on the site concerning the problem of finding ideals and prime ideals of $\Bbb Z[x]$.

Here are the few I've seen before:

Ideals of $\mathbb{Z}[X]$

Classification of prime ideals of $\mathbb{Z}[X]$

In a lot of cases, you are probably going to be able to find several prime (or at least maximal) ideals by inspection. You're aided by the fact that $\Bbb Z[x]$ is a UFD, so factorizations you find are going to give you information about what is above $m$ and $f(x)$. I think we're also aided by an isomorphism $\Bbb Z[x]/(n,f(x))\cong Z_n[x]/(f_n(x))$, where the $_n$ is denoting "mod $n$".

For the first example with $R=\Bbb Z/(x^3,16)$, you can see right away that $x$ and $2$ are in the nilradical of $R$, which is the intersection of prime ideals of $R$. So any primes you find are going to have to contain the ideal $I=(x,2)$. Moreover $I$ is maximal, and so it is the only prime ideal. I have trouble seeing what the lowest number is, but $I$ is nilpotent. ($I^6=\{0\}$ maybe?) You can see several other ideals between $I$ and $(x^3, 16)$: $(x^i,2^j)$ for $1\leq i\leq 2$ and $1\leq j\leq 3$. I'm not positive if this is exhaustive.

From the links I provided I learned that $(p, f(x))$ is prime if $p$ is prime and $f(x)$ is irreducible mod $p$. I noticed that it's irreducible mod $5$, but reducible mod 7, since $3^2-2=0$ mod 7. So, $(7,x^2-2)$ is not prime and not maximal! Through that I saw that $x^2-3\in (x-3,7)$ and also in $(x+3,7)$, both of which I'm guessing are maximal. (The relevant computation is $x^2-2=(x-3)(x+3)+7$). The solution here then appears to be that $(7,x-3),(7,x+3),(5,x^2-2)$ is a list of the prime ideals in the second ring.

(awaiting verification from commutative algebraists...)

• Sorry, but I lack confidence in my knowledge of these types of rings :) People who study Dedekind domains and unique factorization will no doubt find this trivial. – rschwieb May 2 '13 at 20:54
• I don't think that "One approach would be to learn about all the ideals of Z[x] first, and then determine which ones contain the ideal in question." is a good idea. In fact, it doesn't work in practice. – Martin Brandenburg May 3 '13 at 15:16
• @MartinBrandenburg Yeah, "all" is the wrong thing for me to say. But the strategy of finding ideals in the ring you're quotienting and passing them to a quotient is an obvious strategy everyone uses when thinking about quotient rings. Therefore I can't really understand the comment about it "not working in practice." – rschwieb May 3 '13 at 15:19
• It does not work since only the relations make it possible to characterize the ideals. You cannot list the ideals of Z[x]. I prepare an answer. – Martin Brandenburg May 3 '13 at 15:21
• @MartinBrandenburg I just meant that it will help you find ideals. Well I know from experience it is impossible to change your mind once you've settled on a misinterpretation of what I meant, so by all means, proceed. – rschwieb May 3 '13 at 15:23