text:
\begin{document}
	\title{Partially Information Coupled Duo-Binary Turbo Codes}
	\author{\IEEEauthorblockN{Xiaowei Wu, Min Qiu, and Jinhong Yuan}
		\IEEEauthorblockA{School of Electrical Engineering and Telecommunications\\The University of New South Wales, Sydney, Australia\\Email: xiaowei.wu@unsw.edu.au, min.qiu@unsw.edu.au, j.yuan@unsw.edu.au}
	}
	\maketitle

	\begin{abstract}
		Partially information coupled turbo codes (PIC-TCs) is a class of spatially coupled turbo codes that can approach the BEC capacity while keeping the encoding and decoding architectures of the underlying component codes unchanged. However, PIC-TCs have significant rate loss compared to its component rate-$\frac{1}{3}$ turbo code, and the rate loss increases with the coupling ratio.
		To absorb the rate loss, in this paper, we propose the partially information coupled duo-binary turbo codes (PIC-dTCs).
		Given a rate-$\frac{1}{3}$ turbo code as the benchmark, we construct a duo-binary turbo code by introducing one extra input to the benchmark code. Then, parts of the information sequence from the original input are coupled to the extra input of the succeeding code blocks.
		By looking into the graph model of PIC-dTC ensembles, we derive the exact density evolution equations of the PIC-dTC ensembles, and compute their belief propagation decoding thresholds on the binary erasure channel.
		Simulation results verify the correctness of our theoretical analysis, and also show significant error performance improvement over the uncoupled rate-$\frac{1}{3}$ turbo codes and existing designs of spatially coupled turbo codes.
	\end{abstract}

	\section{Introduction}
	Spatial coupling is a class of code construction techniques which connects a sequence of component codes to form a long codeword chain. It was firstly introduced in \cite{Felstrom-convLDPC} for constructing convolutional low-density parity-check (LDPC) codes, which is also known as spatially coupled LDPC (SC-LDPC) codes.
	Extensive research has been conducted on SC-LDPC codes (see \cite{Kudekar-scLDPC,Lentmaier-scLDPC,Xie-scLDPC} and the references therein) since then.
	In addition, the spatial coupling technique has also been applied to turbo-like codes (SC-TCs), including parallel and serially concatenated convolutional codes \cite{Moloudi-scTurbo}, hybrid concatenated convolutional codes \cite{Moloudi-scHCC}, laminated turbo codes \cite{Huebner-LaminatedTC}, and braided convolutional codes \cite{Zhang-bcc}.
	All the above works have reported that the spatially coupled codes can provide close-to-capacity performance and perform much better than their uncoupled counterparts.
	Most notably, it has been theoretically proven in \cite{Kudekar-scLDPC} that the belief propagation (BP) decoding thresholds of SC-LDPC codes can converge to the maximum-a-posteriori (MAP) decoding thresholds of their underlying component codes, namely the threshold saturation phenomenon.
	 In \cite{Moloudi-scTurbo}, the authors also proved that their proposed SC-TCs have threshold saturation. Apart from the performance improvement, another advantage of spatially coupled codes is that they can be decoded by a windowed decoder with lower decoding latency compared to decoding the whole codeword block.
	 Due to these reasons, it is believed that spatially coupled codes would have a wide range of applications in communications.

	In this work, we focus on a particular spatial coupling technique, namely the partially information coupling (PIC). PIC was firstly introduced in \cite{Yang-picTurbo} with LTE turbo codes as component codes (PIC-TCs).
	In a PIC code, consecutive component code blocks (CBs) are coupled by sharing a portion of the information bits between each other.
	Apart from turbo codes, PIC can be directly applied to various types of component codes, such as LDPC codes \cite{Yang-PIC_LDPC} and polar codes \cite{Wu-picPolar,Wu-picPolarBICM}, without changing the encoding and decoding architectures of the underlying component codes.
	However, due to the coupling, (i.e., the same information sharing between CBs), PIC codes have significant rate loss compared to its component codes. For example, in \cite{Yang-picTurbo,Qiu-picTurboDE}, with a rate-$\frac{1}{3}$ turbo code as component code, the PIC-TC ensembles have a code rate of $\frac{1}{5}$ when half of the information bits are coupled.

	In this paper, we propose a new class of PIC codes, namely the partially information coupled duo-binary turbo codes (PIC-dTCs). Such codes do not have the rate-loss as appeared in the conventional PIC-TCs. More importantly, they can retain the same rate regardless of the couple-ratio.
	Given a $\textnormal{rate-}\frac{1}{3}$ benchmark turbo code, i.e., a parallel concatenation of two rate-$\frac{1}{2}$ recursive systematic convolutional (RSC) code, we construct a duo-binary turbo code \cite{Berrou-nonBinaryTurbo,Berrou-duoBinaryTurbo} by introducing one extra input to the component RSC code.
	After that, we apply partially information coupling to a shortened duo-binary turbo code. The resultant PIC-dTCs have the same code rate as the benchmark turbo code.
	We study the performance of the PIC-dTCs over the binary erasure channel (BEC). We first look into the graph model of the code ensembles. Based on the graph representation, we derive the exact density evolution (DE) equations for the PIC-dTC ensembles with any given coupling ratio and coupling memory. The DE analysis shows that our codes are within a gap of 0.001 to the BEC capacity .
	Simulation results confirm our theoretical analysis, and also show significant error performance improvement over the benchmark turbo code and existing designs of spatially coupled turbo codes.

	\section{Partially Information Coupled Duo-Binary Turbo Codes}
	In this section, we introduce the architecture of PIC-dTCs. We first present the construction of the uncoupled duo-binary turbo codes. Then, we describe the encoding of PIC-dTCs with coupling memory $m=1$, i.e., a CB only shares information with between two consecutive CBs. After that, we will give a general description on the encoding and decoding of PIC-dTCs with coupling memory $m \geq 1$.

	\subsection{Construction of Duo-Binary Turbo Codes}
	We consider a rate-$\frac{1}{3}$ turbo code (referred to as TC1), which is a parallel concatenation of two identical rate-$\frac{1}{2}$ RSC code (referred to as RSC1). To build PIC-dTCs from TC1, the first step is to construct a rate-$\frac{1}{2}$ duo-binary turbo code (referred to as TC2), which is a parallel concatenation of two identical rate-$\frac{2}{3}$ RSC code (referred to as RSC2).

	Let $\mathbf{g}_f$ and $\mathbf{g}_b$ denote the forward and feedback generator polynomial of RSC1, respectively. The generator matrix of RSC1 can then be written as
	\begin{align}
	\mathbf{G}_{\text{RSC}1}=\left [{\begin{matrix} 1  ~ \frac{\mathbf{g}_f}{\mathbf{g}_b}  \end{matrix}}\right ].
	\end{align}
	Let $\ut{}$ denote an information sequence of length $K$.
	When we encode $\ut{}$ with RSC1, the output is ${\ut{} \cdot \mathbf{G}_{\text{RSC}1}=\left [{\begin{matrix} \ut{} ~ \mathbf{v} \end{matrix}}\right ]}$, where ${\mathbf{v} = \frac{\ut{} \cdot \mathbf{g}_f}{\mathbf{g}_b}}$ is the parity sequence.

	By introducing one extra input $\ut{}'$ to RSC1, the generator matrix of RSC2 is in the form of
	\begin{align}
	\mathbf{G}_{\text{RSC}2}=\left [{\begin{matrix} 1 & 0 & \frac{\mathbf{g}_f}{\mathbf{g}_b}  \\ 0 & 1 & \frac{\mathbf{g}_f'}{\mathbf{g}_b}  \end{matrix}}\right ],
	\end{align}
	where $\mathbf{g}_f$ and $\mathbf{g}_f'$ are the forward generator polynomial of the two information sequences $\ut{}$ and $\ut{}'$, respectively, and ${\mathbf{g}_f \neq \mathbf{g}_f'}$.
	Both information sequences share the same feedback generator polynomials $\mathbf{g}_b$ so that RSC1 and RSC2 have the same number of states.
	The encoder output of RSC2 is computed as ${\ut{} \cdot \mathbf{G}_{\text{RSC}2}=\left [{\begin{matrix} \ut{} ~ \ut{}' ~ {\mathbf{v}} \end{matrix}}\right ]}$, where ${\mathbf{v}=\frac{\ut{} \cdot \mathbf{g}_f}{\mathbf{g}_b}+\frac{\ut{}' \cdot \mathbf{g}_f'}{\mathbf{g}_b}}$.
	This ensures RSC1 can be obtained by shortening RSC2, i.e., when $\ut{}'=\mathbf{0}$, the parity sequence from RSC2 is the same as that of RSC1. Consequently, TC1 can be obtained by shortening TC2 in the same manner.

	An example is shown in Fig. \ref{fig:RSC_enc}, where ${\mathbf{G}_{\text{RSC}1}=\left [{\begin{matrix} 1  ~ \frac{5}{7} \end{matrix}}\right ]}$, and ${\mathbf{G}_{\text{RSC}2}=\left [{\begin{smallmatrix} 1 & 0 & \frac{5}{7} \\ 0 & 1 & \frac{3}{7} \end{smallmatrix}}\right ]}$, respectively. Here, ${\mathbf{g}_f'=3}$ is obtained by exhaustive search to ensure that RSC2 has a good distance spectrum, and the resultant TC2 has a good decoding threshold. The extra input $\ut{}'$ are highlighted in red.

	\subsection{Encoding of PIC-dTCs with Coupling Memory $m=1$}
	In the PIC-dTC encoding process, the information sequence $\mathbf{u}$ is divided into $L$ sub-sequences ${\ut{1}, \hdots, \ut{L}}$. For the time instance ${t=1, \hdots, L}$, let \cb{t} represent the $t$-th CB.
	The block diagram of the PIC-dTC encoder at time $t$ with coupling memory ${m=1}$ is depicted in Fig. \ref{fig:TB_encode}.
	The CB encoder takes the $t$-th sub-sequence, i.e., $\ut{t}$, as the first input sequence, and takes ${\ut{t}'=[\ut{t-1,t}, \mathbf{0}]}$ as the second input sequence. Here, $\ut{t-1,t}$ is the coupled information sequence shared between \cb{t} and \cb{t-1}, and shortened bits $\mathbf{0}$ are inserted in the second input sequence so that the length of $\ut{t}$ and $\ut{t}'$ are equal.
	Then, $\ut{t}$ is decomposed into $\ut{t,t}$ and $ \ut{t,t+1}$, where $\ut{t,t}$ represents the uncoupled information sequence, i,e. the information only stays in \cb{t}, and $\ut{t,t+1}$ represents the coupled information sequence  shared between \cb{t} and \cb{t+1}.
	After CB encoding, the codeword of \cb{t} is obtained as ${[\ut{t},\mathbf{v}_t]}$, where $\mathbf{v}_t$ is the parity sequence.
	Note that $\ut{t-1,t}$ is not included in the codeword of \cb{t} because it is included in the codeword of \cb{t-1}.
	To terminate the coupling, both ends of the coupling chain are set to zero, i.e., at time ${t=1}$, ${\ut{0,1}=\mathbf{0}}$, and at time ${t=L}$, ${\ut{L,L+1}=\mathbf{0}}$.

	In \cb{t}, the information length is ${K=\|\ut{t} \|=\|\ut{t}' \|}$, the  length of coupled sequence is ${K_c=\|\ut{t-1,t} \|=\|\ut{t,t+1} \|}$, and the length of parity sequence is ${2K=\|\mathbf{v}_t\|}$.

	The code rate of PIC-dTC is
	\begin{align}
	R  = \frac{KL-K_c}{3KL-K_c} = \frac{L-\lambda}{3L-\lambda} \overset{L\rightarrow\infty}{=} \frac{1}{3}.
	\end{align}
	We define ${\lambda\triangleq\frac{K_c}{K}}$ as the coupling ratio, and $\lambda\in [0,1]$. It is an important parameter that determines the decoding threshold, which will be discussed later.

	\begin{figure}[t]
		\centering
		\includegraphics[width=0.35\textwidth]{RSC_enc.pdf}
		\caption{Block diagram of the rate-$\frac{2}{3}$ RSC encoder. }
		\label{fig:RSC_enc}
	\end{figure}
	\begin{figure}[t]
		\centering
		\includegraphics[width=0.4\textwidth]{TB_encode_small.pdf}
		\caption{Block diagram of PIC-dTC encoder at time $t$. }
		\label{fig:TB_encode}
	\end{figure}

	\subsection{Encoding of PIC-dTCs with Coupling Memory $m \geq 1$}
	For coupling memory ${m \geq 1}$, \cb{t} are coupled with $m$ preceding CBs (from \cb{t-m} to \cb{t-1}) and $m$ succeeding CBs (from \cb{t+1} to \cb{t+m}). The length of coupled sequence becomes $\frac{K_c}{m}$.
	Specifically, at time $t$, the CB encoder takes $\ut{t}$ as the first input sequence, and ${\ut{t}'=[\ut{t-1,t}, \hdots, \ut{t-m,t}, \mathbf{0}]}$ as the second input sequence.
	In the mean time, $\ut{t}$ is decomposed into ${\ut{t,t}, \ut{t,t+1}, \hdots, \ut{t,t+m}}$, where ${\ut{t,t+1}, \hdots, \ut{t,t+m}}$ are passed to $m$ succeeding CBs, respectively.
	 After CB encoding, the codeword of \cb{t} is obtained as
	${[\ut{t},\mathbf{v}_t]}$, i.e.,
	${\ut{t-1,t}, \hdots, \ut{t-m,t}}$ is not included in the codeword.
	The code rate of PIC-dTC is
	\begin{align}
	R  = \frac{KL-\sum_{i=1}^{m} \frac{i \cdot K_c}{m}}{3KL-
		\sum_{i=1}^{m}  \frac{i \cdot K_c}{m}}
	= \frac{L-  \frac{m+1}{2} \lambda } {3L-  \frac{m+1}{2} \lambda}
	\overset{L\rightarrow\infty}{=} \frac{1}{3}.
	\end{align}

	\textbf{Remark}: We compare the construction of the PIC-dTCs with that of the PIC-TCs \cite{Yang-picTurbo,Qiu-picTurboDE}. For the PIC-TCs with TC1 as component code, the CB encoder only has one information sequence. Hence, there is a rate loss related to the coupling ratio $\lambda$. Specifically, the code rate of PIC-TCs is given by ${\frac{1-\lambda }{3-\lambda}}$, where ${\lambda\in[0,\frac{1}{2}]}$.
	Puncturing is required in order to increase the code rate of PIC-TCs to $\frac{1}{3}$.

	For the PIC-dTCs, the CB encoder takes two input sequences $\ut{t}$ and $\ut{t}'$. Unlike the PIC-TCs, we add an extra input to the TC1, resulted in TC2, and put the coupled sequence from previous CBs into the extra input sequence. This design can absorb the rate loss as appeared in the PIC-TCs. Hence, it allows the resultant PIC-dTCs to maintain the rate of TC1, i.e., 1/3, without rate loss. In addition, the PIC-dTCs can attain the close-to-capacity performance which will be shown in our performance analysis and numerical results later.

	\subsection{Decoding of PIC-dTCs}
	The decoding of PIC-dTCs can be accomplished by a feed-forward and feed-back (FF-FB) scheme \cite{Yang-picTurbo,Qiu-picTurboDE} in an iterative manner. In short, it employs a serial scheduling by decoding from the first CB to the last CB serially and then decoding backwards from the last CB to the first CB if necessary. For \cb{t}, the decoder takes the received signal associated with the codeword ${[\ut{t},\mathbf{v}_t]}$ as well as the extrinsic information associated with ${\ut{t-m,t}, \hdots, \ut{t-1,t}}$ and ${\ut{t,t+1}, \hdots, \ut{t,t+m}}$  as input, and outputs the soft-decision estimation of the information sequences. The decoding of RSC2 is realized by the BCJR algorithm \cite{bcjr}\cite{turbo_yuan}.

	\section{Performance Analysis of PIC-{\upshape d}TCs}
	In this section, we analyse the decoding performance of the PIC-dTCs by using density evolution. We first look into the corresponding graph model of the PIC-dTC. Later, the exact DE equations are then derived based on the graph model.

	\subsection{Graph Model Representation}
	For the ease of presentation, we first consider the coupling memory ${m = 1}$ and then extend to the coupling memory ${m \geq 1}$.
	Fig. \ref{fig:factor_graph_uc} shows the compact graph representation \cite{Moloudi-scTurbo} of the uncoupled TC2. In the compact graph, at time $t$, the two information sequences $\ut{t}$ and $\ut{t}'$ are represented by two different variable nodes. We use two factor nodes $f^U$ and $f^L$ to represent the upper and the lower RSC decoders, respectively.
	Each of the variable nodes is connected with the upper and lower factor nodes, meaning that the extrinsic information is passed between the upper and lower decoder via the corresponding variable node.
	The parity sequences enter the upper and lower decoder are denoted by $\mathbf{v}^U_t$ and  $\mathbf{v}^L_t$, respectively. The interleaver is represented by a slash on the edge between the variable nodes and the lower factor node.

	Fig. \ref{fig:factor_graph_1} shows the compact graph of PIC-dTC with coupling memory ${m=1}$. For each CB, we treat the uncoupled information, the coupled information, and the shortened bits node (denoted by $\mathbf{0}$ in	Fig. \ref{fig:factor_graph_1}) separately. At time $t$, we use two variable nodes to represent $\ut{t}'$, i.e., we treat $\ut{t-1,t}$ and $\mathbf{0}$ as two separate nodes. Also, we use two variable nodes to represent $\ut{t}$ by treating $\ut{t,t}$ and $\ut{t,t+1}$ separately.
	As $\ut{t-1,t}$ is shared by $\ut{t-1}$ and $\ut{t}'$, the node representing $\ut{t-1,t}$ is connected to both \cb{t-1} and \cb{t}, meaning that $\ut{t-1,t}$ is encoded twice at time ${t-1}$ and time $t$.
	Due to the similar reason, the node $\ut{t,t+1}$ is connected to both \cb{t} and \cb{t+1}.

	In summary, the compact graph shows that the extrinsic information of $\ut{t-1,t}$ is passed between the upper and lower factor nodes of \cb{t-1} and \cb{t}; the extrinsic information of $\ut{t,t+1}$ is passed between the upper and lower factor nodes of \cb{t} and \cb{t+1}; and the extrinsic information of $\ut{t,t}$ is passed between the upper and lower factor nodes of \cb{t} only.

	\begin{figure}[t]
		\centering
		\hspace{-2mm}
		\subcaptionbox{\label{fig:factor_graph_uc}}
		{\includegraphics[height=4.1cm]{factor_graph_uc.pdf}}
		\hspace{-4mm}
		\subcaptionbox{\label{fig:factor_graph_1}}
		{\includegraphics[height=4.1cm]{factor_graph_2.pdf} }
		\hspace{-5mm}
		\subcaptionbox{ \label{fig:factor_graph_m}}
		{\includegraphics[height=4.1cm]{factor_graph_m.pdf}	}
		\caption{Compact factor graph of (a) uncoupled turbo codes, and (b) PIC-dTC with coupling memory ${m=1}$, and (c) PIC-dTC with coupling memory ${m \geq 1}$.}
		\label{fig:factor_graph}
	\end{figure}

	\subsection{Density Evolution for Coupling Memory $m=1$} \label{sec:de}
	For transmission over the BEC, the asymptotic behaviour of the PIC-dTCs can be analysed by tracking the evolution of the erasure probability over decoding iterations. Here, we first consider coupling memory ${m=1}$.

	Let $\varepsilon$ denote the channel erasure probability.
	At time $t$ and the $i$-th iteration, let $\bar{p}_{1,L,t}^{(i)} $ and $\bar{p}_{2,L,t}^{(i)}$ denote the average extrinsic erasure probability passed from $\ut{t}$ and $\ut{t}'$ to $f^U$, respectively. Let $p_{1,U,t}^{(i)} $ and $p_{2,U,t}^{(i)}$ denote the extrinsic erasure probability from $f^U$ to $\ut{t}$ and $\ut{t}'$, respectively.
	Likewise, let $\bar{p}_{1,U,t}^{(i)} $ and $\bar{p}_{2,U,t}^{(i)}$ denote the average extrinsic erasure probability passed from $\ut{t}$ and $\ut{t}'$ to $f^L$, respectively. Let $p_{1,L,t}^{(i)} $ and $p_{2,L,t}^{(i)}$ denote the extrinsic erasure probability from $f^L$ to $\ut{t}$ and $\ut{t}'$, respectively.

	Based on the graph model in Fig. \ref{fig:factor_graph_1}, $\bar{p}_{1,L,t}^{(i)}$ is the weighted sum of the erasure probabilities of variable node $\ut{t,t}$ and $\ut{t,t+1}$, and $\bar{p}_{2,L,t}^{(i)}$ is the weighted sum of the erasure probabilities of variable node $\ut{t-1,t}$ and $\mathbf{0}$.
	For $\bar{p}_{1,L,t}^{(i)}$, $\ut{t,t}$ can only obtain extrinsic information from $f^L$ at time $t$, while $\ut{t,t+1}$ can obtain extrinsic information from $f^L$ at time $t$, as well as from $f^L$ and $f^U$ at time $t+1$. It is computed as
	\vspace{-0.5mm}
	\begin{align}
	\bar{p}_{1,L,t}^{(i)}=\varepsilon \cdot p_{1,L,t}^{(i)} \cdot \left( 1 - \lambda + \lambda \cdot p_{2,U,t+1}^{(i-1)} \cdot  p_{2,L,t+1}^{(i)}   \right) .
	\vspace{-0.5mm}
	\end{align}
	For $\bar{p}_{2,L,t}^{(i)}$, the erasure rate of $\mathbf{0}$ is 0, while $\ut{t-1,t}$ can collect extrinsic information from $f^L$ at time $t$, as well as $f^U$ and $f^L$ at time ${t-1}$. It is computed as
	\vspace{-0.5mm}
	\begin{align}
	\bar{p}_{2,L,t}^{(i)}=\varepsilon \cdot \lambda \cdot  p_{2,L,t}^{(i)} \cdot p_{1,U,t-1}^{(i-1)}  \cdot  p_{1,L,t-1}^{(i)} .
	\end{align} \vspace{-5mm}
	$\!\!$Likewise, the average erasure probability from $\ut{t}$ and $\ut{t}'$ to $f^L$ is computed as
	\begin{align}
	\bar{p}_{1,U,t}^{(i)} = \varepsilon \cdot p_{1,U,t}^{(i)} \cdot  \left( 1 - \lambda + \lambda  \cdot p_{2,U,t+1}^{(i)} \cdot  p_{2,L,t+1}^{(i-1)} \right) ,
	\end{align}
	\vspace{-0.5mm}
	$\!\!$and
	\vspace{-0.5mm}
	\begin{align}
	\bar{p}_{2,U,t}^{(i)}=\varepsilon \cdot \lambda \cdot  p_{2,U,t}^{(i)}  \cdot  p_{1,U,t-1}^{(i)} \cdot p_{1,L,t-1}^{(i-1)} ,
	\end{align}
	respectively.
	The erasure probability of $\mathbf{v}_t^U$ and $\mathbf{v}_t^L$ are the same as the channel erasure probability because no extrinsic information is passed to the parity nodes.

	Let $F_{1}^U$ and$F_{2}^U$ represent the information sequence transfer functions of $f^U$, and $F_{1}^L$ and $F_{2}^L$ represent the information sequence transfer functions of $f^L$, which are derived following \cite{Kurkoski-turboDE}, respectively. At time $t$ and the $i$-th iteration, the evolution of the erasure probability for $\ut{t}$ and $\ut{t}'$ inside $f^U$ is
	\begin{align}
		p_{1,U,t}^{(i)}=F_{1}^U\left(\bar{p}_{1,L,t}^{(i)},\bar{p}_{2,L,t}^{(i)},\varepsilon\right),\\
		p_{2,U,t}^{(i)}=F_{2}^U\left(\bar{p}_{1,L,t}^{(i)},\bar{p}_{2,L,t}^{(i)},\varepsilon\right),
	\end{align}
	and the evolution of erasure probability inside $f^L$ is
	\begin{align}
	p_{1,L,t}^{(i)}=F_{1}^L\left(\bar{p}_{1,U,t}^{(i)},\bar{p}_{2,U,t}^{(i)},\varepsilon\right),\\
	p_{2,L,t}^{(i)}=F_{2}^L\left(\bar{p}_{1,U,t}^{(i)},\bar{p}_{2,U,t}^{(i)},\varepsilon\right).
	\end{align}
	The a-posteriori erasure probability of $\ut{t}$ after $i$ iterations is
	\begin{align}
	p_{\ut{t}}^{(i)}=\varepsilon \!\cdot\! p_{1,U,t}^{(i)}  \!\cdot\! p_{1,L,t}^{(i)} \!\cdot\!\left(1-\lambda + \lambda \!\cdot\!  p_{2,U,t+1}^{(i)}  \!\cdot\! p_{2,L,t+1}^{(i)} \right).
	\end{align}

	\subsection{Density Evolution for Coupling Memory $m \geq 1$}
	Here, we generalize the DE analysis to coupling memory ${m \geq 1}$.
	As shown in Fig. \ref{fig:factor_graph_m}, the erasure probability of $\ut{t}$ depends on the erasure probability of uncoupled information $\ut{t,t}$ as well as the coupled information ${\ut{t,t+1}, \hdots, \ut{t,t+m}}$. The average extrinsic erasure probability from $\ut{t}$ to the $f^U$ is computed as
	\vspace{-2mm}
	\begin{align}
		\bar{p}_{1,L,t}^{(i)}=\varepsilon  \!\cdot\!  p_{1,L,t}^{(i)}  \!\cdot\!  \Big(  1 - \lambda + \frac{\lambda}{m} \sum_{j=1}^{m}  p_{2,U,t+j}^{(i-1)}   \!\cdot\!  p_{2,L,t+j}^{(i)}  \Big).
	\end{align}

	The erasure probability of $\ut{t}'$ only depends on the erasure probability of the coupled information ${\ut{t-m,t}, \hdots, \ut{t-1,t}}$. The average extrinsic erasure probability from $\ut{t}'$ to the $f^U$ is computed as
	\vspace{-2mm}
	\begin{align}
	\bar{p}_{2,L,t}^{(i)}=\varepsilon \cdot  p_{2,L,t}^{(i)} \cdot \frac{\lambda}{m} \sum_{j=1}^{m}
	 p_{1,U,t-j}^{(i-1)}  \cdot p_{1,L,t-j}^{(i)} .
	\end{align}

	The average erasure probability from $\ut{t}$ and $\ut{t}'$ to $f^L$, i.e., $\bar{p}_{1,U,t}^{(i)}$ and $\bar{p}_{2,U,t}^{(i)}$, can be computed in similar manner, so we omit the details here. The a-posteriori erasure probability of $\ut{t}$ after $i$ iterations is
	\vspace{-2mm}
	\begin{align}
	 \!  \!  \!  \!  p_{\ut{t}}^{(i)}=\varepsilon \!  \cdot  \! p_{1,U,t}^{(i)} \!  \cdot \!  p_{1,L,t}^{(i)}  \!\cdot\! \Big(1 \! - \! \lambda  \! + \!
	\frac{\lambda}{m} \sum_{j=1}^{m} p_{2,U,t+j}^{(i)}  \!\cdot\!  p_{2,L,t+j}^{(i)} \Big).
	\end{align}

	\section{Numerical Results}
	In this section, we first present the BP decoding threshold ${\varepsilon_{_{\text{BP}}}}$ for some PIC-dTC ensembles by using the DE analysis derived in Section \ref{sec:de}. After that, we show the simulation results on the error performance of our PIC-dTCs.
	We consider TC1 with ${\mathbf{G}_{\text{RSC}1}=\left [{\begin{matrix} 1 ~ \frac{5}{7} \end{matrix}}\right ]}$ as the benchmark, and we use TC2 with ${\mathbf{G}_{\text{RSC}2}= \left [{\begin{smallmatrix} 1 & 0 & \frac{5}{7} \\ 0 & 1 & \frac{3}{7} \end{smallmatrix}}\right ]}$ as component code to construct the PIC-dTCs ensembles.

	\subsection{Density Evolution Results} \label{sec:de_result}
	\begin{figure}[t]
		\centering
		\includegraphics[width=0.5\textwidth]{dec_th.eps}
		\caption{BP Decoding thresholds of rate-$\frac{1}{3}$ PIC-dTCs with ${m=1}$ over coupling ratio $\lambda$.}
		\label{fig:dec_th}

	\vspace{2mm}
	\includegraphics[width=0.5\textwidth]{dec_th_m.eps}
	\caption{BP decoding thresholds of rate-$\frac{1}{3}$  PIC-dTCs over coupling memory $m$.}
	\label{fig:dec_th_m}
	\vspace{-5mm}
\end{figure}

	We plot the BP decoding thresholds of the PIC-dTCs versus the coupling ratio $\lambda$ for coupling memory ${m=1}$ in Fig. \ref{fig:dec_th}. It can be seen that the decoding threshold improves with $\lambda$ increasing.
	When ${\lambda=\frac{1}{2}}$, the gap between the decoding threshold and the BEC capacity is around 0.009. When $\lambda$ approaches $1$, the gap is only 0.0073.
	However, it can also be observed that the increment of decoding threshold slows down when $\lambda$ keeps increasing. When $\lambda$ is increased from $\frac{3}{4}$ to 1, the decoding threshold has minor improvement.

	To see how the decoding threshold improves with the coupling memory $m$, we plot the decoding thresholds of the PIC-dTCs as functions of $m$ in Fig. \ref{fig:dec_th_m}. For all considered coupling ratio $\lambda$ shown in the legend, the decoding threshold significantly improves when we increase $m$ from from 1 to 50. It is observed that the PIC-dTC can approach the BEC capacity with a gap around 0.0011 with ${\lambda=1}$ and ${m=50}$.
	Although it is unclear how the decoding performance would be when $m$ approach infinite, the threshold still keeps improving even when ${m>50}$. For example, with ${\lambda=1}$, the decoding threshold of PIC-dTC ensemble is 0.6657 when ${m=200}$, which is better than that for ${m = 50}$.  The investigation for threshold saturation is left for our future work.

	We also compare our PIC-dTCs to other benchmark coding schemes. Specifically, in Table \ref{tb:e_bp}, we show the decoding thresholds of the PIC-TCs with ${\lambda=\frac{1}{2}}$, PIC-dTCs with ${\lambda=1}$, and state-4 SC-TCs in \cite{Moloudi-scTurbo}, including spatially coupled parallel concatenated convolutional codes (SC-PCCs), spatially coupled serial concatenated convolutional codes (SC-SCCs), and braided convolutional codes (BCCs).
	Code rate ${R=\frac{1}{3}}$ and coupling memory ${m=1,5,50}$ are considered. Note that for ${m=50}$, we list the MAP decoding thresholds of the SC-TCs  due to threshold saturation.
	It can be seen that the decoding thresholds of the PIC-dTCs is better than that of the PIC-TCs. When ${m=1}$, the PIC-dTCs outperform SC-PCCs and SC-SCCs, but is slightly worse than the BCCs. When $m$ is large, the PIC-dTC with ${\lambda=1}$ has the largest decoding threshold among all the benchmark codes.

	\begin{table}[]
		\centering
		\begin{tabular}{l c c c}
			 \hline \\[-6pt]
			Ensemble & $\varepsilon_{_{\text{BP}}}, m=1 $& $\varepsilon_{_{\text{BP}}}, m=5 $ & $\varepsilon_{_{\text{BP}}}, m=50 $\\[2pt] \hline \\[-6pt]
			PIC-TC, $\lambda=\frac{1}{2}$       & 0.6566      & 0.6625    & 0.6639 \\[2pt]
			PIC-dTC, $\lambda=1$       & 0.6594     & 0.6644    & 0.6656 \\[2pt]
			SC-PCC        & 0.6553     & 0.6553    & 0.6553 \\[2pt]
			SC-SCC        & 0.6437     & 0.6654    & 0.6654 \\[2pt]
			BCC Type-I  & 0.6609     & 0.6650    & 0.6653 \\[2pt]
			BCC Type-II & 0.6651     & 0.6653    & 0.6653 \\[2pt] \hline
		\end{tabular}
		\caption{BP Decoding thresholds of rate-$\frac{1}{3}$ spatially coupled codes. }
		\label{tb:e_bp}
	\end{table}

	\subsection{Error Performance Simulation Results}
	We now present simulation results for the PIC-dTCs with ${m=1}$ and code rate $\frac{1}{3}$.
	We set ${L=100}$ to minimize the rate loss due to coupling termination.
	The error performance of PIC-dTCs is measured in terms of bit erasure rate (BER) versus the erasure probability of the BEC.

	In order to verify the correctness of the DE analysis, we compare the decoding threshold with the simulated BER (denoted as sim in the legend) of PIC-dTCs with ${K=10^5}$ and ${\lambda=\frac{1}{8},\frac{1}{4},\frac{1}{2},\frac{3}{4}}$.
	The results are shown in Fig. \ref{fig:ber_K100000}.
	It can be observed that all the PIC-dTCs are within 0.002 to the decoding threshold at a BER of $10^{-5}$.

	\begin{figure}[t]
		\vspace{-2mm}
		\centering
		\includegraphics[width=0.5\textwidth]{ber_K100000.eps}
		\caption{Error performance of rate-$\frac{1}{3}$ PIC-dTCs with ${m=1,}$ $K=10^5, L=100$.}
		\label{fig:ber_K100000}
		\vspace{2mm}

		\includegraphics[width=0.5\textwidth]{ber_K10000_update.eps}
		\caption{Error performance of rate-$\frac{1}{3}$ PIC-dTCs and PIC-TCs with $m=1, K=10^4, L=100$.}
		\label{fig:ber_K10000}
	\end{figure}

	In Fig. \ref{fig:ber_K10000}, to evaluate the performance of the PIC-dTCs with moderate information length, we plot the BER of PIC-dTCs with ${K=10^4}$, the PIC-TCs \cite{Yang-picTurbo,Qiu-picTurboDE} with ${K=10^4}$ (whose parity sequences are random punctured to increase the code rate to $\frac{1}{3}$), and TC1 with ${K=10^6}$.
	It can be seen that all the PIC-dTCs outperform the uncoupled TC1 even though they have almost the same information length.
	It is also observed that the PIC-dTCs can achieve better error performance by simply increasing $\lambda$, while the PIC-TCs need to optimize $\lambda$ in order to obtain a good error performance. Nevertheless, we observe that the PIC-dTCs have better error performance than the PIC-TCs when $\lambda$ is greater than $\frac{1}{4}$.

	\section{Conclusion}
	In this paper, we proposed the partially information coupled duo-binary turbo codes (PIC-dTCs), which do not have the rate loss as appeared in the PIC-TCs,  and investigated their performance. We considered the PIC-dTCs with coupling ratio ${\lambda \in [0,1]}$ and coupling memory ${m \geq 1}$. The encoding and decoding procedures for such codes are presented.
	We then introduced the graph model representations of the PIC-dTCs ensembles, and derived the exact DE equations for any given coupling memory $m$ and coupling ratio $\lambda$.
	We showed that the decoding thresholds of PIC-dTCs can approach the BEC capacity with a gap within 0.001 for a large coupling memory. The simulation results confirmed the correctness of the analysis. Both theoretical analysis and simulation results demonstrated the superior error performance of our PIC-dTCs over the uncoupled turbo codes and existing spatially coupled turbo codes at the same rate.

	 \section*{Acknowledgement}
	 The work was partially supported in part by the Australian Research Council Discovery Project under Grant DP190101363 and in part by the Linkage Project under Grant LP170101196.

	\bibliographystyle{ieeetr}
	\bibliography{pic_turbo_isit_reference}
\end{document}


TITLE: A problem about an unramified prime in a Galois extension.
QUESTION [3 upvotes]: Let $K/\mathbb{Q}$ be a Galois extension of degree $n$, we will denote its ring of integers by $\mathcal{O}_K$. Let $\mathfrak{p}$ be an arbitrary prime ideal of $\mathcal{O}_K$, which is unramified over $\mathbb{Z}$, and prime to $n!$. We will denote the residue field of $\mathfrak{p}$ by $\kappa(\mathfrak{p})$, its characteristics by $p$, and its residue degree by $f$. Let $x \in \mathcal{O}_K$, and let $\bar{x}$ be its image in $\kappa(\mathfrak{p})$.
and assume that $P \in \mathbb{Z}[X]$ is a monic minimal polynomial of $\bar{x}$, such that $P(x) \in \mathfrak{p} \backslash \mathfrak{p}^2$, and $\deg(P)=f$.
(Q): Show that $\mathcal{O}_K/\mathfrak{p}^2$ is generated by the image of $x$ over $\mathbb{Z}/p^2\mathbb{Z}$.

My attempts: Since $P$ have the minimal degree, among the polynomials which are vanishing $x$ module $\mathfrak{p}$, then it should be irreducible over the field $\mathbb{Z}/p\mathbb{Z}$.
Therefore $1, x, \cdots, x^{f-1}$ are linearly independent over $\mathbb{Z}/p$.
Also, notice that  $$\dfrac{\dfrac{\mathbb{Z}}{p\mathbb{Z}}}{P(X)} \equiv \dfrac{\mathbb{Z}}{p\mathbb{Z}} \oplus x \dfrac{\mathbb{Z}}{p\mathbb{Z}} \oplus \cdots \oplus x^{f-1}\dfrac{\mathbb{Z}}{p\mathbb{Z}}$$
is a field between $\dfrac{\mathbb{Z}}{p\mathbb{Z}}$ and $\dfrac{\mathcal{O}_K}{\mathfrak{p}}$, with $\dfrac{\mathbb{Z}}{p\mathbb{Z}}$-degree equal to $f=[\dfrac{\mathcal{O}_K}{\mathfrak{p}}:\dfrac{\mathbb{Z}}{p\mathbb{Z}}]$, so it should equal to $\dfrac{\mathcal{O}_K}{\mathfrak{p}}$. So we can conclude that $\dfrac{\mathcal{O}_K}{\mathfrak{p}}$ is generated by the image of $x$ over $\dfrac{\mathbb{Z}}{p\mathbb{Z}}$. (My proof on this fact, may contain extra details; if so let me know please.) But I don't have any idea why $\mathcal{O}_K/\mathfrak{p}^2$ is generated by the image of $x$ over $\mathbb{Z}/p^2\mathbb{Z}$?

I'm looking to figure out how, in this case, "the assumption $P(x) \in \mathfrak{p} \backslash \mathfrak{p}^2$" helps me solve the problem. I have this issue with similar problems; for instance, I had trouble dealing with exercises 19-22 from chapter $4$ of Marcus's Number Fields. (In these exercises I had to deal with "the assumption $\pi \in Q \backslash Q^2$".) Also, I tried to look for some versions of Nakayama's lemma, but I was not succeded.

REPLY [1 votes]: It's one of the main theorems about Dedekind domains that $\mathfrak{p}$ becomes principal $ = (\pi)$ in $O_{K,p}$ thus in $O_K/(\mathfrak{p}^m)$.
$\pi$ can be chosen to be any element of $\mathfrak{p}\setminus \mathfrak{p}^2$.
With $S\subset O_K/(\pi^m)$ a set of representatives of $O_K/(\pi)$ then $$O_K/(\pi^m) = \{ \sum_{j=0}^{m-1} s_j \pi^j,s_j\in S\}$$
$\quad$ (given any element $a\in \pi^j O_K/\pi^m O_K$ there is a unique $s_j\in S$ such that $a-s_j\pi^j\in \pi^{j+1} O_K/\pi^m O_K$)
In your question $\pi= P(x)$ and the set $S$ is taken in the subalgebra generated by $x$, from that $x$ generates $O_K/\mathfrak{p}$ as a $Z/(p)$ algebra (if it was smaller then $x$'s $Z/(p)$-minimal polynomial would be of degree $<f$)
no need that $\mathfrak{p}$ is unramified.


TITLE: Is ECI a pseudo-inertial frame?
QUESTION [1 upvotes]: The Python poliastro package documentation states that, when propagating from position and velocity vectors, the orbit's reference frame will be "one pseudo-inertial frame around the attractor," which in the case of earth-orbiting objects, means some form of ECI.  However, I want to make sure I am matching up coordinates because I am using another bit of code to convert a position on Earth to ECI using the IERS.
I have already checked answers to a similar post and found the clarity to be lacking.  I want a specific answer in this case from someone who has used poliastro in the following form:
from astropy import units
from poliastro.bodies import Earth
from poliastro.twobody import Orbit
from poliastro.twobody.propagation import kepler

ephemerisPosition = (ephemerisPosition * units.earthRad).to(units.meter)
ephemerisVelocity = (ephemerisVelocity * units.earthRad / units.day).to(units.meter / units/second)
seconds = ephememerisStart + secondsOffset

for i, time in enumerate(seconds):
    ss = Orbit.from_vectors(Earth, ephemerisPosition, ephemerisVelocity).propagate(time * units.second, method=kepler)

REPLY [3 votes]: First things first: Software questions are off-topic at this site.
So I'll focus my answer from the perspective of the title question, with a hint toward poliastro.

Is ECI a pseudo-inertial frame?

This question is being asked from a Newtonian perspective. (Poliastro is fully Newtonian.) The answer is of course it is a pseudo-inertial frame. The Earth orbits the Sun. QED. Or, as someone challenged me forty years ago: "There is no such a thing as a Newtonian inertial frame of reference. Name one if you think otherwise."
Using a coordinate system with the origin at the center of a solar system body is inherently non-inertial. The central body is accelerating toward all the other bodies in the solar system. This acceleration is why any frame of reference whose axes are aligned with the ICRF axes but whose origin is at the center of a solar system body is pseudo inertial frame rather than an inertial frame.
Poliastro even provides a function, poliastro.core.perturbations.third_body, that very explicitly takes into account that a non-rotating body-centered frame is by definition a pseudo-inertial frame of reference. What solar system dynamicists and spacecraft engineers call the "third body effect" explicitly captures the non-inertial nature of a body-centered frame of reference.


TITLE: How do photons get into the eyes?
QUESTION [28 upvotes]: I hope you will understand me correctly because there are some things that I translated.
It is known that we see the world around us thanks to photons that
are reflected from the surfaces of objects, so I have the following question:
If you imagine, for example, a huge gray column 200 meters from the eyes.
Why are the photons reflected off this column flying straight into your eyes
all the time while you're looking? I mean, is it some huge stream flying in all directions, parts of which will necessarily fall into the eyes? How does this stream not mix with others?
What does that even look like? An infinite number of randomly intersecting and moving points?
How do we distinguish which photons are reflected from what?

REPLY [0 votes]: Photons have a code (frequency)
All the eye perceive is light (photons) and each spectrum of photons have a individual code that when perceived by the eye creates a image within the brain that is reality (environment)


TITLE: Proving inequalities with analysis
QUESTION [0 upvotes]: Suppose that for all $0<c \in \mathbb{R}$ that $a < bc + b$ where $a, b \in \mathbb{R}$. Prove that $b \geq a$ and $b \geq 0$.
My attempt:
We start by considering $a < bc + b$. We have that
$$a < bc + b \implies bc + b  - a > 0$$
Using the archimedian property of real numbers, it follows
$$bc + b - a > \frac{1}{n}$$
$$nbc + nb  - na > 1$$
Now, by the archimedian property involving integers, there is an $m \in \mathbb{Z}$ such that we have
$$m \leq nbc + nb < m + 1$$
This is as far as I have gotten with this proof, and I'm not sure if I'm even right thus far. I am new to this topic and I am not sure how to manipulate the archimedian property/ies to complete the proof. Any assistance is much appreciated.

REPLY [1 votes]: $a<bc+b$
We know that this must be true for any real number $c$ greater than, but not equal, to 0. Let's first assume $b>0$, then we can establish an upper bound for $a$ by letting $c$ approach zero.
$a<\lim_{c\to 0}(bc+b)\  \to \ (a<b)$
Since $c$ cannot equal zero, than $a=b$ also satisfies $a<bc+b$.
Therefore:
$b>0\Rightarrow a\leq b$
Let's consider when $b<0$.
$a<\lim_{c\to\infty}(bc+b)\ \to \ (a<-\infty)$
This is impossible.
$b\nless 0$
Lets consider when $b=0$
$a<bc+b$
$a<0c+0$
$a<0$
This is a perfectly valid possibility.
Therefore:
$b\geq 0$
$b \geq a$


TITLE: How does the smoothness condition of a potential function imply the smoothness of its equipotential line?
QUESTION [0 upvotes]: I am wondering how does the smoothness condition of a potential function imply the smoothness of its equipotential line. I would like to know if there is some theorem on this kind of questions.
The smoothness condition could be anything like continuous, Lipschitz continuous, differentiable, analytical, etc.
For example, let $f:\mathbb{R}^2\to \mathbb{R}$ be a differentiable potential function, assume we have a parametrized curve $c(t)$ where $f(c(t))=0$ for all $t\in[0,1]$, what can we say about this curve $c$? Is it, for example, differentiable?
Any help would be appreciated!

REPLY [1 votes]: The Implicit Function Theorem is what you need. If $f$ has continuous partial derivatives and $\nabla f(c(t_0))\ne(0,0)$ for some $t_0$, then $c$ is continuously differentiable on a neighborhood of $c(t_0)$.


TITLE: Can we determine the sign of this product of complex numbers?
QUESTION [0 upvotes]: Let $$\Lambda=\prod_{n=1}^N(a_n+ib_n)\not=0$$
where $a_n,b_n$ are real. Can we determine $\mathrm{sign}(\Lambda)$ when $\mathrm{Im}(\Lambda)=0$ and $a_n<0\;\forall n$?
The result can depend on $N$, but not the individual $a_n$s and $b_n$s.

The context for this problem is that I have the matrix product $$A=BC$$ where $A$ and $C$ are square and (in general) nonsymmetric, so $$\mathrm{det}(A)=\mathrm{det}(BC)=\mathrm{det}(B)\mathrm{det}(C).$$ I know that $\mathrm{det}(B)$ is positive and real and that $\mathrm{det}(C)$ is real (since the matrix $C$ is real, its determinant can only be real). Now I write $\mathrm{det}(A)$ as the product of the (complex) eigenvalues of $A.$ Furthermore, I know that all eigenvalues of $A$ have negative real part.

REPLY [0 votes]: We can't know the sign. Assuming $a+b+c=abc$ we have that
$$(-1+ai)(-1+bi)(-1+ci)=ab+ac+bc-1.$$ Now, if $a=1,b=-1,c=0$ we get $-2<0$ and if $a=b=-2,c=-4/3$ we get $25/3>0.$


TITLE: Optimal tree structure within an undirected weighted graph
QUESTION [2 upvotes]: I am looking for an algorithm to split a graph into subgraphs to optimize drawing of the graph.
The initial graph is a weighted bipartite graph. Let's call the nodes on one side elements and on the other busses. I want to cut the edges on the busses so all busses have degree two while minimizing the weight of the cut edges. This would result in a graph that can be drawn as a forest with the elements being the nodes and the busses being the edges. Not all elements have to be in the final tree, although the number of elements in the tree must be maximized.
An example structure is shown here:

The best algorithm I have found so far is a longest path algorithm. Although it is quite easy to create a graph where a tree structure is more efficient than simply using a longest graph.
Next I tried an algorithm where the longest path is combined with a tree splitting, so all elements where multiple busses originate that are not part of the longest path would have a new longest path originating there with the remaining nodes. But this also was not optimal as it would not provide a good solution with cyclic graphs.
Update - Brute force solution
I brute forced the graph in the image above to find the solution. The python code used to force this solution is:
#%% Imports
import itertools
import numpy as np
import typing

#%% Construct the graph
nodes: typing.List[str] = [str(i + 1) for i in range(7)] + [chr(i) for i in range(65, 70)]
bus_nodes: typing.List[str] = [chr(i) for i in range(65, 70)]
edges: typing.Dict[typing.Tuple[str, str], int] = {
    ("1", "A"): 1,
    ("1", "C"): 3,
    ("2", "A"): 4,
    ("2", "B"): 2,
    ("3", "A"): 7,
    ("3", "B"): 5,
    ("3", "C"): 6,
    ("4", "B"): 7,
    ("4", "D"): 3,
    ("5", "A"): 6,
    ("5", "C"): 1,
    ("5", "D"): 1,
    ("5", "E"): 9,
    ("6", "A"): 2,
    ("7", "B"): 8,
    ("7", "E"): 3
}

#%% Convert the nodes into an adjacency matrix.
N: int = len(nodes)
adj: np.ndarray = np.zeros(shape=(N, N), dtype=int)
for edge, weight in edges.items():
    i_a: int = nodes.index(edge[0])
    i_b: int = nodes.index(edge[1])
    ima = max(i_a, i_b)
    imi = min(i_a, i_b)
    adj[ima, imi] = weight

#%% Get each bus vertex that must be cut and get the options.
bus_nodes_to_options: typing.Dict[str, typing.Tuple[int, int]] = dict()
for node in bus_nodes:
    index = nodes.index(node)
    options = list(np.squeeze(np.argwhere(adj[index,:] > 0)))
    if len(options) == 2:
        continue
    bus_nodes_to_options[node] = list(itertools.combinations(options, r=2))

#%% Implement Kruskal algorithm
def kruskal_islands(adj: np.ndarray) -> typing.List[typing.Set[int]]:
    # Get the number of connected sets based on krugals algorithm.
    N: int = adj.shape[0]
    sets: typing.List[typing.Set[int]] = [{i, } for i in range(N)]
    for i,j in [(i, j) for i in range(N) for j in range(i)]:
        if adj[i,j] == 0:
            continue
        set_i = next(s for s in sets if i in s)
        set_j = next(s for s in sets if j in s)
        if set_i == set_j:
            continue
        set_i.update(set_j)
        sets.remove(set_j)
    return sets

#%% Create the graph for each options and calculate it's value
result: typing.List[typing.Tuple[int, int]] = list()
options = list(itertools.product(*bus_nodes_to_options.values()))
o = len(bus_nodes)
for q, option in enumerate(options):
    adj_copy = np.copy(adj)
    for i, row in enumerate(option):
        index = nodes.index(bus_nodes[i])
        adj_row = np.zeros(N)
        adj_row[row[0]] = adj[index, row[0]]
        adj_row[row[1]] = adj[index, row[1]]
        adj_copy[index, :] = adj_row
    total_weight = np.sum(adj_copy[-o:-1, 0:-o])
    num_islands = len(kruskal_islands(adj_copy))
    result.append((total_weight, num_islands))

#%% Determine the best option.
min_islands = min([a[1] for a in result])
max_rows = max([a[0] for a in result if a[1] == min_islands])
opt = result.index((max_rows, min_islands))
print(max_rows)
print(opt)
print(options[opt])

This resulted in the following graph:

All lines that are red are cut from the actual solution.
Although this brute force tactic works, it is also extremely slow as I have to do similar operations continuously. Is there a more elegant solution to my problem?
Update - Partial solution leading to restructuring
With the partial solution provided by @connor harris the problem can be rewritten. Now we can choose edge from all busses that must surely be part of the bus. All busses that only have two connection are already predefined. With these two we can group the remaining elements into different section as shown in this image:
Additionally, the connection between B-4 can be removed as it will connect between two nodes that are already part of the same group and thus would result in a loop in the final tree which is not allowed.
With these there are 5 groups remaining that are connected. From each bus we still need to chose the second connection that must be optimized. Different greedy algorithms don't work. For example in the restructured image (which is the same as the one above) here:
A greedy algorithm would start with the connection from A to yellow. Although this connection is not part of the optimal solution as the brute force algorithm shows.

REPLY [2 votes]: Only a partial result for now, but this should provide a considerable advance over brute force.
Lemma. The optimal forest includes, for every bus $b \in B$, the edge to $b$ with maximum weight.
Proof. Let $F$ be some forest structure on our original graph, and let $E_1, \ldots, E_k$ be a division of the elements $E$ into connected components of $F$ minus all edges to the bus $b$: that is, if $e_1, e_2$ are in different connected components $E_i$, then either there is no path from $e_1$ to $e_2$ through $F$, or the (necessarily unique) path passes through $b$. This means that we can modify $F$ by changing the two elements $e_1, e_2$ that connect to $b$, and as long as $e_1$ and $e_2$ are in different connected components, $F$ remains acyclic. The optimum choice is thus given by connecting $b$ to the two maximum-weight elements that also have the maximum weight in their connected components: that is, choose $e_1 \in E$ such that $w(e_1, b)$ is maximal, and then choose $e_2 \in E$ such that $w(e_2, b)$ is maximal among all elements that are not in the connected component $E_i$ that contains $e_1$.
Remarks: 1) If $b$ has multiple edges with the same maximum weight, then we could choose any edge. 2) This lemma applies even if we restrict $F$ to be a tree; in that case, there are exactly two connected components $E_1, E_2$.

This result lets us choose, in linear time, a subgraph of the optimal tree (or forest) consisting of a number of "complexes", each containing one element with connections to zero or more buses. Our task now is to find a "maximum spanning tree" on these complexes. by connecting a bus from one complex to the sole element of the other. Unfortunately, the usual MST algorithms don't work for this, because the connection weight between two complexes isn't independent from how they're connected to other complexes: it's possible that the highest-weight connections from $e_1$ to $e_2$ and $e_3$, for instance, both run through the same bus $b$, and we can't use both connections. So greedy algorithms that expand maximum spanning trees by choosing the maximum-weight edge at each step won't work.
(For instance: suppose we have three elements $1, 2, 3$ and two buses $A, B$ with connection weights $w(1, A) = w(2, B) = 20$, $w(2, A) = 10$, $w(1, B) = 9$, $w(3, A) = 9$, $w(3, B) = 1$. The maximum tree has to include edges $w(1, A)$ and $w(2, B)$, for weight 40. If we follow Kruskal's algorithm and take the greedy choice $(2, A)$ for our next edge, then we have to connect to $3$ via $B$, giving a total weight of $51$, whereas using $B$ for the connection between $1$ and $2$ in order to preserve $A$ for a better connection to $3$ would give us a total weight of $58$.)


TITLE: Proof Using Gronwall's Inequality
QUESTION [1 upvotes]: I have been asked to complete the following problem using the Gronwall Inequality. I'm not sure I applied the conditions appropriately because I feel there's too many gaps in my understanding of what I've done to say this proof is correct.

Let $f(t, x)$ be continuous on $\mathbb{R} \times \mathbb{R}^n$ and there exists $k_1,k_2 > 0$ such that $$\|f(t, x)\| \le k_1 + k_2\|x\|$$ for any $x\in \mathbb{R}^n$ and for all $t \in [t_0, \infty)$.
Use Gronwall's Inequality to show that the solution of $$\dot x =  f(t, x), \,\,\,\,x(t_0) = x_0$$ satisfies $$\|x(t)\| \le \|x_0\|e^{k_2(t - t_0)} + {k_1 \over k_2}\left(e^{k_2(t - t_0)} - 1\right)$$ for all $t \ge t_0$ for which the solution exists.

We received a hint that says to convert the differential equation to an integral equation which then the condition implies that $${k_1 \over k_2} + \|x(t)\| \le \|x_0\| + {k_1 \over k_2} + k_2 \int_{t_0}^t \left[{k_1 \over k_2} + \|x(s)\|\right]ds.$$
I'm unfortunately stuck here. I can convert the differential equation to an integral equation quite simply: $$\dot x = f(t, x), \,\,\,\, x(t_0) = x_0 \,\,\, \iff \,\,\, x(t) = x_0 + \int_{t_0}^tf(s, x(s))\,ds.$$
But I'm not understanding the motivation behind the hint. Here's what I did initially: $$\begin{align}\|x(t)\| & = \left\|x_0 + \int_{t_0}^tf(s, x(s))\,ds\right\| \\ &\le \|x_0\| + \int_{t_0}^t\|f(s, x(s))\| \, ds \\ &\le \|x_0\| + \int_{t_0}^t\left[k_1 + k_2\|x(s)\|\right]ds \\ \implies {k_1 \over k_2} + \|x(t)\| & \le \|x_0\| + {k_1 \over k_2} + k_2 \int_{t_0}^t\left[{k_1 \over k_2} + \|x(s)\|\right]\,ds,\end{align}$$
as the hint implies. We can see that since $\|x_0\|$ and $k_2$ are constant, by the Gronwall Inequality, $$\|x(t)\| \le \|x_0\|e^{k_2(t - t_0)} + {k_1 \over k_2}\left(e^{k_2(t - t_0)} - 1\right).$$
The last step feels like magic though, as if I just constructed the correct answer (probably because I did). Can someone explain how we get to the last step appropriately?

REPLY [2 votes]: To see what happens, set $\varphi(t) = \frac{k_1}{k_2} + \|x(t)\|$. Then your last inequality
$$ \frac{k_1}{k_2} + \|x(t)\| \leq \|x_0\| +  \frac{k_1}{k_2} + k_2 \int_{t_0}^{t} \, \left[  \frac{k_1}{k_2} + \|x(s)\| \right] ds$$ becomes
$$\varphi(t) \leq \Big( \|x_0\| +  \frac{k_1}{k_2}\Big)  + \int_{t_0}^{t} k_2 \, \varphi(s) \, ds$$ which is the assumption in the integral form of  Gronwall's inequality. Now according to Gronwall's inequality, $\varphi(t)$ should satisfy the inequality
$$\varphi(t) \leq  \left(\|x_0\| +  \frac{k_1}{k_2} \right) \exp\left({\int_{t_0}^{t} k_2 \, ds}\right)  =  \left(\|x_0\| +  \frac{k_1}{k_2} \right)\, e^{k_2 (t-t_0)}.$$ Now recall what
$\varphi(t)$ was and you get
 $$\frac{k_1}{k_2} + \|x(t)\| \leq \left(\|x_0\| +  \frac{k_1}{k_2} \right)\, e^{k_2 (t-t_0)}$$ which turns into
$$\|x(t)\| \leq   \left(\|x_0\| +  \frac{k_1}{k_2} \right)\, e^{k_2 (t-t_0)} - \frac{k_1}{k_2}  = \|x_0\| \, e^{k_2 (t-t_0)}  + \frac{k_1}{k_2} \big(e^{k_2 (t-t_0)} - 1\big)$$


text:
\section{Upstairs Decoding}
\label{sec:recovery}

In this section, we justify the fault tolerance of STAIR codes defined by
$m$ and $\mb{e}$. We introduce an {\em upstairs decoding} method
that systematically recovers the lost symbols when both device and sector
failures occur.

\subsection{Homomorphic Property}
\label{subsec:homomorphism}

The proof of fault tolerance of STAIR codes builds on the concept of a
{\em canonical stripe}, which is constructed by augmenting the existing stripe
with additional {\em virtual parity symbols}.  To illustrate,
Figure~\ref{fig:canonical} depicts how we augment the stripe of
Figure~\ref{fig:construction} into a canonical stripe.  Let $d^*_{h,j}$ and
$p^*_{h,k}$ denote the virtual parity symbols encoded with $\mc{C}_{col}$ from
a data chunk and a row parity chunk, respectively, where $0\le j\le n-m-1$,
$0\le k\le m-1$, and $0\le h\le e_{m'-1}-1$.

Specifically, we use $\mc{C}_{col}$ to generate virtual parity symbols from
the data and row parity chunks as follows:

\smallskip\noindent
For $j=0,1,\cdots,n-m-1$,

\begin{equation}\label{equ:virtualdata}
    d_{0,j},d_{1,j},\cdots,d_{r-1,j} \overset{\mc{C}_{col}}{\Longrightarrow} d^*_{0,j},d^*_{1,j},\cdots,d^*_{e_{m'-1}-1,j};
\end{equation}
and for $k=0,1,\cdots,m-1$,

\begin{equation}\label{equ:virtualparity}
    p_{0,k},p_{1,k},\cdots,p_{r-1,k} \overset{\mc{C}_{col}}{\Longrightarrow} p^*_{0,k},p^*_{1,k},\cdots,p^*_{e_{m'-1}-1,k}.
\end{equation}

The virtual parity symbols $d^*_{h,j}$'s and $p^*_{h,k}$'s, along with the
real and dummy global parity symbols, form $e_{m'-1}$ augmented rows of $n+m'$
symbols. In fact, the resulting canonical stripe in Figure~\ref{fig:canonical}
is a codeword of the product code \cite{Elias54} of $\mc{C}_{row}$ and
$\mc{C}_{col}$.  To make our discussion simpler, we number the rows and
columns of the canonical stripe from 0 to $r+e_{m'-1}-1$ and from 0 to
$n+m'-1$, respectively, as shown in Figure~\ref{fig:canonical}.

\begin{figure}[t]
\centering
\includegraphics[width=4.3in]{fig/homomorphism2}
\caption{A canonical stripe augmented from the stripe in
Figure~\ref{fig:construction}. The rows and columns are labeled from 0 to 5
and 0 to 10, respectively, for ease of presentation.}
\label{fig:canonical}
\end{figure}

Referring to Figure~\ref{fig:canonical}, we know that the upper $r$ rows of
$n+m'$ symbols are codewords of $\mc{C}_{row}$.  We argue that each of the
lower $e_{m'-1}$ augmented rows is in fact also a codeword of $\mc{C}_{row}$.

We call this the {\em homomorphic property}, since the encoding of each chunk
in the column direction preserves the coding structure in the row direction.
We formally prove the homomorphic property in Appendix~\ref{sec:appendix-Homomorphic}.
We use this property to prove the fault tolerance of STAIR codes.

\subsection{Proof of Fault Tolerance}
\label{subsec:recovery_proof}

\begin{figure}[t]
\centering
\includegraphics[width=4in]{fig/recover_step2}
\caption{Upstairs decoding based on the canonical stripe in
Figure~\ref{fig:canonical}.}
\label{fig:recover_step}
\end{figure}

We prove that for a STAIR code with configuration parameters $n$, $r$, $m$,
and $\mb{e}$, as long as the failure pattern is within the failure coverage
defined by $m$ and $\mb{e}$, the corresponding lost symbols can always be
recovered (or decoded).  In addition, we present an {\em upstairs decoding}
method, which systematically recovers the lost symbols for STAIR codes.

For a stripe of the STAIR code, we consider the worst-case recoverable failure
scenario where there are $m$ failed chunks (due to device failures) and $m'$
additional chunks that have $e_0$, $e_1$, $\cdots$, $e_{m'-1}$ lost
symbols (due to sector failures), where $0 < e_0 \leq e_1 \leq
\cdots \leq e_{m'-1}$.  We prove that all the $m'$ chunks with sector failures
can be recovered with global parity symbols.  In particular, we show that these
$m'$ chunks can be recovered in the order of $e_0$, $e_1$,
$\cdots$, $e_{m'-1}$.  Finally, the $m$ failed chunks due to device failures
can be recovered with row parity chunks.

\subsubsection{Example}

We demonstrate via our exemplary configuration how we recover the lost data
due to both device and sector failures.
Figure~\ref{fig:recover_step} shows the sequence of our decoding steps.
Without loss of generality, we logically assign the column identities such
that the $m'$ chunks with sector failures are in Columns~$n-m-m'$ to
$n-m-1$, with $e_0$, $e_1$, $\cdots$, $e_{m'-1}$ lost symbols, respectively,
and the $m$ failed chunks are in Columns~$n-m$ to $n-1$.  Also, the sector
failures all occur in the bottom of the data chunks.  Thus, the lost symbols
form a stair, as shown in Figure~\ref{fig:recover_step}.

The main idea of upstairs decoding is to recover the lost symbols from left to
right and bottom to top.  First, we see that there are $n-m-m'=3$ good chunks
(i.e., Columns~0-2) without any sector failure.  We encode via
$\mc{C}_{col}$ (which is a (6,4)-code) each such good chunk to obtain
$e_{m'-1}=2$ virtual parity symbols (Steps~1-3).  In Row~4, there are
now six available symbols. Thus, all the unavailable symbols in this row can
be recovered using $\mc{C}_{row}$ (which is a (11,6)-code) due to the
homomorphic property (Step 4).   Note that we only need to recover the $m'=3$
symbols that will later be used to recover sector failures.  Column~3 (with
$e_0=1$ sector failure) now has four available symbols.  Thus, we
can recover one lost symbol and one virtual parity symbol using $\mc{C}_{col}$
(Step 5).  Similarly, we repeat the decoding for Column~4 (with $e_1=1$ sector
failure) (Step 6).  We see that Row~5 now contains six available symbols, so we
can recover one unavailable virtual parity symbol (Step 7).  Then Column~5 (with
$e_2=2$ sector failures) now has four available symbols, so we can recover two
lost symbols (Step 8).  Now all chunks with sector failures are recovered.
Finally, we recover the $m=2$ lost chunks row by row using $\mc{C}_{row}$
(Steps 9-12).  Table~\ref{tab:recovery} lists the detailed decoding steps of
our example in Figure~\ref{fig:recover_step}.

\begin{table}[t]
  \centering

  \caption{Upstairs decoding: detailed steps for the example in Figure~\ref{fig:recover_step}. }
  \label{tab:recovery}

  \begin{tabular}{|c|c@{\ }c@{\ }c|c|}
  \hline

  \textbf{Step} & \multicolumn{3}{c|}{\textbf{Detailed Description}} & \textbf{Coding Scheme} \\
  \hline
  \hline
  1 & $d_{0,0}, d_{1,0}, d_{2,0}, d_{3,0}$ & $\Rightarrow$ & $d^*_{0,0}, d^*_{1,0}$ & $\mc{C}_{col}$ \\
  \hline
  2 & $d_{0,1}, d_{1,1}, d_{2,1}, d_{3,1}$ & $\Rightarrow$ & $d^*_{0,1}, d^*_{1,1}$ & $\mc{C}_{col}$ \\
  \hline
  3 & $d_{0,2}, d_{1,2}, d_{2,2}, d_{3,2}$ & $\Rightarrow$ & $d^*_{0,2}, d^*_{1,2}$ & $\mc{C}_{col}$ \\
  \hline
  4 & $d^*_{0,0}, d^*_{0,1}, d^*_{0,2}, g_{0,0}, g_{0,1}, g_{0,2}$ & $\Rightarrow$ & $d^*_{0,3}, d^*_{0,4}, d^*_{0,5}$ & $\mc{C}_{row}$ \\
  \hline
  5 & $d_{0,3}, d_{1,3}, d_{2,3}, d^*_{0,3}$ & $\Rightarrow$ & $d_{3,3}, d^*_{1,3}$ & $\mc{C}_{col}$ \\
  \hline
  6 & $d_{0,4}, d_{1,4}, d_{2,4}, d^*_{0,4}$ & $\Rightarrow$ & $d_{3,4}, d^*_{1,4}$ & $\mc{C}_{col}$ \\
  \hline
  7 & $d^*_{1,0}, d^*_{1,1}, d^*_{1,2}, d^*_{1,3}, d^*_{1,4}, g_{1,2}$ & $\Rightarrow$ & $d^*_{1,5}$ & $\mc{C}_{row}$ \\
  \hline
  8 & $d_{0,5}, d_{1,5}, d^*_{0,5}, d^*_{1,5}$ & $\Rightarrow$ & $d_{2,5}, d_{3,5}$ & $\mc{C}_{col}$ \\
  \hline
  9 & $d_{0,0}, d_{0,1}, d_{0,2}, d_{0,3}, d_{0,4}, d_{0,5}$ & $\Rightarrow$ & $p_{0,1}, p_{0,2}$ & $\mc{C}_{row}$ \\
  \hline
  10 & $d_{1,0}, d_{1,1}, d_{1,2}, d_{1,3}, d_{1,4}, d_{1,5}$ & $\Rightarrow$ & $p_{1,1}, p_{1,2}$ & $\mc{C}_{row}$ \\
  \hline
  11 & $d_{2,0}, d_{2,1}, d_{2,2}, d_{2,3}, d_{2,4}, d_{2,5}$ & $\Rightarrow$ & $p_{2,1}, p_{2,2}$ & $\mc{C}_{row}$ \\
  \hline
  12 & $d_{3,0}, d_{3,1}, d_{3,2}, d_{3,3}, d_{3,4}, d_{3,5}$ & $\Rightarrow$ & $p_{3,1}, p_{3,2}$ & $\mc{C}_{row}$ \\
  \hline
\end{tabular}
\end{table}

\subsubsection{General Case}
\label{subsec:general}

We now generalize the steps of upstairs decoding.

\textbf{(1) \emph{Decoding of the chunk with $e_0$ sector failures:}} It is
clear that there are $n-(m+m')$ good chunks without any sector failure in the
stripe.  We use $\mc{C}_{col}$ to encode each such good chunk to obtain
$e_{m'-1}$ virtual parity symbols.  Then each of the first $e_0$ augmented rows must
now have $n-m$ available symbols: $n-(m+m')$ virtual parity symbols that have just
been encoded and $m'$ global parity symbols.   Since an augmented row is a
codeword of $\mc{C}_{row}$ due to the homomorphic property, all the
unavailable symbols in this row can be recovered using $\mc{C}_{row}$.
Then, for the column with $e_0$ sector failures, it now has $r$ available
symbols: $r-e_0$ good symbols and $e_0$ virtual parity symbols that have just been
recovered. Thus, we can recover the $e_0$ sector failures as well as the
$e_{m'-1}-e_0$ unavailable virtual parity symbols using $\mc{C}_{col}$.

\textbf{(2) \emph{Decoding of the chunk with $e_i$ sector failures ($1 \leq i
\leq m'-1$):}}   If $e_i=e_{i-1}$, we repeat the decoding for the
chunk with $e_{i-1}$ sector failures.  Otherwise, if $e_i>e_{i-1}$, each of the
next $e_i-e_{i-1}$ augmented rows now has $n-m$ available symbols:
$n-(m+m')$ virtual parity symbols that are first recovered from the good
chunks, $i$ virtual parity symbols that are recovered while the sector
failures are recovered, and $m'-i$ global parity symbols. Thus, all the
unavailable virtual parity symbols in these $e_i-e_{i-1}$ augmented rows can
be recovered.
Then the column with $e_i$ sector failures now has $r$ available symbols:
$r-e_i$ good symbols and $e_i$ virtual parity symbols that have been recovered.
This column can then be recovered using $\mc{C}_{col}$.  We repeat this
process until all the $m'$ chunks with sector failures are recovered.

\textbf{(3) \emph{Decoding of the $m$ failed chunks:}} After all the $m'$
chunks with sector failures are recovered, the $m$ failed chunks can be
recovered row by row using $\mc{C}_{row}$.

\subsection{Decoding in Practice}
\label{subsec:practice}

In \S\ref{subsec:recovery_proof}, we describe an upstairs decoding method for
the worst case.   In practice, we often have fewer lost symbols than the
worst case defined by $m$ and $\mb{e}$.  To achieve efficient decoding, our
idea is to recover as many lost
symbols as possible via row parity symbols. The reason is that such decoding
is local and involves only the symbols of the same row, while decoding via
global parity symbols involves almost all data symbols within the stripe.  In
our implementation, we first locally recover any lost symbols using row parity
symbols whenever possible. Then, for each chunk that still contains lost
symbols, we count the number of its remaining lost symbols.  Next, we globally
recover the lost symbols with global parity symbols using upstairs decoding
as described in \S\ref{subsec:recovery_proof}, except those in the $m$ chunks
that have the most lost symbols.  These $m$ chunks can be finally recovered
via row parity symbols after all other lost symbols have been recovered.

config: arxiv


TITLE: Finding domain of $f\colon x\mapsto\sin^{-1}\frac{1+x^2}{2x}$
QUESTION [0 upvotes]: Consider $$\frac{1+x^2}{2x}$$ Dividing by $x\neq 0$, I get $$\dfrac{\frac{1}{x} + x}{2}\;$$ Now $$\left|\frac{\frac 1x + x}2\right|\geqslant 2$$
So, using this in original function, it's producing a range where $\sin^{-1}$ is not defined.
So the domain should be $\emptyset$.
But my textbook says it's the set of real numbers. Where am I wrong?

REPLY [0 votes]: You can see easily that $\frac{1+x^2}{2x}$ is always greater than $1$ or smaller that $-1$ (in fact taking the derivative you have $x^2-1=0$ and $1$ gives a minimun and $-1$ gives a maximun).
It follows that for all value of $x\notin\{-1,1\}$ the function
$$f\colon x\mapsto\sin^{-1}\frac{1+x^2}{2x}$$ is not defined, thus the domain of $f$ is the set $\{-1,1\}$ of just two points. There are maybe a typo in your book, in particular for $f=\sin$ instead of $f=\sin^{-1}$ all change.


TITLE: How to understand the Riemann surface of $\log z$ using the formal definition of Riemann surface?
QUESTION [5 upvotes]: I am a beginner studying Riemann surface. First things first, I learned about the definition of Riemann surface as follows.
Definition: A Riemann surface $X$ is defined by the following data:

a connected Hausdorff topological space $X$;
an open cover $\{U_\alpha\}_{\alpha\in A}$ of $X$;
for each $\alpha\in A$, a homeomorphism $\phi_\alpha:U_\alpha\rightarrow V_\alpha$ to an open subset $V_\alpha\subset\mathbb{C}$ in such a way that for each $\alpha,\beta\in A$, if $U_\alpha \cap U_\beta\neq \emptyset$, the transition functions
$$\phi_\beta\circ\phi^{-1}_\alpha:\phi_\alpha(U_\alpha\cap U_\beta)\rightarrow\phi_\beta(U_\alpha\cap U_\beta),$$
is bi-holomorphic, namely, holomorphic with inverse holomorphic.

We know the famous Riemann surface for $\log z$, which has the following shape

How can I describe such surface with the formal definition above? In other words, I need to construct a precise $U_\alpha$, $\phi_\alpha$ and transition map to describe the Riemann surface for $\log z$, not using intuitive words such as "gluing", "rotate", "visualized like parking lot" etc...
Thanks very much for your help.

REPLY [0 votes]: I am trying to describe the Riemann surface of $\log z$ using the fundemental definition of Riemann surface.
First, constructing a surface $X$ with coordinate $(r\cos\theta,r\sin\theta,\theta)$ where $-\infty<\theta<\infty$ and $0<r<1$. Clearly,$X$ is a Hausdorff topogical space, which satisfies condition 1.
Second, constructing a bunch of open set covering $X$. For arbitrary $x_\alpha=(r_\alpha \cos\theta_\alpha,r_\alpha\sin\theta_\alpha,\theta_\alpha)\in X$, there is a isomorphism $f:\{|z-z_\alpha|<\delta\}\rightarrow U_\alpha$ where $z_\alpha = r_\alpha e^{i\theta_\alpha\pi}$ and $\delta$ is suffiently small. Therefore $U_\alpha$ is an open set, and $\{U_\alpha\}$ covers $X$.
Third, constructing $\phi_\alpha:(r \cos\theta,r\sin\theta,\theta)\in U_\alpha\rightarrow \log r+i\theta\in V_\alpha$. Clearly, $V_\alpha\subset\mathbb{C}$, and $\phi_\alpha$ is homeomorphism. And the transition function $\phi_\beta\circ\phi_\alpha^{-1}$ is just a identity function, obviously holomorphic.
Now we have proved the Riemann surface for $\log z$ satisfies all three conditions of the fundemental definition.
Is my proof correct? Thanks for your criticize.


text:
{\bf Problem.} A spherical scoop of vanilla ice cream with radius of 2 inches is dropped onto the surface of a dish of hot chocolate sauce. As it melts, the ice cream spreads out uniformly forming a cylindrical region 8 inches in radius. Assuming the density of the ice cream remains constant, how many inches deep is the melted ice cream? Express your answer as a common fraction.
{\bf Level.} Level 4
{\bf Type.} Geometry
{\bf Solution.} The ice cream sphere has volume $\frac{4}{3}\pi(2^3) = \frac{32\pi}{3}$ cubic inches.  Let the height of the cylindrical region be $h$; then, the volume of the cylindrical region is $\pi (8^2)h=64\pi h$.  Thus, we have \[\frac{32\pi}{3} = 64\pi h.\] Dividing both sides by $64\pi$ yields $h = \boxed{\frac{1}{6}}$ inches.

set_name: MATH


text:
\begin{document}

\maketitle

\begin{abstract}
    We build on the work of Drakakis et al.\ (2011) on the maximal cross-correlation of the families
    of Welch and Golomb Costas permutations. In particular, we settle some of their conjectures.
    More precisely, we prove two results.

    First, for a prime $p\ge 5$, the maximal cross-correlation of the family of the $\varphi(p-1)$ different Welch Costas permutations of $\{1,\ldots,p-1\}$ is $(p-1)/t$, where $t$ is the smallest prime divisor of $(p-1)/2$ if $p$ is not a safe prime and at most $1+p^{1/2}$ otherwise. Here $\varphi$ denotes Euler's totient function and a prime $p$ is a safe prime if $(p-1)/2$ is also prime.

    Second, for a prime power $q\ge 4$ the maximal cross-correlation of a subfamily of Golomb Costas permutations of $\{1,\ldots,q-2\}$ is $(q-1)/t-1$ if~$t$ is the smallest prime divisor of $(q-1)/2$ if $q$ is odd and of $q-1$ if~$q$ is even provided that $(q-1)/2$ and $q-1$ are not prime, and at most $1+q^{1/2}$ otherwise.
        Note that we consider a smaller family than Drakakis et al. Our family is of size $\varphi(q-1)$ whereas there are $\varphi(q-1)^2$ different Golomb Costas permutations. The maximal cross-correlation of the larger family given in the tables of Drakakis et al.\ is larger than our bound (for the smaller family) for some $q$.
        \end{abstract}

{\bf MSC.} 05B15, 05A05, 94A05, 05B20

{\bf Keywords.} Costas arrays, permutations, cross-correlation, Welch construction, Golomb construction,
radar, sonar

\section{Introduction}

For a positive integer $n$, let $\pi$ be a permutation of $\{1,\ldots,n\}$ satisfying
$$\pi(i+k)-\pi(i)\ne \pi(j+k)-\pi(j)$$
for any integers $1\le k\le n-2$ and $1\le i<j\le n-k$.
Such a permutation is called a {\em Costas permutation} of $\{1,\ldots,n\}$
and the corresponding $(n\times n)$-permutation matrix $A=(a_{ij})_{i,j=1}^n$ defined by
$$a_{ij}=1 \mbox{ if and only if }\pi(i)=j$$
is called a {\em Costas array} of size $n$.
These objects are crucial in some problems arising from radar and sonar, see for example \cite[Section~7.6]{ju} and \cite{gota}.

The {\em cross-correlation $C_{f_1,f_2}(u,v)$} between two mappings
$$f_1,f_2:\{1,\ldots,n\}\rightarrow \{1,\ldots,n\}$$
at $(u,v)\in \Z^2$, $1-n\le u,v\le n-1$, is the number of solutions
$$x\in \{\max\{1,1-u\},\ldots,\min\{n,n-u\}\}$$
of the equation
\begin{equation}\label{cor} f_1(x)+v=f_2(x+u).
\end{equation}

For a family ${\cal F}$ of Costas permutations of $\{1,\ldots,n\}$, the {\em maximal cross-correlation} $C({\cal F})$ is
$$C({\cal F})=\max_{u,v} \max_{\genfrac{}{}{0pt}{}{f_1,f_2\in {\cal F}}{f_1\ne f_2}}C_{f_1,f_2}(u,v).$$
Studying the maximal cross-correlation of a family of Costas permutations is not only a very interesting mathematical problem, since families with small maximal cross-correlation are of high practical importance, see \cite{drakakis2011maximal} and references therein.

In this note, we study the maximal cross-correlation of two families of Costas permutations, the
family of Welch Costas permutations and a subfamily of Golomb Costas permutations defined below. In particular, we will address some open problems from \cite{drakakis2011maximal}.

{\em Welch's construction} of Costas permutations is defined as follows, see \cite{gota,ju}. For a prime $p>2$, let $g$ be a primitive root modulo $p$ and $\pi_g$ the permutation of $\{1,\ldots,p-1\}$ defined by
$$\pi_g(i) \equiv g^i \bmod p.$$
Then, for $p\ge 5$, the family ${\cal W}_p$ of Welch Costas permutations of $\{1,\ldots,p-1\}$ is
$${\cal W}_p=\{\pi_g : g \mbox{ primitive root modulo $p$}\},$$
so that,
$|{\cal W}_p|=\varphi(p-1),$
where $\varphi$ is {\em Euler's totient function}.

A prime $p$ is a {\em safe prime} if $(p-1)/2$ is also
a prime, called {\em Sophie Germain prime}.
Therefore,
$$|{\cal W}_p|=\frac{p-3}{2}\quad \mbox{if $p\ge 7$ is a safe prime}$$
and $|{\cal W}_5|=2$.

In this note we prove the following result on $C({\cal W}_p)$.

\begin{theorem}
\label{main}
For a prime $p\ge 5$, let $t$ be the smallest prime divisor of \hbox{$(p-1)/2$}. Then, the maximal cross-correlation $C({\cal W}_p)$ of the family of Welch Costas permutations ${\cal W}_p$ of $\{1,\ldots,p-1\}$ satisfies
$$C({\cal W}_p)\left\{\begin{array}{ll} \le 1+\lfloor(1-2/(p-1))p^{1/2}\rfloor & \mbox{if $p$ is a safe prime},\\
= (p-1)/t & \mbox{otherwise}.\end{array} \right.$$
\end{theorem}
Note that we can substitute each $\pi_g(i)$ by a shift $\pi_g(i+c_g)$ and get the same result.
However, ${\cal W}_p$ must not contain two shifts for the same primitive element~$g$.
In particular, for non-safe primes, Theorem~\ref{main} settles the first conjecture in
Drakakis et al.\ \cite[Conjecture 3]{drakakis2011maximal}.
We prove Theorem~\ref{main} in Section~\ref{secW}.

{\em Golomb's construction} of Costas permutations is the following, see \cite{comu,Golomb1984,ju,moso}. For a prime power $q>2$ and primitive elements $g_1$ and $g_2$ of the finite field $\F_q$, let $\pi_{g_1,g_2}$ be the permutation of $\{1,\ldots,q-2\}$ defined by
$$\pi_{g_1,g_2}(i)=h \mbox{ if and only if } g_1^i+g_2^h=1.$$
For $q\ge 4$ and fixed $g_2$ we study the subfamily ${\cal G}_q$ of the family of Golomb Costas permutations of $\{1,\ldots,q-2\}$ defined by
$${\cal G}_q=\{\pi_{g_1,g_2} : g_1 \mbox{ primitive element of $\F_q$}\}.$$
Then we have $|{\cal G}|_q=\varphi(q-1).$
In Section~\ref{golomb}, we prove the following result on $C({\cal G}_q)$.
\begin{theorem}\label{main2}
 For a prime power $q\ge 4$, let $t$ be the smallest prime divisor of \hbox{$(q-1)/2$} if $q$ is odd and
 of $q-1$ if $q$ is even. Then, the maximal cross-correlation $C({\cal G}_q)$ of the family of Golomb Costas permutations ${\cal G}_q$ of $\{1,\ldots,q-2\}$ satisfies
 $$C({\cal G}_q)\left\{\begin{array}{ll}\le 1+\lfloor (1-2/(q-1))q^{1/2}\rfloor & \mbox{if $q$ is odd and }t=(q-1)/2,\\
 \le \lfloor(1-1/(q-1))(1+q^{1/2})\rfloor & \mbox{if $q$ is even and $t=q-1$},\\
 = (q-1)/t-1 & \mbox{otherwise}.\end{array}\right.$$
\end{theorem}

Besides $C({\cal G}_q)$, it is interesting to study the cross-correlation $C({\cal L}_q)$
of the larger set ${\cal L}_q$ of all Golomb Costas permutations
$${\cal L}_q=\{\pi_{g_1,g_2}: g_1,g_2 \mbox{ primitive elements of }\F_q\}$$
of size
$$|{\cal L}_q|=\varphi(q-1)^2.$$
The tables of \cite{drakakis2011maximal} show that $C({\cal L}_q)$ is larger than $C({\cal G}_q)$ for some small values of $q$.
For example, for $q=59$, we have $C({\cal L}_{59})=12$ but $C({\cal G}_{59})\le 8$.
However, for all prime values of $q$ with $61\le q\le 271$ and all strict prime powers $25\le q\le 343$, the bound of Theorem~\ref{main2} is also valid for $C({\cal L}_q)$.
It remains an open problem to prove the conjecture that this bound holds for $C({\cal L}_q)$ up to a few exceptions of $q$ with~$q\le 59$.

\section{Proof of Theorem~\ref{main}}
\label{secW}

By \cite[Theorem~1]{drakakis2011maximal}, we have
$$\max_{u\in \Z} \max_{\genfrac{}{}{0pt}{}{f_1,f_2\in {\cal W}}{f_1\ne f_2}}C_{f_1,f_2}(u,0)=\frac{p-1}{t}.$$
Since $t\le \sqrt{(p-1)/2}$ if $p$ is not a safe prime, it remains to prove the following lemma, from which Theorem~\ref{main} follows immediately
after verifying
$$\frac{p-1}{t}\ge \sqrt{2(p-1)}\ge 1+p^{1/2}\quad \mbox{for }p\ge 11$$
and that $5$ and $7$ are both safe primes.

\begin{lemma}\label{Welch}
For any prime $p\ge 5$ we have
$$\max_u \max_{v\ne 0}\max_{\genfrac{}{}{0pt}{}{f_1,f_2\in {\cal W}_p}{f_1\ne f_2}}C_{f_1,f_2}(u,v)\le 1+\left\lfloor\left(1-\frac{2}{p-1}\right)p^{1/2}\right\rfloor.$$
\end{lemma}
Proof.
The maximum in the statement can be bounded by the maximal number $N$ of solutions
$x\in \F_p^*$ of any equation of the form
\begin{equation}\label{eq} ax^r\equiv x+v \bmod p,\quad \mbox{with } av\not\equiv 0\bmod p,\quad
\gcd(r,p-1)=1,~1<r<p-1,
\end{equation}
since, if $g$ is a fixed primitive root modulo $p$, all other primitive roots modulo~$p$
are of the form $g^r$ with $\gcd(r,p-1)=1$.
For fixed $a$ and $v$ with $av\not\equiv 0\bmod p$, the number of solutions of $(\ref{eq})$
is
$$\frac{1}{p-1}\sum_{\chi} \sum_{x\in \F_p^*\setminus\{-v\}} \chi(ax^r)\overline{\chi}(x+v)$$
by the orthogonality relations
$$\frac{1}{p-1}\sum_{\chi}\chi(x)\overline{\chi}(y)=\left\{\begin{array}{cc} 1, & x=y,\\ 0, & x\ne y,\end{array}\right\} \quad\mbox{for all } x,y \in \F_p^*,$$
where the sum runs through all multiplicative characters $\chi$ of $\F_p$.

The contribution of the trivial character $\chi_0$ is $(p-2)/(p-1)$ and that of the quadratic character $\eta$ is
$-\eta(a)/(p-1)$ by \cite[Lemma 7.3.7]{ju}.
Thus,
\begin{eqnarray*}
N&\le& 1+\frac{p-3}{p-1}\max_{v\in \F_p^*}\max_{\chi\not\in\{\chi_0,\eta\}}\left|\sum_{x\in \F_p^*}\chi(x^r(x+v)^{p-2})\right|\\
&\le& 1+\left(1-\frac{2}{p-1}\right)p^{1/2}
\end{eqnarray*}
by the Weil bound, see for example \cite[Theorem 5.41]{LN}.~\hfill $\Box$

\section{Proof of Theorem~\ref{main2}}
\label{golomb}
For $u=v=0$, we have, by \cite[Theorem~3]{drakakis2011maximal}
$$ \max_{\genfrac{}{}{0pt}{}{f_1,f_2\in {\cal G}_q}{f_1\ne f_2}}C_{f_1,f_2}(0,0)=\frac{q-1}{t}-1,
$$
where $t$ is the smallest prime divisor of $(q-1)/2$ if $q$ is odd and of $q-1$ if $q$ is even.

Next we prove an upper bound for $v=0$ and arbitrary $u$.
\begin{lemma}\label{gol0}
 We have
 $$\max_{u} \max_{\genfrac{}{}{0pt}{}{f_1,f_2\in {\cal G}_q}{f_1\ne f_2}}C_{f_1,f_2}(u,0)\le
  \frac{q-1}{t}-1$$
  if $t\not\in\{(q-1)/2,q-1\}$
  and
  $$\max_{u} \max_{\genfrac{}{}{0pt}{}{f_1,f_2\in {\cal G}_q}{f_1\ne f_2}}C_{f_1,f_2}(u,0)\le 2$$
  otherwise.
\end{lemma}
Proof.
Since
$$C_{f_1,f_2}(-u,0)=C_{f_2,f_1}(u,0)$$
we may assume $u\ge 1$.
Let $f_1$ and $f_2$ be defined by $f_1(x)=h$ if and only if $g_1^x+g_2^h=1$ and
$f_2(x)=h$ if and only if $g_1^{xr}+g_2^h=1$, respectively, for some integer $r$ with $\gcd(r,q-1)=1$ and
$1<r<q-1$. Then, the number of solutions~$x$ of $(\ref{cor})$ with $v=0$ (and $n=q-2$) is the number of integers $x$ in the range $1\le x\le q-2-u$ such that
$$ g_1^x=g_1^{(x+u)r},$$
that is, $x$ satisfies
$$(r-1)x\equiv -ur \bmod (q-1).$$
Put $d=\gcd(r-1,q-1)$ and let $a$ be the inverse of $(r-1)/d$ modulo $(q-1)/d$.
There is no solution if $d$ does not divide~$u$. Otherwise, the solutions
are those $x$ with
\begin{equation}\label{equal}x\equiv -a(u/d)r \bmod (q-1)/d.
\end{equation}
We have at most $d$ such solutions $x$ with $1\le x\le q-2$.
Obviously, we have $d\le (q-1)/t$.
The result follows immediately if $d< (q-1)/t$. It remains to study the case
$d=(q-1)/t$.
Then either
$$u\ge d=(q-1)/t\ge (q-1)^{1/2}\ge t$$ or
$$\mbox{for $q$ odd}, \quad t=(q-1)/2 \mbox{ and }d=2 $$
and
$$\mbox{for $q$ even}, \quad t=q-1 \mbox{ and }d=1.$$
In the fist case, the solutions $x$ of~$(\ref{equal})$ are of the form $x=x_0+kt$ with $1\le x_0\le t$ and
$0\le k\le d-1$. However, $k=d-1$ is not possible since
$$x_0+(d-1)t> q-1-t>q-2-(q-1)^{1/2}\ge q-2-d\ge q-2-u$$
and there are at most $d-1=(q-1)/t-1$ solutions.
In the remaining cases we have at most $2$ solutions.
~\hfill $\Box$\\

For $v\ne 0$, analogously to Lemma~\ref{Welch}, we get the following bound.
\begin{lemma}\label{gol1}
For odd $q$, we have
$$\max_u \max_{v\ne 0} \max_{\genfrac{}{}{0pt}{}{f_1,f_2\in {\cal G}_q}{f_1\ne f_2}}(u,v)\le 1+\left\lfloor\left(1-\frac{2}{q-1}\right)q^{1/2}\right\rfloor$$
and, for even $q$,
$$\max_u \max_{v\ne 0}\max_{\genfrac{}{}{0pt}{}{f_1,f_2\in {\cal G}_q}{f_1\ne f_2}}(u,v)\le \left\lfloor\left(1-\frac{1}{q-1}\right)\left(1+q^{1/2}\right)\right\rfloor.$$
\end{lemma}
Proof.
Again, let $f_1(x)=h$ whenever $g_1^x+g_2^h=1$ and $f_2(x)=h$ whenever $g_1^{rx}+g_2^h=1$
for some $r$ with $\gcd(r,q-1)=1$ and $1<r<q-1$. Then, $(\ref{cor})$ implies
$$g_2^v(1-g_1^x)=1-g_1^{r(x+u)}.$$
Substituting $y=1-g_1^x$, $a=g_2^v$ and $b=g_1^{ru}$, we get
$$ay=1-b(1-y)^r.$$
Note that $a\ne 1$ since $v\not= 0$ and $y\not\in\{0,1\}$ since $1\le x\le q-2$.
Hence, we have to estimate the number $N$ of solutions of equations of the form
$$b(1-y)^r=1-ay,\quad y\in \F_q^*\setminus\{1\},$$
for any $a\in \F_q^*\setminus\{1\}$ and $b\in \F_q^*.$
We can represent $N$ by character sums
$$N=\frac{1}{q-1} \sum_{\chi} \sum_{y\in \F_q^*\setminus\{1\}} \chi(b) \chi((1-y)^r(1-ay)^{q-2}).$$
The contribution of the trivial character is $(q-2)/(q-1)$ and, for odd $q$, that of
the quadratic character is $-\chi(b)/(q-1)$. For the remaining characters, the absolute value of the inner sum is at most $q^{1/2}$.
Collecting these facts, the result follows.~\hfill $\Box$\\

Theorem~\ref{main2} is proved by combining Lemmas~\ref{gol0} and \ref{gol1},
after verifying that $t<(q-1)/2$ implies the following results.

For any odd $q$, we have $t\le \sqrt{\frac{q-1}{2}}$, and thus
$$1+q^{1/2}\le \frac{q-1}{t}-1 \quad \mbox{for any odd $q\ge 27$}.$$
For the remaining odd $q$ with $q\le 25$, the following refinement holds,
$$1+\left\lfloor\left(1-\frac{2}{q-1}\right)q^{1/2}\right\rfloor\le \frac{q-1}{t}-1.$$

For even $q\ge 4$, by Mih\u ailescu’s Theorem (former Catalan conjecture), $q-1$ is not a perfect square and thus $q-1\ge t(t+2)$, that is, $t\le -1+q^{1/2}$.

If $q=2^r$ with an odd $r$, then
$$1+\lfloor q^{1/2}\rfloor < 1+ q^{1/2}\le \frac{q-1}{t}.$$
If $q=2^r$ with an even $r$, then $t=3$ and
$$1+q^{1/2}\le \frac{q-1}{3}-1 \quad \mbox{for $q\ge 64$}.$$
In the remaining case, that is $q=16$, the more precise bound of Lemma 3 equals $(q-1)/t-1=4$.~\hfill $\Box$

\section*{Acknowledgments}

The first author is partially supported
by the Consejer\'ia de Universidades e Investigaci\'on, Medio Ambiente y Politica Social del Gobierno de Cantabria, reference number Vp34.

The second author is partially supported by the Austrian Science Fund FWF Project P 30405-N32.


TITLE: What is the average distance in 1D Brownian motion?
QUESTION [1 upvotes]: I would like to understand the time-dependence of the average distance from the start-point in 1D Brownian motion. It's said the expected distance in Brownian motion is 0, which I would call the average end-position, including (-) signs. But here I am interested in the average distance using only (+) signs!
It's said the expected "spread" is √t (p,q .. probability for left,right, t.. time). Unfortunately I am not sure if "spread" is what I am looking for. For this reason I would like to ask in the form of this specific example, so that misunderstandings are prevented:
Imagine an object randomly moving either left or right, with P(left)=0.25 and P(right)=0.75! Each "time" it moves by length 1. I would like to understand how to calculate the average distance from the start point after e.g. 100 times.
I know how to calculate the average distance based on the Binomial distribution:
P(48 x left, 52 x right) x2 + P(53 x left, 47 x right) x3 + .. every outcome-probability x distance .. you get the idea!
So is there a formula to calculate this "average distance"? I would especially be interested in the time-dependence.

REPLY [2 votes]: It sounds, from comments, that you want, for fixed time $t$, the expected value of the absolute value of where a Brownian motion particle is, assuming it started at $0$ at time $t=0$.  That is, you want $E[ |B(t) |]$.
(As if you released a zillion BM particles at $0$ at time $0$, and at some later $t$ each sends in a report telling how far from $0$ it is just then, and you take the average of all those  reported distances.)
Since $B(t)\sim N(0,t)$, you want $\sqrt t$ times the expected value of the absolute value of  standard normal random variable:
$$ E[|B(t)|] = \frac {2\sqrt t} {\sqrt{2\pi}} \int_0^\infty x e^{-x^2/2}dx = \sqrt{\frac {2t} \pi}.$$


TITLE: Galois group of $f(X) = X^4 + 3X^2 + 1$
QUESTION [3 upvotes]: I'm trying to compute the Galois group $G$ of $$f=X^4 + 3X^2 + 1$$ over $\mathbb{Q}$. This is what I worked out so far:

The discriminant is $2^4\cdot 5^2$, a square, so $G\subset A_4$
$f$ is irreducible, as one can see by the Cohn's criterion with the
prime $10301$, hence $G$ is a transitive subgroup of $S_4$
$f$ can be rewritten as $Y^2+3Y+1$, so the roots are easily found by
the quadratic formula. It turns out that they are all pure
imaginary, namely $$ \pm\sqrt{\frac{-3\pm\sqrt{5}}{2}} $$ From this
I deduce that (denote by $K$ the splitting field of $f$)
$[K:\mathbb{Q}] = 4$, and so also $|G|=4$. The only candidates for
$G$ are therefore the Klein group $V_4$ or the cyclic $C_4$.
With Mathematica I computed the factorisations of $f$ modulo $p$ for the first
$1000$ primes, and $f$ is never irreducible. This strongly suggests
that $G=V_4$, because it looks like it doesn't contain any
$4$-cycle.

If you agree with my reasoning, please can you help me to prove that the Galois group is actually $V_4$? Otherwise shame on me! ;-)

REPLY [1 votes]: But C4 is not in A4, right? So once you know that |G|=4 you know that G=V4.


TITLE: Finding a planar graph satisfying these properties
QUESTION [5 upvotes]: I need to construct a 3-regular connected planar graph with a planar embedding where each face has degree 4 and 6. In addition, each vertex must be incident with exactly one face of degree 4.

seems to fit the description well if extended infinitely but unfortunately infinite graphs are not allowed. I spent so much time trying to construct such a graph! The hard part is that there is that annoying unbounded face outside everything...

REPLY [2 votes]: The colours show the order in which I constructed the graph. Every vertex must be part of one face of order 4, so I start with a square (black, centre).
Now, each vertex is of order 3, and the four vertices have order 2, so extend one edge out from each. They're next to their face of order 4, so these edges must be parts of hexagons (blue).
We now have four vertices which are already of order 3 and missing their face of order 4, and eight vertices which are of order 2 and missing their face of order 4. Create the suitable faces (red).
Now each "edge" of the square formed by the red edges is really three edges, and they must each form part of a hexagon. The 4 corners of the red square are order 2, so they need one more edge each, and that brings us to 5 of the 6 edges of each hexagon, so just join them up in the green square.
Check: the outside face is also of order 4, so this works.


TITLE: I don't fully understand why Pythagorean theorem works with velocity vectors.
QUESTION [2 upvotes]: I get why it works with displacement because that's what the theorem was originally meant for, lengths.... I find it harder to wrap my head around it when its velocity. If anyone has a good visualization or anything that will help me understand It will really help. I scoured the internet for a while but all of them were just:-  put V(y) velocity arrow perpendicular to V(x) head ,for some reason this explanation isn't working out for me.... well looking forward to the responses!
cheers!

REPLY [2 votes]: In Euclidean space, the Pythagorean theorem tells us for orthogonal vectors $u,v,$
$$\|u+v\|^2=\|u\|^2+\|v\|^2.$$

I get why it works with displacement because that's what the theorem was originally meant for, lengths

Go back to what a vector in Euclidean space is: an object with direction and length. The vector may represent many things, e.g. displacement, velocity, acceleration, force, electric field etc. Since vectors have a notion of length, applying Pythagorean theorem makes perfect sense if the vector quantity obeys the superposition principle.

REPLY [2 votes]: It works because a right triangle of velocity vectors is just a right triangle of displacement vectors, all divided by the same constant time increment.

REPLY [1 votes]: Suppose you’re on a ship moving with velocity $v_1$ (relative to the shore) and you’re walking with velocity $v_2$ (relative to the ship). In time $\Delta t$ the ship is displaced by $v_1 \Delta t$ (relative to the shore) and you are displaced by $v_2 \Delta t$ (relative to the ship). Your displacement relative to the shore is $(v_1 + v_2) \Delta t$. So your velocity relative to the shore is $v = v_1 + v_2$. If $v_1 \perp v_2$, then the Pythagorean theorem (which holds whenever we add orthogonal vectors) tells us that $\| v \|^2 = \| v_1 \|^2 + \| v_2 \|^2$.
If you’d like, you could apply the Pythagorean theorem to the displacement vectors then divide by $\Delta t^2$ to obtain the Pythagorean theorem for the velocity vectors.


text:
(***********************************************************************************
 * Copyright (c) 2016-2018 The University of Sheffield, UK
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * * Redistributions of source code must retain the above copyright notice, this
 *   list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * SPDX-License-Identifier: BSD-2-Clause
 ***********************************************************************************)

section\<open>Object\<close>
text\<open>In this theory, we introduce the typed pointer for the class Object. This class is the
common superclass of our class model.\<close>
theory ObjectPointer
  imports
    Ref
begin

datatype 'object_ptr object_ptr = Ext 'object_ptr
register_default_tvars "'object_ptr object_ptr"

instantiation object_ptr :: (linorder) linorder
begin
definition less_eq_object_ptr :: "'object_ptr::linorder object_ptr \<Rightarrow> 'object_ptr object_ptr \<Rightarrow> bool"
  where "less_eq_object_ptr x y \<equiv> (case x of Ext i \<Rightarrow> (case y of Ext j \<Rightarrow> i \<le> j))"
definition less_object_ptr :: "'object_ptr::linorder object_ptr \<Rightarrow> 'object_ptr object_ptr \<Rightarrow> bool"
  where "less_object_ptr x y \<equiv> x \<le> y \<and> \<not> y \<le> x"
instance by(standard, auto simp add: less_eq_object_ptr_def less_object_ptr_def
      split: object_ptr.splits)
end

end

subset_name: curated


TITLE: Prove that the length of a curve is given by integral
QUESTION [3 upvotes]: I have found the following problem in "Introduction to Analysis" by Rosenlicht. I am not sure if my solution is correct and I highlighted my uncertainties.

First we have to show that the set $$S=\Bigg\{\sum_{i=1}^N d(f(x_{i-1}),f(x_i)):x_0,x_1,\ldots , x_N \mbox{ is a partition of } [a,b]\Bigg\}$$ is bounded from above and that the sequence of the above sums is increasing as the mesh of the partition goes to $0$, so this sequence necessarily converges to $\sup S$.

I'm not even sure if the above part is correct and how to formally show it. It is crucial for the later part.

Next, since $\sqrt{(f_1^{'}(x))^2+\ldots+(f_n^{'}(x))^2}$ is continuous on $[a,b]$, the integral $$\int_a^b \sqrt{(f_1^{'}(x))^2+\ldots+(f_n^{'}(x))^2} dx $$ exists.
Fix a partition $x_0,x_1,\ldots , x_N$ of $[a,b]$.
From the mean value theorem we know that for $j=1,\ldots,n$ if $x_{i-1}$ and $x_i$ are two points from $[a,b]$ such that $x_{i-1}<x_i$ then there exists some $\zeta_{i}^j$ between them and
$$f_j(x_i)-f_j(x_{i-1})=f'_j(\zeta_{i}^j)(x_i-x_{i-1})\mbox{.}$$
We have:
$$\sum_{i=1}^N d(f(x_{i-1}),f(x_i))=\sum_{i=1}^N \sqrt{(f_1(x_{i-1})-f_1(x_{i}))^2+\ldots+(f_n(x_{i-1})-f_n(x_{i}))^2}=$$
$$=\sum_{i=1}^N \sqrt{(f^{'}_1(\zeta_i^1))^2+\ldots+(f^{'}_n(\zeta_i^n))^2}(x_i-x_{i-1}) \mbox{.}$$

Intuition tells me that this is okay, but how can I formally show that it does not matter if $\zeta_i^1,\ldots, \zeta_i^n$ are different, as long as they are "trapped" between $x_{i-1}$ and $x_i$?

If we go with the mesh of the partition to $0$, then the above sum converges to the integral $$\int_a^b \sqrt{(f_1^{'}(x))^2+\ldots+(f_n^{'}(x))^2} dx $$ which is equal to $\sup S$.

REPLY [1 votes]: As for your first question: note that $f$ as a continuosly differentiable curve is Lipshitz continuous and the derivate (since it is continuous by assumption) is bounded, so $f$ is Lipschitz continuous with a bound on the Lipschitz constant $L$ given by a norm bound for the derivative. So your set is bounded by $L(b-a)$.
For your second question it is possible to show that, for continously differentiable $f$, the following is true: to $\varepsilon>0$ there is $\delta >0$ such that $|t-s|< \delta \Rightarrow$
$$ (\#)\quad\quad\quad\quad\quad\quad\quad ||\frac{f(t)-f(s)}{t-s} - f^\prime(t)||\le \varepsilon $$
(note the choice of the argument of $f^\prime$). If you can show this your second question will be resolved. $(\#)$ is a consequence of the mean value theorem the way you used it and uniform continuity of $f^\prime$.
Edit: more detailed explanation of the last remark.
To derive the result from $(\#)$ recall first that, for the Riemannian integral and the Riemann integrable function $||f^\prime(t)||$ and given $\varepsilon > 0$, for any sufficiently fine partition $a= t_0<t_1< \ldots < t_N=b$, e.g. for $|t_i-t_{i-1}|<\delta$,
$$(*)\quad\quad \quad\quad\quad\left|\int_a^b ||f^\prime(t)|| dt - \sum\limits_{i=1}^N ||f^\prime(t_i)||(t_i-t_{i-1})\right| < \varepsilon $$
If the partition is fine enough we can apply $(\#)$ for adjacent values $t_k, t_{k-1}$ in this partition, use the triangle inequality and multiply by $t_k-t_{k-1}$ to get
$$(**) \quad\quad \quad \left|\, ||f(t_k)-f(t_{k-1})||-||f^\prime(t_k)|| (t_k-t_{k-1}) \right|\le \varepsilon(t_k-t_{k-1})$$
Now it's just a matter of putting things together: we look at the expression wich should become arbitrarily small, less than $\varepsilon^*$, say:
$$
(***)\quad\quad\quad \quad\quad\left|\sum_{i=1}^N ||f(t_i)-f(t_{i-1})|| - \int_a^b ||f^\prime(t)||\,dt\right|
$$
and add and subtract under the norm the term
$$ \sum_{i=1}^N ||f^\prime(t_i)||(t_i-t_{i-1})$$
By the triangle inequality, $(***)$ is bounded from above by
$$\left|\sum_{i=1}^N ||f(t_i)-f(t_{i-1})|| -  \sum_{i=1}^N ||f^\prime(t_i)||(t_i-t_{i-1})\right|+\left| \sum_{i=1}^N ||f^\prime(t_i)||(t_i-t_{i-1})- \int_a^b ||f^\prime(t)||\,dt \right|$$
Here the second term is bounded by $\varepsilon$ according to $(*)$. The first one is bounded, according to $(**)$ by
$$\sum_{i=1}^N \varepsilon (t_i-t_{i-1})= (b-a)\varepsilon$$
So by making $\varepsilon $ so small that $(b-a+1) \varepsilon <\varepsilon^*$ we may choose the partition fine enough and the result follows.
(You may have noticed that I did not provide a proof of $(\#)$, only a hint on how to prove it, i.e. I left you some work to do on your own).


TITLE: Showing that $\{(x,y):x-y\ne 2\}$ in $\mathbb{R}^2$ is open
QUESTION [2 upvotes]: Let $A=\{(x,y):x-y\ne 2\}$ be a subspace of $\mathbb{R}^2$. Would it be correct to argue that this set is open because for any $\vec{x}\in A$, we can pick $\varepsilon=\Vert \vec{x}-proj_{x-y=2}(\vec{x})\Vert >0$ so that $B_\varepsilon(\vec{x})\in A$. Thus $A$ is open.
I'm wondering if my definition of the $\varepsilon$ is correct, since $x-y=2$ does not go through the origin and is thus probably not a vector space. Alternatively, we could define this distance as $\frac{\lvert y_0-x_0-2\lvert}{\sqrt{2}}$, where $\vec{x}:=(x_0, y_0)$.

REPLY [2 votes]: The questions already been answered, but I thought I would try one with just inequalities (and avoiding the messy calculations). Let $(x,y)\in A$. Then either $x-y>2$ or $x-y<2$. The cases are similar, so assume that $x-y>2$. Then there is a real number $r$ such that $x-y>r>2$. Define $\epsilon = \frac{r-2}{2} > 0$.
We will now show that $B_\epsilon(x,y)\subset A$. For $(x_1,y_1)\in B_\epsilon(x,y)$, we have $$x_1 - y_1 > (x-\epsilon) - (y+\epsilon) = x-y -2\epsilon > r-2\epsilon = 2.$$ So $x_1-y_1>2$ and $(x_1,y_1)\in A$. Therefore $B_\epsilon(x,y)\subset A$.
Checking the $x-y<2$ case is nearly identical. Thus $A$ is open.


TITLE: A positive constant bounding all $L^p$-norm of a function for $p>1$
QUESTION [2 upvotes]: Prove or disprove: If there exists a positive constant $M$ such that $||f||_{L^p(\mathbb{R})}<M$ for any $p > 1$, then $f \in L^1(\mathbb{R})$.

We have $$\left(\int_{\mathbb{R}}|f|^p\right)^{1/p} < M \implies \int_\mathbb{R}|f|^p < M^p.$$ Thus $f \in L^p(\mathbb{R})$. But since $1 < p$, wouldn't it automatically mean that $f \in L^1(\mathbb{R})$?
Anyway, I'm thinking of using Holder's inequality to prove that the statement is true, since on the left side we will always have $||f||_1$. Let $1<p,p'<\infty$ such that $\frac{1}{p}+\frac{1}{p'}=1$, then we have $$||f||_1 \leq ||f||_p||f||_{p'}$$ and so $$\int _\mathbb{R}|f| \leq \left(\int_\mathbb{R}|f|^p\right)^{\frac{1}{p}}\left(\int_\mathbb{R}|f|^{p'}\right)^{\frac{1}{p'}}<M\cdot M = M^2.$$ Hence $f \in L^1(\mathbb{R})$. Did I miss out anything?
EDIT. I forgot that the left side should be a product of functions, let me rewrite it as: $$\int_\mathbb{R}f^2 < M^2$$ which doesn't seem helpful. Also, $\mathbb{R}$ has infinite measure. I'm starting to think that this statement is false.

REPLY [2 votes]: This is an immediate consequence of Fatou's Lemma. We have $\int |f|^{p} \leq M^{p}$. Letting $p \to 1$ ,say through the sequence $(1+\frac 1 n)$, we get $\int |f| \leq \lim \inf \int |f|^{p}\leq \lim \inf M^{p}=M$.


TITLE: Write the expression in terms of a single sin $-\sqrt{3} \sin x + \cos x$
QUESTION [0 upvotes]: Write the expression in terms of a single sin
$$ -\sqrt{3}\sin x + \cos x$$
So this was a question on my test today. I used a cofunction identity to solve it. Can someone tell me what the correct answer is. I think mine was something like $1-\sqrt{3}\sin x +1$ or something like that.

REPLY [1 votes]: \begin{align}
-\sqrt{3}\sin x + \cos x
&=
-2(\sin x\cos(-\tfrac\pi6) +\cos x\sin(-\tfrac\pi6))
=-2\sin(x-\tfrac\pi6)
\end{align}

REPLY [1 votes]: We have:
$$
-\sqrt{3}\sin x + \cos x=\\
=2\left(-\frac{\sqrt{3}}{2}\sin x + \frac{1}{2}\cos x\right)=\\
=2\left(\cos\frac{5\pi}{6}\sin x + \sin\frac{5\pi}{6}\cos x\right)=\\
=2\sin\left(\frac{5\pi}{6}+x\right).
$$
Notice that:
$$
2\sin\left(x+\frac{5\pi}{6}\right)=
-2\sin\left(x-\frac{\pi}{6}\right)=
-2\sin\left(x+\arctan\left(-\frac{1}{\sqrt 3}\right)\right).
$$


TITLE: A trivial question about the $n^{\text{th}}$ prime number
QUESTION [2 upvotes]: I would like to ask for a little help about a very trivial question from the number theory.

If $p_{n}$ is the $n^{\text{th}}$ prime number in the ascending sequence of prime numbers, show that $$p_{n}\sim n \log(n).$$

I am pretty sure, we should use the prime number theorem, which says that $$\mathbb{P}(x) = \sum_{p\leq x}1 \sim \frac{x}{\log(x)} $$ where $p$ is a prime number.
I would be glad if someone could help me with the idea. Thanks in advance!

REPLY [3 votes]: At the lowest level, this isn't a question about prime numbers at all; instead, it's a question about finding the inverse to the function $f(x) = \frac{x}{\log x}$.  A classic method for (asymptotically) approximating inverses is bootstrapping: start with some reasonable guess, 'plug it in' to the functional equation (in some form) to get a better approximation, and continue until your approximation stops getting better (or you get enough terms).
In this case, we want to find a $g(n)$ such that $n = \frac{g(n)}{\log g(n)}$; rearranging this gives $g(n) = n\log g(n)$, which seems like a fine place to start the bootstrapping.  A reasonable first guess is simply $g_0(n)=n$ (note that starting with a constant $g_0()$ would lead to a linear guess on the first iteration); plugging this in to the equation yields, successively:
$$g_1(n) = n\log g_0(n) = n\log n$$
$$g_2(n) = n\log g_1(n) = n\log(n\log n) = n(\log n+\log\log n)$$
$$g_3(n) = n\log\left(n\log n+n\log\log n\right) = n\log\left(n\log n\cdot\left(1+\frac{\log\log n}{\log n}\right)\right)\\=n\left(\log n+\log\log n+\log\left(1+\frac{\log\log n}{\log n}\right)\right)\\=n\left(\log n+\log\log n+\frac{\log\log n}{\log n}+o\left(\frac{\log\log n}{\log n}\right)\right)$$
In the case to hand, of course, there are error terms in the original approximation $\pi(n) = \frac{n}{\log n}$ that make the higher-order terms here less relevant, but a slightly more careful bootstrapping will show that the top-order $\theta(n\log n)$ term survives unscathed; the exact expression, as per Wikipedia, is:
$$\frac{p_n}{n} = \log n+\log\log n-1+O\left(\frac{\log\log n}{\log n}\right)$$