TITLE: How to prove that $\sum_{n_j\ge i-1}[n_j-(i-1)]-\sum_{n_j\ge i}(n_j-i)= \max\{j: n_j\ge i\}$
QUESTION [2 upvotes]: Let $n_1\ge n_2\ge...\ge n_m$ so that $n_j\in \mathbb Z^{+}$  $\forall 1\le j \le m$ and let $i\in \mathbb Z^{+}$. Prove that:
$$\sum_{n_j\ge i-1}[n_j-(i-1)]-\sum_{n_j\ge i}(n_j-i)= \max\{j: n_j\ge i\}$$
What I did: Let $n_j-(i-1)=k$ then: $$\begin{align} \sum_{n_j\ge i-1}[n_j-(i-1)]-\sum_{n_j\ge i}(n_j-i) & = \sum_{k\ge 0}k-\sum_{k\ge 1}(k-1)\\ & = \sum_{k\ge 1}k-\sum_{k\ge 1}(k-1)\\ & = \sum_{k\ge 1}k-(k-1)\\ & = \sum_{k\ge 1}1 \\ & = \sum_{n_j\ge i}1 \end{align}$$
But I don´t know if this is correct; if so does that mean that $$\sum_{n_j\ge i}1=\max\{j: n_j\ge i \}?$$
I would really appreciate your help :)

REPLY [3 votes]: Your proof is almost correct. It is just that $k$ depends on $j$ and so you cannot write
just $k$ because then it looks like you sum together first positive (nonnegative) integers.
But one can think as follows: if there exists $n_j$ such that $n_j=i-1$, then in the sum
$$ \sum_{n_j\geq i-1}[n_j-(i-1)] $$
the first term is zero, if there is no $n_j$ equal to $i-1$, then
$$ \sum_{n_j\geq i-1}[n_j-(i-1)]=\sum_{n_j\geq i}[n_j-(i-1)]. $$
Hence, the LHS is actually
$$ \sum_{n_j\geq i}\bigl([n_j-(i-1)]-(n_j-i)\bigr)=\sum_{n_j\geq i}1. $$
Note that RHS in this last equality counts how many $n_j$ are greater or equal to $i$.
Since $n_1\geq n_2\geq \cdots \geq n_m$ the number of those $n_j$ which are greater or equal to $i$ is precisely the maximal $j$ such that $n_j\geq i$.


text:
\begin{document}
\begin{center}
{\rm {\LARGE On lifting modules \\
which do not satisfy the finite internal exchange property}}
\end{center}
\vsp

\begin{center}
{\rm {\Large  Yoshiharu Shibata}}\\
Graduate School of Sciences and Technology for Innovation,
Yamaguchi University,\\
1677-1 Yoshida, Yamaguchi, 753-8512, Japan\\
e-mail: b003wb@yamaguchi-u.ac.jp
\end{center}

\vsp

\begin{center}
{\large {\bf Abstract}}
\end{center}

A module $M$ is said to be {\it lifting} if,
for any submodule $N$ of $M$,
there exists a direct summand $X$ of $M$ contained in $N$
such that $N/X$ is small in $M/X$.
A module $M$ is said to satisfy
the {\it finite internal exchange property} if,
for any direct summand $X$ of $M$ and
any finite direct sum decomposition $M = \bigoplus_{i = 1}^n M_i$,
there exists $M_i' \subseteq M_i$ $(i = 1, 2, \ldots, n)$ such that
$M = X \oplus (\bigoplus_{i = 1}^n M_i')$.
In this paper, we consider the open problem:
does any lifting module satisfy
the finite internal exchange property?
We give characterizations for
the square of a hollow and uniform module
to be lifting,
and solve the above problem negatively
as an application of this result.

\footnote[0]{$2010$ Mathematics Subject Classification{\rm :}
Primary  16D40, ; Secondary 16D70. \\
\hspace{5mm}
Key Words{\rm:} lifting modules, extending modules, finite internal exchange property.}

\section{Preliminaries}

Throughout this paper, $R$ is a ring with identity and
modules are unitary right $R$-modules.
Let $M$ be a module and $N, K$ submodules of $M$ with $K \subseteq N$.
$N$ is said to be {\it small} in $M$ (or a {\it small submodule} of $M$)
if $N + X \neq M$ for any proper submodule $X$ of $M$
and we denote by $N \ll M$ in this case.
A pair $(Q, f)$ of a module $Q$ and an epimorphism $f : Q \to M$
be a {\it small cover} of $M$ if $\Ker f \ll Q$.
$K$ is said to be a {\it coessential submodule} of $N$ in $M$ if
$N/K \ll M/K$
and we write $K \coess N$ in $M$ in this case.

A module $M$ is said to satisfy the {\it finite internal exchange property}
(or briefly, {\it FIEP}) if, for any direct summand $X$ of $M$ and
any finite direct sum decomposition $M = \bigoplus_{i = 1}^n M_i$,
there exists $M_i' \subseteq M_i$ $(i = 1, 2, \ldots, n)$ such that
$M = X \oplus (\bigoplus_{i = 1}^n M_i')$.
Let $M = A \oplus B$ be a module
and $h : A \to B$ a homomorphism.
Then $\{a + h(a) \ | \ a \in A\}$
is called a {\it graph} of $h$ and denoted by $\graph{h}$.
It is clear that $M = \graph{h} \oplus B$,
$M = A + \graph{h}$ if $h$ is an epimorphism, and $A \cap \graph{h} = \Ker h$.

A module $M$ is said to be {\it extending} (or {\it CS}) if,
for any submodule $N$ of $M$,
there exists a direct summand $X$ of $M$
such that $N$ is an essential submodule of $X$.
An indecomposable extending module is called {\it uniform}.
A lifting module is defined as a dual concept of an extending module,
that is, a module $M$ is said to be {\it lifting} if,
for any submodule $N$ of $M$,
there exists a direct summand $X$ of $M$
such that $X$ is a coessential submodule of $N$ in $M$.
An indecomposable lifting module is called {\it hollow}.
It is well-known that uniform modules (hollow modules, resp.)
are closed under nonzero submodules and essential extensions
(nonzero factor modules and small covers, resp.).
A module $M$ is said to be {\it uniserial} if
its submodules are linearly ordered by inclusion.
Clearly, any uniserial module is hollow and uniform.
However the converse is not true.
We consider
\[
	R = \left(\begin{array}{@{\,}cccc@{\,}}
			K & K & K & K \\
			0 & K & 0 & K \\
			0 & 0 & K & K \\
			0 & 0 & 0 & K
	\end{array}\right), \quad
	M_R = (K, K, K, K)
\]
where $K$ is a field.
Then $M$ has only $6$ submodules
\[
	M, \ (0, K, K, K), \ (0, K, 0, K), \ (0, 0, K, K), \ (0, 0, 0, K), \ 0.
\]
Hence $M$ is hollow and uniform but not uniserial.

Extending modules and lifting modules are important
because they characterize right noetherian rings,
right perfect rings,
semiperfect rings, right (co-)H-rings and
Nakayama rings (cf. \cite{BO}).

Let $A$ and $B$ be modules.
$A$ is called {\it generalized $B$-injective} if,
ffor any module $X$,
any homomorphism $f : X \to A$
and any monomorphism $g : X \to B$,
there exist direct sum decompositions
$A = A_1 \oplus A_2$ and $B = B_1 \oplus B_2$,
a homomorphism $h_1 : B_1 \to A_1$ and a monomorphism $h_2 : A_2 \to B_2$
such that $p_1f = h_1q_1g$ and $q_2g = h_2p_2f$,
where $p_i : A = A_1 \oplus A_2 \to A_i$,
$q_i : B = B_1 \oplus B_2 \to B_i$ $(i = 1, 2)$ are canonical projections (\cite{HKO}).
$A$ is called {\it generalized $B$-projective} if,
for any module $X$,
any homomorphism $f : A \to X$
and any epimorphism $g : B \to X$,
there exist direct sum decompositions
$A = A_1 \oplus A_2$ and $B = B_1 \oplus B_2$,
a homomorphism $h_1 : A_1 \to B_1$ and an epimorphism $h_2 : B_2 \to A_2$
such that $f|_{A_1} = gh_1$ and $g|_{B_2} = fh_2$.
It is already known that,
a finite direct sum of lifting modules (extending modules, resp.)
 with the FIEP $M = \bigoplus_{i = 1}^n M_i$ is
 lifting (extending, resp.) with the FIEP if and only if
$K$ and $L$ are
relative generalized projective
(relative generalized injective, resp.)
for every $k = 1, 2, \ldots, n$,
any direct summand $K$ of $M_k$ and
any direct summand $L$ of $\bigoplus_{i \neq k} M_i$
by \cite[Theorem 3.7]{K1} (\cite[Theorem 2.15]{HKO}, resp.).

In this paper, we consider the open problem:
does any lifting module satisfy
the finite internal exchange property?
By certain projectivities (injectivities),
we give characterizations for
the square of a hollow and uniform module
to be a lifting module (an extending module)
which does not necessarily satisfy the FIEP.
Using this result, we give an example of a lifting module
not satisfying the FIEP
in order to solve the above problem negatively.

For undefined terminologies, the reader is referred to
\cite{AF}, \cite{BO}, \cite{CLVW}, \cite{MM} and \cite{Wi}.

\section{Main results}

\begin{lem}\label{hollowlemma}
	Let $A$ and $B$ be modules and put $M = A \oplus B$.
    For any nonzero proper direct summand $X$ of $M$, the following holds:
	\begin{itemize}
    	\item[(1)]	If $A$ and $B$ are hollow, then so is $X$.
        \item[(2)]	If $A$ and $B$ are uniform, then so is $X$.
    \end{itemize}
\end{lem}

\begin{proof}
	Let $p : M = A \oplus B \to A$ and $q : M = A \oplus B \to B$
    be canonical projections.

	(1) Since $A$ and $B$ are hollow and $X$ is non-small,
    	$X$ satisfies either $p(X) = A$ or $q(X) = B$.
        Without loss of generality, we can take $X$ with $p(X) = A$.
        By $X \neq M$,
        we see $X \cap B \ll B$ because $B$ is hollow.
        Since $X$ is a proper direct summand of $M$,
        we obtain $\Ker p|_X = X \cap B \ll X$.
        Hence $(X, p|_X)$ is a small cover of $A$.
        Therefore $X$ is hollow.

    (2) Since $A$ and $B$ are uniform and $X$ is non-essential,
    	$X$ satisfies either $X \cap A = 0$ or $X \cap B = 0$.
        Without loss of generality, we can take $X$ with $X \cap A = 0$.
        Then $q|_X : X \to B$ is a nonzero monomorphism.
        Therefore $X$ is uniform because
        it is isomorphic to a submodule of a uniform module $B$.
\end{proof}

Here we give a key lemma in this paper.

\begin{lem}\label{graphlemma}
	Let $U$ be a hollow and uniform module
    and put $M = U^2$, $U_1 = U \times 0$ and $U_2 = 0 \times U$.
    Then for any submodule $N_1$ of $U_1$ and
    any epimorphism $h_1$ from $N_1$ to $U_2$,
    $\langle h_1 \rangle$ is a direct summand of $M$.
\end{lem}

\begin{proof}
    If $N_1 = U_1$ or $\Ker h_1 = 0$,
    it is clear $M = \langle h_1 \rangle \oplus U_2$
    or $M = \langle h_1 \rangle \oplus U_1$.
    We assume $N_1 \neq U_1$ and $\Ker h_1 \neq 0$,
    and take a submodule $N_2$ of $U_2$
    which is a natural isomorphic image of $N_1$ and
    an epimorphism $h_2$ from $N_2$ to $U_1$.
    Now we prove $M = \langle h_1 \rangle \oplus \langle h_2 \rangle$.

    First we show $M = \langle h_1 \rangle + \langle h_2 \rangle$.
    Let $\iota_i : h_i^{-1}(N_j) \to U_i$ $(i \neq j)$
    be the inclusion mapping.
    Then $\image \iota_i = h_i^{-1}(N_j) \subseteq h_i^{-1}(U_j)
    = N_i \subsetneq U_i$
    $(i \neq j)$.
    We define a homomorphism $h_i'$ from $h_i^{-1}(N_j)$ to $U_i$
    by $h_i'(x) = h_jh_i(x)$ for $x \in h_i^{-1}(N_j)$ $(i \neq j)$.
    Then $h_i'$ is onto $(i = 1, 2)$.
    Since $U_i$ is hollow,
    we obtain that $\iota_i - h_i' : h_i^{-1}(N_j) \to U_i$ is onto
    $(i \neq j)$.
    For any element $u_1 + u_2$ of $M$ $(u_i \in U_i)$,
    there exists an element $x_i$ of $h_i^{-1}(N_j)$ such that
    $(\iota_i - h_i')(x_i) = u_i$ $(i \neq j)$.
    Hence
    \begin{align*}
    	u_1 + u_2 	&= ((x_1 - h_2(x_2)) + h_1(x_1 - h_2(x_2)))
        			+ ((x_2 - h_1(x_1)) + h_2(x_2 - h_1(x_1))) \\
	    &\in \langle h_1 \rangle + \langle h_2 \rangle.
    \end{align*}
    Therefore  $M = \langle h_1 \rangle + \langle h_2 \rangle$.

    Next we show $\langle h_1 \rangle \cap \langle h_2 \rangle = 0$.
    We see
    \[
    	(\langle h_1 \rangle \cap \langle h_2 \rangle) \cap \Ker h_1
    	= (\langle h_1 \rangle \cap \langle h_2 \rangle)
        		\cap (\langle h_1 \rangle \cap N_1)
        \subseteq \langle h_2 \rangle \cap N_1 = 0.
    \]
	Since $\langle h_1 \rangle \cong N_1$ is uniform and $\Ker h_1 \neq 0$,
    we obtain $\langle h_1 \rangle \cap \langle h_2 \rangle = 0$.
\end{proof}

The following is one of our main results.

\begin{thm}\label{lifting}
	Let $U$ be a hollow and uniform module
    and  put $M = U^2$, $U_1 = U \times 0$ and $U_2 = 0 \times U$.
    Then the following conditions are equivalent:
    \begin{itemize}
    	\item[(a)]	$M$ is lifting,
    	\item[(b)]	for any module $X$,
        			any homomorphism $f : U_1 \to X$
        			and any epimorphism $g : U_2 \to X$,                     one of the following holds:
                    \begin{itemize}
				    	\item[(i)]	there exists a homomorphism
                        			$h : U_1 \to U_2$
				        			such that $f = gh$,
				        \item[(ii)]	there exist a submodule $N$ of $U_2$
                        			and an epimorphism $h : N \to U_1$
                                    such that $g|_N = fh$,
   					\end{itemize}
        \item[(c)]	for any module $X$,
        			any homomorphism $f : U_1 \to X$
        			and any epimorphism $g : U_2 \to X$,
                    one of the following holds:
                    \begin{itemize}
				    	\item[(i)]	there exists a homomorphism
                        			$h : U_1 \to U_2$
				        			such that $f = gh$,
				        \item[(ii)] there exist a submodule $K$ of $\Ker g$									 and a monomorphism $h : U_1 \to U_2/K$
                                     such that $g'h = f$, where
                                     $g' : U_2/K \to X$ is defined by
                                     $g'(\overline{u}) = g(u)$
                                     for $\overline{u} \in U_2/K$.
   					\end{itemize}
    \end{itemize}
\end{thm}

\begin{proof}
    Let $p_i : M = U_1 \oplus U_2 \to U_i$
    be the canonical projection ($i = 1, 2$).

    (a) $\Rightarrow$ (b):
    Let $f : U_1 \to X$ be a nonzero homomorphism and
    $g : U_2 \to X$ an epimorphism.
    We define a homomorphism $\varphi : M \to X$
    by $\varphi(u_1 + u_2) = f(u_1) - g(u_2)$
    for $u_i \in U_i$ $(i = 1, 2)$.
    Since $M$ is lifting, there exists a direct summand $A$ of $M$
    such that $A \coess \Ker \varphi$ in $M$.
    Then $M = \Ker \varphi + U_2 = A + U_2$ because $g$ is onto.
    So $p_1(A) = U_1$.

    If $A \cap U_2 = 0$,
    we can define a homomorphism $h : U_1 = p_1(A) \to U_2$
    by $h(p_1(a)) = p_2(a)$ for $a \in A$, and
    $h$ satisfies $f = gh$.
    Therefore (i) holds.

    Otherwise we see $A \cap U_1 = 0$ since $U$ is uniform.
    Hence we can define an epimorphism
    $h : p_2(A) \to p_1(A) = U_1$ by $h(p_2(a)) = p_1(a)$ for $a \in A$,
    and $h$ satisfies $g|_{p_2(A)} = fh$.
    Therefore (ii) holds.

    (b) $\Rightarrow$ (a):
	Let $X$ be a submodule of $M$.
    We may assume that $X$ is a proper non-small submodule of $M$.
    Since $U_1$ and $U_2$ are hollow with $U_1 \cong U_2$,
    we only consider the case $p_1(X) = U_1$.
    Then $M = X + U_2$.
    Let $\pi : M \to M/X$ be the natural epimorphism.
    Since $\pi|_{U_2}$ is onto,
	one of the following (i) or (ii) holds:
    \begin{itemize}
    	\item[(i)]	there exists a homomorphism $h : U_1 \to U_2$
        				such that $\pi|_{U_1} = \pi|_{U_2}h$,
        \item[(ii)]	there exist a submodule $N$ of $U_2$ and
        				an epimorphism $h : N \to U_1$ such that
                        $\pi|_N = \pi|_{U_1}h$.
    \end{itemize}
    In either case, we see
    $\graph{-h}$ is a direct summand of $M$ by Lemma \ref{graphlemma},
    and $\graph{-h} \subseteq X$ by the commutativity of the diagram.
    Put $M = \graph{-h} \oplus T$ using a direct summand $T$ of $M$.
    Since $T$ is hollow by Lemma \ref{hollowlemma},
    we obtain $T \cap X \ll T$.
    Hence $\graph{-h} \coess X$ in $M$.
    Therefore $M$ is lifting.

    (b) $\Rightarrow$ (c):
    It is enough to show (b)(ii) $\Rightarrow$ (c)(ii).
    For any homomorphism $f : U_1 \to X$ and
    any epimorphism $g : U_2 \to X$,
    we assume that
    there exist a submodule $N$ of $U_2$ and
    an epimorphism $h : N \to U_1$
    such that $g|_N = fh$.
    Then $\Ker h \subseteq \Ker g$,
    hence we can define an epimorphism $g' : U_2/\Ker h \to X$
    by $g'(\overline{u}) = g(u)$ for $\overline{u} \in U_2/\Ker h$.
    Let $\overline{h} : N/\Ker h \to U_1$ be the natural isomorphism
    and $\iota : N/\Ker h \to U_2/\Ker h$ the inclusion mapping,
    and put $h' = \iota \overline{h}{}^{-1}$.
    Clearly, $h'$ is a monomorphism and $g'h' = f$.

    (c) $\Rightarrow$ (b):
    We show (c)(ii) $\Rightarrow$ (b)(ii).
    For any homomorphism $f : U_1 \to X$ and
    any epimorphism $g : U_2 \to X$,
    we assume that
    there exist a submodule $K$ of $\Ker g$
    and a monomorphism $h : U_1 \to U_2/K$
    such that $f = g'h$,
    where $g' : U_2/K \to X$ is defined
    by $g'(\overline{u}) = g(u)$ for $\overline{u} \in U_2/\Ker h$.
    We express $\image h = N/K$.
    Let $\varphi : N/K \to U_1$ be the inverse map of $h$ and
    $\pi : N \to N/K$ the natural epimorphism,
    and put $h' = \varphi \pi$.
    Then $h'$ is onto and $g|_N = fh'$.
\end{proof}

\begin{thm}\label{extending}
	Let $U$ be a uniform and hollow module
    and put $M = U^2$, $U_1 = U \times 0$ and $U_2 = 0 \times U$.
    Then the following conditions are equivalent:
    \begin{itemize}
    	\item[(a)]	$M$ is extending,
        \item[(b)] 	for any module $X$,
        			any homomorphism $f : X \to U_2$ and
        			any monomorphism $g : X \to U_1$,
				    one of the following holds:
				    \begin{itemize}
				    	\item[(i)]	there exists a homomorphism
                        			$h : U_1 \to U_2$ such that $f = hg$,
				        \item[(ii)]	there exist a submodule $K$ of $U_1$
                        			and a monomorphism $h : U_2 \to U_1/K$
                                    such that $hf = \pi g$,
                                    where $\pi$ is the natural epimorphism
                                    from $U_1$ to $U_1/K$,
    				\end{itemize}
        \item[(c)]	for any module $X$,
        			any homomorphism $f : X \to U_2$ and
        			any monomorphism $g : X \to U_1$,
				    one of the following holds:
				    \begin{itemize}
				    	\item[(i)]	there exists a homomorphism
                        			$h : U_1 \to U_2$ such that $f = hg$,
				        \item[(ii)]	there exist a submodule $N$ of $U_1$
                        			containing $\image g$ and
				        			an epimorphism $h : N \to U_2$
                                    such that $f = hg$.
    				\end{itemize}
    \end{itemize}
\end{thm}

\begin{proof}
    Let $p_i : M = U_1 \oplus U_2 \to U_i$
    be the canonical projection ($i = 1, 2$).

    (a) $\Rightarrow$ (c):
    Let $f : X \to U_2$ be a nonzero homomorphism and
    $g : X \to U_1$ a monomorphism.
    We define a homomorphism $\varphi : X \to M$
    by $\varphi(x) = g(x) + f(x)$ for $x \in X$.
    Since $M$ is extending,
    there exists a direct summand $A$ of $M$
    such that $\image \varphi \ess A$.
    By $\image \varphi \cap U_2 = 0$, $A \cap U_2 = 0$.

    If $p_1(A) = U_1$,
    we can define a homomorphism $h : U_1 = p_1(A) \to U_2$
    by $h(p_1(a)) = p_2(a)$ for $a \in A$,
    and $h$ satisfies $f = hg$.
    Therefore (i) holds.

    Otherwise, we see $p_2(A) = U_2$ since $U$ is hollow.
    We see $\image g \subseteq p_1(A)$, and
    we can define an epimorphism
    $h : p_1(A) \to p_2(A) = U_2$ by $h(p_1(a)) = p_2(a)$ for $a \in A$.
    Then $h$ satisfies $f = hg$.
    Therefore (ii) holds.

	(c) $\Rightarrow$ (a):
    Let $X$ be a submodule of $M$.
    We may assume that
    $X$ is a nonzero non-essential submodule of $M$.
    Since $U_1$ and $U_2$ are uniform with $U_1 \cong U_2$, ,
	we only consider the case $X \cap U_2 = 0$ because $U$ is uniform.
    Since $p_1|_X$ is a monomorphism,
	one of the following (i) or (ii) holds:
    \begin{itemize}
    	\item[(i)]	there exists a homomorphism $h : U_1 \to U_2$
        				such that $p_2|_X = hp_1|_X$.
        \item[(ii)]	there exist a submodule $N$ of $U_1$
				        containing $p_1(X)$ and
        				an epimorphism $h : N \to U_2$ such that
                        $p_2|_X = hp_1|_X$.
    \end{itemize}
    In either case,
    $\graph{h}$ is a direct summand of $M$ by Lemma \ref{graphlemma},
    and $X \subseteq \graph{h}$ by commutativity of the diagram.
    Since $\graph{h}$ is uniform by Lemma \ref{hollowlemma},
    we obtain $X \ess \graph{h}$.
    Therefore $M$ is extending.

	(c) $\Rightarrow$ (b):
    It is enough to show (c)(ii) $\Rightarrow$ (b)(ii).
    For any homomorphism $f : X \to U_2$ and
    any monomorphism $g : X \to U_1$,
    we assume that
    there exist a submodule $N$ of $U_1$ containing $\image g$ and
    an epimorphism $h : N \to U_2$ such that $f = hg$.
    Let $\overline{h} : N/\Ker h \to U_2$ be the natural isomorphism
    and $\iota : N/\Ker h \to U_1/\Ker h$ the inclusion mapping,
    and put $h' = \iota \overline{h}{}^{-1}$.
    Then $h'$ is a monomorphism and $h'f = \pi g$, where
    $\pi : U_1 \to U_1/\Ker h$ is the natural epimorphism.

    (b) $\Rightarrow$ (c):
    We show (b)(ii) $\Rightarrow$ (c)(ii).
    For any homomorphism $f : X \to U_2$ and
    any monomorphism $g : X \to U_1$,
    we assume that there exist a submodule $K$ of $U_1$
    and a monomorphism $h : U_2 \to U_1/K$
    such that $hf = \pi g$,
    where $\pi : U_1 \to U_1/K$ is the natural epimorphism.
    We express $\image h = N/K$.
    Let $\varphi : N/K \to U_2$ be the inverse map of $h$
    and $\eta : N \to N/K$ the natural epimorphism,
    and put $h' = \varphi \eta$.
    Then we see $\image g \subseteq N$,
    $h'$ is an epimorphism and $f = h'g$.
\end{proof}

\begin{rem}
	In Theorem \ref{extending},
    the assumption ``hollow'' cannot be removed.
    In fact, $U_\ZZ = \ZZ$ is uniform and $U^2$ is extending.
    However it does not hold neither (i) nor (ii)
    in Theorem \ref{extending} (b)
    for a homomorphism $f : 2\ZZ \to U$ defined by $f(2n) = 3n$
    and the inclusion mapping $g : 2\ZZ \to U$.
\end{rem}

Lifting modules do not necessarily satisfy the FIEP.
We can make an example of a lifting module without the FIEP,
using Theorem \ref{lifting}.

\begin{exam}
    Let $\ZZ_{(p)}$ and $\ZZ_{(q)}$ be the localizations of $\ZZ$
    at two distinct prime numbers $p$ and $q$ respectively.
    We consider a semiperfect ring
    $R = \left(\begin{array}{@{\,}cc@{\,}}
				\ZZ_{(p)} & \QQ \\
				0 & \ZZ_{(q)}
		\end{array}\right)$
    and its right ideal
    $L = \left(\begin{array}{@{\,}cc@{\,}}
				0 & \ZZ_{(q)} \\
				0 & \ZZ_{(q)}
		\end{array}\right)$,
    and put $U_R = R/L$.
    Then $U$ is uniserial
    whose the endomorphism ring is not local (see. \cite{FS}).
    According to \cite[Proposition 12.10]{AF},
    $U^2$ does not satisfy the FIEP.
    We show $U^2$ is lifting.
    For any nonzero homomorphism $f : U \to U/X$
    where $X$ is a submodule of $U$,
    we can take
    \[
    	f(\overline{\left(\begin{array}{@{\,}cc@{\,}}
				1 & 0 \\
				0 & 0
			\end{array}\right)})
        = \overline{\left(\begin{array}{@{\,}cc@{\,}}
				x & 0 \\
				0 & 0
			\end{array}\right)} + X
        \quad (x \in \ZZ_{(p)})
    \]
    If $x \in \ZZ_{(q)}$,
    we can define a homomorphism $h : U \to U$ with
    $h(\overline{\left(\begin{array}{@{\,}cc@{\,}}
				1 & 0 \\
				0 & 0
			\end{array}\right)})
        = \overline{\left(\begin{array}{@{\,}cc@{\,}}
				x & 0 \\
				0 & 0
			\end{array}\right)}$,
    and $h$ satisfies $\pi h = f$,
    where $\pi$ is the natural epimorphism from $U$ to $U/X$.
    Otherwise we can express $x = p^m \frac{1}{q^n} \frac{t}{s}$,
    where $m \in \NN \cup \{0\}$, $n \in \NN$ and
    $s, t \in \ZZ \setminus (p\ZZ \cup q\ZZ$).
    Put $N = \overline{\left(\begin{array}{@{\,}cc@{\,}}
				p^m & 0 \\
				0 & 0
			\end{array}\right)}R$.
    We can define an epimorphism
    $h : N =  \to U$
    with $h(\overline{\left(\begin{array}{@{\,}cc@{\,}}
				p^m & 0 \\
				0 & 0
			\end{array}\right)})
        = \overline{\left(\begin{array}{@{\,}cc@{\,}}
				q^n \frac{s}{t} & 0 \\
				0 & 0
			\end{array}\right)}$,
    and $h$ satisfies $fh = \pi |_N$,
    where $\pi$ is the natural epimorphism from $U$ to $U/X$.
    Therefore $U^2$ is lifting by Theorem \ref{lifting}.
\end{exam}

\section*{Acknowledgements}
The author would like to thank Professors Yosuke Kuratomi and
Isao Kikumasa for valuable comments.

config: arxiv


TITLE: Prove if $f$ is a concave function, then $f\left(\frac{ax_1+bx_2+cx_3}{a+b+c}\right)\geq \frac{af(x_1)+bf(x_2)+cf(x_3)}{a+b+c}.$
QUESTION [0 upvotes]: The question is

Prove: If $f$ is a concave function, then $$f\left(\frac{ax_1+bx_2+cx_3}{a+b+c}\right)\geq \frac{af(x_1)+bf(x_2)+cf(x_3)}{a+b+c},$$
where $a,b,c$ are positive numbers and $x_1,x_2,x_3$ are any points in the domain.

My attempt is:
The case if more than one point is equal can be proven using definition. So WLOG, assume that $x_1<x_2<x_3$, then $x_2=tx_1+(1-t)x_2$, for some $t \in (0,1).$ After plugging this, we can group the terms $x_1$ and$ x_2$. The coefficients of $x_1$ and $x_2$ are $\frac{a+bt}{a+b+c}$ and $\frac{b(1-t)+c}{a+b+c}$. Then we can use the definition of a concave function to 'expand' into an inequality. For the terms $f(x_1),f(x_3)$, the coefficients are as desired, but the remaining term is $\frac{btf(x_1)+b(1-t)f(x_3)}{a+b+c}.$ I almost get the inequality, but the remaining term runs the inequality in an opposite direction ($\leq$).
May someone just give some comments (small tips is enough)? Thank you.

REPLY [1 votes]: If $f$ is a concave function, Jensen's inequality says that
$$f\left(\frac{\sum_i a_ix_i}{\sum_i a_i} \right) \ge \frac{\sum_i a_i f(x_i)}{\sum_i a_i}$$
Put $a_1 = a$, $a_2 = b$, $a_3 = c$ where the sum runs over $1\le i\le 3$.
Note: If $f$ is a convex function, Jensen's inequality reverses and now says that
$$f\left(\frac{\sum_i a_ix_i}{\sum_i a_i} \right) \le \frac{\sum_i a_i f(x_i)}{\sum_i a_i}$$


text:
\begin{document}

\title{Universal Coding on Infinite Alphabets:\\ Exponentially Decreasing Envelopes}

\author{Dominique~Bontemps
\thanks{D. Bontemps is PhD fellowship holder at Laboratoire de Math\'ematiques, Univ. Paris-Sud 11, Orsay, 91405 France.}

}

\maketitle

\begin{abstract}
This paper deals with the problem of universal lossless coding on a countable infinite alphabet. It focuses on some classes of sources defined by an envelope condition on the marginal distribution, namely exponentially decreasing envelope classes with exponent $\alpha$.

The minimax redundancy of exponentially decreasing envelope classes is proved to be equivalent to $\frac{1}{4 \alpha \log e} \log^2 n$. Then, an adaptive algorithm is proposed, whose maximum redundancy is equivalent to the minimax redundancy.
\end{abstract}

\begin{IEEEkeywords}
Data compression, universal coding, infinite countable alphabets, redundancy, Bayes mixture, adaptive compression.
\end{IEEEkeywords}

\IEEEpeerreviewmaketitle

\section{Introduction}

\IEEEPARstart{C}{ompression} of data is broadly used in our daily life: from the movies we watch to the office documents we produce. In this article, we are interested in lossless data compression on an unknown alphabet. This has applications in areas such as language modeling or lossless multimedia codecs.

First, we present briefly the problematics of data compression. More details are available in general textbooks, like \cite{eec_IEEE:cover_thomas_91}. Then we make a short review of preceding results, in which we situate the topic of this article, exponentially decreasing envelope classes, and we announce our results.

\subsection{Lossless data compression}

Consider a finite or countably infinite alphabet ${\mathcal X}$. A source on ${\mathcal X}$ is a probability distribution $\boldsymbol{P}$, on the set ${\mathcal X}^{\N}$ of infinite sequences of symbols from ${\mathcal X}$. Its marginal distributions are denoted by $P^n$, $n \geq 1$ (for $n=1$, we only note $P$). The scope of lossless data compression is to encode a sequence of symbols $X_{1:n}$, generated according to $P^n$, into a sequence of bits as small as possible. The algorithm has to be uniquely decodable.

The binary entropy $H(P^n) = \E_{P^n} [-\log_2 P^n(X_{1:n})]$ is known to be a lower bound for the expected codelength of $X_{1:n}$. From now on, $\log$ denotes the logarithm taken to base $2$, while $\ln$ is used to denote the natural logarithm. Since arithmetic coding based on $P^n$ encodes a message $x_{1:n}$ with $\lceil -\log P^n(x_{1:n})\rceil +1$ bits, this lower bound can be achieved within two bits. Then, the expected redundancy measures the mean number of extra bits, in addition to the entropy, a coding strategy uses to encode $X^n$. In the sequel, we use the word \emph{redundancy} instead of \emph{expected redundancy}.

Furthermore, together with Kraft-McMillan inequality, arithmetic coding provides an almost perfect correspondence between coding algorithms and probability distributions on ${\mathcal X}^{n}$. In this setting, if an algorithm is associated to the probability distribution $Q^n$, its expected redundancy reduces to the Kullbach-Liebler divergence between $P^n$ and $Q^n$
\[ D(P^n; Q^n) = \E_{P^n} \left[ \log \frac{P^n(X_{1:n})}{Q^n(X_{1:n})} \right]. \]
We call this quantity (expected) redundancy of the distribution $Q^n$ (with respect to $P^n$).

Unfortunately, the true statistics of the source are not known in general, but $P^n$ is supposed to belong to some large class of sources $\Lambda$ (for instance, the class of all iid sources, or the class of Markov sources). In this paper, the maximum redundancy
\[ R_n(Q^n; \Lambda) = \sup_{\boldsymbol{P} \in \Lambda} R_n(Q^n; P^n) \]
measures how well a coding probability $Q^n$ behave on an entire class $\Lambda$. With this point of view, the best coding probability is a \emph{minimax} coding probability, that achieves the \emph{minimax redundancy}
\[ R_n(\Lambda) = \inf_{Q^n} R_n(Q^n; \Lambda). \]

Another way to measure the ability of a class of sources to be efficiently encoded is the \emph{Bayes redundancy}
\[ R_{n,\mu}(\Lambda) = \inf_{Q^n} \int_{\Lambda} R_n(Q^n; P^n) \,\ud\mu(\boldsymbol{P}) \]
where $\mu$ is a prior distribution on $\Lambda$ endowed with the topology of weak convergence and the Borel $\sigma$-field. Only one coding strategy achieves the Bayes redundancy: the Bayes mixture
\begin{equation*}\label{eq:Mixture}
 M_{n,\mu}(x_{1:n}) = \int_{\Lambda} P^n(x_{1:n}) \,\ud\mu(\boldsymbol{P}).
\end{equation*}
When $\Lambda$ is a class of iid sources on the set ${\mathcal X}=\N_{*}=\N \backslash \{0\}$, there is a natural parametrization of $\Lambda$ by $P_{\boldsymbol{\theta}}(j) = \theta_j$, with $\boldsymbol{\theta} = (\theta_1, \theta_2, \ldots) \in \Theta_\Lambda$.  $\Theta_\Lambda$ is then a subset of
\[ \Theta = \left\{ \boldsymbol{\theta}=(\theta_1,\theta_2,\ldots) \in [0,1]^{\N}: \sum_{i\geq 1} \theta_i = 1 \right\} \]
and it is endowed with the topology of pointwise convergence. In this case we write $\mu$ as a prior on $\Theta_\Lambda$.

Minimax redundancy and Bayes redundancy are linked by an important relation \cite{eec_IEEE:Gallager68,eec_IEEE:DavissonLeonGarcia80}; it is written here in the context of iid sources on a finite or countably infinite alphabet, but Haussler \cite{eec_IEEE:haussler96general} has shown that it can be generalized for all classes of stationary ergodic processes on a complete separable metric space.
\begin{thm} \label{thm:MinimaxMaximin}
 Let $\Lambda$ be a class of iid sources, such that the parameter set $\Theta_{\Lambda}$ is a measurable subset of $\Theta$. Let $n\geq 1$. Then
 \[ R_n(\Lambda) = \sup_{\mu} R_{n,\mu}(\Lambda), \]
 where the supremum is taken over all (Borel) probability measures on $\Theta_{\Lambda}$.
\end{thm}
The quantity $\sup_{\mu} R_{n,\mu}(\Lambda)$ is called \emph{maximin redundancy}. A prior whose Bayes redundancy corresponds to the maximin redundancy is said to be maximin, or least favorable. \\
Theorem~\ref{thm:MinimaxMaximin} says that maximin redundancy and minimax redundancy are the same. It provides a tool to calculate the minimax redundancy.

Before speaking about known results, let us make mention of other two notions. \\
With an asymptotic point of view, a sequence of coding probabilities $(Q_n)_{n\geq 1}$ is said to be weakly universal if the per-symbol redundancy tends to $0$ on $\Lambda$: $\sup_{\boldsymbol{P} \in \Lambda} \lim_{n\rightarrow \infty} \frac{1}{n} D(P^n; Q^n) = 0$. \\
Instead of the expected redundancy, many authors
consider individual sequences. In this case, the \emph{minimax regret}
\[R_n^{*}(\Lambda) = \inf_{Q^n} \sup_{\boldsymbol{P}\in\Lambda} \sup_{x_{1:n}\in {\mathcal X}^n} \log \frac{P^n(x_{1:n})}{Q^n(x_{1:n})} \]
plays the role that the minimax redundancy plays with the expected redundancy.

\subsection{Exponentially decreasing envelope classes}

In the case of a finite alphabet of size $k$, many classes of sources have been studied in the literature, for which estimates of the redundancy have been provided. In particular we have the class of all iid sources (see \cite{eec_IEEE:Krichevsky81,eec_IEEE:XieB97,eec_IEEE:XieB00,eec_IEEE:BarronRissanenYu98,eec_IEEE:Catoni2001,eec_IEEE:DrmotaS04}, and references therein), whose minimax redundancy is
\[\frac{k-1}{2} \log \frac{n}{2\pi e} + \log \frac{\Gamma(1/2)^k}{\Gamma(k/2)} + o(1).\]
This last class can be seen as a particular case of a $(k-1)$-dimensional class of iid sources on a (possibly) bigger alphabet, for which we have a similar result under certain conditions (see \cite{eec_IEEE:ClarkeB90,eec_IEEE:ClarkeB94,eec_IEEE:Barron98}). Similar results are still available for classes of Markov processes and finite memory tree sources on a finite alphabet (see \cite{eec_IEEE:Krichevsky81,eec_IEEE:Davisson83,eec_IEEE:willems95contexttree,eec_IEEE:Atteson99}), and for $k$-dimensional classes of even non-iid sources on an arbitrary alphabet (see \cite{eec_IEEE:Rissanen84}). \\
The results become less precise when one considers infinite dimensional classes on a finite alphabet. A typical example is the class of renewal processes, for which we do not have an equivalent of the expected redundancy, but we know that it is lower and upper bounded by a constant times $\sqrt{n}$ (see \cite{eec_IEEE:CsiszarShields96,eec_IEEE:FlajoletS02}). \\
Eventually, it is well known that the class of stationary ergodic sources on a finite alphabet is weakly universal (see \cite{eec_IEEE:cover_thomas_91}). However, Shields \cite{eec_IEEE:Shields93} showed that this class does not admit non-trivial universal redundancy rates.

In the case of a countably infinite alphabet, the situation is significantly different. Even the class of all iid sources is not weakly universal (see \cite{eec_IEEE:Kieffer78,eec_IEEE:GyorfiPM94}). Kieffer characterized weakly universal classes in \cite{eec_IEEE:Kieffer78} (see also \cite{eec_IEEE:GyorfiPM93,eec_IEEE:GyorfiPM94}):
\begin{prop}
 A class $\Lambda$ of stationary sources on $\N_{*}$ is weakly universal if and only if there exists a probability distribution $Q$ on $\N_{*}$ such that for every $\boldsymbol{P} \in \Lambda$, $D(P; Q) < \infty$.
\end{prop}

In the literature, we find two main ways to deal with infinite alphabets. The first one \cite{eec_IEEE:OrlitskySZ04,eec_IEEE:OrlitskyS04,eec_IEEE:JevticOS05,eec_IEEE:OrlitskySVZ06,eec_IEEE:ShamirC04,eec_IEEE:ShamirDCC04,eec_IEEE:GemelosW06,eec_IEEE:Garivier06Pattern,eec_IEEE:ChoiSzpankowski07} separates the message into two parts: a description of the symbols appearing in the message, and the \emph{pattern} they form. Then the compression of patterns is studied.

A second approach \cite{eec_IEEE:Elias75,eec_IEEE:GyorfiPM93,eec_IEEE:HeY05,eec_IEEE:FosterSW02,eec_IEEE:BouGarGas06} studies collections of sources satisfying Kieffer's condition, and proposes compression algorithms for these classes. A result from \cite{eec_IEEE:BouGarGas06} indicates us such a way:
\begin{prop}
 Let $\Lambda$ be a class of iid sources over $\N_{*}$. Let the envelope function $f$ be defined by $f(x) = \sup_{\boldsymbol{P} \in \Lambda} P(x)$. Then the minimax regret verifies
 \[ R_n^{*}(\Lambda) < \infty \Leftrightarrow \sum_{x\in \N_{*}} f(x) < \infty. \]
\end{prop}

It is therefore quite natural to consider classes of iid sources with envelope conditions on the marginal distribution. In this article we study specific classes of iid sources introduced by \cite{eec_IEEE:BouGarGas06}, and called \emph{exponentially decreasing envelope classes}.
\begin{df}\label{def:ExpEnvClass}
   Let $C$ and $\alpha$ be positive numbers satisfying $C > e^{2\alpha}$. The exponentially decreasing envelope class $\Lambda_{C e^{-\alpha\cdot}}$ is the class of sources defined by
   \begin{equation*}
    \begin{split}
     \Lambda_{C e^{-\alpha\cdot}} &= \{ \boldsymbol{P}: \forall k \geq 1,\ P(k) \leq C e^{-\alpha k} \\
      & \qquad \text{and } \boldsymbol{P}\ \text{is stationary and memoryless.} \}
    \end{split}
   \end{equation*}
\end{df}
The first condition addresses mainly the queue of the distribution of $X_1$; it means that great numbers must be rare enough. It does not mean that the distribution is geometrical: if $C$ is big enough, many other distributions are possible. Furthermore we will see that the exact value of $C$ does not change significantly the minimax redundancy, unlike $\alpha$.

Since in this paper we are going to only talk about exponentially decreasing envelope classes, we simplify the notations $R_n(Q^n; \Lambda_{C e^{-\alpha\cdot}})$, $R_n(\Lambda_{C e^{-\alpha\cdot}})$, and $R_{n,\mu}(\Lambda_{C e^{-\alpha\cdot}})$ into $R_n(Q^n; C,\alpha)$, $R_n(C,\alpha)$, and $R_{n,\mu}(C,\alpha)$ respectively. The subset of $\Theta$ corresponding to $\Lambda_{C e^{-\alpha\cdot}}$ is denoted by
\begin{equation} \label{eq:ThetaCalpha}
 \begin{split}
  \Theta_{C,\alpha} &= \{ \boldsymbol{\theta}=(\theta_1,\theta_2,\ldots) \in [0,1]^{\N}: \\
   &\qquad \sum_{i\geq 1} \theta_i = 1\ \text{and } \forall i \geq 1,\ \theta_i \leq C e^{-\alpha i} \}.
 \end{split}
\end{equation}

We present two main results about these classes.

In Section~\ref{sec:MinimaxRedundancy} we calculate the minimax redundancy of exponentially decreasing envelope classes, and we find that it is equivalent to $\frac{1}{4 \alpha \log e} \log^2 n$ as $n$ tends to the infinity. This rate is interesting for two main reasons. Up to our knowledge, exponentially decreasing envelope classes are the first family of classes on an infinite alphabet for which an equivalent of the minimax redundancy is known. Then, even the rate is new: until now only rates in $\log n$ or $\sqrt{n}$ have been obtained.

Once the minimax redundancy of a class of sources is known, we are interested in finding a minimax coding algorithm. Section~\ref{sec:code} proposes a new adaptive coding algorithm, and we show that its maximum redundancy is equivalent to the minimax redundancy of exponentially decreasing envelope classes.

Eventually, the Appendix contains some proofs and some auxiliary results used in the main analysis.

\section{Minimax redundancy} \label{sec:MinimaxRedundancy}

In this section we state our main result. Theorem~\ref{thm:ExpClassRedundancy} below gives an equivalent of the minimax redundancy of exponentially decreasing envelope classes. To get it, we use a result due to Haussler and Opper \cite{eec_IEEE:HausslerOpper97}.

\begin{thm} \label{thm:ExpClassRedundancy}
 Let $C$ and $\alpha$ be positive numbers satisfying $C > e^{2 \alpha}$. The minimax redundancy of the exponentially decreasing envelope class $\Lambda_{C e^{-\alpha\cdot}}$ verifies
 \[ R_n(C,\alpha) \underset{n \rightarrow \infty}{\sim} \frac{1}{4 \alpha \log e} \log^2 n. \]
\end{thm}

Theorem~\ref{thm:ExpClassRedundancy} improves on a preceding result of \cite[Theorem~7]{eec_IEEE:BouGarGas06}. In that article the following bounds of the minimax redundancy of exponentially decreasing envelope classes are given:
\begin{equation*}
 \begin{split}
  &\frac{1}{8 \alpha \log e} \log^2 n\, (1+o(1)) \\
   &\qquad \leq R_n(C,\alpha) \\
   &\qquad \leq \frac{1}{2 \alpha \log e} \log^2 n + O(1).
 \end{split}
\end{equation*}

In subsection~\ref{sec:Haussler} we outline the work done in \cite{eec_IEEE:HausslerOpper97}, and then we use it in subsection~\ref{sec:EnvClassRedundancy} to prove Theorem~\ref{thm:ExpClassRedundancy}.
Eventually, we discuss in subsection~\ref{sec:PolyEnvClasses} the adaptation of this method to other envelope classes.

\subsection{From the metric entropy to the minimax redundancy} \label{sec:Haussler}

To study the redundancy of a class of sources, \cite{eec_IEEE:HausslerOpper97} considers the Hellinger distance between the first marginal distributions of each source. Bounds on the minimax redundancy are provided in terms of the metric entropy of the set of the first marginal distributions, with respect to the Hellinger distance. As a consequence, that method can be applied only to iid sources. However it is very efficient in the case of exponentially decreasing envelope classes.

First, we need to define the Hellinger distance and the metric entropy. In the case of sources on a countably infinite alphabet, the Hellinger distance can be defined in the following way:
\begin{df}
 Let $P$ and $Q$ two probability distributions on $\N_{*}$. Then the Hellinger distance between $P$ and $Q$ is defined by
 \[ h(P,Q) = \sqrt{ \sum_{k\geq 1} \left( \sqrt{P(k)} - \sqrt{Q(k)} \right)^2 }. \]
\end{df}

A related metric can be defined on the parameter set $\Theta$:
\[ d(\boldsymbol{\theta},\boldsymbol{\theta}') = h(P_{\boldsymbol{\theta}},P_{\boldsymbol{\theta}'}) = \sqrt{ \sum_{k\geq 1} \left( \sqrt{\theta_k} - \sqrt{\theta'_k} \right)^2 }. \]

From a metric we can define the \emph{metric entropy}. We need to define first some numbers.
\begin{df}
 Let $S$ be a subset of $\Theta$, and $\epsilon$ be a positive number.
 \begin{enumerate}
  \item We denote by ${\mathcal D}_{\epsilon}(S,d)$ the cardinality of the smallest finite partition of $S$ with sets of diameter at most $\epsilon$, or we set ${\mathcal D}_{\epsilon}(S,d)=\infty$ if no such finite partition exists.
  \item The metric entropy of $(S,d)$ is defined by
   \[ {\mathcal H}_{\epsilon}(S,d) = \ln {\mathcal D}_{\epsilon}(S,d).\,\footnote{We follow \cite{eec_IEEE:HausslerOpper97} in this definition of the metric entropy. Several authors use a slightly different definition, based on the covering number or the packing number.} \]
  \item An \emph{$\epsilon$-cover} of $S$ is a subset $A\subset S$ such that, for all $x$ in $S$, there is an element $y$ of $A$ with $d(x,y)<\epsilon$. The \emph{covering number} ${\mathcal N}_{\epsilon}(S,d)$ is the cardinality of the smallest finite $\epsilon$-cover of $S$, or we define ${\mathcal N}_{\epsilon}(S,d)=\infty$ if no finite $\epsilon$-cover exists.
  \item An \emph{$\epsilon$-separated subset} of $S$ is a subset $A\subset S$ such that, for all distinct $x,\,y$ in $A$, $d(x,y)>\epsilon$. The \emph{packing number} ${\mathcal M}_{\epsilon}(S,d)$ is the cardinality of the largest finite $\epsilon$-separated subset of $S$, or we define ${\mathcal M}_{\epsilon}(S,d)=\infty$ if arbitrary large $\epsilon$-separated subsets exist.
 \end{enumerate}
\end{df}

The following lemma explains how these numbers are linked. It is a classical result that can be found for instance in \cite{eec_IEEE:VaartWellner96}.
\begin{lem}\label{lem:numbers}
 Let $S$ be a subset of $\Theta$. For all $\epsilon>0$,
 \[ {\mathcal M}_{2 \epsilon}(S,d) \leq {\mathcal D}_{2 \epsilon}(S,d) \leq {\mathcal N}_{\epsilon}(S,d) \leq {\mathcal M}_{\epsilon}(S,d). \]
\end{lem}
Lemma~\ref{lem:numbers} enables us to choose the most convenient number to calculate the metric entropy.

From the metric entropy one can define the notion of metric dimension, which generalizes the classical notion of dimension. But the metric entropy lets us know in some way how dense the elements are in a set, even infinite dimensional.

Another quantity that \cite{eec_IEEE:HausslerOpper97} uses is the \emph{minimax risk for the $(1+\lambda)$-affinity}
\[ R_\lambda(\Lambda) = \inf_{Q} \sup_{\boldsymbol{\theta}\in \Theta_{\lambda}} \sum_{k\geq 1} P_{\boldsymbol{\theta}}(k)^{1+\lambda} Q(k)^{-\lambda}, \]
defined for all $\lambda>0$. \\
More precisions about the $(1+\lambda)$-affinity are given in
\cite{eec_IEEE:HausslerOpper97}
. See also \cite{eec_IEEE:BontempsrapportM2} for a special regard payed to envelope classes.

In the case of an envelope class $\Lambda_f$ defined by an integrable envelope function $f$, it is easy to see that $R_\lambda<\infty$ for all $\lambda>0$. Indeed the choice
\[ Q(k) = \frac{f(k)}{\sum_{l\geq 1} f(l)} \]
leads to the relation
\[ R_\lambda \leq \left( \sum_{k\geq 1} f(k) \right)^{\lambda}. \]

We can now write a slightly modified version\,\footnote{The separation of the upper and lower bounds have no effect on the proof given by Haussler and Opper. A complete justification is available in \cite{eec_IEEE:BontempsrapportM2}.} of Theorem~5 of \cite{eec_IEEE:HausslerOpper97} in the context of data compression on an infinite alphabet.
\begin{thm}\label{thm:HausslerThm5}
 Let $\Lambda$ be a class of iid sources on $\N_{*}$, such that the parameter set $\Theta_{\Lambda}$ is a measurable subset of $\Theta$. Assume that there exists $\lambda>0$ such that $R_\lambda<\infty$.
 Let $h(x)$ be a continuous, non-decreasing function defined on the positive reals such that, for all $\gamma\geq 0$ and $C>0$,
 \begin{enumerate}
  \item \[ \lim_{x\rightarrow\infty} \frac{h\left(C x \left(h(x)\right)^\gamma\right)}{h(x)} = 1 \]
   and
  \item \[ \lim_{x\rightarrow\infty} \frac{h\left(C x (\ln x)^\gamma\right)}{h(x)} = 1. \]
 \end{enumerate}
 Then
 \begin{enumerate}
  \item If
   \[ {\mathcal H}_{\epsilon}(\Theta_{\Lambda},d) \underset{\epsilon \rightarrow 0}{\sim} h\left(\frac{1}{\epsilon}\right), \]
   then
   \[ R_n(\Lambda) \underset{n \rightarrow \infty}{\sim} (\log e)\, h(\sqrt{n}).\,\footnote{The $(\log e)$ factor comes from the use of the logarithm taken to base $2$, in the definition of $R_n$.} \]
  \item\label{thm5:lower} If, for some $\alpha>0$ and $c>0$,
   \[ \liminf_{\epsilon\rightarrow 0} \frac{{\mathcal H}_\epsilon(\Theta_{\Lambda},d)}{ (1/\epsilon)^{\alpha} h(1/\epsilon)} \geq c, \]
   then
   \[ \liminf_{n\rightarrow\infty} \frac{R_n(\Lambda)}{n^{\alpha/(\alpha+2)} \left[ h(n^{1/(\alpha+2)}) \right]^{2/(\alpha+2)}} > 0. \]
  \item\label{thm5:upper} If, for some $\alpha>0$ and $C>0$,
   \[ \limsup_{\epsilon\rightarrow 0} \frac{{\mathcal H}_\epsilon(\Theta_{\Lambda},d)}{ (1/\epsilon)^{\alpha} h(1/\epsilon)} \leq C, \]
   then
   \[ \limsup_{n\rightarrow\infty} \frac{R_n(\Lambda)}{(n \ln n)^{\alpha/(\alpha+2)} \left[ h(n^{1/(\alpha+2)}) \right]^{2/(\alpha+2)}} < \infty. \]
 \end{enumerate}
\end{thm}
The conditions concerning the function $h$ mean that $h$ cannot grow too fast. For instance, $h$ can grow like $C (\ln x)^\beta$, with $\beta\geq 0$.

The first case in the theorem is the one we use for exponentially decreasing envelope classes. In this case, the fast decreasing envelope produces a ``not too big'' metric entropy. Theorem~\ref{thm:HausslerThm5} gives us an equivalent of the minimax redundancy of the class of sources when $n$ goes to the infinity. This turns out very useful, as it improves a preceding result of \cite{eec_IEEE:BouGarGas06}. However it is only an asymptotic result, without any convergence speed.

The second and the third items correspond to bigger classes of sources. In these cases the result is a bit less interesting: it gives a speed for the growth of the redundancy, but without the associated constant factor. Furthermore there is a gap of $(\ln n)^{\alpha/(\alpha+2)}$ between the lower bound of point~\ref{thm5:lower} and the upper bound of point~\ref{thm5:upper}. However it allows us to retrieve more or less a result of \cite{eec_IEEE:BouGarGas06} for another type of envelope classes.

We develop now these applications.

\subsection{The minimax redundancy of exponentially decreasing envelope classes} \label{sec:EnvClassRedundancy}

Here we want to prove Theorem~\ref{thm:ExpClassRedundancy} by applying Theorem~\ref{thm:HausslerThm5}. Thus we have to calculate the metric entropy of exponentially decreasing envelope classes. This is done by Proposition~\ref{EnvClassLowerEntropy}:

\begin{prop} \label{EnvClassLowerEntropy}
 Let $C$ and $\alpha$ be positive numbers satisfying $C > e^{2 \alpha}$. The metric entropy of the parameters set $\Theta_{C,\alpha}$ verifies
 \[ {\mathcal H}_\epsilon(\Theta_{C,\alpha},d) = (1+o(1)) \frac{1}{\alpha} \ln^2 (1/\epsilon), \]
 where $o(1)$ is a function $g(\epsilon)$ such that $g(\epsilon)\rightarrow 0$ as $\epsilon\rightarrow 0$.
\end{prop}

\begin{proof}[Proof of Theorem~\ref{thm:ExpClassRedundancy}]
 Just apply Theorem~\ref{thm:HausslerThm5}, with $h(x) = \frac{1}{\alpha} \ln^2 (x)$, to get the result.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{EnvClassLowerEntropy}]
 The outlines of the proofs of the next lemmas can be found in Appendix~\ref{sec:EnvClassesMetrEnt}. The corollaries are simple applications and the proofs are skipped.

 We start with general considerations. Let $\Lambda_f$ be the envelope class defined by the integrable envelope function $f$. Let $\Theta_f$ be the corresponding parameter set
 \begin{equation*}
 \begin{split}
  \Theta_{f} &= \{ \boldsymbol{\theta}=(\theta_1,\theta_2,\ldots) \in [0,1]^{\N}: \\
   &\qquad \sum_{i\geq 1} \theta_i = 1\ \text{and } \forall i \geq 1,\ \theta_i \leq f(i) \}.
 \end{split}
\end{equation*}

 The function $\boldsymbol{\theta} \mapsto (\sqrt{\theta_1},\sqrt{\theta_2},\ldots)$ is an isometry between the metric space $(\Theta_f,d)$ and the subset $A_f \cap \{ \|x\| = 1 \}$ of $\ell^2$, equipped with the classical euclidean norm $\|\cdot\|$, where $A_f$ is defined by
 \begin{equation}
  A_f = \{ (x_k)_{k\in\N^*} \in \ell^2: \ \forall k\in\N^*, \ 0 \leq x_k \leq \sqrt{f(k)} \}.
 \end{equation}
 The metric entropy of $(\Theta_f,d)$ can be calculated in this space.

 Next we truncate some coordinates, to work in a finite dimensional space instead of $\ell^2$. Together with an adequate use of Lemma~\ref{lem:numbers}, this helps us to obtain upper and lower bounds for the metric entropy of $(\Theta_f,d)$. We start with the upper bound.

 \begin{lem} \label{lem:UpperEntropy}
  Let $\Lambda_f$ be the envelope class defined by the integrable envelope function $f$, and let $\epsilon$ be a positive number. Let $N_\epsilon$ denote the integer
  \begin{equation*}
   N_\epsilon = \inf \left\{n\geq 1: \ \sum_{k\geq n+1} f(k) \leq \frac{\epsilon^2}{16} \right\}.
  \end{equation*}
  For $U\in\R^N$ and $a>0$, let $B_{\R^{N}}(U, a)$ denote the ball in $\R^n$ with center $U$ and radius $a$. Then
  \[ {\mathcal H}_\epsilon(\Theta_f,d) \leq N_\epsilon \ln (1/\epsilon) + 3 N_\epsilon \ln 2 + A(N_\epsilon) + B(\epsilon), \]
  where
  \[ A(N) = -\ln \vol \left( B_{\R^{N}}(0, 1) \right) = \ln \frac{\Gamma(\frac{N}{2}+1)}{\pi^{\frac{N}{2}}} \]
  and
  \[ B(\epsilon) = \sum_{k=1}^{N_\epsilon} \ln \left(\sqrt{f(k)} + \frac{\epsilon}{4}\right). \]
  Furthermore
  \[ A(N_\epsilon) \underset{\epsilon \rightarrow 0}{\sim} \frac{N_\epsilon}{2} \ln N_\epsilon. \]
 \end{lem}
 Note that
 \[ -N_\epsilon \ln (1/\epsilon) - 2 N_\epsilon \ln 2 \leq B(\epsilon) \leq \frac{\epsilon}{4} N_\epsilon. \]
 These bounds on $B(\epsilon)$ show that $B(\epsilon)$ tends to decrease the upper bound, while $A(N_\epsilon)$ contributes to its growth. If $\ln N_\epsilon$ behaves like $\ln (1/\epsilon)$ up to a constant factor, then the upper bound given in Lemma~\ref{lem:UpperEntropy} corresponds to a constant times $N_\epsilon \ln N_\epsilon$, and we are concerned with the point~\ref{thm5:upper} of Theorem~\ref{thm:HausslerThm5}.

 If we apply Lemma~\ref{lem:UpperEntropy} to the case of exponentially decreasing envelope classes, we obtain the upper bounds
 \begin{gather*}
  N_\epsilon \leq \frac{2}{\alpha} \ln (1/\epsilon) + \frac{1}{\alpha} \ln \frac{16 C}{1-e^{-\alpha}} \\
  B(\epsilon) \leq -\frac{\alpha}{4} N_\epsilon^2 + \left(\frac{\ln C}{2} + \frac{1}{\sqrt{1-e^{-\alpha}}}\right) N_\epsilon.
 \end{gather*}
 This leads to
 \begin{corol} \label{corol:EnvClassUpperEntropy}
  Let $C$ and $\alpha$ be positive numbers satisfying $C > e^{2\alpha}$. The metric entropy of the parameter set $\Theta_{C,\alpha}$
  defined by (\ref{eq:ThetaCalpha})
  verifies
  \[ {\mathcal H}_\epsilon(\Theta_{C,\alpha},d) \leq (1+o(1)) \frac{1}{\alpha} \ln^2 (1/\epsilon), \]
  where $o(1)$ is a function $g(\epsilon)$ such that $g(\epsilon)\rightarrow 0$ as $\epsilon\rightarrow 0$.
 \end{corol}

 Now we need to get a lower bound on the metric entropy. In this case too, we want to truncate some coordinates to bring ourselves to a smaller finite dimensional space. This time we truncate the first coordinates. Let us consider the number
 \begin{equation*}
  l_f = \min \{ l\geq 0: \sum_{k\geq l+1} f(k) \leq 1 \}.
 \end{equation*}

 \begin{lem} \label{lem:LowerEntropy}
  Let $\Lambda_f$ be the envelope class defined by an integrable envelope function $f$, which verifies
  \[ \sum_{k\geq 1} f(k) \geq 2. \]
  Let $\epsilon>0$ be a positive number, and let $m\geq 1$ be an integer. Then
  \begin{equation*}
   {\mathcal H}_\epsilon(\Theta_f,d) \geq \frac{1}{2} \sum_{k=l_f+1}^{l_f+m} \ln f(k) + m \ln \left(\frac{1}{\epsilon}\right) + A(m),
  \end{equation*}
  where $A(m)$ is defined as in Lemma~\ref{lem:UpperEntropy}:
  \[ A(m) = -\ln \vol \left( B_{\R^{m}}(0, 1) \right) \underset{m \rightarrow \infty}{\sim} \frac{m}{2} \ln m. \]
 \end{lem}
 Note that exponentially decreasing envelopes verify the condition  $\sum_{k\geq 1} f(k) \geq 2$. Indeed the envelope of exponentially decreasing envelope classes is
 \[ f(k) = \min(1,C e^{-\alpha k}), \]
 and the condition $C > e^{2\alpha}$ entails that $f(1)= f(2) = 1$.

 From Lemma~\ref{lem:LowerEntropy} we can infer the following corollary, with the choice $m=\left\lfloor \frac{2}{\alpha} \ln\left(\frac{1}{\varepsilon}\right) \right\rfloor$.

 \begin{corol} \label{corol:EnvClassLowerEntropy}
  Let $C$ and $\alpha$ be positive numbers satisfying $C > e^{2 \alpha}$. The metric entropy of the parameters set $\Theta_{C,\alpha}$ verifies
  \[ {\mathcal H}_\epsilon(\Theta_{C,\alpha},d) \geq (1+o(1)) \frac{1}{\alpha} \ln^2 (1/\epsilon), \]
  where $o(1)$ is a function $g(\epsilon)$ such that $g(\epsilon)\rightarrow 0$ as $\epsilon\rightarrow 0$.
 \end{corol}
 Note that the bound is the same as in Corollary~\ref{corol:EnvClassLowerEntropy}. Therefore this concludes the proof of Proposition~\ref{EnvClassLowerEntropy}.
\end{proof}

\subsection{What about other envelope classes?} \label{sec:PolyEnvClasses}
In \cite{eec_IEEE:BouGarGas06} the redundancy of another type of envelope classes is also studied. The \emph{power-law envelope class} $\Lambda_{C \cdot^{-\alpha}}$ is defined, for $C>1$ and $\alpha>1$, by the envelope function $f_{\alpha,C}(x) = \min(1,\frac{C}{x^\alpha})$. The bounds obtained in \cite[Theorem~6]{eec_IEEE:BouGarGas06} are
\begin{equation} \label{eq:BGGClassesPoly}
 \begin{split}
  &A(\alpha) n^{1/\alpha} \log \lfloor C \zeta(\alpha) \rfloor \\
   &\qquad\leq \R_n(\Lambda_{C\cdot^{-\alpha}}) \\
   &\qquad\leq \left( \frac{2 C n}{\alpha-1} \right)^{1/\alpha} (\log n)^{1-1/\alpha} + O(1),
 \end{split}
\end{equation}
where
\[ A(\alpha) = \frac{1}{\alpha} \int_{1}^{\infty} \frac{1-e^{-1/(\zeta(\alpha) u)}}{u^{1-1/\alpha}} \ud u, \]
and $\zeta$ denotes the classical function $\zeta(\alpha) = \sum_{k\geq 1} \frac{1}{k^\alpha}$, for $\alpha>1$.

If one adapts the calculus made earlier to the power-law envelope classes, one can get the following upper and lower bounds: \\
There are two (calculable) constants $K_1,K_2>0$ such that, for all $\epsilon>0$,
\[ K_1 \left(\frac{1}{\epsilon}\right)^{\frac{2}{\alpha-1}} \leq {\mathcal H}_\epsilon \leq K_2 (1+o(1)) \left(\frac{1}{\epsilon}\right)^{\frac{2}{\alpha-1}} \ln \left(\frac{1}{\epsilon}\right). \]
Unfortunately this formula leaves a gap between the lower bound and the upper bound. The application of Theorem~\ref{thm:HausslerThm5} makes the gap worse. Indeed the polynomial part $\left(\frac{1}{\epsilon}\right)^{\frac{2}{\alpha-1}}$ of the metric entropy causes an additional gap of $\log^{1/\alpha} n$. In practice the bounds are the following: \\
There are two (unknown) constants $C,c>0$ such that, for all $n\geq 1$,
\begin{equation} \label{eq:PowerLawClasses}
c (1+o(1)) n^{1/\alpha} \leq R_n(\Lambda_{C \cdot^{-\alpha}}) \leq C (1+o(1)) n^{1/\alpha} \log n.
\end{equation}

These inequalities improve in no way the result of \cite{eec_IEEE:BouGarGas06}. May a better calculus of the metric entropy improve either their lower bound or their upper bound? Anyway the metric entropy of power-law envelope classes is ``too big'' to efficiently apply Theorem~\ref{thm:HausslerThm5}: it does not leave the hope for an equivalence, as for exponentially decreasing envelope classes. To summarize, the strategy based on the metric entropy and Theorem~\ref{thm:HausslerThm5} turns out efficient for ``small'' classes of sources.

\section{AutoCensuring Code} \label{sec:code}

This section presents a new algorithm called AutoCensuring Code (\textup{\texttt{ACcode}}). It is in fact a modification of the Censuring Code proposed by Boucheron, Garivier and Gassiat in \cite{eec_IEEE:BouGarGas06}. We keep the idea that big symbols are very few, and must be encoded differently, with an Elias code. Smaller symbols are encoded by arithmetic coding based on Krichevsky-Trofimov mixtures, which are known to be effective for finite alphabets. Our innovation is a data-driven cutoff $M_i = \sup_{1 \leq k \leq i} X_k$ used to encode $X_{i+1}$: with this choice we do not need to know the exact parameters of the exponentially decreasing envelope.

\textup{\texttt{ACcode}} is a prefix code on the set of all finite length messages, and it works on line. Its maximum redundancy on an exponentially decreasing envelope class $\Lambda_{Ce^{-\alpha\cdot}}$ is equivalent to the minimax redundancy of this class of sources. Furthermore \textup{\texttt{ACcode}} is adaptive, as the same algorithm verifies this property with all exponentially decreasing envelope classes. This is formulated in the following theorem, proved in Appendix~\ref{sec:proof-ACcode}. \\
 Let $\textup{\texttt{ACcode}}(x_{1:n})$ denote the binary string produced by \textup{\texttt{ACcode}} when it encodes the message $x_{1:n}$, and let $l(\cdot)$ denote the length of a string.

\begin{thm} \label{thm:ACcodeRedundancy}
 For any positive numbers $C$ and $\alpha$ satisfying $C > e^{2 \alpha}$,
 \[ \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n}[l(\textup{\texttt{ACcode}}(X_{1:n})) - H(P^n)] \underset{n \rightarrow \infty}{\sim} R_n(C, \alpha). \]
\end{thm}
The difference between the redundancy of \textup{\texttt{ACcode}} and the minimax redundancy is not necessarily bounded: there may exist codes whose redundancy is smaller than the redundancy of \textup{\texttt{ACcode}}, but with a benefit negligible with respect to $\log^2 n$.

Additionally, Theorem~\ref{thm:ACcodeRedundancy} enables us to retrieve the upper bound of the minimax redundancy obtained in the section~\ref{sec:MinimaxRedundancy}.

Let us now define \textup{\texttt{ACcode}}. Let $n\geq 1$ be some positive integer, and let $x_{1:n}=x_1 x_2\ldots x_n$ be a string from $\N_{*}^n$ to be encoded. We define the sequence of maxima
\[ m_0 = 0 \text{ and } m_i = \sup_{1 \leq k \leq i} x_k, \text{ for all } 1 \leq i \leq n. \]

The sequence $(m_i)_{1\leq i \leq n}$ is non-decreasing, piecewise constant. For $1\leq i \leq n$, let $n_{i}^0=\sum_{j=1}^{i} \1_{m_j>m_{j-1}}$ be the number of plateaus between $1$ and $i$. For $1\leq k \leq n^0_n$, let $\widetilde{m}_k$ be the $k^\text{th}$ new maximum:
\begin{equation} \label{eq:mmtilde}
 m_i = \widetilde{m}_{n_i^0}.
\end{equation}

We define also $\widetilde{m}_0=0$. Let string $\m$ be the sequence $(\widetilde{m}_1 - \widetilde{m}_{0} +1), \ldots, (\widetilde{m}_{n_n^0} - \widetilde{m}_{n_n^0-1} +1), 1$. $\m$ is encoded into a binary string $\textup{\texttt{C2}}$ by applying Elias penultimate code (see \cite{eec_IEEE:Elias75}) to each number in $\m$. It is a prefix code which uses $l_E(x)$ bits to encode a positive integer $x$, with
\begin{equation} \label{eq:EliasLength}
 \begin{split}
   l_E(1) &= 1, \\
   l_E(x) &= 1 + \lfloor \log x \rfloor + 2 \left\lfloor \log \lfloor \log x \rfloor + 1 \right\rfloor \quad \text{if } x\geq 2.
 \end{split}
\end{equation}

Meanwhile the sequence of censored symbols is encoded using side information from $\m$. Consider the censored sequence $\widetilde{x}_{1:n}=\widetilde{x}_1 \widetilde{x}_2\ldots \widetilde{x}_n$ defined by
\[ \widetilde{x}_{i} = x_i \1_{x_i\leq m_{i-1}} = \left\{ \begin{array}{ll}
                                                 x_i &\text{if } x_i\leq m_{i-1}, \\
                                                 0 &\text{otherwise.}
                                                \end{array} \right. \]
All symbols greater than $m_{i-1}$ are encoded together: they are replaced by the extra symbol $0$, and this extra symbol is encoded instead. $0$ has a special use in our setting: it makes the decoder to know when $m_i$ changes, and that the new value has to be read in $\textup{\texttt{C2}}$. We add at the end of $\widetilde{x}_{1:n}$ an additional $0$, which acts as a termination signal together with the last $1$ in $\m$. This makes our code to be prefix on the set of all finite length messages (whatever $n$).

Therefore we produce the binary string $\textup{\texttt{C1}}$ by arithmetic coding of $\widetilde{x}_{1:n}0$. The conditional coding probabilities are defined by
\begin{align*}
  Q_{i+1}(\widetilde{X}_{i+1}=j | X_{1:i} = x_{1:i}) &= \frac{n_i^j + \frac{1}{2}}{i + \frac{m_i + 1}{2}} \quad\text{if}\quad 1 \leq j \leq m_i, \\
  Q_{i+1}(\widetilde{X}_{i+1} = 0 | X_{1:i} = x_{1:i}) &= \frac{1/2}{i + \frac{m_i + 1}{2}},
\end{align*}
where for $j\geq 1$ and $i\geq 0$, $n_i^j$ is the number of occurrences of symbol $j$ in $x_{1:i}$ (with convention $n_0^j = 0$ for all $j\geq 1$).

If $i\leq n-1$, the event $\{\widetilde{X}_{i+1} = 0\}$ is equal to $\{X_{i+1} > M_i\}$. If $x_{i+1} = j > m_i$, then $n_i^j=0$, and we still have
\[ Q_{i+1}(\widetilde{X}_{i+1} = 0 | X_{1:i} = x_{1:i}) = \frac{n_i^j + \frac{1}{2}}{i + \frac{m_i + 1}{2}}. \]

In the sequel we note the coding probability used to encode the entire string $\widetilde{x}_{1:n}0$ by
\[ Q^{n+1}(\widetilde{x}_{1:n}0) = Q_{n+1}(0 | x_{1:n}) \prod_{i=0}^{n-1} Q_{i+1}(\widetilde{x}_{i+1} | x_{1:i}). \]

A remark we can do is that the symbol $0$ is always considered as new: when $x_{i+1}>m_i$, we encode $0$ but we increment the counter $n^{x_{i+1}}_{i}$. (This choice has been made to simplify the calculation of the redundancy of \textup{\texttt{ACcode}}, but we suspect that changing this behavior could improve the performances.)

Now we have defined $\textup{\texttt{C1}}$ and $\textup{\texttt{C2}}$, we have to describe how they are transmitted. To keep our code on line, we overlap these two strings in the following way.

Arithmetic code needs a certain amount of bits, say $l_{i}$, to send the first $i$ symbol of $\widetilde{x}_{1:n}$. Unfortunately, $l_{i}$ depends on whether $i=n+1$ or not. In previous case $l_{n+1} = \lceil -\log Q^{n+1}(\widetilde{x}_{1:n}0) \rceil +1$, and in later one $l_{i}$ depends on the following symbols and has to be computed. \\
\textup{\texttt{ACcode}} begins with $\textup{\texttt{C2}}$, by the transmission of the Elias code of $\widetilde{m}_1+1$. Then the transmission of $\textup{\texttt{C1}}$ is initiated. Suppose that $\widetilde{x}_{i} = 0$ and $n^0_{i}=k$. As soon as $l_{i}$ bits of $\textup{\texttt{C1}}$ have been sent,

the \textup{\texttt{ACcode}} algorithm sends the Elias code of $\widetilde{m}_k-\widetilde{m}_{k-1}+1$. Then $\textup{\texttt{C1}}$ is transmitted again, from the next bit.

To decode the $i^{\text{th}}$ symbol in $\textup{\texttt{C1}}$, the knowledge of the current maximum $m_{i-1}$ is needed; it is obtained from the beginning of the string $\textup{\texttt{C2}}$. The decoder also needs the counters $(n_{i-1}^j)_{j\geq 1}$, which can be computed from the first $i-1$ decoded symbols. As soon as $l_i$ bits of $\textup{\texttt{C1}}$ have been received, $\widetilde{x}_i$ can be decoded. When the decoder meets a $0$ at the $i^{\text{th}}$ position, he knows that the next bits are the Elias code of the next symbol in $\m$, and deduces $m_{i}$ via (\ref{eq:mmtilde}). Since the Elias code is prefix, the decoder knows when he receives $\textup{\texttt{C1}}$ again. Then the $(i+1)^{\text{th}}$ symbol can be processed.

Fig.~\ref{fig:ExACcode} shows an illustration of the transmission process. In this example, the initial message is $x_{1:4} = 5, 3, 2, 7$. Then the message encoded in $\textup{\texttt{C1}}$ is $\widetilde{x}_{1:4}0 = 0, 3, 2, 0, 0$. $13$ bits are needed to transmit the second $0$, and $15$ bits for the last one. In $\textup{\texttt{C2}}$ we transmit $\m = 6, 3, 1$.

\begin{figure*}[!t]
 \centering
  \begin{tabular}{c@{}c@{}c@{}c@{}c}
   $\underbrace{01110}$ & $\underbrace{0110011001101}$ & $\underbrace{0101}$
     & $\underbrace{00}$ & $\underbrace{1}$ \\
   $\downarrow$ &
     \begin{tabular}{c}
      beginning \\
      of $\textup{\texttt{C1}}$
     \end{tabular} &
     $\downarrow$ &

     \begin{tabular}{c}
      last bits \\
      of $\textup{\texttt{C1}}$
     \end{tabular} &
     $\downarrow$ \\
   \begin{tabular}{c}
     Elias code \\
     of $\widetilde{m}_1+1$
   \end{tabular} &
     & \begin{tabular}{c}
        Elias code \\
        of $\widetilde{m}_2-\widetilde{m}_1+1$
       \end{tabular} &
     & \begin{tabular}{c}
        Elias code \\
        of $1$
       \end{tabular}
  \end{tabular}
 \caption{Example of \textup{\texttt{ACcode}}}
 \label{fig:ExACcode}
\end{figure*}

In the previous example, exact calculations have been performed, but this is not sensible for a practical implementation of arithmetic coding. Some rule is needed to set the precision in calculus, and it must be used by both coder and decoder. To avoid a too big extra redundancy caused by approximations, precision can grow as $n$ grows. For instance, calculations can be made in memory with a further precision of $2\,\lceil \log i \rceil$ bits, in addition to the $\lceil -\log Q^{i}(\widetilde{x}_{1:i}) \rceil +1$ bits needed to encode $x_{1:i}$; this insures that the extra redundancy is bounded.

\appendices

\section{Metric entropy of exponentially decreasing envelope classes} \label{sec:EnvClassesMetrEnt}

We give here the outlines of the lemmas we stated in subsection~\ref{sec:EnvClassRedundancy}.

\begin{proof}[Proof of Lemma~\ref{lem:UpperEntropy}]
 $N_\epsilon$ denotes the threshold from which we want to truncate the coordinates. If $y=(y_n)_{n\geq 1}$ is an element of $A_f$, its truncated version is $\widetilde{y} = (y_n \1_{n\leq N_\epsilon})_{n\geq 1}$. One can check that
 \begin{equation*}
   \|y - \widetilde{y}\| \leq \frac{\epsilon}{4}.
 \end{equation*}

 Suppose now that $S$ is an $\epsilon/4$-cover of $\{y\in A_f: \ \forall n\geq N_\epsilon, y_n=0\}$. Let $z$ denote an element of $A_f$. Then it exists some $y\in S$ such that $\|\widetilde{z} - y\| \leq \epsilon/4$. Thus $\|z - y\| \leq \epsilon/2$, and $S$ is an $\epsilon/2$-cover of $A_f$. This leads to
 \begin{equation*}
  \begin{split}
   {\mathcal D}_\epsilon(\Theta_f,d) &\leq {\mathcal M}_{\epsilon/4}\left( \prod_{1\leq k\leq N_\epsilon} \left[0,\sqrt{f(k)}\right], \|\cdot\|_{\R^{N_\epsilon}} \right) \\
    &\leq \frac{\vol \left( \prod_{1\leq k\leq N_\epsilon} \left[ -\frac{\epsilon}{8}, \sqrt{f(k)} + \frac{\epsilon}{8} \right] \right)}{\vol \left( B_{\R^{N_\epsilon}}(0, \frac{\epsilon}{8}) \right)} \\

  \end{split}
 \end{equation*}

 A first consequence of that calculus is that ${\mathcal D}_\epsilon(\Theta_f,d)$ is finite for all $\epsilon>0$. The first assertion of Lemma~\ref{lem:UpperEntropy} is then obtained by applying the logarithm function.

 The rest of Lemma~\ref{lem:UpperEntropy} follows from the Feller bounds, in their version proposed by \cite[ch. XII]{eec_IEEE:whittaker_watson}:
 \begin{equation} \label{eq:stirling}
  \Gamma(x) = \sqrt{2\pi}\, x^{x-1/2} e^{-x} e^{\frac{\beta}{12 x}}, \quad\text{with } \beta \in [0,1].
 \end{equation}
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:LowerEntropy}]
 Let $m\geq 1$ be an integer. We project the set $A_f \cap \{ \|x\| = 1 \}$ over the $m$-dimensional space
 \[E_m = \{0\}^{l_f} \times \R^m \times \{0\}^{\{k:k\geq l_f+m+1\}}\]
 generated by the coordinates from $l_f+1$ to $l_f+m$. This leads to
 \begin{equation*}
  \begin{split}
   {\mathcal D}_\epsilon(\Theta_f,d) &\geq {\mathcal N}_\epsilon \left( \prod_{k=l_f+1}^{l_f+m} \left[0,\sqrt{f(k)}\right], \|\cdot\|_{\R^{m}} \right) \\
    &\geq \frac{\vol \left( \prod_{k=l_f+1}^{l_f+m} \left[0,\sqrt{f(k)}\right] \right)}{\vol \left( B_{\R^{m}}(0, \epsilon) \right)}.
  \end{split}
 \end{equation*}
 It only remains to apply the logarithm function.
\end{proof}

\section{Redundancy of \textup{\texttt{ACcode}}} \label{sec:proof-ACcode}

\subsection{Moments of $M_n$} \label{sec:ProofExpectedMn}

We first need a lemma which contains several useful results about the moments of $M_n$.

\begin{lem} \label{lem:ExpectedMn}
 Let $C$ and $\alpha$ be positive numbers satisfying $C > e^{2 \alpha}$.

 Then, for all $n\geq1$,
 \begin{enumerate}
  \item \label{lem:Mn1}
   \[ \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_P[M_n] \leq \frac{1}{\alpha} \left( \ln n + \ln \frac{C}{1-e^{-\alpha}} +1 \right). \]
  \item \label{lem:Mn2} \[ \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_P \left[ M_n \1_{M_n > \frac{1}{\alpha} \ln \frac{C n^2}{1-e^{-\alpha}}} \right] = O\left(\frac{\ln n}{n}\right). \]
  \item \label{lem:Mn3} \[ \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_P[M_n \ln M_n] = o(\ln^2 n). \]
 \end{enumerate}
\end{lem}

\begin{proof}
 Let $F$ denote the distribution function associated with $P$. For $t\geq 0$, we have
 \begin{equation*}
  \begin{split}
   \Proba(X_1>t)
    &= \sum_{k\geq \lfloor t\rfloor +1} P(k) \\

    &\leq \frac{C}{1-e^{-\alpha}} e^{-\alpha (\lfloor t\rfloor +1)} \\

    &\leq e^{-\alpha (t - \beta)},
  \end{split}
 \end{equation*}
 where $\beta = \frac{1}{\alpha} \ln \frac{C}{1-e^{-\alpha}}$. Therefore $F(t) \geq G(t)$ for all $t\in\R$, where
 \begin{equation*}
  G(t) = \1_{t \geq \beta} \left(1-e^{-\alpha (t - \beta)} \right).
 \end{equation*}
 We can identify in $G$ the distribution function of the random variable $\beta + Y$, where $Y$ follows the exponential distribution with parameter $\alpha$.

 Let $U_1, \ldots, U_n$ be $n$ iid random variables following the uniform distribution on $[0,1]$. For $1\leq i\leq n$, let us define
 \begin{equation*}
  \begin{split}
   X'_i &= F^{-1}(U_i) \\
   Y_i &= G^{-1}(U_i)-\beta,
  \end{split}
 \end{equation*}
 where $F^{-1}$ and $G^{-1}$ denote the pseudo-inverses of $F$ and $G$:
 \[ \forall t \in [0,1], \quad F^{-1}(t) = \inf \{x\in\R: F(x) \geq t\}. \]

 Then the $n$-dimensional vector $X'_{1:n} = (X'_1,\ldots,X'_n)$ has the same distribution as $X_{1:n}$, and the maxima $M'_n = \sup_{1\leq i\leq n} X'_i$ and $M_n$ follow the same distribution.

 On the other hand, the relation $F \geq G$ entails $X'_i \leq \beta+Y_i$, for all $1\leq i\leq n$. As the consequence, if $M''_n = \sup_{1\leq i\leq n} Y_i$ denotes the maximum of all $Y_i$, we have $M'_n \leq \beta+M''_n$. Since the random variables $Y_i$ are independent, the probability distribution of $M''_n$ is easy to calculate. Indeed for all $t>0$,
 \begin{equation*}
  \begin{split}
   \Proba(M''_n \leq t) &= \Proba(\forall\ 1\leq i\leq n,\ Y_i \leq t) \\

    &= \left(1-e^{-\alpha t}\right)^n.
  \end{split}
 \end{equation*}
 We can write down the density function of $M''_n$:

 \[ f(t) = \left\{ \begin{array}{ll} n\, \alpha\, e^{-\alpha t} (1-e^{-\alpha t})^{n-1} & \text{if } t>0, \\ 0 & \text{otherwise.} \end{array} \right. \]

 Now we look for an upper bound of $\E[M_n]$ by taking advantage of the knowledge of that distribution:
 \begin{equation*}
  \begin{split}
   \E[M_n] &= \E[M'_n] \\
    &\leq \E[\beta+M''_n] \\

    &= \beta+ \int_{0}^{\infty} t\, n\, \alpha\, e^{-\alpha t} (1-e^{-\alpha t})^{n-1}\,\ud t \\

    &= \beta+  \int_{0}^{\infty} \left(1-(1-e^{-\alpha t})^{n}\right)\,\ud t
  \end{split}
 \end{equation*}
 integrating by parts. Use now the change of variables
 \begin{equation*}
  \left\{ \begin{array}{l}
   u = 1 - e^{-\alpha t} \\
   t = \frac{-\ln (1-u)}{\alpha}
  \end{array} \right.
 \end{equation*}
 \begin{equation*}
  \begin{split}
   \E[M_n] &\leq \beta+ \frac{1}{\alpha} \int_{0}^{1} \frac{1-u^n}{1-u} \ud u \\

    &\leq \frac{1}{\alpha}\left( \ln n + 1 + \ln \frac{C}{1-e^{-\alpha}} \right).
  \end{split}
 \end{equation*}

 Since the upper bound does not depend on $P$, that achieves the proof of the point~\ref{lem:Mn1}. We can handle the point~\ref{lem:Mn2} in the same way.
 For all $t>0$, we have
 \begin{equation*}
  \begin{split}
   \E\left[M_n \1_{M_n>\beta+t}\right] &\leq \E\left[(\beta+M''_n) \1_{M''_n>t}\right] \\

    &\leq \int_{t}^{\infty} (\beta+u) n\, \alpha\, e^{-\alpha u}\,\ud u \\
    &= n e^{-\alpha t} \left(t+\frac{1}{\alpha}+\beta\right).
  \end{split}
 \end{equation*}
 With $t=\frac{2}{\alpha} \ln n$, we get the second point of Lemma~\ref{lem:ExpectedMn}.

 The third item is similar. Since the function $x\mapsto x\ln x$ is increasing on $[1,+\infty)$ and $1\leq M'_n \leq \beta+M''_n$, we have
 \begin{equation*}
  \begin{split}
   &\E\left[M_n \ln M_n\right] \\
    &\quad\leq \E\left[(\beta+M''_n) \ln (\beta+M''_n)\right] \\
    &\quad= \E\left[\1_{M''_n\leq \beta} (\beta+M''_n) \ln (\beta+M''_n)\right] \\
     &\quad\qquad + \E\left[\1_{M''_n> \beta} \1_{M''_n\leq \frac{2}{\alpha} \ln n} (\beta+M''_n) \ln (\beta+M''_n)\right] \\
     &\quad\qquad + \E\left[\1_{M''_n> \beta} \1_{M''_n> \frac{2}{\alpha} \ln n} (\beta+M''_n) \ln (\beta+M''_n)\right] \\
    &\quad\leq 2\beta \ln (2\beta) + \frac{4}{\alpha} (\ln n) \ln \left(\frac{4}{\alpha} \ln n\right)  \\
     &\quad\qquad + \E\left[2 M''_n \ln (2 M''_n) \1_{M''_n> \frac{2}{\alpha} \ln n}\right] \\
    &\quad\leq 2\beta \ln (2\beta) + \left(\frac{4}{\alpha} \ln \frac{4}{\alpha}\right) \ln n + \frac{4}{\alpha} (\ln n) (\ln \ln n) \\
     &\quad\qquad + \E\left[4 {M''_n}^2 \1_{M''_n> \frac{2}{\alpha} \ln n}\right].
  \end{split}
 \end{equation*}
 Let us define
 \[ \gamma(n) = 2\beta \ln (2\beta) + \left(\frac{4}{\alpha} \ln \frac{4}{\alpha}\right) \ln n + \frac{4}{\alpha} (\ln n) (\ln \ln n). \]
 Note that $\gamma(n) = o(\ln^2 n)$. Then
 \begin{equation*}
  \begin{split}
   \E\left[M_n \ln M_n\right]
    &\leq \gamma(n) + \int_{\frac{2}{\alpha} \ln n}^{\infty} 4 u^2 n\, \alpha\, e^{-\alpha u}\,\ud u \\
    &= \gamma(n) + \frac{4 n e^{-2 \ln n}}{\alpha^2} (4 \ln^2 n + 4 \ln n + 2).
  \end{split}
 \end{equation*}
 Taking the supremum over $P$, we get
 \begin{equation*}
  \begin{split}
   \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_P\left[M_n \ln M_n\right] &\leq \gamma(n) + \frac{16 \ln^2 n + 16 \ln n + 8}{\alpha^2\, n} \\
    &= o(\ln^2 n).
  \end{split}
 \end{equation*}
\end{proof}

\subsection{Contribution of \textup{\texttt{C1}}} \label{sec:ContribC1Lemmas}

\begin{prop} \label{prop:ContribC1}
 Let $C$ and $\alpha$ be positive numbers satisfying $C > e^{2 \alpha}$. Then
 \begin{equation*}
  \begin{split}
   &\sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [ - \log  Q^n(\widetilde{X}_{1:n}) - H(P^n) ] \\
     &\qquad \leq (1+o(1)) \frac{1}{4 \alpha \log e} \log^2 n.
  \end{split}
 \end{equation*}
\end{prop}

\begin{proof}
  We give here the sketch of the proof, and we delay the proofs of (\ref{eq:C1A1}), (\ref{eq:C1A2}), (\ref{eq:C1A3}), and (\ref{eq:C1A4}).

  Here we deal with the quantity
  \begin{equation*}
  (\textup{A}) = \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [ - \log  Q^n(\widetilde{X}_{1:n}) - H(P^n)].
  \end{equation*}
  that corresponds to the contribution of $\textup{\texttt{C1}}$. As we saw in Section~\ref{sec:code}, the coding probability $Q^n$ is based on Krichevsky-Trofimov mixtures. For $k\geq 1$, let $KT_k$ denote the usual Krichevsky-Trofimov mixture on the alphabet $\{1, \ldots, k\}$, whose conditional probabilities are, for all $0\leq i \leq n-1$ and for all $1\leq j \leq k$,
  \begin{equation*}
  KT_k(X_{i+1}=j | X_{1:i} = x_{1:i}) = \frac{n_i^j + \frac{1}{2}}{i + \frac{k}{2}}.
  \end{equation*}
  Let us choose $k=m_n+1$. In this case, there is a simple relation between $KT_{m_n+1}$ and $Q^n$. For any sequence of $n$ positive integers $x_{1:n}\in\N_{*}^n$,
  \begin{multline*}
  Q_{i+1}(\widetilde{X}_{i+1}=\widetilde{x}_{i+1} | X_{1:i} = x_{1:i}) \\
    = \frac{ 2 i + 1 + m_n}{2 i + 1 + m_i} KT_{m_n+1}(X_{i+1}=x_{i+1} | X_{1:i} = x_{1:i}).
  \end{multline*}
  As a consequence, we can link the redundancy of $Q^n$ to the redundancy of $KT_{m_n+1}$:
  \begin{equation*}
    \log  Q^n(\widetilde{X}_{1:n}) = \log KT_{M_n+1}(X_{1:n}) +\sum_{i=0}^{n-1} \log \frac{ 2 i + 1+ M_n}{2 i + 1 + M_i}
  \end{equation*}
  and therefore
  \begin{equation*}
  \begin{split}
    (\textup{A}) &= \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \Bigg( \overset{(\textup{A}_1)}{\overbrace{ \E_{P^n} \big[ -\log KT_{M_n+1}(X_{1:n}) - H(P^n)\big] }} \\
    &\qquad - \overset{(\textup{A}_2)}{\overbrace{ \E_{P^n} \bigg[ \sum_{i=0}^{n-1} \log \frac{ 2 i +1 + M_n}{2 i + 1 + M_i} \bigg] }} \Bigg).
  \end{split}
  \end{equation*}
  Note that $(\textup{A}_2)$ corresponds to the gain in redundancy of $Q^n$ with respect to $KT_{M_n+1}$. It illustrates the benefit of taking $M_i$ instead of $M_n$ as cutoff to encode $X_{i+1}$.

  On the one hand, we have
  \begin{equation} \label{eq:C1A1}
    (\textup{A}_1) \leq \frac{\E[M_n]}{2} \log n + \E[\log (M_n+1)].
  \end{equation}
  Since $\E[\log M_n] \leq \E[M_n]$, Lemma~\ref{lem:ExpectedMn} entails
  \[\sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E[\log (M_n+1)] = o(\log^2 n).\]

  Applying Lemma~\ref{lem:ExpectedMn} again, we see that $(\textup{A}_1)$ produces a redundancy equivalent to $\frac{1}{2 \alpha \log e} \log^2 n$, which is twice bigger than the minimax redundancy obtained in Theorem~\ref{thm:ExpClassRedundancy}. So, we will hope the corrective term $(\textup{A}_2)$ to be about $\frac{1}{4 \alpha \log e} \log^2 n$. \\
  To deal with $(\textup{A}_2)$, we use the concavity of the $\log$ function, and we group the terms in the sum, $M_n$ by $M_n$. Let $m=\big\lfloor \frac{n-1}{M_n} \big\rfloor$ be the number of bundles. \\
  To simplify the expression, we also neglect few terms at the beginning of the sum. Let $(h_n)_{n\geq 1}$ be a non-decreasing sequence of positive integers, such that $h_n \rightarrow \infty$ as $n \rightarrow \infty$, and let us define $\lambda_n = 2 h_n \log \left( 1+ \frac{1}{2 h_n}\right)$. Then
  \begin{equation} \label{eq:C1A2}
    (\textup{A}_2) \geq \lambda_n \E_{P^n} \left[ \sum_{k=h_n +1}^{m} \frac{M_n-M_{k M_n}}{2 (k +1)} \right].
  \end{equation}
  It is easy to verify that the function $x \mapsto x \log \left(1+\frac{1}{x}\right)$ is non-decreasing, and tends to $\log e$ when $x$ tends to the infinity; therefore $(\lambda_n)$ tends to $\log e$. We can write now
  \begin{align*}
    (\textup{A}) &\leq \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \Bigg( \frac{\E[M_n]}{2} \log n \\
      &\qquad - \lambda_n \E \left[ \sum_{k=h_n +1}^{m} \frac{M_n-M_{k M_n}}{2 (k +1)} \right] \Bigg) + o(\log^2 n) \\
  \begin{split}
    &\leq \frac{1}{2} \overset{(\textup{A}_3)}{\overbrace{ \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} \left[ M_n \log n - \lambda_n M_n \sum_{k=h_n +1}^{m} \frac{1}{k + 1} \right] }} \\
      &\qquad + \frac{\lambda_n}{2} \overset{(\textup{A}_4)}{\overbrace{ \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} \left[ \sum_{k=h_n +1}^{m} \frac{M_{k M_n}}{k + 1} \right] }} + o(\log^2 n)
  \end{split}
  \end{align*}

  Let us choose $h_n = \max \{1,\lfloor \ln n - 2 \rfloor\}$. Then
  \begin{equation} \label{eq:C1A3}
    (\textup{A}_3) = o(\log^2 n)
  \end{equation}
  \begin{equation} \label{eq:C1A4}
    (\textup{A}_4) \leq \frac{\log^2 n}{2 \alpha \log^2 e} + o(\log^2 n).
  \end{equation}

  Therefore we have
  \begin{equation*}
  \begin{split}

    (\textup{A})
      &\leq (1+o(1)) \frac{1}{4 \alpha \log e} \log^2 n
  \end{split}
  \end{equation*}
  which concludes the proof of Proposition~\ref{prop:ContribC1}.
\end{proof}

\begin{proof}[Proof of (\ref{eq:C1A1})]
 Let
 \[ \widehat{P}^n(x_{1:n}) = \sup_{P^n} P^n(x_{1:n}) = \prod_{j\in \{x_1,\ldots,x_n\}} \left(\frac{n_j^n}{n}\right)^{n_j^n} \]
 be the maximum likelihood of the string $x_{1:n}$ over all iid distribution on $\N^n$. Then
 \begin{equation*}
  \begin{split}
   (\textup{A}_1) &\leq \E_{P^n} \left[ \log \frac{\widehat{P}^n(X_{1:n})}{KT_{M_n+1}(X_{1:n})} \right] \\
    &\leq \E_{P^n} \left[ \sup_{x_{1:n} \in \{1, \ldots, M_n+1\}} \log \frac{\widehat{P}^n(x_{1:n})}{KT_{M_n+1}(x_{1:n})} \right]
  \end{split}
 \end{equation*}
 Now we can apply a result from Catoni \cite[prop~1.4.1]{eec_IEEE:Catoni2001}:
 \begin{lem}
  For all $k\geq 1$ and for all $x_{1:n} \in \{1, \ldots, k\}^n$,
  \[ -\log KT_{k}(x_{1:n}) + \log \widehat{P}^n(x_{1:n}) \leq \frac{k-1}{2} \log n + \log k. \]
 \end{lem}

\end{proof}

\begin{proof}[Proof of (\ref{eq:C1A2})]
 We group the terms in $(\textup{A}_2)$, $M_n$ by $M_n$:
 \begin{equation*}
  \begin{split}
   (\textup{A}_2)
    &\geq \E_{P^n} \left[ \sum_{k=1}^{m-1} \sum_{i=k M_n +1}^{(k+1) M_n} \log \left(1+ \frac{M_n-M_i}{2 i + M_i +1}\right) \right].
  \end{split}
 \end{equation*}

 From the relation $M_k \leq M_{k'}$ for all $k'\geq k \geq 1$, we can infer, for all $i\geq k M_n$,
 \[ \frac{M_n-M_i}{2 i + M_i +1} \leq \frac{M_n}{2 k M_n} = \frac{1}{2 k}  \]
 Since $\log$ is a concave function, we have $\log (1 + x) \geq \frac{x \log (1 + a)}{a}$ for all $a>0$ and $0\leq x\leq a$. Consequently, if we choose $a=\frac{1}{2 k}$,
 \begin{equation*}
  \begin{split}
   (\textup{A}_2) &\geq \E_{P^n} \left[ \sum_{k=1}^{m-1} \sum_{i=k M_n +1}^{(k+1) M_n} 2 k \log \left(1+ \frac{1}{2 k}\right) \frac{M_n-M_i}{2 i + M_i +1} \right] \\

    &\geq \E_{P^n} \left[ \sum_{k=h_n +1}^{m} \lambda_n \frac{M_n-M_{k M_n}}{2 k +2} \right].
  \end{split}
 \end{equation*}
\end{proof}

\begin{proof}[Proof of (\ref{eq:C1A3})]
 We have
 \begin{equation*}
  \begin{split}
   (\textup{A}_3) &= \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \Bigg[ \sum_{j\geq 1} P^n(M_n=j) \\
    &\qquad\qquad \times \Bigg( j \log n - \lambda_n j \sum_{k=h_n + 1}^{\left\lfloor \frac{n-1}{j} \right\rfloor} \frac{1}{k + 1} \Bigg) \Bigg].
  \end{split}
 \end{equation*}
 Then we plug in $h_n = \lfloor \ln n - 2 \rfloor$. For $n$ large enough, $h_n\geq 1$, and we have
 \begin{equation*}
  \begin{split}
   j \sum_{k=h_n + 1}^{\left\lfloor \frac{n-1}{j} \right\rfloor} \frac{1}{k + 1} &\geq j \int_{\ln n - 1}^{\left\lfloor \frac{n-1}{j} \right\rfloor + 1} \frac{\ud x}{x + 1} \\
   &= j\left( \ln \left(\left\lfloor\frac{n-1}{j}\right\rfloor + 2\right) - \ln (\ln n) \right) \\
   &\geq j \ln (n-1) - j \ln j - j \ln (\ln n),
  \end{split}
 \end{equation*}
 and therefore
 \begin{equation*}
  \begin{split}
   (\textup{A}_3) &\leq \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \big[(\log e - \lambda_n) \E[M_n] \ln n \\
    &\qquad\qquad + \lambda_n \E[M_n] \ln \frac{n}{n-1} \\
    &\qquad\qquad + \lambda_n \E[M_n \ln M_n] + \lambda_n \E[M_n] \ln (\ln n)\big].
  \end{split}
 \end{equation*}
 Then, if we use Lemma~\ref{lem:ExpectedMn} and the fact that $\lambda_n$ tends to $\log e$, we get (\ref{eq:C1A3}).
\end{proof}

\begin{proof}[Proof of (\ref{eq:C1A4})]
 We want to commute the expected value and the sum in $(\textup{A}_4)$. To do it, we need to get rid of $m$. We can note that the condition $k\leq m = \lfloor \frac{n-1}{M_n} \rfloor$ entails $k M_n \leq n-1$. Consequently, for $n$ big enough,
 \begin{equation*}
  \begin{split}
   (\textup{A}_4) &\leq \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} \left[ \sum_{k=3}^{m} \frac{M_{k M_n}}{k + 1} \right] \\
    &\leq \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} \left[ \sum_{k=3}^{n-1} \frac{M_{k M_n} \1_{k M_n \leq n-1}}{k + 1} \right] \\
    &\leq \sum_{k=3}^{n-1} \frac{\sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [M_{k M_n} \1_{M_n \leq l_n}]}{k + 1} \\
     &\quad + \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [M_{n} \1_{M_n > l_n}] \sum_{k=3}^{n-1} \frac{1}{k + 1},
  \end{split}
 \end{equation*}
 where $l_n = \left\lfloor \frac{1}{\alpha} \left( 2\ln n + \ln \frac{C}{1-e^{-\alpha}}\right) \right\rfloor$. We can now plug in the results of Lemma~\ref{lem:ExpectedMn}:
 \begin{equation*}
  \begin{split}
   (\textup{A}_4) &\leq \sum_{k=3}^{n-1} \frac{\ln (k l_n) + 1 + \ln \frac{C}{1-e^{-\alpha}}}{(k + 1)\alpha} + o(1) \sum_{k=3}^{n-1} \frac{1}{k + 1} \\
    &\leq \frac{1}{\alpha} \sum_{k=3}^{n-1} \frac{\ln k}{k + 1} + \frac{1}{\alpha} (\ln l_n + O(1)) \sum_{k=3}^{n-1} \frac{1}{k + 1}.
  \end{split}
 \end{equation*}
 Note that $l_n = O(\ln n)$, and consequently $\ln l_n = O(\ln \ln n)$. So
 \begin{equation*}
  \begin{split}
   (\textup{A}_4) &\leq \frac{1}{\alpha} \int_{3}^{n} \frac{\ln x}{x}\,\ud x + O(\ln \ln n) \int_{3}^{n} \frac{\ud x}{x} \\
    &\leq \frac{1}{2 \alpha} \ln^2 n + o(\ln^2 n).
  \end{split}
 \end{equation*}
\end{proof}

\subsection{Contribution of \textup{\texttt{C2}}} \label{sec:ContribC2Lemmas}

\begin{prop} \label{prop:ContribC2}
 Let $C$ and $\alpha$ be positive numbers satisfying $C > e^{2 \alpha}$. Then
 \[ \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [l(\textup{\texttt{C2}})] \leq o(\log^2 n). \]
\end{prop}

\begin{proof}
 Like in the previous subsection, we give first the sketch of the proof, and we delay several technical lemmas.
 \begin{multline*}
  \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [l(\textup{\texttt{C2}})] \\
  \leq 1 + \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \sum_{i=1}^{n} \E_{P^n} \left[  \1_{X_i>M_{i-1}} l_E(X_i+1) \right].
 \end{multline*}

  We deal with this sum thanks to the following lemma:
  \begin{lem} \label{lem:C2point1}
  Let $g$ be a positive and non-decreasing function on $[1,\infty)$. Let $(K_n)_{n\geq 1}$ be a non-decreasing sequence of positive integers. Then, for all $n\geq 1$,
  \begin{multline*}
    \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \sum_{i=1}^{n} \E_{P^n} \left[  \1_{X_i>M_{i-1}} g(X_i) \right]  \\
    \leq (1+o(1)) g(K_n) \frac{1}{\alpha} \ln n + C\, n \int_{K_n}^{\infty} g(x+1) e^{-\alpha x} \,\ud x.
  \end{multline*}
  \end{lem}

  To apply Lemma~\ref{lem:C2point1}, we extend the definition of $l_E$ on $[1,\infty)$ by
  \[ l_E(x) = \left\{ \begin{array}{ll} 1 & \text{if } x \in [1,2), \\ 1 + \lfloor \log x \rfloor + 2 \left\lfloor \log \lfloor \log x \rfloor + 1 \right\rfloor & \text{if } x\geq 2. \end{array} \right. \]
  We get
 \begin{multline*}
  \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [l(\textup{\texttt{C2}})] \\
  \leq (1+o(1)) \frac{l_E(K_n+1)}{\alpha} \ln n + C\, n \int_{K_n}^{\infty} l_E(x+2) e^{-\alpha x} \,\ud x
 \end{multline*}

  Then we can choose $K_n=\max \{1,\lfloor \frac{1}{\alpha} \ln n \rfloor\}$. This entails
  \[l_E(K_n+1) \underset{n \rightarrow \infty}{\sim} \log K_n \sim \log \log n = o(\log n),\]
  and therefore
  \[ \frac{1}{\alpha} l_E(K_n+1) \ln n = o(\log^2 n). \]

  The remaining term is treated by Lemma~\ref{lem:C2point2}, which achieves the proof of Proposition~\ref{prop:ContribC2}:

  \begin{lem} \label{lem:C2point2}
  Let $\alpha>0$ be a real number, and let $K_n=\max \{1,\lfloor \frac{1}{\alpha} \ln n \rfloor\}$. Then
  \[ n \int_{K_n}^{\infty} l_E(x+2) e^{-\alpha x} \,\ud x = o(\log n). \]
  \end{lem}
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:C2point1}]
 Let $\boldsymbol{P}$ be an element of $\Lambda_{C e^{-\alpha\cdot}}$. Let us define, for all $k\geq 0$,
 \[ \bar{p}(k) = P(X_1>k) = \sum_{j\geq k+1} P(k), \]
 and
 \[ (\textup{B}_1) = \sum_{i=1}^{n} \E_{P^n} \left[  \1_{X_i>M_{i-1}} g(X_i) \right]. \]
 Note that, for all $1\leq i\leq n$, $X_i$ and $M_{i-1}$ are independent random variables, and
 \begin{equation*}
  \begin{split}
   P^n(M_i \leq k) &= P^n(\forall\ 1\leq j \leq i,\ X_j \leq k) \\

    &= (1-\bar{p}(k))^i.
  \end{split}
 \end{equation*}
 Then we can write
 \begin{equation*}
  \begin{split}
   (\textup{B}_1) &= \sum_{i=1}^{n} \sum_{k\geq 0} P^n(M_{i-1} = k) \sum_{m\geq k+1} P(m) g(m) \\
    &= \sum_{m\geq 1} P(m) g(m) \sum_{i=1}^{n} \sum_{k=0}^{m-1} \Proba(M_{i-1} = k) \\

    &= P(1) g(1) + \sum_{m\geq 2} P(m) g(m) \sum_{i=1}^{n} (1-\bar{p}(m-1))^{i-1} \\
    &= \sum_{m\geq 1} P(m) g(m) \frac{1-(1-\bar{p}(m-1))^{n}}{\bar{p}(m-1)}.
  \end{split}
 \end{equation*}
 If we take $g(x)=1$ for all $x$, we get
 \begin{equation*}
  \begin{split}
   \sum_{m\geq 1} P(m) \frac{1-(1-\bar{p}(m-1))^{n}}{\bar{p}(m-1)} &= \E \left[ \sum_{i=1}^{n} \1_{X_i>M_{i-1}} \right] \\
    &\leq \E [M_n].

  \end{split}
 \end{equation*}
 In the general case, we can split the sum at $K_n$, and we get
 \begin{equation*}
  \begin{split}
   (\textup{B}_1) &= \sum_{m=1}^{K_n} P(m) g(m) \frac{1-(1-\bar{p}(m-1))^{n}}{\bar{p}(m-1)} \\
     &\qquad + \sum_{m\geq K_n+1} P(m) g(m) \frac{1-(1-\bar{p}(m-1))^{n}}{\bar{p}(m-1)} \\
    &\leq g(K_n) \sum_{m\geq 1} P(m) \frac{1-(1-\bar{p}(m-1))^{n}}{\bar{p}(m-1)} \\
     &\qquad + \sum_{m\geq K_n+1} n P(m) g(m) \\
    &\leq g(K_n) \E[ M_n] + C\, n \sum_{m\geq K_n+1} g(m) e^{-\alpha m}.
  \end{split}
 \end{equation*}
 At this point, we can take the supremum over all sources $\boldsymbol{P}$ in $\Lambda_{C e^{-\alpha\cdot}}$:
 \begin{equation*}
  \begin{split}
   &\sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \sum_{i=1}^{n} \E_{P^n} \left[  \1_{X_i>M_{i-1}} g(X_i) \right]  \\
   &\quad\leq (1+o(1)) g(K_n) \frac{1}{\alpha} \ln n + C\, n \int_{K_n}^{\infty} g(x+1) e^{-\alpha x} \,\ud x.
  \end{split}
 \end{equation*}
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:C2point2}]
 \begin{equation*}
  \begin{split}
   &n \int_{K_n}^{\infty} l_E(x+2) e^{-\alpha x} \,\ud x \\
    &\quad\leq n \int_{K_n}^{\infty} \left( \log (x+2) +2 \log \log (x+3) + 1 \right) e^{-\alpha x} \,\ud x \\
    &\quad\leq n e^{-\alpha K_n} \log (K_n+3) \\
     &\quad\qquad\int_{K_n +3}^{\infty} \frac{\log x +2 \log \log x + 1}{\log (K_n+3)} e^{-\alpha (x-K_n -3)} \,\ud x \\
    &\quad\leq e^{\alpha} \log (K_n+3) \left(\sup_{x\geq K_n+3} \frac{\log x +2 \log \log x + 1}{\log x}\right) \\
     &\quad\qquad \int_{K_n +3}^{\infty} \frac{\log x}{\log (K_n+3)} e^{-\alpha (x-K_n -3)} \,\ud x \\
    &\quad= O(\log K_n) \int_{0}^{\infty} \left(1+\frac{\log \left(1+\frac{x}{K_n+3}\right)}{\log (K_n+3)}\right) e^{-\alpha x} \,\ud x \\
    &\quad= o(\log n).
  \end{split}
 \end{equation*}
 The supremum is correctly defined and bounded, because the function
 \[ x \mapsto \frac{\log x +2 \log \log x + 1}{\log x} \]
 is continuous and tends to $1$ as $x$ tends to the infinity.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:ACcodeRedundancy}}

The message sent by the \textup{\texttt{ACcode}} algorithm is compound of two strings $\textup{\texttt{C1}}$ and $\textup{\texttt{C2}}$. $\textup{\texttt{C1}}$ corresponds to the part of the message encoded by the arithmetic code, with coding probability $Q^{n+1}$. The arithmetic code encodes a message $\widetilde{x}_{1:n}0$ with $\lceil - \log Q^{n+1}(\widetilde{x}_{1:n}0) \rceil +1$ bits. We have
 \begin{equation*}
 \begin{split}
  \E_{P^n} [- \log Q_{n+1}(0 | X_{1:n})]
   &= \E_{P^n} [\log (M_n +1 + 2n) ] \\

   &\leq \log (2n) + \frac{\E_{P^n} [ M_n+1 ]}{2n} \\

   &= O(\log n)
 \end{split}
 \end{equation*}
 thanks to Lemma~\ref{lem:ExpectedMn}. Therefore the redundancy of \textup{\texttt{ACcode}} can be upper bounded, for all $n\geq 2$, by
 \begin{multline*}
 \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [ l(\textup{\texttt{C1}})+l(\textup{\texttt{C1}})] - H(P^n)]  \\
  \begin{aligned}
   &\leq\sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [ - \log  Q^n(\widetilde{X}_{1:n}) - H(P^n) ] \\
   &\quad + \sup_{\boldsymbol{P} \in \Lambda_{C e^{-\alpha\cdot}}} \E_{P^n} [l(\textup{\texttt{C2}})] + O(\log n).
  \end{aligned}
 \end{multline*}
 We conclude thanks to Propositions~\ref{prop:ContribC1} and \ref{prop:ContribC2}.

\section*{Acknowledgment}

I wish thank Elisabeth Gassiat for her helpful advice, for the many ideas in this paper she suggested me, and for her constant availability to my questions.

Thanks also to Aur\'elien Garivier and to St\'ephane Boucheron for the useful discussions we had. I don't forget the ideas I got from my classmates, especially Rafik Imekraz.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi


TITLE: Minkowski content of a Cantor-like fractal
QUESTION [0 upvotes]: Let $K_0 = [0,1]$. Split $K_0$ into 4 intervals and remove the middle half. This gives $K_1 = [0,1/4] \cup [3/4, 1]$ and so on and set $K = \cap K_i$.
I computed the upper and lower Minkowski content of K and found that they are different, but how could I prove this without evaluating them?
Many thanks in advance!

REPLY [1 votes]: The $s$-dimensional upper and lower Minkowski contents, up to some constant factor (same for both), are $$\limsup_{r\to 0}\ r^{s-1}|K_r| \quad \text{ and }\quad \liminf_{r\to 0}\ r^{s-1}|K_r| $$ where $|K_r|$ is the Lebesgue measure of the $r$-neighborhood of the set $K$. It suffices to exhibit two sequences $r_n\to 0$ and $r_n'\to 0$ along which $|K_r|$ follows two different patterns.
When $r = 4^{-n}$, the set $K_r$ is the $r$-neighborhood of $K_{n-1}$ (all gaps of size $2r$ and smaller are closed). Therefore, $K_r $ consists of $2^{n-1}$ intervals of size $4^{1-n}+2r$. This adds up to
$$|K_r| = 2^{1-n} + 2^{-n} = 3\cdot 2^{-n},\qquad r = 4^{-n} \tag1$$
When $r = 2 \cdot 4^{-n}$, the set $K_r$ still consists of $2^{n-1}$ intervals of size $4^{1-n}+2r$. This adds up to
$$|K_r| = 2^{1-n} + 2^{1-n} = 4\cdot 2^{-n},\qquad r = 2\cdot 4^{-n} \tag2$$
Since $s=1/2$, the values of $r^{s-1}|K_r|$ between (1) and (2) are different.

Nothing special about $2$ here: $r = x\cdot 4^{-n}$ would work for $x\in (1,4)$. The idea is that in this range of scales the size of $r$-neighborhood grows linearly,  which does not exactly match the fractional dimension of the set.


TITLE: There are 14 students: 8 girls and 6 boys. In how many ways can you make a 4-student committee which has at least one boy?
QUESTION [0 upvotes]: In a group of $14$ students there are $8$ girls and $6$ boys. Determine the number of ways that a committee of $4$ students which has at least $1$ boy can be chosen from the group.
Here is what I have so far:
Method $1$
If there is $1$ boy: $(^6C_1)\cdot (^8C_3) = 336$
If there are $2$ boys: $(^6C_2)\cdot (^8C_2)= 420$
If there are $3$ boys: $(^6C_3)\cdot (^8C_1) = 160$
If there are $4$ boys: $(^6C_4)\cdot (^8C_0)= 15$
$336+420+160+15 = 931$
I was confident in this answer, until I tried solving another way.
Method $2$
number of comittees with at least one boy = total number of committees possible – number of comittees with zero boys
$=(^{14}C_4)\cdot (^8C_8) = 1000$
Why are my two answers different?
EDIT:
Method $2$ should be as follows:
$= (^{14}C_4)-(^8C_4)$
$= 931$

REPLY [2 votes]: Method 2 should be $14\choose 4$-$8\choose 4$.
That will give you 931.

REPLY [1 votes]: I think in the last step, you wanted to write $^{14}C_4-^8C_8=1000?$ In that case, why $^8C_8?$ From $8$ girls, you are choosing $4$ girls, so you should subtract $^8C_4$. Then you get 931.


TITLE: Equivalent definitions of Hyperkahler manifolds.
QUESTION [1 upvotes]: I am reading the paper HYPERKAHLER METRICS ON COTANGENT BUNDLES OF ¨
HERMITIAN SYMMETRIC SPACE by OLIVIER BIQUARD AND PAUL GAUDUCHON.
Suppose $M$ is a manifold with a triple $(g,I,J)$ where g is a metric and $I,J$ are anti-commuting $g$ orthogonal almost complex structures. Then in the paper $M$ is said to be hyperkahler if and only if

$d\omega_I=d\omega_J=d\omega_K=0$
where $K=IJ$. (And this would imply $I,J,K$ are integrable almost complex structures.)

Now suppose $M$ is the cotangent bundle $T^*\Sigma$ of a complex manifold $\Sigma$. Let $I$ be the complex structure induced from the complex structure of $\Sigma$. Let $J$ a $(1,1)$ tensor such that $\omega_J=g(J(\cdot),\cdot)$ is equal to the canonical symplectic form of $M$ as a contangent bundle.
Then the paper claims that $(g,I,J)$ being Hyperkahler is equivalent to the following conditions:

$g(I(\cdot),I(\cdot))=g(\cdot,\cdot)$

$J^2=-1$

$d\omega_I=0$  where $\omega_I=g(I(\cdot),\cdot)$.

But from these conditions, I can only obtain that

$d\omega_I=d\omega_J=0$, and $\nabla I=0$.

So my problem is, are these conditions equivalent to saying that $M$ is hyperKahler? Any help or hints or reference are appreciated. Thank you in advanced.

REPLY [1 votes]: Let $\omega_c$ be the holomorphic symplectic form on $T^*\Sigma$. Then $\omega_c(IX,IY) = - \omega_c(X,Y)$, since $\omega_c$ is of type $(2,0)$ with respect to $I$. Taking the real part on both sides, we get:
$$\omega_J(IX,IY) = -\omega_J(X,Y).$$
Therefore we have
$$g(JIX,IY) = -g(JX,Y) = -g(IJX,IY).$$
And since this is true for any $X$ and $Y$, this implies that $IJ = -JI$.
Moreover, since $K = IJ$ and since $\omega_J$ is of type $(2,0)$ with respect to $I$, therefore $\omega_K$ is the imaginary part of $\omega_c$, and it follows that $\omega_K$ is also closed, so that $(g,I,J)$ is hyperkähler, assuming the $3$ conditions you wrote down.


TITLE: Canonical Vector Bundle associated to a complete intersection
QUESTION [0 upvotes]: I am constructing the algebraic cycle of an analytic set that is local complete intersection in a algebraic smooth variety using Chern classes.
-I would like to know which in the canonical Vector bundle associated to a local complete intersection, to just do the explicit calculation. (Can we do it even more explicit as in the case of the hypersurfaces?)

REPLY [2 votes]: Suppose $X$ is a  complex manifold and let $Y\subset X$ be a divisor.
This means that you are given a covering $(U_i)_{i\in I}$ of $X$ and a family of holomorphic functions $(f_i)_{i\in I}$ with $f_i\in \mathcal O(U_i)$ and that these data are submitted to the condition that there exists $g_{ij}\in \mathcal O^*(U_{i}\cap U_{j})$ (non-vanishing holomorphic functions ) such that $f_i=g_{ij}f_j$ on $U_{i}\cap U_{j}$.
You can then construct a line bundle  $\mathcal O(D)$ on $X$ thanks to the cocycle $g_{ij}$ and the restriction $\mathcal O(D)\mid D$ of that line bundle to $D$ is the conormal sheaf of $D$ in $X$.
If $D$ is smooth it is  indeed the dual of the normal bundle, as the name implies: $$\mathcal O(D)\mid D=N^*(Y/X)=(\frac {T(X)\mid Y}{T(Y)})^*$$
The condition for $D$ to be smooth is that for every $i\in I$ the differential $d_yf_i\in T^*_y(X)$ be non-zero at each $y\in Y\cap U_i$.
The case of  codimension higher than $1$ is  more complicated.
However if $i: Y\hookrightarrow X$ is a local complete intersection defined by the sheaf $\mathcal I_Y\subset \mathcal O_X$, you still have  a locally free normal sheaf  on $Y$ defined by $\mathcal N(Y/X)=\mathcal Hom_{\mathcal O_Y}(\mathcal I_Y/\mathcal I_Y^2,\mathcal O_Y)$ .
Here  is an online document on the subject, extracted from De Jong and collaborators' Stacks Project (look at section 33).