# Fully factored integer polynomials with constant differences

Given a degree $d$, it is possible to construct a pair $(F,\delta),$ where $F$ is a polynomial in $\mathbb{Z}[X]$ and $\delta$ a non-zero integer, such that $F(X)$ and $F(X)+\delta$ both split into linear factors over $\mathbb{Z}[X]$ ?

This is easy for $d=2$, as shown by the pair $F(X)=X^2$ and $\delta=-a^2$ (for an arbitrary integer $a$). Indeed, $F(X)=X \cdot X$ and $F(X)+\delta=(X-a)\cdot (X+a).$ What can be said for $d>2$ ?

• @JaycobColeman I don't think so. E.g. $X^4-16$ factors as $(X-2)\cdot (X+2) \cdot (X^2+4)$ with $X^2+4$ irreducible. – minar Aug 9 '13 at 19:18
• This is a really neat question. Might I ask how you came across it? – Alex Wertheim Aug 9 '13 at 19:19
• @AWertheim Playing around with symmetric polynomials. In fact, I initially wondered whether you can find two distinct $t$-uples of integers with identical values of their symmetric polynomials except for $S_t$. I asked the question in the above form because this elementary formulation seemed nicer. – minar Aug 9 '13 at 19:26
• @minar, Beautiful, thanks for sharing. Tinkering with it now, but can't say it's an easy question! I'll post anything I can uncover :) – Alex Wertheim Aug 9 '13 at 19:28
• You definitely can't use a polynomial with too many repeated roots, because for example if you try $X^d$ as one of your polynomials, then $X^d - a$ will only have at most 2 roots (can be seen geometrically, noting that the $x$-axis will be crossed at most twice), and these real-valued roots must have multiplicity of 1 because the derivative won't vanish at any non-zero roots. – user2566092 Aug 9 '13 at 22:13

This question is closely related to the Prouhet-Tarry-Escott problem.

The so-called ideal solution to PTE asks for two distinct sets of integers $A$ and $B$ with $|A|=|B|=d$, such that for all $k$ with $1\leq k\leq (d-1)$, we have $$\sum_{a\in A} a^k = \sum_{b\in B} b^k$$ It's easy to see that these equalities imply that all the symmetric polynomials of degree up to $(d-1)$ applied to members of $A$ and $B$ have identical values. Therefore, the difference of $$P_A=\prod_{a\in A}(x-a)$$ and $$P_B=\prod_{b\in B}(x-b)$$ must be a (non-zero) constant, making the pair $(P_A, P_B-P_A)$ a solution to this question for degree $d$.

At least one ideal PTE solution is known for $d\leq 10$ and for $d=12$; examples can be found at this page. Although the page is somewhat aged, I believe no solution of higher degree has been discovered subsequently, nor has the $n=11$ case been resolved. Also, as far as I know, there is no reason to believe that there is some upper bound on $d$ after which no solutions can be found; although the search is certainly getting considerably more difficult with increasing $d$.

The main difference between PTE and this problem is that this one allows non-monic polynomials and also repeated roots of the polynomials. Thus this question admits solutions which wouldn't be solutions of PTE; e.g. the one listed in the problem statement.

• The stated question is equivalent to PTE for multisets of integers -- that is, non-monicity isn't important. If $(F,\delta)$ solves the stated question, and we write $U$ and $V$ for the (multi-)sets of roots of $F(X)$ and $F(X)+\delta$, then $U$ and $V$ are multisets of rational numbers such that both $C$ and $D$ have the same cardinality $d$ (namely $d=\rm{deg} F$), and also $\sum_{u\in U}u^k = \sum_{v\in V}v^k$ for all $k$ with $1\le k\le d-1$. Now let $m$ be a common denominator of all the numbers in $U$ and $V$. Then $A=mU$ and $B=mV$ are multisets of integers solving PTE. – Michael Zieve Aug 10 '13 at 21:56
• Great answer. Exactly what I was looking for. Even if the problem is open for large $d>12$, it is already very nice to see the small degree solutions. – minar Aug 11 '13 at 7:07

I couldn't resist seeing the degree-$12$ solution with my own eyes (from the website linked in Peter Košinár's answer). It's $$F(X)=X^{12} - 1812X^{11} + 1434735X^{10} - 651551410X^9 + 187228503603X^8 - 35425220352696X^7 + 4450555420480105X^6 - 365361907449541290X^5 + 18776316466170261396X^4 - 556138149602905800792X^3 + 8118307377660639252960X^2 - 42308199268401215635200X$$ where $$\delta=67440294559676054016000.$$
Here both $F(X)$ and $F(X)+\delta$ are monic and squarefree, and the roots of $F(X)$ are $$0, 11, 24, 65, 90, 129, 173, 212, 237, 278, 291, 302$$ while the roots of $F(X)+\delta$ are $$3, 5, 30, 57, 104, 116, 186, 198, 245, 272, 297, 299.$$

After writing this out, I can see why the PTE community focuses on the roots rather than the polynomials...

• Thanks for making this example explicit. Indeed looking at the roots is much easier than looking at the coefficients. – minar Aug 11 '13 at 7:06