\documentclass[12pt]{article}

\usepackage{theorem,amsmath,amssymb}

\input{listki.tex}

\begin{document}

\listok{3}{GEOMETRY 3: Metric spaces and norm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

You are supposed to know the definition of a linear space and dot
product (i.e. a positive bilinear symmetric form). Consult ALGEBRA 3.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subs{Metric spaces, convex sets, norm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{opredelenie} A metric space is a set $X$ equipped with a
  function $d:\; X \times X \to \R$ such that
\begin{enumerate}
\item 
$d(x,y)> 0$ for all $x\neq y \in X$;  moreover, $d(x,x)=0$.

\item Symmetry: $d(x, y) = d (y, x)$

\item ``Triangle inequality'': for all $x, y, z \in X$,
$$
d(x,z) \leq  d(x,y) + d(y,z).
$$
\end{enumerate}
A function $d$ which satisfies these conditions is called {\bf
  metric}. The number $d(x,y)$ is called  ``distance between $x$ and
$y$''.
\end{opredelenie}

If $x\in X$ is a point and $\epsilon$ is a real number
then the set
$$ 
B_\epsilon(x) = \{ y \in X \ \  | \ \  d(x,y)< \epsilon
$$
is called an {\bf (open) ball of radius $\epsilon$ with the center in $x$}.
Such ball can be called as well an {\bf $\epsilon$-ball}. A closed
ball is defined as follows
$$ 
\overline B_\epsilon(x) = \{ y \in X \ \  | \ \  d(x,y)\leq \epsilon.
$$

\begin{zadacha} Consider any subset of a Euclidean plane
$\R^2$ and the function $d$ defined as $d(a, b)= |ab|$ where $|ab|$ is
the length of a segment $[a, b]$ on the plane. Prove that this defines
a metric space.
\end{zadacha}

\begin{zadacha} Consider the function  $d_\infty:\;\R^2\times \R^2
\to \R$:
$$
(x, y), (x', y') \mapsto \max (|x-x'|, |y-y'|).
$$
Prove that this is a metric. Describe a unit ball with the center in zero.
\end{zadacha}

\begin{zadacha} Consider a function $d_1:\;\R^2\times \R^2 \to \R$:
$$
(x, y), (x', y') \mapsto |x-x'|+ |y-y'|.
$$
Prove that this is a metric. Describe a unit ball with the center in zero.
\end{zadacha}

\begin{zadacha}[*] A function $f:\; [0, \infty[ \to [0, \infty[$ is
  said to be {\bf upper convex} if $f(\frac{ax+by}{a+b}) \geq \frac{
    af(x) + bf(y)}{a+b}$, for any positive $a$, $b\in \R$.  Let $f$ be
  such a function and $(X, d)$ be a metric space.  Suppose that
  $f(\lambda)=0$ iff $\lambda = 0$. Prove that the function $d_f(x,y)
  = f(d(x,y))$ defines a metric on $X$.
\end{zadacha}

\begin{zadacha} Let $V$ be a linear space with a positive bilinear
  symmetric form $g(x,y)$ (in what follows we will call that form a
  {\bf dot product}). Define the ``distance'' $d_g:\; V\times V \to
  \R$ as $d_g(x, y) = \sqrt{g(x-y, x-y)}$. Prove that $d(x,y)\geq 0$
  where equality holds iff $x=y$.
\end{zadacha}

\begin{opredelenie} Let $x\in V$ be a vector from a vector space $V$.
{\bf Parallel transport along vector $x$} is a mapping  $P_x:\;
V \to V$, $y\mapsto y+x$.
\end{opredelenie}

\begin{zadacha} Prove that a function $d_g$ is ``invariant with
  respect to parallel transports'', i.e.  $d_g(a, b) = d_g
(P_x(a), P_x(b))$.
\end{zadacha}

\begin{zadacha} Prove that if $y \neq 0$, then  $d_g$ satisfies the
  triangle inequality:
$$
\sqrt{g(x-y,x-y)} \leq \sqrt{g(x,x)}+ \sqrt{g(y,y)}
$$
\end{zadacha}

\begin{ukazanie} Consider a two-dimensional subspace $V_0 \subset V$,
  generated by $x$ and $y$. Prove that it is isomorphic (as a space
  with dot product) to the space $\R^2$ with dot product $g((x,y),
  (x', y')) = xx' + yy'$.  Use the triangle inequality for $\R^2$.
\end{ukazanie}

\begin{zadacha}[!] Prove that $d_g$ satisfies the triangle
  inequality.
\end{zadacha}

\begin{ukazanie} Use invariance of parallel transports and reduce to
  the previous problem.
\end{ukazanie}

\begin{opredelenie} Consider a vector space  $V$ with a dot product
  $g$, and let $d_g$ be the metric constructed above. This metric is
  called a {\bf euclidean} metric.
\end{opredelenie}

\begin{opredelenie} Consider a vector space $V$, a parallel transport
  $P_x: \; V \to V$ and a one-dimensional subspace $V_1\subset V$.
Then the image $P_x(V_1)$ is called a {\bf line} in $V$.
\end{opredelenie}

\begin{zadacha} Consider two different points in $x, y \in V$. Prove
  that there exists a unique line $V_{x,y}$ through $x$ and $y$.
\end{zadacha}

\begin{opredelenie} Consider a line $l$ through points 
 $x$ and $y$, and a point $a$ on $l$. We say that $a$
 lies {\bf between} $x$ and $y$, if  $d(x,a)+ d(b,y)= d(x,y)$.
A {\bf line segment between $x$ and $y$} 
(denoted $[x,y]$) is the set of all points belonging to the line $V_{x,y}$,
that ``lie between'' $x$ and $y$. 
\end{opredelenie}

\begin{zadacha} consider three different points on a line. Prove that
  one (and only one) of these points lies between two other points.
Prove that the line segment $[x,y]$ is a set of all points  $z$ of the
form $a x + (1-a) y$, where $a \in [0, 1] \subset \R$.
\end{zadacha}

\begin{opredelenie} Consider a vector space $V$, and let $B\subset V$
  be its subset. We say that $B$ is {\bf convex} if 
$B$ contains all points of the line segment $[x,y]$
for any $x, y \in V$. 
\end{opredelenie}

\begin{opredelenie} Let $V$ be a vector space 
over $\R$. A {\bf norm} on $V$ is a function $\rho:\; V
\to \R$, such that the following hold:
\begin{enumerate}
\item For any $v\in V$ one has $\rho(v) \geq 0$. Moreover,
$\rho(v)>0$ for all nonzero $v$.

\item $\rho(\lambda v) = |\lambda| \rho(v)$

\item For any $v_1, v_2\in V$ one has $\rho(v_1+ v_2) \leq
\rho(v_1)+ \rho(v_2)$.
\end{enumerate}
\end{opredelenie}

\begin{zadacha} Consider a vector space $V$ over $\R$, and let
  $\rho:\; V \to \R$ be a norm on $V$.  Consider the function $d_\rho:\;
  V \times V \to \R$, $d_\rho (x, y) = \rho(x-y)$. Prove that this is
  a metric on $V$.
\end{zadacha}

\begin{zadacha}[*] Let $d:\; V \times V \to \R$ be a metric on  $V$,
  invariant w.r.t. the parallel transports. Suppose that $d$ satisfies
$$
d(\lambda x, \lambda y)= |\lambda| d(x,y)
$$
for all $\lambda \in \R$. Prove that $d$ can be obtained from the norm
$\rho:\; V \to \R$ by using the formula $d (x, y) = \rho(x-y)$.
\end{zadacha}

\begin{zadacha} Let $V$ be a linear space over $\R$ and $\rho:\; V \to
  \R$ be a norm on $V$. Consider the set $B_1(0)$ of all points with
  the norm $\leq 1$. Prove that this set is convex.
\end{zadacha}

\begin{opredelenie} Consider a vector space $V$ over $\R$ and let $v$
  be a nonzero vector. Then the set of all vectors of the form $\{
  \lambda v\mid \lambda >0\}$ is called a {\bf half-line} (or a
  {\bf ray}) in $V$.
\end{opredelenie}

\begin{opredelenie} A {\bf central symmetry} in $V$ is the mapping $x
  \mapsto -x$.
\end{opredelenie}

\begin{zadacha}[*] Consider a central symmetric convex set 
$B\subset V$ that does not contain any half-lines and has an
intersection with any half-line $\{
\lambda v\mid \lambda >0\}$. Consider the function $\rho$
$$
v \overset{\rho}{\mapsto} \inf\{\lambda \in \R^{>0}\ \ | \ \ \lambda
v\notin B\}
$$
Prove that this is a norm on $V$. Prove that all the norms can be
obtained that way.
\end{zadacha}

\begin{zadacha} Consider an abelian group $G$ and a function $\nu:\; G
  \to \R$ satisfying $\nu(g)\geq 0$ for all $g\in G$, and $\nu(g)>0$ 
  whenever $g\neq 0$. Suppose that $\nu(a+b) \leq \nu(a) + \nu(b)$, $\nu(0)=0$
  and that $\nu(g) = \nu(-g)$ for all $g\in G$.  Prove that the
  function $d_\nu:\; G \times G \to \R$, $d_\nu(x, y) = \nu (x-y)$ is
  a metric on $G$.
\end{zadacha}

\begin{zadacha} A metric $d$ on an abelian group $G$ is called an
{\bf invariant} metric if $d(x+g, y+g) = d(x,y)$ for all $x, y, g
\in G$. Prove that any invariant metric $d$ 
is obtained from a function $\nu:\; G \to \R$ by setting $d(x, y) = \nu
(x-y)$.
\end{zadacha}

\begin{opredelenie} 
Fix a prime number $p\in \Z$. The function $\nu_p:\; \Z
\to \R$, which given a number $n = p^k r$ ($r$ is not divisible by
$p$) yields  $p^{-k}$, and  satisfies $\nu_p(0)=0$,  is called the 
{\bf $p$-adic norm on $\Z$}.
\end{opredelenie}

\begin{zadacha} Prove that the function  $d_p(m, n) = \nu_p(n-m)$
defines a metric on $\Z$. This metric is called {\bf $p$-adic metric on $\Z$}.
\end{zadacha}

\begin{ukazanie} Check that $\nu_p(a+b) \leq \nu(a) +
\nu(b)$ holds and use the previous problem.
\end{ukazanie}

\begin{opredelenie} Let $R$ be a ring and $\nu:\; R \to \R$ be a
  function that is positive and yields strictly positive values for
  all nonzero $r$. Suppose that $\nu(r_1 r_2) =
\nu(r_1) \nu(r_2)$ and $\nu(r_1+r_2) \leq \nu(r_1) + \nu(r_2)$.
Then $\nu$ is called a {\bf norm} on $R$. A ring endowed with
a norm is called a {\bf normed ring}.
\end{opredelenie}

\begin{zamechanie} It follows from the problems above that a norm on a
  ring $R$ defines an invariant metric on $R$. In what follows any
  normed ring will be regarded as a metric space.
\end{zamechanie}

\begin{zadacha} Prove that $\nu_p$ is a norm on a ring  $\Z$. Define a
  norm on $\Q$ that extends $\nu_p$.
\end{zadacha}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subs{Complete metric spaces.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{opredelenie} Let $(X, d)$ be a metric space and $\{a_i\}$ be a
  sequence of point from $X$. A sequence $\{a_i\}$ is called a {\bf
    Cauchy sequence}, if for every $\epsilon>0$ there exists an
  $\epsilon$-ball in $X$ which contains all but a finite number of
  $a_i$.
\end{opredelenie}

\begin{zadacha} Let $\{a_i\}$, $\{b_i\}$ be Cauchy sequences in
  $X$. Prove that $\{ d(a_i, b_i)\}$ is a Cauchy sequence in $\R$.
\end{zadacha}

\begin{opredelenie} Let $(X, d)$ be a metric space
and $\{a_i\}$, $\{b_i\}$ be Cauchy sequences in
$X$. Sequences $\{a_i\}$ and $\{b_i\}$ are called {\bf
equivalent}, if the sequence  $a_0, b_0, a_1, b_1,\ldots$
is a Cauchy sequence.
\end{opredelenie}

\begin{zadacha} Let $\{a_i\}$, $\{b_i\}$ be Cauchy sequences in
$X$. Prove that $\{a_i\}$, $\{b_i\}$ are equivalent iff
 $\lim_{i\to \infty} d(a_i, b_i) =0$.
\end{zadacha}

\begin{zadacha} Let $\{a_i\}$, $\{b_i\}$ be equivalent Cauchy sequences
in  $X$, and $\{c_i\}$ be another Cauchy sequence. Prove that
$$
\lim_{i\to \infty} d(a_i, c_i)=
   \lim_{i\to \infty} d(b_i, c_i)
$$
\end{zadacha}

\begin{zadacha}[!] Let $(X, d)$ be a metric space and $\overline{X}$
  be the set of equivalence classes of Cauchy sequences. Prove that
  the function
$$
\{a_i\}, \{b_i\} \mapsto \lim_{i\to \infty} d(a_i, b_i)
$$
defines a metric on $\overline X$.
\end{zadacha}

\begin{opredelenie}\label{compl.bad.defn} 
In that case, $\overline{X}$ is called the {\bf completion of $X$}.
\end{opredelenie}

\begin{zadacha} Consider a natural mapping
$X \to \overline{X}$, $x \mapsto \{ x, x, x, x, ...\}$. Prove that 
it is an injection which preserves the metric.
\end{zadacha}

\begin{opredelenie} Let $A$ be a subset of $X$.
An element $c\in X$ is called an {\bf accumulation point (limit point)} of a set 
$A$ if any open ball containing $c$ contains an infinite number of
elements of $A$.
\end{opredelenie}

\begin{zadacha} Prove that a Cauchy sequence cannot have
  more than one accumulation point.
\end{zadacha}

\begin{opredelenie} Let $\{a_i\}$ be a Cauchy sequence. It is said
  that $\{a_i\}$ {\bf converges to $x\in X$}, or that $\{a_i\}$ {\bf 
has the limit $x$} (denoted as $\lim_{i\to \infty} a_i =x$), if $x$
is an accumulation point of $\{a_i\}$
\end{opredelenie}

\begin{opredelenie}
A metric space $(X,d)$ is called {\bf complete} if any Cauchy sequence
in $X$ has a limit.
\end{opredelenie}

\begin{zadacha}[!] Prove that the completion of a metric space is complete.
\end{zadacha}

\begin{opredelenie} A subset $A \subset X$ of a metric space 
is called {\bf dense} if any open ball in $X$ contains an element from
$A$. 
\end{opredelenie}

\begin{zadacha} Prove that $X$ is dense in its completion $\overline{X}$.
\end{zadacha}

\begin{zadacha}[*]
  Let $X$ be a metric space and consider a metric preserving mapping
  $j: X \to Z$ from $X$ into a complete metric space $Z$. Prove that $j$
  can be uniquely extended to $\overline{j}:\overline{X} \to Z$.
\end{zadacha}

\begin{zamechanie}
This problem can be used as a definition of 
$\overline{X}$. The definition~\ref{compl.bad.defn} then becomes a
theorem. 
\end{zamechanie}

\begin{zadacha}[!] Let $R$ be a ring endowed with a norm $\nu$.
  Define addition and multiplication on the completion of $R$ with
  respect to the metric corresponding to $\nu$. Prove that
  $\overline{R}$ has a norm that extends the norm $\nu$ on $R$.
\end{zadacha}

\begin{opredelenie} The normed ring $\overline{R}$ is called the 
{\bf completion of $R$ with respect to the norm $\nu$.}
\end{opredelenie}

\begin{zadacha}[*] Let $R$ be a normed ring and $\overline{R}$ be its
  completion. Suppose that $R$ is a field. Prove that $\overline{R}$
  is also a field.
\end{zadacha}

\begin{zadacha}[*] Let $R$ be a ring without zero divisors  (i.e.\
  it satisfies the following property: if
  $r_1$, $r_2$ are nonzero elements, then $r_1r_2$ is also non-zero).
Consider a function $\nu:\; R \to \R$ which maps all non-zero elements
of $R$ to unity and maps zero to zero. Prove that $\nu$ is a
norm. What is $\overline{R}$? 
\end{zadacha}

\begin{zadacha} Prove that $\R$ can be obtained as the completion of
$\Q$ with respect to the norm $q \mapsto |q|$. 
Can this statement be used
as a definition of $\R$?
\end{zadacha}

\begin{opredelenie} The completion of $\Z$ with respect to the norm
$\nu_p$ is called the {\bf ring of integer $p$-adic numbers}. This ring
is denoted by $\Z_p$.
\end{opredelenie}

\begin{zadacha} Let $(X, d)$ be a metric space and $\{a_i\}$ be a
  sequence of points in $X$.  Suppose that the series $\sum d(a_i,
  a_{i-1})$ converges. Prove that $\{a_i\}$ is a Cauchy sequence. Is
  the converse true?
\end{zadacha}

\begin{zadacha}[!] Prove that for any sequence of integer numbers
  $a_k$ the series $\sum a_k p^k$ converges in $Z_p$.
\end{zadacha}

\begin{ukazanie} Use the previous problem.
\end{ukazanie}

\begin{zadacha} Prove that $(1-p) (\sum_{k=0}^\infty  p^k) =1$
in $Z_p$.
\end{zadacha}

\begin{zadacha}[*] Prove that any integer number which is not
  divisible by $p$ is invertible in $Z_p$.
\end{zadacha}

\begin{opredelenie} The completion of  $\Q$ with respect to the norm
  obtained by extension of $\nu_p$, is denoted by $\Q_p$ and is called
the   {\bf field of $p$-adic numbers}.
\end{opredelenie}

\begin{zadacha}[*] Take $x\in \Q_p$. Prove that 
$x = \frac {x'}{p^k}$, where $x'\in \Z_p$.
\end{zadacha}

\begin{zadacha}[*]
Prove that $\lim\limits_{n\to \infty} \sqrt[n]{n}=1$.
\end{zadacha}

\begin{opredelenie} A norm $\nu$ on a ring $R$ is called
{\bf non-Archimedean}, if $\nu (x+y) \leq \max (\nu(x), \nu(y))$
for all $x,y$. Otherwise the norm is called {\bf Archimedean}.
\end{opredelenie}

\begin{zadacha}[*] Let $\nu$ be a norm on $\Q$.  Prove that $\nu$ is
  non-Archimedean iff $\Z$ is contained in the unit ball.
\end{zadacha}

\begin{ukazanie} Use the following equality: 
$\lim\limits_{n\to \infty} \sqrt[n]{n}=1$.
Find an estimate of $\sqrt[n]{((\nu(x+y)^n)}$ for big $n$ using the
estimate of binomial coefficients: $\nu(\binom{k}{n})\leq 1$.
\end{ukazanie}

\begin{zadacha}[*] Let $\nu$ be a non-Archimedean norm on $\Q$.
Consider ${\mathfrak m} \subset \Z$ consisting of all
integers $n$ such that $\nu(n)<1$. 
Prove that $\mathfrak m$ is an {\em ideal} in $\Z$
(ideal in a ring $R$ is a subset which is closed under addition and
multiplication by elements of $R$). Prove that the ideal
$$
{\mathfrak m} = \{ n\in \Z \ \ | \ \ \nu(n)<1\}
$$
is {\em prime} (prime ideal is an ideal such that $xy \notin
{\mathfrak m}$ for all $x, y \notin {\mathfrak m}$). 
\end{zadacha}

\begin{zadacha}[*] Prove that any ideal in $\Z$ 
is of the form  $\{0, \pm1 m, \pm 2m, \pm3m, ...\}$ for some $m\in \Z$.
Prove that any prime ideal  ${\mathfrak m}$ 
in $\Z$ is of the form $\{0, \pm p, \pm 2p, \pm3p, ...\}$, where $p=0$
or $p$ prime.
\end{zadacha}

\begin{ukazanie} Use the Euclid's Algorithm.
\end{ukazanie}

\begin{zadacha}[*] Let $\nu$ be a non-Archimedean norm $\Q$ and
  $\mathfrak m = \{p, 2p, 3p, 4p, ...\}$ be an ideal constructed
  above. Prove that there exists a real number $\lambda>1$ such that
  $\nu(n) = \lambda^{-k}$ for any $n=p^k r$, $r\not\vdots p$.
\end{zadacha}

\begin{zadacha}[*] Let $\nu$ be a norm on $\Q$ such that
 $\nu(2)\leq 1$. Prove that $\nu(a)< \log_2 (a)+1$
for any integer $a>0$.
\end{zadacha}

\begin{ukazanie} Use the binary representation of a number.
\end{ukazanie}

\begin{zadacha}[*] Let $\nu$ be a norm on $\Q$ such that
  $\nu(2)<1$. Prove that $\nu(a)\leq 1$ for any integer $a>0$ (i.e.\
  $\nu$ is non-Archimedean).
\end{zadacha}

\begin{ukazanie} Deduce from
$\lim\limits_{n\to \infty} \sqrt[n]{n}=1$ that
$\lim\limits_{n\to \infty} \frac{\log n}{n}=0$. Prove
$\lim\limits_{N\to \infty} \nu(a^N)\leq 1$, using the previous
problem. 
\end{ukazanie}

\begin{zadacha}[*] Let $a_i$ be a Cauchy sequence of rational numbers
  of the form $\frac{x}{2^n}$ (``Cauchy sequence'' here means the same
  thing as Cauchy sequence of real numbers).  Suppose that a norm
  $\nu$ on $\Q$ is Archimedean.  Prove that $\nu(a_i)$ is a Cauchy
  sequence.
\end{zadacha}

\begin{ukazanie}
Write down $x$ in the binary system and prove that 
 \[ \nu(x/2^n)\leq
  \nu(2)^{\log_2(x)+1} /\nu(2)^n\leq \nu(2)^{\log_2|x+1/2^n|}.\]
\end{ukazanie}

\begin{zadacha}[*] Deduce that
$\nu$ can be extended to a continuous function on $\R$,
which satisfies $\nu(xy)=\nu(x)\nu(y)$. Prove that 
$\nu$ can be obtained as $x \mapsto |x|^\lambda$ for some constant
$\lambda>0$. Express $\lambda$ in terms of $\nu(2)$.
\end{zadacha}

\begin{zadacha}[*] For which $\lambda>0$ the function  $x \mapsto
|x|^\lambda$ defines a norm on $\Q$?
\end{zadacha}

We have obtained a complete classification of norms on $\Q$: any norm
can be obtained as a power of either a $p$-adic norm or the 
absolute value norm. This classification is called {\bf Ostrovsky theorem}.
\end{document}