co.combinatorics - Asymptotic growth of a certain integer sequence

Here is an easier way to see this result:

• If f(x)=$sum a_kx^k$ is a polynomial divisible by $(x-1)^{n+1}$ then $sum a_kg(k)=0$ for any polynomial of degree n (or less).

It is enough to verify this for a basis of the set of polynomials of these degrees. Since x=1 is a root of the jth derivative $f^{(j)}$ the claimed equality holds for $g(k)=k(k-1)(k-2)cdots(k-j+1)$.

So $(x-1)(x^2-1)(x^4-1)=x^7-x^6-x^5+x^4-x^3+x^2+x-1$ and hence $sum_{[0,3,5,6[}k^j=sum_{[1,2,4,7]}k^j$ for $j=0,1,2$. Then a(3)=7 because nothing smaller works for the restricted problem $sum_A k^j=sum_Bk^j$ just for $j=2$ but with $A,B$ a partition of the positive integers to some point. Note that the partition is according to the parity of the sum of the bits in the the binary form of m. The similar construction shows that the integers from 1 to b^{n+1}-1 can be partitioned into b sets of size b^{n) with the sets agreeing on all sums of jth powers j=0..n.

$(x-1)(x^2-1)(x^3-1)$ yields $sum_{[0,4,5]}k^j=sum_{[1,2,6]}k^j$ for $j=0,1,2$, but there is that gap at 3. The paper The Prouhet-Tarry-Escott problem revisited Enseign. Math. (2) 40 (1994) by Peter Borwein and Colin Ingalls gives a wealth of information about this amazing (other) problem of equal sums of powers jth powers j=0,1,2,...,n . It is usually available on the website http://www.cecm.sfu.ca/ but at the moment I could not get there.

The value a(3)=12 comes from the partition {1,2,4,8,9,12},{3,5,6,7,10,11} and there is the polynomial (shifting down) $$1+x-x^2+x^3-x^4-x^5-x^6+x^7+x^8-x^9-x^{10}+x^{11}=$$ $$(x^3-1)(x^8-x^7-x^6+2x^5-2x^3+x^2-x-1)$$

The value a(4)=16 comes from the partition {5, 6, 7, 13, 14, 15}, {1, 2, 3, 4, 8, 9, 10, 11, 12, 16} and there is the polynomial (shifting down) $$x^{15}-x^{14}-x^{13}-x^{12}+x^{11}+x^{10}+x^9+x^8+x^7-x^6-x^5-x^4+x^3+x^2+x+1=$$
$$(x^7-x^6-x^5-x^4+x^3+x^2+x+1)(x^8+1)$$ which is intriguing. However I did not find anything that factored for a(9) (where the sets are listed at the OEIS) and didn't do the search for the sets giving the other a(n).

It may be that you can find constructions giving solutions with nice patterns that are not minimal but do establish an upper bound. However I can't at the moment. I'd try polynomials either shifting k to $x^{k-1}$ or else putting a 1 for $x^0$ into one set or the other.