5
$\begingroup$

This is a question I will answer myself immediately by repeating one of my old AoPS posts, since the latter post no longer renders on AoPS.

Convention. In the following, whenever $A$ is a commutative ring with $1$, and $f$ and $g$ are two polynomials over $A$ in the variable $x$, then we denote by $f\left[g\right]$ the evaluation of the polynomial $f$ at $g$. This evaluation is defined as the image of $f$ under the $A$-algebra homomorphism $A\left[x\right] \to A\left[x\right]$ which maps $x$ to $g$ (this homomorphism is unique, due to the universal property of the polynomial ring). Equivalently, this evaluation is $\sum_{i\geq 0} f_i g^i$, where $f_0, f_1, f_2, \ldots$ are the coefficients of the polynomial $f$ before $x^0, x^1, x^2, \ldots$, respectively.

Note that the evaluation $f\left[g\right]$ is frequently denoted by $f\left(g\right)$ in literature, but this $f\left(g\right)$ notation is slightly ambiguous, because $f\left(g\right)$ can also mean the product of the polynomials $f$ and $g$ (in particular, this often happens when $g$ is a complicated sum, so that the parentheses around $g$ are required), and this is an entirely different thing. Thus we are always going to denote the evaluation by $f\left[g\right]$, and never by $f\left(g\right)$.

Also note that every polynomial $f\in A\left[x\right]$ satisfies $f\left[x\right]=f$ and $x\left[f\right]=f$.

Also, I let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$.

Theorem 1. Let $A$ be a commutative ring with $1$, and let $f\in A\left[x\right]$ be a polynomial over $A$ in the variable $x$. Let us define a polynomial $f_n\in A\left[x\right]$ for every $n\in\mathbb{N}$. Namely, we define $f_n$ by induction over $n$: We start with $f_0=x$, and continue with the recursive equation $f_{n+1}=f\left[f_n\right]$ for every $n\in\mathbb N$. [Note that I hesitate to denote $f_n$ by $f^n$ since $f^n$ already stands for "$n$-th power of $f$ with respect to multiplication of polynomials", and that's something different from $f_n$.] Then, for any nonnegative integers $n$ and $k$, we have \begin{equation} \prod_{i=1}^n\left(f_i-x\right) \mid \prod_{i=k+1}^{k+n}\left(f_i-x\right) \end{equation} in the ring $A\left[x\right]$.

Theorem 2. Let $A$, $f$ and $f_n$ be as in Theorem 1. Then, for any two coprime positive integers $m$ and $n$, we have \begin{equation} \left(f_m - x\right) \left(f_n - x\right) \mid \left(f_{mn} - x\right) \left(f - x\right) \end{equation} in the ring $A\left[x\right]$.

The question is to prove these two theorems.

Theorem 1 has been posted by gammaduc at https://artofproblemsolving.com/community/c7h412796 ; Theorem 2 has been posted by gammaduc at https://artofproblemsolving.com/community/c7h412797 .

$\endgroup$
3
$\begingroup$

Proof of Theorem 1

[Remark: The following proof was written in 2011 and only mildly edited now. There are things in it that I would have done better if I were to rewrite it.]

Proof of Theorem 1. First, let us prove something seemingly obvious: Namely, we will prove that for any nonnegative integers $a$ and $b$ such that $a\geq b$, we have

\begin{equation} f_b\left[f_{a-b}\right] = f_a . \label{darij-proof.1} \tag{1} \end{equation}

This fact appears trivial if you think of polynomials as functions (in which case $f_k$ is really just $\underbrace{f \circ f \circ \cdots \circ f}_{k \text{ times}}$); the only problem with this approach is that polynomials are not functions. Thus, let me give a proof of \eqref{darij-proof.1}:

[Proof of \eqref{darij-proof.1}. For every polynomial $g\in A\left[x\right]$, let $R_g$ be the map $A\left[x\right]\to A\left[x\right]$ mapping every $p\in A\left[x\right]$ to $g\left[p\right]$. Note that this map $R_g$ is not a ring homomorphism (in general), but a polynomial map.

Next we notice that $f_n = R_f^n\left(x\right)$ for every $n\in\mathbb N$. In fact, this can be proven by induction over $n$: The induction base (the case $n=0$) is trivial (since $f_0=x$ and $R_f^0\left(x\right)=\operatorname{id}\left(x\right)=x$). For the induction step, assume that some $m\in\mathbb N$ satisfies $f_m = R_f^m\left(x\right)$. Then, $m+1$ satisfies

\begin{align} f_{m+1} &= f\left[f_m\right] \qquad \left(\text{by the recursive definition of $f_{m+1}$}\right) \\ &= R_f\left(f_m\right) \qquad \left(\text{since $R_f\left(f_m\right)=f\left[f_m\right]$ by the definition of $R_f$}\right) \\ &= R_f\left(R_f^m\left(x\right)\right) \qquad \left(\text{since $f_m=R_f^m\left(x\right)$}\right) \\ &= R_f^{m+1}\left(x\right) . \end{align}

This completes the induction.

We thus have shown that $f_n = R_f^n\left(x\right)$ for every $n\in\mathbb N$. Since $f_n=f_n\left[x\right]=R_{f_n}\left(x\right)$ (because the definition of $R_{f_n}$ yields $R_{f_n}\left(x\right)=f_n\left[x\right]$), this rewrites as follows:

\begin{equation} R_{f_n}\left(x\right) = R_f^n\left(x\right) \qquad \text{ for every $n\in\mathbb N$.} \label{darij-proof.1.5} \tag{2} \end{equation}

Now we will prove that

\begin{equation} f_n\left[p\right] = R_f^n\left(p\right) \text{ for every } n\in\mathbb N \text{ and every } p\in A\left[x\right] . \label{darij-proof.2} \tag{3} \end{equation}

[Proof of \eqref{darij-proof.2}. Let $p\in A\left[x\right]$ be any polynomial. By the universal property of the polynomial ring $A\left[x\right]$, there exists an $A$-algebra homomorphism $\Phi : A\left[x\right] \to A\left[x\right]$ such that $\Phi\left(x\right) = p$. Consider this $\Phi$. Then, for every polynomial $q\in A\left[x\right]$, we have $\Phi\left(q\right) = q\left[p\right]$. (This is the reason why $\Phi$ is commonly called the evaluation homomorphism at $p$.)

Now, every $A$-algebra homomorphism $A\left[x\right] \to A\left[x\right]$ commutes with $R_g$ for every $g\in A\left[x\right]$ (this is just a formal way to state the known fact that every $A$-algebra homomorphism commutes with every polynomial map). Applying this to the homomorphism $\Phi$, we conclude that $\Phi$ commutes with $R_g$ for every $g\in A\left[x\right]$. Thus, in particular, $\Phi$ commutes with $R_{f_n}$ and with $R_f$. Since $\Phi$ commutes with $R_f$, it is clear that $\Phi$ also commutes with $R_f^n$, and thus $\Phi\left(R_f^n\left(x\right)\right)=R_f^n\left(\Phi\left(x\right)\right)$. Since $\Phi\left(x\right)=p$, this rewrites as $\Phi\left(R_f^n\left(x\right)\right)=R_f^n\left(p\right)$. On the other hand, $\Phi$ commutes with $R_{f_n}$, so that $\Phi\left(R_{f_n}\left(x\right)\right)=R_{f_n}\left(\underbrace{\Phi\left(x\right)}_{=p}\right)=R_{f_n}\left(p\right)=f_n\left[p\right]$ (by the definition of $R_{f_n}$). In view of \eqref{darij-proof.1.5}, this rewrites as $\Phi\left(R_f^n\left(x\right)\right) = f_n\left[p\right]$. Hence,

\begin{equation} f_n\left[p\right] = \Phi\left(R_f^n\left(x\right)\right) = R_f^n\left(p\right) , \end{equation}

and thus \eqref{darij-proof.2} is proven.]

Now, we return to the proof of \eqref{darij-proof.1}: Applying \eqref{darij-proof.2} to $n=b$ and $p=f_{a-b}$, we obtain $f_b\left[f_{a-b}\right] = R_f^b\left(f_{a-b}\right)$. Since $f_{a-b} = f_{a-b}\left[x\right] = R_f^{a-b}\left(x\right)$ (by \eqref{darij-proof.2}, applied to $n=a-b$ and $p=x$), this rewrites as

\begin{equation} f_b\left[f_{a-b}\right] = R_f^b\left(R_f^{a-b}\left(x\right)\right) = \underbrace{\left(R_f^b\circ R_f^{a-b}\right)}_{=R_f^{b+\left(a-b\right)}=R_f^a} \left(x\right) = R_f^a\left(x\right) . \end{equation}

Compared with $f_a = f_a\left[x\right] = R_f^a\left(x\right)$ (by \eqref{darij-proof.2}, applied to $n=a$ and $p=x$), this yields $f_b\left[f_{a-b}\right] = f_a$. Thus, \eqref{darij-proof.1} is proven.]

Now here is something less obvious:

For any nonnegative integers $a$ and $b$ such that $a\geq b$, we have

\begin{equation} f_{a-b}-x\mid f_a-f_b \qquad \text{ in } A\left[x\right] . \label{darij-proof.3} \tag{4} \end{equation}

[Proof of \eqref{darij-proof.3}. Let $a$ and $b$ be nonnegative integers such that $a\geq b$. Let $I$ be the ideal of $A\left[x\right]$ generated by the polynomial $f_{a-b}-x$. Then, $f_{a-b}-x\in I$, so that $f_{a-b}\equiv x\mod I$.

We recall a known fact: If $B$ is a commutative $A$-algebra, if $J$ is an ideal of $B$, if $p$ and $q$ are two elements of $B$ satisfying $p\equiv q\mod J$, and if $g\in A\left[x\right]$ is a polynomial, then $g\left[p\right]\equiv g\left[q\right]\mod J$. (This fact is proven by seeing that $p^u\equiv q^u\mod J$ for every $u\in\mathbb N$.) Applying this fact to $B=A\left[x\right]$, $J=I$, $p=f_{a-b}$, $q=x$ and $g=f_b$, we obtain $f_b\left[f_{a-b}\right] \equiv f_b\left[x\right] = f_b \mod I$. Due to \eqref{darij-proof.1}, this becomes $f_a \equiv f_b \mod I$. Thus, $f_a-f_b \in I$. Since $I$ is the ideal of $A\left[x\right]$ generated by $f_{a-b}-x$, this yields that $f_{a-b}-x\mid f_a-f_b$. This proves \eqref{darij-proof.3}.]

For any nonnegative integers $a$ and $b$ such that $a\geq b$, let $f_{a\mid b}$ be some polynomial $h\in A\left[x\right]$ such that $f_a-f_b = h\cdot\left(f_{a-b}-x\right)$. Such a polynomial $h$ exists according to \eqref{darij-proof.3}, but needs not be unique (e. g., if $f=x$ or $a=b$, it can be arbitrary), so we may have to take choices here. Thus,

\begin{equation} f_a-f_b = f_{a\mid b} \cdot\left(f_{a-b}-x\right) \label{darij-proof.4} \tag{5} \end{equation} for any nonnegative integers $a$ and $b$ such that $a\geq b$.

Let us now define a polynomial $f_{a,b} \in A\left[x\right]$ for any nonnegative integers $a$ and $b$. Namely, we define this polynomial by induction over $a$:

Induction base: For $a=0$, let $f_{a,b}$ be $\delta_{0,b}$ (where $\delta$ means Kronecker's delta, defined by $\delta_{u,v}= \begin{cases} 1, & \text{if }u=v;\\ 0, & \text{if }u\neq v\end{cases}$ for any two objects $u$ and $v$).

Induction step: Let $r\in\mathbb N$ be positive. If $f_{r-1,b}$ is defined for all $b \in \mathbb N$, then let us define $f_{r,b}$ for all $b \in \mathbb N$ as follows:

\begin{align} f_{r,b} &= f_{r-1,b} + f_{r\mid r-b} f_{r-1,b-1} \text{ if } 0 \leq b \leq r \text{ (where $f_{r-1,-1}$ means $0$)}; \\ f_{r,b} &= 0 \text{ if } b > r . \end{align}

This way, we inductively have defined $f_{a,b}$ for all nonnegative integers $a$ and $b$.

We now claim that

\begin{equation} f_{a,b} \prod_{i=1}^b\left(f_i-x\right) = \prod_{i=a-b+1}^{a}\left(f_i-x\right) \label{darij-proof.5} \tag{6} \end{equation}

for any nonnegative integers $a$ and $b$ such that $a\geq b$.

[Proof of \eqref{darij-proof.5}. We will prove \eqref{darij-proof.5} by induction over $a$:

Induction base: For $a=0$, proving \eqref{darij-proof.5} is very easy (notice that $0=a\geq b$ entails $b=0$, and use $f_{0,0} = 1$). Thus, we can consider the induction base as completed.

Induction step: Let $r\in\mathbb N$ be positive. Assume that \eqref{darij-proof.5} holds for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r-1$. Now let us prove \eqref{darij-proof.5} for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r$:

Let $a$ and $b$ be nonnegative integers such that $a\geq b$ and $a=r$.

Then, $r=a\geq b$. Thus, $b$ is a nonnegative integer satisfying $b\leq r$. This shows that we must be in one of the following three cases:

Case 1: We have $b=0$.

Case 2: We have $1\leq b\leq r-1$.

Case 3: We have $b=r$.

Let us first consider Case 1: In this case, $b=0$. The recursive definition of $f_{r,b}$ yields

\begin{equation} f_{r,0} = f_{r-1,0} + f_{r\mid r-0} \underbrace{f_{r-1, 0-1}}_{=f_{r-1,-1} = 0} = f_{r-1,0} . \end{equation}

We can apply \eqref{darij-proof.5} to $r-1$ and $0$ instead of $a$ and $b$ (since we assumed that \eqref{darij-proof.5} holds for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r-1$). This yields the identity

\begin{equation} f_{r-1,0} \prod_{i=1}^0\left(f_i-x\right) = \prod_{i=r-1-0+1}^{r-1}\left(f_i-x\right) . \end{equation}

Since both products $\prod_{i=1}^0\left(f_i-x\right)$ and $\prod_{i=r-1-0+1}^{r-1}\left(f_i-x\right)$ are equal to $1$ (since they are empty products), this simplifies to $f_{r-1,0} \cdot 1 = 1$, so that $f_{r-1,0} = 1$. Now,

\begin{equation} f_{r,0} \underbrace{\prod_{i=1}^0\left(f_i-x\right)}_{=\left(\text{empty product}\right)=1} = f_{r,0} = f_{r-1,0} = 1 \end{equation}

and

\begin{equation} \prod_{i=r-0+1}^{r}\left(f_i-x\right) = \left(\text{empty product}\right) = 1 . \end{equation}

Comparing these equalities yields

\begin{equation} f_{r,0} \prod_{i=1}^0\left(f_i-x\right) = \prod_{i=r-0+1}^{r}\left(f_i-x\right) . \end{equation}

Since $0=b$ and $r=a$, this rewrites as

\begin{equation} f_{a,b} \prod_{i=1}^b\left(f_i-x\right) = \prod_{i=a-b+1}^{a}\left(f_i-x\right) . \end{equation}

In other words, we have proven \eqref{darij-proof.5} for our $a$ and $b$ in Case 1.

Next let us consider Case 2: In this case, $1\leq b\leq r-1$. Hence, $0 \leq b-1 \leq r-1$ and $r-1 \geq b \geq b-1$.

In particular, $r-1$ and $b-1$ are nonnegative integers satisfying $r-1 \geq b-1$. Hence, we can apply \eqref{darij-proof.5} to $r-1$ and $b-1$ instead of $a$ and $b$ (since we assumed that \eqref{darij-proof.5} holds for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r-1$). This yields the identity

\begin{equation} f_{r-1,b-1} \prod_{i=1}^{b-1}\left(f_i-x\right) = \prod_{i=\left(r-1\right)-\left(b-1\right)+1}^{r-1}\left(f_i-x\right) . \end{equation}

Since $\left(r-1\right)-\left(b-1\right)+1=r-b+1$, this simplifies to

\begin{equation} f_{r-1,b-1} \prod_{i=1}^{b-1}\left(f_i-x\right) = \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) . \end{equation}

On the other hand, $r-1$ and $b-1$ are nonnegative integers satisfying $r-1 \geq b$. Thus, we can apply \eqref{darij-proof.5} to $r-1$ and $b$ instead of $a$ and $b$ (since we assumed that \eqref{darij-proof.5} holds for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r-1$). This gives us

\begin{equation} f_{r-1,b} \prod_{i=1}^{b}\left(f_i-x\right) = \prod_{i=\left(r-1\right)-b+1}^{r-1}\left(f_i-x\right) . \end{equation}

Since $\left(r-1\right)-b+1=r-b$, this rewrites as

\begin{equation} f_{r-1,b} \prod_{i=1}^{b}\left(f_i-x\right) = \prod_{i=r-b}^{r-1}\left(f_i-x\right) = \left(f_{r-b}-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) \end{equation}

(because $r-1 \geq r-b$).

Since $0\leq b\leq r$, we have $0\leq r-b\leq r$, and \eqref{darij-proof.4} (applied to $r$ and $r-b$ instead of $a$ and $b$) yields

\begin{equation} f_r-f_{r-b} = f_{r\mid r-b}\cdot \left(f_{r-\left(r-b\right)}-x\right) . \end{equation}

Since $r-\left(r-b\right)=b$, this simplifies to

\begin{equation} f_r-f_{r-b} = f_{r\mid r-b}\cdot \left(f_b-x\right) . \label{darij-proof.5.5} \tag{7} \end{equation}

Since $0\leq b\leq r$, the recursive definition of $f_{r,b}$ yields

\begin{equation} f_{r,b} = f_{r-1,b} + f_{r\mid r-b} f_{r-1,b-1} . \end{equation}

Thus,

\begin{align} & f_{r,b} \prod_{i=1}^b\left(f_i-x\right) \\ &= \left(f_{r-1,b} + f_{r\mid r-b} f_{r-1,b-1}\right) \prod_{i=1}^b\left(f_i-x\right) \\ &= f_{r-1,b} \prod_{i=1}^b\left(f_i-x\right) + f_{r\mid r-b} f_{r-1,b-1} \underbrace{\prod_{i=1}^b\left(f_i-x\right)}_{=\left(f_b-x\right)\prod_{i=1}^{b-1}\left(f_i-x\right)} \\ & = f_{r-1,b} \prod_{i=1}^b\left(f_i-x\right) + f_{r\mid r-b} f_{r-1,b-1} \left(f_b-x\right) \prod_{i=1}^{b-1}\left(f_i-x\right) \\ & = \underbrace{f_{r-1,b} \prod_{i=1}^b\left(f_i-x\right)}_{= \left(f_{r-b}-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) } + \underbrace{f_{r\mid r-b} \cdot \left(f_b-x\right)}_{\substack{=f_r-f_{r-b} \\ \text{(by \eqref{darij-proof.5.5})}}} \underbrace{f_{r-1,b-1} \prod_{i=1}^{b-1}\left(f_i-x\right)}_{= \prod_{i=r-b+1}^{r-1}\left(f_i-x\right)} \\ &= \left(f_{r-b}-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) + \left(f_r-f_{r-b}\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) \\ &= \underbrace{\left( \left(f_{r-b}-x\right) + \left(f_r-f_{r-b}\right) \right)}_{=f_r-x} \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) \\ &= \left(f_r-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) = \prod_{i=r-b+1}^{r}\left(f_i-x\right) . \end{align}

Since $r=a$, this rewrites as

\begin{equation} f_{a,b} \prod_{i=1}^b\left(f_i-x\right) = \prod_{i=a-b+1}^{a}\left(f_i-x\right) . \end{equation}

In other words, we have proven \eqref{darij-proof.5} for our $a$ and $b$ in Case 2.

Next let us consider Case 3: In this case, $b=r$.

In this case, we proceed exactly as in Case 2, except for one small piece of the argument: Namely, in Case 2 we were allowed to apply \eqref{darij-proof.5} to $r-1$ and $b$ instead of $a$ and $b$, but now in Case 3 we are not allowed to do this anymore (because \eqref{darij-proof.5} requires $a\geq b$). Therefore, we need a different way to prove the equality

\begin{equation} f_{r-1,b} \prod_{i=1}^{b}\left(f_i-x\right) = \left(f_{r-b}-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) \label{darij-proof.6} \tag{8} \end{equation}

in Case 3. Here is such a way:

By the inductive definition of $f_{r-1,b}$, we have $f_{r-1,b}=0$ (since $b=r>r-1$). Thus, the left hand side of \eqref{darij-proof.6} equals $0$. On the other hand, $b=r$ yields $f_{r-b}=f_{r-r}=f_0=x$, so that $f_{r-b}-x=0$. Thus, the right hand side of \eqref{darij-proof.6} equals $0$. Since both the left hand side and the right hand side of \eqref{darij-proof.6} equal $0$, it is now clear that the equality \eqref{darij-proof.6} is true, and thus we can proceed as in Case 2. Hence, \eqref{darij-proof.5} is proven for our $a$ and $b$ in Case 3.

We have thus proven that \eqref{darij-proof.5} holds for our $a$ and $b$ in each of the three possible cases 1, 2 and 3. Thus, \eqref{darij-proof.5} is proven for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r$. This completes the induction step.

Thus, the induction proof of \eqref{darij-proof.5} is done.]

Now, any nonnegative integers $n$ and $k$ satisfy

\begin{equation} f_{k+n,n} \prod_{i=1}^n\left(f_i-x\right) = \prod_{i=\left(k+n\right)-n+1}^{k+n}\left(f_i-x\right) \end{equation}

(by \eqref{darij-proof.5}, applied to $a=k+n$ and $b=n$). Since $\left(k+n\right)-n=k$, this simplifies to

\begin{equation} f_{k+n,n} \prod_{i=1}^n\left(f_i-x\right) = \prod_{i=k+1}^{k+n}\left(f_i-x\right) . \end{equation}

This immediately yields Theorem 1. $\blacksquare$

$\endgroup$
3
$\begingroup$

Proof of Theorem 2

The proof of Theorem 2 I shall give below is merely a generalization of GreenKeeper's proof at AoPS, with all uses of specific properties of $A$ excised.

If $a_1, a_2, \ldots, a_m$ are some elements of a commutative ring $R$, then we let $\left< a_1, a_2, \ldots, a_m \right>$ denote the ideal of $R$ generated by $a_1, a_2, \ldots, a_m$. (This is commonly denoted by $\left(a_1, a_2, \ldots, a_m\right)$, but I want a less ambiguous notation.)

Lemma 3. Let $R$ be a commutative ring. Let $a, b, c, u, v, p$ be six elements of $R$ such that $a \mid p$ and $b \mid p$ and $c = au+bv$. Then, $ab \mid cp$.

Proof of Lemma 3. We have $a \mid p$; thus, $p = ad$ for some $d \in R$. Consider this $d$.

We have $b \mid p$; thus, $p = be$ for some $e \in R$. Consider this $e$.

Now, from $c = au+bv$, we obtain $cp = \left(au+bv\right)p = au\underbrace{p}_{=be} + bv\underbrace{p}_{=ad} = aube + bvad = ab\left(ue+vd\right)$. Hence, $ab \mid cp$. This proves Lemma 3. $\blacksquare$

Lemma 4. Let $A$, $f$ and $f_n$ be as in Theorem 1. Then, for any nonnegative integers $a$ and $b$ such that $a \geq b$, we have \begin{equation} f_{a-b}-x\mid f_a-f_b \qquad \text{ in } A\left[x\right] . \end{equation}

Proof of Lemma 4. Lemma 4 is precisely the relation \eqref{darij-proof.3} from the proof of Theorem 1; thus, we have already shown it. $\blacksquare$

Lemma 5. Let $A$, $f$ and $f_n$ be as in Theorem 1. Let $a$ and $b$ be nonnegative integers such that $a \geq b$. Then, $\left< f_a - x, f_b - x \right> = \left< f_{a-b} - x, f_b - x \right>$ as ideals of $A\left[x\right]$.

Proof of Lemma 5. We have $a \geq b$, thus $0 \leq b \leq a$. Hence, $0 \leq a-b \leq a$. Therefore, $a-b$ is a nonnegative integer such that $a \geq a-b$. Hence, Lemma 4 (applied to $a-b$ instead of $b$) yields $f_{a-\left(a-b\right)} - x \mid f_a - f_{a-b}$. In view of $a-\left(a-b\right) = b$, this rewrites as $f_b - x \mid f_a - f_{a-b}$. In other words, $f_a - f_{a-b} \in \left< f_b - x \right>$.

Hence, $f_a - f_{a-b} \in \left< f_b - x \right> \subseteq \left< f_{a-b} - x, f_b - x \right>$. Thus, both elements $f_a - f_{a-b}$ and $f_{a-b} - x$ of $A\left[x\right]$ belong to the ideal $\left< f_{a-b} - x, f_b - x \right>$. Hence, their sum $\left(f_a - f_{a-b}\right) + \left(f_{a-b} - x\right)$ must belong to this ideal as well. In other words, \begin{equation} \left(f_a - f_{a-b}\right) + \left(f_{a-b} - x\right) \in \left< f_{a-b} - x, f_b - x \right> . \end{equation} In view of $\left(f_a - f_{a-b}\right) + \left(f_{a-b} - x\right) = f_a - x$, this rewrites as $f_a - x \in \left< f_{a-b} - x, f_b - x \right>$. Combining this with the obvious fact that $f_b - x \in \left< f_{a-b} - x, f_b - x \right>$, we conclude that both generators of the ideal $\left< f_a - x, f_b - x \right>$ belong to $\left< f_{a-b} - x, f_b - x \right>$. Hence, \begin{equation} \left< f_a - x, f_b - x \right> \subseteq \left< f_{a-b} - x, f_b - x \right> . \label{darij-proof2.1} \tag{11} \end{equation}

On the other hand, $f_a - f_{a-b} \in \left< f_b - x \right> \subseteq \left< f_a - x, f_b - x \right>$. Thus, both elements $f_a - f_{a-b}$ and $f_a - x$ of $A\left[x\right]$ belong to the ideal $\left< f_a - x, f_b - x \right>$. Hence, their difference $\left(f_a - x\right) - \left(f_a - f_{a-b}\right)$ must belong to this ideal as well. In other words, \begin{equation} \left(f_a - x\right) - \left(f_a - f_{a-b}\right) \in \left< f_a - x, f_b - x \right> . \end{equation} In view of $\left(f_a - x\right) - \left(f_a - f_{a-b}\right) = f_{a-b} - x$, this rewrites as $f_{a-b} - x \in \left< f_a - x, f_b - x \right>$. Combining this with the obvious fact that $f_b - x \in \left< f_a - x, f_b - x \right>$, we conclude that both generators of the ideal $\left< f_{a-b} - x, f_b - x \right>$ belong to $\left< f_a - x, f_b - x \right>$. Hence, \begin{equation} \left< f_{a-b} - x, f_b - x \right> \subseteq \left< f_a - x, f_b - x \right> . \end{equation} Combining this with \eqref{darij-proof2.1}, we obtain $\left< f_a - x, f_b - x \right> = \left< f_{a-b} - x, f_b - x \right>$. This proves Lemma 5. $\blacksquare$

Lemma 6. Let $A$, $f$ and $f_n$ be as in Theorem 1. Let $a$ and $b$ be two nonnegative integers. Then, \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a,b\right)} - x \right> \end{equation} as ideals of $A\left[x\right]$.

Here, we follow the convention that $\gcd\left(0,0\right) = 0$. Note that \begin{equation} \gcd\left(a,b\right) = \gcd\left(a-b,b\right) \qquad \text{for all integers $a$ and $b$.} \label{darij.proof2.gcd-inva} \tag{12} \end{equation}

Proof of Lemma 6. We shall prove Lemma 6 by strong induction on $a+b$:

Induction step: Fix a nonnegative integer $N$. Assume (as the induction hypothesis) that Lemma 6 holds whenever $a+b < N$. We must now show that Lemma 6 holds whenever $a+b = N$.

We have assumed that Lemma 6 holds whenever $a+b < N$. In other words, if $a$ and $b$ are two nonnegative integers satisfying $a+b < N$, then \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a,b\right)} - x \right> . \label{darij.proof2.l6.pf.1} \tag{13} \end{equation}

Now, fix two nonnegative integers $a$ and $b$ satisfying $a+b = N$. We want to prove that \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a,b\right)} - x \right> . \label{darij.proof2.l6.pf.2} \tag{14} \end{equation} Since our situation is symmetric in $a$ and $b$, we can WLOG assume that $a \geq b$ (since otherwise, we can just swap $a$ with $b$). Assume this.

We have $f_0 = x$ and thus $f_0 - x = 0$. Hence, \begin{equation} \left< f_a - x, f_0 - x \right> = \left< f_a - x, 0 \right> = \left< f_a - x \right> = \left< f_{\gcd\left(a,0\right)} - x \right> \end{equation} (since $a = \gcd\left(a,0\right)$). Hence, \eqref{darij.proof2.l6.pf.2} holds if $b = 0$. Thus, for the rest of the proof of \eqref{darij.proof2.l6.pf.2}, we WLOG assume that we don't have $b = 0$. Hence, $b > 0$, so that $a+b > a$. Therefore, $\left(a-b\right) + b = a < a+b = N$. Moreover, $a-b$ is a nonnegative integer (since $a \geq b$). Therefore, \eqref{darij.proof2.l6.pf.1} (applied to $a-b$ instead of $a$) yields \begin{equation} \left< f_{a-b} - x, f_b - x \right> = \left< f_{\gcd\left(a-b,b\right)} - x \right> . \end{equation} Comparing this with the equality $\left< f_a - x, f_b - x \right> = \left< f_{a-b} - x, f_b - x \right>$ (which follows from Lemma 5), we obtain \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a-b,b\right)} - x \right> . \end{equation} In view of $\gcd\left(a-b,b\right) = \gcd\left(a,b\right)$ (which follows from \eqref{darij.proof2.gcd-inva}), this rewrites as \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a,b\right)} - x \right> . \end{equation} Thus, \eqref{darij.proof2.l6.pf.2} is proven.

Now, forget that we fixed $a$ and $b$. We thus have shown that if $a$ and $b$ are two nonnegative integers satisfying $a+b = N$, then \eqref{darij.proof2.l6.pf.2} holds. In other words, Lemma 6 holds whenever $a+b = N$. This completes the induction step. Hence, Lemma 6 is proven by induction. $\blacksquare$

Lemma 7. Let $A$, $f$ and $f_n$ be as in Theorem 1. Let $p$ and $q$ be nonnegative integers such that $p \mid q$ (as integers). Then, $f_p - x \mid f_q - x$ in $A\left[x\right]$.

Proof of Lemma 7. We have $\gcd\left(p,q\right) = p$ (since $p \mid q$). Applying Lemma 6 to $a = p$ and $b = q$, we obtain \begin{equation} \left< f_p - x, f_q - x \right> = \left< f_{\gcd\left(p,q\right)} - x \right> = \left< f_p - x \right> \end{equation} (since $\gcd\left(p,q\right) = p$). Hence, \begin{equation} f_q - x \in \left< f_p - x, f_q - x \right> = \left< f_p - x \right> . \end{equation} In other words, $f_p - x \mid f_q - x$. This proves Lemma 7. $\blacksquare$

Proof of Theorem 2. Let $m$ and $n$ be two coprime positive integers. Thus, $\gcd\left(m,n\right) = 1$ (since $m$ and $n$ are coprime). Hence, $f_{\gcd\left(m,n\right)} = f_1 = f$.

Lemma 7 (applied to $p=m$ and $q = mn$) yields $f_m - x \mid f_{mn} - x$ (since $m \mid mn$ as integers). Lemma 7 (applied to $p=n$ and $q = mn$) yields $f_n - x \mid f_{mn} - x$ (since $n \mid mn$ as integers).

But Lemma 6 (applied to $a = m$ and $b = n$) yields \begin{equation} \left< f_m - x, f_n - x \right> = \left< f_{\gcd\left(m,n\right)} - x \right> = \left< f - x \right> \end{equation} (since $f_{\gcd\left(m,n\right)} = f$). Hence, $f - x \in \left< f - x \right> = \left< f_m - x, f_n - x \right>$. In other words, there exist two elements $u$ and $v$ of $A\left[x\right]$ such that $f - x = \left(f_m - x\right) u + \left(f_n - x \right) v$. Consider these $u$ and $v$.

Now, Lemma 3 (applied to $R = A \left[x\right]$, $a = f_m - x$, $b = f_n - x$, $c = f - x$ and $p = f_{mn} - x$) yields $\left(f_m - x\right) \left(f_n - x\right) \mid \left(f - x\right) \left(f_{mn} - x\right) = \left(f_{mn} - x\right) \left(f - x\right)$. This proves Theorem 2. $\blacksquare$

$\endgroup$
2
$\begingroup$

Notation and Lemmas

I will let $$\def\c[#1]{^{\circ #1}}f\c[n]:= f_n$$ Letting $f\circ g=f[g]$, I claim $\circ$ is associative. This follows because any polynomial defines a map $f:A\to A$, and the polynomial corresponding the composition of the maps $f,g:A\to A$ can be shown to be $f\circ g$. This immediately implies that

Lemma 1: $ f\c[(a+b)] = f\c[a][f\c[b]] $

We also have

Lemma 2: For all $n,k\ge 0$, $f\c[k]-x$ divides $f\c[(n+k)]-f\c[n]$

Proof: Writing $f\c[n]=\sum_{h=0}^d a_h x^h$, then $$ f\c[(n+k)]-f\c[n]=f\c[n][f\c[k]] - f\c[n]=\sum_{h=0}^d a_h((f\c[k])^h-x^h) $$ Since $f\c[k]-x$ divides $(f\c[k])^h-x^h$ for all $h\ge 0$, it follows $f\c[k]-x$ divides $f\c[(n+k)]-f\c[n]$.

Lemma 3: $f\c[n]-x$ divides $f\c[mn]-x$

Proof: Apply Lemma 2 to each summand in $$ (f\c[mn]-f\c[(m-1)n])+(f\c[(m-1)n]-f\c[(m-2)n])+\dots+(f\c[n]-x). $$

Theorem 1

First, I deal with the trivial case where $f\c[i]=x$ for some $1\le i \le n$. This implies by induction on $m$ that $f\c[mi]=x$ for all $m\ge 0$, since $f\c[mi]=f\c[(m-1)i]\circ f\c[i]=f\c[(m-1)i]\circ x=f\c[(m-1)i]=x.$ Since there exists an $m$ for which $k+1\le mi\le k+n$, it follows that the product $$ \prod_{i=k+1}^{k+n} (f\c[i]-x) $$ contains a zero, so we are done.

Therefore, we can assume $f\c[i]\neq x$ for all $i\le n$. This means $$ \binom{n+k}n_f:=\frac{\prod_{i=k+1}^{k+n}(f\c[i]-x)}{\prod_{i=1}^n (f\c[i]-x)} $$ is a well defined element of the fraction field $A(x)$ of $A[x]$. We prove this is actually a polynomial by induction on $\min(n,k)$. The base case $\min(n,k)=0$ follows because when $n=0$, both products are empty so the ratio is $\frac11=1$, and when $n=k$, both products are equal so the ratio is again $1$. By straightforward algebraic manipulations, you can show when $\min(n,k)\ge 1$, then $$ \binom{n+k}n_f = \frac{f\c[(n+k)]-f\c[n]}{f\c[k]-x}\binom{n+k-1}n_f+\binom{n+k-1}{n-1}_f, $$

so by the induction hypothesis and Lemma 2, this is a polynomial.

Theorem 2

First, I claim that for any coprime integers $m,n$, we have the following equality of ideals: $$ \def\<{\langle}\def\>{\rangle}\<f\c[n]-x\> + \<f\c[m]-x\>=\<f-x\> $$ The proof is by induction on $\max(n,m)$, the base case where $\max(n,m)=1$ being obvious.

By Lemma 3, we have $f-x$ divides both $f\c[n]-x$ and $f\c[m]-x$, proving the inclusion $\<f\c[n]-x\> + \<f\c[m]-x\>\subseteq \<f-x\>$. For the other inclusion, assume that $n>m$, note that by induction we have $$ \<f-x\> =\<f\c[(n-m)]-x\>+\<f\c[m]-x\> \subseteq\<f\c[n]-f\c[(n-m)]\>+\<f\c[n]-x\>+\<f\c[m]-x\> $$ Since Lemma 2 impies $\<f\c[n]-f\c[(n-m)]\>\subset \<f\c[m]-x\>$, the claim follows.

The claim implies that $$ (f\c[n]-x)p(x)+(f\c[m]-x)q(x)=f-x $$ for some polynomials $p$ and $q$. Multiplying both sides by $(f\c[mn]-x)$, we get $$ (f\c[mn]-x)(f\c[n]-x)p(x)+(f\c[mn]-x)(f\c[m]-x)q(x)=(f-x)(f\c[mn]-x) $$ Since Lemma 3 implies $f\c[m]-x$ divides $f\c[mn]-x$, we have $(f\c[m]-x)(f\c[n]-x)$ divides $(f\c[mn]-x)(f\c[n]-x)p(x)$. Similarly, $(f\c[m]-x)(f\c[n]-x)$ divides $(f\c[mn]-x)(f\c[m]-x)q(x)$. Since $(f\c[m]-x)(f\c[n]-x)$ divides both summands on the LHS of the above equation, it divides the RHS, as desired.

$\endgroup$
  • 1
    $\begingroup$ Thanks. From a quick look, this looks very much like my argument, except you're assuming more than I do about $A$. In particular, $A\left[x\right]$ doesn't need to have a fraction field in my setting, so I have to keep all the denominators on the left hand side of the $\mid$ sign. Also, if you want to prove the associativity of $\circ$ by regarding polynomials as functions, you should let them act on an arbitrary commutative $A$-algebra (as natural transformations) rather than on $A$, since $A$ might be too small to tell the difference. $\endgroup$ – darij grinberg Sep 15 '18 at 18:58
  • $\begingroup$ @darijgrinberg Thanks for the feedback, I agree. I was hoping that a much more streamlined proof would be possible, but I lost generality. Either way it was fun to write :) $\endgroup$ – Mike Earnest Sep 15 '18 at 19:02
  • $\begingroup$ Yeah, in a sense this is the honest version of my argument, while my posts give the technically correct version. $\endgroup$ – darij grinberg Sep 15 '18 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.