Eigenvalues of the Kneser graph

On Tuesday Ehud Friedgut gave a beautiful talk in the Bristol Combinatorics Seminar, titled ‘The most complicated proof ever of Mantel’s theorem, and other applications of the representation theory of the symmetric group’, based on joint work with Yuval Filmus, Nathan Lindzey and Yuval Wigderson. As the title promised, he used the representation theory of the symmetric group to prove Mantel’s Theorem, that if a graph on vertices has more edges than the complete bipartite graph with bipartition into two parts of size then it contains a triangle. He illustrated the method by instead proving the Erdős–Ko–Rado Theorem, that the maximum size of a family of -subsets of such that any two members of the family have a non-trivial intersection is . The purpose of this post is to outline the new proof (as I understand it from Ehud’s talk) of this result, dropping in my own proof of one of the lemmas he used. At the end I’ll record a possible generalization/variation I raised at the end of the talk. Let me emphasise that — apart from the minor proof of the lemma, which in any case uses results of James — no originality is claimed for anything in this post.

A graph for the Erdős–Ko–Rado Theorem

The graph we need to prove the Erdős–Ko–Rado Theorem is the Kneser graph, having as its vertices the -subsets of . Two subsets and are connected by an edge if and only if . The Erdős–Ko–Rado Theorem is then the claim that the maximum size of an independent set in is . As we shall see below, this follows from the Hoffman bound, that an independent set in a -regular graph on vertices with adjacent matrix and least eigenvalue has size at most . (Note that since the sum of the eigenvalues is the trace of the adjacency matrix, namely , and the largest eigenvalue is the degree , the least eigenvalue is certainly negative.)

Representations

To find the eigenvalues of , Ehud and his coauthors use the representation theory of the symmetric group. Let be the permutation module of acting on the -subsets of . It is well known that has character

Since this character is multiplicity-free, there is a unique direct sum decomposition of into Specht modules,

The adjacent matrix acts as a linear map on that commutes with the -action. Therefore, by Schur’s Lemma, for each with there is a scalar such that acts on as multiplication by . Thus the are the eigenvalues (possibly with repetition, but this turns out not to be the case) of .

Lemma. The adjacency matrix acts on by scalar multiplication by .

Proof. It follows from the theory in Chapter 17 of James’ Springer lecture notes on the symmetric groups that has a filtration

such that and for . The submodule is spanned by certain ‘partially symmetrized’ polytabloids. Rather than introduce this notation, which is a bit awkward for a blog post, let me instead suppose that acts on the set where . Let be a fixed -subset of . Then is a cyclic -module generated (using right modules) by where

There is a ‘raising map’ which — viewing as a submodule of the permutation module of acting on -subsets — is defined on the generator by

Applying the adjacency matrix sends an -subset to all those -subsets that it does not meet. Hence if we first apply then to then, in order to get a scalar multiple of , we must pick an -subset not meeting that contains , i.e. an -subset of the form

where is an -subset of . Since , there are possible choices. Each comes with sign .

End of proof

The lemma implies that is the least eigenvalue of . Putting this into Hoffman’s bound and using that the graph is regular of degree , since this is the number of -subsets of not meeting , we get that the maximum size of an independent set is at most

which is just a shade more than . Thus we (or rather Ehud and his coauthors) have proved the Erdős–Ko–Rado Theorem for sufficiently large. Ehud mentioned that it was legitimate to apply the Hoffman bound to a scaled adjacency matrix, and by choosing a clever scaling, one could get the theorem on the nose. He then went on to outline how the method applies to Mantel’s Theorem: the relevant representation is, in the usual notation, ; note one may interpret an -tabloid as an ordered pair encoding the path of length 3 with edges and . There is a proof of Mantel’s Theorem by double counting using these paths: as Ehud remarked (quoting, if I heard him right, Kalai) ‘It’s very hard not to prove Mantel’s Theorem’.

Possible variations

I’ll end with two possible avenues for generalization, both motivated by the classification of multiplicity-free permutation characters of symmetric groups. My paper built on work of Saxl and was published at about the same time as parallel work of Godsil and Meagher.

Foulkes module

The symmetric group acts on the set of set partitions of into sets each of size . The corresponding permutation character is multiplicity free: it has the attractive decomposition , where is the partition obtained from by doubling the length of each path. Moreover, my collaborator Rowena Paget has given an explicit Specht filtration of the corresponding permutation module, analogous to the filtration used above of . So everything is in place to prove a version of the Erdős–Ko–Rado Theorem for perfect matchings.

Finite general linear groups

There is a remarkably close connection between the representations of and the unipotent representations of the finite general linear group , which perhaps will, one day, be explained by defining the symmetric group as a group of automorphisms of a vector space over the field with one element. Coming down to earth, the analogue of the permutation module of acting on -subsets is the permutation module of acting on -subspaces of . This decomposes as a direct sum of irreducible submodules exactly as in above, replacing the Specht modules with their -analogues. So once again the decomposition is multiplicity-free. This suggests there might be a linear analogue of the Erdős–Ko–Rado Theorem in which we aim to maximize the size of a family of subspaces of such that any two subspaces have at least a -dimensional intersection.

A Putnam problem

The second suggested generalization might tie in with another project I’ve worked on but neglected to write up beyond a blog post: to prove the -analogue of the spectral results on the Kneser graph motivated by Problem A2 in the 2018 Putnam.

Commuting group actions

In Schur–Weyl duality one has commuting actions of two algebras and on a vector space such that each is the other’s centralizer. That is and . In particular the actions of and on commute. Using a left-action for and a right-action for , this says that

for all , and , a fact one would surely expect from the notation. The purpose of this post is to record a lemma about commuting group actions that arose in this context.

Let and be finite groups with acting on the left on and acting on the right on , such the actions commute. For a simple example where and may be non-abelian, fix a group and take . Then, for each , we have

by the associativity of group multiplication. The slogan ‘action on places commutes with action on values’ gives another family of examples, typified by with acting on the left on by position permutation, and acting on the right, diagonally on each of the factors, by permuting values. For instance, if and then one joint orbit is

The orbit has size so we expect the stabiliser of points in the orbit to have order ; a little thought shows that the stabiliser of is

(Here group elements are tagged by the group they live in.) Note the ‘diagonally embedded’ element : even though we are working in , it is not the case that the stabiliser factors as .

Since there is no established notation for the joint stabiliser in a simultaneous left- and right- action (in fact such a notation would probably just be a standing invitation to commit the diagonal fallacy), I’m going to switch to two commuting faithful right-actions, thought of as a right action of the Cartesian product , in which, by definition, the two factors commute. Since letters will make it clear which group contains each element, I’ll write rather than the formally correct .

Proposition.

Let and be finite groups. Suppose that acts transitively on a set . Fix .

1. The orbits of on are blocks for the action of .
2. Every point in the -orbit of has the same -stabiliser.
3. We have where is the subgroup of those fixing setwise the orbit . Moreover is transitive on if and only both these groups are .
4. There is an isomorphism of right -modules .
5. There are isomorphisms of right -modules

where we use (3) to regard as a -module in the second line and as a -module in the third line.

Proof.

1. More generally, if is a normal subgroup of a permutation group then the orbits of are blocks for the action of , and for the action of any subgroup of .
2. Points in the same orbit have conjugate stabilisers, but here the conjugation action is trivial. Or, to see it very concretely, suppose that . Then . This shows that and by symmetry equality holds.
3. The left-hand side is the set of cosets such that for some . The right-hand side is the set of cosets such that for some . These are equivalent conditions: take and use that the actions commute. Finally, identifying with the coset spacewe see that is transitive if and only if . Since is a normal subgroup of , we may switch the order to get , as required.
4. This is very basic. A nice proof uses the characterisation of induced modules that if and only if has a submodule isomorphic to and . In this case we take to to be the right -module .
5. The first isomorphism follows as in (4) using that acts transitively on . The second follows from the third by (3). Finally the third isomorphism can be proved similarly using the characterisation of induced modules.

Note that each part has a dual result swapping and . Since there is a reasonable notation for bimodule induction, using, as above, uparrows on the right, and writing for induction on the left, we can state the following corollary with left- and right-actions.

Corollary.

Let and be finite groups with acting on the left on and acting on the right on , such the actions commute. Then is a left – and right -bimodule and, given any we have

Proof.

This is immediate from (5) in the proposition and its dual version.

It is interesting to note that if, as in the example below, is transitive, then the effect of the left induction functor in the isomorphism in the second line is simply to turn a right-module into a bimodule, without changing its dimension or its right-module structure in any way.

Example: permuting matchings.

To finish, here is one of a family of interesting examples that come from taking two wreath products whose top groups are equal (as abstract groups) but whose base groups are different. Let

The groups and act on the set of four edge matchings between the parts and that respect the blocks , , , shown by the rooted trees in the graph below. The matching shown by black lines is .

It is clear that the actions of and commute. Moreover, it is an easy exercise to show that and both and act regularly. We have

and so . This is shown graphically below.

Similarly . On the other hand, the permutation cannot be undone by a permutation in . In fact, switching to right-actions for both groups, as in the proposition, we have

Note that, as predicted by the dual version of (3) in the lemma, since is transitive, the stabiliser meets every coset of and .

Scrapbook on plethysms

I’m visiting OIST in Okinawa, Japan for 6 weeks, in which I plan to work on some of the problems in the (over)-extended research summary I wrote for the Oberwolfach meeting in September. The purpose of this post is to collect some bits and pieces maybe relevant to these problems or that come in my reading.

I was briefly tempted to title this post ‘tropical plethysms’, but then it occurred to me that perhaps the idea was perhaps not completely absurd: as a start, is there such a thing as a tropical symmetric function?

A generalized deflations recurrence

For this post, let us say that a skew partition of is a horizontal -border strip if there is a border-strip tableau of shape comprised of disjoint -hooks, such that these hooks can be removed working right-to-left in the Young diagram. It is an exercise (see for instance the introduction to my paper on the plethystic Murnaghan–Nakayama rule) to show that at most one such exists. We define the -sign of the skew partition, denoted , to be if is not a horizontal -border strip, and otherwise to be where is the sum of leg lengths in . Thus a skew partition is -decomposable if and only if it is a horizontal strip in the usual sense of Young’s rule, a skew partition of is -decomposable if and only if it is an -hook (and then its -sign is the normal sign), and

as shown by the tableau below:

Proposition 5.1 in this joint paper with Anton Evseev and Rowena Paget, restated in the language of symmetric functions is the following recurrence for the plethysm multiplicities relevant to Foulkes’ Conjecture:

Our proof of Proposition 5.1 uses the theory of character deflations, as developed earlier in the paper, together with Frobenius reciprocity.

Generalizations of the Foulkes recurrence

My former Ph.D. student Jasdeep Kochhar used character deflations to prove a considerable generalization, in which is replaced with an arbitrary partition, and with an arbitrary hook partition. I think the only reason he stopped at hook partitions was that this was the only case where there was a convenient combinatorial interpretation of a certain inner product (see the end of this subsection), because his argument easily generalizes to show that

where is any partition of , the first sum is over all (as before) and the second sum is over all . Since a one part partition has a unique -hook, if then the only relevant is . Hence a special case of Kochhar’s result, that generalizes the original result in only one direction, is

with the same condition on the sum over . In the special case where , the plethystic Murnaghan–Nakayama rule states that

and substituting appropriately we recover the original result. More generally, Theorem 6.3 in the joint paper implies that if is a hook partition then is the product of and the size of a certain set of border-strip tableaux in which all the border strips have length .

Kochhar’s recurrence can be generalized still further, replacing and with skew partitions and . Below we will prove

where is a skew partition of , and the sums are over all and such that , and are skew partitions.

Preliminaries for a symmetric functions proof of ()

We will use several times that if and are symmetric functions of degrees and , and is a partition of then

One nice proof uses that the coproduct on the ring of symmetric functions satisfies and the general fact

expressing that the coproduct is the dual of multiplication — here one must think of multiplication as the linear map defined by .

Let be the power sum symmetric function labelled by the partition . The expansion of an arbitrary homogeneous symmetric function of degree in the power sum basis is given by

where is the size of the centralizer of an element of cycle type in the symmetric group . (This is in fact the most useful definition for our purposes, but there is also the explicit formula , where is the number of parts of size in , or equivalently, the number of -cycles in .) The symmetric functions version of the Murnaghan–Nakayama rule is

where is the symmetric group character canonically labelled by the skew partition . Thus

expresses a general Schur function in the power sum basis. More typically the Murnaghan–Nakayama rule is applied inductively by repeatedly removing hooks: if then, the coproduct relation implies that

and hence interpreting each side as a character value, we get the familiar relation

where is an -cycle disjoint from .

A symmetric functions proof of ()

Expressing in the power sum basis we get

To continue we proceed as in both Kochhar’s proof and the proof of the original Foulkesian recurrence by splitting up the sum according to the length of the cycle of containing . There are

ways to choose elements to define an -cycle containing ; we must then choose a permutation of the remaining elements. We saw in the preliminaries that, by the Murnaghan–Nakayama rule, if is an -cycle then . Hence the right-hand side displayed above is

We now use that for any symmetric functions (this is clear for with positive integer monomial coefficients from the interpretation of plethysm as ‘substitute monomials for variables’) and an application the coproduct relation from the preliminaries to get

Repeating the first steps in the proof in reverse order in the inductive case for , this becomes

where the sums are as before. This completes the proof.

Stability of Foulkes Coefficients

I’m in the process of typing up a joint paper with my collaborator Rowena Paget where we prove a number of stability results on plethysm coefficients. Here I’ll show the method using the plethysm relevant to Foulkes’ Conjecture.

Let be the set of semistandard tableaux of shape . This set is totally ordered by setting if and only if, in the rightmost column in which and differ, the larger entry occurs in rather than . Identifying semistandard tableaux of shape with -subsets of , this order becomes the colexicographic order on sets; similarly identifying semistandard tableaux of shape with -multisubsets of , it becomes the colexicographic order on multisets. An initial segment of when is shown below.

Plethystic semistandard tableaux

We can now give the key definition.

Definition. Let be a partition of and let be a partition of . A plethystic semistandard tableaux of shape is a -tableau with entries from the set , such that the -tableau entries are weakly increasing order along the rows, and strictly increasing order down the columns, with respect to the total order .

Definition. The weight of a plethystic semistandard tableau is the sum of the weights of its -tableau entries.

Let denote the set of plethystic semistandard tableaux of shape and weight . For example the three elements of are shown below.

It is a nice exercise to show that the set is in bijection with the set of partitions of contained in an box, by the map sending a partition of to the plethystic semistandard tableau whose th largest -tableau entry has exactly entries equal to (the rest must then be ).

Monomial coefficients in plethysms

The Schur function enumerates semistandard -tableaux by their weight. Working with variables and writing, as is common, for , we have

In close analogy, the plethsym enumerates plethystic semistandard tableau of shape by their weight. With the analogous definition of for a plethystic semistandard tableau, we have

Let denote the monomial symmetric function labelled by the partition . (We avoid the usual notation since is in use as the size of .) For instance

It is immediate from the previous displayed equation that the coefficient of the monomial symmetric function in is . Moreover, by the duality

(stated using an Iverson bracket) between the monomial symmetric functions and the complete homogeneous symmetric functions , we have

This equation is the critical bridge we need from the combinatorics of plethystic semistandard tableaux to the decomposition of the plethysm into Schur functions.

Two row constituents in the Foulkes plethysm

As an immediate example, we use the suggested exercise above to find the multiplicities . We require the following lemma.

Lemma. If then .

Stated as above, perhaps the quickest proof of the lemma is to apply the Jacobi—Trudi formula. Recast as a result about characters of the symmetric group, the lemma says that , where is the permutation character of acting on -subsets of . This leads to an alternative proof by orbit counting.

Proposition. We have , where is the number of partitions of contained in an box.

Proof. This is immediate from the lemma above and equation .

In particular, it follows by conjugating partitions that if then the multiplicities of in and agree: this verifies Foulkes’ Conjecture in the very special case of two row partitions. Moreover, specializing to two variables, it follows by conjugating partitions that

This is a combinatorial statement of Hermite reciprocity. More explicitly, since is contained in which, by Young’s rule, has only constituents with at most parts, we have

where the sum ends with if is even, or if is odd.

Stable constituents in the Foulkes plethysm

By the proposition above, if and , then the multiplicity of in , is equal to , independently of and . The following theorem generalizes this stability result to arbitrary partitions. It was proved, using the partition algebra, as Theorem A in The partition algebra and plethysm coefficients by Chris Bowman and Rowena Paget. I give a very brief outline of their proof in the third section below.

Given a partition of , and , let denote the partition . To avoid an unnecessary restriction in the theorem below we also define . For example, the lemma in the previous section that can now be stated more cleanly as . We generalize this in the first lemma following the theorem below.

Theorem [Foulkes stability] Let be a partition of . The multiplicity is independent of and for .

To prove the Foulkes stability theorem we need two lemmas. I am grateful to Martin Forsberg Conde for pointing out that the stability property in the first lemma is critical to the proof and should be emphasised.

Lemma [Schur/homogeneous stability]. Fix and . Let . For each partition there exist unique coefficients for such that

Moreover and unless .

Proof. Going in the opposite direction, we have

where the Kostka number is the number of semistandard Young tableaux of shape and content . Since unless , we are justified in summing only over elements of in .

Let be the set of semistandard tableaux of shape and content . Let . Observe that in any , there are entries of , and since , these s fill up the first row of beyond the end of the second part . This leaves boxes in the top row to be occupied by entries , where the only restriction is that these entries are weakly increasing. Therefore there is a bijection between and the set of semistandard tableaux of disjoint skew-shape and content . It follows that

independently of . Moreover, since , we have , and since unless , we have unless . The lemma now follows by inverting the unitriangular matrix .

Lemma [PSSYT stability]. Fix . For each partition with , the size of the set is independent of and , provided that and .

Outline proof. Observe that if then any -tableau entry in a plethystic semistandard tableau of shape and weight has as its leftmost entry. Similarly, if then the first -tableau entry in such a plethystic semistandard tableau is the all-ones tableau. This shows how to define a bijection between the sets and .

We are now ready to prove the Foulkes stability theorem.

Proof of Foulkes stability theorem Let . By the lemma on homogeneous/Schur stability, it is sufficient to prove that for each partition such that or , the multiplicities are independent of and . This is immediate from equation and the second lemma on PSSYT stability.

Stability for more general plethysms

Let be the set of integer sequences such that for all and . Given and a partition such that is also a partition, we define to be the maximum number of single box moves, always from longer rows to shorter rows, that take the Young diagram of to the Young diagram of .

For instance when and , the maximum number of moves is : the unique longer sequence moves one box from row to row , then three boxes from row to row , then one box from row to row , and finally one box from row to row . The sequence of partitions is

We leave it to the reader to check that ; since one box must be moved directly from row to row , the move sequence above is no longer feasible.

As background and motivation, we remark that is the weight space of the Lie algebra , and an upper bound for is the minimal length of an expression for as a sum of the basic roots . For instance, again with we have

corresponding to the move sequence above, and . In general, we have , or, equivalently,

Remark. Brion uses this Lie theoretic interpretation the stability part of the claim below as Theorem 3.1(ii) in his paper Stable properties of plethysm. Part (i) proves that the multiplicity is increasing, while (iii) gives a geometric interpretation of the stable multiplicity.

Claim Let be a partition and let be such that is also a partition. Let . The plethysm coefficient is constant for and the stable value is .

Our proof again uses the machine of plethystic semistandard tableaux and stable weight space multiplicities, as computed by taking the inner product with complete homogeneous symmetric functions. As a final remark, note that if for a partition then and the claim gives the stability bound in the Foulkes case originally due to Bowman and Paget and proved above.

The partition algebra and stability

Let be the natural representation of the general linear group . In conventional Schur—Weyl duality, one uses the bimodule , acted on diagonally by on the left and by place permutation by on the right to pass between polynomial representations of of degree and representations of . The key property that makes this work is that the two actions commute, and, stronger, they have the double centralizer property:

It follows that when one restricts the left action of by replacing the general linear group with a smaller subgroup, the group algebra must be replaced with some larger algebra. For the orthogonal group one obtains the Brauer algebra, and restricting all the way to the symmetric group , one obtains the partition algebra (each defined with parameter ). In the recent meeting at Oberwolfach, Mike Zabrocki commented that he expected new progress on plethysm problems to be made by applying Schur—Weyl-duality in these variants. Incidentally, I highly recommend Zabrocki’s Introduction to symmetric functions for an elegant modern development of the subject.

An outline of the Bowman—Paget method

Given a partition of , let be the collection of set partitions of into disjoint sets of sizes . The symmetric group acts transitively on each ; let be the corresponding permutation module defined over and let be the corresponding permutation character. For instance the permutation character appearing in Foulkes’ Conjecture of acting on set partitions of into sets each of size is . In this case, each set partition in has stabiliser ; in general a stabiliser is a direct product of wreath products acting on disjoint subsets.

Let denote the set of partitions of into parts all of size at least . The following theorem is an equivalent restatement of Theorem 8.9 in the paper of Bowman and Paget cited above.

Theorem [Bowman—Paget 2018]. Let be a partition of and let . The stable multiplicity is equal to .

The proof is an impressive application of Schur—Weyl duality and the partition algebra. In outline, the authors start by interpreting the left-hand side as the multiplicity of the Specht module in the permutation module . They then apply Schur—Weyl duality to move to the partition algebra, defined with parameter . In this setting, the Specht module becomes the standard module for the partition algebra canonically labelled by . Conveniently this module is simply the inflation of the Specht module from to the partition algebra. By constructing a filtration of the partition algebra module corresponding to , they are able to show that

Restated using characters, this is the version of their theorem stated above. Bowman and Paget also show that depends on the parameters and only through their product (provided, as ever, ); this gives an exceptionally elegant proof that the stable multiplicities for and agree.

A new result obtained by the partition algebra

Using the method of Bowman and Paget I can prove the analogous results for the stable multiplicities in the plethysm . Here it is very helpful that the natural representation of decomposes as , making it not too hard to describe all the embeddings of the representation into the tensor product .

For the case, the analogue of the set is the set of set partitions of into disjoint sets of sizes , now with one subset marked. Let be the corresponding permutation character. Let be the set of partitions of with one marked part, and at most one part of size ; if there is a part of size , it must be the unique marked part, and only the first part of a given size may be marked.

Theorem. Let be a partition of and let . The multiplicity is stable for and . The stable multiplicity is equal to .

As a quick example, the marked partitions lying in are , and with corresponding permutation modules induced from , , and . (This example is atypical in that the subgroups are all Young subgroups; in general they are products of wreath products.) The sum of the permutation charaters is from which one can read off the stable multiplicities of in . For instance has stable multiplicity .

Parallelism in Haskell

The purpose of this post is to give the simplest way I’ve found to get parallel execution to work in ghc 8.10.1.

The unhelpful cabal

I’ll begin by getting rid of the trivial difficulties. I’m obliged to use Stack (and the related cabal system), as it’s the only way I can find to get ghc onto recent versions of Mac OS X. I am unable to make stack work in any simple way. Here is the complicated way I’ve settled on. For each project:

1. Make a directory with all .hs source files.
2. Create a .cabal file as the example below.
3. Run stack --init.
4. Edit stack.yaml so that the resolver field reads resolver: lts-18.3.
5. Run stack ghci
6. Build with stack build
7. Run executable with stack exec Main <arguments>

For (1) use a separate Main.hs module declaring main. Do not expect the ghc option -main-is to work. A suitable .cabal file for (2) is

name:               ParTest
version:            0.0.0.0
cabal-version:      >= 1.22
build-type:         Simple

executable Main
  main-is:          Main.hs
  other-modules:    ParTest
  build-depends:    base >= 4.14.1.0, array, deepseq, parallel
  default-language: Haskell98
  ghc-options:      -threaded -O2 -with-rtsopts=-N

Note that the build-depends field is separate from any import declarations in the .hs files and uses a different naming convention. For instance the package parallel above corresponds to import Control.Parallel and import Control.Parallel.Strategies in the module file. Fortunately if you omit a required package from build-depends then there is a very helpful error message that includes the package name you need. The purpose of (4) is to prevent stack from downloading a more recent version of ghc than it supports: ‘Stack has not been tested with GHC versions above 8.10, and using 9.0.2, this may fail’ — indeed, fail it does. (Thanks to stack‘s insistence on downloading an entirely fresh ghc for each project, I suspect I have now downloaded over 30Gb worth of copies of ghc trying to chase down this glitch.) At least once I’ve found that (6) fails unless one first does (5): I have no idea why.

More positively, while I’ve had no success at all in using --ghc-options="-threaded" to pass options to ghc, the ghc-options field in the cabal file automates all of this, with the relevant run-time option included to boot. And I will concede that despite all the fuss of using cabal, it does in my experience avoid the dreaded ‘dependency hell’.

Note that ghc has to be explicitly told to compile threaded code. If one omits -threaded then par and the related constructs from Control.Parallel appear to have no effect. (When testing this, I discovered that its often essential to run stack clean after editing the .cabal file to make the changes ‘stick’.) This behaviour of ghc seems unnecessarily unhelpful to me: why can’t the compiler issue a warning when it sees par without threading turned on?

Benchmarking with lazy evaluation

A recurring issue with Haskell benchmarks is that lazy evaluation means that it’s very easy to write code that executes quickly, but only becaue it doesn’t do what strict imperative languages such as C might lead one to expect. For a simple example, suppose expensive :: Integer -> Integer is a function such that expensive k takes time to compute. We can build a list of the first n values of expensive using

testExpensive n = length [expensive k | k <- [1..n]]

Irrespective of how expensive is defined, evaluating testExpensive
at the Haskell prompt takes time . The reason is that under lazy evaluation, only the existence of each entry of the list has to be established; each expensive k sits within the list as an unevaluated thunk. This can be seen interactively using the very useful sprint command in ghci. Try for instance

let xs = [expensive k | k <- [1..n]]

for the expensive function of your choice (for instance collatzSum below), followed by :sprint xs, length xs, :sprint xs, sum xs, :sprint xs.

Warning: if you do this interactively, you must avoid giving xs a polymorphic type, as will probably happen if you omit all type annotations. For instance if xs has type Num a => [a] then each evaluation will refer to a separate copy of xs. Thus with let xs = map (\x -> x + 1) [1..10] you’ll always get _ from :sprint xs, whereas let xs = map (\x -> x + 1) [1..10] :: [Int] will work as expected.

An expensive function the compiler can’t magic away

Open mathematical problems are a rich source of such functions. Here I’ll go for the Collatz conjecture, on which Paul Erdős said “Mathematics is not yet ripe enough for such questions”; despite an astonishing partial result due to Terence Tao, his assessment still stands today. Let us define:

collatzList :: Integer -> [Integer] 
collatzList 0 = error "collatzList: 0"
collatzList 1 = []
collatzList n | n `mod` 2 == 0 = n : collatzList (n `div` 2)
              | otherwise      = n : collatzList (3 * n + 1)
          
collatzSum :: Integer -> Integer
collatzSum n = sum $ collatzList n

While ghc is a deeply impressive piece of software, I think we can safely assume that it does not have, deeply embedded in its internals, an effective proof of the Collatz conjecture that gives a short-circuited evaluation of collatzSum. We can therefore take collatzSum as the expensive function we require.

Parallelising the Collatz sum of sums

Evaluating sum [collatzSum k | k <- [1..1000000], using the module Main.hs at the end of this post, takes about 9.5 seconds on my computer. The code below parallelises this computation by splitting the list in two, and evaluating the sum of each half in parallel. Its running time is about 5 seconds.

collatzSumOfSumsP :: Integer -> Integer
collatzSumOfSumsP r = sA `par` (sB `par` sA + sB)
    where sA = sum [collatzSum n | n <- [1..r], n `mod` 2 == 0]
          sB = sum [collatzSum n | n <- [1..r], n `mod` 2 == 1]

Here par is a Haskell function with the type a -> b -> b. The unusual type is a clue that it breaks the normal rules of evaluation. (Indeed, the reasoning used in Wadler’s remarkable paper Theorems for free! shows that the only strict function with this type must discard the first variable and return the second unmodified.) The effect of par is to evaluate the first argument to weak head normal form (WHNF), and then, in parallel, but otherwise following the usual rules of Haskell evaluation, evaluate the second argument. (Compare seq :: a -> b -> b which does exactly the same, but in series.) In particular, since sA is defined in the where clause, it is evaluated exactly once, in parallel with sB.

In fact the simpler definition collatzSumOfSumsP r = sA `par` sA + sB also works: the compiler is smart enough to avoid the ‘not-parallel’ code that in theory computes sA and sA+sB in parallel, but hangs on sA+sB waiting for sA, rather than getting on with sB.

The variation below evaluates the lists in parallel and then takes the sum. Its running time is (up to random noise) the same as collatzSumOfSumsP. For rpar import Control.Monad.Strategies and for force import Control.DeepSeq.

interleave :: [a] -> [a] -> [a]
interleave xs [] = xs
interleave [] ys = ys 
interleave (x : xs) (y : ys) = x : y : interleave xs ys 

parallelInterleave :: (NFData a) => [a] -> [a] -> [a]
parallelInterleave xs ys =
    runEval $ do 
        xsP <- rpar (force xs)
        ysP <- rpar (force ys)
        return $ interleave xsP ysP

collatzSumOfSumsPL :: Integer -> Integer
collatzSumOfSumsPL r = sum $ parallelInterleave ssA ssB
    where ssA = [collatzSum n | n <- [1..r], n `mod` 2 == 0]
          ssB = [collatzSum n | n <- [1..r], n `mod` 2 == 1]

This version is more typical of the kind of problem I really want to parallelise, in which a huge collection of candidate solutions is generated, and then some further computation is done on this collection to decide which solutions work.

Parallel interleave

The engine driving collatzSumOfSumsPL is the function parallelInterleave, which uses rpar from Control.Parallel.Strategies and force from Control.Deepseq to evaluate the lists in parallel.

The use of force is essential because of a very well-known Haskell ‘gotcha’. Consider for instance let xs = collatzList 10; seq xs "Now xs has been evaluated?!". One can check using :sprint that xs is indeed evaluated, but only to WHNF: the output is xs = 10 : _. The correct implementation of force (for lists) is recursive:

forceList :: [a] -> [a]
forceList [] = []
forceList (x : xs) = let xsF = forceList xs in xsF `seq` (x : xsF)  

This can be used as a drop-in replacement for force in parallelInterleave. But it’s all fiddly enough that I think it’s best to leave it to the experts who wrote the Control.DeepSeq package and use force as above. (The first version of this post even had a version that accidentally erased the list, while still failing to force non-head terms.)

The problem with collatzSumOfSumsPL is that since it evaluates both the lists ssA = [collatzSum n | n <- [1..r], n `mod` 2 == 0] and ssB = [collatzSum n | n <- [1..r], n `mod` 2 == 1] in full before taking the sum of each list (and then the sum of the sums), it uses memory proportional to the running time of the entire program, rather than memory bounded by the largest value of collatzSum n as in collatzSumOfSumsP. Our use of par and seq has forced us to confront the messy reality that semantically equivalent programs can have very different space requirements.

More on space

The code below computes collatzSumOfSums by using an array, storing the value collatzSum n for each relevant n. Since Haskell arrays are strict, this means each call collatzSumOfSums r has to fully allocate an array of size .

hugeCollatz :: Integer -> Array Integer Integer
hugeCollatz r = array (1, r) [(i, collatzSum i) | i <- [1..r]]

sumArray :: Array i Integer -> Integer
sumArray arr = sum $ elems arr

collatzSumOfSumsA :: Integer -> Integer
collatzSumOfSumsA r = sumArray $ hugeCollatz r

Using collatzSumOfSumsA as the expensive function in our benchmarks, the extra space required to interleave the strictly evaluated lists before taking the sum can easily be seen using top.

collatzSumOfSumOfSums :: Integer -> Integer
collatzSumOfSumOfSums t = sum [collatzSumOfSums r | r <- [1..t]]

collatzSumOfSumOfSumsAPHuge :: Integer -> Integer
collatzSumOfSumOfSumsAPHuge t = sum [sumArray arr | arr <- arrays]
    where arraysA = [hugeCollatz r | r <- [1..t], r `mod` 2 == 0]
          arraysB = [hugeCollatz r | r <- [1..t], r `mod` 2 == 1]
          arrays  = parallelInterleave arraysA arraysB

collatzSumOfSumOfSumsAPSmall :: Integer -> Integer
collatzSumOfSumOfSumsAPSmall t = sum ss
    where ssA = [sumArray $ hugeCollatz r | r <- [1..t], r `mod` 2 == 0]
          ssB = [sumArray $ hugeCollatz r | r <- [1..t], r `mod` 2 == 1]
          ss  = parallelInterleave ssA ssB

On my machine, evaluating these three functions for t = 2500 take respectively:

• 14 seconds, memory 20Mb
• 8 seconds, memory growing to 320Mb
• 8 seconds, memory 20Mb

The saving in collatzSumOfSumOfSumsAPSmall from summing the arrays as they are produced is shown in the diagram below.

Conclusion

Despite my initial struggles, I think these experiments show that it’s possible to get a substantial gain from parallelism in Haskell without any very expert knowledge or recondite tricks. But to get the full benefit one has to parallelise all the code, not just the first stage in the pipeline. This is of course the more complicated option: my hope for my intended applications is that functions such as rdeepseq can automate the plumbing.

Further reading

I discovered the Eval monad used by rpar :: Strategy a (equivalently, rpar :: a -> Eval a) from Chapter 2 of Parallel and concurrent programming in Haskell by Simon Marlow. Chapter 3 goes into much more detail. See also Chapter 24 of Real world Haskell by Bryan O’Sullivan, Don Stewart, and John Goerzen.

Appendix: Main module

For the record here is the Main.hs module I used to get these timings.

module Main where

import System.Environment

import ParTest

-- Tests with r = 1000000
testSumOfSums :: IO ()
testSumOfSums =
do putStrLn "testSumOfSums"
rStr : _ <- getArgs
let r = read rStr :: Integer
-- putStrLn $ show $ collatzSumOfSums r   -- 316% cpu, 9.582 total
-- putStrLn $ show $ collatzSumOfSumsP r  -- 304% cpu, 4.962 total
putStrLn $ show $ collatzSumOfSumsPL r    -- 342% cpu, 4.998 total

-- Tests with t = 2500
testSumOfSumOfSums :: IO ()
testSumOfSumOfSums =
do tStr : _ <- getArgs
let t = read tStr :: Integer
--putStrLn $ show $ collatzSumOfSumOfSums t       -- 312% cpu 13.837 total, memory 20Mb
--putStrLn $ show $ collatzSumOfSumOfSumsAPHuge t -- 435% cpu 7.902 total, memory to 320Mb
putStrLn $ show $ collatzSumOfSumOfSumsAPSmall t  -- 377% cpu 7.077 total, memory 20Mb

main :: IO ()
main = testSumOfSums
-- main = testSumOfSumOfSums

Q is for quantum

The purpose of this post is to serve partly as a review of Terry Rudolph’s book Q is for quantum and partly as a record of my thoughts after a few months of reading about quantum computation. The first part of Ruldolph’s book may be downloaded for free from his website.

Part 1: Q-computing

The PETE box and the Stern–Gerlach experiment

Q is for quantum begins with a version of the Stern–Gerlach experiment. We are asked to imagine that black and white balls are sent through a box called ‘PETE’. (The afterword makes clear the name ‘PETE’ comes from Rudolph’s collaborator Pete Shadbolt.) After a black ball goes through a PETE box, it is observed to be equally likely to be black and white. The same holds for white balls.

No physical experiment can distinguish the black balls that come out from the black balls that come in, or a white ball that comes out from a white ball from the supply of fresh balls. For example, if the white balls that come out are discarded, and the black balls that come out are passed through a second PETE box, then again the output ball is equally likely to be black and white.

The surprise comes when PETE boxes are connected so that a white ball put into the first one passes immediately into the second. Now the output is always white.

Naturally we are suspicious that, despite our earlier failure to distinguish balls output from PETE boxes from fresh balls, the first PETE box has somehow ‘tagged’ the input ball, so that when it goes into the second box, the second PETE box knows to output a white ball. When we test this suspicion by observing the output of the first PETE box, we find (as expected) that the output of the first box is 50/50, but so is the output of the second. Somehow observation has changed the outcome of the experiment.

This should already seem a little surprising. But if we accept that observed balls coming out of PETE are experimentally indistinguishable from fresh balls then, Rudolph argues, we have to make a more radical change to our thinking: there is no way to interpret the state of an unobserved ball midway between two PETE boxes as either black or white. As Rudolph says, ‘We are forced to conclude that the logical notion of “or” has failed us’. This quickly leads Rudolph to introduce an informal idea of superposition and his central concept of a misty state. For example, the state shown above is drawn as the diagram below.

Rudolph then makes the bold step of supposing that when a black ball, represented by is put through PETE, the output is ; of course this is drawn in his book as another misty state, this time with a minus sign attached to the black ball. Does this minus sign contradict the experimental indistinguishability of output balls? I’ll quote Rudolph’s explanation of this point since it is so clear, even though (alas) it contains the one typo I found in the entire book (page 19):

But it isn’t a “physically different” type of black ball; if we looked at the ball at this stage we would just see it as randomly either white or black. No matter what we do, we won’t be able to see anything to tell us that when it we see it black [sic] it is actually “negative-black”.

In the mathematical formalism, this is the unobservability of a global phase (a consequence of the Born rule for measurement). Thus in a sense the PETE box does tag the black balls, but not in a way we can observe. The behaviour of a white ball sent into two PETE boxes in immediate succession is easily explained using superposition. The mathematical calculation

is not significantly shorter than Rudolph’s equivalent demonstration using misty diagrams on page 20. His book shows impressive economy by explaining many of the key ideas in quantum theory and computation using just these misty diagrams to compute with the PETE box and certain carefully chosen initial states.

Indeed, Rudolph has already shown one fundamental idea: if we accept that the misty state drawn above is a complete description (much more on this later) of a ball leaving a PETE box, then we have to give up on determinism. Instead the universe is fundamentally random. This was difficult for the early architects of quantum theory to accept, since it contradicts the idea that all physical properties have a definite value. Things are perhaps easier for us now: on the quantum side we are used to the uncertainty principle, and I’d argue that the complexity of modern life, and our relentless exposure to probabilistic and statistical reasoning, makes it easier for us to accept that randomness might be ‘hard-wired’ into the laws of physics. We return to these subtle points after the discussion of Part 2 of Rudolph’s book, where we follow Bell’s argument in refuting the ‘local hidden variable’ theory that, even though we cannot observe it for ourselves, PETE boxes are deterministic, and emit balls tagged in such a way that the laws of physics conspire to agree with the predictions from the misty state theory.

Translating from misty diagrams to the usual bra/ket formalism is of course routine. As one might hope, this infusion of mathematics has some advantages. For instance, if we accept the Born rule that measuring in the orthogonal basis , gives with probability and with probability , then conservation of probability requires that this state evolves by unitary transformations in . Rudolph’s ‘bold’ step is now forced: once we have

unitary dynamics requires that, up to a phase,

Thus, as my notation in the diagrams above suggests, the PETE box is the Hadamard gate

The Stern–Gerlach experiment shows further quantum effects which are not captured by Rudolph’s thought experiment. In the original experiment, silver atoms were sent through a magnetic field, strongest at the top of the apparatus and weakest at the bottom. The atomic number of silver is

and correspondingly there is a single electron in the 4f subshell. The behaviour of the atom in the magnetic field in the experiment is determined by the spin of this electron. After passing through the magnetic field, two beams of atoms are observed: one deflected upwards and one deflected downwards. The amount of deflection is constant, showing the quantisation of the spin of this single electron.

Rudolph’s thought experiment corresponds to an extended version of this experiment, in which two different fields are used. Interpreting as `spin up’, the diagram below shows atoms, prepared in the spin-up state by a vertical field, being deflected first by a horizontal magnetic field and then a second horizontal field in the combiner (this field has the reverse gradient to the first horizontal field), and finally a third vertical magnetic field identical to the first one.

If the atoms are observed in the middle part of the apparatus (shown by a blue box above), or if one of the ‘mirrors’ indicated by diagonal lines is replaced with a barrier, then the output is 50%/50% (red text above). This is interpreted on the Wikipedia page as

… the measurement of the angular momentum on the direction destroys the previous determination of the angular momentum in the direction.

But if the atoms are not observed in the middle, then the output from the final vertical field is 100% spin-up, as for the output from the first vertical field. This holds even if the blue part of the apparatus, in which  the horizontal field polarises electrons horizontally into two different beams, sends the atoms on a round trip of thousands of kilometres. As long as, they meet up at the combiner (without observation at any stage), the same interference occurs, and the output from the final vertical field is always spin-up.  Since Rudolph’s thought experiment has no analogue of horizontal polarisation, this feature is not captured. But Rudolph has already made a convincing (and entirely honest) case that quantum phenomena cannot be understood by classical physics or conventional probability.

For a detailed account of the physics of the Stern–Gerlach experiment I found these notes useful. See Figure 6.9 for the experiment shown schematically above. Also I highly recommend this MIT lecture by Allan Adams for an entertaining and instructive treatment of the Stern–Gerlach experiment that has some features in common with Rudolph’s presentation, for instance, the use of colour to replace the spin-up and spin-down states , ; he also brings in `hardness’  to replace horizontal polarisation and the states , seen in the blue part of the diagram above.

Bank vaults and the Deutsch–Josaz algorithm

Part I ends with an illustration of quantum computing. We are asked to imagine that thieves have broken into a bank vault, in which each room is stocked with eight golden bars, numbered from up to . In some rooms, all bars are fake (‘all that glistens is not gold’); in other rooms, there are four fake bars and four real bars. Happily each room has an ‘Archimedes’ machine, that given as input the ball sequence encoding the bar number in binary and one extra ball, flips the colour of the extra ball if and only if the bar is genuine. For example since is in binary, the input balls encoding are black, black, white. We could use either colour for the extra ball. If we use white, then, supposing that bar is genuine, the output is

Moving the result from the -basis to the -basis, , we may rewrite this as

Less happily for them, the thieves only have time to use the Archimedes machine once. The ingenious solution is to apply Archimedes to a superposition of the numbers of all bars, created by three white balls put into three PETE boxes in parallel, with the extra ball in the state , created by putting a black ball into a PETE box. The input is therefore and the output is

where if bar is fake, and if bar is genuine. If all bars are fake then the output is

in agreement with the input. In this case, measuring in the basis must give . Suppose instead that the vault has an even split. Since

measuring in the basis cannot give . Therefore one use of Archimedes suffices to distinguish the two classes of room.

My account here differs from Rudolph’s only in measuring in the -basis rather than applying a further three PETE boxes to move the first three balls back to the -basis, where they can be measured (in the only way possible in his book) by inspecting their colour. This change replaces an operation with a computational flavour (applying three gates in parallel) with mere linear algebra (just express the output in the -basis). Similary I prefer to think of the input as the product state in the -basis rather than as the result of four gates applied to the product state in the -basis. Of course this reflects my perspective that quantum computation is hard but (after 25 years of it) linear algebra is easy. The change of perspective is shown in the two circuit diagrams below.

Rudolph can’t employ these dodges and instead gives a `proof by example’ for the even split case, using an alphabetic notation for the final misty state in the -basis:

with entries. The reader is invited to check that the coefficient of WWW is zero. With the exception of the final discussion of ‘ontic states’, this is probably the hardest part of the book, as clearly the author was aware, writing ‘Even if you raced through all that (as I would do on a first reading) and didn’t really follow it, that’s OK.’ Besides the jump in difficulty, a possible weakness of this section is the contrived nature of the problem. This however reflects the history of the subject: the Deutsch–Josaz algorithm was one of the earliest instances of quantum speed-up over classical algorithms. Rudolph illustrates this speed-up by considering a vault with 65536 gold bars.

I think it is a little too tempting to conclude from Rudolph’s exposition that quantum computers are, at least for some tasks, strictly superior to classical computers. This however is unproved: the subtle point is that in any algorithmic specification of the problem, the Boolean function either has to be treated as an oracle, in which case the Deutsch–Josaz algorithm only proves the weaker result that relative to an oracle quantum computers are superior to classical computers, or given as part of the input, in which case it is no longer clear that there is no better classical algorithm than evaluating at of the inputs.

Still, this section is a nice illustration that quantum computers derive their power from interference, and not just (as Rudolph very clearly explains on page 50) from the superposition of exponentially many states. The reversible nature of quantum computing also emerges quite naturally from the white/black ball model and the use of the fourth ball in the input to Archimedes, but Rudolph chooses not to comment on this.

Part 2: Q-entanglement

This part, the highlight of the book for me, has an exceptionally clearly presented and improved version of the EPR-paradox. I’ll begin by giving my version of the original, separate from the more philosophical concerns of Einstein, Podolsky and Rosen, which I discuss in the final part.

The EPR-paradox as it seems now

Let be -dimensional Hilbert space modelling a single qubit, with -basis , . Alice and Bob have shared the Bell state

so that Alice has control of the first qubit and Bob the second. If all Alice and Bob can do is measure their qubit in the -basis then behaves exactly like a shared (but unknown) classical bit: for each when Alice measures , she can be certain Bob will also measure , and vice-versa.

To motivate the next step we observe that is not, as might seem from the formula above, in any way tied to the -basis. For instance, it is easy to check that

and in fact this formula holds replacing with any orthonormal basis of . It follows that Alice and Bob can measure in any pre-agreed basis of , and obtain the same classical bit. This suggests they might also try measuring in different bases. Let Alice’s basis (for the first qubit) be

and let Bob’s basis (for the second qubit) be

Thus Alice’s basis is obtained by rotating the -basis by , and Bob’s basis by rotating the -basis by . It follows, by considering the inverse rotation, that and . There are of course similar expressions for the -basis elements in terms of Bob’s basis, obtained by replacing with . Using these we obtain

For instance if then , so Alice and Bob either both measure or both measure , as we claimed above. In particular, as already remarked, if Alice and Bob agree to measure in the -basis, so then when Alice measures she can be sure Bob will also measure . If instead then the other two summands vanish and Alice measures if and only if Bob measures . If then there is no correlation between Alice’s measurement and Bob’s measurement. In particular, if Alice and Bob agree that Alice will measure in the -basis and Bob will measure in the -basis then Bob is equally likely to measure as , irrespective of Alice’s measurement.

In general, by the Born rule, if then the probability that Alice and Bob obtain the same result (i.e. either for Alice and for Bob or for Alice and for Bob) is . All this leaves no doubt that Alice’s measurement affects Bob’s. This is the spooky ‘action at a distance’, or non-locality, that so bothered Einstein. We defer further discussion to Part 3, and instead present the main result from Bell’s 1964 paper, written 29 years after Einstein, Podolsky and Rosen.

Bell’s game

We suppose that Alice and Bob are, as is usual in the tortured circumstances of thought experiments in quantum mechanics, held in isolated Faraday cages 20 light years apart. They are made to play the following game. The Gamesmaster chooses two classical bits and tells Alice and Bob . Alice and Bob must each submit further classical bits and . They win if . That is, if then Alice and Bob win if and only if they guess the same, and if then Alice and Bob win if and only if they guess differently.

Using a single shared (but unknown) classical bit, or equivalently, by only measuring the Bell state in the same pre-agreed basis, Alice and Bob can win with probability . One simple strategy is to ignore and entirely and simply submit their shared classical bit. In this case and our heroes win if and only if , which holds with probability . In another strategy Alice submits and Bob submits ; since except when and , again the winning probability is . (This strategy makes no use of their shared bit.) It is not hard to convince oneself that, provided the Gamesmaster plays optimally, for instance by choosing and independently and uniformly at random, no better strategies are available. This holds even if Alice and Bob are allowed to use their own (independent, classical) sources of randomness before deciding what to submit.

By measuring in different bases, Alice and Bob can do strictly better. It is clear that if Alice is told , she wants to choose a basis that must be close to Bob’s, while if Alice is told , then she wants a basis close to Bob’s when , and a basis rotated by nearly a right angle when . Bob is of course in the same position. Thinking along these lines one can show that a good choice of bases for the measurements (each basis depending only on the classical bit each of them is told) is as follows:

• For Alice: if take , if take ;
• For Bob: if take , if take .

These bases are shown in the diagram below.

Note that Alice’s basis is the -basis when and the -basis when . This collection of all four bases is in fact the unique optimal configuration, up to rotations and reflections.

Checking the four cases for shows that if then the bases chosen by Alice and Bob differ by an angle of . Therefore Alice and Bob measure in nearby bases and submit identical bits with probability , winning with probability . If then the bases chosen by Alice and Bob differ by an angle of . The probability that Alice and Bob submit identical bits is now . Since their aim now is to submit different bits, they win again with probability .

To give an explicit example, suppose that , so Alice measures in the -basis, and so Bob measures in the basis rotated by . The relevant form for is

and so, as just claimed, the probability that either Alice measures and Bob measures or Alice measures and Bob measures is .

The Gamesmaster can arrange that Alice and Bob are told and at the same time, and must then reply within a few seconds. (To take into account special relativity, we put Aice at the origin and Bob in a position space-like separated from Alice so that in any reference frame light takes more than the allowed number of seconds to travel from Alice to Bob.) This rules out even one way communication between Alice and Bob, unless they can employ a particle travelling faster than light. By applying a Lorentz transform one can convert any FTL-communication into a violation of causality. It is inconceivable that Alice’s qubit somehow transmits the result of Alice’s measurement to Bob’s qubit. But still, by choosing their bases carefully, Alice and Bob are able to influence the strength of the correlation (or anti-correlation) between their two measurements to the extent that they can play the game strictly better than classical physics allows. All this follows just from the Born rule for measurement and the simple rule proved above for how the Bell state transforms under two different rotations.

Rudolph’s improved version

To make a convincing demonstration of the improvement from the classical winning probability to , Alice and Bob would of course have to play the game multiple times, and accept that they will lose with probability about 15%. For instance, after 100 trials with 85 successes, one would reject the null-hypothesis that Alice and Bob are using a classical strategy with confidence specified by the -value .

In Part 2, Rudolph offers an improved version of the EPR-paradox, using a game with three outcomes (win, draw, lose) in which, by using a suitable entangled -qubit state, Alice and Bob can sometimes win and guarantee never to lose. Rudolph’s ingenious construction means that only measurements in the – and -basis are required, so (making the same shift from measurement-in-arbitrary-basis to computation-by-unitary-operator-and--basis measurement remarked on earlier) Alice and Bob can work the magic using only black and white balls and the PETE box. Rudolph sets things up very carefully, in the entertaining context of Randi’s well known million dollar price for an experimentally testable demonstration of telepathy (or indeed, any psychic phenomenon). In particular, my claim above that no classical strategy can beat in the EPR-game becomes the claim that any classical strategy in Rudolph’s game that has a non-zero winning probability also has a non-zero losing probability: this is convincingly shown in the narrative.

Part 2 ends with a discussion of just what is paradoxical about the games. Rudolph argues that a causal explanation of the nonlocal correlation in misty states is inconsistent with our understanding that causes precede effects, and that information cannot be transmitted faster than light. He remarks ‘physicists seriously consider other disturbing options’, for instance the super-deterministic theory where the bits and and Alice and Bob’s strategy (and even, whether or not Alice and Bob will follow their strategy as instructed) are already ‘known’ to the entangled qubits. Another possibility is that Rudolph’s ‘misty state’, modelling the two entangled qubits, is in fact ‘some kind of real physical object like a radio wave or a bowl of soup, and when we separate the psychics the mist is stretched between them’. (Rudolph is very clear that until this point, the misty states have been a mathematical abstraction, just as my calculations with unitary matrices above.)

Part 3: Q-reality

It is both a strength and weakness of Q is for quantum that at this point it is very tempting to throw up one’s hands and say ‘okay, I’m convinced misty states are the best approximation to reality there is, non-locality and paradoxical behaviour accepted’. I think this is particularly tempting for mathematicians —  surely a theory of such beauty and explanatory power has to be ‘right’? As a partial corrective to this, let me break from following Rudolph’s book, and instead consider the EPR-paradox in its historical context. We follow this with a discussion of quantum teleportation, before rejoining Rudolph’s final chapter.

Rocky states and the EPR-paradox as presented by the authors

At the end of Part 2, Rudolph introduces the idea of a ‘rocky state’, namely a classical probability distribution on physical states. He shows that the entanglement in the Bell state cannot be explained in this way: in mathematical language, a classical probability distribution that gives some probability to the observations and for both Alice and Bob must give a non-zero probability to , but this has coefficient zero in . This supports his conclusion that quantum theory (rather than classical probability) is required to explain the EPR-paradox.

Whatever the status of misty states, rocky states are certainly epistemic: on page 103 early in Part 3, Rudolph writes `the rocky states are unquestionably representing our knowledge’. For example, if I borrow a coin from Malcolm and flip it on a table, and see roughly how far it is from the edge, my rocky state might be as shown left below. Malcolm however knows his coin is double-headed, so his rocky state is as shown on the right.

As Rudolph writes (page 104),

the very fact that two different rocky states can correspond to the same real state indicates that the rocky states themselves are not a physical property of the coin.

So far, so clear, I hope. It is therefore striking that a very similar argument led Einstein, Podolsky and Rosen to conclude that misty states could not be in bijection with real states. To understand this, I think one must first appreciate that the authors took at one of the starting points in their paper that particles had real physical properties that were revealed by observation. Some version of this view, ‘scientific realism’, is implicit in the scientific method, and helps to explain its power. (We used it earlier, when we deduced from the experimental indistinguishability of balls output by the PETE box from fresh balls that there was a fundamental randomness in the laws of physics.) As a working definition, let me define naive realism to mean that an output ball from a PETE box is definitely either black or white — we just don’t know what it is until observation. Equivalently, the -basis state is a convenient mathematical representation for a real state that, on observation, turns out to be either or . Thus, in naive realism, quantum states are incomplete descriptions of real states, and the real states have deterministic non-random behaviour.

Suppose as in the exposition of the EPR-paradox in Part 2, that Alice and Bob share the entangled Bell state , but now separated by (let us say) 10 light seconds, and that Bob refuses to measure until he hears that Alice has done so. Suppose that Bob always measures in the -basis. We saw that if Alice also measures in the -basis then Alice and Bob are guaranteed to get the same -basis measurement, while if Alice measures in the -basis, Bob is equally likely to get as , whatever Alice measures. This agrees with the predictions of the extended version of the Born rule dealing with a measurement on just one qubit in an entangled system. In detail, if Alice measures in the -basis

• and gets then Bob’s qubit is in the state and Bob measures ,
• and gets then Bob’s qubit is in the state and Bob measures .

If Alice measures in the -basis

• and gets then Bob’s qubit is in the state and, by the Born rule, Bob is equally likely to measure as ;
• and gets then Bob’s qubit is in the state and, by the Born rule, Bob is equally likely to measure as .

Thus depending on Alice’s measurement, the vector in Hilbert space (equivalently one of Rudolph’s ‘misty states’, or the ‘wavefunction’ in the language of the EPR paper) describing Bob’s qubit may take two different values. Except for changing ‘position’ to -basis and ‘momentum’ to -basis, this is the same situation as on page 779 of the EPR paper, where the authors write

We see therefore that as a consequence of two different measurements performed upon the first system, the second system may be left in states with two different wavefunctions. On the other hand, since at the time of measurement the two systems no longer interact, no real change can take place in the second system in consequence of anything that may be done to the first system. This is, of course, merely a statement of what is meant by the absence of an interaction between the two systems. Thus, it is possible to assign two different wavefunctions … to the same reality (the second system after the interaction with the first).

The authors conclude that the wavefunction is, like the rocky state of the flipped coin above, an incomplete description of reality. Repeating Rudolph’s argument from page 104 quoted above, since two different rocky states correspond to the same real state, the rocky state cannot be a physical property of the coin. This is consistent with (but does not imply in its full strength) naive realism.

The expectation of the EPR authors, if I understand the history correctly, was that quantum mechanics would be subsumed by a larger theory — maybe with ‘hidden variables’ — whose states would, everyone could agree, be in bijection with physical reality. Even the term ‘hidden variable’ now seems pejorative, but this idea of a progression of understanding by a sequence of more and more refined theories is of course entirely consistent with the history of physics.

Note the quote makes it very clear that the EPR authors do not regard Alice’s act of measurement as an interaction with Bob’s qubit. This assumption should seem doubtful given the game discussed in Part 2, where we saw that the improvement in the winning chance from to depended on Alice and Bob being able to influence the correlation between their measurements of their shared Bell state by careful choice of bases, using only locally available information. Indeed Bell’s 1964 paper concludes that this improvement is inconsistent with a local hidden variable theory:

In a theory in which parameters are added to quantum mechanics to determine the results of individual measurements, without changing the statistical predictions, there must be a mechanism whereby the setting of one measuring device can influence the reading of another instrument, however remote. Moreover, the signal involved must propagate instantaneously, so that such a theory could not be Lorentz invariant.

This puts us back where we were at the end of Part 2, forced to accept the spooky ‘action at a distance’ effect of measuring. This non-locality was the central problem for Einstein with the theory: on the inability to measure Bob’s qubit in both the – and -bases he wrote `es ist mir wurst’ (literally, ‘it is a sausage to me’). I’m happy to agree: I think scientific realism can easily stretch to accommodate measurements whose precision is limited by the uncertainty principle, and even to ruling out as simply nonsensical the idea of measuring both the position and momentum of a particle at the same instant. (Like the – and -matrices, position and momentum are conjugate Hermitian operators.) More worrying perhaps, we are left with no better candidates for the ultimate elements of reality that Rudolph’s misty states. Rudolph admits the problems (page 81):

Such a mist would … have to have many physical properties that differ from any other kind of physical stuff we have ever encountered. It would be arbitrarily stretchable and move instantaneously when you whack it at one end, for example. The whole question of how to interpret the mist—as something physically real? as something which is just mathematics in our heads?—is one of the major schisms between physicists.

I would have liked to see it mentioned here that even if Alice’s measurement does, as experimentally verified, instantaneously affect Bob’s qubit, it appears to be impossible to use this effect to transmit information. To be fair, Rudolph does consider this point carefully, but only later in Part 3. This distinction is particularly relevant in the context of quantum teleportation, which I discuss next.

Quantum teleportation

Most accounts of quantum teleportation that I have seen begin with the circuit below.

Alice begins in control of three unentangled qubits. The first is in the state that she wants to teleport to Bob. After applying the Hadamard and CNOT gates, Alice sends the third qubit to Bob. She then applies another CNOT gate, a Hadamard gate and measures her two qubits in the -basis. (Why?, you might well ask.) She sends the two classical bits that are the results of her measurements to Bob by a classical channel, marked as double blue lines in the diagram. Finally Bob applies a correction by and gates and, as if by magic, obtains .

I think I would have got the idea rather more quickly if the circuit diagram had been accompanied by the explanations below:

• The circuit left of the red dashed line prepares the Bell state on the second and third qubits.
• The CNOT gate and Hadamard gate on the right of the red dashed line transform the Bell basis to the -basis. One example is shown above, another is which is sent by the CNOT gate to and then by the Hadamard gate to .
• By the identity
  when Bob applies the corrections from the classical bits sent by Alice, he obtains . (Note there is no ambiguity in because and stabilise . This identity follows easily from the calculations on page 83 of Quantum computing: A gentle introduction by E. Rieffel and W. Polak.)

Since learning the rudiments of the ZX-calculus, I also find the graphical proof that the circuit behaves as claimed quite satisfying. Note in particular that the Bell state is simply the cup (shown horizontally) on the left of the dashed red-line.

The algebraic view of the ‘yank’ that simplifies the ZX-calculus diagram is the identity

See (36) and (37) in ZX-calculus for the working computer scientist by John van de Wetering for more on this.

It is not hard to convince oneself that Bob cannot learn anything by observing the state unless he knows at least one of the classical bits and sent to him by Alice. For instance, if is known by all to be a -basis element then Bob needs . (And in this case Alice might as well have sent the bit to Bob directly.) Thus while we believe that Alice’s measurements instantaneously affect Bob’s qubit, Bob cannot learn any information until light from Alice can reach Bob. This can be made precise using density matrices: the density matrix for Bob’s qubit is the uniform linear combination of the rank 1 density matrices for the four post-measurement states of the third qubit in the quantum teleportation protocol, namely

Setting this becomes

The right-hand side is the density matrix for the second qubit in the Bell state and is maximally uninformative: measurement in any orthonormal basis gives each basis vector with equal probability .

In addition, quantum teleportation appears to be consistent with naive realism as defined above. Let and think of as a qubit that is with probability and is with probability . At the end of the protocol, this probability distribution is transferred from Alice’s qubit to Bob’s qubit. This is consistent with the idea that the qubit has a definite, but unknown state, to which this probability distribution refers.

In a classical analogue (which I learned from Prof. Ruediger Schack) this transfer of probability distributions can, and in fact must be interpreted entirely epistemically. The analogue of the Bell state is two coins in unknown but equal states: imagine Alice tapes coin 2 to coin 3, flips the composite coin, and then without looking at either coin, keeps coin 2, and gives coin 3 to Bob. The analogue of is a classical probability distribution on coin 1. In the protocol, Alice performs a parity measurement by performing another ‘tapped together flip’ on coins 1 and 2. She then looks at them both, and learns whether they are ‘same’ or ‘different’. She reports this to Bob, who then flips coin 3 if and only if Alice reports ‘different’.

Alice’s probability distribution now refers to coin 3: if Alice believed that coin 1 was heads with probability then she should now believe that Bob’s coin 3 is heads with probability . To show the epistemic character of this, imagine that coin 1 is prepared by a coin toss performed by Alice’s assistant Charlie, and that Alice does not look at the coin until after the parity measurement. If the coin is fair then Alice’s probability is , but Charlie’s probability is either or . In each case, this probability refers to coin 3 at the end of the protocol. Even though can be any real number in the interval , it may now seem that no information is teleported, except the single classical bit from Alice’s ‘same’ or ‘different’.

I think this makes it all a little more plausible that quantum states are incomplete descriptions of a deterministic theory, and that while this theory must include instantaneous ‘actions at a distance’ effects, it could be that such effects cannot be used to convey information, and so do not (from our human perspective) violate causality. And while we saw in the discussion of the PETE box in Part 1, that the realist point of view that qubits have a definite state —  we just don’t know what it is until observation —  requires hidden variables, the asymmetry between Alice and Charles seen above, and the epistemic interpretation of the ‘teleportation’, shows that the existence of such hidden information by no means impossible.

Discussion of Part 3

Rudolph begins this part by explaining that if misty states are real then the behaviour of the PETE box can be explained: for example the -basis state models a white ball output by a PETE box; if the next PETE box can ‘see’ this state then it can of course output a white ball in response. (That this happens by linear unitary evolution is nice for mathematicians, but potentially misleading: while linearity means we only have to state the effect of the Hadamard transformation on basis vectors, the behaviour of the PETE box, or rather the Stern–Gerlach magnetic fields, on superpositions is a property of the physical theory.) He also notes that this hypothesis does not require that misty states are a complete description of physical states.

The difficulty with this hypothesis is of course observation: why can PETE boxes observe -basis states without collapse, while human observation collapse everything we see into the -basis? We have seen that this act of observation requires instantaneous ‘action at a distance’ effects. Rudolph mentions attempts to make measurement compatible with unitary dynamics, writing (page 113)

But there are some models which work (at least for the ball type experiments we have considered; making them work for all experiments we can presently do is more tricky), and which soon will be experimentally ruled in or out.

Unhelpfully, no more details are given. He also mentions the ‘many worlds interpretation’ in which measurement splits the universe in two, in which the observer becomes a gigantic misty state representing a superposition of ‘observer saw black’ and ‘observer saw white’.

Next Rudolph considers the epistemic idea that misty states are ‘features of our knowledge, rather than real states of the world’ (page 115). He gives the argument from the EPR paper that since Alice’s measurement of her qubit in the entangled Bell pair can leave Bob’s qubit in two different misty states, and assuming that these measurements do not affect the physical properties of Bob’s qubit, two different misty states correspond to the same physical state, and so misty states cannot be physical properties. We saw above that the improvement from to in the winning probability for Bell’s game makes this assumption very doubtful; Rudolph makes the same point very clearly using his improved version of Bell’s game.

Rudolph goes on to illustrate, as usual in his toy model of black and white balls and PETE boxes, that measurements on an entangled Bell pair cannot be used to send information, by giving a special case of the calculation with density matrices above. The section concludes (page 126)

All this is mainly strange if you consider the mist to be real—if you follow Enstein and deny that the real state of Bob’s ball is changing at all then you should not expect them to be able to communicate in this manner.

But then how would you explain how the psychics won your gold?

The Bell game requires Alice and Bob to share the entangled Bell state; Rudolph’s improved version requires a slightly more complicated entanglement. Rudolph concludes with a demonstration that even separable quantum states show behaviour that is incompatible with naive realism as defined above. (He also paints Einstein as a naive realist, but on my understanding does not accurately reflect Einstein’s opinions by the end of his life.) Rudolph’s exposition features an entertaining dialogue between Einstein and Pooh Bear. I’ll present it rather more briefly here.

Suppose that Malcolm prepares one of the four states

1. ,
2. ,
3. ,
4. .

If, as in naive realism, we do not believe that misty states are themselves real, but instead think that is really either or (we just don’t know which until observation), then since any of the four states may give on observation, it is experimentally impossible to learn anything about which state was prepared. This however is false. We calculate that the output of the circuit shown below

is

1. ,
2. ,
3. ,
4. .

Now consider what happens when we measure the second qubit in the -basis.

• If it is measured as we measure the first qubit in the -basis; if the result of both measurements is then the initial state was not (1), if is then the initial state was not (4).
• If instead the second qubit is measured as then we apply a Hadamard gate to the first qubit, giving (1) , (2) , (3) , (4) , and then measure the first qubit in the -basis. Now from cases (2) and (3) we see that if the result of both measurements is the initial state was not (3), and if it is the initial state was not (2).

Therefore in all cases something can be deduced about the initial state.

Rudolph clearly explains that this result is inconsistent with naive realism but consistent with the view that physical states correspond to unique misty states. But, like Einstein, Rudolph finds the consequences of this, in particularly non-locality, hard to swallow. He concludes (page 139):

I personally live in cognitive dissonance: on a day-to-day basis I talk about the physical properties of the photons … as if they are as tangible as any of the physical properties of the human-scale objects in the room around me. They are not. I suspect I should treat the misty states as states of knowledge, but to be understood within a more general framework of theories of inference than our present theories find comfortable.

The idea that things may not be precisely as they present themselves to our senses has a long pedigree, going back as far as Plato and his shadows on the cave. Hume says it clearly in Section 118 in Enquiry concerning human understanding:

The table, which we see, seems to diminish, as we remove further from it. But the real table, which exists independently of us, suffers no alteration. If was therefore, nothing buts its image, which as present to the mind.

The tension here between things as they are (ontological properties) and things as they seem to us (epistemological properties) has of course been much debated by philosophers after Hume, most notably Kant with his noumena (or Ding an such) and phenomena. What we have seen in this post is that it may be impossible to maintain this separation: the EPR-paradox, Bell’s game, and Rudolph’s final demonstration all point to a theory in which the physical properties making up a real state includes a unique misty state. Moreover, neither the Stern–Gerlach experiment (with its random deflections), nor the EPR-paradox (with its spooky ‘action at a distance’), nor Rudolph’s final demonstration (quantum effects without initial entanglement) require the real state to be anything more than the misty state. But if this is true, it follows that our observed experience of phenomena cannot be disentangled with the ontological question: what is the nature of things as they really are?

Playing the majority game with boolean formulae

In the majority game, there are numbered balls, each either black or white. One knows that black balls are in the majority. At each step, the questioner may ask

‘are balls and the same colour’

and get a truthful answer. How many questions does it take to find a black ball? This problem was first solved by Saks and Werman, who proved the elegant result that questions are necessary and sufficient, where is the number of s in the binary form of .

It is a nice exercise to find a questioning strategy that meets this target. If you discover something fundamentally different to the ‘Binary Knight Hunt’ from Section 2 of this paper, I would like to know about it! (The name of this strategy comes from a reframing of the problem in which black balls become Knights, who always tell the truth, white balls become Knaves, who always lie, and a comparison between balls and becomes the question `Person , is Person a knight?’.)

Since we need it later, I’ll summarise the Binary Knight Hunt here. At each step, the question graph is a forest and all components have -power size. Say that a component is uniform if all its balls have the same colour. At each step the questioner picks two balls in uniform components of the same size and compares them. If the answer is ‘different’, black and white balls are equally balanced in the new unified component; this component can then be ignored. Suppose that a position is reached in which the uniform components have distinct sizes . Since black and white balls are equally balanced in the remaining components and , the balls in the component of size are in the majority. (We will see later that this generalises to multiple colours.) Moreover, since the sum of component sizes expresses as a sum of powers of , the number of components is at least . Since each question reduces the number of components by one, it follows that the Binary Knight Hunt wins in at most questions.

The harder part of the Saks—Werman result is that questions are necessary. This part was generalised by John Britnell and me to the case where black balls outnumber white balls by at least a specified excess.

A related problem asks for the minimum number of questions to identify the colour of every ball. After the Binary Knight Hunt finds a black ball, the question graph is a forest: turning it into a tree by connecting the component of the known black ball to all other components identifies all the balls in questions; the final question graph is a tree. When is odd, there are possible sets of black balls (for each partition one may colour the larger set black), and so we must learn bits of information. Therefore this strategy is optimal. For even the same result holds, but requires a bit more work to prove: see Theorem 4 in this later paper of mine.

The majority game for a boolean function

To state the intended generalisation we need some more notation.
Let be the colour of ball , identifying black with and white with . A comparison of ball with ball reveals . This is where is the two-variable boolean formula

In this post we present some preliminary results and open problems on generalizations of the majority game in which is replaced with an arbitrary boolean formula.

Note that, in the original game, we cannot know for sure a ball is of the minority colour unless it has been compared with a ball known to be of majority colour. This observation has no analogue when comparison is replaced with evaluation of an arbitrary boolean formula. For each boolean formula we therefore have three variants of the majority game.

1. Find a ball of known colour.
2. Find a ball of the majority colour.
3. Find the colour of every ball.

For simplicity we shall assume from now on that is odd.

Linear formulae

The relevant formulae are . We immediately note that if is odd then , and so we can determine a ball’s colour in just one evaluation, making (1) trivial. For (2), the first questions may find white balls, so evaluations are necessary and sufficient. For (3) the obvious strategy uses questions.

Problem 1. Is it possible, using when is odd and , to find the colour of every ball using evaluations?

An attempt to block this strategy by requiring the arguments of to be distinct is easily subverted, provided that . (Equivalently, .) Begin by evaluating for distinct choices of . Suppose that the results are

Since , exactly one of and is odd. If it is then

if it is then

Therefore we obtain balls such that . Since  we are again in the happy position of being able to learn a ball’s colour with a single evaluation. This gives a strategy for game (1) using evaluations. For game (2) we use evaluations

for distinct , each not equal to any of ; this is possible since .

Problem 2. Find optimal strategies for games (1), (2) and (3) using when repeated arguments are disallowed.

Problem 3. Show that game (1) cannot be won if .

When is even one can use a similar trick to reduce to the case by noting that . If distinct arguments are required then one can use questions to find balls such that ; then

Problem 4. Do these reductions give optimal strategies for the three problems?

The results so far suggest that games (1) and (2), with repeated arguments permitted, are the most appealing problems.

Majority vote

An important example of a non-linear boolean function is the -way majority vote function

Since , we must require distinct arguments to avoid the reduction to Problem 1. With this condition, observe that if

then , and since swapping and affected the majority, we must also have ; now for any . This suggests the following strategy: evaluate at disjoint triples until both values and are seen. Let

Now, interpolating between the sets by evaluating and , one can find and with . As above, one further question will win game (1) and one can use very similar ideas to win games (2) and (3).

Unfortunately, if there are few white balls, it may take many evaluations to find a triple in which white balls are in the majority. For instance, suppose that and there are just two white balls. We identify with and cover the -subsets of points of using the

lines in . Since there are distinct -subsets, and each -subset contains -subsets, this is the minimum possible number of -subsets. Still the questioning strategy requires evaluations (plus those to find and ). Generally if then there are lines, and so evaluations may be necessary. Thus the attractive feature of the majority game (and many related Knights and Spies problems) that only questions are needed is lost.

It therefore seems natural to require that there are exactly white balls and black balls. Suppose, again for simplicity, that is odd. If we evaluate at distinct triples (using of the balls) and get every time, then we have used up at least black balls and at most white balls. Hence any remaining triple must have white balls in the majority. This gives a strategy for games (1) and (2) using questions, and for game (3) using questions.

Problem 5. Are these strategies optimal?

Problem 6. Generalize to the majority-vote function with any odd number of variables.

The majority game with values in

Another generalization that might be of interest is to allow different colours, labelled by elements of . The result of a comparison of balls with colours and is now . Components in the question graph are now labelled by -tuples up to cyclic permutation. For example, when a component labelled contains balls of colour , balls of colour and no balls of colour , for some . A comparison of a ball in the component with one in the component unites the components as

for some . In one version of the problem, it is known that balls of one colour are strictly in the majority, and the aim is to find one; in another, the aim is to either find a ball of a colour in plurality (strictly more than such balls) or correctly declare that all colours occur equally often, in a third, the aim is to find a ball of plurality colour (knowing that black balls are in plurality).

Problem 7. Since bits of information are learned in each evaluation, we might expect fewer questions to be necessary than in the usual majority game. On the other hand, the greater number of colours gives the adversary more options. What are optimal strategies for the cyclic -coloured majority and plurality games?

-coloured majority games

Some computer analysis of the cyclic -coloured majority game suggests it may be disappointingly technical. To state some results, it is convenient to define the value of a game to be the number of components in a final position. For , the value is , as for the -colour majority game. But for , the value is and the questioner can win in questions, claiming in a terminal position has three components. One optimal line of questioning follows a Binary Knight Hunt to reach the position

The scan below (click for a larger version) then shows the game tree.

The effect of the cyclic restriction is seen only in some of the sublines. In particular, note that from the position

written as above, a move connecting the components results in either , or and in all cases a majority ball is now known. But without the restriction, the next position may be and no majority ball can be identified. Another subtle point is that the next position cannot be , since this has no colour in the majority.

Perhaps surprisingly, if we drop the cyclic ordering, so that components and may be united as

for any permutation then the -coloured majority game essentially reduces to the -colour majority game.

Theorem. For any , the value of -coloured majority game on balls with arbitrary permutations permitted is .

Proof. Let Paul be the questioner and suppose that Carole (an anagram of oracle) supplies the answer. Paul’s aim is to maximise the value of the final position, Carole to minimise it. Paul commits at the start to playing the Binary Knight Hunt: as in the -colour version, an unbalanced component are is now played in after their formation, and Paul stops as soon as all uniform components have distinct sizes. The non-obvious point is that this still works: suppose that the uniform components have sizes and the balanced components have sizes . Let black be the majority colour. If balls in the uniform component of size are not black, then since we have

a contradiction. Therefore the value is at least . On the other hand, Carole can say at the start ‘I promise to play as if there are only two colours’, and, by using an optimal strategy for the -colour game ensure that when Paul claims there are no more than components.

Since removing the cyclic restriction makes the questioners task harder, the theorem implies that the value of the cyclic -coloured majority game is at least . The example above shows that strict inequality may hold.

Other games in the literature

Neither -coloured game is the same as the ‘plurality problem’ considered for three colours in this article in STACS2004 by Martin Aigner, Gianluca De Marco, Manuela Montangero, in which the result of a comparison is the familiar ‘same’ / ‘different’ from the majority game, rather than ‘0 so same’, ‘1 so different with shift 1’, ‘2 so different with shift 2′ as here. The authors’ main result is that between and comparisons are necessary and sufficient to find a black ball.

The closest game considered in the literature appears to come from A plurality problem with three colors and query size three, by Dániel Gerbner, Dániel Lenger and Máté Vizer: here each query involves three balls (so three components are united), and there is no cyclic order on colours. Thus a query with components labelled , , may give . The main result is impressively sharp: if is even then between and questions are needed to identify a ball whose colour is in a plurality.

Engaging students from diverse backgrounds

On 14 September 2021 Royal Holloway Mathematics held a meeting Engaging students from diverse backgrounds, organised by Stefanie Gerke and me, and sponsored by the London Mathematical Society. The speakers were invited to give practical advice on the challenges of teaching university level mathematics. I won’t try to summarise all aspects of the four interesting talks, or all the discussion they stimulated, but here at least is a partial record.

Lara Alcock

Lara Alcock first spoke at Royal Holloway back in 2015. I wrote up this meeting here. For many of us, this was the first time we had heard anyone talk about research in mathematical pedagogy; the event spurred several of us to experiment with new teaching approaches, including the ‘flipped classroom’. Lara’s preferred model was clear from her title: Tilting the classroom: engaging students in large classes. As her abstract promised, she gave 18 (a mathematical 18, there were probably more) straightforward practices to improve student engagement in large lectures. Here are some that stood out for me.

• Put administrative announcements on the board / projector as students come in.
• Start with simple multiple choice questions that test students on material they are supposed to have prepared. I think something like this is essential: students won’t bother preparing unless they know we are serious about it, and this means investing time in live-sessions.
• Give students `gappy’ notes or other activities that they complete during the lecture or during pauses in online videos. For instance, the matching exercise shown below, which seems a nice way to demystify the dry-as-dust field axioms.

• Give students guidance on how to study: Lara mentioned a study of Bjork et al showing there are powerful misconceptions on this issue: one conclusion (see after Figure 3) is that learners typically underestimate the improvement they can make due to studying, but also underestimate the amount they will forget without periodic reinforcement.
• Self-explanation training: how to think deeply about a proof in a way that goes beyond paraphrasing it.
• Ask questions that may split the audience, for instance, which of , , is correct in this gap? `Whatever you think, half the people disagree with you … do you want to change your mind?’.
• Read and explain a proof to the person next to you (viable even with social distancing).

The context was a first year analysis course, a subject that is a notorious cause of student disengagement. It was clear from Lara’s talk and the comments from students that her approach worked, and that students rose to the challenge of her course, both when delivered using live large lectures and, post-Covid, with online lectures. Lara’s enthusiasm for the large lecture as an effective way to teach students shone through: she ended by remarking `I’d much rather have large lectures back: I miss the atmosphere’. For more on of Lara’s approach to analysis teaching, I highly recommend her book, How to think about analysis.

Barrie Cooper

Barrie Cooper’s talk came second and touched on many themes developed more fully in the other three talks. His title was Competencies, challenge, and co-curation: selected strategies for inclusive assessment in mathematics. He started by asking the audience what the terms ‘diversity’ and ‘inclusion’ meant to them: answers included the students’ race, gender and social capital (a useful notion, I think: easy to take it for granted when one has it, and easy to assume others have it when they don’t), and the preparedness of our students for academic study. He then discussed strategies for designing inclusive assessments. One key point was that we should make clear what is expected at each level: what do students need to do to pass, to get a 2:1, and to get a first? Not making these expectations clear may particularly hurt students coming from disadvantaged backgrounds.

Barrie pointed out that designing inclusive assessment meant assessing different skills, and assessing in different ways. For example, his course (on graph theory) had only 30% of credit on the final exam, which was open book. Part of the balance was made up of ‘competency based assessment’: basic tests of understanding on which the required pass mark was 100%. Tools such as Stack, Numbas and, more ambitiously, GitHub Classroom were mentioned.

Barrie finished by going into more detail on ‘co-curation’ in the topical context of epidemic modelling on a dynamic network with probabilistic infection. Students used the R-package epimodel, working in small groups to generate results by experimentation with the model, and sharing whatever resources they found most useful — not always those that Barrie had anticipated. It all sounded like a great exercise to me: both mathematically deep, but also bringing in wider concerns, and open-ended in that (as we’ve seen many times in the last 18 months) there’s no unique right answer.

Matthew Inglis

Matthew Inglis‘ title was Individual differences in students’ use of optional learning resources and concerned two cohorts of students: one doing a mathematics degree, the other studying mathematics as part of an engineering degree. The resources available to them were

• Traditional live lectures;
• Mathematics Learning Support Centre (like a continuous workshop with a staff member always on call);
• Online video lectures and other E-resources.

Usage was tracked throughout the term. It was quickly clear that there were four distinct clusters: the `traditionalists’ who attended live lectures, the `MLSCers’ who made high use of the support centre, the `E-learners’, and (his term) the `slackers’, who did not make much use of anything.

As his graph above shows, the clusters were very pronounced: despite all our efforts with `active blended learning’, it seems students stuck with one learning mode throughout their course. Matthew presented extensive data showing that the traditionalists and MLSCers did best at the exam, the E-learners did significantly worse, and the slackers did very badly indeed. The most significant correlation across all clusters for attainment was with live-lecture attendance, even after normalising the data to take into account the different courses.

Matthew ended by speculating on what would happen if the online lectures were withdrawn? Would the E-learners simply become slackers? Or would they move into another cluster? Since the E-learners did less well than the other two clusters, is producing online videos a good investment of our time? When I lectured cryptography last year, I put a vast effort into making short online videos: even without editing (but some re-recording) I think this took me far longer than delivering the lectures. They were very popular with the students, and attainment was good, but I certainly can’t give an unqualified `yes’ in answer to Matthew’s question. As he said, offering students too much choice makes work for their lecturers.

Maurice Chiodo

After a break for lunch we finished with Maurice Chiodo‘s talk Societal responsibility and ethical conduct in mathematics. He started by challenging the idea that pure mathematics is a universal force for good, or, at worst, morally neutral. Instead, like any powerful tool, it can be used for good or harm, and the harm may arise inadvertently.

A compelling example of this is the use of machine learning algorithms in predictive policing: concentrating police in one area may well find more crime, but at the expense of leaving other crime undetected, and creating a feedback loop that damages community relations. Other examples included the epidemic modelling from Barrie Cooper’s talk, the A-level results fiasco in September 2020, and what we know from the Snowden leaks about mass internet surveillance.

A recurring theme was that models based on unsound implicit assumption could be mathematically sound, but lead to the wrong conclusions. For instance, incredibly enough, the model used to predict the spread of Covid-19 in care homes failed to consider that many staff (often employed by agencies) moved between care homes. Another instance comes from finance: given independent risky assets each with a normal return, their mean has variance , so mathematically is a safer investment. (This is the basis of the infamous Collatoralized Debt Obligation, peddled enthusiastically by investment banks such as Goldman Sachs who rewarded their clients by then betting against the asset they had just purchased.) As the 2008 Financial Crisis showed, the independence assumption is utter garbage. Yet another worrying example comes from the use of machine learning in sentencing algorithms: the algorithm faithfully learns to perpetuate past racial biases.

Maurice then made the key point that students `fail to hear us say that there are ethical issues’. If they are important (and they are), why don’t we tell them? Successfully introducing ethics into the mathematics curriculum has three requirements:

• A seminar series or lecture series or course on societal responsibility in mathematics;
• Mathematical exercises with an ethical component;
• Students must see that all their lecturers take ethics seriously.

As a step towards this, next time I lecture a cryptography course I will set explicit questions on the ethnical issues, rather than just leave them to asides in lectures or printed notes. I hope Maurice’s talk will encourage others to make similar changes: this seems to be to be a valuable way we can broaden our curriculum and maybe even increase student engagement.

Maurice made many further interesting points. For instance, mathematics students appear to gravitate to a utilitarian perspective on ethics; he mentioned the Trolley Problem as a way to counter this. (Even before the Fat Man makes his appearance one can challenge strictly utilitarian `body-count’ ethics by making the person on the second track a close relative, rather than the typical stranger.) He finished by saying that `He was far more scared of 10 mathematicians than 10 lawyers … so why is it that the lawyers get ethical training but we don’t?’

Conclusion

We were lucky to get four interesting talks by excellent speakers. We had postponed the meeting from May 2020 in the hope of holding it face-to-face, but still, the online format enabled a broader attendance from people around the UK.

All four talks had practical advice, but also surprises to offer: how many of us would have predicted the four sharp clusters in Matthew Inglis’ talk (well perhaps, the existence of the ‘slacker’ cluster was no surprise), or the enthusiasm for live lectures shown by Lara’s students.

The final discussion session also offered much to think about: for instance, my not-so-secret view is that university education by intelligent, well-read, liberally minded people has a civilizing influence and value that goes beyond the subject specific skills and knowledge we hope to impart; but this view can rightly be challenged as patronising to our students. Barrie’s talk in particular made me realise that ‘decolonizing the curriculum’ isn’t just the buzz-phrase de jour: there are real practical changes we should all be making to ensure that the mathematics we love so much remains accessible to our changing student intake.

Comments are very welcome and can be posted below.

The Hamming code, quadratic residue codes and an exceptional isomorphism

As a pleasant way to pass a Sunday afternoon — or at least, more pleasant than flat-hunting in Bristol in a wildly inflated property market — let me offer yet another way to prove the exceptional isomorphism . An earlier post uses modular representation theory to do in about a screenful of WordPress. Here we do it using the well known result that, up to position permutation, there is a unique perfect -error correcting linear binary code of length .

The Hamming code

We define the –Hamming code to be the linear code of length and dimension with parity check matrix

Since each non-zero binary word of length appears exactly once as a column of , the syndromes for the possible one bit errors, namely

are distinct. Hence is -error correcting, and therefore has minimum distance . Since the disjoint Hamming balls of radius about the codewords each contain binary words of length , and , these balls partition . Therefore is a perfect -error correcting linear binary code.

Lemma. The automorphism group of is a subgroup of containing .

Proof. Each permutes the non-zero elements of . Let be the position permutation of the columns of induced by . For example,

and so in this case . (Since I am hyper-paranoid about such things, I will verify that is a homomorphism by comparing

with , where denotes the column permutation action.) Now writing for the permutation matrix of (acting on the right as usual when composing permutations left to right, so ), we have

for any . If then the left-hand side is

Therefore , and indeed the image of the homomorphism is a group of position permutations of . For instance, in the example above, and correspondingly, is a codeword in . Since the group homomorphism is injective, the lemma follows. .

Another nice way to prove the lemma is to calculate the words in of weight . By the definition above, these have non-zero entries in the positions

as shown below as the lines in the Fano plane .

Quadratic residue codes

We may construct as where has minimal polynomial . The binary quadratic residue code of length is the cyclic code whose generator polynomial has as its roots the powers of corresponding to the quadratic residues modulo , namely , and . That is,

Since these roots are conjugate under the Frobenius automorphism of , the generator polynomial is the minimum polynomial of ; that is . Thinking of as the ideal of , we have if and only if . From this it is easy to see that has minimum weight and so, as before, is a perfect -error correcting binary code. (More generally, in a quadratic residue code of odd prime length , the minimum distance satisfies .) The same argument holds for the cyclic code whose generator polynomial is is defined using the non-residues modulo .

By the uniqueness result mentioned earlier, the codes , and are all equivalent. Fix a bijection .

We now identify the positions of with . Since is cyclic, the position permutation is an automorphism of . This gives one element of . To obtain the rest, we need the following two claim.

Claim. If then the position permutation preserves .

Proof. Thinking of as an ideal, we have if and only if , so if and only if . This deals with the case , and is obtained by squaring. .

Claim. If then the position permutation sends to . The position permutation and sends to .

Proof. For the first part, use that the generator polynomial for is defined using the non-residues modulo . The second part follows similarly, since is a root of if and only if is a root of .

We may therefore define an action of on by identifying the positions of codewords with and then applying the corresponding position permutation, followed by if (according to the second claim above), we end in rather than in . Using that is a simple group, we see this homomorphism is injective.

Conclusion

We have shown that the automorphism group, say, of a perfect -error correcting linear binary code contains subgroups and isomorphic to the finite simple groups and of order . Setting we have . Since , and and , we have . Hence has index at most in . The coset action of on now gives a homomorphism ; since is simple and has elements of order , this homomorphism must be trivial. Therefore . Similarly . Hence and we have the required automorphism.

Collisions in Greg Egan’s Orthogonal physics

In Greg Egan’s remarkable Orthogonal Trilogy, physics differs from ours in one crucial respect: the Lorentz metric is replaced with the Riemannian metric , putting time on the same footing as space. As one would expect from this author, the consequences are worked out in great detail, and are integral to the plot. This comes at some predictable expense to characterisation and versimilitude: still I’ve found the first two books sufficiently interesting that I can (almost) ignore that much of the exposition consists of the characters giving each other physics tutorials, conducting experiments (which remarkably always work, even if the results often come as a surprise) or listening to each other give lectures and seminars. That said, the physics is leavened by some set-piece ethical dilemmas, and there is also a well-developed biological theme, concentrated on the unique (but not completely implausible) morphology of the Orthogonal race.

The purpose of this post is to do one of the exercises left implicitly to the reader in the second book, The Eternal Flame, in which it is observed that when a photon is deflected by a stationary particle of ordinary matter (called a `luxagen’ in the trilogy), it may glance off at two different angles. Moreover, there is a maximum deflection angle, which is independent of the energy of the photon.

Here I’ll show that this follows from the relation between energy and momentum in Orthogonal physics, and the two conservation laws, and implies that Orthogonal photons are heavier than luxagens. I’ll also show that the same behaviour holds in our universe, whenever the moving particle is heavier than the particle it strikes. My solution uses piles and piles of algebra to arrive at a surprisingly simple answer. Egan’s book hints at a simple trigonometric solution: made more plausible because his characters are of course brilliant at Euclidean geometry, thanks to the double motivation from their physics and our shared mathematics. Or maybe there is a better way to organize the algebra, perhaps starting `We take the Lagrangian …’, or maybe `By working in the reference frame in which the centre of momentum is fixed …’. Either way, I would like to know it.

Much of my interest arises from how Egan (and his characters) arrive at this setup: for more background see the supplementary material on Egan’s website, or read the first book in the trilogy, The Clockwork Rocket. At the time of writing I still have the third book to look forward to.

Space-time and the energy-momentum relation

There is -dimensional space-time. In our universe, when we measure a time interval by the distance that light travels in this interval, space-time has the Lorentz metric . For example, a photon may move from to in one unit of time, and, corresponding to the fact that no time passes for the photon, the Lorentz distance between these space-time points is zero.

In the Orthogonal universe space-time has the Riemannian metric , where is a constant with dimension distance/time; by choosing units appropriately (thus sweeping under the carpet the first half of the first book on Yalda’s experiments on Mount Peerless, the beautiful dual Pythagorean Theorem, and the fact that in Orthogonal physics, the speed of light is not constant), we may assume that the numerical value of is . We take the following (and only the following, for the time being) as further axioms:

1. Physical laws are invariant under the group of transformations preserving the Lorentz/Riemannian metric.
2. Every particle has a symmetry invariant tangent vector to its world line called its –velocity with units distance/time; in our universe and in the Orthogonal universe . A stationary observer measures the particle’s velocity as the -vector , as illustrated in the diagram below (click for a larger pdf).
3. Multiplying the -velocity, normalized to have length (our universe) or (the Orthogonal universe), by the mass of a particle gives its -momentum , where is the -vector momentum.

Note that (1) only makes sense because we measure time and distance in compatible units: thus is dimensionless (while the constant has units distance/time) and whenever a time appears, such as in the diagram above, it is multiplied by . Therefore the symmetry group of space-time can reasonably mix them up.

The way I imagine (2), half-remembered from when I did special relativity 20 years ago (my reference frame), is that the -plane has clocks every metre, connected by rigid rods, which record the time of passing of every particle. The particle is at position (which conveniently enough happens to have a clock) at time , and at position (similarly conveniently placed) at time . The stationary observer can therefore collect the measurements from the clocks (simply by travelling to each one), and approximate the particle’s velocity as and so . Everyday objects in our universe, such as cars, trains and coronavirus, move at a negligible fraction of the speed of light, so is typically huge compared to , and corresponding the velocity measured by the observer is a tiny fraction of the speed of light.

Note this is not the velocity that an observer travelling with the particle would measure. This requires the notion of proper time, seen in the diagram above as the lengths of the trajectories (1 and 2) in the -plane. Using this one can define the -vector velocity as the rate of change of space-time position with respect to the proper time along the trajectory. But in this post we will instead use the axiomatic definition in (2).

In general, writing for the -velocity, and as usual in physics, for the square of its -vector Euclidean norm

axiom (2) implies that . By symmetry invariance, the Lorentzian norm squared of the tangent vector is , and the Euclidean norm squared is (using the assumption that ). Now since has units distance/time, and we care only about the direction of the tangent vector, not its magnitude, it is most convenient (and usual in physics, although I’ve never seen it clearly explained why) to require, as in axiom (3), that the Lorentzian length is .

Thus in our universe , and so , where is the usual dimensionless Lorentz factor. In the Orthogonal universe ; this is again dimensionless because the in the numerator implicitly has units distance/time.

Therefore the -vector velocity is

in our universe and

in the Orthogonal universe.

According to (3) the familiar -vector momentum is obtained by multiplying the spatial component of each of these -vector velocities by the rest mass . In our universe, this agrees with special relativity: a particle moving at -vector velocity is heavier according to a stationary observer by the factor . In the Orthogonal universe, we find instead that the -vector momentum is , so fast moving particles are lighter according to a stationary observer.

Again by (3), the energy of the particle is given by in our universe, and in the Orthogonal universe. Substituting in the -vectors, we find that in our universe has Lorentzian length , and in the Orthogonal universe, has Euclidean length . Equivalently, energy and momentum are related in our universe by

and in the Orthogonal universe by

The former is one statement of the energy-momentum relation between the energy and the -momentum . Observe that the Orthogonal energy-momentum relation can be stated very neatly as and , where . The analogue for our universe, using the identity , is and . We show both by the triangles below, noting that only the Orthogonal triangle is a genuine geometric representation, rather than a helpful aide-memoire.

Collision setup

We now need one final pair of axioms

4. In any system of particles, the sum of all -vector momenta is conserved;
5. In any system of particles, the sum of all energies (as recorded in the time component of -vector momenta) is conserved.

The diagrams below show a stationary particle with mass hit by a heavy particle with mass moving in the direction (and also in time, of course). Again click on the diagram for a larger pdf; four final zero coordinates got clipped off in the scan.

We can suppose that after the collision motion is contained in -space (of which the diagram above shows only the -plane), so all -coordinates are zero: let (oriented clockwise) and (oriented anticlockwise) be the deflection angles of the lighter and heavier particle. The -momenta conservation equations are, in our universe,

Notice that these are homogeneous in . We can therefore divide through by and obtain the equations for the Orthogonal universe by replacing hyperbolic functions with trigonometric functions throughout. As a further small simplification we introduce and observe that for our universe

and for the Orthogonal universe,

Therefore a unified system of equations is

where are in our universe and in the Orthogonal universe. The expression is positive in our universe and negative for the Orthogonal universe; it has the three constants , and (all with units of mass) which we regard as determined by the experimental setup. The unknowns are , , and , appearing only on the right-hand sides.

Numerical solutions

It is routine to solve these equations numerically using NSolve in Mathematica. As an example, we suppose that the heavier particle has three times the mass of the lighter, so . The graph below show the post-collision velocity of the heavier particle for each of the two possible deflection angles , as the energy of the heavier particle increases from least (red) to greatest (violet).

This agrees with the experiment conducted in Orthogonal where the heavier particle is a photon, and the characters observe the deflection angle by visual observation of a system of mirrors. The graph below the has the same axes, comparing the post-collision velocity in the Orthogonal universe (solid) and our universe (dashed), choosing the energies to get comparable shapes. Notice that the maximum deflection angle does not depend on the energy of the heavier particle, or even on which universe we are in: we show below that its sine is the ratio of the masses. Thus in these graphs it is .

The graph below is the equivalent of the first graph showing the final energy of the heavier particle. If you are surprised that red is now at the top, note that in Orthogonal physics, the energy is , so is lower for faster moving particles.

Tangent space equation

Differentiating the momentum conservation equations using that , we obtain

At an extremum for , we have . Multiplying the top equation by and the bottom equation by and subtracting, we obtain

Differentiating the equation from energy conservation, using that and , so the same sign appears both times, we get

Comparing these relations between the independent differentials and , we see that the coefficients must be in the same ratio: that is

or equivalently,

where is in our universe and in the Orthogonal universe.

Solution for maximum deflection

First step: solving for and

The sum of the squares of the two equations for momentum is

By the equation from the tangent space, at maximum deflection . Substituting and using

we get

in which the only unknowns are and . The only equation we have not yet used is the energy conservation equation

It implies that

and, by squaring this relation and subtracting , that

where the sign is for our universe and for the Orthogonal universe. Using these two relations to eliminate and and recalling that is positive for our universe and negative for the Orthogonal universe, we obtain

with the same conventions for the universe dependent signs. Now only appears. After multiplying through by we can simplify the right-hand side as follows

It seems somewhat remarkable to me that all the signs cancel, and we are left with such a simple equation. Perhaps this is a sign that there is some more direct derivation that I am missing. Anyway, cancelling the factors of on each side and rearranging, we get the final equation

which clearly has unique solution

Using the relation from energy conservation we immediately get

hence

Final step: finding and

Substituting these expressions for and into the equation from the tangent space equation we obtain

Again there is a surprising simplification: the numerator of the left-hand fraction becomes if , and so vanishes if . (Of course only the specialization is physically meaningful.) The quotient by is . Hence we have

Similarly one can show that the denominator factorizes as

Therefore the expression above for simplifies to

Using the momentum conservation equation

and the same factorizations to simplify we get

Hence

Rewriting the equation for so it uses only sines and then substituting for using the equation above gives

Hence writing for we get by a rearrangement and squaring the following quadratic equation in :

It is routine to check that the difference between the two sides is

and so the unique solution is . (This is one of several places where we can see that there is a maximum deflection angle if and only if .) Since is positive, we have , and, as claimed some time ago, the sine of the maximum deflection angle is simply the ratio of the masses.

The equation for above now implies that

and hence

Summary

A somewhat remarkable feature of the unique solution for the maximum deflection

where is the total energy (up to the factor in our universe), is that it depends on which universe we are working in only by a change from the hyperbolic function (our universe) to the trigonometric function (Orthogonal universe). Moreover, the maximum deflection angle does not depend on the universe at all.

Signed binomial matrices of small order

Let denote the Pascal’s Triangle matrix defined by , where, as in the motivating paper, we number rows and columns of matrices from 0. More generally, let be the shifted Pascal’s Triangle matrix defined by . Let be the involution reversing the order of rows (or columns) of a matrix, and let

Since is fixed throughout, we shall write , , and for readability in proofs.

Claim 1. For any , and any , the matrix is an involution.

Proof. Since , the matrix is not the identity. Since we have

as required.

Claim 2. We have and .

Proof. The alternating sum used to prove Claim 1 can be used to show that . Hence

as required. The second identity is proved very similarly.

Claim 3. For any , the matrix has order if is odd and order if is even.

Proof. Since we have

It is easily seen that the matrix is not a scalar multiple of the identity, therefore it has the claimed order.

Alternative proof. Another proof uses Claims 1 and 2, as follows

with the end as before.

Let denote the half-turn rotation of an matrix , as defined by . By Claim 3,

is conjugate to and so to . Hence this matrix has order when is odd and order when is even. We state without proof some further identities along these lines.

Claim 4. The matrix has order . If is even then has order . If is odd then has order .

The second case seems particularly remarkable. There are some obstructions (related to root systems) to integer matrices having finite order. These identities were discovered as a spin-off of a somewhat involved construction with linear algebra; I have no idea how to motivate them in any other way. For instance, how looking at

would one guess that it has order ? A computer search found many more examples involving more lengthy products of the signed binomial matrices and their rotations, for instance

 

has order .