5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @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. $\endgroup$ Aug 16, 2020 at 21:14
  • $\begingroup$ @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. $\endgroup$
    – Sil
    Aug 17, 2020 at 8:05
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 17, 2020 at 8:12
  • 1
    $\begingroup$ See mathoverflow.net/a/314264/297 for several related results. $\endgroup$ Feb 11, 2021 at 13:52

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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...) $\endgroup$
    – Sil
    Jan 26, 2021 at 22:29
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 27, 2021 at 8:55
  • $\begingroup$ 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. $\endgroup$ Jan 27, 2021 at 9:48
  • $\begingroup$ 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? $\endgroup$
    – Sil
    Jan 27, 2021 at 9:54
  • 1
    $\begingroup$ Factorize over $\mathbb C$. The linear factors are of the form $(x - \alpha)$ with $\alpha$ an algebraic integer. $\endgroup$ Jan 27, 2021 at 9:55
1
$\begingroup$

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

$\endgroup$
0

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.