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


    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


    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook