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.