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

Challenge 5: Sum Free Subsets

  1. Oct 25, 2013 #1

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    A set A of non-zero integers is called sum-free if for all choices of [itex] a,b\in A[/itex], a+b is not contained in A.

    The Challenge: Find a constant c > 0 such that for every finite set of integers B not containing 0, there is a subset A of B such that A is sum-free and |A| ≥ c|B|, where |A| means the number of elements of A.


    Every solution (by a new poster) which improves on the best constant known up until that point in the thread will be awarded a fresh 2 points, and of course alternate solutions which do not improve on the best known constant are more than welcome as well! Solutions which show a c exists but do not calculate it are also OK.
     
    Last edited: Oct 25, 2013
  2. jcsd
  3. Oct 25, 2013 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    I don't understand why you specified "non-zero integers", since a sum-free set of integers clearly can not contain 0.

    What do you mean by |A|, when A is a set? The number of elements in A? Some sort of norm?
     
  4. Oct 25, 2013 #3

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, it means the number of elements of A (I edited the OP to add that in for future viewers). I guess I didn't need to specify that a sum-free set doesn't contain zero, but it is mildly important that B not contain zero otherwise the set {0} screws up the statement of the problem.
     
  5. Oct 25, 2013 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Here's a first stab at simplifying the problem somewhat.

    Suppose we can find a ##c_p## which works when ##B## is restricted to contain only positive integers. Then of course the same ##c_p## will work if ##B## contains only negative integers.

    We can then solve the general case by removing either all of the negative integers or all of the positive integers from ##B##, whichever causes fewer elements to be removed. By doing so, we will have reduced ##|B|## by at most a factor of ##1/2##. Our solution for the positive case then gives us a subset ##A## containing at least ##(c_p/2)|B|## elements.

    So, to prove the existence of the required constant ##c##, we may without loss of generality assume that ##B## contains only positive integers. (In order to obtain the best possible ##c##, we may have to consider the general case.)
     
  6. Oct 26, 2013 #5

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    I'm not sure if this leads anywhere in the general case, but if all the elements of B are odd, then A = B and c = 1.

    How about dividing A into disjoint sets ##\{O_i2^k\}, k = 0, 1, \dots## where the ##O_i## are all odd numbers ....
     
    Last edited: Oct 26, 2013
  7. Oct 27, 2013 #6

    Filip Larsen

    User Avatar
    Gold Member

    Not sure if upper limits for c are considered useful in this context, but if they are there is an obvious one:

    If |B| = 3 and B is not sum-free, then |A| = 2 and, if c exists, we must have that c ≤ 2/3.

    (Working on a lower limit, but that is much harder :tongue:)
     
  8. Oct 27, 2013 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    An upper limit can be found by an example:
    B={1,2}, the largest sum-free subsets are A={1} and A={2}, so c≤1/2.

    If all elements of B are a common multiple of some integer n, we can construct B' by dividing all integers by n, and get the same problem again. Therefore, WLOG, we can assume that the largest common divisor of B is 1.
    I guess we can find an element for every prime number here, but that won't give a lower limit >0, as the prime number density goes to zero.

    There is an interesting "weighting" issue: If our smallest sum-free subset (SFS) A has an element a, we can also add an element -a without loosing the SFS-property. This can be shown by modifying "a+b=c" to "b=c+(-a)". If B has both a and -a, adding this element is a bit like a number with a weight of 2. To get a large minimal c, it is favorable to add this number, even if you have to kick out another number.


    I wonder if c=1/2 is the real value. Looking at small |B|, I didn't find any example where c has to be lower.
     
    Last edited: Oct 27, 2013
  9. Oct 28, 2013 #8

    Filip Larsen

    User Avatar
    Gold Member

    Oh, I completely missed that a and b can be the same number. Oh well ...
     
  10. Oct 28, 2013 #9
    Generalized oddness would be modular arithmetic. A necessary but not sufficient condition for a + b = c is that the residue of a + b divided by m is the same as the residue of c divided by m, a prime number.

    Let B be a set of random integers, consider the subset of B, A = {a, b}, which is clearly sum-free, the chance that an element c of B \ A has the same residue as a + b when divided by m is 1/m. Let p be the probability that a + b and c have the residue when divided by m.
     
    Last edited: Oct 28, 2013
  11. Oct 28, 2013 #10

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    What if a + a = b?
     
  12. Oct 29, 2013 #11
    True but ultimately irrelevant, start with a subset A = {a} which is clearly sum-free because a is a non-zero integer. a + b is still defined if a, b are elements of A. Change "random integers" to "random natural numbers".
    a + a = b does imply that the set {0, ..., m - 1} is the largest guaranteed sum-free subset. Since m can be every prime number smaller than the smallest prime number greater than the greatest element of B. The average of all possible m's divided by the size of B gives an approximation (A) of c.

    Approximate (B) the sum of all m's by including all non-prime numbers not greater than the greatest element of B, thus the approximation (A) of c is at most |B|/2 * 1/|B| = 1/2.
     
    Last edited: Oct 29, 2013
  13. Oct 29, 2013 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    {0, ..., m - 1} is not sum-free.
    If you have 0, the set is not sum-free at all. And what about examples like 1+2=3?
    {m, ..., 2m - 1} is sum-free, but that is trivial.

    I don't understand your argument.
     
  14. Oct 29, 2013 #13
    You're right to because it's a completely wrong argument, I must have been confused. If a sum a + b has a different residue when divided by m than c then a + b =/= c. The probability that a number has residue r when divided by m is 1/m.

    I must have had the 'different residues' in my mind and wrote that down without thinking. Very stupid.

    What it should have been: all the numbers that have the same residue not equal to 0 when divided by m form a sum-free set.
     
    Last edited: Oct 29, 2013
  15. Oct 29, 2013 #14

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Unfortunately, we cannot guarantee to get a fraction c>0 of those numbers. Most numbers could be divisible by m.

    Hmm, that might lead to an existence proof:

    Suppose we can find a series Bi with maximal SFS (sum-free subsets) Ai where |Ai| / |Bi goes to zero. In general, we have some choice for Ai, we choose one and fix it for the remaining analysis.

    Using the argument given by jbunniii in post 4, it is sufficient to consider sets with only positive numbers - if there is such a series, there is also a series where all sets have no negative numbers.

    Every subsequence of this will also have the same property and |Bi| has to go to infinity, so WLOG we can assume |Bi+1| > |Bi|.


    For an arbitrary prime p where a fraction mp of all elements in |B| is divisible by p, we can find a SFS of at least |B|*(1-mp)/(p-1) elements with the same remainder.

    Therefore, a lower limit on the fraction of elements in a maximal SFS is
    $$\max_{\text{p prime}} \frac{1-m_p}{p-1}$$

    How can we show that not all m_p can go to 1 at the same time?
     
  16. Oct 29, 2013 #15
    |B| = s*t where s is the smallest prime divisor of |B| and t = |B| / s.
    There exists a subset A, containg all elements with an equal residue r when divided by s, and where |A| >= t, by the pigeonhole principle.

    => c = 1 / s
     
  17. Oct 29, 2013 #16

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    s could be arbitrarily large so you don't get a universal constant, and if the elements all have residue 0 then it's not necessarily a sum-free subset.

    I think that collectively you guys are bringing something together, I'm going to rethink the scoring to reward teamwork I think.
     
  18. Nov 6, 2013 #17
    Not sure if this can help, nor whether anyone else thought of this already, but for any set [itex]B[/itex], you can associate another set [itex]B_n[/itex] containing all residues mod n of the elements of [itex]B[/itex]. (so for n = 2, this means all even numbers map to 0 and all odd numbers map to 1). So the problem can be reduced to sets of the form [itex]\{0,1,...,n-1\}[/itex].

    Let [itex]A_{n}[/itex] be the largest residue class mod n contained in [itex]B_{n}[/itex]. In "most" cases, this class will not be 0, and the set of all elements in B congruent to [itex]A_{n}[/itex] will be sum free. So we would have a set of size at least |B|/n and c = 1/n. (For n = 2, this would be equivalent to saying that if there are more odd numbers than even numbers, then the set of all odd numbers is sum-free and is larger than |B|/2 ).

    Unfortunately, it may be possible for most, or all, numbers in B to be multiples of n for n = 2,3,4... and so on until we can't talk about constants anymore...
     
  19. Nov 7, 2013 #18

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That's the issue, indeed. "most" cases are easy, the tricky part are the cases where the residue of 0 is the largest group for all small primes. This requires a large spread in the numbers and I have some feeling that we have to consider the largest number in the set to show that this would grow too fast (so even if the residues match, we get large sum-free subsets just because the numbers vary too much in their magnitude). But I did not manage to find a proof based on this.
     
  20. Nov 7, 2013 #19
    Since the originator of the problem seems to look for an approximation, a probabilistic attack seems in place, I haven't considered how exactly, but it certainly involves residues.
     
  21. Nov 7, 2013 #20

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You are looking for a maybe tiny fraction of all sets which could have values different from all other sets a probabilistic approach catches.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge 5: Sum Free Subsets
  1. Subset product (Replies: 2)

Loading...