A gem of elementary algebra

 Many years ago my former doctoral adviser Peter Neumann introduced me to an intriguing problem on number sequences. I believe he had seen it somewhere in a notorious article by John Hammersley: "On the enfeeblement of mathematical skills by ‘Modern Mathematics’ and by similar soft intellectual trash in schools and universities". Wow! That's a provocative title if ever there was one! It was published in the Bulletin of the Institute of Mathematics and its Applications, Volume 4 (1968), pages 66–85. It's a serious article and well worth reading. Hammersley mentioned this problem as an example of the kind he thought educators would find useful to introduce as part of a course designed to teach mathematical problem-solving. I'm describing it in this post because it is indeed a pretty problem which should be better known and Hammersley's more detailed follow-up article ("Sequences of Absolute Differences", SIAM Review, volume 11, pages 73–74) is (for me) hidden behind a paywall. See also this Wikipedia article for the origin of the problem.

The problem is about integer sequences and a certain operation that turns one sequence into another. Here's an absolutely trivial example with the sequence 2 4 1. We form another sequence by taking the differences of successive terms (the first term succeeding the last term), always taking the positive value. Thus 2 4 1 transforms in 2 3 1 (4-2=1, 4-1=3, and 2-1=1). Then we apply this same process again and again. We get

1 2 1, 1 1 2, 0 1 1, 1 0 1, 1 1 0, 0 1 1, 1 0 1, 1 1 0. Now we are in an infinite loop 

1 1 0, 0 1 1, 1 0 1, 1 1 0. 

It seems somewhat unnatural to always take the positive value of the difference but we'll see the reason soon. What is clear is that, no matter which sequence we start with, and no matter how long it is, the process will eventually settle into a loop (because in each interim sequence the maximum term cannot get larger as we go from one sequence to the next).

Let's try another sequence, this time of length 4, say 3 1 4 1. The sequence of sequences is now

3 1 4 1, 2 3 3 2, 1 0 1 0, 1 1 1 1, 0 0 0 0

This time we have actually reached a stationary point. Here's another length 4 example:

2 1 4 3 , 1 3 1 1, 2 2 0 0, 0 2 0 2, 2 2 2 2, 0 0 0 0

Another stationary point. One more length 4 example:

5 1 2 4, 4 1 2 1, 3 1 1 3, 2 0 2 0, 2 2 2 2 , 0 0 0 0.

Now a length 5 example

2 7 1 8 2,  5 6 7 6 0, 1 1 1 6 5, 0 0 5 1 4,  0 5 4 3 4, 5 1 1 1 4, 4 0 0 3 1, 4 0 3 2 3

4 3 1 1 1, 1 2 0 0 3, 1 2 0 3 2, 1 2 3 1 1, 1 1 2 0 0, 0 1 2 0 1, 1 2 2 1 0, 1 0 1 1 1

1 1 0 0 1, 0 1 0 1 0, 1 1 1 1 0, 0 0 0 1 1, 0 0 1 0 1, 0 1 1 1 0, 1 0 0 1 0,

and we have reached a cycle of length 7.

After a lot of similar exploration it turns out that cycles can be quite long and, while there is a lot of work on what they can be, there doesn't seem to be any significant interest in this exploration. 

Except for just one amazing fact: in lengths 2, 4, 8, and any power of 2, the only cycle is the singleton cycle of all zeros. In the rest of this post I'll explain the reason for this.

From now on we'll be considering sequences of length n where n=2^m is a power of 2. To begin with we'll regard the components of the sequences to be reduced modulo 2 - elements of the field of 2 elements. In this field addition and subtraction are the same so the basic transformation T (which is linear) takes a vector 

v = (v₁, v₂, ..., v_n) 

into 

T(v) = (v₁+v₂, v₂+v₃, ..., v_n-1+v_n, v_n+v₁) = v + S(v) where

S(v₁,v₂...,v_n-1, v_n) = (v₂,v₃, ..., v_n,v₁)

and S is the (linear) shift operator. Thus, with I denoting the identity operator, we have

T(v) = (I + S)(v)

Then, because I and S commute and we are working modulo 2, 

Then T²(v) = (I + S)²(v) = (I² + 2IS + S²) = (I + S²)(v). Similarly

T^2k(v) = (I + S)^2k(v) = (I+ S^2k)(v), for all k.

In particular, when k=m, and n=2^m, Sⁿ=I

showing that Tⁿ(v) = (I + I)(v) = 0.

Returning now to regarding each vector v as a vector of integers, this shows that, after n iterations of the T operator, we have a a vector with all even components. But then after a further n iterations of T we get a vector with all components being multiples of 4. And so on. So, since all the components are bounded, we eventually reach the all 0s vector.

Geometry and AI assistants

 Recently, in a moment of idleness, I fired up ChatGPT and asked "Will you show me some interesting geometric theorems?". It produced some theorems I already knew but two were new to me.

The first was Viviani's theorem. Choose any point P within an equilateral triangle and drop perpendiculars to each side of the triangle. Then the sum of the perpendicular distances is independent of the point chosen.

I didn't know whether this was a very deep theorem (on a par with Morley's miracle theorem for example) or not. However a few minutes of elementary calculations showed me it was easy to prove and I announced it to my daughter Laura when I saw her next. Laura is not a mathematician but she is certainly clever and it was disconcerting that she thought for a only moment before saying "Oh yes, I see". Humiliatingly, her proof was even easier than mine. The triangle is the decomposition of 3 triangles, each with a vertex at P and their combined areas are the sum (base*height)/2. The bases are constant and the sum of the heights is therefore a constant.

Anyway, never let a good proof go to waste. By a similar argument we can replace the equilateral triangle by any convex polygon with equal side lengths. There are other more complicated generalisations.

The second theorem that ChatGPT told me about was Miquel's theorem and not quite so transparent. Let points A, B, C define a triangle (any triangle) and choose any points on the sides: D on side BC, E on side CA, F on side AB (they don't even have to be interior to the side). Now draw the circumcircles of the triples AFE, BDF, CED. The conclusion, Miquel's 3 line theorem, is that these circles pass through a common point M.

This seemed extraordinary given the freedom to choose the 6 points. However, when one knows the proof (an angle-chasing argument) it loses its mystery. 

The proof seems to assume D, E, F to be internal points on each triangle side but a more sophisticated approach can remove this assumption.

It turns out that there are a number of connected results but one of them is also called Miquel's 4 line theorem. One begins with a complete quadrangle - a quadrilateral on 4 points A, B, C, D - where opposite sides are extended to meet at two further points E, F.

In this figure of 4 points and 6 lines there are 4 triangles AED, ABF, BEC, DCF. Miquel's 4 line theorem is that the circumcircles of these 4 triangles have a common point M. Again, a seemingly extraordinary result. But, again, there is an angle-chasing argument that demystifies it although the argument is more complex because the figure is more cluttered.

I wondered whether these two theorems were related; the most likely possibility was that the 3 line theorem was a special case of the 4 line theorem. However I couldn't make this work and so I turned once more to ChatGPT and asked it for a derivation of the 3 line theorem from the 4 line theorem. Its response was immediate but, as I soon checked, it had errors. I had seen repeated failures before and had previously found that Claude was less dogmatic. However Claude, while initially optimistic, also failed. However Claude was more humble in admitting its shortcomings and, at one point, while giving an argument observing for itself that it was flawed.

A few days later I did find a connection between the 3 line and 4 line versions. To my surprise, rather than deriving the 3 line version from the 4 line version, I found that two applications of the 3 line version gave rise to the 4 line version. Consider the 3 line version in which the points D, E, F are collinear:

Applying the 3 line theorem directly the conclusion is that the circumcircles of triangles AFE, BDF, and CED have a common point P. But these triangles are three out of the four triangles in the quadrangle shown. Similarly, therefore, the circumcircle of the remaining triangle ABC must pass through this common point also.

In retrospect I believe that the "reasoning" behind ChatGPT's and Claude's failures was syntactic rather than semantic; they put together plausible chains of statements which were plausible because they had the right form. Not surprising in view of the fact that Large Language Models are trained on textual samples where only syntax is present. However my interactions with them were not wasted - they kept me engaged and led me to a conclusion I might not otherwise have drawn.