\documentclass[12pt]{article} \usepackage{amsmath,amsfonts,enumerate,amssymb,amsthm,color} \usepackage{e-jc} \specs{P4.45}{21(4)}{2014} \def\G{\mathcal{G}} \def\R{\mathcal{R}} \def\bR{\mathbf{R}} \def\S{\mathbf{S}} \def\Z{\mathbb{Z}} \DeclareMathOperator{\cay}{Cay} \theoremstyle{plain} \newtheorem{thm}{Theorem} \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \title{\bf On groups all of whose undirected Cayley graphs of bounded valency are integral} \author{Istv\'an Est\'elyi\thanks{Supported in part by the Young Researcher grant of ARRS (Agencija za raziskovanje Republike Slovenija), and the ARRS grant no.\ P1-0294.} \\ \small FMF, University of Ljubljana \\ [-0.8ex] \small Jadranska 19, 1000 Ljubljana, Slovenia \\ \small\tt istvan.estelyi@student.fmf.uni-lj.si \and Istv\'an Kov\'acs\thanks{Supported in part by the ARRS grant no.\ P1-0285.} \\ \small IAM, University of Primorska \\ [-0.8ex] \small Muzejski trg 2, 6000 Koper, Slovenia \\ \small\tt istvan.kovacs@upr.si } \date{\dateline{Apr 4, 2014}{Nov 17, 2014}{Nov 27, 2014}\\ \small Mathematics Subject Classifications: 05C50, 20C10} \begin{document} \maketitle \begin{abstract} A finite group $G$ is called Cayley integral if all undirected Cayley graphs over $G$ are integral, i.e., all eigenvalues of the graphs are integers. The Cayley integral groups have been determined by Kloster and Sander in the abelian case, and by Abdollahi and Jazaeri, and independently by Ahmady, Bell and Mohar in the non-abelian case. In this paper we generalize this class of groups by introducing the class $\G_k$ of finite groups $G$ for which all graphs $\cay(G,S)$ are integral if $|S| \le k$. It will be proved that $\G_k$ consists of the Cayley integral groups if $k \ge 6;$ and the classes $\G_4$ and $\G_5$ are equal, and consist of:\ (1) the Cayley integral groups, (2) the generalized dicyclic groups $Dic(E_{3^n} \times \Z_6),$ where $n \ge 1$. \bigskip\noindent \textbf{Keywords:} integral graph, Cayley graph, Cayley integral group \end{abstract} \section{Introduction} A finite simple graph is called \emph{integral} if all its eigenvalues are integers. These graphs were introduced by Harary and Schwenk \cite{HarS74}, and have been attracting considerable attention (see the surveys \cite{AhmABS09,BalCRSS03}). In \cite{AbdV09}, Abdollahi and Vatandoost proposed to consider those integral graphs which are also Cayley graphs. Recall that, given a finite group $G$ and a subset $S$ of $G$ with $1 \notin S$ and $S=S^{-1}=\{s^{-1} : s \in S\},$ the \emph{Cayley graph} $\cay(G,S)$ has vertex set $G,$ and edges in the form $\{g,s g\},$ $g \in G$ and $s \in S$. Klotz and Sander \cite{KloS10} called a finite group $G$ \emph{Cayley integral} if all graphs $\cay(G,S)$ are integral. Before we recall the classification of Cayley integral groups it is necessary to set some notation. The cyclic, the elementary abelian, and the dihedral group of order $n$ are denoted by $\Z_n, \, E_n$ and $D_n,$ respectively. Given a group $G$ and $x,y \in G,$ we will denote by $x^y$ the conjugate $y^{-1}xy$. Let $A$ be an abelian group having a unique involution $t$ and of order $|A| > 2$. The {\em generalized dicyclic group} $Dic(A) = \langle A, x \rangle,$ where $x^2=t,$ and $a^x=a^{-1}$ for every $a \in A$ (see \cite[page 252]{Sco64}). In the case when $A \cong \Z_n$ it is also called the {\em dicyclic group} of order $2n,$ denoted by $Dic_{2n};$ and when $A \cong \Z_{2^n}$ it is also known as the {\em generalized quaternion group} of order $2^{n+1},$ denoted by $Q_{2^{n+1}}$. \medskip In \cite{KloS10}, Klotz and Sander determined the abelian Cayley integral groups (see \cite[Theorem~13]{KloS10}): \begin{thm}\label{KS}{\rm (Klotz and Sander \cite{KloS10})} The only finite abelian Cayley integral groups are $E_{2^n} \times E_{3^m}$ and $E_{2^n} \times \Z_4^m,$ where $m,n \ge 0$. \end{thm} The non-abelian Cayley integral groups were found recently by Abdollahi and Jazaeri (see \cite[Theorem~1.1]{AbdJ14}), and independently by Ahmady et al.\ (see \cite[Theorem~4.2]{AhmBM14}): \begin{thm}\label{ABM}{\rm (Abdollahi and Jazaeri \cite{AbdJ14}; Ahmadi et al.\ \cite{AhmBM14})} The only finite non-abelian Cayley integral groups are $D_6, \, Dic_{12}$ and $Q_8 \times E_{2^n},$ where $n \ge 0$. \end{thm} In this paper we are going to study groups $G$ for which we require $\cay(G,S)$ to be integral only when $|S|$ is bounded by a fixed number. Formally, for $k \in \mathbb{N},$ we set $$ \G_k = \big\{ G \, : \, \cay(G,S) \text{ is integral whenever } |S| \le k \big\}. $$ It is obvious that $\G_1$ is just the class of all finite groups, and in $\G_2$ there are exactly the groups whose non-identity elements are of order $2,3,4$ or $6,$ and contain no subgroup isomorphic to $D_n$ for any even number $n \ge 8$. The class $\G_3$ is the most intricate. Regarding $p$-groups, it is clear that all groups of exponent $3$ are in $\G_3,$ and we will show (see Proposition~\ref{P 2-Grp}) that a non-abelian $2$-group is in $\G_3$ if and only if it is of exponent $4,$ and any minimal non-abelian subgroup is isomorphic to $Q_8, \, H_2$ or $H_{32},$ where the latter groups $H_2$ and $H_{32}$ are defined in Corollary~\ref{Rc}. It is known that there are five minimal non-abelian groups of exponent $4$ (see Corollary~\ref{Rc}). In \cite{Jan07}, Janko described the non-abelian $2$-groups all of whose minimal non-abelian subgroups are either of order $8,$ or isomorphic to exactly one of these five groups. In particular, if they all are isomorphic to $Q_8,$ then $G \cong Q_{2^m} \times E_{2^n},$ where $m \ge 3, \, n \ge 0$ (see \cite[Corollary~2.4]{Jan07}). We will make use of this result when deriving that $Q_8 \times E_{2^n}$ are the only non-abelian $2$-groups in $\G_k$ if $k \ge 4$. Our goal in this paper is to determine the classes $\G_k$ when $k \ge 4$. Our main result is the following theorem: \begin{thm}\label{T main} Every class $\G_k$ consists of the Cayley integral groups if $k \ge 6$. Furthermore, $\G_4 $ and $\G_5$ are equal, and consist of the following groups: \begin{enumerate}[(1)] \item the Cayley integral groups, \item the generalized dicyclic groups $Dic(E_3^n \times \Z_6),$ where $n \ge 1$. \end{enumerate} \end{thm} In Section 2 we prove some useful properties of the groups in $\G_k$. Theorem~\ref{T main} will be derived in Section 3. \section{Some properties of the groups in $\mathbf{\G_k}$} All groups in this paper will be finite. Our notation and terminology for finite groups follow \cite{Sco64}. \medskip Case (i) in our first lemma is essentially \cite[Lemma~11]{KloS10}, cases (ii) and (iii) can be deduced from \cite[Lemma~4.3]{AhmBM14}. \begin{lem}\label{L basic} The following hold for every $G \in \G_k$ if $k \ge 2$. \begin{enumerate}[(i)] \item For every $x \in G$, the order of $x$ is in $\{1,2,3,4,6\}$. \item For every subgroup $H \le G,$ $H \in \G_k$. \item For every $N \unlhd G$ such that $|N| \mid k,$ $G/N \in \G_l,$ where $l = k / |N|$. \end{enumerate} \end{lem} In contrast to the class of Cayley integral groups, the class $\G_k$ is not closed under forming factor groups for every $k$. For example, consider the non-trivial semidirect product $\Z_4 \rtimes \Z_4$. It is easy to see that this group is in $\G_2,$ and that it has a factor group isomorphic to $D_8$. The group $D_8$ is clearly not in $\G_2$. Below we prove a weaker property. \begin{lem}\label{L section} Let $G \in \G_k,$ and $N \unlhd G,$ $N$ is abelian and $|N|$ is odd. Then $G/N \in \G_k$. \end{lem} Before we prove the lemma, we need to recall a result in \cite{KovMMM14} about eigenvalues of graphs which admit an abelian semiregular automorphism group. Let $\Gamma$ be a graph, and $H$ be an abelian semiregular group of automorphisms of $\Gamma$ with $m$ orbits on the vertex set. Fix $m$ vertices $v_1,\ldots,v_m$ of $\Gamma$ such that no two are from the same $H$-orbit. The \emph{symbol} of $\Gamma$ relative to $H$ and the $m$-tuple $(v_1,\ldots,v_m)$ is the $m \times m$ array $\S$ of subsets of $H,$ written as $\S = (S_{ij})_{i,j \in \{1,\ldots,m\}},$ where \begin{equation}\label{Sij} S_{ij} = \{ x \in H : v_i \sim v_j^x \text{ in } \Gamma \}. \end{equation} Here and in what follows, $v_i \sim v_j^x$ means that the vertices $v_i$ and $v_j^x$ are adjacent in $\Gamma$. For an irreducible character $\chi$ of $H,$ let $\chi(\S)$ be the $m \times m$ complex matrix defined by \begin{equation}\label{chiS} (\chi(\S))_{ij} = \begin{cases} \sum_{s \in S_{ij}}\chi(s) & \text{ if } S_{ij} \ne \emptyset \\ 0 & \text{ otherwise, } \end{cases} \; i,j \in \{1,\ldots,m\}. \end{equation} Note that, since $H$ is abelian, the irreducible characters are just the homomorphisms from $H$ to the multiplicative group of complex numbers. The following theorem is \cite[Proposition~3.1]{KovMMM14}: \begin{thm}\label{KMMM} {\rm (Kov\'acs et al.\ \cite{KovMMM14})} With notation as above, the spectrum of $\Gamma$ is equal to the union (counting multiplicities) of spectra of all $\chi(\S),$ where $\chi$ runs over the set of all irreducible characters of $H$. \end{thm} \noindent{\it Proof of Lemma~\ref{L section}.} \ Let $\Gamma_{G/N}=\cay(G/N,\R),$ and $\R$ be written as $\R = \{N r : r \in R\}$ for some $R \subset G$. It is clear that $N \cap R = \emptyset,$ in particular, $1 \notin R$. Observe that $N r^{-1} = (N r)^{-1} \in \R$. Therefore, if $(N r)^{-1} \ne N r,$ then we may assume that both $r$ and $r^{-1}$ are in $R$. Let $N r = (N r)^{-1}$. Then $r^2 \in N,$ hence $|\langle N,r \rangle| = 2|N|$. This together with $2 \nmid |N|$ imply that $r$ can be chosen to be an involution in $\langle N,r \rangle,$ and so $r^{-1} \in R$. Therefore, we may choose $R$ so that $1 \notin R$ and $R^{-1} = R,$ and thus we have the Cayley graph $\Gamma_G=\cay(G,R)$. Let $m = |G : N|,$ the index of $N$ in $G,$ and $T = \{ t_1,\ldots,t_m\}$ be a complete set of $N$-coset representatives in $G$ such that $R \subseteq T$. From now on every $x \in N$ will stand also for the permutation of $G$ acting as $g^x = g x, \, g \in G,$ and $N$ will stand for the group of all such permutations. Clearly, $N$ is a semiregular group of automorphisms of $\Gamma_G$ with $m$ orbits; and as vertices of $\Gamma_G,$ $t_1, \ldots, t_m$ represent all $N$-orbits. Let $\bR = (R_{ij})$ be the symbol of $\Gamma_G$ relative to $N$ and the $m$-tuple $(t_1,\ldots,t_m)$. By Theorem~\ref{KMMM}, the eigenvalues of $\Gamma_G$ are equal to the eigenvalues of $\chi(\bR),$ where $\chi$ runs over the set of all irreducible characters of $N$. Therefore, it is sufficient to show that the spectrum of $\chi(\bR)$ is equal to the spectrum of $\Gamma_{G/N},$ where $\chi$ is the trivial character of $H$ (i.e., $\chi(x)=1$ for every $x \in H$). Since $\chi(\bR)_{ij} = |R_{ij}|,$ see \eqref{chiS}, the latter statement follows from the following equivalence: \begin{equation}\label{iff} \forall i,j \in \{1,\ldots,m\}: |R_{ij}| \le 1, \text{ and } |R_{ij}|=1 \iff N t_i \sim N t_j \text{ in } \Gamma_{G/N}. \end{equation} We may write, see \eqref{Sij}, \begin{equation}\label{Rij} R_{ij} = \{ x \in N : t_i \sim t_j x \text{ in } \Gamma_G \} = \{ x \in N : t_j x t_i^{-1} \in R \}| = N \cap t_j^{-1} R t_i. \end{equation} Using that $N \unlhd G,$ this gives that $|R_{ij}|=|N \cap t_j^{-1} R t_i|= |N t_j t_i^{-1} \cap R|$. As $R \subseteq T,$ $|N t_j t_i^{-1} \cap R| \le 1$. Furthermore, $|N t_j t_i^{-1} \cap R|=1$ if and only if $N t_j t_i^{-1} = N r$ for some $r \in R,$ or equivalently, $N t_j (N t_i)^{-1} = N t_j t_i^{-1} \in \R$ holds in $G/N,$ or equivalently, $N t_j$ and $N t_i$ are adjacent in $\Gamma_{G/N}$. This completes the proof of \eqref{iff}. \hfill $\square$ \medskip It is well-known that the eigenvalues of a Cayley graph over an arbitrary group $G$ can be computed using the irreducible representations of $G$ (see \cite{DiaS81}). In this paper we will rather use Theorem~\ref{KMMM}, and hence avoid the representation theory of non-abelian groups. \medskip For $x,y \in G,$ we will denote by $[x,y]$ the \emph{commutator element,} i.e., $[x,y]=x^{-1}y^{-1}x y$. \begin{lem}\label{L dic} The group $Dic(E_{3^n} \times \Z_6)$ is in $\G_5$ for every $n \ge 0$. \end{lem} \begin{proof} Let $G = Dic(E_{3^n} \times \Z_6)$ and $S \subseteq G$ of size $|S| \le 5$. We have to show that $\cay(G,S)$ is integral. This is clear if $|S| \le 2$. Let $|S|=3$. It is easy to see that $G = P \rtimes \langle x \rangle,$ where $P \cong E_{3^{n+1}},$ $x$ is of order $4,$ and $u^x=u^{-1}$ for every $u \in P$. Notice that $x^2$ is the unique involution of $G$ which is in $Z(G)$. Therefore, $x^2 \in S$ and $\langle S \rangle$ is abelian. This implies that $\cay(G,S)$ is integral. Let $|S|=4$. Define $H = \langle P,x^2 \rangle \cong E_{3^{n+1}} \times \Z_2$. If $S \subseteq H,$ then $\langle S \rangle \le H,$ and hence $\cay(G,S)$ is integral. Thus we may assume that $S$ contains two elements in the form $x u$ and $(x u)^{-1}=x^{-1} u$ for some $u \in H$. Consider the symbol $\S = (S_{ij})$ of $\cay(G,S)$ relative to $H$ and the pair $(1,x)$. Let $S \cap H = \emptyset$. Then $S = \{xu, x^{-1}u, xv, x^{-1}v\},$ where $u,v \in H$ and $u \ne v$. According to \eqref{Rij}, the subsets $S_{ij}$ are computed as: $S_{11} = H \cap S = \emptyset,$ $S_{12} = H \cap x^{-1}S = \{u,x^2u,v,x^2v \},$ $S_{21} = H \cap S x = \{x^2 u^{-1},u^{-1},x^2 v^{-1},v^{-1} \},$ and $S_{22} = H \cap x^{-1} S x = \emptyset,$ i.e., $$ \S=\begin{pmatrix} \emptyset & \{u,x^2u,v,x^2 v\} \\ \{x^2u^{-1},u^{-1},x^2 v^{-1},v^{-1}\} & \emptyset \end{pmatrix}. $$ For an irreducible character $\chi$ of $H,$ $\chi(\S)$ has eigenvalues $\pm (1+\chi(x^2)) |\chi(u)+\chi(v)|$. This is equal to $0$ if $\chi(x^2)=-1$. Otherwise, $\chi(x^2) = 1,$ and both $\chi(u)$ and $\chi(v)$ are complex $3^{rd}$ roots of unities, showing that the eigenvalues are also integers in this case. Let $S \cap H = \{v,v^{-1}\}$. Then $$ \S=\begin{pmatrix} \{v,v^{-1}\} & \{u,x^2u\} \\ \{u^{-1},x^2u^{-1}\} & \{v,v^{-1}\} \end{pmatrix}. $$ The two eigenvalues of $\chi(\S)$ are $\chi(v)+\chi(v^{-1}) \pm (1+\chi(x^2))$. These are also integers, and this completes the proof of the case when $|S|=4$. Let $|S|=5$. In this case $S$ must contain the unique involution $x^2$. Repeating the above analysis with the set $S \setminus \{x^2\},$ one can deduce that $\cay(G,S)$ is always integral. \end{proof} \section{The classes $\mathbf{\G_k, \, k \ge 4}$} A finite group $G$ is said to be \emph{minimal non-abelian} if all proper subgroups of $G$ are abelian. The following result is due to R\'edei \cite{Red47}: \begin{thm}\label{R}{\rm (R\'edei \cite{Red47})} Let $G$ be a minimal non-abelian $p$-group. Then $G$ is one of the following groups: \begin{enumerate}[(i)] \item $Q_8;$ \item $\big\langle a, b \, | \, a^{p^m}=b^{p^n}=1, a^b=a^{1+p^{m-1}} \big\rangle,$ where $m \ge 2$ (metacyclic); \item $\big\langle a, b, c \, | \, a^{p^m}=b^{p^n}=c^p=1, [a, b]=c, [c,a]=[c,b]=1 \big\rangle,$ where $m+n \ge 3$ if $p=2$ (non-metacyclic). \end{enumerate} \end{thm} \begin{cor}\label{Rc} The minimal non-abelian groups of exponent at most $4$ are the following: \begin{enumerate}[(i)] \item $Q_8;$ \item $D_8=\big\langle a,b \, \mid \, a^4=b^2=1, a^b=a^{-1} \big\rangle,$ \\ $H_2 = \big\langle a,b \, \mid a^4=b^4=1, a^b=a^{-1} \big\rangle$ (metacyclic); \item $H_{16}=\big\langle a, b, c \, | \, a^4=b^2=c^2=1, [a, b]=c, [c,a]=[c,b]=1 \big\rangle ,$ \\ $H_{32} =\big\langle a, b, c \, | \, a^4=b^4=c^2=1, [a, b]=c, [c,a]=[c,b]=1 \big\rangle ,$ \\ $H_{27} = \big\langle a,b,c \, \mid \, a^3=b^3=c^3=1, [a,b] = c, [c,a] = [c,b] = 1 \big\rangle$ (non-metacyclic). \end{enumerate} \end{cor} \begin{lem}\label{L p} Every $p$-group in $\G_k$ is Cayley integral if $k \ge 4$. \end{lem} \begin{proof} Fix a number $k \ge 4$ and let $G \in \G_k$ be a $p$-group. Lemma~\ref{L basic}(i) gives that $p=2$ or $3,$ and the lemma follows at once when $G$ is abelian. Assume that $G$ is non-abelian. We have to prove that $G \cong E_{2^n} \times Q_8$ for some $n \ge 0$. In view of \cite[Corollary~2.4]{Jan07} (see the introduction), it is sufficient to show that every minimal non-abelian subgroup of $G$ is isomorphic to $Q_8$. Let $N$ be a minimal non-abelian subgroup of $G$. Note that, $N \in \G_k$ because of Lemma~\ref{L basic}(ii). If $p=3,$ then $N \cong H_{27},$ see Corollary~\ref{Rc}. We exclude this possibility by showing that the graph $\Gamma = \cay(H_{27},\{a,a^{-1},b,b^{-1}\})$ is non-integral. Let $H = \langle a,c \rangle \cong E_9,$ and $\S = (S_{ij})$ be the symbol of $\Gamma$ relative to $H$ and the triple $(1, b,b^{-1})$. Then compute that $$ S_{11} = \{ a,a^{-1} \}, \; S_{22}=\{ac,(ac)^{-1}\}, \; S_{33}= \{ac^{-1},a^{-1}c \}, $$ and $S_{ij}=\{1\}$ if $i \ne j$. Let $\chi$ be the irreducible character of $H$ defined by $\chi(a) = 1$ and $\chi(c) = e^{2\pi i/3}$. Then $$ \chi(\S) = \begin{pmatrix} 2 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end{pmatrix}. $$ The eigenvalues of $\chi(\S)$ are $-2$ and $1 \pm \sqrt{3},$ and as these are also eigenvalues of $\Gamma,$ see Theorem~\ref{KMMM}, $\Gamma$ is indeed non-integral. Thus $p=2,$ and $N$ is isomorphic to one of the following groups: $$ Q_8, \; D_8, \; H_2, \; H_{16} \text{ and } H_{32}. $$ We complete the proof by excluding the last four groups. \medskip $\bullet$ $D_8:$ Let $D_8 = \langle a,b \mid a^4=b^2=1, bab=a^{-1} \rangle$. It is easy to see that $\cay(H,\{ab,b\})$ is isomorphic to an $8$-cycle, which is not integral. We actually obtained that $D_8 \notin \G_2$. \medskip $\bullet$ $H_{2}:$ Notice that $\langle b^2 \rangle \unlhd H_2,$ and $H_2/\langle b^2 \rangle \cong D_8$. As $D_8 \notin \G_2,$ this and Lemma~\ref{L basic}(iii) yield that $H_2 \notin \G_k$. \medskip $\bullet$ $H_{16}:$ In fact, we show that $H_{16} \notin \G_3$. Consider the graph $\cay(H_{16},\{ba,ba^{-1}c,b\})$. Compute its symbol $\S$ relative to $H = \langle a,c \rangle \cong \Z_4 \times \Z_2$ and the pair $(1,b):$ $$ \S = \begin{pmatrix} \emptyset & \{a,a^{-1}c,1\} \\ \{ac,a^{-1},1\} & \emptyset \end{pmatrix} \text{ and } \chi(\S) = \begin{pmatrix} 0 & 2i+1 \\ -2i+1 & 0 \end{pmatrix}, $$ where $\chi$ is defined by $\chi(a)=i$ (the complex imaginary unit), and $\chi(c)=-1$. The eigenvalues of $\chi(\S)$ are $\pm \sqrt{5},$ and so $H_{16} \notin \G_k$ if $k \ge 3$. \medskip $\bullet$ $H_{32}:$ Consider the graph $\cay(H_{32},\{ba,b^{-1}a^{-1}c,b,b^{-1}\})$. Compute its symbol $\S$ relative to $H = \langle a,b^2,c \rangle \cong \Z_4 \times E_4$ and the pair $(1,b):$ $$ \S = \begin{pmatrix} \emptyset & \{a,b^2 a^{-1}c,1,b^2\} \\ \{b^2 a c,a^{-1},b^2,1\} & \emptyset \end{pmatrix} \text{ and } \chi(\S) = \begin{pmatrix} 0 & 2i+2 \\ -2i+2 & 0 \end{pmatrix}, $$ where $\chi$ is defined by $\chi(a)=i$ (the complex imaginary unit), $\chi(b^2)=1$ and $\chi(c)=-1$. The eigenvalues of $\chi(\S)$ are $\pm 2\sqrt{2},$ and so $H_{32} \notin \G_k$ if $k \ge 4$. \end{proof} \begin{lem}\label{L nil} Every nilpotent group in $\G_k$ is Cayley integral if $k \ge 4$. \end{lem} \begin{proof} Let $G \in \G_k$ be nilpotent for some $k \ge 4$. In view of the previous lemma we may assume that $G$ is not a $p$-group. By Lemma~\ref{L basic}(ii), every Sylow $p$-subgroup of $G$ is in $\G_k,$ and hence it is Cayley integral by Lemma~\ref{L p}. Since $G$ is nilpotent, we may write that $G = P \times Q,$ where $P$ is a Cayley integral $2$-group and $Q$ is a Cayley integral $3$-group. Theorems~\ref{KS} and \ref{ABM} show that $P \cong E_{2^n} \times \Z_4^m$ or $Q_8 \times E_{2^n}$ for some $m,n \ge 0$ such that $|P| \ne 1,$ and $Q \cong E_{3^l}$ for some $l \ge 1$. If $P$ contains an element of order $4,$ then we can see that $G$ contains an element of order $12,$ which is impossible according to Lemma~\ref{L basic}(i). We conclude that $P \cong E_{2^n},$ and so $G \cong E_{2^n} \times E_{3^l},$ which is Cayley integral. This completes the proof of the lemma. %$G$ is Cayley integral unless $P \cong E_{2^n} \times \Z_4^m$ or %$Q_8 \times E_{2^n}$ for some integers $m \ge 1$ and $n \ge 0,$ and %$Q \cong E_{3^l}$ for some integer $l \ge 1$. In each of these cases, however, $G$ %contains an element of order $12,$ which is impossible according to %Lemma~\ref{L basic}(i). \end{proof} It is worth to derive the following characterization of non-abelian $2$-groups in $\G_3$. \begin{prop}\label{P 2-Grp} Let $G$ be a non-abelian $2$-group of exponent $4$. Then $G \in \G_3$ if and only if every minimal non-abelian subgroup of $G$ is isomorphic to $Q_8,\, H_2$ or $H_{32}$. \end{prop} \begin{proof} As none of $D_8$ and $H_{16}$ is in $\G_3$ (see the above proof), the ``only if'' part follows immediately from this and Lemma~\ref{L basic}(ii). For the ``if'' part, assume that no minimal non-abelian subgroup of $G$ is isomorphic to $D_8$ or $H_{16}$. It is sufficient to prove that every involution of $G$ is in the center $Z(G)$. It is easy to deduce from this that $\langle S \rangle$ is abelian for every inverse-closed subset $S \subset G$ with $1 \notin S$ and $|S| \le 3,$ and hence that $G \in \G_3$. Assume, towards a contradiction, that $[t,x] \ne 1$ for some involution $t$ and element $x$ in $G,$ and let $H=\langle t,x \rangle$. Clearly, $t \notin Z(H)$. Since $H \not\cong D_8,$ $x$ must be of order $4$. Also, $x^2 \in Z(H),$ hence $H/\langle x^2 \rangle$ is generated by two involutions. Since $H$ is of exponent $4$, we obtain that $|H| =8$ or $16$. In the first case, since $H$ is non-abelian, $H \cong Q_8$. This contradicts that $t \notin Z(H)$. Therefore, $|H| = 16$. If $H$ is minimal non-abelian, then $H \cong H_2$ or $H_{16}$. Both cases are impossible, every involution of $H_2$ is in $Z(H_2),$ while the involution $t \notin Z(H),$ and $H \not\cong H_{16}$ by assumption. Thus $H$ contains a non-abelian subgroup of order $8,$ say $Q$. Then $Q \cong Q_8,$ and as $|H:Q|=2,$ $Q$ is normal in $H$. Thus if $t \in Q,$ then both $t$ and $t^x$ are involutions of $Q,$ implying that $t^x=t,$ i.e., $[t,x]=1,$ a contradiction. Thus $t \notin Q,$ and hence $H = Q \rtimes \langle t \rangle$ is a non-trivial semidirect product. There is an element $y \in Q$ such that $y^t \ne y$. Clearly, $y$ is of order $4$. If $y^t = y^{-1},$ then $\langle y,t \rangle \cong D_8,$ a contradiction. If $y^t \ne y^{-1},$ then putting $z = y y^t,$ we find that $z$ is of order $4,$ and $z^t = (y y^t)^t = y^t y = z^{-1}$. Thus $\langle z, t \rangle \cong D_8,$ a contradiction. This completes the proof of the proposition. \end{proof} Now, we return to the classes $\G_k, \, k \ge 4$. \begin{lem}\label{L normal} Suppose that $G \in \G_k, \, k \ge 4,$ and $3 \mid |G|$. Then $G$ has a normal Sylow $3$-subgroup. \end{lem} \begin{proof} We proceed by induction on the order of $G$. There is nothing to prove if $G$ is a $3$-group, hence we may assume that $2$ and $3$ are the prime divisors of $|G|,$ see Lemma~\ref{L basic}(i). Burnside's ``pq''~Theorem gives that $G$ is solvable. Let $K$ be a minimal normal subgroup of $G$. It is well-known that $K$ is elementary abelian, and hence $K < G$. Let $M$ be a maximal normal subgroup of $G$ which contains $K$. Then $G/M$ is simple and solvable (see \cite[2.5.2 and 2.6.1]{Sco64}), which imply that $G/M$ is of prime order (see \cite[Exercise~2.6.6]{Sco64}). Therefore, $|G : M|=2$ or $3$. Also note that, $M \in \G_k$ because of Lemma~\ref{L basic}(ii). If $|G : M|=2,$ then the induction hypothesis gives that $M$ has a normal Sylow $3$-subgroup, say $N$. Since $N$ is characteristic in $M$ (being a normal Sylow $3$-subgroup of $M$) and $M$ is normal in $G,$ we find that $N$ is also a normal Sylow $3$-subgroup of $G$. Let $|G : M|=3,$ and suppose that $3 \mid |M|$. Then the the induction hypothesis gives that $M$ has a normal Sylow $3$-subgroup, say $N$. Using again that $N$ is characteristic in $M$ and $M$ is normal in $G$, we find that $N$ is normal in $G$. By Lemma~\ref{L basic}(ii), $N$ is in $\G_k,$ and since it is also a $3$-group, it has to be Cayley integral, see Lemma~\ref{L p}. Then it follows from Theorems~\ref{KS} and \ref{ABM} that $N$ is an elementary abelian $3$-group, and Lemma~\ref{L section} can be applied to $G$ and $N$. We conclude that $G/N \in \G_k,$ hence $G/N$ has a normal Sylow $3$-subgroup, say $L$ ($L \cong \Z_3$). Then the pre-image $\eta^{-1}(L),$ where $\eta : G \to G/N$ is the natural projection, is a normal Sylow $3$-subgroup in $G$. We are left with that case that $9 \nmid |G|,$ and $G$ has a normal Sylow $2$-subgroup. Thus $G = P \rtimes \langle x \rangle,$ where $P$ is a $2$-group and $x$ is of order $3$. We complete the proof by showing that $x$ centralizes $P,$ and thus $G$ is abelian. Assume, towards a contradiction, that $[u,x] \ne 1$ for some $u \in P$. Let $U=\langle u,u^x,u^{x^2} \rangle$ and $V=\langle u, x \rangle$. Clearly, $U \unlhd V$ and $V \cong U \rtimes \Z_3$. Suppose for the moment that $u$ is of order $2$. The group $P$ is Cayley integral, see Lemma~\ref{L p}, in particular, all involutions of $P$ are in the center $Z(P)$. This implies that $U \cong E_4$ or $E_8$. If $U \cong E_4,$ then $V = E_4 \rtimes \Z_3 \cong A_4$. If $U \cong E_8,$ then consider the group $\langle u u^x, u u^{x^2}, x \rangle$. As this is isomorphic to $A_4,$ we see that in either case, $V$ contains a subgroup isomorphic to $A_4$. We show next that this is impossible by proving that $A_4 \not\in \G_k$. Write $A_4=\langle (1,3)(2,4), (1,2,3) \rangle,$ and let $\Gamma=\cay(A_4,\{a,b,c,c^{-1}\}),$ where $a=(1,2)(3,4),$ $b=(1,3)(2,4)$ and $c=(1,2,3)$. Let $\S$ be the symbol of $\Gamma$ relative to $H = \langle a,b \rangle$ and the triple $(1,c,c^{-1}),$ and let $\chi$ be the irreducible character of $H$ defined by $\chi(a)=1$ and $\chi(b)=-1$. Then $$ \S=\begin{pmatrix} \{a,b\} & \{1\} & \{1\} \\ \{1\} & \{ab,a\} & \{1\} \\ \{1\} & \{1\} & \{b,ab\} \end{pmatrix} \text{ and } \chi(\S) = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & -2 \end{pmatrix}. $$ The eigenvalues of $\chi(\S)$ are $-1$ and $\frac{1}{2}(-1 \pm \sqrt{17}),$ hence $A_4 \notin \G_k$. We conclude that $x$ centralizes all involutions of $P$. Let $u$ be of order $4,$ and $W=\langle u \rangle$. Since $[u,x] \ne 1,$ $W^x \ne W,$ and thus $W, W^x$ and $W^{x^2}$ are three distinct subgroups of order $4$ contained in $U$. Since $x$ centralizes all involutions of $P,$ it follows that \begin{equation}\label{cap} W \cap W^x \cap W^{x^2} = \langle u^2 \rangle. \end{equation} Suppose that $P$ is abelian. Then $P \cong E_{2^m} \times \Z_4^n$ for some $m \ge 0, n \ge 1$. Using that $U/\langle u^2 \rangle$ is elementary abelian of order $4$ or $8,$ we deduce that $U \cong \Z_2 \times \Z_4$ or $U \cong E_4 \times \Z_4$. The first case cannot occur, $U$ has three distinct subgroups of order $4$. In the second case there are four subgroups in $U$ of order $4$ containing $u^2,$ and thus must be one normalized by $x$. This, however, gives rise to an element in $G$ of order $12,$ and this is impossible. Let $P$ be non-abelian. Then $P \cong E_{2^m} \times Q_8.$ All subgroups of $P$ of order $4$ intersect at the same subgroup, the Frattini subgroup $\Phi(P)$. Thus \eqref{cap} gives that $\Phi(P) = \langle u^2 \rangle,$ $U/\langle u^2 \rangle \cong E_4$ or $E_8,$ and $U \cong Q_8$ or $U \cong \Z_2 \times Q_8$ respectively. If $U \cong Q_8,$ then $V \cong Q_8 \rtimes \Z_3$. Let $U \cong Q_8 \times \Z_2$. Then $U$ contains exactly four subgroups isomorphic to $Q_8$. Thus one of them must be normalized by $x,$ but not centralized, hence we see that $V$ always contains a subgroup isomorphic to $Q_8 \rtimes \Z_3$. We finish the proof by showing that $Q_8 \rtimes \Z_3 \not\in \G_k$. Write $Q_8=\{\pm 1,\pm i,\pm j,\pm k\}$ (the usual quaternion group) and $Q_8 \rtimes \Z_3 = Q_8 \rtimes \langle \sigma \rangle,$ where $\sigma^3=1,$ $[-1,\sigma]=1,$ $i^\sigma=j, j^\sigma=k,$ and $ k^\sigma=i$. Let $\Gamma = \cay(Q_8 \rtimes \Z_3, \{i,-i,\sigma,\sigma^{-1}\}),$ and $\S$ be the symbol of $\Gamma$ relative to $H = \langle -1,\sigma \rangle$ and the quadruple $(1,i,j,k)$. Let $\chi$ be the trivial character of $H$. Then $$ \S= \begin{pmatrix} \{\sigma,\sigma^{-1}\} & \{1,-1\} & \emptyset & \emptyset \\ \{1,-1\} & \emptyset & \{\sigma^{-1}\} & \{\sigma\} \\ \emptyset & \{\sigma\} & \emptyset & \{1,-1,\sigma^{-1}\} \\ \emptyset & \{\sigma^{-1}\} & \{1,-1,\sigma\} & \emptyset \end{pmatrix} \text{ and } \chi(\S) = \begin{pmatrix} 2 & 2 & 0 & 0 \\ 2 & 0 & 1 & 1 \\ 0 & 1 & 0 & 3 \\ 0 & 1 & 3 & 0 \end{pmatrix}. $$ The eigenvalues of $\chi(\S)$ are $4,$ $-3,$ and $\frac{1}{2}(1 \pm \sqrt{17}),$ hence $Q_8 \rtimes \Z_3 \notin \G_k,$ as claimed. \end{proof} \begin{lem}\label{L non-nil} Suppose that $G \in \G_k, \, k \ge 4,$ and $G$ is not nilpotent. Then $G \cong D_6$ or $Dic(E_3^n \times \Z_6)$ for some $n \ge 0$. \end{lem} \begin{proof} By Lemma~\ref{L normal}, $G$ contains a normal Sylow $3$-subgroup, say $P$. Since $G$ is non-abelian, there is an element $x$ of order $2$ or $4$ such that $x \notin C_G(P)$. Indeed, since $G \in \G_k, k\ge 4,$ every Sylow $2$-subgroup and $3$-subgroup of $G$ must be Cayley integral by Lemma~\ref{L p}. Therefore, if every element of order $2$ or $4$ is in $C_G(P),$ then the non-abelian group $G$ has an element of order $12$ since $G$ is not nilpotent, which is a contradiction. We consider first the case when $x$ is of order $2$. Suppose that $w^x \notin \langle w \rangle$ for some $w \in P$. Let $u=w^x w,$ $v=w^x w^{-1}$ and $U = \langle u, v \rangle$. Then $U \cong E_9,$ $u^x= u$ and $v^x = v^{-1}$. Thus $V = \langle U, x \rangle \cong D_6 \times \Z_3$. We exclude this possibility by showing that $V \notin \G_k$. Let $\Gamma = \cay(V,\{ x u,x u^{-1},x v \}),$ $\S$ be the symbol of $\Gamma$ relative to $U$ and the pair $(1,x),$ and let $\chi$ be the irreducible character of $U$ defined by $\chi(u)=1$ and $\chi(v)=\xi=e^{2i \pi/3}$. Then $$ \S=\begin{pmatrix} \emptyset & \{u,u^{-1},v\} \\ \{u,u^{-1},v^{-1}\} & \emptyset \end{pmatrix} \text{ and } \chi(\S) = \begin{pmatrix} 0 & 2+\xi \\ 2+\xi^{-1} & 0 \end{pmatrix}. $$ The eigenvalues of $\chi(\S)$ are $\pm \sqrt{3},$ hence $V \notin \G_k$. We are left with the case that $x$ inverts all elements of $P$. Assume that $|P| > 3$. Then let $\hat{U}= \langle u,v \rangle \cong E_9,$ and $\hat{V} = \langle \hat{U},x \rangle \cong E_9 \rtimes \Z_2$. Copying the above argument for the graph $\Gamma = \cay(\hat{V},\{ xu,xu^{-1},xv\}),$ we find again that $\pm \sqrt{3}$ are eigenvalues of $\Gamma,$ a contradiction. Therefore, $|P|=3$. Let $N = C_G(P),$ the centralizer of $P$ in $G$. Notice that, $N$ is an abelian normal subgroup of $G,$ and by the N/C Theorem (see \cite[Theorem~3.2.3]{Sco64}), $G/N$ is isomorphic to a subgroup of Aut$(P) \cong \Z_2$. Since $G$ is non-abelian, $G \ne N,$ and thus $|G : N|=2$. If $N \ne P,$ then take an involution $y \in N$. Then $y \in Z(G),$ hence $\langle x,y,P \rangle = \langle x,u \rangle \times \langle y \rangle \cong D_6 \times \Z_2 \cong D_{12},$ a contradiction. Therefore, $N=P,$ and $G \cong D_6$. To sum up, we may assume that $G \not\cong D_6$ and all involutions of $G$ are in $C_G(P)$. Let $x \in G \setminus C_G(P),$ and let $Q$ be a Sylow $2$-subgroup such that $x \in Q$. Suppose that $u^x \notin \langle u \rangle$ for some $u \in P$. Let $v=u^x u$. Since $P$ is an elementary abelian normal subgroup of $G$ and $[x^2,u]=1,$ we have $v^x = u^{x^2} u^x = u u^x=v,$ hence $v x$ is of order $12,$ a contradiction. %Then using that $[x^2,u]=1,$ we can prove, as above, that $v^x = v$ for some %$v \in P,$ hence $v x$ is of order $12,$ a contradiction. Therefore, $u^x = u^{-1}$ for every $u \in P$. Let $y$ be an involution of $Q$ such that $y \ne x^2,$ and let $V = \langle x,y,u \rangle,$ where $u \in P, \, u \ne 1$. Then $y \in Z(G),$ hence $V = \langle x,u \rangle \times \langle y \rangle \cong Dic_{12} \times \Z_2$. Then $\langle x^2 \rangle \unlhd V,$ and $V/\langle x^2 \rangle \cong D_6 \times \Z_2 \cong D_{12}$. This and Lemma~\ref{L basic}(iii) yield that $V \notin \G_k,$ a contradiction. Thus $Q$ has a unique involution, and hence $Q \cong \Z_4$ or $Q_8$ (recall that $Q$ is Cayley integral). Let $Q \cong Q_8$ and $K = \langle u, Q \rangle$ for some $u \in P, \, u \ne 1$. Then $\langle u \rangle \unlhd K,$ $|K| = 24,$ and the centralizer $C_K(u)$ is of order at least $12$. This shows that $C_K(u)$ contains an element of order $4,$ and so $K$ contains element of order $12,$ a contradiction. Therefore, $Q \cong \Z_4,$ and $G \cong Dic(E_{3^n} \times \Z_6),$ where $n \ge 0$. This completes the proof of the lemma. \end{proof} Everything is prepared to derive the main theorem. \medskip \noindent{\it Proof of Theorem~\ref{T main}.} Fix a number $k \ge 4,$ and let $G \in \G_k$ be a group which is not Cayley integral. By Lemma~\ref{L nil}, $G$ is not nilpotent, hence by Lemma~\ref{L non-nil}, $G \cong Dic(E_{3^n} \times \Z_6)$ for some $n \ge 1$ (here we use that $Dic(\Z_6) \cong Dic_{12},$ which is Cayley integral). By Lemma~\ref{L dic}, these groups are also in $\G_4$ and $\G_5,$ and this settles the the second part of the theorem. It remains to prove that $Dic(E_{3^n} \times \Z_6) \notin \G_k$ if $n \ge 1$ and $k \ge 6$. Observe that, all these groups contain a subgroup isomorphic to $Dic(\Z_3 \times \Z_6)$. Therefore, it is sufficient to show that $Dic(\Z_3 \times \Z_6) \notin \G_k$ if $k \ge 6$ (see Lemma~\ref{L basic}(ii)). Write $Dic(\Z_3 \times \Z_6) = E \rtimes \langle x \rangle,$ where $E \cong E_9,$ $x$ is of order $4,$ and $x$ inverts every element in $E$. Then $\langle x^2 \rangle$ is normal in $E \rtimes \langle x \rangle,$ and $(E \rtimes \langle x \rangle)/\langle x^2 \rangle \cong E_9 \rtimes \Z_2$. However, the latter group is not in $\G_3$ (see the proof of Lemma~\ref{L non-nil}). This and Lemma~\ref{L basic}(iii) yield that $E \rtimes \langle x \rangle \notin \G_k$ if $k \ge 6$. This completes the proof of the theorem. \hfill $\square$ \subsection*{Acknowledgements} The authors are grateful to the anonymous reviewers for the valuable comments. \begin{thebibliography}{12} \bibitem{AbdV09} A.~Abdollahi, E.~Vatandoost, Which Cayley graphs are integral, {\em Electronic J.\ Combin.}, 16:1--17, \#R122, 2009. \bibitem{AbdJ14} A.~Abdollahi, M.~Jazaeri, Groups all of whose undirected Cayley graphs are integral {\em Europ.\ J.\ Combin.}, 38:102--109, 2014. \bibitem{AhmABS09} O.~Ahmadi, N.~Alon, L.~F. ~Blake, I.~E.~Shparlinski, Graphs with integral spectrum, {\em Linear Algebra Appl.}, 430:547–-552, 2009. \bibitem{AhmBM14} A.~Ahmady, J.~P.~Bell, B.~Mohar, Integral Cayley graphs and groups, {\em SIAM J.\ Discrete Math.}, 28:685--701, 2014. \bibitem{BalCRSS03} K.~Bali\'nska, D.~Cvetkovi\'c, Z.~Radosavljevi\'c, S.~Simi\'c, D.~Stevanovi\'c, A survey on integral graphs, {\em Univ.\ Beogr.\ Publ.\ Elektrotehn.\ Fak.\ Ser.\ Mat}, 13:42–-65, 2003. \bibitem{DiaS81} P.~Diaconis, M.~Shahshahani, Generating a random permutation with random transpositions, {\em Z.\ Wahsch.\ Verw.\ Gebiete}, 57:159--179, 1981. \bibitem{HarS74} F.~Harary, A.~J.~Schwenk, Which graphs have integral spectra? in ``Graphs and Combinatorics (Proc.\ Capital Conf., George Washington Univ., Washington, D.C., 1973)'', Lecture Notes in Mathematics 406, Springer, Berlin, 45–-51, 1974. \bibitem{Jan07} Z.~Janko, On finite nonabelian $2$-groups all of whose minimal nonabelian subgroups are of exponent $4,$ {\em J.\ Algebra.}, 315:801--808, 2007. \bibitem{KloS10} W.~Klotz, T.~Sander, Integral Cayley graphs over abelian groups, {\em Electronic J.\ Combin.}, 17:1--13, \#R81, 2010. \bibitem{KovMMM14} I.~Kov\'{a}cs, D.~Maru\v{s}i\v{c}, A.~Malni\v{c}, \v{S}.~Miklavi\v{c}, Transitive group actions: (im)primitivity and semiregular subgroups, {\em J.\ Algebraic Comb.} (2014), \doi{10.1007/s10801-014-0556-z}. %preprint arXiv:math/0701686v2 [math.GR] 2014. \bibitem{Red47} L.~R\'{e}dei, Das schiefe Product in der Gruppentheorie, {\em Comment.\ Math.\ Helv.}, 20:225–-267, 1947. \bibitem{Sco64} W.~R.~Scott, Group theory, Prentice-Hall, New Jersey 1964. \end{thebibliography} \end{document}