% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.27}{24(2)}{2017} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \newtheorem{construction}[theorem]{Construction} \newtheorem{problem}[theorem]{Problem} \theoremstyle{definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{eg}[theorem]{Example} \newcommand{\PGL}{\mathop{\mathrm{PGL}}} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Sym}{Sym} \DeclareMathOperator{\Inn}{Inn} \DeclareMathOperator{\soc}{Soc} \DeclareMathOperator{\Diag}{Diag} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \DeclareMathOperator{\Wr}{wr} \newcommand{\PGammaL}{\mathop{\mathrm{P}\Gamma\mathrm{L}}} \newcommand{\norml}{\vartriangleleft} \def\a{\alpha} \def\b{\beta} \def\g{\gamma} \def\d{\delta} \def\e{\varepsilon} \def\r{\rho} \def\s{\sigma} \def\t{\tau} \def\om{\omega} \def\k{\kappa} \def\th{\theta} \def\ld{\lambda} \def\ph{\varphi} \def\z{\zeta} \def\D{\Delta} \def\Th{\Theta} \def\Ld{\Lambda} \def\si{\Sigma} \def\O{\Omega} \def\G {\Gamma} \def\o{\omega} \def\ov{\overline} \def\PO{{\rm P\Omega}} \def\PSL{{\rm PSL}} \def\AGL{{\rm AGL}} \def\qqed{\hfill $\Box$ \vspace{3truemm}} \def\di{{\,\Big|\,}} \def\PGaL{{\rm P\G L }} \def\Syl{{\rm Syl}} \def\Cay{{\rm Cay}} \def\Z{\mathbb Z} \def\K{{\rm\bf K}} \def\P{{\mathcal P}} \def\F{{\mathcal F}} \def\A{{\mathcal A}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title {\bf Circulant homogeneous factorisations of \\complete digraphs $\K_{p^d}$ with $p$ an odd prime} \author{Jing Xu\thanks{This work was supported by NSFC (project number 11371259).}\\ \small Department of Mathematics\\[-0.8ex] \small Capital Normal University\\[-0.8ex] \small Beijing 100048, China\\ \small\tt xujing@cnu.edu.cn} \date{\dateline{Sep 21, 2016}{May 15, 2017}{Jun 2, 2017}\\ \small Mathematics Subject Classifications: 05C25, 20B25} \begin{document} \maketitle \begin{abstract}Let $\F=(\K_{n},\P)$ be a circulant homogeneous factorisation of index $k$, that means $\P$ is a partition of the arc set of the complete digraph $\K_n$ into $k$ circulant factor digraphs such that there exists $\s\in S_n$ permuting the factor circulants transitively amongst themselves. Suppose further such an element $\s$ normalises the cyclic regular automorphism group of these circulant factor digraphs, we say $\F$ is normal. Let $\F=(\K_{p^d},\P)$ be a circulant homogeneous factorisation of index $k$ where $p^d$, ($d\ge 1$) is an odd prime power. It is shown in this paper that either $\F$ is normal or $\F$ is a lexicographic product of two smaller circulant homogeneous factorisations. \end{abstract} \section{Introduction} Let $\G=(V,A)$ be a \emph{digraph} with vertex set $V=V(\G)$ and arc set $A=A(\G)$. A \emph{factorisation} of $\G$ is a partition $\mathcal{P}=\{P_1,\ldots,P_k\}$ of $A$, and is denoted by the pair $(\G,\mathcal{P})$. This gives rise to \emph{factor digraphs}, $\G_i=(V, P_i)$ for $i=1,\ldots,k$. Moreover the integer $k=|\mathcal P|$ is called the \emph{index} of the factorisation and $|V|$ is called the \emph{order} of the factorisation. An \emph{automorphism} of a factorisation $(\G, \P)$ is an automorphism of the digraph $\G$ that preserves the partition $\P$. The automorphism group $\Aut(\G,\P)$ consists of all automorphisms of $(\G, \P)$. A factorisation $(\G, \mathcal{P})$ is called \emph{transitive} if $\Aut (\G, \mathcal{P})$ induces a transitive action on $\mathcal P$; further $(\G, \mathcal{P})$ is called \emph{homogeneous} if it is transitive and in addition the kernel of $ \Aut(\G, \mathcal P)$ acting on $\mathcal P$ is transitive on the vertex set $V(\G)$. That is there exists a subgroup $G\le \Aut(\G,\P)$ that permutes the parts $P_i$ transitively, and the kernel $M(=G\cap \Aut(\G_1)\cap \cdots \cap \Aut(\G_k))$ of $G$ acting on $\mathcal P$ is vertex transitive on each of the $\G_i$. Hence $G$ induces isomorphisms between each pair of the factor digraphs. To emphasise the groups $M$ and $G$, we say that the factorisation $(\G, \mathcal P)$ is \emph{$(M,G)$-homogeneous.} Such a factorisation is also denoted by $(\G,\mathcal P, M, G)$. We say a homogeneous factorisation $(\G,\mathcal P, M, G)$ is\emph{ cyclic} if the induced group $G^{\mathcal P}$ is cyclic. A digraph is called a {\it circulant} if it has a cyclic group of automorphisms which is regular on the vertex set. (A permutation group is \emph{regular} if it is transitive and the only element that fixes a point is the identity.) Let $(\G, \mathcal P)$ be $(M,G)$-homogeneous, suppose further that $M$ contains a regular cyclic subgroup. Then all of the factor digraphs $\G_i$ are circulants relative to the same cyclic regular subgroup, and $(\G, \mathcal P)$ is called a \emph{circulant }$(M,G)$-homogeneous factorisation. We denote by $\K_n$ the complete digraph on $n$ vertices in which each ordered pair of distinct vertices is an arc. Homogeneous factorisations of $\K_n$ with index 2 arise from pairs $\G, \ov \G$, where $\G$ is a vertex transitive digraph isomorphic to its complement $\ov\G$, that is, $\G$ is a vertex transitive \emph{self-complementary } directed graph. Suppose further that the factors $\G, \ov \G$ are undirected. Then $\G$ is a vertex transitive self-complementary undirected graph. Moreover it is easy to see that self-complementary circulants $(\G, \ov \G)$ correspond to a circulant homogeneous factorisation arising from this pair. A better understanding of vertex transitive self-complementary undirected or directed graphs is a principal motivation for studying homogeneous factorisations of $\K_n$, see for example \cite{lipraeger1, lipraeger}. In \cite{lsx}, self-complementary circulants of prime power order have been classified. Our main purpose of this paper is to classify circulant homogeneous factorisations of complete digraphs with prime power order, which can be viewed as a generalization of the result of \cite{lsx}. Let $\F=(\K_{n},\P)$ be a circulant homogeneous factorisation. An automorphism $\t(\in \Aut(\F))$ is called a \emph{ cyclic isomorphism} of $\F$ if $\t$ is transitive on $\P$. Suppose further that $\F$ is $(M, G)$-homogeneous. It is proved in \cite[Theorem 4.1]{lipraeger} that $\F$ must be cyclic, that is there exists $\s\in G\setminus M$ such that $G=\la M,\s\ra$ and $G^{\P}=\la\s^{\P}\ra$. Such an element $\s$ is a cyclic isomorphism of $\F$, and we often refer to $(\K_n, \P, M, \s)$ as this factorisation when we wish to emphasise this cyclic isomorphism. Moreover, let $Z_{n}(\le M)$ be the regular subgroup on $V(\K_n)$ and we identify the vertex set with this regular group $Z_n$. Suppose further that there exists a cyclic isomorphism $\s$ fixing point 1 (the identity element of $Z_n$) and normalising the regular cyclic subgroup $Z_{n}$. We say such a circulant homogeneous factorisation is \emph{normal}. In this case, $\s$ can be viewed as an automorphism of the cyclic group $Z_{n}$, and we can construct such factorisations easily, see Construction \ref{con1} for more details. We also give examples of non-normal circulant homogeneous factorisations in Proposition \ref{nonnormal}. We next present a lexicographic product construction of two circulant homogeneous factorisations which is analogous to the lexicographic product construction of two digraphs. For more information see \cite{GLPP, cons-sc}. For two digraphs $\G_i=(V_i,A_i)$ with $i=1, 2$, we denote by $A_1[A_2]$ the set of all pairs $((u_1, u_2), (v_1, v_2))$ such that either $(u_1, v_1)\in A_1$, or $u_1=v_1$ and $(u_2, v_2)\in A_2$. Then the \emph{lexicographic product } $\G_1[\G_2]$ is defined as the digraph with vertex set $V_1\times V_2$ and arc set $A_1[A_2]$. For $i=1,2$, let $\mathcal F_i=(\K_{n_i}, \P_i, M_i, \s_i)$ be a circulant homogeneous factorisation of index $k$ where $\s_i$ is a cyclic isomorphism of $\F_i$. Let $\P_i=\{P_{i,1},\ldots,P_{i,k}\}$ and suppose that $\s_i: P_{i,j}\mapsto P_{i,j+1}$ (reading the second subscript modulo $k$). Write the vertex set $\K_{n_1n_2}$ as $V(\K_{n_1})\times V(\K_{n_2})$ and let $ \F_1[\F_2] =(\K_{n_1 n_2},\P)$ where $\P=\{P_{1,j}[P_{2,j}]| 1\le j\le k\}$. It is proved in Lemma \ref{lexi} that $\F_1[\F_2]$ is a circulant homogeneous factorisation of index $k$ and $\F_1[\F_2]$ is called the \emph{lexicographic product} of $\mathcal F_1$ and $\F_2$. Let $\G_{i,j} (i=1,2, j=1,\ldots,k)$ be the factors of $\F_i$. Then $ \G_{1,j}[\G_{2,j}]$ are factors of $\F_1[\F_2]$. In this paper, we will classify circulant homogeneous factorisations of a complete digraph $\K_{p^d}$ where $p$ is an odd prime and $d\ge 1$. The main theorem is the following. \begin{theorem}\label{mainthm} Let $\F=(\K_{p^d},\P)$ be a circulant homogeneous factorisation of index $k$ where $p^d (d\ge 1)$ is an odd prime power. Then either $\F$ is normal or $\F=\F_1[\F_2]$ is a lexicographic product where $\F_i $ is a circulant homogeneous factorisation of index $k$ and order $p^{d_i}$ for $i=1,2$ and $d=d_1+d_2$ ($d_1,d_2\ge 1$). \end{theorem} \section{Preliminary results} From now on, we always assume that $p^d (d\ge 1)$ is an odd prime power. A finite permutation group is called a \emph{c-group} if it contains a cyclic regular subgroup. A precise list of primitive c-groups is given in the following lemma. \begin{lemma}\label{primitive-c-gps}{\rm(\cite[Theorem 1.2]{lipraeger})} Suppose that $X$ is a primitive permutation group on $\O $ and $X$ contains a cyclic regular subgroup. Then one of the following holds: \begin{itemize} \item[(i)] $|\O |=q$, and $X\le\AGL(1,q)$, where $q$ is a prime; \item[(ii)] $|\O |=4$, and $X= Sym(\O)$; \item[(iii)] $X$ is almost simple and $2$-transitive on $\O $. \end{itemize} \end{lemma} \begin{corollary}\label{X-prim} Suppose that $X$ is a solvable primitive c-group on $\O$ where $|\O|=p^d$ is an odd prime power. Then $|\O|=p$ and $\Z_p\le X\le\AGL(1,p)$. \end{corollary} Let $Z_n$ be a cyclic group of order $n$, considered in its action (by multiplication) as a subgroup of the symmetric group $\Sym (Z_n)$. A \emph{$Z_n$-circulant} is a Cayley digraph $\G=\Cay(Z_n,S)$ with vertex set $Z_n$ and arc set $A(\G)=\{(g,sg)\mid g\in Z_n, s\in S\}$, for some non-empty subset $S$ of $Z_n\setminus \{1\}$. We also denote by $\hat Z_{n}$ the right regular representation of the group $Z_{n}$. Then each $Z_n$-circulant $\G$ admits $\hat Z_n$ as a subgroup of automorphisms. Consider also $\Aut(Z_n)$ as a subgroup of $\Sym(Z_n)$ in its natural action. Then $\Aut(Z_n)$ normalises $\hat Z_n$ in $\Sym(Z_n)$, and $\Aut(Z_n)\cap \Aut(\G)$ is equal to $\Aut(Z_n,S):= \{\s\in\Aut(Z_n)\mid S^{\s}=S\}$. In fact the normaliser $N_{\Aut(\G)}(\hat Z_n)=\hat Z_n\rtimes\Aut(Z_n,S)$, see for example \cite{godsil,Xu-survey}. The Cayley digraph $\G=\Cay(Z_n, S)$ is said to be a \emph{normal circulant} if $\hat Z_n$ is normal in $\Aut(\G)$, or equivalently, if $\Aut(\G)=\hat Z_n\rtimes \Aut(Z_n,S)$. A circulant is called \emph{arc-transitive} if its automorphism group is transitive on the arc set. The finite arc-transitive circulants were classified independently by Istv\'an Kov\'acs~\cite{kovacs} and Cai Heng Li~\cite{li-arc-circ} in 2004. The following result concerning arc-transitive circulants of order $p^d$ is an immediate corollary of Theorem 1.3 in \cite{li-arc-circ}, (just note that in \cite[Theorem 1.3]{li-arc-circ}, the orders of the deleted lexicographic product type digraphs cannot be a prime power). \begin{theorem}\label{arc-circ} Let $\G=\Cay(Z_{p^d}, S)$ be a connected arc transitive directed circulant of order $p^d$ where $p$ is an odd prime and $d\ge 1$ is an integer. Then one of the following holds: \begin{enumerate} \item[(i)] $\G$ is a complete digraph. \item[(ii)] $\G$ is a normal circulant. \item[(iii)] There exists an arc-transitive circulant $\si$ of order $p^{d-i}$ such that $\G=\si[\ov K_{p^i}]$ where $1\le i p^m$, $sZ_{p^m}\subseteq S_j$. \end{corollary} \begin{proof} Just note that by Lemma \ref{block} (4), $Z_{p^m}$ is a block of $\Aut(\F)$, the result follows from Lemma \ref{lexi} and \ref{lexi2}. \end{proof} Moreover we have the following useful remark. \begin{remark}\label{lexire}Let $\F=(\K_{n},\P, X, \s)$ be a circulant homogeneous factorisation of index $k$ where $\s$ is a cyclic isomorphism fixing point 1 and let $\P=\{P_1,\ldots,P_k\}$. Suppose further that $\F=\F_1[\F_2]$ is of lexicographic product form where $\F_2$ is of order $n_2$, and $Z_{n_2}$ is a block of $\la X,\s\ra$. Then $\F_2$ is the sub-factorisation induced on the block $Z_{n_2}$ by $\F$, and $\F_1$ is the quotient factorisation induced on the block system $\{gZ_{n_2}| g\in Z_{n}\}$ defined as in the proof of Lemma \ref{lexi2}. In particular, with the notation in Lemma \ref{lexi2}, the factor digraphs of $\F_1$ are the quotient cayley digraphs $\G_{1,j}=\Cay(Z_{n}/Z_{n_2},\ov {P_{1,j}(1)})$ and $\ov {P_{1,j}(1)}=\{\ov s=sZ_{n_2}\mid s\in P_{1,j}(1)\}$. Suppose that $\s: P_j\to P_{j+1}$. Then $\bar \s: \G_{1,j}\to \G_{1,j+1}$. \end{remark} \section{Cyclic isomorphisms and normal circulant homogeneous factorisations of order $p^d$ } Let $(\K_{p^d},\P)$ be a circulant $(X,Y)$-homogeneous factorisation of index $k$, and suppose that $X$ contains a regular cyclic subgroup $Z_{p^d}$. We always identify the vertex set of $\K_{p^d}$ with the group $Z_{p^d}$. The following lemma discusses the orders of the cyclic isomorphisms. \begin{lemma}\label{orders}Let $\F=(\K_{p^d},\P)$ be a circulant $(X, Y)$-homogeneous factorisation of index $k$ and let $\t$ be a cyclic isomorphism. Then $k|(p-1)$ and $k|o(\t)$. Moreover there exists a cyclic isomorphism $\s\in Y$ such that $\s$ fixes 1 and $r|k$ for each prime divisor $r$ of the order $o(\s)$. \end{lemma} \begin{proof} By Theorem \ref{lpthm}, $k|(p-1)$. Since $\t$ is transitive on $\P$ and $|\P|=k$, $k|o(\t)$. By Theorem \ref{lpthm} again, there exists a cyclic isomorphism $\s\in Y\setminus X$ such that $Y=\la X,\s\ra$ and $Y^{\P}=\la \s ^{\P}\ra$ is a cyclic group of order $k$. Since $\hat Z_{p^d}\le X$ is vertex transitive, we may assume that $\s$ fixes the point 1. Let $q$ be a prime such that $(q,k)=1$. For any positive integer $m$, $\s^{q^m}(\in Y)$ is still transitive on $\P$ and so is also a cyclic isomorphism of $\F$. Therefore replacing $\s$ by some power of $\s$ if necessary, we may assume $r|k$ for each prime divisor $r$ of the order $o(\s)$. \end{proof} \begin{remark}\label{ordersre} Let $\F=(\K_{p^d},\P)$ be a circulant homogeneous factorisation of index $k$. For convenience we will assume from now on that, for a cyclic isomorphism $\s$ of $\F$, $\s$ fixes the point 1. Moreover if $r|k$ for each prime divisor $r$ of the order $o(\s)$, then we say the cyclic isomorphism $\s$ \emph{satisfies Lemma \ref{orders}}. \end{remark} Suppose further that the circulant homogeneous factorisation $(\K_{p^d},\P)$ is normal, that is there exists a cyclic isomorphism $\s$ normalising the regular subgroup $Z_{p^d}$. Hence $\s$ can be viewed as an automorphism of the group $Z_{p^d}$, that is $\s \in \Aut(Z_{p^d}) \cong Z_{p^{d-1}(p-1)}$. \begin{construction}\label{con1} Let $p^d$ be an odd prime power such that $d\ge 1$ and $k\ge 2$ a positive integer such that $k|(p-1)$. Suppose that $\s\in \Aut(Z_{p^d})$ such that each prime divisor of $o(\s)$ divides $k$ and $k|o(\s)$. In particular $(o(\s), p)=1$. Since $\Aut(Z_{p^d}) \cong Z_{p^{d-1}}\times Z_{p-1}$, $\s$ belongs to the cyclic subgroup of order $p-1$ and hence $\s$ acts semiregularly on $Z_{p^d}\setminus\{1\}$. Let $\D_1,\ldots, \D_t$ be the orbits of $\s$ on $Z_{p^d}\setminus\{1\}$. As $k|o(\s)$, $\s^k$ divides each $\D_i$ into $k$ orbits, say $\D_{i,1},\D_{i,2},\ldots,\D_{i,k}$. Relabeling if necessary, we may assume that $\D_{i,j}^{\s}=\D_{i,j+1}$ where $i\in\{1,\ldots,t\}, j\in\{1,\ldots,k\}$ (reading the second subscript modulo $k$). For any $j_1,\ldots,j_t\in \{1,\ldots,k\}$, let $$P_1(1)= \D_{1,j_1}\cup \D_{2,j_2}\cup\cdots\cup\D_{t, j_t}.$$ For $i=2,\ldots,k$, let $$P_i(1)=P_1(1)^{\s^{i-1}}= \D_{1,j_1+(i-1)}\cup \D_{2,j_2+(i-1)}\cup\cdots\cup\D_{t, j_t+i-1}.$$ Then $\P(1) =\{P_1(1),\ldots,P_k(1) \}$ is a $\s$-invariant partition of $Z_{p^d}\setminus\{1\}$. For each $i$, let $\G_i =\Cay(Z_{p^d}, P_i(1))$, let $P_i $ be the set of arcs of the circulant $\G_i $, and let $\P =\{P_1,\ldots,P_k\}$. By Lemma \ref{pointstab} (2) (taking $G$ as $\la Z_{p^d}, \s\ra$), $\F=(\K_{p^d},\P )$ is a normal circulant homogeneous factorisation of index $k$ and $\s$ is a cyclic isomorphism of this factorisation. Denote $J=\{j_1,\ldots,j_t\}$. Since this construction $\F$ depends on the choice of $\s$ and $J$, we also denote this construction by $\F_{\s, J}$. \end{construction} Note that there do exist $p, d, k,\s$ satisfying the conditions of Construction \ref{con1}. Conversely, suppose that $(\K_{p^d},\P)$ is a normal circulant homogeneous factorisation of index $k$. Then each factor digraph $\G_i$ is a circulant $\Cay(Z_{p^d}, P_i(1))$ where $P_i(1)=\{\a\in Z_n| (1,\a)\in P_i\}$. Let $\s\in \Aut(Z_{p^d})$ be a cyclic isomorphism. As proved in Lemma \ref{orders}, we may assume that each prime divisor of the order $o(\s)$ divides $k$. Therefore $\s$ induces a transitive action on $\P(1)=\{P_1(1),\ldots,P_k(1)\}$ and $\s^k$ fixes each $P_i(1)$ for $i=1,\ldots,k$. As defined above in Construction \ref{con1}, let $\D_1,\ldots, \D_t$ be the orbits of $\s$ on $Z_{p^d}\setminus\{1\}$. And for each $i$, $\s^k$ divides $\D_i$ into $k$ orbits, say $\D_{i,1},\D_{i,2},\ldots,\D_{i,k}$ such that $\D_{i,j}^{\s}=\D_{i,j+1}$. It is easy to show that there exists $j_1,\ldots,j_t\in \{1,\ldots,k\}$ such that $P_1(1)= \{\D_{1,j_1}\cup \D_{2,j_2}\cup\cdots\cup\D_{t, j_t}\}$ and $P_i(1)=P_1(1)^{\s^{i-1}}$ as in Construction \ref{con1}. Therefore Construction~\ref{con1} provides us with a method for constructing all normal circulant homogeneous factorisations of order $p^d$, we write this result in the following proposition. \begin{prop}\label{normalcon}Let $\F$ be a normal circulant homogeneous factorisations of order $p^d$ and index $k$. And let $\s\in \Aut(Z_{p^d})$ be a cyclic isomorphism of $\F$ which satisfies Lemma \ref{orders}. With above notation, there exists $J=\{j_1,\ldots,j_t\}$ such that $\F=\F_{\s,J}$ which is defined in Construction \ref{con1}. \end{prop} We will need the following easy lemma for the proof of the main theorem. \begin{lemma}\label{auto} Let $p^d$ be an odd prime power such that $d\ge 2$, and let $\s\in \Aut(Z_{p^d})$ such that $o(\s)|(p-1)$. Let $Z_{p^i}\le Z_{p^d}$ be a subgroup. Then (1) $o(\s|_{Z_{p^i}})=o(\s)$. (2) Let $\bar \s \in \Aut(Z_{p^d}/Z_{p^i})$ be the automorphism of the quotient group induced by $\s$. Then $o(\s)=o(\bar \s)$. \end{lemma} \begin{proof}(1) Suppose $\Aut(Z_{p^d})=\la \mu \ra\times \la \g\ra=Z_{p-1}\times Z_{p^{d-1}}$. Then $\mu$ is a product of $\frac{p^d-1}{p-1}$ disjoint $(p-1)$-cycles acting on $Z_{p^d}\setminus \{1\}$. By assumption $\s \in \la\mu\ra$ and hence $o(\s|_{Z_{p^i}})=o(\s)$. (2) It is easy to check that $\Aut(Z_{p^d}/Z_{p^i})= \Aut(Z_{p^d})/\la \g^{p^{d-1-i}}\ra$ and so $o(\s)=o(\bar\s)$. \end{proof} \begin{lemma}\label{use} Suppose that $(\K_{p^d},\P)$ is a normal circulant homogeneous factorisation of index $k$ and $\s\in \Aut(Z_{p^d})$ is a cyclic isomorphism satisfying Lemma \ref{orders}. Let $\t \in Aut(Z_{p^d})$ such that $k|o(\t)$ and each prime divisor of $o(\t)$ divides $k$. Then $\t$ is a cyclic isomorphism of $(\K_{p^d},\P)$ if and only if $o(\sigma)=o(\t)$. \end{lemma} \begin{proof} By assumption we may assume that $o(\s)=mk, o(\t)=nk$ where $m, n$ are positive integers and each prime divisor of $m$ and $n$ divides $k$. Suppose first that $o(\s)=o(\t)$. Since $\Aut(Z_{p^d})$ is cyclic, $\t=\s^l$ for some integer $l$ such that $(l, o(\t))=1$. This implies $(l,k)=1$. Since $\s$ is transitive on $\P$ and $|\P|=k$, so is $\t$. Therefore $\t$ is a cyclic isomorphism of $(\K_{p^d},\P)$. Conversely, suppose that $\t$ is a cyclic isomorphism. Then $\t$ is transitive on $\P$. Let $H=\la\s,\t\ra$. Then $H$ is transitive on $\P$. Note that $\s, \t\in \Aut(Z_{p^d})\cong Z_{(p-1)p^{d-1}}$, we have that $H=\la\a\ra$ where $\a$ generates $H$ and $o(\a)=\frac{mk\cdot nk}{(m,n)k}=\frac{mn}{(m,n)}k$. Suppose that $m\ne n$, without loss of generality, we may assume $\frac{m}{(m,n)}\ne 1$ and $\t=\a^{\frac{m}{(m,n)}}$. Since both $\a$ and $\t$ are transitive on $\P$, $(k,\frac{m}{(m,n)})=1$. However by assumption each prime divisor of $m$ divides $k$, a contradiction. Therefore $m=n$ and $o(\s)=o(\t)$. \end{proof} \begin{lemma}\label{normalcyc}Suppose that $\F=(\K_{p^d},\P)$ is a normal circulant homogeneous factorisation of index $k$ where $\P=\{P_1,..,P_k\}$. Let $\s$ be a cyclic isomorphism (not required to be a group automorphism) such that $\s: P_i\to P_{i+1}$ (reading the subscript modulo $k$). Then there exists a cyclic isomorphism $\t\in \Aut(Z_{p^d})$ satisfying Lemma \ref{orders} and $\t: P_i\to P_{i+1}$ too. \end{lemma} \begin{proof} Since $\F$ is normal, by definition there exists a cyclic isomorphism $\t\in \Aut(Z_{p^d})$ satisfying Lemma \ref{orders}. Consider $Y=\la \hat Z_{p^d}, \s,\t\ra$ and let $X$ be the kernel of $Y$ acting on $\P$. Let $\bar \s=\s^{\P}$ and $\bar \t=\t^{\P}$. Then $Y/X=\la \bar\s \ra=\la\bar\t\ra$, and hence $\bar\s=\bar\t^l$ for some positive integer. Replacing $\t$ by $\t^l$, we have that $\t: P_i\to P_{i+1}$ as required. \end{proof} Lastly in this section we give examples of non-normal circulant homogeneous factorisations of order $p^2$. Note that there do exist $p, k, \s_1, \s_2$ satisfying the conditions of the following proposition. \begin{prop}\label{nonnormal}Let $p$ be an odd prime and $k(\ge 2)$ a positive integer such that $k|(p-1)$. Suppose further that $\s_1, \s_2\in \Aut(Z_{p})$ such that $o(\s_1)=k$ and $o(\s_2)=mk$ where $m\ge 2$ and each prime divisor of $m$ divides $k$. By Construction \ref{con1}, there exist circulant homogeneous factorisations $\F_i $ of index $k$ and order $p$ such that $\s_i$ is a cyclic isomorphism of $\F_i$ respectively. Take $\F=\F_1[\F_2]$. Then $\F$ is a non-normal circulant homogenous factorisation of order $p^2$. \end{prop} \begin{proof} By Lemma \ref{lexi} $\F$ is a circulant homogeneous factorisation of order $p^2$. Suppose conversely that $\F$ is normal and $\s \in \Aut(Z_{p^2})$ is a cyclic isomorphism of $\F$ satisfying Lemma \ref{orders}. By Remark \ref{lexire}, $\F_2$ is the sub-factorisation induced on the block $Z_p$. By Lemma \ref{block} (2), $\s|_{Z_{p}}\in \Aut(Z_{p})$ is also a cyclic isomorphism of $\F_2$. By Lemma \ref{use}, $o(\s|_{Z_{p}})=o(\s_2)$. It follows from Lemma \ref{auto} that $o(\s_2)=o(\s)$. On the other hand, $\F_1$ is the quotient factorisation of the block system $\{gZ_p|g\in Z_{p^2}\}$ by Remark \ref{lexire}, and the induced $\bar \s\in \Aut(Z_{p^2}/Z_{p})$ is also a cyclic isomorphism of $\F_1$. Still by Lemma \ref{use} and Lemma \ref{auto}, we have $o(\s_1)=o(\bar\s)=o(\s)$ which contradicts the fact that $o(\s_1)\ne o(\s_2)$. Therefore $\F$ is not normal. \end{proof} \section{Proof of Theorem \ref{mainthm}} We first study the structures of circulant homogeneous factorisations of order $p^d$. \begin{lemma}\label{step1} Let $(\K_{p^d},\P, X, Y)$ be a circulant homogeneous factorisation of index $k$, and let $\s\in Y$ be a cyclic isomorphism. Let $\G_i=\Cay(Z_{p^d}, S_i)$ be the factor digraphs where $1\le i\le k$. Then either $\hat Z_{p^d}\lhd Y$ and $\s\in\Aut(Z_{p^d})$, or for any $i\in \{1,\ldots,k\}$ and any $s\in S_i$ with $o(s)=p^d$, $sZ_{p}\subset S_i$. \end{lemma} \begin{proof} If $d=1$ then $Y$ is a soluble primitive c-group. It follows from Corollary \ref{X-prim} that $\hat Z_{p}\lhd Y\le \AGL(1,p)$ and $\s\in \Aut(Z_p)$. Next suppose that $d\ge 2.$ Let $X_1$ and $Y_1$ be the point stabilizers of $1$ in $X$ and $Y$ respectively. Then $Y_1=\la X_1, \s\ra$ and suppose that $\s: S_i\to S_{i+1} (1\le i\le k)$, reading the subscript modulo $k$. First take any $g\in S_1$ with $o(g)=p^d$. Consider the orbital digraph $\G_g$ of $Y$ with arc set $\D=(1,g)^Y$. Then $\G_g=\Cay(Z_{p^d},S_{1g}\cup S_{2g}\cup\cdots \cup S_{kg})$ where $S_{1g}=g^{X_1}$ is a subset of $S_1$ and $S_{ig}=(S_{1g})^{\s^{i-1}}\subseteq S_i$ for $i=2,\ldots,k$. Since $o(g)=p^d$, $\G_g$ is a connected $Y$-arc-transitive circulant of order $p^d$. By Lemma \ref{block} (4), $o(h)=p^d$ for any $h\in S_{1g}\cup S_{2g}\cup\cdots \cup S_{kg}$. In particular, $\G_g$ is not the complete graph $\K_{p^d}$. Applying Theorem \ref{arc-circ}, we have either $\hat{Z_{p^d}}\lhd Y$ and $\s\in \Aut(Z_{p^d})$ or $gZ_{p}\subset S_{1g}\cup S_{2g}\cup\cdots \cup S_{kg}$. In the latter case, we claim that $gZ_p\subset S_{1g}\subset S_1$. Note that $\mathcal B=\{xZ_p\mid x\in Z_{p^d}\}$ is a block system of $Y$. Suppose $gZ_p\cap S_{ig}\not=\varnothing$ where $k\ge i\ge 2$. Then $g^{\s^{1-i}} Z_p\cap S_{1g}\not=\varnothing$. Since $S_{1g}=g^{X_1}$, there exists $x\in X_1$ such that $g^x\in g^{\s^{1-i}} Z_p$. It follows that $(gZ_p)^{\s^{1-i}}=(gZ_p)^x$ and so $gZ_p$ is fixed by $x\s^{i-1}$. Since $gZ_p\ne Z_p$, $x\s^{i-1}$ fixes at least two blocks $gZ_p$ and $Z_p$, contradicting Lemma \ref{unique}. Hence $gZ_p\subset S_{1g}$. For any $g_i\in S_i (i\ge 2)$ with $o(g_i)=p^d$, we consider the orbital digraph $\G_{g_i}$ of $Y$ with arc set $\D=(1,g_i)^Y$ as well. Applying the same argument as above repeatedly, it is easy to deduce that either $\hat Z_{p^d}\lhd Y$ and $\s\in\Aut(Z_{p^d})$, or for any $i\in \{1,\ldots,k\}$, $sZ_{p}\subset S_i$ where $s\in S_i$ with $o(s)=p^d$. \end{proof} \begin{prop}\label{s sets} Let $(\K_{p^d},\P, X, Y)$ be a circulant homogeneous factorisation of index $k$, and let $\s\in Y$ be a cyclic isomorphism. Let $\G_i=\Cay(Z_{p^d}, S_i)$ be the factor digraphs. Then there exists $n\in \{1,\ldots,d\}$ such that $\hat{Z_{p^n}}\lhd Y_{Z_{p^n}}^{Z_{p^n}}$ and $\s|_{Z_{p^n}}\in\Aut(Z_{p^n})$. Moreover, for each $i\in \{1,\ldots,k\}$ and each $s\in S_i$ with $o(s)>p^n$, we have $sZ_p\subset S_i$. \end{prop} \begin{proof} If $d=1$, then take $n=1$, the result follows from Corollary \ref{X-prim}. Suppose next that $d\ge 2$. By Lemma \ref{step1}, we may assume that for any $i\in \{1,\ldots,k\}$, $sZ_p\subset S_i$ where $s\in S_i$ with $o(s)=p^d$. By Lemma \ref{block} (4), the subgroup $Z_{p^{d-1}}$ is a block of $Y$ and the induced factorisation $\F_{d-1}=(\K_{p^{d-1}}, \P_{Z_{p^{d-1}}}, X_{Z_{p^{d-1}}}^{Z_{p^{d-1}}}, Y_{Z_{p^{d-1}}}^{Z_{p^{d-1}}})$ is a circulant homogeneous factorisation where $Y_{Z_{p^{d-1}}}^{Z_{p^{d-1}}}=\la X_{Z_{p^{d-1}}}^{Z_{p^{d-1}}}, \s|_{Z_{p^{d-1}}}\ra$. For any $i\in \{1,\ldots,k\}$, let $\G_i(d-1)=\Cay(Z_{p^{d-1}}, S_i(d-1))$ be the corresponding factor digraphs of $\F_{d-1}$. Then $S_i(d-1)=\{s\in S_i | o(s)\le p^{d-1}\}$. Applying Lemma \ref{step1} to $\F_{d-1}$, we deduce that either $\hat{Z_{p^{d-1}}}\lhd Y_{Z_{p^{d-1}}}^{Z_{p^{d-1}}}$ and $\s|_{Z_{p^{d-1}}}\in \Aut(Z_{p^{d-1}})$, or for any $i\in \{1,\ldots,k\}$, $sZ_p\subset S_i$ where $s\in S_i$ with $o(s)=p^{d-1}$. Continuing in this fashion (note that $\hat{Z_p}\lhd Y_{Z_p}^{Z_p}$ by Lemma \ref{block} (3)) we have that an integer $n$ exists such that $n\in\{1,\ldots,d\}$, $\hat{Z_{p^n}}\lhd Y_{Z_{p^n}}^{Z_{p^n}},$ $\s|_{Z_{p^n}}\in\Aut(Z_{p^n})$ and for any $i\in \{1,\ldots,k\}$, $sZ_{p}\subset S_i$ where $s\in S_i$ with $o(s)>p^n$. \end{proof} Suppose $(\K_{p^d},\P, X, Y)$ is a circulant homogeneous factorisation and denote the factor digraphs by $\G_i=\Cay(Z_{p^d}, S_i)$. By Proposition \ref{s sets}, there exists $n\in \{1,\ldots,d\}$ such that $\hat{Z_{p^n}}\lhd Y_{Z_{p^n}}^{Z_{p^n}}$ and for each $i\in \{1,\ldots,k\}$ and each $s\in S_i$ with $o(s)>p^n$, $sZ_p\subset S_i$. Thus for any $i\in \{1,\ldots,k\}$, we divide the Cayley subset $S_i$ into the following two parts. Let \begin{equation}\label{s1s2}S_i^1=\{s\in S_i\mid o(s)\le p^n \} \mbox{ and } S_i^2=\{s\in S_i\mid p^d\ge o(s)\ge p^{n+1} \}.\end{equation} Then $S_i=S_i^1\cup S_i^2$. Note that we set $S_i^2=\varnothing$ if $n=d$. \begin{lemma}\label{induction}Suppose that $\F=(\K_{p^d},\P, X, Y)$ is a circulant homogeneous factorisation of index $k$ with $d\ge 2$, and let $\s\in Y$ be a cyclic isomorphism. For any $i\in\{1,\ldots,k\}$, let $\G_i=\Cay(Z_{p^d}, S_i)$ be the factor digraphs, and suppose that $\s: \G_i\to \G_{i+1}$ (reading the subscript modulo $k$). Suppose further that $n, S_i^1, S_i^2$ are defined as above in $(\ref{s1s2})$. Then there exists a factorisation $\F'=(\K_{p^d}, \P')$ satisfying the following conditions. \begin{itemize} \item[(i)] $\F'$ is also a circulant $(X, Y)$-homogeneous factorisation of index $k$. Let $\si_i=\Cay(Z_{p^d}, T_i)$ be the corresponding factor digraphs of $\F'$. Then $\s: \si_i\to \si_{i+1}$ is a cyclic isomorphism of $\F'$. \item[(ii)] For any $i\in \{1,\ldots,k\}$ and any $r\in T_i$ such that $o(r)>p$, we have $rZ_p\subseteq T_i$. (This implies $\F'$ is of lexicographic product form by Corollary \ref{lexico}.) \item[(iii)] For any $i\in \{1,\ldots,k\}$, let $T_i^2=\{r\in T_i | o(r)>p^n\}$. Then $T_i^2=S_i^2$. \item[(iv)] For any $i\in \{1,\ldots,k\}$, let $S_i^0=\{s\in S_i \mid o(s)=p\}$ and $ T_i^0=\{r\in T_i \mid o(r)=p\}.$ Then $T_i^0=S_i^0$. \end{itemize} \end{lemma} \begin{proof} If $n=1$, take $\F'=\F$. We next assume that $n\ge 2$. Let $X_n=X_{Z_{p^n}}^{Z_{p^n}}, Y_n=Y_{Z_{p^n}}^{Z_{p^n}}$ and let $\t=\s|_{Z_{p^n}}$. Then $Y_n=\la X_n, \t\ra$. By Lemma \ref{block} the induced sub-factorisation (on the block $Z_{p^n}$) $\F_{n}=(Z_{p^n},\P_{Z_{p^n}})$ is $(X_n, Y_n)$-homogeneous and $\t$ is a cyclic isomorphism of $\F_n$. By Proposition \ref{s sets}, $X_n=\hat Z_{p^n}\rtimes L$ where $L\le\Aut(Z_{p^n})$ and fixes each $S_i^1 (1\le i\le k)$ setwise. Moreover $\t\in \Aut(Z_{p^n})$ and $\t^k\in L$. Applying Lemma \ref{block} to $\F_n$, $\mathcal B_1=\{gZ_p\mid g\in Z_{p^n}\}$ forms a complete block system of $Y_n$ on $Z_{p^n}$. As $\t$ normalises $L$, $(gZ_p)^{L\t}=(gZ_p)^{\t L}$. For any $gZ_p\in\mathcal B_1$ such that $gZ_p\ne Z_p$, it follows from Lemma \ref{unique} that $g^{\t^i}Z_p\ne (gZ_p)^x$ for any $x\in L$ and $1\le ip^n$, $sZ_p\subset S_i$. Let $S_i^1=\{s\in S_i\mid o(s)\le p^n \}$ and $S_i^2=\{s\in S_i\mid p^d\ge o(s)\ge p^{n+1} \}$. Then $S_i=S_i^1\cup S_i^2$. By Lemma \ref{induction}, there exists a circulant $(X,Y)$ homogeneous factorisation $\F'=(\K_{p^d}, \P')$ such that $\s$ is also a cyclic isomorphism of $\F'$. Let $\si_i=\Cay(Z_{p^d}, T_i)$ be the corresponding factor digraphs of $\F'$. Then $\s: \si_i\to \si_{i+1},$ (reading the subscript modulo $k$). Setting $T_i^1=\{s\in T_i\mid o(s)\le p^n \}$ and $T_i^2=\{s\in T_i\mid p^d\ge o(s)\ge p^{n+1} \}$, we have $T_i^2=S_i^2$. Moreover, let $S_i^0=\{s\in S_i \mid o(s)=p\}$ and $ T_i^0=\{r\in T_i \mid o(s)=p\}.$ Then $T_i^0=S_i^0$ by Lemma \ref{induction}. By Corollary \ref{lexico} $\F'$ is of lexicographic product form. Suppose $l(\ge 1)$ is maximal such that $\F'= \F'_1[\F'_2]$ where $\F_2'$ is a circulant homogeneous factorisation of order $p^l$ and $\F_1'$ is a circulant homogeneous factorisation of order $p^{d-l}$. Then $\F_1'$ can not be a lexicographic product of two smaller circulants homogeneous factorisations. By induction, $\F_1'$ is normal. Suppose first that $l\ge n$. By Corollary \ref{lexico}, for each $i\in \{1,\ldots,k\}$, $rZ_{p^l}\subseteq T_i$ for any $r\in T_i^2$ with $o(r)> p^l$. Since $T_i^2=S_i^2 (1\le i\le k)$, we have $sZ_{p^l}\subseteq S_i$ for any $s\in S_i^2$ with $o(s)> p^l$. By Corollary \ref{lexico}, $\F= \F_1[\F_2]$ where $\F_2$ is a circulant homogeneous factorisation of order $p^l$ and $\F_1$ is a circulant homogeneous factorisation of order $p^{d-l}$. Suppose next that $l p^l$. By Remark \ref{lexire} we may suppose the factor digraphs of $\F'_1$ are the quotient Cayley digraphs $\ov\si_i =\Cay(Z_{p^d}/Z_{p^{l}},\ov {T_i})$ and $\ov {T_i}=\{\ov r=rZ_{p^{l}}\mid r\in T_i, o(r)>p^l\}$ where $1\le i\le k$. And the induced natural cyclic isomorphism $\bar \s:\ov T_i\to \ov T_{i+1}$. By induction, we have seen that $\F_1'$ is normal, and so by Lemma \ref{normalcyc} there exists a cyclic isomorphism $\bar\psi\in \Aut(Z_{p^d}/Z_{p^{l}})$ satisfying Lemma \ref{orders} such that $\bar \psi: \ov T_i\to \ov T_{i+1}$. By Lemma \ref{auto}, we may also assume that $\bar\psi$ is induced by $\psi\in \Aut(Z_{p^d})$ where $o(\psi)=o(\bar\psi)$. In particular $\psi: T_i^2\to T^2_{i+1}, (1\le i \le k,$ reading the subscript modulo $k$). Since $l p^l$, and so the normal circulant homogeneous factorisation $\mathcal A'=\mathcal A'_1[\mathcal A'_2]$ is also of lexicographic product type where $\A'_1$ is of order $p^{n-l}$ and $\A_2'$ is of order $p^l$. Again by Remark \ref{lexire}, $\A'_1$ is the quotient factorisation induced by $\A'$ on the block system $\{xZ_{p^l}|x\in Z_{p^n}\}$, and so the induced automorphism $\bar \t\in \Aut(Z_{p^n}/Z_{p^l})$ is a cyclic isomorphism of $\A'_1$. As $\t$ satisfies Lemma \ref{orders}, by Lemma \ref{auto}, $o(\bar\t)=o(\t)$. On the other hand, since $Z_{p^n}/Z_{p^{l}}< Z_{p^d}/Z_{p^{l}}$, we can also view $\A'_1$ as the induced sub-factorisation by $\F_1'$ on the block $Z_{p^n}/Z_{p^{l}}$, and so $\bar \psi|_{Z_{p^n}/Z_{p^{l}}}$ is also a cyclic isomorphism of $\A'_1.$ This forces $o(\psi|_{Z_{p^n}})=o(\bar\psi|_{Z_{p^n}/Z_{p^{l}}})=o(\bar \t)=o(\t)$ by Lemma \ref{auto} and Lemma \ref{use}. Next we apply Lemma \ref{use} to $\A'$, then $\psi|_{Z_{p^n}}$ is also a cyclic isomorphism of $\A'$ and hence $\psi|_{Z_{p^n}}$ induces a transitive action on $\{T_i^1| i=1,\ldots,k\}$. Note that $\bar \psi: \ov T_i\to \ov T_{i+1} (1\le i\le k)$ where $\ov {T_i}=\{\ov r=rZ_{p^{l}}\mid r\in T_i, o(r)>p^l\}$ and $l