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



A conjecture on a Subset Power Sum Problem motivated by Computer Science
Here is what I think proves that for any *i*, there is no constant *k**i* satisfying *f*(*n*,*i*)≤*n**k**i*. 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*={*x*1,…,*x**n*} contains two subsets *A* and *B* such that |*A*|=|*B*|, *A*≠*B*, and the sum of *A* is equal to the sum of *B*, then *X* cannot be 1-sum-avoiding since assigning *c**j* as follows violates the condition: *c**j*=2 if *x**j* belongs to *A* but not to *B*, *c**j*=0 if *x**j* belongs to *B* but not to *A*, and *c**j*=1 if neither holds.


Let *m* be a positive integer and *X* be a 1-sum-avoiding set of size 2*m*. 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*(2*m*,1) > 2*m*−1. This establishes the claim for *i*=1.


Now observe that if a set *X*={*x*1,…,*x**n*} is *i*-sum-avoiding, then the set {*x*1*i*,…,*x**n**i*} 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**.


