text:
\begin{document}

\title{ \huge On the Deterministic Code Capacity Region
of an Arbitrarily Varying Multiple-Access Channel Under List Decoding}

\author{
\authorblockN{Sirin Nitinawarat}
\authorblockA{Department of Electrical and Computer Engineering\\
and Institute for Systems Research \\
University of Maryland\\ College Park, MD 20742, USA \\
Email: nitinawa@umd.edu}
}

\maketitle

\begin{abstract}

We study the capacity region $C_L$ of an arbitrarily varying
multiple-access channel (AVMAC) for deterministic codes with
decoding into a list of a fixed size $L$ and for the average error
probability criterion. Motivated by known results in the study of
fixed size list decoding for a point-to-point arbitrarily varying
channel, we define for every AVMAC whose capacity region for
random codes is nonempty, a nonnegative integer $U$ called its
symmetrizability. It is shown that for every $L \leq U$, $C_L$ has
an empty interior, and for every $L \geq (U+1)^2$, $C_L$ equals
the capacity region of the AVMAC for random codes with a known
single-letter characterization.

\end{abstract}

\section{Introduction}

We study the deterministic code capacity region of an arbitrarily
varying multiple-access channel (AVMAC) under fixed size-$L$ list
decoding.

For every received sequence, a list decoder outputs a list of
message pairs of size at most $L$.  The error occurs when the
transmitted message pair is not in the output list. We restrict
ourselves to a discrete memoryless AVMAC with finite inputs,
output and state alphabets and the average error probability
criterion.

For point-to-point transmission over an arbitrarily varying
channel (AVC), it is known \cite{Ahlswede_78} that the
(list-of-$1$ size) deterministic code capacity equals either 0 or
the random code capacity.  The latter capacity is defined for a
``random code'' in which the encoder and the decoder are assumed
to have shared access to a random experiment whose result can be
used in selecting a deterministic code from a pool of such codes.
Later, it was shown in \cite{Ericson_85, Csiszar_Narayan_88} that
a necessary and sufficient condition for the deterministic code
capacity to be zero is when the AVC is ``symmetrizable.'' When
list decoding of a fixed size $L$ is considered, it also holds
that the list-of-$L$ size capacity for deterministic codes equals
either 0 or the random code capacity; a necessary and sufficient
condition for the list-of-$L$ size capacity for deterministic
codes to be zero was given in \cite{Blinovsky-Narayan-Pinsker_95,
Hughes_97} in terms of a quantity termed the ``symmetrizability''
of the AVC defined in \cite{Hughes_97}.  This latter concept can
be regarded as a generalization of the symmetrizable condition of
the AVC considered in \cite{Ericson_85, Csiszar_Narayan_88}.
Precisely, an AVC is symmetrizable if its symmetrizability is at
least 1.

Next, turning to transmission over an AVMAC with the usual
decoding ($L$ = 1), Jahn \cite{Jahn_81} has shown that the
capacity region $C_1$ for deterministic codes either has an empty
interior or equals the random code capacity region defined and
characterized therein.  Gubner \cite{Gubner_90} introduced the
symmetrizable condition for an AVMAC and showed that it implies
that the interior of $C_1$ is empty.  Later, Ahlswede and Cai
\cite{Ahlswede-Cai_99} proved that this condition is also
necessary for $C_1$ to have an empty interior.

In the present paper, we introduce a concept of symmetrizability
of an AVMAC and study its relationship with its list-of-$L$ size
capacity region for deterministic codes

\section{Preliminaries}

We start with the definition of a discrete memoryless AVMAC and
certain quantities showing its specific behavior.

Let $\mathcal{X}, \mathcal{Y}, \mathcal{Z}$ and $\mathcal{S}$ be
finite sets representing the alphabets of the two inputs, output
and state, respectively.  The AVMAC is determined by a family of
conditional distributions $W(z|x, y, s)$ on $\mathcal{Z} (z \in
\mathcal{Z})$, defined by two input symbols $x \in \mathcal{X},\ y
\in \mathcal{Y}$ and a state $s \in \mathcal{S}$. It is assumed
that the AVMAC is memoryless, i.e., that the transition
probability function $W^n({\bf z} | {\bf x}, {\bf y}, {\bf s}),\
{\bf x} = (x_1, \ldots, x_n) \in \mathcal{X}^n,\ {\bf y} = (y_1,
\ldots, y_n) \in \mathcal{Y}^n,\ (z_1, \ldots, z_n) \in
\mathcal{Z}^n,\ {\bf s} = (s_1, \ldots, s_n) \in \mathcal{S}^n$
satisfies $W^n({\bf z} | {\bf x}, {\bf y}, {\bf s}) = \prod_{i =
1}^n W(z_i | x_i, y_i, s_i)$.  We denote such a channel as $G=(W,
\mathcal{X}, \mathcal{Y}, \mathcal{S}, \mathcal{Z})$.  A
deterministic code $(\mathcal{U}^{(n)}, \mathcal{V}^{(n)})$ of
length $n$ and cardinalities $M_1$, $M_2$ is a collection of
$\mathcal{U}^{(n)} = \{{\bf x}_1, \ldots, {\bf x}_{M_1}\}
~\subseteq~ \mathcal{X}^n$ and $\mathcal{V}^{(n)} = \{{\bf y}_1,
\ldots, {\bf y}_{M_2}\} ~\subseteq~ \mathcal{Y}^n$. We call $R_1 =
\frac{1}{n} \log_2{M_1}$ (resp. $R_2 = \frac{1}{n} \log_2{M_2}$)
the {\em rate} of the code for transmitter 1 (resp. transmitter 2)
and $(R_1, R_2)$ the {\em rate-tuple} of the code.

In the present paper, we consider list decoding of a fixed size $L$;
the usual decoding
corresponds to a special case of $L = 1$.  Given $M_1$ and $M_2$, a
list-of-$L$ size decoder is defined with a collection
$\{A_{ij}\}_{i=1,\ j=1}^{M_1,\ M_2}$ with $A_{ij} \subseteq
\mathcal{Z}^n,\ i=1, \ldots, M_1,\ j=1, \ldots, M_2,$ representing
the set of all received sequences each having the message pair
$(i, j)$ in its decoding list.  Further, it is
required that $\bigcap_{(i,j) \in K} A_{ij} = \emptyset$ for all
$K \subseteq [M_1] \times [M_2]$ with $|K| \geq L + 1$, where
$[M_1] \triangleq \{1, \ldots, M_1\},
[M_2] \triangleq \{1, \ldots, M_2\}$.
Consequently, a received sequence ${\bf z}$ is decoded into a list
of $L' \leq L$ message pairs
$\{(i_1, j_1), \ldots, (i_{L'}, j_{L'})\} \subseteq
[M_1] \times [M_2]$.  The decoding rule is
$\phi_L({\bf z}) = \{(i,j) \in [M_1] \times [M_2]:\ {\bf z} \in A_{ij}\}$.
The code together with the decoder $\mathcal{C}_L = (\mathcal{U},
\mathcal{V}, \phi_L)$ is called a deterministic code decoded into
a list of size $L$.  The error probability of decoding into a
list of size $L$ when the message pair $(i,j)$ is transmitted over
the AVMAC in the state ${\bf s} \in \mathcal{S}^n$ is defined as
\begin{eqnarray}
    e_L(i, j, {\bf s}) &=& e_L(i, j, {\bf s}, \mathcal{C}_L) \nonumber \\
    &\triangleq& \sum_{{\bf z} \in \mathcal{Z}^n:\, (i,j) \notin \phi_L({\bf z})}
        W^n({\bf z}| {\bf x}_i, {\bf y}_j, {\bf s})
\end{eqnarray}
and the corresponding average error probability is defined as
\begin{equation}
    \bar{e}_L({\bf s})\ =\ \bar{e}_L({\bf s}, \mathcal{C}_L)\ \triangleq\
    \sum_{i = 1}^{M_1} \sum_{j = 1}^{M_2} \frac{1}{M_1 M_2}
    e_L(i, j, {\bf s}).
\end{equation}
For $R_1 >0, R_2 >0$, we are interested in the quantity
\begin{equation}
\nonumber
    \bar{p}_L(R_1, R_2) \ =\ \limsup_{n \rightarrow \infty}~
    ~\mathop{\min_{\mathcal{C}_L,\ \log_2{M_1} \geq R_1 n}}_{\ \ \ \ \log_2{M_2} \geq R_2 n}
    ~\max_{{\bf s} \in \mathcal{S}^n} \bar{e}_L({\bf s}, \mathcal{C}_L).
\end{equation}
Define the {\em list-of-$L$ size capacity region} $C_L = C_L(G)$
of $G$ for deterministic codes under the average error probability
criterion to be the closure of the region $\{(R_1 \geq 0, R_2 \geq
0):\ \bar{p}_L(R_1, R_2) = 0\}$; let $int(C_L)$ denote the
interior of $C_L$.

The random code capacity region $C^R$, defined in \cite{Jahn_81},
will play a central role in this paper.  $C^R$ was characterized
therein as the closure of the convex hull of the following region
\begin{equation}
    \mathop{\bigcup_{P_X(x)}}_{P_Y(y)}
    \left \{ (R_1, R_2):
    \begin{array}{ll}
        0 \leq R_1 \leq \inf_{P_S(s)}
                 I(X \wedge Z | Y) \\
        0 \leq R_2 \leq \inf_{P_S(s)}
                 I(Y \wedge Z | X) \\
        R_1 + R_2 \leq \inf_{P_S(s)}
                 I(X, Y \wedge Z)
    \end{array} \right \}, \nonumber
\end{equation}
with the union being over all distributions $P_X$ on $\mathcal{X}$
and $P_Y$ on $\mathcal{Y}$ and with the joint distribution of $(X,
Y, Z) \in \mathcal{X} \times \mathcal{Y} \times \mathcal{Z}$ being
$P_{XYZ}(x, y, z) = P_X(x) P_Y(y) \sum_{s \in
\mathcal{S}} P_S(s) W(z|x, y,s)$.

\section{Main Results}

The following proposition extends the statement of Jahn
\cite{Jahn_81} from $L = 1$ to the case $L \geq 1$.

\vspace{0.05in} \textbf{Proposition 1:}  {\em Either $C_L$ equals
$C^R$ or $~int(C_L) = \emptyset$.} \vspace{0.05in}

The proof of Proposition 1 follows the derivation in
\cite{Jahn_81}.  When $~int(C_L) \neq \emptyset$, a
deterministic prefix code can be used with decoding into a list of
size $L$ at a rate-tuple with each individual rate being nonzero
to show that $C_L \supseteq C^R$. The fact that $C_L \subseteq
C^R$ also follows, upon noting that $C_1 \subseteq C^R$, in a
similar manner to the AVC case \cite{Blinovsky-Narayan-Pinsker_95,
Hughes_97} and an exercise in \cite[p. 230]{Csiszar_Korner_81}.

\vspace{0.05in}
\textbf{Definition 1:}  For a positive integer $u$, an AVMAC $G$ is
{\em u-symmetrizable} if either of the following holds.

a) There exists a conditional distribution\\
$U(s | x_2, y_2, \ldots, x_{u+1}, y_{u+1}),\ s \in \mathcal{S},$\\
$(x_2, y_2), \ldots, (x_{u+1}, y_{u+1}) \in \mathcal{X} \times \mathcal{Y}$
such that for any $x_1, \ldots, x_{u+1} \in \mathcal{X},\
y_1, \ldots, y_{u+1} \in \mathcal{Y},\ z \in \mathcal{Z}$ and any permutation $\pi$ on $[u+1] \triangleq
\{1, \ldots, u+1\}$,
\begin{equation}
    \hspace{-0.5in} \sum_{s \in \mathcal{S}} W(z | x_1, y_1, s)
                U(s | x_2, y_2, \ldots, x_{u+1}, y_{u+1}) = \nonumber
\end{equation}
\begin{equation}
    \label{sym-1}
    \sum_{s \in \mathcal{S}} W(z | x_{\pi(1)}, y_{\pi(1)}, s)
                U(s | x_{\pi(2)}, y_{\pi(2)}, \ldots, x_{\pi(u+1)}, y_{\pi(u+1)}).
\end{equation}

b) For some $a, b$ satisfying $(a+1)(b+1) \geq u+1$,
there exists a conditional distribution\\
$U(s | x_2, \ldots, x_{a+1}, y_2, \ldots, y_{b+1}),\ s \in
\mathcal{S},\ x_2, \ldots, x_{a+1} \in \mathcal{X},$\\ $y_2,
\ldots, y_{b+1} \in \mathcal{Y}$ such that for any $x_1, \ldots,
x_{a+1} \in \mathcal{X},\ y_1, \ldots, y_{b+1} \in \mathcal{Y},\ s
\in \mathcal{S},\ z \in \mathcal{Z}$, and any permutations $\pi$
on $[a+1]$ and $\sigma$ on $[b+1]$,
\begin{equation}
    \hspace{-0.4in} \sum_{s \in \mathcal{S}} W(z | x_1, y_1, s)
                U(s | x_2, \ldots, x_{a+1}, y_2, \ldots, y_{b+1}) = \nonumber
\end{equation}
$\sum_{s \in \mathcal{S}} W(z | x_{\pi(1)}, y_{\sigma(1)}, s)$
\begin{eqnarray}
    U(s | x_{\pi(2)}, \ldots, x_{\pi(a+1)}, y_{\sigma(2)}, \ldots, y_{\sigma(b+1)}).
    \label{sym-2}
\end{eqnarray}
To simplify terminology, we take all AVMACs to be 0-symmetrizable.
It is clear that if $G$ is $u$-symmetrizable, then $G$ is also
$u'$-symmetrizable for all $0 \leq u' \leq u$.  The symmetrizability
of $G$ denoted by $U = U(G)$ is defined as the largest integer $u$
for which $G$ is $u$-symmetrizable.

\vspace{0.05in}
\textbf{Theorem 2:}  {\em For an AVMAC with symmetrizability $U$,
$~int(C_L) = \emptyset$ for every $L \leq U$.}
\vspace{0.05in}

\textbf{Theorem 3:}  {\em For an AVMAC with symmetrizability $U$
and for every $L \geq (U+1)^2$, $C_L$ equals $C^R$.}

\section{Outline of Proofs}

For a positive integer $M$, let $[M]$ denote $\{1, \ldots, M\}$.
For a set $K \subseteq [M] \times [M]$, let $I_K \triangleq \{i
\in [M]: \exists j \in [M] \mbox{~such~that}~(i,j) \in K \}$ and
$J_K \triangleq \{j \in [M]: \exists i \in [M]
\mbox{~such~that}~(i,j) \in K \}$.

\vspace{0.05in} \textbf{Outline of the Proof of Theorem 2:}  For a
fixed $L \leq U$ and any $\delta > 0$, we consider any
deterministic code (decoded into a list of size $L$)
$\mathcal{C}_L = (\mathcal{U}^{(n)}=\{{\bf x}_i\}_{i=1}^M,\
\mathcal{V}^{(n)}=\{{\bf y}_i\}_{i=1}^M,\ \phi_L({\bf z}))$ with
$R=\frac{1}{n}\log_2{M} \geq \delta$.  By Definition 1, either
(\ref{sym-1}) holds with $u = U$ or (\ref{sym-2}) holds with some
$a, b$ such that $(a+1)(b+1) = U+1$.

First, suppose that (\ref{sym-1}) holds with $u = U$. For any $K =
\{(i_1, j_1), (i_2, j_2), \ldots, (i_U, j_U)\}\subset [M] \times
[M]$, with $(i_1, j_1) < (i_2, j_2) < \ldots < (i_U, j_U)$ (for a
fixed ordering of $[M] \times [M]$), satisfying $|K| = |I_K| =
|J_K| = U$, let $S_K$ denote a random state sequence with
distribution $U^n({\bf s} | {\bf x}_{i_1}, {\bf y}_{j_1}, \ldots,
{\bf x}_{i_U}, {\bf y}_{j_U} )$. Also, for any $(i, j) \in [M]
\times [M]$, let

\vspace{0.01in} $E[W^n({\bf z} | {\bf x}_i, {\bf y}_j, S_K)]
\triangleq$
\[\sum_{{\bf s} \in \mathcal{S}^n} W^n({\bf z} | {\bf x}_i, {\bf y}_j, {\bf s})
U^n({\bf s} | {\bf x}_{i_1}, {\bf y}_{j_1}, \ldots, {\bf x}_{i_U},
{\bf y}_{j_U}).\] Then, for any $K' = \{(i_1, j_1), \ldots,
(i_{U+1}, j_{U+1})\} \subset [M] \times [M]$, with $(i_1, j_1) <
(i_2, j_2) < \ldots < (i_{U+1}, j_{U+1})$, satisfying
$|K'|=|I_{K'}|=|J_{K'}|=U+1$, we have

\vspace{0.07in}
$\sum_{k=1}^{U+1}
        E[e_L(i_k, j_k, S_{K' \backslash \{(i_k, j_k)\}})]$
\begin{eqnarray}
&=& \sum_{k=1}^{U+1}
    \left ( 1 -
      \mathop{\sum_{{\bf z}: (i_k, j_k)}}_{\ ~~~\in \phi_L({\bf z})}
      E[W^n({\bf z} | {\bf x}_{i_k}, {\bf y}_{j_k}, S_{K' \backslash \{(i_k, j_k)\}})] \right ) \nonumber
\end{eqnarray}
\begin{eqnarray}
&=& (U+1) - \nonumber \\
& &   \sum_{{\bf z}} \mathop{\sum_{k \in [U+1] :}}_{(i_k, j_k) \in \phi_L({\bf z})}
      E[W^n({\bf z} | {\bf x}_{i_1}, {\bf y}_{j_1}, S_{K' \backslash \{(i_1, j_1)\}})]      \mbox{~by~}(\ref{sym-1}) \nonumber \\
&\geq& (U+1) - L,\ \ \ \ \mbox{by~}|\phi_L({\bf z})| \leq L. \label{eqn:Proof-Thm2-1}
\end{eqnarray}

Next, let $\mathcal{P}_U = \{K \subset [M] \times
[M]:\ |K|=|I_K|=|J_K|=U \}$.  Then, $|\mathcal{P}_U| =
{\small \left( \begin{array}{cc} M \\ U \end{array} \right)^2} U!$
and

$\frac{1}{|\mathcal{P}_U|} \sum_{K \in \mathcal{P}_U}
    E[\bar{e}_L(S_K)]$
\begin{eqnarray}
    &\geq&
    \frac{1}{|\mathcal{P}_U| M^2} \sum_{K \in \mathcal{P}_U}
    \sum_{(i,j) \in I_K^c \times J_K^c} E[e_L(i, j, S_K)] \nonumber  \\
    &=&
    \frac{1}{|\mathcal{P}_U| M^2} \sum_{K' \in \mathcal{P}_{U+1}}
    \sum_{(i,j) \in K'} E[e_L(i, j, S_{K' \backslash \{(i,j)\}})] \nonumber \\
    &\geq&  \frac{|\mathcal{P}_{U+1}|(U+1)}{|\mathcal{P}_U| M^2} (1 - \frac{L}{U+1}),\
            \mbox{~by~}(\ref{eqn:Proof-Thm2-1})  \nonumber \\
    &=& (\frac{M-U}{M})^2(1-\frac{L}{U+1}). \nonumber
\end{eqnarray}
Then, for any $M=\lfloor 2^{\delta n} \rfloor$,
\[\liminf_{n
\rightarrow \infty} \frac{1}{|\mathcal{P}_U|} \sum_{K \in
\mathcal{P}_U} E[\bar{e}_L(S_K)] > 0\] if $L \leq U$. Since the
left side is an average of $\bar{e}_L({\bf s})$ with respect to a
distribution of $S_K$ with $K$ being uniform on $\mathcal{P}_U$
and $\delta > 0$ is arbitrary small, it follows that $~int(C_L) =
\emptyset$.

The case in which (\ref{sym-2}) holds with some $a, b$ satisfying
$(a+1)(b+1) = U + 1$ can be handled in a similar manner. In
particular, by considering $\mathcal{P}_{(a,b)}=\{(I,J): I \subset
[M],\ J \subset [M],\ |I| = a,\ |J| = b\}$ with
$|\mathcal{P}_{(a,b)}| =\scriptsize{\left( \begin{array}{cc} M \\
a \end{array} \right) \left( \begin{array}{cc} M \\ b \end{array}
\right)}$, we can find a positive lower bound to
\[\frac{1}{|\mathcal{P}_{(a,b)}|} \sum_{(I, J) \in
\mathcal{P}_{(a,b)}}
    E[\bar{e}_L(S_{I,J})]\]
for any $M = \lfloor 2^{\delta n} \rfloor$ where $\delta$ is
arbitrarily small.  Here, for $I = \{i_1, \ldots, i_a\} \subset
[M]$, with $i_1 < i_2 < \ldots < i_a$, and $J = \{j_1, \ldots,
j_b\} \subset [M]$, with $j_1 < j_2 < \ldots < j_b$, $S_{(I,J)}$
denotes a random state sequence with distribution $U^n({\bf s} |
{\bf x}_{i_1}, \ldots, {\bf x}_{i_a}, {\bf y}_{j_1}, \ldots, {\bf
y}_{j_b})$. The proof is omitted for this case. $\qed$

\vspace{0.05in} \textbf{Outline of Proof of Theorem 3:}  We start
with some standard notations.  For positive numbers $a, b$ and
some sequences, $({\bf x}_1, \ldots, {\bf x}_a, {\bf y}_1, \ldots,
{\bf y}_b, {\bf s}, {\bf z}) \in {(\mathcal{X}^a)}^n \times
{(\mathcal{Y}^b)}^n \times \mathcal{S}^n \times \mathcal{Z}^n,\
P_{({\bf x}_1, \ldots, {\bf x}_a, {\bf y}_1, \ldots, {\bf y}_b,
{\bf s}, {\bf z})}$ denotes the joint type of the sequences: the
empirical distribution on $\mathcal{X}^a \times \mathcal{Y}^b
\times \mathcal{S} \times \mathcal{Z}$ of the sequences.

For a finite set $\mathcal{A}$ and any two distributions $P_1(a),
P_2(a),\ a \in \mathcal{A}$, let $D(P_1 || P_2)$ (resp. $d(P_1,
P_2)$) denote the divergence (resp. variational distance) of $P_1,
P_2$.

Recall from Proposition  1 that it suffices to show that $int(C_L) \neq
\emptyset$.  To this end, we consider a ``constant composition''
code $\mathcal{U} = \mathcal{U}^{(n)}_{{\bf x}} = \{{\bf x}_1,
\ldots, {\bf x}_M\}$ and $\mathcal{V} = \mathcal{V}^{(n)}_{{\bf
y}} = \{{\bf y}_1, \ldots, {\bf y}_M\}$ with each ${\bf x}_i$
(resp. ${\bf y}_j$) being of the same type $P_X(x) = P_{({\bf
x})}$ (resp. $P_Y(y) = P_{({\bf y})}$) that coincides with the
type of a fixed sequence ${\bf x} \in \mathcal{X}^n$ (resp. ${\bf
y} \in \mathcal{Y}^n$).  We first describe a list decoding
algorithm for such codes and show in Lemma 1 that it is a
list-of-$L$ size decoder.  Then, a ``good'' code is specified in
Lemma 4 and is used, together with the decoder, to show that
$int(C_L) \neq \emptyset$.

The list decoding algorithm consists of two steps and
is parameterized by a (small) parameter $\eta > 0$ to be
chosen shortly.  This
algorithm follows the ideas of \cite{Csiszar_Narayan_88,
Blinovsky-Narayan-Pinsker_95, Hughes_97, Ahlswede-Cai_99}.

1.  Collect a list of message pairs $\Gamma \subseteq
[M] \times [M]$ such that for every $(i,j) \in \Gamma$, there exists
a state sequence ${\bf s} \in \mathcal{S}^n$ such that for
$P_{X Y S Z} = P_{({\bf x}_i, {\bf y}_j, {\bf s}, {\bf z})}$, it holds
that
\begin{equation}
    D(P_{X Y S Z} || P_{X} \times P_{Y} \times P_S \times W)
    \leq \eta.      \label{eqn:ProofThm3-1}
\end{equation}

2.  Put a message pair $(i, j)$ in
$\phi_L^{\mathcal{U}, \mathcal{V}}({\bf z})$ if $(i,j) \in \Gamma$
and if for some ${\bf s} \in \mathcal{S}^n$ satisfying
(\ref{eqn:ProofThm3-1}), it holds that for every subset
$K \subseteq \Gamma$ such that $(i,j) \in K$ and $|K| = L+1$,
\begin{equation}
    I(X Y Z \wedge X^{a-1}, Y^{b-1} | S)
    \leq \eta,          \label{eqn:ProofThm3-2}
\end{equation}
where $a = |I_K|$ and $b = |J_K|$ and $P_{X Y X^{a-1} Y^{b-1} S Z}
= P_{({\bf x}_i, {\bf y}_j, {\bf x}_{I_{K} \backslash \{i\}},
{\bf y}_{J_{K} \backslash \{j\}}, {\bf s}, {\bf z})}$.

Let $\phi_L^{\mathcal{U}, \mathcal{V}}({\bf z}) = \{(1,1)\}$ if
no $(i,j)$ satisfies (\ref{eqn:ProofThm3-1}) and (\ref{eqn:ProofThm3-2}).

\vspace{0.05in}
\textbf{Lemma 1:}  {\em There exists a function
$f:\{0, 1, \ldots \} \rightarrow \{0, 1, \ldots \}$ and a
sufficiently small $\eta$ (cf. (\ref{eqn:ProofThm3-1}) and
(\ref{eqn:ProofThm3-2})) such that for an AVMAC with
symmetrizability $U$, any $\alpha > 0$, any ${\bf x} \in
\mathcal{X}^n$ (resp. ${\bf y} \in \mathcal{Y}^n$) satisfying
$\min_{x \in \mathcal{X}} P_{({\bf x})}(x) > \alpha$ (resp.
$\min_{y \in \mathcal{Y}} P_{({\bf y})}(y) > \alpha$), every $L
\geq f(U)$ and any deterministic code $(\mathcal{U}_{{\bf x}},
\mathcal{V}_{{\bf y}})$, the decoding algorithm
$\phi_L^{\mathcal{U}, \mathcal{V}} ({\bf z})$ as above satisfies
$|\phi_L^{\mathcal{U}, \mathcal{V}} ({\bf z})| \leq L$ for every
${\bf z} \in \mathcal{Z}^n$.}
\vspace{0.05in}

\textbf{Proof:}  For positive integers $A, M$, we shall call
a set $K \subseteq [M] \times [M]$ an $A$-diagonal if $|K| = |I_K|
= |J_K| = A$ and call $K$ an $A$-rectangle if $|K| = |I_K||J_K| \geq
A$.  Further, $K$ is said to contain an $A$-diagonal (resp.
$A$-rectangle) if there exists $K' \subseteq K$ such that $K'$
is an $A$-diagonal (resp. $A$-rectangle).  For any positive integers
$A, R, M$ such that $A \leq R$, let $B(A, R, M) \triangleq
|\{K \subseteq [M] \times [M]: |K|=R,\ K \mbox{~contains~no~}A
\mbox{-diagonal~and~no~}A\mbox{-rectangle}\}|$.

{\em Claim:} for any $A \geq 1,$ any $R \geq (A-1)^2 A$ and any $M
> 0,\ B(A, R, M) = 0$.  To see this, consider an arbitrary $M > 0$
and a set $K \subseteq [M] \times [M]$ with $|K| = R \geq (A-1)^2
+1$. If $|I_K| \geq A$ and $|J_K| \geq A$, then clearly $K$
contains an $A$-diagonal.  Consider the rest of the $K$s with,
say, $|I_K| \leq A - 1$.  As $(A-1)^2+1 \leq |K| = \sum_{i \in
I_K} |K \cap \{i\} \times J_K|$ and $|I_K| \leq A-1$, there exists
an $i \in I_K$ for which $|K \cap \{i\} \times J_K| \geq A$, i.e.,
$K$ contains an $A$-rectangle.  This proves the claim.

Next, let
\begin{equation}
    g(A) \triangleq \mathop{\min_{R \geq A}}_{\sup_{M > 0} B(A, R, M) = 0} R \,\leq\, (A-1)^2 + 1,\ \mbox{by~the~Claim}.  \label{eqn:ProofThm3-3}
\end{equation}
The significance of $g$ in (\ref{eqn:ProofThm3-3}) can be understood as follows.
For $A \geq 1$ and {\em any} $M > 0$, it holds that
{\em any} set $K \subseteq [M] \times [M]$ with $|K| \geq g(A)$ must
contain either an $A$-diagonal or an $A$-rectangle.  We now let,
for every $u \geq 0$,
\begin{equation}
    f(u) \triangleq g(u+2) - 1 \leq (u+1)^2,\ \mbox{by}~
    (\ref{eqn:ProofThm3-3}). \label{eqn:ProofThm3-4}
\end{equation}
We shall prove Lemma 1 with this $f$ by
contradiction.  Suppose that there exists an output sequence
${\bf z} \in \mathcal{Z}^n$ such that $|\phi_L^{\mathcal{U}, \mathcal{V}}({\bf z})|
\geq L+1$.  Pick some $K \subseteq \phi_L^{\mathcal{U}, \mathcal{V}}({\bf z})$
with
\begin{equation}
    |K| = L + 1 \geq f(U) + 1 = g(U+2),\ \mbox{by~}(\ref{eqn:ProofThm3-4}).    \label{eqn:ProofThm3-5}
\end{equation}
Then, for any $(i, j) \in K$,
by (\ref{eqn:ProofThm3-1}) and (\ref{eqn:ProofThm3-2}),
we have that for some ${\bf s}_{ij} \in
\mathcal{S}^n$ with $P_{X_{I_K} Y_{J_K} S_{ij} Z} = P_{
({\bf x}_{I_K}, {\bf y}_{J_K}, {\bf s}_{ij}, {\bf z})}$, it holds that
\begin{eqnarray}
    2 \eta &\geq& D(P_{X_{i} Y_{j} S_{ij} Z} ||
                    P_{X_i} \times P_{Y_j} \times P_{S_{ij}} \times
                    W)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \nonumber \\
            & &   +\ I(X_i Y_j Z \wedge X_{I_K \backslash \{i\}} Y_{J_K \backslash \{j\}} | S_{ij})
                  \nonumber \\
        &=& D \left(\begin{array}{ll}
                   P_{X_{I_K} Y_{J_K} S_{ij} Z} || \\
                   P_{X_i} \times P_{Y_j} \times P_{S_{ij} X_{I_K \backslash \{i\}} Y_{J_K \backslash \{j\}}} \times
                   W
              \end{array}\right ).
              \label{eqn:ProofThm3-5-2}
\end{eqnarray}
Next, from (\ref{eqn:ProofThm3-5}) and (\ref{eqn:ProofThm3-3}),
$K$ contains either a $(U+2)$-diagonal or a $(U+2)$-rectangle.

First, consider the case in which $K$ contains a $(U+2)$-diagonal.
Specifically, there exists a subset $K' \subseteq K$ such that
$|K'|=|I_{K'}|=|J_{K'}|=U+2$.  By separately permuting the pair of
indices of $[M] \times [M]$, we can assume without any loss of
generality that $K' = \{(1,1), \ldots, (U+2, U+2)\}$.  Applying the
logsum inequality to
(\ref{eqn:ProofThm3-5-2}) to every $(i,i) \in K',\ i \in [U+2]$,
we get \\
\begin{equation}
    2 \eta \geq D \left(\begin{array}{ll}
                   P_{X^{U+2} Y^{U+2} Z} || \\
                   P_{X_i} \times P_{Y_i} \times
                   (\sum_{s \in \mathcal{S}} P_{S_{ii} X^{U+2}_{i} Y^{U+2}_{i}} \times
                   W)
              \end{array} \right),
              \label{eqn:ProofThm3-6-1}
\end{equation}
where $X^{U+2}_{i} \triangleq X_{[U+2] \backslash \{i\}}$ and
$Y^{U+2}_{i} \triangleq Y_{[U+2] \backslash \{i\}}$.  Applying
Pinsker's inequality \cite[p. 58]{Csiszar_Korner_81} to
(\ref{eqn:ProofThm3-6-1}), we get that,
for each $i \in [U+2]$,
\begin{equation}
             c \sqrt{2 \eta} \geq d \left(
                \begin{array}{ll}
                   P_{X^{U+2} Y^{U+2} Z}, \\
                   P_{X_i} \times P_{Y_i} \times
                   (\sum_{s \in \mathcal{S}}
                   P_{S_{ii} X^{U+2}_i Y^{U+2}_i} \times
                   W)
              \end{array} \right),
              \label{eqn:ProofThm3-6}
\end{equation}
where $c$ is an absolute constant.  By the triangle inequality, we
obtain that

\vspace{0.05in}
$\hspace{-0.15in} 2c \sqrt{2 \eta} \geq \max_{1 \leq i < j \leq U+2}$
\begin{eqnarray}
              \ \ \ d \left(\begin{array}{ll}
                   P_{X_i} \times P_{Y_i} \times
                   (\sum_{s \in \mathcal{S}} P_{S_{ii} X^{U+2}_i Y^{U+2}_{i}} \times
                   W), \\
                   P_{X_j} \times P_{Y_j} \times
                   (\sum_{s \in \mathcal{S}} P_{S_{jj} X^{U+2}_j Y^{U+2}_{j}} \times
                   W)
              \end{array} \right).
              \label{eqn:ProofThm3-7}
\end{eqnarray}
Note that $P_{X_i}=P_{({\bf x})}$ (resp. $P_{Y_i}=P_{({\bf y})}$),
$i = 1, \ldots, U+2$, with
$\min_{x \in \mathcal{X}} P_{({\bf x})}(x) > \alpha$ (resp.
$\min_{y \in \mathcal{Y}} P_{({\bf y})}(y) > \alpha$).  The sought
contradiction is obtained by invoking the following Lemma 2 upon
setting $\eta$ sufficiently small.  The proof of Lemma 2 is similar
to that of Lemma A4 of \cite{Hughes_97} and is omitted.

\vspace{0.05in} \textbf{Lemma 2:} {\em For an AVMAC $G$ with
symmetrizability $U$ and any $\alpha > 0$, there exists
$\nu(\alpha) > 0$ such that for any pair of distributions $P(x),\
x \in \mathcal{X}$, and $Q(y),\ y \in \mathcal{Y}$, satisfying
$\min_{x \in \mathcal{X}} P(x) > \alpha$, $\min_{y \in
\mathcal{Y}} Q(y) > \alpha$ and any collection of $U+2$
distributions $U_i(x^{U+1}, y^{U+1}, s),\ (x^{U+1}, y^{U+1}, s)
\in \mathcal{X}^{U+1} \times \mathcal{Y}^{U+1} \times
\mathcal{S},\ i = 1, \ldots, U+2$, it holds that

$\hspace{-0.1in} \max_{1 \leq i < j \leq U+2}$
\begin{eqnarray}
\ \ \ \ d \left (
\begin{array}{ll}
    P(x_i)Q(y_i) \\
    (\sum_{s \in \mathcal{S}} W(z|x_i, y_i, s)
    U_i(x^{U+2}_{i}, y^{U+2}_{i}, s), \\
    P(x_j)Q(y_j) \\
    (\sum_{s \in \mathcal{S}} W(z|x_j, y_j, s)
    U_j(x^{U+2}_{j}, y^{U+2}_{j}, s)
\end{array}
\right )
\geq \nu. \nonumber
\end{eqnarray}}
\vspace{0.05in}

Lastly, we consider the case in which $K$ contains a
$(U+2)$-rectangle. Precisely, there exists $I \times J \subseteq
K$ with $|I| = a+1$, $|J| = b+1$ and $(a+1)(b+1) \geq U+2$.  By
separately permuting the pair of indices of $[M] \times [M]$, we
can assume without any loss of generality that $I=[a+1],\
J=[b+1]$. Similar to the argument leading to
(\ref{eqn:ProofThm3-7}), we get

\vspace{0.05in}
$\hspace{-0.15in} 2c \sqrt{2 \eta} \geq
    \max_{(i, j), (i', j') \in [a+1] \times [b+1],\ (i, j) \neq (i', j')}$
\begin{eqnarray}
              \ \ \ d \left(\begin{array}{ll}
                   P_{X_i} \times P_{Y_j} \times
                   (\sum_{s \in \mathcal{S}} P_{S_{ij} X^{a+1}_i Y^{b+1}_j} \times
                   W), \\
                   P_{X_{i'}} \times P_{Y_{j'}} \times
                   (\sum_{s \in \mathcal{S}} P_{S_{i'j'} X^{a+1}_{i'} Y^{b+1}_{j'}} \times
                   W)
              \end{array} \right).
              \label{eqn:ProofThm3-8}
\end{eqnarray}
The sought contradiction is obtained by invoking the following
Lemma 3, whose proof is also omitted, upon setting $\eta$
sufficiently small.  This completes the proof of Lemma 1.

\vspace{0.05in} \textbf{Lemma 3:} {\em For an AVMAC $G$ with
symmetrizability $U$ and any $\alpha > 0$, there exists
$\nu(\alpha) > 0$ such that for any pair of distributions $P(x),\
x \in \mathcal{X}$, and $Q(y),\ y \in \mathcal{Y}$, satisfying
$\min_{x \in \mathcal{X}} P(x) > \alpha$, $\min_{y \in
\mathcal{Y}} Q(y) > \alpha$ and any collection of $(a+1)(b+1) \geq
U+2$ distributions $U_{ij}(x^{a}, y^{b}, s),\ (x^{a}, y^{b}, s)
\in \mathcal{X}^{a} \times \mathcal{Y}^{b} \times \mathcal{S},\ i
= 1, \ldots, a+1,\  j = 1 \ldots, b+1$, it holds that

$\hspace{-0.1in} \max_{(i,j), (i', j') \in [a+1] \times [b+1],\ (i,j) \neq (i', j')}$
\begin{eqnarray}
\ \ \ \ d \left (
\begin{array}{ll}
    P(x_i)Q(y_j)\\
    (\sum_{s \in \mathcal{S}}
    W(z|x_i, y_j, s)U_{ij}(x^{a+1}_i, y^{b+1}_j, s), \\
    P(x_{i'})Q(y_{j'})\\
    (\sum_{s \in \mathcal{S}}
    W(z|x_{i'}, y_{j'}, s)U_{i'j'}(x^{a+1}_{i'}, y^{b+1}_{j'}, s)
\end{array}
\right )
\geq \nu. \nonumber
\end{eqnarray}}
\vspace{0.05in}

We now specify in the following Lemma 4 a ``good'' deterministic
code, with nonzero rates; the proof of the lemma is similar to
that of Lemma 2 in \cite{Ahlswede-Cai_99} and is omitted.

For a deterministic code $(\mathcal{U}^{(n)}_{{\bf x}},
\mathcal{V}^{(n)}_{{\bf y}})$ with $|\mathcal{U}| = |\mathcal{V}|
= M$ and $R = \frac{1}{n}\log_2{M}$, any $\epsilon > 0$ and any
${\bf s} \in \mathcal{S}^n$, we define
\begin{eqnarray}
    \mathcal{A}_{\epsilon}({\bf s}) \triangleq
    \left \{
    \begin{array}{ll}
        (i,j) \in [M] \times [M]: \\
        D(P_{X Y S}||P_X \times P_Y \times P_S) < \epsilon\\
        \mbox{where~}P_{XYS} = P_{({\bf x}_i, {\bf y}_j, {\bf s})}
    \end{array}
    \right \}, \label{eqn:ProofThm3-9}
\end{eqnarray}
\begin{eqnarray}
    \mathcal{B}_{\epsilon}({\bf s}) \triangleq
    \left \{
    \begin{array}{ll}
        i \in [M]: \mbox{for~any~}I \subseteq [M] \backslash \{i\},\ |I| = L \\
        \mbox{~and~any~} J \subseteq [M],\ |J| = L + 1,\ \\
        I(X \wedge X_I, Y_J, S) < (2L + 1)R + \epsilon,\ \\
        \mbox{where}\ P_{X X_I Y_J S} =
        P_{({\bf x}_i, {\bf x}_I, {\bf y}_J, {\bf s})}
    \end{array}
    \right \},     \label{eqn:ProofThm3-10}
\end{eqnarray}
\begin{eqnarray}
   \mathcal{C}_{\epsilon}({\bf s}) \triangleq
    \left \{
    \begin{array}{ll}
        j \in [M]: \mbox{for~any~}J \subseteq [M] \backslash \{j\},\ |J| = L \\
        \mbox{~and~any~} I \subseteq [M],\ |I| = L + 1,\ \\
        I(Y \wedge X_I, Y_J, S) < (2L + 1)R + \epsilon,\ \\
        \mbox{where}\ P_{X_I Y Y_J S} =
        P_{({\bf x}_I, {\bf y}_j, {\bf y}_J, {\bf s})}
    \end{array}
    \right \},     \label{eqn:ProofThm3-11}
\end{eqnarray}

\vspace{0.05in} \textbf{Lemma 4:} {\em For any $0 < \epsilon <
\delta$, any sequences ${\bf x} \in \mathcal{X}^n$ and ${\bf y}
\in \mathcal{Y}^n$ with $H(P_{({\bf x})}) > \delta$ and
$H(P_{({\bf y})}) > \delta$, and all sufficiently large $n$, there
exists a deterministic code $(\mathcal{U}_{{\bf x}},
\mathcal{V}_{{\bf y}})$ as above with $R \geq \delta$ such that
for every ${\bf s} \in \mathcal{S}^n$,
\begin{equation}
    |\mathcal{A}_{\epsilon}({\bf s})| \leq 2^{-\frac{\epsilon}{4}}M^2\ \mbox{and}
    \label{eqn:ProofThm3-12}
\end{equation}
\begin{equation}
    |\mathcal{B}_{\epsilon}({\bf s})|, |\mathcal{C}_{\epsilon}({\bf s})| \leq 2^{-\frac{\epsilon}{4}}M.
    \label{eqn:ProofThm3-13}
\end{equation}}
\vspace{0.05in}

For a fixed $\alpha > 0$ and all $n$ sufficiently large, choose
${\bf x} \in \mathcal{X}^n$ and ${\bf y} \in \mathcal{Y}^n$ so
that $\min_{x \in \mathcal{X}} P_{({\bf x})}(x) > \alpha$ and
$\min_{y \in \mathcal{Y}} P_{({\bf y})}(y) > \alpha$.  We then
choose $\eta$ sufficiently small according to Lemma 1.  Next, for
the ${\bf x}$ and ${\bf y}$, and for some $\epsilon$ and $\delta$
sufficiently small so that $H(P_{({\bf x})}) > \delta$ and
$H(P_{({\bf y})}) > \delta$ and
\begin{equation}
    0 < \epsilon < \delta \leq R < \frac{\eta}{2(6L+4)},     \label{eqn:ProofThm3-14}
\end{equation}
we get from Lemma
$4$ a deterministic code $(\mathcal{U}_{{\bf x}}, \mathcal{V}_{{\bf y}})$
with some $R$ satisfying (\ref{eqn:ProofThm3-14}), (\ref{eqn:ProofThm3-12})
and (\ref{eqn:ProofThm3-13}).  Combining this code with the
decoding algorithm from Lemma 1, we obtain a
deterministic code decoded into a list of size $L$.
Lastly, we show that for every ${\bf s} \in \mathcal{S}^n$,
$\bar{e}_L({\bf s})$ approaches zero exponentially
fast.

First, we note that it suffices to prove that for all $(i, j) \in
\mathcal{A}_{\epsilon}({\bf s}) \cap [\mathcal{B}_{\epsilon}({\bf s})
\times \mathcal{C}_{\epsilon}({\bf s})],\ e_{L}(i,j, {\bf s})$
approaches zero exponentially fast, because by (\ref{eqn:ProofThm3-12})
and (\ref{eqn:ProofThm3-13}),
\begin{equation}
    \bar{e}_L({\bf s}) \leq
    \frac{1}{M^2} \sum_{(i,j) \in \mathcal{A}_{\epsilon}({\bf s}) \cap [\mathcal{B}_{\epsilon}({\bf s})
    \times \mathcal{C}_{\epsilon}({\bf s})]} e_L(i,j, {\bf s}) +
    3 \times 2^{-\frac{\epsilon}{4}n}.
\nonumber
\end{equation}
For a fixed ${\bf s}$ and $(i, j) \in \mathcal{A}_{\epsilon}({\bf s}) \cap [\mathcal{B}_{\epsilon}({\bf s})
\times \mathcal{C}_{\epsilon}({\bf s})],\ e_{L}(i,j, {\bf s})$
is the probability of the event
\begin{equation}
    \bigcap_{{\bf s}' \in \mathcal{S}^n} \left \{ E_0({\bf s}') \bigcup
    \left (\bigcup_{(a,b): \mathcal{K}_{a,b}^{L, (i,j)} \neq \emptyset } E_{a,b}({\bf s}') \right ) \right \},
    \label{eqn:ProofThm3-15}
\end{equation}
with respect to the distribution $W^n({\bf z} | {\bf x}_i, {\bf
y}_j, {\bf s})$.  $E_0({\bf s}')$ is the set of all ${\bf z} \in
\mathcal{Z}^n$ for which (\ref{eqn:ProofThm3-1}) is violated with
${\bf x}_i, {\bf y}_j, {\bf x}_{I_K \backslash \{i\}}, {\bf
y}_{J_K \backslash \{j\}}, {\bf s}', {\bf z}$ and each of the
$E_{a,b}({\bf s}')$ is the set of all ${\bf z} \in \mathcal{Z}^n$
for which (\ref{eqn:ProofThm3-2}) is violated with ${\bf x}_i,
{\bf y}_j, {\bf s}', {\bf z}$ for some $K \in
\mathcal{K}_{a,b}^{L, (i,j)}$, where $\mathcal{K}_{a,b}^{L, (i,j)}
\triangleq \{ K \subseteq [M] \times [M],\ (i, j) \in K,\ |K| =
L+1,\ |I_{K}| = a,\ |J_{K}| = b\}$. As
\begin{equation}
    E_0({\bf s}) \bigcup \left ( \bigcup_{(a,b): \mathcal{K}_{a,b}^{L, (i,j)} \neq \emptyset } E_{a,b}({\bf s}) \right)
    \label{eqn:ProofThm3-15-b}
\end{equation}
subsumes (\ref{eqn:ProofThm3-15}), it suffices to prove the
exponential decays of $W^n(E_0({\bf s}))|{\bf x}_i, {\bf y}_j,
{\bf s})$ and $W^n(E_{a, b}({\bf s}))|{\bf x}_i, {\bf y}_j, {\bf
s})$, for every ${\bf s}$, $(i, j) \in \mathcal{A}_{\epsilon}({\bf
s}) \cap [\mathcal{B}_{\epsilon}({\bf s}) \times
\mathcal{C}_{\epsilon}({\bf s})]$ and $(a, b)$ such that
$\mathcal{K}_{a,b}^{L, (i,j)} \neq \emptyset$.  These proofs
follow using the well-known techniques from the method of types
\cite{Csiszar_Korner_81}.  Specifically, the former follows
exactly as in (35) of \cite{Ahlswede-Cai_99} using
(\ref{eqn:ProofThm3-9}), the complement of (\ref{eqn:ProofThm3-1})
and (\ref{eqn:ProofThm3-14}), while the latter is a
straight-forward modification of (40) and (46) of
\cite{Ahlswede-Cai_99} using (\ref{eqn:ProofThm3-10}),
(\ref{eqn:ProofThm3-11}), the complement of
(\ref{eqn:ProofThm3-2}) and (\ref{eqn:ProofThm3-14}). The details
are omitted. $\sqr$\newpage

\section{Discussion}

At present, there is a gap between Theorem 2 and Theorem 3, i.e.,
there exists a range of list sizes for which we cannot determine
$C_L$.  This is caused by the fact that our present definition of
symmetrizability only captures the ``shapes'' of an $A$-diagonal
(\ref{sym-1}) and an $A$-rectangle (\ref{sym-2}), while the output
of a list decoder (for a fixed received sequence) can have any
``shape.'' It remains to capture the other shapes in a ``single-letter'' form.

The generalization to the case of an AVMAC with $m$-transmitters
is fairly straightforward.  In particular, Definition 1 can be
modified to take care of A-diagnals and A-rectangles in the
$m$-product space of indices.  In addition, $g_m(A)$ (as in
(\ref{eqn:ProofThm3-3})) can also be defined as the smallest
cardinality of a subset of the $m$-product space of indices which
always contains either an A-diagonal or an A-rectangle.  In
general, $g_m(A) \leq (A-1)^m + 1$. By suitably generalizing the
list decoding scheme and Lemma 4 in the proof of Theorem 3, the
latter can be generalized for an AVMAC with $m$-transmitters which
will give a lower bound $= (U+1)^m$ for the list size above which
$C_L = C^R$.

\section{Acknowledgement}
The work of S. Nitinawarat was supported by the National Science
Foundation under Grants CCF0515124, CCF0635271, CCF0830697.  The
author thanks Arya Mazumdar for his helpful comment leading to
(\ref{eqn:ProofThm3-3}).


TITLE: Simplifying pre-calc
QUESTION [0 upvotes]: I'm doing my homework and I'm stuck on this problem:
$$ \frac{\frac 1 {\sqrt{a}} + \frac {\sqrt{a}} 2}{\frac 1 {\sqrt{a}} - \frac {\sqrt{a}} 2} $$
I tried playing around with the powers, but failed pretty hard.

REPLY [2 votes]: Expand by $2\sqrt{a}$ and your'e done.


TITLE: On odd perfect numbers $q^k n^2$ and the deficient-perfect divisor $q^{\frac{k-1}{2}} n^2$ - Part II
QUESTION [2 upvotes]: (This question is an offshoot of this earlier post.)
Let $\sigma(x)$ be the sum of divisors of the positive integer $x$.  Denote the deficiency of $x$ by $D(x)=2x-\sigma(x)$, and the sum of the aliquot divisors of $x$ by $s(x)=\sigma(x)-x$.  Denote the abundancy index of $x$ by $I(x)=\sigma(x)/x$.
If $\sigma(m)=2m$ and $m$ is odd, then $m$ is called an odd perfect number.  It is currently unknown whether there are any odd perfect numbers, although it is widely believed that there is none.
Euler proved that an odd perfect number $m$, if one exists, must have the so-called Eulerian form
$$m = q^k n^2$$
where $q$ is the special/Euler prime satisfying $q \equiv k \equiv 1 \pmod 4$ and $\gcd(q,n)=1$.
Since the divisor sum function $\sigma$ is a multiplicative function and $m = q^k n^2$ is perfect, we obtain
$$2 q^k n^2 = 2m=\sigma(m)=\sigma(q^k n^2)=\sigma(q^k)\sigma(n^2)$$
which implies that
$$2 = \dfrac{\sigma(m)}{m} = \dfrac{\sigma\Bigg({q^{\dfrac{k+1}{2}}\bigg(q^{\dfrac{k-1}{2}}{n^2}\bigg)}\Bigg)}{{q^{\dfrac{k+1}{2}}\bigg(q^{\dfrac{k-1}{2}}{n^2}\bigg)}} \leq \dfrac{\sigma\Bigg({q^{\dfrac{k+1}{2}}}\Bigg)}{q^{\dfrac{k+1}{2}}}\cdot\dfrac{\sigma\Bigg({q^{\dfrac{k-1}{2}}}{n^2}\Bigg)}{q^{\dfrac{k-1}{2}}{n^2}} = I\bigg(q^{\dfrac{k+1}{2}}\bigg)I(d),$$
where
$$d = q^{\dfrac{k-1}{2}}{n^2}.$$
We now compute
$$\dfrac{d}{D(d)} = \dfrac{q^{\dfrac{k-1}{2}}{n^2}}{2q^{\dfrac{k-1}{2}}{n^2} - \dfrac{\bigg(q^{\dfrac{k+1}{2}} - 1\bigg)\sigma(n^2)}{q - 1}} = \dfrac{q^{\dfrac{k-1}{2}}{n^2}}{2q^{\dfrac{k-1}{2}}{n^2} - \dfrac{\sigma(q^k)\sigma(n^2)}{q^{\dfrac{k+1}{2}} + 1}} = \dfrac{q^{\dfrac{k-1}{2}}{n^2}}{2q^{\dfrac{k-1}{2}}{n^2} - \dfrac{2q^k n^2}{q^{\dfrac{k+1}{2}} + 1}},$$
which simplifies to
$$\dfrac{d}{D(d)} = \dfrac{q^{\dfrac{k+1}{2}} + 1}{2\Bigg(q^{\dfrac{k+1}{2}} + 1\Bigg) - 2\Bigg(q^{\dfrac{k+1}{2}}\Bigg)} = \dfrac{q^{\dfrac{k+1}{2}} + 1}{2}.$$
This confirms a theorem of Holdener and Rachfal.  (That is, the proper divisor
$$d = q^{\dfrac{k-1}{2}}{n^2}$$
of an odd perfect number
$$m = q^k n^2$$
must be deficient-perfect.)
So now we have the inequality
$$\dfrac{2}{I\bigg(q^{\dfrac{k+1}{2}}\bigg)} \leq I(d),$$
which implies that
$$\dfrac{D(d)}{d} = 2 - I(d) \leq 2 - \dfrac{2}{I\bigg(q^{\dfrac{k+1}{2}}\bigg)},$$
from which it follows that
$$\dfrac{q^{\dfrac{k+1}{2}} + 1}{2} = \dfrac{d}{D(d)} \geq \dfrac{I\bigg(q^{\dfrac{k+1}{2}}\bigg)}{2\Bigg(I\bigg(q^{\dfrac{k+1}{2}}\bigg) - 1\Bigg)}.$$
We therefore have to solve the resulting inequality
$$q^{\dfrac{k+1}{2}} + 1 \geq \dfrac{I\bigg(q^{\dfrac{k+1}{2}}\bigg)}{I\bigg(q^{\dfrac{k+1}{2}}\bigg) - 1} = \dfrac{\dfrac{q^{\dfrac{k+3}{2}} - 1}{q^{\dfrac{k+1}{2}} \bigg(q - 1\bigg)}}{\Bigg(\dfrac{q^{\dfrac{k+3}{2}} - 1}{q^{\dfrac{k+1}{2}} \bigg(q - 1\bigg)}\Bigg) - 1}$$
which implies that
$$\Bigg(q^{\dfrac{k+1}{2}} + 1\Bigg)\cdot\Bigg(q^{\dfrac{k+1}{2}} - 1\Bigg) \geq q^{\dfrac{k+3}{2}} - 1$$
from which it follows that
$$q^{k+1} - 1 \geq q^{\dfrac{k+3}{2}} - 1 \implies q^{k+1} \geq q^{\dfrac{k+3}{2}} \implies q^{2k+2} \geq q^{k+3} \implies 2k+2 \geq k+3 \implies k \geq 1.$$
INQUIRY

Is it possible to improve on the approach/attack as outlined in this post to hopefully produce a nontrivial lower bound for $k$?

REPLY [1 votes]: Too long to comment :
You used an inequality
$$\sigma\Bigg({q^{\dfrac{k+1}{2}}\bigg(q^{\dfrac{k-1}{2}}{n^2}\bigg)}\Bigg)\le \sigma\Bigg({q^{\dfrac{k+1}{2}}}\Bigg)\sigma\Bigg({q^{\dfrac{k-1}{2}}}{n^2}\Bigg)$$
This inequality is true, but we can have
$$\sigma\Bigg({q^{\dfrac{k+1}{2}}\bigg(q^{\dfrac{k-1}{2}}{n^2}\bigg)}\Bigg)$$
$$=\sigma\Bigg({q^{\dfrac{k+1}{2}}}\Bigg)\sigma\Bigg({q^{\dfrac{k-1}{2}}}{n^2}\Bigg)-\frac{q\Bigg(q^{\dfrac{k-1}{2}}-1\Bigg)\Bigg(q^{\dfrac{k+1}{2}}-1\Bigg)}{(q-1)^2}\sigma(n^2)$$
since we have
$$\begin{align}&\sigma\Bigg({q^{\dfrac{k+1}{2}}}\Bigg)\sigma\Bigg({q^{\dfrac{k-1}{2}}}{n^2}\Bigg)-\sigma\Bigg({q^{\dfrac{k+1}{2}}\bigg(q^{\dfrac{k-1}{2}}{n^2}\bigg)}\Bigg)
\\\\&=\sigma\Bigg({q^{\dfrac{k+1}{2}}}\Bigg)\sigma\Bigg({q^{\dfrac{k-1}{2}}}\Bigg)\sigma({n^2})-\sigma(q^k)\sigma(n^2)
\\\\&=\Bigg(\frac{q^{\dfrac{k+3}{2}}-1}{q-1}\cdot\frac{q^{\dfrac{k+1}{2}}-1}{q-1}-\frac{q^{k+1}-1}{q-1}\Bigg)\sigma(n^2)
\\\\&=\frac{\Bigg(q^{\dfrac{k+3}{2}}-1\Bigg)\Bigg(q^{\dfrac{k+1}{2}}-1\Bigg)-(q^{k+1}-1)(q-1)}{(q-1)^2}\sigma(n^2)
\\\\&=\frac{q\Bigg(q^{\dfrac{k-1}{2}}-1\Bigg)\Bigg(q^{\dfrac{k+1}{2}}-1\Bigg)}{(q-1)^2}\sigma(n^2)\end{align}$$


TITLE: Why doesn't the Meissner effect follow from zero resistance?
QUESTION [4 upvotes]: In articles on superconductivity (see, for example, the original BCS paper or Leggett's review article), the Meissner effect is treated as a seperate phenomena that must be explained in addition to the fact that the material has zero resistance. In Leggett's article, he especially mentions that the two phenomena are independent, and one may arise without the other. But thinking about it, it seems to me that any material that has zero resistance must expel magnetic fields. What's wrong with the following argument?
Say you have a ring with zero resistance. The ring has some inductance, L, and you want to thread some flux $\Phi_{ext}$ through the ring.

At any time, the total flux through the ring will be given by
$$
\Phi_{total}(t)=\Phi_{ext}(t)+LI(t)
$$
If you start with zero current and zero external flux and increase the external flux over time, the EMF around the loop is given by
$$
\mathcal{E}(t)=-\frac{d\Phi_{total}}{dt}=-\frac{d\Phi_{ext}}{dt}-L\frac{dI}{dt}
$$
Since the ring has zero resistance, the EMF at any time must be zero, so
$$
0=-\frac{d\Phi_{ext}}{dt}-L\frac{dI}{dt}
$$
$$
\frac{d\Phi_{ext}}{dt}=-L\frac{dI}{dt}
$$
or, integrating both sides from $t=0$,
$$
\Phi_{ext}(t)=-LI(t)
$$
so that $\Phi_{total}(t)=0$ at all times, and we've completely expelled the external magnetic field.
Where does this argument break down?

REPLY [5 votes]: Your argument assumes the flux in the medium begins at zero, and concludes that it will remain zero, which is true.  However, consider a medium that begins with nonzero resistance, has magnetic flux introduced, and then is cooled to the point of superconductivity.  In that case, the classical theory you're using just says that whatever magnetic field is in the material when it becomes superconducting will remain there, "frozen" in place as it were.  Zero resistance implies constant field (no diffusion), not necessarily zero field.  In the Meissner effect, by contrast, any field present in the material up to the transition is actually forcefully ejected when the material becomes superconducting.  Something causes the field to diffuse out of the medium very fast during the transition.  (The converse is also true: by making the magnetic pressure on a superconductor big enough, you can force magnetic field into it, but in doing so you destroy its superconductivity.)  (+! @knzhou!)


TITLE: Why the Equality Axioms are considered as logical axioms?
QUESTION [1 upvotes]: This question is from Introduction to Mathematical Logic by Elliot Mendelson , page 94-95 , First order theories with equality.There is a line which is kind of confusing for me.

The numbering (A6) and (A7) is a continuation of the numbering of the logical axioms.

Here , (A6) and (A7) are the following axioms:
$(A6)$ $(\forall x_1)x_1=x_1$
$(A7)$ $x=y \to (\mathscr B(x,x) \to \mathscr B(x,y))$
My question is , why they are considered logical axioms ? Shouldn't they be in the category of proper (or non-logical) axioms?

REPLY [2 votes]: What is your criterion of what counts as a "logical constant"? The connectives and first-order quantifiers count as logical notions -- but why?
There are various stories on the market for demarcating the logical constants.  Depending on the details, some count the identity predicate as a logical constant, some don't. For an accessible discussion of some of the options here, see e.g. https://plato.stanford.edu/entries/logical-constants/
But certainly, some standard accounts do treat the notion of identity as logical: it is topic neutral and general enough; it is governed by introduction and elimination rules in the right sort of way, and so on. Mendelson is not at all going out on a limb in treating the identity laws as logical.


TITLE: Is $S^3/S^2$ homeomorphic to $S^1$?
QUESTION [0 upvotes]: If we define a relation in $\mathbb R^3$
such that, $x$~$y$ iff $x = \alpha y$ with $\alpha >0$, the the quotient space $\mathbb R^3/\mathbb R^+$ is homeomorphic to $S^2$.
My question is
Let $S^3=\{(x, y, z, w) :x^2+y^2+z^2+w^2=1\}$ and  $S^2=\{(x, y, z) : x^2+y^2+z^2=1\}$ then what is the quotient space $S^3/S^2$?

REPLY [2 votes]: I want to try to answer your question in the title.
Because $(S^3,S^2)$ is a 2-connected CW-pair and $S^2$ is 1-connected. By Excision Theorem, we would have an isomorphism
$$\pi_i(X,A)\to\pi_i(X/A), \ i\leq (2+1)=3$$
Then if we write the long exact sequence of the pair $(S^3,S^2)$, we get
$$\cdots\to\pi_1(S^3)=0\to\pi_1(S^3,S^2)\cong\pi_1(S^3/S^2)\to\pi_0(S^2)=0\to\pi_0(S^3)=0\to\cdots$$
This tells us that $$\pi_1(S^3,S^2)\cong\pi_1(S^3/S^2)=0\neq\pi_1(S^1)\cong\mathbb{Z}$$
Hence $S^3/S^2$ is not homotopy equivalent to $S^1$. It cannot be homeomorphic to $S^1$ either.