TITLE: Minimal collection of subsets to reconstruct singletons
QUESTION [6 upvotes]: I have come across the following problem in a technical application. For a given integer $n$, what is the minimal collection of subsets of $\{1,\dots,n\}$ such that all "singleton" sets $\{1\}, \{2\}, \dots, \{n\}$ can be "reconstructed" by set operations (intersection, union, set difference, complement) on those subsets?
For example, with $n = 5$ a possible collection is $S_1 = \{1,2,3\}, S_2 = \{2,3,4\}, S_3 = \{3,4,5\}$, because we can write
$$ \{1\} = S_1 \setminus S_2 \\
\{2\} = S_2 \setminus S_3 \\
\{3\} = S_1 \cap S_2 \cap S_3 \\
\{4\} = S_2 \setminus S_1 \\
\{5\} = S_3 \setminus S_2$$
In believe that in general, the sets $S_k = \{k,k+1,\dots,k+c-1\}$, $1\le k \le n-c+1$ and $c = \lceil n / 2 \rceil $ are sufficient, but I am not convinced they are minimal.
I am sure this problem has been studied in some context but I am not a professional mathematician and I don't even know where to look ... Any help appreciated!

REPLY [1 votes]: It turns out you can get by with only $\lceil \lg n\rceil$ sets, where $\lg$ as usual denotes logarithm base $2$.  I'll give a construction and prove that it is optimal.
Note that you can construct all singletons with set operations if and only if you can construct all subsets of $[n]=\{1,\ldots,n\}$; it can be useful to think of the latter as an equivalent goal.
For each $i\ge 0$, let $S_i$ be the subset of $[n-1]$ whose binary expansions contain a $1$ in the $i$-th position.  (We don't need to include $n$ in any of our sets; it's unnecessary, since the union of the $S_i$'s is $[n-1]$, so we can get the singleton $\{n\}$ by complementing.)  So $S_i$ is nonempty precisely when $n-1\ge 2^i$, i.e. $i<\lg n$.  Thus the nonempty $S_i$'s are indexed from $0,\ldots \lceil \lg n\rceil-1$.
It's easy to see how to get any singleton $\{k\}$ from the $S_i$'s: look at the binary expansion of $k$; if the $i$-th bit of $k$ is $1$ then $k\in S_i$, otherwise $k\in \bar{S_i}$.  Intersecting the appropriate sets for each $i$ leaves the singleton $k$.
The fact that this construction is optimal follows immediately from the fact that the free Boolean algebra generated by $m$ elements contains $2^{2^m}$ elements.
In a little more detail: the collection of all subsets of a given set forms a so-called Boolean algebra, under the correspondence $\wedge\leftrightarrow\cup$, $\vee\leftrightarrow\cap$, and $\neg\leftrightarrow\textrm{complement}$. Roughly, the free Boolean algebra $FA(m)$ on $m$ generators is the "largest" Boolean algebra that can be generated from the generators; the elements of $FA(m)$ are all of the non-equivalent Boolean expressions which can be formed from the given $m$ elements.  It is a standard result that $|FA(m)|=2^{2^m}$.  Any Boolean algebra $\mathcal{A}$ which can be generated by $m$ elements is a quotient of $FA(m)$, so in particular $\mathcal{A}$ can't have any more than $2^{2^m}$ elements.
To sum up, if $m$ subsets of $[n]$ can generate all subsets via set operations, then we must have $2^{2^m}\ge 2^n$, i.e. $m\ge \lceil\lg n\rceil$. The given construction achieves this bound.
You can turn this into a nice card trick.  Have someone think of a card, deal the deck into two piles, ask them which pile the card is in, pick up the cards and repeat 5 more times.  Then you can guess their card.  The point is that, at the $i$-th stage, the two piles correspond to the sets $S_i$ and $\bar{S_i}$.


TITLE: $n^{\text{th}}$ term of The Maclaurin Expansion of $\dfrac{1}{(1-x)^3(1+x)(1+x+x^2)}$?
QUESTION [2 upvotes]: I am trying to find the coefficient of $n^{\text{th}}$ term of the Maclaurin series of $$\dfrac{1}{(1-x)^3(1+x)(1+x+x^2)}.$$
How can I find the coefficient of $n^{\text{th}}$ term of this function?

REPLY [1 votes]: As noted by @Daniel, it equals $1/(1-x)(1-x^2)(1-x^3)$.  Another way to put that is $$\frac{(1+x+...+x^5)(1+x^2+x^4)(1+x^3)}{(1-x^6)^3}$$


TITLE: Prove that the interval $ \ [0,2)$ and $ \ [5,6) \cup [7,8)$ have the same cardinality
QUESTION [2 upvotes]: Question:
Prove that the interval $[0,2)$ and $[5,6) \cup [7,8)$ have the same cardinality by constructing a bijection between the two sets. You can add a graph to support your argument.
I tried graphing a function with domain $[0,2)$  and target space $[5,6) \cup [7,8)$ but I can't come up with an explicit formula. Will the function be linear?

REPLY [2 votes]: To map the interval $[0;2)$ to the union of two disjoint intervals $[5;6)\cup[7;8)$ you will clearly need a piecewise function.   To be bijective, this function must have an inverse.
$$\newcommand{\hide}[1]{\underline{\phantom{#1}}}\begin{align*} f(x) =\begin{cases} \hide{x+5} & :& x\in [\hide{0;1}) \\[1ex] \hide{x+6} &:& x\in[\hide{1;2}) \\[1ex] \text{undefined} &:& \text{elsewhere}\end{cases} \\[2ex] f^{-1}(y) =\begin{cases} \hide{y-1} & :& y\in [5;6) \\[1ex] \hide{y-6} &:& y\in[7;8) \\[1ex] \text{undefined} &:& \text{elsewhere}\end{cases}\end{align*}$$
Can you find such a function and show $\forall x{\in}[0;2):\Big(\big(f(x){\in}[0;5){\cup}[6;7)\big)\wedge\big( f^{-1}\circ f(x)=x\big)\Big)$.


text:
\begin{document}

\title[Lattice on Caratheodory Extension]{Construction of A Lattice on the completion space of an algebra and an isomorphism to its Caratheodory Extension}

\author{Jun Tanaka}
\address{University of California, Riverside, USA}
\email{juntanaka@math.ucr.edu, yonigeninnin@gmail.com, junextension@hotmail.com}

\author{Peter F. Mcloughlin}
\address{Crafton Hills College, USA}
\email{pmcloughlin@aol.com}

\keywords{Caratheodory Extension Theorem, Lattice Theory, Measure Theory}
\subjclass[2000]{Primary: 28A12, 28B20}
\date{August, 10, 2008}

\begin{abstract}
In this paper, we will show how one is able to construct a lattice on the completion of an algebra and to obtain an isomorphism to its Caratheodory Extension. In addition, it will be shown that the lattice form a $ \sigma$-algebra and a complete Heyting algebra of countable type.
\end{abstract}

\maketitle

\section{\textbf{Introduction}}
The Caratheodory Extension Theorem is a crucial part of any advanced
Real Analysis course; the process extends an algebra to a $
\sigma$-algebra and a measure on an algebra to a measure on a $
\sigma $-algebra. This is a powerful tool in both measure theory and
statistics (see for example, \cite{fleming},\cite{stochastic}). A Boolean Algebra structure on the Caratheodory Extension was discussed in several papers (e.g. Kolmogorov, \cite{Boolean1}, Coquand and Palmgren \cite{Boolean2}). Furthermore, the Caratheodory Extension is complete with a pseudometric $ d ( . , .) = \mu^{\ast} (. \triangle . ) $ where $\mu^{\ast} ( . ) $ is the outer measure on the power set P(X) (Please refer to \cite{Dun}). The Caratheodory Extension has various rich structures which are open to further investigation.

In this paper, we will show how the Caratheodory Extension process
is intimately related to the metric completion process. In
particular, it will be shown how one is able to construct a lattice on the completion of an algebra and to obtain an isomorphism
to its Caratheodory Extension. The author believes this method to be new, intuitive, and constructive. Especially noteworthy is that, in Definition \ref{d:9} of this paper, we give a precise definition of $\vee^{\infty}$ on the completion space $ ( \bar{d}, \overline{\Omega}$) of an algebra $\Omega$ and show that the lattice is a complete Heyting algebra of countable type.

Let X be an arbitrary nonempty set, and let $ \mu$ be a finite measure on an algebra $ \Omega \subset \mathbf{P}(X)$.
Note that $ d ( . , .) = \mu^{\ast} (. \triangle . ) $ defines a pseudometric on
$ \Omega$. Denote by $(\bar{d} , \overline{\Omega})$ the completion
of $ (d, \Omega)$. Also, let $S$ be the set of all Cauchy sequences
in $(d, {\Omega})$. By the metric completion procedures, we know $
\bar{d} ( \{ \overline{B^{\alpha_{1}}_n} \}, \{
\overline{B^{\alpha_{2}}_n} \}) = \lim d  ( {B^{\alpha_{1}}_n} ,
{B^{\alpha_{2}}_n}) $ where $ \{  {B^{\alpha_{i}}_n} \} $ is in $S$
with $ \{ \overline{B^{\alpha_{i}}_n} \} = \{ \{B_n \}  \in S : \lim
d (B_n, B_n ^{\alpha_{i}} ) = 0 \} $ for $ i  = 1 $or 2.

\begin{definition}\label{d:1}
Let $ \bar{\mu} ( \{ \overline{B^{\alpha}_{n}} \})  = \bar{d} ( \{
\overline{B^{\alpha}_{n}} \} , \{ \bar{\phi} \} ) = \lim \mu (
{B^{\alpha}_{n}}  )$.
\end{definition}

\begin{definition}\label{d:2}
If $ B _n \in \Omega$, then $ \{ B_n \} $ is called a $ \mu$-Cauchy
sequence if $\mu (B_n \triangle B_m ) \rightarrow 0 $ as n,m $\rightarrow \infty$.

\end{definition}

\begin{definition}\label{d:3}
For A, B in $\mathbf{P}(X) $, A = B a.e. if $\mu^{\ast} ( A  \triangle B )  =0. $

\end{definition}

In Section \ref{Se:Completion}, we will show that a lattice structure can be naturally defined on $
\overline{\Omega} $ which makes it a $ \sigma$-algebra. Let $ \widetilde{\mathbf{S}}$ = $\{S \in \mathbf{P}(X) \ |$ $ \exists \ \mu$-Cauchy sequence  $\{B_{n}   \}   $ s.t. $ \lim \mu^{\ast} ( B_{n}   \triangle S)  =0   \}$. In \cite{Junext}, we proved that $ \widetilde{\mathbf{S}}$ is a $\sigma$-algebra where, for any $\mu$-Cauchy sequence $ \{ B_{n} \}$ such that $ \lim \mu^{\ast} ( B_{n}   \triangle S)  =0 $, the measure $\widetilde{\mu} (S) $ on $ \widetilde{\mathbf{S}}$ is defined as $\widetilde{\mu} (S) $ = $\lim \mu ( B_{n}   )   $. In addition, we proved that $  \widetilde{\mu}$ is a countably additive measure on $ \widetilde{\mathbf{S}}$. Thus, ($\widetilde{\mu}$, $ \widetilde{\mathbf{S}}$) is a measure space. We showed that the Caratheodory Extension of $\Omega$ can be expressed as the set of limit points of $\mu$-Cauchy sequences under the pseudometric $d(A,B)$ = $\mu^{\ast}(A \triangle B)$. Moreover, when the measure is a $\sigma$-finite measure, we obtained an equivalent expression of the Caratheodory Extension, $ \widetilde{\mathbf{S}}$ = $\{S \in \mathbf{P}(X) $ $ | $  $\exists \ \mu$-Cauchy sequence  $\{B_{n}   \}   $ s.t. $ \lim \mu^{\ast} ( B_{n}   \triangle S)  =0   \}$. Theorem 2 in \cite{Junext} shows that $E$ is a measurable set iff  $E$ is in $ \widetilde{\mathbf{S}}$. Thus, the measure space ($\widetilde{\mu}$, $ \widetilde{\mathbf{S}}$) agrees with the Caratheodory Extension when $\mu$ is a finite measure. Moreover, it shows that measurable sets are exactly limit points of $\mu$-Cauchy sequences. The $\sigma$-finite case follows from the finite case. In Section \ref{Se:Iso}, we will define a $\sigma$-algebra lattice isomorphism between two $\sigma$-algebras, and define a map $F :$ $\overline{\Omega}   \rightarrow \mathbf{P}(X) $ given by $F ( \overline{\{B_{n}\}} )  = B $ where $ \lim \mu^{\ast} ( B_{n}   \triangle B  )  =0   $. We will show that $F$ is an isometry and a $\sigma$-algebra lattice isomorphism between the completion $\overline{\Omega}$ and the Caratheodory Extension of $\Omega$ under the equivalence relation $\sim$ defined as A $\sim$ B iff $\mu^{\ast}(A \triangle B)$ =0.

\section{\textbf{Main Definitions and Notations}}

Our notation agrees with that in \cite{Junext}. For emphasis, let X be a nonempty set. Throughout the paper, unless otherwise stated, $ \mu$ will be a finite measure on an algebra $ \Omega \subset \mathbf{P}(X)$. Unless otherwise stated, $\{ B^\alpha_n\}$ will be a $ \mu$-Cauchy
sequence.

In addition, for each $ \mu$-Cauchy
sequence $\{ B_n\}$, a capital letter corresponds to the limit point of the $ \mu$-Cauchy
sequence. For instance,
$ \lim \mu^{\ast} ( A_{n}   \triangle A  )  =0   $, $ \lim \mu^{\ast} ( B_{n}   \triangle B  )  =0   $, $ \lim \mu^{\ast} ( Y_{L}   \triangle Y  )  =0   $. There exist such limit points in $\mathbf{P}(X)$ since the Caratheodory Extension is complete under the pseudometric d $($\cite{Dun}$)$.

We recall that by a $\sigma$-algebra of subsets of X, we mean a family $\Omega$ of subsets such that (1) every countable union of sets in $\Omega$ is in $\Omega$, and (2) $A^C$ is in $\Omega$ whenever A is.

\begin{definition}\label{d:5}
Define a map $F :$ $\overline{\Omega}   \rightarrow \mathbf{P}(X) $ given by $F ( \overline{\{B_{n}\}} )  = B $

where $ \lim \mu^{\ast} ( B_{n}   \triangle B  )  =0   $. Note that such a B always exists in $\mathbf{P}(X)$ since the Caratheodory Extension is complete $($\cite{Dun}$)$.

\end{definition}

\begin{definition}\label{d:6}{\textbf{$\sigma$-algebra lattice isomorphism}}

Suppose lattices $($X, $\vee_X$,$\wedge_X$ $)$ and $($Y, $\vee_Y$,$\wedge_Y$ $)$ are $\sigma$-algebras, and H: X $\rightarrow  $ Y is a one-to-one, onto well-defined map. Then H is called a $\sigma$-algebra lattice isomorphism if
\[
\begin{aligned}
H(\cdot  \vee_X \cdot ) = & H(\cdot ) \vee_Y  H(\cdot )  , \  \  \ \  \ \  \  H(\vee^{\infty}_{X } \ \cdot ) & = &  \vee^{\infty}_{Y}   H(\cdot )  ,  \\
H(\cdot  \wedge_X \cdot ) = & H(\cdot ) \wedge_Y H(\cdot )  ,\ \ \  \ \ \ \ H(\cdot^{\textbf{C}} ) & = & H(\cdot )^{\textbf{C}} .
\end{aligned}
\]

\end{definition}

We will show that F is a $\sigma$-algebra lattice isomorphism between $\overline{\Omega}$ and $ \widetilde{\mathbf{S}}_{\diagup_{\sim} }$ where $\sim$ is an equivalence relation in the sense of Definition \ref{d:3}.

\section{\textbf{Preliminaries}}

In this section, we shall briefly review the well-known facts about lattice theory (e.g. Birkhoff \cite{Birk}, Iwamura \cite{Iwamura}), propose an extension lattice, and investigate its properties, as well as some lemmas from \cite{Junext}. A nonempty set L is called a lattice if L is closed under the operations of meet ($\wedge  $) and join ($\vee  $). It is denoted by (L,$\wedge  $,$\vee  $) or simply L. If it satisfies, in addition, the distributive law, then it is called a distributive lattice. For two lattices L and $L'$, a bijection from L to $L'$, which preserves lattice operations is called a lattice isomorphism, or simply an isomorphism. If there is an isomorphism from L to $L'$, then L is called lattice-isomorphic with $L'$, and we write L $\cong$ $L'$. We write x $\leq $ y if x $\wedge$ y = x or, equivalently, if x $\vee$ y = y. L is called complete if, for any subset A of L, L contains the supremum $\vee $A and the infimum $\wedge$A, with respect to the above order. A complete lattice L includes the maximum and minimum elements, which are denoted by I and O, or 1 and 0, respectively. A distributive lattice is called a Boolean algebra or a Boolean lattice, if, for any element x in L, there exists a unique complement $x^C \in L$ such that x $\vee$ $x^C$ = 1 and $x \wedge x^C$ = 0.
Let L be a lattice and $\cdot^{c}$: L $\rightarrow $ L be an operator. Then $\cdot^{c}$ is called a lattice complement in L if the following conditions are satisfied:

(1) $\forall x$ $\in$ L, $x^C \wedge x$ = 0, $x^C \vee x$ = I,

(2) $\forall$ x, y $\in$ L, x $\leq$ y $\Rightarrow$ $x^C \geq y^C$,

(3) $\forall$ x $\in$ L, $(x^C)^C$ = x.

\begin{definition}

A complete lattice L is called a lattice $\sigma$-algebra or simply a $\sigma$-algebra if the following conditions are satisfied:

(1) $\forall$ A $\in$ L, $A^C \in $L where $ \cdot^C$ is a lattice complement,

(2) $\forall$ $A_i \in$ L, $\vee^{\infty} A_i \in$ L.

\end{definition}

\begin{definition}\label{cha:1}

A complete lattice is called a complete Heyting algebra $($cHa$)$, if
\[
\begin{aligned}
\vee_{i \in I} \ ( x_{i} \wedge y ) =  (\vee_{i \in I} \  x_{i} ) \wedge y
\end{aligned}
\]
holds for $\forall x_{i} , y \in L$ $(i \in I)$; where I is an index set of arbitrary cardinal number. In the case that the cardinality of I is countable, it is called a complete Heyting Algebra of countable type.
\end{definition}

It is well-known that for a set E, $| P(E) |$= $2^{|E|}$. The set of all subsets of E is a Boolean algebra.

\begin{lemma}\label{le:1}
If $ \{B_n\} $ is a $ \mu$-Cauchy sequence, then $ \{ \mu (B_n) \} $
is a Cauchy sequence of real numbers.
\end{lemma}

\begin{proof}
Note $ B_n \subseteq (B_n \triangle B_m) \cup B_m $ and $ B_m
\subseteq (B_n \triangle B_m) \cup B_n $ implies $ \mu(B_n) \leq \mu
(B_n \triangle B_m) + \mu (B_m) $ and $ \mu (B_m ) \leq \mu (B_n
\triangle B_m) + \mu (B_n) $. Hence, $| \mu (B_n) - \mu (B_m ) |\leq
\mu (B_n \triangle B_m )$.
\end{proof}

\begin{lemma}\label{le:2}
$ d(A _1 \cup A_2, A_3 \cup A_4 ) \leq d (A_1, A_3) + d (A_2 , A_4 )
$ for any $ A _i \in \Omega $.
\end{lemma}

\begin{proof}
The proof is in \cite{Junext}
\end{proof}

\begin{lemma}\label{le:3}
$\{B^\alpha _n \cup B^\gamma _n \} $ and $ \{ ( B ^\alpha _n )^C \}
$ are $ \mu$-Cauchy sequences.
\end{lemma}

\begin{proof} By Lemma $\ref{le:2}$,
\[d(B^\alpha _ n \cup B^\gamma _n , B ^\alpha _m \cup B^\gamma _m ) \leq d (B^\alpha _n, B^\alpha _m ) + d (B ^\gamma _n, B^\gamma _m ).
\]
\[
\begin{aligned}
& \mbox{Moreover}, \, \,  d ((B^\alpha _n )^C , (B^\alpha _m )^C ) = \mu ( (B^\alpha _n )^C \triangle (B^\alpha _m )^C ) =  \mu (B^\alpha _n  \Delta B^\alpha _m ) = d (B^\alpha _n ,
B^\alpha _m ).\\  & \mbox{Hence, the claim follows}.
\end{aligned}
\]
\end{proof}

\section{\textbf{The Completion Space $ ( \bar{d}, \overline{\Omega}$) and the Lattice (L,$\wedge  $,$\vee  $)} }\label{Se:Completion}

In this section, we introduce the completion of ($d$,$\Omega$) where $\Omega$ is an algebra of subsets of X.

\begin{definition}\label{d:7}
Let $E_\alpha = \{ \overline{ B^\alpha_n}\} $ and $E_A = \overline{ \{
A \} } $ when $ A \in \Omega $ and $\{  B^\alpha_n \} $ is a sequence in $\Omega$.
\end{definition}

\begin{definition}\label{d:8}
Define $ E_\alpha \vee E_\gamma = \{ \overline{B^\alpha _n \cup B
^\gamma _n } \} $, $ E_\alpha \wedge E_\gamma = \{ \overline{B^\alpha _n \cap B
^\gamma _n } \} $, and $ E^C _\alpha  = \{ \overline{(B^\alpha _n )
^C }\} $.
\end{definition}

\begin{remark}\label{n:1}
$ E _\alpha \wedge E_\gamma = E _\phi $ iff $ \bar{\mu} (E_\alpha
\wedge E_\gamma) = 0 $ iff $ \lim \mu (B^\alpha _n \cap B ^\gamma
_n ) = 0 $. Moreover, $ E_\alpha \subset E_\gamma $ iff $ \bar{\mu}
( E _\alpha \wedge E ^C_\gamma ) = 0 $. The containment may be written in the usual lattice sense; namely, $ E_\alpha \wedge E_\gamma = E_\alpha$.
\end{remark}

\begin{lemma}\label{le:4}
The map $ \vee : \overline{\Omega} \times \overline{\Omega} \rightarrow
\overline{\Omega} $ defined by $ \vee (E_\alpha \times E_\gamma ) =
E_\alpha \vee E_\gamma = \{ \overline{B^\alpha _n \cup B^\gamma
_n} \}   $ is well-defined.
\end{lemma}

\begin{proof} Suppose $\{ \overline{B^\alpha _n} \} = \{ \overline{A^\alpha _n} \} $ and $ \{ \overline{A^\gamma _n} \} = \{ \overline{B^\gamma _n} \}$.

Then $ \lim d (B^\alpha _n, A ^\alpha _n) = \lim d (B^\gamma _n,
A^\gamma _n)=0 $. Also, by Lemma 3, $ \{B^\alpha _n \cup
B^\gamma _n \} $ and $ \{ A^\alpha _n \cup A^\gamma _n\} $ are $
\mu$-Cauchy sequences.

Hence, by Lemma $\ref{le:2}$, $ d (B^\alpha _n \cup B^\gamma _n, A^\alpha
_n\cup A^\gamma _n) \leq d(B^\alpha _n , A^\alpha _n) + d( B^\gamma
_n, A^\gamma _n) $ and the claim follows.
\end{proof}

\begin{lemma}\label{le:5} The map $ \cdot {}^C : \overline{\Omega} \rightarrow \overline{\Omega}  $ defined by \[ (\{ \overline{B^\alpha _n} \}) ^C = \overline{ \{ ( B^\alpha _n)^C \} } \]
is well-defined.
\end{lemma}

\begin{proof}
Suppose $ \{ \overline{B^\alpha _n} \} = \{ \overline{A^\alpha _n}
\}$. Then $ \lim d (B ^\alpha _n , A ^\alpha _n ) = 0$. Now, $d ((
B^\alpha _n)^C, (A^\alpha _n)^C )= \mu (( B^\alpha _n )^C \triangle
(A^\alpha _n)^C )= \mu (B^\alpha _n \triangle A^\alpha _n) = d (
B^\alpha _n , A^\alpha _n ) $ which implies $ \{ ( B^\alpha _n )^C
\} \sim \{(A^\alpha _n)^C\}$.
\end{proof}

\begin{lemma}\label{le:4}
The map $ \wedge : \overline{\Omega} \times \overline{\Omega} \rightarrow
\overline{\Omega} $ defined by $ \wedge (E_\alpha \times E_\gamma ) =
E_\alpha \wedge E_\gamma = \{ \overline{B^\alpha _n \cap B^\gamma
_n} \}   $ is well-defined.
\end{lemma}

\begin{proof}
The proof follows immediately from the two previous lemmas.
\end{proof}

\begin{lemma}
$ \cdot {}^C $ in Lemma \ref{le:5} is a lattice complement.
\end{lemma}

\begin{proof}
The proof is obvious.
\end{proof}

\begin{lemma}\label{le:6} $ \bar{\mu} (E_\alpha \vee E_\gamma ) \leq \bar{\mu} (E _{\alpha} ) + \bar{\mu} (E_\gamma) $ for $ E_\alpha , E _\gamma \in \overline{\Omega} $.
\end{lemma}

\begin{proof}
$E_\alpha = \{ \overline{B^\alpha _n} \} $ and $ E_\gamma = \{
\overline{B^\gamma _n} \} $ implies  $E_\alpha \vee E_\gamma = \{
\overline{B^\alpha _n \cup B^\gamma _n} \} $. Hence $ \bar{\mu} ( E
_\alpha \vee E _\gamma )= \lim \mu ( B^\alpha _n \cup B^\gamma _n
)  \leq \lim [ \mu (B^\alpha _n) + \mu (B^\gamma _n)] = \lim \mu
(B^\alpha _n) + \lim \mu ( B^\gamma _n) \leq \bar{\mu}(E_\alpha ) +
\bar{\mu} (E _\gamma)$.
\end{proof}

\begin{lemma}\label{le:7}
If $ E _{\alpha_{1}} $ and $ E _{\alpha_{2}}$ are disjoint, then $
\bar{\mu} (E _{\alpha_{1}} \vee E _{\alpha_{2}} ) = \bar{\mu} (E
_{\alpha_{1}} ) + \bar{\mu} (E _{\alpha_{2}} )$.
\end{lemma}

\begin{proof}
 By Remark $\ref{n:1}$, we must have $ \lim \mu ( B ^{\alpha_{1}} _n \cap B ^{\alpha_{2}} _n)=0$. Note, $B ^{\alpha_{i}} _n = (B ^{\alpha_{i}} _n \cap B ^{\alpha_{j}} _n) \ \cup \ ( B ^{\alpha_{i}} _n \cap (B ^{\alpha_{j}} _n) ^C )$ implies $ \mu (B ^{\alpha_{i}} _n) = \mu ( B ^{\alpha_{i}} _n  \cap B ^{\alpha_{j}} _n )+ \mu (B ^{\alpha_{i}} _n \cap (B ^{\alpha_{j}} _n)^C )$ and $\lim \mu (B ^{\alpha_{i}} _n ) = \lim \mu (B ^{\alpha_{i}} _n \cap (B ^{\alpha_{j}} _n )^C )$ for $ \{i , j \} = \{1, 2\} $.

Moreover,  $ \mu ( B ^{\alpha_{1}} _n   \cup B ^{\alpha_{2}} _n  ) =
\mu ( \ ( B ^{\alpha_{1}} _n \cap B ^{\alpha_{2}} _n ) \ \cup \ (B ^{\alpha_{1}} _n  \cap ( B ^{\alpha_{2}} _n  )^C ) \ \cup \ (B ^{\alpha_{2}} _n   \cap (B ^{\alpha_{1}} _n
 )^C ) \ ) = \mu (B ^{\alpha_{1}} _n
 \cap B ^{\alpha_{2}} _n
)+ \mu (B ^{\alpha_{1}} _n
 \cap (B ^{\alpha_{2}} _n
 )^C )+ \mu (B ^{\alpha_{2}} _n  \cap (B ^{\alpha_{1}} _n
)^C) $ implies $ \bar{\mu} (E _{\alpha_{1}} \vee E _{\alpha_{2}})
= \lim \mu
 (B ^{\alpha_{1}}_n  \cup B ^{\alpha_{2}}_n)= \lim \mu (B ^{\alpha_{1}}_n)+ \lim \mu (B ^{\alpha_{2}}_n)= \bar{\mu} ( E_{\alpha_{1}} ) + \bar{\mu} (E_{\alpha_{2}}) $.
\end{proof}

\begin{theorem}\label{le:8}
$ \overline{\Omega} $ is an algebra and $ \bar{\mu} $ is a measure
on $ \overline{\Omega} $.
\end{theorem}

\begin{proof} By Lemmas $\ref{le:3}$, $\ref{le:4}$  and $\ref{le:5}$,  $ \overline{\Omega}$ is an algebra. Moreover,  the fact that $\bar{\mu}$ takes on values in $\mathbb{R} ^+ $ along with Lemmas 6 and 7 imply $ \bar{\mu} $ is a measure on  $\overline{\Omega} $.
\end{proof}

\begin{remark}\label{n:2}  $ \bar{d} ( E_{\alpha},  E _\gamma ) = \lim d (B ^{\alpha}_n  ,   B ^{\gamma}_n ) = \lim [ \mu (B ^{\alpha}_n  \cap (B ^{\gamma}_n )^C )+ \mu (B ^{\gamma}_n \cap (B ^{\alpha}_n )^C)] = \lim \mu (B ^{\alpha}_n  \cap (B ^{\gamma}_n )^C)+\lim \mu (B ^{\gamma}_n  \cap (B ^{\alpha}_n )^C) = \bar{\mu} ( E_{\alpha} \wedge (E_{\gamma})^C)+ \bar{\mu} ( E_{\gamma} \wedge (E_{\alpha}) ^C) = \bar{\mu} (E_{\alpha} \triangle E_{\gamma}) $.
\end{remark}

\begin{lemma}\label{le:1}

Let $E_{i}$ =  $\overline{\{B^{i}_{n}\}}$  $\in \overline{\Omega}$ for i $\geq$ 1 and by following the proof of Lemma 8 in \cite{Junext}, construct $Y_{L} $ =  $\cup_{i=1}^{N_{L}} B^{i}_{K_{L}}$ for each $L$ such that

\[
\mu^{\ast}(\cup_{i=1}^{\infty}   S_{i}  \triangle  \cup_{i=1}^{N_{L}} B^{i}_{K_{L}}     ) \leq  \mu^{\ast}(\cup_{i=N_{L}+1}^{\infty}   S_{i}) + \mu^{\ast}(\cup_{i=1}^{N_{L}}   S_{i}  \triangle  \cup_{i=1}^{N_{L}} B^{i}_{K_{L}}     ) < \frac{1}{L}.
\]

Then
E := $\overline{\{ Y_{L}   \}}  $ satisfies the following conditions;

\[
\begin{aligned}
1. & \vee ^n _{i=1} E _{i}  \leq E \ \ \mbox{for all} \  n, \\
2. &\lim \bar{\mu} (E \wedge ( \vee ^n_{i=1} E _{i}
)^C ) = 0   .
\end{aligned}
\]

In particular, E is uniquely determined in $\overline{\Omega}$.

\end{lemma}

\begin{proof}
Note that $E_{i}$ =  $\overline{\{B^{i}_{n}\}}$ = $\overline{\{B^{i}_{K_{L}}\}}$.

$( \vee_{i=1}^{n}   E_{i}  ) \wedge \overline{\{ Y_{L}   \}} $  =  $ \overline{\{  \cup_{i=1}^{n} B^{i}_{K_{L}}   \cap  Y_{L}         \}}   $ = $ \overline{\{  \cup_{i=1}^{n} B^{i}_{K_{L}}     \}}   $ = $\vee_{i=1}^{n}   E_{i}   $ for any n.

Let $N_{L} > n$.
\[
\begin{aligned}
\mu( \cup_{i=1}^{N_{L}} B^{i}_{K_{L}}  \cap  (\cup_{i=1}^{n} B^{i}_{K_{L}})^{\textbf{C}}   ) = & \mu( \cup_{i=1}^{N_{L}} B^{i}_{K_{L}}  \triangle  \cup_{i=1}^{n} B^{i}_{K_{L}}     )  = \mu^{\ast}( \cup_{i=1}^{N_{L}} B^{i}_{K_{L}}  \triangle  \cup_{i=1}^{n} B^{i}_{K_{L}}     ) \\  \leq & \mu^{\ast}(\cup_{i=1}^{\infty}   S_{i}  \triangle  \cup_{i=1}^{N_{L}} B^{i}_{K_{L}}     ) + \mu^{\ast}(\cup_{i=1}^{\infty}   S_{i}  \triangle  \cup_{i=1}^{n} B^{i}_{K_{L}}     ).
\end{aligned}
\]

This implies that $\lim  \overline{\mu}( \overline{\{ Y_{L}   \}}  \wedge ( \vee_{i=1}^{n}     E_{i}) ^{\textbf{C}}  )   $ = 0.

Suppose $E, E^\prime \in \overline{\Omega} $ both satisfy condition 1 and 2 above. Then $  \vee ^n _{i=1} E _{i}  \leq E \wedge E^\prime \leq E$ for all n. Hence, we must have $ E = E \wedge E ^\prime $. Similarly, we must have $ E^\prime = E \wedge E^\prime $. Therefore E is unique.

\end{proof}

\begin{lemma}\label{le:14}
Let $E_{i}$ =  $\overline{\{B^{i}_{n}\}}$  $\in \overline{\Omega}$ for i $\geq$ 1 and $ E_{i} \wedge E_{j}  = E_\phi $ for $ i
\neq j$. Then $ \bar{\mu} (E) = \sum ^\infty _{i=1} \bar{\mu}
(E_{i}) $ where E is defined as in Lemma \ref{le:1}.

\end{lemma}

\begin{proof}
Suppose that $E_{i}$ =  $\overline{\{B^{i}_{n}\}}$  $\in \overline{\Omega}$ for i $\geq$ 1 and $ E_{i} \wedge E_{j}  = E_\phi $ for $ i \neq j$. Then it follows that $ \bar{\mu} (\vee ^n _{i=1} E _{i}) = \sum^k_{i=1} \bar{\mu} ( E_{i} ) \leq \bar{\mu} (E) $ for all $k$.

Hence, we must have
\begin{equation}\label{Eq:1}
\sum^\infty_{i=1} \bar{\mu} ( E_{i } ) \leq
\bar{\mu} (E).
\end{equation}

Now since  $ \bar{\mu} (E) = \bar{\mu}
(\vee ^n _{i=1} E _{i}) + \bar{\mu} (E \wedge (\vee ^n _{i=1} E _{i} )^C )$  for all n and $\lim \bar{\mu} (E \wedge ( \vee ^n_{i=1} E _{i}
)^C ) = 0  $ ,  we must have $ \bar{\mu}
(E) = \sum^\infty _{i=1} \bar{\mu} ( E_{i} ) $ by (\ref{Eq:1}).

\end{proof}

\begin{definition} \label{d:9} For $ {E}_{i}$ in $ \overline{\Omega} $, we define $ \vee ^\infty _{i=1} {E}_{i} = E $ where $E$ is as in Lemma $\ref{le:1}$.
\end{definition}

\begin{theorem}\label{le:10}
$ ( \bar{\mu} , \overline{\Omega} )$ is a measure space.
\end{theorem}

\begin{proof}
This follows by Theorem $\ref{le:8}$, $\ref{le:1}$, and $\ref{le:14}$, and Definition $\ref{d:9}$.
\end{proof}

\section{\textbf{The Isomorphism} }\label{Se:Iso}

In this section, we introduce an isomorphism $F :$ $\overline{\Omega}   \rightarrow \mathbf{P}(X) $ given by $F ( \overline{\{B_{n}\}} )  = B $.

\begin{lemma}

$F$ : $\overline{\Omega}   \rightarrow  \widetilde{\mathbf{S}}_{\diagup_{\sim} } $ is a well-defined map.
\end{lemma}

\begin{proof}
Suppose that $\overline{\{A_{n}\}} =  \overline{\{B_{n}\}}$.

There exist A and B in $\mathbf{P}(X)$ such that $ \lim \mu^{\ast} ( A_{n}   \triangle A  )  =0   $  and  $ \lim \mu^{\ast} ( B_{n}   \triangle B  )  =0   $.

$ \mu^{\ast} (  A  \triangle B  )  \leq  $ $ \mu^{\ast} (  A  \triangle  A_{n}  )  +   \mu^{\ast} (   A_{n}  \triangle B_{n}  ) +   \mu^{\ast} (  B_{n}  \triangle B )  $ by the triangle inequality.

By taking limits on both sides, $ \mu^{\ast} (  A  \triangle B  ) = 0$.

Thus, A = B a.e.. Therefore, F is well-defined.

\end{proof}

\begin{theorem}\label{t:3}
F is an isometry between $\overline{\Omega}$ and $ \widetilde{\mathbf{S}}_{\diagup_{\sim} }$.
\end{theorem}

\begin{proof}
First, we show F is onto $ \widetilde{\mathbf{S}}$. Let $X \in \widetilde{\mathbf{S}}$. Then there exists a $\mu$-Cauchy sequence  $\{B_{n}   \}   $ such that $ \lim \mu^{\ast} ( B_{n}   \triangle X)  =0   $. Thus $F ( \overline{\{B_{n}\}} )    = X $ a.e.. Therefore, F is onto.

Second, we will show F preserves the metric. Let $\overline{\{A_{n}\}}$, $ \overline{\{B_{n}\}}$ $\in $  $\overline{\Omega}$. Letting A and B be as before, we have
\[
  \lim \mu (   A_{n}  \triangle B_{n}  )  =    \mu^{\ast} (  A  \triangle B  )   .
\]
Therefore, $\overline{d}( \overline{\{A_{n}\}}, \overline{\{B_{n}\}} ) $ = $\lim \mu (   A_{n}  \triangle B_{n}  ) $ = $\mu^{\ast} (  A  \triangle B  )     $

=  $\mu^{\ast} (  F ( \overline{\{A_{n}\}} )   \triangle   F ( \overline{\{B_{n}\}} )  )     $ = $d(  F ( \overline{\{A_{n}\}} )  ,   F ( \overline{\{B_{n}\}} )     ) $. Thus, F preserves the metric.

Lastly, we will show that F is one-to-one. Let $  F ( \overline{\{A_{n}\}} )  ,   F ( \overline{\{B_{n}\}} )    \in \widetilde{\mathbf{S}}$ such that $  F ( \overline{\{A_{n}\}} )  =  F ( \overline{\{B_{n}\}} ) $ a.e..

Then $ A  =  B   $ a.e. implies $\mu^{\ast} (  A  \triangle B  ) = 0$. Then, as in the proof of F being onto,  $\lim \mu (   A_{n}  \triangle B_{n}  ) $ = $\mu^{\ast} (  A  \triangle B )     $. Thus $\overline{\{A_{n}\}}$ = $\overline{\{B_{n}\}}$ and F is one-to-one. Therefore, F is an isometry between $\overline{\Omega}$ and $ \widetilde{\mathbf{S}}_{\diagup_{\sim} }$.

\end{proof}

\begin{theorem}\label{t:4}
F is a $\sigma$-algebra lattice isomorphism between $\overline{\Omega}$ and $ \widetilde{\mathbf{S}}_{\diagup_{\sim} }$.
\end{theorem}

\begin{proof}
We already showed that F is a one-to-one, onto map in Theorem $\ref{t:3}$.

$F ( \overline{\{A_{n}\}}  \vee  \overline{\{B_{n}\}} )$ = $F ( \overline{\{A_{n} \cup B_{n}\}} )$ = $F ( \overline{\{A_{n}\}} )  \cup F(  \overline{\{B_{n}\}} )$ a.e. since $\lim \mu (   A_{n} \cup B_{n} \ \ \triangle \ \ A \cup B  ) $ = 0.

Let $\overline{\{B_{n}\}} \in \overline{\Omega}$.

Then,
\[
F ( \overline{\{B_{n}\}}^{\textbf{C}} )  =    F ( \overline{\{  ( B_{n})^{\textbf{C}}   \}} )   =   B^{\textbf{C}} \ \ a.e..
\]
Thus, $F(\cdot^{\textbf{C}} )$ =  $F(\cdot )^{\textbf{C}} $ in $ \widetilde{\mathbf{S}}_{\diagup_{\sim} }$.

Similarly, $F(\cdot  \wedge \cdot )$ = $F(\cdot^{\textbf{C}} \vee \cdot^{\textbf{C}} )^{\textbf{C}} $ =  $[ F(\cdot^{\textbf{C}} ) \cup  F(\cdot^{\textbf{C}} ) ]^{\textbf{C}} $= $F(\cdot ) \cap F(\cdot )  $.

Let $E_{\alpha_{i}}$ $\in \overline{\Omega}$ for i $\geq$ 1 and $E_{\alpha_{i}}$ = $\overline{\{B^{\alpha_{i}}_{n}\}}$.

Then for each i, there exists an $S_{i}   \in   \widetilde{\mathbf{S}}  $ such that $ \lim \mu^{\ast} (B^{\alpha_{i}}_{n} \triangle S_{i})  =0  $.

Now suppose we have $\{ Y_{L} \}$ in the same manner as in Lemma $\ref{le:1}$. By design, $\{ Y_{L} \}$ converges to $\cup_{i=1}^{\infty}   S_{i} $. Then $\overline{ \{ Y_{L} \}  }$ = $\vee_{i=1}^{\infty}   E_{\alpha_{i}}  $ by Lemma $\ref{le:1}$. Now we have

\[
F( \vee_{i=1}^{\infty}   E_{\alpha_{i}}  )  = F(\vee_{i=1}^{\infty}   \overline{\{B^{\alpha_{i}}_{n}\}}  )  = F ( \overline{ \{ Y_{L} \}  } ) = Y  .
\]
Since $\lim \mu^{\ast} ( Y_{L} \triangle Y  )  =0  $ and $\lim \mu^{\ast} ( Y_{L} \triangle \cup^{\infty}_{i=1} S_{i}  )  =0  $, we have $Y   $ = $\cup^{\infty}_{i=1} S_{i}  $ a.e.. In addition, $\cup^{\infty}_{i=1} S_{i}  $ = $\cup^{\infty}_{i=1} F(  \overline{\{B^{\alpha_{i}}_{n}\}}  )  $.

Thus,
\[
F( \vee_{i=1}^{\infty}   E_{\alpha_{i}}  )  = \cup^{\infty}_{i=1} F( E_{\alpha_{i}} )  .
\]
Therefore, the claim follows.

\end{proof}

\begin{theorem}\label{t:countable}
$( \overline{\Omega}$,$\wedge  $,$\vee  )$ is a complete Heyting algebra of countable type. More precisely, it is the case that the cardinality of I in Definition $\ref{cha:1}$ is countable.
\end{theorem}

\begin{proof}
Since  $ \widetilde{\mathbf{S}}$ is a complete Heyting algebra of countable type, the proof follows from Theorem $\ref{t:4}$.
\end{proof}

\section{\textbf{Conclusion}}
Theorems $\ref{t:3}$ and  $\ref{t:4}$ show that the completion of $\Omega$ is isometric and $\sigma$-algebra lattice isomorphic to $ \widetilde{\mathbf{S}}_{\diagup_{\sim} }$. Thus, by the conclusion in \cite{Junext} the completion of $\Omega$ is isometric to, as well as $\sigma$-algebra isomorphic to, the Caratheodory Extension under the equivalence relation $\sim$ . An important note is that the isomorphism shows that Caratheodory Extension Theorem and the Metric Completion Process are essentially the same, differing only on measure zero sets. In addition, the completion $\overline{\Omega}$ of $\Omega $ is a complete Heyting algebra of countable type by Theorem \ref{t:countable}. The $\sigma$-finite case follows from the finite case.

\section{\textbf{Acknowledgement}}
The first author would like to thank Professors who gave him very professional advice and suggestions, which he truly believes improved the presentation of this paper.

config: arxiv


TITLE: Why can't impulse be instantaneous?
QUESTION [4 upvotes]: We know from 2nd law of motion that $$\vec{F} = \frac{d\vec{p}}{dt}.$$
Now, a rate of change can be instantaneous. So, rate of change of momentum is instantaneous. But I doubt how can there be change of momentum at an instant?
But when it comes to impulse, it always acts for a certain time, however small (infinitesimal) it might be. If rate of change of momentum is instantaneous and force is instantaneous, why can't the impulse be instantaneous? What is the cause?
Can anyone also tell how can there be change of momentum at an instant?

REPLY [5 votes]: Consider a superball falling toward a hard tile floor. The ball will bounce rather nicely. How to model this collision?
If you look very closely at the bounce, a normal force from the floor starts acting on the ball when the bottom of the ball hits the floor. At this point in time, the top of the ball doesn't "know" that the bottom of the ball has hit the floor. That information propagates upward as a finite velocity pressure wave in the ball. The top of the ball keeps falling downward for a while. The ball gets compressed, rebounds, and flies back upwards. Some energy is lost as the ball is compressed and then relaxes back to its round shape.
One way to model this is to ignore all those details of the bounce. Since the duration is so very short, the bounce can be modeled as an instantaneous change in momentum determined by the ball's coefficient of restitution. This is a simplification that intentionally ignore the details of the bounce. While the maximum force is very high compared to the weight of the ball, the force is never infinite, and the change in momentum is not instantaneous.
The same applies to any application where one models forces as impulsive. It's just a model, a simplification that lets one ignore the details. The force is never truly infinite, so the change in momentum is never truly instantaneous.

REPLY [3 votes]: but I doubt how can there be change of momentum at an instant?

It isn't clear to me what you mean here.  Do you mean you doubt that momentum can be discontinuous?
If so, then your doubt is justified.  Classically, momentum cannot actually be discontinuous at some time $t_0$ since that would imply an actually infinite force acting at $t_0$.
If you're trying to say something else, please clarify your question.

But when it comes to impulse, it always acts for a certain time,

It isn't clear to me what you're thinking here.  An impulse does not act for a certain time, a force acts for a certain time.
When we integrate the force (with respect to time) over that certain time, the result is the impulse of the force acting for that time - impulse has time 'built in'.
So, for example, if a force acts over some time $\Delta t$ and we integrate the force over that time, the result is the time average of that force multiplied by $\Delta t$ and this is called the impulse produced by the force:
$$\mathbf J = \mathbf F_{avg}\Delta t $$

Can anyone also tell how can there be change of momentum at an
  instant?

If you mean a finite (rather than infinitesimal) change at an instant, this requires an actually infinite force which isn't physical.  However, mathematically, we can abstractly describe such a force with a Dirac delta distribution which can be useful.  For example, take a look at Green's functions.


TITLE: rectangle size vs window size
QUESTION [0 upvotes]: I always want the large dimension of a rectangle to fill 75% of the small dimension of a window. The rectangle can be any size and the window can be any size. How do I do this?

REPLY [0 votes]: Let $W$ be a window with real dimensions $W_s, W_l : W_s \leq W_l$.
Let $R$ be a rectangle with real dimensions $R_s, R_l : R_s \leq R_l$.
Then you require it so that $R_l = .75(W_s)$.
We are done.


TITLE: Period notation in group theory
QUESTION [2 upvotes]: In the context of finite fields, quotient groups, and characteristics, what does
$$n.1=0$$
mean, i.e., what is the period notation?

REPLY [1 votes]: $n \cdot 1$ most probably means $1 + 1 + \cdots + 1$, with $n$ terms.
Both $1$ and $+$ are to be interpreted in the given field.


TITLE: What does it mean by 'monotone' when referring to functions?
QUESTION [2 upvotes]: To clarify, I know what it means when a function is surjective, injective, bijective, and what its inverse is. This is something my module notes covers.
However, I have a question (past exam paper) asking to show that a function is monotone. I have no clue what it means, and there is not a single mention of it in the module notes (provided by the professor, and I don't have access to a recommended textbook either).
Please could someone explain what monotone means?

REPLY [3 votes]: A real valued function $f$ of a real variable is monotonically increasing if
$$
f(a) \ge f(b) \text{ when } a > b.
$$
"Monotone" might be monotonically increasing or monotonically decreasing. Sometimes you want the inequality to exclude equality. Then you use the adjective "strictly".


text:
\begin{document}

\title{A New Class of Multiple-rate Codes Based on Block Markov Superposition Transmission}

\author{Chulong~Liang,
        Jingnan~Hu,
        and~Xiao~Ma,~\IEEEmembership{Member,~IEEE,}
        and~Baoming~Bai,~\IEEEmembership{Member,~IEEE}

\thanks{This work was supported by the 973 Program (No.2012CB316100) and the NSF (No.61172082) of China.}
\thanks{Chulong~Liang, Jingnan~Hu and Xiao~Ma are with the Department of Electronics and Communication Engineering, Sun Yat-sen University, Guangzhou 510006, China (e-mail: lchul@mail2.sysu.edu.cn, hujingn@mail2.sysu.edu.cn, maxiao@mail.sysu.edu.cn).}
\thanks{Baoming~Bai is with State Lab. of ISN, Xidian University, Xi'an 710071, Shaanxi, China (e-mail: bmbai@mail.xidian.edu.cn).}}

\maketitle

\begin{abstract}

Hadamard transform~(HT) as over the binary field provides a natural way to implement multiple-rate codes~(referred to as {\em HT-coset codes}), where the code length $N=2^p$ is fixed but the code dimension $K$ can be varied from $1$ to $N-1$ by adjusting the set of frozen bits. The HT-coset codes, including Reed-Muller~(RM) codes and polar codes as typical examples, can share a pair of encoder and decoder with implementation complexity of order $O(N \log N)$. However, to guarantee that all codes with designated rates perform well, HT-coset coding usually requires a sufficiently large code length, which in turn causes difficulties in the determination of which bits are better for being frozen. In this paper, we propose to transmit short HT-coset codes in the so-called block Markov superposition transmission~(BMST) manner.
At the transmitter, signals are spatially coupled via superposition, resulting in long codes. At the receiver, these coupled signals are recovered by a sliding-window iterative soft successive cancellation decoding algorithm.
Most importantly, the performance around or below the bit-error-rate~(BER) of $10^{-5}$ can be predicted by a simple genie-aided lower bound. Both these bounds and simulation results show that the BMST of short HT-coset codes performs well~(within one dB away from the corresponding Shannon limits) in a wide range of code rates.
\end{abstract}
\begin{IEEEkeywords}

Fast Hadamard transform~(HT), iterative soft successive cancellation, multiple-rate codes, short polar codes, spatial coupling.
\end{IEEEkeywords}

\section{Introduction}

In practical communication systems, it is frequently required to implement several codes with different code rates. This is critical for wireless communication systems to implement the adaptive coded modulation~\cite{tse2005}, which can lower down the outage probability of a single code and hence allows more efficient use of the scarce bandwidth resources~\cite{Alamouti94}. {It is then desirable to implement codes with all different rates of interest with a pair of encoder and decoder~\cite{Sun07}}. Rate-compatible~(RC) codes are a class of multiple-rate codes, which are usually constructed from a mother code by the use of code modifying techniques such as shortening information bits and extending or puncturing parity-check bits~\cite{Hagenauer88, acikel1999, yazdani2004, ha2004rate, zhang2012}, as summarized in~\cite{Casado2009}.

The rate-compatible codes usually have different code lengths for different code rates. For some applications, the code lengths can be varied in a wide range. For example, Raptor codes~(with length as long as required) were optimized by designing the degree profiles to maximize the average throughput~\cite{Uppal11}.
In 2009, Casado~{\em et al} proposed multiple-rate codes with fixed code length by combining rows of the parity-check matrix of a mother code. In 2012, Liu~{\em et al} constructed multiple-rate nonbinary low-density parity-check~(LDPC) codes with fixed block length by using higher order Galois fields for codes of lower rates~\cite{liu2012}. Although fixed-length multiple-rate codes are not applicable to hybrid automatic repeat request~(HARQ) with incremental redundancies, they may find applications in some other scenarios.
{\color{black}
\begin{itemize}
  \item Fixed-length multiple-rate codes can be applied to the scenarios where a framing constraint is imposed on the physical layer. This occurs, for example, when orthogonal frequency division modulation~(OFDM) with a fixed number of subcarriers is used~\cite{Huang08}. In this scenario, fewer information bits should be encoded to maintain the reliability requirement when the channel is in a low signal-to-noise ratio~(SNR) level.
  \item Fixed-length multiple-rate codes may also find applications in flash memory systems, where the channel capacity decreases with ages but the number of memory cells keeps unchanged~\cite{Huang2013}.
      The older flash memory, which has undergone a large number of erase cycles, has a degraded capacity and requires a code of lower rate; while the ``younger" flash memory has a larger capacity and supports a code of higher rate. In this scenario, fixed-length multiple-rate codes with the same pair of encoder and decoder are preferred.

\end{itemize}

Block Markov superposition transmission~(BMST) is a construction of big convolutional codes from short codes~(referred to as \emph{basic codes})~\cite{Ma13,Ma13x}, which has a good performance over the binary-input additive white Gaussian noise channel~(BI-AWGNC).
{\color{black}In~\cite{Ma13x}, it has been pointed out that any short code with fast encoding algorithm and soft-in soft-out~(SISO) decoding algorithm can be chosen as the basic code.}
A sliding-window decoding~(SWD) algorithm with a tunable decoding delay, as similar to the pipeline message-passing decoding algorithm of the LDPC convolutional codes~\cite{Felstrom99,Ueng12}, can be implemented to decode the BMST system.
Most importantly, the performance of the SWD algorithm in the low error rate region can be predicted by a simple genie-aided lower bound.

}

{\color{black}In this paper, the BMST is used to construct a new class of multiple-rate codes with fixed code length.}
First, we propose to construct short multiple-rate codes by adjusting the set of frozen bits in Hadamard transform~(HT), resulting in {\em HT-coset codes}. This family of codes, which have length $N=2^p$ for some $p>0$ and dimension $K$ ranging from $1$ to $N-1$, can be implemented by the use of a pair of encoder and decoder with complexity of order $O(N \log N)$. Such a pair of encoder and decoder were first demonstrated using normal graph for Reed-Muller~(RM) codes by Forney in~\cite{Forney2001}. The HT-coset codes considered in this paper are also closely related to the polar codes~\cite{Arikan2009}, however, channel polarization plays a less important role here because the considered codes will be very short~(typically $N \leq 16$). Then, to improve the performance of the short HT-coset codes, we propose to transmit short HT-coset codes in the BMST manner~\cite{Ma13,Ma13x}.
The resulting system, referred to as a BMST-HT system for convenience, takes as the basic code a Cartesian product of short HT-coset codes and hence has encoding/decoding complexity linearly growing with the transmission block length. {\color{black}In addition, the unified structure of the HT-coset codes can significantly simplify the hardware implementation.} Simulation results show that the BMST-HT systems perform well~(within one dB away from the corresponding Shannon limits) in a wide range of code rates.

{\color{black}The rest of this paper is organized as follows. In Section~\ref{sec:HTcosetCode}, we present the encoding and decoding algorithm for the multiple-rate HT-coset codes. In Section~\ref{sec:BMST-HT}, we construct BMST-HT systems with a general design procedure and present the encoding and decoding algorithm for the multiple-rate BMST-HT systems.

Section~\ref{sec:result} concludes this paper.}

\section{Short Multiple-rate Codes}~\label{sec:HTcosetCode}
\subsection{Fast Hadamard Transform~(FHT)}

We consider the Hadamard transform~(HT) defined over the binary field.

Let $N = 2^p$ for some positive integer $p$. Any non-negative integer $j < N$ has a binary expansion $j \triangleq \left(j_{p-1} j_{p-2} \cdots j_1 j_0 \right)_2$ in the sense that $j = \sum_{0 \leq s \leq p-1}j_s 2^s$ and $j_s \in \left\{ 0, 1 \right\}$. We call $\left(j, j' \right) \left( j < j' \right)$ an {\em s-complementary pair} if and only if their binary expansions differ only in the $s$-th bit.
For example, $(0, 1)$ is a 0-complementary pair, $(4, 6)$ is a 1-complementary pair and $(3, 7)$ is a 2-complementary pair.
A Hadamard matrix of order $N$ over the binary field $\mathbb{F}_2 = \left\{ 0, 1 \right\}$ can be defined recursively as~\cite{Forney2001}
\begin{equation}
\mathbfit{H}_N = \left[
    \begin{array}{cc}
    \mathbfit{H}_{N/2} & \mathbfit{H}_{N/2} \\
    \mathbf{0}         & \mathbfit{H}_{N/2}
    \end{array}
    \right]
\end{equation}
for $p > 1$ with $\mathbfit{H}_2 = \left[
\begin{array}{cc}
1 & 1 \\
0 & 1
\end{array}
\right]$. Notice that $\mathbfit{H}_2$ is the transpose of $\mathbfit{F}_2$ in~\cite{Arikan2009}.
Let $\mathbfit{u}_{0} = \left( u_{0,0}, u_{0,1}, \cdots, u_{0,N-1} \right) \in \mathbb{F}_2^N$ be a binary vector.

The Hadamard transform of $\mathbfit{u}_{0}$ is defined as $\mathbfit{u}_{p} = \mathbfit{u}_{0}\mathbfit{H}_{N}$, which can be computed recursively in $p$ stages, see Fig.~\ref{HadaGraph} for reference.
\begin{algorithm}{The Fast Hadamard Transform}\label{alg:FHT}

\begin{itemize}
  \item At stage $s = 0, 1, \cdots, p-1$, compute $\mathbfit{u}_{s+1} \triangleq \mathbfit{u}_{s}\mathbfit{T}_{s}$, where $\mathbfit{T}_{s}$ is a linear transform, whose basic operation is the transform defined by $\mathbfit{H}_{2}$ as
\begin{eqnarray*}
    u_{s+1,j}  &=& u_{s,j}, \\
    u_{s+1,j'} &=& u_{s,j} + u_{s,j'}
\end{eqnarray*}
for each $s$-complementary pair $\left( j, j' \right)$, see Fig.~\ref{HadaGraph}(b) for reference.
\end{itemize}
\end{algorithm}

\begin{figure}[t]
\centering
\includegraphics[width=0.5\textwidth]{HadamardT.eps}
\caption{Fast Hadamard transform. (a)~A general framework with $N=2^p$. (b)~The basic building block of the Hadamard transform at the $s$-stage, where $(j, j')$ is an $s$-complementary pair, meaning that their binary expansions differ only in the $s$-th bit.}
\label{HadaGraph}
\end{figure}

We use $\mathbfit{U}_{0}$ and $\mathbfit{U}_{p}$ to denote a {\em random} vector and its Hadamard transform, respectively. That is, $\mathbfit{U}_p = \mathbfit{U}_0 \mathbfit{H}_N$, or equivalently\footnote{This can be verified by checking that $\mathbfit{H}_N^2 = \mathbfit{I}_N$, the identity matrix of order $N$.}, $\mathbfit{U}_0 = \mathbfit{U}_p \mathbfit{H}_N$.
In this paper, a message associated with a discrete random variable is represented by its probability mass function. Suppose that, for each $j$, $0 \leq j \leq N-1$, the {\em a priori} messages of $U_{0,j}$ and $U_{p,j}$ are available, which are denoted as $P^{a}_{{U}_{0,j}} \left( u \right), u \in \mathbb{F}_2$ and $P^{a}_{{U}_{p,j}} \left( u \right), u \in \mathbb{F}_2$, respectively. We further assume that all $U_{0,j}$~(resp. $U_{p,j}$) are independent. Then we have
\begin{equation}\label{eq:ProbU0}
P_{ \mathbfit{U}_{0} } \left( \mathbfit{u}_{0} \right) \triangleq \Pr \left\{ \mathbfit{U}_{0} = \mathbfit{u}_{0} \right\} = \prod\limits_{0 \leq j \leq N-1} P^{a}_{{U}_{0,j}} \left( u_{0,j} \right)
\end{equation}
and
\begin{equation}\label{eq:ProbUp}
P_{ \mathbfit{U}_{p} } \left( \mathbfit{u}_{p} \right) \triangleq \Pr \left\{ \mathbfit{U}_{p} = \mathbfit{u}_{p} \right\} = \prod\limits_{0 \leq j \leq N-1} P^{a}_{{U}_{p,j}} \left( u_{p,j} \right)
\end{equation}

{\color{black}For any given component~(say $U_{0,j}$) of interest in $\mathbfit{U}$ and $\mathbfit{V}$, the {\em extrinsic message}~(denoted by, say, $P^{e}_{{U}_{0,j}} \left( u \right), u \in \mathbb{F}_2$)} is defined as a probability mass function that is proportional to the likelihood function, i.e.,
\begin{equation}
P^{e}_{{U}_{0,\!j}} \!\left(\! u \!\right) \!\propto\! \sum\limits_{\!\mathbfit{u}_0:u_{0,\!j}\!=\!u\!} P_{ \mathbfit{U}_{p} } \left(\! \mathbfit{u}_0 \mathbfit{H}_{N} \!\right) \!\prod_{\!0 \!\leq\! k \!\leq N\!-\!1\!, k \!\neq\! j} \!P^{a}_{U_{0, k}}(\! u_{0,\!k} \!), u \in \mathbb{F}_2
\end{equation}
and
\begin{equation}
P^{e}_{{U}_{p,\!j}} \!\left(\! u \!\right) \!\propto\! \sum\limits_{\!\mathbfit{u}_p:u_{p,\!j}\!=\!u\!} P_{ \mathbfit{U}_{0} } \left(\! \mathbfit{u}_p \mathbfit{H}_{N} \!\right) \!\prod_{\!0 \!\leq\! k \!\leq N\!-\!1\!, k \!\neq\! j\!} \!P^{a}_{U_{p,\!k}}(\! u_{p,\!k} \!), u \in \mathbb{F}_2.
\end{equation}
Note that the extrinsic message associated with a random variable is irrelevant to the associated {\em a priori} message.
{\color{black}The complexity to compute all {\em exact} extrinsic messages using the above equations is of order $O(N 2^N)$, which, however, can be reduced if approximate extrinsic messages are tolerable.} This can be attained by performing an iterative message passing/processing algorithm over the normal graph as shown in
Fig.~\ref{HadaGraph}(a).

The normal graph has $p$ super nodes, corresponding to $p$ stages, respectively, where the node $\mathbfit{T}_s$ imposes a constraint that $\mathbfit{U}_{s+1} = \mathbfit{U}_s \mathbfit{T}_s$.
Recalling that the basic building block to implement the transformation $\mathbfit{T}_s$ is the transform defined by $\mathbfit{H}_2$, we have the following algorithm, which falls into the general framework given by Forney~\cite{Forney2001}.

\begin{algorithm}{The Forward-backward SISO Algorithm}\label{alg:SISO_FHT_DEC}
\begin{itemize}
  \item {\bf Initialization:}~Assume that $P^{a}_{U_{0,j}}(u),u \in \mathbb{F}_2$ and $P^{a}_{U_{p,j}}(u),u \in \mathbb{F}_2(0 \leq j \leq N-1)$ are available. All intermediate variables are initialized to have a uniform distribution over $\mathbb{F}_2$.

  \item {\bf Iteration:}~Perform iteratively the following steps $J$ times for a preset integer $J>0$.

  {\em Backward recursion:}
   For $s = p-1, p-2, \cdots, 0$, for each $s$-complementary pair $(j,j')$, compute
   \begin{eqnarray*}
   P^{e}_{{U}_{s, j}} \left(\! u \!\right) \!&\propto& \!\sum\limits_{u' \in \mathbb{F}_2 } P^{a}_{ {U}_{s,j'} } \left(\! u' \!\right) P^{a}_{ {U}_{s+1,j} } \left(\! u \!\right) P^{a}_{U_{s+1,j'}} \left(\! u\!+\!u' \!\right), \\

   P^{e}_{ {U}_{s,j'} } \left(\! u' \!\right) \!&\propto&\! \sum\limits_{u \in \mathbb{F}_2 } P^{a}_{ {U}_{s,j} } \left(\! u \!\right) P^{a}_{ {U}_{s+1,j} } \left(\! u \!\right) P^{a}_{ {U}_{s+1,j'} } \left(\! u\!+\!u' \!\right)
  \end{eqnarray*}
   and
   update $P^{a}_{{U}_{s, j}}\left( u \right) = P^{e}_{{U}_{s, j}}\left( u \right)$ and $P^{a}_{{U}_{s, j'}}\left( u' \right) = P^{e}_{{U}_{s, j'}}\left( u' \right)$ for $u, u' \in \mathbb{F}_2$.

  {\em Forward recursion:}
  For $s = 0, 1, \cdots, p-1$, for each $s$-complementary pair $(j,j')$, compute
  \begin{eqnarray*}
   P^{e}_{{U}_{s+1,j}} \left(\! u \!\right) \!&\propto&\! \sum\limits_{u' \in \mathbb{F}_2 } P^{a}_{ {U}_{s+1,j'} } \left(\! u' \!\right) P^{a}_{ {U}_{s,j} } \left(\! u \!\right) P^{a}_{U_{s,j'}} \left(\! u\!+\!u' \!\right), \\

   P^{e}_{ {U}_{s+1,j'} } \left(\! u' \!\right) \!&\propto&\! \sum\limits_{u \in \mathbb{F}_2 } P^{a}_{ {U}_{s+1,j} } \left(\! u \!\right) P^{a}_{ {U}_{s,j} } \left(\! u \!\right) P^{a}_{ {U}_{s,j'} } \left(\! u\!+\!u' \!\right)
  \end{eqnarray*}
  and update $P^{a}_{{U}_{s+1, j}}\left( u \right) = P^{e}_{{U}_{s+1, j}}\left( u \right)$ and $P^{a}_{{U}_{s+1, j'}}\left( u' \right) = P^{e}_{{U}_{s+1, j'}}\left( u' \right)$ for $u, u' \in \mathbb{F}_2$.

\end{itemize}
\end{algorithm}

{\bf Remark.}~It can be seen that both Algorithm~\ref{alg:FHT} and Algorithm~\ref{alg:SISO_FHT_DEC} have complexity of order $O(N\log N)$ since the fast Hadamard transform has $p = \log N$ stages and each stage can be decomposed into $N/2$ independent building blocks as specified by $\mathbfit{H}_2$, each of which is for one complementary pair.

\subsection{Multiple-rate Codes Based on Hadamard Transform}
Given $N$, we can construct a family of codes with dimension $K$ ranging from $1$ to $N-1$. Each code in this family is encoded in the same manner $\mathbfit{v} = \mathbfit{u} \mathbfit{H}_N$. The code rate $K/N$ is attained by fixing some $N-K$ bits in $\mathbfit{u}$ and leaving the other bits free to carry the information. Following~\cite{Arikan2009}, this family of codes are called $\mathbfit{H}_{\!N}$-coset~(or HT-coset) codes. The issue is how to determine a good {\em active} set for a given $K$. For this end, we define a permutation matrix $\mathbfit{\Pi}_N$ of order $N$ such that the rows of the matrix $\mathbfit{G}_N = \mathbfit{\Pi}_N \mathbfit{H}_N$ has a desired order. We may define $\mathbfit{\Pi}_N$ following the polar coding approach~\cite{Arikan2009}, which requires sorting the Bhattacharyya parameters or the mutual information rates for some {\em artificial} channels and usually depends on the channel condition, say, the SNR. Here we define $\mathbfit{\Pi}_N$ according to a channel-independent rule, which was referred to as RM-rule in~\cite{Arikan2009}, such that the rows of $\mathbfit{G}_N = \mathbfit{\Pi}_N \mathbfit{H}_N$ are ordered with non-decreasing Hamming weight. Given $\mathbfit{\Pi}_N$, the encoding algorithm and decoding algorithm for the HT-coset codes
are essentially the same as Algorithm~\ref{alg:FHT} and Algorithm~\ref{alg:SISO_FHT_DEC}, respectively. We only need to freeze some $N-K$ bits when encoding and to initialize these frozen bits with deterministic messages when decoding. These two basic adaptations are summarized in the following algorithms for completeness, where $K$ is specified. See Fig.~\ref{Hadamard} for reference.

\begin{figure}[t]
\centering
\includegraphics[width=0.5\textwidth]{HadaEncoder.eps}

\caption{The encoding diagram for HT-coset codes.}
\label{Hadamard}
\end{figure}
\begin{algorithm}{The Encoding Algorithm for HT-coset Codes}
\begin{itemize}
  \item {\bf Input:}~Take as input the information sequence $\mathbfit{u} = (u_0, u_1, \cdots, u_{K-1})$.
  \item {\bf Zero padding and permutation:}~The information sequence $\mathbfit{u}$ is expanded by padding $N-K$ zeros and then permuted by $\mathbfit{\Pi}_N$. The resulting vector is denoted by $\tilde{\mathbfit{u}} = (u_0, u_1, u_{K-1},$ $\underbrace{0, \cdots, 0}_{N-K}) \mathbfit{\Pi}_N$.

  \item {\bf Output:}~Deliver as output the codeword $\mathbfit{v} = \tilde{\mathbfit{u}} \mathbfit{H}_N$, which can be computed by Algorithm~\ref{alg:FHT}.
\end{itemize}
\end{algorithm}

\begin{algorithm}{The SISO Decoding Algorithm for HT-coset Codes}\label{alg:HT-coset-dec}
\begin{itemize}
  \item \textbf{Input:}~Take as input $P_{V_j}^a(v), v \in \mathbb{F}_2$ for $0 \leq j \leq N-1$ and $P_{U_j}^a(u), u \in \mathbb{F}_2$ for $0 \leq j \leq K-1$, where the former are usually computable from the channel observations and the latter are available from the source distribution, which are usually assumed to be uniform distribution.

  \item \textbf{{\em A priori} message freezing:}~Set $P_{U_j}^a(0) = 1$ and $P_{U_j}^a(1) = 0$ for $K \leq j \leq N-1$.

   \item \textbf{Output:}~Deliver as output $P^{e}_{U_j}(u), u \in \mathbb{F}_2(0 \leq j \leq K-1)$ for hard decisions and $P^{e}_{V_j}(v), v \in \mathbb{F}_2(0 \leq j \leq N-1)$ for possible use in concatenated systems. These extrinsic messages can be computed by Algorithm~\ref{alg:SISO_FHT_DEC} {\color{black}with the exception that the permutation $\mathbfit{\Pi}_N$ need to be taken into account.}
\end{itemize}
\end{algorithm}

\subsection{A Construction Example}\label{example}
We take $N = 8$ as an example to illustrate the construction procedure. The Hadamard matrix of order $8$ is given by
\begin{equation}\label{HM}
  {\mathbfit{H}_8} = \left[ {\begin{array}{*{20}{c}}
1&1&1&1&1&1&1&1\\
0&1&0&1&0&1&0&1\\
0&0&1&1&0&0&1&1\\
0&0&0&1&0&0&0&1\\
0&0&0&0&1&1&1&1\\
0&0&0&0&0&1&0&1\\
0&0&0&0&0&0&1&1\\
0&0&0&0&0&0&0&1
\end{array}} \right],
\end{equation}
whose rows have Hamming weights $(8, 4, 4, 2, 4, 2, 2, 1)$, respectively. Hence a permutation matrix $\mathbfit{\Pi}_N$ is required to swap the $3$rd row and the $4$th row~(counting from zero). {\color{black}The encoding process is depicted in Fig.~\ref{fig:HadaEnc}, where the dimension $K$ can be varied from $1$ to $7$.}

{Assume that the codeword is transmitted over an additive white Gaussian noise~(AWGN) channel with binary phase-shift keying~(BPSK) signalling.
{\color{black}The performances of the HT-coset codes at the BER around $10^{-5}$ can be evaluated by simulation, while the performances at the extremely low BER~(say $10^{-10}$) can be predicted using the union bound with the help of the input-output weight enumerating function~(IOWEF)~\cite{Mceliece98,Lin04}.} Since the number of codewords of the considered HT-coset codes with $N=8$ is small, we compute the IOWEFs by an exhaustive search. Table~\ref{tab:HTcosetIOWEF} presents the IOWEFs of all HT-coset codes with $N=8$.

We have simulated all these HT-coset codes under the SISO decoding algorithm~(Algorithms~\ref{alg:SISO_FHT_DEC} and~\ref{alg:HT-coset-dec}) with an iteration number $J = 3$. {\color{black}We find that all simulation curves~(not shown here) except that of rate $4/8$ match well with the corresponding union bounds at the BER lower than $10^{-3}$. Fig.~\ref{fig:HTcosetUB} shows the performance curves of the code with rate $4/8$~(the [8, 4] Reed-Muller code). We can see that the performance curve of the rate $4/8$ code under the maximum {\em a posterior} probability~(MAP) decoding matches well with the union bound at the BER lower than $10^{-3}$. However, compared with the union bound, the SISO decoding algorithm~(Algorithms~\ref{alg:SISO_FHT_DEC} and~\ref{alg:HT-coset-dec}) with $J=3$ causes a performance loss of about $0.5$ dB. This performance loss can be narrowed to $0.2$~dB  by increasing $J$, as already pointed out in~\cite{Forney2001}.
}
}

\begin{table}[t]

\renewcommand{\arraystretch}{1.2}
\caption{The IOWEFs for HT-coset Codes with $N=8$\label{tab:HTcosetIOWEF}}
\centering

\begin{tabular}{c||p{7.3cm}}
 \hline
 Codes & IOWEFs \\
 \hline \hline
 $[8, 1]$ & $1 +  XY^8$ \\
 \hline
 $[8, 2]$ & $1 +  XY^4 +  XY^8 +  X^2Y^4$ \\
 \hline
 $[8, 3]$ & $1 + 2XY^4 +  XY^8 + 3X^2Y^4 +  X^3Y^4$\\
 \hline
 $[8, 4]$ & $1 + 3XY^4 +  XY^8 + 6X^2Y^4 + 4X^3Y^4 +  X^4Y^4$ \\
 \hline
 $[8, 5]$ & $1 +  XY^2 + 3XY^4 +  XY^8   + 2X^2Y^2 + 7X^2Y^4 +  X^2Y^6  + 7X^3Y^4 + 3X^3Y^6 + X^4Y^2 + 4X^4Y^4 + X^5Y^4$ \\
 \hline
 $[8, 6]$ & $1 + 2XY^2 + 3XY^4 + XY^8 + 5X^2Y^2 + 8X^2Y^4 + 2X^2X^6 + X^3Y^2 + 12X^3Y^4 + 7X^3Y^6 + 3X^4Y^2 + 11X^4Y^4 + X^4Y^6 + 4X^5Y^4 + 2X^5Y^6 + X^6Y^2$ \\
 \hline
 $[8, 7]$ & $1 + 3XY^2 + 3XY^4 + XY^8 + 9X^2Y^2 + 9X^2Y^4 + 3X^2Y^6 + 3X^3Y^2 + 20X^3Y^4 + 12X^3Y^6 + 9X^4Y^2 + 23X^4Y^4 + 3X^4Y^6 + 12X^5Y^4 + 9X^5Y^6 + 3X^6Y^2 + 3X^6Y^4 + X^6Y^6 + X^7Y^2$ \\
 \hline
\end{tabular}
\end{table}

\begin{figure}[t]
\centering
\includegraphics[width=0.48\textwidth]{Hadaexam.eps}

\caption{The encoding process for HT-coset codes with $N=8$.}
\label{fig:HadaEnc}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=0.48\textwidth]{polar84.eps}

\caption{The performance of the HT coset code with $K=4$ and $N=8$ under the SISO decoding algorithm~(Algorithms~\ref{alg:SISO_FHT_DEC} and \ref{alg:HT-coset-dec}) with an iteration number $J=3$. The union bound and the performance curve of the MAP decoding are also plotted.}
\label{fig:HTcosetUB}
\end{figure}

\section{BMST of Short HT-coset Codes}\label{sec:BMST-HT}
\subsection{Choice of Encoding Memory}\label{subsec:ChooseMemory}
We have demonstrated that Hadamard transform can be used to construct a family of codes with constant length $N$ and flexible dimension $K$.
This family of codes can be implemented by the same pair of encoder and decoder but with adjustable inputs.
However, the performances are far away from the Shannon limits, as evidenced by the construction example with $N=8$. One possible way to improve the performance is to enlarge the order of the Hadamard transform. As $N$ becomes sufficiently large, for any given dimension $K$, we have chance to select active set to approach the channel capacity. The difficulty lies in the choice of the active set when $N$ becomes large. Here we propose to combine the BMST with the HT-coset codes. As pointed out in~\cite{Ma13x}, any short code can be embedded into the BMST system to obtain extra coding gain in the low BER region. The critical parameter for BMST is the encoding memory $m$, which predicts the extra coding gain of $10\log_{10}(m+1)$ dB over AWGN channels.
{\color{black}
Given this predictable extra coding gain, we can use the following deterministic procedure to find the encoding memory $m_K$ required by the BMST-HT system~$(N = 2^p, p > 1)$ to approach the Shannon limit at a target BER $p_{\rm target}$.

{\bf \em A General Procedure of Determining the Encoding Memories for the BMST-HT Systems}\label{pcs:DesignBMST}
\begin{itemize}

  \item For $K = 1, 2, \cdots, N-1$, determine the encoding memory $m_K$ with the following steps.
\begin{enumerate}
  \item From the union bound of the HT-coset code with information bit $K$, find the required $E_b/N_0=\gamma_{K}$ to achieve the target BER $p_{\rm target}$.
  \item Find the Shannon limit for the code rate $K/N$, denoted by $\gamma_{K}^{*}$.
  \item Determine the encoding memory by $10\log_{10}(m+1) \geq \gamma_{K} - \gamma_{K}^{*}$. That is,
        \begin{equation}\label{eq:ComputeMemory}
        m_K = \left\lfloor 10^{\frac{\gamma_K - \gamma^*_K}{10}} - 1 \right\rceil,
        \end{equation}
        where $\lfloor x \rceil$ stands for the integer that is closest to $x$.
\end{enumerate}

\end{itemize}
}

Table~\ref{gap} shows the memory required for each code rate using the BMST of HT-coset codes with $N = 8$ to approach the Shannon limit at a target BER of $p_{\rm target} = 10^{-5}$.

\begin{table}[t]

\renewcommand{\arraystretch}{1.2}
\caption{The Memory Required for Each Code Rate Using the BMST of HT-coset Codes with $N=8$ to Approach the Shannon Limit at the BER of $10^{-5}$\label{gap}}
\centering

\begin{tabular}{p{1.6cm}||c|c|c|c|c|c|c}
 \hline
 \small Rate $R=K/8$ & 1/8 & 2/8 & 3/8 & 4/8 & 5/8 & 6/8 & 7/8\\
 \hline \hline
 \small $\gamma^*_K$~(dB) & -1.2 & -0.8 & -0.3 & 0.2 & 0.8 & 1.6 & 2.9 \\
 \hline
 \small $\gamma_K$~(dB) & 9.6 & 9.8 & 8.4 & 7.7 & 8.9 & 8.6 & 8.2 \\
 \hline
 \small Gap~$\gamma_K\!-\!\gamma^*_K$~(dB)  & 10.8 & 10.6 & 8.7 & 7.5 & 8.1 & 7.0 & 5.3\\
 \hline
 \small Memory $m_K$ & 11 & 10 & 6 & 5 & 5 & 4 & 2 \\
 \hline
\end{tabular}
\end{table}

\subsection{Encoding of BMST-HT System}
\begin{figure}[t]
\centering
\includegraphics[angle=270,width=0.5\textwidth]{Encoder.eps}

\caption{The encoding diagram of the BMST-HT system with a maximum memory $m$.}
\label{encoder}
\end{figure}
A BMST-HT system is constructed by taking the encoder for the HT-coset codes as the basic encoder, which accepts as input a binary information sequence of length $BK$ and delivers as output a binary coded sequence of length $BN$. More precisely, the basic code $\mathscr{C}[n,k]$ is a $B$-fold Cartesian product of $\mathscr{C}[N,K]$, where $n=BN$ and $k=BK$. To approach the capacity, we usually choose $B$ such that $BN>10000$. Since $K$ can be varied from $1$ to $N-1$, the basic encoder actually works as a multiple-rate encoder. To guarantee that all members from the family of the considered HT-coset codes have capacity-approaching performance, the encoder must be furnished with  $m~(=\max\limits_{1 \leq K \leq N-1}{m_K})$ interleavers.
The basic structure of the encoder is shown in Fig.~\ref{encoder}, which consists of one basic encoder, represented by ENC, and $m$ interleavers, represented by $\mathbfit{\Pi}_1, \cdots, \mathbfit{\Pi}_m$, respectively. The switches between the buffers D are used to adjust the encoding memory. In our simulations, all interleavers are randomly generated but fixed. The encoding algorithm is described as follows, where $K$ is specified. See Fig.~\ref{encoder} for reference.
\begin{algorithm}{The Encoding Algorithm for BMST-HT System}
\begin{itemize}
  \item \textbf{Input:}~Take as input $L$ blocks of data $\mathbfit{u}^{(0)}, \mathbfit{u}^{(1)}, \cdots, \mathbfit{u}^{(L-1)}$, where $\mathbfit{u}^{(t)} \in \mathbb{F}_2^{BK}$.
  \item \textbf{Memory choosing:}~Turn on the $m_K$ left-most switches and turn off the other $m-m_K$ switches~see Fig.~\ref{encoder} for reference.
  \item \textbf{Output:}~Deliver as output $L+m_K$ coded sub-blocks $\mathbfit{c}^{(0)}, \mathbfit{c}^{(1)}, \cdots, \mathbfit{c}^{(L+m_K-1)}$ for transmission, where $\mathbfit{c}^{(t)} \in \mathbb{F}_2^{BN}$. This can be done by the encoding algorithm of BMST with memory $m_K$~\cite{XiaoMa2013}.
\end{itemize}
\end{algorithm}

\textbf{Remark.} The code rate decreases to $\frac{{KL}}{{N(L + m_K)}}$ due to the termination. However, the rate loss is negligible for large $L$.

\subsection{Decoding of BMST-HT System}
\begin{figure}[t]
\centering
\includegraphics[width=0.5\textwidth]{Decoder.eps}

\caption{The normal graph of the BMST-HT system with $L = 4$ and $m = 2$.}
\label{decoder}
\end{figure}
Assume that $\mathbfit{c}^{(t)}$ is transmitted with BPSK signalling over AWGN channels, resulting in a received vector $\mathbfit{y}^{(t)}$. The decoding algorithm can be implemented as
an iterative message processing/passing algorithm over a unified~(high-level) normal graph, see Fig.~\ref{decoder} for an example of a BMST system with $L = 4$ and $m = 2$. The normal graph can be divided into $L+m$ layers, each of which typically consists of one node of type \fbox{C} for the basic code, one node of type~\fbox{=} that connects to $m$ future layers via interleavers, and one node of type~\fbox{+} that connects to $m$ past layers. The basic structure is applicable to all members from the family of HT-coset codes. Once $K$~(hence the memory $m_K$) is specified, we only need
to disconnect the edges~(if they exist) between the $t$-th layer and the $(t+\ell)$-th layer for $t \geq 0$ and $\ell>m_K$.
{\color{black}With this adaptation, the sliding-window decoding algorithm is the same as Algorithm~3 in~\cite{Ma13x} with $m$ replaced by $m_K$.}

{\bf Remark.}~We need to point out that both the encoding and the decoding have linear complexity in the code length $n$. Actually, since the basic code is a $B$-fold Cartesian product of a short HT-coset code, the computational complexity at the node \fbox{C} is linear in $B$~(equivalently, the basic code length $n$). In addition, the computational complexity at the node~\fbox{$+$} as well as the node~\fbox{$=$} is also linear with the basic code length~$n$.

\subsection{A Construction Example~(Continued)}
We continue the construction example given in Section~\ref{example}. We take the $B$-fold Cartesian product $\mathscr{C}[8,K]^B(1 \leq K \leq 7)$ as the basic code, where $B = 1250$. The memory required for each $K$ to approach the corresponding Shannon limit at the BER of $10^{-5}$ is specified in Table~\ref{gap}. Hence we need an encoder with a maximum memory $m = 11$.

The SISO decoding algorithm~(Algorithms 2 and 4) with an iteration number $J=3$ is used to implement the SISO decoding algorithm for the basic code.
The iterative sliding-window decoding algorithm for the BMST-HT system is performed with a maximum iteration number of $18$, where the entropy-based early stopping criterion~\cite{Ma04,Ma13x} is used with a threshold of $10^{-5}$. Simulation results with $L=1000$ for encoding are shown in Fig.~\ref{polar}, where the decoding delay is specified as $d_K = 2m_K$ for code rate $K/N$. {\color{black}

Also shown in Fig.~\ref{polar} are the genie-aided lower bounds, which are obtained by shifting the corresponding performance curves of the basic codes to left by $10 \log_{10}(1 + m_K)$~dB.}
We can see that the performances of the BMST-HT system match well with the
respective genie-aided lower bounds in the low BER region for all considered code rates.
{\color{black}To evaluate the bandwidth efficiency of the BMST-HT system, we plot the required SNR to achieve the BER of $10^{-5}$ against the code rate in Fig.~\ref{capacity}. We can see that the BMST-HT system achieves the BER of $10^{-5}$ within one dB from the Shannon limit for all considered code rates.}
However, the performance gap of the $[8,4]$ code is slightly larger. This is due to the sub-optimality of Algorithm~\ref{alg:SISO_FHT_DEC}, as mentioned previously. {\color{black}If an optimal~(locally) SISO algorithm~(the MAP decoding) is used for the $[8, 4]$ code, the performance can be improved, as marked in Fig.~\ref{capacity} by the cross $\mathbf{\times}$.

\subsection{Further Discussions}
We have also constructed a BMST-HT system using the $B$-fold Cartesian product $\mathscr{C}[16,K]^B$ $(1 \leq K \leq 15)$ as the basic code, where $B = 625$.

The required encoding memories can be determined following the procedure described in Section~\ref{subsec:ChooseMemory}, which are shown in Table~\ref{tab:memory16}.

The required SNR to achieve the BER of $10^{-5}$ is plotted against the code rate in Fig.~\ref{fig:capacity16}.
{\color{black}We can see that the BMST-HT system also has a BER of $10^{-5}$ within one dB away from the Shannon limits for all considered code rates.

Using HT-coset codes with larger $N$, we can implement codes with finer code rates.

However, this simple approach can only construct codes with rates of form $K/2^p$.

In practice, other code rates~(say $1/3$ and $4/5$ in the standard of Long Term Evolution~(LTE)) are required~\cite{3GPPR11}.
In this case, we can construct the basic code by combining several HT-coset codes with different rates.
Taking rate $1/3$ as an example, we can use the Cartesian product of the HT-coset codes $\left[[4,1]\times[4,1]\times[4,2]\right]^B$ as the basic code.

}
{
\begin{figure}[t]
\centering
\includegraphics[width=0.5\textwidth]{moderate_m.eps}

\caption{\color{black}Performance of the BMST-HT system using the Cartesian products of the HT-coset codes $[8,K]^{1250}(1 \leq K \leq 7)$ with $L=1000$. The sliding-window decoding algorithm is performed with a maximum iteration number $I_{\max}=18$ and a decoding delay $d_K=2m_K$ for the code of rate $K/8$.}
\label{polar}
\end{figure}
}
\begin{figure}[t]
\centering
\includegraphics[width=0.47\textwidth]{capacity8.eps}

\caption{The required SNR for the BMST-HT system using the
Cartesian products of HT-coset codes $[8,K]^{1250}(1 \leq K \leq 7)$ to achieve the BER of $10^{-5}$ with BPSK signalling over AWGN channels.}
\label{capacity}
\end{figure}

\begin{table}[t]

\renewcommand{\arraystretch}{1.2}
\caption{The Memory Required for Each Code Rate Using the BMST of HT-coset Codes with $N=16$ to Approach the Shannon Limit at the BER of $10^{-5}$\label{tab:memory16}}
\centering

\begin{tabular}{c||c|c|c|c}
 \hline
 $R=K/16$ & $\gamma^*_K$~(dB) & $\gamma_K$~(dB) & $\gamma_K\!-\!\gamma^*_K$~(dB) & $m_K$ \\
 \hline \hline
 1/16 & -1.4 & 9.6 & 11.0 & 12 \\
 \hline
 2/16 & -1.2 & 9.8 & 11.0 & 12 \\
 \hline
 3/16 & -1.0 & 8.4 & 9.4 & 8 \\
 \hline
 4/16 & -0.8 & 7.7 & 8.5 & 6 \\
 \hline
 5/16 & -0.6 & 7.4 & 8.0 & 5 \\
 \hline
 6/16 & -0.3 & 8.1 & 8.4 & 6 \\
 \hline
 7/16 & -0.1 & 7.9 & 8.0 & 5 \\
 \hline
 8/16 &  0.2 & 7.6 & 7.4 & 4 \\
 \hline
 9/16 &  0.5 & 7.4 & 6.9 & 4 \\
 \hline
 10/16 & 0.8 & 7.2 & 6.4 & 3 \\
 \hline
 11/16 & 1.2 & 7.5 & 6.3 & 3 \\
 \hline
 12/16 & 1.6 & 8.2 & 6.6 & 4 \\
 \hline
 13/16 & 2.2 & 8.4 & 6.2 & 3 \\
 \hline
 14/16 & 2.8 & 8.4 & 5.6 & 3 \\
 \hline
 15/16 & 3.9 & 8.3 & 4.4 & 2 \\
 \hline
\end{tabular}
\end{table}
\begin{figure}[t]
\centering
\includegraphics[width=0.48\textwidth]{capacity16.eps}

\caption{The required SNR for the BMST-HT system using the
Cartesian products of HT-coset codes $[16,K]^{625}(1 \leq K \leq 15)$ to achieve the BER of $10^{-5}$ with BPSK signalling over AWGN channels.}
\label{fig:capacity16}
\end{figure}

\section{Conclusions}\label{sec:result}

In this paper, we have proposed a new class of multiple-rate codes by embedding the Hadamard transform~(HT) coset codes into the block Markov superposition transmission~(BMST) system, resulting in the BMST-HT system. The implementation complexity of the system is linear in the code length, while the performance in the low error rate region can be predicted. The simulation results show that the BMST-HT system can approach the Shannon limit within one dB at the BER of $10^{-5}$ for a wide range of code rates.


TITLE: $x^\alpha$ as an example of an $\alpha$-Hölder continuous function
QUESTION [5 upvotes]: I saw the following statement by user Mark Joshi in response to the question :
Non-trivial exemple of Hölder continuous function.

$x^\alpha$ for $x > 0$ and $0$ otherwise for $0 < \alpha < 1$ is Holder continuous of order $\alpha$

I cannot seem to prove this statement. How do I proceed to show that the function $f(x) = x^{\alpha}$ is Holder continuous of order $\alpha<1$, i.e., $|f(x_1) - f(x_2)| \leq c |x_1-x_2|^{\alpha}$ for all $x_1, x_2 \in (0, \infty)$, and some $c>0$.

REPLY [3 votes]: Take $x_{0} \geq 0$ and, for $x > x_{0}$, define
$$g(x) = x^{\alpha} - x_{0}^{\alpha} - (x-x_{0})^{\alpha}.$$
Then
$$g'(x) = \alpha x^{\alpha-1} - \alpha(x-x_{0})^{\alpha-1}.$$
Since $\alpha - 1 < 0$ and $x > x_{0}$, $g'(x) \le 0$. So, $g'$ is decreasing with $g(x_{0}) = 0$, for $x > x_{0}$. Can you continue?


TITLE: Probability of choosing two random cards of the same value
QUESTION [3 upvotes]: I know this question was asked here: What is the probability of choosing two cards of the same value?
But I'm trying to understand it in terms of combinations.
Two cards are randomly chosen from a deck of 52.  What is the probability that they have the same value?
I'm thinking:
$\frac{\binom{13}{1} \binom{3}{1}}{\binom{52}{2}}$
Out of 13 possibilities you choose the first card (say it's a 7).  Then for the second card you need to pick another 7 out of the remaining three 7's.
Can anyone explain to me where I'm going wrong in my thinking?
Thanks

REPLY [3 votes]: Your thinking is very close to what is needed. The issue is, the choice of your second card is not independent from the first. When you pick the first card, you are forcing an ordering where that first card must be picked first, then the second card must be picked. Parcly Taxel's method adeptly shows how you can carefully include the consideration of the order in which the cards are selected. That approach works really well, and I highly recommend it.
However, if your goal is truly for an approach using only combinations, then it is important to avoid inducing any ordering.
The goal is to pick both cards at the same time instead of one then the next.
Instead of picking the first card then the second, pick the value of the two cards, but do not actually pick a card. There are $\dbinom{13}{1}$ ways of choosing the value. Regardless of which value is chosen, there are four cards of that value. Now, we select both cards at once in $\dbinom{4}{2}$ ways. This gives the probability of selecting two of the same card:
$$\dfrac{\dbinom{13}{1}\dbinom{4}{2}}{\dbinom{52}{2}} = \dfrac{1}{17}$$
This gives the exact same answer as Parcly Taxel's solution. In fact, it is counting the same thing, just in a different way.


text:
\begin{document}
\fancytitle

\begin {abstract}
Richard G.\ Swan proved in 1962 that trinomials $x^{8k}+x^m+1\in\F_2[x]$
with $8k>m$ have
an even number of irreducible factors, and so cannot be irreducible.
In fact, he found the parity of the number of irreducible factors
for any square-free trinomial in $\F_2[x]$.
We prove a result that is similar in spirit. Namely, suppose $n$ is odd
and $f(x) = x^n + \sum_{i\in S} x^i + 1\in\F_2[x]$, where
$S\subset\{i: i\ odd, 0 < i < n/3\} \cup \{i: i=n \pmod 4, 0<i<n\}$.
We show that if $n=\pm1 \pmod 8$ then $f$ has  an odd number of
irreducible factors, and if $n=\pm 3 \pmod 8$ then $f$ has an even
number of irreducible factors.  This has an application to the
problem of finding polynomial bases $\{1,\alpha,\ldots,\alpha^{n-1}\}$
of $\F_{2^n}$ such that $\Tr(\alpha^i)=0$ for all $1\le i<n$.

\end{abstract}

\section{Introduction}
For purposes of implementing field arithmetic in $\F_{2^n}$ efficiently,
it is desirable to have an irreducible polynomial $f(x)\in\F_2[x]$
of degree~$n$ with as few terms as possible.  The number of terms
must be odd, as otherwise
$x+1$ would be a factor.  Often a trinomial $x^n+x^m+1$ can be found,
or at least a pentanomial, $x^n+x^{m_1}+x^{m_2}+x^{m_3}+1$, where
$n>m_1>m_2>m_3>0$.  If $\alpha$ is a root of $f$, then $\{1,\alpha,\alpha^2,
\ldots,\alpha^{n-1}\}$ is a basis for $\F_{2^n}/\F_2$, called
a {\it polynomial basis}.  Multiplication with respect to this basis
is more efficient when the number of terms in $f$ is small.
In addition, multiplication will be more efficient if $f$ has the
form $x^n+g(x)$, where $\deg(g)$ is small.
For a trinomial, we would like $m$ to be small, and for
a pentanomial, we would like $m_1$ to be small.

It is also desirable to be able to compute the trace
quickly. Now $\Tr(\sum a_i\alpha^i)= \sum_{i\in I}a_i$, where
$I=\{i : \Tr(\alpha^i)=1\}$.  Thus, trace is especially easy to compute
if $I$ has a single element.  Ahmadi and Menezes \cite{AM} showed that
if $n$ is odd, then $|I|=1$ if and only if $f(x)+1$ contains only monomials
of odd degree.  They computed irreducible trinomials and pentanomials
with this property
($m$ odd for a trinomial, and $m_1m_2m_3$ odd for a pentanomial.)
To their surprise, $m_1$ seemed to be always small when $n=\pm1 \pmod 8$,
but $m_1\ge n/3$ when $n=\pm 3 \pmod 8$.  This article explains their
observation:  we prove that if $n=\pm3\pmod8$ and $m_1 < n/3$,
then $x^n+x^{m_1}+x^{m_2}+x^{m_3}+1$ has an {\it even} number of
irreducible factors, and so it cannot be irreducible. More generally,
we prove:

\proclaim{Theorem}.
{Let $n$ be odd
and $f(x)=x^n+\sum_{i\in S} x^i + 1 \in\F_2[x]$, where
\begin{equation}
\label{Sdef}
S\subset \{\,i:i\ {\rm odd}, 0<i<n/3\,\} \cup
\{\,i: i= n \pmod 4, 0<i<n\,\}.
\end{equation}

Then $f$ has no repeated roots.
If $n=\pm 1 \pmod 8$ then $f$ has an odd number of irreducible
factors. If $n=\pm 3 \pmod 8$ then $f$ has an even number of
irreducible factors.
}

The bound $n/3$ is sharp, as shown by the example
$x^{21}+x^7+1$, which is irreducible.

\begin{corollary} Let $n=\pm3\pmod 8$ and let $f\in\F_2[x]$ be an
irreducible polynomial of degree~$n$ such that $\Tr(\alpha^i)=0$
for each $1\le i < n$. Then $f(x)$ contains a term $x^k$
with $n>k\ge n/3$.
\end{corollary}

\begin{proof} Ahmadi and Menezes \cite{AM} showed that all the terms
occurring in $f+1$ have odd exponent. Let $f=x^n + x^k +$ lower degree terms.
By the theorem,
$f$ will have an even number of irreducible factors unless $k\ge n/3$.
\end{proof}

Our theorem is closely related to work of Fredricksen, Hales, and
Sweet \cite{FHS}.
The first theorem in their paper, when specialized
to $g(x) = 1 + \sum_{i\ odd} a_i x^i$, yields a weak form of this theorem,
namely that for $n$ odd and $n>5\deg(g)$, the parity of the number
of factors of $x^n+g(x)$ is a periodic function of $n$, with period~8.

\section{Resultants and discriminants}
\label{discSec}

This section gives background on resultants which will be needed
for the proof of the theorem.  An excellent reference
is \cite[Sections 5.8 and 5.9]{vanderWaerden}.

Let $f=\sum_{i=0}^n a_i x^{n-i}$ and $g=\sum_{i=0}^m b_i x^{m-i}$ be polynomials
in $K[x]$, where $K$ is a field and $a_0b_0\ne 0$. The resultant
of $f$ and $g$, denoted $R(f,g)$,  is the determinant of the matrix
\begin{equation}
\begin{pmatrix}
a_0 & a_1 & a_2    &\ldots & a_n&\\
    & a_0 & a_1    & a_2 & \ldots & a_n & \\
&   &     & \ldots &     &        &     & \\
&   &     & a_0 & a_1    & a_2 &\ldots & a_n \\
b_0 & b_1 & b_2 &\ldots  & b_m&&\\
&b_0 & b_1 & b_2 & \ldots  &b_m&\\
&&   &     & \ldots              &     && \\
&   &     &        &      b_0    & b_1 &\ldots & b_m \\
\end{pmatrix}.
\end{equation}
Here there are $m$ rows containing coefficients of $f$ and $n$ rows
containing coefficients of $g$, and the principal diagonal contributes
$a_0^m b_m^n$ to the determinant.
Now $f,g$ can be factored completely into linear factors over the algebraic
closure:
\begin{eqnarray*}
f(x) &=& a_0 (x-x_1)(x-x_2)\cdots(x-x_n) \\
g(x) &=& b_0 (x-y_1)(x-y_2)\cdots(x-y_m).
\end{eqnarray*}
As shown in \cite{vanderWaerden},
$$R(f,g)=a_0^m\prod_{i=1}^n g(x_i) = (-1)^{mn}\, b_0^n\, \prod_{j=1}^m f(y_j).$$
The resultant respects the following properties.
\begin{enumerate}
\item[(R1)]{If $g=fq+r$, $R(f,g)= R(f,r)$.}
\item[(R2)]{$R(x,g)=g(0)$, $R(f,-x)=f(0)$.}
\item[(R3)]{$R(f_1f_2,g)=R(f_1,g)R(f_2,g)$, $R(f,g_1g_2)=R(f,g_1)R(f,g_2)$.}
\end{enumerate}

Note that $R(f,g)=0$ if and only if $f$ vanishes at a root of $g$ in $\cj K$;
equivalently, if and only if $\GCD(f,g)$ has degree $\ge 1$.
Also, if the coefficients of $f,g$ belong to a subring $A\subset K$, then
$R(f,g)\in A$. We will apply this to the case $\Z\subset \Q$;
thus $R(f,g)\in\Z$ is defined for $f,g\in\Z[x]$.
It will be handy to note that if $a_0=1$ then we can pad $g(x)$
with leading zeros (thereby increasing $m$ and allowing $b_0=0$)
without affecting the determinant of the above matrix.

If $f=(x-x_1)\cdots(x-x_n)$ then
$$R(f,f') = \prod_i f'(x_i)=\prod_{i\ne k} (x_i-x_k)
= (-1)^{n(n-1)/2} \prod_{i<k} (x_i-x_k)^2.$$
The {\it discriminant} of $f$ is defined as
$$\disc(f) = \prod_{i < j} (x_i-x_j)^2 = (-1)^{n(n-1)/2} R(f,f').$$

Swan \cite[Corollary 3]{Swan} proved the following:
\proclaim{Stickelberger-Swan Theorem}. {Let $f\in\F_2[x]$,
and suppose $\disc(f)\ne 0$ (equivalently, $f$ has no repeated roots).
Let $t$ denote the number of irreducible factors of
$f(x)$ over $\F_2[x]$. Let $F(x)\in\Z[x]$ be any monic lift to the integers.
Then $t=\deg(f)\pmod 2$ if and only if $disc(F)=1\pmod 8$.}

Swan used this result to characterize the square-free trinomials in
$\F_2[x]$ which
have an odd number of irreducible factors.  A characterization
for tetranomials in $\F_2[x]$ was recently obtained by
Hales and Newhart \cite{HN}.
Another very interesting generalization of Swan's Theorem
is given by Fredricksen, Hales, and Sweet \cite{FHS}.

\section{Proof of the theorem}
Let $F$ be the lift of $f$ to $\Z$ which has all its coefficients
equal to 0 or~1, that is,
\begin{equation}
\label{Fdef}
F(x)=x^n + \sum_{i \in S} x^i + 1 \in \Z[x].
\end{equation}
We will show $\disc(F)=1\pmod 8$ if $n=\pm1\pmod8$
and $\disc(F)=5\pmod 8$ if $n=\pm3\pmod8$.
Since $\disc(f)=\disc(F)\pmod 2$, this will imply
$f$ has nonzero discriminant, hence distinct roots. Further,
the Stickelberger-Swan Theorem
will imply that $f$ has an odd number of irreducible factors
if and only if $n=\pm1\pmod 8$.

We compute $\disc(F)$ using the properties of discriminants and resultants
given in Section~\ref{discSec}. We have
\begin{equation*}
\disc(F) = (-1)^{n(n-1)/2} R(F,F').
\end{equation*}
Since $R(F,-x)=F(0)=1$, we have
$R(F,F')=R(F,-xF')=R(F,-xF'+nF)$, and so
\begin{equation*}
n^n \disc(F) = (-1)^{n(n-1)/2} R(F,G), \qquad\text{where $G=n(nF-xF')$.}
\end{equation*}
Now
$$G=\sum_{i \in S} n(n-i) x^i + n^2 = 4G_4(x) + 2 G_2(x)+1\pmod 8,$$
where
\begin{eqnarray*}
G_2(x) &=& \sum_{i\in S,\ n-i=2\,(\bmod 4)} \left(\frac{n(n-i)}{2}\right) x^i, \\
G_4(x) &=& \sum_{i\in S,\ n-i=4\,(\bmod 8)} \left(\frac{n(n-i)}{4}\right) x^i.
\end{eqnarray*}
Note that $\deg(G_2) < n/3$ and $\deg(G_4) < n$ by~(\ref{Sdef}). We will prove that
$$R(F,G)=1\pmod 8.$$
This will imply
$n^n\disc(F)=(-1)^{n(n-1)/2}\pmod 8$.
Since $n^2=1\pmod 8$ we conclude $\disc(F)=n(-1)^{n(n-1)/2} \pmod 8$,
and this equals 1 if $n=\pm 1\pmod 8$, or 5 if $n=\pm 3\pmod 8$,
as required.

It remains to prove $R(F,G)=1\pmod 8$.
Since we are allowed to pad $G$ with leading zeros (as explained
in Section~\ref{discSec}), we may assume $\deg(G)=n-4$.  Now set up the corresponding
matrix for the resultant.  Lemma~\ref{general} below implies that this matrix
has determinant $1\pmod8$.  This completes the proof of the theorem.

Unfortunately, Lemma~\ref{general} is technical and unenlightening.  For this reason, we include
two simpler lemmas which imply special cases of the theorem. Namely, Eq~(\ref{eq1})
of Lemma~\ref{lemma1} (with $F_0=F_1=0$) implies our result when $S\subset \{\,i\ odd: 0 < i < n/3\,\}$,
and Eq~(\ref{eq2}) handles the case when $S\subset \{\, i: i = n \pmod 4, i < n/2\,\}$.
Lemma~\ref{lemma2} implies $R(F,G)=1 \pmod 8$ when
$S\subset \{\,i: i = n \pmod 4, 0 < i < n \,\}$.

\section{Some lemmas}
\label{resSec}

In this section we provide the lemmas which were promised at the end of the preceding
section. Lemmas~\ref{lemma1} and~\ref{lemma2} can be used to show
$R(F,G)=1 \pmod 8$ in special cases, and Lemma~\ref{general}
handles the general case.

\begin{lemma}\label{Dlemma}
Let $D$ be a square matrix with entries in $\Z/8\Z$ such that
$D_{ij}$ is even and $D_{ij}D_{ji}=0$ whenever $i\ne j$. Then $\det(D)=\prod D_{ii}$.
\end{lemma}

\begin{proof}
Consider the expansion of
$\det(D)$. The principal diagonal contributes $\prod_{i=1}^n D_{ii}$.
We claim all other terms are 0 mod~8. Indeed, a nonprincipal summand contains
some $D_{ij}$ with $i\ne j$.  If it also contains $D_{ji}$ then the
summand is $0\pmod 8$. If not then the summand contains
some $D_{j\ell}$ from the $j$th row and $D_{k i}$ from the $i$th column,
where $i,j,k$ and $i,j,\ell$ are distinct; but in that case the summand is
again $0\pmod 8$ since it contains the product of at least three
off-diagonal entries.
\end{proof}

\begin{lemma} \label{lemma1} Let $H\in\Z[x]$, $x | H$, and $\deg(H)=s$. Let $n > 1$
and $F_0,F_1,F_2\in\Z[x]$ such that $\deg(F_k) < n - ks$, $k=0,1,2$.
Then
\begin{equation}
R(x^n + 4 F_0(x) + 2 F_1(x) + F_2(x), 2H + 1) = 1 \pmod 8\label{eq1}
\end{equation}
\begin{equation}
R(x^n + 2 F_0(x) +  F_1(x), 4H + 1) = 1 \pmod 8. \label{eq2}
\end{equation}
\end{lemma}

\begin{proof}
First we prove (\ref{eq1}).
The resultant $R(x^n+4 F_0(x)+2F_1(x)+F_2(x),2H(x)+1)$ is the determinant
of an $(n+s)\times (n+s)$
matrix of a special shape; we will take advantage of this to show that its
determinant is $1\pmod 8$.  For example, in the case
$s=3$, $n=12$ the matrix looks like:
\begin{equation*}
\begin{pmatrix}
   \text{I 4 4 4 2 2 2 * * * * * * 0 0} \\
   \text{0 I 4 4 4 2 2 2 * * * * * * 0}\\
   \text{0 0 I 4 4 4 2 2 2 * * * * * *}\\
   \text{2 2 2 I 0 0 0 0 0 0 0 0 0 0 0}\\
   \text{0 2 2 2 I 0 0 0 0 0 0 0 0 0 0}\\
   \text{0 0 2 2 2 I 0 0 0 0 0 0 0 0 0}\\
   \text{0 0 0 2 2 2 I 0 0 0 0 0 0 0 0}\\
   \text{\ \ \ \ \ \ \ $\ldots$ }\\
   \text{0 0 0 0 0 0 0 0 0 0 0 2 2 2 I}
\end{pmatrix}
\end{equation*}
where $I$ denotes an integer which is $1\pmod 8$,
$*$ denotes any integer, 2 denotes any even integer,
4 denotes any integer which is divisible by 4, and
0 denotes any integer which is divisible by 8.
There are $s$ 4's, $s$ 2's, and $(n-2s)$ *'s in each of the first $s$ rows.
Let $M$ denote this matrix, and $\cj M$ its image in $\Z/8\Z$.
Since $\det(\cj M)=\det(M)\pmod 8$, it suffices to consider the entries
as belonging to $\Z/8\Z$.

Use the 1's in the first $s$ rows as pivots to clear the even numbers
in the columns below them to obtain a matrix of the form:
\begin{equation*}
\begin{pmatrix}
   \text{I 4 4 4 2 2 2 * * * * * * 0 0} \\
   \text{0 I 4 4 4 2 2 2 * * * * * * 0}\\
   \text{0 0 I 4 4 4 2 2 2 * * * * * *}\\
   \text{0 0 0 I 4 4 4 2 2 2 2 2 2 2 2}\\
   \text{0 0 0 2 I 4 4 4 2 2 2 2 2 2 2}\\
   \text{0 0 0 2 2 I 4 4 4 2 2 2 2 2 2}\\
   \text{0 0 0 2 2 2 I 0 0 0 0 0 0 0 0}\\
   \text{0 0 0 0 2 2 2 I 0 0 0 0 0 0 0}\\
   \text{0 0 0 0 0 2 2 2 I 0 0 0 0 0 0}\\
   \text{\ \ \ \ \ \ \ $\ldots$ }\\
   \text{0 0 0 0 0 0 0 0 0 0 0 2 2 2 I}
\end{pmatrix}
\end{equation*}
This matrix has the form $\cj M=\left({A\atop 0}{B\atop D}\right)$, where
$A$ is upper-triangular with 1's on the diagonal and $D$ has 1's on the
diagonal and satisfies
the conditions of Lemma~\ref{Dlemma}. Hence, $\det(\cj M)=\det(A)\det(D)=1$.

The equation (\ref{eq2}) is proved similarly, except that one begins
with a matrix of the form
\begin{equation*}
\begin{pmatrix}
   \text{I 2 2 2 * * * * * * * * * 0 0} \\
   \text{0 I 2 2 2 * * * * * * * * * 0}\\
   \text{0 0 I 2 2 2 * * * * * * * * *}\\
   \text{4 4 4 I 0 0 0 0 0 0 0 0 0 0 0}\\
   \text{0 4 4 4 I 0 0 0 0 0 0 0 0 0 0}\\
   \text{0 0 4 4 4 I 0 0 0 0 0 0 0 0 0}\\
   \text{0 0 0 4 4 4 I 0 0 0 0 0 0 0 0}\\
   \text{\ \ \ \ \ \ \ $\ldots$ }\\
   \text{0 0 0 0 0 0 0 0 0 0 4 4 4 I 0}\\
   \text{0 0 0 0 0 0 0 0 0 0 0 4 4 4 I}
\end{pmatrix}.
\end{equation*}
\end{proof}

If $F=x^n + \sum_{i\in S} x^i + 1$ with $S\subset \{\,i\ odd: 0<i<n/3\,\}$ then we
can apply Eq.~(\ref{eq1}) to show $R(F,G)=1\pmod 8$, taking $F_0=F_1=0$, $F_2=\sum_{i\in S} x^i + 1$, $H=G_2+2G_4$.
If $S\subset \{\,i: i=n (\bmod\ 4),
0<i<n/2\,\}$ then we apply Eq.~(\ref{eq2}) with $F_0=0$, $F_1=\sum_{i\in S} x^i + 1$, $H=G_4$.
For the case $S\subset \{\,i: i=n (\bmod\ 4), 0<i<n\,\}$
one verifies that the matrix $M$ which computes $R(F,G)$, when reduced mod~8,
satisfies the
conditions of Lemma~\ref{lemma2} below, and so $R(F,G)=\det(M)=1\pmod 8$.
For the general case of $S$ as in~(\ref{Sdef}), we require the more complicated
Lemma~\ref{general} in order to show $R(F,G)=1\pmod 8$.

\begin{lemma}  \label{lemma2} Let $0\le m < n$ and let $M$ be an
$(m+n)\times(m+n)$ matrix with entries in $\Z/8\Z$ of the form:
\begin{equation*}
\begin{pmatrix}
A & B \\ C & \raisebox{-7pt}[0pt][0pt]{D}\\ 0 &

\end{pmatrix}
\end{equation*}
where $A=(a_{ij}),C=(c_{ij})$ are $m\times m$ matrices, $B=(b_{i\ell})$ is $m\times n$, $D=(d_{k\ell})$ is
$n\times n$. Assume the following conditions hold:
\begin{enumerate}
\item{The principal diagonal entries of $M$ are all equal to~1 ({\it i.e.},
$a_{ii}=d_{kk}=1$ for $1\le i\le m$ and $1\le k\le n$).}
\item{$A$ is upper-triangular, and $a_{ij}$ is even when $i+j$ is odd.}
\item{$C$ is upper-triangular, all entries of $C$ are divisible by~4, and $c_{ij}=0$ when
$i+j$ is odd.}
\item{$d_{k\ell}=0\pmod 4$ when $k\ne \ell$.}
\item{$b_{ir}$ is even when $r\le i$ and $i+r$ is even.}
\end{enumerate}
Then $\det(M)=1\pmod 8$.
\end{lemma}

\begin{proof}
Since $A$ is upper-triangular with 1's on its principal diagonal, the top $m$ rows of $M$
may be used as pivots. Because of the conditions on $C$, a row operation
will consist of adding four times the $i$-th row of $(A\ B)$ onto
the $r$th row of $({C\atop 0}\ D)$, where $r\le i$ and $r=i\pmod 2$.
After each pivot operation, the conditions on $C$ will remain true: the
entries of $C$ will still be divisible by~4, and $c_{rs}$ will
still be 0 when $r+s$ is odd because $a_{is}$ is even when $i+s$ is odd.
The conditions on $D$ will also remain true: $d_{rr}$ will still be one because
$b_{ir}$ is even.  After completing the pivot operations, $C$ will be reduced
to 0. Thus, $\det(M)=\det(A)\det(D)$. Clearly $\det(A)=1$, and $\det(D)=1$
by Lemma~\ref{Dlemma}.

\end{proof}

The next lemma implies $R(F,G)=1$ in the general case where $S$ is as in~(\ref{Sdef}). Here $F,G$ have the form
\begin{eqnarray*}
F(x) &=& x^n + \sum_{ {4|k} \atop {0<k<n} } a_k x^{n-k}
+ \sum_{ {k=2\,(\bmod\ 4)} \atop{(2n/3)<k<n} } a_k x^{n-k} + 1 \\
G(x) &=& 4 \sum_{ {4|k} \atop {0<k<n}} b_k x^{n-k} +
2 \sum_{ {k=2\,(\bmod\ 4)} \atop {(2n/3)<k<n} } b_k x^{n-k} + 1
\end{eqnarray*}
where $a_k,b_k\in\Z$.  We consider $G$ to have degree~$m=n-4$ (possibly
with leading zeroes) and set up the matrix $M$ which computes the
resultant $R(F,G)$.  This matrix, when reduced mod~8, satisfies the
conditions of the next lemma, so $R(F,G)=\det(M)=1\pmod8$.
 The proof of Lemma~\ref{general} is
similar to that of Lemma~\ref{lemma2}, but
the details are much messier.

\begin{lemma} \label{general}
Let $n\ge5$ be odd, $m=n-4$, and $M=\left(X\atop Y\right)$ be a square
matrix over $\Z/8\Z$, where $X$ is $m\times (m+n)$ and $Y$ is $n\times(m+n)$.
Let $s=\lfloor (n-1)/3\rfloor$.  Assume
\begin{enumerate}
\item[(H1)] {$M_{ii}=1$ for $1\le i\le n+m$; equivalently, $X_{ii}=Y_{r,r+m}=1$ for $1\le i\le m$
and $1\le r \le n$.}
\item[(H2)]{$X_{ij}=0$ unless $j-i\in ([0,n-s)\cap4\Z)\cup([n-s,n)\cap2\Z)\cup \{n\}$.}
\item[(H3)]{$Y_{ij}=0$ if $j<i$, and $Y_{ij}$ is even if $j\ne m+i$.}
\item[(H4)]{For $k\in [0,m-s)$, we have $$Y_{i,i+k}= \begin{cases}0\pmod4 & \text{if $k=0\pmod4$}\\
0\pmod 8  & \text{otherwise.} \end{cases}$$}
\item[(H5)]{For $k\in [m-s,m+n-2s)$ and $k\ne m$, we have
$$Y_{i,i+k}=\begin{cases}0\pmod2& \text{if $k=2\pmod 4$,}\\
0\pmod4&\text{if $k=0\pmod 4$, or if $k$ is odd and $i+k>m$,} \\ 0\pmod 8 & \text{otherwise.} \end{cases}$$ }
\end{enumerate}
Then $\det(M)=1\bmod 8$.
\end{lemma}

\begin{proof}
Write $X=\left(A\ B\right)$, where $A$ is $m\x m$. By hypothesis, $A$ is an
upper-triangular matrix with 1's on the diagonal, and so the rows of $X$ may be used as pivots
to clear the first $m$ columns of $Y$. We will show below that the new $Y$ still
satisfies the hypotheses, but with the first $m$ columns of $Y$ equal
to 0. Let $D$ denote the rightmost $n$ columns of $Y$; then
$\det(M)=\det(D)$. We will show below that $\det(D)=1$.

It remains to prove the two claims:
(1) when a row of $X$ is used as a pivot to clear
the first $m$ columns, the new matrix still satisfies the hypotheses; and
(2) $\det(D)=1$.

We begin with the second claim. We show that $D$ has 1's on the diagonal and
satisfies the hypotheses of Lemma~\ref{Dlemma}.
By (H1) and (H3), the diagonal entries
$D_{ii}$ are equal to~1, and the off-diagonal entries are even.
We now show $D_{ij}D_{ji}=0\pmod8$ if $i\ne j$. By symmetry we can assume
$i<j$. Since $D_{ij}$ and $D_{ji}$ are even, it suffices to show
one of $D_{ij}$, $D_{ji}$ is $0\pmod4$.
Assume 4 does not divide $D_{ji}$ and we will show that 4 divides $D_{ij}$.
Let $t=j-i>0$. Then $D_{ij}=Y_{i,i+(m+t)}$, $D_{ji}=Y_{j,j+(m-t)}$.
Since 4 does not divide $D_{ji}$, (H4) implies
that $m-t$ is not in $[0,m-s)$. By (H3), $m-t\ge0$. Thus, $m-t\ge m-s$,
and so $0<t\le s$. Then, $(m-t)$ is in $[m-s,m)$. By (H5), $m-t=2\pmod 4$.
Then $t$ is odd, so $2t=2\pmod 4$. Thus, $m+t=(m-t)+2t=0\pmod4$. Further,
$m+t$ lies in the interval $(m,m+s]$, so by (H5), $D_{ij}=0\pmod 4$. We
conclude that $D_{ij}D_{ji}=0\pmod 8$.
Thus, $\det(D)=1$ by Lemma~\ref{Dlemma}.

Now we verify the first claim.
Consider a nonzero entry in the leftmost $m$ columns of~$Y$,
say $e=Y_{ri}\ne 0$, where $i\le m$. To clear this entry, we subtract $e$ times the $i^{th}$
row of $X$ from the $r^{th}$ row of~$Y$.  Let $Y'$ denote the new matrix, thus
$Y'_{r's}=Y_{r's}$ if $r'\ne r$ and
$$Y_{rs}' = Y_{rs} - e X_{is},\qquad e=Y_{ri}.$$
We must check that if the hypotheses hold for $X$ and $Y$ then they also hold for $X$ and $Y'$.
The hypotheses will certainly hold for $Y_{rs}'$ if $eX_{is}=0$, so we may assume
$e X_{is}\ne0$.

Let $k=i-r$, and note that $k<i\le m$. We have $e=Y_{r,r+k}\ne0$. By (H3), $k\ge0$.
Since $0\le k < m$ and $k+r=i\le m$, (H4) and (H5) imply one of the following holds:
\begin{equation}
\label{kConditions}
\text{$0 \le k < m$, $4|k$, $4|e$\qquad  {\it or}} \qquad
 \text{$m-s\le k < m$, $k=2$ mod 4, $e$ is even.}
\end{equation}

Let $k'=s-r$. The equation $Y'_{rs}=Y_{rs}-eX_{is}$  can be rewritten as
$$Y_{r,r+k'}' = Y_{r,r+k'} - e X_{i,i+k'-k},\qquad e=Y_{r,r+k}.$$
Since $X_{is}=X_{i,i+k'-k}$, and we may assume this is non-zero, we have by (H2),
\begin{equation}
\label{kprime}
k'-k\in ([0,n-s)\cap4\Z)\cup([n-s,n)\cap2\Z)\cup \{n\}.
\end{equation}
Now we check the hypotheses (H1), (H3), (H4), and (H5) for $Y'$.

{\it Verification of (H1):  Is $Y_{r,r+m}'=1$?}  Equations~(\ref{kConditions}) and~(\ref{kprime})
cannot both hold when $k'=m$, therefore $Y'_{r,r+m}=Y_{r,r+m}=1$.

{\it Verification of (H3):} First we show $Y_{rj}'=0$ if $j<r$. Since $k=i-r\in[0,m)$,
we see $j<r\le i$, and so $X_{ij}=0$.  Then $Y_{rj}'=Y_{rj}=0$.  Next, we show $Y'_{rj}$
is even when $j\ne m+r$. This is because $Y_{rj}'=Y_{rj}-eX_{ij}$, $e$ is even, and
$Y_{rj}$ is even.

{\it Verification of (H4):} Let $0 \le k' < m - s$. Then $k'-k<m-s$, so $k'=k\pmod 4$
and $k\le k'<m-s$ by (\ref{kprime}). By~(\ref{kConditions}), $4|k$ and $4|e$.
Since $k'=k\pmod 4$, $4|k'$. Then
$Y'_{r,r+k'}\equiv Y_{r,r+k'}\equiv 0\pmod 4$, as required.

{\it Verification of (H5):} Let $m-s \le k' < m + n - 2s$ and $k'\ne m$.
We will show (H5) holds for $Y'_{r,r+k'}$.
Since $Y'_{r,r+k'}=Y_{r,r+k'}-eX_{i,i+k'-k}$
and (H5) holds for $Y_{r,r+k'}$, it suffices to show
\begin{equation}
\label{eX}
eX_{i,i+k'-k}=\begin{cases}0\pmod2& \text{if $k'=2\pmod 4$,}\\
0\pmod4&\text{if $k'=0\pmod 4$, or if $k'$ is odd and $r+k'>m$,} \\ 0\pmod 8
& \text{if $k'$ is odd and $r+k'\le m$.}
\end{cases}
\end{equation}
This is certainly true when $k'=2\pmod 4$ since $e$ is always even, so assume $k'\ne2\pmod 4$.
We claim $4|k$. If not, then by (\ref{kConditions}), $k=2\pmod 4$ and $k\ge m-s$, so
$k'-k<(m+n-2s)-(m-s)\le n-s$. By~(\ref{kprime}), $k'-k\in [0,n-s)\cap4\Z$.
So $k'=k=2\pmod4$, contradicting our assumption that
$k'\ne 2\pmod4$. This proves the claim that $4|k$. By (\ref{kConditions}), $4|e$. Thus, (\ref{eX})
holds except possibly when $k'$ is odd and $r+k'\le m$. By~(\ref{kConditions}) and~(\ref{kprime}),
$k'$ odd implies $k'-k=n$, in which case $r+k'>m$. This proves (H5).
\end{proof}


TITLE: Flow of electrons in an open circuit
QUESTION [0 upvotes]: In a closed circuit, electrons flow from negative electrode to positive electrode.
In an open circuit, electrons only flow up to the end of the circuit.
Why don't the electrons keep flowing into the vacuum until the negative electrode on the battery drains off electrons ?

REPLY [0 votes]: in an open circuit electrons do not flow like in closed.
If electrons leap out in space battery will get positively charged and will prevent electron from escaping. in closed circuit there is no net charge on battery.