Let $\mathbb N_{n} = \{1,2,\cdots,n\}$.

Let $S$ be of cardinality $n$ where elements of $S$ are integers from $\mathbb N_{n}$ and at least one element of $S$ is repeated (That is at least one integer from $\mathbb N_{n}$ is skipped. One can easily find a set $S$ with the property that: $\displaystyle \sum_{j \in S}j^{i} = \displaystyle \sum_{j \in \mathbb N_{n}}j^{i}$ when $i = 1$. (Example: $n=4$, $S=\{1,1,4,4\}$ has sum $10$, the same as sum of first n consecutive integers)

How about for $i \ge 2$? It is not obvious that higher power sum sets exist due to constraint in the cardinality of $S$ and $\mathbb N_{n}$. One cannot deny it either? Is there a easy way to tackle some sumset questions?

For $i=2$ it is related to quadratic forms and integer norms. In an integer coordinate system, how many ways can a given integer norm occur when the coordinates are bounded?


It's a little easier to state an answer if you let $N_n=\lbrace0,1,\dots,n-1\rbrace$.

Let $n=2^k$, let $S$ be the multiset of integers with an odd number of ones in binary, each such integer appearing with multiplicity 2. Then it works for all $i\lt k$.

E.g., $k=3$, $S=\lbrace1,2,4,7\rbrace$, each taken twice, you get $1^i+2^i+4^i+7^i=0^i+3^i+5^i+6^i$ for $i=0,1,2$ (where, by convention, $0^0=1$).

If you really need the range to start at 1, just add 1 to everything, take $S=\lbrace2,3,5,8\rbrace$.

This has to do with the Tarry-Escott problem, q.v.

  • $\begingroup$ How about if $n \ne 2^{k}$? Is there always such an $S$? Actually I am looking for a negative answer:)? If I have a negative answer there is a way to solve some hard problems in computer science in a somewhat easier manner. $\endgroup$
    – Mr.
    Oct 17 '10 at 1:29
  • $\begingroup$ "q.v."? . $\endgroup$
    – JBL
    Oct 17 '10 at 1:30
  • $\begingroup$ quod vide, q.v. $\endgroup$ Oct 17 '10 at 7:03
  • $\begingroup$ If $n\ne2^k$, say $2^k\lt n\lt2^{k+1}$, then let $T$ be the set that works for $2^k$, and let $S=T\cup\lbrace2^k+1,\dots,n\rbrace$. There may be other solutions - again, check out Tarry-Escott. $\endgroup$ Oct 17 '10 at 7:12
  • 1
    $\begingroup$ q.v. = quod vide, Latin for "Google it". $\endgroup$ Oct 17 '10 at 7:19

As soon as you have a sum of distinct $i$th powers, say $a_1^i+\dots+a_s^i$, equal to another sum of (not necessarily distinct) $i$th powers $b_1^i+\dots+b_s^i$ ($s$ is, of course, the same), you have the desired property for $n\ge\max\lbrace a_1,\dots,a_s,b_1,\dots,b_s\rbrace$. So, your question is about a "minimal" solution of $$a_1^i+\dots+a_s^i=b_1^i+\dots+b_s^i$$ in integers with $a_1,\dots,a_s$. The equation does not look pretty enough, and solutions for small $i$ can be found "by hand".

Let me conclude that your problem is a version of Waring's_problem.


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.