Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
You probably meant $\mathbb M_m=\mathbb N_n$ –  zhoraster Oct 17 '10 at 8:07
    
$\mathbb M_m=\mathbb N_m$, sorry –  zhoraster Oct 17 '10 at 8:07
    
... fixed. –  Pietro Majer Oct 17 '10 at 8:20
    
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. –  Gerry Myerson Oct 17 '10 at 10:25
1  
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. –  sleepless in beantown Oct 17 '10 at 11:29

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
… 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. –  Tsuyoshi Ito Oct 18 '10 at 3:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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