Asymptotic growth of a certain integer sequence

Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence A019568 defined as follows:

$a(n):=$ the smallest positive integer $k$ such that the set $\{1^n, 2^n, 3^n,\dots k^n\}$ can be partitioned into two sets with equal sum.

In other words, $a(n)$ is the smallest $k$ such that there is a choice of signs + or - in the expression $$1^n\pm2^n\pm\dots\pm k^n \qquad\qquad(1)$$ that makes it vanish. In order to show that this $a(n)$ is a well-defined integer (that is: that at least one such $k$ does exist), a simple observation gives in fact a bound $$a(n)<2^{n+1}.$$ Reason: $(1-x)^{n+1}$ divides the polynomial $$Q(x):=(1-x)(1-x^2)(1-x^4)\dots(1-x^{2^n})=+1-x-x^2+x^3-\dots +(-1)^n x^{2^{n+1}-1},$$ therefore, if $S$ is the shift operator on sequences, the operator $Q(S)$ has the $(n+1)$-th discrete difference $(I-S)^{n+1}$ as factor, hence annihilates any sequence that is polynomial of degree not greater than $n$. In particular, the algebraic sum (1) with the signs of the coefficients of $Q(x)$ vanishes (incidentally, the sequence of signs is the so called Thue-Morse sequence A106400, $+--+-++--++-+--+\dots$.

However, looking at the reported values of $a(n)$ for $n$ from $0$ to $12:$

$$2,\ 3,\ 7,\ 12,\ 16,\ 24, \ 31,\ 39,\ 47,\ 44,\ 60,\ 71,\ 79,$$

it looks like the growth of $a(n)$ is much below $2^{n+1}$ (I have a weakness for sequences that grow slowly, here's possibly the main motivation of this question).

Question: Does anybody have a reference for the above sequence? Can you see how to prove an asymptotics, or a more realistic bound than $a(n)<2^{n+1}$?

Since there are about 2k possible sums, with typical order of magnitude about kn, it seems reasonable to guess that the first case when one of these sums is 0 will occur when these 2 numbers are about equal, which is when k is about n log(n)/log(2). This incredibly crude estimate is somewhat smaller than the numerical data, but maybe suggests about the right growth rate,

• Several notes on this post: we can be a little more precise and contain every sum in the interval $[-k^{n+1},k^{n+1}]$; there are really only $2^{k-1}$ sums, and any sums that coincide we can work with. Suppose we have some $a_i, b_i = \pm 1$ with $\sum_{i=1}^k a_ii^n = \sum_{i=1}^k b_ii^n$. Let $i_1 < i_2 < \cdots < i_m$ be the indices with $a_i \neq b_i$; then we have $\sum_{i = i_1,\cdots,i_m} a_ii^n = 0$. So we have two sets of integers $A, B \subset [1,n]$ with $\sum_{a \in A} a^n = \sum_{b \in B} b^n$. Presumably there are not terribly many of these, so we can derive a decent bound. – dvitek Aug 29 '10 at 21:40
• Alright, so some more thinking gives a way to formulate a pretty good upper bound in terms of a completely different problem, and even invoke Fermat's Last Theorem. Looks like it's time to actually put up a reasonable answer. – dvitek Aug 29 '10 at 21:51

This is building off of the work of Richard Borherds' answer and the comment I made there. We can provide a way to compute an upper bound which would be much better than the current exponential bound in $n$, but relies on enumerating solutions to certain Diophantine equations.

We are going to try and enumerate the distinct values of the expression $$e_11^n+e_22^n+\cdots+e_kk^n,$$ where $e_i = \pm 1$ for $i \in [1,n]$. Let $S$ be the set of all values attained by this expression. We have obviously $|S| \le 2^k$ as there are $2^k$ ways to choose the signs, but we know that two different choices for the $e_i$ may give the same numeric value. An illustrative example occurs in case $(k,n) = (5,2)$, where we have $$+1^2+2^2+3^2+4^2-5^2 = +1^2+2^2-3^2-4^2+5^2 = 5.$$ If we have two choices for the $e_i$ - for now, call the two lists of coefficients $a_i$ and $b_i$ that coincide, we may form sets $A = \{i \in [1,n]: a_i = +1, b_i = -1\}$ and $B = \{i \in [1,n]: a_i = -1, b_i = +1 \}$. Then we know that $A \cap B = \emptyset$, and more importantly, $\sum_{a\in A}a^n = \sum_{b \in B}b^n$.

Now define a function $s(k,n,a,b)$, with $a \ge b$ and $a+b \le k$, to count the number of pairs of sets $(A,B)$ satisfying the following conditions:

• $A \cup B \subseteq [1,k]$;
• $A \cap B = \emptyset$;
• $|A| = a$ and $|B| = b$;
• if $a = b$, then $\max{A} < \max{B}$;
• $\sum_{a\in A}a^n = \sum_{b \in B}b^n$.

Then we may write $$|S| \ge 2^k - \sum_{m=3}^k2^{k-m-1}\sum_{1 \le j \le m/2}s(k,n,m-j,j).$$ Indeed, we see that if some set of choices of $e_i$ give the same numerical value, all but one will be removed by this inclusion-exclusion counting. We may simplify this a bit further by writing $$f(k,n) = \sum_{m=3}^k2^{-m-1}\sum_{1 \le j \le m/2}s(k,n,m-j,j)$$ as our equation then becomes $|S| \ge 2^k(1-f(k,n))$. Now once we have established suitable bounds on $f(k,n)$, we may proceed as Richard did, noting that we simply solve for the least valid value of $k$ in the inequality $$2^k(1-f(k,n)) \ge 2\sum_{i=1}^ki^n.$$

Where does Fermat's Last Theorem come in? Well, in case $n \ge 3$, we need only sum from $m = 4$ to $k$ - there are no solutions for $m = 3$, as a solution for $m = 3$ takes the form $x^n + y^n = z^n$! So we lose what is (possibly?) the largest contributing term to $f(k)$.

EDIT: I was off by a factor of two. Darn.

• Can you, please, give an explicit bound? Due to the wealth of notation, I had a hard time inferring it from your answer. – Victor Protsak Aug 30 '10 at 4:42
• Sorry - I was writing this late at night running off of thoughts (as opposed to coffee or what-have-you). I edited the post a little bit to make this clearer, but to find $k$ we simply test values until we get one such that $2^k(1-f(k,n)) \ge 2\sum_{i=1}^k i^n$. Unfortunately, what I didn't realize is that the LHS will actually ALWAYS be less than the RHS (the LHS under-counts distinct values; the RHS over-counts them). So there isn't an explicit bound that this method can give - even doing more inclusion-exclusion on the LHS won't fix it. – dvitek Aug 30 '10 at 14:28

While I have no idea how to put an upper bound on it, I seem to have at least found a loose linear lower bound. I started by noticing that it takes a sufficiently large $k$ for $k^n$ to be smaller than the sum of the smaller numbers in the set. If the entire rest of the set can't sum to equal that one element, there clearly can't be an equal partition.

Since you've shown that there is always a solution, for a given $n$, there is some smallest integer $k^\star$ such that:

$\sum_{i=1}^{k^\star-1} i^n \ge k^{\star n}$

Since $k^\star$ is the smallest such integer,

$\sum_{i=1}^{k^\star-2} i^n < (k^\star-1)^n$

and therefore:

$2 (k^\star-1)^{n} > \sum_{i=1}^{k^\star-1} i^n \ge k^{\star n}$

For n>0, this gives:

$2^{1/n} > \frac{k^*}{k^\star-1}$

$2^{-1/n} < 1-\frac{1}{k^\star}$

$k^\star > \frac{1}{1-2^{-1/n}} = \sum_{i=0}^{\infty}2^{-i/n} > \frac{n}{2} + 1$

(My apologies if the latex doesn't parse correctly, the preview seems to show it only some of the time.)

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.

• thanks for correcting, of course it was $2^{n+1}$ like in the OEIS link, not $2^n$. Fixed now. – Pietro Majer Aug 29 '10 at 20:44