Exercise 13.3.13

Proof. The action of a group G on the set of three-elements subsets of $\{1,\dots ,7\}$ is transitive when, for all triples of distinct elements $i,j,k$ and distinct elements $i^{\prime },j^{\prime },k^{\prime }$, there is a $g\in G$ such that $\{g\cdot i,g\cdot j,g\cdot k\}=\{i^{\prime },j^{\prime },k^{\prime }\}$ (which is less constraining that $\sigma (i)=i^{\prime },\sigma (j)=j^{\prime },\sigma (k)=k^{\prime }$).

The distinctness of elements means $i\ne j$ and $j\ne k$ and $i\ne k$. The possibilities $i=i^{\prime }$ (or $j^{\prime }$ or $k^{\prime }$) or $j=j^{\prime }$ (or $i^{\prime }$ or $k^{\prime }$) or $k=k^{\prime }$ (or $i^{\prime }$ or $j^{\prime }$) is allowed.

(a)

Let $A$ be the set of three-elements subsets of $\{1,\dots ,7\}$. If $\{i,j,k\}\in A$, we show the existence of $\sigma \in A_7$ such that $\sigma (1),\sigma (2),\sigma (3)=\{i,j,k\}$.

Since $\mathrm{Card}(\{1,2,3\})=\mathrm{Card}(\{i,j,k\})=3$, there exists some bijection ${\sigma }_1:\{1,2,3\}\to \{i,j,k\}$, for instance ${\sigma }_1:1\mapsto k,2\mapsto i,3\mapsto j$.

Since $\mathrm{Card}(\{4,5,6,7\})=\mathrm{Card}(\{1,\dots ,7\}\setminus \{i,j,k\})=4$, there exists a bijection ${\sigma }_2:\{4,5,6,7\}\to \{1,\dots ,7\}\setminus \{i,j,k\}$.

Then the map $s$ defined by $s(i)={\sigma }_1(i)$ if $i\in \{1,2,3\}$ and $s(i)={\sigma }_2(i)$ if $i\in \{4,5,6,7\}$ is a bijection, so that $s\in S_7$.

If $s$ is even, take $\sigma =s$, and if $s$ is odd, take $\sigma =s\circ (12)$. In both cases $\sigma \in A_n$ and $\sigma (\{1,2,3\})=\{i,j,k\}$.

Therefore the orbit of $\{1,2,3\}$ is $A_n\cdot \{1,2,3\}=A$, which has 35 elements, so that $A_7$ acts transitively on three-element subsets of $\{1,\dots ,7\}$. A fortiori $S_n\supset A_n$ acts transitively on the same set.

(b)

The following Sage instructions give the length of the orbits of $\{0,1,2\}$ and $\{0,1,3\}$

     F = GF(7)
     
     def t(a,b,i):
         return F(a*i + b)
     
     def orbit(u,v,w):
         """ returns the orbit of {u,v,w} """
         orb = set()
             for a in range(1,7):
                 for b in range(7):
                     l = [t(a,b,u), t(a,b,v), t(a,b,w)]
                     l.sort()
                     orb.add(tuple(l))
         return orb
     
     print(len(orbit(0,1,2)), len(orbit(0,1,3)))

(21,14)

For instance, the orbit of $\{0,1,3\}$ is

$$\begin{array}{llll}\hfill \mathrm{AGL}(1,{𝔽}_7)\cdot \{0,1,3\}=\{& \{3,4,6\},\{2,3,5\},\{0,4,5\},\{2,4,5\},\{0,2,3\},\{0,2,6\},\{1,5,6\},& \hfill & \\ \hfill & \{3,5,6\},\{1,2,4\},\{1,3,4\},\{0,1,5\},\{1,2,6\},\{0,1,3\},\{0,4,6\}\}.& \hfill & \end{array}$$

Alternatively, one can find the isotropy group of these unordered triples :

The one-dimensional affine linear group $\mathrm{AGL}(1,{𝔽}_7)$ is the group of order $7\times 6=42$ consisting of maps $i\mapsto \mathit{ai}+b$ where $i,a,b\in {𝔽}_7$ and $a\ne 0$. The isotropy group of an unordered triple $x^3=\{x_1,x_2,x_3\}$ is the subgroup $G_{x^3}=\{g\in {𝔽}_7|g\cdot x^3=x^3\}$. Solutions to the equations $a{x}_i+b=x_{\sigma (i)},i\in (1,2,3),\sigma \in S_3$ are giving the elements of isotropy group.

In matrix form the equations are:

$$\left(\begin{array}{cc}\hfill x_1& \hfill 1\\ \hfill x_2& \hfill 1\\ \hfill x_3& \hfill 1\end{array}\right)\left(\begin{array}{c}\hfill a\\ \hfill b\end{array}\right)=\left(\begin{array}{c}\hfill x_{\sigma (1)}\\ \hfill x_{\sigma (2)}\\ \hfill x_{\sigma (3)}\end{array}\right)$$

The extended matrix for all $\sigma \in S_3$ excluding identity permutation is:

$$\left(\begin{array}{ccccccc}\hfill x_1& \hfill 1& \hfill x_1& \hfill x_2& \hfill x_2& \hfill x_3& \hfill x_3\\ \hfill x_2& \hfill 1& \hfill x_3& \hfill x_1& \hfill x_3& \hfill x_1& \hfill x_2\\ \hfill x_3& \hfill 1& \hfill x_2& \hfill x_3& \hfill x_1& \hfill x_2& \hfill x_1\end{array}\right)$$

$\text{∙}$

Case $x^3=(0,1,2)$: Gauss transformation of extended matrix to bring the first two columns to $$\left(\begin{array}{cc}\hfill 0& \hfill 1\\ \hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right)$$

gives:

$$\left(\begin{array}{ccccccc}\hfill 0& \hfill 1& \hfill 0& \hfill 1& \hfill 1& \hfill 2& \hfill 2\\ \hfill 1& \hfill 1& \hfill 2& \hfill 0& \hfill 2& \hfill 0& \hfill 1\\ \hfill 2& \hfill 1& \hfill 1& \hfill 2& \hfill 0& \hfill 1& \hfill 0\end{array}\right)=\left(\begin{array}{ccccccc}\hfill 0& \hfill 1& \hfill 0& \hfill 1& \hfill 1& \hfill 2& \hfill 2\\ \hfill 1& \hfill 0& \hfill 2& \hfill 6& \hfill 1& \hfill 5& \hfill 6\\ \hfill 2& \hfill 1& \hfill 1& \hfill 2& \hfill 0& \hfill 1& \hfill 0\end{array}\right)=\left(\begin{array}{ccccccc}\hfill 0& \hfill 1& \hfill 0& \hfill 1& \hfill 1& \hfill 2& \hfill 2\\ \hfill 1& \hfill 0& \hfill 2& \hfill 6& \hfill 1& \hfill 5& \hfill 6\\ \hfill 0& \hfill 1& \hfill 4& \hfill 4& \hfill 5& \hfill 5& \hfill 2\end{array}\right)$$

There is only one solution corresponding to $a=6,b=2$, i.e., the order of isotropy group is $2$ and (cf. Theorem A.4.9) the appropriate orbit has $42∕2=21$ elements.

$\text{∙}$

Case $x^3=(0,1,3)$: $$\left(\begin{array}{ccccccc}\hfill 0& \hfill 1& \hfill 0& \hfill 1& \hfill 1& \hfill 3& \hfill 3\\ \hfill 1& \hfill 1& \hfill 3& \hfill 0& \hfill 3& \hfill 0& \hfill 1\\ \hfill 3& \hfill 1& \hfill 1& \hfill 3& \hfill 0& \hfill 1& \hfill 0\end{array}\right)=\left(\begin{array}{ccccccc}\hfill 0& \hfill 1& \hfill 0& \hfill 1& \hfill 1& \hfill 3& \hfill 3\\ \hfill 1& \hfill 0& \hfill 3& \hfill 6& \hfill 2& \hfill 4& \hfill 5\\ \hfill 3& \hfill 1& \hfill 1& \hfill 3& \hfill 0& \hfill 1& \hfill 0\end{array}\right)=\left(\begin{array}{ccccccc}\hfill 0& \hfill 1& \hfill 0& \hfill 1& \hfill 1& \hfill 3& \hfill 3\\ \hfill 1& \hfill 0& \hfill 3& \hfill 6& \hfill 2& \hfill 4& \hfill 5\\ \hfill 0& \hfill 1& \hfill 6& \hfill 6& \hfill 1& \hfill 3& \hfill 6\end{array}\right)$$

There are two solutions corresponding to $a=2,b=1$ and $a=4,b=3$, i.e., the order of isotropy group is $3$, hence the appropriate orbit has $42∕3=14$ elements.