Poncelet’s porism: the Socratic dialogue

In the 1994 proceedings of the Mathematical Association of America, there is a truly wonderful article by Jonathan King. Entitled Three Problems in Search of a Measure, it provides three very different examples of problems that can be solved using elementary methods by considering the notion of a measure. The appeal of the article stems largely from the fact that the proofs are so clean and elegant, motivating measures and ergodic theory without having to rely on any advanced theorems.

One of the problems is the Arctic circle problem, which I first encountered in Geoff Smith’s Geometry Thoughts for the Day on 2011-06-11:

This problem is quite well known, and is related to something that has been discussed recently. A fishing hole in the ice forms a perfect circle of diameter d. A rich supply of arbitrarily thin planks of all sorts of length and widths is available. The hole must be covered with planks for Health ‘n Safety. Clearly this can be done with a finite collection of planks of total width d by placing them in parallel fashion.

Is it possible to cover the hole by using a finite collection of planks of total width less than d by using some kind of cunning criss-cross arrangement of the planks?

I’ll leave you to contemplate this; it’s very satisfying to solve.

Poncelet’s porism

Suppose we have an n-gon with both an incircle and a circumcircle. Poncelet’s porism is the theorem that we can then find infinitely many n-gons sharing the same incircle and circumcircle, by starting from any point on the circumcircle. If you prefer, Wolfram MathWorld has a very instructive animation of the statement of the porism:

The usual ‘proof from the book’ of Poncelet’s porism involves the theory of elliptic curves. By comparison, the concepts in King’s proof are sufficiently elementary that I claim the proof could be understood by the Ancient Greeks. To emphasise this point, I shall present a slight reworking of King’s proof as a Socratic dialogue between Archimedes (who has hypothetically discovered the proof) and Eratosthenes. I have chosen Eratosthenes over the more usual candidates of:

  • Meno’s slave (if you’re Plato);
  • A Magdalene undegraduate reading Land Economy through the bottom of a Pimm’s glass (if you’re Piers Bursill-Hall);
  • Tim Gowers’s son (if you’re Tim Gowers);

on the basis that I wanted a contemporary of Archimedes who would be able to understand the subtleties of the proof.

dialogue

Quod erat demonstrandum. By the way, the result can be generalised to ellipses instead of circles by applying a projective transformation, although of course this would be beyond Ancient Greek mathematics so I decided against including it in the Socratic dialogue.

Posted in Uncategorized | 1 Comment

Cipher 65: Melencolia

Firstly, congratulations to the British EGMO team (Olivia, Kasia, Katya and Eloise) for their impressive performance, coming eighth out of 29 competing teams. Apparently the competition was held in the same five-star hotel in Antalya enjoyed by a previous Balkan Mathematical Olympiad, a humorous report of which was written by Gabriel Gendler.

Unfortunately, I have completely run out of inspiration for ciphers. However, I would like to instead mention a very beautiful engraving by the German Renaissance polymath Albrecht Dürer, entitled Melencolia I:

Albrecht Dürer's Melencolia I -- click to enlarge.

Albrecht Dürer’s Melencolia I — click to enlarge.

One of the most interesting features of the engraving is the polyhedron on the left of the picture. Indeed, it is referred to as Dürer’s solid, and its skeleton is the Dürer graph (one of many interesting generalised Petersen graphs).

I happened to visit the Serpentine Gallery whilst in Kensington, London on the 8th April (for reasons which would have been revealed in the private cipher solvers’ area, had I actually made a cipher for today, which of course I didn’t). There was another one of Dürer’s famous engravings, namely Saint Jerome in his Study, which was unarguably my favourite art work in the gallery.

Posted in Ciphers | Leave a comment

Lifting the exponent

I overheard mention of a particular problem on a recent British Mathematical Olympiad, namely the following:

A number written in base 10 is a string of 3^2013 digit 3s. No other digit appears. Find the highest power of 3 which divides this number.

Personally, I bemoan such problems that are trivialised by the knowledge of advanced theorems, as it enables competitors to gain an unfair advantage by rote-learning many results rather than demonstrating creative mathematical thought. In this case, the question is trivialised by a rather elegant but little-known lemma called lifting the exponent.

So, what does the lemma state? Firstly, we establish the following definition:

Definition: the p-adic valuation v_p(n) of an integer n to be the highest power of p which divides n. For example, v_2(40) = 3, since 2^3 divides 40 but 2^4 does not.

Then the lemma is as follows:

Theorem (lifting the exponent): Let p be an odd prime, and a and b integers such that neither a nor b is divisible by p, but p divides their difference ab. Then v_p(a^n − b^n) = v_p(ab) + v_p(n).

Why is this true? The idea is that we factorise a^n − b^n like so, where n = k p^m and k is not divisible by p:

lte-factorisation

The factors in the final factorisation are highlighted. It is clear that it is sufficient to prove that the yellow factor is coprime to p (which is easy, since all of the terms are congruent modulo p and are non-zero) and each of the blue factors are divisible by p (easy for the same reason) but not by p², as we shall prove:

  • If a and b are congruent modulo p², this is again trivial for the same reason as before.
  • Otherwise, we have to actually rely on the property that p is odd (if p = 2, we need a and b to be congruent modulo 4 rather than modulo 2). We let x and y be equal to a^p^i and b^p^i, respectively, for the obvious value of i, such that the factor is of the form:

Γ = x^(p-1) + x^(p-2) y + x^(p-3) y^2 + … + y^(p-1)

Then we set y = x + lp for some integer l (which we can do, since y and x are clearly congruent modulo p). Expand the factor Γ to produce a sum of binomial expansions; we can ignore all terms of order p² and higher since we’re only interested in the residue modulo p². This gives the following expression:

px^{p-1} + \frac{1}{2}p^2(p-1) x^{p-1}

The rightmost term vanishes, leaving something that is clearly not divisible by p². Consequently, the proof is complete and the result follows immediately.

Zsigmondy’s theorem

Another useful fact concerning a^n − b^n is this: except in a few exceptional cases, it has a new prime factor p that does not occur in any of ab, a² − b², a³ − b³, …, a^(n−1) − b^(n−1). The exceptions to the rule are the following:

  • a = 2, b = 1, n = 6: we have 2^6 − 1^6 = 63, whose prime factors are 3 and 7, which occur in 2^2 − 1^2 and 2^3 − 1^3, respectively.
  • a + b is a power of 2, and n = 2: then a² − b² = (a + b)(ab). The first factor is a power of 2 (so no new primes there), and the second factor is itself the previous term in the sequence (so, by definition, no new primes there either).

A related statement about Fibonacci numbers (where the integers a and b are replaced with irrational algebraic integers, and an extra factor of √5 slips in) is known as Carmichael’s theorem. Zsigmondy’s theorem and Carmichael’s theorem can be mutually generalised to other Lucas sequences.

Posted in Uncategorized | Leave a comment

Cipher 64: Sic transit gloria Monday

Firstly, I have a few late items of news to discuss:

  • Maria Holdcroft (former UK EGMO team member) and I survived our skydive on Wednesday, and have so far raised in excess of £886.77 (a large portion of which is from cp4space readers!) for the Schistosomiasis Control Initiative. A video of the freefall component of my jump is available; you may also want to visit the Facebook page. I’ll be writing the cheque to the SCI imminently, so if you want to support the cause (saving children in Africa from parasitic infections) then please e-mail me as soon as possible. If you happen to enjoy watching people jump out of aeroplanes, then you may want to watch this video of my friend Mehr, who partially inspired me.
  • Today we marked the First Selection Test to decide the preliminary UK IMO squad who will be attending further training sessions in Oundle. The team for the Balkan Mathematical Olympiad will also be announced shortly on Joseph Myers’ website, but until then I’m sworn to secrecy. Congratulations, nonetheless, to our newly-appointed squad of Joe Benton, Gabriel Gendler, Frank Han, Liam Hughes, Freddie Illingworth, Andrew Kenyon-Roberts, Warren Li, Neel Nanda and Harvey Yau for their excellent performance in the selection tests, and good luck in South Africa.
  • Also, I would like to draw attention to the final of University Challenge between Trinity College, Cambridge, and Somerville College, Oxford. As with the results of the IMO selection tests, I shall not reveal the scores…

Anyway, I suppose I should provide a cipher since we are rapidly approaching a Tuesday in the middle of Season III.

magicknight

The password is eight letters long.

Posted in Uncategorized | Leave a comment

Cayley-Menger determinants

Niccolo Fontana Tartaglia, whom you may recognise from having discovered Cardano’s solution to the general cubic equation, also discovered a generalisation of Heron’s formula to compute the volume of a tetrahedron:

tartaglia

As you may expect, this can be generalised to compute the volume of any n-simplex (n = 2 reducing to Heron’s formula for the area of a triangle). I wondered how one would go about proving this identity, and then realised it can be accomplished by elementary facts about determinants. Firstly, it is easy to show the following result:

  • The volume of an n-simplex S with vertices at {0, e_1, …, e_n} is equal to 1/n!, where e_i is the ith standard basis vector.

This can be proved, for instance, by subdividing a unit cube into n! simplices, each of which is congruent to S. Now, we know that the determinant of a matrix gives the volume scale factor of the associated linear transformation, enabling us to generalise the previous result:

  • The volume of an n-simplex T with vertices at {0, a_1, …, a_n} is equal to V = det(a_1, …, a_n)/n! where we form the matrix by writing down the coordinates of a_i in the ith column.

Recall that determinants are multiplicative, so we can multiply this by its transpose to get the following equation (which is satisfyingly coordinate-independent):

  • V² = (det R)/((n!)²), where the entries of R are given by Rij = a_i · a_j.

And then by scaling, we obtain:

  • V² = (det Q)/((−2)^n (n!)²), where the entries of Q are given by Qij = −2 a_i · a_j.

This in turn leads to the following:

  • V² = (det P)/((−2)^(n+1) (n!)²), where P (an n + 2 by n + 2 matrix) is obtained by taking the matrix Q and appending two useless ’1′s (whose only affect is to negate the determinant) to the diagonal like so:

matrix-P

Now, we want to apply determinant-preserving elementary row operations to convert the Cayley-Menger matrix M given at the beginning of the article into the matrix P. Perform the following operations in succession:

  • Subtract the 1st row from the 2nd, 3rd, …, (n+1)th rows;
  • Subtract appropriate multiples of the final column from the other columns so that the first row is (0, 0, 0, …, 0, 1);
  • Subtract the 1st column from the 2nd, 3rd, …, (n+1)th columns;
  • Subtract appropriate multiples of the final row from the other rows so that the first column is (0, 0, 0, …, 0, 1).

Then it is easy to verify that the result is equal to P, by expanding each entry in terms of dot products.

Applications of the Cayley-Menger determinant

  • The Cayley-Menger determinant is beautiful in its own right, expressing the squared volume of a tetrahedron solely as a polynomial in the squared edge lengths. Similar results hold for other polyhedra, which was a necessary component in establishing the Bellows Conjecture.
  • If we form the Cayley-Menger determinant of five nearby points in general linear position in three-dimensional space, it will allow one to deduce whether the local Gaussian curvature is positive, zero or negative. This is described in more detail here.
  • Several other theorems in distance geometry follow as special cases, such as Stewart’s theorem.
  • The distances between atoms are determined by the bond lengths, so the shapes of certain molecules can be predicted using distance geometry.
Posted in Uncategorized | 1 Comment

Most difficult chess problem

Neil Bickford has exhaustively searched the space of 5 × 4 sliding-block puzzles* to determine the one with the longest minimal solution. The unique result, which requires a whopping 235 moves, happens to be Bob Henderson’s Gauntlet puzzle:

*subject to the constraint that the objective is to move the red monomino to the upper-left corner.

Despite having far fewer positions than a Rubik’s cube, the graph of this sliding-block puzzle has a much longer diameter. Tomas Rokicki proved that the Rubik’s cube has a diameter of 20 in the half-turn metric, and there’s an upper bound of 28 for its diameter in the more natural quarter-turn metric. It has also recently been proved that the Rubik’s cube Cayley graph (which is vertex- and edge-transitive) is also Hamiltonian; it is conjectured that every Cayley graph is Hamiltonian.

Now, chess problems are harder than sliding-block puzzles, since you have to account for all possible moves that your opponent could make. For instance, ‘mate in 3′ problems are quite difficult due to the plethora of possible combinations for which one must account. This is reflected in the fact that (generalised) chess is EXPTIME-complete, whereas sliding-block puzzles are merely PSPACE-complete.

If mate-in-3 problems can be difficult, then surely the following mate-in-549 problem must be completely intractable? Even the best grandmasters can see no logic behind the majority of the moves, since the depth of the problem is beyond human comprehension. Indeed, it would probably please even Doron Zeilberger, who considers Fermat’s Last Theorem to be trivial due to the existence of a human proof.

White to play and mate in 549...

White to play and mate in 549…

This configuration was discovered by programmers at Lomonosov University, Moscow, who exhaustively catalogued all reasonable seven-piece chess endgames. White can force a win, eventually, but Black can prolong defeat for as many as 549 moves. Interestingly, the optimal sequence of moves for White involves promoting the pawn to a knight, rather than to a queen.

If we’re allowed an infinite board, then it’s possible to have mate-in-ω games and beyond, where White eventually wins, but Black can delay White by an arbitrarily long time. It is also conceivable that there is an algorithm for converting a statement in Peano arithmetic to a chess configuration in which White can force a checkmate if and only if the statement is true. (Both of these rely on the fact that rooks, bishops and queens can move by any integer in a single move.)

Posted in Chess | 23 Comments

Cipher 62: Also untitled

By the way, we’ve raised £463.00 so far for the Schistosomiasis Control Initiative (see this post for an explanation). This week’s cipher uses a couple of relatively simple ideas, although I could imagine it being difficult to cryptanalyse.

DKGOQXIWSASPYKOWEEPLELTLELFSKTPITLJFCLXSANZRYYNTAAJDQC

Good luck.

Posted in Ciphers | Leave a comment