TITLE: how to approximate this expression $\frac{1}{8}x^2(1-\frac{1}{12}x^2)/(1-\frac{1}{4}x^2)$
QUESTION [0 upvotes]: when x is small, for example <1, then the expression can be approximate by (from a book)
$$ g(x)= \frac{-x^2}{8}{\frac { \left( 1-1/12\,{x}^{2} \right) }{1-1/4\,{x}^{2}}
}= \frac{-x^2}{8} \frac{1}{1-1/6{x}^{2}} $$  (1.1)
let $$ f(x)= {\frac { \left( 1-1/12\,{x}^{2} \right) }{1-1/4\,{x}^{2}}
}$$
the  expression $g(x)$ should be dimensionless, so there should be keep a $ {x}^{2}$ in the denom part.
I have known that we can do this using the taylor series, like
$taylor(f(x),x)$ is $(1+{\frac {1}{6}}{x}^{2}+{\frac {1}{24}}{x}^{4}+O \left( {x}^{6}
 \right) )
 $
but this not in denom,
a trick is $taylor(1/f(x),x)$ ,which will be $(1-{\frac {1}{6}}{x}^{2}-{\frac {1}{72}}{x}^{4}+O \left( {x}^{6}
 \right) ) $
so we can get the approximate like the
$$ g(x)= \frac{-x^2}{8}{\frac { 1 }{1-1/6\,{x}^{2}}
}$$
could other person give another method more directly, because I think this is too tricky.
and the second problem is, why we can not just in the numer make $1-x^2/12=1$, and the denom part not changed.
howerver this will get a expression $$ g(x)= \frac{-x^2}{8}{\frac { 1 }{1-1/4\,{x}^{2}}
}$$  (1.2)
(1.2) is not good like (1.1), we can just take a taylor, then we can compare.
but from the first eye, $x^2/8*(1-x^2/12)$ have a term $x^4$ ,when x is small, this can be dropped.
but the fact is cannot, why? Does this means,if $x is not <<1$, but only $<1$, then we can not to drop a term, but have to do a taylor siries.
drop a term is only when the $x->0$, but taylor could get better approximation. even the term is two order high than other terms
comment, these approximate come frome a acoustic problem for a duct absorption problems, the impedance have a part like $$\left[ 1-\dfrac {2} {\sqrt {-i}k}\dfrac {J_{1}\left( \sqrt {-j}k\right) } {J_0\left( \sqrt {-jk}\right) }\right] ^{-1}$$
take the taylor series for $J_1$ and $J_0$, then get the polynom, the do another approximate, do this approximate, we can take the low frequency and high frequency easy.

REPLY [0 votes]: $$\frac{1}{8}x^2\frac{1-\frac{1}{12}x^2}{1-\frac{1}{4}x^2}=\frac18x^2\frac1{(1-(1/4)x^2)(1-(1/12)x^2)^{-1}}\approx\frac18x^2\frac1{(1+(1/12-1/4)x^2)}=\frac18x^2\frac1{(1-(1/6)x^2)}$$
As:
$$(1+x)^n=1+nx+n(n-1)x^2/2+...\approx 1+nx\tag{$x\ll1$}$$
$$(1+ax)(1+bx)=1+(a+b)x+abx^2\approx1+(a+b)x\tag{$x\ll1$}$$


text:
\begin{document}

\title{Acyclic orientations with degree constraints}

\author{Zolt\'an Kir\'aly\thanks{Research is supported by a grant (no.\ K
    109240) from the National Development Agency
    of Hungary, based on a source from the Research and Technology Innovation
    Fund.
  }\\[-0.8ex]
\small E\"otv\"os Lor\'and University \\[-0.8ex]
\small Department of Computer Science \\[-0.8ex]
\small P\'azm\'any P\'eter s\'et\'any 1/C \\[-0.8ex]
\small Budapest, Hungary, H-1117\\[-0.8ex]
\small \texttt{kiraly@cs.elte.hu}
  \and
  D\"om\"ot\"or P\'alv\"olgyi\thanks{Research is supported by the Lend\"ulet program of the Hungarian Academy of Sciences (MTA), under grant number LP2017-19/2017.
}\\[-0.8ex]
  \small MTA-ELTE Lend\"ulet Combinatorial Geometry Research Group\\[-0.8ex]
	\small E\"otv\"os Lor\'and University \\[-0.8ex]
\small Department of Computer Science \\[-0.8ex]
\small P\'azm\'any P\'eter s\'et\'any 1/C \\[-0.8ex]
\small Budapest, Hungary, H-1117\\[-0.8ex]
\small \texttt{dom@cs.elte.hu}
}

\maketitle

\begin{abstract}
  In this note we study the complexity of some generalizations of the notion of $st$-numbering.
	Suppose that given some functions $f$ and $g$, we want to order the vertices of a graph such that every vertex $v$ is preceded by at least $f(v)$ of its neighbors and succeeded by at least $g(v)$ of its neighbors.
	We prove that this problem is solvable in polynomial time if $fg\equiv 0$, but it becomes NP-complete for $f\equiv g \equiv 2$.
	This answers a question of the first author posed in 2009.
\end{abstract}

\section{Introduction}

In this paper $G=(V,E)$ always denotes an undirected connected graph,
parallel edges are allowed but loops are not.
We use $n=|V|$, $d(v)$ for the degree of a vertex $v\in V$ and
$d(v,Y)$ for the number of edges going from $v$ to $Y$.
For a function $f: V\to \N$, we use the notation $f(X)=\sum_{x\in X}
f(x)$ for any $X\subseteq V$.

In a digraph, the indegree (number of incoming arcs) of a
vertex $v$ (or of a set $X\subseteq V$)
is denoted by $\rho(v)$ (or $\rho(X)$, resp.)
and the outdegree is denoted by $\delta(v)$ (or $\delta(X)$, resp.).

The first named author proposed to study the complexity of the following problem in
2009 in Category ``Orientations'' of EgresOpen \cite{egresopen}.

\begin{problem}[\cite{egresopen}]\label{pr1}
Given $G=(V,E)$ and $s,t\in V$ and positive integers $k,\ell$,
decide whether $G$ has an \emph{acyclic} orientation where for every
vertex $v\in V\setminus\{s,t\}$, there are $k$
pairwise arc-disjoint directed paths from $s$ to $v$, and $\ell$
pairwise arc-disjoint directed paths from $v$ to $t$.
\end{problem}

In this paper we settle the complexity of this problem by show that it is NP-complete, already for $k=\ell=2$.

A more general problem that plays a central role in this note, is the following.
We are given $G=(V,E)$ and two functions
  $f: V\to \N$ and $g: V\to \N$ with
$f(v)+g(v)\le d(v)$ for each $v\in V$. An orientation of $G$ is called
$(f,g)$-\emph{bounded} if $f(v)\le\rho(v)\le d(v)-g(v)$ for each $v\in V$.

\begin{problem}[Degree constrained acyclic orientation problem]\label{dcaop}
  Given $G,f,g$, decide whether $G$ has an \emph{acyclic}
  $(f,g)$-bounded orientation.
\end{problem}

Note that $f(v)$ is a lower bound for the indegree of $v$ while
$g(v)$ is a lower bound for the outdegree of $v$ as we are dealing with
orientations, so $\delta(v)=d(v)-\rho(v)$.

\begin{claim}\label{claim}
  Problem \ref{pr1} is equivalent to the degree constrained acyclic orientation
  problem if $f(v)=k$ and  $g(v)=\ell$ for all $v\in V\setminus\{s,t\}$;
  and $f(s)=g(t)=0, \; g(s)=f(t)=d(s)$.
\end{claim}

\prf If the prescribed pairwise arc-disjoint directed paths exist,
then obviously
for every $v\in V\setminus\{s,t\}$ we have $\rho(v)\ge k$ and
$\delta(v)\ge \ell$.

Suppose we have an orientation $\oG$ where all $v\in V\setminus\{s,t\}$ have
$\rho(v)\ge k$ and
$\delta(v)\ge \ell$. This orientation defines a (not necessarily unique)
topological order, $V=\{v_1,\ldots,v_n\}$, such that for every directed edge
$v_iv_j$ we have $i<j$ (we may suppose $v_1=s$ and $v_n=t$).
By symmetry and by Menger's theorem, it is enough to prove that for any
$X\subseteq V$ if $s\not\in X$, then $\rho (X)\ge k$. Let $v_i$ be the first
vertex of $X$.
As $s\not\in X$ we have $i>1$.
Clearly $\rho(X)\ge\rho(v_i)\ge k$.\qed

\section{Polynomially solvable cases}

First we examine the special case of Problem \ref{dcaop} when $g(v)=0$ for all $v$, i.e., only lower
bounds on the indegrees are given.
For a set $X\subseteq V$, we call a vertex $x\in X$ a \emph{potential source}
if $f(x)\le d(x,V\setminus X)$.

\begin{cond}\label{cond}
  For every non-empty set $X\subseteq V$, there exists an $x\in X$ which is a
  potential source for $X$.
\end{cond}

\begin{thm}[Folklore]\label{thm_poli_upper}
There exists an acyclic orientation of $G$ where $\rho(v)\ge f(v)$ for every
$v\in V$ if and only if
Condition \ref{cond} is satisfied. Moreover, such an orientation can be produced
(and simultaneously Condition \ref{cond} can be checked) by a greedy
algorithm.
\end{thm}

\prf If the orientation exists, then for each $X$ take $x$ as the first vertex
of it (by a topological order). Clearly $f(x)\le\rho(x)\le d(x,V\setminus X)$.

Suppose Condition \ref{cond} is satisfied.
By applying it to $X=V$, we obtain a vertex $v_1$ with $f(v_1)=0$.
Let $G':=G-v_1$ and for any $v\in V\setminus\{v_1\}$ let $f'(v):=\max(f(v)-d(v_1,v),0)$.
Clearly Condition \ref{cond} is satisfied for the new $G'$ and $f'$, thus, by
induction, there is an acyclic orientation of $G'$ where the indegrees are
lower-bounded by $f'$. The required orientation of $G$ is given by orienting
the edges incident with $v_1$ from $v_1$.

If, at some point of this recursive process, we do not have any
vertex $v$ such that the current $f(v)$ is $0$, then the
set $X$ of the current vertices violates Condition \ref{cond}.
Otherwise we get the orientation required, thus by the first part of the
proof Condition \ref{cond} is satisfied.
\qed

We can go a little bit further.

\begin{thm}\label{thm_upper-or-lower}
  If $G=(V,E)$ and $f(v)g(v)=0$ for every $v\in V$
  (i.e., every vertex has either only a
  lower bound or only an upper bound on the indegree), then we can decide in
  polynomial time whether there is an $(f,g)$-bounded acyclic orientation of
  $G$.
\end{thm}
\prf Let $A=\{v\in V \;|\; f(v)=0, \; g(v)>0\}, \;
B=\{v\in V \;|\; f(v)=0, \; g(v)=0\}, \;
C=\{v\in V \;|\; f(v)>0, \; g(v)=0\}$, by the condition of the theorem these
three sets partition $V$. Call an acyclic orientation ABC if
there is a topological order where the vertices of $A$ come first, then the
vertices of $B$, and finally the vertices of $C$.
It is easy to observe that if an $(f,g)$-bounded acyclic orientation of
  $G$ exists, then there is another one which is ABC.
Let $G'=G[A]$, and $f'(a)=0, \; g'(a)=\max(g(a)-d(a,V\setminus A),0)$ for $a\in A$.
Furthermore let $G''=G[C]$ and $f''(c)=\max(f(c)-d(c,V\setminus C),0), \; g''(c)=0$
for $c\in C$.
By Theorem \ref{thm_poli_upper}, we can check in polynomial time whether
there is an $(f',g')$-bounded acyclic orientation of
  $G'$ and  whether
there is an $(f'',g'')$-bounded acyclic orientation of
  $G''$.
\qed

We call a vertex $v$ \emph{strict} if $f(v)+g(v)=d(v)$.
The next special case we study is, when every vertex is strict.

\begin{thm}\label{thm_poli_strict}
There exists an acyclic orientation of $G$ where $\rho(v)= f(v)$ for every
$v\in V$ if and only if $f(V)=|E|$ and
Condition \ref{cond} is satisfied. Moreover, such an orientation can be produced
(and simultaneously Condition \ref{cond} can be checked) by a greedy
algorithm.
\end{thm}

\prf Observe that if $f(V)=|E|$, then $\rho(v)\ge f(v)$ for every $v$ if
and only if $\rho(v)=f(v)=d(v)-g(v)$ for every $v$.
\qed

We have one more sporadic example where the problem is known to be
in P, see Theorem \ref{k_is_1} in the last subsection.

\section{NP-complete cases}

\begin{thm}\label{NPC}
  The degree constrained acyclic orientation problem
(Problem \ref{dcaop})
  is NP-complete.
\end{thm}

We prove a much stronger theorem about a very restricted version of
Problem \ref{dcaop}.

\begin{thm}\label{main-NPC}
  The degree constrained acyclic orientation problem is NP-complete even if
  every vertex $v$ is $\rho$-lower-bounded by 0 or 1
  (i.e., $f(v)\le 1$ and $g(v)=0$)
  except one vertex y, which is strict (i.e., $f(y)+g(y)=d(y)$).
\end{thm}

\prf As the problem is obviously is in class NP, it is enough to show its
hardness.
We reduce the well-known NP-complete problem {\sc Vertex-Cover} \cite{GJ}
to this restricted version. In the problem {\sc Vertex-Cover}, a graph $G=(V,E)$
and an integer $k\le |V|$ is given and we have to decide whether there is a set
$T\subseteq V$ with $|T|=k$ such that every edge has at least one endvertex
in $T$.

Given $G=(V,E)$ and $k$, we need to construct $G'=(V',E')$ and functions
$f,g$. Let $V'=V\cup E\cup \{y\}$ (where $y\not\in V\cup E$).
Let $m=|E|,\; M=m+1$ and $E'=\{ve \;|\; v\in V,\; e\in E,\; v$ is incident to
$e\} \cup \{ye  \;|\; e\in E\} \cup M\{yv  \;|\; v\in V\}$,
where the last edge-set is meant to have $M$ parallel edges between $y$ and
any vertex $v\in V$. The construction of $G'$ is finished, its degree-function
is denoted by $d'$.

Let $f(v)=0$ for $v\in V$, $f(e)=1$ for $e\in E$ and $f(y)=m+kM$.
Let $g(v)=0$ for $v\in V$, $g(e)=0$ for $ e\in E$ and $g(y)=(n-k)M=d'(y)-f(y)$.
We need to prove that $G$ has a cover $T$ of size $k$ if and
only if $G'$ has an acyclic orientation satisfying these degree bounds.
First suppose $T$ is such a cover and let $E_2\subseteq E$ denote the edges
with both endvertices in $T$. As $T$ is a cover, every edge in
$E_1=E\setminus E_2$ connects $T$ to $V\setminus T$. Define an order on $V'$ as follows.
We start by putting vertices of $T$ (in any order), then elements of $E_1$, then
$y$, and finally vertices of $V\setminus T$ (in any order).
We still need to place each $uv\in E_2$,
we put such an edge between $u$ and $v$ (thus it will precede exactly one of
its endvertices). This order defines an acyclic orientation of $G'$
(edges oriented from earlier vertex to the later one). The indegree of any
$e\in E$ is exactly one and $\rho(y)=m+kM$, thus this acyclic orientation is
indeed $(f,g)$-bounded.

For the other direction, suppose there exists an acyclic $(f,g)$-bounded
orientation of $G'$, and fix any topological order.  First we claim that $y$
is preceded by every $e\in E$ and by exactly $k$ elements of $V$ (call this
latter subset $T$). If $y$ is preceded by at most $k-1$ elements of $V$, then
$\rho(y)\le (k-1)M+m<f(y)=kM+m$.  If $y$ is preceded by at least $k+1$
elements of $V$, then $\rho(y)\ge (k+1)M>d'(y)-g(y)=kM+m$. Accordingly,
exactly $k$ vertices of $V$ precedes $y$, and as its indegree is exactly $kM+m$,
necessarily every $e\in E$ must also precede it.

It remains to prove that $T$ is a cover in $G$. Suppose this is not the case,
there is an $e=uv\in E$ with $u\not\in T$ and $v\not\in T$. As $e$ precedes
$y$ and $y$ precedes both $u$ and $v$, $\rho(e)=0<f(e)=1$, a contradiction.
\qed

The graph $G'$ used in the proof is not simple.
However, one can split every edge $e$ of $G'$ with a new vertex $w_e$ and
define $f(w_e)=g(w_e)=1$. This gives the following corollary.

\begin{coroll}\label{simple}
  The degree constrained acyclic orientation problem for \emph{simple} graphs
  is NP-complete even if for
  every vertex $v$ either $f(v)+g(v)=d(v)$ (i.e., $v$ is strict) or
  $f(v)\le 1$ and $g(v)=0$ ($v$ is lower-bonded by 0 or 1).
\end{coroll}

\begin{thm}\label{egres-NPC}
Problem \ref{pr1} is NP-complete.
\end{thm}

\prf We reduce Problem \ref{dcaop} to Problem \ref{pr1}.
Given $G,f,g$, we construct an instance of Problem \ref{pr1} as follows.
First we fix $k=\ell$ as the maximum degree in $G$.
We add two new vertices, $s$ and $t$. Then for each vertex $v$ we add
$k-f(v)$ parallel edges between $s$ and $v$, and we also add $k-g(v)$
parallel edges between $t$ and $v$. Let $G'=(V',E')$ denote the resulting
graph (where $V'=V\cup\{s,t\}$).

By Claim \ref{claim}, it is enough to show that the following are equivalent.
\begin{itemize}
\item $G'$ has an acyclic orientation with source $s$ and sink $t$ where for
  every $v\in V$, we have $\rho'(v)\ge k$ and $\delta'(v)\ge k$.
\item $G$ has an acyclic $(f,g)$-bounded orientation.
\end{itemize}

First suppose we have the above acyclic orientation of $G'$.
After deleting $s$ and $t$, we get an acyclic orientation of $G$ where, for
every $v\in V$, we have $\rho(v)=\rho'(v)-k+f(v)\ge f(v)$, and
$\delta(v)=\delta'(v)-k+g(v)\ge g(v)$.

Next suppose  we have an acyclic orientation of $G$ where for
every $v\in V$ we have $f(v)\le\rho(v)\le d(v)-g(v)$.
To orient $G'$, we keep the
orientation of the original edges and orient the edges of form $sv$ from $s$
to $v$, and the edges of form $vt$ from $v$ to $t$;
resulting in an acyclic orientation of $G'$.
As $\rho'(v)=\rho(v)+k-f(v)$, we get $\rho'(v)\ge k$. We also have
$\delta'(v)=\delta(v)+k-g(v)\ge k$.
\qed

\subsection{Problem \ref{pr1} for small $k$ values}

We proved that Problem \ref{pr1} is NP-complete if $k$ and $\ell$ are
part of the input.
What can we say about its status if $k$ and $\ell$ are fixed  small numbers?

The first case is well known, it was solved in \cite{LEC} where
$st$-numbering was introduced.

\begin{thm}[\cite{LEC}]\label{k_is_1}
  If $k=\ell$ is fixed to one,
  then we can answer Problem \ref{pr1} in polynomial
  time, namely there is a required orientation if and only if $G+st$ is
  biconnected.
\end{thm}

On the other hand, we can prove the following.

\begin{thm}\label{thm_NPC_k=3}
Problem \ref{pr1} is NP-complete for $k=\ell=2$.
\end{thm}

\prf
The problem is obviously in NP.
We will reduce the problem {\sc Not-all-Equal}
3SAT \cite{GJ} to it.
In the problem {\sc Not-all-Equal} 3SAT there are variables $x_1,\dots,x_n$ and
clauses $C_1,\dots,C_m$, each clause contains exactly three literals
(a literal is a variable or a negated variable), and we
need to decide whether there is a truth assignment to the variables such that
every clause has at least one \igaz and at least one \hamis literal in it.
Given a {\sc Not-all-Equal} 3SAT instance, we first construct the multigraph $G$ as follows.

\noindent
$V:=\{s\!=\!a_0, a_1, a_2,\dots, a_{4n+2m}, a_{4n+2m+1}\!=\!t,\; y_1,\dots,y_n, z_1,\dots,z_n, C_1,\dots,C_m\}\cup$
$\cup\{x_1,\dots,x_n,\bar{x}_1,\dots,\bar{x}_n\}$.

First we add edges to make the ``skeleton''.
We add two parallel edges between $a_{2i}$ and $a_{2i+1}$ for
$i=0,\dots,2n+m$. We also add one edge between $a_{2i-1}$ and $a_{2i}$ for
$i=1,\dots,2n+m$.
Then we connect $a_{2i-1}$ to $y_i$ and $y_i$ to $a_{2i}$,
and we also connect $a_{2n+2m+2i-1}$ to $z_i$ and $z_i$ to $a_{2n+2m+2i}$ for
$i=1,\dots,n$.
To finish the skeleton we connect $a_{2n+2j-1}$ to $C_j$ and $C_j$ to
$a_{2n+2j}$ for $j=1,\dots,m$.

\begin{figure}[!ht]
      \centering
      \smallskip
      \includegraphics{construction.eps}
\begin{center}
      \caption{The construction for $n=3,\; m=1,\; C_1=x_1\vee \bar{x}_2\vee
        x_3$
      (except the parallel edges between the literals and $s$ and $t$ added at the end).}\label{fig_constr}
\end{center}
\end{figure}

We are left to connect the literals to the skeleton.
For $i=1,\dots,n$, we connect both $x_i$ and $\bar{x}_i$ to $y_i$ and $z_i$.
Then for $j=1,\dots,m$, we connect $C_j$ to the three literals it contains.
Finally we add two parallel edges between $s$ and any literal, and also
between $t$ and every literal.

The construction of $G$ is finished, see Figure \ref{fig_constr}.

Note
that the vertices $a_1,\dots,a_{4n+2m}$ have degree four
as well as vertices $y_1,\dots,y_n$ and $z_1,\dots,z_n$, while vertices
$C_1,\dots,C_m$ have degree five.

First we show that if we have an assignment to the variables such that every
clause has at least one and at most two \igaz literals in it, then we can make
an acyclic orientation of $G$
where for every vertex $v\in V\setminus\{s,t\}$ we have $\rho(v)\ge 2$ and
$\delta(v)\ge 2$.
We give the orientation by defining the topological order.
First we define the order of the skeleton:
$$a_0,a_1,y_1,a_2,a_3,y_2,a_4,\dots,y_n,a_{2n},a_{2n+1},
C_1,a_{2n+2},a_{2n+3},\dots,a_{2n+2m-1},C_m,$$
$$a_{2n+2m},a_{2n+2m+1},z_1,a_{2n+2m+2},\dots,a_{4n+2m-1},z_n,a_{4n+2m},a_{4n+2m+1}.$$
Note that the vertices $a_i$ are ordered by the indices, and every
$y_i, z_i, C_j$ is between its two neighbors.
So far each $a_i$ has indegree 2 and outdegree 2 for $1\le i\le 4n+2m$ and
vertices $y_i, z_i, C_j$ have indegree 1 and outdegree 1.
Finally we place all the \igaz literals between $a_1$ and $y_1$ (in any order),
and we place all the \hamis literals between $z_{n}$ and $a_{4n+2m}$
(in any order). First note that due to the parallel edges added at the end,
every literal  has at least two incoming and at least two outgoing arcs.
As any vertex $y_i$ or $z_i$ is preceded by the \igaz literal, and succeeded by the \hamis
literals, every $y_i$ and $z_i$ has
indegree and outdegree exactly two.
Finally, a clause is preceded by its \igaz literals, we have one or two of them,
consequently either its indegree is two and its outdegree is three,
or vice versa.

It remains to show that if the required acyclic orientation exists, then we
have an assignment to the variables such that each clause gets one or two
\igaz values. Take the topological order of a good acyclic orientation.
First we claim that the skeleton is in the same order as we defined in the
previous part. Suppose for a contradiction that $i$ is the smallest index $(1\le i\le 4n+2m-1)$
such that $a_{i+1}$ precedes $a_i$. In this case $a_i$ has at least three
incoming arcs, so this case is impossible. Next suppose that $w$ is the first
vertex from $y_1,\dots, y_n, C_1,\dots, C_m, z_1,\dots, z_n$ which is not
between its two $a_i$-neighbors. If it is before that place, then its
lower-indexed  $a_i$-neighbor has indegree three, if it is after that place,
then its higher-indexed  $a_i$-neighbor has outdegree three. Next observe
that for all $1\le i\le n$, one of $x_i$ and  $\bar{x}_i$  must be before
$y_i$ (consequently before $a_{2n}$) and the other must be after $z_i$
 (consequently after $a_{2n+2m}$), since otherwise either $y_i$ or $z_i$ does
not have the prescribed indegree two.
Now we can define the assignment: a literal is \igaz if it precedes $a_{2n}$.
To finish the proof, observe that if $C_j$ has for example three \igaz
literals, then its indegree is four, so its outdegree is only one.
\qed

\bigskip

The graph $G$ used in the above proof is not simple, actually the answer is
always NO for a simple graph, as the second vertex cannot have two incoming
arcs.
However, one can split any edge $e=uv$ of $G$ with a new degree four vertex $w_e$ that is connected to $s,u,v,t$.
Such a $w_e$ must necessarily be between $u$ and $v$, thus their in- and outdegrees will not be affected.
This way we can obtain a graph that is almost simple - only edges adjacent to $s$ or $t$ might have multiplicity $2$.

By splitting $s$ into two vertices, $s_1$ and $s_2$, and similarly $t$ into $t_1$ and $t_2$, and dividing the multiple edges among them, we obtain that the following problem is NP-complete.

\begin{problem}
	Given a simple graph $G=(V,E)$ and $s_1,s_2,t_1,t_2\in V$,
	decide whether there is an order of the vetrtices such that
        every vertex $v\in V\setminus\{s_1,s_2,t_1,t_2\}$ has at least
        $2$ neighbors preceding it and also at least $2$ neighbors succeedenig
        it.
\end{problem}

Some of the questions left open are the following.

\begin{opprob}
Is Problem \ref{pr1} in P for the special case $k=2$ and $\ell=1$?
\end{opprob}

\begin{opprob}
  Is Problem \ref{dcaop} in P for the special case $f(v)+g(v)\le 2$ for all
  $v\in V$?
\end{opprob}

\begin{opprob}
  Is Problem \ref{dcaop} in P for the special case $f(v)+g(v)\le 3$ for all
  $v\in V$?
\end{opprob}

\begin{opprob}
	Is Problem \ref{dcaop} in P for the special case $f(v)g(v)\le 1$ for all
	$v\in V$?
\end{opprob}

config: arxiv


text:
\begin{document}
\maketitle

\noindent\textbf{Abstract.}\ \
Quantum Bernoulli noises are annihilation and creation operators acting on Bernoulli functionals,
which satisfy the canonical anti-commutation relations (CAR) in equal-time.
In this paper, we use quantum Bernoulli noises to introduce a model of open quantum walk on the $d$-dimensional
integer lattice $\mathbb{Z}^d$ for a general positive integer $d\geq 2$, which we call the $d$-dimensional open QBN walk.
We obtain a quantum channel representation of the $d$-dimensional open QBN walk,
and find that it admits the ``separability-preserving'' property.
We prove that, for a wide range of choices of its initial state,
the $d$-dimensional open QBN walk has a limit probability distribution of $d$-dimensional Gauss type.
Finally we unveil links between the $d$-dimensional open QBN walk and the unitary quantum walk recently introduced in
[Ce Wang and Caishi Wang, Higher-dimensional quantum walk in terms of quantum Bernoulli noises, Entropy 2020, 22, 504].
\vskip 2mm

\noindent\textbf{Keywords}\ \  Open quantum walk; Quantum Bernoulli noises;  Quantum probability.
\vskip 2mm

\noindent\textbf{Mathematics Subject Classification}\ \  81S25; 81S22

\section{Introduction}

Open quantum walks (OQW for short) are also known as open quantum random walks,
which are quantum analogs of classical Markov chains in probability theory.
As a new type of quantum walks, OQWs are finding application in the generalisations of the theory of quantum probability,
and have potential application in dissipative quantum computation, quantum state engineering
and transport in mesoscopic systems \cite{sinayskiy}.

Unlike unitary quantum walks (UQW for short), which have been well studied (see \cite{kemp,konno-1, venegas} and references therein),
the dynamics of OQWs are non-unitary due to the effects of the local environments.
Indeed, OQWs, step by step, describe typically quantum behaviors, but seem to show up a rather classical asymptotic behavior \cite{attal-2}.

The first model of OQW was introduced by Attal, Petruccione, Sabot and Sinayskiy
in 2012 (see \cite{attal-1} for details). Since then, much attention has been paid to OQWs.
Attal \textit{et al}  \cite{attal-2} established the central limit theorem (CLT)
for a class of homogeneous OQWs on $\mathbb{Z}^d$ with a unique invariant state.
Konno and Yoo  \cite{konno-2} applied the CLT to the study of limit probability distributions for various OQWs.
Sadowski and Pawela \cite{sadowsk} investigated a generalisation of the CLT for the case of nonhomogenous OQWs.
Sinayskiy and Petruccione examined the properties of OQWs on the $1$-dimensional integer lattice $\mathbb{Z}$ for the case
of simultaneously diagonalisable transition operators \cite{sinayskiy-0}.
Carbone and Pautrat \cite{carbone}, from a perspective of classical Markov chain,
introduced notions of irreducibility, period, communicating classes for OQWs.
Lardizabal \cite{lardizabal} defined a notion of hitting time for OQWs and obtained some useful
formulas for certain cases. There are many other researches on OQWs
(see the recent survey article \cite{sinayskiy} by Sinayskiy and Petruccione and references therein).

From a physical point of view, OQWs are quantum walks where the transitions between the sites
(or vertices) are driven by the interaction with an environment, which can
cause dissipation and decoherence. This suggests that the effects of an environment play an important role
in the time evolution of the involved OQW.
On the other hand, quantum Bernoulli noises \cite{w-c-l} have turned out to be an alternative approach to the environment of
an open quantum system (see, e.g. \cite{w-t-r} and references therein).
It is then natural to apply quantum Bernoulli noises to the study of OQWs.

In 2018, by using quantum Bernoulli noises, Wang \textit{et al} \cite{w-w-r-t} introduced
a model of OQW on the $1$-dimensional integer lattice $\mathbb{Z}$,
which we call \textbf{the $1$-dimensional open QBN walk} below. In this paper,
we would like to extend the $1$-dimensional open QBN walk to a higher-dimensional case.
More specifically, for a general integer $d\geq 2$, we will introduce a model of OQW
on the $d$-dimensional integer lattice $\mathbb{Z}^d$ in terms of quantum Bernoulli noises
and examine its dynamical behavior from a perspective of probability distribution.
Our main work is as follows. Let $\mathcal{H}$ be the space of square integrable Bernoulli functionals and
$\mathscr{T}^{(d)}(\mathcal{H})$ the set of $d$-dimensional nucleuses on $\mathcal{H}$
(see Definition~\ref{def-2-2} for its exact meaning).
\begin{itemize}
  \item By using quantum Bernoulli noises, we construct a sequence of mappings
        $\mathfrak{J}_n^{(d)}$, $n\geq 0$, on $\mathscr{T}^{(d)}(\mathcal{H})$
         to describe the change in the internal degree of freedom of the walker.
  \item With the above-mentioned mappings $\mathfrak{J}_n^{(d)}$, $n\geq 0$, as the main tool, we establish our model of OQW
        on the $d$-dimensional integer lattice $\mathbb{Z}^d$, which we call \textbf{the $d$-dimensional open QBN walk}.
  \item We obtain a quantum channel representation of the $d$-dimensional open QBN walk and find
        that it admits the ``separability-preserving'' property.
  \item We prove that, for a wide range of choices of its initial state, the $d$-dimensional open QBN walk has
        a limit probability distribution of $d$-dimensional Gauss type.
  \item We unveil links between the $d$-dimensional open QBN walk and the unitary quantum walk recently introduced in \cite{w-w},
        which was called the $d$-dimensional QBN walk therein.
\end{itemize}
Some other interesting results are also proven.

The paper is organized as follows. In Subsection~\ref{subsec-2-1}, we briefly recall some necessary notions
and facts about quantum Bernoulli noises.
Subsections~\ref{subsec-2-2}, \ref{subsec-2-3} and \ref{subsec-2-4} are one part of our main work,
which includes several technical theorems we prove, the definition of our model of OQW (namely the $d$-dimensional open QBN walk)
and its quantum channel representation, among others.
Another part of our main work lies in Sections~\ref{sec-3} and~\ref{sec-4}, where we show that
the walk admits the ``separability-preserving'' property,
we prove that, for a wide range of choices of its initial state, the walk has
a limit probability distribution of $d$-dimensional Gauss type,
and finally we show links between the $d$-dimensional open QBN walk and the unitary quantum walk recently introduced in \cite{w-w}.

Throughout this paper, $\mathbb{Z}$ always denotes the set of all integers, while
$\mathbb{N}$ means the set of all nonnegative integers. For a positive integer $d\geq 2$, we use $\mathbb{Z}^d$ to mean
the $d$-dimensional integer lattice.
We denote by $\Gamma$ the finite power set of $\mathbb{N}$, namely
\begin{equation}\label{eq-1-1}
    \Gamma
    = \{\,\sigma \mid \text{$\sigma \subset \mathbb{N}$ and $\#\,\sigma < \infty$} \,\},
\end{equation}
where $\#\sigma$ means the cardinality of $\sigma$.
If $\mathcal{X}$ is a Hilbert space and $d\geq 2$ a positive integer, then $\mathcal{X}^{\otimes n}$ denotes the $d$-fold tensor product of $\mathcal{X}$. We denote by $\mathfrak{B}(\mathcal{X})$ the set of all bounded linear operators on $\mathcal{X}$.
As usual, a density operator on a Hilbert space means a positive operator of trace class with unit trace on that space.
By convention, $\mathrm{Tr}A$ denotes the trace of an operator of trace class $A$.
Unless otherwise stated, letters like $j$, $k$ and $n$ stand for nonnegative integers, namely elements of $\mathbb{N}$.

\section{Definition of walk and its basic properties}\label{sec-2}

In this section, we first define our model of OQW (open quantum walk) on the $d$-dimensional integer lattice $\mathbb{Z}^d$
by using quantum Bernoulli noises, which we will call the $d$-dimensional open QBN walk,
and then we examine its basic properties.

\subsection{Quantum Bernoulli noises}\label{subsec-2-1}

We first briefly recall some necessary notions and facts about quantum Bernoulli noises.
We refer to \cite{w-c-l} for details about quantum Bernoulli noises.

Let $\Omega$ be the set of all functions $f\colon \mathbb{N} \mapsto \{-1,1\}$, and
$(\zeta_n)_{n\geq 0}$ the sequence of canonical projections on $\Omega$ given by
\begin{equation}\label{eq-2-1}
    \zeta_n(f)=f(n),\quad f\in \Omega.
\end{equation}
Let $\mathscr{F}$ be the $\sigma$-field on $\Omega$ generated by the sequence $(\zeta_n)_{n\geq 0}$,
and $(p_n)_{n\geq 0}$ a given sequence of positive numbers with the property that $0 < p_n < 1$ for all $n\geq 0$.
Then there exists a unique probability measure $\mathbb{P}$ on $\mathscr{F}$ such that
\begin{equation}\label{eq-2-2}
\mathbb{P}\circ(\zeta_{n_1}, \zeta_{n_2}, \cdots, \zeta_{n_k})^{-1}\big\{(\epsilon_1, \epsilon_2, \cdots, \epsilon_k)\big\}
=\prod_{j=1}^k p_j^{\frac{1+\epsilon_j}{2}}(1-p_j)^{\frac{1-\epsilon_j}{2}}
\end{equation}
for $n_j\in \mathbb{N}$, $\epsilon_j\in \{-1,1\}$ ($1\leq j \leq k$) with $n_i\neq n_j$ when $i\neq j$
and $k\in \mathbb{N}$ with $k\geq 1$. Thus one has a probability measure space $(\Omega, \mathscr{F}, \mathbb{P})$,
which is referred to as the Bernoulli space and random variables on it are known as Bernoulli functionals.

Let $Z=(Z_n)_{n\geq 0}$ be the sequence of Bernoulli functionals generated by sequence $(\zeta_n)_{n\geq 0}$, namely
\begin{equation}\label{eq-2-3}
   Z_n = \frac{\zeta_n + q_n - p_n}{2\sqrt{p_nq_n}},\quad n\geq0,
\end{equation}
where $q_n = 1-p_n$. Clearly $Z=(Z_n)_{n\geq 0}$ is an independent sequence of random variables on the
probability measure space $(\Omega, \mathscr{F}, \mathbb{P})$.
Let $\mathcal{H}$ be the space of square integrable complex-valued Bernoulli functionals, namely
\begin{equation}\label{eq-2-4}
  \mathcal{H} = L^2(\Omega, \mathscr{F}, \mathbb{P}).
\end{equation}
We denote by
$\langle\cdot,\cdot\rangle$ the usual inner product of the space $\mathcal{H}$, and by $\|\cdot\|$ the corresponding norm.
It is known that $Z$ has the chaotic representation property.
Thus $\mathfrak{Z} = \{Z_{\sigma}\mid \sigma \in \Gamma\}$  form an orthonormal basis (ONB) of $\mathcal{H}$,
which is known as the canonical ONB of $\mathcal{H}$.
Here $Z_{\emptyset}=1$ and
\begin{equation}\label{eq-2-5}
    Z_{\sigma} = \prod_{j\in \sigma}Z_j,\quad \text{$\sigma \in \Gamma$, $\sigma \neq \emptyset$}.
\end{equation}
Clearly $\mathcal{H}$ is infinite-dimensional as a complex Hilbert space.

It can be shown that \cite{w-c-l}, for each $k\in \mathbb{N}$, there exists a bounded operator $\partial_k$ on
$\mathcal{H}$ such that
\begin{equation}\label{eq-2-6}
    \partial_k Z_{\sigma} = \mathbf{1}_{\sigma}(k)Z_{\sigma\setminus k},\quad \partial_k^{\ast} Z_{\sigma}
    = [1-\mathbf{1}_{\sigma}(k)]Z_{\sigma\cup k}\quad
    \sigma \in \Gamma,
    \sigma \in \Gamma,
\end{equation}
where $\partial_k^{\ast}$ denotes the adjoint of $\partial_k$, $\sigma\setminus k=\sigma\setminus \{k\}$, $\sigma\cup k=\sigma\cup \{k\}$
and $\mathbf{1}_{\sigma}(k)$ the indicator of $\sigma$ as a subset of $\mathbb{N}$.

The operators $\partial_k$ and $\partial_k^{\ast}$ are usually known as the annihilation and
creation operators acting on Bernoulli functionals, respectively.
And the family $\{\partial_k, \partial_k^{\ast}\}_{k \geq 0}$ is referred to as \textbf{quantum Bernoulli noises}.

A typical property of quantum Bernoulli noises is that they satisfy
the canonical anti-commutation relations (CAR) in equal-time \cite{w-c-l}.
More specifically, for $k$, $l\in \mathbb{N}$, it holds true that
\begin{equation}\label{eq-2-7}
    \partial_k \partial_l = \partial_l\partial_k,\quad
    \partial_k^{\ast} \partial_l^{\ast} = \partial_l^{\ast}\partial_k^{\ast},\quad
    \partial_k^{\ast} \partial_l = \partial_l\partial_k^{\ast}\quad (k\neq l)
\end{equation}
and
\begin{equation}\label{eq-2-8}
   \partial_k\partial_k= \partial_k^{\ast}\partial_k^{\ast}=0,\quad
   \partial_k\partial_k^{\ast} + \partial_k^{\ast}\partial_k=I,
\end{equation}
where $I$ is the identity operator on $\mathcal{H}$.

For a nonnegative integer $n\geq 0$, one can define, respectively, two self-adjoint operators $L_n$ and $R_n$ on $\mathcal{H}$ in the following manner
\begin{equation}\label{eq-2-9}
L_n = \frac{1}{2}(\partial_n^* + \partial_n -I),\quad R_n=\frac{1}{2}(\partial_n^* + \partial_n +I).
\end{equation}
It then follows from the properties of quantum Bernoulli noises that the operators $L_n$, $R_n$, $n\geq 0$, form a commutative family, namely
\begin{equation}\label{eq-2-10}
  L_kL_l = L_lL_k,\quad R_kL_l = L_lR_k,\quad R_kR_l = R_lR_k,\quad k,\, l\geq 0.
\end{equation}

\begin{lemma}\label{lem-2-3}\cite{w-w-r-t}
For all $n\geq 0$, operators $L_n$ and $R_n$ admit the following operational properties
\begin{equation}\label{eq-2-11}
L_n^2=-L_n,\quad L_nR_n=R_n L_n=0,\quad R_n^2=R_n,\quad L_n^2 + R_n^2=I.
\end{equation}
\end{lemma}

\subsection{Technical theorems}\label{subsec-2-2}

In this subsection, we prove some technical theorems, which will be used in defining our model of OQW
and examining its properties.

In what follows, we always assume that $d\geq 2$ is a given positive integer and $\Lambda =\{-1,\, +1\}$.
We denote by $\Lambda^d$ the $d$-fold cartesian product of $\Lambda$,
and by $\mathcal{H}^{\otimes d}$ the  $d$-fold tensor product space of $\mathcal{H}$.
In addition, we assume that $\mathsf{K}\colon \mathcal{H}^{\otimes d}\rightarrow \mathcal{H}$ is a fixed unitary isomorphism.
Such a unitary isomorphism does exist because $\mathcal{H}$ is infinite-dimensional and separable.

To facilitate our discussions, we further write $\mathfrak{S}(\mathcal{H})$ for the space of all operators
of trace class on $\mathcal{H}$ with the trace norm and $\mathfrak{S}_+(\mathcal{H})$ for the cone of all positive elements of $\mathfrak{S}(\mathcal{H})$.
Similarly, we use symbol $\mathfrak{S}\big(\mathcal{H}^{\otimes d}\big)$ and $\mathfrak{S}_+\big(\mathcal{H}^{\otimes d}\big)$.

\begin{definition}\label{def-2-1}
For $n\geq 0$ and $\varepsilon=(\varepsilon_1, \varepsilon_2, \cdots, \varepsilon_d)\in \Lambda^d$, we define
\begin{equation}\label{eq-2-12}
  C_n^{(\varepsilon)} = \mathsf{K}\Big(\bigotimes_{j=1}^d B_n^{(\varepsilon_j)}\Big)\mathsf{K}^{-1},
\end{equation}
where $\mathsf{K}^{-1}$ is the inverse of the unitary isomorphism $\mathsf{K}\colon \mathcal{H}^{\otimes d}\rightarrow \mathcal{H}$,
and $B_n^{(\varepsilon_j)}$ is given by
\begin{equation}\label{eq-2-13}
  B_n^{(\varepsilon_j)}=
  \left\{
    \begin{array}{ll}
      L_n, & \hbox{$\varepsilon_j =-1$;} \\
      R_n, & \hbox{$\varepsilon_j =+1$}
    \end{array}
  \right.
\end{equation}
for $i=1$, $2$, $\cdots$, $d$.
\end{definition}

It can be shown that, for all $n\geq 0$, $\big\{C_n^{(\varepsilon)}\mid \varepsilon\in \Lambda^d\big\}$ are self-adjoint
operators on $\mathcal{H}$. And moreover, they admit the following useful properties:\ $C_n^{(\varepsilon)}C_n^{(\varepsilon')}=0$
for $\varepsilon$, $\varepsilon'\in \Lambda^d$ with $\varepsilon\neq \varepsilon'$; and their sum
$\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}$ is a unitary operator on $\mathcal{H}$ (see \cite{w-w} for details).

\begin{theorem}\label{thr-2-4}
Let $n\geq 0$. Then $\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}C_n^{(\varepsilon)}=I$, where $I$ denotes the identity operator on $\mathcal{H}$.
\end{theorem}

\begin{proof}
By the definition of $B_n^{-1}$ and $B_n^{(+1)}$ and Lemma~\ref{lem-2-3}, we have
\begin{equation*}
  \sum_{\varepsilon_j\in \Lambda}B_n^{(\varepsilon_j)}B_n^{(\varepsilon_j)}
  = B_n^{(-1)}B_n^{(-1)} + B_n^{(+1)}B_n^{(+1)}
  = L_n^2 + R_n^2
  = I
\end{equation*}
for $j=1$, $2$, $\cdots$, $d$, where $I$ denotes the identity operator on $\mathcal{H}$.
Making tensor products gives
\begin{equation*}
  \sum_{\varepsilon\in \Lambda^d}\Big(\bigotimes_{j=1}^d B_n^{(\varepsilon_j)}\Big)\Big(\bigotimes_{j=1}^d B_n^{(\varepsilon_j)}\Big)
  = \sum_{\varepsilon\in \Lambda^d}\Big(\bigotimes_{j=1}^d B_n^{(\varepsilon_j)}B_n^{(\varepsilon_j)}\Big)
  = \bigotimes_{j=1}^d\sum_{\varepsilon_j\in \Lambda}B_n^{(\varepsilon_j)}B_n^{(\varepsilon_j)}
  = \bigotimes_{j=1}^dI.
\end{equation*}
This, together with the definition of $C_n^{(\varepsilon)}$ as well as properties of the unitary isomorphism $\mathsf{K}$, yields
\begin{equation*}
  \sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}C_n^{(\varepsilon)}
  = \mathsf{K}\Big[\sum_{\varepsilon\in \Lambda^d}\Big(\bigotimes_{j=1}^d B_n^{(\varepsilon_j)}\Big)
    \Big(\bigotimes_{j=1}^d B_n^{(\varepsilon_j)}\Big)\Big]\mathsf{K}^{-1}
  = \mathsf{K}\Big[\bigotimes_{j=1}^dI\Big]\mathsf{K}^{-1}
  = I.
\end{equation*}
Here we note that $\bigotimes_{j=1}^dI$ is just the identity operator on $\mathcal{H}^{\otimes d}$.
\end{proof}

\begin{theorem}\label{thr-2-5}
For all $\varrho \in \mathfrak{S}_+(\mathcal{H})$ and $n\geq 0$, the sum operator
$\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}\varrho\, C_n^{(\varepsilon)}$ belongs to $\mathfrak{S}_+(\mathcal{H})$,
and moreover it holds true that
\begin{equation}\label{eq-2-14}
  \mathrm{Tr}\Big[\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}\varrho\, C_n^{(\varepsilon)}\Big]
  = \mathrm{Tr}\varrho.
\end{equation}
\end{theorem}

\begin{proof}
For each $\varepsilon \in \Lambda^d$, $C_n^{(\varepsilon)}\varrho\, C_n^{(\varepsilon)}$ is a positive
operator of trace class on $\mathcal{H}$ since $\varrho$ is such an operator and $C_n^{(\varepsilon)}$ is self-adjoint.
Thus $\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}\varrho\, C_n^{(\varepsilon)}$ is also a
positive operator of trace class on $\mathcal{H}$, namely it belongs to $\mathfrak{S}_+(\mathcal{H})$.
Now, by using Theorem~\ref{thr-2-4}, we find
\begin{equation*}
  \mathrm{Tr}\Big[\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}\varrho\, C_n^{(\varepsilon)}\Big]
  = \sum_{\varepsilon\in \Lambda^d} \mathrm{Tr}\big[\varrho\,C_n^{(\varepsilon)} C_n^{(\varepsilon)}\big]
  = \mathrm{Tr}\big[ \varrho \sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)} C_n^{(\varepsilon)}\big]
  =\mathrm{Tr}\varrho.
\end{equation*}
This completes the proof.
\end{proof}

\begin{definition}\label{def-2-2}
A $d$-dimensional nucleus $\omega$ on $\mathcal{H}$ is a mapping $\omega \colon \mathbb{Z}^d \rightarrow \mathfrak{S}_+(\mathcal{H})$
satisfying that
\begin{equation}\label{eq-2-16}
  \sum_{\mathrm{x}\in \mathbb{Z}^d}\mathrm{Tr}[\omega(\mathrm{x})]=1.
\end{equation}
The set of all $d$-dimensional nucleuses on $\mathcal{H}$ is denoted as $\mathscr{T}^{(d)}(\mathcal{H})$.
\end{definition}

It can be seen that, for each $d$-dimensional nucleus $\omega \in \mathscr{T}^{(d)}(\mathcal{H})$,
the corresponding function $\mathrm{x}\mapsto \mathrm{Tr}[\omega(\mathrm{x})]$ defines
a probability distribution on $\mathbb{Z}^d$.

\begin{theorem}\label{thr-2-6}
For each $n\geq 0$, there exists a mapping
$\mathfrak{J}_n^{(d)} \colon \mathscr{T}^{(d)}(\mathcal{H}) \rightarrow \mathscr{T}^{(d)}(\mathcal{H})$ such that
\begin{equation}\label{eq-2-17}
  \big[\mathfrak{J}_n^{(d)}\omega\big](\mathrm{x})
  = \sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}\omega(\mathrm{x}-\varepsilon)C_n^{(\varepsilon)},\quad \mathrm{x}\in \mathbb{Z}^d,\, \omega\in \mathscr{T}^{(d)}(\mathcal{H}),
\end{equation}
where $\sum_{\varepsilon\in \Lambda^d}$ means to sum over $\Lambda^d$.
\end{theorem}

\begin{proof}
Let $n\geq 0$.
For each $\omega\in \mathscr{T}^{(d)}(\mathcal{H})$, there is naturally a mapping $\omega'$ on $\mathbb{Z}^d$ associated with
$\omega$ in the following way
\begin{equation*}
  \omega'(\mathrm{x})=\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}\omega(\mathrm{x}-\varepsilon)C_n^{(\varepsilon)},\quad \mathrm{x}\in \mathbb{Z}^d.
\end{equation*}
We observe that $C_n^{(\varepsilon)}\omega(\mathrm{x}-\varepsilon)C_n^{(\varepsilon)}\in \mathfrak{S}_+(\mathcal{H})$
for all $\mathrm{x}\in \mathbb{Z}^d$ and all $\varepsilon\in \Lambda^d$, which implies that
$\omega'(\mathrm{x}) \in \mathfrak{S}_+(\mathcal{H})$ for all $\mathrm{x}\in \mathbb{Z}^d$,
hence $\omega'$ is a mapping from $\mathbb{Z}^d$ to $\mathfrak{S}_+(\mathcal{H})$.

Next we show that $\sum_{\mathrm{x}\in \mathbb{Z}^d}\mathrm{Tr}[\omega'(\mathrm{x})]=1$.
In fact, for each $\mathrm{x}\in \mathbb{Z}^d$, by Theorem~\ref{thr-2-5} we have
\begin{equation*}
  \sum_{\varepsilon\in \Lambda^d}\mathrm{Tr}\big[C_n^{(\varepsilon)}\omega(\mathrm{x})C_n^{(\varepsilon)}\big]
  = \mathrm{Tr}[\omega(\mathrm{x})].
\end{equation*}
Thus, in view of the fact that all the series involved have positive terms, we get
\begin{equation*}
  \sum_{\mathrm{x}\in \mathbb{Z}^d}\mathrm{Tr}[\omega'(\mathrm{x})]
  = \sum_{\mathrm{x}\in \mathbb{Z}^d}\sum_{\varepsilon\in \Lambda^d}
    \mathrm{Tr}\big[C_n^{(\varepsilon)}\omega(\mathrm{x}-\varepsilon)C_n^{(\varepsilon)}\big]
  = \sum_{\mathrm{x}\in \mathbb{Z}^d}\sum_{\varepsilon\in \Lambda^d}
    \mathrm{Tr}\big[C_n^{(\varepsilon)}\omega(\mathrm{x})C_n^{(\varepsilon)}\big]
  = \sum_{\mathrm{x}\in \mathbb{Z}^d}\mathrm{Tr}[\omega(\mathrm{x})],
\end{equation*}
which together with $\omega\in \mathscr{T}^{(d)}(\mathcal{H})$ implies that
$\sum_{\mathrm{x}\in \mathbb{Z}^d}\mathrm{Tr}[\omega'(\mathrm{x})]=1$. Now, according to Definition~\ref{def-2-2},
we know that $\omega'\in \mathscr{T}^{(d)}(\mathcal{H})$.
Finally, we define a mapping
$\mathfrak{J}_n^{(d)} \colon \mathscr{T}^{(d)}(\mathcal{H}) \rightarrow \mathscr{T}^{(d)}(\mathcal{H})$
as
\begin{equation*}
  \mathfrak{J}_n^{(d)}\omega = \omega',\quad \omega\in \mathscr{T}^{(d)}(\mathcal{H}).
\end{equation*}
Then $\mathfrak{J}_n^{(d)}$ is the desired.
\end{proof}

\subsection{Definition of walk}\label{subsec-2-3}

This subsection first offers the definition of our model of OQW and then examines its basic properties.

As mentioned above, we call a positive operator of trace class (on a Hilbert space)
a density operator if it has unit trace.
Recall that $d\geq 2$ is a given positive integer.
We denote by $l^2(\mathbb{Z}^d)$ the space of square summable complex-valued functions
on the $d$-dimensional integer lattice $\mathbb{Z}^d$. As a Hilbert space, $l^2(\mathbb{Z}^d)$ has
a countable orthonormal basis $\big\{\delta_{\mathrm{x}} \mid \mathrm{x}\in \mathbb{Z}^d\big\}$, which is known as
the canonical ONB of $l^2(\mathbb{Z}^d)$, where $\delta_{\mathrm{x}}$ is the function on $\mathbb{Z}^d$ given by
\begin{equation*}
  \delta_{\mathrm{x}}(\mathrm{z})=
  \left\{
    \begin{array}{ll}
      1, & \hbox{$\mathrm{z}=\mathrm{x}$, $\mathrm{z}\in \mathbb{Z}^d$;} \\
      0, & \hbox{$\mathrm{z}\neq \mathrm{x}$, $\mathrm{z}\in \mathbb{Z}^d$.}
    \end{array}
  \right.
\end{equation*}
By convention, we use $|\delta_{\mathrm{x}}\rangle\!\langle \delta_{\mathrm{x}}|$ to mean the Dirac operator associated with $\delta_{\mathrm{x}}$, which is a density operator on $l^2(\mathbb{Z}^d)$.

By the general theory of trace class operators on a Hilbert space \cite{simon}, one can easily come to the
next lemma, which provides a way to construct a density operator on
the tensor space $l^2(\mathbb{Z}^d)\otimes \mathcal{H}$ from the
canonical ONB of $l^2(\mathbb{Z}^d)$ and elements of $\mathscr{T}^{(d)}(\mathcal{H})$.

\begin{lemma}\label{lem-2-7}
Let $\omega \in \mathscr{T}^{(d)}(\mathcal{H})$. Then,  for each $\mathrm{x}\in \mathbb{Z}^d$, $|\delta_{\mathrm{x}}\rangle\!\langle\delta_{\mathrm{x}}|\otimes \omega(\mathrm{x})$
is a positive operator of trace class on $l^2(\mathbb{Z}^d)\otimes \mathcal{H}$. Moreover, the operator series
\begin{equation}\label{eq-2-17}
  \sum_{\mathrm{x}\in \mathbb{Z}^d}|\delta_{\mathrm{x}}\rangle\!\langle\delta_{\mathrm{x}}|\otimes \omega(\mathrm{x})
\end{equation}
is convergent in the trace operator norm and its sum operator is a density operator on $l^2(\mathbb{Z}^d)\otimes \mathcal{H}$.
\end{lemma}

With help of this lemma, we are now ready to introduce our model of OQW as follows.

\begin{definition}\label{def-2-3}
The $d$-dimensional open QBN walk is an open quantum walk on the $d$-dimensional integer lattice $\mathbb{Z}^d$ that admits the following features.
\begin{itemize}

\item Its states are represented by density operators on the tensor space $l^2(\mathbb{Z}^d)\otimes \mathcal{H}$.

\item Let $\widetilde{\omega^{(n)}}$ be the state of the walk at time $n\geq 0$. Then $\widetilde{\omega^{(n)}}$ takes the form
     \begin{equation}\label{eq-2-18}
     \widetilde{\omega^{(n)}} = \sum_{\mathrm{x} \in \mathbb{Z}^d}|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{x}}|\otimes \omega^{(n)}(\mathrm{x}),
     \end{equation}
  where $\omega^{(n)}\in \mathscr{T}^{(d)}(\mathcal{H})$, which is called the nucleus of the state $\widetilde{\omega^{(n)}}$.

  \item The time evolution of the walk is governed by equation
     \begin{equation}\label{eq-2-19}
      \omega^{(n+1)} = \mathfrak{J}_n^{(d)}\omega^{(n)},\quad n\geq 0,
      \end{equation}
 where $\omega^{(n+1)}$ and $\omega^{(n)}$ are the nucleuses of the states $\widetilde{\omega^{(n+1)}}$ and $\widetilde{\omega^{(n)}}$, respectively and $\mathfrak{J}_n^{(d)}$ is the mapping described in Theorem~\ref{thr-2-6}.
\end{itemize}
In that case, the function $\mathrm{x}\mapsto \mathrm{Tr}[\omega^{(n)}(\mathrm{x})]$ on $\mathbb{Z}^d$ is called
the probability distribution of the walk at time $n\geq 0$,
while the quantity $\mathrm{Tr}[\omega^{(n)}(\mathrm{x})]$ is the probability to find out the walker
at position $\mathrm{x}\in \mathbb{Z}^d$ and time $n\geq 0$.
By convention, the state $\widetilde{\omega^{(0)}}$ of the walk at time $n=0$ is usually known as its initial state.
\end{definition}

Physically, $l^2(\mathbb{Z}^d)$ describes the position of the walk, while $\mathcal{H}$ describes the
internal degrees of freedom of the walk. As shown above, $\mathcal{H}$ is infinitely dimensional,
which means that the $d$-dimensional open QBN walk has infinitely many internal degrees of freedom.

\begin{remark}
It is not hard to see that the $d$-dimensional open QBN walk is completely determined by the nucleus sequence of its states.
Let $\big(\omega^{(n)}\big)_{n\geq 0}$ be the nucleus sequence of states of the $d$-dimensional open QBN walk.
Then, by Theorem~\ref{thr-2-6}, one has the following evolution relations
\begin{equation}\label{eq-2-20}
  \omega^{(n+1)}(\mathrm{x}) = \sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}\omega^{(n)}(\mathrm{x}-\varepsilon)C_n^{(\varepsilon)},
  \quad \mathrm{x}\in \mathbb{Z}^d,\, n\geq 0,
\end{equation}
which actually give an alternative description of the evolution of the $d$-dimensional open QBN walk.
\end{remark}

\subsection{Quantum channel representation}\label{subsec-2-4}

In this subsection, we mainly offer a quantum channel representation of the $d$-dimensional open QBN walk.

For $n\geq 0$ and $\mathrm{x}$, $\mathrm{y}\in \mathbb{Z}^d$, we define an operator $M^{(n)}(\mathrm{x},\mathrm{y})$ on the tensor space $l^2(\mathbb{Z}^d)\otimes \mathcal{H}$ as
\begin{equation}\label{eq-2-21}
  M^{(n)}_{\mathrm{x},\mathrm{y}}=
  \left\{
    \begin{array}{ll}
      |\delta_{\mathrm{x}}\rangle\!\langle \delta_{\mathrm{y}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}, & \hbox{$\mathrm{x}-\mathrm{y} \in \Lambda^d$;} \\
      0, & \hbox{$\mathrm{x}-\mathrm{y} \notin \Lambda^d$.}
    \end{array}
  \right.
\end{equation}
Clearly, for each $n \geq 0$, the operator family
$\big\{M^{(n)}_{\mathrm{x},\mathrm{y}} \mid \mathrm{x},\, \mathrm{y} \in \mathbb{Z}^d\big\}$
is infinite and countable.

\begin{theorem}\label{thr-2-8}
For each $n\geq 0$, the countable family
$\big\{M^{(n)}_{\mathrm{x},\mathrm{y}} \mid \mathrm{x},\, \mathrm{y} \in \mathbb{Z}^d\big\}$ of  operators satisfies
the following relation
\begin{equation}\label{eq-2-22}
  \sum_{\mathrm{x},\mathrm{y} \in \mathbb{Z}^d}{M^{(n)}_{\mathrm{x},\mathrm{y}}}^*M^{(n)}_{\mathrm{x},\mathrm{y}}=I,
\end{equation}
where ${M^{(n)}_{\mathrm{x},\mathrm{y}}}^*$ means the adjoint of $M^{(n)}_{\mathrm{x},\mathrm{y}}$, $I$ denotes the identity operator on $l^2(\mathbb{Z}^d)\otimes \mathcal{H}$
and the operator series converges strongly.
\end{theorem}

\begin{proof}
First, for each $\mathrm{y}\in \mathbb{Z}^d$, we find that there are at most finitely many $\mathrm{x}\in \mathbb{Z}^d$
such that $M^{(n)}_{\mathrm{x},\mathrm{y}}\neq 0$,
which implies that the series
$\sum_{\mathrm{x} \in \mathbb{Z}^d}{M^{(n)}_{\mathrm{x},\mathrm{y}}}^*M^{(n)}_{\mathrm{x},\mathrm{y}}$
is actually a sum of finitely many summands. On the other hand, for each $\mathrm{y}\in \mathbb{Z}^d$,
by a direct calculation we have
\begin{equation*}
\begin{split}
\sum_{\mathrm{x} \in \mathbb{Z}^d}{M^{(n)}_{\mathrm{x},\mathrm{y}}}^*M^{(n)}_{\mathrm{x},\mathrm{y}}
   &= \sum_{\mathrm{x}-\mathrm{y} \in \Lambda^d}
    \big(|\delta_{\mathrm{x}}\rangle\!\langle \delta_{\mathrm{y}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}\big)^*
    \big(|\delta_{\mathrm{x}}\rangle\!\langle \delta_{\mathrm{y}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}\big)\\
   &= \sum_{\mathrm{x}-\mathrm{y} \in \Lambda^d}
    \big(|\delta_{\mathrm{y}}\rangle\!\langle \delta_{\mathrm{x}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}\big)
    \big(|\delta_{\mathrm{x}}\rangle\!\langle \delta_{\mathrm{y}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}\big)\\
   &= \sum_{\mathrm{x}-\mathrm{y} \in \Lambda^d}|\delta_{\mathrm{y}}\rangle\!\langle \delta_{\mathrm{y}}|
      \otimes \big( C_n^{(\mathrm{x}-\mathrm{y})} C_n^{(\mathrm{x}-\mathrm{y})}\big)\\
   &= |\delta_{\mathrm{y}}\rangle\!\langle \delta_{\mathrm{y}}|\otimes \sum_{\mathrm{x}-\mathrm{y} \in \Lambda^d}
        C_n^{(\mathrm{x}-\mathrm{y})} C_n^{(\mathrm{x}-\mathrm{y})}\\
   &= |\delta_{\mathrm{y}}\rangle\!\langle \delta_{\mathrm{y}}|\otimes I_{\mathcal{H}}.
\end{split}
\end{equation*}
Therefore, using the fact that the series
$\sum_{\mathrm{y} \in \mathbb{Z}^d}|\delta_{\mathrm{y}}\rangle\!\langle \delta_{\mathrm{y}}|$
strongly converges to $I_{l^2(\mathbb{Z}^d)}$, we finally come to
\begin{equation*}
  \sum_{\mathrm{x},\mathrm{y} \in \mathbb{Z}^d}{M^{(n)}_{\mathrm{x},\mathrm{y}}}^*M^{(n)}_{\mathrm{x},\mathrm{y}}
  = \sum_{\mathrm{y} \in \mathbb{Z}^d}\sum_{\mathrm{x} \in \mathbb{Z}^d}
    {M^{(n)}_{\mathrm{x},\mathrm{y}}}^*M^{(n)}_{\mathrm{x},\mathrm{y}}
 = \sum_{\mathrm{y} \in \mathbb{Z}^d}|\delta_{\mathrm{y}}\rangle\!\langle \delta_{\mathrm{y}}|\otimes I_{\mathcal{H}}
 = I_{l^2(\mathbb{Z}^d)}\otimes I_{\mathcal{H}}
 = I.
\end{equation*}
Here, $I_{l^2(\mathbb{Z}^d)}$ and $I_{\mathcal{H}}$ mean the identity operators on $l^2(\mathbb{Z}^d)$
and $\mathcal{H}$, respectively.
\end{proof}

As above, we denote by $\mathfrak{S}\big(l^2(\mathbb{Z}^d)\otimes \mathcal{H}\big)$
the space of trace class operators on $l^2(\mathbb{Z}^d)\otimes \mathcal{H}$.
Then, by the general theory of trace class operators \cite{simon}, for each $n\geq 0$ and
each $\widetilde{\omega} \in \mathfrak{S}\big(l^2(\mathbb{Z}^d)\otimes \mathcal{H}\big)$,
the operator series
\begin{equation*}
  \sum_{\mathrm{x},\mathrm{y} \in \mathbb{Z}^d} M^{(n)}_{\mathrm{x},\mathrm{y}}\,\widetilde{\omega}\, {M^{(n)}_{\mathrm{x},\mathrm{y}}}^*
\end{equation*}
converges in the trace norm, and moreover its sum still belongs to
$\mathfrak{S}\big(l^2(\mathbb{Z}^d)\otimes \mathcal{H}\big)$.

\begin{definition}\label{def-2-4}
For $n\geq 0$, we define a mapping
$\mathsf{M}^{(n)}\colon \mathfrak{S}\big(l^2(\mathbb{Z}^d)\otimes \mathcal{H}\big) \rightarrow \mathfrak{S}\big(l^2(\mathbb{Z}^d)\otimes \mathcal{H}\big)$ as
\begin{equation}\label{eq}
  \mathsf{M}^{(n)}(\widetilde{\omega})
= \sum_{\mathrm{x},\mathrm{y} \in \mathbb{Z}^d} M^{(n)}_{\mathrm{x},\mathrm{y}}\, \widetilde{\omega}\, {M^{(n)}_{\mathrm{x},\mathrm{y}}}^*,\quad
\widetilde{\omega} \in \mathfrak{S}\big(l^2(\mathbb{Z}^d)\otimes \mathcal{H}\big),
\end{equation}
where $\sum_{\mathrm{x},\mathrm{y} \in \mathbb{Z}^d}$ means to sum for all $\mathrm{x}$, $\mathrm{y} \in \mathbb{Z}^d$.
\end{definition}

From a point of quantum information theory \cite{petz}, the mapping $\mathsf{M}^{(n)}$ is actually a quantum channel of Krauss type.
The next result then gives a quantum channel representation of the $d$-dimensional open QBN walk.

\begin{theorem}\label{thr-2-9}
Let $\left(\widetilde{\omega^{(n)}}\right)_{n\geq 0}$ the state sequence of the $d$-dimensional open QBN walk. Then it satisfies the following evolution equation
\begin{equation}\label{eq-2-24}
  \widetilde{\omega^{(n+1)}} = \mathsf{M}^{(n)}\left(\widetilde{\omega^{(n)}}\right),\quad n\geq 0.
\end{equation}
\end{theorem}

\begin{proof}
Let $n\geq 0$. By Definition~\ref{def-2-3}, $\widetilde{\omega^{(n)}}$ has a representation of the following form
\begin{equation*}
  \widetilde{\omega^{(n)}}
= \sum_{\mathrm{z} \in \mathbb{Z}^d}|\delta_{\mathrm{z}}\rangle\langle\delta_{\mathrm{z}}|\otimes \omega^{(n)}(\mathrm{z}),
\end{equation*}
where the series converges strongly. For $\mathrm{x}$, $\mathrm{y}\in \mathbb{Z}^d$
with $\mathrm{x}-\mathrm{y}\in \Lambda^d$, in view of the fact
\begin{equation*}
  |\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{y}}|\,|\delta_{\mathrm{z}}\rangle\langle\delta_{\mathrm{z}}|
  =\left\{
     \begin{array}{ll}
       |\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{y}}|, & \hbox{$\mathrm{z}=\mathrm{y}$;} \\
       0, & \hbox{$\mathrm{z}=\mathrm{y}$, $\mathrm{z}\in \mathbb{Z}^d$,}
     \end{array}
   \right.
\end{equation*}
we have
\begin{equation*}
\begin{split}
  M^{(n)}_{\mathrm{x},\mathrm{y}}\, \widetilde{\omega^{(n)}}\, {M^{(n)}_{\mathrm{x},\mathrm{y}}}^*
   &= \big[|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{y}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}\big]
      \Big[\sum_{\mathrm{z} \in \mathbb{Z}^d}|\delta_{\mathrm{z}}\rangle\langle\delta_{\mathrm{z}}|
      \otimes \omega^{(n)}(\mathrm{z})\Big]
      \big[|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{y}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}\big]^*\\
  &= \big[|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{y}}|
          \otimes \big(C_n^{(\mathrm{x}-\mathrm{y})}\omega^{(n)}(\mathrm{y})\big)\big]
      \big[|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{y}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}\big]^*\\
  &= \big[|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{y}}|
          \otimes \big(C_n^{(\mathrm{x}-\mathrm{y})}\omega^{(n)}(\mathrm{y})\big)\big]
      \big[|\delta_{\mathrm{y}}\rangle\langle\delta_{\mathrm{x}}|\otimes C_n^{(\mathrm{x}-\mathrm{y})}\big]\\
  &= |\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{x}}| \otimes
      \big(C_n^{(\mathrm{x}-\mathrm{y})}\omega^{(n)}(\mathrm{y})C_n^{(\mathrm{x}-\mathrm{y})}\big).
\end{split}
\end{equation*}
For $\mathrm{x}$, $\mathrm{y}\in \mathbb{Z}^d$ with $\mathrm{x}-\mathrm{y}\in \Lambda^d$,
in view of $M^{(n)}_{\mathrm{x},\mathrm{y}}=0$, we simply have
$M^{(n)}_{\mathrm{x},\mathrm{y}}\, \widetilde{\omega^{(n)}}\, {M^{(n)}_{\mathrm{x},\mathrm{y}}}^*=0$.
Thus, for each $\mathrm{y}\in \mathbb{Z}^d$, as a sum actually with a finite number of summands,
\begin{equation*}
\begin{split}
  \sum_{\mathrm{x}\in \mathbb{Z}^d} M^{(n)}_{\mathrm{x},\mathrm{y}}\, \widetilde{\omega^{(n)}}\,
       {M^{(n)}_{\mathrm{x},\mathrm{y}}}^*
  &= \sum_{\mathrm{x}-\mathrm{y}\in \Lambda^d} M^{(n)}_{\mathrm{x},\mathrm{y}}\, \widetilde{\omega^{(n)}}\,
       {M^{(n)}_{\mathrm{x},\mathrm{y}}}^*\\
  &= \sum_{\mathrm{x}-\mathrm{y}\in \Lambda^d}|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{x}}| \otimes
      \big(C_n^{(\mathrm{x}-\mathrm{y})}\omega^{(n)}(\mathrm{y})C_n^{(\mathrm{x}-\mathrm{y})}\big)\\
  & = \sum_{\varepsilon\in \Lambda^d}|\delta_{\mathrm{y}+\varepsilon}\rangle\langle\delta_{\mathrm{y}+\varepsilon}| \otimes
      \big(C_n^{(\varepsilon)}\omega^{(n)}(\mathrm{y})C_n^{(\varepsilon)}\big).
\end{split}
\end{equation*}
Therefore
\begin{equation*}
\begin{split}
\mathsf{M}^{(n)}\left(\widetilde{\omega^{(n)}}\right)
& = \sum_{\mathrm{y} \in \mathbb{Z}^d} \sum_{\mathrm{x} \in \mathbb{Z}^d}
     M^{(n)}_{\mathrm{x},\mathrm{y}}\,\widetilde{\omega^{(n)}}\, {M^{(n)}_{\mathrm{x},\mathrm{y}}}^*\\
& = \sum_{\mathrm{y} \in \mathbb{Z}^d}
    \sum_{\varepsilon\in \Lambda^d}|\delta_{\mathrm{y}+\varepsilon}\rangle\langle\delta_{\mathrm{y}+\varepsilon}|
   \otimes \big(C_n^{(\varepsilon)}\omega^{(n)}(\mathrm{y})C_n^{(\varepsilon)}\big)\\
& = \sum_{\mathrm{x} \in \mathbb{Z}^d}|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{x}}|\otimes
    \sum_{\varepsilon\in \Lambda^d}
    C_n^{(\varepsilon)}\omega^{(n)}(\mathrm{x}-\varepsilon)C_n^{(\varepsilon)}\\
& = \sum_{\mathrm{x} \in \mathbb{Z}^d}|\delta_{\mathrm{x}}\rangle\langle\delta_{\mathrm{x}}|\otimes
    \omega^{(n+1)}(\mathrm{x})\\
& = \widetilde{\omega^{(n+1)}}.
\end{split}
\end{equation*}
Here we make use of the strong convergence of the involved series.
\end{proof}

\section{Probability distribution of walk}\label{sec-3}

In the present section, we consider the $d$-dimensional open QBN walk from a perspective
of probability distribution. We first show that the $d$-dimensional open QBN walk admits the
``separability-preserving'' property, and then, based on this property, we calculate explicitly
the limit probability distribution of the walk for a wide range of choices of its initial state.

\subsection{Separability-preserving property}\label{subsec-3-1}

Let $\mathscr{T}(\mathcal{H})$ be the $1$-dimensional counterpart of the $d$-dimensional nucleus set $\mathscr{T}^{(d)}(\mathcal{H})$, namely
\begin{equation}\label{eq-3-1}
\mathscr{T}(\mathcal{H})=\Big\{ \rho\colon \mathbb{Z} \rightarrow \mathfrak{S}_+(\mathcal{H})\Bigm| \sum_{x=-\infty}^{\infty}\mathrm{Tr}[\rho(x)]=1\Big\}.
\end{equation}
Elements of $\mathscr{T}(\mathcal{H})$ are called $1$-dimensional nucleuses on $\mathcal{H}$.

\begin{lemma}\label{lem-3-1}\cite{w-w-r-t}
For each $n\geq 0$, there exists a mapping $\mathfrak{J}_n \colon \mathscr{T}(\mathcal{H}) \rightarrow \mathscr{T}(\mathcal{H})$ such that
\begin{equation}\label{eq-3-2}
  [\mathfrak{J}_n\rho](x) =  L_n\rho(x+1)L_n + R_n\rho(x-1)R_n,\quad x\in \mathbb{Z},\, \rho\in \mathscr{T}(\mathcal{H}).
\end{equation}
\end{lemma}

By this Lemma, we find that $\left(\prod_{k=0}^n \mathfrak{J}_k\right)\rho \in \mathscr{T}(\mathcal{H})$ for all $n\geq 0$ whenever $\rho \in \mathscr{T}(\mathcal{H})$,
where $\prod_{k=0}^n \mathfrak{J}_k$ means the composition of mappings $\mathfrak{J}_0$, $\mathfrak{J}_1$, $\cdots$, $\mathfrak{J}_n$.

\begin{theorem}\label{thr-3-2}
Let $\rho_1$, $\rho_2$, $\cdots$, $\rho_d\in \mathscr{T}(\mathcal{H})$ be $1$-dimensional nucleuses on $\mathcal{H}$. Define
\begin{equation}\label{eq}
  \omega(\mathrm{x}) = \mathsf{K}\Big(\bigotimes_{j=1}^d \rho_j(x_j) \Big)\mathsf{K}^{-1},\quad \mathrm{x}=(x_1, x_2, \cdots, x_d)\in \mathbb{Z}^d.
\end{equation}
Then $\omega \in \mathscr{T}^{(d)}(\mathcal{H})$, namely $\omega$ is a $d$-dimensional nucleus on $\mathcal{H}$.
\end{theorem}

\begin{proof}
\begin{equation*}
\sum_{\mathrm{x}\in \mathbb{Z}^d}\mathrm{Tr}[\omega(\mathrm{x})]
= \sum_{\mathrm{x}\in \mathbb{Z}^d}\mathrm{Tr}\Big[\bigotimes_{j=1}^d \rho_j(x_j) \Big]
= \sum_{\mathrm{x}\in \mathbb{Z}^d} \prod_{j=1}^d\mathrm{Tr} [\rho_j(x_j)]
= \prod_{j=1}^d\sum_{x_j\in \mathbb{Z}}\mathrm{Tr} [\rho_j(x_j)]
= \prod_{j=1}^d 1 =1.
\end{equation*}
\end{proof}

\begin{definition}\label{def-3-1}
A $d$-dimensional nucleus $\omega \in \mathscr{T}^{(d)}(\mathcal{H})$ is said to
 to be separable if there exist $1$-dimensional nucleuses
$\rho_1$, $\rho_2$, $\cdots$, $\rho_d\in \mathscr{T}(\mathcal{H})$ such that
\begin{equation}\label{eq}
  \omega(\mathrm{x}) = \mathsf{K}\Big(\bigotimes_{j=1}^d \rho_j(x_j) \Big)\mathsf{K}^{-1},\quad \mathrm{x}=(x_1, x_2, \cdots, x_d)\in \mathbb{Z}^d.
\end{equation}
A state $\widetilde{\omega^{(n)}}$ of the $d$-dimensional open QBN walk is said to be separable
if its nucleus $\omega^{(n)}$ is separable.
\end{definition}

The next theorem shows that all the states of the $d$-dimensional open QBN walk are separable provided
its initial state is separable. In other words, the $d$-dimensional open QBN walk
has the ``separability-preserving'' property.

\begin{theorem}\label{thr-3-3}
Let $\big(\omega^{(n)}\big)_{n\geq 0}$ be the nucleus sequence of the states of the $d$-dimensional open QBN walk. Suppose that
\begin{equation}\label{eq-3-5}
  \omega^{(0)}(\mathrm{x}) = \mathsf{K}\Big(\bigotimes_{j=1}^d \rho_j^{(0)}(x_j) \Big)\mathsf{K}^{-1},\quad \mathrm{x}=(x_1, x_2, \cdots, x_d)\in \mathbb{Z}^d,
\end{equation}
where $\rho_1^{(0)}$, $\rho_2^{(0)}$, $\cdots$, $\rho_d^{(0)}\in \mathscr{T}(\mathcal{H})$. Then, for all $n\geq 1$, $\omega^{(n)}$ has a representation of the following form
\begin{equation}\label{eq-3-6}
  \omega^{(n)}(\mathrm{x}) = \mathsf{K}\Big(\bigotimes_{j=1}^d \rho_j^{(n)}(x_j) \Big)\mathsf{K}^{-1},\quad \mathrm{x}=(x_1, x_2, \cdots, x_d)\in \mathbb{Z}^d,
\end{equation}
where
\begin{equation}\label{eq-3-7}
\rho_j^{(n)} = \Big(\prod_{k=0}^{n-1}\mathfrak{J}_k\Big)\rho_j^{(0)}
\end{equation}
for $j=1$, $2$, $\cdots$, $d$.
\end{theorem}

\begin{proof}
According to Lemma~\ref{lem-3-1}, $\rho_j^{(n)} \in \mathscr{T}(\mathcal{H})$ for each $j$ with $1\leq j \leq d$
and each $n\geq 0$. Thus, by Theorem~\ref{thr-3-2}, there exists a sequence $\big(\omega'^{(n)}\big)_{n\geq 0}$
in $\mathscr{T}^{(d)}(\mathcal{H})$ such that
\begin{equation}\label{eq-3-8}
  \omega'^{(n)}(\mathrm{x}) = \mathsf{K}\Big(\bigotimes_{j=1}^d \rho_j^{(n)}(x_j) \Big)\mathsf{K}^{-1},\quad
  \mathrm{x}=(x_1, x_2, \cdots, x_d)\in \mathbb{Z}^d,\ \ n\geq 0.
\end{equation}
In particular, we have
\begin{equation*}
  \omega'^{(0)}(\mathrm{x}) = \mathsf{K}\Big(\bigotimes_{j=1}^d \rho_j^{(0)}(x_j) \Big)\mathsf{K}^{-1},\quad
  \mathrm{x}=(x_1, x_2, \cdots, x_d)\in \mathbb{Z}^d,
\end{equation*}
which, together with the assumption given in (\ref{eq-3-5}), implies that $\omega^{(0)}=\omega'^{(0)}$.

On the other hand, for $n\geq 1$, by (\ref{eq-3-7}) we have $\rho_j^{(n)}= \mathfrak{J}_{n-1}\rho_j^{(n-1)}$,
$1\leq j\leq d$,
which together with Lemma~\ref{lem-3-1} implies that
\begin{equation*}
  \rho_j^{(n)}(x_j)
  = \sum_{\varepsilon_j\in \Lambda}B_{n-1}^{(\varepsilon_j)}\rho_j^{(n-1)}(x_j-\varepsilon_j)B_{n-1}^{(\varepsilon_j)},\quad
  x_j \in \mathbb{Z},\ \ 1\leq j \leq d.
\end{equation*}
Here $B_{n-1}^{(-1)}=L_{n-1}$ and $B_{n-1}^{(+1)}=R_{n-1}$ as indicated in Definition~\ref{def-2-1}.
Taking tensor product gives
\begin{equation*}
 \bigotimes_{j=1}^d \rho_j^{(n)}(x_j)
  = \sum_{\varepsilon\in \Lambda^d}
     \Big(\bigotimes_{j=1}^dB_{n-1}^{(\varepsilon_j)}\Big)
     \Big(\bigotimes_{j=1}^d\rho_j^{(n-1)}(x_j-\varepsilon_j)\Big)
     \Big(\bigotimes_{j=1}^dB_{n-1}^{(\varepsilon_j)}\Big),
\end{equation*}
$\mathrm{x}=(x_1, x_2, \cdots, x_d) \in \mathbb{Z}^d$,\ $n\geq 1$,
where $\varepsilon=(\varepsilon_1, \varepsilon_2, \cdots, \varepsilon_d)$.
This, together with (\ref{eq-3-8}) and Definition~\ref{def-2-1}, yields
\begin{equation*}
 \omega'^{(n)}(\mathrm{x})
  = \sum_{\varepsilon\in \Lambda^d}
     C_{n-1}^{(\varepsilon)}
     \omega'^{(n-1)}(\mathrm{x}-\varepsilon)
     C_{n-1}^{(\varepsilon)},\quad \mathrm{x}=(x_1, x_2, \cdots, x_d) \in \mathbb{Z}^d,\ n\geq 1,
\end{equation*}
namely
\begin{equation*}
 \omega'^{(n)}
  = \mathfrak{J}_{n-1}^{(d)}\omega'^{(n-1)},\quad n\geq 1,
\end{equation*}
which together with (\ref{eq-2-19}) and $\omega^{(0)}=\omega'^{(0)}$ implies that $\omega^{(n)}=\omega'^{(n)}$ for all
$n\geq 0$, which together with (\ref{eq-3-8}) gives (\ref{eq-3-6}).
\end{proof}

As an immediate consequence of the previous theorem, we have the following corollary,
which gives a formula for calculating the probability distributions of the $d$-dimensional open QBN walk.

\begin{corollary}\label{coro-3-4}
Let the nucleus $\omega^{(0)}$ of the initial state of the $d$-dimensional open QBN walk take the following form
\begin{equation}\label{eq-3-9}
  \omega^{(0)}(\mathrm{x}) = \mathsf{K}\Big(\bigotimes_{j=1}^d \rho_j^{(0)}(x_j) \Big)\mathsf{K}^{-1},\quad \mathrm{x}=(x_1, x_2, \cdots, x_d)\in \mathbb{Z}^d,
\end{equation}
where $\rho_1^{(0)}$, $\rho_2^{(0)}$, $\cdots$, $\rho_d^{(0)}\in \mathscr{T}(\mathcal{H})$. Then, at time $n\geq 1$, the walk has a probability distribution of the following form
\begin{equation}\label{eq-3-10}
  \mathrm{Tr}\big[\omega^{(n)}(\mathrm{x})\big] = \prod_{j=1}^d \mathrm{Tr}\big[\rho_j^{(n)}(x_j)\big],\quad \mathrm{x}=(x_1, x_2,\cdots, x_d)\in \mathbb{Z}^d,
\end{equation}
where
\begin{equation}\label{eq-3-11}
\rho_j^{(n)} = \Big(\prod_{k=0}^{n-1}\mathfrak{J}_k\Big)\rho_j^{(0)}
\end{equation}
for $j=1$, $2$, $\cdots$, $d$.
\end{corollary}

\subsection{Limit probability distribution}\label{subsec-3-2}

Let $\rho$ be a $1$-dimensional nucleus on $\mathcal{H}$, namely $\rho\in \mathscr{T}(\mathcal{H})$.
A sequence $\big(\rho^{(n)}\big)_{n\geq 0}$ of $1$-dimensional nucleuses on $\mathcal{H}$ is said to be generated by $\rho$
and $\big(\mathfrak{J}_n\big)_{n\geq 0}$ if $\rho^{(0)}=\rho$ and
\begin{equation*}
\rho^{(n+1)} = \mathfrak{J}_n\rho^{(n)},\quad n\geq 0.
\end{equation*}
We note that if a sequence $\big(\rho^{(n)}\big)_{n\geq 0}$ is generated by $\rho$
and $\big(\mathfrak{J}_n\big)_{n\geq 0}$, then $\rho^{(0)}=\rho$ and
\begin{equation*}
\rho^{(n)} = \Big(\prod_{k=0}^{n-1}\mathfrak{J}_k\Big)\rho^{(0)},\quad n\geq 1,
\end{equation*}
where $\prod_{k=0}^{n-1}\mathfrak{J}_k$ means the composition of mappings $\{\,\mathfrak{J}_k \mid 0\leq k \leq n-1\,\}$.

\begin{definition}\label{def-3-2}
A $1$-dimensional nucleus $\rho$ on $\mathcal{H}$ is said to be regular if
the sequence $\big(\rho^{(n)}\big)_{n\geq 0}$ generated by $\rho$
and $\big(\mathfrak{J}_n\big)_{n\geq 0}$ satisfies that
\begin{equation*}
  \lim_{n\to \infty}\sum_{x\in \mathbb{Z}}\mathrm{e}^{\frac{\mathrm{i}tx}{\sqrt{n}}}\mathrm{Tr}\big[\rho^{(n)}(x)\big]
  = \mathrm{e}^{-\frac{t^2}{2}},\quad t\in \mathbb{R}.
\end{equation*}
\end{definition}

The next example shows that there exist infinitely many $1$-dimensional nucleuses on $\mathcal{H}$ that are regular.

\begin{example}\label{exam-3-1}
Let $\sigma\in \Gamma$ and $Z_{\sigma}$ the corresponding basis vector of the canonical ONB of $\mathcal{H}$.
Define
\begin{equation}\label{eq-3-12}
  \rho_{\sigma}(x)=\left\{
            \begin{array}{ll}
              |Z_{\sigma}\rangle\!\langle Z_{\sigma}|, & \hbox{$x=0$;} \\
              0, & \hbox{$x\neq 0$, $x\in \mathbb{Z}$,}
            \end{array}
          \right.
\end{equation}
where $|Z_{\sigma}\rangle\!\langle Z_{\sigma}|$ is the Dirac operator associated with the basis vector $Z_{\sigma}$.
Then $\rho_{\sigma}$ is a regular $1$-dimensional nucleus on $\mathcal{H}$.
\end{example}

\begin{proof}
Clearly $\rho_{\sigma}$ is a $1$-dimensional nucleus on $\mathcal{H}$. Next we show that it is also regular.
To this end, we consider the space $l^2(\mathbb{Z},\mathcal{H})$ of square summable $\mathcal{H}$-valued functions defined on $\mathbb{Z}$,
which is endowed the usual inner product and norm. It can be verified (see \cite{w-r-t} and references therein) that for each $n\geq 0$,
there exists a unitary operator $\mathcal{U}_n$ on $l^2(\mathbb{Z}, \mathcal{H})$ such that
\begin{equation}\label{eq-3-13}
  (\mathcal{U}_n\Phi)(x) = R_n\Phi(x-1) + L_n\Phi(x+1),\quad x\in \mathbb{Z},\; \Phi\in l^2(\mathbb{Z}, \mathcal{H}).
\end{equation}
Now define $\Phi_n= \big(\prod_{k=0}^{n-1}\mathcal{U}_k\big)\Phi_0$, $n\geq 1$, where $\Phi_0\in l^2(\mathbb{Z}, \mathcal{H})$
is taken as
\begin{equation*}
  \Phi_0(x)=\left\{
              \begin{array}{ll}
                Z_{\sigma}, & \hbox{$x=0$;} \\
                0, & \hbox{$x\neq 0$, $x\in \mathbb{Z}$.}
              \end{array}
            \right.
\end{equation*}
Then, by a result recently proven by Wang \textit{et al} (see \cite{w-r-t} for details), we have
\begin{equation}\label{eq-3-14}
\|\Phi_n(x)\|^2=
 \left\{
   \begin{array}{ll}
     \frac{1}{2^n}\binom{n}{j}, & \hbox{$x=n-2j$, $0\leq j \leq n$;} \\
     0, & \hbox{otherwise,}
   \end{array}
 \right.
\end{equation}
for all $n\geq 1$. On the other hand, let $\big(\rho^{(n)}\big)_{n\geq 0}$ be the $1$-dimensional nucleus sequence on
$\mathcal{H}$ generated by $\rho_{\sigma}$ and $\big(\mathfrak{J}_n\big)_{n\geq 0}$.
Then, by a careful check, we find that
\begin{equation*}
  \rho^{(0)}(x) = \rho_{\sigma}(x)=|\Phi_0(x)\rangle\langle \Phi_0(x)|,\quad x\in \mathbb{Z}.
\end{equation*}
This, together with Theorem 4.2 of \cite{w-w-r-t}, as well as (\ref{eq-3-14}), implies that
\begin{equation}\label{eq-4-15}
\mathrm{Tr}[\rho^{(n)}(x)]=
 \left\{
   \begin{array}{ll}
     \frac{1}{2^n}\binom{n}{j}, & \hbox{$x=n-2j$, $0\leq j \leq n$;} \\
     0, & \hbox{otherwise.}
   \end{array}
 \right.
\end{equation}
Consequently, by a careful calculation, we finally come to
\begin{equation*}
  \lim_{n\to \infty}\sum_{x\in \mathbb{Z}}\mathrm{e}^{\frac{\mathrm{i}tx}{\sqrt{n}}}\mathrm{Tr}\big[\rho^{(n)}(x)\big]
  = \lim_{n\to \infty}\cos^n\frac{t}{\sqrt{n}}
  =\mathrm{e}^{-\frac{t^2}{2}},\quad t\in \mathbb{R},
\end{equation*}
which means that $\rho_{\sigma}$ is regular.
\end{proof}

The next theorem shows that, for a wide range of choices of its initial state, the $d$-dimensional open QBN walk has
a limit probability distribution of $d$-dimensional Gauss type.

\begin{theorem}\label{thr-3-5}
Let $\big(\widetilde{\omega^{(n)}}\big)_{n\geq 0}$ be the state sequence of the $d$-dimensional open QBN walk
and $\omega^{(n)}$ the nucleus of $\widetilde{\omega^{(n)}}$, $n\geq 0$. Suppose that
the nucleus $\omega^{(0)}$ of the initial state $\widetilde{\omega^{(0)}}$ takes the following form
\begin{equation}\label{eq-3-16}
  \omega^{(0)}(\mathrm{x}) = \mathsf{K}\Big(\bigotimes_{j=1}^d \rho_j^{(0)}(x_j) \Big)\mathsf{K}^{-1},\quad \mathrm{x}=(x_1, x_2, \cdots, x_d)\in \mathbb{Z}^d,
\end{equation}
where $\big\{\,\rho_j^{(0)} \mid 1\leq j \leq d \,\big\}$ are regular $1$-dimensional nucleuses on $\mathcal{H}$.
For $n\geq 0$, let $X_n$ be a $d$-dimensional random vector with probability distribution
\begin{equation}\label{eq-3-17}
  P\{X_n = \mathrm{x}\} = \mathrm{Tr}[\omega^{(n)}(\mathrm{x})],\quad \mathrm{x}\in \mathbb{Z}^d.
\end{equation}
Then
\begin{equation*}
\frac{X_n}{\sqrt{n}}\Longrightarrow N(\mathbf{0},I_{d\times d}),
\end{equation*}
namely $\frac{X_n}{\sqrt{n}}$ converges in law to
the $d$-dimensional standard Gauss distribution as $n\rightarrow \infty$.
\end{theorem}

\begin{proof}
Let $n\geq 1$.
Consider the characteristic function $C_{\frac{X_n}{\sqrt{n}}}(\mathbf{t})$ of the random vector $\frac{X_n}{\sqrt{n}}$.
By definition, we have
\begin{equation}\label{eq-3-18}
  C_{\frac{X_n}{\sqrt{n}}}(\mathbf{t})
= \sum_{\mathbf{x}\in \mathbb{Z}^d}\mathrm{e}^{\frac{\mathrm{i}}{\sqrt{n}}\sum_{j=1}^dt_jx_j}
\mathrm{Tr}[\omega^{(n)}(\mathrm{x})],\quad \mathbf{t}=(t_1, t_2,\cdots, t_d)\in \mathbb{R}^d,
\end{equation}
where $\mathbf{x}=(x_1, x_2,\cdots, x_d)$. Using Corollary~\ref{coro-3-4} gives
\begin{equation*}
  C_{\frac{X_n}{\sqrt{n}}}(\mathbf{t})
= \prod_{j=1}^d \Big(\sum_{x_j\in \mathbb{Z}}\mathrm{e}^{\frac{\mathrm{i}t_jx_j}{\sqrt{n}}}
  \mathrm{Tr}\big[\rho_j^{(n)}(x_j)\big]\Big), \quad \mathbf{t}=(t_1, t_2,\cdots, t_d)\in \mathbb{R}^d,
\end{equation*}
where
\begin{equation*}
\rho_j^{(n)} = \Big(\prod_{k=0}^{n-1}\mathfrak{J}_k\Big)\rho_j^{(0)},\quad 1\leq j\leq d.
\end{equation*}
Now consider $\lim_{n\to \infty}C_{\frac{X_n}{\sqrt{n}}}(\mathbf{t})$.
For each $j$, since $\rho_j^{(0)}$ is regular and $\big(\rho_j^{(n)}\big)_{n\geq 0}$ is generated by $\rho_j^{(0)}$ and $\big(\mathfrak{J}_n\big)_{n\geq 0}$, we have
\begin{equation*}
  \lim_{n\to \infty}\sum_{x_j\in \mathbb{Z}}\mathrm{e}^{\frac{\mathrm{i}t_jx_j}{\sqrt{n}}} \mathrm{Tr}\big[\rho_j^{(n)}(x_j)\big]
   = e^{-\frac{t_j^2}{2}},\quad t_j \in \mathbb{R},
\end{equation*}
which implies that
\begin{equation*}
  \lim_{n\to \infty}C_{\frac{X_n}{\sqrt{n}}}(\mathbf{t})
= \prod_{j=1}^d \Big(\lim_{n\to \infty}\sum_{x_j\in \mathbb{Z}}\mathrm{e}^{\frac{\mathrm{i}t_jx_j}{\sqrt{n}}}
  \mathrm{Tr}\big[\rho_j^{(n)}(x_j)\big]\Big)
= \prod_{j=1}^d e^{-\frac{t_j^2}{2}}
= e^{-\frac{1}{2} \sum_{j=1}^d t_j^2},
\end{equation*}
$\mathbf{t}=(t_1, t_2,\cdots, t_d)\in \mathbb{R}^d$. Thus, $\frac{X_n}{\sqrt{n}}$ converges in law to
the $d$-dimensional standard Gauss distribution as $n\rightarrow \infty$.
\end{proof}

\section{Links with unitary quantum walk}\label{sec-4}

In the final section, we unveil links between the $d$-dimensional open QBN walk
and the unitary quantum walk recently introduced in \cite{w-w}, which was called the $d$-dimensional QBN walk therein.

As before, $d\geq 2$ is a given positive integer.
We denote by $l^2\big(\mathbb{Z}^d, \mathcal{H}\big)$ the space of square summable functions
defined on $\mathbb{Z}^d$ and valued in $\mathcal{H}$, namely
\begin{equation}\label{eq-4-1}
  l^2\big(\mathbb{Z}^d, \mathcal{H}\big)
= \Big\{ W\colon \mathbb{Z}^d\rightarrow \mathcal{H} \Bigm| \sum_{\mathrm{x}\in \mathbb{Z}^d} \|W(\mathrm{x})\|^2<\infty\Big\},
\end{equation}
where $\|\cdot\|$ is the norm in $\mathcal{H}$.
It is known that $l^2\big(\mathbb{Z}^d, \mathcal{H}\big)$ forms a separable Hilbert space with
the inner product induced by the that in $\mathcal{H}$.

Recall that, for each $n\geq 0$,  $\big\{C_n^{(\varepsilon)}\mid \varepsilon\in \Lambda^d\big\}$ are self-adjoint
operators on $\mathcal{H}$ with properties that:\ $C_n^{(\varepsilon)}C_n^{(\varepsilon')}=0$
for $\varepsilon$, $\varepsilon'\in \Lambda^d$ with $\varepsilon\neq \varepsilon'$; and their sum
$\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}$ is a unitary operator on $\mathcal{H}$
(see Subsection~\ref{subsec-2-2} for details).
Using these facts, we can prove that there exists a sequence of unitary operators $\big(\mathcal{U}_n^{(d)}\big)_{n\geq 0}$
on $l^2\big(\mathbb{Z}^d, \mathcal{H}\big)$ such that
\begin{equation}\label{eq-4-2}
  \big(\mathcal{U}_n^{(d)}W\big)(\mathbf{x}) =\sum_{\varepsilon \in \Lambda^d} C_n^{(\varepsilon)}W(\mathbf{x}-\varepsilon),\quad \mathbf{x}\in \mathbb{Z}^d,\; W \in l^2\big(\mathbb{Z}^d, \mathcal{H}\big),\, n\geq 0.
\end{equation}
With these unitary operators as the evolution operators, the authors of \cite{w-w} introduced a unitary quantum walk on the $d$-dimensional integer lattice $\mathbb{Z}^d$
in the following manner.

\begin{definition}\label{def-4-1}\cite{w-w}
The $d$-dimensional QBN walk is a discrete-time unitary quantum walk on the $d$-dimensional integer lattice $\mathbb{Z}^d$ that satisfies the following requirements.
\begin{itemize}
\item Its states are represented by unit vectors in space $l^2\big(\mathbb{Z}^d, \mathcal{H}\big)$.

\item The time evolution of the walk is governed by equation
     \begin{equation}\label{eq-4-3}
      W_{n+1}= \mathcal{U}_n^{(d)}W_n,\quad  n\geq 0,
      \end{equation}
 where $W_n \in l^2\big(\mathbb{Z}^d, \mathcal{H}\big)$ denotes the state of the walk at time $n\geq 0$, and in particular $W_0$ is the initial state of the walk.
\end{itemize}
In that case, the function $\mathbf{x}\mapsto \|W_n(\mathbf{x})\|^2$ on $\mathbb{Z}^d$ is called the probability distribution of the walk at time $n\geq 0$,
while the quantity $\|W_n(\mathbf{x})\|^2$ is the probability to find out the walker
at position $\mathbf{x}\in \mathbb{Z}^d$ and time $n\geq 0$.
\end{definition}

\begin{remark}\label{rem-4-1}
According to (\ref{eq-4-2}), which describes the definition of unitary operators $\mathcal{U}_n^{(d)}$,
the evolution equation of the $d$-dimensional QBN walk can also be represented as
\begin{equation}\label{eq-4-4}
  W_{n+1}(\mathrm{x})
  = \sum_{\varepsilon\in \Lambda^d} C_n^{(\varepsilon)}W_n(\mathrm{x}-\varepsilon),\quad \mathrm{x} \in \mathbb{Z}^d,\, n\geq 0,
\end{equation}
which is more convenient to use.
\end{remark}

As is seen, the $d$-dimensional QBN walk is driven by the sequence $\big(\mathcal{U}_n^{(d)}\big)_{n\geq 0}$
of unitary operators. Hence it belongs to the category of unitary quantum walks. In other words,
it is indeed a unitary quantum walk.
The next result shows links between the $d$-dimensional open QBN walk and the $d$-dimensional QBN walk.

\begin{theorem}\label{thr-4-1}
Let $\big(\widetilde{\omega^{(n)}}\big)_{n\geq 0}$ be the state sequence of the $d$-dimensional open QBN walk,
where $\omega^{(n)}$ is the nucleus of $\widetilde{\omega^{(n)}}$.
Let $\big(W_n\big)_{n\geq 0}$ be the state sequence of the $d$-dimensional QBN walk.
Suppose that
\begin{equation}\label{eq-4-5}
  \omega^{(0)}(\mathrm{x}) = |W_0(\mathrm{x})\rangle\langle W_0(\mathrm{x})|,\quad \mathrm{x}\in \mathbb{Z}^d,
\end{equation}
where $|W_0(\mathrm{x})\rangle\langle W_0(\mathrm{x})|$ is the Dirac operator associated with $W_0(\mathrm{x})$.
Then, for all $n\geq 0$, it holds that
\begin{equation}\label{eq-4-6}
  \mathrm{Tr}\big[\omega^{(n)}(\mathrm{x})\big] = \|W_n(\mathrm{x})\|^2,\quad \mathrm{x}\in \mathbb{Z}^d.
\end{equation}
\end{theorem}

\begin{proof}
We first recall some algebraic and analytical properties of operators $C_n^{(\varepsilon)}$.
As is indicated above, for each $n\geq 0$, $\big\{C_n^{(\varepsilon)}\mid \varepsilon\in \Lambda^d\big\}$
are self-adjoint operators on $\mathcal{H}$ with the property that $C_n^{(\varepsilon)}C_n^{(\varepsilon')}=0$
for $\varepsilon$, $\varepsilon'\in \Lambda^d$ with $\varepsilon\neq \varepsilon'$, which implies that
\begin{equation}\label{eq-4-7}
  \Big\|\sum_{\varepsilon\in \Lambda^d}C_n^{(\varepsilon)}\xi_{\varepsilon}\Big\|^2
  = \sum_{\varepsilon\in \Lambda^d}\big\|C_n^{(\varepsilon)}\xi_{\varepsilon}\big\|^2
\end{equation}
whenever $\big\{\,\xi_{\varepsilon} \mid \varepsilon\in \Lambda^d\,\big\} \subset \mathcal{H}$.
And moreover, it follows from (\ref{eq-2-10}) and Definition~\ref{def-2-1}
that all the operators $\big\{\,C_n^{(\varepsilon)} \mid \varepsilon\in \Lambda^d,\, n\geq 0\,\big\}$ form a commutative family.

Now we consider (\ref{eq-4-6}). Clearly, it holds for $n=0$. In the following, we let $n\geq 1$ and $\mathrm{x}\in \mathbb{Z}^d$.
Using (\ref{eq-4-4}) and (\ref{eq-4-7}) gives
\begin{equation*}
  \|W_n(\mathrm{x})\|^2
    =\sum_{\varepsilon^{(n-1)}\in \Lambda^d}\big\|C_{n-1}^{(\varepsilon^{(n-1)})}W_{n-1}\big(\mathrm{x}-\varepsilon^{(n-1)}\big)\big\|^2,
\end{equation*}
where, by using the commutativity of the family
$\big\{\,C_k^{(\varepsilon)} \mid \varepsilon\in \Lambda^d,\, k\geq 0\,\big\}$
and (\ref{eq-4-7}), we have
\begin{equation*}
  \big\|C_{n-1}^{(\varepsilon^{(n-1)})}W_{n-1}\big(\mathrm{x}-\varepsilon^{(n-1)}\big)\big\|^2
  = \sum_{\varepsilon^{(n-2)}\in \Lambda^d}\big\|C_{n-1}^{(\varepsilon^{(n-1)})}
    C_{n-2}^{(\varepsilon^{(n-2)})}W_{n-2}\big(\mathrm{x}-\varepsilon^{(n-1)}-\varepsilon^{(n-2)}\big)\big\|^2.
\end{equation*}
Thus
\begin{equation*}
 \|W_n(\mathrm{x})\|^2
 = \sum_{\varepsilon^{(n-1)}\in \Lambda^d}\sum_{\varepsilon^{(n-2)}\in \Lambda^d}\big\|C_{n-1}^{(\varepsilon^{(n-1)})}
    C_{n-2}^{(\varepsilon^{(n-2)})}W_{n-2}\big(\mathrm{x}-\varepsilon^{(n-1)}-\varepsilon^{(n-2)}\big)\big\|^2.
\end{equation*}
It then follows by the induction that
\begin{equation}\label{eq-4-8}
 \|W_n(\mathrm{x})\|^2
 = \sum_{\varepsilon^{(n-1)}\in \Lambda^d}\cdots \sum_{\varepsilon^{(0)}\in \Lambda^d}
 \big\|C_{n-1}^{(\varepsilon^{(n-1)})}\cdots C_{0}^{(\varepsilon^{(0)})}
 W_{0}\big(\mathrm{x}-\varepsilon^{(n-1)}- \cdots - \varepsilon^{(0)}\big)\big\|^2.
\end{equation}
Similarly, repeatedly using the evolution relation (\ref{eq-2-20}) of the $d$-dimensional open QBN walk yields that
\begin{equation*}
  \omega^{(n)}(\mathrm{x})
  = \sum_{\varepsilon^{(n-1)}\in \Lambda^d}\cdots \sum_{\varepsilon^{(0)}\in \Lambda^d}
    C_{n-1}^{(\varepsilon^{(n-1)})}\cdots C_{0}^{(\varepsilon^{(0)})}
    \omega^{(0)}\big(\mathrm{x}-\varepsilon^{(n-1)}-\cdots - \varepsilon^{(0)}\big)
    C_{0}^{(\varepsilon^{(0)})}\cdots C_{n-1}^{(\varepsilon^{(n-1)})}.
\end{equation*}
Taking the trace gives
\begin{equation}\label{eq-4-9}
\begin{split}
 \mathrm{Tr}&\big[ \omega^{(n)}(\mathrm{x})\big]\\
  &= \sum_{\varepsilon^{(n-1)}\in \Lambda^d}\cdots \sum_{\varepsilon^{(0)}\in \Lambda^d}
   \mathrm{Tr}\big[ C_{n-1}^{(\varepsilon^{(n-1)})}\cdots C_{0}^{(\varepsilon^{(0)})}
    \omega^{(0)}\big(\mathrm{x}-\varepsilon^{(n-1)}-\cdots - \varepsilon^{(0)}\big)
    C_{0}^{(\varepsilon^{(0)})}\cdots C_{n-1}^{(\varepsilon^{(n-1)})}\big].
\end{split}
\end{equation}
On the other hand,  for $\varepsilon^{(n-1)}\in \Lambda^d$, $\cdots$, $\varepsilon^{(0)}\in \Lambda^d$, by using the assumption (\ref{eq-4-5}) we find
\begin{equation*}
\begin{split}
&\big\|C_{n-1}^{(\varepsilon^{(n-1)})}\cdots C_{0}^{(\varepsilon^{(0)})}
          W_{0}\big(\mathrm{x}-\varepsilon^{(n-1)}- \cdots - \varepsilon^{(0)}\big)\big\|^2\\
  &= \mathrm{Tr}\big[\big| C_{n-1}^{(\varepsilon^{(n-1)})}\cdots C_{0}^{(\varepsilon^{(0)})} W_{0}\big(\mathrm{x}-\varepsilon^{(n-1)}- \cdots - \varepsilon^{(0)}\big)\big\rangle \big\langle C_{n-1}^{(\varepsilon^{(n-1)})}\cdots C_{0}^{(\varepsilon^{(0)})} W_{0}\big(\mathrm{x}-\varepsilon^{(n-1)}- \cdots - \varepsilon^{(0)}\big)\big|\big]\\
  &= \mathrm{Tr}\big[ C_{n-1}^{(\varepsilon^{(n-1)})}\cdots C_{0}^{(\varepsilon^{(0)})}
           \omega^{(0)}\big(\mathrm{x}-\varepsilon^{(n-1)}-\cdots - \varepsilon^{(0)}\big)
          C_{0}^{(\varepsilon^{(0)})}\cdots C_{n-1}^{(\varepsilon^{(n-1)})}\big],
\end{split}
\end{equation*}
which, together with (\ref{eq-4-8}) and (\ref{eq-4-9}), implies that $\mathrm{Tr}\big[ \omega^{(n)}(\mathrm{x})\big] = \|W_n(\mathrm{x})\|^2$.
\end{proof}

\begin{remark}\label{rem-4-2}
It should be mentioned that under the conditions given in Theorem~\ref{thr-4-1}, one has, in general, that
\begin{equation}\label{eq-4-10}
  \omega^{(n)}(\mathrm{x}) \neq |W_n(\mathrm{x})\rangle\langle W_n(\mathrm{x})|,\quad \mathrm{x}\in \mathbb{Z}^d,\, n\geq 1.
\end{equation}
This suggests that the $d$-dimensional open QBN walk is mathematically different from the
$d$-dimensional QBN walk.
\end{remark}

However, from a perspective of physical realization, transition may happen between
these two walks. As an immediate consequence of Theorem~\ref{thr-4-1}, the next corollary
describes the limit case when such transition happens.

\begin{corollary}\label{coro-4-2}
Let the initial state $\widetilde{\omega^{(0)}}$ of the $d$-dimensional open QBN walk be such that
\begin{equation}\label{eq-4-11}
  \widetilde{\omega^{(0)}} = \sum_{\mathrm{x}\in \mathbb{Z}^d}|\delta_{\mathrm{x}}\rangle\langle \delta_{\mathrm{x}}|
  \otimes |W_0(\mathrm{x})\rangle\langle W_0(\mathrm{x})|,
\end{equation}
where $W_0$ is the initial state of the $d$-dimensional QBN walk. Then, the $d$-dimensional open QBN walk has a limit probability distribution
if and only if the $d$-dimensional QBN walk
has a limit probability distribution. In that case, their limit probability distributions
are identical.
\end{corollary}

\section*{Acknowledgement}

This work is partly supported by National Natural Science Foundation of China (Grant No. 11861057).


TITLE: Use Fubini's Theorem to verify the integration by parts formula, and justify that the hypotheses of Fubini's Theorem are satisfied.
QUESTION [2 upvotes]: Let $f$ and $g$ be Lebesgue integrable real-valued functions on $[0,1]$, and define
$$F(x) = \int_0^x f(t)dt, \quad \text{and} \quad G(x) = \int_0^x g(t) dt.$$
Use Fubini's Theorem to verify the integration by parts formula
$$\int_0^1 F(x)g(x)dx = F(1)G(1) - \int_0^1 f(x)G(x)dx.$$
Justify that the hypotheses of Fubini's Theorem are satisfied.
This one seems straightforward to us, but for some reason we can't get anything nice to appear.
Here are our attempts for the left-hand side and the right-hand side respectively after the hint:
$$\begin{aligned} \int_0^1 F(x)g(x)dx &= \int_0^1 \int_0^x f(t)dtg(x)dx\\
&= \int_0^1\int_0^1 1_{[0,x]}f(t)g(x)dtdx\\
&= \int_0^1 f(t) \int_0^1 1_{[0,x]}g(x)dxdt. \end{aligned}$$
$$\begin{aligned} F(1)G(1) - \int_0^1 f(x)G(x)dx &= F(1)G(1) - \int_0^1 f(x)\int_0^x g(t)dtdx\\
&= F(1)G(1) - \int_0^1\int_0^1 1_{[0,x]}f(x)g(t)dtdx\\
&= F(1)G(1) - \int_0^1g(t)\int_0^1 1_{[0,x]}f(x)dxdt.\end{aligned}$$

REPLY [3 votes]: The first few steps just involves rewriting the terms as they are defined and moving constants inside or outside of an integral as needed.
$$
\begin{align*}F(1)G(1)&=\Big(\int_0^1f(t)dt\Big)\Big(\int_0^1 g(x)dx\Big)= \int_0^1g(x)\Big(\int_0^1 f(t)dt\Big)dx\\
&= \int_0^1g(x)\Big(\int_0^x f(t)dt\Big)dx + \int_0^1g(x)\Big(\int_x^1 f(t)dt\Big)dx\\
&= \int_0^1 g(x)F(x)dx + \int_0^1g(x)\Big(\int_x^1 f(t)dt\Big)dx\end{align*}$$
Now we use Fubini's Theorem to show that the second integral takes the appropriate form. Well
$$\begin{align*}\int_0^1 g(x)\Big(\int_x^1 f(t)dt\Big)dx &= \int_0^1g(x)\int_0^1 1_{[0\leq x\leq t\leq 1]}(x,t)f(t)dt dx\\
&= \int_0^1\int_0^1 1_{[0\leq x\leq t\leq 1]}(x,t)g(x)f(t)dt dx\\
&= \int_0^1\int_0^1 1_{[0\leq x\leq t\leq 1]}(x,t)g(x)f(t)dxdt\\
&= \int_0^1f(t)\int_0^1 1_{[0\leq x\leq t\leq 1]}(x,t)g(x)dx dt \\
&= \int_0^1f(t)\Big(\int_0^1 1_{[0\leq x\leq t]}(x)g(x)dx\Big) dt \\
&= \int_0^1f(t)\Big(\int_0^t g(x)dx\Big) dt \\
&= \int_0^1 f(t)G(t)dt\end{align*}$$
Hence after a change of variables we have that
$$F(1)G(1) = \int_0^1 g(x)F(x)dx + \int_0^1 f(x)G(x)dx $$


TITLE: What is the speed of light in geometrical optics?
QUESTION [2 upvotes]: Geometrical optics or Hamiltonian optics is the short wave length limit of Maxwells equations of light. In Hamiltonian form it is equivalent to the Hamiltonian description of a single, classical, non-relativistic particle with mass $m$.
However in non-relativistic, classical mechanics it is sometimes said, that the speed of light is assumed to be infinite. But I believe it must be assumed, that the speed of light is at least finite (but probably not invariant for inertial observers?) for the theory to make sense. But I'm not sure. What is the assumed speed of light within the framework of this theory?

REPLY [4 votes]: In the construction of geometrical optics, no assumption is made on the speed of light. One can construct the Fermat principle and associated approximations even in fully relativistic formalism. (An example can be found in the book Gravitation by Misner, Thorne and Wheeler.)
On the other hand, if deriving non-relativistic mechanics from relativity, we do assume that the constituents of the mechanical system move at speeds $v$ much smaller than the speed of light $c$ in our lab frame. I.e. $v/c \approx 0$ and our lab frame plays a privileged role.
The fact that both classical mechanics and ray optics both have a Lagrangian and Hamiltonian formulation does not mean they are both ``nonrelativistic" in some sense or that they can be derived using some unified limit - they are not. In fact, even fully relativistic particle mechanics have a Lagrangian and Hamiltonian formulation. This is because the Lagrangian and Hamiltonian formalism is more of a mathematical method how to describe dynamics of a broad class of systems.
But! Your are correct that using Hamiltonian optics and generally any light dynamics along with non-relativistic mechanics leads to a weird inelegant system. Namely, weird extra terms pop up e.g. in dispersion relations of light when transforming between reference frames using Galilean transformations.
This was often historically hand-waived away by saying that the "nice" equations for the propagation of light are defined with respect to the reference frame of the medium and this also lead to the postulation of aether, the ``vacuum medium". Ultimately, this weird aether business and the Michelson-Morley experiment lead Einstein to his special relativity.
So the "classical" or "non-relativistic" sets of theories for light and massive particles are not quite consistent and one cannot really expect them to be. (They are quite useful nonetheless...)


TITLE: Can the pushforward of a very ample invertible sheaf under a birational morphism be reflexive?
QUESTION [5 upvotes]: Let $f: Y \to X$ be a birational  morphism of  projective varieties.  Let $\mathcal{M}$ be a very ample invertible sheaf on $Y$.  Suppose also that:

$f^{-1}$ is defined away from a single point $x \in X$.
$f_* \mathcal{O}_Y = \mathcal{O}_X$.

Two questions:
(1) If $V$ is a set of global sections of $\mathcal{M}$ that generate $\mathcal{M}$, consider the induced evaluation map
$ V \otimes \mathcal{O}_X \to f_* \mathcal{M}$.
Let $\mathcal{N}$ be the image of this map.  Is it possible for $\mathcal{N}$ to be reflexive?  (Full disclosure:  I would like the answer to be no.)
If we know that $X$ is smooth at $x$, or more generally that $(f_* \mathcal{M})^{\vee\vee}$ is invertible, then the answer   is no.  Let $E$ be the exceptional locus of $f$.  Then $E$ is positive-dimensional, so any hyperplane section meets $E$ nontrivially, and thus any section of $f_* \mathcal{M}$ must vanish at $x$.  But if $(f_* \mathcal{M})^{\vee\vee}$ is only reflexive, then I don't see how to generalise this argument.
(2)
Is it possible for $f_* \mathcal{M}$ to be reflexive?  If so, what is the weakest possible condition that will guarantee that $f_* \mathcal{M}$ is not reflexive?
My chief interest in (2) is that a negative answer to (2) would be a cheap way to get a negative answer to (1).

REPLY [3 votes]: Hi Sue, I think it can be reflexive.
Let's consider $X = \text{Proj} k[x,y,u,v,t]/\langle xy - uv \rangle$.  This has only an isolated singularity at $x=y=u=v=0$ (it's the simplest non-Q-factorial singularity I know of).  Fix $U$ to be the regular locus of $X$.
(Blow up a divisor:) Set $\pi: Y \to X$ to be the blowup of the prime divisor $D = V(x,u)$.  This is a small resolution of $X$ (and also contains $U$ as an open set).  Lets define $F$ on $Y$ to be such that $O_Y(-F) = O_X(-D) \cdot O_Y$.  In other words, $F$ is the inverse image of $D$.  Notice that $\pi_* O_Y(-F) = O_X(-D)$ since $\pi$ is a small resolution.  Let me explain this point.
Choose $V \subseteq X$ an open set.  Then
$$
\Gamma(V, \pi_* O_Y(-F)) = \Gamma(\pi^{-1} V, O_Y(-F)) = \Gamma((\pi^{-1} V) \cap U, O_Y(-F))
$$
since $\pi^{-1}V \setminus U$ is codimension 2 (see for example THIS ANSWER by Sándor Kovács).
But $\Gamma((\pi^{-1} V) \cap U, O_Y(-F)) = \Gamma(V \cap U, \pi_* O_Y(-F))$.  It follows that $\pi_* O_Y(-F)$ is determined away from the singularity, and is therefore S2 / reflexive.
Since $Y$ is smooth, $F$ is a Cartier divisor and we know that $-F$ is $\pi$-ample by construction.  Set $A = V(t)$ to be an ample Cartier divisor on $X$ (the choice of $A$ doesn't matter so much here).
(Define $\mathcal{M}$): It follows that $\mathcal{M} = O_Y(-F + n \pi^*A)$ is ample on $Y$ for $n \gg 0$.
Then we know
$$
\pi_* O_Y(-F + n \pi^* A) = (\pi_* O_Y(-F) ) \otimes O_X(nA) = O_X(-D + nA).
$$
which is reflexive.  Note that you can also consider $-mF + mn \pi^* A$ to make  $\mathcal{M}^m$ as ample as you'd like.  The same sort of computation still holds.
Ok, so this gives a negative answer for (2).
(Question 1.): Let's now consider (1).  Note $\pi_* \mathcal{M}$ is globally generated (since $n \gg 0$).  But on the other hand,
$$H^0(X, \pi_* \mathcal{M}) = H^0(U, \mathcal{M}) = H^0(Y, \mathcal{M})$$ again since $X \setminus U$ and $Y \setminus U$ are codimension 2.
Thus the global section of $H^0(Y, \mathcal{M})$ already globally generate $\pi_* \mathcal{M}$, so I don't think (1) works either.
Obviously if $X$ is Factorial then you won't run into this problem as you already pointed out.


TITLE: Prove $|A| \leq |B|$ for $1-1$ function.
QUESTION [0 upvotes]: Prove $|A|\leq |B|$ if function $F:A\rightarrow B$ is a $1-1$ function.
I wanted to know how to prove this out of curiosity. The help is appreciated.

REPLY [1 votes]: By definition a function ($F$) is called one-to-one (aka injective) if every element in the codomain ($B$) is mapped to by at most one element of the domain ($A$).
It follows immediately that the codomain must have at least as great a cardinality as the domain; $|A|\leqslant |B|$.   This holds whether the sets have finite or transfinite cardinality.


TITLE: Interesting properties of complex tori as groups and how they affect our understanding of elliptic curves
QUESTION [2 upvotes]: I'm finishing up a small project I've written up for my final year of college, where I was given the objective to learn about elliptic curves and write a paper on what I've learned. I'm writing for an audience that knows basic commutative algebra and complex analysis (up until just before Riemann surfaces), and I am proving everything by first principles.
How I structured the paper so far is as follows:

Defined algebriac curves, (proved Hilbert's Nullstellensatz in the appendix)
Proved Bézout's theorem using resultants and derived some properties of cubics such as the Cayley-Bacharach theorem
Proved that every non-singular cubic curve in the plane is equivalent to a cubic in Weierstrass form by a change of variables and are therefore elliptic curves
Defined the group law on elliptic curves and proved it was associative
Defined  complex tori, elliptic functions and the Weierstrass-$\wp$ function. Showed that every complex torus is isomorphic to an elliptic curve and vice versa

Now I am exploiting this isomorphism to derive properties of the group law on the elliptic curve. So far I've proved that the group law on an elliptic curve is divisible, and that $E[n]\cong (\mathbb{Z}/n\mathbb{Z})\times (\mathbb{Z}/n\mathbb{Z}).$
My question is this: is there any other interesting facts about the group law that can be derived from this isomorphism? I want to make all of the work put in to read through everything seem more "worthwhile".

REPLY [2 votes]: You can show using this description the nice description of what the endomorphisms of the group are (either $\mathbb{Z}$ or an order in an imaginary quadratic field, depending on which lattice you chose).


TITLE: Implication of Correlation on Conditional Expectation
QUESTION [0 upvotes]: I came across a result saying that if the conditional expectation function $E[Y|X=x]$ is increasing in $x$, then the correlation of $X$ and $Y$ must be positive. Is there any kind of converse to this? That is, if the correlation of $X$ and $Y$ is positive, can we say anything about $E[Y|X\geq x]$ and $E[Y|X\leq x]$?

REPLY [0 votes]: If $E[Y|X]=h(X)$, with $h$ an increasing function, then $Y$ is positively  correlated with every random variable of the form $g(X)$, with $g$ increasing (provided the correlations exist). This more detailed correlation information as hypothesis may lead to an interesting converse. The positive correlation of $Y$ and $X$ alone seems to be not enough information to get what you want.


TITLE: Discontinuity phenomenon in polynomial optimization
QUESTION [1 upvotes]: Let $Q(x,y)$ be a polynomial in the two variables $x$ and $y$, with real coefficients. Let $a<b$; for any fixed $x$ the polynomial $Q(x,.)$ has a minimum $m(x)$ when $y$ varies in $[a,b]$. We know that this minimum is attained ; call $\eta (x)$ the smallest value in $[a,b]$ where $Q(x,.)$ reaches this minimum. It is also well-known that $\eta (x)$ is either $a$, or $b$, or that $\frac{\partial Q}{\partial y}(x,\eta(x))=0$.
Now there are cases when the fonction $\eta$ is not continuous everywhere : I provide a complicated example below. My example has total degree 12 (degree $6$ in both $x$ and $y$) . I am looking for simpler examples, so here goes my question : what is the smallest total degree of $Q$ for such a phenomenon to appear ?
The example : let $a=0,b=4$ and
$$
Q(x,y)=12348(x^6 + y^6 + 1)+64344(x^5(y+1)+y^4(x+1)+x+y)+111977((y^2 + 1)x^4 + (x^2 + 1)y^4 + x^2 + y^2)+113162((xy)^3+x^3+y^3)+136346xy(x^3+y^3+1)-150890xy((y + 1)x^2+(x+1)y^2+x+y)-938154(xy)^2
$$
Then one can check with GP that :
The polynomial $R(x)={\sf Res}_y(Q(x,y)-Q(x,0),\frac{\partial Q}{\partial x}(x,y))$ is a product of three factors : it is $(x+1)^2$ times a polynomial of degree $4$ times a polynomial $S(x)$ of degree $20$. Then $S(x)$ has eight real roots. The fifth root, $\alpha$, is approximately
$\alpha=0.5267883330835579971974199435$.
The polynomial $T(y)=\frac{\partial Q}{\partial x}(\alpha,y)$ has five real roots. The largest, $\beta$, is approximately  $\beta=0.5185888479238405761315858539$.
And one has $\eta(x)=0$ for $x \in [0,\alpha[$, $\eta(x)>\beta$ for $x\in ]\alpha,1]$. So $\eta$ has a jump at $\alpha$.

REPLY [3 votes]: Take $Q(x,y) = xy$ and see what happens at $x=0$.  Note that $Q(x, \cdot)$ is linear for each $x$

REPLY [1 votes]: If I understand correctly, you're asking about discontinuities in the function $$\eta(x) = \operatorname{arg\,min}\limits_{y \in [a,b]}\ Q(x,y).$$
Consider the function $y^4 - y^2 + xy$. For small $x$, this looks like a Mexican hat potential with two local minima; the value of $x$ determines which one is the global minimum.
I think this sort of thing is studied in catastrophe theory.
But the answer to your question of the smallest total degree is just two. Let $Q(x,y) = xy$. Depending on the sign of $x$, the value of $\eta(x)$ is either $a$ or $b$.

REPLY [1 votes]: What about $Q(x,y) = -(x-y)^2$, $[a,b] = [0,1]$, where $\eta(x) = 0$ if $x \le 1/2$ and $1$ if $x > 1/2$?