TITLE: Prove that three segments in a convex hexagon intersect at one point
QUESTION [5 upvotes]: Let $ABCDEF$ be convex hexagon such that $\angle ABC=\angle BCD=\angle DEF=\angle EFA$ and $|AB|+|DE| =|AF|+|CD|$.
Prove that line $l_{AD}$ and perpendicular bisectors of sides $\overline{BC}$ and $\overline{EF}$ intersect at some point.
This is the diagram:

As you can see, I prolonged segments $\overline{CD}$ and $\overline{AB}$ to intersect at $X$ and, similarly, $\overline{DE}$ and $\overline{AF}$ to intersect at $Y$. Then, as $\angle ABC=\angle BCD$, we have that triangle $\triangle BXC$ is equilaterial and the perpendicular bisector of the side $\overline{BC}$ is in fact the bisector of the angle $\angle BXC$, and, similarly, perpendicular bisector of $\overline{FE}$ bisects $\angle EYF$.
But what now? Any hints?

REPLY [1 votes]: Let me write another solution. Using your picture, $XC=XB$ and $EY=FY$. It follows that $$AX+DY=BX+AB+ED+EY=CX+AF+CD+FY=AY+DX,$$ therefore quadrilateral $AXDY$ is circumscribed. Let $I$ be the center of the circle inscribed in $AXDY$.
Note that the perpendicular bisectors of $BC$ and $EF$ are angle bisectors of $BXC$ and $EYF$. This is because triangles $BXC$ and $EYF$ are isosceles. Thus we only need to prove that $I$ lies on $AD$.
Let $\alpha$ be the common value of angles $ABC, BCD, DEF, EFA$. The internal angle $AID$ in the pentagon $AIDEF$ is equal to
$$540^\circ - \angle IDE - \angle DEF - \angle EFA - \angle FAI = 540^\circ - \frac 12 \angle CDE - 2\alpha - \frac 12 \angle FAB. $$
Similarly , the internal angle $DIA$ in the pentagon $DIABC$ is equal to
$$540^\circ - \angle IAB - \angle ABC - \angle BCD - \angle CDI = 540^\circ - \frac 12 \angle FAB - 2 \alpha - \frac 12 \angle CDE.$$
It follows that these two angles are equal. On the other hand, they add up to $360^\circ$, so $\angle AID = 180^\circ$. Therefore $I$ lies on $AD$.


text:
{\bf Problem.} Let $\mathcal{R}$ be the region consisting of the set of points in the coordinate plane that satisfy both $|8 - x| + y \le 10$ and $3y - x \ge 15$. When $\mathcal{R}$ is revolved around the line whose equation is $3y - x = 15$, the volume of the resulting solid is $\frac {m\pi}{n\sqrt {p}}$, where $m$, $n$, and $p$ are positive integers, $m$ and $n$ are relatively prime, and $p$ is not divisible by the square of any prime. Find $m + n + p$.

{\bf Level.} Level 5
{\bf Type.} Geometry
{\bf Solution.} [asy]size(280); import graph; real min = 2, max = 12; pen dark = linewidth(1);   real P(real x) { return x/3 + 5; } real Q(real x) { return 10 - abs(x - 8); } path p = (2,P(2))--(8,P(8))--(12,P(12)), q = (2,Q(2))--(12,Q(12)); pair A = (8,10), B = (4.5,6.5), C= (9.75,8.25), F=foot(A,B,C), G=2*F-A; fill(A--B--C--cycle,rgb(0.9,0.9,0.9));  draw(graph(P,min,max),dark); draw(graph(Q,min,max),dark); draw(Arc((8,7.67),A,G,CW),dark,EndArrow(8)); draw(B--C--G--cycle,linetype("4 4"));  label("$y \ge x/3 + 5$",(max,P(max)),E,fontsize(10)); label("$y \le 10 - |x-8|$",(max,Q(max)),E,fontsize(10)); label("$\mathcal{R}$",(6,Q(6)),NW);   /* axes */ Label f; f.p=fontsize(8); xaxis(0, max, Ticks(f, 6, 1)); yaxis(0, 10, Ticks(f, 5, 1));  [/asy]
The inequalities are equivalent to $y \ge x/3 + 5, y \le 10 - |x - 8|$. We can set them equal to find the two points of intersection, $x/3 + 5 = 10 - |x - 8| \Longrightarrow |x - 8| = 5 - x/3$. This implies that one of $x - 8, 8 - x = 5 - x/3$, from which we find that $(x,y) = \left(\frac 92, \frac {13}2\right), \left(\frac{39}{4}, \frac{33}{4}\right)$. The region $\mathcal{R}$ is a triangle, as shown above. When revolved about the line $y = x/3+5$, the resulting solid is the union of two right cones that share the same base and axis.
[asy]size(200); import three; currentprojection = perspective(0,0,10); defaultpen(linewidth(0.7)); pen dark=linewidth(1.3); pair Fxy = foot((8,10),(4.5,6.5),(9.75,8.25)); triple A = (8,10,0), B = (4.5,6.5,0), C= (9.75,8.25,0), F=(Fxy.x,Fxy.y,0), G=2*F-A, H=(F.x,F.y,abs(F-A)),I=(F.x,F.y,-abs(F-A)); real theta1 = 1.2, theta2 = -1.7,theta3= abs(F-A),theta4=-2.2;  triple J=F+theta1*unit(A-F)+(0,0,((abs(F-A))^2-(theta1)^2)^.5 ),K=F+theta2*unit(A-F)+(0,0,((abs(F-A))^2-(theta2)^2)^.5 ),L=F+theta3*unit(A-F)+(0,0,((abs(F-A))^2-(theta3)^2)^.5 ),M=F+theta4*unit(A-F)-(0,0,((abs(F-A))^2-(theta4)^2)^.5 ); draw(C--A--B--G--cycle,linetype("4 4")+dark); draw(A..H..G..I..A); draw(C--B^^A--G,linetype("4 4")); draw(J--C--K); draw(L--B--M); dot(B);dot(C);dot(F);  label("$h_1$",(B+F)/2,SE,fontsize(10)); label("$h_2$",(C+F)/2,S,fontsize(10)); label("$r$",(A+F)/2,E,fontsize(10)); [/asy]
Let $h_1,h_2$ denote the height of the left and right cones, respectively (so $h_1 > h_2$), and let $r$ denote their common radius. The volume of a cone is given by $\frac 13 Bh$; since both cones share the same base, then the desired volume is $\frac 13 \cdot \pi r^2 \cdot (h_1 + h_2)$. The distance from the point $(8,10)$ to the line $x - 3y + 15 = 0$ is given by $\left|\frac{(8) - 3(10) + 15}{\sqrt{1^2 + (-3)^2}}\right| = \frac{7}{\sqrt{10}}$. The distance between $\left(\frac 92, \frac {13}2\right)$ and $\left(\frac{39}{4}, \frac{33}{4}\right)$ is given by $h_1 + h_2 = \sqrt{\left(\frac{18}{4} - \frac{39}{4}\right)^2 + \left(\frac{26}{4} - \frac{33}{4}\right)^2} = \frac{7\sqrt{10}}{4}$. Thus, the answer is $\frac{343\sqrt{10}\pi}{120} = \frac{343\pi}{12\sqrt{10}} \Longrightarrow 343 + 12 + 10 = \boxed{365}$.

set_name: MATH


TITLE: Showing $s^2=\frac{1}{n-1}\sum_{i=1}^n(x_i-\bar{x})^2=\frac{1}{n-1}\left [\sum_{i=1}^n x_i^2-\frac{1}{n}\left ( \sum_1^nx_i\right )^2 \right ]$
QUESTION [2 upvotes]: I've got as far as this  $$s^2=\frac{1}{n-1}\sum_{i=1}^n(x_i-\bar{x})^2=\frac{1}{n-1}\sum_{i=1}^n\left ( x_i^2-2x_i\bar{x}+\bar{x}^2\right )$$ $$=\frac{1}{n-1}\left [\sum_{i=1}^nx_i^2+\bar{x}^2-2\bar{x}\sum_{i=1}^n x_i \right ]$$ $$\frac{1}{n-1}\left [\sum_{i=1}^nx_i^2 +\left ( \bar{x}-\sum_{i=1}^n x_i\right )^2 -\left (\sum_{i=1}^n x_i \right  )^2\right ]$$ And now I'm stuck. I can use $$\sum_{i=1}^n\frac{x_i}{n}=\bar{x}$$ However can't get the result. If someone could point me in the right direction I'd be grateful.

REPLY [1 votes]: Your second line should be
$$=\frac{1}{n-1}\left [\sum_{i=1}^nx_i^2+n\bar{x}^2-2\bar{x}\sum_{i=1}^n x_i \right ]$$
Then just as you said, you can use
$$\sum_{i=1}^n\frac{x_i}{n}=\bar{x}$$
to continue.


TITLE: injective $R$-module homomorphism vs. injective ring homomorphism
QUESTION [6 upvotes]: The following question has been lingering in my mind for months.
Let $R$ be a non-zero commutative ring with $1$. Consider $\phi : R^n \rightarrow R^m$,
1) as an injective $R$-module homomorphism.
2) as an injective ring homomorphism. (by definition $\phi(1)=1$.)
In which of the above cases, we can deduce that $n \leq m$? and why?

REPLY [4 votes]: Let $R = \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} \times \ldots \times \mathbb{Z}/2\mathbb{Z}$ (infinitely many times). Then as a ring $R^m = R^n = R$ $\forall m, n \in \mathbb{N}$. So the answer is negative in the case 2. But in the first case the answer is YES. But proof for general commutative ring is complicated. Here I am giving an easy proof assuming $R$ is commutative noetherian ring. After localizing at a minimal prime ideal we may assume that $R$ is a zero dimensional local ring ie artinian ring and $\phi : R^n \rightarrow R^m$ is an injective $R$ module homomorphism. Now length of $R$ as a $R$ module is finite and is equal to $l$ (say). Then comparing the length of both sides we have $ln \leq lm$. This means that $n \leq m$


TITLE: Discrete Math - Show Logically $X$ beat $Y$ exactly 2 Times
QUESTION [2 upvotes]: I was given a statement that I need to show logically. The question is #6 on this page. I have figured out the other 3 on my own but am stuck on this part of question:

Define the predicate $B(x, y)$ to mean that $x$ beat $y$ in the race. Give the logical expression equivalent to 'Sam beat exactly two people'.

I know that the use of a universal or existential quantifier is most likely required here but I am not sure how to write the expression "equal to two" in conjunction with them.
Any help would be greatly appreciated.

REPLY [2 votes]: HINT: You want to say that there exist people $x$ and $y$ such that:

Sam beat $x$;
Sam beat $y$;
$x$ and $y$ are not the same person; and
for any person $z$, if Sam beat $z$, then $z$ is $x$ or $z$ is $y$.


text:
\begin{document}

\title{State-Dependent Relay Channel with Private Messages with  Partial Causal and Non-Causal Channel State Information}

\author
{Bahareh Akhbari, Mahtab Mirmohseni, and Mohammad Reza Aref\\
Information Systems and Security Lab (ISSL)\\
Electrical Engineering Department, Sharif University of Technology, Tehran, Iran.\\
Email: b\_akhbari@ee.sharif.edu, mirmohseni@ee.sharif.edu, aref@sharif.edu
\thanks{This work was partially supported by Iranian
National Science Foundation (INSF) under contract No.
84,5193-2006 and by Iran Telecommunication Research Center (ITRC) under contract No. T500/20958.}}
\maketitle
\begin{abstract}
In this paper, we introduce a discrete memoryless State-Dependent Relay Channel with Private Messages (SD-RCPM) as a generalization of the state-dependent relay channel. We investigate two main cases: SD-RCPM with \textit{non-causal} Channel State Information (CSI), and SD-RCPM with \textit{causal} CSI. In each case, it is assumed that \textsl{partial} CSI is available at the source and relay. For non-causal case, we establish an achievable rate region using Gel'fand-Pinsker type coding scheme at the nodes informed of CSI, and Compress-and-Forward (CF) scheme at the relay. Using Shannon's strategy and CF scheme, an achievable rate region for  causal case is obtained. As an example, the Gaussian version of SD-RCPM is considered, and an achievable rate region for Gaussian SD-RCPM with non-causal perfect CSI only at the source, is derived. Providing numerical examples, we illustrate the comparison between achievable rate regions derived using CF and Decode-and-Forward (DF) schemes.
\end{abstract}

\IEEEpeerreviewmaketitle
\vspace{-3mm}
\section{Introduction}
\fontsize{9.6}{11}
\selectfont
The Relay Channel (RC) \cite{CoveElg79}, is a communication system in which a message is transmitted from the source to the destination with the help of a relay. The Partially Cooperative Relay Broadcast Channel (PC-RBC) studied in \cite{LianVee07, LianKra07}, is a generalization of RC in which the source node also sends a private message intended for the relay node. Therefore, in this channel the relay is also a sink of data. The Relay Channel with Private Messages  (RCPM) studied in \cite{TannNos07}, is a generalization of RC in which the relay is both a source and a sink of data. Hence, RCPM  can be regarded as a generalization of PC-RBC  wherein the relay is also a source of data and sends a private message to the destination. The  RCPM model  fits  networks in which  dedicated relays are not available, and relaying is performed by the nodes that each node is a source and a sink of data.

In this paper, we assume that RCPM is controlled by random parameters called  channel state and we refer to it as State-Dependent Relay Channel with Private Messages (SD-RCPM).
Recently, state-dependent channels have attracted considerable attention. In these channels, the information on the channel state can be known to the terminals causally or non-causally.  For a comprehensive overview on state-dependent channels see  \cite{Jafa06, KeshSteMer08}.

Among state-dependent multiuser models, some results have also been obtained for the State-Dependent RC (SD-RC) and State-Dependent PC-RBC (SD-PCRBC) \cite{SiguKim05}-\cite{ZaidVan07} for Gaussian and discrete memoryless cases with causal or non-causal Channel State Information (CSI).
Since RCPM can be regarded as a generalization of RC and PC-RBC, the SD-RCPM can be regarded as a generalization of SD-RC and SD-PCRBC.

In this paper, after introducing SD-RCPM, we investigate two main cases: SD-RCPM with non-causal CSI, and SD-RCPM with causal CSI. In each case, we investigate SD-RCPM with partial CSI at the source and the relay. As special cases it includes three different situations in which perfect CSI is available i) only at the source, ii) only at the relay, and iii) both at the source and the relay. Situations i and ii called \textit{asymmetric} scenarios refer to the cases in which CSI is available only at some of the nodes. Situation iii is called the \textit{symmetric} scenario. In fact in the asymmetric cases, it is assumed that only some of the nodes have the ability or the permission to know CSI.  In \cite{AkhbMirAre09, MirmAkhAre09}, unlike most of the previous works  on SD-RC, we have used CF strategy \cite{CoveElg79} for relaying in SD-RC, and showed  that there exist cases (similar to the classic RC) for which  CF scheme achieves  rates higher than those  derived using DF strategy \cite{CoveElg79} for SD-RC with asymmetric CSI in \cite{ZaidKotLan08b, ZaidVan08b}. Now, in this paper we also focus on  CF relaying scheme. In fact similar to what is shown for classic RC, the CF and DF are both able to outperform each other under different conditions. In  DF (or Partial DF)  scheme, the relay has to decode the whole message intended for the destination (or a part of it). Therefore, when only the source is informed of CSI, due to lack of knowledge of CSI at the relay,  the rate loss is caused at the relay as shown in \cite{ZaidShaPiaVan10}. On the other hand, when only the relay is informed of CSI, the source cannot use CSI and cannot conceive what the relay exactly sends, and as shown in \cite{ZaidKotLan08b}, this causes a loss in the  coherence gain  which is  expected to be achieved by DF relaying. However, DF based rate can be optimal for certain cases as shown recently in \cite{ZaidKotLan08b, ZaidShaPiaVan10}. On the other hand, in  CF strategy  independent codebooks are exploited at the source and relay,  and the relay simply  compresses its received signal. Also, CF outperforms DF  for relaying the message intended for the destination, when the link between the source and relay is worse than the direct link.

Here, for the non-causal situation, we derive an inner bound on the capacity region (achievable rate region) of SD-RCPM based on using Gel'fand-Pinsker (GP) type coding \cite{GelfPin80} at the nodes informed of CSI, and using CF scheme at the relay. We derive an achievable rate region for SD-RCPM in the causal case using Shannon's strategy \cite{Shan58} and CF scheme. We show that our result for the causal case can be considered as a special case of non-causal CSI, and this is in analogy with the relation between the capacity of the single user channel with causal CSI \cite{Shan58}, and its non-causal counterpart \cite{GelfPin80}. We also show that our results subsume the results in \cite{AkhbMirAre09, MirmAkhAre09} which are for SD-RC, and the result in \cite{TannNos07} which is for RCPM (state-independent), as special cases. As an example, we consider the Gaussian version of SD-RCPM with additive independent identically distributed (i.i.d) state process, and  obtain achievable rate region for the case where perfect CSI is available non-causally only at the source. We also illustrate  the trade-off between relayed message rate and private messages rates for this channel. Since there is no available  achievable region for SD-RCPM which is established based on DF scheme, to compare DF and CF strategies for this channel,  we consider a scenario in which the relay sends no private message to the destination (i.e., SD-RCPM reduces to SD-PCRBC). For this scenario, we  make a comparison between our CF based derived achievable region and the  rate region  derived in \cite{ZaidVan07} based  on DF.

The rest of paper is organized as follows. Section \ref{sec:definition}, introduces SD-RCPM  channel model and  notations. Section \ref{sec:noncausal}, investigates SD-RCPM with non-causal CSI. The causal case is considered in section \ref{sec:causal} and finally, Section \ref{sec:Gaussian} contains Gaussian examples.
\vspace{-2mm}
\section{Preliminaries and Definitions}\label{sec:definition}
In this paper, upper case letters (e.g., $X$) are used to denote Random Variables (RVs) while their realizations are denoted by lower case letters (e.g., $x$). $X_i^j$ indicates the sequence of RVs $(X_i,X_{i+1},\ldots, X_j)$, and for brevity, $X^j$ is used instead of $X_1^j$. $p_X(x)$ denotes the probability mass function (p.m.f) of $X$ on a set $\Xc$, where occasionally subscript $X$ is omitted. $A_\epsilon^n(X,Y)$ denotes the set of strongly jointly $\epsilon$-typical length-$n$ sequences  on $p(x,y)$, which is abbreviated by $A_\epsilon^n$  if it is clear from the context.

A discrete memoryless SD-RCPM is denoted by $(\Xc_1 \times \Xc_2,p(y_2,y_3|x_1,x_2,s),\Yc_2 \times \Yc_3)$, where $p(y_2,y_3|x_1,x_2,s)$ is the    probability transition function. $X_1\in \Xc_1$ and $X_2\in \Xc_2$ are the source and  relay inputs, respectively. $Y_2\in \Yc_2$ and $Y_3\in \Yc_3$ are respectively the outputs at the relay and  destination, and $s$ denotes the channel state. We assume that the source and relay know an i.i.d noisy version of states (i.e., partial CSI) drawn by $p(s,s_1,s_2)$ where $s\in \Sc$, $s_1\in \Sc_1$ and  $s_2\in \Sc_2$. The CSI at the source (or the relay) is perfect if $s_{1,j}$ (or $s_{2,j}$) equals $s_j$ for
$1\leq j \leq n$.

A $((2^{nR_{12}},2^{nR_{23}},2^{nR_{13}}),n)$ code for SD-RCPM consists of three message sets $\Wc_{12}=\{1,\ldots,2^{nR_{12}}\}$ (source to relay private message), $\Wc_{23}=\{1,\ldots,2^{nR_{23}}\}$ (relay to destination private message), and $\Wc_{13}=\{1,\ldots,2^{nR_{13}}\}$ (sent from the source to the destination  with the help of the relay),
where  independent messages $W_{12}$, $W_{23}$ and $W_{13}$  are uniformly distributed over respective sets.  It also consists of  an encoder at the source and a set of encoding functions at the relay where for non-causal CSI are defined as $\phi_{1}:\Wc_{12}\times\Wc_{13}\times\Sc_1^{n}\rightarrow\Xc_{1}^{n}$, and   $\phi_{2,j}:\Yc_{2}^{j-1}\times\Wc_{23}\times\Sc_2^{n}\rightarrow\Xc_{2}$ for $j=1,\ldots,n$, respectively. For causal CSI these encoders are respectively defined by
$\phi_{1,j}:\Wc_{12}\times\Wc_{13}\times\Sc_1^{j}\rightarrow\Xc_{1}$ and $\phi_{2,j}:\Yc_{2}^{j-1}\times\Wc_{23}\times\Sc_2^{j}\rightarrow\Xc_{2}$, for $j=1,\ldots,n$. Two decoding functions $d_1$ and $d_2$ at the relay and destination are defined  respectively as: $d_1:\Yc_2^n \times\Sc_2^{n}\rightarrow \Wc_{12}$ and
$d_2:\Yc_3^n \rightarrow \Wc_{23} \times\Wc_{13}$. Note that, for decoding at the relay there is no difference between causal and non-causal cases since the relay can wait until the end of the block, before decoding. The average probability of error ($P_e^{(n)}$) is defined as the one for RCPM in \cite{TannNos07}. A rate tuple $(R_{12},R_{23},R_{13})$ is said to be achievable for SD-RCPM, if there exists a sequence of codes $((2^{nR_{12}},2^{nR_{23}},2^{nR_{13}}),n)$ with  $P_e^{(n)}\rightarrow 0$ as $n\rightarrow \infty$.

\section{SD-RCPM with Non-Causal CSI}\label{sec:noncausal}
In this section, we consider SD-RCPM with partial non-causal CSI  at the source and the relay. In the following, the achievable rate region  of this channel is derived.
\begin{theorem}\label{th:noncausal}
In the discrete memoryless SD-RCPM with non-causal CSI $S_1$ and $S_2$ respectively at the source and the relay,  the nonnegative rate tuples  {\small $(R_{12},R_{23},R_{13})$} denoted as $\Rc_1$, satisfying:
\begin{align}
&\!\!R_{13}< I(T_1;\hat Y_2,Y_3|K_2,Q_2)-I(T_1;S_1)\label{eq:lowerCFsourcerelaync1}\\
&\!\!R_{12}< I(T_2;Y_2,S_2|K_2,Q_2)-I(T_2;S_1)\label{eq:lowerCFsourcerelaync2}\\
&\!\!R_{13}+R_{12}< I(T_1;\hat Y_2,Y_3|K_2,Q_2)+I(T_2;Y_2,S_2|K_2,Q_2)\nonumber\\
&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -I(T_1;S_1)-I(T_2;S_1)-I(T_1;T_2|S_1)\label{eq:lowerCFsourcerelaync3}\\
&\!\!R_{23}<I(K_2;Y_3)-I(K_2;S_2)\label{eq:lowerCFsourcerelaync4},
\end{align}
subject to the constraint
{\small
\begin{flalign}
\!\!\!\! I(\hat Y_2;Y_2,S_2,T_2|K_2,Q_2,Y_3) \leq I(Q_2;Y_3|K_2)-I(Q_2;S_2|K_2),\label{eq:condCFsourcerelaync}
\end{flalign}
}are achievable for any joint p.m.f of the form
\begin{flalign}
&\!\!p(s,s_1,s_2,k_2,q_2,t_1,t_2,x_1,x_2,\hat y_2,y_2,y_3)=\nonumber \\
&\!\!p(s,s_1,s_2)p(k_2|s_2)p(q_2|k_2,s_2)p(x_2|q_2,k_2,s_2)p(t_1,t_2|s_1)\nonumber\\
&\!\!\!\!\times p(x_1|t_1,t_2,s_1)p(y_2,y_3|x_1,x_2,s)p(\hat y_2|y_2,q_2,k_2,s_2,t_2).\label{eq:pmfsourcerelaync}
\end{flalign}
\end{theorem}
\begin{remark}\label{mk:CFsourcerelaync1}
The relay which is the middle terminal, knows CSI $S_2$. Hence, the relay  acting as a decoder of the source-relay link and based on its knowledge of CSI, tries to cancel the effect of the channel state on $y_2$. Moreover, it can compress $S_2$ (besides $Y_2$) and sends it to  destination to provide it with a partial CSI, when needed. For example, if {\small $Y_2=\emptyset$} the relay can  compress only $S_2$  and sends it to the destination, and so the destination can use this partial CSI. To achieve these two goals, in general, we assume that in  \eqref{eq:pmfsourcerelaync} $\hat y_2$ is conditioned on $s_2$.
Moreover,  $T_2$ which is decoded at the relay is not decoded at the destination ($T_2$ carries source to relay private message), and hence can be regraded as a channel state for destination. So, {\small $T_2$} can be treated similar to {\small $S_2$}, and we assume that in \eqref{eq:pmfsourcerelaync} $\hat y_2$ is also conditioned on $t_2$. Note that, by these assumptions, the case where the relay only compresses {\small $Y_2$} is also included.
\end{remark}

\textit{Outline of the Proof:}
The proof is based on random coding scheme which combines GP-type coding at the source and relay, and CF strategy. More precisely,
since the source is informed of CSI $S_1$,  the coding scheme  which extends Marton's region to the state-dependent Broadcast Channel (BC) with non-causal CSI at Transmitter (CSIT) \cite{SteiSha05} is used at the source.  The relay decoder uses $S_2$ as part of channel
output. Moreover, the relay encoder uses CF and since it is informed of $S_2$, it
uses GP coding to send the index of the compressed signal which is superimposed on the relay-destination private message.
The auxiliary RV $K_2$ stands for private message sent from the relay to destination using GP coding,
and $Q_2$ represents the bin of compressed signal's index.
Now, consider a  block Markov encoding scheme where a sequence of  $B-1$ messages  ({\small $W_{12,i},W_{23,i},W_{13,i}$}) for $i=1,\ldots,B-1$ is transmitted in $B$ blocks, each of $n$ symbols.  As {\small $B\rightarrow \infty$}, the  rate tuple {\small $(R_{12},R_{23},R_{13})\times\frac{(B-1)}{B}$} approaches {\small $(R_{12},R_{23},R_{13})$}.

\textit{Random Coding:}
For any joint p.m.f defined in (\ref{eq:pmfsourcerelaync}), generate  $2^{n(\rys+\rys')}$ i.i.d codewords $t_1^n(\wys,k)$   where $\wys\in[1,2^{n\rys}]$ and $k\in[1,2^{n\rys'}]$. Generate $2^{n(\ryd+\ryd')}$ i.i.d $t_2^n(\wyd,l)$, $\wyd\in[1,2^{n\ryd}]$, $l\in[1,2^{n\ryd'}]$. Generate $2^{n(\rds+\rds')}$ i.i.d codewords $k_2^n(\wds,m)$, $\wds\in[1,2^{n\rds}]$, $m\in[1,2^{n\rds'}]$.
For each $k_2^n(\wds,m)$, generate $2^{n(R_2+R'_2)}$ i.i.d $q_2^n(t,r|\wds,m)$, $t\in[1,2^{nR_2}]$, $r\in[1,2^{nR_2'}]$.
In codewords $t_1^n$, $t_2^n$, $k_2^n$ and $q_2^n$, the first index represents the bin, and the second one indexes  the sequence within the particular bin. For each $k_2^n(\wds,m)$ and $q_2^n(t,r|\wds,m)$, generate $2^{n\hat R_2}$ i.i.d $\hat y_2^n(z|t,r,\wds,m)$ each with probability
$\prod_{j=1}^n p(\hat y_{2j}|q_{2j},k_{2j})$. Randomly partition the set $\{1,\ldots,2^{n\hat R_2}\}$ into $2^{nR_2}$ bins defined as $B(t)$.

\textit{Encoding (at the beginning of block $i$):}
We assume that the CSI $S_1^n$ and $S_2^n$
in each block are non-causally known to the source and the relay, respectively. Then:

1) Let $(w_{13,i},w_{12,i})$ be the new message pair  to be sent  from the source in block $i$. The source looks for the smallest $k\in[1,2^{n\rys'}]$ and $l\in[1,2^{n\ryd'}]$, such that
$(t_1^n(w_{13,i},k),t_2^n(w_{12,i},l),s_1^n(i))\in A_\epsilon^n$.
Denote this $k$ and $l$ with $k_i$ and $l_i$, respectively. If no such indices $k$ and $l$ exist, an encoding error is declared.  There exist such indices $k_i$ and $l_i$ with arbitrarily high probability, if $n$ is large enough and
 \begin{align}
    \rys'>& I(T_1;S_1)\label{eq:covsourcenc1}\\
    \ryd'>& I(T_2;S_1)\label{eq:covsourcenc2}\\
    \rys'+\ryd'>& I(T_1;S_1)+I(T_2;S_1)+I(T_1;T_2|S_1)\label{eq:covsourcenc3}
\end{align}

Note that  \eqref{eq:covsourcenc1}-\eqref{eq:covsourcenc3} can be showed using techniques similar to that in  \cite{ElgaVan81}-\cite{ElgaKim10} (mutual covering lemma).

Then, the source
transmits i.i.d $x_1^n(w_{13,i},w_{12,i})$ drawn according to $p(x_1|t_1,t_2,s_1)$.

2) Knowing $s_2^n(i)$, the relay searches for the smallest $m\in[1,2^{nR_{23}'}]$ such that
$(k_2^n(w_{23,i},m),s_2^n(i))\in A_\epsilon^n$. Denote this $m$ as $m_i$. If no such index $m$  exists, an encoding error is declared. Based on covering lemma, for sufficiently large $n$ such an index $m_i$ can be found with arbitrarily high probability, if
\begin{equation}\label{eq:GPCFrelaync1}
R'_{23}\geq I(K_2;S_2).
\end{equation}

3) At the relay, assume
$(\hat y_2^n(z_{i-1}|t_{i-1},r_{i-1},w_{23,i-1},m_{i-1}),\\k_2^n(w_{23,i-1},m_{i-1}),q_2^n(t_{i-1},r_{i-1}|w_{23,i-1},m_{i-1}),
y_2^n(i-1),\\t_2^n(w_{12,i-1},l_{i-1}),s_2^n(i-1))\in A_\epsilon^n$,
and $z_{i-1} \in B(t_i)$. Knowing
$t_i$, $s_2^n(i)$, $w_{23,i}$ and $m_i$, the relay looks for the smallest $r\in[1,2^{nR'_2}]$ denoted as $r_i$ such that $(q_2^n(t_i,r_i|w_{23,i},m_i),k_2^n(w_{23,i},m_i),s_2^n(i))\in A_\epsilon^n$.
 For sufficiently large $n$  there exists such an index $r_i$ with arbitrarily high probability, if
\begin{equation}\label{eq:GPCFrelaync2}
R_{2}'>I(Q_2;S_2|K_2).
\end{equation}

Then the relay  transmits i.i.d $x_2^n(t_i|w_{23,i})$  drawn according to $p(x_2|q_2,k_2,s_2)$.

\textit{Decoding (at the end of block $i$):} The destination  at the end of block $i$  decodes $w_{13,i-1}$, $w_{23,i}$, and the relay  decodes
$w_{12,i}$.

1) Knowing $t_i$ from the previous block, the relay seeks  a unique pair $(\hat w_{12,i}, \hat l_i)$ such that $(t_2^n(\hat w_{12,i},\hat l_i),  y_2^n(i),q_2^n(t_i,r_i|w_{23,i},m_i),k_2^n(w_{23,i},m_{i}),s_2^n(i))$ $\in A_\epsilon^n$. For sufficiently large $n$, $(\hat w_{12,i}, \hat l_i)=(w_{12,i},l_i)$ with arbitrarily small probability of error if
\begin{equation}\label{eq:sourcerelayCFsourcenc}
\ryd+\ryd'<I(T_2;Y_2,S_2|K_2,Q_2).
\end{equation}

Note that we have performed a full decoding of the message $w_{12}$  and   the index $l$, at the relay. So, the full vector $t_2^n(w_{12,i},l_i)$ has been decoded.

2) The relay finds a unique index $z$ such that:
$(\hat y_2^n(z|t_i,r_i,w_{23,i},m_i),q_2^n(t_{i},r_{i}|w_{23,i},m_i),k_2^n(w_{23,i},m_{i}), y_2^n(i),$ $t_2^n(w_{12,i},l_i),s_2^n(i))\in A_\epsilon^n$.
There exists such an index $z$ with arbitrarily high probability, if $n$ is
sufficiently large and
\begin{equation}\label{eq:WZCFrelaync}
\hat R_2> I(\hat Y_2;Y_2,S_2,T_2|K_2,Q_2).
\end{equation}

3) At first, the destination finds a unique pair $(\hat w_{23,i}, \hat m_i)$, such that $(k_2^n(\hat w_{23,i},\hat m_{i}),y_3^n(i))\in A_\epsilon^n$.
The decoding error can be made small if
\begin{equation}\label{eq:relaydestCFrelaync}
R_{23}+R_{23}'<I(K_2;Y_3).
\end{equation}

4) Then, the destination looks for a unique pair $(\hat t_i,\hat r_i)$ such that
$(q_2^n(\hat t_i,\hat r_i|w_{23,i},m_i),k_2^n(w_{23,i},m_{i}),y_3^n(i))\in A_\epsilon^n$.
The decoding error can be made small if
\begin{equation}\label{eq:relaydestCFrelaync2}
   R_2+R'_2 < I(Q_2;Y_3|K_2).
\end{equation}

Note that we have performed a full decoding of $k_2^n$  and $q_2^n$ at the destination in  steps 3 and 4.

5) Now, knowing  $t_{i-1},r_{i-1},w_{23,i-1}$ and $m_{i-1}$ (from the previous block), the destination calculates a set of indices $z$ denoted by the list $\Lc(y_3^n(i-1))$  such that
$(\hat y_2^n(z|t_{i-1},r_{i-1},w_{23,i-1},m_{i-1}),q_2^n(t_{i-1},r_{i-1}|w_{23,i-1},m_{i-1}),\\k_2^n(w_{23,i-1},m_{i-1}),y_3^n(i-1)) \in A_\epsilon^n$.
Then the destination declares that $\hat z_{i-1}$ has been sent in block
$i-1$, if $\hat z_{i-1} \in B(t_i) \cap \Lc (y_3^n(i-1))$.
With arbitrarily high probability $\hat z_{i-1}=z_{i-1}$,  if
$n$ is sufficiently large and
\begin{equation}\label{eq:listcodeCFrelaync}
    \hat R_2 < R_2 + I(\hat Y_2;Y_3|Q_2,K_2).
\end{equation}

6) Finally, the destination uses  $y_3^n(i-1)$ and $\hat y_2^n(z_{i-1}|t_{i-1},r_{i-1},w_{23,i-1},m_{i-1})$,
 and declares that $\hat w_{13,i-1}$ is sent, if there is a unique $\hat w_{13,i-1}$ for some $k_{i-1} \in[1,2^{n\rys'}]$  such that
$(t_1^n(\hat w_{13,i-1},k_{i-1}),q_2^n(t_{i-1},r_{i-1}|w_{23,i-1},m_{i-1}),y_3^n(i-1),k_2^n(w_{23,i-1},m_{i-1}),\hat y_2^n(z_{i-1}|t_{i-1},r_{i-1},w_{23,i-1},m_{i-1}))\in A_\epsilon^n$.
Thus,  $\hat w_{13,i-1}=w_{13,i-1}$ with arbitrarily high probability, if $n$ is sufficiently large and
\begin{equation}\label{eq:destCFsourcenc}
    R_{13}+R_{13}'<I(T_1;Y_3,\hat Y_2|Q_2,K_2).
\end{equation}

Combining \eqref{eq:covsourcenc1},  \eqref{eq:covsourcenc2}, \eqref{eq:covsourcenc3} with \eqref{eq:sourcerelayCFsourcenc}, \eqref{eq:destCFsourcenc}, and  \eqref{eq:GPCFrelaync1} with \eqref{eq:relaydestCFrelaync} yields \eqref{eq:lowerCFsourcerelaync1}-\eqref{eq:lowerCFsourcerelaync4}.  The constraint in \eqref{eq:condCFsourcerelaync} follows from combining \eqref{eq:GPCFrelaync2}, \eqref{eq:WZCFrelaync}, \eqref{eq:relaydestCFrelaync2}  and \eqref{eq:listcodeCFrelaync}. Moreover, note that since $R_{13},R_{12},R_{23}>0$ and due to \eqref{eq:condCFsourcerelaync}, full decoding of $t_2^n,k_2^n$  and $q_2^n$ does not cause additional constraints. This completes the proof. \IEEEQED

\begin{remark}\label{mk:CFsourcerelaync2}
By setting $S=S_1=S_2=\emptyset$ (to make state-independent channel),  and re-defining $T_1=U_1$, $T_2=U_2$, $K_2=V$ and $Q_2=X_2$  in  the region $\Rc_1$, it yields the achievable region for RCPM in \cite[Theorem 2]{TannNos07}. After these substitutions and simplifications, the only difference is in  \eqref{eq:condCFsourcerelaync}, with its counterpart in \cite[Equation 21]{TannNos07}, where the reason is as follows: since the destination does not decode $U_2$ ($T_2$ is re-defined as $U_2$), in the random coding process $\hat Y_2$ is not generated for each $U_2$. Therefore, due to covering lemma \cite{ElgaKim10}, $\hat Y_2$ should cover both $Y_2$ and $U_2$, and  $\hat R_2>I(\hat Y_2;Y_2,U_2|V,X_2)$ is obtained.  But in \cite{TannNos07} the authors did not notice this point,  and to obtain $\hat R_2$ they erroneously made conditioning on $U_2$ and so they obtained $\hat R_2>I(\hat Y_2;Y_2|U_2,V,X_2)$.
\end{remark}
\begin{remark}\label{mk:CFsourcerelaync3}
By setting $(S_2,Q_2,K_2,X_2,\hat Y_2)=\emptyset$ in   region $\Rc_1$ (i.e., disable relaying), $\Rc_1$ reduces  to  the achievable rate region  for BC with non-causal CSIT that has been derived in \cite{SteiSha05}.
\end{remark}
\begin{remark}\label{mk:CFsourcerelaync4}
The region $\Rc_1$, reduces to the  achievable rate for SD-RC  with non-causal perfect CSI only at the source in \cite[Theorem 1]{AkhbMirAre09} by setting $K_2=\emptyset$ (no private $W_{23}$ from the relay to  destination and $R_{23}=0$), $T_2=\emptyset$ (no private $W_{12}$ from the source to the relay and $R_{12}=0$), $S_2=\emptyset$ and $S_1=S$  (only the source is informed of perfect CSI) and re-defining $Q_2=X_2$ in $\Rc_1$. Moreover, setting $S_1=\emptyset$, $S_2=S$, $T_2=\emptyset$,   $K_2=\emptyset$,  and re-defining {\small $T_1=X_1$} in $\Rc_1$, results in the achievable rate for SD-RC  with non-causal perfect CSI only at the relay in \cite[Theorem 2]{AkhbMirAre09}.
\end{remark}

Now, we specialize Theorem \ref{th:noncausal} to  cases where perfect CSI is available non-causally only at the source, only at the relay, or both at the source and relay.
\begin{corol}\label{corol:noncausal}
Theorem \ref{th:noncausal} is specialized  to an  achievable rate region for SD-RCPM  with non-causal perfect CSI only at the source, by setting   $S_1=S$, $S_2=\emptyset$ (since only the source is informed of CSI) and re-defining  $K_2=V$, $Q_2=X_2$ in $\Rc_1$.  Furthermore, setting $S_1=\emptyset$,  $S_2=S$ and re-defining $T_1=U_1$, $T_2=U_2$   in $\Rc_1$,  yields an achievable rate region for SD-RCPM  with non-causal perfect CSI only at the relay. Setting $S_1 = S_2 = S$ in $\Rc_1$ yields an achievable rate region for SD-RCPM  with non-causal perfect CSI at both the source and relay.\end{corol}
\vspace{-2mm}
\section{SD-RCPM with Causal CSI}\label{sec:causal}
In many practical applications, the state sequence is not known in advance, and has to be known in a causal manner. In this section, we consider SD-RCPM with partial causal CSI  at the source and the relay. In the following, the achievable rate region  for this channel is derived.
\begin{theorem}\label{th:causal}
In the discrete memoryless SD-RCPM with causal CSI $S_1$ and $S_2$ respectively  at the source and  the relay, the nonnegative rate tuples  $(R_{12},R_{23},R_{13})$ denoted as $\Rc_2$, satisfying:
\begin{align}
R_{13}<&I(T_1;\hat Y_2,Y_3|K_2,Q_2)\label{eq:lowerCFsourcerelayc1}\\
R_{12}< &I(T_2;Y_2,S_2|K_2,Q_2)\label{eq:lowerCFsourcerelayc2}\\
R_{13}+R_{12}< &I(T_1;\hat Y_2,Y_3|K_2,Q_2)\nonumber\\
&+I(T_2;Y_2,S_2|K_2,Q_2)-I(T_1;T_2)\label{eq:lowerCFsourcerelayc3}\\
R_{23}<&I(K_2;Y_3)\label{eq:lowerCFsourcerelayc4},\\
\!\!\!\!\!\textrm{subject to}\ \ I(\hat Y_2&;Y_2,S_2,T_2|K_2,Q_2,Y_3) \leq I(Q_2;Y_3|K_2),\label{eq:condCFsourcerelayc}
\end{align} are achievable for any joint p.m.f of the form
\begin{align}
&p(s,s_1,s_2)p(k_2)p(q_2|k_2)p(x_2|q_2,k_2,s_2)p(t_1,t_2)p(x_1|t_1,t_2,s_1)\nonumber\\
&\ \times p(y_2,y_3|x_1,x_2,s)p(\hat y_2|y_2,q_2,k_2,s_2,t_2),\label{eq:pmfsourcerelayc}
\end{align} where $X_1=f_1(T_1,T_2,S_1)$, $X_2=f_2(Q_2,K_2,S_2)$ and $f_1(\cdot)$ and $f_2(\cdot)$ are two arbitrary deterministic functions.
\end{theorem}
\begin{proof}
Similar to the single user channel, the proof of the causal case follows the lines of the proof  for the non-causal case in Theorem \ref{th:noncausal}. The only difference is that since in the causal case  $(T_1,T_2)$ and $S_1$ are independent (see \eqref{eq:pmfsourcerelayc}), the encoding scheme for the non-causal case is reduced to the one that does not include GP binning, and therefore does not require non-causal knowledge of $S_1$. Similar situation happens for $(K_2,Q_2)$ and $S_2$. So, the coding scheme is obtained based on using Shannon's strategy \cite{Shan58} at the source and the relay which are informed of CSI to incorporate the state knowledge,
using random binning corresponds to Marton's simplified region for BC \cite{ElgaVan81} at the source, and using CF relaying scheme at the relay. The proof is rather straightforward and  is omitted here for brevity.
\end{proof}
\begin{remark}\label{mk:CFsourcec1}
The expression of  $\Rc_2$ can be interpreted as a special case of $\Rc_1$, where $(T_1,T_2)$ are independent of $S_1$, and $(K_2,Q_2)$ are independent of $S_2$. This is similar to the relation between the expression for the capacity of state-dependent single user channel with causal CSI \cite{Shan58}, and its non-causal counterpart \cite{GelfPin80}. Hence, similar to Remark \ref{mk:CFsourcerelaync4},  $\Rc_2$ can  be reduced to  achievable rates derived for SD-RC with causal CSI in \cite{MirmAkhAre09}. Moreover, similar to  Corollary \ref{corol:noncausal},   $\Rc_2$ can be specialized to  achievable rate regions for SD-RCPM for the cases where CSI is available causally only at the source, only at the relay, or both at the source and relay.
\end{remark}
\vspace{-2mm}
\section{Gaussian Example}\label{sec:Gaussian}
In this section, we consider a general full-duplex Gaussian RC with private messages and with  additive independent Gaussian state and noise, and we refer to it as Gaussian SD-RCPM.  The outputs at the relay and the destination at time $j=1,\ldots,n$ for Gaussian SD-RCPM are given by:
{\small
\begin{equation}\label{eq:Gaussmodel2}
Y_{2j}=X_{1j}+Z_{2j}+S_j\ \  \textrm{and}\ \  Y_{3j}=X_{1j}+X_{2j}+Z_{3j}+S_j,
\end{equation}}where  $X_{1j}$ and $X_{2j}$ are transmitted signals by the source and the relay with individual average power constraints  $P_1$ and $P_2$. $Z_{2j}$ and $Z_{3j}$ are  independent zero-mean Gaussian RVs with variances   $N_2$ and $N_3$. The channel state $S_j$  is a zero-mean Gaussian RV with variance $Q$, and is  independent of $Z_{2j}$ and $Z_{3j}$.

As an example, we consider the case where the source knows state sequence $S^n$ non-causally and perfectly, while the relay is not informed of CSI. To provide an achievable rate region for this Gaussian case, we use the results obtained  in Corollary \ref{corol:noncausal} for this scenario.  For simplicity, we assume that input distributions are Gaussian, although this assumption may not be optimal. Similar to \cite{TannNos07},  we assume that the generated codebook at the source is mapped into Gaussian RVs as $X_1=U_1+U_2$, and $\rho$ denotes the correlation coefficient between $U_1$ and $U_2$. Power constraint $P_1$ at the source, and parameter $\rho$ lead to power constraints for $U_1$ and $U_2$ (i.e., $P_{u2}=\gamma P_1, P_{u1}+P_{u2}+2\rho\sqrt{P_{u1}P_{u2}}=P_1$). Now, since the source is informed of CSI, it uses Dirty Paper Coding (DPC) \cite{Cost83} for  transmission  of message $W_{12}$ (codeword $U_2$) to relay, and uses  another  DPC for transmission  of message $W_{13}$ (codeword $U_1$) to destination. Hence, similar to Costa's initial DPC, the auxiliary RVs $T_1$ and $T_2$ are defined as $T_1=U_1+\alpha_1 S$ and $T_2=U_2+\alpha_2 S$, respectively. Moreover, to partially cancel the state,  arbitrary correlations are assumed between $U_1$ and $S$ (via $\rho_{u_1s}$), and between $U_2$ and $S$ (via $\rho_{u_2s}$) which is called Generalized DPC (GDPC) \cite{ZaidVan08b}. Without loss of generality $\rho_{u2s}$ can be set to zero (i.e., using DPC instead) since $U_2$ is defined for transmission of $W_{12}$
on the point to point link between the source and relay. The relay is not informed of CSI, so $E(X_2S)=0$ and it does not use DPC. At the relay, $\theta$ is the fraction of the relay's power which is dedicated to the relay's private message. Therefore, $X_2=V+X'_2$, where $V\sim\mathcal{N}(0,\theta P_2)$ and $X'_2\sim\mathcal{N}(0,(1-\theta)P_2)$ are independent.
We assume $\hat Y_2=\beta Y_2+f T_2+\hat Z$ where $\beta\in[0,1]$ and $f\in[-1,1]$, and compression noise $\hat Z\sim\mathcal{N}(0,\hat N)$ is independent of $S,X_1,X_2,Z_2,Z_3$. We  let $f$ to be negative to consider the cases   where the relay peels-off the part intended for the relay (i.e., $T_2$), and then compresses the remaining part to send to the destination. $f=0$ refers to the case where  relay only compresses $Y_2$ without removing or compressing $T_2$. So, we evaluate \eqref{eq:lowerCFsourcerelaync1}-\eqref{eq:condCFsourcerelaync}  for this scenario (informed source only) and for a given ($\rho,\gamma,\alpha_1,\alpha_2,\rho_{u_1s},\rho_{u2s},\theta,\beta,f$). By varying these parameters, and taking the union of the resulted regions, the achievable rate region for this scenario is established (its expression is omitted here due to space). By ignoring private messages in this channel (i.e., setting $\gamma=0$ and $\theta=0$), this achievable region  reduces to  the achievable rate  derived in \cite[Theorem 4]{AkhbMirAre09} for Gaussian SD-RC   with non-causal CSI only at the source.

In Fig. \ref{fig:CFRCPMsource1}, our  achievable rate region for Gaussian SD-RCPM with non-causal CSI at the source, is plotted for
$P_1=Q=N_3=10\textrm{dB}$, $P_2=15\textrm{dB}$, $N_2=0\textrm{dB}$,  parameterized by the fraction of the relay's power dedicated to relay's private message ($\theta$), and we can see the trade-off between $R_{13}$ and $R_{12}$. As illustrated in Fig.~\ref{fig:CFRCPMsource1}, when  $\theta$ is increased, the maximum achievable $R_{13}$ is decreased. For example, $\theta=0$ refers to the case where the relay sends no private message to the destination ($W_{23}=\emptyset$), and Gaussian SD-RCPM reduces to Gaussian SD-PCRBC. Therefore, for this case  we can compare our CF based  achievable  region, with the DF based  achievable region   derived in \cite[Lemma 2]{ZaidVan07} for  SD-PCRBC with informed source only. Moreover, the outer bound on the capacity region of Gaussian PC-RBC (state-independent) in \cite[Theorem 5]{LianVee07} is a trivial  outer bound on the capacity region of SD-PCRBC. So  we illustrate this outer bound, DF and CF based rate regions  in Fig. \ref{fig:Figure2} for two examples of noise configuration: 1) $N_2=N_3$ ($N_2,N_3=10\textrm{dB}, P_1=20\textrm{dB}$) which is denoted as ``power set 1'' in Fig. \ref{fig:Figure2}, 2) $N_3>N_2$ ($N_3=10\textrm{dB}, N_2=8\textrm{dB}, P_1=16\textrm{dB}$) denoted as ``power set 2''. For both ``power set 1'' and ``power set 2'', $Q=10\textrm{dB}$, $P_2=25\textrm{dB}$. For these power sets, CF outperforms DF in PC-RBC (state-independent). So,  in the state-dependent version of this channel it can outperform DF which is shown in Fig. \ref{fig:Figure2}. In these examples, if $P_2$ is also increased, CF based bound becomes closer to its respective outer bound. Note that for noise configuration where $N_3<N_2$, it is clear that CF outperforms DF, and  to  prevent  having a messy figure this case is not depicted in Fig. \ref{fig:Figure2}. We remark that  these power sets are chosen to have cases that can be presented  in one figure. It is also interesting to note that for all these cases,  maximum achievable $R_{12}$ (when $R_{13}=0$) coincides with that of derived for PC-RBC (state-independent), and this confirms that a complete state cancellation is performed for sending $U_2$ on the source-relay link for $R_{13}=0$.

\begin{figure}[tb]
  \centering
  \includegraphics[width=6.4cm]{figure1.eps}
    \caption{CF based achievable rate region for general Gaussian SD-RCPM with non-causal CSI only at the source, parametrized by $\theta$.}
    \label{fig:CFRCPMsource1}
    \vspace{-4mm}
\end{figure}

\begin{figure}[tb]
  \centering
  \includegraphics[width=6.4cm]{figure2.eps}
    \caption{General Gaussian SD-PCRBC  with  non-causal CSI only at the source, for ``power set 1'' and ``power set 2''.}
    \label{fig:Figure2}
     \vspace{-5mm}
\end{figure}

\vspace{-2mm}
\section{Conclusion}\label{sec:conclusion}
We introduced SD-RCPM as a generalization of SD-RC and SD-PCRBC. In order to have a unified view, both causal and non-causal cases were investigated. In each case, an achievable rate region for SD-RCPM with partial CSI at the source and relay was derived  using CF scheme. We also derived an achievable rate region for Gaussian version of SD-RCPM with non-causal perfect CSI only at the source. In ongoing work, we are using  DF scheme for both  discrete memoryless and Gaussian version of SD-RCPM with causal and non-causal CSI.

config: arxiv


TITLE: A field for the weak nuclear force
QUESTION [1 upvotes]: This is a thought experiment, and I seek to learn that this is a silly question.
Assume electrons were placed in a plane, and in a parallel plane you were able to confine neutrinos. Given that they have opposite quantum numbers for the third component of weak isospin, would there be a field of the weak force between the two planes?
Obviously the force is mediated by W and Z bosons, which have a very short range. If the two planes are placed within that range, ignoring other effects, what would happen?

REPLY [4 votes]: You can't meaningfully take the classical limit of the weak force, because at the scales where you could neglect the quantum interactions, the classical potential of the weak force is suppressed so strongly by the masses of the W- and Z- bosons that it is practically non-existent. This is because forces mediated by massive particles don't follow a pure inverse-square law in their classical limit, but have an additional factor $\exp(-\mu r)$ where $\mu$ is the mass of the mediator.
The weak force, like the strong force, is significant and meaningful only in its fully quantum description - there is no use in trying to describe classical aspects of it. But the notion of a "weak field" surrounding weak charges, just like the notion of a constant electric field surrounding an electric charge according to Coulomb's law, is a classical notion. There is a "weak field" in the sense that the quantum field whose quanta are the W- and Z-bosons is a potential fully analogous to the electromagnetic vector potential.
However, if you just formally take the classical limit and don't care for how physically meaningful it is, then the answer is that the "weak field" you would get would obey a distance law $\propto \frac{\exp(-\mu r)}{r^2}$ instead of the electromagnetic $\propto\frac{1}{r^2}$.


text:
\begin{document}

\title[The Erd\H os conjecture for primitive sets]{The Erd\H os conjecture for primitive sets}

\author{Jared Duker Lichtman}

\address{Department of Mathematics, Dartmouth College, Hanover, NH 03755}

\email{jdl.18@dartmouth.edu}
\email{jared.d.lichtman@gmail.com}

\author{Carl Pomerance}
\address{Department of Mathematics, Dartmouth College, Hanover, NH 03755}
\email{carl.pomerance@dartmouth.edu}

\subjclass[2010]{Primary 11B83; Secondary 11A05, 11N05}

\date{June 30, 2018.}

\keywords{primitive set, primitive sequence, Mertens' product formula}

\begin{abstract}
A subset of the integers larger than 1 is {\it primitive} if no member divides another.
Erd\H os proved in 1935 that the sum of $1/(a\log a)$ for $a$ running over a primitive set $A$
is universally bounded over all choices for $A$.  In 1988 he asked if this universal bound is
attained for the set of prime numbers.  In this paper we make some progress on several fronts,
and show a connection to certain prime number ``races" such as the race between $\pi(x)$
and $\li(x)$.
\end{abstract}

\maketitle

\section{Introduction}

A set of positive integers $>1$ is called {\bf primitive} if no element divides any other (for convenience, we exclude the singleton set $\{1\}$).   There are
a number of interesting and sometimes unexpected theorems about primitive sets.
After Besicovitch \cite{besicovitch}, we know that the upper asymptotic density of a primitive set can be arbitrarily close to $1/2$, whereas the lower asymptotic density is always $0$.  Using the fact that
if a primitive set has a finite reciprocal sum, then
the set of multiples of members of the set has an asymptotic density, Erd\H os gave an elementary proof that the
set of nondeficient numbers (i.e., $\sigma(n)/n\ge2$, where $\sigma$ is the sum-of-divisors
function) has an asymptotic density.  Though the reciprocal sum of a primitive set can
possibly diverge, Erd\H os \cite{erdos35} showed that for a primitive set $A$,
$$
\sum_{a\in A}\frac1{a\log a}<\infty.
$$
In fact, the proof shows that these sums are uniformly bounded as $A$ varies over
primitive sets.

Some years later in a 1988 seminar in Limoges, Erd\H os suggested that in fact we always have
\begin{equation}
\label{eq:conj}
f(A):=\sum_{a\in A}\frac1{a\log a}\le\sum_{p\in\PP}\frac1{p\log p},
\end{equation}
where $\PP$ is the set of prime numbers.  The assertion \eqref{eq:conj} is now known
as the Erd\H os conjecture for primitive sets.

In 1991, Zhang \cite{zhang1} proved the
Erd\H os conjecture for primitive sets $A$ with no member having more than 4 prime factors
(counted with multiplicity).

After Cohen \cite{cohen}, we have
\begin{equation}
\label{eq:cohen}
    C: = \sum_{p\in \PP}\frac1{p\log p} = 1.63661632336\ldots\,,
\end{equation}
the sum over primes in \eqref{eq:conj}.
Using the original Erd\H os argument in \cite{erdos35}, Erd\H os and Zhang showed that
$f(A)<2.886$ for a primitive set $A$, which was later improved by Robin to $2.77$.  These unpublished
estimates are reported in Erd\H os--Zhang \cite{ez} who used another method to show that
 $f(A)<1.84$.   Shortly after, Clark \cite{clark} claimed that
$f(A)\le e^\gamma=1.781072\dots$\,.  However, his brief argument appears to be
incomplete.

Our principal results are the following.
\begin{theorem}\label{thm:egamma}
For any primitive set $A$ we have $f(A) < e^\gamma$.
\end{theorem}
\begin{theorem}
\label{thm:no8s}
For any primitive set $A$ with no element divisible by $8$, we have $f(A)<C+2.37\times10^{-7}$.
\end{theorem}

Say a prime $p$ is
{\bf Erd\H os strong} if for any primitive set $A$ with the property that each element of $A$ has least prime
factor $p$, we have $f(A)\le 1/(p\log p)$.
We conjecture that every prime is Erd\H os strong.  Note that
the Erd\H os conjecture \eqref{eq:conj} would immediately follow, though it is not clear that the Erd\H os conjecture implies our conjecture.  Just proving our conjecture for the case of $p=2$ would give the inequality in
Theorem \ref{thm:no8s} for all primitive sets $A$.
Currently the best we can do for a primitive set $A$ of even numbers is that
$f(A)<e^\gamma/2$, see Proposition \ref{lem:erdos} below.

For part of the next result, we assume the Riemann hypothesis (RH) and the Linear Independence hypothesis (LI), which asserts that the sequence of numbers $\gamma_n>0$ such that $\zeta(\tfrac{1}{2}+i\gamma_n)=0$ is linearly independent over $\Q$.

\begin{theorem}
\label{thm:race}
Unconditionally, all of the odd
primes among the first $10^8$ primes are Erd\H os strong.
Assuming RH and LI,
the Erd\H os strong primes have  relative lower logarithmic
density $>0.995$.
\end{theorem}
The proof depends strongly on a recent result of Lamzouri \cite{lamz} who was interested in
the ``Mertens race" between $\prod_{p\le x}(1-1/p)$ and $1/(e^\gamma \log x)$.

For a primitive set $A$, let $\PP(A)$ denote the support of $A$, i.e., the
set of prime numbers that divide some member of $A$.  It is clear that the
Erd\H os conjecture \eqref{eq:conj} is equivalent to the same assertion where
the prime sum is over $\PP(A)$.
\begin{theorem}
\label{thm:support}
If $A$ is a primitive set with $\PP(A)\subset[3,\exp(10^6)]$, then
$$
f(A)\le\sum_{p\in\PP(A)}\frac{1}{p\log p}.
$$
\end{theorem}
If some primitive set $A$ of odd numbers exists with $f(A)>\sum_{p\in\PP(A)}1/(p\log p)$,
Theorem \ref{thm:support} suggests that it will be very difficult indeed to give a concrete example!

For a positive integer $n$, let $\Omega(n)$ denote the number of prime factors of $n$
counted with multiplicity.  Let $\N_k$ denote the set of integers $n$ with $\Omega(n)=k$.
Zhang \cite{zhang2} proved a result that implies $f(\N_k)< f(\N_1)$ for each $k\ge2$, so that the Erd\H os conjecture holds for the primitive sets $\N_k$.  More recently, Banks and Martin
\cite{bm} conjectured that $f(\N_1)>f(\N_2)>f(N_3)>\cdots$\,.  The inequality
$f(\N_2)>f(\N_3)$ was just established by Bayless, Kinlaw, and Klyve \cite{BKK}.
We prove the following result.
\begin{theorem}
\label{thm:Nk}
There is a positive constant $c$ such that $f(\N_k)\ge c$ for all $k$.
\end{theorem}

We let the letters $p,q,r$ represent primes.  In addition, we let $p_n$ represent the
$n$th prime.  For an integer $a>1$, we let $P(a)$ and $p(a)$ denote the largest and smallest prime factors of $a$. Modifying the notation introduced in \cite{ez}, for a primitive set $A$ let
\begin{align*}
 A_p & = \{a\in A: p(a)\ge p\},\\
 A'_p & = \{a\in A: p(a) = p\},\\
 A''_p & = \{a/p : a\in A'_p\}.
\end{align*}
We let $f(a)=1/(a\log a)$ and so $f(A)=\sum_{a\in A}f(a)$.
In this language, Zhang's full result \cite{zhang2} states that $f((\N_k)'_p)\le f(p)$ for all primes $p$, $k\ge1$.
We also, let
$$
g(a)=\frac1a\prod_{p<P(a)}\left(1-\frac1p\right),\quad h(a)=\frac1{a\log P(a)},
$$
with
$ g(A)=\sum_{a\in A}g(a)$ and $h(A)=\sum_{a\in A}h(a)$.

\section{The Erd\H os approach}

In this section we will prove Theorem \ref{thm:egamma}.
We begin with an argument inspired by the original 1935 paper of Erd\H os \cite{erdos35}.

\begin{proposition}\label{lem:erdos}
For any primitive set $A$, if $q\notin A$ then
$$f(A'_q) < e^\gamma g(q) = \frac{e^\gamma}{q}\prod_{p<q}\bigg(1-\frac{1}{p}\bigg).$$
\end{proposition}
\begin{proof}
For each $a\in A'_q$, let $S_a = \{ba : p(b) \ge P(a)\}$. Note that $S_a$ has asymptotic density $g(a)$. Since $A'_q$ is primitive, we see that the sets $S_a$ are pairwise disjoint. Further, the union of the sets $S_a$ is contained in the set of all natural numbers $m$ with $p(m) = q$, which has asymptotic density $g(q)$. Thus, the sum of densities for each $S_a$ is dominated by $g(q)$, that is,
\begin{align}\label{eq:g(A)}
g(A'_q)=\sum_{a\in A'_q}g(a) \le g(q).
\end{align}

By Theorem 7 in \cite{RS1}, we have for $x\ge285$,
\begin{equation}
\label{eq:mert}
\prod_{p\le x}\left(1-\frac1p\right)>\frac{1}{e^\gamma\log(2x)},
\end{equation}
which may be extended to all $x\ge 1$ by a calculation. Thus, since each $a \in A'_q$ is composite,
$$g(a)=\frac{1}{a}\prod_{p<P(a)}\bigg(1-\frac{1}{p}\bigg) > \frac{e^{-\gamma}}{ a\log\big(2P(a)\big)} > \frac{e^{-\gamma}}{ a\log a} = e^{-\gamma}f(a).$$
Hence by \eqref{eq:g(A)},
\begin{equation*}

    f(A'_q)/e^\gamma < g(A'_q) \le g(q).
\end{equation*}
\end{proof}
\begin{remark}
Let $\sigma$ denote the sum-of-divisors function and let $A$ be the set of $n$ with
$\sigma(n)/n\ge2$ and $\sigma(d)/d<2$ for all proper divisors $d$ of $n$, the set of
primitive nondeficient numbers.  Then an appropriate analog of
 $g(A)$ gives the density of nondeficient numbers, recently shown in \cite{mits1} to lie in the tight interval
$(0.2476171,\,0.2476475)$.
In \cite{JDLpnd}, an analog of
Proposition \ref{lem:erdos} is a key ingredient for sharp bounds on the reciprocal sum of the
primitive nondeficient numbers.
\end{remark}
\begin{remark}
We have $g(\mathcal P)=1$. It is easy to see by induction over primes $r$ that
\begin{equation*}

\sum_{p\le r}g(p)=\sum_{p\le r}\frac1p\prod_{q<p}\left(1-\frac1q\right)=1-\prod_{p\le r}\left(1-\frac1p\right).
\end{equation*}
Letting $r\to\infty$ we get that $g(\mathcal P)=1$.  There is also a holistic way of seeing this.
Since $g(p)$ is the density of the set of integers with least prime factor $p$,
it would make sense that
$g(\mathcal P)$ is the density of the set of integers which have a least prime factor, which is 1.
To make this rigorous, one notes that the density of the set of integers whose least prime factor
is $>y$ tends to 0 as $y\to\infty$.
As a consequence of $g(\mathcal P)=1$, we have
\begin{equation}
\label{eq:ident}
\sum_{p>2}g(p)=\frac12,
\end{equation}
an identity we will find to be useful.
\end{remark}

For a primitive set $A$, let
$$A^k = \{a: 2^k\| a\in A\}, \qquad B^k = \{a/2^k: a\in A^k\}.$$
The next result will help us prove Theorem \ref{thm:egamma}.

\begin{lemma}\label{lem:egamma}
For a primitive set $A$, let $k\ge1$ be such that $2^k\notin A$. Then we have
$$f(A^{k}) < \frac{e^\gamma}{2^k}\sum_{p\notin A\atop p>2}g(p).$$
\end{lemma}
\begin{proof}
If $2^kp\notin A$ for a prime $p>2$, then $(B^k)'_p$ is a primitive set of odd composite numbers,
 so by Proposition \ref{lem:erdos}, $f((B^k)'_p) < e^\gamma g(p)$.

Now if $2^kp\in A$ for some odd prime $p$, then $(B^{k})'_p=\{p\}$ and note $p\notin A$ by primitivity. We have $f(2^kp) < 2^{-k}e^\gamma g(p)$ since
$$
\frac1{2^kp\log(2^kp)}\le\frac1{2^kp\log(2p)}<\frac{e^\gamma}{2^k}g(p),
$$
which follows from \eqref{eq:mert}.  Hence combining the two cases,
\begin{align*}
f(A^k)=\sum_{p\notin A\atop p>2}f(2^k{\cdot}(B^k)'_p)& \le \sum_{p\in B^k,p\notin A\atop p>2}f(2^kp) + 2^{-k}\sum_{p\notin B^k,p\notin A\atop p>2}f((B^k)'_p)\\
& < \frac{e^\gamma}{2^k}\sum_{p\notin A\atop p>2}g(p).
\end{align*}
\end{proof}
With Lemma \ref{lem:egamma} in hand, we prove $f(A)<e^\gamma$.
\begin{proof}[Proof of Theorem \ref{thm:egamma}]
 From Erd\H os--Zhang \cite{ez}, we have that $f(A_3)<0.92$.  If $2\in A$, then $A'_2=\{2\}$, so that
 $f(A)=f(A_3)+f(A'_2)<0.92+1/(2\log2)<e^\gamma$.  Hence we may assume that $2\notin A$.
 If $A$ contains every odd prime, then $f(A'_2)$ consists of at most one power
 of 2, and the calculation just concluded shows we may assume this is not the case.
Hence there is at least one odd prime $p_0\notin A$.
By Proposition \ref{lem:erdos}, we have
\begin{align}\label{eq:A}
    f(A) &= \sum_pf(A'_p)= \sum_{p\in A}f(p) + \sum_{p\notin A} f(A'_p) < \sum_{p\in A}f(p) + e^\gamma\sum_{p\notin A\atop p>2} g(p) + f(A'_2).
\end{align}
First suppose $A$ contains no powers of $2$. Then by Lemma \ref{lem:egamma},
\begin{align*}

    f(A'_2) = \sum_{k\ge1}f(A^{k}) < \sum_{k\ge1}\frac{e^\gamma}{2^k}\sum_{p\notin A\atop p>2}g(p) = e^\gamma\sum_{p\notin A\atop p>2}g(p).
\end{align*}
Substituting into  \eqref{eq:A}, we conclude, using \eqref{eq:ident},
\begin{align}
\label{eq:fA}
    f(A) & < \sum_{p\in A}f(p) + 2e^\gamma\sum_{p\notin A\atop p>2}g(p) \le 2e^\gamma\sum_{p>2}g(p) = e^\gamma.
\end{align}
For the last inequality we used that for every prime $p$,
\begin{equation}
\label{eq:fgineq2}
\frac{f(p)}{e^\gamma g(p)}<1.082,
\end{equation}
which follows after a short calculation using \cite[Theorem 7]{RS1}.

Now if $2^K\in A$ for some positive integer $K$, then $K$ is unique and $K\ge 2$.
Also $A^K=\{2^K\}$ and
 $A^k=\emptyset$ for all $k>K$, so again by Lemma \ref{lem:egamma},
\begin{align*}
    f(A'_2) = \sum_{k=1}^Kf(A^{k}) = f(2^K) + \sum_{k=1}^{K-1}\frac{e^\gamma}{2^k}\sum_{p\notin A\atop p>2}g(p) = f(2^K) + (1-2^{1-K})e^\gamma\sum_{p\notin A\atop p>2}g(p).
\end{align*}
Substituting into \eqref{eq:A} gives
\begin{align}
\label{eq:fAK}
    f(A) < \sum_{p\in A}f(p) + f(2^K) + (2-2^{1-K})e^\gamma\sum_{p\notin A\atop p>2}g(p) & \le f(2^K) + (2-2^{-1})e^\gamma\sum_{p>2}g(p)\nonumber\\
    & \le f(2^2) + (1-2^{-2})e^\gamma < e^\gamma,
\end{align}
using $K\ge2$, the identity \eqref{eq:ident}, inequality \eqref{eq:fgineq2}, and $f(2^2)< 2^{-2} e^\gamma$. This completes the proof.
\end{proof}

\section{Mertens primes}

In this section we will prove Theorems \ref{thm:race} and Theorem \ref{thm:support}.
Note that by Mertens' theorem,
$$
\prod_{p<x}\left(1-\frac1p\right)\sim\frac1{e^\gamma\log x},\quad x\to\infty,
$$
where $\gamma$ is Euler's constant.
We say a prime $q$ is {\bf Mertens} if
\begin{equation}
\label{eq:help}
e^\gamma\prod_{p<q}\Big(1-\frac{1}{p}\Big) \le \frac{1}{\log q},
\end{equation}
and let $\mathcal P^{\textrm{Mert}}$ denote the set of Mertens primes. We are interested in Mertens primes because of the following consequence of Proposition \ref{lem:erdos}, which shows that every Mertens prime is Erd\H os strong.

\begin{corollary}\label{cor:mert}
Let $A$ be a primitive set.
If $q\in \PP^{\rm Mert}$, then $f(A'_q)\le f(q)$. Hence if $A'_q \subset \{q\}$ for all $q\notin \PP^{\rm Mert}$, then $A$ satisfies the Erd\H os conjecture.
\end{corollary}
\begin{proof}
By Proposition \ref{lem:erdos} we have $f(A'_q)\le\max\{e^\gamma g(q),f(q)\}$. If $q\in\PP^{\textrm{Mert}}$, then
$$e^\gamma g(q) = \frac{e^\gamma}{q}\prod_{p<q}\bigg(1-\frac{1}{p}\bigg)\le \frac{1}{q\log q} =f(q),$$
so $f(A'_q)\le f(q)$.
\end{proof}

Now, one would hope that the Mertens inequality \eqref{eq:help}
holds for all primes $q$. However, \eqref{eq:help} fails for $q=2$ since $e^\gamma > 1/\log 2$. We have computed that $q$ is indeed a Mertens prime for all $2<q\le p_{10^8} = 2{,}038{,}074{,}743$, thus proving the unconditional part of Theorem \ref{thm:race}.

\subsection{Proof of Theorem \ref{thm:race}}

To complete the proof, we use a result of Lamzouri \cite{lamz} relating the Mertens inequality to the race between $\pi(x)$
and $\li(x)$, studied by Rubinstein and Sarnak \cite{RubSarn}. Under the assumption of RH and LI,
he proved that the set $\mathcal N$ of real numbers $x$ satisfying
\begin{align*}
    e^\gamma \prod_{p\le x}\bigg(1-\frac{1}{p}\bigg) > \frac{1}{\log x},
\end{align*}
has logarithmic density $\delta(\mathcal{N})$ equal to the logarithmic density of numbers $x$ with $\pi(x)>\li(x)$,
and in particular
\begin{align}
\delta(\mathcal N) = \lim_{x\to\infty}\frac{1}{\log x}\int_{t\in \mathcal N\cap[2,x]}\frac{dt}{t} = 0.00000026\ldots\,.
\end{align}

We note that if a prime $p=p_n\in \mathcal N$, then for $p'=p_{n+1}$ we have $[p,p')\subset\mathcal N$ because the prime product on the left-hand side is constant on $[p,p')$, while $1/\log x$ is decreasing for $x\in [p,p')$.

The set of primes $\QQ$ in $\mathcal N$ is precisely the set of non-Mertens primes, so $\QQ=\mathcal P\setminus\mathcal P^{\textrm{Mert}}$.  From the above observation, we may leverage knowledge of the continuous logarithmic density $\delta(\mathcal N)$ to obtain an upper bound on the relative (upper) logarithmic density of non-Mertens primes
\begin{align}
\label{eq:dens}
\bar\delta(\QQ) := \limsup_{x\to \infty}\frac{1}{\log x}\sum_{p\le x\atop p\in \QQ}\frac{\log p}{p}.
\end{align}

 From the above observation, we have
\begin{align*}
\delta(\mathcal N) \ge \limsup_{x\to\infty}\frac{1}{\log x}\sum_{p\le x\atop p\in \mathcal Q}\int_{p}^{p'}\frac{dt}{t} & = \limsup_{x\to\infty}\frac{1}{\log x}\sum_{p\le x\atop p\in \mathcal Q}\log(p'/p).
\end{align*}
Then letting $d_p=p'-p$ be the gap between consecutive primes, we have
\begin{align*}
\delta(\mathcal N) \ge \limsup_{x\to\infty}\frac{1}{\log x}\sum_{p\le x\atop p\in \mathcal Q}\frac{d_p}{p},
\end{align*}
since $\sum\log(p'/p) = \sum d_p/p + O(1)$. The average gap is roughly $\log p$, so we may consider the primes for which $d_p < \epsilon \log p$, for a small positive constant $\epsilon$ to be determined.

We claim
\begin{align}\label{eq:RVclaim}
\limsup_{x\to\infty}\frac1{\log x}\sum_{\substack{p\le x\\ d_p < \epsilon \log p}}\frac{\log p}{p} \ \le \ 16\epsilon,
\end{align}
from which it follows
\begin{align*}
\bar\delta(\QQ) & = \limsup_{x\to\infty}\frac{1}{\log x}\sum_{p\le x\atop p\in \QQ}\frac{\log p}{p} \le \limsup_{x\to\infty}\frac{1}{\log x}\Big(\sum_{\substack{p\le x\\ p\in \QQ\\d_p \ge \epsilon \log p}}\frac{d_p/\epsilon}{p} + \sum_{\substack{p\le x\\ d_p < \epsilon \log p}}\frac{\log p}{p}\Big)\\
& \le \delta(\mathcal N)/\epsilon + 16\epsilon.
\end{align*}
Hence to prove Theorem \ref{thm:race} it suffices to prove \eqref{eq:RVclaim}, since taking $\epsilon = \sqrt{\delta(\mathcal N)}/4$ gives
\begin{align}
    \bar\delta(\QQ) < 8\sqrt{\delta(\mathcal N)} < 4.2\times10^{-3}.
\end{align}

By Riesel-Vaughan \cite[Lemma 5]{RV}, the number of primes $p$ up to $x$ with $p+d$ also prime is at most
\begin{align*}
    \sum_{p\le x\atop p+d\textrm{ prime}}1 \le \frac{8c_2x}{\log^2 x}\prod_{p\mid d\atop p>2}\frac{p-1}{p-2},
\end{align*}
where $c_2$ is for the twin-prime constant $2\prod_{p>2}p(p-2)/(p-1)^2=1.3203\ldots$.
Denote the prime product by $F(d) = \prod_{p\mid d\atop p>2}\frac{p-1}{p-2}$, and consider the multiplicative function $H(d) = \sum_{u\mid d}\mu(u)F(d/u)$. We have $H(2^k)=0$ for all $k\ge1$, and for $p>2$ we have $H(p)=F(p)-1$, and $H(p^k)=0$ if $k\ge2$. Thus,
\begin{align*}
\sum_{d\le y} F(d) & = \sum_{d\le y}\sum_{u\mid d}H(u) = \sum_{u\le y}H(u)\sum_{d\le y/u}1\le y\sum_{u\le y}\frac{H(u)}{u} \le y\prod_{p>2}\Big(1 + \frac{H(p)}{p}\Big)\\
& = y\prod_{p>2}\Big(1 + \frac{(p-1)/(p-2)-1}{p}\Big) = y\prod_{p>2}\Big(1 + \frac{1}{p(p-2)}\Big).
\end{align*}
Noting that $c_2':=\prod_{p>2}(1 + 1/[p(p-2)])=2/c_2$, we have
\begin{align*}
\sum_{\substack{p\le x\\ d_p < \epsilon \log p}}1\le \sum_{d\le \epsilon\log x}\sum_{p\le x\atop p+d\textrm{ prime}}1 \le \frac{8c_2x}{\log^2 x}\sum_{d\le \epsilon\log x}F(d) \le \epsilon\frac{8c_2c_2'x}{\log x} = \epsilon\frac{16x}{\log x}.
\end{align*}
Thus, \eqref{eq:RVclaim} now follows by partial summation, and the proof is complete.

\begin{remark}
The concept of relative upper logarithmic density of the set of non-Mertens primes in
\eqref{eq:dens}  can be replaced in the theorem with
$$
\bar\delta_0(\QQ):=\limsup_{x\to\infty}\frac1{\log\log x}\sum_{\substack{p\le x\\p\in \QQ}}\frac1p.
$$
Indeed, $\bar\delta_0(\QQ)\le\bar\delta(\QQ)$ follows from the identity
$$
\sum_{\substack{p\le x\\p\in \QQ}}\frac1p=\frac1{\log x}\sum_{\substack{p\le x\\p\in \QQ}}\frac{\log p}p
+\int_2^x\frac1{t(\log t)^2}\sum_{\substack{p\le t\\p\in \QQ}}\frac{\log p}p\,dt.
$$
\end{remark}

\begin{remark}
\label{rmk:martin}
Greg Martin has indicated to us that one should be able to prove (under RH and LI) that the relative logarithmic density
of $\QQ$ exists and is equal to the logarithmic density of $\mathcal N$.  The idea is as follows.  Partition
the positive reals into intervals of the form $[y,y+y^{1/3})$.  Let $E_1$ be the union of those intervals
$[y,y+y^{1/3})$ where the sign of $e^\gamma\prod_{p\le x}(1-1/p)-1/\log x$ is not constant and let
$E_2$ be the union of those intervals $[y,y+y^{1/3})$ which do not have $\sim y^{1/3}/\log y$ primes
as $y\to\infty$.  The the logarithmic density of $E_1\cup E_2$ can be shown to be 0, from which the assertion
follows.
\end{remark}

\subsection{Proof of Theorem \ref{thm:support}}

We now use some numerical estimates of Dusart \cite{dusart} to prove Theorem \ref{thm:support}.

We say a pair of primes $p\le q$ is a {\bf Mertens pair} if
$$
\prod_{p\le r<q}\left(1-\frac1r\right)>\frac{\log p}{\log pq}.
$$
We claim that every pair of primes $p,q$ with $2<p\le q<e^{10^6}$ is a Mertens pair.
Assume this and let $A$ be a primitive set supported on the odd primes to $e^{10^6}$.
By \eqref{eq:g(A)}, if $p\notin A$, we have
\begin{align*}
\frac1{p}&\ge\sum_{a\in A'_p}\frac1a\prod_{p\le r <P(a)}\left(1-\frac1{r}\right)
>\sum_{a\in A'_p}\frac{\log p}{a\log(p\,P(a))}\\
&\ge\sum_{a\in A'_p}\frac{\log p}{a\log a}=f(A'_p)\log p.
\end{align*}
Dividing by $\log p$ we obtain $f(A'_p)\le f(p)$, which also holds if $p\in A$. Thus, the claim about Mertens pairs implies the theorem.

To prove the claim, first note that if $p$ is
a Mertens prime, then $p,q$ is a Mertens pair for all primes $q\ge p$.  Indeed, we have
$$
\prod_{p\le r<q}\left(1-\frac1r\right)=\prod_{r<p}\left(1-\frac1r\right)^{-1}\prod_{r<q}\left(1-\frac1r\right)
>e^\gamma \log p\prod_{r<q}\left(1-\frac1r\right).
$$
By \eqref{eq:mert}, this last product exceeds $e^{-\gamma}/\log(2q)>e^{-\gamma}/\log(pq)$,
and using this in the above display shows that $p,q$ is indeed a Mertens pair.  Since
all of the odd primes up to $p_{10^8}$ are Mertens, to complete the proof of our assertion,
it suffices to consider the case when $p>p_{10^8}$.  Define $E_p$ via the
equation
$$
\prod_{r<p}\left(1-\frac1r\right)=\frac{1+E_p}{e^\gamma \log p}.
$$
Using \cite[Theorem 5.9]{dusart}, we have for $p>2{,}278{,}382$,
\begin{equation}
\label{eq:D}
|E_p|\le .2/(\log p)^3.
\end{equation}
  A routine calculation
shows that if $p\le q<e^{4.999(\log p)^4}$, then
$$
\prod_{p\le r<q}\left(1-\frac1r\right)=\frac{\log p}{\log q}\cdot\frac{1+E_q}{1+E_p}
>\frac{\log p}{\log pq}.
$$
It remains to note that $4.999(\log p_{10^8})^4 >1{,}055{,}356$.

It seems interesting to record the principle that we used in the proof.
\begin{corollary}
\label{cor:mertens}
If $A$ is a primitive set such that $p(a),P(a)$ is a Mertens pair for each $a\in A$, then
$f(A)\le f(\PP(A))$.
\end{corollary}

\begin{remark}
\label{rmk:ford}
Kevin Ford has noted to us the remarkable similarity between the concept of Mertens primes in this
paper and the numbers
$$
\gamma_n=\left(\gamma+\sum_{k\le n}\frac{\log p_k}{p_k-1}\right)\prod_{k\le n}\left(1-\frac1{p_k}\right)
$$
discussed in Diamond--Ford \cite{DF}.  In particular, while it may not be obvious from the definition, the analysis in
\cite{DF} on whether the sequence $\gamma_1,\gamma_2,\dots$ is monotone
 is quite similar to the analysis in \cite{lamz} on the Mertens inequality. Though the numerical evidence
 seems to indicate we always have $\gamma_{n+1}<\gamma_n$, this is disproved in \cite{DF}, and it is
 indicated there that the first time this fails may be near $1.9\cdot10^{215}$.  This may also be near where the
 first odd non-Mertens prime exists.  If this is the case, and under assumption of RH, it may be that
 every pair of primes $p\le q$ is a Mertens pair when $p>2$ and $q < \exp(10^{100})$.
 \end{remark}

\section{Odd primitive sets}

In this section we prove Theorem \ref{thm:no8s} and establish a curious result on parity for primitive sets.

Let
$$
\epsilon_0=\sum_{\substack{p>2\\p\notin\PP^{\rm Mert}}}\left(e^\gamma g(p)-f(p)\right).
$$
\begin{lemma}
\label{lem:eps}
We have $0\le\epsilon_0<2.37\times10^{-7}$.
\end{lemma}
\begin{proof}
By the definition of $\PP^{\rm Mert}$, the summands in the definition of $\epsilon_0$ are nonnegative,
so that $\epsilon_0\ge0$.    If $p>2$ is not Mertens, then $p>p_{10^8}>2\times10^9$, so that \eqref{eq:D} shows that
\begin{equation}
\label{eq:nonM}
e^\gamma g(p)-f(p)<\frac1{5p(\log p)^4}.
\end{equation}
By \cite[Proposition 5.16]{dusart}, we have
$$
p_n  >n(\log n+\log\log n-1 +(\log\log n-2.1)/\log n,\quad n\ge 2.
$$
Using this we find that
$$
\sum_{n>10^8}\frac1{5p_n(\log p_n)^4}<2.37\times10^{-7},
$$
which with \eqref{eq:nonM} completes the proof.
\end{proof}

\begin{remark}
Clearly, a smaller bound for $\epsilon_0$ would follow by raising the search limit for Mertens primes.
Another small improvement could be made using the estimate in \cite{axler} for $p_n$.
It follows from the ideas in Remark \ref{rmk:martin} that $\epsilon_0>0$.  Further, it may be provable
 from the ideas in
Remark \ref{rmk:ford} that $\epsilon_0<10^{-100}$ if the Riemann Hypothesis holds.
\end{remark}

We have the following result.
\begin{theorem}
\label{thm:odd}
For any odd primitive set $A$, we have
\begin{align}
\label{eq:odd}
f(A)  \le f(\PP(A))+\epsilon_0.
\end{align}
\end{theorem}
\begin{proof}
Assume that $A$ is an odd primitive set.  We have
$$
f(A)=\sum_{p\in\PP(A)}f(A'_p)\le\sum_{p\in\PP(A)\cap\PP^{\rm Mert}}f(p)+\sum_{p\in\PP(A)\setminus\PP^{\rm Mert}}e^\gamma g(p)
\le\epsilon_0+\sum_{p\in\PP(A)}f(p)
$$
by the definition of $\epsilon_0$.  This completes the proof.
\end{proof}

This theorem yields the following corollary.
\begin{corollary}\label{cor:8}
If $A$ is a primitive set containing no multiple of $8$, then \eqref{eq:odd} holds.
\end{corollary}
\begin{proof}
We have seen the corollary in the case that $A$ is odd.
  Next, suppose that $A$ contains an even number, but no multiple of 4.
If $2\in A$, the result follows by applying Theorem \ref{thm:odd} to $A\setminus\{2\}$, so assume
$2\notin A$.  Then $A''_2$ is an odd primitive set and $f(A'_2)\le f(A''_2)/2$.
We have by the odd case that
\begin{equation}
\label{eq:2mod4}
f(A)=f(A_3)+f(A'_2)< f(\PP(A_3))+\epsilon_0+\frac12\left(f(\PP(A''_2))+\epsilon_0\right).

\end{equation}
Since
$$
\frac12f(\PP(A''_2))\le\frac12f(\PP\setminus\{2\})<0.4577
$$
and $f(2)=0.7213\dots$, \eqref{eq:2mod4} and Lemma \ref{lem:eps} imply that $f(A)<f(\PP(A))$,
which is stronger than required.  The case when $A$ contains a multiple of 4
but no multiple of 8 follows in a similar fashion.
\end{proof}
Since a cube-free number cannot be divisible by 8,  \eqref{eq:odd} holds for all primitive sets $A$ of cube-free numbers.  Also, the proof of Corollary \ref{cor:8} can be adapted to show that \eqref{eq:odd} holds
for all primitive sets $A$ containing no number that is 4~(mod~8).

We close out this section with a curious result about those primitive sets $A$ where \eqref{eq:odd}
does not hold.
Namely, the Erd\H os conjecture must then hold for the set of odd members of $A$.
 Put another way, \eqref{eq:odd} holds for any primitive set $A$ for
which the Erd\H os conjecture for the odd members of $A$ {\it fails}.
\begin{theorem}
\label{thm:curious}
If $A$ is a primitive set with $f(A)> f(\PP(A))+\epsilon_0$, then $f(A_3)<f(\PP(A_3))$.
\end{theorem}
\begin{proof}[Proof (Sketch)]
Without loss of generality, we may include in $A$ all primes not in $\PP(A)$, and so assume that $\PP(A)=\PP$
and $f(A)>C+\epsilon_0$.
By Theorem \ref{thm:odd} we may assume that $A$ is not odd, and by Corollary \ref{cor:8}
we may assume that $2\notin A$.  By the proof of Theorem \ref{thm:egamma} (see \eqref{eq:fA} and
\eqref{eq:fAK}), if $3\in A$, we have
$$
f(A)<f(3)+\frac23e^\gamma<C,
$$
a contradiction, so we may assume that $3\notin A$.  We now apply the method of proof of Theorem \ref{thm:egamma}
to $A_3$, where powers of 3 replace powers of 2.  This leads to
$$
f(A_3)<\frac12e^\gamma<C-f(2)=f(\PP(A_3)).
$$
This completes the argument.
\end{proof}

\section{Zhang primes and the Banks--Martin conjecture}

Note that
$$
\sum_{p\ge x}\frac1{p\log p}\sim\frac1{\log x},\quad x\to\infty.
$$
In Erd\H os--Zhang \cite{ez} and in Zhang \cite{zhang2}, numerical approximations
to this asymptotic relation are exploited.
Say a prime $q$  is {\bf Zhang} if
$$\sum_{p\ge q}\frac{1}{p\log p} \le \frac{1}{\log q}.$$
Let $\mathcal P^{\textrm{Zh}}$ denote the set of Zhang primes. We are interested in Zhang primes because of the following result.

\begin{theorem}\label{thm:zhang}
If $\mathcal P(A'_p)\subset \mathcal P^{\textrm{Zh}}$, then $f(A'_p) \le f(p)$.
Hence the Erd\H os conjecture holds for all primitive sets $A$ supported on $\mathcal P^{\textrm{Zh}}$.
\end{theorem}
\begin{proof}
As in \cite{ez} it suffices to prove the theorem in the case that $A$ is a finite set.  By $d^\circ(A)$ we mean
the maximal value of $\Omega(a)$ for $a\in A$.
We proceed by induction on $d^\circ(A_p')$. If $d^\circ(A'_p)\le 1$, then $f(A_p') \le  f(p)$. If $d^\circ(A'_p)> 1$, then $f(A_p')\le f(A_p'')/p$. The primitive set $B:=A_p''$ satisfies $f(B)=f(B_p)=\sum_{q\ge p}f(B_q')$. Since $d^\circ(B_q') \le d^\circ(B) < d^\circ(A'_p)$, by induction we have $f(B_q') \le f(q)$. Thus, since $p$ is Zhang,
$$f(A_p'') = f(B)=\sum_{q\ge p}f(B_q')\le \sum_{q\ge p}\frac{1}{q\log q} \le \frac{1}{\log p},$$
from which we obtain $f(A_p')\le f(A_p'')/p \le 1/(p\log p)$. This completes the proof.
\end{proof}

 From this one might hope that all primes are Zhang. However, the prime 2 is not Zhang since $C> 1/\log 2$,
 and the prime 3 is not Zhang since $C-1/(2\log2)>1/\log3$. Nevertheless, as with Mertens primes, it is true that the remaining
primes up to $p_{10^8}$ are Zhang. Indeed, starting from \eqref{eq:cohen}, we
computed that
\begin{align}
\sum_{p\ge q}\frac1{p\log p} = C - \sum_{p < q}\frac{1}{p\log p} \le \frac{1}{\log q}\qquad\textrm{for all } 3< q \le p_{10^8}.
\end{align}
The computation stopped at $10^8$ for convenience, and one could likely extend this further with some patience.  It seems likely that there is also a ``race" between $\sum_{p\ge q}1/(p\log p)$
and $1/\log q$, as with Mertens primes, and that a large logarithmic density of primes $q$
are Zhang, with a small logarithmic density of primes failing to be Zhang.

A related conjecture due to Banks and Martin \cite{bm} is the chain of inequalities,
\begin{align*}
    \sum_{p}\frac{1}{p\log p} > \sum_{p\le q}\frac{1}{pq\log pq} > \sum_{p\le q\le r}\frac{1}{pqr\log pqr} > \cdots,
\end{align*}
succinctly written as $f(\N_k) > f(\N_{k+1})$ for all $k\ge1$, where
$\N_k = \{n: \Omega(n) = k\}$.  As mentioned in the introduction, we know only that
$f(\N_1)> f(\N_k)$ for all $k\ge2$ and $f(\N_2)>f(\N_3)$.
More generally, for a subset $Q$ of primes, let $\N_k(Q)$ denote the subset of $\N_k$ supported on $Q$. A result of Zhang \cite{zhang2} impies that $f(\N_1(Q)) > f(\N_{k}(Q))$ for all $k>1$, while Banks and Martin showed that $f(\N_k(Q)) > f(\N_{k+1}(Q))$ if $\sum_{p\in Q}1/p$ is not too large.
We prove a similar result in the case where $Q$ is a subset of the Zhang primes and we
replace $f(\N_k(Q))$ with $h(\N_k(Q))$. Recall $h(A) = \sum_{a\in A}1/(a\log P(a))$.

\begin{proposition}
For all $k\ge1$ and $Q\subset \mathcal P^{\textrm{Zh}}$,
we have $h(\N_k(Q)) \ge h(\N_{k+1}(Q))$.
 \end{proposition}
\begin{proof}
Since $p_k$ is a Zhang prime, we have
\begin{align*}
h(\N_{k+1}(Q)) & = \sum_{\substack{q_1\le \cdots\le q_{k+1}\\ q_i\in Q}}\frac{1}{q_1\cdots q_k q_{k+1}\log q_{k+1}} \\
& = \sum_{\substack{q_1\le \cdots\le q_{k}\\ q_i\in Q}}\frac{1}{q_1\cdots q_{k}}\sum_{q_{k+1}\ge q_{k}}\frac{1}{q_{k+1}\log q_{k+1}}\\
& \le \sum_{\substack{q_1\le \cdots\le q_{k}\\ q_i\in Q}}\frac{1}{q_1\cdots q_{k} \log q_k} = h(\N_{k}(Q)).
\end{align*}
This completes the proof.
\end{proof}

It is interesting that if we do not in some way restrict the primes used, the analogue
of the Banks--Martin conjecture for the function $h$ fails.  In particular, we have
$$
h(\N_2)>\sum_{m\le 10^4}\frac1{p_m}\sum_{n\ge m}\frac1{p_n\log p_n}
=\sum_{m\le 10^4}\frac1{p_m}\left(C-\sum_{k<m}\frac1{p_k\log p_k}\right)
>1.638,
$$
while $h(\N_1)=C<1.637$.

It is also interesting that the analogue of the Banks--Martin conjecture for the function $g$ is
false since
$$
1=g(\N_1)=g(\N_2)=g(\N_3)=\cdots\,.
$$
We have already shown in \eqref{eq:g(A)} that
$g(A'_q)\le g(q)$ for any primitive set $A$ and prime $q$, so the analogue for $g$ of the strong Erd\H os conjecture holds.

\subsection{Proof of Theorem \ref{thm:Nk}.}

We now return to the function $f$ and prove Theorem \ref{thm:Nk}.

We may assume that $k$ is large.  Let $m=\lfloor\sqrt{k}\rfloor$ and let
$B(n)=e^{e^n}$.  We have
\begin{align*}
f(\N_k)&=\sum_{\Omega(a)=k}\frac1{a\log a} >\sum_{\substack{\Omega(a)=k\\
e^{e^{k}}<a\le e^{e^{k+m}}}}\frac1{a\log a}\\
&=\sum_{j\le m}\sum_{\substack{\Omega(a)=k\\B({k+j-1})<a\le
B(k+j)}}\frac1{a\log a} >
\sum_{j\le m}\frac1{\log
B({k+j})}\sum_{\substack{\Omega(a)=k\\B(k+j-1)<a\le B({k+j})}}
\frac1a.
\end{align*}
Thus it suffices to show that there is a positive constant $c$ such that for $j\le m$ we have
\begin{equation}
\label{eq:ss}
\sum_{\substack{\Omega(a)=k\\B({k+j-1})<a\le B({k+j})}}\frac1a
\ge c\frac{\log B({k+j})}m=c\frac{e^{k+j}}m,
\end{equation}
so that the proposition will follow.

Let $N_k(x)$ denote the number of members of $\N_k$ in $[1,x]$.
We use the Sathe--Selberg theorem, see \cite[Theorem 7.19]{MV},
from which we have that uniformly for $B({k})< x\le B({k+m})$, as $k\to\infty$,
$$
N_k(x)\sim \frac x{k!}\frac{(\log\log x)^k}{\log x}.
$$
This result also follows from Erd\H os \cite{erdos48}.

We have
\begin{align*}
\sum_{\substack{\Omega(a)=k\\B({k+j-1})<a\le B({k+j})}}\frac1a
&>\int_{B({k+j-1})}^{B({k+j})}\frac{N_k(x)-N_k(B({k+j-1}))}{x^2}\,dx\\
&\gg \int_{2B({k+j-1})}^{B({k+j})}\frac{N_k(x)}{x^2}\,dx.
\end{align*}
Thus,
\begin{align*}
\sum_{\substack{\Omega(a)=k\\B({k+j-1})<a\le B({k+j} )}}\frac1a
&\gg \frac{(\log\log
B({k+j-1}))^k}{k!}\int_{2B({k+j-1})}^{B({k+j})}\frac{dx}{x\log x}\\
&=\frac{(k+j-1)^k}{k!}(\log\log B({k+j})-\log\log(2B({k+j-1}))\\
&\gg\frac{(k+j-1)^k}{k!}\gg\frac{e^{k+j}}{\sqrt{k}},
\end{align*}
the last estimate following from Stirling's formula.  This proves
\eqref{eq:ss},
and so the theorem.

The sets $\N_k$ and Theorem \ref{thm:Nk} give us the following result.
\begin{corollary}
\label{cor:largex}
We have that
$$
\limsup_{x\to\infty}\{f(A):A\subset[x,\infty),\,A \textnormal{ primitive}\}>0.
$$
\end{corollary}

\section*{Acknowledgments}
We thank Greg Martin for  the content of Remark \ref{rmk:martin} and Kevin Ford for the content of
Remark \ref{rmk:ford}.
We thank Paul Kinlaw and Zhenxiang Zhang for some helpful comments.

\bibliographystyle{amsplain}


TITLE: Collatz Conjecture: Understanding the Chain Equation (2.1) in the proof by Simons & de Weger (2003)
QUESTION [3 upvotes]: I am trying to understand the observations that make up the Chain Equation (2.1) from this paper by Simons & de Weger (2003).
I am not clear on the first two observations in the statement of the chain equation.
Let:

$n$ be a natural number.

$T(n) = \begin{cases}
\frac{1}{2}(3n + 1), && \text{if }n\text{ is odd}\\
\frac{1}{2}n, && \text{if }n\text{ is even}\\
\end{cases}$

sequence be an increasing subsequence of odd integers followed by a decreasing subsequence of even integers

a cycle be an $m$-cycle if it consists of $m$ sequences with a total of $K$ odd numbers and a total of $L$ even numbers.

a non-trivial cycle be any cycle that contains natural numbers greater than $2$.

a sequence is periodic if there exists an integer $p \ge 1$ in the sequence $\{ n, T(n), T^2(n), \dots, T^{p}(n) \}$ where:

$T^0(n) = n$
$T^{i+1}(n) = T(T^i(n))$
$T^p(n) = n$

$t_0, t_1, \dots, t_{m-1}$ be the indices of the $m$ local minima in an $m$-cycle such that:

$t_0 = 0$
$t_0 < t_1 < t_2 < \dots < t_{m-1} < p$

$s_0, s_1, \dots, s_{m-1}$ be the indices of the $m$ local maxima in an $m$-cycle such that:

$t_0 < s_0 < t_1 < s_1 < \dots < t_{m-1} < s_{m-1} \le p-1$

$x_i, y_i$ be the values of the local minima and maxima so that:

$x_i = T^{t_i}(n)$
$y_i = T^{s_i}(n)$

$k_i, l_i$ be defined so that:

$k_i = s_i - t_i$ for $i = 0, \dots, m-1$
$l_i = t_{i+1} - s_i$ for $i = 0, \dots, m-2$ and $l_{m-1} = p + t_0 - s_{m-1}$
$K = \sum\limits_{i=0}^{m-1}k_i$
$L = \sum\limits_{i=0}^{m-1}l_i$

I am unclear on Observation 1 and Observation 2 relating to the chain equation. I am clear on Observation 3 and Observation 4.
Observation 1: $x_i = 2^{k_i}a_i - 1$ for some $a_i \ge 1$

Since $x_i$ is odd, there exists $u$ such that $x_i = 2u + 1 = 2(u+1)-1$

$k_i = s_i - t_i$ where $s_i$ is the index of the local maxima and $t_i$ is the index of the local minima.

It is not clear to me how we can be sure that $k_i$ is the power of $2$ that applies.
Observation 2:  $y_i = 3^{k_i}a_i - 1$

If I understand correctly, then $y_i$, the value of the maxima is also odd.

To show my confusion, let's assume that $y_i = \frac{1}{2}(3x_i + 1)$ which applying Observation 1 gives:

$$y_i = \frac{1}{2}(3(2^{k_i}a_i - 1) + 1) = 3\cdot2^{k_i-1}a_i - 1$$

Which suggests that the $y_i = 3^{k_i}2^u a_i - 1$  but not $y_i = 3^{k_i}a_i - 1$.  Does this imply that $a_i$ in Observation 2 is different than the $a_i$ from Observation 1?

I am not clear how $a_i$ is the same value in both observations.
Observation 3: $y_i = 2^{l_i}x_{i+1}$
I am clear on this observation.
Observation 4: The Chain Equation:  $3^{k_i}a_i - 1 = 2^{k_{i+1}+l_i}a_{i+1} - 2^{l_i}$
I am clear on the Chain Equation.  Here's my reasoning.

Here's what I get:

$$3^{k_i}a_i - 1 = 2^{l_i}x_{i+1}$$
So that:
$$3^{k_i}a_i - 1 = 2^{l_i}2^{k_{i+1}}a_{i+1} - 2^{l_i} = 2^{k_{i+1}+l_i}a_{i+1} - 2^{l_i}$$

REPLY [5 votes]: For some integers $z_i$ and $a_i$, we have
$$x_i \equiv z_i \pmod{2^{k_i}} \implies x_i = 2^{k_i}a_i + z_i \tag{1}\label{eq1A}$$
Next, there are $k_i$ odd integer results in a row after repeated applications of the $T$ function starting with $x_i$. This gives for the first one,
$$\begin{equation}\begin{aligned}
T^{1}(x_i) & = \frac{3x_i + 1}{2} \\
& = \frac{3(2^{k_i}a_i + z_i) + 1}{2} \\
& = \frac{3(2^{k_i}a_i) + 3(z_i) + 1}{2}
\end{aligned}\end{equation}\tag{2}\label{eq2A}$$
The next one becomes
$$\begin{equation}\begin{aligned}
T^{2}(x_i) & = \frac{3T^{1}(x_i) + 1}{2} \\
& = \frac{3\left(\frac{3(2^{k_i}a_i) + 3(z_i) + 1}{2}\right) + 1}{2} \\
& = \frac{\frac{3^2(2^{k_i}a_i) + 3^2(z_i) + 3}{2} + \frac{2}{2}}{2} \\
& = \frac{3^2(2^{k_i}a_i) + 3^2(z_i) + 3 + 2}{2^2}
\end{aligned}\end{equation}\tag{3}\label{eq3A}$$
The third one is
$$\begin{equation}\begin{aligned}
T^{3}(x_i) & = \frac{3T^{2}(x_i) + 1}{2} \\
& = \frac{3\left(\frac{3^2(2^{k_i}a_i) + 3^2(z_i) + 3 + 2}{2^2}\right) + 1}{2} \\
& = \frac{\frac{3^3(2^{k_i}a_i) + 3^3(z_i) + 3^2 + 3(2)}{2^2} + \frac{2^2}{2^2}}{2} \\
& = \frac{3^3(2^{k_i}a_i) + 3^3(z_i) + 3^2 + 3(2) + 2^2}{2^3}
\end{aligned}\end{equation}\tag{4}\label{eq4A}$$
By continuing this, the general result for $T^{q}(x_i)$ for any $1 \le q \le k_i$, which you can fairly easily prove by induction & which I'll leave to you to do, becomes
$$\begin{equation}\begin{aligned}
T^{q}(x_i) & = \frac{3^{q}(2^{k_i}a_i) + 3^{q}(z_i) + \sum_{j=0}^{q-1}3^{q-1-j}2^{j}}{2^{q}} \\
& = \frac{3^{q}(2^{k_i}a_i) + 3^{q}(z_i) + 3^{q-1}\sum_{j=0}^{q-1}3^{-j}2^{j}}{2^{q}} \\
& = \frac{3^{q}(2^{k_i}a_i) + 3^{q}(z_i) + 3^{q-1}\sum_{j=0}^{q-1}\left(\frac{2}{3}\right)^{j}}{2^{q}} \\
& = \frac{3^{q}(2^{k_i}a_i) + 3^{q}(z_i) + 3^{q-1}\left(\frac{1-\left(\frac{2}{3}\right)^{q}}{1-\frac{2}{3}}\right)}{2^{q}} \\
& = \frac{3^{q}(2^{k_i}a_i) + 3^{q}(z_i) + 3^{q}\left(\frac{3^{q} - 2^{q}}{3^{q}}\right)}{2^{q}} \\
& = \frac{3^{q}(2^{k_i}a_i) + 3^{q}(z_i + 1) - 2^{q}}{2^{q}} \\
& = 3^{k_i}\left(2^{k_i-q}\right)a_i + \frac{3^{k_i}(z_i + 1)}{2^{q}} - 1
\end{aligned}\end{equation}\tag{5}\label{eq5A}$$
With $q = k_i$, \eqref{eq5A} becomes
$$T^{k_i}(x_i) = 3^{k_i}a_i + \frac{3^{k_i}(z_i + 1)}{2^{k_i}} - 1 \tag{6}\label{eq6A}$$
For $T^{k_i}(x_i)$ to be an integer requires the middle term's numerator to be a multiple of $2^{k_i}$. Since $\gcd(3^{k_i}, 2^{k_i}) = 1$, this gives for some integer $r$ that
$$2^{k_i} \mid 3^{k_i}(z_i + 1) \implies 2^{k_i} \mid z_i + 1 \implies z_i = r\left(2^{k_i}\right) - 1 \tag{7}\label{eq7A}$$
Thus, $r = 0$ gives $z_i = -1$ to be a solution. Also, the middle term in \eqref{eq5A} becomes $0$ so the equation simplifies to $T^{q}(x_i) = 3^{k_i}\left(2^{k_i-q}\right)a_i - 1$. As such, for each $q \lt k_i$, it's an odd integer, matching the requirement that these values all be odd. In addition, \eqref{eq1A} then becomes your Observation $1$, i.e.,
$$x_i = 2^{k_i}a_i - 1 \tag{8}\label{eq8A}$$
Note with $z_i = -1$ that \eqref{eq6A} simplifies to
$$T^{k_i}(x_i) = 3^{k_i}a_i - 1 \tag{9}\label{eq9A}$$
With the definitions being used, after $k_i$ iterations of applying $T$ starting with $x_i$, the set of odd numbers end and an even number is the result at this point (note this means $a_i$ must be odd). The value increases when $T$ is applied to each odd number, but it decreases with each even number, so $T^{k_i}(x_i)$ is a local maximum, i.e., it's your $y_i$. Thus, \eqref{eq9A} gives your Observation $2$, i.e.,
$$y_i = 3^{k_i}a_i - 1 \tag{10}\label{eq10A}$$


text:
\begin{algorithm}[htb!]
		\caption{Variance-Reduced QVI\label{alg-halfErr}}
		\begin{algorithmic}[1]
			\State
			\textbf{Input:} A sampling oracle for DMDP $\cM=(\cS, \cA, \br, \bP, \gamma)$
			\State
			\textbf{Input:} Upper bound on error $u\in[0,(1-\gamma)^{-1}]$ and error probability $\delta \in (0, 1)$
			\State
			\textbf{Input:}
			Initial values $\bv^{(0)}$ and policy $\pi^{(0)}$ such that $\bv^{(0)}\le \cT_{\pi^{(0)}}\bv^{(0)}$, and $\bv^*-\bv^{(0)} \le u \one$;
			\State\textbf{Output:} $\bv, \pi$ such that $\bv \le \cT_{\pi}(\bv)$ and $\bv^*-\bv \le (u/2)\cdot\one$.
			\State
			\State\textbf{INITIALIZATION:}
			\State Let $\beta\gets (1-\gamma)^{-1}$, and $R\gets\lceil c_1\beta\ln[\beta u^{-1}]\rceil$ for constant $c_1$;
			\State Let $m_1 \gets{c_2\beta^3u^{-2}{\log(8|\cS||\cA|\delta^{-1})} }{}$ for constant $c_2$;
			\State Let $m_2\gets {c_3\beta^{2}\log[2R|\cS||\cA|\delta^{-1}]}$ for constant $c_3$;
			\State Let $\alpha_1\gets{m_1}^{-1}{\log(8|\cS||\cA|\delta^{-1})}$;
			\State
			For each  $(s, a)\in \cS\times\cA$,
			sample independent samples $s_{s,a}^{(1)}, s_{s,a}^{(2)}, \ldots, s_{s,a}^{(m_1)}$ from $\bP_{s,a}$;
			\State
			Initialize $\bw=\wt{\bw} = \wh{\bsigma}=\bQ^{(0)} \gets {\bf0}_{\cS \times \cA}$, and $i\gets 0$;
			\For{each $(s, a)\in \cS\times\cA$}
			\State \emph{\textbackslash \textbackslash Compute empirical estimates of $\bP_{s,a}^{\top}\bv^{(0)}$ and $\bsigma_{\bv^{(0)}}(s,a)$}
			\State
			Let $\wt{\bw}(s,a) \gets \frac{1}{m_1}
			\sum_{j=1}^{m_1} \bv^{(0)}(s_{s,a}^{(j)})$
			\label{alg1: compute w1}
			\State

			Let $\wh{\bsigma}(s,a)\gets \frac{1}{m_1} \sum_{j=1}^{m_1}(\bv^{(0)})^2(s_{s,a}^{(j)}) - \wt{\bw}^2(s,a)$  \label{alg1: compute w}
			\State

			\State \emph{\textbackslash \textbackslash Shift the empirical estimate to have one-sided error and guarantee monotonicity }
			\State
			$\bw(s, a) \gets \wt{\bw}(s,a) - \sqrt{2\alpha_1\wh{\bsigma}(s,a)} - 4\alpha_1^{3/4}\norm{\bv^{(0)}}_\infty - (2/3)\alpha_1\norm{\bv^{(0)}}_{\infty}$

			\State

			\State \emph{\textbackslash \textbackslash Compute coarse estimate of the  $Q$-function}

			\State
			$\bQ^{(0)}(s,a) \gets \br(s,a) + \gamma \bw(s,a)$

			\EndFor
			\State

			\State\textbf{REPEAT:} \emph{\qquad\qquad\textbackslash \textbackslash successively improve}
			\For{$i=1$ to $R$}
			\State  \emph{\textbackslash \textbackslash Compute $\bg^{(i)}$ the estimate of $\bP \big[\bv^{(i)}  - \bv^{(0)}\big]$ with one-sided error}
			\State\label{alg: v1} Let ${\bv}^{(i)} \gets \bv( \bQ^{(i-1)})$, ${\pi}^{(i)}\gets \pi(\bQ^{(i-1)})$; \textbackslash \textbackslash \emph{let $\wt{\bv}^{(i)}\gets \bv^{(i)}, \wt{\pi}^{(i)}\gets {\pi}^{(i)}$ (for analysis)};
			\State\label{alg: v2} For each $s\in \cS$, if ${\bv}^{(i)}(s)\le \bv^{(i-1)}(s)$, then
			$\bv^{(i)}(s)\gets \bv^{(i-1)}(s)$ and $\pi^{(i)}(s)\gets \pi^{(i-1)}(s)$;
			\State For each $(s, a)\in \cS\times\cA$,
			draw independent samples $\wt{s}_{s,a}^{(1)}, \wt{s}_{s,a}^{(2)}, \ldots, \wt{s}_{s,a}^{(m_2)}$ from $\bP_{s,a}$;
			\State  \label{alg1: compute g} Let $\bg^{(i)}(s,a)\gets {\frac{1}{m_2}} \sum_{j=1}^{m_2} \big[\bv^{(i)}(\wt{s}_{s,a}^{(j)}) - \bv^{(0)}(\wt{s}_{s,a}^{(j)}) \big]- (1-\gamma)u/8$; \\
\State  \emph{\textbackslash \textbackslash Improve $\bQ^{(i)}$}
			\State \label{alg: q-func} $\bQ^{(i)}\gets \br + \gamma\cdot[\bw+\bg^{(i)}]$;
			\EndFor
			\State \textbf{return} $\bv^{(R)}, \pi^{(R)}$.
		\end{algorithmic}
	\end{algorithm}
	\vspace{-2mm}

\section{Algorithm and Analysis}
\label{sec:alg_policy}

In this section we provide and analyze our near sample/time optimal
 $\epsilon$-policy computation algorithm. As discussed in Section~\ref{sec:overview} our algorithm combines three main ideas: variance reduction, the monotone value/policy iteration, and the reduction of accumulated error via Bernstein inequality. These ingredients are used in the Algorithm~\ref{alg-halfErr} to provide a routine which halves the error of a given policy. We analyze this procedure in Section~\ref{sub:var_reduce} and use it to obtain our main result in Section~\ref{sub:halving}.

\subsection{The Analysis of the Variance Reduced Algorithm}
\label{sub:var_reduce}

In this section we analyze Algorithm~\ref{alg-halfErr}, showing that each iteration of the algorithm approximately contracts towards the optimal value and policy and that ultimately the algorithm halves the error of the input value and policy with high probability. All proofs in this section are deferred to Appendix~\ref{sec:proof of main alg}.

We start with bounding the error of $\wt{\bw}$ and $\wh{\bsigma}$ defined in Line \ref{alg1: compute w1} and \ref{alg1: compute w} of Algorithm 1.
Notice that these are the empirical estimations of $\bP_{s,a}^{\top}\bv^{(0)}$ and $\bsigma_{\bv^{(0)}}(s,a)$.
\begin{lemma}[Empirical Estimation Error]
    \label{lemma: emprical mean}
	Let $\wt{\bw}$ and $\wh{\bsigma}$ be computed in Line \ref{alg1: compute w1} and \ref{alg1: compute w} of Algorithm \ref{alg-halfErr}.
	Recall that $\wt{\bw}$ and $\wh{\bsigma}$ are empirical estimates of $\bP\bv$ and $\bsigma_{\bv}=\bP\bv^2 - (\bP\bv)^2$ using $m_1$ samples per $(s,a)$ pair.

	With probability at least $1-\delta$, for $L \defeq \log(8|\cS||\cA|\delta^{-1})$, we have
	\begin{align}
	\label{eqn:estimate pv}

    \big|{\wt{\bw} - \bP^\top\bv^{(0)}}\big|\le \sqrt{{2m_1^{-1}\bsigma_{\bv^{(0)}}\cdot{L}}} + {2(3m_1)^{-1}\norm{\bv^{(0)}}_{\infty} {L}}
	\end{align}
and
	\begin{align}
		\label{eqn:estimate sigma}
		\forall (s,a)\in \cS\times \cA:\quad
		\big|\wh{\bsigma}(s,a) - \bsigma_{\bv^{(0)}}(s, a)\big| \le 4\norm{\bv^{(0)}}_{\infty}^2 \cdot \sqrt{{2m_1^{-1}{L}}}.
	\end{align}
\end{lemma}
The proof is a straightforward application of Bernstein's inequality and Hoeffding's inequality.

Next we show that the difference between $\sigma_{\bv^{(0)}}$ and $\sigma_{\bv^{*}}$ is also bounded.

\begin{lemma}
\label{lemma: variance triangle}
Suppose $\norm{\bv-\bv^*}_{\infty}\le \epsilon$ for some $\epsilon > 0$, then
$
\sqrt{\bsigma_{\bv}} \le \sqrt{\bsigma_{\bv^*}} + \epsilon\cdot\one.
$
\end{lemma}
Next we show that in Line~\ref{alg1: compute g}, the computed $\bg^{(i)}$ concentrates to and is an overestimate of $\bP[\bv^{(i)}  - \bv^{(0)}]$ with high probability.
\begin{lemma}
	\label{lemma:bounds on g}
	Let $\bg^{(i)}$ be the estimate of $\bP\big[\bv^{(i)}  - \bv^{(0)}\big]$ defined in Line~\ref{alg1: compute g} of Algorithm~\ref{alg-halfErr}.

	Then conditioning on the event that $\norm{\bv^{(i)} - \bv^{(0)}}_{\infty}\le 2u$, with probability at least $1-\delta/R$,
	\vspace{-1mm}
	\[
		\bP  \big[\bv^{(i)}  - \bv^{(0)}\big] - \frac{(1-\gamma)u}{4}\cdot\one\le \bg^{(i)} \le \bP  \big[\bv^{(i)}  - \bv^{(0)}\big]
	\]
	provided appropriately chosen constants $c_1$, $c_2$, and $c_3$ in Algorithm~\ref{alg-halfErr}.
\end{lemma}

Now we present the key contraction lemma, in which we set the constants, $c_1, c_2, c_3$, in Algorithm~\ref{alg-halfErr} to be sufficiently large (e.g., $c_1 \ge 4, c_2\ge8192, c_3\ge128$).

Note that these constants only need to be sufficiently large so that the concentration inequalities hold.
\begin{lemma}
	\label{lemma:induction lemma}
Let $\bQ^{(i)}$ be the estimated $Q$-function of $\bv^{(i)}$ in Line~\ref{alg: q-func} of Algorithm 1.

Let $\pi^{(i)}$ and $\bv^{(i)}$ be estimated in iteration $i$, as defined in Line~\ref{alg: v1} and \ref{alg: v2}.

Then, with probability at least $1- 2\delta$, for all

$1\le i \le R$,
\[
\bv^{(i-1)}\le \bv^{(i)}\le \cT_{\pi^{(i)}}[\bv^{(i)}],\quad \bQ^{(i)}\le \br+\gamma\bP \bv^{(i)},
\quad\text{and}\quad
\bQ^* - \bQ^{(i)} \le \gamma \bP^{\pi^*}\big[\bQ^* - \bQ^{(i-1)}\big]
 +\bxi,
\]

where for $\alpha_1=m_1^{-1}L< 1$ the error vector $\bxi$ satisfies
\[
{\bf0}\le \bxi\le C\sqrt{\alpha_1\bsigma_{\bv^*}} +\Big[{(1-\gamma)u}/C+ C\alpha_1^{3/4}\norm{\bv^{(0)}}_\infty\Big]\cdot\one,
\]
for some sufficiently large constant $C\ge 8$.

\end{lemma}

Using the previous lemmas we can prove the guarantees of Algorithm~\ref{alg-halfErr}.

\begin{proposition}
	\label{thm:alg 1}

	On an input value vector $\bv^{(0)}$, policy $\pi^{(0)}$, and parameters $u\in(0, (1-\gamma)^{-1}], \delta\in(0,1)$ such that $\bv^{(0)}\le \cT_{\pi^{(0)}}[\bv^{(0)}]$, and $\bv^*-\bv^{(0)} \le u \one$,
	Algorithm~\ref{alg-halfErr} halts in time
	\[
	O\bigg[\bigg(u^{-2}
	+
	\log\frac{1}{(1-\gamma)u}\bigg)\cdot \frac{|\cS||\cA|\cdot \log(|\cS||\cA|\delta^{-1})}{(1-\gamma)^{3}}
	\bigg]

	\]
	and outputs values $\bv$ and policy $\pi$ such that

$	\bv \le \cT_{\pi}(\bv)$

 and
$ \bv^*-\bv \le (u/2) \one$

with probability at least $1-\delta$, provided appropriately chosen constants, $c_1, c_2, c_3$.
\end{proposition}

We prove this proposition by iteratively applying Lemma~\ref{lemma:induction lemma}. Suppose
$\bv^{(R)}$ is the output of the algorithm, after $R$ iterations. We show
$
\bv^* - \bv^{(R)} \le\gamma^{R-1}\bP^{\pi^*}\big[\bQ^* - \bQ^{0}\big] + (\bI-\gamma\bP^{\pi^*})^{-1}\bxi.
$
Notice that $(\bI-\gamma\bP^{\pi^*})^{-1}\bxi$ is related to $(\bI-\gamma\bP^{\pi^*})^{-1}\sqrt{\bsigma_{\bv^*}}$.
We then apply the variance analytical tools presented in Section~\ref{sec:var_bounds} to show that
$(\bI-\gamma\bP^{\pi^*})^{-1}\bxi \le (u/4) \one$ when setting the constants properly in Algorithm~\ref{alg-halfErr}.
We refer this technique as the \emph{total-variance technique}, since $\|(\bI-\gamma\bP^{\pi^*})^{-1}\sqrt{\bsigma_{\bv^*}}\|_{\infty}^2\le O[(1-\gamma)^{-3}]$

instead of a na\"ive bound of $(1-\gamma)^{-4}$.
We complete the proof by choosing $R=\wt{\Theta}((1-\gamma)^{-1}\log(u^{-1}))$ and showing that $\gamma^{R-1}\bP^{\pi^*}\big[\bQ^* - \bQ^{0}\big]\le  (u/4) \one$.

\subsection{From Halving the Error to Arbitrary Precision}
\label{sub:halving}

In the previous section, we provided an algorithm that on an input policy, outputs a policy with value vector that has $\ell_\infty$ distance to the optimal value vector only half of that of the input one.

In this section, we give a complete policy computation algorithm by by showing that it is possible to apply this error ``halving'' procedure iteratively. We summarize our meta algorithm in Algorithm~\ref{alg-meta}.
Note that in the algorithm, each call of $\halfErr$ draws new samples from the sampling oracle.
We refer in this section to Algorithm~\ref{alg-halfErr} as a subroutine \halfErr, which given an input MDP $\cM$ with a sampling oracle, an input value function $\bv^{(i)}$, and an input policy $\pi^{(i)}$, outputs an value function  $\bv^{(i+1)}$ and a policy $\pi^{(i+1)}$.

{\small
\begin{algorithm}[tb!]\caption{Meta Algorithm\label{alg-meta}}
	\begin{algorithmic}[1]
		\State
		\textbf{Input:} A sampling oracle of some $\cM=(\cS, \cA, \br, \bP, \gamma)$, $\epsilon>0, \delta\in(0,1)$
		\State
		\textbf{Initialize:} $\bv^{(0)}\gets{\bf 0}$, $\pi^{(0)}\gets$ arbitrary policy, $R\gets \Theta[\log(\epsilon^{-1}(1-\gamma)^{-1})]$
		\For{$i=\{1,2,\ldots,R\}$}
		\State //\emph{\halfErr~ is initialized with QVI$(u=2^{-i+1}(1-\gamma)^{-1}, \delta, \bv^{(0)}=\bv^{(i-1)}, \pi^{(0)}=\pi^{(i-1)})$}
		\State $\bv^{(i)},\pi^{(i)}\gets\halfErr\gets \bv^{(i-1)},\pi^{(i-1)}$
		\EndFor
		\State
		\textbf{Output:} $\bv^{(R)},\pi^{(R)}$.
	\end{algorithmic}
\end{algorithm}
}

Combining Algorithm~\ref{alg-meta} and Algorithm~\ref{alg-halfErr}, we are ready to present main result.
\begin{theorem}
	\label{thm:dmdp1}
    Let $\cM=(\cS, \cA, \bP, \br, \gamma)$ be a DMDP with a generative model.
    Suppose we can sample a state from each probability vector $\bP_{s,a}$ within time $O(1)$.	Then for any $\epsilon,\delta\in(0,1)$, there exists an algorithm that halts in time

	\[
		T:=O\left[\frac{|\cS||\cA|}{(1-\gamma)^3 \epsilon^2} \log \left(\frac{|\cS||\cA|}{ (1-\gamma)\delta\epsilon}\right)\log\left(\frac{1}{(1-\gamma)\epsilon}\right)\right]
	\]
	and obtains a policy $\pi$ such that $\bv^* - \epsilon\one\le \bv^{\pi} \le \bv^*$, with probability at least $1-\delta$ where $\bv^{*}$ is the optimal value of $\cM$.
	The algorithm uses space $O(|\cS||\cA|)$ and queries the generative model for at most $O(T)$ fresh samples.

\end{theorem}
\begin{remark}
In the above theorem, we require $\epsilon\in(0,1)$.
For $\epsilon\ge 1$, our sample complexity may fail to be optimal.
We leave this for a future project.
\end{remark}
\begin{remark}
	The full analysis of the halving algorithm is presented in Section~\ref{sec:half}.
	Our algorithm can be implemented in space $O(|\cS||\cA|)$ since in Algorithm~\ref{alg-halfErr}, the initialization phase can be done for each $(s,a)$ and compute $\bw(s,a), \wt{\bw}(s,a),$ $\wh{\bsigma}(s,a), \bQ^{(0)}(s,a)$ without storing the samples.
	The updates can be computed in space $O(|\cS||\cA|)$ as well.
\end{remark}