Iyfjky

Question

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 $fleft[gright]$ the evaluation of the polynomial $f$ at $g$. This evaluation is defined as the image of $f$ under the $A$-algebra homomorphism $Aleft[xright] to Aleft[xright]$ which maps $x$ to $g$ (this homomorphism is unique, due to the universal property of the polynomial ring). Equivalently, this evaluation is $sum_igeq 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 $fleft[gright]$ is frequently denoted by $fleft(gright)$ in literature, but this $fleft(gright)$ notation is slightly ambiguous, because $fleft(gright)$ 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 $fleft[gright]$, and never by $fleft(gright)$.

Also note that every polynomial $fin Aleft[xright]$ satisfies $fleft[xright]=f$ and $xleft[fright]=f$.

Also, I let $mathbbN = left0,1,2,ldotsright$.

Theorem 1. Let $A$ be a commutative ring with $1$, and let $fin Aleft[xright]$ be a polynomial over $A$ in the variable $x$. Let us define a polynomial $f_nin Aleft[xright]$ for every $ninmathbbN$. Namely, we define $f_n$ by induction over $n$: We start with $f_0=x$, and continue with the recursive equation $f_n+1=fleft[f_nright]$ for every $ninmathbb 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
beginequation
prod_i=1^nleft(f_i-xright) mid prod_i=k+1^k+nleft(f_i-xright)
endequation
in the ring $Aleft[xright]$.

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
beginequation
left(f_m - xright) left(f_n - xright) mid left(f_mn - xright) left(f - xright)
endequation
in the ring $Aleft[xright]$.

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 .

score 3 · Answer 1 · 2018-09-15 15:56:03Z

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 $ageq b$, we have

beginequation
f_bleft[f_a-bright] = f_a .
labeldarij-proof.1
tag1
endequation

This fact appears trivial if you think of polynomials as functions (in which case $f_k$ is really just $underbracef 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 eqrefdarij-proof.1:

[Proof of eqrefdarij-proof.1. For every polynomial $gin Aleft[xright]$, let $R_g$ be the map $Aleft[xright]to Aleft[xright]$ mapping every $pin Aleft[xright]$ to $gleft[pright]$. 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^nleft(xright)$ for every $ninmathbb 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^0left(xright)=operatornameidleft(xright)=x$). For the induction step, assume that some $minmathbb N$ satisfies $f_m = R_f^mleft(xright)$. Then, $m+1$ satisfies

beginalign
f_m+1 &= fleft[f_mright]
qquad left(textby the recursive definition of $f_m+1$right) \
&= R_fleft(f_mright)
qquad left(textsince $R_fleft(f_mright)=fleft[f_mright]$ by the definition of $R_f$right) \
&= R_fleft(R_f^mleft(xright)right)
qquad left(textsince $f_m=R_f^mleft(xright)$right) \
&= R_f^m+1left(xright) .
endalign

This completes the induction.

We thus have shown that $f_n = R_f^nleft(xright)$ for every $ninmathbb N$. Since $f_n=f_nleft[xright]=R_f_nleft(xright)$ (because the definition of $R_f_n$ yields $R_f_nleft(xright)=f_nleft[xright]$), this rewrites as follows:

beginequation
R_f_nleft(xright) = R_f^nleft(xright)
qquad text for every $ninmathbb N$.
labeldarij-proof.1.5
tag2
endequation

Now we will prove that

beginequation
f_nleft[pright] = R_f^nleft(pright) text for every ninmathbb N text and every pin Aleft[xright] .
labeldarij-proof.2
tag3
endequation

[Proof of eqrefdarij-proof.2. Let $pin Aleft[xright]$ be any polynomial. By the universal property of the polynomial ring $Aleft[xright]$, there exists an $A$-algebra homomorphism $Phi : Aleft[xright] to Aleft[xright]$ such that $Phileft(xright) = p$. Consider this $Phi$. Then, for every polynomial $qin Aleft[xright]$, we have $Phileft(qright) = qleft[pright]$. (This is the reason why $Phi$ is commonly called the evaluation homomorphism at $p$.)

Now, every $A$-algebra homomorphism $Aleft[xright] to Aleft[xright]$ commutes with $R_g$ for every $gin Aleft[xright]$ (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 $gin Aleft[xright]$. 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 $Phileft(R_f^nleft(xright)right)=R_f^nleft(Phileft(xright)right)$. Since $Phileft(xright)=p$, this rewrites as $Phileft(R_f^nleft(xright)right)=R_f^nleft(pright)$. On the other hand, $Phi$ commutes with $R_f_n$, so that $Phileft(R_f_nleft(xright)right)=R_f_nleft(underbracePhileft(xright)_=pright)=R_f_nleft(pright)=f_nleft[pright]$ (by the definition of $R_f_n$). In view of eqrefdarij-proof.1.5, this rewrites as $Phileft(R_f^nleft(xright)right) = f_nleft[pright]$. Hence,

beginequation
f_nleft[pright] = Phileft(R_f^nleft(xright)right) = R_f^nleft(pright) ,
endequation

and thus eqrefdarij-proof.2 is proven.]

Now, we return to the proof of eqrefdarij-proof.1: Applying eqrefdarij-proof.2 to $n=b$ and $p=f_a-b$, we obtain $f_bleft[f_a-bright] = R_f^bleft(f_a-bright)$. Since $f_a-b = f_a-bleft[xright] = R_f^a-bleft(xright)$ (by eqrefdarij-proof.2, applied to $n=a-b$ and $p=x$), this rewrites as

beginequation
f_bleft[f_a-bright] = R_f^bleft(R_f^a-bleft(xright)right) = underbraceleft(R_f^bcirc R_f^a-bright)_=R_f^b+left(a-bright)=R_f^a left(xright) = R_f^aleft(xright) .
endequation

Compared with $f_a = f_aleft[xright] = R_f^aleft(xright)$ (by eqrefdarij-proof.2, applied to $n=a$ and $p=x$), this yields $f_bleft[f_a-bright] = f_a$. Thus, eqrefdarij-proof.1 is proven.]

Now here is something less obvious:

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

beginequation
f_a-b-xmid f_a-f_b qquad text in Aleft[xright] .
labeldarij-proof.3
tag4
endequation

[Proof of eqrefdarij-proof.3. Let $a$ and $b$ be nonnegative integers such that $ageq b$. Let $I$ be the ideal of $Aleft[xright]$ generated by the polynomial $f_a-b-x$. Then, $f_a-b-xin I$, so that $f_a-bequiv xmod 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 $pequiv qmod J$, and if $gin Aleft[xright]$ is a polynomial, then $gleft[pright]equiv gleft[qright]mod J$. (This fact is proven by seeing that $p^uequiv q^umod J$ for every $uinmathbb N$.) Applying this fact to $B=Aleft[xright]$, $J=I$, $p=f_a-b$, $q=x$ and $g=f_b$, we obtain $f_bleft[f_a-bright] equiv f_bleft[xright] = f_b mod I$. Due to eqrefdarij-proof.1, this becomes $f_a equiv f_b mod I$. Thus, $f_a-f_b in I$. Since $I$ is the ideal of $Aleft[xright]$ generated by $f_a-b-x$, this yields that $f_a-b-xmid f_a-f_b$. This proves eqrefdarij-proof.3.]

For any nonnegative integers $a$ and $b$ such that $ageq b$, let $f_amid b$ be some polynomial $hin Aleft[xright]$ such that $f_a-f_b = hcdotleft(f_a-b-xright)$. Such a polynomial $h$ exists according to eqrefdarij-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,

beginequation
f_a-f_b = f_amid b cdotleft(f_a-b-xright)
labeldarij-proof.4
tag5
endequation
for any nonnegative integers $a$ and $b$ such that $ageq b$.

Let us now define a polynomial $f_a,b in Aleft[xright]$ 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= begincases 1, & textif u=v;\ 0, & textif uneq vendcases$ for any two objects $u$ and $v$).

Induction step: Let $rinmathbb 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:

beginalign
f_r,b &= f_r-1,b + f_rmid 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 .
endalign

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

We now claim that

beginequation
f_a,b prod_i=1^bleft(f_i-xright) = prod_i=a-b+1^aleft(f_i-xright)
labeldarij-proof.5
tag6
endequation

for any nonnegative integers $a$ and $b$ such that $ageq b$.

[Proof of eqrefdarij-proof.5. We will prove eqrefdarij-proof.5 by induction over $a$:

Induction base: For $a=0$, proving eqrefdarij-proof.5 is very easy (notice that $0=ageq b$ entails $b=0$, and use $f_0,0 = 1$). Thus, we can consider the induction base as completed.

Induction step: Let $rinmathbb N$ be positive. Assume that eqrefdarij-proof.5 holds for any nonnegative integers $a$ and $b$ such that $ageq b$ and $a=r-1$. Now let us prove eqrefdarij-proof.5 for any nonnegative integers $a$ and $b$ such that $ageq b$ and $a=r$:

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

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

Case 1: We have $b=0$.

Case 2: We have $1leq bleq 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

beginequation
f_r,0 = f_r-1,0 + f_rmid r-0 underbracef_r-1, 0-1_=f_r-1,-1 = 0 = f_r-1,0 .
endequation

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

beginequation
f_r-1,0 prod_i=1^0left(f_i-xright) = prod_i=r-1-0+1^r-1left(f_i-xright) .
endequation

Since both products $prod_i=1^0left(f_i-xright)$ and $prod_i=r-1-0+1^r-1left(f_i-xright)$ 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,

beginequation
f_r,0 underbraceprod_i=1^0left(f_i-xright)_=left(textempty productright)=1 = f_r,0 = f_r-1,0 = 1
endequation

and

beginequation
prod_i=r-0+1^rleft(f_i-xright) = left(textempty productright) = 1 .
endequation

Comparing these equalities yields

beginequation
f_r,0 prod_i=1^0left(f_i-xright) = prod_i=r-0+1^rleft(f_i-xright) .
endequation

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

beginequation
f_a,b prod_i=1^bleft(f_i-xright) = prod_i=a-b+1^aleft(f_i-xright) .
endequation

In other words, we have proven eqrefdarij-proof.5 for our $a$ and $b$ in Case 1.

Next let us consider Case 2: In this case, $1leq bleq 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 eqrefdarij-proof.5 to $r-1$ and $b-1$ instead of $a$ and $b$ (since we assumed that eqrefdarij-proof.5 holds for any nonnegative integers $a$ and $b$ such that $ageq b$ and $a=r-1$). This yields the identity

beginequation
f_r-1,b-1 prod_i=1^b-1left(f_i-xright) = prod_i=left(r-1right)-left(b-1right)+1^r-1left(f_i-xright) .
endequation

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

beginequation
f_r-1,b-1 prod_i=1^b-1left(f_i-xright) = prod_i=r-b+1^r-1left(f_i-xright) .
endequation

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

beginequation
f_r-1,b prod_i=1^bleft(f_i-xright) = prod_i=left(r-1right)-b+1^r-1left(f_i-xright) .
endequation

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

beginequation
f_r-1,b prod_i=1^bleft(f_i-xright) = prod_i=r-b^r-1left(f_i-xright) = left(f_r-b-xright) prod_i=r-b+1^r-1left(f_i-xright)
endequation

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

Since $0leq bleq r$, we have $0leq r-bleq r$, and eqrefdarij-proof.4 (applied to $r$ and $r-b$ instead of $a$ and $b$) yields

beginequation
f_r-f_r-b = f_rmid r-bcdot left(f_r-left(r-bright)-xright) .
endequation

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

beginequation
f_r-f_r-b = f_rmid r-bcdot left(f_b-xright) .
labeldarij-proof.5.5
tag7
endequation

Since $0leq bleq r$, the recursive definition of $f_r,b$ yields

beginequation
f_r,b = f_r-1,b + f_rmid r-b f_r-1,b-1 .
endequation

Thus,

beginalign
& f_r,b prod_i=1^bleft(f_i-xright) \
&= left(f_r-1,b + f_rmid r-b f_r-1,b-1right) prod_i=1^bleft(f_i-xright) \
&= f_r-1,b prod_i=1^bleft(f_i-xright) + f_rmid r-b f_r-1,b-1 underbraceprod_i=1^bleft(f_i-xright)_=left(f_b-xright)prod_i=1^b-1left(f_i-xright) \
& = f_r-1,b prod_i=1^bleft(f_i-xright) + f_rmid r-b f_r-1,b-1 left(f_b-xright) prod_i=1^b-1left(f_i-xright) \
& = underbracef_r-1,b prod_i=1^bleft(f_i-xright)_= left(f_r-b-xright) prod_i=r-b+1^r-1left(f_i-xright) + underbracef_rmid r-b cdot left(f_b-xright)_substack=f_r-f_r-b \ text(by eqrefdarij-proof.5.5) underbracef_r-1,b-1 prod_i=1^b-1left(f_i-xright)_= prod_i=r-b+1^r-1left(f_i-xright) \
&= left(f_r-b-xright) prod_i=r-b+1^r-1left(f_i-xright) + left(f_r-f_r-bright) prod_i=r-b+1^r-1left(f_i-xright) \
&= underbraceleft( left(f_r-b-xright) + left(f_r-f_r-bright) right)_=f_r-x prod_i=r-b+1^r-1left(f_i-xright) \
&= left(f_r-xright) prod_i=r-b+1^r-1left(f_i-xright) = prod_i=r-b+1^rleft(f_i-xright) .
endalign

Since $r=a$, this rewrites as

beginequation
f_a,b prod_i=1^bleft(f_i-xright) = prod_i=a-b+1^aleft(f_i-xright) .
endequation

In other words, we have proven eqrefdarij-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 eqrefdarij-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 eqrefdarij-proof.5 requires $ageq b$). Therefore, we need a different way to prove the equality

beginequation
f_r-1,b prod_i=1^bleft(f_i-xright) = left(f_r-b-xright) prod_i=r-b+1^r-1left(f_i-xright)
labeldarij-proof.6
tag8
endequation

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 eqrefdarij-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 eqrefdarij-proof.6 equals $0$. Since both the left hand side and the right hand side of eqrefdarij-proof.6 equal $0$, it is now clear that the equality eqrefdarij-proof.6 is true, and thus we can proceed as in Case 2. Hence, eqrefdarij-proof.5 is proven for our $a$ and $b$ in Case 3.

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

Thus, the induction proof of eqrefdarij-proof.5 is done.]

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

beginequation
f_k+n,n prod_i=1^nleft(f_i-xright) = prod_i=left(k+nright)-n+1^k+nleft(f_i-xright)
endequation

(by eqrefdarij-proof.5, applied to $a=k+n$ and $b=n$). Since $left(k+nright)-n=k$, this simplifies to

beginequation
f_k+n,n prod_i=1^nleft(f_i-xright) = prod_i=k+1^k+nleft(f_i-xright) .
endequation

This immediately yields Theorem 1. $blacksquare$

score 1 · Answer 2 · 2018-09-15 16:44:35Z

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_mright)$, 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+bvright)p = auunderbracep_=be + bvunderbracep_=ad = aube + bvad = ableft(ue+vdright)$. 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
beginequation
f_a-b-xmid f_a-f_b qquad text in Aleft[xright] .
endequation

Proof of Lemma 4. Lemma 4 is precisely the relation eqrefdarij-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 $Aleft[xright]$.

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-bright) - x mid f_a - f_a-b$. In view of $a-left(a-bright) = 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 $Aleft[xright]$ belong to the ideal $left< f_a-b - x, f_b - x right>$. Hence, their sum $left(f_a - f_a-bright) + left(f_a-b - xright)$ must belong to this ideal as well. In other words,
beginequation
left(f_a - f_a-bright) + left(f_a-b - xright) in left< f_a-b - x, f_b - x right> .
endequation
In view of $left(f_a - f_a-bright) + left(f_a-b - xright) = 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,
beginequation
left< f_a - x, f_b - x right> subseteq left< f_a-b - x, f_b - x right> .
labeldarij-proof2.1
tag11
endequation

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 $Aleft[xright]$ belong to the ideal $left< f_a - x, f_b - x right>$. Hence, their difference $left(f_a - xright) - left(f_a - f_a-bright)$ must belong to this ideal as well. In other words,
beginequation
left(f_a - xright) - left(f_a - f_a-bright) in left< f_a - x, f_b - x right> .
endequation
In view of $left(f_a - xright) - left(f_a - f_a-bright) = 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,
beginequation
left< f_a-b - x, f_b - x right> subseteq left< f_a - x, f_b - x right> .
endequation
Combining this with eqrefdarij-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,
beginequation
left< f_a - x, f_b - x right> = left< f_gcdleft(a,bright) - x right>
endequation
as ideals of $Aleft[xright]$.

Here, we follow the convention that $gcdleft(0,0right) = 0$. Note that
beginequation
gcdleft(a,bright) = gcdleft(a-b,bright)
qquad textfor all integers $a$ and $b$.
labeldarij.proof2.gcd-inva
tag12
endequation

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
beginequation
left< f_a - x, f_b - x right> = left< f_gcdleft(a,bright) - x right> .
labeldarij.proof2.l6.pf.1
tag13
endequation

Now, fix two nonnegative integers $a$ and $b$ satisfying $a+b = N$. We want to prove that
beginequation
left< f_a - x, f_b - x right> = left< f_gcdleft(a,bright) - x right> .
labeldarij.proof2.l6.pf.2
tag14
endequation
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,
beginequation
left< f_a - x, f_0 - x right> = left< f_a - x, 0 right> = left< f_a - x right> = left< f_gcdleft(a,0right) - x right>
endequation
(since $a = gcdleft(a,0right)$). Hence, eqrefdarij.proof2.l6.pf.2 holds if $b = 0$. Thus, for the rest of the proof of eqrefdarij.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-bright) + b = a < a+b = N$. Moreover, $a-b$ is a nonnegative integer (since $a geq b$). Therefore, eqrefdarij.proof2.l6.pf.1 (applied to $a-b$ instead of $a$) yields
beginequation
left< f_a-b - x, f_b - x right> = left< f_gcdleft(a-b,bright) - x right> .
endequation
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
beginequation
left< f_a - x, f_b - x right> = left< f_gcdleft(a-b,bright) - x right> .
endequation
In view of $gcdleft(a-b,bright) = gcdleft(a,bright)$ (which follows from eqrefdarij.proof2.gcd-inva), this rewrites as
beginequation
left< f_a - x, f_b - x right> = left< f_gcdleft(a,bright) - x right> .
endequation
Thus, eqrefdarij.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 eqrefdarij.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 $Aleft[xright]$.

Proof of Lemma 7. We have $gcdleft(p,qright) = p$ (since $p mid q$).
Applying Lemma 6 to $a = p$ and $b = q$, we obtain
beginequation
left< f_p - x, f_q - x right> = left< f_gcdleft(p,qright) - x right> = left< f_p - x right>
endequation
(since $gcdleft(p,qright) = p$). Hence,
beginequation
f_q - x in left< f_p - x, f_q - x right> = left< f_p - x right> .
endequation
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, $gcdleft(m,nright) = 1$ (since $m$ and $n$ are coprime). Hence, $f_gcdleft(m,nright) = 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
beginequation
left< f_m - x, f_n - x right> = left< f_gcdleft(m,nright) - x right> = left< f - x right>
endequation
(since $f_gcdleft(m,nright) = 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 $Aleft[xright]$ such that $f - x = left(f_m - xright) u + left(f_n - x right) v$. Consider these $u$ and $v$.

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

Mike Earnest 18.2k11850 · Answer 3 · 2018-09-15 18:45:40Z

Notation and Lemmas

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

Lemma 1: $
fc[(a+b)] = fc[a][fc[b]]
$

We also have

Lemma 2: For all $n,kge 0$, $fc[k]-x$ divides $fc[(n+k)]-fc[n]$

Proof: Writing $fc[n]=sum_h=0^d a_h x^h$, then
$$
fc[(n+k)]-fc[n]=fc[n][fc[k]] - fc[n]=sum_h=0^d a_h((fc[k])^h-x^h)
$$
Since $fc[k]-x$ divides $(fc[k])^h-x^h$ for all $hge 0$, it follows $fc[k]-x$ divides $fc[(n+k)]-fc[n]$.

Lemma 3: $fc[n]-x$ divides $fc[mn]-x$

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

Theorem 1

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

Therefore, we can assume $fc[i]neq x$ for all $ile n$. This means
$$
binomn+kn_f:=fracprod_i=k+1^k+n(fc[i]-x)prod_i=1^n (fc[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
$$
binomn+kn_f = fracfc[(n+k)]-fc[n]fc[k]-xbinomn+k-1n_f+binomn+k-1n-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<langledef>rangle<fc[n]-x> + <fc[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 $fc[n]-x$ and $fc[m]-x$, proving the inclusion $<fc[n]-x> + <fc[m]-x>subseteq <f-x>$. For the other inclusion, assume that $n>m$, note that by induction we have
$$
<f-x>
=<fc[(n-m)]-x>+<fc[m]-x>
subseteq<fc[n]-fc[(n-m)]>+<fc[n]-x>+<fc[m]-x>
$$
Since Lemma 2 impies $<fc[n]-fc[(n-m)]>subset <fc[m]-x>$, the claim follows.

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

Thanks. From a quick look, this looks very much like my argument, except you're assuming more than I do about $A$. In particular, $Aleft[xright]$ 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. — 10 mins ago
@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 :) — 6 mins ago
Yeah, in a sense this is the honest version of my argument, while my posts give the technically correct version. — 5 mins ago

score 3 · Answer 4 · 2018-09-15 15:56:03Z