Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
This helped a lot thank you. –  J.A Oct 17 '10 at 0:58
    
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. –  J.A Oct 17 '10 at 1:29
    
"q.v."? . –  JBL Oct 17 '10 at 1:30
    
quod vide, q.v. –  Gerry Myerson Oct 17 '10 at 7:03
1  
q.v. = quod vide, Latin for "Google it". –  Hugo van der Sanden Oct 17 '10 at 7:19
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.