# Swift chiral quantum walks

Massimo Frigerio 1,2, Matteo G. A. Paris 1,2 1 Quantum Technology Lab,
Dipartimento di Fisica Aldo Pontremoli, Università degli Studi di Milano,
I-20133 Milano, Italy
2 INFN, Sezione di Milano, I-20133 Milano, Italy

###### Abstract

A continuous-time quantum walk (CTQW) is sedentary if the return probability
in the starting vertex is close to one at all times. Recent results imply
that, when starting from a maximal degree vertex, the CTQW dynamics generated
by the Laplacian and adjacency matrices are typically sedentary. In this
paper, we show that the addition of appropriate complex phases to the edges of
the graph, defining a _chiral_ CTQW, can cure sedentarity and lead to _swift
chiral quantum walks_ of the adjacency type, which bring the return
probability to zero in the shortest time possible. We also provide a no-go
theorem for swift chiral CTQWs of the Laplacian type. Our results provide one
of the first, general characterization of tasks that can and cannot be
achieved with chiral CTQWs.

###### keywords:

continuous quantum walks , sedentary walks , regular graphs

###### MSC:

05C50 , 05C81 , 15A16 , 81P45

##  1 Introduction

In the physical modeling of quantum discrete structures, the notion of
continuous-time quantum walks (CTQWs) is widely adopted as a convenient
mathematical construct [1, 2, 3, 4, 5, 6, 7]. Their applications range from
quantum computation [8] and quantum search [9, 10] to the study of perfect
state transfer [11, 12, 13, 14] and quantum transport [15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28]. Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$
be a simple, connected, unweighted and undirected graph with vertex set
$\mathcal{V}$ and edge set $\mathcal{E}$. Let $|\mathcal{V}|=N$ be the order
of $\mathcal{G}$ and $\mathbf{A}$ its adjacency matrix, once a numbering of
the vertices has been assigned, i.e. $\mathbf{A}_{jk}=1$ if vertices $j$ and
$k$ are connected, while all the other entries (including the diagonal ones)
are null. We will denote by $\mathbf{L}=\mathbf{D}-\mathbf{A}$ the Laplacian
of $\mathcal{G}$, where $\mathbf{D}$ is the diagonal matrix encoding the
(positive) degrees of the vertices of $\mathcal{G}$ [29, 30]. In its simplest
form, a quantum walk on $\mathcal{G}$ is described by a Hilbert space
isomorphic to $\mathds{C}^{N}$ with a reference basis formed by vectors
$\underline{e}_{v}$ that are the characteristic vectors of the vertices of
$\mathcal{G}$ (the vertex basis), and by a one-parameter subgroup of the
unitary group on $\mathds{C}^{N}$ generated by either $\mathbf{A}$ or
$\mathbf{L}$ [31] and effecting the time evolution of the vectors in the
Hilbert space. More concretely, given an initial vector
$\underline{\psi}_{0}=\underline{\psi}(0)$, its evolution will be governed by
the Schrödinger equation [32]:

$i\dfrac{d}{dt}\underline{\psi}(t)\ =\ \mathbf{H}\ \underline{\psi}(t)$ (1)

where $\mathbf{H}$ can be $\mathbf{A}$ or $\mathbf{L}$, and whose solution is
simply:

$\underline{\psi}(t)\ =\ e^{-i\mathbf{H}t}\underline{\psi}_{0}$ (2)

Recently, more generic hermitian generators, still reflecting the connectivity
of $\mathcal{G}$, have been considered [33, 34, 35, 36]. Specifically, a
_chiral adjacency matrix_ $\tilde{\mathbf{A}}$ on $\mathcal{G}$ is an $N\times
N$ hermitian matrix such that
$\mathbf{A}_{jk}=1\implies\tilde{\mathbf{A}}_{jk}=e^{i\theta_{jk}}$ with
$\theta_{jk}\in[0,2\pi)$ and
$\mathbf{A}_{jk}=0\implies\tilde{\mathbf{A}}_{jk}=0$
($\theta_{jk}=-\theta_{kj}$ is required by the hermiticity condition). In
other words, a generic chiral adjacency matrix $\tilde{\mathbf{A}}$ is
obtained by replacing each nonzero entry of $\mathbf{A}$ with a generic
complex phase and enforcing that the resulting matrix is hermitian. A _chiral
Laplacian_ on $\mathcal{G}$ is an hermitian matrix
$\tilde{\mathbf{L}}=\mathbf{D}-\tilde{\mathbf{A}}$ where $\tilde{\mathbf{A}}$
is a chiral adjacency matrix. Finally, a _chiral Hamiltonian_ on $\mathcal{G}$
is an hermitian matrix of the form
$\mathbf{H}=\tilde{\mathbf{D}}+\tilde{\mathbf{A}}$ where $\tilde{\mathbf{D}}$
is a generic, real diagonal matrix and $\tilde{\mathbf{A}}$ again a chiral
adjacency matrix. We will say that a chiral quantum walk is _of the adjacency
type_ (resp. _of the Laplacian type_) if it is generated by a chiral adjacency
matrix (resp. a chiral Laplacian). Among others, the typically relevant
quantities for these systems are transport probabilities between two vertices
$j$ and $k$, defined by:

$p^{\mathbf{H}}_{j\to k}(t)\ =\
|\underline{e}_{k}^{\dagger}e^{-it\mathbf{H}}\underline{e}_{j}|^{2}$ (3)

where now $\mathbf{H}$ can be a generic chiral Hamiltonian on the graph and
$|\cdot|$ is the modulus of a complex number. Given a vertex $v\in\mathcal{G}$
and a numbering of the vertices, its characteristic vector $\underline{e}_{v}$
is the vector in the canonical basis of $\mathds{C}^{N}$ whose only nonzero
entry is in correspondence to the number associated with $v$.

###  1.1 Sedentarity in Laplacian and adjacency continuous-time quantum walks

To set the stage for our results, it is useful to introduce some nomenclature
for graphs with maximally connected vertices: a _cone_ on a graph
$\mathcal{G}^{\prime}$ is a graph $\mathcal{G}$ obtained by adding a vertex
$v$ to the vertex set of $\mathcal{G}^{\prime}$ and connecting it to every
vertex in $\mathcal{G}^{\prime}$. Recently, a number of results for both
Laplacian and adjacency type CTQWs [37, 38] indicate that the evolution
starting from maximally connected vertices can be plagued by a sedentary
behaviour, meaning that the return probability to the initial vertex stays
close to $1$ at all times if its degree is sufficiently large. The maximally
connected vertex $v$ will be called the _apex_ of the cone. For Laplacian
quantum walks this is always the case, since their evolution from a maximally
connected vertex in any graph with $N+1$ vertices is the same as the one from
the center (labelled by $1$) of an $N$-pointed star graph, whose return
probability is [39]:

$p^{L}_{1\to 1}(t)\ =\ 1-2\frac{N-2}{(N-1)^{2}}\left[1-\cos(Nt)\right]$ (4)

and it is clearly sedentary, since $p^{L}_{1\to 1}(t)\rightarrow 1\ \forall
t\in\mathds{R}$ as $N\to+\infty$. This general result was proved in [38].

Concerning adjacency CTQWs, instead, the situation is currently less clear.
The dynamics starting from the central vertex of the $N$-pointed star graph in
this case is not sedentary, nor it is the one which starts from the center of
the wheel graph. Moreover, each adjacency CTQW starting from a maximally
connected vertex could yield a different evolution, depending upon the
connectivity of the remaining vertices. However, it was shown in [37] that
adjacency quantum walks from the apex of cones over several infinite families
of graphs are sedentary. Importantly, this is the case when the cone is over
$m$-regular graphs with $N$ vertices and the degree $m$ grows faster than
linearly with $N$.

In this paper, we show that the addition of appropriate complex phases to the
edges of several graphs eliminates sedentarity and allows one to obtain _swift
chiral quantum walks_ of the adjacency type, where the returning probability
goes to zero in the shortest time possible. We also provide a no-go theorem
for swift chiral CTQWs of the Laplacian type. Overall, our results provide one
of the first, general characterization of tasks that can and cannot be
achieved with chiral CTQWs and they hint at several challenging graph-
theoretical questions concerning the existence of swift phases configurations.

##  2 Results for adjacency quantum walks

Let us consider a quantum walk starting at the apex of a cone graph
$\mathcal{G}$ over an $m$-regular graph of $N$ vertices, whose state vector
will be labelled $\underline{e}_{1}$. Since this vertex is maximally
connected, the adjacency matrix $\mathbf{A}$ of the full graph will have the
following structure:

$\mathbf{A}\ =\ \left(\begin{array}[]{c|cccc}0&1&1&1&\dots\\\ \hline\cr
1&&&&\\\ 1&&&&\\\ 1&&&\mathbf{A^{\prime}}&\\\ \vdots&&&&\\\
\end{array}\right)$ (5)

where $\mathbf{A^{\prime}}$ is the adjacency matrix of the $m$-regular graph
$\mathcal{G}^{\prime}$. Since each vertex has exactly $m$ neighbours, calling
$\underline{1}_{N}$ the vectors of all ones in the subspace of
$\mathcal{G}^{\prime}$ we have:

$\mathbf{A^{\prime}}\underline{1}_{N}\ =\ m\underline{1}_{N}$ (6)

But notice that $\mathbf{A}$ maps $\underline{e}_{1}$ to the vector
$\underline{e}^{\prime}=(0,1,1,\cdots)^{T}$ which coincides with
$\underline{1}_{N}$ on $\mathbf{A^{\prime}}$ and is orthogonal to
$\underline{e}_{1}$. Moreover, it is clear from Eq.(6) that:

$\mathbf{A}\underline{e}^{\prime}\ =\ N\underline{e}_{1}\ +\
m\underline{e}^{\prime}$ (7)

Therefore, calling
$\underline{e}_{E}=\frac{1}{\sqrt{N}}\underline{e}^{\prime}$ the normalized
associated with $\underline{e}^{\prime}$, $\mathbf{A}$ reduces to a simple
$2\times 2$ block in the space spanned by
$\\{\underline{e}_{1},\underline{e}_{E}\\}$ [40]:

$\mathbf{A}_{\mathrm{red}}=\left(\begin{array}[]{cc}0&\sqrt{N}\\\
\sqrt{N}&m\end{array}\right)$ (8)

This is easily diagonalized, and the resulting return probability starting
from $\underline{e}_{1}$ is given by:

$p^{\mathbf{A}}_{1\to 1}(t)\ =\
1-\frac{2N}{m^{2}+4N}\left[1-\cos(\sqrt{m^{2}+4N}t)\right]$ (9)

whereas, with probability $1-p^{\mathbf{A}}_{1\to 1}(t)$ the walker will be in
the state $\underline{e}_{E}$ orthogonal to $\underline{e}_{1}$, from which
all the other site-to-site transition probabilities follow.

Eq.(9) can be regarded as a partial result on the adjacency version of the
general theorem (4) for Laplacian quantum walks. It states that the dynamics
starting from the apex of a cone over _any_ $m$-regular graph is fully
specified by $m$ and the number of vertices of the underlying graph $N$
(notice that the full graph has $N+1$ vertices instead). If we define a family
of regular graphs such that the degree scales as $m\sim
O(N^{{\color[rgb]{1,0,0}\frac{1}{2}}+\alpha})$ with $\alpha>0$, it follows
that $p^{A}_{1\to 1}$ stays very close to $1$ at all times, for large enough
$N$. This construction leads to a result originally presented in [37].

##  3 Swift chiral quantum walks

Now suppose that we can attach complex phases to the edges of the $m$-regular
graph $\mathcal{G}^{\prime}$ such that the resulting chiral adjacency matrix
$\tilde{\mathbf{A}}$, which would substitute $\mathbf{A^{\prime}}$ in Eq.(5),
fulfils the following condition:

$\tilde{\mathbf{A}}\underline{1}_{N}\ =\ 0$ (10)

that is to say, the phases conjure in such a way that the sum of each row of
$\tilde{\mathbf{A}}$ is zero. Retracing the steps to arrive at Eq.(9), we find
the following reduced Hamiltonian for the chiral QW on the cone in the
subspace spanned by $\\{\underline{e}_{1},\underline{e}_{E}\\}$:

$\mathbf{H}_{\mathrm{red}}=\left(\begin{array}[]{cc}0&\sqrt{N}\\\
\sqrt{N}&0\end{array}\right)$ (11)

from which the return probability to the starting, maximally connected vertex
is calculated to be:

$p^{\tilde{\mathbf{A}}}_{1\to 1}(t)\ =\ \cos^{2}(\sqrt{N}t)$ (12)

Notice that this is the same return probability that would result from the
adjacency quantum walk starting from the center of an $N$-pointed star graph,
which cannot support chiral quantum walks since it is a tree graph. This
equation motivates the following definition:

######  Definition 1.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a simple, connected and
undirected graph, let $v\in\mathcal{V}$ be a vertex of $\mathcal{G}$ and
denote by $N$ the cardinality of the set of neighbours of $v$ in
$\mathcal{G}$. Given a chiral Hamiltonian $\mathbf{H}$ on $\mathcal{G}$, it is
said to generate a _swift chiral quantum walk_ starting from $v$ in
$\mathcal{G}$ if:

$\forall t\geq 0:\ \
|\underline{e}_{v}^{\dagger}e^{-i\mathbf{H}t}\underline{e}_{v}|^{2}\ =\
\cos^{2}\left(\sqrt{N}t\right)$ (13)

Therefore, whenever it is possible to attach phases to the edges such that
Eq.(10) is fulfilled, we obtain a similar result to the one which is valid for
the Laplacian quantum walks, in the sense that all the adjacency-type _swift_
chiral quantum walks starting from a maximally connected vertex have the same
dynamics as that of the adjacency quantum walk on the star graph. Notice,
however, that Laplacian quantum walks tend to stay on the initial vertex, if
this has maximal degree, whereas swift quantum walks abandon it fast. In the
following, we will formalize this observation and the nomenclature of _swift
chiral quantum walks_ with rigorous and general results.

_Remark._ If $\mathcal{G}^{\prime}$ has a vertex of degree $1$, then Eq.(10)
cannot be fulfilled by any assignment of phases on its edges.

######  Theorem 1.

Let $\mathcal{G}$ be a graph and let $v$ be a vertex of $\mathcal{G}$ with
degree $N$. Out of all the chiral quantum walks starting from $v$ in
$\mathcal{G}$ (with generic diagonal entries of the chiral Hamiltonian), a
_swift chiral quantum walk_ , when it exists, is the fastest at leaving $v$,
in the sense that it evolves to a state orthogonal to $v$ in a time
$\tau_{s}=\frac{\pi}{2\sqrt{N}}$ which achieves the shortest quantum speed
limit among all chiral evolutions starting from $v$ on $\mathcal{G}$.

###### Proof.

The speed limit to completely leave $v$ is the speed limit to go to a generic
state orthogonal to $\underline{e}_{v}$. The generic formula of the quantum
speed limit for orthogonal final state is [41, 42, 43, 44]:

$\tau_{QSL}:=\max\left\\{\frac{\pi}{2\Delta\mathbf{H}}\ ,\
\frac{\pi}{2(\langle\mathbf{H}\rangle-E_{0})}\right\\}$ (14)

where
$\Delta\mathbf{H}=\sqrt{\langle\mathbf{H}^{2}\rangle-\langle\mathbf{H}\rangle^{2}}$
is the standard deviation of energy on the orbit of $\underline{e}_{v}$,
$\langle\mathbf{H}\rangle=\underline{e}_{v}^{\dagger}\mathbf{H}\underline{e}_{v}$
its average energy and $E_{0}$ is the ground state’s energy. Notice that the
quantum speed limit is defined for a _fixed_ Hamiltonian, and we are looking
for the _smallest_ quantum speed limit over all chiral Hamiltonians on
$\mathcal{G}$.

But for any localized state $|v\rangle$ with degree $N$ and any chiral
Hamiltonian $\mathbf{H}$ on $\mathcal{G}$, it is always true that
$\Delta\mathbf{H}=\sqrt{N}$. Indeed, let
$\underline{e}_{v}^{\dagger}\mathbf{H}\underline{e}_{v}=d$, then
$\underline{e}_{v}^{\dagger}\mathbf{H}^{2}\underline{e}_{v}=\underline{h}_{v}^{\dagger}\underline{h}_{v}=d^{2}+N$
where $\underline{h}_{v}$ is the $v$-th row of $\mathbf{H}$, whose $v$-th
entry is $d$ and all the other non-zero entries are precisely $N$ complex
phases. Therefore we can rewrite:

$\tau_{QSL}:=\max\left\\{\frac{\pi}{2\sqrt{N}}\ ,\
\frac{\pi}{2(-E_{0})}\right\\}\ =\ \max\left\\{\tau_{s}\ ,\
\frac{\pi}{2(-E_{0})}\right\\}$ (15)

To conclude the proof, let us suppose that there is a better chiral
Hamiltonian for which the second expression of Eq.(15) applies, which, because
of the $\max$, implies that $\tau_{QSL}>\tau_{s}$. But since we supposed that
a swift chiral quantum walk exists, we know that $\tau_{s}$ can be achieved by
the swift chiral Hamiltonian, which shows that the second expression in
Eq.(15) is never the best quantum speed limit whenever a swift chiral quantum
walk exists. As a byproduct, we deduce that for swift chiral quantum walks the
ground state energy fulfils $E_{0}\leq-\sqrt{N}$. ∎

_Remark._ It is not immediate to conclude that any chiral quantum walk which
achieves this limit $\tau_{s}$ must be a swift chiral quantum walk since, a
priori, the specific form of the return probability need not be given by
Eq.(13).

It is a very interesting question to ask when is it possible to construct a
swift chiral quantum walk (of the adjacency type) starting from maximally
connected vertices in any graph $\mathcal{G}$ having no vertex with degree $2$
or, equivalently, to find a chiral adjacency matrix fulfilling Eq.(10) on any
graph $\mathcal{G}^{\prime}$ having no vertex of degree $1$. We shall
introduce the following definition:

######  Definition 2.

Let $\mathcal{G}^{\prime}$ be a graph of order $N$ and suppose there exists a
chiral Hamiltonian $\mathbf{H}$ on $\mathcal{G}^{\prime}$ with eigenvector
$\mathbf{1}_{N}$ and eigenvalue $0$ (where $\mathbf{1}_{N}\in\mathds{R}^{N}$
is the vector of all ones) or, equivalently, such that the sum of each row of
$\mathbf{H}$ is zero. We will say that the phases assigned to the edges of
$\mathcal{G}^{\prime}$ by $\mathbf{H}$ provide a _swift phases configuration_
for $\mathcal{G}^{\prime}$.

We could not provide general criteria for a graph (with minimal degree $\geq
2$) to admit a swift phases configuration. Nevertheless, we shall prove that
many infinite families of graphs admit such a construction. Missing proofs can
be found in Appendix A.

######  Theorem 2.

If all the vertices of $\mathcal{G}^{\prime}$ have even degree, then it admits
a swift phases configuration.

######  Theorem 3.

A $3$-regular graph $\mathcal{G}^{\prime}$ admits a swift phases configuration
if and only if one of the following equivalent conditions is met:

  1. 1.

$\mathcal{G}^{\prime}$ has a perfect matching

  2. 2.

$\mathcal{G}^{\prime}$ can be covered with vertex disjoint cycles (it has a
$2$-factor)

We recall that a perfect matching of $\mathcal{G}^{\prime}$ is a $1$-factor,
i.e. a partition of all the vertices in pairs such that the vertices in each
pair are adjacent in $\mathcal{G}^{\prime}$ and each vertex appears in just a
single pair. Moreover, we say that $\mathcal{G}^{\prime}$ can be covered with
vertex disjoint cycles if there exists a set of cycles that are subgraphs of
$\mathcal{G}^{\prime}$, whose union covers all the vertices of
$\mathcal{G}^{\prime}$ and such that each vertex of $\mathcal{G}^{\prime}$
belongs to a single cycle. This is also called a $2$-factor of
$\mathcal{G}^{\prime}$. Notice that Theorem 3 also implies that there are
regular graphs not admitting a swift phases configuration: an example is
provided by the graph in Fig. 1.

Figure 1: A $3$-regular graph having no perfect matching and therefore no
swift phases configuration.

######  Corollary 1.

A bridgeless $3$-regular graph always admits a swift phases configuration.

###### Proof.

Recall that a graph is $k$-edge connected if $k$ is the minimum number of
edges to be deleted in order to make the graph disconnected. A non connected
graph is bridgless if $k>1$ for each connected component. Petersen theorem
ensures that bridgless $3$-regular graphs admit perfect matching and the
thesis follows from Therorem 3. ∎

Notice that the converse is not true: there exist $3$-regular graphs with
perfect matching and with bridges. An example is provided in Fig. 2.

Figure 2: A $3$-regular graph with a bridge and a perfect matching, thus
admitting a swift phases configuration.

######  Corollary 2.

An hamiltonian $3$-regular graph always admits a swift phases configuration.

###### Proof.

A graph $\mathcal{G}^{\prime}$ is said to be hamiltonian if it admits a
hamiltonian cycle, a closed path passing through each vertex of
$\mathcal{G}^{\prime}$ exactly once. The thesis is then a direct consequence
of Theorem 3 ∎

######  Theorem 4.

Complete graphs $K_{N}$ and bipartite complete graphs $K_{N_{1},N_{2}}$ admit
a swift phases configuration for all integers $N\geq 3$ and $N_{1},N_{2}\geq
2$.

######  Lemma 1.

Let $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ be two graphs such that a cone
with apex $v$ on $\mathcal{G}_{1}$ (resp. $\mathcal{G}_{2}$) admits a swift
chiral quantum walk starting from $v$. Then also the cone over their disjoint
union $\mathcal{G}=\mathcal{G}_{1}\bigcup\mathcal{G}_{2}$ admits a swift
chiral quantum walk starting from its apex.

##  4 Gauge fixing and uniqueness

A quasi-gauge transformation for a chiral quantum walk [33, 34] is a unitary
transformation $\mathbf{U}_{g}$ that is diagonal in the vertex basis and acts
on chiral Hamiltonians $\mathbf{H}$ as
$\mathbf{H}^{\prime}=\mathbf{U}_{g}\mathbf{H}\mathbf{U}_{g}^{\dagger}$. They
have the important property of preserving site-to-site transport probabilities
[45, 35]. Therefore, as far as we focus on these quantities, the set of chiral
Hamiltonians on a graph $\mathcal{G}$ can be partitioned into equivalence
classes, such that any two matrices belonging to the same class are linked by
a quasi-gauge transformation. Whenever $\mathcal{G}$ is a tree graph (i.e. it
has no loops), all chiral adjacency matrices on it belong to the same
equivalence class, thus they generate site-to-site transport probabilities
identical to those generated by the standard adjacency matrix of the graph
(and similarly for chiral Laplacians and, more generically, chiral
Hamiltonians for a fixed choice of diagonal elements). In contrast, as soon as
$\mathcal{G}$ has at least one loop, there will be an uncountable number of
distinct equivalence classes, which can be indexed by the sums of the phases
along each loop of the graph, for an initially fixed orientation.

In the light of these observations and before discussing the uniqueness of the
swift chiral quantum walk construction on a given graph and for a given
starting vertex, it is useful to fix a gauge. Indeed, since quasi-gauge
transformations do not affect site-to-site transport probabilities, they will
transform a swift chiral quantum walk into another one, without modifying the
defining condition Eq.(12). Let us consider the case of a cone $\mathcal{G}$,
with apex labelled by $1$, over a graph $\mathcal{G}^{\prime}$ of order $N$.
The first column $\underline{h}_{1}$ of a chiral Hamiltonian
$\tilde{\mathbf{H}}$ on $\mathcal{G}$ will have the following structure
$\underline{h}_{1}=(d_{1},\underline{h^{\prime}}_{1})^{T}$ where
$d_{1}\in\mathds{R}$ and $\underline{h}^{\prime}_{1}\in\mathds{C}^{N}$ is a
vector whose entries are all complex numbers of modulus 1. Then, a gauge-
fixing can be imposed by asking that
$\underline{h^{\prime}}_{1}=(1,1,...,1)^{T}\in\mathds{R}^{N}$; indeed, in any
class of gauge-equivalent chiral Hamiltonians, there will be just one
representative fulfilling this condition. With this gauge choice, a chiral
adjacency matrix $\tilde{\mathbf{A}}$ on $\mathcal{G}$ will generate a swift
chiral quantum walk from $1$ if and only if the corresponding submatrix
$\tilde{\mathbf{A}}^{\prime}$ (which is a chiral adjacency matrix on
$\mathcal{G}^{\prime}$) is such that the sum of each of its rows (and
therefore of each column) is zero.

######  Theorem 5.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a simple, connected and
undirected graph with $|\mathcal{V}|=N$ vertices. Let $v\in\mathcal{V}$ be a
generic vertex of $\mathcal{G}$ and denote $\mathcal{G}_{v}$ the subgraph of
$\mathcal{G}$ obtained by keeping $v$ and all its neighbours, and deleting
every other vertex and the respective edges. Then there exists a _swift chiral
quantum walk_ (of the adjacency type) starting from $v$ in $\mathcal{G}$ if
and only if the following conditions hold:

  1. (a)

There is a swift chiral quantum walk starting from $v$ in the cone
$\mathcal{G}_{v}$

  2. (b)

Any vertex $v^{\prime}\in\mathcal{G}$ which is not a neighbour of $v$ has
either $0$ or $\geq 2$ common neighbours with $v$.

###### Proof.

_Sufficiency of conditions._ Let us call $N^{\prime}$ the cardinality of the
subset of $\mathcal{V}$ consisting of the neighbors of $v$, so that there are
exactly $N-N^{\prime}-1$ vertices in $\mathcal{G}$ which are not connected to
$v$. Let us enumerate with $1$ the vertex $v$, with progressive integers from
$2$ to $N^{\prime}+1$ the neighbours of $\mathcal{V}$ and with the remaining
integers from $N^{\prime}+2$ to $N$ the rest of the vertices. Then the
adjacency matrix of $\mathcal{G}$ will be written in the following block form:

$\mathbf{A}\ =\
\left(\begin{array}[]{c|ccc|ccc}0&1&{\color[rgb]{1,0,0}\cdots}&{\color[rgb]{1,0,0}1}&0&{\color[rgb]{1,0,0}\cdots}&{\color[rgb]{1,0,0}0}\\\
\hline\cr 1&&&&\\\
{\color[rgb]{1,0,0}\vdots}&&\mathbf{A^{\prime}}&&&\mathbf{B}^{\mathrm{T}}&\\\
{\color[rgb]{1,0,0}1}&&&&\\\ \hline\cr 0&&&&&&\\\
{\color[rgb]{1,0,0}\vdots}&&\mathbf{B}&&&\mathbf{A^{\prime\prime}}&\\\
{\color[rgb]{1,0,0}0}&&&&&&\\\ \end{array}\right)$ (16)

where $\mathbf{B}$ is an $(N-N^{\prime}-1)\times N^{\prime}$ matrix (whose
entries are either $0$ or $1$ since $\mathbf{A}$ is an adjacency matrix) and
$\mathbf{B}^{\mathrm{T}}$ is its transpose. Calling
$\underline{e}_{1}=(1,0,0,0...)^{T}$ the vector associated with vertex $v$, we
have:

$\mathbf{A}\underline{e}_{1}\ =\ \sqrt{N^{\prime}}\underline{e}_{v}\ =\
0\oplus\mathbf{1}_{N^{\prime}}\oplus\mathbf{0}_{N-N^{\prime}-1}\in\mathds{C}\oplus\mathds{C}^{N^{\prime}}\oplus\mathds{C}^{N-N^{\prime}-1}\
\simeq\ \mathds{C}^{N}$ (17)

where
$\underline{e}_{v}=\frac{1}{\sqrt{N^{\prime}}}(0,1,\cdots,1,0,\cdots,0)^{T}$.
By condition (a), we can attach complex phases to the nonzero entries of
$\mathbf{A^{\prime}}$ to get a chiral Hamiltonian $\mathbf{H^{\prime}}$
reflecting the same graph topology of $\mathbf{A^{\prime}}$, and such that
$\mathbf{H^{\prime}}\mathbf{1}_{N^{\prime}}=0$. As previously discussed, we
can always assume a gauge choice that keeps the first row and column of
$\mathbf{A}$ as in Eq.(16): if $\mathcal{G}$ is not a cone, this will not
fully fix the gauge since additional local phase changes can be made on the
vertices not directly connected with $1$. Moreover, letting $j>N^{\prime}+1$,
by condition (b) we can deduce that the $(j-N^{\prime}-1)$th row of
$\mathbf{B}$ contains either with $N^{\prime}$ zeroes _or_ at least two
entries of the row are $1$s. Therefore, by replacing the ones with the roots
of unity whenever a row of $\mathbf{B}$ is not the null vector, we can always
arrange a matrix of phases $\mathbf{X}$ whose nonzero entries are in the same
place as those of $\mathbf{B}$ and which fulfils
$\mathbf{X}\mathbf{1}_{N^{\prime}}=0$. Combining these facts, we can then
define a chiral Hamiltonian:

$\mathbf{H}_{v}\ =\ \left(\begin{array}[]{c|ccc|ccc}0&1&1&\cdots&0&0&\cdots\\\
\hline\cr 1&&&&\\\ 1&&\mathbf{H^{\prime}}&&&\mathbf{X}^{\dagger}&\\\
\vdots&&&&\\\ \hline\cr 0&&&&&&\\\
0&&\mathbf{X}&&&\mathbf{A^{\prime\prime}}&\\\ \vdots&&&&&&\\\
\end{array}\right)$ (18)

describing the same graph $\mathcal{G}$, which reduces to a $2\times 2$ real
block in the subspace generated by
$\\{\underline{e}_{1},\underline{e}_{v}\\}$:

$\tilde{\mathbf{H}}_{v}=\left(\begin{array}[]{cc}0&\sqrt{N^{\prime}}\\\
\sqrt{N^{\prime}}&0\end{array}\right)$ (19)

and therefore the chiral dynamics generated by $\mathbf{H}_{v}$ and starting
from $v$ is swift.

_Necessity of conditions._
Considering Eq.(13), it is clear that the returning probability can take the
form of a squared cosine if and only if the initial state is a superposition
of only two energy eigenstates, such that its dynamics is confined to a two-
dimensional subspace of the full Hilbert space. Moreover, any chiral
Hamiltonian $\mathbf{H}$ (of adjacency type) on the unweighted graph, upon
acting on $\underline{e}_{1}$ will yield a flat state with support on the
neighbours of vertex $1$ and orthogonal to it, coinciding with the first
column $\underline{h}_{1}$ of $\mathbf{H}$. Let
$\underline{e}_{E}=\frac{1}{\sqrt{N^{\prime}}}\underline{h}_{1}$ be the
normalized vector corresponding to $\underline{h}_{1}$; then we have:

$\displaystyle\mathbf{H}\underline{e}_{1}\ =\
\sqrt{N^{\prime}}\underline{e}_{E}$ (20)
$\displaystyle\mathbf{H}\underline{e}_{E}\ =\
\sqrt{N^{\prime}}\underline{e}_{1}\ +\ \underline{e^{\prime}}_{E}$

where in the second equation $\underline{e^{\prime}}_{E}$ is a generic vector
orthogonal to $\underline{e}_{1}$ (and possibly with support also outside the
neighbours of vertex $1$)111Notice that this is valid even if
$\underline{e}_{E}$ is a vector with complex entries. . But the conditions
that the dynamics reduces to a two-dimensional subspace and that the return
probability coincides with Eq.(13) immediately imply that
$\underline{e^{\prime}}_{E}=0$, from which the two conditions of the theorem
follow. ∎

##  5 No-go theorems for Laplacian quantum walks

As was reminded in the introduction, continuous-time quantum walks generated
by the Laplacian and starting from a vertex with maximal degree all have the
same dynamics and they are sedentary. If we allow for an oracle, this
behaviour can be easily fixed to get a swift (non-chiral) quantum walk.
Indeed, let $\mathbf{L}$ be the Laplacian of a graph $\mathcal{G}$ which is a
cone over some other graph $\mathcal{G}^{\prime}$, let us label with $1$ the
apex of the cone, with a corresponding state vector $\underline{e}_{1}$, and
call $N$ its degree. Then if we define:

$\mathbf{\tilde{L}}\ :=\ \mathbf{L}-{\color[rgb]{1,0,0}(N-1)}\mathbf{P}_{1}$
(21)

where $\mathbf{P}_{1}$ is the orthogonal projector on $\underline{e}_{1}$, it
is straightforward to see that in the reduced basis generated from
$\underline{e}_{1}$ the matrix $\mathbf{\tilde{L}}$ takes the same form of
Eq.(11), apart for the addition of an immaterial identity matrix and a sign
difference, therefore the returning probability is that of a swift quantum
walk, Eq.(12). Notice that this is equivalent to Grover’s Hamiltonian for
quantum search on a graph, generalized to the case where just the target
vertex has maximal degree222Usually Grover’s algorithm on quantum walks just
considers the case of complete graphs..

However, in the spirit of using chiral quantum walks and the phases degrees of
freedom, it is interesting to ask whether the oracle of Eq.(21) can be
replaced by a suitable phases configuration while keeping the swift dynamics.
In general, this is not possible. Indeed, we already proved that to get the
swift evolution, the reduced Hamiltonian in the reduced basis of the starting
state vector $\underline{e}_{1}$ should be $2\times 2$, and by enforcing the
diagonal elements of the Laplacian and attributing generic phases to the
links, this matrix must have the following structure:

$\tilde{\mathbf{H}}_{k}=\left(\begin{array}[]{cc}N&\sqrt{N}\\\
\sqrt{N}&k\end{array}\right)$ (22)

where we chose the second vector of the reduced basis to be the
$\underline{e}_{E}=\frac{1}{\sqrt{N}}(\underline{h}_{1}-N\underline{e}_{1})$,
where $\underline{h}_{1}$ is the first column of the full chiral Hamiltonian
we are considering (with diagonal elements fixed by the Laplacian) and the
number $k$ is the only parameter we may try to adjust by choosing a phases
configuration. For simplicity, suppose that the graph $\mathcal{G}^{\prime}$
is $m$-regular. Then clearly $|k|\leq 2m{\color[rgb]{1,0,0}+1}$, since the
matrix minor of the chiral Hamiltonian pertaining to $\mathcal{G}^{\prime}$
has all the diagonal elements equal to $m{\color[rgb]{1,0,0}+1}$ and exactly
$m$ nonzero off-diagonal entries in every row, each of which is a complex
phase. But by looking at the dynamics generated by the reduced Hamiltonian
(22) we get a returning probability of:

$p_{1\to 1}^{\mathbf{\tilde{H}}_{k}}(t)\ =\
1-\dfrac{2N}{(k-N)^{2}+4N}\left(1-\cos{\sqrt{(k-N)^{2}+4N}t}\right)$ (23)

which is sedentary unless $(k-N)\sim O(\sqrt{N})$. Therefore, on cones over
$m$-regular graphs whose degree does not grow with the number of vertices,
chiral quantum walks of the Laplacian type starting from the apex cannot be
swift. Despite its generality, this result relies on the assumption that the
dynamics reduces to a $2\times 2$ subspace, which would be needed to achieve
the exact swift evolution. In fact, a more general no-go theorem holds.

######  Theorem 6.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a cone over a subgraph
$\mathcal{G}^{\prime}$ of order $N$ (then $|\mathcal{V}|=N+1$) and denote by
$\underline{e}_{1}$ the characteristic vector of the apex of the cone,
labelled by $1$. Let $d^{>}$ be the largest degree for the vertices of
$\mathcal{G}^{\prime}$. Then, if $d^{>}\sim o(N)$ for large $N$, any chiral
quantum walk of the Laplacian type starting from $1$ is sedentary333In the
original definition by Godsil [37], sedentarity requires that the return
probability has the asymptotic form $1-\frac{k}{N}$ for constant $k$ and large
order $N$. Here we slightly relax this definition by allowing asymptotic
scaling of the form $1-\frac{k}{N^{\alpha}}$ for $\alpha>0$, such that it is
still true that the return probability is close to $1$ as $N\to\infty$. In
particular, Theorem 6 implies sedentarity with $\alpha=1/2$. ; more generally,
if $\tilde{\mathbf{L}}$ is a chiral Laplacian on $\mathcal{G}$:

$p^{\tilde{\mathbf{L}}}_{1\to 1}(t)\ \geq\ 1-\dfrac{\sqrt{N}}{N-2d^{>}}$ (24)

(assuming $2d^{>}<N$).

###### Proof.

We will prove this statement via energy conservation, i.e. imposing that the
expectation value of $\tilde{\mathbf{L}}$ be the same at the beginning and at
the end of the unitary evolution. Suppose that at a time $t$ the quantum walk
starting from $1$ has evolved into:

$\underline{e}(t)\ =\ e^{-it\tilde{\mathbf{L}}}\underline{e}_{1}\ =\
\alpha\underline{e}_{1}\ +\ \beta\underline{f}$ (25)

where $\underline{f}$ is a normalized vector with support on
$\mathcal{G}^{\prime}$ ($\underline{f}^{\dagger}\underline{f}=1$ and
$\underline{e}_{1}^{\dagger}\underline{f}=0$), with
$|\alpha|^{2}+|\beta|^{2}=1$. In the appendix, we prove that if
$\underline{f}$ is normalized and with support on $\mathcal{G}^{\prime}$
having maximum degree $d^{>}$, then:

$\underline{f}^{\dagger}\tilde{\mathbf{L}}\underline{f}\ \leq\ 2d^{>}$ (26)

Notice also that:

$\underline{e}^{\dagger}(t)\tilde{\mathbf{L}}\underline{e}(t)\ =\
\underline{e}^{\dagger}_{1}\tilde{\mathbf{L}}\underline{e}_{1}\ =\ N$

which can be combined with Eq.(25) to get:

$N=\underline{e}^{\dagger}(t)\tilde{\mathbf{L}}\underline{e}(t)\ \leq\
N|\alpha|^{2}\ +\ 2d^{>}|\beta|^{2}\ +\
\left(\alpha\beta^{*}\underline{f}^{\dagger}\tilde{\mathbf{L}}\underline{e}_{1}+\
h.c.\right)$

where $h.c.$ stands for the hermitian conjugate of the first term in
parenthesis and we invoked Eq.(26). Since
$\tilde{\mathbf{L}}\underline{e}_{1}$ projected onto $\mathcal{G}^{\prime}$ is
a complex vector with norm $\sqrt{N}$ and $\underline{f}$ is normalized and
has support on $\mathcal{G}^{\prime}$, Cauchy-Schwarz inequality in
$\mathds{C}^{N}$ implies:

$|\underline{f}^{\dagger}\tilde{\mathbf{L}}\underline{e}_{1}|\leq\sqrt{N}$

and consequently, using the fact that $|\alpha\beta^{*}+\alpha^{*}\beta|\leq
1$:

$|\alpha\beta^{*}\underline{f}^{\dagger}\tilde{\mathbf{L}}\underline{e}_{1}+\
h.c.|\leq\sqrt{N}$

In conclusion, we arrived at the following inequality:

$N\ \leq\ N|\alpha|^{2}\ +\ 2d^{>}|\beta|^{2}\ +\ \sqrt{N}$

which can be rearranged by using $|\alpha|^{2}+|\beta|^{2}=1$ into:

$N\ \leq\ (N-2d^{>})|\alpha|^{2}\ +\ 2d^{>}\ +\ \sqrt{N}$ (27)

If $2d^{>}<N$, then we get the following bound on $|\alpha|^{2}$:

$|\alpha|^{2}\ \geq\ 1-\dfrac{\sqrt{N}}{N-2d^{>}}$ (28)

∎

_Remark._ The fact that $\mathcal{G}$ is a cone is not strictly necessary for
the theorem above to hold. Indeed, it is sufficient that the starting vertex
has the largest degree ($N$) and that the degrees of all the other vertices
are $o(N)$. In this sense, this result indicates that the diagonal elements of
the chiral Laplacians strongly hinder the transport between vertices with
highly different degrees, and this issue cannot be overcome by leveraging on
chirality.

##  6 Conclusions

Previous results indicate that sedentarity, i.e. a return probability close to
$1$ at all times, seems a general property of continuous-time quantum walks
starting from a maximal degree vertex. This is a general statement when the
generator is the Laplacian, thanks to the universality of the corresponding
dynamics [38], while it is also true for CTQWs generated by the adjacency
matrix when the underlying graph is sufficiently connected. In this paper, we
have shown that the sedentarity of adjacency type CTQWs can be amended by
considering _chiral_ adjacency matrices as generators of the unitary
evolution. In particular, a configuration of phases on the edges of a graph
can be chosen such that the dynamics starting from the apex of a cone over
such a graph will leave the apex in the shortest time possible allowed by
unitary evolutions generated by generic Hamiltonians compatible with the graph
topology. We termed this construction _swift chiral quantum walks_ and the
question about its feasibility on generic graphs naturally lead to the
nontrivial problem of the existence of a swift phases configuration, which we
were able to settle for several families of graphs. By contrast, the
sedentarity of Laplacian quantum walks cannot always be resolved by adding
phases to the edges; we proved that whenever the initial vertex has a degree
which is considerably larger than the degrees of all other vertices in the
graph, _any_ chiral Laplacian will still generate a sedentary evolution. The
relevance of these results partly relies in their generality, since up to now
very little was known about tasks that can or cannot be achieved by
introducing chirality into CTQWs on general graphs. Moreover, Theorem 3
suggests that deep mathematical questions about graphs could arise from the
analytical study of the theory of chiral quantum walks, despite the modest
attention they elicited so far. Indeed, necessary and sufficient graph-
theoretical conditions for generic odd-degree regular graphs to admit a swift
phases configuration are still unknown, let alone for non-regular graphs.

##  Appendix A Proof of theorems on swift phases configurations

###  A.1 Proof of Theorem 2

###### Proof.

We will prove that one can associate phases of $i$ and $-i$ to all the
directed edges of $\mathcal{G}^{\prime}$ such that the sum of the outgoing
phases from any vertex is $0$. First notice that this is equivalent to
assigning arrows to the edges: each arrow indicates a phase of $i$ when the
edge is seen in the corresponding direction, and a factor of $-i$ for the
opposite direction. A solution to our problem then would be a configuration of
arrows on all edges such that each vertex has an equal number of outgoing and
incoming arrows. To achieve such a configuration, let us start from a vertex,
pick a random edge and assign an arrow on it directed towards the
corresponding neighbour. Repeat this operation again and again, possibly
landing more than once on the same vertex, but with the condition that an edge
which has already been assigned an arrow cannot be traversed again. This can
always be done, since each time we arrive at a vertex (except for the initial
one) the number of arrows already assigned to its edges will be odd (two
arrows for each time we visited that vertex before, and one additional arrow
for visiting it again at the present stage). Therefore, since its connectivity
is even by hypothesis, there will be another edge attached to the vertex
without an already assigned arrow. Since the graph is finite and this process
can continue each time we land on a vertex which is not the starting one,
sooner or later we are bound to reach the initial vertex. At that point, each
vertex will have an even number of assigned arrows attached to it, and half of
them will be outgoing and the other half will be incoming, since each time we
arrived at the vertex with an arrow and we left it with another one. Let us
now delete all the edges that have been labelled with an arrow: the remaining
graph will still satisfy the initial property that each vertex has an even
degree, since we removed an even number of edges from each vertex. Therefore,
we can start the process again on the remaining edges, until the whole graph
will be covered by arrows fulfilling our condition.
∎

Notice that a shorter proof can be given by relying on Euler’s theorem from
graph theory, stating that a connected graph has a closed Eulerian trail (a
closed path visiting each vertex exactly once) if and only if all its vertices
have even degree.

###  A.2 Proof of theorem 3

###### Proof.

To prove that the first and second condition are equivalent, consider a
$3$-regular graph with a perfect matching: the edges that are not involved in
the matching must form cycles, since each vertex will have exactly $2$ of such
edges attached to it. Moreover, these cycles must be vertex disjoint for the
same reason. On the other hand, if $\mathcal{G}$ can be covered with vertex
disjoint cycles, each vertex will have exactly one edge attached to it which
is not involved in the cycles, and the collection of these edges must form a
perfect matching.

We will thus prove the theorem by showing that the first condition is
necessary and the second is sufficient for the existence of a swift phases
configuration. First, suppose that $\mathcal{G}$ can be covered with vertex
disjoint cycles. For each cycle, we pick a random orientation and we attribute
a phase of $e^{\frac{2i\pi}{3}}$ to all of its edges in the chosen
orientation. We then assign a phase of $1$ to all the remaining edges, which
form a perfect matching, as we argued before. In this way, the three edges
attached to any given vertex will have phases of $1$, $e^{\frac{2i\pi}{3}}$
and $e^{-\frac{2i\pi}{3}}$, summing to $0$ as requested.

Now suppose instead that there exists a swift phases configuration on
$\mathcal{G}$ and, for convenience, assume that $\mathcal{G}$ is connected
(otherwise the reasoning would apply to each connected component). Pick a
random edge, which will have an assigned phase of $e^{i\phi}$ in a given
orientation, say from vertex $v_{1}$ to vertex $v_{2}$. Now notice that three
complex phases can sum to $0$ if and only if they form an equilateral triangle
in the complex plane; therefore the phases associated with the other two edges
attached to $v_{1}$ must be $e^{i\phi+\frac{2i\pi}{3}}$ and
$e^{i\phi-\frac{2i\pi}{3}}$. The same reasoning applies to all other edges,
therefore fixing a phase on a single edge restricts the possible choice of
phases on all the other edges to a finite set, which we can take to be
$\\{e^{i\phi},e^{i\phi+\frac{2i\pi}{3}},e^{i\phi-\frac{2i\pi}{3}}\\}$ for an
appropriately chosen orientation of each edge. At this point there are two
possibilities:

  * •

The set $\\{e^{i\phi},e^{i\phi+\frac{2i\pi}{3}},e^{i\phi-\frac{2i\pi}{3}}\\}$
is equal (as a set) to $\\{1,e^{\frac{2i\pi}{3}},e^{-\frac{2i\pi}{3}}\\}$ or
to $\\{-1,-e^{\frac{2i\pi}{3}},-e^{-\frac{2i\pi}{3}}\\}$

  * •

The set $\\{e^{i\phi},e^{i\phi+\frac{2i\pi}{3}},e^{i\phi-\frac{2i\pi}{3}}\\}$
and its complex conjugate
$\\{e^{-i\phi},e^{-i\phi+\frac{2i\pi}{3}},e^{-i\phi-\frac{2i\pi}{3}}\\}$ have
no number in common

In the first case, the edges with phase $1$ (or $-1$) must form a perfect
matching, since each vertex must have exactly one edge with such a phase
attached to it. In the second case, all the edges with a phase of $e^{i\phi}$
(in any one of the two orientations) still form a perfect matching: indeed,
each vertex will have exactly one edge with phase $e^{i\phi}$ or $e^{-i\phi}$
attached to it (and it cannot have both $e^{i\phi}$ and $e^{-i\phi}$). In
either case, we conclude that $\mathcal{G}$ must admit a perfect matching. ∎

###  A.3 Proof of Theorem 4

###### Proof.

An explicit construction when $\mathcal{G}^{\prime}$ is a complete graph was
implicitly provided in [36]. A complete bipartite graph $K_{N_{1},N_{2}}$ is a
graph with two sets of vertices $\mathcal{V}_{A}$ with cardinality $N_{1}$ and
$\mathcal{V}_{B}$ with cardinality $N_{2}$, such that no edge connects
vertices from the same set and every vertex in $\mathcal{V}_{A}$ is connected
with every vertex in $\mathcal{V}_{B}$. The adjacency matrix of such a graph
can be written in the following form:

$\mathbf{A}_{K_{N_{1},N_{2}}}=\left(\begin{array}[]{cc}\mathbf{0}_{N_{1}\times
N_{1}}&\mathbf{B}\\\ \mathbf{B}^{T}&\mathbf{0}_{N_{2}\times
N_{2}}\end{array}\right)$ (29)

where $\mathbf{B}$ is an $N_{1}\times N_{2}$ matrix filled with $1$s. A chiral
adjacency matrix fulfilling Eq.(10) can be constructed by replacing
$\mathbf{B}$ with a matrix of phases $\tilde{\mathbf{B}}$ with entries
$\tilde{\mathbf{B}}_{jk}=e^{i\frac{2\pi j}{N_{1}}}e^{i\frac{2\pi k}{N_{2}}}$,
since
$\sum_{j=1}^{N_{1}}\tilde{\mathbf{B}}_{jk}=\sum_{k=1}^{N_{2}}\tilde{\mathbf{B}}_{jk}=0$.
∎

##  Appendix B A result on the spectrum of chiral adjacency matrices

######  Theorem 7.

Let $\mathcal{G}$ be a graph and let $\tilde{\mathbf{A}}$ be a chiral
adjacency matrix on $\mathcal{G}$. Let $d^{>}$ be the largest degree among the
vertices of $\mathcal{G}$. Then if $\lambda_{A}$ is an eigenvalue of
$\tilde{\mathbf{A}}$:

$|\lambda_{A}|\leq d^{>}$ (30)

Analogously, if $\tilde{\mathbf{L}}$ is a chiral Laplacian on $\mathcal{G}$
and $\lambda_{L}$ is one of its eigenvalues:

$|\lambda_{L}|\leq 2d^{>}$ (31)

###### Proof.

Let $\underline{x}$ be an eigenvector of $\tilde{\mathbf{A}}$ with eigenvalue
$\lambda$ and let $|x_{j_{0}}{\color[rgb]{1,0,0}|}=\sup_{j}|x_{j}|$ be the
largest entry of $\underline{x}$ (in absolute value). Then:

$|\lambda||x_{j_{0}}|\ =\ |(\tilde{\mathbf{A}}\underline{x})_{j_{0}}|\ \leq\
\sum_{k}|\tilde{\mathbf{A}}_{j_{0}k}x_{k}|\ \leq\
|x_{j_{0}}|\sum_{k}|\tilde{\mathbf{A}}_{j_{0}k}|\ \leq\ |x_{j_{0}}|d^{>}$ (32)

from which the thesis follows444Notice that $|x_{j_{0}}|>0$ and it cannot
vanish since an eigenvector is never the null vector.. To derive the above
inequalities, we used the fact that the entries of $\tilde{\mathbf{A}}$ are
complex numbers of modulus $1$ and that the maximum number of nonzero entries
in each row is $d^{>}$, by definition. The same reasoning applied to a chiral
Laplacian gives the other bound, since $\sum_{k}|\tilde{\mathbf{L}}_{j_{0}k}|$
is upper bounded by $2d^{>}$, because of the diagonal contribution. ∎

######  Corollary 3.

If $\underline{f}$ is a normalized vector with support on $\mathcal{G}$, then
for any chiral adjacency matrix $\tilde{\mathbf{A}}$ and any chiral Laplacian
$\tilde{\mathbf{L}}$:

$|\underline{f}^{\dagger}\tilde{\mathbf{A}}\underline{f}|\ \leq\ d^{>}\ \ ,\ \
\ \ |\underline{f}^{\dagger}\tilde{\mathbf{L}}\underline{f}|\ \leq\ 2d^{>}$
(33)

## References

  * [1] Farhi E and Gutmann S 1998 Phys. Rev. A 58(2) 915–928 URL https://link.aps.org/doi/10.1103/PhysRevA.58.915
  * [2] Portugal R 2018 Quantum walks and search algorithms (AG: Springer Nature Switzerland)
  * [3] Venegas-Andraca S E 2012 Quant. Inf. Process. 11 1015–1106
  * [4] Kempe J 2003 Contemp. Phys. 44 307–327
  * [5] Ambainis A 2003 Int. J. Quantum Inf. 1 507–518
  * [6] Mülken O and Blumen A 2011 Phys. Rep. 502 37–87
  * [7] Childs A M, Farhi E and Gutmann S 2002 Quantum Information Processing 1 35–43 URL https://doi.org/10.1023/A:1019609420309
  * [8] Childs A M 2009 Phys. Rev. Lett. 102 180501
  * [9] Shenvi N, Kempe J and Whaley K B 2003 Phys. Rev. A 67 052307
  * [10] Childs A M and Goldstone J 2004 Physical Review A 70 022314
  * [11] Alvir R, Dever S, Lovitz B, Myer J, Tamon C, Xu Y and Zhan H 2016 J. Algebr. Comb. 43 801–826
  * [12] Christandl M, Datta N, Ekert A and Landahl A J 2004 Phys. Rev. Lett. 92 187902
  * [13] Kendon V M and Tamon C 2011 J. Comput. Theor. Nanos. 8 422–433
  * [14] Cameron S, Fehrenbach S, Granger L, Hennigh O, Shrestha S and Tamon C 2014 Linear Algebra and its Applications 455 115–142 ISSN 0024-3795 URL https://www.sciencedirect.com/science/article/pii/S0024379514002845
  * [15] Beggi A, Razzoli L, Bordone P and Paris M G A 2018 Physical Review A 97 013610
  * [16] Agliari E, Blumen A and Mülken O 2008 Journal of Physics A: Mathematical and Theoretical 41 445301
  * [17] Salimi S 2010 Quantum Information Processing 9 75–91
  * [18] Darázs Z, Anishchenko A, Kiss T, Blumen A and Mülken O 2014 Physical Review E 90 032113
  * [19] Li X, Chen H, Wu M, Ruan Y, Liu Z and Tan J 2020 Quantum Information Processing 19 1–13
  * [20] Rai A, Agarwal G S and Perk J H 2008 Physical Review A 78 042304
  * [21] Blumen A, Bierbaum V and Mülken O 2006 Physica A: Statistical Mechanics and its Applications 371 10–15
  * [22] Mülken O, Pernice V and Blumen A 2007 Physical Review E 76 051125
  * [23] Xu X P, Li W and Liu F 2008 Physical Review E 78 052103
  * [24] Yalouz S and Pouthier V 2018 Physical Review E 97 022304
  * [25] Mülken O, Blumen A, Amthor T, Giese C, Reetz-Lamour M and Weidemüller M 2007 Physical review letters 99 090601
  * [26] Agliari E, Muelken O and Blumen A 2010 International Journal of Bifurcation and Chaos 20 271–279
  * [27] Cavazzoni S, Razzoli L, Bordone P and Paris M G A 2022 arXiv.2205.09408
  * [28] Razzoli L, Paris M G A and Bordone P 2021 Entropy 23 URL https://www.mdpi.com/1099-4300/23/1/85
  * [29] Godsil C and Royle G F 2013 Algebraic graph theory 2001st ed Graduate Texts in Mathematics (New York, NY: Springer)
  * [30] Brouwer A E and Haemers W H 2011 Spectra of graphs 2012th ed Universitext (New York, NY: Springer)
  * [31] Wong T G, Tarrataca L and Nahimov N 2016 Quantum Information Processing 15 4029–4048
  * [32] Sakurai J J and Napolitano J 2011 Modern quantum mechanics 2nd ed (San Francisco, CA: Addison-Wesley)
  * [33] Zimborás Z, Faccin M, Kádá Z, Whitfield J D, Lanyon B P and Biamonte J 2013 Sci. Rep. 3 2361
  * [34] Lu D, Biamonte J D, Li J, Li H, Johnson T H, Bergholm V, Faccin M, Zimborás Z, Laflamme R, Baugh J and Lloyd S 2016 Phys. Rev. A 93(4) 042302 URL https://link.aps.org/doi/10.1103/PhysRevA.93.042302
  * [35] Frigerio M, Benedetti C, Olivares S and Paris M G A 2021 Phys. Rev. A 104(3) L030201 URL https://link.aps.org/doi/10.1103/PhysRevA.104.L030201
  * [36] Frigerio M, Benedetti C, Olivares S and Paris M G A 2022 Phys. Rev. A 105(3) 032425 URL https://link.aps.org/doi/10.1103/PhysRevA.105.032425
  * [37] Godsil C 2021 Linear Algebra and its Applications 614 356–375 ISSN 0024-3795 special Issue ILAS 2019 URL https://www.sciencedirect.com/science/article/pii/S0024379520304067
  * [38] Razzoli L, Bordone P and Paris M G A 2022 Journal of Physics A: Mathematical and Theoretical 55 265303 URL https://doi.org/10.1088/1751-8121/ac72d5
  * [39] Xu X P 2009 Journal of Physics A: Mathematical and Theoretical 42 115205 URL https://doi.org/10.1088/1751-8113/42/11/115205
  * [40] Novo L, Chakraborty S, Mohseni M, Neven H and Omar Y 2015 Sci. Rep. 5 13304
  * [41] Giovannetti V, Lloyd S and Maccone L 2003 The quantum speed limit Fluctuations and Noise in Photonics and Quantum Optics vol 5111 ed Abbott D, Shapiro J H and Yamamoto Y International Society for Optics and Photonics (SPIE) pp 1 – 6 URL https://doi.org/10.1117/12.507486
  * [42] Giovannetti V, Lloyd S and Maccone L 2003 Phys. Rev. A 67(5) 052109 URL https://link.aps.org/doi/10.1103/PhysRevA.67.052109
  * [43] Giovannetti V, Lloyd S and Maccone L 2004 Journal of Optics B: Quantum and Semiclassical Optics 6 S807–S810 URL https://doi.org/10.1088/1464-4266/6/8/028
  * [44] Deffner S and Campbell S 2017 Journal of Physics A: Mathematical and Theoretical 50 453001 URL https://doi.org/10.1088/1751-8121/aa86c6
  * [45] Turner J W and Biamonte J 2021 Journal of Physics A: Mathematical and Theoretical 54 235301 URL https://doi.org/10.1088/1751-8121/abf9d0


# On tameness of zonoids

Antonio Lerario  SISSA, Via Bonomea 265, 34136 Trieste, Italy
<EMAIL_ADDRESS>and  Leo Mathis  SISSA, Via Bonomea 265, 34136 Trieste, Italy
<EMAIL_ADDRESS>
###### Abstract.

We prove that in a tame family of convex bodies the set of zonoids is tame.
Here “tame” means “definable in the o-minimal structure generated by globally
subanalytic sets and the graph of the exponential function”.

##  1\. Introduction

A _zonoid_ in $\mathbb{R}^{n}$ is a convex body that can be approximated, in
the Hausdorff metric, by finite sums of line segments. Zonoids appear in
several different contexts of modern mathematics: functional analysis, measure
theory, stochastic geometry, geometric convexity, enumerative geometry [AL16,
Bol71, BLM89, BL18, GW92, GW93, LM20, NRZ08, Vit91, Wit73]. Despite the simple
definition, the problem of deciding whether a given convex body is a zonoid is
considerably hard, and it is referred to as the zonoid problem.

In $\mathbb{R}^{2}$ every centrally symmetric convex body is a zonoid, but for
$n\geq 3$ no simple geometric characterization exists for zonoids in
$\mathbb{R}^{n}$. For example, an interesting non-trivial characterization
says that a convex body is a zonoid if and only if its support function is
conditionally positive definite111A function $f:\mathbb{R}^{n}\to\mathbb{R}$
is said to be _conditionally positive definite_ , see [Sch14, Notes for
Section 3.5, pag. 204], if for all $k\in\mathbb{N}$ and for all
$x_{1},\ldots,x_{k}\in\mathbb{R}^{n}$ and
$\alpha_{1},\ldots,\alpha_{k}\in\mathbb{R}$ such that
$\alpha_{1}+\cdots+\alpha_{k}=0$ we have
$\sum_{i,j=1}^{k}\alpha_{i}\alpha_{j}f(x_{i}-x_{j})\geq 0.$ : this
characterization involves nice inequalities on the values of the support
function, but an _infinite_ number of them.

In this paper we show that, as soon as we restrict to a “tame” family of
convex bodies, the set of zonoids in this family can be described using only a
finite number of “tame” conditions.

Here _tame_ means _definable in the o-minimal structure
$\mathbb{R}_{\mathrm{an},\mathrm{exp}},$_ i.e. the o-minimal structure
generated by globally subanalytic sets and the graph of the exponential
function. With this notation, our main result is the following theorem.

######  Theorem 1.

In a tame family of convex bodies, the set of zonoids is tame.

######  Remark 2.

Our study was motivated by the following question, suggested by B. Sturmfels:
given a semialgebraic convex body, is there an algorithm to decide whether it
is a zonoid or not? For example, let $p\in\mathbb{R}[x_{1},\ldots,x_{n}]_{d}$
be a polynomial of degree $d$ in $n$ variables and let
$K_{p}:=\left\\{x\in\mathbb{R}^{n}\ |\ p(x)\geq 0\right\\}$. We define
$P:=\left\\{p\in\mathbb{R}[x_{0},\ldots,x_{n}]\ |\ \textrm{$K_{p}$ is a convex
body}\right\\}$. This defines a tame (semi-algebraic) family of convex bodies.
Is there an algorithm that, given the polynomial $p$, decides whether $K_{p}$
is a zonoid or not? Consider now the set:

(1.1) $\mathscr{Z}(P):=\left\\{p\in P\ |\ K_{p}\text{ is a zonoid}\right\\}.$

If $\mathscr{Z}(P)$ is semialgebraic, such an algorithm (in the sense of
[BPR06]) exists. In general, for $n\geq 3$, it is not known if
$\mathscr{Z}(P)$ is semi-algebraic. Our Theorem 1 above proves that it is at
least definable in the o-minimal structure $\mathbb{R}_{\mathrm{an,exp}}$, and
therefore it cannot be “wild” (in particular it shares with semialgebraic sets
many finiteness properties). Our proof of Theorem 1 is constructive but it is
not clear to us whether this can be called an algorithm.

######  Remark 3.

The main idea of the proof is to reduce the problem to the study of a “tame”
family of distributions on the unit interval. More precisely, our first step
consists in associating to our family of convex bodies a new tame family of
rotational invariant convex bodies. The support functions of these convex
bodies depend on one variable only and zonoids correspond to members of the
family such that an appropriate integral transform of their support function
is a non–negative measure. Using the language of distributions, we show that
the condition of being a non–negative measure can be expressed in a tame way
using a second primitive of the integral transform.

If we start with a semialgebraic family, both the process of moving to
rotational invariant bodies and of taking the second primitive take us out of
the semialgebraic world, but keeps us inside the tame one. (If in addition the
support function – and not just the body – is polynomial, then is is easy to
see that the condition of being a zonoid is semialgebraic in the coefficients
of the polynomial.)

###  1.1. Acknowledgements

The authors wish to thank B. Sturmfels for suggesting the question from which
this paper started, and S. Basu for many helpful comments.

##  2\. Preliminaries

###  2.1. Zonoids

Let us recall some definitions from convex geometry. For a more detailed
treatment we refer to [Sch14]. Our main object of study are _convex bodies_ ,
i.e. non-empty, compact and convex subsets of Euclidean space. Recall that the
_support function_ of a convex body $K\subset\mathbb{R}^{n+1}$ is the function
on $h_{K}:S^{n}\to\mathbb{R}$ given by:

(2.1) $h_{K}(u):=\sup\left\\{\langle u,x\rangle\ |\ x\in K\right\\}.$

A convex body $K$ is called a _zonoid_ if there exists an even, non–negative
measure $\mu$ on $S^{n}$ such that the support function of $K$ can be written
in the following form

(2.2) $h_{K}(u)=\frac{1}{2}\int_{S^{n}}|\langle u,x\rangle|\mathrm{d}\mu(x)$

We will use the following notion introduced by Lonke in [Lon].

######  Definition 4.

Let $f:S^{n}\to\mathbb{R}$ be a measurable function and $e\in S^{n}$. We
denote by

(2.3) $O(e):=\mathrm{Stab}_{O(n+1)}(e)\simeq O(n)\subset O(n+1)$

the stabilizer of $e$ in $O(n+1)$, endowed with the normalized Haar measure
$\mathrm{d}g$. We then define the measurable function
$S_{e}f:S^{n}\to\mathbb{R}$ by

(2.4) $S_{e}f(u):=\int_{O(e)}f\left(g(u)\right)\mathrm{d}g.$

If $K\subset\mathbb{R}^{n+1}$ is a centrally symmetric convex body whose
support function is $h_{K}$ we define $S_{e}K$ to be the convex body whose
support function is given by:

(2.5) $h_{S_{e}K}:=S_{e}h_{K}.$

The fact that $S_{e}h_{K}$ is the support function of a convex body follows
from the characterization of support functions as positively homogeneous
sublinear functions [Sch14, Section 1.7].

Using Definition 4 one can give the following alternative characterization of
zonoids, see [Lon, Theorem 1.1].

######  Lemma 5.

A convex body $K\subset\mathbb{R}^{n+1}$ is a zonoid if and only if for all
$e\in S^{n}$, $S_{e}K$ is a zonoid.

###  2.2. O-minimal structures and tameness

We denote by $\mathbb{R}_{\mathrm{an},\mathrm{exp}}$ the o-minimal structure
generated by the globally subanalytic sets together with the graph of the
exponential function, see [vdD99]. We say that a set or a function is _tame_
if it is definable in $\mathbb{R}_{\mathrm{an},\mathrm{exp}}$.

We will use the following crucial result [CM11, Theorem 1.3].

######  Theorem 6.

Let $F:P\times\mathbb{R}^{m}\to\mathbb{R}$ be a tame function, with $P$
subanalytic. Suppose that for all $p\in P$ the function
$F(p,\cdot):\mathbb{R}^{m}\to\mathbb{R}$ is integrable. Then the the function
$I(F):P\to\mathbb{R}$ defined by
$I(F)(p):=\int_{\mathbb{R}^{m}}F(p,x)\mathrm{d}x$ is tame.

######  Remark 7.

In the case $F:P\times\mathbb{R}^{m}\to\mathbb{R}^{m}$ is semialgebraic, then
the parametrized integral function $I(F)$ is definable in a structure strictly
smaller than $\mathbb{R}_{\mathrm{an},\mathrm{exp}}$, see [Kai13].

######  Corollary 8.

If $h:S^{n}\to\mathbb{R}$ is tame, the function $(e,u)\mapsto S_{e}h(u)$ is
also tame.

###### Proof.

Consider a tame function $F:S^{n}\times O(n)\to O(n+1)$ such that for almost
all $e\in S^{n}$ the function $F(e,\cdot)$ is a tame isomorphism between
$O(n)$ and $O(e)$. (Since we are only requiring that $F$ is tame, such
function can also be defined piecewise.) Then we can write:

(2.6) $S_{e}h_{p}(u)=\int_{O(n)}h_{p}\left(F(e,\tilde{g})(u)\right)|\det
JF(e,\cdot)|d\tilde{g},$

where $d\tilde{g}$ is the normalized Haar measure on $O(n)$. Since the
integrand is tame, the result follows by applying Theorem 6 after noticing
that there is a tame diffeomorphism between an open dense of subset of $O(n)$
and $\mathbb{R}^{m}$, $m=n(n-1)/2$ (for instance one can take the restriction
of the Riemannian exponential map at the identity on an appropriate tame
domain). ∎

######  Definition 9.

Let $P$ be a tame set. A _tame family_ of convex bodies in $\mathbb{R}^{n+1}$
is a tame set $T\subset P\times\mathbb{R}^{n+1}$ such that for every $p\in P$
the set

(2.7) $K_{p}:=\left\\{x\in\mathbb{R}^{n+1}\ |\ (p,x)\in T\right\\}$

is a convex body. For $p\in P$, we will denote by $h_{p}$ the support function
of $K_{p}$ (instead of $h_{K_{p}}$).

Notice that if $T\subset P\times\mathbb{R}^{n+1}$ is a tame family of convex
bodies, the function $H:P\times S^{n}\to\mathbb{R}$, given by
$H(p,u)=h_{K_{p}}(u)$, is tame. Moreover, if $P$ is a tame set and $T\subseteq
P\times\mathbb{R}^{n+1}$ is tame, denoting by
$T_{p}:=\left\\{x\in\mathbb{R}^{n+1}\ |\ (p,x)\in T\right\\},$ it is immediate
to see that the following sets are tame:

  1. (i)

$\mathscr{K}(P):=\left\\{p\in P\ |\ T_{p}\text{ is a convex body}\right\\};$

  2. (ii)

$\mathscr{K}_{0}(P):=\left\\{p\in P\ |\ T_{p}\text{ is a centrally symmetric
convex body, centered at the origin}\right\\}.$

The following lemma will also be useful for us.

######  Lemma 10.

Let $F:P\times[-1,1]\to\mathbb{R}$ be a tame function. For every $p\in P$ and
for $k\in\mathbb{N}$ consider the set $\Sigma_{k}(p)\subset[-1,1]$ defined by
$\Sigma_{k}(p):=\left\\{z\in[-1,1]\ |\ F(p,\cdot)\text{ is not $C^{k}$ at
$z$}\right\\}$. Then the set $\Sigma_{k}:=\left\\{(p,z)\in P\times[-1,1]\ |\
z\in\Sigma_{k}(p)\right\\}$ is tame.

###### Proof.

Consider the case $k=1$. The function $F(p,\cdot)$ is $C^{1}$ at $z$ if and
only if the limit $\lim_{h\to 0}\frac{F(p,z+h)-F(p,z)}{h}$ exists and is
finite. This is a first order formula involving only tame objects. This proves
that the complement of $\Sigma_{1}$ is tame and thus $\Sigma_{1}$ itself is
tame. The general case is proved similarly. ∎

###  2.3. Distributions

Let $X$ be a smooth manifold. We denote by $C^{\infty}_{c}(X)$ the space of
compactly supported, smooth functions on $X$, endowed with the $C^{\infty}$
topology (see [Hir94]). The space of _distributions_ on $X$ is denoted by
$\mathcal{D}^{\prime}(X)$: it is the dual of $C^{\infty}_{c}(X)$, endowed with
the weak–$*$ topology.

######  Remark 11.

If $X$ is compact $C^{\infty}_{c}(X)=C^{\infty}(X)$.

######  Remark 12.

Let $G$ be a group. Any group action $G\curvearrowright X$ gives rise to a
group action on $C^{\infty}_{c}(X)$ by
$g\cdot\varphi(x):=\varphi\left(g^{-1}\cdot x\right)$ for all $g\in G$,
$\varphi\in C^{\infty}_{c}(X)$ and $x\in X$. This induces a group action on
$\mathcal{D}^{\prime}(X)$ defined by $\langle
g\cdot\rho,\varphi\rangle:=\langle\rho,g^{-1}\cdot\varphi\rangle$ for all
$g\in G$, $\varphi\in C^{\infty}_{c}(X)$ and $\rho\in\mathcal{D}^{\prime}(X)$.
We denote by $C^{\infty}_{c}(X)^{G}$ (respectively
$\mathcal{D}^{\prime}(X)^{G}$) the functions (respectively distributions)
which are invariant under these actions. Note that
$\left(C^{\infty}_{c}(X)^{G}\right)^{*}=\mathcal{D}^{\prime}(X)^{G}$.

In our case $X$ will be $S^{n}$, $[-1,1]$ or $(-1,1)$ an $G$ will be $O(e)$
for some $e\in S^{n}$.

######  Definition 13.

We denote by $C^{\infty}_{even}(S^{n})^{O(e)}$ (respectively
$\mathcal{D}^{\prime}_{even}(S^{n})^{O(e)}$) the functions (respectively
distributions) on $S^{n}$ invariant by the group generated by $O(e)$ and the
antipodal map $u\mapsto-u$. Similarly we denote by $C^{\infty}_{even}([-1,1])$
(respectively $\mathcal{D}^{\prime}_{even}([-1,1])$) the even functions
(respectively distributions) on $[-1,1]$.

######  Remark 14.

Recall that there is a dense embedding
$C^{\infty}_{even}(S^{n})\hookrightarrow\mathcal{D}^{\prime}_{even}(S^{n})$,
$f\mapsto\rho_{f}$ given, for all $g\in C^{\infty}_{even}(S^{n})$, by:

(2.8) $\langle\rho_{f},g\rangle:=\int_{S^{n}}f(x)g(x)\mathrm{d}x,$

where $\mathrm{d}x$ denotes the integration with respect to the standard
volume form on $S^{n}$. There is a similar dense embedding for $[-1,1]$.

######  Lemma 15.

Consider the map $\sigma:[-1,1]\to[0,1]$ given by $\sigma(z):=\sqrt{1-z^{2}}$.
Then the operator $\mathcal{P}$ defined for all $\varphi\in
C^{\infty}_{even}([-1,1])$ by $\mathcal{P}\varphi:=\varphi\circ\sigma$ is a
continuous automorphism of $C^{\infty}_{even}([-1,1])$.

###### Proof.

It is enough to know that for every $\varphi\in C^{\infty}_{even}([-1,1])$
there exists $\psi\in C^{\infty}([0,1])$ such that $\varphi(z)=\psi(z^{2})$
and that the map $\varphi\mapsto\psi$ is continuous in the $C^{\infty}$
topology. This is done in [Whi43]. ∎

######  Proposition 16.

For every $e\in S^{n}$ there is a linear homeomorphism

(2.9) $\zeta_{n}:C^{\infty}_{even}(S^{n})^{O(e)}\to
C^{\infty}_{even}([-1,1]).$

Its inverse is given by $(\zeta_{n}^{-1}\varphi)(u):=\varphi\left(\langle
u,e\rangle\right)$. By density this gives a linear homeomorphism
$\zeta_{n}:\mathcal{D}^{\prime}_{even}(S^{n})^{O(e)}\to\mathcal{D}^{\prime}_{even}([-1,1]).$

###### Proof.

Let $f\in C^{\infty}_{even}(S^{n})^{O(e)}$ and let us consider an orthonormal
basis $v_{1},\ldots,v_{n},e$. In this basis

(2.10) $(\zeta_{n}f)(z)=f(0,\ldots,0,\sqrt{1-z^{2}},z).$

Denoting by $\gamma:[-1,1]\to S^{n}$ the curve
$\gamma(z):=(0,\ldots,0,\sqrt{1-z^{2}},z)$, we see that
$(\zeta_{n}f)=f\circ\gamma$.

This function is cleary even and $C^{\infty}$ away from $z=\pm 1$. We show now
that it is also smooth near these points. Consider the local coordinate chart
$\pi$ around the north pole $(0,\ldots,0,1)$ that is the projection on the
first $n$ coordinates. Then near the north pole,
$\zeta_{n}f=\tilde{f}\circ\pi\circ\gamma$ where $\tilde{f}:=f\circ\pi^{-1}$.
The function $\tilde{f}$ is smooth because it is a composition of smooth
functions. Consider now first the case $n=1$, for which we have

(2.11) $(\zeta_{1}f)(z)=\tilde{f}(\sqrt{1-z^{2}})=(\mathcal{P}\tilde{f})(z).$

In this case it is enough to apply the previous lemma. For the general case we
note that $\zeta_{n}$ is the composition of $\zeta_{1}$ with the restriction
to any $2$-plane containing $e$. This proves that $\zeta_{n}f\in
C^{\infty}_{even}([-1,1]).$

The map $\zeta_{n}$ is linear and, by (2.11) and Lemma 15, it is also
continuous. Its inverse, given by
$(\zeta_{n}^{-1}\varphi)(u):=\varphi\left(\langle u,e\rangle\right)$, is also
clearly continuous in the $C^{\infty}$ topology. ∎

The isomorphism $\zeta_{n}=\zeta_{n,e}$ defined above depends on $e\in S^{n}$.
However this dependence is _tame_ in the following sense.

######  Proposition 17.

Let $F:S^{n}\times S^{n}\to\mathbb{R}$ be a tame function such that for all
$e\in S^{n}$ the function $f_{e}:=F(e,\cdot)$ is $O(e)$-invariant. Then the
function $(e,z)\mapsto(\zeta_{n,e}f_{e})(z)$ is a tame function on
$S^{n}\times[-1,1]$.

###### Proof.

Take a tame function $v_{0}:S^{n}\to S^{n}$ such that for all $e\in S^{n}$,
$\langle e,v_{0}(e)\rangle=0$. Then we can write
$(\zeta_{n,e}f_{e})(z)=F(e,ze+\sqrt{1-z^{2}}\ v_{0}(e))$, and this is tame
because it is a composition of tame functions. ∎

######  Definition 18.

Let $\varphi$ be a function on $[-1,1]$ or $(-1,1)$. Suppose $\varphi$ is
locally integrable and thus defines a distribution. We will denote by
$D^{k}\varphi$ its $k$-th distributional derivative and by $\varphi^{(k)}$ the
classical derivative whenever this is defined and locally integrable (we will
also use $\frac{\mathrm{d}^{k}\varphi}{\mathrm{d}z^{k}}$ when we need to
specify the variable of differentiation), i.e.:

(2.12) $\langle
D^{k}\varphi,\psi\rangle=(-1)^{k}\int_{I}\varphi\,\psi^{(k)}\quad\mathrm{and}\quad\langle\varphi^{(k)},\psi\rangle=\int_{I}\varphi^{(k)}\,\psi.$

Let $\rho\in\mathcal{D}^{\prime}(X)$. We say that $\rho$ is _non negative_ and
write $\rho\geq 0$ if for all $\varphi\in C^{\infty}_{c}(X)$ such that
$\varphi\geq 0$ we have $\langle\rho,\varphi\rangle\geq 0$.

Let us recall some properties of distributions. For proof and details, see
[Sch66]. For $x\in X$ we denote by $\delta_{x}$ the Dirac delta measure at
$x$.

######  Proposition 19.

Distributions satisfy the following properties:

  * (i)

let $\rho\in\mathcal{D}^{\prime}(X)$. Then $\rho\geq 0$ if and only if $\rho$
is a positive (finite) Borel measure on $X$;

  * (ii)

let $x\in[-1,1]$ and let $\rho\in\mathcal{D}^{\prime}\left([-1,1]\right)$ such
that $\operatorname{supp}(\rho)=\\{x\\}$. Then there exist $N\in\mathbb{N}$
and $r_{0},\ldots,r_{N}$ such that $\rho=\sum_{i=0}^{N}r_{i}D^{i}\delta_{x}$;
if moreover $\rho\geq 0$, then $r_{0}\geq 0$ and $r_{i}=0$ for all $i>0;$

  * (iii)

let $\rho\in\mathcal{D}^{\prime}\left((-1,1)\right).$ Then $\rho\geq 0$ iff
there is a convex function $\gamma:(-1,1)\to\mathbb{R}$ such that
$D^{2}\gamma=\rho$.

######  Remark 20.

Let $\rho\in\mathcal{D}^{\prime}(S^{n})^{O(e)}$. Then $\rho\geq 0$ in
$\mathcal{D}^{\prime}(S^{n})^{O(e)}$ if and only if $\zeta_{n}\rho\geq 0$ in
$\mathcal{D}^{\prime}_{even}([-1,1])$. This is because $f\geq 0$ iff
$\zeta_{n}f\geq 0$.

A straightforward computation gives also the following lemma.

######  Lemma 21.

Let $\psi$ be $k$ times differentiable on $[a,b]$ with $-1\leq a<b\leq 1$.
Then the following properties are true:

  * (i)

If $\psi^{(k)}\in L^{1}([a,b])$, then

(2.13)
$D^{k}\psi=\psi^{(k)}+\sum_{i=0}^{k-1}\psi^{(i)}(a)D^{k-1-i}\delta_{a}-\psi^{(i)}(b)D^{k-1-i}\delta_{b};$

  * (ii)

for every $x\in[a,b]$ we have

(2.14) $\psi\cdot
D^{k}\delta_{x}=(-1)^{k}\sum_{i=0}^{k}(-1)^{i}\binom{k}{i}\psi^{(k-i)}(x)D^{i}\delta_{x}.$

Next lemma characterizes non–negative measures on $[-1,1]$.

######  Lemma 22.

Let $\Lambda\in\mathcal{D}^{\prime}([-1,1])$ and let
$W^{2,1}\left([-1,1]\right)$ be the Sobolev space of (equivalence classes of)
functions on $[-1,1]$ with integrable second derivative. Then $\Lambda\geq 0$
if and only if the following two conditions are both satisfied:

  * (i)

There is $\gamma:[-1,1]\to\mathbb{R}$ in $W^{2,1}([-1,1])$ convex such that
$D^{2}\gamma|_{(-1,1)}=\Lambda|_{(-1,1)};$

  * (ii)

There exist $\lambda_{-1},\lambda_{1}\geq 0$ such that:

(2.15) $\Lambda-\gamma^{(2)}=\lambda_{-1}\delta_{-1}+\lambda_{1}\delta_{1}.$

###### Proof.

Assume that (i) and (ii) are satisfied. Then $\gamma^{(2)}\geq 0$ and
therefore (2.15) defines a positive measure.

Now suppose $\Lambda\geq 0$. Then $\Lambda|_{(-1,1)}\geq 0$ and by point (iii)
of Proposition 19 there is $\gamma:(-1,1)\to\mathbb{R}$ convex such that
$D^{2}\gamma|_{(-1,1)}=\Lambda|_{(-1,1)}$. Since $\Lambda$ is finite on the
closed interval $[-1,1]$, then $\gamma^{(2)}$ is integrable near $\\{\pm
1\\}$, i.e. $\gamma$ is in $W^{2,1}\left([-1,1]\right)$ (in particular
$\gamma$ is also defined in $\\{\pm 1\\}$). This shows that (i) is satisfied.

Now since $\gamma^{(2)}=D^{2}\gamma|_{(-1,1)}=\Lambda|_{(-1,1)}$, then
$\Lambda-\gamma^{(2)}$ has support on $\\{\pm 1\\}$ and by point (ii) of
Proposition 19 it is a sum of deltas and its derivatives. Since both $\Lambda$
and $\gamma^{(2)}$ are measures, then $\Lambda-\gamma^{(2)}$ has no
derivatives of deltas. Thus there exist
$\lambda_{1},\lambda_{-1}\in\mathbb{R}$ such that
$\Lambda=\gamma^{(2)}+\lambda_{-1}\delta_{-1}+\lambda_{1}\delta_{1}$. Since
$\Lambda\geq 0$ point (ii) follows. ∎

###  2.4. Integral Transforms

We recall now some classical construction of integral transforms. We refer the
reader to [GW92] for more details.

The _Cosine Transform_ $T_{n}$ and the _Radon Transform_ $R_{n}$ are the
endomorphisms of $C^{\infty}_{even}(S^{n})$ given for all $f\in
C^{\infty}_{even}(S^{n})$ by

(2.16) $T_{n}f(u):=\frac{1}{2}\int_{S^{n}}|\langle
u,x\rangle|f(x)\mathrm{d}x\quad\textrm{and}\quad
R_{n}f(u):=\int_{S\left(u^{\perp}\right)}f(x)\mathrm{d}x,$

where $S\left(u^{\perp}\right)=S^{n}\cap u^{\perp}$ is the unit sphere on
$u^{\perp}$ and $\mathrm{d}x$ denotes the integration with respect to the
standard volume forms of the corresponding spheres.

######  Remark 23.

The two operators $T_{n}$ and $R_{n}$ are linear continuous bijections from
the space $C^{\infty}_{even}(S^{n})$ to itself. One can define the transpose
of these operators on the dual space $\mathcal{D}^{\prime}_{even}(S^{n})$ in
the usual way. More precisely, for every
$\rho\in\mathcal{D}^{\prime}_{even}(S^{n})$ and for every $f\in
C^{\infty}_{even}(S^{n})$, we set:

(2.17) $\langle(T_{n})^{t}\rho,f\rangle:=\langle\rho,T_{n}f\rangle,$

and similarly we do for $(R_{n})^{t}$.

With this definition it turns out that

(2.18) $(T_{n})^{t}|_{C^{\infty}_{even}(S^{n})}=T_{n}\ \text{and
}(R_{n})^{t}|_{C^{\infty}_{even}(S^{n})}=R_{n},$

when the space of smooth functions is embedded into the space of distribution
in the usual way (see Remark 14). Thus $(T_{n})^{t}$ and $(R_{n})^{t}$ can be
seen as extensions of the original operators to the space of distributions,
and we will still denote these extension by $T_{n}$ and $R_{n}$, see [GW92].

Observe that a convex body $K$ in $\mathbb{R}^{n+1}$ is a zonoid if and only
if there is a non negative measure $\mu$ on $S^{n}$ such that:

(2.19) $h_{K}=T_{n}\mu.$

Following [GW92], we define the following differential operator on
$C^{\infty}_{even}(S^{n})$:

(2.20) $\square:=\Delta_{S^{n}}+n,$

where $\Delta_{S^{n}}$ is the Spherical Laplacian on $S^{n}$. The various
operators defined so far satisfy the following intertwining properties [GW92,
Proposition 2.1]:

(2.21) $\square T_{n}=R_{n}\quad\textrm{and}\quad T_{n}^{-1}=\square
R_{n}^{-1}.$

We use now Proposition 16 to turn these operators into operators on the space
of distributions on the interval, as follows.

######  Definition 24.

We define the operators $r_{n},t_{n}$ on $\mathcal{D}^{\prime}([-1,1])$ by:

(2.22) $r_{n}:=\zeta_{n}R_{n}\zeta_{n}^{-1}\quad\textrm{and}\quad
t_{n}:=\zeta_{n}T_{n}\zeta_{n}^{-1}.$

######  Remark 25.

Since $\square$ commutes with the action of $O(n+1)$, it preserves the space
$C^{\infty}_{even}(S^{n})^{O(e)}$. Using the isomorphism $\zeta_{n}$ we
consider the operator $\zeta_{n}\square\zeta_{n}^{-1}$ that we still denote by
$\square$. This is a differential operator on
$C^{\infty}_{even}\left([-1,1]\right)$. For any $\varphi\in
C^{\infty}_{even}([-1,1])$, it is given by

(2.23) $\square\varphi(z)=(1-z^{2})\
\varphi^{(2)}(z)-nz\varphi^{(1)}(z)+n\varphi(z)$

In fact, let $\theta=\theta(u)$ be the angle between $e$ and $u$. By
Proposition 16, $f:=\zeta_{n}^{-1}\varphi$ as a function of $\theta$ is given
by $f(\theta)=\varphi(\cos(\theta))$. Equivalently
$\varphi(z)=f\left(\arccos(z)\right)$. It is then enough to consider the
spherical Laplacian of a function that depends only on $\theta$, which is
given by
$\Delta_{S^{n}}f(\theta)=(\sin\theta)^{1-n}\frac{\partial}{\partial\theta}\left((\sin\theta)^{n-1}\frac{\partial
f}{\partial\theta}\right),$ and apply the change of variables $z=\cos(\theta)$
to obtain (2.23).

The following proposition gives an integral expression for $r_{n}$.

######  Proposition 26.

Let $\varphi\in C^{\infty}_{even}([-1,1])$ and let
$z^{\prime}:=\sqrt{1-z^{2}}$. We have:

(2.24)
$(r_{n}\varphi)(z)=c_{n}\frac{1}{(z^{\prime})^{n-2}}\int_{0}^{z^{\prime}}\varphi(w)\left((z^{\prime})^{2}-w^{2}\right)^{\frac{n-3}{2}}\mathrm{d}w$

where $c_{n}=2\operatorname{vol}_{n-2}(S^{n-2})$.

###### Proof.

Let $f:=\zeta_{n}^{-1}\varphi$ in such a way that
$r_{n}\varphi=\zeta_{n}R_{n}f$. Consider an orthonormal basis
$v_{1},\ldots,v_{n},e$ and let $u(z):=z\ e+z^{\prime}\ v_{n}$. The unit sphere
in the space $u(z)^{\perp}$ can be parametrized by $z^{\prime}\cos\phi\
e+z\cos\phi\ v_{n}+\sin\phi\ v$ where $\phi\in[0,\pi]$ and $v$ belongs to the
unit sphere of $\operatorname{Span}\left\\{v_{1},\ldots,v_{n-1}\right\\}$.
Then, using the $O(e)$ invariance and the fact that $f$ is even, we get

(2.25)
$\zeta_{n}R_{n}f(z)=R_{n}f(u(z))=2\int_{0}^{\frac{\pi}{2}}f\left(z^{\prime}\cos\phi\
e+z\cos\phi\
v_{n}\right)(\sin\phi)^{n-2}\operatorname{vol}_{n-2}\left(S^{n-2}\right)\mathrm{d}\phi.$

We then note that $f\left(z^{\prime}\cos\phi\ e+z\cos\phi\
v_{n}\right)=\varphi(z^{\prime}\cos\phi)$ and apply the change of variable
$w=z^{\prime}\cos\phi$ to get (2.24). ∎

We notice the particular cases:

(2.26)
$r_{2}\varphi(z)=c_{2}\int_{0}^{z^{\prime}}\frac{\varphi(w)}{\sqrt{(z^{\prime})^{2}-w^{2}}}\mathrm{d}w\quad\textrm{and}\quad
r_{3}\varphi(z)=\frac{c_{3}}{z^{\prime}}\int_{0}^{z^{\prime}}\varphi(w)\mathrm{d}w.$

The equation on the left in (2.26) is known as Abel Equation and the second
one can be inverted as follows. Recall that the operator $\mathcal{P}$ from
Lemma 15 is defined by $\mathcal{P}\varphi(z)=\varphi(z^{\prime})$, with
$z^{\prime}=\sqrt{1-z^{2}}$.

######  Corollary 27.

The inverse of $r_{3}$ is given by
$r_{3}^{-1}=\frac{1}{c_{3}}\left(1+z\frac{\mathrm{d}}{\mathrm{d}z}\right)\circ\mathcal{P}$.

###### Proof.

We differentiate equation (2.26) to obtain
$\frac{\mathrm{d}}{\mathrm{d}z^{\prime}}r_{3}\varphi(z)=-\frac{1}{z^{\prime}}r_{3}\varphi(z)+\frac{c_{3}}{z^{\prime}}\varphi(z^{\prime})$.
Then write $\varphi=r_{3}^{-1}\psi$ and change $z^{\prime}$ for $z$. ∎

The following can be deduced from (2.24) with a straightforward computation.

######  Proposition 28.

Let $\varphi\in C^{\infty}_{even}([-1,1])$. For any positive integer $k\leq
n/2-1$

(2.27)
$\left(\frac{1}{z^{\prime}}\frac{d}{dz^{\prime}}\right)^{k}\left((z^{\prime})^{n-2}r_{n}\varphi(z)\right)=c_{n,k}\
(z^{\prime})^{n-2-2k}r_{n-2k}\varphi(z),$

where $c_{n,k}=\frac{(n-3)!!}{(n-3-2k)!!}\frac{c_{n-2k}}{c_{n}}$.

Together with Corollary 27 this implies the following.

######  Corollary 29.

For odd $n:=2m+1$, $m\geq 1$ and for $\psi\in C^{\infty}_{even}([-1,1])$ the
inverse of $r_{n}$ is given by

(2.28) $\left(r_{2m+1}\right)^{-1}\psi(z)=\frac{1}{c_{2m+1,m-1}c_{3}}\ z\
\left(\frac{1}{z}\frac{d}{dz}\right)^{m}\left(z^{2m-1}\mathcal{P}\psi(z)\right)$

###### Proof.

Apply Proposition 28 with $k=m-1$ to obtain

(2.29)
$\varphi(z)=\frac{1}{c_{2m+1,m-1}}r_{3}^{-1}\left(\frac{1}{z^{\prime}}\left(\frac{1}{z^{\prime}}\frac{\mathrm{d}}{\mathrm{d}z^{\prime}}\right)^{m-1}(z^{\prime})^{2m-1}r_{2m+1}\varphi(z)\right).$

Then write $\psi:=r_{2m+1}\varphi$ and apply Corollary 27. It is then enough
to note that, as operators,
$\left(z\frac{\mathrm{d}}{\mathrm{d}z}+1\right)\frac{1}{z}=\frac{\mathrm{d}}{\mathrm{d}z}$.
∎

######  Remark 30.

Note that in (2.28) the coefficients of the differential operator on the right
hand side are _polynomial_ functions of $z$. Indeed the term of lowest degree
is $z\left(\frac{1}{z}\frac{d}{dz}\right)^{m}\left(z^{2m-1}\right)$ which is
of degree zero. In other words, there exist polynomials $Q_{k,m}$ such that

(2.30)
$\left(r_{2m+1}\right)^{-1}\psi(z)=\sum_{k=0}^{m}Q_{k,m}(z)\left(\frac{\mathrm{d}}{\mathrm{d}z}\right)^{k}\mathcal{P}\psi(z).$

Thus we can still define the operator
$\sum_{k=0}^{m}Q_{k,m}(z)D^{k}\mathcal{P}$ on distributions. By density this
is also equal to the inverse of $r_{2m+1}$.

Remark 30 together with (2.21) and Remark 25 proves the following.

######  Lemma 31.

Let $f\in C^{\infty}\left([-1,1]\right)$. There are polynomials $P_{k,m}$ such
that

(2.31)
$\left(t_{2m+1}\right)^{-1}\psi=\sum_{k=0}^{m+2}P_{k,m}(z)\left(\frac{\mathrm{d}}{\mathrm{d}z}\right)^{k}\mathcal{P}\psi(z).$

This allows us to define the operator
$\left(t_{2m+1}\right)^{-1}:=\sum_{k=0}^{m+2}P_{k,m}D^{k}\mathcal{P}$ on
$\mathcal{D}^{\prime}\left([-1,1]\right)$.

##  3\. Proof of Theorem 1.

In this section we prove Theorem 1, which states that in a tame family of
convex bodies the set of zonoids is tame. We reformulate this as follows.

######  Theorem 32.

Let $P$ be a tame set and let $\left\\{K_{p}\ |\ p\in P\right\\}$ be a tame
family of convex bodies in $\mathbb{R}^{n+1}$. Then the set
$\mathscr{Z}(P):=\left\\{p\in P\ |\ K_{p}\text{ is a zonoid}\right\\}$ is
tame.

###### Proof.

Let us consider $n=2m+1$ with $m\geq 1$. We will prove that the set

(3.1) $S\mathscr{Z}:=\left\\{(p,e)\in P\times S^{n}\ |\ S_{e}K_{p}\text{ is a
zonoid}\right\\}$

is tame. By Lemma 5 we have that $\mathscr{Z}(P)=\left\\{p\in P\ |\ \forall
e\in S^{n},\ (p,e)\in S\mathscr{Z}\right\\}$. Thus if $S\mathscr{Z}$ is tame
then $\mathscr{Z}(P)$ is also tame.

For $p\in P$ let $h_{p}$ be the support function of $K_{p}$ and let $e\in
S^{n}$. Then by (2.19) $S_{e}K_{p}$ is a zonoid if and only if
$\left(T_{2m+1}\right)^{-1}S_{e}h_{p}\geq 0$.

Let
$\eta=\eta_{p,e}:=\zeta_{n}S_{e}h_{p}\in\mathcal{D}^{\prime}_{even}([-1,1])$
and let
$\Lambda=\Lambda_{p,e}:=t_{2m+1}^{-1}\eta\in\mathcal{D}^{\prime}_{even}([-1,1])$.
Then, by Remark 20, $S_{e}K_{p}$ is a zonoid if and only if $\Lambda\geq 0$.
By Lemma 22 this is equivalent to have the following two conditions satisfied:

  * (i)

there is $\gamma:[-1,1]\to\mathbb{R}$ in $W^{2,1}([-1,1])$ convex such that
$D^{2}\gamma|_{(-1,1)}=\Lambda|_{(-1,1)}$;

  * (ii)

there exist $\lambda_{-1},\lambda_{1}\geq 0$ such that
$\Lambda-\gamma^{(2)}=\lambda_{-1}\delta_{-1}+\lambda_{1}\delta_{1}$.

The function $S_{e}h_{p}$ is tame (Corollary 8) thus, by Proposition 17,
$\eta$ is tame (as a function of $e$, $p$ and $z$) and thus piecewise
$C^{m+2}$ as a function of $z$. Let $-1=a_{1}<a_{2}<\cdots<a_{\nu}=1$ be the
points of $[-1,1]$ where $\eta$ _is not_ $C^{m+2}$ and the boundary points.
Note that $\nu$ and the points $\\{a_{i}\\}$ depend on $(p,e)$ in a definable
way, but we omit this dependence in the notation when not necessary. By
tameness (Lemma 10) $\nu=\nu(p,e)$ is bounded, i.e. there exists
$N\in\mathbb{N}$ such that $\forall(p,e)\in P\times S^{n}$ we have $\nu\leq
N$.

For all $1\leq i\leq N$ we define $I_{i}:=]a_{i},a_{i+1}[$ if $i=1,\ldots,\nu$
and $I_{i}:=\emptyset$ if $\nu<i\leq N$. For $1\leq i\leq\nu$ we define
$\bar{a}_{i}:=(a_{i}+a_{i+1})/2\in I_{i}$. Let $\eta_{i}:=\eta|_{I_{i}}$. By
Lemma 31 $\left(t_{2m+1}\right)^{-1}\eta_{i}$ is a continuous tame function on
$I_{i}$ and, as a distribution, it equals $(\Lambda_{p,e})|_{I_{i}}$. For
$i=1,\ldots,\nu$, we define the following function on $I_{i}$:

(3.2)
$\tilde{\psi}_{p,e,i}(z):=\int_{\bar{a}_{i}}^{z}\int_{\bar{a}_{i}}^{s}\left(\left(t_{2m+1}\right)^{-1}\eta_{i}\right)(w)\mathrm{d}w\mathrm{d}s.$

The integrand is tame and Theorem 6 implies that $\tilde{\psi}_{p,e,i}$ is
tame (as a function of $p$, $e$ and $z$).

For $\alpha,\beta\in\mathbb{R}^{N}$ we let $\psi_{p,e}^{\alpha,\beta}(z)$ be
the function on $[0,1]\setminus\\{a_{i}\\}_{i=1,\ldots,\nu}$ given by

(3.3)
$\psi_{p,e}^{\alpha,\beta}(z):=\sum_{i=1}^{\nu}\left(\tilde{\psi}_{p,e,i}(z)+\alpha_{i}z+\beta_{i}\right)\mathds{1}_{(a_{i},a_{i+1})}(z).$

Condition (i) above if satisfied if and only if there exist
$\alpha,\beta\in\mathbb{R}^{N}$ such that $\psi_{p,e}^{\alpha,\beta}$ extends
to a convex function on $[-1,1]$; note that if such $\alpha,\beta$ exist, the
convex function $\psi_{p,e}^{\alpha,\beta}$ is in $W^{2,1}([-1,1])$ because
its second derivative equals $\Lambda=t_{2m+1}^{-1}\eta$ (which is a
distribution, thus locally, and therefore globally on $[-1,1]$, integrable).

Since $\tilde{\psi}_{p,e,i}$ is tame, and the characteristic functions of the
intervals $(a_{i},a_{i+1})$ are tame, we can express this condition as a first
order formula involving only tame objects, therefore (i) is a tame condition.

Suppose (i) is satisfied, then we can write
$\Lambda_{p,e}-(\psi_{p,e}^{\alpha,\beta})^{(2)}$ as

(3.4)
$\Lambda_{p,e}-(\psi_{p,e}^{\alpha,\beta})^{(2)}=\sum_{i=0}^{m+2}\left(\lambda^{(i)}_{-1}D^{i}\delta_{-1}+\lambda^{(i)}_{1}D^{i}\delta_{1}\right),$

where the order of the distribution is bounded by $m+2$ because of Lemma 31.
Moreover the numbers $\lambda_{\pm 1}^{(i)}$ are tame functions of $(p,e)$.
Indeed by Lemma 21, their expression only involves the value of $P_{k,m}$ from
(2.31), $\eta_{p,e}$ and their derivatives at the points $\pm 1$. Thus
condition (ii) is tame as well:

(3.5) $\mathrm{(ii)}\iff\lambda_{\pm 1}^{(0)}\geq
0\quad\textrm{and}\quad\lambda_{\pm 1}^{(i)}=0\quad\forall i=1,\ldots,m+2.$

This proves that the set $S\mathscr{Z}:=\left\\{(p,e)\in P\times S^{2m+1}\ |\
\Lambda_{p,e}\geq 0\right\\}$ is tame, as claimed.

Now if $n=2m$ is even, $m\geq 1$, we consider the natural embedding

(3.6) $\displaystyle\iota:\mathbb{R}^{2m+1}$
$\displaystyle\hookrightarrow\mathbb{R}^{2m+2}$ (3.7)
$\displaystyle(x_{1},\ldots,x_{2m+1})$
$\displaystyle\mapsto(x_{1},\ldots,x_{2m+1},0),$

which induces an embedding $\iota_{*}$ at the level of convex bodies. A convex
body $K\subset\mathbb{R}^{2m+1}$ is a zonoid if and only if
$\iota_{*}K\subset\mathbb{R}^{2m+2}$ is a zonoid. Moreover we have
$h_{\iota_{*}K}(u)=h_{K}(\pi(u))$ where
$\pi:\mathbb{R}^{2m+2}\to\mathbb{R}^{2m+1}$ is the projection on the first
$2m+1$ coordinates. This implies that the family $\left\\{\iota_{*}K_{p}\ |\
p\in P\right\\}$ is a tame family of convex bodies in $\mathbb{R}^{2m+2}$. In
particular

(3.8) $\mathscr{Z}(P)=\left\\{p\in P\ |\ K_{p}\text{ is a
zonoid}\right\\}=\left\\{p\in P\ |\ \iota_{*}K_{p}\text{ is a
zonoid}\right\\}$

is tame by the previous part of the proof. ∎

## References

  * [AL16] Guillaume Aubrun and Cécilia Lancien.  Zonoids and sparsification of quantum measurements.  Positivity, 20(1):1–23, 2016.
  * [BL18] Peter Buergisser and Antonio Lerario.  Probabilistic schubert calculus.  Crelle’s journal, 2018.  to appear.
  * [BLM89] J. Bourgain, J. Lindenstrauss, and V. Milman.  Approximation of zonoids by zonotopes.  Acta Math., 162(1-2):73–141, 1989.
  * [Bol71] E. D. Bolker.  Research Problems: The Zonoid Problem.  Amer. Math. Monthly, 78(5):529–531, 1971.
  * [BPR06] Saugata Basu, Richard Pollack, and Marie-Françoise Roy.  Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics.  Springer-Verlag, Berlin, second edition, 2006.
  * [CM11] Raf Cluckers and Daniel J. Miller.  Stability under integration of sums of products of real globally subanalytic functions and their logarithms.  Duke Math. J., 156(2):311–348, 2011.
  * [GW92] Paul Goodey and Wolfgang Weil.  Centrally symmetric convex bodies and the spherical Radon transform.  J. Differential Geom., 35(3):675–688, 1992.
  * [GW93] Paul Goodey and Wolfgang Weil.  Zonoids and generalisations.  In Handbook of convex geometry, Vol. A, B, pages 1297–1326. North-Holland, Amsterdam, 1993.
  * [Hir94] Morris W. Hirsch.  Differential topology, volume 33 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1994.  Corrected reprint of the 1976 original.
  * [Kai13] Tobias Kaiser.  Integration of semialgebraic functions and integrated Nash functions.  Math. Z., 275(1-2):349–366, 2013.
  * [LM20] Antonio Lerario and Léo Mathis.  Probabilistic schubert calculus: Asymptotics.  Arnold Mathematical Journal, 2020.
  * [Lon] Yossi Lonke.  A characterization of zonoids.  preprint.
  * [NRZ08] Fedor Nazarov, Dmitry Ryabogin, and Artem Zvavitch.  On the local equatorial characterization of zonoids and intersection bodies.  Adv. Math., 217(3):1368–1380, 2008.
  * [Sch66] Laurent Schwartz.  Théorie des distributions.  Publications de l’Institut de Mathématique de l’Université de Strasbourg, No. IX-X. Nouvelle édition, entiérement corrigée, refondue et augmentée. Hermann, Paris, 1966.
  * [Sch14] Rolf Schneider.  Convex bodies: the Brunn-Minkowski theory, volume 151 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, expanded edition, 2014.
  * [vdD99] Lou van den Dries.  o-minimal structures and real analytic geometry.  In Current developments in mathematics, 1998 (Cambridge, MA), pages 105–152. Int. Press, Somerville, MA, 1999.
  * [Vit91] R. A. Vitale.  Expected absolute random determinants and zonoids.  Ann. Appl. Probab., 1(2):293–300, 1991.
  * [Whi43] Hassler Whitney.  Differentiable even functions.  Duke Math. J., 10(1):159–160, 03 1943.
  * [Wit73] H. S. Witsenhausen.  Metric inequalities and the zonoid problem.  Proc. Amer. Math. Soc., 40:517–520, 1973.