\documentstyle[12pt,draft]{article}
\tolerance 450

\def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm
T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox
to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox
to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox
to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}}
\def\bbbr{{\rm I\!R}} %reelle Zahlen
\def\bbbz{{\mathchoice {\hbox{$\sf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\sf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\sf\scriptstyle Z\kern-0.3em Z$}}
{\hbox{$\sf\scriptscriptstyle Z\kern-0.2em Z$}}}}
\def\bbbn{{\rm I\!N}} %natuerliche Zahlen
\def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox
to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox
to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox
to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox
to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}}
\def\bbbs{{\mathchoice
{\setbox0=\hbox{$\displaystyle     \rm S$}\hbox{\raise0.5\ht0\hbox
to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox
to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle        \rm S$}\hbox{\raise0.5\ht0\hbox
to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox
to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle      \rm S$}\hbox{\raise0.5\ht0\hbox
to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox
to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox
to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox
to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}}

\newcommand{\square}{\Box}
\newcommand{\infp}{\mathop{\rm inf\vphantom p}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\ov}{\overline}
\newcommand{\Ker}{\mathop{\rm Ker}\nolimits}
\newcommand{\cl}{\mathop{\rm cl}\nolimits}
\newcommand{\ch}{\mathop{\rm ch}\nolimits}
\newcommand{\co}{\mathop{\rm co}\nolimits}
\newcommand{\overset}[2]{\buildrel#1\over#2}
\newcommand{\spa}{\mathop{\rm span}\nolimits}
\newcommand{\supp}{\mathop{\rm supp}\nolimits}

\renewcommand{\abstractname}{\ }
\renewcommand{\refname}{\large\sc\hfil References\hfil}

\newcommand{\eqalign}[1]{\null\,\vcenter{\openup\jot\mathsurround=0pt
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqlines#1#2#3{\refstepcounter{equation}\label{#1}$$\displaylines{
\quad#2\hfill\cr\hfill#3\quad(\theequation)}$$}

\def\lines#1#2{$$\displaylines{\quad#1\hfill\cr\hfill#2\quad}$$}
\def\multlines#1#2#3{$$\displaylines{\quad#1\hfill\cr#2\cr\hfill#3\quad}$$}
\def\teqmultlines#1#2#3#4{$$\displaylines{\quad#1\hfill\cr#2\cr\hfill#3
\quad(#4)}$$}
\def\eqmultlines#1#2#3#4{\refstepcounter{equation}\label{#1}$$\displaylines{
\quad#2\hfill\cr#3\cr\hfill#4\quad(\theequation)}$$}


\newcommand{\at}[2]{{\scriptstyle#1\atop\scriptstyle#2}}
\newcommand{\dfrac}[2]{\displaystyle\frac{#1}{#2}}

\newcounter{theorem}
\newcounter{cor}
\newcounter{lemma}
\newcounter{pro}
\newenvironment{theorem}{\trivlist\refstepcounter{theorem}%
\itemindent=\parindent\item[\hspace{%
\labelsep}\sc Theorem\ \thetheorem.]\it}{\endtrivlist}

\def\thtext[#1]{\trivlist\refstepcounter{theorem}%
\itemindent=\parindent\item[\hspace%
{\labelsep}\sc Theorem\ \thetheorem\ (#1).]\it}
\newenvironment{Theorem}{\thtext}{\endtrivlist}

\newenvironment{cor}{\trivlist\refstepcounter{cor}%
\itemindent=\parindent\item[\hspace{%
\labelsep}\sc Corollary\ \thecor.]\it}{\endtrivlist}
%\newtheorem{theorem}{\sc\hskip\parindent Theorem}
%\newcommand{\thecor}{\arabic{theorem}}
\newenvironment{lemma}{\trivlist\refstepcounter{lemma}%
\itemindent=\parindent\item[\hspace{%
\labelsep}\sc Lemma\ \thelemma.]\it}{\endtrivlist}
\newenvironment{pro}{\trivlist\refstepcounter{pro}%
\itemindent=\parindent\item[\hspace{%
\labelsep}\sc Proposition\ \thepro.]\it}{\endtrivlist}
\newenvironment{proof}{\trivlist\itemindent=\parindent\item[\hspace{%
\labelsep}\it Proof.]}{\endtrivlist}

\begin{document}

\title{On Exact Values of $n$-Widths in a Hilbert Space\thanks{This
research was supported in part by the Russian Foundation for Basic Research
(Grants \#96-01-10035 and \#99-01-01181), the State Program on Support of
Leading Scientific Schools (Grant \#96-15-96072), and INTAS--OPEN \#97-1050.}}

\date{}
\maketitle

\vspace{-60pt}
\begin{center}
\large Georgii G.~Magaril-Il'yaev\\
\smallskip
\small\it Department of Mathematics, Moscow State Institute of Radio
Engineering, Electronics and Automation (Technology University),\\
Moscow 117454, pr.~Vernadskogo 78, Russia
\end{center}

\begin{center}
\large Konstantin Yu.~Osipenko\\
\smallskip
\small\it
Department of Mathematics, MATI --- Russian State Technological University,
Moscow 121552, Orshanskaya 3, Russia
\end{center}

\begin{center}
\large Vladimir M.~Tikhomirov\\
\smallskip
\small\it
Department of Mechanics and Mathematics, Moscow State University,\\
Moscow 119899, Vorobjovy Gory, Russia
\end{center}

\begin{abstract}
There are two basic classes of functions for which the exact values of
Kolmogorov $n$-widths have been calculated. They are, on the one hand,
classes of real functions defined by variation diminishing kernels and
similar classes of analytic functions, and, on the other hand, classes of
functions in a Hilbert space which are elliptical cylinders or generalized
octahedra (see \cite {1,2}). This paper is devoted to a survey and to new
results in this second case. For $n$-widths of ellipsoids, elliptic
cylinders, and generalized octahedra upper bounds for the $n$-widths are
based on the Fourier method. The lower bounds are based on the method of
``embedded balls'' (see \cite1) for ellipsoids, and the method of averaging
for generalized octahedra. General theorems concerning elliptical cylinders
and generalized octahedra are proved in Section~1 and Section~2. In
Section~3 various corollaries from these general theorems are considered.
Some additional problems (average $n$-widths, extremal spaces for an
ellipsoids and octahedra, etc) are discussed in Section 4.
\end{abstract}

\section*{\large\sc\hfil Introduction\hfil}

\hspace{\parindent}Let $H$ be a Hilbert space and $C\subset H$ a centrally
symmetric set. For $n \in\bbbz_+$ the {\it Kolmogorov $n$-widths} of $C$ in
$H$ are given by
$$d_n(C,H)=\infp_{L_n}\sup_{x\in C}\infp_{y\in L_n}\|x-y\|_H,$$
where the left-most infimum is taken over all $n$-dimensional linear
subspaces $L_n$ of $H$.

Let $r\in\bbbn$ and $1\le p\le\infty$. Denote by $W_p^r(\bbbt)$ ($\bbbt=[0,
2\pi)$) the Sobolev class of $2\pi$-periodic functions whose $(r-1)$-st
derivative is absolutely continuous and
$$\|x^{(r)}\|_{L_p(\bbbt)}:=\left(\int_{\bbbt}|x^{(r)}(t)|^p\,dt\right)^{1/
p}\le1.$$

The subject considered in this paper goes back to two papers by Kolmogorov.
In \cite3 Kolmogorov proved the formula
$$d_{2n-1}(W_2^r(\bbbt),L_2(\bbbt))=d_{2n}(W_2^r(\bbbt),L_2(\bbbt))=n^{-r}.
$$
In the paper of Kolmogorov, Petrov, Smirnov \cite4, which was supplemented
by Maltsev \cite5, the equality
\begin{equation}\label1
d_n(Bl_1^N,l_2^N)=\sqrt{\frac{N-n}N},
\end{equation}
where
$$l_p^N:=\left\{\,x=(x_1,\ldots,x_N)\in\bbbr^N\Bigm|\|x\|^p_{l_p^N}:=\sum_{
k=1}^N|x_k|^p\,\right\},\quad 1\le p<\infty,$$
and $Bl_1^N$ is the unit ball in $l_1^N$ was, in fact, proved. The authors
of these papers did not actually state, that they had calculated $n$-widths.
This was noted by Stechkin \cite6). Note that the Sobolev class $W_2^r(
\bbbt)$ is an elliptical cylinder (it is the orthogonal sum of the
one-dimensional space of constants and compact ellipsoid) and $Bl_1^N$ is a
regular octahedra in $\bbbr^N$. We consider generalizations of these two
results.

\section*{\large\sc\hfil1. $n$-Widths of Ellipsoids and Elliptical
Cylinders\hfil}

\hspace{\parindent}An {\it ellipsoid} is the image of a ball of a Hilbert
space under a linear continuous mapping. If $H$ and $H_1$ are Hilbert
spaces, $BH$ is the unit ball in $H$, and $T\colon H\to H_1$ is a linear
continuous operator, then $T(BH)$ is an ellipsoid which we denote by $E(T)
$. Let $L$ be a finite-dimensional subspace in $H_1$. We call the orthogonal
sum of an ellipsoid $E(T)$ and $L$
$$E(T)\oplus L=\{\,y=y_1+y_2\in H_1\mid y_1\in E(T),\ y_2\in L,\ y_1\mbox
{\large$\scriptstyle\perp$}y_2 \,\}$$
an {\it elliptical cylinder with base $E(T)$ and generalized axis} $L$.

Denote by $N$, $0\le N\le\infty$ the dimension of $\spa E(T)$.
Further we calculate the $n$-widths of compact ellipsoids and elliptical
cylinders with compact base.

Let $T$ be a compact operator. By the Hilbert--Schmidt theorem (see, for
example, \cite[page~231]{7}) for the self-adjoint compact operator $T'T$
($T' $ is the adjoint operator to $T$) there exists an orthonormal system
of eigenvectors $\{e_k\}_ {k\ge1}$ which corresponding to eigenvalues $s_k^
2$, $s_k \downarrow0$, $s_k\ne0$, such that each element $x\in H$ has the
unique representation
\begin{equation}\label{HS}
x=\sum_{k\ge1}\la x,e_k\ra e_k+\xi,
\end{equation}
where $\xi\in\Ker T$. (The numbers $s_k$ are called the $s$-{numbers\/} of
$T$.)

The following theorem was proved by many authors (see Comments below).

\begin{Theorem}[$n$-widths of compact ellipsoids]\label{Th1}
Let $H$ and $H_1$ be Hil\-bert spaces, $T\colon H\to H_1$ a compact operator,
$C=E(T)\oplus L_m$ $(\dim E(T)=N$, $\dim L_m=m)$ and $n\in\bbbz_+$. Then
$$d_n(C,H_1)=\cases{\infty,&$n<m$,\cr
s_{n+1-m},&$m\le n\le N+m$,\cr
0,&$n> N+m$.}$$
The linear, Gel'fand, and Bernstein $n$-widths satisfy the same equalities.
\end{Theorem}

\begin{proof}
We prove the theorem for the Kolmogorov $n$-width. The statement of the
theorem for the cases when $n<m$ and $n>N+m$ may be easily checked. Let $n<
N$ and for simplicity assume $m=0$ (the general case easily follows from
this). The upper bound will be proved by the {\it Fourier method}. Let $y
\in E(T)$ that is $y=Tx$, $\|x\|_H\le1$. By (\ref{HS}) $y=\sum_{k\ge1}\la x
,e_k\ra Te_k$ and $\|x\|^2_H=\sum_{k\ge1}|\la x,e_k\ra|^2+\|\xi\|^2_H\le1$.
Let us approximate $y$ by $S_ny=\sum_{k=1}^n\la x,e_k\ra Te_k$. Then taking
into account the orthogonality of the system $\{Te_k\}$, we have
$$\|y-S_ny\|^2_{H_1}=\sum_{k\ge n+1}s_k^2|\la x,e_k\ra|^2\le s_{n+1}^2\sum_
{k\ge n+1}|\la x,e_k\ra|^2\le s_{n+1}^2.$$
The upper bound is proved. The lower bound will be proved by the method of
{\it embedded balls}. We consider the $n+1$-dimensional subspace $\widehat
L=\spa\{Te_k\}_{k=1}^{n+1}$ of $H_1$ and show that the set $s_{n+1}BH_1\cap
\widehat L$ lies in $E(T)$. Let $y\in s_{n+1}BH_1\cap\widehat L$. Then $y=
\sum_{k=1}^{n+1}y_kTe_k$ and $\|y\|^2_{H_1}=\sum_{k=1}^{n+1}y_k^2s_k ^2\le
s_{n+1}^2$. If $x=\sum_{k=1}^{n+1}y_ke_k$, then it is clear that $y=Tx$ and
since
$$\|x\|_H^2=\sum_{k=1}^{n+1}y_k^2=\sum_{k=1}^{n+1}\frac{y_k^2 s_k^2}{s_k^2}
\le\frac1{s_{n+1}}\sum_{k=1}^{n+1}y_k^2s_k^2\le1,$$
we obtain that $s_{n+1}BH_1\cap\widehat L\subset E(T)$. By the theorem on $
n$-widths of a ball (see, for example, \cite[p.~12]2) which is trivial for
a Hilbert space, we have $d_n\left(E(T),H_1\right)\ge d_n\left(s_{n+1}BH_1
\cap\widehat L,H_1\right)=s_{n+1}$.$\quad\rule{5pt}{12pt}$
\end{proof}

\section*{\large\sc\hfil2. $n$-Widths of generalized octahedra\hfil}

\hspace{\parindent}In finite-dimensional geometry an octahedra is the
convex hull of a simplex with a vertex at the origin and simplex symmetric to
it. For octahedra which are so defined there is no known general method for
calculating its $n$-widths. But it is possible to calculate $n$-widths for
octahedra in $\bbbr^N$ which are the convex hull of the vectors $\{\pm f_k
\}$, $1\le k\le N$ obtained from one vector $K=(k_1,\ldots,k_N)$ by cyclical
permutation. Such octahedra may be considered as Sobolev classes $W_1^K(
\bbbz_N)$ consisting of functions $y=(y_1,\ldots,y_N)$ on the cyclical group
of order $N$ defined by a convolution
$$W_1^K(\bbbz_N)=\{\,y\in\bbbr^N\mid y=K*x,\ \|x\|_{l_1^N}\le1\,\},$$
where $x=(x_1,\ldots,x_N)$, $y_i=\sum_{j=1}^Nk_{i+j-1}x_j$, and the
summation is carried out modulo $N$. The regular octahedra can be defined
in this same way as a convolution class on the cyclical group $\bbbz_N$
with the kernel $K$ equal to $1$ at the zero of the group and $0$ at all
other elements.

It gives us the possibility to consider generalized Sobolev classes of
so-called sourcewise represented functions which are similar to generalized
octahedra.

First we recall some definitions (details may be found in~\cite8). Let $G$
be a compact group with Haar measure $\mu$ ($\mu(G)=1$). Let $\{T^\alpha\}_
{\alpha\in\cal A}$ (where $\cal A$ is at most a countable set) be a
complete system of finite-dimensional nonreducible unitary representations
of $G$. For each $\alpha\in\cal A$ we denote by $t^\alpha_{ij}(\cdot)$, $i,
j=1,\ldots, n_\alpha=\dim T^\alpha$, the matrix elements of the
representation $T^\alpha$ in some orthonormal basis. These functions are
continuous and the functions $\{\sqrt{n_\alpha}t^\alpha_{ij}(\cdot)\}$, $
\alpha\in\cal A$, $i, j=1,\ldots,n_\alpha$ form an orthonormal basis in $L_
2(G)$. Note that if $G$ is an Abelian group, then all representations $T^
\alpha$, $\alpha\in\cal A$, are one-dimensional. For each $\alpha\in\cal A$
and $1\le j\le n_\alpha$ set $H^\alpha_j=\spa\{t^\alpha_{ij}(\cdot)\mid i=1
,\ldots,n_\alpha\}$. The space $L_2(G)$ is represented as the direct sum of
those spaces which are left translation-invariant.

A set $X$ is called a {\it homogeneous $G$-space} if the group $G$ acts
transitively on $X$. In other words, if there exists a map $G\times X\to X$,
$(g,x)\to gx$ such that $(g_2g_1)x=g_2(g_1x)$, $ex=x$ ($e$ is the unity
element of $G$) for all $g_1,g_2\in G$ and $x\in X$ and in addition for
every $x_1,x_2\in X$ there exists a $g\in G$ for which $x_2=gx_1$. It is
obvious that any group $G$ is a homogeneous $G$-space with respect to the
operation $(g,g_0)\to gg_0$.

Let $x_0\in X$, $H=\{g\in G\mid gx_0=x_0\}$ and $G/H$ be the set of (left)
residue classes of group $G$ on the subgroup $H$. Consider the map $p\colon
X\to G/H$ which associates $x$ with the residue class $gH$ such that $gx_0=
x$. The map $p$ is a one-to-one mapping. Thus any function on $X$ may be
considered as a function on $G$, which is constant on  the residue classes.
By virtue of this fact for any topological homogeneous $G$-space $X$ with
compact group $G$ and measure $\nu$ invariant with respect to $G$ (that is
$\nu(A)=\nu(gA)$ for any measurable subset $A\subset X$ and $g\in G$) the
structure of $L_2(X)$ is analogous to the structure of $L_2(G)$. More
precisely $L_2(X)$ is a direct sum of at most an enumerable set of
finite-dimensional subspaces $H_k$ invariant with respect to $G$ consisting
of continuous functions.

We will need the following auxiliary result.

\begin{lemma}\label{L}
Let $X$ be a topological homogeneous $G$-space with compact group $G$ and
probability measure invariant with respect to $G$. If $\{e_k(\cdot)\}_{k=1}
^n$ is an orthonormal system of continuous functions from $L_2(X)$ such that
$L_n=\spa\{e_k(\cdot)\}_{k=1}^n$ is invariant with respect to $G$, then
$$\sum_{k=1}^n|e_k(\cdot)|^2\equiv n.$$
\end{lemma}

\begin{proof}
For $x\in X$ consider the function
$$\xi_x(\cdot)=\sum_{k=1}^n\ov{e_k(x)}e_k(\cdot).$$
If $y(\cdot)\in L_n$ then it is clear that
\begin{equation}\label{i}
\la y(\cdot),\xi_x(\cdot)\ra=y(x).
\end{equation}
Let $x_1,x_2\in X$ and $g\in G$ such that
\begin{equation}\label{ii}
x_2=gx_1.
\end{equation}
Using the invariance of the measure, (\ref i), and (\ref{ii}), for every $y(
\cdot)\in L_n$ we have
$$\la y(\cdot),\xi_{x_2}(g\cdot)\ra=\la y(g^{-1}\cdot),\xi_{x_2}(\cdot)\ra=
y(g^{-1}x_2)=y(x_1)=\la y(\cdot),\xi_{x_1}(\cdot)\ra.$$
Thus $\xi_{x_2}(g\cdot)=\xi_{x_1}(\cdot)$. Substituting here $x_1$ we obtain
that
$$\sum_{k=1}^n|e_k(x_1)|^2=\sum_{k=1}^n|e_k(x_2)|^2=C.$$
Since the given measure is a probability measure and the system $\{e_k(\cdot
)\}_{k=1}^n$ is orthonormal we have
$$C=\int_X\sum_{k=1}^n|e_k(x)|^2\, d\mu(x)=n.\quad\rule{5pt}{12pt}$$
\end{proof}

Let $X$ be a topological homogeneous $G$-space with compact group $G$ and
probability measure invariant with respect to $G$. As was mentioned, in this
case $L_2(X)$ may be represented in the form
$$L_2(X)=\sum_{k\ge1}H_k,\quad \dim H_k=n_k<\infty,$$
where the $H_k$ are shift-invariant spaces of continuous functions.
Consider the classes of functions represented as a convolution with kernels
\begin{equation}\label{Ker}
K(t,\tau)=\sum_{k\ge1}\sum_{j=1}^{n_k}\gamma_{kj}e_{kj}(t)\ov{e_{kj}(\tau)},
\end{equation}
where the $\{e_{kj}(\cdot)\}_{j=1}^{n_k}$ is an orthonormal basis for $H_k$
of continuous functions and $\gamma_{kj}\in\bbbc$ such that
\begin{equation}\label{Gamma}
\sum_{k\ge1}n_k\max_{1\le j\le n_k}|\gamma_{kj}|^2<\infty.
\end{equation}

The function $K(\cdot,\cdot)$ induces the operator
$$Ax(t)=\int_XK(t,\tau)x(\tau)\,d\mu(\tau).$$
We show that $A$ is a continuous operator from $L_1(X)$ into $L_2(X)$.
Indeed, by the Cauchy--Bunyakovsky inequality for all $t\in X$
\lines{|Ax(t)|\le\int_X\left(|K(t,\tau)|^2|x(\tau)|\right)^{1/2}|x(\tau
)|^{1/2}\,d\mu(\tau)}
{\le\left(\int_X|K(t,\tau)|^2|x(\tau)|\,d\mu(\tau)\right)^{1/2}\|x(\cdot)\|_
{L_1(X)}^{1/2}.}
Squaring this inequality, integrating it, and then changing the order of
integration, we obtain
\lines{\|Ax(\cdot)\|_{L_2(X)}^2\le\|x(\cdot)\|_{L_1(X)}^2\sup_{t\in X}\int_X|K(t,
\tau)|^2\,d\mu(\tau)}
{=\|x(\cdot)\|_{L_1(X)}^2\sup_{t\in X}\|K(t,\cdot)\|^2_{
L_2(X)}.}
According to the Parseval equality for all $t\in X$
$$\|K(t,\cdot)\|^2_{L_2(X)}=\sum_{k\ge1}\sum_{j=1}^{n_k}|\gamma_{kj}|^2|e_{k
j}(t)|^2.$$
By Lemma~\ref{L} $\sum_{j=1}^{n_k}|e_{kj}(t)|^2=n_k$. In view of (\ref
{Gamma}) we have that $\|K(t,\cdot)\|_{L_2(X)}\le C$. Therefore $A\colon L_
1(X)\to L_2(X)$ is a continuous operator.

Set
$$W_1^K(X)=\{\,y(\cdot)\in L_2(X)\mid y(\cdot)=Ax(\cdot),\ \|x(\cdot)\|_{L_
1(X)}\le1\,\}.$$

\begin{theorem}\label{Th2}
Let $X$ be a topological homogeneous $G$-space with compact group $G$ and
probability measure invariant with respect to $G$. Let $K\colon X\times X\to
\bbbc$ be a function of the form $(\ref{Ker})$, where the $\gamma_{kj}$
satisfy the additional condition $|\gamma_{kj}|=\lambda_k$, $1\le j\le n_k$,
$k\ge1$. Assume that $\{\lambda_k\}_{k\ge1}$ are in decreasing order. Then
for all $n=n_1+\ldots+n_s$ $$d_n(W_1^K(X),L_2(X))=\biggl(\sum_{k\ge s+1}
\lambda_k^2n_k\biggr)^{1/2}.$$
\end{theorem}

\begin{proof}
Since $W_1^K(X)=\cl\co\{K(\cdot,\tau)\}_{\tau\in X}$ it is sufficient to
prove the statement of the theorem for the set $\{K(\cdot,\tau)\}_{\tau\in
X}$.

{\sl The upper bound.} We use the Fourier method projecting our class on
the subspace $L_n=\spa\{e_{kj}(\cdot)\mid1\le j\le n_k,\ 1\le k\le s\}$.
Then for any $\tau\in X$ using the Parseval equality, hypothesis of the
theorem, and Lemma, we have $$d^2(K(\cdot,\tau),L_n,L_2(X))=\sum_{k\ge
s+1}\lambda_k^2n_k.$$ Hence the required estimate follows.

{\sl The lower bound.} We use the method of averaging. Let $L_n$ be an
$n$-dimen\-sional subspace of $L_2(X)$, and $\{f_m\}_{m=1}^n$ an orthonormal
basis of $L_n$. Then for all $\tau\in X$
\begin{equation}\label{i1}
d^2(K(\cdot,\tau),L_n,L_2(X))=\|K(\cdot,\tau)\|_{L_2(X)}^2-\sum_{m=1}^n
\left|\int_XK(t,\tau)\ov{f_m(t)}\,d\mu(t)\right|^2.
\end{equation}
In view of the hypothesis of the theorem and by Lemma~\ref{L} we have
\begin{equation}\label{ii1}
\|K(\cdot,\tau)\|_{L_2(X)}^2=\sum_{k\ge1}\sum_{j=1}^{n_k}|\gamma_{kj}|^2|
e_{kj}(t)|^2=\sum_{k\ge1}\lambda_k^2\sum_{j=1}^{n_k}|e_{kj}(t)|^2=\sum_{k
\ge1}\lambda_k^2n_k.
\end{equation}
Furthermore,
$$\left|\int_XK(t,\tau)\ov{f_m(t)}\,d\mu(t)\right|^2=\biggl|\sum_{k\ge1}
\sum_{j=1}^{n_k}\gamma_{kj}\ov{e_{kj}(\tau)}\int_X e_{kj}(t)\,\ov{f_m(t)}\,
d\mu(t)\biggr|^2.$$
Substituting it and (\ref{ii1}) into (\ref{i1}), integrating the obtained
expression and using the Parseval equality with the hypothesis of the
theorem, we obtain
\eqmultlines{iii1}{\int_Xd^2(K(\cdot,\tau),L_n,L_2(X))\,d\mu(\tau)}
{=\sum_{k\ge1}\lambda_k^2n_k-\sum_{m=1}^n\sum_{k\ge1}\sum_{j=1}^{n_k}|
\gamma_{kj}|^2\left|\int_X e_{kj}(t)\ov{f_m(t)}\,d\mu(t)\right|^2}
{=\sum_{k\ge1}\lambda_k^2n_k-\sum_{m=1}^n\sum_{k\ge1}\lambda_k^2\sum_{j=1}^
{n_k}\left|\int_X e_{kj}(t)\ov{f_m(t)}\,d\mu(t)\right|^2.}
For $k\ge1$ set
$$\widehat c_k=\sum_{m=1}^n\sum_{j=1}^{n_k}\left|\int_X e_{kj}(t)\ov{f_m(t)
}\,d\mu(t)\right|^2.$$
It is easy to check that $0\le\widehat c_k\le n_k$ and $\sum_{k\ge1}
\widehat c_k=n_1+\ldots+n_s$. Consider the problem of linear programming
$$\sum_{k\ge1}\lambda_k^2c_k\to\max,\quad0\le c_k\le n_k,\quad\sum_{k\ge1}c
_k=n_1+\ldots+n_s.$$
The solution of this problem is evidently
$$c_k=n_k,\ 1\le k\le s,\quad c_k=0,\ k\ge s+1$$
(we recall that $\lambda_1\ge\lambda_2\ge\ldots$).
Thus we obtain the lower bound for the left-hand side of (\ref{iii1})
$$c_k=n_k,\ 1\le k\le s,\quad c_k=0,\ k\ge s+1.$$
Standard arguments now lead to the required estimate. $\quad\rule{5pt}
{12pt}$
\end{proof}

\section*{\large\sc\hfil3. Corollaries from the general theorems\hfil}

\hspace{\parindent}We begin with $n$-widths of convolution classes of
functions defined on a compact group. Let $G$ be a compact group and
$K(\cdot)\in L_2(G)$. The operator of convolution is defined as
\begin{equation}\label{Con}
Tx(g)=\int_GK(gs^{-1})x(s)\,d\mu(s).
\end{equation}
It is a compact operator from $L_2(G)$ into $L_2(G)$. Moreover, it follows
from the Minkowski inequality that (\ref{Con}) is a continuous operator from
$L_1(G)$ into $L_2(G)$. Set
$$W_p^K(G)=\left\{\,y(\cdot)\in L_2(G)\mid y(\cdot)=Tx(\cdot),\ \|x(\cdot)
\|_{L_p(G)}\le1\,\right\},\quad p=1,2.$$

\begin{theorem}
Let $G$ be a compact group and $K(\cdot)\in L_2(G)$ be such that its Fourier
coefficients $c_{ij}^\alpha$ when expanded in the orthonormal basis $e_{ij}
^\alpha(\cdot)=\sqrt{n_\alpha}t_{ij}^\alpha(\cdot)$, $\alpha\in\cal A$, $i,
j=1,\ldots,n_\alpha$, satisfy the condition: for any $\alpha\in\cal A$ the
matrix $C_\alpha=\left(c_{ij}^\alpha\right)_{i,j=1}^{n_\alpha}$ has the form
$\lambda_\alpha U_\alpha$ where $\lambda_\alpha\in\bbbc$ and $U_\alpha$ is an
unitary matrix. Assume that $\{\lambda_k/\sqrt{n_k}\}_{k\ge1}$ is the
sequence $\{\lambda_\alpha/\sqrt{n_\alpha}\}_{\alpha\in\cal A}$ ordered in
decreasing order. Then for all $m\ge1$ $(n_0=0)$

$1)$ for any $n$ such that $n_1^2+\ldots+n_{m-1}^2<n\le n_1^2+\ldots+n_m^2$
$$d_n(W_2^K(G),L_2(G))=\frac{|\lambda_m|}{\sqrt{n_m}},$$

$2)$ for any $n=n_1^2+\ldots+n_{m-1}^2+n_ms_m$, where $1\le s_m\le n_m$,
$$d_n(W_1^K(G),L_2(G))=\biggl(|\lambda_m|^2(n_m-s_m)+\sum_{k\ge m+1}|
\lambda_k|^2n_k\biggr )^{1/2}.$$
\end{theorem}

\begin{proof}
1. Using properties of the matrix elements
$$t_{ij}^\alpha(g_1g_2)=\sum_{k=1}^{n_\alpha}t_{ik}^\alpha(g_1)t_{kj}^
\alpha(g_2),\quad t_{ij}^\alpha(g)=\ov{t_{ji}^\alpha(g^{-1})},$$
we have
\begin{equation}\label{Matr}
K(gs^{-1})=\sum_{\alpha\in\cal A}\sum_{i,j=1}^{n_\alpha}c_{ij}^\alpha e_{
ij}^\alpha(gs^{-1})=\sum_{\alpha\in\cal A}\sum_{i,j=1}^{n_\alpha}\frac1{
\sqrt{n_\alpha}}c_{ij}^\alpha\sum_{k=1}^{n_\alpha}e_{ik}^\alpha(g)\ov{e_{jk
}^\alpha(s)}.
\end{equation}
It is easy to verify that if $x=(x_1,\ldots,x_{n_\alpha})$ is an
eigenvector of $C'_\alpha C_\alpha$ for the eigenvalue $\lambda$, then for
all $1\le k\le n_\alpha$ the functions $\sum_{j=1}^{n_\alpha}x_je_{jk}^
\alpha(\cdot)$ are eigenfunctions for $T'T$ with eigenvalue $\lambda/\sqrt
{n_\alpha}$. Consequently, $s_j$ are the $s$-numbers of $T'T$. It remains to
use Theorem~\ref{Th1}.

2. By (\ref{Matr}) we have
$$K(gs^{-1})=\sum_{\alpha\in\cal A}\frac1{\sqrt{n_\alpha}}\sum_{k,i=1}^{n_
\alpha}e_{ik}^\alpha(g)\sum_{j=1}^{n_\alpha}c_{ij}^\alpha\ov{e_{jk}^\alpha(
s)}.$$
Set
$$E_k^\alpha(g):=\left(\begin{array}{c}
e_{1k}^\alpha(g)\\
\vdots\\
e_{n_{\alpha}k}^\alpha(g)
\end{array}\right).$$
Then
$$K(gs^{-1})=\sum_{\alpha\in A}\frac1{\sqrt{n_\alpha}}\sum_{k=1}^{n_\alpha}
\left(E_k^\alpha(g),\ov{C}_\alpha E_k^\alpha(s)\right)_\alpha=\sum_{\alpha
\in A}\frac{\lambda_\alpha}{\sqrt{n_\alpha}}\sum_{k=1}^{n_\alpha}\left(E_k^
\alpha(g),\ov{U}_\alpha E_k^\alpha(s)\right)_\alpha,$$
where
$$(a,b)_\alpha:=\sum_{i=1}^{n_\alpha}a_i\ov b_i.$$
There exists an unitary matrix $V_\alpha$ such that
$$V_\alpha U_\alpha V_\alpha^*=\left(\begin{array}{ccc}
\gamma_1^\alpha&\\
\raise-7pt\hbox{\hphantom{00}$0$}&\ddots&\raise7pt\hbox{$0$\hphantom{00}}\\
&&\gamma_{n_\alpha}^\alpha\end{array}\right)=:\Gamma_\alpha,$$
where $|\gamma_j^\alpha|=1$, $j=1,\ldots,n_\alpha$. Set
$$F_k^\alpha(g)=\ov V_\alpha E_k^\alpha(g)=:\left(\begin{array}{c}
f_{1k}^\alpha(g)\\
\vdots\\
f_{n_{\alpha}k}^\alpha(g)
\end{array}\right).$$
Then $E_k^\alpha(g)=\ov V_\alpha^*F_k^\alpha(g)$, $f_{ik}^\alpha(g)$ is an
orthonormal basis, and
\multlines{K(gs^{-1})=\sum_{\alpha\in A}\frac{\lambda_\alpha}{\sqrt{n_
\alpha}}\sum_{k=1}^{n_\alpha}\left(\ov V_\alpha^*F_k^\alpha(g),\ov U_\alpha
\ov V_\alpha^*F_k^\alpha(s)\right)_\alpha}
{=\sum_{\alpha\in A}\frac{\lambda_\alpha}{\sqrt{n_\alpha}}\sum_{k=1}^{n_
\alpha}\left(F_k^\alpha(g),\ov V_\alpha\ov U_\alpha\ov V_\alpha^*F_k^\alpha
(s)\right)_\alpha}
{=\sum_{\alpha\in A}\frac{\lambda_\alpha}{\sqrt{n_\alpha}}\sum_{k=1}^{n_
\alpha}\left(F_k^\alpha(g),\ov\Gamma_\alpha F_k^\alpha(s)\right)_\alpha=
\sum_{\alpha\in A}\frac{\lambda_\alpha}{\sqrt{n_\alpha}}\sum_{k,j=1}^{n_
\alpha}\gamma_j^\alpha f_{jk}^\alpha( g)\ov{f_{jk}^\alpha(s)}.}
Using Theorem~\ref{Th2} we obtain the desired equality. $\quad\rule{5pt}
{12pt}$
\end{proof}

\begin{cor}
Let $G$ be a compact Abelian group, $K(\cdot)\in L_2(G)$, $c_j$, $j\ge1$,
be Fourier coefficients of $K$ in an orthonormal basis formed by characters
of the group. Assume that the $c_j$ are arranged in decreasing order. Then
for all $n\in\bbbz_+$
$$\eqalign{d_n(W_2^K(G),L_2(G))&=|c_{n+1}|,\cr
d_n(W_1^K(G),L_2(G))&=\biggl(\sum_{j\ge n+1}|c_j|^2\biggr)^{1/2}.}$$
\end{cor}

\begin{cor}
For $K=(k_1,\ldots,k_N)$ set
$$c_j=\sum_{m=1}^Nk_me^{-2\pi i(j-1)m/N}.$$
Assume that $c_j$ are arranged in decreasing order. Then for all $n\in\bbbz_
+$
$$\eqalign{d_n(W_2^K(\bbbz_N),L_2(\bbbz_N))&=|c_{n+1}|,\cr
d_n(W_1^K(\bbbz_N),L_2(\bbbz_N))&=\biggl(\frac1N\sum_{j\ge n+1}|c_j|^2
\biggr)^{1/2}.}$$
\end{cor}

If $K=(1,0,\ldots,0)$, then from the last equality we obtain (\ref1).

Let
$$\bbbs^d=\Bigl\{\,x=(x_1,\ldots,x_{d+1})\in\bbbr^{d+1}\Bigm|\sum_{j=1}^{
d+1}x_j^2=1\,\Bigr\}$$
be the unit sphere. It is known (see~\cite9) that $L_2(\bbbs^d)=\sum_{k=0}
^\infty H_k$ where
$$\dim H_k=n_k={d+k\choose k}-{d+k-1\choose k-2}$$
($H_k$ is the set of spherical harmonics of the order $k$). Let $\{Y_j^k\}_
{j=1}^{n_k}$ be an orthonormal basis of $H_k$. For the Laplace operator
$\Delta$ and any $x(\cdot)\in H_k$ the equality
$$\Delta x(\cdot)=-\lambda_kx(\cdot)$$
holds where $\lambda_k=k(k+d-1)$. For $\alpha>0$ the operator $(-\Delta)^{
\alpha/2}$ is defined by
$$(-\Delta)^{\alpha/2}x(\cdot)=\sum_{k=1}^\infty\lambda_k^{\alpha/2}\sum_{j
=1}^{n_k}x_{kj}Y_j^k(\cdot),$$
where $x(\cdot)\in L_2(\bbbs^d)$ and $x(\cdot)=\sum_{k=0}^\infty\sum_{j=1}^
{n_k}x_{kj}Y_j^k(\cdot)$.

Set
$$W_2^\alpha(\bbbs^d)=\{\,x(\cdot)\in L_2(\bbbs^d)\mid\|(-\Delta)^{\alpha
/2}x(\cdot)\|_{L_2(\bbbs^d)}\le1\,\}.$$
It is easy to check that this class can be represented in the form
$$W_2^\alpha(\bbbs^d)=\{\,x(\cdot)\in L_2(\bbbs^d)\mid x(\cdot)=c+Ty(\cdot),
\ c\in\bbbr,\ y(\cdot)\in L_2(\bbbs^d),\ y(\cdot)\mbox{\large$\scriptstyle
\perp$}1\,\},$$
where for $y(\cdot)=\sum_{k=1}^\infty\sum_{j=1}^{n_k}y_{kj}Y_j^k(\cdot)$
$$Ty(\cdot)=\sum_{k=1}^\infty\sum_{j=1}^{n_k}\lambda_k^{-\alpha/2}y_{kj}Y_j
^k(\cdot).$$

\begin{cor}
Let $n_0+\ldots+n_{k-1}\le n<n_0+\ldots+n_k$. Then
$$d_n(W_2^\alpha(\bbbs^d),L_2(\bbbs^d))=\lambda_k^{-\alpha/2}.$$
\end{cor}

The class $W_2^\alpha(\bbbs^d)$ for $d=1$ and $\alpha=r\in\bbbz_+$
coincides with the Sobolev class $$W_2^r(\bbbt)=\{\,x(\cdot)\in
L_2(\bbbt)\mid x^{(r-1)}(\cdot)\mbox{ abs.\ cont., }\|x^{(r)}(\cdot)\|_{L_2
(\bbbt)}\le1\,\}.$$
In this case $\lambda_k=k^2$, $n_0=1$, $n_k=2$, $k\ge1$. Thus we obtain

\begin{cor}
For all $n\in\bbbz_+$
$$d_{2n-1}(W_2^r(\bbbt),L_2(\bbbt))=d_{2n}(W_2^r(\bbbt),L_2(\bbbt))=\frac1
{n^r}.$$
\end{cor}

One does not obtain results similar to those obtained in Corollary 3 and 4
for the classes $W_1^\alpha(\bbbs^d)$ and $W_1^r(\bbbt)$. The reason for
this is the additional condition $y(\cdot)\mbox{\large$\scriptstyle\perp$}1
$ which does not permit us to apply Theorem~\ref{Th2}. Some estimates of $d
_n(W_1^r(\bbbt),L_2(\bbbt))$ may be found in \cite[p.~101]2.

\section*{\large\sc\hfil4. Average widths\hfil}

\hspace{\parindent}In this section we calculate exact values of average
Kolmogorov widths for some classes of functions defined on $\bbbr^d$ and
$\bbbz^d$ in the $L_2$ metric. We begin with the definition of the average
dimension of subspace. Let $G=\bbbr^d$ or $\bbbz^d$ and $\mu_G$ be the
Lebesgue measure on $G$ if $G=\bbbr^d$, and discrete measure if $G=\bbbz^d$.
Let ${\cal A}(G)$ be the set of positive numbers if $G=\bbbr^d$ and the set
of natural numbers for $G=\bbbz^d$. Assume that $A$ is a subset of $L_p(G)$
($1\le p\le\infty$) and $\alpha\in{\cal A}(G)$. Denote by $A_{\alpha}$ the
restriction of $A$ to the set $$\square_\alpha=\{\,t=(t_1,\ldots,t_d)\in G
\mid |t_j|\le\alpha,\,\,j=1,\ldots,d\,\}.$$

Let $L$ be a subspace of $L_p(G)$. For every $\varepsilon>0$ and $\alpha\in{
\cal A}(G)$ consider the value
$$K_\varepsilon\left(\alpha,L,L_p(G)\right)=\min\{\,n\in\bbbz_+\mid d_n
\left((L\cap BL_p(G))_{\alpha},L_p(\square_\alpha)\right)<\varepsilon\,\},
$$
where $BL_p(G)$ is the unit ball of $L_p(G)$. It is clear that $K_
\varepsilon\left(\alpha,L,L_p(G)\right)$ is the minimal dimension of a
subspace of $L_p(\square_\alpha)$ which approximates the set $(L\cap BL_p(G
))_\alpha$ to within $\varepsilon$. It is easy to check that for every $
\varepsilon>0$ the function $\alpha\to K_\varepsilon\left(\alpha,L,L_p(G)
\right)$ does not decrease, and obviously for every $\alpha>0$ the function
$\varepsilon\to K_\varepsilon\left(\alpha,L,L_p(G)\right)$ does not increase.

The {\it average dimension of $L$ in $L_p(G)$} is defined as
$$\ov{\dim}\left(L,L_p(G)\right)=\lim_{\varepsilon\to0}\liminf_{\alpha\to
\infty}\frac{K_\varepsilon\left(\alpha,L,L_p(G)\right)}{\mu_G(\square_
\alpha)}.$$

It is clear that $\ov{\dim}\left(L,L_p(\bbbz^d)\right)\le1$.

We shall formulate here one result about average dimension of functional
spaces which we later need. Let $G^*$ be $\bbbr^d$ for $G=\bbbr^d$ and
$\bbbt^d$ (a $d$-dimensional torus) for $G=\bbbz^d$. Let $\mu_{G^*}$ be
the Lebesgue measure on $G^*$ divided by $(2\pi)^d$. (The last condition is
connected with the fact that $\mu_G$ is the natural Haar measure on $G$ as
on a locally compact Abelian group and $\mu_{G^*}$ is just the Haar measure
associated with it on the dual group $G^*$.)

Let $A$ be a subset of $G^*$ and $1\le p\le\infty$. Set
$${\cal B}_{A,p}(G)=\{\,x(\cdot)\in L_p(G)\mid\supp\widehat x(\cdot)\subset
A\,\},$$
where $\supp\widehat x(\cdot)$ is the support of Fourier transform of $x(
\cdot)$ ($x(\cdot)$ is considered as an distribution). It is clear that ${
\cal B}_{A,p}(G)$ is a subspace of $L_p(G)$.

Recall that  a set $A\subset G^*$ is called Jordan measurable if its
characteristic function is integrable in the sense of Riemann. The
following two theorems (Theorem~\ref{avd} and \ref{awb}) were proved in
\cite{M1,M2} for $G=\bbbr^d$. In a general case these theorems may be
proved in much the same way.

\begin{Theorem}[about average dimension]\label{avd}
Let $G=\bbbr^d$ or $\bbbz^d$, $A$ be a Jordan measurable subset of $G^*$
with finite measure and $1\le p\le\infty$. Then
$$\ov{\dim}\left({\cal B}_{A,p}(G),L_p(G)\right)=\mu_{G^*}(A).$$
\end{Theorem}

The notion of average dimension leads at once to the corresponding analogue
of Kolmogorov $n$-width. Let $C$ be a centrally symmetric subset of $L_p(G)$
and $\nu\ge0$. The {\it Kolmogorov average $\nu$-width of $C$ in $L_p(G)$}
is defined as follows
$$\ov d_{\nu}\left(C,L_p(G)\right)=\infp_{L}\sup_{x(\cdot)\in C}\infp_{y(
\cdot)\in L}\|x(\cdot)-y(\cdot)\|_{L_p(G)},$$
where the first infimum is taken over all subspaces $L$ of $L_p(G)$ such
that $\ov{\dim}\left(L,L_p(G)\right)\le\nu$. Any subspace for which this
infimum is attained we call an {\it extremal subspace for $\ov d_{\nu}
\left(C,L_p(G)\right)$.}

The following analogue for average widths of the theorem about widths of a
ball  holds.

\begin{Theorem}[about widths of a ball]\label{awb}
Let $A\subset G^*$ be a Jordan measurable set, $\nu>0$, and
$\mu_{G^*}(A)>\nu$. then
$$\ov d_{\nu}\left({\cal B}_{A,p}(G)\cap BL_p(G),L_p(G)\right)=1.$$
\end{Theorem}

We calculate the exact value of the average width in $L_2$ for the set $C$
which is a convolution class of functions defined on $G$. If $K(\cdot)\in
L_2(G)$, then the operator of convolution with this kernel $x(\cdot)\to
(K*x)(\cdot)$ is obviously a linear continuous operator from $L_2(G)$ into
$L_2(G)$. Set
$$W_2^K(G)=\{\,y(\cdot)\in L_2(G)\mid y(\cdot)=(K*x)(\cdot),\ \|x(\cdot)\|_
{L_2(G)}\le1\,\}.$$

Denote by $\widehat z(\cdot)$ the Fourier transform of the function $z(\cdot
)\in L_2(G)$.

\begin{theorem}
Let $K(\cdot)\in L_1(G)\cap L_2(G)$, $\nu>0$ if $G=\bbbr^d$, and $0<\nu<
1$ if $G=\bbbz^d$. Then
$$\ov d_{\nu}\left(W_2^K(G),L_2(G)\right)=\widehat K^*(\nu),$$
where $\widehat K^*(\cdot)$ is the non-decreasing permutation of $\widehat
K(\cdot)$. Moreover, the space ${\cal B}_{A(\nu),2}(G)$, where $A(\nu)=\{
\tau\in G^*\mid|\widehat K(\tau)|>\widehat K^*(\nu)\}$ is an extremal space
for $\ov d_{\nu}\left(W_2^K(G),L_2(G)\right)$.
\end{theorem}

\begin{proof}
The lower bound. We use the method of ``embedded balls''. For every
$\gamma>0$ consider the set $A(\gamma)=\{\tau\in G^* \mid\widehat
K(\tau)|>\gamma\}$. Since $K(\cdot)\in L_1(G)$ the function $\widehat
K(\cdot)$ is continuous and $\widehat K(\tau)\to0$ as $|\tau|\to\infty$ if
$G=\bbbr^d$. Therefore the set $A(\gamma)$ is open and bounded. Thus it is
Jordan measurable, as is easy to check. We prove that
\begin{equation}\label{i2}
{\cal B}_{A(\gamma),2}(G)\cap\gamma BL_2(G)\subset W_2^K(G).
\end{equation}
Indeed, let $y(\cdot)$ belong to the left-hand side of (\ref{i2}). Assume
that $x(\cdot)\in L_2(G)$ is defined by the condition: $\widehat x(\tau)=0$
almost everywhere if $\tau\notin A(\gamma)$ and $\widehat x(\tau)=\widehat
K^{-1}(\tau)\widehat y(\tau)$ almost everywhere if $\tau\in A(\gamma)$.
Thus $y(\cdot)=(K*x)(\cdot)$ and we have to show that $\|x(\cdot)\|_{L_2(G)
}\le1$. By the Plancherel theorem
\lines{\|x(\cdot)\|^2_{L_2(G)}=\int_G\left|\widehat K^{-1}(\tau)
\widehat y(\tau)\right|^2d\tau=\int_{A(\gamma)}\left|\widehat K^{-1}(\tau)
\widehat y(\tau)\right|^2d\tau}
{\le\gamma^{-2}\int_{A(\gamma)}|\widehat y(\tau)|^2d\tau\le\gamma^{-2}\|y(
\cdot)\|^2_{L_2(G)}\le1,}
that is, $y(\cdot)\in W_2^K(G)$.

Now $\gamma>0$ is such that $\mu_{G^*}(A(\gamma))>\nu$. By Theorem~\ref{avd}
$$\ov{\dim}\left({\cal B}_{A(\gamma),2}(G),L_2(G)\right)=\mu_{G^*}\left(A(
\gamma)\right)>\nu.$$
Then by Theorem~\ref{awb} (taking into account the obvious property of
homogeneity of these widths) we obtain
$$\ov d_{\nu}\left({\cal B}_{A(\gamma),2}(G)\cap\gamma BL_2(G),L_2(G)\right
)=\gamma.$$
From this and (\ref{i2}), using the monotonicity of widths it follows that
$$\ov d_{\nu}\left(W_2^K(G),L_2(G)\right)>\gamma.$$
Passing to the supremum in this inequality over all $\gamma>0$ for which $
\mu_{G^*}\left(A(\gamma)\right)>\nu$ (in view of the continuity of $\widehat
K(\cdot)$ this is equivalent to passage to the supremum over all $\gamma>0$
for which $\mu_{G^*}\left(A(\gamma)\right)\ge\nu$) we obtain the required
lower bound.

The upper bound is based on the approximation of $W_2^K(G)$ by the Fourier
method. Let $\gamma=\gamma(\nu)$ be such that $\mu_{G^*}\left(A(\gamma)
\right)=\nu$ (it is clear that in this case $\gamma=\widehat K^*(\nu)$). By
Theorem~\ref{avd} $\ov{\dim}\left({\cal B}_{A(\gamma),2}(G),L_2(G)\right)=
\nu$. With every $y(\cdot)=(K*x)(\cdot)\in W_2^K(G)$ associate the function
$\eta(\cdot)\in{\cal B}_{A(\gamma),2}(G)$ such that $\widehat\eta(\cdot)=
\chi_{A(\gamma)}(\cdot)\widehat y(\cdot)$ where $\chi_{A(\gamma)}(\cdot)$ is
the characteristic function of the set $A(\gamma)$.$\quad\rule{5pt}{12pt}$
\end{proof}

The next result is the analogue of (\ref1) for average widths.

\begin{theorem}
Let $0<\nu<1$. Then
$$\ov d_{\nu}\left(Bl_1(\bbbz^d),l_2(\bbbz^d)\right)=\sqrt{1-\nu}.$$
\end{theorem}

\begin{proof}
The arguments do not depend on the dimension $d$ so for simplicity we
consider the case $d=1$.

The lower bound. Let $L$ be a subspace of $l_2(\bbbz)$, $\ov{\dim}\left(
L,l_2(\bbbz)\right)\le\nu$, and $\varepsilon>0$. Assume that $\{N_k\}$ is a
subsequence of natural numbers such that
\begin{equation}\label{i3}
\liminf_{N\to\infty}\frac{K_\varepsilon\left(N,L,l_2(\bbbz)\right)}{2N+1
}=\lim_{k\to\infty}\frac{K_\varepsilon\left(N_k,L,l_2(\bbbz)\right)}{2N_k+
1}.
\end{equation}
By the definition of average dimension, for every $k$ there exists a
subspace $M_k\subset l_2^{2N_k+1}$ such that
\begin{equation}\label{ii3}
d\left((L\cap Bl_2(\bbbz))_k,M_k,l_2^{2N_k+1}\right)<\varepsilon,
\end{equation}
\begin{equation}\label{iii3}
\dim M_k\le K_\varepsilon\left(N_k,L,l_2(\bbbz)\right).
\end{equation}

Let $x\in Bl_1^{2N_k+1}$. Extending $x$ by zero to $\bbbz$ we obtain $x\in
Bl_1(\bbbz)$ and consequently $x\in Bl_2(\bbbz)$. Let $y\in L$ and $z\in M_
k$ be such that
\begin{equation}\label{iv3}
\|y-z\|_{l_2^{2N_k+1}}=d\left(y,M_k,l_2^{2N_k+1}\right).
\end{equation}
Then using the triangle inequality, (\ref{iv3}), (\ref{ii3}), and again the
triangle inequality, we have
\multlines{\|x-y\|_{l_2(\bbbz)}\ge\|x-y\|_{l_2^{2N_k+1}}\ge\|x-z\|_{l_2^{2
N_k+1}}-\|y-z\|_{l_2^{2N_k+1}}}
{\ge d\left(x,M_k,l_2^{2N_k+1}\right)-d\left(y,M_k,l_2^{2N_k+1}\right)\ge
d\left(x,M_k,l_2^{2N_k+1}\right)-\varepsilon\|y\|_{l_2(\bbbz)}}
{\ge d\left(x,M_k,l_2^{2N_k+1}\right)-\varepsilon\|x-y\|_{l_2(\bbbz)}-
\varepsilon\|x\|_{l_2(\bbbz)}.}
Consequently,
$$(1+\varepsilon)\|x-y\|_{l_2(\bbbz)}\ge d\left(x,M_k,l_2^{2N_k+1}\right)-
\varepsilon.$$
Hence,
\begin{equation}\label{v3}
(1+\varepsilon)d\left(Bl_1(\bbbz),L,l_2(\bbbz)\right)\ge d\left(Bl_1^{2
N_k+1},M_k,l_2^{2N_k+1}\right)-\varepsilon.
\end{equation}

From (\ref{i3}) (taking into account (\ref{iii3})) it follows that for every
$0<\delta<1-\nu$ there exists $k_0$ such that for all $k\ge k_0$
$$\dim M_k\le K_\varepsilon\left(N_k, L,l_2(\bbbz)\right)\le(\nu+\delta)(2
N_k+1).$$
Put $N(k)=2N_k+1$ and $n(k)=\left[(\nu+\delta)(2N_k+1)\right]$. Then
$\dim M_k\le n(k)<N(k)$. Taking into account these inequalities, (\ref{v3}),
and (\ref1) we have
\lines{(1+\varepsilon)d\left(Bl_1(\bbbz),L,l_2(\bbbz)\right)\ge d_{n(k)}
\left(Bl_1^{N(k)},l_2^{N(k)}\right)-\varepsilon}
{=\sqrt{1-\frac{n(k)}{N(k)}}-\varepsilon=\sqrt{1-(\nu+\delta)}-\varepsilon.}
In view of the arbitrariness of $\varepsilon$, $\delta$, and $L$ we obtain the
required lower bound.

The upper bound. Let $\varepsilon>0$ and the numbers $n,N\in\bbbn$ be chosen
so that $n<N$ and $(n/N)\le\nu\le(n/N)+\varepsilon$. Denote by $L_{n,N}$ a
subspace of $l_2^N$ with dimension at most $n$ which is extremal for $d_n
\left(Bl_1^N,l_2^N\right)$. We consider this subspace as a subspace of
functions on $\bbbz$ with support on $\{0,1,\ldots,N-1\}$. Let $e_i(\cdot)$,
$i=1,\ldots,N$, be a basis for $L_{n,N}$. If $k\in\bbbz$, then the functions
$e_i(\cdot+kN)$, $i=1,\ldots,N$, form a basis in the space of all functions
from $L_{n,N}$ shifted by $kN$. Denote by  $L$ the set of functions $y(\cdot
)$ defined on $\bbbz$ which have the form $y(\cdot)=\sum_{k\in\bbbz}\sum_{i=
1}^nx_{ki}e(\cdot+kN)$ where $\sum_{k\in\bbbz}\sum_{i=1}^nx^2_{ki}<\infty$.
It is clear that $L$ is a subspace of $l_2(\bbbz)$.

We show that $\ov{\dim}\left(L,l_2(\bbbz)\right)\le\nu$. Indeed, denote by
$L_m$ the restriction of $L$ to $\{-mN,\ldots,mN\}$. It is easy to see that
$\dim L_m\le 2mn+1$ and therefore
$$\ov{\dim}\left(L,l_2(\bbbz)\right)\le\liminf_{m\to\infty}\frac{2mn+1}{2mN
+1}=\frac{n}{N}\le\nu.$$
Denote by $M_k$ the restriction of $L$ to $\Delta_k=\{kN,\ldots,(k+1)N-1\}$.

Now let $x\in Bl_1(\bbbz)$ and $x_k$ be the restriction of $x$ to
$\Delta_k$. Since $x_k\in\|x_k\|_{l_1^N}Bl_1^N$ and $M_k=L_{n,N}$ (if
$L_{n,N}$ is considered as a set of functions defined on $\Delta_k$) there
exists $y _k\in M_k$ for which
\begin{equation}\label{ii4}
\|x_k-y_k\|_{l_2^N}\le\sqrt{1-(n/N)}\|x_k\|_{l_1^N}.
\end{equation}
Let $y\in L$ be a function such that the restriction of $y$ to $\Delta_k$
equals $y_k$. Then using (\ref{ii4}) and the mean inequality we have
\lines{\|x-y\|_{l_2(\bbbz)}=\left(\sum_{k\in\bbbz}\|x_k-y_k\|^2_{l_2^N}
\right)^{1/2}\le\sqrt{1-\frac{n}{N}}\left(\sum_{k\in\bbbz}\|x_k\|^2_{l_1^N}
\right)^{1/2}}
{\le\sqrt{1-\frac{n}{N}}\sum_{k\in\bbbz}\|x_k\|_{l_1^N}=\sqrt{1-\frac{n}{N}}
\| x\|_{l_1(\bbbz)}\le\sqrt{1-\frac{n}{N}}\le\sqrt{1-\nu+\varepsilon}.}
In view of the arbitrariness of $\varepsilon$ we obtain the required
estimate.$\quad\rule{5pt}{12pt}$
\end{proof}

We note here one general fact which in particular enables us to obtain at
once a series of extremal spaces for the widths $d_n(Bl_1^N,l_2^N)$ and $
\ov d_\nu(Bl_1(\bbbz^d),l_2(\bbbz^d))$.

Let $G$ be a locally compact Abelian group (LCAG), $G^*$ be the dual group
to $G$ (that is, the group of all continuous characters on $G$), and
$\ch(g,g^*)$ be the value of $g^*\in G^*$ at the element $g\in G$. We
define by $\mu_G$ ($\mu_{G^*}$) the Haar measure on $G$ ($G^*$).

For every $x(\cdot)\in L_1(G)$ the function $\widehat x(\cdot)$ defined on
$G^*$ which is given by the formula
\begin{equation}\label{i5}
\widehat x(g^*)=\int_Gx(g)\ch(-g,g^*)d\mu_G
\end{equation}
is called the {\it Fourier transform of $x(\cdot)$}. By (\ref{i5}) it
follows that $\widehat x(\cdot)$ is a continuous function and
\begin{equation}\label{ii5}
\|\widehat x(\cdot)\|_{C(G^*)}\le\|x(\cdot)\|_{L_1(G)}.
\end{equation}
The Fourier transform can be extended up to an isometric operator from $L_2
(G)$ onto $L_2(G^*)$ (this extension we define by the same symbol $\widehat
x(\cdot)$). Thus we have the Parseval equality
\begin{equation}\label{iii5}
\|x(\cdot)\|_{L_2(G)}=\|\widehat x(\cdot)\|_{L_2(G^*)}.
\end{equation}
If $G$ is a discrete group, then the dual group $G^*$ is compact and we
shall usually assume that $\mu_{G^*}(G^*)=1$.

Let $A$ be a nonempty subset of $G^*$ and $p=1$ or $2$. Set
$${\cal B}_{A,p}(G)=\{x(\cdot)\in L_p(G)\mid\supp\widehat x(\cdot)\subset
A\},$$
where $\supp\widehat x(\cdot)$ is the support of $\widehat x(\cdot)$. It is
clear that ${\cal B}_{A,p}(G)$ is a subspace of $L_p(G)$.

\begin{pro}\label{pro}
Let $G$ be a discrete LCAG and $A$ a measurable subset of $G^*$. Then
$L_1(G)$ is embedded in $L_2(G)$ and
$$d\left(BL_1(G),{\cal B}_{A,2}(G),L_2(G)\right)\le\sqrt{1-\mu_{G^*}(A)}.$$
\end{pro}

\begin{proof}
Let $x(\cdot)\in BL_1(G)$ and the function $y(\cdot)\in L_2(G)$ be such that
$\widehat y(\cdot)=\chi_A(\cdot)\widehat x(\cdot)$ ($\chi_A(\cdot)$ is the
characteristic function of $A$). It is clear that $y(\cdot)\in{\cal B}_{A,2}
(G)$. Using (\ref{iii5}) and (\ref{ii5}), we have
\lines{\|x(\cdot)-y(\cdot)\|^2_{L_2(G)}=\int_{G^*\setminus A}|\widehat x(g^*)
|^2d\mu_{G^*}\le\|\widehat x(\cdot)\|^2_{C(G^*)}\int_{G^*\setminus A}d\mu_{
G^*}}
{\le\|x(\cdot)\|^2_{L_1(G)}\left(1-\mu_{G^*}(A)\right)\le 1-\mu_{G^*}(A).}
If we take here $x(\cdot)\in L_1(G)$ and $y(\cdot)=0$, then we obtain that
$\|x(\cdot)\|_{L_2(G)}\le\|x(\cdot)\|_{L_1(G)}$. This means that $L_1(G)$
is continuously embedded in $L_2(G)$. $\quad\rule{5pt}{12pt}$
\end{proof}

We apply this result to the mentioned above problems.

1. The space $l_p^N$, $1\le p\le\infty$, can be considered as $L_p(G)$
where $G=\bbbz_N=\{0,1,\ldots,N-1\}$ is a finite discrete Abelian group
with the operation of addition modulo $N$. Characters of this group are the
functions $k\to\exp(2\pi kl/N)$, $k\in \bbbz_N$, where $0\le l\le N-1$.
Therefore we can identify the dual group $\bbbz_N^*$ with $\bbbz_N$. Let $n
<N$ and $A=\{l_{j_1},\ldots,l_{j_n}\}\subset\bbbz_N^*$. It is clear that $
\mu_{\bbbz_N^*}(A)=n/N$. Consider the space $L_n=\spa\{\exp(2\pi il_{j_1}
\cdot/N),\ldots,\exp(2\pi il_{j_n}\cdot/N)\}$, $\dim L_n=n$. From
Proposition~\ref{pro} and (\ref1) it follows that $L_n$ is an extremal
subspace for $d_n(Bl_1^N,l_2^N)$.

2. Let $A\subset\bbbt^d$ be Jordan measurable, $\mu_{\bbbt^d}(A)=\nu$, $0<
\nu<1$. Consider the space $L_\nu=\{x(\cdot)\in l_2(\bbbz^d)|\supp\widehat
x(\cdot)\subset A\}$. By Theorem~\ref{avd} we have $\ov{\dim}(L_\nu,l_2(
\bbbz^d))=\nu$. Now from Proposition~\ref{pro} and Theorem~\ref{avd} it
follows that $L_\nu$ is an extremal subspace for $\ov d_\nu(Bl_1(\bbbz^d),
l_2(\bbbz^d))$.

\section*{\large\sc\hfil5. Comments\hfil}

\hspace{\parindent} Various statements which are equivalent to Theorem~\ref
{Th1} were proved by many authors (see \cite{Al,T60,T76,Pi,2}). Of course
this result was known to Kolmogorov who considered in \cite3 only
particular cases of elliptical cylinders.

In a finite-dimensional space $n$-widths of regular octahedra were in fact
obtained in two papers \cite4 (the upper bound) and \cite5 (the lower
bound). It is interesting to note that Kolmogorov in 1948 did not take into
consideration that in these papers $d_n(Bl_1^N,l_2^N)$ were calculated.
This fact was noted by Stechkin \cite6 who used it to find asymptotic
values of $n$-widths for functional classes.

There is one more type of octahedra for which it is possible to calculate
exact values of widths. They are octahedra with different axes
$$Bl_1^N(a):=\left\{\,x\in\bbbr^N\Bigm|\sum_{k=1}^N\frac{|x_k|}{a_k}\le1\,
\right\},\qquad a_1\ge\ldots\ge a_N.$$
For the dual case Smolyak \cite{10} found the exact values of the linear ($
\lambda_n$) and Gel'fand ($d^n$) $n$-widths
$$\lambda_n(Bl_2^N(a),l_\infty^N)=d^n(Bl_2^N(a),l_\infty^N)=\max_{m>n}\sqrt
{\frac{m-n}{\sum_{k=1}^ma_k^{-2}}}.$$
For the Kolmogorov $n$-width $d_n(Bl_1(a),l_2)$ the exact result was
obtained by Sofman \cite{11,12} (see also \cite{13}).

In the continuous case estimates for the $n$-widths of generalized octahedra
and even more general sets (images of compacts under continuous
transformation in the Hilbert space) can be obtained using results such as a
theorem of Ismagilov \cite{14} which is based on the method of averages (we
demonstrated this method in the proof of Theorem~\ref{Th2}). Ismagilov cited
Obukhov \cite{Ob} as a predecessor in using the method of averages. Several
statements of a similar type which are used for calculating exact values of
$n$-widths for classes of analytic functions can be found in \cite
{15,16,17}. In those papers the dual situation is considered and the exact
values of linear, Gel'fand, and Bernstein widths of $W_2^K(X)$ in $C(X)$ are
found. In the dual case using the Hilbert space structure it is possible to
calculate the exact values of $n$-widths for $W_2^\alpha(\bbbs^d)$ and $W_2^
r(\bbbt)$.

The concept of average dimension takes the beginning from the definition of
``average entropy" for stochastic signals with bounded spectrum which was
offered by Shannon \cite{Sh}. Further Kolmogorov modified this definition for
determined functions. Then Tikhomirov \cite{T80} defined the notion of
average dimension replacing entropy by Kolmogorov widths. The definition of
the average dimension used in the paper is a modification of Tikhomirov's
definition. The notion of the Kolmogorov average widths is due to
Magaril-Il'yaev.

\begin{thebibliography}{99} \small

\bibitem{1}{\sc V.~M.~Tikhomirov}, ``Approximation Theory''. Encyclopedia
of Math. Sci., vol. 14 [Analysis, II], Springer-Verlag, Berlin, 1990.

\bibitem{2}{\sc A. Pinkus}, ``$n$-Widths in Approximation Theory'',
Springer-Verlag, Berlin, 1985.

\bibitem{3}{\sc A.~N.~Kolmogorov}, \"Uber die beste Ann\"aherung von
Functionen einer gegebenen Functionenklasse, {\it Ann. of Math.} {\bf37}
(1936), 107--110.

\bibitem{4}{\sc A.~N.~Kolmogorov, A.~A.~Petrov, Yu.~M.~Smirnov}, A formula
of Gauss in the theory of the method of least squares, {\it Izv. Akad.
Nauk SSSR Ser. Mat.} {\bf11} (1947), 561--566.

\bibitem{5}{\sc A.~I.~Maltsev}, A remark on the paper of A.~N.~Kolmogorov,
A.~A.~Petrov, and Yu.~M.~Smirnov ``A formula of Gauss on the theory of
least squares'', {\it Izv. Akad.  Nauk SSSR Ser. Mat.} {\bf11}
(1947), 567--568.

\bibitem{6}{\sc S.~B.~Stechkin}, On the best approximation of given classes
by any polynomials, {\it Uspekhi Mat. Nauk} {\bf9} (1954), 133-134.

\bibitem{7}{\sc A.~N.~Kolmogorov, S.~V.~Fomin}, ``Elements of Theory of
Functions and Functional Analysis'', Nauka, Moscow, 1972.

\bibitem{8}{\sc A.~Weil}, ``L'int\'egration dans les Groupes Topologiques
et ses Applications'', Hermann, Paris, 1965.

\bibitem{9}{\sc E.~M.~Stein, G.~Weiss}, ``Introduction to Fourier Analysis
on Euclidean Spaces'', Princeton University Press, Princeton, 1971.

\bibitem{M1}{\sc G.~G.~Magaril-Il'yaev}, Mean dimension, widths, and
optimal recovery of Sobolev classes of functions on the line, {\it Mat. Sb.}
{\bf182} (1991), 1635--1656; English translation {\it Math. USSR Sbornik}
{\bf74}, 381--403.

\bibitem{M2}{\sc G.~G.~Magaril-Il'yaev}, Average widths of Sobolev classes
on $\bbbr^n$, {\it J. Approx. Theory} {\bf76} (1994), 65--76.

\bibitem{Al}{\sc D.~T.~Allahverdiev}, On the rate of approximation of
completely continuous operators by finite-dimensional operators, {\it
Azerb. Gos. Univ. Uchen. Zap.} {\bf2} (1957), 27--35.

\bibitem{T60}{\sc V.~M.~Tikhomirov}, Diameters of sets in functional spaces
and the theory of best approximations, {\it Uspekhi Mat. Nauk} {\bf15}
(1960), 81--120; English translation {\it Russian Math. Surveys} {\bf15},
75--111.

\bibitem{T76}{\sc V.~M.~Tikhomirov}, `` Some Questions of Approximation
Theory'', Moscow State University, Moscow, 1976.

\bibitem{Pi}{\sc A.~Pietsch}, ``Operator Ideals'', North-Holland Publ. Co.,
Amsterdam, 1980.

\bibitem{10}{\sc S.~A.~Smolyak}, ``On Optimal Restoration of Functions and
functionals of Them'', Candidate dissertation, Moscow State University,
Moscow, 1965.

\bibitem{11}{\sc L.~B.~Sofman}, Diameters of octahedra, {\it Mat. Zametki}
{\bf5} (1969), 429--436; English translation {\it Math. Notes} {\bf5},
258--262.

\bibitem{12}{\sc L.~B.~Sofman}, Diameters of an infinite-dimensional
octahedra, {\it Vestnik Mosk. Univ. Mat.} {\bf28} (1973), 54--56; English
translation {\it Moscow Univ. Math. Bull} {\bf28}, 45--47.

\bibitem{13}{\sc C.~V.~Hutton, J.~S.~Morrel, J.~R.~Retherford}, Diagonal
operators, approximation numbers, and Kolmogoroff diameters, {\it J.
Approx. Theory} {\bf16} (1976), 48--80.

\bibitem{14}{\sc R.~S.~Ismagilov}, On $n$-dimensional diameters in a Hilbert
space, {\it Funktsional. Anal. i Prilozhen.} {\bf2} (1968), 32--39; English
translation {\it Functional Anal. Appl.} {\bf2}, 125--132.

\bibitem{Ob}{\sc A.~M.~Obukhov}, On statistically orthogonal decomposition
of empirical function, {\it Izv. Akad. Nauk SSSR. Ser. Geophys.} {\bf3}
(1960) 432--439.

\bibitem{15}{\sc K.~Yu.~Osipenko, M.~I.~Stessin}, On $n$-widths of the
Hardy class $H^2$ in the unit ball of $\bbbc^n$, {\it Uspekhi Mat. Nauk}
{\bf45} (1990), 193--194; English translation {\it Russian Math. Surveys}
{\bf45}, 235--236.

\bibitem{16}{\sc K.~Yu.~Osipenko}, On $N$-widths of holomorphic functions
of several variables, {\it J. Approx. Theory} {\bf82} (1995),
135--155.

\bibitem{17}{\sc K.~Yu.~Osipenko, O.~G.~Parfenov}, Ismagilov type theorems
for linear, Gel'fand and Bernstein $n$-widths, {\it J. Complexity} {\bf11}
(1995), 474--492.

\bibitem{Sh}{\sc C.~E.~Shannon}, A mathematical theory of communication,
{\it Bell System Techn. J.} {\bf27} (1948), 379--423, 623--656.

\bibitem{T80}{\sc V.~M.~Tikhomirov}, On approximation characteristics of
multivariate smooth functions, in ``Proceedings of the Conference on
Differential Equations and Applied Mathematics'', Nauka, SO AN SSSR, 1980,
183--188.

\end{thebibliography}
\end{document}