## Subset higher power sum question (related to quadratic forms)

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

## 2 Answers

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.

-
This helped a lot thank you. – unknown (google) Oct 17 2010 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. – unknown (google) Oct 17 2010 at 1:29
"q.v."? . – JBL Oct 17 2010 at 1:30
quod vide, q.v. – Gerry Myerson Oct 17 2010 at 7:03

1
q.v. = quod vide, Latin for "Google it". – Hugo van der Sanden Oct 17 2010 at 7:19
show 1 more comment

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9218083024024963, "perplexity_flag": "head"}