Fair games and Artin’s conjecture

A few years ago I described Persi Diaconis’ response to G. H. Hardy’s claim that there is a real dividing line between real and recreational mathematics. (See the report here.) This led from Persi’s first experiments in card shuffling to Artin’s conjecture on primitive roots modulo a prime and on beyond that to the generalised Riemann hypothesis.

I am pleased to be able to report another application of Artin’s conjecture, or at least of the special case of Artin’s conjecture which asserts that there are infinitely many prime numbers p such that 2 is a primitive root mod p (that is, the multiplicative order of 2 in the integers mod p is p−1.

It is pleasant to report that the same end point can be reached from an entirely different start, in game theory (which, despite its title, has some claim to be regarded as “real mathematics” itself). The context is n-player simple games in the sense of von Neumann and Morgenstern, those where the structure of the game is determined completely by knowledge of the winning coalitions, those sets of players which by cooperating can completely defeat their opponents. Obviously a superset of a winning coalition is a winning coalition, and the complement of a winning coalition is a “losing coalition”.

Isbell had the idea that, to ensure the game is fair, we could require a group of automorphisms of the up-set of winning coalitions which acts transitively on the set of players. For which n does such a fair game exist? Isbell showed that it was necessary and sufficient that there exists a transitive permutation group on the set of n players which contains no fixed-point-free element of 2-power order. For, if such an element exists, then it maps some subset to its complement, and so cannot preserve a simple game. Conversely, if there is a group containing no such element, the subsets of size n/2 fall into complementary orbits; choosing one of each pair to be winning coalitions, together with all sets of size larger than n/2, gives a fair simple game.

Isbell conjectured that, if the 2-part of n is sufficiently large compared to the odd part, then any transitive permutation group of degree n should contain a fixed-point-free 2-element, and hence no fair game on n players can exist. This conjecture is still unproven well over 50 years later, and is one of the conjectures I would most like to see resolved.

Any transitive group of 2-power degree contains a fixed-point-free 2-element (choose an element in the centre of a Sylow 2-subgroup). For a simple example, take n = 4. It is readily checked that there are two types of winning coalitions of two players: all those containing a fixed player A, or all those not containing a fixed player Z. Clearly A or Z plays a special role in this case; players are not all alike.

In investigating this conjecture, I was led to the following problem (you can ponder the exact link if you like, but it is not immediately relevant to what follows). Suppose that n is odd. Let V be the vector space of all n-tuples over the 2-element field F. What is the largest codimension of a subgroup W of V with the property that the cyclic shifts of W cover V?

It is not hard to see that we lose nothing by replacing V by its codimension-1 subspace consisting of all vectors containing an even number of ones. In this case, if n is greater than 3, there is always a subspace of codimension at least 2 which is cyclically covering. For any vector in this space has an odd number of zeros, and hence a run of zeros of odd length, and so contains a run 000 or 101; thus some cyclic shift of it lies in the subspace defined by the equations x1 = x3, x2 = 0. I wondered whether the maximum codimension tends to infinity with n, or whether the value 2 is attained infinitely often.

I posed this problem some time ago at the British Combinatorial Conference. Nothing happened until very recently, but now there are two preprints on it available. David Ellis and his student William Raynaud generalised it considerably, replacing F by an arbitrary finite field, n by an arbitrary integer, and the cyclic shift by an arbitrary transitive group. See arXiv 1810.03485.

But I really want to draw attention to a different paper, by James Aaronson, Carla Groenland and Tom Johnston from Oxford. In a 34-page paper arXiv 1903.10613, they show that, if n is an odd prime and 2 a primitive root mod n, then the maximum codimension is indeed 2. So they answer my original question, conditional on the Artin conjecture!

I will not attempt to summarise their proof, other than to say it is a clever mixture of algebraic and graph-theoretic argument. I certainly have not had time to read it carefully. But I am delighted, and in part feel vindicated that I was not able to do this myself; it is clearly harder than the simple statement suggests.

About Peter Cameron

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

2 Responses to Fair games and Artin’s conjecture

  1. A free download of my paper with David Ellis and William Raynaud is available for 50 days from today (20 June), at https://authors.elsevier.com/c/1ZFhgiVNk4fj6

  2. Pingback: Cyclically covering subspaces

Leave a Reply

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

WordPress.com Logo

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

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.