Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sumfree subsets

  1. Mar 28, 2010 #1

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  2. jcsd
  3. Apr 2, 2010 #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?)
     
  4. Apr 2, 2010 #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.
     
  5. Apr 2, 2010 #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?
     
  6. Apr 2, 2010 #5

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  7. Apr 2, 2010 #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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook