# Domain Wall AdS/QCD

Nick Evans  STAG Research Centre & Physics and Astronomy, University of
Southampton, Southampton, SO17 1BJ, UK  Jack Mitchell  STAG Research Centre &
Physics and Astronomy, University of Southampton, Southampton, SO17 1BJ, UK

###### Abstract

We construct a new holographic description of QCD using domain wall fermions.
The construction consists of probe D7 branes in a D5 brane geometry describing
quarks on a 4+1d defect in a 5+1d gauge theory. We then compactify one
dimension of the D5 to introduce confinement in the gauge degrees of freedom.
In addition we allow a spatial dependent mass term for the D7 brane quarks to
isolate chiral fermions on 3+1d domain walls. The D7 world volume fields, when
restricted to the domain wall position, provide an AdS/QCD description. We
compute the spectrum and compare to data. We include higher dimension
operators to systematically improve the description.

Domain wall fermions Kaplan:1992bt  are a powerful technique for isolating
massless, chiral fermions within a gauge theory. The technique is widely used
in lattice QCD simulations to enforce chiral symmetry. Recently we
investigated the technique in a holographic setting CruzRojas:2021pql
providing a holographic description of 2+1 dimensional domain wall fermions on
a probe D7 brane in the AdS5 space generated by ${\cal N}=4$ super Yang-Mills
theory Maldacena:1997re . In the limit where the higher dimension mass is very
large the position of the domain wall (where the chiral fermions are massless)
can be found exactly. Restricting the holographic fields to the locus of the
domain wall gives a holographic description of the dynamics of those chiral
fermions.

Here we take this approach to provide a description of a 3+1 dimensional
domain wall theory with $N_{f}$ chiral quarks on the defect - the basic
construct is a 5+1 dimensional gauge theory (on a D5 brane) compactified in
one dimension (introducing confinement), with quarks present on 4+1
dimensional defects (probe D7 branes). The domain wall structure is then used
to place chiral fermion on 3+1 dimensional defects. When the 4+1d mass is
large the position of the domain wall can be found and the holographic fields,
when reduced to this locus, provide a description of the chiral fermions. We
present the construction of this Domain Wall AdS/QCD theory and compute the
light meson spectrum it predicts. The UV of the theory, reflecting that the
gauge dynamics is 5+1 dimensional, does not match to perturbative QCD so we
impose a cut off at the 3 GeV scale and only work at lower scales in the
holographic model. The predictions are comparable in quality to those of other
AdS/QCD constructions Erlich:2005qh ; Sakai:2004cn .

The holographic description should be matched at the 3 GeV upper cut off to
QCD in the intermediate coupling regime and higher dimension operators would
be expected to be present Evans:2006ea . We include such operators using
Witten’s multi-trace prescription Witten:2001ua  (see Evans:2016yas ;
Clemens:2017udk  for previous examples of using HDOs in holographic
descriptions of QCD). We fit the couplings of these operators to the meson
data since we can not compute the non-perturbative QCD matching. We show that
the predictions of the model can be systematically improved in this way.

##  I I The Brane Construction

Our construction is built around the D5/probe D7 system with five coincident
directions in the configuration (one of the systems discussed in Myers:2006qr
).

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---|---
D5 | - | - | - | - | - | (-) | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$
D7 | - | - | - | - | - | $\bullet$ | - | - | - | $\bullet$

(1)

The UV theory is therefore a supersymmetric 5+1d gauge theory with quark
hypermultiplets restricted to a 4+1d domain wall. The gauge theory is strongly
coupled in the UV but we will set up our QCD-like dynamics in the IR where the
supergravity approximation holds. We will compactify one of the five spatial
directions on the D5 brane, shown by the brackets in (1). This breaks
supersymmetry and introduces an IR confinement scale by making the geometry a
cigar in the $x_{5}$ and radial direction.

Note if the D7 brane were at $x_{9}=0$ describing a massless quark, then the
D7 would wrap around the cigar and re-emerge as an anti-D7 brane anti-podal on
the circle in $x_{5}$. This demonstrates that the theory needs an anti-D5 in
order for the D7 fluxes to have a sensible solution on the $x_{5}$ circle.
Here though we will, except on a domain wall, set the quark mass very large so
that the D7 only live at large radius where they are widely separated on the
$x_{5}$ circle. We will assume that there is then no interaction between the
anti-podal branes and concentrate on the dynamics on one brane.

The final trick we will employ is to allow the quark mass, $M$, on the 4+1d
defect to be $x_{4}$ dependent. We will assume it is positive and very large
everywhere except in an interval of width $w$ where the sign flips. The
boundaries of this region have $M=0$ and are the domain walls. One expects the
localization of 3+1d chiral fermions, one on each domain wall. As in the
previous examples we studied in CruzRojas:2021pql , the domain walls approach
and merge as one moves into the IR of the holographic description indicating
the presence of chiral symmetry breaking. The $v_{9}$ field, which describes
the condensate of the left and right handed fermions, can have solutions
isolated on the domain wall. We show that the solutions display, consistently,
chiral symmetry breaking solutions on the U-shaped embeddings of the domain
wall configurations.

###  I.1 D5 Geometry

The geometry generated by the D5 branes with a compact direction is known. One
takes the thermal geometry for example found in Itzhaki:1998dd  and Wick
rotates to interchange a spatial and the time direction as described in
Horowitz:1998ha . This leads to the near-horizon metric
($U=r/\alpha^{\prime}$, $K=\frac{(2\pi)^{3/2}}{g_{YM}\sqrt{N}}$)

${ds^{2}\over\alpha^{\prime}}=KU(-dt^{2}+dx_{4}^{2}+hdz^{2})~{}~{}+\frac{1}{KU}\Big{(}{1\over
h}dU^{2}+U^{2}d\Omega_{3}^{2}\Big{)}$ (2)

where

$h(U)=1-{U_{0}^{2}\over U^{2}}$ (3) $e^{\phi}={U\over
K},~{}~{}~{}~{}~{}~{}g_{YM}^{2}=(2\pi)^{3}g_{s}\alpha^{\prime}$ (4)

Note that in the 5+1d dual the gauge field is of energy dimension one so
$1/g^{2}_{YM}$ has energy dimension two. Here we see that $U$ has dimension
one and the dilaton is dimensionless.

To find the circumference of the circle in $z$ we expand near the “horizon”,
$U=U_{0}+\delta U$, and find to leading order in the $U-z$ plane

$ds^{2}=2K\delta Udz^{2}+{1\over 2K\delta U}d\delta U^{2}$

We then set $\alpha=Kz$ and $\delta U={1\over 2}K\sigma^{2}$ and obtain

$ds^{2}=\left(d\sigma^{2}+\sigma^{2}d\alpha^{2}\right)$

which is a plane. To have no deficit angle $0<\alpha<2\pi$ so $0<z<2\pi/K$.

Before we can embed the D7 brane we need to write the metric so that the
directions transverse to the D5 are a flat plane (as in the cases explored in
Babington:2003vm ). The relevant pieces of the metric are

$ds^{2}=\frac{U}{K}\Big{(}{1\over U^{2}h(U)}dU^{2}+d\Omega_{3}^{2}\Big{)}$ (5)

We change coordinates so

${dv^{2}\over v^{2}}={dU^{2}\over U^{2}h(u)}$ (6)

so that

$ds^{2}=\frac{1}{K}{U(v)\over v^{2}}\Big{(}dv^{2}+v^{2}d\Omega_{3}^{2}\Big{)}$
(7)

which we can then write as

$ds^{2}={1\over K}{U(v)\over
v^{2}}\Big{(}d\rho^{2}+\rho^{2}d\Omega_{2}^{2}+dv_{9}^{2}\Big{)}$ (8)

Solving (6) gives

$v^{2}={1+{u\over\sqrt{u^{2}-u_{0}^{2}}}\over{u\over\sqrt{u^{2}-u_{0}^{2}}}-1}~{}~{}~{}~{}{\rm
or}~{}~{}~{}~{}{U\over U_{0}}={1+v^{2}\over 2v}$ (9)

Note that $v\rightarrow 1$ as $U/U_{0}\rightarrow 1$ and at large $U$ we find
$v^{2}=4U^{2}/U_{0}^{2}$.

Finally, the metric can be written

$ds^{2}=G_{x}(dx_{0-3}^{2}+hdx_{5}^{2})+{G_{v}}(d\rho^{2}+\rho^{2}d\Omega_{2}^{2}+dv_{9}^{2})$
(10)

with

$G_{x}=KU_{0}{v^{2}+1\over 2v},\hskip 28.45274pth(v)=1-\left({2v\over
v^{2}+1}\right)^{2}$ (11) $G_{v}={U_{0}\over K}{1+v^{2}\over 2v^{3}}\hskip
28.45274pte^{-\phi}={K\over U_{0}}{2v\over 1+v^{2}}$ (12)

It is worth noting here that the holographic directions in this set of
coordinates do not carry the field theory energy dimensions. $G_{x}$ does and
this is a useful check of equations below.

###  I.2 D7 Probe Action

Next we include 4+1d quark hypermultiplets on defects in the 5+1d glue theory
by the inclusion of a probe D7 brane Karch:2002sh  in the configuration of
(1). The DBI action takes the form

$S_{D7}=-T_{7}\int d^{8}\xi\sqrt{{\rm
det}(P[G_{ab}]+2\pi\alpha^{\prime}F_{ab})}$ (13)

where $\xi$ are the world volume coordinates and $P$ denotes the pullback. We
find, setting the worldvolume vector to zero for now,

$\begin{array}[]{r}S_{D7}=-{\cal N}\int
d^{5}x~{}d\rho~{}\rho^{2}e^{-\phi}G_{x}^{5/2}G_{v}^{3/2}\\\ \\\
\times\sqrt{1+(\partial_{\rho}v_{9})^{2}+{G_{v}\over
G_{x}}(\partial_{x_{0-4}}v_{9})^{2}}\end{array}$ (14)

where ${\cal N}=T_{7}\ \int d\Omega_{2}$. The factor

$e^{-\phi}G_{x}^{5/2}G_{v}^{3/2}={K^{2}U_{0}^{3}\over 8}\big{(}1+{1\over
v^{2}}\big{)}^{3}$ (15)

and blows up as $v\rightarrow 0$ which encourages the D7 to bend away from
$v=0$ by switching on $v_{9}$ and generating chiral symmetry breaking. The
equation for the D7 embedding that encodes this is

$\begin{array}[]{l}\partial_{\rho}\left[{\rho^{2}e^{-\phi}G_{x}^{5/2}G_{v}^{3/2}\over\sqrt{1+(\partial_{\rho}v_{9})^{2}}}\partial_{\rho}v_{9}\right]\\\
\\\ -2\rho^{2}\sqrt{1+(\partial_{\rho}v_{9})^{2}}\left({d\over
dv^{2}}e^{-\phi}G_{x}^{5/2}G_{v}^{3/2}\right)v_{9}=0\end{array}$ (16)

The UV solution is $v_{9}\simeq M+C/\rho~{}(\simeq U/2U_{0})$ and so the mass
is proportional to $MU_{0}$ and the condensate (of dimension four in 4+1d) to
$CK^{2}U_{0}^{2}$ (note that the condensate is a derivative with respect to
the mass on the action so naturally picks up the $K^{2}$ factor from (15)). We
will avoid this chiral symmetry breaking (and any interaction with any anti-
podal anti-D7) by taking configurations where $M\rightarrow\infty$ except on
domain walls.

###  I.3 Domain Walls

Our final ingredient is to introduce a quark mass that has spatial dependence
in the $x_{4}$ direction. We take the UV mass to be $M$ except, on the
boundary,

$v_{9}=-M\hskip 28.45274pt-w/2<x_{4}<w/2$ (17)

We expect 3+1d chiral fermions to be isolated at the two discontinuities where
$M=0$. We will now work in the infinite $M$ limit CruzRojas:2021pql  so that
any issues with the 4+1d quarks are pushed to the far UV and so that the
$x_{4}$ derivative of $v_{9}$ becomes a delta function. One must be careful to
include appropriate Jacobian factors in the form of the delta function (these
are those that effectively reduce the D7 action to that of a 6 brane). We
have, with $M$ vanishing on the contour $x_{4}(\rho)$

$\partial_{\rho}v_{9}=\left.{1\over G_{v}^{1/2}(\partial_{4}\rho)}\right|_{\rm
locus}\delta(x_{4}-x_{4}(\rho))$ (18)

We now insert this factor into the D7 action (14) assuming that $v_{9}=0$
(formally $v_{9}\ll M$) giving

$S_{\rm locus}=-{\cal N}\int
d^{4}x~{}d\rho~{}\rho^{2}e^{-\phi}G_{x}^{2}{G_{v}^{3/2}}\sqrt{1+{G_{x}\over
G_{v}}(\partial_{\rho}x_{4})^{2}}$ (19)

which is an action that determines the locus on which $M=0$ in the $\rho-
x_{4}$ plane. (19) has a conserved quantity which we denote ${\cal C}$ and we
find

$\partial_{\rho}x_{4}={G_{v}^{1/2}\over
G_{x}^{1/2}\sqrt{e^{-2\phi}\rho^{4}G_{x}^{5}G_{v}^{2}{\cal C}^{2}-1}}$ (20)

Figure 1: The loci of the domain walls in the $\rho-x_{4}$ plane for different
choices of ${\cal C}/\rho_{\rm min}$. Here we set $KU_{0}=1$ for numerics.

Note the large $\rho$ limit of this is $4\sqrt{2}/({\cal
C}K^{7/2}U_{0}^{5/2}\rho^{7/2})$ and ${\cal C}$ has energy dimension -5.

The solutions are U-shaped in the $\rho-x_{4}$ plane with the minimum $\rho$
value given when the denominator vanishes. We display these solutions in
Figure 1.

##  II II The Domain Wall Theory

We now wish to describe holographically the 3+1d chiral fermions living on the
domain walls and their interactions - this is the Domain Wall AdS/QCD theory.
One wants solutions of the D7 brane world volume fields that are of the form
of a delta function on the loci found above and shown in Figure 1. To find
such solutions we, by hand, dimensionally reduce the D7 brane action in (14)
onto the loci by imposing a delta function of the form in (18).

###  II.1 The Quark Mass and Condensate

As a first example let’s find the vacuum configuration describing the quark
condensate by considering just the field $v_{9}$. We obtain the action

$\begin{array}[]{r}S_{D7}=-{\cal N}\int
d^{4}x~{}d\rho~{}\rho^{2}e^{-\phi}G_{x}^{5/2}{G_{v}^{3/2}\over
G_{v}^{1/2}(\rho)}(\partial_{\rho}x_{4})\\\ \\\ \times\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}+{G_{v}\over
G_{x}}(\partial_{x_{0-3}}v_{9})^{2}}\end{array}$ (21)

where

${\cal F}=1+{G_{v}\over G_{x}(\partial_{\rho}x_{4})^{2}}$ (22)

It’s worth noting that in the large $\rho$ limit for the pieces

Figure 2: Numerical solutions for the vacuum functions $v_{9}(\rho)$.

relevant for the vacuum configuration becomes

$S_{D7}\sim-\int d^{4}x~{}d\rho~{}{1\over{\cal C}K\rho}\sqrt{1+{{\cal
C}^{2}K^{5}U_{0}^{5}\over 32}\rho^{5}(\partial_{\rho}v_{9})^{2}}$ (23)

The large $\rho$ solution is $v_{9}=m+c/\rho^{3}$. Note here we use little $m$
and $c$ \- they are masses and condensates between the chiral fermions on the
domain wall which are distinct from the $M,C$ of the 4+1d theory. The
condensate is identified by taking a derivative with respect to the mass,
$mU_{0}$, on the action - as written in this limit the action is $m$
independent so one must imagine a sub-leading term, for example coming from
the expansion of the dilaton, $\int d\rho~{}v_{9}^{2}/{\cal C}K\rho$. Now one
sets $v_{9}=m+c/\rho^{3}$ and differentiates the cross term w.r.t $U_{0}m$:
thus we find the condensate is proportional to $c~{}/{\cal C}KU_{0}$ which is
both proportional to $c$ and of dimension 3.

The resulting full equation of motion for an $x$ independent $v_{9}$ vacuum
solution is

$\begin{array}[]{l}\partial_{\rho}\bigg{(}e^{-\phi}\rho^{2}{G_{x}^{5/2}G_{v}^{3/2}\over
G_{v}^{1/2}(\rho)}(\partial_{\rho}x_{4}){{\cal
F}\;\partial_{\rho}v_{9}\over\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}}\bigg{)}\\\ \\\
-{2\rho^{2}(\partial_{\rho}x_{4})\over
G_{v}^{1/2}(\rho)}v_{9}{\partial\over\partial
v^{2}}\Big{(}e^{-\phi}G_{x}^{5/2}G_{v}^{3/2}\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}\Big{)}=0\end{array}$ (24)

In the UV the solution is of the form $m+c/\rho^{2}$. We find solutions
numerically by shooting from the IR boundary conditions $v_{9}(\rho_{\rm
min})=\rho_{\rm min}$ (this is required for the IR mass gap to be consistent
with the gap described by the loci in Figure 1) and $v_{9}^{\prime}(\rho_{\rm
min})=0$. We display the results in Figure 2. The numerics become highly tuned
as $\rho_{\rm min}$ approaches one and the U-shaped loci become infinitely
wide but the results look very consistent with the UV quark mass being zero in
this limit (which is the case for the D7 embedding in a uncompactified D5
background). For small separations of the domain walls, large $\rho_{\rm
min}$, the quark mass scales as $1/\rho_{\rm min}$ as we found in similar
configurations in CruzRojas:2021pql . The massless embedding shows chiral
symmetry breaking behaviour generating the $\rho_{\rm min}=1$ mass gap.

Figure 3: A plot of $M_{\pi}^{2}$ against $m_{q}$ with a guiding linear
function plotted (red).

###  II.2 Pions

The quark condensate and mass are complex objects and we would expect a second
degree of freedom in the dual that forms a complex pair with $v_{9}$. Let us
call this $v_{10}$ although there is no such field in the DBI action. We can
immediately write down it’s equation following that for $v_{9}$ since it has a
U(1) symmetry that mixes it with that field. The equation of motion for
fluctuations of $v_{10}$ in the background of the $v_{9}$ vacuum solution is
simply

$\begin{array}[]{l}\partial_{\rho}\bigg{(}e^{-\phi}\rho^{2}{G_{x}^{5/2}G_{v}^{3/2}\over
G_{v}^{1/2}(\rho)}(\partial_{\rho}x_{4}){{\cal
F}\;\partial_{\rho}v_{10}\over\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}}\bigg{)}\\\ \\\
-{2\rho^{2}(\partial_{\rho}x_{4})\over
G_{v}^{1/2}(\rho)}v_{10}{\partial\over\partial
v^{2}}\Big{(}e^{-\phi}G_{x}^{5/2}G_{v}^{3/2}\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}\Big{)}\\\ \\\
+M^{2}e^{-\phi}\rho^{2}{G_{x}^{3/2}G_{v}^{5/2}\over
G_{v}^{1/2}(\rho)}(\partial_{\rho}x_{4}){v_{10}\over\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}}=0\end{array}$ (25)

This equation is therefore sufficient to compute the behaviour of the
Goldstone mode and its radially excited states of the theory. $v_{10}$ does
not appear explicitly in the model but this is because the $v_{9}+iv_{10}$
complex number can be written as $v_{9}e^{i\phi}$ and then a U(1)A
transformation used to set $\phi=0$. The degrees of freedom though remain and
the solutions will emerge as components of the gauge fields which are present
on the U-shaped locus. It is easiest to compute using the logic here though.

The Goldstone nature of this $v_{10}$ state follows simply from (25). If one
sets $M^{2}=0$ and $v_{10}$ equal to the $v_{9}$ background solution then (25)
is simply (24). This solution though can only be used as a physical state for
the massless theory since we require that asymptotically it falls to zero so
it describes a fluctuation of the operator (rather than asymptoting to a
source). Away from the massless quark theory we must solve (25) numerically
with $v^{\prime}_{10}(\rho_{\rm min})=0$ and vary $M^{2}$ to achieve
$v_{10}(\infty)=0$. We show our numerical data in Figure 3. The results
sensibly match a Gell-Mann-Oakes-Renner relation ($M_{\pi}^{2}\sim
m_{q}$)GellMann:1968rz  at small quark mass but at larger quark mass
$M^{2}\sim m_{q}^{2}$ as one would expect.

###  II.3 Vector and Axial vector mesons

The Lagrangian for a small $F^{\mu\nu}$ fluctuation is given by

${\cal L}={{\cal N}\over 2}\rho^{2}{e^{-\phi}G_{x}^{5/2}G_{v}^{3/2}\over
G_{v}^{1/2}(\rho)}{(\partial_{\rho}x_{4})\over\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}}g^{\mu\alpha}g^{\nu\beta}F_{\mu\nu}F_{\alpha\beta}$
(26)

Note here the $x_{4}$ derivative should be included in the sense that on the
vacuum locus it contributes to the $\rho$ derivative as
$\partial_{x^{4}}=\partial_{\rho}/\partial_{\rho}x^{4}$. The resulting
equation for the spatial mesons is given by

$\begin{array}[]{r}\partial_{\rho}\left[\rho^{2}e^{-\phi}G_{x}^{3/2}{G_{v}^{1/2}\over
G_{v}^{1/2}(\rho)}{(\partial_{\rho}x_{4}){\cal F}\over\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}}\partial_{\rho}A_{x}\right]\\\ \\\
+M^{2}\rho^{2}e^{-\phi}G_{x}^{1/2}{G_{v}^{3/2}\over
G_{v}^{1/2}(\rho)}{(\partial_{\rho}x_{4})\over\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}}A_{x}=0\end{array}$ (27)

Vector mesons have IR boundary conditions $\partial_{\rho}A(\rho_{\rm min})=0$
and $A(\infty)=0$ (note the linearized equation doesn’t depend on $A(\rho_{\rm
min})$ so one varies $M^{2}$ to satisfy the UV boundary condition). Axial-
vector mesons have $A(\rho_{\rm min})=0$ and $A(\infty)=0$ (again the
linearity means the derivative is only defined up to a constant - so one picks
some fixed IR derivative and varies $M^{2}$ to find a solution that matches
the UV boundary conditions).

The solutions for the vector meson must be normalized - one requires that it’s
kinetic term is canonical so

${\cal N}\int d\rho~{}\rho^{2}{e^{-\phi}G_{x}^{1/2}G_{v}^{3/2}\over
G_{v}^{1/2}(\rho)}{(\partial_{\rho}x_{4})\over\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}}(A_{x})^{2}=1$ (28)

To normalize the source solutions we must investigate the UV behaviour of
(27). At large $\rho$ we have

$\partial_{\rho}\left[{CK^{4}U_{0}^{3}\over
8}\rho^{4}\partial_{\rho}A_{x}\right]+M^{2}{4\over{\cal
C}K^{3}U_{0}^{2}}{1\over\rho^{3}}A_{x}=0$ (29)

The solutions of this are not of the Log $Q^{2}/\rho^{2}$ form found in
AdS/QCD Erlich:2005qh  since the UV of the theory is not a conformal 3+1d
theory (the higher dimensional glue theory’s coupling runs as a power law in
the UV). However, it is always a sleight of hand to match a gravity dual to
perturbative QCD since the dual must fail (or become strongly coupled itself)
as QCD becomes perturbative. A simple fix is to only allow the gravity
description to extend to a UV cut off. We will take $10U_{0}$ \- $U_{0}$ sets
the scale of the IR quark mass as shown in Figure 2 so is matched to of order
300 MeV - thus the UV cut off scale corresponds 3 GeV or so. One should match
to QCD at this UV cut off in the region where QCD is between weak and strong
coupling. Rather than attempting to match (which would require calculation in
QCD in an intermediate coupling regime) we will simple set the normalization
of the source solutions by fitting to $F_{V}$. We can then predict $F_{A}$ and
$f_{\pi}$.

$F_{V}^{2}$ is defined as the Feynman rule for a vector meson to turn directly
into it’s source at $q^{2}=0$. We must solve (27) with $M^{2}=0$ to find a
solution that asymptotes to a constant in the UV to represent the source.

Now we can compute the decay constant (removing the UV surface term between
the operator and source) as

$\begin{array}[]{c}F_{V}^{2}={\cal N}\int
d\rho~{}\partial_{\rho}\left[\rho^{2}{e^{-\phi}G_{x}^{3/2}G_{v}^{1/2}\over
G_{v}^{1/2}(\rho)}\right.\\\ \\\
\left.~{}~{}~{}~{}~{}~{}~{}~{}\times{(\partial_{\rho}x_{4}){\cal
F}\over\sqrt{1+{\cal
F}(\partial_{\rho}v_{9})^{2}}}\partial_{\rho}A_{V}\right]A_{\rm
source}\end{array}$ (30)

We cut the integration off at $10U_{0}$ and set the source normalization to
give the observed value of $F_{V}$. The $F_{A}$ coupling is then a repeat of
this computation with the axial vector meson solutions and using the same
normalization at the cut off.

$f_{\pi}^{2}$ is given by the axial axial correlator

$\begin{array}[]{l}f_{\pi}^{2}={\cal N}\int
d\rho~{}\rho^{2}{e^{-\phi}G_{x}^{3/2}G_{v}^{1/2}\over G_{v}^{1/2}(\rho)}\\\
\\\ \left.\right.\hskip 56.9055pt\times{(\partial_{\rho}x_{4}){\cal
F}\over\sqrt{1+{\cal F}(\partial_{\rho}v_{9})^{2}}}(\partial_{\rho}A_{\rm
source~{}A})^{2}\end{array}$ (31)

Now we can compute $m_{\pi}$, $M_{V}$, $M_{A}$, $F_{V}$, $F_{A}$ and
$f_{\pi}$. We use $M_{V}$ and $M_{\pi}$ to set the overall scale and quark
mass and $F_{V}$ sets the source normalization, leaving 3 predictions. We
display these results in Table 1. The model like many AdS/QCD models gives the
correct ball-park spectrum but here we find the axial sector predictions
($f_{\pi},M_{A},F_{A}$) all lie above the QCD values. Radially excited states’
masses also rise sharply suggesting $M\sim n$ rather than $M\sim\sqrt{n}$ as
is widely the case in AdS/QCD models Shifman:2005zn .

We can improve the predictions by adding higher dimension operators at the UV
cut off scale Evans:2006ea . These should represent the generation of such
operators in the intermediate regime between strong and weak coupling where
one should match to perturbative QCD. Using Witten’s multi-trace prescription,
we change the UV boundary conditions on the holographic fields to allow
solutions with non-zero source. We interpret the source as due to the presence
of generically an operator $G{\cal O}^{\dagger}{\cal O}$ which when ${\cal O}$
condenses generates an effective source $G\langle{\cal O}\rangle$.

| QCD | DW AdS/QCD | Improved
---|---|---|---
|  |  | DW AdS/QCD
$m_{\rho}$ | 775 MeV | $775^{*}$ | $g_{q}=0.247$
$m_{\pi}$ | 139 MeV | $139^{*}$ | $g_{v}=0.656$
$m_{a}$ | 1230 MeV | $1,955$ | $g_{A}=1.287$
$F_{V}$ | 345 MeV | $345^{*}$ |
$F_{A}$ | 433 MeV | $726.7$ |
$f_{\pi}$ | 93 MeV | $135.3$ | $128.8$
$M_{v,n=1}$ | 1465 MeV | 3284 | 1881.8
$M_{A,n=1}$ | 1655 MeV | 5043 | 2752.5

Table 1: Mesonic observables - QCD values and the basic Domain Wall AdS/QCD
model’s predictions. Starred quantities are used to fix parameters as
described in the text. In the final column we list the values of the higher
dimension operator couplings in the improved version of the model - here
$f_{\pi}$, and the excited state masses are predicted.

See Clemens:2017udk  for recent examples of this methodology in alternative
AdS/QCD set ups.

In particular we proceed as follows. We start by considering different
background embeddings for $v_{9}$ that asymptote in the UV to different source
values. For each we compute the pion mass. We then fix by hand the ratio of
the vector meson mass to the pion mass to its observed value and find the wave
function, which does not asymptote to zero in the UV - we can extract the HDO
coupling from the source and operator values at the cut off, assuming the
presence of an operator $g_{V}^{2}/\Lambda^{2}|\bar{q}\gamma^{\mu}q|^{2}$ (we
will quote $g_{V}^{2}=\Lambda^{2}{\cal J}/{\cal O}$). Next we fit the
normalization of the source to fit $F_{V}$. In the axial sector we allow a
coupling $g_{A}^{2}/\Lambda^{2}|\bar{q}\gamma^{\mu}\gamma^{5}q|^{2}$ to fit
the axial vector meson mass. Now $F_{A}$ and $f_{\pi}$ can be computed.
Repeating this for all the $v_{9}$ embeddings we can achieve the physical
value of $f_{A}$, fixing the background embedding. The pion decay constant
reduces a little as shown in Table 1 but not as low as the physical value.
There is a bigger improvement in the predictions of the radial excited state
masses as we show for the first excitations of the $\rho$ and $a$ mesons,
although they too still remain high.

##  III III Discussion

We have presented a holographic domain wall theory of 3+1 dimensional chiral
quarks interacting via confining gauge interactions. Here the gauge
interactions are five dimensional albeit with one compact dimension to
generate the confinement scale. The quarks of a 4+1 dimensional theory are
isolated on separated domain walls where the 4+1 dimensional theory’s mass
vanishes. The holographic fields on the locus of the defects provide a
holographic description of a QCD-like theory. We have shown the theory has
chiral symmetry breaking and generates a spectrum that quite closely resembles
QCD. Deviations are likely due to the gauge coupling growing into the UV - we
have included a UV cut off to stop this growth and included some higher
dimension operators at the cut off. The spectrum is then improved but the full
effects of the higher dimension gauge dynamics are not suppressed.

In lattice simulations using the domain wall fermion method the gauge fields
are isolated on the defects and independent of the higher dimensions. It would
be interesting to try to arrange such a set up holographically using multi-
centre brane solutions, although non-supersymmetric multi-centre solutions are
hard to find.

We have presented the model on the surface of a single D7 brane generating
just a single flavour of quarks. However, one would expect the domain wall
trick to generate non-abelian SU($N_{f})_{L}\times$ SU($N_{f})_{R}$ flavour
symmetries - on a domain wall only a single chiral quark is massless whilst
the other is massive, so the interaction with the adjoint scalar superpartner
of the gauge field is suppressed on the wall. Thus the theory on the surface
of $N_{f}$ D7 branes is just that of the abelian case but fields are promoted
to $N_{f}\times N_{f}$ matrices and the full action should be traced in
flavour space. The bosonic fields will form U($N_{f}$) multiplets of the
vector flavour symmetry with the masses and couplings of the abelian case we
have described.

In conclusion we believe it has been interesting to generate a new type of
AdS/QCD model which uses the domain wall fermion method. The method may allow
a wider class of chiral theories to be explored in the future.

Acknowledgements: NEs work was supported by the STFC consolidated grants
ST/P000711/1 and ST/T000775/1. JMs work was supported by an STFC studentship.

## References

  * (1) D. B. Kaplan, Phys. Lett. B 288 (1992), 342-347 doi:10.1016/0370-2693(92)91112-M [arXiv:hep-lat/9206013 [hep-lat]].
  * (2) J. Cruz Rojas, N. Evans and J. Mitchell, [arXiv:2106.08753 [hep-th]].
  * (3) J. M. Maldacena, Adv. Theor. Math. Phys. 2 (1998) 231 [hep-th/9711200]; E. Witten, Adv. Theor. Math. Phys. 2 (1998) 253 [hep-th/9802150]; S. S. Gubser, I. R. Klebanov and A. M. Polyakov, Phys. Lett. B 428 (1998) 105 [hep-th/9802109].
  * (4) J. Erlich, E. Katz, D. T. Son and M. A. Stephanov, Phys. Rev. Lett. 95 (2005), 261602 doi:10.1103/PhysRevLett.95.261602 [arXiv:hep-ph/0501128 [hep-ph]]; L. Da Rold and A. Pomarol, Nucl. Phys. B 721 (2005), 79-97 doi:10.1016/j.nuclphysb.2005.05.009 [arXiv:hep-ph/0501218 [hep-ph]].
  * (5) T. Sakai and S. Sugimoto, Prog. Theor. Phys. 113 (2005), 843-882 doi:10.1143/PTP.113.843 [arXiv:hep-th/0412141 [hep-th]].
  * (6) N. Evans and A. Tedder, Phys. Lett. B 642 (2006), 546-550 doi:10.1016/j.physletb.2006.10.019 [arXiv:hep-ph/0609112 [hep-ph]].; N. Evans, J. P. Shock and T. Waterson, Phys. Lett. B 622 (2005), 165-171 doi:10.1016/j.physletb.2005.07.014 [arXiv:hep-th/0505250 [hep-th]].
  * (7) E. Witten, [arXiv:hep-th/0112258 [hep-th]].
  * (8) N. Evans and K. Y. Kim, Phys. Rev. D 93 (2016) no.6, 066002 doi:10.1103/PhysRevD.93.066002 [arXiv:1601.02824 [hep-th]].
  * (9) W. Clemens and N. Evans, Phys. Lett. B 771 (2017), 1-4 doi:10.1016/j.physletb.2017.05.027 [arXiv:1702.08693 [hep-th]]; J. Erdmenger, N. Evans, W. Porod and K. S. Rigatos, JHEP 02 (2021), 058 doi:10.1007/JHEP02(2021)058 [arXiv:2010.10279 [hep-ph]]; M. Jarvinen, JHEP 07 (2015), 033 doi:10.1007/JHEP07(2015)033 [arXiv:1501.07272 [hep-ph]].
  * (10) R. C. Myers and R. M. Thomson, JHEP 09 (2006), 066 doi:10.1088/1126-6708/2006/09/066 [arXiv:hep-th/0605017 [hep-th]].
  * (11) N. Itzhaki, J. M. Maldacena, J. Sonnenschein and S. Yankielowicz, Phys. Rev. D 58 (1998), 046004 doi:10.1103/PhysRevD.58.046004 [arXiv:hep-th/9802042 [hep-th]].
  * (12) G. T. Horowitz and R. C. Myers, Phys. Rev. D 59 (1998), 026005 doi:10.1103/PhysRevD.59.026005 [arXiv:hep-th/9808079 [hep-th]].
  * (13) J. Babington, J. Erdmenger, N. J. Evans, Z. Guralnik and I. Kirsch, Phys. Rev. D 69 (2004), 066007 doi:10.1103/PhysRevD.69.066007 [arXiv:hep-th/0306018 [hep-th]].
  * (14) A. Karch and E. Katz, JHEP 0206 (2002) 043 [arXiv:hep-th/0205236]; M. Grana and J. Polchinski, Phys. Rev. D 65 (2002) 126005 [arXiv:hep-th/0106014]; M. Bertolini, P. Di Vecchia, M. Frau, A. Lerda and R. Marotta, Nucl. Phys. B 621 (2002) 157 [arXiv:hep-th/0107057];M. Kruczenski, D. Mateos, R. C. Myers and D. J. Winters, JHEP 07, 049 (2003) doi:10.1088/1126-6708/2003/07/049 [arXiv:hep-th/0304032 [hep-th]]; J. Erdmenger, N. Evans, I. Kirsch, and E. Threlfall, Eur. Phys. J. A35 (2008) 81–133, [arXiv:0711.4467].
  * (15) M. Gell-Mann, R. J. Oakes and B. Renner, Phys. Rev. 175 (1968), 2195-2199 doi:10.1103/PhysRev.175.2195
  * (16) M. Shifman, doi:10.1142/9789812774132_0025 [arXiv:hep-ph/0507246 [hep-ph]]; A. Karch, E. Katz, D. T. Son and M. A. Stephanov, Phys. Rev. D 74 (2006), 015005 doi:10.1103/PhysRevD.74.015005 [arXiv:hep-ph/0602229 [hep-ph]].


factor of interest. P values were adjusted with Tukey method to account for
multiple comparisons. The results of the cumulative link models were
consistent with the results obtained from the linear models in 6.2.

Similar to the results we observed for the linear model counterparts, the
effects of veracity in the veracity model and perceived accuracy in the
perceived accuracy model were both significant [$\chi^{2}(1)=29.80$, $p<0.001$
for veracity model, $\chi^{2}(1)=1851.56$, $p<0.001$ for perceived accuracy
model]. The EMMeans showed that participants were more likely to have the
intention of sharing objectively true rather than false headlines [$z=5.03$,
$p<0.001$, $E(False)=1.23$, $E(True)=1.48$]. Similarly, they were more likely
to share headlines that they perceived as true [$z=13.49$, $p<0.001$,
$E(\textit{Perceived as false})=1.05$, $E(\textit{Perceived as true}=1.58$].

Similarly, providing accuracy assessments had a significant effect on
participants’ likelihood of sharing either false or true headlines
[$\chi^{2}(1)=33.83$, $p<0.001$]. The EMMeans test revealed that participants
were more likely to share headlines if they were not asked about their
accuracy [$z=4.89$, $p<0.001$, $E(\textit{Accuracy not provided})=1.44$,
$E(\textit{Accuracy provided})=1.28$].

In addition, the effects of providing reasoning and the format of reasoning
were significant in both the veracity and the perceived accuracy models
[providing reasoning: $\chi^{2}(1)=13.05$, $p<0.001$ for veracity,
$\chi^{2}(1)=13.38$, $p<0.001$ for perceived accuracy; reasoning format:
$\chi^{2}(1)=6.21$, $p=0.01$ for veracity, $\chi^{2}(1)=5.14$, $p=0.02$ for
perceived accuracy]. Participants were more likely to share headlines if they
were not asked to provide their reasoning about why the claim was or was not
accurate [$z=3.52$, $p<0.001$, $E(\textit{Reasoning not provided})=1.41$,
$E(\textit{Reasoning provided})=1.30$ for veracity; $z=3.38$, $p<0.001$,
$E(\textit{Reasoning not provided})=1.36$, $E(\textit{Reasoning
provided})=1.26$ for perceived accuracy]. Providing reasons via the checkbox
set of reason categories also lowered their likelihood of sharing content
[$z=2.60$, $p=0.01$, $E(\textit{Free-text})=1.40$, $E(\textit{Checkbox})=1.32$
for veracity; $z=2.58$, $p=0.01$, $E(\textit{Free-text})=1.35$,
$E(\textit{Checkbox})=1.27$ for perceived accuracy].

The veracity model also indicated that the interaction between veracity and
providing accuracy is statistically significant [$\chi^{2}(1)=10.98$,
$p<0.001$]. The interaction however, was not practically meaningful
[$E(\textit{False, Accuracy not provided})=1.32$, $E(\textit{False, Accuracy
provided})=1.15$, $E(\textit{True, Accuracy not provided})=1.57$,
$E(\textit{True, accuracy provided})=1.40$].

##  Appendix D Investigation of Potential Confounds in the Nudge Study

###  D.1. Makeup of Data and Impact of Removing Spams.

The task in the Nudge study presented 10 claims to each participant but
because some participants abandoned the task before its conclusion, we had
fewer data from them. It is conceivable that if the attrition rate is
different across conditions, then the conditions differ not only in what
treatment they received, but also in what type of people contributed more data
to each condition. Therefore, we probed how many participants per condition
did not finish all the 10 headlines. This number across all conditions was in
the range of 30-50, suggesting that the dropout rate was similar. We then
analyzed the spam rate across conditions which was more variant (condition 1:
145 , condition 2: 114 , condition 3: 136, condition 4: 174). It is possible
that different interventions result in different spam rates and that those
participants who stay and work through a more laborious condition, are in
fact, characteristically different from those who finish the task by spamming.

We performed a Pearson’s Chi Square test to investigate if the distribution of
spams was different from a uniform distribution. The difference was
statistically significant [$\chi^{2}(3)=13.02$, $p=0.005$], suggesting that
the conditions may have had a role in different numbers of users becoming
spammers across conditions. We then analyzed the share rate in spams across
different conditions which was similar (see Table 6), with share mean of
approximately 0.72 across all conditions regardless of headline veracity.

In the main section of the paper, we have presented our findings above
excluding the Spams. However, we perform the same analyses including the spam
datapoints in the Appendix section E. Some of our results that pertain to
conditions that have heavier interventions are no longer statistically
significant when spams are included. The reason is that in these conditions,
the share rates are low and therefore the difference between conditions is
smaller but detectable in the absence of noise. Including noise, i.e., spams,
in a condition, increases the sample size while adding a relatively large
number of positive datapoints, or datapoints that indicate a positive
intention of sharing, for both true and false headlines. The difference that
existed before will now be diluted.

###  D.2. Deliberation Priming.

Although in the control condition for the Taxonomy study we did not have any
of the accuracy and reasoning nudges, after each sharing decision, we asked
participants why they would or would not share the article. This question by
itself may have acted as a deliberation prime on subsequent sharing decisions.
To test this hypothesis, we developed a model with share intention as the
dependent variable and veracity and whether the item was the first item
presented to the user as independent variables and included participant
identifier as a random effect. We fit the model to the first and last
datapoints that participants in the control condition provided. We found that
as expected, veracity was positively correlated with sharing intentions and
the correlation was statistically significant [$\beta=0.16,p<0.001$]. Being
the first decision by the participant also had a positive albeit
nonsignificant correlation with sharing [$\beta=0.49,p=0.23$]. The interaction
between the two had a negative and nonsignificant correlation
[$\beta=-0.08,p=0.20$]. Despite the lack of significance, we observe that the
effect of veracity on the last item presented to the user is twice as large as
that of the first item [$0.16$ for the last decision, $0.16-0.08=0.08$ for the
first]. This observation gives some degree of support to the hypothesis that
simply asking users to ponder over their sharing decision may have primed them
to be mindful of the headline’s accuracy over time.

###  D.3. Investigating Potential Learning Effects of Repeated Accuracy
Assessments

We wished to investigate whether making repeated judgements about accuracy had
a learning effect on participants leading their subsequent accuracy
assessments to be closer to the headline’s actual veracity. Therefore, we fit
the following model to the first and last datapoints that participants in the
treatment conditions had provided:

(5) $\text{accuracy assessment}==\text{veracity}\sim\text{is first
question}\times(\text{reasoning condition}+\text{reasoning format})\\\
+(1|\text{participant})+(1|\text{claim})$

Because the outcome of the model was dichotomous (1 if veracity and perceived
accuracy matched, 0 if they did not), we used the function “glmer” with link
“logit” from the R package “lme4” to fit the data. A Wald Chi-Square test on
the model revealed that the effect of whether the participant’s judgement was
the first or the last was in fact not significant [$\chi^{2}(1)=0.07$,
$p=0.80$], indicating that repeated judgements had not been a significant
confounder in the study.

##  Appendix E Spams

In this section, we include the spam datapoints of the Nudge study in the
dataset and perform the same analyses that we conducted in the Results
section.

The Wald-Chi Square tests fitted to our linear models revealed that the effect
of veracity in the veracity model and the effect of perceived accuracy in the
perceived accuracy model on sharing intention were both significant
[$\chi^{2}(1)=30.13$, $p<0.001$ for veracity, $\chi^{2}(1)=2645.61$, $p<0.001$
for perceived accuracy]. Post-hoc Estimated Marginal Means tests revealed that
participants were more likely to share an objectively true headline compared
to a false one [$z=4.60,p<0.001$]. Similarly, they were more likely to share a
headline that they perceived as true rather than one they perceived as false
[$z=42.04,p<0.001$]

###  E.1. Effect of Providing Accuracy Assessments

Consistent with the results we observed when excluding spams, providing
accuracy assessment had a significant effect on sharing intentions for the
veracity model [$\chi^{2}(1)=32.04$, $p<0.001$].

Figure 18 shows how sharing rates differ in conditions 1 and 2 by whether
participants were asked about accuracy and headline veracity. Asking people to
provide accuracy assessments decreases sharing of false headlines by 29% while
the reduction in sharing of true content is 17%.

###  E.2. Effect of Providing Reasoning

The effect of reasoning on sharing intention when including spams was not
significant in either the veracity or the perceived accuracy models
[$\chi^{2}(1)=0.40$, $p=0.53$ for the veracity model, $\chi^{2}(1)=0.50$,
$p=0.48$ for the perceived accuracy model]. Similarly, the interaction effect
of reasoning and veracity was not significant in the veracity model
[$\chi^{2}(1)=1.13$, $p=0.29$]. However, the effect of interaction between
reasoning and perceived accuracy was significant [$\chi^{2}(1)=7.25$,
$p=0.007$].

Figure 18 shows sharing rate means across true and false headlines for
conditions 2 and 3 which differ in whether participants provided reasoning.
Figure 19 shows that the sharing of headlines that are perceived as true is
reduced when reasoning is requested. The means in sharing rate of headlines
perceived as false however, do not vary much across the 2 conditions.

###  E.3. Effect of Reasoning Format

We observed that the effect of reasoning form when including spams was not
significant in either the veracity or the perceived accuracy models
[$\chi^{2}(1)=0.61$, $p=0.43$ in the veracity model, $\chi^{2}(1)=0.52$,
$p=0.47$ in the perceived accuracy model]. The effect of the interaction
between veracity and reasoning form was not significant either
[$\chi^{2}(1)=2.92$, $p=0.09$]. However, the interaction between reasoning
form and perceived accuracy was significant [$\chi^{2}(1)=14.81$, $p<0.001$].

Figure 18 shows the means across the conditions with different instruments for
capturing reasoning. Figure 19 shows that in condition 4 where checkboxes were
presented, people shared headlines that they initially perceived as false at a
higher rate compared to condition 3.

Table 6. Share means in spam entries across experimental conditions and headline veracity. Veracity. | Cond. 1 | Cond. 2 | Cond. 3 | Cond. 4
---|---|---|---|---
True | 0.76 | 0.70 | 0.67 | 0.70
False | 0.74 | 0.72 | 0.71 | 0.73

Figure 18. Share rate of true and false headlines across study conditions
including spam datapoints. The results suggest that people are less likely to
share both accurate and inaccurate content if they are asked to assess the
content’s accuracy although the reduction in shared false content is higher
(condition 1 vs 2). However, asking people to provide their reasoning in
addition to assessing accuracy does not result in a statistically significant
difference compared to if they only assess accuracy (condition 2 vs 3).
Similarly, there does not exist a statistically significant difference in
means of sharing true and false content across the reasoning format conditions
(condition 3 vs 4).

Figure 19. Share rate of headlines across study conditions including spam
datapoints for headlines that were perceived as true or false. In condition 3
where participants where asked about their rationales, the share mean for
headlines perceived as true was decreased compared to condition 2 (condition 2
vs 3). However, asking people people about their rationales via a checkbox
increases sharing of content that they initially perceived as false (condition
3 vs 4).

##  Appendix F Headlines Used in the Study of Behavioral Nudges

We present the headlines that we used in the user study of behavioral nudges
along with their veracity and partisanship. Partisanship of a headline was
rated by each participant that was presented the headline in the study. The
partisanship measure in the table is an average over all these ratings on
scale of -2 (more favorable for Democrats) to 2 (more favorable for
Republicans).


###### Abstract

We consider the problem of constructing prefix-free codes in which a
designated symbol, a space, can only appear at the end of codewords. We
provide a linear-time algorithm to construct almost-optimal codes with this
property, meaning that their average length differs from the minimum possible
by at most one. We obtain our results by uncovering a relation between our
class of codes and the class of one-to-one codes. Additionally, we derive
upper and lower bounds to the average length of optimal prefix-free codes with
a space in terms of the source entropy.

###### keywords:

codes; entropy; average length; prefix-free codes; one-to-one codes

Entropic Bounds on the Average Length of Codes with a Space Roberto Bruno† and
Ugo Vaccaro*,† Roberto Bruno and Ugo Vaccaro Correspondence<EMAIL_ADDRESS>These authors contributed equally to this work.

##  1 Introduction

Modern natural languages achieve the unique parsability of written texts by
inserting a special character (i.e., a space ) between words DW  (See wiki
for a few exceptions to this rule). Classical Information Theory, instead,
studies codes that achieve the unique parsability of texts by imposing diverse
combinatorial properties on the codeword set: e.g., the prefix property,
unique decipherability, etc. CT . With respect to the efficiency of such codes
(usually measured via the average number of code symbols per source symbol),
it is well known that the Shannon entropy of the information source
constitutes a fundamental lower bound for it. On the other hand, if one drops
the property of the unique parsability of code messages into individual
codewords, and simply requires that different source symbols be encoded with
different codewords, one can obtain codes (known as one-to-one codes) with
efficiency below the source Shannon entropy (although not too much below; see,
e.g., Alon ; Blundo ).

Jaynes Jaynes  took the approach of directly studying source codes in which a
designated character of the code alphabet is exclusively used as a word
delimiter. More precisely, Jaynes studied the possible decrease of the
noiseless channel capacity (see shannon , p. 8) associated with any code that
uses a designated symbol as an end-of-codeword mark, as compared with the
noiseless channel capacity of an unconstrained code. Quite interestingly,
Jaynes proved that the decrease of the noiseless channel capacity of codes
with an end-of-codeword mark becomes negligible, as the maximum codeword
length increases.

In this paper, we study the problem of constructing prefix-free codes where a
specific symbol (referred to as a ‘space’) can only be positioned at the end
of codewords. We refer to this kind of prefix code as prefix codes ending with
a space. We develop a linear-time algorithm that constructs ‘almost’-optimal
codes with this characteristic, in the sense that the average length of the
constructed codes is at most one unit longer than the shortest possible
average length of any prefix-free code in which the space can appear only at
the end of codewords. We prove this result by highlighting a connection
between our type of codes and the well-known class of one-to-one codes. We
also provide upper and lower limits of the average length of optimal prefix
codes ending with a space, expressed in terms of the source entropy and the
cardinality of the code alphabet.

The paper is structured as follows. In Section 2, we illustrate the
relationships between prefix codes ending with a space and one-to-one codes.
Specifically, we prove that, from one-to-one codes, one can easily construct
prefix codes ending with a space, and we give an upper bound on the average
length of the constructed codes. Successively, we show that, if we remove all
the spaces from the codewords of prefix codes ending with a space, one obtains
a one-to-one code. This result allows us to prove that the average length of
our prefix codes ending with a space differs from the minimum possible by at
most one. In Sections 4 and 3, we derive upper and lower bounds on the average
length of optimal prefix codes ending with a space in terms of the source
entropy and the cardinality of the code alphabet.

##  2 Relations between One-to-One Codes and Prefix Codes Ending with a Space

Let $S=\\{s_{1},\ldots,s_{n}\\}$ be the set of source symbols,
${\mathbf{p}}=(p_{1},\ldots,p_{n})$ be a probability distribution on the set
$S$ (that is, $p_{i}$ is the probability of source symbol $s_{i}$), and
$\\{0,\dots,k-1\\}$ be the code alphabet. We denote by $\\{0,\dots,k-1\\}^{+}$
the set of all non-empty sequences on the code alphabet $\\{0,\dots,k-1\\}$,
$k\geq 2$, and by $\\{0,\dots,k-1\\}^{+}\sqcup$ the set of all non-empty
$k$-ary sequences that ends with the special symbol $\sqcup$, i.e., the space
symbol.

A prefix-free code ending with a space is a one-to-one mapping:

$C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$

in which no codeword $C(s)$ is a prefix of another codeword $C(s^{\prime})$,
for any $s,s^{\prime}\in S$, $s\neq s^{\prime}$.

A $k$-ary one-to-one code (see Alon ; Blundo ; Courtade ; Kontoyiannis ; Kosut
; Szpankowski  and the references therein quoted) is a bijective mapping
$D:S\longmapsto\\{0,\dots,k-1\\}^{+}$ from $S$ to the set of all non-empty
sequences over the alphabet $\\{0,\dots,k-1\\}$, $k\geq 2$.

The average length of an arbitrary code for the set of source symbols
$S=\\{s_{1},\ldots,s_{n}\\}$, with probabilities
${\mathbf{p}}=(p_{1},\ldots,p_{n})$, is $\sum_{i=1}^{n}p_{i}\ell_{i}$, where
$\ell_{i}$ is the number of alphabet symbols in the codeword associated with
the source symbol $s_{i}$.

Without loss of generality, we assume that probability distribution
${\mathbf{p}=(p_{1},\ldots,p_{n})}$ is ordered, that is $p_{1}\geq\ldots\geq
p_{n}$. Under this assumption, it is apparent that the best one-to-one code
proceeds by assigning the shortest codeword (e.g., in the binary case,
codeword $0$) to the highest probability source symbol $s_{1}$, the next
shortest codeword $1$ to the source symbol $s_{2}$, the codeword $00$ to
$s_{3}$, the codeword $01$ to $s_{4}$, and so on.

An equivalent approach for constructing an optimal one-to-one code, which we
will use later, proceeds as follows: Let us consider the first $n$ non-empty
$k$-ary strings according to the radix order Knuth  (that is, the $k$-ary
strings are ordered by length and, for equal lengths, ordered according to the
lexicographic order). We assign the strings to the symbols
$s_{1},\ldots,s_{n}$ in $S$ by increasing the string length and, for equal
lengths, by inverse order according to the lexicographic order. For example,
in the binary case, we assign the codeword $1$ to the highest probability
source symbol $s_{1}$, the codeword $0$ to the source symbol $s_{2}$, the
codeword $11$ to $s_{3}$, the codeword $10$ to $s_{4}$, and so on. Therefore,
one can see that, in the general case of a $k$-ary code alphabet, $k\geq 2$,
an optimal one-to-one code of minimal average length assigns a codeword of
length $\ell_{i}$ to the $i$-th symbol $s_{i}\in S$, where $\ell_{i}$ is given
by:

$\ell_{i}=\lfloor\log_{k}((k-1)\,i+1)\rfloor.$ (1)

Moreover, the codewords of an optimal $k$-ary one-to-one code can be
represented as the nodes of a $k$-ary tree of maximum depth
$h=\lceil\log_{k}(n-\lceil n/k\rceil)\rceil$, where, for each node $v$, the
$k$-ary string (codeword) associated with $v$ is obtained by concatenating all
the labels in the path from the root of the tree to $v$.

It is evident that, if we apply the above encoding to a sequence of source
symbols, the obtained binary sequence is not uniquely parsable in terms of
individual codewords. Let us see how one can recover unique parsability by
appending a space $\sqcup$ to judiciously chosen codewords of an optimal one-
to-one code. To gain insight, let us consider the following example. Let
$S=\\{s_{1},s_{2},s_{3},s_{4},s_{5},s_{6},s_{7},s_{8},s_{9},s_{10}\\}$ be the
set of source symbols, and and let us assume that the code alphabet is
$\\{0,1\\}$. Under the standing hypothesis that $p_{1}\geq\ldots\geq p_{10}$,
one has that the best prefix-free code $C$ one can obtain by the procedure of
appending a space $\sqcup$ to codewords of the optimal one-to-one code for $S$
is the following:

$\displaystyle C(s_{1})$ $\displaystyle=1\sqcup$ $\displaystyle C(s_{2})$
$\displaystyle=0\sqcup$ $\displaystyle C(s_{3})$ $\displaystyle=11$
$\displaystyle C(s_{4})$ $\displaystyle=10$ $\displaystyle C(s_{5})$
$\displaystyle=01\sqcup$ $\displaystyle C(s_{6})$ $\displaystyle=00\sqcup$
$\displaystyle C(s_{7})$ $\displaystyle=011$ $\displaystyle C(s_{8})$
$\displaystyle=010$ $\displaystyle C(s_{9})$ $\displaystyle=001$
$\displaystyle C(s_{10})$ $\displaystyle=000.$

Observe that we started from the codewords of the optimal one-to-one code
constructed according to the second procedure previously described. Moreover,
note that the codewords associated with symbols $s_{1},s_{2},s_{5}$, and
$s_{6}$ necessitate the space character $\sqcup$ at their end; otherwise, the
unique parsability of some encoded sequences of source symbols would not be
guaranteed. On the other hand, the codewords associated with symbols
$s_{3},s_{4},s_{7},s_{8},s_{9}$, and $s_{10}$ do not necessitate the space
character $\sqcup$. Indeed, the codeword set

$\\{1\sqcup,0\sqcup,11,10,01\sqcup,00\sqcup,011,010,001,000\\}$

satisfies the prefix-free condition (i.e., no codeword is a prefix of any
other); therefore, it guarantees the unique parsability of any coded message
in terms of individual codewords.

The idea of the above example can be generalized, as shown in the following
lemma.

Let $S=\\{s_{1},\ldots,s_{n}\\}$ be the set of source symbols and
${\mathbf{p}}=(p_{1},\ldots,p_{n})$, $p_{1}\geq\ldots\geq p_{n}>0$, be a
probability distribution on $S$. Let $\\{0,\dots,k-1\\}$ be the $k\geq 2$-ary
code alphabet. We can construct a prefix-free code
$C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$, in
$O(n)$, such that its average length $L(C)$ satisfies

$\displaystyle L(C)$
$\displaystyle=L_{+}+\sum_{i=1}^{\frac{k^{{h}-1}-1}{k-1}-1}\\!\\!\\!\\!p_{i}+\sum_{i=\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil
n/k\rceil}^{\frac{k^{{h}}-1}{k-1}-1}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{i}$
(2) $\displaystyle\leq L_{+}+\sum_{i=1}^{\lceil n/k\rceil-1}p_{i},$ (3)

where $L_{+}$ is the average length of an optimal one-to-one code
$D:S\longmapsto\\{0,\dots,k-1\\}^{+}$ and $h=\lceil\log_{k}(n-\lceil
n/k\rceil)\rceil$.

###### Proof.

Under the standing hypothesis that the probabilities of the source symbols are
ordered from the largest to the smallest, we show how to construct a prefix-
free code—by appending the special character $\sqcup$ to the end of (some)
codewords of an optimal one-to-one code for $S$—having the average length
upper bounded by (2).

Among the class of all the prefix-free codes that one can obtain by appending
the character $\sqcup$ to the end of (some) codewords of an optimal one-to-one
code for $S$, we aim to construct the one with the minimum average length.
Therefore, we have to ensure that, in the $k$-ary tree representation of the
code, the following basic condition holds: For any pair of nodes $v_{i}$ and
$v_{j}$, $i<j$, associated with the symbols $s_{i}$ and $s_{j}$, the depth of
the node $v_{j}$ is not smaller than the depth of the node $v_{i}$. In fact,
if it were otherwise, the average length of the code could be improved.

Therefore, by recalling that $h=\lceil\log_{k}(n-\lceil n/k\rceil)\rceil$ is
the height of the $k$-ary tree associated with an optimal one-to-one code, we
have that the prefix-free code of the minimum average length that one can
obtain by appending the special character $\sqcup$ to the end of (some)
codewords of an optimal one-to-one code for $S$ assigns a codeword of length
$\ell_{i}$ to the $i$-th symbol $s_{i}\in S$, where $\ell_{i}$ is given by:

$\ell_{i}=\begin{cases}\lfloor\log_{k}((k-1)\,i+1)\rfloor+1,&\mbox{if
$i\leq\frac{k^{{h}-1}-1}{k-1}-1$},\\\
\lfloor\log_{k}((k-1)\,i+1)\rfloor+1,&\mbox{if
}i\geq\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil n/k\rceil\\\ &\mbox{ and
}i\leq\frac{k^{{h}}-1}{k-1}-1,\\\
\lfloor\log_{k}((k-1)\,i+1)\rfloor,&\mbox{otherwise}.\end{cases}$ (4)

We stress that the obtained prefix-free code is not necessarily a prefix-free
code $C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$ of
minimum average length. Now, we justify the expression (4). First, since the
probabilities $p_{1},\ldots,p_{n}$ are ordered in non-increasing fashion, the
codeword lengths $\ell_{i}$ of the code are ordered in non-decreasing fashion,
that is $\ell_{1}\leq\ldots\leq\ell_{n}$. Therefore, in the $k$-ary tree
representation of the code, it holds the desired basic condition: For any pair
of nodes $v_{i}$ and $v_{j}$, $i<j$, associated with the symbols $s_{i}$ and
$s_{j}$, the depth of the node $v_{i}$ is smaller than or equal to the depth
of the node $v_{j}$.

Furthermore, we need to append the space character only to the $k$-ary strings
that are the prefix of some others. Therefore, let us consider the first $n$
non-empty $k$-ary strings according to the radix order Knuth , in which, we
recall, the $k$-ary strings are ordered by length and, for equal lengths,
ordered according to the lexicographic order. We have that the number of
strings that are a prefix of some others is exactly
$\lceil\frac{n}{k}\rceil-1$. One obtains this number by seeing the strings as
corresponding to nodes in a $k$-ary tree with labels $0,\dots,k-1$ on the
edges. The number of strings that are a prefix of some others (among the $n$
strings) is exactly equal to the number of internal nodes (except the root) in
such a tree. This number of internal nodes is equal to
$\lceil\frac{N-1}{k}\rceil-1$, where $N$ is the total number of nodes that, in
our case, is equal to $N=n+1$ (i.e., $N$ counts also the root of the tree).

Moreover, starting from the optimal one-to-one code constructed according to
our second method, that is by assigning $k$-ary strings to the symbols by
increasing length and, for equal lengths, by inverse order according to the
lexicographic order, one can verify that the $\lceil\frac{n}{k}\rceil-1$
internal nodes are associated with the codewords of the symbols $s_{i}$, for
$i$ that goes from $1$ to $\frac{k^{{h}-1}-1}{k-1}-1$, and from
$\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil n/k\rceil$ to $\frac{k^{{h}}}{k-1}-2$.

In fact, since the height of the $k$-ary tree is ${h}=\lceil\log_{k}(n-\lceil
n/k\rceil)\rceil$ and since all the levels of the tree, except the last two,
are full, we need to append the space to all symbols from $1$ to
$\frac{k^{{h}-1}-1}{k-1}-1$. While on the second-to-last level, we have to
append the space only to the remaining internal nodes associated with the
symbols $s_{i}$, where $i$ goes from $\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil
n/k\rceil$ to $\frac{k^{{h}}-1}{k-1}-1$. Those remaining nodes are exactly,
among all the nodes in the second-to-last level, the ones associated with the
symbols that have smaller probabilities. Thus, we obtain (4).

Summarizing, we can construct a prefix-free code
$C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$, in
$O(n)$ time, with lengths defined as in (4), starting from an optimal one-to-
one code. Thus:

$\displaystyle L(C)=$ $\displaystyle\sum_{i=1}^{n}p_{i}\ell_{i}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}p_{i}\lfloor\log_{k}((k-1)\,i+1)\rfloor+\sum_{i=1}^{\frac{k^{{h}-1}-1}{k-1}-1}\\!\\!\\!\\!p_{i}+\sum_{i=\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil
n/k\rceil}^{\frac{k^{{h}}-1}{k-1}-1}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{i}$
$\displaystyle=$ $\displaystyle
L_{+}+\sum_{i=1}^{\frac{k^{{h}-1}-1}{k-1}-1}\\!\\!\\!\\!p_{i}+\sum_{i=\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil
n/k\rceil}^{\frac{k^{{h}}-1}{k-1}-1}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{i}$
$\displaystyle\leq$ $\displaystyle L_{+}+\sum_{i=1}^{\lceil
n/k\rceil-1}\\!\\!\\!\\!\\!p_{i}\quad\mbox{(since we are adding $\lceil
n/k\rceil-1$ $p_{i}$'s, and the $p_{i}$'s are ordered).}$

∎

Note that, from Lemma 2, we obtain that the average length of any optimal
(i.e., of minimum average length) prefix-free code ending with a space is
upper bounded by the formula (2). Furthermore, we have an upper bound on the
average length of the optimal prefix-free codes ending with a space in terms
of the average length of optimal one-to-one codes.

We can also derive a lower bound on the average length of optimal prefix-free
codes ending with a space in terms of the average length of optimal one-to-one
codes. For such a purpose, we need two intermediate results. We first recall
that, given a $k$-ary code $C$, its codewords can be represented as nodes in a
$k$-ary tree with labels $0,\dots,k-1$ on the edges. Indeed, for each node
$v$, the $k$-ary string (codeword) associated with $v$ can be obtained by
concatenating all the labels in the path from the root of the tree to $v$. We
also recall that, in prefix-free codes, the codewords correspond to the node
leaves of the associated tree, while in one-to-one codes, the codewords may
correspond also to the internal nodes of the associated tree.

Let $S=\\{s_{1},\ldots,s_{n}\\}$ be the set of source symbols, and let
${\mathbf{p}}=(p_{1},\ldots,p_{n})$, $p_{1}\geq\ldots\geq p_{n}>0$, be a
probability distribution on $S$. There exists an _optimal prefix-free_ code
ending with a space
$C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$ such that
the following property holds: For any internal node $v$ (except the root) of
the tree representation of $C$, if we denote by $w$ the $k$-ary string
associated with the node $v$, then the string $w\sqcup$ belongs to the
codeword set of $C$.

###### Proof.

Let $C$ be an arbitrary optimal prefix-free code ending with a space. Let us
assume that, in the tree representation of $C$, there exists an internal node
$v$ whose associated string $w$ is such that $w\sqcup$ does not belong to the
codeword set of $C$. Since $v$ is an internal node, there is at least a leaf
$x$, which is a descendant of $v$, whose associated string is the codeword of
some symbol $s_{j}$. We modify the encoding, by assigning the codeword
$w\sqcup$ to the symbol $s_{j}$. The new encoding is still prefix-free, and
its average length can only decrease since the length of the newly assigned
codeword to $s_{j}$ cannot be greater than the previous one. We can repeat the
argument for all internal nodes that do not satisfy the property stated in the
lemma to complete the proof. ∎

Let $C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$ be an
arbitrary prefix-free code, then the code
$D:S\longmapsto\\{0,\dots,k-1\\}^{+}$ one obtains from $C$ by removing the
space $\sqcup$ from each codeword of $C$ is a _one-to-one_ code.

###### Proof.

The proof is straightforward. Since $C$ is prefix-free, it holds that, for any
pair $s_{i},s_{j}\in S$, with $s_{i}\neq s_{j}$, the codeword $C(s_{i})$ is
not a prefix of $C(s_{j})$ and vice versa. Therefore, since $D$ is obtained
from $C$ by removing the space, we have four cases:

  1. 1.

$C(s_{i})=D(s_{i})$ and $C(s_{j})=D(s_{j})$: then $D(s_{i})\neq D(s_{j})$
since $C(s_{i})\neq C(s_{j})$;

  2. 2.

$C(s_{i})=D(s_{i})\sqcup$ and $C(s_{j})=D(s_{j})\sqcup$: then $D(s_{i})\neq
D(s_{j})$ since $C(s_{i})$ is not a prefix of $C(s_{j})$ and vice versa;

  3. 3.

$C(s_{i})=D(s_{i})\sqcup$ and $C(s_{j})=D(s_{j})$: then $D(s_{i})\neq
D(s_{j})$ since $C(s_{j})$ is not a prefix of $C(s_{i})$;

  4. 4.

$C(s_{i})=D(s_{i})$ and $C(s_{j})=D(s_{j})\sqcup$: then $D(s_{i})\neq
D(s_{j})$ since $C(s_{i})$ is not a prefix of $C(s_{j})$.

Therefore, for any pair $s_{i},s_{j}\in S$, with $s_{i}\neq s_{j}$,
$D(s_{i})\neq D(s_{j})$, and $D$ is a one-to-one code. ∎

We can now derive a lower bound on the average length of optimal prefix-free
codes with space in terms of the average length of optimal one-to-one codes.

Let $S=\\{s_{1},\ldots,s_{n}\\}$ be the set of source symbols, and let
${\mathbf{p}}=(p_{1},\ldots,p_{n})$, $p_{1}\geq\ldots\geq p_{n}>0$, be a
probability distribution on $S$, then the average of an optimal prefix-free
code $C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$
satisfies

$L(C)\geq L_{+}+\sum_{i=1}^{\lceil n/k\rceil-1}p_{n-i+1},$ (5)

where $L_{+}$ is the average length of an optimal $k$-ary one-to-one code on
$S$.

###### Proof.

From Lemma 2, we know that there exists an optimal prefix-free code $C$ with a
space in which exactly $\lceil\frac{n}{k}\rceil-1$ codewords contain the space
character at the end. Let $A\subset\\{1,\dots,n\\}$ be the set of indices
associated with the symbols whose codeword contains the space. Moreover, from
Lemma 2, we know that the code $D$ obtained by removing the space from $C$ is
a one-to-one code. Putting it all together, we obtain that

$\displaystyle L(D)=L(C)-\sum_{i\in A}p_{i}.$ (6)

From (6), we have that

$\displaystyle L(C)$ $\displaystyle=L(D)+\sum_{i\in A}p_{i}$
$\displaystyle\geq L_{+}+\sum_{i\in A}p_{i}\qquad\mbox{(since $D$ is a one-to-
one code)}$ $\displaystyle\geq L_{+}+\sum_{i=1}^{\lceil
n/k\rceil-1}\\!\\!\\!p_{n-i+1}\quad\mbox{(since $A$ contains
$\lceil\frac{n}{k}\rceil-1$ elements).}$

∎

We notice that the difference between the expression (2) and the lower bound
(5) is, because of (3), less than

$\sum_{i=1}^{\lceil n/k\rceil-1}p_{i}-\sum_{i=1}^{\lceil
n/k\rceil-1}p_{n-i+1}<1;$ (7)

therefore, the prefix-free codes ending with a space that we construct in
Lemma 2 have an average length that differs from the minimum possible by at
most one. Moreover, since both the upper bound (3) and the lower bound (5) are
easily computable, we can determine the average length of an optimal prefix-
free code $C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$
with a tolerance at most of one. One can also see that the left-hand side of
(7) is, often, much smaller than one.

In the following sections, we will focus on providing upper and lower bounds
on the average length $L_{+}$ of $k$-ary optimal one-to-one codes in terms of
the $k$-ary Shannon entropy
$H_{k}({\mathbf{p}})=-\sum_{i=1}^{n}p_{i}\log_{k}p_{i}$ of the source
distribution ${\mathbf{p}}$. Because of Lemma 2 and Lemma 2, this will give us
the corresponding upper and lower bounds on the average length of optimal
prefix-free codes ending with a space.

##  3 Lower Bounds on the Average Length

In this section, we provide lower bounds on the average length of the optimal
one-to-one code and, subsequently, thanks to Lemma 2, on the average length of
the optimal prefix-free code with a space. For technical reasons, it will be
convenient to consider one-to-one codes that make use of the empty word
$\epsilon$, that is one-to-one mappings
$D_{\epsilon}:S\longmapsto\\{0,1,\ldots,k-1\\}^{+}\cup\\{\epsilon\\}$. It is
easy to see (cf. (1)) that the optimal one-to-one code that makes use of the
empty word assigns to the $i$-th symbol $s_{i}\in S$ a codeword of length
$\ell_{i}$ given by:

$\ell_{i}=\lfloor\log_{k}((k-1)i)\rfloor.$ (8)

where $k$ is the cardinality of the code alphabet.

Thus, by denoting by $L_{+}$ the average length of the optimal one-to-one code
that does not make use of the empty word and with $L_{\epsilon}$ the average
length of the optimal one-to-one code that does use it, we obtain the
following relation:

$L_{+}=L_{\epsilon}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}\\!\\!\\!\\!\\!\\!p_{\frac{k^{i}-1}{k-1}}.$
(9)

Our first result is a generalization of the lower bound to the average length
of the optimal one-to-one codes presented in Blundo , from the binary case to
the general case of $k$-ary alphabets, $k\geq 2$. Our proof technique differs
from that of Blundo  since we are dealing with a set of source symbols of
bounded cardinality (in Blundo , the authors considered the case of a
numerable set of source symbols).

Let $S=\\{s_{1},\ldots,s_{n}\\}$ be the set of source symbols and
${\mathbf{p}}=(p_{1},\ldots,p_{n})$ be a probability distribution on $S$, with
$p_{1}\geq\ldots\geq p_{n}$. The average length $L_{\epsilon}$ of the optimal
one-to-one code
$D:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1\\}^{+}\cup\\{\epsilon\\}$
satisfies

$\displaystyle L_{\epsilon}>$ $\displaystyle
H_{k}({\mathbf{p}})-(H_{k}({\mathbf{p}})+\log_{k}(k-1))\log_{k}\left(1+\frac{1}{H_{k}({\mathbf{p}})+\log_{k}(k-1)}\right)$
$\displaystyle-\log_{k}(H_{k}({\mathbf{p}})+\log_{k}(k-1)+1),$

where $H_{k}({\mathbf{p}})=-\sum_{i=1}^{n}p_{i}\log_{k}p_{i}$.

###### Proof.

The proof is an adaptation of Alon et al.’s proof Alon  from the binary case
to the $k\geq 2$-ary case.

We recall that the optimal one-to-one code (i.e., whose average length
achieves the minimum $L_{\epsilon}$) has codeword lengths $\ell_{i}$ given by:

$\ell_{i}=\lfloor\log_{k}((k-1)i)\rfloor.$ (10)

For each $j\in\\{0,\dots,\lfloor\log_{k}n\rfloor\\}$, let us define the
quantities $q_{j}$ as

$q_{j}=\sum_{i=\frac{k^{j}-1}{k-1}+1}^{\frac{k^{j+1}-1}{k-1}}\\!\\!\\!\\!\\!p_{i}.$

It holds that $\sum_{j=0}^{\lfloor\log_{k}n\rfloor}q_{j}=1.$ Let ${Y}$ be a
random variable that takes values in $\\{0,\dots,\lfloor\log_{k}n\rfloor\\}$
according to the probability distribution
${\mathbf{q}}=(q_{0},\dots,q_{\lfloor\log_{k}n\rfloor})$, that is

$\forall j\in\\{0,\dots,\lfloor\log_{k}n\rfloor\\}\quad\Pr\\{{Y}=j\\}=q_{j}.$

From (10), we have

$\displaystyle L_{\epsilon}=$
$\displaystyle\sum_{i=1}^{n}\lfloor\log_{k}((k-1)i)\rfloor p_{i}$
$\displaystyle=$
$\displaystyle\sum_{j=0}^{\lfloor\log_{k}n\rfloor}\sum_{i=\frac{k^{j}-1}{k-1}+1}^{\frac{k^{j+1}-1}{k-1}}\lfloor\log_{k}((k-1)i)\rfloor
p_{i}$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{\lfloor\log_{k}n\rfloor}jq_{j}=\mathbb{E}[{Y}].$
(11)

By applying the entropy grouping rule (CT , Ex. 2.27) to the distribution
${\mathbf{p}}$, we obtain

$\displaystyle H_{2}({\mathbf{p}})$
$\displaystyle=H_{2}({\mathbf{q}})+\sum_{j=0}^{\lfloor\log_{k}n\rfloor}q_{j}H_{2}\left(\frac{p_{\frac{k^{j}-1}{k-1}+1}}{q_{j}},\dots,\frac{p_{\frac{k^{j+1}-1}{k-1}}}{q_{j}}\right)$
$\displaystyle\leq
H_{2}({\mathbf{q}})+\sum_{j=0}^{\lfloor\log_{k}n\rfloor}q_{j}\log_{2}k^{j}\hskip
28.45274pt\mbox{(since
$H_{2}\left(\frac{p_{\frac{k^{j}-1}{k-1}+1}}{q_{j}},\dots,\frac{p_{\frac{k^{j+1}-1}{k-1}}}{q_{j}}\right)\leq\log_{2}k^{j}$)}$
$\displaystyle=H_{2}({\mathbf{q}})+\sum_{j=0}^{\lfloor\log_{k}n\rfloor}jq_{j}\log_{2}k$
$\displaystyle=H_{2}({\mathbf{q}})+\mathbb{E}[{Y}]\log_{2}k.$ (12)

We now derive an upper bound to $H_{2}({Y})=H_{2}(q)$ in terms of the expected
value $\mathbb{E}[{Y}]$.

To this end, let us consider an auxiliary random variable ${Y}^{\prime}$ with
the same distribution of ${Y}$, but with values ranging from $1$ to
$\lfloor\log_{k}(n)\rfloor+1$ (instead of from $0$ to
$\lfloor\log_{k}(n)\rfloor$). It is easy to verify that
$\mu=\mathbb{E}[{Y}^{\prime}]=\mathbb{E}[{Y}]+1$.

Let $\alpha$ be a positive number, whose value will be chosen later. We obtain
that

$\displaystyle H_{k}({Y})-\alpha\mu$
$\displaystyle=\sum_{i=1}^{\lfloor\log_{k}(n)\rfloor+1}q_{i-1}\log_{k}\frac{1}{q_{i-1}}-\alpha\sum_{j=1}^{\lfloor\log_{k}(n)\rfloor+1}jq_{j-1}$
$\displaystyle=\sum_{i=1}^{\lfloor\log_{k}(n)\rfloor+1}q_{i-1}\log_{k}\frac{1}{q_{i-1}}+\sum_{j=1}^{\lfloor\log_{k}(n)\rfloor+1}(-\alpha
j)q_{j-1}$
$\displaystyle=\sum_{i=1}^{\lfloor\log_{k}(n)\rfloor+1}q_{i-1}\log_{k}\frac{1}{q_{i-1}}+\sum_{j=1}^{\lfloor\log_{k}(n)\rfloor+1}q_{j-1}\log_{k}(k^{-\alpha
j})$
$\displaystyle=\sum_{i=1}^{\lfloor\log_{k}(n)\rfloor+1}q_{i-1}\log_{k}\frac{k^{-\alpha
i}}{q_{i-1}}$
$\displaystyle\leq\log_{k}\sum_{i=1}^{\lfloor\log_{k}(n)\rfloor+1}k^{-\alpha
i}\qquad\qquad\mbox{( by Jensen's inequality)}$
$\displaystyle=\log_{k}\left[\left(\frac{1}{k^{\alpha}}\right)\left(\frac{1-k^{-\alpha(\lfloor\log_{k}(n)\rfloor+1}}{1-k^{-\alpha}}\right)\right]$
$\displaystyle\leq\log_{k}\left(\frac{1-k^{-\alpha(\log_{k}(n)+1)}}{k^{\alpha}-1}\right)$
$\displaystyle=\log_{k}\left(\frac{1-(kn)^{-\alpha}}{k^{\alpha}-1}\right).$

By substituting $\log_{k}\frac{\mu}{\mu-1}$ with $\alpha$ in the obtained
inequality

$H_{k}({Y})\leq\alpha\mu+\log_{k}\left(\frac{1-(kn)^{-\alpha}}{k^{\alpha}-1}\right),$

we obtain

$\displaystyle
H_{k}({Y})\leq\mu\log_{k}\frac{\mu}{\mu-1}+\log_{k}(\mu-1)+\log_{k}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\frac{\mu}{\mu-1}}\right).$
(13)

Since $\left(\frac{1}{kn}\right)^{\log_{k}\frac{\mu}{\mu-1}}$ is decreasing in
$\mu$, and because $\mu=\mathbb{E}[{Y}]+1>1$, we obtain:

$\displaystyle
H_{k}({Y})<\mathbb{E}[{Y}]\log_{k}\left(1+\frac{1}{\mathbb{E}[{Y}]}\right)+\log_{k}(\mathbb{E}[{Y}]+1).$
(14)

By applying (14) to (3) and since $H_{k}({Y})=\frac{H_{2}({Y})}{\log_{2}k}$,
we obtain

$\displaystyle H_{2}({\mathbf{p}})<$
$\displaystyle\mathbb{E}[{Y}]\log_{2}k+\mathbb{E}[{Y}]\log_{2}\left(1+\frac{1}{E[{Y}]}\right)+\log_{2}(E[{Y}]+1).$
(15)

From (11), we have that $L_{\epsilon}=\mathbb{E}[{Y}]$; moreover, from the
inequality (28) of Lemma 4 (proven in the next Section 4), we know that

$L_{\epsilon}\leq H_{k}({\mathbf{p}})+\log_{k}(k-1).$ (16)

Hence, since the function $f(z)=z\log_{k}\left(1+\frac{1}{z}\right)$ is
increasing in $z$, we can apply (16) to upper-bound the term

$\mathbb{E}[{Y}]\log_{2}\left(1+\frac{1}{E[{Y}]}\right),$

to obtain the following inequality:

$\displaystyle H_{2}({\mathbf{p}})<$ $\displaystyle
L_{\epsilon}\log_{2}k+(H_{k}({\mathbf{p}})+\log_{k}(k-1))\log_{2}\left(1+\frac{1}{H_{k}({\mathbf{p}})+\log_{k}(k-1)}\right)$
(17) $\displaystyle+\log_{2}(H_{k}({\mathbf{p}})+\log_{k}(k-1)+1).$

Rewriting (17), we finally obtain

$\displaystyle L_{\epsilon}>$ $\displaystyle
H_{k}({\mathbf{p}})-(H_{k}({\mathbf{p}})+\log_{k}(k-1))\log_{k}\left(1+\frac{1}{H_{k}({\mathbf{p}})+\log_{k}(k-1)}\right)$
$\displaystyle-\log_{k}(H_{k}({\mathbf{p}})+\log_{k}(k-1)+1),$

and that concludes our proof. ∎

By bringing into play the size of the largest mass in addition to the entropy,
Lemma 3 can be improved, as shown in the following result. Let
$S=\\{s_{1},\ldots,s_{n}\\}$ be the set of source symbols and
${\mathbf{p}}=(p_{1},\ldots,p_{n})$, $p_{1}\geq\ldots\geq p_{n}$, be a
probability distribution on $S$. The average length $L_{\epsilon}$ of the
optimal one-to-one code
$D:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1\\}^{+}\cup\\{\epsilon\\}$ has the
following lower bounds:

1. If $0<p_{1}\leq 0.5$,

$\displaystyle L_{\epsilon}\geq$ $\displaystyle
H_{k}({\mathbf{p}})-(H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1))$
$\displaystyle\log_{k}\left(1+\frac{1}{H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)}\right)$
$\displaystyle-\log_{k}(H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)+1)$
$\displaystyle-\log_{k}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\left(1+\frac{1}{1-p_{1}}\right)}\right),$
(18)

2\. if $0.5<p_{1}\leq 1$

$\displaystyle L_{\epsilon}\geq$ $\displaystyle
H_{k}({\mathbf{p}})-(H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(1+\log_{k}(k-1)))$
$\displaystyle\log_{k}\left(1+\frac{1}{H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(1+\log_{k}(k-1))}\right)$
$\displaystyle-\log_{k}(H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(1+\log_{k}(k-1))+1)$
$\displaystyle-\log_{k}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\left(1+\frac{1}{1-p_{1}}\right)}\right),$
(19)

where $\mathcal{H}_{k}(p_{1})=-p_{1}\log_{k}p_{1}-(1-p_{1})\log_{k}(1-p_{1})$.

###### Proof.

The proof is the same as the proof of Lemma 3. However, we change two steps in
the demonstration.

First, since

$\left(\frac{1}{kn}\right)^{\log_{k}\frac{\mu}{\mu-1}}=\left(\frac{1}{kn}\right)^{\log_{k}\frac{\mathbb{E}[{Y}]+1}{\mathbb{E}[{Y}]}}=\left(\frac{1}{kn}\right)^{\log_{k}\left(1+\frac{1}{\mathbb{E}[{Y}]}\right)}$

is decreasing in $\mu$ and
$\mathbb{E}[{Y}]=L_{\epsilon}=0p_{1}+1p_{2}+\dots\geq 1-p_{1}$, we have

$\log_{k}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\frac{\mu}{\mu-1}}\right)\leq\log_{k}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\left(1+\frac{1}{1-p_{1}}\right)}\right).$
(20)

Hence, by applying (20) to the right-hand side of (13), we obtain

$H_{k}({Y})\leq\mathbb{E}[{Y}]\log_{k}\left(1+\frac{1}{\mathbb{E}[{Y}]}\right)+\log_{k}(\mathbb{E}[{Y}]+1)+\log_{k}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\left(1+\frac{1}{1-p_{1}}\right)}\right).$
(21)

Now, by applying (21) (instead of (14)) to (3) and since
$H_{k}({Y})=\frac{H_{2}({Y})}{\log_{2}k}$, we obtain

$\displaystyle H_{2}({\mathbf{p}})\leq$
$\displaystyle\mathbb{E}[{Y}]\log_{2}k+\mathbb{E}[{Y}]\log_{2}\left(1+\frac{1}{E[{Y}]}\right)+\log_{2}(E[{Y}]+1)$
$\displaystyle+\log_{2}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\left(1+\frac{1}{1-p_{1}}\right)}\right).$
(22)

Here, instead of applying the upper bound:

$L_{\epsilon}\leq H_{k}({\mathbf{p}})+\log_{k}(k-1)$

of Lemma 4 to the right-hand side of (3), we apply the improved version:

$L_{\epsilon}\leq\begin{cases}H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)\text{
if }\ 0<p_{1}\leq 0.5,\\\
H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})\log_{k}2(k-1)\text{ if }\
0.5<p_{1}\leq 1,\end{cases}$

proven in Lemma 4 of the Section 4. Then, we simply need to rewrite the
inequality, concluding the proof. ∎

Thanks to Lemma 2 and the formula (9), the above lower bounds on
$L_{\epsilon}$ can be applied to derive our main results for prefix-free codes
with a space, as shown in the following theorems. The average length of an
optimal prefix-free code with space
$C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$ satisfies

$\displaystyle L(C)>$ $\displaystyle
H_{k}({\mathbf{p}})-(H_{k}({\mathbf{p}})+\log_{k}(k-1))\log_{k}\left(1+\frac{1}{H_{k}({\mathbf{p}})+\log_{k}(k-1)}\right)$
$\displaystyle-\log_{k}(H_{k}({\mathbf{p}})+\log_{k}(k-1)+1)+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}{p_{n-i+1}}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}.$
(23)

###### Proof.

From Lemma 2 and the formula (9), we have

$L(C){\geq}L_{\epsilon}+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}{p_{n-i+1}}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}.$
(24)

By applying the lower bound (3) of Lemma 3 to (24), we obtain (3). ∎

Analogously, by exploiting (the possible) knowledge of the maximum source
symbol probability value, we have the following result.

The average length of the optimal prefix-free code with space
$C:S\longmapsto\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$ has the
following lower bounds:

1. If $0<p_{1}\leq 0.5$:

$\displaystyle L(C)\geq$ $\displaystyle
H_{k}({\mathbf{p}})-(H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1))$
$\displaystyle\log_{k}\left(1+\frac{1}{H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)}\right)$
$\displaystyle-\log_{k}(H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)+1)$
$\displaystyle-\log_{k}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\left(1+\frac{1}{1-p_{1}}\right)}\right)+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}{p_{n-i+1}}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}.$
(25)

2. If $0.5<p_{1}\leq 1$:

$\displaystyle L(C)\geq$ $\displaystyle
H_{k}({\mathbf{p}})-(H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(1+\log_{k}(k-1)))$
$\displaystyle\log_{k}\left(1+\frac{1}{H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(1+\log_{k}(k-1))}\right)$
$\displaystyle-\log_{k}(H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(1+\log_{k}(k-1))+1)$
$\displaystyle-\log_{k}\left(1-\left(\frac{1}{kn}\right)^{\log_{k}\left(1+\frac{1}{1-p_{1}}\right)}\right)+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}{p_{n-i+1}}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}.$
(26)

###### Proof.

From Lemma 2 and the formula (9), we have

$L(C){\geq}L_{\epsilon}+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}{p_{n-i+1}}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}.$
(27)

By applying the lower bounds (3)-(3) of Lemma 3 to (27), we obtain (3) or (3)
according to the value of the maximum source symbol probability. ∎

##  4 Upper Bounds on the Average Length

In this section, we will first derive upper bounds on the average length of
optimal one-to-one codes. Successively, we will provide corresponding upper
bounds on the average length of optimal prefix-free codes ending with a space.

We start by extending the result obtained in Wyner  from the binary case to
the $k$-ary case, $k\geq 2$. Let $S=\\{s_{1},\ldots,s_{n}\\}$ be the set of
source symbols and ${\mathbf{p}}=(p_{1},\ldots,p_{n})$, $p_{1}\geq\ldots\geq
p_{n}$, be a probability distribution on $S$. The average length
$L_{\epsilon}$ of the optimal one-to-one code
$D:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1\\}^{+}\cup\\{\epsilon\\}$
satisfies

$L_{\epsilon}\leq H_{k}({\mathbf{p}})+\log_{k}(k-1).$ (28)

###### Proof.

Under the standing hypothesis that $p_{1}\geq\ldots\geq p_{n}$, it holds that

$\forall i=1,\ldots,n\qquad p_{i}\leq\frac{1}{i}.$ (29)

We recall that the length of the $i$-th codeword of the optimal one-to-one
code $D$ is equal to

$\ell_{i}=\lfloor\log_{k}((k-1)i)\rfloor.$ (30)

Therefore, from (29), we can upper bound each length $\ell_{i}$ as

$\ell_{i}=\lfloor\log_{k}((k-1)i)\rfloor\leq\log_{k}((k-1)i)\leq\log_{k}(k-1)+\log_{k}\frac{1}{p_{i}}.$
(31)

Hence, by applying (31) to the average length of $D$, we obtain

$L_{\epsilon}=\sum_{i=1}^{n}p_{i}\ell_{i}\leq\sum_{i=1}^{n}p_{i}\left(\log_{k}(k-1)+\log_{k}\frac{1}{p_{i}}\right)=H_{k}({\mathbf{p}})+\log_{k}(k-1).$
(32)

This concludes our proof. ∎

By exploiting the knowledge of the maximum probability value of
${\mathbf{p}}$, we generalize the upper bound in Blundo  from $k=2$ to
arbitrary $k\geq 2$.

Let $S=\\{s_{1},\ldots,s_{n}\\}$ be the set of source symbols and
${\mathbf{p}}=(p_{1},\ldots,p_{n})$, $p_{1}\geq\ldots\geq p_{n}$, be a
probability distribution on $S$. The average length $L_{\epsilon}$ of the
optimal one-to-one code
$D:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1\\}^{+}\cup\\{\epsilon\\}$
satisfies

$L_{\epsilon}\leq\begin{cases}H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)\text{
if }0<p_{1}\leq 0.5,\\\
H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})\log_{k}2(k-1)\text{ if
}0.5<p_{1}\leq 1.\end{cases}$ (33)

###### Proof.

Let us prove first that the length of an optimal one-to-one code satisfies the
inequality:

$\displaystyle L_{\epsilon}\leq$
$\displaystyle\sum_{i=2}^{n}p_{i}\log_{k}(i(k-1))-0.5\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}\\!\\!\\!\\!\\!\\!p_{\frac{k^{j}-1}{k-1}}.$ (34)

Indeed, by recalling that $\ell_{1}=\lfloor\log_{k}(k-1)\rfloor=0$, we can
write $L_{\epsilon}$ as follows:

$\displaystyle L_{\epsilon}=$
$\displaystyle\sum_{i=2}^{n}p_{i}\lfloor\log_{k}(i(k-1))\rfloor$
$\displaystyle=$ $\displaystyle\sum_{j\geq 1:\frac{k^{j}-1}{k-1}+1\leq
n}\sum_{i=\frac{k^{j}-1}{k-1}+1}^{\min(\frac{k^{j+1}-1}{k-1}-1,n)}p_{i}\lfloor\log_{k}(i(k-1))\rfloor+\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq
n}p_{\frac{k^{j}-1}{k-1}}\left\lfloor\log_{k}\left(\frac{k^{j}-1}{k-1}(k-1)\right)\right\rfloor$
$\displaystyle=$ $\displaystyle\sum_{j\geq 1:\frac{k^{j}-1}{k-1}+1\leq
n}\sum_{i=\frac{k^{j}-1}{k-1}+1}^{\min(\frac{k^{j+1}-1}{k-1}-1,n)}p_{i}\lfloor\log_{k}(i(k-1))\rfloor+\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}p_{\frac{k^{j}-1}{k-1}}\log_{k}(k^{j}-1)$
$\displaystyle-\sum_{j\geq 2:\frac{k^{j}-1}{k-1}\leq
n}p_{\frac{k^{j}-1}{k-1}}(\log_{k}(k^{j}-1)-\lfloor\log_{k}(k^{j}-1)\rfloor)$
$\displaystyle\leq$
$\displaystyle\sum_{i=2}^{n}p_{i}\log_{k}(i(k-1))-\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq
n}p_{\frac{k^{j}-1}{k-1}}(\log_{k}(k^{j}-1)-\lfloor\log_{k}(k^{j}-1)\rfloor),$

where the last inequality holds since

$\sum_{j\geq 1:\frac{k^{j}-1}{k-1}+1\leq
n}\sum_{i=\frac{k^{j}-1}{k-1}+1}^{\min(\frac{k^{j+1}-1}{k-1}-1,n)}p_{i}\lfloor\log_{k}(i(k-1))\rfloor\leq\sum_{j\geq
1:\frac{k^{j}-1}{k-1}+1\leq
n}\sum_{i=\frac{k^{j}-1}{k-1}+1}^{\min(\frac{k^{j+1}-1}{k-1}-1,n)}p_{i}\log_{k}(i(k-1)).$

We note that the function
$f(j)=\log_{k}(k^{j}-1)-\lfloor\log_{k}(k^{j}-1)\rfloor$ is increasing in $j$.
Therefore, it reaches the minimum at $j=2$, where it takes the value

$\log_{k}(k^{2}-1)-\lfloor\log_{k}(k^{2}-1)\rfloor=1+\log_{k}\left(1-\frac{1}{k^{2}}\right)>0.5,$

for any $k\geq 2$. Thus, (34) holds as we claimed.

Let us now show that

$L_{\epsilon}\leq
H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)-0.5\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}p_{\frac{k^{j}-1}{k-1}}.$ (35)

Since the distribution ${\mathbf{p}}$ is ordered in a non-increasing fashion,
from (29) and (34), we have

$\displaystyle L_{\epsilon}$
$\displaystyle\leq\sum_{i=2}^{n}p_{i}\log_{k}(i(k-1))-0.5\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}p_{\frac{k^{j}-1}{k-1}}$
$\displaystyle\leq\sum_{i=2}^{n}p_{i}\log_{k}\frac{1}{p_{i}}(k-1)-0.5\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}p_{\frac{k^{j}-1}{k-1}}\hskip
28.45274pt\mbox{(since $i\leq\frac{1}{p_{i}}$)}$
$\displaystyle=H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)-0.5\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}p_{\frac{k^{j}-1}{k-1}}.$

Therefore, (35) holds.

To conclude the proof, it remains to prove that

$L_{\epsilon}\leq
H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(\log_{k}2(k-1))-0.5\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}p_{\frac{k^{j}-1}{k-1}}.$ (36)

By observing that for any $i\geq 2$, it holds that

$p_{i}\leq\frac{2(1-p_{1})}{i},$ (37)

we obtain:

$\displaystyle L_{\epsilon}$
$\displaystyle\leq\sum_{i=2}^{n}p_{i}\log_{k}(i(k-1))-0.5\\!\\!\\!\\!\\!\\!\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}\\!\\!\\!p_{\frac{k^{j}-1}{k-1}}$
$\displaystyle\leq\sum_{i=2}^{n}p_{i}\log_{k}\left(\frac{2(1-p_{1})}{p_{i}}(k-1)\right)-0.5\\!\\!\\!\\!\\!\\!\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}\\!\\!\\!\\!\\!p_{\frac{k^{j}-1}{k-1}}\hskip
5.69046pt\mbox{(since from (\ref{eq2}), we have
$i\leq\frac{2(1-p_{1})}{p_{i}}$)}$
$\displaystyle=H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(\log_{k}2+\log_{k}(1-p_{1})+\log_{k}(k-1))(1-p_{1})-0.5\\!\\!\\!\\!\\!\\!\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}\\!\\!\\!p_{\frac{k^{j}-1}{k-1}}$
$\displaystyle=H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(\log_{k}2(k-1))-0.5\\!\\!\\!\\!\\!\\!\\!\\!\sum_{j\geq
2:\frac{k^{j}-1}{k-1}\leq n}p_{\frac{k^{j}-1}{k-1}}.$

Therefore, (36) holds as well.

From (35) and (36), since

$\sum_{j\geq 2:\frac{k^{j}-1}{k-1}\leq n}p_{\frac{k^{j}-1}{k-1}}\geq 0,$

we obtain

$L_{\epsilon}\leq
H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1),$

and

$L_{\epsilon}\leq
H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})(\log_{k}2(k-1)).$

Now, it is easy to verify that
$p_{1}\log_{k}\frac{1}{p_{1}}\geq\mathcal{H}_{k}(p_{1})+(1-p_{1})\log_{k}2$
for $0<p_{1}\leq 0.5$, proving the Lemma. ∎

Thanks to the result of Lemma 2 and to the formula (9), the upper bounds
obtained above can be used to derive our upper bounds on the average length of
optimal prefix-free codes with space, as shown in the following theorems.

The average length of an optimal prefix-free code with space
$C:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$
satisfies

$\displaystyle L(C)\leq$ $\displaystyle
H_{k}({\mathbf{p}})+\log_{k}(k-1)+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}$
$\displaystyle+{\sum_{i=1}^{\frac{k^{{h}-1}-1}{k-1}-1}\\!\\!\\!\\!p_{i}+\sum_{i=\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil
n/k\rceil}^{\frac{k^{{h}}-1}{k-1}-1}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{i}}$
(38) $\displaystyle\leq$ $\displaystyle
H_{k}({\mathbf{p}})+\log_{k}(k-1)+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}p_{i},$
(39)

where $h=\lceil\log_{k}(n-\lceil n/k\rceil)\rceil$.

###### Proof.

From Lemma 2 and the formula (9), we have

$\displaystyle L(C)\leq$ $\displaystyle
L_{\epsilon}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}$
$\displaystyle+{\sum_{i=1}^{\frac{k^{{h}-1}-1}{k-1}-1}\\!\\!\\!\\!p_{i}+\sum_{i=\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil
n/k\rceil}^{\frac{k^{{h}}-1}{k-1}-1}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{i}}.$
(40)

By applying the upper bound (28) on $L_{\epsilon}$ of Lemma 4 to (40), we
obtain (4). ∎

The average length of an optimal prefix-free code with space
$C:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$
satisfies

$\displaystyle
L(C)\leq\begin{cases}H_{k}({\mathbf{p}})-p_{1}\log_{k}\frac{1}{p_{1}}+(1-p_{1})\log_{k}(k-1)\\\
+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}p_{i}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}\hskip
56.9055pt\text{ if }0<p_{1}\leq 0.5,\vspace{0.5cm}\\\
H_{k}({\mathbf{p}})-\mathcal{H}_{k}(p_{1})+(1-p_{1})\log_{k}2(k-1)\\\
+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}p_{i}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}\hskip
56.9055pt\text{ if }0.5<p_{1}\leq 1.\end{cases}$ (41)

###### Proof.

From Lemma 2 and the formula (9) and by recalling that
$h=\lceil\log_{k}(n-\lceil n/k\rceil)\rceil$, we have

$\displaystyle L(C)\leq$ $\displaystyle
L_{\epsilon}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}$
$\displaystyle+{\sum_{i=1}^{\frac{k^{{h}-1}-1}{k-1}-1}\\!\\!\\!\\!p_{i}+\sum_{i=\frac{k^{{h}}+k^{{h}-1}-2}{k-1}-\lceil
n/k\rceil}^{\frac{k^{{h}}-1}{k-1}-1}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!p_{i}}$
$\displaystyle\leq$ $\displaystyle
L_{\epsilon}+\sum_{i=1}^{\lceil\frac{n}{k}\rceil-1}p_{i}+\sum_{i=1}^{\lfloor\log_{k}\lceil\frac{n-1}{k}\rceil\rfloor}p_{\frac{k^{i}-1}{k-1}}.$
(42)

We apply the upper bound (33) on $L_{\epsilon}$ of Lemma 4 to (42). That gives
us (41). ∎

One can estimate how much the average length of optimal prefix-free codes
ending with a space differs from the minimum average length of _unrestricted_
optimal prefix-free codes on the alphabet $\\{0,1,\ldots,k-1,\sqcup\\}$, that
is optimal prefix-free codes in which the special symbol $\sqcup$ is not
constrained to appear at the end of the codewords, only.

Let $S=\\{s_{1},\ldots,s_{n}\\}$ be the set of source symbols and
$\mathbf{p}=(p_{1},\ldots,p_{n})$ be a probability distribution on $S$. Let us
denote by
$C_{\sqcup}:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1\\}^{+}\cup\\{0,\dots,k-1\\}^{+}\sqcup$
an optimal prefix-free code ending with a space for $S$ and by
$C:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1,\sqcup\\}^{+}$ an optimal prefix-
free code without the restriction of where the space can occur. Clearly,
$L(C_{\sqcup})<H_{k}(\mathbf{p})+1$, since the more constrained optimal code
$C^{\prime}:\\{s_{1},\dots,s_{n}\\}\to\\{0,\dots,k-1\\}^{+}$ has an average
length less than $H_{k}(\mathbf{p})+1$. Therefore,

$\displaystyle L(C_{\sqcup})-L(C)<$ $\displaystyle H_{k}(\mathbf{p})+1-L(C)$
$\displaystyle\leq$ $\displaystyle
H_{k}(\mathbf{p})+1-H_{k+1}(\mathbf{p})\qquad\mbox{(since $L(C)\geq
H_{k+1}(\mathbf{p})$)}$ $\displaystyle=$ $\displaystyle
H_{k}(\mathbf{p})\left(1-\frac{1}{\log_{k}(k+1)}\right)+1.$

Since $\lim_{k\to\infty}\log_{k}(k+1)=1$, we have that, as the cardinality of
the code alphabet increases, the constraint that the space can appear only at
the end of codewords becomes less and less influential.

##  5 Concluding Remarks

In this paper, we have introduced the class of prefix-free codes where a
specific symbol (referred to as a “space") can only appear at the end of
codewords. We have proposed a linear-time algorithm to construct
“almost"-optimal codes with this characteristic, and we have shown that their
average length is at most one unit longer than the minimum average length of
any prefix-free code in which the space can appear only at the end of
codewords. We have proven this result by highlighting a connection between our
type of codes and the well-known class of one-to-one codes. We have also
provided upper and lower limits of the average length of optimal prefix-free
codes ending with a space, expressed in terms of the source entropy and the
cardinality of the code alphabet.

We leave open the problem of providing an efficient algorithm to construct
optimal prefix-free codes ending with a space. It seems that there is no easy
way to modify the classical Huffman greedy algorithm to solve our problem. It
is possible that the more powerful dynamic programming approach could be
useful to provide an optimal solution to the problem, as done in CG  for
optimal binary codes ending with ones. This will be the subject of future
investigations.

References

## References

  * (1) Daniels, P.T.; Bright, W. (Eds.) The World’s Writing Systems, Oxford University Press: Oxford, UK, 1996.
  * (2) Wikipedia: Writing systems without word boundaries. Available online: https://en.wikipedia.org/wiki/Category:Writing_systems_without_word_boundaries (accessed on:March 25, 2024)
  * (3) Cover, T. M.; Thomas, J.A. Elements of Information Theory, 2nd ed.; Wiley-Interscience: Hoboken, NJ, USA , 2006.
  * (4) Alon, N.; Orlitsky. A. A lower bound on the expected length of one-to-one codes. IEEE Trans. Inf. Theory 1994, 40, 1670–1672.
  * (5) Blundo, C.; De Prisco, R. New bounds on the expected length of one-to-one codes. IEEE Trans. Inf. Theory 1996, 42, 246–250.
  * (6) Jaynes, E. Note on unique decipherability. Ire Trans. Inf. Theory 1959, 5, 98–102.
  * (7) Shannon, C.E. The Mathematical Theory of Communication, University of Illinois Press: Urbana, IL, USA, 1949.
  * (8) Courtade, T.; Verdú, S.; Cumulant generating function of codeword lengths in optimal lossless compression. IEEE Int. Symp. Inf. Theory 2014, 2494–2498.
  * (9) Kontoyiannis, I.; Verdú, S. Optimal lossless data compression: non-asymptotics and asymptotics. IEEE Trans. Inf. Theory 2014, 60, 777–795.
  * (10) Kosut, O.; Sankar, L. Asymptotics and non-asymptotics for universal Fixed-to-Variable source coding. IEEE Trans. Inf. Theory 2017, 63, 3757–3772.
  * (11) Szpankowski, W.; Verdu, S. Minimum expected length of Fixed-to-Variable lossless compression without prefix constraints. IEEE Trans. Inf. Theory 2011, 57, 4017–4025.
  * (12) Knuth, D. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching; Publisher: Addison Wesley Longman Publishing Co., Inc.: Boston, MA, USA, 1998.
  * (13) Wyner, A. An upper bound on the entropy series. Inf. Control 1972, 20, 176–181.
  * (14) Chan, S.-L.; Golin M.J. A dynamic programming algorithm for constructing optimal 1-ended binary prefix-free codes. IEEE Trans. Inf. Theory 2000, 46, 1637–1644.