CSTBC: Theory Bridge CourseInstructor: Kevin Milans (milans@uiuc.edu) Newsgroup: news.cs.uiuc.edu/class.i2cs.theorybridge 

Photo by Bryan Clark 
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 = {1,2,3,4} S = {1,2} AS = {3,4}
About how it is possible to have z+z=c: For example, if instead of S={1,2} (which is not sumfree), 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 sumfree 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 nonnegative integers.. so this case is also impossible.
So what have we argued, so far? If we start out with a sumfree 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.
P = {c/2  c \in S} Q = {a+b  a,b \in S} R = {ca  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 sumfree 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 ca is not the same as ac. 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 AS is an example of a value z which, when added to S, introduces a sum. So AS is contained in (P union Q union R) and therefore AS 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.