#  _Chandra_ ’s insight into SN 2023ixf111Released on November, 6th, 2023

Poonam Chandra National Radio Astronomy Observatory, 520 Edgemont Rd,
Charlottesville VA 22903, USA  Roger A. Chevalier Department of Astronomy,
University of Virginia, Charlottesville VA 22904-4325, USA  Keiichi Maeda
Department of Astronomy, Kyoto University, Kitashirakawa-Oiwake-cho, Sakyo-ku,
Kyoto, 606-8502. Japan  Alak K. Ray Homi Bhabha Centre for Science Education,
TIFR, Mumbai 400088, India  Nayana A.J. Department of Astronomy, University of
California at Berkeley Berkeley, CA 94720-3411

###### Abstract

We report _Chandra_ -ACIS observations of SN 2023ixf in M101 on day 13 and 86
since the explosion. The X-ray emission in both epochs are characterized by a
high temperature plasma from the forward shocked region as a result of
circumstellar interaction. We are able to constrain the absorption column
density at both _Chandra_ epochs. The column density is much larger than that
of the Galactic absorption column, and we attribute it to absorption by
circumstellar matter. Combining this with the _NuSTAR_ published measurement
on day 4, we show that the column density declines as $t^{-2}$ between day 4
to day 13 and then evolves as $t^{-1}$. The unabsorbed $0.3-10$ keV luminosity
evolves as $t^{-1}$ during the _Chandra_ epochs. At the first _Chandra_ epoch
we detect the Fe K-$\alpha$ fluorescent line at 6.4 keV indicating presence of
cold material in the vicinity of the SN. The line is absent on day 86,
consistent with the decreased column density by a factor of 7 between the two
epochs. Our analysis indicate that during 10 years to 1.5 years before
explosion, the progenitor was evolving with a constant mass-loss rate of
$5.6\times 10^{-4}$ $M_{\odot}\,\rm yr^{-1}$. The X-ray measurements indicate
asymmetry in the CSM.

Stellar mass loss (1613) — Core-collapse supernovae (304) — Circumstellar
matter (241) — X-ray transient sources (1852)

]

##  1 Introduction

Understanding and mapping the progenitors to their core-collapse supernovae
(CCSNe) are one of the biggest challenges in stellar astronomy. An important
component tying CCSNe to their massive progenitors is an understanding of
stellar mass-loss during the final evolutionary phases, forming the
circumstellar material (CSM) surrounding the star, which can dramatically
alter the observable properties of a supernova (SN). One of the major
developments in this field is indications that most progenitors may undergo
the enhanced mass-loss just before explosions, evidence of which has been seen
observationally via “flash” spectroscopy (e.g. Gal-Yam et al., 2014; Yaron et
al., 2017; Kochanek, 2019, etc.). While it is not entirely clear, the mass-
loss could be enhanced via several mechanisms, including, but not limited to,
nuclear burning instabilities (Smith & Arnett, 2014) and gravity wave driven
mass-loss (Quataert & Shiode, 2012).

SN 2023ixf is the closest Type II SN observed in decades and hence, provides
an excellent opportunity to study iin detail. SN 2023ixf was discovered on
2023 May 19.73 UT in a nearby galaxy M101 by an amateur astronomer Itagaki
(Itagaki, 2023) and was quickly classified as a Type II supernova (Perley et
al., 2023). Later it was further classified as a Type IIL SN (Bianciardi et
al., 2023). Hiramatsu et al. (2023) estimated the explosion date to be MJD
$=60082.743\pm 0.083$ (2023 May 18.75 UT), corresponding to 0.98 days before
the discovery. We adopt this explosion date throughout the paper.

Due to the proximity, detailed observations of SN 2023ixf have been possible
in several wavebands. In addition, M101 is a well observed galaxy with a rich
archival pre-explosion dataset. The pre- and post-explosion dataset have
provided important insights into the progenitor of SN 2023ixf. The pre-
explosion images have revealed the progenitor star to be a red supergiant in a
dusty region (Jencson et al., 2023; Kilpatrick et al., 2023; Soraisam et al.,
2023; Van Dyk et al., 2023). Several groups have constrained the mass of the
progenitor in a large mass range within 8–20 $M_{\odot}$ (Pledger & Shara,
2023; Kilpatrick et al., 2023; Jencson et al., 2023; Soraisam et al., 2023;
Niu et al., 2023).

The optical light curve of SN 2023ixf is characterized by a sharp rise to peak
in 5 days from absolute magnitude $-M_{V}=10$ mag to $M_{V}=-18$ and then a
plateau phase lasting for 30 days at magnitude $-17.6$ days followed by a
smooth decay (Hiramatsu et al., 2023; Singh Teja et al., 2023). The data
reveal prominent flash features of hydrogen, helium, carbon, and nitrogen in
the spectra up to 5 days (Yamanaka et al., 2023; Jacobson-Galan et al., 2023;
Smith et al., 2023; Bostroem et al., 2023; Singh Teja et al., 2023). The UV
data along with the flash features indicate a temperature rise which is not
expected in a pure-shock cooling event and thus suggested a delayed shock
breakout in a dense CSM (Zimmerman et al., 2023). Vasylyev et al. (2023)
measured high polarization and rapid evolution during 2-15 days, and explained
it as asymmetric ejecta coming out of dense asymmetric CSM, suggesting a
highly asymmetric mass-loss rate process.

The early X-ray emission was reported by _NuSTAR_ within 4 days (Grefenstette
et al., 2023), whereas the first radio detection occurred on 2023 Jun 17,
around a month after explosion (10 GHz flux density $41\pm 8$ $\mu$Jy,
Matthews et al., 2023). Berger et al. (2023) reported a non-detection in
millimeter bands at 2.6–18.6 days post-explosion.

There are various mass-loss estimates in the literature. Based on flash
ionization features, Jacobson-Galan et al. (2023); Zimmerman et al. (2023);
Bostroem et al. (2023) have determined an enhanced mass-loss rate of $\sim
10^{-2}$ $M_{\odot}\,\rm yr^{-1}$ just before explosion and indicated confined
CSM of $<10^{15}$ cm. Based on 19 years of archival IR data, Soraisam et al.
(2023) indicated mass-loss rate of $(2-4)\times 10^{-4}$ $M_{\odot}\,\rm
yr^{-1}$, which was also obtained by Grefenstette et al. (2023) in their X-ray
_NuSTAR_ measurements. On the lower end, Jencson et al. (2023) and Niu et al.
(2023) estimated it to be $(3-30)\times 10^{-5}$ $M_{\odot}\,\rm yr^{-1}$, and
$10^{-5}$ $M_{\odot}\,\rm yr^{-1}$, respectively, in 3-20 years before
explosion. The metallicity has ranged between half the solar Niu et al.
(2023), to solar (Van Dyk et al., 2023; Zimmerman et al., 2023).

We present here _Chandra_ X-ray observations of SN 2023ixf providing us the
opportunity to constrain the evolution of the progenitor. We adopt a distance
of 6.85 Mpc (Riess et al., 2022), a Milky Way extinction of $E(B-V)_{\rm
MW}=0.0077$ mag (Schlafly & Finkbeiner, 2011), and a host galaxy extinction of
$E(B-V)_{\rm host}=0.033$ (Lundquist et al., 2023; Smith et al., 2023;
Jacobson-Galan et al., 2023). We also adopt a standard extinction law with
$R_{V}=3.1$ (Cardelli et al., 1989).

##  2 Observations

SN 2023ixf was observed with the _Chandra_ under the approved DDT program
24508911 (PI: Chandra). The first observations took place on 2023 May 31
15:34:04 UT for 20.3 ks. The second set of observations were on 2023 Aug 11
18:17:07 and 2023 Aug 12 12:07:33 UT for 11.18 and 10.02 ks, respectively. The
observations were taken with ACIS-S without grating in a VFAINT mode. We
extracted the spectra using CIAO software222http://asc.harvard.edu/ciao/
version 4.15 and used xspec under
HEAsoft333http://heasarc.gsfc.nasa.gov/docs/software/lheasoft/ version 6.31 to
carry out the spectral analysis. For the second epoch, the individually
processed spectra on Aug 11 and 12 were combined using combine_spectra. A
total of 720 counts were obtained in May 2023 spectrum and 233 counts in Aug
2023 in about 20 ks of exposure time each.

Figure 1: Left: Contour plot of the best fit parameter values column density
and the plasma temperature for the May 2023 _Chandra_ spectrum. The column
density is well constrained while the temperature is not. Right: Contour plot
of the best fit values of a Gaussian line temperature and the column density.
Both the parameters are well constrained.

For the May 2023 spectral fits, initially we fit the optically thin ionized
plasma model absorbed with a column density. We fit the data assuming solar
metallicity. While the column density is well constrained, the best fit
temperature ($\sim 60$ keV) is not constrained towards the upper end (Fig. 1).
That is most likely the case if the plasma temperature is high as the
_Chandra_ energy range is not sensitive to high plasma temperature. We note
that Grefenstette et al. (2023) constrained the plasma temperature to 34 keV
at around 29th May based on _NuSTAR_ data (day 11), which is within 2 days of
our first epoch. Thus we fix the plasma temperature to 34 keV. We also see an
excess of flux around $6-7$ keV, though not captured in the plasma model. We
add a Gaussian to fit the excess flux. While the line width is not constrained
due to poor energy resolution of _Chandra_ the best fit line energy is $\sim
6.4$ keV, which matches with the Iron K$\alpha$ line energy, and is also seen
in the _NuSTAR_ data. We use Kallman et al. (2004) to freeze the line width to
0.2 keV (see §3 for the details). The line energy is $6.43^{+0.19}_{-0.20}$
keV (Fig. 1). Our best fit column density is $2.50^{+0.40}_{-0.34}\times
10^{22}$ cm-2. Our value is slightly smaller than that in the _NuSTAR_ data on
day 11 $(5.6\pm 2.7)\times 10^{22}$ cm-2), though consistent within error
bars.

In the second spectrum, we again start with fitting the absorbed plasma model
and allow both the temperature and column density to vary. There may be a hint
of temperature becoming lower than the first epoch (best fit temperature $\sim
10$ keV; however, due to limited energy range of _Chandra_ , it is not
possible to constrain the upper bound of the temperature (Fig. 2). As
discussed in §3, we freeze the temperature to 21 keV. The column density is
well constrained at this epoch and has substantially decreased to
$0.36^{+0.22}_{-0.17}\times 10^{22}$ cm-2(Fig. 3). We do not see evidence of
an Iron line at this epoch. However, considering the column density has
decreased by a factor of 7 and line evolution follows the continuum evolution,
a factor of 7 decrease in line strength will not lead to a detection. In Fig.
3, we plot the best fit spectra at both epochs.

Figure 2: Contour plot of the best fit parameter values column density and the
plasma temperature for the Aug 2023 _Chandra_ spectrum. The column density is
well constrained while the temperature is not.

Figure 3: Left: May 2023 best fit spectrum of SN 2023ixf. The model is fit
with an absorbed plasma with a Gaussian profile. Right: Aug 2023 best fit
spectrum of SN 2023ixf. The 6.4 Fr K$\alpha$ line is no longer detected.

##  3 Results and discussion

###  3.1 SN 2023ixf X-ray characteristics

Table 1 lists the best fit model parameters and the derived flux values. Due
to the limited energy range, the _Chandra_ observations could not constrain
the plasma temperature. We use the temperature of 34 keV in the first
spectrum, as obtained in the nearly coincident _NuSTAR_ data (Grefenstette et
al., 2023). As discussed below, we find that during the _Chandra_ observation
epochs, the column density and the luminosity evolution follow the standard
wind scenario under constant mass-loss rate $\rho\propto r^{-2}$ (Chevalier &
Fransson, 2017). Based on this we scale temperature to $t^{-2/(n-2)}$ (where
$n$ is the power-law index of the ejecta density profile Chevalier & Fransson,
2017). If we assume $n\sim 10$, the temperature at the second epoch should be
around 21 keV $t^{-0.25}$. While the temperature may only be approximate, this
does not introduce significant errors in our modeling. We find that for a 20%
change in the plasma temperature, the column density changes by only 5% and
the flux normalization changes by 1.5%

The high plasma temperature likely means that the X-ray emission is arising
from the forward shock. We do not see a low energy plasma. It is possible if
the CSM density is high enough that a cool dense shell forms between the
forward and reverse shocks and most of the lower temperature emission from the
reverse shock is absorbed. In the forward shock interpretation, the shock
velocity can be deduced as $v_{\rm
sh}=(16kT/(3\mu))^{1/2}=5000(kT/34\,keV)^{1/2}$ km s-1, where $k$ is
Boltzmann’s constant and $\mu$ is the mean particle weight which is taken to
be 0.61 here. Our velocity estimate is slightly smaller than the value of 8500
km s-1 derived by Jacobson-Galan et al. (2023), based on H$\alpha$ and
H$\beta$ line profiles. This suggests that either the H$\alpha$ and H$\beta$
profiles are arising from physically distinct regions than the X-ray emission
or the shock velocity is evolving to a lower value, since Jacobson-Galan et
al. (2023) derived the above ejecta velocity at earlier epochs.

Table 1: Spectral model fits to the SN 2023ixf spectra  | Spectrum 1 | Spectrum 2
---|---|---
Date | 2023 May 31 | 2023 Aug 11–12
Epoch | day $\sim 13$ | day $\sim 86$
Exposure (ks) | 20.3 | 21.2
Model |  $N_{\rm H,tot}\times$(apec+Gauss) |  $N_{\rm H,tot}\times$ apec
$N_{\rm H,tot}$ (cm-2) | $2.50^{+0.40}_{-0.34}\times 10^{22}$ | $0.36^{+0.22}_{-0.17}\times 10^{22}$
apec kT (keV) | 34 (fixed) | 21 (fixed)
apec flux (erg cm-2 s-1) | $1.43^{+0.09}_{-0.09}\times 10^{-12}$ | $2.09^{+0.23}_{-0.23}\times 10^{-13}$
Gauss kT (keV) | $6.43^{+0.19}_{-0.20}$ | $\cdots$
Gauss Sigma (keV) | 0.20 (fixed) | $\cdots$
Gauss flux (erg cm-2 s-1) | $1.01^{+0.45}_{-0.45}\times 10^{-13}$ | $\cdots$
Abs. flux (erg cm-2 s-1) | $1.01^{+0.07}_{-0.07}\times 10^{-12}$ | $2.09^{+0.23}_{-0.23}\times 10^{-13}$
Unabs. flux (erg cm-2 s-1) | $1.53^{+0.10}_{-0.10}\times 10^{-12}$ | $2.55^{+0.28}_{-0.28}\times 10^{-13}$
Unabs. $L_{\rm 0.3-10\,keV}$ (erg sec-1) | $8.53^{+0.56}_{-0.56}\times 10^{39}$ | $1.43^{+0.16}_{-0.16}\times 10^{39}$
${\chi}^{2}/{\nu}$ | 1.04 | 0.65

The column densities due to the Milky Way and the host are ($E(B-V)_{\rm
MW}=0.0077$, $E(B-V)_{\rm host}=0.033$), respectively. We adopt the method
listed in Schlegel et al. (1998), recalibrated by Schlafly & Finkbeiner
(2011), and derive $N_{\rm MW}=0.45\times 10^{20}$ cm-2 and $N_{\rm
host}=1.91\times 10^{20}$ cm-2. Thus the total extinction due to Milky Way and
M101 is $2.36\times 10^{20}$ cm-2. The column densities derived at the two
_Chandra_ epochs are $2.50\times 10^{22}$ cm-2 and $0.36\times 10^{22}$ cm-2,
respectively, which are around 130 and 20 times larger than that in the
direction of M101. Thus most of the column density is due to the presence of
not completely ionized material in the vicinity of the CSM. The column density
evolves as $t^{-1.03\pm 0.29}$, suggesting that between days 13 and 86, the
wind evolves with standard $r^{-2}$ dependence, where $r$ is the CSM distance
from the SN explosion center. However, if one combines this along with the
column density obtained in the _NuSTAR_ early data on day 4, it appears that
the column density decreased faster between day 4 and 13 with $t^{-2}$ before
starting to follow $t^{-1}$ evolution (Fig. 4). This is consistent with the
confined dense CSM seen via the flash ionization spectroscopy (Jacobson-Galan
et al., 2023; Bostroem et al., 2023; Singh Teja et al., 2023; Smith et al.,
2023), and is indicative of a scenario in which the supernova underwent a very
high mass-loss rate just before the explosion which resulted in a high column
density on day 4, before transitioning in to a low density region of nearly
constant mass-loss region revealed around day 13 onwards (see below). The
column density on day 4 from _NuSTAR_ data corresponds to an electron
scattering column depth of $\sim 0.2$. Thus electron scattering may have been
important before day 4, but not after day 4.

The flux between the two _Chandra_ epochs changes by a factor of $\sim 6$. The
unabsorbed 0.3–10.0 keV luminosity evolves at $t^{-0.95\pm 0.07}$ which is
also consistent with standard evolution (Chevalier & Fransson, 2017). The
luminosity on day 13 is $8.53\times 10^{39}$ erg sec-1 which is slightly lower
than the extrapolated value in the _Chandra_ energy range from the _NuSTAR_
observation at day 11 ($\sim 1.4\times 10^{40}$ erg sec-1), and is roughly
consistent within the error bars. Panjkov et al. (2023) reported the first
_Swift-XRT_ detection on day 4.3 and combined the first 46 days of data to
derive an unabsorbed luminosity of $(3.0\pm 0.7)\times 10^{39}$ erg sec-1.
Since we know that parameters such as column density are evolving quickly, we
do not take this approach. We combine the _Swift-XRT_ measurements covering
_NuSTAR_ epoch 1, i.e. day 3.9–4.8 and find that there is a 3-$\sigma$
detection with 0.3–10 keV count rate of $(1.88\pm 0.65)\times 10^{-3}$ counts
sec-1. We derive the flux using the _NuSTAR_ best fit parameters on day 4,
i.e. $N_{H}=2.6\times 10^{23}$ cm-2 and use a plasma temperature of 34 keV
(Grefenstette et al., 2023). This provides an unabsorbed (absorbed) 0.3–10 keV
flux of $(9.16\pm 3.17)\times 10^{-13}$ erg cm-2 s-1 ($(3.07\pm 1.06)\times
10^{-13}$ erg cm-2 s-1), or an equivalent unabsorbed 0.3–10 keV luminosity of
$(5.14\pm 1.78)\times 10^{39}$ erg sec-1. As we show in Fig. 4, the 0.3–10 keV
unabsorbed luminosity initially increases between day 4 and 13 as $t^{+0.6}$
and then evolves as $t^{-1}$ throughout. This simply means that initially the
plasma is quite hot and more emission is coming in the hard X-rays. The X-ray
behaviour is qualitatively consistent with the one reported in Zimmerman et
al. (2023).

Assuming that the radiation is adiabatic at _Chandra_ epochs on days 13 and
86, we use equation (3.8) of Fransson et al. (1996) to calculate the mass-loss
rate. We estimate the spectral luminosity at 10 keV and derive the Gaunt
factor at 10 keV using Mewe et al. (1986). The mass-loss rates at the two
epochs are $(5.58\pm 0.18)\times 10^{-4}$ $M_{\odot}\,\rm yr^{-1}$,and
$(5.63\pm 0.30)\times 10^{-4}$ $M_{\odot}\,\rm yr^{-1}$, on days 13 and 86,
respectively. The uncertainties are only due to the flux errors. Here we
assumed the forward shock velocity of $\sim 5000$ km s-1 based on the X-ray
temperature, and the wind velocity of 115 km s-1 based on the narrow optical
line widths (Smith et al., 2023). The constant mass-loss rate between the two
_Chandra_ epochs is consistent with the scenario where the forward shock is
moving in a wind profile of $\rho_{\rm CSM}\propto 1/r^{2}$.

We check whether the forward shock is radiative or adiabatic. In the radiative
case, the luminosity of the forward shock will be $\propto\dot{M}$, whereas
the adiabatic shock luminosity will scale as $\propto\dot{M}^{2}$. Using
Chevalier & Fransson (2017), we can estimate the cooling time for the forward
shock. The cooling time scale as compared to SN age (assuming $n=10$ and
forward shock velocity $5000$ km s-1) is $t_{\rm cool}/t_{\rm age}=0.44t_{\rm
age,d}/(\dot{M}_{-4}/v_{\rm wind,2})$. Here $t_{\rm age,d}$ is the SN age in
days, $\dot{M}_{-4}$ is the mass-loss rate in units of $10^{-4}$
$M_{\odot}\,\rm yr^{-1}$, and $v_{\rm wind,2}$ is the wind velocity in units
100 km s-1. This means the forward shock is radiative if on day 4, the mass-
loss rate is larger than $2.2\times 10^{-4}$ $M_{\odot}\,\rm yr^{-1}$. The
flash ionization spectral analysis and at this epoch (e.g. Jacobson-Galan et
al., 2023; Bostroem et al., 2023) and from the delayed shock breakout
calculation (Zimmerman et al., 2023), the mass-loss rate is found to be of the
order of $10^{-2}$ $M_{\odot}\,\rm yr^{-1}$, indicating the forward shock is
indeed radiative around day 4. This value for the mass-loss rate is $\geq
10^{-3}$ $M_{\odot}\,\rm yr^{-1}$ and $\geq 5\times 10^{-3}$ $M_{\odot}\,\rm
yr^{-1}$ on day 13 and 86 for the forward shock to be radiative. Hence our
mass-loss rate estimation derived above at the _Chandra_ epochs considering
adiabatic expression is correct.

If we assume a column density is due to the CSM, that too provides an
independent estimate of the mass loss rate. Following Fransson et al. (1996),
this value is $8.7\times 10^{-5}$ $M_{\odot}\,\rm yr^{-1}$ at the two epochs,
which is clearly smaller than the one obtained from the X-ray observations.
This discrepancy is by a factor of 6. Even if the metallicity is half of solar
metallicity, the column density will increase by only a factor of 2 and the
discrepancy cannot be alleviated. This can probably be ascribed to a non-
spherically symmetric CSM.

Based on our derived mass-loss rate and forward shock velocity, we can
constrain the forward shock radius at the two _Chandra_ epochs to be
$0.56\times 10^{15}$ cm and $3.72\times 10^{15}$ cm, and the CSM density at
these epochs to be $7.84\times 10^{-16}$ g cm-3 and $1.79\times 10^{-17}$ g
cm-3. These values are in excellent agreement with mapping of the CSM
structure provided by Zimmerman et al. (2023).

Figure 4: Evolution of column density (left) and 0.3–10 keV unabsorbed
luminosity (right). The first red data point on day 4 in the column density
plot is the _NuSTAR_ data point (Grefenstette et al., 2023) for the column
density. The purple data point on the luminosity evolution plot is the _Swift-
XRT_ data point. While the column density evolves faster between day 4 and 13
before starting to follow the standard $t^{-1}$ evolution, the 0.3–10 keV
luminosity initially rises and then follows $t^{-1}$ evolution.

We note the presence of a 6.4 keV line which is identified with the Fe
K$\alpha$ line. The theoretical line width can be calculated using equation
(5) of Kallman et al. (2004) and is $\sim 0.1$ keV, which is unresolvable in
_Chandra_ ACIS-S data. Taking into account some uncertainties, in our fits we
fix the line width to 0.2 keV. This line arises from neutral or low ionized
iron (Fe I to Fe XI), and requires an ionization parameter $\zeta\approx 5$
(Kallman et al., 2004). Assuming the CSM is ionized by the X-rays, we can
estimate the ionization parameter $\zeta=L/nr^{2}$ using the X-ray luminosity
and our derived mass-loss rate. The mass-loss rate corresponds to a number
density of $\sim 3.7\times 10^{8}$ cm-3. The value is around 250 at the first
_Chandra_ epoch. This value means elements C, N, and O are completely ionized
but heavy elements like S and Fe are not. The line is not detected in the
second epoch. However, at the second epoch, $N_{H}$ is smaller by a factor of
7, so the strength of the Fe line should be correspondingly smaller. This is
consistent with the non-detection of the line.

###  3.2 Implications of the X-Ray Emission

The analysis of the X-ray emission in the previous subsection indicates that
the X-rays at _Chandra_ epochs are arising from the high temperature adiabatic
forward shock. The X-ray luminosity ($\sim 10^{40}$ erg sec-1) of SN 2023ixf
falls somewhere in the average luminosity of core-collapse SNe (Chandra,
2018). However, a mystery remains that the X-rays are a very small fraction of
the bolometric luminosity (Martinez et al., 2023), which is largely dominated
by interaction, especially at the first _Chandra_ epoch (Zimmerman et al.,
2023). One possibility is that most of the X-rays are reprocessed to longer
wavelength radiation. However, one requires a radiative forward shock, which
our data do not indicate. The only other possibility is if that X-rays are
coming from a physically distinct region than where the most of the lower
frequency emission is arising. This indicates asymmetry in the CSM. Some of
the indications of CSM asymmetry in our analysis are: lower shock velocity
derived from X-ray data as compared to H$\alpha$ velocity, lower mass-loss
rate indicated by the column density, and lower ionization parameter required
for Fe K$\alpha$ line than indicated from the X-ray luminosity. Early time
spectropolarimetry (Vasylyev et al., 2023) and a lack of narrow blueshifted
absorption profiles in optical spectra (Smith et al., 2023) have suggested
that much of the CSM is not along our line of sight, implying significant
asphericity of the CSM.

##  4 Summary and conclusions

In this work we present SN 2023ixf observations with the _Chandra_ ACIS-S at
two epochs separated by around 2.5 months. The column density and the 0.3–10
keV luminosity decline as $t^{-1}$ during the two _Chandra_ observations on
day 13 and 86, indicating that the SN ejecta is expanding in a standard
$r^{-2}$ wind created by a constant mass-loss rate of $(5.6\pm 0.18)\times
10^{-4}$ $M_{\odot}\,\rm yr^{-1}$ during 10–1.5 years before explosion, and is
consistent with the SN 2023ixf progenitor being a more massive red supergiant.
The day 13 _Chandra_ data also show the presence of the Fe 6.4 keV line
suggesting that the CSM may not have been fully ionized by the X-ray
radiation. The line disappears on the second epoch, consistent with the
decreased column density. The X-ray data indicate asymmetry in the CSM.

SN 2023ixf will be monitored for years to come and future studies will throw
light on our understanding of massive stars evolving to become CCSNe at their
endpoints.

##  5 Acknowledgments

PC acknowledges support from NASA through Chandra award number DD3-24141X
issued by the Chandra X-ray Center. RAC acknowledges support from NSF grant
AST-1814910. K.M. acknowledges support from the Japan Society for the
Promotion of Science (JSPS) KAKENHI grant JP18H05223, JP20H00174, and
JP20H04737. The scientific results reported in this article are based on
observations made by the Chandra X-ray Observatory, data obtained from the
Chandra Data Archive, and software provided by the Chandra X-ray Center. The
National Radio Astronomy Observatory is a facility of the National Science
Foundation operated under cooperative agreement by Associated Universities,
Inc. This research has made use of NASA’s Astrophysics Data System
Bibliographic Services. This research has made use of data and/or software
provided by the High Energy Astrophysics Science Archive Research Center
(HEASARC), which is a service of the Astrophysics Science Division at
NASA/GSFC. We acknowledge the use of public data from the Swift data archive.

## References

  * Berger et al. (2023) Berger, E., Keating, G. K., Margutti, R., et al. 2023, ApJ, 951, L31, doi: 10.3847/2041-8213/ace0c4
  * Bianciardi et al. (2023) Bianciardi, G.and Ciccarelli A., M., Conzo, G., D’Angelo, M., et al. 2023, Multiband Photometry Evolution in the First Weeks of SN 2023ixf, a possible II-L Subtype Supernova, arXiv, doi: 10.48550/ARXIV.2307.05612
  * Bostroem et al. (2023) Bostroem, K. A., Pearson, J., Shrestha, M., et al. 2023, arXiv e-prints, arXiv:2306.10119, doi: 10.48550/arXiv.2306.10119
  * Cardelli et al. (1989) Cardelli, J. A., Clayton, G. C., & Mathis, J. S. 1989, ApJ, 345, 245, doi: 10.1086/167900
  * Chandra (2018) Chandra, P. 2018, Space Sci. Rev., 214, 27, doi: 10.1007/s11214-017-0461-6
  * Chevalier & Fransson (2017) Chevalier, R. A., & Fransson, C. 2017, in Handbook of Supernovae, ed. A. W. Alsabti & P. Murdin, 875, doi: 10.1007/978-3-319-21846-5_34
  * Fransson et al. (1996) Fransson, C., Lundqvist, P., & Chevalier, R. A. 1996, ApJ, 461, 993, doi: 10.1086/177119
  * Gal-Yam et al. (2014) Gal-Yam, A., Arcavi, I., Ofek, E. O., et al. 2014, Nature, 509, 471, doi: 10.1038/nature13304
  * Grefenstette et al. (2023) Grefenstette, B. W., Brightman, M., Earnshaw, H. P., Harrison, F. A., & Margutti, R. 2023, ApJ, 952, L3, doi: 10.3847/2041-8213/acdf4e
  * Hiramatsu et al. (2023) Hiramatsu, D., Tsuna, D., Berger, E., et al. 2023, arXiv e-prints, arXiv:2307.03165, doi: 10.48550/arXiv.2307.03165
  * Itagaki (2023) Itagaki, K. 2023, Transient Name Server Discovery Report, 2023-39, 1
  * Jacobson-Galan et al. (2023) Jacobson-Galan, W. V., Dessart, L., Margutti, R., et al. 2023, arXiv e-prints, arXiv:2306.04721, doi: 10.48550/arXiv.2306.04721
  * Jencson et al. (2023) Jencson, J. E., Pearson, J., Beasor, E. R., et al. 2023, ApJ, 952, L30, doi: 10.3847/2041-8213/ace618
  * Kallman et al. (2004) Kallman, T. R., Palmeri, P., Bautista, M. A., Mendoza, C., & Krolik, J. H. 2004, ApJS, 155, 675, doi: 10.1086/424039
  * Kilpatrick et al. (2023) Kilpatrick, C. D., Foley, R. J., Jacobson-Galán, W. V., et al. 2023, ApJ, 952, L23, doi: 10.3847/2041-8213/ace4ca
  * Kochanek (2019) Kochanek, C. S. 2019, MNRAS, 483, 3762, doi: 10.1093/mnras/sty3363
  * Lundquist et al. (2023) Lundquist, M., O’Meara, J., & Walawender, J. 2023, Transient Name Server AstroNote, 160, 1
  * Martinez et al. (2023) Martinez, L., Bersten, M. C., Folatelli, G., Orellana, M., & Ertini, K. 2023, arXiv e-prints, arXiv:2310.08733, doi: 10.48550/arXiv.2310.08733
  * Matthews et al. (2023) Matthews, D., Margutti, R., AJ, N., et al. 2023, The Astronomer’s Telegram, 16091, 1
  * Mewe et al. (1986) Mewe, R., Lemen, J. R., & van den Oord, G. H. J. 1986, A&AS, 65, 511
  * Niu et al. (2023) Niu, Z.-X., Sun, N.-C., Maund, J. R., et al. 2023, arXiv e-prints, arXiv:2308.04677, doi: 10.48550/arXiv.2308.04677
  * Panjkov et al. (2023) Panjkov, S., Auchettl, K., Shappee, B. J., et al. 2023, arXiv e-prints, arXiv:2308.13101, doi: 10.48550/arXiv.2308.13101
  * Perley et al. (2023) Perley, D. A., Gal-Yam, A., Irani, I., & Zimmerman, E. 2023, Transient Name Server AstroNote, 119, 1
  * Pledger & Shara (2023) Pledger, J. L., & Shara, M. M. 2023, arXiv e-prints, arXiv:2305.14447, doi: 10.48550/arXiv.2305.14447
  * Quataert & Shiode (2012) Quataert, E., & Shiode, J. 2012, MNRAS, 423, L92, doi: 10.1111/j.1745-3933.2012.01264.x
  * Riess et al. (2022) Riess, A. G., Yuan, W., Macri, L. M., et al. 2022, ApJ, 934, L7, doi: 10.3847/2041-8213/ac5c5b
  * Schlafly & Finkbeiner (2011) Schlafly, E. F., & Finkbeiner, D. P. 2011, ApJ, 737, 103, doi: 10.1088/0004-637X/737/2/103
  * Schlegel et al. (1998) Schlegel, D. J., Finkbeiner, D. P., & Davis, M. 1998, ApJ, 500, 525, doi: 10.1086/305772
  * Singh Teja et al. (2023) Singh Teja, R., Singh, A., Basu, J., et al. 2023, arXiv e-prints, arXiv:2306.10284, doi: 10.48550/arXiv.2306.10284
  * Smith & Arnett (2014) Smith, N., & Arnett, W. D. 2014, ApJ, 785, 82, doi: 10.1088/0004-637X/785/2/82
  * Smith et al. (2023) Smith, N., Pearson, J., Sand, D. J., et al. 2023, arXiv e-prints, arXiv:2306.07964, doi: 10.48550/arXiv.2306.07964
  * Soraisam et al. (2023) Soraisam, M. D., Szalai, T., Van Dyk, S. D., et al. 2023, arXiv e-prints, arXiv:2306.10783, doi: 10.48550/arXiv.2306.10783
  * Van Dyk et al. (2023) Van Dyk, S. D., Srinivasan, S., Andrews, J. E., et al. 2023, arXiv e-prints, arXiv:2308.14844, doi: 10.48550/arXiv.2308.14844
  * Vasylyev et al. (2023) Vasylyev, S. S., Yang, Y., Filippenko, A. V., et al. 2023, ApJ, 955, L37, doi: 10.3847/2041-8213/acf1a3
  * Yamanaka et al. (2023) Yamanaka, M., Fujii, M., & Nagayama, T. 2023, arXiv e-prints, arXiv:2306.00263, doi: 10.48550/arXiv.2306.00263
  * Yaron et al. (2017) Yaron, O., Perley, D. A., Gal-Yam, A., et al. 2017, Nature Physics, 13, 510, doi: 10.1038/nphys4025
  * Zimmerman et al. (2023) Zimmerman, E. A., Irani, I., Chen, P., et al. 2023, arXiv e-prints, arXiv:2310.10727, doi: 10.48550/arXiv.2310.10727


12216200 LABEL:LastPageMar. 15, 2020Jul. 13, 2020

# Density of Metric Small Cancellation in Finitely Presented Groups

Alex Bishop  University of Technology Sydney, Australia
https://alexbishop.github.io<EMAIL_ADDRESS>and  Michal Ferov
University of Newcastle, Australia<EMAIL_ADDRESS>
###### Abstract.

Small cancellation groups form an interesting class with many desirable
properties. It is a well-known fact that small cancellation groups are
generic; however, all previously known results of their genericity are
asymptotic and provide no information about “small” group presentations. In
this note, we give closed-form formulas for both lower and upper bounds on the
density of small cancellation presentations, and compare our results with
experimental data.

###### Key words and phrases:

finitely presented groups, random groups, small cancellation.

##  1\. Introduction

Informally speaking, a group is a $\operatorname{C}^{\prime}(\lambda)$ small
cancellation group if it is given by a presentation that satisfies the
$\operatorname{C}^{\prime}(\lambda)$ metric small cancellation condition, i.e.
a presentation where no two relators share a common segment of proportion
$\lambda$ (see Subsection 2.1 for a formal definition). Small cancellation
groups form a class with many desirable algebraic and algorithmic properties.
For example, both the word problem and the conjugacy problem are uniformly
solvable in linear time by Dehn’s algorithm [5]. Following [1, Lemma 3] and
[6, Section 9.B] it is known that small cancellation presentations are
“generic” meaning that a random presentation will most likely present a small
cancellation group (see Subsection 2.2). Furthermore, given a finite
presentation one can easily check whether or not it satisfies the small
cancellation property: all one needs to do is to inspect all pairs of relators
for a common segment of critical length. For these reasons small cancellation
groups were suggested as a platform for computation in several cryptographic
protocols (see [11, 12, 4, 7]).

The results of [1] and [6] on genericity of small cancellation groups are
asymptotic, stating that a “big enough presentation” will, with overwhelming
probability, be a small cancellation presentation. In particular, neither of
these papers specify how big is “big enough”. For practical applications, such
as in cryptography, this is not sufficient. In this paper we improve the
aforementioned results by giving closed-form formulas for both a lower and an
upper bound on the probability that a random presentation satisfies the small
cancellation condition. Moreover, using these bounds, we are able to derive
the asymptotic bounds on genericity as given in [1, 6].

In Lemma 3.1, we will see that we have a lower bound as follows.

######  Theorem 1.

There is a function $p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)$ given by
a closed-form formula such that a presentation chosen uniformly at random from
the set of all presentations of the form $\langle X\mid W\rangle$, where
$|X|=r$, $|W|=m$ and $\ell_{1}\leqslant|w|\leqslant\ell_{2}$ for each $w\in
W$, is power-free and satisfies the metric small cancellation condition
$\operatorname{C}^{\prime}(\lambda)$ with probability at least
$p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)$. Moreover, we have

$1-p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)\leqslant
8m^{2}r\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)(2r-1)^{-\lambda\ell_{2}-1},$

and thus
$\lim_{\ell_{2}\to\infty}p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)=1$ for
each fixed $r\geqslant 2$, $\lambda$ and $m$.

Moreover, from Propositions 8 and 12 we have an upper bound on the probability
of small cancellation given in Theorem 2 below.

######  Theorem 2.

There is a function $p^{\geqslant}_{\lambda}(r,\ell,m)$ given by a closed-form
formula such that a presentation chosen uniformly at random from the set of
all presentations of the form $\langle X\mid W\rangle$, where $|X|=r$, $|W|=m$
and $|w|=\ell$ for all $w\in W$, is power-free and satisfies the metric small
cancellation condition $\operatorname{C}^{\prime}(\lambda)$ with probability
at most $p^{\geqslant}_{\lambda}(r,\ell,m)$. Moreover, for each $m\geqslant 1$
and $r\geqslant 2$, we have

$\ln(1/p^{\geqslant}_{\lambda}(r,\ell,m))\geqslant\frac{1}{8}{(m-1)}^{2}\ell{(2r-1)}^{-\lceil\lambda\ell\rceil},$

that is, $p^{\geqslant}_{\lambda}(r,\ell,m)$ is not simply the constant
function $1$. Notice that from Theorem 1 we have
$\lim_{\ell\to\infty}p^{\geqslant}_{\lambda}(r,\ell,m)=1$, and thus

$\lim_{\ell\to\infty}\ln(1/p^{\geqslant}_{\lambda}(r,\ell,m))=0$

for each fixed $r\geqslant 2$, $\lambda$ and $m$.

Using the lower bound presented in Section 3.1, we show that the probability
of obtaining a small cancellation presentation is non-trivial even for
relatively small parameters, and compare our results with experimental data.

The organisation of the paper is as follows. In Section 2, we provide the
preliminary notions; in particular, in Subsection 2.1 we recall the formal
definition of metric small cancellation, and in Subsection 2.2 we recall the
notion of random groups. In Section 3, we give the main results of this paper;
in particular, Subsection 3.1 derives a lower bound for the probability of
small cancellation in terms of the given parameters of the presentation, and
in Subsection 3.2 we give an upper bound. In Section 4.1, we combine these two
bounds to discuss the limitations on the choice of parameters in regards to
maximise the probability of small cancellation. Finally, in Appendix A we
compare our theoretical results with experimental data; in particular, we
provide several heat maps which show how our bounds differ as we vary the
parameters of the presentation.

##  2\. Preliminaries

Given a finite set $X=\\{x_{1},x_{2},\ldots,x_{r}\\}$, we denote the free
group generated by $X$ as $F(X)$. Further, we write $w\in F(X)$ to denote that
$w$ is a freely reduced word in $\left(X^{\pm 1}\right)^{*}$, that is, $w$
does not contain $xx^{-1}$ or $x^{-1}x$ as a factor for any $x\in X$. Notice
that each word $w\in F(X)$ corresponds to a unique element of the free group
on the generating set $X$.

Let $w=x_{i_{1}}^{\epsilon_{1}}x_{i_{2}}^{\epsilon_{2}}\cdots
x_{i_{k}}^{\epsilon_{k}}$ with $x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}}\in X$ and
each $\epsilon_{j}\in\\{-1,1\\}$. Then we define the _word length_ of $w$ as
$|w|_{X}=k$; and $|w|$ when the generating set $X$ is clear from the context.
Further, for each $0\leqslant d<k=|w|$ we write $w_{\ll d}$ to denote the
_(left) cyclic permutation of $w$ by a distance of $d$_, that is,

$w_{\ll d}=x_{i_{d+1}}^{\epsilon_{d+1}}x_{i_{d+2}}^{\epsilon_{d+2}}\cdots
x_{i_{k}}^{\epsilon_{k}}\
x_{i_{1}}^{\epsilon_{1}}x_{i_{2}}^{\epsilon_{2}}\cdots
x_{i_{d}}^{\epsilon_{d}}.$

We say that a word $w$ is _cyclically reduced_ if all of its cyclic
permutations are freely reduced, or equivalently, if
$w=x_{i_{1}}^{\epsilon_{1}}x_{i_{2}}^{\epsilon_{2}}\cdots
x_{i_{k}}^{\epsilon_{k}}$ is freely reduced and $x_{i_{1}}^{\epsilon_{1}}\neq
x_{i_{k}}^{-\epsilon_{k}}$ with respect to the free group $F(X)$.

Let $X$ be a set with $r=|X|$ elements, and $W\in F(X)^{m}$ be a list of $m$
words, where each $w\in W$ is cyclically reduced; then $\langle X\mid
W\rangle$ is a presentation with $r$ generators and $m$ relators. Notice that
$W$ may contain the same element twice; and further presentations that differ
only by permuting relators are considered to be distinct. For example $\langle
x,y\mid x^{2},y^{2}\rangle$ and $\langle x,y\mid y^{2},x^{2}\rangle$ are
considered to be distinct presentations. For the ease of writing, as a slight
abuse of notation, $w\in W$ will denote that there is an
$i\in\\{1,2,\ldots,m\\}$ such that $\pi_{i}(W)=w$, where $\pi_{i}\colon
F(X)^{m}\to F(X)$ is the projection onto the $i$-th component of $F(X)^{m}$.

###  2.1. Small Cancellation Presentations

The notation and terminology used in this section follows that of [8].

We denote the _symmetric closure_ of a finite list of words $W\subset
F(X)^{*}$ as

$W^{S}=\left\\{w_{\ll d},(w_{\ll d})^{-1}\,\middle|\,w\in W\text{ and
}0\leqslant d<|w|\right\\}.$

We say that a word $u$ is a _symmetric consequence_ of a word $w$ if
$u\in(w)^{S}$. Further, we say that $W$ is _minimal_ if there is no proper
sublist $U$ such that $U^{S}=W^{S}$. For example, $(aaaa,baba,abab)$ is not
minimal as $baba=abab_{\ll 1}$, however, the list $(aaaa,abab)$ is minimal.

Let $w\in F(X)$, then the maximum size of $(w)^{S}$ is given by $2|w|$, that
is, $|(w)^{S}|\leqslant 2|w|$. Notice that a cyclically reduced word $w$
factors as a proper power, $w=u^{n}$, with $n>1$, if and only if
$|(w)^{S}|<2|w|$; thus we say that $w$ is _power-free_ if we have
$|(w)^{S}|=2|w|$.

Let $\mathcal{P}=\left\langle X\,\middle|\,W\right\rangle$ be a presentation
where $W\in F(X)^{*}$ is the list of cyclically reduced relators. Then, we say
that $\mathcal{P}$ has _metric small cancellation
$\operatorname{C}^{\prime}(\lambda)$_ if the list $W$ is minimal, each word
$w$ in the list $W$ is power-free, and any pair of words $u,w\in W^{S}$ may
only have a short common prefix; in particular, if $u=pa$, $w=pb$ with
$p,a,b\in F(X)$ such that $|u|=|p|+|a|$ and $|w|=|p|+|b|$, then
$|p|<\lambda\cdot\min(|u|,|w|)$.

Furthermore, as Greedinger’s lemma [5] applies to presentations with property
$\operatorname{C}^{\prime}(1/6)$, we will only be interested in the case where
$\lambda\leqslant 1/6$. From our definition of small cancellation
presentations as given above, a group with property
$\operatorname{C}^{\prime}(1/6)$ is torsion-free hyperbolic.

Moreover, in this note we will only be interested in groups with at least two
generators. Thus, in the remainder of this paper we have $r=|X|\geqslant 2$.

###  2.2. Random groups

In this subsection we recall the notion of random groups and random
presentations. For more details we refer the reader to the survey [9]. Notice
that we require each relater in a presentation to be cyclically reduced.

In this subsection, we fix a generating set $X$ with cardinality
$r=|X|\geqslant 2$. As stated previously, $\langle X\mid W\rangle$ is a
presentation on $m$ relators over $X$ if $W\in F(X)^{m}$ where each relator
$w\in W$ is cyclically reduced. We write $\mathcal{W}_{m,\ell}$ for the set of
all presentations with $m$ relators, each with length at most $\ell$; and
$\mathcal{W}=\bigcup_{m=1}^{\infty}\bigcup_{\ell=1}^{\infty}\mathcal{W}_{m,\ell}$
for the set of all presentation.

Let $\mathcal{P}\subseteq\mathcal{W}$ be a set of presentations, then we say
that a randomly chosen presentation from $\mathcal{W}_{m,\ell}$ belongs to the
set $\mathcal{P}$ with probability

$p_{m,\ell}(\mathcal{P})=\frac{|\mathcal{P}\cap\mathcal{W}_{m,\ell}|}{|\mathcal{W}_{m,\ell}|}.$

The main two models of randomness in group theory are the _few relations
model_ and the _density model_. We say that a set of presentations
$\mathcal{P}\subseteq\mathcal{W}$ is _generic_ in the few relation model if,
for each $m\geqslant 1$, we have

$\lim_{\ell\to\infty}p_{m,\ell}(\mathcal{P})=1.$

Furthermore, we say that $\mathcal{P}$ is _strongly generic_ if this limit
converges exponentially fast. It was proved in [1, Lemma 3] that the set of
all presentations satisfying the metric small cancellation
$\operatorname{C}^{\prime}(\lambda)$ is strongly generic.

Let some $d$ with $0\leqslant d\leqslant 1$ be given and let
$f_{X,d}(\ell)=(2r-1)^{d\ell}$. Then, we say that a set of presentations
$\mathcal{P}$ is _generic at density $d$_ if

$\lim_{\ell\to\infty}p_{f_{X,d}(\ell),\ell}(\mathcal{P})=1$

and we say that $\mathcal{P}$ is _negligible at density $d$_ if

$\lim_{\ell\to\infty}p_{f_{X,d}(\ell),\ell}(\mathcal{P})=0.$

It was proved in [6, Section 9.B] that, for $0<\lambda<1$, the set of all
presentations satisfying the metric small cancellation condition
$\operatorname{C}^{\prime}(\lambda)$ is generic at density $d$ if
$d<\lambda/2$, and negligible at density $d$ if $d>\lambda/2$.

Using the result in Theorem 1 we are able to show that small cancellation is
strongly generic with respect to the few relations model, and that small
cancellation is generic at densities $d<\lambda/2$. In particular, from
Theorem 1 we have the upper bound

$1-p^{\leqslant}_{\lambda}(r,0,\ell,m)\leqslant
8m^{2}r\ell^{3}(2r-1)^{-\lambda\ell-1},$

where the limit
$\lim_{\ell\to\infty}(1-p^{\leqslant}_{\lambda}(r,0,\ell,m))=0$ converges
exponentially fast for each $r$, $m$ and $\lambda$. Then, we find that the
limit $\lim_{\ell\to\infty}p^{\leqslant}_{\lambda}(r,0,\ell,m)=1$ converges
exponentially fast, and thus small cancellation is strongly generic. Moreover,
we find that, for each $0\leqslant d<1$, we also have the bound

$1-p^{\leqslant}_{\lambda}(r,0,\ell,f_{X,d}(\ell))\leqslant
8r\ell^{3}(2r-1)^{(2d-\lambda)\ell-1}.$

Then, we see that
$\lim_{\ell\to\infty}(1-p^{\leqslant}_{\lambda}(r,0,\ell,f_{X,d}(d\ell)))=0$
for each $d<\lambda/2$, and thus small cancellation is generic at density $d$
if $d<\lambda/2$.

Another version of the density model was considered in [2], where the authors
fix the length and let the number of generators grow. We will call this model
the Ashcroft and Roney-Dougal density model. Using Theorem 1 we immediately
get a statement similar to the positive part of [6, Section 9.B].

######  Proposition 3.

The set of power-free finite presentations satisfying property
$\operatorname{C}^{\prime}(\lambda)$ is generic in the density model of
Ashcroft and Roney-Dougal at densities $d<\lambda/2$.

##  3\. Density of Small Cancellation

As was mentioned in the previous section, it is well-known that small
cancellation is generic, i.e. “almost all” presentations satisfy metric small
cancellation. However, both [1, Lemma 3] and [6, Section 9.B] are purely
asymptotic statements and neither informs us of what happens for relatively
small parameters. Thus, in this section we give closed-form formulas for both
lower and upper bounds on the probability that a random presentation with
given parameters will have small cancellation.

To simplify notation we write $F_{r}$ to denote a free group of rank $r$, that
is, $F_{r}=F(X)$ where $X=\\{x_{1},x_{2},\ldots,x_{r}\\}$. Let
$\operatorname{FR}(r,\ell)$ denote the number of freely reduced words of
length $\ell$ in $F_{r}$, then

$\operatorname{FR}(r,\ell)=2r(2r-1)^{\ell-1}.$

Further, let $\operatorname{CR}(r,\ell)$ denote the number of cyclically
reduced words of length $\ell$ in $F_{r}$, then, as was shown by Rivin [10,
Theorem 1.1],

$\operatorname{CR}(r,\ell)=(2r-1)^{\ell}+1+(r-1)\left(1+(-1)^{\ell}\right).$

Moreover, we write $\operatorname{CR}(r,\ell_{1},\ell_{2})$ to denote the
total number of cyclically reduced words of length $\ell$, where
$\ell_{1}\leqslant\ell\leqslant\ell_{2}$, in $F_{r}$. That is,

$\operatorname{CR}(r,\ell_{1},\ell_{2})=\sum_{\ell=\ell_{1}}^{\ell_{2}}\operatorname{CR}(r,\ell).$

Notice that, if a presentation $\mathcal{P}=\left\langle X\mid W\right\rangle$
does not satisfy small cancellation $\operatorname{C}^{\prime}(\lambda)$, then
it must satisfy at least one of the following two conditions.

  1. (1)

$\operatorname{NC}_{\lambda}^{1}$ — there is a relator $w\in W$, and two
offsets $d_{1},d_{2}\in\mathbb{N}$ with $0\leqslant d_{1}<d_{2}<|w|$, such
that $w^{\prime}=w_{\ll d_{1}}$ and $w^{\prime\prime}=w_{\ll d_{2}}$ factor as
$w^{\prime}=xa$, $w^{\prime\prime}=yb$ where $a,b,x,y\in F_{r}$, $x=y^{\pm 1}$
and $|x|\geqslant\lambda|w|$.

  2. (2)

$\operatorname{NC}_{\lambda}^{2}$ — there are two relators $w_{1},w_{2}\in W$
with cyclic permutations $w_{1}^{\prime}$ and $w_{2}^{\prime}$, respectively,
that factor as $w_{1}^{\prime}=xa$ and $w_{2}^{\prime}=yb$ where $a,b,x,y\in
F_{r}$, $x=y^{\pm 1}$ and $|x|\geqslant\lambda\cdot\min(|w_{1}|,|w_{2}|)$.

We write $\operatorname{NC}_{\lambda}^{1}(r,\ell)$ to denote the number of
length $\ell$ words $w\in F_{r}$ satisfying property
$\operatorname{NC}_{\lambda}^{1}$; and
$\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})$ to denote the number of
word pairs $w_{1},w_{2}\in F_{r}$, each with lengths between $\ell_{1}$ and
$\ell_{2}$, that satisfying property $\operatorname{NC}_{\lambda}^{2}$.
Furthermore, we write $\operatorname{NC}_{\lambda}^{1}(r,\ell_{1},\ell_{2})$
to denote the sum
$\sum_{\ell=\ell_{1}}^{\ell_{2}}\operatorname{NC}_{\lambda}^{1}(r,\ell)$; and
$\operatorname{NC}_{\lambda}^{2}(r,\ell)$ to denote
$\operatorname{NC}_{\lambda}^{2}(r,\ell,\ell)$.

Suppose that we choose a presentation $\mathcal{P}=\left\langle X\mid
W\right\rangle$ uniformly at random from the class of presentations with
$|X|=r$, $|W|=m$ and $\ell_{1}\leqslant|w|\leqslant\ell_{2}$ for each $w\in
W$. Then, we denote the probability of $\mathcal{P}$ having property
$\operatorname{C}^{\prime}(\lambda)$ as $p_{\lambda}(r,\ell_{1},\ell_{2},m)$.
In the remainder of this section, we derive lower and upper bounds for this
probability.

###  3.1. Lower bounds

In the following, we derive a closed-form lower bound
$p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)$ on the probability of a
randomly chosen presentation having small cancellation with the given
parameters.

Clearly, we have the lower bound

$p_{\lambda}(r,\ell_{1},\ell_{2},m)\geqslant
1-m\cdot\frac{\operatorname{NC}_{\lambda}^{1}(r,\ell_{1},\ell_{2})}{\operatorname{CR}(r,\ell_{1},\ell_{2})}-\binom{m}{2}\cdot\frac{\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})}{\operatorname{CR}(r,\ell_{1},\ell_{2})^{2}}.$
(1)

Thus, to find a lower bound on $p_{\lambda}(r,\ell_{1},\ell_{2},m)$, we will
derive upper bounds on $\operatorname{NC}_{\lambda}^{1}(r,\ell)$ and
$\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})$. In particular, we
obtain the bounds given in Lemmas 4 and 6 below.

######  Lemma 4.

We have the upper bound

$\operatorname{NC}_{\lambda}^{1}(r,\ell)\leqslant
2\ell(\ell-2\left\lceil\lambda\ell\right\rceil-2)\operatorname{FR}(r,\left\lceil\lambda\ell\right\rceil)(2r-1)^{\ell-2\left\lceil\lambda\ell\right\rceil}+\sum_{k=1}^{\left\lceil\lambda\ell\right\rceil}\ell\operatorname{CR}(r,k)(2r-1)^{\ell-\left\lceil\lambda\ell\right\rceil-k}.$

######  Proof 3.1.

Let $w\in F_{r}$ be a length $\ell$ cyclically reduced word chosen uniformly
at random. If $w$ satisfies property $\operatorname{NC}_{\lambda}^{1}$, then
one of the following two cases must apply.

  1. (1)

There is a cyclic permutation $w^{\prime}=w_{\ll d}$ that factors as both
$w^{\prime}=xa$ and $w^{\prime}=b_{1}yb_{2}$ where $a,b_{1},b_{2},x,y\in
F_{r}$ with $x=y^{\pm 1}$, $|x|=\lceil\lambda\ell\rceil$ and
$1\leqslant|b_{1}|\leqslant|x|$.

  2. (2)

There is a cyclic permutation $w^{\prime}=w_{\ll d}$ that factors as
$w^{\prime}=xayb$ where $a,b,x,y\in F_{r}$ with $x=y^{\pm 1}$,
$|x|=\lceil\lambda\ell\rceil$ and $|a|,|b|\geqslant 1$.

In case 1 it follows that $x=y$ and that $x$ is of the form

$x=(x_{1}x_{2}\cdots x_{k})^{p}\ x_{1}x_{2}\cdots x_{q}$

where $k=|b_{1}|$, $0\leqslant q<|b_{1}|$ and the subword $x_{1}x_{2}\cdots
x_{k}$ is cyclically reduced.

To see this, let $k=|b_{1}|$ and let $p,q\in\mathbb{N}$ be such that
$|x|=p\cdot k+q$ where $0\leqslant q<k$. Now suppose $k=|x|$, so that
$w^{\prime}$ factors as $w^{\prime}=xyb_{2}$; thus $x\neq y^{-1}$ and
$x=x_{1}x_{2}\cdots x_{k}$ is cyclically reduced. Suppose instead that
$1\leqslant k<|x|$; then $x$ and $y$ must factor as $x=x^{\prime}c$ and
$y=cy^{\prime}$ where $x^{\prime},y^{\prime},c\in F_{r}$ and $c$ is of length
$|x|-k$. Thus, if $x=y^{-1}$, then $c=c^{-1}$ which is not possible as
$c\neq\varepsilon$. Hence, $x=y$ and, since $x$ and $y$ overlap, it follows
that

$x=(x_{1}x_{2}\cdots x_{k})^{p}\ x_{1}x_{2}\cdots x_{q}$

where the subword $x_{1}x_{2}\cdots x_{k}$ is cyclically reduced.

We are now ready to consider the number of words counted in these two cases.
Let us consider case 1. Suppose that $k=|b_{1}|$; then there are $\ell$
choices for the shift $d$, $\operatorname{CR}(r,k)$ choices for the subword
$x=(x_{1}x_{2}\cdots x_{k})^{p}x_{1}x_{2}\cdots x_{q}$, and
$(2r-1)^{\ell-\lceil\lambda\ell\rceil-k}$ choices for the remaining letters in
the word $w$. Thus, by summing over all such choices for $k$, we obtain

$\sum_{k=1}^{\lceil\lambda\ell\rceil}\ell\operatorname{CR}(r,k)(2r-1)^{\ell-\lceil\lambda\ell\rceil-k}$

as an upper bound for the number of counted words.

Now consider case 2. There are $\ell$ choices for the offset $d$,
$2\cdot\operatorname{FR}(r,\lceil\lambda\ell\rceil)$ choices for the pair $x$
and $y$, $\ell-2\lceil\lambda\ell\rceil-2$ choices for $|a|$, and
$(2r-1)^{\ell-2\lceil\lambda\ell\rceil}$ choices for the remaining letters of
the word $w$. Thus, we obtain

$2\ell(\ell-2\lceil\lambda\ell\rceil-2)\operatorname{FR}(r,\lceil\lambda\ell\rceil)(2r-1)^{\ell-2\lceil\lambda\ell\rceil}$

as an upper bound on the number of such words counted in this case.

Thus, by combining our two previous bounds we obtain our result.

######  Corollary 5.

We have the upper bounds

$\operatorname{NC}_{\lambda}^{1}(r,\ell)\leqslant
4r\ell^{2}(2r-1)^{\ell-\lambda\ell-1}$

and

$\operatorname{NC}_{\lambda}^{1}(r,\ell_{1},\ell_{2})\leqslant
4r\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)(2r-1)^{\ell_{2}-\lambda\ell_{2}-1}$

for each $r\geqslant 2$.

######  Proof 3.2.

Applying the upper bound

$\operatorname{CR}(r,\ell)\leqslant(2r-1)^{\ell}+2r-1$

to the inequality given in Lemma 4 we obtain

$\operatorname{NC}_{\lambda}^{1}(r,\ell)\leqslant
2\ell(\ell-2\left\lceil\lambda\ell\right\rceil-2)\cdot\operatorname{FR}(r,\lceil\lambda\ell\rceil)\cdot(2r-1)^{\ell-2\left\lceil\lambda\ell\right\rceil}\\\
+\sum_{k=1}^{\left\lceil\lambda\ell\right\rceil}\ell\left[(2r-1)^{k}+2r-1\right](2r-1)^{\ell-\left\lceil\lambda\ell\right\rceil-k}.$

After some rearrangement, we obtain

$\operatorname{NC}_{\lambda}^{1}(r,\ell)\leqslant
4r\ell(\ell-2\left\lceil\lambda\ell\right\rceil-2)(2r-1)^{\ell-\left\lceil\lambda\ell\right\rceil-1}+\ell(2r-1)^{\ell-\left\lceil\lambda\ell\right\rceil}\sum_{k=1}^{\left\lceil\lambda\ell\right\rceil}\left[1+(2r-1)^{1-k}\right].$

From this, we can then obtain the upper bound

$\operatorname{NC}_{\lambda}^{1}(r,\ell)\leqslant
4r\ell(\ell-2\left\lceil\lambda\ell\right\rceil-2)(2r-1)^{\ell-\lambda\ell-1}+\ell(2r-1)^{\ell-\lambda\ell}\left(\left\lceil\lambda\ell\right\rceil+2\right).$

Thus,

$\operatorname{NC}_{\lambda}^{1}(r,\ell)\leqslant\left[4r(\ell-2\left\lceil\lambda\ell\right\rceil-2)+(2r-1)(\left\lceil\lambda\ell\right\rceil+2)\right]\ell(2r-1)^{\ell-\lambda\ell-1}.$

From this upper bound, we can then obtain our bound

$\operatorname{NC}_{\lambda}^{1}(r,\ell)\leqslant
4r\ell^{2}(2r-1)^{\ell-\lambda\ell-1}.$

Then, using the bound
$\sum_{\ell=\ell_{1}}^{\ell_{2}}\ell^{2}a^{\ell}\leqslant\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)a^{\ell_{2}}$
for each $a\geqslant 1$ and $1\leqslant\ell_{1}\leqslant\ell_{2}$, we obtain
our bound on $\operatorname{NC}^{1}_{\lambda}(r,\ell_{1},\ell_{2})$.

######  Lemma 6.

We have the upper bound

$\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})\leqslant\sum_{j_{1}=\ell_{1}}^{\ell_{2}}\sum_{j_{2}=\ell_{1}}^{\ell_{2}}2j_{1}j_{2}\operatorname{FR}(r,\left\lceil\lambda\cdot\min(j_{1},j_{2})\right\rceil)(2r-1)^{j_{1}+j_{2}-2\left\lceil\lambda\cdot\min(j_{1},j_{2})\right\rceil}.$

######  Proof 3.3.

Suppose that we choose two cyclically reduced words $v,w\in F_{r}$ of lengths
$j_{1}$ and $j_{2}$, respectively, where $\ell_{1}\leqslant
j_{i}\leqslant\ell_{2}$ for each $j_{i}$. Then for the pair of words $v,w$ to
satisfy property $\operatorname{NC}_{\lambda}^{2}$ there must be cyclic
permutations $v^{\prime}={v}_{\ll d_{1}}$ and $w^{\prime}=w_{\ll d_{2}}$ that
factor as $v^{\prime}=xa$ and $w^{\prime}=yb$ where $a,b,x,y\in F_{r}$,
$x=y^{\pm 1}$ and $|x|=\lceil\lambda\cdot\min(j_{1},j_{2})\rceil$.

Thus, we have $j_{1}$ possible choices for the offset $d_{1}$, $j_{2}$
possible choices for the offset $d_{2}$, at most
$2\cdot\operatorname{FR}(r,\lceil\lambda\cdot\min(j_{1},j_{2})\rceil)$
possible choices for the pair of words $x$ and $y$, at most
$(2r-1)^{j_{1}-\lceil\lambda\cdot\min(j_{1},j_{2})\rceil}$ possible choices
for the word $a$, and at most
$(2r-1)^{j_{2}-\lceil\lambda\cdot\min(j_{1},j_{2})\rceil}$ possible choices
for the word $b$. Hence, we have an upper bound of

$2j_{1}j_{2}\operatorname{FR}(r,\lceil\lambda\cdot\min(j_{1},j_{2})\rceil)(2r-1)^{j_{1}+j_{2}-2\lceil\lambda\cdot\min(j_{1},j_{2})\rceil}$

for the number of pairs $v$ and $w$, as before, satisfying property
$\operatorname{NC}_{\lambda}^{2}$.

Thus, by summing over $j_{1}$ and $j_{2}$ from $\ell_{1}$ to $\ell_{2}$, we
obtain our bound.

######  Corollary 7.

We have the upper bounds

$\operatorname{NC}_{\lambda}^{2}(r,\ell)\leqslant
4r\ell^{2}(2r-1)^{2\ell-\lambda\ell-1}$

and

$\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})\leqslant
16r\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)(2r-1)^{2\ell_{2}-\lambda\ell_{2}-1}.$

######  Proof 3.4.

From the bound in Lemma 6 and $\operatorname{FR}(r,\ell)=2r(2r-1)^{\ell-1}$ we
immediately obtain the upper bound

$\operatorname{NC}_{\lambda}^{2}(r,\ell)\leqslant
4r\ell^{2}(2r-1)^{2\ell-\lambda\ell-1}.$

To derive our second bound, we rewrite the bound in Lemma 6 to obtain

$\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})\leqslant
2\sum_{j_{1}=\ell_{1}}^{\ell_{2}}\sum_{j_{2}=j_{1}}^{\ell_{2}}2j_{1}j_{2}\operatorname{FR}(r,\left\lceil\lambda
j_{1}\right\rceil)(2r-1)^{j_{1}+j_{2}-2\left\lceil\lambda j_{1}\right\rceil}.$

We then see that we have the upper estimate

$\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})\leqslant
8r\ell_{2}^{2}(2r-1)^{-1}\sum_{j_{1}=\ell_{1}}^{\ell_{2}}(2r-1)^{j_{1}-\lambda
j_{1}}\sum_{j_{2}=j_{1}}^{\ell_{2}}(2r-1)^{j_{2}}.$

Since $(2r-1)>2$, we have
$\sum_{j_{2}=j_{1}}^{\ell_{2}}(2r-1)^{j_{2}}\leqslant 2(2r-1)^{\ell_{2}}$, and
thus we have

$\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})\leqslant
16r\ell_{2}^{2}(2r-1)^{\ell_{2}-1}\sum_{j_{1}=\ell_{1}}^{\ell_{2}}(2r-1)^{j_{1}-\lambda
j_{1}}.$

Then, using the bound
$\sum_{j_{1}=\ell_{1}}^{\ell_{2}}a^{j_{1}}\leqslant(\ell_{2}-\ell_{1}+1)a^{\ell_{2}}$
for each $a\geqslant 1$, we have

$\operatorname{NC}_{\lambda}^{2}(r,\ell_{1},\ell_{2})\leqslant
16r\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)(2r-1)^{2\ell_{2}-\lambda\ell_{2}-1}$

as required.

Using the bounds obtained in this section, we prove Theorem 1 as follows.

######  Proof 3.5 (Proof of Theorem 1).

Combining the bounds in Lemmas 4 and 6 with the inequality (1) we obtain a
lower bound $p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)$ on the
probability of small cancellation. That is, we have
$p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)\leqslant
p_{\lambda}(r,\ell_{1},\ell_{2},m)$.

From the upper bound

$\operatorname{CR}(r,\ell_{1},\ell_{2})\geqslant(2r-1)^{\ell_{2}}$

and the bounds in Corollaries 5 and 7, we obtain the bound

$1-p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)\leqslant\frac{m}{(2r-1)^{\ell_{2}}}\cdot
4r\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)(2r-1)^{\ell_{2}-\lambda\ell_{2}-1}\\\
+\frac{m(m-1)}{2(2r-1)^{2\ell_{2}}}\cdot
16r\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)(2r-1)^{2\ell_{2}-\lambda\ell_{2}-1}.$

Thus, we obtain the upper bound

$1-p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)\leqslant
8m^{2}r\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)(2r-1)^{-\lambda\ell_{2}-1}$

as required.

###  3.2. Upper bounds

In this section, we present an upper bound on the probability
$p_{\lambda}(r,\ell,\ell,m)$ in Proposition 8 below.

######  Proposition 8.

If $\operatorname{FR}(r,\lceil\lambda\ell\rceil)<2m\ell$, then
$p_{\lambda}(r,\ell,\ell,m)=0$; otherwise

$\frac{1}{\operatorname{CR}(r,\ell)^{m}}\prod_{i=1}^{m}\min\Bigg{[}\omega_{i}(r,\ell,m),\
\beta(r,\ell,m)\cdot\prod_{k=1}^{\ell_{1}}\min\bigg{(}(2r-1)^{\lceil\lambda\ell\rceil},\,\alpha_{i,k}(r,\ell,m)\bigg{)}\Bigg{]}$

is an upper bound for $p_{\lambda}(r,\ell,\ell,m)$ where

$\displaystyle\omega_{i}(r,\ell,m)$
$\displaystyle=\operatorname{CR}(r,\ell)-4(i-1)\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1},$
$\displaystyle\beta(r,\ell,m)$ $\displaystyle=\operatorname{FR}(r,\ell_{2}),$
$\displaystyle\alpha_{i,1}(r,\ell,m)$
$\displaystyle=\operatorname{FR}(r,\lceil\lambda\ell\rceil)-2(i-1)\ell\mathrm{\
\ and}$ $\displaystyle\alpha_{i,k}(r,\ell,m)$
$\displaystyle=\operatorname{FR}(r,\lceil\lambda\ell\rceil)-2(i-1)\ell-2\Big{(}(k-2)\lceil\lambda\ell\rceil+\ell_{2}+1\Big{)}$

for each $i\geqslant 1$, $k\geqslant 2$ and
$\ell=\ell_{1}\lceil\lambda\ell\rceil+\ell_{2}$ with
$\ell_{1},\ell_{2}\in\mathbb{N}$ and
$0\leqslant\ell_{2}<\lceil\lambda\ell\rceil$.

######  Proof 3.6.

Let $\mathcal{P}=\left\langle X\,|\,W\right\rangle$ be a presentation such
that $r=|X|$, $m=|W|$ and each word in the list $W$ is cyclically reduced with
length $\ell$. We write $(w_{1},w_{2},\ldots,w_{m})=W$ for the list of
relators, and the length as $\ell=\ell_{1}\lceil\lambda\ell\rceil+\ell_{2}$
where $\ell_{1},\ell_{2}\in\mathbb{N}$ and
$0\leqslant\ell_{2}<\lceil\lambda\ell\rceil$. We factor each relator $w_{i}$
as

$w_{i}=b_{i}\,a_{i,1}\,a_{i,2}\,a_{i,3}\,a_{i,4}\,\cdots\,a_{i,\ell_{1}}$ (2)

where each $|a_{i,k}|=\lceil\lambda\ell\rceil$ and $|b_{i}|=\ell_{2}$.

If $\mathcal{P}$ satisfies property $\operatorname{C}^{\prime}(\lambda)$, then
each word of the form $(w_{i}^{\pm 1})_{\ll d}$, with $0\leqslant d<\ell$, has
a distinct length $\lceil\lambda\ell\rceil$ prefix. Thus, if
$\operatorname{FR}(r,\lceil\lambda\ell\rceil)<2m\ell$, then
$p_{\lambda}(r,\ell,\ell,m)=0$ as there would be no choice for these $2m\ell$
distinct prefixes. Thus, in the remainder of this proof, we will assume that
$\operatorname{FR}(r,\lceil\lambda\ell\rceil)\geqslant 2m\ell$ which also
implies that

$\operatorname{CR}(r,\ell)-4m\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}\geqslant
0$ (3)

as each such freely reduced word is the prefix of at least

$(2r-2)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}$

cyclically reduced words. Thus, all that remains is to establish our upper
bound.

In the remainder of this proof, we place an upper bound on the number of
choices for $W$ which result in $\mathcal{P}$ having the small cancellation
property $\operatorname{C}^{\prime}(\lambda)$. In particular, we will describe
a process of choosing relators such that the resulting presentation satisfies
property $\operatorname{C}^{\prime}(\lambda)$.

Suppose that we have already chosen the relators $w_{1},w_{2},\ldots,w_{i-1}$
in the presentation. Then, we derive an upper bound on the number of choices
for the relator $w_{i}$ for which the presentation may satisfy property
$\operatorname{C}^{\prime}(\lambda)$.

For $\mathcal{P}$ to satisfy property $\operatorname{C}^{\prime}(\lambda)$,
the length $\lceil\lambda\ell\rceil$ prefix of $w_{i}$ must be distinct from
each length $\lceil\lambda\ell\rceil$ prefix of $(w_{j}^{\pm 1})_{\ll d}$,
where $1\leqslant j<i$ and $0\leqslant d<\ell$, which must themselves be
pairwise distinct. Thus, we find that there are $2(i-1)$ prefixes that need to
be avoided when choosing the relator. Moreover, since there are
$(2r-2)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}$ cyclically reduced words
corresponding to each avoided prefix, there are at most

$\omega_{i}(r,\ell,m)=\operatorname{CR}(r,\ell)-4(i-1)\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}$

choices for the word $w_{i}$; and from (3) we know $w_{i}(r,\ell,m)$ is non-
negative.

Now consider the word $w_{i}$ as written in (2); we will now place another
upper bound on the number of choices for the word $w_{i}$ by deriving an upper
bound on the number of choices for each of its factors. Firstly, since $w_{i}$
is cyclically reduced, there are no more than
$\beta(r,\ell,m)=\operatorname{FR}(r,\ell_{2})$ choices for the factor
$b_{i}$, and no more than $(2r-1)^{\lceil\lambda\ell\rceil}$ choices for each
factor of the form $a_{i,j}$. Moreover, since $a_{i,1}$ must be freely reduced
and distinct from each length $\lceil\lambda\ell\rceil$ prefix of some
$(w_{j}^{\pm 1})_{\ll d}$, with $1\leqslant j<i$ and $0\leqslant d<\ell$, we
find that there can be at most

$\alpha_{i,1}(r,\ell,m)=\operatorname{FR}(r,\ell)-2(i-1)\ell$

choices for the factor $a_{i,1}$. Now suppose that we have made a choice for
the factors $b_{i}a_{i,1}a_{i,2}\cdots a_{i,k-1}$ with $k\geqslant 2$; then
the factor $a_{i,k}$ must also avoid each length $\lceil\lambda\ell\rceil$
subword of $(b_{i}a_{i,1}a_{i,2}\cdots a_{i,k-1})^{\pm 1}$. Thus, there are at
most

$\alpha_{i,k}(r,\ell,m)=\operatorname{FR}(r,\lceil\lambda\ell\rceil)-2(i-1)\ell-2\Big{(}(k-2)\lceil\lambda\ell\rceil+\ell_{2}+1\Big{)}$

choices for the factor $a_{i,k}$.

Hence, after making a choice for the words $w_{1},w_{2},\ldots,w_{i-1}$, we
find that there are no more than

$\min\left[\omega_{i}(r,\ell,m),\
\beta(r,\ell,m)\cdot\prod_{k=1}^{\ell_{1}}\min\bigg{(}(2r-1)^{\lceil\lambda\ell\rceil},\,\alpha_{i,k}(r,\ell,m)\bigg{)}\right]$

choices for the word $w_{i}$.

Thus, by combining our bounds for each $w_{i}$ we obtain our desired upper
bound on the probability $p_{\lambda}(r,\ell,\ell,m)$.

######  Corollary 9.

If $\operatorname{FR}(r,\lceil\lambda\ell\rceil)\geqslant 2m\ell$, then

$p_{\lambda}(r,\ell,\ell,m)\leqslant\frac{1}{\operatorname{CR}(r,\ell)^{m^{\prime}}}\left(\operatorname{CR}(r,\ell)-4m^{\prime}\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}\right)^{m^{\prime}}$

where $m^{\prime}=\lfloor m/2\rfloor$.

######  Proof 3.7.

From Proposition 8, we see that, if
$\operatorname{FR}(r,\lceil\lambda\ell\rceil)\geqslant 2m\ell$, then

$p_{\lambda}(r,\ell,\ell,m)\leqslant\prod_{i=1}^{m}\frac{\omega_{i}(r,\ell,m)}{\operatorname{CR}(r,\ell)}$

where

$\omega_{i}(r,\ell,m)=\operatorname{CR}(r,\ell)-4(i-1)\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}.$

Then, since $0\leqslant\omega_{i}(r,\ell,m)\leqslant\operatorname{CR}(r,\ell)$
where $1\leqslant i\leqslant m$, we see that

$p_{\lambda}(r,\ell,\ell,m)\leqslant\prod_{i=m^{\prime}+1}^{m}\frac{\omega_{i}(r,\ell,m)}{\operatorname{CR}(r,\ell)}.$

Notice that $\omega_{i}(r,\ell,m)\leqslant\omega_{m^{\prime}+1}(r,\ell,m)$ for
each $i\geqslant m^{\prime}+1$. We see that

$p_{\lambda}(r,\ell,\ell,m)\leqslant\left(\frac{\omega_{m^{\prime}+1}(r,\ell,m)}{\operatorname{CR}(r,\ell)}\right)^{m^{\prime}}.$

That is,

$p_{\lambda}(r,\ell,\ell,m)\leqslant\frac{1}{\operatorname{CR}(r,\ell)^{m^{\prime}}}\left(\operatorname{CR}(r,\ell)-4m^{\prime}\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}\right)^{m^{\prime}}$

as required.

From Proposition 8, given above, we have an upper bound
$p^{\geqslant}_{\lambda}(r,\ell,m)$ such that
$p^{\geqslant}_{\lambda}(r,\ell,m)\geqslant p_{\lambda}(r,\ell,\ell,m)$. At
the end of the following section, we will see that this upper bound is indeed
the one described in Theorem 2.

##  4\. Finding Limitations on the Parameters

In this section, we derive several conditions for small cancellation to take
place with a specified probability. In particular, we show that, if we wish to
have $p_{\lambda}(r,\ell_{1},\ell_{2},m)\geqslant p$ for some $p<1$, then we
can do so by either choosing $r$ or $\ell_{2}$ to be sufficiently large, or,
if possible, by choosing $m$ to be sufficiently small. Moreover, we establish
an upper bound on the value of $m$ for small cancellation to occur with a
given probability. This section concludes with a proof of Theorem 2.

######  Proposition 10.

If

$\displaystyle\ell_{2}$ $\displaystyle\geqslant
e\cdot\frac{\ln\left(8rm^{2}\right)-\ln(1-p)-\ln(2r-1)}{\lambda
e\ln\left(2r-1\right)-3}\quad\text{or}$ $\displaystyle r$
$\displaystyle\geqslant\left(\frac{8m^{2}\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)}{1-p}\right)^{1/\lambda\ell_{2}}$

then we have $p\leqslant
p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)\leqslant
p_{\lambda}(r,\ell_{1},\ell_{2},m)$.

######  Proof 4.1.

We see that $p\leqslant p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)$ if
$1-p\geqslant 1-p^{\leqslant}_{\lambda}(r,\ell_{1},\ell_{2},m)$. Then, from
Theorem 1, we have the sufficient condition

$1-p\geqslant 8m^{2}r\ell_{2}^{3}(2r-1)^{-\lambda\ell_{2}-1}.$

Then, taking the logarithm of both sides, we find that

$\ln(1-p)\geqslant\ln(8m^{2}r)+3\ln(\ell_{2})+(-\lambda\ell_{2}-1)\ln(2r-1).$

Thus, after rearranging and using the bound
$\ln(\ell_{2})\leqslant\ell_{2}/e$, we obtain

$\ell_{2}\geqslant
e\cdot\frac{\ln\left(8rm^{2}\right)-\ln(1-p)-\ln(2r-1)}{\lambda
e\ln\left(2r-1\right)-3}$

as a sufficient condition.

Again, from the bound in Theorem 1, we see that, since $2r-1\geqslant r$, we
obtain the sufficient bound

$1-p\geqslant 8m^{2}\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)r^{-\lambda\ell_{2}}.$

Then, after rearrangement, we obtain the bound

$r\geqslant\left(\frac{8m^{2}\ell_{2}^{2}(\ell_{2}-\ell_{1}+1)}{1-p}\right)^{1/\lambda\ell_{2}}$

as required.

######  Proposition 11.

If $m$ is such that

$1\leqslant m\leqslant\sqrt{\frac{(1-p)(2r-1)^{1+\lambda\ell}}{8r\ell^{2}}},$

then $p\leqslant p^{\leqslant}_{\lambda}(r,\ell,\ell,m)\leqslant
p_{\lambda}(r,\ell,\ell,m)$.

######  Proof 4.2.

From Theorem 1 may derive the sufficient condition

$1-p\geqslant 8m^{2}r\ell^{2}(2r-1)^{-\lambda\ell-1}.$

Then, after some rearrangement, we obtain the desired result.

From Proposition 8, we may derive the following bound on $m$.

######  Proposition 12.

If we have $p^{\geqslant}_{\lambda}(r,\ell,m)\geqslant p>0$, then

$m\leqslant
1+2\sqrt{\frac{\ln(1/p)(2r-1)^{1+\lceil\lambda\ell\rceil}}{2\ell(r-1)}}.$

In particular, the above bound holds if
$p^{\geqslant}_{\lambda}(r,\ell,m)\geqslant
p_{\lambda}(r,\ell,\ell,m)\geqslant p>0$.

######  Proof 4.3.

Firstly, suppose that $\operatorname{FR}(r,\lceil\lambda\ell\rceil)<2m\ell$;
then $p_{\lambda}(r,\ell,\ell,m)=0$ by Proposition 8 and thus our statement
holds as there would be no such $p$. In the remainder of this proof, we
suppose that $\operatorname{FR}(r,\lceil\lambda\ell\rceil)\geqslant 2m\ell$
and thus we have the bound in Proposition 8.

Then, from Corollary 9, we have

$p_{\lambda}(r,\ell,\ell,m)\leqslant\frac{1}{\operatorname{CR}(r,\ell)^{m^{\prime}}}\left(\operatorname{CR}(r,\ell)-4m^{\prime}\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}\right)^{m^{\prime}}$

where $m^{\prime}=\lfloor m/2\rfloor$. After some rearrangement, if
$p_{\lambda}(r,\ell,\ell,m)\geqslant p$, then

$\left(1-m^{\prime}\cdot\frac{4\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}}{\operatorname{CR}(r,\ell)}\right)^{m^{\prime}}\geqslant
p.$

Taking the logarithm of both sides we obtain

$m^{\prime}\cdot\ln\left(1-m^{\prime}\cdot\frac{4\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}}{\operatorname{CR}(r,\ell)}\right)\geqslant\ln(p).$

We can thus apply the Taylor series for $\ln(1-x)$, to obtain

$-m^{\prime}\sum_{i=1}^{\infty}\frac{1}{i}\cdot\left(m^{\prime}\cdot\frac{4\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}}{\operatorname{CR}(r,\ell)}\right)^{i}\geqslant\ln(p)$

as a necessary condition.

Hence, we can now see that $m^{\prime}$ must satisfy

$\left(m^{\prime}\right)^{2}\cdot\frac{4\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}}{\operatorname{CR}(r,\ell)}\leqslant\ln(1/p),$

and thus,

$m^{\prime}\leqslant\sqrt{\frac{\operatorname{CR}(r,\ell)\ln(1/p)}{4\ell(r-1)(2r-1)^{\ell-\lceil\lambda\ell\rceil-1}}}.$

Thus, by taking the upper bound $\operatorname{CR}(r,\ell)\leqslant
2(2r-1)^{\ell}$, we see that

$m^{\prime}\leqslant\sqrt{\frac{(2r-1)^{1+\lceil\lambda\ell\rceil}\ln(1/p)}{2\ell(r-1)}}.$

Since $m\leqslant 1+2m^{\prime}$, we have our result.

From Proposition 12, we may prove Theorem 2 as follows.

######  Proof 4.4 (Proof of Theorem 2).

From Proposition 8 we have $p^{\geqslant}_{\lambda}(r,\ell,m)\geqslant
p_{\lambda}(r,\ell,\ell,m)$. Moreover, after some rearrangement of the bound
obtained in Proposition 12, we find that

$\ln(1/p^{\geqslant}_{\lambda}(r,\ell,m))\geqslant\frac{1}{4}{(m-1)}^{2}\ell\frac{2r-2}{{(2r-1)}^{1-\lceil\lambda\ell\rceil}}.$

Then, since $2(2r-2)\geqslant 2r-1$ for each $r\geqslant 2$, we see that,

$\ln(1/p^{\geqslant}_{\lambda}(r,\ell,m))\geqslant\frac{1}{8}{(m-1)}^{2}\ell{(2r-1)}^{-\lceil\lambda\ell\rceil}$

for each $m\geqslant 1$ and $r\geqslant 2$.

###  4.1. Optimal choice of relator length

In a way, an optimal choice of length $\ell$ is one for which there exists an
integer $k\in\mathbb{N}$ such that $\ell=\lceil k/\lambda\rceil+1$. For
example, if $\lambda=1/6$, then we would be interested in lengths of the form
$\ell=6\ell_{1}+1$ as they have the property that

$p_{\lambda}(r,\,6\ell_{1}+1,\,6\ell_{1}+1,\,m)\geqslant
p_{\lambda}(r,\,6\ell_{1}+1+\ell_{2},\,6\ell_{1}+1+\ell_{2},\,m)$

for each $\ell_{2}$ with $0\leqslant\ell_{2}<6$. This property, as we see
below, follows from the definition of small cancellation.

Notice that the length $\ell\geqslant 1$ can be uniquely written as
$\ell=\ell_{1}/\lambda+\ell_{2}$ where $\ell_{1}\in\mathbb{N}$ and
$\ell_{2}\in\mathbb{R}$ with $0<\ell_{2}\leqslant 1/\lambda$. Then, we see
that a presentation, $\mathcal{P}=\left\langle X\mid R\right\rangle$, with
length $\ell$ relators fails property $\operatorname{C}^{\prime}(\lambda)$ if
and only if either

  1. (1)

there are two words $u,v\in W$ and offsets $d_{1},d_{2}$, with each
$0\leqslant d_{i}<\ell$, such that $u_{\ll d_{1}}$ and $v_{\ll d_{2}}$ share a
length $\lceil\lambda\ell\rceil=\ell_{1}+1$ prefix; or

  2. (2)

there is a word $w\in W$ and two offsets $d_{1},d_{2}$, with $0\leqslant
d_{1}<d_{2}<\ell$, such that $w_{\ll d_{1}}$ and $w_{\ll d_{2}}$ share a
length $\lceil\lambda\ell\rceil=\ell_{1}+1$ prefix.

Thus, we see that increasing $\ell_{2}$ within the range $0<\ell_{2}\leqslant
1/\lambda$ can only increase the probability of $W$ containing such a choice
of words and thus decrease the probability of small cancellation. Hence, with
$\ell$ in the range $\lceil
k/\lambda\rceil+1\leqslant\ell<\lceil(k+1)/\lambda\rceil+1$, the probability,
$p_{\lambda}(r,\ell,\ell,m)$, of small cancellation is maximal at $\ell=\lceil
k/\lambda\rceil+1$.

##  Appendix A Experimental Results

In this appendix we compare our lower and upper bounds, from Section 3.1 and
Proposition 8 respectively, with estimates of $p_{\lambda}(r,\ell,\ell,m)$
obtained from computational experiment. The code used to create this section
is provided at [3]. In particular, we present several heatplots which show how
our bounds on $p_{\lambda}(r,\ell,\ell,m)$ compare as we vary the values of
$r$, $\ell$ and $m$. Each data-point in each heatplot was obtained from a data
sample consisting of at least 35 000 randomly chosen presentations. Within
this appendix, unless otherwise specified, $\lambda=1/6$.

In Figure 1 we fix the number of generators, $r$, to 20, and compare the
probability of small cancellation, $p_{\lambda}(20,\ell,\ell,m)$, as we vary
the number of relators, $m$, and the length of such relators, $\ell$.
Counterintuitively, it appears that the probability of small cancellation is
not monotone non-decreasing with respect to the relator length $\ell$. In
fact, the probability appears to be decreasing within ranges of length
$6=1/\lambda$. A similar phenomenon appears again in Figure 2, in which the
number of relators, $m$, is fixed to $10$ and the probability
$p_{\lambda}(r,\ell,\ell,10)$ is compared as $r$ and $\ell$ are varied.
Moreover, we see that, if we instead set $\lambda=1/100$, as in Figure 3, then
we obtain the same pattern where the probability decreases within ranges of
size $100=1/\lambda$. The reason behind this pattern is explained in Section
4.1.

Finally, in Figure 4, we fix the relator length, $\ell$, to 20, and compare
the probabilities of small cancellation, $p_{\lambda}(r,20,20,m)$, as we vary
the number of generators, $r$, and relators, $m$.

(a) Lower bound from Section 3.1. (b) Upper bound from Proposition 8. (c)
Experimental approximation.

Figure 1. Heatmaps giving upper and lower bounds, and an experimental
approximation of $p_{\lambda}(20,\ell,\ell,m)$ as $\ell$ and $m$ are varied,
with $r$ fixed to be $20$.

(a) Lower bound from Section 3.1. (b) Upper bound from Proposition 8. (c)
Experimental approximation.

Figure 2. Heatmaps giving upper and lower bounds, and an experimental
approximation of $p_{\lambda}(r,\ell,\ell,10)$ as $\ell$ and $r$ are varied,
with $m$ fixed to be $10$.

(a) Lower bound from Section 3.1. (b) Upper bound from Proposition 8. (c)
Experimental approximation.

Figure 3. Heatmaps giving upper and lower bounds, and an experimental
approximation of $p_{1/100}(r,\ell,\ell,10)$ as $\ell$ and $r$ are varied,
with $m$ fixed to be $10$ and $\lambda=1/100$.

(a) Lower bound from Section 3.1. (b) Upper bound from Proposition 8. (c)
Experimental approximation.

Figure 4. Heatmaps giving upper and lower bounds, and an experimental
approximation of $p_{\lambda}(r,20,20,m)$ as $r$ and $m$ are varied, with
$\ell$ fixed to be $20$.

## Acknowledgements

A large proportion of the theoretical work presented in this paper was a part
of the second named author’s master thesis at Charles University in Prague,
Czech Republic, which was supervised by Pavel Příhoda. The first named author
acknowledges support from an Australian Government Research Training Program
Scholarship. The authors also acknowledge support from Australian Research
Council grant DP160100486.

## References

  * [1] G. N. Arzhantseva and A. Yu. Olshanskiĭ.  Generality of the class of groups in which subgroups with a lesser number of generators are free.  Mat. Zametki, 59(4):489–496, 638, 1996.
  * [2] Calum J. Ashcroft and Colva M. Roney-Dougal.  On random presentations with fixed relator length.  Communications in Algebra, 0(0):1–15, 2020.
  * [3] Alex Bishop.  Small cancellation.  https://github.com/alexbishop/small-cancellation, 2019.
  * [4] Bren Cavallo and Delaram Kahrobaei.  Secret sharing using non-commutative groups and the shortlex order.  In Algorithmic problems of group theory, their complexity, and applications to cryptography, volume 633 of Contemp. Math., pages 1–8. Amer. Math. Soc., Providence, RI, 2015.
  * [5] Martin Greendlinger.  On Dehn’s algorithms for the conjugacy and word problems, with applications.  Comm. Pure Appl. Math., 13:641–677, 1960.
  * [6] M. Gromov.  Asymptotic invariants of infinite groups.  In Geometric group theory, Vol. 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1–295. Cambridge Univ. Press, Cambridge, 1993.
  * [7] Maggie Habeeb, Delaram Kahrobaei, and Vladimir Shpilrain.  A secret sharing scheme based on group presentations and the word problem.  In Computational and combinatorial group theory and cryptography, volume 582 of Contemp. Math., pages 143–150. Amer. Math. Soc., Providence, RI, 2012.
  * [8] Roger C. Lyndon and Paul E. Schupp.  Combinatorial group theory.  Classics in Mathematics. Springer-Verlag, Berlin, 2001.  Reprint of the 1977 edition.
  * [9] Yann Ollivier.  A January 2005 invitation to random groups, volume 10 of Ensaios Matemáticos [Mathematical Surveys].  Sociedade Brasileira de Matemática, Rio de Janeiro, 2005.
  * [10] Igor Rivin.  Growth in free groups (and other stories)—twelve years later.  Illinois J. Math., 54(1):327–370, 2010.
  * [11] Vladimir Shpilrain and Gabriel Zapata.  Combinatorial group theory and public key cryptography.  Appl. Algebra Engrg. Comm. Comput., 17(3-4):291–302, 2006.
  * [12] Vladimir Shpilrain and Gabriel Zapata.  Using decision problems in public key cryptography.  Groups Complex. Cryptol., 1(1):33–49, 2009.