text:
\begin{document}
		\begin{spacing}{0.95}

	\title{An Explicit Formula for the\\Zero-Error Feedback Capacity of a \\Class of Finite-State Additive Noise Channels}

		\author{Amir Saberi\textsuperscript{ a}, Farhad Farokhi\textsuperscript{ a,b} and Girish N.~Nair\textsuperscript{ a}}
	\author{{Amir Saberi, Farhad Farokhi and Girish N.~Nair}
	\thanks{The authors are with the Department of Electrical and Electronic Engineering, University of Melbourne, VIC 3010, Australia  (e-mails: asaberi@student.unimelb.edu.au, \{ffarokhi, gnair\}@unimelb.edu.au). F. Farokhi is also with the CSIRO's Data61 (e-mail: farhad.farokhi @data61.csiro.au). $ \qquad  \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad$
		{\textcopyright} 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ }}

	\maketitle
	\thispagestyle{empty}

	\begin{abstract}
		It is known that for a discrete channel with correlated additive noise, the ordinary capacity with or without feedback both equal $ \log q-\mathcal{H} (Z) $, where $ \mathcal{H}(Z) $ is the entropy rate of the noise process $ Z $ and $ q $ is the alphabet size. In this paper, a class of finite-state additive noise channels is introduced. It is shown that the zero-error feedback capacity of such channels is either zero or $C_{0f} =\log q -h (Z) $, where $ h (Z) $ is the {\em topological entropy} of the noise process. A topological condition is given when the zero-error capacity is zero, with or without feedback. Moreover, the zero-error capacity without feedback is lower-bounded by $ \log q-2 h (Z) $. We explicitly compute the zero-error feedback capacity for several examples, including channels with isolated errors and a Gilbert-Elliot channel.
	\end{abstract}

	\section{Introduction}
	In his 1956 paper \cite{shannon1956zero}, Shannon introduced the concept of zero-error communication. Although, a general formula is still missing for the zero-error capacity $ C_0 $ of a discrete memoryless channel (DMC) without feedback, Shannon derived one for the zero-error capacity $ C_{0f} $ of a DMC with noiseless feedback. In recent years, there has been progress towards determining $ C_{0f} $ for channels with memory. In \cite{zhao2010zero}, Zhao and Permuter introduced a dynamic programming formulation for computing  $ C_{0f} $ for a finite-state channel modeled as a Markov decision process, assuming state information is available at both encoder and decoder. However, the problem is still open when there is no state information at the decoder.

	In this paper, we study the zero-error capacity, with and without feedback, of discrete channels with additive correlated noise. The ordinary capacities with and without feedback of such channels are studied in \cite{alajaji1995feedback}, in which it is proved that
	 \begin{align}
	 C=C_f=\log_2 q-\mathcal{H} (Z),\label{ccf}
	 \end{align}
	where $q$ is the input alphabet size and $\mathcal{H}(Z) $ is the entropy rate of the noise process $ Z $. In this paper, we consider additive noise channels where the noise is generated by a finite-state machine.  We prove a similar formula for the zero-error feedback capacity $ C_{0f} $ and a lower bound for the zero-error capacity $ C_0 $, in terms of {\em topological entropy} (Theorem \ref{thm:zero-error}).  Unlike \cite{zhao2010zero}, we do not assume that channel state information is available at the encoder or decoder. In \cite{saberi2019state}, we studied $ C_0 $ of some special cases of these channels and derived a similar lower bound. In this paper, we extend that result to a more general channel model, and also derive an exact formula for $C_{0f}$.  Examples including the well-known Gilbert-Elliot channel are considered, for which the explicit value of $ C_{0f} $ is computed. To the best of our knowledge, this has not been done for these channels.

	The rest of paper is organized as follows. In Section~\ref{sec:model} the channel model and main results are presented. Proofs are given in Sections~\ref{sec:proof} and \ref{sec:proofl} and some examples are discussed in \ref{sec:examps}. Finally, concluding remarks and future extensions are discussed in section~\ref{sec:conclusions}.

	Throughout the paper, calligraphic letters such as $ \mathcal{X} $, denote sets. The cardinality of set $ \mathcal{X} $ is denoted by $ |\mathcal{X}| $. The channel input alphabet size is $ q $, logarithms are in base $2$. Random variables are denoted by upper case letters such as $ X $, and their realizations by lower case letters such as $ x $. The vector $ (x_i)_{i=m}^n $ is denoted by $ x_{m:n} $.

	\section{Channel Model and Main Results} \label{sec:model}
	Let the input, output and noise at time $ i\in \mathbb{N} $ in the channel be $ x_i \in \mathcal{X} $, $ y_i \in \mathcal{Y} $, and $ z_i \in \mathcal{Z} $, respectively. Before we describe the channel, we define the following notion.
	\begin{defi}[Finite-state machine] \label{def:fsm}
		A {\em finite-state machine} is defined as directed graph $\mathscr{G}=(\mathcal{S},\mathcal{E})$, where the vertex set $ \mathcal{S}=\{0,1,\dots,|\mathcal{S}|-1\} $ denotes {\em states} of the machine, and the edge set $\mathcal{E}\subseteq\mathcal{S}\times \mathcal{S}$ denotes possible transitions between two states. We say a process $(S_i)_{i\geq 1}$ is described by $\mathscr{G}$ if a) there is a positive probability that any state is eventually visited, i.e. $\forall s\in\mathcal{S}$, $\exists i\geq 1$ s.t.  $P(S_i=s)>0$, b) if $(s,s')\in\mathcal{E}$, a transition  $s\to s'$ is always possible for all possible past state sequences, i.e. $P(S_{i+1}=s'|S_i=s, s_{1 :i-1}) > 0$ whenever $P(S_i=s, s_{1 :i-1}) > 0$; and c) conversely, if $(s,s')\notin \mathcal{E}$, then $P(S_{i+1}=s'|S_i=s, s_{1 :i-1}) = 0$ whenever $P(S_i=s, s_{1 :i-1}) > 0$.
	\end{defi}

	{\bf Remark:} Processes described by a finite-state machine are {\em topologically Markov} [5, Ch.2], but need not be stochastic Markov chains.

	The following channel is studied in this paper.
	\begin{defi}[Finite-state additive noise channels]
		\label{def:fanchannel}
		A discrete channel with common input, noise and output $ q $-ary alphabet $ \mathcal{X} $ is called {\em finite-state additive noise} if its output at time $ i \in \mathbb{N} $ is obtained by
		\begin{align*}
		Y_i = X_i \oplus Z_i, \, i \in \mathbb{N},
		\end{align*}
		where $ \oplus $ is modulo $ q $ addition and the correlated additive noise $ Z_i $ is governed by a state process $ (S_i) $ on a finite-state machine such that each outgoing edge from a state $ s_i $ corresponds to different values $ z_i $ of the noise. Thus, there are at most $ q $ outgoing edges from each state.
		We assume the state transition diagram of the channel is strongly connected  and that $Z_i$ is independent\footnote{ This can be relaxed to {\em qualitative independence} \cite[Ch.1]{renyi1970foundations}; i.e. if $P(X_{1:k}~=~x_{1:k})$ and $P(Z_k=z_k)$ are both positive, then  $P(X_{1:k}=x_{1:k},Z_k=z_k)>0$.} of $X_{1:i}$.
	\end{defi}
	Figure \ref{fig:examp} shows a noise process which defines a channel that has no more than two consecutive errors. For example, the transition at time $ i $ from state $ S_i=0 $ to itself corresponds to $ Z_i=0 $. Moreover, $ Z_i=1 $ leads to the transition ending in state $ S_{i+1}=1 $ (state at next time step). Note that, in $ S_i=2 $, the noise can only take $ Z_i=0 $ and transits to $ S_{i+1}=0 $.

\begin{figure}[t]
	\centering
	\begin{tikzpicture}
	[->, auto, semithick, node distance=3.4cm]
	\tikzstyle{every state}=[fill=white,draw=black,thick,text=black,scale=1]
	\node[state]   (S1)       {$ S_i=0 $};
	\node[state]   (S2)[right of=S1]   {$ S_i=1 $};
	\node[state]   (S3)[right of=S2]   {$ S_i=2 $};
	\path
	(S1) edge[out=160, in=200,looseness=5] node [above=0.25] {$ Z_i=0 $}(S1)
	edge[bend left] node [above] {$ Z_i=1 $}  (S2)
	(S2) edge[bend left]  node [above=0.1] {$ Z_i=0 $}  (S1)
	edge[bend left]  node [above] {$ Z_i=1 $}  (S3)
	(S3) edge[bend left]  node [above] {$ Z_i=0 $}  (S1.300);
\end{tikzpicture}
\caption{State transition diagram of a noise process in a channel at which no more than two consecutive errors can happen in the channel.}
\label{fig:examp}
\end{figure}
\begin{defi}[Coupled graph] \label{def:dg}
	{\em Coupled graph} of a finite-state machine (with labeled graph $ \mathscr{G} $) is defined as a labeled directed graph\footnote{This product is called {\em tensor product},  as well as {\em Kronecker  product} \cite[Ch. 4]{hammack2011handbook}. } $\mathscr{G}_c=\mathscr{G}\times \mathscr{G}$, such that it has vertex set $ V=\mathcal{S}\times \mathcal{S} $ and has an edge from node $ u=(i,j) \in V $ to $ v=(k,m) \in V  $ if and only if there are edges from $ S=i $ to $ S=k $ (with a label value $ E_{ik} $) and from $ S=j $ to $ S=m $ (with a label value $ E_{jm} $) in $ \mathscr{G} $, each edge has a label equal to $E_{ik} \ominus E_{jm}$, where $ \ominus $ is modulo $ q $ subtraction.
\end{defi}
For a state-dependent channel, the zero-error capacity is defined as follows.
\begin{defi} \label{def:c0}
	The zero-error capacity, $C_0$, is the largest block-coding rate that permits zero decoding errors, i.e.,
	\begin{align}
	C_0:=\sup_{n \in \mathbb{N}, \, \mathcal{F} \in \mathscr{F}}
	\frac{\log |\mathcal{F}|}{n}, \label{c0def}
	\end{align}
	where $ \mathscr{F}\subseteq \mathcal{X}^{n}$  is the set of all block codes of length $ n $ that yield zero decoding errors for any channel noise sequence and channel initial state, such that no state information is available at the encoder and decoder. In a zero-error code, any two distinct codewords $ x_{1:n},\, x'_{1:n} \in \mathscr{F} $ can never result in the same channel output sequence, regardless of the channel noise and initial state.
\end{defi}
The zero-error feedback capacity $C_{0f}$ is defined in the presence of a noiseless feedback from the output. In other words, assuming $ m \in \mathcal{M} $ is the message to be sent and  $ y_{1:n} $ is the output sequence received then $ x_i(m)=f_{m,i}(y_{1:i-1}), \, i=1,\dots, n, $ where $ f_{m,i} $ is the encoding function. Let the family of encoding functions $ \mathcal{F_{\mathcal{M}}}=\{f_{m,n}: m \in \mathcal{M}\} $. The zero-error feedback capacity, is the largest block-coding rate that permits zero decoding errors.

Before, presenting the main results, we need some preliminaries from symbolic dynamics.
In symbolic dynamics, topological entropy is defined as the asymptotic growth rate of the number of possible  state sequences. For a finite-state machine with an irreducible transition matrix $\mathcal{A}$, the topological entropy $ h $ is known to coincide with $\log\lambda$, where $\lambda$ is the {\em Perron value} of $\mathcal{A}$~\cite{lind1995introduction}. This is essentially due to the fact that the number of the paths from state $ S=i $ to $ S=j $ in $ n $ steps is the $ (i+1,j+1) $-th element of $ \mathcal{A}^n$, which grows at the rate of $\lambda^n$ for large $n$.

First we give a topological condition on when zero-error capacity is zero, with or without feedback.
\begin{thm}\label{thm:c0f0}
	The zero-error capacity with(out) feedback $ C_{0f} \,$(resp. $ C_0 $) of a finite-state additive noise channel [Def. \ref{def:fanchannel}] having finite-state machine [Def. \ref{def:fsm}] graph  $\mathscr{G}=(\mathcal{S},\mathcal{E}) $  is zero, if and only if $ \forall \, d_{1:n} \in \mathcal{X}^{n} , n \in \mathbb{N} $, there exists a walk on the {\em coupled graph} [Def. \ref{def:dg}] of $ \mathscr{G} $ with the label sequence $ d_{1:n} $.
\end{thm}
\textbf{Remark:} This result implies that $ C_0 = 0 $ if and only if $ C_{0f} = 0 $ for finite-state additive noise channels.
\begin{proof}
	\textit{Sufficiency:} We show that for any choice of encoding functions and blocklength $ n $ there is a common output for $ m,m' \in \mathcal{M}$, i.e., $ \exists z_{1:n},z'_{1:n} $ such that the output sequences, $ y_{1:n}=y'_{1:n} $, where $ y_{1:n}=f_{m,1:n}\oplus z_{1:n}, \,y'_{1:n}=f_{m',1:n}\oplus z'_{1:n} $. In other words, $\forall \, n \in \mathbb{N}$, and
\[ d_{1:n}:=f_{m',1:n}(z'_{1:n-1}) \ominus f_{m,1:n}(z_{1:n-1})\, \in \mathcal{X}^n,\]
$\exists\, z_{1:n},z'_{1:n}$ such that $d_{1:n}(z_{1:n-1},z_{1:n-1})= z_{1:n} \ominus z'_{1:n} $.

First observe that having current states $ S_i=s$ and $S'_i=s' $, for two noise sequences of $ z_{1:i-1}$ and $z'_{1:i-1} $, respectively, the label on out-going edges in the coupled graph is belong to $ \{z_i \ominus z'_i |  S_i=s,  S'_i=s' \}$.
Now consider the first transmission, by choosing any inputs $ f_{m,1}, f_{m',1} \in \mathcal{X}$, if there is an edge from any state $ (k,j) \in V $ with the value $d_1:=f_{m',1}\ominus f_{m,1} \in \mathcal{X}$ then there exist $ z_1,z'_1 \in \mathcal{X} $ that produce a common output for two channel inputs $ f_{m,1} $ and $ f_{m',1} $. By continuing this argument for any $ i\in \mathbb{N} $ having $ y_{1:i-1}=y'_{1:i-1} $, if $ d_i =f_{m',i}(z'_{1:i-1}) \ominus f_{m,i}(z_{1:i-1}) \in \mathcal{X} $ is chosen such that there is an edge with value $ d_i $ then there is an output shared with two messages. In other words, by choosing any value for $ d_i $, if there is an edge with corresponding value it means there is a pair of noise values $ (z_i,z'_i) $ such that $ d_i=z_i \ominus z'_i $, therefore $ y_i=y'_i $. If there is no such an edge for a particular $ d_i $, then there is no pair of noise values that produces the same output, and thus, $  y_i \neq y'_i $.

Therefore, if $ \forall n \in \mathbb{N} $ and for any choice of $ d_{1:n} \in \mathcal{X}^n $ there is a walk on the coupled graph then the corresponding noise sequences of the walk can produce the same output, i.e. $ y_{1:n}=y'_{1:n} $ which implies $ C_{0f}=0 $ and therefore $ C_0=0 $.\\

\textit{Necessity:} Assume there is no walk for a sequence of $ d_{1:n} $ then by choosing any two input sequences $x_{1:n}, x'_{1:n}$ such that $ x_{1:n}\ominus x'_{1:n}=d_{1:n} $, two messages $ m $ and $ m' $ can be transmitted with zero-error which contradict with the assumption that $ C_{0}=0 $ (and also $ C_{0f}=0 $).
\end{proof}
We now relate the zero-error capacities of the channel to the noise process topological entropy.

\begin{thm}\label{thm:zero-error}
	The zero-error feedback capacity of the finite-state additive noise channel [Def. \ref{def:fanchannel}] with topological entropy $h(Z)$ of the noise process where no state information is available at the transmitter and decoder is either zero or
	\begin{align}
	C_{0f} &= \log q-h(Z).\label{c0f}
	\end{align}
	Moreover, the zero-error capacity (without feedback) is lower bounded by
		\begin{align}
	C_{0} &\geq \log q - 2h(Z).\label{c0l}
	\end{align}
\end{thm}
\textbf{Remarks:} \begin{itemize} \item The zero-error feedback capacity has a similar representation to the ordinary feedback capacity in \eqref{ccf} but with the stochastic noise entropy rate  $ \mathcal{H} (Z) $ replaced with the topological entropy $h(Z)$.

	\item The topological entropy can be viewed as the rate at which the noise dynamics generate uncertainty. Intuitively, this uncertainty cannot increase which explains why it appears as a negative term on the right hand side of \eqref{c0f} and \eqref{c0l}. Moreover, the sum of zero-error feedback capacity and the topological entropy is always equal to $ \log q $, meaning that if the noise uncertainty is increased, the same amount will be decreased in the capacity.

	\item The result of \eqref{c0f} is an explicit closed-form solution, which is a notable departure from the iterative, dynamic programming solution in \cite{zhao2010zero}.

	\item Following Definition \ref{def:fanchannel}, the channel states are not assumed to be Markov, just topologically Markov. Thus the  transition probabilities in the finite-state machine can be time-varying dependent on previous states. In other words, as long as the graphical structure is not changed, the result is valid.
\end{itemize}

\section{Proof of the Zero-error Feedback Capacity} \label{sec:proof}

The conditions on when $ C_{0f}=0 $ is given in Theorem \ref{thm:c0f0}. Here, we consider $ C_{0f}>0 $. Before presenting the rest of the proof, we give the following lemma.
\begin{lem}\label{lem:out}
	For a finite-state additive noise channel with irreducible adjacency matrix, there exist positive constants $ \alpha $ and  $ \beta $ such that, for any input sequence $ x_{1:n} \in \mathcal{X}^n $, the number of all possible outputs
	\begin{align}
	\alpha \lambda^n \leq |\mathcal{Y}(s_0,x_{1:n}) |=|\mathcal{Z}(s_0,n) | \leq  \beta  \lambda^n , \label{outlam}
	\end{align}
	where $\lambda $ is the Perron value of the adjacency matrix. Moreover, $ \mathcal{Y}(s_0,x_{1:n}) $ and $ \mathcal{Z}(s_0,n) $ are the possible output and noise values for a given initial state $ s_0 $ and input sequence $ x_{1:n} $.
\end{lem}
\begin{proof}
	The output sequence, $ y_{1:n} $, is a function of input sequence, $ x_{1:n} $, and channel noise, $ z_{1:n} $, which can be represented as the following
	\begin{align}
	y_{1:n} = x_{1:n} \oplus z_{1:n},  \label{adnoise}
	\end{align}
	where $ z_{1:n} \in \mathcal{Z}(s_0,n) $. The set of all output sequences $ \mathcal{Y}(s_0,x_{1:n}) $ can be obtained as $\mathcal{Y}(s_0,x_{1:n})=\{ x_{1:n} \oplus z_{1:n}| z_{1:n} \in \mathcal{Z}(s_0,n)\}$.
	Since for given $ x_{1:n} $, \eqref{adnoise} is bijective, we have the following
	\begin{align}
	|\mathcal{Y}(s_0,x_{1:n})|=| \mathcal{Z}(s_0,n)|. \label{yvsize}
	\end{align}

	For a given initial state $s_0\in\mathcal{S}$, define the binary indicator vector $ \zeta \in\{0,1\}^{|\mathcal{S}|} $ consisting of all zeros except for a 1 in the position corresponding to $s_0$; e.g. in Fig.\ref{fig:examp}, if starting from state $ S=0 $, then $\zeta  =[1, 0, 0]$. Observe that since each output of the finite-state additive channel triggers a different state transition, each sequence of state transitions has a one-to-one correspondence to the output sequence, given the input sequence.

	The total number of state trajectories after $n$-step starting from state $s_i$ is equal to sum of $i$-th row of $\mathcal{A}^n$ \cite{lind1995introduction}. Hence, because of a one-to-one correspondence between state sequences and output sequences then $|\mathcal{Z}(s_0,n)|=\zeta ^\top \mathcal{A}^n \mathbbm{1}$.

	Next, we show the upper and lower bounds in \eqref{outlam}. According to the Perron-Frobenius Theorem, for an irreducible $|\mathcal{S}|\times |\mathcal{S}|$ matrix $\mathcal{A} $ (or, equivalently, the adjacency matrix for a strongly connected graph), the entries of eigenvector $v \in \mathbb{R}^{|\mathcal{S}|}$ corresponding to $\lambda$ are strictly positive \cite[Thm. 8.8.1]{godsil2001strongly},\cite[Thm. 4.2.3]{lind1995introduction}. Therefore, multiplying $ \mathcal{A} $ by $ \mathcal{A} v=\lambda v $ results in $ \mathcal{A}^n v=\lambda^n v $ for $ n \in \mathbb{N} $.
	Left multiplication by the indicator vector, $ \zeta ^\top $ yields
	\begin{align}
	\zeta ^\top\mathcal{A}^n v = \lambda^n \zeta ^\top v. \label{eigv}
	\end{align}
	Denote minimum and maximum element of vector $ v $ by $ v_{min} $ and $ v_{max} $ respectively.	Hence, considering that all the elements in both sides of \eqref{eigv} are positive, we have
	\begin{align*}
	v_{min}\zeta ^\top\mathcal{A}^n \mathbbm{1}\leq \zeta ^\top\mathcal{A}^n v &\leq v_{max} \lambda^n \zeta ^\top \mathbbm{1} = v_{max} \lambda^n,
	\end{align*}
	where $ \mathbbm{1} $ is all-one column vector. Therefore, dividing by $v_{min}$, we have
	\begin{align}
	|\mathcal{Y}(s_0,x_{1:n})| =\zeta ^\top\mathcal{A}^n &\leq \frac{v_{max}}{v_{min}} \lambda^n = \beta \lambda^n, \label{out_up}
	\end{align}
	where $ \beta:= v_{max}/v_{min} > 0 $.	Moreover, for deriving the lower bound similar to above, we have
	\begin{align*}
	v_{min}\lambda^n \zeta ^\top \mathbbm{1}\leq \zeta ^\top\mathcal{A}^n v &\leq v_{max} \zeta ^\top\mathcal{A}^n \mathbbm{1}  =v_{max} |\mathcal{Y}(s_0,x_{1:n}) |.
	\end{align*}
	Let  $ \alpha:= v_{min}/v_{max}=1/\beta > 0 $, hence $\alpha \lambda^n \leq |\mathcal{Y}(s_0,x_{1:n}) |$ which combining it with \eqref{out_up} results in \eqref{outlam}.
\end{proof}
\subsection{Converse} \label{uppb}
We prove no coding method can do better than \eqref{c0f}.

Let $ m \in \mathcal{M} $ be the message to be sent and  $ y_{1:n} $ be the output sequence received such that
\begin{align*}
y_i=f_{m,i}(y_{1:i-1})\oplus z_i, \, i=1,\dots, n,
\end{align*}
where $ z_{1:n} \in \mathcal{Z}(s_0,n) \in \mathcal{X}^{n}$ is the additive noise and $ f_{m,i} $ the encoding function. Therefore, the output is a function of encoding function and noise sequence, i.e., $ y_{1:n}=\psi(f_{m,1:n},z_{1:n}) $.
We denote all possible outputs $ \Psi (\mathcal{F_{\mathcal{M}}},\mathcal{Z}(s_0,n))=\{y_{1:n}| m \in \mathcal{M}, z_{1:n} \in \mathcal{Z}(s_0,n) \} $, where $ \mathcal{F_{\mathcal{M}}}=\{f_{m,t}: m \in \mathcal{M}\} $ is the family of encoding functions.

For having a zero-error code any two $ m, m' \in \mathcal{M}, m\neq m'$ and any two $ z_{1:n}, z_{1:n}' \in \mathcal{Z}(s_0,n)$ must result in $ \psi(f_{m,1:n},z_{1:n})\neq \psi(f_{m',1:n},z_{1:n}') $. Note that when $ m = m' $, (even with feedback) at first position that $ z_{1:n} \neq z_{1:n}' $ will result in $ \psi(f_{m,1:n},z_{1:n})\neq \psi(f_{m,1:n},z_{1:n}') $. Therefore, assuming the initial condition is known at both encoder and decoder,
\begin{align*}
|\Psi (\mathcal{F_{\mathcal{M}}},\mathcal{Z}(s_0,n))| =M|\mathcal{Z}(s_0,n)| \leq q^n.
\end{align*}
Therefore, $ M $ is an upper bound on the number of messages that can be transmitted when initial condition is not available. We know that
$ \alpha \lambda^n| \leq |\mathcal{Z}(s_0,n)| \leq \beta \lambda^n $. Therefore,
\begin{align*}
C_{0f} \leq \sup_{f \in F_{\mathcal{M}}} \frac{\log M}{n}  &\leq \frac{1}{n} \log \frac{q^n}{\alpha \lambda^n} =\log q-\log \lambda -\frac{\log\alpha}{n}  .
\end{align*}
Moreover, $ \lim_{n \rightarrow \infty} \frac{1}{n} \log \alpha = 0 $, which proves the converse in \eqref{c0f}.
\subsection{Achievability} \label{downb}

A coding method is proposed that achieves \eqref{c0f}. Consider a code of length $ n $ such that first $ k<n $ symbols are the data to be transmitted and the rest of $ n-k $ symbols serve as parity check symbols.

We know that for an input of size $ k $ there are $ |\mathcal{Y}(k)|=|\mathcal{Z}(k)|=|\cup_{s_0} \mathcal{Z}(s_0,k)|$ possible output sequences, which is bounded as follows
\begin{align*}
\alpha \lambda^k \leq |\mathcal{Z}(s_0,k)| \leq |\mathcal{Y}(k)| \leq (|\mathcal{S}| \beta) \lambda^k.
\end{align*}
The transmitter having the output sequence $ y_{0:k-1} $, sends the receiver which output pattern (e.g. a message from $\{1,\dots, |\mathcal{Y}(k)|\} $ ) was received using the $ n-k $ parity check symbols. Assume that the transmitter sends the parity check symbols with a rate slightly below the zero-error feedback capacity, i.e., $ R=C_{0f}-\delta $, where $ \delta >0 $ is arbitrary small.\footnote{The reason to choose $ \delta $ is to deal with situation when $ C_{0f} $ is achieved when blocklength tends to infinity.}
Therefore, \[C_{0f}-\delta. = \frac{\log |\mathcal{Y}(k)|}{n-k}. \]

Using the upper bound on size of the output, i.e., $ |\mathcal{Y}(k)| \leq (|\mathcal{S}| \beta)\lambda^k $ and rearranging the inequality, gives
\begin{align*}
k &\geq \frac{(C_{0f}-\delta)n-\log(|\mathcal{S}|\beta)}{(C_{0f}-\delta +\log \lambda)}.
\end{align*}

Considering the fact that the total rate of coding is upper-bounded by $ C_{0f} $, we have
\begin{align*}
C_{0f} &\geq \frac{k}{n}\log q \geq \frac{C_{0f}-\delta-\frac{\log(|\mathcal{S}|\beta)}{n}}{C_{0f}-\delta +\log \lambda} \log q.
\end{align*}

Rearranging gives the following.
\begin{align*}
C_{0f} & \geq  \log q-\log \lambda  -\delta \bigg(1-\frac{1}{C_{0f}}\bigg)\log q -\frac{\log(|\mathcal{S}|\beta)}{nC_{0f}} \log q.
\end{align*}

By choosing $ \delta $ small and making $ n $ large, the last two terms disappear and this concludes the proof.

\section{Proof of the Zero-Error Capacity Lower Bound} \label{sec:proofl}
First, we give the following Lemma.
\begin{lem} \label{lemnss}
	Let $ \mathcal{G}(s_0,y_{1:n}) $ be subset of the inputs that can result in output $y_{1:n}$ with initial state $ s_0 $ for the finite-state additive noise channel. The following holds
	\begin{align}
	\alpha \lambda^n \leq |\mathcal{G}(s_0,y_{1:n})| \leq \beta \lambda^n,
	\end{align}
\end{lem}
where $ \alpha $ and $ \beta $ are constants appeared in \eqref{outlam}.
\begin{proof}
	The subset of the inputs that can result in output $y_{1:n}$ with initial state $ s_0 $, $ \mathcal{G}(s_0,y_{1:n}) $ is defined as the following
	\begin{align*}
	\mathcal{G}(s_0,y_{1:n})=\{ x_{1:n} |x_{1:n} \oplus z_{1:n} = y_{1:n}, z_{1:n} \in \mathcal{Z}(s_0,n)\}.
	\end{align*}
	Fixing $ y_{1:n} $, the mapping $x_{1:n} \to z_{1:n}$ in \eqref{adnoise} is bijective, hence $|\mathcal{G}(s_0,y_{1:n})|=| \mathcal{Z}(s_0,n)|$. Combining it with \eqref{yvsize} yields $ |\mathcal{G}(s_0,y_{1:n})|= |\mathcal{Y}(s_0,x_{1:n})| $. Moreover, Lemma \ref{lem:out} gives the bounds on $ |\mathcal{Y}(s_0,x_{1:n})| $.
\end{proof}
\begin{figure}[t]
	\centering
	\begin{tikzpicture}
	[->, auto, semithick, node distance=3.4cm]
	\tikzstyle{every state}=[fill=white,draw=black,thick,text=black,scale=1]
	\node[state]   (S1)       {$ S_i=0 $};
	\node[state]   (S2)[right of=S1]   {$ S_i=1 $};
	\path
	(S1) edge[out=160, in=200,looseness=5] node [left=0.1cm] {$ Z_i=0 $}(S1)
	edge[bend left] node [above] {$ Z_i=1 $}  (S2)
	(S2) edge[bend left]  node [below] {$ Z_i=0 $}  (S1);
	\end{tikzpicture}
	\caption{State transition diagram of a noise process in a channel at which no two consecutive errors can happen in the channel.}
	\label{fig:ex2stat}
\end{figure}
Let $ c(1) \in \mathcal{X}^n $ be the first codeword for which adjacent inputs denoted by $ \mathcal{Q}(c(1)) $. Again, each output sequence is in $\mathcal{Y}_T(c(1)):= \cup_{s_0 \in \mathcal{S}} \mathcal{Y}(s_0,c(1)) $. Hence,
\begin{align}
\mathcal{Q}(c(1))&=\bigcup_{y_{1:n} \in \mathcal{Y}_T(c(1)) } \mathcal{G}(y_{1:n}), \label{q3}
\end{align}
where, $ \mathcal{G}(y_{1:n}):=\bigcup_{s_0 \in \mathcal{S}} \mathcal{G}(s_0,y_{1:n}) $,
which gives
\begin{align*}
|\mathcal{Q}(c(1))|&\leq \sum_{y_{1:n} \in \mathcal{Y}_T(c(1))}\sum_{s_0 \in \mathcal{S}} |\mathcal{G}(s_0,y_{1:n})|.
\end{align*}
Using Lemma \ref{lemnss}, we have
\begin{align*}
|\mathcal{Q}(c(1))|&\leq|\cup_{s_0 \in \mathcal{S}} \mathcal{Y}(s_0,c(1))|(|\mathcal{S}| \times\beta \lambda^n).
\end{align*}
According to \eqref{outlam}, for any initial state the number of outputs is upper-bounded by $ \beta \lambda^n $. Therefore,
\begin{align*}
|\mathcal{Q}(c(1))|&\leq \big(|\mathcal{S}| (\beta \lambda^n) \big)\times(\beta|\mathcal{S}| \lambda^n) =\big( \beta|\mathcal{S}| \lambda^n \big)^2.
\end{align*}
By choosing non-adjacent inputs as the codebook, results in an error-free transmission. The above argument is true for other codewords, i.e.,
\begin{align*}
|\mathcal{Q}(c(i))|&\leq \big( \beta|\mathcal{S}| \lambda^n \big)^2, i \in \{1,\dots, M \},
\end{align*}
where $ M $ is the number of codewords in the codebook such that union of corresponding $\mathcal{Q}(c(i))$ for $i=1,\dots,M,$ covers $ \mathcal{X}^n $. Then,
\begin{align*}
q^n = |\bigcup_{i=1}^M \mathcal{Q} (c(i))| &\leq \sum_{i=1}^{M} |\mathcal{Q} (c(i))|\leq M 	\times \big( \beta|\mathcal{S}| \lambda^n \big)^2.
\end{align*}
A a result, the number of distinguishable inputs is lower bounded by $M \geq q^n/( \beta|\mathcal{S}| \lambda^n )^2$.
Therefore, according to zero-error capacity definition
\begin{align*}
C_0&\geq \log \frac{q}{(\beta |\mathcal{S}|)^2 (\lambda)^{2n}} =\log q-2\log \lambda - \frac{2}{n} \log (\beta |\mathcal{S}|).
\end{align*}
If $n$ is large, the last term vanishes and proves the lower bound in \eqref{c0l}.
\section{Examples} \label{sec:examps}
Here, we provide some examples, and for them, compute $ C_{0f} $ explicitly. Examples \ref{2stat} and \ref{3stat} consider channels with isolated and limited runs of errors. In Example \ref{estat} we consider a Gilbert-Elliot channel. Moreover, for examples \ref{2stat} and \ref{3stat}, we investigate that minimum value of ordinary feedback capacity $ C_f $ over the transition probabilities and observe how far is this natural upper bound from the zero-error feedback capacity.\smallskip

\begin{figure}[t]
	\centering
	\begin{tikzpicture}
	[->, >=stealth, auto, semithick, node distance=3.4cm]
	\tikzstyle{every state}=[fill=white,draw=black,thick,text=black,scale=1]
	\node[state] (A1)   {$ S_i=0 $};
	\node[] (state0)[below=0.1cm of A1] {$ Z_i=0 $};
	\node[state]   (A2)[right of=A1]   {$S_i=1 $};
	\node[] (state1)[below=0.1cm of A2] {$  Z_i \in \{0,1\} $};
	\path
	(A1) edge[out=160, in=200,looseness=5] node [left] {$ 1-p $} (A1)
	edge [bend left] node [above] {$ p $}  (A2)
	(A2) edge[bend left]  node [below] {$ 1$}  (A1);
\end{tikzpicture}
\caption{Markov chain for channel states in Example \ref{estat}.}
\label{fig:estat}
\end{figure}

\begin{ex}\label{2stat}
	Consider a channel with no two consecutive errors (Fig.~\ref{fig:ex2stat}). If $ q = 2 $ then $ C_0=C_{0f}=0 $. Whilst, if $ q \geq 3 $ it has a zero-error feedback capacity of $ C_{0f}=\log q-\log(\frac{1+\sqrt{5}}{2}) $ bit/use where $ \frac{1+\sqrt{5}}{2} $ is known as the golden ratio.

	Moreover, assuming Markovianity with the transition probability $ P(S_{i+1}=1|S_i=0)=p $, the ordinary feedback capacity is $ C_f (p)= \log q-\frac{H(p)}{1+p}$ from \eqref{ccf}, where $ H(.) $ is the binary entropy function. It turns out that
	$ C_{0f}= \min_{p\in (0,1)} C_f(p) $.
\end{ex} \smallskip

\begin{ex}\label{3stat}
	 The example of Fig.~\ref{fig:examp} represents a channel with no more than two consecutive errors, having adjacency matrix
\begin{align*}
\mathcal{A}=\begin{bmatrix}
1&1&0\\
1&0&1\\
1&0&0
\end{bmatrix}.
\end{align*}
	 If $ q = 2 $ then $ C_0=C_{0f}=0 $ and if $ q =3 $ it has $ C_{0f} = 0.7058$.

	 If the channel states are Markov with transition probabilities $ P(S_{i+1}=1|S_i=0)=p $ and $ P(S_{i+1}=2|S_i=1)=r $, it can be shown that\\ $ \min_{p,r\in (0,1)}C_f (p,r)= 0.7935 > C_{0f} $.
\end{ex}\smallskip

\begin{ex}\label{estat} Consider a Gilbert-Elliot channel with input alphabet of size $ q=5 $ and two states (Fig.~\ref{fig:estat}). When the state $ S_i=0 $ the channel is error-free, i.e., $ P(Z_i\neq 0|S_i=0)= 0 $ and when state $ S_i=1 $ it acts like a noisy type-writer channel (Fig.~\ref{fig:pen}) which is also known as the Pentagon channel \cite{shannon1956zero}. In this state, the probability of error for any input symbol is $ P(Z_i=1|S_i=1)= r $ and thus the probability of error-free transmission is $ P(Z_i=0|S_i=1)=1-r $. Figure~\ref{fig:estat} shows this channel's state transition diagram. However, this channel does not fit Definition \ref{def:fanchannel}, because outgoing edges are not associated with unique noise values. This reflects the fact that the noise process is a hidden Markov model, not a Markov chain, and the same state sequence can yield multiple noise sequences.
\end{ex}
Nonetheless, in the following we show an equivalent representation of this channel compatible with Definition \ref{def:fanchannel}. The resultant model (shown in Fig.~\ref{fig:eq2}) is a state machine that produces the same set of noise sequences, where the edges define the noise values in each transmission.
\begin{figure}
	\centering
	\begin{tikzpicture}[->, >=stealth, auto, semithick, node distance=1cm]
	\tikzstyle{every state}=[fill=white,thick,text=black,scale=1]
	\node[]    (S1)  				{0};
	\node[]    (S2)[below of=S1]   {1};
	\node[]    (S3)[below of=S2]   {2};
	\node[]    (S4)[below of=S3]   {3};
	\node[]    (S5)[below of=S4]   {4};
	\node[]    (S6)[right of=S1,right=2cm]   {0};
	\node[]    (S7)[below of=S6]   {1};
	\node[]    (S8)[below of=S7]   {2};
	\node[]    (S9)[below of=S8]   {3};
	\node[]    (S10)[below of=S9]   {4};

	\path
	(S1.0) edge   (S6)
	edge    (S7.180)
	(S2.0) edge  (S7)
	edge  (S8.180)
	(S3.0) edge   (S8)
	edge    (S9.180)
	(S4.0) edge  (S9)
	edge  (S10.180)
	(S5.0) edge   (S10)
	edge    (S6.180);
	\end{tikzpicture}
	\caption{Pentagon channel.}
	\label{fig:pen}
\end{figure}
Note that if the channel is in state $ S_i=0 $, the noise can only take value $ Z_i=0 $, but in state $ S_i=1 $, the noise $ Z_i\in \{0,1\} $, thus $ Z_i\in \{0,1\} $ at all times. In the sequel, we show that
\begin{align}
P(Z_{i+1}=1|Z_i=1,z_{1:i-1})&=0,\label{zz11}\\
P(Z_{i+1}=0|Z_i=0,z_{1:i-1})&>0,\label{zz00}\\
P(Z_{i+1}=1|Z_i=0,z_{1:i-1})&>0,\label{zz10}
\end{align}
whenever the conditioning sequence of $ Z_i=j,Z_{1:i-1}=z_{1:i-1}, j\in \{0,1\} $ occurs with non-zero probability. Therefore, irrespective of past noises the state machine shown in Fig.~\ref{fig:eq2} can produce all noise sequences that occur with nonzero probability. It should be stressed that this noise process may not be a stochastic Markov chain, however, it is a topological Markov chain \cite[Ch.2]{lind1995introduction}.
First, note by inspection of Fig.~\ref{fig:estat} that the noise process has zero probability of taking value $ 1 $ twice in a row. Thus
$ P(Z_{i+1}=1, Z_i =1, z_{1:i-1}) = 0 $.
Using Bayes rule, it then follows that
\begin{align*}
P(Z_{i+1}=1|Z_i=1,z_{1:i-1}) &=0,
\end{align*}
whenever $ P(Z_i=1, z_{1:i-1}) >0 $.

Next we show \eqref{zz00}-\eqref{zz10}. Let $z_{1:i-1}$ be any past noise sequence such that $P(Z_i=0, z_{1:i-1}) >0$.Therefore, $\exists s_{1:i} $ such that
\begin{align}
P(Z_i=0,z_{1:i-1},s_{1:i}) &=P(Z_i=0|s_i)P(z_{1:i-1},s_{1:i})>0.\label{con0}
\end{align}
From Fig.~\ref{fig:estat}, $ P(Z_{i+1}=0,Z_i=0|s_i=j)>0, j\in \{0,1\} $. Thus
\begin{align*}
P(Z_{i+1}=0,Z_i=0,z_{1:i-1},s_{1:i})&=P(Z_{i+1}=0,Z_i=0|s_i)P(z_{1:i-1},s_{1:i})>0,
\end{align*}
since the second factor on the RHS is positive, by \eqref{con0}. Therefore, $ P(Z_{i+1}=1, Z_i=0, z_{1:i-1}) > 0 $, and \eqref{zz00} holds. Now, we show \eqref{zz10}. If $ S_i=0 $, it can be shown from Fig.~\ref{fig:estat} and the noise probabilities that
\begin{align}
P(Z_{i+1}=1,Z_i=0|S_i=0)&=rp>0. \label{z10rp}
\end{align}
Therefore,
\begin{align*}
P(Z_{i+1}=1,Z_i=0,z_{1:i-1}) &\geq P(Z_{i+1}=1,Z_i=0,z_{1:i-1},S_i=0, s_{1:i-1})\\
&=P(Z_{i+1}=1,Z_i=0|S_i=0)P(S_i=0,z_{1:i-1},s_{1:i-1})\\
&=rp\,P(S_i=0,z_{1:i-1},s_{1:i-1})>0.
\end{align*}
Note from Fig.~\ref{fig:estat} that $ P(S_i=0|s_{i-1})>0 $. Thus,
\begin{align*}
P(S_i=0,z_{1:i-1},s_{1:i-1})&=P(S_i=0|s_{i-1})P(z_{1:i-1},s_{1:i-1})>0.
\end{align*}
Consequently, \eqref{zz11}-\eqref{zz10} hold yielding the state machine in Fig.~\ref{fig:eq2}. Note that, $ \hat{S}_i=0 $ corresponds to $ Z_i=0 $ and  $ \hat{S}_i=1 $, to $ Z_i=1 $.

\begin{figure}[t]
	\centering
	\begin{tikzpicture}
	[->, auto, semithick, node distance=3.4cm]
	\tikzstyle{every state}=[fill=white,draw=black,thick,text=black,scale=1]
	\node[state]   (S1)       {$ \hat{S}_i=0 $};
	\node[state]   (S2)[right of=S1]   {$ \hat{S}_i=1 $};
	\path
	(S1) edge[out=160, in=200,looseness=5] node [left=0.1cm] {$ Z_{i}=0 $} (S1)
	edge[bend left]  node [above] {$ Z_{i}=1 $}  (S2)
	(S2) edge[bend left]  node [below] {$Z_{i}=0 $}  (S1);
	\end{tikzpicture}
	\caption{State machine generating the noise sequence of Example \ref{estat}.}
	\label{fig:eq2}
\end{figure}
Now, we can use the results of Theorem \ref{thm:zero-error}, to get
 \[ \log5-2\log\bigg(\frac{1+\sqrt{5}}{2}\bigg) \leq C_0 \leq C_{0f} = \log5-\log\bigg(\frac{1+\sqrt{5}}{2}\bigg). \]
 This shows that the zero-error feedback capacity of some channels with different structure than Definition \ref{def:fanchannel}, such as time-varying state transmissions (non-homogeneous Markov chains) and even transitions that depend on previous transmissions can be explicitly obtained.
	\section{Conclusion} \label{sec:conclusions}
	We introduced a formula for computing the zero-error feedback capacity for a class of additive noise channels without state information at the decoder and encoder. This reveals a close connection between the topological entropy of the underlying noise process and the zero-error communication.
	Moreover, a lower bound on zero-error capacity (without feedback) was given based on the topological entropy.

	Future work includes extending these results to a more general class of channels.
\end{spacing}
\bibliographystyle{IEEEtran}
\bibliography{ieeetranb}
\end{document}


TITLE: First Order Logic : Predicates
QUESTION [1 upvotes]: I have a small problem with the first order logic, in particular, predicate logic
Let us take this sentence as an example:
Each teacher has given a form to each student.

From this sentence, can we have different reading?
This is my try to solve such problem, I did not know if this is the answer for such question:
Every Teacher has given a form to each Student.

(∀x)Teacher(x)^(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

If X is a Student then he has received a form from a teacher

Student(x)→(∃y)  Teacher(y)^(∃z)Form(z)^Give(x,y,z)

If X is a Teacher then he has gave a from for all his students

Teacher(x)→(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

If X is a form then a teacher gave it to all student.

Form(x)→(∀y)  Employer(y)^(∃z)Teacher(z)^Give(x,y,z)

REPLY [1 votes]: The sentence:

Each teacher has given a form to each student.

does indeed have some multiple readings, but not all of the ones you propose:

Every Teacher has given a form to each Student.
(∀x)Teacher(x)^(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

I would say that this is the 'default' reading of the sentence, i.e. the one that is probably meant. Please note though that you should symbolize this as:
$$\forall x (Teacher(x) \to \forall y  (Student(y) \to \exists z (Form(z) \land Give(x,y,z))))$$
In other words: you needed to use $\to$ instead of $\land$ in a few places (because of the $\forall$), and you needed to add parentheses to indicate the scope of the quantifiers.

If X is a Student then he has received a form from a teacher
Student(x)→(∃y)  Teacher(y)^(∃z)Form(z)^Give(x,y,z)

This is not a good reading of the English sentence, since it does not specify that each teacher has given a form.

If X is a Teacher then he has gave a from for all his students
Teacher(x)→(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

This statement requires $x$ to be quantified, and once you add the (universal, since it says each) quantifier, it is of course just the same sentence as the first one (of course, you also need to make the corrections I indicated earlier)

If X is a form then a teacher gave it to all student.
Form(x)→(∀y)  Employer(y)^(∃z)Teacher(z)^Give(x,y,z)

.. I am not sure why you use 'Employer' as a predicate here instead of 'Student'., but more importantly, your reading is not a viable reading of the original sentence, since this reading states that all forms are given to students, but the original sentence makes no such claim. If not all forms are given to students, the original sentence can still be true, as long as each student receives some form.
A reading that is a viable alternative, is to interpret the original sentence as saying that it is the same form that each teacher has given to each student, which would be:
$$\exists z (Form(z) \land \forall x (Teacher(x) \to \forall y  (Student(y) \to Give(x,y,z))))$$
And a third one would be kind of 'in between' the first and this last one:  the form that each teacher hands to their students is the same one for that teacher, but different teachers may end up giving a different form:
$$\forall x (Teacher(x) \to \exists z (Form(z) \land \forall y  (Student(y) \to Give(x,y,z))))$$


TITLE: Natural Deduction and Identity
QUESTION [4 upvotes]: In Logic and Structure, p. 99, Van Dalen gives a brief summary of the rules for predicate logic involving identity. Now, I would like to think of myself as quite proficient in terms of constructing tree proofs, both in propositional logic and predicate logic as well. However, for some reason (most probably due to lack of exposure), I find the introduction of identity somewhat difficult to handle. For instance, consider the following problem (which is not in the book):

Derive in natural deduction, without any undischarged assumptions, the following formula: $$\exists x_{0} \forall x_{1} (x_{0} \dot{=}x_{1})  \to \forall x_{0} \forall x_{1} (x_{0} \dot{=}x_{1})$$

Now, if I would want to construct a proof tree of this, then I reckon by its form that the last rule should be $\to I$ and the rule above $\forall I$. However, once we reach this step I go completely blank. A part of me wants to use the $\exists E$, take $\exists x_{0} \forall x_{1} (x_{0}\dot{=}x_{1})$ as the main premise and derive $\forall x_{1}(x_{0} \dot{=} x_{1})$. But, another part simply says this reasoning would not be valid. Could anyone help me out, by explaining this example and/or provide more information about how one should approach derivations involving identity in general.

REPLY [3 votes]: Let's think through a proof (I'll use $x$ and $y$ rather than $x_0$ and $x_1$ for ease of typing and readability)!
We need to prove a conditional proposition. So, as typical in an ND system, we assume the antecedent and aim to derive the consequent, then use CP (conditional proof) to discharge the antecedent and infer the desired conditional. What else could we do?? So the proof should have the shape:

$\quad\quad|\quad \exists x\forall y\, x = y\\
\quad\quad|\quad\ldots\\
\quad\quad|\quad\forall x\forall y\, x = y\\
\exists x\forall y\, x = y\ \to\ \forall x\forall y\, x = y\quad\quad\quad\text{By Conditional Proof}$

And now there's only one way to use an existential assumption $\exists x\varphi(x)$ if that's all we've got to work with ... We temporarily assume $\varphi(a)$ for some new name $a$, and derive some conclusion $C$ which doesn't involve $a$. Then we can use the original existential assumption  and discharge the temporary assumption to derive $C$. So the proof has to go:

$\quad\quad|\quad \exists x\forall y\, x = y\\
\quad\quad|\quad\quad|\quad \forall y\, a = y\\
\quad\quad|\quad\quad|\quad\ldots\\
\quad\quad|\quad\quad|\quad\forall x\forall y\, x = y\\
\quad\quad|\quad\forall x\forall y\, x = y\quad\quad\quad\quad\quad\quad\text{By EE}\\
\exists x\forall y\, x = y\ \to\ \forall x\forall y\, x = y$

So far, so automatic, yes???
What now? We obviously have to use the universal. So let's instantiate with an new name: to get

$\quad\quad|\quad \exists x\forall y\, x = y\\
\quad\quad|\quad\quad|\quad \forall y\, a = y\\
\quad\quad|\quad\quad|\quad a = b\\
\quad\quad|\quad\quad|\quad\ldots\\
\quad\quad|\quad\quad|\quad\forall x\forall y\, x = y\\
\quad\quad|\quad\forall x\forall y\, x = y\\
\exists x\forall y\, x = y\ \to\ \forall x\forall y\, x = y$

But we can't get from that alone to the desired doubly quantified conclusion, because we can't generalize on $a$. [MAJOR REALITY CHECK: why can't we generalize on $a$?? If you don't understand that, you need to revise the ND rules for the quantifiers!!!] But we need two names we can generalize on get to the desired conclusion. Ok .... well, nothing stops us introducing another one using our temporary assumption at line 2: so we have

$\quad\quad|\quad \exists x\forall y\, x = y\\
\quad\quad|\quad\quad|\quad \forall y\, a = y\\
\quad\quad|\quad\quad|\quad a = b\\
\quad\quad|\quad\quad|\quad a = c\\
\quad\quad|\quad\quad|\quad\ldots\\
\quad\quad|\quad\quad|\quad\forall x\forall y\, x = y\\
\quad\quad|\quad\forall x\forall y\, x = y\\
\exists x\forall y\, x = y\ \to\ \forall x\forall y\, x = y$

Ah hah! Now if should be obvious how to proceed ....

$\quad\quad|\quad \exists x\forall y\, x = y\\
\quad\quad|\quad\quad|\quad \forall y\, a = y\\
\quad\quad|\quad\quad|\quad a = b\\
\quad\quad|\quad\quad|\quad a = c\\
\quad\quad|\quad\quad|\quad b = c \quad\quad\quad\quad\quad \text{By Leibniz's Law}\\
\quad\quad|\quad\quad|\quad \forall y\, b = y \quad\quad\quad\quad \text{By Univ. quantifier introduction}\\
\quad\quad|\quad\quad|\quad\forall x\forall y\, x = y\quad\quad\quad \text{By Univ. quantifier introduction again}\\
\quad\quad|\quad\forall x\forall y\, x = y\\
\exists x\forall y\, x = y\ \to\ \forall x\forall y\, x = y$

Just ensure you really understand the use of the quantifier rules here, and why the applications of the universal quantifier introduction moves are legitimate.


TITLE: Set of idempotent elements closed under addition: prove $a+a = 0, ab=ba$
QUESTION [1 upvotes]: The statement of the problem:
If $R$ is a ring and $a \in R$, $a$ is idempotent if $a^2 = a$. If the set of all idempotent elements of $R$ is closed under addition, prove that for any $x, y \in R$ we have $x+x = 0, \space xy = yx$. Hint: start with $(x+x)^2$ and $(x+y)^2$.
What's confusing me here is that the statement seems wrong, as I have no idea how to use the fact that the idempotent elements are closed under addition  to prove $x+x = 0$ or $xy = yx$ for any $x, y \in R$, but I can't seem to think of a counterexample. The only example where the set of idempotent elements is closed under addition that I could think of is $\mathbb{Z}_{2}$, and the statement indeed holds for that ring. Is there a way to connect an arbitrary element of a ring with the idempotent ones, or is the statement of the problem wrong?
P.S. The statement is easy to prove if we add the requirement that $x, y$ are themselves idempotent: $(x+x)^2 = 4x^2 = 4x$, and since $x + x$ is also idempotent, $(x+x)^2 = x+x =2x$, so $4x = 2x$, so $x+x+x+x=x+x$, so $x+x=0$.
On the other hand, $(x+y)^2 = x + y = x^2+y^2+xy+yx=x+y+xy+yx$, so $xy+yx=0$, and I get stuck here again because $xy = -yx$, which isn't the same as $xy = yx$.

REPLY [3 votes]: The observation of the characteristic being $2$ is already well covered by Hagen von Eitzen's solution. This is to address the claim that the ring is also commutative.

What's confusing me here is that the statement seems wrong, as I have no idea how to use the fact that the idempotent elements are closed under addition  to prove $x+x = 0$ or $xy = yx$ for any $x, y \in R$, but I can't seem to think of a counterexample.

I think you're right to feel that way.
Consider the free $F_2$ algebra (where $F_2$ is the field of two elements) $F_2\langle x,y\rangle$. Keep in mind that $x$ and $y$ are two indeterminates that do not commute.
We'll say that the "degree" of a polynomial in this algebra is the largest total of exponents of a monomial with nonzero coefficient. So, for example, the degree of $xyxy+x^2y^2x$ is $5$. Clearly if $a,b$ are in the algebra and $deg(b)>0$, then $deg(ab)>deg(a)$. Using this observation, we can see that the idempotents have to have degree $0$, and so the only ones are $\{0,1\}$. (Alternatively, this ring is a domain, so the only idempotents are $\{0,1\}$.)
However, this algebra is not commutative.


TITLE: Rationalizing the denominator of $\frac {\sqrt{10}}{\sqrt{5} -2}$
QUESTION [2 upvotes]: I have the expression
$$\frac {\sqrt{10}}{\sqrt{5} -2}$$
I can't figure out what to do from here, I can't seem to pull any numbers out of either of the square roots so it appears that it must remain as is.

REPLY [3 votes]: To rationalize the denominator i. e. turn the denominator rational multiply both numerator and denominator by
the conjugate of the denominator $-\sqrt{5}-2$ or its symmetric  $\sqrt{5}+2$, expand both and
simplify
$$\begin{eqnarray*}
\frac{\sqrt{10}}{\sqrt{5}-2} &=&\frac{\sqrt{10}\left( \sqrt{5}+2\right) }{
\left( \sqrt{5}-2\right) \left( \sqrt{5}+2\right) }=\frac{\sqrt{10}\sqrt{5}+\sqrt{10}\times 2}{\left( \sqrt{5}\right) ^{2}-2^{2}} \\
&=&\frac{\sqrt{50}+2\sqrt{10}}{5-4}=\frac{\sqrt{50}+2\sqrt{10}}{1}=\sqrt{50}%
+2\sqrt{10}.
\end{eqnarray*}.
$$
In general [Edited to correct] $$\frac{1}{a+\sqrt{b}}=\frac{a-\sqrt{b}}{\left( a+\sqrt{b}\right)
\left( a-\sqrt{b}\right) }=\frac{a-\sqrt{b}}{a^{2}-b}.$$


TITLE: Cohomology of an orbit space
QUESTION [5 upvotes]: Let $T^n = (S^1)^n$ be the $n$-torus and $G = (\mathbb{Z}_2)^n$ be product of $n$ copies of the group of order $2$. Consider the action of $G$ on $T^n$ induced by the antipodal action componentwise.
Computing the cohomology $H^*(T^n/G;\mathbb{Z}_2)$, I am tempted to say that $T^n/G \cong (S^1/\mathbb{Z}_2)^n$ since the action happens componentwise, but I am not sure if that is correct. Also, I am trying to avoid a Spectral sequences argument, but if there is a solution in that way will be useful for future computations.

REPLY [3 votes]: Your temptation is correct.  If two elements of $T^n$ are related by an element of $G$, that just means that on each coordinate they are related by an element of $\mathbb{Z}_2$.  So an orbit of $G$ consists of just a product of orbits of $\mathbb{Z}_2$ on each component.  This gives a bijection $f:T^n/G\to (S^1/\mathbb{Z}_2)^n$ which is easily seen to be continuous using the universal property of $T^n/G$.  Since $T^n/G$ is compact and $(S^1/\mathbb{Z}_2)^n$ is Hausdorff, you can conclude that $f$ is a homeomorphism.
Since $S^1/\mathbb{Z}_2\cong S^1$, this means that $T^n/G\cong T^n$, so you are just taking the cohomology of $T^n$.


TITLE: Equation with absolute value and parameter
QUESTION [1 upvotes]: How to solve this equation over real numbers with parameter $p \in \Bbb R$?
$$(1 - p)(\left\lvert x + 2 \right\rvert + \left\lvert x \right\rvert) = 4 - 3p$$
I know how to solve absolute value equations without parameter.

REPLY [3 votes]: We have
$$|x|+|x+2|=\frac{4-3p}{1-p}\tag1$$
Case 1 : For $x\gt 0$,
$$(1)\iff x+(x+2)=\frac{4-3p}{1-p}\iff x=\frac{2-p}{2(1-p)}$$
Here, $\frac{2-p}{2(1-p)}\gt 0\iff p\lt 1\quad\text{or}\quad p\gt 2$.
Case 2 : For $-2\lt x\le 0$,
$$(1)\iff -x+(x+2)=\frac{4-3p}{1-p}\iff p=2$$
Case 3 : For $x\le -2$,
$$(1)\iff -x-(x+2)=\frac{4-3p}{1-p}\iff x=\frac{6-5p}{2(p-1)}$$
Here, $\frac{6-5p}{2(p-1)}\le -2\iff p\lt 1\quad\text{or}\quad p\ge 2$.
So, the answer is the followings :

For $p\lt 1\ \text{or}\ p\gt 2$, $x=\frac{2-p}{2(1-p)},\frac{6-5p}{2(p-1)}$.
For $p=2$, $-2\le x\le 0$.
For $1\le p\lt 2$, there is no such $x$.


TITLE: Given a knight on an infinite chess board that moves randomly, what's the expected number of distinct squares it reaches in 50 moves?
QUESTION [9 upvotes]: I was asked this in an interview and wasn't sure how to frame the answer. Basically as in the question you have a knight on an infinite chess board and it chooses one of its valid 8 moves uniformly at each move. After 50 moves, the question was to give (as tight as possible) a lower and upper bound on the expected number of distinct squares it reached.
I got as far as realizing that the knight must live in a 200x200 square, and that it can only reach half of the squares (since it must end at the same colour as it started). However this doesn't really address the randomness aspect of the question.

REPLY [3 votes]: An exact solution can be acquired by computing $d_{x, y}(n)$ which is the number of distinct paths reaching $(x, y)$ for the first time after $n$ steps. The total number of paths $p_{x,y}(n)$ which contains $(x, y)$ after $n$ steps then has relationship:
$$p_{x, y}(n) = 8p_{x, y}(n-1) + d_{x, y}(n)$$
Using this we can express the expected number of distinct squares per path after $n$ steps, as counting the total number of distinct squares for each path and the total number of distinct paths crossing a square is equivalent when summing over all paths or all squares.
Then, saving some computation time we find by four-fold rotational symmetry that the expected number of distinct squares per path after $n$ steps is equivalent to:
$$1 + \frac{4}{8^{n}}\sum_{(x > 0, y \geq 0)} p_{x, y}(n)$$
How do we compute $d_{x, y}(n)$? We do it using matrices $M_{x, y}(n)$ which are initially zero everywhere except at $(0, 0)$ where they have value $1$. Then we apply a kernel convolution encoding the possible knight moves:
$$M'_{x, y}(n)=\begin{bmatrix}0&1&0&1&0\\
1&0&0&0&1\\
0&0&0&0&0\\
1&0&0&0&1\\
0&1&0&1&0\\\end{bmatrix}\star M_{x, y}(n-1)$$
Then $d_{x, y}(n)$ is the element at $(x, y)$ in $M'_{x, y}(n)$, and we set $(x, y)$ in the above matrix to zero to get $M_{x, y}(n)$ for future computation. Because we repeatedly set that coefficient to zero after each iteration it is that we count the number of distinct paths reaching $(x, y)$ for the first time, rather than all the paths that reach $(x, y)$ after $n$ steps. Unfortunately this does mean that for all possible $(x, y)$ we must compute these matrices a total of $n$ times.
I've implemented the above in Rust:
use gmp::mpz::Mpz;
use gmp::mpq::Mpq;
use rayon::prelude::*;

fn knight_step(d: Vec<Mpz>, w: i32) -> Vec<Mpz> {
    let mut nd = vec![Mpz::new(); (w*w) as usize];
    for &(dx, dy) in &[(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)] {
        let rx = (-dx).max(0)..(w-dx).min(w);
        let ry = (-dy).max(0)..(w-dy).min(w);
        for x in rx {
            for y in ry.clone() {
                let cx = x + dx;
                let cy = y + dy;
                nd[(x*w + y) as usize] += &d[(cx*w + cy) as usize];
            }
        }
    }

    nd
}

fn count_distinct(n: usize) -> Mpz {
    let w = 4*n + 1; // Size of a side of the board.
    let z = 2*n; // Origin is at (z, z);

    let mut total_distinct = Mpz::new();
    for x in z+1..w {
        println!("{}", x);
        let subproblems: Vec<_> = (z..w).collect::<Vec<usize>>().par_iter().map(|y| {
            let mut d = vec![Mpz::new(); w*w];
            d[z*w + z] = Mpz::from(1);
            let mut p = Mpz::new();

            for _ in 0..n {
                d = knight_step(d, w as i32);
                p = 8i64*p + &d[x*w + y];
                d[x*w + y] = 0.into();
            }

            p
        }).collect();

        for s in &subproblems {
            total_distinct += 4i64*s;
        }
    }

    total_distinct
}

fn main() {
    let n = 50;
    let q = Mpq::ratio(&count_distinct(n), &Mpz::from(8).pow(n as u32));
    println!("{}", q + &1.into());
}

Giving the exact result:
$$\frac{455207943209697100946821497094086408107332219}{11150372599265311570767859136324180752990208} \approx 40.82446$$


TITLE: Why does normal distribution have the same shape regardless of its parameters?
QUESTION [1 upvotes]: The formula for normal distribution is quite complicated, it has $\sigma$ in the exponent and in denominator. And no matter what $\sigma$ is, the shape of its pdf is the same (i.e. for example 3 standard deviations lie on the same point of the graph, no matter what $\sigma$ we choose). Could anyone explain how is that possible?
I guess that's why we can use things such as Z-score - the shape is universal, and thus probability as well. We only calculate the distance from the mean expressed in standard deviations.
http://en.wikipedia.org/wiki/68%E2%80%9395%E2%80%9399.7_rule
http://en.wikipedia.org/wiki/Normal_distribution

REPLY [0 votes]: Normal distribution two parameters Mean and Standard Deviation do effect Normal distribution.
Mean
Mean will shift the Normal distribution forward or backward on it's axis.
Mean will not distort shape of Normal Distribution
Standard Deviation
Standard Deviation does effect shape A large Standard Deviation mean that normal distribution will approach to less peakedness and more tailedness and a low standard deviation will clutter values around Mean and normal distribution will have large peak.
Theoretically speaking Mount Everest the world tallest Mountain of the world if assumed to be like Normal distribution has low standard deviation.


TITLE: How to calculate $\operatorname{Spec} \mathbb{C}[x,y]/(y^2-x^3)$
QUESTION [1 upvotes]: Is there a general  method for calculating things like
$\operatorname{Spec} \mathbb{C}[x,y]/I$ ?
Maximal ideals are
$ \{(x-\tilde{a},y-\tilde{b}): b^2-a^3=0\}$
because of
$f(x,y)(x-a)+g(x,y)(x-b)=y^2-x^3$ evaluated in $x=a$ and $y=b$.
 But how to calculate non-maximal ideals?

REPLY [2 votes]: Just a hint. $\operatorname{Spec}\mathbb{C}[x,y]/I$ is in bijection with the set of all primes $p$ in $\mathbb{C}[x,y]$ such that $I(=(y^{2}-x^{3}))\subseteq p$. Now, can you describe what are the elements of $\operatorname{Spec}\mathbb{C}[x,y]$? (Hint: you have the zero ideal and the maximal ideals in that spectrum and certainly all the principal ideals generated by an irreducible polynomial in $\mathbb{C}[x,y]$. Prove that these exhaust all the possibilities).


TITLE: Probability of convergence of $\int_{1}^{\infty} \frac{B_s}{s^{3/2}} \, \mathrm d s$
QUESTION [4 upvotes]: I'm trying to find out whether the integral $$\int_{1}^{\infty} \frac{B_s}{s^{3/2}} \, \mathrm d s,$$ where $B_s$ is a standard Brownian motion, converges with non-zero probability/almost surely as an improper integral. In the Lebesgue sense, this definitely diverges with nonzero probability (and I'd guess almost surely), because $\Bbb E[|B_t|] = \sqrt{\frac{2t}{\pi}}$. In the improper/Riemann-sense, it's not quite clear to me though, since I'd think one gets something akin of an alternating sequence, and since the law of the iterated logarithm makes $\frac{B_s}{s^{1/2+\varepsilon}}$ vanish.
Thanks!
Edit: With a substitution $t = \frac{1}{s}$ I get $$\int_{1}^{\infty} \frac{B_s}{s^{3/2}} \, \mathrm d s = \int_0^1 \frac{1}{t^{3/2}} t B_{1/t} \, \mathrm d t \overset{d}{=} \int_0^1  \frac{1}{t^{3/2}}\tilde B_t \, \mathrm dt,$$ where $\tilde B_t$ is a Brownian motion as well, by the time inversion identity. This looks more like a divergent integral to me, but this must have infinitely many zeros as well in the interval $[0,1]$ so I can't conclude that this is not convergent alternating series.
Edit2: The convergence set of the integral $\int_0^1  \frac{1}{t^{3/2}}\tilde B_t \, \mathrm dt$ should be measurable with respect to the germ-sigma-algebra $\mathcal F_0^+$, I think, and thus have measure $0$ or $1$ by Blumenthal's 0-1-law.

REPLY [1 votes]: Denote
\begin{gather*}
 I(t)=\int_1^t \frac{B_s}{s^{3/2}}\,\mathrm{d}s,\\
 C=\Big\{ \omega: -\infty<\varliminf_{t\to\infty} I(t)=\varlimsup_{t\to\infty} I(t) <\infty \Big\}, \tag{1}
\end{gather*}
The $ \mathsf{P}(C)=0 $ will be proved as follows.
Let
\begin{equation*}
 Y_n=I(4^{n+1})-I(4^n)=\int_{4^n}^{4^{n+1}} \frac{B_s}{s^{3/2}}\,\mathrm{d}s, \quad n\ge  0,
\end{equation*}
then $ \{Y_n, n\ge0 \}$ are Gaussian distributed with
\begin{equation*}
 \mathsf{E}[Y_n]=0,\qquad \mathsf{var}[Y_n] =\log4-1 \stackrel{\triangle}{=}\sigma_0^2 ,
 \qquad n\ge 0.
\end{equation*}
Taking $ a=\sigma_0\sqrt{\pi/8}(>0) $, then
\begin{align*}
 \mathsf{P}(|Y_n|<a)&=\sqrt{\dfrac{2}{\pi}}\int_{0}^{a/{\sigma_0}}e^{-x^2/2}\,\mathrm{d}x
 \le \sqrt{\dfrac{2}{\pi}}\frac{a}{\sigma_0}=\frac12,\\
 \mathsf{P}(|Y_n|\ge a)&=\frac12.\qquad n\ge 0
\end{align*}
Furthermore,
\begin{align*}
  \mathsf{P}(\varlimsup_{n\to\infty} |Y_n|\ge a)
  &\ge \mathsf{P}( \{\omega:|Y_n|\ge a\} \; \text{i.o.})\\
  & \ge \varlimsup_{n\to\infty} \mathsf{P}(|Y_n|\ge a)\qquad \text{(by Fatou Lemma)} \\
  &\ge \frac12. \tag{2}
\end{align*}
Meanwhile,
\begin{align*}
 C&\subset \Big\{ \omega: -\infty<\varliminf_{n\to\infty} I(4^n)=\varlimsup_{n\to\infty} I(4^n) <\infty \Big\}
 \subset  \Big\{ \omega: \lim_{n\to\infty} |Y_n|=0 \Big\} .\\
 C^c& \supset \Big\{ \omega: \varlimsup_{n\to\infty} |Y_n|\ge a \Big\}
\end{align*}
Furthermore,
\begin{align*}
  \mathsf{P}(C^c)&\ge \mathsf{P}(\varlimsup_{n\to\infty} |Y_n|\ge a )\ge \frac12>0,\\
  \mathsf{P}(C)& <\frac12<1.
\end{align*}
Now, $ \mathsf{P}(C)=0 $ holds from 0-1 law(In Edit 2 above).


TITLE: Canonical second quantization vs canonical quantization with multisymplectic form in AQFT
QUESTION [7 upvotes]: First of all, I'm a mathematician that knows less than the basics of QFT, so forgive me if this question is trivial. Please, keep in my mind that my background in physics is very poor.
1) The usual process of quantization of a free scalar field on $Q$ is by using Weyl operators $W (f)$ for each $f \in S \subset L^2 (T^*Q)$ (where S is a space of solutions) such that $$W(f)W(g) = \exp (-i \sigma (f, g)) W (f + g)$$ for some (pre-)symplectic form $\sigma$.
This process is explained for the Klein-Gordon equation here The most general procedure for quantization
2) On the other side, in http://arxiv.org/abs/physics/9801019 and http://arxiv.org/abs/math-ph/0408008, given a configuration bundle $$F \twoheadrightarrow X$$ with $X$ a globally hyperbolic Lorentzian manifold of dimension $n + 1$ and a Lagrangian density $$\mathcal{L}: J^1F  \rightarrow \Lambda^{n + 1} T^*X$$ such that $\mathcal{L} = Ldx$. Let $$(J^1 (F))^* = \text{Hom} (J^1F, \Lambda^{n + 1}T^*X),$$ $$\mathbb{F} \mathcal{L} : J^1F \rightarrow (J^1F)^*$$ be the Legendre transform, $\omega =- d\theta$ and $\theta$ is the canonical form on $(J^1F)^*$. Then $$\omega_L = -\mathbb{F} \mathcal{L}^* \omega = -d \theta_L$$ for $\theta_L = \mathbb{F} \mathcal{L}^* \theta$ is a a multisymplectic form of degree $n + 2$.
Given Cauchy surface $\Sigma \subset X$, it's possible to produce a (pre-)symplectic form $$\Omega_{\Sigma} = \int_{\Sigma} \omega_L$$ on the off-shell (the space of all sections).
Locally on coordinates $$\theta_L = \frac{\partial L}{\partial v^a_\mu} \wedge du^a \wedge dx_0 \wedge … \wedge \hat{dx_\mu} \wedge … \wedge dx_n + (L - \frac{\partial L}{\partial v^a_\mu}v^a_\mu )dx$$
3) Analogously in http://arxiv.org/1402.1282 and http://ncatlab.org/nlab/show/multisymplectic+geometry, one can consider the first variation $$\delta \mathcal{L} = \sum_a (EL_L)_a \wedge \delta u^a + d \theta_L$$, where $(EL_L)_a$ is the Euler-Lagrange equation and $(x_{\mu}, u^a, v^a_{\mu})$ are the local coordinates of $J^1 F$. In this context $$\omega_L = EL_L + \delta \theta_L $$ is a $n + 2$-form which is (pre-) multisymplectic.
In a lot of references, it's said that the variational principle 3) coincides with 2). It's said too that $\theta_L$ in 3) coincides with the usual boundary condition $$\sum_{a, \mu} \frac{\partial L}{\partial v^a_{\mu}} \delta u^a $$ (which seems impossible). I would like an answer to these two questions. These are two minor questions that are probably because of a miscalculation of my part or the authors.
Now my main question is : How can one relate 1) to 3)?
More precisely, are the symplectic forms the same in these two approaches? If not, do canonical quantization of 3) (via Weyl CCR or non-exponeniated CCR) produce an equivalent QFT?

EDIT
The second of my minor question is obviously true, because of the Stokes formula. The boundary condition can be written as $$\int _{\partial V} \sum_{a, \mu} \frac{\partial L}{\partial v^a_{\mu}} \delta u^a vol_{\partial V}= \int_V \sum_{a, \mu} d(\frac{\partial L}{\partial v^a_{\mu}} \delta u^a) dx$$ for some suitable region $V \subset X$.
Anyway the first minor question remains. In other words, is $\theta_L = \frac{\partial L}{\partial v^a_{\mu}} \delta u^a dx$ in 3) equals to $\frac{\partial L}{\partial v^a_\mu} \wedge du^a \wedge dx_0 \wedge … \wedge \hat{dx_\mu} \wedge … \wedge dx_n + (L - \frac{\partial L}{\partial v^a_\mu}v^a_\mu )dx$   ($\theta_L$ in 2))?
All the terms except $Ldx$ seems reasonable to appear in $\theta_L$ of  3).

REPLY [1 votes]: A multisymplectic form is not a symplectic form and cannot be canonically quantized. Thus your main question doesn't make sense as made ''more precise''. (By the way, I have never seen a way to quantize a multisymplectic form.
You would have to quantize the symplectic form underlying the Peierls bracket constructed from the multisymplectic framework. This would give the same result as the quantization in point 1).
The equivalence of the various symplectic forms with the Peierls bracket is demonstrated (with varying amounts of detail) in work by Forger/Romero, by Marolf, by Esposito et al., by Khavkine. They are all constructed to be equivalent, in the hope that one of them might oneday lead to a better approach to a nonperturbative quantization.


TITLE: Qualitative theory of ODE’s restricted to bounded solutions
QUESTION [0 upvotes]: Assume that you have an ODE
$$F(t,x(t),…,x^n(t))=0$$,
and you know that there exist some subset on the space on initial conditions such that every solution of the ODE with initial values in this subset yields a bounded orbit.
Is there any qualitative theory for ODE’s applying for the bounded orbits only? For example, that the bounded orbits have some sort of stability that the non-bounded orbits don’t,etc.

REPLY [0 votes]: In general, bounded orbits are not a stable property, consider e.g $F(x, x') = x—x'$.
Looking for instance at first order autonomous system $x'(t) = F(x(t))$, assuming each orbit is complete and $F:\mathbb{R} \to \mathbb{R}$ is continuous, then the orbits in a connected component of the open subset $\{F\neq 0\}$ of $\mathbb{R}$ all do the same thing: either flow off to infinity (unbounded component) or flow to the left (or right) towards a critical point on the boundary of the connected component (bounded on the left or respectively right). This shows that the non-trivial bounded orbits form an open set (hence stable). But so do the unbounded orbits. The remaining orbits are trivial orbits (the zeros of $F$).
Is this what you had in mind?


TITLE: What is meant by $\infty^1$, $\infty^2$, $\infty^3$?
QUESTION [1 upvotes]: I find the notation $\infty^1$, $\infty^2$, $\infty^3$ in an old paper by Kasner [1].  The context is, for example, "...we obtain from a given system in general $\infty^3$ new systems" and "A turbine consists of $\infty^1$ elements whose points form a circle..."  What is the meaning of this $\infty^n$ notation?
[1] Kasner, Edward, "The Group of Turns and Slides and the Geometry of Turbines," Am. J. Math., Vol. 33, No. 1/4 (Jan., 1911), pp. 193-202.

REPLY [1 votes]: I find the notation somewhat bewildering. Without actually understanding what the author writes about, I have the strong impression that $\infty^n$ refers to a geometric "$n$-parameter" family of things — i.e. an $n$-dimensional space.
(I emphasize geometric, since the author does talk about $n$-parameter groups)
The best concrete conformation I have for this interpretation is the phrase

... the $\infty^3$ circles of a plane

since one can parametrize circles in the plane with three parameters; e.g. the $x$ and $y$ coordinates of the origin along with the radius.


TITLE: Is there an optimal game theory strategy for choosing the second lowest number?
QUESTION [4 upvotes]: Say there is a group of n people, and they all must select an integer, x, between 1 and 100 with the goal being that in the set, y, of all numbers selected only one is less than the number you selected. So the person(s) who selected the second lowest number is the winner.
If you tie you split the prize, but if everyone says the same number no one wins because they are all the lowest number.
How does the solution change if the number is not limited to integers?

REPLY [3 votes]: First of all, it's clearly a Nash equilibrium for everyone to choose $100$. Nobody wins, and nobody can make themselves win. Let's call that the trivial equilibrium.
If $n=2$, then there are also nontrivial equilibria where player 1 always chooses $100$ and player 2 does... anything at all. Player 2 never wins, so it doesn't matter what they choose; and player 1 has no incentive to choose anything less than $100$.
If $n>2$, there there is still a nontrivial equilibrium in which player 1 chooses between $99$ and $100$, possibly randomly, and every other player always chooses $100$. Player 1 can't win, so they are indifferent between all choices. The remaining players might win with $100$, or they might not, but they have no incentive to switch, because they definitely wouldn't win with anything else.
I claim that there are no other equilibria, pure or mixed, than those described above. This should be provable by inductively ruling out $0$, then $1$, then every other choice less than $99$. Since it's Friday, this proof is left as an exercise for the reader.


TITLE: Legendre-Symbol, an easy example.
QUESTION [1 upvotes]: First I start with the important equivalence (Euler) due to the quadratic residue:
$$(a|p) \equiv a^{\frac{1}{2}(p-1)} \pmod{p}$$
Having $(-2|p) = 1 \Leftrightarrow p\equiv 1 \text{ or },3 \pmod{8}$ I would like to know if I'm right with $$(-1|p) = 1 \Leftrightarrow p\equiv 1 \text{ or },5 \pmod{8}?$$
Am I right to consider that $$(I)\ \ (2|p) = (-1|p)\cdot(-2|p) = 1 \Leftrightarrow (-1|p)=(-2|p)=1 \text{ or } (-1|p)=(-2|p)=-1?(*)$$
If I am, so why is $$ (2|p) = 1 \Leftrightarrow p \equiv \pm 1 \pmod{p}?$$
The case $p \equiv +1 \pmod{p}$ should be clear, the other should come from the equivalence above $(I,[\ldots] = -1)$. But I'm not sure about how exactly. I would be thankful for any kind of help!

REPLY [0 votes]: Your question seems to be the following. Given that $(-2|p)=1$ iff $p\equiv 1$ or $p\equiv 3 \pmod{8}$, show that $(2|p)=1$ iff $p\equiv \pm 1\pmod{8}$.
Use the fact that $(2|p)=(-2|p)(-1,p)$. An odd prime is congruent to $1$, $3$, $5$, or $7$ modulo $8$.
If $p\equiv 1\pmod{8}$, then $(-2|p)=1$ and $(-1|p)=1$, giving $(2|p)=1$.
If $p\equiv 3\pmod{8}$, then $(-2|p)=1$ and $(-1|p)=-1$, giving $(2|p)=-1$.
If $p\equiv 5\pmod{8}$, then $(-2|p)=-1$ and $(-1|p)=1$, giving $(2|p)=-1$.
If $p\equiv 7\pmod{8}$, then $(-2|p)=-1$ and $(-1|p)=-1$, giving $(2|p)=1$.
It is common to write $p\equiv 7\pmod{8}$ in the equivalent form $p\equiv -1\pmod{8}$.


TITLE: Let A be an mxn matrix of rank 1. Using the definition of rank, show that there exists an mx1 matrix X and an 1xn matrix Y such that A=XY
QUESTION [1 upvotes]: How do I approach this question? I know the X and Y can be the basis for the columnspace of A and the basis of rowspace of A, but how can it be? Thanks for help!

REPLY [1 votes]: If the rank of $A$ is equal to $1$, then its columns are all in the vectorial line generated by a non zero vector $Y$ of dimension $m$.
That means that the columns of $A$ are
$$x_1 Y, x_2 Y, \dots , x_nY.$$ If you denote $X^T=(x_1, \dots , x_n)$, you get the desired result
$$A=X^T Y.$$


TITLE: Does an integral of a polar function from $0$ to infinity have to diverge?
QUESTION [1 upvotes]: This is more of a theoretical question, but I was curious if a polar equation automatically diverges as it goes to infinity? After all, the area will just be the area in the polar graph added to itself infinitely, right?

REPLY [0 votes]: Hint:
I'm not sure to interpret correctly your question, but, for $r=e^{-\theta^2}$ we have:
$$
\int_0^\infty r d\theta=\frac{\sqrt{\pi}}{2}
$$
and also
$$
\int_0^\infty r^2 d\theta=\frac{1}{2}\sqrt{\frac{\pi}{2}}
$$


TITLE: Exponentiation with complex numbers
QUESTION [0 upvotes]: If a complex number $z$ is multiplied with itself n times, will the result $z^n$ always be greater in magnitude than $z^{n-1}$ or z ?
Is there some formula to find the magnitude of $z^n$ , without finding $z^n$ first?

REPLY [1 votes]: Note that every complex number $z$ can be written as $re^{i \theta}$ where $r$ is the magnitude of $z$.
Now it follows $z^n=r^n e^{in \theta}$
$$=r^n \left( \cos n \theta + i \sin n \theta \right)$$
$$=r^n \cos n \theta + i r^n \sin n \theta$$
What's the magnitude of $z^n$?
Well, it's $\sqrt{\left(r^n \cos n \theta \right)^2+ \left( r^n \sin n \theta \right)^2}=r^n$
Now ask yourself when $r^n$ is greater than $r^{n-1}$ or, simply $r$.


TITLE: What's the correct way for proving by Well Ordering Principle that any positive integer can be expressed as a sum of powers of two?
QUESTION [1 upvotes]: I have the following proof.
Proof:
Let $C = \{ m \:| \:\forall\: k \in \mathbb{Z}^+, k < 2^{m + 1}, k \neq 2^{a_1} + 2^{a_2} + \ldots + 2^{a_i}, a_i < m + 1 \}$, now, let's assume that this is a nonempty set, assuming this we are saying that there is a minimum element in the set (because of the Well Ordering Principle), let this element be $m_0$, this means that for every positive integer less than $2^{m_0 + 1}$ such integer can't be expressed as a sum of powers of 2, it follows that the statement holds for $m_0 - 1$, but this is a contradiction, because if it's true then there are integers less than $2^{m_0 + 1}$ that can be expressed as a sum of powers of two, then such a set has no minimum element, meaning it's empty.
QED
Is this proof the correct way of proving such property? Is convinging enough? Thanks beforehand.

REPLY [2 votes]: You need to keep track of "for all" and "there exists" statements.  Here's a proof that you might be looking for:
Proof: Let $S$ be the set of all positive integers not expressible as a sum of powers of $2$.  For the sake of contradiction, assume $S$ is nonempty.  By the Well-Order Principle, $S$ has a least element, say $m \in S$.  Clearly, $m\neq1$ since $1=2^0$, so $m>2^0$.  Let $n$ be the largest natural number such that $m>2^n$.  Then $m-2^n>0$ and $m-2^n<m$.  So by our choice of $m$, $m-2^n \notin S$.  Therefore, $m-2^n=2^{n_1}+2^{n_2}+\ldots +2^{n_k}$ for some $n_i$.  However, then we have $m=2^n+2^{n_1}+2^{n_2}+\ldots +2^{n_k}$, contradicting our assumption. QED


TITLE: Differential equations and linearly independent solutions
QUESTION [2 upvotes]: If $$y_1(x)=\sin 2x$$ and $$y_2(x)=\cos 2x$$ are two solutions of $$y^{,,}+4y=0,$$ show that $y_1(x)$ and $y_2(x)$ are linearly independent solutions.
I think to prove linearly independent,the equation will be
$$c_1\sin 2x+c_2\cos 2x=0$$,where $c_1$ and $c_2$ have to be equal to zero,but how to prove that??,please help me..

REPLY [2 votes]: One way to show the independence of solutions is to show that the Wronskian is not identically zero.
$$ W= \det \begin {bmatrix}y_1&y_2\\y'_1&y'_2\end{bmatrix}\not = 0$$
You can take it from here.

REPLY [1 votes]: $$c_1\sin 2x+c_2\cos 2x=0,  \forall x$$
for $x=\frac {\pi}4$
$$\implies c_1=0$$
for $x=0$
$$\implies c_2=0$$


TITLE: One infinite series question, two different result?
QUESTION [0 upvotes]: The 1st way:
$$f(x)=\frac{4x}{x^2+2x-3}=\frac{3x-3+x+3}{(x+3)(x-1)}=\frac{3}{x+3}+\frac{1}{x-1}=\frac{1}{1+\frac{x}{3}}-\frac{1}{1-x}=\sum_{i=0}^\infty{(\frac{-x}{3})^i}-\sum_{i=0}^\infty{x^i}=\sum_{i=0}^\infty{[(\frac{-1}{3})^i-1]}x^i$$
The 2nd way:
$$f(x)=\frac{4x}{x^2+2x-3}=x[\frac{(x+3)-(x-1)}{(x+3)(x-1)}]=x[\frac{1}{x-1}-\frac{1}{x+3}]=x[-\frac{1}{3}\frac{1}{1+\frac{x}{3}}-\frac{1}{1-x}]=x[-\frac{1}{3}\sum_{i=0}^\infty{(\frac{-x}{3})^i}-\sum_{i=0}^\infty{x^i}]=\sum_{i=0}^\infty{[(\frac{-1}{3})^{i+1}-1]}x^{i+1}$$
The calculation seems right, but I get 2 different result.

REPLY [3 votes]: Haven't checked your calculations but the two sums have equal value.
The first sum has one element more than the second, the element with i=0. But this element's value is $(1-1)x^0$ which is $0$.


TITLE: What is a 2-regular graph?
QUESTION [2 upvotes]: What is a 2-regular graph? Is is the same thing as an 2-connected graph where a 2-connected graph is a graph G such that G-V ( G minus a vertex V) is still connected?

REPLY [0 votes]: So now you know what a $k$-regular graph is, but what do you think in particular a 2-regular graph looks like?
Certainly, all cycle graphs are 2-regular, but that's not all of them...what other graphs are 2-regular but not a cycle? (think about integer partitions of $n$)


TITLE: Video of Double Slit Experiment Observer Effect
QUESTION [4 upvotes]: I have been watching a lot of videos of the double slit experiment and trying to wrap my head around it.
I found examples of where the experiment has been done, however the videos cut out and only simulate the effect an observer has on it. I understand that the wave interference pattern collapses when an observer is put into play.
Is there a video that displays the observer effect in comparison to the regular double slit experiment? I would like to see how observing the particles before and after they go through the slit changes the resulting patterns.
Follow up question:
I watched this video https://www.youtube.com/watch?v=Iuv6hY6zsd0
This video demonstrates the interference pattern created by sunlight in a box. I understand that this is how light behaves (photons? Particles? I am not sure ...)
Question: would it be possible to do this experiment, and somehow "measure" the light before or after it goes through the slits, to create the pattern that is created when observing?
And if not, why is that?

REPLY [1 votes]: Great question!  I suspect the reason you can't find videos (although I haven't looked for them myself) is because most of the videos of interference will be videos of photon interference, since that is the easiest kind of interference experiment to do.  However, the only kind of measurements we can perform on photons in this experimental context are what we call "destructive" measurements: for example, you could just block off one of the two slits, and then for any of the photons that get through you will know which slit they went through... but you will be destroying the other half of the photons.
This is therefore not as compelling an illustration of the collapse of interference patterns as an experiment in which you can measure which slit the particles go through while still allowing them to pass through the slits.  For this, you need to use some other kind of particles, such as electrons.  This has been done, and the interference pattern indeed collapses when you measure which slit each electron passes through, but I still don't know if there is a video...


TITLE: order of meromorphic functions on Riemann torus
QUESTION [1 upvotes]: Let $\Lambda$ be a lattice in $\mathbb{C}$ and $f$ be a meromorphic function on $\mathbb{C}$ such that $f(z)=f(z+w)$ for all $z\in\mathbb{C}$ and $w\in\Lambda$. Then I want to know how to prove $\sum_{z\in\mathbb{C}/\Lambda}\text{ord}_z(f)·z=0$, this is an equality in the additive group $\mathbb C/\Lambda$.
Thanks very much!

REPLY [1 votes]: Your map $f$ defined on $\mathbb{C}$ can be extend to the torus $\mathbb{C}/\Lambda$. In general when you have a meromorphic function $f$ on a Riemann surface, you can define the so called principal divisor of the function
$div(f)=\sum_{p}ord_p(f)\cdot p$
At this point it is necessary to define the Abel map of a complex torus that permit us to consider each divisor as an element of the torus itself, that is an additive group.
In fact the structure of the additive group $\mathbb{C}$ can be induced on the complex torus $\mathbb{C}/\Lambda$ becoming an abelian  group. You have another important abelian group on a Riemann surface $X$, the group of divisors $Div(X)$, the free $\mathbb{Z}$-module generated by the set $X$.
The Abel map is $A: Div(\mathbb{C}/\Lambda)\to \mathbb{C}/\Lambda$ that assigns to each $\sum_{k}a_kp_k$, the element $\sum_{k}a_kp_k+\Lambda$ on the group $\mathbb{C}/\Lambda$.
Your statement is equivalent to prove each meromorphic function $f$ on the torus  satisfies the condition
$A(div(f))=0$
To prove this, we consider the set of zeros $\{p_i\}_{i=1}^n$ and poles $\{q_j\}_{j=1}^m$ of $f$, where we repeat the points according to the order of $f$ in that points. Then we get
$div(f)=\sum_{i=1}^np_i- \sum_{j=1}^mq_j$
However the complex torus is a compact Riemann Surface and it holds the fundamental fact
$deg(div(f))=0$
that permit us to say $n=m$.
This means $div(f)$ can be written as $\sum_{i=1}^n(p_i-q_i)$.
Assume by contradiction that $\sum_{i=1}^np_i\neq  \sum_{i=1}^nq_i$ on the complex torus. Then we can consider two new distinct points $p_0$ and $q_0$ such that
$p_0=(\sum_{i=1}^np_i-  \sum_{i=1}^iq_i)+q_0$
and this time we get $\sum_{i=0}^np_i=\sum_{i=0}^nq_i$. Moreover we can choose $x_i\in \pi^{-1}(p_i)$ and $y_i\in \pi_i^{-1}(q_i)$, where $\pi$ is the quotient map of the complex torus. In. this case we get
$\sum_{i=0}^nx_i-\sum_{i=0}^ny_i=\lambda \in \Lambda$
and so
$\sum_{i=0}^nx_i=\sum_{i=0}^ny_i$
replacing $x_0$ with $x_0-\lambda$.
We are in the situation to built a new meromorphic function on the complex torus:
$R(z):=\frac{\prod_{i=0}^n\theta^{(x_i)}(z)}{\prod_{i=0}^n\theta^{(y_i)}(z)}$
At this point we can observe $R/f$ is a meromorphic function that has only one zero and one pole:
$div(R/f)=div(R)-div(f)=\sum_{i=0}^np_i-\sum_{i=0}^nq_i-(\sum_{i=1}^np_i-\sum_{i=1}^nq_i)=p_0-q_0$
This is a contradiction because $\mathbb{P}^1$ is the only Riemann surface for which there exists a meromorphic function that has only one zero and one pole.
This is not the end of the story because also the converse is true, i.e. if $D$ is a divisor on the torus such that $deg(D)=0$ and $A(D)=0$, the $D$ is a principal divisor, so it is a divisor of a meromorphic function on the torus.
This permit us to say $A: deg^{-1}(0)/Pdiv(\mathbb{C}/\Lambda)\to \mathbb{C}/\Lambda$ is injective and it is called the Abel-Jacobi theorem.