# Minimizing the kinematical effects on LISA’s performance

Ioannis Deligiannis  Theocharis A. Apostolatos  Section of Astronomy,
Astrophysics, and Mechanics
University of Athens
Panepistimiopolis, Zografos, GR-15783, Athens, Greece

###### Abstract

Proper tuning of the orbital characteristics of the three spacecrafts that
constitute the usual triangular configuration of the space-borne
gravitational-wave detector LISA, could minimize the breathing mode of its
arm-lengths. Since the three spacecrafts form three pairs of interferometric
arms, we have the freedom to minimize whichever combination of arm-length
variations that might be useful in signal analysis. Thus for any kind of time
delay interferometry (TDI), that is chosen to be used in analysing the data,
the optimal orbital characteristics could be chosen accordingly, so as to
enhance the performance of the gravitational wave detector.

###### pacs:

04.80.Nn

††preprint: APS/123-QED

##  I  Introduction

The joint ESA-NASA future mission to launch a spaceborne gravitational wave
antenna, known as LISA (Laser Interferometer Space Antenna), is expected to
offer us invaluable information for the Universe. The detector will be able to
monitor low frequency gravitational waves, the source of which could be either
supermassive black hole binaries at cosmological distances Schu86 ; CutlVali07
, white dwarf and/or neutron star binaries Ferretal , or primordial waves of
cosmological origin LISA ; ChonEfsta . Detection of such gravitational waves
could be achieved by placing three spacecrafts into three distinct Earth-like
orbits, so that they form an equilateral triangle of almost constant size
DhurNayaKoshVine , and monitoring interferometrically the tiny variations of
distances between any pair of such spacecrafts that are induced by
gravitational waves passing by LISA LISA1 . Since the frequency band that this
detector is sensitive at is in the region $10^{-4}$ to $10^{-1}$ Hz, any
possible relative motions of spacecrafts that occur at much lower frequencies
of order $\sim 10^{-7}$ Hz (due to orbital periodicities) could be filtered
out from the signal CornRubo ; 02TintEstaArms . However, despite the fact that
the large beat modes due to Doppler shifts caused by arm-length variations
could be effectively eliminated, the same arm-length variations could cause
unpleasant complications while attempting to reduce internal noise by various
schemes of time delay interferometry (known as TDI’s) TDI ; ValiTDI . This
happens because, while the laser beams travel back and forth across the arms,
they pass through each spacecraft at different times due to arm-length
changes; thus any reference frequency variations of local lasers do not
exactly cancel out in the corresponding combination of signals, as it would
happen if there was no flexing of the arms. Consequently, if the variability
of the size of the triangular formation could be minimized by suitable
adjustment of their orbital characteristics, this would lead to a suppression
of the internal noise of LISA, which, in its turn, would be highly beneficial
for its performance as a gravitational wave detector.

We start by writing down the position of each spacecraft, accurate up to
second order with respect to its eccentricity. Each spacecraft moves on a
slightly elliptical orbit with semi-major axis equal to 1 AU, the plane of
which is slightly inclined with respect to the plane of the ecliptic. Finally
the orbit of each spacecraft is rotated by an angle of $\pm 2\pi/3$, with
respect to the other two orbits, on the ecliptic plane. The initial position
of the three spacecrafts on their corresponding orbits is such that they form
an equilateral triangle that remains equilateral to first order with respect
to the eccentricity $e$ of the orbits. The proposed configuration of LISA,
that is widely used in corresponding analyses DhurNayaKoshVine , assumes that
the plane of the triangular configuration forms an exact $60^{\circ}$ angle
with respect to the ecliptic plane, with the triangle being exactly
equilateral initially. Indeed this configuration ensures stable distances
between spacecrafts to first order with respect to the eccentricity of the
orbits $e$. However, this configuration leads to a breathing mode of the arms
with amplitude of order $e^{2}$ NayaKoshDhurVine . This arm flexing end up
generating noise, by one way or another, in detector’s output DhurNayaKoshVine
; CornHell ; ValiTDI .

It is to verify that each spacecraft has 3 extra degrees of freedom that could
be used to minimize whichever arm-length variation might one choose. Of course
this fine tuning of the orbital characteristics should be one order of $e$
higher than the initially proposed value of the characteristics themselves, so
that the invariance of the arm-lengths to order $e$ is not destroyed. These
nine, altogether, degrees of freedoms could be chosen to be the eccentricities
of the orbits, their inclinations, and the initial angle position of each
spacecraft along its own slightly eccentric and inclined orbit. The choice
could be such that the initial configuration deviates from being equilateral
to order $e$, and/or its plane inclination deviates from the $60^{\circ}$ to
order $e$, as well. On the other hand such an adjustment could reduce the
time-variation of any arm-length, or the relative variation of any pair of
arm-lengths, at its minimum value.

The rest of the paper is organized as follows. In Sec. II we repeat the basic
calculations, in a form that could be later extended to higher order with
respect to $e$, that show why the initially designed configuration leads to a
time-independent equilateral triangular configuration to order $e$. By
expanding the spacecraft distances to order $e^{2}$, we compute the time
variation of the arm-lengths at this order. In Sec. III we introduce nine
extra parameters of order $e^{2}$ that modify the initial positions of the
three spacecrafts. Then we calculate once again the distances between each
pair of spacecrafts as a function of time, which are now parametrized by the
six (out of nine) essential parameters that determine the initial location of
the spacecrafts. Finally, in Sec. IV we show how we could optimally choose the
fine tuning parameters so as to get the minimum contribution to noise from the
variations of the arm-lengths, depending on the TDI scheme that one might
choose to use in signal extraction.

##  II The initially designed orbits

The orbit of each spacecraft is a Keplerian ellipse, if one ignores the
gravitational attraction due to planets (mainly Earth, and Jupiter) and
relativistic effects. Assuming that all spacecrafts are moving on orbits that
have semi-major axis of 1 AU, so that all return at their initial positions
after one year, and are not drifting away secularly with respect to Earth,
their distance from the Sun could be written as

$\displaystyle r=a(1+e\cos\xi)$ (1)

where $a$, the semi-major axis, is common for all spacecrafts and is equal to
1 AU. The eccentricity, $e$, is common for all spacecrafts, as well, for the
proposed configuration and is the only parameter that uniquely characterizes
all three orbits (see below). Finally, $\xi$ is the so called eccentric
anomaly, which is an angle parameter that determines the position of the
spacecraft along its elliptical orbit. Now the orbital plane of each
spacecraft is inclined with respect to the ecliptic plane by an angle $\lambda
e$, where $\lambda$ is a number that will be determined by demanding the
configuration of the three spacecrafts to be an equilateral triangle with
invariant size to first order with respect to $e$. The three inclined orbital
planes are rotated by an angle of $\pm 2\pi/3$, with respect to each other, on
the ecliptic plane (see Fig. 1). By using the eccentric anomaly to describe
the position of each spacecraft along its orbit, instead of the polar angle
$\theta$, the calculations that lead to the distance between two spacecrafts
as a function of time are made easier since by conservation of angular
momentum the angular position $\theta$ on a keplerian orbit as a function of
time is given by

$\displaystyle
t=\int_{\theta_{0}}^{\theta(t)}\frac{d\theta}{\dot{\theta}}=\frac{ma^{2}(1-e^{2})^{2}}{L}\int_{\theta_{0}}^{\theta(t)}\frac{d\theta}{(1-e\cos\theta)^{2}},$
(2)

while by using the eccentric anomaly parameter $\xi$ which is related to
$\theta$ via

$\displaystyle 1+e\cos\xi\equiv\frac{1-e^{2}}{1-e\cos\theta},$ (3)

the cartesian coordinates of the orbital position are

$\displaystyle\begin{split}x&=&r\cos\theta=a(\cos\xi+e),\\\
y&=&r\sin\theta=a\sqrt{1-e^{2}}\sin\xi,\end{split}$ (4)

and the integral of Eq. (2) is easily computed to yield

$\displaystyle\xi-\xi_{0}+e(\sin\xi-\sin\xi_{0})=\frac{L}{ma^{2}\sqrt{1-e^{2}}}t=\omega
t,$ (5)

(c.f. Landau ). The last expression is easier to use, than Eq. (2), to compute
$t(\xi)$, in contrast to $t(\theta)$. The above transcendental equation could
not be exactly inverted in a closed analytical form. However, this could be
achieved in the form of a power expansion with respect to $e$, yielding

$\displaystyle\xi=\omega t+\xi_{0}$ $\displaystyle+$
$\displaystyle\left(\sin(\omega t+\xi_{0})-\sin\xi_{0}\right)\times$ (6)
$\displaystyle\left(-e+e^{2}\cos(\omega t+\xi_{0})+O(e^{3})\right).$

The cartesian coordinates of each spacecraft on the heliocentric system, with
the $z$-axis perpendicular to the ecliptic plane, are thus given by

$\displaystyle{\bf x}^{(i)}=R^{(i)}_{\textrm{rot}}R^{(i)}_{\textrm{inc}}{\bf
x}^{(i)}_{\textrm{op}}$ (7)

where ${\bf x}^{(i)}_{\textrm{op}}$ is the position of the $i$-th spacecraft
on its orbital plane, that is

$\displaystyle{\bf
x}^{(i)}_{\textrm{op}}=\left(\begin{array}[]{c}r^{(i)}\cos\theta^{(i)}\\\
r^{(i)}\sin\theta^{(i)}\\\
0\end{array}\right)=\left(\begin{array}[]{c}a(e+\cos\xi^{(i)})\\\
a\sqrt{1-e^{2}}\sin\xi^{(i)}\\\ 0\end{array}\right)$ (14)

where the expressions in the last array come from Eqs. (4). The matrix
$R^{(i)}_{\textrm{inc}}$ produces an inclination of the orbital plane by an
angle $\lambda e$ with respect to ecliptic plane around $y$-axis. Therefore,

$\displaystyle R^{(i)}_{\textrm{inc}}=\left(\begin{array}[]{ccc}\cos(\lambda
e)&0&\sin(\lambda e)\\\ 0&1&0\\\ -\sin(\lambda e)&0&\cos(\lambda e)\\\
\end{array}\right).$ (18)

Finally, $R^{(i)}_{\textrm{rot}}$ is the matrix that rotates the orbit of the
$i$-th spacecraft by $\Phi_{1}=0,\Phi_{2}=2\pi/3$, and $\Phi_{3}=4\pi/3$,
respectively, on the ecliptic plane, that is

$\displaystyle
R^{(i)}_{\textrm{rot}}=\left(\begin{array}[]{ccc}\cos\Phi_{i}&\sin\Phi_{i}&0\\\
-\sin\Phi_{i}&\cos\Phi_{i}&0\\\ 0&0&1\end{array}\right).$ (22)

By combining the coordinates of each spacecraft given above, and choosing the
initial angular positions $\xi^{(i)}_{0}$ (the superscript (i) refers to the
$i$-th spacecraft) to be

$\displaystyle(\xi^{(1)}_{0},\xi^{(2)}_{0},\xi^{(3)}_{0})=(0,\frac{2\pi}{3}-\frac{\sqrt{3}}{2}e,\frac{4\pi}{3}+\frac{\sqrt{3}}{2}e),$
(23)

along with the common inclination parameter $\lambda=\sqrt{3}$, we obtain the
following time depending distance of each pair of spacecrafts to second order
with respect to $e$:

$\displaystyle r_{12}(t)$ $\displaystyle=$ $\displaystyle
2\sqrt{3}ae-\frac{\sqrt{3}}{32}\left(19\cos(\omega t)-19\sqrt{3}\sin(\omega
t)-2\cos(3\omega t)\right)ae^{2}+O(e^{3}),$ (24) $\displaystyle r_{23}(t)$
$\displaystyle=$ $\displaystyle
2\sqrt{3}ae+\frac{\sqrt{3}}{16}\left(7\cos(\omega t)+\cos(3\omega
t)\right)ae^{2}+O(e^{3}),$ (25) $\displaystyle r_{31}(t)$ $\displaystyle=$
$\displaystyle 2\sqrt{3}ae-\frac{\sqrt{3}}{32}\left(19\cos(\omega
t)+19\sqrt{3}\sin(\omega t)-2\cos(3\omega t)\right)ae^{2}+O(e^{3}).$ (26)

The choice of initial parameters for the three spacecrafts, mentioned above,
is the one that leads to the essential advantage of the configuration; that is
to keep the distances equal, and time-invariant to lowest order (first order)
with respect to parameter $e$. However, the arm-lengths vary with time to
order $e^{2}$. The magnitude of the arm-length oscillation is thus of order
$10^{4}$ km as shown in Figure 2.

Figure 1: The figure depicts the orbits of the three spacecrafts labeled 1, 2,
and 3 respectively. The triangular configuration is shown at an instance when
spacecraft 1 is at its aphelion ($\theta_{1}=0$) while the other spacecrafts
are located at angles $\theta_{2}=2\pi/3+{\cal O}(e)$, and
$\theta_{3}=4\pi/3+{\cal O}(e)$, respectively. The three elliptical orbits are
inclined with respect to the ecliptic plane (shown in the figure); thus the
part of the ellipses that lie above the ecliptic plane are drawn thicker than
the parts that lie below. Also the three orbits are rotated with respect to
each other by exactly $\pm 2\pi/3$, as shown in the figure. The inclinations
and the eccentricities presented in this figure are highly exaggerated to
clearly illustrate the geometry of the orbits. Figure 2: This diagram shows
the variation of the three arm-lengths for the configuration of LISA that was
initially designed. The range of arm-lengths’ variation is $6.6\times 10^{4}$
km, for $r_{13}$, and $r_{12}$, and $2.1\times 10^{4}$ km, for $r_{23}$,
respectively. The first two pairs have similar time evolution due to symmetric
arrangements of the corresponding sides of the equilateral triangle. Actually
$r_{12}(t)=r_{13}(-t)$, if $t=0$ corresponds to configuration shown in Figure
2.

##  III  Lowering the amplitude of arm flexing

In this section we will use our freedom of choosing the initial positioning of
the three spacecrafts, in order to minimize whichever distance variation we
might like. Of course by placing two spacecrafts on a circular orbit around
the Sun the distance between them will remain fixed, but in order to sense the
quadrupole nature of a gravitational wave we need al least one more spacecraft
that is not along the same line of the former two ones. Thus, by placing a
third spacecraft in an orbit that is inclined with respect to the orbit the
other pair, we will have a time varying arm-length between the third and each
one of the other two spacecrafts, the overall variation of which will be of
the order of the initial arm-length. The clever symmetric configuration of the
three slightly inclined and slightly non-circular orbits that was discussed in
the previous section manages to keep all the arm-lengths constant, at least at
the order of magnitude of the arm-lengths themselves. On the other hand by
trying to achieve a very symmetric configuration we have ignored any possible
freedom we still have to shift our orbits so as to reduce the variation of
distances to even higher order.

Speaking of freedom of initial positioning, the three elliptical orbits could
be a little different, with respect to eccentricity and with respect to
inclination, with each other. Of course the fine tuning of the corresponding
six parameters will be of order $e^{2}$, so as to keep the main characteristic
of the configuration; namely the constant value of the arm-lengths at order
$e$. Furthermore one could also loosen the exact symmetric placement of the
orbits by a rotating angle of $\pm 2\pi/3$ with respect to each other. However
these angles could be kept invariant, and we could alternatively adjust the
initial angular positions $\xi^{(i)}_{0}$ to order $e^{2}$.

Henceforth we will assume that the three orbits are characterized by the
following orbital parameters:

$\displaystyle\begin{array}[]{ccc}e_{1}=e,&e_{2}=e+\alpha_{2}e^{2},&e_{3}=e+\alpha_{3}e^{2},\\\
\lambda_{1}=\sqrt{3}+\beta_{1}e,&\lambda_{2}=\sqrt{3}+\beta_{2}e,&\lambda_{3}=\sqrt{3}+\beta_{3}e.\end{array}$
(29)

We have actually chosen the eccentricity of the first spacecraft’s orbit as a
reference for the other two. This eccentricity will play the role of the small
expansion parameter in all positional expressions. Next we define the initial
positions of the spacecrafts along these slightly deformed, and differently
inclined orbits by the initial angles

$\displaystyle\begin{split}&\xi^{(1)}_{0}=0,\\\
&\xi^{(2)}_{0}=\frac{2\pi}{3}-\frac{\sqrt{3}}{2}e+\gamma_{2}e^{2},\\\
&\xi^{(3)}_{0}=\frac{4\pi}{3}+\frac{\sqrt{3}}{2}e+\gamma_{3}e^{2},\end{split}$
(30)

where once again by setting $\xi^{(1)}_{0}$ equal to zero, we have just
adjusted the initial time of the configuration to coincide with the aphelion
of spacecraft 1. As we see now there are only 7 parameters that we could tune
to make the configuration comply with our demands. The assumed shifts of the
orbital parameters of the three spacecrafts are independent to each other, and
thus they exhaust the whole freedom we have to shift the initial positions of
the spacecrafts.

Actually the proposed configuration that forms initially an exact equilateral
triangle inclined by $60^{\circ}$ with respect to the equatorial orbit
corresponds to some specific relations between these 7 new parameters since,
as is shown in Figure 2, omission of all these parameters does not lead to
three equal arm-lengths at $t=0$.

Repeating once again the computations of the previous section with all seven
new parameters introduced in the formulae for ${\bf x}_{\textrm{op}}^{(i)}$,
$R_{\textrm{inc}}^{(i)}$, and $\xi^{(i)}_{0}$, we obtain the following
expressions for the three distances as functions of time:

$\displaystyle\left(\begin{array}[]{c}r_{12}(t)\\\ r_{31}(t)\\\
r_{23}(t)\end{array}\right)=2\sqrt{3}ae\left(\begin{array}[]{c}1\\\ 1\\\
1\end{array}\right)+\frac{ae^{2}}{32\sqrt{3}}{\bf A}(t)+\textrm{O}(e^{3})$
(37)

with

$\displaystyle{\bf A}(t)={\bf C}_{0}+{\bf C}_{1}\cos(\omega t)+{\bf
C}_{2}\cos(2\omega t)+{\bf C}_{3}\cos(3\omega t)+{\bf S}_{1}\sin(\omega
t)+{\bf S}_{2}\sin(2\omega t).$ (38)

The $3\times 1$ column matrices ${\bf C}_{k}$’s and ${\bf S}_{k}$’s, through
which we have decomposed the time-depending second-order column matrix ${\bf
A}(t)$, correspond to the following expressions that depend only on the seven
fine-tuning parameters introduced above:

$\displaystyle\begin{array}[]{cc}{\bf
C}_{0}=12\left(\begin{array}[]{c}8\alpha_{2}+\sqrt{3}(\beta_{1}+\beta_{2})\\\
8\alpha_{3}+\sqrt{3}(\beta_{1}+\beta_{3})\\\
8(\alpha_{2}+\alpha_{3})+\sqrt{3}(\beta_{2}+\beta_{3})\end{array}\right),{\bf
C}_{1}=\left(\begin{array}[]{c}-57-8(3\alpha_{2}+2\sqrt{3}\gamma_{2})\\\
-57-8(3\alpha_{3}-2\sqrt{3}\gamma_{3})\\\
42-16(3(\alpha_{2}+\alpha_{3})+2\sqrt{3}(\gamma_{2}-\gamma_{3}))\end{array}\right),\\\
{\bf C}_{2}=12\sqrt{3}\left(\begin{array}[]{c}\beta_{1}\\\ \beta_{1}\\\
-(\beta_{2}+\beta_{3})\end{array}\right),{\bf
C}_{3}=6\left(\begin{array}[]{c}1\\\ 1\\\ 1\end{array}\right),\\\ {\bf
S}_{1}=3\left(\begin{array}[]{c}19\sqrt{3}+8\sqrt{3}\alpha_{2}+16\gamma_{2}\\\
-19\sqrt{3}-8\sqrt{3}\alpha_{3}+16\gamma_{3}\\\ 0\end{array}\right),{\bf
S}_{2}=12\left(\begin{array}[]{c}\beta_{1}+2\beta_{2}\\\
-\beta_{1}-2\beta_{3}\\\ \beta_{2}-\beta_{3}\end{array}\right).\end{array}$
(60)

An obvious optimization choice of parameters is
$\beta_{1}=\beta_{2}=\beta_{3}=0$, since then the component of the variation
of arms that oscillates at frequency $2\omega$ vanishes (${\bf C}_{2}={\bf
S}_{2}={\bf 0}$) without affecting the rest time-depending components ${\bf
C}_{1},{\bf C}_{3},{\bf S}_{1}$. On the other hand the only component of arm-
length oscillation with frequency $3\omega$ cannot be adjusted through
suitable choice of the parameters. Finally the magnitude of the components
corresponding to frequency $\omega$ could be adjusted by varying the value of
specific combinations of $\alpha_{2},\gamma_{2}$, and $\alpha_{3},\gamma_{3}$.
More specifically by using the following replacements

$\displaystyle\begin{split}\chi_{2}&=57+8(3\alpha_{2}+2\sqrt{3}\gamma_{2}),\\\
\chi_{3}&=57+8(3\alpha_{3}-2\sqrt{3}\gamma_{3}),\end{split}$ (61)

where the two new parameters $\chi_{2},\chi_{3}$ could be adjusted
independently to each other, the lowest-order arm-length variations
oscillating at frequency $\omega$ turn out to be

$\displaystyle\frac{ae^{2}}{32\sqrt{3}}\left(\left(\begin{array}[]{c}-\chi_{2}\\\
-\chi_{3}\\\ 156-(\chi_{2}+\chi_{3})\end{array}\right)\cos(\omega
t)+\right.\left.\sqrt{3}\left(\begin{array}[]{c}\chi_{2}\\\ -\chi_{3}\\\
0\end{array}\right)\sin(\omega t)\right)=$ (68)
$\displaystyle\frac{ae^{2}}{32\sqrt{3}}\left(\begin{array}[]{c}2\chi_{2}\cos(\omega
t-2\pi/3)\\\ 2\chi_{3}\cos(\omega t-4\pi/3)\\\
\left[156-(\chi_{2}+\chi_{3})\right]\cos(\omega t)\end{array}\right).$ (72)

Therefore, all possible optimizations could be done by suitable adjustments of
$\chi_{2},\chi_{3}$ alone, that is, by simultaneous adjustments of
$\alpha_{i}$’s and $\gamma_{i}$’s. For example, by choosing
$\chi_{2}=\chi_{3}=0$, two out of three arms are oscillating with the lowest
possible amplitude, which is a mere $5\%$ of the amplitude of the initially
designed configuration. The price though is that then the third arm is
oscillating with an amplitude that is $\sim 3.4$ times higher than the
corresponding amplitude of the initial configuration. On the other hand if we
need to use all arms in our signal analysis, we could make a compromise by a
suitable choice of $\chi_{i}$’s and manage to decrease the oscillation
amplitude of all arms at an optimized ratio. In Figure 3, we have plotted the
time-varying arm-lengths in a period of one year, for two choices of
$\chi_{i}$’s.

Figure 3:  This diagram shows the time varying length of the three arms when
the orbital characteristics of the three spacecrafts are a little bit
different than the ones of the initial design. The left diagram shows the
extreme case $\chi_{2}=\chi_{3}=0$, where two of the arms are oscillating at a
small fraction of the oscillation amplitude of the initial configuration (only
by $0.2\times 10^{4}$ km in amplitude), while the third arm is oscillating
with an amplitude which is more than 3 times larger than the amplitude in the
initial configuration. The right diagram shows a more balanced fine tuning of
the parameters ($\chi_{2}=\chi_{3}=39$) where all arms are oscillating with an
amplitude $\sim 60\%$ lower than the maximum amplitudes of initial
configuration.

##  IV Reducing the noise in various TDI schemes

The optimal geometric configuration, that we could achieve by suitable initial
positioning of the three spacecrafts, depends on the specific TDI (time delay
interferometry) scheme that we decide to use in order to extract the signal
from the internal noise of local lasers in each spacecraft. For example, if we
had chosen to synthesize the phase-differences in an equal-arm four-link
Michelson scheme interferometry (see TDI ; ValiTDI ) the noise induced by the
breathing mode of the arms would be

$\displaystyle 2{\dot{C}}_{1}(t)(L_{2}(t)-L_{3}(t)),$ (73)

assuming that the spacecraft 1 is the corner station of the corresponding
Michelson interferometer. $L_{i}(t)$ is the time depending length of the
$i$-th arm, while $C_{i}(t)$ describes the time-dependent fluctuations of the
$i$-th laser frequency (assuming there is only one reference laser in each
spacecraft). The lasers of LISA mission are designed to have single-sided
spectral density of order $30~{}\textrm{Hz}/\sqrt{\textrm{Hz}}$. The initial
configuration has a time varying arm-length difference which has an amplitude
of $3.3\times 10^{4}~{}\textrm{km}$ (c.f. Figure 2). On the other hand in the
optimized configuration with $\chi_{2}=\chi_{3}=0$ although these two arms
actually breathe, they have continuously exactly the same length (at least to
order $e^{2}$ which corresponds to our approximations). The same holds good
also for an unequal-arm eight-link Michelson combination, denoted X by
Armstrong, Estabrook, and Tinto ArmsEstaTint99 , which is a second-generation
TDI scheme ValiTDI , since the antisymmetric combination
$\dot{L}_{2}L_{3}-\dot{L}_{3}L_{2}$ is again continuously zero (to the same
order of approximation), and thus the internal laser noises cancel out (c.f.
Eq. (12) of ValiTDI ).

Let us examine one more second-generation TDI scheme that is, now, not
symmetric with respect to a specific pair of arms. For example, the eight-link
Relay scheme, denoted U in ArmsEstaTint99 , leads to the following TDI noise
due to laser internal noise:

$\displaystyle{\dot{C}}_{3}(t)[({\dot{L}}_{1^{\prime}}+{\dot{L}}_{1})(L_{3^{\prime}}+L_{2^{\prime}})-({\dot{L}}_{3^{\prime}}+{\dot{L}}_{2^{\prime}})(L_{1^{\prime}}+L_{1})+{\dot{L}}_{1}L_{1^{\prime}}-{\dot{L}}_{1^{\prime}}L_{1}].$
(74)

By expressing the three arm-lengths as $L_{i}=L_{i^{\prime}}=L_{0}+l_{i}(t)$
where $L_{0}$ is of order $ae$ while $l_{i}(t)$ is of order $ae^{2}$ and the
numbering is such that it corresponds to the $i$-th component of the column
matrix of Eq. (72) the above expression for the noise yields

$\displaystyle{\dot{C}}_{3}(t)\frac{2L_{0}ae^{2}\omega}{32\sqrt{3}}[(156+\chi_{2}-2\chi_{3})\sin\omega
t+\sqrt{3}(2\chi_{2}+\chi_{3})\cos\omega t]+\textrm{O}(e^{4}).$ (75)

To compute the above expression, only the Fourier components corresponding to
frequency $\omega$ has been written down, since the Fourier component of arm
breathing with frequency $3\omega$ is the same for all arms (c.f. ${\bf
C}_{3}$ of Eq. (60)), and the corresponding terms cancel out. From expression
(75) it is easy to verify that by choosing $\chi_{2}=-156/5$ and
$\chi_{3}=312/5$ we could nullify the noise of this TDI scheme to this order;
namely $a^{2}e^{3}$. It should be noted that the specific choice of numbering
of the arms with respect to the assumed distance $r_{ij}$ that we have used in
our analysis leads to the specific optimizing parameter values $\chi_{2,3}$
that we have found.

Actually, all second generation eight-link TDI schemes lead to similar
expressions for the noise, which could be written as antisymmetric products of
arm-length variations and arm-lengths ValiTDI . These products could be
expressed as a combination of $\sin\omega t$ and $\cos\omega t$ terms with
corresponding factors that depend on the two parameters $\chi_{2,3}$.
Therefore there is always a suitable combination of the $\chi_{2,3}$
parameters that eliminates the noise to that order, which means that by
suitable fine initial positioning of the three spacecrafts we could depress
the laser noise at the level of ${\dot{C}}a^{2}e^{4}\omega$. This is the best
optimization we could achieve for a specific second generation eight-link TDI
scheme based on the kinematics of LISA. As an order of magnitude, this means a
reduction in the noise of LISA by $e\simeq 1/100$ with respect to a non-
optimizing positioning of the spacecrafts.

##  V Conclusions

In this short paper we have shown that we could adjust the orbital
characteristics of the three spacecrafts which consist LISA detector at one
order, with respect to $e$, higher than what is initially designed, in order
to achieve specific kinematical properties. Namely, we could make the
breathing mode of detector arms be optimized with respect to noise induced in
the signal through any TDI scheme used to reduce the noise implications. We
have shown, by presenting a few examples, that suitable initial positioning of
the three spacecrafts could reduce the noise, due to lasers, by two orders of
magnitude with respect to initial design. We should note though that since the
positioning of spacecrafts could not be changed throughout mission’s lifetime,
only a specific TDI could be highly optimized. If another TDI scheme is used
simultaneously to analyze some signal the benefits of the fine-tuned
kinematics will not be equally highlighted. Hence the choice of kinematics
should be based on the TDI scheme that will be most often used in signal
analysis.

###### Acknowledgements.

This research was supported by Grant No 70/4/7672 of the Special Account for
Research Grants of the University of Athens.

## References

  * (1) B. F. Schutz, Nature 323 (1986) 310.
  * (2) C. Cutler, M. Vallisneri Phys. Rev. D 76 (2007) 104018.
  * (3) R. Schneider, V. Ferrari, S. Matarrese, S. F. Portegies Zwart Mon. Not. Roy. Astron. Soc. 324 (2001) 797.
  * (4) P. Bender,P. Danzmann, and the LISA Study Team (1998) “Laser Interferometer Space Antenna for the Detection of Gravitational Waves, Pre-Phase A Report” MPQ 233 (Garching: Max- Planck-Instit ut f ur Quantenoptik).
  * (5) S. Chongchitnan, G. Efstathiou Phys. Rev. D 73 (2006) 083511.
  * (6) S. V. Dhurandhar, K. R. Nayak, S. Koshti, and J. Y. Vinet, Class. Quantum Grav. 22 481 (2005).
  * (7) “LISA: A Cornerstone Mission for the Observation of Gravitational Waves”, System and Technology Study Report (2000).
  * (8) M. Tinto, F. B. Estabrook, and J. W. Armstrong Phys. Rev. D. 65 (2002) 082003.
  * (9) N. J. Cornish, L. J. Rubbo Phys. Rev. D 67 (2003) 022001; Erratum-ibid. D 67 (2003) 029905.
  * (10) J. W. Armstrong, F. B. Estabrook, and M. Tinto Ap. J. 527 (1999) 814.
  * (11) M. Vallisneri Phys.Rev. D, 72 (2005) 042003.
  * (12) K. R. Nayak, S. Koshti, S. V. Dhurandhar, and J. Y. Vinet preprint arXiv:gr-qc/0507105.
  * (13) N. J. Cornish, R. W. Hellings Class. Quant. Grav. 20 (2003) 4851-4860.
  * (14) L. D. Landau, and E. M. Lifshitz, Mechanics, Addison-Wesley, Reading, MA 1960.
  * (15) J. W. Armstrong, F B. Estabrook, and M. Tinto, Astrophys. J. 527 (1999) 814.


# On the Symmetries of the Deletion Channel ††thanks: Work partially supported
by CURIS 2021.

Francisco Pernice  Stanford University
<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider a class of symmetry groups associated to
communication channels, which can informally be viewed as the transformations
of the set of inputs that “commute” with the action of the channel. These
groups were first studied by Polyanskiy in [1]. We show the simple result that
the input distribution that attains the maximum mutual information for a given
channel is a “fixed point” of its group. We conjecture (and give empirical
evidence) that the channel group of the deletion channel is extremely small
(it contains a number of elements constant in the blocklength). We prove a
special case of this conjecture. This serves as some formal justification for
why the analysis of the binary deletion channel has proved much more difficult
than its memoryless counterparts.

###### Index Terms:

channel symmetries, groups, deletion channel.

##  I Introduction

Many natural models of communication errors, like those captured by the class
of discrete memoryless channels, are by now well understood. Their capacity
has been known since Shannon’s original paper [2], and codes with efficient
encoding and decoding algorithms have been proved to achieve the capacity
(e.g., [3]). By contrast, other similarly natural error models, like those
captured by the _binary deletion channel_ or other synchronization channels,
are much less well understood. For example, the capacity of the deletion
channel is unknown, although several lower and upper bounds have been proved
[4, 5, 6, 7]. In this paper, we work towards an answer to the following
question: can we give formal justification for why the binary deletion channel
is so much more difficult to analyze than, say, the binary symmetric channel?
In a talk in 2008, Mitzenmacher [8] gave the following example to illustrate
the difference between the two. Consider the strings

$s_{1}=00000,\qquad s_{2}=01010.$

From the point of view of the binary deletion channel, these two strings seem
quite different: for example, deleting any one bit from $s_{1}$ will produce
the same output, while deleting different single bits from $s_{2}$ will
produce all different outputs. On the other hand, from the point of view of
the binary symmetric channel, these two strings seem “equivalent,” in the
sense that there is no clear formal way to distinguish them in terms of the
consequences that bit flips have on them. Mitzenmacher went on to say that
“erasure and error channels have pleasant symmetries; deletion channels do
not” and that “understanding this asymmetry seems fundamental” [8].

In this paper, we consider a symmetry group
$\mathcal{G}_{\operatorname{\mathsf{Ch}}}$ associated to any given
communication channel $\operatorname{\mathsf{Ch}}$, which can informally be
viewed as the set of transformations of the set of inputs that “commute” with
the action of the channel. These groups were first studied in the context of
nonasymptotic coding converse bounds by Polyanskiy [1], but as far as we know,
have never been applied to the deletion channel. For a general class of
channels, we show the simple result that the distribution over the inputs that
maximizes the mutual information between the input and output of a given
channel is a “fixed point” of the action of the channel’s group. This is
analogous to Polyanskiy’s results [1] on the invariance under these group
actions of the distributions which solve minimax problems at the heart of
finite-length channel coding converse results [9]. These invariance theorems
motivate the study of these groups as a coarse measure of the “hardness” of a
channel: for channels with large symmetry groups, one can vastly simplify
capacity calculations, while for asymmetric channels, one gets no such
assistance.

We compare the cases of the binary symmetric channel (BSC) and binary deletion
channel (BDC). The case of the BSC was already studied by Polyanskiy [1]; we
mainly treat it here to introduce our notation and for contrast with the case
of the BDC, which is our main focus. We conjecture (and give empirical
evidence) that the channel group of the BDC is extremely small (it contains a
number of elements constant in $n$); this is in contrast with memoryless
channels, whose group size was shown by Polyanskiy [1] to grow at least like
$n!$ (by virtue of a natural inclusion
$\iota:S_{n}\xhookrightarrow{}\mathcal{G}_{\operatorname{\mathsf{Ch}}}$ for
$\operatorname{\mathsf{Ch}}$ memoryless). We prove a special case of our
conjecture: within the class of symmetries given by permutations of the
indices, $\mathcal{G}_{\operatorname{\mathrm{BDC}}}$ has only two elements.

Given the channel group, one can define the natural induced notion of
equivalence between strings: we say strings $s_{1}$ and $s_{2}$ are equivalent
if they lie on the same orbit of the channel group action on $\\{0,1\\}^{n}$,
i.e. if there exists a group element mapping $s_{1}$ to $s_{2}.$ In this
formal sense, the two example strings given by Mitzenmacher are equivalent
with respect to the binary symmetric channel, but not with respect to the
binary deletion channel. More generally, given any code $\mathcal{C}$ for a
channel, applying any group element to all its codewords yields a new code
$\mathcal{C}^{\prime}$ that is “equivalent” to $\mathcal{C}$ in a formal
sense: $\mathcal{C}$ and $\mathcal{C}^{\prime}$ have the same number of
codewords, and the existence of a decoder for $\mathcal{C}$ implies the
existence of a decoder for $\mathcal{C}^{\prime}$ with the same error
probability, and vice versa.

###  I-A Correction

A prior version of this manuscript incorrectly claimed that channel groups
were first defined in this work. We thank anonymous reviewers for their
helpful comments, which led the author to the work of Polyanskiy [1] where, as
discussed above, channel groups had already been defined and studied in a
different context. Moreover, the prior version contained a theorem regarding
the uniqueness of the channel group for channel families forming homogeneous
Markov chains; the proof had a bug, so the result has been removed.

##  II Definitions

###  II-A Notation and Elementary Definitions

Throughout this paper, for $\mathcal{X}$ a set (alphabet), $\mathcal{X}^{n}$
denotes the set of strings of $n$ symbols from $\mathcal{X};$ we also let
$\mathcal{X}^{*}=\bigcup_{j=0}^{\infty}\mathcal{X}^{j}$ and $\mathcal{X}^{\leq
n}=\bigcup_{j=0}^{n}\mathcal{X}^{j}$. For $x\in\mathcal{X}^{n},$ we let
$x_{i}^{j}\in\mathcal{X}^{j-i+1}$ denote the substring of $x$ starting at
index $i$ and ending at $j,$ inclusive; unless otherwise specified, we let
$x_{i}:=x_{i}^{i}$. If $\mathcal{X}$ can naturally be viewed as a field, we
use $x\in\mathcal{X}^{n}$ to refer to the vector space element or the string
interchangeably. For $x,y\in\mathcal{X}^{*},$ we let $xy$ denote their
concatenation. For $x\in\mathcal{X}^{n},$ we let $|x|=n$ denote the string
length. All logs (hence entropies, etc.) in this paper are of base equal to
the alphabet size unless otherwise specified.

To treat symmetry groups of general channels, it will be useful to view a
channel as acting on strings of arbitrary length.

######  Definition II.1.

For $\Omega$ a probability space and $\mathcal{X},\mathcal{Y}$ sets
(alphabets),111In this paper, we take all alphabets to be finite. a channel is
a map
$\operatorname{\mathsf{Ch}}:\mathcal{X}^{*}\times\Omega\to\mathcal{Y}^{*}.$
For $x\in\mathcal{X}^{*},$ we write $\operatorname{\mathsf{Ch}}x$ for the
random variable $\omega\mapsto\operatorname{\mathsf{Ch}}(x,\omega).$

For completeness, we give definitions of memoryless channels, the binary
symmetric channel and the binary deletion channel in this notation.

######  Definition II.2.

A channel
$\operatorname{\mathsf{Ch}}:\mathcal{X}^{*}\times\Omega\to\mathcal{Y}^{*}$ is
_memoryless_ if $x\in\mathcal{X}$ implies
$\operatorname{\mathsf{Ch}}x\in\mathcal{Y}$ with probability 1, and for
$x\in\mathcal{X}^{n}$ we have
$\operatorname{\mathsf{Ch}}x\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(\operatorname{\mathsf{Ch}}^{1}x_{1})\dots(\operatorname{\mathsf{Ch}}^{n}x_{n}),$
where $\stackrel{{\scriptstyle\mathcal{D}}}{{=}}$ denotes equality in
distribution and the $\operatorname{\mathsf{Ch}}^{i}$ are independent copies
of $\operatorname{\mathsf{Ch}}.$

######  Definition II.3.

Let $\mathcal{X}=\mathcal{Y}=\\{0,1\\},p\in[0,1],$ and
$\Omega=\\{0,1\\}^{\infty}$ (the infinite product space) with a
$Bernoulli(p)^{\infty}$ measure (the infinite product measure). The _binary
symmetric channel_ acts on an input $x\in\\{0,1\\}^{n}$ as
$\operatorname{\mathrm{BSC}}_{p}(x,\omega)=x+\omega_{1}^{n},$ where addition
is elementwise and mod 2. The _binary deletion channel_ acts on an input
$x\in\\{0,1\\}^{n}$ as
$\operatorname{\mathrm{BDC}}_{p}(x,\omega)=x_{i_{1}}x_{i_{2}}\dots x_{i_{k}},$
where $|x|-k$ is the hamming weight of (number of ones in) $\omega_{1}^{n}$,
and $i_{j}$ is the index of the $j$th zero in $\omega.$

It will sometimes be useful to consider the action of the channel only on
strings of a particular length.

######  Definition II.4.

Let $\operatorname{\mathsf{Ch}}:\mathcal{X}^{*}\times\Omega\to\mathcal{Y}^{*}$
be a channel, $n\in\mathbb{N},$ and let
$\operatorname{\mathsf{Ch}}|_{n}:\mathcal{X}^{n}\times\Omega\to\mathcal{Y}^{*}$
be the restriction of $\operatorname{\mathsf{Ch}}$ to the strings of length
$n$. Suppose there exists $k=k(n)\in\mathbb{N}$ such that the image of
$\operatorname{\mathsf{Ch}}|_{n}$ is contained in $\mathcal{Y}^{\leq k}.$ In
that case let $m=m(n)$ the minimal such $k$. Then the _$n$ th transition
matrix of $\operatorname{\mathsf{Ch}}$_ is the linear map
$M_{n}:\mathbb{R}^{\mathcal{X}^{n}}\to\mathbb{R}^{\mathcal{Y}^{\leq m}}$
giving the transition probabilities of $\operatorname{\mathsf{Ch}}|_{n}.$

Finally we define the automorphism group of a set; the channel symmetry groups
we will study will be _subgroups_ of the automorphism group of the message
set.

######  Definition II.5.

Given a set $A$, the _automorphism group_ of $A$, denoted $\mathsf{Aut}(A),$
is the set of bijections from $A$ to itself.

In the case where $A$ is finite, we have $\mathsf{Aut}(A)\cong S_{|A|},$ the
group of permutations of $|A|$ elements.

###  II-B Channel Symmetry Groups

Given a channel $\operatorname{\mathsf{Ch}}$ over an alphabet $\mathcal{X}$,
we consider the subgroup of elements of $\mathsf{Aut}(\mathcal{X}^{*})$ which
“commute with $\operatorname{\mathsf{Ch}}$.”

######  Definition II.6.

Given a channel
$\operatorname{\mathsf{Ch}}:\mathcal{X}^{*}\times\Omega\to\mathcal{Y}^{*}$, we
let the _channel group_ of $\operatorname{\mathsf{Ch}}$ be defined as

$\displaystyle\mathcal{G}_{\operatorname{\mathsf{Ch}}}=\\{g\in\mathsf{Aut}(\mathcal{X}^{*}):\exists
h\in\mathsf{Aut}$
$\displaystyle(\mathcal{Y}^{*}),\;(h\operatorname{\mathsf{Ch}}g)x\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\operatorname{\mathsf{Ch}}x,$
$\displaystyle|g(x)|=|x|\;\forall x\in\mathcal{X}^{*}\\},$

where $\stackrel{{\scriptstyle\mathcal{D}}}{{=}}$ denotes equality in
distribution, and by the conjugation $(h\operatorname{\mathsf{Ch}}g)x$ we mean
the random variable $\Omega\ni\omega\mapsto
h(\operatorname{\mathsf{Ch}}(g(x),\omega)).$

######  Remark II.7.

In the case where $\mathcal{X}=\mathcal{Y},$ in many channels of interest one
can fix $h=g^{-1}$ without loss of generality. In that case
$\mathcal{G}_{\operatorname{\mathsf{Ch}}}$ is _exactly_ the set of bijections
that commute (in the sense of equality in distribution) with
$\operatorname{\mathsf{Ch}}.$

The above definition is a special case of the one given in Section VI.A of
[1]; our definition differs from that one in the following two ways:

  1. 1.

In [1], the domain and range of the channels in question are not required to
have a product-like structure, or even to be countable.

  2. 2.

In [1], the group elements are not required to preserve string length.

Both of these assumptions hold automatically for many channels and symmetries
of interest. The first one will simplify our proofs; the second one will allow
us to have a well-defined notion of how the group “grows” with the
blocklength:

######  Definition II.8.

For each $n,$ consider the restrictions of the elements of
$\mathcal{G}_{\operatorname{\mathsf{Ch}}}$ to $\\{0,1\\}^{n}$, to obtain a
group
$\mathcal{G}_{\operatorname{\mathsf{Ch}}}^{n}\subseteq\mathsf{Aut}(\\{0,1\\}^{n})$
with a (not necessarily canonical) inclusion
$\mathcal{G}_{\operatorname{\mathsf{Ch}}}^{n}\xhookrightarrow{}\mathcal{G}_{\operatorname{\mathsf{Ch}}}$.
We say that the size of the channel group
$\mathcal{G}_{\operatorname{\mathsf{Ch}}}$ at blocklength $n$ is
$|\mathcal{G}_{\operatorname{\mathsf{Ch}}}^{n}|.$

It’s an elementary exercise to check that II.6 indeed defines a group in the
formal sense; we include a proof in the appendix for completeness:

######  Lemma II.9.

The channel group $\mathcal{G}_{\operatorname{\mathsf{Ch}}}$ is a group.

Given the channel group $\mathcal{G}_{\operatorname{\mathsf{Ch}}},$ we can
define the natural induced notion of equivalence between strings.

######  Definition II.10.

Given two strings $x,y\in\mathcal{X}^{*}$ and a channel
$\operatorname{\mathsf{Ch}}$ over the alphabet $\mathcal{X}^{*},$ we say $x$
and $y$ are _equivalent with respect to_ $\operatorname{\mathsf{Ch}}$, and
write $x\sim y,$ if there exists
$g\in\mathcal{G}_{\operatorname{\mathsf{Ch}}}$ such that $gx=y.$ We then
define the equivalence class of $x\in\mathcal{X}^{*}$ as
$[x]=\\{x^{\prime}\in\mathcal{X}^{*}:x^{\prime}\sim x\\}.$

It’s again an elementary exercise to check that this defines an equivalence
relation in the formal sense, and hence partitions the space of messages
$\mathcal{X}^{*}$ into a new set of disjoint equivalent classes (or _orbits_)
$(\mathclose{\mathcal{X}^{*}}/\mathopen{\sim})=\\{[x]:x\in\mathcal{X}^{*}\\},$
called the _quotient space_ of $\mathcal{X}^{*}$ by $\sim.$ We remark that,
given a code $\mathcal{C}=\\{\mathcal{C}_{n}\\}_{n\in\mathbb{N}}$ for
$\operatorname{\mathsf{Ch}}$, where $\mathcal{C}_{n}\subseteq\mathcal{X}^{n}$,
and a group element $g\in\mathcal{G}_{\operatorname{\mathsf{Ch}}},$ we can
define a new code $g\mathcal{C}=\\{g\mathcal{C}_{n}\\}_{n\in\mathbb{N}},$
where by $g\mathcal{C}_{n}$ we mean $\\{gc:c\in\mathcal{C}_{n}\\}.$ The code
$g\mathcal{C}$ can be decoded on the channel $\operatorname{\mathsf{Ch}}$ by
applying $g^{-1}$ to the received message, and then using any decoder for
$\mathcal{C}$; by the definition of
$\mathcal{G}_{\operatorname{\mathsf{Ch}}},$ this new decoder will have the
same probability of error as the decoder for $\mathcal{C}.$

##  III Invariance Theorem

As a simple general result, we show that, for a wide class of channels, the
distribution over the input strings that achieves the maximum mutual
information between input and output is a fixed point of the action of the
channel group. As was mentioned, this is a similar flavor of result to Theorem
20 in [1], but in the setting of channel capacity instead of finite
blocklength performance minimax bounds. As we illustrate in Section IV, the
conditions of the following theorem apply broadly.

######  Theorem III.1.

Let $\operatorname{\mathsf{Ch}}$ be a channel. Suppose the $n$th transition
matrix $M_{n}$ of $\operatorname{\mathsf{Ch}}$ exists and is full-rank. If we
have

$\mathcal{D}\in\operatorname*{arg\,max}_{\mathcal{D}^{\prime}}I(X^{\prime};Y^{\prime}),$

where $X^{\prime}\sim\mathcal{D}^{\prime}$ and
$Y^{\prime}=\operatorname{\mathsf{Ch}}X^{\prime}$, then
$gX\stackrel{{\scriptstyle\mathcal{D}}}{{=}}X$ for $X\sim\mathcal{D}$ for all
$g\in\mathcal{G}_{\operatorname{\mathsf{Ch}}}$. Above, the maximum is taken
over all probability distributions $\mathcal{D}^{\prime}$ supported on
$\mathcal{X}^{n}.$

We relegate the proof to the appendix. We remark that, by Shannon’s Theorem
[2], for memoryless channels $\operatorname{\mathsf{Ch}}$, if $\mathcal{D}$ is
the mutual-information-maximizing distribution from the theorem above and
$X\sim\mathcal{D},Y=\operatorname{\mathsf{Ch}}X$, then $\frac{1}{n}I(X;Y)$ is
the capacity of $\operatorname{\mathsf{Ch}},$ for every $n.$ Even for non-
memoryless channels like the deletion channel or other synchronization
channels, Dobrushin [10] proved that the capacity is given by the limit of
$\frac{1}{n}I(X;Y)$ as $n\to\infty.$ Informally, Theorem III.1 shows that,
when looking for the distribution that achieves capacity, we can restrict
attention to the distributions which “respect the symmetries of the channel.”
The following corollary, which follows immediately from Theorem III.1, makes
this more concrete.

######  Corollary III.2.

If $\mathcal{D}$ is the mutual-information-maximizing distribution of Theorem
III.1, then $\mathcal{D}$ is uniform when restricted to the subsets of
$\mathcal{X}^{n}$ that are equivalence classes with respect to
$\operatorname{\mathsf{Ch}}.$

In other words, if $x,y\in\mathcal{X}^{n},x\sim y$ with respect to
$\operatorname{\mathsf{Ch}}$, and $X\sim\mathcal{D},$ then
$\mathbb{P}(X=x)=\mathbb{P}(X=y).$ Hence maximizing the mutual information
over all distributions in $\mathcal{X}^{n}$ is equivalent to maximizing it
over the smaller quotient space
$(\mathclose{\mathcal{X}^{n}}/\mathopen{\sim}).$ In particular, if we have a
sufficiently large channel group, our variational problem III.1 can reduce to
a polynomial, or even constant number of variables, as it’s easy to see occurs
for memoryless channels [1].

##  IV Examples and Conjecture

In this section, we compare the examples of the binary symmetric channel and
binary deletion channel, we give our conjecture, and we prove a simple special
case. The case of the BSC was treated in [1], but here we re-derive what we
need for completeness and to introduce the ideas that will carry over to the
case of the BDC.

###  IV-A Binary Symmetric Channel [1]

In order for Theorem III.1 to apply, we need to show that the
$\operatorname{\mathrm{BSC}}$’s $n$th transition matrix $M_{n}$ is full-rank.

######  Lemma IV.1.

For every $n$ and $p\in(0,1/2)$, the $n$th transition matrix of the
$\operatorname{\mathrm{BSC}}_{p}$ is full-rank.

###### Proof.

This follows automatically from the fact that the transition matrix for a
single bit $M_{1}$ is clearly full-rank, and that $M_{n}=M_{1}^{\otimes n}$ by
the memoryless property. ∎

We now give two families of examples of elements in
$\mathcal{G}_{\operatorname{\mathrm{BSC}}}.$ These examples were already given
by Polyanskiy [1]. In each case, we only specify the action of the group
element on strings of a particular length $n.$ A general group element may be
formed by any choice a fixed-length transformation per string length.

  1. 1.

_Any permutation of the indices._ This is in fact a subgroup of the channel
group of any memoryless channel, as is easily verified.

  2. 2.

_Translation by any element._ Fix an element $x\in\\{0,1\\}^{n}$ and consider
the transformation $y\mapsto y+x,$ where addition is elementwise and mod 2.
This is clearly an element of $\mathcal{G}_{\operatorname{\mathrm{BSC}}}$ with
inverse equal to itself.

While there may be other families of transformations, just the transformations
of type (2) suffice to show that any two strings of the same length are
equivalent with respect to the $\operatorname{\mathrm{BSC}}.$ Namely, for
$y,z\in\\{0,1\\}^{n}$, letting $x=z-y,$ the map $w\mapsto w+x$ maps $y$ to
$z$, and hence $y\sim z.$ Then $[x]=\\{0,1\\}^{n}$ for every
$x\in\\{0,1\\}^{n}$ and from Corollary III.2 we recover the classical result
that the maximum mutual information in the $\operatorname{\mathrm{BSC}}$ is
achieved by a uniform distribution over the input. Finally, we note that, just
by considering transformations of type (1),
$\mathcal{G}_{\operatorname{\mathrm{BSC}}}$ grows at least like $n!$, in the
sense of Definition II.8, and hence grows faster than any exponential
function. This will be in stark contrast with the case of the
$\operatorname{\mathrm{BDC}}$, which we now consider.

###  IV-B Binary Deletion Channel

We check the applicability of Theorem III.1 by showing that the $n$th
transition matrix of the $\operatorname{\mathrm{BDC}}$ is full-rank.

######  Lemma IV.2.

For every $n$ and $p\in(0,1)$, the $n$th transition matrix of the
$\operatorname{\mathrm{BDC}}_{p}$ is full-rank.

###### Proof.

For $x\in\\{0,1\\}^{n},$ let $\vec{x}\in\mathbb{R}^{\\{0,1\\}^{n}}$ be the
probability vector with a $1$ in the coordinate corresponding to $x$, and
zeros in all other coordinates. It suffices to show that
$\\{M_{n}\vec{x}\\}_{x\in\\{0,1\\}^{n}}$ are linearly independent. But note
that, for $y\in\\{0,1\\}^{n},$ the $y$th coordinate of $M_{n}\vec{x}$ is
nonzero if and only if $x=y$, and hence they are clearly linearly independent.
∎

As before, we now give two examples of elements of
$\mathcal{G}_{\operatorname{\mathrm{BDC}}};$ it’s trivial to verify that these
are indeed in the channel group.

  1. 1.

_A flip of all bits._ This is the same as translation by the all-ones string.

  2. 2.

_A rotation about the center._ This is the transformation $x_{1}x_{2}\dots
x_{n}\mapsto x_{n}x_{n-1}\dots x_{1}.$

Each of these operations are of order 2 (they are their own inverses), and
they commute. Hence the group they generate is of size 4. Amazingly, we
conjecture that these are _all_ the symmetries of the
$\operatorname{\mathrm{BDC}}$! More precisely, these symmetries certainly
generate a _subgroup_ of $\mathcal{G}_{\operatorname{\mathrm{BDC}}};$ call
this subgroup $\widetilde{\mathcal{G}}_{\operatorname{\mathrm{BDC}}}.$ Then
two strings $x$ and $y$ are equivalent with respect to
$\widetilde{\mathcal{G}}_{\operatorname{\mathrm{BDC}}}$ if there is
$g\in\widetilde{\mathcal{G}}_{\operatorname{\mathrm{BDC}}}$ (i.e. either a
flip of all bits or a rotation around the center, or their composition, or the
identity) such that $gx=y.$ We conjecture that any two strings
$x,y\in\\{0,1\\}^{n}$ are equivalent with respect to
$\mathcal{G}_{\operatorname{\mathrm{BDC}}}$ if and only if they are equivalent
with respect to $\widetilde{\mathcal{G}}_{\operatorname{\mathrm{BDC}}}.$ This
in particular would imply the following concise statement.

######  Conjecture IV.3.

The size of any equivalence class (orbit) of $\\{0,1\\}^{n}$ under the action
of the channel group of the BDC is at most 4, independently of $n.$

In other words, when searching for the distribution that achieves capacity,
while in the case of the $\operatorname{\mathrm{BSC}}$ symmetry suffices to
solve the problem, in the case of the $\operatorname{\mathrm{BDC}}$ it
_essentially buys us nothing_.

To justify our conjecture, we note that if two strings $x,y\in\\{0,1\\}^{n}$
are equivalent with respect to the $\operatorname{\mathrm{BDC}}_{d},$ then
since by definition of equivalence there is a group element such that
$g^{-1}\operatorname{\mathrm{BDC}}_{1/2}y\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\operatorname{\mathrm{BDC}}_{1/2}x,$
in particular we must have
$H(\operatorname{\mathrm{BDC}}_{1/2}y)=H(\operatorname{\mathrm{BDC}}_{1/2}x).$222Here
the choice of $d=1/2$ is of course arbitrary; the channel group should be
invariant to the parameter, as long as $d\in(0,1).$ In the data files
available in arXiv together with this paper, we show numerically that for
string lengths $n$ up to 14, the equivalence classes under
$\widetilde{\mathcal{G}}_{\operatorname{\mathrm{BDC}}}$ coincide exactly with
the sets of strings of equal entropy when passed through the
$\operatorname{\mathrm{BDC}}_{1/2}.$

We now prove a simple but significant special case of our conjecture. Let
$\mathsf{Perm}(\\{0,1\\}^{*})$ be the subgroup of
$\mathsf{Aut}(\\{0,1\\}^{*})$ of all $h\in\mathsf{Aut}(\\{0,1\\}^{*})$ that
act on $\\{0,1\\}^{n}$ by a permutation of the indices. Specifically, for
$h\in\mathsf{Aut}(\\{0,1\\}^{*})$, we have $h\in\mathsf{Perm}(\\{0,1\\}^{*})$
if and only if for all $n\in\mathbb{N}$, there exists a permutation
$\pi_{n}:[n]\to[n]$ such that for all $x\in\\{0,1\\}^{n}$, we have

$h(x)=x_{\pi_{n}(1)}x_{\pi_{n}(2)}\dots x_{\pi_{n}(n)}.$

We note that in the case of the BSC (and memoryless channels more generally
[1]), we have
$\mathcal{G}_{\operatorname{\mathrm{BSC}}}\cap\mathsf{Perm}(\\{0,1\\}^{*})=\mathsf{Perm}(\\{0,1\\}^{*}),$
and of course $\mathsf{Perm}(\\{0,1\\}^{*})$ grows like $n!$, in the sense of
Definition II.8. By contrast, we prove the following.

######  Proposition IV.4.

If
$g\in\mathcal{G}_{\operatorname{\mathrm{BDC}}}\cap\mathsf{Perm}(\\{0,1\\}^{*}),$
then $g$ is either a rotation about the center, in the sense of (2), or the
identity.

Before proving the proposition, we prove a useful lemma. We use the following
notation: for $i\in[n]$, we let $\mathsf{ne}_{n}(i):=\\{i-1,i+1\\}\cap[n]$ be
the indices neighboring $i.$

######  Lemma IV.5.

A symmetry $h\in\mathsf{Perm}(\\{0,1\\}^{*})$ is either a rotation about the
center or the identity if and only if we have the following local property for
all $n$:

$j\in\mathsf{ne}_{n}(i)\iff\pi_{n}(j)\in\mathsf{ne}_{n}(\pi_{n}(i))\quad\forall
i\neq j\in[n].$

###### Proof.

Clearly if $h$ is a rotation about the center or the identity, then it
satisfies (IV.5) for all $n$. For the other direction, we proceed by induction
on the blocklength $n$. For $n=1,2,$ our thesis holds trivially. For $n\geq
3,$ property (IV.5) implies the following on the first $n-1$ indices:

$j\in\mathsf{ne}_{n}(i)\iff\pi_{n}(j)\in\mathsf{ne}_{n}(\pi_{n}(i))\quad\forall
i\neq j\in[n-1],$

which implies that $\pi_{n}([n-1])$ is contiguous, and hence equal to $[n-1]$
or $[n]\setminus\\{1\\}.$ After a shift by $-1$ in the latter case, we can
identify the restriction $\pi|_{[n-1]}$ with a permutation
$\widetilde{\pi}_{n-1}:[n-1]\to[n-1].$ Property (IV-B) for $\pi_{n}$ clearly
implies property (IV.5) for $\widetilde{\pi}_{n-1}$. Hence by inductive
hypothesis, $\widetilde{\pi}_{n-1}$ is either the identity or a rotation about
the center. Going back to $\pi_{n},$ we have the following two cases:

  1. 1.

If $\pi_{n}([n-1])=[n-1],$ then $\widetilde{\pi}_{n-1}$ cannot be a rotation
about the center, or else condition (IV.5) is violated at $i=n.$ Hence
$\widetilde{\pi}_{n-1}=\pi_{n}|_{[n-1]}$ is the identity and $\pi(n)=n,$ so
$\pi_{n}$ is the identity as well.

  2. 2.

If $\pi_{n}([n-1])=[n]\setminus\\{1\\},$ then $\widetilde{\pi}_{n-1}$ cannot
be the identity, or else condition (IV.5) is violated at $i=n.$ Hence
$\widetilde{\pi}_{n-1}=\pi_{n}|_{[n-1]}-1$ is a rotation about the center, and
since $\pi_{n}(n)=1,$ so is $\pi_{n}.$

This completes the proof. ∎

Now we can prove the proposition.

###### Proof of Proposition IV.4.

Let
$g\in\mathcal{G}_{\operatorname{\mathrm{BDC}}}\cap\mathsf{Perm}(\\{0,1\\}^{*}),$
and let $\pi_{n}:[n]\to[n]$ be the associated index permutations at each
blocklength. Suppose for contradiction that $g$ is neither the identity nor a
rotation about the center. Then by Lemma IV.5, we must have $n$ and $i\neq
j\in[n]$ such that $i$ and $j$ are neighbors but $\pi_{n}(i)$ and $\pi_{n}(j)$
are not. Assume without loss that $j=i+1$ and (by composing $\pi_{n}$ with a
rotation about the center on the _right_ if needed) that
$\pi_{n}(i)+1<\pi_{n}(i+1).$ Let $k\in[n]$ be such that
$\pi_{n}(i)<\pi_{n}(k)<\pi_{n}(i+1),$ and assume, again without loss (by
composing $\pi_{n}$ with a rotation about the center on the _left_ if needed),
that $k>i+1.$ Consider the string $x$ which is all-ones up to index $i+1,$
inclusive, and all-zeros afterwards (see Figure 1). We claim that
$|\mathsf{supp}(\operatorname{\mathrm{BDC}}_{d}x)|\neq|\mathsf{supp}(\operatorname{\mathrm{BDC}}_{d}gx)|$
for any $d$.333Here and below $\mathsf{supp}$ denotes the support of the
distribution. This of course automatically implies that there can be no
$h\in\mathsf{Aut}(\mathcal{Y}^{*})$ such that
$\operatorname{\mathrm{BDC}}_{d}x\stackrel{{\scriptstyle\mathcal{D}}}{{=}}h\operatorname{\mathrm{BDC}}_{d}gx,$
yielding a contradiction of $g\in\mathcal{G}_{\operatorname{\mathrm{BDC}}}$
and proving the proposition. To prove the claim, note first that, by a simple
calculation, we have
$|\mathsf{supp}(\operatorname{\mathrm{BDC}}_{d}x)|=(i+2)(n-i)$: there is
exactly one possible subsequence of $x$ for each valid choice of a number of
ones and a number of zeros in the output. Moreover since $g$ preserves string
weight, $x$ and $g(x)$ have the same total number of ones and zeros. Hence
$|\mathsf{supp}(\operatorname{\mathrm{BDC}}_{d}g(x))|\geq(i+2)(n-i)$ by the
same argument: there is a (now not necessarily unique) subsequence of $g(x)$
for each valid choice of a number of ones and a number of zeros in the output.
To show that the inequality is strict, it suffices to exhibit two indices
$s\neq t$ such that $g(x)_{s}=g(x)_{t}=1$, and such that deleting index $s$
(and nothing else) from $g(x)$ will produce a different output than deleting
index $t$. A moment of thought reveals that $s=\pi_{n}(i)$ and
$t=\pi_{n}(i+1)$ works, since they don’t lie in the same contiguous block of
ones by construction (see Figure 1).

Figure 1: An example of the string $x\in\\{0,1\\}^{n}$ used in our proof, and
the group element $g$ acting on it via the permutation $\pi_{n}$ of its
indices. The question marks denote bits of $g(x)$ which we cannot determine
just with our assumptions on $g.$

∎

##  V Acknowledgements

The author would like thank Ray Li, Mary Wootters and Marco Mondelli for
illuminating discussions and invaluable feedback on early versions of the
ideas presented in this paper. We also thank anonymous reviewers for their
comments, which led to the simplification of various proofs, and for pointing
our some errors and reference omissions (mentioned above) in a prior version
of this paper.

## References

  * [1] Y. Polyanskiy, “Saddle point in the minimax converse for channel coding,” _IEEE Transactions on Information Theory_ , vol. 59, no. 5, pp. 2576–2595, 2012.
  * [2] C. E. Shannon, “A mathematical theory of communication,” _The Bell System Technical Journal_ , 1948.
  * [3] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” _IEEE Transactions on Information Theory_ , vol. 55, no. 7, pp. 3051–3073, 2009.
  * [4] E. Drinea and M. Mitzenmacher, “Improved lower bounds for the capacity of i.i.d. deletion and duplication channels,” _IEEE Transactions on Information Theory_ , 2007.
  * [5] M. Mitzenmacher and E. Drinea, “A simple lower bound for the capacity of the deletion channel,” _IEEE Transactions on Information Theory_ , 2006.
  * [6] M. Cheraghchi, “Capacity upper bounds for deletion-type channels,” _J. ACM_ , 2019.
  * [7] M. Cheraghchi and J. L. Ribeiro, “An overview of capacity results for synchronization channels,” _IEEE Transactions on Information Theory_ , 2019\.
  * [8] M. Mitzenmacher, “New results and open problems for channels with synchronization,” 2008, Algorithm Theory – SWAT 2008. [Online]. Available: https://www.eecs.harvard.edu/~michaelm/Talks.html
  * [9] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” _IEEE Transactions on Information Theory_ , vol. 56, no. 5, pp. 2307–2359, 2010.
  * [10] R. L. Dobrushin, “Shannon’s theorems for channels with synchronization errors,” _Problemy Peredachi Informatsii_ , 1967.

##  VI Appendix

###### Proof of Lemma II.9.

We verify the axioms:

  1. 1.

_Inclusion of 1._ We trivially have
$1\in\mathcal{G}_{\operatorname{\mathsf{Ch}}}.$

  2. 2.

_Closedness under inverses._ Suppose
$g\in\mathcal{G}_{\operatorname{\mathsf{Ch}}}$. Clearly
$g^{-1}\in\mathsf{Aut}(\mathcal{X}^{*})$ and $g^{-1}$ preserves string length.
Moreover by assumption there exists $h\in\mathsf{Aut}(\mathcal{Y}^{*})$ such
that
$h\operatorname{\mathsf{Ch}}gx\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\operatorname{\mathsf{Ch}}x$
for all $x\in\mathcal{X}^{*}.$ Multiplying by $h^{-1}$ on the left and letting
$x^{\prime}=gx,$ we have
$\operatorname{\mathsf{Ch}}x^{\prime}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}h^{-1}\operatorname{\mathsf{Ch}}g^{-1}x^{\prime}$.
But $\\{gx:x\in\mathcal{X}^{*}\\}=\mathcal{X}^{*}$ since
$g\in\mathsf{Aut}(\mathcal{X}^{*}),$ so
$g^{-1}\in\mathcal{G}_{\operatorname{\mathsf{Ch}}}.$

  3. 3.

_Closedness under multiplication._ Let
$g_{1},g_{2}\in\mathcal{G}_{\operatorname{\mathsf{Ch}}}.$ Clearly we have
$g_{1}g_{2}\in\mathsf{Aut}(\mathcal{X}^{*}),$ and $g_{1}g_{2}$ preserves
string length. Moreover, letting $h_{1},h_{2}$ be such that
$h_{i}\operatorname{\mathsf{Ch}}g_{i}x\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\operatorname{\mathsf{Ch}}x$
for all $x\in\mathcal{X}^{*},i=1,2,$ we have

$\displaystyle h_{2}h_{1}\operatorname{\mathsf{Ch}}g_{1}g_{2}x$
$\displaystyle=h_{2}(h_{1}\operatorname{\mathsf{Ch}}g_{1})(g_{2}x)$
$\displaystyle\stackrel{{\scriptstyle\mathcal{D}}}{{=}}h_{2}\operatorname{\mathsf{Ch}}g_{2}x$
$\displaystyle\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\operatorname{\mathsf{Ch}}x,$

so $g_{1}g_{2}\in G_{\mathcal{D}}(\operatorname{\mathsf{Ch}})$.

∎

###### Proof of Theorem III.1.

Fix a channel $\operatorname{\mathsf{Ch}}$ over an alphabet $\mathcal{X}$ and
a group element $g\in\mathcal{G}_{\operatorname{\mathsf{Ch}}}.$ Suppose
$\mathcal{D}$ is the mutual-information-maximizing distribution of the
statement of the theorem, $X\sim\mathcal{D}$ and
$Y=\operatorname{\mathsf{Ch}}X.$ Then let $X^{\prime}=gX$ and
$Y^{\prime}=\operatorname{\mathsf{Ch}}X^{\prime}.$ We will prove two claims:
(1) that $I(X;Y)=I(X^{\prime};Y^{\prime}),$ and (2) that, under the
assumptions of the theorem, the mutual information $I(X;Y)$ is maximized by a
unique distribution of $X.$ The combination of these two claims yields
$X^{\prime}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}X,$ proving the theorem.

For the first claim, we show the stronger statement that, for $h$ as in
Definition II.6, we have
$(g^{-1}X^{\prime},hY^{\prime})\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(X,Y)$;
since $\mathcal{X}\times\mathcal{Y}\ni(x,y)\mapsto(g^{-1}x,hy)$ is a
bijection, this then immediately gives (1). Indeed, we have

$\displaystyle\mathbb{P}((g^{-1}X^{\prime},$ $\displaystyle
hY^{\prime})=(x,y))$
$\displaystyle=\mathbb{P}(g^{-1}gX=x,h\operatorname{\mathsf{Ch}}gX=y)$
$\displaystyle=\mathbb{P}(X=x,h\operatorname{\mathsf{Ch}}gX=y)$
$\displaystyle=\mathbb{P}(X=x)\mathbb{P}(h\operatorname{\mathsf{Ch}}gX=y|X=x)$
$\displaystyle=\mathbb{P}(X=x)\mathbb{P}(h\operatorname{\mathsf{Ch}}gx=y)$
$\displaystyle=\mathbb{P}(X=x)\mathbb{P}(\operatorname{\mathsf{Ch}}x=y)$
$\displaystyle=\mathbb{P}(X=x)\mathbb{P}(\operatorname{\mathsf{Ch}}X=y|X=x)$
$\displaystyle=\mathbb{P}(X=x,\operatorname{\mathsf{Ch}}X=y)$
$\displaystyle=\mathbb{P}((X,Y)=(x,y)),$

as desired.

For the second claim, if $X\sim\mathcal{D}_{X}$, it suffices to show that the
function $\mathcal{D}_{X}\mapsto I(X;Y)$ is strictly concave.444Note that the
full rank assumption on the transition matrix is necessary here: while entropy
is always a strictly concave function of the distribution, mutual information
is only a concave (and not necessarily strictly concave) function of the input
distribution. But writing

$I(X;Y)=H(Y)-H(Y|X),$

the second term is a linear function of $\mathcal{D}_{X}$ (it can be written
$H(Y|X)=\mathbb{E}_{x\sim\mathcal{D}_{X}}H(Y|X=x)$), and the first is a
strictly concave function (the entropy) of the distribution of $Y$ (call it
$\mathcal{D}_{Y}$). Now we may obtain $\mathcal{D}_{Y}$ as a linear function
of the distribution of $X$, i.e. $\mathcal{D}_{Y}=M_{n}\mathcal{D}_{X}$ (where
$M_{n}$ is the $n$th transition matrix of $\operatorname{\mathsf{Ch}}$), and
since $M_{n}$ is full-rank, $\mathcal{D}_{X}\mapsto\mathcal{D}_{Y}$ is an
injective linear function, hence $\mathcal{D}_{X}\mapsto H(Y)$ is strictly
concave. This proves (2) and hence the theorem. ∎