# Search for anisotropic, birefringent spacetime-symmetry breaking in
gravitational wave propagation from GWTC-3

Leïla Haegel<EMAIL_ADDRESS>Université Paris Cité, CNRS,
Astroparticule et Cosmologie, F-75013 Paris, France  Kellie O’Neal-Ault
<EMAIL_ADDRESS>Embry-Riddle Aeronautical University, Prescott, AZ, 86301,
USA  Quentin G. Bailey<EMAIL_ADDRESS>Embry-Riddle Aeronautical University,
Prescott, AZ, 86301, USA  Jay D. Tasson  Carleton College, Northfield, MN
55057, USA  Malachy Bloom  Carleton College, Northfield, MN 55057, USA  Lijing
Shao  Kavli Institute for Astronomy and Astrophysics, Peking University,
Beijing 100871, China
National Astronomical Observatories, Chinese Academy of Sciences, Beijing
100012, China

###### Abstract

An effective field theory framework, the Standard-Model Extension, is used to
investigate the existence of Lorentz and CPT-violating effects during
gravitational wave propagation. We implement a modified equation for the
dispersion of gravitational waves, that includes isotropic, anisotropic and
birefringent dispersion. Using the LIGO-Virgo-KAGRA algorithm library suite,
we perform a joint Bayesian inference of the source parameters and
coefficients for spacetime symmetry breaking. From a sample of 45 high
confidence events selected in the GWTC-3 catalog, we obtain a maximal bound of
$3.19\times 10^{-15}$ m at 90% CI for the isotropic coefficient
$k_{(V)00}^{(5)}$ when assuming the anisotropic coefficients to be zero. The
combined measurement of all the dispersion parameters yields limits on the
order of $10^{-13}$ m for the 16 $k_{(V)ij}^{(5)}$ coefficients. We study the
robustness of our inference by comparing the constraints obtained with
different waveform models, and find that a lack of physics in the simulated
waveform may appear as spacetime symmetry breaking-induced dispersion for a
subset of events.

Lorentz invariance violation, CPT symmetry breaking, spacetime birefringence,
gravitational waves, gravity

††preprint: APS/123-QED

##  I Introduction

In the search for a fundamental unified theory of physics, it may be
imperative to reconsider the axioms underlying General Relativity (GR)and the
Standard Model (SM)of particle physics. Many theoretical proposals argue for a
possible breaking of spacetime symmetries, including Lorentz invariance
(LI)and Charge-Parity-Time (CPT)symmetry [1, 2, 3, 4, 5, 6], in such a way
that it may be detectable in sensitive tests. The direct detections of
gravitational waves (GWs)reported by the LIGO-Virgo-KAGRA (LVK)collaboration
provide a new channel to test the rich phenomenology induced by spacetime-
symmetry breaking in the gravitation sector [7, 8, 9, 10, 11].

The effective field theory referred to as the Standard-Model Extension (SME)is
a theoretical framework dedicated to derive the observable consequences of
spacetime-symmetry breaking that is punctilious and model independent. The
framework is comprised of the action of GR and the SM plus all possible terms
obtainable from GR and SM field operators contracted with coefficients for
spacetime-symmetry breaking, including local Lorentz, CPT, and diffeomorphism
breaking terms [12, 13, 14, 15, 16, 17, 18, 19, 20, 21]. Extensive constraints
have been derived on these terms within the matter sector and in the gravity
sector [22], the latter having been studied with a wide range of astrophysical
probes [15, 19, 20, 23, 24, 25]. Existing analysis includes short-range
gravity tests [26, 27, 28], gravimetry tests [29, 30, 31, 32, 33, 34, 35],
astrophysical tests with pulsars [36, 37, 38], solar system planetary tests
[39, 40, 41], near-Earth tests [42, 43, 44, 45], and tests with GWs [46, 19,
47, 48, 49, 50, 51]. We complement those searches with further study of the LI
and CPT-violating effects on propagation of GW. We use dynamical equations for
the metric fluctuations derived from the action of the SME, and the resulting
effects include dispersion, anisotropy, and birefringence.

Several tests of GR have been performed with the GW events detected by the LVK
[47, 48, 52, 49, 50, 53, 54]. Some related works focus on parameterizations of
the deviations from GR [9, 10, 55, 56], including waveform consistency tests,
modification of the GW generation, presence of extra polarization modes, and
tests using specific models [57, 58, 59, 60, 61, 55, 62]. The current searches
for LI violation performed by the LVK collaboration notably rely on a modified
dispersion relation that includes isotropic and polarization-independent
effects [53, 63, 64]. Using the SME framework, we extend this phenomenology by
measuring the coefficients for LI and CPT violation, including anisotropic and
polarization-dependent dispersion. First estimates of those coefficients have
been derived using posterior probabilities released with previous GW catalog
releases, effectively neglecting the correlations between the parameters
describing the source and the spacetime-symmetry breaking coefficients [49,
50]. In this article, we present a joint measurement of the source parameters
and the coefficients, alongside studying the robustness of the results we
obtain.

Section II summarizes the derivation of the phenomenology induced by LI and
CPT violation in the SME framework. Section III details the methodological
aspects, including the dataset used for the measurement of the spacetime-
symmetry breaking coefficients. Section IV presents the obtained results, as
well as a discussion of the impact of the underlying gravitational waveform
model and correlations with source parameters. Section V discusses those
results in light of existing studies and future GW instrument sensitivities.
Theoretical portions of this paper work with natural units, where $\hbar=c=1$
and Newton’s gravitational constant is $G_{N}\neq 1$, while our data analysis
work follows SI units. Greek letters are used for spacetime indices while
Latin letters for spatial indices. We work with the spacetime metric signature
$(-,+,+,+)$.

##  II Theoretical derivation of a dispersion relation for gravitational waves

We summarize previous derivations in [19, 65, 66], focusing on gravity-sector
terms within the SME framework. The spacetime metric is expanded as
fluctuations about the Minkowski metric,
$g_{\mu\nu}=h_{\mu\nu}+\eta_{\mu\nu}$, and we consider up to second order in
$h_{\mu\nu}$ for the action, which is sufficient to characterize propagation
effects. This gives the following action:

$I={\textstyle{{1}\over{8\kappa}}}\int
d^{4}x\,h_{\mu\nu}\hat{K}^{(d)\mu\nu\rho\sigma}h_{\rho\sigma}.$ (1)

The operator $\hat{K}^{(d)\mu\nu\rho\sigma}$, consists of partial derivatives
that act on $h_{\mu\nu}$,

$\hat{K}^{(d)\mu\nu\rho\sigma}=K^{(d)\mu\nu\rho\sigma\epsilon_{1}...\epsilon_{d-2}}\partial_{\epsilon_{1}}...\partial_{\epsilon_{d-2}},$
(2)

and $K^{(d)\mu\nu\rho\sigma\epsilon_{1}...\epsilon_{d-2}}$ are general
background coefficients that are considered small, constant and control the
size of any Lorentz or CPT violation;

Ensuring linearized gauge symmetry, i.e., $h_{\mu\nu}\rightarrow
h_{\mu\nu}+\partial_{\mu}\xi_{\nu}+\partial_{\nu}\xi_{\mu}$, and retaining
only terms that contribute to the resulting field equations, we arrive at the
following Lagrange density [19]:

$\displaystyle{\cal L}$ $\displaystyle=$
$\displaystyle{\textstyle{{1}\over{8\kappa}}}\epsilon^{\mu\rho\alpha\kappa}\epsilon^{\nu\sigma\beta\lambda}\eta_{\kappa\lambda}h_{\mu\nu}\partial_{\alpha}\partial_{\beta}h_{\rho\sigma}$
(3)
$\displaystyle+{\textstyle{{1}\over{8\kappa}}}h_{\mu\nu}(\hat{s}^{\mu\rho\nu\sigma}+\hat{q}^{\mu\rho\nu\sigma}+\hat{k}^{\mu\rho\nu\sigma})h_{\rho\sigma}.$

The first term is the standard GR term written with the totally antisymmetric
Levi-Civita tensor density $\epsilon^{\mu\rho\alpha\kappa}$, and the remaining
terms contain all additional Lorentz invariant and violating terms, organized
into three terms based on symmetry properties: $\hat{s}$ is CPT even with mass
dimension $d\geq 4$; $\hat{q}$ is CPT odd with mass dimension $d\geq 5$;
$\hat{k}$ is CPT even with mass dimension $d\geq 6$. Details of these terms
including the corresponding Young Tableaux can be found in Table 1 of Ref.
[19]. As an example, for mass dimension $5$,

$\hat{q}^{\mu\rho\nu\sigma}=q^{(5)\mu\rho\epsilon\nu\zeta\sigma\kappa}\partial_{\epsilon}\partial_{\zeta}\partial_{\kappa},$
(4)

where $q^{(5)\mu\rho\epsilon\nu\zeta\sigma\kappa}$ has $60$ independent
components. Note that the gauge symmetry requirement can be relaxed [20, 67],
but we do not consider such terms here. The origin of the effective action for
$h_{\mu\nu}$ resulted from explicit symmetry breaking or spontaneous-symmetry
breaking as discussed elsewhere [15, 68, 19, 69].

Performing the variation with respect to $h_{\mu\nu}$ on the action (3),
results in the vacuum field equations,

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\,G^{\mu\nu}\,-[{\textstyle{{1}\over{4}}}(\hat{s}^{\mu\rho\nu\sigma}+\hat{s}^{\mu\sigma\nu\rho})+{\textstyle{{1}\over{2}}}\hat{k}^{\mu\nu\rho\sigma}$
(5)
$\displaystyle+{\textstyle{{1}\over{8}}}(\hat{q}^{\mu\rho\nu\sigma}+\hat{q}^{\nu\rho\mu\sigma}+\hat{q}^{\mu\sigma\nu\rho}+\hat{q}^{\nu\sigma\mu\rho})]\,h_{\rho\sigma}.$

Assuming plane wave solutions,
$\bar{h}_{\mu\nu}=A_{\mu\nu}e^{-ip_{\alpha}x^{\alpha}}$, where $x^{\mu}$ is
spacetime position and $p^{\mu}=(\omega,\vec{p})$ is the four-momentum for the
plane wave, and transforming into momentum space with
$\partial_{\alpha}=-ip_{\alpha}$ the dispersion relation can be obtained
independently of gauge conditions, as shown in references [70, 20]. The
dispersion relation for the two propagating modes is given by

$\omega=|\vec{p}|\,\left(1-\zeta^{0}\pm|\vec{\zeta}|\right),$ (6)

where

$|\vec{\zeta}|=\sqrt{(\zeta^{1})^{2}+(\zeta^{2})^{2}+(\zeta^{3})^{2}}$ (7)

and

$\displaystyle\zeta^{0}$ $\displaystyle=$
$\displaystyle{\textstyle{{1}\over{4|{\vec{p}}|^{2}}}}\left(-\hat{s}^{\mu\nu}\,_{\mu\nu}+{\textstyle{{1}\over{2}}}\hat{k}^{\mu\nu}\,_{\mu\nu}\right),$
$\displaystyle(\zeta^{1})^{2}+(\zeta^{2})^{2}$ $\displaystyle=$
$\displaystyle{\textstyle{{1}\over{8|{\vec{p}}|^{4}}}}\left(\hat{k}^{\mu\nu\rho\sigma}\hat{k}_{\mu\nu\rho\sigma}-\hat{k}^{\mu\rho}\,_{\nu\rho}\,\hat{k}_{\mu\sigma}\,^{\nu\sigma}\right.$
$\displaystyle\left.\hskip
75.0pt+{\textstyle{{1}\over{8}}}\hat{k}^{\mu\nu}\,_{\mu\nu}\,\hat{k}^{\rho\sigma}\,_{\rho\sigma}\right),$
$\displaystyle(\zeta^{3})^{2}$ $\displaystyle=$
$\displaystyle{\textstyle{{1}\over{16|{\vec{p}}|^{4}}}}\left(-{\textstyle{{1}\over{2}}}\hat{q}^{\mu\rho\nu\sigma}\,\hat{q}_{\mu\rho\nu\sigma}-\hat{q}^{\mu\nu\rho\sigma}\,\hat{q}_{\mu\nu\rho\sigma}\right.$
(8) $\displaystyle\hskip
40.0pt\left.+(\hat{q}^{\mu\rho\nu}\,_{\rho}+\hat{q}^{\nu\rho\mu}\,_{\rho})\hat{q}_{\mu\sigma\nu}\,^{\sigma}\right).$

We retrieve the GR case when symmetry-breaking coefficients, i.e. $\zeta^{0}$
and $|\vec{\zeta}|$, vanish. Note that this result holds at leading order in
the coefficients for Lorentz violation, hence higher modes do not contribute
in this perturbative treatment [70, 20]. Relaxing some of the assumptions in
this framework, allowing for other fields to contribute dynamically to the
action, could result in additional modes [71, 72].

GR predicts two linearly independent polarizations for GWs propagating in
vacuum, traveling at the speed of light. Possible modifications for observable
Lorentz and CPT violating effects from (6) include birefringence, e.g.,
altered relative travel speeds between the polarizations, which result from
the two possible signs for $|\vec{\zeta}|$ in (6), requiring a minimum mass
dimension $5$. Furthermore, the presence of higher powers of frequency and
momentum in the terms above, indicates beyond GR dispersion as well. All of
these effects depend on the sky location of the propagating wave, and thus a
breaking of rotational isotropy occurs.

To take into account the sky localization dependence of the source in the
detector frame, it is advantageous to project the SME coefficients onto
spherical harmonics [70],

$\displaystyle\zeta^{0}$ $\displaystyle=$
$\displaystyle\sum\limits_{djm}\omega^{d-4}\,Y_{jm}(\hat{\textbf{n}})\,k^{(d)}_{(I)jm},$
(9) $\displaystyle\zeta^{1}\mp i\,\zeta^{2}$ $\displaystyle=$
$\displaystyle\sum\limits_{djm}\omega^{d-4}\,_{\pm
4}Y_{jm}(\hat{\textbf{n}})\left(k^{(d)}_{(E)jm}\pm ik^{(d)}_{(B)jm}\right),$
(10) $\displaystyle\zeta^{3}$ $\displaystyle=$
$\displaystyle\sum\limits_{djm}\omega^{d-4}\,Y_{jm}(\hat{\textbf{n}})\,k^{(d)}_{(V)jm},$
(11)

where $-j\leq m\leq j$, the $Y_{jm}(\hat{\textbf{n}})$ are the standard
spherical harmonics while ${}_{\pm 4}Y_{jm}(\hat{\textbf{n}})$ are spin-
weighted spherical harmonics, and ${\hat{n}}=-{\hat{p}}$.

Expressions for the two linearly independent GW polarizations, in the
transverse-traceless gauge, result in a phase shift from the additional
symmetry-breaking effects,

$\displaystyle h_{(+)}$ $\displaystyle=$ $\displaystyle
e^{i\delta}(\cos\beta-i\sin\vartheta\cos\varphi\sin\beta)\,h^{LI}_{(+)}$
$\displaystyle-e^{i\delta}\sin\beta(\cos\vartheta+i\sin\vartheta\sin\varphi)\,h^{LI}_{(\times)}$
$\displaystyle h_{(\times)}$ $\displaystyle=$ $\displaystyle
e^{i\delta}(\cos\beta+i\sin\vartheta\cos\varphi\sin\beta)\,h^{LI}_{(\times)}$
(12)
$\displaystyle+e^{i\delta}\sin\beta(\cos\vartheta-i\sin\vartheta\sin\varphi)\,h^{LI}_{(+)}.$

where

$\displaystyle\delta$ $\displaystyle=\omega^{d-3}\tau\zeta^{(d)0},$
$\displaystyle\beta$ $\displaystyle=\omega^{d-3}\tau|\vec{\zeta}^{(d)}|,$

and the modified redshift becomes

$\tau=\int_{0}^{z}dz{{(1+z)^{d-4}}\over{H(z)}}.$ (13)

For notational convenience, the angles in (12) are defined by the expressions
below,

$\sin\,\vartheta={\textstyle{{|\zeta^{1}\mp
i\zeta^{2}|}\over{|\vec{\zeta}|}}},\phantom{30}\cos\vartheta={\textstyle{{\zeta^{3}}\over{|\vec{\zeta}|}}},\phantom{30}e^{\mp
i\varphi}={\textstyle{{\zeta^{1}\mp
i\zeta^{2}}\over{\sqrt{(\zeta^{1})^{2}+(\zeta^{2})^{2}}}}}.$ (14)

One of the key features of spacetime symmetry breaking, as evidenced in the
equations above, is the breaking of isotropy. The strength of the LI violation
can change with source location [66]. Unless otherwise stated, the spherical
coefficients in (9)-(11) are expressed in the Sun-Centered Celestial
Equatorial reference frame (SCF), as is standard in the literature [73, 22],
and allows comparisons with other non-GW tests in the gravity sector.
Rotations and boosts of the spherical coefficients relative to this frame must
be taken into account, as discussed elsewhere [74].

##  III Data and parameter inference

###  III.1 Bayesian inference of source and symmetry-breaking parameters

For mass dimension $4$, LI violation leads to a modification of the GW group
velocity that can be measured with multimessenger signals; constraints on the
$\hat{s}$ operator of Eq. (3) have been obtained from the observation of
GW170817/GRB170817A [47] comparing light and GW travel time, and travel time
across the Earth [48].

In this analysis, we focus on the coefficients for Lorentz and CPT violation
contained in the operator $\hat{q}$ for $d=5$ (see Eq (5)), with the first
mass dimension in the action series (3) where GW dispersion occurs. We probe
the impact of isotropic and anisotropic dispersion, as well as birefringence,
with a joint estimation of the source parameters and the $16$ a priori
independent $k_{(V)ij}^{(5)}$ coefficients of Eq. (11). Specifically, we are
considering in this work, a subset of (12), where $\delta=0$. In this case the
remaining coefficients are contained in $\beta$. The expression is lengthy but
takes the form [66]:

$\displaystyle\beta^{(5)}$ $\displaystyle=$
$\displaystyle{\textstyle{{\omega^{2}\tau^{(5)}}\over{2\sqrt{\pi}}}}\,\bigl{\lvert}k^{(5)}_{(V)00}-\sqrt{{\textstyle{{3}\over{2}}}}\sin\theta\left(e^{i\phi}\,k^{(5)}_{(V)11}+e^{-i\phi}\,k^{(5)*}_{(V)11}\right)$
(15) $\displaystyle+\sqrt{3}\cos\theta\,k^{(5)}_{(V)10}+...\bigr{\rvert},$

with the superscript $(5)$ meaning all quantities are evaluated with $d=5$
like equation (13).

Using a Bayesian inference framework, we compare the strain detected by the
LVK interferometers with a template bank of gravitational waveforms modified
as outlined in Eq. (12). The strain takes the form,

$S_{A}=F_{(+)}h_{(+)}+F_{(\times)}h_{(\times)},$ (16)

where $h_{(+,\times)}$ are the expressions (12), and $F_{(+,\times)}$ are the
standard detector response functions. The rotation angles relating different
frames, are included in the expressions for $F_{(+,\times)}$. These are
defined in the LALSuite software, including the source frame and the detector
frame. Again, the coefficients $k_{(V)ij}^{(5)}$ in (15) are left in the SCF.

We use the LALSuite algorithm package, modifying the LALSimulation subpackage
to generate dispersed waveforms and performing the parameter estimation with a
custom version of LALInference [75]. For a single event, LALInference
evaluates the posterior probability with a Markov chain process using the
matched-filtered likelihood:

$\displaystyle
P(d|\vec{\theta}_{GR},\vec{\theta}_{SME},I)=\exp\bigg{(}\sum_{i}$
$\displaystyle-{\textstyle{{2|\tilde{d}_{i}-\tilde{h}_{i}(\vec{\theta}_{GR},\vec{\theta}_{SME})|^{2}}\over{TS_{n}(f_{i})}}}$
(17) $\displaystyle-{\textstyle{{1}\over{2}}}\log\left({\textstyle{{\pi
TS_{n}(f_{i})}\over{2}}}\right)\bigg{)}$

where $\tilde{h}_{i}$ is the template signal, $\tilde{d}_{i}$ is the
interferometer datastream, $T$ is the duration of the signal, and $S_{n}$ the
power spectral density (PSD)of the detector noise. Included in the vector set
of GR prior parameters $\vec{\theta}_{GR}$, are the intrinsic parameters
describing the binary system (e.g. the masses and spins), as well as the
(extrinsic) astrophysical environment parameters (e.g. the sky location,
distance, inclination). The additional parameters $\vec{\theta}_{SME}$,
contain the SME coefficients $k^{(5)}_{(V)jm}$.

The analysis is performed in the frequency domain, as detailed in [66]. The
configurations of the Bayesian inferences, including the Markov chain
algorithms and parameters, PSD and calibration envelops, are the same as the
ones used by the LVK collaboration for parameter estimation. They are
retrieved with the PESummary package [76], selecting the options associated
with the IMRPhenomPv2 waveform model [77].

For each GW event, we first measure the isotropic dispersion coefficient
$|k_{(V)00}^{(5)}|$, by taking a limiting case of (15) where we temporarily
ignore the sky angle dependence and assume a flat prior on the SME
coefficient. We then combine individual posterior probability densities to
obtain a measurement of the 16 anisotropic coefficients $k_{(V)ij}^{(5)}$
while taking into account the source sky localization via the full expression
in (15). We perform the combination by interpreting the sampled parameter as
the linear combination:

$\vec{K}=\bm{Y}\cdot\vec{k_{(V)ij}^{(5)}},$ (18)

where $\vec{K}$ is the vector of 45 posteriors of $k_{(V)00}^{(5)}/Y_{00}$,
$\bm{Y}$ is the matrix of spherical harmonics, and $\vec{k_{(V)ij}^{(5)}}$
corresponds to the 16 SME coefficients. We invert Eq. 18 using the Singular
Value Decomposition (SVD)method, for which:

$\vec{k}=\bm{V}\bm{\Sigma^{\dagger}}\bm{U^{T}}\vec{K},$ (19)

where the $\bm{V},\bm{\Sigma^{\dagger}}$ and $\bm{U^{T}}$ matrices are the SVD
factorisation of $\bm{Y}$.

###  III.2 Dataset from the GWTC-3 catalog

We perform our analysis on the events detected during the three first
observing runs, corresponding to the cumulative catalog GWTC-3 [11]. All the
GW detections originate from the coalescence of binary systems of black holes
and/or neutron stars, and the catalog reports 90 events with a probability of
astrophysical origin larger than 50%. The study of GW residual shows that
after subtraction of the best-fitted waveforms assuming GR, the leftover
signals are consistent with noise, indicating that deviations from GR are
higher order terms inducing small modification of the signal morphology [53].
Therefore, low-sensitivity events are unsuited for tests of GR as they may
lead to false apparent deviations due to transient noise or incomplete
modelling of the gravitational waveform [78, 79]. To prevent such undesirable
features, we add the following requirements: (i) the false alarm rate
(FAR)must be lower than $10^{-3}\ \text{year}^{-1}$, in order to only use
high-confidence signals; and (ii) the event must have been selected by the LVK
to test the modified dispersion relation, as while we use a different
theoretical framework and phenomenology, we are also performing a measurement
of GW dispersion. The final selection contains 45 events (10 events first
reported in GWTC-1, 23 events in GWTC-2, and 12 events in GWTC-3), with
signal-to-noise ratio (SNR)comprised within [9.2; 26.8] and luminosity
distances within $[0.32,4.42]$ Gpc.

##  IV Measuring spacetime symmetry breaking parameters

###  IV.1 Constraints with GWTC-3

The marginalised posterior distribution of the isotropic dispersion
coefficient $|k_{(V)00}^{(5)}|$ is obtained for all the events described on
Sec. III.2. As shown in Fig. 1, most events are compatible with a zero value
of $|k_{(V)00}^{(5)}|$, corresponding to the GR case. The 68.3% upper bounds
range between $\mathcal{O}(10^{-14})$ and $\mathcal{O}(10^{-13})$ according to
the event, with 10 events presenting a 68.3% credible interval not compatible
with GR. Only one event, GW190828_065509, is not compatible with GR at 90% CI.
The combined constraint from all events on $|k_{(V)00}^{(5)}|$ is $3.19\cdot
10^{-15}$ m at 90% CI. At 68.3% CI, the combined bound is $5.62\cdot
10^{-16}<|k_{(V)00}^{(5)}|<2.81\cdot 10^{-15}$ m. This deviation from GR is
driven by the events GW190720_000836, GW190828_065509, GW200225_060421, and is
alleviated when removing the three posteriors from the combination.

Figure 1:  Posterior probability on the isotropic dispersion coefficient
$|k_{(V)00}^{(5)}|$ from individual events. The events in color presents a
68.3% CI not compatible with the GR case of $|k_{(V)00}^{(5)}|=0$, while the
events in grey are compatible.

Using the fact that we have more individual events than coefficients, we
perform a sky-localisation dependent analysis to extract the 16
$k_{(V)ij}^{(5)}$ coefficients from the $|k_{(V)00}^{(5)}|$ posteriors,
separating the anisotropic coefficients into real and imaginary components.
The credible intervals obtained with the SVD inverting method described on
Sec. III.1, including the correlations between the parameters, are shown in
Fig. 2. The bounds on the spacetime symmetry breaking coefficients are
extracted from the marginalised 1-dimensional posterior probability
distributions displayed diagonally in Fig. 2, and summarised in Table 1. All
the anisotropic coefficients are compatible with the GR case. The isotropic
coefficient $k_{(V)00}^{(5)}$ presents a deviation towards values superior to
0, driven by the events presenting a deviation in Fig. 1. When removing those
10 events, the deviation from GR does not appear anymore. The joint estimation
is however less constraining than the individual one, as the bounds are three
orders of magnitude larger than the combined constraint of individual events
assuming the anisotropic coefficients to be zero.

Figure 2:  Posterior probability of the $k_{(V)ij}^{(5)}$ coefficients (in $10^{-12}$ m). For the 2-dimensional distribution, dark blue are the 68.3% credible intervals and light blue the 90% credible intervals.  90% | 68.3% | $k_{(V)ij}^{(5)}$ | 68.3% | 90%
---|---|---|---|---
lower | lower | coefficient | upper | upper
0.51 | 1.21 | $k_{00}$ | 4.38 | 7.37
-4.54 | -2.13 | $k_{10}$ | 1.19 | 3.91
-2.30 | -1.00 | $Re(k_{11})$ | 1.73 | 3.39
-3.64 | -1.21 | $Im(k_{11})$ | 2.35 | 4.45
-7.40 | -3.75 | $k_{20}$ | 1.10 | 3.78
-1.75 | -0.61 | $Re(k_{21})$ | 1.43 | 3.02
-2.77 | -1.16 | $Im(k_{21})$ | 1.71 | 3.67
-3.58 | -1.72 | $Re(k_{22})$ | 1.02 | 2.55
-2.49 | -0.96 | $Im(k_{22})$ | 2.80 | 5.58
-6.40 | -3.31 | $k_{30}$ | 1.17 | 3.57
-3.34 | -1.65 | $Re(k_{31})$ | 0.98 | 2.48
-3.90 | -1.92 | $Im(k_{31})$ | 1.75 | 3.87
-2.76 | -1.23 | $Re(k_{32})$ | 1.34 | 2.87
-2.26 | -0.90 | $Im(k_{32})$ | 1.82 | 3.60
-3.95 | -1.95 | $Re(k_{33})$ | 1.28 | 3.18
-3.22 | -1.35 | $Im(k_{33})$ | 2.25 | 4.78
Table 1: Credible intervals on the $k_{(V)ij}^{(5)}$ coefficients (in
$10^{-13}$ m), determined from the marginalised posterior probability
distributions estimated with the joint estimation of the 16 $k_{(V)ij}^{(5)}$
coefficients shown in diagonal in Fig. 2.

###  IV.2 Robustness tests

The events shown in color in Fig. 1 present a 68.3% CI not compatible with the
GR case of $|k_{(V)00}^{(5)}|=0$ m. We have surveyed the results presented by
the LVK in their articles summarising several tests of GR to look for other
pathological behaviour from those events [9, 10, 53]. We find two events from
O2 (GW170729, GW170814) and two from O3 (GW190828_065509, GW200225_060421)
that have been shown to drive a bias in the estimation of the modified
dispersion relation parameters. Three O3 events (GW190519_153544,
GW190521_074359, and GW190828_065509) present deviations in parameterised
post-Newtonian tests, while one O3 event (GW200225_060421) presents poor score
in residual tests. Those features indicate a lack of new physics in the model
used to generate the GR parts $h_{(+)}^{LI}$ and $h_{(\times)}^{LI}$ of Eq.
(12), that may originate from the lack of dynamical effects of features of a
new theory. The mismodeling or lack of modeling of dynamical phenomena, such
as an approximation of precession or assuming circular orbits, can impact the
estimation of beyond-GR parameters [79].

In order to investigate the robustness of the results, we inferred
$|k_{(V)00}^{(5)}|$ using different waveform models for several binary black
hole events, as shown for two cases on Fig. 3. We compared the posterior
probability densities obtained with IMRPhenomPv2 with the ones inferred with
the SEOBNRv4, that uses an effective one-body description of the dynamics of
spinning binaries [80]; and IMRPhenomXPHM, an updated version of IMRPhenomPv2
including higher harmonics and updated calibration to precession [81]. For the
23 events where we compared IMRPhenomPv2 and IMRPhenomXPHM, only four events
showed a considerable modification of the credible intervals with a mode
different from zero for only one of the model (GW190519_153544,
GW190706_222641, GW200219_094415, GW200225_060421). For the four events where
we compared IMRPhenomPv2 and SEOBNRv4, two presented a modification of the
credible intervals (GW190630_185205, GW190720_000836). When investigating the
events presenting a CI not including 0, only three of the ten events are
compatible with the GR case with another model (GW190519_153544,
GW190706_222641, GW190720_000836). While this rules out mismodelling as the
unique source of tension, it points towards a lack of dynamics in the
underlying model for some cases, and highlights the sensitivity of our
analysis to spot deviations in GW signals. However, as waveform models share
some common assumptions, and the uncertainty due to the modeling process
(i.e., their mismatch with numerical relativity simulations) is not propagated
during the analysis, more detailed study about waveform accuracy must be
carried before ruling it out as a cause for apparent deviations from GR.

Figure 3:  Posterior probability on the isotropic dispersion coefficient
$|k_{(V)00}^{(5)}|$ obtained with different waveform models. The top figure
presents consistent estimation while the bottom figure presents a case where
the probability shape is different according to the waveform model used for
inference.

By measuring jointly the source and symmetry breaking parameters, the
correlations between the variables are taken into account during the
inference. We evaluate them by measuring the Pearson coefficients between
$|k_{(V)00}^{(5)}|$ and the source parameters as shown in Fig. 4, where the
events presenting deviations from GR at 68.3% CI are highlighted. Most events
show no or very moderate correlations, and amongst the highlighted events,
whileGW170814 and GW190519_153544 present large (anti)correlation with the
mass and spin parameters, other events in agreement with GR present larger
correlations. Those results indicate that a more accurate measurement of the
source parameters, as could be obtained from higher SNR or from the detection
of higher modes, can lead to an improvement of the constraints on the SME
coefficients.

Figure 4:  Correlations between $|k_{(V)00}^{(5)}|$ and the source parameters.
The x-axis shows the chirp mass $M_{c}$, the mass ratio $q$, the luminosity
distance $D_{L}$, the spin magnitudes $a_{1}$ and $a_{2}$, the spin tilt
angles $\theta_{1,2}$, the projected angle difference between spins
$\phi_{12}$, the right ascension $\alpha$, and the declination $\delta$. The
colored markers corresponding to the events presenting a deviation on Fig. 1,
with GW170814 in pink and GW190519_153544 in blue; the grey markers are the
other events.

##  V Discussion

This work presents a new probe of Lorentz and CPT violation with GWs,
extending the search for possible signals from a unified theory of physics.
Our analysis relies on an effective field theory framework, which allows one
to derive phenomenological consequences of spacetime-symmetry breaking across
many regimes. This work complements existing parameterizations of LI violation
in GWs. We extend the measurement of SME coefficients to higher mass dimension
terms in the action, compared to constraints derived from speed of gravity
tests, by probing GW dispersion, including anisotropic and birefringence
effects. Our method goes beyond existing measurements by performing a joint
inference of source parameters and symmetry-breaking coefficients, effectively
taking into account correlations. Compared to SME measurements relying on time
delay measurements, estimated from posterior probabilities inferred assuming
GR, we find milder constraints on the order of $\mathcal{O}(10^{-13}\
\text{m})$ instead of $\mathcal{O}(10^{-16}\ \text{m})$ [49, 50]. These
results indicate that correlations between GR and SME coefficients must be
taken into account and the simplified treatments in earlier work should be
replaced with proper parameter estimation.

While this work was carried, another team performed an independent measurement
of SME coefficients for $d=5$ [51]. Our analysis differs by estimating the
joint posterior probability for 16 $k_{(V)ij}^{(d=5)}$ coefficients, while
they perform a measurement of single and dual coefficients only, assuming the
remaining coefficients to be zero. Consequently, our analysis includes
possible correlations between SME coefficients, as can be seen in Fig. 2. On
the methodological side, our analysis relies on the LALInference software,
while [51] relies on the bilby software. Using different methods enables us to
verify the validity of the inferences provided by each software, and we find
our results to be in agreement as we both derive a joint constraint around
$|k_{(V)00}^{(d=5)}|<\mathcal{O}(10^{-15}\ \text{m})$ when assuming that all
other coefficients are zero.

Note also that the main measurement results in this paper, the limits on
coefficients in Table 1, can be directly compared to the results from other
tests in gravity [22]. For example, solar-system tests like lunar laser
ranging have yielded measurements on $15$ linear combinations of the $60$
independent mass dimension $5$ coefficients in
$(q^{(5)})^{\alpha\beta\gamma\mu\nu\rho\sigma}$ in Eq. (3), with limits on the
order of $10^{3}$ m [44]. This seems substantially poorer than the limits in
this paper from GWs, but the $16$ $k_{(V)ij}^{(d=5)}$ coefficients probed in
this paper are distinct linear combinations of the
$(q^{(5)})^{\alpha\beta\gamma\mu\nu\rho\sigma}$ coefficients from those
occurring in lunar laser ranging. Similarly, limits from pulsars via orbital
tests are on the order of $10^{6}$ m [37], but probe distinct coefficients
from GWs. Should a nonzero detection occur, it will be important to compare
measurements in distinct tests.

While our global results are compatible with GR, a subset of events show non-
zero $k_{(V)00}^{(d=5)}$ estimates. We investigated possible shared features
between those events, that do not display similar sky localisation neither
other common parameters. Robustness tests indicate that for few events, the
addition of higher modes resolves the tension. However, several events do not
present modified posterior probability profiles when using other waveform
models, pointing to the possibility that existing waveform models may lack
dynamical features degenerate with the effects of dispersion. The current
efforts in creating more accurate waveform templates, e.g. with the addition
of eccentric trajectories, will provide a better understanding of the
relevance of modelling accuracy for SME tests in particular and tests of GR in
general.

The analysis in this paper studies propagation effects from LI violation. The
addition of other possible effects from higher-order (in $h_{\mu\nu}$) terms
in the SME on the waveform itself, for example, via a post-Newtonian multipole
expansion in the SME framework, could provide new tests. The latter work is in
progess [24, 69].

###### Acknowledgements.

LH is supported by the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie grant agreement No
945298-ParisRegionFP, and is a Fellow of Paris Region Fellowship Programme
supported by the Paris Region. She acknowledges the support of the COST Action
CA18108. Work on this project by QGB and KOA was supported by the United
States National Science Foundation (NSF) under grant numbers 1806871 and
2207734. Work on this project by JDT and MB was supported by the NSF under
grant number 1806990. LS was supported by the National Natural Science
Foundation of China (11975027, 11991053, 11721303), the National SKA Program
of China (2020SKA0120300), and the Max Planck Partner Group Program funded by
the Max Planck Society. The authors would like to thank the LIGO-Virgo-KAGRA
collaboration for general support, and particularly Duncan MacLeod, Peter Tsun
Ho Pang, Charlie Hoy, Geraint Pratten and John Veitch for the useful
discussion concerning the software infrastructure. This research has made use
of data or software obtained from the Gravitational Wave Open Science Center
(gw-openscience.org), a service of LIGO Laboratory, the LIGO Scientific
Collaboration, the Virgo Collaboration, and KAGRA. LIGO Laboratory and
Advanced LIGO are funded by the NSF as well as the Science and Technology
Facilities Council (STFC) of the United Kingdom, the Max-Planck-Society (MPS),
and the State of Niedersachsen/Germany for support of the construction of
Advanced LIGO and construction and operation of the GEO600 detector.
Additional support for Advanced LIGO was provided by the Australian Research
Council. Virgo is funded, through the European Gravitational Observatory
(EGO), by the French Centre National de Recherche Scientifique (CNRS), the
Italian Istituto Nazionale di Fisica Nucleare (INFN) and the Dutch Nikhef,
with contributions by institutions from Belgium, Germany, Greece, Hungary,
Ireland, Japan, Monaco, Poland, Portugal, Spain. The construction and
operation of KAGRA are funded by Ministry of Education, Culture, Sports,
Science and Technology (MEXT), and Japan Society for the Promotion of Science
(JSPS), National Research Foundation (NRF) and Ministry of Science and ICT
(MSIT) in Korea, Academia Sinica (AS) and the Ministry of Science and
Technology (MoST) in Taiwan. The authors are grateful for computational
resources provided by the LIGO Laboratory and supported by the NSF PHY-0757058
and PHY-0823459.

## References

  * Kostelecký and Samuel [1989] V. A. Kostelecký and S. Samuel, Spontaneous breaking of lorentz symmetry in string theory, Phys. Rev. D 39, 683 (1989).
  * Gambini and Pullin [1999] R. Gambini and J. Pullin, Nonstandard optics from quantum space-time, Phys. Rev. D 59, 124021 (1999).
  * Carroll  _et al._ [2001] S. M. Carroll, J. A. Harvey, V. A. Kostelecký, C. D. Lane, and T. Okamoto, Noncommutative field theory and lorentz violation, Phys. Rev. Lett. 87, 141601 (2001).
  * Alan Kostelecký and Potting [1991] V. Alan Kostelecký and R. Potting, Cpt and strings, Nuclear Physics B 359, 545 (1991).
  * Addazi  _et al._ [2022] A. Addazi _et al._ , Quantum gravity phenomenology at the dawn of the multi-messenger era—A review, Prog. Part. Nucl. Phys. 125, 103948 (2022), arXiv:2111.05659 [hep-ph] .
  * Mariz  _et al._ [2022] T. Mariz, J. R. Nascimento, and A. Y. Petrov, Lorentz symmetry breaking – classical and quantum aspects, (2022), arXiv:2205.02594 [hep-th] .
  * Abbott  _et al._ [2016a] B. P. Abbott _et al._ (LIGO Scientific, Virgo), Observation of Gravitational Waves from a Binary Black Hole Merger, Phys. Rev. Lett. 116, 061102 (2016a), arXiv:1602.03837 [gr-qc] .
  * Abbott  _et al._ [2016b] B. P. Abbott _et al._ (LIGO Scientific, Virgo), Tests of general relativity with GW150914, Phys. Rev. Lett. 116, 221101 (2016b), [Erratum: Phys.Rev.Lett. 121, 129902 (2018)], arXiv:1602.03841 [gr-qc] .
  * Abbott  _et al._ [2019a] B. P. Abbott _et al._ (LIGO Scientific, Virgo), Tests of General Relativity with the Binary Black Hole Signals from the LIGO-Virgo Catalog GWTC-1, Phys. Rev. D 100, 104036 (2019a), arXiv:1903.04467 [gr-qc] .
  * Abbott  _et al._ [2021a] R. Abbott _et al._ (LIGO Scientific, Virgo), Tests of general relativity with binary black holes from the second LIGO-Virgo gravitational-wave transient catalog, Phys. Rev. D 103, 122002 (2021a), arXiv:2010.14529 [gr-qc] .
  * Abbott  _et al._ [2021b] R. Abbott _et al._ (LIGO Scientific, VIRGO, KAGRA), GWTC-3: Compact Binary Coalescences Observed by LIGO and Virgo During the Second Part of the Third Observing Run, (2021b), arXiv:2111.03606 [gr-qc] .
  * Colladay and Kostelecký [1997] D. Colladay and V. A. Kostelecký, $\mathrm{CPT}$ violation and the standard model, Phys. Rev. D 55, 6760 (1997).
  * Colladay and Kostelecký [1998] D. Colladay and V. A. Kostelecký, Lorentz-violating extension of the standard model, Phys. Rev. D 58, 116002 (1998).
  * Kostelecký [2004] V. A. Kostelecký, Gravity, lorentz violation, and the standard model, Phys. Rev. D 69, 105009 (2004).
  * Bailey and Kostelecký [2006] Q. G. Bailey and V. A. Kostelecký, Signals for lorentz violation in post-newtonian gravity, Phys. Rev. D 74, 045001 (2006).
  * Kostelecky and Tasson [2011] V. A. Kostelecky and J. D. Tasson, Matter-gravity couplings and Lorentz violation, Phys. Rev. D 83, 016013 (2011), arXiv:1006.4106 [gr-qc] .
  * Bailey  _et al._ [2015] Q. G. Bailey, A. Kostelecký, and R. Xu, Short-range gravity and Lorentz violation, Phys. Rev. D 91, 022006 (2015), arXiv:1410.6162 [gr-qc] .
  * Bluhm [2015] R. Bluhm, Explicit versus spontaneous diffeomorphism breaking in gravity, Phys. Rev. D 91, 065034 (2015).
  * Kostelecký and Mewes [2016] V. A. Kostelecký and M. Mewes, Testing local lorentz invariance with gravitational waves, Phys. Lett. B 757, 510 (2016).
  * Kostelecký and Mewes [2018] V. A. Kostelecký and M. Mewes, Lorentz and diffeomorphism violations in linearized gravity, Phys. Lett. B 779, 136 (2018).
  * Kostelecký and Li [2021] V. A. Kostelecký and Z. Li, Backgrounds in gravitational effective field theory, Phys. Rev. D 103, 024059 (2021).
  * Kostelecký and Russell [2011] V. A. Kostelecký and N. Russell, Data tables for lorentz and $cpt$ violation, Rev. Mod. Phys. 83, 11 (2011).
  * Xu [2019] R. Xu, Modifications to Plane Gravitational Waves from Minimal Lorentz Violation, Symmetry 11, 1318 (2019), arXiv:1910.09762 [gr-qc] .
  * Xu  _et al._ [2021] R. Xu, Y. Gao, and L. Shao, Signatures of Lorentz Violation in Continuous Gravitational-Wave Spectra of Ellipsoidal Neutron Stars, Galaxies 9, 12 (2021), arXiv:2101.09431 [gr-qc] .
  * Nascimento  _et al._ [2021] J. R. Nascimento, A. Y. Petrov, and A. R. Vieira, On plane wave solutions in Lorentz-violating extensions of gravity, Galaxies 9, 32 (2021), arXiv:2104.01651 [gr-qc] .
  * Long and Kostelecký [2015] J. C. Long and V. A. Kostelecký, Search for Lorentz violation in short-range gravity, Phys. Rev. D 91, 092003 (2015), arXiv:1412.8362 [hep-ex] .
  * Shao  _et al._ [2016] C.-G. Shao _et al._ , Combined search for Lorentz violation in short-range gravity, Phys. Rev. Lett. 117, 071102 (2016), arXiv:1607.06095 [gr-qc] .
  * Shao  _et al._ [2019] C.-G. Shao, Y.-F. Chen, Y.-J. Tan, S.-Q. Yang, J. Luo, M. E. Tobar, J. C. Long, E. Weisman, and V. A. Kostelecký, Combined Search for a Lorentz-Violating Force in Short-Range Gravity Varying as the Inverse Sixth Power of Distance, Phys. Rev. Lett. 122, 011102 (2019), arXiv:1812.11123 [gr-qc] .
  * Muller  _et al._ [2008] H. Muller, S.-w. Chiow, S. Herrmann, S. Chu, and K.-Y. Chung, Atom Interferometry tests of the isotropy of post-Newtonian gravity, Phys. Rev. Lett. 100, 031101 (2008), arXiv:0710.3768 [gr-qc] .
  * Chung  _et al._ [2009] K.-Y. Chung, S.-w. Chiow, S. Herrmann, S. Chu, and H. Muller, Atom interferometry tests of local Lorentz invariance in gravity and electrodynamics, Phys. Rev. D 80, 016002 (2009), arXiv:0905.1929 [gr-qc] .
  * Hohensee  _et al._ [2011] M. A. Hohensee, S. Chu, A. Peters, and H. Muller, Equivalence Principle and Gravitational Redshift, Phys. Rev. Lett. 106, 151102 (2011), arXiv:1102.4362 [gr-qc] .
  * Hohensee  _et al._ [2013] M. A. Hohensee, H. Mueller, and R. B. Wiringa, Equivalence Principle and Bound Kinetic Energy, Phys. Rev. Lett. 111, 151102 (2013), arXiv:1308.2936 [gr-qc] .
  * Flowers  _et al._ [2017] N. A. Flowers, C. Goodge, and J. D. Tasson, Superconducting-Gravimeter Tests of Local Lorentz Invariance, Phys. Rev. Lett. 119, 201101 (2017), arXiv:1612.08495 [gr-qc] .
  * Shao  _et al._ [2018] C.-G. Shao, Y.-F. Chen, R. Sun, L.-S. Cao, M.-K. Zhou, Z.-K. Hu, C. Yu, and H. Müller, Limits on Lorentz violation in gravity from worldwide superconducting gravimeters, Phys. Rev. D 97, 024019 (2018), arXiv:1707.02318 [gr-qc] .
  * Ivanov  _et al._ [2019] A. N. Ivanov, M. Wellenzohn, and H. Abele, Probing of violation of Lorentz invariance by ultracold neutrons in the Standard Model Extension, Phys. Lett. B 797, 134819 (2019), arXiv:1908.01498 [hep-ph] .
  * Shao [2014] L. Shao, Tests of local Lorentz invariance violation of gravity in the standard model extension with pulsars, Phys. Rev. Lett. 112, 111103 (2014), arXiv:1402.6452 [gr-qc] .
  * Shao and Bailey [2018] L. Shao and Q. G. Bailey, Testing velocity-dependent CPT-violating gravitational forces with radio pulsars, Phys. Rev. D 98, 084049 (2018), arXiv:1810.06332 [gr-qc] .
  * Wex and Kramer [2020] N. Wex and M. Kramer, Gravity Tests with Radio Pulsars, Universe 6, 156 (2020).
  * Iorio [2012] L. Iorio, Orbital effects of Lorentz-violating Standard Model Extension gravitomagnetism around a static body: a sensitivity analysis, Class. Quant. Grav. 29, 175007 (2012), arXiv:1203.1859 [gr-qc] .
  * Hees  _et al._ [2013] A. Hees, B. Lamine, S. Reynaud, M. T. Jaekel, C. Le Poncin-Lafitte, V. Lainey, A. Fuzfa, J. M. Courty, V. Dehant, and P. Wolf, Simulations of Solar System observations in alternative theories of gravity, in  _13th Marcel Grossmann Meeting on Recent Developments in Theoretical and Experimental General Relativity, Astrophysics, and Relativistic Field Theories_ (2013) arXiv:1301.1658 [gr-qc] .
  * Le Poncin-Lafitte  _et al._ [2016] C. Le Poncin-Lafitte, A. Hees, and S. Lambert, Lorentz symmetry and Very Long Baseline Interferometry, Phys. Rev. D 94, 125030 (2016), arXiv:1604.01663 [gr-qc] .
  * Bourgoin  _et al._ [2016] A. Bourgoin, A. Hees, S. Bouquillon, C. Le Poncin-Lafitte, G. Francou, and M. C. Angonin, Testing Lorentz symmetry with Lunar Laser Ranging, Phys. Rev. Lett. 117, 241301 (2016), arXiv:1607.00294 [gr-qc] .
  * Bourgoin  _et al._ [2017] A. Bourgoin, C. Le Poncin-Lafitte, A. Hees, S. Bouquillon, G. Francou, and M.-C. Angonin, Lorentz Symmetry Violations from Matter-Gravity Couplings with Lunar Laser Ranging, Phys. Rev. Lett. 119, 201102 (2017), arXiv:1706.06294 [gr-qc] .
  * Bourgoin  _et al._ [2021] A. Bourgoin _et al._ , Constraining velocity-dependent Lorentz and $CPT$ violations using lunar laser ranging, Phys. Rev. D 103, 064055 (2021), arXiv:2011.06641 [gr-qc] .
  * Pihan-Le Bars  _et al._ [2019] H. Pihan-Le Bars _et al._ , New Test of Lorentz Invariance Using the MICROSCOPE Space Mission, Phys. Rev. Lett. 123, 231102 (2019), arXiv:1912.03030 [physics.space-ph] .
  * Kostelecký and Tasson [2015] V. A. Kostelecký and J. D. Tasson, Constraints on lorentz violation from gravitational čerenkov radiation, Physics Letters B 749, 551 (2015).
  * Abbott  _et al._ [2017] B. P. Abbott _et al._ (LIGO Scientific, Virgo, Fermi-GBM, INTEGRAL), Gravitational Waves and Gamma-rays from a Binary Neutron Star Merger: GW170817 and GRB 170817A, Astrophys. J. Lett. 848, L13 (2017), arXiv:1710.05834 [astro-ph.HE] .
  * Liu  _et al._ [2020] X. Liu, V. F. He, T. M. Mikulski, D. Palenova, C. E. Williams, J. Creighton, and J. D. Tasson, Measuring the speed of gravitational waves from the first and second observing run of Advanced LIGO and Advanced Virgo, Phys. Rev. D 102, 024028 (2020), arXiv:2005.03121 [gr-qc] .
  * Shao [2020] L. Shao, Combined search for anisotropic birefringence in the gravitational-wave transient catalog GWTC-1, Phys. Rev. D 101, 104019 (2020), arXiv:2002.01185 [hep-ph] .
  * Wang  _et al._ [2021a] Z. Wang, L. Shao, and C. Liu, New Limits on the Lorentz/CPT Symmetry Through 50 Gravitational-wave Events, Astrophys. J. 921, 158 (2021a), arXiv:2108.02974 [gr-qc] .
  * Niu  _et al._ [2022] R. Niu, T. Zhu, and W. Zhao, Constraining Anisotropy Birefringence Dispersion in Gravitational Wave Propagation with GWTC-3, (2022), arXiv:2202.05092 [gr-qc] .
  * Abbott  _et al._ [2019b] B. P. Abbott _et al._ (LIGO Scientific, Virgo), Tests of General Relativity with the Binary Black Hole Signals from the LIGO-Virgo Catalog GWTC-1, Phys. Rev. D 100, 104036 (2019b), arXiv:1903.04467 [gr-qc] .
  * Abbott  _et al._ [2021c] R. Abbott _et al._ (LIGO Scientific, VIRGO, KAGRA), Tests of General Relativity with GWTC-3 (2021c), arXiv:2112.06861 [gr-qc] .
  * Wang  _et al._ [2021b] Y.-F. Wang, S. M. Brown, L. Shao, and W. Zhao, Tests of Gravitational-Wave Birefringence with the Open Gravitational-Wave Catalog (2021b), arXiv:2109.09718 [astro-ph.HE] .
  * Wang and Zhao [2020] S. Wang and Z.-C. Zhao, Tests of CPT invariance in gravitational waves with LIGO-Virgo catalog GWTC-1, Eur. Phys. J. C 80, 1032 (2020), arXiv:2002.00396 [gr-qc] .
  * Wang  _et al._ [2021c] Y.-F. Wang, R. Niu, T. Zhu, and W. Zhao, Gravitational Wave Implications for the Parity Symmetry of Gravity in the High Energy Region, Astrophys. J. 908, 58 (2021c), arXiv:2002.05668 [gr-qc] .
  * Yunes  _et al._ [2016] N. Yunes, K. Yagi, and F. Pretorius, Theoretical physics implications of the binary black-hole mergers gw150914 and gw151226, Phys. Rev. D 94, 084002 (2016).
  * Berti  _et al._ [2018] E. Berti, K. Yagi, and N. Yunes, Extreme Gravity Tests with Gravitational Waves from Compact Binary Coalescences: (I) Inspiral-Merger, Gen. Rel. Grav. 50, 46 (2018), arXiv:1801.03208 [gr-qc] .
  * Amarilo  _et al._ [2019] K. M. Amarilo, M. Barroso, F. Filho, and R. V. Maluf, Modification in Gravitational Waves Production Triggered by Spontaneous Lorentz Violation, PoS BHCB2018, 015 (2019).
  * Ferrari  _et al._ [2007] A. Ferrari, M. Gomes, J. Nascimento, E. Passos, A. Petrov, and A. da Silva, Lorentz violation in the linearized gravity, Phys. Lett. B 652, 174 (2007).
  * Tso and Zanolin [2016] R. Tso and M. Zanolin, Measuring violations of general relativity from single gravitational wave detection by nonspinning binary systems: Higher-order asymptotic analysis, Phys. Rev. D 93, 124033 (2016), arXiv:1509.02248 [gr-qc] .
  * Qiao  _et al._ [2019] J. Qiao, T. Zhu, W. Zhao, and A. Wang, Waveform of gravitational waves in the ghost-free parity-violating gravities, Phys. Rev. D 100, 124058 (2019), arXiv:1909.03815 [gr-qc] .
  * Mirshekari  _et al._ [2012] S. Mirshekari, N. Yunes, and C. M. Will, Constraining Generic Lorentz Violation and the Speed of the Graviton with Gravitational Waves, Phys. Rev. D 85, 024041 (2012), arXiv:1110.2720 [gr-qc] .
  * Haegel [2021] L. Haegel, Searching for new physics during gravitational waves propagation, in  _55th Rencontres de Moriond on Gravitation_ (2021) arXiv:2106.05097 [gr-qc] .
  * Mewes [2019] M. Mewes, Signals for Lorentz violation in gravitational waves, Phys. Rev. D 99, 104062 (2019), arXiv:1905.00409 [gr-qc] .
  * O’Neal-Ault  _et al._ [2021a] K. O’Neal-Ault, Q. G. Bailey, T. Dumerchat, L. Haegel, and J. Tasson, Analysis of Birefringence and Dispersion Effects from Spacetime-Symmetry Breaking in Gravitational Waves, Universe 7, 380 (2021a), arXiv:2108.06298 [gr-qc] .
  * O’Neal-Ault  _et al._ [2021b] K. O’Neal-Ault, Q. G. Bailey, and N. A. Nilsson, 3+1 formulation of the standard model extension gravity sector, Phys. Rev. D 103, 044010 (2021b), arXiv:2009.00949 [gr-qc] .
  * Seifert [2009] M. D. Seifert, Vector models of gravitational lorentz symmetry breaking, Phys. Rev. D 79, 124012 (2009).
  * Bailey [2021] Q. G. Bailey, Construction of higher-order metric fluctuation terms in spacetime symmetry-breaking effective field theory, Symmetry 13, 834 (2021), arXiv:2104.08930 [gr-qc] .
  * Kostelecký and Mewes [2009] V. A. Kostelecký and M. Mewes, Electrodynamics with lorentz-violating operators of arbitrary dimension, Phys. Rev. D 80, 015020 (2009).
  * Yagi  _et al._ [2014] K. Yagi, D. Blas, N. Yunes, and E. Barausse, Strong binary pulsar constraints on lorentz violation in gravity, Phys. Rev. Lett. 112, 161101 (2014).
  * Liang  _et al._ [2022] D. Liang, R. Xu, X. Lu, and L. Shao, Polarizations of Gravitational Waves in the Bumblebee Gravity Model, (2022), arXiv:2207.14423 [gr-qc] .
  * Kostelecky and Mewes [2002] V. A. Kostelecky and M. Mewes, Signals for Lorentz violation in electrodynamics, Phys. Rev. D 66, 056005 (2002), arXiv:hep-ph/0205211 .
  * Kostelecký and Vargas [2018] V. A. Kostelecký and A. J. Vargas, Lorentz and CPT Tests with Clock-Comparison Experiments, Phys. Rev. D 98, 036003 (2018), arXiv:1805.04499 [hep-ph] .
  * Veitch  _et al._ [2015] J. Veitch, V. Raymond, B. Farr, W. Farr, P. Graff, S. Vitale, B. Aylott, K. Blackburn, N. Christensen, M. Coughlin, and et al., Parameter estimation for compact binaries with ground-based gravitational-wave observations using the lalinference software library, Phys. Rev. D 91, 042003 (2015).
  * Hoy and Raymond [2021] C. Hoy and V. Raymond, PESummary: the code agnostic Parameter Estimation Summary page builder, SoftwareX 15, 100765 (2021), arXiv:2006.06639 [astro-ph.IM] .
  * Hannam  _et al._ [2014] M. Hannam, P. Schmidt, A. Bohé, L. Haegel, S. Husa, F. Ohme, G. Pratten, and M. Pürrer, Simple Model of Complete Precessing Black-Hole-Binary Gravitational Waveforms, Phys. Rev. Lett. 113, 151101 (2014), arXiv:1308.3271 [gr-qc] .
  * Kwok  _et al._ [2022] J. Y. L. Kwok, R. K. L. Lo, A. J. Weinstein, and T. G. F. Li, Investigation of the effects of non-Gaussian noise transients and their mitigation in parameterized gravitational-wave tests of general relativity, Phys. Rev. D 105, 024066 (2022), arXiv:2109.07642 [gr-qc] .
  * Moore  _et al._ [2021] C. J. Moore, E. Finch, R. Buscicchio, and D. Gerosa, Testing general relativity with gravitational-wave catalogs: The insidious nature of waveform systematics, iScience 24, 102577 (2021).
  * Bohé  _et al._ [2017] A. Bohé _et al._ , Improved effective-one-body model of spinning, nonprecessing binary black holes for the era of gravitational-wave astrophysics with advanced detectors, Phys. Rev. D 95, 044028 (2017), arXiv:1611.03703 [gr-qc] .
  * Pratten  _et al._ [2021] G. Pratten _et al._ , Computationally efficient models for the dominant and subdominant harmonic modes of precessing binary black holes, Phys. Rev. D 103, 104056 (2021), arXiv:2004.06503 [gr-qc] .


# Encoding Scheme for Infinite Set of Symbols:
the Percolation Process on Infinite Perfect Binary Trees

Yousof Mardoukhi
Institute of Physics and Astronomy, University of Potsdam, 14476 - Potsdam,
Germany
<EMAIL_ADDRESS>
###### Abstract

It is shown here that the percolation cluster that emerges from the
percolation process on infinite perfect binary trees, is genuinely an encoding
scheme for an infinite set of symbols. The average codeword length and the
entropy of such an encoding scheme are still finite as long as the percolation
density $p$ is between $1/2\leq p<\sqrt[3]{1/4}$.

_K_ eywords Binary Tree $\cdot$ Efficient Encoding $\cdot$ Entropy $\cdot$
Huffman Encoding Scheme $\cdot$ Percolation Process $\cdot$ Bienaymé-Galton-
Watson Process

##  1 Introduction

Binary trees are perennial and indispensable part of information and coding
theory in computer science. They are used for storage file systems and
databases [1, 2]. For instance, the Btrfs (pronounced as B-Tree Filesystem) is
a filesystem utilising the Balanced Tree structure to store large data [3]. In
databases, indexing in many widely used database software such as PostgreSQL
and Oracle SQL use B-tree indexing (see their respective documentations and
also refer to [4] for recent methods and technologies). In a different area
-data compression- the foundation of much popular data compression software
such as .arc, .pk(X)zip, gzip, .bzip and the famous .zip is based on the
Huffman encoding scheme [5].

In real-life cases, the source of the information is represented by a finite
set of symbols (also called alphabets). In these situations, the Huffman
encoding scheme ensures via an encoding procedure that the length of the
codewords associated to each symbol yields an average codeword length which is
the smallest given the frequency of the appearance of each symbol in the
source [5]. Yet, one can get audacious and think of a situation where the set
of symbols is countably infinite. Although, this would not happen in day to
day problems, one can ask whether there exists a physical process that
genuinely encodes the information in a manner that yields a finite average
codeword length. For instance, one can consider a physical system with a set
of discrete energy levels that are countably infinite. If one attempts to
label these discrete levels with a set of codewords, what are the criteria
such that these energy levels are expressed in these codewords and still on
average the codeword length is finite.

In this article, it is demonstrated that the Bienaymé-Galton-Watson process
with maximum two offspring [6, 7], is a process that itself generates the
symbols and encodes them simultaneously in such a manner that the state of the
system described by these symbols can be expressed with an infinite set of
codewords that yields a finite average codeword length. The Bienaymé-Galton-
Watson process with maximum two offspring has an equivalent representation,
namely the percolation process on infinite perfect binary trees. Applications
of the percolation process are far-reaching in many areas, ranging from soft
materials such as polymers [8, 9] to brittle and rigid materials such as rock
[10]. It has been used to model the financial markets [11, 12] or division of
labour markets [13] or to understand the dynamics of a protein in lipid
membranes [14]. Yet with many of these applications, little has been said on
the application of the percolation process from the perspective of information
theory and coding theory [15]. It is demonstrated here that the percolation
cluster that emerges at the critical percolation density $p_{c}$ has
undeniable similarity to the well-known Huffman encoding scheme. This
establishes a direct connection between the Bienaymé-Galton-Watson process,
the percolation process and the Huffman encoding scheme.

The structure of this article is such that it first gives a gentle
introduction to the Bienaymé-Galton-Watson process. Then it is shown that it
is equivalent to the percolation process on perfect binary trees if the number
of the offspring is limited to maximum of two descendants. The section
afterwards is dedicated to the derivation of the generalised probability
generating function for the Bienaymé-Galton-Watson process. With the
generalised probability function in hand, one then can investigate the number
of nodes and leaves of the percolation cluster at different generations. The
last section concludes the results and provides the reader with comparisons
between the analytical and the simulation results.

##  2 Bienaymé-Galton-Watson Process and Percolation Process on Perfect Binary
Trees

The Bienaymé-Galton-Watson process is a branching process
$\\{\mathcal{N}_{n}\\}_{n\in\mathbb{N}}$ where $n\in\mathbb{N}$ is called the
generation and $\mathcal{N}_{n}$ the population of the $n^{th}$ generation.
Each member of a generation has the possibility to have offspring in the next
generation according to a specific probability distribution. The central
question here is to know the number of the population at the $(n+1)^{th}$
generation given the number of the population at the $n^{th}$ generation.

In the most simplest form, it is assumed that the number of offspring each
member of a generation has is independent of the other members of that
generation or any other generations before. If the number of offspring the
$i^{th}$ member of the $n^{th}$ generation has is denoted by
$X_{n}^{i}\in\mathbb{N}$, then the assumption made earlier implies that
$X_{n}^{i}$’s are _i.i.d_ random variables according to a given fixed
probability distribution. Therefore,

$\displaystyle\mathcal{N}_{n+1}=\sum_{i=1}^{\mathcal{N}_{n}}X_{n}^{i}.$ (1)

It follows immediately that the transition probability function for the
process is as follows [16]

$\displaystyle
P\big{(}\mathcal{N}_{n}=i\,|\,\mathcal{N}_{n-1}=j\big{)}=\begin{cases}p_{i}^{*j},&\text{if}\quad
i\geq 1,\,j\geq 0\\\ \delta_{0i},&\text{if}\quad i=0,\,j\geq 0\end{cases},$
(2)

where $p_{i}^{*j}$ is understood as the $j$-fold probability convolution. Note
that this probability transition function implies that the process is a Markov
chain.

There is a kin relation between the Bienaymé-Galton-Watson process and the
percolation process on trees. Since the ultimate goal of this article is about
information encoding, henceforth only the binary trees are assumed here.
Specifically, consider infinite perfect binary trees with the root $\emptyset$
at the top. The percolation process on such trees is the process of assigning
to each edge independent of any other edges the state of being open with
probability $p$and the state of being closed with probability $q=1-p$. The
probability $p$ is also known as the percolation density. The nodes in the
immediate vicinity of the root belong to the first generation and are the
offspring of the root. The nodes that are in the immediate vicinity of the
nodes in the first generation belong to the second generation and so on. A
realisation of such a process on a perfect binary tree up to the third
generation is shown in Fig. 1.

Figure 1: A perfect binary tree with $n=3$. The percolation process on this
tree left behind a set of open edges (solid lines) along with closed edges
(dashed lines) with probability $p$ and $q$ respectively.

An open path between a node in the $n^{th}$ generation and a node in the
$m^{th}$ generation is a sequence of open edges that starts at the former node
and ends at the latter. Consequently, two nodes are said to be connected if
there is an open path between them. A set of nodes that are connected form an
_open cluster_. The size of an open cluster is simply the number of nodes it
has. A node is also said to be a leaf if it does not have any offspring.

When $p=1$, a single perfect tree emerges and all the nodes belong to one
unique open cluster. On the other hand, when $q=1$, nodes are trivial trees.
In this case, one has a forest in which the nodes are the trivial trees in
this forest. In Bienaymé-Galton-Watson process if the probabilities of having
offspring more than two are zero, then every open cluster of the percolation
process is a realisation of a Bienaymé-Galton-Watson process that commences at
a node which is not the offspring of any other node.

The interesting fact here though is the emergence of an infinite open cluster
that includes the root when $p$ reaches a critical value called $p_{c}$ when
for the first time an open cluster called the percolation cluster emerges that
is infinite in size when $n\rightarrow\infty$. This corresponds to the
critical Bienaymé-Galton-Watson process when it thrives ad infinitum. It is
possible to investigate the distribution of the nodes and leaves at $p_{c}$
(also for any other $p$) using the known tool of probability generating
functions [17, 18] discussed in the following subsection.

###  2.1 Probability generating function of the Bienaymé-Galton-Watson process

The probability generating function for the Bienaymé-Galton-Watson process
over the states $\mathbb{N}=\\{0,1,2,\cdots\\}$ and the associated
probabilities $\\{p_{k}\\}_{k\in\mathbb{N}}$ is defined by

$\displaystyle f(\xi)=\sum_{k=0}^{\infty}p_{k}\xi^{k},\quad|\xi|\leq 1,$ (3)

where the dummy index $k$ counts the number of offspring and $p_{k}$ is the
probability of having $k$ offspring. Note that in the case of binary trees,
$p_{k}=0$ for all $k>2$. Hence, the upper bound of the sum is identically 2\.
Nonetheless, the results derived henceforth in this section are not limited to
this constraint. The iterates of the probability generating function Eq. (3)
are given by

$\displaystyle f_{0}(\xi)=\xi,\quad f_{1}(\xi)=f(\xi),\quad
f_{n}(\xi)=f[f_{n-1}(\xi)].$

It is not difficult to establish the following using Eq. (2)

$\displaystyle\sum_{k}P(\mathcal{N}_{n}=k\,|\,\mathcal{N}_{n-1}=1)\xi^{k}=\sum_{k}p_{k}\xi^{k}=f(\xi),$
(4a)
$\displaystyle\sum_{k}P(\mathcal{N}_{n}=k\,|\,\mathcal{N}_{n-1}=i)\xi^{k}=[f(\xi)]^{i}.$
(4b)

The most central identity concerning the probability generating function
defined in Eq. (3) and the probability transition function given by Eq. (2) is
the one that establishes a relation between the $n^{th}$ iterate of the
probability generating function $f_{n}(\xi)$ and the probability generating
function associated with the $n^{th}$ step of the probability transition
function, denoted by $f_{(n)}(\xi)$. Due to Chapman-Kolmogorov equation
111also known as Smoluchowski equation for Markov chains observe that

$\displaystyle f_{(n)}(\xi)$
$\displaystyle=\sum_{k}P(\mathcal{N}_{n}=k\,|\,\mathcal{N}_{0}=1)\xi^{k}=\sum_{k}\sum_{s}P(\mathcal{N}_{n-1}=s\,|\,\mathcal{N}_{0}=1)P(\mathcal{N}_{n}=k\,|\,\mathcal{N}_{n-1}=s)\xi^{k}$
$\displaystyle=\sum_{s}P(\mathcal{N}_{n-1}=s\,|\,\mathcal{N}_{0}=1)\sum_{k}P(\mathcal{N}_{n}=k\,|\,\mathcal{N}_{n-1}=s)\xi^{k}$
$\displaystyle=\sum_{s}P(\mathcal{N}_{n-1}=s\,|\,\mathcal{N}_{0}=1)[f(\xi)]^{s}=f_{(n-1)}[f(\xi)]=\underbrace{f[\cdots[f(\xi)]]}_{n\text{times}}=f_{n}(\xi)$
(5)

The identity above is crucial to deduce moments and properties of the
Bianaymé-Galton-Watson process. In this regard, first note that the mean and
the variance of the population in the first generation can be calculated via
the probability generating function $f(\xi)$.

$\displaystyle\frac{d}{d\xi}f(\xi)\Big{|}_{\xi=1}=\sum_{k=0}^{2}kp_{k}=\mathbb{E}[\mathcal{N}_{1}]:=\mu,$
(6a)
$\displaystyle\frac{d^{2}}{d\xi^{2}}f(\xi)\Big{|}_{\xi=1}=\sum_{k=0}^{2}k(k-1)p_{k}=\mathrm{Var}[\mathcal{N}_{1}]-\mu+\mu^{2}.$
(6b)

Moreover

$\displaystyle\mathbb{E}[\mathcal{N}_{n}]$
$\displaystyle=\frac{d}{d\xi}f_{(n)}(\xi)\Big{|}_{\xi=1}=\frac{d}{d\xi}f_{n}(\xi)\Big{|}_{\xi=1}=\frac{d}{d\xi}f[f_{n-1}(\xi)]\Big{|}_{\xi=1}$
$\displaystyle=f^{\prime}[f_{n-1}(\xi)]f^{\prime}_{n-1}(\xi)\Big{|}_{\xi=1}=f^{\prime}(1)f^{\prime}_{n-1}(1)=[f^{\prime}(1)]^{n}=\mu^{n},$
(7)

where the prime in $f^{\prime}(.)$ stands on the derivative with respect to
the argument. In the last step, one recursively invokes the same identity for
$f^{\prime}_{n-1}(\xi)$ and arrives at $\mu^{n}$. Follow the same procedure
and deduce that

$\displaystyle\mathrm{Var}[\mathcal{N}_{n}]-\mu^{n}+\mu^{2n}$
$\displaystyle=\frac{d^{2}}{d\xi^{2}}f_{(n)}(\xi)\Big{|}_{\xi=1}=\frac{d^{2}}{d\xi^{2}}f_{n}(\xi)\Big{|}_{\xi=1}=\frac{d^{2}}{d\xi^{2}}f[f_{n-1}(\xi)]$
$\displaystyle=f^{\prime\prime}[f_{n-1}(\xi)](f^{\prime}_{n-1}(\xi))^{2}\Big{|}_{\xi=1}+f^{\prime}[f_{n-1}(\xi)]f^{\prime\prime}_{n-1}(\xi)\Big{|}_{\xi=1}$
$\displaystyle=f^{\prime\prime}(1)\mu^{2n-2}+\mu
f^{\prime\prime}_{n-1}(1)=f^{\prime\prime}(1)\mu^{2n-2}\sum_{i=0}^{n-1}\mu^{-i}.$
(8)

The last line in the equation above is due to applying recursively the
identity $f^{\prime\prime}_{n}(1)=f^{\prime\prime}(1)\mu^{2n-2}+\mu
f^{\prime\prime}_{n-1}(1)$. Depending on the value of $\mu$ and by
substituting $f^{\prime\prime}(1)$ with Eq. (6b) the variance obeys the
following expressions

$\displaystyle\mathrm{Var}[\mathcal{N}_{n}]=\begin{cases}\mathrm{Var}[\mathcal{N}_{1}]\mu^{n}\left(\frac{\mu^{n}-1}{\mu^{2}-\mu}\right),&\text{if}\quad\mu\neq
1\\\ n\mathrm{Var}[\mathcal{N}_{1}],&\text{if}\quad\mu=1\end{cases}.$ (9)

So far, the discussion was focused on the statistical properties of
$\mathcal{N}_{n}$ . In the picture of the percolation process on infinite
perfect binary trees $\mathcal{N}_{n}$’s correspond to the number of nodes at
different generations. Yet, the number of those nodes without any offspring
(called leaves) is of utmost importance in the upcoming section. The number of
leaves at generation $n$ is a random variable $\mathcal{L}_{n}$ and it is
formally given by the following sum.

$\displaystyle\mathcal{L}_{n}=\sum_{i=1}^{\mathcal{N}_{n}}\mathds{1}_{L}(i),$

where $\mathds{1}_{L}(i)$ is an indicator function such that
$\mathds{1}_{L}(i)=1$ if $i$ belongs to the set of leaves
$\overline{L}\subset\\{\mathcal{N}_{n}\\}$ and is zero otherwise. The notation
$\\{\mathcal{N}_{n}\\}$ indicates the set of the population at the $n^{th}$
generation. The probability transition function for $\mathcal{L}_{n}$ is read
as

$\displaystyle\mathrm{Pr}(\mathcal{L}_{n}=i\,|\,,\mathcal{N}_{n}=j\wedge\mathcal{N}_{n-1}=k)=P(\mathcal{L}_{n}=i\,|\,\mathcal{N}_{n}=j)P(\mathcal{N}_{n}=j\,|\,\mathcal{N}_{n-1}=k).$
(10)

This implies that the probability of observing $i$ leaves at generation $n$ is
the joint probability of having $j$ nodes at the same generation given that
the number of nodes in the previous generation is $k$, and from those $j$
nodes $i$ of them are leaves i.e.

$\displaystyle
P(\mathcal{L}_{n}=i\,|\,\mathcal{N}_{n}=j\wedge\mathcal{N}_{n_{1}}=1)=$
$\displaystyle
P(\mathcal{L}_{n}=i\,|\,\mathcal{N}_{n}=j)P(\mathcal{N}_{n}=j\,|\,\mathcal{N}_{n-1}=1)=\binom{j}{i}u_{1}^{i}u_{0}^{j-i}p_{j}.$

Here $u_{1}$ is the probability of being a leaf whilst $u_{0}$ is the
probability of not being a leaf. The notation $\binom{j}{i}$ stands on
choosing $i$ elements from $j$ elements. Multiply both sides by
$\xi^{j}\zeta^{i}$ and sum over $i$ and $j$ and arrive at the following.

$\displaystyle\sum_{i,j}P(\mathcal{L}_{n}=i\,|\,\mathcal{N}_{n}=j)P(\mathcal{N}_{n}=j\,|\,\mathcal{N}_{n-1}=1)=$
$\displaystyle\sum_{j}p_{j}\xi^{j}\sum_{i}\binom{j}{i}u_{1}^{i}u_{0}^{j-i}\zeta^{i}=\sum_{j}p_{j}[\xi(u_{1}\zeta+u_{0})]^{j}=f\big{(}\xi
g(\zeta)\big{)},$ (11)

where $g(\zeta)=(u_{1}\zeta+u_{0})$ is the probability generating function of
the state of a single node being a leaf or not and $f\big{(}\xi
g(\zeta\big{)}$ is the _generalised probability generating function_ that
includes the information of both the number of nodes and leaves at a given
generation $n$.

The generalised probability generating function satisfies the same properties
that $f(\xi)$ exhibits. For instance

$\displaystyle f_{(n)}\big{(}\xi g(\zeta)\big{)}$
$\displaystyle=\sum_{i,j}P(\mathcal{L}_{n}=i\,|\,\mathcal{N}_{n}=j\wedge\mathcal{N}_{0}=1)\xi^{j}\zeta^{i}$
$\displaystyle=\sum_{i,j}P(\mathcal{L}_{n}=i\,|\,\mathcal{N}_{n}=j)P(\mathcal{N}_{n}=j\,|\,\mathcal{N}_{0}=1)\xi^{j}\zeta^{i}$
$\displaystyle=\sum_{i,j}P(\mathcal{L}_{n}=i\,|\,\mathcal{N}_{n}=j)\sum_{k}P(\mathcal{N}_{n}=i\,|\,\mathcal{N}_{n-1}=k)P(\mathcal{N}_{n-1}=k\,|\,\mathcal{N}_{0}=1)\xi^{j}\zeta^{i}$
$\displaystyle=\sum_{k}P(\mathcal{N}_{n-1}=k\,|\,\mathcal{N}_{0}=1)\left[f\big{(}\xi
g(\zeta)\big{)}\right]^{k}=f_{(n-1)}\left[f\big{(}\xi
g(\zeta)\big{)}\right]=f_{n}\big{(}\xi g(\zeta)\big{)},$ (12)

where the last term is followed by induction. The average number of leaves at
a given generation $n$ is achieved by taking the first order partial
derivative of $f_{(n)}\big{(}\xi g(\zeta)\big{)}$ with respect to $\zeta$

$\displaystyle\mathbb{E}[\mathcal{L}_{n}]$
$\displaystyle=\frac{\partial}{\partial\zeta}f_{(n)}\big{(}\xi
g(\zeta)\big{)}\Big{|}_{\xi=\zeta=1}=\frac{\partial}{\partial\zeta}f_{n}\big{(}\xi
g(\zeta)\big{)}\Big{|}_{\xi=\zeta=1}=\frac{\partial}{\partial\zeta}f[f_{n-1}\big{(}\xi
g(\zeta)\big{)}]\Big{|}_{\xi=\zeta=1}$
$\displaystyle=f^{\prime}\left[f_{n-1}\big{(}\xi
g(\zeta)\big{)}\right]f^{\prime}_{n-1}\big{(}\xi g(\zeta)\big{)}\xi
g^{\prime}(\zeta)\Big{|}_{\xi=\zeta=1}$
$\displaystyle=u_{1}f^{\prime}(1)f^{\prime}_{n-1}(1)=u_{1}[f^{\prime}(1)]^{n}=u_{1}\mathbb{E}[\mathcal{N}_{n}]=u_{1}\mu^{n},$
(13)

where in the last line the identity that
$f^{\prime}_{n}(1)=[f^{\prime}(1)]^{n}$ derived in Eq. (7) is used. In a
similar fashion used in Eq. (8) the variance of $\mathcal{L}_{n}$ is deduced
to be

$\displaystyle\mathrm{Var}[\mathcal{L}_{n}]=u_{1}^{2}\mathrm{Var}[\mathcal{N}_{n}].$
(14)

###  2.2 The percolation process on perfect binary trees and the statistical
properties of $\mathcal{N}_{n}$ and $\mathcal{L}_{n}$

As previously mentioned, percolation process is equivalent to the Bienaymé
-Galton-Watson process discussed earlier. If one limits the number of
offspring of each node only to the set $\\{0,1,2\\}$, then one deals with the
percolation process on perfect binary trees. The fact that a node does not
have any offspring corresponds to the situation where the edges coming out of
that very node are both closed which corresponds to the probability $q^{2}$.
Likewise, the possibility of having only one offspring corresponds to the
situation where one edge is closed and the other one is open which implies the
probability $2pq$ and having exactly two offspring indicates that both edges
are open and the probability associated to this event is $p^{2}$. Hence one
identifies the probabilities $p_{0},p_{1}$ and $p_{2}$ with $q^{2},2pq$ and
$p^{2}$ respectively. Thus, the probability generating function $f(\xi)$ given
by Eq. (3) in closed form is written as

$\displaystyle
f(\xi)=\sum_{i=0}^{2}p_{i}\xi^{i}=q^{2}+2pq\xi+p^{2}\xi^{2}=(p\xi+q)^{2}.$
(15)

Moreover, a node is a leaf if the edges coming out of it are both closed,
corresponding to the probability $q^{2}$. Whilst, it is not a leaf if it has
at least one offspring which corresponds to the probability $2pq+p^{2}$.
Therefore, the probability generating function of leaves, namely $g(\zeta)$ is
given by

$\displaystyle g(\zeta)=\sum_{i=0}^{1}u_{i}\zeta^{i}=q^{2}\zeta+2pq+p^{2}.$
(16)

Using Eq. (15) and Eq. (16), the generalised probability generating function
$f\big{(}\xi g(\zeta)\big{)}$ is given by

$\displaystyle f\big{(}\xi g(\zeta)\big{)}=\sum_{i=0}^{2}p_{i}\big{(}\xi
g(\zeta)\big{)}^{i}=\big{(}p\xi g(\zeta)+q\big{)}^{2}.$ (17)

All the possible configurations of the nodes that this generalised probability
function generates are listed in Fig. 2. It is straightforward to calculate
the mean and variance of $\mathcal{N}_{1}$ thanks to Eq. (6a) and Eq. (6b),

$\displaystyle\mathbb{E}[\mathcal{N}_{1}]=\mu=\frac{\partial}{\partial\xi}f\big{(}\xi
g(\zeta)\big{)}\Big{|}_{\xi=\zeta=1}=2pq+2p^{2}=2p$ (18a)
$\displaystyle\mathrm{Var}[\mathcal{N}_{1}]=\frac{\partial^{2}}{\partial\xi^{2}}f\big{(}\xi
g(\zeta)\big{)}\Big{|}_{\xi=\zeta=1}-\mu^{2}+\mu=2p^{2}-(2p)^{2}+2p=2p(1-p)=2pq.$
(18b)

Figure 2: All possible configurations of nodes at $n=1$. Solid lines represent
edges that are open with probability $p$ and dashed lines represent edges that
are blocked with probability $q$. These are all the configurations that the
Eq. (17) generates.

Then due to Eq. (7) and Eq. (9) the followings are yielded

$\displaystyle\mathbb{E}[\mathcal{N}_{n}]=(\mathbb{E}[\mathcal{N}_{1}])^{n}=(2p)^{n},$
(19a)
$\displaystyle\mathrm{Var}[\mathcal{N}_{n}]=\begin{cases}\mathrm{Var}[\mathcal{N}_{1}]\mu^{n}\left(\frac{\mu^{n}-1}{\mu^{2}-\mu}\right)=q(2p)^{n}\left[\frac{(2p)^{n}-1}{2p-1}\right],&\text{if}\quad
p\neq 1/2\\\ n\mathrm{Var}[\mathcal{N}_{1}]=2npq=\frac{n}{2},&\text{if}\quad
p=1/2\end{cases}.$ (19b)

By virtue of equations (13) and (14) and the results of the equations above,
the mean and the variance of $\mathcal{L}_{n}$ are given by

$\displaystyle\mathbb{E}[\mathcal{L}_{n}]=q^{2}\mathbb{E}[\mathcal{N}_{n}]=q^{2}(2p)^{n},$
(20a)
$\displaystyle\mathrm{Var}[\mathcal{L}_{n}]=q^{2}\mathrm{Var}[\mathcal{N}_{n}]=\begin{cases}q^{3}(2p)^{n}\left[\frac{(2p)^{n}-1}{2p-1}\right],&\text{if}\quad
p\neq 1/2\\\ 2npq^{3}=\frac{n}{8},&\text{if}\quad p=1/2\end{cases}.$ (20b)

It is worthwhile to discuss for which $p$ the percolation cluster emerges. It
is clear that the emergence of the percolation cluster is associated to the
critical Bienaymé-Galton-Watson process. Equation (7) implies that when
$\mu<0$, the expectation value of $\mathcal{N}_{n}$ tends to zero as
$n\rightarrow\infty$ and for $\mu>0$, $\mathcal{N}_{n}$ diverges conversely.
Yet, for $\mu=1$, for all the generations, the expectation value remains
unity. This case implies that for the percolation process $p=1/2$, since
$\mu=2p=1$. Hence, for $p<1/2$ all the open clusters for a percolation process
on a perfect binary tree are finite in size and when $p>1/2$ a unique
percolation cluster exists. The value $p=1/2$ is also deducible by solving the
equation $\xi=f(\xi)$.

$\displaystyle(p\xi+q)^{2}=\;$
$\displaystyle\xi\rightarrow\xi=\frac{2p^{2}+1-2p-|1-2p|}{2p^{2}}$
$\displaystyle\xi=\begin{cases}1\quad&\mathrm{if}\quad p\leq 1/2,\\\
(q/p)^{2}\quad&\mathrm{if}\quad p>1/2\end{cases}.$

When $p<1/2$, the probability that the percolation cluster emerges is zero
whilst when $p>1/2$, the chance that it does not appear is given by
$(q/p)^{2}$ [7].

##  3 Maximal encoded information

The percolation clusters on perfect binary trees discussed in the previous
section are unquestionably related to the Huffman encoding scheme which is
used to efficiently encode symbols into strings of 0’s and 1’s
algorithmically. Binary encoding is the process of assigning a binary string
to a set of symbols. For instance, the English alphabets A to Z can be
represented by strings of 0’s and 1’s. An example of such an encoding
procedure is shown in Tab. 1.

Symbol | Encoded
---|---
A | 00000
B | 00001
C | 00010
D | 00011
⋮ | ⋮
Z | 11010
Table 1: One possible fixed-length encoding scheme for the English alphabets.

This encoding is called fixed-length encoding scheme [19]. Though convenient,
it is not the best and efficient encoding procedure as there are many
unnecessary 0’s and 1’s that are used to represent the symbols. Another
supplementary piece of information that indeed helps to make the encoding more
efficient is the fact that the English alphabets have different frequencies of
appearance in text sources. For instance, the letter $E$ with 12.02% has the
highest frequency of appearance and the letter $Z$ with 0.07% has the least.
Thus, it is logical to represents the letter $E$ with fewer bits of 0’s and
1’s, e.g. with only one single digit 0.

One defines an information source as an ordered pair $\mathcal{S}=(S,P)$ where
$S$ is the set of symbols e.g. $S=\\{s_{1},s_{2},\cdots,s_{n}\\}$ and $P$ is a
probability measure $P=\\{p_{s_{1}},p_{s_{2}},\cdots,p_{s_{n}}\\}$, where
$p_{s_{i}}$ is the probability of appearance of the symbol $s_{i}$ in the
source. An encoding scheme is then an ordered pair $\mathcal{E}=(C,f_{c})$
where $C$ is the set of codes e.g. $\\{00,01,000,101,\cdots\\}$ and $f_{c}$ is
the encoding function $f_{c}:S\rightarrow C$ which maps a symbol from the set
$S$ to a codeword in $C$. The average codeword length for an information
source $\mathcal{S}$ and the encoding scheme $\mathcal{E}$ is defined as

$\displaystyle
L=\sum_{i=1}^{n}p_{s_{i}}\mathrm{Len}\big{(}f_{c}(s_{i})\big{)},$ (21)

where $\mathrm{Len}\big{(}f_{c}(s_{i})\big{)}$ is the length of the codeword
associated with the symbol $s_{i}$ via the map $f_{c}(.)$.

The average codeword length is a quantity which its magnitude measures how
efficient an encoding scheme is. Obviously, the smaller the $L$ is, the more
efficient the encoding is as lesser bits of 0’s and 1’s are required to
represent the message formed by the set of the symbols. Note that $L$ cannot
be arbitrarily small as it is required that the encoding scheme $\mathcal{E}$
to be uniquely decipherable or even more desirable, to be instantaneous [19].
Huffman devised an algorithm which is now known after his name that yields the
most efficient encoding scheme ensuring that the scheme is instantaneous [5].
The lower bound for $L$ was proved to be the amount of the information in
$\mathcal{S}$ which is given by the Shannon’s entropy defined as [19]

$\displaystyle\mathcal{H}=-\sum_{i=1}^{n}p_{s_{i}}\log(p_{s_{i}})\leq L.$ (22)

###  3.1 Percolation cluster as an efficient encoding scheme

The percolation cluster, though not an encoding scheme per se, can be regarded
as encoding scheme which assign to a set of symbols (leaves) a set of
probabilities of appearance. Thus, one can say that the percolation cluster
contains the information source $\mathcal{S}$ and encodes it simultaneously
according to the following procedure

  1. (i)

every leaf represents a symbol which has a probability associated with
identified by the Bernoulli probability measure $\prod_{i}^{n}p$ where $n$ is
the generation at which the leaf resides.

  2. (ii)

the leaf is encoded as a binary string of length $n$. The string is generated
by mapping every turn to the left to the digit 0 and every turn to the right
to the digit 1 when traversing the open path from the root $\emptyset$ to the
leaf similar to the procedure in Huffman encoding.

To elaborate this further, consider an imaginary open cluster generated by an
arbitrary percolation process depicted in Fig. 3.

Figure 3: An open cluster with $n=4$ generated by some percolation process.
Only the open edges are shown. The leaves represents the symbols. Every edge
to the left can be represented by the bit 0 and to the right with 1.

In this figure the open cluster has 7 leaves at different generations. Every
leaf in that very process can be associated to a single symbol. One can
further intuitively assign to each symbol a unique codeword by traversing the
open path which starts at the root and ends at the symbol. Every turn to the
left represents the bit 0 and to the right the bit 1. Hence, the open cluster
automatically provides an encoding scheme $\mathcal{E}$ which maps the symbols
$S=\\{s_{1},s_{2},\cdots,s_{7}\\}$ according to the one-to-one correspondence
shown in Tab. 2.

Symbols | Codewords
---|---
$s_{1}$ | 00
$s_{2}$ | 0100
$s_{3}$ | 0101
$s_{4}$ | 1010
$s_{5}$ | 1011
$s_{6}$ | 110
$s_{7}$ | 1110
Table 2: Instantaneous encoding yielded by the open cluster in Fig. 3 yielded
by a percolation process.

This encoding is instantaneous. This is deduced by the fact that every
instantaneous encoding has binary tree representation (refer to [20] and the
Kraft’s and McMillan’s theorem for instance in [19]).

Since the appearance of each leaf is independent of the other leaves, a
natural Bernoulli probability measure can be associated to each leaf. Thus,
for instance, the symbol $s_{1}$ has the probability of appearance
proportional to $\prod_{i=0}^{2}p$ and the symbol $s_{7}$, $\prod_{i=0}^{4}p$.
Hence, the probability of the codewords is spontaneously yielded by the open
cluster with the extra caution that it has to be normalised.

Therefore, every open cluster generated via a percolation process is
inherently an encoding scheme in which the information source $\mathcal{S}$ is
the ordered pair of the set of symbols $S$ identified by the leaves and the
probability distribution $P$ which is identified by the Bernoulli measure
associated to the length of the open path starting from the root and ending at
the leaves. The codeword for each symbol is understood as the sequence of 0’s
and 1’s where the digit 0 represents the open edges to the left and the digit
1 represents the open edges to the right. Subsequently, the encoding function
$f_{c}$ is identified by the correspondence between the symbols and the
sequence of 0’s and 1’s which is yielded by traversing the open path from the
root to the leaf representing the symbol.

###  3.2 Encoding a countably infinite set of symbols

When the set of symbols $S$ is finite, given that $P$ is a probability measure
and the length of the codewords in $C$ is finite, the Shannon’s entropy and
the average codeword length are both well-defined and finite. Yet, a legit
question would be whether one can efficiently encode a set of symbols that is
countably infinite. As discussed earlier, a finite cluster formed when $p<1/2$
can be thought of an encoding scheme on a finite set of symbols. Au contraire,
when $p>1/2$ the percolation cluster emerges and the number of leaves goes to
infinity and hence one can consider the percolation cluster as an encoding
scheme on an infinite set of symbols. For a given realisation $\mathcal{C}$ of
a percolation cluster, the Shannon’s entropy Eq. (22) can be rewritten as
follows

$\displaystyle\mathcal{H}(\mathcal{C})=-\sum_{i=1}^{\infty}p\left(s_{i}\,|\,\mathcal{C}\right)\log_{2}\big{(}p(s_{i}\,|\,\mathcal{C})\big{)}=-\sum_{n=0}^{\infty}\mathcal{L}_{n}(\mathcal{C})p^{n}\log_{2}(p^{n}),$
(23)

where now instead of having the dummy index of the sum counting the index of
the symbols, it goes through different generations of the tree. The
probabilities are factorised by the number of leaves at every given generation
$n$. The problem here is that the set $P$ does not sum to unity and hence not
a probability measure. Hence, it is required to normalise the probabilities
i.e.

$\displaystyle\mathcal{H}(\mathcal{C})=-\sum_{n=0}^{\infty}\frac{\mathcal{L}_{n}(\mathcal{C})p^{n}}{\Lambda(\mathcal{C})}\log_{2}\left(\frac{p^{n}}{\Lambda(\mathcal{C})}\right),$
(24)

where
$\Lambda(\mathcal{C})=\sum_{n=0}^{\infty}\mathcal{L}_{n}(\mathcal{C})p^{n}$ is
the normalisation factor for a given configuration $\mathcal{C}$. Clearly,
$\Lambda(\mathcal{C})$ is a random variable that depends on the configuration
$\mathcal{C}$ . Therefore, taking the average of the entropy $H(\mathcal{C})$
involves taking average over $\Lambda(\mathcal{C})$ as well. Yet, observe that

$\displaystyle\mathbb{E}[\Lambda(\mathcal{C})]:=\lambda=\sum_{n=0}^{\infty}\mathbb{E}[\mathcal{L}_{n}(\mathcal{C})]p^{n}=q^{2}\sum_{n=0}^{\infty}(2p^{2})^{n}=\frac{q^{2}}{1-2p^{2}},\quad\text{when}\quad
1/2\leq p<\sqrt{1/2}$
$\displaystyle\mathrm{Var}[\Lambda(\mathcal{C})]=\sum_{n=0}^{\infty}\mathrm{Var}[\mathcal{L}_{n}]p^{n}=\frac{q^{3}}{2p-1}\sum_{n=0}^{\infty}(2p^{2})^{n}\left[(2p)^{n}-1\right]$
$\displaystyle\qquad=\frac{q^{3}}{2p-1}\left[\frac{1}{1-4p^{3}}-\frac{1}{1-2p^{2}}\right]=\frac{2p^{2}q^{3}}{(1-4p^{3})(1-2p^{2})}\quad\text{when}\quad
1/2\leq p<\sqrt[3]{1/4},$
$\displaystyle\mathrm{Var}[\Lambda(\mathcal{C})]=\sum_{n=0}^{\infty}\mathrm{Var}[\mathcal{L}_{n}]p^{n}=2pq^{3}\sum_{n=0}^{\infty}np^{n}=2qp^{2}=1/4\quad\text{when}\quad
p=1/2$

Therefore, as long as $1/2\leq p<\sqrt[3]{1/4}$ the mean and the variance of
$\Lambda$ are finite and well-defined. Thus, as $n\rightarrow\infty$ it is
sound to substitute $\Lambda(\mathcal{C})$ with its mean $\lambda$. This
allows one to rewrite Eq. (24) as follows

$\displaystyle\mathcal{H}(\mathcal{C})=-\sum_{n=0}^{\infty}\frac{\mathcal{L}_{n}(\mathcal{C})p^{n}}{\lambda}\log\left(\frac{p^{n}}{\lambda}\right).$
(25)

Consequently,

$\displaystyle\mathbb{E}[\mathcal{H}(\mathcal{C})]$
$\displaystyle=-\sum_{n=0}^{\infty}\frac{\mathbb{E}[\mathcal{L}_{n}(\mathcal{C})]p^{n}}{\lambda}\log\left(\frac{p^{n}}{\lambda}\right)=-\frac{q^{2}}{\lambda}\sum_{n=0}^{\infty}(2p^{2})^{n}\log(p^{n}/\lambda)$
$\displaystyle=-\frac{q^{2}}{\lambda}\Big{[}\sum_{n=0}^{\infty}n(2p^{2})^{n}\log(p)-\sum_{n=0}^{\infty}(2p^{2})^{n}\log(\lambda)\Big{]}=\frac{2p^{2}\log(1/p)}{1-2p^{2}}+\log(\lambda).$
(26)

Similarly, for the average codeword length,

$\displaystyle\mathbb{E}[L(\mathcal{C})]=\sum_{n=0}^{\infty}\frac{n\mathbb{E}[\mathcal{L}_{n}(\mathcal{C})]p^{n}}{\lambda}=\frac{q^{2}}{\lambda}\sum_{n=0}^{\infty}n(2p^{2})^{n}=\frac{2p^{2}}{1-2p^{2}}$
(27)

This demonstrates that the percolation cluster formed via the percolation
process on infinite perfect binary trees equipped with the Bernoulli
probability measure, encodes the leaves of the percolation cluster in such a
way that the entropy and the average codeword length remain finite, although
the number of leaves tend to infinity when $1/2\leq p<\sqrt[3]{1/4}$.

These results are also tested against the simulations. The simulation
procedure is such that an ensemble of perfect binary trees are generated up to
a maximum upper bound for the generation $n$ called the depth. Afterwards, the
edges of the trees are assigned to the state of being open with probability
$p$ and to the state of being closed with the probability $q=1-p$. This yields
a random forest of trees within one instance of simulation. The tree that
contains the root is sieved out as a realisation of the Bienaymé-Galton-Watson
process. Note that, the nodes that are lying at the maximum depth are not
considered as leaves.

Figure 4: (left) The average codeword length $\mathbb{E}[L]$ depicted by solid
lines and average entropy $\mathbb{E}[\mathcal{H}]$ depicted by dash lines
versus the percolation density $p$ for three different depths $n=7,12$ and
$16$. Note that when $p=1.0$ both quantities drop to zero since there are no
leaves present at $p=1.0$. This is expected since there is no information due
to randomness at this density. (right) The same quantities versus the maximum
depth $n$ for various percolation densities $p$. Again the solid lines
represent the average codeword length and the dashed lines represent the
average entropy. It is seen that both quantities are bounded as long as
$1/2\leq p<1/\sqrt[3]{4}$. For $p=0.7$ observe that they grow exponentially as
$n$ grows.

The simulation results are in agreement with the results yielded above. In
Fig. 4 on the left pane, the dependence of $\mathbb{E}[L]$ and
$\mathbb{E}[\mathcal{H}]$ on the maximum generation (depth) $n$ and the
percolation density $p$ are shown. It is observed that the average codeword
length and the average entropy versus $p$ monotonically increase until they
reach their maximum and then reach the value zero when $p=1.0$. This is due to
the fact that when $p=1.0$ there are no leaves that contribute to $L$ and
$\mathcal{H}$. Moreover, in the same figure on the right pane, the dependence
of $\mathbb{E}[L]$ and $\mathbb{E}[\mathcal{H}]$ on the depth of the
simulation is depicted. It is clear that so long $1/2\leq p<\sqrt[3]{1/4}$
both quantities remain finite. To make this stand out, the average codeword
length and the entropy at $p=0.7$ are plotted and it is seen that in contrast
to the other percolation densities, $\mathbb{E}[L]$ and
$\mathbb{E}[\mathcal{H}]$ grow exponentially. In Fig. 5 the average codeword
length and the entropy yielded by the simulation results are plotted against
their analytical expressions given by Eq. (26) and Eq. (27) respectively. The
dashed lines are the analytical expressions describing the asymptotic
behaviour of the aforementioned quantities in the limit of
$n\rightarrow\infty$. Obviously, there is a gap between the asymptotics
yielded by the simulation results due to the fact that while deriving the
expressions Eq. (26) and Eq. (27) it was assumed that $\Lambda(\mathcal{C})$
is a constant when $n\rightarrow\infty$ and hence substituted by its means.
Yet, for the simulation results, the normalisation factor $\Lambda$ is
calculated exactly. Nevertheless, it is still promising to indeed observe the
that the average codeword length and the average entropy both remain finite as
$n$ increases as long as $1/2\leq p<\sqrt[3]{1/4}$.

Figure 5: (left) The average codeword length for various percolation densities
$p$ versus the depth of the tree $n$. It is seen that $\mathbb{E}[L]$
saturates as long as $1/2\leq p<1/\sqrt[3]{4}$. (right) The same as the left
pain but for the average entropy $\mathbb{E}[\mathcal{H}]$ . The solid lines
represent the simulation results while the dashed lines are the saturation
plateaus predicted by the Eq. (27) and Eq. (26).

##  4 Conclusion

It is demonstrated here that a given percolation cluster generated via a
Bernoulli percolation process on a perfect binary tree can be regarded as an
encoding scheme with a set of symbols identified as the leaves of the cluster,
along with their associated probabilities satisfying the Bernoulli probability
measure. The codewords are simultaneously yielded by traversing the open paths
from the root of the tree to their respective leaves. It was proven that with
this very configuration, one can still have a set of infinite symbols and keep
the amount of the information and the average codeword length finite by
choosing the percolation density $p$ appropriately.

One of the aims of this paper was to show that a branching process as simple
as Bienaymé-Galton-Watson process could have potential applications in
computer science. It may have deep implications in how one algorithmically
encodes large data, stores, compresses and also importantly encrypts them.
Other non-trivial branching processes may be even found more crucial in
shaping our understanding of data integrity and storage or encryption methods
that are far challenging to be breached. Also the author wants to note that
the Bienaymé-Galton-Watson process has already been used to study some natural
processes. For instance in the electron multiplier detector or nuclear chain
reactions [21, 22]. Not only limited to these, other processes such as the
birth-death process which can be utilised to find the rate at which a new
species emerges [23]. It may be that the nature intrinsically encodes the
information in such a manner that the entropy remains bounded yet the possible
outcomes are infinitely many.

## Acknowledgement

The author wants to cordially thank Prof Aleksei Chechkin for his constructive
suggestions and critical views and Prof Stephan Foldes for initiating useful
discussions that shaped many of the building blocks of this article. The
author further expresses his gratitudes towards Prof Sylvie Roelly for her
constructive views and supports.

## References

  * [1] Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil.  The log-structured merge-tree (lsm-tree).  Acta Informatica, 33(4):351–385, 1996.
  * [2] Pradeep J Shetty, Richard P Spillane, Ravikant R Malpani, Binesh Andrews, Justin Seyster, and Erez Zadok.  Building workload-independent storage with vt-trees.  In 11th $\\{$USENIX$\\}$ Conference on File and Storage Technologies ($\\{$FAST$\\}$ 13), pages 17–30, 2013.
  * [3] Ohad Rodeh, Josef Bacik, and Chris Mason.  Btrfs: The linux b-tree filesystem.  ACM Transactions on Storage (TOS), 9(3):1–32, 2013.
  * [4] Goetz Graefe and Harumi Kuno.  Modern b-tree techniques.  In 2011 IEEE 27th International Conference on Data Engineering, pages 1370–1373. IEEE, 2011.
  * [5] David A Huffman.  A method for the construction of minimum-redundancy codes.  Proceedings of the IRE, 40(9):1098–1101, 1952.
  * [6] Henry William Watson and Francis Galton.  On the probability of the extinction of families.  The Journal of the Anthropological Institute of Great Britain and Ireland, 4:138–144, 1875.
  * [7] G. Grimmett.  Percolation.  Grundlehren der mathematischen Wissenschaften : a series of comprehensive studies in mathematics. Springer Verlag, 1989.
  * [8] Wolfgang Bauhofer and Josef Z Kovacs.  A review and analysis of electrical percolation in carbon nanotube polymer composites.  Composites science and technology, 69(10):1486–1498, 2009.
  * [9] Harry Kesten.  Percolation theory and first-passage percolation.  The Annals of Probability, 15(4):1231–1271, 1987.
  * [10] Ahmad Mardoukhi, Yousof Mardoukhi, Mikko Hokka, and Veli-Tapani Kuokkala.  Effects of heat shock on the dynamic tensile behavior of granitic rocks.  Rock mechanics and rock engineering, 50(5):1171–1182, 2017.
  * [11] Dietrich Stauffer.  Can percolation theory be applied to the stock market?  Annalen der Physik, 7(5-6):529–538, 1998.
  * [12] Yao Yu and Jun Wang.  Lattice-oriented percolation system applied to volatility behavior of stock market.  Journal of Applied Statistics, 39(4):785–797, 2012.
  * [13] Thomas Owen Richardson, Kim Christensen, Nigel Rigby Franks, Henrik Jeldtoft Jensen, and Ana Blagovestova Sendova-Franks.  Ants in a labyrinth: a statistical mechanics approach to the division of labour.  PLoS One, 6(4):e18416, 2011.
  * [14] Paulo FF Almeida, Winchil LC Vaz, and TE Thompson.  Lateral diffusion and percolation in two-phase, two-component lipid bilayers. topology of the solid-phase domains in-plane and across the lipid bilayer.  Biochemistry, 31(31):7198–7210, 1992.
  * [15] Kingo Kobayashi, Hiroyoshi Morita, and Mamoru Hoshi.  Percolation on a k-ary tree.  In General Theory of Information Transfer and Combinatorics, pages 633–638. Springer, 2006.
  * [16] Søren Asmussen, Heinrich Hering, et al.  Branching processes, volume 3.  Springer, 1983.
  * [17] Theodore Edward Harris et al.  The theory of branching processes, volume 6.  Springer Berlin, 1963.
  * [18] Michael Drmota.  Distribution of the height of leaves of rooted trees.  Diskretnaya Matematika, 6(1):67–82, 1994.
  * [19] Steven Roman.  Introduction to coding and information theory.  Springer Science & Business Media, 1996.
  * [20] S Cortes Reina, Stephan Foldes, Yousof Mardoukhi, and Navin M Singhi.  Note on islands in path-length sequences of binary trees.  arXiv preprint arXiv:1409.3855, 2014.
  * [21] W Shockley and JR Pierce.  A theory of noise for electron multipliers.  Proceedings of the Institute of Radio Engineers, 26(3):321–332, 1938.
  * [22] D Hawkins and S Ulam.  Theory of Multiplicative Process, volume 287.  Atomic Energy Commission, 1946.
  * [23] George Udny Yule.  Ii.—a mathematical theory of evolution, based on the conclusions of dr. jc willis, fr s.  Philosophical transactions of the Royal Society of London. Series B, containing papers of a biological character, 213(402-410):21–87, 1925\.