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

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

2010-10-17T07:48:24Z

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

Answer by Gerry Myerson for A conjecture on a Subset Power Sum Problem motivated by Computer Science

2010-10-17T22:34:07Z

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.

Answer by Tsuyoshi Ito for A conjecture on a Subset Power Sum Problem motivated by Computer Science

2010-10-18T12:15:10Z

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₁,…,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 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) > 2^m−1. This establishes the claim for i=1.

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

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

2011-06-02T20:35:01Z

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.