Consider the polynomial $f(x)=x^3+3x$ over $\mathbb{Z}$.

I am trying to find a polynomial $g(x)$ $(\neq f^{\circ n})$ of any degree (or series) without constant term which commutes with $f$ (or any iteration $f^{\circ n}, ~n \geq 1)$ under composition.

Trivially, any $g(x)=x$, is another polynomial (or series) commutes with $f(x)$.

By hand it seems to be laborious.

Suppose I start with an investigation if there are degree $2$ polynomial $g(x)=ax+bx^2$ such that $f \circ g=g\circ f$. Then \begin{align} &f(g(x))=f(ax+bx^2)=3(ax+bx^2)+(ax+bx^2)^3=3ax+3bx^2+a^3x^3+3a^2bx^4+3ab^2x^5+b^3x^6, \\ &g(f(x))=g(x^3+3x)=a(x^3+3x)+b(x^3+3x)^2=3ax+ax^3+bx^6+6bx^4+9bx^2 \end{align}

Comparing both equations, we get $b=0$ and $a=a^3 \Rightarrow a=\pm 1$. In this case $g(x)=\pm 1$, the trivial one.

Suppose I start with an investigation if there are degree $3$ polynomial $g(x)=ax+bx^2+cx^3$ such that $f \circ g=g\circ f$. Then \begin{align} &f(g(x))=f(ax+bx^2+cx^3)=3(ax+bx^2+cx^3)+(ax+bx^2+cx^3)^3=3ax+3bx^2+3cx^3+c^3x^9+3bc^2x^8 \hspace{3cm}+(3ac^2+3b^2c)x^7+(6abc + b^3)x^6 + (3a^2c + 3ab^2)x^5 + 3a^2bx^4 + a^3x^3, \\ &g(f(x))=g(x^3+3x)=a(x^3+3x)+b(x^3+3x)^2+c(x^3+3x)^3=3ax+ax^3+2bx^6+6bx^4+9bx^2+cx^9+9cx^7+27cx^5+27cx^3 \end{align} Comparing both sides we get $b=0$ and the following equations: \begin{align} a^3-a=24c, \\ a^2c=9c, \\ 3ac^2=9c,\\ c^3=c. \end{align} Solving these, we see $c^3=c$ and $3ac^2=a^2c$. These two gives us $c=0$ or $c=\pm 1$. If $c \neq 0$, then $a=\pm 3$. Thus $g(x)=\pm (3x+ x^3)$, which is equivalent to $f(x)$ upto signs.

Suppose I start with an investigation if there are degree $4$ polynomial $g(x)=ax+bx^2+cx^3+dx^4$ such that $f \circ g=g\circ f$. Then it becomes laborious.

Is there any way to find non-trivial $g$ with the help of PARI/GP or SAGE ?

Edit 1: According to the hints given by @achille hui, I have found that $g(x)=-5x-5x^3-x^5$ commutes with $x^3+3x$. However, I am looking for an polynomial whose first degree coefficient is $3$ or multiple of $3$. I would appreciate one such example.

Edit 2: But I need to find the polynomial with degree one coefficient, a multiple of $3$ and it is certainly possible as $f$ commutes with its iteration and each iteration has the degree one coefficient , a multiple of 3

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Dec 22, 2021 at 13:15

1 Answer 1


We have $$f(x):=x^3+3x$$ and you already found $$h(x)=x^5+5x^3+5x$$ with $$h(f(x))=f(h(x))$$ but the coefficient of $x$ of $h$ is not divisible by $3$. But $$g(x)=h(f(f(x)))$$ has this property because

$$g(x)=h(f(f(x)))=f(h(f(x))=(h(f(x))^3+3(h(f(x))$$ and the lowest non vanishing power of $(h(f(x))^3$ is $x^3$ and all coefficients of $x$ in $3(h(f(x))$ are divisible by $3$.

And $$g(f(x))=h(f(f(f(x)))=f(h(f(f(x)))=f(g(x))$$

(I missed that g(x):=h(f(x)) already has the required property- It is equal to the degree 15 polynomial I calculated in the second part of this post)

The polynomial $g(x)$ is

$${{x}^{45}}+45 {{x}^{43}}+945 {{x}^{41}}+12300 {{x}^{39}} \\+111150 {{x}^{37}}+740259 {{x}^{35}}+3764565 {{x}^{33}}+14945040 {{x}^{31}}\\ +46955700 {{x}^{29}}+117679100 {{x}^{27}}+236030652 {{x}^{25}}+378658800 {{x}^{23}}\\ +483841800 {{x}^{21}}+488494125 {{x}^{19}}+384942375 {{x}^{17}}+232676280 {{x}^{15}}\\ +105306075 {{x}^{13}}+34512075 {{x}^{11}}+7811375 {{x}^{9}}+1138500 {{x}^{7}}\\ +95634 {{x}^{5}}+3795 {{x}^{3}}+45 x$$ which can be factored to

$$x\, \left( {{x}^{2}}+3\right) \, \left( {{x}^{4}}+5 {{x}^{2}}+5\right) \, \left( {{x}^{6}}+6 {{x}^{4}}+9 {{x}^{2}}+3\right) \,\\ \left( {{x}^{8}}+7 {{x}^{6}}+14 {{x}^{4}}+8 {{x}^{2}}+1\right) \, \\ \left( {{x}^{24}}+24 {{x}^{22}}+252 {{x}^{20}}+1519 {{x}^{18}}\\ +5796 {{x}^{16}}+14553 {{x}^{14}}+24206 {{x}^{12}}+26169 {{x}^{10}}\\ +17523 {{x}^{8}}+6623 {{x}^{6}}+1182 {{x}^{4}}+72 {{x}^{2}}+1\right) $$

Here is a smaller one

${{x}^{15}}+15 {{x}^{13}}+90 {{x}^{11}}+275 {{x}^{9}}+450 {{x}^{7}}+378 {{x}^{5}}+140 {{x}^{3}}+15 x$

I calculated some polynomials with Maxima. The following commute with $f$ and are the only one with nonnegative leading coefficient and a highest power less or equal $15$:

$$0$$ $$x$$ $$x^3+3x$$ $$x^5+5x^3+5x$$ $$x^7+7x^5+14x^3+7x$$ $${{x}^{9}}+9 {{x}^{7}}+27 {{x}^{5}}+30 {{x}^{3}}+9 x$$ $${{x}^{11}}+11 {{x}^{9}}+44 {{x}^{7}}+77 {{x}^{5}}+55 {{x}^{3}}+11 x$$ $${{x}^{13}}+13 {{x}^{11}}+65 {{x}^{9}}+156 {{x}^{7}}+182 {{x}^{5}}+91 {{x}^{3}}+13 x$$ $${{x}^{15}}+15 {{x}^{13}}+90 {{x}^{11}}+275 {{x}^{9}}+450 {{x}^{7}}+378 {{x}^{5}}+140 {{x}^{3}}+15 x$$

Note that

$${{x}^{9}}+9 {{x}^{7}}+27 {{x}^{5}}+30 {{x}^{3}}+9 x=f(f(x))$$ and $${{x}^{15}}+15 {{x}^{13}}+90 {{x}^{11}}+275 {{x}^{9}}+450 {{x}^{7}}+378 {{x}^{5}}+140 {{x}^{3}}+15 x = h(f(x))$$ where $$h(x)=x^5+5x^3+5$$

If we call these polynomials (excluding 0) $h_1,h_3,h_5,\ldots, h_{15}$, so the index $i$ of $h_i$ is the degree of the polynomials, the following holds:


Here is an online version of Maxima. This is how I calculated the coefficients of $h_9$ by comparing the coefficients of $(f(g(x))$ and $g(f(x))$ N:9 is the degree of the polynomial g(x). The statement starting with empty checks if all coefficients of the difference $(f(g(x))-g(f(x))$ become $0$. If the result of this statement is false, the solution is invalid. This happens if we choose $N$ and even number.

emptyp(sublist(coeff_list,lambda([t], is(t#0)))),solutions;

Here is the same algorithm implemented as SmPy scirpt.

These polynomials are related to Chebyshev Polynomials as some commenters pointed out. In the comments alex.jordan linked to A082985 and Lubin mentions the comments of achillehui of the OPs questions, which contains references to a paper on this topic by F.J.Ritt, Permutable Rational Functions.

  • 1
    $\begingroup$ See oeis.org/A082985. $\endgroup$
    – 2'5 9'2
    Dec 21, 2021 at 23:18
  • $\begingroup$ Ahh! It is excellent. I already found out the f(f(x)) one. But you found lots. I really appreciate your help $\endgroup$
    – MAS
    Dec 22, 2021 at 0:32
  • 3
    $\begingroup$ These are Čebyšev polynomials of some sort. It’s Ritt’s Theorem, referenced by @achillehui. $\endgroup$
    – Lubin
    Dec 22, 2021 at 4:30
  • $\begingroup$ @mirace173, just one comment. You have created $g(x)=9x+30x^3+27x^5+9x^7+{{x}^{9}}$. Let $h(x)=x^m, \ m \geq 2$. Can you help me to create another polynomial $q(x)$ such that $(g(x))^m=q(x^m)$. For $m=1$, it is trivial taking $g(x)=q(x)$. But for $m \geq 2$, I don't know $\endgroup$
    – MAS
    Dec 22, 2021 at 7:15
  • 1
    $\begingroup$ @learner I seems that the number of terms becomes too large to be handled by the program, In you case your polynomial is f(f(x)), where f(x)=x^3+6*x^2+9*x, so you can try to find a g, such that g(f(x))=f(g(x)) and this g is commutative with your polynomial too, The Maxima command polydecomp(x*(x+3)^2*(x*(x+3)^2+3)^2,x) will calculate f. $\endgroup$
    – miracle173
    Dec 23, 2021 at 7:39

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.