It’s now New Year’s Eve, which is why the cp4space banner has changed again.
As is usual for this time of year, there is a joint Anglo-Hungarian IMO training camp in Tata, Hungary. I’ve mentioned it before at the end of 2012, but perhaps it is worth re-iterating that this is where Complex Projective 4-Space was originally popularised. I shall start by discussing a problem that appeared on the selection test at the end of this camp two years ago, which recently resurfaced on an online forum.
Given any arrangement of white and black tokens along the circumference of a circle, we’re allowed the following operations- take out a white token and change the colour of both its neighbours, or put in a white token and change the colour of both its neighbours. Is it possible to go from a configuration with just two tokens, both white, to a configuration with two tokens, both black?
You may want to attempt this problem for yourself before reading further. One of the members of the forum posted graphs of what appear to be three equivalence classes of ‘necklaces’ (we shall later prove whether or not this is actually the case), where edges represent elementary operations. Here is one of the equivalence classes:
I had seen an ‘official’ solution to this problem, but as is usual for official solutions, it was not particularly insightful. By contrast, Gabriel Gendler devised a much more interesting interpretation, which, whilst essentially equivalent to the official solution, offers far more insight and generalises beautifully.
The idea is to ‘break’ the necklace at an arbitrary prespecified point, so that the beads form a linear string. For example, we can break the following necklace at the point specified by the arrow to give a linear string:
This string will be represented as WWBWBB. Cutting the same necklace at a different point would give a different string, such as WBWBBW, but we will consider this caveat later. For now, we will focus on the simpler problem where the string is linear, rather than cyclic. This is the famous word problem, which is undecidable in general but easy in this particular case. We can summarise the elementary operations as relations:
BWB = WW
- BWW = WB
- WWB = BW
- WWW = BB
If we allow the elements to have inverses, then this becomes a group presentation. Gabriel noticed that in particular, this is a presentation for the permutation group S3, where B = (1 2) is a transposition and W = (1 2 3) is a 3-cycle. We can convert between words only if* they represent the same group element in S3.
* Again, if we allow inverses, things become much neater and the converse also holds. Otherwise, it is necessary to consider small cases separately.
However, we now need to remember that in the original problem, the string is cyclic. Hence, where x and y are arbitrary strings, xy and yx represent the same necklace cut at different places. Consequently, as well as the local operations encoded in the group presentation, we also need to consider the global operation of ‘remove a string from the left and append it to the right’.
Gabriel remarked that if xy = e, then yx = e (where e is the identity) and therefore it is impossible to convert an identity necklace into a non-identity necklace or vice-versa, solving the original problem. However, it doesn’t solve the problem of whether we can convert between BBB and WWWW, since these are both non-identity necklaces. However, thinking for a moment results in the following observation.
yx = y xy y’
Here y’ is the inverse of y. So, we can think of moving the string y from the left to the right as conjugating by y. Indeed, this operation of rotating the beads on the necklace is precisely the same operation as conjugation: no more; no less. This leads to this rather neat conclusion:
We can convert between two necklaces if and only if they are in the same conjugacy class.
Gabriel attempted to construct similar problems based on other groups. I mentioned how the dihedral groups have relatively small group presentations, and this is the smallest non-trivial example. Eventually, I suggested the following problem:
We have three types of bead (red, gold and forest green, to make this problem nice and festive!), and are allowed the following operations:
Insertion or deletion of five consecutive red beads;
- Insertion or deletion of three consecutive gold beads;
- Insertion or deletion of two consecutive green beads;
- Replacing a red-gold (in clockwise order!) pair with a green bead, or vice-versa.
Then, a nice problem is to determine necessary and sufficient conditions for it to be possible to convert a necklace of m red beads into a necklace of n red beads. Also, you may want to work out which group underlies this problem (the answer is nice and simple!), and how many conjugacy classes it possesses; post your solutions in the ‘comments’ section at the bottom of this post.
Problems, books and quotations
Anyway, Gabriel’s solution is what Paul Erdős would call a proof from the book, meaning that it is clearly the right way to think about the problem. I particularly like this problem from the Advanced Mentoring Scheme, which has a horribly ugly case-bash official solution as well as a beautiful proof from the book. See if you can find the latter (again, post your solutions as comments on this article):
A class of students takes eight exams of which each student passes exactly four. For each pair of students, there are precisely two exams passed by the first and not the second, and precisely two passed by the second and not the first. What is the maximum possible size of the class?
Completely coincidentally, whilst checking my e-mails to find the exact verbatim statement of the AMS problem, I have just received one from Gabriel entitled ‘positive consequence of cp4space’ explaining how he used the Cayley-Bacharach theorem to solve question G6 on the 2006 IMO shortlist. Again, this is shorter and more elegant than the official solutions, although I wouldn’t go as far as saying that this was a proof from the book (a term generally associated with using more advanced theory than is necessary to understand the problem). Indeed, Erdős believed that God has a book containing the most elegant proof of each theorem.
More generally, Erdős famously used rather colourful terminology to refer to various concepts. They are mentioned in this delightful comic by Mike. Nevertheless, I suppose that my favourite amusing quotation by a great mathematician is this one of Hilbert’s:
A mathematician should have both a wife and a concubine. That way your wife thinks you are with the concubine, the concubine thinks you are with the wife, and finally you have time to do some maths.
(Depending on the gender and sexuality of the mathematician, you may need to replace ‘wife’ with ‘husband’. I think that concubine is technically gender-neutral.)
More mathematical quotations can be found on MathOverflow.