Orders for which there exist exactly six or seven groups

Given a square-free integer $n$, a prime factor $p$ and a subset $\pi$ of its prime factors, we let $v(p,\pi)$ be the number of $q$ in $\pi$ such that $q\equiv 1\ (\mathrm{mod}\ p)$. In this case, we say that $p$ is related to $q$, and $p$ and $q$ are related. We also let $\Gamma$ be the set of all prime factors of $n$. Then we have

It is therefore natural to define the \hg1 $\Gamma=\Gamma(n)$ of a square-free integer $n$ to be the unlabeled directed graph whose vertices are the prime factors, and where we have an edge $p\rightarrow q$ precisely when $p$ is related to $q$. Observe also that when the out-degree of every vertex is at most 1, $g(n)$ depends solely on the shape of the \hg1, and therefore we are justified in speaking of $g(\Gamma).$ We call both $n$ and $\Gamma$ regular in this case. We will occasionally treat directed acyclic graphs $\Gamma$ where we only know the labels, or the numerical values, of the vertices whose out-degree exceeds $1$. In this case, we can still speak of $g(\Gamma)$ without ambiguity, as it will be independent of the labels of the rest of the vertices. We also observe that Dirichlet’s theorem on arithmetic progressions shows that a given (unlabeled) directed acyclic graph is always realizable as the \hg1 of some odd square-free integer.

We generalize this to arbitrary $n=p_{1}^{\alpha_{1}}\cdots p_{s}^{\alpha_{s}}$ as follows: The vertices are now the $p_{i}^{\alpha_{i}}$, and an edge $p^{\alpha}\rightarrow q^{\beta}$ exists precisely when $q^{j}\equiv 1\ (\mathrm{mod}\ p^{i})$ for some $1\leq i\leq\alpha$ and $1\leq j\leq\beta$. We will call this the generalized \hg of $n$, also denoted by $\Gamma(n)$. Typically, $n$ will be cube-free, in which case we write $p^{2}\dashrightarrow q$ to mean $p\parallel q-1$, and $q\dashrightarrow p^{2}$ to mean $q\mid p+1$ but $q\nmid p-1$. We call these two types of arrows weak, and other arrows strong.

A vertex is said to be initial if it has an out-degree of $0$, and terminal if it has an in-degree of $0$. We also let $S(\pi,\Gamma)=\prod_{p\notin\pi}h_{\Gamma}(p,\pi)$ be the summand in Hölder’s formula corresponding to the subset $\pi$. If there is a vertex $p$ not connected to any vertex in $\pi,$ the entire summand $S(\pi\Gamma)$ vanishes. Motivated by this observation, we call a subset $\pi$ central if, for every vertex outside of it, there exists at least one edge to a vertex inside it – equivalently, if $S(\pi\Gamma)$ does not vanish. We remark that $n$ is regular precisely when $g(\Gamma(n))$ is equal to the number of central subsets.

We have already observed that $g(ab)\geq g(a)g(b)$ for coprime $a,b$. When does equality hold? If it does hold, then every group of order $ab$ splits as a direct product of groups of orders $a$ and $b.$ Coprimality is therefore a necessary condition: If $p$ divides both $a$ and $b,$ we simply observe that the group $\operatorname{C}_{a/p}\times\operatorname{C}_{p^{2}}\times\operatorname{C}_{b/p}$ does not split in this way. Next, it must be impossible to form semidirect products. If $p$ divides $b$ and $q^{n}$ divides $a$, we observe that $\lvert\operatorname{Aut}(\operatorname{C}_{q}^{n})\rvert$ has $q^{i}-1$ as a factor for all $1\leq i\leq n$, and therefore a nontrivial semidirect product exists if there is a relation $p\rightarrow q^{n}.$ In this case, $a$ and $b$ are said to be arithmetically dependent. We conclude that another necessary condition is $\Gamma(n)=\Gamma(a)\sqcup\Gamma(b)$. The converse is also true:

In solving $g(n)=c$, it is useful to define the cyclic part of $n$ to be $m$ (in this notation), and call $n$ cyclic-free if $m=1$. Next, whenever $c=c_{1}\cdots c_{s}$, finding solutions $g(n_{i})=c_{i}$ with pairwise independent $n_{i}$ leads to a solution to $c$. It is therefore natural to consider “prime” values of $n$, that is, those with $k=1$. We will call cyclic-free $n$ with $k=1$ connected. By considering non-nilpotent groups, we can get a lower bound on $g(n)$. We will only make use of the following (weak) lower bound:

Given disjoint graphs $\Gamma$ and $\Lambda$ with a fixed terminal vertex $\tilde{q}$ in $\Gamma$ and any vertex $\tilde{p}$ in $\Lambda$, we can make a new graph $\Gamma\rightarrow\Lambda$ by adjoining an arrow $\tilde{p}\rightarrow\tilde{q}$ to the union of $\Gamma$ and $\Lambda$. This depends on the choice of $\tilde{q}$ and $\tilde{p}$ in general, but we will not explicitly refer to them when there is no risk of confusion. In addition, we tacitly assume that we are given the functions $h_{\Gamma}$ and $h_{\Lambda}$. We use the notation $g(X;v)$ to refer to the sum in Hölder’s formula but only considering subsets $\pi$ with $v\in\pi$.

We can iterate the first operation, starting with a graph $\Gamma_{0}$ and a fixed terminal vertex $q$ in it and define $\Gamma_{n+1}=\Gamma_{n}\rightarrow v_{n+1}$, where the $v_{i}$ are all distinct. If we let $\alpha=g(\Gamma_{0}-\{q\})$ and $\beta=g(\Gamma_{0})$, then the sequence $a_{n}=g(\Gamma_{n})$ satisfies the recurrence relation $a_{n+2}=a_{n+1}+a_{n}$ with initial values $a_{-1}=\alpha$ and $a_{0}=\beta$. Starting with a single vertex, we get

An amusing consequence of this fact is this. Since $\Phi_{m+n}=\Phi_{m}\rightarrow\Phi_{n}$, and we have just seen that $g(\Phi_{m}-\{\text{final}\})=F_{m}$ and $g(\Phi_{n};\text{initial})=F_{n}$, we can now apply \threfeustick to obtain the well-known identity,

We have already seen that $g(\Phi_{n})$ is the Fibonacci sequence, and so it grows exponentially with $n$. It follows that $g$ grows exponentially in the length of the longest directed path, since $g(\Gamma)\geq g(\Gamma_{0})$ for all subgraphs $\Gamma_{0}\subseteq\Gamma$. It grows exponentially in the in- and out-degrees as well:

We first dispose of the disconnected case. Let $n=n_{1}\cdots n_{k}m$ be the unique factorization of $n$ in the notation of \threfeuufd, with $m=1$ and $n_{i}$ ordered such that $g(n_{i})$ is non-decreasing. The primality of $7$ shows that $k=1$ when $g(n)=7$, so it is enough to consider connected $n$ in this case. If $g(n)=6$, either $k=1$ or $g(n_{1})=2$ and $g(n_{2})=3$. For the sake of completeness, we briefly re-derive the solutions in $n_{1}$ and $n_{2}$ here.

First, $n_{1}$ is cube-free and has at most one square factor. If it has none, then it must have the graph . If it has one, then $n_{1}=p^{2}$. Next, if $n_{2}$ is square-free, \threfeuinout forces its graph to be . If it is not, then it is easy to see that it must be of the form $p^{2}q$ with $q\dashrightarrow p^{2}$ and $p,q$ odd. \threfeuppq asserts that this is also a sufficient condition. We summarize the results:

Let $i(\Gamma),o(\Gamma)$ denote the maximum in- and out-degree of a vertex in a \hg1 $\Gamma$. If $o(\Gamma)=3$, we get at least $1+\frac{p^{3}-1}{p-1}=p^{2}+p+2\geq 8$. It follows that $o(\Gamma)\leq 2$, and, for a similar reason, $i(\Gamma)\leq 2$. We therefore have four cases to consider.

1 $i(\Gamma)=1,o(\Gamma)=1$. In this case $\Gamma$ is simply a path $\Phi_{k}$ for some $k$, and as neither 6 nor 7 is a Fibonacci number, so by \threfeufibo this is never an admissible graph.

2 $i(\Gamma)=2,o(\Gamma)=1$. It is clear that there is a unique vertex $v$ with in-degree 2, so let $w_{1},w_{2}\rightarrow v$ be arrows, and call this subgraph $K$. We have $g(K)=2^{2}=4$, and the only way to add edges is by adding vertices, since we have $o(\Gamma)=1$. A new vertex $u$ can be connected to $w_{1}$ to get $u\rightarrow w_{1}$, this would give $g(K)+g(K;w_{1})=4+2=6$ groups by \threfeujoin, so call this new graph $Q$. We cannot extend $Q$: Both extensions $b\rightarrow Q$ and $Q\rightarrow f$ give too many groups by \threfeustick. In the other direction, we could add $v\rightarrow f_{1}$ in $K$ instead, yielding $g(K)+g(\leavevmode\hbox to20.16pt{\vbox to2.17pt{\pgfpicture\makeatletter\hbox{\hskip 1.08525pt\lower-1.08525pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {{}} \hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{ }{}\pgfsys@moveto{0.88525pt}{0.0pt}\pgfsys@curveto{0.88525pt}{0.4889pt}{0.4889pt}{0.88525pt}{0.0pt}{0.88525pt}\pgfsys@curveto{-0.4889pt}{0.88525pt}{-0.88525pt}{0.4889pt}{-0.88525pt}{0.0pt}\pgfsys@curveto{-0.88525pt}{-0.4889pt}{-0.4889pt}{-0.88525pt}{0.0pt}{-0.88525pt}\pgfsys@curveto{0.4889pt}{-0.88525pt}{0.88525pt}{-0.4889pt}{0.88525pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{{{{}}}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\pgfsys@color@gray@fill{0}\pgfsys@invoke{ }{}\pgfsys@moveto{18.87384pt}{0.0pt}\pgfsys@curveto{18.87384pt}{0.4889pt}{18.4775pt}{0.88525pt}{17.98859pt}{0.88525pt}\pgfsys@curveto{17.49968pt}{0.88525pt}{17.10333pt}{0.4889pt}{17.10333pt}{0.0pt}\pgfsys@curveto{17.10333pt}{-0.4889pt}{17.49968pt}{-0.88525pt}{17.98859pt}{-0.88525pt}\pgfsys@curveto{18.4775pt}{-0.88525pt}{18.87384pt}{-0.4889pt}{18.87384pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{17.98859pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{ } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{17.98859pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})=5$. However, this can only be extended forward, that is, by taking $(K\rightarrow f_{1})\rightarrow f_{2}$, and this yields $g(K\rightarrow f_{1})+g(K)=4+5=9$ groups. Thus the only admissible graph is $Q$, with $g(Q)=6$.

3 $i(\Gamma)=1,o(\Gamma)=2$. It is clear that there is a unique vertex with out-degree 2, so label it $p$ for some prime $p$. We get at least $p+2$ groups, so we have $p\leq 5$ and therefore $p$ is initial (there can be no vertex labeled 2 because it would have an out-degree of at least 2). We cannot add edges without adding vertices. Using \threfeustick, we see that adding a new vertex $v$ and an arrow $u\rightarrow v$, where $u$ is either of the two vertices connected with $p$, yields $p+4$ groups. As $p>2$, we must have $p=3$. This completes the analysis for all such graphs: We get admissible graphs when $p=5$ in the first sub-case and when $p=3$ in the second sub-case, both yielding $g=7$.

4 $i(\Gamma)=2,o(\Gamma)=2$. A vertex labeled $p$ with in-degree and out-degree both equal to $2$ has $p>2$, and would yield $4+p+1=p+5>7$ groups. So let $u$ be the unique vertex with out-degree $2$ and label it $p$, and assume we have $u\rightarrow v_{1},v_{2}$, and call this graph $Q$. We have already seen that $g(Q)=p+2$. We show that we cannot add a vertex $w$. First, we cannot connect it with $u$: An arrow $w\rightarrow u$ is impossible since it means $w=2$, and $u\rightarrow w$ is ruled out by the condition on $o(\Gamma)$. Adding $w\rightarrow v_{1}$ does not give an admissible graph, because the subsets $\{v_{1},v_{2}\}$ and $\{w,v_{1},v_{2}\}$ would both be central, yielding $2(p+1)=2p+2\geq 8$ groups in total. Finally, if we add $v_{1}\rightarrow w$ instead, we are back to Case $3$ with $p+4\geq 7$ groups, and it is now impossible to achieve $i(\Gamma)=2$.

We can add an edge $v_{1}\rightarrow v_{2}$ to $Q$ without adding $w$. This will give $p+4$ groups, and is the only admissible case, giving $6$ if $p=2$ and $7$ if $p=3$.

In this section, we consider non-square-free admissible $n$ with $\lambda(n)\leq 4$. Following [5], we list special cases of formulae for $g(p^{2}q^{2}),g(p^{2}qr),g(p^{2}q)\text{ and }g(p^{3}q)$ and analyze them one by one. In their notation, $w_{r}(s)$ is defined to be 1 if $s\mid r$ and 0 otherwise.

Analysis. We have $p\nmid q-1$, since otherwise we would get at most $5$ groups. Thus we need $q\mid p-1$, and this yields admissible $n$ precisely when $q=3$, giving $6$ groups, and when $q=5$, giving $7$ groups.

Analysis. If $p\mid q-1$, we have at least $p+10$ groups. It is also clear that we cannot have $q\mid p-1$. We therefore have $g(p^{3}q)=5+w_{p+1}(q)+w_{(p+1)(p^{2}+p+1)}(q)$. The last summand is $1$, and thus $g(p^{3}q)=6$ if $q\mid(p^{2}+p+1)$ and $g(p^{3}q)=7$ if $q\mid p+1$.

Analysis. It is clear that we need $p\nmid q-1$, so $p\mid q+1$. This gives 6 or 7 groups, depending on whether $p^{2}\mid q+1$ as well or not.

Analysis. This case is more complicated, so we divide the proof into several steps. We begin by applying the formula to the graph $D(p)$ with $p^{2}\dashrightarrow q,r$: It can be seen that $g(D(p))=2p+5\geq 9$.

We see that $p\neq 2$, since otherwise we would have $D(2)$ as a subgraph. Next, we show that there is no strong arrow to $p^{2}$. By \threfeuppq we see that there is no $r\rightarrow p^{2}$ since $r\geq 5$. If we have $q\rightarrow p^{2}$, we get $g(p^{2}q)=6$, and the connectivity of $n$ forces one of $w_{r-1}(p),w_{r-1}(q)$ and $w_{p+1}(r)$ to be equal to $1$. The formula then implies that we get $2(p-1)$, $\frac{(q-1)(q+4)}{2}$, or $w_{p^{2}-1}(qr)+w_{p+1}(r)$ more groups, respectively, showing that $n$ is inadmissible.

Observe that $h$ depends only on the shape of the generalized graph of $n$, and not on the magnitudes of its prime factors. Consequently, if $k(n)=0$, we can calculate $g(n)$ for all $n$ with a specific graph simply by calculating $g(n)$ for a single representative, using the Cubefree package in GAP[7, 3]. We will call $n$ “regular” in this case as well.

We analyze $k(n)$. If there is an arrow $q\rightarrow r$, then we have $h(n)\geq 2+2w_{r-1}(q)=4$, and if there is no arrow then both $q$ and $r$ are connected with $p^{2}$. A case-by-case analysis shows that $h(n)\geq 5$ in this case. Consequently, we must have $k(n)\leq 3$ in all admissible cases, with equality implying the existence of an arrow $q\rightarrow r$.

Assume now that $k(n)>0$, that is, $n$ is not regular. By considering the “coefficients” of the $w$-sums in the formula for $k$, we observe that all of them are greater than $3$ except possibly $p-1$ and $\frac{q-1}{2}$. First, the sum whose coefficient is $(p-1)$ must vanish, as otherwise would get $D(p)$ as a subgraph.

Secondly, we consider $\frac{q-1}{2}$. Our analysis shows that all the summands but $w_{p+1}(q)w_{r-1}(q)$ must vanish. Let $\text{M}_{1}(q)$ be the graph with $q\rightarrow r$ and $q\dashrightarrow p^{2}$ (we emphasize its dependence on $q$). We see that $g(\text{M}_{1}(q))=5+\frac{q-1}{2}$, thus we get admissible $n$ precisely when $q=3$ or $q=5$, yielding $6$ and $7$ groups, respectively, and this is the only irregular admissible case.

Finally, it remains to handle non-square-free admissible $n$ with $\lambda(n)=5$. There are three cases to consider.

A $n=p^{3}qr$. We immediately see that $q$ and $r$ are not related, since otherwise we would get at least $g(p^{3})g(qr)=10$ groups. We must have $g(p^{3}q)\geq 6$, and by connectivity, we have $g(p^{3}q)=6$ and $r\mid p^{\alpha}-1$ for some $1\leq\alpha\leq 3$. The case that yields the least number of groups is $r\mid p^{3}-1$ with $r\nmid p^{2}-1$, and in this case we get $2^{2}=4$ groups of the form $\operatorname{C}_{p}^{3}\rtimes\operatorname{C}_{qr}$ and 4 groups of the form $P\times\operatorname{C}_{qr}$, where $P$ is any group of order $p^{3}$ different from $\operatorname{C}_{p}^{3}$. This gives a total of 8 groups, proving that $n$ is inadmissible.