3
$\begingroup$

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

$\endgroup$
19
  • $\begingroup$ 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. $\endgroup$ Oct 17, 2010 at 10:25
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 17, 2010 at 11:29
  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Oct 17, 2010 at 19:10
  • $\begingroup$ then please spell out one example of these hard problems that you can solve, and how ? $\endgroup$ Oct 17, 2010 at 21:57
  • $\begingroup$ @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. $\endgroup$ Oct 17, 2010 at 22:27

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ … 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. $\endgroup$ Oct 18, 2010 at 3:12
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.