Can You Find the Best Constant for Sum-Free Subsets?

  • Context: Graduate 
  • Thread starter Thread starter Office_Shredder
  • Start date Start date
  • Tags Tags
    Challenge Subsets Sum
Click For Summary

Discussion Overview

The discussion revolves around finding a constant \( c > 0 \) such that for every finite set of non-zero integers \( B \), there exists a sum-free subset \( A \) of \( B \) with \( |A| \geq c|B| \). The conversation explores theoretical approaches, potential bounds for \( c \), and specific cases of integer sets.

Discussion Character

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

Main Points Raised

  • Some participants clarify that a sum-free set cannot contain zero, emphasizing the importance of specifying non-zero integers in the problem statement.
  • One participant suggests simplifying the problem by considering only positive integers, proposing that the same constant \( c_p \) could apply to negative integers as well.
  • Another participant notes that if all elements of \( B \) are odd, then \( A = B \) and \( c = 1 \) could be a solution.
  • Several participants propose upper limits for \( c \), with one stating that if \( |B| = 3 \) and \( B \) is not sum-free, then \( c \leq 2/3 \), while another gives an example with \( B = \{1, 2\} \) leading to \( c \leq 1/2 \).
  • One participant discusses the implications of adding elements with negative counterparts to a sum-free set, suggesting it could influence the value of \( c \).
  • A later reply questions the validity of certain arguments regarding residues and modular arithmetic, indicating confusion and a need for clarification on the conditions for sum-free sets.
  • Another participant introduces a potential lower limit for \( c \) based on the density of prime numbers and their divisibility properties within the set \( B \).
  • One participant highlights that if \( |B| \) has a smallest prime divisor \( s \), then a subset \( A \) can be formed with elements having equal residues when divided by \( s \), leading to \( c = 1/s \).
  • Concerns are raised about the possibility of \( s \) being arbitrarily large, which could prevent a universal constant from being established.

Areas of Agreement / Disagreement

Participants express various viewpoints on the existence and bounds of the constant \( c \). There is no consensus on a definitive value for \( c \), and multiple competing perspectives remain throughout the discussion.

Contextual Notes

Participants note limitations in their arguments, such as the dependence on the properties of integers in set \( B \) and the challenges in establishing universal constants due to varying conditions of the elements.

  • #31
I probably won't produce any more explicit sets after this, but just for something more to chew on,
B={1,2,3,4,5,6,8,10,12,15,16,18,20,24,25,30,32,36,40,48,50,60,64,80} has maximal sum-free subset size of 10, giving a new upper bound on c ≤ 10/24 = 5/12
 
Mathematics news on Phys.org
  • #32
@Joffan: See post #29 for the constant.
 
  • #33
mfb said:
@Joffan: See post #29 for the constant.
I was deliberately ignoring post#29 as it uses outside knowledge.

I thought real data sets might also help to restart the thought processes of those of us still interested in solving it and perhaps serve as test cases. A bit of groping around blindly perhaps, but that can occasionally turn up something interesting.
 

Similar threads

  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 19 ·
Replies
19
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 5 ·
Replies
5
Views
1K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 66 ·
3
Replies
66
Views
7K
  • · Replies 5 ·
Replies
5
Views
4K
  • · Replies 1 ·
Replies
1
Views
2K