Suppose a group of mathematicians need to decide between two different coffee machines for the department.
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.