# Nonequilibrium electron rings for synchrotron radiation production

Hywel Owen<EMAIL_ADDRESS>The University of Manchester and
Cockcroft Institute, Manchester M13 9PL, United Kingdom  Peter H. Williams
STFC Daresbury Laboratory and Cockcroft Institute, Daresbury Science and
Innovation Campus, Warrington WA4 4AD, United Kingdom  Scott Stevenson  The
University of Oxford, Oxford OX1 2JD, United Kingdom

###### Abstract

Electron storage rings used for the production of synchrotron radiation (SR)
have an output photon brightness that is limited by the equilibrium beam
emittance. By using interleaved injection and ejection of bunches from a
source with repetition rate greater than 1 kHz, we show that it is practicable
to overcome this limit in rings of energy $\sim 1$ GeV. Sufficiently short
kicker pulse lengths enable effective currents of many milliamperes, which can
deliver a significant flux of diffraction-limited soft X-ray photons. Thus,
either existing SR facilities may be adapted for non-equilibrium operation, or
the technique applied to construct SR rings smaller than their storage ring
equivalent.

###### pacs:

29.20.db,29.20.dk,29.27.Bd,41.60.Ap

††preprint:

The storage ring - developed from the synchrotron McMillan (1945); Goward and
Barnes (1946) \- overcomes the relativistic limitation of fixed-target
particle physics experiments by colliding counter-rotating beams of particles
O’Neill (1956, 1963). The emitted synchrotron radiation (SR) Schwinger (1949)
from cycling electron synchrotrons was already used parasitically from the
1970s for techniques such as X-ray crystallography Rowe and Mills (1973);
Worgan (1982); Suller and Thompson (1978). Second- and third-generation
facilities Thompson (1980) use storage rings; third-generation rings provide
magnet-free straight sections with zero (or small) dispersion Thompson (1982,
1983), and may accommodate periodic magnetic insertion devices (IDs) that
induce strong (and sometimes coherent) photon emission at selected
wavelengths. The use of electron storage rings for SR blossomed in the 1980s
and is now a mature field with around sixty facilities conducting a myriad of
experiments Laclare (2001); Bilderback et al. (2005). Electron beam quality is
characterised by the emittances $\epsilon_{x}$ and $\epsilon_{y}$, where, for
a single dipole radius $\rho$, $\epsilon_{x}=55\hbar\gamma^{2}\langle
H_{x}\rangle_{s}/32\sqrt{3}m_{e}cJ_{x}\rho$ is determined by the energy (via
$\gamma$) and by the magnetic lattice via
$\left<H_{x}\right>_{s}=\left<\beta_{x}\eta_{x}^{\prime
2}+2\alpha_{x}\eta_{x}\eta_{x}^{\prime}+\gamma_{x}\eta_{x}^{2}\right>_{s}$
($J_{x}$ is the horizontal damping partition number). Demand for better
resolution pushes ring design to ever-smaller $\epsilon_{x}$ using lattices
that minimise $\left<H_{x}\right>_{s}$ (and thereby the equilibrium between
radiation damping and quantum excitation), for example the ‘Theoretical
Minimum Emittance’ (TME) lattice Lee and Teng (1991); Lee and Choi (2003,
2004); Wang (2009) in which only a small fraction of the circumference $C$ may
be used for IDs. $\epsilon_{y}$ is coupled to $\epsilon_{x}$ mainly by ring
magnet roll misalignments Loulergue and Payet (1998); Clarke et al. (2001):
originally 10% for the European Synchrotron Radiation Facility (ESRF) Witte
(1990); ESRF (1987), coupling values better than 0.1% are achieved today
Bartolini et al. (2008), smaller than the diffraction limit for many IDs. One
may also increase $C$ to incorporate more dipoles to minimise $<\eta_{x}>$ in
them Ropert et al. (2000); Elleaume and Ropert (2003); Tsumaki and Kumagai
(2006), conceptually simple but expensive and yielding only modest gains: it
is therefore unlikely that rings much larger than the $\sim 1$ km APS, ESRF
and SPRING-8 will be built (PETRA-III is a special case of a large pre-
existing ring for particle physics Balewski et al. (2004)).

Fourth-generation SR facilities overcome some limitations of storage rings,
particularly the linac-driven free-electron laser (FEL) Fuoss (1988); Winick
et al. (1994); Arthur et al. (1995) first demonstrated at X-ray wavelengths at
the LCLS Emma et al. (2009); Ratner et al. (2009). Whilst FELs may provide
enormous peak brightness, their average flux is rather modest in comparison
with storage rings due to the limitations in either gun or linac macropulse
repetition rate. Average flux may be increased by using superconducting
cavities and high-current electron injectors: the energy-recovery linac (ERL)
uses both to provide quasi-continuous bunch trains whilst alleviating power
requirements in the cavities: each electron’s energy is recycled as the
returned bunches are decelerated, and passed to new electrons Neil and
Merminga (2002); Quinn et al. (2005). JLab has demonstrated 10 kW of FEL power
at 100 MeV electron energy in a 10 mA ERL Neil et al. (2000, 2006).

Low-energy ERLs may circulate large currents without the strong intrabeam
scattering (IBS) that would limit the emittance of a storage ring at the same
energy Hoffstaetter et al. (2006); Smith et al. (2006). At sufficiently large
electron energies ERLs gain an emittance advantage over that possible from a
storage ring. We recall that in the absence of dilution the emittance
$\epsilon=\epsilon_{n}/\beta\gamma$ reduces adiabatically under acceleration.
In Figure 1 we compare the achievable emittances from a typical modern
electron injector to TME lattices of differing size. This emittance advantage
has led to several proposed facilities (e.g. Seddon et al. (2006)), including
the conversion of existing storage rings Hoffstaetter et al. (2012); Borland
et al. (2007). However, since each electron only contributes once to the
effective current the charge passing through the accelerator is very high and
beam loss control will be difficult. Several proposals assume tens of MWs of
circulating beam power and losses kept to a few W/m: for example, a 6 GeV ERL
circulating 100 mA through 1 km deposits 600 kW continuously if losses are
kept to typical values $\sim$0.1%, whereas the equivalent storage ring would
deposit only 2000 J if a fill were completely lost. An ERL cavity injection
scheme may be used to circulate each injected bunch four times instead of just
once Nakamura (2008), but extending that concept is very challenging.

Figure 1:  Variation of circulating beam emittance in a storage ring versus
energy, comparing an injector (with normalised emittance
$\epsilon_{n}=10^{-6}$ m) with equilibrium emittances for storage rings
composed from TME double-bend achromats of 5, 10 and 20 cells (dashed lines).

All present-day electron storage rings circulate bunches where classical SR
damping and quantum excitation give an equilibrium emittance
$\epsilon_{\mathrm{eq}(x,y)}$, the stored charge either accumulated over
repeated bunch injection or transferred in one train from another storage
ring. The injected emittances $\epsilon_{\mathrm{inj}(x,y)}$ are usually
larger than $\epsilon_{\mathrm{eq}(x,y)}$, particularly in the vertical plane,
although this need not be the case Boege et al. (1998). At energies above
$\sim 1$ GeV the damping time $\tau_{x,y}=3m_{e}^{3}c^{5}C\rho/(2\pi
r_{e}J_{x,y}E^{3})$ falls to a few milliseconds: linear collider damping rings
use this to take a (relatively) large injector emittance and reduce it;
bunches are left in just long enough to sufficiently damp before they are
passed to a downstream linac.

We propose the opposite process, in which low-emittance bunches are repeatedly
injected into a ring and grow larger: they are ejected and replaced with new
ones well before equilibrium is obtained, so that the effective emittance is
essentially $\epsilon_{\mathrm{inj}}$. This process may be carried out in any
of the radio-frequency (RF) buckets, limited by the injection rate. This
concept has been proposed to improve Compton photon production Yu et al.
(2009) and for electron cooling Derbenev et al. (2007), but not yet proposed
for the production of SR. At large enough energies $\tau_{x,y}$ will be too
short to allow repeated injection at a feasible rate. However, we here show an
energy range exists between a lower-energy emittance crossover point and the
damping rate limit where there is an emittance advantage with reasonable
average output flux.

Table 1: Principal properties of the MAX-II, MAX-III and Super-ACO storage rings when operated in equilibrium. | MAX-II | MAX-III | Super-ACO
---|---|---|---
Max. Energy (GeV) | 1.5 | 0.7 | 0.8
Design current (mA) | 200 | 250 | 400
C (m) | 90 | 36 | 72
$\rho$ (m) | 3.33 | 3.036 | 1.7
$T_{\mathrm{rev}}$ (ns) | 300 | 120 | 240
$\epsilon_{\mathrm{eq},(x)}$ (nm) | 8.9 | 12.8 | 38.0
$\tau_{x,y}$ (ms) | 6.7 | 24 | 18
$\sigma_{t}$ ($1\sigma$, ps) | 53 | 89 | 90
$\sigma_{E}$ ($1\sigma$) $(/10^{-4})$ | 7.1 | 8.6 | 5.3
$J_{x}$ | 1.0 | 2.4 | 1.0

We illustrate this non-equilibrium (NEQ) approach using the designs of the
existing Swedish MAX-II Sjostrom et al. (2007); LeBlanc and Lindgren (1996)
and MAX-III storage rings Sjostrom et al. (2009) and the French Super-ACO ring
Couprie et al. (1991); Zyngier et al. (1985), which in normal operation have
the properties given in Table 1; the energy of each ring may be readily
lowered to reduce $\epsilon_{\mathrm{eq}(x)}$ and increase $\tau_{x,y}$. We
assume full-energy injection of bunches with charge $q=1$ nC is possible at a
frequency $f_{l}$ up to 10 kHz, from a suitable injector with
$\epsilon_{n}=10^{-6}$ m: several FEL proposals indicate these parameters are
accessible Sannibale et al. (2012); Aeppli et al. (2009). We consider the use
of fast bunch-by-bunch injection and extraction as proposed for collider
damping rings, for example the 0.73 m DAF$\Phi$NE and 1.4 m KEK kicker designs
where short enough rise/fall times (12.4 ns and 6 ns) and peak-to-peak (p-p)
stability of 0.07% are possible with deflection angles at 1 GeV of 2.6 mrad
and 3.0 mrad respectively Alesini et al. (2006); Naito et al. (2007);
continuous repetition rates over 1 kHz have been proposed for other fast
kickers Aeppli et al. (2009); Placidi et al. (2012). Over straight lengths of
a few metres the total kick angle from several kickers ($>5$ mrad for $E<1$
GeV) is sufficient to translate the beam at least 10 mm from an injection
septum, thereby providing ample Touschek and quantum lifetime for the
circulating beam.

There is no significant radiation damping, since by definition electrons are
resident for a time smaller than $\tau_{x,y}$. Emittance dilution due to
injection steering errors will persist, and may be estimated as
$\Delta\epsilon/\epsilon=(\Delta x^{2}+(\beta_{0}\Delta
x^{\prime}+\alpha_{0}\Delta x)^{2})/2\beta_{0}\epsilon$. Dilution is small at
energies below 1 GeV for achievable p-p stabilities and may be suppressed by
reducing $\beta_{0}$ at the injection point; other dilution effects such as
optical mismatch and steering fluctuations are expected to be small Fischer et
al. (1997).

The low energy and large bunch charges mean that IBS is important Kubo et al.
(2005). Growth rate estimates using elegant Borland (2000) indicate initial
characteristic times $\tau_{\mathrm{IBS}}\lesssim 1$ ms for injected bunch
lengths $\sigma_{t}\sim 1$ ps; $\tau_{\mathrm{IBS}}$ varies linearly with
$\sigma_{t}$, and so may be made greater than $\tau_{x,y}$ by increasing
$\sigma_{t}$ from 1 ps to the equilibrium stored lengths of either 50 or 90
ps. Large injected $\sigma_{t}$ may be achieved either with linac RF phasing
or with bunch shear from a magnetic chicane. For large $\sigma_{t}$ the
variation in deflection angle over the kicker pulse is still small, and even
at $\sigma_{t}\sim$ 90 ps the dilution effect on the circulating emittance is
less than 1%. Interleaved injection/extraction is therefore feasible, but the
alternative scheme of repeatedly injecting bunch trains is not, since the much
longer required kicker pulse will vary significantly in amplitude over the
train. We note that other collective effects such as resistive wall
instabilities, microbunching and so on will either be small or controllable
with feedback Hock and Wolski (2009).

Figure 2:  Variation of emittance with energy, comparing an injector (with
normalised emittance $\epsilon_{n}=10^{-6}$ m) with the equilibrium emittance
of the MAX-II, MAX-III and Super-ACO storage rings. Also shown is the range of
the diffraction-limited emittance $\epsilon_{d,\mathrm{crit}}$ for bending
radii $\rho$ from 1.7 m to 3.33 m.

The number of bunches $n_{b}$ that may be circulated in NEQ mode is limited by
the kicker rise/fall time rather than by $f_{l}$, as it is in damping rings.
For $q=1$ nC the total current that may be circulated is simply $I=q/\tau_{b}$
where $\tau_{b}$ is the possible bunch spacing, i.e. $I=8.3$ mA for 12 ns
spacing (6 ns kicker rise and fall time), with
$n_{b}=T_{\mathrm{rev}}/\tau_{b}$; there is an insignificant reduction in
effective $I$ due to the time taken to replace each bunch (which is smaller
than $T_{\mathrm{rev}}$). The residence time of each bunch in the ring is
determined by the repetition rate $f_{l}$ of the injector as
$\tau_{r}=n_{b}/f_{l}$. With a 1 kHz injector rate the residence times are
long enough that IBS would determine the emittance, but at $f_{l}=10$ kHz
$\tau_{r}$ is small enough that no significant emittance growth occurs. Table
2 gives example operating energies for each of the considered rings, and shows
that a significant emittance advantage may be obtained using NEQ operation.

Table 2: Non-equilibrium operation of MAX-II, MAX-III and Super-ACO, assuming an injected bunch length equal to the natural bunch length at full energy. The beam current in all cases is 8.3 mA, limited by the 12 ns bunch spacing. | MAX-II |  | MAX-III |  | Super-ACO |
---|---|---|---|---|---|---
Energy (GeV) | 0.7 | 1.0 | 0.5 | 0.7 | 0.5 | 0.8
$n_{b}$ | 25 | 25 | 10 | 10 | 20 | 20
$\tau_{r}$ (ms) for $f_{l}=10$ kHz | 2.5 | 2.5 | 1.0 | 1.0 | 2.0 | 2.0
$\tau_{x,y}$ (ms) | 66 | 23 | 13,32 | 4.8,11.5 | 74 | 18
$\tau_{\mathrm{IBS}x,init}$ (ms) | 13 | 22 | 2.0 | 3.8 | 4.8 | 11.7
$\epsilon_{\mathrm{eq},x}$ (nm) | 2.73 | 3.95 | 6.5 | 12.8 | 15.0 | 38.0
$\epsilon_{\mathrm{inj},x}$, $\epsilon_{\mathrm{inj},y}$ (nm) | 0.730 | 0.511 | 1.28 | 1.02 | 1.02 | 0.639
$\epsilon_{d,\mathrm{crit}}$ (nm) | 0.432 | 0.148 | 2.11 | 1.08 | 0.604 | 0.138
$\Delta\epsilon/\epsilon$ (x,y) from p-p stability (%) | 16,2.7 | 22,3.8 | 1.0,0.7 | 1.4,1.0 | 5.0,5.8 | 8.0,9.4
Dump power (kW) for $f_{l}=10$ kHz | 7 | 10 | 5 | 7 | 5 | 8

IDs will deliver photons comparable to the critical wavelength
$\lambda_{c}=4\pi\rho/3\gamma^{3}$ of the main ring dipoles: we may therefore
use the diffraction-limited emittance at $\lambda_{c}$, given as
$\epsilon_{d,\mathrm{crit}}=\rho/3\gamma^{3}$, as an estimate of the useful
emittance from NEQ operation; this is compared to the equilibrium and NEQ
emittances in Figure 2. Equating $\epsilon_{d,\mathrm{crit}}$ with
$\epsilon_{\mathrm{inj}}$ we obtain the electron energy at which NEQ operation
gives an advantage, $E\simeq m_{e}c^{2}\sqrt{\rho/3\epsilon_{n}}$, around 0.4
GeV to 0.7 GeV for typical dipole radii. The upper limit on $E$ is set by
ensuring $\tau_{r}\ll\tau_{x}$, in other words that $f_{l}\gg 2\pi
r_{e}JE^{3}/3m_{e}^{3}c^{6}\rho\tau_{b}$; this limit is about 1.5 GeV to 2.5
GeV depending on $\rho$, and is similar to the energy limit from kicker
emittance dilution. The beam power deposited at the dump is simply that from
the injector, and is readily manageable even at $f_{l}=10$ kHz Seddon et al.
(2006); Aeppli et al. (2009); Wiseman et al. (1997); Maslov et al. (2006);
Fernandez-Hernando and Angal-Kalinin (2010): the beam power is therefore
limited by the kicker rise/fall time. A significant beam power saving is
obtained over an equivalent ERL, with no emittance penalty. Compared to an
equilibrium storage ring, the horizontal emittance is reduced significantly
with NEQ operation and may be brought close to $\epsilon_{d,\mathrm{crit}}$;
the equilibrium vertical emittance is typically smaller than
$\epsilon_{d,\mathrm{crit}}$, so the increase from NEQ operation incurs no
penalty for most IDs. The range of output photon energies over which NEQ
operation gives an emittance advantage is from about $\sim 0.1$ keV to $\sim
2$ keV. We suggest that NEQ rings of simple optical design and small $\rho$
may be an inexpensive way to add spontaneous photon beamlines to a linac that
drives a soft X-ray or higher energy FEL. A small circumference lattice can
give NEQ emittances similar to much larger rings operated in equilibrium,
whilst still delivering simultaneous photons with significant flux to numerous
IDs and their associated experiments.

This work was supported in part by the Science and Technology Facilities
Council. We would like to thank Jim Clarke and James Jones of STFC Daresbury
Laboratory, and Sara Thorin of MAX-Lab, for technical information and useful
discussions.

## References

  * McMillan (1945) E. McMillan, Phys. Rev. 68, 143 (1945).
  * Goward and Barnes (1946) F. K. Goward and D. E. Barnes, Nature 158, 413 (1946).
  * O’Neill (1956) G. O’Neill, Phys. Rev. 102, 1418 (1956).
  * O’Neill (1963) G. O’Neill, Science 141, 679 (1963).
  * Schwinger (1949) J. Schwinger, Phys. Rev. 75, 1912 (1949).
  * Rowe and Mills (1973) E. Rowe and F. Mills, Particle Accelerators 4, 211 (1973).
  * Worgan (1982) J. Worgan, Nucl. Inst. Meth. 195, 49 (1982).
  * Suller and Thompson (1978) V. Suller and D. Thompson, Nucl. Inst. Meth. 152, 1 (1978).
  * Thompson (1980) D. Thompson, Nucl. Inst. Meth. 177, 43 (1980).
  * Thompson (1982) D. Thompson, Nucl. Inst. Meth. 201, 1 (1982).
  * Thompson (1983) D. Thompson, Nucl. Inst. Meth. 208, 1 (1983).
  * Laclare (2001) J. L. Laclare, Nucl. Inst. Meth. A467, 1 (2001).
  * Bilderback et al. (2005) D. Bilderback, P. Elleaume, and E. Weckert, J. Phys. B 38, 773 (2005).
  * Lee and Teng (1991) S. Lee and L. Teng, in _Proc. 14th Part. Accel. Conf., San Francisco_ (1991), ‘Theoretical Minimum Emittance Lattice for an Electron Storage Ring’.
  * Lee and Choi (2003) T. Lee and J. Choi, Nucl. Inst. Meth. A515, 410 (2003).
  * Lee and Choi (2004) T. Lee and J. Choi, Nucl. Inst. Meth A534, 371 (2004).
  * Wang (2009) C.-X. Wang, Phys. Rev. ST Accel. Beams 12, 061001 (2009).
  * Loulergue and Payet (1998) A. Loulergue and J. Payet, in _Proc. 6th European Part. Accel. Conf., Stockholm_ (1998), ‘Correction of vertical dispersion and betatron coupling for SOLEIL storage ring’.
  * Clarke et al. (2001) J. A. Clarke et al., in _Proc. 19th Part. Accel. Conf., Chicago_ (2001), ‘Recent Developments in the DIAMOND Storage Ring Design’.
  * Witte (1990) K. Witte, Synchrotron Radiation News 3, 6 (1990).
  * ESRF (1987) ESRF, Tech. Rep. (1987), ‘ESRF Foundation Phase Report (Red Book)’.
  * Bartolini et al. (2008) R. Bartolini, I. P. S. Martin, J. H. Rowland, P. Kuske, and F. Schmidt, Phys. Rev. ST Accel. Beams 11, 104002 (2008).
  * Ropert et al. (2000) A. Ropert et al., in _Proc. 7th European Part. Accel. Conf., Vienna_ (2000), ‘Towards the ultimate storage ring-based light source’.
  * Elleaume and Ropert (2003) P. Elleaume and A. Ropert, Nucl. Inst. Meth. A500, 18 (2003).
  * Tsumaki and Kumagai (2006) K. Tsumaki and N. Kumagai, Nucl. Inst. Meth. A565, 394 (2006).
  * Balewski et al. (2004) K. Balewski, W. Brefeld, W. Decking, Y. Li, G. Sahoo, and R. Wanzenberg, in _Proc. 9th European Part. Accel. Conf., Lucerne_ (2004), ‘PETRA III: a new high Brilliance Synchrotron Radiation Source at DESY’.
  * Fuoss (1988) P. H. Fuoss, Nucl. Inst. Meth. A264, 497 (1988).
  * Winick et al. (1994) H. Winick et al., Nucl. Inst. Meth. A347, 199 (1994).
  * Arthur et al. (1995) J. Arthur, G. Materlik, R. Tatchyn, and H. Winick, Rev. Sci. Inst. 66, 1987 (1995).
  * Emma et al. (2009) P. Emma et al., in _Proc. 23rd Part. Accel. Conf., Vancouver_ (2009), ‘First Lasing of the LCLS X-Ray FEL at 1.5 Angstroms’.
  * Ratner et al. (2009) D. Ratner et al., in _Proceedings of FEL2009 Conference, Liverpool_ (2009), ‘FEL Gain Length and Taper Measurements at LCLS’.
  * Neil and Merminga (2002) G. Neil and L. Merminga, Rev. Mod. Phys. 74, 685 (2002).
  * Quinn et al. (2005) F. M. Quinn et al., Proc. SPIE 5917, 59170C (2005).
  * Neil et al. (2000) G. Neil et al., Phys. Rev. Lett. 84, 662 (2000).
  * Neil et al. (2006) G. Neil et al., Nucl. Inst. Meth. A557, 9 (2006).
  * Hoffstaetter et al. (2006) G. Hoffstaetter, V. Litvinenko, and H. L. Owen, Nucl. Inst. Meth. A557, 345 (2006).
  * Smith et al. (2006) S. Smith et al., Nucl. Inst. Meth. A557, 145 (2006).
  * Seddon et al. (2006) E. A. Seddon et al., Tech. Rep., CCLRC (2006), ‘4GLS Conceptual Design Report’.
  * Hoffstaetter et al. (2012) G. Hoffstaetter et al., Tech. Rep., Cornell University (2012), ‘Cornell Energy Recovery Linac - PDDR’.
  * Borland et al. (2007) M. Borland et al., Nucl. Inst. Meth. A582, 54 (2007).
  * Nakamura (2008) T. Nakamura, Phys. Rev. ST Accel. Beams 11, 032803 (2008).
  * Boege et al. (1998) M. Boege et al., in _Proc. 6th European Part. Accel. Conf., Stockholm_ (1998), ‘The Swiss Light Source Accelerator Complex’.
  * Yu et al. (2009) P. Yu, Y. Wang, and W. Huang, Phys. Rev. ST Accel. Beams 12, 061301 (2009).
  * Derbenev et al. (2007) Y. Derbenev et al., in _Proc. COOL 2007, Bad Kreuznach_ (2007), ‘Electron Cooling for a High Luminosity Electron-Ion Collider’.
  * Sjostrom et al. (2007) M. Sjostrom, H. Tarawneh, E. Wallen, and M. Eriksson, Nucl. Inst. Meth. A577, 425 (2007).
  * LeBlanc and Lindgren (1996) G. LeBlanc and L. J. Lindgren, in _Proc. 5th European Part. Accel. Conf., Sitges_ (1996), ‘The Injection Scheme for the New 1.5 GeV Storage Ring, MAX-II’.
  * Sjostrom et al. (2009) M. Sjostrom, E. Wallen, M. Eriksson, and L. J. Lindgren, Nucl. Inst. Meth. A601, 229 (2009).
  * Couprie et al. (1991) M. E. Couprie, M. Velghe, R. Prazeres, D. Jaroszynski, and M. Billardon, Phys. Rev. A 44, 1301 (1991).
  * Zyngier et al. (1985) J. L. Zyngier et al., IEEE Trans. Nucl. Sci. NS32, 3371 (1985).
  * Sannibale et al. (2012) F. Sannibale et al., Phys. Rev. S. T. Accel. Beams 15, 103501 (2012).
  * Aeppli et al. (2009) G. Aeppli et al., Tech. Rep., Science and Technology Facilities Council (2009), ‘NLS Project, Science Case and Outline Facility Design’.
  * Alesini et al. (2006) D. Alesini, F. Marcellini, S. Guiducci, and P. Raimondi, Tech. Rep., LNF-INFN (2006), ‘Fast injection kickers for DAFNE and ILC damping rings’, EUROTeV-Report-2006-025.
  * Naito et al. (2007) T. Naito, H. Hayano, M. Kuriki, N. Terunuma, and J. Urakawa, Nucl. Inst. Meth. A571, 599 (2007).
  * Placidi et al. (2012) M. Placidi et al., in _Proc. 3rd International Part. Accel. Conf., New Orleans_ (2012).
  * Fischer et al. (1997) W. Fischer, W. Mackay, S. Peggs, and J. Wei, Particle Accelerators 58, 181 (1997).
  * Kubo et al. (2005) K. Kubo, S. K. Mtingwa, and A. Wolski, Phys. Rev. ST Accel. Beams 8, 081001 (2005).
  * Borland (2000) M. Borland, Tech. Rep., Advanced Photon Source (2000), technical Report LS-287.
  * Hock and Wolski (2009) K. M. Hock and A. Wolski, Phys. Rev. ST Accel. Beams 12, 091001 (2009).
  * Wiseman et al. (1997) M. Wiseman et al., in _Proc. 17th Part. Accel. Conf., Vancouver_ (1997), ‘High Power Electron Beam Dumps at CEBAF’.
  * Maslov et al. (2006) M. Maslov, M. Schmitz, and V. Sychev, Tech. Rep., DESY (2006).
  * Fernandez-Hernando and Angal-Kalinin (2010) J. L. Fernandez-Hernando and D. Angal-Kalinin, in _Proc. 1st International Part. Accel. Conf., Kyoto_ (2010), ‘Beam Dump and Collimation Design Studies for NLS’.


# Holey graphs: very large Betti numbers are testable

Dániel Szabó  Université Paris Cité, CNRS, IRIF, Paris, France  Simon Apers
Université Paris Cité, CNRS, IRIF, Paris, France

###### Abstract

We show that the graph property of having a (very) large $k$-th Betti number
$\beta_{k}$ for constant $k$ is testable with a constant number of queries in
the dense graph model. More specifically, we consider a clique complex defined
by an underlying graph and prove that for any $\varepsilon>0$, there exists
$\delta(\varepsilon,k)>0$ such that testing whether
$\beta_{k}\geq(1-\delta)d_{k}$ for $\delta\leq\delta(\varepsilon,k)$ reduces
to tolerantly testing $(k+2)$-clique-freeness, which is known to be testable.
This complements a result by Elek (2010) showing that Betti numbers are
testable in the bounded-degree model. Our result combines the Euler
characteristic, matroid theory and the graph removal lemma.

##  1 Introduction

In graph property testing we wish to decide whether a graph has a certain
property, or whether it is “far” from having that property [Gol10]. In the
_dense_ graph model, an $n$-vertex graph is $\varepsilon$-far from having a
property if we have to add or remove more than $\varepsilon n^{2}$ edges for
the graph to have the property. A _tester_ for a given property is a
randomized algorithm that, given query access to the adjacency matrix of a
graph $G$, can distinguish with constant success probability whether $G$ has
that property or is $\varepsilon$-far from having it. A graph property is said
to be _testable_ if there exists a tester that makes a number of queries that
is a function only of $\varepsilon$, and so independent of the graph size.
Examples of testable properties are bipartiteness, triangle-freeness and, more
generally, monotone (closed under removing edges) and hereditary (closed under
removing vertices) graph properties [AS05, AS08].

In this work we prove the following theorem (for a more formal statement see
Theorem 2).

######  Theorem 1 (Informal).

The property of having a (very) large $k$-th Betti number is testable for
constant $k$.

Strictly speaking, we consider the $k$-th Betti number of the _clique complex_
associated to $G$. This is the simplicial complex defined by the family of all
vertex subsets that induce a clique in $G$. On an intuitive level, the $k$-th
Betti number $\beta_{k}$ of this complex counts the number of independent
$k$-dimensional “holes” in the complex, which is bounded by the number of
$k$-cliques $d_{k}$ in $G$. More formally, $\beta_{k}$ equals the rank of the
$k$-th _homology group_. We prove Theorem 1 by showing that, for any constant
$k$ and $\varepsilon>0$, there exists $\delta(\varepsilon,k)>0$ such that
testing whether $\beta_{k}\geq(1-\delta)d_{k}$ for some fixed
$\delta\leq\delta(\varepsilon,k)$ reduces to tolerantly testing
$(k+2)$-clique-freeness. We prove the result for

$\delta(\varepsilon,0)=\sqrt{2\varepsilon}\;,\qquad\delta(\varepsilon,1)=\varepsilon/3\;,\qquad\delta(\varepsilon,k)=1/\mathrm{tower}(k^{4}\log(1/\varepsilon))\;\;(k>1).$

Here the $\mathrm{tower}(\ell)$-function denotes a height-$\ell$ tower of
powers of 2’s – this explains the extra quantifier in “ _(very)_ large Betti
numbers”. Nonetheless, this property is neither trivial for constant $k$ and
$\varepsilon$ nor monotone or hereditary. To see this, consider the
$(k+1)$-partite graph which has $d_{k}=(\frac{n}{k+1})^{k+1}$ and
$\beta_{k}=(\frac{n}{k+1}-1)^{k+1}$ [BSG+22, Proposition 1], and so
$\beta_{k}/d_{k}=1-O(k^{2}/n)$. This shows that for any $k$ and $\delta>0$
there exist graphs with the property $\beta_{k}\geq(1-\delta)d_{k}$. Moreover,
the quantity $\beta_{k}/d_{k}$ increases as a function of $n$, so the property
cannot be monotone or hereditary.

#### Betti numbers in the bounded-degree model.

This work was partly motivated by the result of Elek [Ele10] in the _bounded-
degree model_. In this model, the graph is assumed to have a constant bound
$d$ on the vertex degrees, and a query reveals the (at most $d$) neighbours of
a vertex. Elek showed that, for any $\varepsilon>0$ and with a number of
queries only dependent on $\varepsilon$, it is possible to return an estimate
$\hat{\beta}_{k}$ satisfying $\hat{\beta}_{k}=\beta_{k}\pm\varepsilon n$ for
$k<d$ (for $k\geq d$ necessarily $d_{k}=\beta_{k}=0$). The proof is based on
(sparse) graph limits, and is very different from our approach.

Unfortunately, such a result in the dense graph model is not possible:
returning an estimate $\hat{\beta}_{k}=\beta_{k}\pm\varepsilon n$ (or even
$\hat{\beta}_{k}=\beta_{k}\pm\varepsilon d_{k}$) requires $\Omega(n)$ many
queries in the dense graph model. To see this, consider the case $k=0$ for
which $d_{0}=n$ and $\beta_{0}$ equals the number of connected components of
the graph. The cycle graph has $\beta_{0}=1$ while any graph with $\leq n/2$
edges has $\beta_{0}\geq n/2$. However, it takes $\Omega(n)$ queries to
distinguish these graphs in the dense model. This motivates the weaker
formulation of large Betti number testability that we use in our work.111Note
also that the contrapositive, having a small Betti number, is trivial to test.
E.g., a graph cannot be far from having small Betti number $\beta_{0}$ since
we can always add a cycle, thereby setting $\beta_{0}=1$.

#### Quantum algorithms for large Betti numbers.

Another motivation came from a recent stream of works on quantum algorithms
for estimating Betti numbers (see e.g. [LGZ16, GCD22, Hay22, CK22]). Under
certain conditions (e.g., a form of well-conditionedness), these works suggest
an exponential quantum speedup over classical algorithms, returning an
estimate $\hat{\beta}_{k}=\beta_{k}\pm\varepsilon n^{k}$ in time
$\mathrm{poly}(n,k,1/\varepsilon)$. Such an estimate is only relevant for very
large Betti numbers ($\beta_{k}$ scaling with $n^{k}$), and a stringent
question is whether “typical” graphs can have such large Betti numbers. In a
recent work [AGSS23] a classical benchmark algorithm was proposed based on
path-integral Monte Carlo. The algorithm has a polynomial runtime in certain
regimes, narrowing down the conditions for a potential exponential quantum
speedup.

The current work investigates this question from a new (property testing)
perspective, and it yields a tool to investigate whether typical graphs can
have a (very) large Betti number.

#### Open questions.

Our work raises a number of open questions. The most obvious one is whether
our results can be pushed further. E.g., it might be possible to test more
moderately sized Betti numbers, or Betti numbers for non-constant $k$ (the
case of interest for quantum algorithms).

Another open direction is to generalize the framework of graph property
testing to simplicial complexes more generally. By limiting ourselves to
clique complexes, we could phrase our results in the graph property testing
language, but this might not be the most natural approach.

#### Outline of proof and paper.

In Section 2 we formally introduce property testing, simplicial complexes, and
the necessary matroid theory.

The first contribution appears in Section 3. We use the matroid notion of
independence to relate the Betti number $\beta_{k}$ to the number of
“independent” $K_{k+2}$ cliques in the graph, and we bound the total number of
cliques as a function of the number of independent cliques. Using the Euler
characteristic we show that having a large Betti number is equivalent to
having few independent $K_{k+2}$ subgraphs.

Finally, in Section 4, we build on these tools to reduce the problem of
testing large Betti numbers to that of (tolerantly) testing clique-freeness,
which is known to be testable. In particular, we show that having a large
Betti number implies that the graph is close to being $K_{k+2}$-free, while
being far from having a large Betti number implies that the graph is far from
being $K_{k+2}$-free.

##  2 Preliminaries

In this section we introduce necessary but well-known preliminaries on graph
property testing, simplicial complexes and matroid theory.

###  2.1 Property testing and subgraph freeness

In graph property testing we want to decide if an $n$-vertex input graph $G$
has a property $P$ or if it is $\varepsilon$-far from any graph satisfying
$P$. In the dense graph model we have query access to elements of the
adjacency matrix of $G$, and we want to minimise the number of queries we
make. This model was introduced in [GGR98].

######  Definition 1 ($\varepsilon$-far).

The distance of two graphs $G$ and $G^{\prime}$ is defined as

$D(G,G^{\prime})=\frac{\min_{\pi}\\{G\triangle\pi(G^{\prime})\\}}{n^{2}},$

where $\pi$ is any permutation of the vertices and $\triangle$ denotes the
symmetric difference of the two edge sets. We say that $G$ is _$\varepsilon$
-far_ from property $P$ if $D(G,G^{\prime})>\varepsilon$ for all $G^{\prime}$
satisfying $P$.

######  Definition 2 (Property tester).

In the dense graph model, a randomised algorithm $A$ is a property testing
algorithm for property $P$ if given query access to the adjacency matrix of
the input graph $G$, it satisfies the following.

  * •

If $G$ satisfies $P$ then $A$ returns “YES” with probability $\geq 2/3$.

  * •

If $G$ is $\varepsilon$-far from $P$ then $A$ returns “NO” with probability
$\geq 2/3$.

A _tolerant_ property testing algorithm satisfies a stronger constraint: for
some $\varepsilon_{1}<\varepsilon_{2}$, it distinguishes (i) $G$ being
$\varepsilon_{1}$-close to $P$, from (ii) $G$ being $\varepsilon_{2}$-far from
$P$.

We call a property $P$ (tolerantly) testable if there is a (tolerant) property
testing algorithm such that the number of queries it makes is independent of
the input length.

The following well-known lemma (that can be proved using the Szemerédi
regularity lemma [Sze78]) has been central to proving many testability
results, and we will also use it.

######  Lemma 1 (Graph removal lemma, [Für95]).

For any graph $H$ and any $\varepsilon>0$ there exists a $\delta>0$ such that
the following holds: any $n$-vertex graph $G$ ($|V(H)|<n$) that contains at
most $\delta n^{|V(H)|}$ copies of $H$ as subgraphs can be made $H$-free by
removing at most $\varepsilon n^{2}$ edges (i.e. $G$ is $\varepsilon$-close to
being $H$-free).

It follows almost directly from this result that, for any constant-sized graph
$H$, the property of being $H$-free is testable [ADL+94]. Combined with the
fact that every testable property in the dense graph model is also
_tolerantly_ testable [FN07]222More precisely, they prove that for every
testable property there is a distance approximation algorithm. This implies
tolerant testability., we get the following lemma which we are going to use
later.

######  Lemma 2.

For any graph $H$ the property of $H$-freeness is tolerantly testable in the
dense graph model. The number of queries depends only on the distance
parameters $\varepsilon_{1},\varepsilon_{2}$ and on $|H|$.

###  2.2 Simplicial complexes

A simplicial complex is a downward closed set family over a set $V$ of
vertices. As such, it can be thought of as a higher-dimensional generalisation
of graphs (albeit more restrictive than hypergraphs).

######  Definition 3 (Simplicial complex).

An (abstract) simplicial complex $\Delta$ is a set of subsets of the vertex
set $V$, such that if $S\in\Delta$ and $S^{\prime}\subset S$ then also
$S^{\prime}\in\Delta$. The sets in $\Delta$ with cardinality $k+1$ are called
the $k$-faces of $\Delta$.

We are going to denote the set of $k$-faces of a complex by
$F_{k}(\Delta)=\\{S\in\Delta,|S|=k+1\\}$ and its size by
$d_{k}(\Delta)=|F_{k}(\Delta)|$. When it is clear from the context which
simplicial complex is being considered, we will write only $F_{k}$ and
$d_{k}$. If the largest subset of $V$ that is in the complex is of cardinality
$D+1$ then we say that the complex is $D$-dimensional.

A clique complex is a special case of a simplicial complex, and is defined by
some underlying graph $G$. The sets in the clique complex associated to $G$
are exactly the cliques of $G$. This implies for instance that a size-$(k+1)$
subset $S\subseteq V$ is in the complex if (and only if) all the size-$k$
subsets of $S$ are in the complex.

For our analysis we wish to consider unoriented faces. This is in contrast to
most of the works on simplicial homology, but for our combinatorial arguments
it is sufficient and makes more intuitive sense. The $k$-chain group $C_{k}$
of a simplicial complex $\Delta$ over an Abelian group G is defined as
$C_{k}=\\{\sum_{i=1}^{d_{k}}\alpha_{i}S_{i}\\}$ where $S_{i}\in F_{k}(\Delta)$
and $\alpha_{i}\in\textbf{{G}}$. Most sources consider integer coefficients
($\textbf{{G}}=\mathbb{Z}$), but for our unoriented case we are going to
consider only binary coefficients ($\textbf{{G}}=\mathbb{Z}_{2}$). This
corresponds to taking $C_{k}=2^{F_{k}}$, the set of all the subsets of
$F_{k}$. This way, we will refer to the elements of $C_{k}$ either as a sum of
$k$-faces or as a set of $k$-faces – the two are equivalent.

For each $k>0$, the $k$-th boundary operator $\delta_{k}$ is a homomorphism
that maps a $k$-face to the sum of the $(k-1)$-faces that “surround” the
$k$-face.

######  Definition 4 (Boundary operator).

For any $k\geq 1$ the $k$-th boundary operator is a homomorphism
$\delta_{k}:C_{k}\to C_{k-1}$. For $S\in F_{k}(\Delta)$ and
$S=\\{v_{1},v_{2},\dots,v_{k+1}\\}$ it is defined by
$\delta_{k}(S)=\sum_{i=1}^{k+1}S\setminus\\{v_{i}\\}$.

It follows from this definition that the boundary of a boundary is always
zero, i.e., $\delta_{k}(\delta_{k+1}(.))=0$. Sometimes we are going to use the
same notation for _boundary vector_ s: for $S\in F_{k}$,
$\delta_{k}(S)\in\\{0,1\\}^{d_{k-1}}$, where a coordinate is 1 iff the
corresponding $(k-1)$-face appears in the boundary of $S$.

Now we can define the Betti numbers, that are at the center of interest in
this article.

######  Definition 5 (Betti number).

The $k$-th Betti number $\beta_{k}$ of a simplicial complex $\Delta$ is the
rank of the $k$-th homology group:

$\beta_{k}(\Delta)=\textnormal{rk}(\ker(\delta_{k})/\operatorname{\mathrm{im}}(\delta_{k+1})).$

More intuitively, define a $k$-dimensional hole as a subset $H\subseteq
F_{k}(\Delta)$ that _has_ no boundary and _is_ no boundary. Equivalently,
$\delta_{k}(H)=0$ (and so $H\in\ker(\delta_{k})$) and there exists no
$H^{\prime}\subseteq F_{k+1}(\Delta)$ such that $\delta_{k+1}(H^{\prime})=H$
(and so $H\notin\operatorname{\mathrm{im}}(\delta_{k+1})$). Then $\beta_{k}$
counts the number of “independent” $k$-dimensional holes in the complex –
where we formalize the notion of independence in the next section.

Our result strongly relies on the so-called Euler characteristic. This is a
topological invariant that connects the number of faces in a complex to its
Betti numbers.

######  Definition 6 (Euler characteristic).

The Euler characteristic of a simplicial complex $\Delta$ is

$\chi(\Delta)=\sum_{k=0}^{\infty}(-1)^{k}d_{k}(\Delta)=\sum_{k=0}^{\infty}(-1)^{k}\beta_{k}(\Delta).$

###  2.3 Matroids

The appropriate notion of independence of faces and of holes comes from
matroid theory. A matroid is a downward closed set family with an additional
property333In this sense matroids are a specialisation of simplicial
complexes, although we are going to use them in a different way. called the
exchange property.

######  Definition 7 (Matroid).

A matroid $M$ over ground set $E$ is a family of subsets $I\subseteq 2^{E}$
called the independent subsets of $E$, and which satisfies the following
properties.

  1. 1.

$\emptyset\in I$.

  2. 2.

If $A\in I$ and $B\subseteq A$ then $B\in I$.

  3. 3.

If $A,B\in I$ and $|B|<|A|$ then $\exists v\in A\setminus B$ such that
$B\cup\\{v\\}\in I$.

The easiest example of a matroid is a graph. In this case, the ground set $E$
in the matroid is the edge set of the graph, and we call a subset of edges
independent if it is cycle-free. Matroids that can be defined this way by a
graph are called graphic matroids or cycle matroids.

Another important example is linear independence of vectors. The elements of
$E$ are vectors from a vector space, and a subset of them is called
independent if the vectors are linearly independent (over a field $F$).
Matroids that can be defined in this way are called linear matroids (or
representable over $F$).

The _simplicial matroid_ (or simplicial geometry) $M_{k}(\Delta)$ associated
to a simplicial complex $\Delta$ is a linear matroid defined as follows. It
appears in e.g. [CR70, CL87].

######  Definition 8 (Simplicial matroid).

The $k$-simplicial matroid $M_{k}(\Delta)$ associated to a simplicial complex
$\Delta$ is the linear matroid whose ground set is the set of boundary vectors
$\delta_{k}(S)\in\\{0,1\\}^{d_{k-1}}$ for $S\in F_{k}(\Delta)$.

Motivated by this, we call a subset of $k$-faces independent if the
corresponding boundary vectors are linearly independent (over the field
$\\{0,1\\}$).

A maximal independent set of a matroid $M$ is called a basis. It is well known
that all the bases of a matroid have the same size, equal to the rank
$\mathrm{rk}(M)$ of the matroid. The full $k$-simplicial matroid
$M_{k}(\Delta_{k}^{\mathrm{full}})$ is the $k$-simplicial matroid associated
to the full complex $\Delta_{k}^{\mathrm{full}}=\\{S\subseteq V,|S|\leq
k+1\\}$ that contains all the $k+1$-subsets as $k$-faces, but it does not have
any higher dimensional face.

######  Claim 1 (e.g. [CL87], Proposition 6.1.5).

$\mathrm{rk}(M_{k}(\Delta_{k}^{\mathrm{full}}))=\binom{n-1}{k}$.

For a construction, fix a vertex $u$ of $\Delta_{k}^{\mathrm{full}}$ and take
the set of $k$-faces that contain $u$. It is easy to see that this set of size
$\binom{n-1}{k}$ is a basis of the matroid.

##  3 Betti numbers via independent faces

In this section we connect the number of independent $k$-faces with the total
number of $k$-faces, and connect the Betti number $\beta_{k}$ to the number of
independent $k$\- and $(k+1)$-faces in the complex. While we could find in the
literature variants of some of the claims in this section (see e.g. Remark 1),
the key claims were unknown to us before.

The notion of independence of faces in Definition 8 leads to the following
useful observation. It is a direct consequence of the fact that a set of
$k$-faces has zero boundary if and only if the sum of the corresponding
boundary vectors is the zero vector.

######  Claim 2.

In a $k$-dimensional simplicial complex (i.e., $|F_{k+1}|=0$), a set of
$k$-faces is independent iff no subset of them forms a $k$-dimensional hole.

The independence of holes is defined similarly. A $k$-dimensional hole is a
set of $k$-faces (an element of $C_{k}$), and associated to it is a
characteristic vector over $\\{0,1\\}^{d_{k}}$. We associated the same kind of
(boundary) vectors to $(k+1)$-faces: in this sense a $k$-dimensional hole can
be seen as the boundary of a virtual $(k+1)$-dimensional object. This way, a
set of holes is independent if the corresponding vectors are linearly
independent (over field $\\{0,1\\}$). An analogue of 2 tells us that a set of
$k$-dimensional holes is independent iff no subset of them (as virtual
$(k+1)$-faces) forms a $(k+1)$-dimensional hole.

Let us denote the rank $\mathrm{rk}(M_{k}(\Delta))$ of the $k$-simplicial
matroid (i.e. the size of a maximal independent set of $k$-faces in $\Delta$)
by $r_{k}(\Delta)$. We are going to need a lower bound on this value in terms
of the total number of $k$-faces $d_{k}(\Delta)$. For the sake of
completeness, we also include an upper bound in the statement.

######  Lemma 3.

For any $0\leq k<n$ and any simplicial complex $\Delta$

$\frac{k+1}{n}d_{k}(\Delta)\leq
r_{k}(\Delta)\leq\min\left\\{d_{k}(\Delta),\binom{n-1}{k}\right\\}.$

###### Proof.

Trivially, $r_{k}(\Delta)\leq d_{k}(\Delta)$. Moreover, the set of $k$-faces
$F_{k}(\Delta)$ of any complex $\Delta$ can be obtained from that of the full
complex $F_{k}(\Delta^{\mathrm{full}}_{k})$ by removing faces, and this can
only decrease the rank. Combined with 1 we hence get
$r_{k}(\Delta)\leq\binom{n-1}{k}$.

Now let us prove the main part of the claim, which is the lower bound. We use
a similar argument to the one below 1. Let $u$ be a vertex in $\Delta$ that is
included in a maximum number of $k$-faces (i.e., the vertex with the highest
“$k$-face-degree”). These $k$-faces that contain $u$ are independent because
each contains a $(k-1)$-face that the others do not (the one without $u$), and
this is a non-zero element in their boundary vector. As there are $d_{k}$ many
$k$-faces in $\Delta$, each incident to $k+1$ vertices, the average “$k$-face-
degree” of a vertex is $(k+1)d_{k}/n$. Thus the independent set of $k$-faces
defined by $u$ has at least this many $k$-faces, and so
$r_{k}\geq(k+1)d_{k}/n$. ∎

The next lemma shows a nice connection between the rank, the number of faces
and the Betti number. For $k=0$ the formula gives the well-known graph formula
$c=n-t$, where $t$ is the number of edges in a spanning forest, $n$ is the
number of vertices, and $c$ is the number of connected components. When $k=1$
and the underlying graph is connected and planar, it gives the Euler formula
$n+f=e+2$ (with $n$ the number of vertices, $f$ the number of faces surrounded
by edges and $e$ the number of edges) because $\beta_{1}=f-1$, $d_{1}=e$,
$r_{1}=n-1$ and $r_{2}=0$.

######  Lemma 4.

For any simplicial complex, $\beta_{k}=d_{k}-r_{k}-r_{k+1}$.

###### Proof.

The proof goes by induction. Let $\Delta$ denote the simplicial complex being
considered and let us take a basis of the $k$-simplicial matroid over
$\Delta$. For the base case, we consider the subcomplex where this is the set
of all $k$-faces and all the higher dimensional faces are removed, in which
case $r_{k}=d_{k}$ and $\beta_{k}=r_{k+1}=0$ and so the formula holds. In the
inductive step we will put back all of the removed faces. We start by adding
the rest of the $k$-faces one by one, and we argue that each added face
creates exactly one new independent hole.

First, note that adding a dependent $k$-face $S$ to the complex creates at
least one hole (otherwise we could have added it to the basis by 2). Moreover,
the hole is independent of the previous ones because it contains the face $S$,
which no other hole contains so far.

Then, we prove that adding a $k$-face creates at most one hole. By
contradiction, assume that there is a $k$-face $S$ such that when added to the
set, more than one new independent holes are created. We consider two of them,
$\\{S,R_{1},\dots,R_{p}\\}$ and $\\{S,T_{1},\dots,T_{q}\\}$, which we call the
“$R$-hole” and the “$T$-hole”. Necessarily they have zero boundary (we denote
the boundary vectors the same way as the $k$-faces):

$\displaystyle S+R_{1}+\dots+R_{p}$ $\displaystyle=0$ $\displaystyle
S+T_{1}+\dots+T_{q}$ $\displaystyle=0.$

Adding the equations shows that $\\{R_{1},\dots,R_{p},T_{1},\dots,T_{q}\\}$
must also be a hole, call it the “$RT$-hole”. It does not contain $S$, and so
must have been present before adding $S$. However, by construction, the $R$-,
$T$\- and $RT$-holes are not independent, and so we get a contradiction.

Let $\Delta_{k}$ denote the complex we have now: it contains exactly the faces
of $\Delta$ up to dimension $k$, and no faces of higher dimension. So far we
proved that $r_{k}=d_{k}-\beta_{k}(\Delta_{k})$. Let us consider the set of
“potential $k$-holes” in $\Delta_{k}$, i.e. sets $H$ of cardinality $k+2$
where all the $(k+1)$-subsets of $H$ are in $\Delta_{k}$. These are those
holes of $\Delta_{k}$ that may be filled by $(k+1)$-faces in $\Delta$.

Now we continue the induction by adding to $\Delta_{k}$ the $(k+1)$-faces of
$\Delta$ one by one (and in the end the higher dimensional faces as well) to
get back $\Delta$. Each $(k+1)$-face fills a potential hole, and it is
independent of the previously added ones if and only if the hole being filled
is independent of the previously filled ones (as they are the same subset).
Thus, every time $\Delta$ gains an independent $(k+1)$-face it loses an
independent $k$-hole. This finishes the proof, as adding faces of dimension
larger than $k+1$ does not change any parameter in the claim. ∎

In the special case where $k=0$ and the graph defined by the vertices and
edges of $\Delta$ is connected, we have $\beta_{0}=0$, $d_{0}=n$ and
$r_{k+1}=n-1$ (a spanning tree of the graph is a maximal independent edge
set). Thus, $r_{0}$ has to be defined as 0, which makes sense if we think
about $r_{k}$ as $r_{k}=\dim(\operatorname{\mathrm{im}}(\delta_{k}))$.

######  Remark 1.

Let $T_{\ell}=\\{S\subseteq V,\,|S|=\ell+1\\}$ and $A\subseteq T_{k}$. In
previous works [CR70, Cor78] only complexes of the form
$\Delta^{\mathrm{full}}_{k-1}\cup A$ are analysed in detail. This family of
complexes is not enough to express the $k$-th Betti number of an arbitrary
simplicial complex. For example, for this restricted class of complexes
Cordovil [Cor78, Proposition 1.2] showed that $r_{k}=d_{k}-\beta_{k}$, which
is only a special case of Lemma 4 (with $r_{k+1}=0$).

An easy consequence of Lemma 4 is the following statement.

######  Claim 3.

For any simplicial complex $\Delta$ and $k\geq 1$,
$\beta_{k}(\Delta)\leq\binom{n-1}{k+1}$.

###### Proof.

In $\Delta^{\mathrm{full}}_{k}$ we have
$\beta_{k}=d_{k}-r_{k}-0=\binom{n}{k+1}-\binom{n-1}{k}=\binom{n-1}{k+1}$, and
removing $k$-faces or adding $(k+1)$-faces cannot increase this value. ∎

##  4 Testing large Betti numbers

In this section we turn to our main result, proving that we can test whether a
Betti number is large. We now state our main theorem again.

######  Theorem 2 (formal version of Theorem 1).

Consider a clique complex $\Delta$. For any constant $k$ and $\varepsilon>0$,
there exists $\delta(\varepsilon,k)>0$ such that the property of having $k$-th
Betti number $\beta_{k}(\Delta)\geq(1-\delta)d_{k}$ is testable for any
$\delta\leq\delta(\varepsilon,k)$ (with distance parameter $\varepsilon$).

Even though our results in Section 3 hold for general simplicial complexes,
the main theorem is restricted to clique complexes. The reason for this is
that we wish to phrase our results in the well-established setting of graph
property testing. By constraining ourselves to clique complexes, having a
large Betti number becomes a graph property (of the underlying graph) rather
than a property of an abstract simplicial complex. Also, this way we can use
some previous results from graph property testing, like the tolerant
testability of subgraph freeness (Lemma 2).

###  4.1 Warm-up: testing many components

The $0$-th Betti number $\beta_{0}$ of a clique complex $\Delta$ equals the
number of connected components of the underlying graph $G$. As an informal
warm-up and a blueprint for the general case, we show how to test whether
$\beta_{0}\geq(1-\delta)n$. The argument involves two reductions.

First, we argue that having a large 0-th Betti number is equivalent to having
few independent edges. From Lemma 4 we get that $\beta_{0}=n-r_{1}-r_{0}$
where $r_{0}=0$. Thus, $\beta_{0}\geq(1-\delta)n$ is equivalent to
$r_{1}\leq\delta n$, and so testing large $\beta_{0}$ reduces to testing
whether $G$ has a small number of independent edges.

Now comes the second reduction, in which we argue that testing whether $G$ has
few independent edges can be reduced to _tolerantly_ testing edge-freeness.
For this, note that if $G$ has $r_{1}\leq\delta n$ independent edges then the
total number of edges $|E|\leq\binom{\delta
n+1}{2}<\delta^{2}n^{2}/2+O(n)$,444From Lemma 3 we would get $|E|\leq
r_{1}n/2\leq\delta n^{2}/2$. We get the better bound by noticing that if there
are $\delta n$ independent edges, then we have a maximum number of edges if
all the independent edges are in the same connected component and this
component is a $K_{\delta n+1}$. and so $G$ must be $1.1\delta^{2}/2$-close to
being edge-free. On the other hand, if $G$ is $\varepsilon$-far from having
$r_{1}\leq\delta n$, then $G$ must also be $\varepsilon$-far from having
$r_{1}=0$, i.e from being edge-free. So we reduced the problem of testing
$\beta_{0}\geq(1-\delta)n$ to that of tolerantly testing edge-freeness (with
parameters $\varepsilon_{1}=1.1\delta^{2}/2$ and
$\varepsilon_{2}=\varepsilon$). It remains to note that edge-freeness is
tolerantly testable by Lemma 2.

###  4.2 General case

We now turn to proving our general result (Theorem 2), that having a Betti
number $\beta_{k}\geq(1-\delta)d_{k}$ is testable for constant $k$. Following
the blueprint from the previous section, we first reduce the problem to
testing whether there are few independent $(k+1)$-faces, and then reduce
testing few independent $(k+1)$-faces to tolerantly testing $(k+2)$-clique
freeness.

We consider a clique complex $\Delta$ with underlying graph $G$. From Lemma 4
we get that

$d_{k}-r_{k+1}\geq\beta_{k}=d_{k}-r_{k+1}-r_{k},$ (1)

which directly implies the following lemma.

######  Lemma 5 (Large Betti number $\preceq$ few independent cliques).

In a clique complex $\Delta$ with underlying graph $G$, if
$\beta_{k}\geq(1-\delta)d_{k}$ then $r_{k+1}\leq\delta d_{k}$. If $G$ is
$\varepsilon$-far from having $\beta_{k}\geq(1-\delta)d_{k}$ in $\Delta$ then
it is also $\varepsilon$-far from having $r_{k+1}=0$, i.e., $G$ is
$\varepsilon$-far from $K_{k+2}$-freeness.555For this last point, note that by
Lemma 4 we have that $r_{k+1}\leq\delta d_{k}-r_{k}$ is equivalent to
$\beta_{k}\geq(1-\delta)d_{k}$. Hence, a graph that is $\varepsilon$-far from
$\beta_{k}\geq(1-\delta)d_{k}$ must also be $\varepsilon$-far from
$r_{k+1}\leq\delta d_{k}-r_{k}$ (and so certainly from being $K_{k+2}$-free).

For our second reduction, we use Lemma 3, which tells us that if
$r_{k+1}\leq\delta d_{k}$ then

$d_{k+1}\leq\frac{\delta}{k+2}nd_{k}\leq\frac{\delta}{k+2}n\binom{n}{k+1}\leq\frac{\delta}{(k+2)!}n^{k+2}.$

Combined with Lemma 5 we get that $\beta_{k}\geq(1-\delta)d_{k}$ implies
$d_{k+1}\leq\frac{\delta}{(k+2)!}n^{k+2}$. We see that a large Betti number
implies a small number of $K_{k+2}$’s in the graph, while being far from
having a large Betti number implies being far from $K_{k+2}$-freeness (by
Lemma 5).

In fact, by the graph removal lemma (Lemma 1), a small number of $K_{k+2}$’s
implies that the graph is close to being $K_{k+2}$-free. More specifically,
for any $\varepsilon^{\prime}>0$ there exists
$\delta=\delta(k,\varepsilon^{\prime})>0$ such that if $G$ has at most
$\frac{\delta}{(k+2)!}n^{k+2}$ many $K_{k+2}$’s then $G$ is
$\varepsilon^{\prime}$-close to being $K_{k+2}$-free. By picking (say)
$\varepsilon^{\prime}=\varepsilon/2$, it follows that we can test whether
$\beta_{k}\geq(1-\delta)d_{k}$ by tolerantly testing whether $G$ is
$\varepsilon/2$-close or $\varepsilon$-far from $K_{k+2}$-freeness. By Lemma 2
we know that $K_{k+2}$-freeness is indeed tolerantly testable, and this proves
our main Theorem 2.

To finish, we comment on the scaling of $\delta(k,\varepsilon)$. The current
best upper bound in the graph removal lemma requires
$\delta(k,\varepsilon)\leq 1/\mathrm{tower}(5(k+2)^{4}\log(1/\varepsilon))$
[Fox11], where $\mathrm{tower}(i)$ is a tower of twos of height $i$ (e.g.,
$\mathrm{tower}(3)=2^{2^{2}}$). For the case of $k=0$ we could avoid this:
recall from Section 4.1 that $r_{1}\leq\delta n$ implies that $G$ is
$\delta^{2}/2$-close to being edge-free. Similarly, for $k=1$ we can get a
better bound: $r_{2}\leq\delta n^{2}$ implies that $G$ is $3\delta$-close to
being triangle-free. Indeed, if we remove all the edges of a maximal
independent triangle set (at most $3\delta n^{2}$ edges), then any remaining
triangle in the graph would contradict the maximality of the chosen set. We
leave the extension of similar arguments to higher $k$ for future work. In
conclusion, we get a tester that distinguishes $\beta_{k}\geq(1-\delta)d_{k}$
from being $\varepsilon$-far under the constraints

$\delta<\sqrt{2\varepsilon}\;\;(k=0),\qquad\delta<\varepsilon/3\;\;(k=1),\qquad\delta<1/\mathrm{tower}(5(k+2)^{4}\log(1/\varepsilon))\;\;(k>1).$

##  5 Acknowledgements

The authors were partially supported by French projects EPIQ
(ANR-22-PETQ-0007), QUDATA (ANR-18-CE47-0010) and QUOPS (ANR22-CE47-0003-01),
and EU project QOPT (QuantERA ERA-NET Cofund 2022-25).

## References

  * [ADL+94] Noga Alon, Richard A Duke, Hanno Lefmann, Vojtech Rodl, and Raphael Yuster.  The algorithmic aspects of the regularity lemma.  Journal of Algorithms, 16(1):80–109, 1994.
  * [AGSS23] Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó.  A (simple) classical algorithm for estimating betti numbers.  Quantum, 7:1202, 2023.
  * [AS05] Noga Alon and Asaf Shapira.  Every monotone graph property is testable.  In Proceedings of the thirty-seventh annual ACM Symposium on Theory of Computing, pages 128–137, 2005.
  * [AS08] Noga Alon and Asaf Shapira.  A characterization of the (natural) graph properties testable with one-sided error.  SIAM Journal on Computing, 37(6):1703–1727, 2008.
  * [BSG+22] Dominic W Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, and Ryan Babbush.  Quantifying quantum advantage in topological data analysis.  arXiv:2209.13581, 2022.
  * [CK22] Marcos Crichigno and Tamara Kohler.  Clique homology is QMA1-hard.  arXiv:2209.11793, 2022.
  * [CL87] Raul Cordovil and Bernt Lindström.  Simplicial matroids.  In Combinatorial Geometries. Cambridge University Press, 1987.
  * [Cor78] Raul Cordovil.  Sur les géometries simpliciales.  Comptes Rendus hebdomadaires des séances de l’Académie des Sciences, 286(25):1219–1222, 1978.
  * [CR70] Henry H. Crapo and Gian-Carlo Rota.  On the Foundations of Combinatorial Theory II. Combinatorial Geometries.  Studies in Applied Mathematics, 49(2):109–133, 1970.
  * [Ele10] Gábor Elek.  Betti numbers are testable.  Fete of combinatorics and computer science, pages 139–149, 2010\.
  * [FN07] Eldar Fischer and Ilan Newman.  Testing versus estimation of graph properties.  SIAM Journal on Computing, 37(2):482–501, 05 2007.
  * [Fox11] Jacob Fox.  A new proof of the graph removal lemma.  Annals of Mathematics, pages 561–579, 2011.
  * [Für95] Zoltán Füredi.  Extremal hypergraphs and combinatorial geometry.  In Proceedings of the International Congress of Mathematicians, pages 1343–1352. Birkhäuser Basel, 1995.
  * [GCD22] Casper Gyurik, Chris Cade, and Vedran Dunjko.  Towards quantum advantage via topological data analysis.  Quantum, 6:855, 2022.
  * [GGR98] Oded Goldreich, Shari Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  Journal of the ACM, 45(4):653–750, jul 1998.
  * [Gol10] Oded Goldreich.  Introduction to testing graph properties.  Property testing: current research and surveys, pages 105–141, 2010\.
  * [Hay22] Ryu Hayakawa.  Quantum algorithm for persistent Betti numbers and topological data analysis.  Quantum, 6:873, 2022.
  * [LGZ16] Seth Lloyd, Silvano Garnerone, and Paolo Zanardi.  Quantum algorithms for topological and geometric analysis of data.  Nature communications, 7(1):1–7, 2016.
  * [Sze78] Endre Szemerédi.  Regular partitions of graphs.  In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Colloq. Internat. CNRS, pages 399–401. CNRS, Paris, 1978.