Proving Sum-Free Sets: A Presentation

[Office_Shredder]

I'm doing a presentation on using probability to prove various results, and one of them is that given any set of natural numbers B, it contains a set A that is sum-free, i.e. no two elements in A sum to another element in A, such that $$|A| \geq \frac{|B|}{3}$$.

I looked around and found a slightly better result that there is always a sum free subset of B of magnitude $$|A| \geq \frac{|B+2|}{3}$$. I've been trying to construct an example for B that gets this bound or close to it, but it's not working out so well. Does anyone know of a good example of such a set, or if there's a better bound that's known?

 

[Martin Rattigan]

Is that no two distinct elements ...? I.e. would $\{1,2\}$ count as sum-free or not?

Then you're looking for a $B$ in which no subset $A$ with $|A|>(|B|+2)/3$ is sum free, but which has a sum-free subset of size $(|B|+2)/3$. Is that right?

(Why doesn't this drop out of your proof by the way?)

 

[Martin Rattigan]

Actually what I said can't be right because then any singleton other than $\{0\}$ would do for $B$, and even $\{0\}$ if elements in sums need to be distinct. Perhaps I should think about it a bit more.

 

[Martin Rattigan]

OK - give me a clue. Why isn't $B=\{1\}$ an example of a set that "gets" the bound? The bound in this case would be (1+2)/3=1. $B$ has a sum-free subset of this size viz. $\{1\}$ and has no larger sum-free subset (because it has no larger subset).

Off-beam, I assume, but why?

 

[Office_Shredder]

Yes, the set {1.2} is sum-free. You don't get to repeat elements. I don't know the proof for the better bound but the proof for the bound oesn't suggest it's a good one, or even how to tell whether this is a good bound without just testing every subset (take the set mod p for some large value of p and multiply it by random elements of Z_p. One such element must take 1/3 of B to the middle third of Z_p which is a sum-free set).

Singleton sets work but are pretty lame as examples

 

[Martin Rattigan]

OK, but $\{1,2\}$ is then an example for the same reason, so you'll have to specify what minimum size of example you want.