# Depolarization of MgH Solar Lines by Collisions with Hydrogen Atoms

Saleh Qutub Astronomy & Space Science Dept, Faculty of Science, King Abdulaziz
University, Jeddah, Saudi Arabia  Yulia Kalugina Department of Optics and
Spectroscopy, Tomsk State University, 36 Lenin av., Tomsk 634050, Russia
Institute of Spectroscopy, Russian Academy of Sciences, Fizicheskaya St. 5,
108840 Troitsk, Moscow, Russia  Moncef Derouich Astronomy & Space Science
Dept, Faculty of Science, King Abdulaziz University, Jeddah, Saudi Arabia

(Received 2021 February 15; Revised 2021 May 27; Accepted 2021 May 27)

###### Abstract

Interpretations of the very rich second solar spectrum of the MgH molecule
face serious problems owing to the complete lack of any information about
rates of collisions between the MgH and hydrogen atoms. This work seeks to
begin the process of filling this lacuna by providing, for the first time,
quantum excitation, depolarization, and polarization transfer collisional
rates of the MgH ground state $X^{2}\Sigma$. To achieve the goals of this
work, potential energy surfaces are calculated and then are included in the
Schrödinger equation to obtain the probabilities of collisions and, thus, all
collisional rates. Our rates are obtained for temperatures ranging from
$T\\!\\!=$2000 K to $T\\!\\!=$15,000 K. Sophisticated genetic programming
methods are adopted in order to fit all depolarization rates with useful
analytical functions of two variables: the total molecular angular momentum
and temperatures. We study the solar implications of our results, and we find
that the $X^{2}\Sigma$ state of MgH is partially depolarized by isotropic
collisions with neutral hydrogen in its ground state ${}^{2}S$. Our findings
show the limits of applicability of the widely used approximation in which the
lower-level polarization is neglected. _Unified Astronomy Thesaurus concepts_
: Solar physics (1476); Solar atmosphere (1477); Solar magnetic fields (1503)

##  1 Introduction

Linear polarization, formed by scattering of anisotropic radiation and
measured by observing the limb of the Sun, is called second solar spectrum
(SSS). Numerical simulations of the SSS, stimulated by current and future
spectropolarimetric projects, have opened new windows especially into the
field of the quiet Sun’s magnetism (e.g., Bellot Rubio & Orozco Suárez 2019).
The preparation of these projects and their scientific exploitation require
collisional molecular data to be included in the coupled set of the radiative
transfer equations and the statistical equilibrium equations (SEEs) for
modeling the formation of the SSS.

The interest of molecular spectral lines observed in the SSS is twofold:
first, they are in general optically thin lines, which facilitates modeling
the formation of their polarization since the radiative transfer problem is
less complicated when the line is optically thin. Second, each molecular
multiplet contains numerous lines with different magnetic sensitivities (i.e.,
with sufficiently different Landé g-factors) in a narrow spectral window that
allows a multiline determination of the magnetic field, a technique known as
the “differential Hanle effect” (e.g., Berdyugina & Fluri 2004; Asensio Ramos
& Trujillo Bueno 2005; Bommier et al. 2006).

Nevertheless, different analyses (e.g., Berdyugina & Fluri 2004; Asensio Ramos
& Trujillo Bueno 2005; Bommier et al. 2006) have obtained a value of $\sim$
7-15 G for the photospheric turbulent magnetic field, which is clearly
different from the value obtained by analyzing observations of the line
polarization of Sr I $\lambda$4607 Å ($\sim$ 40 G; e.g., Derouich et al.
2006). This difference seems to be due to the fact that collisions were
usually neglected in the case of molecules as the molecular collisional rates
are completely unknown. Therefore, a better understanding of the SSS of
molecules, and consequently a more accurate determination of the solar
magnetic field, requires a precise determination of molecular collisional
depolarization and transfer of polarization rates.

In particular, the scattering polarization of MgH is one of the most prominent
features of the SSS (e.g., Mohan Rao & Rangarajan 1999; Gandorfer 2000;
Faurobert & Arnaud 2003; Asensio Ramos & Trujillo Bueno 2005; Bommier et al.
2006; Milić & Faurobert 2012). MgH polarized lines must be analyzed in a
comprehensive way to uncover important mysteries of the SSS and to address
controversies surrounding Hanle effect diagnostics of turbulent magnetic
fields at subtelescopic scales (e.g., Bellot Rubio & Orozco Suárez 2019).
Interpretation of the MgH polarized lines is difficult and incomplete because
the Hanle effect and the effect of isotropic collisions are mixed in the same
observable (the polarization state; Mohan Rao & Rangarajan 1999; Asensio Ramos
& Trujillo Bueno 2005; Bommier et al. 2006).

Our intention in this work is to provide new (de-)excitation, depolarization,
and polarization transfer rates for the MgH molecule in its ground state
$X^{2}\Sigma$ owing to collisions with the hydrogen atom, H. These rates are
very important in SSS studies. Computations of quantum collisional rates occur
in two steps: (1) determination of potential energy surfaces (PESs) for
interaction of MgH and H, and (2) study of the collisional dynamics by solving
the Schrödinger equation with these PESs. Reliable PESs for the interaction
between H(${}^{2}S$) and MgH($X^{2}\Sigma^{+}$) were obtained by Ben Abdallah
et al. (2009). A thorough theoretical investigation of interaction potentials
was carried out there, and the surfaces were represented in terms of Legendre
polynomials. As a confirmation of the result of Ben Abdallah et al. (2009), we
have performed additional calculation of the PESs of the MgH-H system with
higher resolution. As we show below, our PESs are in very good agreement with
those of Ben Abdallah et al. (2009). Nevertheless, our PESs are more accurate
for radial separation larger than 9 $a_{0}$.

The treatment of the collision dynamics was made possible thanks to the
MOLSCAT code (Hutson & Green 1994). The infinite-order-sudden (IOS)
approximation is adopted to compute (de-)excitation, depolarization, and
polarization transfer cross sections for kinetic energies ranging from 50 to
37000 cm-1 and for the first 70 rotational levels. This allows us to calculate
the corresponding rates for temperatures between 2000 and 15,000 K 111The data
can be found at 10.5281/zenodo.4694455. Sophisticated genetic programming (GP)
codes are used to infer analytical expressions depending on the temperature
and total molecular angular momentum by fitting our collisional data (see
Derouich et al. 2015). From the GP expressions, one can obtain depolarization
collisional rates with accuracy better than 5%. We study in some detail the
solar implications of our results.

##  2 Theoretical Background

We study the effects of isotropic collision of the MgH in the
${}^{2}\Sigma^{+}$ state with the hydrogen atom in its ground state ${}^{2}S$.
We describe the MgH levels in Hund’s limiting case (b). Molecular quantum
numbers are denoted by $j$ and $N$, where $j$ is the total angular momentum
and $N$ is the rotational angular momentum related to $j$ by
$\vec{j}\\!=\\!\vec{N}\\!+\\!\vec{S}_{MgH}$ where $S_{MgH}\\!=\\!1/2$ is the
spin of MgH. Therefore, $j\\!=\\!N\\!\pm\\!1/2$. The spin of the hydrogen is
$S_{H}\\!=\\!1/2$; thus, the collision results in producing a singlet state
${}^{1}A^{\prime}$ with total spin $S_{tot}\\!=\\!0$ and a triplet state
${}^{3}A^{\prime}$ with $S_{tot}\\!=\\!1$.

The SSS of MgH molecule is quantified by using the density matrix formalism
expressed on the basis of irreducible tensor operators (ITOs), which has been
introduced by Fano (1957) and then adopted in solar physics by many authors
(e.g., Sahal-Bréchot 1977; Trujillo Bueno 2001; Landi Degl’Innocenti &
Landolfi 2004). In the ITOs basis, the density matrix elements are denoted by
$\rho_{q}^{k}(j)$ with a tensorial order $0\\!\leqslant\\!k\\!\leqslant\\!2j$
and a coherence number $-k\\!\leqslant\\!q\\!\leqslant\\!k$. The state of the
radiation emitted by the MgH molecule can be obtained by knowing the
$\rho_{q}^{k}(j)$. In fact, intensity, circular polarization, and linear
polarization are associated with the $\rho_{q}^{k}(j)$ elements of order $k$ =
0, $k$ odd integer (i.e. $k$=1, 3, 5, etc.), and $k$ even integer (i.e. $k$=2,
4, 6, etc.), respectively. The contribution of collisions to the evolution of
the density matrix $\rho$ is given by the following rate equations:

$\displaystyle\Big{(}\frac{d\;^{j}\rho_{q}^{k}}{dt}\Big{)}_{coll}$
$\displaystyle\\!=\\!$ $\displaystyle-D^{k}(j,T)\;^{j}\rho_{q}^{k}$
$\displaystyle\\!-^{j}\rho_{q}^{k}\\!\sum_{j^{\prime}\neq
j}\\!\sqrt{\frac{2j^{\prime}+1}{2j+1}}D^{0}(j\\!\to\\!j^{\prime},T)$
$\displaystyle\\!+\\!\sum_{j^{\prime}\neq
j}\\!D^{k}(j^{\prime}\\!\to\\!j,T)\;^{j^{\prime}}\rho_{q}^{k}\,.$

$D^{k}(j,T)$ are the depolarization rates of the $j$-level due to purely
elastic collisions, and $D^{k}(j\\!\to\\!j^{\prime},T)$ are the rates of
polarization transfer between the $j$ and $j^{\prime}$ levels.

Note that apart from the multiplicity factor
$\sqrt{(2j^{\prime}\\!+\\!1)/(2j\\!+\\!1)}$, the $C^{k}(j,j^{\prime})$ denoted
by Landi Degl’Innocenti & Landolfi (2004) become the collisional transfer
rates $D^{k}(j^{\prime}\\!\to\\!j)$ defined here and in Sahal-Bréchot (1977)
and adopted by Derouich et al. papers (e.g. Derouich et al. 2003 and Derouich
2006). One can refer to Derouich & Ben Abdallah 2009 for more details about
the origin of the multiplicity factor
$\sqrt{(2j^{\prime}\\!+\\!1)/(2j\\!+\\!1)}$. We emphasize that, after plugging
in all collisional rates, the final collisional rate equations,
$({d\;^{j}\rho_{q}^{k}}/{dt})_{coll}$, become exactly the same in both
conventions. The collisional rates are obtained through integration of cross-
sections $\sigma^{k}$ over Maxwellian distribution of relative velocities
(e.g. Derouich 2006). In addition,

$\displaystyle
D^{k}(j,T)\\!=\\!D^{0}(j\\!\to\\!j,T)\\!-\\!D^{k}(j\\!\to\\!j,T),$ (2)

which implies that $D^{0}(j)\\!=\\!0$.

We use the approach of Corey & Alexander (1985) and Corey et al. (1986) to
obtain expressions for the polarization transfer cross-sections
$\sigma^{k}(j\\!\to\\!j^{\prime},E)$ and depolarization cross-sections
$\sigma^{k}(j,E)$. In addition, the IOS approximation is adopted which can be
well justified especially for sufficiently high temperatures (see e.g. Lique
et al. 2007). In these conditions, the $\sigma^{k}$ adopted in this work are
given, for example, by Eq. (1) of Qutub et al. (2020). The total collisional
rates averaged over spin can then be calculated via the relation (Corey &
Alexander 1985):

$\displaystyle D^{k}(j\to j^{\prime},T)$ $\displaystyle=$
$\displaystyle\frac{1}{4}\,\big{[}3\,D^{k}(j\to
j^{\prime},T;\;^{3}A^{\prime})$ (3) $\displaystyle+D^{k}(j\to
j^{\prime},T;\;^{1}A^{\prime})\big{]}\,.$

##  3 Potential Energy Surfaces

Figure 1: Two-dimensional PES for ${}^{1}A^{\prime}$ state (left panel) and
${}^{3}A^{\prime}$ state (right panel). Energy is in cm-1.

We adopt the coordinate system of Jacobi ($R$, $r_{MgH}$, $\theta$) for the
calculation of PESs. Here $R$ represents the distance from the center of mass
of the MgH molecule to the H atom, and $\theta$ is the rotation angle of the H
atom around the MgH. The MgH molecule is assumed to be rigid with Mg-H
distance frozen at its equilibrium value $r_{MgH}$ = 3.2692 $a_{0}$ (Rosen
1970).

Accurate ab initio computations of the PESs for the ${}^{1}A^{\prime}$ and
${}^{3}A^{\prime}$ states are performed in the internally contracted
multireference configuration interaction level of theory (Werner & Knowles
1988). Partial size consistency is corrected by following the Davidson (+Q)
correction (Davidson & Silver 1977). The remaining correction is made by
subtracting the energy at $R$=100 $a_{0}$. The five lowest orbitals of the Mg
atom were kept frozen. The active space consists of four electrons distributed
in six active orbitals. The augmented correlation-consistent triple zeta (V5Z)
basis set (Dunning 1989) for Mg and the VQZ basis set for the H atoms were
used. All the PESs are obtained using the MOLPRO package (e.g., Werner et al.
2010).

For the ${}^{1}A^{\prime}$ state the $R$ values were varied from 1.75 to 50
$a_{0}$, giving 55 grid points. For the ${}^{3}A^{\prime}$ state the $R$
values were varied from 2.0 to 50 $a_{0}$, with a total of 61 grid points. We
used a variable step in angle $\theta$ in order to cover the complex behavior
of both PESs. The total number of ab initio points is 3300 for the singlet
state and 3294 for the triplet state. We checked the energy convergence for
more problematic regions (0∘–20∘ and 150∘–180∘) by taking different starting
points for ab initio calculations. For ${}^{1}A^{\prime}$ and
${}^{3}A^{\prime}$ potentials, the 2D spline was employed. This allows us to
avoid fitting errors.

The resulting PESs for the ${}^{1}A^{\prime}$ and ${}^{3}A^{\prime}$
electronic states are shown in Figure 1. For the singlet state, there are two
minima on the PES associated with the formation of HMgH and MgHH molecules.
The HMgH arrangement corresponds to the minimal structure with
$\theta\\!=\\!180^{\circ}$ and $R\\!=\\!3.36$ $a_{0}$ and has the well depth
$E\\!=\\!-25531.5$ cm-1. The minimum compares well with the
$E\\!=\\!-25561.55$ cm-1 at $R\\!=\\!3.40$ $a_{0}$ obtained by Ben Abdallah et
al. (2009). The MgHH minimal structure corresponds to $\theta\\!=\\!0^{\circ}$
and $R=$4.59 $a_{0}$ and has a well depth $E\\!=\\!-18791.2$ cm-1 (compared to
$E\\!=\\!-19642.06$ cm-1 at $R\\!=\\!4.60$ $a_{0}$ of Ben Abdallah et al.
2009). The minimum for the triplet state occurs at $R\\!=\\!3.45$ $a_{0}$,
$\theta\\!=\\!26^{\circ}\\!\\!.99$ and has an energy $E\\!=\\!-6531.3$ cm-1
(compared to $E\\!=\\!-6758.80$ cm-1 at $R$=3.2 $a_{0}$ and
$\theta\\!=\\!33^{\circ}$ of Ben Abdallah et al. 2009).

##  4 Results and Discussions

###  4.1 Depolarization Rates

Figure 2: Variation with $j$ (left panel) and with $T$ (right panel) of the
collisional depolarization rates for $k\\!=\\!1$ (open circles) and
$k\\!=\\!2$ (open triangles). The dashed and solid curves show the GP fit
values obtained using Equations (4) and (5), respectively.

In Figure 2, we show the variation of collisional depolarization rates for the
orientation, $k\\!=\\!1$ (open circles), and the alignment, $k\\!=\\!2$ (open
triangles), as a function of $j$ at $T\\!=\\!6000$ K in the left panel and as
a function of $T$ for the level $N_{j}\\!=\\!5_{5.5}$ in the right panel. As
one would expect, the collisional depolarization rates increase with
temperature (roughly $D^{1},D^{2}\\!\propto\\!T^{0.34}$ for the given level)
and decrease with increasing $j$ (roughly $D^{1}\\!\propto\\!j^{-0.78}$ and
$D^{2}\\!\propto\\!j^{-0.70}$ for the given temperature) as the energy
separation between rotational levels decreases with increasing $j$.

It is clear from Figure 2 that the depolarization rates with tensorial order
$k\\!=\\!2$ are larger than those with tensorial order $k\\!=\\!1$. Using GP
fitting techniques, we obtain the following relations, which represent the
depolarization rates in the temperature range 2000 – 15,000 K and for total
angular momentum up to 50.5 with error less than 5%:222Separate fits for the
singlet and triplet contributions are also available from the authors upon
request.

$\displaystyle\frac{D^{1}(j,T)}{n_{\rm
H}\\!\\!\times\\!\\!10^{-10}}\\!\\!=\\!\\!\frac{0.0004582j^{3.9722}T^{0.41185}\\!\\!-\\!0.0005562j^{3.9806}T^{0.398}\\!\\!+\\!1.23653j^{0.19053}T^{0.000014}\\!\\!-\\!10.4679j^{0.02168}\\!\\!+\\!9.2281}{15.5575\frac{j^{4.52315}}{T^{0.518178}}\\!\\!-\\!1.58\\!\times\\!10^{-8}j^{6.79}T^{0.326}\\!\\!-\\!7.2\\!\times\\!10^{-16}j^{4.786}T^{2.69}\\!\\!-\\!15.2825\frac{j^{4.5256}}{T^{0.51576}}\\!\\!-\\!\frac{0.024}{T^{0.36}}},$
(4) $\displaystyle\frac{D^{2}(j,T)}{n_{\rm
H}\\!\\!\times\\!\\!10^{-10}}\\!\\!=\\!\\!\frac{0.0005\\!+\\!15.5158\frac{T^{0.00011}}{j^{1.5021}}\\!\\!+\\!\frac{0.048}{j^{3.26}T^{0.014}}\\!\\!-\\!\frac{15.56}{j^{1.50455}}}{7\\!\times\\!10^{-10}j^{2.634}T^{0.49}\\!\\!+\\!0.046\frac{j^{1.045}}{T^{0.84}}\\!\\!+\\!4.516\\!\times\\!10^{-7}\frac{T^{1.1984}}{j^{0.0017}}\\!\\!+\\!\frac{0.0352}{j^{0.079}T^{0.22}}\\!\\!-\\!6.544\\!\times\\!10^{-7}T^{1.161}}.$
(5)

The dashed and solid curves in Figure 2 represent the GP fit values calculated
using Equations (4) and (5), respectively, which are in very good agreement
with the directly calculated rates.

###  4.2 (De-)excitation and Transfer of Polarization Rates

Figure 3: Variation of the collisional transfer rates for $k\\!=\\!0$,
$k\\!=\\!1$, and $k=2$ as functions of $j$ (left panel) for
$j^{\prime}\\!-\\!j\\!=\\!1$ and $T\\!=\\!6000$ K and as functions of
$j^{\prime}\\!-\\!j$ for the level $N_{j}\\!=\\!5_{5.5}$ and $T\\!=\\!6000$ K.
The dotted, dashed, and solid curves in the left panel show the GP fit values
obtained using Equations (4.2)–(8), respectively.

We now turn our attention to the (de-)excitation and polarization transfer
rates. In Figure 3, we show the variation with $j$ in the left panel (for
$j^{\prime}\\!-\\!j\\!=\\!1$ and $T\\!=\\!6000$ K) and with
$j^{\prime}\\!-\\!j$ in the right panel (for $N_{j}\\!=\\!5.5$ and
$T\\!=\\!6000$ K) of the upward transfer of population $k\\!=\\!0$ and of
polarization $k\\!=\\!1,2$ collisional rates. Note that the collisional
(de-)excitations rates, $C(j\\!\to\\!j^{\prime})$, are related to the rates of
transfer of population due to collisions, $D^{0}(j\\!\to\\!j^{\prime})$, via
the relation
$C(j\\!\to\\!j^{\prime})\\!=\\!\sqrt{(2j^{\prime}\\!+\\!1)/(2j\\!+\\!1)}\,D^{0}(j\\!\to\\!j^{\prime})$
(e.g. Derouich 2006). One can see from the left panel of Figure 3 that the
transfer rates increase with increasing $j$ as the energy difference between
levels decreases with $j$: $D^{0}(j\\!\to\\!j\\!+\\!1)\\!\propto\\!j^{-0.11}$,
$D^{1}(j\\!\to\\!j\\!+\\!1)\\!\propto\\!j^{-0.18}$, and
$D^{2}(j\\!\to\\!j\\!+\\!1)\\!\propto\\!j^{-0.37}$ roughly upto $j\\!=\\!15$
for the case at hand. For the same reason the collisional transfer rates
decrease with increasing $|j^{\prime}\\!-\\!j|$ (see the right panel of Figure
3): roughly
$D^{0}(j\\!\to\\!j^{\prime})\\!\propto\\!|j^{\prime}\\!-\\!j|^{-1.1}$,
$D^{1}(j\\!\to\\!j^{\prime})\\!\propto\\!|j^{\prime}\\!-\\!j|^{-1.2}$, and
$D^{2}(j\\!\to\\!j^{\prime})\\!\propto\\!|j^{\prime}\\!-\\!j|^{-1.3}$ for the
given case. As one would expect, the collisional transfer rate with
$|j^{\prime}\\!-\\!j|\\!=\\!1$ are dominant, as can be seen from the right
panel of Figure 3. Therefore, by using GP fitting techniques, we obtain the
following relations, which represent the collisional transfer rates with
$j^{\prime}\\!-\\!j\\!=\\!1$ in the temperature range 2000 – 15,000 K and for
total angular momenta up to 50.5 with maximum error less than 1%:333Separate
fits for the singlet and triplet collisional transfer rates, in addition to
fits for the collisional transfer rates with $j^{\prime}\\!-\\!j\\!>\\!1$, are
available from the authors upon request.

$\displaystyle\frac{D^{0}(j\\!\to\\!j\\!+\\!1,T)}{n_{\rm
H}\\!\\!\times\\!\\!10^{-10}}\\!=\\!\frac{1.82599342j^{0.72733479}T^{0.000035887}\\!\\!+\\!2.23672898\frac{j^{0.72827942}}{T^{0.000028873}}\\!\\!+\\!2129.2\frac{j^{0.3877}}{T^{1.9607}}\\!\\!-\\!4.06270986j^{0.727856143}\\!\\!-\\!6.4\\!\times\\!10^{-6}}{3.42\\!\times\\!10^{-9}j^{0.389}T^{0.662}\\!\\!+\\!0.02708\frac{j^{0.19}}{T^{0.9462}}\\!\\!+\\!\frac{825}{j^{0.252}T^{2.1375}}\\!\\!+\\!6680\frac{j^{0.402}}{T^{2.311}}\\!\\!-\\!\frac{0.0563}{T^{1.051}}},$
(6) $\displaystyle\frac{D^{1}(j\\!\to\\!j\\!+\\!1,T)}{n_{\rm
H}\\!\\!\times\\!\\!10^{-10}}\\!=\\!\frac{317.35\frac{j^{2.2305}}{T^{0.855}}\\!\\!+\\!2.118\frac{j^{1.2645}}{T^{0.03446}}\\!\\!+\\!3.347\\!\times\\!10^{-9}j^{2.1953}T^{1.812}\\!\\!-\\!2.619j^{0.2628}\\!\\!+\\!1.8358}{1.56\\!\times\\!10^{-11}j^{1.414}T^{2.2627}\\!\\!+\\!1.35\\!\times\\!10^{-10}j^{2.2524}T^{1.9059}\\!\\!+\\!21\frac{j^{1.2844}}{T^{0.4977}}\\!\\!+\\!959.7\frac{j^{2.2353}}{T^{1.19094}}\\!\\!-\\!\frac{332109}{T^{2.31}}},$
(7) $\displaystyle\frac{D^{2}(j\\!\to\\!j\\!+\\!1,T)}{n_{\rm
H}\\!\\!\times\\!\\!10^{-10}}\\!=\\!\frac{3.16488j^{3.08986}T^{0.000001128}\\!\\!+\\!3.18179j^{0.000029}T^{0.00000074}\\!\\!-\\!3.16486j^{3.08986}\\!\\!-\\!0.002713\frac{j^{2.8955}}{T^{0.4695}}\\!\\!-\\!3.18176}{1.52\\!\times\\!10^{-15}j^{2.849}T^{2.206}\\!\\!+\\!0.002613\frac{j^{2.8175}}{T^{0.5484}}\\!\\!+\\!0.00521\frac{j^{1.076}}{T^{0.503}}\\!\\!+\\!4.6\\!\times\\!10^{-17}j^{1.066}T^{2.677}\\!\\!-\\!\frac{0.21}{T^{1.165}}}.$
(8)

The dotted, dashed, and solid curves in the left panel of Figure 3 represent
the GP transfer rates calculated using Equations (4.2)–(8), respectively,
which agree extremely well with the original rates. The GP analytical
functions given in Equations (4.2)–(8) can be implemented in the numerical
codes calculating the theoretical polarization to generate the rates for any
$j$ and $T$ values.

We remark that the collisional transfer rates have similar behavior with
temperature to the collisional depolarization rates. Downward collisional
transfer rates exhibit a similar behavior with $j$ and $T$ to the upward
transfer rates. In fact, for isotropic collisions, which is the case under
consideration, one has (e.g., Derouich et al. 2007)

$\displaystyle
D^{k}(j_{u}\\!\to\\!j_{\ell},T)\\!=\\!\frac{2j_{\ell}\\!+\\!1}{2j_{u}\\!+\\!1}\exp\\!\left(\\!\frac{\Delta
E_{j_{u},j_{\ell}}}{k_{\rm B}T}\\!\right)\\!D^{k}(j_{\ell}\\!\to\\!j_{u},T),$

with $\Delta E_{j_{u},j_{\ell}}$ being the energy difference between the upper
$j_{u}$ and lower $j_{\ell}$ levels and $k_{\rm B}$ being the Boltzmann
constant.

It is interesting to note that for the MgH molecule and other molecules such
as the CN (Qutub et al. 2020), collisional depolarization rates are
significantly smaller than collisional transfer rates. It is also worth noting
that the collisional depolarization and transfer rates are larger for the MgH
molecule as compared to those of the CN molecule. This is due to the MgH
molecule being more asymmetric than the CN molecule.

###  4.3 On the Accuracy of the Collisional Rates

There are no experimental or other theoretical values of depolarization and
polarization transfer rates associated with MgH solar lines to compare with.
In addition, as far as we know, neither experimental nor theoretical work is
being currently performed to provide detailed collisional data that would
enable a quantitative analysis of the MgH polarization. This work is a first
step toward complete determination of the MgH depolarization and polarization
transfer rates.

We use up-to-date quantum methods to calculate new PESs and to solve the
collision dynamics allowing the calculation of the rate coefficients. The IOS
approximation (e.g., Goldflam et al. 1977; Parker & Pack 1978) used in this
work is known to be sufficiently precise for solar temperatures (e.g.,
Derouich & Ben Abdallah 2009). Our quantum collisional rates should be
sufficiently accurate for solar applications.

###  4.4 Solar Implications

Table 1: Comparison of the Inverse Lifetime $\frac{1}{t_{life}}$=$B_{\ell
u}I(\lambda)$ of the MgH $X^{2}\Sigma$ State to Its Linear Depolarization
Rates $D^{2}$

$\lambda_{u\ell}\,(\mbox{\AA})$ | $N_{\ell}$ | $j_{\ell}$ | $I(\lambda_{u\ell})\,(10^{-5}{\rm erg}$ | $A_{u\ell}$ | $B_{\ell u}I(\lambda_{u\ell})$ | $\omega_{L}|g_{j_{\ell}}|\,(10^{7}{\rm s}^{-1})$ | $D^{2}(N_{\ell}j_{\ell},T\\!=\\!5778~{}\rm{K})\ (10^{5}{\rm s}^{-1})$
---|---|---|---|---|---|---|---
|  |  | ${\rm cm}^{-2}\,{\rm s}^{-1}{\rm sr}^{-1}{\rm Hz}^{-1})$ | $(10^{7}{\rm s}^{-1})$ | $(10^{5}{\rm s}^{-1})$ | ${\rm B}\\!=\\!10{\rm G}$ | ${\rm B}\\!=\\!100{\rm G}$ | $n_{\rm H}\\!=\\!10^{15}{\rm cm}^{-3}$ | $n_{\rm H}\\!=\\!10^{16}{\rm cm}^{-3}$
$5170.574$ | 12 | 11.5 | $2.84645$ | $1.99441$ | $1.97524$ | $0.70353$ | $7.03530$ | $0.52392$ | $5.23920$
$5171.012$ | 12 | 12.5 | $2.75250$ | $1.99977$ | $1.91567$ | $0.70353$ | $7.03530$ | $0.49026$ | $4.90260$
$5174.895$ | 10 | 9.5 | $2.89082$ | $1.98276$ | $1.99932$ | $0.83753$ | $8.37530$ | $0.60793$ | $6.07930$
$5175.419$ | 10 | 10.5 | $2.91406$ | $1.98974$ | $2.02310$ | $0.83753$ | $8.37530$ | $0.56288$ | $5.62880$
$5176.816$ | 9 | 8.5 | $2.88194$ | $1.97566$ | $1.98825$ | $0.92569$ | $9.25690$ | $0.65950$ | $6.59500$
$5178.503$ | 8 | 7.5 | $2.94770$ | $1.97052$ | $2.03031$ | $1.03460$ | $10.34600$ | $0.71797$ | $7.17970$
$5179.994$ | 7 | 6.5 | $1.54633$ | $1.95580$ | $1.05803$ | $1.17255$ | $11.72550$ | $0.78215$ | $7.82150$
$5180.593$ | 7 | 7.5 | $2.87995$ | $1.96892$ | $1.98444$ | $1.17255$ | $11.72550$ | $0.71797$ | $7.17970$
$5181.307$ | 6 | 5.5 | $2.31560$ | $1.93665$ | $1.57007$ | $1.35294$ | $13.52940$ | $0.84786$ | $8.47860$
$5181.930$ | 6 | 6.5 | $2.60932$ | $1.95880$ | $1.79011$ | $1.35294$ | $13.52940$ | $0.78215$ | $7.82150$

Note. Also compared is $B_{\ell u}I(\lambda)$ with the values
$(\omega_{L}|g_{j_{\ell}}|)^{-1}$ that estimate the Hanle depolarization.

Let us briefly highlight the importance of our collisional rates for solar
spectropolarimetry. Rotational levels of the electronic ground state of the
solar MgH molecule, $X^{2}\Sigma$, can be polarized owing to the anisotropy of
the incident radiation. This polarization could either be transferred to the
MgH upper electronic states via radiative absorption, hence contributing to
polarization of the emitted radiation, or get destroyed by isotropic
collisions. This is usually quantified by solving the full set of coupled SEEs
governing the population and polarization of different atomic or molecular
levels taking into account all the intervening processes. However, this goes
beyond the scope of this work.

Nevertheless, for the purpose of exploring the possible effect of collisions
on the MgH ground-state depolarization, it is sufficient to compare the
radiative transfer rates due to absorption for the rotational levels of the
MgH electronic ground state, $B_{\ell u}I(\lambda_{u\ell})$ (which determine
lifetimes of the levels of the electronic ground state, $t_{\rm
life}^{-1}\\!=\\!B_{\ell u}I(\lambda_{u\ell})$), with the corresponding
collisional depolarization rates, $D^{k}(j_{\ell})$. Here $I(\lambda_{u\ell})$
denotes the intensity of light of wavelength $\lambda_{u\ell}$ at the center
of the solar disk incident on the MgH molecules, and $B_{\ell
u}\\!=\\!(g_{u}/g_{\ell})(c^{2}/2h\nu_{u\ell}^{3})A_{u\ell}$ is the Einstein
absorption coefficient, with $A_{u\ell}$ being the Einstein coefficient for
spontaneous emission, $g_{u}$ and $g_{\ell}$ the multiplicity of upper and
lower levels, $h$ Planck’s constant, and $c$ the speed of light. For
concreteness, we contrast the collisional linear depolarization rates of the
state $X^{2}\Sigma$, $D^{2}(j_{\ell})$, calculated at the effective
photospheric temperature, $T\\!=\\!5778$ K, and for the typical photospheric
density of hydrogen: $n_{H}\\!=\\!10^{15}\\!-\\!10^{16}$ cm-3, with the
corresponding radiative absorption rates, $B_{\ell u}I(\lambda_{u\ell})$, for
some representative lines of the $A^{2}\Pi-X^{2}\Sigma$ system of MgH.

We display the values of both $D^{2}(j_{\ell})$ and $B_{\ell
u}I(\lambda_{u\ell})$ for selected lines in Table 1. The values of the core
relative intensity of the selected lines were obtained from Delbouille et al.
(1972), and the corresponding values of the absolute continuum were determined
by interpolation from the data of Allen (1976). The values of the Einstein
$A_{u\ell}$ coefficients were taken from Bommier et al. (2006).

From Table 1, one can see that for both $n_{H}\\!=\\!10^{15}{\rm cm}^{-3}$ and
$10^{16}{\rm cm}^{-3}$, $D^{2}(j_{\ell})$ is comparable to $B_{\ell
u}I(\lambda)$. This implies that the $X^{2}\Sigma$ sate of MgH cannot be
completely depolarized by collisions. Hence, one has to take into account the
lower-level polarization when solving the SEEs to calculate the polarization
of observed lines. This is an important result since previously the lower-
level polarization was neglected by assuming that it is completely depolarized
by collisions (Mohan Rao & Rangarajan 1999; Asensio Ramos & Trujillo Bueno
2005; Bommier et al. 2006).

We also consider the Hanle effect due to turbulent magnetic field on the
polarization of the MgH ground state, $X^{2}\Sigma$. The Hanle effect is
important only if $t_{\rm life}$ of the considered level [$t_{\rm
life}\\!=\\!(B_{\ell u}I(\lambda_{u\ell})^{-1}$ for the ground state] is
comparable to $(\omega_{L}|g_{j}|)^{-1}$, where
$\omega_{L}\\!=\\!8.79\\!\times\\!10^{6}$ B is Larmor angular frequency, with
B being the magnetic field strength in gauss.

In Table 1, we display values of $\omega_{L}|g_{j_{\ell}}|$ calculated at
${\rm B}\\!=\\!10\;{\rm G}$ and ${\rm B}\\!=\\!100\;{\rm G}$. One can see that
$\omega_{L}|g_{j_{\ell}}|\\!\gg\\!B_{\ell u}I$ in all cases, which implies
that for typical values of the photospheric turbulent magnetic field $\sim
10-100$ G the saturation regime of the Hanle effect on linear polarization of
MgH $X^{2}\Sigma$ is reached.

##  5 Conclusion

We provide (de-)excitation, depolarization, and polarization transfer rates of
the MgH $X^{2}\Sigma$ state by collisions with neutral hydrogen in its
${}^{2}S$ ground state. These rates are important for precise interpretation
of MgH blue lines in the SSS. A detailed discussion of the results is
presented and general trends of the collisional rates are given so as to gain
some understanding about the completely unknown role of collisions on the
polarization of other molecules. We obtain useful variation laws of the
depolarization rates with the temperature and the total angular momentum.
Important solar implications of our findings are pointed out.

## Acknowledgements

This research work was funded by the Institutional Fund Projects under grant
No. (IFPHI-179-130-2020). Therefore, authors gratefully acknowledge technical
and financial support from the Ministry of Education and King Abdulaziz
University, DSR, Jeddah, Saudi Arabia.

## References

  * (1) Allen, C. W., 1976, Astrophysical Quantities, (3rd ed., London: Athlone)
  * (2) Asensio Ramos, A. & Trujillo Bueno, J., 2005, ApJL, 635, 109
  * (3) Bellot Rubio, L. & Orozco Suárez, D., 2019, LRSP, 16, 1
  * (4) Ben Abdallah, D., Najar, F., Jaidane, N., et al., 2009, CPL, 473, 39
  * (5) Berdyugina, S. V. & Fluri, D. M., 2004, A&A, 417, 775
  * (6) Bommier, V., Landi Degl’Innocenti, E., Feautrier, N., & Guillaume, M., 2006, A&A, 458, 625
  * (7) Corey, G. C., & Alexander, M. H., 1985, JChPh, 83, 5060
  * (8) Corey, G. C., Alexander, M. H., & Dagdigian, P. J., 1986, JChPh, 84, 1547
  * (9) Davidson, E. R. & Silver, D. W., 1977, CPL, 52, 403
  * (10) Delbouille, L., Neven, L., & Roland, G., 1972, BASS2000 Solar Survey Archive, http://bass2000.obspm.fr/solar_spect.php
  * (11) Derouich, M., 2006, A&A, 449, 1
  * (12) Derouich, M., & Ben Abdallah, D., 2009, in ASP Conf. Ser. 405, Solar Polarization 5: In Honor of Jan Stenflo, ed. Berdyugina, S. V, Nagendra, K. N., & Ramelli, R. (San Francisco, CA: ASP), 355
  * (13) Derouich, M., Bommier, V., Malherbe, J. M., & Landi Degl’Innocenti, E., 2006, A&A 457, 1047
  * (14) Derouich, M., Radi, A., & Barklem, P. S., 2015, A&A, 584, A64
  * (15) Derouich, M., Sahal-Bréchot, S., & Barklem, P. S., 2003, A&A, 409, 369
  * (16) Derouich, M., Trujillo Bueno, J., & Manso Sainz, R., 2007, A&A, 472, 269
  * (17) Dunning, T. H., 1989, JChPh, 90, 1007
  * (18) Fano, U., 1957, RvMP, 29, 74
  * (19) Faurobert, M. & Arnaud, J., 2003, A&A, 412, 555
  * (20) Gandorfer, A., 2000, The Second Sol. Spectrum: A High Spectral Resolution Polarimetric Survey of Scattering Polarization at the Solar Limb in Graphical Representation, Vol. II: 3910 Å to 4630 Å (Zürich: vdf Hochschulverlag)
  * (21) Goldflam, R., Kouri, D. J., & Green, S., 1977, JChPh, 67, 4149
  * (22) Hutson, J. M. & Green, S., MOLSCAT Computer Code, Version 14, https://github.com/molscat/molscat
  * (23) Landi Degl’Innocenti, E. & Landolfi, M. 2004, Polarization in Spectral Lines (Dordrecht: Kluwer)
  * (24) Lique, F., Spielfiedel, A. & Feautrier, N., 2007, JPhB, 40, 787
  * (25) Milić, I. & Faurobert, M., 2012, A&A, 547, 7
  * (26) Mohan Rao, D., & Rangarajan, K. E., 1999, ApJL, 524, 139
  * (27) Parker, G. A., & Pack, R. T., 1978, JChPh, 68, 1585
  * (28) Qutub, S., Derouich, M., Kalugina, Y. N., Asiri, H. & Lique, F., 2020, MNRAS, 491, 1213
  * (29) Rosen, B., 1970, International Tables of Selected Constants, (Oxford: Pergamon)
  * (30) Sahal-Bréchot, S., 1977, ApJ, 213, 887
  * (31) Trujillo Bueno, J., 2001, Advanced Solar Polarimetry–Theory, Observation, and Instrumentation–20TH NSO/Sac Summer Workshop (San Francisco, CA: ASP), 161
  * (32) Werner, H.-J. & Knowles, P. J., 1988, JChPh, 89, 5803
  * (33) Werner, H.-J., Knowles, P. J., Knizia, G., et al., MOLPRO Quantum Chemistry Software, Version 2010.1, a Package of ab initio Programs, http://www.molpro.net


# HyT-NAS: Hybrid Transformers Neural Architecture Search for Edge Devices

Lotfi Abdelkrim Mecharbat1, Hadjer Benmeziane2, Hamza Ouarnoughi2 and Smail
Niar2 1Ecole Nationale Supérieure d’Informatique, Algiers, Algeria
2Université Polytechnique Hauts-de-France, Valenciennes, France
Email<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Vision Transformers have enabled recent attention-based Deep Learning (DL)
architectures to achieve remarkable results in Computer Vision (CV) tasks.
However, due to the extensive computational resources required, these
architectures are rarely implemented on resource-constrained platforms.
Current research investigates hybrid handcrafted convolution-based and
attention-based models for CV tasks such as image classification and object
detection. In this paper, we propose HyT-NAS, an efficient Hardware-aware
Neural Architecture Search (HW-NAS) including hybrid architectures targeting
vision tasks on tiny devices. HyT-NAS improves state-of-the-art HW-NAS by
enriching the search space and enhancing the search strategy as well as the
performance predictors. Our experiments show that HyT-NAS achieves a similar
hypervolume with less than 5x training evaluations. Our resulting architecture
outperforms MLPerf MobileNetV1 by 6.3% accuracy improvement with 3.5x less
number of parameters on Visual Wake Words.

###### Index Terms:

component, formatting, style, styling, insert

##  I Introduction

Recent advances have proven the efficacy of the attention operation, in
different domains such as Natural Language Processing (NLP) or Computer Vision
(CV). For the latter, Vision Transformers (ViT) [6] outperform state-of-the-
art in image classification [4] and object detection [19].

In parallel, there is a growing need of vision tasks deployment at the edge
for privacy and efficiency purposes. The remarkable success of ViT
architectures is often at the expense of a huge number of parameters and a
time-consuming inference. This makes ViT unsuitable for edge and tiny devices.

Current research investigates the hybrid convolution and attention
architectures to meet the edge requirements. Attention operations are mainly
used to enhance the task-specific performance, e.g., accuracy for image
classification or the Average Precision (AP) for object detection. However,
even hybrid networks [5, 7] are far from an optimal edge deployment. Figure 1
shows the difference in terms of number of parameters and accuracy of state-
of-the-art architectures on image classification. We notice that under the
edge limit, almost all architectures are convolution-only with some hybrid
architecture. In addition, near the tiny limit which allows up to 1M
parameters, all the architectures are convolution-only.

Figure 1: Number of parameters and accuracy on Imagenet of state-of-the-art DL
architectures. The limits are obtained from MCUNet [8] Figure 2: Hybrid
attention and convolution based macro-architecture

Hardware-aware Neural Architecture Search (HW-NAS) [2] automates the
identification of efficient neural network (NN) architecture given a task-
specific evaluation criterion and hardware-specific constraints, such as
latency and energy consumption. The problem is then cast to a multi-objective
optimization search where the obtained result is a Pareto front. The latter
represents a set of NN architectures that give the best trade-off between the
different objectives.

In this paper, we propose HyT-NAS, an optimized HW-NAS for hybrid attention
and convolution-based architectures. Our contributions can be summarized as
follows:

  1. 1.

A new hybrid search space that includes convolution and attention blocks
targeting tiny and edge devices.

  2. 2.

An adapted search strategy based on Multi-Objective Bayesian Optimization
using a customized performance evaluation predictors.

  3. 3.

HyT-NAS library enables to use the search methodology for a given task and
hardware platform defined by the user. Our code and library are available
111https://anonymous.4open.science/r/HyT-NAS-Search-Algorithm-A864/README.md.

Using HyT-NAS, we bring down the size of hybrid architectures to the tiny
architectures while achieving interesting performances. Our final
architectures have been tested on Visual Wake Words and Person Detection. The
best obtained architecture outperforms MLPerf MobileNetV1 by +6.3% more
accuracy with 3.5x less number of parameters on Visual Wake Words, while on
Person Detection, we achieve the same mAP as MobileNetV3 with a 7x smaller
model.

The rest of the paper is structured as follows: First, in section II we give
an overview of Hardware-aware Neural Architecture Search and Hybrid Attention
and Convolution Architectures. Section III details our approach HyT-NAS with
its components. Finally, we provide extensive comparison between HyT-NAS and
state-of-the-art search methodologies and apply our final models in Visual
Wake Words and Object Detection. The results are presented in section IV.

##  II Background & Related Works

###  II-A Hardware-aware Neural Architecture Search

HW-NAS [2] is cast as a multi-objective optimization problem where the search
space represents a set of possible architectures. Given that, increasing the
accuracy tends to increase the model’s size and thus its latency and energy
consumption, all the objectives conflict. The results in a Pareto front that
contains the most interesting solutions in term of trade-off between the
different objectives.

Evaluating the accuracy and hardware performances for each sampled
architecture hinders HW-NAS. Several methods [17] estimate the accuracy. A
surrogate model is built to predict the architecture’s ranking using the
learning to rank theory [18, 3] based on its characteristics. A common
practice to assess the search strategies is to compare the number of
evaluations required by each algorithm.

###  II-B Bayesian Optimization

Bayesian Optimization (BO) is a sample-efficient methodology to optimize
expensive black-box functions such as the accuracy that requires hours of
training. Intuitively BO tries to answer the question: Based on what we know
so far, which point should we evaluate next in the search process?. It
leverages a probabilistic surrogate model, generally a Gaussian process [12].
BO build an acquisition function to enable exploring uncertain regions that
might contain good solutions. Acquisition functions are heuristics that
provide the desirable it is to evaluate a point. In multi-objective settings,
the acquisition function [12] tries to improve the hypervolume of the Pareto
front approximation in each step.

###  II-C Hybrid Attention and Convolution Architectures

Vision transformers [6] have made a remarkable success in Computer vision
outperforming Convnets in several tasks such as image classification [4] and
object detection [19]. Many papers [14],[16] compared the representations
extracted from a ConvNet and Transformers. A general result is that both
operations extract different features, giving rise to hybrid attention and
convolution networks.

ConViT [5] modifies the attention operation. It incorporates soft
convolutional inductive biases using a gated positional self-attention. PiT
[7] merges Vit and ConvNets by inserting a depth-wise convolution-based
pooling layer in the original ViT definition.

##  III Proposed Approach

This paper describes a dedicated search methodology for tiny and edge hybrid
attention and convolution architectures. This methodology is composed of two
fundamental components: the Hybrid Attention-Convolution Search Space and the
HyT-NAS Search strategy.

###  III-A Hybrid Attention-based Search Space

Our search space is inspired by the MobileVit [11] architecture. Figure 2
depicts the macro-architecture used to construct all architectures in our
search space. The architecture consists of a series of interleaved convolution
and transformer blocks. Each block has its own set of hyperparameters
described in Table I. The total size of our search space is approximately
$1.2*10^{9}$.

Each convolution block is a MobileNetV2 [15] block. We sweep over: the number
of convolutions, their expansion ratio, and their output channel size. These
blocks’ inner output channel size is then computed with the input channel size
multiplied by the expansion ratio. Each attention block is a Vision
transformer encoder block. Particularly, we sweep the number of heads and MLP
layers size contained in each attention block.

Block |  Hyperparameter | Values
---|---|---
Convolution Block |  Number of blocks | [1, 2, 3, 4]
Expand ratio | [1x, 2x, 4x]
Out channel size | [8, 16, 24, 32]
Attention Block |  Expand ratio | [1x, 2x, 4x]
Channel size | [1x, 1.5x, 2x]
Number of heads | [1, 2, 4]
Feed forward ratio | [1x, 1.5x, 2x]
TABLE I: Search space hyperparameters

###  III-B Search Algorithm

Our search strategy is an optimized multi-objective bayesian optimization
(MOBO).

Figure 3 shows the pipeline of our search algorithm. Steps 1 to 5 are repeated
for a user-defined number of iterations:

  * •

First, an initial population of architectures $A_{0}=\\{a_{1},...,a_{n}\\}$ is
sampled via latent hypercube sampling [10]. The elements of the population
will then be evaluated to construct a dataset
$D={(a_{1},y_{1}),...,(a_{n},y_{n})}$ where $y_{i}$ is a tuple containing the
accuracy and latency of the architecture $a_{i}$. The dataset grows
incrementally throughout the search.

  * •

In each iteration, the surrogate model is trained using the dataset containing
all previously evaluated points. The predictions of the model are then used to
approximate the objectives via an acquisition function.

  * •

Finally, the surrogate problem defined as minimizing the acquisition function
is solved using NSGA-II. The optimal points found by the solver will go
through a selection process based on Hypervolume Improvement (HVI). This
selection will result in the construction of the new population $A_{i}$ that
will be evaluated and added to the dataset $D$.

Surrogate model: In the standard MOBO, a Gaussian process (GP) is used to
model each objective independently. GPs are known for their low performance on
high dimensional data (d$>$10) and their poor scalability with respect to the
number of evaluations. Thus, we replace them with a set of rank predictors of
different depths and widths. Rank predictors are models that rank the values
of the target instead of approximating them. These models are trained at each
iteration on all previously evaluated architectures $D$. The mean and standard
deviation of the networks’ predictions are used to approximate the rank of the
objectives via an acquisition function.

Acquisition function: The most common acquisition functions used in literature
are: expected improvement (EI), probability of improvement (PI), and upper
confidence bound (UCB). The latter is used in our search strategy. The UCB
algorithm enables us to balance exploration and exploitation. It shifts from
concentrating on exploration, choosing the least preferred actions, to
focusing on exploitation, which is adequate to our surrogate model’s learning.

Figure 3: HyT-NAS Search Strategy

Selection strategy: Our selection strategy involves two steps: First, points
obtained from the solver are sorted using the non-dominated sorting algorithm.
Then, the points belonging to the two first dominance levels are passed to the
second selection phase based on HVI.

###  III-C Accuracy & Latency Predictors

To reduce the search time, we build ML predictors to predict the
architecture’s accuracy and latency within hundreds of milliseconds, which
takes the search time a few seconds. We uniformly sample architectures from
our search space to construct the training dataset.

The latency dataset is more extensive for two reasons: (1) the latency
increase is subtle from one architecture to the other, provided we do not
increase the number of blocks. In other terms, if we only increase the
expansion ratio or the channel size, the increase in the latency is small but
not negligible. The predictor thus requires more training points to catch
these differences. (2) It takes more time to train the architectures than to
run them on the target hardware.

We empirically tested multiple ML predictors: XGBoost, LGBoost, MLP (2layers)
and MLP (3layers). Each predictor was trained to predict the accuracy and
latency using the mean squared error. We compared the kendal tau ranking
correlation of each predictor. XGBoost gives 95% and 93% for latency and
accuracy estimation respectively.

##  IV Evaluation

###  IV-A Expirements setup and Implementation Details

Search Algorithm settings: We initialize each ranker randomly from a set of
predefined hyperparmaters which are: number of estimators={100, 400, 800,
1000}, max depth for the estimators ={3, 6, 12} and learning rate ={0.01, 0.1,
0.5}. We used NSGA-II with a population size of 100 and a number of
generations of 20.

Evaluation strategy settings: we have used predictors for both objectives :
accuracy and latency. These predictors were built using a dataset of 300
models trained partially for 50 epochs on 8 Nvidia A100 GPUs accessed through
Grid5000[1] for accuracy, and a dataset of 1700 models executed each using an
image size of 224 on a Raspberry Pi Model 3 B For latency.

Model | Accuracy (%) | Latency (s) | Nb Param (M) |  | Hardware-aware
---
Search
MobileNetV1 | 83.7 | 2.61 | 0.67 | No
MobileNetV2 (x0.35) | 86.34 | 4.23 | 1.7 | No
ProxylessNAS | 86.55 | 2.51 | 4.0 | Yes
MobileVit-XS | 82.14 | 2.08 | 2.3 | No
MobileVit-S | 84.64 | 2.49 | 5.6 | No
HyT-NAS-BL (ours) | 85.48 | 0.47 | 0.015 | Yes
HyT-NAS-BA (ours) | 92.25 | 2.04 | 2.7 | Yes
HyT-NAS-O (ours) | 90.02 | 0.63 | 0.187 | Yes
TABLE II: Comparison between state-of-the-art architectures and HyT-NAS
optimal architectures on Visual Wake Words. BL stands for ”Best Latency”. BA
stands for ”Best Accuracy”. ”O” stands for optimal trade-off.

###  IV-B End-to-end Results

We compare our search strategy to three state-of-the-art and well-known
optimization algorithms: Random Search (RS), NSGA II, and Multi-objective
Bayesian Optimization (MOBO). For a fair comparison, we use our latency and
accuracy predictors for each method, i.e., the evaluation is done by calling
the two predictors.

Figure 4: Evolution of the hypervolume with respect to the number of
evaluations for state-of-the-art search strategies

Figure 4 shows the evolution of the hypervolume with respect to the number of
evaluations. Compared to these methods, our strategy rapidly achieves a higher
hypervolume with less than 500 evaluations. We can notice the importance and
efficiency of optimizing the surrogate model in MOBO compared to GP. Figure 5
shows the Pareto front approximations. Our method, in green, get the closest
to the optimal corner, i.e., where the latency is minimal and the accuracy is
maximal.

Figure 5: Pareto front approximations using different search strategies

Overall our search strategy takes few minutes to achieve a better Pareto front
approximation. Our work targets tiny DL architectures. For this reason, we
first target Visual wake words task. This task consists on classifying whether
or not an image contains a person.

Table II compares state-of-the-art architectures to HyT-NAS optimal
architectures. From the final Pareto front approximation, we select three
architectures: HyT-NAS-BL corresponding to the architecture with minimum
latency, HyT-NAS-BA corresponding to the architecture with maximum accuracy,
and HyT-NAS-O an in-between architecture. HyT-NAS-BL outperforms MobileVit
variants while significantly decreasing the latency and number of parameters.
This architecture only contains 15k parameters, which makes even its training
faster. HyT-NAS-BA outperforms all state-of-the-art architectures in terms of
accuracy and latency while having a decent number of parameters under the edge
limit. Our optimal architecture, HyT-NAS-O, decreases the number of parameters
to 187k, making it suitable for tiny devices. HyT-NAS-O outperforms state-of-
the-art architectures in terms of accuracy.

###  IV-C Use Case: Object Detection

Object detection is an important task at the edge. It is used in autonomous
driving, robots, and medical assistants [13]. Generally, object detection
models are composed of three components: Backbone, Neck and Head. Typically,
the backbone is the most time-consuming component among almost all state-of-
the-art models. This why it’s the focus of our optimization method.

We apply our optimal model as a backbone and use SSD-Lite [9] as head. We
compare our optimal architecture with state-of-the-art models. For a fair
comparison, we use the same training methodology explained in MobileVit [11]
to fairly compare the models. TableIII illustrates that our model is 3.8x
smaller with 2.8% off from the medium MobileVit-XS. Compared to MobileNetV3,
we achieve the same mAP with a 7x smaller model.

Backbone | Nb param | mAP
---|---|---
MobilenetV3 | 4.9M | 22.0
MobileViT-XXS | 1.9M | 21.4
MobileViT-XS | 2.7M | 24.8
HyT-NAS-O (ours) | 0.7M | 22.0
TABLE III: Object Detection with SSD-Lite

##  V Conclusion

This paper introduces HyT-NAS, a Hardware-aware Neural Architecture Search
(HW-NAS) for hybrid attention and convolution based models, targeting edge and
tiny devices. We fulfilled the initial promise of bringing hybrid models to
the tiny realm with less than 300k parameters and state-of-the-art accuracy
for Visual Wake Words and Person Detection.

## References

  * [1] Daniel Balouek, Alexandra Carpen Amarie, Ghislain Charrier, Frédéric Desprez, Emmanuel Jeannot, Emmanuel Jeanvoine, Adrien Lèbre, David Margery, Nicolas Niclausse, Lucas Nussbaum, Olivier Richard, Christian Pérez, Flavien Quesnel, Cyril Rohr, and Luc Sarzyniec.  Adding virtualization capabilities to the Grid’5000 testbed.  In Ivan I. Ivanov, Marten van Sinderen, Frank Leymann, and Tony Shan, editors, Cloud Computing and Services Science, volume 367 of Communications in Computer and Information Science, pages 3–20. Springer International Publishing, 2013.
  * [2] Hadjer Benmeziane, Kaoutar El Maghraoui, Hamza Ouarnoughi, Smaïl Niar, Martin Wistuba, and Naigang Wang.  Hardware-aware neural architecture search: Survey and taxonomy.  In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 4322–4329. ijcai.org, 2021.
  * [3] Hadjer Benmeziane, Hamza Ouarnoughi, Kaoutar El Maghraoui, and Smaïl Niar.  Accelerating neural architecture search with rank-preserving surrogate models.  In Manar Abu Talib, Laila Benhlima, and Kaoutar El Maghraoui, editors, ArabWIC 2021: The 7th Annual International Conference on Arab Women in Computing in Conjunction with the 2nd Forum of Women in Research, Sharjah, United Arab Emirates, August 25 - 26, 2021, pages 21:1–21:6. ACM, 2021.
  * [4] Zihang Dai, Hanxiao Liu, Quoc V. Le, and Mingxing Tan.  Coatnet: Marrying convolution and attention for all data sizes.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 3965–3977, 2021.
  * [5] Stéphane d’Ascoli, Hugo Touvron, Matthew L. Leavitt, Ari S. Morcos, Giulio Biroli, and Levent Sagun.  Convit: Improving vision transformers with soft convolutional inductive biases.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2286–2296. PMLR, 2021.
  * [6] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
  * [7] Byeongho Heo, Sangdoo Yun, Dongyoon Han, Sanghyuk Chun, Junsuk Choe, and Seong Joon Oh.  Rethinking spatial dimensions of vision transformers.  In 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021, pages 11916–11925. IEEE, 2021.
  * [8] Ji Lin, Wei-Ming Chen, Yujun Lin, John Cohn, Chuang Gan, and Song Han.  Mcunet: Tiny deep learning on iot devices.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [9] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott E. Reed, Cheng-Yang Fu, and Alexander C. Berg.  SSD: single shot multibox detector.  In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision - ECCV 2016 - 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part I, volume 9905 of Lecture Notes in Computer Science, pages 21–37. Springer, 2016.
  * [10] Michael D. McKay, Richard J. Beckman, and William J. Conover.  A comparison of three methods for selecting values of input variables in the analysis of output from a computer code.  Technometrics, 42(1):55–61, 2000.
  * [11] Sachin Mehta and Mohammad Rastegari.  Mobilevit: Light-weight, general-purpose, and mobile-friendly vision transformer.  CoRR, abs/2110.02178, 2021.
  * [12] J. B. Mockus and L. J. Mockus.  Bayesian approach to global optimization and application to multiobjective and constrained problems.  J. Optim. Theory Appl., 70(1):157–172, jul 1991.
  * [13] Victor F. Muñoz-Martínez, Carlos Vara-Thorbeck, Jesús M. Gómez de Gabriel, Jesús Fernández-Lozano, E. Sanchez-Badajoz, Alfonso García-Cerezo, Robert Lopez Toscano, and A. Jimenez-Garrido.  A medical robotic assistant for minimally invasive surgery.  In Proceedings of the 2000 IEEE International Conference on Robotics and Automation, ICRA 2000, April 24-28, 2000, San Francisco, CA, USA, pages 2901–2906. IEEE, 2000.
  * [14] Maithra Raghu, Thomas Unterthiner, Simon Kornblith, Chiyuan Zhang, and Alexey Dosovitskiy.  Do vision transformers see like convolutional neural networks?  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 12116–12128, 2021.
  * [15] Mark Sandler, Andrew G. Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pages 4510–4520. Computer Vision Foundation / IEEE Computer Society, 2018.
  * [16] Shikhar Tuli, Ishita Dasgupta, Erin Grant, and Thomas L Griffiths.  Are convolutional neural networks or transformers more like human vision?  arXiv preprint arXiv:2105.07197, 2021.
  * [17] Colin White, Arber Zela, Robin Ru, Yang Liu, and Frank Hutter.  How powerful are performance predictors in neural architecture search?  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 28454–28469, 2021.
  * [18] Martin Wistuba and Tejaswini Pedapati.  Learning to rank learning curves.  In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 10303–10312. PMLR, 2020.
  * [19] Hao Zhang, Feng Li, Shilong Liu, Lei Zhang, Hang Su, Jun Zhu, Lionel M. Ni, and Heung-Yeung Shum.  DINO: DETR with improved denoising anchor boxes for end-to-end object detection.  CoRR, abs/2203.03605, 2022.


# GMRT observations of the radio source $4C\;35.06$: precessing jets from a cD
galaxy under assembly?

Biju K.G  WMO Arts & Science college, Muttil, Kerala, India-673122
<EMAIL_ADDRESS>Newmann College, Thodupuzha, Kerala, India, 685584  M.
Pandey-Pommier  Centre de Recherche Astrophysique de Lyon- Observatoire de
Lyon, 9 avenue Charles André,
Saint-Genis Laval, F-69230, France  Sunilkumar P  Govt. College, Malappuram,
Kerala, India  Samir Dhurde  Inter University Centre for Astronomy and
Astrophysics(IUCAA), P.B No.7, Ganeshkhind, Pune-411 007, India  Joydeep
Bagchi  Inter University Centre for Astronomy and Astrophysics(IUCAA), P.B
No.7, Ganeshkhind, Pune-411 007, India  Ishwara-Chandra C.H  National Centre
for Radio Astrophysics, TIFR, P.B No.3,Ganeshkhind, Pune-411 007, India  Joe
Jacob  Newmann College, Thodupuzha, Kerala, India, 685584

###### Abstract

We report GMRT observation of the strong radio source $4C\;35.06$, an extended
( $z=0.047$) radio-loud AGN at the center of galaxy cluster $Abell\;407$. The
radio map at 610 MHz reveal a striking, helically twisted jet system emanating
from an optically faint AGN host. The radio morhology closely resembles the
precessing jets of the galactic microquasar $SS\;433$. The optical SDSS images
of central region show a complex ensemble of nine galactic condensations
within $1arc\ minute$, embedded in a faint, diffuse stellar halo. This system
presents a unique case for studying the formation of a giant elliptical galaxy
(cD) at the cluster center.

##  1 Introduction

The formation of cD galaxies are suggested to be occurring at the centre of
rich galaxy clusters in which multiple merger of galactic members take place.
The central region of the galaxy cluster $Abell\;407$, is the most convincing
and rare example of such a merger in the offing (Schneider et al.$1982$). This
region, where a conglomeration of nine galaxies shrouded in a stellar halo is
a typical case for studying the processes involved in such mergers. In this
study we focus mainly on the morphology of the jet from the radio source
$4C\;35.06$ hosted by the cluster $Abell\;407$.

Figure 1: (a) $SS\;433$ radio map(top)and 610 MHz radio map of
$4C\;35.06$(bottom);(b)The SDSS r band and $2MASS$ J band images of the
central region of $A\;407$. The galaxy, marked as A appears as the AGN host

##  2 Radio and optical studies of the source $4C35.06$

The low frequency maps from GMRT data show extended faint diffuse emission
from the jet structure of $4C\;35.06$. The 610 MHz radio map shows a jet with
helically twisted morphology and with a size estimate of approximately
$250\;kpc$, closely resembling that of the well known microquasar $SS\;433$
(Blundell and Bowler 2004). It points to the fact that the jet is precessing
and that the basic processes in jet emission in the stellar scales is the same
in galactic scales also(Fig-1(a)). Also there are no hot spots observed in the
jet, indicating the continuous shifting of jet direction.
The SDSS and 2MASS images show a faint galaxy coincident with the central
region of the radio map with a positional accuracy of 1.5” (Fig-1(b)). Since
powerful radio jets are observed to emanate only from massive elliptical
galaxies, this observation seems to be very unusual. For this low luminous
optical host, possibly majority of its stars might have been stripped off
during the violent mergers, still retaining a massive black hole at the
centre.
Results and conclusion:The radio source $4C\;35.06$ hosts a precessing kpc
scale jet similar to that of the microquasar $SS\;433$, and is seen to be
emanating from the faintest galactic member. $4C\;35.06$ underscores the
paradigm that despite the vast difference in scales, jet phenomena in radio
loud AGNs keep a striking similarity with that in microquasars.

## References

  * [1] Blundell K. M.,Bowler M. G 2004, ApJ, 616L, 159
  * [2] Schneider P.Donald., Gunn E.James., 1982, ApJ,311, 345.


# The time complexity of some algorithms for generating the spectra of finite
simple groups

Alexander Buturlakin<EMAIL_ADDRESS>Sobolev Institute of Mathematics,
4 Acad. Koptyug avenue, 630090 Novosibirsk, Russia.

###### Abstract

The spectrum $\omega(G)$ is the set of orders of elements of $G$. We consider
the problem of generating the spectrum of a finite nonabelian simple group $G$
given by the degree of $G$ if $G$ is an alternating group, or the Lie type,
Lie rank and order of the underlying field if $G$ is a group of Lie type.

Keywords: spectrum, finite simple group, algorithm, time complexity.

MSC2010: 20D06, 20D60.

1\. Introduction

The spectrum $\omega(G)$ is the set of orders of elements of a group $G$. Let
$G$ be a finite nonabelian simple group. We discuss whether there exists an
algorithm that given the degree of $G$ if it is an alternating group, or the
Lie type, Lie rank and order of the underlying field if $G$ is a group of Lie
type, outputs the spectrum of $G$. It is known that the size of the spectrum
of an alternating group is an exponential function of its degree (see Lemma
2.3 below). The size of the spectrum of a group of Lie type happens to be an
exponential function of its Lie rank (Lemma 3.3 below) and is a polynomial
function of the order of the field (this immediately follows from the
description of the spectra of these groups). So we are looking for an
algorithm with running time bounded by a polynomial in the length of the
output. Define the length of a set of positive integers $\mathcal{S}$ to be
the sum of $\log s$ (note that $\log$ will always mean the natural logarithm)
where $s$ runs over $\mathcal{S}$.

Let $\mu(G)$ be the set of elements of $\omega(G)$ that are maximal with
respect to divisibility. Since the spectrum is closed under taking divisors,
it is uniquely determined by any subset of $\omega(G)$ that contains $\mu(G)$.

######  Theorem 1.

Let $G$ be a symmetric or alternating group of degree $n$. There is an
algorithm that given $n$ outputs $\mu(G)$ and $\omega(G)$ in time bounded by a
polynomial of the length of the output.

Thus, the required algorithm exists in the case of alternating groups. As for
the groups of Lie type, we have a weaker result. For the exceptional groups,
we still have a polynomial algorithm but only for $\mu(G)$.

######  Theorem 2.

Let $G$ be a finite exceptional group of Lie type over a field of order $q$.
There is an algorithm that given the Lie type of $G$ and $q$ outputs $\mu(G)$
in time bounded by a polynomial of the length of the output.

Theorem 2 directly follows from the existing description of the spectra of the
exceptional groups. For more details see the proof of this theorem in Section
3.

In the case of classical groups, we only prove the existence of a quasi-
polynomial algorithm.

######  Theorem 3.

Let $G$ be a finite classical group of Lie rank $n$ over a field of order $q$.
Let $m$ be the length of $\mu(G)$. There is an algorithm that given the Lie
type of $G$, $n$ and $q$ outputs $\mu(G)$ in time $m^{O(\sqrt{\log\log m})}$.

Observe that we actually do not provide any new algorithm for the spectrum
generation. We just analyze the efficiency of the most straightforward
algorithms provided by the known description of spectra of groups of Lie type
(see [2, 3] for the classical groups, and [4] and references therein for the
exceptional groups) and the description of conjugacy classes of alternating
groups. We also want to note that we have no evidence for the existence or
non-existence of a polynomial-time algorithm for the classical groups.

The results of this paper complement the main theorem of [5], which is
concerned with the following problem. Given a finite set $\mathcal{M}$ of
natural numbers, determine whether there exists a finite simple group $G$
whose spectrum coincide with the set of divisors of elements of $\mathcal{M}$.
It is proved in [5] that there is a polynomial-time algorithm which returns a
unique candidate for $G$ (more precisely, its parameters in the sense
described above) or says that there is no such group. This candidate $G$
satisfies the following conditions: $\mathcal{M}$ is a subset of $\omega(G)$
and if $H$ is a finite simple group whose spectrum differs from the spectrum
of $G$, then the set of divisors of elements of $\mathcal{M}$ is not the
spectrum of $H$. Thus, to complete the task it remains to verify whether
$\omega(G)$ is equal to the set of divisors of elements of $\mathcal{M}$, or
equivalently, whether $\mu(G)$ is a subset of $\mathcal{M}$. Hence the
following statements are corollaries of the main result of [5] and Theorems 1,
2 and 3.

######  Corollary 1.

There is an algorithm that given a set $\mathcal{M}$ of positive integers
outputs the degree of an alternating group whose spectrum coincides with the
set of divisors of elements of $\mathcal{M}$, or says that there is no such a
group. The running time of the algorithm is polynomial in the length of
$\mathcal{M}$.

######  Corollary 2.

There is an algorithm that given a set $\mathcal{M}$ of positive integers
outputs a finite simple exceptional group of Lie type (the Lie type, Lie rank
and order of the underlying field) whose spectrum coincides with the set of
divisors of elements of $\mathcal{M}$, or says that there is no such group.
The running time of the algorithm is polynomial in the length of
$\mathcal{M}$.

######  Corollary 3.

There is an algorithm that given a set $\mathcal{M}$ of positive integers
outputs a finite simple classical group of Lie type (the Lie type, Lie rank
and order of the underlying field) whose spectrum coincides with the set of
divisors of elements of $\mathcal{M}$, or says that there is no such a group.
The running time of the algorithm is $m^{O(\sqrt{\log\log m})}$, where $m$ is
the length of $\mathcal{M}$.

2\. Alternating groups

Denote by $Sym_{n}$ and $Alt_{n}$ the symmetric and alternating group of
degree $n$. We write $g(n)$ for Landau’s function of a positive integer $n$,
that is, the largest order of an element of the group $Sym_{n}$.

######  Lemma 2.1.

If $n\geqslant 810$, then $0.99\leqslant\log g(n)/\sqrt{n\log n}\leqslant
1.08$.

######  Proof.

Directly follows from the bounds for $g(n)$ introduced in [7, Theorems 1, 2].

For a positive integer $n$, denote by $\sigma(n)$ the divisor function of $n$,
that is, the number of divisors of $n$. The following is a direct corollary of
[8, Theoreme 1].

######  Lemma 2.2.

Put

$n_{0}=2^{5}\cdot 3^{3}\cdot 5^{2}\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19$

and

$\alpha_{0}=\frac{\log\sigma(n_{0})\log\log n_{0}}{\log n_{0}}.$

If $n\geqslant 2$, then

$\log\sigma(n)\leqslant\alpha_{0}\frac{\log n}{\log\log n}.$

######  Lemma 2.3.

  * $(1)$

$|\omega(Sym_{n})|=\exp\left(\frac{2\pi}{\sqrt{6}}\sqrt{\frac{n}{\log
n}}+O\left(\frac{\sqrt{n}\log\log n}{\log n}\right)\right).$

  * $(2)$

$|\mu(Sym_{n})|\geqslant\exp\left(c\sqrt{\frac{n}{\log
n}}+o\left(\sqrt{\frac{n}{\log n}}\right)\right)$ for a positive $c$ greater
than $\left(\frac{2\pi}{\sqrt{6}}-2.16\alpha_{0}\right)>0.26$, where
$\alpha_{0}$ is defined in Lemma 2.2.

######  Proof.

Statement $(1)$ is proved in [6, Theorem I]. To prove the second statement,
let us bound the number $\sigma(m)$ of divisors of an element $m$ of
$\mu(Sym_{n})$. Since the bound in Lemma 2.2 is an increasing function, we can
write

$\log\sigma(m)\leqslant\alpha_{0}\frac{\log g(n)}{\log\log g(n)}.$

It follows from Lemma 2.1, that

$\log\sigma(m)\leqslant\alpha_{0}\frac{1.08\sqrt{n\log
n}}{\log(1.08\sqrt{n\log n})}=\frac{2\cdot 1.08\alpha_{0}\sqrt{n\log n}}{2\log
1.08+\log n+\log\log n}\leqslant 2.16\alpha_{0}\sqrt{\frac{n}{\log n}}.$

Finally, the inequalities

$|\omega(Sym_{n})|\geqslant|\mu(Sym_{n})|\geqslant\frac{|\omega(Sym_{n})|}{\max_{m\in\mu(Sym_{n})}\sigma(m)}$

give the required asymptotic.

Given a positive integer $n$, define $l(n)$ to be the minimal degree such that
$Sym_{l(n)}$ contains an element of order $n$. That is, $l(n)=0$ if $n=1$, and
$l(n)=p_{1}^{\alpha_{1}}+\dots+p_{k}^{\alpha_{k}}$ if $n\neq 1$ and
$n=p_{1}^{\alpha_{1}}\dots p_{k}^{\alpha_{k}}$, where $p_{1}$, $\dots$,
$p_{k}$ are pairwise distinct primes and every $\alpha_{i}>0$.

######  Proof of Theorem 1.

Let us first prove the statement for the whole spectrum in the case of
symmetric group. The algorithm proceeds as follows. First, it generates the
list of all primes up to $n$ using the sieve of Eratosthenes. Denote them by
$p_{1}<p_{2}<\dots<p_{k}$. Put $P_{i}=\\{p_{i}^{a}|\ a\geqslant 0\text{ is an
integer and }p_{i}^{a}\leqslant n\\}$. Next the algorithm generates the sets
$P_{i}$ for $1\leqslant i\leqslant k$. The elements of $\omega(Sym_{n})$ are
parameterized by elements of the direct product of the sets $P_{i}$. Now the
algorithm picks some $x_{1}$ from $P_{1}$. If $n-l(x_{1})<p_{2}$, then the
algorithm outputs $(x_{1},1,\dots,1)$. Otherwise it proceeds to $P_{2}$.
Assume that $x_{1}$, $\dots$, $x_{i}$ are chosen. If $i=k$ or $n-l(x_{1}\dots
x_{i})<p_{i+1}$, then the algorithm outputs $(x_{1},\dots,x_{i},1,\dots,1)$.
Otherwise it chooses $x_{i+1}$ from $P_{i+1}$ such that $l(x_{1}\dots
x_{i+1})\leqslant n$.

Obviously this algorithm visits every element of $\omega(Sym_{n})$ once and
the number of steps required to write down such an element is at most $k$,
which is less than $n$. Hence, it remains to show that the time required to
find all primes not exceeding $n$ is polynomial in output.

By Lemma 2.3, there exists a number $N$ such that for every $n>N$ we have

$\exp\left(\frac{3\pi}{\sqrt{6}}\sqrt{\frac{n}{\log
n}}\right)\geqslant|\omega(Sym_{n})|\geqslant\exp\left(\frac{\pi}{\sqrt{6}}\sqrt{\frac{n}{\log
n}}\right).$

Hence the length of the output is an exponential function of $n$. The sieve of
Eratosthenes requires $O(n\log\log n)$ steps, and the theorem is proved for
symmetric groups.

To obtain an analogous algorithm for alternating group, one should change the
definition of $P_{1}$: now $P_{1}$ = $\\{2^{a}+2|a\geqslant 0\text{ is an
integer and }2^{a}+2\leqslant n\\}$. The rest of the algorithm remains
unchanged.

Finally, Lemma 2.3 implies that there exist polynomials $p_{1}$ and $p_{2}$
such that

$|\omega(Sym_{n})|\leqslant p_{1}(|\mu(Sym_{n})|)\text{ and
}|\omega(Alt_{n})|\leqslant p_{2}(|\mu(Alt_{n})|).$

Hence the elements of $\mu(G)$ where $G$ is $Alt_{n}$ or $Sym_{n}$ can be
constructed from $\omega(G)$ in time polynomial in the length of $\mu(G)$.
This completes the proof.

3\. Groups of Lie type

######  Proof of Theorem 2.

The spectra of all finite simple exceptional groups of Lie type are described
(see, for example, [4] and references therein). It follows from these
descriptions that there exists a constant $C$ not depending on $G$ such that
the spectrum of $G$ contains a subset $\nu(G)$ with the following properties:
$\mu(G)$ is a subset of $\nu(G)$, the cardinality of $\nu(G)$ is at most $C$
and every element of $\nu(G)$ can be computed in time polynomial in $\log q$,
where $q$ is the order of the underlying field of $G$. Hence $\nu(G)$ can be
computed in time bounded by a polynomial of $\log q$ and so can be $\mu(G)$.
This proves the theorem.

Before proving Theorem 3, we need to introduce some notations and preliminary
results.

Fix an integer $a$ with $|a|>1$. If $s$ is an odd integer coprime to $a$,
define $e(s,a)$ to be the multiplicative order of $s$ modulo $a$. If $a$ is
odd, put $e(2,a)=1$ if $a\equiv 1$ modulo $4$, and $e(2,a)=2$ otherwise. A
prime $r$ is said to be a primitive prime divisor of $a^{i}-1$ if $e(r,a)=i$.
We write $r_{i}(a)$ to denote some primitive prime divisor of $a^{i}-1$, if
such a prime exists, and $R_{i}(a)$ to denote the set of all such divisors. In
[1, 10], it is proved that primitive prime divisors exist for almost all pairs
$(a,i)$.

######  Lemma 3.1.

Let $a$ be an integer and $|a|>1$. For every positive integer $i$ the set
$R_{i}(a)$ is nonempty, except for the pairs
$(a,i)\in\\{(2,1),(2,6),(-2,2),(-2,3),(3,1),(-3,2)\\}$.

For a pair of integers $a$ and $b$, denote by $(a,b)$ and $[a,b]$ their
greatest common divisor and least common multiple. If $b$ is a prime, then
denote by $(a)_{b}$ the $b$-part of $a$, that is, the greatest power of $b$
that divides $a$, and by $(a)_{b^{\prime}}$ the ratio $|a|/(a)_{b}$.

The following lemma is elementary.

######  Lemma 3.2.

Let $a$ be an integer such that $|a|>1$ and $s$, $t$ positive integers.

$1)$ $(a^{s}-1,a^{t}-1)=a^{(s,t)}-1;$

$2)$ $(a^{s}+1,a^{t}-1)=\begin{cases}a^{(s,t)}+1\text{ if
}\frac{s}{(s,t)}\text{ is odd and }\frac{t}{(s,t)}\text{ is even},\\\
(2,a-1)\text{ otherwise}.\end{cases}$

If $r_{i}(a)$ exists, let $r^{*}_{i}(a)$ be the greatest power of $r_{i}(a)$
dividing $a^{i}-1$. Also define $r_{3}^{*}(-2)=r_{6}^{*}(2)=9$ and
$r_{2}^{*}(-3)=8$. The following statement is a direct consequence of Lemma
3.2.

######  Corollary 4.

Let $s$ be a prime, $\alpha$ a positive integer, and $a$ an integer such that
$|a|>1$. Suppose that $r^{*}_{s^{\alpha}}(a)$ is defined. If
$r^{*}_{s^{\alpha}}(a)$ divides

$A=[a^{n_{1}}-\varepsilon_{1},\dots,a^{n_{l}}-\varepsilon_{l}],$

where $\varepsilon_{i}\in\\{1,-1\\}$, then one of the following statements
holds:

$1)$ there exists $i\in\\{1,\dots,l\\}$ such that $s^{\alpha}$ divides
$n_{i}$;

$2)$ $s=2$ and there exists $i\in\\{1,\dots,l\\}$ such that
$\varepsilon_{i}=-1$ and $s^{\alpha-1}$ divides $n_{i}$.

If $(r^{*}_{s^{\alpha}}(a),a-1)\neq 1$, then either $s^{\alpha}=2$ and
$r^{*}_{s^{\alpha}}(a)$ is a power of $2$, or $s^{\alpha}=3$ and
$r^{*}_{s^{\alpha}}(a)$ is a power of $3$.

Denote by $p(n)$ the number of partitions of $n$. For a group of Lie type over
a field of characteristic $p$, denote by $\omega_{p^{\prime}}(G)$ the set of
orders of semisimple elements, that is, elements whose order is coprime to
$p$. Put $\mu_{p^{\prime}}(G)=\mu(\omega_{p^{\prime}}(G))$. Following [9], we
use the notation $\operatorname{prk}(G)$ for the dimension of $G$ if $G$ is a
linear or unitary group and the Lie rank of $G$ if $G$ is an orthogonal or
symplectic group.

######  Lemma 3.3.

Let $G$ be a simple classical group with $\operatorname{prk}(G)=n$. Then

$|\mu_{p^{\prime}}(G)|\geqslant|\mu(Sym_{n})|$

unless $G=PSU_{n}(2)$ and always

$|\mu(G)|\geqslant|\mu(Sym_{n})|.$

######  Proof.

We will prove the lemma by constructing an injection $\phi$ from
$\mu(Sym_{n})$ to $\mu_{p^{\prime}}(G)$ for groups distinct from $PSU_{n}(2)$
and to $\mu(G)$ otherwise.

Assume that $G=PSL_{n}^{\varepsilon}(q)$, where $\varepsilon\in\\{+,-\\}$.
Suppose that $n_{1},\dots,n_{s}$ are positive integers such that
$n_{1}+\dots+n_{t}\leqslant n$. Define

$c(n_{1},\dots,n_{t})=\begin{cases}1&\text{if }t+n-(n_{1}+\dots+n_{t})>2;\\\
(n/(n_{1},n_{2}),\varepsilon q-1)&\text{if }t=2\text{ and
}n=n_{1}+\dots+n_{t};\\\ (n,\varepsilon q-1)&\text{if }t=1\text{ and
}n=1+n_{1}+\dots+n_{t};\\\ (q-\varepsilon 1)((n,\varepsilon q-1)&\text{if
}t=1\text{ and }n=n_{1}+\dots+n_{t}.\\\ \end{cases}$

In any case, $\pi(c(n_{1},\dots,n_{t}))\subseteq\pi(\varepsilon q-1)$.

According to [2, Corollary 3], for every $n_{1},\dots,n_{t}$ such that
$n_{1}+\dots+n_{t}\leqslant n$, $\omega(G)$ contains the number

$[(\varepsilon q)^{n_{1}}-1,\dots,(\varepsilon
q)^{n_{t}}-1]/c(n_{1},\dots,n_{t}),$

and every element of $\mu_{p^{\prime}}(G)$ has such a form.

Let

$a=p_{1}^{\alpha_{1}}\dots p_{t}^{\alpha_{t}}$

for prime numbers $p_{1}<\dots<p_{t}$ be an element of $\mu(Sym_{n})$. Since
$l(a)\leqslant n$, the number of the form

$b_{a}=[(\varepsilon q)^{p_{1}^{\alpha_{1}}}-1,\dots,(\varepsilon
q)^{p_{t}^{\alpha_{t}}}-1]/c(p_{1}^{\alpha_{1}},\dots,p_{t}^{\alpha_{t}})$

is an element of $\omega(G)$.

Assume that for some $i$, the number
$r^{*}=r^{*}_{p_{i}^{\alpha_{i}}}(\varepsilon q)$ is defined but does not
divide $b_{a}$. Then $r^{*}$ is not coprime to
$c(p_{1}^{\alpha_{1}},\dots,p_{t}^{\alpha_{t}})$, in particular, $t\leqslant
2$. By Corollary 4, it follows that $p_{i}^{\alpha_{i}}=2$ or $3$ and $r^{*}$
is a power of $p_{i}^{\alpha_{i}}$. If $t=2$, then
$n=p_{i}^{\alpha_{i}}+p_{j}^{\alpha_{j}}$ is coprime to $p_{i}^{\alpha_{i}}$,
and so $(c(p_{i}^{\alpha_{i}},p_{j}^{\alpha_{j}}),r^{*})=1$. If $t=1$, then
$n=2$ or $3$ (the lemma in this cases can be easily checked and we will assume
in what follows that $n>3$). So we may assume that every
$r^{*}_{p_{i}^{\alpha_{i}}}(\varepsilon q)$ divides $b_{a}$ if exists.

Suppose that $r^{*}_{p_{i}^{\alpha_{i}}}(\varepsilon q)$ is defined for all
$i$ and let $A$ be an element of $\mu_{p^{\prime}}(G)$ divisible by $b_{a}$.
We define $\phi(a)=A$.

Suppose that there exists an element $a^{\prime}=r_{1}^{\beta_{1}}\dots
r_{u}^{\beta_{u}}$ of $\mu(Sym_{n})$ such that $a^{\prime}\neq a$, all
$r^{*}_{r_{j}^{\beta_{j}}}(\varepsilon q)$ are defined, and
$\phi(a)=\phi(a^{\prime})$. Let

$A=[(\varepsilon q)^{m_{1}}-1,\dots,(\varepsilon
q)^{m_{s}}-1]/c(m_{1},\dots,m_{s})$

with $m_{1}+\dots+m_{s}\leqslant n$. It follows from Corollary 4 that for each
$p_{i}^{\alpha_{i}}$, there exists a number $m_{k}$ divisible by
$p_{i}^{\alpha_{i}}$. The same is true for each $r_{j}^{\beta_{j}}$. Since
$m_{1}+\dots+m_{s}\leqslant n$, the least common multiple of $m_{1}$, $\dots$,
$m_{s}$ lies in $\mu(Sym_{n})$. By maximality of $a$ and $a^{\prime}$, this
number is equal to both $a$ and $a^{\prime}$, which is a contradiction.

Assume that some $r^{*}_{p_{i}^{\alpha_{i}}}(\varepsilon q)$ does not exists.
By Lemma 3.1, we have $G=PSU_{n}(2)$ and $p_{i}^{\alpha_{i}}=2$ (in fact,
$p_{1}^{\alpha_{1}}=2$). Observe that the cases when $n<8$ can be checked by
direct computations. Since $2a$ is not an element of $\mu(Sym_{n})$, the sum
of $p_{i}^{\alpha_{i}}$ for $i>1$ is $n-3$ or $n-2$. Define $\phi(a)$ to be

$2\left[2^{p_{2}^{\alpha_{2}}}+1,\dots,2^{p_{t}^{\alpha_{t}}}+1\right]/d\text{
if this sum is }n-2,$

and as

$4\left[2^{p_{2}^{\alpha_{2}}}+1,\dots,2^{p_{t}^{\alpha_{t}}}+1\right]/d\text{
otherwise},$

where in both cases $d=1$ if $t>1$, and $d=(n,3)$ otherwise. Using [2,
Corollary 3] and the fact that $r^{*}_{p_{i}^{\alpha_{i}}}(\varepsilon q)$
divides $\phi(a)$ for $i>1$, it is easy to see that $\phi(a)\in\mu(G)$ and the
resulting $\phi$ is an injection from $\mu(Sym_{n})$ to $\mu(PSU_{n}(2))$.
Thus the lemma is proved for all linear and unitary groups.

Assume that $G=PSp_{2n}(q)$ or $\Omega_{2n+1}(q)$. Again let
$a=p_{1}^{\alpha_{1}}\dots p_{t}^{\alpha_{t}},$ where $p_{1}$, $\dots$,
$p_{t}$ are pairwise distinct primes, be an element of $\mu(Sym_{n})$. By [3,
Corollaries 2, 3, 6], $\omega(G)$ contains the number

$b_{a}=[q^{p_{1}^{\alpha_{1}}}+(-1)^{p_{1}},\dots,q^{p_{t}^{\alpha_{t}}}+(-1)^{p_{t}}]/(2,q-1).$
(1)

Observe that $b_{a}$ is divisible by all $r^{*}_{p_{i}^{\alpha_{i}}}(q)$ for
$p_{i}\neq 2$ and also by $r^{*}_{2p_{i}^{\alpha_{i}}}(q)$ if $p_{i}=2$.
Define $\phi(a)$ to be an element of $\mu_{p^{\prime}}(G)$ divisible by
$b_{a}$. It follows from [3, Corollaries 2, 3, 6] that $\phi(a)$ has the form

$[q^{m_{1}}-\varepsilon_{1},\dots,q^{m_{s}}-\varepsilon_{s}]/c,$ (2)

where $\varepsilon_{i}\in\\{1,-1\\}$ and $c=1,2$. It follows from Corollary 4,
that for each $i$ there exists index $j$ such that $p_{i}^{\alpha_{i}}$
divides $m_{j}$. As before, the assumption that $\phi$ is not injective leads
to a contradiction with the maximality of $a$ in $\mu(Sym_{n})$.

Let $G=P\Omega_{2n}^{\varepsilon}(q)$, where $\varepsilon\in\\{+,-\\}$. By [3,
Corollaries 8, 9], the number of the form (1), but with possibly
$(4,q-\varepsilon)$ instead of $(2,q-1)$ in the denominator, lies in
$\omega(G)$ if and only if either $l(a)<n$, or the number of pluses among
$(-1)^{p_{i}}$ is even when $\varepsilon=+$ and odd otherwise. Hence we should
worry about the signs in the definition of $b_{a}$ in this case. If $l(a)<n$,
then the previous definition of $b_{a}$ works. Suppose that $l(a)=n$. If
$t\leqslant 2$ or $p_{1}\neq 2$, then one can substitute
$q^{p_{i}^{\alpha_{i}}}-1$ by $q^{p_{i}^{\alpha_{i}}}+1$ for one odd prime
$p_{i}$ if necessary. If $n=a$ is a power of $2$, then
$b_{a}=(q^{n}+1)/(2,q-1)$ if $\varepsilon=-$ and
$b_{a}=(q^{n}-1)_{2^{\prime}}$ if $\varepsilon=+$. Again $b_{a}$ is divisible
by $r^{*}_{p_{i}^{\alpha_{i}}}(q)$ or $r^{*}_{2p_{i}^{\alpha_{i}}}(q)$ for
each odd $p_{i}$ and also by $r^{*}_{2p_{i}^{\alpha_{i}}}(q)$ if $p_{i}=2$ and
$(n,a,\varepsilon)\neq(2^{l},2^{l},+)$. As before, define $\phi(a)$ to be an
element of $\mu_{p^{\prime}}(G)$ divisible by $b_{a}$.

To see that $\phi$ is bijection, it is sufficient to show that
$\phi(a)\neq\phi(n)$ when $\varepsilon=+$, $n$ is a power of $2$ and $a\neq
n$. Suppose that $\phi(a)=\phi(n)=A$. Then $A$ has the form as in (2) but with
$c=1,2,4$. Reasoning as above, we conclude that $a=[m_{1},\dots,m_{s}]$. Since
$A$ is divisible by $r_{n}^{*}(q)$ then there exists index $j$ such that $n/2$
divides $m_{j}$. If $m_{j}=n$, then $a=n$, so $m_{j}=n/2$. Since $A$ is
divisible by $r_{n/2}^{*}(q)$ then there exists index $j_{1}$ such that $n/4$
divides $m_{j_{1}}$. Repeating this argument until $n/2^{l}\geqslant 4$, we
see that each of $m_{1},\dots,m_{s}$ divides $m_{j}$ and so $a=n/2$, which
contradicts maximality of $a$. The lemma is proved.

######  Proof of Theorem 3.

Let $G$ be a classical group with $\operatorname{prk}(G)=n$ over a field of
characteristic $p$ and order $q$. By Lemma 3.3, we have
$|\mu(G)|\geqslant|\mu(Sym_{n})|$. Hence there exist $\varepsilon>0$ and $M$
such that for all $n>M$, we have

$|\mu(G)|>\exp\left(\varepsilon\sqrt{\frac{n}{\log n}}\right).$ (3)

If $G$ is a linear or unitary group, then by [2, Corollary 3] there is a
subset $\nu(G)$ of $\omega(G)$ containing $\mu(G)$ whose elements are
parameterized by partitions of $n$ of the form

$n=(p^{\alpha}-1)+n_{1}+\dots+n_{s},$ (4)

where first term can be not presented. There are at most $1+\log_{2}(n+1)$
choices for the first term (including its absence), and the number of choices
for $n_{1}$, $\dots$, $n_{s}$ obviously not exceeds $p(n)$ for each choice of
the first term. Therefore we have

$|\nu(G)|<p(n)\log_{2}(2n+2).$

Every element of $\nu(G)$ can be computed in time polynomial in $n\log q$.
Hence the bound (3) provides the required bound on the running time of the
algorithm that just generates all partitions of the form (4) and calculates
corresponding elements of $\nu(G)$.

Let $G$ be a symplectic or orthogonal group. By [3, Corollaries 2, 3, 6],
there is a subset $\nu(G)$ of $\omega(G)$ containing $\mu(G)$ whose elements
are parameterized by partitions of $n$ of the form

$n=f(p)+\overline{m}_{1}+\overline{m}_{2},$

where $\overline{k}$ denote a partition of a number $k$ and first term $f(p)$
can be not presented. The function $f(p)$ depends on the Lie type of $G$ and
its characteristic and is equal to $\frac{p^{k}+i}{2}$ for some
$i\in\\{1,2,3,4\\}$. As before, we obtain the required bound on the running
time of the brute force algorithm in this case. This completes the proof.

4\. Acknowledgments

The author thanks M.A. Grechkoseeva and A.V. Vasil’ev for valuable comments.

The work is supported by the Mathematical Center in Akademgorodok under the
agreement No. 075-15-2019-1613 with the Ministry of Science and Higher
Education of the Russian Federation.

## References

  * [1] A. S. Bang, _Taltheoretiske undersolgelser_ , Tidskrift f. Math., 5 (1886), 70–80, 130–137.
  * [2] A. A. Buturlakin, _Spectra of finite linear and unitary groups_ , Algebra Logic, 47 (2008), no. 2, 91–99.
  * [3] A. A. Buturlakin, _Spectra of finite symplectic and orthogonal groups_ , Siberian Adv. Math. 21 (2011), no. 3, 176–210.
  * [4] A. A. Buturlakin, _Spectra of the groups $E_{8}(q)$_, Algebra Logic, 57 (2018), no. 1, 1–8.
  * [5] A. A. Buturlakin, A. V. Vasil’ev _The graph of atomic divisors and recognition of finite simple groups_ , J. Algebra, 537 (2019), 478–502.
  * [6] P. Erdős, P. Turán, _On some problems of a statistical group-theory. IV_ , Acta Mathematica Academiae Scientiaruin Hungaricae, V. 19 (3-4), (1968), pp. 413–435.
  * [7] J.P. Massias, J.L. Nicolas, and G. Robin, _Effective bounds for the maximal order of an element in the symmetric group_ , Math. Comp. 53 (1989), no. 188, 665–678.
  * [8] J.L. Nicolas and G. Robin, _Majorations explicites pour le nombre de diviseurs de $N$_, Canad. Math. Bull. 53 (1983), no. 4, 485–492.
  * [9] A. V. Vasil’ev, _On finite groups isospectral to simple classical groups_ , J. Algebra 423 (2015), 318–374.
  * [10] K. Zsigmondy, _Zur Theorie der Potenzreste_ , Monatsh. Math. Phys. 3 (1892), 265–284.