# Magnetic Ordering in GdAuAl4Ge2 and TbAuAl4Ge2: layered compounds with
triangular lanthanide nets

Keke Feng  Department of Physics, Florida State University.  National High
Magnetic Field Laboratory  Ian Andreas Leahy  Department of Physics,
University of Colorod Boulder  Olatunde Oladehin  Department of Physics,
Florida State University.  National High Magnetic Field Laboratory  Kaya Wei
National High Magnetic Field Laboratory  Minhyea Lee  Department of Physics,
University of Colorod Boulder  Ryan Baumbach  Department of Physics, Florida
State University.  National High Magnetic Field Laboratory

###### Abstract

We report the synthesis of the entire $Ln$AuAl4Ge2 ($Ln$ = Y, Pr, Nd, Sm, Gd,
Tb, Dy, Ho, Er, and Tm) series and focus on the magnetic properties of
GdAuAl4Ge2 and TbAuAl4Ge2. Temperature and magnetic field dependent
magnetization, heat capacity, and electrical resistivity measurements reveal
that both compounds exhibit several magnetically ordered states at low
temperatures, with evidence for magnetic fluctuations extending into the
paramagnetic temperature region. For magnetic fields applied in the $ab$-plane
there are several ordered state regions that are associated with metamagnetic
phase transitions, consistent with there being multiple nearly degenerate
ground states. Despite Gd being an isotropic $S$-state ion and Tb having an
anisotropic $J$-state, there are similarities in the phase diagrams for the
two compounds, suggesting that factors such as the symmetry of the crystalline
lattice, which features well separated triangular planes of lanthanide ions,
or the Ruderman-Kittel-Kasuya-Yosida interaction as defined by the Fermi
surface topography control the magnetism. We also point out similarities to
other centrosymmetric compounds that host skyrmion lattices such as Gd2PdSi3,
and propose that the $Ln$AuAl4Ge2 family of compounds are of interest as
reservoirs for complex magnetism and electronic behaviors such as the
topological Hall effect.

###### pacs:

Valid PACS appear here

††preprint: APS/123-QED

##  I Introduction

There is ongoing interest in magnetic skyrmions because (i) they may be useful
for spintronics applications or as new generation of information storage
devices and (ii) they present opportunities for basic science [1, 2]. Early
work focused on materials such as MnSi [3] and Fe0.5Co0.5Ge [4], where the
non-centrosymmetric crystal structure produces a Dzyaloshinskii-Moriya (DM)
interaction. More recently, there has been a surge of interest in
centrosymmetric lanthanide metals that exhibit topologically non-trivial
magnetic textures in the absence of a DM interaction [5, 6, 7, 8, 9, 10, 11].
In these materials, a delicate balance between the crystalline anisotropy and
various magnetic energy scales (e.g., geometric frustration [12, 13],
competing RKKY interactions [14, 15, 16]), and crystal electric field effects
[17, 18, 19]) combine to produce their complex magnetic states. It is also
seen that these materials feature unexpected coupling between different
degrees of freedom, where a hallmark behavior is the topological Hall effect
[20, 21].

Motivated by this, we recently investigated the weakly correlated $f$-electron
metal CeAuAl4Ge2 [22, 23], where the planar triangular arrangement of the
cerium ions resembles what is seen for Gd2PdSi3 [9, 24]. In this case, we
demonstrated that the cerium ions are trivalent, are weakly interacting, and
there is limited evidence for magnetic frustration. This led us to consider
whether strengthened magnetic interactions could drive magnetic frustration:
e.g., by replacing Ce with other lanthanide ($Ln$) ions. Here we report the
synthesis of single crystals of the entire $Ln$AuAl4Ge2 series and focus on
the magnetic properties of GdAuAl4Ge2 and TbAuAl4Ge2. These examples not only
are expected to have have large effective magnetic moments ($\mu_{\rm{eff}}$
$=$ 7.94 $\mu_{\rm{B}}$/Gd and 9.72 $\mu_{\rm{B}}$/Tb), but also allow a
comparison between a pure spin ion (Gd3+; $S$ $=$ 7/2, $L$ $=$ 0, $J$ $=$ 7/2)
and a mixed spin-orbital ion (Tb3+; $S$ $=$ 3, $L$ $=$ 3, $J$ $=$ 6).
Temperature and field dependent magnetization measurements reveal that
GdAuAl4Ge2 shows little anisotropy in the paramagnetic state while TbAuAl4Ge2
shows easy $ab$-plane anisotropy. Complex magnetic ordering appears at low
temperatures for both compounds, where GdAuAl4Ge2 has three magnetic phase
transitions at $T_{\rm{N1}}$ = 17.8 K, $T_{\rm{N2}}$ = 15.6 K, and
$T_{\rm{N3}}$ = 13.8 K and TbAuAl4Ge2 exhibits two magnetic phase transitions
at $T_{\rm{N1}}$ = 13.9 K and $T_{\rm{N2}}$ = 9.8 K. All of these transitions
are antiferromagnetic-like in low fields, but magnetic fields applied in the
$ab$ plane drive metamagnetic phase transitions into spin polarized states.

From these measurements, we construct $T-H$ magnetic phase diagrams, where
there are several regions with complex magnetic configurations. Heat capacity
measurements additionally show that a substantial fraction of the magnetic
entropy is found at temperatures above the ordered states, consistent with the
presence of magnetic fluctuations (and crystal electric field effects for
TbAuAl4Ge2) [25, 26, 27, 28]. Finally, the temperature dependent electrical
resistivity for GdAuAl4Ge2 exhibits a broad minimum that precedes the ordered
state, providing evidence for possible magnetic frustration [29, 30]. Taken
together, these measurements reveal that although these compounds form with a
relatively simple crystal structure, they nonetheless exhibit magnetic
degeneracy that resembles what is seen for other centrosymmetric skyrmion
lattices such as Gd2PdSi3. This invites further investigation to determine
whether these compounds are hosts for magnetically ordered states with
multiple q-vectors or nontrivial magnetic topologies, where phenomena such as
the topological Hall effect might be observed.

##  II Experimental Methods

$Ln$AuAl4Ge2 ($Ln$ = Y, Pr, Nd, Sm, Gd, Tb, Dy, Ho, Er, and Tm) single
crystals were grown using an aluminum molten metal flux, as previously
reported [22]. Elements with purities $>$ 99.9$\%$ were combined in the molar
ratio (RE):1(Au):10(Al):5(Ge) and loaded into 2-mL alumina Canfield crucibles
[31]. The crucibles were sealed under vacuum in quartz tubes, heated to 1000
∘C at a rate of 83∘C/h, kept at 1000∘C for 15 h, then cooled to 860∘C at a
rate of 7∘C/h and held at 860 ∘C for 48 h. This was followed by cooling down
to 700∘C at a rate of 12∘C/h. Excess flux was removed by centrifuging the
tubes at 700∘C, after which single-crystal platelets were collected. Crystals
exhibited triangular facets that are associated with the $ab$ plane.

Room temperature powder x-ray diffraction (PXRD) measurements were performed
using a Rigaku SmartLab SE X-ray diffractometer with a Cu K$\alpha$ source.
Crystal structure refinement analysis was performed using the Winprep
software. The principal axes were identified using Enraf-Nonius CAD-4
diffractometer, where the orientation of the full reciprocal lattice is
obtained. Magnetization $M$ measurements were carried out at temperatures $T$
= 1.8 - 300 K under applied magnetic fields of $\mu_{0}H$ = 0.5 - 9 T applied
parallel ($\|$) to the crystallographic $c$ axis and the $ab$ plane using a
Quantum Design VSM Magnetic Property Measurement System. Specific heat $C$
measurements were performed for temperatures $T$= 1.8 - 70 K in a Quantum
Design Physical Properties Measurement Systems using a conventional thermal
relaxation technique. DC electrical resistivity $\rho$ measurements for
temperatures $T$= 1.8 - 300 K were performed in a four-wire configuration for
polished single crystal using the same system.

##  III Results

###  III.1 $Ln$AuAl4Ge2 X-ray Diffraction

Figure 1: (a) Powder x-ray diffraction data for $Ln$AuAl4Ge2 ($Ln$ = Y, Pr,
Nd, Gd, Tb, Dy, Ho, Er, and Tm). The normalized intensity patterns are
compared to the theoretical peaks for CeAuAl4Ge2 [22] and have been shifted
vertically for clarity. The impurity peaks are marked with stars. (b) $Ln$
dependence of the diffraction peak at 006. The dashed line is a guide to the
eye. (c) The lattice constants $a$ and $c$ determined from Reitveld analysis
of powder x-ray diffraction measurements. Results for Ce are from Ref. [22].
(d) The ratio $c/a$ vs. $Ln$. (e) The unit cell volume $V$ vs. $Ln$. The
dashed lines are guides to the eye.

It was previously reported that CeAuAl4Ge2 crystallizes in a well-ordered
rhombohedral structure with space group $R\overline{3}m$ [22, 23] where the
cerium ions are in the trivalent state. In Fig. 1 we present powder x-ray
diffraction patterns for the other members of the $Ln$AuAl4Ge2 series ($Ln$ =
Y, Pr, Nd, Sm, Gd, Tb, Dy, Ho, Er, and Tm), showing that the same structure
persists across the lanthanide series (except Eu). Production of phase pure
specimens is challenging, as evidenced by the presence of extra peaks in the
XRD pattern that do not belong to the $Ln$AuAl4Ge2 structure. For $Ln$ = Pr
and Nd we were unable to index the additional peaks, but for $Ln$ = Dy, Ho,
Er, and Tm they are consistent with the $Ln$Al2Ge2 structure [32, 33]. In the
latter case, there is a close similarity between $Ln$Al2Ge2 and the
$Ln$AuAl4Ge2 phases, which likely relates to its tendency to appear in these
crystals. We also find that the $Ln$ = Y, Ce, Gd, Tb, and Sm compound can be
obtained as phase-pure crystals. Rietveld refinements were performed for the
entire series and the obtained lattice parameters ($a$ and $c$), the ratio
($c$/$a$), and the unit cell volume ($V$) are plotted in Figs. 1c-e, where
their variation is consistent with a trivalent lanthanide contraction that
isotropically compresses the unit cell. This behavior is expected since the
radius of the lanthanide ions decreases with increasing atomic number, as long
as the valence is fixed.

|  $T_{\rm{N1}}$(K) |  $T_{\rm{N2}}$(K) |  $T_{\rm{N3}}$(K) |  $H_{\rm{C1}}$(T) |  $H_{\rm{C2}}$(T) |  $H_{\rm{C3}}$(T) |  $\theta$(K) |  $\mu_{\rm{eff}}$($\mu_{B}$/F.U.) |  $M_{\rm{sat}}$($\mu_{B}$/F.U.)
---|---|---|---|---|---|---|---|---|---
$Gd$ | 17.8 | 15.6 | 13.8 | 1.9 | — | — | 2.3 | 7.93 | —
$Tb$ | 13.9 | 9.8 | — | 1.3 | 1.9 | 2.7 | 18 | 9.89 | 8.31
Table 1:  Summary of magnetic properties for GdAuAl4Ge2 and TbAuAl4Ge2
obtained from the magnetic susceptibility $\chi$($T$), the magnetization
$M(H)$, and the heat capacity $C(T)$. $\chi(T)$ was collected in a magnetic
field $\mu_{0}H$ $=$ 0.5 T. $C(T)$ and $\rho(T)$ were collected in $\mu_{0}H$
$=$ 0 T. $T_{\rm{N1}}$, $T_{\rm{N2}}$, and $T_{\rm{N3}}$ are the ordering
temperatures, $H_{\rm{C1}}$, $H_{\rm{C2}}$, and $H_{\rm{C3}}$ are critical
fields at $T$ $=$ 1.8 K, $\theta$ and $\mu_{\rm{eff}}$ are the Curie-Weiss
temperatures and the effective magnetic moments obtained from fits to
$\chi(T)$, and $M_{\rm{sat}}$ is that saturation moment obtained from $M(H)$.

###  III.2 GdAuAl4Ge2

The temperature-dependent magnetic susceptibility $\chi(T)$ $=$ $M/H$ for
GdAuAl4Ge2 is shown in Fig. 2. Curie-Weiss behavior with little anisotropy is
seen for $T$ $=$ 50 - 300 K, and fits to the data using the expression $\chi$
= $C$/($T$-$\theta$) yield the parameters $\theta$ = 2.3 K and
$\mu_{\rm{eff}}$ = 7.93 $\mu_{B}$/Gd ($\mu_{\rm{eff}}$ = 7.94 $\mu_{B}$ for
Gd3+). Anisotropic and field dependent magnetic ordering is seen at low
temperatures (Fig. 2c,d). For $\mu_{0}H$ $=$ 0.5 T applied in the $ab$-plane,
there are three distinct transitions at $T_{\rm{N1}}$ = 17.8 K, $T_{\rm{N2}}$
= 15.6 K, and $T_{\rm{N3}}$ = 13.8 K which are defined from the derivative of
the magnetic susceptibily $\partial\chi$/$\partial T$ (panels e and f). In the
low field region, each transition decreases the magnitude of $\chi$ (i.e.,
they are antiferromagnetic-like) and they are suppressed with increasing $H$.
There are abrupt changes in these trends above $\mu_{0}H$ = 1.5 T, where
$\chi(T)$ no longer strongly decreases at $T_{\rm{N1}}$ and instead tends to
saturate at low temperatures. This is consistent the occurrence of field
driven metamagnetic phase transitions where the spins abruptly become more
fully polarized. Within the spin polarized state, $T_{\rm{N1}}$ continues to
be suppressed by field and there are additional features at $T_{\rm{FM1}}$ and
$T_{\rm{FM2}}$ that suggest further weak spin reorientations. These
transitions are seen as subtle features in $\chi(T)$ and its temperature
derivative, but future work is needed to fully clarify the spin states that
are associated with them. It is also seen that for $H$ $\parallel$ $c$,
$\chi(T)$ only clearly shows the transitions at $T_{\rm{N1}}$ and
$T_{\rm{N3}}$, which are gradually suppressed with $H$. The sharpness of the
feature at $T_{\rm{N3}}$ suggests that it is first order.

Figure 2: (a) The inverse magnetic susceptibility $\chi^{-1}=(M/H)^{-1}$ vs
temperature $T$ for GdAuAl4Ge2 collected in a magnetic field $\mu_{0}H$ $=$
0.5 T applied parallel to $ab$-plane. The dotted line is a fit to the data
using the Curie-Weiss law, as described in the text. (b) $\chi(T)$ for
$\mu_{0}H$ $=$ 0.5 T applied both parallel (black line) to the $ab$-plane and
c-axis (red line). (c,d) $\chi(T)$ for 1.8 K $<T<$ 30 K emphasizing the region
near the magnetic ordering temperatures $T_{\rm{N1}}$, $T_{\rm{N2}}$,
$T_{\rm{N3}}$, $T_{\rm{FM1}}$, and $T_{\rm{FM}}$ which are defined in the
text. (e,f) Derivatives of the magnetic susceptibilities with respect to
temperature $\frac{\partial\chi}{\partial T}$. Data have been shifted
vertically for clarity, the dashed lines and short dot lines are guided to the
eye. Figure 3:  (a) Isothermal magnetic field dependent magnetization $M(H)$
for GdAuAl4Ge2 with fields applied in the $ab$ plane. (b) Zoom of the region
near the metamagnetic phase transition at $H_{\rm{C1}}$. Data are shifted
vertically for clarity. (c) $M(H)$ for fields along the $c$-axis. (d) The
derivative of the magnetization $\frac{\partial M}{\partial H}$ for $H$
$\parallel$ $ab$ at various temperature. Data have been shifted vertically for
clarity and the dashed line is a guide to the eye.

Isothermal magnetization $M(H)$ measurements are shown in Fig. 3. For $H$ $\|$
$c$ at $T$ = 1.8 K, $M(H)$ increases linearly with applied field and does not
saturate by 7 T. For $H$ $\parallel$ $ab$ at $T$ = 1.8 K, $M(H)$ initially
exhibits a linear increase in the magnetization, then undergoes an abrupt and
hysteretic increases at $H_{\rm{C1}}$ = 1.9 T. Such behavior is typically
associated with a first order spin flop transition. $M(H)$ subsequently
increases linearly and does not saturate for $\mu_{0}H$ $<$ 7 T, where it
reaches 62 % of the expected value for Gd3+ ($M_{\rm{sat}}$ = 7.94
$\mu_{B}$/Gd). This transition moves towards lower fields with increasing
temperature, where it is seen at 10 K but is no longer observed at 15 K.

Figure 4:  Temperature $T$ vs magnetic field $H$ phase diagram for GdAuAl4Ge2
constructed from the magnetic susceptibility $\chi(T)$ and isothermal
magnetization $M(H)$. The zero field phase transitions agree with results from
heat capacity $C(T)$, and electrical resistivity $\rho(T)$ data, described
below. The various regions wAFM1, wAFM2, SR, FM1, and FM2 are described in the
text.

These results are used to construct the phase diagrams shown in Fig 4, where a
rich family of ordered phases is seen for $H$ $\parallel$ $ab$. Starting from
the paramagnetic state at low $H$, we find that the transition at
$T_{\rm{N1}}$ weakly reduces $\chi$ upon entering an antiferromagnetic-like
region (wAFM1). This is rapidly replaced by another transition that further
reduces $\chi$ upon entering another antiferromagnetic-like region (wAFM2).
Finally, there is a strong reduction in $\chi$ when the system undergoes a
first order phase transition into the spin reoriented ground state (SR). The
rapid progression of phases, and the reductions in $\chi$, suggests that the
phases are characterized by progressively more anti-aligned spin
configurations which may feature complicated wave vectors. Above 1.5 T there
is an abrupt change in the ordered state behavior, where the transition into
the wAFM state continues to appear as a weak reduction from the paramagnetic
behavior, but the low field reductions in $\chi$ are replaced by
ferromagnetically spin polarized states labeled FM1 and FM2. These boundaries
are suppressed with increasing field, and are extrapoled to collapse towards
zero temperature near 8-10 T. The low temperature boundary between SR and FM1
is clearly seen in the field dependent magnetization, where it appears as a
hysteretic first order metamagnetic step. These results are contrasted with
what is seen when fields are applied along the $c$ axis, where the phase
boundaries are gradually suppressed with $H$.

Figure 5:  (a) The heat capacity divided by temperature $C/T$ vs. $T$ for
GdAuAl4Ge2 and YAuAl4Ge2. $C_{\rm{mag}}/T$ is calculated as described in the
text. (b) Zoom of $C_{\rm{mag}}/T$ near the transition temperatures. (c)
Magnetic entropy entropy $S_{\rm{mag}}$ vs. $T$, which is obtained from the
heat capacity data as described in the text. The dotted line represents the
calculated entropy for the full $J$ $=$ 7/2 Hund’s rule multiplet. (d) Zoom of
$S_{\rm{mag}}$ in the region near the magnetic ordering.

Heat capacity divided by temperature $C$/$T$ data are compared to those of the
$J$ = 0 nonmagnetic analogue YAuAl4Ge2 in Fig. 5a. As expected, there is close
agreement between these curves at elevated temperatures, where phonons
dominate the heat capacity. However, for $T$ $\lesssim$ 60 K, the Gd curve
begins to deviate from the phonon behavior. In order to expose this trend, we
plot the isolated magnetic contribution given by $C_{\rm{mag}}$/$T$ $=$
($C_{\rm{Gd}}$ \- $C_{\rm{Y}}$)/$T$, where a long and increasing tail precedes
the ordered states. Consistent with $\chi(T)$, three distinct transitions are
subsequently seen at $T_{\rm{N1}}$, $T_{\rm{N2}}$, and $T_{\rm{N3}}$. While
the first two have typical second order $\lambda$-shape peaks, the feature at
$T_{\rm{N3}}$ is sharp and hysteretic which confirms that it is a first-order
phase transition. Finally, we determine the magnetic contribution to the
entropy $S_{\rm{mag}}$($T$) (Figs. 5 c,d) by integrating $C_{\rm{mag}}$/$T$
for $T$ $>$ 1.8 K. $S_{\rm{mag}}(T$) reaches 12.8 J mol-1 K-1 at
$T_{\rm{N1}}$, which is reduced from the full theoretical magnetic entropy
given by $S_{\rm{mag}}$ = $R$ln(2$J$ \+ 1) = 17.3 J mol-1 K-1 ($S$ $=$ 7/2,
$L$ $=$ 0, and $J$ $=$ 7/2). After this, $S_{\rm{mag}}$ continues to increase
until it reaches a saturated value near 16.4 J mol-1 K-1 for $T$ $\approx$ 40
K. Given that crystal electric field splitting is not expected to influence
the behavior of Gd, this suggests that the excess entropy above $T_{\rm{N1}}$
likely originates from magnetic fluctuations of the Gd ions.

Figure 6:  Electrical resistivity $\rho$($T$) at zero magnetic fields with the
electrical current applied in an arbitrary direction for GdAuAl4Ge2. The main
panel (a) shows the low temperature region near the phase transitions.
$T_{\rm{N1}}$ and $T_{\rm{N2}}$ from $\chi$($T$) are marked. The inset figure
(b) shows the full temperature range between 1.8 K $<$ $T$ $<$ 300 K.
Resistivity minimum at $T$ = 33.8 K is marked with an arrow.

Fig. 6 shows the temperature dependent electrical resistivity $\rho$($T$),
with the electrical current applied in an arbitrary direction. Metallic
behavior is observed from room temperature, where the phonon-electron term is
dominant for 50 $<$ $T$ $<$ 300 K. The magnetic ordering is preceded by a weak
minimum that is centered near 25 K. This resembles what is seen for Gd2PdSi3,
where the minimum in the resistivity is thought to be associated with an
interplay between the RKKY interaction and magnetic frustration [29, 30].
$T_{\rm{N1}}$ and $T_{\rm{N2}}$ slightly reduce $\rho$, and there is a strong
decrease at $T_{\rm{N3}}$. This shows (i) that spin fluctuations above the
ordered state enhance $\rho$ and (ii) that the ordering removes of spin
scattering of conduction electrons. We also emphasize that the sharp reduction
at $T_{\rm{N3}}$ provides further evidence that this is a first order phase
transition.

###  III.3 TbAuAl4Ge2

Figure 7: (a) The inverse magnetic susceptibility $\chi^{-1}=(M/H)^{-1}$ vs
temperature $T$ for TbAuAl4Ge2 collected in a magnetic field $\mu_{0}H$ $=$
0.5 T applied parallel to $ab$-plane. The dotted line is a fit to the data
using the Curie-Weiss law, as described in the text. (b) $\chi(T)$ for
$\mu_{0}H$ $=$ 0.5 T applied both parallel (black line) to the $ab$-plane and
c-axis (red line). (c,d) $\chi(T)$ for 1.8 K $<T<$ 30 K emphasizing the region
near the magnetic ordering temperatures $T_{\rm{N1}}$, $T_{\rm{N2}}$, and
$T_{\rm{FM}}$ which are defined in the text. (e,f) Derivatives of the magnetic
susceptibilities with respect to temperature $\frac{\partial\chi}{\partial
T}$. Data have been shifted vertically for clarity, the dashed lines and short
dot lines are guided to the eye.

The temperature dependent magnetic susceptibility for TbAuAl4Ge2 is shown in
Fig. 7, where there is strong anisotropy that is associated with the non-zero
angular momentum ($L$ = 3). The spins prefer to align in the $ab$-plane, and a
Curie-Weiss temperature dependence for 100 K $<$ $T$ $<$ 300 K is observed.
Fits to the data yield the parameters $\theta$ = 18.0 K and $\mu_{\rm{eff}}$ =
9.89 $\mu_{B}$/Tb ($\mu_{\rm{eff}}$ = 9.72 $\mu_{B}$ for Tb3+). For $H\|$ c,
the weak $T$ dependence makes it difficult to perform a reliable Curie-Weiss
fit. The ordered state behaviors are shown in Figs. 7c,d, where
antiferromagnetic-like phase transitions at $T_{\rm{N1}}$ = 13.9 K and
$T_{\rm{N2}}$ = 9.8 K are seen for $\mu_{0}H$ $=$ 0.5 T applied in both
directions. For $H$ $\parallel$ $ab$, $T_{\rm{N1}}$ and $T_{\rm{N2}}$ are
suppressed with increasing $\mu_{0}H$ up to 1 T, after which larger fields
produce a field polarized state with a subphase that appears as a weak
reduction of $\chi(T)$ at $T_{\rm{FM}}$. Figs. 7e,f shows
$\partial\chi/\partial T$, where for $H$ $\parallel$ $ab$ the transitions at
$T_{\rm{N1}}$ and $T_{\rm{N2}}$ are seen as steps that are visible up to
$\mu_{0}H$ $=$ 1 T. Above this, $T_{\rm{N1}}$ is suppressed with increasing
$H$ until it is no longer observed above 3 T. There is also weak feature
within the field polarized state at $T_{\rm{FM}}$ that resembles what is seen
for the Gd analogue. Further work is needed to clarify the spin orientation
that is associated with it. For $H$ $\parallel$ $c$ the features at
$T_{\rm{N1}}$ and $T_{\rm{N2}}$ evolve in a more complicated way. While
$T_{\rm{N1}}$ is nearly field independent, $T_{\rm{N2}}$ evolves from being a
second-order-like reduction in $\chi$ towards a much sharper decrease, which
resembles what is seen for the Gd analogue in low fields.

Figure 8:  (a) Isothermal magnetic field dependent magnetization $M(H)$ for
TbAuAl4Ge2 with fields applied in the $ab$ plane and along the $c$-axis. (b)
Zoom of $M(H)$ near the metamagnetic phase transitions at $H_{\rm{C1}}$,
$H_{\rm{C2}}$, and $H_{\rm{C3}}$. Data are shifted vertically for clarity. (c)
The derivative of the magnetization $\frac{\partial M}{\partial H}$ for $H$
$\parallel$ $ab$ at various temperature. The curves have been shifted
vertically and the dashed lines are guides to the eye.

Isothermal magnetization $M(H)$ measurements are shown in Fig. 8. For $H$
$\parallel$ $ab$ at $T$ $=$ 1.8 K, the magnetization initially increases
linearly and undergoes an abrupt and hysteretic increase at $H_{\rm{C1}}$ $=$
1.3 T. This is followed by several additional transitions at $H_{\rm{C2}}$ $=$
1.9 T and $H_{\rm{C3}}$ $=$ 2.7 T, which are revealed in the derivative of the
magnetization $\partial$$M$/$\partial$$H$ (Fig. 8c). The magnetization finally
reaches a value of 8.31 $\mu_{B}$/F.U at 7 T, which is 85% of the expected
saturation value ($M_{\rm{sat}}$ = 9.72 $\mu_{B}$/Tb). Increasing temperature
causes the transitions to broaden and while $H_{\rm{C1}}$ is gradually
suppressed, $H_{\rm{C2}}$ and $H_{\rm{C3}}$ move towards larger values. In
contrast to this, $M(H)$ for $H$ $\parallel$ $c$ increases linearly with $H$
and shows no evidence for any transitions.

Figure 9:  Temperature $T$ vs magnetic field $H$ phase diagram for TbAuAl4Ge2
constructed from the magnetic susceptibility $\chi(T)$ and isothermal
magnetization $M(H)$. The zero field phase transition agree with results from
heat capacity $C(T)$, and electrical resistivity $\rho(T)$ data, described
below. The various regions wAFM1, wAFM2, SR, FM1, and FM2 are described in the
text.

The resulting phase diagrams are shown in Fig 9, where there are noteworthy
similarities to what is seen for GdAuAl4Ge2. For $H$ $\parallel$ $ab$ and at
low $H$, the system undergoes a second order transition into a state that
reduces $\chi$ below the extrapolated paramagnetic curve (wAFM1). This is
rapidly followed by another second order transition that further reduces
$\chi$ (SR). Again, this suggests that each of these transitions represents
progressively more antialigned spin configurations with complicated wave
vectors. Above $\mu_{0}H$ $\approx$ 1.5 T there is an abrupt change in the
ordered state behavior, where the transition into the wAFM state continues to
appear as a weak reduction from the paramagnetic behavior, but the low field
reductions in $\chi$ are replaced by spin polarized states labeled FM1 and
FM2. These boundaries are suppressed with increasing field, but unlike what is
seen for GdAuAl4Ge2, are sharply truncated and collapse towards zero
temperature near 2.5-3 T. The low temperature boundaries between SR, FM1, and
FM2 are clearly seen in the field dependent magnetization, where the boundary
between SR and FM1 appears as a hysteretic first order metamagnetic step, and
the subsequent boundaries are broader increases in $M$. The $T-H$ phase
diagram is much simpler when fields are applied along the $c$ axis, where the
phase boundaries are gradually suppressed with $H$.

Figure 10: (a) The heat capacity divided by temperature $C/T$ vs. $T$ for
TbAuAl4Ge2 and YAuAl4Ge2. $C_{\rm{mag}}/T$ is calculated as described in the
text. (b) Magnetic entropy entropy $S_{\rm{mag}}$ vs. $T$, which is obtained
from the heat capacity data as described in the text. The dotted line
represents the calculated entropy for the full $J$ $=$ 6 Hund’s rule
multiplet. (c) Zoom of $S_{\rm{mag}}$ in the region near the magnetic ordering
temperatures.

The heat capacity divided by temperature $C$/$T$ data are compared to those
for YAuAl4Ge2 in Fig. 10. As for the Gd analogue, at elevated temperatures
there is close agreement between the data sets but for $T$ $\lesssim$ 70 K,
the data deviate from what is seen for the Y compound. The isolated magnetic
contribution $C_{\rm{mag}}$/$T$ $=$ ($C_{\rm{Tb}}$ \- $C_{\rm{Y}}$)/$T$
reveals that a long and increasing tail precedes the ordered states and that
ordering is seen at $T_{\rm{N1}}$ = 13.9 K, $T_{\rm{N2}}$ = 9.8 K as second-
order peaks. The magnetic entropy $S_{\rm{mag}}$($T$) is shown in Fig. 10c,
where $S_{\rm{mag}}(T$) reaches 13.9 J mol-1 K-1 at $T_{\rm{N1}}$. Again this
value is reduced from the expected value $S_{\rm{mag}}$ = $R$ln(2$J$ \+ 1) =
21.3 J mol-1 K-1 ($S$ $=$ 3, $L$ $=$ 3, and $J$ $=$ 6). After this it
continues to increase until reaching a saturation value of 20.7 J mol-1 near
$T$ $\approx$ 70 K. This provides evidence that (i) the crystal electric field
split levels are fully populated around this temperature and (ii) magnetic
fluctuations may extend well above the ordered state, although the influences
of these factors are not distinguishable.

Figure 11:  Electrical resistivity $\rho$($T$) at zero magnetic field with the
electrical current applied in an arbitrary direction for TbAuAl4Ge2. The main
panel show the low temperature region near the phase transitions and the inset
shows the full temperature range between 1.8 K $<$ $T$ $<$ 300 K.

Fig. 11 shows the temperature dependence of the electrical resistivity
$\rho$($T$) for TbAuAl4Ge2 with the electrical current applied in an arbitrary
direction. Metallic behavior is observed from room temperature, where the
phonon-electron term is dominant for 50 $<$ $T$ $<$ 300 K. It is noteworthy
that the minimum that is seen for the Gd analogue does not appear here.
Finally, the rapid decrease in $\rho(T)$ coincides with the onset of the
magnetic ordering at $T_{\rm{N1}}$ and indicates the significant removal of
spin scattering of conduction electrons.

##  IV Discussion

Taken together, these measurements show that both GdAuAl4Ge2 and TbAuAl4Ge2
exhibit complex magnetic phenomena with noteworthy similarities. Evidence for
this includes (i) magnetic entropy that extends to temperatures well above the
ordered states, (ii) a sharp drop of resistivity as the magnetic order sets
in, and (iii) the occurrence of multiple magnetically ordered states that are
delicately tuned by magnetic fields. These features are shared by other other
magnetically frustrated materials that have nontrivial spin textures (e.g.,
Gd2PdSi3, GdRu2Si2, and Gd3Ru4Al12[5, 6, 7, 8, 9]) and are currently
motivating investigations of a variety of related materials (e.g.,
$Ln_{2}$RhSi3 $Ln$ = Gd, Tb, Dy [30]). However, it is also well known that Gd
and Tb based metals exhibit a wide variety of complex magnetic states with no
obvious connection to skyrmion states [26, 34]. Based on this, we propose that
further studies that target the magnetic structure such as neutron scattering,
Lorentz tunnelling electron microscopy, and magnetic force microscopy will be
of interest to clarify the behavior of the spins in these compounds. Also
needed are efforts to investigate whether these compounds exhibit novel
electrical transport properties such as a topological Hall effect.

Irrespective of whether any of these states exhibit nontrivial electronic
behaviors such as the topological Hall effect, it will also be of interest to
understand the various magnetically ordered phases that are present, the
factors that drive differences or similarities between the Gd and Tb examples,
and their interactions with other degrees of freedom. For example, it is
currently unclear why the Gd case exhibits a cascade of transitions between
the wAFM1, wAFM2, and SR states, along with a first order phase transition,
while the Tb example does not. We speculate that this relates to differences
in the magnetic interactions that are associated with the isotropic pure spin
Gd ions and the anisotropic Tb ions, but more work is needed to verify this.
It is also noteworthy that while GdAuAl4Ge2 exhibits a resistivity minimum
that precedes the ordering, TbAuAl4Ge2 does not. This implies that variation
of the lanthanide ions will likely be useful to optimize both magnetic
frustration and the conditions for the formation of a possible skyrmion
lattice.

##  V Conclusions

In summary, we have produced the series of compounds $Ln$AuAl4Ge2 ($Ln$ = Y,
Pr, Nd, Sm, Gd, Tb, Dy, Ho, Er, and Tm) and have focused on the bulk magnetic
properties of the Gd and Tb variants. Temperature and magnetic field dependent
magnetization, heat capacity, and electrical resistivity measurements show
that both of these compounds exhibit several magnetically ordered states at
low temperatures, with evidence for magnetic fluctuations extending into the
paramagnetic temperature region. Applied magnetic fields produce several
distinct magnetically ordered regions, where there are many similarities
between the two compounds. This is surprising given their different orbital
quantum numbers, and suggests that the features of the crystalline lattice or
the Fermi surface topography are dominant factors in determining the ground
state behavior. Thus, the family of materials $Ln$AuAl2Ge2 emerges as a
reservoir for novel metallic magnetism and invites investigations into them to
search for nontrivial spin structures and novel electronic behavior such as
the topological Hall effect.

##  VI Acknowledgements

RB, KF, and OO were supported by the National Science Foundation through NSF
DMR-1904361. Work at the University of Colorado Boulder was supported by Award
No. DE-SC0021377 of the U.S. Department of Energy, Basic Energy Sciences,
Materials Sciences and Engineering Division. The National High Magnetic Field
Laboratory is supported by the National Science Foundation through NSF
DMR-1644779 and the State of Florida.

## References

  * Kim [2019] B. S. Kim, Skyrmions and Hall transport, Journal of Physics: Condensed Matter 31, 383001 (2019).
  * Tokura and Kanazawa [2021] Y. Tokura and N. Kanazawa, Magnetic Skyrmion Materials, Chemical Reviews 121, 2857 (2021), pMID: 33164494, https://doi.org/10.1021/acs.chemrev.0c00297 .
  * Mühlbauer  _et al._ [2009] S. Mühlbauer, B. Binz, F. Jonietz, C. Pfleiderer, A. Rosch, A. Neubauer, R. Georgii, and P. Böni, Skyrmion Lattice in a Chiral Magnet, Science 323, 915 (2009).
  * Z.Yu  _et al._ [2010] X. Z.Yu, Y. Onose, N. Kanazawa, J. H. Park, J. H. Han, Y. Matsui, N. Nagaosa, and Y. Tokura, Real-space observation of a two-dimensional skyrmion crystal, Nature 465, 901 (2010).
  * Leonov and Mostovoy [2015] A. O. Leonov and M. Mostovoy, Multiply periodic states and isolated skyrmions in an anisotropic frustrated magnet, Nature Communications 6, 8275 (2015).
  * Lin and Batista [2018] S.-Z. Lin and C. D. Batista, Face Centered Cubic and Hexagonal Close Packed Skyrmion Crystals in Centrosymmetric Magnets, Phys. Rev. Lett. 120, 077202 (2018).
  * Hirschberger  _et al._ [2019] M. Hirschberger, T. Nakajima, S. Gao, L. Peng, A. Kikkawa, T. Kurumaji, M. Kriener, Y. Yamasaki, H. Sagayama, H. Nakao, K. Ohishi, K. Kakurai, Y. Taguchi, X. Yu, T.-h. Arima, and Y. Tokura, Skyrmion phase and competing magnetic orders on a breathing kagomé lattice, Nature Communications 10, 5831 (2019).
  * Khanh  _et al._ [2020] N. D. Khanh, T. Nakajima, Y. Tokura, and S. Seki, Nanometric square skyrmion lattice in a centrosymmetric tetragonal magnet, Nature Nanotechnology 15, 444 (2020).
  * Kurumaji  _et al._ [2019] T. Kurumaji, T. Nakajima, M. Hirschberger, A. Kikkawa, Y. Yamasaki, H. Sagayama, H. Nakao, Y. Taguchi, T. hisa Arima, and Y. Tokura, Skyrmion lattice with a giant topological hall effect in a frustrated triangular-lattice magnet, Science 365, 914 (2019), https://www.science.org/doi/pdf/10.1126/science.aau0968 .
  * Sunku  _et al._ [2016] S. S. Sunku, T. Kong, T. Ito, P. C. Canfield, B. S. Shastry, P. Sengupta, and C. Panagopoulos, Hysteretic magnetoresistance and unconventional anomalous Hall effect in the frustrated magnet TmB4, Phys. Rev. B 93, 174408 (2016).
  * Wang and Paglione [2021] K. Wang and J. Paglione, Crystalline symmetry-protected non-trivial topology in prototype compound BaAl4, npj Quantum Materials 6, 28 (2021).
  * Guo and Franz [2009] H.-M. Guo and M. Franz, Topological insulator on the kagome lattice, Phys. Rev. B 80, 113102 (2009).
  * Ezawa [2018] M. Ezawa, Higher-Order Topological Insulators and Semimetals on the Breathing Kagome and Pyrochlore Lattices, Phys. Rev. Lett. 120, 026801 (2018).
  * Selke [1988] W. Selke, The ANNNI model — Theoretical analysis and experimental application, Physics Reports 170, 213 (1988).
  * Rossat-Mignod  _et al._ [1977] J. Rossat-Mignod, P. Burlet, J. Villain, H. Bartholin, W. Tcheng-Si, D. Florence, and O. Vogt, Phase diagram and magnetic structures of CeSb, Phys. Rev. B 16, 440 (1977).
  * Chen  _et al._ [2017] K.-W. Chen, Y. Lai, Y.-C. Chiu, S. Steven, T. Besara, D. Graf, T. Siegrist, T. E. Albrecht-Schmitt, L. Balicas, and R. E. Baumbach, Possible devil’s staircase in the kondo lattice CeSbSe, Phys. Rev. B 96, 014421 (2017).
  * Feile  _et al._ [1981] R. Feile, M. Loewenhaupt, J. K. Kjems, and H. E. Hoenig, Influence of Superconductivity on Crystal Electric Field Transitions in ${\mathrm{La}}_{1-x}{\mathrm{Tb}}_{x}{\mathrm{Al}}_{2}$, Phys. Rev. Lett. 47, 610 (1981).
  * Silva  _et al._ [2017] L. S. Silva, S. G. Mercena, D. J. Garcia, E. M. Bittar, C. B. R. Jesus, P. G. Pagliuso, R. Lora-Serrano, C. T. Meneses, and J. G. S. Duque, Crystal field effects in the intermetallic $R{\mathrm{Ni}}_{3}{\mathrm{Ga}}_{9}$ ($R=\mathrm{Tb}$, Dy, Ho, and Er) compounds, Phys. Rev. B 95, 134434 (2017).
  * Ramakrishnan  _et al._ [2001] S. Ramakrishnan, N. G. Patil, A. D. Chinchure, and V. R. Marathe, Magnetism and crystal-field effects in the ${R}_{2}{\mathrm{Rh}}_{3}{\mathrm{Si}}_{5}(R=\mathrm{La},$ Ce, Pr, Nd, Tb, Gd, Dy, Er, Ho, and Tm) system, Phys. Rev. B 64, 064514 (2001).
  * Göbel  _et al._ [2017] B. Göbel, A. Mook, J. Henk, and I. Mertig, Antiferromagnetic skyrmion crystals: Generation, topological Hall, and topological spin Hall effect, Phys. Rev. B 96, 060406 (2017).
  * Hamamoto  _et al._ [2015] K. Hamamoto, M. Ezawa, and N. Nagaosa, Quantized topological Hall effect in skyrmion crystal, Phys. Rev. B 92, 115417 (2015).
  * Wu and Kanatzidis [2005] X. Wu and M. G. Kanatzidis, REAuAl4Ge2 and REAuAl4(AuxGe1-x)2 (RE=rare earth element): Quaternary intermetallics grown in liquid aluminum, Journal of Solid State Chemistry 178, 3233 (2005).
  * Zhang  _et al._ [2017] S. Zhang, N. Aryal, K. Huang, K.-W. Chen, Y. Lai, D. Graf, T. Besara, T. Siegrist, E. Manousakis, and R. E. Baumbach, Electronic structure and magnetism in the layered triangular lattice compound CeAuA4Ge2, Phys. Rev. Materials 1, 044404 (2017).
  * Saha  _et al._ [1999] S. R. Saha, H. Sugawara, T. D. Matsuda, H. Sato, R. Mallik, and E. V. Sampathkumaran, Magnetic anisotropy, first-order-like metamagnetic transitions, and large negative magnetoresistance in single-crystal ${\mathrm{Gd}}_{2}{\mathrm{PdSi}}_{3}$, Phys. Rev. B 60, 12162 (1999).
  * Kumar  _et al._ [2008] P. Kumar, K. G. Suresh, and A. K. Nigam, Magnetism, heat capacity, magnetocaloric effect and magneto-transport in R2Al (R = Nd, Gd, Tb) compounds, Journal of Physics D: Applied Physics 41, 105007 (2008).
  * Bouvier  _et al._ [1991] M. Bouvier, P. Lethuillier, and D. Schmitt, Specific heat in some gadolinium compounds. I. Experimental, Phys. Rev. B 43, 13137 (1991).
  * Mallik  _et al._ [1998] R. Mallik, E. V. Sampathkumaran, M. Strecker, and G. Wortmann, Observation of a minimum in the temperature-dependent electrical resistance above the magnetic-ordering temperature in Gd2PdSi3, Europhysics Letters (EPL) 41, 315 (1998).
  * Nakamura  _et al._ [2018] S. Nakamura, N. Kabeya, M. Kobayashi, K. Araki, K. Katoh, and A. Ochiai, Spin trimer formation in the metallic compound ${\mathrm{Gd}}_{3}{\mathrm{Ru}}_{4}{\mathrm{Al}}_{12}$ with a distorted kagome lattice structure, Phys. Rev. B 98, 054410 (2018).
  * Wang  _et al._ [2016] Z. Wang, K. Barros, G.-W. Chern, D. L. Maslov, and C. D. Batista, Resistivity Minimum in Highly Frustrated Itinerant Magnets, Phys. Rev. Lett. 117, 206601 (2016).
  * Kumar  _et al._ [2020] R. Kumar, K. K. Iyer, P. L. Paulose, and E. V. Sampathkumaran, Magnetic and transport anomalies in ${R}_{2}\mathrm{RhS}{\mathrm{i}}_{3}\phantom{\rule{4.0pt}{0.0pt}}(R=\mathrm{Gd}$, Tb, and Dy) resembling those of the exotic magnetic material $\mathrm{G}{\mathrm{d}}_{2}\mathrm{PdS}{\mathrm{i}}_{3}$, Phys. Rev. B 101, 144440 (2020).
  * Canfield  _et al._ [2016] P. C. Canfield, T. Kong, U. S. Kaluarachchi, and N. H. Jo, Use of frit-disc crucibles for routine and exploratory solution growth of single crystalline samples, Philosophical Magazine 96, 84 (2016), https://doi.org/10.1080/14786435.2015.1122248 .
  * Kranenberg  _et al._ [2002] C. Kranenberg, D. Johrendt, and A. Mewis, The stability range of the CaAl2Si2-type structure in case of LnAl2Ge2 compounds, Solid State Sciences 4, 261 (2002).
  * Qin  _et al._ [2008] P. Qin, Y. Chen, J. He, W. He, L. Nong, and L. Zeng, Investigation on structural and thermal expansion properties of Al2ErGe2, Materials Chemistry and Physics 109, 515 (2008).
  * Gschneidner and Eyring [1982] K. A. Gschneidner and L. Eyring,  _Handbook on the Physics and Chemistry of Rare Earths, Volume 1: Metals_ (North-Holland Publishing Company, Amsterdam, 1982).


# Almost optimum $\ell$-covering of $\mdmathbb{Z}_{n}$

Ke Shi School of Computer Science and Engineering, University of Electronic
Science and Technology of China, Chengdu, China 610054<EMAIL_ADDRESS>Chao Xu Corresponding author. School of Computer Science and Engineering,
University of Electronic Science and Technology of China, Chengdu, China
610054<EMAIL_ADDRESS>
###### Abstract

A subset $B$ of ring $\mdmathbb{Z}_{n}$ is called a $\ell$-covering set if
$\\{ab\pmod{n}\mid 0\leq a\leq\ell,b\in B\\}=\mdmathbb{Z}_{n}$. We show there
exists a $\ell$-covering set of $\mdmathbb{Z}_{n}$ of size
$O(\frac{n}{\ell}\log n)$ for all $n$ and $\ell$, and how to construct such
set. We also show examples where any $\ell$-covering set must have size
$\Omega(\frac{n}{\ell}\frac{\log n}{\log\log n})$. The proof uses a refined
bound for relative totient function obtained through sieve theory, and
existence of a large divisor with linear divisor sum.

##  1 Introduction

For two sets $A,B\subseteq\mdmathbb{Z}_{n}$, we let $A\cdot
B=\left\\{ab\pmod{n}\mid a\in A,b\in B\right\\}$. For a set $A$, $A^{\circ b}$
for some relation $\circ$ is defined as the set $\\{a\mid a\in A,a\circ b\\}$.
A subset $B$ of ring $\mdmathbb{Z}_{n}$ is called a _$\ell$ -covering set_ if
$\mdmathbb{Z}_{n}^{\leq\ell}\cdot B=\mdmathbb{Z}_{n}$. Let $f(n,\ell)$ be the
size of the smallest $\ell$-covering set of $\mdmathbb{Z}_{n}$. Equivalently,
we can define a _segment_ of slope $i$ and length $\ell$ to be
$\\{ix\pmod{n}\mid x\in\mdmathbb{Z}_{n}^{\leq\ell}\\}$, and we are interested
in finding a set of segments that covers $\mdmathbb{Z}_{n}$.

$\ell$-covering sets are useful in designing codes to flash storage related
design, including correct limited-magnitude errors[9, 10, 8], design memory
application for flash storage[7]. Since we can _compress_ a segment by
dividing everything by its slope, algorithm where the running time depends on
the size of the numbers in the input can be cut down. The first significant
improvement to modular subset sum was through partitioning by $\ell$-covering
[11]. There are also generalizations to $\mdmathbb{Z}^{d}_{n}$ [8].

The major question is finding the right bound for $f(n,\ell)$. The trivial
lower bound is $f(n,\ell)\geq\frac{n}{\ell}$. On the upper bound of
$f(n,\ell)$, there are multiple studies where $\ell$ is a small constant, or
$n$ has lots of structure, like being a prime number or maintaining certain
divisibility conditions [9, 10, 8]. A fully general non-trivial upper bound
for all $\ell$ and $n$ was first established by Chen et.al., which shows an
explicit construction of a $O(\frac{n(\log n)^{\omega(n)}}{\ell^{1/2}})$ size
$\ell$-covering set. They also showed
$f(n,\ell)=\frac{n^{1+o(1)}}{\ell^{1/2}}$ using the fourth moment of character
sums, but without providing a construction [2]. In the same article, the
authors shows $f(p,\ell)=O(\frac{p}{\ell})$ for prime $p$ with a simple
explicit construction. Koiliaris and Xu improved the result for general $n$
and $\ell$ using basic number theory, and showed
$f(n,\ell)=\frac{n^{1+o(1)}}{\ell}$ [11]. A $\ell$-covering set of the same
size can also be found in $O(n\ell)$ time. The value hidden in $o(1)$ could be
as large as $\Omega(\frac{1}{\log\log n})$. A closer inspection of their
result shows $f(n,\ell)=O(\frac{n}{\ell}\log n\log\log n)$ if $\ell$ is
neither too large nor too small. That is, if $t\leq\ell\leq n/t$, where
$t=n^{\Omega(\frac{1}{\log\log n})}$. See Figure 1.1 for comparison of the
results.

The covering problem can be considered in a more general context. For any
_semigroup_ $(M,\diamond)$, define $A\diamond B=\\{a\diamond b\mid a\in A,b\in
B\\}$. For $A\subseteq M$, we are interested in finding a small $B$ such that
$A\diamond B=M$. Here $B$ is called an $A$-covering. The $\ell$-covering
problem is the special case where the semigroup is $(\mdmathbb{Z}_{n},\cdot)$,
and $A=\mdmathbb{Z}_{n}^{\leq\ell}$. When $M$ is a group, it was studied in
[1]. In particular, they showed for a finite group $(G,\diamond)$ and any
$A\subseteq G$, there exists an $A$-covering of size no larger than
$\frac{|G|}{|A|}(\log|A|+1)$. We emphasis that our problem is over the
_semigroup_ $(\mdmathbb{Z}_{n},\cdot)$, which is _not a group_ , and can
behave very differently. For example, if $A$ consists of only elements
divisible by $2$ and $n$ is divisible by $2$, then no $A$-covering of
$(\mdmathbb{Z}_{n},\cdot)$ exists. It was shown that there exists $A$ that is
a set of $\ell$ consecutive integers, any $A$-covering of
$(\mdmathbb{Z}_{n},\cdot)$ has $\Omega(\frac{n}{\ell}\log n)$ size [13]. This
shows the choice of the set $\mdmathbb{Z}_{n}^{\leq\ell}$ is very special, as
there are examples where $\ell$-covering has $O(\frac{n}{\ell})$ size [2]. In
the pursuit of our main theorem, another instance of the covering problem
arises and might be of independent interest. Let the semigroup be
$(\mdmathbb{D}_{n},\odot)$, where $\mdmathbb{D}_{n}$ is the set of divisors of
$n$, and $a\odot b=\gcd(ab,n)$, where $\gcd$ is the greatest common divisor
function. We are interested in finding a $\mdmathbb{D}_{n}^{\leq s}$-covering
set.

| Size of $\ell$-covering | Construction Time
---|---|---
Chen et. al. [2] | $O\left(\frac{n(\log n)^{\omega(n)}}{\ell^{1/2}}\right)$ | $\tilde{O}\left(\frac{n(\log n)^{\omega(n)}}{\ell^{1/2}}\right)$
Chen et. al. [2] | $\frac{n^{1+o(1)}}{\ell^{1/2}}$ | Non-constructive
Koiliaris and Xu [11] | $\frac{n^{1+o(1)}}{\ell}$ | $O(n\ell)$
Theorem 4.3 | $O(\frac{n}{\ell}\log n)$ | $O(n\ell)$
Theorem 4.5 | $O(\frac{n}{\ell}\log n\log\log n)$ |  $\tilde{O}(\frac{n}{\ell})+n^{o(1)}$ randomized
Figure 1.1: Comparison of results for $\ell$-covering for arbitrary $n$ and
$\ell$. $\omega(n)$ is the number of distinct prime factors of $n$.

###  1.1 Our Contributions

  1. 1.

We show $f(n,\ell)=O(\frac{n}{\ell}\log n)$ for all $\ell<n$.

  2. 2.

We show there exists a constant $c$ and an infinite number of $n$ and $\ell$,
such that $f(n,\ell)\geq c\frac{n}{\ell}\frac{\log n}{\log\log n}$.

We also show some interesting number theoretical side results. One is a
sharper bound for the relative totient function, the other is the existence of
a large divisor with linear divisor sum.

###  1.2 Technical overview

Our approach is similar to the one of Koiliaris and Xu [11]. We breifly
describe their approach. Recall $\mdmathbb{Z}_{n}$ is the set of integers
modulo $n$. We further define
$\mdmathbb{Z}_{n,d}=\left\\{x\mid\gcd(x,n)=d,x\in\mdmathbb{Z}_{n}\right\\}$,
and $\mdmathbb{Z}^{*}_{n}=\mdmathbb{Z}_{n,1}$. Let $\mathcal{S}_{\ell}(X)$ to
be the set of segments of length $\ell$ and slope in $X$. Their main idea is
to convert the covering problem over the _semigroup_
$(\mdmathbb{Z}_{n},\cdot)$ to covering problems over the _group_
$(\mdmathbb{Z}^{*}_{n/d},\cdot)$ for all $d\in\mdmathbb{D}_{n}$. Since
$\mdmathbb{Z}_{n,d}$ forms a partition of $\mdmathbb{Z}_{n}$, one can reason
about covering them individually. That is, covering $\mdmathbb{Z}_{n,d}$ by
$\mathcal{S}_{\ell}(\mdmathbb{Z}_{n,d})$. This is equivalent to cover
$\mdmathbb{Z}^{*}_{n/d}$ with $\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{n/d})$,
and then lift to a cover in $\mdmathbb{Z}_{n,d}$ by multiply everything by
$d$. Hence, now we only have to work with covering problem over
$(\mdmathbb{Z}^{*}_{n/d},\cdot)$ for all $d$, all of which are _groups_. The
covering results for groups can be readily applied [1]. Once we find the
covering for each individual $(\mdmathbb{Z}^{*}_{n/d},\cdot)$, we take their
union, and obtain a $\ell$-covering.

The approach is sufficient to obtain $f(n,\ell)=O(\frac{n}{\ell}\log n\log\log
n)$ if $\ell$ is neither _too small_ nor _too large_. However, their result
suffers when $\ell$ is extreme in two ways.

  1. 1.

$\ell=n^{1-o(\frac{1}{\log\log n})}$: Any covering obtained would have size at
least the number of divisors of $n$, which in the worst case can be
$n^{\Omega(\frac{1}{\log\log n})}$, and dominates $\frac{n}{\ell}$.

  2. 2.

$\ell=n^{o(\frac{1}{\log\log n})}$: If we are working on covering
$\mdmathbb{Z}^{*}_{n}$, we need to know $|\mdmathbb{Z}^{*\leq\ell}_{n}|$, also
know as $\varphi(n,\ell)$. Previously, the estimate for $\varphi(n,\ell)$ is
insufficient when $\ell$ is small.

Our approach removes the deficiency, and also eliminate the extra $\log\log n$
factor.

First, we improve the estimate for $\varphi(n,\ell)$. This value is tightly
connected with how many times an element is covered by segments, which is also
connected with how large a $\ell$-covering has to be. Second, we use
$\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{n})$ to cover more than just
$\mdmathbb{Z}^{*}_{n}$. It might be the case that a small number of segments
in $\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{n})$ can cover $\mdmathbb{Z}_{n,d}$
for many $d$, simultaneously. Therefore it would decrease the number of
segments required for the cover. This change can shave off a $\log\log n$
factor. Finally, we need to handle the case when $\ell$ is large. Clever
choices are required to make sure we can shave off the $\log\log n$ factor
while maintaining the set of divisors involved in the segments are small.

#### Organization

The paper is organized as follows. Section 2 are the preliminaries, which
contains all the necessary number theory backgrounds. Section 3 describes some
number theoretical results on bounding $\varphi(n,\ell)$ and finding a large
divisor of $n$ with linear divisor sum. Section 4 proves the main theorem that
$f(n,\ell)=O(\frac{n}{\ell}\log n)$, discuss its construction, and also
provides a lower bound.

##  2 Preliminaries

The paper has a few simple algorithmic ideas, but our methods are mainly
analytical. Hence, we reserved a large amount of space in the preliminaries to
set up the scene.

Let $\mathcal{X}$ be a collection of sets in the universe $U$. A _set cover_
of $U$ is a collection of subsets in $\mathcal{X}$ which together covers $U$.
Formally, $\mathcal{X}^{\prime}\subseteq\mathcal{X}$ such that
$U=\bigcup_{X\in\mathcal{X}^{\prime}}X$. The _set cover problem_ is the
computational problem of finding a minimum cardinality set cover.

All multiplications in $\mdmathbb{Z}_{n}$ are modulo $n$, hence we will omit
$\pmod{n}$ from now on. Recall a set of the form $\left\\{ix\mid
x\in\mdmathbb{Z}_{n}^{\leq\ell}\right\\}$ is called a _segment_ of length
$\ell$ with slope $i$. Note that the segment of length $\ell$ might have fewer
than $\ell$ elements. Recall $\mathcal{S}_{\ell}(X)$ is the segments of length
$\ell$ with slope in $X$, namely $\left\\{\left\\{ix\mid
x\in\mdmathbb{Z}_{n}^{\leq\ell}\right\\}\mid i\in X\right\\}$. Hence, finding
a $\ell$-covering is equivalent to set cover with segments in
$\mathcal{S}_{\ell}(\mdmathbb{Z}_{n})$, and the universe is
$\mdmathbb{Z}_{n}$.

Set cover problem has some well-known bounds relating the size of a set cover
and the frequency of element covered[12, 15].

######  Theorem 2.1 ([12, 15]).

Let there be a collection of $t$ sets each with size at most $a$, and each
element of the universe is covered by at least $b$ of the sets, then there
exists a subcollection of $O(\frac{t}{b}\log a)$ sets that covers the
universe.

The above theorem is the main combinatorial tool for bounding the size of a
set cover. To obtain a cover of the specified size, the greedy algorithm is
sufficient.

The base of the $\log$ is $e$. To avoid getting into the negatives, we take
$\log(x)$ to mean $\max(\log(x),1)$. $\tilde{O}(f(n))$, the soft $O$, is a
short hand for $O(f(n)\operatorname{polylog}n)$.

###  2.1 Number theory

We refer to some standard notation and bounds, where it can be found in
various analytic number theory textbook, for example [4]. Recall
$\mdmathbb{Z}_{n}$ is the set of integers modulo $n$,
$\mdmathbb{Z}_{n,d}=\left\\{x|\gcd(x,n)=d,x\in\mdmathbb{Z}_{n}\right\\}$, and
$\mdmathbb{Z}^{*}_{n}=\mdmathbb{Z}_{n,1}$. $\mdmathbb{Z}^{*}_{n}$ is the set
of numbers in $\mdmathbb{Z}_{n}$ that are relatively prime to $n$. The
notation $m|n$ means $m$ is a divisor of $n$.

  1. 1.

$\pi(n)$, the _prime counting function_ , is the number of primes no larger
than $n$, and $\pi(n)=\Theta(\frac{n}{\log n})$.

  2. 2.

$\varphi(n)$, the _Euler totient function_ , defined as
$\varphi(n)=|\mdmathbb{Z}^{*}_{n}|=n\prod_{p|n}\left(1-\frac{1}{p}\right)$,
and is bounded by $\Omega(\frac{n}{\log\log n})$.

  3. 3.

$\omega(n)$, the _number of distinct prime factors_ of $n$, has the relation
$\omega(n)=O(\frac{\log n}{\log\log n})$.

  4. 4.

$d(n)$, the _divisor function_ , is the number of divisors of $n$, and
$d(n)=n^{O(\frac{1}{\log\log n})}=n^{o(1)}$.

  5. 5.

$\sigma(n)$, the _divisor sum function_ , is the sum of divisors of $n$, and
$\sigma(n)\leq\frac{n^{2}}{\varphi(n)}$. This also implies
$\sigma(n)=O(n\log\log n)$.

  6. 6.

The sum of reciprocal of primes no larger than $n$ is $\sum_{p\leq n,p\text{
prime}}\frac{1}{p}=O(\log\log n)$.

The center of our argument lies in the _relative totient function_ , denoted
as $\varphi(n,\ell)=|\mdmathbb{Z}^{*\leq\ell}_{n}|$. We present a simple lemma
in number theory, this is undoubtedly known, but it is easier to prove it
directly.

######  Lemma 2.2.

Let $y\in\mdmathbb{Z}^{*}_{n}$, and $B\subseteq\mdmathbb{Z}_{n}^{*}$. The
number of $x\in\mdmathbb{Z}_{dn}^{*}$ such that $xb\equiv y\pmod{n}$, and
$b\in B$ is $|B|\frac{\varphi(dn)}{\varphi(n)}$.

  * Proof

Indeed, the theorem is the same as finding the number of solutions to $x\equiv
yb^{-1}\pmod{n}$ where $b\in B$. For a fixed $b$, let $z=yb^{-1}$. We are
asking the number of $x\in\mdmathbb{Z}^{*}_{dn}$ such that $x\equiv
z\pmod{n}$. Consider the set $A=\\{z+kn\mid 0\leq k\leq d-1\\}$. Let the
distinct prime factors set of $n$ be $P_{n}$. Note $\gcd(z,n)=1$, thus $p\in
P_{n}$ can’t divide any element in $A$. Let $P_{dn}\setminus
P_{n}=P_{d}^{\prime}\subseteq P_{d}$. Let $q$ be the product of some elements
in $P_{d}^{\prime}$, $q|d$, $(q,n)=1$. Let $A_{q}=\\{a|a\in A,q|a\\}$.
Consider $q|z+kn\Leftrightarrow k\equiv-zn^{-1}\pmod{q}$, and note $0\leq
k\leq d-1,q|d$, therefore $|A_{q}|=\frac{d}{q}$.
We can use the principle of inclusion-exclusion to count the elements $a\in A$
such that $\gcd(a,dn)=1$

$\sum_{i=0}^{|P_{d}^{\prime}|}(-1)^{i}\sum_{S\subseteq
P_{d}^{\prime},|S|=i}|A_{\prod_{p\in
S}p}|=\sum_{i=0}^{|P_{d}^{\prime}|}(-1)^{i}\sum_{S\subseteq
P_{d}^{\prime},|S|=i}\frac{d}{\prod_{p\in S}p}=d\prod_{p\in
P_{d}^{\prime}}(1-\frac{1}{p})=\frac{\varphi(dn)}{\varphi(n)}.$

Because all the solution sets of $x$ for different $b\in B$ are disjoint, we
obtain the total number of solutions over all $B$ is
$|B|\frac{\varphi(dn)}{\varphi(n)}$.

######  Corollary 2.3.

Consider integers $0\leq\ell<n$, $y\in\mdmathbb{Z}_{n,d}$. The number of
solutions $x\in\mdmathbb{Z}^{*}_{n}$ such that $xb\equiv y\pmod{n}$ for some
$b\leq\ell$ is

$\frac{\varphi(\frac{n}{d},\left\lfloor\frac{\ell}{d}\right\rfloor)}{\varphi(\frac{n}{d})}\varphi(n).$

  * Proof

Since $x\in\mdmathbb{Z}_{n}^{*}$, we see that $xb\equiv y\pmod{n}$ if and only
if $d|b$, $x\frac{b}{d}\equiv\frac{y}{d}\pmod{\frac{n}{d}}$, and
$\frac{b}{d}\leq\left\lfloor\frac{\ell}{d}\right\rfloor$. We can then apply
section 2.1 and obtain the number of solutions is
$\varphi(n/d,\left\lfloor\ell/d\right\rfloor)\varphi(n)/\varphi(n/d)$.

The following is a highly technical theorem from sieve theory.

######  Theorem 2.4 (Brun’s sieve [3, p.93] ).

Let $\mathcal{A}$ be any set of natural number $\leq x$ (i.e. $\cal{A}$ is a
finite set) and let $\mathcal{P}$ be a set of primes. For each prime
$p\in\mathcal{P}$, Let $\mathcal{A}_{p}$ be the set of elements of
$\mathcal{A}$ which are divisible by $p$. Let $\mathcal{A}_{1}:=A$ and for any
squarefree positive integer $d$ composed of primes of $\mathcal{P}$ let
$\mathcal{A}_{d}:=\cap_{p|d}A_{p}$. Let $z$ be a positive real number and let
$P(z):=\prod_{p\in\mathcal{P},p<z}p$.
We assume that there exist a multiplicative function $\gamma(\cdot)$ such
that, for any $d$ as above,

$|\mathcal{A}_{d}|=\frac{\gamma(d)}{d}X+R_{d}$

for some $R_{d}$, where

$X:=|A|.$

We set

$S(\mathcal{A},\mathcal{P},z):=|\mathcal{A}\backslash\cup_{p|P(z)}\mathcal{A}_{p}|=|\\{a:a\in\mathcal{A},\gcd(a,P(z))=1\\}|$

and

$W(z):=\prod_{p|P(z)}(1-\frac{\gamma(p)}{p}).$

Supposed that
1.$|R_{d}|\leq\gamma(d)$ for any squarefree $d$ composed of primes of
$\mathcal{P}$;
2.there exists a constant $A_{1}\geq 1$ such that

$0\leq\frac{\gamma(p)}{p}\leq 1=\frac{1}{A_{1}};$

3.there exists a constant $\kappa\geq 0$ and $A_{2}\geq 1$ such that

$\sum_{w\leq p<z}\frac{\gamma(p)\log
p}{p}\leq\kappa\log\frac{z}{w}+A_{2}\quad\text{if}\quad 2\leq w\leq z.$

4.Let $b$ be a positive integer and let be a real number satisfying

$0\leq\lambda e^{1+\lambda}\leq 1.$

Then

$\displaystyle S(\mathcal{A},\mathcal{P},z)\geq$ $\displaystyle
XW(z)\\{1-\frac{2{}^{2b}e^{2\lambda}}{1-{}^{2}e^{2+2\lambda}}\exp((2b+2)\frac{c_{1}}{\lambda\log
z})\\}$ $\displaystyle+O(z^{2b-1+\frac{2.01}{e^{2\lambda/\kappa}-1}}),$

where

$c_{1}:=\frac{A_{2}}{2}\\{1+A_{1}(\kappa+\frac{A_{2}}{\log 2})\\}.$

##  3 Number theoretical results

This section we show some number theoretical bounds. The results are
technical. The reader can skip the proofs of this section on first view.

###  3.1 Estimate for relative totient function

This section proves a good estimate of $\varphi(n,\ell)$ using sieve theory,
the direction was hinted in [6].

######  Theorem 3.1.

There exists positive constant $c$, such that

$\varphi(n,\ell)=\begin{cases}\Omega(\frac{\ell}{n}\varphi(n))&\text{ if
}\ell>c\log^{5}n\\\ \Omega(\frac{\ell}{\log\ell})&\text{ if }\ell>c\log n\\\
\end{cases}$

  * Proof

Case 1. $\ell>c\log^{5}n$.

Let $z$ be a value we will define later.

Let $n_{0}=\prod_{p|n,p<z}p$, we can see $\varphi(n,\ell)$ and
$\varphi(n_{0},\ell)$ are close.

$\displaystyle|\varphi(n,\ell)-\varphi(n_{0},\ell)|$
$\displaystyle=\left|\sum_{0\leq{m}\leq{\ell},(m,n_{0})=1}1-\sum_{0\leq{m}\leq{\ell},(m,n)=1}1\right|$
$\displaystyle\leq\sum_{1\leq{m}\leq{\ell}:p|n,p\geq z,p|m}1$
$\displaystyle\leq\sum_{p|n,p\geq z}\frac{\ell}{p}$
$\displaystyle\leq\frac{\ell\omega(n)}{z}$
$\displaystyle\leq\frac{c_{1}\ell\log{n}}{z\log\log n}$

Now, we want to estimate $\varphi(n_{0},\ell)$ using the Brun’s sieve. The
notations are from the theorem. Let
$\mathcal{A}=\\{1,2,\ldots,\ell\\},\mathcal{P}=\\{p:p|n\\},X=|\mathcal{A}|=\ell$,
the multiplicative function $\gamma(p)=1$ if $p\in\mathcal{P}$ otherwise $0$.

    * ·

Condition (1). For any squarefree $d$ composed of primes of $\mathcal{P}$,

$\displaystyle|R_{d}|$
$\displaystyle=\left|\left\lfloor\frac{\ell}{p}\right\rfloor-\frac{\ell}{p}\right|\leq
1=\gamma(d).$

    * ·

Condition (2). We choose $A_{1}$ = 2, therefore
$0\leq\frac{\gamma(p)}{p}=\frac{1}{p}\leq\frac{1}{2}=1-\frac{1}{A_{1}}$.

    * ·

Condition (3). Because $R(x):=\sum_{p<x}\frac{\log p}{p}=\log x+O(1)$ [3], we
have

$\sum_{w\leq p<z}\frac{\gamma(p)\log{p}}{p}\leq\sum_{w\leq
p<z}\frac{\log{p}}{p}=R(z)-R(w)=\log{\frac{z}{w}}+O(1).$

We can choose $\kappa=1$ and some $A_{2}$ large enough to satisfy Condition
(3).

    * ·

Condition (4). By picking $b=1,\lambda=\frac{2}{9}$, $b$ is a positive integer
and $0<\frac{2}{9}e^{11/9}\approx 0.75<1$.

We are ready to bound $\varphi(n_{0},\ell)$. Brun’s sieve shows

$\displaystyle\varphi(n_{0},\ell)=S(\mathcal{A},\mathcal{P},z)\geq$
$\displaystyle\ell\frac{\varphi(n_{0})}{n_{0}}\left(1-\frac{2{}^{2b}e^{2\lambda}}{1-{}^{2}e^{2+2\lambda}}\exp((2b+2)\frac{c_{1}}{\lambda\log
z})\right)$ $\displaystyle+O(z^{2b-1+\frac{2.01}{e^{2\lambda/\kappa}-1}})$
$\displaystyle\geq$
$\displaystyle\ell\frac{\varphi(n_{0})}{n_{0}}\left(1-0.3574719\exp(\frac{18c_{1}}{\log
z})\right)+O(z^{4.59170})$

Which means that there exists some positive constant $c_{2}$ such that for
some small $\varepsilon>0$,

$\varphi(n_{0},\ell)\geq\ell\frac{\varphi(n_{0})}{n_{0}}\left(1-\frac{2}{5}\exp(\frac{18c_{1}}{\log
z})\right)-c_{2}z^{5-\varepsilon}.$

We choose some constant $z_{0}$ such that $\frac{2}{5}\exp(\frac{18c_{1}}{\log
z_{0}})\leq\frac{1}{2}$, if $z>z_{0}$(we will later make sure $z>z_{0}$), then

$\varphi(n_{0},\ell)\geq\frac{1}{2}\ell\frac{\varphi(n_{0})}{n_{0}}-c_{2}z^{5-\varepsilon}.$

Note if $n_{1}|n_{2}$, then $\varphi(n_{1})/n_{1}\geq\varphi(n_{2})/n_{2}$
since $\varphi(n)/n=\prod_{p|n}(1-1/p)$ and every prime factor of $n_{1}$ is
also the prime factor of $n_{2}$. Therefore,

$\varphi(n_{0},\ell)\geq\frac{1}{2}\ell\frac{\varphi(n)}{n}-c_{2}z^{5-\varepsilon}.$

Recall there exists a $c_{3}$ such that
$\frac{\varphi(n)}{n}\geq\frac{c_{3}}{\log\log n}$,

$\displaystyle\varphi(n,\ell)$
$\displaystyle\geq\varphi(n_{0},\ell)-c_{1}\frac{\ell\log n}{z\log\log n}$
$\displaystyle\geq\frac{1}{2}\ell\frac{\varphi(n)}{n}-c_{2}z^{5-\varepsilon}-c_{1}\frac{\ell\log
n}{z\log\log n}$
$\displaystyle=\frac{1}{4}\ell\frac{\varphi(n)}{n}+(\frac{1}{8}\ell\frac{\varphi(n)}{n}-c_{2}z^{5-\varepsilon})+(\frac{1}{8}\ell\frac{\varphi(n)}{n}-c_{1}\frac{\ell\log
n}{z\log\log n})$
$\displaystyle\geq\frac{1}{4}\ell\frac{\varphi(n)}{n}+(\frac{c_{3}}{8}\frac{\ell}{\log\log
n}-c_{2}z^{5-\varepsilon})+(\frac{c_{3}}{8}\frac{\ell}{\log\log
n}-c_{1}\frac{\ell\log n}{z\log\log n}).$

By picking

$z=\frac{8c_{1}}{c_{3}}\log n=C\log n,$

we obtain

$c_{1}\frac{\ell\log n}{z\log\log n}\leq\frac{c_{3}}{8}\frac{\ell}{\log\log
n}.$

By picking $c=8\frac{c_{2}}{c_{3}}C^{5}$ and

$\ell\geq\frac{8c_{2}}{c_{3}}C^{5}\log^{5-\varepsilon}n\log\log
n=c\log^{5-\varepsilon}n\log\log n,$

we obtain

$cz^{5-\varepsilon}\leq\frac{\ell}{\log\log n}.$

Recall for the above to be true we require $z>z_{0}$, note $z=C\log n$, for
$n$ is sufficiently large is enough.

We obtain if $n$ is sufficiently large and $\ell\geq c\log^{5}n\geq
c\log^{5-\varepsilon}n\log\log n$, then
$\varphi(n,\ell)\geq\frac{\ell}{4n}\varphi(n)$. Thus for all $n$ and $\ell\
\geq c\log^{5}n$, $\varphi(n,\ell)=\Omega(\ell\frac{\varphi(n)}{n})$.

Case 2. $\ell>c\log n$.

Observe that for all $\ell\leq n$, $\varphi(n,\ell)\geq
1+\pi(\ell)-\omega(n)$. This is because the primes no larger than $\ell$ are
relatively prime to $n$ if it is not a factor of $n$, and $1$ is also
relatively prime to $n$.

We show there exists a constant $c$ such that
$\varphi(n,\ell)=\Omega(\frac{\ell}{\log\ell})$ for $\ell\geq c\log n$, by
showing $\frac{1}{2}\pi(\ell)\geq\omega(n)$. There exists constant
$c_{1},c_{2}$ such that $\pi(\ell)\geq c_{1}\frac{\ell}{\log\ell}$ and
$\omega(n)\leq c_{2}\frac{\log n}{\log\log n}$. Therefore, we want some
$\ell$, such that $\frac{c_{1}}{2}\frac{\ell}{\log\ell}\geq c_{2}\frac{\log
n}{\log\log n}$. It is true as long as $\ell\geq c\log n$ for some
sufficiently large $c$.

Noting the $c$ in two parts of the proof might be different, we pick the the
larger of the two to be the one in the theorem.

As a corollary, we prove Theorem 3.2.

######  Theorem 3.2.

There exists a constant $c$, such that for any $n$, and a divisor $d$ of $n$,
if $\frac{\ell}{c\log^{5}n}\geq d$, then each element in $\mdmathbb{Z}_{n,d}$
is covered $\Omega(\frac{n}{\ell}\varphi(n))$ times by
$\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{n})$.

  * Proof

By section 2.1, the number of segments in
$\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{n})$ covering some fixed element in
$\mdmathbb{Z}_{n,d}$ is $\frac{\varphi(n/d,\ell/d)}{\varphi(n/d)}\varphi(n)$.
As long as $\varphi(n,\ell)$ where $\ell$ is not too small,
$\varphi(n,\ell)=\Omega(\frac{\ell}{n}\varphi(n))$. In particular, by Theorem
3.1, if $\lfloor\ell/d\rfloor\geq c\log^{5}(n/d)$, we have
$\varphi(n/d,\ell/d)/\varphi(n/d)=\Omega(\frac{\ell}{n})$. Therefore, each
element in $\mdmathbb{Z}_{n,d}$ is covered $\Omega(\frac{\ell}{n}\varphi(n))$
times.

###  3.2 Large divisor with small divisor sum

######  Theorem 3.3.

If $r=n^{O(\frac{1}{\log\log\log n})}$, then there exists $m|n$, such that
$m\geq r$, $d(m)=r^{O(\frac{1}{\log\log r})}$ and $\sigma(m)=O(m)$.

  * Proof

If there is a single prime $p$, such that $p^{e}|n$ and $p^{e}\geq r$, then we
pick $m=p^{e^{\prime}}$, where $e^{\prime}$ is the smallest integer such that
$p^{e^{\prime}}\geq r$. One can see $d(m)=e^{\prime}=O(\log
r)=r^{O(\frac{1}{\log\log r})}$, also
$\sigma(m)=m(1-\frac{1}{p})\geq\frac{m}{2}$, and we are done.

Otherwise, we write $n=\prod_{i=1}^{k}p_{i}^{e_{i}}$, where each $p_{i}$ is a
distinct prime number. The prime $p_{i}$ are ordered by the weight
$w_{i}=e_{i}p_{i}\log p_{i}$ in decreasing order. That is $w_{i}\geq w_{i+1}$
for all $i$. Let $j$ be the smallest number such that
$\prod_{i=1}^{j}p_{i}^{e_{i}}\geq r$. Let $m=\prod_{i=1}^{j}p_{i}^{e_{i}}$.

First, we show $d(m)$ is small. Let $m^{\prime}=m/p_{j}^{e_{j}}$. One can see
that $m^{\prime}<r$.

$\displaystyle d(m)\leq 2d(m^{\prime})=r^{O(\frac{1}{\log\log r})}$

To show that $\sigma(m)=O(m)$, we show $\varphi(m)=\Theta(m)$. Indeed, by
$\sigma(m)\leq\frac{m^{2}}{\varphi(m)}$, we obtain $\sigma(m)=O(m)$.

For simplicity, it is easier to work with sum instead of products, so we take
logarithm of everything and define $t=\log n$.

By our definition, $\log r\leq\frac{t}{\log\log t}$ and
$\sum_{i=1}^{k}e_{i}\log p_{i}=t$.

Let $j$ be the smallest number such that $\sum_{i=1}^{j}e_{i}\log
p_{i}\geq\log r$. This also implies $\sum_{i=1}^{j}e_{i}\log p_{i}<2\log
r\leq\frac{2t}{\log\log t}$.

Now, consider $e^{\prime}_{1},\ldots,e^{\prime}_{k}$, such that the following
holds.

    * item

$\sum_{i=1}^{j}e_{i}\log p_{i}=\sum_{i=1}^{j}e_{i}^{\prime}\log p_{i}$, and
$e_{i}^{\prime}p_{i}\log p_{i}=c_{1}$ for some $c_{1}$, when $1\leq i\leq j$,

    * item

$\sum_{i=j+1}^{k}e_{i}\log p_{i}=\sum_{i=j+1}^{n}e_{i}^{\prime}\log p_{i}$,
$e_{i}^{\prime}p_{i}\log p_{i}=c_{2}$ for some $c_{2}$, where $j+1\leq i\leq
k$.

Note $c_{1}$ and $c_{2}$ can be interpreted as weighted averages. Indeed,
consider sequences $x_{1},\ldots,x_{n}$ and $y_{1},\ldots,y_{n}$, such that
$\sum_{i}x_{i}=\sum_{i}y_{i}$. If for some non-negative $a_{1},\ldots,a_{n}$,
we have $a_{i}y_{i}=c$ for all $i,j$, then $c\leq\max_{i}a_{i}x_{i}$. Indeed,
there exists $x_{j}\geq y_{j}$, so $\max_{i}a_{i}x_{i}\geq a_{j}x_{j}\geq
a_{j}y_{j}=c$. Similarly, $c\geq\min_{i}a_{i}x_{i}$. This shows $c_{1}\geq
c_{2}$, because $c_{2}\leq\max_{i=j+1}^{k}w_{i}=w_{j+1}\leq
w_{j}=\min_{i=1}^{j}w_{i}\leq c_{1}$.

We first give a lower bound of $c_{2}$.

$\sum_{i=j+1}^{k}\frac{c_{2}}{p_{i}}=\sum_{i=j+1}^{k}e^{\prime}_{i}\log
p_{i}\geq t(1-\frac{2}{\log\log t})\geq\frac{t}{2}$.

$\sum_{i=j+1}^{k}\frac{c_{2}}{p_{i}}\leq
c_{2}\sum_{i=1}^{k}\frac{1}{p_{i}}\leq c_{2}\sum_{p\text{
prime},p=O(t)}\frac{1}{p}\leq c_{2}\log\log t$.

This shows $c_{2}\log\log t\geq\frac{t}{2}$, or $c_{2}\geq\frac{t}{2\log\log
t}$.

Since $c_{1}\geq c_{2}$,
$\sum_{i=1}^{j}\frac{1}{p_{i}}=\sum_{i=1}^{j}\frac{e_{i}^{\prime}\log
p_{i}}{c_{1}}\leq\frac{\frac{2t}{\log\log
t}}{c_{1}}\leq\frac{\frac{2t}{\log\log t}}{\frac{t}{2\log\log t}}=4$.

Note $\varphi(m)=m\prod_{i=1}^{j}(1-\frac{1}{p_{i}})$. Because
$-2x<\log(1-x)<-x$ for $0\leq x\leq 1/2$, so
$\sum_{i=1}^{j}\log(1-\frac{1}{p_{i}})\geq-2\sum_{i=1}^{j}\frac{1}{p_{i}}=-\Theta(1)$.
Hence $\prod_{i=1}^{j}(1-\frac{1}{p_{i}})=\Theta(1)$, and
$\varphi(m)=\Theta(m)$.

Some interesting number theoretical results are direct corollary of Theorem
3.3.

######  Corollary 3.4.

For positive integer $n$, there exists a $m|n$ such that
$m=n^{\Omega(\frac{1}{\log\log\log n})}$ and $\sigma(m)=O(m)$.

It would be interesting to know if the above corollary is tight.

######  Lemma 3.5.

Let $m|n$ and $m\geq\frac{n}{s}$, then $\mdmathbb{D}_{n}^{\leq
s}\odot\mdmathbb{D}_{m}=\mdmathbb{D}_{n}$.

  * Proof

Consider divisor $d$ of $n$, let $d_{1}=\gcd(m,d)\in\mdmathbb{D}_{m}$, and
$d_{2}=d/d_{1}$. $d_{2}|\frac{n}{m}\leq s$, so $d_{2}\in\mdmathbb{D}_{n}^{\leq
s}$.

######  Corollary 3.6.

For $s\leq n$, there exists a $B$ such that $\mdmathbb{D}_{n}^{\leq s}\odot
B=\mdmathbb{D}_{n}$ and
$|B|=(\frac{n}{s})^{O(\frac{1}{\log\log\frac{n}{s}})}$.

  * Proof

Let $r=\frac{n}{s}$, and let $m$ be the one in the construction in Theorem
3.3. Let $B=\mdmathbb{D}_{m}$. Note in the proof of Theorem 3.3, we showed
$|B|=d(m)=r^{O(\frac{1}{\log\log r})}$ without using requiring any information
on how large $r$ has to me. Also, $\mdmathbb{D}_{n}^{\leq s}\odot
B=\mdmathbb{D}_{n}$ by section 3.2.

##  4 $\ell$-covering

In this section, we prove our bounds in $f(n,\ell)$ and also provide a quick
randomized construction.

###  4.1 Upper bound

The high level idea is to split the problem to sub-problems of covering
multiple $\mdmathbb{Z}_{n,d}$. Can we cover $\mdmathbb{Z}_{n,d}$ for many
distinct $d$, using only a small number of segments in
$\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{n})$? We answer the question
affirmatively. For the rest of this section, $s=\frac{\ell}{c\log^{5}n}$,
where $c$ is the constant in Theorem 3.1. Define $g(n,\ell)$ to be the size of
the smallest set cover of $\bigcup_{d|n,d\leq s}\mdmathbb{Z}_{n,d}$ using
$\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{n})$.

We bound $g(n,\ell)$ using the fact that each element is covered many times,
and the combinatorial set cover upper bound Theorem 2.1.

######  Theorem 4.1.

$g(n,\ell)\leq\begin{cases}O(\frac{n}{\ell}\log\ell)&\text{ if }\ell\geq
c\log^{5}n\\\ O(\frac{\varphi(n)}{\ell}\log^{2}\ell)&\text{ if }\ell\geq c\log
n\\\ \varphi(n)&\text{ for all }\ell.\end{cases}$

  * Proof

We consider $3$ cases.

Case 1. If $\ell>c\log^{5}n$, then
$\varphi(n,\ell)=\Omega(\frac{\ell}{n}\varphi(n))$ by Theorem 3.1. By Theorem
2.1, there exists a cover of size

$g(n,\ell)=O\left(\frac{\varphi(n)\log\ell}{\frac{\ell}{n}\varphi(n)}\right)=O\left(\frac{n}{\ell}\log\ell\right).$

Case 2. If $\ell\geq c\log n$, then we obtain

$g(n,\ell)=O\left(\frac{\varphi(n)\log\ell}{\frac{\ell}{\log\ell}}\right)=O\left(\frac{\varphi(n)}{\ell}\log^{2}\ell\right).$

Note this requires the fact that $\log^{2}\ell=\Omega((\log\log
n)^{2})\geq\frac{n}{\varphi(n)}=O(\log\log n)$.

Case 3. The last case is trivial,
$g(n,\ell)\leq|\mdmathbb{Z}^{*}_{n}|=\varphi(n)$.

Our approach is to find some set $B\subseteq\mdmathbb{D}_{n}$, and for each
$b\in B$, we generate a cover of all $\bigcup_{d\leq s}\mdmathbb{Z}_{n,b\odot
d}$ using $\mathcal{S}_{\ell}(\mdmathbb{Z}_{n,b})$, by Theorem 3.2. Certainly,
$B$ has to be chosen so $\mdmathbb{D}_{n}^{\leq s}\odot B=\mdmathbb{D}_{n}$.

Since want to find some $B$ such that $\mdmathbb{D}_{n}^{\leq s}\odot
B=\mdmathbb{D}_{n}$. Then each sub-problem is precisely using
$\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{\frac{n}{b}})$ to cover $\bigcup_{d\leq
s,d|\frac{n}{b}}\mdmathbb{Z}_{\frac{n}{b},d}$ for $b\in B$. Hence we obtain

$f(n,\ell)\leq\sum_{b\in B}g(\frac{n}{b},\ell).$

There can be many choices of $B$, but we need to make sure $|B|$ is not too
large when $s$ is large. Also, we need to make sure the number of segments
chosen over $\mathcal{S}_{\ell}(\mdmathbb{Z}^{*}_{b})$ for all $b\in B$ is
also small. Here are the two possible choice we use in our construction.

  1. 1.

Let $B=\mdmathbb{D}_{n}^{>s}\cup\\{1\\}$. If $d\leq s$, then $d=d\cdot 1$, if
$d>s$, then $d=1\cdot d$. Hence $\mdmathbb{D}_{n}^{\leq s}\odot
B=\mdmathbb{D}_{n}$.

  2. 2.

Let $m|n$, $m\geq\frac{n}{s}$ and $B=\mdmathbb{D}_{m}$. section 3.2 showed
that $\mdmathbb{D}_{n}^{\leq s}\odot B=\mdmathbb{D}_{n}$.

The first choice works well when $\ell$ is not too large.

######  Lemma 4.2.

There is a constant $c$, such that $f(n,\ell)=O(\frac{n}{\ell}\log n)$ if
$\ell\leq n^{1-\frac{c}{\log\log n}}$.

  * Proof

Let $B=\\{d\mid d\in\mdmathbb{D}_{n},d\geq s\\}\cup\\{1\\}$. Observe that
$|B|\leq d(n)=n^{O(\frac{1}{\log\log n})}\leq\frac{n}{\ell}$. $|B|$ is
dominated by our desired bound of $O(\frac{n}{\ell}\log n)$, and hence
irrelevant.

#### Case 1

If $\ell<c\log n$, then we are done, since $f(n,\ell)\leq
n=O(\frac{n}{\ell}\log n)$.

#### Case 2

Consider $\ell>c\log^{5}n$.

$\displaystyle f(n,\ell)$ $\displaystyle\leq\sum_{d\in B}g(\frac{n}{d},\ell)$
$\displaystyle\leq\sum_{d\in B}\frac{n}{d}\frac{\log\ell}{\ell}+1$
$\displaystyle=|B|+\frac{n\log\ell}{\ell}+\frac{\log\ell}{\ell}\sum_{d\in
B\setminus\\{1\\}}\frac{n}{d}$ $\displaystyle=O\left(\frac{n\log
n}{\ell}\right)+\frac{\log\ell}{\ell}\sum_{d\in B\setminus\\{1\\}}\frac{n}{d}$

Hence, we are concerned with the last term.

We further separate into $2$ cases. If $\ell<n^{\frac{c}{\log\log n}}$,

$\displaystyle\frac{\log\ell}{\ell}\sum_{d\in B\setminus\\{1\\}}\frac{n}{d}$
$\displaystyle\leq\frac{\sigma(n)\log\ell}{\ell}$
$\displaystyle\leq\frac{n\log\log n\log\ell}{\ell}$
$\displaystyle=O\left(\frac{n\log\log n\frac{\log n}{\log\log
n}}{\ell}\right)$ $\displaystyle=O\left(\frac{n\log n}{\ell}\right)$

Otherwise $\ell\geq n^{\frac{c}{\log\log n}}$. Since all values in
$B\setminus\\{1\\}$ is at least $s$, so we know that. $\sum_{d\in
B\setminus\\{1\\}}\frac{n}{d}\leq|B|\frac{n}{s}$. In particular, there is a
universal constant $c$, such that $|B|\leq\frac{n^{\frac{c}{\log\log
n}}}{c\log^{u}n}\leq s$.

$\displaystyle\frac{\log\ell}{\ell}\sum_{d\in B\setminus\\{1\\}}\frac{n}{d}$
$\displaystyle\leq|B|\frac{n}{s}\frac{\log\ell}{\ell}$
$\displaystyle=O\left(\frac{n\log\ell}{\ell}\right)$
$\displaystyle=O\left(\frac{n\log n}{\ell}\right)$

#### Case 3

Finally, consider $c\log n\leq\ell\leq c\log^{5}n$.

$\displaystyle f(n,\ell)$ $\displaystyle\leq\sum_{d\in B}g(\frac{n}{d},\ell)$
$\displaystyle\leq\sum_{d\in
B}\left(\varphi(n/d)\frac{(\log\ell)^{2}}{\ell}+1\right)$ $\displaystyle\leq
O(\frac{n}{\ell}\log^{2}\ell)$ $\displaystyle=O\left(\frac{n}{\ell}(\log\log
n)^{2}\right)$ $\displaystyle=O\left(\frac{n\log n}{\ell}\right)$

We are ready to prove the main theorem by handling the case when $\ell$ is
large using the second choice.

######  Theorem 4.3 (Main).

There exists a $\ell$-covering of size $O(\frac{n\log n}{\ell})$ for all
$n,\ell$ where $\ell<n$.

  * Proof

When $\ell\leq n^{1-\frac{c}{\log\log n}}$, section 4.1 handles it. Otherwise,
$\ell>n^{1-\frac{c}{\log\log n}}$. By Theorem 3.3, there exists a $m|n$, such
that $d(m)=m^{O(\frac{1}{\log\log m})}$, $\sigma(m)=O(m)$ and
$m\geq\frac{n}{s}$. Note $\mdmathbb{D}_{n}^{\leq
s}\odot\mdmathbb{D}_{m}=\mdmathbb{D}_{n}$.

Therefore we can obtain the following.

$\displaystyle f(n,\ell)$
$\displaystyle\leq\sum_{d|m}g\left(\frac{n}{d},\ell\right)$
$\displaystyle\leq\sum_{d|m}\frac{n}{d}\left(\frac{\log n}{\ell}+1\right)$
$\displaystyle\leq\frac{n}{m}\sum_{d|m}\frac{m}{d}\frac{\log n}{\ell}+d(m)$
$\displaystyle=\frac{n}{m}\sigma(m)\frac{\log
n}{\ell}+O\left(\left(\frac{cn\log^{5}n}{\ell}\right)^{\frac{1}{\log\log\frac{n}{s}}}\right)$
$\displaystyle=\frac{n}{m}m\frac{\log
n}{\ell}+O\left(\left(\frac{cn\log^{5}n}{\ell}\right)^{\frac{1}{\log\log
n}}\right)$ $\displaystyle=O\left(\frac{n\log n}{\ell}\right)$

The upper bound automatically leads to a construction algorithm. First find
the prime factorization in $n^{o(1)}$ time, then compute the desired $B$ in
$n^{o(1)}$ time, and then cover each $\bigcup_{d|n/b,d\leq
s}\mdmathbb{Z}_{n/b,d}$ using $\mathcal{S}_{\ell}(\mdmathbb{Z}_{n,b})$ for
$b\in B$. If we use the linear time greedy algorithm for set cover, then the
running time becomes $O(n\ell)$ [11].

One can use a randomized constructive version of Theorem 2.1. The following
result can be proven easily through set cover LP and randomized rounding.

######  Theorem 4.4.

Let there be $t$ sets each with size at most $a$, and each element of the size
$n$ universe is covered by at least $b$ of the sets, then there exists subset
of $O(\frac{t}{b}\log n)$ size that covers the universe, and can be found with
high probability using a Monte Carlo algorithm that runs in
$\tilde{O}(\frac{t}{b})$ time.

  * Proof

The condition shows the set cover LP has a feasible solution where every
indicator variable for each set has value $\frac{1}{b}$. The standard
randomized rounding algorithm of picking each set with probability equals
$\frac{1}{b}$ independently, for $\Theta(\log n)$ rounds, would cover the
universe with high probability [16]. It can be simulated through independently
sample sets of size $\frac{t}{b}$ for $\Theta(\log n)$ rounds instead, which
can be done in $\tilde{O}(\frac{t}{b})$ time.

The main difference is the coverage size between Theorem 4.4 and Theorem 2.1.
The randomized algorithm have a higher factor of $\log n$ instead of $\log a$.
If we use more sophisticated rounding techniques, we can again obtain $\log a$
[14]. However, the algorithm will not be as fast. The change to $\log n$ has a
consequence in the output size. In particular, following the proof of section
4.1, there will be an extra $\log\log n$ factor to the size of the cover.

The analysis is similar as before, and we can obtain the following theorem.

######  Theorem 4.5.

A $O(\frac{n}{\ell}\log n\log\log n)$ size $\ell$-covering of
$\mdmathbb{Z}_{n}$ can be found in $\tilde{O}(\frac{n}{\ell})+n^{o(1)}$ time
with high probability.

###  4.2 Lower bound

We remark our upper bound is the best possible result obtainable through the
combinatorial set covering property (Theorem 2.1). The $\log n$ factor cannot
be avoided when $\ell=n^{\Omega(1)}$. In order to obtain a better bound,
stronger _number theoretical properties_ has to be exploited, as it was for
the case when $n$ is a prime [2].

We show that it is unlikely we can get much stronger bounds when $\ell$ is
small. For infinite many $(n,\ell)$ pairs, our bound is only $\log\log n$
factor away from the lower bound.

######  Theorem 4.6.

There exists a constant $c>0$, where there are infinite number of $n,\ell$
pairs where $f(n,\ell)\geq c\frac{n}{\ell}\frac{\log n}{\log\log n}$.

  * Proof

Let $n$ be the product of the $k$ smallest prime numbers, then
$k=\Theta(\frac{\log n}{\log\log n})$. Let $\ell$ be the smallest number where
$\pi(\ell)=k$. Because $\pi(\ell)=\Theta(\frac{\ell}{\log\ell})$, we know
$\ell=\Theta(\log n)$.

Observe that $\varphi(n,\ell)=1$. Indeed, every number $\leq\ell$ except $1$
has a common factor with $n$. In order to cover all elements in
$\mdmathbb{Z}^{*}_{n}\subseteq\mdmathbb{Z}_{n}$, the $\ell$-covering size is
at least $\varphi(n)=\Omega(\frac{n}{\log\log
n})=\Omega(\frac{n}{\ell}\frac{\log n}{\log\log n})$.

## References

  * [1] Béla Bollobás, Svante Janson, and Oliver Riordan.  On covering by translates of a set.  Random Structures & Algorithms, 38(1-2):33–67, 2011.
  * [2] Zhixiong Chen, Igor E. Shparlinski, and Arne Winterhof.  Covering sets for limited-magnitude errors.  IEEE Transactions on Information Theory, 60(9):5315–5321, September 2013.
  * [3] Alina Carmen Cojocaru, M Ram Murty, et al.  An introduction to sieve methods and their applications, volume 66.  Cambridge University Press, 2006.
  * [4] Harold Davenport, Hugh L Montgomery, and Ann Arbor.  Multiplicative number theory.  Graduate Texts in Mathematics. Springer, New York, NY, 3 edition, October 2000.
  * [5] H Halberstam and HE Richert.  Sieve methods, acad.  Press, London, pages 208–209, 1974.
  * [6] Lucia (https://mathoverflow.net/users/38624/lucia).  Bounds for relative totient function for small values.  MathOverflow.  URL:https://mathoverflow.net/q/252852 (version: 2016-10-23).
  * [7] Anxiao Jiang, Michael Langberg, Moshe Schwartz, and Jehoshua Bruck.  Trajectory codes for flash memory.  IEEE Transactions on Information Theory, 59(7):4530–4541, 2013\.
  * [8] Torleiv Kløve.  On covering sets for limited-magnitude errors.  Cryptography and Communications, 8(3):415–433, July 2016.
  * [9] Torleiv Klove, Jinquan Luo, and Somaye Yari.  Codes correcting single errors of limited magnitude.  IEEE Transactions on Information Theory, 58(4):2206–2219, 2012\.
  * [10] Torleiv Kløve and Moshe Schwartz.  Linear covering codes and error-correcting codes for limited-magnitude errors.  Designs, Codes and Cryptography, 73(2):329–354, November 2014.
  * [11] Konstantinos Koiliaris and Chao Xu.  Faster Pseudopolynomial Time Algorithms for Subset Sum.  ACM Transactions on Algorithms, 15(3):1–20, July 2019.
  * [12] L. Lovász.  On the ratio of optimal integral and fractional covers.  Discrete Mathematics, 13(4):383–390, 1975.
  * [13] Oliver Roche-Newton, Ilya D Shkredov, and Arne Winterhof.  PACKING SETS OVER FINITE ABELIAN GROUPS.  page 9, 2018.
  * [14] Aravind Srinivasan.  Improved Approximation Guarantees for Packing and Covering Integer Programs.  SIAM Journal on Computing, 29(2):648–670, January 1999.
  * [15] S.K Stein.  Two combinatorial covering theorems.  Journal of Combinatorial Theory, Series A, 16(3):391–397, May 1974\.
  * [16] Vijay V. Vazirani.  Approximation Algorithms.  Springer, Berlin ; New York, 2001.