How to show associativity of multiplication of polynomials in $R[x]$, where $R$ is a commutative, associative ring

Question

Suppose that we have a commutative, associative ring $R$ which we use to generate the polynomial $R[x]$. Then $p(x) \in R[x]$ is of the form $p(x) = \sum_{i=0}^n a_i x^i$ for some $n \in \mathbb{N}$.

Now, I wish to understand why $R[x]$ is itself a commutative, associative ring. I am happy showing all of the necessary properties to show this to be the case, except for associativity of multiplication.

I understand that given $p(x), q(x) \in R[x]$, such that

$$p(x) = \sum_{i=0}^n a_i x^i, \ \ q(x) = \sum_{i=0}^m b_i x^i$$

for some $m, n \in \mathbb{N}$, where $a_i, b_i \in R, \forall i$, we may (quite naturally) define their product

$$p(x)q(x)= \left(pq \right)(x):=\sum_{k=0}^{n+m} \sum_{i+j=k, \ i,j \in \mathbb{N}_0} a_i b_j x^k.$$

However, I get rather lost when I introduce another polynomial, $r(x) \in R[x]$ such that

$$r(x) = \sum_{i=0}^o c_i x^i$$

for some $o \in \mathbb{N}$, where $c_i \in R, \forall i$ and attempt to show that

$$\left(p(x) q(x) \right) r(x) = p(x) \left(q(x) r(x) \right).$$

Would any kindly soul be able to show me how?

Answer 1

I agree with the structural approaches suggested in the other answers. But I don't see where's the problem with a direct computation? It isn't horrible at all and actually also works for formal power series.

I will write $p_i$ for the coefficient of $x^i$ in $p$. We have by definition

$$(p(qr))_n = \sum_{i+j=n} p_i (qr)_j = \sum_{i+j=n} p_i \sum_{u+v=j} q_u r_v = \sum_{i+j=n} ~\sum_{u+v=j} p_i (q_u r_v)$$

By a simple substitution this equals

$$\sum_{i+u+v=n} p_i (q_u r_v).$$ Now use associativity in $R$ and the same reasoning backwards, then you get $((pq)r)_n$.

Answer 2

Instead of directly showing that two expressions for triple products with different orders are the same, it might be both easier and more illuminating to show that the $k$-th coefficient in the product of any number of polynomials taken in any order is the sum of all products of coefficients, one from each factor, whose powers add up to $k$. This implies associativity.

We can prove this by structural induction over the factors. So let some multiple product of polynomials be given, and focus on the "outermost" multiplication, the one to be applied last. We have

$$p(x) = \sum_{i=0}^n a_i x^i, \ \ q(x) = \sum_{i=0}^m b_i x^i\;,$$

where $p(x)$ and $q(x)$ are the results of carrying out all the other multiplications. By the induction hypothesis, $a_i$ is the sum of all products of coefficients, one from each factor in the left factor, whose powers add up to $i$, and the same for $b_i$ and the right factor. Now the $k$-th coefficient in the product is by definition

$$\sum_{i+j=k, \ i,j \in \mathbb{N}_0} a_i b_j\;.$$

Clearly when we multiply all these products out using distributivity, we'll get every product of coefficients, one from each factor, whose powers add up to $k$, and we'll get it exactly once. That completes the induction.

Answer 3

Lately, I've been wondering about a proof of this. Here's my approach.

First I need the following two lemmas; and let $(G,+)$ be a commutative monoid and $0$ be its identity.

Lemma 1: For any $f:X \to G$ and $g:Y \to G$, and $A,B$ finite subsets of $X$ and $Y$ respectively, we have

$$ \sum_{x \in A} f(x) = \sum_{x \in B} g(x) $$

there always exist a bijection $\sigma : A \to B$, such that $f(x)=g(\sigma(x))$ for all $x \in A$.

Lemma 2: Let be $A$ a finite set, $B_x$ be finite sets for all $x \in A$, and $f_x$ be functions such that $f_x(B_x) \subseteq G$ for all $x \in A$. We have $$ \sum_{x \in A} \left( \sum_{y \in B_x} f_x(y) \right) = \sum_{(x,y) \in B} f_x(y) $$ where $B=\{ (x,y) \, : \, x \in A, \, y \in B_{x} \}$.

Proof: Use induction and considering the following facts:

$i) \sum_{x \in \emptyset} f(x) = 0$

$ii) \sum_{x \in A} = f(c)+\sum_{x \in A \backslash \{c\}} f(x)$ for some $c \in A$, $A$ is always a finite non-empty set.

Now let $R$ be a ring, $0$ be its additive identity and consider $R[x]$ as the equivalent definition of the polynomial ring

$$ R[x] = \{\, a \in R^{\mathbb{N}} \, : \, \text{there is exist a} \, n \in \mathbb{N} \, \text{such that} \, a_k=0 \, \text{for all} \, k>n \} $$

with sum $$ (a+b)_n = a_n + b_n $$ and product $$ (a \cdot b)_n = \sum_{0 \leq k \leq n} a_k b_{n-k} $$ for all $a,b \in R[x]$ and $n \in \mathbb{N}$.

As $(R[x],+)$ is an abelian group, it's clear that it is a commutative monoid. Now let $a,b,c \in R[x]$. For $n \in \mathbb{N}$ we have

$$ \begin{align} (a \cdot (b \cdot c))_n &= \sum_{0 \leq i \leq n} a_i (b \cdot c)_{n-i} \\ &= \sum_{0 \leq i \leq n} a_i \left(\sum_{0 \leq j \leq n-i}b_{j}c_{(n-i)-j}\right) \\ &= \sum_{0 \leq i \leq n} \left( \sum_{0 \leq j \leq n-i} a_{i} (b_{j}c_{(n-i)-j} ) \right) \\ &= \sum_{(i,j) \in A} f(i,j) \end{align} $$ where $$ A= \{ \, (i,j) \, : 0 \leq i \leq n,\, 0 \leq j \leq n-i \, \} $$ and $$ f(i,j)=a_i(b_jc_{n-(i+j)})\, $$ this for the second lemma. To the other side $$ \begin{align} ((a \cdot b) \cdot c)_n &= \sum_{0 \leq i \leq n} (a \cdot b)_i c_{n-i} \\ &= \sum_{0 \leq i \leq n} \left(\sum_{0 \leq j \leq i}a_{j}b_{i-j}\right) c_{n-i} \\ &= \sum_{0 \leq i \leq n} \left(\sum_{0 \leq j \leq i}(a_{j}b_{i-j}) c_{n-i} \right) \\ &= \sum_{(i,j) \in B} g(i,j) \end{align} $$ where $$ B= \{ \, (i,j) \, : 0 \leq i \leq n,\, 0 \leq j \leq i \, \} $$ and $$ g(i,j)=(a_jb_{i-j})c_{n-i} $$ this for the second lemma.

Now consider $\sigma : A \to B$ such that $\sigma(i,j)=(i+j,i)$. We claim that $\sigma$ is a bijection. First, let's show that $\sigma$ is well defined. If $(i,j) \in A$ then $0 \leq i \leq n$ and $0 \leq j \leq n-i$, so $0 \leq i+j \leq n$ y $0 \leq i \leq i+j$, thus $\sigma(i,j) \in B$. If $(i,j) \in B$, we have $0\leq i \leq n$ and $0 \leq j \leq i$, then $0 \leq j \leq n$ and $0 \leq i-j \leq n-j$, so $(j,i-j) \in A$ and $\sigma(j,i-j)=(j+(i-j),j)=(i,j)$, thus $\sigma$ is surjective. If $\sigma(i,j)=\sigma(r,s)$ then $(i+j,i)=(r+s,r)$, so $i=r$ and $j=s$, $(i,j)=(r,s)$, thus $\sigma$ is injective, therefore $\sigma$ is a bijection; and since

$$ g(\sigma(i,j))=g(i+j,i)=(a_ib_{(i+j)-i})c_{n-(i+j)}= (a_ib_{j})c_{n-(i+j)}=a_i(b_jc_{n-(i+j)})=f(i,j) $$

then by the first lemma we have $$ \sum_{(i,j) \in A} f(i,j) = \sum_{(i,j) \in B} g(i,j) $$ then $$ (a \cdot (b \cdot c))_n = ((a \cdot b) \cdot c)_n $$ and finally $$ (a \cdot (b \cdot c)) = ((a \cdot b) \cdot c) $$ $$\tag*{$\blacksquare$}$$

I know it, it's a very long proof for something that seems trivial, but at least I'm pleased with the argument.

Answer 4

I've been wondering about the same thing, two years later. Here's a proof outline I came up with that limits the horrible sums at the expense of requiring a lemma and three different inductive steps. In the following, all polynomials are over a ring $R$.

Lemma: Let $p(x)$ and $q(x)$ be polynomials, let $a\in R$ and $n\in \Bbb N_{>0}$. Then $ax^n(p(x)q(x)) = (ax^np(x))q(x)$, $p(x)(ax^nq(x))=(p(x)ax^n)q(x)$, and $p(x)(q(x)ax^n) = (p(x)q(x))ax^n$.

Proof: Fill in the blank.

Theorem: Polynomial multiplication is associative.

Proof: Proceed by induction on the structure or degrees of the three polynomials, using the product ordering. That is, show that assuming the inductive hypothesis:

• Whenever three polynomials $p(x),q(x),r(x)$ have degrees $d,e,f$, $p(x)(q(x)r(x))=(p(x)q(x))r(x)$

allows you to prove that whenever either:

• $p$ has degree $d$, $q$ has degree $e$, and $r$ has degree $f+1$,
• $p$ has degree $d$, $q$ has degree $e+1$, and $r$ has degree $f$, or
• $p$ has degree $d+1$, $q$ has degree $e$, and $r$ has degree $f$,

then $p(x)(q(x)r(x))=(p(x)q(x))r(x)$.

I'm hoping someone else has a way to improve/flesh out this approach, so I'm making it CW.