# Collective effects enhanced multi-qubit information engines

Noufal Jaseem  Department of Physical Sciences, Indian Institutes of Science
Education and Research Berhampur, India.  Victor Mukherjee  Department of
Physical Sciences, Indian Institutes of Science Education and Research
Berhampur, India.

###### Abstract

We study a quantum information engine (QIE) modeled by a multi-qubit working
medium (WM) collectively coupled to a single thermal bath. We show that one
can harness the collective effects to significantly enhance the performance of
the QIE, as compared to equivalent engines lacking collective effects. We use
one bit of information about the WM magnetization to extract work from the
thermal bath. We analyze the work output, noise-to-signal ratio and
thermodynamic uncertainty relation, and contrast these performance metrics of
a collective QIE with that of an engine whose WM qubits are coupled
independently to a thermal bath. We show that in the limit of high
temperatures of the thermal bath, a collective QIE always outperforms its
independent counterpart. In contrast to quantum heat engines, where collective
enhancement in specific heat plays a direct role in improving the performance
of the engines, here the collective advantage stems from higher occupation
probabilities for the higher energy levels of the positive magnetization
states, as compared to the independent case.

††preprint: APS/123-QED

##  I Introduction

The relationship between information theory and thermodynamics has been a
topic of intense interest in the research community during the last few
decades [1], with information engines, i.e. engines which use information to
extract useful work, playing a significant role in this regard [2, 3, 4]. The
concept of Maxwell’s demon [5], first proposed by James Clerk Maxwell in 1867,
was one of the earliest works suggesting the possibility of using information
to extract work from a single heat bath in classical systems. Subsequently,
the idea of using information and measurements to extract work was extended to
the quantum regime [2, 6, 7, 8, 9, 10, 1, 11, 12, 13, 14, 15, 16, 17, 18], and
also realized experimentally in recent years [19, 20].

One of the major aims of the field of quantum technologies is to study the
effects of quantum mechanics on the operation of such technologies [21, 22,
23]. For example, quantum coherence has been shown to improve the power output
of quantum heat engines [24], while squeezed thermal reservoirs have been used
to significantly enhance the efficiencies of such engines [25, 26, 27]; non-
adiabatic excitations in quantum critical systems driven out of equilibrium
have been shown to aid in the charging of quantum batteries [28], and
entanglement may help in extracting work from such batteries [29]. Quantum
features have been used to design quantum information engines (QIEs) as well.
For example, a bosonic quantum Szilard engine has been shown to outperform its
fermionic counterpart [2]. Ref. [14] showcases the use of quantum coherence to
extract non-trivial work from the process of unselective measurement, akin to
information erasure. This stands in contrast to the Landauer principle, which
imposes a thermodynamic work cost for both classical and quantum erasure.

In recent years, collective effects in many-body quantum technologies
comprising indistinguishable particles collectively coupled to thermal baths
have received significant attention from the research community [30, 31, 32,
33, 34, 35]. For example, collective effects have been used to perform high-
precision quantum thermometry [32] and to obtain enhanced work output [30, 31,
32], efficiency [36], and reliability [34] in quantum thermal machines. In
this work, we propose a collective effects enhanced many-body QIE, modeled by
a working medium (WM) of $n$ non-interacting indistinguishable spin $1/2$s,
collectively coupled to a single heat bath. Information about the
magnetization direction of the WM allows us to extract work. Our analysis
shows that in comparison to an equivalent QIE modeled by $n$ non-interacting
spin $1/2$s independently coupled to heat baths, the collective effects may
result in significantly enhanced work output, low noise-to -signal ratio, and
low Thermodynamic Uncertainty ($\mathcal{Q}$). The collective advantage
originates from higher occupation probabilities for the higher energy levels
of the positive magnetization states compared to the independent case.

The paper is organized as follows. In Sec. II, we discuss the model of the
many-body QIE, its operation, and the process of work extraction, in detail.
The different performance metrics of the QIE are studied, and compared with
their independent QIE counterparts, in Sec. III. Finally, we summarize our
results in Sec. IV.

##  II Many-body information engine

###  II.1 Information engine

We consider a working medium (WM) consisting of $n$ spin-$1/2$ systems. One
can model a three-stroke information engine as follows (see Fig. 1):

  * •

Stroke 1: In the first energizing stroke, the WM is coupled to a thermal bath
at an inverse temperature $\beta$. The WM undergoes a non-unitary evolution,
wherein energy flows from the bath to the system, resulting in the WM reaching
a steady state $\rho^{\text{ss}}$ at long times.

  * •

Stroke 2: In the second stroke the WM is decoupled from the bath, and the
direction of the magnetization $m$ of the WM, or equivalently, the sign of
$m$, is measured. A positive magnetization implies the WM has non-zero
ergotropy [37], part of which can be extracted by applying a global unitary
$U_{\rm flip}$ to flip all the qubits of the WM.

  * •

Stroke 3: Following the result of the measurement in stroke 2, we apply a
global unitary $U_{\rm flip}$ to flip all the qubits of the WM for $m>0$,
thereby changing the sign of $m$, and extracting work in the process. On the
other hand, a negative $m$ is detrimental to work extraction under the above
unitary $U_{\rm flip}$. Consequently no unitary is applied in case of $m\leq
0$.

Finally, we couple the WM with the Markovian bath introduced in stroke 1, and
repeat all the steps mentioned above, thereby giving rise to a cyclic
information engine.

Figure 1:  A schematic representation of an information engine comprising $n$
qubits, highlighting the three strokes of the cycle.

###  II.2 Model and dynamics

In this section, we discuss in detail the dynamics involved in stroke 1 of the
information engine, introduced above. To this end, we consider a WM composed
of multiple non-interacting qubits with bare Hamiltonian given by
$H=\hbar\omega(t)\mathcal{J}_{z}$, where we define the collective angular
momentum operators as
$\mathcal{J}_{i}:=\frac{1}{2}\sum_{k=1}^{n}\sigma^{k}_{i}$. Here the Pauli
matrix $\sigma_{i}^{k}$ is the spin operator along the $i$ axis ($i=x,y,z$),
acting on the $k$-th spin. The spins are collectively coupled to a thermal
bath during the non-unitary stroke 1 through the system-bath interaction
Hamiltonian $H_{\rm int}=\gamma\mathcal{J}_{x}\otimes\mathcal{B}$. Here
$\gamma$ denotes the coupling strength, while $\mathcal{B}$ is an operator
acting on the thermal bath. As shown in the references [30, 38, 32], such
collective system-bath interaction may generate quantum coherence in the
steady-state density matrix $\rho^{\rm ss}_{\rm col}$ of the WM, characterized
by the presence of off-diagonal elements in the WM density matrix in the local
spin basis. The dynamics of the WM is described by the master equation [30,
38, 32]

$\displaystyle\frac{d\rho}{dt}=-\frac{i}{\hbar}[H,\rho]+\Gamma(\omega)\mathcal{D}(\mathcal{J}^{+})\rho+\Gamma(-\omega)\mathcal{D}(\mathcal{J}^{-})\rho,$
(1)

where $\mathcal{D}[O]\rho=(2O^{\dagger}\rho O-OO^{\dagger}\rho-\rho
OO^{\dagger})/2$, the collective ladder operators of the spin system are given
by $\mathcal{\mathcal{J}}^{\pm}:=\mathcal{\mathcal{J}}_{x}\pm
i\mathcal{\mathcal{J}}_{y}$, and $\Gamma(\omega)$ is the spectral function of
the bath at frequency $\omega$. The spectral functions $\Gamma(\omega)$ and
$\Gamma(-\omega)$ are related to each other via the Kubo-Martin-Schwinger
condition $\Gamma(-\omega)=\exp\left(-\beta\hbar\omega\right)\Gamma(\omega)$
[39]. The steady-state $\rho^{ss}_{\rm col}$ can be expressed in the
collective basis $|j,m\rangle_{i}$ of the common eigenvectors of
$\mathcal{J}_{z}$ and
$\mathcal{J}^{2}=\mathcal{J}_{x}^{2}+\mathcal{J}_{y}^{2}+\mathcal{J}_{z}^{2}$
as [38]:

$\displaystyle\rho^{ss}_{\rm col}(\beta,\omega)$ $\displaystyle=$
$\displaystyle\sum_{j=j_{0}}^{n/2}\sum_{i=1}^{l_{j}}P_{j,i}\;\rho_{j,i}^{\text{th}}(\beta,\omega),$
(2) $\displaystyle\rho_{j,i}^{\text{th}}(\beta,\omega)$ $\displaystyle=$
$\displaystyle\frac{1}{Z_{j}}\sum_{m=-j}^{j}e^{-\beta
m\hbar\omega}|j,m\rangle_{i}{}_{i}\langle j,m|.$

Here $Z_{j}=\sum_{m=-j}^{j}e^{-\beta m\hbar\omega}$ is the partition function
of the angular momentum subspace $j$, $-j\leq m\leq j$, $j\in[j_{0};n/2]$, and
$j_{0}=1/2$ for odd $n$ and $j_{0}=0$ for even $n$. The index $i\in[1;l_{j}]$,
where $l_{j}$ is the multiplicity of the eigenspaces associated with the
eigenvalue $j$ of the operator $\mathcal{J}^{2}$ [40]. The initial state,
$\rho_{0}$, of the WM determines the probability $P_{j,i}$ through the
relation $P_{j,i}=\sum_{m=-j}^{j}\;{}_{i}\langle j,m|\rho_{0}|j,m\rangle_{i}$.

Previous studies have shown that an initial state prepared in the $j=n/2$
subspace is the most favorable for obtaining collective advantage in quantum
thermal machines [30, 32, 34]. Consequently, here we restrict ourselves to the
$j=n/2$ subspace, such that $l_{j=n/2}=1$, $P_{j=n/2}=1$ and the corresponding
steady state is given by [32, 23]

$\rho^{ss}_{\rm
col}(\beta,\omega)=\frac{1}{Z_{n/2}}\sum_{m=-n/2}^{n/2}{e^{-\beta
m\hbar\omega}}\left|\frac{n}{2},m\right\rangle\left\langle\frac{n}{2},m\right|.$
(3)

We note that in contrast to the setup introduced above, one can consider an
independent WM-bath coupling, described by an interaction Hamiltonian of the
form $H_{\rm
int}=\frac{\gamma}{2}\sum_{k=1}^{n}\sigma_{x}^{k}\otimes\mathcal{B}_{k}$,
where $\mathcal{B}_{k}$ denotes an operator acting on the bath coupled to the
$k$-th spin. In the latter scenario, the steady-state reached at the end of
the non-unitary thermal interaction stroke is a direct product state of the
form [39, 30, 38, 32, 23]

$\displaystyle\rho^{ss}_{\rm ind}(\beta,\omega)$ $\displaystyle=$
$\displaystyle\otimes_{k=1}^{n}\rho^{ss}_{k}(\beta,\omega),$ (4)

where
$\rho^{ss}_{k}(\beta,\omega)=\frac{\exp\left(-\beta\hbar\omega\sigma_{z}^{k}/2\right)}{{\rm
Tr}\left[\exp\left(-\beta\hbar\omega\sigma_{z}^{k}/2\right)\right]}$ is the
steady state density matrix corresponding to the $k$th spin.

##  III Statistics of the output work

The unitary operation $U_{\rm flip}$ considered in the second stroke
introduced in Sec. II.1 acts only the states $|n/2,m\rangle$ with $m>0$; a
part of the ergotropy of such states is extracted in the form of output work,
while those states are transformed to $|n/2,-m\rangle$ at the end of this
stroke. For the independent bath coupling as well, a state $|{m}\rangle$ with
$m>0$ denotes the presence of non-zero ergotropy, which can be used to perform
useful work through unitary transformation to the state $|{-m}\rangle$. We
take the sign of energy outflow from the WM as positive and the inflow as
negative. If $w_{m}=2m\hbar\omega$ is the amount of work extracted from the
state $|{n/2,m}\rangle$ or from $|{m}\rangle$ with probability
$p_{m}^{\alpha}$ ($\alpha=$ col, ind), then the average work takes the form,

$\displaystyle\langle W_{\alpha}\rangle$ $\displaystyle=$
$\displaystyle\sum_{m\geq 0}w_{m}p_{m}^{\alpha},$ (5)

and its variance,
$\text{var}(W_{\alpha})=\langle{W_{\alpha}^{2}}\rangle-\langle{W_{\alpha}}\rangle^{2}$,
is given by

$\displaystyle\text{var}(W_{\alpha})$ $\displaystyle=$
$\displaystyle\sum_{m\geq 0}w_{m}^{2}p_{m}^{\alpha}-\langle
W_{\alpha}\rangle^{2}.$ (6)

In Eqs. (5) and (6), $m=0,1,2,...,n/2$ for even $n$, while
$m=1/2,3/2,5/2,...,n/2$ for odd $n$. For the collective engine, the
probability is given by (see Eq. (3))

$\displaystyle p_{m}^{\rm col}=\frac{e^{-\beta m\hbar\omega}}{Z_{n/2}},$ (7)

while in the case of the independent engine, we have (see Eq. (4))

$\displaystyle p_{m}^{\rm ind}=\;{}^{n}C_{n/2-m}\;\frac{e^{-\beta
m\hbar\omega}}{Z_{\rm ind}}.$ (8)

Here $Z_{\rm ind}=\left(e^{-\beta\omega/2}+e^{\beta\omega/2}\right)^{n}$ is
the partition function corresponding to the thermal state of the independent
engine’s WM. The factor ${}^{n}C_{n/2-m}$ in Eq. (8) denotes the number of
combinations of spin arrangements that give rise to a magnetization $m$.

Figure 2: The average work outputs $\langle W_{\rm col}\rangle$ and $\langle
W_{\rm ind}\rangle$ are plotted as functions of $\beta$ for $n=3$ and $n=10$.
In the inset, we present the variation of the ratio $\lambda_{\rm w}=\langle
W_{\rm col}\rangle/\langle W_{\rm ind}\rangle$ with respect to $n$ and
$T=1/\beta$. The green contour line represents $\lambda_{\rm w}=1$. The values
of $\hbar$, $k_{\rm B}$ and $\omega$ are set to 1.

Figure 3: (a) The work output of the collective and independent engines given
in Eqs. (9) and (10) are plotted as functions of the number of qubits $n$, for
$\beta\to 0$. The dashed and dot-dashed lines represent the work output
obtained in the large $n$ limit. The inset shows the same quantities but for
finite temperatures, with $\beta$ values of $0.01$ and $0.05$. (b) The figure
shows the ratio of the occupation probabilities $\mathcal{R}_{m}\equiv
p_{m}^{\rm col}/p_{m}^{\rm ind}$ plotted against the inverse temperature
$\beta$ for a system of $n=6$ spin particles. The plot illustrates that for
$m=1,2,3$, the collective occupation probabilities for the higher energy
levels remain larger than the corresponding independent probabilities over a
range of high temperatures. The values of $\hbar$, $k_{\rm B}$, and $\omega$
are set to 1.

###  III.1 Information engine in the high temperature limit

In the limit $\beta=\frac{1}{k_{B}T}\to 0$, all the basis states will have
equal probability of being occupied, and hence from Eq. (5), we get the
collective work output as (see Appendix),

$\lim_{\beta\to 0}\langle W_{\rm col}\rangle=\lim_{\beta\to 0}\sum_{m\geq
0}w_{m}p_{m}^{\rm col}\;=\;\frac{\hbar\omega}{n+1}\sum_{r=0}^{r_{\rm
max}}(n-2r).$ (9)

Here $p_{m}^{col}(\beta\to 0)=1/(n+1)$, $w_{m}=2\hbar\omega
m=\hbar\omega(n-2r)$ with $r=n/2-m$, $r_{\rm max}=n/2$ for even $n$, and
$r_{\rm max}=(n-1)/2$ for odd $n$. The above equation simplifies to $\langle
W_{\text{col}}\rangle=(n+1)\hbar\omega/4$ for odd $n$, and to $\langle W_{\rm
col}\rangle=\frac{n(n+2)}{4(n+1)}\hbar\omega$ for even $n$, which, in the
limit of large $n$, can be approximated to $n\hbar\omega/4$. Similarly, the
work output for the independent case can be obtained as

$\langle{W_{\rm ind}}\rangle=\sum_{m\geq 0}p_{m}^{\rm
ind}w_{m}\;=\;\frac{\hbar\omega}{2^{n}}\sum_{r=0}^{r_{\rm
max}}\;{}^{n}C_{r}(n-2r),$ (10)

where $p_{m}^{ind}(\beta\to 0)=\;{}^{n}C_{r}/2^{n}$ and
$w_{m}=\hbar\omega(n-2r)$. The above equation readily simplifies to $\langle
W_{\rm ind}\rangle=2^{-(n+1)}\;{}^{n}C_{\frac{n+1}{2}}\;(n+1)\hbar\omega$ for
odd $n$ and $\langle W_{\rm
ind}\rangle=\frac{1}{2^{n+1}}\;{}^{n}C_{\frac{n}{2}}\;n\hbar\omega$ for even
$n$, where ${}^{r}C_{s}\equiv\frac{r!}{(r-s)!s!}$. By identifying the Catalan
number $\mathbb{C}_{r}=\frac{1}{r+1}{}^{2r}C_{r}$ [41, 42] which approximates
to $4^{r}/(r\sqrt{r\pi})$ in the large $r$ limit, we get $\langle{W_{\rm
ind}}\rangle\approx\sqrt{\frac{n}{2\pi}}\hbar\omega$ for both odd and even
$n$. From the above, the ratio of the work output of the collective to the
independent case can be calculated to be,

$\lambda_{\rm w}\;=\;\frac{\langle W_{\text{col}}\rangle}{\langle
W_{\text{ind}}\rangle}\approx\frac{\sqrt{2\pi n}}{4},$ (11)

for large $n$ values (see fig. 2). Therefore we get a quadratic increase in
the output work for the collective engine over the independent one, as also
shown in fig. 3.

We note that as discussed in [32, 34], in the case of a collective quantum
heat engine, the improvement in its performance is a direct consequence of the
collective enhancement in the specific heat, which depends on the populations
and the energies of all the magnetization $m$ states of the WM. In contrast,
in the QIE introduced here, only the $m>0$ states contribute to work
extraction (see Sec. II.1); in this case, the collective advantage stems from
higher occupation probabilities $p_{m}^{\rm col}$ for large $m>0$, as compared
to $p_{m}^{\rm ind}$ for an independent QIE, we discuss below. In the limit of
high temperatures ($\beta\to 0$), the partition functions for the collective
and independent cases are given by $Z_{\rm col}=n+1$ and $Z_{\rm ind}=2^{n}$.
With the working medium state constrained to the $j=n/2$ subspace, there is a
unique eigenstate corresponding to $|{n/2,m}\rangle$, while for the
independent case, there are ${}^{n}C_{n/2-m}$ degenerate eigenstates
$|{m}\rangle$; the degeneracy ${}^{n}C_{n/2-m}$ increases with decreasing
$|m|$. Consequently, $p_{m}^{\rm ind}$ surpasses $p_{m}^{\rm col}$ for smaller
values of $|m|$. A similar analysis for finite temperatures shows that
collective advantages persist for $n\beta\ll 2/\left(\hbar\omega\right)$, as
shown by the ratio $\mathcal{R}_{m}=p_{m}^{\rm col}/p_{m}^{\rm ind}$ for large
$m>0$ (see Eqs. (7), (8) and fig. 3).

Figure 4: The main plot shows the noise-to-signal ratios for the collective
(${\rm nsr}_{\rm col}$) and the independent (${\rm nsr}_{\rm ind}$) cases as
functions of the number of qubits $n$, for $\beta\to 0$. The inset presents
the $\rm nsr$ as a function of $\beta$ for $n=20$ and $25$. The values of
$\hbar$, $k_{\rm B}$ and $\omega$ are set to 1.

####  III.1.1 Noise to signal ratio and TUR:

The reliability of an engine can be quantified through the noise-to-signal
ratio $\text{nsr}=\text{var}(W)/\langle W\rangle^{2}$. One can calculate the
variance of work for the collective and independent cases for $\beta\to 0$ as
(see Eqs. (6) - (8))

$\displaystyle\text{var}(W_{\text{col}})$ $\displaystyle=$
$\displaystyle\frac{\hbar^{2}\omega^{2}}{n+1}\sum_{r=0}^{r_{\rm
max}}(n-2r)^{2}$ (12)
$\displaystyle\qquad-\left(\frac{\hbar\omega}{n+1}\sum_{r=0}^{r_{\rm
max}}(n-2r)\right)^{2},$

and

$\displaystyle\text{var}(W_{\text{ind}})$ $\displaystyle=$
$\displaystyle\frac{\hbar^{2}\omega^{2}}{2^{n}}\sum_{r=0}^{r_{\rm
max}}\;{}^{n}C_{r}(n-2r)^{2}$ (13)
$\displaystyle\quad-\left(\frac{\hbar\omega}{2^{n}}\sum_{r=0}^{r_{\rm
max}}\;{}^{n}C_{r}(n-2r)\right)^{2}.$

As shown in fig. 4, for small values of $n$, odd values yield a lower nsr
compared to even values, both for collective, as well as independent engines.
However, as $n$ increases, the nsrs for both even and odd values converge
asymptotically, with the asymptotic value in the collective case being smaller
than that in the independent case, demonstrating a collective advantage in
engine performance.

As discussed in [43] a low nsr can be accompanied by a large entropy
production $\Sigma$, which in turn, can be expected to reduce the efficiencies
of heat engines. A trade-off between nsr and $\Sigma$ can be quantified using
the thermodynamic uncertainty, expressed as
$\mathcal{Q}\equiv\text{nsr}\;\Sigma/k_{\rm B}$, which is generally lower
bounded by the inequality $\mathcal{Q}\geq 2$ in the case of classical [44,
45, 46] and incoherent quantum [47, 48, 49] heat engines. Recently, violations
of this inequality have been observed for quantum-coherent and quantum-
entangled systems [50, 51, 47, 52, 53, 54, 34]. In case of the collective and
independent QIEs considered here, analogous to Szilard engines [2], the
minimum entropy production arising due to memory erasure is given by $\Delta
S_{\rm era}^{\rm min}=k_{\rm B}\ln 2$. Consequently, the minimum Thermodynamic
Uncertainty $\mathcal{Q}_{\rm min}=\ln 2\;\rm{nsr}$, which in the limit of
large $n$, is less than the standard limit of $\mathcal{Q}=2$ discussed above
(see fig. 4).

###  III.2 Finite temperature information engine

We now focus on the finite-temperature regime. The mean and variance of the
output work, as well as the nsr, can be evaluated using Eqs. (5) and (6) for
arbitrary $n$ and $\beta$ (see Figs. 2, 3, 4). Detailed equations for
calculating the mean and variance can be found in the appendix (see (15) -
(22)). In the limit of large $n$, the analysis for the collective case can be
simplified by replacing the summations in Eqs. (5) and (6) with integrations
to get

$\displaystyle\langle W_{\rm col}\rangle$ $\displaystyle=$
$\displaystyle\frac{[\beta\hbar\omega(n-2r_{\rm max})+2]\;e^{\beta\hbar\omega
r_{\rm max}}-n\beta\hbar\omega-2}{\beta\left(e^{\beta
n\hbar\omega}-1\right)}.$

As expected, Eq. (LABEL:eq:wcolfinite) simplifies to $\langle W_{\rm
col}\rangle\approx n\hbar\omega/4$ in the limit of $\beta\to 0$ (see section
III.1). Furthermore, as discussed above, the collective advantage manifests
itself for high temperatures $n\beta\ll 2/\left(\hbar\omega\right)$. In
contrast, numerical analysis confirms that independent engines outperform
their collective counterparts for low temperatures (see Fig. 3). As shown in
fig. 4, collective effects result in QIEs with low nsr in the high-temperature
limit, as compared to their independent counterparts. However, for low
temperatures, independent QIEs may be more reliable than the collective ones,
as signified by the nsr of collective QIEs surpassing that for independent
QIEs, with increasing $\beta$, for a fixed finite $n$ (see the inset of fig.
4).

For a finite temperature information engine, the entropy change due to the
heat exchange between the WM and the heat source is given by $\Delta
S^{(\alpha)}_{h}=-\langle W_{\alpha}\rangle/T_{h}$, where we have considered
the conservation of energy, so that on an average, the work output equals the
heat input from the bath. Further, the process of memory erasure results in an
increase of entropy of the universe by $\Delta S_{\rm era}\geq k_{B}\ln 2$,
where $\alpha={\rm col,ind}$. Therefore, the total entropy production is given
by $\langle\Sigma_{\alpha}\rangle=\Delta S_{h}+\Delta S^{\alpha}_{\rm
era}=-\langle W_{\alpha}\rangle/T_{h}+\Delta S^{\alpha}_{\rm era}$. Utilizing
the results for $\langle W_{\rm col}\rangle$ and $\langle W_{\rm ind}\rangle$
(cf. Eqs. (15) - (18)), it can be shown that the entropy production is always
non-negative, as depicted in fig. 5, thereby satisfying the second law of
thermodynamics.

Furthermore, the collective effects enhance $\langle W_{\rm col}\rangle$ at
high temperatures for a given $n$, resulting in reduced entropy production
($\langle\Sigma_{\rm col}\rangle<\langle\Sigma_{\rm ind}\rangle$) and reduced
thermodynamic uncertainty ($\mathcal{Q}_{\rm col}<\mathcal{Q}_{\rm ind}$) for
the collective QIE, as compared to its independent counterpart. Assuming the
minimal erasure entropy production, $\Delta S_{\rm era}$, to be equal to
$k_{\text{B}}\ln 2$, both the independent and the collective cases violate the
standard TUR at high temperatures for a given $n$ (i.e., $\mathcal{Q}_{\rm
col}<\mathcal{Q}_{\rm ind}<2$), as shown in fig. 6. $Q_{\rm col}$ may surpass
$Q_{\rm ind}$ at low temperatures, thus again showing the importance of high
temperatures for achieving collective advantage in QIEs.

Figure 5: Plot showing the total average entropy production
$\langle\Sigma\rangle$ as a function of $\beta$ for $n=25$ and $n=50$. As
shown here, $\langle\Sigma\rangle$ is always non-negative, thereby satisfying
the second law of thermodynamics. The values of $\hbar$, $k_{\rm B}$ and
$\omega$ are set to 1. Figure 6:  Plot showing the thermodynamic uncertainty
$\mathcal{Q}=\text{nsr}\langle{\Sigma}\rangle/k_{\rm B}$ for $n=25$ and
$n=50$. The values of $\hbar$, $k_{\rm B}$ and $\omega$ are set to 1.

##  IV Discussion

In this work, we have studied a many-body QIE that relies on one bit of
information to extract work from a single heat bath. The engine considered
here is modeled by a multi-qubit system WM interacting collectively with a
heat reservoir. The collective effects observed in this system arise from the
bath’s inability to distinguish between the qubits as they exchange energy,
which results in a non-trivial steady state of the WM. Based on the
measurement outcome of the net magnetization direction of the steady state, a
unitary operation may be performed to extract useful work.

Our findings demonstrate that by utilizing effects stemming from the
collective system-bath coupling, the QIE can achieve a quadratic advantage in
the mean work output, as compared to its independent counterpart in the large
temperature limit. However, this quadratic advantage is limited to finite
sizes of the WM in the case of finite temperatures. Additionally, we have
shown that this collective advantage is present in other performance metrics
as well, such as low noise-to-signal ratio and low thermodynamic uncertainty,
for appropriate parameter values. Our research is motivated by recent findings
that demonstrate that such collective effects can significantly enhance the
performance of quantum heat engines [30, 31, 32, 36, 34]. However, in contrast
to collective quantum heat engines, where the improvement in performance
follows from collective enhancement in the specific heat of the WM, here the
collective advantage stems from the higher occupation probabilities of the
high positive magnetization states of the WM.

Finally, we note that the collective quantum information engine proposed here
can be expected to be experimentally realizable in several existing setups,
such as by using Rydberg atoms placed in a cavity [55], atomic sodium [56],
quantum dots [57], and organic microcavity [58].

## ACKNOWLEDGEMENTS

V.M. acknowledges support from Science and Engineering Research Board (SERB)
through MATRICS (Project No. MTR/2021/000055) and Seed Grant from IISER
Berhampur. V.M. also acknowledges Sai Vinjanampathy and Gershon Kurizki for
helpful discussions.

## References

  * [1] Sai Vinjanampathy and Janet Anders.  Quantum thermodynamics.  Contemporary Physics, 57(4):545–579, 2016.
  * [2] Sang Wook Kim, Takahiro Sagawa, Simone De Liberato, and Masahito Ueda.  Quantum szilard engine.  Physical review letters, 106(7):070401, 2011.
  * [3] J. M. Diaz de la Cruz and M. A. Martin-Delgado.  Quantum-information engines with many-body states attaining optimal extractable work with quantum control.  Phys. Rev. A, 89:032327, Mar 2014.
  * [4] Alhun Aydin, Altug Sisman, and Ronnie Kosloff.  Landauer’s principle in a quantum szilard engine without maxwell’s demon.  Entropy, 22(3), 2020.
  * [5] Cargill Gilston Knott.  Life and scientific work of Peter Guthrie Tait, volume 1.  Рипол Классик, 1911.
  * [6] Alhun Aydin, Altug Sisman, and Ronnie Kosloff.  Landauer’s principle in a quantum szilard engine without maxwell’s demon.  Entropy, 22(3):294, 2020.
  * [7] Eric Lutz and Sergio Ciliberto.  From maxwell’s demon to landauer’s eraser.  Phys. Today, 68(9):30, 2015.
  * [8] Étienne Jussiau, Léa Bresque, Alexia Auffèves, Kater W Murch, and Andrew N Jordan.  Many-body quantum vacuum fluctuation engines.  arXiv preprint arXiv:2208.07225, 2022.
  * [9] Lídia del Rio, Johan Åberg, Renato Renner, Oscar Dahlsten, and Vlatko Vedral.  The thermodynamic meaning of negative entropy.  Nature, 474(7349):61–63, 2011.
  * [10] Nathan M Myers, Obinna Abah, and Sebastian Deffner.  Quantum thermodynamic devices: from theoretical proposals to experimental reality.  AVS Quantum Science, 4(2):027101, 2022.
  * [11] Kagan Yanik, Bibek Bhandari, Sreenath K Manikandan, and Andrew N Jordan.  Thermodynamics of quantum measurement and the demon’s arrow of time.  arXiv preprint arXiv:2205.08031, 2022.
  * [12] Cyril Elouard, David Herrera-Martí, Benjamin Huard, and Alexia Auffeves.  Extracting work from quantum measurement in maxwell’s demon engines.  Physical Review Letters, 118(26):260603, 2017.
  * [13] Bibek Bhandari and Andrew N Jordan.  Continuous measurement boosted adiabatic quantum thermal machines.  Physical Review Research, 4(3):033103, 2022.
  * [14] Philipp Kammerlander and Janet Anders.  Coherence and measurement in quantum thermodynamics.  Scientific reports, 6(1):1–7, 2016.
  * [15] Andrew N Jordan, Cyril Elouard, and Alexia Auffèves.  Quantum measurement engines and their relevance for quantum interpretations.  Quantum Studies: Mathematics and Foundations, 7(2):203–215, 2020\.
  * [16] Léa Bresque, Patrice A Camati, Spencer Rogers, Kater Murch, Andrew N Jordan, and Alexia Auffèves.  Two-qubit engine fueled by entanglement and local measurements.  Physical Review Letters, 126(12):120605, 2021.
  * [17] Sreenath K Manikandan, Cyril Elouard, Kater W Murch, Alexia Auffèves, and Andrew N Jordan.  Efficiently fueling a quantum engine with incompatible measurements.  Physical Review E, 105(4):044137, 2022.
  * [18] Lorenzo Buffoni, Andrea Solfanelli, Paola Verrucchi, Alessandro Cuccoli, and Michele Campisi.  Quantum measurement cooling.  Physical review letters, 122(7):070603, 2019.
  * [19] Jonne V Koski, Ville F Maisi, Jukka P Pekola, and Dmitri V Averin.  Experimental realization of a szilard engine with a single electron.  Proceedings of the National Academy of Sciences, 111(38):13786–13789, 2014.
  * [20] Kunkun Wang, Ruqiao Xia, Léa Bresque, and Peng Xue.  Experimental demonstration of a quantum engine driven by entanglement and local measurements.  Phys. Rev. Res., 4:L032042, Sep 2022.
  * [21] David Gelbwaser-Klimovsky, Wolfgang Niedenzu, and Gershon Kurizki.  Chapter twelve - thermodynamics of quantum systems under dynamical control.  volume 64 of Advances In Atomic, Molecular, and Optical Physics, pages 329–407. Academic Press, 2015.
  * [22] Sourav Bhattacharjee and Amit Dutta.  Quantum thermal machines and batteries.  The European Physical Journal B, 94(12):239, Dec 2021.
  * [23] Victor Mukherjee and Uma Divakaran.  Many-body quantum thermal machines.  Journal of Physics: Condensed Matter, 33(45):454001, Aug 2021.
  * [24] Raam Uzdin, Amikam Levy, and Ronnie Kosloff.  Equivalence of quantum heat machines, and quantum-thermodynamic signatures.  Phys. Rev. X, 5:031044, Sep 2015.
  * [25] J. Roßnagel, O. Abah, F. Schmidt-Kaler, K. Singer, and E. Lutz.  Nanoscale heat engine beyond the carnot limit.  Phys. Rev. Lett., 112:030602, Jan 2014.
  * [26] Wolfgang Niedenzu, Victor Mukherjee, Arnab Ghosh, Abraham G. Kofman, and Gershon Kurizki.  Quantum engine efficiency bound beyond the second law of thermodynamics.  Nature Communications, 9(1):165, Jan 2018.
  * [27] Jan Klaers, Stefan Faelt, Atac Imamoglu, and Emre Togan.  Squeezed thermal reservoirs as a resource for a nanomechanical engine beyond the carnot limit.  Phys. Rev. X, 7:031044, Sep 2017.
  * [28] Obinna Abah, Gabriele De Chiara, Mauro Paternostro, and Ricardo Puebla.  Harnessing nonadiabatic excitations promoted by a quantum critical point: Quantum battery and spin squeezing.  Phys. Rev. Res., 4:L022017, Apr 2022.
  * [29] Robert Alicki and Mark Fannes.  Entanglement boost for extractable work from ensembles of quantum batteries.  Phys. Rev. E, 87:042123, Apr 2013.
  * [30] Wolfgang Niedenzu and Gershon Kurizki.  Cooperative many-body enhancement of quantum thermal machine power.  New Journal of Physics, 20(11):113038, Nov 2018.
  * [31] Michal Kloc, Pavel Cejnar, and Gernot Schaller.  Collective performance of a finite-time quantum otto cycle.  Phys. Rev. E, 100:042126, Oct 2019.
  * [32] C L Latune, I Sinayskiy, and F Petruccione.  Collective heat capacity for quantum thermometry and quantum engine enhancements.  New Journal of Physics, 22(8):083049, Aug 2020.
  * [33] Leonardo da Silva Souza, Gonzalo Manzano, Rosario Fazio, and Fernando Iemini.  Collective effects on the performance and stability of quantum heat engines.  Phys. Rev. E, 106:014143, Jul 2022.
  * [34] Noufal Jaseem, Sai Vinjanampathy, and Victor Mukherjee.  Quadratic enhancement in the reliability of collective quantum engines.  Phys. Rev. A, 107:L040202, Apr 2023.
  * [35] Dmytro Kolisnyk and Gernot Schaller.  Performance boost of a collective qutrit refrigerator.  Phys. Rev. Appl., 19:034023, Mar 2023.
  * [36] David Gelbwaser-Klimovsky, Wassilij Kopylov, and Gernot Schaller.  Cooperative efficiency boost for quantum heat engines.  Phys. Rev. A, 99:022129, Feb 2019.
  * [37] Francesco Campaioli, Felix A. Pollock, and Sai Vinjanampathy.  Quantum Batteries, pages 207–225.  Springer International Publishing, Cham, 2018.
  * [38] Camille L Latune, Ilya Sinayskiy, and Francesco Petruccione.  Phys. Rev. Research, 1:033192, 2019.
  * [39] H. P. Breuer and F. Petruccione.  The Theory of Open Quantum Systems.  Oxford University Press, 2002.
  * [40] Leonard Mandel and Emil Wolf.  Optical coherence and quantum optics.  Cambridge university press, 1995.
  * [41] Thomas Koshy.  Catalan numbers with applications.  Oxford University Press, 2008.
  * [42] Richard P Stanley.  Catalan numbers.  Cambridge University Press, 2015.
  * [43] Massimiliano F. Sacchi.  Thermodynamic uncertainty relations for bosonic otto engines.  Phys. Rev. E, 103:012111, Jan 2021.
  * [44] Andre C. Barato and Udo Seifert.  Thermodynamic uncertainty relation for biomolecular processes.  Phys. Rev. Lett., 114:158101, Apr 2015.
  * [45] Patrick Pietzonka and Udo Seifert.  Universal trade-off between power, efficiency, and constancy in steady-state heat engines.  Physical review letters, 120(19):190602, 2018.
  * [46] Jordan M Horowitz and Todd R Gingrich.  Thermodynamic uncertainty relations constrain non-equilibrium fluctuations.  Nature Physics, 16(1):15–20, 2020.
  * [47] Giacomo Guarnieri, Gabriel T Landi, Stephen R Clark, and John Goold.  Thermodynamics of precision in quantum nonequilibrium steady states.  Physical Review Research, 1(3):033021, 2019.
  * [48] Paul Menczel, Eetu Loisa, Kay Brandner, and Christian Flindt.  Thermodynamic uncertainty relations for coherently driven open quantum systems.  Journal of Physics A: Mathematical and Theoretical, 54(31):314002, 2021.
  * [49] Arpan Das, Shishira Mahunta, Bijay Kumar Agarwalla, and Victor Mukherjee.  Precision bound in periodically modulated continuous quantum thermal machines.  arXiv preprint arXiv:2204.14005, 2022.
  * [50] Bijay Kumar Agarwalla and Dvira Segal.  Assessing the validity of the thermodynamic uncertainty relation in quantum systems.  Physical Review B, 98(15):155438, 2018.
  * [51] Krzysztof Ptaszyński.  Coherence-enhanced constancy of a quantum thermoelectric generator.  Physical Review B, 98(8):085425, 2018.
  * [52] Loris Maria Cangemi, Vittorio Cataudella, Giuliano Benenti, Maura Sassetti, and Giulio De Filippis.  Violation of thermodynamics uncertainty relations in a periodically driven work-to-work converter from weak to strong dissipation.  Physical Review B, 102(16):165418, 2020.
  * [53] Alex Arash Sand Kalaee, Andreas Wacker, and Patrick P Potts.  Violating the thermodynamic uncertainty relation in the three-level maser.  Physical Review E, 104(1):L012103, 2021.
  * [54] Massimiliano F Sacchi.  Multilevel quantum thermodynamic swap engines.  Physical Review A, 104(1):012217, 2021.
  * [55] J. M. Raimond, P. Goy, M. Gross, C. Fabre, and S. Haroche.  Collective absorption of blackbody radiation by rydberg atoms in a cavity: An experiment on bose statistics and brownian motion.  Phys. Rev. Lett., 49:117–120, Jul 1982.
  * [56] M Gross, C Fabre, P Pillet, and S Haroche.  Observation of near-infrared dicke superradiance on cascading transitions in atomic sodium.  Physical Review Letters, 36(17):1035, 1976.
  * [57] Michael Scheibner, Thomas Schmidt, Lukas Worschech, Alfred Forchel, Gerd Bacher, Thorsten Passow, and Detlef Hommel.  Superradiance of quantum dots.  Nature Physics, 3(2):106–110, 2007.
  * [58] James Q Quach, Kirsty E McGhee, Lucia Ganzer, Dominic M Rouse, Brendon W Lovett, Erik M Gauger, Jonathan Keeling, Giulio Cerullo, David G Lidzey, and Tersilla Virgili.  Superabsorption in an organic microcavity: Toward a quantum battery.  Science advances, 8(2):eabk3160, 2022.

Appendix

*

##  Appendix A Finite temperature work and its variance

The work outputs and their variances for the independent and collective
engines can be calculated from equations Eq.(5) and (6), as shown below for
even and odd numbers of qubits.

$\displaystyle\langle{W_{\rm ind}^{{\rm even}\;n}}\rangle$ $\displaystyle=$
$\displaystyle
n\hbar\omega\Big{[}\frac{2^{n}\Gamma\left(\frac{n+1}{2}\right)e^{\frac{1}{2}\beta(n+2)\hbar\omega}{\,{}_{2}F_{1}}\left(\frac{n}{2},n+1,\frac{n}{2}+2,-e^{\beta\hbar\omega}\right)}{\sqrt{\pi}\left(e^{\beta\hbar\omega}+1\right)\Gamma\left(\frac{n}{2}+2\right)}-\tanh\frac{\beta\hbar\omega}{2}\Big{]},$
(15) $\displaystyle\langle{W_{\rm ind}^{{\rm odd}\;n}}\rangle$
$\displaystyle=$
$\displaystyle\frac{2^{n}\hbar\omega\Gamma\left(\frac{n}{2}+1\right)e^{\frac{1}{2}\beta(n+1)\hbar\omega}\left(2\;_{2}F_{1}\left(2,\frac{1-n}{2},\frac{n+3}{2},-e^{\beta\hbar\omega}\right)-\;_{2}F_{1}\left(1,\frac{1-n}{2},\frac{n+3}{2},-e^{\beta\hbar\omega}\right)\right)}{\sqrt{\pi}\Gamma\left(\frac{n+3}{2}\right)\left(e^{\beta\hbar\omega}+1\right)^{n}}$
$\displaystyle-n\hbar\omega\tanh\frac{\beta\hbar\omega}{2},$
$\displaystyle\langle{W_{\rm col}^{{\rm even}\;n}}\rangle$ $\displaystyle=$
$\displaystyle\frac{\hbar\omega\left(2e^{\frac{1}{2}\beta(n+2)\hbar\omega}-(n+2)e^{\beta\hbar\omega}+n\right)}{\left(e^{\beta\hbar\omega}-1\right)\left(e^{\beta(n+1)\hbar\omega}-1\right)},$
(17) $\displaystyle\langle{W_{\rm col}^{{\rm odd}\;n}}\rangle$
$\displaystyle=$
$\displaystyle\frac{\hbar\omega\left(e^{\frac{1}{2}\beta(n+1)\hbar\omega}+e^{\frac{1}{2}\beta(n+3)\hbar\omega}-(n+2)e^{\beta\hbar\omega}+n\right)}{\left(e^{\beta\hbar\omega}-1\right)\left(e^{\beta(n+1)\hbar\omega}-1\right)},$
(18)

$\displaystyle{\rm var}(W)_{\rm ind}^{{\rm even}\;n}$ $\displaystyle=$
$\displaystyle\frac{1}{4}\hbar^{2}\omega^{2}\text{sech}^{2}\frac{\beta\hbar\omega}{2}\Bigg{\\{}4n+\frac{2\Gamma(n+1)e^{\frac{\beta
n\hbar\omega}{2}}}{\Gamma\left(\frac{n}{2}+2\right)\Gamma\left(\frac{n}{2}\right)}\;_{2}F_{1}\left(\frac{n}{2},n+1,\frac{n}{2}+2,-e^{\beta\hbar\omega}\right)$
(19)
$\displaystyle\left[-\frac{2^{n}n\Gamma\left(\frac{n+1}{2}\right)e^{\frac{1}{2}\beta(n+2)\hbar\omega}\;_{2}F_{1}\left(\frac{n}{2},n+1,\frac{n}{2}+2,-e^{\beta\hbar\omega}\right)}{\sqrt{\pi}\Gamma\left(\frac{n}{2}+2\right)}+n\left(e^{\beta\hbar\omega}-1\right)-2\right]$
$\displaystyle-\frac{2n\Gamma(n+1)e^{\frac{\beta
n\hbar\omega}{2}}}{\Gamma\left(\frac{n}{2}+2\right)\Gamma\left(\frac{n}{2}\right)}\left(e^{\beta\hbar\omega}+1\right)^{1-n}\;_{2}F_{1}\left(1,1-\frac{n}{2},\frac{n}{2}+2,-e^{\beta\hbar\omega}\right)\Bigg{\\}}$

$\displaystyle{\rm var}(W)_{\rm col}^{{\rm even}\;n}$ $\displaystyle=$
$\displaystyle\frac{\hbar^{2}\omega^{2}e^{\beta\hbar\omega}}{\left(e^{\beta\hbar\omega}-1\right)^{2}\left(e^{\beta(n+1)\hbar\omega}-1\right)^{2}}\Bigg{\\{}-n^{2}e^{\beta
n\hbar\omega}+4e^{\beta\hbar\omega+\frac{3\beta
n\hbar\omega}{2}}+4e^{\frac{1}{2}\beta(3n+4)\hbar\omega}-(n+2)^{2}e^{\beta(n+2)\hbar\omega}$
(20) $\displaystyle\qquad-4(n+1)e^{\frac{\beta
n\hbar\omega}{2}}+4(n+1)e^{\frac{1}{2}\beta(n+2)\hbar\omega}+2(n(n+2)-4)e^{\beta(n+1)\hbar\omega}+4\Bigg{\\}},$

$\displaystyle{\rm var}(W)_{\rm ind}^{{\rm odd}\;n}$ $\displaystyle=$
$\displaystyle\frac{\hbar^{2}\omega^{2}}{\pi\left(e^{\beta\hbar\omega}+1\right)^{2}}\Bigg{\\{}4\pi
ne^{\beta\hbar\omega}-\frac{\left(e^{\beta\hbar\omega}+1\right)^{-2n}}{2\Gamma\left(\frac{n+3}{2}\right)^{2}}\Bigg{\\{}2^{2n+1}\Gamma\left(\frac{n}{2}+1\right)^{2}e^{\beta(n+1)\hbar\omega}$
(21)
$\displaystyle\left[n\left(e^{\beta\hbar\omega}-1\right)\;_{2}F_{1}\left(1,\frac{1-n}{2},\frac{n+3}{2},-e^{\beta\hbar\omega}\right)+n+1\right]^{2}+\pi(n+1)\Gamma(n+1)e^{\frac{1}{2}\beta(n+1)\hbar\omega}\left(e^{\beta\hbar\omega}+1\right)^{n}$
$\displaystyle\left[-2ne^{\beta\hbar\omega}(n\cosh\beta\hbar\omega-n-2)\;_{2}F_{1}\left(1,\frac{1-n}{2},\frac{n+3}{2},-e^{\beta\hbar\omega}\right)-(n+1)^{2}\left(e^{\beta\hbar\omega}-1\right)\right]\Bigg{\\}}\Bigg{\\}}$

and

$\displaystyle{\rm var}(W)_{\rm col}^{{\rm odd}\;n}$ $\displaystyle=$
$\displaystyle\frac{\hbar^{2}\omega^{2}e^{\frac{\beta\hbar\omega}{2}}}{\left(e^{\beta\hbar\omega}-1\right)^{2}\left(e^{\beta(n+1)\hbar\omega}-1\right)^{2}}\Bigg{\\{}4e^{\frac{\beta\hbar\omega}{2}}-\left(n^{2}+1\right)e^{\frac{\beta\hbar\omega}{2}+\beta
n\hbar\omega}+2(n-1)(n+3)e^{\frac{3\beta\hbar\omega}{2}+\beta n\hbar\omega}$
(22) $\displaystyle\qquad+e^{\beta\hbar\omega+\frac{3\beta
n\hbar\omega}{2}}-2e^{\frac{1}{2}\beta(n+2)\hbar\omega}+e^{\frac{3}{2}\beta(n+2)\hbar\omega}+6e^{\frac{1}{2}\beta(3n+4)\hbar\omega}-(2n+1)e^{\frac{\beta
n\hbar\omega}{2}}$
$\displaystyle\qquad\qquad+(2n+3)e^{\frac{1}{2}\beta(n+4)\hbar\omega}-(n(n+4)+5)e^{\frac{5\beta\hbar\omega}{2}+\beta
n\hbar\omega}\Bigg{\\}},$

where $\,{}_{p}F_{q}(a;b;z)$ is the hypergeometric function,

$\displaystyle{}_{p}F_{q}(a;b;z)$ $\displaystyle\equiv$
$\displaystyle{}_{p}F_{q}(a_{1},...,a_{p};b_{1},...,b_{q};z)$ (23)
$\displaystyle=$
$\displaystyle\sum_{k=0}^{\infty}\frac{(a_{1})_{k}...(a_{p})_{k}}{(b_{1})_{k}...(b_{q})_{k}}\frac{z^{k}}{k!}.$

Here the rising factorial $(x)_{n}$ is given by
$(x)_{n}=x(x+1)(x+2)...(x+n-1),\;n\geq 1$.

The above finite-temperature equations can be simplified further by assuming
the large $n$-limit where the summation in Eqs.(5) and (6) can be replaced by
integration, and we get the (LABEL:eq:wcolfinite)(see also Fig. 3). As
expected, Eq. (LABEL:eq:wcolfinite) simplifies to $\langle W_{\rm
col}\rangle\approx n\hbar\omega/4$ in the limit of $\beta\to 0$ (see section
III.1). The variance of the output work can be obtained using Eq. (6), where
the expression for the average of the square of the work in the large $n$
limit takes the form

$\displaystyle\langle W^{2}_{\rm col}\rangle$ $\displaystyle=$
$\displaystyle\frac{e^{\beta\hbar\omega r_{\rm max}}B-A}{\beta^{2}(e^{a}-1)},$

$A=[a(a+4)+8]$, $B=[b(b+4)+8]$, $a=\beta n\hbar\omega$, and
$b=\beta\hbar\omega(n-2r_{\rm max})$.


# On the automorphism group of a distance-regular graph

László Pyber  HUN-REN Alfréd Rényi Institute of Mathematics, Realtanoda utca
13-15, H-1053, Budapest, Hungary<EMAIL_ADDRESS>and  Saveliy V.
Skresanov  Sobolev Institute of Mathematics, 4 Acad. Koptyug avenue,
Novosibirsk, Russia<EMAIL_ADDRESS>
###### Abstract.

The motion of a graph is the minimal degree of its full automorphism group.
Babai conjectured that the motion of a primitive distance-regular graph on $n$
vertices of diameter greater than two is at least $n/C$ for some universal
constant $C>0$, unless the graph is a Johnson or Hamming graph. We prove that
the motion of a distance-regular graph of diameter $d\geq 3$ on $n$ vertices
is at least $Cn/(\log n)^{6}$ for some universal constant $C>0$, unless it is
a Johnson, a Hamming or a crown graph. This follows using an improvement of an
earlier result by Kivva who gave a lower bound on motion of the form
$n/c_{d}$, where $c_{d}$ depends exponentially on $d$. As a corollary we
derive a quasipolynomial upper bound for the automorphism group of a primitive
distance-regular graph acting edge-transitively on the graph and on its
distance-2 graph. The proofs use elementary combinatorial arguments and do not
depend on the classification of finite simple groups.

###### Key words and phrases:

distance-regular graph, motion, diameter, automorphism group

This work on the project leading to this application has received funding from
the European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No. 741420). The first
named author was partly supported by the National Research, Development and
Innovation Office (NKFIH) Grant No. K138596. The research of the second named
author was carried out within the framework of the Sobolev Institute of
Mathematics state contract (project FWNF-2022-0002).

##  1\. Introduction

The degree of a permutation $g$ of the set $V$ is the number of points of $V$
not fixed by $g$. Given a permutation group $H$ on $V$, let the minimal degree
$\operatorname{mindeg}(H)$ be the minimum of degrees of all nonidentity
elements of $H$. Describing finite primitive permutation groups with small
minimal degree is a classical problem in finite group theory which goes back
to the works of Jordan and Bochert. In [15] Bochert proved that a doubly
transitive permutation group of degree $n$ has minimal degree at least $n/4-1$
with known exceptions. Using the classification of finite simple groups
(CFSG), Liebeck and Saxl [25] classified primitive permutation groups of
degree $n$ with minimal degree less than $n/3$, and Guralnick and Magaard [20]
further strengthened this result to a description of primitive permutation
groups with minimal degree at most $n/2$.

Given a combinatorial object $G$ (a graph or a coherent configuration) let the
motion of $G$ be
$\operatorname{motion}(G)=\operatorname{mindeg}(\operatorname{Aut}(G))$. As an
attempt to generalize the above results to a combinatorial setting, Babai
proved the following result on motion of distance-regular graphs of diameter
two, that is, strongly-regular graphs:

######  Proposition 1.1 ([2, 3]).

Let $G$ be a strongly-regular graph on $n\geq 29$ vertices. Then either

$\operatorname{motion}(G)\geq\frac{n}{8},$

or $G$ or its complement is a Johnson graph, a Hamming graph or a disjoint
union of cliques of the same size.

Furthermore, Babai proposed a conjecture, which gives a natural generalization
of the above result to distance-regular graphs of arbitrary diameter:

Conjecture. (Babai, [22, Conjecture 6.6]) _There exists $\gamma>0$ such that
for any primitive distance-regular graph $G$ of diameter greater than two on
$n$ vertices either_

$\operatorname{motion}(G)\geq\gamma n,$

_or $G$ is a Johnson or a Hamming graph._

The first step to settling the conjecture was made by Kivva, who proved it for
distance-regular graphs of bounded diameter, i.e. in his result the constant
$\gamma$ is allowed to depend on the diameter of the graph. In fact, he was
able to establish his result both for primitive and imprimitive distance-
regular graphs. Recall that a _crown graph_ is a graph obtained from a regular
complete bipartite graph by removing a perfect matching.

######  Proposition 1.2 ([22, Theorem 1.12]).

For any $d\geq 3$ there exists $\gamma_{d}>0$ such that for any distance-
regular graph $G$ of diameter $d$ on $n$ vertices either

$\operatorname{motion}(G)\geq\gamma_{d}n$

or $G$ is a Johnson graph, a Hamming graph or a crown graph.

Bounds on $\operatorname{motion}(G)$ have strong structural consequences for
the structure of the automorphism group of $G$. The thickness $\theta(H)$ of a
group $H$ is the largest degree of an alternating section of $H$. It follows
from a result of Wielandt [29] (see Proposition 4.3), that if
$\operatorname{mindeg}(H)\geq\alpha n$, where $n$ is the degree of $H$ and
$\alpha>0$, then $\theta(H)\leq\frac{3}{\alpha}\log n$. In particular, Kivva’s
result has the following immediate consequence.

######  Corollary 1.3 ([22, Theorem 6.3]).

For any $d\geq 3$ there exists $\alpha_{d}>0$ such that for any distance-
regular graph $G$ of diameter $d$ on $n$ vertices either

$\theta(G)\leq\alpha_{d}\log n$

or $G$ is a Johnson graph, a Hamming graph or a crown graph.

One shortcoming of Kivva’s result is that, in the notation of Proposition 1.2,
the constant $1/\gamma_{d}$ grows exponentially in $d$, see [23, Remark 4.9].
In particular, even though it follows from a result of Pyber [27] (see
Proposition 2.1) that the diameter $d$ of a distance-regular graph on $n$
vertices of valency at least 3 is bounded above by $5\log n$, we cannot obtain
a polylogarithmic bound on the thickness of the automorphism group from
Proposition 1.2. Our main result is an improvement of Kivva’s theorem, namely,
we show that $1/\gamma_{d}$ can be taken to be a polynomial in $d$.

######  Theorem 1.4.

Let $G$ be a distance-regular graph on $n$ points of diameter $d\geq 3$. Then
either $G$ is a Johnson, Hamming or crown graph, or

$\operatorname{motion}(G)\geq C\frac{n}{d^{6}}$

for some universal constant $C>0$.

As mentioned earlier, $d\leq 5\log n$ if $G$ has valency at least 3, hence in
this case the motion is bounded below by $Cn/(5\log n)^{6}$. Now using
Wielandt’s bound for thickness, we immediately obtain the following
polylogarithmic estimate.

######  Corollary 1.5.

Let $G$ be a distance-regular graph on $n$ points of diameter $d\geq 3$. Then
either $G$ is a Johnson, Hamming or crown graph, or

$\theta(G)\leq C(\log n)^{7}$

for some universal constant $C>0$.

It follows from CFSG and a result of Babai, Cameron and Pálfy [7] that the
order of a primitive permutation group $H$ is bounded above in terms of its
degree and thickness by $n^{\theta(H)^{c}}$ for some universal constant $c>0$.
In particular, this implies a quasipolynomial bound for a primitive group of
automorphisms of a distance-regular graph, which is not a Johnson, Hamming or
a crown graph. Our second main result is an improvement to this observation,
which does not require CFSG. For a connected graph $G$ on $V$ let $G_{2}$
denote the distance 2 graph, i.e.

$G_{2}=\\{\\{x,y\\}\subseteq V\mid d(x,y)=2\\}.$

It turns out that instead of assuming that the group of automorphisms is
primitive, it suffices to assume that the group acts edge-transitively on $G$
and $G_{2}$.

######  Theorem 1.6.

Let $G$ be a primitive distance-regular graph on $n$ points of diameter
greater than two, which is not a Johnson or a Hamming graph. Assume that its
full automorphism group $H$ acts edge-transitively on $G$ and $G_{2}$. Then
$H$ has a base of size at most $C(\log n)^{9}$ for some universal constant
$C>0$, in particular, $|H|\leq n^{C(\log n)^{9}}$.

It is desirable to prove a similar bound for arbitrary groups of automorphisms
of distance-regular graphs, i.e. without necessarily assuming edge-
transitivity on $G$ or $G_{2}$. Note that Babai [3] conjectures that such a
result holds for strongly-regular graphs. This conjecture ultimately aims at
obtaining an elementary, that is, CFSG-free, proof of Cameron’s theorem [16,
Theorem 6.1] on the orders of primitive permutation groups, and our Theorem
1.6 is a step in this direction.

The main novelty of our proof lies in the following improvement of [23,
Theorem 1.7].

######  Theorem 1.7.

Let $G$ be a primitive distance-regular graph on $n$ vertices with diameter
$d\geq 3$. Then either $\operatorname{motion}(G)\geq n/(40d^{5})$ or $G$ is
Delsarte-geometric with the smallest eigenvalue at least $-5d$.

The original result of Kivva [23] relies on a series of elaborate
inequalities, involving Ostrowski’s theorem on matrix eigenvalues and the
“growth-induced tradeoff” [23, Theorem 1.2]. Our proof offers both a
significant simplification of the argument and a better bound on the motion.
The main tools for us are the Bang-Koolen theorem [10], Metsch theorem [26]
and a generalization of Babai-Szegedy’s [8] edge expansion bound to coherent
configurations. Namely, in Proposition 2.8 we prove that edge expansion of a
connected symmetric relation of a homogeneous coherent configuration is
bounded below by $k/(2d)$, where $k$ is the degree and $d$ is the diameter of
the relation. As an application of that bound, in Proposition 2.9 we show that
the second largest eigenvalue $\theta$ of a distance-regular graph of degree
$k$ and diameter $d$ satisfies $\theta\leq k(1-1/(8d^{2}))$, which may be of
independent interest. We believe that extending other results on vertex- and
edge-transitive graphs to coherent configurations may be an interesting area
of research.

In the proof of Theorem 1.4 we use Theorem 1.7 together with deep results of
Kivva on characterizations of Johnson and Hamming graphs [22].

The proof of Theorem 1.6 relies on a small combinatorial trick (Lemma 4.4)
and, surprisingly, on the argument of the first author showing that the orders
of doubly transitive permutation groups not containing the alternating group
have quasipolynomial size [28].

We mention that, similarly to distance-regular graphs, Babai conjectured that
the motion of a primitive coherent configuration of degree $n$ should be at
least $\gamma n$ for some universal constant $\gamma>0$, unless the
configuration is a so-called Cameron scheme, see [22, Conjecture 6.5] and [1,
Conjecture 12.1]. If true, this would give a combinatorial analogue of Liebeck
and Saxl’s description of primitive permutation groups of small minimal
degree. The case of rank 3 coherent configurations was settled by Babai in [2,
3] and the case of rank 4 by Kivva in [24]. Yet, recently this conjecture was
refuted by Eberhard [19] who proposed a new construction of primitive coherent
configurations with small motion. The motion conjecture for distance-regular
graphs therefore stands as an important open case.

The structure of the paper is as follows. In Section 2 we provide preliminary
results and notation for distance-regular graphs (Subsection 2.1), coherent
configurations (Subsection 2.2), and recall Kivva’s characterizations of
Johnson and Hamming graphs (Subsection 2.3). In Section 3 we prove Theorems
1.4 and 1.7, and in Section 4 we establish Theorem 1.6.

##  2\. Preliminaries

###  2.1. Distance-regular graphs

Let $G$ be a connected graph on $n$ points, and let $V$ denote the set of
vertices. For two vertices $x,y\in V$ let $d(x,y)$ denote the distance between
$x$ and $y$, and let $\Gamma_{i}(x)$ be the set of $y$ with $d(x,y)=i$.

For vertices $x$ and $y$ at distance $j$ write
$c_{j}(x,y)=|\Gamma_{j-1}(x)\cap\Gamma_{1}(y)|$,
$a_{j}(x,y)=|\Gamma_{j}(x)\cap\Gamma_{1}(y)|$ and
$b_{j}(x,y)=|\Gamma_{j+1}(x)\cap\Gamma_{1}(y)|$. The graph $G$ is called
_distance-regular_ , if these numbers depend only on the distance $j$ between
$x$ and $y$. In this case we will simply write $c_{j}$, $a_{j}$ and $b_{j}$.
If $k$ is the valency of $G$, then for all $j$ we have $a_{j}=k-b_{j}-c_{j}$.

If $d$ is the diameter of $G$, then we have the following inequalities

$\displaystyle k$ $\displaystyle=b_{0}>b_{1}\geq b_{2}\geq\dots\geq
b_{d-1}\geq 1,$ $\displaystyle 1$ $\displaystyle=c_{1}\leq c_{2}\leq\dots\leq
c_{d}\leq k.$

As distance-regular graphs of valency $2$ are cycles, we will assume that
$k>2$.

The numbers $k_{i}=|\Gamma_{i}(x)|$, $i=1,\dots,d$, do not depend on the
vertex $x\in V$ and satisfy

$\frac{k}{c_{2}}=\frac{b_{0}}{c_{2}}>\frac{b_{1}}{c_{2}}=\frac{k_{2}}{k_{1}}\geq\dots\geq\frac{k_{d}}{k_{d-1}}.$

We may also always assume that $k_{1}\leq k_{2}$ [14, Proposition 5.1.1].

In the following $\log n$ is a logarithm in base 2.

######  Proposition 2.1 ([27]).

The diameter of a distance-regular graph on $n$ vertices and valency greater
than two is at most $5\log n$.

In [11, Theorem 1.5] this bound was improved to $\frac{8}{3}\log n$, but in
our proof the multiplicative constant will not play a significant role.

The adjacency matrix of a distance-regular graph has precisely $d+1$ distinct
eigenvalues. All of them are real, the largest being $k$. Let $\theta$ denote
the second largest eigenvalue, and let $m$ be the smallest eigenvalue. We have
$m<0$.

######  Lemma 2.2 (Delsarte bound [18], [21, p. 276]).

In a distance-regular graph the size of every clique is bounded above by
$1-k/m$.

A clique of order $1-k/m$ is called a _Delsarte clique_. A clique geometry on
$G$ is a set of maximal cliques such that every edge of $G$ is contained in
exactly one clique from the set. A graph is called _Delsarte-geometric_ if it
has a clique geometry consisting of Delsarte cliques.

######  Lemma 2.3 ([22, Lemma 2.15]).

Let $G$ be a Delsarte-geometric distance-regular graph of diameter at least
$2$ with smallest eigenvalue $m$. Let $\mathcal{C}$ be a clique geometry on
$G$ consisting of Delsarte cliques. Then $m$ is an integer and every vertex in
$G$ belongs to precisely $-m$ cliques from $\mathcal{C}$.

A graph $G$ is called _sub-amply regular_ with parameters $(n,k,\lambda,\mu)$
if it is a regular graph on $n$ vertices of degree $k$ and every two adjacent
vertices have exactly $\lambda$ neighbors in common while every two vertices
at distance 2 from each other have at most $\mu$ neighbors in common. A
distance-regular graph is sub-amply regular for $\lambda=a_{1}$ and
$\mu=c_{2}$.

######  Lemma 2.4 ([22, Lemma 2.5]).

For a distance-regular graph of diameter at least $2$ one has $2\lambda\leq
k+\mu$.

The following theorem by Bang and Koolen gives a sufficient condition for a
distance-regular graph to be Delsarte-geometric.

######  Proposition 2.5 ([10]).

If $\lambda>m^{2}\mu$ for a distance-regular graph $G$, then $G$ is Delsarte-
geometric.

A result of Metsch [26] gives constraints on parameters of sub-amply regular
graphs which guarantee the existence of a certain clique geometry. Babai and
Wilmes [9, Theorem 3] gave an asymptoric version of Metsch’s theorem with a
simpler proof, which states that a sub-amply regular graph with
$k\mu=o(\lambda^{2})$ with respect to $n\to\infty$ has a maximal clique of
order approximately $\lambda$. It will be more convenient for our applications
to have an explicit version, which we derive from Metsch’s theorem directly.

######  Proposition 2.6.

Let $G$ be a sub-amply regular graph with parameters $(n,k,\lambda,\mu)$ such
that $\lambda^{2}\geq 4k\mu$. Then $G$ contains a clique of size at least
$\lambda/2$.

###### Proof.

A corollary from the result of Metsch [26, Result 2.1], see also [9, Corollary
1], implies that if

(1) $(\lambda+1)^{2}>(3k+\lambda+1)(\mu-1)$

then $G$ contains a clique of size at least

(2) $\lambda+2-(\lceil(3/2)k/(\lambda+1)\rceil-1)(\mu-1).$

Since $\lambda\leq k-1$, we have $3k+\lambda+1\leq 4k$. Hence inequality
$\lambda^{2}\geq 4k\mu$ implies inequality (1) from Metsch’s theorem, and we
have a clique of size at least (2). We claim that

$\lambda+2-(\lceil(3/2)k/(\lambda+1)\rceil-1)(\mu-1)\geq\lambda/2+2.$

Indeed, this inequality is follows from a stronger one

$\frac{\lambda}{2}\geq\frac{3k}{2(\lambda+1)}(\mu-1),$

which is implied by our assumption $\lambda^{2}\geq 4k\mu$. ∎

###  2.2. Coherent configurations and motion

Let $\operatorname{\mathfrak{X}}=(V,X)$ be a tuple, where $V$ is a set and $X$
is a partition of $V\times V$. We say that $\operatorname{\mathfrak{X}}$ is a
_homogeneous coherent configuration_ if the following holds [17, Definitions
2.1.1 and 2.1.3]:

  * •

The diagonal $\\{(v,v)\mid v\in V\\}$ lies in $X$;

  * •

For every relation $R\in X$ its transpose $\\{(v,u)\mid(u,v)\in R\\}$ lies in
$X$;

  * •

For any relations $R,S,T\in X$ and any $(u,v)\in R$, the number

$c_{ST}^{R}=|\\{w\in V\mid(u,w)\in S,\,(w,v)\in T\\}|$

does not depend on the choice of $(u,v)\in R$.

The size of $X$ is called the rank. The configuration is called _primitive_ if
all its nondiagonal relations are connected.

If $G$ is a distance-regular graph of diameter $d$, then the relations

$X_{i}=\\{(x,y)\in V\times V\mid d(x,y)=i\\},\,i=0,\dots,d,$

form a coherent configuration of rank $d+1$ on $V$. A distance-regular graph
is called _primitive_ if all its “at distance $i$“ relations $X_{i}$,
$i=1,\dots,d$, are connected. The corresponding coherent configuration is also
primitive.

In a primitive coherent configuration diameters of nondiagonal relations are
less than its rank [5, Exercise 8.4], so for a primitive distance-regular
graph diameters of $X_{i}$, $i=1,\dots,d$, are at most $d$.

The following fact is well-known.

######  Lemma 2.7 ([17, Exercise 2.7.25], [5, Exercise 2.2]).

Let $\operatorname{\mathfrak{X}}=(V,X)$ be a homogeneous coherent
configuration, and let $R,R_{1},\dots,R_{m-1}\in X$, $m\geq 2$ and $(u,w)\in
R$. Then the number of tuples $(v_{1},\dots,v_{m})\in V^{m}$ such that
$(v_{1},v_{m})=(u,w)$ and $(v_{i},v_{i+1})\in R_{i}$, $i=1,\dots,m-1$ does not
depend on the choice of $(u,w)\in R$.

For a subset $S\subseteq V$ and a graph $G$ on $V$ let $\delta_{G}(S)$ denote
the set of edges joining $S$ with $V\setminus S$ in $G$. Recall that a
relation $G$ of a coherent configuration is symmetric if it coincides with its
transpose, i.e. for every $(u,v)\in G$ we also have $(v,u)\in G$. We can view
such a relation as a regular undirected graph on $V$.

We need a generalization of a result for edge-transitive graphs from [8,
Corollary 2.6]. The proof rests on essentially the same argument as in [8].

######  Proposition 2.8.

Let $\operatorname{\mathfrak{X}}=(V,X)$ be a homogeneous coherent
configuration, and let $G\in X$ be a connected symmetric relation of degree
$k$ and diameter $d$. Then for every nonempty $S\subseteq V$ with
$|S|\leq|V|/2$ we have

$\frac{|\delta_{G}(S)|}{|S|}\geq\frac{k}{2d}.$

###### Proof.

Let $d(x,y)$ denote the distance between vertices $x,y\in V$ in the graph $G$.
A path $x_{0},x_{1},\dots,x_{m}$ in $G$ will be called a geodesic if
$m=d(x_{0},x_{m})$. Note that $x_{m},\dots,x_{1},x_{0}$ is a different
geodesic.

By [17, Theorem 2.6.7] the distance-$i$ graph $\\{(u,v)\in V\times V\mid
d(u,v)=i\\}$ is a union of some relations from $X$, in particular, the
distance between points $x$ and $y$ depends only on the relation where $(x,y)$
lies.

Let $p(x,y)$ denote the number of geodesics between $x$ and $y$. If $e$ is
some edge of $G$, we claim that the number

$P=\sum_{x,y\in V}\frac{1}{p(x,y)}|\\{L\mid L\text{ is a geodesic from
}x\text{ to }y\text{ passing through }e\\}|$

does not depend on the choice of $e\in G$. Indeed, by Lemma 2.7, the number
$p(x,y)$ depends only on the relation where $(x,y)$ lies. The number of
geodesics from $x$ to $y$ passing through $e=(z,w)$ can be expressed as

$N_{(z,w)}(x,y)=\begin{cases}p(x,z)\cdot p(w,y),&\text{ if
}d(x,z)+d(w,y)=d(x,y)-1,\\\ 0,&\text{ otherwise.}\end{cases}$

Thus, by the paragraph above, this number depends only on the relations where
$(x,z)$, $(w,y)$ and $(x,y)$ lie (recall that $(z,w)$ lies in $G$). We now
have the following formula for $P$:

$P=\sum_{R,S,T\in X}\sum_{\begin{subarray}{c}x,y\in V,\\\ (x,z)\in R,(w,y)\in
S,(x,y)\in T\end{subarray}}\frac{1}{p(x,y)}N_{(z,w)}(x,y).$

By Lemma 2.7, the number of tuples $(x,y)$ such that $(x,z)\in R$, $(w,y)\in
S$, $(x,y)\in T$ does not depend on the choice of $(z,w)\in G$, hence $P$ does
not depend on the choice of $e\in G$ as well.

Set $n=|V|$. We now claim that

$nk\cdot P=\sum_{x,y\in V}d(x,y).$

The number of edges in $G$ is exactly $nk$, and since $P$ does not depend on
the choice of $e\in G$ we have

$nk\cdot P=\sum_{e\in G}\sum_{x,y\in V}\frac{1}{p(x,y)}|\\{L\mid L\text{ is a
geodesic from }x\text{ to }y\text{ passing through }e\\}|\\\ =\sum_{x,y\in
V}\frac{1}{p(x,y)}\sum_{e\in G}|\\{L\mid L\text{ is a geodesic from }x\text{
to }y\text{ passing through }e\\}|.$

Since each geodesic from $x$ to $y$ passes through $d(x,y)$ edges (exactly
once through each edge) and there are $p(x,y)$ such geodesics, we have

$\sum_{x,y\in V}\frac{1}{p(x,y)}\sum_{e\in G}|\\{L\mid L\text{ is a geodesic
from }x\text{ to }y\text{ passing through }e\\}|\\\ =\sum_{x,y\in
V}\frac{1}{p(x,y)}\cdot d(x,y)p(x,y)=\sum_{x,y\in V}d(x,y),$

which proves the claim.

Now we are ready to prove the main result. Choose some nonempty $S\subseteq V$
with $|S|\leq n/2$. Note that for $x\in S$, $y\in V\setminus S$ a geodesic
from $x$ to $y$ must pass through an edge in $\delta_{G}(S)$, therefore:

$|S|\cdot|V\setminus S|=\sum_{x\in S}\sum_{y\in V\setminus
S}\frac{1}{p(x,y)}|\\{L\mid L\text{ is a geodesic from }x\text{ to }y\text{
through }\delta_{G}(S)\\}|.$

We extend summation to the whole of $V$ and derive

$|S|\cdot|V\setminus S|\leq\sum_{x,y\in V}\frac{1}{p(x,y)}|\\{L\mid L\text{ is
a geodesic from }x\text{ to }y\text{ through }\delta_{G}(S)\\}|\\\
\leq\sum_{x,y\in V}\frac{1}{p(x,y)}\sum_{e\in\delta_{G}(S)}|\\{L\mid L\text{
is a geodesic from }x\text{ to }y\text{ through }e\\}|\\\
=\sum_{e\in\delta_{G}(S)}\sum_{x,y\in V}\frac{1}{p(x,y)}|\\{L\mid L\text{ is a
geodesic from }x\text{ to }y\text{ through }e\\}|\\\
=\sum_{e\in\delta_{G}(S)}P=|\delta_{G}(S)|\cdot
P=\frac{|\delta_{G}(S)|}{nk}\sum_{x,y\in
V}d(x,y)\leq\frac{dn}{k}\cdot|\delta_{G}(S)|.$

Finally,

$|\delta_{G}(S)|\geq|S|\cdot\frac{k}{d}\cdot\frac{n-|S|}{n}\geq|S|\cdot\frac{k}{2d}.$

The proposition is proved. ∎

Note that the proposition above applies to distance-regular graphs.

######  Proposition 2.9.

Let $G$ be a distance-regular graph of degree $k$ and diameter $d$. Then the
second largest eigenvalue satisfies $\theta\leq k(1-\frac{1}{8d^{2}})$.

###### Proof.

By Proposition 2.8 the edge expansion $h$ of $G$ is bounded below by $k/(2d)$.
The result follows from the Cheeger inequality $h\leq\sqrt{2k(k-\theta)}$. ∎

Given a coherent configuration $\operatorname{\mathfrak{X}}=(V,X)$ and $x,y\in
V$ let $r(x,y)$ denote the unique relation in $X$ containing the pair $(x,y)$.
For $x,y\in V$ set $D(x,y)=\\{z\in V\mid r(x,z)\neq r(y,z)\\}$. Define
$D_{\min}(\operatorname{\mathfrak{X}})=\min_{x\neq y}|D(x,y)|$.

The following result is implicit in [4, 5].

######  Proposition 2.10.

Let $\operatorname{\mathfrak{X}}$ be a primitive coherent configuration on $n$
points with maximal valency $k_{\max}$. If all nondiagonal relations of
$\operatorname{\mathfrak{X}}$ have diameter at most $d$, then
$D_{\min}(\operatorname{\mathfrak{X}})\geq(n-k_{\max})/d$.

###### Proof.

Follows from [5, Lemma 8.9] and [5, Corollary 8.12]. ∎

Next result gives a lower bound on $D_{\min}$ for a configuration
corresponding to a distance-regular graph in terms of its parameters.

######  Proposition 2.11 ([23, Proposition 4.7]).

Let $G$ be a primitive distance-regular graph on $n$ vertices of diameter
$d\geq 2$ and valency $k$, and let $\operatorname{\mathfrak{X}}$ be the
associated coherent configuration. Let $\epsilon>0$. Suppose that for some
$j\in\\{1,\dots,d-1\\}$ the inequalities $b_{j}\geq\epsilon k$ and
$c_{j+1}\geq\epsilon k$ hold. Then
$D_{\min}(\operatorname{\mathfrak{X}})\geq\epsilon n/d$.

Given a permutation $g\in\operatorname{Sym}(V)$ define
$\operatorname{supp}(g)=\\{x\in V\mid x^{g}\neq x\\}$. The minimal degree of a
permutation group $H\leq\operatorname{Sym}(V)$ is the minimum over nonidentity
$g\in H$ of $|\operatorname{supp}(g)|$, i.e. it is the minimal number of
points moved by a nonidentity permutation of $H$.

For a graph $G$ (a coherent configuration $\operatorname{\mathfrak{X}}$) the
_motion_ is the minimal degree of the full automorphism group of $G$ (or
$\operatorname{\mathfrak{X}}$, respectively). We denote it by
$\operatorname{motion}(G)$ or
$\operatorname{motion}(\operatorname{\mathfrak{X}})$. If $G$ is distance-
regular, then the full automorphism groups of $G$ and the associated coherent
configuration $\operatorname{\mathfrak{X}}$ coincide, so
$\operatorname{motion}(G)=\operatorname{motion}(\operatorname{\mathfrak{X}})$
in this case.

######  Proposition 2.12 ([5, Exercise 9.5]).

For a coherent configuration $\operatorname{\mathfrak{X}}$ one has
$\operatorname{motion}(\operatorname{\mathfrak{X}})\geq
D_{\min}(\operatorname{\mathfrak{X}})$.

Given a regular graph $G$ of valency $k$, let $k=\xi_{1}\geq\dots\geq\xi_{m}$
be its eigenvalues. The _zero-weight spectral radius_ of $G$ is
$\xi=\max_{i=2,\dots,m}|\xi_{i}|$. For a distance-regular graph,
$\xi=\max\\{\theta,\,-m\\}$.

######  Proposition 2.13 ([2, Proposition 12]).

Let $G$ be a regular graph of valency $k$ on $n$ vertices with the zero-weight
spectral radius $\xi$. If every pair of vertices has at most $q$ common
neighbors in $G$, then $\operatorname{motion}(G)\geq n(k-\xi-q)/k$.

The next result is a slight modification of [22, Theorem 5.7], but the proof
stays essentially the same. The only difference is that we use a stronger
condition $\xi\leq k(1-\eta)$ instead of assuming that $c_{j}\leq\epsilon k$,
$b_{j}\leq\epsilon k$ for some $j\in\\{1,\dots,d-1\\}$.

######  Proposition 2.14 ([22, Theorem 5.7]).

Let $G$ be a Delsarte-geometric distance-regular graph of diameter $d\geq 2$
on $n$ vertices. Suppose $\mu=1$ and the smallest eigenvalue of $G$ is $m$,
where $-m\geq 3$. Let $0<\eta<1/2$ be some constant such that the zero-weight
spectral radius satisfies $\xi\leq k(1-\eta)$ and
$k\geq\max\\{4(-m)/\eta,\,m^{2}\\}$. Then $\operatorname{motion}(G)\geq
n\eta/4$.

Next proposition covers the case when $\mu=1$ and $m>-3$.

######  Proposition 2.15 ([22, Proposition 5.13]).

Let $G$ be a Delsarte-geometric distance regular graph of diameter at least
$2$. Suppose that $\mu=1$, $k>4$ and the smallest eigenvalue of $G$ is $-2$.
Then $\operatorname{motion}(G)\geq n/16$.

If a distance-regular graph $G$ with diameter $d\geq 2$ on $n$ vertices is
bipartite (and thus necessarily imprimitive), then its distance-2 graph
$G_{2}$ has two components, and the graphs induced on these components by
$G_{2}$ are called its _halved_ graphs. The halved graphs are distance-regular
with diameter $\lfloor d/2\rfloor$ on $n/2$ vertices [14, Proposition 4.2.2].

######  Proposition 2.16 ([23, Proposition 5.7]).

Let $G$ be a bipartite distance-regular graph of diameter $d\geq 3$. Let
$G^{+}$ and $G^{-}$ be the halved graphs of $G$. Then
$\operatorname{motion}(G)\geq\operatorname{motion}(G^{+})+\operatorname{motion}(G^{-})$.

If the distance-$d$ graph $G_{d}$ of a distance-regular graph $G$ of diameter
$d\geq 2$ is a union of cliques, then $G$ is called an _antipodal_ graph. A
_folded_ graph of $G$ is a graph whose vertices are the cliques of $G_{d}$ and
two vertices are adjacent in the folded graph if the corresponding cliques
have vertices adjacent in $G$. The folded graph is distance-regular of
diameter $\lfloor d/2\rfloor$ [14, Proposition 4.2.2].

######  Proposition 2.17 ([23, Proposition 5.3]).

Let $G$ be an antipodal distance-regular graph of diameter $d\geq 3$ on $n$
vertices. Let $\widetilde{G}$ be its folded graph on $\widetilde{n}$ vertices.
If $\operatorname{motion}(\widetilde{G})\geq\alpha\widetilde{n}$ for some
$\alpha>0$, then $\operatorname{motion}(G)\geq\alpha n$.

It is known that an imprimitive distance-regular graph of valency greater than
two is bipartite or antipodal (or both) [14, Theorem 4.2.1], but we will
require a more detailed description.

######  Proposition 2.18 ([23, Proposition 2.14], see also [14, Section
4.2.A]).

Let $G$ be a distance-regular graph of valency greater than two. Then:

  1. (1)

If $G$ is a bipartite graph, then its halved graphs are not bipartite;

  2. (2)

If $G$ is bipartite and either has odd diameter or is not antipodal, then its
halved graph is primitive;

  3. (3)

If $G$ is antipodal and either has odd diameter or is not bipartite, then its
folded graph is primitive;

  4. (4)

If $G$ has even diameter and is both antipodal and bipartite, then its halved
graphs $\frac{1}{2}G$ are antipodal, the folded graph $\widetilde{G}$ is
bipartite and the graphs
$\widetilde{\frac{1}{2}G}\simeq\frac{1}{2}\widetilde{G}$ are primitive.

###  2.3. Characterizations of Johnson and Hamming graphs

For $d\geq 2$ and $s\geq 2d$ the _Johnson graph_ $J(s,d)$ is defined as the
graph having all $d$-element subsets of $\\{1,\dots,s\\}$ as a vertex set,
where two vertices are adjacent if and only if the corresponding subsets
differ in exactly one element. This graph is distance-regular of diameter $d$
and valency $d(s-d)$.

Given a vertex $v$ of the graph $G$, let $G(v)$ denote the neighborhood graph,
i.e. the graph induced by $G$ on the neighbors of $v$.

######  Proposition 2.19 ([22, Theorem 1.2]).

There exists an absolute constant $\epsilon>0.0065$ such that the following is
true. Let $G$ be a Delsarte-geometric distance-regular graph of diameter
$d\geq 2$ with the smallest eigenvalue $m$. Suppose that $\mu\geq 2$ and
$\theta+1>(1-\epsilon)b_{1}$. If the valency satisfies
$k\geq\max\\{|m|^{3},\,29\\}$ and the neighborhood graph $G(v)$ is connected
for some vertex $v$, then $G$ is a Johnson graph $J(s,d)$ with $s=(k/d)+d$.

In a Delsarte-geometric distance-regular graph the neighborhood graphs are
either all connected or all disconnected [12, Theorem 5.3].

######  Proposition 2.20 ([22, Proposition 3.11]).

Let $G$ be a Delsarte-geometric distance-regular graph of diameter greater
than two and with $\mu\geq 3$. If the neighborhood graphs of $G$ are
disconnected, then $\theta+1\leq 5b_{1}/7$.

For $d,s\geq 2$ the _Hamming graph_ has $\\{1,\dots,s\\}^{d}$ as the vertex
set, and two vertices are adjacent if and only if the corresponding $d$-tuples
differ in one coordinate only. This graph is distance-regular with diameter
$d$ and valency $d(s-1)$.

######  Proposition 2.21 ([22, Corollary 4.8]).

Let $G$ be a Delsarte-geometric distance-regular graph of diameter $d\geq 2$.
Suppose that $G$ has $\mu=2$ and the smallest eigenvalue $m$. Take
$0<\epsilon<1/(6m^{4}d)$. If $\theta\geq(1-\epsilon)b_{1}$ and
$c_{i}\leq\epsilon k$, $b_{i}\leq\epsilon k$ for some $i\in\\{1,\dots,d\\}$,
then $G$ is a Hamming graph $H(d,s)$ for $s=(k/d)+1$.

##  3\. Proof of Theorems 1.4 and 1.7

We will prove both theorems from the title simultaneously. Theorem 1.7 will be
an intermediate step in the proof of Theorem 1.4.

Let $G$ be a primitive distance-regular graph of valency $k$ on $n$ points,
where $n$ is large enough (we may assume that by choosing the constant $C$
appropriately). Since cycle graphs have large motion, we may assume that
$k\geq 3$. Let $d\geq 3$ denote the diameter of $G$. We first consider the
case when $G$ is primitive.

Assume that $c_{2}>k/(20d^{4})$. Then

$20d^{4}>\frac{k}{c_{2}}=\frac{b_{0}}{c_{2}}>\frac{b_{1}}{c_{2}}=\frac{k_{2}}{k_{1}}\geq\dots\geq\frac{k_{d}}{k_{d-1}}.$

If $\operatorname{\mathfrak{X}}$ is a coherent configuration associated with
$G$, then the valencies of its nondiagonal relations are $k_{1},\dots,k_{d}$.
If $k_{\max}=k_{i}$, $i\in\\{2,\dots,d\\}$, is the maximal valency, then
$k_{i}<k_{i-1}\cdot 20d^{4}$ and hence $k_{\max}/(20d^{4})<n-k_{\max}$. By
Proposition 2.10, we have $D_{\min}\geq k_{\max}/(20d^{5})$.

If $k_{\max}\geq n/2$, then $D_{\min}\geq n/(40d^{5})$ and we have a bound on
motion by Proposition 2.12. If $k_{\max}<n/2$, then
$D_{\min}\geq(n-k_{\max})/d>n/(2d)$ and we again have a similar bound. From
now one we assume that $c_{2}\leq k/(20d^{4})$. In particular, $k\geq
20d^{4}$.

If $\operatorname{motion}(G)>n/2$ then we are done, so let $g$ be a
nonidentity automorphism of $g$ with $|\operatorname{supp}(g)|\leq n/2$. For
$S=\operatorname{supp}(g)$ Proposition 2.8 gives
$\frac{|\delta_{G}(S)|}{|S|}\geq\frac{k}{2d}$, so there exists a vertex $x\in
S$ with at least $k/(2d)$ neighbors in $V\setminus S$. Vertices $x$ and
$x^{g}$ are distinct and have at least $k/(2d)$ common neighbors. If $x$ and
$x^{g}$ are not adjacent, then $c_{2}\geq k/(2d)$ which contradicts our
assumption. Therefore they are adjacent and thus $\lambda=a_{1}\geq k/(2d)$.

The graph $G$ is sub-amply regular with $\mu=c_{2}\leq k/(20d^{4})$. Then
$k\mu\leq k^{2}/(20d^{4})$ while $\lambda^{2}\geq k^{2}/(4d^{2})$. Therefore

$\lambda^{2}\geq\frac{k^{2}}{4d^{2}}\geq\frac{4k^{2}}{20d^{4}}\geq 4k\mu$

and by Proposition 2.6 the graph $G$ contains a clique of size at least
$\lambda/2$. By the Delsarte bound, $\lambda/2\leq 1+k/(-m)$, thus

$-m\leq\frac{k}{\lambda/2-1}\leq\frac{k}{\frac{k}{4d}-1}<5d.$

Then $m^{2}\mu\leq 25d^{2}\frac{k}{20d^{4}}<\frac{k}{2d}\leq\lambda$, and by
Proposition 2.5 the graph $G$ is Delsarte-geometric. Note that $\mu<\lambda$.

At this point of the proof we have established Theorem 1.7. Now we proceed
with the proof of Theorem 1.4. We roughly follow the argument in [22, Theorem
5.16].

Recall that $1\leq\mu\leq k/(20d^{4})$, so $20d^{4}\leq k$ and $d$ is bounded
in terms of $k$. For a graph of diameter $d$ and valency $k$ we have $n\leq
1+k^{d}$, hence $n$ is bounded in terms of $k$. In particular, by choosing $n$
large enough, we may assume that $k$ is larger than any fixed absolute
constant (we note that this holds in general for any distance-regular graph by
the positive solution of the Bannai-Ito conjecture in [13], but we need not
use this deep result in our argument).

We use the following positive parameter throughout the proof:

$\epsilon=\frac{1}{6\cdot(5d)^{4}\cdot d}.$

By Proposition 2.11, if $b_{j}\geq\epsilon k$ and $c_{j+1}\geq\epsilon k$ for
some $j\in\\{1,\dots,d-1\\}$, then

$\operatorname{motion}(G)\geq\frac{\epsilon n}{d}\geq C\cdot\frac{n}{d^{6}}$

for some universal constant $C>0$. If for all $j$ the inequalities for $b_{j}$
and $c_{j+1}$ do not hold, then since $b_{j}$ are nonincreasing and $c_{j}$
are nondecreasing, we can find some $j\in\\{1,\dots,d\\}$ with
$b_{j}\leq\epsilon k$ and $c_{j}\leq\epsilon k$.

Now we consider several cases.

Case $\theta<(1-\epsilon)b_{1}$. The zero-weight spectral radius of $G$ is
equal to $\xi=\max\\{\theta,\,-m\\}$, consequently,
$\xi\leq\max\\{(1-\epsilon)b_{1},\,-m\\}$. By Lemma 2.4, $2\lambda\leq k+\mu$
hence

$b_{1}=k-1-\lambda\geq\frac{k-\mu-2}{2}.$

As $\mu\leq k/(20d^{4})$, we have $2\mu+4<k$, therefore

$b_{1}\geq\frac{k-\mu-2}{2}>\frac{k}{4},$

and $(1-\epsilon)b_{1}>(1-\epsilon)k/4$. Since $-m<5d<k/4(1-\epsilon)$, as
$k\geq 20d^{4}$, we obtain $\xi\leq(1-\epsilon)b_{1}$.

Every pair of vertices of $G$ has at most $\max\\{\lambda,\,\mu\\}$ common
neighbors. Since this maximum is equal to $\lambda$, Proposition 2.13 implies

$\operatorname{motion}(G)\geq n\frac{k-\xi-\lambda}{k}\geq
n\frac{k-(1-\epsilon)b_{1}-\lambda}{k}.$

Now $(1-\epsilon)b_{1}+\lambda\leq k-\epsilon b_{1}\leq(1-\epsilon/4)k$, thus
$\operatorname{motion}(G)\geq n\epsilon/4\geq C\cdot n/d^{5}$ for some
universal constant $C>0$.

Case $\theta\geq(1-\epsilon)b_{1}$ and $\mu\geq 3$. We claim that for $n$
sufficiently large we have $\max\\{|m|^{3},\,29\\}\leq k$. Since
$|m|^{3}<(5d)^{3}$ and $k\geq 20d^{4}$, this holds for $d\geq 7$. If $d<7$,
then this holds as $k>(5\cdot 6)^{3}$ for $n$ large enough.

Suppose that the neighborhood graphs of $G$ are disconnected, then by
Proposition 2.20, we have $\theta+1\leq 5b_{1}/7$. Then
$5b_{1}/7>(1-\epsilon)b_{1}$ implying $\epsilon>2/7$, which is a
contradiction. We may assume that $\epsilon<0.0065$, therefore the
neighborhood graphs of $G$ are connected and Proposition 2.19 shows that $G$
is a Johnson graph.

Case $\theta\geq(1-\epsilon)b_{1}$ and $\mu=2$. Since $b_{j}\leq\epsilon k$
and $c_{j}\leq\epsilon k$ for some $j\in\\{1,\dots,d-1\\}$, and
$\epsilon<1/(6m^{4}d)$, Proposition 2.21 implies that $G$ is a Hamming graph.

Case $\mu=1$. Assume that $-m\geq 3$. By Proposition 2.9, $\theta\leq
k(1-1/(8d^{2}))$. As $-m\leq 5d$ and $k\geq 20d^{4}$, we have a bound on the
zero-weight spectral radius:

$\xi=\max\\{\theta,\,-m\\}\leq k\left(1-\frac{1}{8d^{2}}\right).$

Set $\eta=1/(8d^{2})$, so $\xi\leq k(1-\eta)$. Clearly $k>m^{2}$ and
$k>4m/\eta=32(-m)d^{2}$. Proposition 2.14 implies
$\operatorname{motion}(G)\geq n\eta/4=n/(32d^{2})$ as wanted.

If $-m<3$, then by Lemma 2.3, $m$ is an integer and every vertex lies in
precisely $-m$ cliques from our geometry, hence $m=-2$. Then by Proposition
2.15 we have $\operatorname{motion}(G)\geq n/16$. This finishes the proof of
the primitive case of Theorem 1.4, namely, we established the following.

######  Proposition 3.1.

Let $G$ be a primitive distance-regular graph on $n$ points of diameter $d\geq
3$. Then either $G$ is a Johnson or a Hamming graph, or

$\operatorname{motion}(G)\geq\gamma_{d}n$

where $\gamma_{d}=C/d^{6}$ for some universal constant $C>0$.

We now assume that $G$ is an imprimitive distance-regular graph. We need the
following lemma, which is an improvement of [23, Theorem 5.8] but with a
better constant.

######  Lemma 3.2.

Let $G$ be a distance-regular bipartite graph of diameter $d\geq 4$ on $n$
vertices. If a halved graph of $G$ is primitive, then

$\operatorname{motion}(G)\geq\gamma^{\prime}_{d}n$

for $\gamma^{\prime}_{d}=\gamma_{\lfloor d/2\rfloor}/2$, where $\gamma_{d}$ is
a function from Proposition 3.1.

###### Proof.

Let $G^{\prime}$ be a primitive halved graph of $G$. By Proposition 2.16,
$\operatorname{motion}(G)\geq\operatorname{motion}(G^{\prime})$, and since
$G^{\prime}$ has diameter $\lfloor d/2\rfloor$ and $n/2$ vertices, the claim
follows from Proposition 3.1. ∎

The rest of the argument closely follows [23, Theorem 5.16], but uses better
constants. We mention that “Conjecture 1.5” in [23] corresponds to our
Proposition 3.1.

Recall that an imprimitive distance-regular graph is bipartite or antipodal,
or both. If $G$ is bipartite but not antipodal and $d\geq 4$, then by
Proposition 2.18 (2) its halved graph is primitive and hence
$\operatorname{motion}(G)\geq\gamma^{\prime}_{d}n$ by Lemma 3.2. If $G$ is
bipartite of diameter $d=3$, then by [23, Theorem 5.12] the graph $G$ is
either a crown graph or $\operatorname{motion}(G)\geq n/6$.

If $G$ is bipartite and antipodal of even diameter $d\geq 6$, then by
Proposition 2.18 (4) its folded graph $\widetilde{G}$ is bipartite (and not
antipodal) of diameter $d/2$. A crown graph is antipodal, hence the previous
paragraph implies

$\operatorname{motion}(\widetilde{G})\geq\min(\gamma^{\prime}_{d},1/6)\widetilde{n},$

where $\widetilde{n}$ is the number of vertices in $\widetilde{G}$. Then by
Proposition 2.17

$\operatorname{motion}(G)\geq\min(\gamma^{\prime}_{d},1/6)n.$

If $G$ is bipartite and antipodal of diameter $d=4$, then by [23, Proposition
5.10], $\operatorname{motion}(G)\geq 0.15n$.

We are left with cases when $G$ is antipodal but not bipartite, and when $G$
is antipodal of odd diameter. By Proposition 2.18 (3), the folded graph
$\widetilde{G}$ is primitive. If $d=3$, then $\operatorname{motion}(G)\geq
n/13$ by [23, Proposition 5.14]. If $d\geq 4$ and $\widetilde{G}$ is not a
Johnson graph, a Hamming graph or a complement to $J(s,2)$ or $H(2,s)$, and
$\widetilde{G}$ has at least 29 vertices, then Proposition 3.1 and Proposition
1.1 imply

$\operatorname{motion}(\widetilde{G})\geq\min(\gamma_{\lfloor
d/2\rfloor},1/8)\widetilde{n},$

where $\widetilde{n}$ is the number of vertices in $\widetilde{G}$. Then by
Proposition 2.17

$\operatorname{motion}(G)\geq\min(\gamma_{\lfloor d/2\rfloor},1/8)n.$

Finally, it is easy to see that if $\widetilde{G}$ has at most $28$ vertices,
then $\operatorname{motion}(G)\geq n/14$, and it follows from [23, Theorem
5.15] that a Johnson graph, a Hamming graph, and complements to $J(s,2)$ or
$H(2,s)$ have no antipodal covers (taking into account our bound on the number
of vertices). Hence we proved that $\operatorname{motion}(G)\geq\gamma n$ for

$\gamma=\min\left(\gamma_{d},\gamma^{\prime}_{d},\gamma^{\prime}_{\lfloor
d/2\rfloor},\gamma_{\lfloor d/2\rfloor},\frac{1}{14}\right).$

For an appropriate universal constant $C>0$ we have $\gamma\geq C/d^{6}$, so
the proof of Theorem 1.4 is finished.

##  4\. Proof of Theorem 1.6

For a permutation group $H$ on $V$ and a subset $\Sigma\subseteq V$ let
$H_{\Sigma}$ denote the pointwise stabilizer of $\Sigma$. Given a graph $G$
with vertex set $V$, we say that $\Sigma\subseteq V$ _splits_ an edge $e$ with
respect to $H$, if the two endvertices of $e$ lie in different
$H_{\Sigma}$-orbits on $V$.

######  Proposition 4.1 ([6, Splitting Lemma 3.1]).

Let $G$ be a graph on $V$ having $q$ edges. Assume that a permutation group
$H$ acts edge-transitively on $G$. If $\Sigma\subseteq V$ splits at least
$cq$, $0<c<1$, edges with respect to $H$, then there exists $\Delta\subseteq
V$ which splits every edge of $G$ with respect to $H$ and
$|\Delta|\leq|\Sigma|\cdot\lceil\frac{-\log q}{\log(1-c)}\rceil$.

Given a permutation group $H$ on $V$, we say that $\Sigma\subseteq V$ is a
_halving set_ if $H_{\Sigma}$ has no orbits of size greater than $|V|/2$.
Recall that the _thickness_ $\theta(H)$ of a group $H$ is the largest degree
of an alternating section of $H$.

######  Proposition 4.2 ([28, Lemma 3]).

Let $H$ be a permutation group on $V$, and suppose that $\theta(H)<k$ for some
$k\geq 12$. Then there is a halving set $\Sigma\subseteq V$ for $H$ with
$|\Sigma|\leq 4k$.

We will require the following corollary of Wielandt’s bound for thickness
[29].

######  Proposition 4.3 ([22, Corollary 6.2]).

Let $H$ be a permutation group of degree $n$ with minimal degree at least
$\alpha n$. Then $\theta(H)\leq\frac{3}{\alpha}\log n$.

The following lemma is key to our proof. Recall that $\\{x,y\\}$ is an edge of
a distance 2 graph $G_{2}$ if and only if $d(x,y)=2$.

######  Lemma 4.4.

Let $G$ be a connected graph on $V$ and let $H$ be its group of automorphisms.
If a nonempty $\Sigma\subseteq V$ splits all edges of $G$ and $G_{2}$, then
$H_{\Sigma}$ is trivial.

###### Proof.

Let $\Delta\subseteq V$ be the set of points stabilized by $H_{\Sigma}$; it
suffices show that $\Delta=V$.

Clearly $\Sigma\subseteq\Delta$, hence $\Delta$ is nonempty. Suppose that
$\Delta$ is a proper subset of $V$, then by connectivity of $G$ there exists
some vertex $x\in V\setminus\Delta$ connected by an edge with some
$y\in\Delta$. By the definition of $\Delta$, the vertex $x$ is not stabilized
by $H$, thus for some $h\in H$ the vertex $x^{\prime}=x^{h}$ lies in
$V\setminus\Delta$ and is adjacent to $y$. There is a path $x,y,x^{\prime}$ in
$G$, so $d(x,x^{\prime})\leq 2$. By our assumptions, $x$ and $x^{\prime}$ must
lie in different $H$-orbits, which is a contradiction with the definition of
$x^{\prime}$. Therefore $\Delta=V$ and we are done. ∎

_Proof of Theorem 1.6._ Let $G$ be a distance-regular graph on $V$, where
$|V|=n$, of diameter greater than two. Let $H$ be its full automorphism group.
By Theorem 1.4 and Proposition 2.1, the minimal degree of $H$ is at least
$Cn/(\log n)^{6}$ for some universal constant $C>0$. By Wielandt’s bound,
$\theta(H)\leq\frac{3}{C}(\log n)^{7}$ and by Proposition 4.2, there exists a
halving set $\Sigma\subseteq V$ with $|\Sigma|\leq C^{\prime}(\log n)^{7}$ for
some universal constant $C^{\prime}>0$.

Let $S\subseteq V$ be some orbit of $H_{\Sigma}$ on $V$. Clearly $|S|\leq n/2$
and by Proposition 2.8, we have $|\delta_{G}(S)|/|S|\geq k/(2d)$, where $k$ is
the valency of $G$ and $d$ is the diameter. This implies that at least
$k|S|/(2d)$ edges of $G$ with an endpoint in $S$ are split by $\Sigma$.
Summing by all orbits of $H$ and recalling that we may count the same edge
twice, we get that at least $kn/(4d)$ edges of $G$ are split by $\Sigma$. If
$q=kn/2$ is the number of edges of $G$, then $\Sigma$ splits at least $q/(2d)$
edges of $G$.

Since $G$ is primitive, the distance 2 graph $G_{2}$ is also connected and its
diameter is bounded by $d$, hence the same reasoning applies and $\Sigma$
splits at least $q_{2}/(2d)$ edges of $G_{2}$, where $q_{2}$ is the number of
edges in $G_{2}$. By Proposition 4.1, there are sets $\Delta$ and $\Delta_{2}$
of size at most $4|\Sigma|d\log n$ which split every edge of the graphs $G$
and $G_{2}$, respectively. By taking $\Sigma^{\prime}=\Delta\cup\Delta_{2}$
and recalling that $d\leq 5\log n$ by Proposition 2.1, we obtain that
$|\Sigma^{\prime}|\leq C^{\prime\prime}(\log n)^{9}$ for some universal
constant $C^{\prime\prime}>0$, and $\Sigma^{\prime}$ splits all edges of $G$
and $G_{2}$. Lemma 4.4 shows that $\Sigma^{\prime}$ is a base for $H$, which
finishes the proof. ∎

##  5\. Acknowledgement

The authors would like to thank B. Kivva for the remarks which improved the
exposition of this paper.

## References

  * [1] L. Babai, _Group, graphs, algorithms: the graph isomorphism problem_ , Proc. Int. Cong. of Math. (2018), Rio de Janeiro, Vol. 3, 3303–3320.
  * [2] L. Babai, _On the automorphism groups of strongly regular graphs I._ In Proc. 5th Conf. on Innov. in Th. Comp. Sc. (ITCS’14) (2014), 359–368.
  * [3] L. Babai, _On the automorphism groups of strongly regular graphs II._ J. Algebra 421 (2015), 560–578..
  * [4] L. Babai, _On the order of uniprimitive permutation groups_ , Annals of Math. 113 (1981), 553–568.
  * [5] L. Babai, _Primitive coherent configurations and the order of uniprimitive permutation groups_ , https://people.cs.uchicago.edu/~laci/papers/uni-update.pdf.
  * [6] L. Babai, _On the order of doubly transitive permutation groups_ , Invent. math. 65 (1982), 473–484.
  * [7] L. Babai, P.J. Cameron, P.P Pálfy, _On the orders of primitive groups with restricted nonabelian composition factors_ , J. Algebra 79 (1) (1982), 161–168.
  * [8] L. Babai, M. Szegedy, _Local expansion of symmetrical graphs_ , Combinatorics, Probability and Computing 1 (1992), 1–11.
  * [9] L. Babai, J. Wilmes, _Asymptotic Delsarte cliques in distance-regular graphs_ , J. Algebr. Comb. 43 (2016), 771–782.
  * [10] S. Bang, J.H. Koolen, _On distance-regular graphs with smallest eigenvalue at least m_ , J. Combin. Theory Ser. B 100 no. 6, (2010), 573–584.
  * [11] S. Bang, A. Hiraki, J.H. Koolen, _Improving diameter bounds for distance-regular graphs_ , European J. Combin. 27 (1) (2006), 79–89.
  * [12] S. Bang, A. Hiraki, J.H. Koolen, _Delsarte clique graphs_ , European J. Combin. 28 (2) (2007), 501–516.
  * [13] S. Bang, A. Dubickas, J.H. Koolen, V. Moulton, _There are only finitely many distance-regular graphs of fixed valency greater than two_ , Adv. Math. 269 (2015), 1–55.
  * [14] A.E. Brouwer, A.M. Cohen, A. Neumaier, _Distance-Regular Graphs_ , Springer-Verlag, Berlin, 1989.
  * [15] A. Bochert, _Ueber die Classe der transitiven Substitutionengruppen_ , Math. Ann. 40 (2) (1892), 176–193.
  * [16] P.J. Cameron, _Finite permutation groups and finite simple groups_ , Bull. London Math. Soc. 13 (1981), 1–22.
  * [17] G. Chen, I. Ponomarenko, _Lectures on coherent configurations_ , Central China Normal Univ Press, Wuhan, 2019.
  * [18] P. Delsarte, _An algebraic approach to the association schemes of coding theory_ , Philips J. Res., no. 10 (1973), vi+97.
  * [19] S. Eberhard, _Hamming sandwiches_ , Combinatorica 43 (2023), 233–256.
  * [20] R. Guralnick, K. Magaard, _On the minimal degree of a primitive permutation group_ , J. Algebra 207 JA987451 (1998), 127–145.
  * [21] C.D. Godsil, _Algebraic combinatorics_ , Chapman & Hall, New York, 1993.
  * [22] B. Kivva, _A characterization of Johnson and Hamming graphs and proof of Babai’s conjecture_ , J. Comb. Theory, Ser. B, 151 (2021), 339–374.
  * [23] B. Kivva, _On the spectral gap and the automorphism group of distance-regular graphs_ , J. Comb. Theory, Ser. B, 149 (2021), 161–197.
  * [24] B. Kivva, _On the automorphism groups of rank-4 primitive coherent configurations_ , J. Comb. Theory, Ser. B, 164 (2024), 245–298.
  * [25] M.W. Liebeck, J. Saxl, _Minimal degrees of primitive permutation groups, with an application to monodromy groups of covers of Riemann surfaces_ , Proc. Lond. Math. Soc. s3-63 (2) (1991), 266–314.
  * [26] K. Metsch, _On a characterization of bilinear forms graphs_ , Eur. J. Comb. 20 (4), (1999), 293–306.
  * [27] L. Pyber, _A bound for the diameter of distance-regular graphs_ , Combinatorica 19 (4), (1999), 549–553.
  * [28] L. Pyber, _On the orders of doubly transitive permutation groups, elementary estimates_ , J. Comb. Theory, Ser. A, 62 (1993), 361–366.
  * [29] H. Wielandt, _Abschätzungen für von vorgeschriebenem Transitivitätsgrad_ , Berlin, 1934, Helmut Wielandt: Mathematical Works, Vol. 1, Group theory (ed. B. Huppert and H. Schneider, de Gruyter, Berlin, 1994), 23–47.