Proof that GAK is transitive

Suppose we have a group autokey (GAK) cipher with a left multiplication action, with state group $G$, hidden subgroup $H$, ciphertext alphabet $C$, and CT mapping function $c: G \rightarrow C$ which identifies each right coset of $H$ with a distinct ciphertext symbol. Each right coset is given by $H g$ for some $g \in G$. There are actually two relevant group actions in this setup, both of them will be shown to be transitive.

A group action on a set of points is defined to be transitive if, starting from any point, any other point can be reached by the action of some group element.

The first action is the left multiplication action of the state group on the states of the cipher. Since the states form a group $G$, this is the action of $G$ on itself as a set of points, where each point is an element of the group, with a left multiplication action. Given points (as group elements) $g$ and $h$, we can directly construct the group element $h g^{-1}$ (guaranteed to be an element of $G$ because groups are closed under multiplication and contain inverses), which when left multiplied by $g$ gives $h g^{-1} g = h$. So the action of $G$ on itself is transitive.

The other action which is relevant is the action of the state group on right cosets, permuting the ciphertext alphabet. However, this is not the left multiplication action. Due to the hidden state, it's possible for the result of left multiplication by the same element of $G$ to end up in different cosets when starting from different elements of the same cosets, meaning different hidden states.

Instead, the action on cosets comes from looking at a pair of isomorphs and finding the transformation which maps between them, and leads to a right multiplication action of the same group. To see how this happens, consider two isomorphs, where at their first letter for each has some states $a$ and $b$ (which had been built by different cumulative sequences of left multiplications by elements of $G$ from the plaintext). These are in cosets of $H$, somewhat trivially, as $a \in H a$ and $b \in H b$, by factoring out $e \in H$ on the left. The transformation between the $H a$ and $H b$ cosets in this case is given by a right multiplication by $a^{-1} b$. Then look at the next letter of the isomorphs. Since the isomorphs have the same underlying plaintext, the states are changed by left multiplication by the same unknown element $g$ in both cases. So we have $g a$ and $g b$ as the new states, which are (again somewhat trivially, factoring out $e \in H$ on the left) in the (new) $H g a$ and $H g b$ cosets. The transformation between these is given by $(g a)^{-1} (g b) = a^{-1} g^{-1} g b = a^{-1} b$, exactly the same transformation as for the first pair of letters. The same process follows for any number of letters in the isomorph, as long as the plaintext for the two is the same. This is how isomorphs end up inducing a permutation of the ciphertext symbols, and this permutation is an element of the underlying state group (namely $a^{-1} b$).

This explanation of how the right action on cosets arises also pretty neatly explains transitivity. Given two different cosets $H a$ and $H b$, we can construct an element $a^{-1} b \in G$ which transforms between them. Since this applies to all pairs of cosets, this makes the action transitive.

For the eyes, this leads directly to The Transitivity Restriction, the conclusion that there are only 6 groups possible for GAK with 83 CT symbols, because there are only 6 different transitive group actions on 83 points.

It's also notable that this right multiplication action on cosets is what is found when doing alphabet chaining.