Reducts and Reed-Muller codes

While I was in Adelaide, supposedly on holiday, Csaba Szabó sent me a preprint of a paper he had written with his student Bertalan Bodor. I read it with interest, and was able to make a small remark on the paper.

This was especially pleasing to me. It represented the first original mathematical thought I have had since the bout of shingles, and it is also something I like best: an unexpected connection between two different areas.

The paper has just gone on the arXiv.

Countably categorical structures and oligomorphic groups

A first-order structure M (a set with specified relations, functions and constants) of countable cardinality is countably categorical if any countable structure over the same language which satisfies the same first-order sentences as M is isomorphic to M. A classical example is the rational numbers (as ordered set): by Cantor’s theorem it is the unique countable dense total order without endpoints. Another is the random graph, which I may have mentioned once or twice …

A permutation group G acting on a set X is oligomorphic if it has only finitely many orbits on Xn for every natural number n.

One of my favourite “connection” theorems, due to Engeler, Ryll-Nardzewski and Svenonius (independently) in 1959, can be stated like this:

Theorem A countable structure is countably categorical if and only if its automorphism group is oligomorphic.

Note that the automorphism group of a first-order structure is closed in the symmetric group, in the topology of pointwise convergence. The closure of a group G is the largest group having the same orbits as G on n-tuples for all n.

One source of such objects is homogeneous structures. A relational structure M is homogeneous if any isomorphism between finite induced substructures of M can be extended to an automorphism of M. Now the automorphism group of a homogeneous relational structure over a finite relational language is oligomorphic: indeed, the number of orbits on Xn is bounded by the exponential of a polynomial in n. (A k-ary relation has at most 2nk restrictions to an n-element set. Multiplying together finitely many expressions of this form gives the exponential of a polynomial in n as an upper bound for the number of n-element structures up to isomorphism, and so by homogeneity the number of orbits of the automorphism group on n-tuples.)

On the other hand, the growth rate for the number of orbits on n-tuples of oligomorphic groups has no upper bound. (Also, any closed permutation group is the automorphism group of some homogeneous relational structure, usually over an infinite language.)

You might hope, then, that we can distinguish homogeneous structures over finite relational languages from arbitrary countably categorical structures by the slow growth of the orbit-counting function.

However, this is not the case. Consider a vector space of countable dimension over the 2-element field. The number of orbits on n-tuples is roughly the exponential of a quadratic. On the other hand, the structure is not homogeneous over a finite relational language. For, given any k, there is a linearly independent k-set, and a k-set for which every (k−1)-subset is linearly dependent but the sum of all the elements is 0. These two k-tuples lie in different orbits, but cannot be distinguished by a relation of arity less than k. So infinitely many relations are required.

Finding properties which distinguish homogeneous structures over finite languages among countably categorical structures appears to be a very hard problem!

Reducts

A reduct of a structure M is a structure N (on the same set, but using a different first-order language) such that the operations and relations on N can be defined in terms of those of M by first-order formulae without parameters. It is proper if M is not a reduct of N.

It follows from the theorem quoted above that proper reducts of the countably categorical structure M correspond to closed overgroups of Aut(M) in the symmetric group.

The first classification of such reducts is attributed to me, though when I proved it I knew nothing about reducts and little about first-order logic. There are five reducts of the ordered set of rationals, corresponding to the order, the betweenness relation, the derived circular order, the separation relation from the circular order, and the trivial reduct (a set with no structure, whose group is the symmetric group). Simon Thomas found the reducts of the random graph; these have the same pattern (the graph itself, up to complementation, up to Seidel switching, up to switching and/or complementation, and the trivial reduct).

This and other examples led Simon to conjecture that a homogeneous structure over a finite relational language has only finitely many reducts. Many special cases of the conjecture has been proved, but the proofs become increasingly difficult, and no general result is known.

What if we step a little further, and ask about countably categorical structures over a finite relational language whose orbit-counting function grows no faster than the exponential of a polynomial?

This is the question which was answered by Bertalan Bodor and Csaba Szabó in a preprint they sent me in late August. Such a structure may have infinitely many reducts!

I will outline the proof below.

Reed–Muller codes

Reed–Muller codes were invented in the 1950s. Although they are not the best codes known, they have such a beautiful structure that both coding theorists and mathematicians keep returning to them.

A linear code of length N over the field F with two elements is a subspace of the vector space FN. (Note that this vector space comes with a fixed basis, so a vector has a weight, the number of non-zero entries. Coding theorists are concerned to find codes with large minimum weight and large dimension; of course, these two properties conflict, so compromises must be made.)

For the Reed–Muller codes, we take N = 2n, and regard vectors as functions from V to F, where V is an n-dimensional vector space over F.

Now the kth order Reed–Muller code RM(k,n) can be defined in two different ways:

  • it is the set of functions represented by polynomials of degree at most k in the coordinates;
  • it is the span of the characteristic functions of subspaces of dimension nk or greater.

Standard facts about these codes include the fact that these two definitions are equivalent, that the dual code of RM(k,n) is RM(nk−1,n), and formulae for the dimension and minimum weight of RM(k,n). I will use an infinite analogue of the first description to construct the reducts, but the second description and the orthogonality will be used to verify their properties. The principle can be expressed as follows: a function on V is represented by a polynomial of degree at most k if and only if it is orthogonal to the characteristic function of every (k+1)-dimensional space.

The construction

Let V be a vector space over the 2-element field F and c a non-zero vector in V. I will show that the subgroup of (GL(V) fixing c has an infinite ascending chain of overgroups.

Let V = V/⟨c⟩. The stabiliser of c in GL(V) is a semidirect product of W by GL(V), where W is the additive group of the dual space of V (the space of linear functions from V to F).

We let Wk be the space of all functions from V to F represented by “polynomials” of degree at most k. (The polynomials are allowed to involve infinitely many monomials; note that a vector in V has only finitely many non-zero coordinates, so the evaluation makes sense. In particular, W1 = WF, the space of functions which are “linear plus constant”.) Clearly the spaces Wk form a strictly increasing sequence, each of which is invariant under GL(V). (The strictly increasing property can be seen because a product of k distinct indeterminates cannot be represented as a polynomial of degree less than k, or alternatively by using the orthogonality property of the next paragraph.) These are “infinite Reed–Muller codes”.

It suffices now to show that they are closed, in the topology of pointwise convergence. For this we observe that a function belongs to Wk if and only if it is orthogonal to the characteristic function of every (k+1)-dimensional subspace. (The standard inner product is not defined on the space of functions on V, but we can compute the inner product of an arbitrary function and a function of finite support.) Now if we have a sequence of functions which converges, then its restriction to every (k+1)-dimensional subspace is ultimately constant, and so the limit function is also orthogonal to every such subspace, and hence lies in Wk.

This observation can also be used to construct a relation invariant under the semidirect product of Wk with GL(V).

A final problem

Problem: Describe all the reducts of the pointed vector space of countable dimension over the 2-element field.

For each of the reducts above, there is another (with group half as large) where we are not allowed to interchange the zero vector with the vector c (The non-zero constant function in Wk swaps the two vectors in each coset of ⟨c⟩.)

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

Perth, week 2

Rottnest birds

The second week in Perth is over. Yesterday we went to Rottnest Island, named by the Dutch sea captain Vlaminck (“rats’ nest”) who mistook the quokkas for large rats; it is Wadjemup in the local Noongar language, and Rotto informally. It is an extraordinary place for birds. The picture shows a black-winged stilt (with what might be a plover of some sort behind), a pelican, baby oystercatchers, and a crested tern. And of course there were more quokkas than you could shake a stick at:

Quokka

This one is a bit unusual; they are mostly very tame, especially round the settlement, but the first two we saw ran into the bushes to hide from us.

On Friday I gave a seminar on “Idempotent generation and road closures”; fortuitously, an email came round warning of further road closures in St Andrews that very day, and I was able to include it in my slides.

Without going into the connection with road closures, the question is: for which transitive permutation groups G is it true that, if O is an orbit of G on 2-subsets of the domain of G, and B a maximal block of imprimitivity for G acting on O, then the graph with edge set O\B is connected?

We know that such a group must be primitive, and must be basic (that is, preserves no Cartesian power structure on its domain). Moreover, João Araújo and I conjecture that, if G is a basic primitive permutation group such that G has no imprimitive subgroup of index 2 and also is not one of a class of examples related to the phenomenon of triality, then G has our “road closure” property.

Since I have been here, Cheryl Praeger and I have thought about one case of this problem, and have been thinking more generally about removing edges from a vertex-transitive graph to disconnect it.

Classical results of Mader and others assert that, if Γ is a vertex-transitive graph of valency k, then the edge-connectivity of Γ is k; this means that removing fewer than k edges do not disconnect the graph. Clearly it can be disconnected by removing the k edges through a vertex, to isolate that vertex. But the argument gives a little bit more. A set of k edges whose removal disconnects the graph must be either the edges through a vertex, or the k edges each with one end in a complete subgraph of size k. (Graphs with this property can be obtained from arc-transitive graphs by replacing each vertex with a clique of size k, each of whose vertices is on one of the edges through the original vertex.)

The second kind of disconnecting set cannot arise in an edge-transitive graph except for a cycle (with k=2) or a complete graph of size k+1, since in general the edges in the clique cannot be equivalent to the other edges under an automorphism.

The proof of this uses the concept of an atom. The boundary of a set of vertices is the set of edges having one end in that set; an atom is a set A of vertices whose boundary is minimal, and subject to that the size of A is minimal.

Cheryl went on to look at “pseudo-atoms”, sets of vertices whose boundary is minimal subject to being greater than k, and subject to this the size of the set is minimal. I will just say that if we add in the condition of edge-transitivity then such a set must be a single edge, with boundary of size 2k−2.

This already gives some information on the road-closure problem, and I hope we will have more progress to report soon. But Cheryl is off for a week in London and Paris on mathematics business …

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

Resources pages going down

At Queen Mary, I used to maintain two pages with links to resources, one for permutation groups, the other for designs. (The latter is quite separate from the DesignTheory.org website.)

These pages have not been maintained for a long time now, and I am sure that many of the links no longer work. But maintaining the pages is not just a case of bringing the links up to date (and deleting those which don’t work), but more importantly would require me to scour the web for new links to add.

I have always thought that a carefully curated page may be more useful than the result of a Google search, but the margin is becoming smaller. So reluctantly I have decided to remove these pages.

They will go at the end of this year. Please let me know if you have any comments or suggestions before then.

Posted in the Web | Tagged , , | 3 Comments

Priority

The arXiv has made it easier to settle questions of priority, since all papers are date-stamped.

However, it hasn’t made the problems go away. See

https://pubpeer.com/publications/90BA3090D680D06326E43EC08CDEE8

for a depressing story.

Will this kind of thing push us to a situation where incomplete papers are posted on the arXiv just so as to claim priority? That would not be in anyone’s interest. But how to deal with the question otherwise?

Posted in publishing | Tagged | 7 Comments

Generational equivalence

If you are interested in generating sets for finite groups, you may want to read this. I started this work with Colva Roney-Dougal some time ago, and I talked about it in Budapest last summer. Andrea Lucchini was in the audience, got interested, and added many new results, so we recruited him to the team; but it has still taken us rather a long time to finish the paper. It has just gone on the arXiv.

Let us say that two elements of a finite group G are m-equivalent if one can be substituted for the other in any generating set for G without destroying the generating property. The “m” here stands for maximal subgroups, since two elements are m-equivalent if and only if they lie in the same maximal subgroups of G. In particular, the m-equivalence class of the identity is the Frattini subgroup, the set of non-generators. (This way of viewing m-equivalence leads to the best algorithm we know for computing it.)

The number of m-equivalence classes is an interesting invariant of the group G. We computed it for the first few symmetric groups, and this is now sequence A270534 in the On-Line Encyclopedia of Integer Sequences. The asymptotic behaviour of this sequence is an unknown problem, on which we make some comments in the paper.

But m-equivalence can be refined. Let us say that two elements are m-equivalent at level i if one can be substituted for the other in any i-element generating set. These equivalence relations, indexed by i, get finer as i increases. What can we say about their behaviour?

The number of level-i equivalence classes is 1 if i < d(G), the smallest number of generators for G, and is strictly greater than 1 if i = d(G). It is easy to see that, for i = d(G), the identity and all the elements of the generating set are pairwise inequivalent, so the number of equivalence classes jumps from 1 to at least d(G)+1. It might be interesting to find a good lower bound.

Another significant point is the value of i where the equivalence relation reaches its final value; we call this number ψ(G). Now one of the most interesting and surprising questions we have come up with, and not been able to answer, is:

Is it true that ψ(G) ≤ d(G)+1?

We have no counterexamples to this, and it follows from a result of Burness, Liebeck and Shalev that ψ(G) ≤ d(G)+5. If the answer to the above question is “yes”, then the number of equivalance classes takes at most three distinct values for any given group. This would also yield a remarkable dichotomy for finite groups, into those with ψ(G) = d(G), and those with ψ(G) = d(G)+1. Is there a more obvious property distinguishing the two types?

There are also connections with the generating graph. If d(G) ≤ 2, we can form a graph with vertex set G, where two vertices are joined if these two elements generate the group. Our research began from the observation that the automorphism group of the generating graph is huge (for the alternating group A5, it has order 23482733690880). The reason is that any permutation which preserves the level-2 m-equivalence classes is an automorphism of the graph: two vertices in the same class have the same neighbours in the graph. In the paper we define a reduction process to a weighted graph whose automorphism group (at least in the case of almost simple groups) appears to be close to the automorphism group of G; the automorphism group of the full generating graph is the semi-direct product of a direct product of symmetric groups (on the level-2 m-equivalence classes) by the automorphism group of the weighted reduced graph, and the latter is equal to the automorphism group of G in many cases (though by no means all).

The vertex weight here is simply the cardinality of the equivalence class which is shrunk to give that vertex. An interesting question is to find examples where the reduced graph has automorphisms not preserving the weighting: we have a couple of examples, but the phenomenon is rare.

So there are several good problems to tackle here. Would you like to join in?

Posted in exposition | Tagged , | 1 Comment

Bad news from Leicester

Last week the news came round that the University of Leicester is forcing most of the mathematics departments to resign their posts and re-apply for them, with a quarter of them to be made redundant and many of the rest moved to teaching-only contracts. The reason given is a budget deficit which is thought to be temporary and caused by a drop in overseas students (not surprising in these troubled times); no-one has suggested that the long-term future of the University is in trouble.

If you don’t need to read any more but simply to sign a petition, here is the link:

http://speakout.web.ucu.org.uk/no-cuts-no-confidence-at-university-of-leicester/

A few points occur to me.

  • There is more damage being inflicted than just the death of the mathematics department: but I can most effectively support what I know about.
  • There are, surprisingly, a few universities where this process has been applied to administrative staff rather than academics, though this is not at all usual. In this case, one might say that a budget deficit is the responsibility of the finance department and/or senior management, so they should take the cuts, not the mathematics department.
  • There is plenty of evidence of the deep commitment of academic staff to the university and its students. Consider the extra hours we work when necessary (setting or marking exams, writing grant applications, and so on), while the administration almost without exception work a 9 to 5 day (and there is evidence that they are under the impression that we do the same).
  • It is easy to destroy a mathematics department, much harder to re-create one. And a mathematics department is very important to a university. I will not forget in a hurry an incident that occurred when I was on a committee considering whether or not to kill off the mathematics department in a certain university. The head of another department was being interviewed by the committee. Before he could be asked any questions, he said, “I would just like to say that I couldn’t hold up my head if I were in a university without a mathematics department”. This was perhaps the turning point, since it was a point of view that the administration had clearly not considered.

So here is that petition again:

http://speakout.web.ucu.org.uk/no-cuts-no-confidence-at-university-of-leicester/

Posted in maybe politics | Tagged , , | 1 Comment

Yanchep National Park

Yanchep fauna

Yesterday we visited Yanchep National Park, north of Perth. I went there on my first visit to Perth in 1966 (when I played golf for the first and last time in my life – I was not very good at it!), and so I was looking forward to the chance to go back.

We were provided with maps by a friend, and had figured out that we could get there by public transport: bus into Perth, train to Butler, then another bus, which would leave us by the side of a busy road a few kilometres from the park. It turned out that there was no footpath beside the road, so we simply had to take our chances. A park employee later told us that the local public transport authority has no interest in providing transport to “tourist attractions”, and despite having been asked often to extend the bus route the short distance into the park, has refused to do so. How stupid is that?

Anyway, we walked by the side of the road, and finally reached a point where a path (part of several marked trails) passed adjacent to the road. So with a sigh of relief we took the path and had a wonderful walk. At the end, a park official berated us for not obeying the rules, which require you to fill in and sign a form before you set out on a trail (just in case the park catches fire!) Of course we hadn’t seen the rules. They are not on the map; if you come by car you will probably see them, but it seems people are not supposed to arrive at a national park on their own feet!

The trail we followed was the Ghost House Walk Trail, a circuit of about 12.4km. All that is left of the Ghost House is a doorway, but the path itself went through extremely varied terrain with a great variety of plant life including many lovely wildflowers. Since I posted some Kings Park wildflowers last week, I thought I would concentrate on animal (including bird and insect) life this week. As well as these, we saw many other birds including ringneck parrots, cockatoos, galahs, crows, willy wagtails, and Pacific black ducks.

As a final nod to Nicolas Baudin, the cockatoos we saw were probably Baudin’s black-cockatoo, though they may have been Carnaby’s.

See Yanchep while you can. A block of land right next to the park has been bought by a developer; the whole area is being bulldozed and turned into Perth suburbs, and no doubt it won’t be long before Yanchep is reduced to an isolated urban green space. (Of course it may be easier to reach by public transport then!)

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