# Red-Giant Branch Stellar Cores as Macroscopic Dark Matter Detectors

Christopher Dessert  Leinweber Center for Theoretical Physics, Department of
Physics, University of Michigan, Ann Arbor, MI 48109 U.S.A.  Berkeley Center
for Theoretical Physics, University of California, Berkeley, CA 94720, U.S.A.
Theoretical Physics Group, Lawrence Berkeley National Laboratory, Berkeley, CA
94720, U.S.A.  Zachary Johnson  Leinweber Center for Theoretical Physics,
Department of Physics, University of Michigan, Ann Arbor, MI 48109 U.S.A.

(August 27, 2024)

###### Abstract

We show that macroscopic dark matter (DM) impacts on the degenerate helium
cores of red-giant branch (RGB) stars can ignite helium fusion via DM-baryon
elastic scattering. The onset of helium burning leads to a characteristic drop
in luminosity and rise in temperature that marks the transition to a
horizontal branch star. We show that such impacts can alter the RGB luminosity
function of globular clusters (GCs), focusing in particular on the GC M15.
Using models of M15 stars constructed with the stellar simulation code MESA,
we compute the expected DM-ignition event rates and the theoretical RGB
luminosity functions under the null and signal hypotheses. We constrain DM
with masses $10^{17}\ {\rm g}\lesssim m_{\chi}\lesssim 10^{20}\ \rm{g}$ and
geometric cross sections $10^{2}\ {\rm cm}^{2}\lesssim\sigma_{\chi n}\lesssim
10^{7}\ \rm{cm}^{2}$ assuming that the DM in M15 is sourced by the background
Milky Way halo. We also place more stringent constraints assuming that M15
formed in a DM subhalo that survives today.

††preprint: LCTP-21-30

###### Contents

  1. I Introduction
  2. II Inducing the HF in Red Giants
  3. III MESA Simulations of M15 RGB stars
  4. IV The DM-Induced He-ignition Rate
  5. V Constraints on Macroscopic DM
  6. VI Discussion
  7. A M15 DM Halo
  8. B Ignition Profile
  9. C Analytic Ignition Rate

##  I Introduction

Dark matter (DM) is known to exist from a multitude of gravitationally-based
evidence accumulated over a century of observation [1]. Much of the
unconstrained DM mass range, which spans from $\sim$ $10^{-22}$ eV fuzzy dark
matter [2] to $\sim$ $5M_{\odot}$ MACHOs [3, 4, 5], lies above the mass scales
involved in the Standard Model (SM). Elementary DM can exist below the Planck
scale, however, more massive DM must be a bound state, typically thought of as
comprising new particles. In this case the DM sector should have a particle-
antiparticle asymmetry to allow bound state coalescence. A wide and continuous
range of interactions can generate DM bound states with masses ranging from
very large nuclei, $m\lesssim\leavevmode\nobreak\ M_{Pl}$ [6, 7, 8], to
nuggets of mass $10^{-7}\leavevmode\nobreak\ \text{ g}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ m\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ 10^{23}$ g [9], and up to substructure of mass
$\gtrsim\leavevmode\nobreak\ M_{\odot}$ [10, 11]. Macroscopic DM can also be
comprised of SM particles or contain SM charges if the bound state is
energetically prevented from decaying to nucleons [12, 13, 14].

Macroscopic DM candidates have sufficiently low event rates as to render
microscopic direct detection experiments, with exposure times $\sim$1 kT yr,
ineffective. However, massive, old astrophysical objects can act as DM
detectors with exposure times $\sim$ $M_{\odot}\times$Gyr
$\approx\leavevmode\nobreak\ 10^{33}$ kT yr. For example, it is well known
that the passage of macroscopic DM through white dwarfs (WD) can deposit
sufficient energy in a local region to ignite a Type 1a supernova [15].
Similarly, macroscopic DM passage in neutron stars can ignite superbursts
[16]. In stars, supersonic DM can dissipate energy in the form of shockwaves,
which travel to the surface, releasing transient UV radiation [17].
Macroscopic DM has also been probed through a host of additional mechanisms
that do not require such extreme exposure times, albeit at lower masses [18,
19, 20, 21, 22, 23, 24].

In this work, we demonstrate that macroscopic DM can ignite helium fusion in
red-giant branch (RGB) stellar cores. An RGB star is a low-mass star which has
completed hydrogen burning on the main sequence but has not yet begun helium
burning. It has an inert electron-degenerate pure-helium core surrounded by a
hydrogen-fusing shell. In the absence of macroscopic dark matter, shell fusion
will continue to heat the core for $\sim 0.5$ Gyr, over which time the
luminosity of the RGB star rises — this continues until the critical
temperature for helium ignition is reached in the core. Because degeneracy
pressure is independent of temperature, the energy released heats the core,
further increasing the fusion rate. The entire core ignites in a runaway
reaction known as the “helium flash” (HF). The only outwardly observable
signal is the essentially instantaneous drop in luminosity of the star over
$\sim$ $10-50$ kyrs, due to expansion and subsequent cooling. The transition
of the RGB star onto the next stage of stellar evolution, the horizontal
branch (HB), then takes place over $\sim$ $2$ Myrs.

The HF can occur prematurely if significant energy is deposited in the core.
When a macroscopic DM particle traverses the degenerate core of an RGB star,
elastic collisions between DM and the stellar material can generate enough
heat to initiate local helium fusion, in an early-onset HF. The star undergoes
the transition to the HB which in the extreme would entirely eliminate the RGB
as a phase of stellar evolution. To capture cases in which only some fraction
of RGB stars are subject to a DM-induced HF, we constrain DM using the
measured RGB luminosity function (LF), which is the observed number of RGB
stars as a function of their luminosity.

The RGB core temperatures and densities increase with time, so the high-
luminosity RGB stars already closest to undergoing the standard HF are more
easily ignited by DM. The presence of macroscopic DM steepens the LF, since
fewer high-luminosity stars survive. To probe this new mechanism, we use the
MESA code [25] to simulate the evolution of the RGB stars in the globular
cluster (GC) M15 and compute theoretical LFs to compare to the M15 LF computed
in Ref. [26]. Old GCs such as M15 are good targets for this search because
they are well-studied and host many RGB stars which were formed in similar
conditions, e.g. in similar metallicity environments. We focus on M15 because
it is the only GC for which an LF has been directly constructed and presented.
The LF can be computed for many other GCs using their Hertzsprung-Russell
diagrams, but this is beyond the scope of this work. Additionally, as we will
discuss, if the GC formation was seeded by an early universe DM overdensity,
then the surviving DM density may be orders of magnitude greater than the
Milky Way (MW) density at that location. We assume the standard Milky Way DM
halo density for our fiducial constraint, but discuss the much stronger limit
obtained if future measurements determine that M15 hosts its own DM halo.

In Sec. II, we examine the physics of the HF and the DM-induced ignition
mechanism. In Sec. III, we detail the MESA simulations of the M15 RGB stars
used in this work. In Sec. IV, we discuss the computation of the DM-induced HF
rate. In Sec. V, we discuss our construction of the LFs and show the 95%
limits on macroscopic DM parameters from the observed M15 LF. Finally, we
conclude and discuss additional targets and methods to improve detection
prospects in Sec. VI.

##  II Inducing the HF in Red Giants

In order to prematurely ignite the helium core, DM must deposit enough energy
to initiate helium fusion before that energy diffuses away. The ignition of
significant helium fusion in a large region will generate a stable flame-
front, or deflagration [27]. In this work, we assume that such an energy
deposition occurs through SM elastic scattering off macroscopic DM with
sufficient interaction strength that the resulting cross section is geometric.

For such a DM candidate undergoing elastic scattering, the average energy
transfer per nuclei is $\mathcal{O}(m_{n}v_{\chi}^{2})$, giving a linear
energy deposition rate of [28]

$\displaystyle\frac{dE}{dx}=\sigma_{\chi n}\rho_{\star}v_{\chi}^{2}.$ (1)

Where $\rho_{*}$ is the stellar density, which varies strongly throughout the
star, and $v_{\chi}$ the DM velocity at that depth in the star. The DM
deposits energy in a cylinder with length a substantial portion of the star,
and cross-sectional area given by the geometric cross section. This energy
deposition has only local effects, and is hence unobservable (but see [17]),
unless it ignites a runaway fusion reaction. A runaway reaction will occur
when the local energy generation rate by fusion exceeds the energy loss rate,
which is dominated by diffusion. To estimate these rates, we must assume a
temperature profile immediately after the DM impact. We work in cylindrical
coordinates where the longitudinal axis points along the direction of the DM
path and $r$ is the distance from the center of the DM path. We assume the
energy deposition is linearly increasing from the edge of the cylinder
($r=\sqrt{\sigma_{\chi n}/\pi}$) to the center, yielding

$\displaystyle\frac{dE}{dV}=\frac{3}{\sigma_{\chi
n}}\left(1-\dfrac{r}{\sqrt{\sigma_{\chi n}/\pi}}\right)\frac{dE}{dx}.$ (2)

This profile is just one example of a heat deposition profile. We vary the
energy deposition profile and find that if they are not sharply peaked at the
center, the effect on the ignition parameter can be $\mathcal{O}(1)$; see
Appendix B for further discussion. We then compute the temperature $T_{\rm
hot}$ that the energy deposition heats the stellar material to, via
numerically solving

$\displaystyle\frac{dE}{dx}=\rho\sigma_{\chi n}\int^{T_{\rm
hot}}_{T_{*}}c_{v}dT.$ (3)

We use analytic approximations for the heat capacities of the electrons, ions
and photons, which are

$\displaystyle c_{v}^{e^{-}}$
$\displaystyle=\left\\{\begin{array}[]{ll}\dfrac{7\pi^{2}}{15}\dfrac{k_{B}^{4}}{\hbar^{3}c^{3}}\dfrac{T^{3}}{\rho_{*}}&T>10^{9}K\vspace{0.2cm}\\\
\dfrac{3k_{B}}{m_{{}^{4}{\rm He}}}&T_{degen}<T<10^{9}K\vspace{0.2cm}\\\
\dfrac{4k_{B}^{2}T}{m_{{}^{4}{\rm
He}}E_{F}\pi^{2}}&T<T_{degen},\end{array}\right.$ (7) $\displaystyle
c_{v}^{\gamma}$
$\displaystyle=\frac{4}{15}\pi^{2}\frac{k_{B}^{4}}{\hbar^{3}c^{3}}\frac{T^{3}}{\rho_{*}},$
(8) $\displaystyle c_{v}^{ion}$ $\displaystyle=\dfrac{3k_{B}}{2m_{{}^{4}{\rm
He}}}.$ (9)

where $T_{degen}=\leavevmode\nobreak\ 3E_{F}/\pi^{2}k_{B}$, for $E_{F}$ the
Fermi energy, and $10^{9}$ K approximates the transition to a relativistic
electron gas. We neglect the relativistic degenerate electron regime because
the electron contributes negligibly to the heat capacity when it applies.

The dominant fusion process is helium fusion, specifically through the triple-
alpha process, wherein three 4He fuse through the resonant Hoyle state to
create a 12C nucleus. The triple-alpha energy generation rate is [27]

$\displaystyle\dot{S}_{3\alpha}=5.1\left(\frac{\rho_{*}(r)}{10^{4}{\rm\
g/cm^{2}}}\right)^{2}\left(\frac{X({\rm
He})}{T_{9}(r)}\right)^{3}e^{-4.4/T_{9}(r)}{\rm\frac{ergs}{s\ g}},$ (10)

where $T_{9}(r)\equiv T(r)/(10^{9}$ K). Electron screening enhances the rate
at low temperatures, however this effect is $\lesssim 5\%$ at $5\times 10^{8}$
K, where the nuclear generation rate is already quite low and so is neglected.
Note that carbon fusion, which operates at similar temperatures, is suppressed
in the initial ignition by the low carbon abundance. Thus we use Eq. (10) to
determine the local energy generation rate, which can be expressed as

$\displaystyle\frac{d\dot{E}_{\rm nuc}}{dx}$
$\displaystyle=2\pi\int\dot{S}(r)\rho_{*}rdr.$ (11)

The heated region cools off via diffusion at a rate of

$\displaystyle\frac{d\dot{E}_{\rm diff}}{dx}=-2\pi
kr\frac{dT}{dr}\bigg{|}_{r=\sqrt{\sigma/\pi}}$ (12)

where $k$ is the thermal conductivity. Runaway nuclear fusion will occur if
the generated heat is greater than that lost through diffusion. To see this
explicitly, we define an ignition parameter, $\zeta$, as

$\displaystyle\zeta$
$\displaystyle\equiv\frac{d\dot{E}_{\textrm{nuc}}/dx}{d\dot{E}_{\textrm{diff}}/dx}.$
(13)

Ignition occurs for $\zeta>1$. We will see that for typical points in our
constrained region, this ratio is far greater than $1$.

##  III MESA Simulations of M15 RGB stars

Figure 1:  Left Panel The internal temperature (black) and density (red)
profiles of the 0.79 $M_{\odot}$ star when it is 13 Gyr old. Right Panel The
central temperature (black) and central density (red) of the 0.79 $M_{\odot}$
star as a function of time during the RGB phase, which spans the x-axis of the
plot. Figure 2: Main Plot The luminosity of the 0.79 $M_{\odot}$ star as a
function of time during the RGB phase, which spans the x-axis of the plot.
Inset The same as the main plot but zoomed in around the red giant bump.

In this section, we describe our MESA simulations of the RGB stars in the GC
M15. We use MESA version 12115 [25] to simulate the evolution of the RGB
stars. The age of M15 is $13\pm 1$ Gyr [26]; we fix its age at 13 Gyr. Under
this assumption, the masses of the RGB stars in M15 range from
$0.785M_{\odot}$ (just ascending the RGB) to $0.795M_{\odot}$ (at the end of
the RGB phase). The metallicity of the M15 GC is [Fe/H]$\leavevmode\nobreak\
=\leavevmode\nobreak\ -2.1$ [26], which corresponds to an average isotopic
abundance of [Z]$\leavevmode\nobreak\ =\leavevmode\nobreak\ -1.57$ [29] — we
fix this to be the initial abundance in the MESA simulations.

We simulate stars of initial mass $M_{*}$ between $0.785$ and $0.795M_{\odot}$
in steps of $0.001M_{\odot}$ from the pre-main sequence through the beginning
of central helium ignition. The MESA simulations return one-dimensional
(radial) profiles of temperature $T$, density $\rho$, and isotopic
compositions at many time points throughout the evolution, along with bulk
properties of the star: age $t$, luminosity $L(t)$, effective temperature
$T_{\rm eff}(t)$ and surface gravity $g(t)$. We use these stellar models to
(i) compute the expected DM-induced HF rate in each star and (ii) compute the
theoretical LFs under the null and signal hypotheses.

In the left panel of Fig. 1, we show the temperature and density profiles, at
$t=13$ Gyr, of the star with mass ${}\mkern 3.0mu\overline{\mkern-3.0muM}$ in
the center of the range, ${}\mkern
3.0mu\overline{\mkern-3.0muM}\leavevmode\nobreak\ \equiv\leavevmode\nobreak\
0.790\leavevmode\nobreak\ M_{\odot}$. Over the full mass range we focus on in
this work, the stellar properties in the RGB phase are the same as those shown
here to $<1\%$. The helium core occupies $\sim$1$\%$ of the stellar radius,
when the temperature and density sharply drop traversing farther out of the
star. The vast majority of the star by volume is the low-density stellar
envelope, which at this time extends out to $\sim$4 $R_{\odot}$, though the
envelope will continue to expand in size until the HF. In the right panel, we
show the time-evolution of the central temperature and density, which sharply
increase as the star nears the flash. The lower and upper x-limit of the plot
corresponds to when the star enters the RGB phase at $\sim$12.68 Gyr and when
the HF occurs at $\sim$13.27 Gyr, corresponding to a total RGB duration for
this star of $T_{\rm RGB}^{{}\mkern 3.0mu\overline{\mkern-3.0muM}}=590$ Myr.
We parameterize the fraction of the RGB branch ascended by the star by $\tau$,

$\tau\equiv\dfrac{t-t_{\rm TAMS}}{T_{\rm RGB}},$ (14)

where $t_{\rm TAMS}$ is the terminal age main sequence, the age at which the
star begins to ascend the RGB, and $T_{\rm RGB}$ is the length of the RGB
phase. Therefore $\tau=0$ defines when the star begins the RGB phase and
$\tau=1$ when the standard HF occurs and the star moves onto the HB. Note that
the explicit mapping between $t$ and $\tau$ depends on the stellar mass
through $t_{\rm TAMS}$ and $T_{\rm RGB}$.

In Fig. 2, we show the luminosity evolution of the star. Based on this plot,
we can reconstruct the two basic features of the LF by making the
approximation that there are the same number of stars in each age interval.
Firstly, because the luminosity increases faster with increasing age, there
will be more stars at lower luminosities. Therefore, the LF will sharply
increase towards lower luminosities. Secondly, at $\sim$13.24 Gyr, the
luminosity abruptly stops increasing for a few Myr (see the inset). As the
hydrogen-burning shell expands outwards, it reaches a composition
discontinuity created by the first dredge-up, which leads to a brief halt in
the luminosity increase. Because of this, stars spend a longer time at this
luminosity level. This is known as the red giant bump [30, 31], and indeed in
the LF there is a small bump at this luminosity.

##  IV The DM-Induced He-ignition Rate

Figure 3:  Top Panels: The maximum ignition parameter, $\zeta$, described in
Eq.(13), for a simulated DM trajectory assuming an initial angular momentum
$\ell_{0}=10^{-4}c\times 10^{10}$ cm, where $10^{10}\text{cm}=0.14\
R_{\odot}$, and the benchmark mass ${}\mkern 3.0mu\overline{\mkern-3.0muM}$
star. In light grey are constraints from non-observation of DM-induced Type Ia
supernova in WDs [32, 16](triangular shape) and from microlensing [33]
(vertical line). Top Left: 100 Myr before the expected HF ( total RGB phase
duration is $T_{\rm RGB}\sim 590$ Myr). Top Right: 1 Myr remaining in the RGB
phase. Bottom Panels: The rate of DM induced HF ignition
$\Gamma^{\overline{M}}$[Gyr-1], with correction factor $c(t)$ set to $1$ for
comparison purposes, see Eq. (16). Bottom Left: $100$ Myr before the nominal
HF. Bottom Right: Ignition rate $1$ Myr before HF.

The rate at which DM trajectories ignite a given stellar core depends
sensitively on the details of the DM distribution. There are two basic
assumptions one can make; either the GC formed within a DM overdensity that
survives today, or that it did not and the only DM around is that of the Milky
Way (MW) halo. This first assumption is nominally the expectation of the
standard model of cosmology, and would give a DM density orders of magnitude
above the MW halo density. However, there is a lack of supporting
observational evidence. In [34] a prototypical GC was found to contain very
little DM under modest assumptions, and [35] found that GCs closer than $100$
kpc to the Galactic Center typically have halos that have already merged with
the galaxy halo (M15 is $\sim 10$ kpc from the Galactic Center). Numerical
simulations of the GC DM halo scenario find that tidal stripping can
significantly reduce the amount of DM, however this still would likely leave
some portion of the DM within the tidal radius [36, 35, 37, 38], and this
scenario is often assumed in the literature [39, 40, 17].

Due to the lack of a complete consensus, we place our fiducial limits assuming
the DM density in M15 is purely that of the MW DM halo, and defer our analysis
including a GC DM halo to App. A.

We model the MW halo with the NFW profile [41, 42] from [43] with scale factor
$r_{s}=20$ kpc, normalized such that distance of Earth to the Galactic Center
is $8.12$ kpc [44]. In the context of this profile, we infer a MW halo DM
density at the location of M15 today, 10.76 kpc from the Galactic Center [45],
of $\rho_{\text{DM}}\leavevmode\nobreak\ =\leavevmode\nobreak\
0.35\leavevmode\nobreak\ \pm\leavevmode\nobreak\ 0.10$ GeV cm-3, and we assume
the lower 1$\sigma$ value $0.25$ GeV cm-3 in our analysis. However, M15 has a
galactic orbital period of $\sim$140 Myr with a $\sim 3.7-4$ kpc periapsis, so
that its local DM density periodically changes by a factor $\sim$4.8 over the
length of the RGB phase, $\sim$600 Myr. This orbit was computed numerically in
Ref. [46] by evolving the M15 orbital trajectory backwards in the galactic
gravitational potential in [47], and in our analysis we assume the best-fit
orbit provided. We assume the DM velocity distribution is given by the
standard halo model,

$\displaystyle\begin{split}f({\bf v},t)=&N\text{exp}\left(-\frac{({\bf
v+v_{GC}}(t))^{2}}{2\sigma_{vr}^{2}}\right)\\\
&\times\Theta(v_{esc}-|\mathbf{v}+\mathbf{v}_{GC}(t)|).\end{split}$ (15)

for normalization $N$, radial velocity dispersion given by the upper $1\sigma$
value from [43], $\sigma_{vr}=167$ km s-1, and a MW escape velocity $v_{esc}$
of $544$ km s-1. The stellar velocity within M15 is $\approx 10$ km s-1, thus
to a good approximation all stars move at the GC velocity. At the present
location of M15, we find $v_{GC}=123\leavevmode\nobreak\
\pm\leavevmode\nobreak\ 1.1\ $km s-1.

The depth to which the DM must penetrate is to the ignition radius of the star
$R_{\zeta=1}(\tau)$, where again $\tau$ is the proportion of the RGB branch a
given star in M15 has gone through. For DM with initial velocity $v_{0}$, the
rate of impacts within radius $R_{\zeta=1}$ is enhanced by a gravitational
focusing factor of
$\left(1+\left(v^{*}_{\text{esc}}(r)/v_{0}\right)^{2}\right)$, where $r$ is
the distance of the DM from the center of the star. The $v_{\text{esc}}$ at
the core is $\sim 10^{3}$ km $s^{-1}$, so we approximate this effect with
$\left(v_{*\text{esc}}(r)/v_{0}\right)^{2}$.111One may also think there is a
gravitational focus from the GC potential, however this effect is not
independent of the stellar focusing and including this effect increases the
rate only by $v^{2}_{GC\text{esc}}/v^{2}_{*\text{esc}}\sim 10^{-4}$.  These
effects can be analytically integrated, which we show in App. C. We divide
these contributions to the DM-induced ignition rate into contributions that
depend only on stellar evolution (i.e., the time-dependence is given only by
$\tau$) and those that depend on the GC location throughout the galaxy, where
the time-dependence is on $t$ directly.

$\displaystyle\Gamma(t,\tau)$ $\displaystyle=\Gamma_{0}\times
c(t,v_{GC},v_{\text{esc}})$ (16) $\displaystyle\Gamma_{0}(\tau)$
$\displaystyle=2\sqrt{2\pi}\frac{\rho_{DM}(t_{0})}{m_{\chi}}R^{2}_{\zeta=1}(\tau)\sigma_{vr}\times\frac{v^{2}_{*\text{esc}}(R_{\zeta=1}(\tau))}{2\sigma_{vr}^{2}}$
(17)

Where $t_{0}$ implies evaluation at the position of M15 today. The correction
factor $c(t,v_{GC},v_{\text{esc}})$ includes the finite MW escape velocity,
and the variation of $v_{GC}$ and $\rho_{DM}$ over time as the GC orbits the
MW. It varies within $c(t)\ \epsilon\ [0.87,2.47]$ with large values occuring
when the GC passes near the galactic center and its higher DM density. We
detail its computation in App. C and show our results in Fig. C.1.

The value of $R_{\zeta=1}$ is determined by simulation of a DM infall to the
benchmark star $\overline{M}=0.79\ M_{\odot}$. We use MESA generated profiles
of the stellar density as a function of radius, and the friction force derived
from Eq. (1). We simulate DM trajectories starting at infinity with varying
impact parameters $b$, scanning over signal parameters ${\bm{\theta}_{s}}$ and
at multiple stellar ages $t$. For each point in the scan, $R_{\zeta=1}$ is
defined as the largest radius at which the trajectory ignites the star,
typically of order $10^{9}$ cm. We implement Fehlberg’s $4^{th}(5^{th})$ order
method and use an error tolerance per step of $10$ m and $10^{-9}c$. We
verified this procedure by checking that in selected cases the global error
estimate was within $10\%$.

An important simplification is that the DM trajectory depends only on the
initial angular momentum per unit mass, $\ell=bv_{0}^{\text{max}}$, rather
than individually on $b$, and velocity at infinity, $v_{0}$, within $\sim
10\%$ below $v_{0}\approx 5\times 10^{-3}c$. Further, the rate of stellar
ignition depends only on the maximum angular momentum, $\ell^{\text{max}}$,
defined by the largest $\ell$ that satisfies our ignition condition,
$\zeta>1$. Trajectories directly towards the star, defined by small
$\ell_{0}$, impact both deeper in the core and at higher velocities, leading
to larger $\zeta$, see Eq. (13). Trajectories with larger initial angular
momentum may result in DM which only skims the core, or in extreme cases
undergoes multiple orbits, resulting in lower $\zeta$. Thus all smaller
$\ell_{0}$ will also ignite. This allows us to eliminate a dimension from our
parameter scan. Thus explicitly what we determine from simulation is the
maximum $\ell=R_{\zeta=1}v_{*\text{esc}}(R_{\zeta=1})$ that causes ignition,
yielding a rate of

$\displaystyle\Gamma^{{}\mkern
3.0mu\overline{\mkern-3.0muM}}({\bm{\theta}_{s}},t)=\sqrt{2\pi}\frac{\rho_{DM}(t_{0})}{m_{\chi}}\frac{\ell_{\rm
max}({\bm{\theta}_{s}},\tau)^{2}}{\sigma_{v_{r}}}\times
c(t,v_{GC},v_{\text{esc}})$ (18)

for our benchmark star.

In the top panels of Fig. 3 we simulate DM trajectories for fixed initial
angular momentum, plotting the maximum ignition ratio $\zeta$ for each
$m_{\chi}$ and $\sigma_{\chi n}$. The left and right panels are for two stars
of the same mass $\overline{M}$ but of different ages, corresponding to 100
and 1 Myr before the standard HF respectively. The triangular shape of each
$\zeta$ contour can be understood simply. The series of “hypotenuses” mark
where the DM loses significant kinetic energy in the stellar envelope. The
white region begins where the DM loses all initial kinetic energy before
reaching the core. The slope of these lines are close to unity as the
acceleration from friction is $\propto\sigma_{\chi n}/m_{\chi}$. Moving
perpendicularly away from the hypotenuse towards larger $m_{\chi}$ and smaller
$\sigma_{\chi n}$ increases the depth at which the DM penetrates. Far away
from this line, friction is irrelevant so the only relevant parameter for
$\zeta$ is $\sigma_{\chi n}$, where lower cross section corresponds to
decreased energy deposition by Eq. (1), until ignition is no longer possible.
We can see from the relative location of the $\zeta=1$ contour in the left and
right panels that as the star approaches the standard HF, smaller cross
sections may ignite the star, consistent with Eq. (2).

In the bottom panels we plot the simulated rate of igniting DM impacts on a
star in M15 for the same two ages. The minimum igniting cross section
decreases over time, following the $\zeta=1$ contour in the top panels. Near
the minimum $\sigma_{\chi n}$ the contours turn sharply due to the rapid
decrease in the portion of the core with sufficient temperature and density to
be ignited by a given cross section. Where the rate is non-zero in both left
and right panels, we see the overall rate increases with time due to the
larger maximum igniting impact parameter for stars closer to their nominal HF.

##  V Constraints on Macroscopic DM

In this section, we outline our modeling of the theoretical LFs under the dark
matter hypothesis and assess their goodness-of-fit to the measured M15 LF.

Although previously in Sec. III we had qualitatively discussed the LF as a
function of $L$, the observable is the apparent $V$-magnitude. M15 was
observed three times between 2002 and 2004 by the Hiltner 2.4m telescope at
the Michigan-Dartmouth-MIT Observatory at Kitt Peak, Arizona. Ref. [26] used
that data to construct the LF between apparent visual magnitudes
$V\leavevmode\nobreak\ \in\leavevmode\nobreak\ [13.94,17.94]$ (except $V$
between $14.34$ and $14.74$) by [26], shown in Fig. 4, and we fit our
theoretical LFs to that data in this work. Explicitly, we start with the
number of stars $N_{i}$ in bin $i$ corresponding to apparent visual magnitude
$V_{i}$ with bin widths of $0.2$ magnitudes. We will refer to this data as
${\bm{d}}=\\{N_{i}\\}$. In particular, the red-giant bump is visible around
15.5 $V$-magnitudes. We mask the four data points between $15.14$ and $15.94$
$V$, where the model in [26] did not accurately capture all of the physics of
the red-giant bump (our null model, also in Fig. 4, is nearly identical to
that found in [26]). The relation between $L$ and $V$ is given by

$\displaystyle V(t;M_{*})=$
$\displaystyle-2.5\log\left(\dfrac{L(t;M_{*})}{L_{\odot}}\right)$ (19)
$\displaystyle+4.74+\mu-BC_{\rm V}(t,T_{\rm eff},g)$ (20)

where $\mu$ is the dereddened distance modulus with best fit $\hat{\mu}=14.86$
[26] and we compute bolometric corrections in the $V$-band $BC_{\rm V}$ with
the python package isochrones [48].

To construct a theoretical LF for the cluster, we need to know the DM-induced
flash rate and the $V$ as a function of time for the range of possible stellar
initial masses in the cluster. The former we have detailed the calculation of
in Sec. IV for the ${}\mkern 3.0mu\overline{\mkern-3.0muM}$ model. To compute
the latter, we start from the luminosity-age relations $L(t;M_{*})$ generated
by MESA and compute $V(t;M_{*})$ as in Eq. (20).

Figure 4:  The M15 LF (black data points) with uncertainties given by
$\sqrt{N_{i}}$. In red, we show the best-fit LF with no DM ignition. In black,
we show the LFs with $m_{\chi}=3\times 10^{18}$ g and $\sigma_{\chi n}=4\times
10^{3}$ cm2 (dashed), $\sigma_{\chi n}=4\times 10^{4}$ cm2 (dotted),
$\sigma_{\chi n}=10^{5}$ cm2 (solid). The hatched region indicates those four
bins around the RGB bump which are masked in the analysis.

We now make the assumption that the GC evolution is coeval [26, 49]. Then the
stellar ages are all $t_{\rm M15}=13$ Gyr, with V magnitudes $V(t_{\rm
M15};M_{*})$. Finally, we invert this relation to obtain the initial stellar
mass as a function of $V$ magnitude today, $M_{*}(V)$. For a particular signal
model ${\bm{\theta}_{s}}$, the expected number of stars in $V$ magnitude bin
$i$ spanning magnitudes $V_{i}^{\rm min}$ to $V_{i}^{\rm max}$ is

$\displaystyle\lambda_{i}({\bm{\theta}_{s}})=A\times
C_{i}\int_{{M_{*}(V_{i}^{\rm min}})}^{M_{*}(V_{i}^{\rm
max})}dM\dfrac{dN}{dM}(M)P_{\rm surv}({\bm{\theta}_{s}},M)$ (21)

where $A$ is an arbitrary normalization constant to be fit to the data and
$C_{i}$ is the completeness factor in bin $i$ computed via artificial star
tests in [26]. $dN(M)/dM$ is the initial mass function, which we take to have
a Salpeter form $dN(M)/dM\propto M^{-2.35}$ [50]. The integration limits are
entirely determined by stellar physics, while the DM physics is only captured
in the survival probability $P_{\rm surv}({\bm{\theta}_{s}},M)$, which we
compute as follows. As detailed in Sec. IV, we have simulated the DM-induced
ignition rate $\Gamma^{{}\mkern
3.0mu\overline{\mkern-3.0muM}}({\bm{\theta}_{s}},t,\tau)$ for the mass
${}\mkern 3.0mu\overline{\mkern-3.0muM}$ star. Then

$\displaystyle P_{\rm
surv}({\bm{\theta}_{s}},M_{*})=\exp\left(-\int_{0}^{t_{\rm M15}}dt\
\Gamma^{M_{*}}({\bm{\theta}_{s}},t,\tau)\right),$ (22)

which implicitly assumes that the DM-induced ignition rates are equal across
stellar masses at fixed percentage of time completed on the RGB stage $\tau$.
Note that the rates are always zero unless the star is on the RGB.

In Fig. 4 we show the theoretical LFs
$\lambda=\\{\lambda_{i}({\bm{\theta}_{s}})\\}$ for three separate cases, along
with the measured completeness-corrected LF of M15. The LF with no DM-ignition
has the shallowest slope, and the red giant bump is clearly visible in the bin
around $V=15.6$ magnitudes. We then show three curves under the model
assumption $m_{\chi}=3\times 10^{18}$ g, at $\sigma_{\chi n}=\\{4\times
10^{3}$ cm2, $4\times 10^{4}$ cm2, $10^{5}$ cm2}. Tracing these curves from
high to low $V$, they tend to follow the no DM-ignition line at until a
particular $V$ at which DM-ignition turns on, which sharpens the slope of the
LF. Recall that stars with lower $V$ are more highly evolved, and so have
smaller survival probabilities. The DM model with the smallest cross section
$\sigma_{\chi n}=4\times 10^{3}$ cm2 is in the region where increasing cross
section decreases the survival probability, because the increased cross
section increases the energy deposition in the core. The model with the
largest cross section $\sigma_{\chi n}=10^{5}$ cm2 lies in the region where
increasing cross section increases the survival probability because the DM has
lost significant kinetic energy in the stellar envelope. The model with
middling cross section $\sigma_{\chi n}=4\times 10^{4}$ cm2 delineates the
boundary between these two regions, and as such has the minimum survival
probability for any DM with that mass. The LFs for other DM masses display
similar behavior.

With the model in the same form as the data, we can write down the joint
likelihood over $V$ magnitude bins

$\displaystyle\mathcal{L}({\bm{d}}|{\bm{\theta}_{s}},{\bm{\theta}_{\rm
nuis}})=\prod_{i}\mathcal{N}(\lambda_{i}({\bm{\theta}_{s}})-N_{i},\sqrt{N_{i}})$
(23)

where the nuisance parameters ${\bm{\theta}_{\rm nuis}}=\\{A,\mu\\}$. $A$, as
mentioned previously, is a normalization parameter that sets the total number
of RGB stars in M15. $\mu$ is the distance modulus for M15, which we let float
around its central value $\hat{\mu}$. $\mathcal{N}(x,\sigma_{x})$ is the
Gaussian likelihood with a mean $x$ and standard deviation $\sigma_{x}$.

We construct the profile likelihood at fixed mass $m_{\chi}$ as a function of
the cross section $\sigma_{\chi n}$, given by

$\displaystyle\mathcal{L}({\bm{d}}|{\bm{\theta}_{s}})=\mathcal{L}({\bm{d}}|{\bm{\theta}_{s}},\hat{{\bm{\theta}}}_{\rm
nuis})$ (24)

where $\hat{{\bm{\theta}}}_{\rm nuis}$ denotes the values of
${\bm{\theta}_{\rm nuis}}$ that maximize the likelihood at that
${\bm{\theta}_{s}}$. To define the region ruled out by this analysis, we
construct the test statistic [51]

$\displaystyle
q({\bm{\theta}_{s}})=\left\\{\begin{array}[]{ll}2\left[\ln\mathcal{L}({\bm{d}}|m_{\chi},\hat{\sigma}_{\chi
n})-\ln\mathcal{L}({\bm{d}}|{\bm{\theta}_{s}})\right]&\hat{\sigma}_{\chi
n}\leq\sigma_{\chi n}\vspace{0.05cm}\\\ 0&\hat{\sigma}_{\chi n}>\sigma_{\chi
n}\end{array}\right.$ (27)

where $\hat{\sigma}_{\chi n}$ is the value of the cross section that maximize
the likelihood at that mass. We exclude at 95% confidence the cross sections
for which $q({\bm{\theta}_{s}})>2.71.$ We additionally apply the Asimov
procedure to the null hypothesis to compute the expected limits [51], and
power-constrain the reported limits [52], although the latter was not
necessary in practice. We do not find any evidence of DM-induced He flash
events in this analysis.

Figure 5:  The red line is the 95% limit on macroscopic DM from the non-
observation of DM-induced He flashes in the GC M15 LF; the region inside this
line is excluded. The dashed line is the Asimov expectation with green
(yellow) bands denoting the 1$\sigma$ (2$\sigma$) containment region. We
assume that the M15 DM is dominantly from the MW halo. We additionally show
constraints from the non-observation of DM-induced Type Ia supernova in WDs
[32, 16] and from microlensing [33]. Macroscopic DM is bounded from above from
CMB observations [53] and the non-observations of gas cloud heating [54],
although at too large cross-section to be shown on this plot. We also show as
a dotted line where the DM is nuclear density $\rho_{0}=2\times 10^{14}$
g/cm3.

We show the 95% limit on macroscopic DM from this search in Fig. 5, and
compare with the expected sensitivity under the null hypothesis from the
Asimov procedure. The analogous plot assuming a GC overdensity is shown in
Appendix Fig. A.1. At fixed $m_{\chi}$, the limits cut off at small
$\sigma_{\chi n}$ below which the DM deposits too little energy to ignite
helium fusion in the core. As $\sigma_{\chi n}$ increases, the signal
increases until the cross section is so large that the DM is slowed by the
stellar envelope. In that case, when the DM reaches the stellar core, it has
too little kinetic energy remaining to ignite fusion, which cuts off the
bounded region at large $\sigma_{\chi n}$. At high masses, the sensitivity
decreases because the DM number density is too low for collisions to occur in
the lifetime of the RGB stars. Nominally the above arguments suggest that the
shape of the excluded region should be a right triangle, as discussed in Sec.
IV. However, the time-dependence of the star over the RGB lifetime distorts
this simple picture. At lower DM masses, the DM flux increases, so that we
have increased sensitivity to DM-induced ignition in older stars. These stars
can be ignited by DM with lower cross sections than their younger
counterparts. Therefore, the bottom of the excluded region is slanted upwards
rather than flat like the DM-induced ignition rates as in Fig. 3.

##  VI Discussion

We have outlined a process wherein macroscopic DM can collide with an RGB star
core, depositing sufficient energy to ignite helium fusion. The result is the
premature end to the RGB stage of stellar evolution for that star. The RGB
luminosity function is a sensitive probe of this process; we use the LF of the
GC M15 to constrain macroscopic DM properties.

A crucial assumption in our work is that the the DM-baryon scattering is
purely elastic with geometric cross section. The elastic assumption breaks
down if the binding energy of DM constituents is of order of the typical
energy transfer $\sim$ MeV. This would unbind the DM, resulting in a smaller
penetration depth, but increased local energy deposition as the DM breaks up.
Even in the elastic scattering regime, whether or not the cross section is
geometric depends on the DM substructure, the resulting form factor and the
mean free path within the DM. It is left for future work to see how relaxing
these assumptions could modify our constraints. For example, primordial black
holes clearly do not obey this assumption [55], though we do not constrain
black hole densities in any case.

There are GC targets with improved sensitivity to this mechanism, although
without existing LF data as in the case of M15. If a GC is found to host a DM
halo, that GC would likely provide the strongest bound on macroscopic DM from
this mechanism (see App. A for an application of this scenario to M15). But we
need not rely on the possibility of GC DM substructure. In particular, the GC
M54 has a much larger DM density than that of M15 because it is located at the
center of the Sagittarius dwarf galaxy. Ref. [56] estimated that the
Sagittarius DM density at the location of M54 is $\sim$7 GeV cm-3, although if
the DM profile is cusped the density could be orders of magnitude larger.
Future measurements of the LF in M54 would have improved discovery potential
over that of M15, in particular at high DM masses $m_{\chi}>10^{21}$ g. The
star clusters in the Galactic Center may also be sensitive probes of DM-
induced HFs, given the extreme DM densities reached there. In fact, there is a
lack of luminous RGB stars in the central $\sim$0.3 pc relative to
expectations [57, 58], where there may be a DM spike around Sagittarius A
[59]. Qualitatively, the missing red giants may be explained by DM-induced
helium ignition, although we leave a quantitative assessment to future work
and note that more standard explanations have been suggested [60, 61, 62, 63,
64, 65, 66].

In this work we elected not to use the well studied tip of the red-giant
branch to constrain the mechanism. The LF is more sensitive in the faint-
signal regime where only a small percentage of high-luminosity RGB stars have
been struck by DM; the slope of the LF can significantly increase even though
the TRGB may be similar to that in the null case, for example if some RGB
stars survive to undergo the standard HF. However, there can be some cases
where the TRGB is affected, which would affect the calibration of the Hubble
constant so that its value is dependent on the DM density in the vicinity of
the RGB population.

In future work, we will investigate additional probes of this mechanism. For
instance, the early ignition of the HF leads to HB stars with smaller helium
cores than typical of HB stars. Therefore, there may be a set of sub-HB stars
at lower luminosity than the normal HB, consisting of stars which did not
ascend the full RGB due to DM impacts. Additionally, the DM impacts may
simultaneously ignite fusion in the whole core at once, whereas in the
standard scenario the HF ignites in a series of layers over a longer
timescale, which may affect direct observations of individual stars. However,
observations have not yet resolved this transitionary period and
distinguishing such stars from RGB or HB stars would likely prove difficult.

In principle, one can also study a HF triggered by the accumulation and
annihilation of DM. However, this mechanism is suppressed relative the
analogous bound in WDs [15] for two reasons. Firstly, RGB stars have a much
lower DM capture rate than WDs due to their low core densities. Secondly, pure
helium matter ignition requires a larger energy injection than the ignition of
the carbon/oxygen matter of WDs. Then the annihilating DM must be more massive
than in the WD case, so the DM number density is also suppressed.

###### Acknowledgements.

We thank Fred Adams for collaboration in the early stages of this work. We
thank Holger Baumgardt for sharing data related to the M15 orbit. We thank
Joshua Foster, Andrew Long, Aaron Pierce, and Benjamin Safdi for useful
conversations. Z.J. was supported in part by DOE grant DE-SC0007859. C.D. was
supported in part by the DOE Early Career Grant DE-SC0019225. C.D. and Z.J.
were partially supported by the Leinweber Graduate Fellowship at the
University of Michigan, Ann Arbor. This research was supported in part through
computational resources and services provided by Advanced Research Computing
at the University of Michigan, Ann Arbor.

## References

  * [1] G. Bertone and D. Hooper, “History of dark matter,” Rev. Mod. Phys. 90 no. 4, (2018) 045002, arXiv:1605.04909 [astro-ph.CO].
  * [2] W. Hu, R. Barkana, and A. Gruzinov, “Cold and fuzzy dark matter,” Phys. Rev. Lett. 85 (2000) 1158–1161, arXiv:astro-ph/0003365.
  * [3] B. Carr and F. Kuhnel, “Primordial Black Holes as Dark Matter: Recent Developments,” Ann. Rev. Nucl. Part. Sci. 70 (2020) 355–394, arXiv:2006.02838 [astro-ph.CO].
  * [4] M. A. Monroy-Rodríguez and C. Allen, “The End of the MACHO Era, Revisited: New Limits on MACHO Masses from Halo Wide Binaries,” Astrophys. J.  790 no. 2, (Aug., 2014) 159, arXiv:1406.5169 [astro-ph.GA].
  * [5] T. D. Brandt, “Constraints on MACHO Dark Matter from Compact Stellar Systems in Ultra-Faint Dwarf Galaxies,” Astrophys. J. Lett. 824 no. 2, (2016) L31, arXiv:1605.03665 [astro-ph.GA].
  * [6] G. Krnjaic and K. Sigurdson, “Big Bang Darkleosynthesis,” Phys. Lett. B 751 (2015) 464–468, arXiv:1406.1171 [hep-ph].
  * [7] E. Hardy, R. Lasenby, J. March-Russell, and S. M. West, “Big Bang Synthesis of Nuclear Dark Matter,” JHEP 06 (2015) 011, arXiv:1411.3739 [hep-ph].
  * [8] M. I. Gresham, H. K. Lou, and K. M. Zurek, “Early Universe synthesis of asymmetric dark matter nuggets,” Phys. Rev. D 97 no. 3, (2018) 036003, arXiv:1707.02316 [hep-ph].
  * [9] Y. Bai, A. J. Long, and S. Lu, “Dark Quark Nuggets,” Phys. Rev. D 99 no. 5, (2019) 055047, arXiv:1810.04360 [hep-ph].
  * [10] J. H. Chang, D. Egana-Ugrinovic, R. Essig, and C. Kouvaris, “Structure Formation and Exotic Compact Objects in a Dissipative Dark Sector,” JCAP 03 (2019) 036, arXiv:1812.07000 [hep-ph].
  * [11] M. R. Buckley and A. DiFranzo, “Collapsed Dark Matter Structures,” Phys. Rev. Lett. 120 no. 5, (2018) 051102, arXiv:1707.03829 [hep-ph].
  * [12] E. Witten, “Cosmic Separation of Phases,” Phys. Rev. D 30 (1984) 272–285.
  * [13] Y. Bai and A. J. Long, “Six Flavor Quark Matter,” JHEP 06 (2018) 072, arXiv:1804.10249 [hep-ph].
  * [14] B. W. Lynn, A. E. Nelson, and N. Tetradis, “STRANGE BARYON MATTER,” Nucl. Phys. B 345 (1990) 186–209.
  * [15] P. W. Graham, R. Janish, V. Narayan, S. Rajendran, and P. Riggins, “White Dwarfs as Dark Matter Detectors,” Phys. Rev. D98 no. 11, (2018) 115027, arXiv:1805.07381 [hep-ph].
  * [16] J. S. Sidhu and G. D. Starkman, “Reconsidering astrophysical constraints on macroscopic dark matter,” arXiv:1912.04053 [astro-ph.CO].
  * [17] A. Das, S. A. R. Ellis, P. C. Schuster, and K. Zhou, “Stellar Shocks From Dark Matter,” arXiv:2106.09033 [hep-ph].
  * [18] A. de Rujula and S. L. Glashow, “Nuclearites-a novel form of cosmic radiation,” Nature (London) 312 no. 5996, (Dec., 1984) 734–737.
  * [19] P. B. Price, “Limits on contribution of cosmic nuclearites to galactic dark matter,” Phys. Rev. D 38 no. 12, (Dec., 1988) 3813–3814.
  * [20] J. Singh Sidhu, R. M. Abraham, C. Covault, and G. Starkman, “Macro detection using fluorescence detectors,” JCAP 02 (2019) 037, arXiv:1808.06978 [astro-ph.HE].
  * [21] J. Singh Sidhu, R. J. Scherrer, and G. Starkman, “Death and serious injury from dark matter,” Phys. Lett. B 803 (2020) 135300, arXiv:1907.06674 [astro-ph.CO].
  * [22] J. S. Sidhu and G. Starkman, “Macroscopic Dark Matter Constraints from Bolide Camera Networks,” Phys. Rev. D 100 no. 12, (2019) 123008, arXiv:1908.00557 [astro-ph.CO].
  * [23] N. Starkman, J. Sidhu, H. Winch, and G. Starkman, “Straight lightning as a signature of macroscopic dark matter,” Phys. Rev. D 103 no. 6, (2021) 063024, arXiv:2006.16272 [astro-ph.CO].
  * [24] V. Cooray, G. Cooray, M. Rubinstein, and F. Rachidi, “Could macroscopic dark matter (macros) give rise to mini-lightning flashes out of a blue sky without clouds?,” arXiv:2107.05338 [physics.ao-ph].
  * [25] B. Paxton, L. Bildsten, A. Dotter, F. Herwig, P. Lesaffre, and F. Timmes, “Modules for experiments in stellar astrophysics (mesa),” The Astrophysical Journal Supplement Series 192 no. 1, (Dec, 2010) 3. http://dx.doi.org/10.1088/0067-0049/192/1/3.
  * [26] D. K. Feuillet, N. E. Q. Paust, and B. Chaboyer, “BVI Photometry and the Red Giant Branch Luminosity Function of M15,” Publications of the Astronomical Society of the Pacific 126 no. 942, (Aug., 2014) 733, arXiv:1406.4883 [astro-ph.SR].
  * [27] F. X. Timmes, “Physical properties of laminar helium deflagrations,” The Astrophysical Journal 528 no. 2, (Jan, 2000) 913–945. https://doi.org/10.1086%2F308203.
  * [28] A. De Rujula and S. L. Glashow, “Nuclearites: A Novel Form of Cosmic Radiation,” Nature 312 (1984) 734–737.
  * [29] C. West and A. Heger, “Metallicity-dependent Galactic Isotopic Decomposition for Nucleosynthesis,” Astrophys. J.  774 no. 1, (Sept., 2013) 75, arXiv:1203.5969 [astro-ph.SR].
  * [30] H. C. Thomas, “Sternentwicklung VIII. Der Helium-Flash bei einem Stern von 1\. 3 Sonnenmassen,” Zeitschrift fur Astrophysik 67 (Jan., 1967) 420.
  * [31] I. Iben, “Age and Initial Helium Abundance of Stars in the Globular Cluster M15,” Nature (London) 220 no. 5163, (Oct., 1968) 143–146.
  * [32] R. Janish, V. Narayan, and P. Riggins, “Type Ia supernovae from dark matter core collapse,” Phys. Rev. D100 no. 3, (2019) 035008, arXiv:1905.00395 [hep-ph].
  * [33] N. Smyth, S. Profumo, S. English, T. Jeltema, K. McKinnon, and P. Guhathakurta, “Updated Constraints on Asteroid-Mass Primordial Black Holes as Dark Matter,” Phys. Rev. D 101 no. 6, (2020) 063005, arXiv:1910.01285 [astro-ph.CO].
  * [34] R. Ibata, C. Nipoti, A. Sollima, M. Bellazzini, S. C. Chapman, and E. Dalessandro, “Do globular clusters possess dark matter haloes? A case study in NGC 2419,” MNRAS 428 no. 4, (Feb., 2013) 3648–3659, arXiv:1210.7787 [astro-ph.CO].
  * [35] B. F. Griffen, M. J. Drinkwater, P. A. Thomas, J. C. Helly, and K. A. Pimbblet, “Globular cluster formation within the Aquarius simulation,” MNRAS 405 no. 1, (June, 2010) 375–386, arXiv:0910.0310 [astro-ph.GA].
  * [36] T. R. Saitoh, J. Koda, T. Okamoto, K. Wada, and A. Habe, “Tidal disruption of dark matter halos around proto-globular clusters,” Astrophys. J. 640 (2006) 22–30, arXiv:astro-ph/0511692.
  * [37] P. Creasey, L. V. Sales, E. W. Peng, and O. Sameie, “Globular clusters formed within dark haloes I: present-day abundance, distribution, and kinematics,” MNRAS 482 no. 1, (Jan., 2019) 219–230, arXiv:1806.11118 [astro-ph.GA].
  * [38] S. Mashchenko and A. Sills, “Globular clusters with dark matter halos. 1. Initial relaxation,” Astrophys. J. 619 (2005) 243, arXiv:astro-ph/0409605.
  * [39] H.E.S.S. Collaboration, A. Abramowski et al., “H.E.S.S. observations of the globular clusters NGC 6388 and M 15 and search for a Dark Matter signal,” Astrophys. J. 735 (2011) 12, arXiv:1104.2548 [astro-ph.HE].
  * [40] R. K. Leane, T. Linden, P. Mukhopadhyay, and N. Toro, “Celestial-Body Focused Dark Matter Annihilation Throughout the Galaxy,” Phys. Rev. D 103 no. 7, (2021) 075030, arXiv:2101.12213 [astro-ph.HE].
  * [41] J. F. Navarro, C. S. Frenk, and S. D. M. White, “The Structure of cold dark matter halos,” Astrophys. J. 462 (1996) 563–575, arXiv:astro-ph/9508025.
  * [42] J. F. Navarro, C. S. Frenk, and S. D. M. White, “A Universal density profile from hierarchical clustering,” Astrophys. J. 490 (1997) 493–508, arXiv:astro-ph/9611107.
  * [43] N. W. Evans, C. A. J. O’Hare, and C. McCabe, “Refinement of the standard halo model for dark matter searches in light of the Gaia Sausage,” Phys. Rev. D 99 no. 2, (2019) 023012, arXiv:1810.11468 [astro-ph.GA].
  * [44] GRAVITY Collaboration, R. Abuter et al., “Detection of the gravitational redshift in the orbit of the star S2 near the Galactic centre massive black hole,” Astron. Astrophys. 615 (2018) L15, arXiv:1807.09409 [astro-ph.GA].
  * [45] H. Baumgardt, M. Hilker, A. Sollima, and A. Bellini, “Mean proper motions, space orbits, and velocity dispersion profiles of Galactic globular clusters derived from Gaia DR2 data,” MNRAS 482 no. 4, (Feb., 2019) 5138–5155, arXiv:1811.01507 [astro-ph.GA].
  * [46] H. Baumgardt, M. Hilker, A. Sollima, and A. Bellini, “Mean proper motions, space orbits, and velocity dispersion profiles of Galactic globular clusters derived from Gaia DR2 data,” MNRAS 482 no. 4, (Feb., 2019) 5138–5155, arXiv:1811.01507 [astro-ph.GA].
  * [47] A. Irrgang, B. Wilcox, E. Tucker, and L. Schiefelbein, “Milky Way mass models for orbit calculations,” A&A 549 (Jan., 2013) A137, arXiv:1211.4353 [astro-ph.GA].
  * [48] T. D. Morton, “isochrones: Stellar model grid package,” Mar., 2015.
  * [49] Y. Tarumi, N. Yoshida, and S. Inoue, “Internal R-process Abundance Spread of M15 and a Single Stellar Population Model,” Astrophys. J. Lett. 921 no. 1, (2021) L11, arXiv:2110.02970 [astro-ph.GA].
  * [50] E. E. Salpeter, “The Luminosity Function and Stellar Evolution.,” Astrophys. J.  121 (Jan., 1955) 161.
  * [51] G. Cowan, K. Cranmer, E. Gross, and O. Vitells, “Asymptotic formulae for likelihood-based tests of new physics,” Eur. Phys. J. C 71 (2011) 1554, arXiv:1007.1727 [physics.data-an]. [Erratum: Eur.Phys.J.C 73, 2501 (2013)].
  * [52] G. Cowan, K. Cranmer, E. Gross, and O. Vitells, “Power-Constrained Limits,” arXiv:1105.3166 [physics.data-an].
  * [53] C. Dvorkin, K. Blum, and M. Kamionkowski, “Constraining Dark Matter-Baryon Scattering with Linear Cosmology,” Phys. Rev. D89 no. 2, (2014) 023519, arXiv:1311.2937 [astro-ph.CO].
  * [54] A. Bhoonah, J. Bramante, S. Schon, and N. Song, “Detecting composite dark matter with long-range and contact interactions in gas clouds,” Phys. Rev. D 103 no. 12, (2021) 123026, arXiv:2010.07240 [hep-ph].
  * [55] P. Montero-Camacho, X. Fang, G. Vasquez, M. Silva, and C. M. Hirata, “Revisiting constraints on asteroid-mass primordial black holes as dark matter candidates,” JCAP 1908 (2019) 031, arXiv:1906.05950 [astro-ph.CO].
  * [56] B. R. Safdi, Z. Sun, and A. Y. Chen, “Detecting Axion Dark Matter with Radio Lines from Neutron Star Populations,” Phys. Rev. D 99 no. 12, (2019) 123021, arXiv:1811.01020 [astro-ph.CO].
  * [57] K. Sellgren, M. T. McGinn, E. E. Becklin, and D. N. Hall, “Velocity Dispersion and the Stellar Population in the Central 1.2 Parsecs of the Galaxy,” Astrophys. J.  359 (Aug., 1990) 112.
  * [58] E. Gallego-Cano, R. Schödel, H. Dong, F. Nogueras-Lara, A. T. Gallego-Calvente, P. Amaro-Seoane, and H. Baumgardt, “The distribution of stars around the Milky Way’s central black hole. I. Deep star counts,” A&A 609 (Jan., 2018) A26, arXiv:1701.03816 [astro-ph.GA].
  * [59] D. Merritt, S. Harfst, and G. Bertone, “Collisionally Regenerated Dark Matter Structures in Galactic Nuclei,” Phys. Rev. D 75 (2007) 043517, arXiv:astro-ph/0610425.
  * [60] T. Bogdanovic, R. M. Cheng, and P. Amaro-Seoane, “Disruption of a Red Giant Star by a Supermassive Black Hole and the Case of PS1-10jh,” Astrophys. J. 788 (2014) 99, arXiv:1307.6176 [astro-ph.HE].
  * [61] P. Amaro-Seoane, X. Chen, R. Schödel, and J. Casanellas, “Making bright giants invisible at the Galactic Centre,” MNRAS 492 no. 1, (Feb., 2020) 250–255, arXiv:1910.04774 [astro-ph.SR].
  * [62] J. E. Dale, M. B. Davies, R. P. Church, and M. Freitag, “Red giant stellar collisions in the Galactic Centre,” Mon. Not. Roy. Astron. Soc. 393 (2009) 1016–1033, arXiv:0811.3111 [astro-ph].
  * [63] F. Antonini, R. Capuzzo-Dolcetta, A. Mastrobuono-Battisti, and D. Merritt, “Dissipationless Formation and Evolution of the Milky Way Nuclear Star Cluster,” Astrophys. J.  750 no. 2, (May, 2012) 111, arXiv:1110.5937 [astro-ph.GA].
  * [64] D. Merritt and A. Szell, “Dynamical cusp regeneration,” Astrophys. J. 648 (2006) 890–899, arXiv:astro-ph/0510498.
  * [65] S. S. Kim and M. Morris, “Dynamical friction on star clusters near the galactic center,” Astrophys. J. 597 (2003) 312–322, arXiv:astro-ph/0307271.
  * [66] M. Zajaček, A. Araudo, V. Karas, B. Czerny, A. Eckart, P. Suková, M. Štolc, and V. Witzany, “Missing bright red giants in the Galactic center: A fingerprint of its once active state?,”  11, 2020.  arXiv:2011.12868 [astro-ph.GA].
  * [67] G. R. Blumenthal, S. M. Faber, R. Flores, and J. R. Primack, “Contraction of Dark Matter Galactic Halos Due to Baryonic Infall,” Astrophys. J.  301 (Feb., 1986) 27.
  * [68] D. Merritt, “Evolution of the dark matter distribution at the galactic center,” Phys. Rev. Lett. 92 (2004) 201304, arXiv:astro-ph/0311594.
  * [69] J. D. Dull, H. N. Cohn, P. M. Lugger, B. W. Murphy, P. O. Seitzer, P. J. Callanan, R. G. M. Rutten, and P. A. Charles, “The Dynamics of M15: Observations of the Velocity Dispersion Profile and Fokker-Planck Models,” Astrophys. J.  481 no. 1, (May, 1997) 267–281.
  * [70] J. Gerssen, R. P. van der Marel, K. Gebhardt, P. Guhathakurta, R. C. Peterson, and C. Pryor, “Hubble Space Telescope evidence for an intermediate - mass black hole in the globular cluster M15: 2. Kinematical analysis and dynamical modeling,” Astron. J. 124 (2002) 3270–3288, arXiv:astro-ph/0209315.
  * [71] J. Lewin and P. Smith, “Review of mathematics, numerical factors, and corrections for dark matter experiments based on elastic nuclear recoil,” Astroparticle Physics 6 no. 1, (1996) 87–112. https://www.sciencedirect.com/science/article/pii/S0927650596000473.

##  Appendix A M15 DM Halo

Figure A.1: The 95% confidence limit on macroscopic DM (red) from the non-
observation of DM-induced He flashes in the GC M15 LF, assuming that M15 hosts
its own DM halo. The region inside the red line is ruled out. The dashed line
is the Asimov expectation under the null hypothesis with green (yellow) bands
denoting the 1$\sigma$ (2$\sigma$) containment region. We show the same
constraints detailed in Fig. 5.

In the main text we made the conservative assumption that the DM in M15 is
sourced by the Milky Way halo. The DM density within GCs can be significantly
larger if the GC formation took place in an initial DM overdensity, although
this scenario is uncertain and we ignored it in our fiducial analysis.
However, if further observations show there is indeed substructure, the
constraints from DM-induced ignition can be improved, and we estimate the
sensitivity gain in this section.

The formation of the GC occurs when the proto-GC virial temperature drops
below $\sim 10^{4}$ K when radiative cooling turns on [35]. At this time the
proto-GC collapses, and the DM halo undergoes adiabatic contraction that
increases the steepness of the density profile towards the center of the GC
[67]. Simulations suggest that at high redshifts the subhalo around GCs is
tidally stripped, such that the GC is baryon-dominated by mass at present
times [36]. At later times, stars kinetically heat the DM so that the profile
becomes cored [68].

We assume the parameters derived in [39], which computed present-day M15 DM
profile under this scenario in the context of DM annihilation searches. The DM
distribution is cored at $\sim 10$ pc [39], inside which nearly all of the RGB
stars are contained [69]. Therefore, we take the DM density to be a constant
throughout the core, with a value of

$\rho_{DM}=35M_{\odot}\ \rm{pc}^{-3}=1.3\times 10^{3}\ \rm{GeV}\
\rm{cm}^{-3}.$ (28)

The radial stellar velocity dispersion $\sigma_{v_{r}}$ in M15 was measured
within the inner $3$ pc by [69]; within the inner $1$ pc that reference found
$\sigma_{v_{r}}$ to be a constant $10.2\pm 1.4$ km s-1, and declines to
$\sim$7 km s-1 at $3$ pc. In [70] $\sigma_{v_{r}}$ was determined out to the
cluster edge, where it continues declining to $\sim$5 km/s. In the central
$\sim$0.3 pc, $\sigma_{v_{r}}$ may rise to $\sim$14 km s-1 [70], but the
number of stars in this region is volume suppressed. Therefore, we adopt the
conservative value $10$ km s-1 as both the stellar and DM velocity dispersion,
so that the relative velocity dispersion is $\sqrt{2}\times 10$ km s-1.
Lastly, the GC escape velocity of stars in this region is $\sim 50$ km s-1
[39]. Therefore it is a very good approximation to use Eq. (16), setting
$c(t)=1$, which gives

$\displaystyle\Gamma$
$\displaystyle=\sqrt{2\pi}\frac{\rho_{DM}}{m_{\chi}}R^{2}_{\zeta=1}\frac{v^{2}_{*\text{esc}}(R_{\zeta=1})}{\sigma_{vr}}.$
(29)

In Fig. A.1, we show the 95% limit on macroscopic DM assuming that M15 hosts a
DM subhalo with the above parameters. Similarly to our fiducial bound plot,
the bounded region is roughly triangular, see text around Fig.5. The extra tip
to the triangle is due to the presence of friction near the hypotenuse, which
for small values actually focuses the DM towards the core. Under this
scenario, the constraints improve substantially, particularly at high
$m_{\chi}$ where the rate is suppressed by low DM number density in the case
where the DM is provided only by the Milky Way halo. The bound is nearly
saturated in the sense that almost all of the parameter space in which DM-
induced HFs are possible is disfavored, as $m_{\chi}>10^{23}$ g is already
disallowed by microlensing. To further sensitivity substantially, new targets
hosting RGB stars of other masses or metallicities may be required, or targets
with more RGB stars that are nearing the standard HF.

##  Appendix B Ignition Profile

We assumed the energy is deposited in a linearly increasing profile from the
edge of the geometric cross section to the center. The exact profile depends
on the form of the DM, as well as on details of shock layer formation in front
of the DM. This could increase the effective area over which the temperature
is spread. In the limit where the only change is in the increase of the
effective area, our bounds simply translate upwards to the correspondingly
larger cross sections.

Separately one may be concerned of a sharp dependence of the ignition ratio,
Eq. 13, on the shape of the profile. To investigate this we generalize Eq. 2
in two ways. Defining $\xi=r/\sqrt{\sigma_{\chi n}/\pi}$, our nominal energy
deposition is $\propto(1-\xi)$. We investigate the two sets of profiles

$\displaystyle\frac{dE}{dV}$ $\displaystyle\propto(1-\xi^{n})\frac{dE}{dx},$
(30) $\displaystyle\propto(1-\xi)^{n}\frac{dE}{dx}.$ (31)

Figure B.1: Left Panel The dimensionless energy deposition profiles. Each is
normalized over a cylinder to give the same $dE/dx$. Right Panel The
corresponding ignition parameter for various profiles. Stellar and DM
properties are fixed at the values shown in the figure inset.

In Fig. B.1 we show these distributions in the left panel, and an example of
the resulting set of ignition ratios in the right panel. For $n=1$ these two
shapes are equivalent, and is the case we assumed for our limits. In the large
$n$ limit, the first set approaches a top hat shape, and the latter approaches
a delta function peaked at the center of the DM ($\xi=0$). Assuming the former
set of lines represent more physical DM models, we find very little shape
dependence.

##  Appendix C Analytic Ignition Rate

In terms of the velocity distribution function, the rate of DM-induced
ignition from an asymptotic surface $\Omega\ r_{\infty}^{2}$ is

$\displaystyle\Gamma$
$\displaystyle=N\frac{\rho_{\chi}}{m_{\chi}}r_{\infty}^{2}\int d\Omega\int
d^{3}{\bf v}\ (-\mathbf{v}\cdot\hat{r})$ (32)
$\displaystyle\times\text{exp}\left(\frac{-({\bf
v+v_{GC}})^{2}}{2\sigma_{vr}^{2}}\right)\Theta(v^{2}_{esc}-({\bf
v+v_{GC}})^{2}).$ (33)

Where $\hat{r}$ points out from the star, and $N$ is the normalization of
$f(\mathbf{v})$

$\displaystyle N^{-1}$ $\displaystyle=(2\pi\sigma_{vr}^{2})^{3/2}\times k,$
(34)

For constant $k$ which accounts for finite MW escape velocity, given by

$\displaystyle
k=\left(erf\left(\frac{v_{esc}}{\sqrt{2}\sigma_{vr}}\right)-\sqrt{\frac{2}{\pi}}\frac{v_{esc}}{\sigma_{vr}}\text{exp}\left(\frac{-v_{esc}^{2}}{2\sigma_{vr}^{2}}\right)\right).$
(35)

The solid angle of velocity space which hits the star is
$\pi\phi^{2}\approx\pi b^{2}/r_{\infty}^{2}$ for impact parameter $b$.
Conserving energy and angular momentum gives the gravitationally focused
impact parameter as a function of the escape velocity from the core of the
star $v_{*esc}$,

$\displaystyle b^{2}=R^{2}_{\zeta=1}\left(1+v^{2}_{*esc}/v^{2}\right)\approx
R_{\zeta=1}^{2}v^{2}_{*esc}/v^{2}.$ (36)

With ${\bf v_{GC}}$ along the $z$-axis, ${\bf v\cdot v_{GC}}=vv_{GC}\text{
cos}\theta$. Applying these gives

$\displaystyle\Gamma$ $\displaystyle=N\frac{\rho_{\chi}}{m_{\chi}}(\pi
R^{2}_{\zeta=1})v^{2}_{\text{esc}}2\pi\int^{1}_{-1}d\text{cos}\theta\int^{\infty}_{0}dv\
v$ (37)
$\displaystyle\times\text{exp}\left(\frac{-(v^{2}+v_{GC}^{2}+2vv_{GC}\text{cos}\theta)}{2\sigma_{vr}^{2}}\right)$
(38)
$\displaystyle\times\Theta(v^{2}_{esc}-(v^{2}+v_{GC}^{2}+2vv_{GC}\text{cos}\theta)).$
(39)

We evaluate this integral with the methods in [71] and arrive with

$\displaystyle\Gamma$ $\displaystyle=\Gamma_{0}\times
c(t,v_{GC},v_{\text{esc}}).$ (40)

Where $\Gamma_{0}$ is the rate including gravitational focusing, but without
MW escape velocity, or GC velocity, evaluated at the current time $t_{0}$. The
correction factor for the latter three effects defines
$c(t,v_{GC}(t),v_{esc})$. These are

$\displaystyle\Gamma_{0}(\tau)$
$\displaystyle=\sqrt{2\pi}\frac{\rho_{DM}(t_{0})}{m_{\chi}}R^{2}_{\zeta=1}(\tau)\frac{v_{*esc}^{2}}{\sigma_{vr}}+\mathcal{O}(\sigma_{vr}^{2}/v^{2}_{*\text{esc}})$
(41) $\displaystyle c(t)$
$\displaystyle=\frac{\rho_{DM}(t)}{\rho_{DM}(t_{0})}\frac{\sqrt{\pi}\sigma_{vr}}{4kv_{GC}}\Big{[}2\sqrt{2}{\rm
erf}(\frac{v_{GC}}{\sqrt{2}\sigma_{vr}}),$ (42) $\displaystyle-{\rm
Exp}\left(\frac{v_{esc}^{2}-2v_{GC}^{2}}{2\sigma^{2}_{vr}}\right)$
$\displaystyle\times\bigg{(}{\rm
erf}\left(\frac{v_{GC}+v_{esc}}{\sigma_{vr}}\right)-{\rm
erf}\left(\frac{v_{esc}-v_{GC}}{\sigma_{vr}}\right)\bigg{)}\Big{]}.$

Using the M15 orbital data obtained from the authors of [46], we compute the
correction factor $c(t)$ for M15 over the last Gyr and show it in Fig. C.1.
This factor accounts for the DM density variation, GC velocity, and MW escape
velocity as M15 orbits the Galactic Center. Minima (maxima) correspond to the
orbital apoapses (periapses). At time $t_{0}$, today, the GC is near its
apoapsis. We see that the rate is enhanced by a factor of $\sim$2.8 at
periapsis relative to apoapsis.

Figure C.1: The correction factor $c(t)$ to the rate of DM-induced ignition
for M15, see Eq. (42).


# Twitter Hash Tag Recommendation

Roman Dovgopol and Matt Nohelty
University of Minnesota

###### Abstract

The rise in popularity of microblogging services like Twitter has led to
increased use of content annotation strategies like the hashtag. Hashtags
provide users with a tagging mechanism to help organize, group, and create
visibility for their posts. This is a simple idea but can be challenging for
the user in practice which leads to infrequent usage. In this paper, we will
investigate various methods of recommending hashtags as new posts are created
to encourage more widespread adoption and usage. Hashtag recommendation comes
with numerous challenges including processing huge volumes of streaming data
and content which is small and noisy. We will investigate preprocessing
methods to reduce noise in the data and determine an effective method of
hashtag recommendation based on the popular classification algorithms.

## I. Introduction

Microblogging services have become increasingly popular in recent years
allowing users to share small snippets of text with the world. Users share a
variety of information from personal opinions and thoughts to breaking news
and product marketing messages. Of the many microblogging services available,
Twitter has become the dominant service with estimates of 250 million
registered users who post up to 500 million Tweets per day [12].

As Twitter grew in popularity, it became apparent that an organizational
strategy was needed to organize the massive amounts of data. In 2009, Twitter
introduced a user driven annotation called a hashtag [3]. Today, hashtags are
used for many purposes such as finding posts of interest, organizing a group
message, and determining the most popular topics of discussion. Users can
apply hashtags to their posts by placing the number sign (#) before a word
they want to use as a hashtag. Users are free to create almost any hashtag
they can imagine as long as it is a single alphanumeric string of text. The
practical ramifications of this mean that hashtags containing more than one
word are simply pushed together by removing spaces so these hashtags are not a
single correctly spelled word. For example, a user who enjoys big data
processing might Tweet something like "I heart #bigdataprocessing".

Hashtags are simple to apply and well known to mainstream Twitter users.
However, hashtags are only used in approximately 10% of Tweets [4]. This
limited usage greatly reduces the usefulness of the hashtag as a global
organizational strategy. If hashtags could be recommended to users before they
post their Tweet, we suspect hashtag usage would increase dramatically.

In this paper, we develop a method for recommending relevant hashtags to users
in real-time. Hashtag recommendation has two main challenges that set it apart
from traditional document tag recommendations. First, the content of a Tweet
is very short and often includes abbreviations, misspellings, and incorrect
grammar. The limited number of words in a Tweet makes traditional document
classification techniques such as TF-IDF (Term Frequency and Inverse Document
Frequency) ineffective because of the TF=1 challenge which means that words
are rarely repeated in a Tweet [10]. This makes it difficult to determine
which words are most important to the meaning of the Tweet. The second
challenge is the sheer volume and speed at which data is produced. Tweets are
produced constantly so the incomming Tweets need to be treated as an infinite
length stream. Our approach to recommendation attempts to handle these
challenges with a variety of preprocessing techniques and a recommendation
model based on the popular classification algorithms K-Nearest Neighbor and
Naive Bayes.

## II. Constraints

Three main constraints were taken into account when developing our
recommendation system. First, our recommendations are based solely upon the
content of the Tweet. We scoped the problem this way because the content of a
Tweet must be the core factor of any hashtag recommendation system so it is
essential to develop a solid approach using this factor alone before extending
the recommender to consider other factors like the author’s social network or
previous posting history.

The second constraint is speed. For this appraoch to be useful in a real world
application, we need to generate many recommendations very rapidly. Today’s
internet users are unwilling to wait for a web page for even a few seconds
[14] so the usefulness would be greatly reduced if recommendations could not
be produced in milliseconds. Also, as previously mentioned, Twitter has seen
as many as 500 million posts per day, so a recommendation system needs to be
able to scale to handle large volumes of input.

The third and final constraint is computational resource demands. The
recommendation system needs to process and infinite length stream, run
indefinitely, and scale gracefully as the stream progresses so demands on
computional resources like CPU and memory need to remain relatively constant.

## III. Prior Work

There has been significant research on keyword extraction, document
classification, and tag recommendation but far less as it relates to very
short documents like microblogging posts. In this section, we briefly review
the main directions for the studies related to this paper.

In some ways, hashtag recommendation is similar to a typical text
classification problem and various algorithms from regression and
classification analysis might be applied here [7][18]. Other studies focus on
classification of short-text documents but commonly use only a limited number
of features. Therefore they almost always degrade if we consider each hashtag
as a separate class. The main reason for this is the obvious obstacles of
maintaining and processing an exceedingly big number of classes [2][8].

Other related methods for hashtag recommendation are based on measuring the
similarity of tweets. Zangerle[5] and Godin[6] have several recommendation
approaches based on TF-IDF methods and feature vectors for each tweet. Also,
several papers have been published on recommending hashtags by using external
meta data sources such as WordNet and Wikipedia to build context which could
be applied to the text of post [11][15]. A study by Kharibi[4] considers a
tweet as a set of words and measures a relevance between the words by
aggregating all relevance scores which are computed from a co-occurrence
graph. Feng’s research [16] develops and expands this approach both with
variety of optimizations and improvements and by processing a user’s personal
information. In this paper, we apply concepts from these papers to develop our
own hashtag recommendation approach.

## IV. Our Approach

Our hashtag recommendation process can be broken down into a three main
topics: preprocessing, classification, and computational resource management.

### I. Preprocessing

Preprocessing is extemely important in many big data applications because it
provides a mechanism to filter, aggregate, and cleanse the dataset making the
actual processing more accurate and efficient. Hashtag recommendation is one
such application that benefits greatly from this approach. Tweet content is
very noisy when compared to many other document datasets because character
constraints force abbreviations and posts are written by millions of different
people so there is no consistency between authors. Because of this,
preprocessing Tweets is an essential first step to minimize the impact of this
noise to prepare the data for accurate classification.

The first preprocessing step was to normalize the character set by converting
all alpha characters to lower case and stripping out punctuation. Our
classifiers work by finding terms that appear in multiple Tweets so this
normalization step allows us to group words with the same meaning. For
example, "Don’t", "don’t", and "dont" are all the same word but are written
differently. This normalization will convert each of these words to "dont" so
each occurrence will be grouped together making the distribution of terms more
favorable for processing and more reflective of the intent of the authors.

For our classifiers to work most effectively, they need to base the
classification on words with the most significance to the meaning of the
Tweet. To maximize the likelihood of this, we removed words that have a high
probability contributing little to the meaning of the Tweet. We removed 175
common English stop words like "a", "the", and "and" as well as common words
found on Twitter like "rt" (i.e. retweet). We also removed any words that
contained less than 3 characters and words made up entirely of numbers. We
also exclude links from consideration in our classifiers. Because of the 140
character limit, links in Twitter are generally created using url shortening
tools like bit.ly (https://bitly.com) which generates unique links for each
user even if they point to the same destination page. Because of this, very
little information can be gleaned from the url.

The final preprocessing step we investigated was stemming using the Porter
Stemming algorithm [9] which removes prefixes and suffixes from each word in a
Tweet. The intution was that this would improve the accuracy of the classifier
because terms with a common stem usually have similar meanings [9]. In
practice however, we found this to have neglible impact on the accuracy of our
recommendations as well as a non-trivial decrease in recommendation speed.
Because of this, we excluded this preprocessing step in our final algorithm.
We did not investigate why stemming did not improve accurracy but our
suspicion is that the many abbreviations, mispellings, and slang terms
commonly used on Twitter interfere with the stemming algorithm. Further
research is necessary here to determine if modifications to the stemming
algorithm could improve results.

### II. Classifications

Our recommendation engine is based primarily on classification. We evaluated a
variety of clustering and classification algorithms and selected K-Nearest
Neighbor and Naive Bayes to base our recommendations on. These algorithms are
straight forward to implement but more importantly, they are lazy evaluating
algorithms. This means the underlying data of the classification model can be
modified without needing to rebuild the entire model. By contrast, decision
trees and rule based classifiers require the decision tree or rule sets to be
regenerated if the model data changes.

#### I. Naive Bayes

Naive Bayes classification uses Bayes’ Theorem to determine the conditional
probability of a class given an item’s features. In this application, the
class is the hashtag and the features are the words in a Tweet. Bayes Theorem
makes it possible to calculate the probability of a hashtag given a set of
words in a Tweet. If this is done for all known hashtags, the hashtags with
the highest probability can be used as the recommendations.

######  Theorem 1 (Bayes’ Theorem).

Multiple Features

$\displaystyle
P(h|w_{1},w_{2},...,w_{n})=\frac{P(w_{1},w_{2},...,w_{n}|h)*P(h)}{P(w_{1},w_{2},...,w_{n})}=P(h|w_{1})*P(h|w_{2})*...*P(h|w_{n})$

However, there are a few problems with this approach. In many cases,
$P(h|w_{i})$ will be zero when we have not yet seen a Tweet containing word
$w_{i}$. If this occurs, the entire $P(h|w_{1},w_{2},...,w_{n})$ goes to zero
even if other words have high conditional probabilities. We investigated
methods such as Laplace Smoothing which did improve our results, but we found
that summing the conditional probabilities instead of using the product
produced even better results. The intuition behind this is that in many cases
a single word is a strong predictor of the hashtag. If most of the words in a
Tweet are unrelated to a hashtag but one word is very related, the unrelated
words drag down the overall probability of that hashtag when computing the
product. By summing the conditional probabilities, we preserve the high
weighting contributed by the high probability words. Summing also handles the
issue where $P(h|w_{i})$ is zero because a word with a score of zero has no
negative impact on $P(h|w_{1},w_{2},...,w_{n})$.

Below is our optimal Naive Bayes algorithm. Let $W$ be the list of words in
the Tweet we are classifying. Let $T$ be the list of Tweets in our
classification model. Let $n$ be the number of hashtag classifications to
return.

$T_{s}=SIMILAR\\_TWEETS(W,T)$

$H=T_{s}.hashtags$ //All hashtags in list of Tweets

$classifications$ = [ ]

for $h$ in $H$ do

$score$ = 0

for $w$ in $W$ do

$score$ += $(\frac{P(w|h)*P(h)}{P(w)}*WORD\\_WEIGHT(w))$

end for

$classifications.add(h,score)$

end for

return $getHighestScores(classifications,n)$ //Return n highest scored
hashtags

Algorithm 1 [$NB\\_CLASSIFY({W,T,n})$]

#### II. K-Nearest Neighbor

K-Nearest Neighbor classifiers find the K most similar data points to the item
being classified and return the most common class found in those K items. The
key to a successful K-Nearest Neighbor algorithm is the similarity measure to
compare two items. There are many ways to do this from simple calculations
like the Tanimoto Distance (number of words found in both documents) to
weighting measures like TF-IDF (Term Frequency and Inverse Document
Frequency). For the Tweet dataset, we found the most successful similarity
measure to be the sum of the Term-Corpus Relevance (TCoR) [10] scores for all
words found in both Tweets. TCoR is a weighting measure proposed by Timonen,
et al. to measure how strong of a class predictor the word is across the
entire dataset.

######  Definition 2.

$TCoR(w)=\frac{\frac{1}{fl(w)}+\frac{1}{c_{w}}}{2}$

$fl(w)$ is the average number of words in Tweets containing the word and
$c_{w}$ is the number of hashtags the word co-occurs with. The intuition for
TCoR is that the fewer number of words in a Tweet, the more important an
individual word is to the overall meaning of that Tweet and words occurring
with a small number of distinct hashtags are more imformative when predicting
a hashtag [10]. Timonen, et al. propose a second measure called Term-Category
Relevance (TCaR) to combine with TCoR for the final weight. Interestingly,
using TCaR reduced the accuracy of our recommendations by almost 50% so we
used TCoR alone to weight the occurrence of words.

Below is our optimal K Nearest Neighbor algorithm. Let $W$ be the list of
words in the Tweet we are classifying. Let $T$ be the list of Tweets in our
classification model. Let $K$ be the number of nearest neighbors to consider.
Let $n$ be the number of hashtag classifications to return.

$T_{s}=SIMILAR\\_TWEETS(W,T)$

$neighbors=$ [ ]

for $t$ in $T_{s}$ do

$score=TCoR(w)*WORD\\_WEIGHT(w)$

$neighbors.add([t,score])$

end for

$nearest\\_neighbors=getHighestScores(neighbors,K)$ //Get K tweets with
highest score

$classifications=$ [ ] //Map of hashtag and count

for $t$ in $nearest\\_neighbors$ do

for $h$ in $t.hashtags$ do

$classifications.add([h,1])$ //Add h with count of 1 (or increment count)

end for

end for

return $getHighestScores(classifications,n)$ //Return n hashtags with highest
count

Algorithm 2 [$KNN\\_CLASSIFY({W,T,K,n})$]

#### III. Shared Classifier Functions

Both the Naive Bayes and K Nearest Neighbor classifiers share a few other
enhancements to improve classification accuracy and speed. We could compute
the classification by considering every Tweet in the dataset but that would be
very slow as the dataset could contain millions of Tweets. Instead, we use
$SIMILAR\\_TWEETS(W,T)$ to quickly narrow down the full list of Tweets to just
the most likely matches.

We do this by computing the Inverse Document Frequency (IDF) for all the words
in $W$. IDF is a commonly used measure of how common a word is across a set of
documents. It is an important measure because not all words contribute equally
to the meaning of a document. A high IDF score indicates the word is rare
across the document set which means it is likely important to the meaning of a
document in which it is found.

######  Definition 3.

$IDF(w)=log(\frac{|T|}{|w\in T|})$

We select the three words from $W$ with highest IDF scores as these are likely
to be the three most important words in the Tweet we are classifying. We then
find all Tweets in our dataset that contain at least one of those three words.
This list of Tweets is just a fraction of the size of the entire Tweet dataset
and likely contains Tweets most similar to the one we are classifying.
Limiting our classification algorithms to investigate only this list of Tweets
improves the speed of classifications and also helps to filter some of the
noise created by high frequency words.

The second shared function is $WORD\\_WEIGHT(w)$ which computes additional
weighting for a given word. If a word starts with an ’@’ it is a mention,
which means the Tweet is directed to a certain user. We apply a weight of 3 to
all mentions because Tweets directed to the same user have a high likelihood
of being similar and containing the same hashtag. If the word is not a
mention, we give it a weight of 1 plus 0.1 for every letter in the word. This
weights longer words more heavily than shorter words. The intuition is that
longer words generally have a more specific meaning and are more likely to be
important to the meaning of the Tweet.

#### IV. Hybrid Classifier

Our final classification model makes use of both the Naive Bayes and K Nearest
Neighbors classifiers described above. We compute classifications using both
algorithms and then combine the results with a weighting factor we determined
experimentally. Each hashtag recommended by Naive Bayes recieves a weight of
0.4 and each hashtag recommended by K Nearest Neighbor receives a weight of
0.6. We sum up the weights and return the hashtags with the highest scores.
Using both classifiers takes advantage of the strengths of each classifier
which causes the most likely hashtags to move to the top of the list of
recommendations.

### III. Computational Resource Management

Finally, we need to consider speed and computational resources. Tweets are
produced in high volume, 24 hours a day, so being able to produce
recommendations quickly with constant computational resources is extremely
important. Traditionally, classification algorithms are given a training set
of data up front to train the classifier and all future classifications are
computed using that initial model. This method doesn’t work for a stream of
Tweets because hashtag usage changes very rapidly on Twitter as topics trend
and fade away. Because of this it’s very important to keep the classifier’s
model as current as possible.

We modified the classifiers to use the "sliding window" pattern which ensures
the most recently seen Tweets are used in the model [4]. In our
implementation, the classifier data model is a FIFO (first in first out)
queue. First, the classifier is initialized with a predefined number of
Tweets. Following initialization, every time a new Tweet arrives from the
stream, the oldest Tweet is removed from the model and the new Tweet is added.
Because we chose to use Naive Bayes and K Nearest Neighbor, which are lazy
evaluating classifiers, adding and removing Tweets to and from the dataset is
very fast because we do not need to regenerate any structures built on top of
the model like a rule set or a decision tree.

However, because these are lazy evaluators, classification itself can take
longer than algorithms that use complex prebuilt structures. Because of this,
we do maintain some external structures that are easy to update when Tweets
are added and removed from the model. Besides the ordered list of Tweets in
the model itself, we keep two hash maps, one indexed by a word and the other
indexed by a hashtag. Each of these hash maps store basic statistics about the
word or hashtag which we use to compute the weights and probabilities needed
in our classification algorithms. Because these are hash maps, we can find
statistics about a given word or hashtag in constant time. This provides a
nice compromise between lazy and eagar classifiers which allows for efficient
updates to our data model as it changes but also supports fast computation of
classifications.

In order to further improve the speed of our recommendations, we parallelized
our classifiers. We observed significant speed improvements when running our
recommendations with multiple threads and did not observe any decrease in
recommendation accuracy. This is an important finding because it shows our
classification can scale to handle larger data volumes. We did not extend this
parallelization to multiple machines so this would be an interesting area to
investigate further.

The final area we investigated to speed up classification was maintaining a
seperate model for each language. This provides a great opportunity to
parallelize the recommendation system even further. Each language could have
it’s own classifier and model which would function independently, and it would
only need to process a fraction of the full volume of Tweets. For example,
when an English Tweet is received it could be routed to the machine, or
cluster of machines, that maintains the English model and performs English
classifications. This system could be duplicated for each language. We proved
out this architecture on a single machine and achieved classifications of
comparable accuracy but found the language detection itself to be such a
bottleneck that it drastically slowed down recommendations. It would be
interesting to investigate this further to see if a faster language detection
algorithm could be designed to take advantage of this further parallelization.

## V. Experimental Results

To evaluate our recommendation algorithm, we simulate how a system like this
would function in a real world application. We begin by initializing the
classifier by fully populating the sliding window dataset with Tweets with
known hashtags. When initialization completes, we start producing
recommendations for Tweets with known hashtags. For each Tweet, we recommend
up to three hashtags. If one of those hashtags matches the actual hashtag of
the Tweet, we consider this recommendation a success. Following each
recommendation, we add that Tweet to the sliding window dataset and removed
the oldest Tweet which maintains our sliding window.

We ran our evaluation with a sliding window size of 1 million Tweets and
produced recommendations for an additional 1 million Tweets. For each Tweet,
we chose to recommend up to three hashtags as this is a realistic number that
could be shown to a user in a real application. The dataset we used for
testing contained a random sampling of 35,575,057 Tweets collected from
4/14/13 to 4/21/13. Of that, 4,038,934 Tweets (11.3%), contained hashtags.

Figure 1: Successful classification percentages for each classifier

The optimal Naive Bayes recommender successfully recommended hashtags for
30.22% Tweets and the optimal K Nearest Neighbor recommender successfully
recommended hashtags for 31.4% of Tweets. When we combined these together in
our Hybrid recommender we were able to achieve a successful recommendations
for 32.71% of the test Tweets. Figure 1 shows the success percentages for each
classifier. We observed a precision of 0.2, recall of 0.27, and an F measure
of 0.23.

This evaluation method is very conservative and underestimates the actual
success rate of our recommendations for a few key reasons. First, each
recommendation is considered successful only if the actual hashtag exactly
matches one of the recommendations. In reality, most Tweets don’t have one
single correct hashtag but could have numerous hashtags that would make sense
to a user and would be considered good recommendations by a human. However,
due to resource and time constaints, it was not possible to have a real person
evaluate the millions of recommendations made by our classifiers during these
evaluations.

The second reason is that we exclude the known hashtag of the Tweet that we
are making recommendations for. Including the hashtag unfairly biases the
recommendation in cases where the hashtag is truely a tag. For example,
consider a Tweet like "Just heard a funny joke #laughoutloud". In this case,
the user would never have included "#laughoutloud" if they did not know about
that hashtag. Because of this, we removed hashtags from the Tweet as we did
not want to give our recommender an unfair advantage. However, this negatively
impacts the recommendations in other cases where the hashtag is part of the
content of the Tweet. For example, "Just heard a funny #joke". In this case,
the user would have likely typed in the word "joke" even if they did not know
to use it as a hashtag. Because we are excluding hashtags, we would not use
the word joke when producing recommendations for this Tweet so we are making
this recommendation without an important word, making it far less likely for
us to produce an accurate recommendation. Including the hashtag when making
our recommendations nearly doubled our success rate.

The Hybrid recommender processed the 1 million test Tweets in just under 29
minutes at an average rate of 576 Tweets / Second. This equates to
approximately 50 million Tweets per day. These tests were run on a standard
laptop. In a real production application, much more powerful hardware would be
available that could fully take advanatage of the parallelization capabilities
discussed previously so we would expect even better performance.

## VI. Conclusions

In this paper we discussed the challenges that come with Twitter hashtag
recommendation and proposed solutions to overcome them. We combined these
ideas to create a scalable recommender system based on Naive Bayes and K
Nearest Neighbor classifiers. We used the sliding window pattern to maintain
constant computational resource demands and used IDF to efficiently filter
down the dataset to allow recommendations to be produced rapidly. To improve
recommendation accuracy, we combined classifiers and used a variety of
weighting measures to ensure these classifiers consider only the most
significant words in each Tweet. Throughout the paper, we also proposed a few
key areas to further extend our work to build upon the speed and accuracy we
were able to achieve with this recommender system.

## References

  * [1] A. Mazzia, J. Juett  Suggesting Hashtags on Twitter.  Computer Science and Engineering, University of Michigan, 2009
  * [2] B. Sriram, D. Fuhry, E. Demir, M. Demirbas.  Short Text Classification in Twitter to Improve Information Filtering.  Ohio State University
  * [3] D. Karr. (2013, November 8)  Infographic: The History of #Hashtags.  Marketing Tech Blog. Retrieved from http://www.marketingtechblog.com/history-hashtags/
  * [4] E. Khabiri, J. Caverlee, K. Kamath.  Predicting Semantic Annotations on the Real-Time Web.  HT’12, Milwaukee, WI, USA
  * [5] E. Zangerle, W. Gassler, and G. Specht.  Recommending #-tags in Twitter.  Proceedings of the Workshop on Semantic Adaptive Social Web, 2011
  * [6] F. Godin, V. Slavkovikj, W. De Neve, B. Schrauwen, R. Van de Walle.  Using Topic Models for Twitter Hashtag Recommendation.  Proceedings of the 22nd international conference on World Wide Web companio,pp. 593-596. International World Wide Web Conferences Steering Committee, 2013
  * [7] F. Sebastiani.  Machine learning in automated text categorization.  ACM Comput. Surv. vol. 34
  * [8] K. Nishida, T. Hoshide, and K. Fujimura.  Improving tweet stream classification by detecting changes in word probability.  SIGIR, 2012
  * [9] M.F. Porter, 1980.  An algorithm for suffix stripping.  Program. 14(3) pp 130-137.
  * [10] M. Timonen, P. Silvonen, M. Kasari.  Classification of Short Documents to Categorize Consumer Opinions.  University of Helsinki
  * [11] S. Banerjee, K. Ramanthan, A. Gupta.  Clustering short text using Wikipedia.  SIGIR 2007, Amsterdam, The Netherlands
  * [12] S. Bennett. (2012, January 13)  Twitter on track for 500 million total users by March, 250 million active users by the end of 2012.  Media Bistro. Retrieved from http://www.mediabistro.com/alltwitter/twitter-active-total-users_b17655
  * [13] S. Chung, D. McLeod.  Dynamic Pattern Mining: An Incremental Data Clustering Approach.  University of Southern California
  * [14] S. Lohr. (2012, February 29)  For Impatient Web Users, an Eye Blink Is Just Too Long to Wait.  New York Times. Retrieved from http://www.nytimes.com/2012/03/01/technology/impatient-web-users-flee-slow-loading-sites.html
  * [15] T. Li, Y. Wu, Y. Zhang  Twitter Hash Tag Prediction Algorithm.  ICOMP’11 - International Conference on Internet Computing, 2011
  * [16] W. Feng, J. Wang, W. Zhang.  We Can Learn Your #Hashtags: Connecting Tweets to Explicit Topics.  ICDE 2014, Chicago, IL, USA
  * [17] X. Hu, L. Tang, L. Huan.  Enhancing Accessibility of Microblogging Messages Using Semantic Knowledge.  CIKM 2011 Glasgow, UK
  * [18] Y. Matsubara, Y. Sakurai, B. A. Prakash, L. Li, and C. Faloutsos.  Rise and fall patterns of information diffusion: model and implications.  KDD, 2012