Sums of cubes: multiple representations

I’m continuing a short series of posts on representing numbers as a sum of three cubes; previous posts are 33 is the sum of three cubes and More sums of three cubes.

We now know that every number less than 100 which is not equivalent to (\pm 4) \pmod 9 can be written as a sum of three cubes. But for some of them we only know of one such representation, which can involve very large numbers. Is it possible that there are yet more ways, using even larger numbers?

Tricubic sums for 0

0 can of course be written as 0^3 + 0^3 + 0^3, but in fact it can be written as a sum of three cubes in infinitely many ways: pick any number c, then 0 = 0^3 + c^3 + (-c)^3. In fact, we know these are must be the only tricubic sums for 0. For suppose there were some nonzero x, y, and z such that 0 = x^3 + y^3 + z^3. In order to get a sum of zero, one of them has to be negative and two positive, or vice versa. If two are negative, then just negate the entire equation so that two are positive and one negative. Then move the negative one (say, z) to the other side of the equation, giving us x^3 + y^3 = z^3—but this would contradict Fermat’s Last Theorem!1

Tricubic sums for 1

1 can of course be written in infinitely many ways as 1^3 + c^3 + (-c)^3. However, there are also other ways. For example, as you can easily check for yourself,

1 = 9^3 + (-6)^3 + (-8)^3.

In fact, for any integer value of b, it turns out that

1 = (9b^4)^3+(3b-9b^4)^3+(1-9b^3)^3.

Let’s prove it! Remember that by the Binomial Theorem, (x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3. There are a lot of exponents and such to keep track of, but ultimately the algebra is not hard, just somewhat tedious:

\begin{array}{cl} & (9b^4)^3+(3b-9b^4)^3+(1-9b^3)^3 \\[1em] =& (9b^4)^3 + \big[(3b)^3 + 3 (3b)^2 (-9b^4) + 3 (3b) (-9b^4)^2 + (-9b^4)^3\big] + \big[1^3 + 3(1^2)(-9b^3) + 3(1)(-9b^3)^2 + (-9b^3)^3\big] \\[1em] =& 3^6 b^{12} + 3^3 b^3 - 3^5 b^6 + 3^6 b^9 - 3^6 b^{12} + 1 - 3^3 b^3 + 3^5 b^6 - 3^6 b^9 \\[1em] =& 1\end{array}

If you look carefully, you’ll see that everything cancels in the last step except for the single 1!

I got the example 1 = 9^3 + (-6)^3 + (-8)^3 by choosing b = 1. As another example, if we pick b = 47, then we get

1 = 43917129^3 + (-43916988)^3 + (-934406)^3

which you can verify for yourself!

Tricubic sums for 2

There are also infinitely many tricubic sums for 2: for any value of c,

2 = (1 + 6c^3)^3 + (1 - 6c^3)^3 + (-6c^2)^3

I’ll let you prove this one yourself. Just expand using the Binomial Theorem and watch everything magically cancel!

Tricubic sums for 3 and beyond

It turns out that as of this writing (September 2019), we only know of two tricubic sums for 3, both rather small:

3 = 1^3 + 1^3 + 1^3 = 4^3 + 4^3 + (-5)^3.

Are there any more? No one knows. However, in 1992, Roger Heath-Brown published a paper in which he conjectured that every number not of the form \pm 4 \pmod 9 has not just one but infinitely many tricubic sums! If true, this means there are infinitely many more tricubic sums for 3 in particular—but if so they involve rather large numbers. So rather than tackling 114 (the current smallest number for which we don’t know a tricubic sum), the next big prize might be to find another tricubic sum for the humble 3. Indeed, Andrew Booker says as much in his Numberphile interview.

  1. We don’t actually need to invoke Fermat’s Last Theorem in full generality—the n=3 case of Fermat’s Last Theorem was first proved by Euler in 1770.

Posted in number theory | Tagged , , , , | Leave a comment

More sums of three cubes

About six months ago I wrote about the recent discovery that 33 can be written as the sum of three cubes. At that time, the only remaining number less than 100 whose status was still unknown was 42. And just recently that, too, has fallen: thanks to Andrew Booker and Andrew Sutherland, we now know that

\displaystyle 42=(-80538738812075974)^3+80435758145817515^3+12602123297335631^3.

Again, this was very difficult to find (it required 1.3 million hours of computer time!) but very easy to verify: you can plug the above numbers into a computer yourself and see that you get 42. In fact, I’ve set up some links here so you can try it yourself using either Wolfram Alpha or Python. (Sadly, most graphing calculators don’t have enough precision to represent these numbers exactly. But seriously, click one of the links above and try it out!)

I still don’t understand the math behind the algorithm Booker and Sutherland used (I tried reading the paper but quickly got lost, and my sense is that I would probably have to spend at least several months doing background reading to be able to understand it). But this time around I’ve been learning more about the sums of three cubes problem itself. Today I’ll write a bit about which numbers actually have a hope of being written as a sum of three cubes, and in a future post I plan to write about numbers that have multiple representations as sums of cubes.

For the rest of this post I’m going to use the word tricubic to refer to numbers which can be written as a sum of three cubes. So, for example, we now know that 42 is tricubic. I’ll also say tricubic sum to refer to three cubes that add up to a given number, for example, “1^3 + 2^3 + 3^3 is a tricubic sum for 36”.

Which numbers are tricubic?

Some numbers definitely aren’t tricubic: for example, 13. How did I know that? The key is to look at the remainders of cubes \pmod 9:

\begin{array}{rcl}0^3 &=& 0 \\[0.5em] 1^3 &=& 1 \\[0.5em] 2^3 &=& 8 \equiv (-1) \pmod 9 \\[0.5em] 3^3 &=& 27 \equiv 0 \pmod 9 \\[0.5em] 4^3 &=& 64 \equiv 1 \pmod 9 \\[0.5em] 5^3 &=& 8 \equiv (-1) \pmod 9 \\[0.5em] 6^3 &=& 216 \equiv 0 \pmod 9 \\[0.5em] 7^3 &=& 343 \equiv 1 \pmod 9 \\[0.5em] 8^3 &=& 512 \equiv (-1) \pmod 9\end{array}

Notice that in the above table we only ever get remainders of -1, 0, or 1. And since every integer is equivalent, \pmod 9, to one of the numbers from 0 through 8, this table actually tells us everything we need to know: every integer cube will be either a multiple of 9, one more than a multiple of 9, or one less. By adding up three remainders which are all -1, 0, or 1, you can get any remainder between -3 and 3, inclusive. But that leaves out exactly two remainders you can’t get: 4 and 5. That’s how I knew 13 is not tricubic: 13 = 9 + 4 is four more than a multiple of 9.

OK, so now we know that any number either 4 or 5 more than a multiple of 9 is not tricubic. What about other numbers? Maybe if we look at remainders modulo some other divisor, say, 347, we can rule out other numbers in a similar way? Actually, no! So far it seems like this simple restriction is the only restriction on tricubic numbers: the conjecture is that every number not of the form 9k + \{4,5\} is tricubic—but right now this is only a conjecture; no one has yet managed to prove it!

So, in general, numbers fall into three groups:

  • Numbers of the form 9k + 4 or 9k + 5 which we know are not tricubic: \{4, 5, 13, 14, 22, 23, 31, 32, \dots\}.
  • Numbers which we know are tricubic, because we know of at least one tricubic sum for them: \{0, 1, 2, 3, 6, 7, 8, \dots\}.
  • Numbers which we think are probably tricubic, but we currently don’t actually know: \{114, 165, 390, 579, 627, \dots\}

Where do we go from here?

Progress on this problem could theoretically come in a lot of different ways.

First, someone could prove that there are additional numbers which are not tricubic. But as far as I can tell, everyone thinks this is pretty unlikely.

Someone could find a way to write some additional numbers as sums of three cubes. For example, the smallest number whose tricubic status we don’t currently know is 114; someone might find a way to write 114 as a sum of three cubes. However, the amount of computer time necessary to search for these may get prohibitively large: as I mentioned earlier, finding a tricubic sum for 42 required 1.3 million hours of computer time. Note, however, that finding 33 and 42 was possible specifically because Andrew Booker came up with a better algorithm than what had been used before. So perhaps someone will come up with an even better algorithm that makes it feasible to search for larger tricubic sums. At some point, however, people will lose interest: finding bigger and bigger tricubic sums just gets boring after a while.

Someone could prove that every number not of the form 9k + \{4,5\} is tricubic by finding an algorithm which takes a number n as input, and spits out a tricubic sum for n. But wait, you ask, don’t we already have that? Weren’t 33 and 42 found using an algorithm? Well, yes, but the search algorithm used to find tricubic sums for 33 and 42 was not guaranteed to find anything. You give it an upper limit for the size of the cubes involved, and it will search everything below that, but there is no guarantee that it will find what it is looking for. You could easily modify the program to run as follows: given a number n for which we wish to find a tricubic sum, start by searching for tricubic sums under a certain upper bound; if nothing is found, increase the upper bound and try again. If nothing is found the second time, increase the upper bound yet again, and so on. This is called a semi-decision procedure: if a tricubic sum exists for n, this program will eventually find it, but if no tricubic sum exists then it will simply run forever (in theory, that is; of course any real computer would run out of memory long before that). So this doesn’t count as a proof because it doesn’t guarantee to find a tricubic sum for every number. An algorithmic proof would consist of an algorithm to find a tricubic sum for any suitable input number, along with a proof that the program will always return a tricubic sum in a finite amount of time for any input.

I don’t actually find the above scenario very likely (though a dramatic example of this kind is the recent proof that every positive integer is a sum of three palindromes). I find it more likely that someone will prove that every number not of the form 9k + \{4,5\} is tricubic, but in a way that is non-effective. That is, we would know that every suitable number must be tricubic, but the proof would not actually give us a way to find a tricubic sum for any given n. (There is a very interesting distinction here between classical and constructive mathematics; maybe I’ll write more on this in a future post!)

Posted in number theory | Tagged , , | 5 Comments

A combinatorial proof: the story so far

In my last post I reintroduced this seemingly odd phenomenon:

Start with n+1 consecutive integers and raise them all to the nth power. Then repeatedly take pairwise differences (i.e. subtract the first from the second, and the second from the third, etc.) until you are left with only one number. That number will always be n!, that is n factorial.

Simon Tatham left a comment on my previous post with a concise algebraic proof; perhaps I’ll write another post expanding on it. But for now I’m not interested in giving the shortest possible proof. My goal is to give a combinatorial proof, that is, a proof of the form “these two numbers must be equal because they are two different ways to count the same set of things”. Not because it is short or easy, but just because it is fun and involves some nice pictures!

So, where are we? In Differences of powers of consecutive integers, Part II, I showed that if we start out with the sequence of numbers k^n,  (k+1)^n, \dots, (k+n)^n and repeatedly take pairwise differences, we end up with a result that consists of adding and subtracting each (k+i)^n a particular number of times. In particular, the number of times (k+i)^n is added or subtracted is exactly the ith entry on the nth row of Pascal’s triangle, that is, \binom{n}{i}. Also, they alternate being added or subtracted. Putting this together into formal notation, we end up with

\displaystyle \sum_{i=0}^n (-1)^{n-i} \binom{n}{i}(k+i)^n

See the above-linked post for an explanation of how Pascal’s triangle enters into it. In any case, our goal is to show this sum is actually equal to n!.

In Combinatorial proofs I explained the idea of a combinatorial proof in general, and gave a simple example involving binomial coefficients.

Then, in Making our equation count, I explained how different parts of this expression can be interpreted as counting something:

  • Factorial, n!, counts the number of permutations of n things, or, from another point of view, the number of 1-1 matchings between two sets of n things.

  • A binomial coefficient \binom{n}{i} is the number of ways to choose exactly i out of n things.

  • Exponentiation, a^b, counts the number of functions from a set of size b to a set of size a. For example, here are the 3^3 = 27 different functions from a set of size 3 to another set of size 3.

  • Finally, that (-1)^{n-i} thing should look sort of familiar—any time you see an alternating sum like this, you should think of the Principle of Inclusion-Exclusion (PIE). More on this soon!

Posted in arithmetic, combinatorics, proof | Tagged , , , | Leave a comment

A combinatorial proof: reboot!

More than seven years ago I wrote about a curious phenomenon, which I found out about from Patrick Vennebush: if you start with a sequence of n + 1 consecutive nth powers, and repeatedly take pairwise differences, you always end up with n!, that is, n factorial.

Repeating the example I used in that post seven years ago, suppose we choose n=4, and start with the five consecutive integers 23, 24, 25, 26, 27. We raise them all to the fourth power, giving us

279841, 331776, 390625, 456976, 531441

Now we take pairwise differences: 331776 - 279841 = 51935, then 390625 - 331776 = 58849, and so on, and we get the new list

51935, 58849, 66351, 74465

Repeating the difference procedure gives

6914, 7502, 8114

588, 612


And 24, of course, is 4! = 1 \cdot 2 \cdot 3 \cdot 4.

I came up with a very cool proof of this, and started to explain it, but got stuck on how to explain the Principle of Inclusion-Exclusion (PIE). But now that I’ve finally done that in the last six posts (A probability puzzle, Probabilistic PIE, Have a piece of PIE, Formal PIE, PIE: proof by algebra, PIE: proof by counting), I’m finally going to finish it! Next time I’ll recap the story so far, with links back to my previous posts, and then we’ll forge onward.

Posted in arithmetic, combinatorics, proof | Tagged , , , | 11 Comments

PIE: proof by counting

Recall the setup: we have a universal set U and a collection of subsets A_1, A_2, A_3, and so on, up to A_n. PIE claims that we can compute the number of elements of U that are in none of the A_i (that is, |U| - |A_1 \cup A_2 \cup \dots \cup A_n|) if we take the sizes of every possible intersection of some of the sets (including none of them, which yields U itself), and alternately add (if we intersected an even number of sets) or subtract (if odd). That is, using formal notation,

\displaystyle \left| |U| - \bigcup_{i = 1}^n A_i \right| = \sum_{S \subseteq \{1, \dots, n\}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|

Last time, we proved this using some algebra. This time, we’re going to prove it by counting. Consider a particular (arbitrary) element x \in U. We want to see how many times x gets counted: we count 1 for each intersection containing x that gets added, and -1 for each intersection containing x that gets subtracted. In the end, x should end up being counted exactly once if it’s not in any of the A_i, and exactly zero times otherwise.

So, suppose x is in exactly k of the sets A_i. Let’s consider intersections of different numbers of sets and see how many times x gets counted in each.

  • There is only one way to intersect 0 of the sets, which gives U itself. x is definitely in there, so including |U| means x gets counted once.

  • “Intersecting one set” sounds nonsensical, but really it just means we are considering the sets A_1, A_2, etc. by themselves; these all get subtracted. By assumption, x is in exactly k of them, so it gets counted -k times.

  • There are a bunch of different ways to intersect two sets, A_i \cap A_j. How many of them contain x? Of course x is in A_i \cap A_j exactly when it is in both A_i and A_j, so the number of two-set intersections containing x is the number of different ways to pick two out of the k sets containing x, that is, \binom{k}{2}. These all get added, so x is counted \binom{k}{2} times.

  • Likewise with intersections of three sets: the only way for x to end up in an intersection of three sets is if x is contained in all of them, and there are \binom{k}{3} ways to choose three out of the k sets containing x. These get subtracted.

In general, there are \binom{k}{i} different intersections of exactly i sets which contain x, up through i = k. So, all in all, x gets counted a grand total of

\displaystyle\binom{k}{0} - \binom{k}{1} + \binom{k}{2} - \binom{k}{3} + \dots \pm \binom{k}{k}

times. Now, when k = 0, this is just \binom{0}{0} = 1, which makes sense: if x is in none of the A_i, then it gets counted exactly once (as a part of U itself), just as it should be. Otherwise, we have an alternating sum of successive binomial coefficients—that is, we add up a row of Pascal’s triangle with alternating signs. Such an alternating sum of binomial coefficients is always zero, which I proved in another blog post. And that’s also as it should be: if x is in at least one of the A_i then we ultimately want it to be counted zero times.

Posted in combinatorics, pattern, proof | Tagged , , , , | 1 Comment

PIE: proof by algebra

In my previous post I stated a very formal, general form of the Principle of Inclusion-Exclusion, or PIE.1 In this post I am going to outline one proof of PIE. I’m not going to give a completely formal proof, because the notation gets quite hairy (imagine doing algebraic manipulations on the formulas in the previous post)! But I hope to give enough of an intuition that when I say “and so on”, intrepid readers with good algebra skills should be able to complete a formal algebraic proof.

Set algebra

For the proof, we will first need a few algebraic facts about set operations:

  1. Set intersection distributes over union, that is,

    (A \cup B) \cap C = (A \cap C) \cup (B \cap C).

    You should be able to convince yourself of this by staring at a picture:

    Also, if you think of union as being like addition and intersection as being like multiplication, then this says (A +  B)C = AC + BC, which makes it easy to remember. (Although unlike the case of addition and multiplication, union also distributes over intersection, that is, (A \cap B) \cup C = (A \cup C) \cap  (B \cup C)—you might like to try convincing yourself that this works. We won’t need this fact, though.)

  2. Set intersection has some nice properties:

    • It is idempotent, that is, A \cap A = A: if you intersect a set with itself you get the same set back.

    • It is commutative, that is, A \cap B = B \cap A: the order of sets being intersected doesn’t matter.

    • Finally, it is associative, that is, (A \cap B) \cap C = A \cap (B \cap C): if we have a sequence of intersections to do it doesn’t matter which one we start with. Because of this we can just write things like A \cap B \cap C \cap D without worrying about parentheses.

    Later in the proof we will use these properties together to argue, for example, that A \cap C \cap B \cap C = A \cap B \cap C: associativity means it doesn’t matter where we put parentheses; commutativity means we can swap the C and B, and then idempotence says that the two adjacent copies of C can be replaced by one copy.

There are lots of other nice properties, too—for example, union has similar properties to intersection—but these are the only ones we will need for the proof below.

Finally, to save space and make things a bit easier to read, in the rest of the post I will sometimes omit the \cap symbol and write just AB instead of A \cap B. For example, using this notation the fact that intersection distributes over union can be written

(A \cup B)C = AC \cup BC.

The proof

Onward to the proof! We’ll prove the alternative presentation of PIE I introduced in my previous post, which tells us how to compute the size of a set like A \cup B \cup C \cup \dots. The proof is by induction on the number of sets being unioned.

First, for n = 1, PIE just says that |A| = |A|. Done!

Well, actually, to get things off the ground we really need to treat n=2 as a base case as well. In this case, PIE says that

|A \cup B| = |A| + |B| - |AB|

(remember that AB means A \cap B). We’ll call this equation PIE2. We can prove it by staring at another picture:

This is pretty clear: adding the sizes of A and B double-counts their overlap, so we have to subtract it once.

Now is where it gets more interesting. Consider the case with three sets, |A \cup B \cup C|. The trick is to start by writing A \cup B \cup C as (A \cup B) \cup C and then to apply PIE2, using A \cup B as the first set and C as the second. In the proof below I’ve written the justification for each step in curly brackets.

\begin{array}{rcl}|A \cup B \cup C| &=& |(A \cup B) \cup C| \\[1em] &=& \quad\text{\{ PIE2 \}} \\[1em] && |A \cup B| + |C| - |(A \cup B)C| \\[1em] &=& \quad\text{\{ intersection distributes over union \}} \\[1em] && |A \cup B| + |C| - |AC \cup BC| \\[1em] &=& \quad\text{\{ PIE2, twice \}} \\[1em] && (|A| + |B| - |AB|) + |C| - (|AC| + |BC| - |ACBC|) \\[1em] &=& \quad\text{\{ intersection properties, rearrange \}} \\[1em] && |A| + |B| + |C| - |AB| - |AC| - |BC| + |ABC| \end{array}

Notice in the last step how we turned ACBC into ABC—recall that the properties of intersection let us reorder the sets in an intersection like this and get rid of duplicates.

And there we go, we have derived PIE for n = 3 just using PIE2 and the laws of set algebra! We’ll call this result PIE3. Now, what about the case for n = 4?

\begin{array}{rcl}|A \cup B \cup C \cup D| &=& |(A \cup B \cup C) \cup D| \\[1em] &=& \quad\text{\{ PIE2 \}} \\[1em] && |A \cup B \cup C| + |D| - |(A \cup B \cup C)D| \\[1em] &=& \quad\text{\{ intersection distributes over union \}} \\[1em] && |A \cup B \cup C| + |D| - |AD \cup BD \cup CD| \\[1em] &=& \quad\text{\{ PIE3, twice \}} \\[1em] \dots \end{array}

There is a lot of algebra to do after applying PIE3 twice, but I think it’s actually better to not do it and instead focus on the big picture. We already know what |A \cup B \cup C| is. We get every combination of intersections among A, B, and C, added or subtracted according to whether the number is odd or even. But what about |AD \cup BD \cup CD|? Notice it’s the same as |A \cup B \cup C| but where each set has been intersected with D. We’re going to end up with every possible intersection between AD, BD, and CD, but because we can cancel out duplicate copies of D, this is the same as taking every possible intersection between A, B, and C, and then intersecting each with one copy of D. Also note that because we’re subtracting |AD \cup BD \cup CD|, the signs will be flipped relative to what we got with |A \cup B \cup C|—which makes sense since each term will have one extra set in it (namely, D) which will turn odd intersections into even and vice versa. In other words, at a very high level we will end up with

(all combinations of A,B,C) + D – (all combinations of A,B,C with a D added)

Notice how every possible combination of A, B, C, and D other than the empty intersection shows up exactly once, with the correct sign: every combination that doesn’t include D shows up in the first part (with the correct sign); then |D| is added by itself; then every combination that does include D and at least one other set shows up in the last part (with sign flipped to reflect the addition of one extra set).

In general, you can see how this is going to work. For each n we can prove PIE(n+1), that is, the version of PIE for a union of n+1 sets, by splitting off a single set X, using PIE2 like so:

|(A_1 \cup \dots \cup A_n) \cup X| = |A_1 \cup \dots \cup A_n| + |X| - |(A_1 \cup \dots \cup A_n)X|

and then using PIEn twice, once yielding all combinations without X, and once yielding all combinations with X. As I said, the notation to write that out formally (without any ellipses!) gets a bit hairy, but hopefully the idea makes sense!

Next time we’ll see a completely different proof of PIE, that relies on counting rather than algebra.

  1. It turns out there are even more general forms—for example see Callan McGill’s comment on my previous post—perhaps a later post!

Posted in combinatorics, induction, pattern, proof | Tagged , , , , , , | 2 Comments

Formal PIE

I’ve been talking informally about the Principle of Inclusion-Exclusion but I realized it would be useful to state it more formally before proceeding to some proofs. The only problem is that a fully formal statement of PIE has a lot of details and uses a lot of notation—so I’ll state it formally and then spend some time going through and explaining the parts carefully.

Suppose we have a collection of n finite sets A_1, A_2, A_3, and so on up to A_n, which are all subsets of a finite set U. We think of U as the “universe”, i.e. the entire population of things we are considering, and all the A_i are sets which “live in” the universe. Each set A_i typically represents a subpopulation with a particular property. For example, U might be the set of all people; then A_1 might be the set of people named Brent, A_2 might be the set of people who own a dog, and so on. Or as another example, U might be the set of natural numbers up to one million, and then A_1 might be the even numbers up to one million, A_2 might be the prime numbers less than one million, A_3 might be the set of all the ages I’ve ever been in my life, and so on.

The diagram below illustrates the general situation for n=3. The big green rectangle is the universe set U; the blue circles represent the three subsets A_1, A_2, and A_3, which in general may overlap, as in the diagram (though they don’t have to).

As I’ve presented it so far, PIE then tells us how to compute the number of elements of the universe which are not in any of the A_i, represented by the green shaded area in the diagram above. Put another way, this is the number of elements of the universe which have none of the properties (e.g. people not named Brent who don’t own a dog; natural numbers up to one million which aren’t even or prime or an age I’ve ever been; etc.).

PIE, formally

Without further ado, here is PIE:

\displaystyle |U| - \left| \bigcup_{i = 1}^n A_i \right| = \sum_{S \subseteq \{1 \dots n\}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|

Let’s go through this piece by piece. On the left-hand side, the big union symbol works just like a summation symbol, i.e. big-sigma notation: so \displaystyle \bigcup_{i=1}^n A_i means A_1 \cup A_2 \cup \dots \cup A_n, the union of all the A_i. Unioning the sets throws out duplicates, so the union represents all the elements of the universe which are in one or more of the A_i (i.e. the blue area in the diagram above). Subtracting this number from the size of U then gives the number of elements which aren’t in any of the A_i.

The right-hand side is a bit more complicated. First, \displaystyle \sum_{S \subseteq \{1 \dots n\}} means we take a sum over every subset of \{1 \dots n\}. That is, we will get one number for every possible subset of \{1 \dots n\} (all 2^n of them), and we add all these numbers up. Now, for each subset S, the big intersection symbol \displaystyle \bigcap_{i \in S} A_i means to take the intersection of all the A_i represented by S. For example, if S = \{2, 3, 7, 9\}, then we get the intersection A_2 \cap A_3 \cap A_7 \cap A_9. We find the size of this intersection and make it either positive or negative: raising -1 to a power keeps flipping back and forth between 1 (if the power is even) and -1 (if the power is odd). So (-1)^{|S|} means we should add the term if the number of A_i in the intersection is even, and subtract if the number is odd.

There is one subtle point to make, which I also mentioned in my previous post. All subsets of \{1 \dots n\} includes the empty subset, S = \varnothing, and it’s not necessarily obvious what the intersection \displaystyle \bigcap_{i \in S} A_i means when S is the empty set. How are we supposed to take the intersection of zero sets? To make everything work, we have to interpret it as being equal to the entire universe U. However, this is actually sensible, since U is like the “identity” for intersection: U \cap A_i = A_i for each A_i. Put another way, intersecting always results in a smaller set than you started with, so when intersecting you always start with the biggest possible set (namely, the universe U) and then the result gets smaller and smaller as you intersect more sets. That is, we can interpret A_i \cap A_j \cap A_k \cap \dots as (((U \cap A_i) \cap A_j) \cap A_k) \cap \dots. So if you don’t intersect any A_i you’re just left with the starting set U. (This is exactly the same argument for why a union of zero sets should be the empty set, but that certainly feels more intuitive! Pop quiz: what do we get if we’re taking the product of a set of numbers and the set is empty?)

For some examples, see the previous post. You might like to try writing out PIE for n=4.

An alternative presentation

Since we just argued why the empty set results in a term of |U| on the right-hand side (note it is positive since (-1)^{|\varnothing|} = (-1)^0 = 1), and there is also a positive |U| term on the left-hand side, we can subtract |U| from both sides to cancel them out, leaving this:

\displaystyle - \left| \bigcup_{i = 1}^n A_i \right| = \sum_{\stackrel{S \subseteq \{1 \dots n\}}{S \neq \varnothing}} (-1)^{|S|} \left|\bigcap_{i \in S} A_i\right|

(Notice how we got rid of the |U| term on the right-hand side just by specifying that the summation should not use S = \varnothing.)

If we finally negate both sides, we get an alternative form of PIE which is actually the way it is typically presented. We can negate every term on the right-hand side by simply adding 1 to the power of (-1), so any terms which used to be positive are now negative and vice versa.

\displaystyle \left| \bigcup_{i = 1}^n A_i \right| = \sum_{\stackrel{S \subseteq \{1 \dots n\}}{S \neq \varnothing}} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|

For example, when n = 3 this says

|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|.

This alternative presentation is nice because it tells us directly about the size of the union of all the A_i, i.e. the number of things in at least one of the sets (the blue region in the diagram), rather than the number of things in none of the sets (the green region). It seems like we would typically care more about the blue region; talking about the green region seems roundabout. However, as you can see, the right-hand side becomes a bit more awkward in this alternative presentation, because of the need to specify the extra condition S \neq \varnothing, and the +1 in the exponent of the (-1). Strange as it might seem at first, PIE is really more natural when phrased in terms of the number of things in none of the sets A_i.

Posted in combinatorics, pattern | Tagged , , , , , | 3 Comments