A conjecture on a Subset Power Sum Problem motivated by Computer Science

Let $X=\{x_{1}, \cdots , x_{n}\}$ be a set of $n$ positive integers and integer $i \ge 1$. Let’s say that the set $X$ is $i$-sum-avoiding if for any nonnegative integers $c_{1}, \cdots, c_{n}$ such that $\sum_{j=1}^{n}c_{j} = n$ and $(c_{1},\cdots, c_{n}) \ne (1,\cdots, 1)$, it holds that

$\displaystyle \sum_{j=1}^{n}c_{j}x_{j}^{i} \ne \displaystyle \sum_{j=1}^{n}x_{j}^{i}$

Let $f(n,i)$ be the minimum value for a given $i \ge 1$ such that there exists an $i$-sum-avoiding set $X$ consisting of $n$ positive integers at most $f(n,i)$. Does there exist a constant $k_{i}$ for every $i$ such that $\forall n \in \mathbb N$, it holds $f(n,i) \le n^{k_{i}}$? If it does, what is the minimum of such $k_{i}$ for every $i$?

Showing such a set would help solve hard problems in computer science given some space relaxations. It seems that the hardness of such problems is directly related to non-existence of such sets. I could only show such sets when $k=n$ that is $k$ is not a constant. My example for $X$ is $X = \{n^{1}, n^{2},\cdots, n^{n}\}$.

$\underline{Conjecture}$: $k_{i} = \infty$ $\forall i \ge 1$.

• I find the statement of the problem very confusing. So long as $S$ is not identical to $N_n$, there will be some $i\ge1$ such that the sums in (1) are unequal. But maybe that is not what you are asking. Oct 17 '10 at 10:25
• Two problems: first, a set does not have duplicate elements, by definition it cannot have duplicate elements. An "ordered list" or a "multiset" can have duplicate elements. Second, you are almost defining something basic. $3^2+4^2=5^2$ is an example for $i=2$, so the multisets {1,2,3,4,5} and {1,2,5,5} work for $i=2$, but obviously not for $i \ne 2$. What's your motivation for this problem? Is this part of a homework problem-set? Please see the FAQ in that instance. Oct 17 '10 at 11:29
• If I find such a set, I can solve some of the hardest problems in computer science given some space relaxations. It seems that the hardness is directly related to non-existence of such sets.
– Mr.
Oct 17 '10 at 19:10
• then please spell out one example of these hard problems that you can solve, and how ? Oct 17 '10 at 21:57
• @sleepless in beantown: I agree that the first point is problematic. As for the second point, your example shows that the set {1,2,3,4,5} does not satisfy the condition for i=2. Oct 17 '10 at 22:27

Here is what I think proves that for any i, there is no constant ki satisfying f(n,i)≤nki. That is:

Claim. Let i be a positive integer. Then the function f(n,i) is not polynomially bounded in n.

Proof. First consider the case of i=1. A key observation is that if X={x1,…,xn} contains two subsets A and B such that |A|=|B|, AB, and the sum of A is equal to the sum of B, then X cannot be 1-sum-avoiding since assigning cj as follows violates the condition: cj=2 if xj belongs to A but not to B, cj=0 if xj belongs to B but not to A, and cj=1 if neither holds.

Let m be a positive integer and X be a 1-sum-avoiding set of size 2m. By the above observation, all m-element subsets of X must have distinct sums, and therefore the largest sum must be at least $\binom{2m}{m}$. Therefore, the largest element in X must be at least $\binom{2m}{m}/m>2^{m-1}$, which implies that f(2m,1) > 2m−1. This establishes the claim for i=1.

Now observe that if a set X={x1,…,xn} is i-sum-avoiding, then the set {x1i,…,xni} is 1-sum-avoiding. This means that f(n,1) ≤ f(n,i)i. Since we already know that f(n,1) is not polynomially bounded, f(n,i) is not polynomially bounded in n, either. QED.

I still find the statement of the problem very confusing. For $i=1$, you want your set $X$ to be a non-averaging set, that is, a set containing no three distinct elements $a,b,c$ such that $a+b=2c$. You want more than that, but that's a start, and there's enough literature on non-averaging sets to give you some kind of lower bound on $k$.

Tsuyoshi Ito posted an answer while I was typing mine, you'll see we're thinking along similar lines.

EDIT: There are several sections of Guy's Unsolved Problems In Number Theory that discuss problems not exactly what you want but not a million miles removed, either, and some of the references given there may be useful. Problem C8 is sets with distinct sums of subsets, C11 is three-subsets with distinct sums, C14 is maximal sum-free sets, C16 is nonaveraging sets.

• … except that I did not realize the connection of the question to non-averaging sets until I read your answer! The connection is interesting. Because of the way the value $k_i$ is defined, considering the non-averaging condition alone indeed gives some lower bound on the value of $k_1$. However, unfortunately the best lower bound on f(n,1) we can hope for from this method is $n^{1+o(1)}$ because there is a “large” non-averaging set (Behrend PNAS 1946 pnas.org/content/32/12/331.full.pdf+html), whereas we do not know if f(n,1) is polynomially bounded or not. Oct 18 '10 at 3:12

Take $x_j=2^{i-1}$. I claim that if $\sum_{j=1}^n c_j 2^{j-1} = \sum_{j=1}^n 2^{j-1}$ with $\sum_{j=1}^n c_j\leq n$, then $c_j=1$ for all $j$. The case $n=1$ is easy. In general note that $c_1$ is odd. We substract 1 on both sides of the equation and divide by 2, replace $c_2$ by $c_2+\frac{c_1-1}{2}$, and finally shift all indices by 1. Then we obtain an equation of the same form as before for a smaller value of $n$, and are done by induction. The same argument shows that $\{1, 2, 4, 8, \ldots\}$ is $i$-sum avoiding for every $i$, however, for larger $i$ there should be more efficient choices.