Polynomials with natural coefficients arising from exponentiation and sums

Question

Is there any nice characterization of the class of polynomials can be written with the following formula for some $c_i , d_i \in \mathbb{N}$? Alternatively, where can I read more about these? do they have a name? $$c_1 + \left( c_2 + \left( \dots (c_k + x^{d_k}) \dots \right)^{d_2} \right)^{d_1}$$

For instance, it is not possible to write $1 + x + x^2$ in this way, but it is possible to write $1 + 2x + x^2$ or $0 + x^3$.

For some context: two actions on the set of polynomials $A \times \mathbb{N}[x] \to \mathbb{N}[x]$, and $B \times \mathbb{N}[x] \to \mathbb{N}[x]$ can be combined into a single one $\left<A,B\right> \times \mathbb{N}[x] \to \mathbb{N}[x]$ that takes a word of elements on $A$ and $B$ and applies the multiple actions in order. In the case of multiplication and exponential, we can see that the class of polynomials $$c_1 \left( c_2 \left( \dots (c_k x^{d_k}) \dots \right)^{d_2} \right)^{d_1}$$ can be just described as the polynomials of the form $cx^d$. I do not expect such a simple characterization in the case of sums and exponentials, but I would like to know if this class of polynomials has been described or studied somewhere.

Answer 1

Some partial elementary observations that might lead to necessary conditions, probably not to a characterization.

If the nonconstant polynomial $p(x)$ has this form then the leading coefficient must be $1$ and you can make the constant term anything you like.

The quadratics are precisely the ones where the coefficient of $x$ is even.

The cubics are the ones of the form $$ c + 3t^2x + 3tx^2 + x^3 . $$ That is, those where the coefficient of $x^2$ is a multiple $t$ of $3$ and the coefficient of $x$ is $t$ times the coefficient of $x^2$.

For degree $n$, must the coefficient of $x^{n-1}$ be a multiple of $n$? How will it restrict some lower order coefficients?

Answer 2

You can figure out if a given polynomial is of that form by "going backwards". Let: $$(a_n x^n + a_{n-1} x^{n-1} + ...a_1 x^1 + a_0) = c_1 + \left( c_2 + \left( \dots (c_k + x^{d_k}) \dots \right)^{d_2} \right)^{d_1}$$ A valid polynomial will always be of the form: $$ c_1 + \left( c_2 + \left( \dots (c_k + x^{d_k}) \dots \right)^{d_2} \right)^{d_1} = x^n + (\frac{n c_{k}}{d_{k}}) x^{n-d_{k}} + ... = P(x)$$ where there are no non-zero intermediate powers between $x^n$ and $x^{n-d_k}$, and $c_{k} \neq 0$ except in the cases where the polynomial is $x^{d_1}$. We solve it by substituting $x = (y-c_k)^{\frac{1}{d_k}}$ in our polynomial from the computed values, checking if $P((y-c_k)^{\frac{1}{d_k}})$ is still an integer polynomial and $c_k$ is an integer, then solving recursively for : $$c_1 + \left( c_2 + \left( \dots (c_{k-1} + x^{d_{k-1}}) \dots \right)^{d_2} \right)^{d_1} = P((y-c_k)^{\frac{1}{d_k}})$$ until all pairs $(c_k,d_k)$ are computed.

Eg: $x^2 + x + 1$ gives $d_k = 1$ and $\frac{2c_k}{1} = 1$ which is non-integer $c_k$ so there are no solutions.

Eg: $P(x) = x^3 + 6x^{1} $ gives $d_k = 3-1 = 2$ and $\frac{3c_k}{2} = 6$ so $c_k = 4$. We then calculate $P((y-4)^{\frac{1}{2}}) = (y-4)^{\frac{3}{2}} + 3 (y-4)^{\frac{1}{2}} $. We see that the exponents are not natural so this cannot be further expanded. There are no solutions.

Eg: $P(x) = x^{20} + 12 x^{15} + 54 x^{10} + 108 x^5 + 83$. We see $d_k = 20-15 = 5 $. Also $\frac{20c_k}{5} = 12$ so $c_k = 3$. We compute $ P((y-3)^{\frac{1}{5}}) = y^4 + 2 = P_{2}(y)$. Applying the same procedure to $P_{2}$ we get $d_{k-1} = 4-0 = 4 $. and $\frac{4c_{k-1}}{4}=2$ so $c_{k-1} = 2$. Substituting again we see that $P_{2}((z-2)^{\frac{1}{4}}) = z$ . So our final result is: $((x^{5}+3)^4 + 2)$ .