# Splitting fields of representations of generalized symmetric groups, 4

This post if an aside on cyclotomic fields and Tchebysheff polynomials. Though it seems certain this material is known, I know of no reference.

Let $n$ denote a positive integer divisible by $4$, let $r=\cos(2\pi/n)$, $s=\sin(2\pi/n)$, and let $d=n/4$. If

$T_1(x)=x,\ \ T_2(x)=2x^2-1,\ \ T_3(x)=4x^3-3x,\ \ T_4(x)=8x^4-8x^2+1,\ \ ...,$

denote the Tchebysheff polynomials (of the 1st kind), defined by

$\cos(n\theta)=T_n(\cos(\theta)),$

then $T_d(r)=0.$

Let $\zeta_n=exp(2\pi i/n)$ and let $F_n={\mathbb{Q}}(\zeta_n)$ denote the cyclotomic field of degree $\phi(n)$ over ${\mathbb{Q}}$. If $\sigma_j\in Gal(F_n/{\Bbb{Q}})$ is defined by $\sigma_j(\zeta_n)=\zeta_n^j$ then

$Gal(F_n/{\Bbb{Q}})\cong ({\Bbb{Z}}/n{\Bbb{Z}})^\times,$

where $\sigma_j\longmapsto j$.

Lemma: Assume $n$ is divisible by $4$.

1. ${\mathbb{Q}}(r)$ is the maximal real subfield of $F_n$, Galois over ${\mathbb{Q}}$ with

$Gal(F_n/{\Bbb{Q}}(r))=\{1,\tau\},$

where $\tau$ denotes complex conjugation. Under the canonical isomorphism

$Gal(F_n/{\Bbb{Q}})\cong ({\Bbb{Z}}/n{\Bbb{Z}})^\times,$

we have

$Gal({\Bbb{Q}}(r)/{\Bbb{Q}})\cong ({\Bbb{Z}}/n{\Bbb{Z}})^\times/\{\pm 1\}.$

2. If $n$ is divisible by $8$ then $r$ and $s$ are conjugate roots of $T_d$. In particular, $s\in {\mathbb{Q}}(r)$ and $T_d(s)=0$.

3. We have $\sigma_j(r)=T_j(r)$.
4. If $n\geq 4$ is a power of $2$ then $T_d$ is the minimal polynomial of ${\mathbb{Q}}(r)$. Furthermore, in this case

$\cos(\pi/4)=\sqrt{2}/2,\ \ \cos(\pi/8)=\sqrt{2+\sqrt{2}}/2,\ \ \cos(\pi/16)=\sqrt{2+\sqrt{2+\sqrt{2}}}/2,\ \ ... .$

# Splitting fields of representations of generalized symmetric groups, 4

First a technical definition.

Let $A=C_\ell^n$. Let $\eta_k(z)=z^k$, for $z\in C_\ell$ and $1\leq k\leq \ell-1$. For $\eta\in C_\ell^*$, let $\mu\otimes \eta =(\mu_1\eta,\mu_2\eta,...,\mu_n\eta)$ where $\mu=(\mu_1,\mu_2,...,\mu_n)$. This defines an action of $C_\ell^*$ on $A^*$ and hence on the set of equivalence classes of $G$, $G^*$. We call two representations $\theta_{\mu,\rho}$, $\theta_{\mu',\rho'}$ $C_\ell^*$-equivalent, and write

$\theta_{\mu,\rho}\sim_\ell \theta_{\mu',\rho'},$

if $\rho=\rho'$ and $\mu'=\mu\otimes \eta$ for some $\eta\in C_\ell^*$. Similarly, we call two characters $\mu$, $\mu'$ of $C_\ell^n$ $C_\ell^*$-equivalent, and write

$\mu\sim_\ell \mu',$

if $\mu'=\mu\otimes \eta$ for some $\eta\in C_\ell^*$.

For example, Let $\ell =9$, $n=3$ and $\mu=(\eta_2,\eta_5,\eta_8)$. Then $\mu\sim \mu\otimes\eta_3$.

Let $\theta_{\mu,\rho}$ be as in the previous post. Note that

$\theta_{\mu\otimes \eta,\rho} = \theta_{\mu,\rho}\otimes \eta ,$

for $\eta\in C_\ell^*$. Therefore, the matrix representations of two $C_\ell^*$-equivalent representations differ only
by a character.

Let $G=C_\ell^n\, >\!\!\lhd \, S_n$.

The results in the above section tells us how to construct all the irreducible representations of $G$. We must

1. write down all the characters (i.e., 1-dimensional representations) of $A=C_\ell^n$,
2. describe the action of $S_n$ on $A^*$,
3. for each $\mu\in [A^*]$, compute the stabilizer $(S_n)_{\mu}$,
4. describe all irreducible representations of each $(S_n)_{\mu}$,
5. write down the formula for the character of $\theta_{\mu,\rho}$.

Write $\mu\in [A^*]$ as $\mu=(\mu_1,...,\mu_n)$, where each component is a character of the cyclic group $C_\ell$, $\mu_j\in C_\ell^*$. Let $\mu'_1,...,\mu'_r$ denote all the distinct characters which occur in $\mu$, so

$\{\mu'_1,...,\mu'_r\}=\{ \mu_1,...,\mu_n\}.$

Let $n_1$ denote the number of $\mu'_1$‘s in $\mu$, $n_2$ denote the number of $\mu'_2$‘s in $\mu$, …, $n_r$ denote the number of $\mu'_r$‘s in $\mu$. Then $n=n_1+...+n_r$. Call this the partition associated to $\mu$.

If two characters $\mu=(\mu_1,...,\mu_n)$, $\mu'=(\mu'_1,...,\mu'_n)$ belong to the same class in $[(C_\ell^n)^*]$, under the $S_n$-equivalence relation, then their associated partitions are equal.

The Frobenius formula for the character of an induced representation gives the following character formula. Let $\chi$ denote the character of $\theta_{\mu,\rho}$. Then

$\chi(\vec{v},p)=\sum_{g\in S_n/(S_n)_\mu} \chi^o_\rho(gpg^{-1})\mu^g(\vec{v}),$

for all $\vec{v}\in C_\ell^n$ and $p\in S_n$. In particular, if $p=1$ then

$\chi(\vec{v},1)=({\rm dim}\ \rho)\sum_{g\in S_n/(S_n)_\mu} \mu^g(\vec{v}).$

# Splitting fields of representations of generalized symmetric groups, 3

The representations of a semi-direct product of a group $H$ by an abelian group $A$, written $G=A\, >\!\!\lhd \, H$ (so $A$ is normal in $G$) can be described explicitly in terms of the representations of $A$ and $H$. The purpose of this post is to explain how this is done.

Again, a good reference for all this is Serre’s well-known book, Linear representations of finite groups.

Let $f$ be a class function on $H$. Extend $f$ to $G$ trivially as follows:

$f^0(g)= \left\{ \begin{array}{cc} f(g),&g\in H,\\ 0, & g\notin H, \end{array} \right.$

for all $g\in G$. This is not a class function on $G$ in general. To remedy this, we “average over $G$” using conjugation: Define the function $f^G=Ind_H^G(f)$ induced by $f$ to be

$Ind_H^G(f)(g)={1\over |H|}\sum_{x\in G} f^0(x^{-1}gx)=\sum_{x\in G/H}f^0(x^{-1}gx).$

This is referred to as the Frobenius formula.

Since $A$ is normal in $G$, $G$ acts on the vector space of formal complex linear combinations of elements of $A^*$ (=the characters of $A$),

$V={\mathbb{C}}[A^*]=span\{\mu\ |\ \mu\in A^*\},$

by

$(g\mu)(a)=\mu(g^{-1}ag),\ \ \ \ \forall g\in G,\ a\in A,\ \mu\in A^*.$

We may restrict this action to $H$, giving us a homomorphism $\phi^*:H\rightarrow S_{A^*}$, where $S_{A^*}$ denotes the symmetric group of all permutations of the set $A^*$. This restricted action is an equivalence relation on $A^*$ which we refer to below as the $H$-equivalence relation}. Let $[A^*]$ denote the set of equivalence classes of this equivalence relation. If $\mu,\mu'$ belong to the same equivalence class then we write

$\mu'\sim \mu$

(or $\mu'\sim_H\mu$ if there is any possible ambiguity). When there is no harm, we identify each element of $[A^*]$ with a character of $A$.

Suppose that $H$ acts on $A$ by means of the automorphism given by a homomorphism $\phi:H\rightarrow S_{A}$, where $S_{A}$ denotes the symmetric group of all permutations of the set $A$. In this case, two characters $\tau,\tau'\in A^*$ are equivalent if there is an element $h\in H$ such that, for all $a\in A$, we have $\tau'(a)=\tau(\phi(h)(a))$.

For each $\mu\in [A^*]$, let

$H_{\mu}=\{h\in H\ |\ h\mu = \mu\}.$

This group is called the stabilizer of $\mu$ in $H$. Let

$G_{\mu}=A\, >\!\!\lhd \, H_{\mu},$

for each $\mu\in [A^*]$. There is a natural projection map

$p_{\mu}:G_{\mu}\rightarrow H_{\mu}$

given by $ah\longmapsto h$, i.e., by $p_\mu(ah)=a$.

Extend each character $\mu\in [A^*]$ from $H_{\mu}$ to $G_{\mu}$ trivially by defining

$\mu(ah)=\mu(a),$

for all $a\in A$ and $h\in H_{\mu}$. This defines a character $\mu\in G^*_{\mu}$. For each $\rho\in H_{\mu}^*$, say $\rho:H_{\mu} \rightarrow Aut(V)$, let $\tilde{\rho}\in G_{\mu}^*$ denote the representation of $G_{\mu}$ obtained by pulling back $\rho$ via the projection $p_\mu:G_{\mu}\rightarrow H_{\mu}$, i.e., define

$\tilde{\rho}=\rho\circ p_{\mu}.$

For each $\mu \in [A^*]$ and $\rho\in H_\mu^*$ as above, let

$\theta_{\mu,\rho}=Ind_{G_\mu}^G(\mu\cdot \tilde{\rho}).$

Finally, we can completely describe all the irreducible representations of $G=A\, >\!\!\lhd \, H$. (This is Proposition 25 in chapter 8 of Serre’s book.)

Theorem:

1. For each $\mu \in [A^*]$ and $\rho\in H_\mu^*$, as above, then $\theta_{\mu,\rho}$ is an irreducible representation of $G$.
2. Suppose $\mu_1,\mu_2 \in [A^*]$, $\rho_1\in H_{\mu_1}^*$, $\rho_2\in H_{\mu_2}^*$. If $\theta_{\mu_1,\rho_1}\cong \theta_{\mu_2,\rho_2}$ then $\mu_1\sim \mu_2$ and $\rho_1\cong \rho_2$.
3. If $\pi$ is an irreducible representation of $G$ then $\pi\cong \theta_{\mu,\rho}$, for some $\mu \in [A^*]$ and $\rho\in H_{\mu}^*$ as above.

In the next post, we will examine the special case $A=C_\ell^n$ and $H=S_n$.

# Splitting fields of representations of generalized symmetric groups, 2

In general, there are three types of (complex) representations of a finite group $G$. (A good reference for all this is Serre’s well-known book, Linear representations of finite groups.)

Let $\rho:H\rightarrow Aut(W)$ be an $n$-dimensional irreducible representation of a finite group $G$ on a complex vector space $W$. Let $\chi$ denote the character of $\rho$.

Exactly one of the following possibilities must hold:

• One of the values of the character $\chi$ is not real. Such representations will be called complex (or type 1 or unitary).
• All the values of $\chi$ are real and $\rho$ is realizable by a representation over a real vector space. Such representations will be called real (or type 2 or orthogonal).
• All the values of $\chi$ are real but $\rho$ is not realizable by a representation over a real vector space. Such representations will be called quaternionic (or type 3 or symplectic).

Proposition (Frobenius-Schur): Let $\rho:H\rightarrow Aut(W)$ be an irreducible representation of a finite group $G$ on a complex vector space $W$ with character $\chi$. Then

${1\over |G|} \sum_{g\in G}\chi(g^2)= \left\{ \begin{array}{cc} 0,&\rho\ {\rm complex},\\ 1,&\rho\ {\rm real},\\ -1,&\rho\ {\rm quaternionic}. \end{array} \right.$

This quantity is sometimes called the Frobenius-Schur indicator of $\rho$.

It can be shown that if $\rho$ $\rho'\cong \rho$ are equivalent representations then $\rho$ and $\rho'$ have the same type.

In the next post we will examine the types that the irreducible representations of semi-direct product $G=C_\ell^n\, >\!\!\lhd \, S_n$ fall into.

# More odd examples of p-ary bent functions

In an earlier post I discussed bent functions $f:GF(3)^2\to GF(3)$. In this post, I’d like to give some more examples, based on a recent paper with Caroline Melles, Charles Celerier, David Phillips, and Steven Walsh, based on computations using Sage/pythpn programs I wrote with Charles Celerier.

We start with any function $f:GF(p)^n\to GF(p)$. The Cayley graph of $f$ is defined to be the edge-weighted digraph

$\Gamma_f = (GF(p)^n, E_f ),$
whose vertex set is $V=V(\Gamma_f)=GF(p)^n$ and the set of edges is defined by

$E_f =\{(u,v) \in GF(p)^n\ |\ f(u-v)\not= 0\},$
where the edge $(u,v)\in E_f$ has weight $f(u-v)$. However, if $f$ is even then we can (and do) regard $\Gamma_f$ as an edge-weighted (undirected) graph.

We assume, unless stated otherwise, that $f$ is even.

For each $u\in V$, define

• $N(u)=N_{\Gamma_f}(u)$ to be the set of all neighbors of $u$ in $\Gamma_f$,
• $N(u,a)=N_{\Gamma_f}(u,a)$ to be the set of all neighbors $v$ of $u$ in $\Gamma_f$ for which the edge $(u,v)\in E_f$ has weight $a$ (for each $a\in GF(p)^\times = GF(p)-\{0\}$),
• $N(u,0)=N_{\Gamma_f}(u,0)$ to be the set of all non-neighbors $v$ of $u$ in $\Gamma_f$ (i.e., we have $(u,v)\notin E_f$),
• the support of $f$ is
${\rm supp}(f)=\{v\in V\ |\ f(v)\not=0\}$

Let $\Gamma$ be a connected edge-weighted graph which is regular as a simple (unweighted) graph. The graph $\Gamma$ is called strongly regular with parameters $v$, $k=(k_a)_{a\in W}$, $\lambda=(\lambda_a)_{a\in W^3}$, $\mu=(\mu_a)_{a\in W^2}$, denoted $SRG_{W}(v,k,\lambda,\mu)$, if it consists of $v$ vertices such that, for each $a=(a_1,a_2)\in W^2$

$|N(u_1,a_1) \cap N(u_2,a_2)| = \left\{ \begin{array}{ll} k_{a}, & u_1=u_2,\\ \lambda_{a_1,a_2,a_3}, & u_1\in N(u_2,a_3),\ u_1\not= u_2,\\ \mu_{a}, &u_1\notin N(u_2),\ u_1\not= u_2,\\ \end{array} \right.$
where $k$, $\lambda$, $\mu$ are as above. Here, $W= GF(p)$ is the set of weights, including $0$ (recall an “edge” has weight $0$ if the vertices are not neighbors).

This example is intended to illustrate the bent function $b_8$ listed in the table below
$\begin{array}{c|ccccccccc} GF(3)^2 & (0, 0) & (1, 0) & (2, 0) & (0, 1) & (1, 1) & (2, 1) & (0, 2) & (1, 2) & (2, 2) \\ \hline b_8 & 0 & 2 & 2 & 0 & 0 & 1 & 0 & 1 & 0 \\ \end{array}$

Consider the finite field
$GF(9) = GF(3)[x]/(x^2+1) = \{0,1,2,x,x+1,x+2,2x,2x+1,2x+2\}.$
The set of non-zero quadratic residues is given by
$D = \{1,2,x,2x\}.$
Let $\Gamma$ be the graph whose vertices are $GF(9)$ and whose edges $e=(a,b)$ are those pairs for which $a-b\in D$.

The graph looks like the Cayley graph for $b_8$ in the Figure below

Bent function b_8 on GF(3)^2

except

$8\to 0, 0\to 2x+2, 1\to 2x+1, 2\to 2x,$
$3\to x+2, 4\to x+1, 5\to x, 6\to 2, 7\to 1, 8\to 0.$
This is a strongly regular graph with parameters $(9,4,1,2)$.

$\begin{array}{c|ccccccccc} v & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline N(v,0) & 3,4,6,8 & 4,5,6,7 & 3,5,7,8 & 0,2,6,7 & 0,1,7,8 & 1,2,6,8 & 0,1,3,5 & 1,2,3,4 & 0,2,4,5 \\ N(v,1) & 5,7 & 3,8 & 4,6 & 1,8 & 2,6 & 0,7 & 2,4 & 0,5 & 1,3 \\ N(v,2) & 1,2 & 0,2 & 0,1 & 4,5 & 3,5 & 3,4 & 7,8 & 6,8 & 6,7 \\ \end{array}$

The axioms of an edge-weighted strongly regular graph can be directly verified using this table.

Let $S$ be a finite set and let $R_0, R_1, \dots, R_s$ denote binary relations on $S$ (subsets of $S\times S$). The dual of a relation $R$ is the set

$R^* = \{(x,y)\in S\times S\ |\ (y,x)\in R\}.$
Assume $R_0=\Delta_S= \{ (x,x)\in S\times S\ |\ x\in S\}$. We say $(S,R_0,R_1,\dots,R_s)$ is an $s$-class association scheme on $S$ if the following properties hold.

• We have a disjoint union

$S\times S = R_0\cup R_1\cup \dots \cup R_s,$
with $R_i\cap R_j=\emptyset$ for all $i\not= j$.

• For each $i$ there is a $j$ such that $R_i^*=R_j$ (and if $R_i^*=R_i$ for all $i$ then we say the association scheme is symmetric).
• For all $i,j$ and all $(x,y)\in S\times S$, define

$p_{ij}(x,y) = |\{z\in S\ |\ (x,z)\in R_i, (z,y)\in R_j\}|.$
For each $k$, and for all $x,y\in R_k$, the integer $p_{ij}(x,y)$ is a constant, denoted $p_{ij}^k$.

These constants $p_{ij}^k$ are called the intersection numbers of the association scheme.

For this example of $b_8$, we compute the adjacency matrix associated to the members $R_1$ and $R_2$ of the association scheme $(G,R_0,R_1,R_2,R_3)$, where $G = GF(3)^2$,

$R_i = \{(g,h)\in G\times G\ |\ gh^{-1} \in D_i\},\ \ \ \ \ i=1,2,$
and $D_i = f^{-1}(i)$.

Consider the following Sage computation:

sage: attach "/home/wdj/sagefiles/hadamard_transform2b.sage"
sage: FF = GF(3)
sage: V = FF^2
sage: Vlist = V.list()
sage: flist = [0,2,2,0,0,1,0,1,0]
sage: f = lambda x: GF(3)(flist[Vlist.index(x)])
sage: F = matrix(ZZ, [[f(x-y) for x in V] for y in V])
sage: F  ## weighted adjacency matrix
[0 2 2 0 0 1 0 1 0]
[2 0 2 1 0 0 0 0 1]
[2 2 0 0 1 0 1 0 0]
[0 1 0 0 2 2 0 0 1]
[0 0 1 2 0 2 1 0 0]
[1 0 0 2 2 0 0 1 0]
[0 0 1 0 1 0 0 2 2]
[1 0 0 0 0 1 2 0 2]
[0 1 0 1 0 0 2 2 0]
sage: eval1 = lambda x: int((x==1))
sage: eval2 = lambda x: int((x==2))
sage: F1 = matrix(ZZ, [[eval1(f(x-y)) for x in V] for y in V])
sage: F1
[0 0 0 0 0 1 0 1 0]
[0 0 0 1 0 0 0 0 1]
[0 0 0 0 1 0 1 0 0]
[0 1 0 0 0 0 0 0 1]
[0 0 1 0 0 0 1 0 0]
[1 0 0 0 0 0 0 1 0]
[0 0 1 0 1 0 0 0 0]
[1 0 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 0 0]
sage: F2 = matrix(ZZ, [[eval2(f(x-y)) for x in V] for y in V])
sage: F2
[0 1 1 0 0 0 0 0 0]
[1 0 1 0 0 0 0 0 0]
[1 1 0 0 0 0 0 0 0]
[0 0 0 0 1 1 0 0 0]
[0 0 0 1 0 1 0 0 0]
[0 0 0 1 1 0 0 0 0]
[0 0 0 0 0 0 0 1 1]
[0 0 0 0 0 0 1 0 1]
[0 0 0 0 0 0 1 1 0]
sage: F1*F2-F2*F1 == 0
True
sage: delta = lambda x: int((x[0]==x[1]))
sage: F3 = matrix(ZZ, [[(eval0(f(x-y))+delta([x,y]))%2 for x in V] for y in V])
sage: F3
[0 0 0 1 1 0 1 0 1]
[0 0 0 0 1 1 1 1 0]
[0 0 0 1 0 1 0 1 1]
[1 0 1 0 0 0 1 1 0]
[1 1 0 0 0 0 0 1 1]
[0 1 1 0 0 0 1 0 1]
[1 1 0 1 0 1 0 0 0]
[0 1 1 1 1 0 0 0 0]
[1 0 1 0 1 1 0 0 0]
sage: F3*F2-F2*F3==0
True
sage: F3*F1-F1*F3==0
True
sage: F0 = matrix(ZZ, [[delta([x,y]) for x in V] for y in V])
sage: F0
[1 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 1]
sage: F1*F3 == 2*F2 + F3
True


The Sage computation above tells us that the adjacency matrix of $R_1$ is

$A_1 = \left(\begin{array}{rrrrrrrrr} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{array}\right),$
the adjacency matrix of $R_2$ is

$A_2 = \left(\begin{array}{rrrrrrrrr} 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{array}\right),$
and the adjacency matrix of $R_3$ is

$A_3 = \left(\begin{array}{rrrrrrrrr} 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \end{array}\right)$
Of course, the adjacency matrix of $R_0$ is the identity matrix. In the above computation, Sage has also verified that they commute and satisfy

$A_1A_3 = 2A_2+A_3$
in the adjacency ring of the association scheme.

Conjecture:
Let $f:GF(p)^n\to GF(p)$ be a bent function, with $p>2$. If the level curves of $f$ give rise to a weighted partial difference set then $f$ is weakly regular, and the corresponding (unweighted) partial difference set is of (positive or negative) Latin square type.

For more details, see the paper [CJMPW] with Caroline Melles, Charles Celerier, David Phillips, and Steven Walsh.

# Complements in the symmetric group

Almost 20 years ago I was asked a question by Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in $S_E$ and $S_V$ (the groups of all permutations of the edges $E$ and vertices $V$, respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of $S_m$ in $S_n$. Specifically, he asked if $S_8$ has a complement in $S_{12}$ (this terminology is defined below). The answer is, as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a ”$k$-tuple of complementary subgroups” for which the answer to the analogous question is ”yes.”

This post is a very short summary of part of a paper I wrote (still unpublished) which can be downloaded here. This post explains the ”no” part of the answer. For the more technical ”yes” part of the answer, see the more complete pdf version.

Notation: If $X$ is any finite set then

• $|X|$ denotes the number of elements in $X$.
• $S_X$ denotes the symmetric group on $X$.
• $S_n$ denotes the symmetric group on $\{1,2,...,n\}$.
• $A_n$ denotes its alternating subgroup of even permutations.
• $C_n$ denotes the cyclic subgroup of $S_n$ generated by the $n$-cycle $(1,2,...,n)$.
• $M_{10}$ denotes ”the Mathieu group of degree $10$” and order $720=10!/7!$, which we define as the subgroup of $S_{10}$ generated by $(2,6,10,7)(3,9,4,5)$ and $(1,5)(3,8)(4,10)(7,9)$.
• $M_{11}$ denotes the Mathieu group of degree $11$ and order $7920=11!/7!$ generated by $(1,2,3,4,5,6,7,8,9,10,11)$ and $(3,7,11,8)(4,10,5,6)$.
• $M_{12}$ denotes the Mathieu group of degree $12$ and order $95040=12!/7!$ generated by $(2,3,5,9,8,10,6,11,4,7,12)$ and $(1,12)(2,11)(3,10)(4,9)(5,8)(6,7)$.
• For any prime power $q$, ${\Bbb F}_q$ denotes the finite field with $q$ elements.
• $AGL_n({{\Bbb F}}_q)$ denotes the affine group of transformations on ${\Bbb F}_q^n$ of the form $\vec{v}\longmapsto A\vec{v}+\vec{a}$, where $A\in GL_n({{\Bbb F}}_q)$ and $\vec{a} \in {\Bbb F}_q^n$.

If $G$ is a finite group and $G_1,G_2$ are subgroups then we say $G_2$ is the complement of $G_1$ when

• $G_1\cap G_2=\{1\}$, the identity of $G$,
and
• $G=G_1\cdot G_2=\{g_1g_2\ |\ g_1\in G_1,\ g_2\in G_2\}$.

Let $X$ denote a finite set. If $G$ is a subgroup of $S_X$ and $x\in X$ then we let $G_x$ denote the stabilizer of $x$ in $G$:
$G_x=\{ g\in G\ |\ g(x)=x\}.$

Let $G$ be a permutation group acting on a finite set $X$ (so $G$ is a subgroup of the symmetric
group of $X$, $S_X$). Let $k\geq 1$ be an integer and let
$X^{(k)}=\{{\rm distinct\ }k{\rm -tuples\ in\ }X\} =\{(x_1,x_2,...,x_k)\ |\ x_i\not= x_j,\ 1\leq i \textless j\leq k\}.$
We say $G$ acts $k$-transitively on $X$ if $G$ acts transitively on $X^{(k)}$ via the ”diagonal” action
$g:(x_1,x_2,...,x_k)\longmapsto (g(x_1),g(x_2),...,g(x_k)).$

If $G$ acts transitively on $X$ and $G_x=1$ for some (hence all) $x\in X$ then we say $G$ acts regularly on $X$. If $G$ acts $k$-transitively on $X$ and acts regularly on $X^{(k)}$ then we say $G$ acts sharply $k$-transitively on $X$.

The classification of $k$-transitive groups, for $k\geq 4$, is to Jordan: A sharply $k$-transitive group, $k\geq 4$, must be one of the following.

• $k \geq 6$: $S_k$ , $S_{k+1}$ and $A_{k+2}$ only.
• $k = 5$: $S_5$ , $S_6$ , $A_7$ and the Mathieu group $M_{12}$.
• $k = 4$: $S_4$ , $S_5$ , $A_6$ and the Mathieu group $M_{11}$.

We give a table which indicates, for small values of $n$, which $S_m$ have a complement in $S_n$.

 $n$ $m$ complement of $S_m$ in $S_n$ $4$ $2$ $A_4$ $4$ $3$ $C_4$ $5$ $2$ $A_5$ $5$ $3$ $\langle (1,2,3,4,5),(2,3,5,4)\rangle \cong AGL_1({{\Bbb F}}_5)$ size $20$ $5$ $4$ $C_5$ $6$ $2$ $A_6$ $6$ $3$ $\langle (2,3,4,5,6),(3,4,6,5)\rangle \cong PGL_2({{\Bbb F}}_5)$ size $120$ $6$ $5$ $C_6$ $7$ $2$ $A_7$ $7$ $5$ $\langle (1,2,6,5,3,7),(1,4,3,2,5,6)\rangle \cong AGL_1({{\Bbb F}}_7)$ size $42$ $7$ $6$ $C_7$ $8$ $2$ $A_8$ $8$ $5$ $\langle (1,5,8,6,7,4),(1,5,8,7)(2,3,4,6)\rangle \cong PGL_2({{\Bbb F}}_7)$ size $336$ $8$ $6$ $AGL_1({{\Bbb F}}_8)$ size $56$ $8$ $7$ $C_8$ $9$ $2$ $A_9$ $9$ $6$ $PGL_2({{\Bbb F}}_8)$ size $504$ $9$ $7$ $AGL_1({{\Bbb F}}_9)$ size $72$ $9$ $8$ $C_9$ $10$ $2$ $A_{10}$ $10$ $7$ $M_{10}$ size $720$ ($PGL_2({{\Bbb F}}_9)$ is another) $10$ $9$ $C_{10}$ $11$ $2$ $A_{11}$ $11$ $7$ $M_{11}$ size $7920$ $11$ $9$ $AGL_1({{\Bbb F}}_{11})$ size $110$ $11$ $10$ $C_{11}$ $12$ $2$ $A_{12}$ $12$ $7$ $M_{12}$ size $95040$ $12$ $9$ $PGL_2({{\Bbb F}}_{11})$ $=\langle (1,2,3,4,5,6,7,8,9,10,11), (1,2,4,8,5,10,9,7,3,6),$ $(1,10)(2,5)(3,7)(4,8)(6,9)(11,12)\rangle$ size $1320$ $12$ $11$ $C_{12}$

Proposition: $S_m$ has a complement in $S_n$ if and only if there is an subgroup $H$ of $S_n$ such that

1. $H$ acts $(n-m)$-transitively on $\{1,2,...,n\}$,
2. $|H|=n(n-1)...(m+1)=n!/m!$.

Example: $S_{10}$ has not one but two non-isomorphic subgroups, $M_{10}$ and $PGL_2({{\Bbb F}}_9)$, of order $720=10!/7!$, each of which acts $3$-transitively on $\{1,2,...,10\}$. Thus $S_7$ has two non-isomorphic complements in $S_{10}$.

The statement below is the main result.

Theorem: The following statements hold.

1. If $n>2$ is not a prime power or a prime power plus $1$ then the only $1 for which $S_m$ has a complement in $S_n$ are $m=2$ and $m=n-1$.
2. If $n>12$ is a prime power and not a prime power plus $1$ then the only $1 for which $S_m$ has a complement in $S_n$ are $m=2$, $m=n-2$ and $m=n-1$.
3. If $n>12$ is a prime power plus $1$ but not a prime power then the only $1 for which $S_m$ has a complement in $S_n$ are $m=2$, $m=n-3$ and $m=n-1$.
4. If $n>12$ is both a prime power plus $1$ and a prime power then the only $1 for which $S_m$ has a complement in $S_n$ are $m=2$, $m=n-3$, $m=n-2$ and $m=n-1$.
5. If $n\leq 12$, see the above table.

# Grobner bases and permutation puzzles, according to Martin Kreuzer

This post is about some research Prof. Martin Kreuzer, at the Univ. of Passau, does which combines Grobner bases and solving permutation puzzles, such as the Rubik’s cube.

Prof. Martin Kreuzer giving a talk in Annapolis, 2013-12-04

Non-commutative Grobner Bases and Twisty Puzzles was the title of his talk (the link takes you to his slides, which he kindly allowed me to post).

Grobner bases were introduced in the mid-1960s (by Bruno Buchberger and, independently, Heisuke Hironaka), but in hindsight it is amazing they weren’t invented earlier. Indeed, Grobner bases arise when one tried to generalize long division of polynomials in one variable to polynomials of several variables. Non-commutative Grobner bases arise when one does not allow the variables to commute with each other. The main setting is where
$G = \langle x_1,...,x_n\ |\ l_1=r_1,...,l_s=r_s\rangle$ is a finitely presented monoid,
$K \langle X \rangle= \oplus_{g\in G} Kg = K/I$ is a monoid ring, and where
$I = \langle l_1-r_1,...,l_s-r_s\rangle$ is a two-sided ideal generated by binomials.

First, Prof. Kreuzer introduces the non-commutative analogs of term ordering, leading term, and Grobner basis with respect to that ordering.

The non-commutative analog of the Buchberger procedure.

After developing enough theory, it turns out that the word problem in group theory can be re-expressed in terms of the membership problem for $K \langle X \rangle$.

Prof Kreuzer discussing aspects of computational group theory.

Martin Kreuzer defines a twisty puzzle as a special form of a permutation puzzle. Its pieces (usually called cubies) can be permuted by twisting certain faces of the puzzle. The cubies carry stickers defining their location in the solved puzzle. For example, with the Rubik’s Cube, the 54 stickers of a 3×3×3 cube can be permuted by 90 degree turns of the faces. The possible permutations form a group called the Rubik’s cube group. Then he gives the following definition and remarkable Theorem.

Definition: Let G be a twisty puzzle group given via a set X of generating twists.
(a) The graph whose vertices are the elements of G and whose edges are pairs of positions which differ by just one twist is called the Cayley graph of G.
(b) The diameter δ(G) of the Cayley graph of G is called God’s number for the twisty puzzle.
(c) An algorithm which produces for every scrambled position p an element of X∗ whose length is the distance (in the Cayley graph) from p to the solved position is called a God’s algorithm for the twisty puzzle.

Theorem (God’s Algorithm via Grobner Bases)
Let X be a set of twists (and their inverses) which generate the group of a twisty puzzle. Given a scrambled position p of the puzzle, perform the following steps:
(1) Compute a Grobner basis G of the defining ideal of the twisty puzzle group ring w.r.t. a length compatible word ordering.
(2) Find any word w ∈ X∗ representing a sequence of twists that result in the position p.
(3) Compute NRG(w) ∈ X∗ and return this word.

This is an algorithm which computes a word representing a shortest possible sequence of twists that produces p from the solved position.

This has even been implemented on a computer in Cocoa, for a permutation puzzle with a very small group.

Prof Kreuzer at his laptop running a “toy” implementation of God’s algorithm.

# God’s number for the Rubik’s cube in the face turn metric

This is an update to the older post.

The story is described well at cube20.org but the bottom line is that Tom Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge have established that every cube position can be solved in 20 face moves or less. The superflip is known to take 20 moves exactly (in 1995, Michael Reid established this), so 20 is best possible – or God’s number in the face turn algorithm. Google (and, earlier, Sony) contributed computer resources to do the needed massive computations. Congradulations to everyone who worked on this!

This would make a great documentary I think!