Can you paint with all the colors of the integers?

I first encountered a variation of this problem while watching the film x+y, a drama about a boy participating in the International Mathematics Olympiad.

Suppose I paint the natural number 1,2,3,… red or blue, each number being painted exactly one color. Do you think you can always find two numbers a and b such that a, b, and a+b are all the same color, i.e. the triple (a,b,a+b) is monochromatic?

The answer is yes. In fact, if you are allowed to have a=b, then even in the worst case scenario you can find a solution without venturing past the number 5. This can be solved backwards: Assume 1 is red, then  in a worst case scenario 2 will be blue (otherwise you would have a=b=1 are red and so is a+b=2). By similar reasoning in the worst case scenario 4 is red, and thus 3 is blue (if 3 were red then we have 1, 3, and 4 are red). Now 5 is either blue or red but either way we have that (1, 4, 5) or (2, 3, 5) are monochromatic. So without even looking at the coloring of the numbers, we are sure to be able to find our monochromatic triple (a,b,a+b). If you aren’t allowed to have a=b, it’s a little more difficult but you can still do it. The worst case would look something like 1 Red, 2 Red, 3 Blue, 4 Red, 5 Blue, 6 Blue, 7 Blue, 8 Red, and regardless of what color 9 is, you’ll have your triple.

Now, what would happen if I were allowed to use more colors to paint? Suppose I can use 3, or 10, or even a million colors. Could I ever come up with a coloring of the natural numbers so that you won’t be able to find a monochromatic triple (a,b,a+b)? Obviously the technique above becomes much more laborious as at every step my repertoire of colors is rather large. Is there some number of colors that I can use though to make an impossible coloring, one in which you will not be able to find your monochromatic triple?

What if I further challenge you to look not for a triple (a,b,a+b) but instead for a 7-tuple (a,b,c,a+b,a+c,b+c,a+b+c) that is monochromatic? Or a 15-tuple (a,b,c,d, a+b,a+c,a+d,b+c,b+d,c+d,a+b+c,a+b+d,a+c+d,b+c+d,a+b+c+d)? Or worse, asking you to find an infinite set of natural numbers such that the sum of every finite subset is the same color. Are you feeling deterred by this Herculean task?

Fear not! For Hindman’s Theorem guarantees that regardless of how many colors I use, subject to it being finite of course, you can always do it. That’s right, even if I used a googolplex of colors, you can find an infinitely large set A of natural numbers such that ever finite subset S\subset A will have a sum \sum_{s\in S} s of the same color.

Note, we are not requiring that this set you find be closed under finite addition of repeated elements, i.e. if x is one color, we do not require x+x is to be the same color. This would actually be impossible even with just two colors as demonstrated by the coloring:

Red: 1
Blue: 2 3
Red: 4 5 6 7
Blue: 8 9 10 11 12 13 14 15
Red: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 …

Here, by creating lists that double in length and alternating between coloring the lists red and blue, every x and x+x are colored differently.

For more details I recommend taking a look at Baumgartner’s short proof of Hindman’s theorem, and also checking out the film x+y when you get a chance!



One day at a time


Expectations vs. Reality

If you asked me a year ago what I expected my second year of graduate school to be like, I might have answered: I would be done with my qualifying exams. I would have taken a bunch of interesting seminars. I would have picked my advisor. I would have organized awesome events. I would have had an awesome summer internship.

Yesterday, I found out that I did pass my final qualifying exam, a bit later than expected, but perfectly in line with what my department expects of its doctoral students. I only took one seminar but it led me to working on a fascinating project with the Yelp Dataset (blog post to follow). Unfortunately, I am not much closer to having an advisor. However, I helped organize some well attended events. I didn’t have an internship, but I still had an awesome summer and learned a lot of mathematics.


Lessons Learned

So what happened? I do not want to go into too much detail, but if you’re interested you can can get slight peek of the events by reading UCLA’s Discrimination Prevention Office Report here. In short, I spent much of the last year defending my rights and the rights of thousands of UCLA students to speak their beliefs. For this, I and a few other students faced large-scale, well-funded, highly-organized harassment and bullying. I was repeatedly ignored by Chancellor Gene Block, I was told to reconsider being involved with Palestinian activism by a high-ranking UCLA administrator, and–surprisingly–I was called a frog face. Ribbit!

In retrospect, I would not do everything the same way if given a second chance, but I do not regret the sacrifices I made. I learned a lot about myself, about my friends, about other graduate students at UCLA, about UCLA’s bureaucracy, and about the law. I made tons of new friends and grew as an advocate for Palestine and Free Speech. As the struggle for liberation and a just peace continues, I hope I continue to become more effective.


Moving Forward and Backward

Today, I and several others found ourselves the victims of another poster campaign on campus (see here and here). As you can see, it’s not new. In fact, you can read more about it here on UCLA Vice Chancellor Kang’s blog. As he mentions, these inflammatory posters violate Regulations Governing Conduct of Non-Affiliates in the Buildings and on the Grounds of the University of California. I’m not sure though if that means UCLA is planning on doing anything about it though. Is this selective enforcement? I can’t say for sure, but it feels like it. As for this round of posters, there was another game-changer that might test this theory:

Cropped shot of one of the posters. 
There were many posters, but as one of the posters depicts the Vice Chancellor himself, I expect the response from UCLA to escalate from the usual campus-wide email. The whole McCarthyist “Red Menace” depiction is just the racist cherry on top of their Hate Group sundae.


Damages and Remedies

Before concerning yourself though with how Jerry Kang is feeling. Let’s take a bird’s eye-view assessing the damage and harm done here. Jerry Kang is a double graduate of Harvard University who has had a long and successful career as a Professor of Law. He has tenure, a Vice Chancellorship, and a consistent salary of around $300,000. When you google his name, it is his research, his blogs, and his websites that show up first. Compare that to the other folks the posters targeted. They are students–mostly students of color–students seeking their first employment, students with less than a hundred dollars to their name. They have no safety net and when you google them, it’s not their own profiles that show up. I can’t even get started on discussing the mental health effects without wanting to write another blog post just about that. Look, I feel bad for him, but this isn’t even apples and oranges.

As for remedies, the administration needs to work on-and this is the operative word here-concrete steps to help its students. I cannot stress this enough. When faced with a multi-million dollar hate machine that funnels money into campaigns to smear students via websites, posters, PR firms, and search engine optimization teams, an administration that is sincerely dedicated to education would not merely send an email. As much as we all want to be civil about this and challenge bad speech with good speech, that strategy has proved to be ineffective here. The point of the posters is to deter future student activists  via guilt-by-association and reputation damage. UCLA has some obvious ways to deal with this. Positively promote these students, give them the stellar attention they deserve. Give them the resources that a multi-billion dollar institution has in order to amplify their voices.  Offer strong letters of recommendation to these students for their fortitude. And frankly, if the administration is not prepared to genuinely defend its students in these kinds of way, they should not waste students’ precious time with meetings.


Looking Ahead

Now, if you ask me now what I expect my third year of graduate school to be like, I would not even try to answer. Being at UCLA is exciting, and so are Palestine solidarity and mathematical research. Ultimately I’ll never be able to expect the unexpected, but I will be able to adapt. And that’s much more useful. 

I woke up today with a long to-do list that I’ve been saving up until I heard back about my results yesterday. These posters may have made the list longer, but like I said, I learned a lot from last year and I am pushing through. My education won’t be stopped. My activism won’t be stopped. I won’t be stopped.