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$.

setdoes 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. $\endgroup$ – sleepless in beantown Oct 17 '10 at 11:2921more comments