# Transverse spectrum of bremsstrahlung in finite condensed media

X.Feal<EMAIL_ADDRESS>R.A.Vazquez<EMAIL_ADDRESS>Departamento de Física de Partículas & Instituto Galego de Física de Altas
Enerxías
Universidade de Santiago de Compostela, 15782 Santiago, SPAIN

###### Abstract

A formalism is presented in which the radiation of photons off high energy
electrons during a multiple scattering process with finite condensed media can
be evaluated for a general interaction. We show that the arising Landau-
Pomeranchuk-Migdal suppression for finite size targets saturates at some
characteristic photon energy. Medium coherence effects in the photon
dispersion relation can be also considered leading to a dielectric suppression
or transition radiation effects in the soft part of the spectrum. The main
results of our formulation are presented for a Debye screened interaction and
its well-known Fokker-Planck approximation, showing that for finite size
targets or for the angular distributions of the final particles the
differences between both scenarios cannot be reconciled into a single
redefinition of the medium transport parameter $(\hat{q})$. Our predictions
are in very good agreement with the experimental data collected at SLAC.

##  I Introduction

The Landau-Pomeranchuk-Migdal (LPM) suppression is a well known effect that
has been extensively studied. Interference phenomena in a multiple scattering
scenario was initially considered by Ter-Mikaelian as the mechanism regulating
the amount of scattering centers which can coherently emit as a single
bremsstrahlung source Termikaelian1953 . A classical evaluation of this effect
for a semi-infinite medium was soon introduced by Landau and Pomeranchuk
Landau1953a ; Landau1953b  and later completed by Migdal Migdal1956  for the
quantum case by means of a Boltzmann transport equation for the electron. This
calculation has shown that except for the spin corrections for hard photons,
the LPM suppression for an averaged target still agrees with the expected
classical behavior of the infrared divergence. Further and more recent
developments in various approaches have been introduced since then by
Blankenbecler and Drell Blankenbecler1 ; Blankenbecler2 ; Blankenbecler3 ,
Zakharov Zakharov2 ; Zakharov3 ; Zakharov1 ; Zakharov3a ; Zakharov4 ;
Zakharov5 ; Zakharov6 , the Baier-Dokshitzer-Mueller-Schiff-Peigné group
(BDMPS) RBaier , Baier and Katkov VBaier1 ; VBaier3 ; VBaier4  and Wiedemann
and Gyulassy Wiedemann1 , and extensive reviews were presented in Klein ;
VBaier2 . We note, however, that all the existing calculations were done in
the Fokker-Planck approximation, which both in the Boltzmann transport
approach Migdal1956 ; RBaier  and in the path integral formulation Zakharov2 ;
Wiedemann1  lead to a Gaussian distribution of momenta. In this approximation,
then, the transport properties of the medium have to be adequated to take into
account the neglected large momentum tails of the original Debye screened or
Coulomb interactions. Few works, on the other hand, considered the finite
target case, which has always been problematic and sometimes misunderstood
lacking a general formulation. Also, the angular distribution of the final
particles has not been studied in general Wiedemann1 . Taking into account
these remarks, no result has ever been given beyond the Fokker-Planck
approximation, that also accounts for the transverse photon and electron
spectrum, and which includes in a natural way the finiteness of the target.

We have developed a formalism and a Monte Carlo code which allows for the
computation of the bremsstrahlung spectrum of finite targets, arbitrary
interactions and with a full control of the kinematics of the process, so that
specific cuts on momenta of the final electron and photon can be applied. In
section II we will briefly explain the LPM effect, review the formalism, and
give several approximations for the calculation. In section III, we will
present and compare our results with the experimental data of SLAC Anthony3 .
Finally, we end in section IV with some conclusions.

##  II Formalism and calculation

It has been predicted by Ter-Mikaelian Termikaelian1953  and Landau and
Pomeranchuk Landau1953a  that at high energies the Bethe-Heitler cross section
Bethe1934  stops being applicable to extended media. In order to understand
this phenomenon we start with the emission amplitude for a process consisting
in a collision with $(n)$ sources

$\displaystyle\mathcal{M}_{em}^{(n)}=-ie\int
d^{4}y\medspace\bar{\psi}_{f}^{(n)}(y)\gamma^{\mu}A_{\mu}^{\lambda}(y)\psi_{i}^{(n)}(y)+\mathcal{O}(e^{2}),$
(1)

where $A_{\mu}^{\lambda}(y)=\mathcal{N}(k)\epsilon_{\mu}^{\lambda}e^{ik\cdot
y}$ is a free photon of momentum $k$ and polarization $\lambda$ and
$\mathcal{N}(k)=\sqrt{2\pi/\omega}$ its normalization, $\Psi_{i,f}^{(n)}(x)$
the incoming and outgoing electron wave functions under the external field of
the medium and $e=\sqrt{\alpha}$ the electron charge. Since in the $\omega\to
0$ limit the number of photons diverges, in virtue of the soft photon theorem
Weinberg1965 , the classical approximation holds bloch1937  and we can replace

$\displaystyle J_{k}(x)=\bar{\Psi}_{f}^{(n)}(x)\gamma_{k}\Psi_{i}^{(n)}(x)\to
J_{k}(x)\equiv v_{k}(t)\medspace\delta^{3}(\bm{x}-\bm{x}(t)),$ (2)

where $\bm{v}(t)\equiv\dot{\bm{x}}(t)$ is the electron velocity, yielding (see
Jackson ; Bell1958

$\displaystyle\mathcal{M}_{em}^{(n)}=-ie\mathcal{N}(k)\int^{+\infty}_{-\infty}dt\medspace\bigg{(}\frac{\bm{k}}{\omega}\times\bm{v}(t)\bigg{)}e^{i\omega
t-i\bm{k}\cdot\bm{x}(t)},$ (3)

and where we used $\bm{\epsilon}^{\lambda}\cdot\bm{k}=0$. One can consider the
integration over time as the point in which the photon is emitted. This
observation becomes manifest by letting the electron describe a discretized
trajectory, with velocities $\bm{v}_{j}$ for $j=1,\ldots,n_{c}+1$ and
piecewise path $\bm{x}_{j}=\bm{x}_{j-1}+\bm{v}_{j-1}(t_{j}-t_{j-1})$, where
$n_{c}$ is the number of collisions. Equation (3) then produces

$\displaystyle\mathcal{M}_{em}^{(n)}=e\mathcal{N}(k)\frac{1}{\omega}\sum_{j=1}^{n_{c}}\bm{\delta}_{j}\medspace
e^{i\varphi_{j}},$ (4)

where we find a superposition of $n_{c}$ single Bethe-Heitler like amplitudes
Bethe1934  of the form

$\displaystyle\bm{\delta}_{j}\equiv\bm{k}\times\bigg{(}\frac{\bm{v}_{j+1}}{\omega-\bm{k}\cdot\bm{v}_{j+1}}-\frac{\bm{v}_{j}}{\omega-\bm{k}\cdot\bm{v}_{j}}\bigg{)},$
(5)

interfering with a phase $\varphi_{j}\equiv\omega
t_{j}-\bm{k}\cdot\bm{x}_{j}$. The evaluation of the square of (4) leads to a
total emission intensity between the photon solid angle $\Omega_{k}$ and
$\Omega_{k}+d\Omega_{k}$ given by

$\displaystyle\omega\frac{dI}{d\omega
d\Omega_{k}}=\frac{e^{2}}{(2\pi)^{2}}\left(\sum_{j=1}^{n_{c}}\bm{\delta}_{j}^{2}+2\operatorname{Re}\sum_{j=1}^{n_{c}}\sum_{i=1}^{j-1}\bm{\delta}_{j}\cdot\bm{\delta}_{i}e^{i\varphi_{i}^{j}}\right),$
(6)

where we have split the sum in a diagonal and a non-diagonal contribution. The
interfering behavior of the above sum is governed by the phase change between
two arbitrary collisions or emission elements

$\displaystyle\varphi_{i}^{j}$
$\displaystyle\equiv\varphi_{j}-\varphi_{i}=k_{\mu}(x_{j}^{\mu}-x_{i}^{\mu})=\int^{z_{j}}_{z_{i}}dz\frac{k_{\mu}p^{\mu}(z)}{p_{0}}$
$\displaystyle=\omega(1-\beta)\int_{z_{i}}^{z_{j}}dz+\omega\int_{z_{i}}^{z_{j}}dz\medspace\frac{\delta\bm{p}^{2}(z)}{2\beta
p_{0}^{2}},$ (7)

where $p_{0}$ is the initial electron energy, $\delta\bm{p}(z)$ is the
accumulated momentum change of the electron at $z$ with respect to the photon
direction and $\beta=|\bm{v}|=\sqrt{1-m_{e}^{2}/p_{0}^{2}}$ the electron
velocity. This phase can be made maximal for large emission angles and/or
photon frequencies, provided that $\varphi_{i}^{i+1}\gg 1$ for any two
consecutive collisions. In that case the non-diagonal sum in (6) cancels and
we are left with a totally incoherent superposition of $(n_{c})$ single Bethe-
Heitler intensities, with a maximal intensity of

$\displaystyle\omega\frac{dI_{sup}}{d\omega
d\Omega_{k}}=\frac{e^{2}}{(2\pi)^{2}}\sum_{j=1}^{n_{c}}\bm{\delta}_{j}^{2}.$
(8)

In this regime emission decouples and all the scatterings can be considered to
be independently emitting. In the opposite case, when the emission angle
and/or photon energy are small so that the phase vanishes, the internal
structure of the scattering is irrelevant. This observation becomes manifest
by setting $\varphi_{j}=0$ in (4), so we are left with the first and last
terms only and intensity acquires the minimum value

$\displaystyle\omega\frac{dI_{inf}}{d\omega
d\Omega_{k}}=\frac{e^{2}}{(2\pi)^{2}}\left|\sum_{j=1}^{n_{c}}\bm{\delta}_{j}\right|^{2},$
(9)

which can be interpreted as a Bethe-Heitler intensity with a final velocity
$\bm{v}_{n_{c}+1}$ due to the coherent deflection with all the medium centers.
In this regime the entire medium acts as a single independent emission
element. This behavior is a consequence of the well known soft photon theorem
Weinberg1965 ; Weinberg , although in the LPM literature it is known as the
Ternovskii-Shul’ga-Fomin emission Ternovskii1 ; ShulgaFomin . The suppression
from the superior (incoherent) plateau of radiation (8) to the inferior
(coherent) plateau (9) is known as the LPM effect for mediums of arbitrary
size. Notice that in the infinite medium limit ($n_{c}\gg 1$) the coherent
plateau can be neglected, since the soft photon theorem is not observed and
then the suppression is infinite.

Figure 1: Diagrammatic representation of the single emission elements
appearing in a discretization in the variable $z$, of the amplitude
$\mathcal{M}_{em}^{(n)}$ given at Equation (10).

The above classical arguments can be made quantitative and hold also for a
quantum evaluation of the amplitude. By Fourier transforming electron states
$\Psi_{i,f}(x)$ to the momentum space, we can write for the quantum amplitude
(1)

$\displaystyle\mathcal{M}_{em}^{(n)}=e\mathcal{N}(k)\int\frac{d^{3}\bm{p}(z)}{(2\pi)^{3}}\int^{l}_{0}dz\exp\left(i\frac{k_{\mu}p^{\mu}(z)}{p_{0}}\right)\frac{d}{dz}\times$
$\displaystyle\left\\{S_{s_{n}s}^{el}(p(l),p(z);l,z)\frac{f_{ss^{\prime}}^{\lambda}(z)}{k_{\mu}p^{\mu}(z)}S_{s^{\prime}s_{0}}^{el}(p(z)+k,p(0);z,0)\right\\},$
(10)

where we used the shorthand notation

$\displaystyle
f_{ss^{\prime}}^{\lambda}(z)\equiv\epsilon_{\mu}^{\lambda}(k)p_{0}\sqrt{\frac{m_{e}}{p_{0}-\omega}}\bar{u}_{s}(p)\gamma^{\mu}u_{s^{\prime}}(p+k)\sqrt{\frac{m_{e}}{p_{0}}}.$
(11)

Here $S_{s_{2}s_{1}}^{el}(p_{2},p_{1};l_{2},l_{1})$ stands for the beyond
eikonal evaluation of the elastic amplitudes for an electron to go from
momentum $p_{1}$ to $p_{2}$ and from spin $s_{1}$ to $s_{2}$ due the amount of
matter between $l_{1}$ and $l_{2}$, thus given by

$\displaystyle
S_{s_{n}s_{0}}^{(n)}(p_{n},p_{0};z_{n},z_{1})=2\pi\delta(p_{n}^{0}-p_{0}^{0})\delta_{s_{0}}^{s_{n}}\beta\left(\prod_{i=i}^{n-1}\int\frac{d^{2}\bm{p}^{t}_{i}}{(2\pi)^{2}}\right)$
$\displaystyle\times\left(\prod_{i=1}^{n}\int
d^{2}\bm{x}^{t}_{i}e^{-i\bm{q}_{i}\cdot\bm{x}_{i}}\exp\left[-i\frac{g}{\beta}\sum_{j=1}^{n(z_{i})}\chi_{0}^{(1)}(\bm{x}-\bm{r}_{j})\right]\right),$
(12)

where we discretized the medium and thus
$\bm{q}_{i}\equiv\bm{p}_{i}-\bm{p}_{i-1}$ is the 3-momentum transfer at the
layer $(i)$ of $n(z_{i})$ scattering centers. The external field
characterizing the medium is given by $(n)$ single Debye static sources with
screening $\mu_{d}\simeq\alpha m_{e}Z^{1/3}$, coupled with strength
$g=Z\alpha$ to the electron, of the form

$\displaystyle\chi_{0}^{(1)}(\bm{x})\equiv\int_{-\infty}^{+\infty}ds\medspace
A_{0}^{(1)}(\bm{x}),\medspace
A_{0}^{(1)}(\bm{x})=\frac{Z\alpha}{|\bm{x}|}e^{-\mu_{d}|\bm{x}|}.$ (13)

The amplitude (10), which corresponds to a sum of the single emission elements
shown in Fig.(1), can be squared and averaged over medium configurations of
infinite transverse size $R\to\infty$ in a finite length $l$, summed over
final states, and averaged over initial states, leading to an intensity of
emission in the photon solid angle $\Omega_{k}$ and $\Omega_{k}+d\Omega_{k}$
and per unit of medium transverse size and unit time of

$\displaystyle\omega$ $\displaystyle\frac{dI}{d\omega
d\Omega_{k}}=\left(\frac{e}{2\pi}\right)^{2}\left(\prod_{k=1}^{n}\int\frac{d^{3}\bm{p}_{j}}{(2\pi)^{3}}\right)\left(\prod_{k=1}^{n}\phi(\delta\bm{p}_{k},\delta
z)\right)$
$\displaystyle\times\left(h^{n}(y)\left|\sum_{j=1}^{n}\bm{\delta}_{j}^{n}e^{i\varphi_{0}^{j}}\right|^{2}+h^{s}(y)\left|\sum_{j=1}^{n}\delta_{j}^{s}e^{i\varphi_{0}^{j}}\right|^{2}\right),$
(14)

where the spin non-flip currents $\bm{\delta}_{j}^{n}$ are given by (5) and
the spin flip currents are given by

$\displaystyle\delta_{j}^{s}\equiv\frac{1}{1-\beta_{k}\hat{\bm{k}}\cdot\bm{v}_{j+1}}-\frac{1}{1-\beta_{k}\hat{\bm{k}}\cdot\bm{v}_{j}}.$
(15)

Here we have introduced explicitely a medium with a refractive index
$1/\beta_{k}$ and $\beta_{k}$ is the photon velocity. The functions $h^{n}(y)$
and $h^{s}(y)$ are the diagonal and non-diagonal sum in spins and helicities
of the squared emission vertex (11), given by

$\displaystyle h^{n}(y)=\frac{1}{2}(1+(1-y)^{2}),\medspace
h^{s}(y)=\frac{1}{2}y^{2},$ (16)

and $y=\omega/p_{0}$ is the fraction of energy carried by the photon. They
produce two contributions of the same order, the last one, however, only
noticeable when $y\approx 1$ due to $h^{s}(y)$. In what follows we will
neglect this contribution by assuming that $y\ll 1$. Within the same
approximation we will assume also that the electron 4-momentum change in the
emission vertex is negligible and $\beta=1$ unless otherwise required. The
local elastic weights arising in the averaging of the square of (12) are given
by

$\displaystyle\phi(\delta\bm{p},\delta z)$
$\displaystyle=\exp\bigg{(}-n_{0}(z)\delta
z\sigma_{t}^{(1)}\bigg{)}(2\pi)^{3}\delta^{3}(\delta\bm{p})$
$\displaystyle+2\pi\delta(\delta p_{0})\beta\Sigma_{2}(\delta\bm{p},\delta
z),$ (17)

where we can define the no collision probability $\exp(-n(z)\delta
z\sigma_{t}^{(1)})$ in the layer of length $\delta z$ and density $n_{0}(z)$
times the forward distribution $\delta^{3}(\delta\bm{p})$, and the collisional
distribution $\Sigma_{2}(\bm{q},\delta z)$ after an incoherent scattering with
the centers in $\delta z$

$\displaystyle\Sigma_{2}(\bm{q},\delta z)$ $\displaystyle\equiv\int
d^{2}\bm{x}e^{-i\bm{q}\cdot\bm{x}}\exp\bigg{(}-n_{0}(z)\delta
z\sigma_{t}^{(1)}\bigg{)}$ (18)
$\displaystyle\times\bigg{(}\exp\bigg{(}n_{0}(z)\delta
z\sigma(\bm{x})\bigg{)}-1\bigg{)},$

which satisfies a Moliere’s equation with boundary condition
$\Sigma_{2}(\bm{q},0)=0$. The required single elastic cross sections at (17)
and (18) can be shown to satisfy $\sigma_{t}^{(1)}\equiv\sigma(\bm{0})$ where,
at leading order in $Z\alpha$ using (13)

$\displaystyle\sigma(\bm{x})\equiv\frac{4\pi(Z\alpha)^{2}}{\beta^{2}\mu_{d}^{2}}\mu_{d}|\bm{x}|K_{1}(\mu_{d}|\bm{x}|)+\mathcal{O}(Z\alpha)^{3}.$
(19)

Figure 2: Schematic representation of the bremsstrahlung regimes for several
scenarios. Totally incoherent Bethe-Heitler superposition (BH), Landau-
Pomeranchuk-Migdal suppression (LPM), totally coherent Bethe-Heitler
superposition ($m_{\gamma}$=0), dielectric suppression (DE) and transition
radiation (TR). See text for definition of the characteristics frequencies
$\omega_{c},\omega_{s},\omega_{de}$

We assume from here onwards a constant density $n_{0}(z)\equiv n_{0}$ so from
(17) the electron mean free path is read $\lambda\equiv
1/n_{0}\sigma_{t}^{(1)}$. In this elastic propagation the electron acquires a
squared momentum transfer additive with the traveled length $l$. Indeed, from
(17) we find

$\displaystyle\frac{\partial}{\partial
l}\left\langle\delta\bm{p}^{2}(l)\right\rangle=n_{0}\sigma_{t}^{(1)}\left\langle\delta\bm{p}^{2}(\delta
l)\right\rangle\equiv 2\hat{q},$ (20)

where we defined the transport parameter $\hat{q}$. The momentum transfer in a
single collision $\delta l\lesssim\lambda$ is given, using (17), by

$\displaystyle\left\langle\delta\bm{p}^{2}(\delta
l)\right\rangle=\mu_{d}^{2}\left(2\log\left(\frac{2p_{0}}{\mu_{d}}\right)-1\right)=\mu_{d}^{2}\eta,$
(21)

where the correction $\eta$ to $\mu_{d}^{2}$ takes into account the long tail
of the Debye interaction (13) and a maximum momentum transfer of
$|\delta\bm{p}|=2p_{0}$ is allowed in a single collision. High momentum
changes are suppressed at high energies, however, due to the functions (5) and
(15) in (14). We have checked that a maximum momentum transfer of
$|\delta\bm{p}|\simeq 2.5m_{e}$ matches the single emission and then we write
for $\eta$ in (21) instead

$\displaystyle\eta=\left(2\log\left(\frac{2.5m_{e}}{\mu_{d}}\right)-1\right)=\left(2\log\left(\frac{2.5}{\alpha
Z^{1/3}}\right)-1\right).$ (22)

This effective momentum transfer under bremsstrahlung agrees with Bethe’s
Bethe1934  estimation $\eta=2\log(183/Z^{1/3})$ within less than $3\%$
deviation in the range $Z=(1,100)$. Using (20), (21) and (22) then
$\hat{q}=(\eta/2)\times n_{0}\sigma_{t}^{(1)}\mu_{d}^{2}$ and the Fokker-
Planck approximation for (18) reads

$\displaystyle\Sigma_{2}^{G}(\bm{q},\delta z)\equiv\frac{2\pi}{\hat{q}\delta
z}\exp\left(-\frac{\bm{q}^{2}}{2\hat{q}\delta z}\right).$ (23)

The above relations hold, however, for the single scattering regime $\delta
z\leq\delta l$, so they can be used only to fix $\eta$ and thus $\hat{q}$ in
the incoherent plateau. For the coherent plateau a medium-length dependent fit
for $\eta$ has to be employed. Correspondingly, a single Fokker-Planck
approximation can not fit both the upper and lower ends of the bremsstrahlung
spectrum unless the medium length is very large, in which case the lower
plateau occurs at very low frequencies and can be neglected.

Before evaluating the expression (14), we will derive an heuristic formula for
finite size targets to qualitatively understand the interference phenomena.
The coherence length defined by the phase modulates the amount of scatterers
which can be considered a single and independent unit of emission in the
squared amplitude. We then define the length $\delta l=z_{j}-z_{i}$ in which
the phase becomes larger than unity, which using (7) becomes

$\displaystyle\varphi^{j}_{i}\simeq\frac{\omega}{2p_{0}^{2}}\left(m_{e}^{2}\delta
l+\hat{q}(\delta l)^{2}\right)\equiv 1,$ (24)

then we get

$\displaystyle\delta
l(\omega)\equiv\frac{m_{e}^{2}}{2\hat{q}}\left(\sqrt{1+\frac{8\hat{q}p_{0}^{2}}{m_{e}^{4}\omega}}-1\right).$
(25)

We also define the frequency $\omega_{c}$ at which the coherence length
becomes equal to $l$ thus $\omega_{c}\simeq
p_{0}^{2}/(m_{e}^{2}l+\hat{q}l^{2})$, and the frequency $\omega_{s}$ in which
the coherence length becomes equal to a mean free path $\lambda$,
$\omega_{s}\simeq p_{0}^{2}/(m_{e}^{2}\lambda+\hat{q}l\lambda/2)$. Since the
medium is finite we further impose to (25) $\delta l(\omega)=l$ for
$\omega>\omega_{c}$. In the coherence length $\delta l(\omega)$ the internal
scattering structure is irrelevant since the phase can be neglected, and the
centers in $\delta l(\omega)$ act coherently like a single scattering source
with the total equivalent charge in $\delta l(\omega)$. Since in the entire
medium $l$ there are $l/\delta l(\omega)$ coherence lengths, then we write the
incoherent sum

$\displaystyle\omega\frac{dI}{d\omega}(l)$ $\displaystyle=\frac{l}{\delta
l(\omega)}e^{2}\int\frac{d\Omega_{k}}{(2\pi)^{2}}\int\frac{d^{3}\delta\bm{p}}{(2\pi)^{3}}$
$\displaystyle\times\left(h^{n}(y)|\bm{\delta}_{1}^{n}|^{2}+h^{s}(y)|\delta_{1}^{s}|^{2}\right)\phi(\delta\bm{p},\delta
l(\omega)).$ (26)

By integrating in the photon solid angle $\Omega_{k}$ and using (17) we find

$\displaystyle\omega\frac{dI(l)}{d\omega}=\frac{l}{\delta
l(\omega)}\frac{e^{2}}{\pi^{2}}\int_{0}^{\pi}d\theta\sin(\theta)F(\theta)\Sigma_{2}(\delta\bm{p},\delta
l(\omega)),$ (27)

where the electron momentum change is
$|\delta\bm{p}|=2p_{0}\beta\sin(\theta/2)$ and

$\displaystyle F(\theta)=\bigg{[}$
$\displaystyle\frac{1-\beta^{2}\cos\theta}{2\beta\sin(\theta/2)\sqrt{1-\beta^{2}\cos^{2}(\theta/2)}}$
(28)
$\displaystyle\log\bigg{[}\frac{\sqrt{1-\beta^{2}\cos^{2}(\theta/2)}+\beta\sin(\theta/2)}{\sqrt{1-\beta^{2}\cos^{2}(\theta/2)}-\beta\sin(\theta/2)}\bigg{]}-1\bigg{]}.$

This last integral (27) can be numerically evaluated and the resulting
intensity is exact for $\omega\gg\omega_{s}$ and $\omega\ll\omega_{c}$. A
simple interpolation formula in the Fokker-Planck approximation can be
obtained from (27) by integrating its two asymptotic values, i.e. $\delta
l(\omega)\gg 1$ and $\delta l(\omega)\ll 1$, and then interpolating both
regions. One finds

Figure 3: Differential spectrum of photons emitted by an electron of $p_{0}=8$
GeV traversing a sheet of gold of $l=0.023$ mm for photon angles
$\theta_{k}=0.01/\gamma$ (a), $\theta_{k}=2/\gamma$ (b) and
$\theta_{k}=10/\gamma$ (c), where $\gamma\equiv p_{0}/m_{e}$, in the Monte
Carlo (MC) evaluations of (14) in the Debye interaction (yellow), in the
Fokker-Planck approximation with $\eta=8$ (purple), $\eta=4$ (dark grey) and
$\eta=2$ (light grey), together with the corresponding path integral (PI)
limits of (14) in the Fokker-Planck approximation (dot-dashed lines). Bands
show the statistical uncertainty of the Monte Carlo.

$\displaystyle\omega\frac{dI(l)}{d\omega}=\frac{l}{\delta
l(\omega)}\frac{2e^{2}}{\pi}\frac{1+n_{m}(\omega)}{3A+n_{m}(\omega)}\log\bigg{(}1+An_{m}(\omega)\bigg{)},$
(29)

where $n_{m}(\omega)\simeq 2\hat{q}\delta l(\omega)/m_{e}^{2}$ is a measure of
the accumulated transverse momentum in a coherence length and
$A=e^{-(1+\gamma)}$ with $\gamma$ Euler’s constant. For completeness we also
write Migdal $y\ll 1$ prediction Migdal1956  for semi-infinite mediums

$\displaystyle\omega$
$\displaystyle\frac{dI(l)}{d\omega}=l\frac{2e^{2}}{\pi}\sqrt{\frac{\hat{q}\omega}{2p_{0}^{2}}}\int_{0}^{\infty}dz\medspace\exp\left(-\frac{z}{\sqrt{2}s}\right)$
(30)
$\displaystyle\times\left(\sin\left(\frac{z}{\sqrt{2}s}\right)+\cos\left(\frac{z}{\sqrt{2}s}\right)\right)\left(\frac{1}{z^{2}}-\frac{1}{\sinh^{2}(z)}\right),$

where $s\equiv(2p_{0}/m_{e}^{2})\sqrt{\hat{q}/\omega}$ and an useful
approximant within less than a $1\%$ of deviation is given by

$\displaystyle\omega\frac{dI(l)}{d\omega}=\frac{2e^{2}}{3\pi}\frac{2\hat{q}l}{m_{e}^{2}}\frac{1-1.52s^{4}+5.8s^{5}}{1+2.44s^{5}+2.73s^{6}}.$
(31)

Migdal result (30) is exactly recovered within our formalism as a restriction
in the domain of integration in $z$ of the emission amplitude (1) squared, as
follows

$\displaystyle\left|\mathcal{M}_{em}^{(n)}\right|^{2}=e^{2}$
$\displaystyle\int_{-\infty}^{+\infty}dz\int_{-\infty}^{+\infty}dz^{\prime}$
(32) $\displaystyle\to e^{2}$
$\displaystyle\left\\{\int^{+\infty}_{0}dz\int^{+\infty}_{0}dz^{\prime}+\int^{0}_{-\infty}dz\int^{0}_{-\infty}dz^{\prime}\right\\}.$

The general behavior of these results can be summarized in Fig.(2) where the
photon intensity is pictured as a function of the photon frequency. Above the
saturation frequency $\omega_{s}$ the photon resolves all the internal
structure of the scattering, the medium emits as a total incoherent sum of
$n_{c}=l/\lambda$ Bethe-Heitler intensities, where $n_{c}$ is the average
number of collisions. In this regime, the photon intensity scales with $l$.
Notice that total suppression can occur provided $\omega_{s}$ becomes larger
than $p_{0}$, which causes that electrons with energies below
$p_{0}^{lpm}=m^{2}_{e}/n_{0}\sigma_{t}^{(1)}$ experiment the bremsstrahlung
suppression in all their spectrum. For smaller frequencies the number of
independent emitters, using (25), decreases with $\sqrt{\omega}$ whereas the
charge of each element logarithmically grows with $\log(1/\sqrt{\omega})$.
This suppression stops at $\omega_{c}$, where the coherence length (25)
acquires the maximum value $l$, the medium emits as a single entity and
intensity saturates to Weinberg’s soft photon theorem Weinberg1965 .

Figure 4: Intensity of photons emitted by an electron of $p_{0}=8$ GeV (top)
and $p_{0}=25$ GeV (bottom) after traversing a sheet of gold of length
$l=0.0038$ mm in the Monte Carlo (MC) evaluation of (14) in the Debye
interaction (squares), the Fokker-Planck approximation with $\eta=8$
(circles), $\eta=4$ (diamonds) and $\eta=2$ (triangles). Also shown our
heuristic formula (27) and the Migdal prediction (31).

The presence of a medium modifies the photon dispersion relation and
substantially changes this picture in the soft limit. For the energies
considered here the photon has velocity given by

$\displaystyle\beta^{2}(k)=1-\frac{\omega_{p}^{2}}{\omega^{2}},$ (33)

where $\omega_{p}^{2}\simeq 4\pi Z\alpha n_{0}/m_{e}\equiv m_{\gamma}^{2}$ is
the plasma frequency, which can be interpreted as a photon mass $m_{\gamma}$.
This scenario induces an additional source of suppression due to the fact that
the wavelength of a photon of frequency $\omega$ is now larger than in the
vacuum case and thus

$\displaystyle k_{\mu}p^{\mu}(\omega_{p})\simeq
k_{\mu}p^{\mu}(0)+\frac{m_{\gamma}^{2}}{2\omega}.$ (34)

This extra term further suppresses the coherent plateau at
$\omega<\omega_{de}$, where $k_{\mu}p^{\mu}(0)\equiv
m_{\gamma}^{2}/2\omega_{de}$, i.e.
$\omega^{2}_{de}=\omega_{p}^{2}l\omega_{c}$, since the denominators of (5) and
(15), defined by (34), grow for smaller frequencies. This suppression is
called the dielectric effect and holds for a totally homogeneous space or
infinite medium. However, if the electron passes through vacuum to a medium
and then again to vacuum, or in general through structured targets where
density cannot be considered constant, then the definition (34) becomes local
for each photon emission point. The photon emitted at the last leg then
satisfies $m_{\gamma}=0$, whereas the first leg photon satisfies
$m_{\gamma}\neq 0$, thus it can be shown that an interference destroys the
dielectric suppression in the coherence plateau, dramatically enhancing the
intensity for $\omega<\omega_{de}$. This is called transition radiation
Jackson ; Ginzburg1945 . Both of these effects have been implemented in our
formalism and Monte Carlo. In Fig. (2) we show qualitatively the dielectric
effect and the transition radiation together with their characteristic
frequency $\omega_{de}$.

##  III Results

Expression (14) can be numerically evaluated for arbitrary interaction models,
for finite size and arbitrarily structured targets with dielectric suppression
and transition radiation effects included. We have developed a Monte Carlo
code to evaluate this intensity by means of discretized paths with a typical
step of $\delta z=0.1\lambda$. In a typical run we computed $10^{4}$ paths for
50 frequencies and 100 photon angles, spanning from $\sim$ $10^{3}$ steps for
the shortest medium to $\sim$ $10^{5}$ steps for the largest. In order to
check that our results are correct we implemented also the Fokker-Planck
approximation (23) for (17) in this discretized approach and compared with the
$\delta z\to 0$ limit of (14), which within this approximation produces six
integrable Gaussian path integrals extending the Boltzmann transport approach
Migdal1956  to finite mediums.

Figure 5: Intensity of photons emitted by an electron of $p_{0}=8$ GeV (top)
and $p_{0}=25$ GeV (bottom) after traversing a sheet of gold of length $l=0.2$
mm in the Monte Carlo (MC) evaluation of (14) in the Debye interaction
(squares), the Fokker-Planck approximation with $\eta=8$ (circles), $\eta=4$
(diamonds) and $\eta=2$ (triangles). Also shown our formula (27) and the
Migdal prediction (31).

We present our result for the Debye and Fokker-Planck cases for targets of
lengths $l=$ 0.0038, 0.023 and 0.2 mm, corresponding to an average of $n_{c}=$
142, 862 and 7502 collisions, respectively, for electrons of $p_{0}=$ 8 and 25
GeV, in order to compare to the SLAC data presented in Anthony3 ; Anthony1 ;
Anthony2 . A systematic study and comparison with other experimental results
will be presented elsewhere FealVazquez_prep . For gold we obtain an estimate
for the Debye mass of $\mu_{d}=16$ keV, a transport parameter of
$\hat{q}=(\eta/2)\times 1.89$ keV3, an effective momentum transfer of $\eta=8$
Debye masses in a single collision and a plasma frequency of
$\omega_{p}=0.080$ keV (see also Tsai ). In Fig.(3) we show the differential
photon intensity as a function of the photon energy for various fixed emission
angles for an electron of $p_{0}=8$ GeV traversing a gold sheet of $l=0.023$
mm. The path integral limit is also shown, and an excellent agreement with the
Fokker-Planck Monte Carlo evaluation is found. At low angles, the Fokker-
Planck approximation overestimates the intensity by $\sim 20\%$. However, at
larger angles the Fokker-Planck approximation underestimates the intensity, in
particular only half of the real emission is obtained for
$\theta=10\gamma^{-1}$.

Figure 6: Intensity of photons emitted by an electron of $p_{0}=8$ GeV (top)
and $p_{0}=25$ GeV (bottom) after traversing a sheet of gold of length
$l=0.023$ mm in the Debye interaction (open squares) and the Fokker-Planck
approximation with $\eta=8$ (circles) with the dielectric and transition
radiation effect included, compared to SLAC experimental data Anthony3  (solid
circles) rescaled.

In Fig.(4) we show the angular integrated spectrum for a sheet of gold of
$l=0.0038$ mm for electron energies of $p_{0}=8$ and 25 GeV. We see that a fix
of $\eta=8$ Debye masses of momentum transfer at each collision in the Fokker-
Planck approximation matches the incoherent plateau but mismatches the
coherent plateau. Also shown are the expression (27) and the Migdal prediction
(31) both in the Fokker-Planck approximation. The predicted characteristic
frequencies are $\omega_{c}=8$ MeV and $\omega_{s}=1.1$ GeV for $p_{0}=8$ GeV,
and $\omega_{c}=$ 80 MeV and $\omega_{s}=$ 11 GeV for $p_{0}=$ 25 GeV, being
in good agreement with the obtained Monte Carlo results.

In Fig.(5) we show the same results for a sheet of gold of $l=0.2$ mm. We see
that Migdal prediction becomes a good approximation for $n_{c}\geq 10^{4}$,
i.e. when the coherent plateau can be neglected. For this length we predicted
$\omega_{c}=8$ keV and $\omega_{s}=60$ MeV for $p_{0}=8$ GeV, and
$\omega_{c}=80$ keV and $\omega_{s}=588$ MeV for $p_{0}=25$ GeV. All these
values are in well agreement with the Monte Carlo evaluation.

In Fig.(6) we show the dielectric and transition radiation effect
implementation both in the Debye interaction and the Fokker-Planck
approximation, and compare with SLAC data Anthony3 , for a sheet of gold of
$l=0.023$ mm and electron energies of $p_{0}=8$ and 25 GeV. The characteristic
frequency predictions $\omega_{de}=0.6$ MeV for $p_{0}=8$ GeV and
$\omega_{de}=1.9$ MeV for $p_{0}=25$ GeV and the comparison with experimental
data are in very good agreement. The LPM characteristic frequencies are given
in this case by $\omega_{c}=0.48$ MeV and $\omega_{s}=418$ MeV for $p_{0}=8$
GeV, and $\omega_{c}=4.7$ MeV and $\omega_{s}=4$ GeV for $p_{0}=25$ GeV.

Figure 7: Intensity of photons emitted by an electron of $p_{0}=8$ GeV after
traversing a sheet of gold of length $l=0.023$ mm from electrons with final
transverse momentum $\bm{p}_{t}>4$ MeV in the Debye interaction (triangles)
and the Fokker-Planck approximation with $\eta=8$ (diamonds), and with
$\bm{p}_{t}<4$ MeV in the Debye interaction (squares) and the Fokker-Planck
approximation with $\eta=8$ (circles).

In Fig.(7) we show the intensity of bremsstrahlung for electron with a final
transverse momentum $|\delta\bm{p}|<4$ MeV or $|\delta\bm{p}|>4$ MeV. We see
that the Fokker-Planck results do not reproduce well the Debye calculation.
Although large differences could be expected for the case of
$|\delta\bm{p}|>4$ MeV, as the Fokker-Planck approximation underestimate the
long tails of the tranverse momentum distribution, it is perhaps more
surprising to find that also cutting at low $p_{t}$ produces different
results: the Fokker-Planck result overestimates the emission in this case at
large frequencies.

##  IV Conclusions

A formalism implemented with a Monte Carlo method has been presented which is
able to evaluate the bremsstrahlung intensity in a multiple scattering
scenario under a general interaction. We have also found an heuristic formula
which describes the LPM effect for finite size targets. Dielectric and
transition radiation effects related to effective photon masses in the medium
dispersion relation are included in this formalism if needed. Our results
reproduce the experimental data of SLAC.

We have shown that the Fokker-Planck approximation does not fit well the
differential angular spectrum, especially if kinematical cuts are applied in
the final particles. In the integrated spectrum, the Fokker-Planck
approximation fails to reproduce the spectrum. If the $\hat{q}$ is fixed using
the incoherent plateau, then the coherent plateau is not well reproduced,
unless a length dependent definition of the transport properties of the medium
is used.

###### Acknowledgements.

We thank J. Alvarez-Muñiz, N. Armesto, C. Salgado, and J. Sanchez-Guillen for
reading the manuscript and for discussions. We thank the grant María de Maeztu
Unit of Excelence of Spain and the support of Xunta de Galicia under the
project ED431C2017. This paper has been partially done under the project
FPA2017-83814-P of MCTU (Spain).

## References

  * (1) M.L. Ter-Mikaelian, The interference emission of high-energy electrons, Zh. Eksp. Teor. Fiz. 25, 296 (1953).
  * (2) L. Landau and I. Pomeranchuk, The limits of applicability of the theory of bremsstrahlung by electrons and of the creation of pairs at large energies, Dokl.Akad.Nauk Ser.Fiz. 92, 535 (1953).
  * (3) L. Landau, Electron-cascade processes at ultra-high energies, Dokl. Akad. Nauk Ser. Fiz. 92, 735 (1953).
  * (4) A.B. Migdal, Bremsstrahlung and Pair Production in Condensed Media at High Energies, Phys. Rev. 103, 1811 (1956).
  * (5) R. Blankenbecler and S.D. Drell, Quantum treatment of beamstrahlung, Phys. Rev. D 36, 277 (1987).
  * (6) R. Blankenbecler, Multiple scattering and functional integrals, Phys. Rev. D 55, 2441 (1997).
  * (7) R. Blankenbecler, Structured targets and the Landau Pomeranchuk Migdal effect, Phys. Rev. D 55, 190 (1997).
  * (8) B.G. Zakharov, Landau Pomeranchuk Migdal effect for finite size targets, Zh. Eksp. Teor. Fiz. 64, 737 (1996).
  * (9) B.G. Zakharov, Fully quantum treatment of the Landau-Pomeranchuk-Migdal effect in QED and QCD, JETP Lett. 63, 952 (1996).
  * (10) B.G. Zakharov, Light cone path integral approach to the Landau Pomeranchuk Migdal effect, Yad. Fiz. 61, 924 (1998).
  * (11) B.G. Zakharov, Radiative energy loss of high energy quarks in finite size nuclear matter and quark gluon plasma, JETP Lett. 65, 615 (1997).
  * (12) B.G. Zakharov, Light cone path integral approach to the LPM effect and the SLAC data on bremsstrahlung from high energy electrons, Yad. Fiz. 62, 1075 (1999).
  * (13) B.G. Zakharov, Fully quantum treatment of the Landau Pomeranchuk Migdal effect in QED and QCD, JETP Lett. 63, 952 (1996).
  * (14) B.G. Zakharov, Transverse spectra of induced radiation, JETP Lett. 70, 176 (1999).
  * (15) R. Baier, Yu.L. Dokshitzer, A.H. Mueller, S. Peigné and D. Schiff The Landau-Pomeranchuk-Migdal effect in QED, Nucl. Phys. B 478, 577 (1996).
  * (16) V.N. Baier and V.M. Katkov, The theory of the Landau Pomeranchuk Migdal effect, Phys. Rev. D 57 (1998) 3146.
  * (17) V.N. Baier and V.M. Katkov, Variation of radiation length due to LPM effect, Phys. Lett. A327, 202 (2004).
  * (18) V.N. Baier and V.M. Katkov, Coherent scattering of high energy photon in a medium, Phys. Rev. D 63, 116008 (2001).
  * (19) U.A. Wiedemann and M. Gyulassy, Transverse momentum dependence of the Landau Pomeranchuk Migdal effect, Nucl. Phys. B560, 345 (1999).
  * (20) S. Klein, Suppression of bremsstrahlung and pair production due to environmental factors, Rev. Mod. Phys. 71, 1501 (1999).
  * (21) V.N. Baier and V.M. Katkov, Concept of formation length in radiation theory, Phys. Rep. 409, 261 (2005).
  * (22) P.L. Anthony et al., Bremsstrahlung suppression due to the Landau Pomeranchuk Migdal and dielectric effects in a variety of materials, Phys. Rev. D 56, 1373 (1997).
  * (23) H. Bethe and W. Heitler, On the Stopping of Fast Particles and on the Creation of Positive Electrons, Proc. Roy. Soc. Lond. A146, 83 (1934).
  * (24) S. Weinberg, Infrared Photons and Gravitons, Phys. Rev. 140, B516 (1965).
  * (25) F. Bloch and A. Nordsieck, Note on the Radiation Field of the Electron, Phys. Rev. 52, 54 (1937)
  * (26) J.D. Jackson, Classical electrodynamics, Wiley, New York, (1998) 3rd ed.
  * (27) J.S. Bell, Bremsstrahlung from multiple scattering, Nucl. Phys. 8, 613 (1958).
  * (28) S. Weinberg, The quantum theory of fields. Vol. 1: Foundations, Cambridge University Press.
  * (29) F.F. Ternovskii, On the theory of radiative processes in piecewise homogeneous media, Sov. Phys. JETP 12, 123 (1961)
  * (30) N.F. Shul’ga and S.P. Fomin, Effect of multiple scattering on the emission of ultrarelativistic electrons in a thin layer of matter, JETP Lett. 86, 32 (1998).
  * (31) V.L. Ginzburg and I.M. Frank, Radiation of a uniformly moving electron due to its transition from one medium into another, Zh. Eksp. Teor. Fiz. 16, 15 (1946).
  * (32) P.L. Anthony et al., Measurement of dielectric suppression of bremsstrahlung, Phys. Rev. Lett. 76, 3550 (1996).
  * (33) P.L. Anthony et al., An accurate measurement of the landau-Pomeranchuk Migdal effect, Phys. Rev. Lett. 75, 1949 (1995).
  * (34) X. Feal and R.A. Vazquez, in preparation.
  * (35) Y. Tsai, Pair production and bremsstrahlung of charged leptons, Rev. Mod. Phys. 46, 815 (1974).


Let $\Gamma$ be a context, and let $u$, $u^{\prime}$, $v$, $t$ and $\alpha$ be
terms We have these congruence relations:

If $\Gamma;v::s\vdash u\leq u^{\prime}$, then $\Gamma;\mathrm{nil}\vdash
u\,v\leq u^{\prime}\,v$.

If $\Gamma,x\leq t;s\vdash u\leq u^{\prime}$ then $\Gamma;s\vdash\lambda x\leq
t.u\leq\lambda x\leq t.u^{\prime}$.

If $\Gamma,x\leq\alpha;s\vdash u\leq u^{\prime}$ then
$\Gamma;\alpha::s\vdash\lambda x\leq t.u\leq\lambda x\leq t.u^{\prime}$.

###### Proof.

We do the first case. Every other case is similar: it lifts B.14.

Suppose we have $\Gamma;v::\mathrm{nil}\vdash u\leq u^{\prime}$. By Lemma 2.4,
we have a term $t$ such that
$u\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t$ and $\Gamma;v::s\vdash
u^{\prime}\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t$.

By reflexitivity of
$v\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}v$, we have
$u\,v\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t\,v$. By Lemma B.14, we have $\Gamma;\mathrm{nil}\vdash
u^{\prime}\,v\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t\,v$ from $\Gamma;v::s\vdash
u^{\prime}\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t$.

We then conclude by Lemma 2.4 with the intermediate term $t\,v$. ∎

###### Lemma B.14 (Congruence of
$\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}$).

Let $\Gamma$ be a context, and let $u$, $u^{\prime}$, $v$ and $t$ be terms We
have these congruence relations:

If $\Gamma;v::s\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}u^{\prime}$, then $\Gamma;s\vdash
u\,v\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}u^{\prime}\,v$.

If $\Gamma,x\leq t;\mathrm{nil}\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}u^{\prime}$ then $\Gamma;\mathrm{nil}\vdash\lambda x\leq
t.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\lambda x\leq
t.u^{\prime}$.

If $\Gamma,x\leq\alpha;s\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}u^{\prime}$ then $\Gamma;\alpha::s\vdash\lambda x\leq
t.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\lambda x\leq
t.u^{\prime}$.

###### Proof.

For the first case, we apply the rule Srs-App on each reduction
$\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}$ of
$\Gamma;v::s\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}u^{\prime}$. The other cases are immediate in the same way. ∎

###### Lemma B.15 (Transitivity is admissible for well-subtyping).

Let $\Gamma;s$ be an extended context and $u$ and $v$ be terms. If
$\Gamma;s\vdash u\leq^{*}_{\mathrm{wf}}v$ then $\Gamma;s\vdash
u\leq_{\mathrm{wf}}v$.

###### Proof.

By the application Lemma 4.4 and by Propositions 2.3 and B.3 and rule Wf-Rule.
∎

###### Lemma B.16 (From transitive subtyping to well-subtyping).

Let $\Gamma;s$ be an extended context and $u$ and $v$ be terms. If we have
$\Gamma;s\vdash u\leq^{*}v$ and $\Gamma;s\vdash u~{}\mathrm{wf}$ and
$\Gamma;s\vdash v~{}\mathrm{wf}$ then we have $\Gamma;s\vdash
u\leq_{\mathrm{wf}}v$.

###### Proof.

From $\Gamma;s\vdash u\leq^{*}v$ we obtain $\Gamma;s\vdash u\leq v$ by Lemma
4.4.

From $\Gamma;s\vdash u\leq v$ and $\Gamma;s\vdash u~{}\mathrm{wf}$ and
$\Gamma;s\vdash v~{}\mathrm{wf}$ we obtain $\Gamma;s\vdash
u\leq_{\mathrm{wf}}v$ by rule Wf-Rule. ∎

###### Lemma B.17 (Narrowing of stack in well-formedness derivation).

Let $\Gamma$ be a context, $s_{0}$ and $s_{1}$ be two stacks. let $u$, $t$ and
$t^{\prime}$ be terms.

If we have $\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash u~{}\mathrm{wf}$, and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$, and
$t$ preserves well-formedness (defined in B.1), then
$\Gamma;s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash u~{}\mathrm{wf}$.

###### Proof.

By induction on the derivation tree of
$\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash u~{}\mathrm{wf}$.

Here are the cases:

Rule W-Var::

By applying the induction hypothesis.

Rule W-Top::

Ok.

Rule W-Fun::

Impossible, stack is not empty.

Rule W-FunOp, with $s_{0}=\mathrm{nil}$::

As assumption, we have $\Gamma;t::s_{1}\vdash\lambda x\leq u.v~{}\mathrm{wf}$.

By rule W-FunOp, we obtain $\Gamma,x\leq t;s_{1}\vdash v~{}\mathrm{wf}$ and
$\Gamma;\mathrm{nil}\vdash u~{}\mathrm{wf}$ from $\Gamma;t::s_{1}\vdash\lambda
x\leq u.v~{}\mathrm{wf}$.

By Lemma B.11, we obtain $\Gamma,x\leq t^{\prime};s_{1}\vdash v~{}\mathrm{wf}$
from $\Gamma,x\leq t;s_{1}\vdash v~{}\mathrm{wf}$, and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$, and
and the fact that $t$ preserves well-formedness (defined in B.1).

By rule W-FunOp, we obtain $\Gamma;t^{\prime}::s_{1}\vdash\lambda x\leq
u.v~{}\mathrm{wf}$ from $\Gamma,x\leq t^{\prime};s_{1}\vdash v~{}\mathrm{wf}$
and $\Gamma;\mathrm{nil}\vdash u~{}\mathrm{wf}$.

Rule W-FunOp, with $s_{0}=\alpha::s_{0}^{\prime}$::

As assumption, we have
$\Gamma;\alpha::s_{0}^{\prime}\mathop{++}(t::s_{1})\vdash\lambda x\leq
u.v~{}\mathrm{wf}$.

By rule W-FunOp we obtain
$\Gamma,x\leq\alpha;s_{0}^{\prime}\mathop{++}(t::s_{1})\vdash v~{}\mathrm{wf}$
from $\Gamma;\alpha::s_{0}^{\prime}\mathop{++}(t::s_{1})\vdash\lambda x\leq
u.v~{}\mathrm{wf}$.

By using the induction hypothesis, we obtain
$\Gamma,x\leq\alpha;s_{0}^{\prime}\mathop{++}(t^{\prime}::s_{1})\vdash
v~{}\mathrm{wf}$, from
$\Gamma,x\leq\alpha;s_{0}^{\prime}\mathop{++}(t::s_{1})\vdash
v~{}\mathrm{wf}$, and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$, and
$t$ preserves well-formedness (defined in B.1).

By rule W-FunOp, we obtain $\Gamma;t^{\prime}::s_{1}\vdash\lambda x\leq
u.v~{}\mathrm{wf}$ from
$\Gamma,x\leq\alpha;s_{0}^{\prime}\mathop{++}(t^{\prime}::s_{1})\vdash
v~{}\mathrm{wf}$.

Rule W-App::

As assumption, we have $\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash
u\,v~{}\mathrm{wf}$.

By rule W-App, we obtain $\Gamma;v::s_{0}\mathop{++}(t::s_{1})\vdash
u\leq_{\mathrm{wf}}\lambda z.\mathsf{Top}$ and $\Gamma;\mathrm{nil}\vdash
v\leq_{\mathrm{wf}}z$ from $\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash
u\,v~{}\mathrm{wf}$.

By Lemma B.3 on $\Gamma;v::s_{0}\mathop{++}(t::s_{1})\vdash
u\leq_{\mathrm{wf}}\lambda z.\mathsf{Top}$ and $\Gamma;\mathrm{nil}\vdash
v\leq_{\mathrm{wf}}z$, we obtain that all the following derivation tree
$\Gamma;v::s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash u~{}\mathrm{wf}$ and
$\Gamma;v::s_{0}\mathop{++}(t::s_{1})\vdash\lambda
z.\mathsf{Top}~{}\mathrm{wf}$ are subtree of our current derivation tree
$\Gamma;s\vdash u~{}\mathrm{wf}$

By the induction hypothesis, we obtain
$\Gamma;v::s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash u~{}\mathrm{wf}$, from
$\Gamma;v::s_{0}\mathop{++}(t::s_{1})\vdash u~{}\mathrm{wf}$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$ and
$t$ preserves well-formedness (defined in B.1).

By the induction hypothesis the same way, we obtain
$\Gamma;v::s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash\lambda
z.\mathsf{Top}~{}\mathrm{wf}$, from
$\Gamma;v::s_{0}\mathop{++}(t::s_{1})\vdash\lambda
z.\mathsf{Top}~{}\mathrm{wf}$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$ and
$t$ preserves well-formedness (defined in B.1).

By Lemma B.18, we obtain $\Gamma;v::s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash
u\leq^{*}\lambda x\leq z.\mathsf{Top}$ from
$\Gamma;v::s_{0}\mathop{++}(t::s_{1})\vdash u\leq^{*}\lambda x\leq
z.\mathsf{Top}$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$.

By the previous two statements, we have
$\Gamma;v::s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash
u\leq_{\mathrm{wf}}\lambda x\leq z.\mathsf{Top}$ by Wf-Rule.

By W-App, we have the result from
$\Gamma;v::s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash
u\leq_{\mathrm{wf}}\lambda x\leq z.\mathsf{Top}$ and
$\Gamma;\mathrm{nil}\vdash v\leq_{\mathrm{wf}}z$.

∎

###### Lemma B.18 (Narrowing of stack in subtyping derivation).

If $\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash u\leq^{*}v$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$ then
$\Gamma;s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash u\leq^{*}v$.

###### Proof.

By the exact same reasoning of B.12, it is sufficient to prove that for any
terms $a$ and $b$, $\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash
a\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}b$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$
implies $\Gamma;s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash a\leq b$.

By induction on $\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash
a\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}b$.

Rule Srs-Prom::

By induction.

Rule Srs-Top::

By assumption we have $\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash
a\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\mathsf{Top}$, and
$\Gamma;s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash
a\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\mathsf{Top}$ is
also valid with Srs-Top.

Rule Srs-Eq::

By assumption we have
$a\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}\mathsf{Top}$,
and $\Gamma;s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash
a\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\mathsf{Top}$ is
also valid with Srs-Eq.

Rule Srs-App::

By assumption we have $\Gamma;s_{0}\mathop{++}(t::s_{1})\vdash
u\,v\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}u^{\prime}\,v$
and $\Gamma;v::s_{0}\mathop{++}(t::s_{1})\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}u^{\prime}$. By
using the induction on $\Gamma;v::s_{0}\mathop{++}(t::s_{1})\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}u^{\prime}$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$, we
obtain $\Gamma;v::s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash u\leq u^{\prime}$.
By Lemma B.13, we obtain $\Gamma;s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash
u\,v\leq u^{\prime}\,v$ from
$\Gamma;v::s_{0}\mathop{++}(t^{\prime}::s_{1})\vdash u\leq u^{\prime}$. Hence
this case.

Rule Srs-FunOp with $s_{0}=\alpha::s_{0}^{\prime}$::

By assumption we have
$\Gamma;\alpha::s_{0}^{\prime}\mathop{++}(t::s_{1})\vdash\lambda y\leq
w.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\lambda y\leq
w.u^{\prime}$, and
$\Gamma,y\leq\alpha;s_{0}^{\prime}\mathop{++}(t::s_{1})\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}u^{\prime}$. By
using the induction on
$\Gamma,y\leq\alpha;s_{0}^{\prime}\mathop{++}(t::s_{1})\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}u^{\prime}$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$, we
obtain $\Gamma,y\leq\alpha;s_{0}^{\prime}\mathop{++}(t^{\prime}::s_{1})\vdash
u\leq u^{\prime}$. By Lemma B.13, we obtain
$\Gamma;\alpha::s_{0}^{\prime}\mathop{++}(t^{\prime}::s_{1})\vdash\lambda
y\leq w.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\lambda
y\leq w.u^{\prime}$ from
$\Gamma,y\leq\alpha;s_{0}^{\prime}\mathop{++}(t^{\prime}::s_{1})\vdash u\leq
u^{\prime}$. Hence this case.

Rule Srs-FunOp with $s_{0}=\mathrm{nil}$::

By assumption we have $\Gamma;t::s_{1}\vdash\lambda y\leq
w.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\lambda y\leq
w.u^{\prime}$, and $\Gamma,y\leq t;s_{1}\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}u^{\prime}$. By
Lemmas B.12, 2.4 and 4.4 we obtain and $\Gamma,y\leq t^{\prime};s_{1}\vdash
u\leq u^{\prime}$ from and $\Gamma,y\leq t;s_{1}\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}u^{\prime}$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t^{\prime}$. By
Lemma B.13, we obtain $\Gamma;t^{\prime}::s_{1}\vdash\lambda y\leq
w.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}\lambda y\leq
w.u^{\prime}$ from $\Gamma,y\leq t^{\prime};s_{1}\vdash u\leq u^{\prime}$.
Hence this case.

Rule Srs-Fun::

Cannot happen. Stack is empty is this case.

∎

###### Lemma B.19
($\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}$ has the diamond
property).

Let $t_{0}$, $t_{1}$, $t_{2}$ be terms.

If $t_{0}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t_{1}$ and
$t_{0}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t_{2}$, then
there exists a term $t_{3}$ such that
$t_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t_{3}$ and
$t_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}t_{3}$.

Diagrammatically,

${t_{2}}$${t_{3}}$${t_{0}}$${t_{1}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$

where the solid arrows are the condition for the existence of the dashed
arrows.

###### Proof.

By induction on the term structure of $t_{0}$. We consider cases according to
the last two rules that are applied respectively in the derivation of the
horizontal and vertical edges of the diagram above, starting by the bottom-
left corner. The base case corresponds to when these two rules are both Cr-
Var, or both Cr-Top, for which the lemma holds trivially. For the general case
we distinguish the subcases below:

Rules Cr-App and Cr-App::

We need to prove the diagram below:

${u_{2}\,v_{2}}$${u_{3}\,v_{3}}$${u_{0}\,v_{0}}$${u_{1}\,v_{1}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$

By the induction hypothesis there exists $u_{3}$ and $v_{3}$ such that
$u_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$ and
$v_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$. The
dashed edges in the diagram above hold by rule Cr-App.

Case Cr-App with Cr-Beta::

Here is the diagram we want to obtain:

${u_{2}[x\backslash v_{2}]}$${u_{3}[x\backslash v_{3}]}$${(\lambda x\leq
t_{0}.u_{0})v_{0}}$${(\lambda x\leq
t_{1}.u_{1})v_{1}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$

By the induction hypothesis there exists $u_{3}$ and $v_{3}$, such that
$u_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$,
$u_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$, and
$v_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$,
$v_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$.

By rule Cr-Beta, the relation $(\lambda x\leq
t_{1}.u_{1})v_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}[x\backslash
v_{3}]$ holds from
$u_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$ and
$v_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$.

By Lemma B.10, the top reduction holds from
$u_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$ and
$v_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$.

Case Cr-App with Cr-TopApp::

The following diagram holds by Cr-Top and Cr-TopApp.

${\mathsf{Top}}$${\mathsf{Top}}$${\mathsf{Top}\,u}$${\mathsf{Top}\,u^{\prime}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$

Case Cr-Fun with Cr-Fun::

We need to prove the diagram below:

${\lambda x\leq t_{2}.u_{2}}$${\lambda x\leq t_{3}.u_{3}}$${\lambda x\leq
t_{0}.u_{0}}$${\lambda x\leq
t_{1}.u_{1}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$

Similar to Cr-App, by the induction hypothesis there exists $u_{3}$ and
$v_{3}$, and both dashed relation holds by Cr-Fun.

Case Cr-Beta with Cr-Beta::

We need to prove the diagram below:

${u_{2}[x\backslash v_{2}]}$${u_{3}[x\backslash v_{3}]}$${(\lambda x\leq
t.u_{0})v_{0}}$${u_{1}[x\backslash
v_{1}]}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$

By the induction hypothesis there exists $u_{3}$ and $v_{3}$, such that
$u_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$,
$u_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$, and
$v_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$,
$v_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$.

By Lemma B.10, the top reduction holds from
$u_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$ and
$v_{2}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$, and
with the same lemma, the right reduction holds from
$u_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u_{3}$ and
$v_{1}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v_{3}$,

Case Cr-TopApp with Cr-TopApp::

The following diagram holds by rule Cr-Top.

${\mathsf{Top}}$${\mathsf{Top}}$${\mathsf{Top}\,u}$${\mathsf{Top}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$

∎

##  Appendix C Lemmas of Section 5

This part of the appendix follows the text.

Lemma 5.1 (Minimal promotion is well defined). Let $\Gamma;s$ be an extended
context. Let $u$ be a term. If $u$ is not $\mathsf{Top}$, then there exists a
unique term $v$ such that $\Gamma;s\vdash
u\mathop{\stackrel{{\scriptstyle\mathrm{mp}}}{{\longrightarrow}}}v$.

###### Proof.

Ok from the definition. ∎

Lemma 5.3 (The minimal promotion is indeed minimal). Promotions
$\mathop{\stackrel{{\scriptstyle\mathrm{mp}}}{{\longrightarrow}}}$ are always
minimal.

###### Proof.

By induction on $\Gamma;\mathrm{nil}\vdash
u_{n}\mathop{\stackrel{{\scriptstyle\,{\leq}\,}}{{\longrightarrow}}}v$. Here
are the cases.

Srs-Prom::

Then $u_{n}=x$, and the algorithm returns the term $t$ such that $x\leq
t\in\Gamma$, just like Srs-Prom.

Srs-Top::

In this case $v=\mathsf{Top}$, and we have $\Gamma;s\vdash
w\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}v$ by Srs-Top.

Srs-Eq::

In this case we have
$u_{n}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}v$. Because
$u_{n}$ is in normal form, we have $v=u_{n}$ and the result follows.

Srs-App::

Here we have $u_{n}=a_{n}\,b$ and $v=a^{\prime}\,b$. By Srs-App, we have
$\Gamma;b::s\vdash
a_{n}\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}a^{\prime}$.
Let’s call $w_{a}$ the term such that $\Gamma;s\vdash
a\mathop{\stackrel{{\scriptstyle\mathrm{mp}}}{{\longrightarrow}}}w_{a}$. By
induction, $\Gamma;s\vdash
w_{a}\mathop{\stackrel{{\scriptstyle\,{\leq}\,}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}a^{\prime}$. By rule Srs-App, we have the desired result.

Srs-FunOp::

Same as Srs-App.

Srs-Fun::

Same as Srs-App.

∎

Theorem 5.5 (Correctness of the subtyping algorithm). Let $\Gamma;s$ be an
extended context. Let $u$ and $t$ be terms.

If the algorithm terminates on $\Gamma,s,u,t$ and returns $\Gamma;s\vdash
u{\,\textsc{st}\,}t$ then we have $\Gamma;s\vdash u\leq t$.

If $\Gamma;s\vdash u\leq t$ and the algorithm terminates on $\Gamma,s,u,t$,
then it returns $\Gamma;s\vdash u{\,\textsc{st}\,}t$.

###### Proof.

Assume the algorithm terminates on $\Gamma,s,u,t$ and returns $\Gamma;s\vdash
u{\,\textsc{st}\,}t$. The result of the algorithm is the derivation tree
$\Gamma;s\vdash u{\,\textsc{st}\,}t$. By replacing in this tree every st
symbol into $\leq$, it becomew a derivation tree of $\Gamma;s\vdash u\leq t$.

Conversly, if we have a derivation tree of $\Gamma;s\vdash u\leq t$. Let’s
denote $t_{n}$ the normal form of $t$. We also have $\Gamma;s\vdash u\leq
t_{n}$. Let’s prove that $t_{n}$ is on the minimal superpath of $u$, that is
$\Gamma;s\vdash
u\mathop{\stackrel{{\scriptstyle\mathrm{mp}}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{n}$. This will build the requested tree $\Gamma;s\vdash
u{\,\textsc{st}\,}t_{n}$. The rest of the proof prove that $t_{n}$ is on the
minimal superpath of $u$.

If $t_{n}$ is on the minimal superpath, we have $\Gamma;s\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{n}$ by rule Srs-Eq, hence $\Gamma;s\vdash u\leq t$. Conversly,
if $\Gamma;s\vdash u\leq t$, there exists by Lemma 2.4 a term $w$ such that
$\Gamma;s\vdash
u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}w$ and
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}w$. But, we have
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{n}$, and $t_{n}$ cannot be reduced anymore by
$\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}$, hence
$w\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{n}$ by confluence of
$\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}$.

Here is the diagram of where we at in the proof:

${t}$${w}$${t_{n}}$${u^{\prime}}$${\cdots}$${u}$${u_{n}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\mathrm{mp}}$

To make the induction easier, we transform
$w\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{n}$ into $\Gamma;s\vdash
w\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{n}$ by rule Srs-Eq. We also remove $t$ from the diagram. It
becomes the following diagram:

${t_{n}}$${u^{\prime}}$${\cdots}$${u}$${u_{n}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\mathrm{mp}}$

We do an induction on the number of terms in normal form $u_{n}$ on the
minimal superpath. There are a finite number of them. If $t_{n}$ is $u_{n}$,
we have nothing to do. Else, we have $\Gamma;s\vdash
u_{n}\mathop{\stackrel{{\scriptstyle{\mathrm{mp}}}}{{\longrightarrow}}}u^{\prime}$,
and $\Gamma;s\vdash
u_{n}\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{n}$ by commutativity. Because
$\mathop{\stackrel{{\scriptstyle{\mathrm{mp}}}}{{\longrightarrow}}}$ is
minimal, and because
$u_{n}\not\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow}}}u^{\prime}$,
we have by Lemma 5.3 either $u^{\prime}=t_{n}$, or
$u^{\prime}\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{n}$. In the first case, we are done, $t_{n}$ is indeed on the
minimal superpath of $u$. Otherwise, we are in the following situation:

${t_{n}}$.${\cdots}$${u^{\prime}}$${u^{\prime}_{n}}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\equiv}$$\scriptstyle{\mathrm{mp}}$

We finish the proof by applying the induction on $u^{\prime}$. ∎

Correctness 5.6 (Correctness of the well-formedness algorithm). Let $\Gamma;s$
be an extended context, such that $\Gamma;s$ is prevalid. Let $u$ be a term.

If the algorithm terminates on $\Gamma,s,u$ and returns $\Gamma;s\vdash
u{~{}\textsc{wf}}$ then we have $\Gamma;s\vdash u~{}\mathrm{wf}$.

If $\Gamma;s\vdash u~{}\mathrm{wf}$ and the algorithm terminates on
$\Gamma,s,u$, then it returns $\Gamma;s\vdash u{~{}\textsc{wf}}$.

###### Proof.

If the algorithm terminates and successfully builds a tree, then as in the
proof of correctness of the subtyping algorithm, we have $\Gamma;s\vdash
u~{}\mathrm{wf}$ by replacing every wf into $\mathrm{wf}$ in the obtained
derivation tree.

Conversly, if $\Gamma;s\vdash u~{}\mathrm{wf}$ we need to a show a derivation
tree $\Gamma;s\vdash u{~{}\textsc{wf}}$ exists. Because the rules are the
same, there is nothing to do except for the rule W-App. In that case, we have
a $t$ such that $\Gamma;s\vdash u\leq\lambda x\,{\leq}\,t.\mathsf{Top}$. If
$t$ is not in normal form, let’s denote $t_{n}$ its normal form. We also have
$\Gamma;s\vdash u\leq\lambda x\,{\leq}\,t_{n}.\mathsf{Top}$. We know from
Lemma 5.5, that there exists a derivation tree of $\Gamma;s\vdash
u{\,\textsc{st}\,}\lambda x\,{\leq}\,t_{n}.\mathsf{Top}$. From the rules of
the algorithm, this derivation tree is built uniquely by iterating
$\mathop{\stackrel{{\scriptstyle\mathrm{mp}}}{{\longrightarrow}}}$ on $u$ to
then be syntaxicly $\lambda x\,{\leq}\,t_{n}.\mathsf{Top}$. Therefore we have
$u\mathop{\stackrel{{\scriptstyle\mathrm{mp}}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}\lambda x\,{\leq}\,t_{n}.\mathsf{Top}$, which concludes this case.
∎

Lemma 5.7[Inversion lemma] Let $\Gamma;s$ be an extended context. Let $\lambda
x\,{\leq}\,t.u$ and $\lambda x\,{\leq}\,t^{\prime}.u^{\prime}$ be terms. If
$\Gamma;s\vdash(\lambda x\,{\leq}\,t.u)\leq(\lambda
x\,{\leq}\,t^{\prime}.u^{\prime})$ then $\Gamma;s\vdash t\equiv t^{\prime}$.

###### Proof.

First, we transform $\Gamma;s\vdash(\lambda x\,{\leq}\,t.u)\leq^{*}(\lambda
x\,{\leq}\,t^{\prime}.u^{\prime})$ into $\Gamma;s\vdash(\lambda
x\,{\leq}\,t.u)\leq(\lambda x\,{\leq}\,t^{\prime}.u^{\prime})$ by Lemma 4.4.

By Lemma 2.4, that means there exists $v$ such that $\Gamma;s\vdash\lambda
x\,{\leq}\,t.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}v$ and $\lambda
x\,{\leq}\,t^{\prime}.u^{\prime}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}v$, from $\Gamma;s\vdash(\lambda x\,{\leq}\,t.u)\leq(\lambda
x\,{\leq}\,t^{\prime}.u^{\prime})$.

First, we have $\lambda
x\,{\leq}\,t^{\prime}.u^{\prime}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}v$. In the above derivation, the only rule applicable is Cr-Fun,
hence the existence of a function $\lambda x\leq t_{f}.u_{f}$ such that
$v\lambda x\leq t_{f}.u_{f}$, and
$t^{\prime}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{f}$ and
$u^{\prime}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}u_{f}$. Only $t_{f}$ is relevant for the end of the proof, $u_{f}$
will be discarded. Now, from $\Gamma;s\vdash\lambda
x\,{\leq}\,t.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}v$ by substituting $v$ we have $\Gamma;s\vdash\lambda
x\,{\leq}\,t.u\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}\lambda x\,{\leq}\,t_{f}.u_{f}$. By the same argument, we have
$t^{\prime}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{f}$.

By Lemma 2.4, we obtain $\Gamma;\mathrm{nil}\vdash t\equiv t^{\prime}$ from
$t\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{f}$ and
$t^{\prime}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}t_{f}$, hence $\Gamma;\mathrm{nil}\vdash t\equiv^{*}t^{\prime}$
which concludes the proof. ∎

Theorem 5.8 (Composability of the typechecking). Let $u=\lambda x\leq
t^{\prime}.b^{\prime}$ and $v$ be terms. Assume $u$ is in normal form. Assume
$\Gamma;s\vdash u~{}\mathrm{wf}$.

We have that $\Gamma;s\vdash u\,v{~{}\textsc{wf}}$ if
$\Gamma;\mathrm{nil}\vdash v{~{}\textsc{wf}}$ and $\Gamma;\mathrm{nil}\vdash
t^{\prime}{~{}\textsc{wf}}$ and for all $\Gamma^{\prime};s^{\prime}$ extended
context where the variable $x$ appear in $u$,
$\Gamma^{\prime};s^{\prime}\vdash v{~{}\textsc{wf}}$ and
$\Gamma^{\prime};s^{\prime}\vdash v{\,\textsc{st}\,}t^{\prime}$.

###### Proof.

Assume the conditions of the lemma. Let’s prove exactly what requires the
algorithm, that is: for the term $t_{n}$ such that $\Gamma;v::s\vdash
u\mathop{\stackrel{{\scriptstyle\mathrm{mp}}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}\lambda x\leq t_{n}.\mathsf{Top}$ we have
$\Gamma;\mathrm{nil}\vdash v{\,\textsc{st}\,}t_{n}$ and $\Gamma;v::s\vdash
u{~{}\textsc{wf}}$ and $\Gamma;\mathrm{nil}\vdash v{~{}\textsc{wf}}$ and
$\Gamma;\mathrm{nil}\vdash t_{n}{~{}\textsc{wf}}$ and
$\Gamma;v::s\vdash\lambda x\leq t_{n}.\mathsf{Top}{~{}\textsc{wf}}$.

First, assume pick $t_{n}$ such that $\Gamma;v::s\vdash
u\mathop{\stackrel{{\scriptstyle\mathrm{mp}}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}\lambda x\leq t_{n}.\mathsf{Top}$. We have $\Gamma;v::s\vdash
u\leq\lambda x\leq t_{n}.\mathsf{Top}$. But, $u=\lambda x\leq
t^{\prime}.b^{\prime}$ so we have $\Gamma;v::s\vdash\lambda x\leq
t^{\prime}.b^{\prime}\leq\lambda x\leq t_{n}.\mathsf{Top}$. By Lemma 5.7, we
then have $\Gamma;v::s\vdash t^{\prime}\equiv t_{n}$. From Lemma 2.4, we have
a term $w$ such that
$t^{\prime}\mathop{\stackrel{{\scriptstyle\equiv}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}w$ and
$t_{n}\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow\rightarrow\hskip
1.99997pt}}}w$. But both $t^{\prime}$ and $t_{n}$ are in normal form by
assumption, so $t^{\prime}=t_{n}$.

Let’s now prove the required properties one by one.

We have $\Gamma;\mathrm{nil}\vdash v{\,\textsc{st}\,}t_{n}$ from
$\Gamma;s\vdash v{\,\textsc{st}\,}t^{\prime}$ and $t^{\prime}=t_{n}$.

We prove $\Gamma;v::s\vdash u{~{}\textsc{wf}}$ below because it’s the
interesting part.

We have $\Gamma;\mathrm{nil}\vdash v{~{}\textsc{wf}}$ from
$\Gamma;\mathrm{nil}\vdash v{~{}\textsc{wf}}$.

We have $\Gamma;\mathrm{nil}\vdash t_{n}{~{}\textsc{wf}}$ from
$\Gamma;\mathrm{nil}\vdash t^{\prime}{~{}\textsc{wf}}$ and $t^{\prime}=t_{n}$.

We have $\Gamma;v::s\vdash\lambda x\leq t_{n}.\mathsf{Top}{~{}\textsc{wf}}$
from $\Gamma;v::s\vdash u{~{}\textsc{wf}}$ and $u=\lambda x\leq
t^{\prime}.b^{\prime}$ and $t^{\prime}=t_{n}$.

About $\Gamma;v::s\vdash u{~{}\textsc{wf}}$. We need to prove that
$\Gamma;v::s\vdash\lambda x\leq t^{\prime}.b^{\prime}{~{}\textsc{wf}}$ by
$u=\lambda x\leq t^{\prime}.b^{\prime}$. We switch to prove that
$\Gamma;v::s\vdash\lambda x\leq t^{\prime}.b^{\prime}~{}\mathrm{wf}$ by
correctness of the algorithm. By rule W-FunOp, this is equivalent to prove
that $\Gamma;\mathrm{nil}\vdash t^{\prime}~{}\mathrm{wf}$ and and
$\Gamma,x\leq v;\mathrm{nil}\vdash b^{\prime}~{}\mathrm{wf}$. By hypothesis,
we have $\Gamma;\mathrm{nil}\vdash t^{\prime}~{}\mathrm{wf}$ and $\Gamma,x\leq
t^{\prime};\mathrm{nil}\vdash b^{\prime}~{}\mathrm{wf}$. To conclude
$\Gamma,x\leq v;\mathrm{nil}\vdash b^{\prime}~{}\mathrm{wf}$, we now do
exactly as in Lemma B.11, we therefore only sketch the proof, the complete
reasoning can be found in Lemmas B.11 and B.12. We replace, for every extended
context $\Gamma^{\prime};s^{\prime}$ where the variable $x$ appear in $u$,
every instance of the rule W-Var $\Gamma;s^{\prime}\vdash x~{}\mathrm{wf}$,
that have as hypothesis $\Gamma^{\prime};s^{\prime}\vdash
t^{\prime}~{}\mathrm{wf}$ into $\Gamma^{\prime};s^{\prime}\vdash
x~{}\mathrm{wf}$ that needs as hypothesis $\Gamma^{\prime};s^{\prime}\vdash
v~{}\mathrm{wf}$, which we do have by assumption. We also need to replace
every promotion of $x$ to $t^{\prime}$ (rule Srs-Prom) in $\Gamma,x\leq
t^{\prime};\mathrm{nil}\vdash b^{\prime}~{}\mathrm{wf}$ by a promotion of $x$
to $v$, and then use our assumption $\Gamma^{\prime};s^{\prime}\vdash v\leq
t^{\prime}$ to transform any derivation of the form $\cdots,x\leq
t^{\prime},\cdots;s^{\prime}\vdash
x\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}t^{\prime}$ into
$\cdots,x\leq v,\cdots;s^{\prime}\vdash
x\mathop{\stackrel{{\scriptstyle\leq}}{{\longrightarrow}}}v\leq t^{\prime}$. A
more rigourous approach of this reasoning is to be found in Lemmas B.11 and
B.12.

This concludes the proof. ∎