The combinatorial hierarchy

Following up a conversation with John Amson at Rufflets Hotel, just outside St Andrews, I was led to a paper on combinatorial physics:

Ted Bastin, H. Pierre Noyes, John Amson, Clive W. Kilmister: On the physical interpretation and the mathematical structure of the combinatorial hierarchy, International Journal of Theoretical Physics 18 (1979), 445–488; doi: 10.1007/BF00670503

Here is the abstract. See what you make of it.

The combinatorial hierarchy model for basic particle processes is based on elementary entities; any representation they may have is discrete and two-valued. We call them Schnurs to suggest their most fundamental aspect as concatenating strings. Consider a definite small number of them. Consider an elementary creation act as a result of which two different Schnurs generate a new Schnur which is again different. We speak of this process as a “discrimination.” By this process and by this process alone can the complexity of the universe be explored. By concatenations of this process we create more complex entities which are themselves Schnurs at a new level of complexity. Everything plays a dual role in which something comes in from the outside to interact, and also serves as a synopsis or concatenation of such a process. We thus incorporate the observation metaphysic at the start, rejecting Bohr’s reduction to the haptic language of common sense and classical physics. Since discriminations occur sequentially, our model is consistent with a “fixed past-uncertain future” philosophy of physics. We demonstrate that this model generates four hierarchical levels of rapidly increasing complexity. Concrete interpretation of the four levels of the hierarchy (with cardinals 3,7,127,2127-1∼1038) associates the three levels which map up and down with the three absolute conservation laws (charge, baryon number, lepton number) and the spin dichotomy. The first level represents +, −, and ± unit charge. The second has the quantum numbers of a baryon-antibaryon pair and associated charged meson (e.g.,n-n,p-n,p-p,n-p,π+0-). The third level associates this pair, now including four spin states as well as four charge states, with a neutral lepton-antilepton pair (e-e or v-v), each pair in four spin states (total, 64 states) – three charged spinless, three charged spin-1, and a neutral spin-1 mesons (15 states), and a neutral vector boson associated with the leptons; this gives 3+15+3×15=63 possible boson states, so a total correct count of 63+64=127 states. Something like SU2×SU3 and other indications of quark quantum numbers can occur as substructures at the fourth (unstable) level. Breaking into the (Bose) hierarchy by structures with the quantum numbers of a fermion, if this is an electron, allows us to understand Parker-Rhodes’ calculation of mp/me =1836.1515 in terms of our interpretation of the hierarchy. A slight extension gives us the usual static approximation to the binding energy of the hydrogen atom, α2mec2. We also show that the cosmological implications of the theory are in accord with current experience. We conclude that we have made a promising beginning in the physical interpretation of a theory which could eventually encompass all branches of physics.

My first reaction is something along these lines. Pythagoras is thought to have believed that “all is number”, and also to have believed in reincarnation. (Of course, we know nothing about what he really believed.) So perhaps these authors are channelling the spirit of Pythagoras.

Note also that Schnur is German for “string”, as claimed, but is also defined by the Urban Dictionary as “the ultimate insult that means absolutely nothing”. Interesting?

Actually reading the paper didn’t clear up all my doubts. The setting is sets of binary strings. A set of strings is called a discriminately closed subset if it consists of the non-zero elements in a subspace of the vector space of all strings of fixed length n. Such a subset has cardinality 2j−1, where j is its dimension. Now a step in the combinatorial hierarchy involves finding a set of 2j−1 matrices which are linearly independent and have the property that each of them fixes just one vector in the subset (I think this is right, but the wording in the paper is not completely clear to me). These matrices span a DCsS of dimension 2j−1 in the space of all strings of length n2.

Of course, the exponential function grows faster than the squaring function, so the hierarchy (starting from any given DCsS) is finite. Their most important example starts with j = n = 2 (two linearly independent vectors in {0,1}2 and their sum), and proceeds to j = 22−1 = 3, n = 22 = 4; then j = 23−1 = 7, n = 42 = 16; then j = 27−1 = 127, n = 162 = 256; then j = 2127−1 ∼ 1038, n = 2562 = 65536 (but this is impossible, so I am not sure what it means to continue the hierarchy to this point).

They point out that the numbers 127 and 2127−1 are close to, respectively, the fine structure constant and the ratio of strengths of electromagnetic to gravitational force between protons. If you use cumulative sums, you get 3, 10, 137 and a number which is again about 1038, and of course 137 is even closer to the target. But I am not sure why you should do this, and in any case, the fine structure constant is measureably different from 137. The non-existence of 1038 linearly independent matrices of order 256 supposedly has something to do with “weak decay processes”.

The paper contains some constructions of the appropriate hierarchies. One could pose the mathematical question: do the required linearly independent non-singular matrices exist for any n and j for which 2j−1 ≤ n2?

By this stage I was floundering, so I gave up my careful reading. I noted at a certain point a calculation of the ratio of proton mass to electron mass giving a value 137π/((3/14)×(1+(2/7)+(2/7)2)×4/5), agreeing with the experimental value to eight significant figures. (There are three terms in the geometric series because the hierarchy falls over at step 4.) Of course, putting in a more accurate value for the fine structure constant would make the agreement less good: the authors do attempt to explain this.

(If you are a mathematician looking at the paper, the mathematics is put in an appendix starting on page 480, so you can avoid the physics.)

At another point in the conversation, John told me that he ran with the fox and hunted with the hounds. On the strength of this, I can perhaps attribute to him a certain degree of scepticism about all this.

Posted in exposition | Tagged , , , , | Leave a comment

Orbital combinatorics

Yesterday I went to Edinburgh to give a colloquium talk about synchronization, including the recent stuff about butterflies. The day before, I had discussed Artur Schäfer’s work with him, and he expressed a hope that if he went to the Postgraduate Combinatorics Conference (at which I am speaking) I wouldn’t steal his topic! At the same time, I am preparing lectures to my year 5 class on counting graph colourings up to symmetry.

So in the morning as I lay half asleep, these ideas assembled themselves into a pattern. Maybe not a really significant pattern, but maybe worth something. It occurred to me that perhaps someone should write a book on this …

The prototype

Recently I wrote about the formulae for the number of ways of choosing a sample of k from a set of n objects:

  • Order significant: with replacement n^k, without replacement n(n-1)\cdots(n-k+1) (the falling factorial)
  • Order not significant: with replacement n+k-1\choose k, without replacement n\choose k

In my view this table illustrates the main division of combinatorics. This is perhaps clearest if we interpret the n objects as “colours”, and regard the task as counting colourings of a set of size k (which we can regard as a complete graph). The first formula is the simplest. Going right along a row, we impose a structural condition: the colouring should be proper (that is, the ends of an edge should get different colours). So the second entry in the first row is the chromatic polynomial of Kk, evaluated at n.

The second row is different: it counts the colourings up to symmetry. That is, it counts orbits of the symmetric group of degree k on the colourings of the two types described in the first row.

Structural combinatorics will take us from this example to graphs, matroids, and beyond. Symmetry seems only to lead to group actions and the resulting counting, but in fact it is much more widespread than that, as I want to discuss.

Orbital chromatic polynomial

It is not hard to extend the above analysis to any graph. The chromatic polynomial of a graph X is a monic polynomial whose degree is equal to the number of vertices of X; it is defined by the property that its evaluation at a positive integer q is equal to the number of q-colourings of X.

What corresponds to the second entry in the second row of our introductory example, when we impose both symmetry and structure (that is, count proper colourings up to symmetry)?

If G is a group of automorphisms of X, there is a polynomial, the orbital chromatic polynomial of X and G: its degree is equal to the number of vertices of X, and its leading coefficient is 1/|G|; its evaluation at a positive integer q is equal to the number of q-colourings up to the action of G, that is, the number of orbits of G on colourings.

To see this, we use the Orbit-counting Lemma, according to which the number of orbits is equal to the average number of fixed points of elements of G. So we have to count the colourings fixed by an automorphism g. Such colourings must be constant on the cycles of g. So, if there are two adjacent vertices in the same cycle, the number is 0. Otherwise, form a contracted graph X/g by shrinking each cycle to a vertex; there is a bijection between colourings of X fixed by g and colourings of X/g, so the required number is the chromatic polynomial of X/g evaluated at q.

Thus, the orbital chromatic polynomial is an average of terms each of which is zero or a chromatic polynomial; the chromatic polynomial of the whole graph appears once in this average. So the claimed result is true.

Koko Kayibi and I started an investigation of roots of orbital chromatic polynomials. There are some similarities, and some differences, with the theory of roots of chromatic polynomials.

A generalisation

In a paper with Bill Jackson and Jason Rudd, which I secretly regard as one of my best (though not many people seem to agree), we gave a far-reaching extension of the orbital chromatic polynomial.

This is in some sense inspired by two pieces of folklore, which are not quite what they seem:

  • Nowhere-zero flows in a graph (with values in a finite abelian group of order q) are “dual” to q-colourings.
  • The number of nowhere-zero flows depends only on the order of the abelian group, and not on its structure.

I wanted to understand these statements, and I believe that the orbital versions given in the paper throw some light on this.

In the case of the first statement, nowhere-zero flows (or 1-coboundaries) are really dual to nowhere-zero tensions (or 1-boundaries). A tension on X with values in an abelian group A is a function on the (oriented) edges with the property that the (signed) sum round any cycle is zero. Thus, such a function is derived from a “potential” function on vertices, so that the value on an edge is the difference of the values at its head and its tail. The tension is nowhere-zero if and only if the potential takes different values on adjacent vertices, in other words, is a q-colouring of the graph. So the numbers of colourings and nowhere-zero tensions are equal (up to a simple normalising factor qc, where c is the number of components). But this is no longer true if we count orbits of an automorphism group.

The second statement is not really folklore, it is a theorem of Tutte. But the same comment applies. The number of orbits of an automorphism group on nowhere-zero flows with values on an abelian group A does depend on the structure of A, and can be expressed as the evaluation of a polynomial which has a variable for each element order in A; the required substitution for this variable is the number of elements of that order. But a variable only occurs in the polynomial if the corresponding order divides the order of the automorphism group G. So, if G is trivial, the structure of A has no effect.

By phrasing the result in the paper in terms of matrices over principal ideal domains, we were able to give a general theorem which specialises not only to nowhere-zero flows and tensions in graphs, but also to weight enumerators of codes.

One final point on this. The nowhere-zero condition is enforced by an inclusion-exclusion argument over subgraphs of the graph. This indicates a general phenomenon: an evaluation of the Tutte polynomial with one of the variables equal to −1 often is equivalent to an inclusion-exclusion argument!

Another generalisation

I have discussed before the connection between transformation monoids and graphs. There are constructions of each type of object from the other, which are not functorial but carry a lot of structural information.

Now transformation monoids, and in particular endomorphism monoids of graphs, are closely connected with a lot of important combinatorics.

This is obscured by the fact that most graphs are cores: they have no proper endomorphisms. But there are many interesting graphs. I will describe here one particular family, but there are many other instances.

The square lattice graph L2(n) has as vertex set the cells of an n×n array; two vertices in the same row or column are joined.

This graph is a pseudocore: it has clique number equal to chromatic number, and all its proper endomorphisms are colourings which take values in a maximum clique.

Now the n-cliques are easy to understand: they are just the rows and columns of the array. But the n-colourings are much more interesting: they are the Latin squares of order n:

Latin square colouring a grid

So we have a transformation monoid whose elements are pairs consisting of a Latin square and a row or column of the corresponding array.

So even finding the order of this monoid requires the classification of Latin squares, which has only been achieved for n ≤ 11 (see here andhere).

At first, when I realised this, I was excited at the thought that Latin squares could be composed. But, of course, the way the composition works, any product is equal to its leftmost factor (up to some renormalisation), so the algebraic structure is not so interesting.

The monoid may not be interesting in its own right. But here is a case where a very important classification in semigroup theory (the J-classes, equivalence classes for Green’s relation J) coincide with an important classification of Latin squares. Two Latin squares are equivalent in this sense if they differ by permuting rows, columns and symbols, and possibly transposing rows and columns. So the equivalence classes lie between isotopy classes and main classes.

In terms of the Green’s relations, the L-classes (corresponding to multiplying by automorphisms on the left) correspond to permuting rows and columns and/or transposing; the R-classes (corresponding to multiplying on the right) correspond to permuting the entries of the square.

There are several other examples where interesting combinatorial structures and their classification problems correspond to computing the endomorphisms of a pseudocore.

For some of our recently-discovered graphs, inspired by the butterfly, things are much more complicated, and the semigroups have a rich structure which we have only begun to explore. Almost certainly there is interesting combinatorics to be discovered, but what will it be?

Posted in exposition | Tagged , , , , , , , , , , | 1 Comment

Red sky at night …

Red sky

… is, if not a shepherd’s, at least a walker’s delight:

Sunny pond

Posted in geography | Tagged , | Leave a comment


Apocalypse on Charles Bridge

February’s picture, called “Apocalypse on Charles Bridge”, is a composite: the silhouettes are figures from the famous Charles Bridge in Prague; the sky behind is over St Andrews, the picture was taken from just outside my front door.

Charles Bridge is on the natural route from the Old Town Square to the castle, and also on the route from the Karolinum to the former Jesuit college which now houses the Applied Mathematics department. But it is so crowded these days that often when I have to go between the last two places I prefer to detour over one of the adjacent bridges.

Posted in geography | Tagged , | Leave a comment

From M12 to M24

On 20 January 2015, Paul Hjelmstad posted the following question on the GAP forum:

Is there an easy way to generate a Steiner system S(5,8,24) for the Mathieu Group M24, if a Steiner system S(5,6,12) for the Mathieu Group M12 is known?

I learned about the Mathieu groups when I was a student. I read Heinz Lüneburg’s book Transitive Erweiterungen endlicher Permutationsgruppen in the Springer Lecture Notes series, in which he constructed the Steiner system (and group) by extending three times the projective plane of order 4.

But, at about the same time, I attended a remarkable series of lectures by Graham Higman. In these lectures, he constructed the outer automorphism of the symmetric group S6, and used it to construct and prove the uniqueness of the projective plane of order 4, the Moore graph of valency 7, and the Steiner system S(5,6,12), and hence deduce properties of their automorphism groups. He then gave an analogue of the “doubling” construction from S6 to M12, starting with M12, constructing its outer automorphism, and using this to build M24 and its Steiner system.

I don’t think he published any of this, and I doubt whether any notes are now available. I used the first part of the material in chapter 6 of my book Designs, Graphs, Codes, and their Links with Jack van Lint. The outer automorphism of S6 is described here.

So I have written out a description of the path from the small to the large Mathieu group, and put a copy here with my lecture notes. This document could be regarded as a supplement to Chapter 6 of my book with Jack. It may be of interest to someone else; let me know if you find it so.

Posted in exposition | Tagged , , , , , | Leave a comment

Ramon Llull

Last Saturday the Guardian had a review of The Serpent Papers by Jessica Cornwell (granddaughter of John Le Carré). Set in Barcelona and Mallorca, the book is a murder mystery and more; its presiding genius is Ramon Llull, the mediaeval Mallorcan who was described by Donald Knuth as “an energetic and quixotic Catalan poet, novelist, encyclopedist, educator, mystic and missionary” (in his article “Two thousand years of combinatorics” in Combinatorics Ancient and Modern).

If you read The Da Vinci Code, you may remember the absurd claim by Dan Brown that public-key cryptography was invented by Leonardo Da Vinci. Well, in Gwyneth Jones’ review of The Serpent Papers, she almost claims that Ramon Llull invented programming languages! She actually describes Llull’s Ars Magna as “a form of algebraic logic expressed in complex diagrams (an ancient forerunner of all programming languages, by the way)”. I haven’t read the book, so I don’t know whether this notion is in it or not.

So I checked on Wikipedia, and found this: “Some computer scientists have adopted Llull as a sort of founding father, claiming that his system of logic was the beginning of information science,” an altogether more modest claim.

So what did Llull do? This is how it seems to me, but I disclaim any expertise on Llull. He was interested in combinatorics, without a doubt. Knuth describes a chapter of his Ars Compendiosa Inveniendi Veritatem which begins by enumerating sixteen attributes of God: goodness, greatness, eternity, power, wisdom, love, virtue, truth, glory, perfection, justice, generosity, mercy, humility, sovereignty, and patience. Then Llull takes each of the 120 combinations of two of these attributes, and writes a short essay on their relationship.

There is much more along the same lines in Llull’s extensive writing. But, perhaps more significantly, he invented mechanical gadgetry for generating all the combinations. His works are full of beautiful diagrams of complete graphs, rotating discs, and so forth.

He seems to have believed that any moral question could be settled by analysis of all possible combinations of attributes, virtues and vices, etc. I am not quite sure how. Neither am I sure where the logic or computer programming comes in.

There was much more to Llull than this. Before his conversion, he was a secular writer and troubador; he wrote the first novel in Catalan (which is possibly the first European novel). Afterwards he set out to convince Jews and Muslims of the truth of Christianity by rational argument (a hopeless quest, you might think – but he always believed in discussion rather than violence). His works also include Latin squares.

I will leave the last word to Jorge Luis Borges:

At the end of the thirteenth century, Raymond Lully was prepared to solve all arcana by means of an apparatus of concentric, revolving disks of different sizes, divided into sectors with Latin words; John Stuart Mill, at the beginning of the nineteenth, feared that some day the number of musical combinations would be exhausted and there would be no place in the future for indefinite Webers and Mozarts; Kurd Lasswitz, at the end of the nineteenth, toyed with the staggering fantasy of a universal library which would register all the variations of the twenty-odd orthographical symbols, in other words, all that it is given to express in all languages. Lully’s machine, Mill’s fear and Lasswitz’s chaotic library can be the subject of jokes, but they exaggerate a propensity which is common: making metaphysics and the arts into a kind of play with combinations.

Posted in mathematics and ... | Tagged , , , , , , , , , | 2 Comments

Chains of semigroups

I have written here about the lovely formula for the length of the longest chain of subgroups in the symmetric group Sn: take n, increase it by 50% (rounding up if necessary), subtract the number of ones in the base 2 representation of n, and subtract another 1, to get the answer.

Last year, James Mitchell and I, talking about possible projects, wondered whether we could get a similar nice formula for the length of the longest chain of sub-semigroups in the full transformation semigroup Tn.

We didn’t succeed in getting a formula. But soon after that, Max Gadouleau came to visit, and got interested; he came up with a method which produces long chains.

Briefly, it goes like this. We look for a long chain among the semigroup of transformations of given rank m (with an added zero, so that if the product of two maps has rank less than m, we re-define it to be zero). Now in a zero semigroup (one with all products zero), any subset is a semigroup, so there is a chain of length one less than the order of the semigroup. So the trick is to find large zero semigroups.

This is done as follows. A map of rank m has an image (a subset of size m) and a kernel (a partition with m parts); the product fg will have rank less than m (so be zero in our semigroup) if and only if the image of f is not a transversal for the kernel of g. So we need a large collection of m-sets and a large collection of m-partitions such that no subset is a transversal for any of the partitions. Max invented the term league for this combinatorial object; the content of a league is the product of the numbers of subsets and partitions.

By finding leagues with large content, we were able to show that the longest chain of sub-semigroups of Tn has length at least a positive fraction 1/e2 of the whole semigroup. (A sharp contrast with groups, where the length of a subgroup chain is bounded by the logarithm with the group order.)

At this point the investigation broadened, and involved James’ former student Yann Peresse, as we tried our hand at various other semigroups. In some cases we were able to find exact results (either as an explicit formula, or in terms of the length of various groups involved). These cases include the inverse semigroup In of partial 1–1 maps on an n-set, another close analogue of the symmetric group.

Our paper has just appeared on the arXiv.

Posted in exposition, open problems, symmetric group | Tagged , , , , , , | 2 Comments