A note on the "trivial group presentation game": \(I\) has a winning strategy on the group \(F_2\)29 May 2015 Paul Plummer
In my post on the strong measure zero game, I mentioned a game , where player one, who I will call , presents player two, who I will call , a subset from a group , where the normal closure of the set is the full group, and , chooses one element from each set presented, trying to get a set whose normal closure is again the full group. The game lasts innings ( if you prefer that notation). Essentially the idea is that gives presentations of the trivial group, and is trying to end up with a presentation of the trivial group.
As a simple example, we can consider the group of integers . Since the group is abelian any group that normally generates the group, also generates the group. This also means that there is some linear combination of elements from any presented set that has value . What player can do to win, is choose a non identity element , where is the least among non identity elements. If , player has already chosen a set that normally generates and may choose arbitrarily. Suppose that has chosen , if we choose an arbitrary element. If we have , then choose an element , so that . Note that we can do that, since otherwise, every element in the presented set would have dividing it, hence the greatest common divisor of the set, without the identity, would be greater than or equal to , contradicting the set generates the group. So we can always decrease our greatest common divisor till we reach . So we have a strategy where will win every time. A similar argument can be used to show that wins in groups where every strictly ascending chain of infinite index subgroups, is finite.
It is pretty easy to find groups where wins, by using large groups, like , but what about finitely generated groups? We will show, in this post, that has a winning strategy to win , in fact it will be a “fixed strategy” where will play the same no matter what picks on ’s turns.
Our proof will use facts from small cancellation theory, in particular small cancellation groups are not trivial. I will explain a bit of the idea of small cancellation conditions, and give key definitions. All the small cancellation that we discuss can be found in Combinatorial Group Theory Lyndon and Schupp, or Geometry of Defining Relations in Groups by Ol’shanskii, or Wikipedia.
The idea of small cancellation theory is that, if you have a set of relations, satisfying a “small cancellation condition”, that is when you multiply the two different words, the length of the reduced product (remove the ) is not much shorter than the the sum of the lengths of the word. This, in a sense, gives control over what words end up representing the identity, and how words can be reduced using the relations that satisfy the small cancellation conditions.
Basic definition for small cancellation theory
The information in this section is all fairly basic stuff, you may want to skip this section, or just read the definition and come back if there are some words you do not know.
Basic definitions for words in free groups. related to words and free groups. A word is a string of elements from some some set called an alphabet. For example and are all (not equal) words from the alphabet . A word is reduced if there is no occurrence of or in the word, and cyclically reduced provided it is not a nontrivial conjugate, so and . The length of a word , which we call is the number of elements in the reduced version of the word; this is well defined. So , for example.
Definition of symmetrized presentation. Suppose . We say the set of relations is symmetrized provided it is closed under taking inverses, and taking cyclic permutations of words up to being cyclically reduced, and every word in is cyclical reduced. has a symmetrized presentation provided is symmetrized. For example
Definition of : We say that is a piece relative to provided there exists two distinct elements with and , where “” is word equality, so no cancellation. We way has condition if and where is a piece, then . There is an entirely similar definition for
The reason I only mention is that it is a strong enough small cancellation condition to guarantee a group is infinite. Note that you can have a group that has a presentation, but may not be given to you that way. It is an interesting fact that for , every group has a presentation. There are many other small cancellation conditions, and for example, and you can mix-and-match different conditions too, but that is really beyond this post.
Player has a winning strategy in
Let be the free group of rank , on the set . We will show that has a winning strategy, by showing that there is a sequence of sets, , that normally generate, even generates, the group , and any one element choice from each of these sets gives a set , which will correspond to a group, , that is , which means that can not normally generate . The strategy for player will be to play on the th turn.
There will be a couple parts where I make some estimates on inequalities, and make no attempt to make these as good as possible(the estimates I make are good enough). If you are sensitive to such disregard of sharp bounds, you will need to have your eyes covered for the rest of this proof. You have been warned.
Proposition 1. Let
Then we have that generates the group , but any one element choice from each results in a set of relations for a group. In particular this means that for any choice of ’s, where , that is an infinite group since it will be .
proof of Lemma 1. First it is clear that each generates since we can multiply to cancel on each term to end up with , which generates the group. Let be the smallest symmetrized set of words containing the word , which is all the cyclically reduced, cyclic permutations of the word and their inverses. For all pieces are of the form , where (note that for many can not actually be obtained). So the length of a pieces are bounded by
and the length of each is bounded from below by
We get that
which for we have the right hand side is less than . A very similar argument can be carried out for and , and in fact you can use the same bounds, since our bounds are so rough. So each , for , gives a presentation. Say that and , and , and we consider . Note, that at “worst” the amount of cancellation between words in and will be bounded by the cancellation bounds we established above for , since elements in have small enough exponents on their ’s that they can not completely cancel out a term in . This worked for arbitrary choices. So let be a sequence where , then is a symmetrized set of relations, and we know that between two words, the cancellation is less than the length of either of the words, so it gives a presentation, hence is a group, and is infinite.
I came up with this game in a class I took on selection principles, and studied it as a final project, and at the time I knew very little group theory (I still know very little), and even thought all finitely generated groups had a winning strategy for player . At the end of the class I only really found some conditions for player winning in finitely generated groups. It had been at the back of my mind since the class, I would pick it up and work on it for a while before setting down, multiple times. In a way, thinking about this problem and closely related things really influenced my mathematical interests, I have a feeling it will show in future posts. In the end I am actually not to sure these ideas are of interest, at least in the finitely generated group case. I suspect it will be a while before I discuss these games on groups again, but I will end this with a couple questions to ponder:
- For finitely generated groups is there a nice demarcation line between player or having a winning strategy? For groups in general?
- Are there groups where there is no winning strategy for either player? Are there finitely generated groups where there is no winning strategy?
- There are a couple of other, similar ideas to consider, one where you replace normally generate with simply generate, or replace with generate finite index subgroup, or normally generate finite index subgroup, or mix-and-match the different sets. (I have not really thought about them much, but there are probably a lot of equivalences, because once you reach a finite index subgroup, in many cases, reach the full group) Are there any interesting connections and differences among them?
- For those who have looked up the connection of these sorts of games with selection principles and Ramsey statements(see the references in the strong measure zero game post): are there interesting connection between those and the games for finitely generated groups? For countable groups? For groups? In particular what would the Ramsey statements be?
- Can you think of any cool group theoretic consequences of a group that has a winning strategy for , how about for ?