\section{Introduction}

\emph{Hierarchical models} are toy models of statistical mechanics that exhibit similar phenomena to their Euclidean counterparts but which are much easier to study thanks to their exact recursive nesting structure.

First introduced by Dyson \cite{dyson1969existence} in 1969, there is now a huge literature on hierarchical models within mathematical and theoretical physics, with Dyson's original paper having over 1000 citations; we refer the reader to \cite{dragovich2017p,dragovich2009p} for broad overviews of the use of hierarchical models in physics and \cite{bleher1987critical,MR3969983} for surveys of the rigorous analysis of critical phenomena in hierarchical models. Beyond their use in physics, hierarchical models have also been used to study epidemic spread \cite{ouboter2016stochastic} and population dynamics \cite{sawyer1983isolation}, where they may arguably be more realistic than either Euclidean or mean-field models.

 In this paper we study the low-temperature behaviour of hierarchical models \emph{at and below their lower-critical dimensions}, where phase transitions do not occur, a subject that has received relatively little prior treatment in the literature. We will see that the model displays particularly interesting behaviour at the lower-critical dimension itself, where it enjoys certain exact self-similarity properties.
  We focus on hierarchical \emph{percolation}, with our results immediately implying analogous results for various other models including the Ising and Potts models by standard stochastic domination properties.

Let us now define the model.
 Given a dimension $d \in \mathbb N$ and a side-length $L \in \mathbb N$ with $L \geq 2$, the hierarchical lattice $\mathbb H_L^d$ is the group $\bigoplus_{i=1}^{\infty} (\mathbb Z / L \mathbb Z)^d$ equipped with the ultrametric given by $\norm{x-y} := L^{\max \{i :\;  x_i \not= y_i \} }$ for all distinct $x,y \in \mathbb H_L^d$. (This metric is \emph{not} a norm, but we use this notation to emphasise its analogy with the metrics on $\mathbb Z^d$ induced by norms on $\mathbb R^d$.)

The ultrametric balls of radius $L^n\mathbbm{1}(n>0)$ in this space are referred to as \textbf{$n$-blocks}, with the $n$-block containing the origin denoted by $\Lambda_n$. As a metric space, $\mathbb H^d_L$ can also be constructed recursively by taking
$\Lambda_0 = \{0\}$ and, for each $n\geq 0$, taking $\Lambda_{n+1}$ to be the union of $L^d$  disjoint copies of $\Lambda_n$ with distances defined by
$\|x-y\| = L^{n+1}$
 for each pair $x, y \in \Lambda_{n+1}$ belonging to distinct copies of $\Lambda_n$.
Given parameters $\alpha, \beta > 0$, we form a random graph $\omega$ with vertex set $\mathbb H_L^d$ by independently including each possible edge $xy:=\{x,y \}$ with probability $1-\exp ( -\beta \norm{ x-y }^{-d-\alpha} )$. We call this model \textbf{long-range percolation on the hierarchical lattice}. We denote its law by $\mathbb P_{\beta}$, omitting $\alpha$ because we typically think of it  as being fixed while $\beta$ varies.

We are primarily interested in the geometry of the connected components of the random graph $\omega$, called \emph{clusters}. We write $K_x=K_x(\omega)$ for the cluster containing the element $x$, $x \leftrightarrow y$ to mean that $K_x = K_y$, and $x \leftrightarrow \infty$ to mean that $K_x$ is infinite. (Note that all these notions depend on the random graph $\omega$, but we suppress this from our notation when doing so does not cause confusion.) It is known that the \textbf{critical parameter}
$\beta_c := \sup \{ \beta : \mathbb P_{\beta} ( o \leftrightarrow \infty ) = 0 \}$ is finite if and only if $d>\alpha$ \cite{dyson1969existence,dawson2013percolation,koval2012long}, so that $d=\alpha$ may be thought of as the \emph{lower-critical dimension} of the model. Since many of the most interesting questions about the model concern its behaviour at and near $\beta=\beta_c$, previous works have naturally focused on the case $0<\alpha<d$, where there is now a fairly good understanding of the model's critical behaviour \cite{hutchcroft2021critical,hutchcroft2022critical,koval2012long}.

In this paper we instead study
 the case $\alpha \geq d$, in which $\beta_c=\infty$. Although the model does not have a phase transition in this regime, the dependence of the model on the parameter $\beta$ remains very interesting. This is particularly true in the marginal case $\alpha=d$, where the model enjoys a certain exact self-similarity property as explained in \cref{sec:renormalization}.  To study this dependence on $\beta$, we focus in particular on the rate of divergence of the \textbf{susceptibility} $\chi(\beta):= \mathbb E_{\beta} \abs{K_0}$
  of the model, i.e.\ the expected
   size of the cluster of the origin.

    The susceptibility $\chi(\beta)$ is finite if and only if $\beta<\beta_c$ by sharpness of the phase transition \cite{MR894398,1901.10363,duminil2015new}, so that $\chi(\beta)$ blows up for finite values of $\beta$ if and only if $\alpha<d$. As such, it is plausible that the marginal case $\alpha=d$, where the model ``almost'' has a phase transition, might be characterized by $\chi(\beta)$ growing much faster as $\beta\to \infty$ when $\alpha=d$ than when $\alpha>d$.
Indeed, the rapid growth of the susceptibility in the case $\alpha=d$
was previously studied by
 Georgakopoulos and Haslegrave\footnote{Interestingly, these authors had their own motivations to study a model equivalent to hierarchical percolation with $d=\alpha$, and were not aware of the previous literature on hierarchical models in physics.} \cite{georgakopoulos2020percolation}, who

   proved that $e^{\Omega(\beta)} \leq \chi(\beta) \leq e^{e^{O(\beta)}}$ and suggested, based on numerical simulations, that the true growth might be of the form $e^{\Theta(\beta \log \beta)}$.

    Our main result states, surprisingly, that the susceptibility is in fact double-exponential in $\beta$ when $\alpha =d$, completely resolving \cite[Problem 8.1]{georgakopoulos2020percolation}. We also show that it grows as a power of $\beta$ when $\alpha>d$, so that there is indeed a striking quantitative distinction between the two cases.

\begin{thm} \label{thm:main}
Let $d \geq 1$ and $L \geq 2$ be integers, let $\alpha \geq d$, and consider long-range percolation on the hierarchical lattice $\mathbb H^d_L$ in which each two vertices are connected by an edge with probability $1-\exp(-\beta\|x-y\|^{-d-\alpha})$. Then
\[
    \chi(\beta) =
    \begin{cases}
        e^{e^{ \Theta(\beta) }} \quad &\text{if $\alpha = d$}\\
                \beta^{\frac{d}{\alpha - d } - o(1)} \quad &\text{if $\alpha > d$}
    \end{cases}

\]
as $\beta \to \infty$.
\end{thm}

\begin{remark}
The same self-similarity property that makes the $\alpha=d$ case particularly interesting from our perspective also leads the model's Euclidean ($Z_t^{(1)}^d$) counterpart to have a rich and fractal-like large-scale geometry in the supercritical regime, with fractal dimension depending on the parameter~$\beta$ \cite{ding2013distances,baumler2022distances,baumler2022behavior}. The Euclidean model with $\alpha=d=1$ is also very interesting as an example of a percolation model undergoing a \emph{discontinuous} phase transition \cite{aizenman1988discontinuity,duminil2020long}, meaning that the close analogy between long-range percolation on the hierarchical and one-dimensional Euclidean lattices that holds for $\alpha<d$ \cite{MR4504407,baumler2022isoperimetric} breaks down rather badly at the point $\alpha=d$.
\end{remark}

\medskip

\noindent \textbf{Consequences for other models.}
\cref{thm:main} immediately implies that analogous estimates hold for a large number of related models that are stochastically dominated above and below by Bernoulli percolation of appropriate parameters.
For example, the random cluster model on $\mathbb H^d_L$ with parameter $q\geq 1$, which in finite volume is defined by weighting the law of the Bernoulli percolation model we consider by a factor proportional to $q^{\#\text{clusters}}$, is always stochastically dominated by Bernoulli-$\beta$ percolation and stochastically dominates Bernoulli-$(\beta/q)$ percolation. It follows in particular that if $\chi(q,\beta)$ is the susceptibility (i.e., the expected size of the cluster of the origin) of the model with $\alpha=d$, then there exist positive constants $c$, $C$, and $\beta_0$ such that
\begin{equation}
e^{e^{\frac{c}{q} \beta}} \leq \chi(q,\beta) \leq e^{e^{C \beta}}
\end{equation}
for every $q\geq 1$ and $\beta\geq \beta_0$. (Note that for $\alpha\geq d$ the susceptibility can be defined without reference to boundary conditions since there is no phase transition and the Gibbs measure is always unique.) Using the Edwards-Sokal \cite{edwards1988generalization} coupling between the random cluster model and the Potts model when $q\geq 2$ is an integer, which identifies the susceptibilities of the two models, it follows that the same susceptibility estimates hold for the hierarchical Potts with interaction $J(x,y)=\|x-y\|^{-d-\alpha}$ for $\alpha =d$, and in particular to

   Dyson's  hierarchical Ising model \cite{dyson1969existence} on $\mathbb H^1_2$ with interaction $|x-y|^{-2}$. Detailed background on these models and their relation to percolation can be found in \cite{MR2243761}. This striking double-exponential growth does not appear to have been discovered previously in any of these  models, even at a heuristic level.

\medskip

\noindent \textbf{About the proof.}  The proofs of the two cases $\alpha=d$ and $\alpha>d$ are very different, with the case $\alpha=d$ being much more delicate due to the model's resulting special self-similarity properties. The remainder of the paper is summarized as follows:
\begin{itemize}
\item In \cref{sec:renormalization} we introduce the renormalization framework that we use and give a very simple proof of the upper bound $\chi(\beta)=O(\beta^{d/(\alpha-d)})$ in the case $\alpha>d$. For the case $\alpha=d$, the most important idea introduced in this section is that by working with a certain mixed site-and-bond model, we can control the behaviour of percolation on large scales in terms of percolation on smaller scales, but with a change of parameters that depends on the size of the largest clusters on the smaller scale.

\item In \cref{sec:alpha>d_lower} we complete the proof of the $\alpha>d$ case of \cref{thm:main} by proving an appropriate lower bound on $\chi(\beta)$ in this case. The proof of the lower bound is based on a modification of an induction-on-scales argument that the second author introduced in \cite{hutchcroft2021critical} to study the $\alpha < d$ regime; a more quantitative implementation of this argument is required to get a non-vacuous output in the case $\alpha>d$.

 \item In \cref{sec:alpha=d} we prove the $\alpha=d$ case of \cref{thm:main}. The proof of the lower bound, which is the primary new contribution of our paper, relies on a technique we call \emph{sprinkled renormalisation}: We use the renormalization technology introduced in \cref{sec:renormalization} to do an induction-on-scales in which we slightly increase the parameter $\beta$ each time we renormalize, taking care to not do this so many times that we increase $\beta$ to more than twice its original value. One interesting feature of this proof is that we \emph{double} the scale at each step of the induction, so that the side length of the block we consider grows doubly-exponentially in the number of steps taken; this turns out to make things work particularly nicely thanks to the self-similarity of the model. Finally, to keep the paper self-contained, in \cref{sec:alpha=d_upper} we give a new proof of the double-exponential upper bound of \cite{georgakopoulos2020percolation} based on the notion of \emph{correlation length} for hierarchical models introduced in \cite{MR4462652}.

\end{itemize}

\section{The basic renormalisation framework}
\label{sec:renormalization}
In this section, we develop notation to describe how to control the percolation process at a given scale by the process at a smaller scale with a different effective parameter. Along the way we will deduce the upper bounds of \cref{thm:main} in the case $\alpha>d$.

\medskip

\textbf{Blocks and their edges.}
Let $d \geq 1$ and $L \geq 2$ be integers, and let $\alpha > 0$ be a constant. For each integer $n \geq 0$ we refer to the ultrametric balls of radius $L^n \mathbbm{1}(n>0)$ in $\mathbb H^d_L$ as \textbf{$n$-blocks}. For each $x\in \mathbb H^d_L$ and $n\geq 0$ we write $\Lambda_n(x)$ for the $n$-block containing $x$ and write $\Lambda_n=\Lambda_n(0)$ for the $n$-block containing the origin. In other words, $\Lambda_n$ is the subset of $\mathbb H_L^d$
consisting of those $x$ with $x_i = 0$ for all $i > n$. We write $E_n(x)$ for the set of unordered pairs of distinct elements of $\Lambda_n(x)$, write $E=\bigcup_{n\geq 1} E_n$ for the set of unordered pairs of distinct elements of $\mathbb H^d_L$, and write $E_n=E_n(0)$.

 We also write $F_k=\bigcup_{x\in \mathbb H^d_L}E_k(x)$ for the set of all unordered pairs of distinct elements with distance at most $L^k$.

 \medskip

\textbf{Block renormalisation.}
 We define $\pi : \mathbb H_L^d \to \mathbb H_L^d$ to be the \emph{left-shift} map defined by $(x_1,x_2,\dots) \mapsto (x_2,x_3,\dots)$ and define $\Phi : \{ 0,1 \}^E \to \{ 0,1\}^E$ mapping $\omega \mapsto \Phi[\omega]$ by setting $\Phi[\omega](e) =1$ if and only if there exists $xy \in E$ such that $\pi(x)\pi(y) = e$ and $\omega_{xy}=1$. This corresponds to zooming out by one scale, treating each copy of $\Lambda_1$ as a single vertex.
In particular, if $x,y\in \mathbb H^d_L$ are connected in a configuration $\omega \in \{0,1\}^E$ then we must also have that $\pi(x)$ and $\pi(y)$ are connected in $\Phi[\omega]$, since any open path connecting $x$ and $y$ is mapped to an open path connecting $\pi(x)$ to $\pi(y)$. (The converse does not always hold.)
 \cref{lem:zoom} states that the effect of the map $\Phi$ on long-range percolation is simply to adjust the parameter $\beta$. Notice that when $\alpha = d$ the model is self-similar in the sense that $\beta$ remains unchanged.

\begin{lem} \label{lem:zoom}
    For all $\beta > 0$, the pushfoward $\Phi_* \mathbb{P}_\beta$ is given by $\Phi_* \mathbb{P}_\beta = \mathbb{P}_{L^{d-\alpha} \beta}$. That is, if $\omega$ has law $\mathbb{P}_\beta$ then $\Phi[\omega]$ has law  $\mathbb{P}_{L^{d-\alpha}\beta}$.
\end{lem}

\begin{proof}
Independence is immediate, so it suffices to check that $\mathbb{P}_{L^{d-\alpha} \beta}$ has the correct marginals. Let $xy \in E$ be arbitrary. There are $L^{2d}$ edges $x'y' \in E$ with $\pi(x')\pi(y') = xy$, and each has $\den{x'-y'} = L \den{x-y}$. The probability that $\omega_{xy} = 0$ under $\Phi_* \mathbb{P}_\beta$ is the probability that $\omega_{x'y'} = 0$ for every one of these edges $x'y'$ under $\mathbb{P}_\beta$, so that
\[
    \Phi_* \mathbb{P}_\beta \bra{ \omega_{xy} = 0 } = \sqbra{e^{-\beta \bra{L \den{ x-y } }^{ - d - \alpha} }}^{L^{2d}} = \mathbb{P}_{ L^{d-\alpha}\beta } \bra{ \omega_{xy} = 0 }
\]
as required.
\end{proof}

This observation already lets us prove the upper bound of \cref{thm:main} in the case $\alpha>d$.

\begin{lem} \label{lem:alpha>d_ub}
If $\alpha>d$ then there exists a constant $C=C(d,L,\alpha)< \infty$ such that

    $\chi(\beta) \leq C \beta^{ \frac{d}{\alpha -d} }$ for every $\beta \geq 1$.
\end{lem}

\begin{proof}
 Recall that $K_0(\omega)$ denotes the cluster of the origin in the configuration $\omega\in \{0,1\}^E$. For each configuration $\omega \in \{ 0,1\}^E$ we have that
\[
|K_0(\omega)| = |\{x\in \mathbb H^d_L: 0 \leftrightarrow x\}| \leq |\{x\in \mathbb H^d_L: \pi(0) \leftrightarrow \pi(x)\}| = L^d |K_0(\Phi[\omega])|,
\]
 where both sides may be infinite. Taking expectations and applying \cref{lem:zoom}, we deduce that
 \[\chi(\beta) \leq L^d \cdot \chi\bigl(L^{-(\alpha-d)} \beta\bigr)\] for every $\beta > 0$ and hence by induction that
\[\chi(\beta) \leq L^{dn} \cdot \chi\bigl( L^{ -(\alpha-d)n } \beta \bigr)\] for every $\beta>0$ and $n \geq 0$.
Taking $n=\lceil \frac{1}{\alpha-d}\log_L \beta\rceil $ to be minimal such that $L^{-(d-\alpha) n}\beta \leq 1$ and using that $\chi(\beta)$ is an increasing function of $\beta$, we deduce that
\[
    \chi(\beta) \leq L^{d \lceil \frac{1}{\alpha-d}\log_L \beta \rceil } \cdot \chi(1) \leq L^d \chi(1) \beta^{\frac{d}{\alpha-d}}
\]
for every $\beta \geq 1$. The claim follows with $C=L^d \chi(1)$ since $\chi(\beta) < \infty$ for every $\beta<\beta_c=\infty$.
\end{proof}

We next discuss a variation on this renormalization procedure that can be used to prove lower bounds.

\medskip

\textbf{Renormalisation with a mixed site-bond model.}
If we zoom out by $k$ scales by iterating the map $\Phi$ for $k$ steps,
we lose all information about the configuration of edges
 in $F_k := \bigcup_{x\in \mathbb H^d_L}E_k(x)$, which join vertices at distance at most $L^k$. As we saw in \cref{lem:alpha>d_ub}, this is not necessarily a problem when proving upper bounds on our original model, where it may suffice to consider worst-case estimates in which every edge of $F_k$ is open.

  To establish non-trivial lower bounds, however, we will require more information about the state of the edges in $F_k$.
Rather than keep track of \emph{all} relevant information about these small-scale edges, we will instead define an appropriate notion of what it means for a block to be `good', and keep track only of which blocks are good when re-scaling.

   Since the goodness of different $k$-blocks will be independent of each other and independent of the status of edges not belonging to $F_k$, this naturally leads us to consider a \emph{mixed} site-bond percolation model.

   For each $p \in [0,1]$, let $\mathbb Q_p$ be the law of the random subset $\eta$ of $\mathbb H_L^d$ obtained by independently including each element with probability $p$. Given $p \in [0,1]$ and $\beta > 0$, let $\mathbb{P}_{\beta,p}$ be the law of a random subgraph of $(\mathbb H_L^d, E)$, encoded as an element of $\Omega=\{0,1\}^{\mathbb H_L^d} \times \{0,1\}^E$ formed as follows: independently sample $\eta \sim \mathbb Q_p$ and $\omega \sim \mathbb{P}_\beta$, and then take the graph with vertex set $\{x : \eta (x) = 1\}$ and edge set $\{ xy : \omega_{xy} = \eta_x = \eta_y =1 \}$. As usual, we will abuse notation to think of $\omega$ and $\eta$ equivalently as the sets $\{e:\omega(e)=1\}$ and $\{x:\eta(x)=1\}$. Given a set $A\subseteq \mathbb H^d_L$, we refer to the connected  components of the subgraph of this graph induced by $A\cap \eta$ as \textbf{$(\eta,\omega)$-clusters in $A$} and say that two vertices $x,y\in A$ are \textbf{$(\eta,\omega)$-connected} in $A$ if they are in the same $(\eta,\omega)$-cluster in $A$. That is, two points $x,y\in A$ are $(\eta,\omega)$-connected in $A$ if there exists a path connecting $x$ to  $y$ all of whose vertices belong to $A\cap \eta$ and all  of  whose edges belong to $\omega$.

We next introduce the notation for zooming out by $k$ scales while only retaining edges between \emph{large} clusters.
Fix an enumeration of $\mathbb H^d_L=\{x_1,x_2,\ldots\}$. Given $(\eta,\omega)\in \Omega$ and a finite set $A\subseteq \mathbb H^d_L$, we define
$K_\mathrm{max}(A)=K_\mathrm{max}(A;(\eta,\omega))$ to be an $(\eta,\omega)$ cluster in $A$ of maximal volume, where if there is more than one cluster of maximal volume we break ties using the fixed enumeration of $\mathbb H^d_L$ by taking the cluster containing a vertex of minimal label among the different maximal volume clusters. (By `volume' we just mean cardinality.) To lighten notation, we also write
\[
K^\mathrm{max}_n=K_\mathrm{max}(\Lambda_n;(\eta,\omega)) \qquad \text{ and } \qquad K^\mathrm{max}_n(z)=K_\mathrm{max}(\Lambda_n(z);(\eta,\omega))
\]
for each $n\geq 0$ and $z\in \mathbb H^d_L$ when the choice of $(\eta,\omega)$ is unambiguous.
For each $\lambda>0$ and $k\geq1$
we define a map $\Psi^{\lambda,k} : \Omega \to \Omega$ by $\Psi^{\lambda,k}(\eta,\omega)=(\eta',\omega')$ where
\[
\eta'_x=\mathbbm{1}\Bigl(x=\pi^k(z) \text{ for some $z$ with $|K^\mathrm{max}_k(z)|\geq \lambda |\Lambda_k|$}\Bigr)
\]
and
\begin{multline*}
\omega'_{xy}=\mathbbm{1}\Bigl(x=\pi^k(z),y=\pi^k(w) \text{ for some $z,w$ with $\omega_{zw}=1$, }  \text{$z\in K^\mathrm{max}_k(z)$, and $w\in K^\mathrm{max}_k(w)$}\Bigr).
\end{multline*}
This function has the following important property.

\begin{lem}
\label{lem:Psi_connectivity}
Let $(\eta,\omega) \in \Omega$, let $k\geq 1$ and let $\lambda>0$.
If $x,y\in \mathbb H^d_L$ and $n\geq 1$ are such that $x \in K^\mathrm{max}_k(x)$, $y \in K^\mathrm{max}_k(y)$, and $\pi^k(x)$ is $\Psi^{\lambda,k}(\eta,\omega)$-connected to $\pi^k(y)$ in $\Lambda_n$ then $x$ and $y$ are $(\eta,\omega)$-connected in $\Lambda_{n+k}$.
In particular,
\[\left|K_\mathrm{max}\left(\Lambda_{n+k};(\eta,\omega)\right)\right| \geq \lambda L^{dk}\left|K_\mathrm{max}\left(\Lambda_{n};\Psi^{\lambda,k}(\eta,\omega)\right)\right| \]
for every $n\geq 1$.
\end{lem}

\cref{lem:zoom+} describes how the effect of $\Psi$ on a mixed percolation process $\mathbb{P}_{\beta,p}$ can be bounded by the effect of adjusting the parameters $\beta$ and $p$.

\begin{lem} \label{lem:zoom+}
For each $p,\lambda \in [0,1]$, $\beta > 0$, and $k\geq 0$ let
\[p' := \mathbb{P}_{\beta,p}( |K^\mathrm{max}_k|\geq \lambda L^{dk}) \qquad \text{and} \qquad \beta' := \lambda^2 L^{k(d-\alpha)} \beta.\]
The law of the random graph with vertex set $\{x : \eta (x) = 1\}$ and edge set $\{ xy : \omega_{xy} = \eta_x = \eta_y =1 \}$ under the measure $\Psi_*^{\lambda,k} \mathbb{P}_{\beta,p}$ stochastically dominates the law of the same random graph under the measure $\mathbb{P}_{\beta',p'}$.
\end{lem}

 Notice that when $\alpha = d$, the parameter $\beta$ is simply replaced by $\beta':=\lambda^2 \beta$.

\begin{proof}
Sample $(\eta,\omega) \sim \mathbb{P}_{\beta,p}$ and set $ (\eta',\omega') := \Psi^{\lambda,k}(\eta,\omega)$. Notice that $\eta'$ is determined by $\eta$ and $\omega \cap F_k$. By construction of $\Psi$, the definition of $p'$, and transitivity, we have that $\eta' \sim \mathbb Q_{p'}$. Hence, it suffices to check that if we fix realisations of $\eta$ and $\omega \cap F_k$ and independently sample $\omega \cap {\{xy \in E \backslash F_k : \eta_x = \eta_y =1 \}}$ according to its law under $\mathbb{P}_\beta$, then the law of $\omega'$ stochastically dominates the law of the restriction of a sample of $\mathbb{P}_{\beta'}$ to the set of edges $xy$ with $\eta'_x = \eta'_y = 1$. Indeed, notice that the state of the edges in $\omega'$ are independent of each other and that, arguing as in the proof of \cref{lem:zoom}, for every edge $xy$ with $\eta'_x = \eta'_y = 1$, the probability that $\omega_{xy} = 0$ is
\[
    \prod_{\substack{x'\in \mathbb H^d_L :\\ \pi^{k}(x') = x} } \prod_{\substack{y'\in \mathbb H^d_L :\\ \pi^{k}(y') = y}} \mathbb{P}_\beta \bra{ \omega_{x'y'} = 0 } \geq \sqbra{e^{ -\beta \bra{ L^{k} \den{x-y}  }^{-d-\alpha}}}^{ (\lambda L^{dk})^2 } = \mathbb{P}_{\beta'}(\omega_{xy} = 0)

\]
as required.
\end{proof}

\section{Lower bounds in the case $\alpha>d$}
\label{sec:alpha>d_lower}

In this section we prove the lower bound of \cref{thm:main} in the case $\alpha>d$. The proof uses an induction on scales that adapts the ideas of \cite[Lemma 2.4]{hutchcroft2021critical} to the large $\alpha$ regime.
Compared to the treatment of \cite{hutchcroft2021critical}, our argument is both more quantitative (which is necessary to get a non-vacuous statement in the large $\alpha$ regime), and is made more streamlined by the use of the renormalization notation established in the previous subsection.

\medskip

  Our argument involves repeatedly zooming out by $k$ scales, where $k$ is a carefully chosen integer depending on $\beta$. More precisely, we pick $k=k(\beta) : = k_0 \vee \lfloor \sqrt{ \log \beta } \rfloor$ where $k_0\geq 1$ is an integer that is sufficiently large to guarantee that

\begin{equation} \label{eq:technical1}
    \mathbb Q_{\frac{1}{2}} \Big( \abs{ \{x \in \Lambda_{k} : \eta_x = 1 \} } \geq \frac{1}{3}L^{dk}  \Big) \geq 1 - \frac{1}{4}
\end{equation}
for every $k\geq k_0$; such a constant $k_0$ exists by the weak law of large numbers. We will zoom out exactly $\ell=\ell(\beta)$ times where $\ell\geq 1$ is the largest integer such that
\begin{equation} \label{eq:l_condition}
   L^{2dk} \exp \bra{ - \frac{\beta}{9^{\ell} L^{ (\alpha-d)\ell k }  } \cdot \frac{1}{L^{(d+\alpha)k}} } \leq \frac{1}{4}.
\end{equation}
If no such $\ell$ exists (which may be the case when $\beta$ is small) we set $\ell=0$.

\begin{lem} \label{lem:induction_alpha>d}
        $\mathbb{P}_\beta(\lvert K^\mathrm{max}_{rk}\rvert \geq 3^{-r}L^{drk}) \geq \frac{1}{2}$ for every $\beta \geq 1$ and $r \in \{ 0, 1 , \dots, \ell \}$.
\end{lem}

\begin{proof}
Fix $\beta \geq 1$. We proceed by induction on $r$. The result is trivial for $r = 0$. Assume that the result holds for some $r \in \{ 0, \dots, \ell-1 \}$. Letting $\mathbf{1}\in \{0,1\}^{\mathbb H^d_L}$ be the all-ones function, we have by \cref{lem:Psi_connectivity} that
\[

    \left|K_\mathrm{max}\left(\Lambda_{(r+1)k};(\mathbf{1},\omega)\right)\right| \geq 3^{-r} L^{drk}\left|K_\mathrm{max}\left(\Lambda_{k};\Psi^{3^{-r},rk}(\mathbf{1},\omega)\right)\right|
\]
for each $\omega \in \{0,1\}^E$ and hence that
\[\mathbb{P}_{\beta, 1}\left(\bigl|K^\mathrm{max}_{(r+1)k}\bigr| \geq 3^{-r-1}L^{d(r+1)k}\right) \geq \Psi_*^{3^{-r}, r k} \mathbb{P}_{\beta, 1}\left(\left|K^\mathrm{max}_{k}\right| \geq \frac{1}{3}L^{dk}\right). \]
Applying \cref{lem:zoom+} with $p := 1$, we deduce that
\begin{equation} \label{eq:apply_gamma}
    \mathbb{P}_\beta \bra{ \left|K^\mathrm{max}_{(r+1)k}\right| \geq 3^{-r-1} L^{d(r+1)k} } \geq \mathbb{P}_{\beta',p'} \bra{ \left|K^\mathrm{max}_{k}\right| \geq \frac{1}{3}L^{dk} },
\end{equation}
where
\[p' = \mathbb{P}_\beta \bra{ \left|K^\mathrm{max}_{(r+1)k}\right|  \geq 3^{-r}L^{drk} } \qquad \text{and} \qquad \beta' := \frac{\beta}{3^{2r} L ^{(\alpha-d)rk}}.\]
We have by the induction hypothesis that $p' \geq \frac{1}{2}$, so that
\begin{align}
\mathbb{P}_\beta(\lvert K^\mathrm{max}_{rk}\rvert \geq 3^{-r}L^{drk}) &\geq \mathbb{P}_{\beta',1/2} \bra{ \left|K^\mathrm{max}_{k}\right| \geq \frac{1}{3}L^{dk} }\nonumber\\
&\geq \mathbb Q_{1/2} \Big( \abs{ \{x \in \Lambda_{k} : \eta_x = 1 \} }\geq \frac{1}{3}L^{dk}  \Big)\cdot \mathbb{P}_{\beta'} \bra{ \omega_e = 1 \; \forall e \in E_k }.\label{eq:wasteful}
\end{align}
Our choice of $k$ ensures that $\mathbb Q_{1/2} \Big( \abs{ \{x \in \Lambda_{k} : \eta_x = 1 \} }\geq \frac{1}{3}L^{dk}  \Big) \geq \frac{3}{4}$, while we have by a union bound and our choice of $\ell$ that
\begin{align*}
    \mathbb{P}_{\beta'} \bra{ \omega_e = 1 \; \forall e \in E_k } &\geq 1 - \abs{E_k} \max_{e \in E_k} \mathbb{P}_{\beta'} \bra{ \omega_e = 0 }
    &\geq 1 - L^{2dk} \text{exp}{\bra{ - \frac{\beta}{3^{2r} L^{ (\alpha-d)rk }  } \cdot \frac{1}{L^{(d+\alpha)k}} }} \geq \frac{3}{4},
\end{align*}
so that
\[
\mathbb{P}_\beta\left(\lvert K^\mathrm{max}_{rk}\rvert \geq 3^{-r}L^{drk}\right) \geq \frac{9}{16}\geq \frac{1}{2}
\]
as claimed.

\end{proof}

The following proposition implies the lower bound of \cref{thm:main} in the case $\alpha>d$, and gives an explicit estimate on the $o(1)$ term appearing in that estimate.

\begin{prop} \label{prop:alpha>d_lb}
If $\alpha>d$ then there exists a constant $C=C(d,L,\alpha) < \infty$ such that
\[
    \chi(\beta) \geq \beta^{ \frac{d}{\alpha - d} - \frac{C}{ \sqrt{\log \beta}} }
\]
for every $\beta \geq 2$.
\end{prop}

\begin{proof}
Fix $\beta \geq 2$. We have by transitivity that

\[
  \chi(\beta) \geq \mathbb{E}_\beta\left[|K^\mathrm{max}_n| \mathbbm{1}(0\in |K^\mathrm{max}_n|) \right] = \frac{1}{|\Lambda_n|}\sum_{x\in \Lambda_n} \mathbb{E}_\beta\left[|K^\mathrm{max}_n| \mathbbm{1}(x\in |K^\mathrm{max}_n|) \right]  = L^{-dn}\mathbb{E}_\beta\left[|K^\mathrm{max}_n|^2 \right]

\]
for every $n\geq 1$, and hence by \cref{lem:induction_alpha>d} that
\begin{equation} \label{eq:chi_raw_alpha>d}
    \chi(\beta) \geq \frac{1}{2} \cdot \frac{L^{dk\ell}}{9^\ell}.
\end{equation}
To complete the proof, we use the definitions of $k$ and $\ell$ to compute that
\[
9^\ell L^{(\alpha-d)k\ell} \sim \frac{1}{2d \log L} \frac{k\beta}{L^{(d+\alpha)k}}= \beta \cdot \exp\left[-O(\sqrt{\log \beta})\right] \qquad \text{ as $\beta \to \infty$},
\]
where $\sim$ means that the ratio of the two sides converges to $1$ in the relevant limit,
so that
\[
\ell \sim \frac{1}{(\alpha -d) \log L} \frac{\log \beta}{k} \sim \frac{1}{(\alpha -d)\log L} \sqrt{\log \beta} \qquad \text{ as $\beta \to \infty$}
\]
and
\[
\frac{L^{dk\ell}}{9^\ell} = 9^{-\frac{\alpha}{\alpha-d} \ell}\left(9^\ell L^{(\alpha-d)k\ell}\right)^{\frac{d}{\alpha-d}} =\beta^{\frac{d}{\alpha-d}} \cdot \exp\left[-O(\sqrt{\log \beta})\right] \qquad \text{ as $\beta \to \infty$,}
\]
 where all implicit constants may depend on $d$, $\alpha$, and $L$. Substituting this estimate into \eqref{eq:chi_raw_alpha>d} implies the claim.
\end{proof}

\begin{remark}
It may seem that the estimate \eqref{eq:wasteful} is very wasteful: The Erd\mathbb{H}{o}s-R\'enyi random graph contains a giant cluster well before every edge is open, and it would suffice for the rest of the analysis to have $\beta' L^{-(d+\alpha)k} \gg L^{-dk}$ rather than $\beta' L^{-(d+\alpha)k} \gg k $ as we require. It turns out, however, that carrying the analysis through with this improvement (and with the resulting optimal choices of $k$ and $\ell$) merely leads to a better value of the constant $C$ in \cref{prop:alpha>d_lb}.
\end{remark}

\section{The case $\alpha=d$}
\label{sec:alpha=d}

In this section we prove the $\alpha=d$ case of \cref{thm:main}. We begin with the lower bound, which is the primary new result of the paper, before giving a short self-contained treatment of the upper bound (which recovers the results of \cite{georgakopoulos2020percolation}) in \cref{sec:alpha=d_upper}. The arguments of \cref{sec:alpha=d_lower} rely on the renormalization framework developed in the previous sections while those of \cref{sec:alpha=d_upper} use a separate argument, which draws in part on the techniques of \cite[Section 4]{MR4462652}.

\subsection{Lower bounds}

\label{sec:alpha=d_lower}

In this section we prove the lower bound of \cref{thm:main} in the case $\alpha=d$.

\begin{prop} \label{prop:alpha=d_lb}
If $\alpha=d$ then there exists $c=c(d,L) > 0$ such that
    $\chi(\beta) \geq e^{ e^{c \beta} }$
for every $\beta \geq 1$.
\end{prop}

 We will prove \cref{prop:alpha=d_lb} using a ``sprinkled renormalization'' argument, in which we slightly increase the parameter each time we zoom out. An interesting feature of the proof is that, rather than going up one scale at a time, we instead \emph{double} the scale at each induction step, so that the side-length of the block considered at the $i$th induction step is double-exponential in $i$. We will rely on two auxiliary lemmas, the first of which encapsulates the induction step.

\begin{lem}[Inductive estimate] \label{lem:alpha=d_induction}
If $\alpha =d$ then the implication
\[
    \left(\mathbb{P}_{\beta,p} \left(|K^\mathrm{max}_n|\geq (1-\varepsilon) \abs{\Lambda_n} \right) \geq p \right) \quad \implies \quad
    \left(\mathbb{P}_{(1+6\varepsilon)\beta,p} \left(|K^\mathrm{max}_{2n}|\geq (1-2\varepsilon) \abs{\Lambda_n} \right) \geq p \right)

\]
holds for every $p\in [0,1]$, $\beta \geq 1$, $0<\varepsilon\leq 1/2$, and $n\geq 1$.
\end{lem}

The next auxiliary lemma establishes the base case of the induction. This base case estimate is more delicate than one might expect, and we do \emph{not} take our base case to be $n=0$. Rather, for the induction to work, we need to find a base scale $n_0$ where the probability that $\abs{K^\mathrm{max}_n}$ is close to $\abs{\Lambda_n}=L^{dn}$ under $\mathbb{P}_{\beta,p}$ is at least $p$, where $p$ is a constant that is bounded away from zero. (NB: It is very important that the $p$ appearing as the parameter in $\mathbb{P}_{\beta,p}$ and the $p$ appearing as the lower bound on the probability of the relevant event are equal!) To address the increase in $\beta$ along the induction, we begin with a lower initial parameter $\frac{\beta}{2}$.

\begin{lem}[Base case] \label{lem:alpha=d_base}
If $\alpha=d$ then there exists a constant $\beta_* =\beta_*(d,L)< \infty$ such that if  we define
\[
\delta = \delta(\beta)=\exp\left[-L^{-9d}\beta\right] \qquad \text{ and } \qquad n_0=n_0(\beta)=  \left\lceil \frac{2 \beta }{L^{9d} d \log L} \right\rceil
\]
then
\[
    \mathbb{P}_{\frac{1}{2}\beta,1-\delta} \bra{ |K^\mathrm{max}_{n_0}| \geq ( 1 -2 \delta) L^{dn_0} } \geq 1 - \delta
\]
for every $\beta \geq \beta_*$.
\end{lem}

Before proving these lemmas, let us first see how they imply \cref{prop:alpha=d_lb}.

\begin{proof}[Proof of \cref{prop:alpha=d_lb}]
The idea is to repeatedly apply \cref{lem:alpha=d_induction} as many times as possible beginning with \cref{lem:alpha=d_base}.
 There are two constraints. First, the value of $\varepsilon$ will eventually increase beyond $\frac{1}{2}$, at which point the hypothesis of \cref{lem:alpha=d_induction} will no longer be met. Second, our parameter, which starts at $\frac{1}{2}\beta$, will eventually increase beyond $\beta$, at which point we can no longer bound $\mathbb{P}_{\beta,p}$ with the current estimate. A satisfactory lower bound on the number of times that we can iterate will be $\ell := \ell(\beta)=\lceil -\log_2 (100 \delta) \rceil$, which satisfies
\[
   \frac{1}{50} \leq 2^{\ell} \delta \leq \frac{1}{100}
\]
for every $\beta \geq 1$.
We may assume that the constant $\beta_*$ is sufficiently large that $\delta(\beta)\leq 1/2$ and $\ell(\beta)\geq 1$ for every $\beta \geq \beta_*$.
Fix $\beta \geq 2 \beta_*$, and for each $0\leq r \leq \ell(\beta)$ let
\[ \delta_r = 2^r \delta , \qquad n_r = 2^r n, \qquad  \text{ and } \qquad \beta_r= \exp\left[ 12 \delta_r \right]\frac{\beta}{2}, \]
so that $\beta/2\leq \beta_r \leq e^{0.12}\beta/2\leq \beta$ for every $0\leq r \leq \ell$ by choice of $\ell$.
We claim that
\begin{equation}
\label{eq:induction_claim}
    \mathbb{P}_{ \beta_r, 1 - \delta } \bra{ |K^\mathrm{max}_{n_r}| \geq (1 - 2\delta_r) L^{dn_r} } \geq 1- \delta
\end{equation}
for every $0\leq r \leq \ell$.
We proceed by induction on $r$. When $r = 0$, the result follows from \cref{lem:alpha=d_base} since $\beta_0 \geq \beta/2$. Assume that the result holds for some $r \in \{ 0,\dots,l-1 \}$.
Since $r \leq \ell$, the definition of $\ell$ guarantees that $\delta_r \leq \frac{1}{2}$ and hence by \cref{lem:alpha=d_induction} (applied with $p=1-\delta$ and $\varepsilon=2\delta_r$) that
\[
    \mathbb{P}_{  (1+12\delta_r )\beta_r , 1 - \delta } \bra{ |K^\mathrm{max}_{n_{r+1}}| \geq (1 - 4 \delta_{r}) L^{dn_{r+1}}  } \geq 1- \delta.
\]
We can therefore conclude the induction step by noting that $4 \delta_{r} = 2\delta_{r+1}$ and

\[
   (1+12\delta_r) \beta_r \ \leq e^{  12 \delta_{r} } \beta_r  =\exp[24 \delta_r] \frac{\beta}{2} = \beta_{r+1} .

\]

It remains to deduce the claimed lower bound on $\chi(\beta)$ from \eqref{eq:induction_claim}. As in the proof of \cref{prop:alpha>d_lb}, it follows from \eqref{eq:induction_claim} and transitivity that
\[
\chi(\beta) \geq L^{-dn_\ell} \mathop{\mathbb E}_\beta \left[|K^\mathrm{max}_{n_\ell}|^2\right] \geq (1-\delta)(1-2\delta_\ell)^2 L^{dn_\ell} \geq \frac{1}{8} L^{dn_\ell}
\]
for every $\beta \geq 2 \beta_*$. The claim follows since
\[
n_\ell =2^\ell n_0 =\Theta\left( e^{L^{-9d}\beta} \beta \right) = e^{\Theta(\beta)}
\]
as  $\beta \to \infty$ by definition of $\ell$ and $n_0$. \qedhere

\end{proof}

We now prove the two auxiliary lemmas, \cref{lem:alpha=d_induction,lem:alpha=d_base}. We begin with the inductive estimate \cref{lem:alpha=d_induction}, which is a simple consequence of \cref{lem:Psi_connectivity,lem:zoom+}.

\begin{proof}[Proof of \cref{lem:alpha=d_induction}]
We may apply \cref{lem:Psi_connectivity} as in the proof of \cref{lem:induction_alpha>d} to obtain that
\[

    \left|K_\mathrm{max}\left(\Lambda_{2n};(\eta,\omega)\right)\right| \geq (1-\varepsilon) L^{dn} \left|K_\mathrm{max}\left(\Lambda_{n};\Psi^{1-\varepsilon,n}(\eta,\omega)\right)\right|
\]
for each $(\eta,\omega) \in \Omega$ and hence that
\[\mathbb{P}_{(1+6\varepsilon)\beta, p}\left(\bigl|K^\mathrm{max}_{2n}\bigr| \geq (1-\varepsilon)^2 L^{2dn}\right) \geq \Psi_*^{1-\varepsilon, n} \mathbb{P}_{(1+6\varepsilon)\beta, p}\left(\left|K^\mathrm{max}_{n}\right| \geq (1-\varepsilon)L^{dn}\right). \]
Now, for $0\leq \varepsilon \leq 1/2$ we have by calculus that $(1-\varepsilon)^2(1+6\varepsilon)\geq 1$ and $(1-\varepsilon)^2 \geq 1-2\varepsilon$,
 and applying \cref{lem:zoom+} (with $k=n$ and $\lambda = 1-\varepsilon$) yields that

\begin{align} \nonumber
    \mathbb{P}_{ (1+6\varepsilon)\beta,p} \bra{ |K^\mathrm{max}_{2n}| \geq (1-2\varepsilon) L^{2dn} } &\geq \mathbb{P}_{(1-\varepsilon)^2(1+6\varepsilon)\beta,p'} \bra{ |K^\mathrm{max}_n| \geq (1-\varepsilon) L^{dn} }\\
    &\geq\mathbb{P}_{\beta,p'} \bra{ |K^\mathrm{max}_n| \geq (1-\varepsilon) L^{dn} }
     \label{eq:alpha=d_key_lemma_second_bound}
\end{align}
 where
 \[p':= \mathbb{P}_{(1+6\varepsilon)\beta,p} \bra{ |K^\mathrm{max}_n| \geq (1-\varepsilon) L^{dn}} \geq \mathbb{P}_{\beta,p} \bra{ |K^\mathrm{max}_n| \geq (1-\varepsilon) L^{dn}}.\]
 If $\mathbb{P}_{\beta,p} \left(|K^\mathrm{max}_n|\geq (1-\varepsilon) \abs{\Lambda_n} \right) \geq p$ then $p'\geq p$ and the claim follows immediately from \cref{eq:alpha=d_key_lemma_second_bound}.
\end{proof}

It remains finally to prove \cref{lem:alpha=d_base}.

\begin{proof}[Proof of \cref{lem:alpha=d_base}]
Fix $\beta \geq 1$. Consider a mixed configuration $(\eta,\omega) \in \Omega$. As usual, we will abuse notation to think of $\eta$ and $\omega$ as subsets of $\mathbb H^d_L$ and $E$ when appropriate and recall that $F_k :=\bigcup_{z \in \mathbb{H}_L^d}E_k(z)$ is the set of all unordered pairs of distinct vertices of distance at most $L^k$.

  Consider the configuration $(\eta',\omega') := \Psi^{L^{-2d},2}(\eta,\omega)$, which satisfies
\[
\eta'_x=\mathbbm{1}\Bigl(x=\pi^2(z) \text{ for some $z$ with $|K^\mathrm{max}_2(z)|\geq 1$}\Bigr)
=
\mathbbm{1}\Bigl(x=\pi^2(z) \text{ for some $z$ with $\eta \cap \Lambda_2(z) \neq \emptyset$}\Bigr).
\]
   In order for the inequality $\abs{K^\mathrm{max}_{n_0}} \geq ( 1 -2 \delta) L^{dn_0}$ to hold, it suffices that the following four conditions all hold:
\begin{enumerate}
    \item $|\eta \cap \Lambda_{n_0}|\geq (1-2\delta) L^{dn_0}$;

    \item $\omega_{xy} = 1$ for all pairs of distinct vertices $x,y \in \eta \cap \Lambda_{n_0}$ with $\|x-y\|\leq L^{2}$;
    \item $\Lambda_{n_0 - 2} \subseteq \eta'$;
    \item For each $0\leq k \leq n_0-3$, the configuration $\Phi^{k} [\omega']$ contains every pair of unordered vertices of $\Lambda_{n_0-2-k}$ with distance exactly $L$.

\end{enumerate}
Indeed, conditions 2-4 ensure that every vertex in $\eta\cap \Lambda_{n_0}$ is contained in a single $(\eta,\omega)$-cluster in $\Lambda_{n_0}$ while condition 1 ensures that this cluster has the required size.

 For each $1\leq i \leq 4$, let $\mathscr{A}_i$ be the event that the $i$th of these conditions holds. It suffices to prove that
\[
\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_i) = 1-o(\delta)
\]

for each $1\leq i \leq 4$ as $\beta \to \infty$, since this guarantees that $\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\cap_{i=1}^4\mathscr{A}_i)\geq 1-\delta$ when $\beta$ is sufficiently large. We bound each of these probabilities in order, and will use repeatedly that $\delta^{-2}\leq L^{dn_0} \leq L^d \delta^{-2}$ by definition of $\delta$ and $n_0$.

\begin{enumerate}
    \item
For the event $\mathscr{A}_1$, the Chernoff bound
 \begin{multline*}
\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_1^c) = \mathbb{Q}_{1-\delta}\bigl(| \Lambda_{n_0}\setminus \eta|\geq 2\delta |\Lambda_{n_0}|\bigr)
\leq e^{-2\lambda \delta L^{dn_0}} \mathop{\mathbb E} e^{\lambda | \Lambda_{n_0}\setminus \eta|} \\\leq e^{-2\lambda \delta L^{dn_0}} \left(1+  (e^{\lambda}-1)\delta \right)^{L^{dn_0}} \leq \exp\left[-\left(2\lambda -(e^{\lambda}-1) \right) \delta L^{dn_0}  \right]
 \end{multline*}
 holds for every $\lambda>0$, and taking $\lambda = \log 2$ yields that

 \[
\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_1)  \geq 1-\left(\frac{e}{4}\right)^{\delta L^{dn_0}} \geq 1- \left(\frac{e}{4}\right)^{\delta^{-1}} =1-o(\delta)
 \]
 as required.
 \item
For the event $\mathscr{A}_2$, we have the union bound
 \begin{equation*}

   \mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_2) = \mathbb{P}_{\frac{1}{2}\beta} \bra{F_2 \cap E_{n_0} \subseteq  \omega } \geq 1 - \abs{\Lambda_2}^2 \abs{\Lambda_{n_0-2}} e^{-\frac{1}{2} L^{-4d}\beta} =1-O\left(\delta^{-2}e^{-\frac{1}{2} L^{-4d}\beta}\right),

\end{equation*}
and since
$e^{-\frac{1}{2} L^{-4d}\beta} = \delta^{\frac{1}{2}L^{5d}} \leq \delta^{16}$ it follows that
\[\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_2) = 1-O(\delta^{14})=1-o(\delta)\]
as required.
\item
For the event $\mathscr{A}_3$, it follows from \cref{lem:zoom+} and a union bound that
\[
\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_3) \geq 1-(1-p')L^{d(n_0-2)}
\qquad
\text{where}
\qquad
    p' := \mathbb{P}_{\frac{1}{2} \beta, 1-\delta } \bra{ |K^\mathrm{max}_2| \geq 1 } = 1 -\delta^{L^{2d}}

\]
and hence that
\[
\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_3) \geq 1-\delta^{L^{2d}} L^{d(n_0-2)} = 1-O\left(\delta^{L^{2d}-2}\right) = 1-o(\delta)
\]
as required, where in the final estimate we used that $L^{2d}-2\geq 2>1$. (We zoomed out using $\Psi$ \emph{twice} precisely to make this step work; zooming out once would not be sufficient when $d=1$ and $L\in \{2,3\}$.)

\item For the event $\mathscr{A}_4$, we will show that $\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_3\setminus \mathscr{A}_4)=o(\delta)$.  We have by \cref{lem:zoom+} that the conditional distribution of $\omega \cap E_{n_0-2}$ given $\mathscr{A}_3$ stochastically dominates $\mathbb{P}_{\beta'}$ where
$\beta'= L^{-4d} \beta$.
Since we also have by \cref{lem:zoom} that $\Phi_*^{k} \mathbb{P}_{\beta'} = \mathbb{P}_{\beta'}$ for all $k$, it follows by a union bound that
\begin{multline*}
\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_3\setminus \mathscr{A}_4) \leq \sum_{k=0}^{n_0-3} \mathbb{P}_{\beta'}(\omega \nsubseteq F_1 \cap E_{n_0-2-k})\\ \leq \sum_{k=0}^{n_0-3}|\Lambda_1|^2|\Lambda_{n_0-3-k}|e^{-L^{-2d}\beta'} = O(L^{dn_0}e^{-L^{-6d}\beta}) =O\left(\delta^{L^{3d}-2}\right) =O(\delta^6)=o(\delta).
\end{multline*}
Since we also have that $\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_3)=1-o(\delta)$, it follows that $\mathbb{P}_{\frac{1}{2}\beta,1-\delta}(\mathscr{A}_4)=1-o(\delta)$ as required.
\end{enumerate}
This concludes the proof. \qedhere

\end{proof}

\subsection{Upper bounds}
\label{sec:alpha=d_upper}

We conclude the paper with a short proof of the upper bound of \cref{thm:main} in the case $\alpha =d$, recovering a result of \cite{georgakopoulos2020percolation}.

\begin{prop} \label{prop:alpha=d_ub}
If $\alpha=d$ then there exists $C=C(d,L) <\infty$ such that
    $\chi(\beta) \leq e^{ e^{C \beta} }$
for every $\beta \geq 1$.
\end{prop}

We will prove \cref{prop:alpha=d_ub} by proving an equivalent upper bound on the \emph{correlation length}  $\xi(\beta)$ as defined in \cite[Section 4]{MR4462652}.
Following Duminil-Copin and Tassion \cite{duminil2015new}, for each  $\beta\geq 0$, and finite subset $S \subseteq \mathbb H^d_L$  containing the origin we consider the quantity
\[
\phi_\beta(S) =\phi_\beta(S,0) := \sum_{y\notin S}\sum_{x\in S} \Bigl(1-e^{-\beta \|x-y\|^{-d-\alpha}}\Bigr)\mathbb{P}_\beta(0 \xleftrightarrow{S} x),
\]
where we write $\{0 \xleftrightarrow{S} x\}$ to mean that $0$ and $x$ are connected by an open path all of whose vertices belong to $S$. It is a straightforward consequence of the BK inequality as explained in \cite[Lemma 4.2]{MR4462652} that
\[
\sum_{x\in S'} \mathbb{P}_\beta(0 \xleftrightarrow{S'} x) \leq \sum_{x\in S} \mathbb{P}_\beta(0 \xleftrightarrow{S} x) + \phi_\beta(S) \cdot \sup_{u\in S'} \sum_{x\in S'} \mathbb{P}_\beta(u \xleftrightarrow{S'} x)
\]
for every $\beta\geq 0$ and every pair of finite sets $S \subseteq S' \subseteq \mathbb H^d_L$. As such, if $\phi_\beta(S)<1$ then we may take the limit as $S'$ exhausts $\mathbb H^d_L$ to obtain that
\[
\sum_{x\in S} \mathbb{P}_\beta(0 \xleftrightarrow{S} x) \leq \chi(\beta)\leq \frac{1}{1-\phi_\beta(S)}\sum_{x\in S} \mathbb{P}_\beta(0 \xleftrightarrow{S} x).
\]
For each $n \geq 0$ we define
\[
\beta_n = \sup\left\{\beta \geq 0 : \phi_\beta(\Lambda_n,0) \leq \frac{1}{2} \right\} \qquad \text{ and } \qquad \beta^*_n = \max_{0 \leq m \leq n} \beta_m,
\]
so that $(\beta_n^*)_{n\geq 0}$ is a non-decreasing sequence.
For each $0\leq \beta<\beta_c$ we define the \textbf{correlation length} $\xi(\beta)$ by
\begin{equation}
\label{eq:correlation_length_definition}
\xi(\beta) = L^{n(\beta)} \qquad \text{ where } \qquad  n(\beta)=\inf\{n\geq 0 : \beta \leq \beta_n^*\},
\end{equation}
which has the property that the global susceptibility $\chi(\beta)$ is within a factor of two of the expected number of points that are connected to $0$ within the ball of radius $\xi(\beta)$:
\begin{equation}
\label{eq:correlation_length_susceptibility}
\sum_{x\in \Lambda_{n(\beta)}} \mathbb{P}_\beta(0\xleftrightarrow{\Lambda_{n(\beta)}} x ) \leq \chi(\beta) \leq 2 \sum_{x\in \Lambda_{n(\beta)}} \mathbb{P}_\beta(0\xleftrightarrow{\Lambda_{n(\beta)}} x ).
\end{equation}
(Note that this estimate holds for every $\alpha>0$.)
Since the right hand side is trivially at most $2|\Lambda_{n(\beta)}|=2 \xi(\beta)^d$, \cref{prop:alpha=d_ub} follows from \eqref{eq:correlation_length_susceptibility} and the following proposition.

\begin{prop}
\label{prop:alpha=d_correlation_length} If $\alpha =d$ then there exist constants $c=c(d,L)>0$ and $C=C(d,L)<\infty$ such that the correlation length satisfies
$e^{e^{c\beta}}\leq \xi(\beta) \leq e^{e^{C\beta}}$
 for every $\beta \geq 1$.
\end{prop}

\begin{proof}
The lower bound follows from \cref{prop:alpha=d_lb} since $\chi(\beta)\leq 2\xi(\beta)^d$; it remains to prove the upper bound. We begin by bounding $\mathbb{P}_\beta(0\leftrightarrow \Lambda_n^c)$ for appropriately large $n$ using an exploration argument.
Define a random sequence $(n_i)_{i\geq 0}$ by setting $n_0=0$ and recursively setting $n_{i+1}$ to be maximal such that there is an open edge connecting $\Lambda_{n_i}$ to $\Lambda_{n_{i+1}}\setminus \Lambda_{n_{i+1}-1}$, taking $n_{i+1}=n_i$ if there are no open edges incident to $\Lambda_{n_i}$. We define $\tau$ to be the minimal $i$ such that $n_{i+1}=n_i$, so that $0\leftrightarrow \Lambda_n^c$ only if $n_\tau>n$. For each $i\geq 0$ let $\mathcal{F}_i$ be the $\sigma$-algebra generated by $n_0,\ldots,n_i$. Since we can compute $n_0,\ldots,n_i$ in such a way that we only reveal edges with at least one endpoint in $\Lambda_{n_i}$ and any revealed edge with an endpoint in $\Lambda_{n_i}^c$ is closed, we have that
\begin{align*}
\mathbb{P}_\beta(n_{i+1}> n_i+k \mid \mathcal{F}_i) &\leq \mathbb{P}_\beta(\text{there is an open edge connecting $\Lambda_{n_i}$ and $\Lambda_{n_i+k}^c$})\\
&=\mathbb{P}_\beta(\text{there is an open edge connecting $\Lambda_{0}$ and $\Lambda_{k}^c$})
\end{align*}
almost surely for each $i,k\geq 0$, where the final equality follows from \cref{lem:zoom} (where $L^{d-\alpha}\beta=\beta$ since $\alpha=d$).
Letting $X_1,X_2,\ldots$ be i.i.d.\ random variables with distribution
\[
\mathbb{P}(X_1 > k) = \mathbb{P}_\beta(\text{there is an open edge connecting $\Lambda_{0}$ and $\Lambda_{k}^c$})
\]
and letting $T=\min\{i:X_i =0\}$, it follows that
\[
\mathbb{P}(n_\tau \geq n) \leq \mathbb{P}\left(\sum_{i=1}^T X_i \geq n\right).
\]
Now, we can compute that
\begin{align*}
\mathbb{P}(X_1 > k)
  &= \mathbb{P}_\beta(\text{there is an open edge connecting $\Lambda_{0}$ and $\Lambda_{k}^c$})
  \\&= 1-\exp\left[-\beta\sum_{\ell=k+1}^\infty  L^{-2d\ell} (L^{d\ell}-L^{d(\ell-1)}) \right]
  = 1-\exp\left[-\beta L^{-d(k+1)}\right]

\end{align*}
so that
$\mathbb{P}(X_1=0)=\exp\left[-L^{-d}\beta \right]$
and
\[
\mathop{\mathbb E} X_1 = \sum_{k=0}^\infty \mathbb{P}(X_1 >k) = \sum_{k=0}^\infty 1-\exp\left[-\beta L^{-d(k+1)}\right] \leq \beta \sum_{k=0}^\infty L^{-d(k+1)} = \frac{L^{-d}}{1-L^{-d}}\beta.
\]
Thus, we have by Markov's inequality that
\[
\mathbb{P}_\beta(0\leftrightarrow \Lambda_n^c) \leq \mathbb{P}_\beta(n_\tau \geq n) \leq \mathbb{P}(T \geq t) + \mathbb{P}\left(\sum_{i=1}^t X_i \geq n\right) \leq (1-e^{-L^{-d}\beta})^t + \frac{L^{-d}}{1-L^{-d}} \frac{\beta t}{n}
\]
for every $n,t\geq 1$. Taking $t=\lceil \beta^{-3} n \rceil$, we deduce that there exist constants $C_1$ and $C_2$ such that if $n \geq C_1 \beta^4 e^{L^{-d} \beta} $ then
\begin{equation}
\label{eq:escape_large_ball}
\mathbb{P}_\beta(0\leftrightarrow \Lambda_n^c) \leq (1-e^{-L^{-d}\beta})^{\lceil \beta^{-3} n \rceil} + O(\beta^{-2}) \leq  C_2 \beta^{-2}.
\end{equation}
To complete the proof, we note (using that $1-e^{-\beta \|x-y\|^{-2d}} \leq \beta \|x-y\|^{-2d}$) that there exists a constant $C_3$ such that
\[
\phi_\beta(\Lambda_n) \leq \sum_{y\in \Lambda_n^c}\sum_{x\in \Lambda_n} \beta \|x-y\|^{-2d} \mathbb{P}_\beta(0 \xleftrightarrow{\Lambda_n} x) \leq C_3 \beta L^{-dn} \sum_{x\in \Lambda_n} \mathbb{P}_\beta(0 \xleftrightarrow{\Lambda_n} x)
\]
for every $n\geq 1$ and that
\[
 \sum_{x\in \Lambda_n} \mathbb{P}_\beta(0 \xleftrightarrow{\Lambda_n} x) \leq 1+ \sum_{k=0}^n L^{d(k+1)}\mathbb{P}_\beta(0\leftrightarrow \Lambda_k^c),
\]
so that there exist constants $C_4$ and $C_5$ such that if $n \geq 2C_1 \beta^4 e^{L^{-d} \beta}$ then
\begin{align*}
\sum_{x\in \Lambda_n} \mathbb{P}_\beta(0 \xleftrightarrow{\Lambda_n} x) &\leq
1+\sum_{k=0}^{\lfloor n/2 \rfloor} L^{d(k+1)} +  \sum_{k=\lceil n/2 \rceil}^{n} L^{d(k+1)} C_2 \beta^{-2} \\&\leq 1+
 \sqrt{L^{d(n+1)}}+C_4 \beta^{-2} L^{dn} \leq C_5 \beta^{-2} L^{dn},
\end{align*}
where we used that $\lceil n/2 \rceil \geq C_1 \beta^4 e^{L^{-d} \beta}$ to apply \eqref{eq:escape_large_ball} in the first inequality.
It follows that if $n\geq 2C_1 \beta^4 e^{L^{-d} \beta}$ then
$\phi_\beta(\Lambda_n) \leq C_3 C_5 \beta^{-1}$,
which is less than $1/2$ when $\beta$ is sufficiently large. This implies that
$n(\beta) = O\left(\beta^4 e^{L^{-d} \beta}\right)=e^{O(\beta)}$
and hence that $\xi(\beta)=e^{e^{O(\beta)}}$ as required. \qedhere

\end{proof}

\begin{proof}[Proof of \cref{prop:alpha=d_ub}]
The claim follows immediately from \cref{prop:alpha=d_correlation_length} and the inequality $\chi(\beta)\leq 2\xi(\beta)^d$.
\end{proof}

\begin{proof}[Proof of \cref{thm:main}]
The case $\alpha>d$ follows from \cref{lem:alpha>d_ub,prop:alpha>d_lb} while the case $\alpha=d$ follows from \cref{prop:alpha=d_lb,prop:alpha=d_ub}.
\end{proof}

\subsection*{Acknowledgements} This work was carried out as part of Caltech's Summer Undergraduate Research Fellowship (SURF) program 2022, during which JK was mentored by PE and TH. During the research, JK was also supported by an NSERC USRA. We thank Louigi Addario-Berry and Johannes B\"aumler for helpful comments on a draft.

\setstretch{1}
\footnotesize{
\bibliographystyle{abbrv}


\section{Introduction}
\label{sec1}

A binary protocol sequence set for transmitting data packets over a multiple-access collision channel without feedback is called a {\it conflict-avoiding code} (CAC) in information theory and has been studied few decades ago by \cite{Mat, NguGyoMas, GyoVaj, TsyRub, LevTon, Lev}. A mathematical model for CACs of {\it length} $n$ and ({\it Hamming}) {\it weight} $w$ is as follows. Let $\zz_n = \zz / n \zz$ be the additive group of $\zz$ modulo $n$. For a $w$-subset ${\bf x} = \{x_1, \ldots, x_w\}$ of $\zz_n$, denote the difference set of ${\bf x}$ by $\Delta({\bf x}) = \{x_i - x_j \mid i \neq j\}$. A CAC of length $n$ and weight $w$ is a collection $\mathcal{C}$ of $w$-subsets of $\zz_n$ such that $\Delta({\bf x}) \cap \Delta({\bf y}) = \varnothing$ for every distinct ${\bf x}, {\bf y}$ of $\mathcal{C}$. Each ${\bf x}$ is called a {\it codeword}. A CAC is said to be {\it optimal} if it has the maximal size among all CACs of the same length and weight. When the weight is $1$ or $2$, there is no difficulty to find the optimal size. For weights more than $2$, however, finding an optimal CAC and determining its size is still an open problem. The first challenge is the weight $3$ and we introduce its development below.

Assume that the weight $w = 3$. The construction of an optimal CAC of an arbitrary even length is completely found by many authors \cite{LevTon, JimMisJanTeyTon, MisFuUru, FuLinMis}. However, the known results for odd lengths are still far from completion. In the case that the length $n$ is odd, the multiplicative order of $2$ in the multiplicative group of units of $\zz_p$ for prime divisors $p$ of $n$ becomes a key role in constructing an optimal CAC. For convenience, we denote $\zz_p^{\times}$ by the multiplicative group of $\zz_p$ and $o_p(2)$ by the multiplicative order of $2$ in $\zz_p^{\times}$ for an odd prime $p$.
A construction of optimal CAC is found in \cite{LevTon} for prime length $p$ such that $4 \mid o_p(2)$. Later, the construction is improved in \cite{Lev} for composite number length where every prime divisor $p$ of the length satisfies $4 \mid o_p(2)$.

The remaining situation is that the length has a prime divisor $p$ such that $4 \nmid o_p(2)$. In \cite{FuLoShu}, the authors prove that the problem of such length can be reduced to the problem of length $n$ such that {\it every} prime divisor $p$ of $n$ satisfies $4 \nmid o_p(2)$. They also prove that an optimal CAC of length $n = p^k$ can be constructed from an optimal CAC of length $p$ where $p$ is a non-Wieferich prime (that $2^{p-1} \not\equiv 1 \pmod{p^2}$). However, the construction for prime length $p$ is not completely found. For other odd lengths
one can refer to \cite{Mom, WuFu, LinMisSatJim, MisMom, HsiLiSun} for the constructions. It turns out that the prime lengths are fundamental objects needed to be solved. This leads us to study CACs prime lengths and weight $3$.

For an odd prime length $p > 3$, a difference set $\Delta({\bf x})$ would have size $4$ or $6$ for a $3$-subset ${\bf x}$ of $\zz_p$. Without loss of generality, we can assume the codeword ${\bf x}$ to be $\{0, \alpha, \beta\}$ for some $\alpha, \beta \in \zz_p^{\times}$. Then $|\Delta({\bf x})| = 4$ if and only if ${\bf x} = \{0, \alpha, 2 \alpha\}$ for some $\alpha$. In this case, ${\bf x}$ is called an {\it equi-difference} codeword. To have an optimal CAC, it is natural to have equi-difference codewords as many as possible.
If $M^e(p)$ denotes the maximal size among all CACs consisting of equi-difference codewords only, then one has
$$M^e(p) = \frac{p-1-2 O(p)}{4}$$ where $O(p) = 0$ if $4$ divides $\left| \langle -1, 2 \rangle \right|$ and $O(p) = (p-1) / \left| \langle -1, 2 \rangle \right|$ otherwise.
Moreover, \cite[Lemma~3]{FuLoShu} provides
\begin{align}
\label{upper bound: FLS}
M^e(p) \leq M(p) \leq M^e(p) + \left\lfloor \frac{O(p)}{3} \right\rfloor
\end{align}
where $M(p)$ denotes the maximal size among all CACs.
Thus, if $O(p) < 3$, then a CAC consisting of equi-difference codewords only must be optimal.
It remains to consider $O(p) \geq 3$.
The authors of \cite{FuLoShu} propose an algorithm for constructing nonequi-difference codewords. They conjecture that the algorithm always works for prime length $p$ for constructing $\left\lfloor \frac{O(p)}{3} \right\rfloor$ nonequi-difference codewords. Then $\frac{p-1-2 O(p)}{4}$ equi-difference codewords could be further obtained and this CAC would be optimal by the upper bound in \eqref{upper bound: FLS}.
For our purpose, we rephrase the statement of their conjecture in terms of cosets of the subgroup $\langle -1, 2 \rangle$, generated by $-1$ and $2$, in the multiplicative group $\zz_p^{\times} = \zz_p \setminus \{0\}$.

\begin{conjectureA}[{\cite[Conjecture~1]{FuLoShu}}]
\label{conjA}
Let $p$ be a non-Wieferich prime.
Then there are $3 \left\lfloor \frac{O(p)}{3} \right \rfloor$ cosets
$A_1, B_1, C_1, \ldots,
A_{\left\lfloor \frac{O(p)}{3} \right \rfloor},
B_{\left\lfloor \frac{O(p)}{3} \right \rfloor},
C_{\left\lfloor \frac{O(p)}{3} \right \rfloor}
$
of the subgroup $\langle -1, 2 \rangle$ in
$\zz_p^{\times}$ such that for each $i$ there exists $(a_i, b_i, c_i) \in A_i \times B_i \times C_i$ satisfying
$$
a_i + b_i = c_i \quad \text{in } \zz_p.
$$
\end{conjectureA}

We remark that each $(a_i, b_i, c_i)$ corresponds to the nonequi-difference codeword
${\bf x}_i = \{0, a_i, c_i\}$
where
$\Delta({\bf x}_i) = \{\pm a_i, \pm b_i, \pm c_i\}$.
Those triples $(a_i, b_i, c_i)$ above correspond to a {\it hypergraph matching} in an auxiliary hypergraph in their terminology.
We give an example to illustrate how Conjecture~\ref{conjA} and their algorithm work for constructing an optimal CAC.

Consider CACs of length $p = 73$ and weight $3$ where $O(p) = 4$. First, there are four cosets of $\langle -1, 2 \rangle$ in $\zz_{73}^{\times}$: $$\langle -1, 2 \rangle, \quad 3 \langle -1, 2 \rangle, \quad 5 \langle -1, 2 \rangle, \quad 11 \langle -1, 2 \rangle.$$
We pick elements $a, b, c$ in three different cosets respectively such that $a + b = c$. For example, we choose $a = 2$, $b = 3$ and $c = 5$ from the first three cosets. Let ${\bf x} = \{0, 2, 5\}$. Then ${\bf x}$ is a nonequi-difference codeword and $\Delta({\bf x}) = \{\pm 2, \pm 3, \pm 5\}$. The elements in $\langle -1, 2 \rangle \setminus \Delta({\bf x})$ lead to four equi-difference codewords $${\bf x}_1 = \{0, 2^2, 2^3\}, \quad {\bf x}_2 = \{0, 2^4, 2^5\}, \quad {\bf x}_3 = \{0, 2^6, 2^7\}, \quad {\bf x}_4 = \{0, 2^8, 2^9\}.$$ It is similar to $3 \langle -1, 2 \rangle \setminus \Delta({\bf x})$, $5 \langle -1, 2 \rangle \setminus \Delta({\bf x})$ and $11 \langle -1, 2 \rangle \setminus \Delta({\bf x})$ that $${\bf x}_{i+4} = \{0, 3 \cdot 2^{2i}, 3 \cdot 2^{2i+1}\}, \quad {\bf x}_{i+8} = \{0, 5 \cdot 2^{2i}, 5\cdot 2^{2i+1}\}, \quad  {\bf x}_{i+12} = \{0, 11 \cdot 2^{2i}, 11 \cdot 2^{2i+1}\},$$ respectively, for $i = 1, 2, 3, 4$. The difference sets of all codewords ${\bf x}, {\bf x}_1, \ldots, {\bf x}_{16}$ are pairwisely disjoint.
By the upper bound of $M(p)$ in \eqref{upper bound: FLS}, the collection $\mathcal{C} = \{{\bf x}, {\bf x}_1, \ldots, {\bf x}_{16}\}$ forms an optimal CAC which consists of $1$ nonequi-difference codeword and $16$ equi-difference codewords. If we choose $a = 6$, $b = 5$ and $c = 11$ such that $a + b = c$, then ${\bf x} = \{0, 6, 11\}$ and $\Delta({\bf x}) = \{\pm 6, \pm 5, \pm 11\}$. The same procedure will lead to another $16$ equi-difference codewords. Different choices of $a, b, c$ will give different optimal CACs.

The authors of \cite{MaZhaShe} independently give a similar thought to the existence of the triples $(A_i, B_i, C_i)$ in Conjecture~\ref{conjA} in terms of the group structure of the quotient group $\zz_p^{\times} / \langle -1, 2 \rangle$.
They notice that $\zz_p^{\times} / \langle -1, 2 \rangle$ is a cyclic group because $\zz_p^{\times}$ is cyclic.

\begin{conjectureA}[{\cite[Conjecture]{MaZhaShe}}]
\label{conjB}
Let $p$ be an odd prime. If $\left[ \zz_p^{\times} : \langle -1, 2 \rangle \right] \geq 3$, then there is a generator $t \langle -1, 2 \rangle$ of the cyclic group $\zz_p^{\times} / \langle -1, 2 \rangle$ for some $t \in \zz_p^{\times}$ such that $$1 + b = c$$ for some $b \in t \langle -1, 2 \rangle$ and $c \in t^2 \langle -1, 2 \rangle$.
\end{conjectureA}

Note that $\left[ \zz_p^{\times} : \langle -1, 2 \rangle \right] \geq 3$ implies either $O(p) = 0$ or $O(p) \geq 3$. Moreover, if Conjecture~\ref{conjB} holds for a prime $p$, then one can set $A_1 = t^0 \langle -1, 2 \rangle$, $B_1 = t^1 \langle -1, 2 \rangle$, $C_1 = t^2 \langle -1, 2 \rangle$, $A_2 = t^3 \langle -1, 2 \rangle$, $B_2 = t^4 \langle -1, 2 \rangle$, $C_2 = t^5 \langle -1, 2 \rangle$ and so on to obtain $t^{3 i} + t^{3 i} b = t^{3 i} c$ for each $i$ where $(t^{3i}, t^{3 i} b, t^{3 i} c) \in A_i \times B_i \times C_i$. Hence, Conjecture~\ref{conjB} implies Conjecture~\ref{conjA}.
For the previous example that $p = 73$, $t$ can be chosen as $5$.
Then $b = 5$, $c = 6 \in 5^2 \langle -1, 2 \rangle$ and $1 + 5 = 6$ in $\zz_p$.
Moreover, $p$ is not assumed to be non-Wieferich.
In \cite{MaZhaShe}, the authors have checked in computer that Conjecture~\ref{conjB} holds for prime $p \leq 2^{30}$.

The motivation of this article is to study Conjecture~\ref{conjB}. Throughout this article, we denote $$\ell = \left[ \zz_p^{\times} : \langle -1, 2 \rangle \right] =\left|\zz_p^{\times} / \langle -1, 2 \rangle\right|$$ for a given prime $p$.
The existence of $b$ and $c$ in Conjecture~\ref{conjB} is strongly related to the so-called {\it cyclotomic numbers $A(i, j)$ of order $\ell$} with respect to a primitive root where $i, j$ are integers. In particular, both $b$ and $c$ exist if and only if $A(i, 2 i) \neq 0$ for certain $i$.
More precisely, Conjecture~\ref{conjB} is equivalent to the following statement. See Section~\ref{sec2} for detail.

\begin{conjecture*}
Let $p$ be an odd prime and let $\ell = \left[ \zz_p^{\times} : \langle -1, 2 \rangle \right]$. If $\ell \geq 3$, then $A(i, 2i) \neq 0$ for some $1 \leq i \leq \ell-1$ with $(i, \ell) = 1$.
\end{conjecture*}

The cyclotomic numbers was considered by C.F. Gauss \cite{Gau} and later L.E. Dickson \cite{Dic, Dic3, Dic4} studied these numbers in the context of Waring's problem. One of the central problems is to determine these numbers in terms of solutions of a certain Diophantine systems.
See also the surveys \cite{Raj,Kat2, AhmTan}. However, it is still not obvious whether $A(i, 2i) \neq 0$ because it is difficult either to find a suitable Diophantine system or to write down the formulas of cyclotomic numbers when $\ell$ is getting larger. Recently, cyclotomic numbers are developed into a secured public-key cryptography model \cite{AhmTanPus}.

In this article, we study the conjecture above and we will prove the following result.

\begin{thmA}
\label{thmA}
Let $p$ be an odd prime and let $\ell = [\zz_p^{\times} : \langle -1, 2 \rangle]$. If $\ell$ is an odd prime, then $A(i, 2 i) \neq 0$ for some $1 \leq i \leq \ell-1$ with $(i, \ell) = 1$.
\end{thmA}

This not only answers Conjecture~\ref{conjB} but Conjecture~\ref{conjA} for a class of primes $p$. Moreover, the size $M(p)$ of optimal CAC can be determined as follows, while $O(p) = \ell$ if $4 \nmid o_p(2)$.

\begin{thmA}
\label{thmB}
Let $p$ be an odd prime with $4 \nmid o_p(2)$. If $\ell = [\zz_p^{\times} : \langle -1, 2 \rangle]$ is an odd prime, then an optimal conflict-avoiding code of length $p$ and weight $3$ has the size $$\frac{p-1-2 \ell}{4} + \left\lfloor \frac{\ell}{3} \right\rfloor.$$
\end{thmA}

This article is organized as follows. In Section~\ref{sec2}, we introduce cyclotomic numbers and see how these numbers connect to Conjecture~\ref{conjB}.
The cyclotomic numbers will lead to an interesting matrix in Section~\ref{sec3}. This matrix can be used to answer Conjecture~\ref{conjB}, as well as Conjecture~\ref{conjA}, for primes with small $\ell$.
In Section~\ref{sec4}, we will see that the number of squares in a certain subset of $\zz_p$ can be represented to a particular sum of cyclotomic numbers. By counting squares and using an upper bound of cyclotomic numbers given in \cite{BetHirKomMun}, we will be able to prove Theorem~\ref{thmA}.
Finally, we remark how an obstacle is encountered for primes with composite number $\ell$.

\section{Preliminaries}
\label{sec2}

In this article, $p$ is an odd prime and $\zz_p$ is the finite field of $p$ elements. Throughout this article, we denote $$L = \langle -1, 2 \rangle$$ the subgroup of $\zz_p^{\times} = \zz_p \setminus \{0\}$ generated by $-1$ and $2$, and then $\ell = \left[ \zz_p^{\times} : L \right]$ is the index of $L$ in $\zz_p^{\times}$. We always assume $$\ell \geq 3.$$ A generator of $\zz_p^{\times}$ is also called a {\it primitive root} of $\zz_p$. Fix a primitive root $g$.
Define the number $$A(i, j) = \left| \left\{(m, n) \mid 0 \leq m, n \leq \frac{p-1}{\ell} - 1 \text{ and } 1 + g^{i + m \ell} = g^{j + n \ell} \right\} \right|$$ for $i, j \in \zz$.
These numbers $A(i, j)$ are called {\it cyclotomic numbers of order $\ell$ with respect to $g$}. We can rewrite $A(i, j)$ as follows. Note that $|L| = \frac{p-1}{\ell}$ and $L$ consists of all $\ell$-th power of elements of $\zz_p^{\times}$. Thus, both $g^{m \ell}, g^{n \ell} \in L$ for $0 \leq m, n \leq |L| - 1$.
It follows that $$A(i, j) = \left| (1 + g^i L) \cap g^j L \right|$$ for $i, j \in \zz$. If $i'$ and $j'$ are integers such that $i' \equiv i \pmod{\ell}$ and $j' \equiv j \pmod{\ell}$, then $g^{i'}L = g^{i} L$ and $g^{j'} L = g^{j} L$. We have $A(i', j') = A(i, j)$. Hence, it is convenient to consider $i, j$ modulo $\ell$.

As $g$ is a primitive root and $\ell = \left[ \zz_p^{\times} : L \right]$, the quotient group $\zz_p^{\times} / L$ consists of elements $g^0 L = L, g^1 L, \ldots, g^{\ell-1} L$. In particular, the set $$\left\{g^i L \mid 1 \leq i \leq \ell \text{ and } (i, \ell) = 1\right\}$$ is a complete set of generators of $\zz_p^{\times} / L$ where $(\cdot, \cdot)$ denotes the greatest common divisor of two given integers. Let $t \in \zz_p^{\times}$. Then $t L$ generates $\zz_p^{\times} / L$ if and only if $t L = g^i L$ for some $1 \leq i \leq \ell$ with $(i, \ell) = 1$.
Moreover, $$\left| (1 + t L) \cap t^2 L \right| = \left| (1 + g^i L) \cap g^{2 i} L \right| = A(i, 2 i).$$ Thus, Conjecture~\ref{conjB} holds for $p$ if and only if $A(i, 2 i) \neq 0$ for some $1 \leq i \leq \ell$ with $(i, \ell) = 1$. Because each $A(i, 2i)$ is nonnegative, it is enough to consider the following sum $$s(\ell) = \sum_{\substack{1 \leq i \leq \ell, \\ (i, \ell) = 1}} A(i, 2i).$$ The argument above actually shows the following lemma.

\begin{lem}
\label{lem2.3}
Let $p$ and $\ell$ be as above. Then $s(\ell) \neq 0$ if and only if \textup{Conjecture~\ref{conjB}} holds for this $p$.
\end{lem}

The sum $s(\ell)$ is defined with respect to a given primitive root $g$. In fact, we can freely compute $s(\ell)$ when picking an {\it arbitrary} primitive root. This helps a lot in practice. We leave a proof below for the readers because we do not find any reference for this fact.

\begin{prop}
\label{prop2.1}
The sum $s(\ell)$ is independent on the choices of primitive roots.
\end{prop}

\begin{proof}
Let $h$ be a primitive root of $\zz_p$. Denote $A'(i, j) = |(1 + h^i L) \cap h^j L|$ and $s'(\ell)$ the sum of $A'\left(i, 2i\right)$ for $i = 1, \ldots, \ell$ with $(i, \ell) = 1$. Since $h L$ also generates $\zz_p^{\times} / L$, $h L = g^k L$ for some $1 \leq k \leq \ell$ with $(k, \ell) = 1$. Then $h^i L = g^{k i} L$ and thus $A'(i, j) = A(k i, k j)$ for $i, j \in \zz$. Recall that $\{1 \leq i \leq \ell \mid (i, \ell) = 1\}$ is a reduced residue system modulo $\ell$. Since $(k, \ell) = 1$, it follows that $\{k i \mid 1 \leq i \leq \ell \text{ and } (i, \ell) = 1\}$ is also a reduced residue system modulo $\ell$. Thus, $$s'(\ell) = \sum_{\substack{1 \leq i \leq \ell, \\ (i, \ell) = 1}} A'(i, 2i) = \sum_{\substack{1 \leq i \leq \ell, \\ (i, \ell) = 1}} A\left(k i, k(2i)\right) = \sum_{\substack{1 \leq i \leq \ell, \\ (i, \ell) = 1}} A(i, 2i) = s(\ell).$$
\end{proof}

As we have mentioned, one of main problems on the theory of cyclotomic numbers is to find explicit formulas for all $A(i, j)$ in terms of solutions of certain Diophantine systems. For example, consider $p \equiv 1 \pmod{3}$ such that $\ell = 3$. It is well-known that the Diophantine system $$\left\{ \begin{array}{c} 4 p = X^2 + 27 Y^2, \\ X \equiv 1 \pmod{3} \end{array} \right.$$ has a solution $(a, b)$ with unique $a$, where $-p < a < p$. \cite[Section~358]{Gau} gives that $$A(0,0) = \frac{1}{9} (p - 8 + a),$$ $$ A(0,1) = A(1,0) = A(2,2) = \frac{1}{18} (2p - 4 - a + 9 b),$$ $$A(0,2) = A(1,1) = A(2, 0) = \frac{1}{18} (2p - 4 - a - 9 b),$$ $$A(1, 2) = A(2, 1) = \frac{1}{9} (p + 1 + a)$$ where the sign of $b$ depends of the choices of primitive roots. In this case, $A(1, 2) = A(2, 1) > 0$ and thus $$s(3) = A(1,2) + A(2, 4) = A(1,2) + A(2,1) >0,$$ while $A(2, 4) = A(2, 1)$ because $4 \equiv 1 \pmod{\ell}$.
However, the formulas for large $\ell$ will be extremely complicated and hard to find. For instance, the formulas for $\ell = 11$ are presented in \cite{LeoWil}. But it is not obvious whether $s(11) \neq 0$ or not for $p \equiv 1 \pmod{11}$. See also Example~\ref{exmp4.1}. \\

We deduce the following useful properties.

\begin{lem
\label{lem4.1}
For $i, j$ modulo $\ell$, $$A(i, j) = A(-i, j-i) \quad \text{and} \quad A(i, j) = A(j, i).$$
\end{lem}

\begin{proof}
For $\alpha \in (1 + g^i L) \cap g^j L$, write $\alpha = 1 + g^i a = g^j b$ for some $a, b \in L$. One has $1 + (\alpha - 1)^{-1} = 1 + g^{-i} a^{-1} \in 1 + g^{-i} L$. Moreover, $1 + (\alpha - 1)^{-1} = (g^i a + 1) g^{-i} a^{-1} = (g^{j} b) (g^{-i} a^{-1}) = g^{j-i} (b a^{-1}) \in g^{j-i} L$. This gives a map $\varphi$ from $(1 + g^i L) \cap g^j L$ into $(1 + g^{-i} L) \cap g^{j-i} L$ given by $\varphi(\alpha) = 1 + (\alpha - 1)^{-1}$. One can deduce that $\varphi$ is a bijection.
Hence, the first equality holds.

For the second equality, observe that $1 - \alpha = 1 + g^j (-b) = g^i (-a) \in (1 + g^j L) \cap g^i L$ as $-1 \in L$. Then $\alpha \mapsto 1 - \alpha$ gives a bijection from $(1 + g^i L) \cap g^j L$ onto $(1 + g^j L) \cap g^i L$.
\end{proof}

\section{Extended Cyclotomic Matrices}
\label{sec3}

The modulo relation and properties of cyclotomic numbers lead us to an interesting matrix. This will provide a new insight to the conflict-avoiding code problem. In this section, we will be able to easily answer Conjecture~\ref{conjB} for small $\ell$.

For a given primitive root of $\zz_p$, the {\it cyclotomic matrix} is an $\ell$-by-$\ell$ matrix defined as follows $$(A(i, j))_{\ell \times \ell} \quad \text{for } i, j = 0, 1, \ldots, \ell-1.$$
It is convenient to give a variation of the cyclotomic matrix. We define the {\it extended cyclotomic matrix} $B = (b_{i, j})_{\ell \times \ell}$ as follows $$b_{i, j} = \left\{ \begin{array}{ll} A(0, 0) + 1 & \text{if $i = j = 0$;} \\ A(i, j) & \text{otherwise}. \end{array} \right.$$
For $i, j$ modulo $\ell$, Lemma~\ref{lem4.1} gives the relation for entries: \begin{align} b_{i, j} = b_{-i, j-i} = b_{j-i, -i} = b_{i-j, -j} = b_{-j, i-j} = b_{j, i}.\label{eq5}\end{align}
For convenience, the row $(b_{i,0}, b_{i, 1}, \ldots, b_{i, \ell-1})$ of $B$ is said to be {\it indexed by $i$} for $i = 0, \ldots, \ell-1$.
This matrix $B$ has following nice properties.

\begin{lem}
\label{lem3.3}
Let $B$ be the extended cyclotomic matrix as above.
\begin{enumerate}
\item[(i)]
$B$ is symmetric with nonnegative integer entries and $b_{0,0} > 0$.
\item[(ii)]
The diagonal entries after $b_{0,0}$ is the reverse of the row indexed by $0$\textup{:} $$(b_{1,1}, b_{2,2}, \ldots, b_{\ell-1, \ell-1}) = (b_{0, \ell-1}, b_{0, \ell-2}, \ldots, b_{0, 1}).$$
\item[(iii)]
For $1 \leq i \leq \ell-1$, the row indexed by $\ell - i$ is shifted $i$ times to the left by the row indexed by $i$\textup{:} $$(b_{\ell-i, 0}, b_{\ell-i, 1}, \ldots, b_{\ell-i, \ell-1}) = (b_{i, i}, b_{i, i+1}, \ldots, b_{i, \ell-1}, b_{i, 0}, \ldots, b_{i, i-1})$$
\item[(iv)]
The trace, the sum of each row and the sum of each column are all $|L| = \frac{p-1}{\ell}$.
\end{enumerate}
\end{lem}

\begin{proof}
(i), (ii) and (iii) are obvious from (\ref{eq5}) that $b_{i, j} = b_{j, i}$, $b_{i, i} = b_{0, \ell-i}$ and $b_{\ell - i, j} = b_{i, j + i}$.

For (iv), let $g$ be the given primitive root. Then the group $\zz_p^{\times}$ is the disjoint union of $g^0 L, g^1 L, \ldots, g^{\ell-1} L$. Since $1 \not\in 1 + L$, the sum of row indexed by $0$ is $$\sum_{j = 0}^{\ell-1} b_{0,j} = 1 + \sum_{j = 0}^{\ell-1} A(0, j) = 1 + \sum_{j=0}^{\ell-1} \left|(1 + L) \cap g^j L \right| = 1 + \left| (1 + L) \cap \zz_p^{\times} \right| = |L|.$$ Moreover, the sum of row indexed by $i$ for $i \neq 0$ is $$\sum_{j=0}^{\ell-1} b_{i, j} = \sum_{j=0}^{\ell-1} A(i, j) = \sum_{j=0}^{\ell-1} \left|(1 + g^i L) \cap g^j L \right| = \left| (1 + g^i L) \cap \zz_p^{\times} \right| = |L|.$$ The trace of $B$ is also $|L|$ by (ii). Finally, the sum of each column is $|L|$ by (i).
\end{proof}

Recall the sum $s(\ell)$ and we have $$s(\ell) = \sum_{\substack{1 \leq i \leq \ell, \\ (i, \ell) = 1}} b_{i, 2i}.$$ The relations~(\ref{eq5}) and Lemma~\ref{lem3.3} lead us to answer that $s(\ell) > 0$ for small $\ell$.

\begin{prop}
\label{prop3.1}
For $\ell = 3, 4, 5$, we have $s(\ell) > 0$.
\end{prop}

\begin{proof}
Using (\ref{eq5}) and (i), (ii), (iii) of Lemma~\ref{lem3.3}, we make the matrix $B$ less complicated.
For convenience, we denote $r_i$ by the row indexed by $i$.

For $\ell = 3$, $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} \\ b_{1,0} & b_{1,1} & b_{1,2} \\ b_{2,0} & b_{2,1} & b_{2,2} \end{matrix} \right).$$ By symmetry, $b_{1,0} = b_{0,1}$, $b_{2,0} = b_{0,2}$ and $b_{2,1} = b_{1,2}$. By Lemma~\ref{lem3.3}(ii), $(b_{1,1}, b_{2,2}) = (b_{0,2}, b_{0,1})$. Thus, $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} \\ b_{0,1} & b_{0,2} & b_{1,2} \\ b_{0,2} & b_{1,2} & b_{0,1} \end{matrix} \right).$$ By Lemma~\ref{lem3.3}(iv), the sums of $r_0$ and $r_1$ are equal. We have $b_{0,0} = b_{1,2}$. We obtain $s(3) = b_{1,2} + b_{2,4} \geq b_{1,2} = b_{0,0} > 0.$

For $\ell = 4$, $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} \\ b_{1,0} & b_{1,1} & b_{1,2} & b_{1,3} \\ b_{2,0} & b_{2,1} & b_{2,2} & b_{2,3} \\ b_{3,0} & b_{3,1} & b_{3,2} & b_{3,3} \end{matrix} \right).$$ By Lemma~\ref{lem3.3}(ii), $b_{1,1} = b_{0,3}$. By (\ref{eq5}), we can deduce that $b_{1,3} = b_{1,2}$. So $r_1$ becomes $(b_{1,0}, b_{0,3}, b_{1,2}, b_{1,2})$. According to Lemma~\ref{lem3.3}(iii), $r_2$ satisfies $(b_{2,0}, b_{2,1}, b_{2,2}, b_{2,3}) = (b_{2,2}, b_{2,3}, b_{2,0}, b_{2,1})$ and then it is $(b_{2,0}, b_{2,1}, b_{2,0}, b_{2,1})$.
Moreover, $r_3 = (b_{0,3}, b_{1,2}, b_{1,2}, b_{1,0})$ by a shifting of $r_1$. Thus, by symmetry, we have
$$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} \\ b_{0,1} & b_{0,3} & b_{1,2} & b_{1,2} \\ b_{0,2} & b_{1,2} & b_{0,2} & b_{1,2} \\ b_{0,3} & b_{1,2} & b_{1,2} & b_{0,1} \end{matrix} \right).$$
Suppose that $s(4) = b_{1,2} + b_{3, 2} = 0$. Then $b_{1,2} = 0$ and $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} \\ b_{0,1} & b_{0,3} & 0 & 0 \\ b_{0,2} & 0 & b_{0,2} & 0 \\ b_{0,3} & 0 & 0 & b_{0,1} \end{matrix} \right).$$ By Lemma~\ref{lem3.3}(iv), the sums of $r_0$ and $r_1$ are equal. We obtain $b_{0,0} = 0$. This contradicts to $b_{0,0} > 0$. Thus, $s(4) \neq 0$.

For $\ell = 5$, $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} & b_{0,4} \\ b_{1,0} & b_{1,1} & b_{1,2} & b_{1,3} & b_{1,4} \\ b_{2,0} & b_{2,1} & b_{2,2} & b_{2,3} & b_{2,4} \\ b_{3,0} & b_{3,1} & b_{3,2} & b_{3,3} & b_{3,4} \\ b_{4,0} & b_{4,1} & b_{4,2} & b_{4,3} & b_{4,4} \end{matrix} \right).$$ By Lemma~\ref{lem3.3}(ii), $b_{1,1} = b_{0,4}$ and $b_{2,2} = b_{0,3}$. By (\ref{eq5}), we can deduce that $b_{1,4} = b_{1,2}$ and $b_{2,3} = b_{2,4} = b_{1,3}$.
Thus, $r_1 = (b_{1,0}, b_{0,4}, b_{1,2}, b_{1,3}, b_{1,2})$ and $r_2 = (b_{2,0}, b_{2,1}, b_{0,3}, b_{1,3}, b_{1,3})$. By Lemma~\ref{lem3.3}(iii), $r_3 = (b_{0,3}, b_{1,3}, b_{1,3}, b_{2,0}, b_{2,1}$ and $r_4 = (b_{0,4}, b_{1,2}, b_{1,3}, b_{1,2}, b_{1,0})$ by shifting $r_2$ and $r_1$, respectively. Hence, by symmetry, we have $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} & b_{0,4} \\ b_{0,1} & b_{0,4} & b_{1,2} & b_{1,3} & b_{1,2} \\ b_{0,2} & b_{1,2} & b_{0,3} & b_{1,3} & b_{1,3} \\ b_{0,3} & b_{1,3} & b_{1,3} & b_{0,2} & b_{1,2} \\ b_{0,4} & b_{1,2} & b_{1,3} & b_{1,2} & b_{0,1} \end{matrix} \right).$$ Suppose that $s(5) = b_{1,2} + b_{2,4} + b_{3,1} + b_{4,3} = 0$. Then $b_{1,2} = b_{1,3} = 0$ and we have $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} & b_{0,4} \\ b_{0,1} & b_{0,4} & 0 & 0 & 0 \\ b_{0,2} & 0 & b_{0,3} & 0 & 0 \\ b_{0,3} & 0 & 0 & b_{0,2} & 0 \\ b_{0,4} & 0 & 0 & 0 & b_{01} \end{matrix} \right).$$ By Lemma~\ref{lem3.3}(iv), the sums of $r_0$ and $r_1$ are equal. We obtain $b_{0,0} = 0$, a contradiction. Thus, $s(5) \neq 0$.
\end{proof}

According to Lemma~\ref{lem2.3}, a prime $p$ will satisfy Conjecture~\ref{conjB}, as well as Conjecture~\ref{conjA}, if $s(\ell) \neq 0$. Thus we have the following conclusion on the size of optimal CAC.

\begin{cor}
\label{cor3.9}
Let $p$ be an odd prime such that $4 \nmid o_p(2)$. If $\ell = \left[\zz_p^{\times} : \langle -1, 2 \rangle\right] = 3, 4, 5$, then
the size of optimal conflict-avoiding codes of length $p$ and weight $3$ is $\frac{p-1-2\ell}{4} + 1$.
\end{cor}

Corollary~\ref{cor3.9} is also known in \cite[Corollary~4.8]{MaZhaShe} in a different method.
When $\ell \geq 6$, the above approach is not enough to check whether $s(\ell) \neq 0$. In the next section, we discover more properties on $s(\ell)$.

\section{The number of squares}
\label{sec4}

In the previous section, we have seen that the sum $s(\ell)$ of particular cyclotomic numbers actually answers Conjecture~\ref{conjA} and \ref{conjB} for some $\ell$. In this section, we will see how $s(\ell)$ connects to squares of $\zz_p$ and answer both conjectures for more $\ell$.
First of all, let us back to the equation $1 + b = c$ in Conjecture~\ref{conjB} where $b \in t L$ and $c \in t^2 L$ for $t \in \zz_p^{\times}$ such that $\zz_p^{\times} / L = \langle t L \rangle$. In this case, $(1 + t L) \cap t^2 L$ is nonempty. Write $b = t \beta$ and $c = t^2 \gamma$ for $\beta, \gamma \in L$. It gives $t^2 \gamma - t \beta - 1 = 0$. Viewing the equation as a quadratic polynomial in $t$, the discriminant provides that $\beta^2 + 4 \gamma$ is a square. Equivalently, $1 + 4 \beta^{-2} \gamma$ is a square. Since $2 \in L$, it follows that $1 + 4 \beta^{-2} \gamma$ is a square in $L$. This leads us to think of squares in $1 + L$. In general, if $1 + \alpha$ is a square for $\alpha \in L$, namely $1 + \alpha = (s-1)^2$ for some $s \in \zz_p^{\times}$, then we have $1 + s (2 \alpha^{-1}) = s^2 \alpha^{-1}$ which gives an element of $(1 + s L) \cap s^2 L$ because $2 \alpha^{-1}, \alpha^{-1} \in L$. Note that $s L = g^i L$ for some $0 \leq i \leq \ell-1$ where $g$ is a given primitive root. It follows that $A(i, 2 i) \neq 0$. Consequently, every square of $1 + L$ (if exists) leads to a nonzero cyclotomic number $A(i, 2 i)$ for some $0 \leq i \leq \ell-1$. We will see $A(i, 2 i) \neq 0$ for some $i \neq 0$. It follows that $s(\ell) \neq 0$ when $\ell$ is prime.

Given a primitive root $g$ of $\zz_p$, we generally consider squares in $1 + g^k L$ for $0 \leq k \leq \ell-1$.
Fix $k$ and let $r \in \zz_p$ such that $r^2 \in 1 + g^k L$. Then $r^2 - 1 \in g^k L$. Observe that $r^2 - 1 = (r-1) (r+1)$ and $r \neq \pm 1$ since $0 \not\in g^k L$. Thus, $r-1 \in g^i L$ and $r+1 \in g^j L$ for some $i, j$ satisfying $i + j \equiv k \pmod{\ell}$ as $(g^i L) (g^j L) = g^k L$. In particular, $r \in (1 + g^i L) \cap (-1 + g^j L)$. Conversely, if $r' \in (1 + g^i L) \cap (-1 + g^j L)$ and $i + j \equiv k \pmod{\ell}$, then we have ${r'}^2 \in 1 + g^k L$. Let $$R(i, j) = (1 + g^{i} L) \cap (-1+g^{j} L)$$ for integers $i, j$ and let $S_k$ be the set of squares of $1 + g^k L$. The discussion above provides a surjective map $$\begin{array}{cccc} f_k: & \displaystyle \bigcup_{\substack{0 \leq i, j \leq \ell-1, \\ i + j \equiv k \; (\text{mod } \ell)}} R(i, j) & \to & S_k \\ & r & \mapsto & r^2. \end{array}$$

\begin{lem}
\label{lem3.5}
Let $R(i, j)$ be as above.
\begin{enumerate}
\item[(i)]
For $0 \leq i, i', j, j' \leq \ell-1$, if either $i \neq i'$ or $j \neq j'$, then $R(i, j) \cap R(i', j') = \varnothing$. Thus, the domain of $f_k$ is a disjoint union of $R(i, j)$.
\item[(ii)]
For $i, j$ modulo $\ell$, $|R(i, j)| = A(i, j).$
\end{enumerate}
\end{lem}

\begin{proof}
For (i), when $i \neq i'$, one has $(1 + g^i L) \cap (1 + g^{i'} L) = \varnothing$ because $g^i L \cap g^{i'} L = \varnothing$. Similarly, when $j \neq j'$, one also has $(-1 + g^j L) \cap (-1 + g^{j'} L) = \varnothing$. The result follows.

For (ii), consider the map $$\begin{array}{cccc} \psi : & R(i, j) & \to & (1 + g^i L) \cap g^j L \\ & r & \mapsto & 2^{-1} (1 + r). \end{array}$$ It is easy to see that $\psi$ is injective. For every $s \in (1 + g^i L) \cap g^j L$, $-1 + 2 s \in T(i, j)$ since $2 \in L$. Moreover, $\psi(-1 + 2 s) = s$. Hence, $\psi$ is a bijection and the result follows by the definition of $A(i, j)$.
\end{proof}

The following lemma provides a connection between a particular sum of cyclotomic numbers and the number of squares.

\begin{lem}
\label{lem3.4}
The number of squares of $1 + L$ is $$\frac{1}{2} + \frac{1}{2} \sum_{i = 0}^{\ell-1} A(i, -i).$$ For $1 \leq k \leq \ell-1$, the number of squares of $1 + g^k L$ is $$\frac{1}{2} \sum_{i = 0}^{\ell-1} A(i, k-i).$$
\end{lem}

\begin{proof}
Let $R(i, j)$, $S_k$ and $f_k$ be as above. Note that if $0 \in R(i, j)$, then $0 \in 1 + g^i L$ and $0 \in -1 + g^j L$. As $1, -1 \in L$, we deduce that $0 \in R(i, j)$ if and only if $i = j = 0$. Recall from Lemma~\ref{lem3.5}(i) that the domain of $f_k$ is a disjoint union of $R(i, j)$ for $0 \leq i, j \leq \ell-1$ and $i + j \equiv k \pmod{\ell}$. We discuss into two cases that $i = j$ and $i \neq j$.

Case 1: $i = j$. Clearly, we have $R(i, i) = - R(i, i)$. Moreover, $f_k(r) = r^2 = f_k(-r)$. Thus, the restriction of $f_k$ to $R(i,i) \setminus \{0\}$ is two-to-one. If $0 \in R(i, i)$, then $i = 0$ and this holds only for $k = 0$. So the image of $R(i, i)$ under $f_0$ has the size $\frac{1}{2} + \frac{1}{2} A(0,0)$ if $i = 0$ and the size $\frac{1}{2} A(i, i)$ if $i \neq 0$. For $k = 1, \ldots, \ell-1$, the image of $R(i, i)$ under $f_k$ has the size $\frac{1}{2} A(i, i)$.

Case 2: $i \neq j$. In this case, $R(i, j) \neq R(j, i)$ and $R(j, i) = - R(i, j)$. Thus, the restriction of $f_k$ to $R(i, j) \cup R(j, i)$ is also two-to-one. It follows that the image of $R(i, j) \cup R(j, i)$ under $f_k$ has the size $\frac{1}{2} (A(i, j) + A(j, i))$.

Since $f_k$ is surjective, Case~1 and 2 lead to $$|S_0| = \frac{1}{2} + \frac{1}{2} \sum_{\substack{0 \leq i, j \leq \ell-1, \\ i + j \equiv 0 \; (\text{mod } \ell)}} A(i, j) \quad \text{and} \quad |S_k| = \frac{1}{2} \sum_{\substack{0 \leq i, j \leq \ell-1, \\ i + j \equiv k \; (\text{mod } \ell)}} A(i, j)$$ for $k = 1, \ldots, \ell-1$. Finally, each $i$ leads to a unique $j$ such that $j \equiv k - i \pmod{\ell}$. The proof is completed.
\end{proof}

\begin{exmp}
Let $p = 31$. Then $L = \{\pm 1, \pm 2, \pm 2^2, \pm 2^3, \pm 2^4\}$ and $\ell = 3$. Choose $g = 3$ a primitive root. Then the sets $S_k$ of squares of $1 + g^k L$ are as follows: $$S_0 = \{0, 2, 5, 9, 16, 28\}, \quad S_1 = \{4, 7, 8, 18, 20, 25\}, \quad S_2 = \{10, 14, 19\}.$$ On the other hand, the cyclotomic matrix (Section~\ref{sec3}) is $$\left( \begin{matrix} A(0,0) & A(0,1) & A(0,2) \\ A(1,0) & A(1,1) & A(1,2) \\ A(2,0) & A(2,1) & A(2,2) \end{matrix} \right) = \left( \begin{matrix} 3 & 4 & 2 \\ 4 & 2 & 4 \\ 2 & 4 & 4 \end{matrix} \right).$$ Indeed, $|S_0| = \frac{1}{2} + \frac{1}{2} (A(0,0) + A(1,2) + A(2, 1))$, $|S_1| = \frac{1}{2} (A(0,1) + A(1,0) + A(2,2))$ and $|S_2| = \frac{1}{2} (A(0,2) + A(1,1) + A(2, 0))$.
\end{exmp}

Let us concentrate on $1 + L$. According to Lemma~\ref{lem4.1}, $A(i, - i) = A(-i, i) = A(i, 2 i)$. Thus, the number of squares of $1 + L$ is also $$\frac{1}{2} + \frac{1}{2} \sum_{i = 0}^{\ell-1} A(i, 2i).$$ Recall that $$s(\ell) = \sum_{\substack{1 \leq i \leq \ell, \\ (i, \ell) = 1}} A(i, 2i).$$ We have the following conclusion.

\begin{prop}
\label{prop4.2}
If $\ell$ is an odd prime, then the number of squares of $1 + L$ is $\frac{1}{2} (1 + A(0, 0) + s(\ell))$.
\end{prop}

Note that $1 + L$ contains at least one square, says $0$. When $\ell$ is an odd prime, Proposition~\ref{prop4.2} provides that we will have $s(\ell) \neq 0$ if $A(0, 0)$ is small enough compared to the number of squares of $1 + L$. Let us see an example below.

\begin{exmp}
\label{exmp4.1}
Let $p = 331$. Then $|L| = 30$ and $\ell = 11$. One can check that $A(0,0) = |(1+L) \cap L| = 5$. Thus, $1 + L$ has $3 + \frac{s(11)}{2}$ squares by Proposition~\ref{prop4.2}. Note that $1 + L$ contains at least $4$ squares such as $0$, $1 + 4 = 233^2$, $1-4 = 63^2$ and $1+8 = 3^2$. We have $s(11) \neq 0$.
Indeed, if we pick a primitive root $g = 3$, then one can compute $A(1, 2) = 3$. This also illustrates $s(11) \neq 0$ since it is independent on the choices of primitive roots by Lemma~\ref{prop2.1}.
\end{exmp}

We now focus on $A(0,0)$ and the number of squares of $1 + L$. In \cite{BetHirKomMun}, the authors study upper bounds of cyclotomic numbers. They determine $A(i, j)$ by computing the rank of certain matrix with entries in $\zz_p$. Estimating the rank provides an upper bound of $A(i, j)$ for general $\ell$. We use their result for $A(0, 0)$ below.

\begin{lem}[{\cite[Theorem~1.1(iii)]{BetHirKomMun}}]
\label{lem4.2}
If $\ell \geq 3$, then $$A(0, 0) \leq \left\lceil \frac{p-1}{2 \ell} \right\rceil - 1$$ where $\lceil \cdot \rceil$ denotes the smallest integer larger than or equal to a given number.
\end{lem}

In our situation, $\frac{p-1}{\ell} = |L|$ and $|L|$ is even as $-1 \in L$. Thus, Lemma~\ref{lem4.2} implies $$A(0,0) \leq \frac{|L|}{2} - 1.$$

We study the number of squares of $1 + L$ in a different way from cyclotomic numbers. Denote $\left( \frac{\cdot}{p} \right)$ the {\it Legendre symbol} by $$\left( \frac{x}{p} \right) = x^{\frac{p-1}{2}} = \left\{ \begin{array}{cl} 0 & \text{if } x = 0; \\ 1 & \text{if $x \neq 0$ is a square}; \\ -1 & \text{if $x \neq 0$ is not a square,} \end{array}\right.$$ for $x \in \zz_p$. Then $x$ is a square in $\zz_p$ if and only if $\left( \frac{x}{p} \right) = 0, 1$. Thus, for every $x, y \in \zz_p$, the collection $\{x, y, x y\}$ must contain at least one square because of the multiplication $$\left( \frac{x}{p} \right) \cdot \left( \frac{y}{p} \right) = \left( \frac{x y}{p} \right)$$ holds (see also \cite[Chapter~9]{Bur}). We have the following conclusion.

\begin{lem}
\label{lem4.3}
If $x, y \in \zz_p$ and $x y \neq 0$, then $$\frac{1}{2}\left(1 + \left( \frac{x}{p} \right) \right) + \frac{1}{2} \left( 1 + \left( \frac{y}{p} \right) \right) + \frac{1}{2} \left( 1 + \left( \frac{x y}{p} \right) \right) \geq 1.$$
\end{lem}

We have a lower bound of the number of squares of $1 + L$ as follows.

\begin{lem}
\label{lem4.4}
The number of squares of $1 + L$ is greater than $\frac{1}{4} |L|$.
\end{lem}

\begin{proof
Let $m = |1+L| = |L|$ and let $\alpha$ be a generator of $L$. The integer $m$ is even because $-1 \in L$. Moreover, $\alpha^{\frac{m}{2}} = -1$. Denote $M$ the number of squares of $1 + L$. Then $$M = 1 + \sum_{\substack{i=0, \\ i \neq \frac{m}{2}}}^{m-1} \frac{1}{2} \left( 1 + \left( \frac{1+\alpha^{i}}{p} \right) \right)$$ where the starting $1$ corresponds to $1 + \alpha^{\frac{m}{2}} = 0$. Since $-1 \in L$, $1 + L = 1 - L$ and we also have $$M = 1 + \sum_{i = 1}^{m-1} \frac{1}{2} \left( 1 + \left( \frac{1-\alpha^{i}}{p} \right) \right)$$ where the starting $1$ corresponds to $1 - \alpha^{0} = 0$.

For every $i = 0, 1, \ldots, m-1$, the collection $\{1 + \alpha^i, 1 - \alpha^i, 1 - \alpha^{2 i}\}$ must contain at least one square since $(1 + \alpha^i) (1 - \alpha^i) = 1 - \alpha^{2 i}$. By Lemma~\ref{lem4.3}, $$\sum_{\substack{i=1, \\ i \neq \frac{m}{2}}}^{m-1} \frac{1}{2} \left( 1 + \left( \frac{1+\alpha^i}{p} \right) \right) + \frac{1}{2} \left( 1 + \left( \frac{1-\alpha^{i}}{p} \right) \right) + \frac{1}{2} \left( 1 + \left( \frac{1-\alpha^{2i}}{p} \right)\right) \geq m-2.$$ The first two sums of $\frac{1}{2} \left( 1 + \left( \frac{1+\alpha^i}{p} \right) \right)$ and $\frac{1}{2} \left( 1 + \left( \frac{1-\alpha^i}{p} \right) \right)$ are partial sums of $M-1$ with nonnegative terms. It follows that $2 (M-1) + M'\geq m-2$ where $$M' = \sum_{\substack{i=1, \\ i \neq \frac{m}{2}}}^{m-1} \frac{1}{2} \left( 1 + \left( \frac{1-\alpha^{2i}}{p} \right) \right).$$ Observe that $\alpha^{2 i} = \alpha^{2 (\frac{m}{2} + i)}$ for $i = 1, \ldots, \frac{m}{2} - 1$. Thus, $$M' = 2 \sum_{i = 1}^{\frac{m}{2} - 1} \frac{1}{2} \left( 1 + \left( \frac{1-\alpha^{2i}}{p} \right) \right).$$ The set $\{1 - \alpha^{2i} \mid i = 1, \ldots, \frac{m}{2} - 1\}$ is a subset of $1 - L$ and then $\frac{M'}{2}$ is a partial sum of $M-1$. We obtain $M' \leq 2 (M-1)$.
As a consequence, we have $4 (M-1) \geq m-2$. Hence, $M \geq \frac{m}{4} + \frac{1}{2}$, as desired.
\end{proof}

Now we can prove the main theorem below.

\begin{thm}
\label{thm3.2}
Let $p$ be an odd prime. If $\ell = [\zz_p^{\times} : \langle -1, 2 \rangle]$ is an odd prime, then $s(\ell) \neq 0$.
\end{thm}

\begin{proof}
According to Proposition~\ref{prop4.2}, the number of squares of $1 + L$ is $\frac{1}{2} (1 + A(0,0) + s(\ell))$. By Lemma~\ref{lem4.4}, this number is greater than $\frac{1}{4} |L|$ and then $1 + A(0,0) + s(\ell) > \frac{1}{2} |L|$. From the below of Lemma~\ref{lem4.2}, $1 + A(0,0) \leq \frac{1}{2} |L|$. Therefore, $s(\ell) > 0$.
\end{proof}

Theorem~\ref{thm3.2} provides the positivity of Conjecture~\ref{conjB} for primes $p$ such that $[\zz_p^{\times} : \langle -1, 2 \rangle]$ is a prime. This also answers Conjecture~\ref{conjA} for such primes. Thus we have the following consequence.

\begin{cor}
\label{cor3.8}
Let $p$ be an odd prime such that $4 \nmid o_p(2)$. If $\ell = [\zz_p^{\times} : \langle -1, 2 \rangle]$ is an odd prime, then the optimal conflict-avoiding codes of length $p$ and weight $3$ has the size $$\frac{p-1-2 \ell}{4} + \left\lfloor \frac{\ell}{3} \right\rfloor.$$
\end{cor}

For example, if $p = 1229241823 > 2^{30}$, then $o_p(2)$ is odd and $\ell = 18307$ is a prime. Thus, we can easily conclude that the size of optimal conflict-avoiding codes of length $p$ and weight $3$ is $307307404$. Indeed, one can check that $A(1, 2) = 4$ with the primitive root $3$. One element of $(1 + 3L) \cap 9L$ is $1 + 3 \cdot 2^{1128543547} = 9 \cdot 2^{249779730}$.

An optimal CAC of length $p^k$, $k \geq 1$, can be constructed from an optimal CAC of length $p$ by \cite[Theorem~8]{FuLoShu}. Applying Corollary~\ref{cor3.8} to \cite[Theorem~8]{FuLoShu}, we obtain the following conclusion.

\begin{cor}
\label{cor4.2}
Let $p > 3$ be a non-Wieferich prime such that $4 \nmid o_p(2)$. If $\ell = [\zz_p^{\times} : \langle -1, 2 \rangle]$ is an odd prime, then an optimal conflict-avoiding code of length $p^k$ and weight $3$ has the size $$\frac{p^k - 1 - 2 k \ell}{4} + k \left\lfloor \frac{\ell}{3} \right\rfloor$$ for every $k \in \nn$.
\end{cor}

\section{Conclusion Remark}

According to Corollary~\ref{cor3.9} and \ref{cor3.8}, we now know the size of optimal CAC of prime length $p$ and weight $3$ where $4 \nmid o_p(2)$ and either $\ell = \left[\zz_p^{\times} : \langle -1, 2 \rangle \right] = 4$ or $\ell$ is an odd prime.
For composite number $\ell \geq 6$, it is not easy to determine whether $s(\ell) \neq 0$ or not. For example, let $\ell = 6$ and using properties given in Section~\ref{sec3}, the extended cyclotomic matrix can be simplified such as $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} & b_{0,4} & b_{0,5} \\ b_{0,1} & b_{0,5} & b_{1,2} & b_{1,3} & b_{1,4} & b_{1,2} \\ b_{0,2} & b_{1,2} & b_{0,4} & b_{1,4} & b_{2,4} & b_{1,3} \\ b_{0,3} & b_{1,3} & b_{1,4} & b_{0,3} & b_{1,3} & b_{1,4} \\ b_{0,4} & b_{1,4} & b_{2,4} & b_{1,3} & b_{0,2} & b_{1,2} \\ b_{0,5} & b_{1,2} & b_{1,3} & b_{1,4} & b_{1,2} & b_{0,1} \end{matrix} \right).$$ Suppose that $s(6) = b_{1,2} + b_{5, 4} = 0$. Then $$B = \left( \begin{matrix} b_{0,0} & b_{0,1} & b_{0,2} & b_{0,3} & b_{0,4} & b_{0,5} \\ b_{0,1} & b_{0,5} & 0 & b_{1,3} & b_{1,4} & 0 \\ b_{0,2} & 0 & b_{0,4} & b_{1,4} & b_{2,4} & b_{1,3} \\ b_{0,3} & b_{1,3} & b_{1,4} & b_{0,3} & b_{1,3} & b_{1,4} \\ b_{0,4} & b_{1,4} & b_{2,4} & b_{1,3} & b_{0,2} & 0 \\ b_{0,5} & 0 & b_{1,3} & b_{1,4} & 0 & b_{0,1} \end{matrix} \right).$$ By Lemma~\ref{lem3.3}(iv), we will obtain that $$\left\{ \begin{array}{l} b_{0,0} + b_{0,2} + b_{0,3} + b_{0,4} = b_{1,3} + b_{1,4}, \\ b_{0,1} + b_{0,5} = b_{0,2} + b_{0,4} + b_{2,4} = 2 b_{0,3} + b_{1,3} + b_{1,4}, \\ b_{0,3} + b_{1,3} + b_{1,4} = \frac{|L|}{2}. \end{array} \right.$$ This gives the equality $$b_{2,4} = b_{0,0} + 3 b_{0,3}.$$
On the other hand, according to Lemma~\ref{lem3.4}, the number of squares of $1 + L$ is $$\frac{1}{2} (b_{0,0} + b_{0,3} + 2b_{2,4}).$$ By Lemma~\ref{lem4.4}, this number is greater than $\frac{1}{4} |L|$ and then $b_{0,0} + b_{0,3} + 2 b_{2,4} > \frac{1}{2} |L|$. Using the equality above, we obtain $3 b_{0,0} + 7 b_{0, 3} > \frac{1}{2} |L|$. However, the upper bound for $b_{0,0}$ given in Lemma~\ref{lem4.3} (or for $b_{0, 3}$ given in \cite{BetHirKomMun}) can not give further information in this case. For composite numbers $\ell \geq 6$, we think that finding smaller upper bounds for cyclotomic numbers may lead to a better approach.
We hope that these ideas could give some inspiration for doing this problem.

\section*{Acknowledgment}

We would like to thank Professor Yuan-Hsun Lo for bringing \cite{FuLoShu} to our attention.
The first named author is partially supported by MOST grant 110-2115-M-003-007-MY2.
The second named author is partially supported by MOST grant 111-2115-M-003-005.
The third named author is supported MOST grant 111-2811-M-003-028.

\bibliographystyle{alphaurl}
\input{CAC_Cyclotomic.bbl}

\end{document}