Difficulty understanding the meaning of quotient rings with regards to polynomials.

Question

I am having difficulty understanding quotient rings with regards to polynomials. For example, the quotient ring $\mathbb{F_2}[x]/(x^3 + 1)$ maps to the set of all remainders when a polynomial of $x$ (with coefficients in $\mathbb{F}_2$) is divisible by $x^3 + 1$. However, it's hard for me to comprehend the exact elements in this quotient ring.

Obviously if the quotient ring is something like $\mathbb{Z}/5$, I know that it maps to the set $\{0, 1, 2, 3, 4\}$, since that is the set of possible remainders when any number is divided by $5$. However, with polynomials, I feel it's more difficult to understand because for instance, I know that when a polynomial of $x$ is divided by $x^3 + 1$, the remainder obviously has to be less than $x^3 + 1$, but a polynomial such as $x^2 + 1$ is greater than $x^3 + 1$ for the domain $(0, 1)$ but not so when $x > 1$. So I'm wondering if there's an objective algorithm to determine the set of all remainders when a polynomial is divided by another polynomial.

Answer 1

The notion of "size" we use when we quotient polynomial rings is not the absolute value, but the degree. So for instance, something like $100x^2 + 500$ (which is degree $2$) would be considered smaller than $x^5 - 50 x^4$ (which is degree $5$), because we only care about the degree.

As for how we compute residue classes, we use the same division algorithm that we're used to in order to compute a remainder. You can see a series of worked out examples here, say.

Now, if we look at $\mathbb{F}_5 = \mathbb{Z} / 5$, the elements we're left with are those which are "smaller" than $5$. So $\{0,1,2,3,4\}$.

If we look at $\mathbb{F}_3[x] / (x^3 - x^2 + 1)$, then the elements we're left with are those which are "smaller" than $x^3 - x^2 + 1$. That is, those polynomials of degree $< 3$. So the elements are

$$ \begin{align} 0 && 1 && 2 \\ x && x+1 && x+2 \\ 2x && 2x+1 && 2x+2 \\ x^2 && x^2 + 1 && x^2 + 2 \\ x^2 + x && x^2 + x+1 && x^2 + x+2 \\ x^2 + 2x && x^2 + 2x+1 && x^2 + 2x+2 \\ 2x^2 && 2x^2 + 1 && 2x^2 + 2 \\ 2x^2 + x && 2x^2 + x+1 && 2x^2 + x+2 \\ 2x^2 + 2x && 2x^2 + 2x+1 && 2x^2 + 2x+2 \\ \end{align} $$

Notice there are $27$ of these, since a general polynomial looks like $a_2 x^2 + a_1 x + a_0$, where each $a_i \in \mathbb{F}_3$.

In general, if $f$ is a polynomial of degree $n$, then $\mathbb{F}_p [x] / (f)$ will have $p^n$ elements for exactly this reason.

As a quick example of how to do reduction, let's reduce $x^4$ mod $x^3 - x^2 + 1$ in $\mathbb{F}_3[x]$.

The key insight is that since $x^3 - x^2 + 1 = 0$ in the quotient ring, we can rearrange this to see $x^3 = x^2 - 1$.

Now $x^4 = (x) (x^3)$, which, by the above argument is $(x) (x^2 - 1)$, or $x^3 - x$. Now we go again, since we still see an $x^3$, and this becomes $(x^2 - 1) - x$.

So then $x^4 = x^2 - x - 1$, and since we are working in a polynomial ring over $\mathbb{F}_3$, we can rewrite this as $x^2 + 2x + 2$, which would be the final answer.

Obviously it's tedious to have to repeatedly subtract off factors of $x^3$ and replace them, but thankfully we don't need to! In addition to the video I linked earlier, you can see a worked example for the division algorithm here which lets you efficiently compute $p(x)$ mod $f(x)$.

---

I hope this helps ^_^

Answer 2

I will try to keep my answer somewhat intuitive and digestible.

However, it's hard for me to comprehend the exact elements in this quotient ring.

The elements are strictly speaking equivalence classes, just like in any other quotient structure. In this case they are equivalence classes of polynomials, which are deemed equivalent when they have the same remainder when divided by $x^3 + 1$.

Now, you seem uncertain about what exactly those equivalence classes are.

So I'm wondering if there's an objective algorithm to determine the set of all remainders when a polynomial is divided by another polynomial.

I encourage you to look at the Wikipedia section on Euclidean division. Note that the theorem says that $\deg(r) < \deg(b)$. So right away that tells you will have as many equivalence classes as there are polynomials with degree less than $\deg(b)$. In your case, there are $2^3 = 8$ equivalence classes because you have two choices of coefficient for the constant term, two choices for the $x$ term, and two choices for the $x^2$ term. Generalizing to finite field $\mathbb F_p$ is simple.

You seem to be a bit fixated on polynomials as you would think of them in a calculus class; this isn't really relevant here.

If you are reasonably comfortable with a quotient like $\mathbb Z / 5$, then I encourage you to keep $\mathbb Z / 5$ in mind when you think about $\mathbb F_2[x]/(x^3 + 1)$. There are some fairly strong parallels. One of the attractive aspects of quotient rings of polynomials is how they parallel quotient rings of the integers, despite ostensibly being a much more complicated thing (polynomials compared to integers).