\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \numberwithin{equation}{section} \theoremstyle{plain} \newtheorem{thm}[equation]{Theorem} \newtheorem{lem}[equation]{Lemma} \newtheorem{cor}[equation]{Corollary} \newtheorem{prop}[equation]{Proposition} \theoremstyle{definition} \newtheorem{defin}[equation]{Definition} \newtheorem{conj}[equation]{Conjecture} \newtheorem{notn}[equation]{Notation} \newtheorem{eg}[equation]{Example} \newtheorem{question}[equation]{Question} \newtheorem{prob}[equation]{Problem} \theoremstyle{remark} \newtheorem{hey}[equation]{Remark} \def\mod{{\rm mod\ }} \def\Aut{{\rm Aut}} \def\la{\langle} \def\ra{\rangle} \def\Z{{\mathbb Z}} \def\Cay{{\rm Cay}} \def\Stab{{\rm Stab}} \def\dist{{\rm dist}} \def\natural {{\mathbb N}} \def\hatZ{{\hat{\mathbb Z}^n}} \newcommand{\GL}{\mathsf{GL}} % \newcommand{\Q}{\mathbb{Q}} \DeclareMathOperator{\PG}{PG} \newcommand{\SL}{\mathsf{SL}} \newcommand{\PGL}{\mathsf{PGL}} \newcounter{case} \newenvironment{case}{\refstepcounter{case} \medskip \indent {\bf Case \textup{\thecase.}} \it\ignorespaces}{\unskip} \renewcommand{\thecase}{\arabic{case}} \title{The CI problem for infinite groups} \author{Joy Morris\thanks{This research was supported in part by the National Science and Engineering Research Council of Canada, Discovery Grant 238552-2011}\\ \small Department of Mathematics and Computer Science \\[-0.8ex] \small University of Lethbridge \\[-0.8ex] \small Lethbridge, AB. T1K 3M4. Canada\\ \small \tt joy.morris@uleth.ca} \date{\dateline{Feb 23, 2015}{Oct 16, 2016}\\ \small Mathematics Subject Classifications: 05C25, 20B27} \begin{document} \maketitle \begin{abstract} A finite group $G$ is a DCI-group if, whenever $S$ and $S'$ are subsets of $G$ with the Cayley graphs Cay$(G,S)$ and Cay$(G,S')$ isomorphic, there exists an automorphism $\varphi$ of $G$ with $\varphi(S)=S'$. It is a CI-group if this condition holds under the restricted assumption that $S=S^{-1}$. We extend these definitions to infinite groups, and make two closely-related definitions: an infinite group is a strongly (D)CI$_f$-group if the same condition holds under the restricted assumption that $S$ is finite; and an infinite group is a (D)CI$_f$-group if the same condition holds whenever $S$ is both finite and generates $G$. We prove that an infinite (D)CI-group must be a torsion group that is not locally-finite. We find infinite families of groups that are (D)CI$_f$-groups but not strongly (D)CI$_f$-groups, and that are strongly (D)CI$_f$-groups but not (D)CI-groups. We discuss which of these properties are inherited by subgroups. Finally, we completely characterise the locally-finite DCI-graphs on $\mathbb Z^n$. We suggest several open problems related to these ideas, including the question of whether or not any infinite (D)CI-group exists. \end{abstract} \section{Introduction} Although there has been considerable work done on the Cayley Isomorphism problem for finite groups and graphs, little attention has been paid to its extension to the infinite case. \begin{defin} A Cayley (di)graph $\Gamma=\Cay(G;S)$ is a {\em (D)CI-graph} if whenever $\phi: \Gamma\to \Gamma'$ is an isomorphism, with $\Gamma'=\Cay(G;S')$, there is a group automorphism $\alpha$ of $G$ with $\alpha(S)=S'$ (so that $\alpha$ can be viewed as a graph isomorphism). \end{defin} Notice that since $\Aut(\Gamma)=\Aut(\overline{\Gamma})$ (where $\overline{\Gamma}$ denotes the complement of $\Gamma$) and any isomorphism from $\Gamma$ to $\Gamma'$ is also an isomorphism from $\overline{\Gamma}$ to $\overline{\Gamma'}$, a graph is a (D)CI-graph if and only if its complement is also a (D)CI-graph. Since at least one of $\Gamma$ and $\overline{\Gamma}$ must be connected, the problem of determining (D)CI-graphs can be reduced to the connected case. This definition extends to a definition for groups. \begin{defin} A group $G$ is a {\em (D)CI-group} if every Cayley (di)graph on $G$ is a (D)CI-graph. \end{defin} These definitions (in the undirected case) as well as the following equivalent condition for a graph to be a (D)CI-graph, first appeared in work by Babai \cite{Baba-1}, extending a research problem posed by \`{A}d\`{a}m for cyclic groups \cite{Adam}. There has been a large body of work on this topic, and Li published a survey paper \cite{Li-survey} outlining many of the results. \begin{thm}[\cite{Baba-1}]\label{CI-alt} A Cayley (di)graph $\Gamma$ on the group $G$ is a (D)CI-graph if and only if any two regular copies of $G$ in $\Aut(\Gamma)$ are conjugate. \end{thm} In the infinite case, it is natural to consider locally-finite (di)graphs: that is, (di)graphs whose valency is finite. When studying Cayley (di)graphs, this means that the set $S$ is finite. However, restricting our consideration to this case complicates matters, as the complement of a locally-finite (di)graph is not locally-finite. For this reason, the standard argument made above that reduces the finite problem to the case of connected (di)graphs, does not apply to infinite (di)graphs that are locally-finite. In other words, if one wishes to study this problem in the context of locally-finite (infinite) (di)graphs, it is necessary to consider disconnected as well as connected (di)graphs. For this reason, we give two new definitions. In the case of finite (di)graphs, both of these definitions coincide with the definition of a (D)CI-group, but in the infinite case they do not, and are themselves (we believe) worthy of study as natural generalisations of finite (D)CI-groups. \begin{defin} A finitely-generated group $G$ is a {\em (D)CI$_f$-group} if every connected locally-finite Cayley (di)graph on $G$ is a (D)CI-graph. \end{defin} Note that it is not possible to have a connected locally-finite Cayley (di)graph on a group that is not finitely-generated, so the requirement that the group be finitely-generated only serves to avoid a situation where all non-finitely-generated groups are vacuously CI$_f$-groups. \begin{defin} A group $G$ is a {\em strongly (D)CI$_f$-group} if every locally-finite Cayley (di)graph on $G$ is a (D)CI-graph. \end{defin} It should be apparent from these definitions that $$\text{(D)CI-group} \Rightarrow \text{strongly (D)CI$_f$-group}$$ and if we restrict our attention to finitely-generated groups, $$\text{strongly (D)CI$_f$-group} \Rightarrow \text{(D)CI$_f$-group}.$$ In this paper we will construct examples of groups that are (D)CI$_f$-groups but not strongly (D)CI$_f$-groups (despite being finitely generated) and groups that are strongly (D)CI$_f$-groups but not (D)CI-groups, so these definitions are interesting. We further study these classes, particularly in the case of infinite abelian groups, including a complete characterisation of the locally-finite graphs on $\Z^n$ that are (D)CI-graphs. We also prove that no infinite abelian group is a (D)CI-group, and that any (D)CI-group must be a torsion group that is not locally finite. We leave open the question of whether or not any infinite (D)CI-groups exist. The first paper we are aware of that solves a CI problem for infinite graphs was by M\"{o}ller and Seifter \cite{MS}. Since they were actually considering the problem of digraphical regular representations (DRRs) of infinite finitely-generated groups, they considered only connected graphs. In the course of determining the DRRs for $\Z$, the results they proved imply (in our terms) that $\Z$ is a CI$_f$-group. In the only prior work that we are aware of that is aimed specifically at solving the CI problem for infinite graphs, Ryabchenko \cite{Ryab} uses the standard definition (the same one we gave above) for a CI-group, and claims to have proven that every finitely-generated free abelian group is a CI-group. It is clear from his proofs that what he in fact shows is that $\Z$ is a strongly CI$_f$-group, and $\Z^n$ is a CI$_f$-group. We will restate the results he actually proves in that paper using our terminology, as well as pointing out several consequences of his proofs that he did not mention. We also show that $\Z^n$ is not a strongly (D)CI$_f$-group if $n>1$. Ryabchenko cites a paper by Chuesheva as the main motivation for his paper, but the journal is obscure and the url he provides no longer exists, so we were not able to obtain a copy of this paper. L\"{o}h has published a paper \cite{Loeh} on the related question of when a graph can be represented as a Cayley graph on more than one finitely-generated infinite abelian group. We will proceed from the strongest property to the weakest. In Section 2, we will consider infinite (D)CI-groups, and prove that various large families of infinite groups cannot be (D)CI-groups; specifically, we show that any infinite CI-group must be a torsion group that is not locally finite. (Since every DCI-group is a CI-group, this result carries over to the directed case.) In Section 3, we consider strongly CI$_f$-groups. We construct an infinite family of such groups, but also prove that $\Z^n$ is not a strongly CI$_f$-group for $n>1$. We show that every finitely-generated subgroup of a strongly CI$_f$-group is a CI$_f$-group, but leave open the question of whether or not all subgroups of strongly CI$_f$-groups are strongly CI$_f$-groups. In Section 4, we consider CI$_f$-groups. We show that without the condition of local-finiteness, connectedness is not sufficient to ensure that a Cayley graph on $\Z^n$ is a CI-graph. We note that $\Z^n$ is a CI$_f$-group for every $n$. In Section 5, we include the results from \cite{Ryab}, the first of which is also attributable to \cite{MS}. We have slightly generalised as well as correcting the statements from \cite{Ryab} (which can be done using the same proofs), and include some easy corollaries of his proofs, showing that every locally-finite Cayley (di)graph on $\Z^n$ is a normal Cayley (di)graph, and in fact has a unique regular subgroup isomorphic to $\Z^n$. Finally, in Section 6, we completely characterise the locally-finite Cayley graphs on $\Z^n$ that are CI-graphs. In particular, we show that if $n \neq 2$ then a (nonempty) locally-finite Cayley graph on $\Z^n$ is a (D)CI-graph if and only if it is connected, and that a (nonempty) locally-finite Cayley graph on $\Z^2$ is a (D)CI-graph if and only if it either \begin{itemize} \item is connected, or \item has exactly two connected components, and the connection set $S$ is invariant under some automorphism of order $3$ of $\langle S\rangle$. \end{itemize} \section{CI-groups} In this section of the paper, we demonstrate that various families of infinite groups are not CI-groups. Since all DCI-groups are also CI-groups, this implies that these groups are not DCI-groups. We also discuss the open questions that remain. \begin{hey}[\cite{Baba-Fran-1}]\label{CI-hereditary} We observe that the property of being a CI-group is inherited by subgroups. \end{hey} There is a standard construction for the above fact, used for finite groups, that works equally well for infinite groups if we are not requiring that graphs be locally finite. That is: if $H 1$. We in fact prove a stronger result, for use later in this paper when we precisely characterise locally-finite graphs in Theorem~\ref{ZnCIiff}. \begin{prop}\label{non-CI-on-Zn} Let $n>1$, and let $\Gamma=\Cay(\Z^n;S)$ be any Cayley (di)graph on $\Z^n$ such that the number of connected components of (the underlying graph of) $\Gamma$ is either infinite, or is divisible by $p^2$ for some prime $p$. Then $\Gamma$ is not a (D)CI-graph. \end{prop} \begin{proof} For this proof, we use the formulation of the CI problem given in Theorem \ref{CI-alt}. Let $G=\langle S \rangle$, and let $\Gamma_0=\Cay(G;S)$ (so this is connected). Then $\Aut(\Gamma)$ will either be $S_{\Z} \wr \Aut(\Gamma_0)$, or $S_n \wr \Aut(\Gamma_0)$, where $n$ is finite and there is some prime $p$ such that $p^2 \mid n$. Consider the subgroup of the appropriate symmetric group that is induced by the natural action of $\Z^n$ on the connected components of $\Gamma$. Clearly this will be a regular abelian subgroup that is either countably infinite, or of order $n$. There are many nonisomorphic countably infinite regular abelian subgroups of $S_{\Z}$ ($\Z$ and $\Z_2 \times \Z$, for example). Likewise, there are at least two nonisomorphic regular subgroups of $S_n$ ($\Z_p \times \Z_{n/p}$ and $\Z_{p^2} \times \Z_{n/p^2}$). Since $n>1$, each of these can be expanded to a regular action isomorphic to $\Z^n$ in $\Aut(\Gamma)$. Since the subgroups are nonisomorphic, they are not conjugate in the appropriate symmetric group, so the expanded actions on $\Gamma$ are not conjugate in $\Aut(\Gamma)$. Thus $\Gamma$ is not a (D)CI-graph. \end{proof} \begin{cor}\label{Zn-not-str-CI} The group $\Z^n$ is not a strongly CI$_f$-group for $n >1$. \end{cor} \begin{proof} When $n>1$, it is easy to construct finitely-generated Cayley graphs on $\Z^n$ for which the number of connected components is either countably infinite, or divisible by a square. For example, $\Gamma_1=\Cay(\Z^n;\{\pm (1,0,\ldots, 0)\})$ has a countably infinite number of connected components, while $\Gamma_2$, the Cayley graph on $\Z^n$ whose connection set is the standard generating set for $\Z^n$ (together with inverses) with the first generator (and its inverse) replaced by $\pm (p^2,0, \ldots, 0)$, will have $p^2$ connected components. So Proposition \ref{non-CI-on-Zn} is sufficient. Had we only wanted to show that $\Z^n$ is not a strongly CI$_f$-group for $n>1$, we could have pointed out that $\Gamma_1 \cong \Cay(\Z^n;\{\pm(2,0,\ldots,0)\})$ but not via a group automorphism of $\Z^n$, or similarly that $\Gamma_2$ is isomorphic to the Cayley graph on $\Z^n$ whose connection set is the standard generating set for $\Z^n$ (together with inverses) with the first generator (and its inverse) replaced by $\pm(p,0,\ldots,0)$, and the second generator (and its inverse) replaced by $\pm (0,p,\ldots, 0)$, but not via a group automorphism of $\Z^n$. \end{proof} Having determined the status of free abelian groups, we turn our attention to the opposite end of the spectrum of infinite abelian groups and consider torsion groups. First we prove a restriction on torsion groups that are strongly CI$_f$-groups (dropping the abelian constraint for the time being). \begin{lem}\label{torsion-str-cont-finite-CI} Suppose that $G$ is a locally-finite torsion group that is a strongly CI$_f$-group. Then every finite subgroup of $G$ is a CI-group. Furthermore, for $p \ge 5$ the Sylow $p$-subgroups of $G$ are elementary abelian, and the Sylow $3$-subgroups are either cyclic of order at most 27, or elementary abelian. \end{lem} \begin{proof} Since $G$ is a strongly CI$_f$-group, an argument similar to that of Remark \ref{CI-hereditary} shows that every finite subgroup must be a CI-group. Babai and Frankl \cite{Baba-Fran-1} showed that for $p \ge 5$ the only finite $p$-groups that are CI-groups are elementary abelian, and the finite $3$-groups that are CI-groups are either cyclic of order at most 27, or elementary abelian. Furthermore, Muzychuk \cite{Muzy-elem-abel} proved that elementary abelian groups of sufficiently high rank are not CI-groups. Since $G$ is locally-finite and the results just stated imply that every finite $p$-subgroup has bounded order, there must be a finite number of generators that contribute to any $p$-group in $G$. In particular, this means that the $p$-groups in $G$ must all be finite. Thus by \cite{Baba-Fran-1} again, we obtain the desired conclusion. \end{proof} In addition to $\Z$ which seems to be a sporadic example, we have been able to find an infinite family of groups that are strongly CI$_f$-groups. \begin{thm}\label{abelian-torsion-str} Let $G$ be a countable abelian torsion group. Then $G$ is a strongly (D)CI$_f$-group if and only if every finite subgroup of $G$ is a (D)CI-group. \end{thm} \begin{proof} Abelian torsion groups are locally-finite, so necessity is shown in Lemma \ref{torsion-str-cont-finite-CI}. For the converse, suppose that $G$ is a countable abelian torsion group, and every finite subgroup of $G$ is a (D)CI-group. By Lemma \ref{torsion-str-cont-finite-CI}, when $p \ge 3$ the Sylow $p$-subgroups of $G$ are elementary abelian, or cyclic of order at most 27. To understand the Sylow $2$-subgroups and to improve our understanding of the Sylow 3-subgroups, we use Lemma \ref{torsion-str-cont-finite-CI} to note that they must be Sylow $2$-subgroups of finite (D)CI-groups. Aside from some finite exceptional groups whose order does not exceed $2^5 3^2=288$, it is known that in any finite abelian (D)CI-group $H$, every Sylow $p$-subgroup of $H$ must be either $\Z_4$, or elementary abelian. This strengthening of the work of Babai and Frankl \cite{Baba-Fran-1} for $p=2$ and $p=3$ is mentioned in \cite{Li-Lu-Palf}. Since $G$ has arbitrarily large finite subgroups all of which are (D)CI-groups, this implies that every Sylow $p$-subgroup of $G$ must be either $\Z_4$, or elementary abelian. Let $\Gamma=\Cay(G;S)\cong \Gamma'=\Cay(G;S')$, with $S$ finite. Since $G$ is an abelian torsion group, $\langle S \rangle$ must be finite, and $\langle S' \rangle$ has the same finite order, so $H=\langle S, S' \rangle$ is a finite subgroup of $G$, so is a (D)CI-group. Clearly $\Cay(H;S) \cong \Cay(H;S')$, so as $H$ is a (D)CI-group, there is an automorphism $\alpha$ of $H$ taking $S$ to $S'$. Since $G$ is countable, list the elements of $G$: $g_1, g_2, \ldots$, so that $H=\{g_1, \ldots, g_{|H|}\}$ (the rest of the list can be arbitrary). For $i \ge |H|$, define $G_i = \langle g_1, \ldots, g_i\rangle$ (so $G_{|H|}=H$). We claim that for $i \ge |H|$, there is an automorphism $\alpha_i$ of $G_i$ that takes $S$ to $S'$ (so is an isomorphism from $\Cay(G_i;S)$ to $\Cay(G_i;S')$) such that for every $j \in \{|H|, |H|+1, \ldots, i\}$, the restriction of $\alpha_i$ to $G_j$ is $\alpha_j$. We prove this claim by induction. The base case of $i=|H|$ has been established. By induction, we can assume that we have $\alpha_{i-1}$ such that the restriction of $\alpha_{i-1}$ to $G_j$ is $\alpha_j$ for every $|H|\le j \le i-1$, so we need only find $\alpha_i$ such that the restriction of $\alpha_i$ to $G_{i-1}$ is $\alpha_{i-1}$. Since $G_i$ is abelian, it is the direct product of its Sylow $p$-subgroups, so if we show that the action of $\alpha_{i-1}$ on any Sylow $p$-subgroup of $G_{i-1}$ is the restriction of the action of $\alpha_i$ on the corresponding Sylow $p$-subgroup of $G_i$, this will suffice. Let $P_i$ be a Sylow $p$-subgroup of $G_i$, and $P_{i-1}$ the corresponding Sylow $p$-subgroup of $G_{i-1}$. If $P_{i-1}=P_i$ then we define $\alpha_i(g)=\alpha_{i-1}(g)$ for every $g \in P_i=P_{i-1}$. If $P_i$ is elementary abelian and $P_i \neq P_{i-1}$, then since $G_i=\langle G_{i-1},g_i\rangle$ is abelian, we must have $P_i\cong P_{i-1} \times \Z_p$. In this case use this representation, and for any $(g,h) \in P_i=P_{i-1} \times\Z_p$, define $\alpha_i(g,h)=(\alpha_{i-1}(g),h)$. The only remaining possibility is that $p=2$, $P_i=\Z_4$, and $P_{i-1}=\Z_2$. In this case, define $\alpha_i(g)=g$ for every $g \in P_i$. Since $\alpha_{i-1}$ must act as the identity on $P_{i-1}\cong \Z_2$, the restriction of $\alpha_i$ to $P_{i-1}$ is again $\alpha_{i-1}$. Now we define $\alpha'$, which will be an automorphism of $G$ that takes $S$ to $S'$. For ease of notation, first define $\alpha_i =\alpha$ for $1 \le i \le |H|$. Now for any $g_i \in G$, define $\alpha'(g_i)=\alpha_i(g_i)$. We show that the map $\alpha'$ is an automorphism of $G$. Let $g_i, g_j \in G$ with $i\le j$. First, notice that because the restriction of $\alpha_j$ to $G_i$ is $\alpha_i$ (where $G_i=H$ for every $1 \le i \le |H|$), we have $\alpha_j(g_i)=\alpha_i(g_i)$. Now, $g_i, g_j, g_ig_j \in G_j$ and $$\alpha'(g_i)\alpha'(g_j)=\alpha_i(g_i)\alpha_j(g_j)=\alpha_j(g_i)\alpha_j(g_j)=\alpha_j(g_ig_j)=\alpha'(g_ig_j).$$ \end{proof} While the finite abelian (D)CI-groups have not been completely determined, elementary abelian groups of rank at most 4 are known to be DCI-groups \cite{Ted-Z_p3,Gods-Z_p2,Hira-Muzy,thesis,Turn-Zp}. So the preceding theorem gives us an infinite class of infinite strongly (D)CI$_f$-groups: namely, pick any infinite set of primes $Q$. For each $p \in Q$, take a cyclic $p$-group. Define $G$ to be the direct product of the chosen groups. Then $G$ is a strongly (D)CI$_f$-group. (It would be nice to be able to select an elementary abelian $p$-group of rank higher than one for at least some of the primes in $Q$; unfortunately, the question of whether or not finite direct products of most such groups are (D)CI-groups remains open.) It is, unfortunately, not clear whether the property of being a strongly (D)CI$_f$-group is necessarily inherited by subgroups of strongly (D)CI$_f$-groups. In the examples that we have found, it is inherited, since the only infinite subgroup of $\Z$ is $\Z$, and if $G$ is any group in the family of strongly (D)CI$_f$-groups described in Theorem \ref{abelian-torsion-str}, and $H$ is any infinite subgroup of $G$, then (by our structural characterisation of the family) $H$ is in the family, so $H$ is a strongly (D)CI$_f$-group. In general, though, we do not see why the following situation might not arise: $G$ is a strongly (D)CI$_f$-group, and for some infinite subgroup $H$ and some finite subsets $S, S'$ of $G$, $\Cay(G; S) \cong \Cay(G;S')$, but for every automorphism $\alpha$ of $G$ that takes $S$ to $S'$, we have $\alpha(H) \neq H$, and in fact no automorphism of $H$ takes $S$ to $S'$. \begin{question}\label{DCIf-closed} Is it true that every subgroup of a strongly (D)CI$_f$-group is a strongly (D)CI$_f$-group? \end{question} Note the answer to Question~\ref{DCIf-closed} is yes in the case of countable abelian torsion groups that are (D)CI$_f$-groups. If $G$ is such a group and $H \le G$, then $H$ is also a countable abelian torsion group (possibly finite) and by Theorem~\ref{abelian-torsion-str}, every finite subgroup of both $G$ and $H$ is a (D)CI-group, so that $H$ is a strongly (D)CI$_f$-group. We can at least say that when a subgroup of a strongly (D)CI$_f$-group is finitely-generated, it must be a (D)CI$_f$-groups. \begin{prop}\label{str-CI_f-to-CI_f} A finitely-generated subgroup of a strongly (D)CI$_f$-group is always a (D)CI$_f$-group. \end{prop} \begin{proof} Let $G$ be a strongly (D)CI$_f$-group, and let $H\le G$ be finitely generated. Suppose that $\langle S \rangle=H$, and $\Cay(H;S) \cong \Cay(H;S')$ for some subset $S'$ of $H$. Since $\Cay(H;S)$ (or the underlying undirected graph) is connected, we also have $\langle S' \rangle =H$. Clearly, $\Cay(G;S) \cong \Cay(G;S')$ since each is the disjoint union of $|G:H|$ copies of the original (di)graph. Since $G$ is a strongly (D)CI$_f$-group, there is an automorphism $\alpha$ of $G$ such that $\alpha(S)=S'$. Since $H=\langle S \rangle=\langle S' \rangle$, we must have $\alpha(H)=H$, so the restriction of $\alpha$ to $H$ is an automorphism of $H$ that takes $S$ to $S'$. \end{proof} \section{CI$_f$-groups} Although it was not the statement he gave, Ryabchenko \cite{Ryab} proved that $\Z^n$ is a CI$_f$-group for every $n$; that is, every finitely-generated free abelian group is a CI$_f$-group. We include a slight generalisation of his proof in Section \ref{sect-Ry}, as Corollary \ref{Zn-is-CI_f}. Currently, these are the only infinite (D)CI$_f$-groups that we know of, since the family of strongly (D)CI$_f$-groups determined in Theorem \ref{abelian-torsion-str} has no finitely-generated members. An interesting observation is that although connectedness is enough to ensure that a locally-finite Cayley graph on $\Z^n$ is a (D)CI-graph, it is not sufficient if the graph is not locally-finite. \begin{cor}\label{locally-infinite} Let $n>1$. Amongst connected Cayley (di)graphs on $\Z^n$ that are not locally finite, some will be (D)CI-graphs and some will not. \end{cor} \begin{proof} Corollary~\ref{Zn-is-CI_f} tells us that any such (di)graph for which the complement is locally finite and connected will be (D)CI, while Proposition \ref{non-CI-on-Zn} tells us that any such (di)graph for which the complement is locally finite with a number of connected components that is infinite or is not square-free, will not be (D)CI. In fact, later in Theorem~\ref{ZnCIiff}, we will see that any such (di)graph for which $n>2$ and the complement is locally finite and disconnected, or for which $n=2$ and the complement is locally finite and has more than 2 connected components, will not be (D)CI. \end{proof} Since subgroups of finitely-generated groups need not be finitely-generated, it is again not at all evident whether or not the property of being a (D)CI$_f$-group is inherited by subgroups. Amongst other things, we would need to determine that all subgroups of (D)CI$_f$-groups are finitely generated. Setting this aside, it is not evident whether or not finitely generated subgroups of (D)CI$_f$-groups are (D)CI$_f$-groups. Since for a (D)CI$_f$-group we only know that connected, locally-finite Cayley (di)graphs are (D)CI-graphs, it is hard to see even how, given two locally-finite, isomorphic Cayley (di)graphs on $H \le G$, one might construct suitable Cayley (di)graphs on $G$ that are locally-finite and connected, to use the (D)CI$_f$-property. One possible approach would involve proving that every Cayley colour graph on $G$ actually has the CI-property, and then using a second colour of edges on a finite number of generators to connect cosets of $H$. We leave this as another question. To prove any result along these lines (e.g. with the additional condition that $|G:H|$ be finite) would be interesting, we believe. \begin{question} If $G$ is a (D)CI$_f$-group and $H \le G$ is finitely-generated, is $H$ a (D)CI$_f$-group? \end{question} \section{Ryabchenko's results}\label{sect-Ry} In this section we state the results from Ryabchenko's paper, and some closely-related results. Although Ryabchenko does not consider digraphs, his proofs in fact cover the more general situation, and have a number of easy and interesting consequences that he does not make note of. \begin{thm}[\cite{MS}, Theorem 1.2; also \cite{Ryab}, Theorem 1]\label{Ry-Z} Let $S \subset \Z$ be finite. If $\Cay(\Z;S') \cong \Cay(\Z;S)$ then $S'=\pm S$. \end{thm} The statement of M\"{o}ller and Seifter's result \cite[Theorem 1.2]{MS} looks much like this, but they assume that $S$ is a generating set for $\Z$ (so that the graphs are connected), since they were looking for DRRs. The general statement given above is an easy consequence of the connected case. Two isomorphic disconnected Cayley graphs on $\Z$ will have the same number of connected components, which determines the index of the subgroup generated by $S$ (and $S'$); each connected component is isomorphic to a Cayley graph on $\Z$ to which the result for connected graphs applies. The statements of Theorem~\ref{Ry-Z} and of Theorem~\ref{isos-on-Zn-are-autos} look quite different from the versions in Ryabchenko's paper, so for the reader's convenience and confidence complete proofs (based on Ryabchenko's proofs, which are quite different from the M\"{o}ller-Seifter proofs) are provided in the ar$\chi$iv version of this paper, \cite{infinite-arxiv}. This has the following immediate consequence. \begin{cor}\label{Z-is-str-CI_f} The group $\Z$ is a strongly $(D)CI_f$-group. \end{cor} \begin{proof} If $\Cay(\Z;S)$ and $\Cay(\Z;S')$ are isomorphic and $S$ is finite, then by Theorem \ref{Ry-Z}, $S'=\pm S$, so either the identity or the automorphism of $\Z$ that takes every integer to its negative will act as an isomorphism from $\Cay(\Z;S)$ to $\Cay(\Z;S')$. \end{proof} The next result does not look at all like the statement of Theorem 2 from~\cite{Ryab}, but is the clearest and most precise statement of the proof he gives for that theorem. \begin{thm}[\cite{Ryab}, Theorem 2]\label{isos-on-Zn-are-autos} Let $S$ be a finite generating set for $\Z^n$, and let $\Gamma=\Cay(\Z^n;S)$. Then if $\Gamma'=\Cay(\Z^n;S')$ and there is an isomorphism $\phi:\Gamma\to\Gamma'$ such that $\phi$ takes the identity of $\Z^n$ to the identity of $\Z^n$, then $\phi$ is a group automorphism of $\Z^n$. \end{thm} Again, a complete proof of this is provided in \cite{infinite-arxiv}. This has an easy corollary, which is (except for his omission of his assumption that the graphs are locally-finite) the result that was stated in \cite{Ryab}, Theorem 2. \begin{cor}\label{Zn-is-CI_f} The group $\Z^n$ is a $(D)CI_f$-group. \end{cor} \begin{proof} Let $\Gamma=\Cay(\Z^n;S)$ and $\Gamma'=\Cay(\Z^n;S')$ with $\phi:\Gamma\to\Gamma'$ an automorphism. Let $\bf 0$ represent the identity element of $\Z^n$. If $c$ is the element of $\Z^n$ that corresponds to the vertex $\phi(\bf 0)$, then $\phi'=\phi-c$ is an isomorphism from $\Gamma$ to $\Gamma'$ that takes $\bf 0$ to $\bf 0$. By Theorem \ref{isos-on-Zn-are-autos}, $\phi'$ must be an automorphism of $\Z^n$. \end{proof} The following corollary was not mentioned in Ryabchenko's paper but is an immediate consequence of his proof. \begin{cor}\label{normal} If $\Gamma=\Cay(\Z^n;S)$ for some finite generating set $S$ of $\Z^n$, then $\Gamma$ is a normal Cayley (di)graph of $\Z^n$. \end{cor} \begin{proof} Let ${\bf 0}$ be the vertex of $\Gamma$ corresponding to the identity element of $\Z^n$. Let $\gamma$ be any automorphism of $\Gamma$. If $c$ is the element of $\Z^n$ that corresponds to the vertex $\gamma(\bf 0)$, then $\gamma'=\gamma-c$ is an automorphism of $\Gamma$ that fixes $\bf 0$. By Theorem \ref{isos-on-Zn-are-autos}, $\gamma'$ must be an automorphism of $\Z^n$, so normalises $\Z^n$. Since translation by $c$ also normalises $\Z^n$, we see that $\Z^n \triangleleft \Aut(\Gamma)$. \end{proof} The final corollary presented in this section is slightly less obvious, but is still essentially a consequence of the proof in \cite{Ryab}. \begin{cor}\label{unique} If $\Gamma=\Cay(\Z^n;S)$ for some finite generating set $S$ of $\Z^n$, then $\Aut(\Gamma)$ has a unique regular subgroup isomorphic to $\Z^n$. \end{cor} \begin{proof} Let $Z_1$ and $Z_2$ be two regular subgroups isomorphic to $\Z^n$ in $\Aut(\Gamma)$ (with $Z_1=\langle S \rangle$). Let $\alpha' \in Z_2$ be arbitrary; we plan to show that $\alpha' \in Z_1$. Let $\alpha \in Z_1$ such that $\alpha'(\bf 0)=\alpha(\bf 0)$, where $\bf 0$ is the vertex corresponding to the identity of $\Z^n$. Then $\beta=\alpha^{-1}\alpha' $ is an automorphism of $\Gamma$ that fixes $\bf 0$, so by Theorem \ref{isos-on-Zn-are-autos}, $\beta \in \Aut(Z_1)$. Since $S$ is finite, $Z_1$ and $Z_2$ each have finite index in $\Aut(\Gamma)$. It is well-known that the intersection of two groups of finite index, itself has finite index (c.f. Problem 6, Section 5.1, \cite{Ash}). Let $Z=Z_1\cap Z_2$. Clearly, since $Z_1$ and $Z_2$ are abelian, $\beta$ commutes with every element of $Z$. But since $\beta \in \Aut(Z_1)$, it can only commute with the elements of $Z$ if it fixes all of them. This means that $\beta$ fixes a finite-index subgroup of $Z_1$ pointwise, so since $\beta \in \Aut(Z_1)$, we must have $\beta=1$. Hence $\alpha'=\alpha \in Z_1$, as claimed. Since $\alpha'$ was arbitrary, $Z_2=Z_1$ is the unique regular subgroup isomorphic to $\Z^n$ in $\Aut(\Gamma)$. \end{proof} \section{Characterisation of locally-finite (D)CI-graphs on $\Z^n$} We have already seen that $\Z$ is a strongly (D)CI$_f$-group, and that for $n>1$, $\Z^n$ is a (D)CI$_f$-group but not a strongly (D)CI$_f$-group. The following theorem gives a simple characterisation of the locally-finite Cayley (di)graphs on $\Z^n$ that are (D)CI-graphs (where $n>1$): \begin{thm} \label{ZnCIiff} Let $\Gamma=\Cay(\Z^n,S)$ be nonempty and locally finite. Then $\Gamma$ is a (D)CI-graph if and only if either: \begin{enumerate} \item \label{ZnCIiff-conn} $\Gamma$ is connected, or \item \label{ZnCIiff-n=1} $n = 1$, or \item \label{ZnCIiff-n=2} $n = 2$, $\Gamma$~has only two connected components, and $S$~is invariant under some automorphism~$\phi$ of the group~$\langle S \rangle$, such that $\phi$~has order~$3$. \end{enumerate} \end{thm} The proof of the above theorem will occupy the rest of this section. The proof of the main lemma (Lemma~\ref{mainlem}) will use the following well-known consequence of Smith normal form (cf.~4.6.1 of~\cite{Ash}). \begin{thm}[Simultaneous Basis Theorem]\label{simult-basis} Let $M$ be a free abelian group of finite rank $n \ge 1$ over $\Z$, and let $H$ be a subgroup of $M$ of rank $r$. Then there is a basis $\{y_1, \ldots, y_n\}$ for $M$ and nonzero elements $a_1, \ldots, a_r \in \Z$ such that $r \le n$, $a_i$ divides $a_{i+1}$ for all $i$, and $\{a_1y_1, \ldots, a_ry_r\}$ is a basis for $H$. \end{thm} \begin{cor}\label{conj-H} Let $H = b_1\Z \times \cdots \times b_n\Z$ for some $b_1, \ldots, b_n \in \Z$ with $\Pi_{i=1}^n b_i=k$, where $k$ is finite and square-free. Then there is an automorphism $\sigma$ of $\Z^n$ such that $H^\sigma= k\Z \times \Z^{n-1}$. \end{cor} \begin{proof} By Theorem~\ref{simult-basis}, there is a basis $\{y_1, \ldots, y_n\}$ for $\Z^n$ and nonzero integers $a_1, \ldots a_n$ such that $a_i$ divides $a_{i+1}$ for all $i$, and $\{a_1y_1, \ldots, a_ny_n\}$ is a basis for $H$. Notice that the index of $H$ in $\Z^n$ is clearly $a_1a_2 \cdots a_n$, so for this product to be the square-free integer $k$ (given that $a_i$ divides $a_{i+1}$ for every $i$), the only possibility is that $a_1=\cdots=a_{n-1}=1$ and $a_n=k$. Thus, there is a basis $\{y_1, \ldots, y_n\}$ for $\Z^n$ such that $\{y_1, \ldots, y_{n-1},ky_n\}$ is a basis for $H$, so taking $\sigma$ to be the automorphism of $\Z^n$ that takes $y_n$ to $e_1$, $y_1$ to $e_n$, and $y_i$ to $e_i$ for $2 \le i \le n-1$, where $e_1, \ldots, e_n$ is the standard basis for $\Z^n$, establishes the desired result. \end{proof} The following technical result is the foundation of the proof of Theorem~\ref{ZnCIiff}. \begin{lem}\label{mainlem} Let $\Gamma=\Cay(\Z^n,S)$ be nonempty and locally finite, with $n>1$. Then $\Gamma$ is a (D)CI-graph if and only if: \begin{itemize} \item $\Gamma$ (or its underlying graph) has a finite, square-free number of components; and \item $\Aut(H)= \Aut(H)_{\Z^n}\cdot\Stab_{\Aut(H)}(S)$, \end{itemize} where $H = \langle S \rangle$, $\Stab_{\Aut(H)}(S)$ is the group of all automorphisms of $H$ that fix $S$ setwise, and $\Aut(H)_{\Z^n}:=\{\phi|_{H}:\phi\in \Aut(\mathbb{Z}^n),\phi(H)=H\}$, where $\phi\vert_H$ denotes the restriction of $\phi$ to its action on $H$. \end{lem} \begin{proof} ($\Rightarrow$) We assume that $\Gamma$ is a (D)CI-graph. By Proposition~\ref{non-CI-on-Zn}, $\Gamma$ must have a finite, square-free number of components. Take any automorphism $\beta$ of $H$. Then $\Cay(\Z^n,\beta(S)) \cong \Gamma$, so since $\Gamma$ is a (D)CI-graph, there must be some $\gamma \in \Aut(\Z^n)$ such that $\gamma(S)=\beta(S)$. So $\gamma^{-1}\beta \vert_{H} \in \Aut(H)$ and fixes $S$ setwise. Hence $\gamma^{-1}\beta\vert_{H} \in \Stab_{\Aut(H)}(S)$. Also since $\beta \in \Aut(H),$ $H=\langle S \rangle$, and $\beta(S)=\gamma(S)$, we have $\gamma(H)=\beta(H)=H$, so $\gamma\vert_{H} \in \Aut(H)$. Hence $\gamma\vert_H \in \Aut(H)_{\Z^n}$. Therefore $\beta=(\gamma\vert_H)(\gamma^{-1}\beta\vert_H) \in \Aut(H)_{\Z^n} \cdot \Stab_{\Aut(H)}(S)$. This shows that $\Aut(H) \le \Aut(H)_{\Z^n} \cdot\Stab_{\Aut(H)}(S)$; since both of the groups in the product are subgroups of $\Aut(H)$, the other inclusion is immediate. ($\Leftarrow$) Suppose that $\Gamma \cong \Gamma'=\Cay(\Z^n,S')$. Let $H =\langle S \rangle$ and $H'=\langle S' \rangle$. Let $k$ be the number of connected components of $\Gamma$ (and therefore of $\Gamma'$), so by assumption $k$ is finite and square-free. Then $|\Z^n:H|=|\Z^n:H'|=k$. Since $k$ is finite, the rank of $H$ (and of $H'$) is also $n$. By Corollary~\ref{conj-H}, we can conjugate both $H$ and $H'$ to $k\Z\times \Z^{n-1}$ using an element of $\Aut(\Z^n)$, so $H$ and $H'$ are conjugate to each other in $\Aut(\Z^n)$. Thus, replacing $S'$ by a conjugate if necessary, we may assume without loss of generality that $H'=H$. Now since $H'=H\cong \Z^n$ and since $\Cay(H,S)\cong \Cay(H',S')=\Cay(H,S')$ is connected, Corollary~\ref{Zn-is-CI_f} tells us that this is a (D)CI-graph, so there is some $\tau \in \Aut(H)$ such that $\tau(S)=S'$. By assumption, $\tau=\tau_1\tau_2$ where $\tau_1 \in \Aut(H)_{\Z^n}$ and $\tau_2 \in \Stab_{\Aut(H)}(S)$. Now, since $\tau_2$ fixes $S$ setwise, we have $\tau_1(S)=\tau\tau_2^{-1}(S)=\tau(S)=S'$. By definition of $\Aut(H)_{\Z^n}$, there is some $\sigma' \in \Aut(\Z^n)$ such that $\sigma'\vert_H=\tau_1$, so since $S \subseteq H$, we have $\sigma'(S)=\tau_1(S)=S'$. This has shown that there is an automorphism of $\Z^n$ taking $S$ to $S'$, so $\Gamma$ is a (D)CI-graph. \end{proof} The proof of Theorem~\ref{ZnCIiff} will also use a bit of number theory and a classical fact from group theory. \begin{defin}[\cite{Feit}] Let $(q , n) \in \Z \times \Z$ with $q,n > 1$. A prime number~$p$ is a \emph{large Zsigmondy prime for $(q,n)$} if $p \mid (q^n - 1)$, but $p \nmid (q^i - 1)$ for $1 \le i < n$, and either $p > n + 1$ or $p^2 \mid (q^n - 1)$. \end{defin} \begin{hey}[{}{\cite{Feit}}] \label{ZsiLarge} If $p$ is a large Zsigmondy prime for $(q,n)$, then $q$ has order~$n$ in the multiplicative group of units modulo~$p$ (which has order~$p - 1$), so $n \le p - 1$. \end{hey} \begin{lem}[Feit {\cite[Thm.~A]{Feit}}] \label{Zsigmondy} If $(q , n) \in \Z \times \Z$ with $q,n > 1$, then there is a large Zsigmondy prime for $(q,n)$, unless either \begin{enumerate} \item $n = 2$, or \item $n = 4$ and $q \in \{2,3\}$, or \item $n = 6$ and $q \in \{2,3,5\}$, or \item $n \in \{10,12,18\}$ and $q = 2$. \end{enumerate} \end{lem} \begin{lem}[Minkowski {\cite[Thm.~1(i), p.~3]{Serre}}] \label{Blichtfeldt} Let $F$ be a finite subgroup of $\GL(n,\mathbb{Q})$ for some~$n$, and let $p$~be a prime. \begin{enumerate} \item \label{Blichtfeldt-p} If $|F|$ is divisible by~$p$, then $n \ge p - 1$. \item \label{Blichtfeldt-p2} If $|F|$ is divisible by~$p^2$, then $n \ge 2(p - 1)$. \end{enumerate} \end{lem} \begin{proof}[\bf\mathversion{bold} Proof of Theorem~\ref{ZnCIiff}] ($\Rightarrow$) Assume $\Gamma$ is (D)CI, but is not connected, and $n > 1$. We will show that the conditions in part~\ref{ZnCIiff-n=2} of the statement of the theorem are satisfied. Let $H = \langle S \rangle$, and let $k = | \Z^n : H |$ be the number of connected components of~$\Gamma$. Then $k > 1$, and Proposition~\ref{non-CI-on-Zn} tells us that $k$ is square-free (and finite, so $H \cong \Z^n$). Therefore, Corollary~\ref{conj-H} allows us to assume $H =k\Z \times \Z^{n-1}$, after conjugating $S$ by an element of $\Aut(\Z^n) = \GL(n,\Z)$. Let $$\sigma=\begin{pmatrix}1/k&0&\ldots &0\\0&1&\ldots&0\\ \vdots&&\ddots\\0&0&\ldots&1\end{pmatrix}.$$ Then $\sigma$ is an isomorphism from $H$ to $\Z^n$. Now $$ \Aut(H)_{\Z^n} = \left\{\phi\vert_H:\phi=\begin{pmatrix} b_{11}&\ldots& b_{1n} \\ \vdots& &\vdots\\b_{n1}&\ldots & b_{nn} \end{pmatrix} \in \GL(n,\Z) \text{ and } b_{12},\ldots, b_{1n} \equiv 0 \ \mod{k} \right\},$$ so $$A_H^\sigma := \sigma \cdot \Aut(H)_{\Z^n} \cdot \sigma^{-1} = \left\{\begin{pmatrix} b_{11}&\ldots& b_{1n} \\ \vdots& &\vdots\\b_{n1}&\ldots & b_{nn} \end{pmatrix} \in \GL(n,\Z): b_{21},\ldots, b_{n1} \equiv 0 \ \mod{k} \right\}.$$ Lemma~\ref{mainlem} tells us $\Aut(H)= \Aut(H)_{\Z^n}\cdot\Stab_{\Aut(H)}(S)$. Conjugating both sides by $\sigma$ yields $ \GL(n,\Z) = A_H^\sigma \, F $, where $F = \Stab_{\Aut(\Z^n)}\bigl( \sigma(S) \bigr)$ is a finite subgroup of $\GL(n,\Z)$. Let $q$~be a prime divisor of~$k$, and let $\pi$ be the natural homomorphism from $\GL(n,\Z)$ to $\GL(n,\Z_q)$. Letting $\SL^{\pm}(n,\Z_q) = \{ g \in \GL(n,\Z_q) \mid \det g = \pm1 \}$, we have $$ \SL^{\pm}(n,\Z_q) = \pi \bigl( \GL(n,\Z) \bigr) = \pi ( A_H^\sigma ) \cdot \pi(F) .$$ Since $\SL^{\pm}(n,\Z_q)$ is transitive on the finite projective space $\PG(n-1,q)$, and $\pi ( A_H^\sigma )$ is the stabilizer in $\SL^{\pm}(n,\Z_q)$ of a point in this space, this implies that $\pi(F)$ is transitive on $\PG(n-1,q)$. In particular, $$ \text{$|\pi(F): \pi(F) \cap \pi ( A_H^\sigma )|$ is divisible by $|{\PG(n-1,q)}| = (q^n - 1)/(q - 1)$.} $$ (And the same is true when $F$ is replaced by any of its conjugates in $\GL(n,\Z)$.) The remainder of the proof is a slight extension of an argument suggested by G.~Robinson \cite{Robinson}. Let $p$ be a prime factor of $(q^n - 1)/(q - 1)$, so $p \mid |F|$. From Lemma~\ref{Blichtfeldt}(\ref{Blichtfeldt-p}), we see that $p \le n + 1$. Furthermore, if $p = n + 1$, then, since $F$ has an element of order~$p$ (by Cauchy's Theorem) and the cyclotomic polynomial $(x^p - 1)/(x - 1)$ is irreducible over~$\Q$, the representation of~$F$ on~$\Q^n$ is irreducible (over~$\Q$). We claim that $p$ is not a large Zsigmondy prime for $(q,n)$. Otherwise, Remark~\ref{ZsiLarge} tells us that $p \ge n + 1$, so Lemma~\ref{Blichtfeldt}(\ref{Blichtfeldt-p2}) implies that $p^2 \nmid |F|$, so $p^2 \nmid (q^n - 1)/(q - 1)$. If $p$ is a large Zsigmondy prime, then $p \nmid (q - 1)$, so we conclude that $p^2 \nmid (q^n - 1)$. The claim now follows by combining this with the fact (in the preceding paragraph) that $p \le n + 1$. We now know that there are no large Zsigmondy primes for $(q,n)$. We conclude from Lemma~\ref{Zsigmondy} that $$n \in \{2,4,6, 10, 12,18\} $$ (and for each~$n$, there are only a few possible values of~$q$, unless $n = 2$). We consider each possible value of~$n$ as a separate case. \setcounter{case}{0} \begin{case} Assume $n = 2$. \end{case} It is well known that every finite subgroup of $\GL(2,\Z)$ is conjugate to a subgroup of either $$D_8 = \left\langle \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \right\rangle \text{ or } D_{12} = \left\langle \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ -1 & 1 \end{pmatrix} \right\rangle .$$ (A list of all the finite subgroups of $\GL(2,\Z)$, up to conjugacy, can be found in \cite[pp.~179--180]{Newman}.) Thus, we may assume, after passing to a conjugate, that $F \subseteq D_m$, with $m \in \{8,12\}$. Note that $|D_m| = m \le 12$. Then, since $$ \left\{ \begin{pmatrix} \pm1 & 0 \\ 0 & \pm1 \end{pmatrix} \right\} \subseteq D_8 \cap A_H^\sigma \text{ \ and \ } \left\langle \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}, \begin{pmatrix} -1 & 1 \\ 0 & 1 \end{pmatrix} \right\rangle \subseteq D_{12} \cap A_H^\sigma ,$$ we have $$ q + 1 = \frac{q^2 - 1}{q - 1} = \frac{q^n - 1}{q - 1} \le \frac{|\pi(F)|}{|\pi(F) \cap \pi ( A_H^\sigma )|} \le \frac{|D_m|}{|D_m \cap A_H^\sigma|} \le \frac{12}{4} = 3 .$$ So $q = 2$. This means $k>1$ is a square-free positive integer whose only prime divisor is~$2$. So $k = 2$. In other words, $\Gamma$~has only two connected components. Furthermore, $|F|$ is divisible by $(q^n - 1)/(q - 1) = (2^2 - 1)/(2 - 1) = 3$, so $F$ has an element of order~$3$. Therefore $\Stab_{\Aut(H)}(S) = \sigma^{-1} F \sigma$ also has an element~$\phi$ of order~$3$. So the conditions in (\ref{ZnCIiff-n=2}) are satisfied. \begin{case} Assume $n = 4$. \end{case} From Lemma~\ref{Zsigmondy}, we have $q \in \{2,3\}$, so $|F|$ must be divisible by either $(2^4 - 1)/(2 - 1) = 15$ or $(3^4 - 1)/(3 - 1) = 40$. Therefore, $F$ is contained in a maximal finite subgroup $M$ of $\GL(4,\Z)$ whose order is divisible by~$5$. The nine maximal finite subgroups of $\GL(4,\Z)$ are listed in \cite[Thm.~4.27]{Dade} (up to conjugacy), and, by inspection, the only two whose order is divisible by~$5$ are $Sx_4$ and $Py_4$. So (after passing to a conjugate) $M$ is either $Sx_4$ or $Py_4$. However, for each maximal subgroup~$M$, the proof in \cite{Dade} provides a finite $M$-invariant subset~$S$ that contains a basis of~$\Z^4$. For $Py_4$, we have $|S| = 10$, so $M$ has an orbit of cardinality $\le 10$ on $\PG(3,q)$; therefore $M$ is not transitive. For $Sx_4$, we have $|S| = 20$, and $M$~is transitive on~$S$; therefore, the cardinality of some orbit on $\PG(3,q)$ must be a divisor of $20$, and is therefore neither $15$ nor $40$. Once again, $M$ is not transitive. Since $F \subseteq M$, this is a contradiction. \begin{case} \label{Case6} Assume $n = 6$. \end{case} From Lemma~\ref{Zsigmondy}, we have $q \in \{2,3,5\}$. However, if $q \in \{3,5\}$, then $(q^{6} - 1)/(q - 1)$ is divisible by either $p = 13$ or $p = 31$, which contradicts the fact that $p \le n + 1 = 7$. Therefore, we must have $q = 2$, so $(q^{6} - 1)/(q - 1) = 3^2 \cdot 7$ is divisible by $p = 7$. Let $M$ be a maximal finite subgroup of $\GL(6,\Z)$ that contains~$F$. We note that $M$ is absolutely irreducible, not merely irreducible over~$\Q$. For example, it is implicit in \cite[Thm.~IV.5 and p.~117]{Plesken} (and stated explicitly, but without proof, on page~483 of \cite{PleskenAppls}) that if a maximal finite subgroup of $\GL(6,\Z)$ is irreducible (over~$\Q$), then it is absolutely irreducible. G.~Robinson \cite{Robinson} has provided two (short) alternative arguments. Begin by noting that if $M$ is not absolutely irreducible, then it is (isomorphic to) a finite subgroup of $\GL(d,\mathbb{C})$, with $d \le 3 = (p - 1)/2$. One argument simply notes that the finite subgroups of $\GL(3,\mathbb{C})$ have been classified. The other argument uses a theorem of R.~Brauer \cite{Brauer}, which implies that either $M$ is isomorphic to $\mathsf{PSL}(2,p) = \mathsf{PSL}(2,7)$ (which is of order 168), or the Sylow $p$-subgroup of~$M$ is normal (which implies $|M|$ is a divisor of $2 (p-1)p = 84$); in either case, $|M|$ is not divisible by $|{\PG(n-1,2)}| = 63$. The seventeen absolutely irreducible maximal finite subgroups of $\GL(6,\Z)$ are listed in \cite[Thm.~4.1]{PleskenPohst} (up to conjugacy), and, by inspection, the only three whose order is divisible by 7 are $\Aut(F_{12})$, $\Aut(F_{13})$, and $\Aut(F_{14})$. The order of $\Aut(F_{14}) \cong \PGL(2,7) \times \{\pm1\}$ is 672, which is not divisible by $|{\PG(n-1,2)}| = 63$. Therefore, $M$ is either $\Aut(F_{12})$ or $\Aut(F_{13})$. These are both isomorphic to $S_p \times \{\pm 1\}$, and they are conjugate over~$\Q$ to the automorphism group of the root lattice ${\mathcal A}_{p-1}$. In the notation of \cite{Dade}, this automorphism group is $Sx_{p-1}$. Specifically, note that $S_p$ acts on~$\Z^p$ by permuting the standard basis vectors $e_1,\ldots,e_p$. The embedding of $Sx_{p-1} = S_p \times \{\pm1\}$ in $\GL(n,\Z)$ is obtained by identifying $\Z^n = \Z^{p-1}$ with the $\Z$-span of the $S_p$-invariant set $\Phi = \{e_i - e_j : i \neq j\}$. Choose $g \in \GL(n,\Q)$ that conjugates $M$ to $Sx_{p-1}$, so $g \Phi$ is an $M$-invariant subset of~$\Q^n$. After multiplying~$g$ by a scalar, we may assume $g \Z^n \subseteq \Z^n$, and (since $\Phi$ contains a basis of~$\Z^n$) that there exists $v \in g\Phi \smallsetminus 2 \Z^n$. Then $v$ represents a point $[v]$ in $\PG(n-1,2)$, and, since $g\Phi$ is $M$-invariant, we have $$ \bigl| M \cdot [v] \bigr| \le |g \Phi| = |\Phi| = p \cdot (p-1) < (2^{p-1} - 1)/(2 - 1) ,$$ which contradicts the fact that $M$ is transitive on $\PG(n-1,2)$ (with $n = p-1$). \begin{case} Assume $n = 10$. \end{case} From Lemma~\ref{Zsigmondy}, we have $q = 2$, so $(q^n - 1)/(q - 1) % = (2^{10} - 1})/(2 - 1) = 2^{10} - 1 % = (2^5 + 1)(2^5 - 1) = 33 \cdot 31 = 3 \cdot 11 \cdot 31$, so letting $p = 31$ contradicts the fact that $p \le n + 1 = 11$. \begin{case} Assume $n = 12$. \end{case} From Lemma~\ref{Zsigmondy}, we have $q = 2$. So $|F|$ must be divisible by $(2^{12} - 1)/(2 - 1) = 3^2 \cdot 5 \cdot 7 \cdot 13$. Let $p = 13$. Since $p > 11$, we know from \cite[Thm.~V.10(iii), p.~31]{NebePlesken} that any finite subgroup of $\GL(p - 1,\Z)$ whose order is divisible by~$p$ is either isomorphic to a subgroup of $\mathsf{PGL}_2(p) \times \{\pm 1\}$, or conjugate in $\GL(p - 1,\Q)$ to a subgroup of $Sx_{p-1}$, the automorphism group of the root lattice ${\mathcal A}_{p-1}$. However, we know, from the argument in the last paragraph of Case~\ref{Case6} of the proof, that $F$ cannot be conjugate in $\GL(p - 1,\Q)$ to a subgroup of $Sx_{p-1}$. Therefore, $F$ must be isomorphic to a subgroup of $\mathsf{PGL}_2(13) \times \{\pm 1\}$. But this, too, is impossible, because $$|\mathsf{PGL}_2(13) \times \{\pm 1\}| = 13 (13^2 - 1) \cdot 2 < (2^{12} - 1)/(2 - 1) = |{\PG(11,2)} | .$$ \begin{case} Assume $n = 18$. \end{case} From Lemma~\ref{Zsigmondy}, we have $q = 2$, so $(q^n - 1)/(q - 1) % = (2^{18} - 1})/(2 - 1) = 2^{18} - 1 % = (2^9 + 1)(2^9 - 1) = 513 \cdot 511 = (3^3 \cdot 19)(7 \cdot 73) = 3^3 \cdot 7 \cdot 19 \cdot 73$, so letting $p = 73$ contradicts the fact that $p \le n + 1 = 19$. \bigbreak % ($\Leftarrow$) From Corollaries~\ref{Zn-is-CI_f} and~\ref{Z-is-str-CI_f}, we know that if either (\ref{ZnCIiff-conn}) or (\ref{ZnCIiff-n=1}) holds, then $\Gamma$ is a CI-graph. Therefore, we need only consider assumption (\ref{ZnCIiff-n=2}): assume $\Gamma$ has two connected components, and $S$~is invariant under some automorphism~$\phi$ of the group~$\langle S \rangle$, such that $\phi$~has order~$3$. Since the number of components of~$\Gamma$ is~2, which is a finite, square-free number, we only need to verify the second condition of Lemma~\ref{mainlem} to see that this is a CI graph. Let $H=\langle S\rangle$. Since $\Gamma$ has two components, we know $|\Z^2 : H| = 2$, so Corollary~\ref{conj-H} tells us that we may assume $H = 2\Z \times \Z$, after applying an automorphism of~$\Z^2$. As in the proof of ($\Rightarrow$), let $$\sigma=\begin{pmatrix} 1/2&0\\ 0 & 1\end{pmatrix}.$$ Since $\phi \in \Stab_{\Aut(H)}(S)$, we have $\sigma \phi \sigma^{-1} \in \Stab_{\Aut(\Z^n)} \bigl( \sigma(S) \bigr)$. It is well known that no element of order~$3$ in $\GL(n,\Z)$ acts trivially on $\PG(n,2)$. (See, for example, Case~1 of the proof of \cite[Thm.~4.8.2, pp.~66--67]{MorrisArith} with $p = 2$ and $k = 3$.) Since $|{\PG(2,2)}| = 3$, this implies that $\langle \phi \rangle$ is transitive on $\PG(2,2)$. Since $\sigma \cdot \Aut(H)_{\Z^2} \cdot \sigma^{-1}$ is the stabilizer in $\GL(2,\Z)$ of a point in $\PG(2,2)$, and $\langle \phi \rangle \subseteq \Stab_{\Aut(\Z^n)} \bigl( \sigma(S) \bigr)$, we conclude that $$ \bigl( \sigma \cdot \Aut(H)_{\Z^2} \cdot \sigma^{-1} \bigr) \cdot \Stab_{\Aut(\Z^n)} \bigl( \sigma(S) \bigr) = \GL(2,\Z) .$$ Conjugating by $\sigma^{-1}$ yields the desired conclusion that $\Aut(H)= \Aut(H)_{\Z^n}\cdot\Stab_{\Aut(H)}(S)$. \end{proof} We remark that graphs described in Theorem~\ref{ZnCIiff}(3) (that is, disconnected, nonempty, locally-finite (D)CI-graphs on $\Z^2$) do arise. \begin{eg} The graph $\Cay(\Z^2,S)$ where $S=\{\pm(2,0), \pm (0,1), \pm (2,1)\}$ is a CI-graph. \end{eg} \begin{proof} The matrix $$\left(\begin{matrix}-1&2\\-\frac{1}{2}&0\end{matrix}\right)$$ has order 3 (its cube is the identity matrix) and is invariant on $S$ (it maps $\pm(2,0)$ to $\pm(-2,-1)$ to $\pm(0,1)$), so is an automorphism of $\langle S\rangle$. Therefore by Theorem~\ref{ZnCIiff}(3), it is a CI-graph. \end{proof} \subsection{Acknowledgments} I am deeply indebted to Laci Babai for many long conversations about this problem that led to the terminology introduced in this paper. Ideas from these conversations also formed the basis of many of the results and proofs presented here. Thanks are also due to the anonymous referee for careful reading of this paper and a number of helpful suggestions. I am also very grateful to Geoff Robinson, whose insightful answer to a question I posed on mathoverflow \cite{Robinson} led to major improvements in Section 6 of this paper. Finally, Dave Witte Morris helped enormously in formulating and writing up the ideas in Section 6. \begin{thebibliography}{10} \bibitem{Adam} A.~Adam. \newblock Research problem 2--10. \newblock {\em J. Combinatorial Theory}, 2:309, 1967. \bibitem{Ash} Robert~B. Ash. \newblock Abstract algebra: The basic graduate year. \newblock \url{http://www.math.uiuc.edu/~r-ash/Algebra.html}, 11 2002. \bibitem{Baba-1} L.~Babai. \newblock Isomorphism problem for a class of point-symmetric structures. \newblock {\em Acta Math. Acad. Sci. Hungar.} 29(3--4):329--336, 1977. %\MR{0485447 (58 \#5281)} \bibitem{Baba-Fran-1} L.~Babai and P.~Frankl. \newblock Isomorphisms of {C}ayley graphs. {I}. \newblock {\em Combinatorics} ({P}roc. {F}ifth {H}ungarian {C}olloq., {K}eszthely, 1976), {V}ol. {I}, Colloq. Math. Soc. J{\'a}nos Bolyai, North-Holland, Amsterdam, 18:35--52, 1978. %\MR{519254 (81g:05066a)} \bibitem{Brauer} Richard Brauer. \newblock On groups whose order contains a prime number to the first power II. \newblock {\em Amer. J. Math.} 64:421--440, 1942. \bibitem{Dade} E. C. Dade. \newblock The maximal finite groups of $4 \times 4$ integral matrices. \newblock {\em Illinois J. Math.} 9:99--122, 1965. \bibitem{Ted-Z_p3} Edward Dobson. \newblock Isomorphism problem for {C}ayley graphs of {$Z^3_p$}. \newblock {\em Discrete Math.}, 147(1--3):87--94, 1995. %\MR{1364506 (96m:05101)} \bibitem{Elsp-Turn} Bernard Elspas and James Turner. \newblock Graphs with circulant adjacency matrices. \newblock {\em J. Combinatorial Theory}, 9:297--307, 1970.% \MR{027265 (42 \#7540)} \bibitem{Feit} Walter Feit. \newblock On large {Z}sigmondy primes. \newblock {\em Proc. Amer. Math. Soc.}, 102:29--36, 1988.% \MR{0915710 (89b:11009)} \bibitem{Gods-Z_p2} C.~D. Godsil. \newblock On {C}ayley graph isomorphisms. \newblock {\em Ars Combin.}, 15:231--246, 1983. %\MR{706302 (84m:20011)} \bibitem{Hall-Kula} P.~Hall and C.~R. Kulatilaka. \newblock A property of locally finite groups. \newblock {\em J. London Math. Soc.}, 39:235--239, 1964. %\MR{0161907 (28 \#5111)} \bibitem{Hira-Muzy} M.~Hirasaka and M.~Muzychuk. \newblock An elementary abelian group of rank 4 is a {CI}-group. \newblock {\em J. Combin. Theory Ser. A}, 94(2):339--362, 2001. %\MR{1825792 (2002a:20003)} \bibitem{Karg} M.~I. Kargapolov. \newblock On a problem of {O}. {J}u. \v {S}midt. \newblock {\em Sibirsk. Mat. \u Z.}, 4:232--235, 1963. %\MR{0148735 (26 \#6241)} \bibitem{Li-survey} Cai~Heng Li. \newblock On isomorphisms of finite {C}ayley graphs---a survey. \newblock {\em Discrete Math.}, 256(1--2):301--334, 2002. %\MR{1927074 (2003i:05067)} \bibitem{Li-Lu-Palf} Cai~Heng Li, Zai~Ping Lu, and P.~P. P{{\'a}}lfy. \newblock Further restrictions on the structure of finite {CI}-groups. \newblock {\em J. Algebraic Combin.}, 26(2):161--181, 2007. %\MR{2335710 (2008g:20048)} \bibitem{Loeh} Clara L{{\"o}}h. \newblock Which finitely generated {A}belian groups admit isomorphic {C}ayley graphs? \newblock {\em Geom. Dedicata}, 164:97--111, 2013. %\MR{3054618} \bibitem{discussion} Avinoam Mann. \newblock Discussion of conjugacy classes of infinite groups. \newblock \url{http://www.math.niu.edu/~rusin/known-math/95/finite.conj}, 09 1995, now available at \url{https://web.archive.org/web/20120310035855/http://www.math.niu.edu/~rusin/known-math/95/finite.conj}. \bibitem{MS} R\"{o}gnvaldur G. M\"{o}ller and Norbert Seifter. \newblock Digraphical Regular Representations of Infinite Finitely Generated Groups. \newblock {\em Europ. J. Combinatorics}, 19:597--602, 1998. \bibitem{MorrisArith} D.~W.~Morris. \newblock {\em Introduction to arithmetic groups}. \newblock Deductive Press, 2015. \url{https://arxiv.org/src/math/0106063v6/anc/IntroArithGrps-FINAL.pdf} \bibitem{thesis} J.~Morris. \newblock Isomorphisms of cayley graphs. \newblock {\em Ph.D. thesis}, Simon Fraser University, 1999. \bibitem{infinite-arxiv} J.~Morris.\newblock The CI problem for infinite groups. \newblock \arxiv{1502.06114}, 02 2015. \bibitem{Muzy-elem-abel} M.~Muzychuk. \newblock An elementary abelian group of large rank is not a {CI}-group. \newblock {\em Discrete Math.}, 264(1--3):167--185, 2003. The 2000 ${\rm{C}}om{^{2}}MaC$ Conference on Association Schemes, Codes and Designs (Pohang). %\MR{1972028 (2004b:20007)} \bibitem{Newman} Morris Newman. \newblock {\em Integral matrices}. \newblock Academic Press, New York-London, 1972. %MR0340283 \bibitem{NebePlesken} G. Nebe and W. Plesken. \newblock Finite rational matrix groups. \newblock {\em Mem. Amer. Math. Soc.} 116 1995, no. 556. \bibitem{Plesken} Wilhelm Plesken. \newblock Bravais groups in low dimensions. \newblock %Proceedings of the Conference on Kristallographische Gruppen (Univ. Bielefeld, Bielefeld, 1979), Part II. Match 10:97--119, 1981. %\url{http://match.pmf.kg.ac.rs/electronic_versions/Match10/match10_97-119.pdf} %MR0620803 \bibitem{PleskenAppls} W.~Plesken. \newblock Some applications of representation theory. \newblock In {\em Representation theory of finite groups and finite-dimensional algebras (Bielefeld, 1991)}, 477--496, Birkh\"auser, Basel, 1991. %MR1112176 \bibitem{PleskenPohst} Wilhelm Plesken and Michael Pohst. \newblock On maximal finite irreducible subgroups of $GL(n,\mathbf{Z})$~II. The six dimensional case. \newblock {\em Math. Comp.} 31:552--€“573, 1977. %MR0444790 \bibitem{Robinson} Geoff Robinson. \newblock Transitive actions of finite subgroups of ${\rm GL}(n,\Z)$ on projective geometries. \newblock \url{http://mathoverflow.net/q/252537}, 10 2016. \bibitem{Ryab} A.~A. Ryabchenko. \newblock Isomorphisms of {C}ayley graphs of a free abelian group. \newblock {\em Sibirsk. Mat. Zh. (Translation in Siberian Math. J.)}, 48(5):1142--1146, (Russian); 919--922 (English), 2007. %\MR{2364633 (2008i:05085)} \bibitem{Serre} Jean-Pierre Serre. \newblock Bounds for the orders of the finite subgroups of $G(k)$. \newblock \arxiv{1011.0346v1}, 11 2010. \bibitem{Somlai-CI} G{{\'a}}bor Somlai. \newblock Elementary abelian {$p$}-groups of rank {$2p+3$} are not {CI}-groups. \newblock {\em J. Algebraic Combin.}, 34(3):323--335, 2011. %\MR{2836364 (2012j:05209)} \bibitem{Spig-CI} Pablo Spiga. \newblock Elementary abelian {$p$}-groups of rank greater than or equal to {$4p-2$} are not {CI}-groups. \newblock {\em J. Algebraic Combin.}, 26(3):343--355, 2007. %\MR{2348100 (2008g:20008)} \bibitem{Turn-Zp} James Turner. \newblock Point-symmetric graphs with a prime number of points. \newblock {\em J. Combinatorial Theory}, 3:136--145, 1967. %\MR{0211908 (35 \#2783)} \end{thebibliography} \end{document}