Sumfree subsets

  • #1
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,435
518
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 [tex] |A| \geq \frac{|B|}{3}[/tex].

I looked around and found a slightly better result that there is always a sum free subset of B of magnitude [tex] |A| \geq \frac{|B+2|}{3}[/tex]. 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?
 

Answers and Replies

  • #2
Is that no two distinct elements ...? I.e. would [itex]\{1,2\}[/itex] count as sum-free or not?

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

(Why doesn't this drop out of your proof by the way?)
 
  • #3
Actually what I said can't be right because then any singleton other than [itex]\{0\}[/itex] would do for [itex]B[/itex], and even [itex]\{0\}[/itex] if elements in sums need to be distinct. Perhaps I should think about it a bit more.
 
  • #4
OK - give me a clue. Why isn't [itex]B=\{1\}[/itex] an example of a set that "gets" the bound? The bound in this case would be (1+2)/3=1. [itex]B[/itex] has a sum-free subset of this size viz. [itex]\{1\}[/itex] and has no larger sum-free subset (because it has no larger subset).

Off-beam, I assume, but why?
 
  • #5
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,435
518
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 Zp. One such element must take 1/3 of B to the middle third of Zp which is a sum-free set).

Singleton sets work but are pretty lame as examples
 
  • #6
OK, but [itex]\{1,2\}[/itex] is then an example for the same reason, so you'll have to specify what minimum size of example you want.
 

Related Threads on Sumfree subsets

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
14K
  • Last Post
5
Replies
102
Views
14K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
3K
Top