This blog post is based on joint work with Tom Johnston and James Aaronson. A talk on this is also available on video.
Suppose a group of mathematicians need to decide between two different coffee machines for the department.
Option A Option B
We ask them to raise their hand if they prefer option A, and record the subset of that raised their hand. For each such subset, we specify whether option A wins or loses. This gives a collection
of winning coalitions. Their are a few very natural assumptions for a ‘fair’ way of deciding who won:
- If more people vote for option A, then option A is more likely to win. In combinatorics terms,
is an upset.
- Option A and B have an equal probability of winning. That is,
.
So far what we have defined is equivalent to a maximal intersecting family. We will add one more assumption which is modelled in a way which is perhaps a bit less natural. The automorphism group Aut() of our set system
is the set of bijections
for which
for all
. We call
symmetric if the action of its automorphism group is transitive, that is, for all
, there exists a
Aut(
) with
.
-
All voters are treated equally.
Our set system
is symmetric.
Such a fair game or symmetric maximal intersecting family need not exist. It is easy to find one for odd: indeed, we can use the voting rule most often used in practice called the majority rule, for which
. However, the existence for even
is far from understood. Isbell proved the following result in his first Homogenous Games paper.
Lemma (Isbell) Let
. The following statements are equivalent.
- There exists a maximal intersecting family on
that is symmetric.
- There exists a transitive subgroup
of
for which every
has at least one odd cycle.
- There exists a transitive subgroup
of
for which every 2-power-order element
has a fixed point
(that is,
).
Isbell conjectured in 1960 that there is a finite bound for each odd
such that no symmetric maximal intersecting family exists for
for all
. Peter Cameron was interested in this problem, and introduced cyclically covering subspaces (the topic of our paper, defined further below). He noticed that a small cyclically covering subspace in
(say codimension
), can be used to construct a large symmetric maximal intersecting family (say for
). (This connection that
is explained in detail by Cameron, Ellis and Raynaud.)
Let denote the cyclic shift, e.g.
and
.
Definition A cyclically covering subpace
is a linear subspace with the property that for all
, there exists a shift
for which
.
It is easy to construct such a subspace: we can always take . It is also clear the subspace cannot be too small, e.g. the all ones and all zeros vectors always need to be a part of
. How small can such a cyclically covering subspace be (given
)? Define
as the largest codimension (
minus dimension) of a cyclically covering subspace in
. More than 25 years ago, Peter Cameron posed the question whether
as
over the odd integers (see Problem 190, and his blog that we are proud to be mentioned on). The main result of our paper answers this question negatively (conditional on Artin’s conjecture).
Theorem (Aaronson, G., Johnston) If
is a prime for which the polynomial
is irreducible over
, then
.
There are infinitely many such primes if Artin’s conjecture is true. Artin conjectured in 1927 a precise density for such primes among the primes, which seems about correct for the primes below 300.000, as can be seen below.

The first couple of Artin primes have their own OEIS sequence.
The proof of our result is quite long. Some of the main steps we take are:
- We reformulate the problem by switching to the orthogonal complement: it suffices to prove that there are no linearly independent
such that the orthogonal complement of these is cyclically covering.
- We show we may assume that
. This is the only step where we use our assumption that
is irreducible, through the fact that
splits into the sum of two fields
. Letting a vector
correspond to the polynomial
, shifting corresponds to multiplying by
. This reformulation was introduced by by Cameron, Ellis and Raynaud, who use algebraic arguments to prove several bounds on
.
- We say a vector is symmetric if
and
. E.g.
is symmetric and
is not. We show, for any prime
, that
cannot ‘work together’ with two additional vector
if either is symmetric.
- We then try to show our conjecture that there is no non-symmetric vector
such that the orthogonal complement of
is a cyclically covering subspace of codimension 2. For this we reformulate into Cayley graphs, giving the equivalent statement of our conjecture below.
- For primes
, by studying additive properties of the set
of
for which
, we try to reduce our conjecture to the case in which
is contained in a small arithmetic progression (which we can handle). We are able to do this whenever the Cayley graph we constructed has no directed cycles of length 4 or 6. Whenever this is not the case, we fail to prove our conjecture, but with some additional case analysis work we show there can’t be an additional
, which suffices for our theorem.
Conjecture Let
be an odd integer which is not divisible by 7 and let
be a Cayley digraph on vertex set
. Then
has no odd-sized induced subgraph with all outdegrees odd if and only if
is a graph.
A Cayley digraph on vertex set is a directed graph where a fixed subset
of
specifies the arcs:
if and only if
. This is a graph if and only if
is symmetric, that is,
(no self-loops) and
(all edges are bidirectional).

One of the directions of our conjecture follows from the handshake lemma. We checked the other direction for all by computer search.
Cameron, Ellis and Raynaud also introduced the generalisation of to
for arbitrary prime powers
. Their problem of determining for which values of
we have
remains open. Several other interesting open problems can be found in our paper.