# Can composition of integer polynomial and rational polynomial with a non-integer coefficient result in integer polynomial?

Can we find two polynomials $$p(x)$$ and $$q(x)$$, where $$p(x)$$ is a non-constant monic polynomial over integers and $$q(x)$$ is a monic polynomial over rationals with at least one non-integer coefficient, such that their composition $$p(q(x))$$ is a polynomial over integers? If not, how to prove it?

For example let $$q(x)=x^2+\frac{1}{2}x+1$$ and $$p(x)=x^3+a_2x^2+a_1x+a_0$$, then $$p(q(x))=x^6+\frac{3}{2}x^5+\dots$$, so no matter what integers $$a_i$$ we choose, the resulting polynomial will have a non-integer coefficient. The monic condition is important, since otherwise we could multiply $$p(x)$$ with such integer that would guarantee all coefficients to be integers. I've tried to look at the coefficient in composition for general polynomials, which I believe should follow this formula:

\begin{align} [x^r]p(q(x))=\sum_{k_1+2k_2+\dots+mk_m=r}\sum_{k_0=0}^{n-(k_1+\dots+k_m)}\binom{k_0+k_1+\dots+k_m}{k_0,k_1,\dots,k_m}a_{k_0+k_1+\dots+k_m}\left(\prod_{j=0}^{m}b_j^{k_j}\right) \end{align} (here $$a_i$$ and $$b_i$$ are the coefficients of $$p(x)$$ and $$q(x)$$ with degrees $$n$$ and $$m$$, respectively). However it is not at all clear on which coefficient to focus to prove it will give the non-integer number.

This arose when trying to solve the Infinitely many solutions leads to existence of a polynomial, but it seems interesting enough by itself.

• @Sil If I had been faced with this conjecture, and had not had the benefit of Doctor Who's answer, I would have tried (very inelegant) induction on the degrees of p and q. First, I would have assumed that p and q are each of degree 1. Then I would have experimented, keeping degree p at 1, and letting q go to degree 2, then degree 3, then degree 4. I would then have reversed the process, keeping degree q at 1, and considering p of degrees 2, 3, and 4. I'm not sure that I would have gotten anywhere, but this (induction or double induction) approach would have been my first try. Aug 16, 2020 at 21:14
• @user2661923 Thanks for the suggestion, I have tried small degrees, but it is unclear how to construct the induction though. I guess looking at the most "extreme" factors in the denominators as shown in Doctor Who's answer is really the key.
– Sil
Aug 17, 2020 at 8:05
• @Sil You might be right. Whenever I am confronted with a problem like this, I try to first take "baby steps". That usually means first looking for a pattern, and then attempting induction rather than elegant manipulation. This is not a foolproof approach. Aug 17, 2020 at 8:12
• See mathoverflow.net/a/314264/297 for several related results. Feb 11, 2021 at 13:52

In fact, we may ignore the assumption that $$q$$ is monic. The composition $$p \circ q$$ cannot have all integer coefficients.

For let $$r$$ be a prime factor of some fully simplified denominator of a coefficient of $$q$$. Consider the largest $$k$$ s.t. $$r^k$$ is a factor of some denominator of a $$q$$ coefficient. Then write the polynomial $$q$$ as $$x^j w(x) / r^k + s(x)$$, where every fully simplified numerator of $$w(x)$$ is not divisible by $$r$$ and no fully simplified denominator of $$s(x)$$ is divisible by $$r^k$$, and where $$w$$ has a non-zero constant term. Do this by grouping all terms with denominators divisible by $$r^k$$, obtaining $$x^j w(x) / r^k$$, and all terms with denominators not divisible by $$r^k$$, obtaining $$s(x)$$.

Let $$n$$ be the degree of $$p$$, and consider the coefficient of $$x^{jn}$$ in $$p \circ q$$. One of the contributing summands will be $$w(0)^n / r^{kn}$$, which is fully simplified. And none of the other summands can have a denominator divisible by $$r^{kn}$$. So this coefficient is not an integer.

One can show this with some elementary properties of algebraic integers:

Fact. If $$p \in \mathbb C[x]$$ and $$q \in \mathbb Q[x]$$ are monic, $$p(0) \in \mathbb Z$$, $$\deg p, \deg q > 0$$ and $$p \circ q \in \mathbb Z[x]$$, then $$q \in \mathbb Z[x]$$.

Proof: We must show that all roots of $$q$$ are algebraic integers. Let $$\alpha$$ be a root of $$q$$. Then $$p(q(\alpha)) - p(0) = 0$$. The assumptions imply that $$r(x) = p(q(x)) - p(0)$$ is a monic integer polynomial. Because $$\alpha$$ is a root of $$r$$, it is an algebraic integer.

• Nice, at first I was a little suspicious of how simply it looks but I couldn't find and error in it, looks good! Only thing that got me stuck is that you use that if $q$ has all roots algebraic integers, then itself must be an integer coefficients polynomial, which I think requires a bit of work (I had to write $q(x)=f(x)g(x)$ with irreducible monic $f \in \mathbb{Z}[x]$ with $f(\alpha)=0$ and $g\in \mathbb{Q}[x]$ monic, and used the same logic repeatedly on $g(x)$ to realize $q(x)$ will end up as a product of polynomials from $\mathbb{Z}[x]$, maybe there is a simpler way though...)
– Sil
Jan 26, 2021 at 22:29
• I was suspicious myself initially. An easier argument is to factorize $q$ into linear factors. Then expand, to see that all coefficients are algebraic integers. They are rational, therefore integer. Jan 27, 2021 at 8:55
• In fact, $q \in \mathbb Q[X]$ and $p \circ q \in \mathbb Q[X]$ implies $p \in \mathbb Q[X]$. So I might as well impose $p \in \mathbb Q[X]$ in the statement. Jan 27, 2021 at 9:48
• Or you could make it as a step in proof. Anyway I don't think you can go straight into linear factors, those won't be necessarily rational (there might be irreducible factor of $q$ in $\mathbb{Q}[x]$ of higher degree), what am I missing?
– Sil
Jan 27, 2021 at 9:54
• Factorize over $\mathbb C$. The linear factors are of the form $(x - \alpha)$ with $\alpha$ an algebraic integer. Jan 27, 2021 at 9:55

For the non-monic case:

Consider the monic polynomial $$p(y) - p(q(x)) \in \mathbb Z[x][y]$$. It has a root $$q(x) \in \operatorname{Frac}(\mathbb Z[x])$$. By the rational root theorem applied to the UFD $$\mathbb Z[x]$$, it follows that $$q(x) \in \mathbb Z[x]$$.