Bridge

CSTBC: Theory Bridge Course

Instructor: Kevin Milans (milans@uiuc.edu)

Newsgroup: news.cs.uiuc.edu/class.i2cs.theory-bridge

Photo by Bryan Clark

Lecture 3, Homework 3

Q: Regarding HW3.4: here is my example. 
A = {1,2,3,4}
S = {1,2}
A-S = {3,4}
How is it possible to have z+z=c? If I assume z=3 then 3+3=6 but 6 does not belong to S, actually, not even to A either. Similarly, how is it possible to have a+z=c where a<>c? In any event, I get stuck at the line that says, "Note..........". Can you please elaborate upon this solution?
A: First, I should point out that {1,2} is not a sum-free set, because 1+1=2 and both 1 and 2 appear in {1,2}.

About how it is possible to have z+z=c: For example, if instead of S={1,2} (which is not sum-free), we just had S={2} (which is sum free), then we could not add z=1 to S, because then S would contain a sum of the form z+z=c (namely 1+1=2).

The idea behind the proof is to start out with a sum-free set S and show that there are only so many numbers that we can add to S which introduce a sum. So if adding a number z to S introduces a sum, then we can find a, b, c in (S union {z}) so that a + b = c. Because there are only three numbers in the equation a + b = c, clearly z must appear 0, 1, 2, or 3 times.

The rest of the proof considers each of those cases in turn, arguing that in each case, z can only be one of a limited number of values. For example -- and this case is not explicitly treated in the solution -- how could it be that z appears 0 times in the equation a + b = c? Well, the answer is that this is impossible -- if z appears 0 times in the equation a + b = c, then a,b,c are elements of S (because the only choices for a,b,c are elements in S and z), and so S would already have a sum before we added z, which is a contradiction.

Similarly, z cannot appear 3 times in the equation, because if a=z, b=z, and c=z, and it is true that a+b=c (which means z+z=z), then it must be the case that z=0. But we are only considering non-negative integers.. so this case is also impossible.

So what have we argued, so far? If we start out with a sum-free set S and adding z to S introduces a sum, then we can find a,b,c in (S union {z}) such that a + b = c, and it must be that 1 or 2 of a,b,c are equal z. Under these conditions, there are only so many possible integers that z can be.

Q: Can you also explain the part after "Note.." especially where you use k-based values for the three cases? I am not sure I am quite clear on them either.
A: Well, once we argue that z must be in one of 3 sets, as shown in the first displayed math in the solution ("It follows that z \in ..."), we then argue that each of these sets is not very large. Here, "very large" is relative to the size of S, our maximum sum-free subset of A. If it will help, we can let k'=|S|. Recall that we are assuming for a contradiction that k' <= k. To be more concrete, let's give names to the three sets. Let 
P = {c/2 | c \in S}
Q = {a+b | a,b \in S}
R = {c-a | c,a \in S and c is not equal to a}
In the first part of the proof, we argue that if z introduces a sum when added to the sum-free set S, z must be a member of (P union Q union R). In the second part of the proof, we find an upper bound the size of (P union Q union R). The size of (P union Q union R) is at most |P|+|Q|+|R|.

What is |P|? Well, each element in S contributes exactly one element to P because we form P by dividing each element in S by 2. Therefore |P| = |S| = k' <= k.

What about |Q|? How many sums can we make by choosing from the k' elements in S? Well, to get an upper bound on |Q|, we use the same trick as before -- we define 

X = {a+b | a,b \in S and a=b }
Y = {a+b | a,b \in S and a is not equal to b }
and, because Q = (X union Y), we have that |Q| <= |X| + |Y|. Clearly, |X| = |S| = k'. What about |Y|? Well, |Y| cannot be larger than the number of ways there are to choose two different elements a,b \in S. But by definition, there are exactly (|S| choose 2) = (k' choose 2) ways to choose two different elements a,b \in S. Therefore |Y| <= (k' choose 2). Putting all these steps together, 
|Q| <= |X| + |Y|
    <= k'  + (k' choose 2)
    <= k   + (k  choose 2)

What about |R|? Well, |R| is at most the number of ways to choose an ordered pair (c,a) from S with c not equal to a. (In contrast to our upper bound on |Y| where we just counted unordered pairs, here we need to count ordered pairs because c-a is not the same as a-c. Actually, we be more careful and get a stronger upper bound here, but we won't worry about that.) There are k' choices for c, and once we've chosen c, there are k'-1 remaining choices for a stronger upper bound here, but we won't worry about that.) There are k' choices for c, and once we've chosen c, there are k'-1 remaining choices for a so that a is different from c. Therefore |R| <= k'(k'-1). By our formula for the binomial coefficients from lecture 2, we know that k'(k'-1) = 2*(k' choose 2). Therefore 

|R| <= 2*(k' choose 2)
    <= 2*(k  choose 2)

Putting all the pieces together, 

|(P union Q union R)| <= |P| + |Q| + |R|
                      <= 3*(k choose 2) + 2*k.
But each element of A-S is an example of a value z which, when added to S, introduces a sum. So A-S is contained in (P union Q union R) and therefore |A-S| is at most 3*(k choose 2) + 2*k. Because |S| <= k, it must be that |A| is at most 3*(k choose 2) + 3*k.