1
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\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$
    – Turbo
    Commented Oct 17, 2010 at 1:29
  • $\begingroup$ "q.v."? . $\endgroup$
    – JBL
    Commented Oct 17, 2010 at 1:30
  • $\begingroup$ quod vide, q.v. $\endgroup$
    – Gerry Myerson
    Commented Oct 17, 2010 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$
    – Gerry Myerson
    Commented Oct 17, 2010 at 7:12
  • 1
    $\begingroup$ q.v. = quod vide, Latin for "Google it". $\endgroup$
    – Hugo van der Sanden
    Commented Oct 17, 2010 at 7:19
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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