A conjecture on a Subset Power Sum Problem motivated by Computer Science - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T22:00:09Z http://mathoverflow.net/feeds/question/42472 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42472/a-conjecture-on-a-subset-power-sum-problem-motivated-by-computer-science A conjecture on a Subset Power Sum Problem motivated by Computer Science unknown (google) 2010-10-17T07:48:24Z 2011-06-02T20:35:01Z <p>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</p> <p>$\displaystyle \sum_{j=1}^{n}c_{j}x_{j}^{i} \ne \displaystyle \sum_{j=1}^{n}x_{j}^{i}$</p> <p>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$?</p> <p>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}\}$.</p> <p>$\underline{Conjecture}$: $k_{i} = \infty$ $\forall i \ge 1$.</p> http://mathoverflow.net/questions/42472/a-conjecture-on-a-subset-power-sum-problem-motivated-by-computer-science/42551#42551 Answer by Gerry Myerson for A conjecture on a Subset Power Sum Problem motivated by Computer Science Gerry Myerson 2010-10-17T22:34:07Z 2010-10-18T04:41:49Z <p>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$. </p> <p>Tsuyoshi Ito posted an answer while I was typing mine, you'll see we're thinking along similar lines. </p> <p>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. </p> http://mathoverflow.net/questions/42472/a-conjecture-on-a-subset-power-sum-problem-motivated-by-computer-science/42620#42620 Answer by Tsuyoshi Ito for A conjecture on a Subset Power Sum Problem motivated by Computer Science Tsuyoshi Ito 2010-10-18T12:15:10Z 2010-10-18T12:15:10Z <p>Here is what I think proves that for any <i>i</i>, there is no constant <i>k</i><sub><i>i</i></sub> satisfying <i>f</i>(<i>n</i>,<i>i</i>)≤<i>n</i><sup><i>k</i><sub><i>i</i></sub></sup>. That is:</p> <p><strong>Claim</strong>. Let <i>i</i> be a positive integer. Then the function <i>f</i>(<i>n</i>,<i>i</i>) is not polynomially bounded in <i>n</i>.</p> <p><strong>Proof</strong>. First consider the case of <i>i</i>=1. A key observation is that if <i>X</i>={<i>x</i><sub>1</sub>,…,<i>x</i><sub><i>n</i></sub>} contains two subsets <i>A</i> and <i>B</i> such that |<i>A</i>|=|<i>B</i>|, <i>A</i>≠<i>B</i>, and the sum of <i>A</i> is equal to the sum of <i>B</i>, then <i>X</i> cannot be 1-sum-avoiding since assigning <i>c</i><sub><i>j</i></sub> as follows violates the condition: <i>c</i><sub><i>j</i></sub>=2 if <i>x</i><sub><i>j</i></sub> belongs to <i>A</i> but not to <i>B</i>, <i>c</i><sub><i>j</i></sub>=0 if <i>x</i><sub><i>j</i></sub> belongs to <i>B</i> but not to <i>A</i>, and <i>c</i><sub><i>j</i></sub>=1 if neither holds.</p> <p>Let <i>m</i> be a positive integer and <i>X</i> be a 1-sum-avoiding set of size 2<i>m</i>. By the above observation, all <i>m</i>-element subsets of <i>X</i> must have distinct sums, and therefore the largest sum must be at least $\binom{2m}{m}$. Therefore, the largest element in <i>X</i> must be at least $\binom{2m}{m}/m>2^{m-1}$, which implies that <i>f</i>(2<i>m</i>,1) &gt; 2<sup><i>m</i>−1</sup>. This establishes the claim for <i>i</i>=1.</p> <p>Now observe that if a set <i>X</i>={<i>x</i><sub>1</sub>,…,<i>x</i><sub><i>n</i></sub>} is <i>i</i>-sum-avoiding, then the set {<i>x</i><sub>1</sub><sup><i>i</i></sup>,…,<i>x</i><sub><i>n</i></sub><sup><i>i</i></sup>} is 1-sum-avoiding. This means that <i>f</i>(<i>n</i>,1) ≤ <i>f</i>(<i>n</i>,<i>i</i>)<sup><i>i</i></sup>. Since we already know that <i>f</i>(<i>n</i>,1) is not polynomially bounded, <i>f</i>(<i>n</i>,<i>i</i>) is not polynomially bounded in <i>n</i>, either. <strong>QED</strong>.</p> http://mathoverflow.net/questions/42472/a-conjecture-on-a-subset-power-sum-problem-motivated-by-computer-science/66767#66767 Answer by jcsp for A conjecture on a Subset Power Sum Problem motivated by Computer Science jcsp 2011-06-02T20:35:01Z 2011-06-02T20:35:01Z <p>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.</p>