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!


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⟩.)


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , . Bookmark the permalink.

2 Responses to Reducts and Reed-Muller codes

  1. dockie73 says:

    I’m a bit puzzled now: from it appears that you succeeded in refuting the Simon Thomas conjecture. But this doesn’t seem to transpire from the current blog post. What am I missing?

    • Simon Thomas’ conjecture refers only to homogeneous structures over finite relational language. The pointed vector space certainly has a finite language, but as I point out, it cannot be made homogeneous over any finite relational language, since for any n there are two n-element structures which are different but whose (n-1)-element structures are all equivalent.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s