The Maximum Size of Disorder
[ C H R O N I C L E ]
Let’s use this double issue to play with maths, as summer is the ideal time for this fun and useful aspect of the discipline (see here). I’m going to set you a little challenge. It’s a colouring question, that needs no special artistic talent. It is a question of combinatorics and logic. Before I set it, let’s go back in time a little to understand its origins and why we want to do this.
The mathematician Frank Ramsey (1903-1930) was a member of the “club” of famous people who died at 27 years of age, like Jimi Hendrix, Janis Joplin and Jim Morrison. However, this British man is known for the Ramsey theory, which gave rise to powerful mathematical tools; in particular it provided the proof that in Paris there are two people who have the same number of hairs on their head. This amusing demonstration uses the principle of Dirichlet drawers, an elementary example of Ramsey theory.
Given that the maximum number of hairs on a human head is 200,000, people are ordered into drawers according to the number of their hairs: in the first drawer, we find bald people; in the second, people with a single hair on their heads; in the third, people with two hairs, and so on. Once all their hairs have been counted, each Parisian will be placed in one of the 200,001 drawers created. After sorting the first 200,001 Parisians, two configurations are possible: either there are already two Parisians in the same drawer and the result is proven, or there is exactly one Parisian per drawer and in this case, the next Parisian will go into a drawer where there is already someone; there will be two of them with the same number of hairs. The demonstration works whenever you have a town of more than 200,001 inhabitants.
If you are allergic to hair or to Parisians, we can reformulate the results in another way: when you colour in at least 200,002 points with 200,001 colours, there are at least two points of the same colour. Don’t worry, in this colouring game, there are fewer felt-tipped pens.
In the 1920s and 30s, several mathematicians followed in the steps of Ramsey and Issaï Schur and David Hilbert - who came before him; they proved far more serious theorems than counting hairs on the heads of Parisians, but the structure of these theorems was similar. The underlying idea is as follows: when we observe a very large “system”, of any type, we notice that “structures” appear, i.e. parts of the system that are not “disordered”. This version of the statement is far too imprecise to be fair, but it inspired the mathematician Theodore Motzkin to produce the following maxim: “Complete disorder is impossible” - useful as a reply to anyone commenting on the state of your desk.
To be more specific, let us look at an elementary example of Ramsey theory that uses drawing; if you draw a line of nine regularly spaced points, using two colours, you will obviously isolate three regularly spaced points of the same colour. Here the system is the set of points, and the structure that appears is the sequence of three regularly spaced points of the same colour. Let us look at the examples below. In the first line, there are three consecutive blue dots at positions 2, 3 and 4; in the second, there are three red dots 2 spaces apart at positions 2, 4 and 6. You can try with your own pens and you will note that there will always be similar sets of three points as this is a theorem, i.e. a proven statement. Getting to the proof however, is a little more delicate. Normally, you would only have to test the 29 = 512 possible drawings to check that this property is always satisfied.
That wasn’t exactly Dutch mathematician Bartel Leendert Van Waerden’s approach when he found the proof in 1927. His proof is interesting, as it is far more general. He showed that if we set a k number of points (the size of the structure), and a c number of colours, there is a number N (which depends on k and c) so that any drawing of N points with c colours will always have k regularly spaced points of the same colour. In the simple example we gave, k = 3 and c = 2, we find that N = 9 works; we can verify that this is the smallest value for N that works because we can draw eight points so as not to have three regularly spaced points of the same colour (for example, with two reds, two blues, two reds and two blues again). If you want to isolate three points with three colours (k = 3 and c = 3), we can show that you need a minimum of twenty-seven points (N = 27).
When I say we can show this, it is because the value of N is not contained in the Van de Waerden theorem. He established the existence of such an integer without calculating its minimum value - the proof only indicates that N is smaller than a “gigantic” quantity. And, in general, it is not at all easy to obtain, so much so that we still don’t know the value of N for k = 5 and c = 3 for example (although we know it is definitely greater than 2,173). That would have been a nice summer challenge, but a little arduous for the beach perhaps.
In 1978, the Israelo-American mathematicians Hillel Furstenberg and Benjamin Weiss established a multidimensional version of Van der Waerden’s theorem (1). Let us consider a regularly checkered square; we have N 3 N points (the grid intersections) that we will colour using two colours. In its 2-dimensional version, the theorem indicates that there is a size N from which, with any colouring, four points of the same colour forming a square will be found (not necessarily at the edge), such as those sized 2, 3 and 4 (Fig. 2) (no conditions are imposed on the colour of the points marked “?”).
In the figure below (Fig. 3), look for a 5-squared shape with the “same coloured corners”. Unless I’m wrong, there are none. This means that the size (unknown) from which one is sure to find this structure is greater than 5. I do not know the smallest N that would impose the presence of this structure. So, I offer you the following challenge: using two different coloured crayons, colour in the largest square grid possible without having four points of the same colour forming a square. Take a picture of your best result and send it to me at courrier@larecherche.fr. The winner will be drawn from the largest entries and will win a year’s subscription to the magazine.
(1) The very long and difficult article (H. Furstenberg et B. Weiss, J. Analyse Math., 34, 61, 1978) can be read here.
> AUTHOR
Roger Mansuy
Mathematician
Roger Mansuy teaches at Louis-Grand Lycée in Paris, and is a member of the French Committee for Maths Teaching (CFEM).
