Question

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?

Answer 1

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.

Answer 2

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.