20
$\begingroup$

We have

$$ X(X+3) + 2 = (X+1)(X+2)$$

and

$$ X(X+4)(X+5) + 12 = (X+1)(X+2)(X+6)$$

and

$$ X(X+4)(X+7)(X+11) + 180 = (X+1)(X+2)(X+9)(X+10).$$

Do similar polynomial identities exist for each degree?

That is, for which positive integers $n$ do there exist integers $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$ such that

$$\prod_{i=1}^n (X + a_i) + c = \prod_{i=1}^n (X+b_i)$$

for some nonzero integer $c$?

Specific examples for the cases $n \ge 5$ are also helpful.

An answer to this question might shed light on this unsolved question. This other question asks for all such identities where $n=3$.

$\endgroup$
8
  • $\begingroup$ Hi Benjamin Wright, would you be helped by a proof for non integers $a_k$, $b_k$ and $c$? $\endgroup$
    – NancyBoy
    Dec 27, 2023 at 23:00
  • 1
    $\begingroup$ @NancyBoy The question is rather trivial if you allow $a_k,b_k\in\Bbb{C}$. $\endgroup$
    – Servaes
    Dec 27, 2023 at 23:01
  • $\begingroup$ That what I was thinking Servaes $\endgroup$
    – NancyBoy
    Dec 27, 2023 at 23:03
  • $\begingroup$ @NancyBoy No, I'm aware that it follows from the fundamental theorem of algebra if you allow complex $a_k$ and $b_k$ $\endgroup$ Dec 28, 2023 at 19:43
  • $\begingroup$ It feels a bit similar to Vinogradov's mean-value theorem, here with $s=n$ and $k=n-1$ resp. $k=n$ but obviously the main conjecture doesn't help you here. You'd want to show that with $k=n$ there are quantifiably less solutions to the system. en.m.wikipedia.org/wiki/Vinogradov%27s_mean-value_theorem $\endgroup$ Jan 2 at 17:43

4 Answers 4

9
+100
$\begingroup$

TL;DR: there are solutions for $n \leq 10$ and for $n=12$. Otherwise it's a well known open problem. See Wikipedia and here: http://euler.free.fr/eslp/TarryPrb.htm (archive).

The question is equivalent to the following:

Given $n$, do there exist integers $a_1, \ldots, a_n, b_1, \ldots, b_n$ such that $$\forall j < n: a_1^j + \cdots + a_n^j = b_1^j + \cdots + b_n^j$$ but $$a_1^n + \cdots + a_n^n \neq b_1^n + \cdots + b_n^n \, ?$$

(For each $j < n$ the polynomial $X_1^j + \cdots + X_n^j$ is a polynomial in the elementary symmetric polynomials of degree $\leq j$ where the one of degree $j$ occurs isolated and with only a linear term. This follows from the fundamental theorem.)

In this form the question apppears in the literature surrounding Vinogradov's Mean Value Theorem, for example here starting on the bottom of page 3 ("Tarry’s problem"):

Wooley, T., Vinogradov’s mean value theorem via efficient congruencing, https://annals.math.princeton.edu/2012/175-3/p12.

In the notations there, the question is whether $W(n-1, 2) = n$. (It is clear that $W(n-1, 2)$ cannot possibly be smaller because polynomials can only have so many roots.) Below Theorem 1.13 it says the answer is positive for $n \leq 10$ and for $n=12$ (there is a typo that makes you think it is for $n \leq 11$ and for $n=13$) and it refers to this page which lists solutions to a slightly more general problem: http://euler.free.fr/eslp/eslp.htm (archive).

For example for $n = 7$ look at the examples under the header "k=1,2,3,4,5,6".

I don't know when that page was last updated. You can search for recent literature on Tarry's problem or the "Tarry-Escott problem of degree $n-1$". As far as I have found, the degree 10 ($n=11$) case is still open.

$\endgroup$
1
  • 2
    $\begingroup$ +1 Great answer. As for your last paragraph; the website itself claims to have been last updated on May 6th, 2001. This article: https://doi.org/10.48550/arXiv.2304.11254 is quite recent, and gives a nice overview of the history of the problem and the progress that has been made so far. It does not mention any solutions for $n=11$ or $n>12$. $\endgroup$
    – Servaes
    Jan 3 at 21:41
7
$\begingroup$

Assuming the respective $a_i$ and $b_i$ values are distinct, the values for $c$ you provide for degrees 2, 3, and 4 are minimal. The minimal values of $c$ for degrees $5$ and $6$ are given by the following equalities.

$$x(x + 4)(x + 8)(x + 16)(x + 17) + 5040 = (x + 1)(x + 2)(x + 10)(x + 14)(x + 18),$$

$$x(x + 5)(x + 6)(x + 16)(x + 17)(x + 22) + 100800 = (x + 1)(x + 2)(x + 10)(x + 12)(x + 20)(x + 21).$$

I have been unable to find a degree $7$ solution. This is not for lack of searching. Unless there is a bug in my program, $c$ must be larger than $60,000,000$ in the minimal degree $7$ solution (if it exists).

I have also attempted to search selective larger values of $c$ (multiples of $100800$, highly composite numbers, b-smooth numbers for small b, etc.) for a solution with degree $7$, to no avail.

If we allow for duplicate $b_i$ values, it is possible to find smaller acceptable $c$ values but only for even degrees.

$$x(x + 2) + 1 = (x + 1)^2,$$

$$x(x + 3)(x + 4)(x + 7) + 36 = (x + 1)^2(x + 6)^2,$$

$$x(x + 3)(x + 5)(x + 11)(x + 13)(x + 16) + 14400 = (x + 1)^2(x + 8)^2(x + 15)^2.$$

I do not know what could be obstructing a solution for degrees $\geq 7$.

$\endgroup$
1
  • 4
    $\begingroup$ Possibly worth noting: the sequence $\sigma_n=\{2, 12, 180, 5040, 100800\}$ doesn't appear in OEIS anywhere. The sequence $\{1, 2, 4, 8, 36\}=(2n)!/\sigma_n$ does occur, but none of the occurences have a plausible match to this; it also seems like $12!/\sigma_6$ (if it exists) will have to be much smaller than 36 based on the bounds of your testing. $\endgroup$ Jan 2 at 21:07
2
$\begingroup$

Let $a_1,\ldots,a_n,b_1,\ldots,b_5,c\in\Bbb{Z}$ with $c\neq0$ be such that $$\prod_{i=1}^n(X-a_i)-\prod_{i=1}^n(X-b_i)=c.\tag{1}$$ Without loss of generality we may order the coefficients such that $a_i\leq a_j$ and $b_i\leq b_j$ whenever $i\leq j$, and interchange the $a_i$ and $b_i$ such that $a_1\leq b_1$. Moreover, for all $t\in\Bbb{Z}$ we have $$\prod_{i=1}^n(X+t-a_i)-\prod_{i=1}^n(X+t-b_i)=c,$$ in particular for $t:=a_1$, and so without loss of generality the $a_i$ and $b_i$ are all nonnegative.


Some observations: Plugging in $0$ or $a_k$ or $b_k$, for all $k$ we have $$c=\prod_{i=1}^n(b_k-a_i)=-\prod_{i=1}^n(a_k-b_i)=(-1)^n\left(\prod_{i=1}^na_i-\prod_{i=1}^nb_i\right).$$ In particular, we see that $a_i\neq b_j$ for all $i$ and $j$ because $c$ is nonzero. As a consequence, for $k=1$ we see that all factors in the second product are negative, and so $c$ is positive if and only if $n$ is odd. Moreover, we see that if $n$ is odd (even), then the number of negative factors in the second product is odd (even), regardless of $k$, and the number of negative factors in the first product is even (odd), regardless of $k$.

Proposition 1: For all $k$, the number of $i$ with $a_k<b_i<a_{k+1}$ is even, and the number of $i$ with $b_k<a_i<b_{k+1}$ is even.

Proof. We prove the claim for $a_k<b_i<a_{k+1}$; the other half of the claim is entirely analogous. If $a_k=a_{k+1}$ then the claim is trivial, so suppose $a_k<a_{k+1}$. Because $c$ is nonzero, the number of negative factors in the products $$\prod_{i=1}^n(a_k-b_i)=-c=\prod_{i=1}^n(a_{k+1}-b_i),$$ is congruent mod $2$. This proves the claim.

Proposition 2: For all $i$ we have $a_i<b_i$ if $i$ is odd, and $a_i>b_i$ if $i$ is even.

Proof. The integral polynomial $f=\prod_{i=1}^n(X-a_i)$ has precisely $n$ roots, counted with multiplicity, and hence it has precisely one extremum between each pair of distinct consecutive roots. This means that whenever $a_i\neq a_{i+1}$, the interval $[a_i,a_{i+1}]$ contains at most two solutions to $f(x)=c$. Of course we have $$f(b_k)=\prod_{i=1}^n(b_k-a_i)=c+\prod_{i=1}^n(b_k-b_i)=c,$$ and so we see that each interval $[a_i,a_{i+1}]$ contains at most two of the coefficients $b_k$. By symmetry each interval $[b_i,b_{i+1}]$ contains at most two of the coefficients $a_k$. By proposition $1$ every such interval contains an even number of these coefficients, from which it follows that the $a_i$ and $b_i$ alternate in pairs.

Next, to see that $a_1\neq a_2$, note that by the Gauss-Lucas theorem, all zeros of the derivative of $$g=\prod_{i=1}^n(X-b_i),$$ are contained in the interval $[b_1,b_n]$. This means there is at most one solution to $g(x)=-c$ with $x<b_1$, which must then be $a_1$. If $a_2=a_1$ then $g(x)+c$ has a double zero at $a_1$, meaning that $g'(a_1)=0$, contradicting the Gauss-Lucas theorem.

This means that the $a_i$ and $b_i$ must be ordered as $$a_1<b_1\leq b_2<a_2\leq a_3<b_3\leq b_4<a_4\leq\ldots,$$ which proves the proposition.


I will not continue this line of investigation, as I have just seen the answer by Bart Michels pointing out that this problem is equivalent to the Prouhet-Tarry-Escott Problem, which has been open for a long time.

$\endgroup$
1
$\begingroup$

Disclaimer: I've been awake for over 50 hours, this is my attempt at catching sleep.

Here's a rather convoluted argument that such coefficients exist for every positive integer $n$: Given $n$, for each positive integer $k$ let $e_k$ denote the $k$-th elementary symmetric polynomial, so that $$e_1=\sum_nX_i,\qquad e_2=\sum_nX_iX_j\qquad\ldots\qquad e_n=\prod_n X_i.$$


Theorem: (Fundamental theorem of symmetric polynomials) For a commutative unital ring $A$, for every symmetric polynomial $P\in A[X_1,\ldots,X_n]$ there exists a unique polynomial $Q\in A[Y_1,\ldots,Y_n]$ such that $$P(X_1,\ldots,X_n)=Q(e_1(X_1,\ldots,X_n),\ldots,e_n(X_1,\ldots,X_n)).$$ Equivalently, for a commutative unital ring $A$, let $X:=(X_1,\ldots,X_n)$ be indeterminates and let $e(X):=(e_1(X),\ldots,e_n(X))$. Then the set of symmetric polynomials in $A[X]$ is precisely the subring $A[e(X)]\subset A[X]$, or more explicitly the subring $$A[e_1(X_1,\ldots,X_n),\ldots,e_n(X_1,\ldots,X_n)]\subset A[X_1,\ldots,X_n],$$ and moreover the $e_k(X)$ are algebraically independent over $A$.


Now you want to find $a,b\in\Bbb{Z}^n$ such that $e_k(a)=e_k(b)$ for all $k<n$, but $e_n(a)\neq e_n(b)$. Suppose such $a$ and $b$ do not exist. Then with $A:=(A_1,\ldots,A_n)$ and $B:=(B_1,\ldots,B_n)$ indeterminates, and $e(X):=(e_1(X),\ldots,e_n(X))$, the polynomial $$e_n(A)-e_n(B)\in\Bbb{Z}[e(A),e(B)],$$ vanishes on the zero locus of the ideal $$I:=\Big\langle e_k(A)-e_k(B):\ k<n\Big\rangle\subset\Bbb{Z}[e(A),e(B)],$$ and so by the Nullstellensatz $(e_n(A)-e_n(B))^r\in I$ for some positive integer $r$. Of course $I$ is radical because it is the kernel of the ring homomorphism $$\Bbb{Z}[e(A),e(B)]\ \longrightarrow\ \Bbb{Z}[e(A)]:\ e(B)\ \longmapsto\ e(A),$$ and so $r=1$. That is to say there are $c_k(A,B)\in\Bbb{Z}[e(A),e(B)]$ such that $$e_n(A)-e_n(B)=\sum_{k=1}^{n-1}c_k(A,B)(e_k(A)-e_k(B)).$$ But then evaluating at $B=0$ yields a contradiction with the fact that the $e_k(A)$ are algebraically independent. Hence such $a$ and $b$ must exist.

$\endgroup$
3
  • 1
    $\begingroup$ This is a little outside my comfort zone, but I think that the Nullstellensatz does not apply, since we're considering the zero locus of an ideal defined over the integers rather than an algebraically closed field. $\endgroup$ Dec 28, 2023 at 19:56
  • $\begingroup$ The example that I'm thinking of is that $A_1 + B_1$ vanishes over the zero locus of $I = \langle A_1^2 + B_1^2 \rangle \subset \mathbb{Z}[A_1, B_1]$, but there is no positive $r$ such that $(A_1+B_1)^r \in I$. $\endgroup$ Dec 28, 2023 at 20:02
  • $\begingroup$ @BenjaminWright I agree entirely, and will think about a fix. The current form of the argument is unnecessarily roundabout anyway. $\endgroup$
    – Servaes
    Dec 28, 2023 at 23:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .