\section{Introduction}
The "heaviest" constituents of the Standard-Model have masses of about 100 GeV/$c^2$. If such objects should be produced in particle collisions, the center of mass energy (cms energy) of the two colliding particles must be of that order or larger.
In particle physics we distinguish two types of experimental set-ups:
\begin{itemize}
\item{fixed target experiments: A particle beam hits after acceleration a target at rest.
}
\item{collision experiments: Two counter rotating particle beams are both accelerated and brought to collisions. The experimental detector encloses the collision point.
}
\end{itemize}

The kinematics of a particle with mass $m$ can be expressed
by its momentum $\vec{p}$ and energy $E$ which form a
four-vector {\bf{p}}$~=~(E,\vec{p})$ whose
square {\bf{p}}$^{2}$ is (with the appropriate norm) (see for example: \cite{bib:COL1})
\begin{equation}\label{eq:002}
     {\bf{p}}^{2}~~=~~E^{2} - \vec{p}^{2}~=~m^{2}
\end{equation}
~\\
In the collision of two particles of masses $m_{1}$ and $m_{2}$ the
total centre of mass energy can be expressed in the form
\begin{equation}\label{eq:003}
     ({\bf{p}}_{1} + {\bf{p}}_{2})^{2}~=~E^{2}_{cm}~=~(E_{1} + E_{2})^{2} - (\vec{p}_{1} + \vec{p}_{2})^{2}
\end{equation}
~\\
This is the available energy for physics experiments.
~\\
In the case of a collider where the collision point is at
rest in the laboratory frame (i.e. $\vec{p_{1}}$ = $-\vec{p_{2}}$),
the centre of mass energy becomes:
\begin{equation}\label{eq:004}
     E^{2}_{cm}~=~(E_{1} + E_{2})^{2}
\end{equation}
~\\
When one particle is at rest, i.e. in the case of so-called fixed
target experiments, (i.e. $\vec{p_{2}}$ = 0), we get:
\begin{equation}\label{eq:005}
     E^{2}_{cm}~=~(m_{1}^{2} + m_{2}^{2} + 2m_{2}E_{1,lab})
\end{equation}
A comparison for different types of collisions is made in Tab.\ref{tab:01}.
\begin{table}[htb]
\centering
\begin{tabular}{||c|c|c||}  \hline
    &        &     \\
          & E$_{cm}$ as collider (GeV) & E$_{cm}$ with fixed target (GeV) \\
    &        &     \\
\hline
    &        &         \\
p on p  (7000 on 7000 GeV)   &  14000          & 114.6           \\
    &        &     \\
e on e   (100 on 100 GeV)   &  200          & 0.32            \\
    &        &     \\
e on p   (30 on 920 GeV)   &  235          & 7.5            \\
    &        &     \\
\hline
\end{tabular}
\caption{Centre of mass energy for different types of collisions.}\label{tab:01}
\end{table}
From this table it is rather obvious why colliding beams are
necessary when centre of mass energies of the order of 100 GeV are required for
particle physics experiments. In fixed target experiments most of the beam energy is "wasted" to accelerate the center of mass and not available for new particle production.
Nevertheless most particles of our present Standard model (all leptons, all quarks other than the t-quark, neutrinos) have been discovered in fixed target experiments.

\section{Main characteristics of a collider}
\label{sec:COL-CHAR}
Particle-Colliders are very expensive and complex installations and up to date only a few "hand-fulls" have been constructed and operated.
The following criteria are useful to classify them:
\begin{itemize}

\item{
\textbf{Accelerated particles}: Particles must be charged for acceleration, apart from that leptons and their antiparticles, proton and their antiparticles or ions can be accelerated in a collider. So all but one colliders that have been built are synchrotrons, in which the colliding beams are accelerated and then kept at constant energy for several hours.
After every revolution the beams encounter themselves and produce particle collisions.
In case of a particle/antiparticle collider it is sufficient to construct a synchrotron with a single beam tube, since the Lorentz-force keeping the particles on a bent orbit changes sign with the change of particle charge. Hence both counter-rotating beams can be kept in the same ring. Special care has to be taken such that in the case of several bunches the bunches do only collide in the wanted interaction regions.
If particles collisions of the same type (for example proton-proton) are wanted, the accelerator must have two beam pipes, which are made to intersect in the interaction regions. There the beams will interact with a small crossing angle.

So far proton-proton, proton-antiproton, electron-positron and various ion species colliders have been built. Also lepton-hadron colliders have been built in order to probe with the elementary electrons the internal structure of the protons.
}
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.9\textwidth]{COL-figures/Figure1}
  \caption{center of mass energy (left) and luminosity (right) of many particle accelerators as a function of time (taken from \cite{bib:COL2}.
Empty symbols are for constructed projects, empty symbols are planned projects
(blue for $e^+ e^-$, red for pp and green for ep colliders).}
  \label{fig:COL1}
\end{figure}
\item{
\textbf{linear - or circular colliders:}
In the case of a linear collider one uses two independent linac structures in order to accelerate the two beams and makes them collide in a central region. The beams are only used once for collisions and are disposed directly after the collision point.
Such colliders are only envisaged for the creation of highest particle masses (above 100 GeV/$c^2$). The linear structures will avoid energy loss due to synchrotron radiation on a curved orbit. So far only one linear collider has been built (SLC:= Stanford Linear Collider), which used in a clever way one linac to accelerate both electrons and positrons plus at the end of the acceleration stage two $180^0$ return arcs in order to make the two beams collide head-on.
}
\item{
\textbf{maximum collision energy:}
In the case of a circular collider the acceleration of the beams can be stopped at any moment, so in principle collision energies from twice the injection energies to twice the maximum synchrotron energies are possible. In a linear collider the beams have to pass in any case through the whole linac structure, which in general can only be operated for a fixed energy. Changes of the energy require significant changes to the settings of the accelerators if not changes to the hardware layout.
}
\item{
\textbf{interaction rate:}
A very important quality indicator of a collider is the rate of particle interactions per unit time. This is characterized by a proportionality factor between the interaction rate $\dot N$ and its cross-section $\sigma_{int}$
\begin{equation}
\dot N \ =\ \cal{L}\cdot \sigma_{int}
\end{equation}
which is called the luminosity $\cal{L}$ of the collider. The luminosity depends on the intensity of the accelerated beams, on the frequency by which they collide and on the density of the beams at the collision point.
Standard units for the cross section are "barns". 1 barn [b] = $10^{-24}\ cm^2$. With this description one imagines the probability for an interaction as a small surface (measured in barns), which needs to be hit by the projectile. Accordingly the luminosity is given in units of $cm^2/s^{-1}$, so the product $\cal{L}\cdot \sigma$ has $s^{-1}$ (a counting rate) as unit.
}
\item{
\textbf{detector occupancy or pile-up:} Another performance criterion has come up in recent years in the LHC (pp-collisions at 13 TeV/$c~2$). In the case of the LHC the total cross-section of the pp interaction and the luminosity of the collider are so large, that the production rate gives more than one beam interaction per beam crossing. Actually beam crossings with more than 100 proton-proton interactions have been observed in the LHC. At these energies the average charged multiplicity of the collison-secondaries is also about 100, so beam crossings with up to 10.000 charged tracks in a detector have been measured. Hence the detector performance puts an upper limit to the luminosity that should be produced; otherwise the collisions can not be measured correctly. The number of interactions per beam crossings is called "detector-occupancy". If the collider produces a too high occupancy, the luminosity has to be lowered artificially. A nice example of a collision snapshot with about 10 interactions per beam crossing is shown in \Fref{fig:COL2}.
}
\end{itemize}
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.9\textwidth]{COL-figures/Figure2}
  \caption{Measured charged tracks close to the vertex region of a collider. The tracks coming from individual particle interactions are coloured in different colors.}
  \label{fig:COL2}
\end{figure}
\Fref{fig:COL1} summarizes the present situation with an overview of constructed and planned collider projects worldwide from the year 1960 to today. It is interesting to see the increase in centre-of-mass energy over the years and also the increase in luminosity.
We will see in a later section that some of the increase in luminosity comes naturally from the fact that with increasing energy the beam sizes shrink (for hadrons), but also fundamental new technologies for making the particle density higher at the interaction point have contributed to the progress in luminosity.

In the following sections further details will be given to each of the above listed items:

\section{What particles for the collisions?}

The choice of particle for the collisions will of course be dominated by the research objectives of the installation. A very brief look at possible collision particle gives the following overview:
\subsection{lepton collisions:}

The lightest and stable members of the lepton family, electrons and positrons are considered elementary, point-like particles, which interact through the electromagnetic and the weak force. This makes them the ideal candidates as choice for collisions, most importantly because of the elementary nature of the particles one knows the interaction center of mass energy by knowing the two beam energies. Precisions of $10^{-5}$ for the collision energy have been obtained, which has allowed to determine the masses of the created particles to that precision \cite{bib:COL3}. The cross sections for $e^+e^-$ collisions is low in the range of nano-barns to femto-barns, which yields even with the highest available luminosities event rates for which one can easily construct detectors.
Electrons are very easy to produce and accelerate, positrons need to be produced by interactions of an electron beam on a target and later reduction of transverse momenta in damping rings.
The main issue preventing  $e^+e^-$ colliders to be the only research tool is synchrotron radiation. Every charged particle following a bent orbit radius $\rho$ looses energy by emission of a photon (:= synchrotron radiation), which can be characterized by the following two quantities:\\
critical energy $E_c$:
\begin{equation*}
E_c\ =\ \frac{3}{2}\hbar c \frac{\gamma ^3}{\rho}
\end{equation*}
Energy loss per turn $U_0$
\begin{equation*}
 U_0\ = \ \frac{4\pi \alpha\hbar c \gamma ^4}{3\rho}
\end{equation*}
with values of the momentum compaction $\alpha \simeq 10^{-4}$. The photon energy increases with $\gamma ^3$ and the energy loss in synchrotron radiation over one turn as $\gamma ^4$. At beam energies around 100 GeV corresponding to a Lorentz factor of
$\gamma \simeq 2\cdot 10^5$ 3\% of the particle energy was lost in LEP in a single turn ($\rho \simeq 7km$). With protons having a rest mass 1836 times higher than electrons, the Lorentz factor is correspondingly smaller and synchrotron radiation only becomes relevant in proton-proton collisions at TeV energy scales.
So in practical terms for $e^+e^-$ collision energies well above 200 GeV the only alternative seems to be linear colliders.
Details on the last built and operated collider LEP and on the two linear collider projects ILC or CLIC can be found in the last section.

There have also been studies for muon-colliders\cite{bib:COL4}. Muons could be generated in the decay channel of pions, then "quickly" accelerated within the muon life time and made collide in a reasonably sized collider ring. Muons are also elementary particles, but about 200 times heavier than electrons and hence do not suffer as much from synchrotron radiation. Conceptually the biggest problem for a muon collider is the lack of methods to generate muons in sufficient density to make the collider luminosity large enough.

\subsection{proton-proton collisons:}

Almost free of synchrotron radiation protons can be accelerated in a circular accelerator to energies in the multi-TeV range. Historically also proton-antiproton colliders have been built, but due to the difficulties in getting large stacks of dense antiproton beams, modern designs for highest collison energies do not consider proton-antiproton colliders anymore due to low achievable luminosities \cite{bib:COL5}.

Protons are not elementary particles, in a very simplistic way one can describe them as three valence quarks, a "sea" of quark-antiquark pairs and gluons, the conveyors of the strong force (more detailed reading for example in  \cite{bib:COL6}). Details of the proton structure depend very much on how hard you hit it in electron scattering experiments ($Q^2$ = negative squared four-momentum transfer between incoming and outgoing electron), but what we retain here is the fact that the valence quarks carry most of the energy of the proton and as \Fref{fig:COL5} shows they carry on average 20\% of the proton energy with a wide probability distribution. But this means that in a proton-proton collider one does not know the initial energy of the collision partners. In some cases it can be determined by summing up all measured energies of the secondary particles. In general the lack of knowledge of the initial energy is one major problem in the data analysis of proton-proton collisions. \Fref[b]{fig:COL5} also means that the highest probability to have valence quark collisions is at about 4\% ($0.2 \cdot 0.2$) of the collision energy.

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.5\textwidth]{COL-figures/Figure5}
  \caption{modelled momentum distribution of valence and sea quarks in a proton at $Q^2$ = 10 GeV$^2$}
  \label{fig:COL5}
\end{figure}
A very significant difference between pp collisons and $e^+e^-$  collisons is the high total cross-section of pp collisons. At 13 TeV cms energy the cross-section is about 100 mb, which is due to the strong interaction $10^5$ times higher than in the case of the electro-weak interactions in $e^+e^-$ collisons.
But most of these many pp interactions only create secondary fragments, which are of little interest to study. Only a very small fraction of the produced interactions represents an event of rare particle production. The situation is depicted in
\Fref{fig:COL6}.
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.5\textwidth]{COL-figures/Figure6}
  \caption{cross-sections for various interesting physics processes as function of the created particle mass. The scales on the right indicate the event rate for a luminosity of $10^{34}cm^{-2}s^{-1}$.}
    \label{fig:COL6}
\end{figure}
One clearly sees with the hight total cross-section ($\sigma_{inelastic}$) event rates close to 1 GHz are possible, which is another way of representing the large detector occupancy at 40 MHz bunch crossing frequency of the LHC (see also \Sref{sec:COL-CHAR}).
Such large amounts of data cannot be recorded. With a sophisticated system of trigger electronics, a subset of events with interesting content is preselected for recording.
As you can see the rate for production a Higgs-boson through gluon fusion ($gg\rightarrow H_{SM}$)
is only about 1 Hz.
\subsubsection*{Brief comparison of pp and $e^+e^-$ colliders}
\begin{itemize}
\item{
\textbf{$e^+e^-$ collider}\\
The highest collison energies produced were just above 200 GeV in LEP. Presently people study a project of a circular collider (FCC-ee) up to 360 GeV and two linear colliders up to a maximum of 3 TeV of beam energy. Such colliders produce almost mono-energetic collisions of elementary particles with very clean experimental background conditions.
}
\item{
\textbf{pp collider}\\
Presently the LHC produces pp-collisions at 13 (max. 14) TeV. There is a project to construct a pp-collider at 100 TeV (FCC-pp). pp-colliders produce the interaction of composite particles, in which the interacting constituents have a large energy spectrum.
Most of the interactions are hadronic debris, which obscures somehow the analysis of the underlying interesting physics events. The data analysis in pp collisions is much more involved, but the research potential is very large, since this way the highest collision energies can be reached.
}

\end{itemize}

\subsection{Other particle colliders}
\begin{itemize}
\item{
\textbf{Ion colliders}
The largest presently operating ion collider is RHIC (= Relativistic Heavy Ion Collider) on Long Island (US).
Several different species of ions are accelerated and collided in two superconducting rings.
The main research objective is to study at very high particle densities. Ions being composed of many protons and neutrons have an even more complex internal structure, so in the event of an ion-ion interaction very high densities of secondary particles are created. More details on RHIC can be found under \cite{bib:COL7}. The LHC at CERN has also been used to collide ions.
}
\item{
\textbf{Hadron - electron colliders}\\
At DESY close to Hamburg (GE) a large collider for protons and electrons has operated in the years 1992 - 2007 for research operation. It used a normal conducting ring for the acceleration of electrons (and occasionally positrons) up to 40 GeV and a superconducting ring for the acceleration of protons to 820 GeV. In these electron-proton collisions, the point-like electron acts like a tiny probe that scans the inside of the proton and reveals its inner structure. The higher the energy of the particle collision, the deeper physicists are able to gaze into the proton, and the more insights they obtain about the inner structure of the proton and the fundamental forces of nature.
More details can be found at \cite{bib:COL8}.
}
\item{
\textbf{photon-photon collisions}\\
The collisions of photons sounds crazy at the first sight, since photons as neutral particles can not be accelerated in an accelerator.
But again synchrotron radiation "helps": Close to the interaction-point of electrons and positrons the Coulomb-force bends the particles towards each other, which stimulates the emission of photons. In some cases a photon is emitted from an electron and a second photon from a positron and they can interact. So photon-photon collisions are a subset of $e^+e^-$ collisions and they provide a large field of research. Although the collisions of the electrons and positrons are always at the sum of the beam energies, the photon energies represent a large spectrum and hence the collision products can have a large energy spectrum (more reading in \cite{bib:COL9}).
}
\item{
\textbf{wakefield accelerators}\\
All accelerators described so far use conventional Rf-Cavities for the particle acceleration. Accelerating gradients of up to 100 MV/m can be reached in extreme cases.
Since many years people try to use wakefields in plasma for the acceleration of electrons or positrons. Theoretically much higher gradients of up to 100 GV/m could be reached.
A full lecture in the same course is dedicated to this research \cite{bib:COL10},\cite{bib:COL11}.
}
\end{itemize}
\section{Computation of luminosity}
\subsection{Fixed target luminosity}
In order to compute a luminosity for fixed target
experiment, we have to take into account the properties of both,
the incoming beam and the stationary target.
The basic configuration is shown in Fig.\ref{fig:01}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.5\textwidth]{COL-figures/fixed1}
\end{center}
\caption{\it{Schematic view of a fixed target collision.}}\label{fig:01}
\end{figure}
The incoming beam is characterized by the flux $\Phi$, i.e. the number
of particles per second.
When the target is homogeneous and larger than the incoming beam,
the distribution of the latter is not important for the luminosity.
~\\
The target is described by its density $\rho_{T}$ and its length $l$.
With a definition of the luminosity like:
\begin{equation}\label{eq:006}
     {\cal{L}}_{FT}~=~\Phi \rho_{T} l
\end{equation}
we write the interaction rate
\begin{equation}\label{eq:007}
     \frac{dR}{dt}~~=\Phi \rho_{T} l~\cdot\sigma_{p}~=~{\cal{L}}_{FT}~\cdot~\sigma_{p}
\end{equation}
as desired.
\subsection{Colliding beams luminosity}
In the case of two colliding beams, both beams serve as target and
"incoming" beam at the same time.
Obviously the beam density distribution is now very important and the
generalization of the above
expression leads to the convolution of the 3-D distribution functions.
\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.5\textwidth]{COL-figures/coll2a}
\end{center}
\caption{\it{Schematic view of a colliding beam interaction.}}\label{fig:02}
\end{figure}
We treat the case of bunched beams, but it can easily be extended
to unbunched beams or other concepts like very long bunches.
A schematic picture is shown in Fig.\ref{fig:02}.
Since the two beams are not stationary but moving through each other,
the overlap integral depends on the longitudinal position of
the bunches and therefore on the time as they move towards and through
each other.
For our integration we use the distance of the two beams to the central
collision point $s_{0} = c\cdot t$ as the "time"
variable (see Fig.\ref{fig:02}).
A priori the two beams have different distribution functions and different
number of particles in the beams.
~\\
The overlap integral which is proportional to the luminosity {\cal{L}}
we can then write as:
\begin{equation}\label{eq:008}
{{\cal L} \propto {{K}} \cdot \int\int\int\int_{-\infty}^{+\infty}} \rho_{1}(x,y,s,-s_{0}) \rho_{2}(x,y,s,s_{0}) dxdydsds_{0}
\end{equation}
Here $\rho_{1}(x,y,s,s_{0})$ and $\rho_{2}(x,y,s,s_{0})$ are the
time dependent beam density distribution functions.
We assume, that the two bunches meet at $s_{0}~=~0$.
Because the beams are moving against each other, we have to
multiply this expression with a kinematic factor \cite{kinfact}:
\begin{equation}\label{eq:009}
 {{K}} = \sqrt{(\vec{v_{1}} - \vec{v_{2}})^{2}  -  (\vec{v_{1}}\times\vec{v_{2}})^{2}/c^{2}}
\end{equation}
~\\
In the next step we assume head-on collisions ($\vec{v_{1}} = -\vec{v_{2}}$)
and that all densities are uncorrelated in all planes.
In that case we can factorize the density distributions and get for
the overlap integral:
\begin{equation}\label{eq:010}
~~~~~~{\cal L} = {{2}} N_{1}N_{2}fN_{b}
\displaystyle{\int\int\int\int_{-\infty}^{+\infty}}
\rho_{1x}(x)\rho_{1y}(y)\rho_{1s}(s - s_{0})
\rho_{2x}(x)\rho_{2y}(y)\rho_{2s}(s + s_{0})~~dxdydsds_{0}
\end{equation}
~\\
We have completed the formula with the beam properties necessary to
calculate the value of the luminosity:
$N_{1}$ and $N_{2}$ are the intensities of two colliding
bunches, $f$ is the revolution frequency and $N_{b}$ is the number
of bunches in one beam.
~\\
To evaluate this integral one should know all distributions.
An analytical calculation is not always possible and a numerical
integration may be required.
However in many cases the beams follow "reasonable" profiles
and we can obtain closed solutions.
\subsection{Luminosity of Gaussian beams colliding head-on}
Often it is fully justified to assume Gaussian distributions.
The luminosity is determined by the overlap of the core of
the distributions and the tails give practically no
contribution to the luminosity. We shall come back to this
point in a later section.
~\\
For the first calculation we assume Gaussian profiles in
all dimensions of the form:
\begin{equation}\label{eq:011}
\ \ \displaystyle{\rho_{iz}(z) = \frac{1}{\sigma_{z}\sqrt{2\pi}}
\exp{\left(-\frac{z^{2}}{2\sigma_{z}^{2}}\right)}}
\ {\mathrm{where}} \ \ i = 1,2,\ \  z = x,y
\end{equation}
\begin{equation}\label{eq:012}
\ \ \displaystyle{\rho_{s}(s \pm s_{0}) =
\frac{1}{\sigma_{s}\sqrt{2\pi}}
\exp{\left(-\frac{(s \pm s_{0})^{2}}{2\sigma_{s}^{2}}\right)}}
\end{equation}
~\\
Furthermore we assume equal beams, i.e.:
{{$\sigma_{1x} = \sigma_{2x}, \sigma_{1y} = \sigma_{2y},\sigma_{1s} = \sigma_{2s}$}} \\
~~~\\
Next we assume the number of particles per bunch $N_{1}$ and $N_{2}$,
a revolution frequency of $f$ and the number of bunches we call $N_{b}$.
In the case of exactly head-on collisions of bunches travelling almost
at the speed of light, the kinematic factor becomes 2.
~~~\\
Using this in equation (\ref{eq:010}) we get the first integral:
\begin{equation}\label{eq:013}
{\cal L} = \frac{2\cdot N_{1}N_{2}fN_{b}}{(\sqrt{2\pi})^{6}\sigma_{s}^{2}\sigma_{x}^{2}\sigma_{y}^{2}}
\displaystyle{\int\int\int\int
e^{-\frac{x^{2}}{\sigma_{x}^{2}}}
e^{-\frac{y^{2}}{\sigma_{y}^{2}}}
e^{-\frac{s^{2}}{\sigma_{s}^{2}}}
e^{-\frac{s_{0}^{2}}{\sigma_{s}^{2}}}  dxdydsds_{0} }\\
\\
\end{equation}
integrating over $s$ and $s_{0}$, using the well known formula:
\begin{equation}\label{eq:014}
 \displaystyle{\int^{+\infty}_{-\infty} e^{-a t^{2}} dt~~~=~~~\sqrt{\pi/a}}
\end{equation}
we get a first intermediate result:
\begin{equation}\label{eq:015}
{\cal L} = \frac{2\cdot N_{1}N_{2}fN_{b}}{8(\sqrt{\pi})^{4}\sigma_{x}^{2}\sigma_{y}^{2}}
\displaystyle{\int\int
e^{-\frac{x^{2}}{\sigma_{x}^{2}}}
e^{-\frac{y^{2}}{\sigma_{y}^{2}}} dxdy }\\
\\
\end{equation}
finally, after integration over x and y:
\begin{equation}\label{eq:016}
{{\Longrightarrow}}~~~{{{\cal L} = \displaystyle{\frac{N_{1}N_{2}fN_{b}}{4\pi\sigma_{x}\sigma_{y}}}}}
\end{equation}
This is the well-known expression for the luminosity of two Gaussian beams
colliding head-on.
It shows how the luminosity depends on the number of particles per bunch and
the beam sizes.
This reflects the 2-dimensional target charge density we have seen in
the evaluation of the fixed target luminosity.
~\\
For the more general case of: {{$\sigma_{1x} \neq \sigma_{2x}, \sigma_{1y} \neq \sigma_{2y}$, but still assuming approximately equal bunch lengths $\sigma_{1s} \approx \sigma_{2s}$}} we get a modified formula:
\begin{equation}\label{eq:017}
{{ {{{\cal L} = \displaystyle{\frac{N_{1}N_{2}fN_{b}}{2\pi\sqrt{\sigma^{2}_{1x} + \sigma^{2}_{2x}}\sqrt{\sigma^{2}_{2y} + \sigma^{2}_{2y}}}}}}  }}
\end{equation}
~\\
This formula is easy to verify and also straightforward to extend to
other cases.
Here it is worth to mention that the luminosity does not depend on
the bunch length $\sigma_{s}$.
This is due to the assumption of uncorrelated density distributions.
\subsection{Examples}
In Table \ref{tab:02} we give some examples of different colliders and
their luminosity and other relevant parameters.
\begin{table}[htb]
\begin{center}
\begin{tabular}{||l|c|c|c|c|c||} \hline
            & Energy & $\cal{L}$ & rate  & $\sigma{x}/\sigma_{y}$ & Particles \\
            & (GeV)    &  cm$^{-2}$s$^{-1}$ & s$^{-1}$ & $\mu$m/$\mu$m & per bunch \\ \hline
 SPS (p$\bar{p}$)  & 315x315    &   6 10$^{30}$   & 4 10$^{5}$ &  60/30 & $\approx$ 10 10$^{10}$ \\
 Tevatron (p$\bar{p}$)  & 1000x1000    &   50 10$^{30}$  & 4 10$^{6}$  &  30/30 & $\approx$ 30/8 10$^{10}$ \\
 HERA (e$^{+}$p)  & 30x920 &   40 10$^{30}$ & 40  &  250/50 & $\approx$ 3/7 10$^{10}$ \\
 LHC (pp)         & 7000x7000     &  10000 10$^{30}$& 10$^{9}$      &  17/17 & 11 10$^{10}$ \\
 LEP (e$^{+}$e$^{-}$) & 105x105  &   100 10$^{30}$ &  $\leq$ 1 &  200/2 & $\approx$ 5 10$^{11}$ \\
 PEP (e$^{+}$e$^{-}$) & 9x3  &  3000 10$^{30}$ &   NA  &  150/5 & $\approx$ 2/6 10$^{10}$ \\
 KEKB (e$^{+}$e$^{-}$) & 8x3.5  &  10000 10$^{30}$ &   NA  &  77/2 & $\approx$ 1.3/1.6 10$^{10}$ \\
\hline \hline
\end{tabular}
\end{center}
\caption{Example of different colliders. We show the energy, luminosity, beam sizes and interaction rate for a comparison.}\label{tab:02}
\end{table}
One may notice the very different interaction rate, in particular between
hadron colliders and high energy lepton colliders.
This is due to the small total cross section of e$^{+}$e$^{-}$ interactions.
Furthermore, since so-called B-factories such as PEP and KEKB operate near or
on resonances, the interaction rate varies very strongly with the precise
energy. Therefore we write the term NA in the table.

\subsection{Additional complications in real machines}
So far we have assumed ideal head-on collisions
of bunches where the particle densities in the three
dimensions are uncorrelated.
In practice, we have to include additional effects in our
computations, some of the most important are:
\begin{itemize}
\item[$\bullet$]Crossing angle
\item[$\bullet$]Collision offset (wanted or unwanted)
\item[$\bullet$]Hour glass effect
\end{itemize}

Crossing angles are often used to avoid unwanted collisions
in machines with many bunches (e.g. LHC, CESR, KEKB).
Such crossing angles can have important consequences for
beam-beam effects \cite{beambeam} but also affect the
luminosity.
When beams do not collide exactly head-on but with a small
offset, the luminosity is reduced.
Such an offset can be wanted (e.g. to reduce luminosity or during
measurements) or unwanted, for example as a result of
beam-beam effects \cite{beambeam}.
The so-called hourglass effect is a geometrical
effect which includes a dependence of the transverse beam sizes
on the longitudinal position and therefore violates our
previous assumption of uncorrelated particles densities.
When the beam profiles deviate from a Gaussian function, we
may have to apply some correction factors and when the dispersion
at the interaction point is not zero, the effective beam sizes
are increased, leading to a smaller luminosity.
In case of optical imperfections the collision point may not
be at the minimum of the betatron function $\beta^{*}$, i.e.
at the waist, but slightly displaced with implications for the
effective beam sizes.
~\\
Some of the most important of these additional effects
we shall investigate in the following sections.

\subsubsection{Crossing angles}
A very prominent collider with a crossing angle is the
LHC presently under construction at CERN.
In the LHC one has almost 3000 closely spaced bunches and to
avoid numerous unwanted interactions, the two beams collide
at a total crossing angle of around $\approx$ 300 $\mu$rad.
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.5\textwidth]{COL-figures/coll4}
  \caption{Schematic view of two bunches colliding at a finite crossing angle.}
  \label{fig:COL-WH03}
\end{figure}

\Fref[b]{fig:COL-WH03} shows a schematic illustration of the collision region.
Colliders with unbunched, i.e. coasting beams such as the ISR need
a sizeable crossing angle to confine the interaction
region (e.g. $\approx$ 18$^{o}$ at the ISR).
~\\
In the following we shall assume without loss of generality
that the crossing angle is in the horizontal plane.

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.6\textwidth]{COL-figures/cross}
  \caption{Rotated reference system for collisions at a finite crossing angle.}
  \label{fig:COL-WH04}
\end{figure}

The overlap integrals are evaluated in the x and y coordinate system
and therefore we have to transform our bunches into the proper system.
The geometry of a collision at a crossing angle $\Phi$
is shown in \Fref{fig:COL-WH04}.
To make the treatment more symmetric, we have assumed that the total
crossing angle is made up by two rotations $\Phi/2$ and $-\Phi/2$
each of the two beams in the x-s plane (see \Fref{fig:COL-WH04}).
~\\
To compute the integral we have to transform $x$ and $s$ to
new, rotated coordinates which are now different for the two beams:
\begin{eqnarray}\label{eq:018}
x_{1} = x\cos\frac{\phi}{2} - s\sin\frac{\phi}{2},~~~~~~~~
s_{1} = s\cos\frac{\phi}{2} + x\sin\frac{\phi}{2}  \\
x_{2} = x\cos\frac{\phi}{2} + s\sin\frac{\phi}{2},~~~~~~~~
s_{2} = s\cos\frac{\phi}{2} - x\sin\frac{\phi}{2}
\end{eqnarray}
The overlap integral becomes:
\begin{eqnarray}\label{eq:019}
{\cal L} = {{2\cos^{2}\frac{\phi}{2}}}N_{1}N_{2}fN_{b}
\displaystyle{\int\int\int\int_{-\infty}^{+\infty}}
\rho_{1x}(x_{1})\rho_{1y}(y_{1})\rho_{1s}(s_{1}-s_{0})
\rho_{2x}(x_{2})\rho_{2y}(y_{2})\rho_{2s}(s_{2}+s_{0}) dxdydsds_{0}
\end{eqnarray}
The factor $2\cos^{2}\frac{\phi}{2}$ is the kinematic factor
when the two velocities of the bunches are not collinear (from eq. (\ref{eq:009})).
~\\
After the integration over $y$ and $s_{0}$, using the formula:
\begin{eqnarray}\label{eq:020}
\displaystyle{\int^{+\infty}_{-\infty} e^{-(a t^{2} + b t + c)} dt~~~=~~~\sqrt{\pi/a} \cdot e^{\frac{b^{2} - a c}{a}}}
\end{eqnarray}
we get:
\begin{eqnarray}\label{eq:021}
{\cal L} = \frac{N_{1}N_{2}fN_{b}}{8\pi^{2}\sigma_{s}\sigma_{x}^{2}\sigma_{y}}{{2\cos^{2}\frac{\phi}{2}}}
\displaystyle{\int\int
e^{-\frac{x^{2}\cos^{2}(\phi/2) + s^{2}\sin^{2}(\phi/2)}{\sigma_{x}^{2}}}}
e^{-\frac{x^{2}\sin^{2}(\phi/2) + s^{2}\cos^{2}(\phi/2)}{\sigma_{s}^{2}}} ~~~dxds
\end{eqnarray}
We make the following approximations:
since both $x$ and sin($\phi/2$) are small, we drop all terms $\sigma^{k}_{x}sin^{l}(\phi/2$) or $x^{k}sin^{l}(\phi/2$) for all k+l$~\geq~4$
and approximate sin($\phi/2$) $\approx$ tan($\phi/2$) by $\phi/2$.
After the final integrations we get for the luminosity an expression
of the form:
\begin{equation}\label{eq:022}
{\cal L} = \displaystyle{\frac{N_{1}N_{2}fN_{b}}
{4\pi\sigma_{x}\sigma_{y}}~\cdot~{S}}
\end{equation}
This looks exactly like the well known formula we have derived already,
except for the additional factor
$S$, the so-called luminosity reduction factor which can be written as:
\begin{equation}\label{eq:023}
{S = \displaystyle{
\frac{1}{\sqrt{1+(\frac{\sigma_{x}}{\sigma_{s}}\tan\frac{\phi}{2})^{2}}}
\frac{1}{\sqrt{1+(\frac{\sigma_{s}}{\sigma_{x}}\tan\frac{\phi}{2})^{2}}}}}
\end{equation}
For small crossing angles and $\sigma_{s} \gg \sigma_{x,y}$ we
can simplify the formula to:
\begin{equation}\label{eq:024}
{S =
\displaystyle{\frac{1}{\sqrt{1+(\frac{\sigma_{s}}{\sigma_{x}} \tan\frac{\phi}{2})^{2}}}}~\approx~
\displaystyle{\frac{1}{\sqrt{1+(\frac{\sigma_{s}}{\sigma_{x}} \frac{\phi}{2})^{2}}}}}
\end{equation}
~\\
A popular interpretation of this result is to consider it a correction
to the beam size and to introduce an "effective beam size" like:
\begin{equation}\label{eq:025}
\displaystyle{\sigma_{eff}~=~\sigma~\cdot~{\sqrt{1+(\frac{\sigma_{s}}{\sigma_{x}} \frac{\phi}{2})^{2}}}}
\end{equation}
The effective beam size can then be used in the standard formula
for the beam size in the crossing plane.
This concept of an effective beam size is interesting because it
also applies to the calculation of beam-beam effects of bunched
beams with a crossing angle \cite{jja1}.
~\\
As an example we use the parameters of the LHC.
The number of particles per bunch is 1.15 10$^{11}$, the beam sizes
in the two planes $\approx$ 16.7~$\mu$m, the bunch
length $\sigma_{s}$ = 7.7~cm and the
total crossing angle $\Phi~=~$285~$\mu$rad.
With the revolution frequency of 11.245 kHz and 2808 bunches, we
get for the head-on luminosity 1.2~10$^{34}$~cm$^{-2}$s$^{-1}$.
For the luminosity reduction factor $S$ we get 0.835 and the final
LHC luminosity with a crossing angle becomes $\approx$~1.0~10$^{34}$~cm$^{-2}$s$^{-1}$.
\newpage
\subsubsection{Crossing angles and offset beams}
A modification of the previous scheme is needed when the beams do not
collide head-on, but with a small transverse offset.
In order to be general, we shall treat the case with crossing angle
and offsets.
\Fref[b]{fig:COL-WH045} shows the modified geometry when we have the
same crossing angle as before, but beam 1 is displaced by $d_{1}$ and
beam 2 is displaced by $d_{2}$ with respect to their reference orbits.
\begin{figure}[ht]
\label{bnote2}
  \centering
  \includegraphics[width=0.6\textwidth]{COL-figures/crossoff}
  \caption{Schematic view of two bunches colliding at a finite crossing angle and an offset between the two beams.}
  \label{fig:COL-WH045}
\end{figure}

~~\\
The coordinate transformations are now:
\begin{eqnarray}\label{eq:026}
x_{1} = {{d_{1}}} + x\cos\frac{\phi}{2} - s\sin\frac{\phi}{2},~~~~~~~~
s_{1} = s\cos\frac{\phi}{2} + x\sin\frac{\phi}{2} \\
x_{2} = {{d_{2}}} + x\cos\frac{\phi}{2} + s\sin\frac{\phi}{2},~~~~~~~~
s_{2} = s\cos\frac{\phi}{2} - x\sin\frac{\phi}{2}
\end{eqnarray}
Following the previous strategy and approximations for the integration,
we get after integrating $y$ and $s_{0}$:
\begin{eqnarray*}
{\cal L} = \frac{N_{1}N_{2}fN_{b}}{8\pi^{2}\sigma_{s}\sigma_{x}^{2}\sigma_{y}}{{2\cos^{2}\frac{\phi}{2}}}
\displaystyle{\int\int
e^{-\frac{x^{2}\cos^{2}(\phi/2) + s^{2}\sin^{2}(\phi/2)}{\sigma_{x}^{2}}}}
e^{-\frac{x^{2}\sin^{2}(\phi/2) + s^{2}\cos^{2}(\phi/2)}{\sigma_{s}^{2}}} \\
\end{eqnarray*}
\begin{eqnarray}\label{eq:027}
\displaystyle{
\times e^{-\frac{d_{1}^{2} + d_{2}^{2} + 2(d_{1} + d_{2})x\cos(\phi/2)
- 2(d_{2} - d_{1})s\sin(\phi/2)}
{2\sigma_{x}^{2}}}dxds}.
\end{eqnarray}
~\\
After the integration over x we obtain:
\begin{equation}\label{eq:028}
{\cal L} = \frac{N_{1}N_{2}fN_{b}}{8\pi^{\frac{3}{2}}\sigma_{s}}
{{2\cos\frac{\phi}{2}}}\int_{-\infty}^{+\infty}W
\frac{e^{-(As^2 + 2Bs)}}{\sigma_{x}\sigma_{y}}ds
\end{equation}
with:
\begin{equation}\label{eq:029}
A = \frac{\sin^{2}\frac{\phi}{2}}{\sigma_{x}^{2}} +
\frac{\cos^{2}\frac{\phi}{2}}{\sigma_{s}^{2}} ,\ \ \
B = \frac{(d_{2} - d_{1})\sin(\phi/2)}{2\sigma_{x}^{2}}
\end{equation}
and
\begin{equation}\label{eq:030}
W = e^{-\frac{1}{4\sigma_{x}^{2}}(d_{2} - d_{1})^{2}}
\end{equation}
We can re-write the luminosity with three correction factors:
\begin{equation}\label{eq:031}
{\cal L} = \frac{N_{1}N_{2}fN_{b}}{4\pi\sigma_{x}\sigma_{y}}\cdot{{W}}
\cdot{{e^{\frac{B^{2}}{A}}}}\cdot{{S}}
\end{equation}
This factorization enlightens the different contributions
and allows straightforward calculations.
The last factor $S$ is the already calculated luminosity reduction
factor for a crossing angle.
One factor $W$ reduces the luminosity in the presence of
beam offsets and the factor $e^{\frac{B^{2}}{A}}$ is only
present when we have a crossing angle and offsets simultaneously.
\subsubsection{Hourglass effect}
So far we have assumed uncorrelated beam density functions
in the transverse and longitudinal planes.
In particular, we have assumed that the transverse beam sizes
are constant over the whole collision regions.
However, since the $\beta$-functions have their minima at the
collision point and increase with the distance this is not
always a good approximation.
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.75\textwidth]{COL-figures/HG}
  \caption{Schematic illustration of the hourglass effect. $\beta$(s) is plotted for two different values of $\beta^{*}$.}
  \label{fig:COL-WH05}
\end{figure}

In a low-$\beta$ region the $\beta$-function varies with the
distance $s$ to the minimum like:
\begin{equation}\label{eq:032}
\beta(s) = \beta^{*}({1+\left(\frac{s}{\beta^{*}}\right)^{2}})
\end{equation}
and therefore the beam size $\sigma~=~\sqrt{\beta(s) \cdot \epsilon}$
increases approximately linearly with the distance to the
interaction point.
This is schematically shown in \Fref{fig:COL-WH05} where the functions $\beta$(s)
are shown for two different values of $\beta^{*}$ (0.50~m and 0.15~m).
Because of the shape of the $\beta$(s) function this effect is called
the hourglass effect.
It is especially important when the $\beta$(s) function at the interaction
point approaches the bunch length $\sigma_{s}$ (\Fref{fig:COL-WH05}) and
not all particles collide at the minimum of the transverse beam size,
therefore reducing the luminosity.
Other effects such as a coupling between the transverse and longitudinal
planes are ignored in this discussion.
~\\
In our formulae we have to replace $\sigma$ by $\sigma$(s)
and get a more general expression for the luminosity:
\begin{equation}\label{eq:033}
\ \ \displaystyle{{\cal L} = \left(\frac{N_{1}N_{2}fN_{b}}
{8\pi\sigma_{x}^{*}\sigma_{y}^{*}}\right)
{\frac{{{2\cos\frac{\phi}{2}}}}{\sqrt{\pi}\sigma_{s}}\int_{-\infty}^{+\infty}
\frac{e^{-s^{2}A}}{{{1+(\frac{s}{\beta^{*}})^{2}}}}ds}}
\end{equation}
with
\begin{equation}\label{eq:034}
\ \ {\displaystyle{
A = \frac{\sin^{2}\frac{\phi}{2}}{(\sigma_{x}^{*})^{2}{{[1+(\frac{s}{\beta^{*}})^{2}]}}}} +
\frac{\cos^{2}\frac{\phi}{2}}{\sigma_{s}^{2}}}  \ \ \
\end{equation}
~\\
Usually it is difficult to compute this integral analytically
and it has to be evaluated by numerical integration.
~\\
To estimate the importance and relevance of this effect,
we shall use the parameters of the LHC,
i.e. $N_{1} = N_{2} = 1.15\times 10^{11}$ particles/bunch,
2808 bunches per beam,
a revolution frequency of
f~=~11.2455 kHz, and a crossing angle of $\phi = 285~\mu$rad.
The nominal $\beta$-functions at the interaction point are
$\beta_{x}^{*} = \beta_{y}^{*} = 0.55~$m, leading to beam sizes of
$\sigma_{x}^{*} = \sigma_{y}^{*} = 16.7 \ \mu$m,  and we use
a r.m.s. bunch length of $\sigma_{s}$ = 7.7~cm.

In the simplest case of a head on collision we get for the luminosity
${\cal L} = 1.200\times10^{34} \ \mathrm{cm}^{-2}\mathrm{s}^{-1}$.
~\\
The effect of the crossing angle we can estimate by the evaluation
of the factor $S$ and get:
${\cal L} = 1.000\times10^{34} \ \mathrm{cm}^{-2}\mathrm{s}^{-1}$.
~\\
When we further include the hourglass effect we get:
${\cal L} = 0.993\times10^{34} \ \mathrm{cm}^{-2}\mathrm{s}^{-1}$.
~\\
While the effect of the crossing angle is very sizeable (S = 0.835),
the further reduction by the hourglass effect is small, at least
for the nominal LHC parameters.
For smaller $\beta$-functions at the interaction point this may
not be the case.

\section{Other luminosity issues}
There are further issues related to the luminosity which
are important for the experiments, such as:
\begin{itemize}
\item Integrated luminosity
\item Time structure of interactions
\item Space structure of interactions
\end{itemize}
The geometry of the interaction regions as well as some basic
parameters entering the standard luminosity formulae
are very important for the above issues and may need
reconsideration to trade off between the different requirements.
\subsection{Integrated luminosity}
\subsubsection{Definition of integrated luminosity}
The maximum luminosity, and therefore the instantaneous number
of interactions per second, is very important, but the
final figure of merit is the so-called integrated luminosity:
\begin{equation}\label{eq:038}
{\cal L}_{\mathrm{int}} = \displaystyle{
\int_{0}^{T}{\cal L}(t')dt'}
\end{equation}
because it directly relates to the number of observed events:
\begin{equation}\label{eq:039}
{\cal L}_{\mathrm{int}} \cdot \sigma_{p} = {\mathrm{number~of~events~of~interest}}
\end{equation}
The integral is taken over the sensitive time, i.e. excluding
possible dead time.
For an evaluation one needs a realistic model for the decay
of the luminosity with time.
Different possibilities exist and
usually one assumes some behaviour (e.g. exponential)
with a given lifetime ${\tau}$:
\begin{equation}\label{eq:040}
 {\cal{L}}(t) \longrightarrow {\cal{L}}_{0}\exp{\left(-\frac{t}{\tau}\right)}
\end{equation}
Contributions to this life time we have from the decay of beam intensity
with time, the growth of the transverse emittance, increase of
the bunch length etc.
The advantage of assuming an exponential decay is that the contributions
from different processes can be easily added.
The differences between the different models is very small in practice.
\subsubsection{Optimization of integrated luminosity}
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.7\textwidth]{COL-figures/intlum}
  \caption{Typical performance curve of a collider: The LHC integrated luminosity for several years of running [taken from CERN courier].}
  \label{fig:intlum}
\end{figure}
The aim of the operation of a collider must be to optimize
the integrated luminosity.
Two parts of the operation must be distinguished: the luminosity
run with a lifetime $\tau$ and the preparation time between
two luminosity runs t$_{p}$.
The optimization problem is very similar to the
challenge of a formula 1 racing team:
the length of running with decreasing performance (slowing down with
ageing tires)
and the time needed to restore the performance (changing tires).
The best strategy should minimize the overall time needed.
~\\
In principle, the knowledge of the preparation time allows
an optimization of ${\cal L}_{\mathrm{int}}$.
~\\
If we assume an exponential decay of the luminosity ${\cal{L}}(t) = {\cal{L}}_{0} \cdot e^{t/\tau}$
we want to maximize the average luminosity $<{\cal{L}}>$:
\begin{equation}\label{eq:041}
<{\cal{L}}> = \frac{\int_{0}^{t_{r}} {\cal{L}}(t) dt}{t_{r} + t_{p}} = {\cal{L}}_{0} \cdot \tau \cdot \frac{1 - e^{-t_{r}/\tau}}{t_{r} + t_{p}}
\end{equation}
Here $t_{r}$ is the length of a luminosity run and $t_{p}$ the preparation
time between two runs.
Since $t_{r}$ is a "free" parameter, i.e. can be chosen
by the operation crew, we can optimize this expression and
get a (theoretical) maximum for:
\begin{equation}\label{eq:042}
t_{r} \approx \tau \cdot {\mathrm{ln}}(1 + \sqrt{2t_{p}/\tau} + t_{p}/\tau)
\end{equation}
Assuming some parameters for the LHC \cite{ob1}: \\
$t_{p}\approx$~10h, $\tau \approx$~15h, we get: $\Rightarrow t_{r} \approx$~15h .
\Fref[b]{fig:intlum} shows as an example a typical performance curve as it has been published for the CERN LHC collider. For every year of running the integrated luminosity is shown. Taking the value at the end of the year and multiplying it with the cross-section of the interaction of interest, one gets easily the number of produced events.

\subsection{Luminous region and space structure of luminosity}
In addition to the number of events, the space structure is important
for the design and running of a particle physics experiment.
The questions we asked are therefore:
\begin{itemize}
\item[$\bullet$] What is the density distribution of interaction vertices ?
\item[$\bullet$] Which fraction of collisions occur {{$\pm$ s}} from the interaction point ?
\end{itemize}
The answers depend on beam properties such as
$\sigma_{x}$, $\sigma_{y}$, and $\sigma_{s}$
but also on the crossing angle $\phi$.
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.6\textwidth]{COL-figures/lreg1}
  \caption{Schematic illustration of luminous regions.}
  \label{fig:COL-WH06}
\end{figure}

This is very schematically indicated by the overlap regions in
\Fref{fig:COL-WH06}.
Depending of the beam and machine parameters, this region can be
very different, with important consequences for e.g. trigger system
or pattern recognition.
We evaluate:
\begin{equation}\label{eq:043}
{\cal L}_{0} = \int_{-\infty}^{+\infty}{\cal L}(s')ds' \longrightarrow {\cal L}({{s}}) = \int_{{{-s}}}^{{{+s}}}{\cal L}(s')ds'
\end{equation}
and get:
\begin{equation}\label{eq:044}
{\cal L}(s) =
\left(\frac{N_{1}N_{2}fN_{b}}{8\pi\sigma_{x}^{*}\sigma_{y}^{*}}\right)
\frac{2\cos\frac{\phi}{2}}{\sqrt{\pi}\sigma_{s}}
\ \sqrt{\frac{\pi}{A}} \ \mathrm{erf}\left(\sqrt{A} \ s \right)
\end{equation}
For the integrated luminosity this becomes:
\begin{equation}\label{eq:045}
{\cal L}_{\mathrm{int}}(s) = \displaystyle{
\int_{0}^{T}\int_{-s}^{+s}{\cal L}(s',t)ds'dt}
\end{equation}

In order to evaluate this numerically, we use again LHC nominal
parameters as above.
The results of our calculations are shown in Tab.\ref{tab:03}.
\begin{table}[htb]
\centering
\begin{tabular}{||c|c||}  \hline
            &     \\
  integration range  & percentage of luminosity \\
            &     \\
\hline
            &         \\
 s~=~$\pm$~12~cm      &   1.000          \\
            &     \\
 s~=~$\pm$~ 8~cm      &   0.950          \\
            &     \\
 s~=~$\pm$~ 7~cm      &   0.900          \\
            &     \\
 s~=~$\pm$~ 6~cm      &   0.850          \\
            &     \\
 s~=~$\pm$~ 5.5~cm      &   0.800          \\
            &     \\
\hline
\end{tabular}
\caption{Percentage of visible luminosity as a function of distance to interaction point.}\label{tab:03}
\end{table}
While practically all luminosity is seen at a distance of $\pm$ 12~cm from
the interaction point, about 20\% is lost when only a region of
$\pm$ 5.5~cm is covered by the detector or the software.
This does strongly depend on the crossing angle.
A detailed examination of this property was done in \cite{bruno1}.
\subsection{Time structure of luminosity}
In addition to the space structure, the time structure of the
interactions is an important input for the setup of an experiment
and even on the possible physics that can be studied.
~\\
In the LHC the bunches cross every 25~ns and it can be calculated easily
that for proton-proton collisions one has to expect $\approx$~20
simultaneous interactions per bunch crossing.
They must be digested by the detectors before the
next bunch crossing occurs, a non trivial task for the
experiments.
Some physics studies that cannot be done with such an event pile up
may require to run at a lower luminosity.
\clearpage

\section{collider examples of "yesterday, today and tomorrow"}

In the last section we highlight some particle colliders, in order to draw the line from first steps in the 1960's to future CERN projects.

\subsection{AdA - first $e^+ e^-$ collider ever (1961-1964)}
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.5\textwidth]{COL-figures/Figure-AdA}
  \caption{photo of the first $e^+ e^-$ collider AdA in Frascati (taken from CERN courier) }
  \label{fig:COL-AdA}
\end{figure}
In the year 1961 the Austrian physicist Bruno Touschek proposed the idea of colliding beams and proposed a demonstrator installation at the LNF (Frascati National Laboratory) in Frascati. At that time many people working on fixed target experiments disliked the idea of replacing the solid target with another counter-rotating beam.
AdA went even one step further replacing the second beam with a beam of antimatter in order to use the same magnetic system.

After the machines construction, it was operated from 1961 to 1964, by the National Institute of Nuclear Physics, in Frascati, Italy. However, in 1962, the machine was relocated to the Laboratoire de l’Accelerateur Lineaire in Orsay, France, where it was used for an additional four years alongside the laboratory's powerful particle injector.

Towards the end of 1963, AdA's first electron-positron collisions were recorded. Then, the machine was operated a few more years for further successful and decisive tests before dismantling. AdA was never used to collect physics data. Instead, it was a testing ground for a breed of machines that was to change the course of particle physics in the following decades.

\subsection{Further milestones in collider developments}

For many years people were sceptical about the possibilities to collide two counter-rotating beams. The worries were that the forces at the interaction moment were so large that the two beams would disintegrate after the collisions (in particular in the case of bunched beams).
All first collider attempts were with electrons and positrons, the first proton-proton collider was the ISR (:= intersection storage rings) at CERN, which used unbunched beams and as consequence large crossing angles. Light ions (alpha, deuterium...) were also collided in the ISR.
Also at the ISR first collisions of protons and antiprotons were made in the year 1981 including first cooling experiments in order to reduce the emittance of the antiproton beam (and hence increase the luminosity of the collisions).

The developments at the ISR have led to the construction of the antiproton accumulator (AA) at CERN paving the way to use the existing SPS fixed target synchrotron as proton-antiproton collider. This happened in the early 1980's at the same time when CERN was preparing for the construction and operation of LEP.

Significant work on increasing the performance of lepton colliders has been done at CESR in Ithaca (NY, United States of America) (= Cornell electron storage ring). Detailed studies on beam-beam forces were carried out there plus the development of a so called "Pretzel" Scheme, in which the electrons and positrons were sent on largely different orbits in the accelerator arcs avoiding parasitic beam crossings in the arc. With a Pretzel scheme a collider can accelerate and store many bunches of particle-antiparticle beams using a single beam-pipe.

\subsection{LEP - $e^+ e^-$ collider (1989 - 2000)}

The direct discovery of the W and Z bosons at the CERN SPS proton-antiproton collider in the year 1982 has defined the energy scale for the next generation of $e^+ e^-$ colliders, for which the principle task was to study with high precision the Z-boson (LEP and SLC) and the charge W bosons (LEP-phase II).
In Europe CERN set out to construct a circular collider with an energy reach of 200 GeV, whereas in the United states at Stanford one opted for the more challenging solution of constructing a linear collider (SLC = Stanford linear collider, next section).

LEP was operated in two phases, first at a cms energy of about 91 GeV in order to mass produce Z bosons, later above 200 GeV in order to produce the charged W bosons in pairs.

In order to reach 100 GeV beam energy a 27 km circumference tunnel was constructed.
The collider was filled with only 4 bunches of both beams producing collisions in four interaction points.

The key technology in order to compensate for the synchrotron radiation loss was an Rf system composed of conventional normal conducting Rf cavities plus a large number of Nb sputtered superconducting cavities.
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.9\textwidth]{COL-figures/Figure-LEP}
  \caption{summary sheet of the CERN LEP $e^+ e^-$ collider (1989 - 2000) }
  \label{fig:COL-LEP}
\end{figure}

\subsection{SLC - $e^+ e^-$ linear collider (1988 - 1998)}

Almost parallel to the efforts at CERN people at SLAC launched the effort to design, build and operate the first linear collider SLC. The accelerator was unique in design since it used the same 3.2 km long linac in order to accelerate the electrons and the positrons in following buckets of the RF system (with opposite sign). At the end of the linac a dipole magnet has split both beams into two $180^0$ return arcs in order to have head-on collisions.
The synchrotron radiation losses on one half turn created an energy spectrum of the colliding beams.
Enabling technology was apart from the linac RF system (normal-conducting) the development of damping rings, in which the emittance of the beams was reduced with the help of synchrotron radiation before entering the main linac.
Also, and contrary to LEP, the beams could be polarized in collision, making some unique physics experiment possible.

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.9\textwidth]{COL-figures/Figure-SLC}
  \caption{summary sheet of the SLAC SLC $e^+ e^-$ collider (1988 - 1998) }
  \label{fig:COL-SLC}
\end{figure}

\subsection{LHC - pp collisions (2008 - today)}

Already in the 1990's CERN decided to reuse after the successful running of LEP the tunnel infrastructure in order to build a superconducting two ring proton-proton collider: the Large Hadron Collider LHC. It started operation in the year 2008 and it is as of today still running.
The physics objective in general are searches for high mass particles, such as the Higgs boson (discovered at the LHC in the year 2012) and possibly particles beyond the Standard Model (BSM-physics).

In the case of the LHC the enabling technology are superconducting dipoles and quadrupoles. The dipoles have a field strength above 8 Tesla.

The four main physics experiments are ATLAS, CMS, ALICE and LHCb. The LHC delivers peak luminosities above $10^{34}cm^{-2}s^{-1}$ at a cms energy of 14 TeV.

\subsection{CLIC - $e^+ e^-$ future CERN linear collider}

Already for more than 30 years CERN pursues also design studies for a linear $e^+ e^-$ collider called CLIC. This collider could be built in several phases with different physics objectives. In the last phase an energy reach of 3 TeV cms energy is envisaged, opening the possibility for detailed studies of particles beyond the Standard Model.

The most important technology item is the up to 50 km long normal conducting linac, which aims at an accelerating record gradient of 100 MV/m. In order to deliver the enormous peak RF power for such a linac, a so called drive beam scheme is envisaged, by which a second low energy , but high intensity beam travelling parallel to the main beam transfers its energy for acceleration.
The  conceptional design report can be found under \cite{bib:COL-CLIC}.
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.8\textwidth]{COL-figures/Figure-CLIC}
  \caption{possible implementation of the CLIC in the Geneva area}
  \label{fig:COL-CLIC}
\end{figure}
\subsection{FCC - future CERN circular collider}

In the coming decades CERN sets out to rewrite the LEP/LHC history with another large circular collider complex (FCC = Future CERN Collider). A tunnel circumference of 100 km is envisaged.
\begin{figure}[ht]
  \centering
  \includegraphics[width=0.5\textwidth]{COL-figures/Figure-FCC}
  \caption{possible implementation of the FCC  in the Geneva area}
  \label{fig:COL-FCC}
\end{figure}

Again the project would start with an $e^+ e^-$ collider, which would also run at the previous LEP energies, but with more than 100 times the luminosity.
The energy scale could be extended up to 360 GeV, which would allow to study the t-quark produced as $t\bar t$ system.
The enabling technology is predominantly large scale superconducting RF systems.

After operation of the lepton machine, the installation of a proton-proton collider is envisaged in the same tunnel. Here one would gain compared to the LHC almost a factor 4 in ring bending radius and another factor 2 in the dipole strength (aim: 16 Tesla). This would give a total cms energy of 100 TeV, which will put this collider forward as search engine for new particles. The conceptual design report can be found under \cite{bib:COL-FCC}.

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.6\textwidth]{COL-figures/Figure-FCClum}
  \caption{luminosity-energy chart for the CERN options for future $e^+ e^-$ colliders}
  \label{fig:COL-FCClum}
\end{figure}
\Fref[b]{fig:COL-FCClum} compares the linear and circular collider options at CERN in respect to energy reach and design luminosities.

\section{Acknowledgements}

I would like to thank Werner Herr (CERN, now EPFL Lausanne, Switzerland), who has given in the past a lecture on collider luminosity for letting me use a significant part of his material including the write-up of the luminosity calculations.
Some of the material has been elaborated by Bruno Moratori (now STFC Daresbury) during his fellowship at CERN.

\clearpage


\section*{Abstract}
\baselineskip20pt
\noindent We study entanglement witness and present a construction of entanglement witnesses in terms of the symmetric informationally complete measurements (SIC-POVM). The capability of our witness is shown by some examples and it can be found this witness detects more entanglement than previous separability method given also by SIC-POVM. What's more, comparing with the dimension dependence of SIC-POVM, we also give the entanglement witnesses can be always constructed from general symmetric informationally complete measurements (GSIC-POVM).
\\~\\
\textbf{Keywords: Entanglement Witness, SIC-POVM}
\end{abstract}

\maketitle

\section{Introduction}
\baselineskip22pt
Quantum entanglement is an important resource that cannot be ignored in the field of quantum information processing\cite{1, 2, 3}. However, in practical applications, determining whether a given state is entangled is a difficult problem \cite{4, 5, 6}. It is essential to develop simple and effective entanglement detection methods, for example, positive partial transposition (PPT) criterion \cite{7,8,9}, realignment criterion \cite{10, 11, 12, 13, 14, 15, 16}, covariance matrix criterion \cite{17}, and correlation matrix criterion \cite{18, 19} are used to distinguish quantum entangled states from the separable ones.

Although for a given known quantum state there are many mathematical tools have been used in entanglement detection, problems related to the experimental implementation of entanglement detection for unknown quantum states have rarely yielded results \cite{20,21, 22, 23, 24}. By taking use of mutually unbiased bases (MUB) \cite{25}, the authors deal with the separability problem in two-qubit,  multipartite and continuous-variable quantum systems \cite{26}. These entanglement criteria are not only powerful, but also can be implemented experimentally. Furthermore, such idea can be generalized to the entanglement criterion based on mutually unbiased measurements (MUM) \cite{27,28,29}. Besides the MUB and MUM, symmetric informationally complete measurements (SIC-POVM) is another intriguing topic in quantum information theory
and enormous work is completed in recent years. In order to avoid the open question that  whether SIC-POVM exists in arbitrary dimension, the authors introduced the general symmetric informationally complete measurements (GSIC-POVM) \cite{30}. Elements of GSIC-POVM are need not to be rank one and  GSIC-POVM exists in all finite dimensions. In fact, GSIC-POVM can be constructed from the generalized Gell-Mann matrices which showed by Gour and Kalev \cite{31}. Many of entanglement detection methods have been given for $d$-dimensional bipartite systems based on SIC-POVM and GSIC-POVM \cite{32,33,34,35,36,37,38,39}.

On the other hand, the entanglement witness (EW) is regarded as a useful approach to characterize the quantum entanglement \cite{40}. Detecting an unknown quantum state by EW requires less information than state tomography. It only concerns the mean values of some observables for a given quantum state. An entanglement witness $W$ is an hermitian operator which is block-positive but not positive. A bipartite state $\rho$ is separable if and only if $\Tr (\rho W)\geqslant0$ for all entanglement witnesses. It would be interesting to combine the entanglement witness with POVM like MUB and MUM. In Refs. \cite{41,42}, the authors constructed the entanglement witness based on MUB and MUM. In this paper, we study the entanglement witness by using the symmetric informationally complete measurements. Detailed examples are presented to illustrate the advantages of these entanglement witnesses. Furthermore, we also give the entanglement witnesses from the general symmetric informationally complete measurements.

\section{Entanglement witness based on SIC-POVM}
In this section, we construct a class of entanglement witnesses based on SIC-POVM through a positive map.
A POVM $\{P_{1}, P_{2}, \cdots, P_{d^2}\}$ with $d^2$ rank one operators acting on $\mathbb{C}^d$ is symmetric informationally complete, if every operator is of the form $P_{j}=\displaystyle \frac{1}{d}|\phi_{j}\rangle\langle \phi_{j}|$, $j=1, 2, \cdots, d^2$, satisfying
\begin{itemize}
  \item $\mathrm{Tr}(P_j^2)=\displaystyle\frac{1}{d^2}$,
  \item $\mathrm{Tr}(P_jP_k)=\displaystyle\frac{1}{d^2(d+1)},~~~~~   j\neq k$.
\end{itemize}

In \cite{32}, the author, based on index of coincidence, derived a number of inequalities satisfied by the SIC-POVM $\{P_{1}, P_{2}, \cdots, P_{d^2}\}$ on $\mathbb{C}^d$ and the density matrix $\rho$,
\be \label{J}
\sum\limits^{d^2}\limits_{i=1}p_i(\mathcal{P}|\rho)=\sum\limits^{d^2}\limits_{i=1}[\Tr(P_i\rho)]^2=\displaystyle \frac{\Tr(\rho)^2+1}{d(d+1)}.
\ee
If $\rho$ is a pure state, in particular, one has $\sum\limits^{d^2}\limits_{i=1}[\Tr(P_i\rho)]^2=\displaystyle \frac{2}{d(d+1)}$.

Now, we are going to give an entanglement witness based on SIC-POVM through constructing a map $\Phi$ which is positive if and only if $\Phi$ maps rank one projector into a ball $\mathfrak{B}$ which takes the maximally mixed state as center (i.e. $\rho \in \mathfrak{B}\Leftrightarrow \mathrm{Tr}(\rho^2)\leqslant \frac{1}{d-1}$)\cite{42+1}. According to the relevant theorem in \cite{2}, we then show our witness by following theorem:

\textit{\textbf{Theorem 1.}} Let $\{P_1,P_2,\cdots,P_{d^2}\}$ denote the SIC-POVM on $\mathbb{C}^d$ and $\mathcal{O}$ be an orthogonal rotation in $\mathbb{R}^{d^2}$ around the axis $\vec{n}=(1,1,\cdots,1)/d$. Then the following map
\be
\Phi X = \frac{1}{d}\mathbb{I}_d\mathrm{Tr} X -\frac{d+1}{d-1}\sum\limits_{k,l=1}^{d^2}\mathcal{O}_{kl} \mathrm{Tr}(XP_{l}- \frac{1}{d}\mathbb{I}_d\mathrm{Tr} XP_{l} )P_{k},
\ee
where the $\displaystyle \frac{1}{d}\mathbb{I}_d\mathrm{Tr} X$ denotes completely depolarizing channel and $P_{l},P_{k}$ are elements of $\{P_1,P_2,\cdots,P_{d^2}\}$ , is positive. Furthermore,
\be
W_{\Phi}=\displaystyle\frac{2}{d(d+1)}\mathbb{I}_d\otimes\mathbb{I}_d- \sum\limits_{k,l=1}^{d^2}\mathcal{O}_{kl} \overline{P}_{l} \otimes P_{k}
\ee
is an entanglement witness, where $\overline{P}_{l} $ denotes the conjugation of $P_{l}$ and $\mathcal{O}_{kl}$ are elements of orthogonal rotation $\mathcal{O}$.

\textit{Proof.} For any rank-1 projector $P = |\phi\rangle\langle \phi|$, we have
\begin{widetext}
\begin{eqnarray}
\mathrm{Tr}(\Phi P)^2 &=&\mathrm{Tr}\left[\frac{1}{d^2}\mathbb{I} -2\frac{d+1}{d-1}\frac{1}{d} \sum\limits_{k,l=1}^{d^2}\mathcal{O}_{kl} \mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l )P_{k} \right.\nonumber\\  &&~~~~~\left.+(\frac{d+1}{d-1})^2 \sum\limits_{k,l,m,n=1}^{d^2}\mathcal{O}_{kl} \mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l )P_{k} \mathcal{O}_{mn} \mathrm{Tr}(PP_{n}-\frac{1}{d}\mathbb{I}_d\Tr P P_n) P_{m}
\right]\nonumber\\
&=&\frac{1}{d}-2\frac{1}{d}\frac{d+1}{d-1} \sum\limits_{k,l=1}^{d^2}\mathcal{O}_{kl} \mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l  )\Tr(P_{k})\nonumber\\
&&+(\frac{d+1}{d-1})^2  \sum\limits_{k,l,m,n=1}^{d^2}\mathcal{O}_{kl} \mathcal{O}_{mn} \mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l  )\mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_n  )\Tr(P_{k} P_{m} )\nonumber\\
&=&\frac{1}{d}+(\frac{d+1}{d-1})^2  \left[ \sum\limits_{k=m=1}^{d^2}\sum\limits_{l,n=1}^{d^2}\mathcal{O}_{kl} \mathcal{O}_{kn} \mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l  )\mathrm{Tr}(PP_{n}-\frac{1}{d}\mathbb{I}_d\Tr P P_n  )\Tr(P_{k} P_{k} ) \right.\nonumber\\  &&~~~~~~~~~~~~~~~~~~~~\left.+\sum\limits_{k\neq m=1}^{d^2}\sum\limits_{l,n=1}^{d^2}\mathcal{O}_{kl} \mathcal{O}_{mn} \mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l )\mathrm{Tr}(PP_{n}-\frac{1}{d}\mathbb{I}_d\Tr P P_n )\Tr(P_{k} P_{m} )
\right]\nonumber\\
&=&\frac{1}{d}+(\frac{d+1}{d-1})^2 \left[ \sum\limits_{l,n=1}^{d^2}\delta_{ln}\mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l )\mathrm{Tr}(PP_{n}-\frac{1}{d}\mathbb{I}_d\Tr P P_n )\frac{1}{d^2}\right.\nonumber\\  &&~~~~~~~~~~~~~~~~~~~~\left.+\sum\limits_{k\neq m=1}^{d^2}\sum\limits_{l,n=1}^{d^2}\mathcal{O}_{kl} \mathcal{O}_{mn} \mathrm{Tr}(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l )\mathrm{Tr}(PP_{n}-\frac{1}{d}\mathbb{I}_d\Tr P P_n )\frac{1}{d^2(d+1)}\right]\nonumber\\
&=&\frac{1}{d}+\frac{1}{d^2}(\frac{d+1}{d-1})^2\sum\limits_{l=1}^{d^2}[\Tr(PP_{l}-\frac{1}{d}\mathbb{I}_d\Tr P P_l)]^2, \nonumber
\end{eqnarray}
\end{widetext}
where the second equality is due to $\mathcal{O}\vec{n}=\pm \vec{n}$. Combining with Eq. (\ref{J}) we arrive at
$\mathrm{Tr}(\Phi P)^2<{1}/({d-1})$. Therefore, $\Phi$ is a positive map.
The corresponding entanglement witness
$W_{\Phi}$ can be obtained from $W_{\Phi}=\displaystyle\frac{d-1}{d+1}\sum\limits_{i,j=1}^{d}|i\rangle\langle j|\otimes \Phi |i\rangle\langle j|$ directly. $\square$

Now, let us consider some examples to show the validity of the entanglement witness $W_{\Phi}$ based on SIC-POVM.

\noindent\textit{Example 1.} We first consider the maximally entangled state $|\phi^{+}\rangle=\displaystyle\frac{1}{\sqrt{d}}\sum\limits_{i=1}\limits^{d}|ii\rangle$. Taking $\mathcal{O}=\mathbb{I}_d$, we have
$$
\begin{array}{rcl}
\mathrm{Tr}\left(W_{\Phi}(|\phi^{+}\rangle\right)&=&\displaystyle\mathrm{Tr}\left(\frac{2}{d^2(d+1)}\sum\limits_{i=1}^{d}\mathbb{I}_d|i\rangle\langle i|\otimes \mathbb{I}_d|i\rangle\langle i|-\frac{1}{d}\sum\limits_{l=1}^{d^2}\sum\limits_{i=1}^{d}\overline{P}_{l}|i\rangle\langle i|\otimes P_{l}|i\rangle\langle i|\right)\\[6mm]
&=&\displaystyle\frac{2}{d(d+1)}-\frac{1}{d}\\[4mm]
&=&\displaystyle\frac{-d+1}{d(d+1)}<0.
\end{array}
$$
Thus the entanglement witness detects all the maximally entangled states.

\noindent\textit{Example 2.} Also, theorem 1 allows us to detect noise levels of mixtures of a maximally entangled state with white noise:
\begin{eqnarray}
\rho_{\mathrm{iso}}=\alpha|\phi^{+}\rangle \langle \phi^{+}|+\frac{1-\alpha}{d^2}\mathbb{I},
\end{eqnarray}
where $|\phi^{+}\rangle=\displaystyle\frac{1}{\sqrt{d}}\sum\limits_{i=1}\limits^{d}|ii\rangle$, $0 \leqslant \alpha <1$. We also take $\mathcal{O}=\mathbb{I}_d$ and get
\be\label{13}
\Tr(W_{\Phi}\rho_{iso})&=&\Tr\left[(\frac{2}{d(d+1)}\mathbb{I}_d\otimes\mathbb{I}_d-\sum\limits_{l=1}^{d^2}\overline{P}_{l}\otimes P_{l})\rho_{iso}\right]\nonumber\\
&=&\frac{2}{d(d+1)}-\frac{(d-1)\alpha+1}{d^2}.
\ee
If $\alpha>\displaystyle\frac{1}{d+1}$, then $\Tr(W_{\Phi}\rho_{iso})<0$ and $\rho_{iso}$ must be entangled. That is to say $W_{\Phi}$ detects all the entanglement in isotropic states which coincides with the one given in \cite{43}. In other words, The separability of $\rho_{iso}$ detected by $W_{\Phi}$ indeed necessary and sufficient.

\noindent\textit{Example 3.} Now, we can consider a more general example that following state $\rho$ given by
\be
\tiny
\left(
\begin{array}{ccccccccc}
 0.18 & 0.19-0.015 i & 0.064+0.093 i & -0.21+0.047 i & 0.096-0.083 i & 0.037-0.072 i & -0.061-0.00074 i & 0.09-0.052 i & 0.098-0.042 i \\
 0.19+0.015 i & 0.21 & 0.062+0.11 i & -0.23+0.034 i & 0.11-0.083 i & 0.046-0.075 i & -0.066-0.0059 i & 0.1-0.049 i & 0.11-0.037 i \\
 0.064-0.093 i & 0.062-0.11 i & 0.072 & -0.052+0.13 i & -0.0093-0.081 i & -0.025-0.045 i & -0.023+0.032 i & 0.0052-0.067 i & 0.014-0.067 i \\
 -0.21-0.047 i & -0.23-0.034 i & -0.052-0.13 i & 0.27 & -0.14+0.075 i & -0.064+0.077 i & 0.073+0.017 i & -0.12+0.039 i & -0.13+0.024 i \\
 0.096+0.083 i & 0.11+0.083 i & -0.0093+0.081 i & -0.14-0.075 i & 0.092 & 0.054-0.022 i & -0.033-0.029 i & 0.074+0.014 i & 0.073+0.024 i \\
 0.037+0.072 i & 0.046+0.075 i & -0.025+0.045 i & -0.064-0.077 i & 0.054+0.022 i & 0.037 & -0.012-0.025 i & 0.04+0.026 i & 0.037+0.031 i \\
 -0.061+0.00074 i & -0.066+0.0059 i & -0.023-0.032 i & 0.073-0.017 i & -0.033+0.029 i & -0.012+0.025 i & 0.021 & -0.031+0.019 i & -0.034+0.015 i \\
 0.09+0.052 i & 0.1+0.049 i & 0.0052+0.067 i & -0.12-0.039 i & 0.074-0.014 i & 0.04-0.026 i & -0.031-0.019 i & 0.062 & 0.062+0.0077 i \\
 0.098+0.042 i & 0.11+0.037 i & 0.014+0.067 i & -0.13-0.024 i & 0.073-0.024 i & 0.037-0.031 i & -0.034-0.015 i & 0.062-0.0077 i & 0.064 \\
\end{array}
\right).\nonumber
\ee
 Taking the orthogonal rotation $\mathcal{O}$ and the SIC-POVM operators shown in Appendix, we can directly obtain the witness $W_{\Phi}$ given by
\be
\tiny
\left(
\begin{array}{ccccccccc}
 0.006 & -0.02-0.009 i & -0.009-0.002 i & 0.005+0.006 i & -0.08-0.002 i & 0.01-0.004 i & 0.01-0.005 i & -0.01-0.002 i & -0.08-0.002 i \\
 -0.02+0.009 i & 0.08 & 0.009-0.009 i & 0.007-0.001 i & -0.005-0.006 i & -0.01+0.01 i & -0.01+0.007 i & -0.01+0.006 i & -0.002+0.005 i \\
 -0.009+0.002 i & 0.009+0.009 i & 0.08 & 0.01-0.002 i & -0.01-0.01 i & 0.003-0.001 i & 0.003-0.003 i & -0.005-0.002 i & 0.0003-0.004 i \\
 0.005-0.006 i & 0.007+0.001 i & 0.01+0.002 i & 0.08 & 0.02+0.009 i & 0.009+0.002 i & -0.01-0.01 i & 0.008+0.01 i & -0.005-0.003 i \\
 -0.08+0.002 i & -0.005+0.006 i & -0.01+0.01 i & 0.02-0.009 i & 0.007 & -0.009+0.009 i & 0.01+0.008 i & 0.01+0.01 i & -0.08+0.001 i \\
 0.01+0.0004 i & -0.01-0.01 i & 0.003+0.001 i & 0.009-0.002 i & -0.009-0.009 i & 0.08 & -0.003-0.005 i & 0.002+0.007 i & -0.0003-0.003 i \\
 0.01+0.0005 i & -0.01-0.007 i & 0.003+0.003 i & -0.01+0.01 i & 0.01-0.008 i & -0.003+0.005 i & 0.08 & -0.005-0.004 i & -0.0001-0.005 i \\
 -0.01+0.002 i & -0.01-0.006 i & -0.005+0.002 i & 0.008-0.01 i & 0.01-0.01 i & 0.002-0.007 i & -0.005+0.004 i & 0.08 & 0.0001-0.001 i \\
 -0.08+0.002 i & -0.002-0.005 i & 0.003+0.004 i & -0.005+0.003 i & -0.08-0.001 i & -0.003+0.003 i & -0.001+0.005 i & 0.0001+0.001 i & 0.001
\end{array}
\right).\nonumber
\ee
Therefore, we have $\Tr(W_{\Phi}\rho)=-0.0152221<0$, namely, the state is entangled.
In Ref. \cite{44}, a separability criterion has been presented based on SIC-POVM:
for any separable state $\rho$,
$G(\mathcal{N}_{AB}|\rho)\leq\displaystyle \frac{2}{d(d+1)}$, where $G(\mathcal{N}_{AB}|\rho)=\sum\limits_{j=1}^{d^2}P(j,j)$, $P(j,j)$ is a joint probability.
For this example, one has $G(\mathcal{N}_{AB}|\rho)-\displaystyle \frac{1}{6}=-0.011341<0$, i.e., this criterion can not detect the entanglement of the state.
\begin{figure*}[htbp]
\centering
\subfigure[The surface under the $0$-plan represents the Bell-diagonal states with the entanglement detected by $W_{\Phi}$.]{
\begin{minipage}[b]{0.53\linewidth}
\includegraphics[width=1\linewidth]{fig1.eps}\vspace{-3pt}
\end{minipage}}~~~~~~~~~~
\subfigure[Entanglement detected by $W_{\Phi}$ for $a=0.2$ and $a=0.3$.]{
\begin{minipage}[b]{0.42\linewidth}
\includegraphics[width=1\linewidth]{fig2.eps}\vspace{10pt}
\end{minipage}}
\caption{Entanglement of the Bell-diagonal states detected by the witness $W_{\Phi}$ when $p>\displaystyle \frac{ad^2+1}{ad^2(d+1)}$. The witness detects more entanglement as $a$ increases.}
\end{figure*}

\section{Conclusion}
The separability problem via symmetric informationally complete measurements are studied in this paper and we show the quantum entanglement witnesses which are experimentally feasible for two-qudit. Some examples, such as maximally entangled states, white noise tolerance of maximally entangled states and a more general particular state are given to show the capability of such witnesses. Especially, for the given quantum state in the example, our witness is more powerful than the known entanglement criterion also based on SIC-POVM. Moreover, we have also presented an entanglement witness for arbitrary dimensional quantum systems based on the general symmetric informationally complete measurements. These results may highlight further investigations on experimentally feasible separability criteria.

\bigskip
{\sf Acknowledgments}~
This work is supported by the NSF of China under Grant No. 11675113, the Research Foundation for Youth Scholars of Beijing Technology and
Business University QNJJ2017-03, Scientific Research General Program of Beijing Municipal Commission of Education (Grant No.KM201810011009), NSF of Beijing under No. KZ201810028042, and Beijing Natural Science Foundation (Z190005), and Academy for Multidisciplinary Studies, Capital Normal University.


\section{Introduction}
Until the selection of the Advanced Encryption Standard~\cite{aes}, Feistel Networks (FN) have probably been the most popular
design framework for iterated block ciphers, whereas today they share the stage with Substitution Permutation Networks (SPN).
Feistel Networks are characterized by the clever idea of splitting the message into two halves, say left part and right part, and applying in each round a key-dependent non-linear transformation called F-function
to the right part, which is successively mixed with the left part, just before the two halves are swapped~\cite{feistel}.
As a notable feature, FNs do not require the F-function to be invertible in order to perform decryption. The framework of SPNs is instead composed
by a sequence of carefully designed key-dependent round functions composed by confusion and diffusion invertible layers acting on the whole block.
If, on the one hand, SPNs' minimalistic design allows a simple description and consequently a more careful security assessment,
on the other, the structure of FNs gives the designers more freedom in the choice of the layers intervening during the encryption,
although keeping confusion and diffusion confined only in half of the block in a single round. The Lai-Massey scheme (LM)~\cite{vaudenay1999lai}, introduced after the design of IDEA~\cite{lai1990proposal}, perfectly
combines the advantages of both frameworks, splitting the message into two halves but mixing the left and right part of the state and
consequently accelerating both diffusion and confusion.
Its pseudo-randomness behavior, its security against impossible differential cryptanalysis and other generic attacks has been addressed in recent years~\cite{quasifeistel,impossibledifferentialLM,randomlaimassey,genericattackLM}.\\

In this paper we focus on the study of a group containing the group generated by the round functions of a general Lai-Massey cipher, proving its resistance against the \emph{imprimitivity
attack}~\cite{paterson1999imprimitive} provided that its inner layers satisfy certain well-established conditions.
Little is known, indeed, on the group-theoretical security of such a design strategy, whereas the one of SPNs and FNs has been addressed in several works in the last decades. One remarkable  exception is a paper due to Wernsdorf~\cite{wenidea} which shows that the multiply-addition box at the center of the round of IDEA generates the alternating group on $\F_2^{32}$ and where it is conjectured that also the entire rounds of IDEA generate the alternating group.

The topic of our research, i.e.\ the group generated by the round functions, was first defined in 1975 by Coppersmith and Grossman~\cite{copgross} and gained more popularity
  when, in 1999, Paterson introduced the imprimitivity attack showing that in a DES-like cipher may exist a partition of the message space which is invariant under the action of the group $\Gamma$ generated by the encryption functions, i.e.\ a block system for $\Gamma$, whose knowledge can be exploited to attack the cipher. After this, the resistance of many known ciphers
to this attack has been proved~\cite{sparwenrij,carantiprimitive,wenkas,aragona2017group,aragona2018primitivity}.
In Aragona et al.~\cite[Theorem 4.5]{aragonawave}, the authors showed that the primitivity of the group generated by the rounds of an FN can be \emph{reduced} to the primitivity of the group generated by the rounds of an SPN whose round functions are the ones implemented as F-functions within each round of the FN, proving, in fact, that the primitivity of structure of an FN, in spite of its complexity,
can be inherited from a simpler design.
We prove here, using a similar approach, that the primitivity of the group generated by the rounds of an SPN implies the one of a group containing the group generated by the rounds of an LM which features in its structure the same key-dependent transformation acting in the SPN. Our result is referred to the closest group containing the actual group generated by the round functions of an LM for which a convenient algebraic description of the generators can be provided.
\subsubsection*{Organization of the paper}
In Section~\ref{sec:pre} we introduce the notation and the preliminary results, and  present our algebraic model
 of Lai-Massey scheme which is the subject of the study. In Section~\ref{sec:pri} we prove the primitivity
 reduction from the LM to the SPN.

\section{Group-theoretical cryptanalysis}\label{sec:pre}
\subsection{Preliminaries}
Let us introduce our notation and some preliminary results.
\subsubsection{Spaces}
Let $n$ be a non-negative integer and $V \deq \F_2^n$ be the $n$-dimensional vector space over $\F_2$. We denote by $\Sym(V)$ the symmetric group acting on $V$ and by $\mbb1$ its identity. The map $\mbb 0 : V \rightarrow V$ denotes the null function. The group of the translations on V, i.e.\ the group of the maps $\sigma_v: V \rightarrow V$, such that $x\sigma_v= x+v$, is denoted by $T_n$, whereas the group of translations on $V \times V$ is denoted by $T_{2n}$, where the translation $\sigma_{(v,w)}$ acts on $(x,y)$ as
$(x,y)\sigma_{(v,w)} = (x+v, y+w)$. Let us also denote by $\AGL(V)$ the group of all affine permutations of $V$ and by $\GL(V)$ the group of the linear ones.
\subsubsection{Groups}
Let $G$ be a finite group acting on a set $M$. For each $g \in G$ and $v \in M$ we denote the action of $g$ on $v$ as $vg$.
The group $G$ is said to be \emph{transitive} on $M$ if for each $v,w \in M$ there exists $g \in G$ such that $vg=w$.
A partition $\mathcal{B}$ of $M$ is \emph{trivial} if $\mathcal{B}=\{M\}$ or $\mathcal{B}=\{\{v\} \mid v \in M\}$, and \emph{$G$-invariant} if for any $B \in \mathcal{B}$ and $g \in G$ it holds $Bg \in \mathcal{B}$. Any non-trivial and $G$-invariant partition $\mathcal{B}$ of $M$ is called a \emph{block system} for $G$. In particular any $B \in \mathcal{B}$ is called an \emph{imprimitivity block}. The group $G$ is \emph{primitive} in its action on $M$ (or $G$ \emph{acts primitively} on $M$) if {$G$ is transitive and} there exists no block system.
Otherwise,  the group $G$ is \emph{imprimitive} in its action on $M$ (or $G$ \emph{acts imprimitively} on $M$). We recall here some well-known results that will be useful in the remainder of this paper~\cite{cameronpermutation}.

\begin{lemma}\label{lemma:trans}
  If $T \leq G$ is transitive, then a block system
  for $G$ is also a block system for $T$.
\end{lemma}

\begin{lemma}\label{translatioBlocks}
Let $M$ be a finite vector space over $\mathbb F_2$ and $T$ its translation group.
Then $T$ is transitive and imprimitive on $M$. A block system $\mathcal U$ for $T$ is composed by
  the cosets  of a non-trivial and proper subgroup $ U < (M,+)$, i.e.
  \begin{equation*}
 \mathcal U =    \{
     U + v
      \mid
 	v \in    M
      \}.
        \end{equation*}
  \end{lemma}
  \subsubsection{Goursat's Lemma}
To prove our results, we need to determine a block system for $V \times V$.
In order to do so, we use the following
characterization of subgroups of the direct product  of two groups in terms of
suitable sections of the direct factors~\cite{goursat}.

\begin{theorem}\label{gours}
  Let $G_1$  and $G_2$ be two  groups. There
  exists  a bijection between
  \begin{enumerate}
  \item
    the set  of all subgroups  of the
    direct  product  $G_1\times   G_2$,  and
  \item
    the  set   of  all  triples
    $(A/B,C/D,\psi )$, where
    \begin{itemize}
    \item $A$ is a subgroup of $G_{1}$;
    \item $C$ is a subgroup of $G_{2}$;
    \item $B$ is a normal subgroup of $A$;
    \item $D$ is a normal subgroup of $C$;
    \item $\psi: A/B\to C/D$ is a group isomorphism.
    \end{itemize}
  \end{enumerate}

\noindent Then, each subgroup of $G_1\times G_2$ can be uniquely
  written as
  \begin{equation*}
    U_{\psi}= \{
      (a,c) \in A \times C
      :
      (a + B) \psi =c + D
      \}.
  \end{equation*}
\end{theorem}

Note that the isomorphism $\psi: A/B\to C/D$ is induced by a homomorphism $\varphi: A \to C$ such that $(a+B)\psi=a\varphi + D$ for any $a\in A$, and $B\varphi\leq D$. Such homomorphism is not unique.
\begin{corollary}[\cite{aragonawave}]\label{lemma:psiforphi}
  Using notation of Theorem~\ref{gours}, given any homomorphism $\phi$ inducing $\psi$, we have
 \begin{equation}\label{eq:upsi}
    U_{\psi}
    =
    \{
      (a, a \varphi + d)
      \mid
      a \in A, d \in D
      \}.
  \end{equation}
\end{corollary}
\subsubsection{Ciphers}
A \emph{block cipher} $\Phi$ is a family of key-dependent permutations
\[\{E_K \mid E_K: \ M \rightarrow M, \, K \in \mathcal K \},\]
 where $M$ is the message space, $\mathcal K$ the key space, and $|M|\leq |\mathcal K|$. The permutation $E_K$ is called the \emph{encryption function induced by the master key} $K$. The block cipher $\Phi$ is called an {iterated block cipher} if there exists $r \in \mathbb N$ such that for each $K \in \mathcal K$ the encryption function $E_K$ is obtained as the composition of $r$ {round functions}, i.e. $E_K = \varepsilon_{1,K}\,\varepsilon_{2,K}\ldots\varepsilon_{r,K}$. To provide efficiency, each round function is the composition of a public component provided by the designers, and a private component derived from the user-provided key by means of a public procedure known as \emph{key-schedule}. The group
\begin{equation*}\label{def:gr}
	\Gamma_{\infty}(\Phi)\deq\langle \varepsilon_{i,K} \mid K \in \mathcal{K}, 1 \leq i \leq r\rangle,
\end{equation*}
called \emph{the group generated by the round functions} of $\Phi$, is studied to prevent
group-theoretical attacks~\cite{kaliski,paterson1999imprimitive,calderini2017translation}.\\

An iterated {block cipher} $\Phi$ is called an $r$-round \emph{Substitution Permutation Network} (SPN) if $M = V$ and for each $1 \leq i \leq r$ we have
 \[
 \varepsilon_{i,K} \deq \rho\sigma_{k_i},
 \]
 where $\rho\in \Sym(V)\setminus \AGL(V)$ is designed to provided both Shannon's principle of confusion and diffusion~\cite{shannon}.
If $\Phi$ is an SPN, then $\Gamma_{\infty}(\Phi) = \Span{\rho, T_n}$\cite{carantiprimitive}.
\subsection{A model for the Lai-Massey scheme}
We introduce here our algebraic description of the Lai-Massey scheme~\cite{lai1990proposal} as presented by Vaudenay~\cite{vaudenay1999lai}.
\begin{definition}\label{LMdef}
Let $r$ be a non-negative integer, $\rho \in \Sym(V)\setminus \AGL(V)$ and $\theta \in \GL(V)$.
An $r$-round Lai-Massey cipher $\mathrm{LM}(\rho,\theta)$ is a set of encryption functions \[\{E_K \mid K \in \mathcal K\} \subseteq \Sym(V\times V)\]  such that  for each $K \in \mathcal K$ the map $E_K$ is the composition of $r$ functions, i.e.\
$E_K =\overline{\varepsilon_{1,K}}\:\overline{\varepsilon_{2,K}}\ldots\overline{\varepsilon_{r,K}}$.
The $i$-th round function
$\overline{\varepsilon_{i,K}}$ is defined as
\[
\overline{\varepsilon_{i,K}} \deq \overline{\rho}\,
\overline\theta
\sigma_{({k_i}\theta,k_i)},
\]
where
\begin{itemize}
\item $\overline{\rho}$ denotes the formal operator $\rhoLM \in \Sym(V\times V)$;
\item $\overline\theta$ denotes the formal operator $\begin{pmatrix}
\theta & \mbb0\\
\theta & \mbb1
\end{pmatrix} \in \Sym(V\times V)$;
\item the  key-schedule $\mathcal{K} \rightarrow V^{r}$, $K \mapsto (k_1,k_2,\ldots,k_r)$ is surjective with respect to any round.
\end{itemize}
\end{definition}
By the assumption on the key-schedule, we can always assume without loss of generality that $0\rho = 0$, provided that,
in each round, the value $(0\rho\theta,0\rho)$ is added to the round key of the previous iteration.
It is well known that, for security concerns, the function $\theta$ is required to be an orthomorphism~\cite{vaudenay1999lai}. However,
we do not make use of this hypothesis in our analysis. We strongly use, instead, the assumption that such a function is linear.\\

The general round function of a Lai-Massey cipher is displayed in Fig.~\ref{fig.rounds}.
Notice that the previous formal definition coincides with the classical
definition given by Vaudenay~\cite{vaudenay1999lai}.
Indeed, given $(x,y) \in V\times V$ we have
\[(x,y)\overline{\varepsilon_{i,K}} = \big((x+(x+y)\rho+k_i)\theta, y+(x+y)\rho+k_i\big).\]

\noindent Moreover, it is easy to check that $\overline{\varepsilon_{i,K}}$ is invertible with the following inverse
\[
\overline{\varepsilon_{i,K}}^{\,-1}  = \overline\theta^{-1}\overline{\rho}^{-1}\sigma_{(k_i,k_i)},
\]
where $\overline{\rho}^{-1} = \rhoinvLM$ and
$\overline\theta^{-1} = \thetainvLM$.

\noindent Note that, as in the Feistel Network case, the inverse $\overline{\varepsilon_{i,K}}^{\, -1}$ of the round function $\overline{\varepsilon_{i,K}}$ of
a Lai-Massey cipher does not involve the inverse of $\rho$. We have nonetheless assumed that $\rho$ is bijective, since in our result it is used
as the generator of a group.

\noindent It is worth mentioning that even if IDEA was the starting point for the definition of the LM framework, it does not fit in the presentation of Definition~\ref{LMdef}, since e.g.\ in IDEA the round key is mixed to the state by  using operations different from the XOR.\\

\begin{figure}
\centering
\includegraphics[scale= 1]{LMprim-pics.pdf}
\caption{The $i$-th round function of a Lai-Massey cipher}\label{fig.rounds}
\end{figure}

Let us define the group
\begin{equation}\label{eqgr}
\Gamma(\mathrm{LM}(\rho,\theta)) \deq \Span{\overline{\rho}, \overline\theta, T_{2n}},
\end{equation}
which clearly contains the group $\Span{\overline{\rho}\,\overline\theta, T_{2n}}$ generated by the round functions of a Lai-Massey cipher.
Notice that considering every possible translation in $T_{2n}$ in Eq.\eqref{eqgr} implicitly means
that the study is carried out without considering the role of the particular choice of the key-schedule.
This is however a common practice in the study of the primitivity of the groups generated by the
rounds of a cipher, except for one recent result~\cite{arafeistel}.

In the following section we will prove our main contribution, i.e.\ that $\Gamma(\mathrm{LM}(\rho,\theta))$ is primitive
provided that $\Span{\rho, T_n}$ is primitive. It is worth mentioning again that
$\Span{\rho, T_n}$ is the group generated by the round functions of the SPN whose  function $\rho$ is
the same that composes the building block for the round functions of the LM. In this sense, the primitivity of a
Lai-Massey scheme is reduced to the one of the corresponding SPN.

\section{The primitivity reduction}\label{sec:pri}
\begin{definition}
A subgroup $  U \leq V\times V$ is a \emph{linear block} for $f \in \Sym(V\times V)$ if for each $(v,w) \in V\times V$ there exists $(v',w') \in V \times V$ such
that
\begin{equation}\label{lin_block}
(U +(v,w))f = U+(v',w').
\end{equation} Notice that we can always assume $(v',w') = (v,w)f.$
\end{definition}
In the following result we assume the existence of a linear block $U$ for $\overline{\rho}$. In this case we have
\[(v',w') = (v+w, w+(v+w)\rho)
.\]
 Moreover, it is easy to check that
$U$ is a linear block also for $\overline{\rho}^{-1}$, from which we  obtain
\[(U +(v,w))\overline{\rho}^{-1} = U +(v+w+v\rho,w+v\rho).\]
We use Theorem~\ref{gours} and Corollary~\ref{lemma:psiforphi} to
provide an useful decomposition of $U$. The explicit dependence of all the groups
from $\rho$  is here omitted.
\begin{lemma}\label{cond}
Let $U \leq V \times V$, and let $A,B,C,D \leq V$ and $\phi: A \to C$ an homomorphism such that
$U = \{ (a, a \varphi + d) \mid a \in A, d \in D\}$.
Let us assume that $U$ is a linear block for $\overline{\rho}$.
Then the following conditions hold:
\begin{enumerate}
\item \label{item_DinA} $D \leq A$;
\item \label{item_AphiinA} $A \phi \leq A$;
\item \label{item_DinDphi} $D \phi \leq D$.
\end{enumerate}
\end{lemma}
\begin{proof}
Since $U$ is a linear block for $\overline{\rho}$, taking $u=v=0$ in Eq.~\eqref{lin_block} we have
that for each $a \in A$ and $d \in D$ there exist $x \in A$ and $y \in D$ such that

\begin{eqnarray*}
(a,a\phi+d)\overline{\rho} &=& (a,a\phi+d)\rhoLM \\
&=& (a+a\phi+d,a\phi+d + (a+a\phi+d)\rho)\\ &=& (x,x\phi+y).
\end{eqnarray*}
 If $a=0$, then
$x=d$ and therefore $D \leq A$, so (\ref{item_DinA}) is proved.
If $d=0$, then $x = a + a\phi$ and therefore $A\phi \leq A$, which is (\ref{item_AphiinA}).
As noticed, $U$ is also a linear block for $\overline{\rho}^{-1}$, hence for each $a \in A$ and $d \in D$ there exist $x \in A$ and $y \in D$ such that
\begin{eqnarray*}
(a,a\phi+d) \overline{\rho}^{-1} &=&(a,a\phi+d)\rhoinvLM\\
&=& (a+a\phi+d+a\rho, a\phi+d+a\rho)\\ &=& (x,x\phi + y).
\end{eqnarray*}
If $a=0$, then $y=d\phi+d$, and consequently $d\phi \in D$, which proves (\ref{item_DinDphi}).
\end{proof}
We now use the previous lemma to show our main result on the primitivity of the Lai-Massey scheme. Notice that the result is valid for any choice of $\theta$.
\begin{theorem}\label{thm:main}
If $\Span{\rho, T_n}$ is primitive, then $\Gamma_{\infty}(\mathrm{LM}(\rho,\theta))$ is primitive.
\end{theorem}
\begin{proof}
It is enough to prove that $\Span{\overline{\rho}, T_{2n}}$ is primitive. Let us assume that it is imprimitive, i.e.\ that there exists
a block system $\mathcal U$ for $\Span{\overline{\rho}, T_{2n}}$. Then, from Lemma~\ref{translatioBlocks},  the block system
is
 $\mathcal U = \{U + (v,w) \mid (v,w) \in V\times V\}$  for a non-trivial proper subspace $U$ of $V\times V$.
 Since $U$ is a linear block for $\overline{\rho}$, we have that for each $(v,w) \in V\times V$ and for each $a \in A$ and $d \in D$ there exist
  $x \in A$ and $y \in D$ such that
\begin{equation*}
\begin{split}
  (a+v, a\phi + d+ w)\overline{\rho}  & =\\
  &  = (a+a\phi+d+v+w, (a+a\phi+d+v+w)\rho + a\phi+d+w) \\
 &= (x+v+w, x\phi+y+w+(v+w)\rho)
\end{split}
\end{equation*}
  If $a=0$, then $x=d$ and
  \[
  y+ d\phi +d+(v+w)\rho= (d+v+w)\rho.
  \]
From Lemma~\ref{cond} we have $d\phi \in D$, and therefore, since $\rho$ is bijective, we obtain the equality
\[
(D+v+w) \rho = D+(v+w) \rho.
\]
If $D$ is a non-trivial proper subgroup of $V$, then $\{D+v \mid v \in V\}$ is a block system for $\Span{\rho, T_n}$, which proves our claim.
In order to conclude the proof, let us prove that both the assumptions $D=\{0\}$ and $D=\F_2^n$ lead to contradictions.\\
{$\mathbf{[D = \F_2^n]}$} Since $D \leq A$, then $A= \F_2^n$, and therefore $B=C = \F_2^n$, since from the hypothesis $A/B \cong C/D$. This proves that $U$ is not proper, a contradiction.\\
{$\mathbf{[D = \{0\}]}$} In this case we have $U = \{(a,a\phi) \mid a \in A\}$, and so, for each $(v,w) \in V\times V$ and for each $a \in A$ there
exists $x \in A$ such that
\begin{eqnarray}
(a+v,a\phi+w)\overline{\rho} &=& (a+a\phi+v+w, (a+a\phi+v+w)\rho + a\phi+w) \nonumber\\
 &=& (x+v+w, x\phi+w+(v+w)\rho)\nonumber,
\end{eqnarray}
then $x= a+a\phi$ and
\begin{equation}\label{eqth}
 (a+a\phi+v+w)\rho = a\phi^2+(v+w)\rho
\end{equation}
Since $B\phi \leq D$, then $B\phi = \{0\}$ and so, if $a \in B$ from Eq.~\eqref{eqth} we obtain
\[
 (a+v+w)\rho =(v+w)\rho,
\]
which implies $a= 0$, i.e.\ $B=\{0\}$. This proves that $\phi = \psi : A \rightarrow C$ is an isomorphism.
But $A\phi \leq A$, from Lemma~\ref{cond},  therefore  $	\phi$ is an automorphism of $A$ and,
from Eq.\eqref{eqth}, we obtain
\[
(A+v+w)\rho = A + (v+w)\rho.
\]
In the case under consideration, i.e.\ when $D = \{0\}$, the claim is proved by showing that $\{A+v \mid v \in V\}$ is a block system. This is
addressed in the remainder of the proof.
Let us prove that $A$ is non-trivial and proper. If $A = \{0\}$, then $C = D = \{0\}$, and so also $B = \{0\}$, therefore $U$ is trivial, a contradiction. To conclude, let us assume $A = \F_2^n$. From Eq.~\eqref{eqth}, setting $v=w=0$, we obtain that $a\phi^2=(a+a\phi)\rho$. If $a \in A$ is a fixed point of $\phi$, i.e.\ $a = a\phi$, then $(a+a\phi)\rho = 0$, and so $a\phi^2 = 0$. Therefore $a = 0$, since $\phi$ is an automorphism. We have proved that $\phi$ is fixed-point free, except for the trivial one $a=0$, from which it follows that  $\mbb1 + \phi$ is injective and, since $A \phi \leq A$, we have
$\{a+a\phi \mid a \in A\} = A = \F_2^n$. Therefore $\rho$ is linear on $\F_2^n$, a contradiction.
\end{proof}
We have already observed that $\Span{\rho, T_n}$ is the group $\Gamma_{\infty}(\Phi)$ generated by the rounds of the Substitution Permutation Network $\Phi$ whose
$i$-th round function is  $\varepsilon_{i,K} = \rho\sigma_{k_i}$ for some $\rho = \gamma\lambda \in \Sym(V)\setminus \AGL(V)$. The conditions which prove $\Gamma_{\infty}(\Phi)$  primitive
in the case of the SPNs has been extensively studied, due to the popularity of the design framework. It has been proved that the primitivity is granted when the confusion
layer $\gamma$ of $\rho$ satisfies some well-established
conditions of non-linearity, provided that $\lambda$ provides sufficient diffusion. The interested reader
may refer to Caranti et al.~\cite{carantiprimitive}, where the primitivity of SPNs is studied in the larger context of \emph{translation-based} ciphers.
\subsection*{Different rounds}
In our analysis we have assumed that, for sake of simplicity, in both the cases of SPNs and of LMs the 	\emph{same} round function is applied to each round,
with the only exception of the round key. It is worth being mentioned here that almost no real cipher can exactly fit this model, due to the
natural need to differentiate the encryption routine by introducing some atypical rounds, for both security and efficiency reasons (see e.g.\ the first and
last rounds of AES~\cite{aes}). However, this does not represent an actual limitation when it comes to evaluate the security of a design
from the point of view of the group generated by the round function. If we assume, indeed, that our target SPN and LM feature different round functions
for each round, then the primitivity of $\Span{\overline{\rho}_i, \overline\theta_i, T_{2n}}$ can be reduced to that of $\Span{\rho_i, T}$, proceeding as in~Theorem~\ref{thm:main}.
When this is true for one round $i$, then the full group
\begin{equation}\label{eqgr2}
\Span{\Span{\overline{\rho}_i, \overline\theta_i, T_{2n}}\mid 1 \leq i \leq r}
\end{equation} is primitive.

Assuming that the definition of SPN and Definition~\ref{LMdef} allow different round functions for each round, then the following consequence of Theorem~\ref{thm:main}
can be derived.
\begin{corollary}
If a given round of an SPN generates a primitive group, then the group defined as in Eq.~\eqref{eqgr2} generated by the rounds of the corresponding LM is primitive.
\end{corollary}

\subsection*{2-transitivity}
It is well known that every 2-transitive group is primitive. It may be natural to ask whether an alternative version of Theorem~\ref{thm:main}
could be obtained, where primitivity is replaced by 2-transitivity. In the case $n=3$, we have exhaustively searched using \texttt{Magma}~\cite{magma} for  all the non-linear functions $\rho$
such that $\Span{\rho, T_3}$ is a 2-transitive group.  For all of those, $\Span{\overline{\rho}, T_6}$ is always 2-transitive. Setting $n=4$, a partial search in the space led to no counterexamples.
A brute-force search when $n\geq 4$ is out of the scopes of this work since requires code optimization and a faster programming language.
On the other side, it is well known that the $2$-transitivity of $\Gamma_{\infty}(\mathrm{LM}(\rho,\theta))$ is equivalent to the transitivity of the stabilizer of $(0,0)$
 on $V \times V\setminus\{(0,0)\}$. However, a description of $\Gamma_{\infty}(\mathrm{LM}(\rho,\theta))_{(0,0)}$ is not
easily obtained from $\Span{\rho, T_n}_0$ due to the non-linear dependence introduced by the Lai-Massey formal operator.
For this reasons, at the time of writing we are not able to conjecture that the 2-transitivity of $\Span{\rho, T_n}$ implies
that $\Gamma_{\infty}(\mathrm{LM}(\rho,\theta))$ is 2-transitive, and we leave this as an open problem.

\section*{Acknowledgment}
The authors are thankful to Massimiliano Sala and Ralph Wernsdorf for some useful discussions and suggestions.
\bibliographystyle{amsalpha}