\section{Deep Impact Framework}

\boldparagraph{Document Expansion.}
In our approach, we leverage \textsf{DocT5Query}\ document expansion to enrich the original document collection with expansion terms. As noted by \citet{doc2query}, document expansion can be seen as a two-fold approach. By adding terms that are already part of the document, it rewrites their frequencies, similar to \textsf{DeepCT}\xspace. Furthermore, it injects into the passage new terms, originally not part of the document, in order to address the term mismatch problem. We refer to the two as \textit{Rewrite} and \textit{Inject}, respectively.
Table~\ref{tab:dtfq} summarizes
the effect of \textsf{DocT5Query}\ when applied to the MSMARCO passage ranking collection, and isolates the two contributions.
While \textit{Rewrite} alone
achieves stronger MRR@10 than \textit{Inject}, the latter achieves higher recall. Using both significantly outperforms either one on both measures. Indeed, \textit{Inject} is important for capturing additional results, but \textit{Rewrite} is needed to then properly weight the injected terms. However, the comparison of \textit{Rewrite} vs. \textsf{DeepCT}\xspace indicates that \textsf{DocT5Query}\ is still sub-optimal in determining the right frequencies, and resulting impact scores, for the terms.

This motivates our approach, \textsf{DeepImpact}, where we first use the \textit{Inject} step of \textsf{DocT5Query}\ to add new terms, and then directly learn the right impact scores for both old and newly injected terms.

\begin{table}[h]
\renewcommand{\arraystretch}{0.7}
\caption{Different contributions to effectiveness metrics of \textsf{DocT5Query}\ on the MSMARCO passage ranking collection.}
\centering
\begin{tabular}{l ccccc}
\toprule
& \multirow{2}{*}{\textsf{BM25}\xspace} & \multirow{2}{*}{\textsf{DeepCT}\xspace} & \multicolumn{3}{c}{\textsf{DocT5Query}} \\
\cmidrule(lr){4-6}
& &  &\multicolumn{1}{c}{Cumulative} & \multicolumn{1}{c}{\textit{Rewrite}} & \multicolumn{1}{c}{\textit{Inject}}   \\
\midrule
MRR@10 & 0.188 & 0.244 & 0.278 & 0.215 & 0.194 \\
Recall & 0.858 & 0.910 & 0.947 & 0.878 & 0.912 \\
\bottomrule
\end{tabular}
\label{tab:dtfq}
\end{table}

\boldparagraph{Neural Network Architecture.}
\looseness -1 The overall architecture of the \textsf{DeepImpact}\ neural network is depicted in Figure~\ref{fig:architecture}. \textsf{DeepImpact}{} feeds a contextual LM encoder the original document terms (in white) and the injected expansion terms (in gray), separating both by a \texttt{[SEP]} separator token to distinguish both contexts. The LM encoder produces an embedding for each input term. The first occurrence of each \textit{unique} term is provided as input to the impact score encoder, which is a two-layer MLP with ReLU activations. This produces a single-value score for each unique term in the document, representing its impact. Given a query $q$, we model the score of document $d$ as simply the sum of impacts for the intersection of terms in $q$ and $d$.

\begin{figure}
\includegraphics[width=0.7\linewidth]{arch3.pdf}
\caption{Neural network architecture of \textsf{DeepImpact}.}\label{fig:architecture}

\vspace{-3mm}
\end{figure}

\boldparagraph{Network Training.}
We train our model using triples sampled from the official MS-MARCO training dataset, consisting of a query, a relevant passage, and a presumed non-relevant passage per sample. We expand each passage using the \textsf{DocT5Query}\ as discussed.
The model converts each document into a list of scores, corresponding to the document terms matching the query. These scores are then summed up, obtaining an accumulated query-document score. For each triple, two scores for the corresponding two documents are computed. The model is optimized via pairwise softmax cross-entropy loss over the computed scores of the documents.  We use BERT-base as the contextualized language model. Max input text length was set to 160 tokens. Losses are back-propagated through the whole \textsf{DeepImpact}\ neural model with a learning rate of $3 \times 10^{-6}$ with the Adam optimizer. We used batches of 32 triples and train for 100,000 iterations.

\boldparagraph{Impact Scores Computation.}
Following the training phase, \textsf{DeepImpact}\ can leverage the learned term-weighting scheme to predict the semantic importance of each token of the documents without the need
for queries. Each document is represented as a list of term-score pairs, which are converted into an inverted index. The index can then be deployed and searched as usual for efficient query processing. We infer the scores using three digits of precision, and we do not perform any scaling.

\boldparagraph{Quantization and Query Processing.}
In our approach we predict real-valued document-term scores, also called impact scores, that we store in the inverted index. Since storing a floating point value per posting would blow up the space requirements of the inverted index, we decided to store impacts in a quantized form. The quantized impact scores belong to the range of $[1,2^b-1]$, where $b$ is the number of bits used to store each value. We experimented with $b = 8$ using linear quantization, and did not notice any loss in precision w.r.t. the original scores. Since we quantized all the scores in the index in the same way, to compute a query-document score at query processing we can just sum up all the quantized scores of the document terms matching the query. %

\section{Experimental Results}
In this section, we analyze the performance of the proposed method with an extensive experimental evaluation in a realistic and reproducible setting, using state-of-the-art baselines and a standard test collection and query logs.

\boldparagraph{Hardware.}
To evaluate the latency, we use a single core of a machine
with four Intel Xeon Platinum 8268 CPUs and 369 GB of RAM, running Linux 4.18.
To run \textsf{ColBERT}\xspace\ a GPU is required, and we used an NVIDIA RTX8000 with 48GB of memory.

\boldparagraph{Dataset and query logs.}
We conduct our experiments on the MSMARCO passage ranking \cite{msmarco} dataset.
To evaluate query processing effectiveness and efficiency, we compare with existing methods using the \textsf{MSMARCO Dev Queries}\xspace{},\footnote{We have made a submission to the official leaderboard and obtained an MRR@10 of 0.318 on the ``eval'' queries.} and we test all methods on the \textsf{TREC 2019}\xspace{}~\cite{trec2019} and \textsf{TREC 2020}\xspace{}~\cite{trec2020} queries from the TREC Deep Learning passage ranking track.

\boldparagraph{Baselines.}
We perform two different sets of experiments. Our initial experiment aims at comparing the performance of \textsf{DeepImpact}\ as a first-stage ranker, processing queries on inverted indexes but without complex reranking. In this experiment we compare our proposed \textsf{DeepImpact}\ with the classical \textsf{BM25}\xspace\ relevance model over the unmodified collection, and state-of-the-art solutions dealing with inverted indexes, namely \textsf{DeepCT}\xspace, and \textsf{BM25}\xspace\ over a collection expanded with \textsf{DocT5Query}.
We do not compare with \textsf{DeepCT}\xspace\ over the collection expanded with \textsf{DocT5Query}, since that would involve training a new \textsf{DeepCT}\xspace{} model from scratch to learn how to weigh expanded documents.
Our second set of experiments compares \textsf{DeepImpact}\ in a re-ranking setting. First, the top 1000 documents retrieved by \textsf{DeepImpact}\ are re-ranked by \textsf{EPIC}\ and \textsf{ColBERT}\xspace and compared to \textsf{ColBERT}\xspace end-to-end (E2E) where the candidates are generated using ANN search. Finally, we look at first-stage recall and re-ranking-stage MRR@10 when applying \textsf{ColBERT}\xspace\ at several first-stage cutoffs to different candidate generation methods.

\boldparagraph{Implementations.}
We use Anserini~\cite{anserini} to generate the inverted indexes of the collections. We then export the Anserini indexes using the CIFF common index file format \cite{ciff}, and process them with PISA~\cite{pisa} using the MaxScore query processing algorithm~\cite{maxscore}.
We use the \textsf{BM25}\xspace{} scoring method provided by Anserini.
For \textsf{DeepCT}\xspace{}, we  used the source code and data\footnote{\url{https://github.com/jmmackenzie/term-weighting-efficiency}} provided by \citet{deepct-efficiency}.
For \textsf{DocT5Query}{} we use the predicted queries available online\footnote{https://github.com/castorini/docTTTTTquery}, using 40 concatenated predictions for each passage in the corpus, as recommended by \citet{docTTTTTquery}.
We use the \textsf{EPIC}{} implementation in OpenNIR~\cite{onir} and the official pretrained model\footnote{\url{https://github.com/Georgetown-IR-Lab/epic-neural-ir}}.
We use the \textsf{ColBERT}\xspace{} implementation\footnote{\url{https://github.com/stanford-futuredata/ColBERT}} provided by \citet{colbert}, trained for 200k iterations.
Both training and indexing tasks of \textsf{DeepImpact}\ are implemented in Python. After the quantization step, the documents are indexed directly by PISA.
Query processing efficiency is measured using PISA for all baselines. Query processing is performed using MaxScore to retrieve the top $1000$ documents. %
Our source code is publicly available\footnote{\url{https://github.com/DI4IR/SIGIR2021}}.

\boldparagraph{Metrics.}
To measure effectiveness, we use the oﬃcial metrics for each query set, mean reciprocal rank (MRR@10) for MSMARCO queries, and normalised discounted cumulative gain (NDCG@10) as well as mean average precision (MAP) for TREC queries, following~\cite{hofstatter2020local}. We also report recall  on the first stage and MRR@10 on the re-ranking stage at different cutoff values. Finally, we compute the mean response time (MRT) for every query processing strategy, in ms.
We conduct Bonferroni corrected pairwise t-tests, and report significance with $p < 0.05$.

\boldparagraph{Overall comparison.}
Our first experiment aims to show the early-stage effectiveness improvements that \textsf{DeepImpact}\ achieves when compared to prior work.
The results are presented in Table~\ref{tab:overall}, which shows effectiveness and efficiency for the three query logs on MS MARCO. We retrieve the top $1000$ documents for each query, without re-ranking, and report the values of NDCG@10, MRR@10, and MAP, as well as MRT.

\textsf{DeepImpact}\ significantly outperforms all methods and is statistically significantly better than other strategies for all effectiveness metrics on the \textsf{MSMARCO Dev Queries}\xspace. For the \textsf{TREC 2019}\xspace\ and \textsf{TREC 2020}\xspace\ queries, \textsf{DeepImpact}\ is always better than the competitors, with statistically significant improvements on NDCG@10 and MAP in some cases. Statistical significance on the latter two query traces is limited by their relatively small number of queries.

We also see that \textsf{DeepImpact}\ mean response time exceeds the time reported for other methods. We trace this to the query processing strategy: the distribution of scores induced by BM25, used in \textsf{BM25}\xspace, \textsf{DeepCT}\xspace, and \textsf{DocT5Query}\ is exploited more efficiently by the MaxScore algorithm. In contrast, \textsf{DeepImpact}\ learns new scores, whose distribution is not efficiently exploited by MaxScore. We performed additional experiments using disjunctive query processing without optimizations, omitted for space limitations. These experiments show \textsf{DeepImpact}\ to be in line with the speed of the other approaches. Optimizing the query processing speed of \textsf{DeepImpact}{} is an interesting open problem for future research.

\input{figures/effectiveness}

\input{figures/reranking}

\boldparagraph{Re-ranking evaluation.}
Table~\ref{tab:reranking} shows the effect of re-ranking the top $1000$ candidates produced by \textsf{DeepImpact}\ using two complex re-rankers, \textsf{EPIC}\ and \textsf{ColBERT}\xspace. The table also shows, as a comparison, the performance obtained by \textsf{ColBERT}\xspace\ when used end-to-end by employing ANN search as the first-stage retrieval mechanism. \textsf{DeepImpact}\ followed by a \textsf{ColBERT}\xspace\ re-ranker obtains higher effectiveness values than \textsf{ColBERT}\xspace\ {\sf E2E} on all query sets. Moreover, \textsf{DeepImpact}\ + \textsf{ColBERT}\xspace\ exhibits a $4.4\times - 5.1\times$ speedup w.r.t. \textsf{ColBERT}\xspace\ {\sf E2E}.

\boldparagraph{First-stage cutoff evaluation.}
\textsf{DeepImpact}\ is able to achieve statistically significant higher recall than all the compared methods (with one single exception at cutoff 1000). In particular, Table~\ref{table:recall} shows that the gap with the other methods is greater with smaller cutoff values, which reduces the re-ranking cost and thus could enable the use of more complex pairwise ranking models, such as DuoBERT \cite{duobert}. In re-ranking, \textsf{DeepImpact}\ outperforms all other methods at cutoff 10. Moreover, it outperforms \textsf{DeepCT}\xspace on all cutoff values except 1000, and it is comparable with \textsf{DocT5Query}.

\input{figures/recall}

\section{Introduction}
Modern search engines employ complex, machine-learned ranking functions to retrieve the most relevant documents for a query. Recently, the development of pre-trained contextualized language models such as BERT~\cite{devlin2018bert} has resulted in impressive benefits in search effectiveness, at the cost of expensive query processing times, which can make their deployment in production scenarios challenging. \citet{nogueira2019bertranker} and \citet{cedr} showed the superior performance of BERT in term of effectiveness for passage and document re-ranking tasks, respectively, by fine-tuning the pre-trained transformer network to distinguish between relevant and non-relevant query--document pairs.
However, several recent studies~\cite{cedr,Hofsttter2019LetsMR} have shown that this can have very high computational cost, even if re-ranking just the top 1000 results.
Other studies~\cite{epic,prettr,colbert} proposed methods with lower lower computational cost but typically some loss in retrieval quality. BERT's Transformer encoder is composed of many neural layers performing expensive processing to compute the query-document relevance signals. Different solutions have been proposed to address this performance bottleneck, based on the pre-computation of query-document representations produced by BERT. \textsf{EPIC}~\cite{epic} proposes to build on top of BERT a new ranking model trained to generate query and document representations in a given fixed-length vector space, equal to the size of the lexicon. Document representations are pre-computed, while query representations are computed at retrieval time, and then used to obtain a ranking score by computing a similarity between the two representations. %

\textsf{PreTTR}~\cite{prettr} and \textsf{ColBERT}\xspace~\cite{colbert} experimentally show that the query-document interactions in most layers of BERT have little impact on the final effectiveness. This leads them to pre-compute document representations at indexing time, which are used at query processing time to compute the query-document interaction only in a final layer. While \textsf{PreTTR}\ still relies upon a first-stage candidate generation based on BM25, \textsf{ColBERT}\xspace investigates the ability of the pre-computed document representations to identify relevant documents among \textit{all} documents in the index. Due to space/time requirements of the document representation, \textsf{ColBERT}\xspace leverages approximate nearest neighbor (ANN) search applied to dense representations as a first-stage retrieval system, followed by an exact re-ranking stage, while similar approaches using exact nearest neighbor search~\cite{xiong2020approximate} can perform processing in a single stage.

Following a different paradigm, \citet{deepct} investigated the use of the contextual word representations from BERT to generate more effective document term weights for bag-of-words retrieval. \textsf{DeepCT}\xspace~\cite{deepct}, for passages, and  \textsf{HDCT}\xspace~\cite{deepct2}, for documents,  estimate a term's context-specific importance in each passage/document, by projecting each word’s BERT representation into a single term weight. These term weights are then transformed into term frequency-like integer values that can be stored in an inverted index to be used with classical retrieval models. A main limitation of \textsf{DeepCT}\xspace\ that we address in this work is that it is trained as a \textit{per-token regression task}, in which a ground truth term weight for every word is needed, and which does not permit the individual impact scores to co-adapt for the downstream objective of identifying relevant documents. %

By storing new integer values as term frequencies in the inverted index, \textsf{DeepCT}\xspace and \textsf{HDCT}\xspace enrich a document's bag-of-words representation with additional document-level context information, to match queries more accurately. Using a different approach, \citet{docTTTTTquery} propose \textsf{DocT5Query}{}, a document expansion strategy to enrich each document with additional terms able to improve the retrieval effectiveness of documents w.r.t. queries for which they are relevant. \textsf{DocT5Query}{} trains a sequence-to-sequence model to predict queries potentially relevant to a given document, and appends these queries to the documents before indexing. As another way of expanding documents, the very recent {\sf SparTerm}~\cite{bai2020sparterm} method predicts an importance score for every term in the vocabulary and uses a gating mechanism to only keep a sparse subset of those, using them to learn an \textit{end-to-end} score for relevant and non-relevant documents. However, this only increases the MRR@10 of \textsf{DocT5Query}{} from 0.277 to 0.279.

\looseness -1 We propose \textsf{DeepImpact}, a more effective approach for learning a relevance score contribution for term-document pairs that can also be stored in a classical inverted index. \textsf{DeepImpact}{} improves impact-score modeling and tackles the vocabulary-mismatch problem~\cite{zhao2012modeling} between queries and documents. Instead of learning \textit{independent} term-level scores without taking into account the term co-occurrences in the document, as in \textsf{DeepCT}\xspace, or relying on unchanged BM25 scoring, as in \textsf{DocT5Query}, \textsf{DeepImpact}\ directly optimizes the \textit{sum} of query term impacts to maximize the score difference between relevant and non-relevant passages for the query.
In other words, while \textsf{DeepCT}\xspace learns the term frequency component of existing IR models, e.g., BM25, \textit{in this work we aim at learning the final term impact jointly across all query terms occurring in a passage}.
In this way, our proposed model learns richer interaction patterns among the impacts, when compared to training each impact in isolation. To address vocabulary mismatch, \textsf{DeepImpact}\ leverages \textsf{DocT5Query}\ to enrich every document  with new terms likely to occur in queries for which the document is relevant. Using a contextualized language model, it directly estimates the semantic importance of tokens in a document, producing a single-value representation for each token in each document that can be stored in an inverted index for efficient retrieval.
Our experiments show that \textsf{DeepImpact}\ significantly outperforms prior first-stage retrieval approaches by up to $17\%$ on effectiveness metrics w.r.t. \textsf{DocT5Query}. When deployed in a re-ranking scenario, it reaches the same effectiveness as state-of-the-art approaches up to $5.1\times$ faster.

In summary, this paper makes the following contributions:
\vspace{-0.4em}
\begin{itemize}
    \item We propose \textsf{DeepImpact}{}, a more effective scheme for \textit{jointly learning} term impacts over \textit{expanded documents}.
    \item We evaluate \textsf{DeepImpact}{} on the MS MARCO passage ranking task.
    We find that \textsf{DeepImpact}{} can improve ranking effectiveness for passage ranking versus prior first-stage retrieval approaches and is competitive when compared to complex systems based on ANN search, while exhibiting much lower computational costs.
    \item We evaluate \textsf{DeepImpact}\ as a first-stage model in a re-ranking pipeline, and show that this pipeline matches or outperforms strong baseline approaches, while being highly efficient.
\end{itemize}

\section{Conclusions and future work}
In this paper, we introduced \textsf{DeepImpact}, a new first-stage retrieval method that leverages a combination of a traditional inverted indexes and contextualized language models for efficient retrieval. By estimating semantic importance, \textsf{DeepImpact}\ produces a single-value impact score for each tokens of a document collection. Our results show that \textsf{DeepImpact}\ outperforms every inverted-index based baseline, in some cases even matching the effectiveness of more complex neural retrieval approaches such as \textsf{ColBERT}\xspace. Furthermore, when \textsf{ColBERT}\xspace\ is used to re-rank candidates retrieved by \textsf{DeepImpact}\, instead of approximate nearest neighbor, we find a dramatic reduction of query processing latency, and a more modest improvement in effectiveness of the whole pipeline.
Future work will focus on further enhancing the underlying model. First, we would like to experiment with more relaxed matching conditions, instead of exact match, between the query-document terms. Second, we believe that we could improve further term expansion with more sophisticated techniques. Finally, we plan to investigate how changing the distribution of impact scores affects query processing algorithms such as MaxScore, and how we can address this issue.


\section{Introduction}

Let $A$ be an Abelian variety, endowed with a polarization $L$. (We view polarizations as divisor classes, rather than line bundles.) Let $S$ be a subvariety of $A$, of dimension $n$. The intersection number $$S \cdot L^n = (L|_S)^n$$ can be considered as a geometric degree of $S$, at least when $L$ is a very ample divisor class. If $S$ is an Abelian subvariety of $A$, the geometric form of the Riemann Roch theorem for Abelian varieties says that
$$\frac{(L|_S)^n}{n!} = \chi(L|_S)$$
is the Euler characteristic of the line bundle associated to the restricted polarization.
So, for an Abelian subvariety, the Euler characteristic $\chi(L|_S)$ can be considered as a `reduced degree'. Denote with the symbol ${\sf AS}_A$ the collection of all Abelian subvarieties of $A$. For every positive integer or real number $t$, define $$N_A(t) := \# \big\{ S \in {\sf AS}_A \mbox{ s.t. } \chi(L|_S) \leq t \big\} \smallskip.$$

That this is a finite number was already known to Poincar\'e, at least for the subcollection of subvarieties of dimension $n=1$. The general statement follows from a result of Birkenhake and Lange \cite{BL}, to the effect that the collection of all Abelian subvarieties with bounded exponent in $A$ is finite. In a couple of papers \cite{Gu1},\cite{Gu2} we studied the problem of giving an asymptotic estimate for the finite number of elliptic curves with bounded degree in $A$. The aim of the present work is to show that the method of the previous papers can be adjusted to the general situation. The argument leads to make explicit the relation between the rate of growth of the counting function $N_A(t)$ and the complete decomposition of $A$ up to isogeny into a product of simple Abelian varieties.

Assume that the complete decomposition of $A$ is given by an isogeny
$$A \approx B_1^{k_1} \times \cdots \times B_q^{k_q}$$
where $B_1,\ldots,B_q$ are simple Abelian varieties, each other non-isogenous,
and where $k_1,\ldots,k_q$ are positive integers. Define the integers: $k$, the maximum among the multiplicities $k_j$, and $h$, the maximum rank of an endomorphism group $End(B_j)$.
In terms of these data, we prove the following
\begin{theorem}
\label{T}
There is an asymptotic estimate
$$N_A(t) = O\left(t^{\,q (kh+2)(k-1)}\right).$$
\end{theorem}

The main tools for the argument are: a thorough use of the complete reducibility theorem in the relative version involving a given polarization (cf. \S \ref{reducibility}, especially Proposition \ref{deg-chi}), and a classical result in Number Theory concerning the number of lattice points in a bounded region of Euclidean space (cf. \S \ref{lattice points}). The proof of Theorem \ref{T} is given in the final \S \ref{finale}.

\section{Some remarks about reducibility}
\label{reducibility}

\subsection{Reducibility with respect to a polarization}
\label{RP}
Let $A$ be an Abelian variety, with a polarization $L$. Let $S$ be an Abelian subvariety of $A$. There is in $A$ an Abelian subvariety $S'$ such that
\begin{itemize}
\item
[$-$] $S \cap S'$ is a finite set and $S + S' = A$, so that
the sum map $$s: S \times S' \rightarrow A$$ is an isogeny, and
\item
[$-$] the pullback polarization from $A$ splits as
$$s^\ast (L) = p^\ast (L|_S) + (p')^\ast (L|_{S'})$$
\end{itemize}
where $p,p'$ denote the natural projections of  the product $S \times S'$ to the factors $S,S'$, respectively.
The complementary Abelian subvariety $S'$ is uniquely determined.

\subsection{On the degree of the sum isogeny}
\label{remark}
In the setting of the preceding section, the following holds:
$$\deg(s)\; \chi(L) = \chi(L|_S)\; \chi(L|_{S'}).$$
In fact, one has $\chi(s^\ast(L)) = \deg(s)\, \chi(L)$ (the behavior of the Euler characteristic under an etale finite morphism) and on the other hand $\chi(s^\ast(L)) = \chi(p^\ast (L|_S) + (p')^\ast (L|_{S'})) = \chi(L|_S)\, \chi(L|_{S'})$ (by the K\"unneth formula for the cohomology of shaves). Furthermore, concerning the degree $\deg(s) = \#(S \cap S')$, we point out the following:

\begin{proposition}
\label{deg-chi}
For the degree of the sum isogeny in the reduciblity theorem, one has the upper bound
$$\deg(s) \leq \chi(L|_S)^2.$$
\end{proposition}

\begin{proof}
When $L$ is a principal polarization on $A$, the relation between the types of the induced polarizations $L|_S$ and $L|_{S'}$ is completely understood (see \cite{CAV}, 12.1.5, p. 366). If the type for the smaller dimension is $(d_1,\ldots,d_m)$ then for the higher dimension the type is $(1,\ldots,1,d_1,\ldots,d_m)$. It follows that $\chi(L|_S) = \chi(L|_{S'})$, both equal to the product $d_1 \cdots d_m$, and therefore $\deg(s) = \chi(L|_S)^2$ follows from the equation above, with $\chi(L) = 1$.

If $L$ is an arbitrary polarization, there is an isogeny $g: A \rightarrow B$ onto an Abelian variety $B$ having a principal polarization $M$ such that $L = g^\ast(M)$ (see \cite{CAV}, 4.1.2, p. 71).
If $S$ is an Abelian subvariety of $A$, define $T := g(A)$ and let $d_S$ be the degree of the restriction $g_S: S \rightarrow T$.
One has $\chi(L|_S) = d_S\, \chi(M|_T)$.

Let $T'$ be the complement of $T$ in $B$ with respect to $M$. Then $S'$, the complement of $S$ in $A$ with respect to $L$, coincides with $g^{-1}_{\, 0}(T')$, the connected component of $0$ in the pre-image $g^{-1}(T')$. In order to check this, it is enough to work with the commutative diagram
$$\begin{CD}
S \times g^{-1}_{\, 0}(T') @>{s}>> A \\
@V{\overline{g \times g}}VV @VV{g}V \\
T \times T' @>>{t}> B
\end{CD}$$
where $s,t$ are the sum homomorphisms,
and check that the pullback of $M$
splits on $S \times g^{-1}_{\, 0}(T')$.
We have just seen that
$\#(T \cap T') = \chi(M|_T)^2$ holds since $M$ is a principal polarization.
Then \smallskip
$\#(S \cap S') \leq \#(S \cap g^{-1}(T')) \leq d_S\, \#(T \cap T')
\leq {d_S}^2 \chi(M|_T)^2 = \chi(L|_S)^2$.
\end{proof}

Finally, here is an immediate consequence:
$$\chi(L|_{S'}) \leq \chi(L)\, \chi(L|_S).$$

\subsection{Complete reducibility with respect to a polarization}
\label{CRP}
As a consequence of the reducibility theorem quoted in \S \ref{RP} one has the following theorem of complete reducibility into simple factors.

Let $A$ be an arbitrary Abelian variety, endowed with a polarization $L$. There exist:
\begin{itemize}
\item[$-$]
a sequence of simple Abelian varieties $B_1,\ldots,B_q$, each other non-isogenous,
\item[$-$] a corresponding sequence of positive integers $k_1,\ldots,k_q$,
\item[$-$]
and an isogeny $$s: B_1^{k_1} \times \cdots \times B_q^{k_q} \rightarrow A$$such that the pullback polarization $s^\ast(L)$ splits. \smallskip
\end{itemize}
In general we say that a polarization on a product variety $S_1 \times \cdots \times S_k$ is a split polarization if it is of the form
$$p_1^\ast(L_1) + \cdots + p_k^\ast(L_k)$$
where $L_i$ is a polarization on $S_i$ and $p_i$ is the projection to the $i$th factor.

In the theorem of complete reducibility,
the collection of pairs $(B_j,k_j)$ is determined from $A$ alone, up to isogeny, however the isogeny $s$ that is described above also depends on the polarization $L$.

\subsection{Behavior under isogenies}
\label{bui}

Let $A$ and $B$ be Abelian varieties, and let
$g : B \rightarrow A$ be an isogeny, of degree $d$.
Let $L$ be a polarization on $A$ and consider on $B$ the pullback polarization $g^\ast(L)$.
There is a one to one correspondence
${\sf AS}_A \overset{_\sim}{\longrightarrow} {\sf AS}_B.$
Given $S \subset A$ the corresponding $S^\ast$ in $B$ is
the connected component of $0$ in the pre-image $\varphi^{-1}(S)$.
The restricted isogeny $S^\ast \rightarrow S$ has degree $d_S \leq d$
(in fact a divisor of $d$). With respect to the polarizations one has
$\chi((g^\ast L)|_{S^\ast}) = d_S\, \chi(L|_S)$.
So there is the chain of inequalities
$\chi(L|_S) \leq \chi((g^\ast L)|_{S^\ast}) \leq d\, \chi(L|_S)$.
It follows that the functions counting Abelian subvarieties in $A$ and in $B$
are related by the inequalities
$$N_A(t) \leq N_B(dt) {\rm \ \ \ and \ \ \ } N_B(t) \leq  N_A(t)$$
and therefore one has
$$N_A(t) = O(t^e) \mbox{ \; if and only if \; } N_B(t) = O(t^e).$$

\begin{remark} \label{R} \em
Because of the invariance under isogeny of the asymptotic estimate for the counting function, and because of the complete reducibility theorem with respect to a polarization, in order to prove Theorem \ref{T} it is enough to confine oneself to the case of a product of simple Abelian varieties endowed with a split polarization. This is what we do in the following.
\end{remark}

\section{Bounding homomorphisms}

\subsection{A quadratic form}
Let $A,A'$ be Abelian varities, of dimensions $n,n'$, endowed with polarizations $\Theta,\Theta'$. Consider the function
$$Hom(A,A') \longrightarrow \mathbb Z$$
which is defined by the assignment
$$f \longmapsto \dfrac{\Theta^{n-1}}{(n-1)!} \cdot f^\ast\Theta'.$$
It is known that this is
a quadratic form,
always non-negative.
positive definite if $A$ is simple.
The second and the third assertion are almost apparent, by some intersection theory.
The first assertion for the special case $A = A'$, i.e. for an endomorphism group $End(A)$, can be found for instance in \cite{CAV}, \S 5.1, p. 117; and the general case can be reduced to this special one by embedding the homomorphism group into a suitable endomorphism group in such a way that the function defined above for homomorphisms can be recovered, up to some scalar factor, as the restriction of the analogous function defined for endomorphisms.

\subsection{Homomorphisms in a hyperellipsoid}
Assume now that $A$ is a simple Abelian variety.
Define
$$\Phi(t) := \# \left\{ f \in Hom(A,A') \mbox{ s.t. } \dfrac{\Theta^{n-1}}{(n-1)!} \cdot f^\ast \Theta' \leq t^2 \right\}.$$
Let $H$ be the rank of the homomorphism group $Hom(A,A')$.

\begin{proposition}
\label{ellipsoid}
There is an asymptotic estimate
$$\Phi(t) = O(t^{H}).$$
\end{proposition}

\begin{proof}
Choose an isomorphism $Hom(A,A') \cong \mathbb Z^H$. The quadratic form on $Hom(A,A')$ corresponds to a quadratic form $Q: \mathbb Z^H \rightarrow \mathbb Z$, and this is naturally extended to $\widehat Q: \mathbb R^H \rightarrow \mathbb R$. As the original form is positive definite, then $Q$ is positive definite and so is $\widehat Q$ too. And so we have
$$\Phi(t) = \# \{ x \in \mathbb Z^H \mbox{ s.t. } Q(x) \leq t^2 \}.$$
Now observe that
$\{ x \in \mathbb Z^H \mbox{ s.t. } Q(x) \leq t^2 \}$
can be written as
$$t \cdot \{ y \in \mathbb R^H \mbox{ s.t. }
\widehat Q(y) \leq 1 \}
\cap\, \mathbb Z^H$$
and that
$\{ y \in \mathbb R^H \mbox{ s.t. }
\widehat Q(y) \leq 1 \}$,
a hyperellipsoid, is compact and convex.
So we are lead to a classical topic in Number Theory, the problem of estimating the number of lattice points belonging to a bounded region in the Euclidean space.
Thus the conclusion follows from the general result quoted below.
\end{proof}

\subsection{Lattice points in a bounded region}
\label{lattice points}
Let $K$ be a subset of $\mathbb R^n$, compact convex and with Lipschitz frontier. The function $\# (tK \cap \mathbb Z^n)$ counts the number of points of the lattice $\mathbb Z^n$ which lie in a deformed region $tK$. There is an asymptotic estimate in the form
$\# (tK \cap \mathbb Z^n) = {\rm Vol}(K)\, t^n + O(t^{n-1})$ (see \cite{M}, Ch. 6, Lemma 2, p. 165),
that we only use in the coarse version
$$\# (tK \cap \mathbb Z^n) = O(t^{n}).$$

\section{Subvarieties from homomorphisms}

Let $A$ and $A'$ be Abelian varieties, and consider the product $A \times A'$ with the natural projections $p,p'$. Let $n$ be the dimension of $A$. If $S$ is an Abelian subvariety in $A \times A'$, we denote by $p^{}_S, p'_S$ the two projections restricted to $S$.

\subsection{Parametrization}
\label{parametrization1}
We describe the Abelian subvarieties $S$ such that the projection
$p_S: S \rightarrow A$ is surjective and finite, i.e. an isogeny. Define
$${\sf AS}_{A \times A' / \,p} :=
\Big\{ S \in {\sf AS}_{A \times A'}
\mbox{ s.t. } p{}_S: S \rightarrow A \mbox{ is an isogeny}
\Big\}.$$

So assume that $p_S: S \rightarrow A$ is an isogeny.
Take the inverse, or dual, isogeny $\widehat {p_S} : A \rightarrow S$ and
define the homomorphism $f:A \rightarrow A'$ as $f := {p'_S} \circ \widehat {p^{}_S}$.
Let $a := \deg(p_S)$. Then $\deg(\widehat {p_S}) = a^{2n-1}$
(follows from $p_S \circ \widehat {p_S} = a_A$).
If $\widehat {p_S}$ is viewed as a map $A \rightarrow A \times A'$,
it is given by $x \mapsto (ax,f(x))$. So we can describe
$S$ as the image of some homomorphism
$A \rightarrow A \times A'$ of the form $(a,f)$.

For every integer $a > 0$ and every homomorphism $f: A \rightarrow A'$
we denote by $C_{a,f}$ the image of the homomorphism
$A \rightarrow A \times A'$ given by the pair $(a,f)$, and denote by the same symbol $(a,f)$ the induced homomorphism $A \rightarrow C_{a,f}$.
The condition that $$\deg(a,f) = a^{2n-1}$$ is necessary and sufficient for
the projection $C_{a,f} \rightarrow A$ to be of degree $a$, and
in this case the inverse isogeny $A \rightarrow C_{a,f} \hookrightarrow A \times A'$ is naturally identified to $(a,f)$.
So we have a correspondence
$$\Bigg\{ \mbox{\begin{tabular}{c} $(a,f)
\in \mathbb Z_{>0} \times Hom(A,A')$ \\
s.t. $\deg(a,f) = a^{2n-1}$ \end{tabular}} \Bigg\}  \longrightarrow
{\sf AS}_{A \times A' / \, p}\,.$$
This is a bijective correspondence.
The surjectivity is clear from the discussion above.
Assume that $(a,f)$ and $(a',f')$ determine the same subvariety $C_{a,f} = C_{a',f'}$.
(Taking the degree of the first projection we already have $a=a'$.)
Taking the inverse of the first projection we have $(a,f) = (a',f')$.

\subsection{Degree}
\label{degree1}
Assume that on $A \times A'$ is given a split polarization $L = {p}^\ast\Theta +{p'}{}^\ast\Theta'$.
For a subvariety $S = C_{a,f}$
we now study the degree $S \cdot L^n = (L|_S)^n$, for which we give some estimate from below.

Pulling back to $A$, by means of $\widehat{p _ S} : A \rightarrow S$, we obtain $\widehat{p _ S}^\ast(L|_S)^n = a^{2n-1} (L|_S)^n$. On the other hand, since $\widehat{p _ S}^\ast(L|_S) = a^{\ast}\Theta + f^{\ast}\Theta'$, we have $\widehat{p _ S}^\ast(L|_S)^n = (a^{2}\Theta + f^{\ast}\Theta')^n$. Here we replaced $a^\ast \Theta $ with $a^2\Theta$, in the computation of the intersection number, because $a^{\ast}(\Theta) \equiv \frac{a^{2}+a}{2}\, \Theta + \frac{a^{2}-a}{2}\, (-1)^\ast \Theta$ in $Pic(A)$ (see \cite{CAV}, Proposition 2.3.5, p. 33) and because $\Theta \equiv (-1)^\ast \Theta$ in $H_{2n-2}(A,\mathbb Z)$. It follows that
$$a^{2n-1} (L|_S)^n = (a^{2}\Theta + f^{\ast}\Theta')^n = \sum_{i=0}^{n} \binom{n}{i} a^{2i}\, (\Theta^i \cdot f^\ast {\Theta'}^{n-i}).$$
 \medskip
Furthermore, due to the ampleness of $\Theta$ and $\Theta'$, one has
$$\Theta^i \cdot f^\ast {\Theta'}^{n-i} > 0$$ for $0 \leq i \leq n$ (see \cite{CAV}, Lemma 4.3.2, p. 76).
As a consequence, if we drop from the right hand side all terms except the two with $i = n, n-1$, and then divide by $n!$, we obtain the inequality
$$\chi(L|_S) = \frac{(L|_S)^n}{n!} \geq a\; \dfrac{\Theta^n}{n!} + \dfrac{1}{a}\; \dfrac{\Theta^{n-1}}{(n-1)!} \cdot f^\ast \Theta'.$$

\subsection{On subvarieties of bounded degree $-$ I}
\label{nec}

Assume now that $A$ is a simple Abelian variety.
We study the set
$${\sf AS}_{A \times A' / \,p} :=
\Big\{ S \in {\sf AS}_{A \times A'}
\mbox{ s.t. } p{}_S : S \rightarrow A \mbox{ is an isogeny}
\Big\}$$
and give an asymptotic estimate for the counting function
$$N_{A \times A' / \,p}(t) :=
\# \Big\{ S \in {\sf AS}_{A \times A' / \,p} \mbox{ s.t. } \chi(L|_S) \leq t \Big\}.$$
The estimate is going to be in terms of the quantity
$$H := \mbox{the rank of the group } Hom(A,A').$$

\begin{theorem}
\label{AA'p}
In the present setting, with $A$ simple, one has
$$N_{A \times A' / \,p}(t) = O\left(t^{H+1}\right).$$
\end{theorem}

\begin{proof}
We apply the description in \S \ref{parametrization1}.
The set ${\sf AS}_{A \times A' / \,p}$ is bijective to the set of parameter data
$$\Big\{ (a,f) \in \mathbb Z_{>0} \times Hom(A, A') \mbox{ s.t. } \deg(a,f) = a^{2n-1} \Big\}.$$
Thus $N_{A \times A' / \,p}(t)$ is the number of elements of the set
$$\Big\{ (a,f) \in \mathbb Z_{>0} \times Hom(A, A') \ \mbox{s.t.} \ \deg(a,f) = a^{2n-1} \ \mbox{and} \
\dfrac{\deg C(a,f)}{n!} \leq t \Big\}.$$
Then we consider the description in \S \ref{degree1}.
We have the inequality
$$\frac{\deg C_{a,f}}{n!} \geq a\; \dfrac{\Theta^n}{n!} + \dfrac{1}{a}\; \dfrac{\Theta^{n-1}}{(n-1)!} \cdot f^\ast \Theta'.$$
Hence the codnition $\frac{\deg C_{a,f}}{n!} \leq t$ implies
$$a \leq \dfrac{t}{M} \ \mbox{ and } \
\dfrac{\Theta^{n-1}}{(n-1)!} \cdot f^\ast \Theta' \leq a\, t,$$
where $M := \Theta^n / n!$.
It follows that the set of parameter data above is a subset of the product
$$\Big\{ a \in \mathbb Z \mbox{ s.t. } 1 \leq a \leq \frac{t}{M} \Big\} \times
\Big\{ f \in Hom(A,A') \ \mbox{s.t.} \ \dfrac{\Theta^{n-1}}{(n-1)!} \cdot f^\ast \Theta' \leq \frac{t^2}{M}\Big\}.$$
Since from Proposition \ref{ellipsoid} we know that the cardinality of the set on the right hand side of the product is a function of order $O(t^{H})$,
it follows that $N_{A \times A' / \,p}(t)$
is bounded above by a function of order $O(t)\, O(t^{H})$
as in the statement.
\end{proof}

\section{Subvarieties of a product variety}

Keeping the notation introduced in the preceding section, we extend the description of subvarieties in the product variety $A \times A'$.

\subsection{Parametrization}
\label{parametrization2}
We describe the Abelian subvarieties $S$ of $A \times A'$ such that the projection
$p{}_S: S \rightarrow A$ is surjective.

Define $F:= Ker_0(p_S)$ and view it as an Abelian subvariety of $A'$.
Let $T$ in $S$ be an Abelian subvariety such that
$F + T = S$ and $F \cap T$ is finite. Then the sum map
$s: F \times T \rightarrow S$ is an isogeny, and
the restricted projection $p_T: T \rightarrow A$
is an isogeny too.

Assume that a polarization $L$ is given on $A \times A'$.
Because of the reducibility theorem relative to a given polarization (cfr. \S \ref{RP}),
we can choose $T$ in such a way that
$s^\ast (L|_S) = {q}^\ast (L|_F) + {q'}{}^\ast (L|_{T})$
where $q$ and $q'$ denote the projections
from $F \times T$ to $F$ and $T$, respectively.

We say that two subvarieties $F$ and $T$ in $A \times A'$ are {complementary} with respect to $L$ when the sum map $s: F \times T \rightarrow F + T$ is an isogeny and the pullback polarization $s^\ast (L|_{F + T})$ splits as ${q}^\ast (L|_F) + {q'}^\ast (L|_{T})$.

There is a correspondence
$$\left\{ \mbox{\begin{tabular}{c}
$(F,T) \in {\sf AS}_{A'} \times {\sf AS}_{A \times A' / \, p}$ \\
s.t. complementary w.r.t. $L$
\end{tabular}} \right\} \longrightarrow
\left\{ \mbox{\begin{tabular}{c}
$S \in {\sf AS}_{A \times A'}$  s.t.  \\
$p_S: S \rightarrow A$ surjective
\end{tabular}} \right\}$$
$$\hspace{38pt} (F,T) \hspace{10pt} \longmapsto \hspace{10pt} F + T $$
and this is a bijective correspondence.
That the correspondence is surjective is clear from the construction.
Given $S$, the choice of $F$ is unique, because $Ker(p_S)$
must be equal to $(T \cap F) + F$ and therefore $Ker_0(p_S) = F$.
That the choice of $T$ is then unique is part of the reducibility theorem.

\subsection{Degree}
\label{degree2}
Concerning the (reduced) degree of $S = F + T$ with respect to the polarization $L = p^\ast\Theta + {p'}{}^\ast\Theta'$, i.e. the Euler characteristic $\chi(L|_S)$, we here recall what we know. Define
$$a := \deg(s: F \times T \rightarrow S) = \# (F \cap T) = \deg(p{}_T: T \rightarrow A).$$
From \S \ref{remark} we have the basic facts
$$a\, \chi(L|_S) = \chi(\Theta'|_F)\, \chi(L|_T) \ \ \ \mbox{ and } \ \ \
\chi(L|_T) \leq \chi(L|_S)\, \chi(\Theta'|_F) \hspace{20pt}$$
and from \S \ref{degree1} we take the inequality
$$a M \leq \chi(L|_T)$$
where $M = \chi(\Theta)$, holding because $T$ is of the form $C_{a,f}$ with $a = \deg(p{}_T)$ as above.

\subsection{On subvarieties of bounded degree $-$ II}
Assume now that $A$ is a simple Abelian variety.
\begin{theorem}
\label{AA'}
If $A$ is simple and if $N_{A'}(t) = O(t^E)$ then $N_{A \times A'}(t) = O\left(t^{E+2(H+1)}\right)$.
\end{theorem}
\begin{proof}
Since $A$ is simple, the set ${\sf AS}_{A \times A'}$ is the disjoint union of ${\sf AS}_{A'}$
and the complementary subset which, according to \S \ref{parametrization2},
is bijective to the set of parameter data
$$\Big\{ (F,T) \in {\sf AS}_{A'} \times {\sf AS}_{A / \, p}
\mbox{ \ s.t. $F$ and $T$ are complementary w.r.t. $L$} \Big\}.$$

The basic facts concerning the degree of $S = F + T$ expressed in terms of the degree $a$ of the sum isogeny $F \times T \rightarrow S$ and the degrees of $F$ and $T$ are collected in \S \ref{degree2}. In the present setting we can show that
$$\chi(L|_S) \leq t \ \ \ \mbox{ implies } \ \ \
\chi(\Theta'|_F) \leq t \ \ \mbox{ and } \ \ \chi(L|_T) \leq t^2.$$
We have $a\, \chi(L|_S) = \chi(\Theta'|_F) \chi(L|_T)$. So from $\chi(L|_T) \geq a M$  we obtain $\chi(\Theta'|_F) \leq t/M$ and from $\chi(L|_T) \leq \chi(L|_S) \chi(\Theta'|_F)$ we obtain $\chi(L|_T) \leq t^2/M$.
Note that in the weaker inequalities stated above we dropped the constant $M$, just because it will not affect the exponent in the estimate of the counting function $N_{A \times A'}(t)$.

Summing everything up, we have
$$N_{A \times A'}(t) \leq N_{A'}(t) +
N_{A'}(t) \, {N}_{A \times A' / \, p}(t^2).$$
From Theorem \ref{AA'p} we know that
$${N}_{A \times A'/ \, p}(t^2) = O(t^{2(H+1)}).$$
So, with the hypothesis that $N_{A'}(t) = O(t^E)$, the statement follows.
\end{proof}

\section{Subvarieties of a completely reduced product}
\label{finale}

Let $A = B^k$ be the $k$th self product of a simple Abelian variety $B$, of dimension $n$, endowed with a split polarization $L = p_1^\ast\Theta_1 + \cdots + p_k^\ast\Theta_k$, where each $\Theta_i$ is a polarization on $B$.
The estimate for the counting function $N_{B^k}(t)$ is in terms of
$h$, the rank of the endomorphism group $End(B)$.

\begin{theorem}
\label{B^k}
There is an asymptotic estimate
$$N_{B^k}(t) = O\left(t^{(kh+2)(k-1)}\right).$$
\end{theorem}

\begin{proof}
By induction on $k$. The initial case $k=1$ being obvious, assume $k \geq 2$.
 Write $B^k = B \times B^{k-1}$ and let $p: B^k \rightarrow B$ and $p': B^k \rightarrow B^{k-1}$ be the natural projections, with $p := p_1$ and $p' := (p_2,\ldots,p_k)$. The given polarization on $B^k$ splits as $L = p^\ast \Theta + p'{}^\ast \Theta'$ where $\Theta := \Theta_1$ and where $\Theta'$ is the split polarization on $B^{k-1}$ obtained from $\Theta_2,\ldots,\Theta_k$.

The group $Hom(B,B^{k-1})$ is of rank $H = (k-1)h$.
By the induction hypothesis we have $N_{B^{k-1}}(t) = O(t^{E})$
with $E = \left((k-1)h+2\right)(k-2)$.
From Theorem \ref{AA'}
we have $N_{B^k}(t) = (t^{E + 2(H+1)})$. In the present setting
$E + 2(H+1) = (kh+2)(k-1)$, and the statement is proven.
\end{proof}

Let $A = B_1^{k_1} \times \cdots \times B_q^{k_q}$ be a product of simple Abelian varieties, each occurring with some multiplicity, and assume that $B_i$ and $B_j$ are not isogenous for $i \neq j$.

Each simple Abelian subvariety of $A$ is contained in a unique $B_j^{k_j}$ and is then isogenous to $B_j$.
An arbitrary Abelian subvariety of $A$ may be written as $S = S_1 \times \cdots \times S_q$ where

\begin{tabular}{ccl}
$S_j$ & = & the sum of all simple Abelian subvarieties of $S$ contained in $B_j^{k_j}$ \\ & & (and hence belonging to the isogeny class of $B_j$) \smallskip \\
& = & $S \cap B_j^{k_j}\, .$ \smallskip
\end{tabular} \\
Thus we have a correspondence
$${\sf AS}_{B_1^{k_1}} \times \cdots \times {\sf AS}_{B_q^{k_q}} \longrightarrow {\sf AS}_{A}$$
$$(S_1,\ldots,S_q) \longmapsto S_1 \times \ldots \times S_q$$
and clearly this is a bijective correspondence.

Let $L$ be a split polarization on $A$. It may be written as $L = p_1^\ast(\Theta_1) + \cdots + p_q^\ast(\Theta_q)$ where each $\Theta_j$ is a split polarization on $B_j^{k_j}$. If $S = S_1 \times \ldots \times S_q$ is an Abelian subvariety of $A$, as above, then
(the K\"unneth formula again)
$$\chi(L|_S) = \chi(\Theta_1|_{S_1}) \cdots \chi(\Theta_q|_{S_q}).$$

In the present setting, the estimate for the function $N_A(t)$, and its proof, involve the following data:

\begin{center}
\begin{tabular}{cl}
$h_j$ & the rank of the endomorphism group $End(B_j)$, \smallskip \\
$h$ & the maximum among the ranks $h_1,\ldots,h_q$, \smallskip \\
$k$ & the maximum among the multiplicities $k_1,\ldots,k_q$. \smallskip
\end{tabular}
\end{center}

\begin{theorem}
\label{B1Bq}
There is an asymptotic estimate
$$N_{B_1^{k_1} \times \cdots \times B_q^{k_q}}(t) = O \left(t^{\,q (kh+2)(k-1)} \right).$$
\end{theorem}

\begin{proof}
We have seen that
the set ${\sf AS}_{A}$ is bijective to ${\sf AS}_{B_1^{k_1}} \times \cdots \times {\sf AS}_{B_q^{k_q}}$ and from the expression for $\chi(L|_S)$ above it follows that
$N_A(t) \leq N_{B_1^{k_1}}(t) \cdots N_{B_q^{k_q}}(t)$.
From Theorem \ref{B^k} we have
$N_{B_j^{k_j}}(t) = O\left(t^{(k_jh_j+2)(k_j-1)}\right)$ and therefore
$N_{B_1^{k_1}}(t) \cdots N_{B_q^{k_q}}(t) = O \left(t^{(k_1h_1+2)(k_1-1) + \cdots + (k_qh_q+2)(k_q-1)} \right)$,
and so the statement follows.
\end{proof}

According to Remark \ref{R} the proof of Theorem \ref{T} is now complete.


\section{Introduction} \label{sec:intro}

An ultrametric space is a metric space $(U,\rho)$ satisfying the strengthened triangle inequality $\rho(x,y)\le \max\{\rho(x,z),\rho(y,z)\}$ for all $x,y,z\in U$.
Saying that $(X,d)$ embeds (biLipschitzly) with distortion $D\in [1,\infty)$ into an ultrametric space means that there exists an ultrametric $\rho$ on $X$ satisfying $d(x,y)\le \rho(x,y)\le Dd(x,y)$ for all $x,y\in X$.
The \emph{ultrametric distortion} of $X$ is the infimum over $D$ for which $X$ embeds in an ultrametric with distortion at most $D$.
Given a metric space $(X,d)$, a point $x\in X$ and a radius $r\in [0,\infty)$, the corresponding closed ball is denoted $B(x,r)=B_d(x,r)=\{y\in X:\ d(y,x)\le r\}$, and the corresponding open ball is denoted $B_d^\circ(x,r)=\{y\in X:\ d(y,x)< r\}$.
The following theorem was proved in~\cite{MN-hausdorff,MN-skeleton}.

\begin{theorem}
\label{thm:um-skeleton}
For every $\e\in (0,1)$ there exists $C_\e\in (0,\infty)$ with the following property.  Let $(X,d)$ be a compact metric space and let $\mu$ be a Borel probability measure on $X$. Then there exists a closed subset $U\subseteq X$  satisfying:
\begin{itemize}[\quad$\bullet$]
\item The ultrametric distortion of $U$ is $O(1/\e)$.
\item There exists a Borel probability measure $\nu$ supported on $U$ satisfying
\begin{equation}\label{eq:measure growth}
\nu\left(B_d(x,r)\right)\le \left(\mu(B_d(x,C_\e r)\right)^{1-\e},
\end{equation}
for all $x\in X$ and $r\in [0,\infty)$.
\end{itemize}
\end{theorem}

The above theorem, termed  \emph{the ultrametric skeleton theorem} in~\cite{MN-skeleton}, has its roots in
Dvoretzky-type theorems for finite metric spaces.
It has applications for algorithms, data-structures, probability, geometric measure theory,
and descriptive set theory. See~\cite{MN-hausdorff,MN-skeleton,KMZ,bartal2021advances}, as well as~\cite[\S8 \& \S9]{Naor-Ribe}, for more details.
One of its corollaries is the following Dvoretzky-type theorem
for Hausdorff dimension.

\begin{corollary}[\cite{MN-hausdorff}]
\label{cor:dvo-Hausdorff}
For every $\delta\in (0,1)$, every compact metric space $X$ has a closed subset $U\subseteq X$ having Hausdorff dimension
$\dim_H (U)\ge (1 - \delta)\dim_H(X)$ whose ultrametric distortion
is at most $C/\delta$, for some universal constant $C>0$.
\end{corollary}
As observed in~\cite{MN-hausdorff}, the trade-off between the Hausdorff dimension and the ultrametric distortion of $U$ in Corollary~\ref{cor:dvo-Hausdorff} is asymptotically tight.

\subsection{A simple proof in doubling spaces}
The proof  of Theorem~\ref{thm:um-skeleton} is involved.
The main purpose of this paper is to present a simple  proof
of a special case of Theorem~\ref{thm:um-skeleton}
when $X$ is a \emph{doubling space},
using only a top-down argument on distances.
A metric space $(X,d)$ is called \emph{$\lambda$-doubling} if any
bounded subset $Z\subseteq X$
can be covered by at most $\lambda$ subsets of diameter at most
$\diam_d(Z)/2$.
It is called \emph{doubling} if it is $\lambda$-doubling for some $\lambda\in\mathbb N$.

\begin{theorem}
\label{thm:um-skeleton-doubling}
Let $(X,d)$ be a $\lambda$-doubling compact metric space, and let $\mu$ be a Borel probability measure on $X$.
Then for every $t\in\mathbb N$ there exists a closed subset $U\subseteq X$  satisfying:
\begin{itemize}[\quad$\bullet$]
\item The ultrametric distortion of $U$ is  at most $8t$.
\item There exists a Borel probability measure $\nu$ supported on $U$ satisfying
\begin{equation}\label{eq:measure growth-doubling}
\nu\left(B_d(x,r)\right)\le \lambda^{2/t} \left(\mu(B_d(x,(16t+1)  r)\right)^{1-1/t},
\end{equation}
for all $x\in X$ and $r\in [0,\infty)$.
\end{itemize}
\end{theorem}

Using Theorem~\ref{thm:um-skeleton-doubling} we obtain a simple proof of Corollary~\ref{cor:dvo-Hausdorff}  in doubling spaces. Both are proved in Section~\ref{sec:simple-proof}.

Comparing Theorem~\ref{thm:um-skeleton-doubling} to Theorem~\ref{thm:um-skeleton},
we see that~\eqref{eq:measure growth-doubling}
is a qualitatively weaker bound than~\eqref{eq:measure growth}
because the doubling constant appears as a multiplicative factor in the upper bound on $\nu$.
However, the bound in~\cite{MN-hausdorff, MN-skeleton} on the balls' blow-up parameter --- $C_\e$ in \eqref{eq:measure growth} ---
is only $C_\e=e^{O(1/\e^2)}$, while
the corresponding parameter in~\eqref{eq:measure growth-doubling}
is  $O(1/\e)$.
Thus, the new proof raises the question of a possible  improvement to Theorem~\ref{thm:um-skeleton}:
\begin{conjecture}
\label{conj:improved-um-skeleton}
Theorem~\ref{thm:um-skeleton} is also true with $C_\e=O(1/\e)$.
\end{conjecture}

In Section~\ref{sec:zindulka} we show that a variant of the proof of Theorem~\ref{thm:um-skeleton-doubling}
can be used to reprove
a result of Zindulka~\cite{Zindulka},
analogous to Corollary~\ref{cor:dvo-Hausdorff},
about
the existence  of  full dimensional subsets of compact metric spaces that are $\beta$-H\"older embedded in ultrametrics, for any $\beta<1$.
The new proof has the advantage of using
a weaker doubling condition,  solving an open problem from~\cite{Zindulka}.

A more advanced version of the proof of Theorem~\ref{thm:um-skeleton-doubling} has been recently used  in a follow-up
paper~\cite{mendel2021dvoretzkytype} to obtain a
stronger form of the ultrametric skeleton theorem:
In addition to the upper bound ~\eqref{eq:measure growth-doubling}
on $\nu$ in terms of $\mu$,
it also has a lower bound on $\nu$ in terms of $\mu$.
That theorem is used to prove
a Dvoretzky-type theorem similar to Corollary~\ref{cor:dvo-Hausdorff} in which both $X$ and $U$ are also \emph{Ahlfors regular}.

\subsection{Bartal's Ramsey decomposition}
For given subsets $P,Q\subset X$ of a metric space $(X,d)$, we denote by $d(P,Q)=\inf\{d(x,y):\; x\in P,\; y\in Q\}$, the lower distance between them. For $x\in X$ we also denote $d(x,Q)=d(\{x\},Q)$.
At the heart of the proof of Theorem~\ref{thm:um-skeleton-doubling}
is the following elegant lemma
of Bartal~\cite{bartal2021advances}.
\begin{lemma}[Bartal's Ramsey decomposition lemma~\cite{bartal2021advances}]
\label{lem:bar-ramsey-decomp}
Let $(X,d)$ be a compact metric space and let $\mu$ be a finite Borel measure on $X$.
For any closed subset $Z\subset X$, $\diam(Z)>0$,
and integer $t\in\{2,3,\ldots\}$, there exist disjoint closed subsets $P,Q\subset Z$
that satisfy
  $d(P,Q)\ge \diam(Z)/(8t)$,
 $\diam(Z\setminus Q)\le \diam(Z)/2$,
and
\begin{equation} \label{eq:bar-ramsey-decomp}
\mu(P)\cdot\mu^*(Z)^{1/t} \ge \mu (Z\setminus Q)\cdot \mu^*(Z\setminus Q)^{1/t}.
\end{equation}
In particular,
\begin{equation} \label{eq:bar-ramsey-decomp-2}
\frac{\mu(P)}{\mu^*(P)^{1/t}} + \frac{\mu(Q)}{\mu^*(Q)^{1/t}} \ge \frac{\mu(Z)}{\mu^*(Z)^{1/t}}.
\end{equation}
Here we use the convention $0/0=0$, and $\mu^*$ is defined as
\begin{equation} \label{eq:mu-star}
\mu^*(A)=\sup_{a\in A}\mu(B(a,\diam(A)/4)\cap A).
\end{equation}
\end{lemma}

Lemma~\ref{lem:bar-ramsey-decomp} is stated slightly differently in~\cite{bartal2021advances}  and only for finite spaces.
For completeness, we prove it in Appendix~\ref{sec:proof-bartal}.
Informally, Theorem~\ref{thm:um-skeleton-doubling} is deduced from
Lemma~\ref{lem:bar-ramsey-decomp} as follows.
Lemma~\ref{lem:bar-ramsey-decomp} is applied  iteratively, obtaining a hierarchy of  decompositions that defines an ultrametric on a subset $U\subseteq X$,
with the following property:
Consider a cover of an ultrametric ball $B\subset U$ by ultrametric balls $B_1,B_2,\ldots,B_m \subset U$.
Those ultrametric balls correspond
to subsets $Q$ and $P_1,P_2\ldots,P_m$ in the hierarchy of decompositions (respectively). A recursive application
of~\eqref{eq:bar-ramsey-decomp-2} gives
\[
\sum_i\frac{\mu(P_i)}{\mu^*(P_i)^{1/t}} \ge \frac{\mu(Q)}{\mu^*(Q)^{1/t}}.
\]
Associate with each ultrametric ball $B$ the value
$\xi(B)=\mu(Q)/ \mu^*(Q)^{1/t}$
(recall that $Q\subseteq X$ is the subset corresponding to $B$).
The above inequality means that $\xi$ is sub-additive on the balls of the ultrametric, and hence a ``sub-measure".
In doubling spaces one can relate
$\mu\asymp\mu^*$, and therefore
$\xi(B)\asymp \mu^{1-1/t}(Q)$.
Using an argument from~\cite{MN-skeleton},
the sub-measure $\xi$ can be transformed into an actual measure $\nu$ on $T$ which is dominated by $\mu^{1-1/t}$
on balls of the metric $d$.

Bartal's Ramsey decomposition lemma and its variants found many applications in metric Ramsey theory.
See~\cite{bartal2021advances} for a survey of these applications.
This paper adds another one,
though it is still unclear whether Bartal's lemma, or some variant thereof, can be used to prove Theorem~\ref{thm:um-skeleton}
(or Conjecture~\ref{conj:improved-um-skeleton}).

\section{Proof of Theorem~\ref{thm:um-skeleton-doubling}}
\label{sec:simple-proof}

The approximate ultrametric subset extracted in Theorem~\ref{thm:um-skeleton-doubling} has a natural hierarchical structure that we represent using a binary tree as follows.

\begin{definition}[Binary trees]
\label{def:btree}
Let $\{0,1\}^{<\omega}$ be the set of finite binary sequences, and
let $|\cdot|:\{0,1\}^{<\omega} \to \mathbb N$ be the length of sequences.
Let $\preceq$ be the partial order of extension over $\{0,1\}^{<\omega}$, i.e., for $u,v\in \{0,1\}^{<\omega}$
$u\preceq v$ if $|u|\le |v|$, and $u_i=v_i$ for every $i\in\{1,\ldots,|u|\}$.
For $u\in\{0,1\}^k$, we denote
$u^\smallfrown0,u^\smallfrown1\in\{0,1\}^{k+1}$ the unique elements in $\{0,1\}^{k+1}$ for which
$u\preceq u^\smallfrown0$, and
$u\preceq u^\smallfrown1$.

A (rooted, full, possibly infinite) binary tree $\T\subset \{0,1\}^{<\omega}$ is a non-empty subset satisfying:
\begin{compactitem}
\item For every $u\preceq v\in \T$, we have $u\in\T$;
\item $u^\smallfrown 0\in \T$ if and only if $u^\smallfrown 1\in \T$.
\end{compactitem}
The elements of $\T$ are called \emph{vertices}.
The vertex $\emptyset\in\{0,1\}^{<\omega}$  must be in every binary tree and is called the \emph{root}.
 For $a\in\{0,1\}$,
if $u\in\T$ is a vertex of $\T$ and $u^\smallfrown a\in \T$ is also a vertex of $\T$ then $u^\smallfrown a$
is called a child of $u$ (in $\T$).
A vertex $u\in \T$ without children in $\T$ is called a leaf (in $\T$).

A subset $b\subseteq \T$ of a binary tree is called a branch in $\T$ if $b$ is  a binary tree in which every vertex has at most one child in $b$, and if this child is a leaf in $b$ then it is also a leaf in $\T$.
The set of branches is called the boundary of $\T$ and is denoted
$\partial_\T(\emptyset)$.
More generally for a vertex $u\in \T$,
the boundary of $u$ is defined as
$\partial_\T(u)=\{b\in\partial_\T(\emptyset):\; b\upharpoonright |u|=u\}$.

The least common ancestor of a pair of distinct branches $b,c\in\partial_\T(\emptyset)$, denoted $u=b\wedge c\in\T$, is the unique vertex such that $u_i=b_i=c_i$, for $i\in\{0,\ldots,|u|\}$,
and $b_{|u|+1}\ne c_{|u|+1}$. The least common ancestor of two vertices is defined similarly.
\end{definition}

\begin{lemma} \label{lem:compact-um}
Let
$\T$ be a binary  tree.
Let $\Delta:\T\to [0,\infty)$ be labels on the vertices of $\T$
that are monotone, i.e.,   $\Delta(v)\le \Delta(u)$ for every
$u\preceq v\in\T$, $\Delta(v)=0$ if and only if $v$ is a leaf,
and for every branch $b\in\partial_\T(\emptyset)$,
$\inf_{v\in b}\Delta(v)=0$.
Define a distance $\rho$ on $x,y\in \partial_\T(\emptyset)$ as follows:
$\rho(x,y)=\Delta(x\wedge y)$.
Then $(\partial_\T(\emptyset),\rho)$ is a compact ultrametric.
Furthermore,
$\mathcal{O}_\T=\{\partial_\T(v): v=\emptyset \;\vee\; \forall u\prec v, \;(\Delta(v)<\Delta(u)) \}$
is the set of open balls in $(\partial_\T,\rho)$, and the set of closed balls in $(\partial_\T,\rho)$ with positive radii.
\end{lemma}

Lemma~\ref{lem:compact-um} is straightforward to prove and folklore. Versions of it can be found, e.g., in~\cite[{\S}2]{MN-skeleton}.
For completeness, we provide a proof in Appendix~\ref{sec:proof-bartal}.

\begin{lemma}
Let $(X,d,\mu)$ be compact metric measure space whose doubling constant is $\lambda\in\N$.
Then, for any Borel set $A\subset X$,
\begin{equation}\label{eq:mu-mu*}
 \mu^*(A) \le \mu(A)\le \lambda^2 \mu^*(A),
\end{equation}
where $\mu^*$ is defined in~\eqref{eq:mu-star}.
\end{lemma}
\begin{proof}
Let $\Delta=\diam_d(A)$.
By the doubling condition there exists $\lambda^2$ subsets
$A_1,\ldots A_{\lambda^2}\subseteq A$,
each of diameter at most $\Delta/4$ that covers $A$.
Let $x_i\in A_i$ be chosen arbitrarily.
Since $B(x_i,\Delta/4)\cap A\supseteq A_i$. The collection of sets
$\{B(x_i,\Delta/4)\cap A\}_{i=1,\ldots \lambda^2}$ covers $A$, and therefore at least one of them satisfies
$\mu(B(x_i,\Delta/4)\cap A)\ge \mu(A) /\lambda^2$. Since the supremum
in~\eqref{eq:mu-star} ranges over all those sets, we conclude that
$\mu^*(A)\ge \mu(A)/\lambda^2$.

In the other direction,
\(
\mu^*(A) =\sup_{a\in A}\mu(B(a,\diam(A)/4)\cap A)
\le \sup_{a\in A} \mu (A)=\mu(A).
\)
\end{proof}

\begin{lemma}
\label{lem:um-skeleton-doubling}
Fix a compact $\lambda$-\emph{doubling} metric space $(X,d)$,
a Borel probability measure $\mu$ on $X$, and  $t\in\{2,3,4,\ldots \}$.
Then there exists a binary
tree $\T$, $\Delta:\T\to [0,\infty)$ with the following properties.
Associated with every $u\in \T$ is a ``cluster" $C_u\subseteq X$ satisfying:
\begin{enumerate}[{\quad}(A)]
\item \label{it:root} $C_\emptyset=X$.
\item \label{it:compact} $C_u$ is a closed subset for every $u\in \T$.
\item \label{it:laminar} $C_v\subseteq C_{u}$ for every $u\preceq v\in\T$.
\item \label{it:Delta} $\Delta(u)= \diam_d(C_u)$
for every $u\in \T$.
\item \label{it:separation} If $u, v\in\T$, $u\wedge v \notin\{u,v\}$,  then $d(C_u,C_v)\ge \Delta({u\wedge v})/(8t)$.
\item \label{it:singleton} For every branch $b\in \partial_\T(\emptyset)$, $\bigcap_{v\in b} C_v$ is a singleton.
\setcounter{EnumResume}{\value{enumi}}
\end{enumerate}
By item~\eqref{it:singleton}, we can define a mapping
$\imath:\partial_\T(\emptyset)\to X$, by the set-equation
$\{\imath(b)\}=\bigcap_{v\in b} C_v$.  Then
\begin{enumerate}[{\quad}(A)]
\setcounter{enumi}{\value{EnumResume}}
\item \label{it:partialT=T}
$\imath(\partial_\T(u))\subseteq C_u$ for every $u\in \T$.
\item \label{it:injective} The mapping $\imath$ is injective.
\setcounter{EnumResume}{\value{enumi}}
\end{enumerate}
Defining
$U=\imath(\partial_\T(\emptyset))\subset X$, and a distance  $\rho(x,y)=\Delta(\imath^{-1}(x)\wedge \imath^{-1}(y))$ for  $x,y\in U$, then:
\begin{enumerate}[{\quad}(A)]
\setcounter{enumi}{\value{EnumResume}}
\item \label{it:rho}
$(U,\rho)$ is a compact ultrametric and
$d(x,y) \le \rho(x,y)\le 8t \cdot d(x,y)$.
\setcounter{EnumResume}{\value{enumi}}
\end{enumerate}
Lastly, there exists a  function $\xi:\T\to[0,\infty)$
satisfying:
\begin{enumerate}[{\quad}(A)]
\setcounter{enumi}{\value{EnumResume}}
\item \label{it:xi subadditive} $\xi$ is sub-additive:
for every non-leaf vertex $u\in T$,
$\xi(u)\le \xi(u^\smallfrown 0)+\xi(u^\smallfrown 1)$.

\item  \label{it:xi-mu}
For every $u\in T$,
\begin{equation}
\label{eq:xi-mu}
\mu^{1-1/t}(C_u)\le \xi(u) \le \lambda^{2/t} \mu^{1-1/t}(C_u).
\end{equation}
\end{enumerate}
\end{lemma}

\begin{proof}
The tree $\T$ and the clusters associated with it are defined recursively.
The cluster associated with  $\emptyset\in\T$ is $C_\emptyset=X$, which satisfies item~\eqref{it:root}.
Assume that a vertex $u\in\T$ and the associated cluster $C_u$ were defined.
If $C_u$ is a singleton then $u$ will remain without children, i.e., a leaf.

Assume next that $C_u$ is not a singleton.
By application of Lemma~\ref{lem:bar-ramsey-decomp} on $Z=C_u$ we have $P,Q\subset C_u$ satisfying
Lemma~\ref{lem:bar-ramsey-decomp}.
Define $C_{u^\smallfrown0}=P$ and $C_{u^\smallfrown 1}=Q$.
This, in particular,
satisfies items~\eqref{it:compact}, and~\eqref{it:laminar}.
Define $\Delta(u)=\diam_d(C_u)$ which satisfies item~\eqref{it:Delta}.

Item~\eqref{it:separation}.
Suppose $u,v\in\T$ such that $u\wedge v \notin\{u,v\}$
(i.e., $u\not\preceq v$ and $v\not\preceq u$).
Let $w=u\wedge v$.   Assume, without loss of generality that $w^\smallfrown 0\preceq u$, and $w^\smallfrown 1\preceq v$.
 By Lemma~\ref{lem:bar-ramsey-decomp},
 \[
 d(C_u,C_v)\ge d(C_{w^\smallfrown 0}, C_{w^\smallfrown 1}) \ge \Delta(u\wedge v)/(8t),\]
 which proves item~\eqref{it:separation}.

Item~\eqref{it:singleton}.
First assume that the branch $b$ is finite. In this case $b\in \T$ is a leaf, and $\cap_{v\in b} C_v=C_b$ which is a singleton by the construction above.
Next assume that $b$ is infinite.
Denote $v_i= b\upharpoonright i$.
By the above construction, all vertices in $b$ have two children, so
let $u_i$ be the ``other child" of $v_i$, i.e., the child of $v_i$ such that $u_i\ne v_{i+1}$.
$(\Delta({v_i}))_i$ is a positive, non-increasing sequence.
Assume towards a contradiction that
$\lim_{i\to\infty} \Delta(v_i)>0$.
That is, there exists $\e>0$ such that $\Delta({v_i})\ge \e$ for every $i\in\mathbb N$.
Observe that for $i<j$, $u_i \wedge u_j=v_i$.
Therefore,
for every $i\ne j$,
\[
d(C_{u_i},C_{u_j})\ge \Delta({v_{\min\{i,j\}}})/(8t)\ge \e/(8t),
\]
which contradicts the compactness of $X$.
Hence, $\lim_{i\to\infty}\diam_d(C_{v_i})=\lim_{i\to\infty} \Delta({v_i})=0$. By Cantor's intersection theorem,
 $\bigcap_{v\in b} C_v$ is a singleton.

Item~\eqref{it:partialT=T} is an immediate corollary of
the definition of $\imath$ and Item~\eqref{it:singleton}.
By Item~\eqref{it:separation}, different branches are  mapped to different points of $X$ by $\imath$,
so Item~\eqref{it:injective} holds.

Item~\eqref{it:rho}.
It follows from Lemma~\ref{lem:compact-um} that  $(U,\rho)$ is a compact ultrametric.
Fix $x,y\in U$, and denote $w=\imath^{-1}(x)\wedge \imath^{-1}(y)$.
Since $x,y\in C_{w}$,
$d(x,y)\le \diam_d(C_w)=\rho(x,y)$.
On the other hand, since $x\in C_{w^\smallfrown 0}$ while
$y\in  C_{w^\smallfrown 1}$ (or vice-versa),
\[
d(x,y) \ge d(C_{w^\smallfrown 0}, C_{w^\smallfrown 1}) \ge \Delta(x\wedge y)/(8t)=
\rho(x,y)/(8t).
\]
This proves Item~\eqref{it:rho}.

Define $\xi:\T\to[0,\infty)$  as
\[
\xi(u)=\frac{\mu(C_u)}{\mu^*(C_u)^{1/t}}.
\]
By inequality~\eqref{eq:bar-ramsey-decomp-2} of Lemma~\ref{lem:bar-ramsey-decomp},
$\xi$ is sub-additive om $\T$,
i.e., $\xi(u)\le \xi(u^\smallfrown 0)+\xi(u^\smallfrown 1)$ for every non-leaf vertex $u\in\T$.
This proves Item~\eqref{it:xi subadditive}.
Lastly, Inequality~\eqref{eq:xi-mu} (Item~\eqref{it:xi-mu})
follows directly from \eqref{eq:mu-mu*}.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:um-skeleton-doubling}]
The case $t=1$ is trivial, so we assume from here on that $t\in\{2,3,4,\ldots\}$.
Apply Lemma~\ref{lem:um-skeleton-doubling}
on the metric space $(X,d)$, and the Borel probability measure $\mu$.
We will define the measure $\nu$ supported on $U$
and check that it satisfies the properties asserted
by the theorem.

First, define $\nu: \{\imath(\partial_\T(v))\}_{v\in \T}\to [0,1]$ recursively on $\T$ as follows.
Define $\nu(U)=1$, and note that
$\nu(\imath(\partial_\T(\emptyset)))=1=\mu(X)^{1-1/t}\le \xi(\emptyset)$.
Assume now that $\nu(\imath(\partial_T(u)))$ was defined,
and define
\[
\nu(\imath(\partial_\T({u^\smallfrown 0}))) = \frac{\xi(u^\smallfrown 0)}{\xi(u^\smallfrown 0)+
\xi(u^\smallfrown 1)} \cdot\nu(\partial_\T(u)), \qquad
\nu(\partial_\T({u^\smallfrown 1})) = \frac{\xi(u^\smallfrown 1)}{\xi(u^\smallfrown 0)+\xi(u^\smallfrown 1)} \cdot\nu(\partial_\T(u)).
\]
From the inductive hypothesis and the sub-additivity of $\xi$,
\[
\nu(\imath(\partial_\T({u^\smallfrown 0}))) \le
{\xi(u^\smallfrown 0)} \cdot\frac{\xi(u)}{\xi(u^\smallfrown 0)+\xi(u^\smallfrown 1)}
\le \xi(u^\smallfrown 0),
\]
and in similar fashion $\nu(\imath(\partial_\T({u^\smallfrown 1 })))\le\xi(u^\smallfrown 1)$.
Furthermore, $\nu$ is additive on $\{\imath(\partial_\T(v))\}_{v\in \T}$.

Recall that a (set theoretic) semi-ring in $X$
is a collection of subsets $\mathcal S\subseteq 2^X$ satisfying
\begin{inparaenum}[(i)]
\item $\emptyset\in \mathcal S$;
\item if $A,B\in\mathcal S$ then $A\cap B\in\mathcal S$;
\item if $A,B\in\mathcal S$ then there exist $n\ge 0$ and
$A_1,\ldots, A_n\in\mathcal S$ pairwise disjoint such that
$A\setminus B=\bigcup_{i=1}^n A_i$.
\end{inparaenum}
By Lemma~\ref{lem:compact-um},
 $\{\emptyset\}\cup \{\partial_\T(v)\}_{v\in\T}$ is
a semi-ring consisting of all the open balls in $(U,\rho)$,
and
$\nu$ is a pre-measure on that semi-ring.
By Carath\'eodory extension theorem (see~\cite[Theorem~1.53]{Klenke}), $\nu$ can be extended to a measure on the $\sigma$-algebra generated by $\{\partial_\T(v)\}_{v\in \T}$,
which is the $\sigma$-algebra of Borel sets of $(U,\rho)$.
Since the metrics $d|_U$ and $\rho$ are topologically equivalent, and $U$ is closed and hence Borel set of $(X,d)$, $\nu$ can be extended to a Borel measure on $X$ by simply define
$\nu(A)=\nu(A\cap U)$ on every Borel $A\subseteq X$.

We are left to prove~\eqref{eq:measure growth-doubling}.
Fix $x\in X$ and $r\ge 0$.
If $B_d(x,r)\cap U=\emptyset$, then
$\nu(B_d(x,r))=0$ and there is nothing to prove.
Otherwise, let $y\in B_d(x,r)\cap U$, so
\[
B_d(x,r)\cap U \subseteq B_d(y,2r) \cap U \subseteq B_\rho(y,16tr).
\]
Since $B_\rho(y,16tr)$ is a closed ball in $(U,\rho)$, by Lemma~\ref{lem:compact-um}  there exists
some $v\in\T$ such that $B_\rho(y,16tr)=\imath(\partial_\T(v))$.
In particular $\diam_d(C_v)=\Delta(v)\le 16tr$.
Observe that
\[
B_\rho(y,16tr)=\imath (\partial_\T(v))\subseteq C_v \subseteq B_d(y,16tr) \subseteq B_d(x,(16t+1)r).
\]
Hence,
\begin{equation*}
\nu (B_d(x,r))\le \nu(\imath(\partial_\T(v))) \le \xi(v)
\stackrel{\eqref{eq:xi-mu}}{\le}\lambda^{2/t} \mu(C_v)^{1-1/t}
\le\lambda^{2/t}
  {\mu(B_d(x,(16t+1)r))^{1-1/t}}. \qedhere
\end{equation*}
\end{proof}

\begin{proof}[Proof of Corollary~\ref{cor:dvo-Hausdorff} in doubling spaces]
We follow the argument in~\cite{MN-skeleton}.
Fix $\e\in(0,1/2)$, and let
$t=\lceil 1/\e \rceil$.
Assume that $(X,d)$ is a complete doubling metric space of Hausdorff dimension greater than $\alpha\in (0,\infty)$, and doubling constant $\lambda\in \mathbb N$.
Then there exists~\cite{How95,Mattila} an $\alpha$-Frostman measure on $(X,d)$.
That is, a positive Borel  measure $\mu$ satisfying $\mu(B_d(x,r))\le Kr^\alpha$ for every $x\in X$ and $r\in (0,\infty)$, where $K>0$ is a constant that may depend  on $X$ and $\alpha$ but not on $x$ and $r$.

By taking $R>0$ sufficiently large, we may assume that
$\mu(B_d(x,R))>0$. So we restrict ourselves to $X=B_d(x,R)$, and by normalizing $\mu$, we may assume that
$\mu(X)=1$. Since a closed bounded subset of complete doubling space is compact, we may assume that $X$ is compact.

An application of Theorem~\ref{thm:um-skeleton-doubling} to $(X,d,\mu)$ yields a compact subset $U\subseteq X$ that embeds into an ultrametric space with distortion $8t\le 12/\e$,
and a Borel probability measure $\nu$ supported on $U$ satisfying
\[
\nu(B_d(x,r))\le \lambda^{2/t} \mu(B_d(x,(16t+1) r))^{1-1/t}\le \lambda^{2/t}K^{1-1/t}(16t+1)^{(1-1/t)\alpha}r^{(1-1/t)\alpha},
\]
 for all $x\in X$ and $r\in (0,\infty)$.
 Hence, $\nu$ is a $((1-1/t)\alpha)$-Frostman measure on $(U,d)$, implying (see~\cite{Mattila}) that $(U,d)$ has Hausdorff dimension at least $(1-1/t)\alpha \ge (1-\e)\alpha$.
\end{proof}

\section{Remarks}
\label{sec:remarks}

The following remarks were communicated to the author by an anonymous referee.

In~\cite{MZ}, an analog of  Corollary~\ref{cor:dvo-Hausdorff} for the packing dimension was proved.
Their proof is an analog of the corresponding proof for Hausdorff dimension in~\cite{MN-hausdorff}, see~\cite[\S2,\S3]{MZ}.
In particular a key step in their proof is the use
of Theorem~\ref{thm:um-skeleton}.
Therefore, Theorem~\ref{thm:um-skeleton-doubling} also gives a simpler proof of their main result for doubling spaces.

It is possible to obtain a result qualitatively similar
to Corollary~\ref{cor:dvo-Hausdorff} in doubling spaces using Assouad's embedding~\cite{Assouad}.
However, this approach, which we outline next,
is quantitatively far from being asymptotically tight (unlike the approach used in this paper).
Let $(X,d)$ be a $\lambda$-doubling compact metric space having Hausdorff dimension $\dim_H(X,d)=\alpha$. Then $\dim_H(X,\sqrt{d})=2\alpha$.
By Naor-Neiman's quantitative version of  Assouad's embedding, see~\cite{Naor-Neiman},
there is a biLipschitz embedding $f:(X,\sqrt{d})\to \mathbb R^n$ with distortion $O(\log \lambda)$ and $n=O(\log \lambda)$. Since biLipschitz embeddings do not change the Hausdorff dimension, $\dim_H(f(X))=2\alpha$.
Consider the following Cantor set $C^n_\e\subseteq \mathbb R^n$:
\[
C^n_\e=\Bigl \{\tfrac{1+\e}{2}\sum_{i=0}^\infty \bigl(\tfrac{1-\e}{2}\bigr)^i \delta_i:\; \delta_i\in\{0,1\}^n\Bigr \}.
\]
The ultrametric distortion of $C_\e^n$ is at most $\sqrt{n}/\e$, and its Hausdorff dimension is $\dim_H(C_\e^n)=n+\log_2(1-\e)$.
By~\cite[Theorem~13.11]{Mattila}, there exists
an isometry $\phi:\mathbb R^n \to \mathbb R^n$,
such that
\[
\dim_H(\phi(C_\e^n)\cap f(X))\ge \dim_H(C_\e^n)+\dim_H(f(X))-n=2\alpha+ \log_2(1-\e).
\]
Let $S=f^{-1}(\phi(C_\e^n)\cap f(X))\subseteq X$. Since Hausdorff dimension is an invariant of biLipschitz embedding,
$(S,\sqrt{d})$ is a closed subset of $(X,\sqrt{d})$
whose Hausdorff dimension is at least
$2\alpha+(\log_2(1-\e))$ and its ultrametric distortion is at most order of
$\log \lambda \cdot \sqrt{n}/\e$.
Observe that square of the distances of an ultrametric is still an ultrametric, and therefore
$(S,{d})$ is a closed subset of $(X,{d})$
whose Hausdorff dimension is at least
$\alpha+(\log_2(1-\e))/2$ and its ultrametric distortion is at most order of
$\log^2 \lambda \cdot {n}/\e^2 \lesssim(\log^3 \lambda)/\e^2$.
By setting $\delta =-  \log_2(1-\e)/(2\alpha)$, we have in terms of Corollary~\ref{cor:dvo-Hausdorff}'s notation, a subspace $(S,d)\subset (X,d)$ whose Hausdorff dimension is at least $(1-\delta)\alpha$,
and its ultrametric distortion is $O(\log^3\lambda/(\alpha^2 \delta^2))$. Since $\alpha\lesssim \log \lambda$, this bound is no better than $O((\log \lambda) /\delta^2)$.

\section{Nearly ultrametric subsets of full dimension}
\label{sec:zindulka}

In~\cite{Zindulka}, Zindulka proved a qualitative variant of Corollary~\ref{cor:dvo-Hausdorff} with a different
trade-off for spaces with a mild doubling condition:
The subset $U\subseteq X$ extracted is full dimensional, i.e.,
$\dim_H(U)=\dim_H(X)$.
But $U$ is not quite biLipschitz equivalent to an ultrametric, rather it is only ``nearly biLipschitz equivalent".
Rigorously:

\begin{definition}[Nearly ultrametric space~{\cite[Def.~2.4, Prop.~2.5]{Zindulka}}]
A bounded metric space $(U,d)$ is called \emph{nearly ultrametric} if there exists an ultrametric $\rho$ on $U$ such tha
\begin{itemize}[$\bullet$ ]
\item The identity map $(U,\rho)\mapsto (U,d)$ is $1$-Lipschitz. I.e., for every $a,b\in U$, $d(a,b)\le \rho(a,b)$.
\item The identity map $(U,d)\mapsto (U,\rho)$ is
\emph{nearly Lipschitz}, i.e., for every $\beta\in(0,1)$  there exists $C>0$ such that
\( \rho(a,b)\le C\cdot d(a,b)^\beta\),
for every $a,b\in U$.
\end{itemize}
\end{definition}

\begin {definition}[Modulus of the doubling condition]
Let $(X,d)$ be  a metric space.
For $\delta>0$,  $\lambda_X(\delta)$ is defined to be the minimal number $\lambda\in \mathbb N\cup\{\infty\}$ such that any subset of diameter at most $\delta$ can be covered by $\lambda$ subsets of diameter at most $\delta/16$
\footnote{The constant $16$ is somewhat arbitrary, and any other constant larger than $1$ can be chosen without altering the meaning of conditions~\eqref{eq:non-exploding} and ~\eqref{eq:non-exploding-2}.
It was chosen  so that $\lambda_X(\delta)$ would be ``compatible" with $\tilde \lambda_Z$ in~\eqref{eq:AP-decomp} and thus spare the need to
introduce more notation.}
\end{definition}

See~\cite{Zindulka} for more context, motivation and applications of those definitions.

\begin{theorem}[{\cite[Theorem~2.6]{Zindulka}}]
\label{thm:zindulka}
Let $(X,d)$ be a compact metric spac
\footnote{The original theorem applies more generally to analytic spaces.
However, the gist of the argument is in the compact case,
and the analytic case can be reduced to the compact case, see~\cite{Mercourakis,Zindulka}.}
whose modulus of the doubling condition satisfie
\footnote{In \cite[Def.~2.1]{Zindulka}  this condition is called
\emph{non-exploding}.
There, $\lambda_X(\delta)$ is replaced with the function $Q(\delta)$ which is defined as ``[the minimal value such that] every closed ball in $X$ of radius $\delta > 0$ is covered by at most $Q(\delta)$ many closed balls of radius $\delta/2$."
These two variants of non-exploding are equivalent, as evident from the (straight-forward) estimates
$Q(\delta/2)\le \lambda_X(\delta) \le  \prod_{i=0}^5 Q(\delta/2^i)$.}
\begin{equation}
\label{eq:non-exploding}
\lim_{\delta\to 0^+}  \frac{\log \lambda_X(\delta)}{\log \delta}=0,
\end{equation}
and let $\mu$ be a finite Borel measure on $X$.
Then for every $\e>0$
there exists a closed subset $U\subset X$ for which
$\mu(X\setminus U)<\e$, and $U$ is nearly ultrametric.
\end{theorem}

The following corollary of Theorem~\ref{thm:zindulka}  should be compared with Corollary~\ref{cor:dvo-Hausdorff}.
\begin{corollary} \label{cor:nearly-UM-full-dimension}
Let $(X,d)$ be a compact metric space satisfying~\eqref{eq:non-exploding}
and assume that
$\mathcal H^\alpha(X)>0$, where $\mathcal H^\alpha$ is the $\alpha$-dimensional Hausdorff measure on $X$
(In particular, $\dim_H(X)\ge \alpha$.)
Then $X$ contains a nearly ultrametric closed subset $U\subseteq X$
having $\dim_H(U)=\alpha$.
\end{corollary}

Zindulka's original proof of Theorem~\ref{thm:zindulka} shares the same high-level approach described in Section~\ref{sec:remarks}:
Apply an Assouad-type embedding (this time, into an infinite dimensional torus) and intersects it with Cantor-like subset.
It was suggested by an anonymous referee that the general approach in this paper may give a different proof of Theorem~\ref{thm:zindulka}.
It turns out that this is indeed true.
In fact, we obtain the conclusion of Theorem~\ref{thm:zindulka} under a milder doubling condition, requiring only that $\lambda_X(\delta)=e^{\delta^{-o(1)}}$
instead of $\lambda_X(\delta)=\delta^{-o(1)}$ as in~\eqref{eq:non-exploding}. Formally:
\begin{theorem}
\label{thm:zindulka-2}
Let $(X,d)$ be a compact
metric space whose modulus of the doubling condition satisfies
\begin{equation}
\label{eq:non-exploding-2}
\lim_{\delta\to 0^+}  \frac{\log \log (e\lambda_X(\delta))}{\log \delta}=0,
\end{equation}
and let $\mu$ be a finite Borel measure on $X$.
Then for every $\e>0$
there exists a closed subset $U\subset X$ for which
$\mu(X\setminus U)<\e$, and $U$ is nearly ultrametric.
\end{theorem}

In particular, Corollary~\ref{cor:nearly-UM-full-dimension}  also holds assuming~\eqref{eq:non-exploding-2} instead of~\eqref{eq:non-exploding}.
Theorem~\ref{thm:zindulka-2} also answers in affirmative Question~5.9 from~\cite{Zindulka}.
We next outline the proof of Theorem~\ref{thm:zindulka-2}.
We begin with an analog to Bartal's Ramsey decomposition lemma.

\begin{lemma} \label{lem:AP-decomp}
Let $(X,d)$ be a compact metric space and let $\mu$ be a finite Borel measure on $X$.
For any closed subset $Z\subset X$, $\diam(Z)>0$,
and integer $t\in\{2,3,\ldots\}$, there exist disjoint closed subsets $P,Q\subset Z$
that satisfy
  $d(P,Q)\ge \diam(Z)/(8t)$,
 $\diam(Z\setminus Q)\le \diam(Z)/2$,
and
\begin{equation} \label{eq:AP-decomp}
\mu(P)\cdot\tilde \lambda_Z^{1/t} \ge \mu (Z\setminus Q).
\end{equation}
Here
$\tilde \lambda_Z$ is the minimal number of subsets of diameter at most $\diam(Z)/8$ needed to cover $Z$.
\end{lemma}

Lemma~\ref{lem:AP-decomp} is a variant of Awerbuch and Peleg's \emph{sparse partitions}~\cite{AP}.
Its proof is similar to (and simpler than)
the proof of Lemma~\ref{lem:bar-ramsey-decomp}.
We prove both of them simultaneously in Appendix~\ref{sec:proof-bartal}.
Next is an analog of Lemma~\ref{lem:um-skeleton-doubling}.

\begin{lemma}
\label{lem:nearly-um-skeleton}
Fix a compact metric space $(X,d)$, a Borel probability measure $\mu$ on $X$, and
$t:\mathbb N \to \{2,3,4,\ldots\}$ non-decreasing.
Then there exists a binary
tree $\T$, $\Delta:\T\to [0,\infty)$ with the following properties.
Associated with every $u\in \T$ is a ``cluster" $C_u\subseteq X$ satisfying:
\begin{enumerate}[{\quad}(A)]
\item \label{it2:root} $C_\emptyset=X$.
\item \label{it2:compact} $C_u$ is closed for every ${u\in\T}$.
\item \label{it2:laminar} $C_v\subseteq C_{u}$ for every $u\preceq v\in\T$.
\item \label{it2:Delta} $\Delta(u)= \diam_d(C_u)$ for every $u\in\T$.
\item \label{it2:separation} If $u, v\in\T$, $u\wedge v \notin\{u,v\}$,  then $d(C_u,C_v)\ge \Delta({u\wedge v})/\bigl(8\cdot t\bigl (\lfloor - \log_2 \Delta(u\wedge v)\rfloor \bigr )\bigr)$.
\item \label{it2:singleton} For every branch $b\in \partial_\T(\emptyset)$, $\bigcap_{v\in b} C_v$ is a singleton.
\setcounter{EnumResume}{\value{enumi}}
\end{enumerate}
By item~\eqref{it2:singleton}, we can define a mapping
$\imath:\partial_\T(\emptyset)\to X$, by the set-equation
$\{\imath(b)\}=\bigcap_{v\in b} C_v$.  Then
\begin{enumerate}[{\quad}(A)]
\setcounter{enumi}{\value{EnumResume}}
\item \label{it2:partialT=T}
$\imath(\partial_\T(u))\subseteq C_u$ for every $u\in \T$.
\item \label{it2:injective} The mapping $\imath$ is injective.
\setcounter{EnumResume}{\value{enumi}}
\end{enumerate}
Denote
$U=\imath(\partial_\T(\emptyset))\subset X$, and a distance  $\rho(x,y)=\Delta(\imath^{-1}(x)\wedge \imath^{-1}(y))$ for  $x,y\in U$. Then:
\begin{enumerate}[{\quad}(A)]
\setcounter{enumi}{\value{EnumResume}}
\item \label{it2:rho}
$(U,\rho)$ is a compact ultrametric and
\begin{equation} \label{eq:nearly-um-bound}
d(x,y) \le \rho(x,y)\le 8 \cdot t \bigl(\lfloor - \log_2 d(x,y)\rfloor \bigr) \cdot d(x,y).
\end{equation}
\setcounter{EnumResume}{\value{enumi}}
\end{enumerate}
Denote $\Level_i=\{u\in\T:\; \Delta(u)\le 2^{-i} \land (\forall v\prec u,\; \Delta(v)> 2^{-i})\}$.
Then:
\begin{enumerate}[{\quad}(A)]
\setcounter{enumi}{\value{EnumResume}}
\item \label{it2:mu-decrease}
For every $i\in\mathbb N$,
\begin{equation}
\label{eq:mu(C_u)-bound}
\mu\Bigl(\bigcup _{u\in\Level_i} C_u\Bigr)
\le \lambda_X(2^{-i})^{1/t({i})}
\mu\Bigl(\bigcup _{u\in\Level_{i+1}} C_u\Bigr).
\end{equation}
\setcounter{EnumResume}{\value{enumi}}
\end{enumerate}
\end{lemma}
\begin{proof}[Outline of the proof]

The construction of the tree $\T$ and the labels
$\Delta:\T\to [0,\infty)$ is similar to the construction in the proof of
Lemma~\ref{lem:um-skeleton-doubling} but instead of applying
Lemma~\ref{lem:bar-ramsey-decomp} to $C_u$ where $u\in\T$,
we apply Lemma~\ref{lem:AP-decomp} to $C_u$ with the parameter $t(\lfloor - \log_2 \Delta(u)\rfloor )$.
Items~\eqref{it2:root}, \eqref{it2:compact}, \eqref{it2:laminar},
\eqref{it:Delta}, \eqref{it2:separation},
\eqref{it2:singleton}, \eqref{it:partialT=T},
 \eqref{it2:injective}, and~\eqref{it2:rho}
are all proved exactly the same as in the proof of Lemma~\ref{lem:um-skeleton-doubling}.

We are left to prove Item~\eqref{it2:mu-decrease}.
For $u\in \T$, denote by $\T_u$ the subtree of $\T$ containing $u$ and all its descendants. To prove~\eqref{eq:mu(C_u)-bound} it is sufficient to prove
that for every $u\in \Level_i$,
\begin{equation} \label{eq:L_i<=L_i+1}
\mu(C_u)\le \lambda_X (2^{-i})^{1/t({i})} \sum_{v\in \Level_{i+1}\cap \T_u} \mu(C_v).
\end{equation}
We fix $u\in\Level_i$.
If $u\in \Level_{i+1}$, then~\eqref{eq:L_i<=L_i+1} holds trivially, so we may assume that $u\notin\Level_{i+1}$.
Since $u\notin\Level_{i+1}$, $u$ is not a leaf
(observe that for a leaf vertex $w$, $\Delta(w)=0$, and therefore if $w\in  \Level_{i}$ then $w\in\Level_j$ for any $j\ge i$).
We claim that the vertices of $\Level_{i+1}\cap \T_u$ have the structure depicted in Fig.~\ref{fig:L_i+1}:
Let $w_1=u$, and $w_{k+1}=w_k{}^\smallfrown 1$,
let $\ell$ be the smallest $k$ such that $\diam(C_{w_k})\le 2^{-i-1}$. Then $w_\ell \in\Level_{i+1}\cap \T_u$,
and for $k<\ell$,
$v_k=w_k{}^\smallfrown 0\in \Level_{i+1}\cap \T_u$, since, by Lemma~\ref{lem:AP-decomp},
\[
\Delta(v_k)= \Delta(w_k{}^\smallfrown 0)=\diam_d(C_{w_k{}^\smallfrown 0})
\le \diam_d(C_{w_k})/2 \le \Delta(u)/2\le 2^{-i-1}.
\]
Since $\Level_{i+1}$ cannot contain two vertices with ancestor/descendant relation, we deduce that
$\Level_{i+1}\cap \T_u=\{v_1,\ldots v_{\ell-1},w_\ell\}$.
Applying Inequality~\eqref{eq:AP-decomp} inductively, and observing that $\tilde \lambda_{C_{w_k}}\le  \lambda_X(2^{-i})$,
for $k\in \{1,\ldots,\ell-1\}$,
we conclude that
\begin{multline*}
\mu(C_u)\le  \lambda_X(2^{-i}))^{1/t(i)}\mu(C_{v_1}) + \mu(C_{w_2})
\le \ldots \le \sum_{k=1}^{\ell-1} \lambda_X(2^{-i})^{1/t(i)}
\mu(C_{v_k})+ \mu(C_{w_\ell})\\
\le
\lambda_X(2^{-i})^{1/t({i})} \Bigl(\sum_{k=1}^{\ell-1} \mu(C_{v_k})+ \mu(C_{w_\ell})\Bigr).
\qedhere
\end{multline*}
\end{proof}
\begin{figure}[ht]
\includegraphics{L_i+1}
\caption{The vertices $v_1,\ldots, v_{\ell-1},w_\ell$ constitutes $\Level_{i+1}\cap\T_u$.}
\label{fig:L_i+1}
\end{figure}

\begin{proof}[Proof of Theorem~\ref{thm:zindulka-2}]
The assertion is trivial when $\mu(X)=0$, so we assume that $\mu(X)>0$.
By rescaling the measure we may actually assume without loss of generality that $\mu$ is a Borel probability measure, i.e., $\mu(X)=1$.
Assume also for now that $\diam_d(X)\le 1/2$.
We will get rid of this condition at the end of the proof.
Fix $\e\in(0,1)$, and define
\begin{align}\label{eq:def:eta-t}
\eta(i)&=\frac{\log_2 \log (e\lambda_X(2^{-i}))}{i} & t(i)= &\Bigl\lceil \e^{-1}2^{i(\eta(i)+ ({2\log_2 e})/{\sqrt{i}}\,)} \Bigr\rceil.
\end{align}
By~\eqref{eq:non-exploding-2},
\(
\lim_{i\to\infty}  \eta(i)=0.
\)

Apply Lemma~\ref{lem:nearly-um-skeleton} to $(X,d)$ and  $\mu$ with $t(\cdot)$.
Inequality~\eqref{eq:nearly-um-bound} implies that $(U,d)$ is nearly ultrametric: $(U,\rho)$ is an ultrametric and dominates the distances in $(U,d)$.
In the other direction, fix $\beta<1$.
Since $\lim_{i\to \infty} \eta(i)+({2\log_2 e})/{\sqrt{i}}=0$, there exists
some $\xi\in \mathbb N$ such that for any $i>\xi$,
\(
{{1-\eta(i)-{(2\log_2 e)}/{\sqrt{i}}}}\ge \beta.
\)
By analyzing two  cases: $d(x,y)\ge 2^{-\xi}$, for which we use $\rho(x,y)\le 1/2$, and  $d(x,y)< 2^{-\xi}$, for which we set $i=\lfloor - \log_2
 d(x,y)\rfloor$ and use~\eqref{eq:nearly-um-bound},
we deduce  that
\begin{multline*}
\rho(x,y)\le \max\bigl\{2^\xi,
 8 \cdot  t(i)
 \bigr\} \cdot d(x,y) \\
 \le  \max\Bigl \{2^\xi, 16 \e^{-1}2^{\eta(i)+(2\log_2 e)/\sqrt{i}}
 d(x,y)^{-\eta(i)-(2\log_2 e)/\sqrt{i}}\Bigr\} \cdot d(x,y) \\
\le  \max\{2^{\xi},32\e^{-1}\} d(x,y)^\beta.
\end{multline*}

We next bound $\mu(U)$ from below.
Observe that
\(U= \bigcap_{i\in\mathbb N} \bigcup _{u\in\Level_{i}} C_u\), and
\((\bigcup _{u\in\Level_{i}} C_u)_i\)
is a non-increasing sequence of subsets.
Therefore,
\(
\lim_{i\to\infty} \mu \bigl(\bigcup _{u\in\Level_{i}} C_u \bigr)=\mu(U).
\)
By~\eqref{eq:mu(C_u)-bound},
\[
\prod_{j=1}^\infty \lambda_X(2^{-j})^{-1/t(j)}
\le \prod_{j=1}^\infty \frac{\mu\Bigl(\bigcup_{u\in\Level_{j+1}} C_u\Bigr)}{\mu\Bigl(\bigcup_{u\in\Level_{j}} C_u\Bigr)} =\frac{\mu(U)}{\mu\Bigl(\bigcup_{u\in\Level_{1}} C_u\Bigr)}=\mu(U).
\]

Estimating the infinite product above on the left-hand side:
\begin{equation*}
\prod_{j=1}^\infty \lambda_X(2^{-j})^{1/t(j)}
\stackrel{\eqref{eq:def:eta-t}}\le \prod_{j=1}^\infty \exp\Bigl(2^{j\eta(j)}
\e 2^{-j\eta(j)} e^{-2\sqrt{j}} \Bigr)
= \prod_{j=0}^\infty \exp\Bigl(
\e e^{-2\sqrt{j}}\Bigr)
=   \exp\biggl(\e \sum_{j=1}^\infty
e^{-2\sqrt{j}}\biggr)
< e^{\e/2},
\end{equation*}
where the last inequality follows from the estimate
\[
\sum_{j=1}^\infty e^{-2\sqrt{j}}\le e^{-2}+ \int_1^\infty e^{-2\sqrt{x}}dx= e^{-2}+ \int_2^\infty 0.5 t e^{-t}dt = e^{-2}+1.5 e^{-2}< 0.5.
\]
In summary,
\(
\mu(U)>e^{-\e/2}\ge 1-\e/2.
\)

When $\diam_d(X)>1/2$, we rescale the metric as follows.
Define $\alpha=1/(2\diam(X))$ and the metric
$\tilde d(x,y)=\alpha\cdot d(x,y)$, so $\diam_{\tilde d}(X)=1/2$.
By the above, there exists $U\subseteq X$ such that
$\mu(U)>1-\e/2$, and an ultrametric $\tilde \rho$ on $U$
for which  for any $\beta<1$ there exists $C>0$ such that
\[ \tilde d(x,y)\le \tilde \rho(x,y)\le C\cdot \tilde d(x,y)^\beta.
\]
Define $\rho=\alpha^{-1}\tilde \rho$, which is also an ultrametric on $U$,
and
\[  d(x,y)\le  \rho(x,y)\le C \alpha^{-1}\cdot \tilde d(x,y)^\beta= C\alpha^{\beta-1}\cdot d(x,y)^\beta.
\qedhere
\]
\end{proof}