# Tree trace reconstruction using subtraces

Tatiana Brailovskaya Princeton University<EMAIL_ADDRESS>Miklós Z.
Rácz Princeton University<EMAIL_ADDRESS>Research supported in part by
NSF grant DMS 1811724 and by a Princeton SEAS Innovation Award.

###### Abstract

Tree trace reconstruction aims to learn the binary node labels of a tree,
given independent samples of the tree passed through an appropriately defined
deletion channel. In recent work, Davies, Rácz, and Rashtchian [9] used
combinatorial methods to show that $\exp(\mathcal{O}(k\log_{k}n))$ samples
suffice to reconstruct a complete $k$-ary tree with $n$ nodes with high
probability. We provide an alternative proof of this result, which allows us
to generalize it to a broader class of tree topologies and deletion models. In
our proofs, we introduce the notion of a subtrace, which enables us to connect
with and generalize recent mean-based complex analytic algorithms for string
trace reconstruction.

##  1 Introduction

Trace reconstruction is a fundamental statistical reconstruction problem which
has received much attention lately. Here the goal is to infer an unknown
binary string of length $n$, given independent copies of the string passed
through a deletion channel. The deletion channel deletes each bit in the
string independently with probability $q$ and then concatenates the surviving
bits into a trace. The goal is to learn the original string with high
probability using as few traces as possible.

The trace reconstruction problem was introduced two decades ago [19, 3], and
despite lots of work over the past two decades [17, 11, 12, 23, 14, 16, 15, 6,
5, 7, 13], understanding the sample complexity of trace reconstruction remains
wide open. Specifically, the best known upper bound is due to Chase [5] who
showed that $\exp(\widetilde{\mathcal{O}}(n^{1/5}))$ samples suffice; this
work builds upon previous breakthroughs by De, O’Donnell, and Servedio [11,
12], and Nazarov and Peres [23], who simultaneously obtained an upper bound of
$\exp(\mathcal{O}(n^{1/3}))$. In contrast, the best known lower bound is
$\widetilde{\Omega}(n^{3/2})$ (see [15, 6]). Considering average-case strings
as opposed to worst-case ones reduces the sample complexity considerably, but
the large gap remains: the current best known upper and lower bounds are
$\exp(\mathcal{O}(\log^{1/3}n))$ (see [16]) and
$\widetilde{\Omega}(\log^{5/2}n)$ (see [6]), respectively. As we can see, the
bounds are exponentially far apart for both the worst-case and average-case
problems.

Given the difficulty of the trace reconstruction problem, several variants
have been introduced, in part to study the strengths and weaknesses of various
techniques. These include generalizing trace reconstruction from strings to
trees [9] and matrices [18], coded trace reconstruction [8, 4], population
recovery [1, 2, 21], and more [22, 7, 10].

In this work we consider tree trace reconstruction, introduced recently by
Davies, Rácz, and Rashtchian [9]. In this problem we aim to learn the binary
node labels of a tree, given independent samples of the tree passed through an
appropriately defined deletion channel. The additional tree structure makes
reconstruction easier; indeed, in several settings Davies, Rácz, and
Rashtchian [9] show that the sample complexity is polynomial in the number of
bits in the worst case. Furthermore, Maranzatto [20] showed that strings are
the hardest trees to reconstruct; that is, the sample complexity of
reconstructing an arbitrary labeled tree with $n$ nodes is no more than the
sample complexity of reconstructing an arbitrary labeled $n$-bit string.

As demonstrated in [9], tree trace reconstruction provides a natural testbed
for studying the interplay between combinatorial and complex analytic
techniques that have been used to tackle the string variant. Our work
continues in this spirit. In particular, Davies, Rácz, and Rashtchian [9] used
combinatorial methods to show that $\exp(\mathcal{O}(k\log_{k}n))$ samples
suffice to reconstruct complete $k$-ary trees with $n$ nodes, and here we
provide an alternative proof using complex analytic techniques. This
alternative proof also allows us to generalize the result to a broader class
of tree topologies and deletion models. Before stating our results we first
introduce the tree trace reconstruction problem more precisely.

Let $X$ be a rooted tree with unknown binary labels on its $n$ non-root nodes.
We assume that $X$ has an ordering of its nodes, and the children of a given
node have a left-to-right ordering. The goal of tree trace reconstruction is
to learn the labels of $X$ with high probability, using as few traces as
possible, knowing only the deletion model, the deletion probability $q<1$, and
the tree structure of $X$. Throughout this paper, we write ‘with high
probability’ to mean with probability tending to $1$ as $n\to\infty$.

While for strings there is a canonical model of the deletion channel, there is
no such canonical model for trees. Previous work in [9] considered two natural
extensions of the string deletion channel to trees: the Tree Edit Distance
(TED) deletion model and the Left-Propagation (LP) deletion model; see [9] for
details. Here we focus on the TED model, while also introducing a new deletion
model, termed All-Or-Nothing (AON), which is more ‘destructive’ than the other
models. In both models the root never gets deleted.

  * •

Tree Edit Distance (TED) deletion model: Each non-root node is deleted
independently with probability $q$ and deletions are associative. When a node
$v$ gets deleted, all of the children of $v$ now become children of the parent
of $v$. Equivalently, contract the edge between $v$ and its parent, retaining
the label of the parent. The children of $v$ take the place of $v$ in the
left-to-right order; in other words, the original siblings of $v$ that are to
the left of $v$ and survive are now to the left of the children of $v$, and
the same holds to the right of $v$.

  * •

All-Or-Nothing (AON) deletion model: Each non-root node is marked
independently with probability $q$. If a node $v$ is marked, then the whole
subtree rooted at $v$ is deleted. In other words, a node is deleted if and
only if it is marked or it has an ancestor which is marked.

Figure 1 illustrates these two deletion models. We refer to [9] for motivation
and further remarks on the TED deletion model. While the AON deletion model is
significantly more destructive than the TED deletion model, an advantage of
the tools we develop in this work is that we are able to obtain similar
results for arbitrary tree topologies under the AON deletion model.

(a) Original tree

(b) TED model

(c) AON model

Figure 1: Actions of deletion models on a sample tree. Original tree in (a),
with orange nodes to be deleted. Resulting trace in the TED model (b) and the
AON model (c).

Before we state our results, we recall a result of Davies, Rácz, and
Rashtchian [9, Theorem 4].

######  Theorem 1 ([9]).

In the TED model, there exists a finite constant $C$ depending only on $q$
such that $\exp(Ck\log_{k}n)$ traces suffice to reconstruct a complete $k$-ary
tree on $n$ nodes with high probability (here $k\geq 2$).

In particular, note that the sample complexity is polynomial in $n$ whenever
$k$ is a constant. Our first result is an alternative proof of the same
result, under some mild additional assumptions, as stated below in Theorem 2.

######  Theorem 2.

Fix $c\in\mathbb{Z}^{+}$ and let $q<\frac{c}{c+1}$. There exists a finite
constant $C$, depending only on $c$ and $q$, such that for any $k>c$ the
following holds: in the TED model, $\exp(Ck\log_{k}n)$ traces suffice to
reconstruct a complete $k$-ary tree on $n$ nodes with high probability.

The additional assumptions compared to Theorem 1 are indeed mild. For
instance, with $c=1$ in the theorem above, Theorem 1 is recovered for $q<1/2$.
Theorem 2 also allows $q$ to be arbitrarily close to $1$, provided that $k$ is
at least a large enough constant.

In [9], the authors use combinatorial techniques to prove Theorem 1. Our proof
of Theorem 2 uses a mean-based complex analytic approach, similar to [11, 12,
23, 18]. The advantage of our approach is that it allows us to reconstruct
labels of more general tree topologies in the TED deletion model, as stated
below in Theorem 3; the combinatorial proof in [9] does not naturally lend
itself to such a generalization.

######  Theorem 3.

Let $X$ be a rooted tree on $n$ nodes with binary labels, with nodes on level
$\ell$ all having the same number of children $k_{\ell}$. Let
$k_{\max}:=\max_{\ell}k_{\ell}$ and $k_{\min}:=\min_{\ell}k_{\ell}$, where the
minimum goes over all levels except the last one (containing leaf nodes). If
$q<\frac{c}{c+1}$ and $k_{\min}>c$ for some $c\in\mathbb{Z}^{+}$, then there
exists a finite constant $C$, depending only on $c$ and $q$, such that
$\exp(Ck_{\max}\log_{k_{\min}}n)$ traces suffice to reconstruct $X$ with high
probability.

Furthermore, with some slight modifications, our proof of Theorem 2 also
provides a sample complexity bound for reconstructing arbitrary tree
topologies in the AON deletion model.

######  Theorem 4.

Let $X$ be a rooted tree on $n$ nodes with binary labels, let $k_{\max}$
denote the maximum number of children a node has in $X$, and let $d$ be the
depth of $X$. In the AON model, there exists a finite constant $C$ depending
only on $q$ such that $\exp(Ck_{\max}d)$ traces suffice to reconstruct $X$
with high probability.

The key idea in the above proofs is the notion of a subtrace, which is the
subgraph of a trace that consists only of root-to-leaf paths of length $d$,
where $d$ is the depth of the underlying tree. In the proofs of Theorems 2 and
3 we essentially only use the information contained in these subtraces and
ignore the rest of the trace. This trick is key to making the setup amenable
to the mean-based complex analytic techniques.

The rest of the paper follows the following outline. We start with some
preliminaries in Section 2, where we state basic tree definitions and define
the notion of a subtrace more precisely. In Section 3 we present our proof of
Theorem 2. In Section 4 we generalize the methods of Section 3 to a broader
class of tree topologies and deletion models, proving Theorems 3 and 4. We
conclude in Section 5.

##  2 Preliminaries

In what follows, $X$ denotes an underlying rooted tree of known topology along
with binary labels associated with the $n$ non-root nodes of the tree.

Basic tree terminology. A tree is an acyclic graph. A rooted tree has a
special node that is designated as the root. A leaf is a node of degree 1. We
say that a node $v$ is at level $\ell$ if the graph distance between $v$ and
the root is $\ell$. We say that node $v$ is at height $h$ if the largest graph
distance from $v$ to a leaf is $h$. Depth is the largest distance from the
root to a leaf. We say that node $u$ is a child of node $v$ if there is an
edge between $u$ and $v$ and $v$ is closer to the root than $u$ in graph
distance. Similarly, we also call $v$ the parent of $u$. More generally, $v$
is an ancestor of $u$ if there exists a path $v=x_{0}$, $\ldots$, $x_{n}=u$
such that $x_{i}$ is closer to the root than $x_{i+1}$ for every
$i\in\\{0,1,\ldots,n-1\\}$. A complete $k$-ary tree is a tree in which every
non-leaf node has $k$ children.

Subtrace augmentation. Above we defined the subtrace $Z$ as the subgraph of
the trace $Y$ containing all root-to-leaf paths of length $d$, where $d$ is
the depth of $X$. In what follows, it will be helpful to slightly modify the
definition of the subtrace by augmenting $Z$ to $Z^{\prime}$ such that
$Z^{\prime}$ is a complete $k$-ary tree that contains $Z$ as a subgraph. Given
$Z$, we construct $Z^{\prime}$ recursively as follows. We begin by setting
$Z^{\prime}:=Z$. If the root of $Z^{\prime}$ currently has fewer than $k$
children, then add more child nodes to the root to the right of the existing
children and label them 0. Now, consider the leftmost node in level 1 of
$Z^{\prime}$. If it has fewer than $k$ children, add new children to the right
of the existing children of this node and label them 0. Then repeat the same
procedure for the second leftmost node in level 1. Continue this procedure
left to right for each level, moving from top to bottom of the tree. See
Figure 2 for an illustration of this process. In Section 3, when we mention
the subtrace of $X$ we mean the augmented subtrace, constructed as described
here. In Section 4, we will slightly modify the notion of an augmented
subtrace for the different tree topologies we will be considering.

(a) Original tree.

(b) TED trace.

(c) Subtrace.

(d) Augmented subtrace.

Figure 2: Construction of an augmented subtrace. Original tree in (a), with
orange nodes to be deleted. The resulting trace under the TED deletion model
in (b). Subtrace in (c). Augmented subtrace in (d), with blue nodes
corresponding to the padding 0s.

##  3 Reconstructing complete $k$-ary trees in the TED model

In this section we prove Theorem 2. The proof takes inspiration from [11, 12,
23, 18]. We begin by computing, for every node in the original tree, its
probability of survival in a subtrace. We then derive a multivariate complex
generating function for every level $\ell$, with random coefficients
corresponding to the labels of nodes in the subtrace. Finally, we show how we
can “average” the subtraces to determine the correct labeling for each level
of the original tree with high probability.

###  3.1 Computing the probability of node survival in a subtrace

Let $d$ denote the depth of the original tree $X$. Let $Y$ denote a trace of
$X$ and let $Z$ denote the corresponding subtrace obtained from $Y$. Observe
that a node $v$ at level $\ell$ of $X$ survives in the subtrace $Z$ if and
only if a root-to-leaf path that includes $v$ survives in the trace $Y$.
Furthermore, there exists exactly one path from the root to $v$, which
survives in $Y$ with probability $(1-q)^{\ell-1}$ (since each of the $\ell-1$
non-root ancestors of $v$ has to survive independently). Let $p_{d-\ell}$
denote the probability that no $v$-to-leaf path survives in $Y$. Thus,

$\mathbb{P}\left(v\text{ survives in }Z\right)=(1-q)^{\ell-1}(1-p_{d-\ell}).$

Thus, we can see that it suffices to compute $p_{h}$ for
$h\in\\{0,1,\ldots,d-1\\}$ in order to compute the probability of survival of
$v$ in a subtrace. The rest of this subsection is thus dedicated to
understanding $\\{p_{h}\\}_{h=0}^{d-1}$. We will not find an explicit
expression for $p_{h}$, but rather derive a recurrence relation for $p_{h}$,
which will prove to be good enough for us.

Let us denote by $v$ a vertex at height $h$, which is the root of the subtree
under consideration. There are two events that contribute to $p_{h}$. Either
$v$ gets deleted (this happens with probability $q$) or all of the $k$
subtrees rooted at the children of $v$ do not have a surviving root-to-leaf
path in the subtrace (this happens with probability $p_{h-1}^{k}$). Thus, we
have the following recurrence relation: for every $h\geq 0$ we have that

$p_{h+1}=q+(1-q)p_{h}^{k};$ (1)

furthermore, the initial condition satisfies $p_{0}=q$. This recursion allows
to compute $\\{p_{h}\\}_{h=0}^{d-1}$. We now prove the following statement
about this recursion, which will be useful later on.

######  Lemma 1.

Suppose that $0<q<\frac{c}{c+1}$ and $k>c$ for some $c\in\mathbb{Z}^{+}$.
There exists $p^{\prime}<1$, depending only on $c$ and $q$, such that
$p_{i}\leq p^{\prime}<1$ for every $i\geq 0$.

###### Proof.

The function $f(p):=1+p+\ldots+p^{c}$ is continuous and strictly increasing on
$[0,1]$ with $f(0)=1$ and $f(1)=c+1$. The assumption $q\in(0,c/(c+1))$ implies
that $1/(1-q)\in(1,c+1)$, so there exists a unique $p^{\prime}\in(0,1)$ such
that $f(p^{\prime})=1/(1-q)$. By construction $p^{\prime}$ is a function of
$c$ and $q$. We will show by induction that $p_{i}\leq p^{\prime}$ for every
$i\geq 0$.

First, observe that $f(p)\leq\sum_{m\geq 0}p^{m}=1/(1-p)$. Thus
$1/(1-p^{\prime})\geq 1/(1-q)$ and so $q\leq p^{\prime}$. Since $p_{0}=q$,
this proves the base case of the induction.

For the induction step, first note that if $p\in(0,1)$, then
$f(p)=(1-p^{c+1})/(1-p)$. Therefore the equation $f(p^{\prime})=1/(1-q)$
implies that $(1-q)\left(p^{\prime}\right)^{c+1}=p^{\prime}-q$. So if
$p_{i}\leq p^{\prime}$, then (1) implies that $p_{i+1}=q+(1-q)p_{i}^{k}\leq
q+(1-q)\left(p^{\prime}\right)^{c+1}=q+(p^{\prime}-q)=p^{\prime}$, where we
also used the assumption $k\geq c+1$ in the inequality. ∎

###  3.2 Generating function derivation

We begin by introducing some additional notation. Let $b_{\ell,i}$ denote the
label of the node located at level $\ell$ in position $i$ from the left in the
original tree $X$; we start the indexing of $i$ from $0$, so $b_{\ell,0}$ is
the label of the leftmost vertex on level $\ell$. Similarly, let $a_{\ell,i}$
denote the label of the node located at level $\ell$ in position $i$ from the
left in the subtrace $Z$. Observe that for $i\in\\{0,1,\ldots,k^{\ell}-1\\}$
we can write $i=t_{\ell-1}k^{\ell-1}+t_{\ell-2}k^{\ell-2}+\ldots+t_{0}$ with
$t_{i}\in\\{0,\ldots,k-1\\}$, that is, $t_{\ell-1}t_{\ell-2}\ldots t_{0}$ is
the base $k$ representation of $i$. To abbreviate notation, we will write
$a_{\ell,i}=a_{\ell,t_{\ell-1}k^{\ell-1}+t_{\ell-2}k^{\ell-2}+\ldots+t_{0}}$
as simply $a_{\ell,t_{\ell-1}\ldots t_{0}}$.

We introduce, for every level $\ell$, a multivariate complex generating
function whose coefficients are the labels of the nodes at level $\ell$ of a
subtrace $Z$. Specifically, we introduce complex variables
$w_{0},\ldots,w_{\ell-1}$ for each position in the base $k$ representation and
define

$A_{\ell}(w):=\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell-1}=0}^{k-1}a_{\ell,t_{\ell-1}\ldots
t_{0}}w_{\ell-1}^{t_{\ell-1}}\ldots w_{0}^{t_{0}}.$ (2)

We are now ready to state the main result of this subsection, which computes
the expectation of this generating function.

######  Lemma 2.

For every $\ell\in\\{1,\ldots,d\\}$ we have that

$\mathbb{E}[A_{\ell}(w)]=(1-q)^{\ell-1}(1-p_{d-\ell})\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell-1}=0}^{k-1}b_{\ell,t_{\ell-1}\ldots
t_{0}}\prod_{m=0}^{\ell-1}((1-p_{d-\ell+m})w_{m}+p_{d-\ell+m})^{t_{m}}.$ (3)

This lemma is useful because the right hand side of (3) contains the labels of
the nodes on level $\ell$ of $X$, while the left hand side can be estimated by
averaging over subtraces.

###### Proof of Lemma 2.

By linearity of expectation we have that

$\mathbb{E}\left[A_{\ell}(w)\right]=\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell-1}=0}^{k-1}\mathbb{E}\left[a_{\ell,t_{\ell-1}\ldots
t_{0}}\right]w_{\ell-1}^{t_{\ell-1}}\ldots w_{0}^{t_{0}},$ (4)

so our goal is to compute $\mathbb{E}\left[a_{\ell,t_{\ell-1}\ldots
t_{0}}\right]$. For node $i=i_{\ell-1}\ldots i_{0}$ on level $\ell$, we may
interpret each digit $i_{m}$ in the base $k$ representation as follows:
consider node $i$’s ancestor on level $\ell-m$; the horizontal position of
this node amongst its siblings is $i_{m}$. Thus, if the original bit
$b_{\ell,i}$ survives in the subtrace, it can only end up in position
$j=j_{\ell-1}j_{\ell-2}\ldots j_{0}$ on level $\ell$ satisfying $j_{m}\leq
i_{m}$ for every $m$. If the $m$th digit of the location of $b_{\ell,i}$ in
the subtrace is $j_{\ell-m}$, then exactly $i_{\ell-m}-j_{\ell-m}$ siblings
left of the ancestor of $i$ on level $\ell-m$ must have gotten deleted and the
ancestor of $i$ on level $\ell-m$ must have survived in the subtrace. Thus,
the probability that bit $a_{\ell,j}$ of the subtrace is the original bit
$b_{\ell,i}$ is given by

$\displaystyle\mathbb{P}(a_{\ell,j_{\ell-1}\ldots
j_{0}}=b_{\ell,i_{\ell-1}\ldots i_{0}})$
$\displaystyle=\binom{i_{0}}{j_{0}}p_{d-\ell}^{i_{0}-j_{0}}(1-p_{d-\ell})^{j_{0}+1}\times\binom{i_{1}}{j_{1}}p_{d-\ell+1}^{i_{1}-j_{1}}(1-p_{d-\ell+1})^{j_{1}}(1-q)\times\ldots$
$\displaystyle\quad\times\ldots\times\binom{i_{\ell-1}}{j_{\ell-1}}p_{d-1}^{i_{\ell-1}-j_{\ell-1}}(1-p_{d-1})^{j_{\ell-1}}(1-q)$
$\displaystyle=(1-q)^{\ell-1}(1-p_{d-\ell})\prod_{m=0}^{\ell-1}\binom{i_{m}}{j_{m}}p_{d-\ell+m}^{i_{m}-j_{m}}(1-p_{d-\ell+m})^{j_{m}}$

Summing over all $i$ satisfying $i_{m}\geq t_{m}$ for every $m$, and plugging
into (4), we obtain that

$\displaystyle\mathbb{E}\left[A_{\ell}(w)\right]$
$\displaystyle=(1-q)^{\ell-1}(1-p_{d-\ell})\times$
$\displaystyle\quad\times\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell-1}=0}^{k-1}\sum_{i_{0}=t_{0}}^{k-1}\ldots\sum_{i_{\ell-1}=t_{\ell-1}}^{k-1}b_{\ell,i_{\ell-1}\ldots
i_{0}}\prod_{m=0}^{\ell-1}\binom{i_{m}}{t_{m}}p_{d-\ell+m}^{i_{m}-t_{m}}(1-p_{d-\ell+m})^{t_{m}}w_{m}^{t_{m}}.$

Interchanging the order of summations and using the binomial theorem ($\ell$
times) we obtain (3). ∎

###  3.3 Bounding the modulus of the generating function

Here we prove a simple lower bound on the modulus of a multivariate Littlewood
polynomial. This bound will extend to the generating function computed above
for appropriate choices of $w_{m}$. The argument presented here is inspired by
the method of proof of [18, Lemma 4]. Throughout the paper we let $\mathbb{D}$
denote the unit disc in the complex plane and let $\partial\mathbb{D}$ denote
its boundary.

######  Lemma 3.

Let $F(z_{0},\ldots,z_{\ell-1})$ be a nonzero multivariate polynomial with
monomial coefficients in $\\{-1,0,1\\}$. Then,

$\sup_{z_{0},\ldots,z_{\ell-1}\in\partial\mathbb{D}}|F(z_{0},\ldots,z_{\ell-1})|\geq
1.$

###### Proof.

We define a sequence of polynomials $\\{F_{i}\\}_{i=0}^{\ell-1}$ inductively
as follows, where $F_{i}$ is a function of the variables
$z_{i},\ldots,z_{\ell-1}$. First, let $t_{0}$ be the smallest power of $z_{0}$
in a monomial of $F$ and let
$F_{0}(z_{0},\ldots,z_{\ell-1}):=z_{0}^{-t_{0}}F(z_{0},\ldots,z_{\ell-1})$. By
construction, $F_{0}$ has at least one monomial where $z_{0}$ does not appear.
For $i\in\\{1,\ldots,\ell-1\\}$, given $F_{i-1}$ we define $F_{i}$ as follows.
Let $t_{i}$ be the smallest power of $z_{i}$ in a monomial of
$F_{i-1}(0,z_{i},\ldots,z_{\ell-1})$ and let
$F_{i}(z_{i},\ldots,z_{\ell-1}):=z_{i}^{-t_{i}}F_{i-1}(0,z_{i},\ldots,z_{\ell-1})$.
Observe that this construction guarantees, for every $i$, that the polynomial
$F_{i}(z_{i},\ldots,z_{\ell-1})$ has at least one monomial where $z_{i}$ does
not appear. In particular, the univariate polynomial $F_{\ell-1}(z_{\ell-1})$
has a nonzero constant term. Since the coefficients of the polynomial are in
$\\{-1,0,1\\}$, this means that the constant term has absolute value $1$, that
is, $|F_{\ell-1}(0)|=1$.

Let $\left(z_{0}^{*},\ldots,z_{\ell-1}^{*}\right)$ denote the maximizer of
$|F(z_{0},\ldots,z_{\ell-1})|$ with $z_{m}\in\partial\mathbb{D}$ for all $m$.
Now, by the maximum modulus principle, observe that for all $i$ we have that

$|(z_{i}^{*})^{t_{i}}||F_{i}(z_{i}^{*},\ldots,z_{\ell-1}^{*})|=|F_{i}(z_{i}^{*},\ldots,z_{\ell-1}^{*})|\geq|F_{i}(0,z_{i+1}^{*},\ldots,z_{\ell-1}^{*})|.$

Using the definition of $F_{i}$ and iterating the above inequality yields, for
all $i\in\\{0,\ldots,\ell-2\\}$, that

$|(z_{i}^{*})^{t_{i}}||F_{i}(z_{i}^{*},\ldots,z_{\ell-1}^{*})|\geq|F_{i+1}(0,z_{i+2}^{*},\ldots,z_{\ell-1}^{*})|.$

By taking the two ends of this chain of inequalities we can thus see that

$|F(z_{0}^{*},\ldots,z_{\ell-1}^{*})|\geq|F_{\ell-1}(0)|=1.\qed$

###  3.4 Finishing the proof of Theorem 2

###### Proof of Theorem 2.

Let $X^{\prime}$ and $X^{\prime\prime}$ be two complete $k$-ary trees on $n$
non-root nodes with different binary node labels. Our first goal is to
distinguish between $X^{\prime}$ and $X^{\prime\prime}$ using subtraces. At
the end of the proof we will then explain how to estimate the original tree
$X$ using subtraces.

Since $X^{\prime}$ and $X^{\prime\prime}$ have different labels, there exists
at least one level of the tree where the node labels differ. Call the minimal
such level $\ell_{*}=\ell_{*}\left(X^{\prime},X^{\prime\prime}\right)$; we
will use this level of the subtraces to distinguish between $X^{\prime}$ and
$X^{\prime\prime}$. Let

$\left\\{b^{\prime}_{\ell_{*},i}:i\in\left\\{0,1,\ldots,k^{\ell_{*}}-1\right\\}\right\\}\quad\text{
and
}\quad\left\\{b^{\prime\prime}_{\ell_{*},i}:i\in\left\\{0,1,\ldots,k^{\ell_{*}}-1\right\\}\right\\}$

denote the labels on level $\ell_{*}$ of $X^{\prime}$ and $X^{\prime\prime}$,
respectively. Furthermore, for every $i$ define
$b_{\ell_{*},i}:=b^{\prime}_{\ell_{*},i}-b^{\prime\prime}_{\ell_{*},i}$. By
construction, $b_{\ell_{*},i}\in\\{-1,0,1\\}$ for every $i$, and there exists
$i$ such that $b_{\ell_{*},i}\neq 0$. Let $Z^{\prime}$ and $Z^{\prime\prime}$
be subtraces obtained from $X^{\prime}$ and $X^{\prime\prime}$, respectively,
and let

$\left\\{Z^{\prime}_{\ell_{*},i}:i\in\left\\{0,1,\ldots,k^{\ell_{*}}-1\right\\}\right\\}\quad\text{
and
}\quad\left\\{Z^{\prime\prime}_{\ell_{*},i}:i\in\left\\{0,1,\ldots,k^{\ell_{*}}-1\right\\}\right\\}$

denote the labels on level $\ell_{*}$ of $Z^{\prime}$ and $Z^{\prime\prime}$,
respectively. By Lemma 2 we have that

$\mathbb{E}\left[\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell_{*}-1}=0}^{k-1}Z^{\prime}_{\ell_{*},t_{\ell_{*}-1}\ldots
t_{0}}\prod_{m=0}^{\ell_{*}-1}w_{m}^{t_{m}}\right]-\mathbb{E}\left[\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell_{*}-1}=0}^{k-1}Z^{\prime\prime}_{\ell_{*},t_{\ell_{*}-1}\ldots
t_{0}}\prod_{m=0}^{t_{\ell_{*}-1}}w_{m}^{t_{m}}\right]\\\
=(1-q)^{\ell_{*}-1}(1-p_{d-\ell_{*}})\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell_{*}-1}=0}^{k-1}b_{\ell_{*},t_{\ell_{*}-1}\ldots
t_{0}}\prod_{m=0}^{\ell_{*}-1}((1-p_{d-\ell_{*}+m})w_{m}+p_{d-\ell_{*}+m})^{t_{m}}.$

Now define the multivariate polynomial $B(z)$ in the variables
$z=\left(z_{0},\ldots,z_{\ell_{*}-1}\right)$ as follows:

$B(z):=\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell_{*}-1}=0}^{k-1}b_{\ell_{*},t_{\ell_{*}-1}\ldots
t_{0}}\prod_{m=0}^{\ell_{*}-1}z_{m}^{t_{m}}.$

Lemma 3 implies that there exists
$z^{*}=\left(z_{0}^{*},\ldots,z_{\ell_{*}-1}^{*}\right)$ such that
$z_{m}^{*}\in\partial\mathbb{D}$ for every
$m\in\left\\{0,\ldots,\ell_{*}-1\right\\}$ and

$\left|B\left(z^{*}\right)\right|\geq 1.$

For $m\in\left\\{0,\ldots,\ell_{*}-1\right\\}$ let

$w_{m}^{*}:=\frac{z_{m}^{*}-p_{d-\ell_{*}+m}}{1-p_{d-\ell_{*}+m}}.$

Note that the polynomial $B$ is a function of $X^{\prime}$ and
$X^{\prime\prime}$, and thus so is $z^{*}$ and also
$w^{*}=\left(w_{0}^{*},\ldots,w_{\ell_{*}-1}^{*}\right)$. Putting together the
four previous displays and using the triangle inequality we obtain that

$\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell_{*}-1}=0}^{k-1}\left|\mathbb{E}\left[Z^{\prime}_{\ell_{*},t_{\ell_{*}-1}\ldots
t_{0}}\right]-\mathbb{E}\left[Z^{\prime\prime}_{\ell_{*},t_{\ell_{*}-1}\ldots
t_{0}}\right]\right|\prod_{m=0}^{\ell_{*}-1}\left|w_{m}^{*}\right|^{t_{m}}\geq(1-q)^{\ell_{*}-1}(1-p_{d-\ell_{*}}).$
(5)

Next we estimate $\left|w_{m}^{*}\right|$. By the definition of $w_{m}^{*}$
and the triangle inequality we have that

$\left|w_{m}^{*}\right|=\frac{\left|z_{m}^{*}-p_{d-\ell_{*}+m}\right|}{1-p_{d-\ell_{*}+m}}\leq\frac{\left|z_{m}^{*}\right|+p_{d-\ell_{*}+m}}{1-p_{d-\ell_{*}+m}}\leq\frac{2}{1-p^{\prime}},$
(6)

where in the last inequality we used that $\left|z_{m}^{*}\right|=1$ and that
$p_{d-\ell_{*}+m}\leq p^{\prime}<1$ (from Lemma 1). Note that $p^{\prime}$ is
a constant that depends only on $c$ and $q$ (recall that $c$ is an input to
the theorem). The bound in (6) implies that

$\prod_{m=0}^{\ell_{*}-1}\left|w_{m}^{*}\right|^{t_{m}}\leq\left(\frac{2}{1-p^{\prime}}\right)^{k\ell_{*}}.$
(7)

Plugging this back into (5) (and using that $p_{d-\ell_{*}}\leq p^{\prime}$)
we get that

$\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell_{*}-1}=0}^{k-1}\left|\mathbb{E}\left[Z^{\prime}_{\ell_{*},t_{\ell_{*}-1}\ldots
t_{0}}\right]-\mathbb{E}\left[Z^{\prime\prime}_{\ell_{*},t_{\ell_{*}-1}\ldots
t_{0}}\right]\right|\geq(1-q)^{\ell_{*}-1}(1-p^{\prime})^{k\ell_{*}+1}(1/2)^{k\ell_{*}}.$

Thus by the pigeonhole principle there exists
$i_{*}\in\left\\{0,1,\ldots,k^{\ell_{*}}-1\right\\}$ such that

$\left|\mathbb{E}\left[Z^{\prime}_{\ell_{*},i_{*}}\right]-\mathbb{E}\left[Z^{\prime\prime}_{\ell_{*},i_{*}}\right]\right|\geq\frac{(1-q)^{\ell_{*}-1}(1-p^{\prime})^{k\ell_{*}+1}(1/2)^{k\ell_{*}}}{k^{\ell_{*}}}\geq\exp\left(-Ck\ell_{*}\right)\geq\exp\left(-Ck\log_{k}n\right),$
(8)

where the second inequality holds for a large enough constant $C$ that depends
only on $c$ and $q$, while the third inequality is because the depth of the
tree is $\log_{k}n$. Note that $i_{*}$ is a function of $X^{\prime}$ and
$X^{\prime\prime}$.

Now suppose that we sample $T$ traces of $X$ from the TED deletion channel and
let $Z^{1},\ldots,Z^{T}$ denote the corresponding subtraces. Let $X^{\prime}$
and $X^{\prime\prime}$ be two complete $k$-ary labeled trees with different
labels, and recall the definitions of
$\ell_{*}=\ell_{*}\left(X^{\prime},X^{\prime\prime}\right)$ and
$i_{*}=i_{*}\left(X^{\prime},X^{\prime\prime}\right)$ from above. We say that
$X^{\prime}$ _beats_ $X^{\prime\prime}$ (with respect to these samples) if

$\left|\frac{1}{T}\sum_{t=1}^{T}Z^{t}_{\ell_{*},i_{*}}-\mathbb{E}\left[Z^{\prime}_{\ell_{*},i_{*}}\right]\right|<\left|\frac{1}{T}\sum_{t=1}^{T}Z^{t}_{\ell_{*},i_{*}}-\mathbb{E}\left[Z^{\prime\prime}_{\ell_{*},i_{*}}\right]\right|.$

We are now ready to define our estimate $\widehat{X}$ of the labels of the
original tree. If there exists a complete $k$-ary tree $X^{\prime}$ that beats
every other complete $k$-ary tree (with respect to these samples), then we let
$\widehat{X}:=X^{\prime}$. Otherwise, define $\widehat{X}$ arbitrarily.

Finally, we show that this estimate is correct with high probability. Let
$\eta:=\exp\left(-Ck\log_{k}n\right)$. By a union bound and a Chernoff bound
(using (8)), the probability that the estimate is incorrect is bounded by

$\mathbb{P}\left(\widehat{X}\neq X\right)\leq\sum_{X^{\prime}:X^{\prime}\neq
X}\mathbb{P}\left(X^{\prime}\text{ beats }X\right)\leq
2^{n}\exp\left(-T\eta^{2}/2\right)=2^{n}\exp\left(-\frac{T}{2}\exp\left(-2Ck\log_{k}n\right)\right).$

Choosing $T=\exp\left(3Ck\log_{k}n\right)$, the right hand side of the display
above tends to $0$. ∎

##  4 Reconstructing more general tree topologies

The method of proof shown in the previous section naturally lends itself to
the more general results of Theorem 3 for the TED deletion model and Theorem 4
for the AON deletion model. The proofs are almost entirely identical to the
one presented above, so we will only highlight the new ideas below and leave
the details to the reader.

###  4.1 TED deletion model, more general tree topologies

Before we proceed with the proof, we must clarify the notion of a subtrace. In
Section 2 we described the notion of an augmented subtrace for a $k$-ary tree.
More generally, for trees in the setting of Theorem 3, we define an augmented
subtrace in a similar way; the key point is that the underlying tree structure
of the augmented subtrace is the same as the underlying tree structure of $X$.
That is, we start with the root of the subtrace $Z$, and if it has less than
$k_{0}$ children, we add nodes with $0$ labels to the right of its existing
children, until the root has $k_{0}$ children in total. We then move on to the
leftmost node on level $1$ and add new children with label 0 to the right of
its existing children, until it has $k_{1}$ children. We continue in this
fashion from left to right on each level, ensuring that each node on level
$\ell$ has $k_{\ell}$ children, moving from top to bottom of the tree.

###### Proof of Theorem 3.

As before, we begin by computing, for every node in the tree, its probability
of survival in a subtrace. The quantities $\\{p_{h}\\}_{h=0}^{d-1}$ can be
defined exactly as before, where again $d$ denotes the depth of the tree. The
recurrence relation changes slightly: for every $h\geq 0$ we have that

$p_{h+1}=q+(1-q)p_{h}^{k_{d-h-1}};$

furthermore, the initial condition satisfies $p_{0}=q$. The following lemma is
the analog of Lemma 1; we omit its proof, since it is identical to that of
Lemma 1.

######  Lemma 4.

Suppose that $0<q<\frac{c}{c+1}$ and $k_{\min}>c$ for some
$c\in\mathbb{Z}^{+}$. There exists $p^{\prime}<1$, depending only on $c$ and
$q$, such that $p_{i}\leq p^{\prime}<1$ for every $i\geq 0$.

Next, we turn to defining and analyzing an appropriate generating function.
Note that there are $\prod_{m=0}^{\ell-1}k_{m}$ nodes on level $\ell$ of the
tree $X$. Observe that every
$i\in\left\\{0,1,\ldots,\prod_{m=0}^{\ell-1}k_{m}-1\right\\}$ can be uniquely
written as

$i=i_{\ell-1}\prod_{m=1}^{\ell-1}k_{m}+i_{\ell-2}\prod_{m=2}^{\ell-1}k_{m}+\ldots+i_{1}k_{\ell-1}+i_{0},$
(9)

where $i_{m}\in\left\\{0,1,\ldots,k_{\ell-1-m}-1\right\\}$ for every
$m\in\\{0,1,\ldots,\ell-1\\}$. The interpretation of each digit $i_{m}$ in
this representation is the same as before: consider node $i$’s ancestor on
level $\ell-m$; the horizontal position of this node amongst its siblings is
$i_{m}$. To abbreviate notation, we write $i=i_{\ell-1}\ldots i_{0}$ for the
expression in (9). With this representation of the nodes at level $\ell$, we
may define the generating function for level $\ell$ as follows:

$A_{\ell}(w):=\sum_{t_{0}=0}^{k_{\ell-1}-1}\ldots\sum_{t_{\ell-1}=0}^{k_{0}-1}a_{\ell,t_{\ell-1}\ldots
t_{0}}w_{\ell-1}^{t_{\ell-1}}\ldots w_{0}^{t_{0}}.$

The following lemma is the analog of Lemma 2; we omit its proof, since it is
analogous to that of Lemma 2.

######  Lemma 5.

For every $\ell\in\\{1,\ldots,d\\}$ we have that

$\mathbb{E}[A_{\ell}(w)]=(1-q)^{\ell-1}(1-p_{d-\ell})\sum_{t_{0}=0}^{k_{\ell-1}-1}\ldots\sum_{t_{\ell-1}=0}^{k_{0}-1}b_{\ell,t_{\ell-1}\ldots
t_{0}}\prod_{m=0}^{\ell-1}((1-p_{d-\ell+m})w_{m}+p_{d-\ell+m})^{t_{m}}.$

With these tools in place, the remainder of the proof is almost identical to
Section 3.4. The inequality (7) is now replaced with

$\prod_{m=0}^{\ell_{*}-1}\left|w_{m}^{*}\right|^{t_{m}}\leq\left(\frac{2}{1-p^{\prime}}\right)^{k_{\max}\ell_{*}}.$

Subsequently, by the pigeonhole principle there exists
$i_{*}\in\left\\{0,1,\ldots,\prod_{m=0}^{\ell_{*}-1}k_{m}-1\right\\}$ such
that

$\left|\mathbb{E}\left[Z^{\prime}_{\ell_{*},i_{*}}\right]-\mathbb{E}\left[Z^{\prime\prime}_{\ell_{*},i_{*}}\right]\right|\geq\exp\left(-Ck_{\max}\ell_{*}\right)\geq\exp\left(-Ck_{\max}d\right),$

where the first inequality holds for a large enough constant $C$ that depends
only on $c$ and $q$. The rest of the proof is identical to Section 3.4,
showing that $T=\exp\left(3Ck_{\max}d\right)$ traces suffice. The claim
follows because the depth of the tree is at most $\log_{k_{\min}}n$. ∎

###  4.2 AON deletion model, arbitrary tree topologies

We begin by first proving Theorem 4 for complete $k$-ary trees. We will then
generalize to arbitrary tree topologies. Importantly, in the AON model we will
work directly with the tree traces, as opposed to the subtraces as we did
previously. As described in Section 2, we augment each trace $Y$ with
additional nodes with 0 labels to form a $k$-ary tree. In what follows, when
we say “trace” we mean this augmented trace.

######  Theorem 5.

In the AON model, there exists a finite constant $C$ depending only on $q$
such that $\exp(Ck\log_{k}n)$ traces suffice to reconstruct a complete $k$-ary
tree on $n$ nodes w.h.p. (here $k\geq 2$).

###### Proof.

We may define $A_{\ell}(w)$, the generating function for level $\ell$, exactly
as in (2). The following lemma is the analog of Lemma 2; we omit its proof,
since it is analogous to that of Lemma 2.

######  Lemma 6.

For every $\ell\in\\{1,\ldots,d\\}$ we have that

$\mathbb{E}\left[A_{\ell}(w)\right]=(1-q)^{\ell}\sum_{t_{0}=0}^{k-1}\ldots\sum_{t_{\ell-1}=0}^{k-1}b_{\ell,t_{\ell-1}\ldots
t_{0}}\prod_{m=0}^{\ell-1}((1-q)w_{m}+q)^{t_{m}}.$

With this lemma in place, the remainder of the proof is almost identical to
Section 3.4. The polynomial $B(z)$, and hence also $z^{*}$, are as before.
Now, we define $w_{m}^{*}:=\left(z_{m}^{*}-q\right)/(1-q)$. The right hand
side of (5) becomes $(1-q)^{\ell_{*}}$. The analog of (6) becomes the
inequality $\left|w_{m}^{*}\right|\leq 2/(1-q)$; moreover, wherever
$p^{\prime}$ appears in Section 3.4, it is replaced by $q$ here. Altogether,
we obtain that there exists
$i_{*}\in\left\\{0,1,\ldots,k^{\ell_{*}}-1\right\\}$ such that

$\left|\mathbb{E}\left[Z^{\prime}_{\ell_{*},i_{*}}\right]-\mathbb{E}\left[Z^{\prime\prime}_{\ell_{*},i_{*}}\right]\right|\geq\exp\left(-Ck\ell_{*}\right)\geq\exp\left(-Ckd\right)\geq\exp\left(-Ck\log_{k}n\right),$

where the first inequality holds for a large enough constant $C$ that depends
only on $q$. The rest of the proof is identical to Section 3.4, showing that
$T=\exp\left(3Ckd\right)=\exp\left(3Ck\log_{k}n\right)$ traces suffice. ∎

###### Proof of Theorem 4.

Suppose that $X$ is a rooted tree with arbitrary topology and let $k_{\max}$
denote the largest number of children a node in $X$ has. Once we sample a
trace $Y$ from $X$, we form an augmented trace similarly to how we do it when
$X$ is a $k$-ary tree, except now we add nodes with $0$ labels to ensure that
each node has $k_{\max}$ children. Thus, each augmented trace is a complete
$k_{\max}$-ary tree. Now, let $X^{\prime}$ denote a $k_{\max}$-ary tree
obtained by augmenting $X$ to a $k_{\max}$-ary tree in the same fashion that
we augment traces of $X$ to a $k_{\max}$-ary tree.

As before, for each node $i$ on level $\ell$ of $X$, there is a unique
representation $i=i_{\ell-1}\ldots i_{0}$ where $i_{m}$ is the position of
node $i$’s ancestor on level $\ell-m$ among its siblings. Importantly, for
every node in $X$, its representation in $X^{\prime}$ is the same. This fact,
together with the augmentation construction, implies that
$\mathbb{E}[a_{\ell,t_{\ell-1}\ldots t_{0}}]$ for the node
$a_{\ell,t_{\ell-1}\ldots t_{0}}$ in $Y$ is identical to
$\mathbb{E}[a_{\ell,t_{\ell-1}\ldots t_{0}}]$ for the node
$a_{\ell,t_{\ell-1}\ldots t_{0}}$ in $Y^{\prime}$, which is a trace sampled
from $X^{\prime}$. Therefore, we can use the procedure presented in Theorem 5
to reconstruct $X^{\prime}$ w.h.p. using $T=\exp\left(Ck_{\max}d\right)$
traces sampled from $X$. By taking the appropriate subgraph of $X^{\prime}$,
we can thus reconstruct $X$ as well. ∎

##  5 Conclusion

In this work we introduce the notion of a subtrace and demonstrate its utility
in analyzing traces produced by the deletion channel in the tree trace
reconstruction problem. We provide a novel algorithm for the reconstruction of
complete $k$-ary trees, which matches the sample complexity of the
combinatorial approach of [9], by applying mean-based complex analytic tools
to the subtrace. This technique also allows us to reconstruct trees with more
general topologies in the TED deletion model, specifically trees where the
nodes at every level have the same number of children (with this number
varying across levels).

However, many questions remain unanswered; we hope that the ideas introduced
here will help address them. In particular, how can we reconstruct, under the
TED deletion model, arbitrary trees where all leaves are on the same level?
Since the notion of a subtrace is well-defined for such trees, we hope that
the proof technique presented here can somehow be generalized to answer this
question.

## References

  * [1] Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, and Sandip Sinha.  Beyond trace reconstruction: Population recovery from the deletion channel.  In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 745–768, 2019.
  * [2] Frank Ban, Xi Chen, Rocco A. Servedio, and Sandip Sinha.  Efficient average-case population recovery in the presence of insertions and deletions.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 145 of LIPIcs, pages 44:1–44:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [3] Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor.  Reconstructing strings from random traces.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 910–918, 2004.
  * [4] Joshua Brakensiek, Ray Li, and Bruce Spang.  Coded trace reconstruction in a constant number of traces.  In Proceedings of the IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2020.
  * [5] Zachary Chase.  New upper bounds for trace reconstruction.  Preprint available at https://arxiv.org/abs/2009.03296, 2020.
  * [6] Zachary Chase.  New Lower Bounds for Trace Reconstruction.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, to appear, 2021.
  * [7] Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha.  Polynomial-time trace reconstruction in the smoothed complexity model.  In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.
  * [8] Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, and Joao Ribeiro.  Coded trace reconstruction.  IEEE Transactions on Information Theory, 66(10):6084–6103, 2020\.
  * [9] Sami Davies, Miklós Z. Rácz, and Cyrus Rashtchian.  Reconstructing Trees from Traces.  The Annals of Applied Probability, to appear, 2021.
  * [10] Sami Davies, Miklós Z. Rácz, Cyrus Rashtchian, and Benjamin G. Schiffer.  Approximate trace reconstruction.  Preprint available at https://arxiv.org/abs/2012.06713, 2020.
  * [11] Anindya De, Ryan O’Donnell, and Rocco A. Servedio.  Optimal mean-based algorithms for trace reconstruction.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1047–1056, 2017.
  * [12] Anindya De, Ryan O’Donnell, and Rocco A. Servedio.  Optimal mean-based algorithms for trace reconstruction.  The Annals of Applied Probability, 29(2):851–874, 2019.
  * [13] Elena Grigorescu, Madhu Sudan, and Minshen Zhu.  Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance.  Preprint available at https://arxiv.org/abs/2011.13737, 2020.
  * [14] Lisa Hartung, Nina Holden, and Yuval Peres.  Trace reconstruction with varying deletion probabilities.  In Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 54–61, 2018.
  * [15] Nina Holden and Russell Lyons.  Lower bounds for trace reconstruction.  Annals of Applied Probability, 30(2):503–525, 2020.
  * [16] Nina Holden, Robin Pemantle, Yuval Peres, and Alex Zhai.  Subpolynomial trace reconstruction for random strings and arbitrary deletion probability.  Mathematical Statistics and Learning, 2(3):275–309, 2020.
  * [17] Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder.  Trace reconstruction with constant deletion probability and related results.  In Proc. 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 389–398, 2008.
  * [18] Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal.  Trace Reconstruction: Generalized and Parameterized.  In 27th Annual European Symposium on Algorithms (ESA 2019), pages 68:1–68:25, 2019.
  * [19] Vladimir I Levenshtein.  Efficient reconstruction of sequences.  IEEE Transactions on Information Theory, 47(1):2–22, 2001.
  * [20] Thomas J. Maranzatto.  Tree Trace Reconstruction: Some Results.  Thesis, New College of Florida, 2020.
  * [21] Shyam Narayanan.  Population Recovery from the Deletion Channel: Nearly Matching Trace Reconstruction Bounds.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.
  * [22] Shyam Narayanan and Michael Ren.  Circular Trace Reconstruction.  In Proceedings of Innovations in Theoretical Computer Science (ITCS), 2021.
  * [23] Fedor Nazarov and Yuval Peres.  Trace reconstruction with $\exp(O(n^{1/3}))$ samples.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1042–1046, 2017.


# On the prime graph of a finite group with unique nonabelian composition
factor

Maria A. Grechkoseeva  Sobolev Institute of Mathematics
Koptyuga 4, Novosibirsk 630090, Russia  and  Andrey V. Vasil’ev  Sobolev
Institute of Mathematics
Koptyuga 4, Novosibirsk 630090, Russia
Novosibirsk State University
Pirogova 1, Novosibirsk 630090, Russia<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We say that finite groups are isospectral if they have the same sets of orders
of elements. It is known that every nonsolvable finite group $G$ isospectral
to a finite simple group has a unique nonabelian composition factor, that is,
the quotient of $G$ by the solvable radical of $G$ is an almost simple group.
The main goal of this paper is prove that this almost simple group is a cyclic
extension of its socle.

To this end, we consider a general situation when $G$ is an arbitrary group
with unique nonabelian composition factor, not necessarily isospectral to a
simple group, and study the prime graph of $G$, where the prime graph of $G$
is the graph whose vertices are the prime numbers dividing the order of $G$
and two such numbers $r$ and $s$ are adjacent if and only if $r\neq s$ and $G$
has an element of order $rs$. Namely, we establish some sufficient conditions
for the prime graph of such a group to have a vertex adjacent to all other
vertices. Besides proving the main result, this allows us to refine a recent
result by P. Cameron and N. Maslova concerning finite groups almost
recognizable by prime graph.

Keywords: almost simple group, group of Lie type, order of an element,
recognition by spectrum, prime graph

This work was supported by the Program of Fundamental Scientific Researches of
the Siberian Branch of Russian Academy of Sciences, I.1.1, project
0314-2019-0001

##  1\. Introduction

Given a finite group $G$, we denote the set of prime divisors of the order of
$G$ by $\pi(G)$. The set of element orders of $G$ is called the spectrum of
$G$ and denoted by $\omega(G)$. If $\omega(G)=\omega(H)$, then $G$ and $H$ are
said to be isospectral.

Suppose that $G$ is a finite group isospectral to a finite nonabelian simple
group $L$. Then $G$ is either solvable, in which case $L$ is one of
$L_{3}(3)$, $U_{3}(3)$, $S_{4}(3)$, or has exactly one nonabelian composition
factor (see [5, Theorem 2]). In what follows, we assume that $G$ is not
solvable, and so $G$ has a normal series

(1.1) $1\leqslant K<H\leqslant G,$

where $K$ is the solvable radical of $G$, $H/K$ is a nonabelian simple group
and $G/K$ is an almost simple group with socle $H/K$. Denoting $H/K$ by $S$,
we may identify $G/K$ with a subgroup of $\operatorname{Aut}S$, and then $G/H$
with a subgroup of $\operatorname{Out}S=\operatorname{Aut}S/S$. Observe that
$G/H$ is solvable.

If $L$ is sufficiently ’large’, more precisely, if $L$ is a classical group of
dimension at least 38 or a non-classical group other than $Alt_{6}$,
$Alt_{10}$, $J_{2}$, ${}^{3}D_{4}(2)$, then $K=1$ and $H\simeq L$ (see [9,
13]). Furthermore, it follows that $G/H$ is cyclic (see [8] and the references
therein). In general case, $K$ is not always trivial and $H/K$ is not always
isomorphic to $L$ but in all known examples, $G/H$ is cyclic. This observation
suggests us to conjecture that $G/H$ is always cyclic and the main goal of
this paper is to prove this conjecture.

###### Theorem 1.

Let $L$ be a finite nonabelian simple group and let $G$ be a nonsolvable
finite group with $\omega(G)=\omega(L)$. Suppose that $1\leqslant K<H\leqslant
G$ is the normal series of $G$ as in (1.1). Then $G/H$ is cyclic. Furthermore,
if $H/K$ is a simple group of Lie type other than $L_{2}(q)$, then $G/H$ does
not contain diagonal automorphisms.

If $L$ is sporadic or alternating, Theorem 1 is a direct consequence of the
known description of groups isospectral to $L$. If $L$ is a group of Lie type,
the proof has several ingredients. The first is the well-known property of
spectra of groups of Lie type stated in Lemma 2.1 in Section 2. The second is
the nilpotency of the solvable radical of $G$ established in [18]. The third
is the following Theorem 2 which concerns all finite groups of some specific
structure, not only those isospectral to simple groups.

###### Theorem 2.

Suppose that a finite group $G$ has a normal series $1\leqslant K<H\leqslant
G$, where $K$ is the solvable radical of $G$, $S=H/K$ is a finite simple group
of Lie type, and $G/K\leq\operatorname{Aut}S$. Suppose also that $K$ is
nilpotent.

  1. (i)

If $S\neq L_{2}(q)$ and $G/H$ contains a diagonal automorphism of $S$ of prime
order $r$, then $rs\in\omega(G)$ for all $s\in\pi(G)\setminus\\{r\\}$.

  2. (ii)

If $G/H$ is not cyclic, then there is $r\in\pi(G/H)$ such that
$rs\in\omega(G)$ for all $s\in\pi(G)\setminus\\{r\\}$.

The set $\omega(G)$ defines the prime graph of $G$ as follows: the vertex set
of this is $\pi(G)$ and two primes $r,s\in\pi(G)$ are adjacent if and only if
$r\neq s$ and $rs\in\omega(G)$. The prime graph is also known as the
Gruenberg–Kegel graph and we denote it by $GK(G)$. It is not hard to see that
Theorem 2 states a property of the graph $GK(G)$ rather than of the whole set
$\omega(G)$. This allows us to apply this theorem to the problem of
recognition of simple groups by prime graph. Recently, P. Cameron and N.
Maslova [1] proved several new results relating to this problem. In Theorem 3,
we slightly refine Theorem 1.4 of [1].

###### Theorem 3.

There exists a function $F(x)=O(x^{5})$ such that for each labeled graph
$\Gamma$, the following conditions are equivalent:

  1. (i)

there exist infinitely many groups $H$ such that $GK(H)=\Gamma$;

  2. (ii)

there exist more than $F(|V(\Gamma)|)$ groups $H$ such that $GK(H)=\Gamma$,
where $V(\Gamma)$ is the set of the vertices of $\Gamma$.

In fact, Theorem 1.4 of [1] states exactly the same as Theorem 3 but with
$x^{7}$ in place of $x^{5}$.

##  2\. Proofs of Theorems 1 and 2

We begin this section with notation and preliminary results. We write
$L^{\varepsilon}_{n}(q)$ and $E^{\varepsilon}_{6}(q)$ assuming that
$\varepsilon\in\\{+,-\\}$, $L_{n}^{+}(q)=L_{n}(q)$, $L_{n}^{-}(q)=U_{n}(q)$,
$E_{6}^{+}(q)=E_{6}(q)$, and $E_{6}^{-}(q)={}^{2}E_{6}(q)$. If $r$ is a prime
and $a$ is an integer, then $(a)_{r}$ is the highest power of $r$ dividing
$a$. If $S$ is a group of Lie type, then $\operatorname{Inndiag}S$ is the
subgroup of $\operatorname{Aut}S$ generated by inner and diagonal
automorphisms, and $\operatorname{Outdiag}S$ is the image of
$\operatorname{Inndiag}S$ in $\operatorname{Out}S$. Also we use the terms
‘field automorphism’ and ‘graph automorphism’ of $S$ according to [4,
Definition 2.5.13].

###### Lemma 2.1.

If $S$ is a finite simple group of Lie type, then for every $r\in\pi(S)$ there
is $s\in\pi(S)$ such that $r\neq s$ and $rs\not\in\omega(S)$.

  * Proof.

This follows from [16, 17] (see, for example, [6, Lemma 2.2]). ∎

###### Lemma 2.2.

Let $S$ be a finite simple group of Lie type in characteristic $p$. If $r$
divides $|\operatorname{Outdiag}S|$ and $rp\not\in\omega(S)$, then either
$S=L_{2}(q)$, or $S=L_{3}^{\varepsilon}(q)$ and $(q-\varepsilon)_{3}=3$.

  * Proof.

This follows, for example, from [16, Propositions 3.1 and 3.2]. ∎

###### Lemma 2.3.

Let $S$ be a finite simple group of Lie type in characteristic $p$. If
$r\in\pi(S)$, $r$ is odd and $2r\not\in\omega(S)$, then either a Sylow
$r$-subgroup of $S$ is cyclic, or $S=L_{2}(q)$ and $r=p$, or
$S=L_{3}^{\varepsilon}(q)$, $p=2$, $r=3$ and $(q-\varepsilon)_{3}=3$.

  * Proof.

This follows from the results of [16, Sections 3 and 4] and the cross-
characteristic Sylow structure of groups of Lie type [3, (10-2)]. ∎

###### Lemma 2.4.

Let $S={}^{t}\Sigma(q)$ be a finite simple group of Lie type, not a Suzuki–Ree
group, and let $\varphi$ be a field automorphism of $S$ of prime order $r$.
Then
$r\cdot\omega(^{t}\Sigma(q^{1/r}))\subseteq\omega(S\rtimes\langle\varphi\rangle)$.

  * Proof.

This follows from the Lang–Steinberg theorem [14, Section 10] (see, for
example, [7, Lemma 2.8]). ∎

###### Lemma 2.5.

Suppose that $G$ is a finite group, $K$ is a normal subgroup of $G$ and every
$g\in G\setminus K$ acts fixed-point-freely on $K$. Then every odd order Sylow
subgroup of $G/K$ is cyclic and a Sylow $2$-subgroup of $G/K$ is cyclic or
generalized quaternion.

  * Proof.

This is a well-known property of fixed-point-free automorphisms (see, for
example, [10, Satz 8.7]). ∎

  * Proof of Theorem 2.

Denote the defining characteristic of $S$ by $p$, $G/K$ by $\overline{G}$ and
$G/H$ by $\widehat{G}$. As we remarked in the introduction, $\widehat{G}$ can
be regarded as a subgroup of $\operatorname{Out}S$.

Clearly, we may assume that either $\operatorname{Outdiag}S\neq 1$ or
$\operatorname{Out}S$ is not cyclic, in particular, we may assume that $S$ is
not a Suzuki–Ree group and so $3\in\pi(S)$.

(i) Suppose that $r\in\pi(\widehat{G}\cap\operatorname{Outdiag}S)$. Observe
that $r\in\pi(S)$ and $r\neq p$. By Lemma 2.2, it follows that
$rp\in\omega(S)$ unless $S=L_{3}^{\varepsilon}(q)$, $r=3$ and
$(q-\varepsilon)_{3}=3$. In this case
$PGL_{3}^{\varepsilon}(q)\leqslant\overline{G}$, and since
$PGL_{3}^{\varepsilon}(q)$ has an element of order $p(q-\varepsilon)$, we see
that $rp\in\omega(\overline{G})$.

Suppose that $s\in\pi(S)$ and $s\neq p$. If
$s\in\pi(\operatorname{Outdiag}S)$, then $rs\in\omega(S)$ since
$\operatorname{Outdiag}S$ is abelian. So we may assume that
$s\not\in\pi(\operatorname{Outdiag}S)$. The maximal tori of
$\operatorname{Inndiag}S$ are isomorphic to those of the universal version
$\tilde{S}_{u}$ of $\tilde{S}$, where $\tilde{S}=S$ if $S$ is not of type
$B_{n}$ or $C_{n}$, and $\tilde{B}_{n}(q)=C_{n}(q)$,
$\tilde{C}_{n}(q)=B_{n}(q)$ (see [2, Section 4.4]). Since every maximal torus
of $\tilde{S}_{u}$ contains the center $Z(\tilde{S}_{u})$ of $\tilde{S}_{u}$
and $|Z(\tilde{S}_{u})|=|\operatorname{Outdiag}S|$, we see that
$\operatorname{Inndiag}S$ includes a maximal torus whose order is divisible by
$s|\operatorname{Outdiag}S|$. So $\overline{G}$ contains an abelian subgroup
of order $sr$.

Let $s\in\pi(\overline{G})\setminus\pi(S)$. Since $s\neq 2,3$ and
$s\not\in\pi(\operatorname{Outdiag}S)$, it follows that $G/K$ contains a field
automorphism of $S$ of order $s$. By Lemma 2.4, we have
$s\cdot\omega(S_{0})\subseteq\omega(G/K)$, where $S_{0}$ is a group of the
same Lie type as $S$. If $r=2,3$, then it is clear that $r\in\pi(S_{0})$. If
$r\neq 2,3$, then $S=L_{n}^{\varepsilon}(q)$, $r$ divides $(n,q-\varepsilon)$
and $S_{0}=L_{n}^{\varepsilon}(q^{1/s})$. Since $r$ divides
$p^{r-1}-\varepsilon^{r-1}$ and $r-1\leqslant n-1$, we see that
$r\in\pi(S_{0})$.

Let $s\in\pi(K)\setminus\pi(\overline{G})$. If $r=2$, then $s$ is adjacent to
$r$ in $GK(G)$ by [15, Proposition 2]. So we may assume that $r$ is odd. If
$S=E_{6}^{\varepsilon}(q)$ or $S=L_{n}^{\varepsilon}(q)$ with $n\geqslant 4$,
then $S$ includes a torus of the form
$\mathbb{Z}_{q-\varepsilon}\times\mathbb{Z}_{q-\varepsilon}$, and hence $S$
includes an elementary abelian group of order $r^{2}$. If
$L=L_{3}^{\varepsilon}(q)$, then
$PGL_{3}^{\varepsilon}(q)\leqslant\overline{G}$ and so $\overline{G}$ includes
an elementary abelian group of order $r^{2}$. Now we apply Lemma 2.5 to
conclude that $rs\in\omega(G)$.

(ii) Let $S\neq L_{2}(q)$. By (i), we may assume that
$\widehat{G}\cap\operatorname{Outdiag}S=1$. Then either $\widehat{G}$ includes
an elementary abelian group of order $2^{2}$, or $S=O_{8}^{+}(q)$ and, up to
conjugation in $\operatorname{Out}S$, $\widehat{G}$ contains the image of the
graph automorphism $\gamma$ of $S$ induced by the symmetry of the Dynkin
diagram of order $3$.

In the first case, $S=L_{n}(q)$, $O_{2n}^{+}(q)$, or $E_{6}(q)$, and we claim
that $2$ is adjacent to all odd primes in $GK(G)$. By [15, Proposition 2],
every $s\in\pi(K)\cup\pi(\widehat{G})$ is adjacent to $2$. Now let
$t\in\pi(S)$ and suppose that $2t\not\in\omega(S)$. Excluding for a while the
case when $t=3$, $S=L_{3}(q)$, $p=2$, $(q-1)_{3}=3$ and applying Lemma 2.3, we
conclude that a Sylow $t$-subgroup $T$ of $S$ is cyclic, and hence
$N_{\overline{G}}(T)/C_{\overline{G}}(T)$ is cyclic. On the other hand, by the
Frattini argument, $N_{\overline{G}}(T)/(N_{\overline{G}}(T)\cap
S)\simeq\widehat{G}$, and so a Sylow $2$-subgroup of $N_{\overline{G}}(T)$ is
not cyclic. Thus $2\in C_{\overline{G}}(T)$, and $2t\in\omega(\overline{G})$.

Suppose that $t=3$, $S=L_{3}(q)$, $p=2$, and $(q-1)_{3}=3$. Since
$\widehat{G}$ includes an elementary abelian group of order $2^{2}$, it
follows that $\overline{G}$ contains a field automorphism of $S$ of order $2$,
and so $6\in\omega(\overline{G})$.

Now suppose that $S=O_{8}^{+}(q)$ and $\overline{G}$ contains the graph
automorphism $\gamma$. The centralizer of $\gamma$ in $S$ is isomorphic to
$G_{2}(q)$ [3, (9-1)] and so $3s\in\omega(G)$ for all $3\neq s\in G_{2}(q)$.
Since $S$ includes an elementary abelian group of order $9$, we conclude that
$3s\in\omega(G)$ for all $s\in\pi(K)\setminus\\{3\\}$. Also a
$2^{\prime}$-Hall subgroup of $\operatorname{Out}S$ is abelian, and hence $3$
is adjacent to every $s\in\pi(\widehat{G})\setminus\\{2,3\\}$ in
$GK(\widehat{G})$.. Let $s\in\pi(S)\setminus\\{3\\}$ and $3s\not\in\omega(S)$.
Then $s$ divides $q^{2}+q+1$ or $q^{2}-q+1$, therefore, $s\in\pi(G_{2}(q))$
and, as we remarked, $3s\in\omega(G)$. Thus $3$ is adjacent to all vertices in
$GK(G)$.

Let $S=L_{2}(q)$, where $q=p^{l}$. We claim that $2$ is adjacent to all odd
primes in $GK(G)$. Since $\operatorname{Out}S$ is a direct product of cyclic
groups of orders $(2,q-1)$ and $l$, it follows that $p$ is odd, $l$ is even
and $\overline{G}=PGL_{2}(q)\rtimes\langle\varphi\rangle$, where $\varphi$ is
a field automorphism of $S$ of even order. Since $PGL_{2}(q)$ contains
elements of orders $q\pm 1$ and $2p\in\omega(\overline{G})$ by Lemma 2.4, we
see that $2$ is adjacent to every odd $s\in\pi(\overline{G})$. Let
$s\in\pi(K)$ be odd. A Sylow 2-subgroup of $PGL_{2}(q)$ is dihedral, and so it
cannot act fixed-point-freely on a Sylow $s$-subgroup of $K$ by Lemma 2.5.
Hence $2s\in\pi(G)$, and the proof of Theorem 2 is complete. ∎

Now we are able to prove Theorem 1. Let $S=H/K$. Clearly, we may assume that
$\operatorname{Out}S$ is not cyclic. In particular, we may assume that $S$ is
neither sporadic nor alternating with the following convention: if
$S=Alt_{6}\simeq L_{2}(9)$, we regard $S$ as a group of Lie type.

If $L$ is sporadic and $L\neq J_{2}$, or if $L=Alt_{n}$ and $n\neq 6,10$, then
$G\simeq L$ (see [11] and [5] respectively). If $L=J_{2}$, then $G\simeq L$ or
$S=Alt_{8}$ by [11]. If $L=Alt_{10}$, then $G\simeq L$ or $S=Alt_{5}$ by [12].
If $L=Alt_{6}$, we regard $L$ as a group of Lie type.

Let $L$ be a group of Lie type. By [18, Theorem 1], it follows that $K$ is
nilpotent, and so $G$ satisfies the hypothesis of Theorem 2. If $G/H$ is not
cyclic or if $S\neq L_{2}(q)$ and $G/H$ contains a diagonal automorphism of
$S$, then there is $r\in\pi(G)$ adjacent to all other vertices in $GK(G)$. But
this is impossible by Lemma 2.1 since $GK(G)=GK(L)$. This contradiction
completes the proof of Theorem 1.

##  3\. Groups almost recognizable by prime graph

Given a positive integer $k$, a finite group $G$ is said to be
$k$-recognizable by prime graph if there are exactly $k$ pairwise
nonisomorphic finite groups $H$ with $GK(H)=GK(G)$ and almost recognizable by
prime graph if it is $k$-recognizable for some $k$.

By [1, Theorem 1.3], if $G$ is almost recognizable by prime graph, then $G$ is
almost simple and each group $H$ with $GK(H)=GK(G)$ is almost simple. So if
$G$ is a $k$-recognizable group, then $k$ is at most the number of almost
simple groups $H$ such that $\pi(H)=\pi(G)$. By [1, Proposition 4.2], this
number is at most $O(|\pi(G)|^{7})$. A direct corollary of this discussion is
the following theorem.

######  Theorem A 0[1, Theorem 1.4].

There exists a function $F(x)=O(x^{7})$ such that for each labeled graph
$\Gamma$, the following conditions are equivalent:

  1. (i)

there exist infinitely many groups $H$ such that $GK(H)=\Gamma$;

  2. (ii)

there exist more then $F(|V(\Gamma)|)$ groups $H$ such that $GK(H)=\Gamma$,
where $V(\Gamma)$ is the set of the vertices of $\Gamma$.

It is clear that estimating $k$ we do not need to calculate all almost simple
groups $H$ such that $\pi(H)=\pi(G)$. It is sufficient to calculate those $H$
whose prime graph satisfies some necessary conditions for $H$ to be almost
recognizable by prime graph. One of these conditions is stated in [1, Theorem
1.3]: 2 is nonadjacent to at least one odd prime in $GK(H)$. But in fact this
condition can be strengthened: every $r\in\pi(H)$ is nonadjacent to at least
one prime $s\neq r$ in $GK(H)$. Indeed, otherwise
$GK(H)=GK(H\times\mathbb{Z}^{k}_{r})$ for all positive integers $k$. Applying
Theorem 2, we see that it sufficient to calculate $H$ such that $H/S$ is
cyclic, where $S$ is the socle of $H$.

###### Lemma 3.1.

There is a function $F(x)=O(x^{2})$ such that if $S$ is a finite simple group
of Lie type, then there are at most $F(|\pi(S)|)$ almost simple groups $H$
with socle $S$ such that $H/S$ is cyclic.

  * Proof.

Let $n$ be the Lie rank of $S$ and $q=p^{l}$ the order of the base field of
$S$. Denote the number of divisors of $l$ by $d(l)$. By [1, Lemma 2.7], we
have $n\leqslant 2|\pi(S)|+3$ and $d(l)\leqslant|\pi(S)|+1$.

Steinberg’s theorem [4, Theorem 2.5.12] states that
$\operatorname{Out}S=\operatorname{Outdiag}S\rtimes\Phi_{S}\Gamma_{S}$, where
$|\operatorname{Outdiag}S|\leqslant n+1$ and $\Phi_{S}\Gamma_{S}$ is either a
subgroup in $\mathbb{Z}_{l}\times Sym_{3}$ or a cyclic group of order $2l$ or
$3l$. In any case the number of cyclic subgroups of $\Phi_{S}\Gamma_{S}$ is at
most $6d(l)$. Thus the number of cyclic subgroups of $\operatorname{Out}S$ is
at most $6(n+1)d(l)$, which is $O(|\pi(S)|^{2})$ by the preceding paragraph. ∎

Now we are ready to prove Theorem 3 (in fact we follow the lines of the proof
of [1, Theorem 1.4] but Theorem 2 allows us to use the bound of Lemma 3.1
instead of that of [1, Proposition 4.1]). It is sufficient to show that there
exists a function $F(x)=O(x^{5})$ such that for every finite group $G$, if $G$
is almost recognizable by prime graph, then there are at most $F(|\pi(G)|)$
pairwise nonisomorphic groups $H$ with $GK(H)=GK(G)$.

Assume that $G$ is $k$-recognizable by prime graph. By [1, Theorem 1.3], each
group $H$ with $GK(H)=GK(G)$ is almost simple. Furthermore, as we remarked,
every $r\in\pi(H)$ is nonadjacent to at least one prime $s\neq r$ in $GK(H)$.
By Theorem 2, it follows that $H$ is a cyclic extension of its socle. By [1,
Proposition 3.1], the number of nonabelian simple groups $S$ such that
$\pi(S)\subseteq\pi(G)$ is bounded by $F_{1}(|\pi(G)|)$ with
$F_{1}(x)=O(x^{3})$. Applying Lemma 3.1, we see that the number of almost
simple groups $H$ with socle $S$ such that $H/S$ is cyclic is at most
$F_{2}(|\pi(S)|)$, where $F_{2}(x)=O(x^{3})$. Thus $k\leqslant
F_{1}(|\pi(G)|)F_{2}(|\pi(G)|)=O(|\pi(G)|^{5})$, and this completes the proof
of Theorem 3.

## References

  * [1] P. J. Cameron and N. V. Maslova, Criterion of unrecognizability of a finite group by its Gruenberg-Kegel graph, 2021, arXiv:2012.01482 [math.GR].
  * [2] R. W. Carter, Finite groups of Lie type. Conjugacy classes and complex characters, John Wiley & Sons, New York, 1985.
  * [3] D. Gorenstein and R. Lyons, Local structure of finite groups of characteristic $2$ type, Memoirs Amer. Math. Soc. 276, 1983.
  * [4] D. Gorenstein, R. Lyons, and R. Solomon, The classification of the finite simple groups. Number 3, Amer. Math. Soc. Surveys and Monographs 40.3, 1998.
  * [5] I. B. Gorshkov, Recognizability of alternating groups by spectrum, _Algebra Logic_ 52 (2013), no. 1, 41–45.
  * [6] M. A. Grechkoseeva, On element orders in covers of finite simple groups of Lie type, _J. Algebra Appl._ 14 (2015), 1550056 [16 pages].
  * [7] M. A. Grechkoseeva, On spectra of almost simple groups with symplectic or orthogonal socle, _Siberian Math. J._ 57 (2016), no. 4, 582–588.
  * [8] M. A. Grechkoseeva, On spectra of almost simple extensions of even-dimensional orthogonal groups, _Siberian Math. J._ 59 (2018), no. 4, 623–640.
  * [9] M. A. Grechkoseeva and A. V. Vasil’ev, On the structure of finite groups isospectral to finite simple groups, _J. Group Theory_ 18 (2015), no. 5, 741–759.
  * [10] B. Huppert, Endliche Gruppen. I, Springer-Verlag, Berlin, 1967.
  * [11] V. D. Mazurov and W. J. Shi, A note to the characterization of sporadic simple groups, _Algebra Colloq._ 5 (1998), no. 3, 285–288.
  * [12] A. M. Staroletov, Groups isospectral to the degree 10 alternating group, _Siberian Math. J._ 51 (2010), no. 3, 507–514.
  * [13] A. Staroletov, On almost recognizability by spectrum of simple classical groups, _Int. J. Group Theory_ 6 (2017), no. 4, 7–33.
  * [14] R. Steinberg, Endomorphisms of linear algebraic groups, Memoirs Amer. Math. Soc. 80, 1968.
  * [15] A. V. Vasil’ev, On connection between the structure of a finite group and the properties of its prime graph, _Siberian Math. J._ 46 (2005), no. 3, 396–404.
  * [16] A. V. Vasil’ev and E. P. Vdovin, An adjacency criterion for the prime graph of a finite simple group, _Algebra Logic_ 44 (2005), no. 6, 381–406.
  * [17] A. V. Vasil’ev and E. P. Vdovin, Cocliques of maximal size in the prime graph of a finite simple group, _Algebra Logic_ 50 (2011), no. 4, 291–322.
  * [18] N. Yang, M. A. Grechkoseeva, and A. V. Vasil’ev, On the nilpotency of the solvable radical of a finite group isospectral to a simple group, _J. Group Theory_ 23 (2020), no. 3, 447–470.