# Notes on altermagnetism and superconductivity

Igor I. Mazin  Department of Physics & Astronomy, George Mason University,
Fairfax, VA 22030, USA  Quantum Science and Engineering Center, George Mason
University, Fairfax, VA 22030, USA.

Altermagnetism is a recently discovered new type of collinear magnets, which
share some characteristic features with ferromagnets (lack of the
nonrelativistic Kramers degeneracy at a general point in the Brillouin zone,
finite anomalous Hall effect, finite magnetooptical effect) and other with
antiferromagnets (net magnetization zero by symmetry)[1]. While numerous
properties of altermagnets have been explored, largely from the point of view
of spintronics, interplay between superconductivity and altermagnetism,
another aspect in which ferro- and antiferromagnets are principally different,
has not been addressed so far. Not surprisingly, there altermagnets can can
manifest properties typical for ferromagnets in one contexts, and those
typical for antiferromagnets in another.

There are two issues that are typically considered in terms of interaction
between magnetism and superconductivity: (1) what kind of superconducting
state may be consistent with a given magnetic order and (2) what kind of
pairing can be generated by proximity to a magnetic order (in other words, if
we can gradually suppress the long range magnetic order by an external
stimulus, such as pressure, what supperconducting symmetry may emerge on the
either side of the quantum crutical point?).

## Superconductivity and ordered altermagnetism

It is well known that the standard antiferromagnetism can support singlet
superconductivity (as for instance in Fe-based superconductors) as long as the
coherence length is much larger than the period of antiferromagnetic order. On
the other hand, a split ferromagnet with spin-split bands ($i.e.$, the
eigenvalues
$\epsilon_{\mathbf{k\uparrow}}\neq\epsilon_{-\mathbf{k\downarrow}}$) can only
support Cooper pairs with the spinor order parameter
$\Delta_{\uparrow\uparrow},$ which is triplet. A standard representation[2] of
the spinor triplet order parameter in terms of a spacial vector $\mathbf{d}$
describe this spinor as

$\Delta_{\alpha\beta}=\begin{pmatrix}-d_{x}+id_{y}&d_{z}\\\
d_{z}&d_{x}+id_{y}\end{pmatrix}$ (1)

Obviously, since only the $\alpha=\beta=\uparrow$ element is nonzero for a
given $\mathbf{k}$, $d_{z}=0,$ and $d_{x}=-id_{y}.$

AM is rather close to FM in this sense, but it has an additional symmetry:
there is an element of the point group that does not map the Fermi surface for
a given spin upon itself, but does map it upon the Fermi surface for the
opposite spin[1, 6]. Let us now, for simplicity, consider a tetragonal FM
material. Then the only triplet state consistent with this requirement is the
nonunitary state d$=F_{1}(k)k_{z}(\hat{x}+i\hat{y}),$ where $F$ has the full
tetragonal symmetry, so that of $\Delta_{\alpha\beta}$ only
$\Delta_{\uparrow\uparrow}\neq 0$. If we now consider the other Fermi surface,
for the opposite spin, the order parameter there will be
$\mathbf{d=}F_{2}(k)k_{z}(\hat{x}-i\hat{y}),$ with only
$\Delta_{\downarrow\downarrow}\neq 0.$ These two order parameters have
different symmetries, and are not degenerate, so the critical temperature
$T_{c}$ will be different. The symmetry consideration dictate that, without
spin-orbit interaction, there will be no coupling between the two order
parameters. In a typical experiment probing the average order parameter such a
system at low temperature will behave as mixed state
$\mathbf{d=}\frac{k_{z}}{2}\mathbf{[}F_{1}(k)+F_{2}(k)]\hat{x}+i\frac{k_{z}}{2}\mathbf{[}F_{1}(k)-F_{2}(k)]\hat{y}.$
This state is nonunitary as long as $F_{1}\neq F_{2},$ and nematic (breaks the
$C_{4}$ symmetry).

AM, despite the absence of the net magnetization, behaves very much like a
ferromagnet in the sense that any Cooper paper can be either
$\Delta_{\uparrow\uparrow}$ or $\Delta_{\downarrow\downarrow}.$
Correspondingly, the order parameters will be
$F_{1}(k)k_{z}(\hat{x}+i\hat{y})$ and $F_{2}(k)k_{z}(\hat{x}-i\hat{y}).$
However, in this case $F_{1}=F_{2}$ by symmetry (the same symmetry that
transfoms one spin sublattice into the other), so the average order parameter
will be just $\mathbf{d=}k_{z}F(k)\hat{x}.$ This order parameter is strictly
unitary (correspondingly, the condensate is not spin-polarized, just as the
normal state isn’t), and nematic. Of course, the partner state
$\mathbf{d=}k_{z}F(k)\hat{y}$ will be degenerate with this one. In this sense,
the AM as regards superconductivity again has some features similar to
ferromagnets, some similar to antiferromagnets, and some unique. An
interesting analogy may be drawn with the Ising superconductivity, appearing
when the Kramers degeneracy is lifted not by the exchange field, but by the
spin-orbit coupling. In that case the two spin-split Fermi surfaces carry
order parameters that are strictly $S+T$ and $S-T,$ where $S(T)$ stands for
singlet(triplet)[7]. Despite that, in most experiments, namely those that
probe the average order parameters, they behave approximately as singlet
(approximately because no symmetry requires the two order parameters to be
exactly the same). In case of AM the difference is that the average order
parameter becomes unitary exactly, by symmetry (of course, remaining triplet)

## Superconductivity and altermagnetic fluctuations

A related question is what superconducting symmetry can be generated by the
AM-type spin fluctuations. Before discussing that let us compare FM and AF
fluctuations a bit more carefully than how it is usually done.

In case of ferromagnetic fluctuations, the spin fluctuation spectrum is peaked
at $\mathbf{q}=0.$ Given that spin fluctuations are repulsive in the singlet
channel (the partners in a Cooper pair interact to a spin fluctuations with
opposite signs), and that by continuity
$\Delta(\mathbf{k)\approx}\Delta(\mathbf{k+q),}$ as long as $\mathbf{q}$ is
small, such fluctuations will always be pair-breaking. Traditional, Néel type
AF order at a finite vector $\mathbf{q}$ (if $\mathbf{q}$ lies at the zone
boundary, this order will correspond to doubling of the unit cell). In that
case spin fluctuations can be pairing as long as
$\Delta(\mathbf{k)\cdot}\Delta(\mathbf{k+q)}<0.$ Popular theories ascribing
the $d$-wave superconductivity in cuprates ($\mathbf{q}_{2D}=\\{\pi,\pi\\})$
and the $s_{\pm}$ superconductivity in Fe pnictides
($\mathbf{q}_{2D}=\\{\pi,0\\})$ to spin fluctuations utilize this property.
While such fluctuations can also generate a $p$-wave pairing, especially when
combined with an anisotropic electron-phonon coupling[3], in practice it is
very difficult[4].

In such discussions it is routinely assumed that AF fluctuations always
correspond to a finite $\mathbf{q.}$ However, several hundreds of known
antiferromagnets have magnetic order corresponding to $\mathbf{q=0.}$ This can
happen, of course, if the magnetic species occupies a Wyckoff position with a
multiplicity larger that one. For instance, the very popular now family of
Kagome superconductors, $A$V3Sb5 ($A$ is an alkaline metal) is believed to
host spin-fluctuations at $\mathbf{q\approx 0}$ and the intra-triangular
correlations of 120${{}^{\circ}}.$ Of course, magnetic order and spin
fluctuations $\mathbf{q\approx 0}$ and collinear spins are also perfectly
possible, and altermagnetic (and some conventional antiferromagnets) belong to
this class.

In order to understand the physics of $\mathbf{q\approx 0}$ spin fluctuations
in the context of superconductivity, let us consider a hypothetical 2D lattice
depicted in Fig. 1(left). Here M is a metal ion and L is a ligand. This is a
tetragonal structure with the symmetry group I4/mmm. Lets us assume that this
structure generates a Fermi surface centered around the X(Y) points, as shown
in Fig. 2 (left), and spin-fluctuations corresponding to
$\mathbf{q=}\\{\pi,\pi\\}.$This model was introduced by Agterberg $et$
$al$[8], and it leads a $d$-wave superconductivity of the type
$k_{x}^{2}-k_{y}^{2}.$

Figure 1: (left) An example of a 2D P4/mmm structure. The grey balls are
metallic (M), and potentially magnetic ions, and the red ones are ligands (L).
(right) Same for a P4/mbm structure, which can carry an altermagnetic state
(shown by arrows)

Let us now introduce a small distortion, rotations of the $ML_{2}$ squares,
shown in Fig. 1(right). The symmetry group is now P4/mbm, it is also
tetragonal, but has now two metal ions per cell. This will lead to folding
down of the original Brillouin zone (Fig. 2), so that now there are to Fermi
contours around each M point; if the original Fermi contours were close to
circular, the downfolded one will be nearly degenerate.

Figure 2: (left) A possible 2D Brillouin zone consistent with the crystal
symmetry shown in Fig. 1(left). (right) The same, after downfolding
corresponding to the double unit cell shown in Fig. 1(right). The downfolded
zone is shown with the dashed lines. Colors reflect the signs of a possible
$d$-wave (in the unfolded zone) order parameter. The arrows give examples of
antiferromagnetic spin fluctuations with $\mathbf{q}\approx{\pi,\pi}$
generating a $d$-wave pairing. Nothe that the case on the right these are
fromally altermagnetic fluctuations.

Altermagnetic spin fluctuations will have $\mathbf{q\approx 0},$ however, this
does not mean that, as in for ferromagnetic fluctuations, such fluctuations
can only generate triplet pairing. In fact, since in this particular example
the AM order only slightly deviates from the AF order, the generated pairing
state must be close to the downfolded $d$-state of Ref. [8]. In principle, the
two crossing Fermi lines will hybridize, and the order parameter form nodal
lines, as discussed in Ref. [9]. However, this is a relatively unimporant
effect.

From the formal point of view, the issue is that $\mathbf{q\approx 0}$ the
spin susceptibility may have importand internal structure, and has to be
written as $\chi(\mathbf{q,r}_{1},\mathbf{r}_{2}),$ where $\mathbf{r}$ is
defined inside the first unit cell, or as a matrix in reciprocal vectors,
$\chi(\mathbf{q+G,q+G}^{\prime}).$ The corresponding vertex will be determined
by the variation of the (nonmagnetic) one-electron Green function with respect
to a fluctuation generating opposite magnetic moments on the two sublattices.
A more detailed theory than that usually used for ferro- or antiferromagnetic
spin fluctuations needs to be developed, and it is not unreasonable to assume
that both triplet and singlet pairing can be iduced by AM spin fluctuations,
depending on the details.

Lastly, one can make another interesting observation: so far, two very
different classes of superconductors offer protection from thermodynamic pair
breaking (Pauli limiting) for some directions of magnetic fields. The first
one are triplet superconductors without net magnetization (such as 3He or the
initial (now debunked) model for Sr2RuO${}_{4})$; there the spin
susceptibility in the superconducting state is the same as in the normal
state, $\chi_{sc}=\chi_{n}$, due to triplet pairs having the same ability to
screen the field (in some directions) as the individual electrons. Unitary
triplet superconductivity, often discussed in connection with some
ferromagnetic U compounds, is also protected, and again $\chi_{sc}=\chi_{n},$
but there the underlying mechanism is different: If there is and easy-axis
magnetocrystalline anisotropy in the normal state, then screening of a small
external field is afforder not by increasing the net number of electrons in
one spin channel at the expense of the other, but by canting spins of
electrons removed from the Fermi level. Indeed, if an external field $H$ is
applied perpendicular to this axis, the Fermi surface does not change in the
linear in $H$ order, but a linear in $H$ magnetization does appear, on the
order of $H\Delta\Omega/\left\langle\delta V_{xc}\right\rangle,$ where
$\Delta\Omega$ is the volume difference between the two spin-split Fermi
surfaces and $\left\langle\delta V_{xc}\right\rangle$ is the properly averaged
exchange splitting. Obviously, the ratio $\Delta\Omega/\left\langle\delta
V_{xc}\right\rangle$ is a number on the order of the density of states, so
this provides a contribution to susceptibilty on the order of the Pauli
susceptibility, and is not affected by opening a superconducting gap
$\Delta\ll\left\langle\delta V_{xc}\right\rangle.$ Note that similar
protections is operative in Ising superconductors, where the role of $\delta
V_{xc}$ is played by the spin-orbit coupling[7]. In the spirit of the key
feature of AM, namely sharing features of both FM and AFM, they also have a
Pauli protection, but which in this case is similar to that in ferromagnets,
so it does not require accounting for relativistic effects in the band
structure, but requires a magnetic anisotropy.

In the above discussion, we have addressed issues related to possible
coexistance of AM and superconductivity, as well as superconductivity possibly
induced by AM spin fluctuation. A further step in investigating the interplay
between magnetism and superconductivity would involve possible effects at the
interface between a conventional superconductor and an altermagnet.

One of the most interesting effects in this environment is spin-polarized
Andreev reflection. Andreev reflection at a boundary between a conventional
superconductor and a ferromagnet is well understood[10] and is often use to
measure the transport spin polarization of ferromagnets. In a generic
ferromagnet, as opposed to a traditional antiferromagnet, the number of
conductivity channels for two spins are not the same (in other words, the area
of the Fermi surface projection onto the interface is spin-dependent. Since an
Andreev process consist of a spin-up electron with a momentum $\mathbf{k}$ and
a spin-down one with a momentum $-\mathbf{k,}$ some electrons will never find
a partner and therefore the conventional Andreev conductivity, which is twice
the normal conductivity, will be suppressed. So defined spin polarization
depends on the orientation of the interface. While for a ferromagnet is can
only be zero by accident, in an AM, for particular interface orientations the
number of conductivity channels is the same for both spins, therefore one
expects no suppression, just as in an AF, but in some other, and in fact in
general directions the areas of the two projections will be different, and a
finite suppression will be measured. Again, an AM sometimes behaves as an AF,
and sometimes as a FM.

Figure 3: (left) A possible 2D Brillouin zone consistent with the crystal
symmetry shown in Fig. 1(left). Specifically, a cut-off of a specific Fermi
surface pocket in the hypothetical altermagnetic FeSb2[6]. Different colors
denote different spins. (right) Projection of this pocket onto the (110)
inteface.

This is illustrated in Fig. 3(left), where a single pocket of the Fermi
surface of the hypothetical AM FeSb2[6] at a particular Fermi energy is cut
off to show the symmetry. Evidently, for a {100), or (010), or (001) interface
every $\mathbf{k}_{||}$ has a partner with $-$ $\mathbf{k}_{||}$ and the
opposite spin, for the (110) interface, for instance, this is not the case, as
is quite obvious from Fig.3(right), where the projections of the two Fermi
surfaces are shown.

In this note we have analyized various aspects of interplay between the novel
magnetic phenomenon, altermagnetism, and superconductivity. This analysis
should be helpful in designing new experiments to further study this unusual
state.

Helpful discussions with Maxim Khodas and financial support from DOE under the
grant DE-SC0021089 are acknowledged.

## References

  * [1] Libor Ŝmejkal, Jairo Sinova, Tomas Jungwirth, Altermagnetism: spin-momentum locked phase protected by non-relativistic symmetries, arXiv:2105.05820 (20121)
  * [2] Manfred Sigrist and Kazuo Ueda, Phenomenological theory of unconventional superconductivity, Rev. Mod. Phys. 63, 239 (1991)
  * [3] I. Schnell, I. I. Mazin, A.Y. Liu, Unconventional superconducting pairing symmetry induced by phonons, Phys. Rev. B 74, 184503 (2006)
  * [4] P. Steffens, Y. Sidis, J. Kulda, Z. Q. Mao, Y. Maeno, I.I. Mazin, and M. Braden, Spin fluctuations in Sr2RuO4 from polarized neutron scattering: implications for superconductivity. Phys. Rev. Lett. 122, 047004 (2019).
  * [5] Brenden R. Ortiz, Lídia C. Gomes, Jennifer R. Morey, Michal Winiarski, Mitchell Bordelon, John S. Mangum, Iain W. H. Oswald, Jose A. Rodriguez-Rivera, James R. Neilson, Stephen D. Wilson, Elif Ertekin, Tyrel M. McQueen, and Eric S. Toberer, New kagome prototype materials: discovery of KV3Sb5, RbV3Sb5, and CsV3Sb${}_{5},$ Phys. Rev. Materials 3, 094407 (2019)
  * [6] Igor I. Mazin, Klaus Koepernik, Michelle D. Johannes, Rafael González-Hernández, and Libor Šmejkal, Prediction of unconventional magnetism in doped FeSb${}_{2},$ PNAS 118, e2108924118 (2021)
  * [7] D. Wickramaratne, S. Khmelevskyi, D. F. Agterberg, and I. I. Mazin, Ising superconductivity and magnetism in NbSe2, Phys. Rev. X 10, 041003 (2020)
  * [8] D. F. Agterberg, Victor Barzykin, and Lev P. Gor’kov, Conventional mechanisms for exotic superconductivity.Phys. Rev. B 60, 14868 (1999)
  * [9] I.I. Mazin, Symmetry analysis of possible superconducting states in KxFe2Se2 superconductors, Phys. Rev. B 84, 024529 (2011)
  * [10] I.I. Mazin, A.A. Golubov, and B. Nadgorny, Probing Spin Polarization with Andreev Reflection: A Theoretical Basis. J. Appl. Phys., 89, 7576 (2001); G.T. Woods, R, J. Soulen Jr., I. I. Mazin, B. Nadgorny, M. S. Osofsky, J. Sanders, H. Srikanth, W. F. Egelhoff and R. Datla, Analysis of Point-contact Andreev Reflection Spectra in Spin Polarization Measurements. Phys. Rev. B 70, 054416 (2004).


Vol.0 (20xx) No.0, 000–000

11institutetext: Key lab of Space Astronomy and Technology, National
Astronomical Observatories, Beijing, 100101, China<EMAIL_ADDRESS>22institutetext: School of Astronomy and Space Science, University of Chinese
Academy of Sciences, Beijing 100049, China;
Received 20xx month day; accepted 20xx month day

# The Quasar Candidates Catalogs of DESI Legacy Imaging Survey Data Release 9

Zizhao He 1122 Nan Li 11

###### Abstract

Quasars can be used to measure baryon acoustic oscillations at high redshift,
which are considered as direct tracers of the most distant large-scale
structures in the Universe. It is fundamental to select quasars from
observations before implementing the above research. This work focuses on
creating a catalog of quasar candidates based on photometric data to provide
primary priors for further object classification with spectroscopic data in
the future, such as The Dark Energy Spectroscopic Instrument (DESI) Survey. We
adopt a machine learning algorithm (Random Forest, RF) for quasar
identification. The training set includes $651,073$ positives and $1,227,172$
negatives, in which the photometric information are from DESI Legacy Imaging
Surveys (DESI-LIS) & Wide-field Infrared Survey Explore (WISE), and the labels
are from a database of spectroscopically confirmed quasars based on Sloan
Digital Sky Survey (SDSS) and the Set of Identifications & Measurements and
Bibliography for Astronomical Data (SIMBAD). The trained RF model is applied
to point-like sources in DESI-LIS Data Release 9. To quantify the classifier’s
performance, we also inject a testing set into the to-be-applied data.
Eventually, we obtained $1,953,932$ Grade-A quasar candidates and $22,486,884$
Grade-B quasar candidates out of $425,540,269$ sources ($\sim 5.7\%$). The
catalog covers $\sim 99\%$ of quasars in the to-be-applied data by evaluating
the completeness of the classification on the testing set. The statistical
properties of the candidates agree with that given by the method of color-cut
selection. Our catalog can intensely decrease the workload for confirming
quasars with the upcoming DESI data by eliminating enormous non-quasars but
remaining high completeness. All data in this paper is publicly available
online.

###### keywords:

quasars: general — catalogs — methods: statistical

##  1 Introduction

The discovery of quasars, also known as quasi-stellar objects (QSOs), is one
of the four significant findings that have been made in astronomy in the 60s
of last century (Schmidt 1963; Kellermann 2014). QSOs are extremely luminous
active galactic nuclei (Osterbrock 1989; Urry & Padovani 1995; Dunlop et al.
2003; Croton et al. 2006, AGN) powered by accretion onto supermassive black
holes at the centers of galaxies, and their typical luminosity is ${10}^{42}$
to ${10}^{48}$ erg/s (Shen et al. 2020) at the redshift from 0.1 $\sim 7$
(Antonucci 1993). The emission of QSOs can significantly outshine their host
galaxies, and their emitting regions are too small to resolve even for the
nearest ones. Hence, QSOs are always considered point-like sources, which
mimic faint blue stars in optical bands. However, they are $\sim 2$ magnitudes
brighter in the near-infrared at all redshifts than stars of similar optical
magnitudes and colors, leading to a neat way to discriminate QSOs from stars
(Ross et al. 2012; Myers et al. 2015; Yèche et al. 2020).

The nature of QSOs has been investigated widely and thoroughly in the past
decades by using tons of corresponding observations. Consequently, QSOs are
used to study astrophysical problems in various fields. For instance, the
spectrum of QSOs is a powerful tracer of the formation and evolution of black
holes, the spins of black holes, and the co-evolution of black holes and host
galaxies (Kormendy & Richstone 1995; Silk & Rees 1998; Kaspi et al. 2000; Di
Matteo et al. 2005; Springel et al. 2005; Kormendy & Ho 2013; Chen 2021;
Valentini et al. 2021); taking advantage of microlensing, astronomers study
the feature of accretion disks with the light curves of QSOs (Agol & Krolik
1999; Morgan et al. 2010; Dexter & Agol 2011; Blackburne et al. 2011); the
absorption lines of quasars are unique tracers of the interstellar media along
the line of sight (Scaringi et al. 2009; Hall et al. 2013; Chen et al. 2020;
Mishra et al. 2021; Zabl et al. 2021). Besides, high-redshift quasars are
valuable for understanding the reionization of the Universe and the formation
of galaxies (McLure & Jarvis 2002; Wang et al. 2019; Lupi et al. 2021).
Statistically, the spatial distribution quasars reflects the baryon acoustic
oscillations (BAOs, e.g. Zhao et al. 2019, for an introduction) and in turn
the large-scale structure of the Universe (Dawson et al. 2013; Font-Ribera et
al. 2014; Delubac et al. 2015; Alam et al. 2021; Merz et al. 2021).
Expectedly, with the next-generation large-scale surveys coming, an
unprecedented dataset of QSOs brings an unparalleled opportunity to trigger a
revolution in these fields.

Mining QSOs from enormous datasets is crucial for carrying out the studies
mentioned above, and plenty of progress has been made. The Palomar-Green
Bright Quasar Survey (BQS, Schmidt & Green 1983) discovered more than $100$
quasars. The Large Bright Quasar Survey (LBQS, Hewett et al. 1995) discovered
more than $1,000$s. The 2-degree Field Quasar Redshift Survey (2QZ, Croom et
al. 2004) discovered about $23,000$s. The Large Sky Area Multi-object Fiber
Spectroscopic Telescope (LAMOST, Dong et al. 2018) discovered more than
$20,000$s. At the moment, the largest confirmed quasar catalog is from Sloan
Digital Sky Survey Data Release $16$ (SDSS DR16, Blanton et al. 2017; Lyke et
al. 2020), which contains $750,414$ spectrally confirmed quasars.
Nevertheless, to implement confirming QSOs with spectrums, one must create a
sample of QSO candidates using or even combining various types of data other
than spectroscopy. For instance, photometry data can be used to select QSO
candidates according to the features of QSOs, such as the ultraviolet excess,
infrared excess, and the light variation (Shen et al. 2011); astrometry data
kicks out the objects with high proper motion in the Milky Way (Fu et al.
2021); and, of course, Radio and X-ray data are valuable complements (Bisogni
et al. 2021).

The Dark Energy Spectroscopic Instrument (DESI,111https://www.desi.lbl.gov/
Levi et al. 2013; DESI Collaboration et al. 2016) is a spectral telescope that
located at Kitt Peak National Observatory (KNPO). It is a Mayall telescope
with a four-meter-aperture primary mirror. It will target about $30$ million
pre-selected galaxies across $\sim 14,000$ square degree sky. It is important
for the discovery of more quasar because of its large sky coverage, good image
quality and depth (compared to SDSS, York et al. 2000), and because it can
provide spectrum. However, the QSO candidates is needed for further conforming
the QSOs. Hence, we acquire the QSO candidates from the photometry catalog of
DESI Legacy Imaging Survey (DESI-LIS).

In this work, to create a catalog of QSO candidates for DESI, we adopt a
machine learning (ML) technology named Random Forest (RF) and apply it to
photometry data from DESI-LIS because its efficiency, flexibility, and
accuracy have been intensively proved previously (e.g. Viquar et al. 2018; Bai
et al. 2019; Clarke et al. 2020; Guarneri et al. 2021), in particular, Bai et
al. (2019) demonstrates that RF is the most efficient and reliable one among
several methods in dealing with quasar-star-galaxy classification. The
training and validation sets are built upon the spectra data from SDSS eBOSS
(extended Baryon Oscillation Spectroscopic Survey, Dawson et al. 2016) DR16
and the photometry data from
WISE222https://irsa.ipac.caltech.edu/Missions/wise.html (Wide-field Infrared
Survey Explorer, Wrigh et al. 2010) and DESI-LIS, labels are generated based
on the database of SIMBAD333http://simbad.u-strasbg.fr/ (the Set of
Identifications, Measurements and Bibliography for Astronomical Data, Wenger
et al. 2000). To evaluate the completeness, accuracy, and purity of
identifying QSOs candidates from the photometry data of point-like sources in
DESI-LIS and WISE, we inject a testing set that mimics to-be-applied data in
magnitude and color space. Later, the trained model is applied to point-like
sources in DESI-LIS, and the quasar candidate catalogs are acquired. At last,
we compare our results to those of the color-cut selection approach for cross-
validation, and they match well. For the convenience of other researchers, we
make the all the data in this paper publicly available
online444https://github.com/EigenHermit/he-li2021.

The paper is organized as follows. The construction of the datasets used in
this paper is presented in Sec. 2. Sec. 3 introduces the details of the
methods for detecting QSOs adopted in this study. We then show the results in
Sec. 4. At last, Sec. 5 delivers the discussion and conclusions. In this
paper, a fiducial cosmological model $\Omega_{m}=0.26$, $\Omega_{DE}=0.74$,
$h=0.72$, $w_{0}=-1$ and $w_{a}=0$ is adopted. The cosmology is the same as
the one adopted in Oguri & Marshall (2010, OM10 hereafter).

##  2 Data-sets

The datasets adopted in this work include DESI-LIS, WISE, SDSS eBOSS DR16, and
SIMBAD. The training set combines photometry data from DESI-LIS and WISE,
while the labels are from the confirmed QSO catalog from SDSS eBOSS DR16 and
SIMBAD. The validation set is extracted from training set. To evaluate the
performance of the classification of QSO candidates, we also build a testing
set with the SIMBAD database and eBOSS dataset. Introduction to the above
datasets and details of the construction of training and testing sets are
described below.

###  2.1 DESI-LIS,WISE,eBOSS,SIMBAD

DESI Legacy Imaging Surveys and WISE

DESI Legacy Imaging Surveys555https://www.legacysurvey.org/ (Dey et al. 2019,
DESI-LIS) contains Dark Energy Camera Legacy Surveys
(DECaLS666https://www.legacysurvey.org/decamls/), Beijing-Arizona Sky Survey
(BASS777https://www.legacysurvey.org/bass/) and Mayall $z$-band Legacy Survey
(MzLS888https://www.legacysurvey.org/mzls/), covering $\sim$ $14,000$ deg2 of
the extra-galactic sky in three optical bands ($g$, $r$, and $z$). Notebly,
DESI-LIS DR9 also includes four mid-infrared bands (at $3.4$, $4.6$, $12$, and
$22$ $\mu m$, corresponding to $W1$, $W2$, $W3$ and $W4$ repectively) observed
by WISE999http://wise.ssl.berkeley.edu/index.html. We adopt the photometry
information in $g$, $r$, $z$, $W1$, $W2$ bands from the above datasets to
search for the quasar candidates from $425,540,269$ point-like sources in
DESI-LIS DR9 catalog101010https://www.legacysurvey.org/dr9/).

SDSS eBOSS DR16

The Sloan Digital Sky Survey (SDSS, see, e.g. York et al. 2000, for more
details) is a major multi-spectral imaging and spectroscopic redshift survey
and has a long-running history of more than 20 years. The eBOSS (grounded upon
SDSS-IV, Blanton et al. 2017) is an extended project of BOSS (Baryon
Oscillation Spectroscopic Survey, grounded upon SDSS-III, Dawson et al. 2013;
Eisenstein et al. 2011), which maps the LRGs (luminous red galaxies, Zhou et
al. 2020; Fortuna et al. 2021) and quasars to determine the characteristic
scale of BAOs imprinted at the large-scale structure. eBOSS covers a broader
range of redshifts than that of BOSS. Based on the Data Release $16$ of eBOSS,
Lyke et al. (2020) publishes a catalog containing $750,414$ quasars (DR16Q,
hereafter), which is the largest catalog of quasars confirmed
spectroscopically. We employ the classification labels from eBOSS DR16 to
construct the part of positives in training and testing sets.

SIMBAD

SIMBAD is a comprehensive database that collects information on astronomical
objects, such as types, fluxes, proper motion, etc., maintained by the Centre
de données astronomiques de Strasbourg (CDS). To date, SIMBAD includes
$11,953,504$ objects, $\sim$ $50\%$ of them are stars (Paturel et al. 2003;
Zuckerman et al. 2003; Cayrel et al. 2004), and the others are non-stellar
objects like AGNs, starburst galaxies, emission-line galaxies (Fu et al.
2021). The types of astronomical
objects111111http://simbad.u-strasbg.fr/simbad/sim-display?data=otypes in
SIMBAD are derived from physical characteristics (Mickaelian et al. 2006;
Małek et al. 2010), and the astronomical objects with uncertain physical types
are marked as ‘XX_Candidate’ or ‘Possible_XX’, e.g., ‘AGN_Candidate’. In
addition, ‘main_type’ and ‘other_types’ are given in SIMBAD to deal with the
situations in which different studies suggest different types of the same
object. We use the non-QSOs data in SIMBAD to build the part of negatives in
training and testing sets.

###  2.2 Training and Testing Datasets

The training and testing sets comprise photometry information and labels,
where the photometry is from DESI-LIS and WISE, and the labels are from eBOSS
DR16 and SIMBAD, respectively. To avoid the problem of overfitting, we extract
a subset from the training set for creating a validation set. Notably, the
testing set is organized for mimicking the to-be-applied dataset to estimate
the classification performance using our method.

Parent Samples

We first make two parent samples (hereafter, $S1$ and $S2$) to separately
prepare the positives and negatives in training and testing sets. For $S1$, we
first obtain $745,417$
QSOs121212https://www.legacysurvey.org/dr9/files/#survey-dr9-region-
dr16q-v4-fits by combining the photometry in DESI-LIS and labels in DR16Q via
cross-matching the catalogs of DESI-LIS and DR16Q. Then, we clean the cross-
matched catalog by selecting point-like sources in DESI-LIS (i.e., classified
as PSFs) that having all five-bands ($g,r,z,W1,W2$) detections. $S1$ holds
$655,017$ QSOs at last. Similarly, $S2$ is acquired by combining photometry in
DESI-LIS and the classification labels in SIMBAD, and the cross-match between
SIMBAD and DESI-LIS PSFs is executed. Besides, we clean the $1,993,373$
sources obtained through the above procedure according to the ‘main_type’ in
SIMBAD. Details are listed below:

  1. 1.

The sources labeled as quasars are abandoned.

  2. 2.

The sources classified by their SEDs (Spectral Energy Distributions, see e.g.
Richards et al. 2006, for an introduction), region, numbers, time-domain
characteristics and the ones with gravitational lensing effect are eliminated.
Therefore, the types listed in the first line of Tab. 1 are excluded.

  3. 3.

The sources that have uncertain physics types are discarded, i.e., we exclude
all the sources that have ‘Candidate’, ‘Possible’, ‘?’, or ‘Unknown’ in their
‘main_type’.

  4. 4.

The sources classified as AGN and the types that relate to galaxies are
excluded. Therefore, the sources have the labels listed in the second line of
Tab. 1 are discarded. Although we only use point-like sources in DESI, some
galaxies are still involved in DESI-LIS PSFs because extremely compact
galaxies and the high-density regions in large galaxies might be classified as
point sources.

  5. 5.

The ‘LINER’, ‘Blazar’, ‘Seyfert’ and ‘BLLac’ are cleaned since they mimic the
color of the quasars (Peters et al. 2015).

After these operations, we further take care of the information given in
‘other_types’. We remove the sources that have the labels listed in the third
line of Tab. 1. At the end, there are $1,363,030$ non-QSOs left from
$1,993,373$ sources. Note that $99.85\%$ of non-QSOs are stars, and the rests
have non-stellar features such as ‘HII (ionized) region’ ($0.11\%$) and
‘Emission Object’ ($0.02\%$). Details of the catalog of negatives are
available online 131313https://github.com/EigenHermit/he-
li2021/blob/main/s2_types.csv.

| SIMBAD Type
---|---
1 | Radio/Region/Gravitation/lensedimage/Lensed/GravLens
Void/Transient/Maser/IR/Red/Blue/UV/X/gamma/multiple_object
2 | SuperClG/ClG/GroupG/Compact_Gr_G/PairG/IG/OpCl
GinPair/LISB_G//HII_G/GinGroup/PartofG/EmG/GinCl/
Galaxy/AGN
3 | quasar/Q?/AGN/Galaxy/G/Gravitation/grv/Lev/LIS?/Le?/LI?/gLe?
gLIS/GWE/reg/vid/SCG/CIG/CrG/CGG/PaG/IG

Table 1: The types of objects that we abandon when build the training and
testing set. See more details at Sec. 2.1

.

Testing Set

The testing set are constructed by selecting objects in $S1$ and $S2$
according to the distributions of magnitudes of QSOs in DESI-LIS modeled by a
typical luminosity function (LF, hereafter) and a SED (Bianchini et al. 2019)
since the distributions of QSO and non-QSO in testing set should be similar to
the corresponding ones of DESI-LIS if we plan to evaluate the classification
performance with the testing set. The LF is double power-law as is modeled in
OM10:

$\frac{d\Phi_{QSO}}{dM}=\frac{\Phi_{*}}{10^{0.4(\alpha+1)(M-M_{*})}+10^{0.4(\beta+1)(M-M_{*})}}\,\,,$
(1)

where $M$ stands for the absolute $i$-band magnitude of quasars. $M_{*}$
indicate the change of LF with redshift, which is given by

$M_{*}=-20.90+5{\rm log}\ h-2.5{\rm log}\ f(z)$ (2) $f(z)=\frac{e^{\zeta
z}(1+e^{\xi z_{*}})}{(\sqrt{e^{\xi z}}+\sqrt{e^{\xi z_{*}}})^{2}}$ (3)

The parameter settings ($\zeta,\ \xi,\ \alpha,\ \beta$) are also taken from
OM10. On the other hand, the number of quasars in a redshift bin
$(z_{0},z_{1})$ is

$N(z_{0},z_{1})=V\int_{M_{2}}^{M_{1}}\frac{d\Phi_{QSO}}{dM}dM\,\,,$ (4)

where $V$ is the comoving volume in $(z_{0},z_{1})$, $\frac{d\Phi_{QSO}}{dM}$
is given by Equ. 1. $M_{1}$ and $M_{2}$ are the upper and lower boundary of
$M$. The comparison of the redshift distributions given by LF and by
observations is show in Fig. 1 and they are in a good agreement.

We further predict the magnitude distributions of $g$, $r$, $z$-bands using a
typical SED (Bianchini et al. 2019) based on the $i$-band magnitude
distribution of QSOs acquired above. According to the predicted distributions
of $g$, $r$, $z$-bands, the $W1,W2$ is directly taken from $3,944$ quasars in
$S1$. The $W1,W2$ cannot be calculated merely based on SED because the host
galaxies of QSOs contribute to the total fluxes considerably in $W1,W2$ bands
(Li et al. 2021). Thus, the $10,000$ mock quasars form the positives in the
testing set, and the distributions are shown in Fig 2.

Moreover, we select the non-QSOs from $S2$ to construct the negative part of
the testing set. The criterion is that: we find such non-QSOs to make the
overall distributions (testing QSOs + non-QSOs) similar to the overall
distributions of DESI-LIS PSFs. The testing set contains $990,000$ non-quasars
($135,858$ individual ones). The comparisons in magnitude and color spaces
between DESI-LIS PSFs and the testing set are shown in Fig. 3. In the space of
all $15$-d colors, the twos show a good agreement and are particularly good in
the color space (the mean and stranded deviation differences are less than
$1\%$). In magnitude space, however, the testing set is slightly brighter than
DESI-LIS PSFs due to the selection effect of SIMBAD.

Above all, the testing set contains $100,000$ sources, 1% (Page 2001) of them
are quasars, built upon $3,944$ quasars in $S1$ and $135,858$ non-quasars in
$S2$.

Training Set

Except for the sources in the testing set, the rests in $S1$ and $S2$ comprise
the training set. Explicitly, there are $651,073$ positives and $1,227,172$
negatives in the training set, and the distributions of quasars in the
training set are shown in Fig. 4.

Figure 1: The comparison of redshfit distributions. The orange one is
calculated by (1). The blue one is from DR16Q.

Figure 2: The distributions of $g,r,z,W1,W2$ of the quasars in the testing
set.

Figure 3: The comparisons between the testing set and DESI-LIS PSFs. The upper
is in color space while the lower in magnitude space.

Figure 4: The distributions of $g,r,z,W1,W2$ of the quasars in the training
set. The $g$-band peak magnitude is shown by the vertical dashed line, which
is determined by a kernel density estimate plot (blue solid curve) that gotten
by kdeplot in seaborn package with the default Gaussian kernel and
$binwidth=0.5$.

##  3 Methodology

The primary approach for identifying QSO candidates is constructed upon Random
Forest in this work. The evaluation metrics for the outcomes include
completeness, accuracy, and area under the receiver operating characteristic
(ROC) curve (AUC). Also, we create a baseline for the identification of QSO
candidates using the traditional color-cut selection method for cross-
validation.

###  3.1 Random Forest

Random Forest is a mature machine learning algorithm and has been widely
employed in astronomy. RF was firstly proposed and named ‘random decision
forests’ by Ho (1995), then improved and renamed ‘random forests’ by Breiman
(2001). The basic workflow of RF is that: 1)Randomly segments the input data;
2) trains a group of decision tree models (Dobra 2018) with the segmented data
separately; 3) gives the final judgments by combining the outputs of all
decision trees. Breiman (2001) has suggested that RF compare favorably to
AdaBoost (Freund & Schapire 1996) but it is more robust on missing and
unbalanced data, and performs well on multi-dimension data.

In particular, when dealing with the classification of star-galaxy-quasar with
photoemtry, Bai et al. (2019) presents the superiority of RF over K-Nearest
Neighbour (Altman 1992) and Support Vector Machine (Cristianini & Ricci 2008)
by implementing a comprehensively comparative investigation, which inspires us
to choose RF for our purpose.

In this study, we construct our classifier based on the RF module in Scikit-
learn package 141414https://scikit-learn.org/stable/ (Pedregosa et al. 2011).
The parameters of RF model are tweaked to achieve the best completeness and
purity (described at Sec 3.3) that evaluated by validation set, explicitly,
$max\\_depth=20$, $n\\_estimators=200$, $oob\\_score=True$, and
$random\\_state=0$.

###  3.2 Color-cut Selection

The color-cut selection (in $g-z$ versus $grz-W$ space, following Yèche et al.
2020) is performed to validate the candidates that selected by Random Forest
model, which is a widely used method for selecting quasars with photometry
data (see e.g. Warren et al. 1991; Croom et al. 2004; Richards et al. 2005;
Morganson et al. 2014, for the applications) because the magnitude of quasars
in the UV band is brighter than normal stars and galaxies (Elvis et al. 1994)
comparing to the stars that have similar magnitudes in optical bands. QSOs are
also roughly two magnitudes brighter in the near infrared bands across a wide
redshift range (Peters et al. 2015). Above all, we slightly update the
strategies of color-cut selection procedure in Yèche et al. (2020), and create
a QSOs candidate catalog for cross-validating with the results given by RF
model. Details of selection criteria are listed in Tab. 2, and the definitions
are:

$\begin{split}flux(grz)&=\frac{flux(g)+0.8\times flux(r)+0.5\times
flux(z)}{2.3}\\\ flux(W)&=0.75\times flux(W1)+0.25\times flux(W2)\end{split}$
(5)

The first four criteria in Tab. 2 are directly taken from Yèche et al. (2020)
while the last one is designed to further limit the samples by taking
advantage of the aforementioned infrared excess. We note that we use depth
limit ($g=22.7$, similar with Yèche et al. 2020) in this color-cut selection.

| Conditions
---|---
1 |  $g$-$r$>1.3
2 |  $-0.4$<$r$-$z$<$1.1$
3 |  $r$>$17.5$
4 |  $grz$>$17.0$
5 |  $-1$<$grz$-$W$<$4$
Table 2: The selection conditions that used in color-cut selection (detailed
at Sec. 3.2.)

###  3.3 Evaluation Metrics

Completeness, accuracy, and AUC are quintessential classification metrics,
which measure the performance of classification models from various angles.
The three quantities can be calculated by combining True Positives (TP), False
Positives (FP), True Negatives (TN), and False Negatives (FN) in different
forms. Specifically, completeness is given by

$completeness=\frac{TP}{TP+FN},$ (6)

meaning the percentage of quasars in the testing set that can be correctly
picked out; accuracy is given by

$accuracy=\frac{TP+TN}{TP+TN+FP+FN}$ (7)

standing for how well the identification of quasars/non-quasars is; purity is
used to assess how much non-quasar contamination in the quasar candidate
catalogs, which is defined as

$purity=\frac{TP}{TP+FP}\,\,;$ (8)

AUC is the area under the ROC (Fawcett 2006), showing the performance of the
classification at all classification thresholds by plotting False Positive
Rate (FPR) versus True Positive Rate (TPR), defined as

$\displaystyle FPR=\frac{FP}{FP+TN}\,\,,TPR=\frac{TP}{TP+FN}\,\,.$ (9)

AUC represents the overall performance of identification results.

##  4 Results

In results of applying our classifier trained by the training set given in
Sec. 2.2 to DESI-LIS point-like sources (Sec 2.1), we accomplish a catalog of
quasar candidates, detailed in Sec. 4.1. Then, we cross-validate the catalog
with the results obtained via color-cut selection method (see Sec. 3.2), and
the details are shown in Sec. 4.2.

###  4.1 Quasar Candidates Catalogs

We acquire $24,440,816$ quasar candidates, and the magnitude distributions is
shown in Fig 5. To evaluate the completeness, purity, accuracy, and AUC of the
classification, our RF model is applied to the testing set, and the result is
shown in Fig. 6. The completeness remains stable while the other metrics drop
significantly at the faint end. The three bins of the testing set are divided
by $g$-band magnitudes given below, and each bin contains similar amounts of
unique sources:

bin1: $18<g<19.8$

bin2: $19.8<g<21.18$

bin3: $21.18<g<24$ .

We split the sample into Grade-A and Grade-B with a $g$ band magnitude of
$21.18$ because the purities of classifying the objects below and above the
magnitude are significantly different. Grade-A and Grade-B contain $1,953,932$
and $22,486,884$ candidates separately.

The above classification is constructed by defining a threshold of the
probability given by our classifier, where $P_{\rm th}=0.5$. Correspondingly,
Grade-A has the purity $\sim 0.3$ and accuracy $\sim 0.99$; Grade-B has the
purity $\sim 0.15$ and accuracy $\sim 0.90$. Notably, the completeness remains
high in all magnitude bins (see the orange line in Fig. 6). The errorbars
represent the uncertainties by bootstrapping the elements in each bin (Efron
1982). Expressly, larger errorbars of purity in brighter bins are due to the
fewer quasars; larger errorbars of accuracy in fainter bins are due to the
decreasing capacity of the RF model.

To further investigate the effects of the thresholds of the probability of
being a QSO on the performance of the classification, we test
$0.5,0.6,0.7,0.8,0.9$ as $P_{\rm th}$, and the result is shown in Fig. 7. In
all cases, the completeness is higher than $0.85$, and the completeness is
even higher than $0.99$ (see the green filled region) when $P_{\rm
th}=\\{0.5,0.6,0.7\\}$, but it decreases to $0.95$ (see the purple filled
region) when $P_{\rm th}=0.8$. Therefore, $P_{\rm th}=0.5$ is for general
purpose, and it gives high completeness but low purity. However, one can
change $P_{\rm th}$ for a specific combination of completeness and purity
according to the tendency shown in Fig. 7.

Considering the various setups of DECaLS and BASS+MzLS, the corresponding QSO
candidates in their footprints have different statistical properties. As
displayed in Fig.8, the $g$-band magnitudes distribution and $g-z$
distribution are identical in DECaLS and BASS + MzLS footprints for Grade A
candidates due to their higher confidence. But for Grade B candidates, the
most significant difference between the magnitude distributions of the
candidates in DECaLS and BASS + MzLS footprints is in the $g$-band because the
most notable difference is in the efficiency of the $g$-filter of DECaLS and
BASS. The Grade B candidates in DECaLS are shallower than those in BASS + MzLS
in the $g$-band and are slightly bluer than those in BASS + MzLS when choosing
$g-z$ as the color indicator. To quantify the influences of the above
differences on the identification of quasar candidates, we explore the
performance of the classification when the RF models are individually trained
by DECaLS (or BASS+MzLS). As shown in Fig. 9, the overall performances
(represented by the area under the ROC, a.k.a AUC) with the new training
strategy are slightly better than the earlier one which ignores the different
setups between DECaLS and BASS + MzLS. However, the differences in
completeness (i.e., TPR) are $\sim 1$ ‰ when we choose 0.5 (the adopted value
in this work) as the classification threshold, while FPRs and Purity increase
$10\sim 20\%$ (see cross-marks and plus-marks in Fig. 9, and Tab. 3 for
explicit values). For others’ convenience, we attach catalogs of quasar
candidates obtained by adopting the latter training and classifying strategy
as complementary to the earlier results, which can be found in the same
repository 151515https://github.com/EigenHermit/he-li2021.

Figure 5: The distributions of $g,r,z,W1,W2$ of all quasars candidates. Figure
6: The results when the RF model (solid lines) and color-cut selection (dashed
lines) are applied to the testing set. The testing set is divide in to three
subsets according to their $g$-band magnitudes. The details are given in Sec.
4.1. When testing the color-cut selection, a limit magnitude is used (detailed
at Sec. 3.2) and shown with red dot-dashed line. Figure 7: The variety of
completeness when different $P_{\rm th}$ are applied. The way of splitting
testing set is the same with the ones for Fig. 6. The area where the
completeness higher than $0.99$ is filled by green, while the ones higher than
$0.95$ is filled by purple.

Grade-A

Grade-B

Figure 8: The $g$ and $g-z$ distributions of Grade-A (first line) and Grade-B
(second line) candidates that been observed in BASS + MzLS and DECaLS
footprints.  Figure 9: The ROC curves of the RF model that is trained in four
different cases. The four scatters explicitly indicate the FPR and TPR when
$P_{\rm th}=0.5$.

###  4.2 Cross-validation

To cross-check the QSO candidates found by our classifier, we identify QSO
candidates using the color-cut selection independently, and the selection
criteria are listed in Sec. 3.2. Consequently, $8,425,413$ and $19,575,604$
candidates are found by the RF model and color-cut selection separately. There
are $6,909,375$ candidates discovered using both approaches, i.e., $\sim 82\%$
RF candidates retrieved by the color-cut selection, as shown in Fig. 10. The
red line represents the hard edge of the color-cut selection, and the color-
cut selection discards the RF candidates below this line. The hard-cut leads
to $\sim 18\%$ of the RF candidates missed by the color-cut selection because
the RF selection gives an irregular shape in the color space. On the other
hand, $12,666,119$ ($\sim 65\%$) of color-cut candidates are new compared to
RF candidates since the color-cut selection has lower purity than the RF model
(see the blue dashed line in Fig. 6), bringing in plenty of False Positives.

Furthermore, we test the Grade-A and B candidates in color-cut space as shown
in Fig. 11. Quantitatively, $\sim 91\%$ ($1,771,762$ / $1,953,932$) Grade-A
candidates and $\sim 79\%$ ($5,137,613$ / $6,471,481$) Grade-B candidates and
can be re-found by color-cut selection. This result is consist with the ones
that could be read from Fig. 6: the purity decrease at fainter region.

Figure 10: Two-dimensional histogram for comparing RF model and color-cut
selection. The definitions of $grz$ and $W$ can be found in Sec. 3.2 and the
red-line represents color-cut condition (Sec. 3.2), the points below the line
are discarded by color-cut selection.

Figure 11: Similar plots with Fig. 10 but for comparing Grade-A candidates (upper) and Grade-B candidates (lower) and the corresponding known quasars. | Completeness (TPR) | Purity | FPR
---|---|---|---
A to A | 1.000 | 0.168 | 0.119
B to B | 1.000 | 0.133 | 0.187
AB to A | 0.995 | 0.143 | 0.143
AB to B | 0.998 | 0.129 | 0.213
Table 3: The completeness, purity, FPR of four cases when $0.5$ is adopted as
threshold. A represents BASS + MzLS while B represents DECaLS (same with Fig.
9).

##  5 Discussion and Summary

In this work, we have built a catalog of QSO candidates by applying an
approach based on Random Forest to the datasets of DESI-LIS and WISE. To train
our method, we construct a training set by cross-matching photometry data,
including $g$,$r$,$z$ from DESI-LIS and $W1$, $W2$ from WISE, with
spectroscopically confirmed QSOs from eBOSS DR16Q for positives and the SIMBAD
database for negatives. A testing set mocking the statistical properties of
to-be-applied data in magnitude and color is also created and injected to
evaluate the completeness, accuracy, and purity of the identification process.
At last, $24,440,816$ QSO candidates are identified out of $425,540,269$
point-like objects in DESI-LIS. In addition, we validate our results with
those of the color-cut selection approach, and they match well. The catalog
can be considered the reference for further observations of DESI and other
spectrum surveys to identify new quasars. Relevant data including Grade-A and
Grade-B catalogs, training and testing sets are available
online161616https://github.com/EigenHermit/he-li2021. Furthermore, the Grade-B
candidates in DECaLS are slightly shallower and bluer than those in BASS +
MzLS footprints due to the difference in the efficiency of the $g$-band
filters in DECaLS and BASS (see Fig.3 in Dey et al. 2019). However, the gap
disappears in Grade-A candidates because of their high signal-to-noise ratios.
The gaps lead to concerns about the selection of training strategies, i.e.,
whether the classifier should be trained with the data from the DESI-LIS
footprint or only from the DECaLS (or BASS + MzLS) footprint. Our experiments
present the completeness is nonsensitive to training strategies when we choose
$P_{\rm th}=0.5$ as the classification threshold (Tab. 3). Regardless,
additional catalogs of quasar candidates obtained through the RF models
trained with the latter training strategy are also published along with the
primary catalogs for the others’ convenience.

According to the evaluations based on the testing set, the overall purity is
$\sim 0.25$ while the completeness is higher than $0.99$. We further define
two grades for the candidates by placing a demarcation in $g$-band magnitudes,
i.e., the Grade-A catalog contains $1,953,932$ candidates that are brighter
than $g=21.18$, while the Grade-B contains $22,486,884$ candidates that are
fainter than $g=21.18$. Besides, the accuracy, purity and AUC of the Grade-A
catalog are all higher than Grade-B catalog’s, specifically, accuracy is $\sim
0.1$ higher, purity is $\sim 0.15$ higher and AUC is $\sim 0.05$ higher.
However, the completeness of Grade-A is barely the same as Grade-B, which is
above 0.85 under all test thresholds (0.5,0.6,0.7,0.8,0.9). The object is
considered as a quasar candidate when its RF score is higher than thresholds.
We select $0.5$ as the identification threshold for general purposes. With
this threshold, $\sim$ 82% of the quasar candidates found by our method could
be rediscovered by the color-cut selection method. Nevertheless, as is
expected, a higher threshold leads to lower completeness but higher purity.
Thus, one can tweak the threshold to satisfy the requirements of their own
scientific goal.

We implement the search for QSOs over the whole field of view of DESI-LIS DR9,
covering $\sim 14000$ square degrees of the extragalactic sky visible from the
northern hemisphere, more extensive than previous work. Besides, by evaluating
the classification outcomes of the testing set, we find that the completeness
of the QSO candidate catalogs has high completeness when selecting $0.5$ as
the identification threshold, which means that the confirmation process with
DESI following our targets catalogs can achieve a QSO catalog with both high
completeness and purity. However, considering the photometry data adopted in
this work ($g,r,z,W1,W2$), the performance of the identification can be
further improved with data in additional bands such as UV and radio. Moreover,
blended objects contaminate the photometry catalog due to the PSF size of
DESI-LIS; for instance, the objects considered as extended sources are
excluded firstly in our work, which might include blended QSOs or blended QSOs
and galaxies. Thus, to further increase the completeness of the targets
catalog, one needs to conduct a deblending operation over the whole datasets
of DESI-LIS before banning negatives, which is part of our further work.

To summarize, this study provides the largest-ever catalog of QSOs candidates
with high completeness, which can be used for the targets dataset for
confirming QSOs with DESI. Furthermore, grounded on this QSO candidates
catalog, we are trying to find the candidates of strongly lensed QSOs with a
catalog-based algorithm. So far, $\sim 800$ high-quality candidates of new
strongly lensed QSO systems have been found and will be reported in a separate
paper. Thorough follow-ups and analyses will be applied to the candidates.
Next, we will constrain the properties of the circumgalactic medium (Cai et
al. 2019; Lau et al. 2022), dark matter distribution in lens galaxies (Oguri
et al. 2014; Sonnenfeld & Cautun 2021), Hubble constant (Suyu et al. 2017;
Liao et al. 2019; Wong et al. 2020) with confirmed strongly lensed QSO
systems.

###### Acknowledgements.

We thank the anonymous referee for valuable and constructive comments. We
acknowledge the science research grants from the China Manned Space Project
with NO.CMS-CSST-2021-A01. We thank China-VO for providing DESI-LIS data and
download service for our catalogs. We thank Huanyuan Shan, Rui Li, Dongxu
Zhang, Heyang Liu, Jiao Li, Hao Tian, Hui Sun and Jiadong Li for the extensive
discussions. We thank astropy, scikit-learn, pandas, seaborn for providing
convenient and reliable python packages.

## References

  * Agol & Krolik (1999) Agol, E., & Krolik, J. 1999, ApJ, 524, 49
  * Alam et al. (2021) Alam, S., Aubert, M., Avila, S., et al. 2021, Phys. Rev. D, 103, 083533
  * Altman (1992) Altman. 1992, The American Statistician, 46, 175
  * Antonucci (1993) Antonucci, R. 1993, ARA&A, 31, 473
  * Bai et al. (2019) Bai, Y., Liu, J., Wang, S., & Yang, F. 2019, AJ, 157, 9
  * Bianchini et al. (2019) Bianchini, F., Fabbian, G., Lapi, A., et al. 2019, ApJ, 871, 136
  * Bisogni et al. (2021) Bisogni, S., Lusso, E., Civano, F., et al. 2021, arXiv e-prints, arXiv:2109.03252
  * Blackburne et al. (2011) Blackburne, J. A., Pooley, D., Rappaport, S., & Schechter, P. L. 2011, ApJ, 729, 34
  * Blanton et al. (2017) Blanton, M. R., Bershady, M. A., Abolfathi, B., et al. 2017, AJ, 154, 28
  * Breiman (2001) Breiman, L. 2001, Machine Learning, 45, 5
  * Breiman (2001) Breiman, L. 2001, Statistical Science, 16, 199
  * Cai et al. (2019) Cai, Z., Cantalupo, S., Prochaska, J. X., et al. 2019, ApJS, 245, 23
  * Cayrel et al. (2004) Cayrel, R., Depagne, E., Spite, M., et al. 2004, A&A, 416, 1117
  * Chen et al. (2020) Chen, C., Hamann, F., Ma, B., et al. 2020, ApJ, 902, 57
  * Chen (2021) Chen, Y.-C. 2021, arXiv e-prints, arXiv:2109.06881
  * Clarke et al. (2020) Clarke, A. O., Scaife, A. M. M., Greenhalgh, R., & Griguta, V. 2020, A&A, 639, A84
  * Cristianini & Ricci (2008) Cristianini, N., & Ricci, E. 2008, Support Vector Machines, ed. M.-Y. Kao, Encyclopedia of Algorithms, ed. M.-Y. Kao (Boston, MA: Springer US), 928
  * Croom et al. (2004) Croom, S. M., Smith, R. J., Boyle, B. J., et al. 2004, Monthly Notices of the Royal Astronomical Society, 349, 1397
  * Croton et al. (2006) Croton, D. J., Springel, V., White, S. D. M., et al. 2006, MNRAS, 365, 11
  * Dawson et al. (2013) Dawson, K. S., Schlegel, D. J., Ahn, C. P., et al. 2013, AJ, 145, 10
  * Dawson et al. (2016) Dawson, K. S., Kneib, J.-P., Percival, W. J., et al. 2016, AJ, 151, 44
  * Delubac et al. (2015) Delubac, T., Bautista, J. E., Busca, N. G., et al. 2015, A&A, 574, A59
  * DESI Collaboration et al. (2016) DESI Collaboration, Aghamousa, A., Aguilar, J., et al. 2016, arXiv e-prints, arXiv:1611.00036
  * Dexter & Agol (2011) Dexter, J., & Agol, E. 2011, ApJ, 727, L24
  * Dey et al. (2019) Dey, A., Schlegel, D. J., Lang, D., et al. 2019, AJ, 157, 168
  * Di Matteo et al. (2005) Di Matteo, T., Springel, V., & Hernquist, L. 2005, Nature, 433, 604
  * Dobra (2018) Dobra, A. 2018, Decision Tree Classification, ed. L. Liu & M. T. Özsu, Encyclopedia of Database Systems, ed. L. Liu & M. T. Özsu (New York, NY: Springer New York), 1017
  * Dong et al. (2018) Dong, X. Y., Wu, X.-B., Ai, Y. L., et al. 2018, AJ, 155, 189
  * Dunlop et al. (2003) Dunlop, J. S., McLure, R. J., Kukula, M. J., et al. 2003, MNRAS, 340, 1095
  * Efron (1982) Efron, B. 1982, The Jackknife, the Bootstrap and other resampling plans
  * Eisenstein et al. (2011) Eisenstein, D. J., Weinberg, D. H., Agol, E., et al. 2011, AJ, 142, 72
  * Elvis et al. (1994) Elvis, M., Wilkes, B. J., McDowell, J. C., et al. 1994, ApJS, 95, 1
  * Fawcett (2006) Fawcett, T. 2006, Pattern Recognition Letters, 27, 861
  * Font-Ribera et al. (2014) Font-Ribera, A., Kirkby, D., Busca, N., et al. 2014, J. Cosmology Astropart. Phys, 2014, 027
  * Fortuna et al. (2021) Fortuna, M. C., Hoekstra, H., Johnston, H., et al. 2021, arXiv e-prints, arXiv:2109.02556
  * Freund & Schapire (1996) Freund, Y., & Schapire, R. E. 1996, in IN PROCEEDINGS OF THE THIRTEENTH INTERNATIONAL CONFERENCE ON MACHINE LEARNING (Morgan Kaufmann), 148
  * Fu et al. (2021) Fu, Y., Wu, X. B., Yang, Q., et al. 2021, VizieR Online Data Catalog, J/ApJS/254/6
  * Guarneri et al. (2021) Guarneri, F., Calderone, G., Cristiani, S., et al. 2021, MNRAS, 506, 2471
  * Hall et al. (2013) Hall, P. B., Brandt, W. N., Petitjean, P., et al. 2013, MNRAS, 434, 222
  * Hewett et al. (1995) Hewett, P. C., Foltz, C. B., & Chaffee, F. H. 1995, AJ, 109, 1498
  * Ho (1995) Ho, T. K. 1995, in Proceedings of 3rd International Conference on Document Analysis and Recognition, Vol. 1, 278
  * Kaspi et al. (2000) Kaspi, S., Smith, P. S., Netzer, H., et al. 2000, ApJ, 533, 631
  * Kellermann (2014) Kellermann, K. I. 2014, Journal of Astronomical History and Heritage, 17, 267
  * Kormendy & Ho (2013) Kormendy, J., & Ho, L. C. 2013, ARA&A, 51, 511
  * Kormendy & Richstone (1995) Kormendy, J., & Richstone, D. 1995, ARA&A, 33, 581
  * Lau et al. (2022) Lau, M. W., Hamann, F., Gillette, J., et al. 2022, arXiv e-prints, arXiv:2203.06203
  * Levi et al. (2013) Levi, M., Bebek, C., Beers, T., et al. 2013, arXiv e-prints, arXiv:1308.0847
  * Li et al. (2021) Li, J., Silverman, J. D., Ding, X., et al. 2021, The Astrophysical Journal, 918, 22
  * Liao et al. (2019) Liao, K., Shafieloo, A., Keeley, R. E., & Linder, E. V. 2019, The Astrophysical Journal, 886, L23
  * Lupi et al. (2021) Lupi, A., Volonteri, M., Decarli, R., Bovino, S., & Silk, J. 2021, arXiv e-prints, arXiv:2109.01679
  * Lyke et al. (2020) Lyke, B. W., Higley, A. N., McLane, J. N., et al. 2020, ApJS, 250, 8
  * Małek et al. (2010) Małek, K., Pollo, A., Takeuchi, T. T., et al. 2010, A&A, 514, A11
  * McLure & Jarvis (2002) McLure, R. J., & Jarvis, M. J. 2002, MNRAS, 337, 109
  * Merz et al. (2021) Merz, G., Rezaie, M., Seo, H.-J., et al. 2021, MNRAS, 506, 2503
  * Mickaelian et al. (2006) Mickaelian, A. M., Hovhannisyan, L. R., Engels, D., Hagen, H. J., & Voges, W. 2006, A&A, 449, 425
  * Mishra et al. (2021) Mishra, S., Gopal-Krishna, Chand, H., et al. 2021, MNRAS, 507, L46
  * Morgan et al. (2010) Morgan, C. W., Kochanek, C. S., Morgan, N. D., & Falco, E. E. 2010, ApJ, 712, 1129
  * Morganson et al. (2014) Morganson, E., Burgett, W. S., Chambers, K. C., et al. 2014, ApJ, 784, 92
  * Myers et al. (2015) Myers, A. D., Palanque-Delabrouille, N., Prakash, A., et al. 2015, ApJS, 221, 27
  * Oguri & Marshall (2010) Oguri, M., & Marshall, P. J. 2010, MNRAS, 405, 2579
  * Oguri et al. (2014) Oguri, M., Rusu, C. E., & Falco, E. E. 2014, MNRAS, 439, 2494
  * Osterbrock (1989) Osterbrock, D. E. 1989, Astrophysics of gaseous nebulae and active galactic nuclei
  * Page (2001) Page, M. 2001, Monthly Notices of the Royal Astronomical Society, 328, 925
  * Paturel et al. (2003) Paturel, G., Petit, C., Prugniel, P., et al. 2003, A&A, 412, 45
  * Pedregosa et al. (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., et al. 2011, Journal of Machine Learning Research, 12, 2825
  * Peters et al. (2015) Peters, C. M., Richards, G. T., Myers, A. D., et al. 2015, The Astrophysical Journal, 811, 95
  * Richards et al. (2005) Richards, G. T., Croom, S. M., Anderson, S. F., et al. 2005, MNRAS, 360, 839
  * Richards et al. (2006) Richards, G. T., Lacy, M., Storrie-Lombardi, L. J., et al. 2006, ApJS, 166, 470
  * Ross et al. (2012) Ross, N. P., Myers, A. D., Sheldon, E. S., et al. 2012, ApJS, 199, 3
  * Scaringi et al. (2009) Scaringi, S., Cottis, C. E., Knigge, C., & Goad, M. R. 2009, MNRAS, 399, 2231
  * Schmidt (1963) Schmidt, M. 1963, Nature, 197, 1040
  * Schmidt & Green (1983) Schmidt, M., & Green, R. F. 1983, ApJ, 269, 352
  * Shen et al. (2020) Shen, X., Hopkins, P. F., Faucher-Giguère, C.-A., et al. 2020, MNRAS, 495, 3252
  * Shen et al. (2011) Shen, Y., Richards, G. T., Strauss, M. A., et al. 2011, ApJS, 194, 45
  * Silk & Rees (1998) Silk, J., & Rees, M. J. 1998, A&A, 331, L1
  * Sonnenfeld & Cautun (2021) Sonnenfeld, A., & Cautun, M. 2021, A&A, 651, A18
  * Springel et al. (2005) Springel, V., Di Matteo, T., & Hernquist, L. 2005, MNRAS, 361, 776
  * Suyu et al. (2017) Suyu, S. H., Bonvin, V., Courbin, F., et al. 2017, MNRAS, 468, 2590
  * Urry & Padovani (1995) Urry, C. M., & Padovani, P. 1995, PASP, 107, 803
  * Valentini et al. (2021) Valentini, M., Gallerani, S., & Ferrara, A. 2021, MNRAS, 507, 1
  * Viquar et al. (2018) Viquar, M., Basak, S., Dasgupta, A., Agrawal, S., & Saha, S. 2018, arXiv e-prints, arXiv:1804.05051
  * Wang et al. (2019) Wang, F., Yang, J., Fan, X., et al. 2019, ApJ, 884, 30
  * Warren et al. (1991) Warren, S. J., Hewett, P. C., Irwin, M. J., & Osmer, P. S. 1991, ApJS, 76, 1
  * Wenger et al. (2000) Wenger, M., Ochsenbein, F., Egret, D., et al. 2000, A&AS, 143, 9
  * Wong et al. (2020) Wong, K. C., Suyu, S. H., Chen, G. C. F., et al. 2020, Monthly Notices of the Royal Astronomical Society, 498, 1420
  * Wrigh et al. (2010) Wrigh, E. L., Eisenhardt, P. R. M., Mainzer, A. K., et al. 2010, AJ, 140, 1868
  * Yèche et al. (2020) Yèche, C., Palanque-Delabrouille, N., Claveau, C.-A., et al. 2020, Research Notes of the American Astronomical Society, 4, 179
  * York et al. (2000) York, D. G., Adelman, J., Anderson, John E., J., et al. 2000, AJ, 120, 1579
  * Zabl et al. (2021) Zabl, J., Bouché, N. F., Wisotzki, L., et al. 2021, MNRAS, 507, 4294
  * Zhao et al. (2019) Zhao, G.-B., Wang, Y., Saito, S., et al. 2019, MNRAS, 482, 3497
  * Zhou et al. (2020) Zhou, R., Newman, J. A., Dawson, K. S., et al. 2020, Research Notes of the American Astronomical Society, 4, 181
  * Zuckerman et al. (2003) Zuckerman, B., Koester, D., Reid, I. N., & Hünsch, M. 2003, ApJ, 596, 477


# Where have all the grasshoppers gone?

János Pach Rényi Institute, Budapest and IST Austria. Research partially
supported by National Research, Development and Innovation Office (NKFIH)
grant K-131529 and ERC Advanced Grant “GeoScape.” Email<EMAIL_ADDRESS>Gábor Tardos Rényi Institute, Budapest. Research partially supported by
National Research, Development and Innovation Office (NKFIH) grants K-132696,
SNN-135643 and ERC Advanced Grants ‘GeoSpace” and “ERMiD” Email:
<EMAIL_ADDRESS>
###### Abstract

Let $P$ be an $N$-element point set in the plane. Consider $N$ (pointlike)
grasshoppers sitting at different points of $P$. In a “legal” move, any one of
them can jump over another, and land on its other side at exactly the same
distance. After a finite number of legal moves, can the grasshoppers end up at
a point set, similar to, but larger than $P$? We present a linear algebraic
approach to answer this question. In particular, we solve a problem of Brunck
by showing that the answer is yes if $P$ is the vertex set of a regular
$N$-gon and $N\neq 3,4,6$. Some generalizations are also considered.

##  1 Introduction.

In 1994, at the Moscow Mathematics Olympiad [8], the following question was
asked: _Four grasshoppers are sitting at the vertices of a square. Every
minute, one of them jumps over another and lands at the point symmetric to it.
Prove that the grasshoppers can never end up sitting at the vertices of a
larger square._ The problem was suggested by A. K. Kovaldzhi.

The solution is simple. Suppose, for contradiction, that the grasshoppers can
end up at the vertices of a _larger_ square. Since the moves are reversible,
starting with the final position and reversing the sequence of moves, we can
get from a square to a _smaller_ square. However, this is impossible. Indeed,
we can assume by scaling that the initial positions of the grasshoppers are
$(0,0),(0,1),(1,0),$ and $(1,1)$. Then they will keep jumping around on the
points of the integer grid ${\mathbb{Z}}^{2}$, which has no four points that
form a square of sidelength smaller than 1.

The same argument works when we have _six_ grasshoppers sitting at the
vertices of a regular hexagon $T$. The only difference is that now the
possible positions of the grasshoppers belong to a triangular lattice induced
by two adjacent side vectors of $T$. As $T$ is the smallest regular hexagon in
this lattice, the grasshoppers can never reach a regular hexagonal position of
smaller—and, therefore, by reversibility—of larger side length than $T$.
Exactly the same argument works if we start with a regular triangle (or with
an arbitrary triangle). However, in this case, we have an even simpler
argument: a legal move never changes the _area_ of the triangle determined by
the three pieces. Therefore, after any number of steps, the positions of the
pieces must form a triangle whose area is the same as that of the initial
triangle.

As far as we know, it was Florestan Brunck [3] who first asked: what happens
if there are $5$ grasshoppers, and their starting position is the vertex set
of a regular pentagon? Can they be taken into the vertices of a larger regular
pentagon?

Somewhat surprisingly, the answer to this question is affirmative.

######  Theorem 1.1.

Let $N\geq 3$, and let $C_{N}$ denote a configuration consisting of $N$ pieces
sitting at the vertices of a regular $N$-gon. In a legal move, any piece can
jump over any other piece and land at the point centrally symmetric about it.

Unless $N=3,4,$ or $6$, there is a finite number of moves that take the pieces
of $C_{N}$ into a strictly larger similar configuration.

One can raise the following more general question. Given any two $N$-element
point sets in the plane or in higher dimensions, is it possible to transform
the first one to the second by a sequence of legal moves? In Section 3, we
develop a linear algebraic approach to answer this question.

Throughout this note, we fix an orthogonal system of coordinates in
${\mathbf{R}}^{d}$. Let $P\subset{\mathbf{R}}^{d}$ be a configuration of
$N=n+1$ points. The position of each piece can be described by a _column
vector_ of length $d$. Assume without loss of generality that initially one of
the pieces is at the origin $0$. We distinguish this piece and call it
_stationary_. All other pieces are said to be _ordinary_. The movement of the
stationary piece is artificially restricted: any ordinary piece is allowed to
jump over it, but this piece is not allowed to jump. Note that it is not
forbidden for two or more pieces to sit at the same point at the same time.

Enumerate the elements of $P$ by the integers $0,1,2,\ldots,n$, where $0$
denotes the stationary piece. We identify $P$ with the $d\times n$ real
matrix, whose $i$th column gives the position of the ordinary piece $i$ for
$1\leq i\leq n$. Without any danger of confusion, we denote both the
configuration and the corresponding matrix by $P$. Part 1 of Lemma 3.1, stated
in the next section, characterizes all configurations $P$ that can be reached
from the initial position under the restriction that piece $0$ is stationary.
In part 2, we get rid of this unnatural condition.

In the special case where we want to transform $P$ into a larger configuration
similar to it, we obtain the following result.

######  Theorem 1.2.

Let $P$ be a configuration of $N=n+1$ points in ${\mathbf{R}}^{d}$, one of
which initially sits at the origin but it is still allowed to jump. Let $P$
also denote the $d\times n$ matrix associated with it.

Then $P$ can be transformed into a similar but larger configuration, using
legal moves, if and only if there is an $n\times n$ integer matrix $A$ with
$|\det A|=1$ such that the configuration associated with $PA$ is similar to
and larger than the initial configuration $P$.

Our paper is organized as follows. In Section 2, we prove a simple lemma for
matrices. It is instrumental for our general linear algebraic approach to the
reconfiguration problem, presented in Section 3. In Section 4, we prove our
main theorems. First we establish Theorem 1.2, and then we show how to deduce
from it Theorem 1.1. In the last section, we mention some open problems and
make a few remarks.

The problem discussed in our paper is broadly related to several topics in
pure and applied mathematics and computer science. For instance, the theory of
_discrete dynamical systems_ deals with models in which changes occur in
discrete time steps, according to a fixed rule; see [5]. A _cellular
automaton_ consists of an array of cells, each of which can be in a finite
number of different states. The states get updated depending on the
neighborhoods of the cells [9, 11]. Perhaps the most famous cellular automaton
is _Conway’s game of life_ [7]. These models are mostly deterministic.
Solitary games in which the player can choose one from several possible legal
moves, are studied in the framework of _combinatorial game theory_ [1, 2].
Similar models are analyzed in _motion planning_ and _robotics_ , related to
the reconfiguration of rotating or sliding systems of modules [4].

##  2 Admissible transformations of matrices.

We follow the notation introduced above: A configuration $P$ consisting of $n$
ordinary pieces and a stationary piece at the origin in ${\mathbf{R}}^{d}$ is
identified with a $d\times n$ matrix, also denoted by $P$, the columns of
which correspond to the positions of the ordinary pieces.

The legal move by which the ordinary piece $i$ ($1\leq i\leq n$) jumps over
piece $j$ ($0\leq j\leq n$ and $i\neq j$) brings configuration $P$ to
$PA_{ij}$, where $A_{ij}=(a^{(ij)}_{kl})_{k,l=1}^{n}$ is the $n\times n$ real
matrix defined as follows.

$a^{(ij)}_{kl}=\left\\{\begin{array}[]{ll}1&\text{for }k=l\neq i\\\
-1&\text{for }k=l=i\\\ 2&\text{for }k=j,l=i\\\
0&\text{otherwise.}\end{array}\right.$

For example, for $n=4$, we have

$A_{2,4}=\begin{bmatrix}1&0&0&0\\\ 0&-1&0&0\\\ 0&0&1&0\\\
0&2&0&1\end{bmatrix}\quad\quad\mbox{and}\quad\quad
A_{2,0}=\begin{bmatrix}1&0&0&0\\\ 0&-1&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{bmatrix},$

where the first matrix corresponds to the jump of piece $2$ over piece $4$,
and the second matrix to the jump of $2$ over the stationary piece $0$.
Indeed, denoting the position vectors of $2$ and $4$ by $v_{2}$ and
$v_{4}\in{\mathbf{R}}^{d}$, respectively, after the first move, the new
position of $2$ will be $v_{4}+(v_{4}-v_{2})=-v_{2}+2v_{4}$. This change of
coordinates is reflected by the second column of $A_{2,4}$.

We call the matrices $A_{ij}$ for $1\leq i\leq n$ and $0\leq j\leq n$, $i\neq
j$, _elementary involutions_. (Note that they are indeed involutions, that is,
$A_{ij}^{2}=I$ holds, reflecting the fact that all legal moves are reversible.
Here $I$ stands for the identity matrix.) The positions reachable from an
initial position $P$ (with the piece at the origin remaining stationary) are
precisely the configurations $PA$, where $A$ belongs to the _matrix group_
generated by the _elementary involutions_.

Our first lemma gives a simple characterization of this matrix group. It will
be used in the next section. We write $\det A$ for the determinant of the
square matrix $A$.

######  Lemma 2.1.

An $n\times n$ integer matrix $A=(a_{ij})$ is generated by elementary
involutions if and only if

  1. (i)

$|\det A|=1$;

  2. (ii)

$a_{ij}$ is _even_ if $i\neq j$ and it is _odd_ if $i=j$.

###### Proof.

All elementary involutions have determinant $-1$ and all are equal to the
identity matrix $I$ modulo $2$. Conditions (i) and (ii) are closed under
taking products. That is, if $A$ and $B$ meet them, then so does $AB$. This
proves the “only if” part of the lemma.

It is instructive to think of the elementary involutions as column operations:
For $1\leq i\leq n$ multiplying by $A_{i0}$ from the right is the same as
multiplying column $i$ by $-1$. If we further have $1\leq j\leq n$ and $j\neq
i$, then multiplying by $A_{ij}A_{i0}$ is the same as _subtracting_ twice
column $j$ from column $i$, while multiplying by $A_{i0}A_{ij}$ is the same as
_adding_ column $j$ twice to column $i$. We call these column operations
_admissible_.

We prove the “if” part of the lemma by showing that any matrix satisfying
conditions (i) and (ii) in the lemma can be transformed into the identity
matrix $I$ by admissible operations. We do this by induction on $n$. For
$n=1$, the statement is trivially true. Suppose now that $n>1$ and that our
statement holds for $n-1$. Let $A$ be an $n\times n$ matrix satisfying
conditions (i) and (ii).

Consider the last row of $A$. As long as we can find two entries $a_{ni}$ and
$a_{nj}$ with $|a_{ni}|>|a_{nj}|>0$, by subtracting or adding twice the $j$th
column to the $i$th column, we can reduce the value of $|a_{ni}|$. In this
step, no other entry of the last row changes. Hence, the sum of the absolute
values of the elements of the last row strictly decreases. After a finite
number of such steps (admissible operations), we will get stuck. At this
point, every entry of the last row is either $0$ or $\pm a$ for some integer
$a>0$. During this process, the absolute value of the determinant of the
matrix has remained $1$. Now it is divisible by $a$, so we must have $a=1$.
Since the parities of the elements have not changed, all entries of the last
row must be $0$, with the exception of the last element, which is either $+1$
or $-1$. Applying a single admissible transformation if necessary, we can
assume that this last element is $+1$.

Let $B$ denote the matrix constructed so far, and let $B^{\prime}$ be the
$(n-1)\times(n-1)$ submatrix of $B$, obtained by deleting its last column and
last row. Expanding the determinant of $B$ along its last row, we get that
$|\det B|=|\det B^{\prime}|=1$. Clearly, $B^{\prime}$ also satisfies condition
(ii) of the lemma. Thus, we can apply the induction hypothesis to
$B^{\prime}$, and conclude that $B^{\prime}$ can be transformed to an
$(n-1)\times(n-1)$ identity matrix by performing a number of admissible
transformations. These transformations can, of course, be extended to the
whole matrix $B$. During this process, the last row of $B$ remains the same:
all of its entries, except the last one, remain $0$. Its last column also
remains unchanged.

The matrix obtained so far coincides with the identity matrix $I$, apart from
the entries of its last column that are arbitrary even integers, except for
the last value of the last column, which is equal to $1$.. We can make them
vanish by adding or subtracting each of the first $n-1$ columns by an even
number of times. Thus, by a sequence of admissible transformations, $A$ can be
transformed into $I$, as required. ∎

##  3 Characterization of all reachable positions.

Our next statement gives a complete linear algebraic description of all
configurations that can be obtained from a given initial position of the
pieces by a sequence of legal moves.

######  Lemma 3.1.

Let $P$ be a $d\times n$ matrix associated with the initial configuration of
the $n+1$ pieces in ${\mathbf{R}}^{d}$, one of them in the origin.

  1. 1.

The configurations that can be reached by a sequence of legal moves that keep
the stationary piece at the origin, are exactly the positions corresponding to
a matrix $PA$, where $A$ is a matrix generated by the elementary involutions.

  2. 2.

If we drop the assumption that the stationary piece must stay at the origin
and allow it to jump over any of the remaining $n$ pieces, every reachable
configuration is a translate of some configuration that can be reached without
moving the stationary piece. Moreover, a translate of such a configuration is
reachable if and only if the translation vector is of the form $2Pw$ for an
integer vector $w$.

###### Proof.

Part 1 is immediate from the observation made in the previous section,
according to which the effect of a legal jump by an ordinary piece on the
matrix associated with the configuration is exactly a multiplication by an
elementary involution.

For the proof of part 2, call the piece originally sitting at the origin
_special_. (We can no longer call it stationary.) All other pieces are
ordinary. Let us define for any ordinary piece $A$ a sequence $S_{A}$
consisting of $2n$ legal jumps as follows. Let $S_{A}$ start with the moves in
which all other pieces (including the special piece) jump over $A$, and
continue with the moves where all ordinary pieces jumps over the special
piece. Notice that if we apply the sequence $S_{A}$ to any configuration, all
pieces will move with the same vector: twice the vector from the special piece
to $A$ (either before or after the execution of $S_{A}$). Applying the same
jumps in reverse order, we can move all pieces with the negative of this
vector. This means that applying several of these sequences right at the
start, we can move all the pieces with $2Pw$, for any integer vector $w$. We
can thereafter keep the special piece stationary and reach the translate of
any configuration that was reachable in part 1. This proves that all
configurations described in part 2 of the theorem are indeed reachable by a
sequence of legal moves.

Next we show that any configuration reachable by legal moves is a translate of
a configuration reached by legal moves keeping the special piece stationary.
Consider an arbitrary sequence of legal moves reaching a configuration $X$.
For every ordinary piece $A$, let us insert the sequence $S_{A}$ of jumps
after every time the special piece jumps over $A$. Clearly, these inserted
sub-sequences just act as translations, so we obtain a longer sequence of
legal moves resulting in a translate of $X$. However, as $S_{A}$ starts with
the special piece jumping over $A$, this longer sequence will have all jumps
of the special piece reversed right away, so the same configuration can also
be reached canceling these jumps and keeping the special piece stationary, as
claimed.

It remains to prove that the translation vector, i.e., the position of the
special piece in a configuration reached by legal moves, is of the form $2Pw$
for an integer vector $w$. For this, notice that the pieces remain in the
additive subgroup of the space generated by the original positions of the
pieces. This subgroup is $L=\\{Pw\mid w\hbox{ integer}\\}$. It may be a
discrete lattice but may even be dense in the entire space. Whenever any piece
jumps, it moves with twice a vector from $L$, so the special piece, which
starts at the origin, must end up in $2L=\\{2Pw\mid w\hbox{ integer}\\}$, as
claimed. ∎

##  4 Proof of main theorems.

Theorem 1.2 provides a simpler condition than Lemma 3.1 for the special case
where the final configuration is a similar but larger copy of the initial one.
A configuration is similar to but larger than the one identified with the
matrix $P$ if and only if its matrix is $\lambda SP$, where $|\lambda|>1$ and
$S$ is a $d\times d$ _orthogonal_ matrix.

Proof of Theorem 1.2: The proof of this result would be an immediate
consequence of Lemma 3.1 and Lemma 2.1 if we had also required that the matrix
$A$ satisfies the parity condition, i.e., $A$ is congruent to the identity
matrix $I$ modulo 2. The main observation here is that this requirement can be
dropped.

To see this, assume that $A$ satisfies the conditions of Theorem 1.2. We have
$|\det A|=1$, but as the parity condition is dropped, $A$ is not necessarily
generated by elementary involutions.

Consider the matrix $A$ modulo 2. Its determinant is 1, so it is an element of
the $n\times n$ _matrix group_ $GL(n,2)$. As $GL(n,2)$ is a _finite_ group,
$A$ must have a finite order $t\geq 1$, for which $A^{t}$ agrees with the
identity matrix modulo 2. We also have $|\det(A^{t})|=|\det A|^{t}=1$. Hence,
$A^{t}$ satisfies both conditions in Lemma 2.1 and is, therefore, generated by
elementary involutions. Hence, by Lemma 3.1, $PA^{t}$ is reachable from the
original configuration $P$ by legal jumps (leaving the special piece
stationary). By our assumption on $A$, we have $PA=\lambda SP$, for some
$|\lambda|>1$ and some orthogonal matrix $S$. This implies that
$PA^{t}=\lambda^{t}S^{t}P$, which means that the configuration $PA^{t}$ is
similar to but larger than $P$. This completes the proof. $\Box$

Now we return to the original question addressed in our paper: to the case of
regular polygons.

Proof of Theorem 1.1: Let $N=n+1$ and let
$p_{0},p_{1},p_{2},\ldots,p_{n}\in{\mathbf{R}}^{2}$ denote the vertices of a
regular $N$-gon in the plane, enumerated in positive (counter-clockwise)
cyclic order, and suppose that $p_{0}=0$. The initial position with the $N$
pieces at these vertices is identified with the $2\times n$ matrix $P$, the
$i$th column of which is $p_{i}$, for all $1\leq i\leq n$.

$p_{2}$$p_{3}$$p_{4}$$p_{2}$$p_{3}-p_{1}$$\frac{2\pi}{5}$$0=p_{0}$$p_{1}$

Figure 1: Illustration to the proof of Theorem 1.1.

Let $M$ denote the $n\times n$ matrix

$M=\begin{bmatrix}-1&-1&\cdots&-1&-1\\\ 1&0&\cdots&0&0\\\ 0&1&\cdots&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\cdots&1&0\end{bmatrix}.$

Note that the $i$th column of $PM$ is $p_{i+1}-p_{1}$ for $1\leq i<n$ and
$-p_{1}$ for $i=n$ and thus can be obtained as the rotation of $p_{i}$ with
the positive angle $2\pi/N$ (see Figure 1). Let

$S=\begin{bmatrix}\cos\frac{2\pi}{n+1}&-\sin\frac{2\pi}{n+1}\\\ &\\\
\sin\frac{2\pi}{n+1}&\cos\frac{2\pi}{n+1}\end{bmatrix}$

be the orthogonal matrix representing this rotation. Now we have $PM=SP$.

At this point, we are almost done. We have $|\det M|=1$, and the position $PM$
is similar to $P$, that is, it is also a regular $(n+1)$-gon. If it was also
larger than $P$, we could apply Theorem 1.2 and finish the proof.
Unfortunately, the configuration $PM=SP$ is of exactly the same size as $P$,
because $S$ is a rotation.

We solve this problem by considering polynomials $f(M)$ of $M$. Obviously, we
have $Pf(M)=f(S)P$. Notice that all polynomials $f(S)$ of the matrix $S$ are
of the form

$\begin{bmatrix}a&-b\\\ b&a\end{bmatrix}=\lambda T,$

for some reals $a,b,\lambda$ and for an orthogonal matrix $T$. So, the
configuration $Pf(M)$ is similar to $P$, i.e., it is a (possibly degenerate)
regular $(n+1)$-gon. We can finish the proof by applying Theorem 1.2 if we
find an integer polynomial $f$ such that

  * (i)

$|\det f(M)|=1$, and

  * (ii)

the regular $(n+1)$-gon identified with $Pf(M)$ is larger than $P$.

For a positive integer $k$, consider the matrix

$B_{k}=\sum_{j=0}^{k-1}M^{j}.$

Note that the characteristic polynomial of $M$ is $\sum_{j=0}^{n}t^{j}$.
Recall that $N=n+1$. Thus, we have $B_{N}=0$. We further have

$B_{kN}=B_{N}\sum_{j=0}^{k-1}M^{jN}=0,$

for all $k>0$, and

$B_{kN+1}=I+MB_{kN}=I.$

Let us fix an integer $i$ with $1\leq i<N$ which is coprime to $N$. We can
find positive integers $l$ and $k$ such that $il=kN+1$, and

$B_{i}\sum_{j=0}^{l-1}M^{ij}=B_{il}=B_{kN+1}=I.$

This shows that the integer matrix $B_{i}$ is invertible and its inverse is
also an integer matrix. Therefore, we have $|\det B_{i}|=1$. This was
condition (i) above that a polynomial of $M$ had to satisfy to finish the
proof.

It remains to verify condition (ii) and check that the configuration
identified with $PB_{i}$ (a regular $N$-gon) is strictly larger than the
starting configuration. The side length of the $N$-gon associated with the
configuration $PB_{i}$ is the distance between $p_{1}B_{i}$, the position of
piece 1, and the special piece at the origin. Here, $p_{1}M^{j}=p_{j+1}-p_{j}$
for $0\leq j<N-1$, so that

$p_{1}B_{i}=\sum_{j=0}^{i-1}p_{1}M^{j}=\sum_{j=0}^{i-1}(p_{j+1}-p_{j})=p_{i}.$

Therefore, the side length of the regular $(n+1)$-gon corresponding to the
configuration $PB_{i}$ is equal to $|p_{i}|$. This is the length of a proper
diagonal of the original configuration $P$ provided that $1<i<N-1$, so
strictly larger than original side length of $|p_{1}|$.

To complete the proof of Theorem 1.1, it is enough to observe that there
always exists an integer $i$ with $1<i<N-1,$ which is coprime to $N$, provided
that $N\geq 5$ and $N\neq 6$. $\Box$

##  5 Remarks and further questions.

In the present note, we defined a game with grasshoppers jumping over each
other and discussed when a configuration of the grasshoppers _can be reached_
from another configuration but we neglected the question of _how many jumps_
it takes to reach the desired configuration. Here, we list several problems
related to this latter question.

A.  The smallest special case of Theorem 1.1 is that of the regular pentagon.
One can implement the steps of the proof above to find a concrete sequence of
jumps for the grasshoppers starting at the vertices of a regular pentagon that
yields a larger regular pentagon, but the sequence so obtained is very long.
Here we give a much shorter sequence meeting the requirements. We number the
grasshoppers $0$ through $4$ and denote by $J_{ij}$ the jump of grasshopper
$i$ over grasshopper $j$. The following sequence of jumps results in a regular
pentagon that is $\sqrt{5}+2$ times larger than the original:

$J_{40}J_{43}J_{20}J_{32}J_{41}J_{12}J_{13}J_{31}J_{23}J_{13}J_{30}J_{24}J_{14}J_{40}$

We do not know whether there exists an even shorter sequence than this.

B.  The same question can be asked more generally:

######  Problem 5.1.

Given an integer $N$ which is either $5$ or larger than $6$, and $N$ pieces
sitting at the vertices of a regular $N$-gon, what is the smallest number of
legal moves that takes them into the vertex set of a larger regular $N$-gon?

How many legal moves are needed to turn a configuration consisting of the
vertices and the center of regular $N$-gon to a similar but larger
configuration? (A finite number of moves always suffice.)

We can turn to the proof of Theorem 1.1 to obtain an explicit bound, but this
bound will be unreasonably large in $N$ for two reasons. First, the
application of Lemma 2.1 may itself yield exponentially long sequences; see
more on this below. Second, in the proof of Theorem 1.2 we take an integer
matrix $A$ and raise it to a power which is the order of $A$ in $GL(n,2)$. But
$GL(n,2)$ has elements of order $2^{n}-1$.

######  Conjecture 5.2.

Every regular $N$-gon ($N>6$) can be transformed to a similar but larger
configuration in polynomially many moves in $N$.

C.  We can also ask how many legal jumps are needed to bring a given
configuration $P$ to another configuration $Q$ whenever this is possible. Here
we cannot hope for a bound that depends only on the number $N$ of pieces in
the configurations. Lemma 3.1 claims that if $P$ can be transformed to $Q$ at
all, then $Q=PA$ for an $(N-1)\times(N-1)$ matrix $A$ generated by the
elementary involutions. (Here we assume that both $P$ and $Q$ have a
stationary piece in the origin and we identify the configurations with
matrices as usual.) It would be interesting to bound the number of legal moves
needed in terms of $N$ and the maximum absolute value of an entry in $A$. This
is the same as asking how long a product of elementary transformations may be
needed to obtain a specific matrix with bounded entries.

As before, our proof of Lemma 3.1 can be turned into an explicit bound.
However, this bound will be exponential. The reason is that the algorithmic
proof of Lemma 2.1, turning a matrix into the identity matrix by a series of
admissible operations, is recursive. We do not know whether this is necessary.

D. What happens if we are given a single configuration of $N$ pieces which
comes with a guarantee that it can be transformed into a similar but larger
configuration using legal jumps? Can we bound the number of jumps needed
solely in terms of $N$?

E. And finally a question _not_ about the number of necessary jumps.

######  Problem 5.3.

For which Platonic solids $T$ can we start the above game at the vertices of
$T$ and arrive at a similar but larger configuration, using legal moves?

If $T$ is a tetrahedron, a cube or an octahedron, then this is clearly
impossible, because all vertices of these solids lie on a cubic lattice. Just
like in the case of the olympiad problem mentioned at the beginning of this
article, if we consider the smallest similar copy of $T$ whose vertices belong
to the integer lattice of side length $1$, we cannot end up with a smaller
configuration similar to $T$. By the reversibility of the moves, neither can
we arrive at a similar, but larger configuration.

We conjecture that starting from the vertices of either of the remaining two
Platonic solids, the dodecahedron or the icosahedron, one can arrive to a
similar but larger configuration by a series of legal moves.

Acknowledgement. We are grateful to Florestan Brunck for communicating this
problem to us. The authors, together with him, posed the question on the 2022
Miklós Schweitzer Competition for Hungarian undergraduates and MSc students.
This is arguably the most difficult mathematics contest of the world. The
participants have 10 days to solve 10 problems [10].

## References

  * [1] Albert, M.H., Nowakowski, R.J., Wolfe, D. (2007). _Lessons in Play: An Introduction to Combinatorial Game Theory_. Natick, MA: A. K. Peters Ltd.
  * [2] Berlekamp, E., Conway, J.H., Guy, R. (2001-2004). _Winning Ways for your Mathematical Plays, 2nd ed._ , Natick, MA: A. K. Peters Ltd.
  * [3] Brunck, F (April 2002). Personal communication.
  * [4] Dumitrescu, A., Suzuki, I., Yamashita, M. (2004). Motion planning for metamorphic systems: feasibility, decidability, and distributed reconfiguration. _IEEE Transactions on Robotics and Automation_ 20(3):409–418.
  * [5] Galor, O. (2007). _Discrete Dynamical Systems_. Berlin: Springer-Verlag.
  * [6] Hardy, G.H., Wright, E.M. (2008). _An Introduction to the Theory of Numbers,_ 6th ed., Oxford: Oxford University Press.
  * [7] Johnston, N., Greene, D. (2022). _Conway’s Game of Life: Mathematics and Construction_. Available online.
  * [8] Fedorov, R.M., Kanel’-Belov, A.Ya., Kovaldzhi, A.K., Yaschenko, I.V. (2006). _Moskovskiye Matematicheskiye Olympiady, 1993-2005 g._ , 1994. Grade 8, Problem 4, p. 23, Moscow: Izdatel’stvo MCNMO. In Russian.
  * [9] Schiff, J.L. (2008). _Cellular Automata–A Discrete View of the World_. Hoboken, NJ: John Wiley & Sons.
  * [10] Székely, G.J., ed. (1995). _Contests in Higher Mathematics: Miklós Schweitzer Competitions, 1962–1991_. New York, NY: Springer-Verlag.
  * [11] Wolfram, S. (2002). _A New Kind of Science_. Champaign, IL: Wolfram Media.