# Polynomials with natural coefficients arising from exponentiation and sums

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 \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.

• Interesting question. It might help to know where it comes from (edit to tell us.) The leading coefficient must bte $1$ (except for the constants). – Ethan Bolker Jul 21 at 12:33
• compound interest ? – Roddy MacPhee Jul 21 at 12:55

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?

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)$$ .