12
$\begingroup$

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$ ?

$\endgroup$
6
  • 2
    $\begingroup$ @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. $\endgroup$
    – minar
    Aug 9, 2013 at 19:18
  • 1
    $\begingroup$ This is a really neat question. Might I ask how you came across it? $\endgroup$
    – Alex Wertheim
    Aug 9, 2013 at 19:19
  • $\begingroup$ @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. $\endgroup$
    – minar
    Aug 9, 2013 at 19:26
  • $\begingroup$ @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 :) $\endgroup$
    – Alex Wertheim
    Aug 9, 2013 at 19:28
  • $\begingroup$ 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. $\endgroup$
    – user2566092
    Aug 9, 2013 at 22:13

2 Answers 2

Reset to default
4
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Michael Zieve
    Aug 10, 2013 at 21:56
  • $\begingroup$ 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. $\endgroup$
    – minar
    Aug 11, 2013 at 7:07
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for making this example explicit. Indeed looking at the roots is much easier than looking at the coefficients. $\endgroup$
    – minar
    Aug 11, 2013 at 7:06

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.