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 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; this is the usual way to define the -vector velocity, but except for the informal diagram and the motivation in the previous paragraph, we’re not going to use it here.)

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.

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 .

Completely monotone sequences

A sequence is monotone decreasing if , or equivalently, if for all . We will decide once and for all to deal with decreasing sequences only, and say that such a sequence is completely monotone if all its iterated difference, including the zero differences, are non-negative. That is , , , for all , and so on. Equivalently,

for all . One family of examples I stumbled across, in what seemed like a completely unrelated context of random walks defined on posets with involution, is the two-parameter family

For instance, for each . For a direct proof that this sequence is completely monotone, we use the -integral to write

In the same context, I came across some multivariable polynomials that I conjecture are always positive when evaluated at a completely monotone sequence. These polynomials include

Their positivity is obvious for , because is equal to a difference. For positivity follows from

Despite much struggling, I was unable to find a similar expression for as a sum of products of positive differences. The main purpose of this post is to show that such expressions exist for linear functions, but not in general. I therefore may well have been on a wild-goose chase, hardly for the first time.

Linear polynomials

Fix . Let be the cone of all completely monotone sequences, as defined by the inequalities at the top of this post. Let be the cone spanned by the coefficients in these inequalities.

To make these cones more explicit, the following notation is helpful. Let . Then , and so . It follows inductively that is the set of non-negative linear combinations of the vectors defined by

For instance, if then are the rows of the matrix below

Suppose that for all completely monotone sequences. That is, for all ; we write this as . By Farkas’ Lemma applied to the cone , either

• , or
• there exists such that and .

In the `either’ case, since , the sequence is completely monotone. But then contradicts the hypothesis on . Therefore . So we have a simple necessary and sufficient condition for a linear polynomial to be non-negative on all completely monotone sequences: this is the case if and only if the coefficients are a linear coefficients of the vectors .

Quadratic example

I had hoped that something similar might work for quadratic and higher degree polynomials based on analogously defined cones coming from the coefficients of products in the differences. Here is an counterexample to this hope.

Take and order monomials lexicographically . The homogeneous quadratics in the difference polynomials span the same subspace as the rows of the matrix below.

For instance, the penultimate row has the coefficients for . Define
.

Claim. for all completely monotonic sequences .

Proof. Since the polynomial is homogeneous, we may assume that . Since is linear in , when evaluated at , it is negative if and only if

This inequality implies that

but the quadratic is always at least . Hence , contradicting complete monotonicity.

Claim. is not a positive linear combination of homogeneous quadratics in the differences , , .

Proof. It is equivalent to show that the coefficients of , namely are not in the cone of positive linear combinations of the matrix above. Using the computer algebra Magma, one can compute its dual cone, which turns out to be the set of positive linear combinations of the rows of the matrix below.

In particular, the dual cone contains , and since , is not in the dual of the dual cone, as required.

I suspect that there is no easy way (or maybe even no algorithmic way?) to decide if a homogeneous polynomial in a completely monotone sequence is non-negative, but would be very happy to be proved wrong on this.

Immanants and representations of the infinite symmetric group

This is a reminder to the author of a wild question. (I won’t even call it an idea.) Given a matrix and a symmetric group character , the immanant is defined by

Thus when is the sign character the immanant is the familiar determinant, and when is the trivial character, it is the permanent, of interest partly because of the Permanent dominance conjecture and its starring role in Valiant’s programme to prove the algebraic analogue of the P NP conjecture. Very roughly stated, a more general conjecture is that all immanants, except for the determinant (or multiples of it), are hard to compute.

My wild question is: can one generalize immanants to representations of infinite symmetric groups, and does this give any extra freedom to in some sense `interpolate’ from the trivial to the sign character?

A game on tournaments with multiple edges

Here is a quick post to record a combinatorial game that I think might be of interest, but I don’t have time to think about seriously now.

When Person A plays Person B on the online chess server on which I spend far too much time, the server looks to see who has the longest run of consecutive games as black, and chooses that person to be white. Ties are broken randomly. This is a simple but effective rule: for instance it guarantees that in a series of games, the players alternate colours.

Now suppose a team of people want to manipulate the server into giving one of their members a long run of consecutive games as white. (This would of course be strictly against the server policies.) How big must the team be to guarantee that some member gets consecutive games as white?

A quick look at the small cases reveals the answer. With three people, having arbitrary past histories (this matters below), A plays B and the black player, B say, then plays C. If B is white, then when A plays B again, either A or B establishes a run of two games as white. If B is black (for instance this always happens if C has had a run of two black games), then when A plays C, either A or C gets the same run. Note that in the first case, A never plays C, but instead plays B twice.

With four people, we use the strategy above to give A a run of two white games, and then using B, C, D, give B say, another run of two white games. Now when A and B play, a run of three white games is established. Continuing inductively we see that people can force consecutive white games.

One might also ask for the analogous result where multiple games between the same people are not allowed. If the aim is instead to maximize the number of games as white, then we obtain the combinatorial game where the ‘Picker’ picks an edge of the complete graph and the ‘Chooser’ chooses its orientation. Since in the end all edges are picked exactly once, the role of the ‘Picker’ is defunct: the Chooser can choose an vertex tournament before play begins, and follow its recommendations. By Theorem 1.2 in this article of Alspach and Gavlas, when is odd, can be decomposed into edge cycles of length if and only if divides . Directing each cycle in an arbitrary way then gives a tournament where every vertex has the same in- and out-degree. A simple solution when is prime is to take and use the cycles for on the vertex set , working modulo . When is even, a discrepancy of between the in- and out-degrees of every vertex is inevitable, and it’s not hard to use the construction for odd to see that this can be achieved.

Returning to the original setting where we care about runs of white games, this shows that the Chooser can guarantee the longest run is at most the maximum out-degree, namely .

I’ll end with two natural questions suggested by this quick analysis.

Question 1

Let be a finite graph. In each step the Picker chooses an edge of , and the Chooser directs it; multiple picks are allowed, and the Chooser may choose a different orientation on different picks. Say that vertex has a run of length if in the most recent picks involving this vertex, it was always the source. What is the maximum run length that the Picker can force somewhere in this graph?

Question 2

As Question 1, but now each edge may only be picked once.

For the first in the case of the complete graph, the analysis above shows that the Picker can force a run of length , and since the chooser can make the next directed edge involving this vertex an in-edge, this is best possible. For the second in the case of the complete graph, the Picker cannot do better than , but I do not know if this is always possible.

Flipped classroom and online learning: Personal FAQ

I spent most of June 2 and 3 attending two meetings about online learning: Flexible education (organized by Royal Holloway), at which a College wide teaching model was unveiled, and Teaching and Learning Mathematics Online (organized by Michael Grove, Rachel Hilliam and Kevin Houston). A recurring theme was ‘Active Blended Learning’ or the ‘Flipped Classroom’.  The purpose of this post is to record some observations made by speakers at these talks and my reflections on the research literature on these pedagogic models. Please may I emphasis that this post has absolutely no official status.

Does the College model require the flipped classroom?

This isn’t said explicitly, but I think it is implicit throughout. For example in the seven step programme that we are supposed to follow for each ‘teaching week’, we read

• 3. Engage with learning material. Provides time for students to independently or in groups to engage with learning materials.
• 4. Learning activity. Enables the practical and critical application of learning through individual or group activities.
• 5. Learning Check. Allows the student and lecturer(s) to check that the student learned the content and achieved the learning outcome(s) for the week through an activity or formative/summative assessment.

All this seems to sit fairly happily in a framework where students are expected to work off-line and then come together for synchronous problem solving sessions, maybe checking their understanding before/after by an online quiz. It does not, as as I see it, fit with the traditional model of three live lectures per week.

What is the research evidence for the flipped classroom and active blended learning?

Freeman et al Active learning increases student performance in science, engineering, and mathematics, PNAS 111 (2014) 410–8415 is a meta-analysis of 225 studies that compared student performance in courses lectured in the traditional style and student performance courses with ‘at least some active learning’. The conclusion is clear: active learning improved student performance by about 1/2 of a standard deviation.

More strikingly, the average failure rate was 21.8% under active learning compared to 33.8% under traditional lecturing. Measures of student engagement and satisfaction were not considered in this meta-analysis; my own guess is that the reduction in failure rate is correlated with greater engagement by the weaker students.

A survey talk by Robert Talbot, updating the conclusions of his 2017 book Flipped Learning: A Guide for Higher Education, also has clear conclusions. From the linked slides (emphasis preserved):

• Students in FL courses typically show either greater gains in measures of learning than students in traditional courses or else the differences are not statistically significant (slide 16).
• Students show higher satisfaction with FL and the active learning techniques once FL is in place (slide 18).
• Students often highly negative about FL when first introduced, ‘even while acknowledging benefits of increased group work, more instructor attention, and better grades’ (slide 18).

In Jacqueline O’Flaherty and Craig Philips The use of flipped classrooms in higher education, Internet and Higher Education 25 (2015) 85–95 the authors conclude in Section 4.4:

Our review indicates a number of positive student learning outcomes from this pedagogical approach,

but add:

This review found very few studies that actually demonstrated robust evidence to support that the flipped learning approach is more effective than conventional teaching methods. Only one study used empirical validation to show that a structured flipped classroom in comparison to the traditional one could effectively engage students in deep learning [Hung, Flipping the classroom for English language learners to foster active learning]. Whilst some studies referred to a modest improvement of academic performance, through outcomes of increased examination scores or improved student satisfaction, further research is required in this area …

The cited study was a randomised controlled trial comparing two flipped models with the traditional lecture model on the same content on 75 students. Taking this as the minimum standard for a reliable study is clearly a high (but not unreasonable) barrier when collecting evidence.

Finally I’ll mention a study by James McEvoy, Interactive problem-solving sessions in an introductory bioscience course engaged students and gave them feedback, but did not increase their exam scores. James ‘partially-flipped’ a Royal Holloway biology course by replacing one of two weekly lectures with an interactive problem solving class (see page 5 for details of how this was run). After the change there was a significant improvement in student responses to the two questions ‘The teaching style was engaging‘ and ‘I received feedback on my progress during the course‘. However other measures of student engagement, and (as the title makes clear) exam performance were not significantly affected; there was however a reduction in failure rate.

McEvoy’s findings are consistent with the Freeman et al study and my belief that the flipped classroom may benefit weakest students the most, by helping them to get somewhere, rather than nowhere (as alas, is too often the case in mathematics courses).

What is ‘flipped learning’ anyway?

Talbot’s suggested definition (see about half way down) is

Flipped Learning is a pedagogical approach in which first contact with new concepts moves from the group learning space to the individual learning space in the form of structured activity, and the resulting group space is transformed into a dynamic, interactive learning environment where the educator guides students as they apply concepts and engage creatively in the subject matter.

He is clear that flipped learning does not necessarily require videos, and that a methodological flaw in some metastudies is that they exclude teaching models where videos were not used. Neither does flipped learning necessarily require lecturing. Instead a key feature is that the first contact with new concepts comes from a structured activity, done on one’s own. On my reading, the instructors’s duty is to plan this activity, and then enable students to apply the ideas creatively in individual and group work. Reassuringly (see slide 20), he reports

Implementation matters but not as much as simply offloading direct instruction into structured student activity and using the class time for active learning.

How does one make the flipped classroom work?

Here are some points that I jotted down from the various talks. Sue Pawley’s talk at TALMO Is there anyone out there? A guide to interactive activities in the online environment was especially useful.

• Make all live sessions worth attending. Don’t deliver the lecture (again), but instead get students to work in groups, learning from each other and you. Make live sessions motivating. Plan your teaching. Think context not content.
• Getting feedback from students is difficult: do not expect many students to speak in front of their peers. They will never speak unless recording is switched off. Quizzes are good and technologically easy. I want a system where students can collaborate in small groups on a ‘digital whiteboard’; at the moment this seems to require high-end tablets.
• Give students a ‘scaffold’. This was stressed by speakers at both events. Do not just say ‘read this’. Do not bombard students with content. Instead say ‘read this, watch that, do this quiz to check your (basic) understanding’.
• Do not use peer review since this just adds to the fear of being wrong. But critiquing anonymous wrong answers (we could even fabricate them) can be useful.
• As an example of what can be done, when everyone involved has a good internet connection and a latest-model iPad Pro, this video has three of the Royal Holloway mathematics staff (two of them pretending to be students) collaborating on a simple geometry problem.
• One thought from me: in all the online talks, the convener collated questions in the chat and then selected the most useful (or most upvoted) to ask. This seems a clear improvement on the traditional model where the most assertive person gets to set the initial subject and tone of the questions.

What ideas are there for quiz questions?

George Kinnear’s talk at TALMO Using quizzes to deliver a course online had many useful ideas, going beyond the usual multiple choice model.

• Faded worked examples: leave gaps in a model proof or solution for students to fill in.
• Invite students to create examples (I think they will need a lot of hand-holding).
• The ‘test effect’: recalling information from memory is beneficial (in the context of the always-connected internet generation, I think this deserves saying). For instance, before a section on integration, he got students to make a table of important functions (left column) and their derivatives (right column).

I very much hope we will be able to use the STACK computer algebra system (which integrates with Moodle) to set questions. It can validate quite complicated algebraic answers and give immediate feedback. For instance, it was used to mark the integration quiz above, and even suggest important functions the students had not used.

My own view is that quiz questions used to review material should be very basic, while questions in interactive workshops should be much tougher and focus on potential misconceptions and common errors.

What about flipping more advanced courses?

All the talks I’ve been to were on fairly basic courses: this includes Kevin Houston’s talk at an LMS Education Day in 2016. There is little research on flipping advanced courses. I believe it can work, e.g. Kinnear’s idea of the faded worked example can be adapted to the faded proof. And advanced courses offer many opportunities for non-trivial (for students) questions about relaxing hypotheses, or strengthening conclusion, as well as reversing implications, chaining implications, spotting contrapositive restatements that are helpful, and so on.

Is this consistent with academic freedom?

I hope so, but at a recent EPMS meeting, the Head of School admitted some freedom would be lost. Personally I’m keen on moving to a flipped model, but I will defend to the (academic) death the freedom of colleagues to teach as they see fit, even when I firmly believe what they are proposing will be ineffective. As the slide below from James McEvoy’s talk shows, the lecturer’s preference for the flipped/traditional model is correlated with student performance.

I’m also concerned about the lack of consultation over the College’s model: I dislike having it patiently explained to me that what they’ve decided is for the best. (Of course consultation is not the same as listening, as we all know well.) By contrast, the Maths model has been extensively consulted on and we are still considering how some parts, e.g. group work, will work in the light of concerns of colleagues.

Athena SWAN: Personal FAQ

Yesterday I finished writing the draft Athena SWAN submission for the Royal Holloway Mathematics and Information Security Group and sent it to members of the two departments for comments.

In this post I’ll collect the gist of those replies I’ve made to comments that might be of general interest (and can be made public), and a few extra ‘non-FAQS’, that I hope will still be of interest. The post ends with the references from the bid with clickable hyperlinks.

Why is the bid so focused on women and gender? What about disability or LGBT+ people?

The primary purpose of Athena SWAN is to address gender inequalities. In Mathematics and Information Security this means tackling the under-representation of women in almost everything we do.

Royal Holloway was one of the first HEIs to get a Race Equality Charter Mark and some of the proposed actions are aimed at BAME (Black, Asian and Minority Ethnic) students. Another action will promote the College workshop ‘How to be an LGBT ally’ and the (excellent) external SafeZone training. Yes, we should do more, but this is a Bronze bid so only the start of a long process to address inequalities.

Are women really under-represented?

I think yes. Mathematics is ahead of many sector norms: for example 40.6% of our undergraduate intake is female, compared to the sector mean of 35.7%; 38.8% of A-level Mathematics students are women. Of our staff 25.0% are women, compared to a sector mean of 20.4%; of professors, 23.1% are women, compared to an appalling sector mean of 12.6%. But all that said, women are half the population, and about 40% of new mathematics graduates are women, so we have very far to go.

Isn’t it discrimination to focus so many actions on women?

I argue very firmly no. The question is a ‘non-FAQ’ that I’ve deliberately worded in a pejorative way. (It is impossible to use the word ‘discrimination’ in this context in the positive sense ‘X has a fine discriminating palate for wine’.) By improving our policies and procedures and thinking particularly about women, we very often make life better for everyone. It is not a zero-sum game. It is legitimate to target actions at women to address under-representation. This does not imply that critical decisions, such as recruitment and promotion, will then be biased in favour of women.

Why the focus on unconscious bias?

Unconscious bias training was the most frequently requested form of training when we surveyed all staff and Ph.D. students. There is strong evidence that unconscious bias exists and prevents women from achieving their potential. An important early study is Science faculty’s subtle gender biases favor male students by Moss-Racusin et al, which asked scientists to evaluate two CVs for a job as a lab manager. The CVs were identical except in one the candidate’s first name was ‘John’, and in the other ‘Jennifer’. Both men and women rated Jennifer as less competent than John, and recommended a lower starting salary.

There is evidence that unconscious bias training can be effective for reducing unconscious bias (see pages 6 and 16: the overall picture is mixed, but the conclusion is clear). My own experience suggests that high-quality training and reading around the issue has made me more aware of the issues, and at least slightly less likely to rush to (probably poor) conclusions.

What can I read about unconscious bias?

I highly recommend the third part of Cordelia Fine’s book Delusions of gender. The first two parts make a very convincing case that many stereotypical gender traits are not hard-wired, but instead products of culture and upbringing, or even (on closer inspection) non-existent. The final part examines how our remorselessly gendered society creates these biases and misconceptions.

What is unconscious bias?

First of all, I prefer the term ‘implicit bias’, since one can wrongly interpret ‘unconscious bias’ as referring to something that is independent of our thought processes and beyond our control.

Let me introduce my personal answer with an object that should be emotionally neutral and familiar to readers, namely ‘a vector space’. What comes into your head? Is it a finite dimensional vector space over , such as the familiar Euclidean space , or (my answer) an indeterminately large space over a finite field: ? Or perhaps the most important vector spaces you meet are function spaces, in which case you might be imagining Hilbert space, with or without a preferred orthonormal basis. Yet other answers are possible: someone working in cryptography might think of . Quite possibly, I’ve missed your preferred example completely. Or maybe your brain just doesn’t work this way, and all you think about is the abstract definition of vector spaces and your immediate associations are to the main theorems you use when working with them. Anyway, my point is that we don’t think about vector spaces ‘in isolation’: instead they come with a bundle of implicit associations that are deeply shaped by our education and day-to-day experience.

Now instead think about ‘Mathematics professor’. Without claiming the thought processes are completely analogous, I hope you will agree that something similar goes on, with a bunch of implicit associations coming into our heads. For instance, I immediately start thinking about some of my professorial colleagues in Mathematics and ISG. In this respect I’m lucky: because I have personal examples to draw on, my immediate mental image is not the stereotypical old white man.

Taking this as a roughly accurate portrait of human cognition, we now see a mechanism in which bias can enter our decisions. For instance, in the Stanford lab manager study, the implicit associations around the word ‘manager’ bring to mind men, and so the male candidate is favoured. I suspect either you will readily accept this point, or feel it is completely unwarranted, so I won’t argue it any further, but instead refer you to the literature.

What about the Implicit Association Test?

My reading suggests that the Implicit Association Test is valuable as a way of raising awarenss of implicit bias. But is has been much criticised, and it is not clear the biases it identifies translate into unfair discrimination.

Isn’t this a huge piece of bureaucracy?

A ‘non-FAQ’, although the question has occurred to others. The answer is ‘Yes’. A recent report has many criticism of the Athena SWAN process. For instance, from the summary on page 3:

The application process must be streamlined and the administrative burden on staff, particularly female staff, reduced.

For what it’s worth, I think I could have written a major grant application or completed a substantial research project in the time it took just to draft the submission. Even this rough measure takes no account of the hours of time (not just mine) spent consulting over draft actions and the many weeks of work that the College’s Equality and Diversity Coordinator put into the bid.

What’s the point of doing all this when it clearly wouldn’t address Y (where Y is the manifest injustice of your choice)?

Just because it (probably) wouldn’t have prevented Y, doesn’t mean it isn’t worth doing for other reasons.

No seriously, what are the consequences if we don’t have an Athena SWAN award?

RCUK (the main funder for mathematics research) recommends ‘participation in schemes such as Athena SWAN’. There is no requirement to have an award, and my impression (contrary to what I half-expected) is that it is not likely to become a requirement in the near future.

Royal Holloway expects its departments to apply for awards. So if we don’t get it, we will either have to change this policy or work towards a reapplication in a few years. In short, we will be back to where we were two years ago. We could implement the Action Plan anyway, but without the motivation of holiding an award, progress might slip.

The Action Plan was formulated after long discussions within the E&D Committee and consulted on widely with department members. All actions are owned by the member of staff most closely involved: this is typically not me (the E&D Champion). I believe it will drive substantial culture improvements in Mathematics and ISG.

Do all Athena SWAN applications have references to the research literature on gender equality and feminism?

(A blatant ‘non-FAQ’.) No. In fact ours is the first I’ve seen. Probably it’s also the first Athena SWAN bid in which the Action Plan is generated by a customised database written from scratch in a functional programming language and outputting to LaTeX.

References

1. Pragya Agarwal, SWAY: Unravelling unconscious bias, Bloomsbury, 2020.
2. Robert W. Aldritch et al, Black, Asian and Minority Ethnic groups in England are at increased risk of death from COVID-19: indirect standardisation of NHS mortality data [version 1; peer review: awaiting peer review], Wellcome Open Research, Coronavirus (COVID-19) collection, 6 May 2020.
3. Doyin Atewologun, Tinu Cornish and Fatima Tresh, Unconscious bias training: An assessment of the evidence for effectiveness, Equality and Human Rights Commission research report 113, March 2018.
4. Athena SWAN Charter Review Independent Steering Group for Advance HE, The Future of Athena SWAN, March 2020.
5. Anne Boring, Kellie Ottoboni and Philip B. Start, Student evaluations of teaching (mostly) do not measure teaching effectiveness, ScienceOpen Research (2016)
6. Caroline Criado-Perez, Invisible Women: Exposing Data Bias in a World Designed for Men, Chatto & Windus, 2019.
7. Cordelia Fine, Delusions of Gender, Icon Books Ltd, 2005.
8. Cordelia Fine, Testosterone Rex Icon Books Ltd, 2017.
9. Uta Frith, Understanding unconscious bias. Royal Society, 2015.
10. Cassandra M. Guarino and Victor M. H. Borden, Faculty service loads and gender: are women taking care of the academic family?, Research in Higher Education (2017) 58 672–694.
11. Nancy Hopkins, Diversification of a university faculty:
    Observations on hiring women faculty in the Schools of Science and Engineering at MIT, MIT Faculty Newsletter 2006 XVIII.
12. Corinne A. Moss-Racusin, John F. Dovidio, Victoria L. Brescoll, Mark J. Grahama, and Jo Handelsmana, Science faculty’s subtle gender biases favor male students, PNAS (2012) 109 16474–16479.
13. Ruth Pearce, Certifying equality? Critical reflections on Athena SWAN and equality accreditation, report for Centre for Women and Gender, University of Warwick, July 2017.
14. Research Excellence Framework, Guidance on submissions 2021, January 2019.
15. Safezone training.
16. UK Trendence Research, How are Gen Z responding to the coronavirus pandemic?, March 2020.
17. Trades Union Congress, Women and casualization: Women’s experience of job insecurity, January 2015.
18. Sandra Tzvetkova and Esteban Ortiz-Ospina, Working women: What determines female labor force participation?, Our World in Data (2017).
19. Liz Whitelegg, Jennifer Dyer and Eugenie Hunsicker, Work allocation models, Athena Forum, January 2018.

The counter-intuitive behaviour of high-dimensional spaces

This post is an extended version of a talk I last gave a few years ago on an extended Summer visit to Bristol; four weeks into lockdown seems like a good time to write it up for a more varied audience. The overall thesis is that it’s hard to have a good intuition for really high-dimensional spaces, and that the reason is that, asked to picture such a space, most of us come far closer to something like then the more accurate . This is reflected in the rule of thumb that the size of a tower of exponents is determined by the number at the top: is tiny compared to and should seem only a tiny bit smaller than

when both are compared with .

Some details in the proofs below are left to the highly optional exercise sheet that accompanies this post. Sources are acknowledged at the end.

As a warm up for my talk, I invited the audience to order the following cardinals:

Of course they are already correctly (and strictly) ordered by size. From the perspective of ‘effective computation’, I claim that and are ‘tiny’, and are ‘huge’ and and sit somewhere in the middle. To give some hint of the most surprising part of this, interpret as the Cantor set , so is the set of subsets of . Computationally definable subsets of are then computable predicates on (i.e. functions ), and since is compact, it is computable whether two such predicates are equal. In contrast, there is no algorithm that, given two predicates on , will run for a finite length of time and then return the correct answer.

Euclidean space and unit balls

Let be the solid -dimensional unit ball in Euclidean space and let be the -dimensional surface of .

House prices in Sphereland

Imagine a hypothetical ‘Sphereland’ whose inhabitants live uniformly distributed on the surface . For instance, is the one-point compactification of Flatland. With a god’s eye view you are at the origin, and survey the world. At what values of the final coordinate are most of the inhabitants to be found?

For example, the diagram below shows the case with two regions of equal height shaded.

It is a remarkable fact, going all the way back to Archimedes, that the surface areas of the red and blue regions are equal: the reduction in cross-section as we go upwards is exactly compensated by the shallower slope. For a calculus proof, observe that in the usual Cartesian coordinate system, we can parametrize the part of the surface with and by . Choose . Then since is orthogonal to the gradient of the sphere at , to first order, if we increase the height from to then we must decrease the second coordinate from to . This is shown in the diagram below.

Hence the norm squared of the marked line segment tangent to the surface is

As in Archimedes’ argument, the area of the region between the lines of latitude of height between and is (to first order in ) the product of and the circumference of the line of latitude at height . It is therefore

which is independent of . As a small check, integrating over from to we get for the surface area of the sphere; as expected this is also the surface area of the enclosing cylinder of radius and height .

This cancellation in the displayed formula above is special to the case . For instance, when , by the argument just given, the arclength at height is proportional to . Therefore in the one-point compactification of Lineland (a place one might feel is already insular enough), from the god’s perspective (considering slices with varying ), most of the inhabitants are near the north and south poles (), and almost no-one lives on the equation ().

More generally, the surface area of is given by integrating the product of the arclength and the surface area of the ‘latitude cross-section’ at height . The latter is the -dimensional sphere of radius . By dimensional analysis, its surface area is for some constant . Hence the density of Sphereland inhabitants at height is proportional to . (A complete proof of this using only elementary calculus is given in Exercise 1 of the problem sheet.) In particular, we see that when is large, almost all the density is at the equator . From the god’s eye perspective, in high-dimensional Sphereland, everyone lives on the equator, or a tiny distance from it. To emphasise this point, here are the probability density functions for using colours red then blue then black.

As a further example, the scatter points below show random samples from , taking (left) coordinates and (right) coordinates. Note that almost no points have a coordinate more than (in absolute value). Moreover, since the expected value of each is , we find most of the mass at .

In particular, if a random inhabitant of large -Spaceland is at then it is almost certain that most of the are very small.

One feature of this seems deeply unintuitive to me. There is, after all, nothing intrinsic about the -coordinate. Indeed, the god can pick any hyperplane in through the origin, and get a similar conclusion.

Concentration of measure

One could make the claim about the expected sizes of the coordinates more precise by continuing with differential geometry, but Henry Cohn’s answer to this Mathoverflow question on concentration of measure gives an elegant alternative approach. Let be independent identically distributed normal random variables each with mean and variance . Then normalized to have length is uniformly distributed on . (A nice way to see this is to use that a linear combination of normal random variables is normally distributed to show invariance under the orthogonal group .) Moreover, , and, using that , we get

Hence, by Chebychev’s Inequality that if is a random variable then

the probability that is at most which tends to as . Therefore we can, with small error, neglect the normalization and regard as a uniformly chosen point on . By Markov’s inequality, that if is a non-negative random variable then , the probability that (or equivalently, ) is at most , and the probability that (or equivalently, with ) is at most . Since

as , we see that with high probability, a random Sphereland inhabitant has all its coordinates in . I think this makes the counter-intuitive conclusion of the previous subsection even starker.

Volume of the unit ball

The ‘length of tangent line times area of cross-section’ argument says that if is the surface area of then

A quick trip to Mathematica to evaluate the integral shows that

It follows easily by induction that . Since and , the volume of is

In particular, from for we get . Hence (is there a quick way to see this?), and the proportion of the cube occupied by the ball is

Thus the proportion tends to , very quickly. I find this somewhat surprising, since my mental picture of a sphere is as a bulging convex object that should somehow `fill out’ an enclosing cube. Again my intuition is hopelessly wrong.

Coding Theory

We now turn to discrete spaces. Our friends Alice and Bob must communicate using a noisy channel that can send the bits and . They agree (in advance) a binary code of length , and a bijection between codewords and messages. When Bob receives a binary word in he decodes it as the message in bijection with the nearest codeword in ; if there are several such codewords, then he chooses one at random, and fears the worst. Here ‘nearest’ of course means with respect to Hamming distance.

Shannon’s probabilistic model

In this model, each bit flips independently with a fixed crossover probability . If then reliable communication is impossible and if then we can immediately reduce to the case by flipping all bits in a received word. We therefore assume that . In this case, Shannon's Noisy Coding Theorem states that the capacity of the binary symmetric channel is , where is the binary entropy function. That is, given any , provided is sufficiently large, there is a binary code and size such that when is used with nearest neighbour decoding to communicate on the binary symmetric channel, the probability of a decoding error is (uniformly for every codeword). We outline a proof later.

For example, the theoretical maximum 4G data rate is bits per second. Since , provided is sufficiently large, even if one in four bits gets randomly flipped by the network, Shannon’s Noisy Coding Theorem promises that Alice and Bob can communicate reliably using a code of size . In other words, Alice and Bob can communicate reliably at a rate of up to million bits per second.

Hamming’s adversarial model

In Hamming’s model the received word differs from the sent word in at most positions, where these positions are chosen by an adversary to be as inconvenient as possible. Nearest neighbour decoding always succeeds if and only if the minimum distance of the code is at least .

In the usual binary symmetric channel with crossover probability , when is large, the chance that the number of flips in the normal binary symmetric channel is more than is negligible. Therefore a binary code with minimum distance can be used to communicate reliably on an adversarial binary symmetric channel with crossover probability , in which the number of flipped bits is always , and these bits are chosen adversarially.

So how big can a code with minimum distance be? Let be such a code and for each , let

Observe that each is a binary code of length and minimum distance at least . By the Plotkin bound, for all . (Equality is attained by the Hadamard codes .) Since each has size at most , we find that

The relative rate of a binary code of length is defined to be . By the bound above, if is -error correcting (and so its minimum distance satisfies ) we have

In particular, if then : the code consists of a vanishing small proportion of . We conclude that if the crossover probability in the channel is or more, fast communication in the Hamming model is impossible.

An apparent paradox

We have seen that Shannon’s Noisy Coding Theorem promises reliable communication at a rate beyond the Plotkin bound. I hope it is clear that there is no paradox: instead we have demonstrated that communication with random errors is far easy than communication with adversarial errors.

In my view, most textbooks on coding theory do not give enough emphasis to this distinction. They share this feature with the students in my old coding theory course: for many years I set an optional question asking them to resolve the apparent clash between Shannon’s Noisy Coding Theorem and the Plotkin Bound; despite several strong students attempting it, only one ever got close to the explanation above. In fact in most years, the modal answer was ‘mathematics is inconsistent’. Of course as a fully paid-up member of the mathematical establishment, I marked this as incorrect.

The structure of large-dimensional vector spaces

I now want to argue that the sharp difference between the Shannon and Hamming models illuminates the structure of for large is large.

When lecturing in the Hamming model, one often draws pictures such as the one below, in which, like a homing missile, a sent codeword inexorably heads towards another codeword (two errors, red arrows), rather than heading in a random direction (two errors, blue arrows).

While accurate for adversarial errors, Shannon’s Noisy Coding Theorem tells us that for random errors, this picture is completely inaccurate. Instead, if is a large code with minimum distance and is sent over the binary symmetric channel with crossover probability , and is received, while is at distance about from , it is not appreciably closer to any other codeword . I claim that this situation is possible because is ‘large’, in a sense not captured by the two-dimensional diagram above.

Shannon’s Noisy Coding Theorem for the binary symmetric channel

To make the previous paragraph more precise we outline a proof of Shannon’s Noisy Coding Theorem for the binary symmetric channel. The proof, which goes back to Shannon, is a beautiful application of the probabilistic method, made long before this was the standard term for such proofs.

We shall simplify things by replacing the binary symmetric channel with its ‘toy’ version, in which whenever a word is sent, exactly bits are chosen uniformly at random to flip. (So we are assuming .) By the Law of Large Numbers, this is a good approximation to binomially distributed errors, and it is routine using standard estimates (Chebychev’s Inequality is enough) to modify the proof below so it works for the original channel.

Proof. Fix and let , where will be chosen later. Choose codewords uniformly at random from . Let be the probability (in the probability space of the toy binary symmetric channel) that when is sent, the received word is decoded incorrectly by nearest neighbour decoding. In the toy binary symmetric channel, the received word is distance from , so an upper bound for is the probability that when is sent, there is a codeword with within distance of the received word. Note that are all themselves random variables, defined in the probability space of the random choice of code.

Now is in turn bounded above by the expected number (over the random choice of code) of codewords with within distance of the received word. Since these codewords were chosen independently of and uniformly from , it doesn't matter what the received word is: the expected number of such codewords is simply

where is the volume (i.e. number of words) in the Hamming ball of radius about . We can model words in this ball as the output of a random source that emits the bits and with probabilities and , respectively. The entropy of this source is , so we expect to be able to compress its -bit outputs to words of length . Correspondingly,

(I find the argument by source coding is good motivation for the inequality, but there is of course a simpler proof using basic probability theory: see the problem sheet.) Hence

Since , the probability of decoding error when is sent becomes exponentially small as becomes large. In particular, the mean probability is smaller than , provided is sufficiently large. A Markov’s Inequality argument now shows that by throwing away at most half the codewords, we can assume that the probability of decoding error is less than for all remaining codewords.

Varying the alphabet

Increasing the size of the alphabet does not change the situation in an important way. In fact, if is replaced with for large then the Singleton Bound, that becomes effective, giving another constraint that also apparently contradicts Shannon’s Noisy Coding Theorem. There is however one interesting difference: in , every binary word has a unique antipodal word, obtained by flipping all its bits, whereas in there are words at distance from any given word. This is the best qualitative sense I know in which is smaller than .

Cryptography and computation

Readers interested in cryptography probably recognised above as the key length of the block cipher DES. This cipher is no longer in common use because a determined adversary knowing (as is usually assumed) some plaintext/cipher pairs can easily try all possible keys and so discover the key. Even back in 2008, an FPGA-based special purpose device costing £10000 could test DES keys every second, giving days for an exhaustive search.

Modern block ciphers such as AES typically support keys of length and . In Applied Cryptography, Schneier estimates that a Dyson Sphere capturing all the Sun’s energy for 32 years would provide enough power to perform basic operations, strongly suggesting that bits should be enough for anyone. The truly paranoid (or readers of Douglas Adams) should note that in Computational capacity of the universe, Seth Lloyd, Phys. Rev. Lett., (2002) 88 237901-3, the author estimates that even if the universe is one vast computer, then it can have performed at most calculations. Thus in a computational sense, is tiny, and and are effectively infinite.

The final number above was . The Chinese supercomputer Sunway TaihuLight runs at 93 Petaflops, that is operations per second. A modern Intel chip has AES encryption as a primitive instruction, and can encrypt at 1.76 cycles per byte for a 256-bit key, encrypting 1KB at a time. If being very conservative, we assume the supercomputer can test a key by encrypting 16 bytes, then it can test keys every second, requiring days to exhaust over keys. Therefore is in the tricky middle ground, between the easily computable and the almost certainly impossible.

My surprising claim that also sits somewhere in the middle comes from my reading of a wonderful blog post by Martín Escardó (on Andrej Bauer’s blog). To conclude, I will give an introduction to his seemingly-impossible Haskell programs.

As a warm-up, consider this Haskell function which computes the Fibonacci numbers , extending the definition in the natural way to all integers .

fib n | n == 0  = 0
      | n == 1  = 1
      | n >= 2  = fib (n-1) + fib (n-2)
      | n <= -1 = fib (n+2) - fib (n+1)

Except from the minor notation change that the conditions appear before rather than after the equals sign, this Haskell code is a verbatim mathematical definition. The code below defines two predicates and on the integers such that is true if and only if and is true if and only if mod .

p n = fib n * fib n - fib (n+1) * fib (n-1) == (-1)^(n+1)  
q n = fib n `mod` 3 == 0

The first equation is Cassini’s Identity, so is true for all ; is true if and only if is a multiple of . We check this in Haskell using its very helpful ‘list-comprehension’ syntax; again this is very close to the analogous mathematical notation for sets.

*Cantor> [p n | n <- [-5..5]]
[True,True,True,True,True,True,True,True,True,True,True]

*Cantor> [q n | n <- [-5..5]]
[False,True,False,False,False,True,False,False,False,True,False]

Therefore if we define to be true (for all ) and to be true if and only if , we have and .

An important feature of Haskell is that it is strongly typed. We haven’t seen this yet because Haskell is also type-inferring in a very powerful way, that makes explicit type signatures usually unnecessary. Simplifying slightly, the type of the predicates above is Integer -> Bool, and the type of fib is Integer -> Integer. (Integer is a built in Haskell type that supports arbitrary sized integers.) The family of predicates defined by

is defined by

r m n = n `mod` m == 0

Here r has type Integer -> Integer -> Bool. It is helpful to think of this in terms of the currying isomorphism , ubiquitous in Haskell code. We now ask: is there a Haskell function

equal :: (Integer -> Bool) -> (Integer -> Bool) -> Bool

taking as its input two predicates on the integers and returning True if and only if they are equal? The examples of above show that such a function would, at a stroke, make most mathematicians unemployed. Fortunately for us, Turing’s solution to the Entscheidungsproblem tells us that no such function can exist.

Escardó’s post concerns predicates defined not on the integers , but instead on the -adic integers . We think of the -adics as infinite bitstreams. For example, the Haskell definitions of the bitstream representing and the bitstream representing

are:

data Bit = Zero | One
type Cantor = [Bit]
zero = Zero : zero
one  = One : zero
bs   = One : Zero : bs :: Cantor

(I’m deliberately simplifying by using the Haskell list type []: this is not quite right, since lists can be, and usually are, finite.) Because of its lazy evaluation — nothing is evaluated in Haskell unless it is provably necessary for the computation to proceed — Haskell is ideal for manipulating such bitstreams. For instance, while evaluating bs at the Haskell prompt will print an infinite stream on the console, Haskell has no problem performing any computation that depends on only finitely many values of a bitstream. As proof, here is :

*Cantor> take 10 (bs + tail bs)
[One,One,One,One,One,One,One,One,One,One]
*Cantor> take 10 (bs + tail bs + one)
[Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero]

(Of course one has to tell Haskell how to define addition on the Cantor type: see Cantor.hs for this and everything else in this section.) As an example of a family of predicates on , consider

twoPowerDivisibleC :: Int -> Cantor -> Bool
twoPowerDivisibleC p bs = take p zero == take p bs

Thus twoPowerDivisibleC p bs holds if and only if bs represents an element of . For example, the odd -adic integers are precisely those for which twoPowerDivisibleC 1 bs is false:

*Cantor> [twoPowerDivisibleC 1 (fromInteger n) | n <- [0..10]]
[True,False,True,False,True,False,True,False,True,False,True]

In the rooted binary tree representation of shown below, the truth-set of this predicate is exactly the left-hand subtree. The infinite path to is shown by thick lines.

Here is a somewhat similar looking definition

nonZeroC :: Cantor -> Bool
nonZeroC (One : _)   = True
nonZeroC (Zero : bs) = nonZeroC bs

While a correct (and correctly typed) Haskell definition, this does not define a predicate on because the evaluation of nonZeroC zero never terminates. In fact, it is surprisingly difficult to define a predicate (i.e. a total function with boolean values) on the Cantor type. The beautiful reason behind this is that the truth-set of any such predicate is open in the -adic topology. Since this topology has as a basis of open sets the cosets of the subgroups , all predicates look something like one of the twoPowerDivisibleC predicates above.

This remark maybe makes the main result in Escardó’s blog post somewhat less amazing, but it is still very striking: it is possible to define a Haskell function

equalC :: (Cantor -> Bool) -> (Cantor -> Bool) -> Bool

which given two predicates on (as represented in Haskell using the Cantor type) returns True if and only if they are equal (as mathematical functions on ) and false if and only if they are unequal. Escardó’s ingenious definition of equalC needs only a few lines of Haskell code: it may look obvious when read on the screen, but I found it a real challenge to duplicate unseen, even after having read his post. I encourage you to read it: it is fascinating to see how the compactness of as a topological space corresponds to a ‘uniformity’ property of Haskell predicates.

Sources

The results on volumes of spheres and balls are cobbled together from several MathOverflow questions and answers, in particular Joseph O’Rourke’s question asking for an intuitive explanation of the concentration of measure phenomenon, and S. Carnahan’s answer to a question on the volume of the -dimensional unit ball. The coding theory results go back to Shannon, and can be found in many textbooks, for example Van Lint’s Introduction to coding theory. The use of the ‘toy’ binary symmetric channel is my innovation, used when I lectured our Channels course in 2019–20 to reduce the technicalities in the proof of Shannon’s Noisy Coding Theorem. The diagrams were drawn using TikZ; for the spheres I used these macros due to Tomasz M. Trzeciak. The material about computability is either very basic or comes from a blog post by Martín Escardó (on Andrej Bauer’s blog) giving an introduction to his paper Infinite sets that admit fast exhaustive search, published in the proceedings of Logic in Computer Science 2007.

A dismal outlook: why does Microsoft Teams make it so hard to join meetings?

The purpose of this post is to document two of the more blatant bugs I’ve encountered in my forced exposure to Microsoft Teams during the Coronavirus crisis. To add insult to injury, the only way to work around them is to use the Microsoft Outlook, another piece of software riddled with deficiencies. And don’t even think of using Microsoft Outlook (the application): instead one must use the still clunkier web interface.

Let’s get started. Here is a screenshot of me scheduling a meeting at 15:22 for 16:00 today.

Notice anything odd. Probably not: what sane person checks the timezone? But, look closely: Microsoft Teams firmly believes that London is on UTC+00:00 (same as GMT), not BST. This belief is not shared by my system, or any other software on it that I can find.

Now let’s try to join the meeting. Okay it’s early, but we are keen. Here is a screenshot of me hovering with my mouse over the meeting.

There is no way to join. Double clicking on the meeting just gives a chance to reschedule it (maybe to a later date, when Microsoft has fixed this glaring deficiency). The ‘Meet now’ button starts an unrelated meeting.

Okay, maybe our mistake was to join an MS Teams meeting using MS Teams. Let’s try using the Outlook web calendar. Here is a screenshot.

Here is a close-up of the right hand of the right-hand side

On the one hand, the times say that the meeting started 46 minutes ago; on the other, it is ‘in 14 min’. Perhaps because of this temporal confusion, there is no way to join the meeting.

Finally, here is MS Teams at 16:00.

Nothing has changed, there is still no way to join the meeting.

Update. Apparently one of my errors was to schedule a meeting with no invitees. Under Microsoft’s interpretation, such meetings may be scheduled, but never attended (even by gate-crashing). On the time-zone front, both the Outlook web calendar and MS Teams continue to insist that London is on UTC+00:00, but, bizarrely, choosing London as my location (it already was) fixed the scheduling bug. In the Outlook example I invited myself, but still there was no link.

Many thanks to Remi from the Royal Holloway IT support team for steering me on an expert course around the shark-invested waters of Microsoft software.

Further update. The other day I accidentally scheduled a meeting using Microsoft Outlook (the application), taking care to include myself on the guestlist, and hit essentially the same bug. Here is me scheduling a test meeting.

and here are three screen shots as I frantically view the meeting in all the available applications, trying to find a way to join it. None is available.

The prosection rests its case. How can Microsoft justify releasing such inept pieces of software? Whatever top-secret protocol they are using, they can’t even speak it fluently between each other!