# Root structures of polynomials with sparse exponents

Reuben Wheeler  Maxwell Institute of Mathematical Sciences and the School of
Mathematics, University of Edinburgh, JCMB, The King’s Buildings, Peter
Guthrie Tait Road, Edinburgh, EH9 3FD, Scotland<EMAIL_ADDRESS>
###### Abstract.

For real polynomials with (sparse) exponents in some fixed set,

$\Psi(t)=x+y_{1}t^{k_{1}}+\ldots+y_{L}t^{k_{L}},$

we analyse the types of root structures that might occur as the coefficients
vary. We first establish a stratification of roots into tiers, each containing
roots of comparable sizes. We then show that there exists a suitable small
parameter $\epsilon>0$ such that, for any root $w\in\mathbb{C}$,
$B(w,\epsilon|w|)$ contains _at most_ $L$ roots, counted with multiplicity.
Our analysis suggests the consideration of a rough factorisation of the
original polynomial and we establish the closeness of the corresponding root
structures: there exists a covering of the roots by balls wherein a) each ball
contains the same number of roots of the original polynomial and of its rough
factorisation and b) the balls are strongly separated.

###  1\. Introduction

Methods for finding solutions to polynomial equations have a storied history
in mathematics, leading to the extension of number systems, the development of
algebra, and being of particular importance in the development of numerical
analysis [3]. Before taking stock of more contemporary developments, let us
recall some points in that history most relevant to our analysis. On the
theoretical side, we have the fundamental theorem of algebra, which tells us
that every degree $n$ complex polynomial has $n$ roots. Nevertheless, Abel and
Ruffini established that there exist polynomials of degree $5$ whose solution
could not directly expressed in terms of radicals. The work of Galois later
established under what conditions all the solutions to polynomial equations
could be finitely expressed in terms of radicals [12]. Despite this, numerical
tools still allow us to approximate the solutions to polynomial equations to
arbitrary degrees of accuracy.

In harmonic analysis, it is useful even to have rough picture of root
structure. We may be interested in the structure of the roots of real
polynomials or, indeed, the roots of polynomials over non-Archimedean fields
(in a suitable field extension). Such characterisations of root structure can
be used to estimate the associated sublevel sets or to bound corresponding
oscillatory integrals via the bounds of Phong and Stein [11].

The analysis contained herein is inspired by work of Kowalski and Wright, [6],
and an unpublished oscillatory integral estimate of Hickman and Wright [17],
Theorem 1.6. It takes the perspective of root clusters, in the spirit of the
famous oscillatory integral estimates of Phong and Stein. We find this to be a
timely moment to make these results, which appeared as part of the author’s
thesis [15], public, as the authors Hickman and Wright have recently shared
work utilising a similar approach [4]. Their presentation is focused on the
non-Archimedean context, but the broader applicability of their arguments is
indicated. Though our analysis is carried out over $\mathbb{R}$, it is likely
that the proofs contained herein are valid over other fields. Indeed, the
proofs are likely cleaner in the non-Archimedean setting as is the case in [6]
and the recent [4].

Before preparing to state our main results, let us note of the important
connections that have been found with the polynomial root finding literature.
Perhaps the most significant are to be found in works by Schönhage [13] and
Bini [2], which we discuss momentarily. Also of note is the fact that root
finding algorithms must carefully account for the ways in which roots can come
close or overlap, which, for example, can cause a break-down in a first order
Newton-Raphson iteration. Much of this literature is concerned with the real
or complex case and makes use of tools fitted to this context such as Rouché’s
theorem. Our work makes use of basic metric properties of $\mathbb{C}$ and its
valuation and is thus likely applicable in other fields. Not all complex root-
finding techniques make use of tools specialised to that context: there is,
for example, an early work by van Vleck [14] which considers polynomials with
sparse exponents and works via the consideration of the vanishing symmetric
functions of roots, as we do. Readers interested in a more comprehensive
perspective on related ideas in polynomial root finding are directed to, for
example, [9] and [7]. Following this history, there are now highly efficient
procedures for complex polynomial root finding [10].

The approximate factorisation method of Schönhage [13] is an effectively
parallelisable algorithm, which can be useful for a localised root finding.
Nevertheless, it involves the calculation of complex residues via a costly
integration procedure. Our later rough factorisation theorem, which is
directly expressed in terms of the polynomial coefficients, may provide a
useful initialisation for this method (or, indeed, other root finding
algorithms).

The root finding approach of Bini [2] makes use of suitably separated root
collections determined via the use of height estimates. Our more explicit
tools for determining the root structure of for polynomials with sparse
exponents, which appear later in our analysis, makes use of these same height
estimates. These height estimates can help us to determine in which annular
regions our different collections of roots lie.

In the case of sparse polynomials, our results may provide some useful
information for root finding algorithms narrowing the scope of the
pathological cases wherein roots coalesce. Indeed, algorithms to identify
appropriate root clusters are the subject of contemporary research [5] [1]. On
the one hand, the results of this paper bound the size of root clusters that
might need to be considered. On the other hand, the root cell covering
appearing arising in our rough factorisation analysis may be viewed as the
construction of appropriate root clusters.

To prepare the statement of our main theorem, let us now consider a couple of
representative examples. Consider the polynomial

$\Psi_{1}(t)=x+y_{1}t+y_{2}t^{2}+\ldots y_{L}t^{L},$

with $x,y_{L}\neq 0$. We know, by the fundamental theorem of algebra, that
$\Psi_{1}$ has $L$ roots, counted with multiplicity. In particular, for some
small $\epsilon>0$, we know that, for any root $w$, at most $L$ roots are
contained in $B(w,\epsilon|w|)$, which is, of course, trivial. Now consider
the polynomial

$\Psi_{k}(t)=\Psi_{1}(t^{k}).$

Corresponding to each root of $w$ of $\Psi_{1}$, we see that there are $k$
roots of $\Psi_{k}$, these are the $k$th roots of $w$. As before, we also have
that, for some small $\epsilon>0$, and for any root $w$, at most $L$ roots are
contained in $B(w,\epsilon|w|)$. See Figures 2 and 2 for a sketch of the roots
of $\Psi_{1}$ and $\Psi_{k}$, respectively, in the case that $L=4$, $k=5$, and

$\Psi_{1}(t)=y_{L}(t-h_{1})(t-h_{2})(t-h_{3})(t+h_{4}).$

More specifically, these figures are sketches of root structure in the case
where $h_{1}\gg h_{2}\approx h_{3}\gg h_{4}>0$. The dotted black circle
corresponds to roots with modulus $h_{1}$. The solid blue lines correspond to
roots with modulus close to $h_{2}$. The dashed red line corresponds with
roots of modulus $h_{4}$. However, for any choice $h_{j}$ one can see we have
the following. For some suitable small $\epsilon>0$ and for any root
$w^{\prime}$ of $\Psi_{k}$, there are at most $L=4$ roots contained in
$B(w^{\prime},\epsilon|w^{\prime}|)$.111In fact, for the sketched case, due to
the indicated strong separation of root heights $h_{1}\gg h_{2}$ and $h_{3}\gg
h_{4}$, we have at most $L=2$ roots contained in such a ball. This is
suggestive of refinements that can be made to our structural statements under
additional restrictions on the polynomial coefficients. This particular
example reflects polynomial root structure more generally, as we outline in
Theorem 1.1.

Figure 1. The roots of $\Psi_{1}$.

Figure 2. The roots of $\Psi_{k}$.

######  Theorem 1.1.

We fix a set of exponents $0=k_{0}<k_{1}<k_{2}<\ldots<k_{L}$ and consider real
polynomials whose exponents are drawn from this set. For any real polynomial
$\Psi(t)=x+y_{1}t^{k_{1}}+y_{2}t^{k_{2}}+\ldots+y_{L}t^{k_{L}}$ with
$x,y_{L}\neq 0$, we have the following structure.

The roots of $\Psi$ are stratified into $s$ tiers of roots
$\mathcal{T}_{1},\mathcal{T}_{2},\ldots,\mathcal{T}_{s}$, for some suitable
$1\leq s\leq L$. The tiers are separated in the sense that, if we take
$w_{i}\in\mathcal{T}_{i}$, then

$|w_{1}|\gg|w_{2}|\gg\ldots\gg|w_{s}|.$

For a suitable $1\leq L(\mathcal{T}_{r})\leq L$, at most $L(\mathcal{T}_{r})$
roots can cluster about a root: there is some suitable small parameter
$\epsilon$ such that, for all $w\in\mathcal{T}_{r}$, there are at most
$L(\mathcal{T}_{r})$ roots of $\Psi$ in $B(w,\epsilon|w|)$, counted with
multiplicity.

######  Remark 1.2.

Our main structural results are sharp in the sense that, we can construct a
polynomial with sparse exponents for which the tiers have repeated roots of
the largest degree permitted by our theorems. In particular, the polynomial

$\Psi(t)=\prod_{r=1}^{s}(t^{k}-h_{r}^{k})^{l_{r}},$

with $h_{1}\gg h_{2}\ldots\gg h_{s}$, is such that $L(\mathcal{T}_{r})=l_{r}$
(repeated) roots are contained in $B(w,\epsilon|w|)$ for any choice of
$w\in\mathcal{T}_{r}$, with $\mathcal{T}_{r}$ consisting of the $k$th roots of
$h_{r}^{k}$ of which appears with multiplicity $l_{r}$.

Let us recall the following structural result of Kowalski and Wright, Theorem
1.6 of [6]. The authors found application of this theorem to bound oscillatory
integrals as well as for estimating the measure of sublevel sets of
polynomials.

######  Theorem 1.3.

Let

$\Psi(t)=a_{k_{L}}t^{k_{L}}+a_{k_{L}-1}t^{k_{L}-1}+\ldots+a_{0}=a_{d}\prod_{j}(t-z_{j})$

be a complex polynomial with $\max_{l}|a_{l}|=1$. Suppose that the
coefficients satisfy $0<\gamma\leq|a_{k_{L}-k}|$ and
$|a_{k_{L}-j}|\leq\delta_{j}(\gamma)$, $0\leq j\leq k-1$ for some $0\leq k\leq
k_{L}$, where $\delta_{j}$ is some suitably small constant for each $0\leq
j\leq k-1$. Then there are exactly $k$ large roots $z_{1},z_{2},\ldots,z_{k}$
and the remaining roots are bounded. In particular, with ordered roots
$|z_{1}|\geq|z_{2}|\geq\ldots\geq|z_{k_{L}}|$, we have that

$\left(\frac{\gamma}{\max_{j}\delta_{j}}\right)^{\frac{1}{k_{L}}}\lesssim|z_{1}|,\ldots,|z_{k}|\text{
and }|z_{k+1}|,\ldots,|z_{k_{L}}|\lesssim 1.$

This result is notably similar to that of van Vleck [14] (following Montel
[8]), which provides an explicit upper bound for the smallest $k_{L}-k$ roots,
if we follow the above statement.

Further to Theorem 1.1, and analogous to Theorem 1.3, we are able to obtain
the following refined structural result.

######  Theorem 1.4.

We fix a set of exponents $0=k_{0}<k_{1}<k_{2}<\ldots<k_{L}$ and consider
certain polynomials whose exponents are drawn from this set. We consider real
polynomials

$\Psi(t)=x+y_{1}t^{k_{1}}+y_{2}t^{k_{2}}+\ldots+y_{L}t^{k_{L}}$

with $x,y_{L}\neq 0$ and $\max_{1\leq j\leq L}|y_{j}|=1$. Let
$\gamma\in(0,1]$. We suppose, additionally, that there exists $m$ such that

$\displaystyle|y_{m}|^{\frac{1}{k_{m}}}\geq\gamma,$ (1)
$\displaystyle\text{and, for }n>m,\;|y_{n}|^{\frac{1}{k_{n}}}\leq\delta,$

where $\delta=\delta(\gamma)>0$ is some suitably small constant. We have the
following refined structure for the roots of $\Psi$.

The roots of $\Psi$ may be stratified into $s=s(1)+s(2)$ tiers of roots
$\mathcal{T}_{1},\mathcal{T}_{2},\ldots,\mathcal{T}_{s}$, where $1\leq s\leq
L$, which are ordered and separated in the sense that, if we take
$w_{i}\in\mathcal{T}_{i}$, then

$|w_{1}|\gg|w_{2}|\gg\ldots\gg|w_{s}|.$

Furthermore, the tiers have the following additional structure.

We refer to each tier $\mathcal{T}_{r}$ with $1\leq r\leq s(1)$ as a large
tier. Likewise, we refer to any $\mathcal{T}_{r}$ with $s(1)<r\leq s(1)+s(2)$
as a small tier. We have that

$1\lesssim_{\gamma}|w|\text{ for }w\in\mathcal{T}_{r}\text{ with }1\leq r\leq
s(1)$ $\text{ and }|w|\lesssim_{\gamma}1\text{ for }w\in\mathcal{T}_{r}\text{
with }s(1)<r\leq s(1)+s(2).$

At most $L-m+1$ large roots can cluster about a point: there is some suitable
small parameter $\epsilon$ such that, for all $w\in\mathcal{T}_{r}$ with
$1\leq r\leq s(1)$, there are at most $L-m+1$ roots of $\Psi$ in
$B(w,\epsilon|w|)$. Furthermore, in the case that $s(2)\geq 1$, we have the
following improvement. For any small root, $w\in\mathcal{T}_{r}$ with
$s(1)<r\leq s(1)+s(2)$, $B(w,\epsilon|w|)$ can contain at most $m$ roots. For
any root $w$ in a large tier, $w\in\mathcal{T}_{r}$ with $1\leq r\leq s(1)$,
$B(w,\epsilon|w|)$ can contain at most $L-m$ roots.

######  Remark 1.5.

Other explicit refinements of the structure theorem, which are amenable to
direct calculation, are possible. These refinements can be achieved according
with our tier height estimation procedure, Lemma 8.1.

As mentioned above, we use these structural results to obtain bounds on
oscillatory integrals with polynomial phases. We consider polynomial phases

$\begin{split}\Phi(t)=xt+\frac{y_{1}}{k_{1}+1}t^{k_{1}+1}+\frac{y_{2}}{k_{2}+1}t^{k_{2}+1}+\ldots+\frac{y_{L}}{k_{L}+1}t^{k_{L}+1},\\\
\text{ with }1<k_{1}<k_{2}<\ldots<k_{L},\end{split}$ (2)

with $y_{L}\neq 0$. Given our main structure result, Theorem 1.4, one can make
use of an oscillatory integral bound for oscillatory integrals due to Phong
and Stein, Theorem 1.7. From this, it is possible to obtain an alternative
proof of the following unpublished oscillatory integral estimate due to
Hickman and Wright, [17]; see [15] for a presentation of their original proof.

######  Theorem 1.6.

For oscillatory integrals

$I(x,y)=\int_{\mathbb{R}}e^{i\Phi(t)}dt$

with phases $\Phi$ given by (2), we have that

$\left|I(x,y)\right|\lesssim\min_{j=1,2,\ldots,L}|y_{j}|^{-\frac{1}{k_{j}+1}},$

provided $k_{1}\geq L$.

A cluster, $\mathcal{C}$, is a non-empty subcollection of roots of
$\Phi^{\prime}$. We make use of the following result of Phong and Stein, [11].

######  Theorem 1.7.

Suppose that $\Phi$, (2), is a real polynomial such that $y_{L}\neq 0$ and
$\Phi^{\prime}$ has roots $z_{1},z_{2},\ldots,z_{k}$, counted with
multiplicity. Then we have the oscillatory integral estimate

$\left|I(x,y)\right|=\left|\int_{\mathbb{R}}e^{i\Phi(t)}dt\right|\leq
C_{k}\max_{j}\min_{\mathcal{C}\ni
z_{j}}\frac{1}{\left(|y_{L}|\prod_{l\notin\mathcal{C}}|z_{j}-z_{l}|\right)^{\frac{1}{|\mathcal{C}|+1}}},$

where the maximum is taken over roots $z_{j}$ and the minimum over clusters of
roots, $\mathcal{C}\subset\left\\{z_{1},z_{2},\ldots,z_{k}\right\\}$, such
that $z_{j}\in\mathcal{C}$.

In fact, our refined structural statement, Theorem 1.4 can be applied to
obtain a refined oscillatory integral estimate. Hickman and Wright established
the previous estimate, Theorem 1.6 and, as shown in [15], their method of
proof is capable of establishing the below result.

######  Theorem 1.8.

For oscillatory integrals

$I(x,y)=\int_{\mathbb{R}}e^{i\Phi(t)}dt$

with phases $\Phi$ given by (2), we have that

$\left|I(x,y)\right|\lesssim\min_{j=1,2,\ldots,L}|y_{j}|^{-\frac{1}{k_{j}+1}},$
(3)

provided $k_{1}\geq L$. More generally, if
$\max_{j}|y_{j}|^{\frac{1}{k_{j}}}=|y_{m}|^{\frac{1}{k_{m}}}$, then

$\left|I(x,y)\right|\lesssim\min_{j=1,2,\ldots,L}|y_{j}|^{-\frac{1}{k_{j}+1}},$

provided $k_{m}\geq L-m+1$.

The structural analysis of polynomial roots in this part is expected to hold
with respect to polynomials over fields other than $\mathbb{R}$. This
corresponds with the arguments in [6], which are presented for non-Archimedean
fields but also hold over $\mathbb{R}$. Wright has developed a framework for
the study of oscillatory integrals over fields other than $\mathbb{R}$ and
proved analogues of the Phong-Stein cluster bound for such oscillatory
integrals. Using bounds for oscillatory integrals over $\mathbb{C}$ from [16],
one could obtain a complex analogue of Theorem 1.8; the proof would be the
same as the proof of Theorem 1.8, as the root structure we make use of depends
only on the size of the coefficients.

######  Theorem 1.9.

We consider complex oscillatory integrals

$I(x,y)=\int_{\mathbb{C}}e(\Phi(t))\phi(t)dt,$

with $\phi\in C_{c}^{\infty}(\mathbb{C})$ and $e(z)=e^{i(\Re(z)+\Im(z))}$. The
phases $\Phi$ we consider are given by

$\Phi(z)=xz+\frac{y_{1}}{k_{1}+1}z^{k_{1}+1}+\ldots+\frac{y_{L}}{k_{L}+1}z^{k_{L}+1},$

with $x,y_{1},\ldots,y_{L}\in\mathbb{C}$ and $y_{L}\neq 0$. We have that

$\left|I(x,y)\right|\lesssim\min_{j=1,2,\ldots,L}|y_{j}|^{-\frac{2}{k_{j}+1}},$
(4)

provided $k_{1}\geq L$. More generally, if
$\max_{j}|y_{j}|^{\frac{1}{k_{j}}}=|y_{m}|^{\frac{1}{k_{m}}}$, then

$\left|I(x,y)\right|\lesssim\min_{j=1,2,\ldots,L}|y_{j}|^{-\frac{2}{k_{j}+1}},$

provided $k_{m}\geq L-m+1$.

######  Remark 1.10.

Note that we have the exponents $\frac{2}{k_{j}+1}$ appearing on the right
hand side of (4), in distinction to the real case. This is a natural feature
of complex oscillatory integrals, as examples in [16] show.

The primary structural result, Theorem 1.1, is not framed for explicit
computation. For example, it makes reference to the _relative_ size of roots
rather than their _actual_ size. For applications, explicit size estimates are
desirable. Indeed, we outline a procedure for estimating the size of roots in
Lemma 8.1 and it is this procedure which allows us to strengthen the statement
of Theorem 1.1 to the refined structural result, Theorem 1.4.

There is one final component of our structural investigations. Our analysis
for tier stratification suggests the consideration of a factorised polynomial
expression, with distinct factors corresponding to distinct root tiers. This
is because of the way in which different coefficients are substantial in our
analysis of different root tiers. For monic polynomials, $\Psi$, we analyse
such a factorisation in Section 9. We find that the factorisation is
quantifiably close to the original polynomial $\Psi$. Furthermore, the root
structure of $\Psi$ is essentially preserved by its rough factorisation.

######  Theorem.

We consider monic polynomials

$x+y_{1}t^{k_{1}}+\ldots+y_{L-1}t^{k_{L-1}}+t^{k_{L}}.$

There exists a polynomial
$\widetilde{\Psi}=\prod_{l=1}^{s}\widetilde{\Psi}_{l}(t)$ which roughly
factorises $\Psi$ in the following sense.

The polynomial $\widetilde{\Psi}_{l}$ has roots,
$\widetilde{\mathcal{T}}_{l}$, which are all of mutually comparable magnitude.
Furthermore, for any choice of roots $w_{j}\in\widetilde{\mathcal{T}}_{j}$, we
have that

$|w_{1}|\gg|w_{2}|\gg\ldots\gg|w_{s}|.$

There exists a covering, $N(\mathcal{R})$, of the roots,
$\mathcal{R}\subset\mathbb{C}$, of $\Psi$ which satisfies the following. Each
connected component of $N(\mathcal{R})$, which we call a cell, is given by a
ball. Each root $w$ of $\Psi$ belongs to a unique cell, which has radius
$\ll\epsilon|w|$, with $\epsilon$ as in Theorem 1.1. Cells are strongly
separated in the sense that, for distinct cells $B$ and $B^{\prime}$,
$d(B,B^{\prime})\gg\max\\{\operatorname{diam}B,\operatorname{diam}B^{\prime}\\}$.

Roots of $\widetilde{\Psi}$ are close to the roots of $\Psi$ in the following
sense. For a cell $B$ containing exactly $m$ roots of $\Psi$, $B$ contains
exactly $m$ roots of $\widetilde{\Psi}$, and we also have that $1\leq m\leq
L$.

The rough factorisation $\widetilde{\Psi}$ is close to $\Psi$ in the following
sense. For $t\notin N(\mathcal{R})$,

$|\Psi(t)-\widetilde{\Psi}(t)|\ll|\Psi(t)|.$ (5)

######  Remark 1.11.

The constant in (5) can be made arbitrarily small provided the tier regime,
which we define in Section 5, is specified with sufficiently strong separation
between tiers. More concretely, provided we make suitable restrictions on the
coefficients, $x,y_{1},\ldots,y_{L}$, we can ensure the rough factorisation
$\widetilde{\Psi}$ is distinct from $\Psi$ and arbitrarily close to it. The
conditions on the coefficients required for such a close approximation may be
realised according with our height estimation lemma, Lemma 8.1.

###  2\. Overview

The critical observation that forms the foundation of this paper is that many
of the symmetric functions of the roots of $\Psi$ are vanishing. Those that
are sufficiently far from vanishing determine the size of the roots.
Additionally, they tell us how many roots might cluster about a point. We
denote the roots of $\Psi$ by $\mathcal{R}$, they may appear with multiplicity
and for this reason we follow a multi-set convention specified below. For at
most $L$ non-zero critical indices
$j\in\left\\{D_{1},D_{2},\ldots,D_{L}\right\\}$, we have that

$S_{j}(\mathcal{R})=\sum_{\begin{subarray}{c}|\mathcal{S}|=j\\\
\mathcal{S}\subset\mathcal{R}\end{subarray}}\prod_{z\in\mathcal{S}}(-z)\neq
0.$

In particular, these indices are given by $D_{1}=k_{L}-k_{L-1}$,
$D_{2}=k_{L}-k_{L-2}$, $\ldots$, $D_{L}=k_{L}-k_{0}=k_{L}$. Throughout, we
work with reference to these symmetric functions, as well as those which are
vanishing.

In Section 3, we introduce notation. In Section 4, we present a model example
for root structure and its relation to the polynomial coefficients
(corresponding to the symmetric functions).

The core of our structural analysis is developed in Part I. Indeed, Sections
5, 6, and 7 contain the proof of the main structure Theorem 1.1. This analysis
pays no great heed to the polynomial coefficients, $x,y_{1},\ldots,y_{L}$.
Indeed, the structural results we obtain in Part I depend implicitly on the
coefficients.

In Section 5, we use the vanishing of certain $S_{j}$ to provide a
stratification of the roots into tiers and formulate the symmetric equations
with respect to these tiers.

In Section 6 we characterise how clustering might occur _within_ a given tier
$\mathcal{T}$. Here, we analyse the simultaneous (near) vanishing of
particular $S_{j}(\mathcal{T})$ and determine when this is inconsistent with
many roots being close together. For this part of the analysis, we form a
series expansion of particular $S_{j}(\mathcal{T})$ in terms of highlighted
roots, which we suppose are close together. Section 7 contains the derivation
of the distinguished root expansion that we use to prove Theorem 6.1, which
concerns the root structure in a single tier.

In Part II, we build on the tools developed in Part I to reveal more explicit
root structure in specific instances. In Section 8, we outline an algorithm
for estimating the heights of root tiers. This height estimation procedure can
then be applied to polynomials satisfying the hypotheses of the refined
structure Theorem 1.4. The result we thus obtain feeds directly into our
previous work to give Theorem 1.4 as a corollary. Section 9 provides an
explicit rough factorisation,
$\widetilde{\Psi}=\prod_{l=1}^{s}\widetilde{\Psi}_{l}(t)$, of monic
polynomials $\Psi$. We show that the roots of $\Psi$ and the roots of
$\widetilde{\Psi}$ almost coincide.

Part III contains a proof of Theorem 1.8 and presents some more refined
oscillatory integral estimates. We also give examples for the sharpness of
some of the oscillatory integral estimates, these examples are also examples
of the sharpness of the structure theorems.

Acknowledgements. The author was supported by The Maxwell Institute Graduate
School in Analysis and its Applications, a Centre for Doctoral Training funded
by the UK Engineering and Physical Sciences Research Council (Grant
EP/L016508/01), the Scottish Funding Council, Heriot-Watt University and the
University of Edinburgh. This work was first presented as part of the author’s
thesis, [15].

The author would like to thank Jim Wright for the patient introduction of the
problem and many helpful conversations at the challenging initial stages of
remote working. The author would like to thank Kevin Hughes for some helpful
suggestions on the presentation of this work. The author would like to thank
Andrew Clausen for the signaling potential connections in the root-finding
literature. The author also wishes to shout out Nammy Wams.

###  3\. Notation

We here introduce some of the notation that we will be using throughout this
paper. We use $\varepsilon$ throughout, often with indexing subscripts, for
error terms that appear in the analysis, where we can have suitable control on
their size. Any $\varepsilon$ that appears will be the sum of (signed)
products of $k$ roots, for some $k$, with size bounds adapted to an
appropriate scale.

To account for repeated roots, it should be understood that we are working
with multi-sets. For example, $\\{1,1,1\\}$ should be considered a $3$-element
(multi-)set. One would more formally write this multi-set as
$\\{1^{(1)},1^{(2)},1^{(3)}\\}$, indexing set elements by their multiplicity,
so we can properly speak about distinct set elements. Another example is the
fundamental theorem of algebra, which may be expressed as follows. If $\Psi$
is a degree $k_{L}$ polynomial, then the (multi-)set of roots of $\Psi$, which
we denote by $\mathcal{R}$, contains $k_{L}$ elements.

We use $\mathcal{R}$ to denote the roots of $\Psi$. We also use $\mathcal{C}$,
$\mathcal{T}$, and $\mathcal{S}$ to denote appropriate subcollections of
roots. We use $\mathcal{K}$ and $\mathcal{D}$ to denote sets of integer
indices, these will be specified but should be thought of as the exponents of
terms in $\Psi$ and the differences between these exponents.

Throughout, we fix some ordering of the roots of
$\Psi(t)=x+y_{1}t^{k_{1}}+y_{2}t^{k_{2}}+\ldots+y_{L}t^{k_{L}}$:

$|z_{1}|\geq|z_{2}|\geq\ldots\geq|z_{k_{L}}|.$ (6)

Later, we will use the notation $w_{1},w_{2},\ldots,w_{k_{L}}$ when we wish to
take an arbitrary enumeration of the roots of $\Psi$.

Throughout this document $C$ will be used to denote a constant, its value may
change from line to line. We use the notation $X\lesssim Y$ or $Y\gtrsim X$ if
there exists some implicit constant $C$ such that $X\leq CY$. When we wish to
highlight the dependence of the implied constant $C$ on some other parameter,
say $C=C(M)$, we will use the notation $X\lesssim_{M}Y$. We use the notation
$X\ll Y$ or $Y\gg X$ if there exists some suitable large constant $D$ such
that $DX\leq Y$.

######  Definition 3.1.

Throughout, we consider elementary symmetric functions of (a subset of) roots
of $\Psi$,

$S_{j}(\mathcal{A})=\sum_{\mathcal{S}\subset\mathcal{A},|\mathcal{S}|=j}\prod_{z\in\mathcal{S}}(-z),$

where $\mathcal{A}$ is some subset of the roots of $\Psi$.

###  4\. A model example for root structure

Working by example, we now give an indication of the possible root structure
of a particular $\Psi$ and see how this relates to the coefficients. We
consider $\Psi$ with

$\Psi(t)=y_{2}\prod_{j=1}^{2}\left(t^{k_{1}}-\alpha_{j}^{k_{1}}\right).$

Note that all real polynomials $x+y_{1}t^{k_{1}}+y_{2}t^{2k_{1}}$ can be
expressed in this way. The roots of the polynomial $\Psi$ are easily
recognised: they appear as the $k_{1}$th roots of $\alpha_{1}^{k_{1}}$ and
$\alpha_{2}^{k_{1}}$. There are some qualitatively different scenarios for the
structure of these roots. These depend on the relative size of $\alpha_{1}$
and $\alpha_{2}$. They also depend on the cancellation between
$\alpha_{1}^{k_{1}}$ and $\alpha_{2}^{k_{1}}$. Without loss of generality,
suppose that $|\alpha_{1}|\geq|\alpha_{2}|$. In the case of positive
$\alpha_{1}$ and $\alpha_{2}$ with $k_{1}=9$, the roots of $\Psi$ are sketched
in Figure 3. Throughout the remainder of this section, $\epsilon$ is some
suitably small fixed parameter.

Figure 3. The roots of $\Psi$ for $k_{1}=9$ and positive $\alpha_{j}$.

Let us first consider the case where $\bm{\alpha_{2}=0}$ and
$\bm{\alpha_{1}\neq 0}$. Here, there are two tiers of roots. There are $k_{1}$
repeated $0$ roots and if we divide out the corresponding factor $t^{k_{1}}$
from $\Psi$ we are left with the polynomial
$y_{2}(t^{k_{1}}-\alpha_{1}^{k_{1}})$, from which the location of the non-zero
roots can be observed directly as the $k_{1}$th roots of
$-S_{k_{1}}(\mathcal{R})=-\frac{y_{1}}{y_{2}}=\alpha_{1}^{k_{1}}$. The non-
zero roots are in $\mathcal{T}_{1}$ and the tier $\mathcal{T}_{2}$ consists of
all zero roots. In this case, for roots $w\in\mathcal{T}_{1}$,
$\bm{B(w,\epsilon|w|)}$ contains only the root $\bm{w}$. Later on, being able
to decouple equations for large and small roots in a similar fashion will
critically allow us to analyse the structure of roots in distinct tiers.

The case that $\bm{\alpha_{1}^{k_{1}}}$ is close to
$\bm{-\alpha_{2}^{k_{1}}}$, in particular,
$|\alpha_{1}^{k_{1}}+\alpha_{2}^{k_{1}}|\ll|\alpha_{1}^{k_{1}}|$. The roots of
$\bm{\Psi}$ appear in one tier and they are close to being the $2k_{1}$th
roots of $-\alpha_{1}^{k_{1}}\alpha_{2}^{k_{1}}$: there are $2k_{1}=k_{2}$
roots $w_{j}$ with $|w_{j}|\sim|\alpha_{1}|$—such roots are in tier
$\mathcal{T}_{1}$. Within $\mathcal{T}_{1}$ the roots are separated in the
sense that, for roots $w\in\mathcal{T}_{1}$, $\bm{B(w,\epsilon|w|)}$ contains
only the root $\bm{w}$. Note that the coefficients of $t^{0}$, $t^{k_{1}}$,
and $t^{2k_{1}}$ in $\Psi$ reflect this behaviour in the fact that
$\left|\frac{x}{y_{2}}\right|^{\frac{1}{2k_{1}}}=\left|S_{2k_{1}}(\mathcal{R})\right|^{\frac{1}{2k_{1}}}=\left|\alpha_{1}^{k_{1}}\alpha_{2}^{k_{1}}\right|^{\frac{1}{2k_{1}}}\gg\left|\alpha_{1}^{k_{1}}+\alpha_{2}^{k_{1}}\right|^{\frac{1}{k_{1}}}=\left|S_{k_{1}}(\mathcal{R})\right|^{\frac{1}{k_{1}}}=\left|\frac{y_{1}}{y_{2}}\right|^{\frac{1}{k_{1}}}$.

The case where $\bm{|\alpha_{1}|}$ is comparable to $\bm{|\alpha_{2}|}$ but
the $t^{k_{1}}$ coefficient of $\Psi$,
$-y_{2}\left(\alpha_{1}^{k_{1}}+\alpha_{2}^{k_{1}}\right)$, does not display
significant cancellation, i.e.
$|\alpha_{1}^{k_{1}}+\alpha_{2}^{k_{1}}|\sim|\alpha_{1}^{k_{1}}|$. This
scenario has one tier of roots,
$\mathcal{T}_{1}=\\{z_{1},z_{2},\ldots,z_{k_{2}}\\}$. Here, all the roots are
of comparable size and $\bm{B(w,\epsilon|w|)}$ contains at most two roots for
any root
$\bm{w\in\mathcal{T}_{1}$}.Tworootswhichmightgetclosearethoserootswhichsharethesameargumentif$α_1^k_1$and$α_2^k_1$arerealvaluedwiththesamesign.Thecoefficientsof$t^0,t^k_1$,and$t^2k_1$in$Ψ$reflectthisbehaviourinthefactthat$$\left|\frac{x}{y_{2}}\right|^{\frac{1}{2k_{1}}}=\left|S_{2k_{1}}(\mathcal{R})\right|^{\frac{1}{2k_{1}}}=\left|\alpha_{1}^{k_{1}}\alpha_{2}^{k_{1}}\right|^{\frac{1}{2k_{1}}}\sim\left|\alpha_{1}^{k_{1}}+\alpha_{2}^{k_{1}}\right|^{\frac{1}{k_{1}}}=\left|\frac{y_{1}}{y_{2}}\right|^{\frac{1}{k_{1}}}=\left|S_{k_{1}}(\mathcal{R})\right|^{\frac{1}{k_{1}}}.$$\par
Finally,weconsiderthe\underline{\textbf{case
where}$\bm{0\neq|\alpha_{2}|\ll|\alpha_{1}|}$}.Hererootsof$Ψ$appearin\textbf{two
tiers}:thereare$k_1$roots$w_j,2$with$—w_j,2—=—α_2—$---suchrootsareintier$T_2$---andtheremaining$k_1$roots$w_l,1$satisfy$—w_l,1—=—α_1—$---suchrootsareintier$T_1$.Withineachtiertherootsareseparatedinthesensethat,$B(w,ϵ—w—)
contains only one root for any root
w∈T_j$.Wealsohaveseparationbetweentiers:givenroots$w_1,∈T_1$and$w_2∈T_2,—w_1—≫—w_2—$.Notethatthecoefficientsof$t^0,t^k_1$,and$t^2k_1$in$Ψ$reflectthisbehaviourinthefactthat$$\left|S_{2k_{1}}(\mathcal{R})\right|^{\frac{1}{2k_{1}}}=\left|\frac{x}{y_{2}}\right|^{\frac{1}{2k_{1}}}=\left|\alpha_{1}\alpha_{2}\right|^{\frac{1}{2}}<\left|\frac{y_{1}}{y_{2}}\right|^{\frac{1}{k_{1}}}=\left|S_{k_{1}}(\mathcal{R})\right|^{\frac{1}{k_{1}}}=\left|\alpha_{1}^{k_{1}}+\alpha_{2}^{k_{1}}\right|^{\frac{1}{k_{1}}}\sim|\alpha_{1}|$$and$$\left|S_{k_{1}}(\mathcal{T}_{2})\right|^{\frac{1}{k_{1}}}=|\alpha_{2}|\sim\left|\frac{\alpha_{1}^{k_{1}}\alpha_{2}^{k_{1}}}{\alpha_{1}^{k_{1}}+\alpha_{2}^{k_{1}}}\right|^{\frac{1}{k_{1}}}=\left|\frac{x}{y_{1}}\right|^{\frac{1}{k_{1}}}=\left|\frac{S_{2k_{1}}(\mathcal{R})}{S_{k_{1}}(\mathcal{R})}\right|^{\frac{1}{k_{1}}}$$$$\ll\left|\frac{y_{1}}{y_{2}}\right|^{\frac{1}{k_{1}}}=\left|\alpha_{1}^{k_{1}}+\alpha_{2}^{k_{1}}\right|^{\frac{1}{k_{1}}}\sim|\alpha_{1}|=\left|S_{k_{1}}(\mathcal{T}_{1})\right|^{\frac{1}{k_{1}}}.$$Theselastequationscorrespondtotheseparationofcertainheightestimates.Suchheightestimateswillnotformapartofourinitialstructuralanalysis,butweeventuallyconsiderthemmoreexplicitlyinSection\ref{sec:heightEst}.\par$

##  Part I Implicit root structure

In this part, we work to uncover some of the root structure of real
polynomials

$\Psi(t)=x+y_{1}t^{k_{1}}+\ldots+y_{L}t^{k_{L}},$

with exponents taken from a fixed set $\\{0,k_{1},\ldots,k_{L}\\}$ and
$x,y_{L}\neq 0$. Throughout, we denote the set of roots of $\Psi$ by
$\mathcal{R}$. Essentially, as there are at most $L+1$ non-vanishing
coefficients, we will find that at most $L$ roots can coalesce about a point.
Throughout this part, our analysis will be carried out with respect to
particular reference heights, $h_{1},h_{2},\ldots,h_{L}$, which depend
implicitly on a given polynomial $\Psi$. We postpone the discussion of more
explicit tools for locating roots to Part II.

###  5\. Root tier stratification

In this section, we work to stratify the roots into tiers. The stratification
of roots is suggested by the example in Section 4. With this in mind, we
define certain reference heights $h_{j}$ for the roots. Before proceeding, let
us introduce some useful indexing notation.

######  Definition 5.1.

We set

$\displaystyle d_{0}(\mathcal{R})=0,\,$ $\displaystyle
d_{1}(\mathcal{R})=k_{L}-k_{L-1},\,$ $\displaystyle\;\ldots\;$ $\displaystyle
d_{L}(\mathcal{R})=k_{1}-k_{0},\quad\text{and}$ (7) $\displaystyle
D_{0}(\mathcal{R})=d_{0}(\mathcal{R}),\,$ $\displaystyle
D_{1}(\mathcal{R})=d_{0}(\mathcal{R})+d_{1}(\mathcal{R}),\,$
$\displaystyle\;\ldots\;$ $\displaystyle
D_{L}(\mathcal{R})=d_{1}(\mathcal{R})+\ldots+d_{L}(\mathcal{R}).$

We also set
$\mathcal{D}(\mathcal{R})=\left\\{0,D_{1}(\mathcal{R}),\ldots,D_{L}(\mathcal{R})\right\\}$.

Note that $D_{j}(\mathcal{R})=k_{L}-k_{L-j}$, although we expressed it
slightly differently in the definition to emphasise that it is the sum of
consecutive $d_{i}$.

Throughout this section, we will be working with reference to _all_ roots,
$\mathcal{R}$, and so we suppress the argument of $D_{j}=D_{j}(\mathcal{R})$
and $d_{j}=d_{j}(\mathcal{R})$. Similarly, in this section, we set
$\mathcal{D}=\mathcal{D}(\mathcal{R})$. We also write $d(j)=d_{j}$ and
$D(j)=D_{j}$.

######  Definition 5.2.

According with the root ordering, (6), we define the reference heights
$h_{1}=|z_{1}|,h_{2}=|z_{D(1)+1}|,h_{3}=|z_{D(2)+1}|,\ldots,h_{L}=|z_{D(L-1)+1}|$.

The following Lemma 5.3 shows exactly why our Definition 5.2 is a sensible
one.

######  Lemma 5.3.

Suppose that, for some $1\leq j\leq k_{L}$, $S_{j}(\mathcal{R})=0$. Then
$|z_{j+1}|\sim|z_{j}|$.

As a consequence, since $S_{j}(\mathcal{R})=0$ for
$j\notin\mathcal{D}=\\{0,D_{1},D_{2},\ldots,D_{L}\\}$, we have that

$\displaystyle h_{1}$ $\displaystyle=|z_{1}|$ $\displaystyle\sim|z_{2}|$
$\displaystyle\sim\ldots$ $\displaystyle\sim|z_{D(1)}|,$ (8) $\displaystyle
h_{2}$ $\displaystyle=|z_{D(1)+1}|$ $\displaystyle\sim|z_{D(1)+2}|$
$\displaystyle\sim\ldots$ $\displaystyle\sim|z_{D(2)}|,$ $\displaystyle\vdots$
$\displaystyle h_{L}$ $\displaystyle=|z_{D(L-1)+1}|$
$\displaystyle\sim|z_{D(L-1)+2}|$ $\displaystyle\sim\ldots$
$\displaystyle\sim|z_{D(L)}|.$

###### Proof.

Suppose that $S_{j}(\mathcal{R})=0$ and consider the corresponding root
$z_{j}$. There are two cases to consider. In the case that $|z_{j}|=0$, the
desired comparison follows directly from the inequality
$|z_{j+1}|\leq|z_{j}|=0$.

It remains to consider the case that $z_{j}\neq 0$. The largest root outwith
$\\{z_{1},z_{2},\ldots,z_{j}\\}$ is $z_{j+1}$. Additionally, the largest $j-1$
roots within $\\{z_{1},z_{2},\ldots,z_{j}\\}$ are
$z_{1},z_{2},\ldots,z_{j-1}$. Thus we find that

$0=|S_{j}|\geq|(-z_{1})(-z_{2})\ldots(-z_{j})|-\binom{k_{L}}{j}|z_{1}\ldots
z_{j-1}z_{j+1}|.$

Rearranging and dividing through by $|(-z_{1})(-z_{2})\ldots(-z_{j})|$ gives
the desired inequality. ∎

######  Remark 5.4.

The constants of comparison we obtain in (8) can be chosen to depend on the
indices $k_{1},k_{2},\ldots,k_{L}$.

In the statement of Theorem 1.1, we said that tiers of roots are well
separated. It is thus natural, and in accordance with Lemma 5.3, to define the
tiers of roots relative to the separation of the reference heights.

######  Definition 5.5.

If we have that

$h_{1}\sim h_{2}\sim\ldots\sim h_{l(1)}$ $\gg h_{l(1)+1}\sim\ldots\sim
h_{l(1)+l(2)}$ $\vdots$ $\gg h_{l(1)+\ldots+l(s-1)+1}\sim\ldots\sim
h_{l(1)+\ldots+l(s)}=h_{L},$

then we define the tiers as follows. First, let $l(0)=0$ and
$L(i)=l(0)+l(1)+\ldots+l(i)$. Then we set

$\mathcal{T}_{i}=\left\\{z_{D(L(i-1))+1},z_{D(L(i-1))+2}\ldots,z_{D(L(i))}\right\\}.$

We also define the reference height for the tiers by

$h(\mathcal{T}_{r})=h_{L(r-1)+1}.$

This definition establishes the first part of our structure theorem, Theorem
1.1. Indeed, by Lemma 5.3, we have that, for any choice of
$w_{i}\in\mathcal{T}_{i}$

$|w_{1}|\gg|w_{2}|\gg\ldots\gg|w_{s}|.$

######  Remark 5.6.

The choice of separation constants defining the tier regime must be suitably
strong. Having a well separated tier regime will ensure we have suitable
control on error terms. In this section, up to an error term, we derive
explicit equations for the symmetric functions of roots in a given tier. The
error terms must be small enough to feed into our later Theorem 6.1. For the
rough factorisation of monic $\Psi$, Theorem 9.2, the definition of a tier
regime requires much stronger separation, as we will see in Section 9.

Analogous to Definition 7, it will be useful to have distinguished indices for
each tier. These distinguished indices will later allow us to pick out
critical symmetric functions of roots within each tier.

######  Definition 5.7.

In the tier $\mathcal{T}_{r}$, we set

$\begin{split}d_{0}(\mathcal{T}_{r})=0,\,d_{1}(\mathcal{T}_{r})=d_{L(r-1)+1},\,d_{2}(\mathcal{T}_{r})=d_{L(r-1)+2},\;\ldots\;d_{l(r)}(\mathcal{T}_{r})=d_{L(r)},\,\text{and}\\\
D_{0}(\mathcal{T}_{r})=0,\,D_{1}(\mathcal{T}_{r})=d_{0}(\mathcal{T}_{r})+d_{1}(\mathcal{T}_{r}),\,\ldots\;D_{l(r)}(\mathcal{T}_{r})=d_{1}(\mathcal{T}_{r})+\ldots+d_{l(r)}(\mathcal{T}_{r}).\;\end{split}$
(9)

There is an appropriate $L(\mathcal{T}_{r})=l(r)=L(r)-L(r-1)$. Note that
$D_{l(r)}(\mathcal{T}_{r})=|\mathcal{T}_{r}|=D(L(r))-D(L(r-1))$, and we also
denote this by $D(\mathcal{T}_{r})$.

If $\mathcal{T}=\mathcal{T}_{r}$, then the distinguished indices for the
symmetric functions in $\mathcal{T}$ are given by
$\mathcal{D}(\mathcal{T})=\left\\{0,D_{1}(\mathcal{T}),\ldots,D_{L(\mathcal{T})}(\mathcal{T})\right\\}$.

We now present the main result of this section, this lemma characterises the
critical symmetric functions with respect to roots within each tier.

######  Lemma 5.8.

According with Definition 5.5, fix a tier $\mathcal{T}=\mathcal{T}_{r}$.

For the positive critical indices $j\in\mathcal{D}(\mathcal{T})$,

$S_{j}(\mathcal{T})=c_{j}(\mathcal{T})+\varepsilon_{j}(\mathcal{T}),$

where $|\varepsilon_{j}(\mathcal{T})|\ll h(\mathcal{T})^{j}$ and

$c_{j}(\mathcal{T})=\frac{S_{D(L(r-1))+j}(\mathcal{R})}{S_{D(L(r-1))}(\mathcal{T}_{1}\cup\mathcal{T}_{1}\cup\ldots\mathcal{T}_{r-1})}.$

For $j\notin\mathcal{D}(\mathcal{T})$, with $1\leq j\leq|\mathcal{T}|$, we
have that

$S_{j}(\mathcal{T})=\varepsilon_{j}(\mathcal{T}),$

where $|\varepsilon_{j}(\mathcal{T})|\ll h(\mathcal{T})^{j}$.

###### Proof.

We consider the symmetric functions of order $D(L(r-1))+j$ for $1\leq j\leq
D(\mathcal{T})$. For ease of notation, we set $D=D(L(r-1))$ and we denote the
reference height $h(\mathcal{T})=h_{L(r-1)+1}$ by $h$.

Splitting the sum defining symmetric functions according to the size of the
summands, we have that

$S_{D+j}(\mathcal{R})=S_{D}(\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\ldots\cup\mathcal{T}_{r-1})S_{j}(\mathcal{T})+\sum_{|\mathcal{S}^{\prime}|=D+j}\prod_{z\in\mathcal{S}^{\prime}}(-z),$
(10)

where the sum in $\mathcal{S}^{\prime}\subset\mathcal{R}$ is taken over
$\mathcal{S}^{\prime}\cap\left(\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\ldots\mathcal{T}_{r-1}\cup\mathcal{T}_{r}\right)^{c}\neq\emptyset$.
Any $\mathcal{S}^{\prime}$ appearing in this proof should be understood as
subject to these restrictions. Note that

$|S_{D}(\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\ldots\cup\mathcal{T}_{r-1})|=|z_{1}z_{2}\ldots
z_{D}|.$

Every product appearing in

$\sum_{|\mathcal{S}^{\prime}|=D+j}\prod_{z\in\mathcal{S}^{\prime}}(-z)$

contains at least one root, $z$, outwith
$\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\ldots\cup\mathcal{T}_{r}$ and, for any
such $z$, $|z|\ll h$. The largest $D+j-1$ roots are
$z_{1},z_{2},\ldots,z_{D+j-1}$. Thus we see that

$\left|\sum_{|\mathcal{S}^{\prime}|=D+j}\prod_{z\in\mathcal{S}^{\prime}}(-z)\right|\ll\left|z_{1}z_{2}\ldots
z_{D+j-1}h\right|.$

Normalising and rearranging (10) we thus see that

$S_{j}(\mathcal{T})=S_{D}(\mathcal{T}_{1}\cup\mathcal{T}_{1}\cup\ldots\cup\mathcal{T}_{r-1})^{-1}S_{D+j}(\mathcal{R})+\varepsilon_{j}(\mathcal{T}),$

where

$\varepsilon_{j}(\mathcal{T})=-S_{D}(\mathcal{T}_{1}\cup\mathcal{T}_{1}\cup\ldots\cup\mathcal{T}_{r-1})^{-1}\sum_{|\mathcal{S}^{\prime}|=D+j}\prod_{z\in\mathcal{S}^{\prime}}(-z).$

To conclude, we observe that

$\left|\varepsilon_{j}(\mathcal{T})\right|\ll\left|z_{D+1}z_{D+2}\ldots
z_{D+j-1}h\right|\sim h^{j},$

as required. ∎

###  6\. Root structure within tiers

Recall how we defined the tiers of roots in Definition 5.5, which immediately
gives the separation between tiers and part of Theorem 1.1. In the regime with
tiers $\mathcal{T}_{1},\mathcal{T}_{2},\ldots,\mathcal{T}_{s}$, we have that

$h(\mathcal{T}_{1})\gg h(\mathcal{T}_{2})\gg\ldots\gg h(\mathcal{T}_{s}),$

where $h(\mathcal{T}_{r})=\max_{w\in\mathcal{T}_{r}}|w|$. To complete the
proof of Theorem 1.1, we must establish the structure of roots _within_ a
tier. In this section, we prove Theorem 6.1, which, combined with Lemma 5.8,
gives the structure Theorem 1.1.

Let us fix $\mathcal{T}=\mathcal{T}_{r}$ for some $r$, where we have that
$h(\mathcal{T})=h_{L(r-1)+1}>0$. For ease of notation, throughout this
section, we denote by $h$ the reference height for roots in $\mathcal{T}_{r}$,
$h=h(\mathcal{T}_{r})=h_{L(r-1)+1}$. With care, we can leverage the statement
of Lemma 5.8 to determine how roots in $\mathcal{T}$ may cluster about a
point.

Recall from Lemma 5.8 that, for $j\notin\mathcal{D}(\mathcal{T})$,
$S_{j}(\mathcal{T})$ is near vanishing. The following theorem tells us what
kind kind of clustering can occur according to how many symmetric functions of
$\mathcal{T}$ are far from vanishing. In particular, we consider what happens
when the symmetric functions, $S_{j}(\mathcal{T})$, are near vanishing away
from some (unspecified) set of exceptional indices
$\widetilde{\mathcal{D}}(\mathcal{T})\subset\mathcal{D}(\mathcal{T})$.

######  Theorem 6.1.

Suppose that, for $0\leq j\leq D(\mathcal{T})$,

$S_{j}(\mathcal{T})=\varepsilon_{j}(\mathcal{T}),\text{ for
}j\notin\widetilde{\mathcal{D}}(\mathcal{T}),$

where $|\varepsilon_{j}(\mathcal{T})|\ll h^{j}$ and
$\widetilde{\mathcal{D}}(\mathcal{T})\subset\mathcal{D}(\mathcal{T})$. Then at
most
$\tilde{L}(\mathcal{T})\coloneqq|\widetilde{\mathcal{D}}(\mathcal{T})|-1\leq|\mathcal{D}(\mathcal{T})|-1=L(\mathcal{T})$
roots in $\mathcal{T}$ can cluster about a point. More precisely, there is is
some suitably small $\epsilon>0$ such that, for any root $w\in\mathcal{T}$, we
have $|w|\sim h>0$ and $B(w,\epsilon h)$ contains at most
$\tilde{L}(\mathcal{T})$ roots $w_{i}\in\mathcal{T}$.

We have as a corollary of Theorem 6.1 and Lemma 5.8 the following structure
theorem, of which Theorem 1.1 is a special case.

######  Theorem 6.2.

We fix a set of exponents $0=k_{0}<k_{1}<k_{2}<\ldots<k_{L}$ and consider real
polynomials whose exponents are drawn from this set. For any real polynomial
$\Psi(t)=x+y_{1}t^{k_{1}}+y_{2}t^{k_{2}}+\ldots+y_{L}t^{k_{L}}$ with
$x,y_{L}\neq 0$, we have the following.

We suppose that the polynomial coefficients $(x,y)$ are such that we are in
the tier regime indexed by $(l_{1},l_{2},\ldots,l_{s})$ in Definition 5.5.

The roots of $\Psi$ are stratified into $s$ tiers of roots
$\mathcal{T}_{1},\mathcal{T}_{2},\ldots,\mathcal{T}_{s}$, where $1\leq s\leq
L$. The tiers are separated in the sense that, if we take
$w_{i}\in\mathcal{T}_{i}$, then

$|w_{1}|\gg|w_{2}|\gg\ldots\gg|w_{s}|.$

At most $L(\mathcal{T}_{r})=l_{r}\leq L$ roots can cluster about a root: there
is some suitable small parameter $\epsilon$ such that, for all
$w\in\mathcal{T}_{r}$, there are at most $L(\mathcal{T}_{r})=l_{r}$ roots of
$\Psi$ in $B(w,\epsilon|w|)$.

We have expressed Theorem 6.1 in a slightly more general form than is required
to prove Theorem 1.1. As a black box, Theorem 6.1 can give improvements to our
main structure Theorem 1.1. Indeed, if it is applied with reference to our
later Proposition 8.2, we can obtain 1.4. It is for this reason we have framed
the theorem in terms of critical indices $\widetilde{\mathcal{D}}$, rather
than $\mathcal{D}$, since some of the symmetric functions indexed by
$\mathcal{D}$ might still be close to vanishing. Nevertheless, all of the
tildes appearing in this section can safely be ignored on first reading under
the assumption that there is only one tier as all of the essential ideas are
contained in this case.

In this section, roots in $\mathcal{T}$ _are not_ ordered in terms of size:
$w_{1},w_{2},\ldots,w_{D(\mathcal{T})}$ is some enumeration of the roots in
$\mathcal{T}$. Our analysis works by highlighting some of these roots,
$\mathpzc{h}\subset\mathcal{T}$, which we will assume are close together. We
expand the symmetric functions in terms of these highlighted roots. We will
recover some structural statements about the roots from the highlighted
expansions. We denote the excluded roots by
$\mathpzc{e}=\mathcal{T}\backslash\mathpzc{h}$.

First, we state the following lemma, which is verified at a glance.

######  Lemma 6.3.

Let $\mathpzc{h}\subset\mathcal{T}$ with $|\mathpzc{h}|=m$. Then

$S_{D(\mathcal{T})-m}(\mathcal{T})=\sum_{l=0}^{\min\\{m,D(\mathcal{T})-m\\}}S_{l}(\mathpzc{h})S_{D(\mathcal{T})-m-l}(\mathpzc{e}).$

Since we will be investigating highlighted roots that are close together, we
distinguish one of these roots to further refine the expansion. By a suitable
recursive procedure, which is outlined in Section 7, we can apply Lemma 6.3 to
obtain the following.

######  Lemma 6.4.

Set

$a_{m}(j)=(-1)^{j-1}\binom{m-1+j}{m-1}.$

Suppose we have $m$ highlighted roots
$\mathpzc{h}=\left\\{w_{1},w_{2},\ldots,w_{m}\right\\}\subset\mathcal{T}$.
Then,

$S_{D(\mathcal{T})-m}(\mathcal{T})=(-w_{m+1})(-w_{m+2})\ldots(-w_{D(\mathcal{T})})$
$+\sum_{j=1}^{D(\mathcal{T})-m}a_{m}(j)(-w_{1})^{j}S_{D(\mathcal{T})-m-j}(\mathcal{T})+\varepsilon_{D(\mathcal{T})-m},$

where

$|\varepsilon_{D(\mathcal{T})-m}|\lesssim\max_{w,w^{\prime}\in\mathpzc{h}}{|w-w^{\prime}|}h^{D(\mathcal{T})-m-1},$

if $m\geq 2$ and $\varepsilon_{D(\mathcal{T})-m}=0$ if $m=1$.

######  Remark 6.5.

It may appear that there is an error in the statement of Lemma 6.4, due to the
apparent double counting of certain expressions. However, these are accounted
for in the error term. The reason we desire such a series expansion is because
those expressions $S_{D(\mathcal{T})-m-j}(\mathcal{T})$ are much more explicit
than, for example, $S_{D(\mathcal{T})-m-j}(\mathpzc{e})$. Indeed, we can
relate $S_{D(\mathcal{T})-m-j}(\mathcal{T})$ to the coefficients of our
original polynomial via Lemma 5.8 and we have no such tools for
$S_{D(\mathcal{T})-m-j}(\mathpzc{e})$ or $S_{j}(\mathpzc{h})$.

Recall Definition 5.7, the definition of distinguished indices for a tier,
$\mathcal{D}(\mathcal{T})$. It will also be necessary to count backwards from
$D(\mathcal{T})$ to $0$ and pick out corresponding critical symmetric
functions of roots in the tier. We make the following further definition of
distinguished exponents for a given tier $\mathcal{T}=\mathcal{T}_{r}$.

######  Definition 6.6.

We set $k_{0}(\mathcal{T})=0$,

$k_{1}(\mathcal{T})=d_{L(r)},\,k_{2}(\mathcal{T})=d_{L(r)}+d_{L(r)-1},\,\ldots\;k_{L(\mathcal{T})}(\mathcal{T})=d_{L(r)}+\ldots+d_{L(r-1)+1}.$
(11)

Note that $k_{L(\mathcal{T})}(\mathcal{T})=D(\mathcal{T})$. We denote by
$\mathcal{K}(\mathcal{T})$ these exponents. Note that

$\mathcal{K}(\mathcal{T})=D(\mathcal{T})-\mathcal{D}(\mathcal{T})=\left\\{D(\mathcal{T}),D(\mathcal{T})-D_{1}(\mathcal{T}),\ldots,0\right\\}.$

According with Theorem 6.1, if we have $\tilde{L}(\mathcal{T})+1$
distinguished indices
$0=\tilde{D}_{0}(\mathcal{T})<\tilde{D}_{1}(\mathcal{T})<\ldots<\tilde{D}_{\tilde{L}(\mathcal{T})}(\mathcal{T})=D(\mathcal{T})$,
given as
$\widetilde{\mathcal{D}}(\mathcal{T})\subset\mathcal{D}(\mathcal{T})$, then,
corresponding with the above, we set
$\widetilde{\mathcal{K}}(\mathcal{T})=D(\mathcal{T})-\widetilde{\mathcal{D}}(\mathcal{T})$.
Naturally, we enumerate $\widetilde{\mathcal{K}}(\mathcal{T})$ by
$0=\tilde{k}_{0}<\tilde{k}_{1}<\ldots<\tilde{k}_{\tilde{L}(\mathcal{T})}$.

With this notation and our series expansion tools, we are now ready to carry
out the analysis of how roots can cluster within $\mathcal{T}$.

###### Proof of Theorem 6.1.

In this proof, we use the notation $D=D(\mathcal{T})=|\mathcal{T}|$,
$\tilde{L}=\tilde{L}(\mathcal{T})=|\widetilde{\mathcal{D}}(\mathcal{T})|-1$,
$\tilde{D}(j)=\tilde{D}_{j}(\mathcal{T})$,
$\tilde{k}_{j}=\tilde{k}_{j}(\mathcal{T})$.

We suppose, by way of contradiction, that, given some small $\epsilon>0$,
there exist roots $w_{1},w_{2},\ldots,w_{\tilde{L}+1}\in B(w_{1},\epsilon
h)\cap\mathcal{T}.$ Working with the symmetric functions
$S_{D-1}(\mathcal{T}),$ $S_{D-2}(\mathcal{T}),$ $\ldots,$
$S_{D-(\tilde{L}+1)}(\mathcal{T})$ we will derive a system of equations which
has no solution.

We can apply Lemma 6.4 to obtain the following. For highlighted roots
$\mathpzc{h}\subset\\{w_{1},w_{2},\ldots,w_{\tilde{L}+1}\\}\subset\mathcal{T}$
containing $m$ elements, we have

$S_{D-m}(\mathcal{T})=(-w_{m+1})(-w_{m+2})\ldots(-w_{D})+\sum_{j=1}^{D-m}a_{m}(j)(-w_{1})^{j}S_{D-m-j}(\mathcal{T})+\varepsilon_{D-m}(\mathpzc{h}),$

where $|\varepsilon_{D-m}(\mathpzc{h})|\ll h^{D-m}$. For $m+1\leq
l\leq\tilde{L}+1$, replacing instances of $(-w_{l})$ with
$(-w_{1})+((-w_{l})-(-w_{1}))$ and observing that $|w_{l}-w_{1}|\leq\epsilon
h$, we find that

$S_{D-m}(\mathcal{T})$
$=(-w_{1})^{\tilde{L}+1-m}(-w_{\tilde{L}+2})(-w_{\tilde{L}+3})\ldots(-w_{D})+\sum_{j=1}^{D-m}a_{m}(j)(-w_{1})^{j}S_{D-m-j}(\mathcal{T})+\varepsilon_{D-m}^{(1)},$

where $|\varepsilon_{D-m}^{(1)}|\lesssim\epsilon h^{D-m}$.

Dividing through by $(-w_{1})^{\tilde{L}+1-m}$, we obtain

$(-w_{1})^{m-(\tilde{L}+1)}S_{D-m}(\mathcal{T})$
$=(-w_{\tilde{L}+2})\ldots(-w_{D})+\sum_{j=1}^{D-m}a_{m}(j)(-w_{1})^{j+m-(\tilde{L}+1)}S_{D-m-j}(\mathcal{T})+\varepsilon_{D-m}^{(2)},$

where $|\varepsilon_{D-m}^{(2)}|\lesssim\epsilon h^{D-(\tilde{L}+1)}$.

Many of the terms appearing in the above sum are near vanishing. To pick out
the significant terms, we observe
$D-m-j\in\widetilde{\mathcal{D}}(\mathcal{T})$ requires that
$j=D(\mathcal{T})-\tilde{D}_{i}(\mathcal{T})-m$ for $0\leq i\leq\tilde{L}$.
The relevant set of indices $j$ is precisely the positive elements of
$\widetilde{\mathcal{K}}(\mathcal{T})-m$. Thus, we find

$\begin{split}&(-w_{1})^{m-(\tilde{L}+1)}S_{D-m}(\mathcal{T})\\\
=&(-w_{\tilde{L}+2})\ldots(-w_{D})+\sum_{\begin{subarray}{c}j\in\widetilde{\mathcal{K}}(\mathcal{T})-m\\\
j\geq
1\end{subarray}}^{D-m}a_{m}(j)(-w_{1})^{j+m-(\tilde{L}+1)}S_{D-m-j}(\mathcal{T})\\\
+&\varepsilon_{D-m}^{(3)},\end{split}$ (12)

where $\varepsilon_{D-m}^{(3)}$ is an error term with
$|\varepsilon_{D-m}^{(3)}|\lesssim\epsilon h^{D-(\tilde{L}+1)}$. The
normalised symmetric functions appearing in the sum are precisely
$(-w_{1})^{\tilde{k}_{i}-(\tilde{L}+1)}S_{\tilde{D}(\tilde{L}-i)}(\mathcal{T})$
where $\tilde{D}(\tilde{L}-i)\in\widetilde{\mathcal{D}}$ and
$\tilde{D}(\tilde{L}-i)<D-m$. Observe that, from Lemma 6.4, $a_{m}(0)=(-1)$ so
that, if $D-m\in\widetilde{\mathcal{D}}$, then (12) can be rearranged to

$\begin{split}\varepsilon_{D-m}^{(4)}&\\\
=&(-w_{\tilde{L}+2})\ldots(-w_{D})+\sum_{\begin{subarray}{c}j\in\widetilde{\mathcal{K}}(\mathcal{T})-m\\\
j\geq
0\end{subarray}}^{D-m}a_{m}(j)(-w_{1})^{j+m-(\tilde{L}+1)}S_{D-m-j}(\mathcal{T}),\end{split}$
(13)

where $\varepsilon_{D-m}^{(4)}$ is an error term with
$|\varepsilon_{D-m}^{(4)}|\ll h^{D-(\tilde{L}+1)}$. In fact, (13) is valid for
all $m$ since, if $D-m\notin\widetilde{\mathcal{K}}$, then
$|(-w_{1})^{m-(\tilde{L}+1)}S_{D-m}(\mathcal{T})|\ll h^{D-(\tilde{L}+1)}$.

We set

$\underline{v}=\begin{pmatrix}(-w_{\tilde{L}+2})(-w_{\tilde{L}+3})\ldots(-w_{D})\\\
(-w_{1})^{\tilde{k}_{1}-(\tilde{L}+1)}S_{D(\tilde{L}-1)}\\\ \vdots\\\
(-w_{1})^{\tilde{k}_{\tilde{L}}-(\tilde{L}+1)}S_{\tilde{D}(\tilde{L}-\tilde{L})}\end{pmatrix},\quad\underline{\varepsilon}=\begin{pmatrix}\varepsilon_{D-1}^{(4)}\\\
\vdots\\\ \varepsilon_{D-(\tilde{L}+1)}^{(4)}\end{pmatrix}.$

Bringing the equations (13) for $1\leq m\leq\tilde{L}+1$ together, we have a
matrix equation

$\underline{\varepsilon}=M\underline{v},$ (14)

with $M$ as specified below. Recall, from Lemma 6.4, that
$a_{m}(j)=(-1)^{j-1}\binom{m-1+j}{m-1}$ so that
$a_{m}(j-m)=(-1)^{j-m-1}\binom{j-1}{m-1}$.

Let us first give an example of $M$. When $\tilde{L}=2$, and $\tilde{k}_{1}>3$
we have

$M=\left({\begin{array}[]{ccc}1&(-1)^{\tilde{k}_{1}-2}&(-1)^{\tilde{k}_{2}-2}\\\
1&(-1)^{\tilde{k}_{1}-3}(\tilde{k}_{1}-1)&(-1)^{\tilde{k}_{2}-3}(\tilde{k}_{2}-1)\\\
1&(-1)^{\tilde{k}_{1}-4}\frac{1}{2}(\tilde{k}_{1}-2)(\tilde{k}_{1}-1)&(-1)^{\tilde{k}_{2}-4}\frac{1}{2}(\tilde{k}_{2}-2)(\tilde{k}_{2}-1)\\\
\end{array}}\right).$

Let us give an example of $M$ when it contains some zero entries. This
happens, for example, if $\tilde{L}=2$ and $\tilde{k}_{2}>3$ but
$\tilde{k}_{1}=2$. In this case,

$M=\left({\begin{array}[]{ccc}1&(-1)^{\tilde{k}_{1}-2}&(-1)^{\tilde{k}_{2}-2}\\\
1&-1&(-1)^{\tilde{k}_{2}-3}(\tilde{k}_{2}-1)\\\
1&0&(-1)^{\tilde{k}_{2}-4}\frac{1}{2}(\tilde{k}_{2}-2)(\tilde{k}_{2}-1)\\\
\end{array}}\right).$

In general, $M$ is an $(\tilde{L}+1)\times(\tilde{L}+1)$ matrix. According
with (13), we must be sensitive to whether $\tilde{\mathcal{K}}-m$ contains
negative elements distinct from $-m$ (as these do not appear in the sum). To
account for these, it is useful to express

$a_{m}(\tilde{k}_{b}-m)=\binom{\tilde{k}_{b}-1}{m-1}=\frac{1}{(m-1)!}\prod_{i=1}^{m-1}(\tilde{k}_{b}-i).$
(15)

For $b\geq 1$, the expression on the right hand side of (15) is equal to $0$
when $\tilde{k}_{b}<m$. If $b\geq 1$ and $\tilde{k}_{b}-(\tilde{L}+1)<0$,
then, for $m>\tilde{k}_{b}$,
$\frac{1}{(m-1)!}\prod_{i=1}^{m-1}(\tilde{k}_{b}-i)=0$. Observe also that
$1=\frac{(-1)^{-m-1}}{(m-1)!}\prod_{i=1}^{m-1}(0-i)$. Thus, for $1\leq
m\leq\tilde{L}+1$ and $1\leq b\leq\tilde{L}+1$ the matrix entry $M(m,b)$ is
given by

$M(m,b)=\frac{(-1)^{\tilde{k}_{b-1}-m-1}}{(m-1)!}\prod_{i=1}^{m-1}(\tilde{k}_{b-1}-i).$
(16)

We claim that $M$ is invertible. Let us suppose, for now, that the claim holds
and see how the result follows. Using the fact that $M$ is invertible, we find
from (14) that

$|\underline{\varepsilon}|\sim h^{D-(\tilde{L}+1)}.$

Throughout, we have tracked error terms so that $|\underline{\varepsilon}|\ll
h^{D-(\tilde{L}+1)}$. As such, we have a contradiction. Therefore,
$B(w_{1},\epsilon|w_{1}|)$ can contain _at most_ $\tilde{L}$ roots.

Let us now prove the claim. First, lets multiply the $j$th column of $M$ by
$(-1)^{\tilde{k}_{j}}$ and call the resulting matrix $\widetilde{M}$. We work
to show the column vectors of $\widetilde{M}$ are linearly independent via a
Taylor expansion. Observe that the columns of $\widetilde{M}$ are evaluations
of the vector polynomial

$\underline{p}(t)=\begin{pmatrix}1\\\ -(t-1)\\\ \frac{1}{2!}(t-1)(t-2)\\\
\vdots\\\
(-1)^{\tilde{L}}\frac{1}{\tilde{L}!}(t-1)(t-2)\ldots(t-\tilde{L})\end{pmatrix}$

at the points $t=0,\tilde{k}_{1}$, $\ldots$ $\tilde{k}_{\tilde{L}}$.
Considering the Maclaurin expansion, we can express $p(t)$ as a matrix
transformation of the curve,

$\underline{q}(t)=\begin{pmatrix}1\\\ t\\\ \frac{1}{2!}t^{2}\\\ \vdots\\\
\frac{1}{\tilde{L}!}t^{\tilde{L}}\end{pmatrix}.$

Note that, since the $j$th component of $\underline{p}$ is a degree $j-1$
polynomial, we can write

$\underline{p}(t)=T\underline{q}(t),$

where $T$ is an upper triangular matrix. It is easy to see that, along the
diagonal, the entries are non-zero, so that $T$ is invertible. It is well
known that $\tilde{L}$ distinct points on the moment curve

$\underline{r}(t)=\begin{pmatrix}t\\\ \frac{1}{2!}t^{2}\\\ \vdots\\\
\frac{1}{(\tilde{L})!}t^{\tilde{L}}\end{pmatrix}$

are in general position. We thus see that

$\dim\operatorname{span}\left\\{\underline{q}(0),\underline{q}(\tilde{k}_{1}),\ldots,\underline{q}(\tilde{k}_{\tilde{L}})\right\\}$
$=1+\dim\operatorname{span}\left\\{\underline{r}(\tilde{k}_{1}),\ldots,\underline{r}(\tilde{k}_{\tilde{L}})\right\\}$
$=\tilde{L}+1.$

We also know, since $T$ is invertible, that

$\dim\operatorname{span}\left\\{T\underline{q}(0),T\underline{q}(\tilde{k}_{1}),\ldots,T\underline{q}(\tilde{k}_{\tilde{L}})\right\\}$
$=\dim\operatorname{span}\left\\{\underline{q}(0),\underline{q}(\tilde{k}_{1}),\ldots,\underline{q}(\tilde{k}_{\tilde{L}})\right\\}$
$=\tilde{L}+1.$

Therefore, the column vectors of $\widetilde{M}$ are linearly independent,
completing the proof that $\widetilde{M}$, and thus $M$, is invertible. ∎

###  7\. A series expansion lemma; proof of Lemma 6.4

In this section, we work to prove our main series expansion Lemma 6.4. The
work is of a rather combinatorial flavour. Lemma 6.4 is a corollary of Lemmas
7.1 and 7.2.

######  Lemma 7.1.

For $m$ highlighted roots, $\mathpzc{h}$, including $w_{1}$ and $D-m$ excluded
roots $\mathpzc{e}=\mathcal{T}\backslash\mathpzc{h}$, the symmetric function
$S_{D-m}(\mathcal{T})$ can be expressed as

$S_{D-m}(\mathcal{T})=S_{D-m}(\mathpzc{e})+\sum_{j=1}^{D-m}a_{m}(j,m)(-w_{1})^{j}S_{D-m-j}(\mathcal{T})+\varepsilon_{D-m},$

where
$|\varepsilon_{D-m}|\lesssim\max_{w,w^{\prime}\in\mathpzc{h}}|w-w^{\prime}|h^{D-m}$,
if $D\geq m\geq 2$, and $\varepsilon_{D-m}=0$, if $m=1$. The coefficients
$a_{m}(j,m)$ are outlined in the following. We first set
$b=\max\\{1,m-(D-m)+1\\}$. We have that $a_{m}(\cdot,\cdot)$ is the solution
of the below recurrence relation:

$\begin{split}a_{m}(1,m)=\binom{m}{m-1},a_{m}(1,m-1)=\binom{m}{m-2},\ldots,a_{m}(1,b)=\binom{m}{b-1},\\\
a_{m}(1,l)=0\text{, for }l\leq b-1\text{ or }l\geq m+1,\\\
a_{m}(j+1,l)=a_{m}(j,l-1)\text{, for }l\leq b-1\text{ or }l\geq m+1,\\\
a_{m}(j+1,l)=-\binom{m}{l-1}a_{m}(j,m)+a_{m}(j,l-1)\text{, for }b\leq l\leq
m.\end{split}$ (17)

In the case that $m\leq D-m$, i.e. $b=1$, we include a figure representing a
step of the recursion for those $1\leq l\leq m$. Figure 4 represents the
dynamics taking us one step from
$\left\\{a_{m}(j,m),\ldots,a_{m}(j,1)\right\\}$ to
$\left\\{a_{m}(j+1,m),\ldots,a_{m}(j+1,1)\right\\}$, where each arrow
represents addition. We suppress the first argument of $a_{m}$.

Figure 4. A step of the recursion (17).

######  Lemma 7.2.

Let $a_{m}(\cdot,\cdot)$ satisfy the recurrence relation (17). For $b\leq
l\leq m$ and $1\leq j\leq D-m$,

$a_{m}(j,l)=(-1)^{j-1}\binom{m-1+j}{l-1}\binom{m-1+j-l}{j-1}.$ (18)

In particular,

$a_{m}(j,m)=(-1)^{j-1}\binom{m-1+j}{m-1},$

for $1\leq j\leq D-m$.

Now we turn to the derivation of our desired series expansion in terms of the
above specified recurrence relation.

###### Proof of Lemma 7.1.

Take $m$ highlighted roots $\mathpzc{h}=\\{w_{1},w_{2},\ldots,w_{m}\\}$. We
work from Lemma 6.3, which gives

$S_{D-m}(\mathcal{T})-S_{D-m}(\mathpzc{e})=\sum_{l=1}^{\min\\{D-m,m\\}}S_{l}(\mathpzc{h})S_{D-m-l}(\mathpzc{e}).$

We perform an iterative procedure to obtain the recurrence relation (17). It
is obtained by expressing each of the highest order $S_{j}(\mathpzc{e})$ in
terms of lower order $S_{l}$ and each $S_{j-l}(\mathpzc{h})$ in terms of a
distinguished root $w_{1}$. One step of this procedure corresponds to first
replacing the instance of $S_{j}(\mathpzc{e})$ with the largest index $j$ with
$S_{j}(\mathcal{T})-\sum S_{i}(\mathpzc{h})S_{j-i}(\mathpzc{e})$ and then
replacing instances of $S_{i}(\mathpzc{h})$ with
$\binom{m}{i}(-w_{1})^{j-l}+\varepsilon_{i}(\mathpzc{h})$, where
$|\varepsilon_{i}(\mathpzc{h})|\lesssim\max_{w,w^{\prime}\in\mathpzc{h}}|w-w^{\prime}|h^{i-1}.$

Let us first consider the simpler case of $m=1$. We see that

$S_{D-1}(\mathcal{T})-S_{D-1}(\mathpzc{e})=(-w_{1})S_{D-2}(\mathpzc{e})=a^{\prime}_{1}(1,1)(-w_{1})S_{D-2}(\mathpzc{e}).$

This gives our initialisation of the recurrence relation, with
$a^{\prime}_{1}(1,1)=1$ with $a^{\prime}_{1}(1,l)=0$ for $l\neq 1$. To begin
the recurrence, we substitute
$S_{D-2}(\mathpzc{e})=S_{D-2}(\mathcal{T})-(-w_{1})S_{D-3}(\mathpzc{e})$,
which gives

$S_{D-1}(\mathcal{T})-S_{D-1}(\mathpzc{e})=(-w_{1})S_{D-2}(\mathcal{T})-(-w_{1})^{2}S_{D-3}(\mathpzc{e})$
$=a^{\prime}_{1}(2,2)(-w_{1})S_{D-2}(\mathcal{T})+a^{\prime}_{1}(2,1)(-w_{1})^{2}S_{D-3}(\mathpzc{e}),$

so that $a^{\prime}_{1}(2,2)=a^{\prime}_{1}(1,1)=1$ and
$a^{\prime}_{1}(2,1)=-1=-a^{\prime}_{1}(1,1)+a^{\prime}_{1}(1,0)$. This
continues until we have eliminated all appearances of the $S_{l}(\mathpzc{h})$
and $S_{l}(\mathpzc{e})$ for $l>1$, the recurrence relation is seen to be
$a^{\prime}_{1}(j+1,1)=-a^{\prime}_{1}(j,1)=-a^{\prime}_{1}(j,1)+a^{\prime}_{1}(j,0)$
for $j\leq D-1$ and $a^{\prime}(j+1,l)=a^{\prime}(j,l-1)$ for $l\neq 1$.

In the case where $m\geq 2$, it is harder to work with exact expressions, so
we will introduce appropriate error terms. We distinguish the root
$w_{1}\in\mathpzc{h}$. Note that, wherever $S_{l}(\mathpzc{h})$ appears, we
can write
$S_{l}(\mathpzc{h})=\binom{m}{l}(-w_{1})^{l}+\varepsilon_{l}(\mathpzc{h})$,
where
$|\varepsilon_{l}(\mathpzc{h})|\lesssim\max_{w,w^{\prime}\in\mathpzc{h}}|w-w^{\prime}|h^{l-1}$,
if $m\geq 2$. This is seen by replacing any instance of $w_{j}$ for $2\leq
j\leq m$ with $w_{j}=w_{1}+(w_{j}-w_{1})$: the term resulting from the
difference on the right hand side of this equation is cast into to the error
term $\varepsilon_{l}(\mathpzc{h})$.

For our initialisation, we first modify all terms featuring highlighted roots
by introducing an appropriate error and find that

$S_{D-m}(\mathcal{T})-S_{D-m}(\mathpzc{e})=\sum_{l=1}^{\min\\{m,D-m\\}}S_{l}(\mathpzc{h})S_{D-m-l}(\mathpzc{e})$
$=\sum_{l=1}^{\min\\{m,D-m\\}}\binom{m}{l}(-w_{1})^{l}S_{D-m-l}(\mathpzc{e})+\left(\sum_{l=1}^{\min\\{m,D-m\\}}\varepsilon_{l}(\mathpzc{h})S_{D-m-l}(\mathpzc{e})\right)$
$=\sum_{l\geq
1}a^{\prime}_{m}(1,m+1-l)(-w_{1})^{l}S_{D-m-l}(\mathpzc{e})+\varepsilon_{D-m}^{(0)},$
(19)

where $a^{\prime}_{m}(1,l)=\binom{m}{l}$ for $1\leq l\leq\min\\{m,D-m\\}$ and
$a^{\prime}_{m}(1,l)=0$ for $l>\min\\{m,D-m\\}$ or $l\leq 0$. Here
$\varepsilon_{D-m}^{(0)}\coloneqq\sum_{l=1}^{\min\\{m,D-m\\}}\varepsilon_{l}(\mathpzc{h})S_{D-m-l}(\mathpzc{e})$
is easily verified to satisfy the required error bound
$|\varepsilon_{D-m}^{(0)}|\lesssim\max_{w,w^{\prime}\in\mathpzc{h}}|w-w^{\prime}|h^{D-m-1}$.
Note that, although $S_{j}(\mathpzc{e})$ appearing in the sum (19) is not
defined for $j>D-m$ or $j<0$, the corresponding terms should not be considered
as part of the sum since the corresponding coefficients are $0$. We write the
initialisation as an infinite series expansion in this way because it makes
the expression of our recursion more convenient.

As the first step of the recursion, we will use the equation

$S_{D-m-1}(\mathpzc{e})=S_{D-m-1}(\mathcal{T})-\sum_{j=1}^{\min\\{m,D-m-1\\}}S_{j}(\mathpzc{h})S_{D-m-1-j}(\mathpzc{e})$
$=S_{D-m-1}(\mathcal{T})-\sum_{j\in\mathbb{Z}}\mathbbm{1}_{I_{1}}(j)\binom{m}{j}(-w_{1})^{j}S_{D-m-1-j}(\mathpzc{e})+\varepsilon_{D-m-1}^{(0,1)}(\mathpzc{h}),$
(20)

where $I_{1}=\left[1,\min\\{m,D-m-1\\}\right]$ and
$\varepsilon^{(0,1)}_{D-m-1}\coloneqq\sum_{j\in\mathbb{Z}}\mathbbm{1}_{I_{1}}(j)\varepsilon_{j}(\mathpzc{h})S_{D-m-1-j}(\mathpzc{e})$
satisfies
$|\varepsilon^{(0,1)}_{D-m-1}(\mathpzc{h})|\lesssim\max_{\\{w,w^{\prime}\in\mathpzc{h}\\}}|w-w^{\prime}|h^{D-m-2}$.

To carry out the first step of our recursive procedure, we substitute (20)
into (19). We end up with

$S_{D-m}(\mathcal{T})-S_{D-m}(\mathpzc{e})$
$=a^{\prime}_{m}(1,m)(-w_{1})S_{D-m-1}(\mathcal{T})+\sum_{j\in\mathbb{Z}}\mathbbm{1}_{I_{1}}(j)\binom{m}{j}(-a^{\prime}_{m}(1,m))(-w_{1})^{j+1}S_{D-m-1-j}(\mathpzc{e})$
$+a^{\prime}_{m}(1,m)(-w_{1})\varepsilon^{(0,1)}_{D-m-1}(\mathpzc{h})$
$+\sum_{l\geq
2}a^{\prime}_{m}(1,m+1-l)(-w_{1})^{l}S_{D-m-l}(\mathpzc{e})+\varepsilon^{(0)}_{D-m}(\mathpzc{h})$
$=a^{\prime}_{m}(1,m)(-w_{1})S_{D-m-1}(\mathcal{T})+\sum_{j\in\mathbb{Z}}\mathbbm{1}_{I_{1}}(j)\binom{m}{j}(-a^{\prime}_{m}(1,m))(-w_{1})^{j+1}S_{D-m-1-j}(\mathpzc{e})$
$+\sum_{j\geq
1}a^{\prime}_{m}(1,m-j)(-w_{1})^{j+1}S_{D-m-1-j}(\mathpzc{e})+\varepsilon_{D-m}^{(1)}(\mathpzc{h})$
$=\sum_{l\leq 0}a^{\prime}_{m}(2,m+1-l)(-w_{1})^{l+1}S_{D-m-1-l}(\mathcal{T})$
$+\sum_{l\geq
1}a^{\prime}_{m}(2,m+1-l)(-w_{1})^{l+1}S_{D-m-1-l}(\mathpzc{e})+\varepsilon_{D-m}^{(1)}(\mathpzc{h})$

where $|\varepsilon_{D-m}^{(1)}(\mathpzc{h})|\ll h^{D-m}$ and

$a^{\prime}_{m}(2,m+1-l)=-\mathbbm{1}_{I_{1}}(l)\binom{m}{l}a^{\prime}_{m}(1,m)+a^{\prime}_{m}(1,m-l).$
(21)

The procedure continues. The recurrence relation we get is

$a^{\prime}_{m}(j+1,m+1-l)=-\mathbbm{1}_{I_{j}}(l)\binom{m}{l}a^{\prime}_{m}(j,m)+a^{\prime}_{m}(j,m-l),$
(22)

where

$I_{j}\coloneqq[1,\min\left\\{m,D-m-j\right\\}],$ (23)

where, if $\min\left\\{m,D-m-j\right\\}<1$, (23) should be understood as a
void interval, i.e. $I_{j}=\emptyset$. The indicator function
$\mathbbm{1}_{I_{j}}$ appearing in (22) simply ensures that we do not pick up
any symmetric functions below $S_{0}(\mathcal{T})$ in our series expansion.

Looking at (22) and (23), we can see that, for $j\geq D-m$,
$a^{\prime}_{m}(j+1,l)=a^{\prime}_{m}(j,l)$ for all $l$. This reflects the
fact that we can only carry out the iteration procedure, where we replace
instances of $S_{D-m-j}(\mathpzc{e})$ with $S_{D-m-j}(\mathcal{T})$, an error,
and terms involving $S_{D-m-j^{\prime}}(\mathpzc{e})$ for $j^{\prime}>j$,
$D-m-1$ times. The derived series expansion for
$S_{D-m}(\mathcal{T})-S_{D-m}(\mathpzc{e})$ is

$S_{D-m}(\mathcal{T})-S_{D-m}(\mathpzc{e})$ $=\sum_{l\leq
0}a^{\prime}_{m}(2,m+1-l)(-w_{1})^{l+1}S_{D-m-1-l}(\mathcal{T})+\sum_{l\geq
1}a^{\prime}_{m}(2,m+1-l)(-w_{1})^{l+1}S_{D-m-1-l}(\mathpzc{e})$
$+\varepsilon_{D-m}^{(1)}(\mathpzc{h})$ $=\sum_{l\leq
0}a^{\prime}_{m}(3,m+1-l)(-w_{1})^{l+2}S_{D-m-2-l}(\mathcal{T})+\sum_{l\geq
1}a^{\prime}_{m}(3,m+1-l)(-w_{1})^{l+2}S_{D-m-2-l}(\mathpzc{e})$
$+\varepsilon_{D-m}^{(2)}(\mathpzc{h})$ $=\ldots$ $=\sum_{l\leq
0}a^{\prime}_{m}(j^{\prime}+1,m+1-l)(-w_{1})^{l+j^{\prime}}S_{D-m-j^{\prime}-l}(\mathcal{T})+\sum_{l\geq
1}a^{\prime}_{m}(j^{\prime}+1,m+1-l)(-w_{1})^{l+j^{\prime}}S_{D-m-j^{\prime}-l}(\mathpzc{e})$
$+\varepsilon_{D-m}^{(j^{\prime})}(\mathpzc{h}).$

Taking $j^{\prime}=D-m-1$, we find that

$S_{D-m}(\mathcal{T})-S_{D-m}(\mathpzc{e})=\sum_{l\leq
0}a^{\prime}_{m}(D-m,m+1-l)(-w_{1})^{l+D-m-1}S_{1-l}(\mathcal{T})$
$+\sum_{l\geq
1}a^{\prime}_{m}(D-m,m+1-l)(-w_{1})^{l+D-m-1}S_{1-l}(\mathpzc{e})+\varepsilon_{D-m}^{(D-m-1)}(\mathpzc{h})$
$=\sum_{l\leq
0}a^{\prime}_{m}(D-m,m+1-l)(-w_{1})^{l+D-m-1}S_{1-l}(\mathcal{T})+a^{\prime}_{m}(D-m,m)(-w_{1})^{D-m}S_{0}(\mathpzc{e})+\varepsilon_{D-m}^{(D-m-1)}(\mathpzc{h})$
$=\sum_{m-D+2\leq l\leq
1}a^{\prime}_{m}(D-m+l-1,m)(-w_{1})^{l+D-m-1}S_{1-l}(\mathcal{T})+\varepsilon_{D-m}^{(D-m-1)}(\mathpzc{h}).$

Now observe that, for $l\leq 0$,
$a^{\prime}_{m}(j+1,m+1-l)=a^{\prime}_{m}(j,m-l)$, by definition (22).
Therefore, for $l\leq 0$,
$a^{\prime}_{m}(j^{\prime},m+1-l)=a^{\prime}_{m}(j^{\prime}+l-1,m).$ In
particular, we have

$S_{D-m}(\mathcal{T})-S_{D-m}(\mathpzc{e})$ $=\sum_{1\leq j\leq
D-m}a^{\prime}_{m}(j,m)(-w_{1})^{j}S_{D-m-j}(\mathcal{T})+\varepsilon_{D-m}^{(D-m-1)}(\mathpzc{h}).$

One can easily see that the recurrence relation (22) differs from the
recurrence relation (17). However, the terms that appear in the series
expansion are $a^{\prime}_{m}(j,m)$ for $1\leq j\leq D-m$ and it can be
verified that these coincide with the same $a_{m}(j,m)$. ∎

###### Proof of Lemma 7.2.

We want to show that, for $b\leq l\leq m$ and $1\leq j\leq D-m$,

$a_{m}(j,l)=(-1)^{j-1}\binom{m-1+j}{l-1}\binom{m-1+j-l}{j-1},$ (24)

where $a_{m}$ satisfies the recurrence relation (17). This is true for $j=1$
by definition. We now work by induction. We must show that the right hand side
of (24) satisfies the recurrence relation (17). We apply the relevant forward
expression to see that, for $b\leq l\leq m$ and $j\geq 1$,

$-\binom{m}{l-1}(-1)^{j-1}\binom{m-1+j}{m-1}+(-1)^{j-1}\binom{m-1+j}{l-2}\binom{m+j-l}{j-1}$
$=(-1)^{j}\left(\frac{m!}{(l-1)!(m-l+1)!}\cdot\frac{(m-1+j)!}{j!(m-1)!}-\frac{(m+j-1)!}{(m+j-l+1)!(l-2)!}\cdot\frac{(m+j-l)!}{(j-1)!(m-l+1)!}\right)$
$=(-1)^{j}\left(\frac{(m-1+j)!}{(l-1)!(m+j-l+1)!}\right)\left(\frac{m(m+j-l+1)!}{(m-l+1)!j!}-\frac{(m+j-l)!(l-1)}{(j-1)!(m-l+1)!}\right)$
$=(-1)^{j}\left(\frac{(m-1+j)!}{(l-1)!(m+j-l+1)!}\right)\left(\frac{(m+j-l)!}{j!(m-l+1)!}\right)\left(m(m+j-l+1)-(l-1)j\right)$
$=(-1)^{j}\left(\frac{(m-1+j)!}{(l-1)!(m+j-l+1)!}\right)\left(\frac{(m+j-l)!}{j!(m-l+1)!}\right)\left((m+j)(m+1-l)\right)$
$=(-1)^{j}\binom{m+j}{l-1}\binom{m+j-l}{j},$

as required. ∎

##  Part II Explicit root structure

In Section 5, we introduced certain reference heights. These reference heights
provided an essential scaffold for our root structure analysis. Nevertheless,
the tools developed so far tell us nothing explicit about even the size of the
reference heights. The reference heights were given in terms of the size of
certain roots and thus depended implicitly on the coefficients of our
polynomial $\Psi$. In this section, we establish an explicit toolkit for
estimating reference heights, from which we are then able to obtain refined
structural statements.

We also consider the rough factorisation of monic $\Psi$ into polynomials
corresponding with each tier. We provide an explicit factorised polynomial
$\widetilde{\Psi}(t)=\prod_{r=1}^{s}\widetilde{\Psi}_{r}(t)$. Our analysis
results in a further tool for root finding, in that a suitable small
neighbourhood of the roots of the polynomial factor $\widetilde{\Psi}_{l}$
will contain the roots of $\Psi$ in the tier $\mathcal{T}_{l}$.

###  8\. Root tier stratification

We have defined the tier structure in terms of reference heights about which
we have no a priori information. The following lemma outlines a useful
procedure for estimating the reference heights in an _unknown_ regime.

In this section, we prove our explicit tool for estimating the heights of
roots, Lemma 8.1. We also prove Theorem 1.4. This is a direct corollary of our
later Proposition 8.2 considered with reference to Theorem 6.1.

######  Lemma 8.1.

We fix a set of exponents $k_{1}<k_{2}<\ldots<k_{L}$ and consider polynomials

$\Psi(t)=x+y_{1}t^{k_{1}}+\ldots+y_{L}t^{k_{L}},$

with $y_{L}\neq 0$. The roots of $\Psi$ are structured into tiers,
$\mathcal{T}_{1}$, $\mathcal{T}_{2}$, $\ldots$ $\mathcal{T}_{s}$, according
with Theorem 1.1. There exists an algorithm outputting a sequence of height
estimates $\eta_{1}\geq\eta_{2}\geq\ldots\geq\eta_{a}$, where $1\leq s\leq
a\leq L$, which satisfy the following.

Associated with $\eta_{1}$, $\eta_{2}$,$\ldots$ $\eta_{a}$ are indices
$0=\alpha(0),\alpha(1),\alpha(2),\ldots,\alpha(a)$ such that

$\eta_{j}^{D(\alpha(j))-D(\alpha(j-1))}=\left|\frac{y_{L-\alpha(j)}}{y_{L-\alpha(j-1)}}\right|.$

For each $0\leq b<a$, we proceed by setting

$\eta_{b+1}=\max_{\alpha(b)<j\leq
L}\left|\frac{y_{L-j}}{y_{L-\alpha(b)}}\right|^{\frac{1}{D(j)-D(\alpha(b))}}=\left|\frac{y_{L-\alpha(b+1)}}{y_{L-\alpha(b)}}\right|^{\frac{1}{D(\alpha(b+1))-D(\alpha(b))}}.$

There exist $0=\beta(0)$, $\beta(1)$, $\beta(2)$, $\ldots$ $\beta(s)=a$ such
that

$\eta_{j}\sim h(\mathcal{T}_{r}),\text{ for }\beta(r-1)<j\leq\beta(r).$

Furthermore, $\alpha(\beta(r))=L(r)$, with the $l_{j}$ and $L(j)$ defined as
in Definition 5.5.

We can reformulate the previous comparison as follows: for $\alpha(j)$ with
$L(r-1)+1\leq\alpha(j)\leq L(r)$,

$\eta_{j}\sim h(\mathcal{T}_{r}).$ (25)

###### Proof.

Suppose we are in the regime indexed by $(l_{1},l_{2},\ldots,l_{s})$, as in
Definition 5.5. We can easily verify that

$\left|S_{D(L(i))}(\mathcal{R})\right|\sim
h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}\ldots
h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}.$ (26)

Indeed, $(-z_{1})(-z_{2})\ldots(-z_{D(L(i))})$ is the term of largest
magnitude appearing in the sum $S_{D(L(i))}(\mathcal{R})$ and it is comparable
in magnitude to $h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}\ldots
h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}.$ Since they must include a root from
a smaller tier, all the remaining terms in the sum $S_{D(L(i))}(\mathcal{R})$
are bounded in magnitude by

$h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}\ldots
h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})-1}h(\mathcal{T}_{i+1})\ll
h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}\ldots
h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}.$

Similarly, note that, for $L(t-1)+1\leq j\leq L(t)$,

$|S_{D(j)}(\mathcal{R})|\lesssim
h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}h(\mathcal{T}_{2})^{D(\mathcal{T}_{2})}\ldots
h(\mathcal{T}_{t-1})^{D(\mathcal{T}_{t-1})}h(\mathcal{T}_{t})^{D(j)-D(L(t-1))}.$
(27)

Set

$\eta_{1}=\max_{1\leq j\leq
L}|S_{D(j)}(\mathcal{R})|^{\frac{1}{D(j)}}=|S_{D(\alpha(1))}(\mathcal{R})|^{\frac{1}{D(\alpha(1))}}=\left|\frac{y_{L-\alpha(1)}}{y_{L}}\right|^{\frac{1}{D(\alpha(1))}}.$

Since all roots are bounded in magnitude by $h(\mathcal{T}_{1})$ and, from
(26), $S_{D(L(1))}(\mathcal{R})\sim h(\mathcal{T}_{1})^{D(L(1))}$, we then see
that $\eta_{1}\sim h(\mathcal{T}_{1})$.

Next, we set

$\eta_{2}=\max_{\alpha(1)<j\leq
L}\left|\frac{S_{D(j)}(\mathcal{R})}{S_{D(\alpha(1))}(\mathcal{R})}\right|^{\frac{1}{D(j)-D(\alpha(1))}}$
$=\left|\frac{S_{D(\alpha(2))}(\mathcal{R})}{S_{D(\alpha(1))}(\mathcal{R})}\right|^{\frac{1}{D(\alpha(2))-D(\alpha(1))}}=\left|\frac{y_{L-\alpha(2)}}{y_{L-\alpha(1)}}\right|^{\frac{1}{D(\alpha(2))-D(\alpha(1))}}.$

Having determined $\eta_{1}$, $\eta_{2}$, $\ldots$, $\eta_{i}$ and
corresponding $\alpha(1)$, $\alpha(2)$, $\ldots$, $\alpha(i)<L$, we set

$\eta_{i+1}=\max_{\alpha(i)<j\leq
L}\left|\frac{S_{D(j)}(\mathcal{R})}{S_{D(\alpha(i))}(\mathcal{R})}\right|^{\frac{1}{D(j)-D(\alpha(i))}}$
(28)
$=\left|\frac{S_{D(\alpha(i+1))}(\mathcal{R})}{S_{D(\alpha(i))}(\mathcal{R})}\right|^{\frac{1}{D(\alpha(i+1))-D(\alpha(i))}}=\left|\frac{y_{L-\alpha(i+1)}}{y_{L-\alpha(i)}}\right|^{\frac{1}{D(\alpha(i+1))-D(\alpha(i))}}.$

We wish to ensure that at least one height estimate corresponds to every
reference height. This is ensured provided $h_{l(r)}\gg h_{l(r)+1}$ for each
$1\leq r\leq s$ with suitable constants in Definition 5.5. In the procedure
defined above, we show that each $y_{L-L(t)}$ appears in one of the
expressions for $\eta_{j}$, (28). Furthermore, for terms picked up in the
procedure, the bound (27) can be upgraded to a comparison. We show this
inductively.

First, take the largest $0\leq\alpha(\beta_{1}-1)$ such that
$\alpha(\beta_{1}-1)<L(1)$. Observe that

$\left|S_{D(L(1))}(\mathcal{R})\right|^{\frac{1}{D(L(1))}}=\left|\frac{y_{L-L(1)}}{y_{L}}\right|^{\frac{1}{D(L(1))}}\sim
h(\mathcal{T}_{1}),$

by (26). Thus we can see, by definition of our height estimates, that, if
$\alpha(\beta_{1}-1)>0$, then
$\left|S_{D(\alpha(\beta_{1}-1))}\right|^{\frac{1}{D(\alpha(\beta_{1}-1))}}\gtrsim
h(\mathcal{T}_{1})$. Considering (27), we then see that either
$\alpha(\beta_{1}-1)=0$ or

$\left|S_{D(\alpha(\beta_{1}-1))}\right|^{\frac{1}{D(\alpha(\beta_{1}-1))}}\sim
h(\mathcal{T}_{1}).$ (29)

We now wish to show that $\alpha(\beta_{1})=L(1)$. Suppose for contradiction
that $\alpha(\beta_{1})>L(1)$. Set $\tilde{h}=h(\mathcal{T}_{2})$ and
$h=h(\mathcal{T}_{1})$. We know that $\tilde{h}\ll h$. Using the equations
(27) and (29) to bound the size of the symmetric functions in terms of height
estimates, we see that

$\eta_{\beta_{1}}=\left|\frac{y_{L-\alpha(\beta_{1})}}{y_{L-\alpha(\beta_{1}-1)}}\right|^{\frac{1}{D(\alpha(\beta_{1}))-D(\alpha(\beta_{1}-1))}}$
$=\left|\frac{S_{D(\alpha(\beta_{1}))}(\mathcal{R})}{S_{D(\alpha(\beta_{1}-1))}(\mathcal{R})}\right|^{\frac{1}{D(\alpha(\beta_{1}))-D(\alpha(\beta_{1}-1))}}$
$\lesssim\left|\frac{\tilde{h}^{D(\alpha(\beta_{1}))-D(L(1))}h^{D(L(1))}}{h^{D(\alpha(\beta_{1}-1))}}\right|^{\frac{1}{D(\alpha(\beta_{1}))-D(\alpha(\beta_{1}-1))}}$
$\leq\left|\frac{\tilde{h}^{D(\alpha(\beta_{1}))-D(L(1))}}{h^{D(\alpha(\beta_{1}))-D(L(1))}}h^{D(\alpha(\beta_{1})))-D(\alpha(\beta_{1}-1))}\right|^{\frac{1}{D(\alpha(\beta_{1}))-D(\alpha(\beta_{1}-1))}}$
$\ll
h=\left|h^{D(L(1))-D(\alpha(\beta_{1}-1))}\right|^{\frac{1}{D(L(1))-D(\alpha(\beta_{1}-1))}}$
$\sim\left|\frac{S_{D(L(1))}(\mathcal{R})}{S_{D(\alpha(\beta_{1}-1))}(\mathcal{R})}\right|^{\frac{1}{D(L(1))-D(\alpha(\beta_{1}-1))}}$
$=\left|\frac{y_{L-L(1)}}{y_{L-\alpha(\beta_{1}-1)}}\right|^{\frac{1}{D(L(1))-D(\alpha(\beta_{1}-1))}}.$

This contradicts the definition of $\eta_{\beta_{1}}$, so we must have that
$\alpha(\beta_{1})=L(1)$. Furthermore, for
$0=\beta(0)<i\leq\beta(1)=\beta_{1}$,

$\eta_{i}\sim h(\mathcal{T}_{1}).$

We proceed inductively. Fix some index $r$. Suppose that $\beta(r-1)$ is such
that $\alpha(\beta(\tilde{r}))=L(\tilde{r})$ for $1\leq\tilde{r}\leq r-1$ and,
for $1\leq\tilde{r}<r$ and $\beta(\tilde{r}-1)<i\leq\beta(\tilde{r})$,

$\eta_{i}\sim h(\mathcal{T}_{\tilde{r}}).$ (30)

We then choose $\beta_{r}$ maximally so that
$\alpha(\beta(r-1))=L(r-1)\leq\alpha(\beta_{r}-1)<L(r)$. Similarly to our
proof of (29), it is routine to verify that

$\left|\frac{y_{L(r)}}{y_{L(r-1)}}\right|^{\frac{1}{D(L(r))-D(\alpha(\beta(r-1)))}}=\left|\frac{S_{D(L(r))}(\mathcal{R})}{S_{D(\alpha(L(r-1))}(\mathcal{R})}\right|^{\frac{1}{D(L(r))-D(\alpha(\beta(r-1)))}}\sim
h(\mathcal{T}_{r}),$

we easily see that, for $\beta(r-1)<i\leq\beta(r)$,

$\eta_{i}\sim h(\mathcal{T}_{r}).$ (31)

As a consequence of (30) and (31), we find that, for
$\beta(r-1)<i\leq\beta(r)$,

$|S_{D(\alpha(i))}(\mathcal{R})|=\left|\prod_{l=1}^{i}\eta_{i}^{D(\alpha(l))-D(\alpha(l-1))}\right|$
$\sim
h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}h(\mathcal{T}_{2})^{D(\mathcal{T}_{2})}\ldots
h(\mathcal{T}_{r-1})^{D(\mathcal{T}_{r-1})}h(\mathcal{T}_{r})^{D(\alpha(i))-D(L(r-1))}.$
(32)

As previously, we now wish to show that $\alpha(\beta_{r})=L(r)$. Suppose,
then, to find a contradiction, that $\alpha(\beta_{r})>L(r)$. Similarly to
(32), we find, setting $h=h(\mathcal{T}_{r})$ and
$\tilde{h}=h(\mathcal{T}_{r+1})$, that

$\eta_{\beta_{r}}=\left|\frac{y_{L-\alpha(\beta_{r})}}{y_{L-\alpha(\beta_{r}-1)}}\right|^{\frac{1}{D(\alpha(\beta_{r}))-D(\alpha(\beta_{r}-1))}}=\left|\frac{S_{D(\alpha(\beta_{r}))}(\mathcal{R})}{S_{D(\alpha(\beta_{r}-1))}(\mathcal{R})}\right|^{\frac{1}{D(\alpha(\beta_{r}))-D(\alpha(\beta_{r}-1))}}$
$\lesssim\left|\frac{h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}h(\mathcal{T}_{2})^{D(\mathcal{T}_{2})}\ldots
h(\mathcal{T}_{r})^{D(\mathcal{T}_{r})}h(\mathcal{T}_{r+1})^{D(\alpha(\beta_{r}))-D(L(r))}}{h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}h(\mathcal{T}_{2})^{D(\mathcal{T}_{2})}\ldots
h(\mathcal{T}_{r-1})^{D(\mathcal{T}_{r-1})}h(\mathcal{T}_{r})^{D(\alpha(\beta_{r}-1))-D(L(r-1))}}\right|^{\frac{1}{D(\alpha(\beta_{r}))-D(\alpha(\beta_{r}-1))}}$
$\sim\left|\frac{h^{D(L(r))-D(L(r-1))}\tilde{h}^{D(\alpha(\beta_{r}))-D(L(r))}}{h^{D(\alpha(\beta_{r}-1))-D(L(r-1))}}\right|^{\frac{1}{D(\alpha(\beta_{r}))-D(\alpha(\beta_{r}-1))}}$
$=\left|h^{D(\alpha(\beta_{r}))-D(\alpha(\beta_{r}-1))}\frac{\tilde{h}^{D(\alpha(\beta_{r}))-D(L(r))}}{h^{D(\alpha(\beta_{r}))-D(L(r))}}\right|^{\frac{1}{D(\alpha(\beta_{r}))-D(\alpha(\beta_{r}-1))}}$
$\ll
h\sim\left|\frac{y_{L(r)}}{y_{L(r-1)}}\right|^{\frac{1}{D(L(r))-D(\alpha(\beta(r-1)))}},$

which contradicts the definition of $\eta_{\beta_{r}}$.

∎

We can use the procedure from Lemma 8.1 to obtain the refined structural
result, Theorem 1.4. Here, with additional restrictions on the coefficients,
we have stronger control on the root structure as a consequence of the
explicit estimates for the reference heights. The following proposition feeds
directly into our result on the structure of roots within a given tier,
Theorem 6.1, to give the refined structural result, Theorem 1.4, as a
corollary.

######  Proposition 8.2.

Fix the set of exponents $k_{1}<k_{2}<\ldots<k_{L}$. We consider polynomials

$\Psi(t)=x+y_{1}t^{k_{1}}+\ldots+y_{L}t^{k_{L}}$

such that

$\max_{1\leq j\leq L}|y_{j}|^{\frac{1}{k_{j}}}\leq 1.$

Take some $\gamma\in(0,1]$ and suppose, additionally, that

$|y_{m}|^{\frac{1}{k_{m}}}\geq\gamma,$

and, for $n>m$,

$|y_{n}|^{\frac{1}{k_{n}}}\leq\delta,$

for some $m$ and some suitably small $\delta=\delta(\gamma)>0$. Then the roots
of $\Psi$ can be classified into large and small tiers $\mathcal{T}_{1}$,
$\ldots$ $\mathcal{T}_{s(1)}$ and $\mathcal{T}_{s(1)+1}$, $\ldots$
$\mathcal{T}_{s(1)+s(2)}$ which satisfy the following.

First, we have that $0\leq s(1)\leq s(1)+s(2)=s\leq L$ and, additionally
$s(1)\leq L-m+1$. If $s(2)\geq 1$, then $s(1)\leq L-m$.

We refer to those tiers $\mathcal{T}_{r}$ with $1\leq r\leq s(1)$ as the large
tiers. For any root $w$ in a large tier, we have that $|w|\gtrsim_{\gamma}1$.
In the case that $s(2)\geq 1$, we refer to those tiers $\mathcal{T}_{r}$ with
$s(1)+1\leq r\leq s(1)+s(2)$ as the small tiers. For any root $w$ in a small
tier, we have that $|w|\lesssim_{\gamma}1$.

The tiers are well separated: for any choice of $w_{j}\in\mathcal{T}_{j}$, we
have that

$|w_{1}|\ll|w_{2}|\ll\ldots\ll|w_{s}|.$

Finally, we have the following. In the case that $s(2)\geq 1$, we have that
$L(s(1))=L-m$. If $s(2)=0$, then, $l_{s(1)}\geq m$ and, for $L-m<L(s-1)+j<L$,

$\left|S_{D(L(s-1)+j)}(\mathcal{R})\right|\ll
h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}h(\mathcal{T}_{2})^{D(\mathcal{T}_{2})}\ldots
h(\mathcal{T}_{s})^{D(L(s-1)+j)-D(L(s-1))}.$

Before proceeding with the proof of Proposition 8.2, let us show how Theorem
1.4 is obtained as a corollary.

###### Proof of Theorem 1.4.

Proposition 8.2 already gives the large and small tiers, and the required
control on their size. It remains to determine the way in which roots may
cluster. To do so, we work with reference to the final paragraph of the
proposition’s statement.

Let us first consider the case that $s(2)\geq 1$. Here we can see, since
$L(s(1))=L-m$, that for $1\leq r\leq s(1)$, $l_{r}\leq L(s(1))\leq L-m$.
Therefore $|\mathcal{D}(\mathcal{T}_{r})|-1=l_{r}\leq L-m$ and, by Theorem
6.1, $B(w,\epsilon|w|)$ contains _at most_ $L-m$ roots for any root $w$ in a
large tier $\mathcal{T}_{r}$. Likewise, for $s(1)+1\leq r\leq s(1)+s(2)$,
$l_{r}\leq L-L(s(1))=m$ so that, for any root $w$ in a small tier
$\mathcal{T}_{r}$, $B(w,\epsilon|w|)$ contains _at most_ $m$ roots.

In the case that $s(2)=0$, we work as follows. We consider a tier
$\mathcal{T}_{r}$. If $l_{r}\leq L-m+1$, then, as above, one has that for any
root $w$ the tier $\mathcal{T}_{r}$, $B(w,\epsilon|w|)$ contains _at most_
$L-m+1$ roots. Otherwise, $L(r)\geq l_{r}>L-m+1$ so that
$L(s)-L(r)=L-L(r)<m-1$. Since $l_{s}\geq m$ we must then have that $r=s$
because otherwise we would have $m\leq l_{s}\leq L(s)-L(r)<m-1$. According
with Lemma 5.8, for $1\leq j\leq l_{s}$, we then approximate
$S_{D_{j}(\mathcal{T}_{s})}(\mathcal{T}_{s})$ by

$\frac{S_{D(L(s-1)+j)}(\mathcal{R})}{S_{D(L(s-1))}(\mathcal{T}_{1}\cup\ldots\cup\mathcal{T}_{s-1})}.$

In particular, we have for $1\leq j\leq l_{s}$ that

$\left|S_{D_{j}(\mathcal{T}_{s})}(\mathcal{T}_{s})-\frac{S_{D(L(s-1)+j)}(\mathcal{R})}{S_{D(L(s-1))}(\mathcal{T}_{1}\cup\ldots\cup\mathcal{T}_{s-1})}\right|\ll
h(\mathcal{T}_{s})^{D_{j}(\mathcal{T}_{s})}.$

Combining this with Proposition 8.2, for $L-m<L(s-1)+j<L$, we see that

$\left|S_{D_{j}(\mathcal{T}_{s})}(\mathcal{T}_{s})\right|\ll
h(\mathcal{T}_{s})^{j}.$

From this, it is a matter of counting to see that _at most_ $L-m+1$ non-
trivial symmetric functions $S_{j}(\mathcal{T}_{s})$ are substantial: we can
choose
$\widetilde{\mathcal{D}}(\mathcal{T}_{s})\subset\mathcal{D}(\mathcal{T}_{s})$
in Theorem 6.1, with $|\widetilde{\mathcal{D}}(\mathcal{T}_{s}))|-1\leq
L-m+1$, so that, for $j\notin\widetilde{\mathcal{D}}(\mathcal{T}_{s})$,
$\left|S_{j}(\mathcal{T}_{s})\right|\ll h(\mathcal{T}_{s})^{j}$. Therefore, by
Theorem 6.1, for any root $w$, $B(w,\epsilon|w|)$ contains _at most_ $L-m+1$
roots. ∎

###### Proof of Proposition 8.2.

We consider what the supposed conditions tell us under the height estimation
procedure, Lemma 8.1. We obtain a sequence of reference heights
$\eta_{1},\eta_{2},\ldots$ and corresponding indices
$\alpha(1),\alpha(2),\ldots$ satisfying the conditions of that lemma.

In the case that $m=L$, there is nothing to prove. The height estimates are
all $\lesssim_{\gamma}1$. We set $s(1)=0$ so that $L(s(1))=0$ and each tier is
a small tier. In what follows, we consider the case $m<L$.

Firstly, observe that
$\left|\frac{y_{m}}{y_{L}}\right|^{\frac{1}{D(L-m)}}\geq\left|\frac{\gamma^{k_{m}}}{\delta^{k_{L}}}\right|^{\frac{1}{D(L-m)}}\gg
1$, provided $\delta$ is sufficiently small. As such, we are guaranteed to
pick up a number of _large_ height estimates $\eta_{j}\gtrsim_{\gamma}1$.

Let $0\leq i_{0}$ be chosen maximally so that $\alpha(i_{0})\leq L-m$. We
either have that $\alpha(i_{0})=L-m$ or $\alpha(i_{0})<L-m$ and we first split
our analysis by these cases. Since, for $n>m$,

$\left|\frac{y_{m}}{y_{n}}\right|^{\frac{1}{D(L-m)-D(L-n)}}\gtrsim_{\gamma}1$

it is easy to see that

$\eta_{\max\\{i_{0},1\\}}\gtrsim_{\gamma}1.$

In the first case, where $L-\alpha(i_{0})=m$, note that $i_{0}\geq 1$. We then
observe that, provided we choose $\delta$ is chosen sufficiently small
depending on $\gamma$, for $1\leq j<m$,

$\left|\frac{y_{j}}{y_{m}}\right|^{\frac{1}{D(L-j)-D(L-m)}}\leq\left|\frac{1}{\gamma^{k_{m}}}\right|^{\frac{1}{D(L-j)-D(L-m)}}$
$\ll\left|\frac{\gamma^{k_{m}}}{\delta^{k_{L-\alpha(i_{0}-1)}}}\right|^{\frac{1}{D(L-m)-D(\alpha(i_{0}-1))}}\leq\left|\frac{y_{m}}{y_{L-\alpha(i_{0}-1)}}\right|^{\frac{1}{D(L-m)-D(\alpha(i_{0}-1))}}=\eta_{i_{0}},$
(33)

by definition of the height estimates. Thus we see that either
$\eta_{i_{0}+1}\ll\eta_{i_{0}}$ or, if $\eta_{i_{0}+1}\gtrsim\eta_{i_{0}}$, we
must have that
$\eta_{i_{0}+1}=\left|\frac{x}{y_{m}}\right|^{\frac{1}{D(L)-D(L-m)}}$.

We now consider what happens in the height estimation procedure in the case
that $\alpha(i_{0})<L-m$. We observe that, for $1\leq j<m$,

$\left|\frac{y_{j}}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L-j)-D(\alpha(i_{0}))}}\leq\left|\frac{1}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L-j)-D(\alpha(i_{0}))}}$
$\ll\left|\frac{y_{m}}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L-m)-D(\alpha(i_{0}))}},$
(34)

where one can verify that the last inequality holds because it is satisfied in
the extreme:

$\left|\frac{1}{\delta^{k_{L-\alpha(i_{0})}}}\right|^{\frac{1}{D(L-j)-D(\alpha(i_{0}))}}\ll\left|\frac{\gamma^{k_{j}}}{\delta^{k_{L-\alpha(i_{0})}}}\right|^{\frac{1}{D(L-m)-D(\alpha(i_{0}))}}.$

Thus, in the case that $\alpha(i_{0})<L-m$, we necessarily have that
$\eta_{i_{0}+1}=\left|\frac{x}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L)-D(\alpha(i_{0}))}}$
and $\alpha(i_{0}+1)=L$, since we have specified that $y_{m}$ contributes to
no height estimate by the condition $\alpha(i_{0})<L-m$.

We continue our analysis by splitting according to the control between height
estimates $\eta(i_{0})$ and $\eta(i_{0}+1)$. Firstly, we analyse the situation
where $\eta(i_{0}+1)\ll\eta(i_{0})$, which can only occur if
$L-m=\alpha(i_{0})$. Secondly, we analyse the situation where either
$\eta(i_{0}+1)\gtrsim\eta(i_{0})$ or where $i_{0}=0$, which can occur with
$L-m=\alpha(i_{0})$ or with $L-m>\alpha(i_{0})$.

The first scenario is where $\eta(i_{0}+1)\ll\eta(i_{0})$. Here, we have that
$\alpha(i_{0})=L-m$. This is the $s(2)\geq 1$ case. According with Lemma 8.1,
we choose $s(1)$ so that the large tiers $\mathcal{T}_{r}$, for $1\leq r\leq
s(1)$ are those corresponding with the height estimates
$\eta_{1},\eta_{2},\ldots,\eta_{i_{0}}$. We must have, by (25) from Lemma 8.1,
that $L(s(1))=\alpha(i_{0})=L-m$. We can also see that

$\eta_{i_{0}}=\left|\frac{y_{m}}{y_{L-\alpha(i_{0}-1)}}\right|^{\frac{1}{D(L-m)-D(\alpha(i_{0}-1))}}\gtrsim_{\gamma}1,$

and, by Lemma 8.1, for roots $w$ in large tiers,

$|w|\gtrsim_{\gamma}1.$

There are also small tiers of roots: following Lemma 8.1, these are the tiers
corresponding with the height estimates
$\eta_{i_{0}+1},\eta_{i_{0}+2},\ldots\eta_{a}$. It is easy to see that
$1\gtrsim_{\gamma}\eta_{i_{0}+1}$, since

$\eta_{i_{0}+1}=\left|\frac{y_{L-\alpha(i_{0}+1)}}{y_{m}}\right|^{\frac{1}{D(\alpha(i_{0}+1))-D(L-m)}}\leq\left|\frac{1}{\gamma}\right|^{\frac{1}{D(\alpha(i_{0}+1))-D(L-m)}},$

and, by Lemma 8.1, for roots $w$ in small tiers,

$|w|\lesssim_{\gamma}1.$

In the second scenario, $\eta(i_{0})\sim\eta(i_{0}+1)$ or there is only one
height estimate and $\alpha(1)=L$. In either case, $\alpha(i_{0}+1)=L$, as we
previously showed how, in this case, we must have
$\eta_{i_{0}+1}=\left|\frac{x}{y_{m}}\right|^{\frac{1}{D(L)-D(L-m)}}$. This is
the $s(2)=0$ case, where all tiers are large. By Lemma 8.1,
$l_{s}\geq\alpha(i_{0}+1)-\alpha(i_{0})\geq L-(L-m)=m$. In this case, to
conclude the proof, we must establish control the size of the symmetric
functions $S_{D(L-j)}(\mathcal{R})$ for $1\leq j<m$. For these $j$, note that
$L-j>L-m\geq L-l_{s}=L(s-1)$. We work to show that that, for $1\leq j<m$,

$\left|S_{D(L-j)}(\mathcal{R})\right|\ll
h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}h(\mathcal{T}_{2})^{D(\mathcal{T}_{2})}\ldots
h(\mathcal{T}_{s})^{D(L-j)-D(L(s-1))}.$

Because we know that
$\eta_{i_{0}+1}=\left|\frac{x}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L)-D(L-\alpha(i_{0}))}}$
is the final height estimate,

$\eta_{i_{0}+1}\sim h(\mathcal{T}_{s}),$ (35)

by Lemma 8.1. We claim that that, for $1\leq j<m$,

$\left|\frac{y_{j}}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L-j)-D(L-\alpha(i_{0}))}}\ll
h(\mathcal{T}_{s}).$ (36)

Assuming for now that (36) holds, also using the inequality (25) from the
statement of Lemma 8.1, we see that, for $1\leq j<m$,

$\left|S_{D(L-j)}(\mathcal{R})\right|=\left|\frac{y_{j}}{y_{L}}\right|$
$=\left|\frac{y_{\alpha(1)}}{y_{L}}\right|\ldots\left|\frac{y_{L-\alpha(i_{0})}}{y_{L-\alpha(i_{0}-1)}}\right|\left|\frac{y_{j}}{y_{L-\alpha(i_{0})}}\right|$
$\ll h(\mathcal{T}_{1})^{D(\mathcal{T}_{1})}\ldots
h(\mathcal{T}_{s-1})^{D(\mathcal{T}_{s-1})}h(\mathcal{T}_{s})^{D(L-j)-D(L(s-1))},$

which, after reindexing, is the desired error bound. To see this, we consider
$1\leq j^{\prime}<l_{s}$ such that $L-(L(s-1)+j^{\prime})=l_{s}-j^{\prime}<m$:
we set $j=L-(L(s-1)+j^{\prime})$, which ranges between $1$ and $m-1$, as in
the proposition’s statement.

To conclude, we prove our claimed inequality (36). In the case that
$L-\alpha(i_{0})=m$, this is a direct consequence of (33) upon observing from
Lemma 8.1 that $\eta_{i_{0}}\sim h(\mathcal{T}_{s})$. In the case that
$\alpha(i_{0})<L-m$, we use (34) and Lemma 8.1: if $i_{0}=0$, then there is
one height estimate
$\eta_{1}=\left|\frac{x}{y_{L}}\right|^{\frac{1}{k_{L}}}\geq\left|\frac{y_{m}}{y_{L}}\right|^{\frac{1}{D(L-m)}}\gg\left|\frac{y_{j}}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L-j)-D(L-\alpha(i_{0}))}}$,
if $i_{0}\geq 1$, then
$\eta_{i_{0}+1}\geq\left|\frac{y_{m}}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L-m)-D(\alpha(i_{0}))}}\gg\left|\frac{y_{j}}{y_{L-\alpha(i_{0})}}\right|^{\frac{1}{D(L-j)-D(L-\alpha(i_{0}))}}$.
Referring to (35), the inequality follows. ∎

######  Remark 8.3.

As for Proposition 8.2, Lemma 8.1 and the procedure it outlines can be used to
obtain other refinements of the main structural result, Theorem 1.1. For
example, if we had that

$\left|\frac{y_{L-1}}{y_{L}}\right|^{\frac{1}{d(1)}}\gg\left|\frac{y_{L-2}}{y_{L-1}}\right|^{\frac{1}{d(2)}}\gg\ldots\gg\left|\frac{x}{y_{1}}\right|^{\frac{1}{d(L)}}>0,$

then we would have $L$ tiers of roots which are separated and, for
sufficiently small $\epsilon$ and some root $z\in\mathcal{R}$,
$B(z,\epsilon|z|)$ contains only the root $z$.

###  9\. Rough factorisation

For notational reasons, we consider monic polynomials in this section:

$\Psi(t)=\sum_{j=0}^{L}y_{j}t^{k_{j}},$

where $k_{0}=0$, $y_{0}\neq 0$, and $y_{L}=1$. In this section, we provide a
rough factorisation of monic polynomials with a well separated tier structure.
To this end, let us suppose that throughout this section we are in the regime
indexed by $(l_{1},l_{2},\ldots,l_{s})$, as in Definition 5.5. Here there are
$s$ tiers, $\mathcal{T}_{1}$, $\ldots$, $\mathcal{T}_{s}$, containing
$D(\mathcal{T}_{1})=|\mathcal{T}_{1}|$, $\ldots$,
$D(\mathcal{T}_{s})=|\mathcal{T}_{s}|$ roots, respectively. The tier regime
may be roughly characterised by

$h(\mathcal{T}_{1})\gg h(\mathcal{T}_{2})\gg\ldots\gg h(\mathcal{T}_{s}),$
(37)

for some suitable choice of constants.

Recall the definition of the $k_{j}(\mathcal{T}_{r})$ exponents for a given
tier, Definition 6.6. More explicitly, for $0\leq j\leq l_{r}$, we can write
$k_{j}(\mathcal{T}_{r})=k_{L-L(r)+j}-k_{L-L(r)}$. Recall also the Definition
5.7 of the distinguished indices $D_{j}(\mathcal{T}_{r})$, which we can write
more explicitly as
$D_{j}(\mathcal{T}_{r})=D(L(r-1)+j)-D(L(r-1))=k_{L-L(r-1)}-k_{L-L(r-1)-j}$.

######  Definition 9.1.

If we are in the regime given in Definition 5.5 indexed by
$(l_{1},l_{2},\ldots,l_{s})$, then, for $1\leq j\leq s$, we define the monic
polynomial

$\widetilde{\Psi}_{j}(t)\coloneqq\frac{1}{y_{L-L(j-1)}}\sum_{i=0}^{l_{j}}y_{L-L(j)+i}t^{k_{i}(\mathcal{T}_{j})}.$
(38)

We define the rough factorisation of $\Psi(t)$ by

$\widetilde{\Psi}(t)\coloneqq\prod_{j=1}^{s}\widetilde{\Psi}_{j}(t).$ (39)

We denote the roots of $\widetilde{\Psi}_{j}$ by $\widetilde{\mathcal{T}_{j}}$
and the roots of $\widetilde{\Psi}$ by $\widetilde{\mathcal{R}}$.

Away from the zeros of the polynomial, the rough factorisation, (39), we seek
should be quantifiably close to the original $\Psi$. Furthermore, the root
structure of $\Psi$ and the root structure of its rough factorisation should
be closely related. In particular, we have Theorem 9.2.

######  Theorem 9.2.

There exists a polynomial
$\widetilde{\Psi}=\prod_{l=1}^{s}\widetilde{\Psi}_{l}(t)$, with
$\widetilde{\Psi}_{l}(t)$ given by (38), which roughly factorises $\Psi$ in
the following sense.

The polynomial $\widetilde{\Psi}_{l}$ has roots,
$\widetilde{\mathcal{T}}_{l}$, which are all of comparable magnitude.
Furthermore, for roots $w_{j}\in\widetilde{\mathcal{T}}_{j}$, we have that

$|w_{1}|\gg|w_{2}|\gg\ldots\gg|w_{s}|.$

There exists a covering, $N(\mathcal{R})$, of the roots,
$\mathcal{R}\subset\mathbb{C}$, of $\Psi$ which satisfies the following. Each
connected component of $N(\mathcal{R})$, which we call a cell, is given by a
ball. Each cell containing contains at most $L$ roots. For a cell $B$
containing exactly $m$ roots of $\Psi$, $B$ contains exactly $m$ roots of
$\widetilde{\Psi}$.

For $t\notin N(\mathcal{R})$,

$|\Psi(t)-\widetilde{\Psi}(t)|\ll|\Psi(t)|.$

One of the strongest similarities between our work and that of Hickman and
Wright [4] is to be found in our proof of the rough factorisation theorem. In
particular, both proofs follow a method of contradiction and taking suitable
estimating the valuation of the respective polynomials. Hickman and Wright
essentially consider the related root structures more general family of close
polynomials, while here we consider only the rough factorisation and the
original polynomial.

The analysis in this section requires strong separation of the height
estimates in the specification of the tier regime, Definition 5.5, as we will
see. It should be noted, however, that the results of Part I do not require
such strong separation, although this is not something we specify in this
paper. All of the results in this section should be understood as valid with
respect to a tier regime specified with sufficiently strong separation in
(37).

To begin with, let us bound the difference of $\Psi(t)$ and
$\widetilde{\Psi}(t)$.

######  Lemma 9.3.

With

$E(t)\coloneqq\widetilde{\Psi}(t)-\Psi(t),$ (40)

we have that, for each $1\leq r\leq s$ and $h(\mathcal{T}_{r+1})\ll|t|\lesssim
h(\mathcal{T}_{r})$, that

$\left|E(t)\right|\leq\epsilon_{f}\left(\prod_{i=1}^{r}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}\right)|t|^{\sum_{j=r+1}^{s}D(\mathcal{T}_{j})},$
(41)

including for $r=s$ and $r=1$, subject to the understanding that
$h(\mathcal{T}_{0})=\infty$ and $h(\mathcal{T}_{s+1})=0$. Here the constant
$\epsilon_{f}$ can be taken arbitrarily small, provided we make a suitably
strong choice of separation constants in the specification of the tier regime,
(37).

###### Proof.

For $1\leq i\leq l_{j}$, we wish to estimate

$\left|\frac{y_{L-L(j)+i}}{y_{L-L(j-1)}}\right|.$

As a consequence of the height estimation lemma, Lemma 8.1, we have that

$\left|\frac{y_{L-L(j)+i}}{y_{L-L(j-1)}}\right|\lesssim
h(\mathcal{T}_{j})^{D_{l_{j}-i}(\mathcal{T}_{j})}.$ (42)

We use this to bound the error term.

We can write

$\widetilde{\Psi}(t)=\prod_{j=1}^{s}\frac{1}{y_{L-L(j-1)}}\left(\sum_{i_{j}=0}^{l_{j}}y_{L-L(j)+i_{j}}t^{k_{i_{j}}(\mathcal{T}_{s})}\right).$

To avoid a proliferation of nested sub and super-scripts, we will sometimes
write $i(j)$ and $l(j)$ in place of $i_{j}$ and $l_{j}$, respectively. If we
expand the above product expression for $\widetilde{\Psi}$, we obtain a sum
that we will refer to throughout this proof. Each term in the resulting sum
can be indexed by $(i_{1},i_{2},\ldots,i_{s})$, where the index $i_{j}$ ranges
over $\\{0,1,\ldots,l_{j}\\}$ for each $1\leq j\leq s$.

We first consider those terms which sum to $\Psi$. For $1\leq a\leq s$ one can
see that the term indexed by
$(0,0,\ldots,i_{a},l_{a+1},l_{a+2},\ldots,l_{s})$, with $0\leq i_{a}<l_{a}$ is
exactly

$\left(\prod_{j=1}^{a-1}\frac{y_{L-L(j)}}{y_{L-L(j-1)}}\right)\left(\frac{1}{y_{L-L(a-1)}}y_{L-L(a)+i(a)}t^{k_{i(a)}(\mathcal{T}_{a})}\right)\left(\prod_{i=a+1}^{s}t^{k_{l(i)}(\mathcal{T}_{i})}\right)$
$=y_{L-L(a)+i(a)}t^{k_{L-L(a)+i(a)}}.$

As an example, corresponding to $a=s$, we have that the term indexed by
$(0,0,\ldots,0,i_{s})$ is

$\left(\prod_{j=1}^{s-1}\frac{y_{L-L(j)}}{y_{L-L(j-1)}}\right)\left(\frac{1}{y_{L-L(s-1)}}y_{L-L(s)+i(s)}t^{k_{i(s)}(\mathcal{T}_{s})}\right)$
$=y_{i(s)}t^{k_{i(s)}}.$

We also have that the term indexed by $(l_{1},l_{2},\ldots,l_{s})$ is

$\left(\prod_{i=1}^{s}t^{k_{l(i)}(\mathcal{T}_{i})}\right)=t^{k_{L}}.$

In this way, we have uniquely indexed all of the terms appearing in the
expansion of $\Psi(t)$. The remaining terms are exactly those which sum to
$E(t)=\widetilde{\Psi}(t)-\Psi(t)$. Before proceeding to bound $E$, let us
consider the size of the terms we have just indexed. This will inform us as to
the bounds we should shoot for on the error term. For the term indexed by
$(0,0,\ldots,i_{a},l_{a+1},l_{a+2},\ldots,l_{s})$, we see using (42) that it
is bounded in magnitude

$\lesssim\left(\prod_{j=1}^{a-1}h(\mathcal{T}_{j})^{D_{l_{j}}(\mathcal{T}_{j})}\right)\left(h(\mathcal{T}_{a})^{D_{l(a)-i(a)}(\mathcal{T}_{a})}|t|^{k_{i(a)}(\mathcal{T}_{a})}\right)\left(\prod_{j=a+1}^{s}|t|^{k_{l(j)}(\mathcal{T}_{j})}\right).$

Now, if we are considering $h(\mathcal{T}_{r+1})\ll|t|\lesssim
h(\mathcal{T}_{r})$, for $1\leq a\leq L$, these terms can be uniformly bounded

$\lesssim\left(\prod_{j=1}^{r}h(\mathcal{T}_{j})^{D_{l_{j}}(\mathcal{T}_{j})}\right)\left(\prod_{j=r+1}^{s}|t|^{k_{l(j)}(\mathcal{T}_{j})}\right)=\left(\prod_{j=1}^{r}h(\mathcal{T}_{j})^{D(\mathcal{T}_{j})}\right)|t|^{\sum_{j=r+1}^{s}D(\mathcal{T}_{j})}.$

In what follows, we consider those terms that we did not specify as summing to
$\Psi$ above. We refer to these as the remainder terms. Let us fix $1\leq
r\leq s$ and consider

$h(\mathcal{T}_{r+1})\ll|t|\lesssim h(\mathcal{T}_{r}).$ (43)

As above, for the term indexed by $(i_{1},i_{2},\ldots,i_{s})$, we can
estimate the size of each of the $s$ factors using (42) and (43). For $1\leq
j\leq r$,

$\left|\frac{1}{y_{L-L(j-1)}}y_{L-L(j)+i(j)}t^{k_{i(j)}(\mathcal{T}_{j})}\right|\lesssim
h(\mathcal{T}_{j})^{D(\mathcal{T}_{j})}.$ (44)

For $r<j\leq s$,

$\left|\frac{1}{y_{L-L(j-1)}}y_{L-L(j)+i(j)}t^{k_{i(j)}(\mathcal{T}_{j})}\right|\lesssim
h(\mathcal{T}_{r})^{D(\mathcal{T}_{j})}.$ (45)

To bound $E$ as an error term, we require stronger control on the remainder
terms. We observe that those terms summing to $E$ are indexed by
$(i_{1},i_{2},\ldots,i_{s})$, such that if $a$ is the smallest index such that
$i_{a}\neq 0$ (or $a=0$ if no such index $i_{j}$ exists), then there exists a
minimal $a^{\prime}>a$ for which $i_{a^{\prime}}<l_{a^{\prime}}$. The
corresponding term is

$\left(\prod_{j=1}^{a-1}\frac{y_{L-L(j)}}{y_{L-L(j-1)}}\right)\left(\frac{1}{y_{L-L(a-1)}}y_{L-L(a)+i(a)}t^{k_{i(a)}(\mathcal{T}_{a})}\right)\left(\prod_{j=a+1}^{s}\frac{1}{y_{L-L(j-1)}}y_{L-L(j)+i(j)}t^{k_{i(j)}(\mathcal{T}_{j})}\right).$

For each of these remainder terms, one of the factors appearing in the above
expression will allow us to establish the error bound. Let us now fix some
remainder term and its corresponding index $(i_{1},\ldots,i_{s})$. We split
our analysis according to whether $r\leq a<s$ or $1\leq a<r$.

If $r\leq a<s$, then, using (42) and the fact that $|t|\gg
h(\mathcal{T}_{r+1})\geq h(\mathcal{T}_{a^{\prime}})$, we can strongly bound
the factor indexed by $i_{a^{\prime}}$

$\left|\frac{1}{y_{L-L(a^{\prime}-1)}}y_{L-L(a^{\prime})+i(a^{\prime})}t^{k_{i(a^{\prime})}(\mathcal{T}_{a^{\prime}})}\right|\lesssim
h(\mathcal{T}_{a^{\prime}})^{D_{l(a^{\prime})-i(a^{\prime})}(\mathcal{T}_{a^{\prime}})}t^{k_{i(a^{\prime})}(\mathcal{T}_{a^{\prime}})}$
$\ll|t|^{k_{l(a^{\prime})}}=|t|^{D(\mathcal{T}_{a^{\prime}})},$

since $D_{l(a^{\prime})-i(a^{\prime})}>0$. Putting this together with (44) and
(45), we can bound the magnitude of the remainder term indexed by
$(i_{1},\ldots,i_{s})$

$\ll\left(\prod_{j=1}^{r}h(\mathcal{T}_{j})^{D_{l_{j}}(\mathcal{T}_{j})}\right)|t|^{D(\mathcal{T}_{a^{\prime}})}\left|\prod_{j=r+1,j\neq
a^{\prime}}^{s}\frac{1}{y_{L-L(j-1)}}y_{L-L(j)+i(j)}t^{k_{i(j)}(\mathcal{T}_{j})}\right|$
$\lesssim\left(\prod_{j=1}^{r}h(\mathcal{T}_{j})^{D_{l_{j}}(\mathcal{T}_{j})}\right)\left|\prod_{j=r+1}^{s}|t|^{D(\mathcal{T}_{j})}\right|.$

If $1\leq a<r$, then we can strongly bound the factor indexed by $i_{a}$

$\left|\frac{1}{y_{L-L(a-1)}}y_{L-L(a)+i(a)}t^{k_{i(a)}(\mathcal{T}_{a})}\right|\ll
h(\mathcal{T}_{a})^{k_{l(a)}}=h(\mathcal{T}_{a})^{D(\mathcal{T}_{a})},$

since $|t|\lesssim h(\mathcal{T}_{r})\ll h(\mathcal{T}_{a})$ and
$k_{i(a)}(\mathcal{T}_{a})>0$. Therefore, also using (44) and (45), we can
bound the remainder term indexed by $(i_{1},\ldots,i_{s})$

$\ll\left(\prod_{j=1,j\neq
a}^{r}h(\mathcal{T}_{j})^{D_{l_{j}}(\mathcal{T}_{j})}\right)\left(h(\mathcal{T}_{a})^{D(\mathcal{T}_{a})}\right)\left(\prod_{j=r+1}^{s}|t|^{D_{l_{j}}(\mathcal{T}_{j})}\right).$

Summing the bounds on each of the remainder terms gives the desired estimate.
∎

For a given tier, $\mathcal{T}_{r}$, there are two important scale parameters
appearing in the previous analysis. Provided the separation in (37) is strong
enough, we can set our fine parameter $\epsilon_{f}$ in Lemma 9.3 as small as
we like. The other important parameter appearing in our analysis is the coarse
scale parameter $\epsilon_{c}$, which we now define. We choose
$\epsilon_{c}>0$ so that, according with Theorem 6.2, _at most_
$L(\mathcal{T}_{r})$ roots from $\mathcal{T}_{r}$ can appear in the ball
$B(w,3\epsilon_{c}h(\mathcal{T}_{r}))$ for any choice of
$w\in\mathcal{T}_{r}$.

Before giving the proof of our main result, we require a covering lemma. This
covering lemma essentially provides a partition of the roots into clusters of
size up to $L$, with strong separation between distinct clusters. In place of
clusters, which are finite collection of roots, we use cells, which are
suitable open balls containing these roots. The proof gives a recursive
construction of these cells. Associated with this construction are a well
separated sequence of parameters,
$\epsilon_{f}\ll\epsilon_{1}\ll\epsilon_{2}\ll\ldots\ll\epsilon_{L}\ll\epsilon_{L+1}\ll\epsilon_{c}$,
which we now define.

######  Definition 9.4.

We set $\epsilon_{1}=\epsilon_{f}^{\frac{1}{L}}$ and, for $1\leq j\leq L$, we
set $\epsilon_{j+1}=\epsilon_{j}^{\frac{1}{L}}$.

######  Remark 9.5.

We can achieve strong separation of the parameters $\epsilon_{j}$ provided we
start from a suitable fine error parameter, $\epsilon_{f}$. Indeed, to have
that $\epsilon_{j}\ll\epsilon_{j+1}$ and $\epsilon_{L}\ll\epsilon_{c}$, the
two things we require are that

$\epsilon_{j}/\epsilon_{j+1}=\epsilon_{j}^{1-\frac{1}{L}}=\epsilon_{1}^{\frac{L-1}{L^{j}}}\ll
1$

and

$\epsilon_{L+1}=\epsilon_{1}^{\frac{1}{L^{L}}}\ll\epsilon_{c}.$

This is possible provided we can take $\epsilon_{f}$ sufficiently small, which
is something we can achieve if we specify the tier regime with strong
separation of the reference heights.

######  Definition 9.6.

For points $w_{1},\ldots,w_{a}\in\mathbb{C}$, we denote by
$A(w_{1},\ldots,w_{a})$ their arithmetic mean:

$A(w_{1},\ldots,w_{a})\coloneqq\frac{1}{a}\sum_{i=1}^{a}w_{i}.$

We can now state our root cell covering lemma.

######  Lemma 9.7.

There exists a covering, $N(\mathcal{R})$, of the roots, $\mathcal{R}$, of
$\Psi$ which satisfies the following.

Each connected component of $N(\mathcal{R})$, which we call a cell, $B$,
contains only roots from one tier. Furthermore, if a cell $B$ contains only
the roots $w_{1},\ldots,w_{b}$ in the tier $\mathcal{T}_{r}$, then
$B=B(A(w_{1},\ldots,w_{b}),\epsilon_{b}h(\mathcal{T}_{r}))$. Each cell can
contain at most $L$ roots.

For distinct cells $B=B(A(w_{1},\ldots,w_{b}),\epsilon_{b}h(\mathcal{T}_{r}))$
and
$B^{\prime}=B(A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}),\epsilon_{b^{\prime}}h(\mathcal{T}_{r}))$
with $b\geq b^{\prime}$,

$d(B,B^{\prime})\geq\frac{1}{4}\epsilon_{b+1}h(\mathcal{T}_{r}).$

In particular, for any root $w^{\prime}$ outwith the cell
$B=B(A(w_{1},\ldots,w_{b}),\epsilon_{b}h(\mathcal{T}_{r}))$ and any root $w\in
B$,

$|w-w^{\prime}|\gtrsim\epsilon_{b+1}h(\mathcal{T}_{r}).$

Figure 5 is a sketch of $4$ nearby root cells from a root cell covering. Roots
are marked with a cross. Note that the larger cells are at a larger distance
from adjacent cells.

Figure 5. Four cells from a root cell covering.

###### Proof.

Let us carry out the construction in each tier separately. Let
$\mathcal{T}=\mathcal{T}_{r}$ for some $r$ and let $h=h(\mathcal{T}_{r})$
denote the corresponding reference height.

The construction is first outlined with reference to a particular choice of
$w_{1}\in\mathcal{T}$. For each $w_{1}\in\mathcal{T}$, we construct an
appropriate ball $N(w_{1})$ containing $w_{1}$ and a number of other roots in
$\mathcal{T}$. The root cell covering $N(\mathcal{R})$ in the lemma statement
is then given as the union of the balls $N(w_{1})$.

For now, let us fix some $w_{1}$. If for all remaining
$w^{\prime}\in\mathcal{T}$, $|w_{1}-w^{\prime}|\geq\epsilon_{2}h$, then we set
$N(w_{1})=B(w_{1},\epsilon_{1}h)$.

Continuing the construction, it remains to consider the case where there
exists $w_{2}$ with $|w_{1}-w_{2}|<\epsilon_{2}h$. Fix some choice of such
$w_{2}$. We then divide our analysis with reference to
$A\left(w_{1},w_{2}\right)=\frac{w_{1}+w_{2}}{2}$. If, for all remaining
$w^{\prime}\in\mathcal{R}$, we have that
$|w^{\prime}-A\left(w_{1},w_{2}\right)|\geq\epsilon_{3}h$, then we set
$N(w_{1})=B(A\left(w_{1},w_{2}\right),\epsilon_{2}h)$. Otherwise, distinct
from $w_{1}$ and $w_{2}$, there exists $w_{3}$ such that
$|w_{3}-A\left(w_{1},w_{2}\right)|\leq\epsilon_{3}h$ and we continue as
previously, fixing some choice of $w_{3}$ and then working with reference to
$A\left(w_{1},w_{2},w_{3}\right)$ and the scale $\epsilon_{4}h$.

The procedure continues; we consider the distance of remaining roots to the
average of the roots already picked up by our procedure. Since there are
finitely many roots, we know that the construction will terminate and we will
refer to the resulting balls as terminal. For each choice of $w_{1}$, we
construct a terminal ball
$N(w_{1})=B(A\left(w_{1},w_{2},\ldots,w_{b}\right),\epsilon_{b}h)$. By
definition, the terminal ball $N(w_{1})$ is constructed so that, for
$w^{\prime}\in\mathcal{R}$ with $w^{\prime}\notin N(w_{1})$,
$\left|w^{\prime}-A\left(w_{1},w_{2},\ldots,w_{b}\right)\right|\geq\epsilon_{b+1}h$.

For each $w_{1}\in\mathcal{T}$, we can construct a ball $N(w_{1})$ following
the above procedure. The root cell covering $N(\mathcal{R})$ is simply given
as the union of the sets $N(w_{1})$. It remains to show that each connected
component of $N(\mathcal{R})$ is given by a ball containing at most
$L(\mathcal{T})$ roots, in particular that it is given by $N(w_{1})$ for some
$w_{1}$.

Let us first determine how close roots $w_{j}$ in a cell are to its centre.
From the cell $B(A(w_{1},\ldots,w_{b}),\epsilon_{b}h(\mathcal{T}_{r}))$, we
take the root $w_{a}$. We see that

$|w_{a}-A(w_{1},\ldots,w_{b})|\leq|w_{a}-A(w_{1},\ldots,w_{a}))|+\sum_{j=a+1}^{b}\left|A(w_{1},\ldots,w_{j-1})-A(w_{1},\ldots,w_{j})\right|$
$=|w_{a}-\frac{1}{a}\left((a-1)A(w_{1},\ldots,w_{a-1})+w_{a}\right)|$
$+\sum_{j=a+1}^{b}\frac{1}{j}\left|jA(w_{1},\ldots,w_{j-1})-\left((j-1)A(w_{1},\ldots,w_{j-1})+w_{j}\right)\right|$
$=\frac{a-1}{a}|w_{a}-A(w_{1},\ldots,w_{a-1})|+\sum_{j=a+1}^{b}\frac{1}{j}\left|A(w_{1},\ldots,w_{j-1})-w_{j}\right|$
$\leq\frac{a-1}{a}\epsilon_{a}h(\mathcal{T}_{r})+\sum_{j=a+1}^{b}\frac{1}{j}\epsilon_{j}h(\mathcal{T}_{r})$
$\leq\frac{b-1}{b}\epsilon_{b}h(\mathcal{T}_{r}).$ (46)

We can verify that the construction of the terminal balls takes at most
$L(\mathcal{T})$ steps. Indeed, suppose that this were not the case and
consider the step from $L(\mathcal{T})$ to $L(\mathcal{T})+1$. We then know we
can find $L(\mathcal{T})+1$ roots $w_{1}\ldots w_{L(\mathcal{T})+1}$ contained
in
$B\left(A\left(w_{1},w_{2},\ldots,w_{L(\mathcal{T})+1}\right),\epsilon_{L(\mathcal{T})+1}h\right)$.
This contradicts the regime specific structure theorem, Theorem 6.2, since

$B\left(A\left(w_{1},w_{2},\ldots,w_{L(\mathcal{T})+1}\right),\epsilon_{L(\mathcal{T})+1}h\right)\subset
B\left(w_{1},3\epsilon_{L(\mathcal{T})+1}h\right)\subset
B\left(w_{1},\epsilon_{c}h\right)$

and $B\left(w_{1},\epsilon_{c}h\right)$ contains at most $L(\mathcal{T})$
roots.

We are now able to show that each cell of $N(\mathcal{R})$ is a ball. To this
end, let us take two terminal balls
$B=B(A(w_{1},\ldots,w_{b}),\epsilon_{b}h(\mathcal{T}_{r}))$ and
$B^{\prime}=B(A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}),\epsilon_{b^{\prime}}h(\mathcal{T}_{r}))$
obtained by the construction outlined above. We suppose that these balls are
such that

$B(A(w_{1},\ldots,w_{b}),\epsilon_{b}h(\mathcal{T}_{r}))\cap
B(A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}),\epsilon_{b^{\prime}}h(\mathcal{T}_{r}))\neq\emptyset.$
(47)

Without loss of generality, suppose that $b^{\prime}\leq b$. We find that, for
any
$w_{a^{\prime}}\in\left\\{w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}\right\\}$,

$|w_{a}^{\prime}-A(w_{1},\ldots,w_{b})|$
$\leq|w_{a}^{\prime}-A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime})|+|A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime})-A(w_{1},\ldots,w_{b})|$
$\leq\frac{b^{\prime}-1}{b^{\prime}}\epsilon_{b^{\prime}}h(\mathcal{T}_{r})+\epsilon_{b^{\prime}}h(\mathcal{T}_{r})+\epsilon_{b}h(\mathcal{T}_{r})$
$<\epsilon_{b+1}h(\mathcal{T}_{r}).$ (48)

In particular, we must have that
$w_{a}^{\prime}\in\left\\{w_{1},\ldots,w_{b}\right\\}$, because otherwise the
construction we outlined above must continue to account for $w_{a^{\prime}}$.
Therefore
$\left\\{w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}\right\\}\subset\left\\{w_{1},\ldots,w_{b}\right\\}$.
It is then easy to verify that $B^{\prime}\subset B$. This is obvious if
$b=b^{\prime}$. To show this when $b^{\prime}<b$, let us take any complex
number $w\in B^{\prime}$. Relating $w$ to $B^{\prime}$ and $B^{\prime}$ to
$w_{1}^{\prime}$, which we know is an element of $B^{\prime}$ and of $B$, we
find that

$d(w,A(w_{1},\ldots,w_{b}))$ $\leq
d(w,A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}))+d(A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}),w_{1}^{\prime})+d(w_{1}^{\prime},A(w_{1},\ldots,w_{b}))$
$\leq\epsilon_{b^{\prime}}h(\mathcal{T}_{r})+\frac{b^{\prime}-1}{b^{\prime}}\epsilon_{b^{\prime}}h(\mathcal{T}_{r})+\frac{b-1}{b}\epsilon_{b}h(\mathcal{T}_{r})$
$<\epsilon_{b}h(\mathcal{T}_{r}),$

so that $w\in B$. Therefore, $B^{\prime}\subset B$.

In fact, the above argument showing that cells are given by terminal balls can
be strengthened. We can show that distinct cells are strongly separated. In
particular, to conclude, we show that, for cells
$B=B(A(w_{1},\ldots,w_{b}),\epsilon_{b}h(\mathcal{T}_{r}))$ and
$B^{\prime}=B(A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}),\epsilon_{b^{\prime}}h(\mathcal{T}_{r}))$
with $b^{\prime}\leq b$,

$d(B,B^{\prime})\gtrsim\epsilon_{b+1}h(\mathcal{T}_{r}).$

Let us suppose, for a contradiction, that there exists a complex number

$w\in
B\left(A(w_{1},\ldots,w_{b}),\frac{1}{3}\epsilon_{b+1}h(\mathcal{T}_{r})\right)\cap
B\left(A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}),\frac{1}{3}\epsilon_{b^{\prime}+1}h(\mathcal{T}_{r})\right).$
(49)

We find that

$d(w_{1}^{\prime},A(w_{1},\ldots,w_{b}))$ $\leq
d(w_{1}^{\prime},A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}))+d(A(w_{1}^{\prime},\ldots,w_{b^{\prime}}^{\prime}),w)+d(w,A(w_{1},\ldots,w_{b}))$
$\leq\frac{b^{\prime}-1}{b^{\prime}}\epsilon_{b^{\prime}}h(\mathcal{T}_{r})+\epsilon_{b^{\prime}}h(\mathcal{T}_{r})+\epsilon_{b}h(\mathcal{T}_{r})$
$<\epsilon_{b+1}h(\mathcal{T}_{r}).$

This inequality contradicts our assumption that
$B=B(A(w_{1},\ldots,w_{b}),\epsilon_{b}h(\mathcal{T}_{r}))$ was a terminal
ball, since it implies that the construction should continue to account for
the root $w_{1}^{\prime}\notin\left\\{w_{1},\ldots,w_{b}\right\\}$. Therefore
(49) can not hold and, in particular,

$d(B,B^{\prime})\geq\frac{1}{4}\epsilon_{b+1}h(\mathcal{T}_{r}).$

∎

######  Lemma 9.8.

The roots, $\widetilde{\mathcal{T}_{j}}$, of the polynomial
$\widetilde{\Psi}_{j}(t)$ are all comparable in magnitude to
$h(\mathcal{T}_{j})$.

###### Proof.

This is a simple consequence of Lemma 8.1, which can be applied with reference
to $\Psi$ or to $\widetilde{\Psi}_{j}$. In either case, we see exactly the
same expressions appearing as height estimates and the lemma tells us that
these are comparable to $h(\mathcal{T}_{j})$. ∎

We are now ready to prove Theorem 9.2.

###### Proof.

In the case that $s=1$, the factorisation is our initial polynomial and there
is nothing to prove. Henceforth, we suppose that $s>1$.

We make use of Lemma 9.8 and consider the factorisations of $\Psi(t)$ and
$\widetilde{\Psi}(t)$ in terms of their roots:

$\Psi(t)=\prod_{j=1}^{s}\prod_{w\in\mathcal{T}_{j}}(t-w)\quad\text{and}\quad\widetilde{\Psi}(t)=\prod_{j=1}^{s}\widetilde{\Psi}_{j}(t)=\prod_{j=1}^{s}\prod_{\tilde{w}\in\widetilde{\mathcal{T}}_{j}}(t-\tilde{w}).$
(50)

Throughout, we appeal to the regime specific structure theorem, Theorem 6.2,
and the root cell covering lemma, Lemma 9.7. Let us consider a specific
$t\notin N(\mathcal{R})$ with $|t|\sim h(\mathcal{T}_{r})$. By the definition
of our covering in Lemma 9.7, the closest $t$ can be to a root
$w\in\mathcal{T}_{r}$ is $\epsilon_{1}h(\mathcal{T}_{r})$ and, furthermore, we
can check that there are at most $L(\mathcal{T}_{r})$ roots $w$ with
$\epsilon_{1}h(\mathcal{T}_{r})<|t-w|<\epsilon_{c}h(\mathcal{T}_{r})$. Indeed,
if $w\in\mathcal{T}_{r}\cap B(t,\epsilon_{c}h(\mathcal{T}_{r}))$, then
$B(t,\epsilon_{c}h(\mathcal{T}_{r}))\subset
B(w,3\epsilon_{c}h(\mathcal{T}_{r}))$, which can contain at most
$L(\mathcal{T}_{r})$ roots, by Theorem 6.2 and our definition of
$\epsilon_{c}$. The remaining roots in $\mathcal{T}_{r}$ are roots
$w^{\prime}\notin B(t,\epsilon_{c}h(\mathcal{T}_{r}))$ and we know there are
at least $D(\mathcal{T}_{r})-L(\mathcal{T}_{r})$ of these. We thus find, using
the factorisation (50), that, for $t\notin N(\mathcal{R})$ with $|t|\sim
h(\mathcal{T}_{r})$,

$|\Psi(t)|\gtrsim\left(\epsilon_{c}^{D(\mathcal{T}_{r})-L(\mathcal{T}_{r})}\epsilon_{1}^{L(\mathcal{T}_{r})}h(\mathcal{T}_{r})^{D(\mathcal{T}_{r})}\right)\prod_{i=r+1}^{s}h(\mathcal{T}_{r})^{D(\mathcal{T}_{i})}\prod_{i=1}^{r-1}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}$
$\gg\epsilon_{f}h(\mathcal{T}_{r})^{D(\mathcal{T}_{r})+D(\mathcal{T}_{r+1})+\ldots+D(\mathcal{T}_{s})}\prod_{i=1}^{r-1}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})},$

provided $\epsilon_{f}$ has been taken small enough, since
$\epsilon_{1}^{L(\mathcal{T}_{r})}\epsilon_{c}^{D(\mathcal{T}_{r})-L(\mathcal{T}_{r})}=\epsilon_{f}^{\frac{L(\mathcal{T}_{r})}{L}}\epsilon_{c}^{D(\mathcal{T}_{r})-L(\mathcal{T}_{r})}\gg\epsilon_{f}$.
We now have an explicit lower estimate on the size of $\Psi(t)$ for $t\notin
N(\mathcal{R})$. It is now possible to make sense of Lemma 9.3 as an error
expression. Indeed, for $|t|\sim h(\mathcal{T}_{r})$, we see that

$|E(t)|\leq\epsilon_{f}h(\mathcal{T}_{r})^{D(\mathcal{T}_{r})+D(\mathcal{T}_{r+1})+\ldots+D(\mathcal{T}_{s})}\prod_{i=1}^{r-1}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})},$
(51)

so that for $|t|\sim h(\mathcal{T}_{r})$ with $t\notin N(\mathcal{R})$,

$|E(t)|\ll|\Psi(t)|.$

In particular, for $t\notin N(\mathcal{R})$,

$\widetilde{\Psi}(t)=\Psi(t)+E(t)\neq 0$

so that, for the roots of $\widetilde{\Psi}$,

$\widetilde{\mathcal{R}}\subset N(\mathcal{R}).$

It remains for us to show that each cell of $N(\mathcal{R})$ contains the same
number of roots of $\Psi$ and $\widetilde{\Psi}$. If there was no error term
and all roots were isolated, this would be easy as both functions would be
equal to zero on $\mathcal{R}\subset N(\mathcal{R})$. In fact, the argument
requires more precision. In order to account for the error term and cells
containing multiple roots, we must consider the size of the functions $\Psi$
and $\widetilde{\Psi}$ at a suitable distance from the roots $\mathcal{R}$. In
particular, we estimate the size of the functions close to the boundary of
$N(\mathcal{R})$. We know that $\mathcal{R}\subset N(\mathcal{R})$ and also
that $\widetilde{\mathcal{R}}\subset N(\mathcal{R})$, which will allow us to
estimate the size of the functions using their factorisations, (50).

For the remainder of the proof, we fix a cell $B=B(u,R)$, containing $m$
roots, with centre $u$ and radius $R=\epsilon_{m}h(\mathcal{T}_{r})$. We
consider the size of the functions $\Psi$ and $\widetilde{\Psi}$ at the
boundary of $B^{*}$, where $B^{*}=B(u,2R)$ is the double of $B$. For
$t\in\partial B^{*}$, using the factorisation (50) and the fact that
$d(t,B)=\epsilon_{m}h(\mathcal{T}_{r})$ with $B$ containing $m$ roots,

$|\Psi(t)|\lesssim\epsilon_{m}^{m}h(\mathcal{T}_{r})^{D(\mathcal{T}_{s})+\ldots+D(\mathcal{T}_{r})}\prod_{i=1}^{r-1}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}.$
(52)

By the covering Lemma 9.7, we can verify that points on $\partial B^{*}$ are
well separated from cells other than $B$. Indeed, $d(\partial
B^{*},B)=R=\epsilon_{m}h(\mathcal{T}_{r})$ and, if we take a distinct cell
$B^{\prime}$, then Lemma 9.7 tells us that
$d(B,B^{\prime})\geq\frac{1}{4}\epsilon_{m+1}h(\mathcal{T}_{r})$ so that
$d(\partial B^{*},B^{\prime})\gtrsim\epsilon_{m+1}h(\mathcal{T}_{r})$. In
particular, since $\widetilde{\mathcal{R}}\subset N(\mathcal{R})$, for
$t\in\partial B^{*}$ and any root
$\tilde{w}^{\prime}\in\widetilde{\mathcal{T}}_{r}$ with
$\tilde{w}^{\prime}\notin B$,

$|w^{\prime}-t|\gtrsim\epsilon_{m+1}h(\mathcal{T}_{r}).$ (53)

We also note that, by Theorem 6.2, for $t\in\partial B^{*}$,
$B(t,\epsilon_{c}h(\mathcal{T}_{r}))$ can contain at most $L(\mathcal{T}_{r})$
roots of $\widetilde{\Psi}$. Let us now suppose that the given cell, $B$,
contains only $\tilde{m}<m$ roots of $\widetilde{\Psi}$. For $t\in\partial
B^{*}\subset N(\mathcal{R})^{c}$, there can be at most
$L(\mathcal{T}_{r})-\tilde{m}$ roots $\tilde{w}^{\prime}\notin B$ for which
$\tilde{w}^{\prime}\in B(t,\epsilon_{c}h(\mathcal{T}_{r}))$. We know that, for
$t\in\partial B^{*}$, $|t|\sim h(\mathcal{T}_{r})$. Therefore, for
$t\in\partial B^{*}$, using the factorisation (50) and also the distance
estimate (53),

$\left|\widetilde{\Psi}(t)\right|\gtrsim\left(\epsilon_{c}^{D(\mathcal{T}_{r})-L(\mathcal{T}_{r})}\epsilon_{m}^{\tilde{m}}\epsilon_{m+1}^{L(\mathcal{T}_{r})-\tilde{m}}h(\mathcal{T}_{r})^{D(\mathcal{T}_{r})}\right)h(\mathcal{T}_{r})^{D(\mathcal{T}_{s})+\ldots+D(\mathcal{T}_{r+1})}\prod_{i=1}^{r-1}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}$
$\gtrsim\left(\epsilon_{c}^{D(\mathcal{T}_{r})-L(\mathcal{T}_{r})}\epsilon_{m}^{m-1}\epsilon_{m+1}^{L(\mathcal{T}_{r})-(m-1)}h(\mathcal{T}_{r})^{D(\mathcal{T}_{r})}\right)h(\mathcal{T}_{r})^{D(\mathcal{T}_{s})+\ldots+D(\mathcal{T}_{r+1})}\prod_{i=1}^{r-1}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}$
$\gg\epsilon_{m}^{m}h(\mathcal{T}_{r})^{D(\mathcal{T}_{s})+\ldots+D(\mathcal{T}_{r})}\prod_{i=1}^{r-1}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})},$
(54)

because
$\epsilon_{c}^{D(\mathcal{T}_{r})-L(\mathcal{T}_{r})}\epsilon_{m+1}^{L(\mathcal{T}_{r})-(m-1)}\gg\epsilon_{m}$.
This contradicts (51): considering (52) and (54) together, we have that

$|E(t)|\gtrsim\left|\widetilde{\Psi}(t)\right|-\left|\Psi(t)\right|\gg\epsilon_{m}^{m}h(\mathcal{T}_{r})^{D(\mathcal{T}_{s})+\ldots+D(\mathcal{T}_{r})}\prod_{i=1}^{r-1}h(\mathcal{T}_{i})^{D(\mathcal{T}_{i})}.$

Therefore, $B$ must contain $m$ roots of $\widetilde{\Psi}$. ∎

##  Part III Oscillatory integral estimates

In this section, we prove the oscillatory integral estimates given by Theorems
1.6 and 1.8. Let us first present an example which shows why the condition
$k_{L-s}\geq s+1$ is required in Theorem 1.8.

######  Proposition 9.9.

For $k\geq m$, define $\Phi(t)$ by

$\Phi(0)=0\text{ and }\Phi^{\prime}(t)=y_{L}(t^{k}-1)^{L-m+1}.$ (55)

We set $y_{1}=\ldots y_{m-1}=0$, the remaining $(x,y)$ parameters are defined
implictly by $\Phi^{\prime}(t)=x+\sum_{j=m}^{L}y_{j}t^{(j-m+1)k}$. For this
polynomial, we have that

$\left|\int e^{i\Phi(t)}dt\right|\gtrsim|y_{m}|^{-\frac{1}{L-m+2}},$

for $(x,y)$ in a region $R$ containing arbitrarily large $y_{m}$. In
particular, for the estimate (3) to hold in the region $R$, we require that
$k=k_{m}\geq L-m+1$.

######  Remark 9.10.

Proposition 9.9 is a direct consequence of the following (equivalent)
proposition, which amounts to a change in notation, and our testing the
inequality

$|y_{m}|^{-\frac{1}{L-m+2}}\lesssim|y_{m}|^{-\frac{1}{k_{m}+1}},$

as $|y_{m}|\rightarrow\infty$. The inequality leads to the necessary condition
$k_{m}\geq L-m+1$.

######  Proposition.

Here, we set $\tilde{L}=L-m+1$. For $k\geq m$, define $\Phi(t)$ by

$\Phi(0)=0\text{ and }\Phi^{\prime}(t)=y_{\tilde{L}}(t^{k}-1)^{l}.$ (56)

The $(x,y)$ parameters are defined implictly by
$\Phi^{\prime}(t)=x+\sum_{j=1}^{\tilde{L}}y_{j}t^{jk}$. For this polynomial,
we have that

$\left|\int e^{i\Phi(t)}dt\right|\gtrsim|y_{1}|^{-\frac{1}{l+1}},$

for $(x,y)$ in a region $R$ containing arbitrarily large $y_{1}$.

We refer the reader to [15] for a proof, in which we work via a standard non-
stationary phase analysis.

Let us now turn to the proof of the oscillatory integral bounds of Hickman and
Wright.

###### Proof of Theorems 1.6 and 1.8.

We first give the proof in the case that $k_{m}\geq L$ (Theorem 1.6) and later
give the technical case splitting required to obtain the result when
$k_{m}\geq L-m+1$ (Theorem 1.8).

Without loss of generality, we can prove the result for $\Phi$ as in (2)
chosen such that $\max_{1\leq j\leq L}{|y_{j}|}=1$. To see this, suppose we
have a phase $\widetilde{\Phi}=\widetilde{\Phi}_{\tilde{x},\tilde{y}}$ of the
same form as (2), where $\tilde{y}\in\mathbb{R}^{L}$ is unrestricted. We wish
to show
$|J(\tilde{x},\tilde{y})|\lesssim\min_{j}|\tilde{y}_{j}|^{-\frac{1}{k_{j}+1}}$,
where $J(\tilde{x},\tilde{y})=\int e^{i\tilde{\Phi}(s)}ds$, with
$\tilde{\Phi}(s)=\tilde{x}s+\frac{\tilde{y}_{1}}{k_{1}+1}s^{k_{1}+1}+\ldots+\frac{\tilde{y}_{L}}{k_{L}+1}s^{k_{L}+1}$.
By making a change of variables in the $s$ coordinate, it suffices to prove
$|J(x,y)|\lesssim 1$, where $J(x,y)=\int e^{i\Phi(s)}ds$, with
$\Phi(s)=xs+\frac{y_{1}}{k_{1}+1}s^{k_{1}+1}+\ldots+\frac{y_{L}}{k_{L}+1}s^{k_{L}+1}$
such that $\max_{1\leq j\leq L}|y_{j}|=1$. Indeed, we set
$\sigma=\max_{j}|\tilde{y}_{j}|^{\frac{1}{k_{j}+1}}$ and make the change of
variables $\sigma s=t$ in the integral expression for $J$. Writing
$\widetilde{\Phi}(s)$ in terms of $t$ we see that

$\widetilde{\Phi}(t)=\tilde{x}t+\frac{\tilde{y}_{1}}{k_{1}+1}t^{k_{1}+1}+\ldots+\frac{\tilde{y}_{L}}{k_{L}+1}t^{k_{L}+1}$
$=xs+\frac{y_{1}}{k_{1}+1}s^{k_{1}+1}+\ldots+\frac{y_{L}}{k_{L}+1}s^{k_{L}+1},$

where $x=\sigma^{-1}\tilde{x}$ and $y_{j}=\sigma^{-(k_{j}+1)}\tilde{y}_{j}$.
By definition of $\sigma$, $\max_{1\leq j\leq L}|y_{j}|=1$.

We now use the root structure Theorem 1.1 to prove the desired inequality

$\left|J(x,y)\right|=\left|\int e^{i\Phi(t)}dt\right|\lesssim 1.$

Let us consider the case where $\max_{1\leq j\leq
L}|y_{j}|^{\frac{1}{k_{j}}}=|y_{m}|^{\frac{1}{k_{m}}}=1$. Here, the
appropriate cluster estimate to consider is the $k_{m}$-cluster estimates,
namely the bound we desire is obtained with a suitable choice of $\mathcal{C}$
such that $|\mathcal{C}|=k_{m}$. We work to show that, for any $z_{j}$, there
exists a $k_{m}$-cluster $\mathcal{C}$ such that

$\prod_{l\notin\mathcal{C}}|z_{j}-z_{l}|\gtrsim|z_{1}z_{2}\ldots
z_{k_{L}-k_{m}}|.$ (57)

Once this has been established we note that

$|z_{1}z_{2}\ldots
z_{k_{L}-k_{m}}|\gtrsim|S_{k_{L}-k_{m}}|=\left|\frac{y_{m}}{y_{L}}\right|=\left|\frac{1}{y_{L}}\right|$

so that we can apply the Phong and Stein estimate, Theorem 1.7, to establish
that

$\left|J(x,y)\right|\lesssim\left(\frac{1}{|y_{L}z_{1}z_{2}\ldots
z_{k_{L}-k_{m}}|}\right)^{\frac{1}{k_{m}+1}}\lesssim 1.$

By Theorem 1.1, given a root of $\Phi^{\prime}$, $z$, there are _at most_ $L$
other roots in $B(z,\epsilon|z|)$, where $\epsilon$ is some suitable small
constant. For a root $z_{j}\notin B(z,\epsilon|z|)$,

$|z_{j}-z|\geq\max\\{\epsilon|z|,|z_{j}|-|z|\\}.$ (58)

We now take an arbitrary root $z$ and construct an appropriate $k_{m}$-cluster
containing $z$. The cluster we will construct will depend on what tier $z$ is
in. If there are not enough roots smaller than $z$, then we will just put the
smallest $k_{m}$ roots in the cluster. As we will see, this will necessarily
include all those roots in $B(z,\epsilon|z|)$. If there are many roots smaller
than $z$, we will choose our cluster to contain all roots in
$B(z,\epsilon|z|)$, with the remaining elements taken to be any small roots.

Recall that $D(\mathcal{T}_{i})=|\mathcal{T}_{i}|$. Let $r$ be chosen such
that $z\in\mathcal{T}_{r}$. In the case that
$D(\mathcal{T}_{r})+D(\mathcal{T}_{r+1})+\ldots+D(\mathcal{T}_{s})\leq k_{m}$
then we choose our cluster
$\mathcal{C}=\left\\{z_{k_{L}},z_{k_{L}-1},\ldots,z_{k_{L}-k_{m}+1}\right\\}\supset\mathcal{T}_{r}\cup\mathcal{T}_{r+1}\cup\ldots\cup\mathcal{T}_{s}$
so that

$\prod_{j\notin\mathcal{C}}|z-z_{j}|\sim|z_{1}z_{2}\ldots z_{k_{L}-k_{m}}|.$

It remains to consider the case that
$D(\mathcal{T}_{r})+D(\mathcal{T}_{r+1})+\ldots+D(\mathcal{T}_{s})>k_{m}$.
After taking roots $\mathcal{C}_{r}=B(z,\epsilon|z|)\cap\mathcal{T}_{r}$, any
choice of $k_{m}-|\mathcal{C}_{r}|$ roots from
$\mathcal{T}_{r}\cup\ldots\cup\mathcal{T}_{s}$ suffices to complete our
cluster $\mathcal{C}$. Indeed, we find, by (58), that

$\prod_{z_{j}\notin\mathcal{C}}|z-z_{j}|$
$=\left(\prod_{z_{j}\in\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\ldots\cup\mathcal{T}_{r-1}}|z-z_{j}|\right)\left(\prod_{j\notin\mathcal{C},z_{j}\in\mathcal{T}_{r}\cup\mathcal{T}_{r+1}\cup\ldots\cup\mathcal{T}_{s}}|z-z_{j}|\right)$