INSTRUCTIONS
Remember to latex the file twice to get correct cross references



 The text between the lines BODY and ENDBODY is made  of


  4538 lines and   138546 bytes (not counting <line feed> or <carriage return>)



 In the following table this count is broken down by ASCII  code;
 immediately following the code is the corresponding  character.

     75523  lowercase letters
      3327  uppercase letters
      8828  digits

     13291  ASCII characters  32  
        66  ASCII characters  33 !
        39  ASCII characters  34 "
        29  ASCII characters  35 #
      3696  ASCII characters  36 $
       652  ASCII characters  37 %
       227  ASCII characters  38 &
       275  ASCII characters  39 '
      2395  ASCII characters  40 (
      2392  ASCII characters  41 )
       695  ASCII characters  42 *
       173  ASCII characters  43 +
      2305  ASCII characters  44 ,
       758  ASCII characters  45 -
       998  ASCII characters  46 .
        57  ASCII characters  47 /
       329  ASCII characters  58 :
        74  ASCII characters  59 ;
        66  ASCII characters  60 <
       638  ASCII characters  61 =
        86  ASCII characters  62 >
         2  ASCII characters  64 @
        63  ASCII characters  91 [
      8432  ASCII characters  92 \
        63  ASCII characters  93 ]
       562  ASCII characters  94 ^
      2487  ASCII characters  95 _
        73  ASCII characters  96 `
      4613  ASCII characters 123 {
       605  ASCII characters 124 |
      4613  ASCII characters 125 }
       114  ASCII characters 126 ~

 BODY
\documentstyle[12pt,amssymbols]{article}
\setlength{\hoffset}{-1cm}
\setlength{\voffset}{-2cm}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{23.5cm}
\setlength{\parindent}{8mm}
\frenchspacing
%******************************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%%        FOR SHORT
%%%
%%%
\newcommand{\beq}{ \begin{equation} }
\newcommand{\eeq}{ \end{equation} }
\newcommand{\beqno}{ \begin{equation*} }
\newcommand{\eeqno}{ \end{equation*} }
\newcommand{\beqa}{ \begin{eqnarray} }
\newcommand{\eeqa}{ \end{eqnarray} }
\newcommand{\beqano}{ \begin{eqnarray*} }
\newcommand{\eeqano}{ \end{eqnarray*} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%%        THEOREMS AND ALIKE
%%%
%%%
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}{Definition}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{sublemma}{Sublemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newcommand\dfn[1]{ \begin{definition}\label{#1} \rm}
\newcommand\dfntwo[2]{ \begin{definition}[#1]\label{#2} \rm}
\newcommand\edfn{ \end{definition} }
\newcommand\rem[1]{ \begin{remark}\label{#1} \rm}
\newcommand\erem{ \end{remark} }
\newcommand\thm[1]{ \begin{theorem}\label{#1}}
\newcommand\thmtwo[2]{ \begin{theorem}[#1]\label{#2}}
\newcommand\ethm{ \end{theorem} }
\newcommand\pro[1]{ \begin{proposition}\label{#1}}
\newcommand\protwo[2]{ \begin{proposition}[#1]\label{#2}}
\newcommand\epro{ \end{proposition} }
\newcommand\lem[1]{ \begin{lemma}\label{#1}}
\newcommand\lemtwo[2]{ \begin{lemma}[#1]\label{#2}}
\newcommand\elem{ \end{lemma} }
\newcommand\sublem[1]{ \begin{sublemma}\label{#1}}
\newcommand\sublemtwo[2]{ \begin{sublemma}[#1]\label{#2}}
\newcommand\esublem{ \end{sublemma} }
\newcommand\cor[1]{ \begin{corollary}\label{#1}}
\newcommand\cortwo[2]{ \begin{corollary}[#1]\label{#2}}
\newcommand\ecor{ \end{corollary} }
%%%
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%%       REFERRING TO
%%%
%
\newcommand\equ[1]{{\rm (\ref{#1})}}
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%%       VARIOUS
%%%
\newcommand{\ie}{{\it i.e. }}
\newcommand{\eg}{{\it e.g. }}
\newcommand{\etc}{{\it etc}}
\newcommand{\HB}{\hfill\break}
\newcommand{\acapo}{\linebreak}
\newcommand{\HALF}{{\textstyle{1\over 2}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%                 A CAPO.....
%%%
%%%
%%%
\newcommand{\giu}{{\medskip\noindent}}
\newcommand{\Giu}{{\bigskip\noindent}}
\newcommand{\nl}{{\smallskip\noindent}}
\newcommand{\nin}{{\noindent}}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\newcommand{\qed}{\hskip.5truecm
\vrule width 1.7truemm height 3.5truemm depth 0.truemm}
\newcommand{\qedd}{\vrule width 1.7truemm height 1.7truemm depth 0.truemm}
\newcommand{\QED}{\hfill\smallskip
         \line{\hfill\vrule height 1.8ex width 2ex depth +.2ex
               \ \ \ \ \ \ }
         \bigskip}
\newcommand{\PROOF}{\medskip\noindent{\bf Proof\ }}
\newcommand{\REMARK}{\medskip\noindent{\bf Remark\ }}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%%                         MATH MODE DEFINITIONS:
%%%
%
%
\newcommand{\ci}{ {C^\infty}   }
\newcommand{\ig}{ {\int}   }
\newcommand{\dpr}{ {\partial}   }
%
\newcommand{\torus}{ {\Bbb T}   }
\renewcommand{\natural}{ {\Bbb N}   }
\newcommand{\real}{ {\Bbb R}   }
\newcommand{\integer}{ {\Bbb Z}   }
\newcommand{\complex}{ {\Bbb C}   }
\newcommand{\tN}{ {\torus^N }   }
\newcommand{\rN}{ {\real^N}   }
\newcommand{\cN}{ {\complex^N }   }
\newcommand{\zN}{ {\integer^N }   }
%
\renewcommand{\a }{ {\alpha}   }
\renewcommand{\b}{ {\beta}   }
\newcommand{\g}{ {\gamma}   }
\newcommand{\G}{ {\Gamma}   }
\renewcommand{\d}{ {\delta}   }
\newcommand{\D}{ {\Delta}   }
\newcommand{\e }{ {\varepsilon}   }
\newcommand{\et}{ {\eta}   }
\newcommand{\th }{ {\theta}   }
\newcommand{\vth }{ {\vartheta}   }
\newcommand{\k}{ {\kappa}   }
\renewcommand{\l}{ {\lambda}   }
\renewcommand{\L}{ {\Lambda}   }
\newcommand{\m}{ {\mu}   }
\newcommand{\n}{ {\nu}   }
\newcommand{\x }{ {\csi}   }
\newcommand{\X }{ {\Csi}   }
\newcommand{\p}{ {\pi}   }
\renewcommand{\P}{ {\Pi}   }
\newcommand{\r}{ {\rho}   }
\newcommand{\s}{ {\sigma}   }
\newcommand{\Si}{ {\Sigma}   }
\renewcommand{\t}{ {\tau}   }
\newcommand{\f}{ {\varphi}   }
\newcommand{\ph}{ {\phi}   }
\newcommand{\F}{ {\Phi}   }
\renewcommand{\c}{ {\chi}   }
\newcommand{\ps}{ {\psi}   }
\renewcommand{\o}{ {\omega}   }
\renewcommand{\O}{ {\Omega}   }
%
\renewcommand{\Im}{{\rm Im}}
\renewcommand{\Re}{{\rm Re}}
\renewcommand{\=}{ {\ \equiv\ }   }
%
\newcommand{\implies}{\ \Longrightarrow\ }
\newcommand{\sse}{\ \Longleftrightarrow\ }
%%%
\newcommand{\Xk}{ X^{(k)} }
\newcommand{\Xj}{ X^{(j)} }
\newcommand{\Xh}{ X^{(h)} }
\newcommand{\Tr}{ {T_r} }
%
\newcommand{\cA}{ {\cal A} }
\newcommand{\cT}{ {\cal T} }
\newcommand{\cR}{ {\cal R} }
\newcommand{\cH}{ {\cal H} }
\newcommand{\cC}{ {\cal C} }
\newcommand{\cF}{ {\cal F} }
\newcommand{\calN}{ {\cal N} }
%
\newcommand{\noin}{ {\not\in} }
\renewcommand{\lg}{ {\langle} }
\newcommand{\rg}{ {\rangle} }
\newcommand\agl[1]{ |\lg{#1}\rg|  }
\newcommand\gl[1]{ \lg{#1}\rg  }
\newcommand{\getr}{{{\ge}_{{\phantom{.}}_{\!\Tr}}}}
\newcommand{\baj}{ {\bar\jmath}}
\newcommand{\bai}{ {\bar\imath}}
\newcommand\bks{\backslash}
\newcommand{\zNn}{ {\zN\backslash \{0\} } }
%
\newcommand\bcR{ {\overline {\cal R}} }
\newcommand\bR{ {\overline  R} }
\newcommand\bT{{ \overline  T}}
\newcommand\bu{{ \bar u}}
\newcommand\bv{{ \bar v}}
\newcommand\bw{{ \bar w}}
\newcommand\bk{{ \bar \k}}
\newcommand\bl{{ \bar \l}}
\newcommand\bs{{ \bar \s}}
\newcommand\tT{{ \widetilde T}}
\newcommand\tcT{{ \widetilde \cT}}
\newcommand\hT{{ \widehat T}}
\newcommand\hcT{{ \widehat \cT}}
%********************************************
\begin{document}
%%%%%%%%%%%%%%%%%%%%%% sections:

\title{A Direct Proof of a Theorem by Kolmogorov \\
in Hamiltonian Systems}

\author{ L. Chierchia \\ 
{\footnotesize
Dipartimento di Matematica} \\ 
{\footnotesize Universit\`a di Genova} \\
{\footnotesize via L.B.Alberti 4, 16132 Genova (Italy) }\\ 
{\footnotesize (Internet: chierchia@mat.utovrm.it)}
\and
C. Falcolini \\ 
{\footnotesize Dipartimento di Matematica} \\ 
{\footnotesize Universit\`a di Roma  ``Tor Vergata"}\\
{\footnotesize via della Ricerca Scientifica,
00133 Roma (Italy)} \\
{\footnotesize (Internet: falcolini@mat.utovrm.it)}}

\date{June 8, 1993}
\maketitle

\begin{abstract}

\nin
We present a direct proof of Kolmogorov's theorem on the persistence of 
quasi-periodic solutions for nearly integrable, real--analytic
Hamiltonian systems with Hamiltonians of the form
$\frac{1}{2} y\cdot y-\e f(x)$ where $(y,x)$ $\in$ $\rN \times\tN$
are standard symplectic coordinates. 
The method of proof consists in constructing, via graph theory, 
the formal solution as a formal power series in $\e$
and to show that the $k^{\rm th}$ coefficient of
such formal series can be bounded by a constant to the $k^{th}$ 
power. All details are presented in a self contained way (included what is 
needed from the theory of graphs). 
\end{abstract}

{\footnotesize \tableofcontents}
%********************************************

\section{Introduction}
%
\label{sec:intro}
\setcounter{equation}{0}

%
Each Section of this paper begins with a short summary of what is
done in that Section: Here we present a bit of history of 
Kolmogorov's Theorem on the stability of quasi--periodic solutions
in Hamiltonian systems followed
by a rough outline of a novel proof, based on a tree representation
of formal series.

\giu
A 1954 theorem by Kolmogorov \cite{Ko} guarantees the existence of
infinitely many quasi--periodic solutions for the (standard)
Hamilton equations
associated to real--analytic, ``spatially periodic"
Hamiltonians of the form
$H(y,x;\e)$ $=$ $
h(y)+\e f(y,x)$, ($y\in U$ open subset of $\rN$,
$x\in\tN\=\rN/(2\pi\zN)$, $\e\ge 0$), 
provided the Hessian matrix $(\frac{\dpr h}{\dpr y_i \dpr y_j})$
is invertible on $U$ and provided $|\e|$ is sufficiently small.
We recall that a solution $(y(t),x(t))$ is called (maximal) 
quasi--periodic if there exists a rationally independent
vector $\o\in\rN$ and smooth functions $Y,X:\tN\to\rN$ such that 
$(y(t),x(t))=(Y(\o t),\o t+ X(\o t))$.
A detailed proof, different from that outlined by Kolmogorov in \cite{Ko},
was provided, in 1963,  
by V.~I.~Arnold in \cite{A1} and J.~Moser \cite{Mo1} proved,
in the same period, an analogous theorem for symplectic diffeomorphisms
removing the hypothesis of analyticity of the perturbation.
The {\it corpus} of results and methods stemmed out from Kolmogorov's
original ideas is now known as ``KAM (Kolmogorov--Arnold--Moser) 
theory".

It is not difficult to write down {\em formal $\e$--expansion}
of quasi--periodic solutions; the problem is then turned into
whether such series are convergent or not. This question
was extensively and thoroughly investigated by 
H.~Poincar\'e in his
{\it m\'ethodes nouvelle de la m\'ecanique c\'eleste} \cite{Po}.
Poincar\'e, following M.~Lindstedt ({\em M\'emoires de l'Acad\'emie de
Saint--P\'etersbourg}, 1882), considered formal 
quasi--periodic solutions for which {\em $\o$ depends on $\e$}
and showed that such series are {\em divergent} (\cite{Po}, vol. II,
\S XIII). The main problem in this context is
that the formal solution has Fourier
coefficients which are divided by terms
of the type $\o\cdot n$ $\equiv$ $\sum_{i=1}^N \o_i n_i$
with $n\in \zNn$, and such factors (``small divisors")
become arbitrarily small as $|n|\to\infty$.
In fact (see Section~\ref{sec:diverge} below),
the {\em repeated occurrence of small divisors} (``resonances")
in the $k^{\rm th}$
coefficient of the formal solution leads to
contributions of the order of $(k!)^a$ with $a>0$.
However, in 1967 Moser \cite{Mo2} showed {\em indirectly} (see below)
that the formal series {\em converges} leading to analytic solutions,
provided the {\em $\e$--independent} vector $\o$ 
satisfies certain number 
theoretic assumptions (verified by almost all (with respect to Lebesgue 
measure) vectors in $\rN$; see the ``Diophantine condition" \equ{dioph}
below). 
This means that the $k^{\rm th}$ coefficient
of the formal solution contains {\em many  huge contributions which
compensate among themselves} 
producing terms that behaves like a constant
to the $k^{\rm th}$ power. Moser's proof, as well as {\em all}
proofs in KAM theory (up to the 1988 Eliasson work \cite{E}),
are based on a ``rapidly convergent" iteration technique.
The strategy, similarly to Newton's method of tangents, consists in 
finding solutions of a nonlinear differential equation
$\calN(u)=0$ by solving  recursively a sequence of approximate equations
of the form $\calN(u_j)=e_j$ 
where the size of the ``error function" $e_j$ 
becomes {\em quadratically smaller} at each step of the procedure.
Such an approach has many advantages and can be used very effectively
(see \cite{CC} for accurate estimates 
and Appendix~2 in \cite{CP} for a five--page proof)
but is indirect and 
hides the mechanism beyond the above mentioned compensations.

In the different context of linearization of germs of analytic
diffeomorphisms, C.~L.~Si\-e\-gel \cite{S} succeeded in 1942
in proving directly the convergence of formal power series
involving small divisors: the crucial difference being that
the small divisors are of the form $\o\cdot n$ {\em with 
$n\in\natural^N$} so that a given divisor {\em occurs at most once}
in each coefficient of the formal solution (\ie ``there are no
resonances"). 

In 1988 Eliasson, in a Report of the University of Stockholm
\cite{E} (which to the best of our knowledge has not been published),
extended Siegel's method so as to cover the Hamiltonian case. 
We present a different version of Eliasson's proof
based on a tree representation of the formal solutions
and on the explicit exhibition of compensations of huge
contributions. We follow closely \cite{E} in its convenient
reformulation of Siegel's method (see Lemma~\ref{lem:se} 
below)
which allows to bound product of (possibly) small divisors
whenever (certain dangerous) repetition do not occur; however
for the crucial part (grouping together the huge contributions)
we adopt a different approach which now we outline.

In order to simplify the presentation {\em we consider
the particular model with Hamiltonian} 
$H= \frac{1}{2}y\cdot y-\e f(x)$: The extension of our method
to the general situation is rather straightforward but
would lead to heavier notations without providing any new insight.

The {\em starting point} is to express the coefficients of the formal
solution in terms of {\em labeled rooted trees}\footnote{The
use of graph theory in connection with formal power series is 
natural and very old (see \eg \cite{GJ} and references therein);
for connections with KAM theory see \cite{CG} and \cite{G}.}.
This allows to express the $k^{\rm th}$ coefficient
in terms of 
a sum over all possible labeled rooted trees of order $k$,
and over all possible (and ``admissible") 
integers $\a_v\in\zNn$ ($v$ denoting a vertex of a tree)  
of
\beq
\prod_V f_{\a_v} \prod_E \a_v\cdot\a_{v'}\ \prod_{V}\d_v^{-2}
\label{1.1}
\eeq
where $V$ and $E$ denote, as customary, the set of vertices $v$ 
and edges $vv'$ of a given tree (see Appendix~\ref{app:tree}), 
$f_n$ denote Fourier 
coefficients of $f$ and $\d_v$ represents the divisor associated
to the vertex $v$ \ie $\d_v\=\o\cdot \sum_{v'\le v} \a_{v'}$
(rooted trees have a natural order according to which the root $r$
is $>v$ for all vertices $v\in V$, $v\neq r$;  the square in \equ{1.1}
comes from the fact that the Hamilton equations for our model
can be immediately written as the second order system
$\ddot x = f_x$; ``admissible" means that $\d_v\neq 0$ $\forall$
$v$ \ie $\sum_{v'\le v} \a_{v'}\neq 0$ $\forall$ $v\in V$).

Now, the {\em main point}
is to make a {\em partition} of the trees of order $k$
into families $\cF$ (called below ``complete families")
so as to be able to bound sums over such families by a
constant to the $k^{\rm th}$ power (recall that even single
contributions given by \equ{1.1} may have size of order
$(k!)^a$ as already mentioned). The main technical estimate is
%
\beq
\big| 
\sum_{T\in\cF} \prod_{vv'\in E(T)} \a_v\cdot\a_{v'}
\prod_V \d_v^{-2}\big| \le
\prod_{v\in V} |\a_v|^{\deg_\cF v} \ c_4^k\ \prod_{v\in V}
|\a_v|^{\b_4}
\label{1.2}
\eeq
for suitable constants $c_4$ and $\b_4$, determined below,
depending on $N$ and on the
numerical properties of the vector $\o$; 
$\deg_\cF v$ is defined
as the maximum degree of $v$ when $T$ varies in the family $\cF$.
Obviously, it is crucial that complete families either do not intersect
or coincide (in fact it is much easier to find families of trees
for which \equ{1.1} holds but which do not form a partition:
clearly such families are of no use for our purposes).
The construction of the partition of complete families is
the delicate part of our paper\footnote{In \cite{G} the problem analyzed
here is also investigated with similar tools; however the families
of trees considered there, as well as most of the technical aspects,
are different from ours.}.
Given Eliasson's version
of Siegel's method  (which we include for completeness)
and the identification of complete
families, the convergence of the formal solutions follows
very easily (under the Diophantine condition on $\o$).
All the constants are computed explicitly 
(see Remark~\ref{rem:constants} below).

\giu
We close this introduction by mentioning possible directions of future 
researches. 

\nin
(i) The method of proof presented here, being based on
a very direct approach, seems particularly suitable for computer--aided
implementations and might shed some new light on the difficult problem of 
the break--down of stability of quasi--periodic solutions in connection
with the $\e$--singularities of the function $X$ (see, \eg,
\cite{CC}, \cite{BC}, \cite{BCCF}, \cite{FL} and references therein).

\nin
(ii) Let $(x^1,x^2)$ with $x^i\in \torus^{N_i}$ and $N_1+N_2=N$,
let $\o\in \real^{N_1}$ 
and let $x^2_0$ be a nondegenerate critical point of the 
periodic function $x^2\in\torus^{N_2}\to\int_{\torus^{N_1}} 
f(x^1,x^2)dx^1$. Then, it is not difficult to see that (if $\o$ satisfies a 
Diophantine condition) there are formal (non maximal) quasi--periodic 
solutions whose first term ($\e=0$) is given by $(\o t,x_0^2)$.
It would be nice to extend the proof in this paper so as to
establish convergence for such formal series.

\nin (iii) It is well known (\cite{Ru}) that maximal quasi--periodic 
solutions are stable under weaker assumptions on the vector $\o$
than the classical one made here. It might be interesting to see how far,
in this direction, can lead the technique worked out in this paper.

\giu
The paper is organized as follows.
In Section~\ref{sec:formal} existence and uniqueness of formal
quasi--periodic solutions are established.
In Section~\ref{sec:tree} the tree expansion of formal 
quasi--periodic solutions is given (the purely combinatorics
aspects are proven in Appendix~\ref{app:combina}). The occurrence
of huge terms is explicitly exhibited in Section~\ref{sec:diverge}.
The construction of complete families is carried out in
Section~\ref{sec:resona} allowing to formulate the
results in Section~\ref{sec:estima} divided in four Lemmas
and one Theorem. Detailed proofs are given in 
Section~\ref{sec:proofs}. 
Graph theory is used here mainly as a (very useful!) language
and the basic definitions (enough to read our paper
without any knowledge of graph theory) are presented in 
Appendix~\ref{app:tree}.

%********************************************

\section{Formal Quasi--Periodic Solutions}
%
\label{sec:formal}
\setcounter{equation}{0}
%
We recall the notions of quasi--periodic and formal quasi--periodic
solution for a ``spatially periodic" Hamiltonian.

\giu
Let $H(y,x)$ be a $\ci(U\times \tN)$ Hamiltonian where $U$ is
an open set of $\rN$ and $\tN$ $\=$ $\rN/2\pi\zN$
(\ie $H$ can be seen as a function of the $2N$ variables
$y_1,...y_N$,$x_1,...,x_N$, $2\pi$--periodic in $x_i$). 
Consider the standard Hamilton equations: 
\begin{equation}
\dot y= - H_x\ ,\qquad 
\dot x= H_y
\label{2.1}
\end{equation}
where, as usual, 
$H_x\=\dpr_x H\=(\frac{\dpr H}{\dpr x_1},..., \frac{\dpr H}{\dpr x_N})$
and
$H_y\=\dpr_y H\=(\frac{\dpr H}{\dpr y_1},..., \frac{\dpr H}{\dpr y_N})$. 
A solution
$(y(t),x(t))$ of \equ{2.1} is called {\em (maximal) quasi--periodic}
with frequency $\o\in\rN$ if $\o$ is rationally independent (\ie
$\o\cdot n\=\sum_{i=1}^N\o_i n_i=0$ 
for some $n\in \zN$ implies $n=0$) and if there
exist smooth functions $Y,X:\tN\to\rN$ such that 
\begin{equation}
y(t)=Y(\o t)\ ,\qquad x(t)=\o t+ X(\o t)
\label{2.2}
\end{equation}
The rational independence of $\o$ easily implies that the functions
$\th\in\tN\to Y(\th),X(\th)$ satisfy the system of equations:

\newpage
\begin{eqnarray}
D Y  =& -H_x(Y,\th+X)\ , &\qquad( D\=\sum_{i=1}^N\o_i\dpr_{\th_i})
\nonumber\\
\o + D X  =& H_y(Y,\th+X)
\label{2.3}
\end{eqnarray}
Viceversa, given a solution of \equ{2.3}, \equ{2.2}
(or more generally \equ{2.2} with $\o t$ replaced by $\th+\o t$
for any $\th\in\tN$) is a quasi--periodic solution of \equ{2.1}.

``Le probl\`eme g\'en\'eral de la dynamique" 
according to Henri Poincar\'e (\cite{Po}, vol. I, chapter I, \S 13)
is the study of the equations governed  
by the ``nearly--integrable" Hamiltonian
\begin{equation}
H(y,x;\e)\=h(y)+\e f(y,x)
\label{h}
\end{equation}
for small values of the parameter $\e$. As we shall see below,
if the Hessian matrix 
$h''$ $\=$ $h_{yy}$ $\=$ $\big(\frac{\dpr^2 h}{\dpr y_i \dpr y_j}\big)$ 
is invertible, then there are ``a lot" of ``formal quasi--periodic
solutions" of the equations \equ{2.1} with Hamiltonian \equ{h}.

A {\em formal $\e$--power series $F$, over $\tN$}, is an infinite sequence
of $\ci(\tN)$ functions $\{ F_k\}_{k\ge 0}$, $F_k=F_k(\th)$, and it is 
customary to write $F\sim \sum_{k\ge 0} F_k \e^k $. If $g$ is a
$\ci$ function and $F\sim \sum_{k\ge 0} F_k \e^k$ a formal series,
one naturally defines the formal series $g\circ F\sim \sum_{k\ge 0}
G_k \e^k$ by setting
\begin{equation}
G_k= \left[ g\big( \sum_{h=0}^k F_h \e^h\big) \right]_k
\= \frac{1}{k!}\  \frac{d^k}{d\e^k}\  g\big(\sum_{h=0}^k F_h \e^h\big)
\Big|_{\e=0}
\label{2.4}
\end{equation}
A formal solution of \equ{2.3} with $H$ as in \equ{h} is a couple of
(vector--valued) formal $\e$--power series over $\tN$,
$Y\sim \sum_{k\ge 0} Y^{(k)} \e^k$, 
$X\sim \sum_{k\ge 0} X^{(k)} \e^k$, 
($Y^{(k)}, X^{(k)}:$ $\tN\to\rN$), verifying \equ{2.3} in the sense 
of formal series (\ie ``$=$" should be replaced by ``$\sim$") or
equivalently:
\begin{eqnarray}
D Y^{(0)} =& 0 \ ,\phantom{Y^{(h)}}  & D Y^{(k)} = \left[
-f_x(\sum_{h=0}^{k-1} Y^{(h)} \e^h ,
\th+\sum_{h=0}^{k-1} X^{(h)}\e^h )\right]_{k-1} \nonumber\\
\o + D X^{(0)} =&  h_y(Y^{(0)})  \ ,\  & D X^{(k)} = \left[
H_y(\sum_{h=0}^{k} Y^{(h)}\e^h ,
\th+\sum_{h=0}^{k-1} X^{(h)}\e^h )\right]_{k} 
\label{2.5}
\end{eqnarray}
where $k\ge 1$; notice the different ranges of indices in the equation for
$D \Xk$ due to the particular form of \equ{h}.

\begin{proposition}
\label{pro:ef}
Let $H$ as in \equ{h} be $\ci$ in a neighborhood of
$\{y_0\}\times \tN$ with $y_0$ such that $h''(y_0)$ is invertible
and $\o\=h'(y_0)\=h_y(y_0)$ is ``Diophantine"
\ie such that
%
\footnote{\rm It is well known that for any $\t>N$, 
almost all (with respect to Lebesgue measure)
$\o\in \rN$ satisfy \equ{dioph} with some $\g>0$ 
(see, \eg, \cite{A2}, chapter I, \S 3) while if $\t=N-1$
then for any $\o\in\rN$ there exist a $\g>0$ and
an infinite number of $n\in\zN$ such
that \equ{dioph} is violated
(this is a theorem by Dirichlet, see, \eg, \cite{Sc}).}
%
\begin{equation}
|\o\cdot n| \ge \frac{1}{\g |n|^\t}\ ,\qquad
\forall\ n\in\zN\backslash\{0\}\ \quad {\rm for\quad some}\quad
\g,\t>0\ .
\label{dioph}
\end{equation}
Then there exists a unique formal quasi--periodic solution $Y,X$ of
\equ{2.5} with
\begin{equation}
\ig_{\tN} X^{(k)} d\th=0\ ,\qquad \forall\ k\ .
\label{av}
\end{equation}
\end{proposition}
%
\PROOF We construct the formal solution by induction over $k$.
For $k=0$ we get immediately from \equ{2.5} that $Y^{(0)}$ and
$X^{(0)}$ are constant vectors and that $h'(Y^{(0)})=\o$
(as if $g$ is a smooth function over $\tN$ and $Dg=a$ with
some constant $a$, then $g\=0=a$) so that, from our hypotheses it follows
that $Y^{(0)}=y_0$; requirement \equ{av} fixes the constant vector 
$X^{(0)}$ to be zero. Let, now, $k\ge 1$ and assume that 
$y_0, Y^{(1)},...,Y^{(k-1)}$,  
$X^{(1)},...,X^{(k-1)}$, are smooth functions over $\tN$ solving 
\equ{2.5} with $\int_\tN X^{(h)}=0$. We claim that 
\begin{equation}
\int_\tN \phi^{(k)}(\th)\=
\int_\tN\Big[ f_x \big( \sum_{h=0}^{k-1} \e^h Y^{(h)}, \th +\sum_{h=0}^{k-1}
\e^h X^{(h)} \big) \Big]_{k-1} = 0
\label{clm}
\end{equation}
(note that the claim is obvious for $k=1$ as in such a case 
\equ{clm} is just the average of the gradient of a periodic function).
If the claim is true, then the proposition follows easily:
$\phi^{(k)}(\th)$ would be a $\ci$ (vector--\-valued) function over $\tN$
with zero average and therefore the solutions of the equation $DY^{(k)}=
\phi^{(k)}$ are given by $Y^{(k)}=D^{-1}\phi^{(k)} + c_k$
with $c_k$ constant and $D^{-1}\phi^{(k)}$ the smooth function with zero average
given in Fourier expansion by
\begin{equation}
D^{-1}\phi^{(k)}\= \sum_{{n\in\zN}\atop{n\neq 0}} \frac{\phi^{(k)}_n}
{i\o\cdot n} e^{i n\cdot \th}
\label{phi}
\end{equation}
where $\phi^{(k)}_n$ are the Fourier coefficients of $\phi^{(k)}$
(notice that the fast decay of the Fourier coefficients of the smooth
function $\phi^{(k)}$ yields the fast decay, in view of \equ{dioph},
of the coefficients in \equ{phi}, ensuring that $D^{-1}\phi^{(k)}$ 
is $\ci(\tN)$). The constant $c_k$ is not arbitrary, as the right hand side 
of the second of \equ{2.5}, in order to make sense,
must have vanishing mean value over $\tN$;
rewriting such equation we get
\begin{eqnarray} 
D X^{(k)} & =  & h_{yy}(y_0) Y^{(k)} + \big[ h_y (\sum_{h=0}^{k-1}
\e^h Y^{(h)} ) \big]_k + \left[ f_y (\sum_{h=0}^{k-1} \e^h Y^{(h)},
\th+\sum_{h=0}^{k-1} \e^h X^{(h)} )\right]_{k-1}
\nonumber \\
& \equiv & h_{yy} (y_0) c_k + \psi^{(k)}\nonumber \\
\label{Xk}
\end{eqnarray}
where $\psi^{(k)}$ is a smooth function (depending on $H$ and
$X^{(h)},Y^{(h)}$ for $h\le k-1$) so that
\begin{equation}
c_k= h_{yy}(y_0)^{-1} \int_\tN\psi^{(k)} 
\label{ck}
\end{equation}
in which case \equ{Xk} has a unique solution with 
$\int_\tN X^{(k)}=0$. 

\nin
It remains to prove \equ{clm}.
Observe that for any (smooth) functions $\bar X, \bar Y$ over $\tN$
one has
\begin{equation}
\int \Big\{ 
\big( D \bar Y + H_x(\bar Y, \th+\bar X) \big) \ 
\big( I + \dpr_\th \bar X \big) \ -
\ \big( \o + D \bar X - H_y(\bar Y, \th + \bar X)\big)\ \dpr_\th \bar Y
\Big\} d\th = 0
\label{av2}
\end{equation}
where $\dpr_\th \bar X$ is the matrix $(\dpr_\th \bar X)_{ij}\=\dpr_{\th_j}
\bar X_i$ and we adopted the standard convention about row--by--column
multiplication of matrices (interpreting vectors as (respectively) $1\times N$
($N\times 1$) matrices if they are to the left  (right) of an 
$N\times N$--matrix); 
identity \equ{av2} follows immediately if one notices that 
$(H_x)(I+\dpr_\th \bar X)+(H_y)(\dpr_\th Y)$ is just the $\th$--gradient
of $\th\to H(\bar Y,\th+\bar X)$ (so that its average vanishes) and that
the remaining terms in \equ{av2} disappear by integration by parts.
Now, we use \equ{av2} with $\bar Y=\sum_{h=0}^{k-1} \e^h Y^{(h)}$,
$\bar X= \sum_{h=1}^{k-1} \e^h X^{(h)}$ to get an identity in $\e$;
differentiating such identity  with respect to $\e$ 
$k$ times and setting $\e=0$ (\ie evaluating $[\cdot]_k$ of the identity)
and using the fact that $Y^{(h)},X^{(h)}$ solve \equ{2.5}, 
for $h\le k-1$ we easily obtain \equ{clm}.
\qed

%********************************************

%
\section{Tree expansion of formal series}
%
\label{sec:tree}
\setcounter{equation}{0}
%
A very explicit representation of the formal solutions described
in Proposition~\ref{pro:ef} can be obtained by mean of
{\em trees}, as explained below. For a different representation
see \cite{V}.

\giu
{\em From now on we restrict our attention on Hamiltonian \equ{h}
of the simple form}
\begin{equation}
H(y,x;\e)= \frac{1}{2}\  y\cdot y\ - \ \e f(x)\ .
\label{h1}
\end{equation}
Such a choice (besides the harmless change of sign in front of the 
perturbation $f$) has the advantage of simplifying sensibly
the notations without introducing any essential modification:
in other words, all the arguments and proofs presented below 
could be extended, at the expense of a heavier formalism,
to cover the general case \equ{h} (with $\det h''\neq 0$).

Thus, in the present case \equ{h1}, Hamilton equations and the equations
characterizing quasi--periodic solutions with frequencies $\o$
are given respectively (see \equ{2.1}, \equ{2.3}) by
\beq
\ddot x=\e f_x(x)\ ,\qquad D^2 X=\e f_x(\th+X)
\label{he}
\eeq
The formal power series $X\sim \sum_{k\ge 1} X^{(k)} \e^k$,
with $\int_\tN X^{(k)}=0$, whose existence and uniqueness
(for $f\in\ci(\tN)$) is guaranteed by Proposition \ref{pro:ef},
satisfies
\beq
D^2 X \sim \e f_x(\th+X)\qquad {\rm or}\qquad
D^2 \Xk = \left[ f_x (\th+\sum_{h=1}^{k-1}\Xh \e^h)\right]_{k-1}
\label{qpe}
\eeq
The rest of this section is devoted to a {\em tree representation}
of the formal solution $X$ of \equ{qpe} (with $\int_\tN \Xk=0$).

We recall that a tree $T$ is a connected acyclic graph
(see Appendix~\ref{app:tree} for the fundamentals used here
or see any introductory book on graph theory such as
\cite{Ha1} or \cite{Bo}).
We denote respectively by $V=V(T)$ and $E=E(T)$
the set of {\em vertices} and {\em edges} (or
{\em points} and {\em lines}) of the tree $T$. A {\em rooted
tree} is a tree with one distinguished vertex called {\em root};
we shall usually denote $r$ such a point and $T_r$ the rooted
tree obtained by selecting, as root, the vertex $r$ of the tree $T$. 
It will also be useful to regard a rooted
tree $\Tr$ as a tree with one extra point $\eta\noin V(\Tr)$,
called the {\em earth}, and one more edge
$\eta r\in E(\Tr)$ connecting the earth $\eta$ to the root $r$.
It is natural to define on  rooted trees a {\em partial ordering}:
Given $T_r$ and $u,v\in V$ we say that
\beq
u\ge v \qquad {\rm or}\qquad  u \ \getr v
\label{ord}
\eeq
if the path with endpoints $r$ and $v$ passes through $u$;
$u>v$ means obviously $u\ge v$ and $u\neq v$. In particular $r\ge v$
for any $v\in V$.

{\em We fix once and for all a Diophantine vector $\o\in\rN$ satisfying}
\equ{dioph} and denote the inner product between $n\in\zN$ and $\o$ by
\beq
\lg n \rg \= \o\cdot n \=\sum_{i=1}^N \o_i n_i
\label{n}
\eeq
Given a rooted tree $\Tr$ and a function $\a:v\in V\to \a_v\in\zN$
we denote by $\d_v(T_r;\a)$ (or $\d_v(T_r)$ or $\d_v$ when there is no 
ambiguity) the number
\beq
\d_v(T_r;\a)\=\lg \sum_{{v'\in V}\atop{v'\le v}} \a_{v'}\rg
\label{del}
\eeq
Given a rooted tree $\Tr$ and an integer--valued function $\a:V\to\zN$
we say that $\a$ is {\em $\Tr$--admissible} if, for all vertices of $\Tr$
one has
\beq
\a_v\neq 0\ ;\qquad \sum_{v'\le v} \a_{v'} \neq 0
\label{adm}
\eeq
We shall denote by $\cA(\Tr)$ the set of all $\Tr$--admissible functions 
over $\Tr$. 

Finally we let $\cT^k$denote the set of {\em rooted, labeled trees}
with $k$ vertices (see Appendix~\ref{app:tree} for more informations);
and, for any integer--valued function $\a$ and any subset $S\subset V$ of 
vertices of a tree $T$, we denote
\beq
\a(S) \= \sum_{v\in S} \a_v
\label{S}
\eeq
%
\begin{proposition}
\label{pro:exptree}
The $j^{\rm th}$ component of the $n$--Fourier coefficients of $\Xk$ is 
given by
\beqa
\Xk_{jn} & = &\frac{1}{k!} 
\sum_{\Tr\in\cT^k} F_{jn}(\Tr)\ ,\qquad{\rm with:}\nonumber\\
F_{jn}(\Tr)& \equiv & (-i)
\sum_{{\a\in\cA(\Tr)}\atop
{\a(\Tr)=n,\a_\eta\equiv e_j}} \prod_{v\in V} f_{\a_v}\ 
\prod_{vv'\in E} \a_v\cdot\a_{v'} \ \prod_{v\in V} \d_v^{-2}
\label{exptree}
\eeqa
where $e_j$ is the unit vector with all zeroes 
except in the $j^{\rm th}$
entry.
\end{proposition}
%
Note that in the above formula $E=E(T_r)$ {\em includes} the edge
$\eta r$ and for this reason the function $\a$ has been extended
on $\eta$ (which is outside $V=V(T_r)$).
%

\rem{rem:exptree}
The above function $F^{(k)}_{jn}$ is obviously a function
of rooted trees rather than labeled rooted trees and the introduction
of the labels has the only task of simplifying the combinatorial
factors entering in the formula. In terms of rooted trees, 
\equ{exptree} can be rewritten as follows. Let $\tT_r\=[\Tr]$
denote the rooted tree obtained by removing the labels from $\Tr$
(clearly $\tT_r$ can be seen as the equivalence class generated by $\Tr$),
and let $\ell(\tT_r)$ denote the number of ways of putting $k$ labels
on $\tT_r$ (\ie $\ell(\tT_r)=\#\{T'_r\in\cT^k:$ $T'_r\in\tT_r\}$).
For example, if $\tT_r$ is the path of order $k$ rooted
in one of its endpoints, then $\ell(\tT_k)=k!$. The ``$\tT_r$--admissible"
class of $\zN$--valued functions is defined in exactly the same way (see
\equ{adm} replacing $T_r$ by $\tT_r$ (as the labeling did not enter
in the definition of $\cA(\Tr)$). 
Finally denote by $\widetilde\cT^k$ the class of all rooted trees of order
$k$. With this notations we see that
\beqa
\Xk_{jn} & = &
\sum_{\tT_r\in\widetilde\cT^k} \frac{\ell(\tT_r)}{k!}\ 
\f_{jn}(\tT_r)\ ,\qquad {\rm with:}\nonumber\\
\f_{jn}(\tT_r)& \equiv & (-i)
\sum_{{\a\in\cA(\tT_r)}\atop
{\a(\tT_r)=n,\a_\eta\equiv e_j}} \prod_{v\in V} f_{\a_v}\ 
\prod_{vv'\in E} \a_v\cdot\a_{v'} \ \prod_{v\in V} \d_v^{-2}
\label{exptreebis}
\eeqa
%
\erem
%
Below it will be useful to exchange the sums 
(over trees and over integers $\a$'s) in \equ{exptree},
in which case we obtain the following formula:
\beq
\Xk_{jn}=\frac{1}{k!} \sum_{ {n_1,...,n_k}\atop{ n_i\in\zN\backslash \{0\},
\sum n_i=n} } \sum_{\Tr\in\cT^k}\bar F_{j\{n_i\}} (\Tr)
\label{exptr1}
\eeq
where if $v_1,...,v_k$ are the labels of $\cT^k$ and if we set
$\a_{v_i}\=n_i$ for any choice of $\{n_i\}$, the function $\bar F$
is defined by
\beq
\bar F_{j\{n_i\}} (\Tr)\= 0\ ,\qquad {\rm if}\quad \exists\ v:\ 
\sum_{v'\le v} \a_{v'} =0
\label{exptr2}
\eeq
and otherwise by
\beq
\bar F_{j\{n_i\}} (\Tr)\=
\prod_{v\in V} f_{\a_v}\ 
\prod_{vv'\in E} \a_v\cdot\a_{v'} \ \prod_{v\in V} \d_v^{-2}
\label{exptr3}
\eeq

\giu
Expansions like \equ{exptree} are quite general; another tree
expansion, which we shall need later,
for a series satisfying an equation simpler than
(but related to)
\equ{qpe}  is described in the following
%
\begin{proposition}
\label{pro:exptree2}
Let $n\in\zN\to \phi_n\in\complex$ decay faster than any 
power of $|n|$ 
(~\ie $\forall$ $s>0$, $\sup_n |n|^s |\phi_n|<\infty$)
and let $g=g(\e)\sim\sum_{k\ge 1}g_k\e^k$ 
be the unique formal solution of the equation:
\beq
g\sim \e \sum_{n\in\zN} \phi_n |n| \exp(|n| g)\ .
\label{gphi}
\eeq
Then
\beqa
g_k & = &\frac{1}{k!} \sum_{T_r\in\cT^k} 
\sum_{{\a:T_r\to\zN}\atop {\a_\eta\equiv 1}} 
\prod_{v\in V} \phi_{\a_v}\ \prod_{vv'\in E} |\a_v|\ |\a_{v'}|
\nonumber\\
& = & \frac{1}{k!} \sum_{T_r\in\cT^k} 
\sum_{\a:T_r\to\zN} 
\prod_{v\in V} \phi_{\a_v}\ \prod_{v\in V} |\a_v|^{\deg v}
\label{exptree2}
\eeqa
where $\deg v$ denotes the degree of $v$ (\ie the number of
edges incident with $v$).
\end{proposition}
%
Actually, if the $\phi_n$'s decay exponentially (\ie
$|\phi_n|\le M \exp(-\xi |n|)$ for some $M,\xi>0$
and all $n\in\zN$), it follows immediately from the (analytic)
Implicit Function Theorem  (applied to the analytic function
of two complex variables $(x,\e)\in\complex^2\to G(x,\e)$
$\=$ $x-\e\sum \phi_n |n| \exp(|n|x)$) that $g$ converges
absolutely near $\e=0$ (see also Subsection~\ref{subsec:1} below).

\giu
The proofs  (by induction on $k$) of 
Proposition~\ref{pro:exptree} and Proposition~\ref{pro:exptree2} 
are of pure combinatorial character. 
Here we outline the main steps and refer to
Appendix~\ref{app:combina} for complete details.
The proofs of the two Propositions are very similar
but, obviously, the proof of Proposition~\ref{pro:exptree2}
is simpler and we discuss it first.

The starting point is so to get a recursive formula for the
coefficients $g_k$ defined implicitly by \equ{gphi}: 
Expanding the right
hand side of \equ{gphi} in Taylor series and comparing
equal powers of $\e$ one immediately obtain
\beqa
g_1 & = & \sum_{n\in\zN} \phi_n |n| \nonumber\\
g_k & = & \sum_{j=2}^k \sum_{n\in\zN} \phi_n\ 
\frac{|n|^j}{(j-1)!} \sum_{ {h_1+\cdots h_{j-1} =k-1}
\atop{h_i\ge 1}} \prod_{i=1}^{j-1} g_{h_i}\ 
\quad (k\ge 2)
\label{3.1}
\eeqa
Now, there is a natural way of
linking (labeled rooted) trees
of order $k$ with all possible trees of order $h_1,...,h_{j-1}$
with $h_1+\cdots+ h_{j-1}=k-1$: This link is based on the following
construction. Let $\tcT^k$ denote the rooted trees of order $k$
(non labeled) and let $\tcT^k_0$ denote the trees of order $k$
(no labels, no root).
\dfn{def:3.1}
Let $s\ge 1$, let $\tT_i\in\tcT^{h_i}$ where $i=1,...,s$
and $h_i\ge 1$ with $h\=\sum_{i=1}^s h_i$.
Let $\tT_i^0$ $\in$ $\tcT^{h_i}_0$  be the (unrooted) tree obtained from
$\tT_i$ by not distinguishing the root.
We define the rooted tree $\tT_1 * \cdots *
\tT_s$ $\in \tcT^{h+1}$ by setting\footnote{
For the (standard) notation see Appendix~\ref{app:tree}}
\beq
\tT_1 * \cdots *\tT_s\= \Big( \tT_1^0\cup \cdots
\cup \tT_s^0 \cup \{r\} + \sum_{i=1}^s rr_i \Big)_r 
\label{3.2}
\eeq
where $r$ is the root of $\tT_1*\cdots *\tT_s$ ($r$ is an extra vertex
\ie $r\noin \tT_i$) and the $r_i$'s are the roots of $\tT_i$
\ie $(\tT_i^0)_{r_i}=\tT_i$.
\edfn
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(385,120)
\thicklines
\put(10,20){\begin{picture}(70,100)
\put(30,25){\circle*{3}}
\put(30,25){\circle{8}}
\put(30,25){\line(-1,1){18}}
\put(12,43){\circle*{3}}
\put(30,25){\line(1,1){36}}
\multiput(48,43)(18,18){2}{\circle*{3}}
\put(35,20){$r_1$}
\put(25,0){$\tT_1$}
\end{picture}}
\put(80,20){\begin{picture}(70,100)
\put(30,25){\circle*{3}}
\put(30,25){\circle{8}}
\put(30,25){\line(-1,1){18}}
\put(12,43){\circle*{3}}
\put(30,25){\line(1,1){18}}
\put(48,43){\circle*{3}}
\put(35,20){$r_2$}
\put(25,0){$\tT_2$}
\end{picture}}
\put(150,20){\begin{picture}(70,100)
\put(30,25){\circle*{3}}
\put(30,25){\circle{8}}
\put(30,25){\line(0,1){15}}
\put(30,40){\line(-1,2){20}}
\multiput(30,40)(-10,20){3}{\circle*{3}}
\put(30,40){\line(1,2){20}}
\multiput(40,60)(10,20){2}{\circle*{3}}
\put(35,20){$r_3$}
\put(25,0){$\tT_3$}
\end{picture}}
\put(240,20){\begin{picture}(145,100)
\put(60,25){\circle*{3}}
\put(60,25){\circle{8}}
\put(60,25){\line(-4,3){20}}
\put(40,40){\line(0,1){36}}
\multiput(40,40)(0,18){3}{\circle*{3}}
\put(40,40){\line(-1,0){18}}
\put(22,40){\circle*{3}}
\put(60,25){\line(0,1){23}}
\put(60,48){\circle*{3}}
\put(60,48){\line(1,2){10}}
\put(70,68){\circle*{3}}
\put(60,48){\line(-1,2){10}}
\put(50,68){\circle*{3}}
\put(60,25){\line(2,1){40}}
\multiput(80,35)(20,10){2}{\circle*{3}}
\put(100,45){\line(1,0){36}}
\multiput(118,45)(18,0){2}{\circle*{3}}
\put(100,45){\line(0,1){36}}
\multiput(100,63)(0,18){2}{\circle*{3}}
\thinlines
\put(-15,50){\vector(1,0){20}}
\put(55,14){$r$}
\put(62,40){$r_2$}
\put(82,25){$r_3$}
\put(35,30){$r_1$}
\put(35,0){$\tT_1 * \tT_2 * \tT_3$}
\end{picture}}
\parbox{12cm}{\caption{\label{fig:3.1} The $*$ operation}}
\end{picture}
\end{center}
\end{figure}

%
\giu
And here it is the combinatorics 
(recall that the number of labeled rooted trees of order $h$
is $h^{h-1}$ (see Appendix~\ref{app:tree}):
\lem{lem:3.1}
For $k\ge j\ge 2$, 
denote by $t_{kj}$ the number of labeled rooted trees of order $k$
with root of degree $j$. Then
\beqano
& {\rm (i)} &\quad  
t_{kj}= k\ {k-2\choose j-2} \ (k-1)^{k-j} \\
& {\rm (ii)} &\quad  
t_{kj}= \frac{k!}{(j-1)!} \sum_{ {h_1+\cdots h_{j-1} =k-1}
\atop{h_i\ge 1}} \prod_{i=1}^{j-1} \frac{h_i^{h_i-1}}{h_i!}\\
& {\rm (iii)} &\quad  
\frac{k^{k-1}}{k!} = \sum_{j=2}^k
\frac{1}{(j-1)!} \sum_{ {h_1+\cdots h_{j-1} =k-1}
\atop{h_i\ge 1}} \prod_{i=1}^{j-1} \frac{h_i^{h_i-1}}{h_i!}
\eeqano
\elem
The proof is given in Appendix~\ref{app:combina}. 
The main point of the above Lemma is (ii): (i)
is just a curiosity and will not be used
and (iii) is simply obtained by summing (ii) over
$j$.
An immediate corollary of this Lemma (better: ``of the proof of this
Lemma") is the following Corollary. 
%
\cor{cor:3.1}
Let $G:\tcT^k\to\complex$. Then
\beq
\frac{1}{k!} \sum_{T\in\cT^k} G(\tT)=
\sum_{j=2}^k 
\frac{1}{(j-1)!} \sum_{ {h_1+\cdots h_{j-1} =k-1}
\atop{h_i\ge 1}} \prod_{i=1}^{j-1} \frac{1}{h_i!}\ \ 
\sum_{ T_1\in \cT^{h_1},...,T_{j-1}\in \cT^{h_{j-1}} }\ 
G(\tT_1 *\cdots *\tT_{j-1})
\label{3.3}
\eeq
\ecor
>From \equ{3.3}, Proposition~\ref{pro:exptree2} will follow at once.
To get also Proposition~\ref{pro:exptree} from Corollary~\ref{cor:3.1},
one needs only to rewrite \equ{exptree} properly. To do this, let
for any $m,n\in\zNn$ and $k\ge 1$
\beq
\xi^m\=i \ m\cdot X\ ,\quad
\xi^{(m,k)}\=i \ m\cdot \Xk\ ,\quad
\xi_n^{(m,k)}\=i \ m\cdot \Xk_n
\label{3.4}
\eeq
Then from \equ{qpe} and Taylor expansion (in $\e$) we obtain
easily
\beqa
\xi_n^{(m,1)} & = & - \gl{n}^{-2} \ m\cdot n\ f_n \nonumber\\
\xi_n^{(m,k)}  & = & - \gl{n}^{-2} \sum_{j=2}^k \sum_{n\in\zNn} 
\sum_{ {n_1+\cdots +n_j=n}\atop{n_i\in\zNn}} \ m\cdot n_j \ f_{n_j}\times
\nonumber\\
&&\qquad  \times
\frac{1}{(j-1)!} \sum_{ {h_1+\cdots h_{j-1} =k-1}
\atop{h_i\ge 1}} \prod_{i=1}^{j-1} \xi_{n_i}^{(n_j,h_i)}  
\quad (k\ge 2)
\label{3.5}
\eeqa
The similarity of \equ{3.5} and \equ{3.1} is 
transparent\footnote{$|n|\phi_n$ corresponds to $\gl{n}^{-2}
m\cdot n_j f_{n_j}$, while $|n|g_{h_i}$ corresponds to 
$\xi_{n_i}^{(n_j,h_i)}$.}
and it is enough to change the extensions of the $\a$ functions
on the earth $\eta$ to generalizes \equ{exptree} to
\beqa
\xi^{(m,k)}_{n} & = &\frac{1}{k!} 
\sum_{\Tr\in\cT^k} F_{mn}\ ,\qquad{\rm with:}\nonumber\\
F_{mn}(\Tr)& \equiv & 
\sum_{{\a\in\cA(\Tr)}\atop
{\a(\Tr)=n,\a_\eta\equiv m}} \prod_{v\in V} f_{\a_v}\ 
\prod_{vv'\in E} \a_v\cdot\a_{v'} \ \prod_{v\in V} \d_v^{-2}
\label{exptreeg}
\eeqa
For full details see Appendix~\ref{app:combina}.

%********************************************

%
\section{Divergences}
%
\label{sec:diverge}
\setcounter{equation}{0}
%
{\em From now on $f$ in \equ{qpe} will be assumed real--analytic}.
In this section we illustrate the well known mechanism
of divergences of series with coefficients of type \equ{exptree},
(for an $f$ in \equ{qpe} real analytic),
{\em if signs are disregarded} \ie
when absolute values are introduced within the sums. This fact,
based on the repetition of particularly small divisors $\d_v$
(``resonances"),
shows the need for detecting the compensations among all the terms
whose size in absolute value grows faster than exponentially in $k$
and whose actual occurrence will readily be seen.

\giu
More explicitely, let, for $1\le \baj\le N$:
\beq
A^{(k)}_{\baj n} = \frac{1}{k!} 
\sum_{\Tr\in\cT^k} 
\sum_{{\a\in\cA(\Tr)}\atop
{\a(\Tr)=n,\a_\eta\equiv e_\baj}} 
\mid\prod_{v\in V} f_{\a_v}\ 
\prod_{vv'\in E} \a_v\cdot\a_{v'}\mid 
\ \prod_{v\in V} \d_v^{-2}
\label{abstree}
\eeq
we want to show that
\beq
\sup_{\baj,k,n}
A^{(k)}_{\baj n}\  e^{-\s|n|}\ \e_0^k=+\infty
\ ,\qquad \forall\ \ \e_0,\ \s>0
\label{diverge}
\eeq
where in the supremum $1\le \baj\le N$, $k\ge 1$ and  $n\in\zN$.
We shall prove \equ{diverge} in the case
\beqa
& & N  =2\ ,\qquad f(x_1,x_2)\=\cos x_1 \ + \cos(x_2-x_1)\ , \nonumber\\
& & \o_2  >\o_1>0\ ,\qquad {\o_1}/{\o_2}\ \quad{\rm irrational}
\label{model}
\eeqa
since it will be clear that the same proof can easily be adapted
to the general analytic case {\em as long as $f$ has two Fourier
coefficients with linearly independent (in $\zN$) indeces.}

\giu
{\bf Proof of \equ{diverge} in case \equ{model}}
%
>From an elementary number theoretical theorem by Dirichlet
(see \cite{Sc})
it follows that there exist
$p_j,q_j\ge 1$, with $q_j\nearrow \infty$ such that
\beq
\mid \frac{\o_1}{\o_2}  \ q_j \ - \ p_j \mid < \frac{1}{q_j}
\label{Dirichlet}
\eeq
and we can assume without loss of generality that for all $j\ge 1$
\beq
q_j > \frac{\o_2}{\o_2-\o_1}
\label{condqj}
\eeq
Observing the the left hand side of \equ{Dirichlet} is bigger
or equal than $p_j-q_j(\o_1/\o_2)$ we see immediately that 
\equ{condqj} implies that
\beq
p_j<q_j
\label{pjqj}
\eeq
We shall now select a particular (unlabeled) rooted tree
and associate to its vertices a particular choice of Fourier indices
(\ie a particular choice of $\a$). Let $P$ be the path of order
$k$, $u_k u_{k-1}...u_1$ rooted at $u_k$: $u_k=r$ and 
$u_k>u_{k-1}>...>u_1$. Let $s_j\=q_j-p_j$ and, for any $h\ge 0$
let $k\=q_j+2h$:
\beq
q_j=p_j+s_j\ ,\qquad 1\le s_j,p_j< q_j\ ,\qquad k=q_j+2h
\label{defsh}
\eeq
Let $\a_{u_i}\=n_i\in\integer^2$ be defined as follows:
\beq
n_i\=
\cases{ (1,0) & if \ $1\le i\le s_j$\cr
        (1,-1) & if \  $s_j<i\le q_j$\cr
        (1,0) & if \ $i=q_j+1,q_j+3,...,q_j+(2h-1)$\cr
        (-1,0) & if \  $i=q_j+2,q_j+4,...,q_j+2h$\cr}
\label{ni}
\eeq
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(400,50)
\thicklines
\put(390,30){\circle{8}}
\put(10,30){\line(1,0){380}}
\multiput(10,30)(20,0){20}{\circle*{3}}
\put(5,20){$u_1$}
\put(85,20){$u_{s_j}$}
\put(185,20){$u_{q_j}$}
\put(385,18){$u_k$}
\put(0,40){{\scriptsize (1,0)}}
\put(80,40){{\scriptsize (1,0)}}
\put(100,40){{\scriptsize (1,-1)}}
\put(180,40){{\scriptsize (1,-1)}}
\put(200,40){{\scriptsize (1,0)}}
\put(220,40){{\scriptsize (-1,0)}}
\put(240,40){{\scriptsize (1,0)}}
\put(260,40){{\scriptsize (-1,0)}}
\put(360,40){{\scriptsize (1,0)}}
\put(380,40){{\scriptsize (-1,0)}}
\multiput(25,42)(5,0){11}{\circle*{1}}
\multiput(125,42)(5,0){11}{\circle*{1}}
\multiput(285,42)(5,0){15}{\circle*{1}}
\parbox{12cm}{\caption{\label{fig:d1} Divergent contributions}}
\end{picture}
\end{center}
\end{figure}

\nin
%
To this choice of Fourier indeces $\a$, for which
\beq
n\=\sum_{i=1}^k n_i = (q_j, -p_j)
\label{4.0}
\eeq
correspond the divisors
\beq 
|\d_{u_i}|=
\cases{ \o_1 \ i & if \ $1\le i\le s_j$\cr
        |\o_1 i - \o_2(i-s_j)|& if \ $s_j<i\le q_j$\cr
        |\o_1 q_j- \o_2 p_j + \o_1| & if \ 
$i=q_j+1,q_j+3,...,q_j+(2h-1)$\cr
        |\o_1 q_j- \o_2 p_j|& if \ 
$i=q_j+2,q_j+4,...,q_j+2h$\cr}
\label{di}
\eeq
>From \equ{Dirichlet}, \equ{condqj} and \equ{di} it follows that
\beqa
& & |\o_1 q_j- \o_2 p_j + \o_1|<\o_2\nonumber \\
& & |\d_{u_i}| < 2 \o_2\ i\ ,\qquad {\rm for} \quad 1\le i\le q_j
\label{4.1}
\eeqa
which, together with \equ{Dirichlet} yields
\beq
\prod_{i=1}^k \d_{u_i}^{-1} > 
\o_2^{-k}\ 2^{-q_j}\ \frac{q_j^h}{q_j!}
\label{4.2}
\eeq
Furthermore, since for \equ{model} it is 
\beq
|f_{\pm(1,0)}|=|f_{\pm(1,-1)}| =\frac{1}{2}
\label{4.3}
\eeq
we have also
\beq
\prod_{i=1}^k |f_{n_i}| = 2^{-k}\ ,\qquad
\prod_{E(P)} |\a_v\cdot\a_{v'}|\ge 1
\label{4.4}
\eeq
having set $\baj=1$ \ie $\a_\eta\=(1,0)$.
We now choose
\beq
h=3q_j\ ,\qquad {\rm so\quad that}\qquad k\=k_j=7q_j
\label{4.5}
\eeq
Then, if in the sum \equ{abstree}  (which is finite in the case
of \equ{model}), we keep only the terms corresponding to the
unlabeled rooted tree $P$ with the above choice of Fourier
indices, recalling from Remark~\ref{rem:exptree} 
that the number of labeled rooted trees corresponding to $P$
are exactly $k!$, we obtain 
(recall that $\baj=1$ and that  $n=(q_j,-p_j)$)
\beq
A^{(k_j)}_{1 n}\ >
2^{-k_j} \ (2\o_2)^{-2k_j}\ (k_j!)^{4/7}
\label{4.6}
\eeq
from which \equ{diverge}
follows at once. Notice that by increasing $h$, the exponent of $k_j!$ in
\equ{4.6} becomes arbitrarly close to 1.
\qed

%********************************************
\section{Resonances}
\label{sec:resona}
\setcounter{equation}{0}
%
Repetitions of small divisors correspond to {\em resonant
subtrees} \ie to subtrees $S$ of a given (labeled rooted)
tree $T$ for which $\a(S)\=\sum_{v\in S}\a_v=0$:
In the example of Section~\ref{sec:diverge}
resonant subtrees are the subtrees with endpoints 
$u_{q_j+s}$ and $u_{q_j+s+1}$ for $1\le s\le k-1$, or the subtrees
with endpoints $u_{q_j+s}$ and $u_{q_j+s+3}$ \etc.
Throughout the rest of the paper (unless otherwise stated),
given $T\in\cT^k$ (we shall often omit the explicit indication
of the root $r$ appearing elsewhere as index of $T$ when this 
does not lead to confusion),
the function $\a:V\=\{v_1,...,v_k\}\to\zN$, 
$\{\a_{v_i}\}$ $\=$ $\{n_i\}$, is
{\em admissible} in the usual sense that $n_i\neq 0$ and
$\sum_{v'\le v} \a_v\neq 0$ for all $v\in V$ (in which
case $\d_v\neq 0$ by the rational independence of $\o$).
In this section we develop the tools needed to
{\em make a partition} of $\cT^k$,
for a given choice of $\{n_i\}$ (see \equ{exptr1}$\div$
\equ{exptr3}), into {\em ``complete families"}. In the next section
we shall see that the main property of complete families is
that  (possibly) huge terms (coming from repetition of small divisors)
{\em compensate among themselves}
within the same class of the partition. This fact will
allow us to bound the contribution
to \equ{exptr1}, coming from the sum over trees belonging
to the same class of the partition, by a constant to the 
$k^{\rm th}$ power.

\giu
The rest of this section consists basically in a sequel
of definitions and checks of elementary properties of
trees with a given admissible $\a_{v_i}\=n_i$,
$v_1,...,v_k$ being the labels of $\cT^k$
(see Appendix~\ref{app:tree} for the fundamentals from graph theory
used here).
Let us begin (with a bit of patience).

\dfntwo{Degree of a subtree}{dfn:1}
Given a (possibly rooted) tree $T$ and
$S\subset T$ (\ie $S$ is a subtree of $T$ \ie $S$ is
a connected subgraph of $T$) 
we call {\em degree of $S$},
$\deg S$,
the number of edges connecting $S$ with $T\backslash S$
(if $T$ is rooted and $r\in S$ the edge $\eta r$ has to
be counted). 
\edfn

\dfntwo{Resonances}{dfn:2}
Given a rooted tree $T$ and an admissible function $\a$ on it,
we say that the subtree $R\subset T$ is {\em resonant} if:
(i) $\deg R=2$; (ii) $R$ is null \ie $\a(R)=0$; 
(iii) $R$ cannot be disconnected by removal of one edge 
into two null subtrees.
A resonant subtree will also be called a {\em resonance}.
\edfn

\dfntwo{Resonant couples}{dfn:4}
Given a rooted tree $T$, $\l>0$ we say that a couple of points
$(u,w)\in V\times V$ is {\em $\l$--resonant} if:
(i) $u>w$; (ii) $\d_u=\d_w$; (iii) $u$ and $w$ are not adjacent and
$|\d_w|\le \l |\d_v|$ for all $v$ between $u$ and $w$.
\edfn
%
Such a notion is given also in \cite{E} where the couple
$(u,w)$ is called a critical resonance; we reserve such a name for a 
different object (see Definition \ref{dfn:6} below).

\dfntwo{$\l$--Resonances}{dfn:5}
Given a rooted tree $T$, $\l>0$ and a resonance $R\subset T$ 
let
\beq
n\= \sum_{v<R} \a_v\ ,\qquad
\D(R)\= \min_{ {R'\subset R}\atop {\a(R')\neq 0} } |\lg \a(R')\rg|
\label{5.1}
\eeq
where $v<R$ means $v<u$ for all $u\in R$.
We say that $R$ is a  {\em $\l$--resonance} (or a $\l$--resonant subtree) if
\beq
|\lg n\rg|\le \l \D(R)\ .
\label{5.2}
\eeq
\edfn

\rem{rem:5.1}
To two points $u>w$ such that $\d_u=\d_w$ but $\d_v\neq \d_u$ for
any $v$ between $u$ and $w$ (if there are any) it is always possible
to associate a resonant subtree $R\=R(u,w)$:
\beq
R(u,w)\= \{ v\in V:\ v\ge u\}\backslash \{v\in V:\ v\ge w\}
\label{5.3}
\eeq
Notice however that $(u,w)$ may be $\l$--resonant while the associated
resonance $R(u,w)$ is not $\l$--resonant as shown in the example in
Figure~\ref{fig:1}:
it is easy to see that one can choose $n_1,n_2,n_3$ so that
$n_1+n_2+n_3=0$ (implying $\d_u=\d_w$) and 
$|\lg n\rg|\le \l|\lg n_2+n_3+n\rg |$ (implying $(u,w)$  $\l$--resonant)
but $|\lg n\rg |>\l |\lg n_3\rg|$ (implying $R(u,w)$ not $\l$--resonant).
\erem
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(350,120)
\put(100,20){\begin{picture}(150,100)
\thicklines
\put(11,40){\circle*{3}}
\put(11,40){\circle{8}}
\multiput(11,40)(3,0){9}{\circle*{1}}
\put(35,40){\line(1,0){85}}
\multiput(50,40)(35,0){3}{\circle*{3}}
\put(85,40){\line(1,3){10}}
\put(95,70){\circle*{3}}
\thinlines
\put(72.5,55){\oval(70,62)}
\put(44,44){$n_1$}
\put(73,44){$n_2$}
\put(90,75){$n_3$}
\put(116,44){$n$}
\put(46,32){$u$}
\put(116,32){$w$}
\put(70,13){$R$}
\end{picture}}
\parbox{12cm}{\caption{\label{fig:1} $R=R(u,w)$}}
\end{picture}
\end{center}
\end{figure}
%

\protwo{Non overlapping of resonant couples}{pro:nonover1}
Let $(u_i,w_i)$ \allowbreak
for 
$i=1,2$ be couples of $\l_i$--resonant points.
If $u_1>u_2>w_1>w_2$ then either $\l_1\ge 1$ or $\l_2\ge 1$.
\epro

\PROOF By contradiction: Assume both $\l_1$ and $\l_2$ are less than 
one.Then:
\beq
|\d_{u_2}|=|\d_{w_2}| \le \l_2 |\d_{w_1}|<|\d_{w_1}|\ ,\qquad
|\d_{w_1}| \le \l_1 |\d_{u_2}| <|\d_{u_2}|
\eeq
which is absurd. \qed

\protwo{Non overlapping of resonances}{pro:nonover2}
Let $R_i$ for $i=1,2$ be $\l_i$--re\-so\-na\-n\-ces 
which are not one subtree of the 
other and with nonempty intersection (\ie with at least one common
vertex). Then either $\l_1\ge 1/2$ or
$\l_2\ge 1/2$.
\epro
\PROOF Two subtrees of degree 2 which are not one a subtree of the other 
can intersect in three ways, see Figure~\ref{fig:2}.
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(385,145)
\put(0,45){\begin{picture}(180,100)
\thicklines
\put(10,50){\line(1,0){120}}
\multiput(10,50)(30,0){5}{\circle*{6}}
\put(130,50){\line(3,1){15}}
\multiput(145,55)(3,1){6}{\circle*{1}}
\put(160,60){$\odot$}
\thinlines
\put(55,50){\oval(50,40)}
\put(85,50){\oval(50,40)}
\put(5,57){$n_1$}
\put(35,57){$n_2$}
\put(65,57){$n_3$}
\put(95,57){$n_4$}
\put(55,15){$R_1$}
\put(85,15){$R_2$}
\put(80,-15){(a)}
\end{picture}}
\put(190,45){\begin{picture}(95,100)
\thicklines
\put(20,65){\line(2,1){40}}
\put(20,65){\circle*{6}}
\put(15,72){$n_1$}
\put(40,75){\circle*{6}}
\put(35,82){$n_2$}
\put(60,85){\circle*{6}}
\put(55,92){$n_3$}
\put(40,75){\line(2,-1){20}}
\put(60,65){\circle*{6}}
\put(55,72){$n_4$}
\put(60,65){\line(1,-1){15}}
\put(75,50){\circle*{6}}
\put(75,50){\line(0,-1){10}}
\multiput(75,40)(0,-3){5}{\circle*{1}}
\put(71,20){$\odot$}
\thinlines
\put(30,72.5){\oval(45,45)}
\put(53,78){\oval(50,50)}
\put(25,35){$R_1$}
\put(50,40){$R_2$}
\put(40,-15){(b)}
\end{picture}}
\put(295,45){\begin{picture}(90,100)
\thicklines
\put(15,75){\line(1,0){60}}
\put(15,75){\circle*{6}}
\put(10,82){$n_1$}
\put(45,75){\circle*{6}}
\put(40,82){$n_2$}
\put(75,75){\circle*{6}}
\put(70,82){$n_3$}
\put(45,75){\line(0,-1){40}}
\put(45,45){\circle*{6}}
\multiput(45,35)(0,-3){6}{\circle*{1}}
\put(41,12){$\odot$}
\thinlines
\put(30,75){\oval(52,40)}
\put(60,75){\oval(52,40)}
\put(20,40){$R_1$}
\put(55,40){$R_2$}
\put(40,-15){(c)}
\end{picture}}
\parbox{12cm}{\caption{\label{fig:2} Intersections of resonances}}
\end{picture}
\end{center}
\end{figure}
%

\giu
In drawing pictures we are using the following

\giu
{\bf Notational Remark} {\em Thick points correspond in general to subtrees
(a subtree of degree $d$ collapse to a thick point of the same degree)
and the $n$ written above a thick point correspond to the sum of $\a_v$
when $v$ varies in the corresponding (collapsed) subtree. In the 
figures, null subtrees (indicated usually by $R$) are encircled
(while the root, as custumary, is distinguished by a small circle
around it.)}

\giu
Since $R_i$ are resonant subtrees $n_2+n_3=0$, $n_3+n_4=0$ in case (a)
while $n_1=-n_2$ in case (b) and (c). We proceed now by contradiction:
Assume $\l_i<1/2$.

\nin In case (a)
\beq
|\lg n_1\rg|\le \l_1 |\lg n_2 \rg|\ ,\qquad |\lg n_1+n_2\rg| \le\l_2|\lg 
n_3\rg|=\l_2|\lg n_2\rg|
\eeq
and
\beq
|\lg n_1+n_2\rg| \ge (1-\l_1)|\lg n_2\rg|\quad
\implies \quad |\lg n_2 \rg|\le \frac{\l_2}{1-\l_1} \ |\lg n_2\rg|
<|\lg n_2 \rg|
\eeq
which is absurd.

\giu
In case (b) and (c): $|\lg n_1\rg|\le \l_1 |\lg n_2\rg|=\l_1|\lg n_1
\rg|$
which is absurd because $\l_1<1$. \qed

\dfntwo{Critical Resonances}{dfn:6}
A resonance $R$ is called {\em critical} (or $\l$--critical)
if it is $\l$--resonant 
with $\l<1/2$ and if it is maximal \ie it is not properly contained
into another $\l$--resonant subtree. 

\nin
Obviously: (i) Critical resonances cannot intersect (by definition
and by Proposition \ref{pro:nonover2}). (ii) Critical resonances
may contain $\l'$--resonances with any $\l'$.
\edfn
%
Critical resonances may appear in sequels where each resonance
is a subtree of another resonance (creating ``hierarchies of 
subresonances"). In order to classify them, we introduce the following
concept.

\dfntwo{$\l$--Subresonances}{dfn:7}
Let $R'$ be a null subtree of degree two of a $\l$--critical 
resonance $R$ and let $u_1v_1$, $u_2v_2$, with $v_i\in R'$, be the two edges
connecting $R'$ with $R\bks R'$ (obviously $u_i\in R$ and $u_1\neq u_2$).
Define
\beq
m\=\sum_{ {v\in R_{v_1}} \atop {v\le u_1} } \a_v=
- \sum_{ {v\in R_{v_2}} \atop {v\le u_2} } \a_v
\label{defm}
\eeq
where $R_{v_i}$ is the rooted tree $R$ with root in $v_i$ and
the order $\le$ in each sum is relative to $R_{v_i}$ 
(we are using the standard convention that $v\in T$ means
$v\in V(T)$). The integer $m\in \zN\bks \{0\}$ is defined up to sign
(as the roles of the $v_i$ can be exchanged).
We then say that $R'$ is a  {\em $\l$--subresonance} if
\beq
\agl{m} \le \l \ \D(R')
\label{subres}
\eeq
\edfn
%
As in case of resonances we have a simple non overlapping 
criterion for subresonances:

\protwo{Non overlapping of subresonances}{pro:nonover3}
Let $R_i'$ for $i=1,2$ be $\l$--\-sub\-re\-so\-nan\-ces 
of a $\l$--critical 
resonance  $R$. Assume that $R_i$ are not one subtree of the other. 
Then $V(R_1)\cap V(R_2)=\emptyset$.
\epro
%
The proof is very similar to the proof of Proposition \ref{pro:nonover2}
and is left to the reader. 

\dfntwo{Hierarchies of critical subresonances}{dfn:8}
Let $R$ be a $\l$--cri\-ti\-cal resonance
(\ie $R$ is a maximal $\l$--resonance with $\l<1/2$). 
Let $R_1$ be a maximal 
$\l$--subresonance (if it exists) of $R$ (maximal means that $R_1$
is not properly contained in another $\l$--subresonance of $R$).
Note that, by Proposition \ref{pro:nonover3}, $R_1$ cannot overlap
with another $\l$--subresonance of $R$.
We can now {\em define subresonances of $R_1$ replacing, in
Definition~\ref{dfn:7}, $R$ with $R_1$}. We then let $R_2$ be a maximal
$\l$--subresonance (if it exists) of $R_1$. And so on, till $R_h$,
$h\ge 1$, does not contain any $\l$--subresonance. We consider also the case
in which $R$ does not contain any $\l$--subresonance setting in such a case 
$h=0$ and $R_0\=R$. The sequence
\beq
\cH\=\cH_\l(R)\=\{R_1,...,R_h\}\ ,\qquad R\supset R_1\supset
\cdots\supset R_h
\label{hierarchy}
\eeq
is called a {\em critical hierarchy of  $\l$--subresonances}
(or simply a hierarchy of subresonances) and the elements of
the hierarchy, $R_i$ with $1\le i\le h$, are called {\em critical
subresonances}. Thus by definition a critical subresonance of 
the rooted tree $T$ is an element of a hierarchy associated to some
critical resonance.
Obviously a critical resonance may contain more than one hierarchy
of subresonances (see Figure~\ref{fig:5} below).
\edfn
%
\rem{rem:5.2}
In general a critical $\l$--subresonance need not be a
$\l$--resonance as shown by the following example.
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(395,100)
\thicklines
\put(110,60){\circle{8}}
\put(110,60){\line(1,0){175}}
\multiput(110,60)(35,0){6}{\circle*{3}}
\thinlines
\put(197.5,60){\oval(70,35)}
\put(197.5,60){\oval(128,60)}
\put(136,67){$-3n$}
\put(170,67){$-9n$}
\put(210,67){$9n$}
\put(235,67){$3n$}
\put(280,67){$n$}
\put(230,35){$R_1$}
\put(260,25){$R$}
\parbox{14cm}{\caption{\label{fig:3} $R_1$ is not a 
$\frac{1}{3}$--resonance}}
\end{picture}
\end{center}
\end{figure}

\giu
%
Fix $\l=1/3$ and let $n\in\zN\bks\{0\}$. Then one checks immediatly
that $R$, in Figure~\ref{fig:3},  is a 
$\l$--critical resonance and that $\cH_\l(R)=\{R_1\}$.
However the critical subresonance {\em $R_1$ is not a $\l$--resonance} 
since  $\agl{4n}>\l\D(R_1)=3\agl{n}$.
\erem

\rem{rem:5.3}
If $R'$ is a $\l$--critical subresonance then $R'=R_i$ for some $1\le i\le h$
where $\{R_1,...,R_h\}$ is a $\l$--hierarchy associated to some
$\l$--critical resonance $R$. To each $R_j$ we can associated (up to sign)
an integer $m_j\in\zNn$ as in \equ{defm} (see Figure~\ref{fig:4}).
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(385,140)
\thicklines
\multiput(45,80)(-3,0){9}{\circle*{1}}
\put(21,80){\circle*{3}}
\put(21,80){\circle{8}}
\put(45,80){\line(1,0){270}}
\multiput(70,80)(35,0){8}{\circle*{6}}
\thinlines
\put(175,80){\oval(20,20)}
\put(175,80){\oval(100,40)}
\put(175,80){\oval(163,60)}
\put(175,80){\oval(245,100)}
\put(60,87){$-m_1$}
\put(95,87){$-m_2$}
\put(130,87){$-m_3$}
\put(205,87){$m_3$}
\put(235,87){$m_2$}
\put(275,87){$m_1$}
\put(310,87){$m_0$}
\put(183,65){$R_3$}
\put(220,55){$R_2$}
\put(255,45){$R_1$}
\put(295,25){$R$}
\parbox{12cm}{\caption{\label{fig:4} A hierarchy of resonances with $h=3$}}
\end{picture}
\end{center}
\end{figure}

%
\nin
Then $\agl{m_j}\le \l \D(R_j)$ for any $j=1,...,h$ and in particular
$\agl{m_j}\le \l \agl{m_{j+1}}$ so that
\beq
\agl{m_i}\le \l^{j-i}\agl{m_j}\ ,\qquad \forall\ \ 1\le i\le j \le h
\label{5.4}
\eeq
and
\beq
\sum_{i=1}^j \agl{m_i} < \frac{1}{1-\l}\ \agl{m_j} \le
\frac{\l}{1-\l} \D(R_j)
\label{5.5}
\eeq
Also, if $\s_h$ is plus or minus one and $\s_i=0$ or $\pm 1$
($i=1,...h-1$) then
\beq
\agl{\sum_{i=1}^h \s_i m_i} \ge \frac{1-2\l}{1-\l} \agl{m_h}
\label{5.6}
\eeq
Furthermore, if we let $m_0\=\sum_{v'< R} \a_{v'}$ (since
$\agl{m_0}\le \l\agl{m_1}$ we get as above:
\beq
\sum_{i=0}^h \agl{m_i}< \frac{1}{1-\l} \agl{m_h} \le \frac{\l}{1-\l}
\D(R_h)
\label{5.7}
\eeq
\erem

\dfntwo{The set of critical (sub)resonance of $T$}{dfn:9}
We shall often use
the \allowbreak 
word\- ``(sub)resonance" to indicate either a resonance
or a subresonance.
Given a rooted tree $T$, an admissible $\a$ and a $\l<1/2$ we let
\beq
\cR\=\cR(T)\=\{\rm \ all\ \l\!-\!critical\ resonances\  and\ 
\l\!-\!critical\ subresonances\ of \ T\}
\label{defR}
\eeq
and
\beq
\cR_0\=\cR_0(T)\=\{
{ \rm \ all\ \l\!-\!critical\ resonances\  of \ T} 
\}
\label{defR0}
\eeq
If $2<p\=|\cR_0|\=$ cardinality of $\cR_0$ then $R^i\cap R^j=\emptyset$
for all $R^i,R^j\in \cR_0$ with $i\neq j$. To each element $R^i$ of $\cR_0$
we can associate an integer $h_i$ which is zero if $R^i$ does not contain
$\l$--critical subresonances, otherwise
\beq
h_i\=\max_{\cH_\l\subset R^i} |\cH_\l|\ ,\qquad
|{\rm \ set}|\= {\rm\ cardinality\ of\ the\ set\ }
\label{defhi}
\eeq
See Figure~\ref{fig:5} for an example of critical resonances and 
subresonances.
(In Figure~\ref{fig:5}
$\cR_0$ $=$ $\{R^1,R^2\}$ and $R_1,...,R_9$ are critical subresonances; 
notice that $R^1$ contains five hierarchies, three of which have $h=1$).
\edfn
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(385,150)
\put(10,10){\begin{picture}(370,140)
\thicklines
\put(1,66){$\odot$}
\multiput(10,70)(3,1){6}{\circle*{1}}
\put(25,75){\line(3,1){15}}
\put(40,80){\line(3,-1){60}}
\multiput(40,80)(30,-10){3}{\circle*{6}}
\put(100,60){\line(1,1){40}}
\put(120,80){\circle*{6}}
\put(140,100){\line(1,0){75}}
\multiput(140,100)(15,0){6}{\circle*{6}}
\put(215,100){\line(3,1){30}}
\put(245,110){\line(1,0){120}}
\multiput(245,110)(30,0){5}{\circle*{6}}
\put(215,100){\line(1,-1){51}}
\put(245,70){\circle*{6}}
\put(266,49){\circle*{6}}
\put(266,49){\line(1,0){15}}
\put(281,49){\circle*{6}}
\thinlines
\put(170,100){\oval(15,15)}
\put(175,86){$R_9$}
\put(120,80){\oval(20,20)}
\put(130,65){$R_7$}
\put(170,100){\oval(50,40)}
\put(193,75){$R_8$}
\put(150,90){\oval(120,90)}
\put(205,40){$R_3$}
\put(245,110){\oval(40,30)}
\put(262,90){$R_6$}
\put(245,70){\oval(20,20)}
\put(240,50){$R_4$}
\put(266,49){\oval(15,15)}
\put(270,34){$R_5$}
\put(335,110){\oval(20,20)}
\put(345,95){$R^2$}
\put(172.5,85){\oval(240,120)}
\put(295,25){$R^1$}
\end{picture}}
\parbox{15cm}{
\caption{\label{fig:5} Critical (sub)resonances}
}
\end{picture}
\end{center}
\end{figure}

%
\dfntwo{Coresonances}{dfn:10}
To any $\l$--critical (sub)resonance
$R$ in $\cR$ we associate {\em its coresonance}
\beq
\bR\= R\bks \{ 
{\rm\ all\ \l\!-\!critical\ subresonances\ contained \ in \ R}
\}
\label{defbR}
\eeq
If $R$ is minimal (\ie does not contain any element of $\cR$)
then $\bR=R$ otherwise $\bR$ is the disjoint union of two or more
subtrees of $T$. In any case, for any coresonance $\bR$,
we always have
\beq
\a(\bR)\=\sum_{v\in\bR} \a_v=0\ .
\label{5.8}
\eeq
We denote
\beq
\bcR\=\bigcup_{R\in\cR} \ \bR
\label{defbcR}
\eeq
the set of all coresonances.
Finally, we let
\beq
\bT\=T\bks \bigcup_{R\in\cR_0} R
\label{defbT}
\eeq
so that $\bT=T$ if $\cR_0=\emptyset=\cR$ and otherwise $\bT$
is the disjoint union of one rooted tree (or only of the earth $\eta$ if 
$r\in R\in\cR_0$) and of one or more subtrees.
\edfn

\rem{rem:5.4}
$R\in\cR$ is connected to $T\bks R$ by two edges $u\bu$, $v\bv$
with $u,v\in T\bks R$ ($u\neq v$ and 
either $u$ or $v$ may be the earth $\eta$)
and with $\bu,\bv\in\bR$ ($\bu,\bv$ may coincide).
\erem

\dfntwo{Subtree contractions}{dfn:11}
Let $T$ ba a (possibly rooted) tree and $R\subset T$ a subtree of 
degree two. We define {\em the contraction of $T$ over $R$}
denoted $T/R$ as follows. Let $u\bu$, $v\bv$, ($\bu,\bv\in R$), 
be the two edges connecting $R$ with $T\bks R$; we then set
\beq
T/R\= T\bks R + uv 
\label{defcontr}
\eeq
See Figure~\ref{fig:6} for examples.
\edfn
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(385,225)
\put(0,125){\begin{picture}(130,100)
\thicklines
\put(20,70){\line(1,-1){20}}
\put(20,70){\circle*{3}}
\put(20,30){\line(1,1){20}}
\put(20,30){\circle*{3}}
\put(40,50){\line(1,0){20}}
\put(40,50){\circle*{3}}
\put(60,50){\circle*{3}}
\put(72,44){\line(3,1){18}}
\put(72,44){\circle*{3}}
\put(57,29){\line(1,1){15}}
\put(57,29){\circle*{3}}
\put(72,44){\line(1,-1){15}}
\put(87,29){\circle*{3}}
\put(72,44){\line(1,2){6}}
\put(78,56){\circle*{3}}
\put(60,50){\line(3,1){18}}
\put(90,50){\line(1,0){20}}
\put(90,50){\circle*{3}}
\put(110,50){\circle*{3}}
\thinlines
\put(75,43){\oval(55,50)}
\put(37,40){$u$}
\put(57,38){$\overline{u}$}
\put(87,38){$\overline{v}$}
\put(105,40){$v$}
\put(100,20){$R$}
\put(20,10){$T$}
\end{picture}}
\put(140,125){\begin{picture}(110,100)
\thicklines
\put(15,30){\line(1,1){20}}
\put(15,30){\circle*{3}}
\put(35,50){\line(1,0){40}}
\multiput(35,50)(20,0){3}{\circle*{3}}
\put(75,50){\line(1,1){20}}
\put(95,70){\circle*{3}}
\put(75,50){\line(1,-1){20}}
\put(95,30){\circle*{3}}
\thinlines
\put(55,50){\oval(20,20)}
\put(50,30){$R$}
\put(20,10){$T$}
\put(40,65){$\overline{u}=\overline{v}$}
\put(33,40){$u$}
\put(70,40){$v$}
\end{picture}}
\put(260,125){\begin{picture}(110,100)
\thicklines
\put(30,70){\line(1,0){20}}
\put(30,70){\circle*{3}}
\put(50,70){\circle*{3}}
\put(50,70){\line(0,1){15}}
\put(50,85){\circle*{3}}
\put(50,70){\line(1,-1){20}}
\put(70,50){\circle*{3}}
\put(70,50){\line(1,1){20}}
\put(90,70){\circle*{3}}
\put(70,50){\line(1,-1){20}}
\put(90,30){\circle*{3}}
\put(45,25){\line(1,1){25}}
\put(45,25){\circle*{3}}
\put(45,25){\circle{8}}
\thinlines
\put(80,50){\oval(55,50)}
\put(107,20){$R$}
\put(25,30){$T$}
\put(45,60){$v$}
\put(76,47){$\overline{u}=\overline{v}$}
\end{picture}}
\put(0,25){\begin{picture}(130,100)
\thicklines
\put(20,70){\line(1,-1){20}}
\put(20,70){\circle*{3}}
\put(20,30){\line(1,1){20}}
\put(20,30){\circle*{3}}
\put(40,50){\line(1,0){30}}
\put(40,50){\circle*{3}}
\put(70,50){\circle*{3}}
\thinlines
\put(40,40){$u$}
\put(65,40){$v$}
\put(40,10){$T/R$}
\put(60,115){\vector(0,-1){30}}
\end{picture}}
\put(140,25){\begin{picture}(110,100)
\thicklines
\put(15,30){\line(1,1){20}}
\put(15,30){\circle*{3}}
\put(35,50){\line(1,0){30}}
\multiput(35,50)(30,0){2}{\circle*{3}}
\put(65,50){\line(1,1){20}}
\put(85,70){\circle*{3}}
\put(65,50){\line(1,-1){20}}
\put(85,30){\circle*{3}}
\thinlines
\put(33,40){$u$}
\put(60,40){$v$}
\put(40,10){$T/R$}
\put(50,115){\vector(0,-1){30}}
\end{picture}}
\put(260,25){\begin{picture}(110,100)
\thicklines
\put(40,60){\line(1,0){20}}
\put(40,60){\circle*{3}}
\put(60,60){\circle*{3}}
\put(60,60){\line(0,1){15}}
\put(60,75){\circle*{3}}
\put(60,60){\line(0,-1){20}}
\put(60,40){\circle*{3}}
\put(60,40){\circle{8}}
\thinlines
\put(65,60){$v$}
\put(50,10){$T/R$}
\put(70,115){\vector(0,-1){30}}
\end{picture}}
\parbox{12cm}{\caption{\label{fig:6} Tree contractions}}
\end{picture}
\end{center}
\end{figure}

%
\nin
Coresonances $\bR$ are crucial for constructing 
``complete families": they will be the invariants
of all the trees (with a common $\a$ function) belonging
to the same complete family. We describe with more detail
the set $\bcR$.

\dfntwo{Critical chains and connecting points}{dfn:12}
{\em A ($\l$)--cri\-ti\-cal chain} $C$ is an {\em
ordered $s$--ple of coresonances},
$(\bR_1,...,$ $\bR_s)$, such that $\bR_i$ is connected with $\bR_{i+1}$
for all $1\le i \le s-1$ and such that $\bR_1$ and $\bR_s$ are also
connected with either $\bT$ or with a coresonance $\bR\in\bcR$ 
which contains the whole chain $C$ (\ie $R_1\cup...\cup R_s\subset R$).
The case $s=1$, {\em trivial chain}, is admitted: in such a case 
$C=\bR_1$ is connected with either $\bT$ or with a coresonance
$\bR$ such that $R_1\subset R$.
Given a chain $C$, $\bR\in C$ means that $C\=(\bR_1,...,\bR_s)$ and 
$\bR=\bR_i$ for some $i$; analogously $v\in C$ means that $v$
is a vertex $\in \bR$ for some $\bR\in C$.
With this convention we see that
\beq
\cC\=\{ 
{\rm\ the \ set\ of\ all\ chains\ }
\}
=\bcR
\label{defcC}
\eeq
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(385,150)
\put(5,40){\begin{picture}(370,100)
\thicklines
\put(77,42){$v_5$}
\put(114,42){$v_2$}
\put(197,42){$v_3$}
\put(38,50){\circle*{3}}
\put(38,50){\circle{8}}
\put(38,50){\line(1,0){242}}
\multiput(60,50)(20,0){5}{\circle*{3}}
\multiput(180,50)(20,0){6}{\circle*{3}}
\put(38,50){\line(1,4){4}}
\put(42,66){\circle*{3}}
\put(34,38){$v_4$}
\put(60,50){\line(1,1){10}}
\put(70,60){\circle*{3}}
\put(50,40){\line(1,1){10}}
\put(50,40){\circle*{3}}
\put(60,50){\line(1,-1){10}}
\put(70,40){\circle*{3}}
\put(80,50){\line(1,1){10}}
\put(90,60){\circle*{3}}
\put(130,40){\line(1,1){10}}
\put(130,40){\circle*{3}}
\put(180,50){\line(1,1){10}}
\put(190,60){\circle*{3}}
\put(170,60){\line(1,-1){10}}
\put(170,60){\circle*{3}}
\put(260,50){\line(1,2){8}}
\put(268,66){\circle*{3}}
\put(260,50){\line(1,-2){8}}
\put(268,34){\circle*{3}}
\put(250,42){$v_1$}
\put(280,50){\line(1,2){15}}
\put(295,80){\circle*{3}}
\put(295,72){$v_6$}
\put(272,42){$v_7$}
\put(280,50){\line(3,-1){45}}
\multiput(295,45)(15,-5){3}{\circle*{3}}
\put(325,35){\line(1,0){15}}
\put(340,35){\circle*{3}}
\put(320,27){$v_8$}
\thinlines
\put(60,50){\oval(30,40)}
\put(52,17){$R_4$}
\put(70,48){\oval(74,70)}
\put(70,0){$R_1$}
\put(140,50){\oval(30,40)}
\put(132,17){$R_6$}
\put(180,50){\oval(30,40)}
\put(172,17){$R_5$}
\put(160,48){\oval(94,70)}
\put(160,0){$R_2$}
\put(230,50){\oval(34,20)}
\put(230,25){$R_3$}
\put(310,40){\oval(80,40)}
\put(310,7){$R_7$}
\put(302.5,42.5){\oval(35,15)}
\put(300,23){$R_8$}
\end{picture}}
\parbox{14cm}{\caption{\label{fig:7}
 Critical chains $\cC\equiv\{(\overline{R}_1,
\overline{R}_2,R_3)$,$(R_5,R_6)$, $R_4$, $\overline{R}_7$, $R_8$ \}
}}
\end{picture}
\end{center}
\end{figure}

\giu
%
Given a chain $C\=(\bR_1,...,\bR_s)$ we let $u\=u(\bR_1)\=u(C)$,
$w\=w(\bR_s)\=w(C)$ be the unique points outside $C$ such that $u\bu$
and $w\bw$ are the edges connecting, respectively, 
$\bR_1$ and $\bR_s$ with $T\bks C$: thus $\bu\in\bR_1$,
$\bw\in\bR_s$, $u$ and $w$ are distinct (and one of them may be the earth 
$\eta$). The points $u,w$ will be called {\em the base points of the
chain $C$}.

\nin
In the example shown in Figure~\ref{fig:7}, if $C_1\=(\bR_1,\bR_2,R_3)$
and $C_2\=(R_5,R_6)$ we have the connecting points: $u(C_1)=\eta$,
$w(C_1)=v_1$, $u(C_2)=v_3$, $w(C_2)=v_2$ and
$u(R_4)=v_5$, $w(R_4)=v_6$, $u(\bR_7)=v_6$, $w(\bR_7)=v_1$,
$u(R_8)=v_7$, $w(R_8)=v_8$.

\nin
We denote by 
\beq
U\=U(T)\=\{ u(C),w(C):\ C\in \cC\}
\label{defU}
\eeq
the {\em set of base points of $T$.}
\edfn

\rem{rem:5.5}
The order of a chain $(\bR_1,...,\bR_s)$ is related to the order in $T$ 
as follows: {\em either} $\bR_1>\cdot\cdot\cdot > \bR_s$
(as in the chain $C_1$ of the above example) {\em or}
$\bR_1<\cdot\cdot\cdot < \bR_s$ (as in $C_2$).
\erem
%
Finally, we are ready to define {\em complete families of trees
generated by a tree $T$ and a given $T$--admissible function $\a$.}

\dfntwo{Complete families}{dfn:13}
Given $T\in\cT^k$, $\a$ $T$--admissible and $\l<1/2$ we define
\beq
\cF(T)\=\{ T\}
\label{defcF1}
\eeq
if $\cR(T)=\emptyset$ (\ie if there are no $\l$--critical resonances
in $T$), otherwise, letting $\cR\=\cR(T)$, $\cC\=\cC(T)$, we define
\beqa
\cF(T)& \= 
\{ T'\in\cT^k: & \ T'= \bT\cup 
\bigcup_{\bR\in\bcR} \bR + \nonumber\\
& &
\sum_{C=(\bR_1,...,\bR_s)\in\cC} 
u(C)\bu_1+ w(C)\bw_s +
\sum_{i=1}^{s-1} \bw_i\bu_{i+1} \ ,\nonumber\\
& &{\rm where}\ \bu_i,\bw_i\ {\rm vary\ in\ }
\bR_i \}
\label{defcF}
\eeqa
if $s=1$ for some $C$ the sum over $i$ has to be omitted.
$\cF$ {\em is called the complete family associated to 
$(T,\a)$}.
\edfn
%
Obviously, the integers $n_i\=\a_{v_i}$, 
which together with the ``topological"
structure of the tree $T$ generates $\cF$, may be thought of as fixed
``attributes" of the labels $v_i$ and, 
{\em by construction,
$\{\a_{v_i}\}$ is admissible for any tree $T'\in\cF(T)$}.
The following Proposition collects a few elementary properties
of complete families.

\begin{figure}[hbt]
\begin{center}
\begin{picture}(385,340)
\multiput(5,20)(0,80){4}{\begin{picture}(380,80)
\multiput(0,0)(95,0){4}{\begin{picture}(90,80)
\thicklines
\put(20,50){\circle*{3}}
\put(40,40){\line(0,1){20}}
\multiput(40,40)(0,20){2}{\circle*{3}}
\put(60,50){\circle*{3}}
\thinlines
\put(40,45){\oval(26,40)}
\put(40,42.5){\oval(60,60)}
\put(46,18){$R_2$}
\put(65,10){$R_1$}
\put(15,40){$v_1$}
\put(35,30){$v_2$}
\put(42,48){$v_3$}
\put(55,40){$v_4$}
\end{picture}}
\put(0,0){\begin{picture}(380,80)
\thicklines
\put(20,50){\line(2,-1){20}}
\put(40,60){\line(2,-1){20}}
\put(115,50){\line(2,1){20}}
\put(135,60){\line(2,-1){20}}
\put(210,50){\line(2,-1){20}}
\put(230,40){\line(2,1){20}}
\put(305,50){\line(2,1){20}}
\put(325,40){\line(2,1){20}}
\end{picture}}
\end{picture}}
\multiput(5,260)(95,0){4}{\begin{picture}(90,80)
\put(20,50){\circle{6}}
\put(60,50){\line(1,0){20}}
\put(80,50){\circle*{3}}
\put(75,40){$v_5$}
\end{picture}}
\multiput(5,180)(95,0){4}{\begin{picture}(90,80)
\put(20,50){\circle{6}}
\put(0,50){\line(1,0){20}}
\put(0,50){\circle*{3}}
\put(0,40){$v_5$}
\end{picture}}
\multiput(5,100)(95,0){4}{\begin{picture}(90,80)
\put(60,50){\circle{6}}
\put(60,50){\line(1,0){20}}
\put(80,50){\circle*{3}}
\put(75,40){$v_5$}
\end{picture}}
\multiput(5,20)(95,0){4}{\begin{picture}(90,80)
\put(60,50){\circle{6}}
\put(0,50){\line(1,0){20}}
\put(0,50){\circle*{3}}
\put(0,40){$v_5$}
\end{picture}}
\parbox{15cm}{\caption{\label{tab:1} A complete family $\cF$ (Example 1)}} 
\end{picture}
\end{center}
\end{figure}
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(385,340)
\multiput(5,20)(0,80){4}{\begin{picture}(380,80)
\multiput(0,0)(95,0){4}{\begin{picture}(90,80)
\thicklines
\put(20,40){\line(0,1){20}}
\multiput(20,40)(0,20){2}{\circle*{3}}
\put(50,40){\line(0,1){20}}
\multiput(50,40)(0,20){2}{\circle*{3}}
\put(70,50){\circle*{3}}
\thinlines
\put(20,45){\oval(26,40)}
\put(50,45){\oval(26,40)}
\put(10,10){$R_1$}
\put(40,10){$R_2$}
\put(15,30){$v_1$}
\put(8,48){$v_2$}
\put(45,30){$v_3$}
\put(52,49){$v_4$}
\put(65,40){$v_5$}
\end{picture}}
\put(0,0){\begin{picture}(380,80)
\thicklines
\put(20,60){\line(1,0){30}}
\put(115,60){\line(3,-2){30}}
\put(210,40){\line(3,2){30}}
\put(305,40){\line(1,0){30}}
\end{picture}}
\end{picture}}
\multiput(5,260)(95,0){4}{\begin{picture}(90,80)
\put(20,40){\circle{6}}
\put(50,60){\line(2,-1){20}}
\end{picture}}
\multiput(5,180)(95,0){4}{\begin{picture}(90,80)
\put(20,40){\circle{6}}
\put(50,40){\line(2,1){20}}
\end{picture}}
\multiput(5,100)(95,0){4}{\begin{picture}(90,80)
\put(20,60){\circle{6}}
\put(50,60){\line(2,-1){20}}
\end{picture}}
\multiput(5,20)(95,0){4}{\begin{picture}(90,80)
\put(20,60){\circle{6}}
\put(50,40){\line(2,1){20}}
\end{picture}}
\parbox{15cm}{\caption{\label{tab:2} A complete family $\cF$ (Example 2)}} 
\end{picture}
\end{center}
\end{figure}
%

\protwo{Properties of $\cF$}{pro:procF}
Let $T\in\cT^k$, $\a$ a $T$--admissible function and $\l<1/2$. Then:
\beqano
& {\rm (i)} & \cF(T)=\{ T\} \sse \ \cR(T)=\emptyset\ ;\\
%
& {\rm (ii)} & \cF(T') = \cF(T)\qquad \forall\ T'\in\cF(T)\ ;\\
%
& {\rm (iiii)} & \cF(T)\cap\cF(T')\neq \emptyset \implies\ 
T'\in \cF(T)\ ;\\
%
& {\rm (iv)} & \bT,\cR(T),U(T)\quad{\rm is\ a\ complete\ 
and \ minimal}\\
& &{\rm set\ of\ invariants\ for\ \cF(T)}\ ;\\ 
%
& {\rm (v)} & |\cF|=\prod_{\bR\in\bcR} |V(\bR)|^2\ ;\\
%
& {\rm (vi)}& \deg_{T'} v\le \deg_{T''} v+2
\qquad \forall\ T',T''\in\cF(T)\\
\eeqano
\epro
The proof of the Proposition is a simple consequence of 
the various definitions.

\rem{rem:5.6}
>From (i), (ii), (iii) above it follows immediately that the property
$T'\in\cF(T)$ is an {\em equivalence relation}.
Thus  the set of all labeled rooted trees, given
$\{n_i\}\=\{\a_{v_i}\}$, can be {\em partitioned
into disjoint complete families}: here we have preassigned
the function $\a_{v_i}\=n_i$ and we
use the convention that if $\a$ is not admissible for some $T$
we are omitting the (meaningless) contribution coming from that tree.
\erem
%
A final comment: the set of labels $\{v_1,...,v_k\}$ of $\cT^k$
can be thought of as the set of vertices $V$ of $\cF$ and for any
$v\in V$ we set
\beq
\deg_\cF v= \max_{T'\in\cF} \deg_{T'} v
\label{defdegF}
\eeq
and from (vi) of Proposition \ref{pro:procF} it follows immediately that:
\beq
\deg_\cF v - 2 \le \deg_{T'} v\le \deg_\cF v\ ,\qquad \forall\ T'\in\cF
\label{degF}
\eeq
In Figure~\ref{tab:1} and Figure~\ref{tab:2} we show the complete
families associated to order 5 trees with two resonances. 
%

\nin
In Figure~\ref{tab:1} we have 
$\cR_0=R_1$, $\cR=\{R_1,R_2\}$, $C_1 \equiv \overline{R}_1$, $C_2 \equiv 
R_2$, $\overline{T} = \{\eta\} \cup \{v_5\}$, $\overline{R}_1 \equiv \{v_1\} 
\cup \{v_4\}$, $u(C_1)=\eta$, $w(C_1)=v_5$, $u(C_2)=v_1$, $w(C_2)=v_4$,
$|\cF|=|V(\bR_1)|^2 |V(R_2)|^2=16$.

\giu
In Figure~\ref{tab:2} we have 
$\cR_0=\cR=\{ R_1, R_2\}$, $C_1=(R_1,R_2)$, $u(C_1)=u(R_1)=\eta$,
$w(C_1)=w(R_2)=v_5$, 
$|\cF|=|V(R_1)|^2 |V(R_2)|^2=16$.
%********************************************

\newpage

\section{Estimates}
\label{sec:estima}
\setcounter{equation}{0}
%
In this section we formulate the estimates on (sums)
of products of small divisors needed to prove Kolmogorov's
(KAM) theorem following Siegel's strategy. The first two
lemmas are a simple generalization of Siegel's argument
and deal with situations without resonances (or better
with non critical resonances). The first lemma is taken from 
\cite{E}. The third and fourth lemmas are the crucial point
of our paper: it is shown that sums over complete families
obey the same bounds that hold for products of small divisors
without resonances (\ie without repetitions). In other words,
the ``divergent terms" whose occurrence has been discussed
in Section~\ref{sec:diverge} compensate (and in fact {\em they
do not cancel exactly}) within complete families.
The four lemmas will easily yield Kolmogorov's  theorem for the
case under consideration \equ{he}; see Theorem~\ref{thm:kam}
below. The proofs are presented in the next section.

\giu
Recall \equ{dioph} and the definition of admissible functions
\equ{adm}.
%
\lemtwo{Siegel, Eliasson}{lem:se}
Let $T\in\cT^k$ be a rooted tree of order $k$ (\ie
$k$ $\=$ cardinality of $V(T)$), $\a$ a $T$--admissible
function and $0<\l<1$. Assume that
\beq
{\rm if}\ \d_u=\d_w\ {\rm for\ some\ }u>w \ \ {\rm then\ }
\exists\ v\ {\rm s.t.} \ u>v>w\ {\rm and}\ |\d_v|>\l |\d_u|
%
\label{hy1}
\eeq
Then there exist constants $c_1>\g$, $\b_1>\t$ such that
\beq
\prod_{v\in T} |\d_v|^{-1}\le c_1^k \ \prod_{v\in T} |\a_v|^{\b_1}
\label{e.1}
\eeq
The constant $c_1,\b_1$ can be taken to be
\beq
c_1=\g\ 2^{6\t}\  \frac{1+\l}{\l}\ ,\qquad
\b_1=3\t
\label{const1}
\eeq
\elem
%
Next Lemma extend the above type of estimate to
products of small divisors arising in trees with (possible)
resonant subtrees which are non $\l$--resonant (for some
prefixed $\l<1/2$); recall that such trees may contain couples 
of points which violate
\equ{hy1} (see Remark~\ref{rem:5.1})
so that the result described in the next Lemma
is a genuine generalization of the estimates described in
Lemma~\ref{lem:se}.
%
\lem{lem:2}
Let $T$ and $\a$ be as in Lemma~\ref{lem:2} and let
$0<\l<1/2$.
Assume that there are no $\l$--resonance (Definition~{\rm\ref{dfn:4}}).
Then there exist constants $c_2>\g$ and $\b_2>\t$ such that
\beq
\prod_{v\in T} |\d_v|^{-1}\le c_2^k \ \prod_{v\in T} |\a_v|^{\b_2}
\label{e.2}
\eeq
The constant $c_2,\b_2$ can be taken to be
\beq
c_2=c_1\ 2^{\t}\  \frac{1-\l}{1-2\l}\ ,\qquad
\b_2=\b_1+\t
\label{const2}
\eeq
\elem
%
\lemtwo{Small divisor compensations}{lem:3}
\HB\nin
Let $T$, $\a$ and $\l$ be as in Lemma~{\rm\ref{lem:2}} and
let $0<\bl<1$.
Let $R$ be a minimal $\l$--(sub)resonance of $T$ 
(\ie $R$ does not contain any $\l$--subresonance,
see Definition~{\rm\ref{dfn:7}}) and
let $n\in\zNn$ be such that $\agl{n}\le \bl \D(R)$.  
Let $z$ be an extra vertex (not in $T$) and
set $\a_z=n$. Finally, for any $u,w\in R$,
denote by $R_u^w$ the tree\footnote{\rm If $R$ is rooted,
$R=R_r$, first remove the edge $\eta r$ so as to obtain
an unrooted subtree.}
$R\cup \{z\}+wz$ rooted at $u$.
Then there exist constants $c_3>\g^2$, $\b_3>2\t$ such that
for all $1\le i,j\le N$
\beq
|\sum_{u,w\in R} \a_{ui} \a_{wj}
\prod_{v\in R} \d_v(R_u^w)^{-2}|
\le c_3^{|V(R)|} \ \prod_{v\in R} |\a_v|^{\b_3}
\label{e.3}
\eeq
where $\a_{ui}$ (respectively $\a_{uj}$) denote 
the $i^{\rm th}$ (respectively the $j^{\rm th}$) 
component of the integer vector $\a_u$.
The constant $c_3,\b_3$ can be taken to be
\beq
c_3=\big( c_2\  2^{\t+1} (1-\bl)^{-1} \big)^2\ ,\qquad
\b_3=2(\b_2+\t+1)
\label{const3}
\eeq
\elem
%
The estimates \equ{e.3} lead easily to control the
contribution to \equ{exptree} coming from
complete families.
%
\lem{lem:4}
Let $T$, $\a$ and $\l<1/2$ be as above. Let $\cF\=\cF(T)$ be
the complete family defined in Definition~{\rm\ref{dfn:13}},
$V\=V(T)=V(\cF)$ and recall the definition of $\deg_\cF$
given in \equ{defdegF}. Then there exist constants
$c_4>\g^2$, $\b_4>2\t$ such that
\beq
\big| 
\sum_{T'\in\cF} \prod_{vv'\in E(T')} \a_v\cdot\a_{v'}
\prod_V \d_v^{-2}\big| \le
\prod_{v\in V} |\a_v|^{\deg_\cF v} \ c_4^{|V|}\ \prod_{v\in V}
|\a_v|^{\b_4}
\label{e.4}
\eeq
The constants $c_4,\b_4$ can be taken to be
\beq
c_4\=(c_2\ 2^{\t+1}\  \frac{1-\l}{1-2\l} )^2\ ,
\qquad \b_4= \b_3
\label{const4}
\eeq
\elem
%
Kolmogorov's theorem follows now easily. We introduce the following 
norms on analytic functions $g:\tN\to\complex$:
\beq
\| g\|_\s \= \sum_{n\in\zN} |g_n| e^{|n|\s}
\label{norm}
\eeq
Clearly, for any analytic function on $\tN$ there exist a $\s>0$ such
that the above norm is finite; viceversa if $g$ is such that 
$\|g\|_\s<\infty$ for some $\s>0$ then $|g_n|\le \|g\|_\s \exp(-|n|\s)$
so that $g$ is analytic. If $g=(g_1,...,g_M):\tN\to\complex^M$
we set
\beq
\|g\|_\s\=\sup_{1\le j\le M} \|g_j\|_\s
\label{norm2}
\eeq
%
\thm{thm:kam}
Let $f$ in \equ{he} be real--analytic with $\| f\|_\bs<\infty$
for some $\bs>0$. Then the formal solution $X(\th,\e)$
described in Proposition~{\rm\ref{pro:ef}} is real--analytic.
Furthermore, fix $0<\s<\bs$, $0<\l<1/2$  and set
\beq
\e_0\=\frac{(\bs-\s)^{\b_5}}{c_5 \|f\|_\bs}\ \quad
{\rm with}\quad\cases{ \b_5\=\b_4+4\cr
c_5\= c_4 2^{\b_5+1}\ \b_5!\cr}
\label{const5}
\eeq
where the constants $\b_4,c_4$ are defined above.
Then $X(\th,\e)$ is jointly analytic in the domain
$\{|\Im \th_i|\le \s\}$ $\times$ $\{|\e|\le \e_0\}$ and for
any (complex) $\e$ with $|\e|<\e_0$ the following bound holds
\beq
\|X(\cdot,\e)\|_\s \le \frac{\bs-\s}{2}\ 
\frac{|\e|}{\e_0-|\e|}
\label{est}
\eeq
\ethm
%
\rem{rem:constants} Choosing $\l=1/5$ (so as to minimize the constant 
$c_5$) one obtains
\beq
\b_5= 10\t+12\ ,\qquad c_5< \g^2 \ 2^{26 \t+23}\ (10\t+12)!
\eeq
Such constants are certainly not optimal.
\erem
% 
%********************************************

\section{Proofs}
\label{sec:proofs}
\setcounter{equation}{0}

%
In the following five Subsections we give 
the proofs of the four Lemmas
and of the Theorem of Section~\ref{sec:estima}.
In the first Subsection we show how  Kolmogorov's Theorem 
can be easily derived from Lemma~\ref{lem:4} and in the remaining
Subsections we give the proofs of the four Lemmas.
%

\subsection{Proof of Theorem {\bf 6.1}} %\ref{thm:kam}
\label{subsec:1} 
%
Recall the form of the coefficients $\Xk_{jn}$ given 
in \equ{exptr1} $\div$ \equ{exptr3}.
By Remark~\ref{rem:5.6} 
we know that, for a given choice of $\{n_1,...,n_k\}$
with $n_i\in\zNn$,the labeled rooted trees in $\cT^k$ can be 
partitioned into complete families having as common
admissible $\a$ function $\a_{v_i}=n_i$. Denote by 
$\calN\=\calN(n_1,...,n_k)$ the set of all such complete
families. Then, by \equ{exptr1} $\div$ \equ{exptr3},
by Lemma~\ref{lem:4} and by \equ{defdegF}, \equ{degF} 
we see that, for any $0<\s<\bs$,
\beqa
&&\sum_{n\in\zNn} e^{\s|n|} |\Xk_{jn}| \nonumber\\
&&= \sum_n e^{\s|n|} \frac{1}{k!}\  \Big|
\sum_{ {n_1,...,n_k}\atop{n_i\neq 0,\sum n_i=n}}
\sum_{\cF\in\calN} \prod_{i=1}^k f_{n_i}
\sum_{T\in \cF} \prod_{vv'\in E(T)} \a_v\cdot\a_{v'}
\prod_{V} \d_v^{-2}\Big| \nonumber\\
&& \le \sum_{n} \frac{1}{k!} 
\sum_{ {n_1,...,n_k}\atop{n_i\neq 0,\sum n_i=n}}
\sum_{\cF\in\calN} \prod_{i=1}^k \big(f_{n_i}e^{\s|n_i|}\big)
\prod_{v\in V} |\a_v|^{\deg_\cF v} c_4^k
\prod_{V} |\a_v^{\b_4}|\nonumber\\
&&\le 
\frac{1}{k!} \sum_{T\in\cT^k} \sum_{\a:T\to\zN}
\prod_{V} \big( c_4 |f_{\a_v} |\a_v|^{\b_4+2} e^{\s |\a_v|}\big)
\prod_V |\a|^{\deg v}
\label{6.1}
\eeqa
In view of Proposition~\ref{pro:exptree2} we see that, if we define
\beq
\phi_n\=c_4|f_n| e^{\s|n|} |n|^{\b_4+2}
\label{6.2}
\eeq
then, last line of \equ{6.1} is exactly the formal solution
$g$ of the equation \equ{gphi} with coefficient $g_k$
given in \equ{exptree2}.
But since (by the analyticity of $f$) the nonnegative numbers
$\phi_n$ decay exponentially fast as $|n|\to\infty$, 
the function of two complex variables
\beq
G(x,\e)\= x-\e\sum_{n\in\zN} \phi_n |n| e^{|n|x}
\label{6.3}
\eeq
is holomorphic and bounded in the complex $2$--disk
\beq
D\=\{ x\in\complex:\ |x|\le s\} \times
\{\e\in\complex: \ |\e|\le\e_0\}
\label{6.4}
\eeq
for any $\e_0>0$ and any $0<s<\bs-\s$. In fact,
recalling that $\b_5\=\b_4+4$ we find
\beqa
\sup_D |G|<\sup_D |G_x| &=&
\e_0 \sum_{n\in\zN} \phi_n |n|^2 e^{\s|n|} \nonumber\\
&\le&
\e_0\ c_4 \ (\bs-\s-s)^{-\b_5} \b_5!\  \|f\|_\bs
\label{6.5}
\eeqa
Taking $s\=(\bs-\s)/2$ and $\e_0$ as in \equ{const5} we see that
$\sup_D |G_x|\le 1/2$, and, since $G(0,0)=0$, by the complex
Implicit Function Theorem, we conclude that there exists a unique 
analytic function $g(\e)$ such that
\beq
G(g(\e),\e)=0\ ,\qquad \sup_{{ \e\in \complex}\atop{|\e|\le\e_0}}
|g(\e)| \le s=\frac{\bs-\s}{2}
\label{6.6}
\eeq
Thus $g_k\le \frac{1}{2} (\bs-\s)\e_0^{-k}$ and therefore
\beq
\| \Xk\|_\s\le \frac{1}{2} (\bs-\s) \e_0^{-k}
\label{6.7}
\eeq
and, for any complex $\e$ with $|\e|<\e_0$
\beq
\| X(\cdot,\e)\|_\s \le \frac{\bs-\s}{2}
\frac{\e/|\e_0 |}{1-\e/|\e_0 |}
\label{6.7bis}
\eeq
completing the proof of Theorem~\ref{thm:kam}. \qed
%

\subsection{Proof of Lemma {\bf 6.1} } %\ref{lem:se}
\label{subsec:2}
We follow \cite{E}. The first two steps are stated in the next
two Sublemmas.
%

\sublem{sublem:1}
Let $P\=v_1...v_k$ be the path with $k$ vertices rooted at $v_1$.
Let $\a:P\to\zNn$ be a $P$--admissible function and fix $0<\l<1$.
Assume that 
\beq
{\rm if}\ \d_u=\d_w\ {\rm\ for\ some}\ u>w\ \ {\rm then}\ \exists
\ v \ {\rm between} \ u\ {\rm and}\ w \ {\rm s.t.}\ 
|\d_w|>\l|\d_v|
\label{6.8}
\eeq
Then there exist positive constants $D_0\ge B_0\ge \g$ such that
\beq
\prod_P |\d_v|^{-1}\le B_0 D_0^{k-1} \prod_V |\a_v|^\t
\label{6.9}
\eeq
The constants $B_0,D_0$ can be taken to be
\beq
B_0=\g\ ,\qquad D_0=\g\  2^\t \ \frac{1+\l}{\l} 
\label{6.10}
\eeq
\esublem
%
\PROOF By induction on $k$. If $k=1$, \equ{6.9}
follows at once from the Diophantine inequality \equ{dioph}.
Let $k\ge 2$ and assume the statement true for all rooted paths
with up to $k-1$ vertices satisfying \equ{6.8}. Let $(P,\a)$ as
above. Define $s$ to be the greatest integer between $1$ and $k$ 
such that
\beq
|\d_{v_s}|\ge \max_{1\le i\le k} |\d_{v_i}|
\label{6.11}
\eeq
There are four cases:
\beqa
& {\rm (i)} \  s=1 \ ,  &{\rm(ii)}\  
\a_{v_s}+\a_{v_{s-1}}\neq 0\ ,
\label{6.12} \\
&{\rm (iii)} \ \a_{v_s}+\a_{v_{s-1}}= 0\ , s+1<k\ ,
&{\rm (iv)}\ \a_{v_s}+\a_{v_{s-1}}= 0\ ,\ s+1=k
\nonumber 
\eeqa
Note that in case (iii) and (iv) we have $s<k$ because $\a$ is
$P$--admissible.
If $i=s$ when $s<k$ or $i=s-1$ when $s>1$, by the maximality of 
$|\d_{v_s}|$ we have
\beq
\agl{\a_{v_i}} = |\d_{v_i}-\d_{v_{i+1}}|\le|\d_{v_i}|+|\d_{v_{i+1}}|
\le 2|\d_{v_s}|
\label{6.13}
\eeq
hence, in case (i), by \equ{dioph},
\beq
|\d_{v_1}|^{-1}\le 2 \agl{\a_{v_1}}^{-1} \le 2 \g|\a_{v_1}|^\t
\label{6.14}
\eeq
while in case (ii)
\beq
|\d_{v_s}|\ge \frac{1}{2} \max\{\agl{\a_{v_s}}, \agl{\a_{v_{s-1}}}\}
\label{6.15}
\eeq
In case (iii) and (iv) we have that $\d_{v_{s+1}}=\d_{v_{s-1}}$,
and by \equ{6.8} 
\beq
|\d_{v_{s+1}}|>\l|\d_{v_s}|>\l|\d_{v_{s+2}}|
\label{6.16}
\eeq
where last inequality holds only in case (iii). In all cases
mimicking \equ{6.13} replacing $2$ by $(1+\l)^{-1}$ we
obtain
\beq
|\d_{v_{s+1}}|\ge \frac{\l}{1+\l} \max \{ \agl{\a_{v_{s+1}}},
\agl{\a_{v_s}}\}\ .
\label{6.17}
\eeq
Let now $\bv\=v_s$ in case (i), (ii) and $\bv\=v_{s+1}$ in case
(iii), (iv) and let, in the cases (ii), (iii), (iv),
$v'>\bv$ be adjacent to $\bv$. Then in case (ii), (iii), (iv)
we obtain from \equ{6.15} and \equ{6.17}, using the Diophantine
inequality \equ{dioph} (and the fact that $\l<1$), that
\beq
|\d_\bv|^{-1}\ \frac{|\a_\bv+\a_{v'}|^\t}{|\a_\bv|^\t  |\a_{v'}|^\t}
\le \frac{1+\l}{\l} 2^\t \g
\label{6.18}
\eeq
Now, if we let $\bar P\= P/\{\bv\}$ (recall Definition~\ref{dfn:11})
and $\bar \a:\bar P\to \zNn$ defined by
\beq
\bar a_v\=\a_v \ {\rm in\ case\ (i)}\ ;
{\rm and \ in\ case\ (ii),(iii),(iv):}\quad
\bar \a_v\equiv \cases{ \a_v & if $v\neq v'$\cr
\a_v+\a_\bv & if $v=v'$\cr}
\label{6.19}
\eeq
Then
\beq
\prod_P |\d_v|^{-1}= |\d_\bv|^{-1} 
\prod_P |\d_v(\bar P;\bar \a)|^{-1}
\label{6.20}
\eeq
If $(\bar P,\bar \a)$ verifies \equ{6.8} then we can apply
the inductive hypothesis and, using \equ{6.15} or \equ{6.16},
the Sublemma would follow immediately.
It remains to check that $(\bar P,\bar \a)$ satisfy \equ{6.8}.

\nin
Case (i) is obvious as $\bar \a$ coincide with $\a$ on
$\bar P=v_2...v_k$. Also case (iv) is easily checked as any couple
of resonant points (\ie points where the divisors $\d$ coincide)
in $\bar P$ would also be resonant for $P$.
Consider case (ii) and assume that $u>w$ form a couple of resonant 
points for $\bar P$. If either $w>v_{s-1}$ or $v_{s-1}>u$,
then \equ{6.8} follows immediately from the validity of \equ{6.8}
for $P$. If $u>v_{s-1}>w$, let $v_i\in P$ be such that $u>v_i>w$
and such that $|\d_w|>\l |\d_{v_i}|$. Then, if $v_i\neq v_s$,
\equ{6.8} holds for $\bar P$ as $v_i\in \bar P$; on the other hand
if $v_i=v_s$ then
\beq
|\d_{v_s}|\ge |\d_{v_{s-1}}|\ \implies
|\d_w|>\l |v_s|\ge \l |\d_{v_{s-1}}|
\label{6.21}
\eeq
showing that \equ{6.8} holds for $\bar P$ also in this case.
Consider case (iii). Arguing as above we see that we only
have to check the case when, in $P$, we have $\d_u=\d_w$
with $u>v_s>w$. Let as above $v_i\in P$ be such that $|\d_w|>\l 
|\d_{v_i}|$. If $v_i=v_{s+1}$ then either $u>v_{s-1}$ or $u=v_{s-1}$.
If $u>v_{s-1}$ then $|\d_w|>\l|\d_{v_{s+1}}|=\l|\d_{v_{s-1}}|$.
If $u=v_{s-1}$, then
\beq
\sum_{ {v\in P}\atop{v_s>v>w}} \a_v= 
\sum_{ {v\in P}\atop{v_{s+1}>v>w}} \a_v=-\a_{v_{s+1}}
\eeq
Hence $v_{s+1}>w$ for a resonant couple in $P$ and there exists
by \equ{6.8} a point $v_j$ between $v_{s+1}$ and $w$
($\implies v_j\in\bar P$) such that $|\d_w|>\l |\d_{v_j}|$
and we see that \equ{6.8} holds for $(\bar P,\bar \a)$
also in this final case. \qed
%

\sublem{sublem:2}
Let $r\ge 0$ and $s\ge 2$ be integers and let 
$x_1,...,x_r$, $y_1,...,y_s$ be real numbers greater or equal
than 1 and let $z$ be their sum
$z\=\sum x_i +\sum y_j$ ($r=0$ means that there are no $x$'s).
If
\beq
\sum_{j=1}^s y_j\ge \frac{z}{2}\qquad
{\rm and} \qquad y_j\le \frac{z}{2}\quad\forall\ j
\label{6.22}
\eeq
then
\beq
\prod_{i=0}^r x_i^{-1} \ \prod_{j=1}^s y_j^{-2}
\le 2^{r+2s} z^{-3}
\label{6.23}
\eeq
\esublem
%
\PROOF The proof is taken from \cite{E}: we include it for 
completeness. 
We first observe that it is enough to prove the statement for
$r\le 1$ (as $\sum x_i\le r \prod x_i \le 2^{r-1} \prod x_i$).
We can also assume that $s\le 3$ (in fact, since $(y_i+y_j)^2\le
4(y_i y_j)^2$, we can replace $y_i$ and $y_j$ by their sum
if such sum is $\le z/2$; hence we can assume $y_i+y_j>z/2$
for all $i\neq j$ and repeating the argument we end up with at most
three $y_j$). Now, let $s=3$. For $z=3$ the result holds
therefore we assume that $z>3$ and $y_1\le y_2\le y_3$. Clearly
$y_2<z/2$ (otherwise $y_3$ would also be $\ge z/2$ contradicting
the positivity of $y_1$). Furthermore 
\beq 
(y_1-t)(y_2-t)\le y_1 y_2\ ,\qquad \forall\ \ 0\le t\le y_1+y_2
\label{6.24}
\eeq
and taking $t=y_1-1$ we see that we can assume that 
$y_1=1$. Repeating the argument for $y_2$ and $y_3$ we can assume
that either $y_2$ or $y_3$ is equal to $z/2$. 
But then $y_1+y_2\le z/2$ and by
the above argument we can reduce to the case $s=2$.
We are thus lead to consider only the case $s=2$. By \equ{6.24}
we can again assume that either $y_1=1$ or $y_2=z/2$. The remaining
cases are checked directly.\qed

\giu
We are now now ready for the

\giu
{\bf Proof of Lemma~\ref{lem:se}} We shall prove, by induction
on the number $|V|$ of vertices of $T$, the following estimate
\beq
\prod_V |\d_v|^{-1}\le B D^{|V|-1} \prod_V |\a_v|^{3\t}
\big( \sum_V |\a_v|\big)^{-2\t}
\label{6.25}
\eeq
for suitable constants $D\ge B\ge \g$ determined below. 
Lemma~\ref{lem:se} follows immediately from \equ{6.25}
by taking $\b_1=3\t$ and $c_1\ge D$.

If $|V|=1$, \equ{6.25} follows from \equ{dioph} (as $B\ge \g$).
Now let $k\ge 2$, assume that \equ{6.25} holds for any
$(T',\a')$ satisfying the hypotheses of Lemma~\ref{lem:se}
and with $|V(T')|\le k-1$ and let $(T,\a)$ be as in
Lemma~\ref{lem:se} with $|V(T)|=k$. We need some notation.
Let
\beq
S_v\= \ {\rm the\ subtree\ }\ \{v'\in T:\ v'\le v\}\ \  
{\rm rooted \ at\ } 
v
\label{Sv}
\eeq
and for any subset of vertices $W\subset V$ let
\beq
|\a|(W)\=\sum_{v\in W} |\a_v|
\label{moda}
\eeq
Define
\beq
P\=\{ v\in T : \ |\a|(S_v)> \frac{1}{2} |\a|(T)\}
\label{defP}
\eeq
It is easy to check that {\em $P$ is a path}: $P=u_0...u_p$ with
$p\ge 0$, $u_0$ being the root $r$ of the tree $T$. To each $u_i$ we
associate $m_i\ge 0$ subtrees $S_{ij}$ 
as follows. Let  $m_i\= \deg u_i-2$
when $i\le p-1$, $m_p\=\deg u_p-1$ and let, for $m_i>0$,  
$v_{ij}$ be the
$m_i$ vertices adjacent to $u_i$ with $v_{ij}\notin P$. We then set
$S_{ij}\=S_{v_{ij}}$ when $m_i\neq 0$ and $S_{ij}=\emptyset$ otherwise.
We also define
\beqa
& & y_{ij}\=|\a|(S_{ij})\ ,\quad y_i\=\sum_{j=1}^{m_i} y_{ij}\ ,\quad
x_i\=|\a_{u_i}|\nonumber\\
& & I\=[0,...,p]\ ,\quad I_0\=\{i\in I:\ m_i=0\}\ ,
\quad I_1\=\{i\in I:\ m_i>0\}\nonumber\\
&&m\=\sum_I m_i\ ,\quad k_{ij}\=|S_{ij}|\ ,
\quad k_i\=\sum_{j=1}^{m_i} k_{ij}\ ,\quad
p_0\=|I_0|\ ,\ p_1\=|I_1|\nonumber\\
&& \phantom{aaaaaaaaaa}
\label{defvarie}
\eeqa
It then follows
\beq
|\a|(T)=\sum_I x_i + \sum_{I_1} y_i\ ,\quad p_0+p_1=p+1\ ,\quad
k=p+1+\sum_{i\in I_1} k_i\ ,\quad m\ge p_1
\label{6.30}
\eeq
and, by the definition of $P$
\beqa
& &\sum_{j\ge i} x_j + \sum_{ {j\ge i}\atop{j\in I_1}} >
\frac{1}{2} |\a|(T)\ ,\qquad \forall\ i\in I\nonumber\\
& &x_i\le \frac{1}{2} |\a|(T)\ \ \forall\ i<p\ ,\quad
y_{ij}\le \frac{1}{2} |\a|(T)\ \ \forall i\in I_1,\ 1\le j\le m_i
\label{6.31}
\eeqa

\begin{figure}[hbt]
\begin{center}
\begin{picture}(350,120)
\put(0,30){\begin{picture}(350,90)
\thicklines
\put(60,40){\circle*{3}}
\put(60,40){\circle{8}}
\put(60,40){\line(1,0){200}}
\multiput(100,40)(40,0){5}{\circle*{3}}
\put(220,40){\line(1,1){30}}
\put(250,70){\circle*{3}}
\put(250,70){\line(1,0){15}}
\put(265,70){\circle*{3}}
\put(250,70){\line(0,1){15}}
\put(250,85){\circle*{3}}
\put(220,40){\line(1,-1){30}}
\put(250,10){\circle*{3}}
\put(250,10){\line(1,0){15}}
\put(265,10){\circle*{3}}
\put(60,40){\line(1,3){5}}
\put(65,55){\circle*{3}}
\put(100,40){\line(1,1){15}}
\put(115,55){\circle*{3}}
\put(115,55){\line(1,0){15}}
\put(130,55){\circle*{3}}
\put(115,55){\line(0,1){15}}
\put(115,70){\circle*{3}}
\put(100,40){\line(-1,1){15}}
\put(85,55){\circle*{3}}
\put(85,55){\line(0,1){15}}
\put(85,70){\circle*{3}}
\thinlines
\put(65,55){\oval(12,12)}
\put(55,65){$S_{01}$}
\put(85,62.5){\oval(25,25)}
\put(75,80){$S_{11}$}
\put(122.5,62.5){\oval(30,30)}
\put(112,82.5){$S_{12}$}
\put(257.5,77.5){\oval(32,35)}
\put(275,85){$S_{41}$}
\put(260,40){\oval(20,20)}
\put(275,40){$S_{42}$}
\put(257.5,10){\oval(30,30)}
\put(275,7){$S_{43}$}
\put(50,28){$u_0$}
\put(90,30){$u_1$}
\put(130,30){$u_2$}
\put(170,30){$u_3$}
\put(210,30){$u_p$}
\end{picture}}
\parbox{14cm}{\caption{\label{fig:8} $m_0 = 1$, $m_1 = 2$, $p=4$ {\rm and} 
$m_p = 3$}}
\end{picture}
\end{center}
\end{figure}

\nin
If $I_1=\emptyset$ then $P\= T$ and we can apply directly
Sublemma~\ref{sublem:1} assuming that
\beq
B\ge B_0\ ,\qquad D\ge 2^{2\t}\  D_0
\label{6.32}
\eeq
>From now on we assume that $I_1\neq \emptyset$ \ie $m\ge p_1>0$.
We shall adopt the convention that {\em sums or products
over empty set of indices have to be disregarded}
(\ie replaced, respectively, by $0$ or $1$).
Next, let
\beq
\bar \a_{u_i}\=\a_{u_i}+\a(S_{ij})\ \qquad \implies \quad
|\bar \a_{u_i}|\le x_i+y_i
\label{6.33}
\eeq
then $\d_{u_i}\=\d_{u_i}(T;\a)=\d_{u_i}(P;\bar \a)$, whence
\beq
\prod_T |\d_v|^{-1}= \prod_P |\d_{u_i}(P;\bar \a)|^{-1}
\prod_{i\in I_1} \prod_{j=1}^{m_i} \prod_{v\in S_{ij}} 
|\d_v|^{-1}
\label{6.34}
\eeq
and we can use Sublemma~\ref{sublem:1} to bound the product
over $P$ (as $(P,\bar \a)$ obviously satisfy \equ{6.8})
and the inductive hypotheses to bound the product over $S_{ij}$
(note that $\d_v(T)=\d_v(S_{ij}$)).
Recalling the definitions in \equ{defvarie}, we obtain from
\equ{6.34} and \equ{6.33}
\beq
\prod_{v\in T} |\d_v|^{-1} \le
M B D^{k-1} \big(\prod_T |\a_v|^{3\t}\big) |\a|(T)^{-2\t}
\label{6.35}
\eeq
with
\beq
M\= \frac{B_0}{B} \big(\frac{B}{D}\big)^m 
\big(\frac{D_0}{D}\big)^p \big[ \prod_{I_0} 
x_i^{-2}\cdot\prod_{I_1}\big(\frac{x_i+y_i}{x_i^3}
\prod_jy_{ij}^{-1}\big)\cdot|\a|(T)^2\big]^\t
\label{6.34bis}
\eeq
and we have to show that $M\le 1$ if we choose suitably 
$D,B$.
Suppose first that $p\in I_0$. Then by 
the first inequality in \equ{6.31} with $i=p$ we have
\beq
x_p>\frac{1}{2} |\a|(T)
\label{6.35bis}
\eeq
Then using repeatedly the bound $\sum_{i=1}^m b_i\le m\prod_{i=1}^m b_i$
$\le$ $2^{m-1} \prod_{i=1}^m b_i$ (valid for real numbers $b_i\ge 1$)
and estimating $|\a|(T)^2$ in \equ{6.34bis} by $4x_p^2$ we get
\beq
M\le \frac{B_0}{B} \big(\frac{D_0}{D}\big)^p
\big[ \prod_{{i\in I}\atop{i\neq p}} x_i^{-2}
2^{p_1+2}\  2^{m-p_1}\  \prod_{i\in I_1,j} y_{ij}^{-1}
\big]^\t\le 1
\label{6.36}
\eeq
provided 
\beq
D\ge 2^\t \max\{B,2^\t D_0\}\ ,\qquad B\ge B_0 2^{2\t}
\label{6.37}
\eeq
(which is stronger than \equ{6.32}).

Suppose now that $p\in I_1$. We can assume that $x_p\le
|\a|(T)/2$ (otherwise \equ{6.35bis} holds also in this
case and we can proceed as above). Then
\beq
M\le \frac{B_0}{B} \big(\frac{B}{D}\big)^m 
\big(\frac{D_0}{D}\big)^p \big[ 2^{2m}\ 
\prod_{{i\in I}\atop{i\neq p}}x_i^{-1}
\cdot\prod_{{i\in I_1}\atop{i=neq p}}
y_i^{-1} \cdot x_p^{-2}
\prod_{j=1}^{m_p} y_{pj}^{-2}\cdot y_p
|\a|(T)^2\big]^\t
\label{6.38}
\eeq
and we see that we are in position to apply Sublemma~\ref{sublem:2}
(with $r=p+p_1-1$, $s=m_p+1$, $z=|\a|(T)=\sum_I x_i+\sum_{I_1} y_i$)
obtaining
\beq
M\le \frac{B_0}{B} \big(\frac{B}{D}\big)^p
\big(\frac{D_0}{D}\big)^p \big[ 2^{2m}\  2^{p+p_1-1}\ 
2^{2(m_p+1)}\  \frac{y_p}{|\a|(T)}\big]^\t\le 1
\label{6.39}
\eeq
provided we take
\beq
B\= B_0 \ 4^\t\ ,\qquad
D\= 4^\t \max\{ D_0,B_0 2^{4\t} \}
\label{6.40}
\eeq
(which satisfy also \equ{6.37}). Thus, by \equ{6.10},  
we can take
\beq
\b_1\=3\t\ ,\qquad c_1=\g\ 2^{6\t}\  \frac{1+\l}{\l}\ 
\label{6.41}
\eeq
This concludes the proof of Lemma~\ref{lem:se}. \qed
%

\subsection{Proof of Lemma {\bf 6.2} } %\ref{lem:2}
\label{subsec:3}
%
We prove the Lemma by induction on $k\=|V|$. For $k=1$,
\equ{e.2} follows from \equ{dioph} (as $c_2>\g$ and $\b_2>\t$).
Let $k\ge 2$, assume that the Lemma holds for all 
trees with up to $k-1$ vertices and let $T\in\cT^k$ 
have no $\l$--resonances.
Recall that even though $T$ does not contain $\l$--resonances,
it may contain either $\l$--resonant couples of points
(compare Remark~\ref{5.1}), or {\em adjacent points} $u,w$
such that $\d_u=\d_w$ (recall that the main hypothesis
of Lemma~\ref{lem:se}, \equ{hy1}, excludes the presence
of adjacent points of constancy for $\d$).
For any couple $(u,w)$ of $\l$--resonant points  let 
$R(u,w)$ be the associated resonant subtree (see
\equ{5.3}).
Let $R$ be a minimal resonant tree associated to a couple
of $\l$--resonant points (minimal meaning that $R$
does not contain $\l$--resonant points); if there are
no $\l$--resonant points we set $R=\emptyset$.
There are two cases: 

\nin
(i) either $R=\emptyset$ or $R$ contains two adjacent points
$u>w$ such that $\d_u=\d_w$, or

\nin
(ii) $R\neq \emptyset$ and $R$ does not contain any couple
of adjacent points on which $\d$ is constant.

\nin
Consider case (i): if there are no couples of adjacent points
$u,w$ such that $\d_u=\d_v$, then Lemma~\ref{lem:2} follows from 
Lemma~\ref{lem:se}, otherwise let $S=S(v_1,v_2)$ be a minimal
resonant subtree such that $v_1$ and $v_2$ are adjacent and 
of constancy for $\d$ (minimal means that $S$ does not contain
any couple of adjacent points on which $\d$ is constant).
Since $\a_v\neq 0$ for all vertices $v$, $S$ contains at least two 
points and by hypothesis $S$ is not $\l$--resonant. Thus observing 
that
\beq 
\prod_T |\d_v|^{-1} = \prod_{T/S} |\d_v|^{-1} \prod_S |\d_v|^{-1}
\= \prod_{T/S} |\d_v|^{-1} \prod_S |\d_v(S_{v_1})|^{-1}
\label{6.42}
\eeq
we see that we can apply Lemma~\ref{lem:se} to the tree $S_{v_1}$
while to the tree $T/S$ we can use the inductive 
%FOOTNOTE
hypothesis\footnote{Note that contracting resonant trees associated to
adjacent points where $\d$ is constant cannot introduce new resonances, 
thus all resonances in $T/S$ are not $\l$--resonant.}
%
so that \equ{e.2} holds in case (i) provided
\beq
c_2\ge c_1\ ,\qquad \b_2\ge \b_1
\label{6.43}
\eeq
%
Consider case (ii).
It is easy to see that the tree $T/R$ does 
not contain any $\l$--resonance and since
\beq 
\prod_T |\d_v|^{-1} = \prod_{T/R} |\d_v|^{-1} \prod_R |\d_v|^{-1}
\label{6.44}
\eeq
we see that we can estimate, by the inductive hypothesis,
the product over $T/R$. To bound the product over $R=R(u,w)$,
let $n\=\sum_{v'\le w} \a_{v'}$. Then, since $(u,w)$ form
a couple of $\l$--resonant points, for any $u<v<w$ we have
\beqa
|\d_w|&\=\agl{n}& \le  \l |\d_v|=\l |\d_v(R_u)+\gl{n}|\nonumber\\
&& \le \l \big(|\d_v(R_u)|+\gl{n}|\big)
\label{6.45}
\eeqa
(where $R_u$ is the tree $R$ rooted at $u$) and therefore
\beq
\agl{n}\le \frac{\l}{1-\l} |\d_v(R_u)|\ ,\quad \forall
\ u<v<w
\label{6.46}
\eeq
Let $\bu$ be the point in $R$ adjacent to $w$ (which is outside $R$)
and let $P$ the path (in $R$) joining $u$ and $\bu$. Then
\beqa
\prod_R |\d_v|^{-1} & =& 
\agl{n}^{-1} \prod_{ {v\in R}\atop{v\notin P}} |\d_v(R_u)|^{-1}
\prod_{ {v\in P}\atop{v\neq u}} |\d_v(R_u) +\gl{n}|^{-1}
\nonumber\\
&\le & \agl{n}^{-1} \prod_{ {v\in R}\atop{v\notin P}} |\d_v(R_u)|^{-1}
\prod_{ {v\in P}\atop{v\neq u}} \frac{1-\l}{1-2\l} |\d_v(R_u)|^{-1}
\nonumber\\ 
&\le & \big(\frac{1-\l}{1-2\l}\big)^k\ \agl{n}^{-1} \prod_{v\in R, v\neq u} 
|\d_v(R_u)|^{-1}
\label{6.47}
\eeqa
Now we can apply Lemma~\ref{lem:se} to the rooted tree(s)
$R\backslash \{u\}$ and, since $R$ is not a $\l$--resonance
\beqa
\agl{n}^{-1}& < & \l^{-1} \D(R)^{-1} \le \l^{-1}
\g \big( \sum_{v\in R} |\a_v|\big)^\t\nonumber\\
&\le &
\l^{-1} 2^{(|V(R)|-1)\t} \g \prod_R |\a_v|^\t
\label{6.48}
\eeqa
Thus
\beq
\prod_R |\d_v|^{-1}\le
(2^\t c_1)^{|V(R)|-1}\  \l^{-1} \g
\big( \frac{1-\l}{1-2\l}\big)^{|V(R)|} 
\prod_R |\a_v|^{\b_1+\t}
\label{6.49}
\eeq
and we see that Lemma~\ref{lem:2} holds also in this case if we take
\beq
\b_2=\b_1+\t\ ,\qquad
c_2=c_1\  2^\t\  \frac{1-\l}{1-2\l}
\label{6.50}
\eeq
(as $2^\t c_1>\l^{-1} \g$). \qed
%

\subsection{Proof of Lemma {\bf 6.3} } %\ref{lem:3}
\label{subsec:4} 
%
The heart of the matter is the following remarkable 
{\em algebraic fact.}

\protwo{Compensations}{pro:comp}
Let $T,R,n$ be as in Lemma~\ref{lem:3} and set
(for prefixed $1\le i,j\le N$)
\beq
\s(x)\= \sum_{u,v\in R} \a_{ui} \a_{uj} 
\prod_{ {v\in P(u,w)}\atop{v\neq u}} \big( \d_v+x\big)^{-2}
\prod_{ v\in R\bks P(u,w)} \d_v^{-2}
\label{6.51}
\eeq
where $P(u,w)$ is the path joining $u$ and $w$
(if $u=w$ the first product is missing, while if
$R$ is a path the second product is missing).
Then
\beq
\s(0)=\s'(0)=0 \qquad ( {}'\ \=\frac{d}{dx})\ .
\label{6.52}
\eeq
\epro
%
Note that
\beq
\s(\gl{n})= \sum_{u,w\in R}
\a_{ui} \a_{uj} \prod_R \d_v(R_u^w)^{-2}
\label{6.53}
\eeq
(the definition of $R_u^w$ is given in Lemma~\ref{lem:3}).
%

\giu\PROOF
Recall that $\a(R)=0$ and define, for any $u$, $w$ in $R$
and any $S\subset V(R)$ such that $\a(S)=0$
\beqa
&& \m(u) \= \prod_{ {v\in R}\atop{ v\neq u}} |\d_v(R_u)| \nonumber\\
&& \n(w)\= \sum_{u\in S,u\neq w}
\a_{wi} \sum_{{v\in P(u,w)}\atop{ v\neq u}} |\d_v(R_u)|^{-1}
\label{6.54}
\eeqa
We claim that
\beqa
&& {\rm the\ functions\ }\ \m\ {\rm and}\ \n \ {\em are\ 
\ independent \ of\ } u \ {\em and}\ w\ : \nonumber\\
&& \m(u)\=\m\=\m_R\ ,\qquad
\n(u)\=\n\=\n_{R,S}
\label{6.55}
\eeqa
The independence of $\m(u)$ from $u$ comes immediately from
the identities
\beq
\d_v(R_u)=\d_v(R_w)\ ,\quad\forall\ v\notin \ P(u,w)
\label{6.56}
\eeq
(where as usual $P(u,w)$ denotes the path joining 
$u$ and $w$) and
\beq
\prod_{ {v\in P(u,w)}\atop{v\neq u}} \d_v(R_u)
=
\prod_{ {v\in P(u,w)}\atop{v\neq w}} \big(-\d_v(T_w)\big)
\ ,\quad \forall \ u\neq w
\label{6.57}
\eeq
Note that \equ{6.56} holds for any rooted tree (\ie not necessarily
null) while in \equ{6.57} it is important that $R$ is null.
Now, for any $u$ and $w$ with $u\neq w$ \equ{6.56} and 
\equ{6.57} imply
\beqa
\m(u) & =& \prod_{ {v\in P(u,w)}\atop{ v\neq u}} |\d_v(R_u)|
\prod_{v\notin P(u,w)} |\d_v(R_u)|\nonumber\\
&=& 
\prod_{ {v\in P(u,w)}\atop{ v\neq w}} |\d_v(R_w)|
\prod_{v\notin P(u,w)} |\d_v(R_w)| = \m(w)
\label{6.58}
\eeqa
which proves the independency of $\m$ from points in $R$.
Next, observe that to prove the independence of $\n$ from 
points in $R$ it is enough to check that $\n(w)=\n(w')$
for {\em adjacent points} $w$ and $w'$. Thus, let $w$, $w'$
be adjacent points in $R$. Then
\beqa
\n(w)-\n(w') &=& \sum_{ {u\in S}\atop{u\neq w,w'}} 
\a_{ui} \Big[ \sum_{ {v\in P(u,w)}\atop{v\neq u}} 
\d_v(R_u)^{-1}-
\sum_{ {v\in P(u,w')}\atop{v\neq u}} 
\d_v(R_u)^{-1}\Big]\ +\nonumber\\
&&\qquad + \chi_{{}_S}(w') \a_{w' i} \d_w(R_{w'})^{-1} -
\chi_{{}_S}(w) \a_{wi} \d_{w'}(R_{w})^{-1}\nonumber\\
&&\phantom{a}\nonumber\\
&=& 
\sum_{ {u\in S}\atop{u\neq w,w'}} 
\a_{ui} \d_w(R_{w'})^{-1}+
\chi_{{}_S}(w') \a_{w' i} \d_w(R_{w'})^{-1} +\nonumber\\
&&\qquad +
\chi_{{}_S}(w) \a_{wi} \d_{w}(R_{w'})^{-1}\nonumber\\
&&\phantom{a}\nonumber\\
&=& \Big( \sum_{u\in S} \a_{ui}\Big)\  \d_w(R_{w'})^{-1}=0
\label{6.59} 
\eeqa
where in the second equality we used $\d_{w'}(R_w)=-\d_w(R_{w'})$
which is a particular case of \equ{6.57} and 
$\chi_{{}_S}$ is the characteristic function of the set $S$.
This finishes the proof of the claim \equ{6.55}.

\nin
The check of \equ{6.52} is now trivial:
\beqano
\s(0) &=& \sum_{u,w\in R} \a_{ui} \a_{wj}
\prod_{ {v\in R}\atop{v\neq u}} \d_v(R_u)^{-2} \\
&=& \m_R^{-2} \sum_{u,w\in R} \a_{ui} \a_{wj}=0
\eeqano
and
\beqano
\frac{d\s}{dx}(0) &=& -2 \sum_{{u,w\in R}\atop{u\neq w}} 
\a_{ui} \a_{wj}
\prod_{ {v\in R}\atop{v\neq u}} \d_v(R_u)^{-2} 
\sum_{ {v\in P(u,w)}\atop{v\neq u}} \d_v(R_u)^{-1}\\
&=& -2 \ \m_R^{-2} \sum_{w\in R} \a_{wj} \Big(
\sum_{u\neq w} \a_{ui} \sum_{ {v\in P(u,w)}\atop{v\neq u}}\d_v(R_u)^{-1}
\Big) \\
&=& -2 \m_R^{-2}\ \n_{R,R}\ \sum_{w\in R} \a_{wj}=0
\eeqano
finishing the proof of Proposition~\ref{pro:comp}. \qed

\rem{rem:comp} In fact, from the above proof it follows 
that \equ{6.52} holds also if the sum over $R$ is replaced
by the sum over any null subset of $R$.
\erem
%
We can now proceed with the Proof of Lemma~\ref{lem:3}.

\giu
Since $\a(R)=0$ we can rewrite the left hand side of
\equ{e.3} as follows
\beqa
\sum_{u,w\in R} \a_{ui} \a_{wj} \prod_R \d_v(R_u^w)^{-2}
& =& \gl{n}^{-2}
\sum_{u,w\in R} \a_{ui} \a_{wj} \prod_{ {v\in R}\atop
{v\neq u}}  \d_v(R_u^w)^{-2}
\nonumber\\
&\equiv & \gl{n}^{-2} \s(\gl{n})
\label{6.60}
\eeqa
see \equ{6.53}. By Proposition~\ref{pro:comp} we see that
\beqa
\s(x) & =& x^2\ \int_0^1 \s''(tx) (1-t)\ dt \nonumber\\
&\equiv & x^2 \bs(x)
\label{6.61}
\eeqa
where $\bs$ is defined here. By assumption we have
\beq
\agl{n}\le \bl \ \D \= \bl \D(R)
\label{6.62}
\eeq
and we see that $\s$ {\em is holomorphic and bounded} in the 
complex disk $\{x\in\complex: |x|\le \frac{1+\bl}{2}\ \D\}$.
Recall the {\em ``Cauchy estimate"}:
\beq
\sup_{D'} |g^{(k)}|\le \ k!\ r^{-k} \sup_D |g|\ ,
\qquad r\={\rm dist} \{D',\dpr D\}
\label{cauchy}
\eeq
valid for any holomorphic function $g$ bounded in a complex domain
$D$, for any $k\ge 0$ and for any subdomain $D'$ whose
closure is contained in $D$ (above $\dpr$ denotes ``boundary 
of")\footnote{The proof of \equ{cauchy} is standard: it follows immediately
by expressing the $k^{\rm th}$ derivative of $g$ at a point $x\in D'$
in terms of Cauchy's integral formula (taking as path of integration
a disk centered at $x$ and of radius $r$).}.
Then, letting
\beq
D\=\{x\in \complex:\ |x|\le \frac{1+\bl}{2}\ \D\}\ ,\quad
D'\=\{x\in \complex:\ |x|\le \bl\ \D\}\ 
\label{6.disk}
\eeq
(recall that $\bl<1$ so that $D'$ is smaller that $D$)
we see that
\beq
\sup_{D'} |\s''| \le 8 \ (1-\bl)^{-2}\ \D^{-2}\ \sup_D |\s|
\label{6.63}
\eeq
Furthermore, for any $x\in D$ and any $u,v\in R$ we have
(recall that from the definition of $\D(R)$ it follows that
$\D\le \d_v(R_u)$).
\beqa
\Big( \d_v(R_u)+x\Big)^{-2} &\le & 
\Big( \d_v(R_u) - \frac{1+\bl}{2}\ \D \Big)^{-2} \nonumber\\
&\le & 4 (1-\bl)^{-2} \ \d_v(R_u)^{-2}
\label{6.64}
\eeqa
Thus, by \equ{6.61}, \equ{6.62}, \equ{6.63}, \equ{6.64},
\equ{6.51} and Lemma~\ref{lem:2}
\beqa
\gl{n}^{-2} |\s(\gl{n})| &=&
|\bs(\gl{n})|\le \frac{1}{2} \sup_{D'} |\s''|\nonumber\\
&\le & 4 (1-\bl)^{-2}\ \D^{-2}\ \sup_D |\s|\nonumber\\
&\le & \Big(4 (1-\bl)^{-2}\Big)^{|V(R)|} \D^{-2}\ 
\sum_{u,w\in R} |\a_u|\ |\a_w|\prod_{v\neq u}
|\d_v(R_u)|^{-2}\nonumber\\
&\le & \Big(4 (1-\bl)^{-2}\Big)^{|V(R)|} \D^{-2}\ 
\Big( |V(R)|\ \prod_{v\in R} |\a_v|\Big)^2
\ c_2^{2(|V(R)|-1)}\ \prod_{ {v\in R}\atop{v\neq u}} |\a_v|^{2\b_2}
\nonumber\\
&\le & \Big( (1-\bl)^{-2}\ 2^{\t+1}\ c_2\Big)^{2|V(R)|} \ \prod_{v\in R}
|\a_v|^{2 (\b_2+\t+1)}
\label{6.65}
\eeqa
where in the last estimate we have applied Lemma~\ref{lem:2} to the tree(s) 
$R\bks \{u\}$ (if $\deg_{R_u} u>2$ then $R\bks \{u\}$ is the disjoint
union of $\deg_{R_u}-1$ trees) and the estimate
\beq
\D^{-1}\le \g\ \big( \sum_R |\a_v|\big)^\t \le \g\ 2^{(|V(R)|-1)\t} 
\prod_R |\a_v|^\t
\eeq
The proof of Lemma~\ref{lem:3} is complete. \qed

\subsection{Proof of Lemma {\bf 6.4}} %lem:4
\label{subsec:5}
%
If $T'\in \cF(T)$, denote by
\beq
\G(T')\=\{vv'\in E(T'):\ \exists\ R\in \cR(T)\ \ {\rm with}
\ \ v'\in\bR \ {\rm and}\ v\notin R\}
\label{6.66}
\eeq
and by $E(\bcR)\=\cup_{\bR\in\bcR} E(\bR)$. Then
\beq
\prod_{vv'\in E(T')} \a_v\cdot\a_{v'} =
\prod_{vv'\in \G(T')} \a_v\cdot\a_{v'}  \ 
\prod_{vv'\in E(\bcR)\cup \bT} \a_v\cdot\a_{v'}
\label{6.67}
\eeq
and the second product does not depend on $T'$
(\ie it is common to all elements of $\cF$).
Furthermore, recalling \equ{defcF}, we see that
\beq
\prod_{vv'\in \G(T')} \a_v\cdot\a_{v'}=
\prod_{C=(\bR_1,...,\bR_s)\in\cC}
\a_{u(C)} \cdot \a_{\bu_1}\ \a_{w(C)}\cdot \a_{\bw_s}
\ \prod_{i=1}^{s-1} \a_{\bw_i}\cdot\a_{\bu_{i+1}}
\label{6.68}
\eeq
last product being absent if $s=1$. Fixing a set of indices
(depending upon $C$ and taking the values $1,...,N$), 
$j_i=j_i(C)$, for $i=0,...,s$, we can make more explicit
\equ{6.67} by writing out the scalar products:
\beq
\prod_{vv'\in \G(T')} \a_v\cdot\a_{v'} =
\sum_{ { \{j_0,...,j_s\}_{C\in\cC}}\atop{1\le j_i\le N}} 
\prod_{C\in\cC}
\a_{u(C)j_0} \a_{w(C)j_s}\ 
\prod_{C\in\cC}
\ \prod_{i=1}^{s} \a_{\bu_i j_{i-1} }\a_{\bw_i j_i}
\label{6.69}
\eeq
Now observe that $|\bcR|\le (|V|-1)/2$, which implies
\beq
\sum_{ \{j_o,...,j_s\}_{C\in\cC}} 1 \le N^{|V|}\ ,
\label{6.70}
\eeq
and notice that, for all $T'\in\cF$ (recall \equ{defdegF})
\beq
\Big| \prod_{vv'\in E(T')} \a_v\cdot\a_{v'}\Big|
\le \prod_{v\in V} |\a_v|^{\deg_{T'} v} \le
\prod_{v\in V} |\a_v|^{\deg_{\cF} v}
\label{6.71}
\eeq
Then
\beqa
&& \Big| 
\sum_{T'\in\cF} \prod_{vv'\in E(T')} \a_v\cdot\a_{v'} \prod_V
\d_v^{-2} \Big|\nonumber\\
&&\quad \le 
\prod_{vv'\in E(\bcR)\cup E(\bT)} |\a_v| \ |\a_v'|\ 
\sum_{ \{j_0,...,j_s\} }\prod_{C\in \cC} |\a_{u(C) j_0}|\ 
|\a_{w(C) j_s} | \ \times\nonumber\\
&&\quad\qquad \times 
\prod_{\bR\in\bcR} \Big| \sum_{\bu,\bw\in\bR} \a_{\bu i_0} \a_{\bw i_0'}
\prod_{v\in T'} \d_v(T')^{-2}\Big|
\nonumber\\
&&\quad \le
\prod_V |\a_v|^{\deg_\cF v} \ N^{|V|}\ 
\sup_{ {T'\in \cF}\atop{1\le i(\bR),i'(\bR)\le N}} 
\Big| \sum_{\bu,\bw\in\bR} \a_{\bu i} \a_{\bw i'}
\prod_V \d_v(T')^{-2}\Big|
\label{6.72}
\eeqa
where the supremum is taken over all choices of the 
indices $\{i(\bR)$, $i'(\bR)\}_{\bR\in\bcR}$
and $i_0,i_0'$ coincide with suitable indices $j$'s.
Fix $T'\in\cF$, fix indices $i\=i(\bR)$ and $i'\=i'(\bR)$ 
($1\le i,j\le N$) and let $R_*$ be a {\em minimal critical
(sub)resonance}: \ie either $R_*\=R_0\in\cR_0$ 
is a critical resonance which
does not contain any critical subresonance or $R_*$ is the 
smallest element
of a hierarchy $\cH_\l(R_0)$ for some $R_0\in\cR_0$:
$\cH_\l(R_0)=\{R_1,...,R_h\}$ and $R_*=R_h$.
Now, observing that
\beq
\bT=\overline{T'/R_*}\ ,\qquad
\bcR(T'/R_*)\=\bcR\bks\{R_*\}
\label{6.73}
\eeq
we have
\beqa
&& \prod_{R\in\bcR(T')} \sum_{\bu,\bw\in \bcR}
\a_{\bu i} \a_{\bw i'} \prod_{v\in T'} \d_v(T')^{-2}\nonumber\\
&& \qquad = \Big( \prod_{R\in\bcR(T'/R_*)} \sum_{\bu,\bw\in \bcR}
\a_{\bu i} \a_{\bw i'} \prod_{v\in T'} \d_v(T'/R_*)^{-2}\Big)
\Big(\sum_{\bu,\bw\in R_*}
\a_{\bu i} \a_{\bw i'} \prod_{v\in R_*} \d_v(T')^{-2}\Big)
\nonumber\\
&&\phantom{aa}
\label{6.74}
\eeqa
If $h>0$ (\ie $R_*$ is a critical subresonance) and if
$m_i$, for $i=0,1,...,h$, are the integer vectors associated
to the hierarchy $\{R_1,...,R_h\}$ (see Remark~\ref{5.3}
of Section~\ref{sec:resona}) 
we have for some $\s_h=\pm 1$ and some $\s_i=0,\pm 1$,
(for $i=0,...,h-1$)
\beq
m_0\= \sum_{v<R_0} \a_v
=\sum_{i=0}^h \s_i m_i\ ,\qquad (|\s_h|=1)
\label{6.75}
\eeq
so that, by \equ{5.7}, we have
\beq
\agl{m_0} < \frac{\l}{1-\l} \ 
\D(R_*)
\label{6.76}
\eeq
Notice that such a bound holds also in the case $R_*=R_0\in\bcR_0$
(and in fact holds without the factor $(1-\l)^{-1}$).
We can apply Lemma~\ref{lem:3} to $R_*$ with
$\bl\=\l/(1-\l)<1$, obtaining
\beq
\Big| \sum_{\bu,\bw\in R_*} \a_{\bu i} \a_{\bw i'}
\prod_V \d_v(T')^{-2}\Big| \le c_3^{|R_*|} \prod_{v\in R_*} 
|\a_v|^{\b_3}
\label{6.77}
\eeq
Repeating the above procedure to the tree $T'/R_*$ it is clear that 
{\em we can inductively contract all critical resonances}
ending up with the tree $T/\bcR_0$ to which Lemma~\ref{lem:2}
can be applied. Thus Lemma~\ref{lem:4} follows with
\beq
c_4\= N\ \max\{ \ c_3\ ,\ c_2^2 \}\ ,\qquad
\b_4\= \ \max\{ \ \b_3\ , \ 2\b_2+2 \}
\label{6.78}
\eeq
which by \equ{const3} yield \equ{const4}. \qed
%********************************************

%%%%%%%%%%%%%%%%%%%%% appendices::
\appendix


\renewcommand{\theequation}{A.\arabic{equation}}
\section{Combinatorics}
\label{app:combina}
\setcounter{equation}{0}

\giu
Here we give the proofs of Lemma~\ref{lem:3.1}, Corollary~\ref{cor:3.1},
Proposition~\ref{pro:exptree2} and Proposition~\ref{pro:exptree}.

\giu
{\bf Proof of Lemma~\ref{lem:3.1}}

\nin
Proof of (i). 
Denote by  $\tcT^k_0$ the set of labeled (unrooted) trees of order $k$.
Then 
\beq
t_{kj}= k\ \#\{ T\in \tcT^k_0:\ \deg v_k=j-1 \}
\label{a_combina.1}
\eeq
Now, recalling (Appendix~\ref{app:tree})
that given integers $d_i\ge 1$ such that 
$\sum_{i=1}^k d_i=2k-2$, one has
\beq
\#\{ T\in\tcT^k_0\ : \ \deg v_i=d_i\}= \frac{(k-2)!}{ \prod_{i=1}^k
(d_i-1)!}
\label{a_combina.2}
\eeq
we obtain
\beqano
t_{kj} &= & k\ \sum_{T\in \tcT^k_0:\ \deg v_k=j-1} 1 =
k\ \sum_{ {d_k=j-1, d_i\ge 1}\atop{ \sum d_i= 2k -2}}
\frac{(k-2)!}{\prod_{i=1}^k (d_i-1)!}\\
&=& k {k-2\choose j-2} 
\sum_{{s_i\ge 0}\atop{s_1+\cdots +s_{k-1}=k-j}}
\frac{(k-j)!}{\prod_{i=1}^{k-1} s_i!}=
k {k-2\choose j-2} (k-1)^{k-j}
\eeqano
proving (i). \qed

\giu
Proof of (ii). It is just a matter of counting: 
For any choice of $j-1$ trees $T_i\in\cT^{h_i}$ with 
$\sum_{i=1}^{j-1} h_i=k-1$, pick one among $k$ labels
(it will be the label of the root of an element of $\cT^k$)
and choose $h_i$ labels among the $k-1$
labels at your disposal. There are $(\sum h_i)!/(h_1!\cdots h_{j-1}!)$
$=$ $(k-1)!/(h_1!\cdots h_{j-1}!)$ ways of doing such a choice.
Now, we attach the $j-1$ trees $T_i$ according to the rule described
in \equ{3.2} (with $s=j-1$)
so as to form a generic element of $\cT^k$: obviously,
since changing the order in \equ{3.2} give rise to the same tree,
we have to divide by $(j-1)!$. Summing over all possible
choices of $h_i$ and over all possible trees in $\cT^{h_i}$
we obtain (ii). \qed

\giu
(iii) is immediately obtained by summing (ii) over all
possible degrees of the root \ie $j=2,...,k$. \qed

\giu
{\bf Proof of Corollary~\ref{cor:3.1}} is an immediate 
consequence of the argument used to prove (ii) above. \qed

\giu
{\bf Proof of Proposition~\ref{pro:exptree2} }
We prove \equ{exptree2} by induction on $k\ge 1$.
For $k=1$ the claim is trivially true. Let $k\ge 2$ and assume
that \equ{exptree2} holds for $1,...,k-1$. 
Denoting, for $T\in\tcT^h$
\beq
F(T)\=\sum_{\a:T\to \zN} \prod_{v\in V} \phi_{\a_v} 
|\a_v|^{\deg v}
\label{a_combina.3}
\eeq
in view of \equ{3.3} we find
\beqano
g_k &=& \sum_{j=2}^k \frac{1}{(j-1)!}
\sum_{{h_i\ge 1}\atop{h_1+\cdots h_{j-1}=k-1}}
\prod_{i=1}^{k-1} \frac{1}{h_i!} \times\\
&&\qquad\times 
\sum_{T_1\in\cT^{h_1},...,T_{j-1}\in\cT^{h_{j-1}}}
\sum_{n\in\zN} \phi_n|n|^j F(\tT_1)\cdots F(\tT_{j-1})\\
&=& \sum_{j=2}^k \frac{1}{(j-1)!}
\sum_{{h_i\ge 1}\atop{h_1+\cdots h_{j-1}=k-1}}
\prod_{i=1}^{k-1} \frac{1}{h_i!} 
\times\\
&&\qquad \times
\sum_{T_1\in\cT^{h_1},...,T_{j-1}\in\cT^{h_{j-1}}}
\sum_{n\in\zN} F(\tT_1 *\cdots *\tT_{j-1})\\
&=& \frac{1}{k!} \sum_{T\in\cT^k} F(\tT)
\eeqano
Notice that in the second equality we have used the crucial
property of $F$:
\beq
\sum_{n\in\zN} \phi_n|n|^j F(\tT_1)\cdots F(\tT_{j-1})=
F(\tT_1 *\cdots *\tT_{j-1})
\label{a_combina*}
\eeq
This finishes the proof of Proposition~\ref{pro:exptree2}. \qed

\rem{rem:a_combina.1} In fact, it is easy to see from
\equ{exptree2} that
\beq
g_k=\frac{1}{k!} \sum_{n_1,...,n_k} \Big( \prod_{i=1}^k
\phi_{n_i} |n_i| \Big) \big(|n_1|+\cdots|n_k|\big)^{k-1}
\label{a_combina.4}
\eeq
However, a direct (arithmetic) proof of \equ{exptree2},
starting from the explicit expression (A.5),
might not be simpler than the proof presented above.
\erem

\giu
{\bf Proof of Proposition~\ref{pro:exptree} }
Notice that $F_{mn}$ in \equ{exptreeg} satisfies,
for any $\tT_i\in\tcT^{h_i}$, ($i=1,...,j-1$),
\beqa
&& \gl{n}^{-2} \sum_{{n1,...,n_{j-1}}\atop{ n_1+\cdots n_{j-1}=n}}
m\cdot n_j\ f_{n_j}\ F_{n_j n_1}(\tT_1)\cdots 
F_{n_j n_{j-1}}(\tT_{j-1})\nonumber \\
&&\qquad= F_{mn}(\tT_1*\cdots* \tT_{j-1})
\label{a_combina**}
\eeqa
Now, mimic the above proof using (A.6) in place of 
(A.4). \qed
%********************************************

\renewcommand{\theequation}{B.\arabic{equation}}
\section{Trees}
\label{app:tree}
\setcounter{equation}{0}
%

\giu
In this appendix we collect the basic facts from graph theory
that are used in the main text. The material is standard and
can be found in the introductory sections of 
most elementary books on graph theory (see \eg \cite{Ha1} or \cite{Bo}).

\giu
Given a finite set $V$, a graph $G$ on $V$ is a couple $(V,E)$
where $E$ is a subset of {\em unordered} couples of different
elements of $V$. If needed, we specify $V\=V(G)$ and $E\=E(G)$.
One can already start to count: if $k\=|V|$ is the cardinality of $V$,
also called the {\em order} of $G$,
then $0\le|E(G)|\le {k \choose 2}$ ($|E|=0$ $\sse$ $E=\emptyset$).
Elements $v$ of $V$  are called equivalently either
{\em vertices} or {\em points} or {\em nodes}, while
elements of $E$, denoted by $vv'\=v'v$ (as the couple are taken
disregarding the order), are correspondently called
{\em edges} or {\em lines} or {\em branches}.
It is customary to write $v\in G$ in place of the proper 
notation $v\in V(G)$ and, analogously, $vv'\in G$ in place
of $vv'\in E(G)$. 
The edge $vv'$ is said to be {\em incident} with the vertices $v$ and 
$v'$. Two vertices are called {\em adjacent} if $vv'\in E$.
Two edges are {\em adjacent} if they are incident with the same vertex.
The number of edges incident with a vertex $v$ is called the 
{\em degree of $v$} and denoted $\deg v$ or $\deg_G v$ when needed.
A point with degree 1 is called an {\em endpoint} 
(or {\em endvertex}). Clearly, $\sum_{v\in G} \deg v= 2 |E(G)|$.
Standard set theoretic notations are
used in graph theory with the obvious meaning clear from context.
For example: a {\em subgraph} $G'$ of $G$, denoted $G'\subset G$,
is a graph such that $V(G')\subset V(G)$ and such that 
$E(G')$ is a subset 
of edges $vv'$ of $E(G)$ with $v,v'\in V(G')$;
if $G_1$ and $G_2$ are two graphs, their union $G_1\cup G_2$
is always meant as {\em disjoint union} 
($V(G_1\cup G_2)$ $\=$  $V(G_1)\dot\cup V(G_2)$,
$E(G_1\cup G_2)$ $\=$  $E(G_1)\dot\cup E(G_2)$);
if $G'$ is a subgraph of $G$, $G\bks G'$ 
is the graph whose vertices are given by $V(G)\bks V(G')$ and
whose edges are given by $E(G)\bks \{vv':v'\in V(G')\}$
(notice that set of edges subtracted is, in general, 
strictly larger than $E(G')$);  if $v,v'\in G$
(but $vv'\notin G$), $G+vv'$ denotes the graph obtained by including
the edge $vv'$.

\giu
All the above definitions, and in general everything concerning
graphs, are better understood by looking at {\em diagrams}.
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(300,100)
\thicklines
\put(0,20){\begin{picture}(50,80)
\put(25,50){\circle*{3}}
\put(20,40){$u$}
\put(20,10){$G_1$}
\end{picture}}
\put(60,20){\begin{picture}(50,80)
\put(10,50){\circle*{3}}
\put(10,50){\line(1,0){30}}
\put(40,50){\circle*{3}}
\put(10,50){\line(3,4){15}}
\put(25,70){\circle*{3}}
\put(25,70){\line(3,-4){15}}
\put(5,40){$v_1$}
\put(35,40){$v_2$}
\put(30,70){$v_3$}
\put(30,10){$G_2$}
\end{picture}}
\put(120,20){\begin{picture}(90,80)
\put(20,50){\circle*{3}}
\put(20,50){\line(1,0){30}}
\put(50,50){\circle*{3}}
\put(50,50){\line(1,1){20}}
\put(70,70){\circle*{3}}
\put(50,50){\line(1,-1){20}}
\put(70,30){\circle*{3}}
\put(15,40){$w_1$}
\put(42,40){$w_2$}
\put(75,70){$w_3$}
\put(75,30){$w_4$}
\put(50,10){$G_3$}
\end{picture}}
\put(220,20){\begin{picture}(110,80)
\multiput(40,55)(30,0){2}{\circle*{3}}
\multiput(40,25)(30,0){2}{\circle*{3}}
\put(40,25){\line(1,1){30}}
\put(40,55){\line(1,-1){30}}
\put(70,25){\line(0,1){30}}
\put(35,60){$z_2$}
\put(65,60){$z_4$}
\put(28,25){$z_1$}
\put(75,25){$z_3$}
\put(50,10){$G_4$}
\end{picture}}
\parbox{14cm}{\caption{\label{fig:b1} $G = G_1 \cup G_2 \cup G_3 \cup G_4$}}
\end{picture}
\end{center}
\end{figure}
%

%
\nin
The set of vertices of the graph $G$ in Figure~\ref{fig:b1} is given
by $\{u$, $v_1$, $v_2$, $v_3$, $w_1$, $w_2$, $w_3$, $w_4$,  
$z_1$, $z_2$, $z_3$, $z_4\}$, and the set of edges is
$\{ v_1v_3,$ $v_1v_2$, $v_3v_2$, $w_1w_2$, $w_2w_3$,
$w_2w_4$, $z_1z_4$, $z_4z_3$, $z_3z_2\}$. The graph $G$
is {\em disconnected} (see below) and the connected components
are given by the subgraphs $G_1$, $G_2$, $G_3$, $G_4$;
the degree of $u$ is 0 ($\sse$ $u$ is an {\em isolated} point)
the degree of $w_2$ is 3; some endpoints are $w_1$ and $z_2$; 
the lines incident with $z_4$ are $z_4z_1$ and $z_3z_4$;
$z_1$ and $z_4$ are adjacent;the 
graph $G'$ given by $V(G')\=\{v_3,v_2\}$
and $E(G')\=\{ v_3v_2\}$ is a subgraph of $G$; the order
of $G$ is 12 and the number of edges is 9.
Two graphs $G,G'$ (and their corresponding diagrams) are {\em identified}
if there exists a bijection $j$ from $V(G)$ onto $V(G')$ such that
$E(G')=$ $\{j(v)j(v'):$ $vv'\in E(G)\}$; $j$ is called
a {\em graph isomorphism}.
Thus $G_4$ in Figure~\ref{fig:b1} and the graphs depicted in
Figure~\ref{fig:b2} all represent the same graph.
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(305,80)
\thicklines
\multiput(5,50)(100,0){3}{\begin{picture}(100,20)
\put(10,0){\line(1,0){75}}
\multiput(10,0)(25,0){4}{\circle*{3}}
\end{picture}}
\put(5,20){\begin{picture}(100,30)
\put(5,20){$z_1$}
\put(30,20){$z_4$}
\put(55,20){$z_3$}
\put(80,20){$z_2$}
\put(40,0){$G_4'$}
\end{picture}}
\put(105,20){\begin{picture}(100,30)
\put(5,20){$u_1$}
\put(30,20){$u_2$}
\put(55,20){$u_3$}
\put(80,20){$u_4$}
\put(40,0){$G_4''$}
\end{picture}}
\put(245,20){$G_4'''$}
\parbox{14cm}{\caption{\label{fig:b2} Graphs isomorphic to $G_4$}}
\end{picture}
\end{center}
\end{figure}
%

\nin
An isomorphism between $G_4'$ and $G_4''$ is $j(z_1)=u_1$,
$j(z_4)=u_2$, $j(z_3)=u_3$, $j(z_2)=u_4$
(another isomorphism is $j(z_1)=u_4$, $j(z_4)=u_3$, $j(z_3)=u_2$,  
$j(z_2)=u_1$);
notice that graphically $G_4'''$ ({\em no labels})
is a complete description of the graph $G_4$.
Here the ``labels" $z_i$ or $u_i$ are used only for notational convenience 
as the only relevant aspect is the ``topology" of lines and points; below 
we shall introduce instead the concept of {\em labeled trees} where points 
are distinguished by labels attached to them.

\nin
{\em Connectedness} is defined thorough paths: 
A {\em path} $P$ is a graph whose vertices can be given
an order such that if $V(P)=\{v_1,...,v_p\}$ then $E(P)$
is given by $\{v_1v_2,...,v_{p-1}v_p\}$
(if $p=1$, $E(P)=\emptyset$ and the path is {\em trivial}).
The {\em length} of a path is given by its order minus 1
($\=$ number of lines in $P$);
a path $P$ is denoted by $v_1v_2\cdots v_p$.
A {\em closed path} or {\em cycle} is defined as a path but
with $v_1=v_p$. A graph $G$ is {\em connected} if any
two (different) points can be joined by a path in $G$.
$G_4$ in Figure~\ref{fig:b1} (and in Figure~\ref{fig:b2})
is a path.

\giu
A {\em tree} is a connected acyclic (\ie with no cycles)
graph. In Figure~\ref{fig:b1}, $G_1,$ $G_3$ and $G_4$ are trees
while $G_2$ is not a tree (being itself a cycle). 
Equivalent characterizations of trees are the following
(see \eg \cite{Ha1}): (i) {\em $T$ is a tree};
(ii) {\em $T$ is connected and $|E(T)|=|V(T)|-1$}
(as above we set $|\emptyset|=0$); (iii) {\em Every two vertex of $T$ are 
joined by a unique path}.
A {\em subtree} $T'$ of $T$ is a connected subgraph of $T$
(hence $T'$ is also a tree); unless otherwise specified,
if $T$ is a tree, $T'\subset T$ means that $T'$ is a subtree
of $T$.
%

\begin{figure}[hbt]
\begin{center}
\begin{picture}(400,100)
\thicklines
\put(0,20){\begin{picture}(50,80)
\put(25,35){\circle*{3}}
\put(25,70){$k=1$}
\end{picture}}
\put(60,20){\begin{picture}(50,80)
\put(10,35){\circle*{3}}
\put(10,35){\line(1,0){30}}
\put(40,35){\circle*{3}}
\put(10,70){$k=2$}
\end{picture}}
\put(120,20){\begin{picture}(80,80)
\multiput(10,35)(30,0){3}{\circle*{3}}
\put(10,35){\line(1,0){60}}
\put(10,70){$k=3$}
\end{picture}}
\put(210,20){\begin{picture}(110,80)
\multiput(10,35)(30,0){4}{\circle*{3}}
\put(10,35){\line(1,0){90}}
\put(10,70){$k=4$}
\end{picture}}
\put(330,20){\begin{picture}(70,80)
\put(10,35){\circle*{3}}
\put(10,35){\line(1,0){30}}
\put(40,35){\circle*{3}}
\put(40,35){\line(1,1){20}}
\put(60,55){\circle*{3}}
\put(40,35){\line(1,-1){20}}
\put(60,15){\circle*{3}}
\end{picture}}
\parbox{14cm}{\caption{\label{fig:b3} Trees up to order $k=4$}}
\end{picture}
\end{center}
\end{figure}
%

\nin
A {\em rooted tree} is a tree with a distinguished vertex
called the {\em root}. 

\nin
A graph (tree) on a set of {\em distinct} points (or {\em labeled
points} or simply {\em labels}) is called a {\em labeled graph
(tree)}.

\nin
{\em Labeled rooted graphs (trees)} are labeled graphs (trees)
with one distinguished (labeled) vertex.

\nin
A useful way of identifying the root $r$ of a rooted tree $T$ is
to introduce an extra point $\eta\notin V(T)$, called
the ``earth", and to {\em add a new edge}, $\eta r$, in $E(T)$:
Thus for rooted trees it is $|E(T)|=|V(T)|$ and the unique
edge of the form $\eta v$ identifies the root $v$ 
(usually denoted $r$). Consistently, we let the degree of the root $r$
be the number of edges incident with $r$, $\eta r$ {\em included}.
If $T$ is an unrooted tree and $v\in V(T)$ we denote by $T_v$
the rooted tree obtained from $T$ putting the root in $v$
(equivalently, adding the edge $\eta v$): $\deg_{T_v} v=$
$\deg_T v+1$. Notice that for rooted trees of order $k$ it is 
$\sum \deg v=2k-1$.

\giu
We conclude by counting some classes of trees. Denote by
\beqa
& \cT^k\=\{ {\rm \ labeled\ rooted\ trees\ of\ order\ } k\}\ ,\quad
& \cT^k_0\=\{ {\rm \ labeled 
\ trees\ of\ order\ } k\}\nonumber\\
& \tcT^k\=\{ {\rm \ rooted\ trees\ of\ order\ } k\}\ ,\quad
\phantom{\ labeled}
& \tcT^k_0\=\{ {\rm \ trees\ of\ order\ } k\}
\label{a:1}
\eeqa
and by $t_k,t^{(0)}_k,\tilde t_k, \tilde t_k^{(0)}$
the respective cardinalities. The only trivial relation
among the $t$'s is that $t_k= k t^{(0)}_k$. Less obvious
are the following statements
\beqa
& {\rm given \ }d_i\ge 1\ {\rm such\ that}\ 
\sum d_i=2k-2,\ 
& \#\{T\in\tcT^k:\ \deg_T v_i=d_i\}= 
\frac{(k-2)!}{\prod_{i=1}^k (d_i-1)!}\nonumber\\
&&\nonumber\\
& {\rm given \ }d_i\ge 1\ {\rm such\ that}\ 
\sum d_i=2k-1,\ 
& \#\{T\in\cT^k:\ \deg_T v_i=d_i\}= 
\frac{(k-1)!}{\prod_{i=1}^k (d_i-1)!}\nonumber\\
&&\nonumber\\
& t_k\= \# \cT^k = k^{k-1} \ ,
& t_k^{(0)}\= \# \cT^k_0 = k^{k-2} 
\label{a:2}
\eeqa
Proofs of these relations can be found in \cite{Bo} (chapter VII,
\S 3).

%
\begin{figure}[hbt]
\begin{center}
\begin{picture}(400,150)
\thicklines
\put(0,20){\begin{picture}(50,130)
\put(25,85){\circle*{3}}
\put(25,85){\circle{6}}
\put(10,120){$k=1$}
\end{picture}}
\put(60,20){\begin{picture}(50,130)
\put(10,85){\circle*{3}}
\put(10,85){\circle{6}}
\put(10,85){\line(1,0){30}}
\put(40,85){\circle*{3}}
\put(10,120){$k=2$}
\end{picture}}
\put(120,20){\begin{picture}(80,130)
\multiput(0,35)(0,30){2}{\begin{picture}(80,30)
\multiput(10,20)(30,0){3}{\circle*{3}}
\put(10,20){\line(1,0){60}}
\end{picture}}
\put(40,55){\circle{6}}
\put(10,85){\circle{6}}
\put(10,120){$k=3$}
\end{picture}}
\put(210,20){\begin{picture}(110,130)
\multiput(0,35)(0,30){2}{\begin{picture}(110,30)
\multiput(10,20)(30,0){4}{\circle*{3}}
\put(10,20){\line(1,0){90}}
\end{picture}}
\put(40,55){\circle{6}}
\put(10,85){\circle{6}}
\put(10,120){$k=4$}
\end{picture}}
\put(330,20){\begin{picture}(70,130)
\multiput(0,15)(0,50){2}{\begin{picture}(70,50)
\put(10,20){\circle*{3}}
\put(10,20){\line(1,0){30}}
\put(40,20){\circle*{3}}
\put(40,20){\line(1,1){20}}
\put(60,40){\circle*{3}}
\put(40,20){\line(1,-1){20}}
\put(60,0){\circle*{3}}
\end{picture}}
\put(40,35){\circle{6}}
\put(10,85){\circle{6}}
\end{picture}}
\parbox{14cm}{\caption{\label{fig:b4} Rooted trees up to order $k=4$}}
\end{picture}
\end{center}
\end{figure}
%

%
\begin{figure}[hbt]
\begin{center}
\begin{picture}(435,160)
\thicklines
\put(0,20){\begin{picture}(30,140)
\put(15,115){\circle*{3}}
\put(10,105){$v_1$}
\put(0,130){$k=1$}
\end{picture}}
\put(40,20){\begin{picture}(40,140)
\put(10,115){\circle*{3}}
\put(5,105){$v_1$}
\put(10,115){\line(1,0){20}}
\put(30,115){\circle*{3}}
\put(25,105){$v_2$}
\put(5,130){$k=2$}
\end{picture}}
\put(90,20){\begin{picture}(50,140)
\multiput(0,35)(0,30){3}{\begin{picture}(50,30)
\multiput(10,20)(15,0){3}{\circle*{3}}
\put(10,20){\line(1,0){30}}
\end{picture}}
\put(0,35){\begin{picture}(50,30)
\put(5,10){$v_2$}
\put(20,10){$v_1$}
\put(35,10){$v_3$}
\end{picture}}
\put(0,65){\begin{picture}(50,30)
\put(5,10){$v_1$}
\put(20,10){$v_3$}
\put(35,10){$v_2$}
\end{picture}}
\put(0,95){\begin{picture}(50,30)
\put(5,10){$v_1$}
\put(20,10){$v_2$}
\put(35,10){$v_3$}
\end{picture}}
\put(10,130){$k=3$}
\end{picture}}
\multiput(150,20)(65,0){3}{\begin{picture}(65,140)
\multiput(0,5)(0,30){4}{\begin{picture}(65,30)
\multiput(10,20)(15,0){4}{\circle*{3}}
\put(10,20){\line(1,0){45}}
\end{picture}}
\end{picture}}
\put(150,115){\begin{picture}(65,30)
\put(5,10){$v_1$}
\put(20,10){$v_2$}
\put(35,10){$v_3$}
\put(50,10){$v_4$}
\end{picture}}
\put(150,85){\begin{picture}(65,30)
\put(5,10){$v_1$}
\put(20,10){$v_2$}
\put(35,10){$v_4$}
\put(50,10){$v_3$}
\end{picture}}
\put(150,55){\begin{picture}(65,30)
\put(5,10){$v_1$}
\put(20,10){$v_3$}
\put(35,10){$v_2$}
\put(50,10){$v_4$}
\end{picture}}
\put(150,25){\begin{picture}(65,30)
\put(5,10){$v_1$}
\put(20,10){$v_3$}
\put(35,10){$v_4$}
\put(50,10){$v_2$}
\end{picture}}
\put(215,115){\begin{picture}(65,30)
\put(5,10){$v_1$}
\put(20,10){$v_4$}
\put(35,10){$v_2$}
\put(50,10){$v_3$}
\end{picture}}
\put(215,85){\begin{picture}(65,30)
\put(5,10){$v_1$}
\put(20,10){$v_4$}
\put(35,10){$v_3$}
\put(50,10){$v_2$}
\end{picture}}
\put(215,55){\begin{picture}(65,30)
\put(5,10){$v_2$}
\put(20,10){$v_1$}
\put(35,10){$v_3$}
\put(50,10){$v_4$}
\end{picture}}
\put(215,25){\begin{picture}(65,30)
\put(5,10){$v_2$}
\put(20,10){$v_1$}
\put(35,10){$v_4$}
\put(50,10){$v_3$}
\end{picture}}
\put(280,115){\begin{picture}(65,30)
\put(5,10){$v_2$}
\put(20,10){$v_3$}
\put(35,10){$v_1$}
\put(50,10){$v_4$}
\end{picture}}
\put(280,85){\begin{picture}(65,30)
\put(5,10){$v_2$}
\put(20,10){$v_4$}
\put(35,10){$v_1$}
\put(50,10){$v_3$}
\end{picture}}
\put(280,55){\begin{picture}(65,30)
\put(5,10){$v_3$}
\put(20,10){$v_1$}
\put(35,10){$v_2$}
\put(50,10){$v_4$}
\end{picture}}
\put(280,25){\begin{picture}(65,30)
\put(5,10){$v_4$}
\put(20,10){$v_1$}
\put(35,10){$v_2$}
\put(50,10){$v_3$}
\end{picture}}
\put(160,150){$k=4$}
\multiput(350,20)(45,0){2}{\begin{picture}(45,140)
\multiput(0,45)(0,40){2}{\begin{picture}(45,40)
\put(10,20){\circle*{3}}
\put(10,20){\line(1,0){15}}
\put(25,20){\circle*{3}}
\put(25,20){\line(1,1){10}}
\put(35,30){\circle*{3}}
\put(25,20){\line(1,-1){10}}
\put(35,10){\circle*{3}}
\end{picture}}
\end{picture}}
\put(350,65){\begin{picture}(45,40)
\put(5,10){$v_1$}
\put(17,10){$v_2$}
\put(35,20){$v_3$}
\put(35,0){$v_4$}
\end{picture}}
\put(350,105){\begin{picture}(45,40)
\put(5,10){$v_2$}
\put(17,10){$v_1$}
\put(35,20){$v_3$}
\put(35,0){$v_4$}
\end{picture}}
\put(395,65){\begin{picture}(45,40)
\put(5,10){$v_1$}
\put(17,10){$v_4$}
\put(35,20){$v_2$}
\put(35,0){$v_3$}
\end{picture}}
\put(395,105){\begin{picture}(45,40)
\put(5,10){$v_1$}
\put(17,10){$v_3$}
\put(35,20){$v_2$}
\put(35,0){$v_4$}
\end{picture}}
\parbox{14cm}{\caption{\label{fig:b5} Labeled trees on \{$v_1,...,v_k$\}, for 
$k=1,...,4$}}
\end{picture}
\end{center}
\end{figure}
%

%
\begin{figure}[hbt]
\begin{center}
\begin{picture}(430,200)
\thicklines
\put(0,20){\begin{picture}(30,180)
\put(15,160){\circle*{3}}
\put(15,160){\circle{6}}
\put(10,150){$v_1$}
\put(15,0){${}^{1}$}
\put(0,170){$k=1$}
\end{picture}}
\put(40,20){\begin{picture}(40,180)
\multiput(0,110)(0,30){2}{\begin{picture}(40,30)
\multiput(10,20)(20,0){2}{\circle*{3}}
\put(10,20){\circle{6}}
\put(10,20){\line(1,0){20}}
\end{picture}}
\put(0,140){\begin{picture}(40,30)
\put(5,10){$v_1$}
\put(25,10){$v_2$}
\end{picture}}
\put(0,110){\begin{picture}(40,30)
\put(5,10){$v_2$}
\put(25,10){$v_1$}
\end{picture}}
\put(25,0){${}^{2}$}
\put(10,170){$k=2$}
\end{picture}}
\put(90,20){\begin{picture}(50,180)
\multiput(0,20)(0,30){5}{\begin{picture}(50,30)
\multiput(10,20)(15,0){3}{\circle*{3}}
\put(10,20){\circle{6}}
\put(10,20){\line(1,0){30}}
\end{picture}}
\put(0,140){\begin{picture}(50,30)
\put(5,10){$v_1$}
\put(20,10){$v_2$}
\put(35,10){$v_3$}
\end{picture}}
\put(0,110){\begin{picture}(50,30)
\put(5,10){$v_1$}
\put(20,10){$v_3$}
\put(35,10){$v_2$}
\end{picture}}
\put(0,80){\begin{picture}(50,30)
\put(5,10){$v_2$}
\put(20,10){$v_1$}
\put(35,10){$v_3$}
\end{picture}}
\put(0,50){\begin{picture}(50,30)
\put(5,10){$v_2$}
\put(20,10){$v_3$}
\put(35,10){$v_1$}
\end{picture}}
\put(0,20){\begin{picture}(50,30)
\put(5,10){$v_3$}
\put(20,10){$v_1$}
\put(35,10){$v_2$}
\end{picture}}
\put(50,0){${}^{9}$}
\put(10,170){$k=3$}
\end{picture}}
\put(140,20){\begin{picture}(50,170)
\multiput(0,50)(0,30){3}{\begin{picture}(50,30)
\multiput(10,20)(15,0){3}{\circle*{3}}
\put(25,20){\circle{6}}
\put(10,20){\line(1,0){30}}
\end{picture}}
\put(0,140){\begin{picture}(50,30)
\multiput(10,20)(15,0){3}{\circle*{3}}
\put(10,20){\circle{6}}
\put(10,20){\line(1,0){30}}
\end{picture}}
\put(0,140){\begin{picture}(50,30)
\put(5,10){$v_3$}
\put(20,10){$v_2$}
\put(35,10){$v_1$}
\end{picture}}
\put(0,110){\begin{picture}(50,30)
\put(5,10){$v_2$}
\put(20,10){$v_1$}
\put(35,10){$v_3$}
\end{picture}}
\put(0,80){\begin{picture}(50,30)
\put(5,10){$v_1$}
\put(20,10){$v_2$}
\put(35,10){$v_3$}
\end{picture}}
\put(0,50){\begin{picture}(50,30)
\put(5,10){$v_1$}
\put(20,10){$v_3$}
\put(35,10){$v_2$}
\end{picture}}
\end{picture}}
\multiput(200,20)(65,0){2}{\begin{picture}(65,170)
\multiput(0,20)(0,30){2}{\begin{picture}(65,30)
\multiput(10,20)(15,0){4}{\circle*{3}}
\put(10,20){\line(1,0){45}}
\end{picture}}
\put(0,80){\begin{picture}(65,30)
\multiput(32.5,0)(0,6){5}{\circle*{2}}
\end{picture}}
\multiput(0,110)(0,30){2}{\begin{picture}(65,30)
\multiput(10,20)(15,0){4}{\circle*{3}}
\put(10,20){\line(1,0){45}}
\end{picture}}
\put(25,0){${}^{24}$}
\end{picture}}
\put(200,160){\begin{picture}(65,30)
\put(10,20){\circle{6}}
\put(5,10){$v_1$}
\put(20,10){$v_2$}
\put(35,10){$v_3$}
\put(50,10){$v_4$}
\end{picture}}
\put(200,130){\begin{picture}(65,30)
\put(10,20){\circle{6}}
\put(5,10){$v_1$}
\put(20,10){$v_2$}
\put(35,10){$v_4$}
\put(50,10){$v_3$}
\end{picture}}
\put(200,70){\begin{picture}(65,30)
\put(10,20){\circle{6}}
\put(5,10){$v_4$}
\put(20,10){$v_3$}
\put(35,10){$v_1$}
\put(50,10){$v_2$}
\end{picture}}
\put(200,40){\begin{picture}(65,30)
\put(10,20){\circle{6}}
\put(5,10){$v_4$}
\put(20,10){$v_3$}
\put(35,10){$v_2$}
\put(50,10){$v_1$}
\end{picture}}
\put(265,160){\begin{picture}(65,30)
\put(25,20){\circle{6}}
\put(5,10){$v_2$}
\put(20,10){$v_1$}
\put(35,10){$v_3$}
\put(50,10){$v_4$}
\end{picture}}
\put(265,130){\begin{picture}(65,30)
\put(25,20){\circle{6}}
\put(5,10){$v_2$}
\put(20,10){$v_1$}
\put(35,10){$v_4$}
\put(50,10){$v_3$}
\end{picture}}
\put(265,70){\begin{picture}(65,30)
\put(25,20){\circle{6}}
\put(5,10){$v_3$}
\put(20,10){$v_4$}
\put(35,10){$v_1$}
\put(50,10){$v_2$}
\end{picture}}
\put(265,40){\begin{picture}(65,30)
\put(25,20){\circle{6}}
\put(5,10){$v_3$}
\put(20,10){$v_4$}
\put(35,10){$v_2$}
\put(50,10){$v_1$}
\end{picture}}
\put(210,190){$k=4$}
\put(335,20){\begin{picture}(45,180)
\multiput(0,90)(0,40){2}{\begin{picture}(45,40)
\put(10,20){\circle*{3}}
\put(10,20){\circle{6}}
\put(10,20){\line(1,0){15}}
\put(25,20){\circle*{3}}
\put(25,20){\line(1,1){10}}
\put(35,30){\circle*{3}}
\put(25,20){\line(1,-1){10}}
\put(35,10){\circle*{3}}
\end{picture}}
\put(0,60){\begin{picture}(45,30)
\multiput(22.5,0)(0,6){5}{\circle*{2}}
\end{picture}}
\put(0,20){\begin{picture}(45,40)
\put(10,20){\circle*{3}}
\put(10,20){\circle{6}}
\put(10,20){\line(1,0){15}}
\put(25,20){\circle*{3}}
\put(25,20){\line(1,1){10}}
\put(35,30){\circle*{3}}
\put(25,20){\line(1,-1){10}}
\put(35,10){\circle*{3}}
\end{picture}}
\put(0,130){\begin{picture}(45,40)
\put(5,10){$v_1$}
\put(17,10){$v_2$}
\put(35,20){$v_3$}
\put(35,0){$v_4$}
\end{picture}}
\put(0,90){\begin{picture}(45,40)
\put(5,10){$v_1$}
\put(17,10){$v_3$}
\put(35,20){$v_2$}
\put(35,0){$v_4$}
\end{picture}}
\put(0,20){\begin{picture}(45,40)
\put(5,10){$v_4$}
\put(17,10){$v_3$}
\put(35,20){$v_2$}
\put(35,0){$v_1$}
\end{picture}}
\put(20,0){${}^{12}$}
\end{picture}}
\put(385,20){\begin{picture}(45,170)
\multiput(0,10)(0,40){4}{\begin{picture}(45,40)
\put(10,20){\circle*{3}}
\put(25,20){\circle{6}}
\put(10,20){\line(1,0){15}}
\put(25,20){\circle*{3}}
\put(25,20){\line(1,1){10}}
\put(35,30){\circle*{3}}
\put(25,20){\line(1,-1){10}}
\put(35,10){\circle*{3}}
\end{picture}}
\put(0,130){\begin{picture}(45,40)
\put(5,10){$v_2$}
\put(17,10){$v_1$}
\put(35,20){$v_3$}
\put(35,0){$v_4$}
\end{picture}}
\put(0,90){\begin{picture}(45,40)
\put(5,10){$v_1$}
\put(17,10){$v_2$}
\put(35,20){$v_3$}
\put(35,0){$v_4$}
\end{picture}}
\put(0,50){\begin{picture}(45,40)
\put(5,10){$v_1$}
\put(17,10){$v_3$}
\put(35,20){$v_2$}
\put(35,0){$v_4$}
\end{picture}}
\put(0,10){\begin{picture}(45,40)
\put(5,10){$v_1$}
\put(17,10){$v_4$}
\put(35,20){$v_2$}
\put(35,0){$v_3$}
\end{picture}}
\put(20,0){${}^{4}$}
\end{picture}}
\parbox{14cm}{\caption{\label{fig:b6} Labeled rooted trees on 
\{$v_1,...,v_k$\}, for $k=1,...,4$}}
\end{picture}
\end{center}
\end{figure}
%

%%%%%%%%%%%%%%%%%%% bibliography: 
\newpage

%\newpage
\begin{thebibliography}{99}
%

\bibitem{A1}
Arnold, V.I.: {\em Proof of A.N. Kolmogorov's theorem on the preservation 
of quasi--periodic motions under small perturbation of the Hamiltonian.}
Usp. Mat. Nauk {\bf 18}, No. 5, 13--40 (1963) (Russian); English
trans.: Russ. Math. Surv. {\bf 18}, No. 5, 9--36 (1963).

\bibitem{A2}
Arnold, V.I.: {\em Small denominators and problems of stability of motions 
in classical and celestial mechanics.}
Usp. Mat. Nauk {\bf 18}, No. 6, 91--192 (1963) (Russian); English
trans.: Russ. Math. Surv. {\bf 18}, No. 6, 85--192 (1963).

\bibitem{BC}
Berretti, A.; Chierchia, L.: {\em On the complex analytic
structure of the golden-mean invariant curve for the standard map},
Nonlinearity {\bf 3}, 39-44 (1990).


\bibitem{BCCF}
Berretti, A.; Celletti, A.; Chierchia, L.; Falcolini, C.: {\em
Natural boundaries for area--preserving twist maps},
Journal of Statistical Physics, {\bf 66} 1613--1630 (1992).

\bibitem{Bo}
Bollobas, B.: {\em Graph Theory}, Springer (Graduate text in mathematics: 
63), 1979.

\bibitem{CC}
Celletti, A.; Chierchia, L.: {\em Construction of analytic KAM 
surfaces and effective stability bounds}, Commun. Math.
Phys. {\bf 118}, 119--161 (1988).

\bibitem{CG}
Chierchia, L.; Gallavotti, G.: {\em Drift and Diffusion in phase space},
Preprint, 1--135 (1992),
to appear in Ann. Inst. Henri Poincar\'e (Physique Th\'eorique).

\bibitem{CP}
Chierchia, L.; Perfetti, P.:
{\em Second order Hamiltonian equations on ${\torus}^\infty$ and
almost--periodic solutions}, 
Preprint, 1--30 (1992), 
to appear in Journal of Differential Equations.

\bibitem{E}
Eliasson, L. H.: {\em Absolutely convergent series expansions
for quasi periodic motions}, Reports Department of Math., Univ. of
Stockholm, Sweden, No. 2, 1--31 (1988).

\bibitem{FL}
Falcolini, C.; de la Llave, R.: {\em Numerical calculation of domains of
analyticity for perturbation theories in the presence of small divisors},
Journal of Statistical Physics, {\bf 67} No. 3/4, (1992).

\bibitem{G}
Gallavotti, G.: {\em Twistless KAM tori, quasi flat homoclinic 
intersections, and other cancellations in the perturbation series
of certain completely integrable hamiltonian systems. A review.}
Preprint (1993).

\bibitem{GJ}
Goulden, I. P.; Jackson, D. M.: {\em Combinatorial Enumeration},
Wyley Interscience Series in Discrete Math., 1983.

\bibitem{Ha1}
Harary, F.: {\it Graph Theory}, Addison--Wesley, 1969.

\bibitem{Ko}
Kolmogorov, A. N.: {\em On conservation of conditionally periodic
motions under small perturbations of the Hamiltonian}.
Dokl. Akad. Nauk SSSR {\bf 98}, No. 4, 527--530 (1954).
(Russian).

\bibitem{Mo1}
Moser, J.: {\em On invariant curves of area--preserving mappings of an 
annulus}. Nachr. Akad. Wiss. G\"ott., II. Math.--Phys. Kl 1962,
1--20 (1962).

\bibitem{Mo2}
Moser, J.: {\em Convergent series expansions for quasi--periodic
motions}. Math. Ann. {\bf 169}, 136--176 (1967).

\bibitem{Po}
Poincar\'e, H.: {\em Les m\'ethodes nouvelles de la m\'ecanique c\'eleste}.
Vols. 1--3. Paris: Gauthier--Villars. (1892/1893/1899).

\bibitem{Ru}
R\"ussmann, H.: {\em Kleine Nenner. I: \"Uber invariante Kurven
differenzierbarer Abbildungen eines Kreisringes.} Nachr. Akad.
Wiss. G\"ott., II. Math.--Phys. Kl. 1970,
67--105 (1970).

\bibitem{Sc}
Schmidt, W. M.: {\em Diophantine Approximation}, Lecture Notes in Math.
{\bf 785}, 1980.

\bibitem{S}
Siegel, C. L.: {\em Iterations of analytic functions}, Annals of Math. 
{\bf 43}, No. 4, 607--612 (1942).

\bibitem{V}
Vittot, M.: {\em Lindstedt perturbation series in Hamiltonian
mechanics: explicit formulation via a multidimensional Burmann--Lagrange
formula}, Preprint 1--20 (1991)
%

\end{thebibliography}
\end{document}