LJ Math
So, I was talking with sammka tonight, and our conversation turned to Livejournal. Specifically, friends lists. I was mentioning why I chose to keep my own friends list small -- I wanted to make sure my private posts were only seen by people I trusted, and I was had mistakenly thought that message filters were only available as a paid feature. Sammka showed me how I could set up filters for my friends list, and as I put a few together, I commented, "You know, I'm almost anal enough to have a filter for every possible subset, but I know how big the power set gets." Sammka gave me a smiley, and said that I could send messages to the union of multiple filters, so I could just have a separate filter for each friend if my flist were small enough. She commented how she wished she could have other operators, like intersection and set difference -- heck, just adding complementation would suffice. I countered by observing that a single operator, the complement of the union, could generate all the other operators, assuming you could freely compose and parenthesis operations.
I then wondered: if you have this expanded set of operators, (union, intersection, and complementation, though this is all equivalent to complementary union) can you get away with a smaller basis? In other words, given that you can generate all possible subsets of your flist with n filters, one for each friend, with unions, can you get away with using even fewer filters, and still be able to send messages to any desired subset, with the extra operators?
Zeroth guess: Obviously yes. Those extra operators must give you more expressive power. Now, if I draw a Karnaugh map...
First guess: Wait a second. If we have k filters, we can combine these to form all of the Boolean functions on k variables. And we're trying to get them to cover...all the Boolean functions on n variables. How many variables does it take to express all the Boolean functions on n variables? Obviously n. So no, we can't have a smaller basis. Obviously. I should be able to turn this into a proof...
First-and-a-halfth guess: D'oh! I'm not trying to span the set of all Boolean functions on n variables, I'm trying to span all the subsets of an n-element set. I should stop thinking about functions...
Second guess: Obviously yes! For n=2, a basis of size 1 clearly works, since we have complementation! That is, if I have a grand total of 2 friends, say sammka and zandperl, I can get by with but a single filter, consisting solely of Zandperl. If I want to send something to Sammka, I just send it to the complement of the Zandperl filter. If I want to send it to both of them, I use no filter. To send it to nobody, I could use the intersection of Zandperl and (not Zandperl). So n-1 filters should definitely suffice.
Third guess: But wait! Complementation basically gives you a free second subset for each original filter. So if we needed n filters before, now we only need n/2 -- rounded up, of course.
Fourth guess: Ooh! Maybe those Karnaugh maps weren't such a bad idea after all! I think I can do this with the base 2 log of n. Yeah, I totally can! Here's how:
Label your friends from 1 to n, in binary. Let's suppose that n is k bits long in binary -- clearly, k is the base 2 log of n, rounded up. We can then get away with just k filters. Let your ith (hee, the html to display that is ith, how pretty (and you don't want to know what the html to display that html was)) filter be the set of all friends who have a 1 in the ith bit of their label.
Now, you can get any single friend from these filters through complementation and intersection. For example, suppose I have 100 friends, and thus 7 filters, and matt_rah is friend number 88 -- that's 1011000 in binary. So I take filter 1 (his label begins with 1), the complement of filter 2 (the second bit is not 1), filter 3, filter 4, and the complements of filters 5, 6, and 7, and intersect all of those. The intersection is the set of all friends whose labels have a 1 in the first position, 0 in the second, 1 in the 3rd, 1 in the 4th, 0 in the 5th through 7th -- in other words, all friends whose label is 1011000, or Matt-Rah and Matt-Rah alone. And since I can get any single friend I want, I can isolate all of those that I want to send to, and then take the union of those singletons. Thus, I can get all subsets of my friend list with those 7 filters.
Fourth guess, postscript: So, the base 2 log of n suffices -- is it the lower bound? I'm pretty sure it is; can I prove it? Oh, yeah! If I can get all the subsets of my friends list, then I have to be able to get every single friend in isolation. And if I can send a message to, say, krchicken, I must be able to do this as a "pure" intersection, with no unions -- if it were a union, then each of the constituent parts would be either the set of KillerChicken, or the empty set. And if I can do it just as an intersection, I can do it as an intersection of every filter or its complement -- if it can be accomplished without filter X, just throw on X or its complement, whichever one happens to contain KillerChicken. Now, suppose I have k filters. How many different intersections of all the filters or their complements are there? 2^k. How many singleton sets do we need these intersections to cover? n. Therefore, 2^k>=n, so the base 2 log of n is in fact the lower bound. Q.E.D.
Conclusion: although I would currently need one filter for each of the 8 journals on my friends list to be fully exhaustive, if Livejournal had Sooper Boolean Filtering Technology, I would only need 3 filters. That's not much of an improvement, but sammka, who has 200 friends and thus lacks the space for an exhaustive set of filters, would need only 8 filters with SBFT. Hooray for sciencemath!
(The implementation of Sooper Boolean Filtering Technology is left as an exercise to the Livejournal programmers.)
I then wondered: if you have this expanded set of operators, (union, intersection, and complementation, though this is all equivalent to complementary union) can you get away with a smaller basis? In other words, given that you can generate all possible subsets of your flist with n filters, one for each friend, with unions, can you get away with using even fewer filters, and still be able to send messages to any desired subset, with the extra operators?
Zeroth guess: Obviously yes. Those extra operators must give you more expressive power. Now, if I draw a Karnaugh map...
First guess: Wait a second. If we have k filters, we can combine these to form all of the Boolean functions on k variables. And we're trying to get them to cover...all the Boolean functions on n variables. How many variables does it take to express all the Boolean functions on n variables? Obviously n. So no, we can't have a smaller basis. Obviously. I should be able to turn this into a proof...
First-and-a-halfth guess: D'oh! I'm not trying to span the set of all Boolean functions on n variables, I'm trying to span all the subsets of an n-element set. I should stop thinking about functions...
Second guess: Obviously yes! For n=2, a basis of size 1 clearly works, since we have complementation! That is, if I have a grand total of 2 friends, say sammka and zandperl, I can get by with but a single filter, consisting solely of Zandperl. If I want to send something to Sammka, I just send it to the complement of the Zandperl filter. If I want to send it to both of them, I use no filter. To send it to nobody, I could use the intersection of Zandperl and (not Zandperl). So n-1 filters should definitely suffice.
Third guess: But wait! Complementation basically gives you a free second subset for each original filter. So if we needed n filters before, now we only need n/2 -- rounded up, of course.
Fourth guess: Ooh! Maybe those Karnaugh maps weren't such a bad idea after all! I think I can do this with the base 2 log of n. Yeah, I totally can! Here's how:
Label your friends from 1 to n, in binary. Let's suppose that n is k bits long in binary -- clearly, k is the base 2 log of n, rounded up. We can then get away with just k filters. Let your ith (hee, the html to display that is ith, how pretty (and you don't want to know what the html to display that html was)) filter be the set of all friends who have a 1 in the ith bit of their label.
Now, you can get any single friend from these filters through complementation and intersection. For example, suppose I have 100 friends, and thus 7 filters, and matt_rah is friend number 88 -- that's 1011000 in binary. So I take filter 1 (his label begins with 1), the complement of filter 2 (the second bit is not 1), filter 3, filter 4, and the complements of filters 5, 6, and 7, and intersect all of those. The intersection is the set of all friends whose labels have a 1 in the first position, 0 in the second, 1 in the 3rd, 1 in the 4th, 0 in the 5th through 7th -- in other words, all friends whose label is 1011000, or Matt-Rah and Matt-Rah alone. And since I can get any single friend I want, I can isolate all of those that I want to send to, and then take the union of those singletons. Thus, I can get all subsets of my friend list with those 7 filters.
Fourth guess, postscript: So, the base 2 log of n suffices -- is it the lower bound? I'm pretty sure it is; can I prove it? Oh, yeah! If I can get all the subsets of my friends list, then I have to be able to get every single friend in isolation. And if I can send a message to, say, krchicken, I must be able to do this as a "pure" intersection, with no unions -- if it were a union, then each of the constituent parts would be either the set of KillerChicken, or the empty set. And if I can do it just as an intersection, I can do it as an intersection of every filter or its complement -- if it can be accomplished without filter X, just throw on X or its complement, whichever one happens to contain KillerChicken. Now, suppose I have k filters. How many different intersections of all the filters or their complements are there? 2^k. How many singleton sets do we need these intersections to cover? n. Therefore, 2^k>=n, so the base 2 log of n is in fact the lower bound. Q.E.D.
Conclusion: although I would currently need one filter for each of the 8 journals on my friends list to be fully exhaustive, if Livejournal had Sooper Boolean Filtering Technology, I would only need 3 filters. That's not much of an improvement, but sammka, who has 200 friends and thus lacks the space for an exhaustive set of filters, would need only 8 filters with SBFT. Hooray for sciencemath!
(The implementation of Sooper Boolean Filtering Technology is left as an exercise to the Livejournal programmers.)