\section{introduction}
During the last years, thermoelectric materials have attracted the attention
of both experimental and theoretical research interest due to their wide
variety of possible technological
applications.\cite{Vining:NAT:2008,Vining:NAT:2009,Dubi:RMP:2011}
These applications aim mainly at the conversion of waste heat into
an electrical current through the Seebeck effect or at cooling through
the Peltier effect.\cite{goldsmid:2010:introduction} An efficient thermocouple
for heat-to-electricity conversion exhibits a low thermal conductance
as well as a large electrical conductance and Seebeck
coefficient.\cite{goldsmid:2010:introduction} In standard
bulk materials there are intrinsic difficulties in disentangling the phonon
and electron contributions to the transport coefficients: improving the
electrical conductance usually increases the thermal conductance and
reduces the Seebeck coefficient. Systems of reduced dimensionality are a
promising alternative since a more accurate and independent control of the
diverse factors dominating the thermoelectric efficiency appears
possible.\cite{Hicks1993} The path
towards molecular electronics and the discovery of two dimensional
materials further expand the scope of potential materials for thermoelectric
applications.\cite{Datta1997,Cuniberti2005,CuevasScheer:10} However, it still
remains a difficult problem to predict which new materials (bulk, layered or
heterostructure) are most apt as thermoelectric devices.

The theory of thermoelectric energy conversion draws from many
sources,\cite{Beenakker:91,Zianni2008,Sothmann2013,Sanchez2013a,DAgosta2013,Eich2014a}
but recently, Density Functional Theory (DFT) has acquired a prominent
role in almost any material
modeling.\cite{Cuniberti2005,Hohenberg1964,Kohn1965}
This popularity is mainly due to two factors: (i) relatively
simple approximations to the so-called exchange-correlation (xc) functional,
the central quantity of DFT, lead to reasonably accurate results for many
material properties and (ii) DFT is numerically very efficient.
For the description of (electronic or thermal) transport, DFT is typically
combined with the Landauer-B\"uttiker (LB-DFT)
formalism.\cite{Datta1997,Cuniberti2005,CuevasScheer:10,ThossEvers:18}
However, formally this approach is incomplete since it treats electrical
transport as a scattering problem of non-interacting electrons and uses
equilibrium DFT for an inherently out-of-equilibrium system. A proper
DFT framework to describe electronic transport is time-dependent DFT (TDDFT).
\cite{RungeGross:84} In TDDFT, one may view steady-state transport as the
long-time limit of a system initially in equilibrium and driven out of
equilibrium by application of an external bias. In the steady state, this
approach will then lead to equations structurally identical to the LB-DFT
equations but with the external bias augmented by a dynamical xc correction.
\cite{StefanucciAlmbladh:04,StefanucciAlmbladh:04-2,SaiZwolakVignaleDiVentra:05,KoentoppBurkeEvers:06,StefanucciKurthRubioGross:06,VignaleDiVentra:09}
As a consequence, the connection between quantities of the real system and those
calculated within the LB-DFT framework is typically nontrivial and strong
corrections may appear.\cite{Stefanucci:NL:2015,Yang:PRB:2016}

More recently, an alternative DFT framework to describe steady-state
electronic transport, dubbed i-DFT, has been
proposed.\cite{Stefanucci:NL:2015} i-DFT directly focusses on the steady state
and is designed to give both the density and the current of a (DC) biased
molecular junction.\cite{Stefanucci:NL:2015} However, it does not make any
statements on the time evolution towards such a steady state. Nevertheless,
just as TDDFT, it also leads to xc corrections to the bias.
So far, functionals for these xc bias corrections have been constructed
for model systems.\cite{Stefanucci:NL:2015,Kurth:PRB:2016,JacobKurth:18}
In particular, i-DFT allows to describe the single impurity Anderson model
(SIAM) both in the Coulomb Blockade (CB) as well as in the Kondo regime.
\cite{Kurth:PRB:2016}

The standard form of i-DFT assumes that the
device and the leads are thermally equilibrated. In this work we
generalize the formalism to finite temperature gradients
between the leads which allows one to use i-DFT as a highly efficient method
to calculate the Seebeck coefficient. Paying special attention to the
temperature dependence of the i-DFT equations we derive: a) an exact expression
for the linear Seebeck coefficient for any system and any regime in terms of pure i-DFT quantities and b) a pair of
xc functionals for the SIAM with explicit dependence on the
thermal gradient $\Delta T$ between the leads which are exact for
$T\gg \gamma$, i.e., for weakly coupled leads. We also model the
effect of the broadening due to the couplings in the functionals and
we equip our functionals to describe the linear Seebeck coefficient in
the Kondo regime in an accurate way.

\section{i-DFT for Thermoelectric effects}

We consider the typical transport setup where a central region, e.g.,
a single molecule or a quantum dot, is coupled to a left (L) and a
right (R) electrode. The system is driven out of equilibrium by
applying a DC bias $V$ across the junction and we are interested in
the resulting steady-state current $I$. The recently suggested i-DFT
framework for steady-state transport\cite{Stefanucci:NL:2015} is based on a
one-to-one mapping between, on the one hand, the density $n(\vr)$ in
the central region and the steady current $I$ through it and, on the
other hand, the external potential $v(\vr)$ in the same region and the
bias $V$ across it. In the original formulation, both left and right
leads are kept at the same temperature $T$ which enters the formalism
as an external parameter only. Here we propose an extension of i-DFT
to include a temperature difference between the leads. This thermal
gradient creates an electronic current which can be compensated by a
bias in an open circuit setup and thus allows to study the Seebeck
effect. For simplicity, we symmetrically apply both a bias $V$ as well
as a temperature difference $\Delta T$ between the two leads, i.e., we
have $V_{\alpha}=\pm V/2$ and $T_{\alpha}=T\pm\Delta T/2$ where $\alpha=L,R$.
\footnote{Needless to say, we assume $T>\Delta T/2$ such that $T_{L},T_{R}>0$.} Of
course, now both $T_L$ and $T_R$ (or, equivalently, $T$ and $\Delta T$)
enter as parameters into the formalism. If we make the (physically
reasonable) assumption that the density in the central region and the
current are continuously differentiable at $\Delta T=0$, the original
i-DFT proof \cite{Stefanucci:NL:2015} of the one-to-one correspondence
between ``densities'' and ``potentials'' can directly be applied to
our situation and we can formulate the i-DFT theorem for leads at
different temperatures (see also
Ref.~\onlinecite{KurthJacobSobrinoStefanucci:19}).

{\em Theorem}:
For any pair of finite temperatures $T_{\alpha}$ in the leads, there
exists a one-to-one correspondence between the pair of ``densities''
$(n,I)$ and the pair of ``potentials'' $(v,V)$ in a finite (and gate
dependent) region around zero voltage $V$ and zero thermal gradient
$\Delta T$.

It is important to note that the proof of the theorem goes through for any
form of the interaction, particularly also for the non-interacting case.
As usual, in order to establish a Kohn-Sham (KS) scheme, we have to assume
non-interacting representability, i.e., that the same densities $(n,I)$ of an
interacting system (with potentials $(v,V)$) can also be obtained as
densities of a non-interacting system with potentials $(v_s,V_s)$.
Following the standard KS procedure, we define the
Hartree-exchange-correlation (Hxc) gate potential as
$v_{\rm Hxc}[n,I]=v_s[n,I]-v[n,I]$  and the xc bias as
$V_{\rm xc}[n,I]=V_s[n,I]-V[n,I]$. The self-consistent coupled KS equations for the
density and the current then are
\begin{align}
n(\vr)&=2\sum_{\alpha=L,R}\int \frac{{\rm d}\omega}{2 \pi} f_{\alpha}(\omega-V_{\alpha,s})
A_{\alpha,s}(\vr,\omega)
\label{n_KS}\\
I&=2\sum_{\alpha=L,R}\int \frac{{\rm d}\omega}{2 \pi}
f_{\alpha}(\omega-V_{\alpha,s})s_{\alpha}\mathcal{T}(\omega)
\label{I_KS}
\end{align}
where $f_{\alpha}(x)=1/(e^{x/T_{\alpha}}+1)$ is the Fermi function (for
lead $\alpha$), $s_{L/R}=\pm$, and $V_{\alpha,s}=s_{\alpha}(V+V_{\rm xc})/2$.
$A_{\alpha,s}(\vr,\omega)=\langle\vr\rvert\mathcal{G}(\omega)\Gamma_{\alpha}(\omega)
\mathcal{G}^{\dagger}(\omega)\rvert\vr\rangle$ is the partial KS spectral function
with the KS Green's function $\mathcal{G}$ and the broadening matrix
$\Gamma_{\alpha}$  of lead $\alpha$. Finally, the transmission function is
given by $\mathcal{T}(\omega)={\rm Tr}\left[\mathcal{G}(\omega)\Gamma_{L}(\omega)
  \mathcal{G}^{\dagger}(\omega)\Gamma_{R}(\omega)\right]$.

Eqs.~(\ref{n_KS}) and (\ref{I_KS}) have the same structure as the original i-DFT
equations \cite{Stefanucci:NL:2015} with the exception that the temperature
difference $\Delta T$ between the two leads enters explicitly both in the Fermi
functions $f_{\alpha}$ and in the functionals for $v_{\rm Hxc}$ and $V_{\rm xc}$. In
the following we use exactly this property to derive an exact expression for
the Seebeck coefficient in terms of i-DFT quantities.

The Seebeck coefficient is defined as that bias which has to be applied to
compensate a small temperature difference between the leads such that no
current flows. Formally it can be written as
\begin{equation}
S=\left.\frac{dV}{d\Delta T}\right\rvert_{\substack{V=0\\ \Delta T=0}}=
\left.\frac{dI/d\Delta T}{dI/dV}\right\rvert_{\substack{V=0\\ \Delta T=0}}.
\label{S_def}
\end{equation}

Both the numerator and the denominator of Eq.~(\ref{S_def}) can be calculated
directly from Eq.~(\ref{I_KS}). The denominator is nothing but the zero-bias
conductance $G$ which can be expressed as \cite{Stefanucci:NL:2015}
\begin{equation}
\label{dI_dV}
G=\left.\frac{dI}{dV}\right\rvert_{\substack{V=0\\ \Delta T=0}}=\frac{G_{s}}{1-G_{s}\left.\frac{\partial V_{xc}}{\partial I}\right\rvert_{{\substack{V=0\\ \Delta T=0}}}}
\end{equation}
where we have defined the KS zero bias conductance
\begin{equation}
G_{s}=-\int \frac{{\rm d}\omega}{2 \pi} f'(\omega)\mathcal{T}(\omega) \;.
\label{ks_cond}
\end{equation}
where $f'(x) = {\rm d}f/{\rm d}x$ with the Fermi function
taken at the temperature $T=T_L=T_R$.

Similarly, the numerator of Eq.~(\ref{S_def}) can be calculated as
\begin{eqnarray}
\label{dI_dDT}
\left.\frac{dI}{d\Delta T}\right\rvert_{\substack{V=0\\ \Delta T=0}} &=&
\int \frac{{\rm d}\omega}{2 \pi} \left[f'(\omega)\left(\frac{\omega}{T}+\frac{dV_{xc}}{d\Delta T}\right)\right]\mathcal{T}(\omega)\nonumber \\
&=&\frac{L_{s}-G_{s}\left.\frac{\partial V_{xc}}{\partial \Delta T}\right\rvert_{{\substack{V=0\\ \Delta T=0}} }}{1-G_{s}\left.\frac{\partial V_{xc}}{\partial I}
  \right\rvert_{{\substack{V=0\\ \Delta T=0}}}}
\end{eqnarray}
where we have defined
\begin{equation}
L_{s}=\frac{1}{T}\int \frac{{\rm d}\omega}{2 \pi} f'(\omega)\omega
\mathcal{T}(\omega) \;.
\end{equation}
In deriving Eq.~(\ref{dI_dDT}) we have expanded out the total
derivative,
\begin{equation}
\frac{{\rm d}V_{xc}}{d\Delta T}= \frac{\partial V_{xc}}{\partial \Delta T}
+ \frac{\partial V_{xc}}{\partial I} \frac{dI}{d\Delta T}
+\int {\rm d}^3 r\; \frac{\delta V_{xc}}{\delta n(\vr)}
\frac{d n(\vr)}{d\Delta T},
\end{equation}
and used the fact that for $I=0$ (i.e., $V=0$ and $\Delta T = 0$) the last term
vanishes because $V_{\rm xc}[n,I=0]=0$.

Combining Eqs.~(\ref{dI_dV}) and (\ref{dI_dDT}), we then arrive at the
following simple expression for the linear Seebeck coefficient
\begin{equation}
S=S_{s}-\left.\frac{\partial V_{xc}}{\partial \Delta T}
\right\rvert_{\substack{\Delta V=0\\ \Delta T=0}},
\label{linear_Seebeck_dft}
\end{equation}
where $S_{s}=\frac{L_{s}}{G_{s}}$ is KS Seebeck coefficient and the second term
of Eq.~(\ref{linear_Seebeck_dft}) is the xc contribution.
Eq.~(\ref{linear_Seebeck_dft}) is one of the central results of the present
work. It is formally exact and expresses the Seebeck coefficient of a general
interacting system solely in terms of i-DFT quantities. In practice, of course,
one has to use approximations for the Hxc gate and the xc bias functionals.
We will address the construction of such approximations for a model system in
the next Section. We also point out that an expression similar to
Eq.~(\ref{linear_Seebeck_dft}) was recently obtained in a standard DFT
framework\cite{Yang:PRB:2016} in the Coulomb Blockade (CB) regime. In the
following Section, we will discuss the connection between the two approaches.

\section{Single Impurity Anderson Model}
\label{siam}

In this Section we consider the single-impurity Anderson model (SIAM) which
also in previous works \cite{Stefanucci:NL:2015,Kurth:PRB:2016,Yang:PRB:2016}
has been used as a first model for the development of approximate i-DFT
functionals. The SIAM describes a single interacting impurity level (quantum
dot) coupled to a left (L) and right (R) lead. The dot is described by
the Hamiltonian
\begin{equation}
\hat{H}^{\rm dot} = \sum_{\sigma} v \hat{n}_{\sigma} + U \hat{n}_{\uparrow}
\hat{n}_{\downarrow}
\end{equation}
where $v$ is the on-site energy of the dot and $U$ is the interaction and
$\hat{n}_{\sigma}$ is the operator for the density of electrons with spin
$\sigma$ on the dot. The system is coupled to left and right featureless
electronic leads described by frequency-independent
couplings $\Gamma_{\alpha}(\omega)=\gamma_{\alpha}$ (with $\alpha=L,R$), i.e., we work in the
wide band limit (WBL). The leads are characterized by temperature $T_{\alpha}$ and
may be subject to a DC bias $V_{\alpha}$ which we take to be symmetric, i.e.,
$V_L=-V_R=V/2$.

If we want to study the system in an i-DFT framework, we need approximations
for the (H)xc functionals. The approximate functionals designed in previous
work \cite{Stefanucci:NL:2015,Kurth:PRB:2016} were restricted to the case of
equal lead temperatures, $T_L=T_R$, and therefore we need to extend the
construction to the more general case $T_L\neq T_R$.

{\em Coulomb blockade regime - }Following ideas used in earlier work
\cite{Stefanucci:NL:2015}, we first aim to construct approximations for the
xc functionals in the Coulomb blockade regime. We start by
expressing both the density on and the current through the dot
in terms of the many-body spectral function $A(\omega)$:
\begin{subequations}
  \begin{equation}
    \begin{split}
      n =& \int \frac{{\rm d}\omega}{2 \pi}\left[ \frac{2\gamma_L}{\gamma}  f_L(\omega-\mu-V_L)\right.\\
     &+ \left. \frac{2\gamma_R}{\gamma}  f_R(\omega-\mu-V_R) \right] A(\omega)
\end{split}
\end{equation}
\begin{equation}
\begin{split}
  I =& \frac{2 \gamma_L \gamma_R}{\gamma} \int \frac{{\rm d}\omega}{2 \pi}\; \left[ f_L(\omega-\mu-V_L) \right. \\
    & \left .- f_R(\omega-\mu-V_R) \right]
A(\omega)
\end{split}
\end{equation}
\label{dens_curr_siam}
\end{subequations}
where $\gamma=\gamma_L+\gamma_R$ is the total broadening.

We want to use Eqs.~(\ref{dens_curr_siam}) to reverse engineer the (H)xc
potentials of i-DFT, therefore we need a model for the many-body spectral
function $A(\omega)$. As a starting point we use the exact spectral function of the
isolated dot which is given by
\begin{equation}
A_0^{\rm mod}(\omega)=\left(1-\frac{n}{2}\right)\delta(\omega-v)+
\frac{n}{2}\delta(\omega-v-U) \;.
\label{A_delta_model}
\end{equation}
Using $A_0^{\rm mod}(\omega)$ as model spectral function for the
{\em contacted} dot and inserting it into Eqs.~(\ref{dens_curr_siam}) leads
to exactly the same expressions for density and current as one would obtain
by working out the rate equations which are valid in
the Coulomb blockade regime.\cite{Beenakker:91} Inserting Eq.~(\ref{A_delta_model})
into Eqs.~(\ref{dens_curr_siam}), the reverse-engineering for the Hxc gate
and xc bias potentials can be done analytically. This follows by forming
from Eqs.~(\ref{dens_curr_siam}) the linear combinations $n+I/\gamma_L$ and
$n-I/\gamma_R$ and realizing that the inversion of the resulting equations for
the potentials $v\pm V/2$ can be done exactly as in
Refs.~\onlinecite{dittmann:PRL:2018,DittmannHelbigKennes:19}.
The resulting Hxc gate and xc bias potentials are
\begin{subequations}
\begin{equation}
\label{v_Hxc}
\tilde{v}_{\rm Hxc}=\frac{1}{2}\left(g(n,-I/\gamma_R,T_{R})+g(n,I/\gamma_L,T_{L})\right)
\;,
\end{equation}
\begin{equation}
\tilde{V}_{\rm xc}=g(n,-I/\gamma_R,T_{R})-g(n,I/\gamma_L,T_{L}) \;,
\label{V_xc}
\end{equation}
\label{xcpots_cb}
\end{subequations}
where we have defined
\begin{equation}
g(n,x,T)= U+T \log\left( \frac{ p+\sqrt{ p^{2}-z y e^{-U/T}}}{y}\right)
 \label{Helbig_functionals}
\end{equation}
with  $z=y-2$, $y=4x+ n$ and $p=n-1+2x\left( 1+ e^{-U/T}\right)$.
As mentioned above, Eqs.~(\ref{xcpots_cb}) are equivalent to
reverse-engineering the rate equations and therefore should be valid at high
temperatures $T\gg\gamma$, i.e. in the parameter regime where the effect of
temperature is much more important than the coupling to the leads.

For the construction of xc potentials which give reasonable approximations
also in the regime of $T\sim\gamma$ we start by using a model spectral function
\cite{Stefanucci:NL:2015} of the form (\ref{A_delta_model}) but with the
delta functions replaced by Lorentzians
$l_{\gamma}(\omega)=\frac{\gamma}{\omega^{2}+\gamma^{2}/4}$ of width
$\gamma=\gamma_L+\gamma_R$, i.e.
\begin{equation}
A_{\gamma}^{\rm mod}(\omega)=\left(1-\frac{n}{2}\right)l_{\gamma}(\omega-v)+
\frac{n}{2}l_{\gamma}(\omega-v-U) \;.
\label{A_lorentzian_model}
\end{equation}
\begin{figure}
  \includegraphics[width=\columnwidth]{4_panel_RE_dft.eps}
  \caption{
    Hxc potentials $\tilde{v}_{\rm Hxc}$ of the symmetrically coupled SIAM
    ($\gamma_L=\gamma_R=\gamma/2$) in the Coulomb blockade regime
    for different temperatures calculated by reverse-engineering (RE)
    compared to the parametrization of Eq.~(\ref{xcpots_cb_tempeff})
    Panels a) and b) are for $U/\gamma=4$, panels c) and d) for $U/\gamma=8$,
    while panels a) and c) are for zero current $I=0$
    and panels b) and d) for $I/\gamma=1/4$.
  }
  \label{fig:fit_T_star}
\end{figure}
For this model, the reverse-engineering cannot be carried out analytically
(not even at $T=0$) but still can easily be done numerically. However, it is
then desirable to have simple parametrizations of the resulting xc potentials.
In Ref.~\onlinecite{Stefanucci:NL:2015} a simple parametrization for
$T=0$ has been suggested. Since here we are interested in finite temperatures,
a generalization is required. To construct such a parametrization we use the
observation \cite{Kurth:JPCM:2017} that both temperature $T$ and
spectral broadening $\gamma$ lead to similar smearing out of step features which
are present in the low-temperature and/or strongly correlated limit.
Therefore we suggest a parametrization using the same analytic form as
in Eqs.~(\ref{xcpots_cb}) but replacing the left and right temperatures
$T_{L/R}$ by effective temperatures $T^{*}_{L/R}$, e.g.,
\begin{subequations}
\begin{equation}
\label{v_Hxc_tempeff}
\tilde{v}_{\rm Hxc}=\frac{1}{2}\left(g(n,-I/\gamma_R,T^*_{R})+g(n,I/\gamma_L,T^*_{L})
\right),
\end{equation}
\begin{equation}
\tilde{V}_{\rm xc}=g(n,-I/\gamma_R,T^*_{R})-g(n,I/\gamma_L,T^*_{L}).
\label{V_xc_tempeff}
\end{equation}
\label{xcpots_cb_tempeff}
\end{subequations}
The effective temperatures $T^{*}_{\alpha}$ we parametrize as
\begin{equation}
T^{*}_{\alpha}(T_{\alpha},\gamma)=\frac{T_{\alpha}^{2}+(\eta\gamma)^{2}+\eta\gamma T_{\alpha}}
{T_{\alpha}+\eta\gamma} \;.
\label{effective_temperature}
\end{equation}
This parametrization is chosen in such a way that
$T_{\alpha}^{*}(T_{\alpha},\gamma\to 0)=T_{\alpha}$  and
$\eta$ is a fit parameter for which we take the value $\eta=0.45$ in the Coulomb
blockade regime. From now on, we always choose symmetric coupling of the leads,
i.e. $\gamma_L=\gamma_R=\gamma/2$. The quality of our parametrization can be appreciated in
Fig.~\ref{fig:fit_T_star} where we compare the model $\tilde{v}_{\rm Hxc}$
with the corresponding results of the reverse engineering (RE) from Eq.~(\ref{A_lorentzian_model})
 for $U/\gamma=4$ (panels a) and b)) and $U/\gamma=8$ (panels c) and d)). We see that, at
equilibrium ($I=0$, panels a) and c)), our parametrization reproduces the
reverse-engineered Hxc potential very accurately for all the considered
temperatures. Also at finite current ($I/\gamma=1/4$, panels b) and d)), our
approach gives a reasonable parametrization of the reverse-engineered Hxc
potential, although there are some differences at the borders of the domain
for the lowest temperature.

As another check on the quality of our parametrization, in Fig.~\ref{n_CB} we
show the density and the electronic current induced by a temperature
difference $\Delta T$ between the leads (at zero bias) as function of
$\Delta T$ for different gate voltages $v_g=v+U/2$. The i-DFT
results are obtained using the xc potentials in Eqs.~(\ref{xcpots_cb_tempeff})
and are compared to those obtained by the direct evaluation of
Eqs.~(\ref{dens_curr_siam}) with the model spectral functions of
Eqs.~(\ref{A_delta_model}) and (\ref{A_lorentzian_model}), respectively. The
agreement, especially for the latter case, is excellent.

\begin{figure}
  \includegraphics[width=\linewidth]{n_I_CB.eps}
  \caption{Densities (panel a)) and currents (panel b)) as function of the
    temperature difference $\Delta T = T_{L}-T_{R}$ for $U/\gamma=5$,
    $T_{R}=0.1$ and $V=0$ for different gate voltages $v_g=v+\frac{U}{2}$.
    The i-DFT results using the xc potentials of Eq.~(\ref{xcpots_cb_tempeff})
    are compared with those obtained directly from Eq.~(\ref{dens_curr_siam})
    when using either the model spectral function $A^{mod}_{0}$ of
    Eq.~(\ref{A_delta_model}) or $A^{mod}_{\gamma}$ of
    Eq.~(\ref{A_lorentzian_model}).
  }
  \label{n_CB}
\end{figure}

An interesting structural property of the xc potentials of
Eqs.~(\ref{xcpots_cb}) is that they are given as the sum of two pieces, each
one depending only on the parameters (temperature and coupling) of one of the
leads. For the couplings this has already been noted in
Ref.~\onlinecite{KurthStefanucci:18}. For the case of different temperatures in
the leads, $T_{\alpha}=T\pm \Delta T/2$, it can be easily shown that this
structure leads to the xc contribution to the many-body Seebeck coefficient
(Eq.~(\ref{linear_Seebeck_dft})) of the form
\begin{equation}
S_{xc}^{CB}=\left.\frac{\partial V_{xc}}{\partial \Delta T}\right
\rvert_{\substack{V=0\\ \Delta T=0}}=\left.\frac{\partial v_{Hxc}}{\partial T}
\right\rvert_{\substack{V=0\\ \Delta T=0}}.
\end{equation}
While this result holds for any approximation with the structural property
mentioned above, for the special case of the functionals of
Eq.~(\ref{xcpots_cb}) it reduces exactly to the expression obtained in
Ref.~\onlinecite{Yang:PRB:2016}.\footnote{Notice that by comparing (18) and (9)
  one arrives at $S=S_s-S_{xc}$. This reflects the standard definition $V_{xc}=V_s-V$.}

\begin{figure}
  \includegraphics[width=\linewidth]{2_panel_densities.eps}
  \caption{\label{fig:densities}
    Panel a) Densities as function of temperature for different gate
    voltages. Panel b) Densities as function of gate voltage
    for different temperatures. In both panels i-DFT results are compared with
    the NRG results of Ref.~\onlinecite{costi:PRB:2010} for $U/\gamma=8$.
    }
\end{figure}

{\em Kondo regime - }So far we have constructed functionals in the temperature
regime of Coulomb blockade $T\gtrsim T_{K}$ where $T_K$ is the Kondo
temperature. In order to extend the range of applicability of our approximation
to temperatures below $T_K$, we follow the ideas outlined in Ref.~
\onlinecite{Kurth:PRB:2016}. There the central observation was that at zero
temperature the correct behaviour of the zero-bias conductance
(Eq.~(\ref{dI_dV})) is already contained in the KS conductance $G_s$ due to
the Friedel sum rule.
\cite{StefanucciKurth:11,Bergfield:PRL:2012,TroesterSchmitteckertEvers:12}
Therefore, at zero temperature the derivative $\partial V_{\rm xc}/\partial I$
has to vanish at $I=0$. Following Ref.~\onlinecite{Kurth:PRB:2016}, we modify
our functional as
\begin{subequations}
\begin{equation}
v_{Hxc}=\left[1-k(n,I,T)\right]\tilde{v}_{Hxc}+k(n,I,T)v_{Hxc}^{(0)}(n)
\end{equation}
\begin{equation}
V_{xc}=\left[1-k(n,I,T)\right]\tilde{V}_{xc}(n,I,T)
\end{equation}
\label{functionals_prefactor}
\end{subequations}
where $v_{Hxc}^{(0)}$ is the zero-temperature, equilibrium Hxc potential of
Ref.~\onlinecite{Bergfield:PRL:2012} which accurately parametrizes density
matrix renormalization group results. We further introduce the prefactor
$k(n,I,T)$ with the properties
$k(n,I=0,T=0)=1$ and $\partial k(n,I,T)/\partial I \vert_{I=0,T=0}=0$.
The first property ensures that at zero current and zero temperature
$v_{\rm Hxc}$ reduces to $v_{\rm Hxc}^{(0)}$, the second one leads to a vanishing
correction to the KS zero-bias conductance at zero temperature.
To be specific, we choose $k(n,I,T)=a(n,I)z(T)$, where $a(n,I)$ is the same
prefactor used in Eq.~(12) of Ref.~\onlinecite{Kurth:PRB:2016}. This
prefactor, although combined with a different form for the Coulomb blockade
functionals $\tilde{v}_{\rm Hxc}$ and $\tilde{V}_{\rm xc}$ ensures
a good description of the finite bias conductance for relatively low
temperatures. We also found it convenient to introduce another prefactor
$z(T)=(1+(2.5T/\gamma)^{3})^{-1}$ to ensure a smooth transition to the Coulomb
blockade form of the functional at high temperatures.
Finally, we redefine $\eta=0.1U/\gamma + 0.36$ entering in the effective
temperature $T^*$ of Eq.~(\ref{effective_temperature}) in order to correct the effect of the interactions at low temperatures.
This is somewhat similar to
Ref.~\onlinecite{Kurth:PRB:2016} where the smoothening of the step features
in the Coulomb blockade part of the functional had to be modified in the
Kondo regime $T\lesssim T_K$.

As a first test of this functional, we calculate self-consistent densities
at equilibrium. In Fig.~\ref{fig:densities} a) we plot the densities obtained
for different gate voltages as function of the temperature of
the leads $T=T_{L}=T_{R}$ for the strongly correlated case with $U/\gamma=8$
and compare with numerical renormalization group (NRG) results of
Ref.~\onlinecite{costi:PRB:2010}. Instead, in Fig.~\ref{fig:densities} b) we
show equilibrium densities as function of gate voltage for different
temperatures. The agreement of our i-DFT densities with the NRG ones is
excellent.

We now turn to the Seebeck coefficient. As first step we analyze the relative
magnitude of the KS Seebeck coefficient ($S_s$) and the xc correction
(see Eq.~\ref{linear_Seebeck_dft}) as a function of the gate voltage and
the correlation strength. In Fig.~\ref{fig:S_s_and_S_xc}, we can
see that, as expected, the xc contribution becomes dominant for almost any
temperature as $U/\gamma$ increases from 1 (Fig.~\ref{fig:S_s_and_S_xc}a)
to 8 (Fig.~\ref{fig:S_s_and_S_xc}d), but also for intermediate values,
$U/\gamma=3$, the two terms have a comparable magnitude for any value of the
gate voltage. Notice that, since both potential and temperature are evaluated
in units of $\gamma$, $S$ and $S_{xc}$ are dimensionless.
\begin{figure}
  \includegraphics[width=\linewidth]{S_s_and_S_xc.eps}
  \caption{Linear KS Seebeck coefficient $S_{s}$ and xc correction $S_{\rm xc}$
    as function of temperature for different gate voltages and
    correlation strengths $U/\gamma$. }
  \label{fig:S_s_and_S_xc}
\end{figure}
In Fig.~\ref{fig:S_K_T} we compare
our results with the NRG ones of Ref.~\onlinecite{costi:PRB:2010} for fixed
gate potential as a function of temperature. Again, similar to
Fig.~\ref{fig:S_s_and_S_xc}, the panels report calculated values from weak (a) to
strong correlations (d) in the dot. As expected we find a very good agreement
between i-DFT and NRG for $T\gtrsim T_{K}$. For lower temperatures, i-DFT
shows small discrepancies with respect to the reference result which
exhibits a different evolution of the local minimum of the Seebeck coefficient
when increasing the interaction.
\begin{figure}
  \includegraphics[width=\linewidth]{Seebeck_compare_NRG.eps}
  \caption{Comparison of the Seebeck coefficient obtained with i-DFT with the
    NRG results of Ref.~\onlinecite{costi:PRB:2010} as function of
    temperature for different gate voltages and correlation
    strengths $U/\gamma$.
  }
  \label{fig:S_K_T}
\end{figure}

In Fig.~\ref{fig:S_K_vg}, we show the Seebeck coefficient as function of the
gate voltage for different values of the temperature and again compare with
NRG results of Ref.~\onlinecite{costi:PRB:2010}. As already noticed above, for
low temperatures there are discrepancies at certain gate values although with
our i-DFT approach we manage to obtain the qualitative behaviour of the NRG
results. For $T/\gamma \gtrsim1$, on the other hand, the i-DFT results are in
excellent agreement with the NRG ones.

\begin{figure}
  \includegraphics[width=0.9\linewidth]{S_v_g.eps}
  \caption{Comparison of the Seebeck coefficient obtained with i-DFT with the
    NRG results of Ref.~\onlinecite{costi:PRB:2010}.$S$ is shown as function
    of the gate voltage for different temperatures and
    for strong correlations $U/\gamma=8$.
  }
  \label{fig:S_K_vg}
\end{figure}

While the main focus of the present work is on the Seebeck coefficient, one
can, of course, also calculate differential conductances from i-DFT. In
Fig.~\ref{fig:conductance_ph}, we show differential conductances for the SIAM
at the particle-hole symmetric point obtained with our present functional and
compare them with those obtained using the functional of
Ref.~\onlinecite{Kurth:PRB:2016} as well as with functional renormalization
group (fRG) results of Ref.~\onlinecite{Jakobs:PRB:2010}. The i-DFT results
with our present functional agree reasonably well with the reference fRG results
although some details like the overall shape of the side peaks seem to be
better captured by the functional of Ref.~\onlinecite{Kurth:PRB:2016}.
Finally, the differential conductance at zero bias has been calculated and
compared with both fRG of Ref.~\onlinecite{Jakobs:PRB:2010} and NRG of
Ref.~\onlinecite{Izumida:PSJ:2001} for different interaction
strengths obtaining very good agreements, as can be appreciated in
Fig.~\ref{fig:conductance_zb}.

\begin{figure}
  \includegraphics[width=0.9\linewidth]{G_ph.eps}
  \caption{Differential conductance $G_{\rm ph}$ at the particle hole symmetric
    point $v=-U/2$ for the SIAM as function of bias $V$ for
    $U/\gamma=3$. The i-DFT results obtained with the functional of
    Eq.~(\ref{functionals_prefactor}) are compared to those from
    Ref.~\onlinecite{Kurth:PRB:2016} and the fRG results of
    Ref.~\onlinecite{Jakobs:PRB:2010}. $G_{0}=1/\pi$ is the quantum of
    conductance.   }
  \label{fig:conductance_ph}
\end{figure}

\begin{figure}
  \includegraphics[width=\linewidth]{4_panel_G_ZB.eps}
  \caption{\label{fig:conductance_zb}
    Zero-bias differential conductance of i-DFT obtained
    with the functional of Eq.~(\ref{functionals_prefactor}) as function of
    the gate level $v$ for different values of $U/\gamma$. In panels
    a) and b) the results are compared to fRG ones from
    Ref.~\onlinecite{Jakobs:PRB:2010}, in panels c) and d) NRG results from
    Ref.~\onlinecite{Izumida:PSJ:2001} are used for comparison.  $G_{0}=1/\pi$
    is the quantum of conductance.
    }
\end{figure}

\section{Conclusions}

In this work we have extended the recently proposed density functional
framework for steady-state transport (i-DFT) to the situation when there is a
temperature gradient across the junction. As a direct consequence, we have
derived an exact expression for the Seebeck coefficient of the interacting
system as a sum of the KS Seebeck coefficient and a correction term related
to a derivative of the i-DFT xc bias functional.

For the SIAM we have constructed an approximation to the (H)xc functionals
both in the Coulomb blockade as well as in the Kondo regime. In the Coulomb
blockade regime we found that both Hxc gate and xc bias potential consist
of a sum or difference of two pieces, each of which depends only on the
temperature of one of the leads. This property allows us to recover an earlier,
approximate expression for the Seebeck coefficient in terms of purely DFT
quantities\cite{Yang:PRB:2016}.
We have compared the Seebeck coefficients for the SIAM obtained with our method
with those from NRG calculations reported in the literature. While our
parametrization by construction becomes exact at high temperatures
($T\gg T_K$), in the Kondo regime ($T\ll T_K$) the agreement is reasonable but
not perfect. However, i-DFT is numerically much cheaper than more
sophisticated many-body methods and extension to more complicated models
can also be relatively straightforward.

\acknowledgments
We gratefully acknowledge useful discussions with Florian Eich, David Jacob
and Gianluca Stefanucci.
We acknowledge funding by the grant ``Grupos Consolidados UPV/EHU del Gobierno
Vasco'' (IT1249-19) as well as the grant of the ``Ministerio de Economia y
Competividad (MINECO)'' (FIS2016-79464-P).


\section{{\large{}introduction}}

{\large{}A partial semigroup is a set with restricted binary operation
defined as,}{\large\par}
\begin{defn}
{\large{}\label{Defn 1} A partial semigroup is defined as a pair
$(S,\ast)$ where $\ast$ maps a subset of $S\times S$ to $S$ and
satisfies for all $a,b,c\in S$ , $(a\ast b)\ast c=a\ast(b\ast c)$
in the sense that if either side is defined, then so is the other
and they are equal.}{\large\par}
\end{defn}

{\large{}There are several notion of largeness of sets in partial
semigroup similar to semigroup arises from similar characterization
of the structure of Stone-\v{C}ech compactification of semigroup,
$\beta S$. The Stone-\v{C}ech compactification of a partial semigroup
contains an interesting subsemigroup, which gives us many important
notions of largeness of sets. }{\large\par}

{\large{}For a commutative semigroup $(S,+)$, the Stone-\v{C}ech
compactification, $\beta S$, is the collection of all ultrafilters
on $S$. Identifying the principal ultrafilters with the points of
$S$ we see that $S\subseteq\beta S$. Given$A\subseteq S$ let us
set,
\[
\overline{A}=\{p\in\beta S:\:A\in p\}.
\]
 Then the set $\{\overline{A}:\:A\subseteq S\}$ is a basis for a
topology on $\beta S$. The operation $'+'$ on $S$ can be extended
to the Stone-\v{C}ech compactification $\beta S$ of $S$ so that
$(\beta S,+)$ is a compact right topological semigroup (meaning that
for any $p\in\beta S$, the function $\rho_{p}:\beta S\rightarrow\beta S$
defined by $\rho_{p}(q)=q+p$ is continuous) with $S$ contained in
its topological center (meaning that for any $x\in S$, the function
$\lambda_{x}:\beta S\rightarrow\beta S$ defined by $\lambda_{x}(q)=x+q$
is continuous). Given $p,q\in\beta S$ and $A\subseteq S$, $A\in p+q$
if and only if $\{x\in S:-x+A\in q\}\in p$, where $-x+A=\{y\in S:x+y\in A\}$.}{\large\par}

{\large{}The following technical definitions are required,}{\large\par}
\begin{defn}
{\large{}\label{Defn 2} Let $\left(S,\ast\right)$ be a partial semigroup.}{\large\par}

{\large{}(a) For $s\in S$, $\varphi\left(s\right)=\left\{ t\in S:\:s\ast t\text{ is defined}\right\} $.}{\large\par}

{\large{}(b) For $H\in\mathcal{P}_{f}\left(S\right),\:\sigma\left(H\right)=\bigcap_{s\in H}\varphi\left(s\right)$.}{\large\par}

{\large{}(c) $\left(S,\ast\right)$ is adequate iff $\sigma\left(H\right)\neq\emptyset$
for all $H\in\mathcal{P}_{f}\left(S\right)$.}{\large\par}

{\large{}(d) $\delta S=\bigcap_{x\in S}\overline{\varphi\left(x\right)}=\bigcap_{H\in\mathcal{P}_{f}\left(S\right)}\overline{\sigma\left(H\right)}$.}{\large\par}
\end{defn}

{\large{}In fact, for a semigroup $S$, $\delta S=\beta S$ and adequacy
is needed in partial semigroup to guarantee that $\delta S\neq\emptyset$.
$(\delta S,+)$ is a compact right topological semigroup \cite[Theorem 2.10]{key-3}.
In particular, the combinatorially and algebraically defined large
sets are sometimes different for partial semigroups. Although, they
coincide for semigroups. In partial semigroup, each algebraically
defined large sets have a combinatorial version which is defined as
using a notions precede by \v{c}.}{\large\par}

{\large{}For details and recent advances on partial semigroup, one
can read \cite{key-2,key-4}.}{\large\par}
\begin{defn}
{\large{}\label{Definition 3} Let $(S,\ast)$ be a partial semigroup
and let $f$ be a sequence in $S$. Then $f$ is $adequate$ if and
only if}\\
{\large{}1. For each $F\in\mathcal{P}_{f}\left(\mathbb{N}\right)$,
$\prod_{t\in F}f(t)$ is defined.}\\
{\large{}2. For each $F\in\mathcal{P}_{f}\left(S\right)$, there exist
$m\in\mathbb{N}$, such that $FP\left(\langle f(t)\rangle_{t=m}^{\infty}\right)\subseteq\sigma(F)$}\\
{\large{}Define for an adequate partial semigroup $(S,\ast)$,
\[
\mathcal{F}=\left\{ f:f\,is\,an\,adequate\,sequence\,in\,S\right\}
\]
}{\large\par}
\end{defn}

{\large{}It has shown in \cite[Theorem 4.1]{key-4} that in countable
adequate partial semigroup $adequate\,sequences$ exists.}{\large\par}

{\large{}For an adequate partial semigroup we have these definitions
of $IP$ set both algebraically and combinatorially.}{\large\par}
\begin{defn}
{\large{}\label{Defn 4} \cite[Definition 5.3]{key-6} Let $\left(S,\ast\right)$
be an adequate partial semigroup and suppose $A\subseteq S$.}{\large\par}

{\large{}(a) $A$ is $IP$ if and only if there exists an idempotent
$p\in\delta S$ such that $A\in p$.}{\large\par}

{\large{}(b) $A$ is \v{c}-$IP$ (combinatorially $IP$) if and only
if there exists a sequence $\left\langle x_{n}\right\rangle _{n=1}^{\infty}$
in $S$ such that for all $F\in\mathcal{P}_{f}\left(\mathbb{N}\right)$,}\\
{\large{} $\prod_{n\in F}x_{n}$ is defined and $\prod_{n\in F}x_{n}\in A$.}{\large\par}
\end{defn}

{\large{}In \cite[Theorem 5.4]{key-6}, McLeod gave an example of
an \v{c}-$IP$ set which is not $IP$. A set is said to be $IP^{\star}$
if it intersects every $IP$ set, i.e, it belongs to every idempotent
$p\in\delta S$. }{\large\par}

\section{{\large{}proof of main theorem}}
\begin{lem}
{\large{}\label{Lemma 5} Let $(S,+)$ be countable adequate partial
semigroup then,
\[
\bigcap_{m=1}^{\infty}\overline{FS\left(\left\langle x_{n}\right\rangle _{n=m}^{\infty}\right)}\cap\delta S
\]
is a semigroup.}{\large\par}
\end{lem}

\begin{proof}
{\large{}Choose an adequate sequence $\left\langle x_{n}\right\rangle _{n=1}^{\infty}$
by \cite[Theorem 4.1]{key-4}. As for each $F\in\mathcal{P}_{f}\left(S\right)$,
there exist $m\in\mathbb{N}$, such that $FS\left(\langle x_{t}\rangle_{t=m}^{\infty}\right)\subseteq\sigma(F)$,
we have $FS\left(\langle x_{t}\rangle_{t=n}^{\infty}\right)\bigcap\sigma(H)\neq\emptyset$
for all $H\in\mathcal{P}_{f}\left(S\right)$ and $n\in\mathbb{N}$.
Now take the following set,
\[
B=\left\{ FS\left(\langle x_{t}\rangle_{t=n}^{\infty}\right)\bigcap\sigma(H):n\in\mathbb{N},H\in\mathcal{P}_{f}\left(S\right)\right\}
\]
Now claim is $B$ satiesfies finite intersection property. To see
this take any two $H,F\in\mathcal{P}_{f}\left(S\right)$ and $m,n\in\mathbb{N}$.
Then,
\begin{align*}
\left(FS\left(\langle x_{t}\rangle_{t=n}^{\infty}\right)\bigcap\sigma(H)\right)\bigcap\left(FS\left(\langle x_{t}\rangle_{t=m}^{\infty}\right)\bigcap\sigma(F)\right)\\
=FS\left(\langle x_{t}\rangle_{t=n}^{\infty}\right)\bigcap FS\left(\langle x_{t}\rangle_{t=m}^{\infty}\right)\bigcap\sigma(H\cup F)\neq\emptyset
\end{align*}
}{\large\par}

{\large{}The last line follows from \cite[Theorem 4.1]{key-4}.}{\large\par}

{\large{}Now as $B$ satiesfies finite intersection property, we have,}\\
{\large{} $\bigcap_{m=1}^{\infty}\overline{FS\left(\left\langle x_{n}\right\rangle _{n=m}^{\infty}\right)}\cap\delta S$
is a semigroup from \cite[Lemma 5.6]{key-6}.}{\large\par}
\end{proof}
\begin{fact}
{\large{}\label{Fact 6} As $\bigcap_{m=1}^{\infty}\overline{FS\left(\left\langle x_{n}\right\rangle _{n=m}^{\infty}\right)}\cap\delta S$
is a semigroup, we have an idempotent $p\in\bigcap_{m=1}^{\infty}\overline{FS\left(\left\langle x_{n}\right\rangle _{n=m}^{\infty}\right)}\cap\delta S$
by \cite[Theorem 2.5, page 40]{key-5}.}{\large\par}
\end{fact}

\begin{defn}
{\large{}\label{Definition 7} Let $\left\langle y_{n}\right\rangle _{n=1}^{\infty}$
be an $adequate\,sequence$ in an adequate commutative partial semigroup
$(S,+)$ and let $k,m\in\mathbb{N}$. Then $\left\langle x_{n}\right\rangle _{n=1}^{m}$
is a product subsystem of $FS\left(\left\langle y_{n}\right\rangle _{n=k}^{\infty}\right)$
if and only if there exists a sequence $\left\langle H_{n}\right\rangle _{n=1}^{m}$
in $\mathcal{P}_{f}\left(\mathbb{N}\right)$ such that}{\large\par}

{\large{}(a) $\min H_{1}\geq k$, }{\large\par}

{\large{}(b) $\max H_{n}<\min H_{n+1}$for each $n\in\left\{ 1,2,\ldots,m-1\right\} $
and}{\large\par}

{\large{}(c) $x_{n}=\sum_{t\in H_{n}}y_{t}$ for each $n\in\left\{ 1,2,\ldots,m\right\} $.}{\large\par}
\end{defn}

{\large{}Now we prove a result which will be useful to our work.}{\large\par}
\begin{thm}
{\large{}\label{Theorem 8} Let $\left(S_{i},+\right),\,i=1,2,\ldots,l$
be $l$ countable adequate commutative partial semigroups and $l\in\mathbb{N}\setminus\{1\}$
and let $\left\langle x_{i,n}\right\rangle _{n=1}^{\infty}$ are sequences
in $S_{i}$ for each $i\in\{1,2,\ldots,l\}$. Let $m,r\in\mathbb{N}$
and $\times_{i=1}^{l}S_{i}=\bigcup_{j=1}^{r}D_{j}$. Then there exists
$j\in\left\{ 1,2,\ldots,r\right\} $ and for each $i\in\left\{ 1,2,\ldots,l-1\right\} $,
there exists a product subsystem $\left\langle y_{i,n}\right\rangle _{n=1}^{m}$
of $FS\left(\left\langle x_{i,n}\right\rangle _{n=1}^{\infty}\right)$
and there exists a product subsystem $\left\langle y_{l,n}\right\rangle _{n=1}^{\infty}$
of $FS\left(\left\langle x_{l,n}\right\rangle _{n=1}^{\infty}\right)$
such that
\[
\left(\times_{i=1}^{l-1}FS\left(\left\langle y_{i,n}\right\rangle _{n=1}^{m}\right)\right)\times FS\left(\left\langle y_{l,n}\right\rangle _{n=1}^{\infty}\right)\subset D_{j}.
\]
}{\large\par}
\end{thm}

\begin{proof}
{\large{}For each $i\in\left\{ 1,2,\ldots,l\right\} $, from fact
\ref{Fact 6}, let $p_{i}$ be the idempotents with
\[
p_{i}\in\bigcap_{k=1}^{\infty}\overline{FS\left(\left\langle x_{i,n}\right\rangle _{n=k}^{\infty}\right)}
\]
 For $\left(y_{1},y_{2},\ldots,y_{i-1}\right)\in\times_{i=1}^{l-1}S_{i}$
and $j\in\left\{ 1,2,\ldots,r\right\} $, take,}\\
{\large{} $B_{l}\left(y_{1},y_{2},\ldots,y_{l-1},j\right)=\left\{ y\in S_{l}:\:\left(y_{1},y_{2},\ldots,y_{l-1},y\right)\in D_{j}\right\} $.}{\large\par}

{\large{}Now, given $t\in\left\{ 2,3,\ldots,l-1\right\} $, assume
that $B_{t+1}\left(y_{1},y_{2},\ldots,y_{t},j\right)$ has been defined
for each $\left(y_{1},y_{2},\ldots,y_{t}\right)\in\times_{i=1}^{t}S_{i}$
and each $j\in\left(1,2,\ldots,r\right)$. Given
\[
\left(y_{1},y_{2},\ldots,y_{t-1}\right)\in\times_{i=1}^{t-1}S_{i}\text{ and \ensuremath{j\in\left\{ 1,2,\ldots,r\right\} }},
\]
 let
\[
B_{t}\left(y_{1},y_{2},\ldots,y_{t-1},j\right)=\:\left\{ y\in S_{t}:\:B_{t+1}\left(y_{1},y_{2},\ldots,y_{t-1},y,j\right)\in p_{t+1}\right\} .
\]
}{\large\par}

{\large{}Finally, given that $B_{2}\left(x,j\right)$ has been defined
for each $x\in S_{1}$ and each $j\in\left\{ 1,2,\ldots,r\right\} $,
let $B_{1}\left(j\right)=\left\{ x\in S_{1}:\:B_{2}\left(x,j\right)\in p_{2}\right\} $.}\\
{\large{} We show by downward induction on $t$ that for each $t\in\left\{ 2,3,\ldots,l\right\} $
and each $\left(y_{1},y_{2},\ldots,y_{t-1}\right)\in\times_{i=1}^{t-1}S_{i}$,
\[
S_{t}=\cup_{j=1}^{r}B_{t}\left(y_{1},y_{2},\ldots,y_{t-1},j\right)
\]
 This is trivially true for $t=l$. }\\
{\large{}Assume $t\in\left\{ 2,3,\ldots,l-1\right\} $ and the statement
is true for $t+1$. }\\
{\large{}Let, $\left(y_{1},y_{2},\ldots,y_{t-1}\right)\in\times_{i=1}^{t-1}S_{i}$.
Given $y\in S_{t}$, one has that,
\[
S_{t+1}=\bigcup_{j=1}^{r}B_{t+1}\left(y_{1},y_{2},\ldots,y_{t-1},y,j\right).
\]
}{\large\par}

{\large{}Now pick $j\in\left\{ 1,2,\ldots,r\right\} $ such that $B_{t+1}\left(y_{1},y_{2},\ldots,y_{t-1},y,j\right)\in p_{t+1}$.
Then $y\in B_{t}\left(y_{1},y_{2},\ldots,y_{t-1},j\right)$.}{\large\par}

{\large{}Since for each $x\in S_{1},S_{2}=\cup_{j=1}^{r}B_{2}\left(x,j\right)$,
one sees similarly that $S_{1}=\cup_{j=1}^{r}B_{1}\left(j\right)$.
Pick $j\in\left\{ 1,2,\ldots,r\right\} $ such that $B_{1}\left(j\right)\in p_{1}$.
Pick a product subsystem $\left\langle y_{1,n}\right\rangle _{n=1}^{\infty}$
of $FS\left(\left\langle x_{1,n}\right\rangle _{n=1}^{\infty}\right)$
such that $FS\left(\left\langle y_{1,n}\right\rangle _{n=1}^{\infty}\right)\subseteq B_{1}\left(j\right)$.
Let $C_{2}=\cap\left\{ B_{2}\left(a,j\right):\:a\in FS\left(\left\langle y_{1,n}\right\rangle _{n=1}^{m}\right)\right\} $.
Since $FS\left(\left\langle y_{1,n}\right\rangle _{n=1}^{m}\right)$
is finite, we have $C_{2}\in p_{2}$ so pick a product subsystem $\left\langle y_{2,n}\right\rangle _{n=1}^{\infty}$
of $FS\left(\left\langle x_{2,n}\right\rangle _{n=1}^{\infty}\right)$
such that $FS\left(\left\langle y_{2,n}\right\rangle _{n=1}^{\infty}\right)\subseteq C_{2}$.
Let $t\in\left\{ 2,3,\ldots,l-1\right\} $ and assume $\left\langle y_{t,n}\right\rangle _{n=1}^{\infty}$
has been chosen. Let
\[
C_{t+1}=\bigcap\left\{ B_{t+1}\left(a_{1},a_{2},\ldots,a_{t},j\right):\:\left(a_{1},a_{2},\ldots,a_{t}\right)\in\times_{i=1}^{t}FS\left(\left\langle y_{i,n}\right\rangle _{n=1}^{m}\right)\right\} .
\]
}{\large\par}

{\large{}Then $C_{t+1}\in p_{t+1}$ so pick a product subsystem $\left\langle y_{t+1,n}\right\rangle _{n=1}^{\infty}$
of $FS\left(\left\langle x_{t+1,n}\right\rangle _{n=1}^{\infty}\right)$
such that $FS\left(\left\langle y_{t+1,n}\right\rangle _{n=1}^{\infty}\right)\subseteq C_{t+1}$.
Then, }{\large\par}

{\large{}
\[
\left(\times_{i=1}^{l-1}FS\left(\left\langle y_{i,n}\right\rangle _{n=1}^{m}\right)\right)\times FS\left(\left\langle y_{l,n}\right\rangle _{n=1}^{\infty}\right)\subset D_{j}.
\]
which proves the theorem.}{\large\par}
\end{proof}
{\large{}To show our main theorem, the following definition is needed,
which is a partial semigroup version of \cite[Definition 18.12 page 469]{key-5}.}{\large\par}
\begin{defn}
{\large{}\label{Definition 9} Let $\langle y_{n}\rangle_{n=1}^{\infty}$
be an $adequate\,sequence$ in an adequate commutative partial semigroup
$(S,+)$ and let $k,m\in\mathbb{N}$. Then $\langle x_{n}\rangle_{n=1}^{m}$
is a weak product subsystem of $\langle y_{n}\rangle_{n=k}^{\infty}$
if and only if there exists a sequence $\langle H_{n}\rangle_{n=1}^{m}$
in $\mathcal{P}_{f}(\mathbb{N})$ such that, }{\large\par}

{\large{}(a) $H_{n}\cap H_{n+1}=\emptyset$ for each $n\neq k$ in
$\{1,2,\ldots,m\}$ and }{\large\par}

{\large{}(b) $x_{n}=\underset{t\in H_{n}}{\sum}y_{t}$ for each $n\in\{1,2,\ldots,m\}$}{\large\par}
\end{defn}

{\large{}Recall that in a product subsystem one requires that $\max H_{n}<\min H_{n+1}$.}{\large\par}
\begin{lem}
{\large{}\label{Lemma 10} Let $l\in\mathbb{N}$ and for each $i\in\left\{ 1,2,\ldots,l\right\} $,
$S_{i}$ be countable adequate commutative partial semigroup and let
$\left\langle x_{i,n}\right\rangle _{n=1}^{\infty}$ be an $adequate\,sequence$
in $S_{i}$. Let,}{\large\par}

{\large{}
\[
\mathscr{L}=\left\{ p\in\delta\left(\times_{i=1}^{l}S_{i}\right):\text{ for each }A\in p\text{ and each }m,k\in\mathbb{N},\right.
\]
}{\large\par}

{\large{}
\[
\text{ there exists for each }i\in\left\{ 1,2,...,l\right\} \text{ a weak product subsystem }
\]
}{\large\par}

{\large{}
\[
\left.\text{\ensuremath{\left\langle x_{i,n}\right\rangle _{n=1}^{m}\text{ of }}\ensuremath{\ensuremath{\left\langle y_{i,n}\right\rangle _{n=k}^{\infty}}} such that }\times_{i=1}^{l}FS\left(\left\langle x_{i,n}\right\rangle _{n=1}^{m}\right)\subseteq A\right\}
\]
}{\large\par}

{\large{}Then $\mathscr{L}$ is a compact subsemigroup of $\delta\left(\times_{i=1}^{l}S_{i}\right)$.}{\large\par}
\end{lem}

\begin{proof}
{\large{}Since any product subsystem is also a weak product subsystem,
we have, from the assumption and theorem \ref{Theorem 8}, $\mathcal{L}\neq\emptyset$
. Since $\mathscr{L}$ is defined as the set of ultrafilters all of
whose members satisfy a given property, $\mathscr{L}$ is closed,
hence compact. To see that $\mathscr{L}$ is a semigroup, let $p,q\in\mathscr{L}$,
let $A\in p+q$ and let $m,k\in\mathbb{N}$. Then $\left\{ \bar{a}\in\times_{i=1}^{l}S_{i}:\:-\bar{a}+A\in q\right\} \in p$
so choose each $i\in\left\{ 1,2,\ldots,l\right\} $ a weak product
subsystem $\left\langle x_{i,n}\right\rangle _{n=1}^{m}$ of $FS\left(\left\langle y_{i,n}\right\rangle _{n=k}^{\infty}\right)$
such that
\[
\times_{i=1}^{l}FS\left(\left\langle x_{i,n}\right\rangle _{n=1}^{m}\right)\subseteq\left\{ \bar{a}\in\times_{i=1}^{l}S_{i}:\:-\bar{a}+A\in q\right\} .
\]
 Given $i\in\left\{ 1,2,\ldots,l\right\} $ and $n\in\left\{ 1,2,\ldots,m\right\} $,
pick $H_{i,n}\in\mathcal{P}_{f}\left(\mathbb{N}\right)$ with min
$H_{i,n}\geq k$ such that,}\\
{\large{} $x_{i,n}=\sum_{t\in H_{i,n}}y_{i,t}$ and if $1\leq n<s\leq m$,
then $H_{i,n}\cap H_{i,s}=\emptyset$. Let $r=\text{max }\left(\bigcup_{i=1}^{l}\bigcup_{n=1}^{m}H_{i,m}\right)+1$
and let
\[
B=\bigcap\left\{ -\bar{a}+A:\:\bar{a}\in\times_{i=1}^{l}FS\left(\left\langle x_{i,n}\right\rangle _{n=1}^{m}\right)\right\} .
\]
 Then $B\in q$ so choose for each $i\in\left\{ 1,2,\ldots,l\right\} $
a weak product subsystem $\left\langle z_{i,n}\right\rangle _{n=1}^{m}$
of $FS\left(\left\langle y_{i,n}\right\rangle _{n=r}^{\infty}\right)$
such that $\times_{i=1}^{l}FS\left(\left\langle z_{i,n}\right\rangle _{n=1}^{m}\right)\subseteq B$.
}\\
{\large{}Given $i\in\left\{ 1,2,\ldots,l\right\} $ and $n\in\left\{ 1,2,\ldots,m\right\} $,
pick $K_{i,n}\in\mathcal{P}_{f}\left(\mathbb{N}\right)$ with min
$K_{i,n}\geq r$ such that $z_{i,n}=\sum_{t\in K_{i,n}}y_{i,t}$ and
if $1\leq n<s\leq m$, then $K_{i,n}\cap K_{i,s}=\emptyset$. For
$i\in\left\{ 1,2,\ldots,l\right\} $ and $n\in\left\{ 1,2,\ldots,m\right\} $,
let $L_{i,n}=H_{i,n}\cup K_{i,n}$. Then
\[
\sum_{t\in L_{i,n}}y_{i,t}=\sum_{t\in H_{i,n}}y_{i,t}+\sum_{t\in K_{i,n}}y_{i,t}=x_{i,t}+z_{i,t}
\]
 and if $1\leq n<s\leq m$, then $L_{i,n}\cap L_{i,s}=\emptyset$
. Thus for each $i\in\left\{ 1,2,\ldots,l\right\} $, $\left\langle x_{i,n}+z_{i,n}\right\rangle _{n=1}^{m}$
is a weak product subsystem of $FS\left(\left\langle y_{i,n}\right\rangle _{n=k}^{\infty}\right)$.}{\large\par}

{\large{}Finally we claim that $\times_{i=1}^{l}FS\left(\left\langle x_{i,n}+z_{i,n}\right\rangle _{n=1}^{m}\right)\subseteq A$.
To this end let $\bar{c}\in\times_{i=1}^{l}FS\left(\left\langle x_{i,n}+z_{i,n}\right\rangle _{n=1}^{m}\right)$
be given. For each $i\in\left\{ 1,2,\ldots,l\right\} $, pick $F_{i}\subseteq\left\{ 1,2,\ldots,m\right\} $
such that $c_{i}=\sum_{t\in F_{i}}\left(x_{i,t}+z_{i,t}\right)$ and
let $a_{i}=\sum_{t\in F_{i}}x_{i,t}$ and $b_{i}=\sum_{t\in F_{i}}z_{i,t}$.
Then $\bar{b}\in\times_{i=1}^{l}FS\left(\left\langle z_{i,n}\right\rangle _{n=1}^{m}\right)$
so $\bar{b}\in B$. }\\
{\large{}Since $\bar{a}\in\times_{i=1}^{l}FS\left(\left\langle x_{i,n}\right\rangle _{n=1}^{m}\right)$
one has that $\bar{b}\in-\bar{a}+A$ so that $\bar{a}+\bar{b}\in A$.
Since each $S_{i}$ is commutative, we have for each $i\in\left\{ 1,2,\ldots,l\right\} $
that
\[
\bar{c}=\sum_{t\in F_{i}}\left(x_{i,t}+z_{i,t}\right)=\sum_{t\in F_{i}}x_{i,t}+\sum_{t\in F_{i}}z_{i,t}=\bar{a}.\bar{b}
\]
 as required. }{\large\par}
\end{proof}
{\large{}Now we will prove our main theorem.}{\large\par}
\begin{thm}
{\large{}\label{Theorem 11} Let $l\in\mathbb{N}$ and for each $i\in\left\{ 1,2,\ldots,l\right\} $,
let $S_{i}$ be countable adequate commutative partial semigroup and
let $\left\langle y_{i,n}\right\rangle _{n=1}^{\infty}$ be a sequence
in $S_{i}$. Let $C$ be an $IP^{*}$ set in $\times_{i=1}^{l}S_{i}$,
and let $m\in\mathbb{N}$. Then for each $i\in\left\{ 1,2,\ldots,l\right\} $
there is a weak product subsystem $\left\langle x_{i,n}\right\rangle _{n=1}^{m}$
of $FS\left(\left\langle y_{i,n}\right\rangle _{n=1}^{\infty}\right)$
such that $\times_{i=1}^{l}FS\left(\left\langle x_{i,n}\right\rangle _{n=1}^{m}\right)\subseteq C$. }{\large\par}
\end{thm}

\begin{proof}
{\large{}Let $\mathscr{L}$ be as in Lemma \ref{Lemma 10}. Then $\mathscr{L}$
is a compact subsemigroup of $\delta\left(\times_{i=1}^{l}S_{i}\right)$.
So there is an idempotent $p\in\mathscr{L}$. Let $C$ be an be an
$IP^{*}$ set in $\times_{i=1}^{l}S_{i}$. Hence $C\in p$. Thus by
the definition of $\mathscr{L}$ for each $i\in\left\{ 1,2,\ldots,l\right\} $,
there is a weak product subsystem $\left\langle x_{i,n}\right\rangle _{n=1}^{m}$
of $FS\left(\left\langle y_{i,n}\right\rangle _{n=1}^{\infty}\right)$
such that $\times_{i=1}^{l}FP\left(\left\langle x_{i,n}\right\rangle _{n=1}^{m}\right)\subseteq C$.}{\large\par}

{\large{}This completes the proof.}{\large\par}
\end{proof}
\textbf{\large{}Acknowledgment: }{\large{}The author thanks to Dibyendu
De for his constant inspiration to do this project.}{\large\par}


\section{Introduction}
\label{introduction}
The probabilistic method uses probability theory to prove existence of a non-random object. Typically, an appropriate probability measure is defined on a suitable space consisting of all objects under consideration. If the probability of an event is shown to be non-zero, then that event must be non-empty (as a set). In particular, if such an event is defined in terms of the objects satisfying certain properties, then this proves the existence of such objects. Though the probabilistic method was initially used primarily in combinatorics, it has since been refined and used in a number of other areas, such as number theory, linear algebra, real analysis and computer science. So many different ways of using probability in these areas have been found that it is now impossible to narrow the probabilistic method down to a few techniques of proof. In this paper, we will focus on one specific technique that exploits restrictions on interdependence of certain events to guarantee the possibility of avoiding all those events. The main result used in this approach is called the Lov\'asz Local Lemma. The simplest form of the result was first introduced by Erd\H{o}s and Lov\'asz to prove results on hypergraph coloring \cite{Erdos/Lovasz}. The interested reader may refer to \cite{Alon/Spencer} for a thorough treatment of other techniques of the probabilistic method.

We will first prove a general version of the lemma as stated in \cite{Lu/Szekely}. Our proof will be a modification of the proof of a slightly weaker form of the lemma in \cite{Alon/Spencer}. Unlike the latter form, the version of Lovasz Local Lemma that we will consider works even if there is \textbf{no} independence among the events. This version is sometimes called the Lopsided Lovasz Local Lemma. It was first introduced by Erd\H{o}s and Spencer in \cite{Erdos/Spencer} to prove a result on Latin transversals. After giving a proof of the lemma, we will describe its applications in hypergraph packings using the machinery of negative dependency graphs on the space of random injections developed in \cite{Lu/Szekely}. We will finally use this new machinery to give a proof of a slightly stronger form of the result on Latin transversals from \cite{Erdos/Spencer}.

\section{The Lemma}
\label{The Lemma}
We first introduce the basic concepts needed from probability and graph theory. A \textbf{probability space} is a triple containing a set, a sigma algebra on that set, and a measure defined on that sigma algebra that assigns the value 1 to the original set. Throughout this section, the probability space is $(\Omega, \mathcal{F}, P)$. Elements of the sigma algebra $\mathcal{F}$ are called the \textbf{events} of the space. A \textbf{Boolean combination} of finitely many events is an element in the smallest algebra generated by these events. Two events $A$ and $B$ are said to be independent if $P(A \cap B) = P(A)P(B)$. A finite collection of events is called \textbf{mutually independent} if any event in that collection is independent of any Boolean combination of the other events in that collection. If $A$ and $B$ are events such that $P(B) \neq 0$, then the \textbf{conditional probability} of $A$ given $B$ is defined as $P(A|B) := \frac{P(A \cap B)}{P(B)}$. The probability measures that we will consider in later sections will always be defined on the sigma algebras of power sets of finite sets. Unless otherwise specified, these measures will always be the \textbf{uniform probability measure}, that is, they will assign the same non-zero probability to all singleton sets in the space.

A \textbf{graph} $G$ is a pair $(V,E)$, where $V$ is a set and $E$ is a collection of $2$-subsets of $V$, that is, $E$ contains subsets of $V$ that have cardinality $2$. The elements of $V$ are called the \textbf{vertices} of the graph $G$, and the elements of $E$ are called the \textbf{edges} of the graph $G$. A vertex of a graph is said to be \textbf{incident} on an edge, if the edge contains that vertex. For a vertex $v$ of a graph $(V,E)$, let $J_v := \{w \in V: \{v,w\} \in E\}$. The number of edges that contain a vertex is called the \textbf{degree} of that vertex. Hence, the degree of a vertex $v$ is equal to the cardinality of $J_v$. The maximum degree of vertices in a graph is called the \textbf{degree} of the graph.

A graph $G$ on $[n] := \{1,\ldots,n\}$ is called a \textbf{negative dependency graph} for the events $A_1, \ldots , A_n$ if, for any $i \in [n]$ and any $S \subseteq {J_i}^c$ with $P(\cap_{j \in S}{A_j}^c) > 0$, we have
\begin{equation}\label{first cond}
P(A_i | \cap_{j \in S}{A_j}^c) \leq P(A_i).
\end{equation}

Note that this is trivially satisfied if $P(A_i) = 0$, and if $P(A_i) > 0$, then the above condition is equivalent to the condition
\begin{equation}\label{second cond}
P(\cap_{j \in S}{A_j}^c | A_i) \leq P(\cap_{j \in S}{A_j}^c) \text{ for any such } S \subseteq J_i.
\end{equation}

We are now ready to state the Lovasz Local Lemma.
\\
\begin{lemma}[Lov\'asz Local Lemma]~\\
Suppose that $A_1, \ldots, A_n$ are events and that $G$ is a negative dependency graph for these events. Suppose that $x_1, \ldots, x_n \in [0,1)$ are such that
\begin{equation}\label{LLL1}
P(A_i) \leq x_i \cdot \prod_{j \in J_i}(1 - x_j),
\end{equation}
then $P(\cap_{i=1}^{n}{A_i}^c) \geq \prod_{i = 1}^{n} (1-x_i) > 0$.
\end{lemma}
The following immediate corollary will be useful in our applications.
\begin{corollary} Suppose that $A_1, \ldots, A_n$ are events and let $G$ be a negative dependency graph for these events. Suppose that the degree of any vertex in $G$ is at most $d$. If $p \in [0,1)$ is such that $P(A_i) \leq p$ for all $i \in [n]$ and $ep(d+1) \leq 1$, then $P(\cap_{i=1}^{n}{A_i}^c) > 0$.
\end{corollary}
\begin{proof}
Let $x_i = \frac{1}{d+1}$ for each $i \in [n]$. The inequality $ep(d+1) \leq 1$ implies that for any $i$,
\vspace{-2mm}
\begin{equation*}
P(A_i) \leq p \leq \frac{1}{e(d+1)} \leq x_i \cdot \frac{1}{e} \leq x_i \cdot \left(1 - \frac{1}{d+1}\right)^d \leq x_i \cdot \left(1 - \frac{1}{d+1}\right)^{|J_i|},
\end{equation*}
since the function $x \mapsto \left(1 - \frac{1}{x+1}\right)^x$ is decreasing on $(0, \infty)$ and converges to $\frac{1}{e}$ as $x \rightarrow \infty$. Hence Lemma 2.1 applies.
\end{proof}
Before giving a proof of the lemma, suppose that $G$ is a graph on $[n]$ such that for any $i \in [n]$, the event $A_i$ is mutually independent of all ${A_j}$ such that $\{i,j\} \notin E(G)$. Such a graph is called a \textbf{dependency graph} for the events $A_1, \ldots, A_n$. A dependency graph clearly also satisfies the conditions of being a negative dependency graph. Many applications of Lemma 2.1 and Lemma 2.2 deal with the setting of a dependency graph.
\begin{proof}[Proof of Lemma 2.1]
For each $k \in [n]$, let $B_k = \cap_{i=1}^{k}{A_i}^c$. We will show by induction on $k$ that
\begin{equation}\label{hypothesis}
P(B_k) \geq \prod_{i = 1}^{k} (1-x_i) > 0.
\end{equation}
Note that
\begin{align*}
\vspace{-2mm}
P(B_1) = P({A_1}^c) = 1 - P(A_1) \geq 1 - x_1 \prod_{j \in J_i}(1 - x_j) \geq 1 - x_1 > 0 .
\end{align*}
So the result is true for $k = 1$.
Suppose it is true for each $k \in \{1, \ldots, m-1\}$, where $m \in \{2, \ldots, n\}$.
Then, we have $P(B_{m-1}) \neq 0$, so that
\begin{align*}
P(B_m) &= P({A_m}^c \cap (\cap_{i = 1}^{m-1}{A_i}^c)) \\
&= P(\cap_{i = 1}^{m-1}{A_i}^c) - P({A_m} \cap (\cap_{i = 1}^{m-1}{A_i}^c)) \\
&= P(B_{m-1}) - P(A_m \cap B_{m-1}) \\
&= P(B_{m-1})\cdot\left[1 - \frac{P(A_m \cap B_{m-1})}{P(B_{m-1})}\right]\\
&\geq \left[\prod_{i=1}^{m-1}(1-x_i)\right]\cdot\left[1 - P(A_m | B_{m-1})\right].
\end{align*}
Thus to complete the proof, it suffices to show that $1 - P(A_m | B_{m-1}) \geq 1 - x_m$, or equivalently, that $P(A_m | B_{m-1}) \leq x_m$.
To show this, we will prove the following stronger claim:

\begin{claim}
Let $S$ be a proper subset of $[n]$ such that $P\left(\cap_{j \in S}{A_j}^c\right) > 0$. Then, for any $i \notin S$,
\vspace{-3mm}
\begin{equation}\label{second induct}
\vspace{-7mm}
P\left(A_i | \cap_{j \in S}{A_j}^c\right) \leq x_i.
\end{equation}
\end{claim}
\begin{claimproof}
We prove this by induction on $|S|$. If $|S| = 0$, then $P(A_i|\cap_{j \in S}{A_j}^c) = P(A_i | \Omega) = P(A_i) \leq x_i \cdot \prod_{j \in J_i}(1 - x_j) \leq x_i$. Hence the hypothesis is true when $|S| = 0$. Suppose that it is true whenever $|S| \leq s - 1$, where $s \in \{1, \ldots, n-1\}$. Let $S \subseteq [n]$ be a set with $|S| = s$ and $P(\cap_{j \in S}{A_j}^c) > 0$. Let $i \notin S$ and define
\vspace{-2mm}
\begin{equation*}
\vspace{-2mm}
S_1 = \{j \in S: \{i,j\} \in E(G)\} \text{ and } S_2 = \{j \in S: \{i,j\} \notin E(G)\}.
\end{equation*}
If $S_1 = \emptyset$, then $P\left(A_i | \cap_{j \in S}{A_j}^c\right) \leq P(A_i) \leq x_i$, by definition of negative dependency graphs. So suppose $|S_1| \geq 1, \text{ say } S_1 = \{j_1, \ldots, j_r\}$, where $1 \leq r \leq s$. Note that $P(\cap_{j \in S}{A_j}^c) > 0 \text{ implies } P(\cap_{j \in S'}{A_j}^c) > 0 \text{ for any } S' \subseteq S$. Hence we have
\begin{align*}
P(A_i | \cap_{j \in S}{A_j}^c) &= \frac{\left(\frac{P(A_i \cap (\cap_{j \in S_1}{A_j}^c) \cap (\cap_{j \in S_2}{A_j}^c))}{P(\cap_{j \in S_2}{A_j}^c)}\right)}{\left(\frac{P((\cap_{j \in S_1}{A_j}^c) \cap (\cap_{j \in S_2}{A_j}^c))}{P(\cap_{j \in S_2}{A_j}^c)}\right)} \\
&\leq \frac{P(A_i | \cap_{j \in S_2} {A_j}^c)}{P(\cap_{j \in S_1} {A_j}^c | \cap_{j \in S_2} {A_j}^c)} \\
&\leq \frac{x_i \prod_{j \in S_1}(1 - x_j)}{P(\cap_{j \in S_1} {A_j}^c | \cap_{j \in S_2} {A_j}^c)},
\end{align*}
where we have used \eqref{first cond} and \eqref{LLL1} on the last line.

Hence it suffices to show that $\prod_{j \in S_1}(1 - x_j) \leq P(\cap_{j \in S_1} {A_j}^c | \cap_{j \in S_2} {A_j}^c)$.
Assuming that $[0] = \emptyset$, a telescopic product argument gives
\begin{align*}
P(\cap_{j \in S_1} {A_j}^c | \cap_{j \in S_2} {A_j}^c) &= \frac{P((\cap_{k \in [r]} {A_{j_k}}^c) \cap (\cap_{j \in S_2} {A_j}^c))}{P(\cap_{j \in S_2} {A_j}^c)} \\
&= \prod_{t=1}^{r} \frac{P((\cap_{k \in [t]} {A_{j_k}}^c) \cap (\cap_{j \in S_2} {A_j}^c))}{P((\cap_{k \in [t-1]} {A_{j_k}}^c) \cap (\cap_{j \in S_2} {A_j}^c))}\\
&= \prod_{t=1}^{r} P({A_{j_t}}^c | \cap_{j \in S_2 \cup \{j_1, \ldots, j_{t-1}\}}{A_j}^c) \\
&= \prod_{t=1}^{r}\left( 1 - P({A_{j_t}} | \cap_{j \in S_2 \cup \{j_1, \ldots, j_{t-1}\}}{A_j}^c) \right) \\
&\geq \prod_{t=1}^{r}(1 - x_{j_t}) = \prod_{j \in S_1}(1 - x_j),
\end{align*}
completing the proof. \qedhere
\end{claimproof}
\end{proof}

\section{Construction of a negative dependency graph for random injections}
In this section, we will construct a negative dependency graph for a collection of events in the space of random injections from one set to another. This construction will then be used to prove results on hypergraph packing and Latin transversals using the Lov\'asz Local Lemma. The construction is from \cite{Lu/Szekely}.

Let $U$ and $V$ be two finite sets with $|U| \leq |V|$. Let $\Omega = I(U,V)$ denote the set of all injective maps from $U$ to $V$, equipped with a uniform probability measure. We define a \text{matching} to be a triple $(S, T, f)$ satisfying:
\begin{enumerate}
\item[(i)] $S, T \text{ are subsets of } U, V \text{ respectively, and}$
\item[(ii)] $f: S \rightarrow T \text{ is a bijection.}$
\end{enumerate}

We denote the set of all such matchings by $M(U,V)$. By a canonical identification, we have $\Omega = I(U,V) \subseteq M(U,V)$. For any permutation $\rho: V \rightarrow V$ of $V$, define the map $\pi_\rho : M(U,V) \rightarrow M(U,V)$ by $(\pi_\rho(g))(u) = \rho(g(u)) \text{ for all } u \in \text{Domain}(g)$. Hence $\pi_\rho(g) = \rho \circ g$. This map induces a natural map on the set of matchings by defining $\pi_\rho((S, T, g)) = (S, \rho(T), g')$, where $g'(u) = \rho(g(u)) \text{ for all } u \in S$. It is easy to see that $\pi_\rho: M(U,V) \rightarrow M(U,V)$ is an injection for each permutation $\rho$ of $V$.

Two matchings $(S_1, T_1, f_1)$ and $(S_2, T_2, f_2)$ are said to \textbf{conflict} each other if either $f_1(k) \neq f_2(k) \text{ for some } k \in S_1 \cap S_2$ or if $f_1^{-1}(k) \neq f_2^{-1}(k)
$ for some $k \in T_1 \cap T_2$. Thus, two non-conflicting matchings can be naturally combined to get a ``bigger'' matching.

For a given matching $(S, T, f)$, we define the event
\begin{equation*}
A_{S,T,f} = \{\sigma \in \Omega: \sigma(i) = f(i) ~\forall ~ i \in S\}.
\end{equation*}
Thus, $A_{S,T,f}$ contains injections from $U$ to $V$ that extend the map $f$. An event is said to be \textbf{canonical} if $A = A_{S,T,f}$ for some matching $(S,T,f)$. It is not very difficult to see that such a canonical representation for an event is unique, except when $|U| = |V|$ and $|A| = 1$. Due to this property of having unique non-trivial representations, the notion of conflicting matchings can be extended to canonical events in a well-defined way. We say that two canonical events conflict each other if their associated matchings conflict. We now make some immediate observations.

\begin{remark}
Two canonical events conflict if and only if they are disjoint.
\end{remark}
\begin{remark}
If $\rho : V \rightarrow V$ is any permutation, and $(S,T,f)$ is a matching, then $\pi_\rho(A_{S,T,f}) = A_{S,\rho(T), f'}$, where $f': S \rightarrow \rho(T)$ is defined by $f'(u) = \rho(f(u))$, as before.
\end{remark}
We now state the result constructing a negative dependency graph for a collection of canonical events. The reader can refer to \cite{Lu/Szekely} for the technical proof.

\begin{theorem}
Let $A_1, \ldots, A_n$ be a collection of canonical events in $\Omega = I(U,V)$. Let $G$ be the graph on $[n]$ with the edge-set
\begin{equation*}
E(G) = \{\{i,j\}: A_i \text{ and } A_j \text{ conflict}\}.
\end{equation*}
Then $G$ is a negative dependency graph for the events $A_1, \ldots A_n$.
\end{theorem}

\section{Applications to packing of hypergraphs}
The negative dependency graph constructed in the previous section can be used in many situations where the events that need to be avoided can be identified with canonical events in a space of injections. In this section, we will demonstrate this with some results on hypergraphs, and we will continue this theme in the next section that covers a result on existence of Latin transversals. The results in this section are from \cite{Lu/Szekely}.

Recall that a hypergraph $H$ is a pair $(V(H), E(H))$ where $V(H)$ is a collection of points that we call the \textit{vertices} of $H$, and $E(H)$ is a collection of subsets of $V(H)$ called \textit{edges} of $H$. A hypergraph is called $\mathbf{r}$\textbf{-uniform} if all of its edges have cardinality equal to $r$. The \textbf{degree} of a vertex is defined as the number of edges that contain that vertex. Thus the \textbf{complete} $r$\textbf{-uniform hypergraph}, denoted $K_n^{(r)}$, is the hypergraph on a set of $n$ vertices whose edges are precisely all $r$-subsets of the vertex-set. A hypergraph $G$ is called a \textbf{subhypergraph} of a hypergraph $H$ if $V(G)$ is a subset of $V(H)$, and $E(G)$ is a subset of the collection of all edges of $H$ that contain elements from $V(G)$.

We say that a collection of $r$-uniform hypergraphs $H_1, \ldots, H_k$ can be \textbf{packed into} an $r$-uniform hypergraph $H$, if there exist injections of $V(H_1) \ldots, V(H_k)$ into $V(H)$ such that the natural images of edge-sets are disjoint. Two hypergraphs $H_1$ and $H_2$ are called \textbf{isomorphic} if there is a bijection from $V(H_1)$ to $V(H_2)$ such that the natural image of the edge-set of $H_1$ coincides with the edge-set of $H_2$. For two $r$-uniform hypergraphs $H$ and $G$, we say that $H$ has a \textbf{perfect} $\mathbf{G}$\textbf{-packing}, if there exist vertex-disjoint hypergraphs $G_1, \ldots, G_k$ of $H$, each isomorphic to $G$, such that the sets $V(G_1), \ldots, V(G_k)$ partition $V(H)$. An obvious necessary condition for $H$ to have a perfect $G$-packing is for $|V(G)|$ to divide $|V(H)|$. We will derive a sufficient condition after we prove the following theorem on packing into complete $r$-uniform hypergraphs.
\vspace{-1mm}
\begin{theorem}
For each $i \in \{1,2\}$ let $H_i$ be an $r$-uniform hypergraph with $m_i$ edges such that each edge in $H_i$ intersects at most $d_i$ other edges of $H_i$. If $(d_1 + 1)m_2 + (d_2 + 1)m_1 < \frac{1}{e}\binom{n}{r}$, then $H_1$ and $H_2$ can be packed into $K_n^{(r)}$.
\end{theorem}
\begin{proof}
Without loss of generality, we assume that $H_2$ is given as a subhypergraph  of $K_n^{(r)}$. Let $U$ be the vertex-set of $H_1$, and let $V$ be that of $K_n^{(r)}$. We consider the probability space $\Omega = I(U,V)$ with uniform probability measure. We are following the notation of Section 3. Hence, $\Omega$ is just the set of all injections from $U$ to $V$, each injection having the same probability of occurring. It is clear that $H_1$ can be embedded into $K_n^{(r)}$ in a way that none of the edges of $H_2$ coincide with image of an edge of $H_1$ if none of the events $A_{F_1,F_2,\phi}$ (where $F_1, F_2$ are edges of $H_1, H_2$ respectively, and $\phi: F_1 \rightarrow F_2$ is a bijection) happen. Define $\mathcal{A} = \{A_{F_1,F_2, \phi} : F_1 \in E(H_1), F_2 \in E(H_2), \phi : F_1 \rightarrow F_2 \text{ is a bijection}\}$. We have the negative dependency graph $G$ for these events as described in the previous section.

Let $|U| = m$. Then, the number of injections from $U $ to $V$ is clearly equal to $\binom{n}{m} \cdot m!$. Now fix edges $F_1$, $F_2$ of $H_1, H_2$ respectively and a bijection $\phi: F_1 \rightarrow F_2$. The number of elements in the event $A_{F_1,F_2,\phi}$ is $\binom{n-r}{m-r} \cdot (m-r)!$. Indeed, the action of any map in this event is already determined on the $r$ elements of $F_1$, and the remaining $(m-r)$ elements of $U$ can be mapped injectively into the remaining $(n-r)$ elements of $V$ in so many ways. Hence,
\begin{align*}
P(A_{F_1, F_2, \phi}) = \frac{|A_{F_1, F_2, \phi}|}{|\Omega|} = \frac{\binom{n-r}{m-r} \cdot (m-r)!}{\binom{n}{m} \cdot m!} = \frac{1}{r! \binom{n}{r}} = p \text{ (say)}.
\end{align*}
Now $A_{F_1,F_2,\phi}$ conflicts with another canonical event $A_{F_1',F_2',\phi'}$ if and only if one of the following happens:
\begin{enumerate}
\item[(i)] $F_1 \cap F_1' = \emptyset$ and $F_2 \cap F_2' \neq \emptyset$.
\item[(ii)]$F_1 \cap F_1' \neq \emptyset$ and $\phi(x) = \phi'(x)$ for some $x \in F_1 \cap F_1'$.
\end{enumerate}
Let $c_1$ denote the number of canonical events $A_{F_1',F_2',\phi'}$ that conflict with $A_{F_1,F_2,\phi}$ due to (i), and let $c_2$ denote the corresponding number due to (ii). Simple counting arguments show that
\begin{align*}
c_1 \leq m_1 (d_2 + 1) r! - 1 \text{ and } c_2 \leq (d_1 + 1) m_2 r! - 1.
\end{align*}
Hence, the degree $d$ of the negative dependency graph $G$ satisfies the inequality $d \leq c_1 + c_2 \leq r![(d_1 + 1)m_2 + (d_2 + 1)m_1] - 1$. Then,
\begin{align*}
ep(d+1) \leq e \frac{1}{r! \binom{n}{r}} r![(d_1 + 1)m_2 + (d_2 + 1)m_1] < 1 \text{ by hypothesis.}
\end{align*}
Hence, by Lemma 2.2, $P(\cap_{A \in \mathcal{A}}A) >0$, which implies that $\cap_{A \in \mathcal{A}}A \neq \emptyset$, as desired.
\end{proof}

Using this result, we can now prove the following sufficient condition for existence of a perfect $G$-packing.

\begin{theorem}
Suppose $G$ and $H$ are two $r$-uniform hypergraphs that satisfy the following:
\begin{enumerate}
\item[(i)] $G$ has $s$ vertices, $H$ has $n$ vertices, and $s$ divides $n$.
\item[(ii)] $G$ has $m$ edges and each edge in $G$ intersects at most $d$ other edges of $G$.
\item[(iii)] Each vertex of $H$ has degree greater than or equal to $(1-x)\binom{n-1}{r-1}$ for some number $x$.
\end{enumerate}
If $x < \frac{1}{e(d + 1 + r^2\frac{m}{s})}$, then $H$ has a perfect $G$-packing.
\end{theorem}
\begin{proof}
Let $H_1$ be the union of $\frac{n}{s}$ vertex-disjoint copies of $G$. Let $H_2$ be the complement $r$-uniform hypergraph of $H$; that is, $V(H_2) = V(H_1)$ and $E(H_2)$ consists of all $r$-subsets of $V(H)$ that are not edges of $H$. It is not very difficult to see that $H$ has a perfect $G$-packing if and only if $H_1$ and $H_2$ can be packed into $K_n^{(r)}$. Following the notation of the previous theorem, we have,
\begin{align}\label{first data}
d_1 = d \text{ and } m_1 = |E(H_1)| = \frac{n}{s}|E(G)| = \frac{nm}{s}.
\end{align}
Now, condition (iii) implies that the degree of any vertex in $H$ is at least $(1-x)\binom{n-1}{r-1}$. Also, given an element of $V(H)$, there are $\binom{n-1}{r-1}$ $r$-subsets of $V(H)$ containing that vertex. Hence the degree of any vertex in $H_2$ is at most $\binom{n-1}{r-1} - (1-x)\binom{n-1}{r-1} = x \cdot \binom{n-1}{r-1}$. Hence, for an edge $F$ of $H_2$, the number of other edges that intersect $H$ is at most equal to $\sum_{v \in F}(d_{H_2}(v) - 1) = r[x \binom{n-1}{r-1} - 1] \leq rx \binom{n-1}{r-1} - 1$, where $d_{H_2}(v)$ denotes the degree of $v$ in $H_2$. Since this is valid for any edge of $H_2$, we have
\begin{equation}\label{second data}
d_2 \leq rx \binom{n-1}{r-1} - 1.
\end{equation}
Also, we have
\vspace{-2mm}
\begin{align*}
|E(H)| &\geq \sum_{v \in V(H)} d_{H}(v) \geq n(1-x)\binom{n-1}{r-1} = r(1-x)\binom{n}{r}\\
&\geq (1-x)\binom{n}{r}.
\end{align*}
Hence, we get
\vspace{-2mm}
\begin{align}\label{third data}
m_2 = |E(H_2)| = \binom{n}{r} - |E(H)| \leq \binom{n}{r} - (1-x)\binom{n}{r} = x \binom{n}{r}.
\end{align}
From, \eqref{first data}, \eqref{second data}, and \eqref{third data}, we have
\begin{align*}
(d_1 + 1)m_2 + (d_2 + 1)m_1 &\leq (d+1)x\binom{n}{r} + rx\binom{n-1}{r-1}\cdot\frac{nm}{s} \\
&\leq \binom{n}{r} \left[ d+1 + \frac{r^2m}{s}\right]x \\
&\leq  \frac{1}{e} \binom{n}{r}, \text{ by hypothesis.}
\end{align*}
Hence Theorem 4.1 applies, completing the proof.
\end{proof}

If $m=1$ (so that $d=0$ and $s=r$), then $G$ can be viewed as a single edge of $H$, and so a perfect $G$-packing of $H$ amounts to a partition of vertices of $H$ by edges of $H$. If such a partition exists, we say that $H$ has a \textbf{perfect matching}. In the further special case when $r = 2$, we get perfect matchings of graphs. Hence we have the following results.
\begin{corollary}
Suppose that $r$ divides $n$. If the degree of each vertex in an $r$-uniform hypergraph $H$ on $n$ vertices is at least $(1 - \frac{1}{e(1+r)})\binom{n-1}{r-1}$, then $H$ has a perfect matching.
\end{corollary}

\begin{corollary}
If the degree of any vertex in a graph $G$ is at least $\frac{(3e-1)(n-1)}{3e}$, then $G$ has a perfect matching.
\end{corollary}

\section{A result on Latin transversals}
Let $A = ((a_{i,j}))$ be an $(n \times n)$ matrix. A permutation $\pi$ of $[n]$ is called a \textbf{Latin transversal} of $A$ if the entries $a_{i, \pi(i)}$ for $i \in [n]$ are all distinct. The Lopsided Lov\'asz Local Lemma was initially introduced in \cite{Erdos/Spencer} to obtain a sufficient condition for existence of Latin transversals. We will use the new terminology built in Section 3 to get a slightly improved version of their result.

\begin{theorem}
Suppose $k \leq \frac{n-1}{4e}$, and suppose that no element appears in more than $k$ entries of $A$. Then $A$ has a Latin transversal.
\vspace{-1mm}
\end{theorem}
\begin{proof}
Let $\Omega = I([n],[n])$ with uniform probability measure. Hence, $\Omega$ is just the set of all permutations of $[n]$, so that $|\Omega| = n!$. Let $\mathcal{B} = \{(\{i,i'\},\{j,j'\}): i < i', j \neq j', a_{i,j} = a_{i',j'}\}$. If $I = \{i, i'\}, J = \{j,j'\}$ are such that $(I,J) \in \mathcal{B}$ with $i < i'$ and $a_{i,j} = a_{i',j'}$, then define $\pi_{(I,J)} : I \rightarrow J$ by $\pi_{(I,J)}(i) = j$, and $\pi_{(I,J)}(i') = j'$. It is not too difficult to see that there is a Latin transversal for $A$ if and only if there is a permutation that is not an element of $A_{I,J,\pi_{(I,J)}}$ for any $(I,J) \in \mathcal{B}$. Hence it suffices to show that $P(\cap_{(I,J) \in \mathcal{B}}{A_{I,J, \pi_{I,J}}}^c) > 0$.

Let $\mathcal{A} = \{A_{I,J,\pi_{(I,J)}} : (I,J) \in \mathcal{B}\}$. Let $G$ be the negative dependency graph for these canonical events, as constructed in Section 4. Let $d$ be the maximum degree of a vertex of $G$, and suppose that it is the degree of the vertex corresponding to the event $A_{I,J,\pi_{(I,J)}}$. Note that for $(I_1,J_1) \in \mathcal{B}\backslash\{(I,J)\}$, $A_{I,J,\pi_{(I,J)}}$ can possibly conflict with $A_{I',J',\pi_{(I',J')}}$ only if $I \cap I' \neq \emptyset$ or $J \cap J' \neq \emptyset$. For such a tuple $(I_1, J_1)$ with $I_1 = \{i_1, i_1'\}$ and $J_1 = \{j_1, j_1'\}$, there are $2n + 2n = 4n$ possible values of $(i_1, j_1)$ (since $i_1 \in I$ or $j_1 \in J$), and for each of these values of $(i_1, j_1)$, there are $k$ possible values of $(i_1', j_1')$, since we require that $a_{i_1, j_1} = a_{i_1', j_1'}$, and an entry is repeated at most $k$ times in the matrix $A$. Hence
\begin{align*}
\vspace{-2.5mm}
d &\leq |\{(I_1,J_1): I \cap I_1 \neq \emptyset \text{ or } J \cap J_1 \neq \emptyset\}\backslash\{(I,J)\}| \\
&= |\{(I_1,J_1): I \cap I_1 \neq \emptyset \text{ or } J \cap J_1 \neq \emptyset\}| - 1 \\
&\leq 4nk - 1.
\vspace{-3mm}
\end{align*}
It is clear that for any $(I,J) \in \mathcal{B}$, $|A_{I,J,\pi_{(I,J)}}| = (n-2)!$, as the action of a permutation in this set is already specified on the set $I$ of two elements. Hence, for any $(I,J) \in \mathcal{B},$
\begin{equation*}
P(A_{I,J,\pi_{(I,J)}}) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)} = p  ~\text{(say)}.
\vspace{-3mm}
\end{equation*}
Then, $ep(d+1) \leq \frac{e(4nk)}{n(n-1)} = e \cdot \frac{4k}{n-1} \leq 1$.
Hence, the conditions of Lemma 2.2 are satisfied, so that $P(\cap_{A \in \mathcal{A}}A^c) >0$, completing the proof.
\end{proof}
\section*{Acknowledgements}
The author is grateful to Stefan van Zwam for his supervision and guidance in this project as part of the course \textit{Communicating Mathematics II} at Louisiana State University.


\part{Introduction}

Single photons are of paramount importance for modern quantum information science. Envisioned applications range from all-optical quantum computation \cite{Knill2001,Minzioni2019} to quantum communication in nonlocal quantum clouds \cite{Kimble2008,Wehner2018}. As all the conceived quantum information protocols involve, in one way or another, interference effects, coherent photons are mandatory for the implementation of these protocols \cite{Rohde2005,Raymer}. This requirement includes the (relative) coherence within the photon wave packet as well as the (absolute) coherence with respect to a common network reference clock. Full control over amplitude and phase of the photon's temporal mode is a challenge \cite{Keller2004,Eisaman2004,Eisaman2005,Balic2005,Kolchin,Kielpinski2011,McKinstrie2012,Matsuda2016,Fisher2016,Karpinski2017,
Zhou2012,Specht2009,NisbetJones2011,NisbetJones2013,Farrera2016,Averchenko2017,Sych2017}, as is the mode conversion for all regimes from narrow to broad-bandwidth single photons. Meeting these challenges would open up new possibilities like temporal mode matching in multimode quantum networks or information encoding in the optical mode of the photon.

Here we exploit the arsenal of cavity quantum electrodynamics (CQED) \cite{Reiserer2015} and demonstrate deterministic mode control over single optical photons. Toward this end, we extend previous models \cite{Law1997,Kuhn1999,Fleischhauer2000, Gorshkov2007,Muecke2013,Dilley2012,Dalibard92,Giannelli2018} and take into account the full energy-level structure of the atom that serves as photon emitter and photon receiver in a high-finesse optical resonator. We find a surprisingly strong frequency dependence of the process efficiency with a pronounced minimum that originates from destructive interference of transition amplitudes. We also show that the emission efficiency is not a reliable measure for photon coherence. We moreover shape the photon phase, demonstrate the mode selectivity of photon absorption, and stretch and compress a given single-photon wave packet by 3 orders of magnitude. All these achievements are realized in combination with a convenient-to-implement coherence-testing method that outputs the time-dependent complex-valued temporal mode function with minimal resources \cite{Morin2019}.
As both the amplitude and the phase of the temporal mode are determined with respect to a commonly accepted reference, a phase-locked laser, we are now in a position to certify the (absolute) coherence of a network photon.

\begin{figure}[!b]
\includegraphics[width=0.99\columnwidth]{setup4.pdf}
\caption{Model of the experimental setup. (a) A single atom of $^{87}$Rb is trapped in a high finesse optical cavity via a 2D optical lattice (not shown). The control field of Rabi frequency $\Omega(t)$ and $\pi$-polarization impinges from the side of the cavity. The incoming photon is a weak coherent pulse of temporal shape $e(t)$. The atom is coupled to the cavity field $\mathcal{E}(t)$ with the light-matter coupling constant $g$. (b) We use a $\Lambda$ scheme with three excited-states. The Zeeman states involved are $m_F=0$ for $F=1$ and $m_F=-1$ for $F=2$ and $F'=1,2,3$.}
\label{fig:setup}
\end{figure}

Our system uses the quantum memory scheme described in Ref.\@  \cite{Koerber2018} and therefore all the following results are also valid for single photons encoding a qubit in their polarization degree of freedom. We use a single $^{87}$Rb atom trapped in an optical high-finesse cavity. The cavity is resonant with the $\text{D}_2$ line of $^{87}$Rb at 780nm. Our output (or input) photon is resonant with the cavity and addresses the transition $\ket{F=1,m_F=0} \leftrightarrow \ket{F'=1,m_F=-1}$ with a single-photon detuning $\Delta$ (see Fig.\@  \ref{fig:setup}). The control light addresses the transition $\ket{F=2,m_F =-1} \leftrightarrow \ket{F'=1,m_F =-1}$  with the same detuning $\Delta$ such that the $\Lambda$ scheme is in two-photon resonance.
The combination of the two light fields drives the atomic population from the state $\ket{F=1, m_F=0}$ to $\ket{F=2,m_F=-1}$ in absorption and vice versa for emission. The cavity is asymmetric such that the photon mostly enters/leaves the cavity via the mirror with the highest transmission. We refer to the decay rate via this mirror as $\kappa_c$, whereas we name $\kappa_l$ the decay rate via the second mirror including intracavity optical losses  (see Fig.\@ \ref{fig:setup}).

Ref.\@  \cite{Giannelli2018} provides a comparison of different models describing the photon absorption/emission by atomic systems \cite{Fleischhauer2000,Dilley2012,Gorshkov2007,Dalibard92}. The one proposed by Gorshkov \textit{et al.} \cite{Gorshkov2007} is particularly relevant for us as it considers a single-photon detuning $\Delta$. We adapt the derivation to a system with multiple excited states and obtain two important expressions, one for the relation between the complex-valued temporal shape of the single photon and the control field and another one for the efficiency of the absorption/emission.

The shape of the single-photon state is specified by its  temporal mode function $e(t)$ i.e. $\ket{1}=\int_\mathbb{R}dt\ e(t) \hat{a}^\dagger(t)\ket{0}$.
For the emission process, the link between the single-photon shape $e(t)$ and the Rabi frequency of the control field $\Omega(t)$ is of the same form as the one derived in \cite{Gorshkov2007}:
\begin{multline}\label{eq:omega}
\Omega(t) = \frac{e(t)}{ \sqrt{ 2 \Re[K] \int_t^\infty |e(t')|^2 dt' }} \\
	\exp\left(- i \frac{\Im[K]}{2\Re[K]} \ln \left( \int_t^\infty |e(t')|^2 dt' \right) \right).
\end{multline}
Here $K$ is a parameter containing all the characteristics of the atomic structure, the cavity parameters and the detunings, as derived in the Supplemental Material (SM). For coherent light-matter interaction, time reversal guarantees that the emission and the absorption processes are described by the same equation: the efficiency is the same and Eq.\@  (\ref{eq:omega}) written for emission is just reversed in time and complex conjugated for the  absorption.

\begin{figure}[!b]
\includegraphics[width=0.99\columnwidth]{eff_det.pdf}
\caption{Efficiency as a function of the single-photon detuning. (a) The three curves correspond to three theoretical models: The dotted blue line for one excited state with $F'=1$, the orange dashed line for two excited states with $F'=1,2$ and the plain green line for three excited states. The dots correspond to experimental measurements. The statistical errors are smaller. Data can be reproduced to within about 10\% (error bars). (b)-(d) Normalized temporal amplitudes for different detunings. The black lines correspond to the targeted shapes. The blue histogram corresponds to the detected photons with right circular polarization (R) and the red with left circular polarization (L). The amount of left polarized light compared to the expectation of only right polarized light witnesses the increase of incoherent processes for large detunings.}
\label{fig:efficiency}
\end{figure}

Following \cite{Gorshkov2007}, the ideal efficiency of the photon absorption/emission process $\eta_C=2C/(2C+1)$ only depends on the cooperativity $C=g^2/2\kappa\gamma$, where $g$ is the light-matter coupling constant, $\kappa = \kappa_c+\kappa_l$ the cavity field decay rate and $\gamma$ the atomic polarization decay rate. For our setup, the parameters have the values $(g,\kappa_c,\kappa_l,\gamma)=2\pi\times(4.9,2.4,0.3,3.03)\ $MHz \cite{CQEDNote}. For an imperfect cavity, however, the overall efficiency reduces to the product of $\eta_C$ and the escape efficiency $\eta_\text{esc}=\kappa_c/(\kappa_c+\kappa_l)$ \cite{Muecke2013}. With multiple excited states, the efficiency becomes a function of the single-photon detuning, $\eta_C(\Delta)$. Indeed, $\Delta$ modifies the strength of the interaction with each excited state.

Figure \ref{fig:efficiency} (a) compares the experimentally measured efficiency with three different models. The three curves correspond to the models with $F'=1$ only, with both $F'=1$ and $F'=2$, and all three excited levels $F'=1,2,3$.
Both states $\ket{F'=1}$ and $\ket{F'=2}$ participate in the Raman process. Depending on the detuning, constructive or destructive interference occurs in the photon absorption/emission process. This explains that the efficiency varies with the detuning and can be larger or smaller than in the case with only one excited level $F'=1$. In contrast, $\ket{F'=3}$ does not couple to the ground state $\ket{F=1}$ but potentially destroys the emission process by incoherent scattering.

Surprisingly, the experimental data tend to follow the model with two excited levels. This is explained by the fact that the models provide the efficiency for a pure temporal mode whereas the single-photon counting modules detect any mode. Therefore, the theoretical efficiency can only be compared with the experimental one in the regime of coherent emission.
For instance, populating state $\ket{F'=3}$ in the emission process leads to decay back into the initial $\ket{F=2}$ ground state and thus to a new emission attempt. This starts at a random time and potentially from a different $m_F$ state. On average, this results in a mixture of wavepackets which are all detected by the single-photon counting modules although they are not part of the coherent emission process.

The presence of incoherent processes in the photon emission is well illustrated in Fig.\@  \ref{fig:efficiency} (b)-(d). Here the temporal distributions of the single-photon detection events are plotted for left and right circular polarizations. For a large red detuning or close to the transition to $\ket{F'=3}$, the photon shape alters and (unwanted) left circularly polarized photons are generated. A simulation of the full system has been performed and supports the experimental observations (see SM).

\begin{figure}[!t]
\includegraphics[width=0.99\columnwidth]{HDmode20MHz.pdf}
\caption{Measurement of the complex temporal shape. The real and imaginary parts of $e(t)$ reconstructed by temporal mode analysis are plotted in arbitrary units but identical scales. (a) corresponds to the case without compensation of the phase chirp induced by light shift, and (b) to the case with phase compensation.  The plain lines correspond to the experimental measurements and the dashed lines to the theoretical shapes. When the phase chirp is compensated, the fidelity between the target shape and the measured one is 90\%. The dotted lines in plot (b) correspond to the shape with a residual detuning of 180kHz with which the fidelity goes up to 98\%. In contrast, without phase compensation, the fidelity is 55\%. For these measurements, the detuning is $\Delta/2\pi = -20$MHz and the targeted temporal shape $e(t)$ of the single photon is a hyperbolic secant with the characteristic time $T=0.5\mu$s.
}
\label{fig:temporal_shape}
\end{figure}

The presence of light in both polarization modes indicates the occurrence of incoherent processes. \textit{A contrario}, the absence of two polarizations in Fig.\@  \ref{fig:efficiency} (c) does not guarantee the coherence of the wavepacket. In addition, the measurement via photon counting does not provide any information about the phase of the temporal shape $e(t)$. In particular, Eq.\@  (\ref{eq:omega}) predicts a time-dependent phase term. This term actually accounts for the light shift induced by the control field. Without compensation of this phase, a frequency chirp is imprinted on the emitted photon.
This chirp is unwanted and can enlarge the photon bandwidth to a value larger than the cavity bandwidth, thus decreasing the emission efficiency. We emphasize here that Fig.\@  \ref{fig:efficiency} was measured with phase compensation that is achieved by properly controlling the phase of the control laser.

In order to evaluate the temporal shape $e(t)$ of the emitted photon, i.e. amplitude and phase, we use a temporal mode analysis technique \cite{MorinMode,Morin2019,LvovskyMode}. As explained in the SM, from a set of homodyne measurements we obtain the real and imaginary part of the temporal mode function $e(t)$. Figure \ref{fig:temporal_shape} shows two cases: (a) without phase control and (b) with phase compensation. Figure \ref{fig:temporal_shape}(a) clearly shows the frequency chirp induced by the control field.
The fidelity with a purely real temporal shape is 55\% in that case \cite{Fid_temp_mode}, showing the detrimental impact of the phase chirp in case it is not properly compensated. With compensation, the imaginary part in Fig.\@  \ref{fig:temporal_shape}(b) becomes  smaller and the fidelity increases up to 90\%. The majority of the remaining infidelity is likely to originate from a residual constant detuning of 180kHz of the local oscillator, as including this into the theory results in a fidelity of 98\%.

In addition, we obtain a photon-number distribution with $p_\ket{0}=0.716(2)$, $p_\ket{1}=0.284(2)$ and $p_\ket{2}=0.001(2)$. Considering the global detection efficiency of 0.6 and the atom preparation efficiency of 0.74, we estimate $p_\ket{1}\approx 0.64$ at the output of the cavity for each successful preparation of the atom. This result agrees with the one obtain by single-photon counting (see SM).

\begin{figure}[!t]
\includegraphics[width=0.95\columnwidth]{mode_select.pdf}
\caption{(color online) Temporal mode selection. (a) In black is plotted the amplitude of the input photon (experimentally a weak coherent state), which at time $t=0$ has a phase jump of $\Delta\phi$. The two other plots correspond to the amplitude of the control field, in plain blue without a phase jump, in red dashed with a phase jump of $\pi$. (b) The global efficiency (absorption and emission) as a function of $\Delta\phi$ for the two different control phase profiles. The curves are fits of the form $A\sin^2 (\Delta\phi+\phi_0) +B$. }
\label{fig:selection}
\end{figure}

Similarly to the emission case, the phase of the temporal profile is also important in absorption. Indeed, not properly compensating the phase chirp induced by the light shift leads to a temporal mode mismatch between the incoming photon and the storage mode defined by the shape of the control field. Figure \ref{fig:selection} illustrates this important aspect. We apply a phase jump of $\Delta\phi$ in the middle of the temporal shape of the input photon. Hence, for a $\pi$ phase jump, the input single photon has a temporal shape orthogonal to the one defined by the control field. This results in a suppressed efficiency. In the case depicted in dashed red, we apply a $\pi$ phase jump on the control field such that, this time, the input photon without phase jump should not be stored as it lives in an orthogonal temporal mode. Note that here and in the following experiments, we use a weak coherent state with a well controlled shape as an input.

By combining absorption and emission, it is in principle possible to convert between arbitrary shapes. We have realized two different conversions. In the first one, we store a photon of duration $T=500\mu$s and re-emit it with a new duration of $T=0.5\mu$s with an overall efficiency of 17\%. In the second one, we have performed the opposite transformation, from $T=0.5\mu$s to $T=500\mu$s, with an efficiency of 22\%. Figure \ref{fig:convert} displays the two corresponding output shapes measured by photon counting. With a total efficiency of about 20\% and a change of pulse duration by three orders of magnitude, our system outperforms the non-unitary reshaping that can be achieved with any amplitude modulator \cite{Kolchin}. This opens up the possibility to connect quantum devices working at very different time scales.

\begin{figure}[!t]
\includegraphics[width=0.98\columnwidth]{convert.pdf}
\caption{Photon conversion: A single photon (experimentally a weak coherent state input) is stored and re-emitted with a different temporal shape with constant efficiency. (a) and (b) illustrate two different photon shape conversions $T=0.5\mu\text{s}\leftrightarrow T=500\mu\text{s}$. The histograms correspond to the detection event of the photon counters and the plain lines correspond to the targeted temporal shapes. In (b) we have subtracted the dark counts of the photon counters.
}
\label{fig:convert}
\end{figure}

Although most of our results show a very good agreement between theory and experiment, the efficiency of about 20\% does not match the theoretical value of $(66\%)^2=43\%$, assuming that absorption and emission have the same efficiency. As we have measured an emission efficiency of about 66\%, this tends to indicate that the absorption is a factor of two smaller than expected. This difference remains unexplained and neither the theory nor the experimental imperfections seem to quantitatively explain the observed discrepancy. Nevertheless, except for this point, our efficiency is in principle not fundamentally limited, and ideally a unitary emission/absorption/transformation is achievable with a non-lossy cavity and a higher cooperativity, as explained above.

In conclusion, we have shown two main achievements. First, we developed a comprehensive description of light-matter interfaces using CQED. This allowed us to extend the operating parameters, especially the detuning of the control laser and the cavity, over a wide range into a regime that was not explored before. For large detunings, we found it mandatory to compensate the photon phase chirp that stems from the in this case large time-dependent control-laser intensity. We also identified efficiency limitations from destructive interference of emission pathways as well as decoherence issues from spontaneous emission and optical pumping. It is worth noting that the drawn results apply formally to any CQED system, and that most of the observed effects are relevant for other physical platforms \cite{Kurpiers2018}.

Second, we used this understanding to demonstrate an unprecedented level of control of the temporal shape of a single photon in absorption and emission, and thus transformation. These are crucial capabilities in many quantum information protocols involving single-photon states. For instance, it allows to achieve a high level of indistinguishability between multiple systems and therefore sustains the scalability of single-photon based quantum architectures. Of course, all the discovered features can immediately be transferred to single photons carrying polarization qubits.

Last but not least, the extended parameter regime with the possibility of using the cavity far-detuned from the atomic resonance will be an important tool for coupling individual atoms from a multi-atom quantum register to the same cavity \cite{Enk97}.\\[0.2cm]

We thank L. Giannelli and S. Ritter for discussions. This work was supported by the Bundesministerium für Bildung und Forschung via the Verbund Q.Link.X (16KIS0870), by the Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy – EXC-2111 – 390814868, and by the European Union’s Horizon 2020 research and innovation programme via the project Quantum Internet Alliance (QIA, GA No. 820445).

\bibliographystyle{plain}

\let\oldaddcontentsline\addcontentslin
\renewcommand{\addcontentsline}[3]{