Proving Sum-Free Sets: A Presentation

  • Context: Graduate 
  • Thread starter Thread starter Office_Shredder
  • Start date Start date
  • Tags Tags
    Presentation Sets
Click For Summary

Discussion Overview

The discussion revolves around the concept of sum-free sets within the context of natural numbers. Participants explore the existence of a sum-free subset A of a given set B, aiming to establish bounds on the size of A relative to B, particularly focusing on the probability-based proof of such results.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant presents a result that for any set of natural numbers B, there exists a sum-free subset A such that |A| ≥ |B|/3.
  • Another participant suggests a potentially improved result stating that |A| ≥ |B+2|/3, and seeks examples to illustrate this bound.
  • Clarification is sought regarding whether the elements in A must be distinct, leading to questions about the nature of sum-free sets.
  • Participants discuss the implications of singleton sets as examples, questioning their relevance and the conditions under which they are considered sum-free.
  • One participant proposes testing subsets of B modulo a large prime to find a sum-free set, indicating a method for exploring the bounds further.

Areas of Agreement / Disagreement

Participants express uncertainty regarding the definitions and examples of sum-free sets, with some disagreement on the implications of specific examples like {1} and {1, 2}. The discussion remains unresolved with multiple competing views on the bounds and examples of sum-free sets.

Contextual Notes

Participants note limitations in their understanding of the bounds and the conditions under which sets are considered sum-free. There is also an acknowledgment of the need for clearer definitions regarding the distinctness of elements in the sets being discussed.

Who May Find This Useful

This discussion may be of interest to those studying combinatorial number theory, particularly in the context of sum-free sets and probabilistic methods in mathematics.

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
Messages
5,706
Reaction score
1,592
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?
 
Physics news on Phys.org
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?)
 
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.
 
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?
 
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
 
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.
 

Similar threads

Undergrad Meaning of "identify" & variations in different math context
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Trouble with a passage in Zariski & Samuel's Commutative algebra text
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Definition of minimal ideal using symbolic logic notation
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Meaning of "passage to the quotient"?
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Question about "A Group Epimorphism is Surjective"
  • · Replies 13 ·
Replies
13
Views
2K
Undergrad Confused about Gauss's Lemma of Irreducibility
  • · Replies 4 ·
Replies
4
Views
4K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Free Groups - Dmmit & Fooote - Section 6.3
  • · Replies 8 ·
Replies
8
Views
2K
MHB Free Groups - Dummit & Fooote - Section 6.3
  • · Replies 2 ·
Replies
2
Views
2K
MHB Tensor Products of Modules and Free Abelian Groups based on Cartesian Product
  • · Replies 2 ·
Replies
2
Views
2K