Can You Find the Best Constant for Sum-Free Subsets?

[Office_Shredder]

A set A of non-zero integers is called sum-free if for all choices of $a,b\in A$, a+b is not contained in A.

The Challenge: Find a constant c > 0 such that for every finite set of integers B not containing 0, there is a subset A of B such that A is sum-free and |A| ≥ c|B|, where |A| means the number of elements of A.Every solution (by a new poster) which improves on the best constant known up until that point in the thread will be awarded a fresh 2 points, and of course alternate solutions which do not improve on the best known constant are more than welcome as well! Solutions which show a c exists but do not calculate it are also OK.

 

[AlephZero]

I don't understand why you specified "non-zero integers", since a sum-free set of integers clearly can not contain 0.

What do you mean by |A|, when A is a set? The number of elements in A? Some sort of norm?

 

[Office_Shredder]

Yes, it means the number of elements of A (I edited the OP to add that in for future viewers). I guess I didn't need to specify that a sum-free set doesn't contain zero, but it is mildly important that B not contain zero otherwise the set {0} screws up the statement of the problem.

 

[jbunniii]

Here's a first stab at simplifying the problem somewhat.

Suppose we can find a $c_p$ which works when $B$ is restricted to contain only positive integers. Then of course the same $c_p$ will work if $B$ contains only negative integers.

We can then solve the general case by removing either all of the negative integers or all of the positive integers from $B$, whichever causes fewer elements to be removed. By doing so, we will have reduced $|B|$ by at most a factor of $1/2$. Our solution for the positive case then gives us a subset $A$ containing at least $(c_p/2)|B|$ elements.

So, to prove the existence of the required constant $c$, we may without loss of generality assume that $B$ contains only positive integers. (In order to obtain the best possible $c$, we may have to consider the general case.)

 

[AlephZero]

I'm not sure if this leads anywhere in the general case, but if all the elements of B are odd, then A = B and c = 1.

How about dividing A into disjoint sets $\{O_i2^k\}, k = 0, 1, \dots$ where the $O_i$ are all odd numbers ...

 

[Filip Larsen]

Not sure if upper limits for c are considered useful in this context, but if they are there is an obvious one:

If |B| = 3 and B is not sum-free, then |A| = 2 and, if c exists, we must have that c ≤ 2/3.

(Working on a lower limit, but that is much harder :tongue:)

 

[mfb]

An upper limit can be found by an example:
B={1,2}, the largest sum-free subsets are A={1} and A={2}, so c≤1/2.

If all elements of B are a common multiple of some integer n, we can construct B' by dividing all integers by n, and get the same problem again. Therefore, WLOG, we can assume that the largest common divisor of B is 1.
I guess we can find an element for every prime number here, but that won't give a lower limit >0, as the prime number density goes to zero.

There is an interesting "weighting" issue: If our smallest sum-free subset (SFS) A has an element a, we can also add an element -a without loosing the SFS-property. This can be shown by modifying "a+b=c" to "b=c+(-a)". If B has both a and -a, adding this element is a bit like a number with a weight of 2. To get a large minimal c, it is favorable to add this number, even if you have to kick out another number.I wonder if c=1/2 is the real value. Looking at small |B|, I didn't find any example where c has to be lower.

 

[Filip Larsen]

An upper limit can be found by an example:
B={1,2}, the largest sum-free subsets are A={1} and A={2}, so c≤1/2.

Oh, I completely missed that a and b can be the same number. Oh well ...

 

[JanEnClaesen]

I'm not sure if this leads anywhere in the general case, but if all the elements of B are odd, then A = B and c = 1.

How about dividing A into disjoint sets $\{O_i2^k\}, k = 0, 1, \dots$ where the $O_i$ are all odd numbers ...

Generalized oddness would be modular arithmetic. A necessary but not sufficient condition for a + b = c is that the residue of a + b divided by m is the same as the residue of c divided by m, a prime number.

Let B be a set of random integers, consider the subset of B, A = {a, b}, which is clearly sum-free, the chance that an element c of B \ A has the same residue as a + b when divided by m is 1/m. Let p be the probability that a + b and c have the residue when divided by m.

 

[jbunniii]

Let B be a set of random integers, consider the subset of B, A = {a, b}, which is clearly sum-free

What if a + a = b?

 

[JanEnClaesen]

What if a + a = b?

True but ultimately irrelevant, start with a subset A = {a} which is clearly sum-free because a is a non-zero integer. a + b is still defined if a, b are elements of A. Change "random integers" to "random natural numbers".
a + a = b does imply that the set {0, ..., m - 1} is the largest guaranteed sum-free subset. Since m can be every prime number smaller than the smallest prime number greater than the greatest element of B. The average of all possible m's divided by the size of B gives an approximation (A) of c.

Approximate (B) the sum of all m's by including all non-prime numbers not greater than the greatest element of B, thus the approximation (A) of c is at most |B|/2 * 1/|B| = 1/2.

 

[mfb]

{0, ..., m - 1} is not sum-free.
If you have 0, the set is not sum-free at all. And what about examples like 1+2=3?
{m, ..., 2m - 1} is sum-free, but that is trivial.

I don't understand your argument.

 

[JanEnClaesen]

{0, ..., m - 1} is not sum-free.
If you have 0, the set is not sum-free at all. And what about examples like 1+2=3?
{m, ..., 2m - 1} is sum-free, but that is trivial.

I don't understand your argument.

You're right to because it's a completely wrong argument, I must have been confused. If a sum a + b has a different residue when divided by m than c then a + b =/= c. The probability that a number has residue r when divided by m is 1/m.

I must have had the 'different residues' in my mind and wrote that down without thinking. Very stupid.

What it should have been: all the numbers that have the same residue not equal to 0 when divided by m form a sum-free set.

 

[mfb]

Unfortunately, we cannot guarantee to get a fraction c>0 of those numbers. Most numbers could be divisible by m.

Hmm, that might lead to an existence proof:

Suppose we can find a series B_i with maximal SFS (sum-free subsets) A_i where |A_i| / |B_i goes to zero. In general, we have some choice for A_i, we choose one and fix it for the remaining analysis.

Using the argument given by jbunniii in post 4, it is sufficient to consider sets with only positive numbers - if there is such a series, there is also a series where all sets have no negative numbers.

Every subsequence of this will also have the same property and |B_i| has to go to infinity, so WLOG we can assume |B_i+1| > |B_i|.


For an arbitrary prime p where a fraction m_p of all elements in |B| is divisible by p, we can find a SFS of at least |B|*(1-m_p)/(p-1) elements with the same remainder.

Therefore, a lower limit on the fraction of elements in a maximal SFS is
$$\max_{\text{p prime}} \frac{1-m_p}{p-1}$$

How can we show that not all m_p can go to 1 at the same time?

 

[JanEnClaesen]

|B| = s*t where s is the smallest prime divisor of |B| and t = |B| / s.
There exists a subset A, containg all elements with an equal residue r when divided by s, and where |A| >= t, by the pigeonhole principle.

=> c = 1 / s

 

[Office_Shredder]

|B| = s*t where s is the smallest prime divisor of |B| and t = |B| / s.
There exists a subset A, containg all elements with an equal residue r when divided by s, and where |A| >= t, by the pigeonhole principle.

=> c = 1 / s

s could be arbitrarily large so you don't get a universal constant, and if the elements all have residue 0 then it's not necessarily a sum-free subset.

I think that collectively you guys are bringing something together, I'm going to rethink the scoring to reward teamwork I think.

 

[Boorglar]

Not sure if this can help, nor whether anyone else thought of this already, but for any set $B$, you can associate another set $B_n$ containing all residues mod n of the elements of $B$. (so for n = 2, this means all even numbers map to 0 and all odd numbers map to 1). So the problem can be reduced to sets of the form $\{0,1,...,n-1\}$.

Let $A_{n}$ be the largest residue class mod n contained in $B_{n}$. In "most" cases, this class will not be 0, and the set of all elements in B congruent to $A_{n}$ will be sum free. So we would have a set of size at least |B|/n and c = 1/n. (For n = 2, this would be equivalent to saying that if there are more odd numbers than even numbers, then the set of all odd numbers is sum-free and is larger than |B|/2 ).

Unfortunately, it may be possible for most, or all, numbers in B to be multiples of n for n = 2,3,4... and so on until we can't talk about constants anymore...

 

[mfb]

That's the issue, indeed. "most" cases are easy, the tricky part are the cases where the residue of 0 is the largest group for all small primes. This requires a large spread in the numbers and I have some feeling that we have to consider the largest number in the set to show that this would grow too fast (so even if the residues match, we get large sum-free subsets just because the numbers vary too much in their magnitude). But I did not manage to find a proof based on this.

 

[JanEnClaesen]

Since the originator of the problem seems to look for an approximation, a probabilistic attack seems in place, I haven't considered how exactly, but it certainly involves residues.

 

[mfb]

You are looking for a maybe tiny fraction of all sets which could have values different from all other sets a probabilistic approach catches.

 

[JanEnClaesen]

I'm not sure I understand your argument, basically you're saying any probabilistic would be too crude a priori?

That being said, 1/e because it's always e, by induction.

 

[mfb]

A random set will have very large sum-free subsets, if you are not extremely careful with the selection of those random sets.

 

[Office_Shredder]

A small hint: Having all the numbers mod p be exactly equal is stronger than what you really need to prove that a set is sum free.

 

[mfb]

It is sufficient (but not necessary) to have the remainders sum-free, but I don't see how that helps.
There are sets where you cannot find a maximal sum-free subset of remainders.

 

[JanEnClaesen]

In the unbounded set {1, 2, ... , N} every one in two numbers is even, but only every one in three even numbers have remainder zero when divided by three, and more certainly form a sum-full set...

What about 1 - 1/c' = 1/2 + 1/2*3 + 1/2*3*5 + 1/2*3*5*7 + ... < e - 2 ?

 

[Office_Shredder]

Jan, what if my set happens to have only one odd number, and of those even numbers only one is not divisble by 3, etc.?

mfb I did say it was a small hint :p. Certainly if you believe the problem statement to be true then there is some prime number for which a large number of remainders are sum-free.

 

[Office_Shredder]

A clever person might infer from my hint what kind of prime numbers might be suitable to mod out by as well.

 

[mfb]

2 and maybe 3 are reasonable choices, as they are close to e and e likes to appear in those problems, but I still don't see how this gives any estimate.

 

[Citan Uzuki]

I don't want to give away the answer, since I found it by googling this exact problem, so I'd just be copying someone else, but I will give you a couple of hints. First, the prime you should choose is one large enough that all of the numbers have distinct residues modulo that prime. Second, the constant you're looking for is 1/3.

 

[Joffan]

I wonder if c=1/2 is the real value. Looking at small |B|, I didn't find any example where c has to be lower.

I didn't see any subsequent challenge to this bound so I thought I would exhibit B={1,2,3,4,5,6,8} , |B|=7, whose maximal sum-free subset size is 3, for example {1,4,6}. Giving c ≤ 3/7.

B={1,2,3,4,5,6,10} also has maximal sum-free subset size of 3.

 

[Joffan]

I probably won't produce any more explicit sets after this, but just for something more to chew on,
B={1,2,3,4,5,6,8,10,12,15,16,18,20,24,25,30,32,36,40,48,50,60,64,80} has maximal sum-free subset size of 10, giving a new upper bound on c ≤ 10/24 = 5/12

 

[mfb]

@Joffan: See post #29 for the constant.

 

[Joffan]

@Joffan: See post #29 for the constant.

I was deliberately ignoring post#29 as it uses outside knowledge.

I thought real data sets might also help to restart the thought processes of those of us still interested in solving it and perhaps serve as test cases. A bit of groping around blindly perhaps, but that can occasionally turn up something interesting.