# Lifts of Brauer characters in characteristic two

Ping Jin  School of Mathematical Sciences, Shanxi University, Taiyuan, 030006,
China<EMAIL_ADDRESS>and  Lei Wang  School of Mathematical Sciences,
Shanxi University, Taiyuan, 030006, China<EMAIL_ADDRESS>
###### Abstract.

A conjecture raised by Cossey in 2007 asserts that if $G$ is a finite
$p$-solvable group and $\varphi$ is an irreducible $p$-Brauer character of $G$
with vertex $Q$, then the number of lifts of $\varphi$ is at most
$|Q:Q^{\prime}|$. This conjecture is now known to be true in several
situations for $p$ odd, but there has been little progress for $p$ even. The
main obstacle appeared in characteristic two is that all the vertex pairs of a
lift are neither linear nor conjugate. In this paper we show that if $\chi$ is
a lift of an irreducible $2$-Brauer character in a solvable group, then $\chi$
has a linear Navarro vertex if and only if all the vertex pairs of $\chi$ are
linear, and in that case all of the twisted vertices of $\chi$ are conjugate.
Our result can also be used to study other lifting problems of Brauer
characters in characteristic two. As an application, we prove a weaker form of
Cossey’s conjecture for $p=2$ “one vertex at a time”.

###### Key words and phrases:

Brauer character; lift; Navarro vertex; vertex pair; twisted vertex

###### 2010 Mathematics Subject Classification:

Primary 20C20; Secondary 20C15

*Corresponding author

##  1\. Introduction

Fix a prime number $p$, and let $G$ be a finite $p$-solvable group. The Fong-
Swan theorem states that for each irreducible $p$-Brauer character
$\varphi\in\operatorname{IBr}_{p}(G)$, there exists some irreducible complex
character $\chi\in\operatorname{Irr}(G)$ such that $\chi^{0}=\varphi$, where
$\chi^{0}$ denotes the restriction of $\chi$ to the $p$-regular elements of
$G$. Such a character $\chi$ is called a lift of $\varphi$. In [2], Cossey
proposed the following conjecture, which also appears as Problem 3.6 of [19].

######  Conjecture 1.1 (Cossey).

Let $G$ be a $p$-solvable group, and let
$\varphi\in\operatorname{IBr}_{p}(G)$. Then

$|L_{\varphi}|\leq|Q:Q^{\prime}|,$

where $L_{\varphi}$ is the set of all lifts of $\varphi$ and $Q$ is a vertex
for $\varphi$ (in the sense of Green).

This global/local conjecture seems difficult to prove, although some progress
has been made for $p$ odd. In 2007, Cossey [2] verified his conjecture for
(solvable) groups of odd order, and in 2011, Cossey, Lewis and Navarro [9]
proved the conjecture under the conditions that either $Q$ is abelian or
$Q\vartriangleleft G$ and $p\neq 2$. Also, Cossey and Lewis [6] computed the
exact number of lifts of $\varphi$ in the case where $\varphi$ lies in a block
with a cyclic defect group. For further background material of this
conjecture, the reader is referred to the survey paper of Cossey [5].

In [3], Cossey assigned to each $\chi\in\operatorname{Irr}(G)$ a pair
$(Q,\delta)$ consisting of a $p$-subgroup $Q$ of $G$ and a character
$\delta\in\operatorname{Irr}(Q)$, which is called a vertex pair for $\chi$
(for precise definition, see Section 2 below or Definition 4.5 of [5]).
Furthermore, the pair $(Q,\delta)$ is said to be linear if
$\delta\in\operatorname{Lin}(Q)$ is a linear character. Of particular note is
the fact that if $\chi$ is a lift of $\varphi\in\operatorname{IBr}_{p}(G)$ and
if $(Q,\delta)$ is a linear vertex pair for $\chi$, then $Q$ is necessarily a
vertex for $\varphi$ (see Theorem 4.6(d) of [5]). The following result, which
is a main theorem of [11], plays a key role in the study of Cossey’s
conjecture as well as many other lifting problems about Brauer characters;
see, for example, [3, 4, 5, 8, 9, 10, 11, 16, 20, 21].

######  Lemma 1.2 (Cossey-Lewis).

Let $G$ be a $p$-solvable group with $p>2$, and suppose that
$\chi\in\operatorname{Irr}(G)$ is a lift of some
$\varphi\in\operatorname{IBr}_{p}(G)$. Then all of the vertex pairs for $\chi$
are linear and conjugate in $G$.

Following the notation of [11], we write $L_{\varphi}(Q,\delta)$ for the set
of those lifts of $\varphi\in\operatorname{IBr}_{p}(G)$ with vertex pair
$(Q,\delta)$ and let $N_{G}(Q,\delta)$ denote the stabilizer of $\delta$ in
$N_{G}(Q)$, where $Q$ is a $p$-subgroup of a $p$-solvable group $G$ and
$\delta\in\operatorname{Irr}(Q)$. In the situation of Lemma 1.2, let $Q$ be a
vertex for $\varphi$, so that each lift of $\varphi$ has vertex pair
$(Q,\delta)$ for some $\delta\in\operatorname{Lin}(Q)$, and let
$\\{\delta_{1},\ldots,\delta_{n}\\}$ be a set of representatives of the
$N_{G}(Q)$-orbits in $\operatorname{Lin}(Q)$ (under the natural action of
$N_{G}(Q)$ on $\operatorname{Lin}(Q)$ induced by the conjugation action of
$N_{G}(Q)$ on $Q$). Then
$L_{\varphi}=\bigcup_{i=1}^{n}L_{\varphi}(Q,\delta_{i})$ is clearly a disjoint
union and

$\sum_{i=1}^{n}|N_{G}(Q):N_{G}(Q,\delta_{i})|=|\operatorname{Lin}(Q)|=|Q:Q^{\prime}|.$

This suggests that perhaps Cossey’s conjecture can be proved “one vertex pair
at a time”, and indeed, Cossey and Lewis established the following strong form
of the conjecture under certain conditions (see the proof of Theorem 1.2 of
[2] for $|G|$ odd, and Theorem 3 of [7] for $Q$ abelian).

######  Theorem 1.3 (Cossey-Lewis).

Let $\varphi\in\operatorname{IBr}_{p}(G)$, where $G$ is $p$-solvable with
$p>2$. If either $|G|$ is odd or $Q$ is abelian, then
$|L_{\varphi}(Q,\delta)|\leq|N_{G}(Q):N_{G}(Q,\delta)|$ for all
$\delta\in\operatorname{Lin}(Q)$.

The purpose of the present paper is to investigate Cossey’s conjecture in the
case where $p=2$, for which there has been little progress. Unfortunately, the
above argument does not work in this case because Lemma 1.2 can fail, and the
examples in [1] and [15] show that for a lift $\chi$ of some
$\varphi\in\operatorname{IBr}_{2}(G)$ in a solvable group $G$, two
possibilities do happen: either $\chi$ has no linear vertex pair or all of the
linear vertex pairs for $\chi$ are not conjugate. This is a major obstacle to
our research on lifts of $2$-Brauer characters. In order to extend Lemma 1.2
to the case $p=2$, we introduced the notion of twisted vertices, and
established the uniqueness of _linear_ twisted vertices under some conditions;
see [20] for more details. We can now use Navarro vertices to deal with _all_
of the twisted vertices for a lift of a given $2$-Brauer character in solvable
groups, and obtain an analogue of Lemma 1.2 for $p$ even. For the definition
of Navarro vertices, see [18] or the next section.

The following is the first main result in this paper, which strengthens
Theorem A and Theorem B of [20]. Also, it is the starting point for our study
of lifting Brauer characters for $p$ even, just like Lemma 1.2 for $p$ odd.

######  Theorem A.

Let $G$ be a solvable group, and let $\chi\in\operatorname{Irr}(G)$ be a lift
of some $\varphi\in\operatorname{IBr}_{2}(G)$. Then the following hold.

(a) $\chi$ has a linear Navarro vertex if and only if every vertex pair for
$\chi$ is linear. In that case, all of the twisted vertices for $\chi$ are
linear and conjugate in $G$.

(b) $\chi$ has a linear Navarro vertex if and only if every primitive
character inducing $\chi$ has odd degree.

(c) If $\chi$ is an $\mathcal{N}$-lift for some $2$-chain $\mathcal{N}$ of
$G$, then $\chi$ has a linear Navarro vertex.

Here, for a prime $p$ (not necessarily $2$), a $p$-chain $\mathcal{N}$ of $G$
is a chain of normal subgroups of $G$:

$\mathcal{N}=\\{1=N_{0}\leq N_{1}\leq\cdots\leq N_{k-1}\leq N_{k}=G\\}$

such that each $N_{i}/N_{i-1}$ is either a $p$-group or a $p^{\prime}$-group,
and $\chi\in\operatorname{Irr}(G)$ is an $\mathcal{N}$-lift if for all
$N\in\mathcal{N}$, every irreducible constituent of $\chi_{N}$ is a lift of
some irreducible $p$-Brauer character of $N$. (See [8] for more details.)

As an application of Theorem A, we consider Cossey’s conjecture for $p=2$.
Given $\varphi\in\operatorname{IBr}_{2}(G)$ with $G$ solvable, we denote by
$\tilde{L}_{\varphi}$ the set of lifts of $\varphi$ that have a linear Navarro
vertex, which cannot be empty by Theorem A(a) of [18], and we write
$\tilde{L}_{\varphi}(Q,\delta)$ for the subset of those characters in
$\tilde{L}_{\varphi}$ with twisted vertex $(Q,\delta)$. By Theorem A,
$\tilde{L}_{\varphi}=\bigcup_{i=1}^{n}\tilde{L}_{\varphi}(Q,\delta_{i})$ is a
disjoint union, where $\\{\delta_{1},\ldots,\delta_{n}\\}$ is a set of
representatives of the $N_{G}(Q)$-orbits in $\operatorname{Lin}(Q)$ as before.
Also, we can prove a weaker form of Cossey’s conjecture for $p$ even “one
vertex pair at a time”; compare the following result with Theorem 1.3.

######  Theorem B.

Let $G$ be a solvable group, and let $\varphi\in\operatorname{IBr}_{2}(G)$
with vertex $Q$. Then

$|\tilde{L}_{\varphi}(Q,\delta)|\leq|N_{G}(Q):N_{G}(Q,\delta)|$

for all $\delta\in\operatorname{Lin}(Q)$. In particular,
$|\tilde{L}_{\varphi}|\leq|Q:Q^{\prime}|$.

To prove Cossey’s conjecture in the situation of Theorem B, it is natural to
ask when it is true that $\tilde{L}_{\varphi}$ and $L_{\varphi}$ coincide
(that is, every lift of $\varphi$ has a linear Navarro vertex). By Theorem A,
$\tilde{L}_{\varphi}=L_{\varphi}$ if and only if for any lift $\chi$ of
$\varphi$, each primitive character inducing $\chi$ has odd degree. As an easy
consequence of Theorems A and B, we present the following purely group-
theoretic condition.

######  Corollary C.

Let $G$ be a solvable group, and let $\varphi\in\operatorname{IBr}_{2}(G)$
with vertex $Q$. Assume that there exist normal subgroups $N\leq M$ of $G$
satisfying

(a) $N$ has odd order,

(b) all Sylow subgroups of $M/N$ are abelian,

(c) $G/M$ is supersolvable.
Then $\tilde{L}_{\varphi}=L_{\varphi}$, and hence
$|L_{\varphi}|\leq|Q:Q^{\prime}|$.

We end this introduction with some remarks. As usual, we will work with
Isaacs’ $\pi$-partial characters in $\pi$-separable groups rather that Brauer
characters in $p$-solvable groups. For the reader’s convenience, we will
briefly review the definitions and basic properties of $\pi$-partial
characters and the associated vertices in the next section (for more details
see Isaacs’ recent new book [14]). Here we emphasize that the “classical” case
of Brauer characters is exactly the situation where $\pi$ is the complement
$p^{\prime}$ of $\\{p\\}$ in the set of all prime numbers. Actually, our proof
of Theorem B is inspired by the arguments used by Cossey and Lewis in the
preprint [7] to handle the case $2\in\pi$. Nevertheless, in our case where
$2\notin\pi$ we need to use the $\pi$-induction of characters defined by
Isaacs [12] to replace ordinary induction, and modify again the definition of
Cossey’s vertex pairs for any $\chi\in\operatorname{Irr}(G)$ to obtain a new
one which we call a $*$-vertex for $\chi$ (see Definition 4.4). As expected,
all of the $*$-vertices for every member of $\tilde{L}_{\varphi}$ are still
conjugate (see Theorem 4.5), which is also complementary to Lemma 1.2 and is
crucial for our goal, and the proof is an immediate application of Theorem B
of [20].

Throughout this paper, all groups are finite, and most of the notation and
results can be found in [13, 17, 14] for ordinary characters, Brauer
characters and Isaacs’ $\pi$-partial characters.

##  2\. Preliminaries

In this section, we briefly review some basic notions and results from Isaacs’
$\pi$-theory needed for our proofs.

2.1 $\pi$-Partial characters

Following Isaacs [14], we fix a set $\pi$ of primes and let $G$ be a
$\pi$-separable group. We write $G^{0}$ for the set of $\pi$-elements of $G$,
and for any complex character $\chi$ of $G$, we use $\chi^{0}$ to denote the
restriction of $\chi$ to $G^{0}$. We call $\chi^{0}$ a $\pi$-partial character
of $G$. If a $\pi$-partial character $\varphi$ cannot be written as a sum of
two $\pi$-partial characters, we say that $\varphi$ is irreducible or that
$\varphi$ is an ${\rm I}_{\pi}$-character. The set of all ${\rm
I}_{\pi}$-characters of $G$ is denoted ${\rm I}_{\pi}(G)$. Also, if
$\chi\in\operatorname{Irr}(G)$ satisfying $\chi^{0}=\varphi$ for some
$\varphi\in{\rm I}_{\pi}(G)$, then $\chi$ is called a $\pi$-lift, or a lift
for short when there is no risk of confusion. We write

$L_{\varphi}=\\{\chi\in\operatorname{Irr}(G)\,|\,\chi^{0}=\varphi\\}$

for the set of all lifts for $\varphi$.

By the Fong-Swan theorem, it follows that if $\pi=p^{\prime}$, the set of
primes different from $p$, then the $\pi$-partial characters of $G$ are
exactly the $p$-Brauer characters in $p$-solvable groups. In this case, we
have ${\rm I}_{\pi}(G)=\operatorname{IBr}_{p}(G)$.

Furthermore, Isaacs constructed a subset ${\rm B}_{\pi}(G)$ of
$\operatorname{Irr}(G)$, which is a canonical lift of ${\rm I}_{\pi}(G)$, so
the map $\chi\mapsto\chi^{0}$ defines a bijection from ${\rm B}_{\pi}(G)$ onto
${\rm I}_{\pi}(G)$ (see Theorem 5.1 of [14]).

We now consider the vertices for ${\rm I}_{\pi}$-characters. Given
$\varphi\in{\rm I}_{\pi}(G)$, a vertex for $\varphi$ is defined to be any Hall
$\pi^{\prime}$-subgroup of a subgroup $U$ of $G$ such that there exists
$\theta\in{\rm I}_{\pi}(U)$, where $\theta^{G}=\varphi$ and $\theta(1)$ is a
$\pi$-number. We use ${\rm I}_{\pi}(G|Q)$ to denote the set of ${\rm
I}_{\pi}$-characters of $G$ having $Q$ as a vertex.

The following result is fundamental.

######  Lemma 2.1 (Theorem 5.17 of [14]).

Let $G$ be $\pi$-separable, where $\pi$ is a set of primes, and let
$\varphi\in{\rm I}_{\pi}(G)$. Then all vertices for $\varphi$ form a single
conjugacy class of $\pi^{\prime}$-subgroups of $G$.

2.2 $\pi$-Factored characters

Let $\chi\in\operatorname{Irr}(G)$, where $G$ is a $\pi$-separable group. We
say that $\chi$ is $\pi$-special if $\chi(1)$ is a $\pi$-number and the
determinantal order $o(\theta)$ is a $\pi$-number for every irreducible
constituent $\theta$ of the restriction $\chi_{S}$ for every subnormal
subgroup $S$ of $G$. The set of $\pi$-special characters of $G$ is denoted
${\rm X}_{\pi}(G)$.

######  Lemma 2.2 (Theorem 2.10 of [14]).

Let $G$ be $\pi$-separable, and let $H\leq G$ have $\pi^{\prime}$-index. Then
restriction $\chi\mapsto\chi_{H}$ defines an injection from ${\rm X}_{\pi}(G)$
into ${\rm X}_{\pi}(H)$.

######  Lemma 2.3 (Theorem 3.14 of [14]).

Let $G$ be $\pi$-separable. Then the map $\chi\mapsto\chi^{0}$ defines an
injection from ${\rm X}_{\pi}(G)$ into ${\rm I}_{\pi}(G)$.

######  Lemma 2.4 (Theorem 2.2 of [14]).

Let $G$ be $\pi$-separable, and suppose that
$\alpha,\beta\in\operatorname{Irr}(G)$ are $\pi$-special and
$\pi^{\prime}$-special, respectively. Then $\alpha\beta$ is irreducible. Also,
if $\alpha\beta=\alpha^{\prime}\beta^{\prime}$, where $\alpha^{\prime}$ is
$\pi$-special and $\beta^{\prime}$ is $\pi^{\prime}$-special, then
$\alpha=\alpha^{\prime}$ and $\beta=\beta^{\prime}$.

If $\chi\in\operatorname{Irr}(G)$ can be written as $\chi=\alpha\beta$, where
$\alpha$ is $\pi$-special and $\beta$ is $\pi^{\prime}$-special, then $\chi$
is said to be $\pi$-factored. Since $\alpha$ and $\beta$ are uniquely
determined by $\chi$, we often use $\chi_{\pi}$ and $\chi_{\pi^{\prime}}$ to
replace $\alpha$ and $\beta$, respectively.

By definition, it is easy to see that every normal constituent of a
$\pi$-special character is also $\pi$-special, and so we have the following.

######  Lemma 2.5.

Let $G$ be $\pi$-separable, and let $N\vartriangleleft G$. If
$\chi\in\operatorname{Irr}(G)$ is $\pi$-factored, then every irreducible
constituent $\theta$ of $\chi_{N}$ is also $\pi$-factored. Furthermore,
$\theta_{\pi}$ and $\theta_{\pi^{\prime}}$ lie under $\chi_{\pi}$ and
$\chi_{\pi^{\prime}}$, respectively.

Recall that if $\theta\in\operatorname{Irr}(H)$, where $H$ is a subgroup of
$G$, we write $\operatorname{Irr}(G|\theta)$ to denote the set of irreducible
constituents of $\theta^{G}$, that is, the set of irreducible characters of
$G$ lying over $\theta$.

######  Lemma 2.6.

Let $N\vartriangleleft G$, where $G$ is $\pi$-separable, and suppose that
$G/N$ is a $\pi^{\prime}$-group. Let $\alpha,\beta\in\operatorname{Irr}(N)$ be
$\pi$-special and $\pi^{\prime}$-special, respectively. Then $\alpha$ is
invariant in $G$ if and only if every member of
$\operatorname{Irr}(G|\alpha\beta)$ is $\pi$-factored, and this happens
precisely when one member of $\operatorname{Irr}(G|\alpha\beta)$ is
$\pi$-factored.

###### Proof.

If $\alpha$ is invariant in $G$, then by Lemma 4.2 of [14] every member of
$\operatorname{Irr}(G|\alpha\beta)$ is $\pi$-factored. Assume some character
$\chi\in\operatorname{Irr}(G|\alpha\beta)$ is $\pi$-factored. By Lemma 2.5, we
see that $\chi_{\pi}$ lies over $\alpha$, and since $G/N$ is a
$\pi^{\prime}$-group and $\chi_{\pi}$ has $\pi$-degree, we have
$(\chi_{\pi})_{N}=\alpha$ by Clifford’s theorem, and thus $\alpha$ is
invariant in $G$. The result now follows. ∎

2.3 Vertex pairs

We continue to assume that $G$ is $\pi$-separable and
$\chi\in\operatorname{Irr}(G)$. Let $Q$ be a $\pi^{\prime}$-subgroup of $G$
and $\delta\in\operatorname{Irr}(Q)$. Following Cossey [5], the pair
$(Q,\delta)$ is called a vertex pair for $\chi$ if there exists a subgroup $U$
of $G$ such that $Q$ is a Hall $\pi^{\prime}$-subgroup of $U$ and
$\delta=(\psi_{\pi^{\prime}})_{Q}$, where $\psi\in\operatorname{Irr}(U)$ is
$\pi$-factored with $\psi^{G}=\chi$. (Recall that we use $\psi_{\pi^{\prime}}$
to denote the $\pi^{\prime}$-special factor of $\psi$.) We say that
$(Q,\delta)$ is a linear vertex if $\delta\in\operatorname{Lin}(Q)$ is a
linear character of $Q$. Clearly, all of the vertex pairs for $\chi$ need not
be conjugate in $G$.

The importance of linear vertex pairs is illustrated by the following result.

######  Lemma 2.7 (Theorem 4.6(d) of [5]).

Let $G$ be a $\pi$-separable group, and let $\chi\in\operatorname{Irr}(G)$ be
a lift of some $\varphi\in{\rm I}_{\pi}(G)$. If $(Q,\delta)$ is a linear
vertex pair for $\chi$, then $Q$ is a vertex for $\varphi$.

2.4 Navarro vertices

The definition of Navarro vertices relies on the following fundamental result,
whose proof can be seen Theorem 2.2 and Corollary 2.4 of [18]. Recall that if
$\theta\in\operatorname{Irr}(N)$, where $N\vartriangleleft G$ and $G$ is a
group, we often use $G_{\theta}$ to denote the inertia group of $\theta$ in
$G$ and write $\chi_{\theta}$ for the Clifford correspondent of any
$\chi\in\operatorname{Irr}(G|\theta)$ with respect to $\theta$.

######  Lemma 2.8.

Let $G$ be a $\pi$-separable group, and let $\chi\in\operatorname{Irr}(G)$.
Then there is a unique normal subgroup $N$ of $G$ maximal with the property
that every irreducible constituent $\theta$ of $\chi_{N}$ is $\pi$-factored.
Furthermore, if $\theta$ is invariant in $G$, that is, if $G_{\theta}=G$, then
$N=G$ and $\theta=\chi$.

Now, the normal nucleus $(W,\gamma)$ for $\chi\in\operatorname{Irr}(G)$ can be
defined inductively. If $\chi$ is $\pi$-factored, then we let
$(W,\gamma)=(G,\chi)$. Otherwise, let $N$ and $\theta$ be as in Lemma 2.8.
Then $G_{\theta}<G$, and we define $(W,\gamma)$ to be the normal nucleus for
$\chi_{\theta}$. It is easy to see that $\gamma$ is $\pi$-factored with
$\gamma^{G}=\chi$, and that the normal nucleus for $\chi$ is uniquely
determined up to conjugacy.

Furthermore, let $Q$ be a Hall $\pi^{\prime}$-subgroup of $W$ and let
$\delta=(\gamma_{\pi^{\prime}})_{Q}$. Then the pair $(Q,\delta)$ is clearly a
vertex pair for $\chi$, which is called a Navarro vertex for $\chi$. By the
construction of normal nuclei, it is easy to see that all of the Navarro
vertices for $\chi$ are conjugate in $G$.

2.5 $\pi$-Induction

Assume that $G$ is a $\pi$-separable group with $2\notin\pi$. For each
subgroup $H$ of $G$, Isaacs defined the $\pi$-standard sign character
$\delta_{(G,H)}$, which is a linear character of $H$ that has values $\pm 1$.
For definition and properties of this sign character, the reader is referred
to [12].

######  Lemma 2.9 (Theorem 2.5 of [12]).

Let $G$ be a $\pi$-separable group, where $2\notin\pi$.

(1) If $H\leq K\leq G$, then
$\delta_{(G,H)}=(\delta_{(G,K)})_{H}\delta_{(K,H)}$.

(2) If $N\leq H\leq G$ and $N\vartriangleleft G$, then $N$ is contained in the
kernel of $\delta_{(G,H)}$.

Using the $\pi$-standard sign character, Isaacs [12] introduced the notion of
$\pi$-induction.

######  Definition 2.10.

Let $G$ be $\pi$-separable with $2\notin\pi$, and suppose that $\theta$ is a
character of some subgroup $H$ of $G$. Write $\theta^{\pi
G}=(\delta_{(G,H)}\theta)^{G}$. We say that $\theta^{\pi G}$ is the
$\pi$-induction of $\theta$ to $G$.

######  Lemma 2.11 (Lemma 7.4 of [12]).

Let $G$ be $\pi$-separable with $2\notin\pi$, and let
$\chi\in\operatorname{Irr}(G)$. Suppose that $H\leq K\leq G$ and $\theta$ is a
character of $H$. Then $(\theta^{\pi K})^{\pi G}=\theta^{\pi G}$.

The next result is the Clifford correspondence for $\pi$-induction.

######  Lemma 2.12 (Lemma 7.5 of [12]).

Let $G$ be $\pi$-separable with $2\notin\pi$, and let $N\vartriangleleft G$
and $\theta\in\operatorname{Irr}(N)$. Then the map $\psi\mapsto\psi^{\pi G}$
defines a bijection
$\operatorname{Irr}(G_{\theta}|\theta)\to\operatorname{Irr}(G|\theta)$.

The following is fundamental when studying induction of $\pi$-special
characters.

######  Lemma 2.13 (Theorem 2.29 of [14]).

Let $\psi\in\operatorname{Irr}(U)$, where $U\leq G$ and $G$ is
$\pi$-separable, and assume that every irreducible constituent of $\psi^{G}$
is $\pi$-special. Then $|G:U|$ is a $\pi$-number and $\psi(1)$ is a
$\pi$-number. Also, $\psi$ is $\pi$-special if $2\in\pi$, and
$\delta_{(G,U)}\psi$ is $\pi$-special if $2\notin\pi$.

##  3\. Proof of Theorem A

We begin with a lemma, which is of fundamental importance for the proof of our
Theorem A.

######  Lemma 3.1.

Let $\chi\in\operatorname{Irr}(G)$ be a lift of $\varphi\in{\rm I}_{\pi}(G)$,
where $G$ is $\pi$-separable with $2\notin\pi$. Then the following are
equivalent.

(a) All of the vertex pairs for $\chi$ are linear.

(b) Every quasi-primitive character $\psi$ inducing $\chi$ has odd degree,
where both $\psi_{\pi}$ and $\psi_{\pi^{\prime}}$ are primitive.

(c) Every $\pi$-factored character $\psi\in\operatorname{Irr}(U)$ inducing
$\chi$ has odd degree, where $U$ is a subgroup of $G$ containing
$O_{\pi}(G)O_{\pi^{\prime}}(G)$ and $\psi_{\pi^{\prime}}$ is primitive.

###### Proof.

Note that by definition, (a) is equivalent to saying that each $\pi$-factored
character that induces $\chi$ has $\pi$-degree. To complete the proof, we fix
a subgroup $U$ of $G$, and let $\psi\in\operatorname{Irr}(U)$ be
$\pi$-factored with $\psi^{G}=\chi$. For notational simplicity, we write
$\alpha=\psi_{\pi}$ and $\beta=\psi_{\pi^{\prime}}$, so that
$\psi=\alpha\beta$.

We claim that $\psi(1)$ is a $\pi$-number if and only if it is odd. To see
this, note that $2\notin\pi$, so $\psi(1)$ is odd whenever it is a
$\pi$-number. Conversely, if $\psi(1)$ is odd, then $\beta(1)$ is also odd,
and since

$(\alpha^{0}\beta^{0})^{G}=(\psi^{0})^{G}=(\psi^{G})^{0}=\chi^{0}=\varphi,$

it follows that $\beta^{0}\in{\rm I}_{\pi}(U)$. Now Corollary 2.14 of [14]
implies that $\beta^{0}$ is rational valued, and Lemma 5.4 of [14] tells us
that $\beta^{0}$ must be principal. Thus $\beta$ is linear, and
$\psi(1)=\alpha(1)$ is a $\pi$-number, as claimed. In particular, this proves
that (a) implies both (b) and (c).

Now assume (b). To establish (a), it suffices to show that $\beta$ is linear.
If $\alpha=\sigma^{U}$, where $\sigma\in\operatorname{Irr}(X)$ is primitive
and $X\leq U$, then
$\chi=(\alpha\beta)^{G}=((\sigma\beta_{X})^{U})^{G}=(\sigma\beta_{X})^{G}$.
Note that $|U:X|$ divides $\alpha(1)$, which is a $\pi$-number, so $\beta_{X}$
is $\pi^{\prime}$-special. Furthermore, by Lemma 2.13, we see that
$\delta_{(U,X)}\sigma$ is $\pi$-special, so
$\sigma\beta_{X}=(\delta_{(U,X)}\sigma)(\delta_{(U,X)}\beta_{X})$ is
$\pi$-factored. To prove that $\beta$ is linear, we can assume, therefore,
that $\alpha$ is primitive with $\sigma\beta_{X}$ in place of $\psi$ and $X$
in place of $U$. Similarly, if $\beta=\rho^{U}$, where
$\rho\in\operatorname{Irr}(Y)$ is primitive and $Y\leq U$. Then $\alpha_{Y}$
is $\pi$-special as $|U:Y|$ is a $\pi^{\prime}$-number, and $\rho$ is
$\pi^{\prime}$-special by Lemma 2.13 again. Now
$\chi=(\alpha\rho^{U})^{G}=(\alpha_{Y}\rho)^{G}$ and $\alpha_{Y}\rho$ is
$\pi$-factored. If we can prove that $\rho$ is linear, then $\rho^{0}$ must be
principal, and since $(\rho^{0})^{U}=(\rho^{U})^{0}=\beta^{0}\in{\rm
I}_{\pi}(U)$ (see the previous paragraph), it follows that $U=Y$, and thus
$\beta=\rho$ is linear. We may assume, therefore, that $\beta$ is primitive
with $\alpha_{Y}\rho$ in place of $\psi$ and $Y$ in place of $U$. Now we
repeat this progress until both $\alpha$ and $\beta$ are primitive. It is
clear that primitive characters in any group are always quasi-primitive, and
that a $\pi$-factored character in a $\pi$-separable group is quasi-primitive
if and only if its $\pi$-special factor and $\pi^{\prime}$-special factor are
all quasi-primitive (by basic properties of $\pi$-special characters). Thus
$\psi=\alpha\beta$ is quasi-primitive, and then (a) follows by (b).

Finally, assume (c). Write $N=O_{\pi}(G)O_{\pi^{\prime}}(G)$. Then each
irreducible character of $N$ is clearly $\pi$-factored. We claim that $|NU:U|$
is a $\pi$-number. To see this, let $\hat{\varphi}\in{\rm B}_{\pi}(G)$ be a
lift of $\varphi$, so that every irreducible constituent $\theta$ of
$\hat{\varphi}_{N}$ is also a ${\rm B}_{\pi}$-character. Note that
$\theta\in\operatorname{Irr}(N)$ is $\pi$-factored, so $\theta$ must be
$\pi$-special (see Theorem 4.12 of [14]), and thus $\theta^{0}\in{\rm
I}_{\pi}(N)$ has $\pi$-degree lying under $\varphi$. Moreover, since
$(\psi^{0})^{G}=(\psi^{G})^{0}=\chi^{0}=\varphi$, it follows by Lemma 5.21 of
[14] that $|NU:U|$ is a $\pi$-number, as claimed. Writing $\xi=\psi^{NU}$, we
see by Lemma 3.1 of [20] that $\xi$ is $\pi$-factored with
$(\xi_{\pi^{\prime}})_{U}=\delta_{(NU,U)}\beta$ . To establish (a), we may
assume further that $\psi$ is quasi-primitive and $\beta$ is primitive by the
equivalence of (a) with (b) just proved. Then $\xi_{\pi^{\prime}}$ is also
primitive with degree $\beta(1)$, so (a) follows by (c) with $\xi$ in place of
$\psi$ and $NU$ in place of $U$. ∎

Following the terminology of Cossey and Lewis [8], a $\pi$-chain $\mathcal{N}$
of $G$ is a chain of normal subgroups of $G$:

$\mathcal{N}=\\{1=N_{0}\leq N_{1}\leq\cdots\leq N_{k-1}\leq N_{k}=G\\}$

such that $N_{i}/N_{i-1}$ is either a $\pi$-group or a $\pi^{\prime}$-group
for $i=1,\dots,k$, and $\chi\in\operatorname{Irr}(G)$ is an $\mathcal{N}$-lift
if every irreducible constituent of $\chi_{N}$ is a lift for all
$N\in\mathcal{N}$.

######  Theorem 3.2.

Let $G$ be $\pi$-separable with $2\notin\pi$, and let
$\chi\in\operatorname{Irr}(G)$ be a lift of $\varphi\in{\rm I}_{\pi}(G)$.
Assume one of the following conditions.

(a) $\chi$ has a linear Navarro vertex.

(b) $\chi$ is an $\mathcal{N}$-lift for some $\pi$-chain $\mathcal{N}$ of $G$.
Then all of the vertex pairs for $\chi$ are linear.

###### Proof.

By Lemma 3.1, it suffices to show that every $\pi$-factored character
$\psi\in\operatorname{Irr}(U)$ that induces $\chi$ has odd degree, where
$U\leq G$ and $\psi_{\pi^{\prime}}$ is primitive. We write $\alpha=\psi_{\pi}$
and $\beta=\psi_{\pi^{\prime}}$, so that $\psi=\alpha\beta$.

Suppose first that $\chi$ is $\pi$-factored. To show the theorem in this
situation, it suffices to establish that $\chi(1)$ is a $\pi$-number as
$2\notin\pi$. In case (b), this is true by Lemma 2.3(2) of [20], and in case
(a), since $(G,\chi)$ is itself a normal nucleus for $\chi$, it follows by the
definition of Navarro vertices that $\chi$ has $\pi$-degree.

Now suppose that $\chi$ is not $\pi$-factored. Reasoning as we did in the
proof of Theorem 3.4 of [20], there exists a normal subgroup $N$ of $G$ such
that every irreducible constituent $\theta$ of $\chi_{N}$ is $\pi$-factored
with $\pi$-degree and $G_{\theta}<G$. (Specifically, in case (a) we let $N$ be
the unique maximal normal subgroup of $G$ such that $\chi_{N}$ has
$\pi$-factored irreducible constituents, and in case (b) we choose
$N\in\mathcal{N}$ maximal with the property that all of the irreducible
constituents of $\chi_{N}$ are $\pi$-factored.) Furthermore, the Clifford
correspondent $\chi_{\theta}$ of $\chi$ over $\theta$ also satisfies the both
conditions on $\chi$ (by replacing $G$ with $G_{\theta}$). Observe that
$\theta^{0}$ is irreducible with $\pi$-degree, and that $\theta^{0}$ lies
under $\varphi$. Since $(\psi^{0})^{G}=\chi^{0}=\varphi$, we deduce by Lemma
5.21 of [14] that $|NU:U|$ is a $\pi$-number. Now Lemma 3.1 of [20] applies,
and writing $\xi=\psi^{NU}$, we know that $\xi$ is $\pi$-factored with
$(\xi_{\pi^{\prime}})_{U}=\delta_{(NU,U)}\beta$. In particular, $\beta$ is
linear if and only if $\xi_{\pi^{\prime}}$ is. It is easy to see that
$\xi_{\pi^{\prime}}$ is necessarily primitive as it is an extension of the
primitive character $\delta_{(NU,U)}\beta$ (by Mackey). Now replacing $U$ by
$NU$ and $\psi$ by $\xi$, we may assume further that $N\leq U$. Moreover, we
can replace $\theta$ by a conjugate and assume that $\theta$ lies under
$\psi$.

We consider the Clifford correspondents
$\psi_{\theta}\in\operatorname{Irr}(U_{\theta})$ and
$\chi_{\theta}\in\operatorname{Irr}(G_{\theta})$ of $\psi$ and $\chi$ over
$\theta$, respectively. Note that $N\vartriangleleft U$ and that both $\psi$
and $\theta$ are $\pi$-factored, so $\theta_{\pi}$ lies under $\alpha$ and
$\theta_{\pi^{\prime}}$ lies under $\beta$. Since $\beta$ is assumed to be
primitive, it follows that $\beta_{N}$ is a multiple of
$\theta_{\pi^{\prime}}$, and hence $\theta_{\pi^{\prime}}$ is invariant in
$U$. From this, we deduce that $U_{\theta}$ is exactly the inertia group of
$\theta_{\pi}$ in $U$. Let $\tilde{\alpha}$ be the Clifford correspondent of
$\alpha$ over $\theta_{\pi}$, so that $\tilde{\alpha}^{U}=\alpha$. By Lemma
2.13, we see that $|U:U_{\theta}|$ is a $\pi$-number and
$\delta_{(U,U_{\theta})}\tilde{\alpha}$ is $\pi$-special. Furthermore, we have
that $\tilde{\beta}\in\operatorname{Irr}(U_{\theta})$ is
$\pi^{\prime}$-special, where $\tilde{\beta}$ denotes the restriction of
$\beta$ to $U_{\theta}$. Now
$(\tilde{\alpha}\tilde{\beta})^{U}=\tilde{\alpha}^{U}\beta=\alpha\beta=\psi$,
so $\tilde{\alpha}\tilde{\beta}$ is irreducible, which clearly lies over
$\theta_{\pi}\theta_{\pi^{\prime}}=\theta$. It follows that
$\tilde{\alpha}\tilde{\beta}$ is the Clifford correspondent of $\psi$ over
$\theta$, that is, $\psi_{\theta}=\tilde{\alpha}\tilde{\beta}$. Also, we have
$\psi_{\theta}=(\delta_{(U,U_{\theta})}\tilde{\alpha})(\delta_{(U,U_{\theta})}\tilde{\beta})$,
and thus $\psi_{\theta}$ is $\pi$-factored. Note that
$(\psi_{\theta})^{G_{\theta}}=\chi_{\theta}$ and $G_{\theta}<G$. By induction
on $|G|$, we conclude that $\psi_{\theta}$ has $\pi$-degree, and thus
$\psi(1)=|U:U_{\theta}|\psi_{\theta}(1)$ is a $\pi$-number. The proof is now
complete. ∎

We can now prove Theorem A in the introduction, which is a special case of the
following more general result (by taking $\pi$ to be the set of all odd
primes). Recall that quasi-primitive characters of solvable groups are
primitive (see Theorem 11.33 of [13]).

######  Theorem 3.3.

Let $G$ be a $\pi$-separable group with $2\notin\pi$, and let
$\chi\in\operatorname{Irr}(G)$ be a lift of some $\varphi\in{\rm I}_{\pi}(G)$.
Then the following hold.

(a) $\chi$ has a linear Navarro vertex if and only if every vertex pair for
$\chi$ is linear. In that case, all of the twisted vertices for $\chi$ are
linear and conjugate in $G$.

(b) $\chi$ has a linear Navarro vertex if and only if every quasi-primitive
character inducing $\chi$ has odd degree.

(c) If $\chi$ is an $\mathcal{N}$-lift for some $\pi$-chain $\mathcal{N}$ of
$G$, then $\chi$ has a linear Navarro vertex.

###### Proof.

The result follows by Lemma 3.1 and Theorem 3.2, together with Theorem B of
[20]. ∎

##  4\. A new modification of vertex pairs

We first need to extend the definition of the set $\tilde{L}_{\varphi}$, which
appeared in the introduction, and for simplicity, we introduce a notion.

######  Definition 4.1.

Let $G$ be $\pi$-separable, and let $\chi\in\operatorname{Irr}(G)$. We say
that $\chi$ is a good lift if $\chi$ is a lift for some $\varphi\in{\rm
I}_{\pi}(G)$ with a linear Navarro vertex. The set of all good lifts for
$\varphi$ is denoted $\tilde{L}_{\varphi}$.

Of course, all of the lifts of a $\pi$-separable group are good whenever
$2\in\pi$ by Lemma 4.3 of [11], so this notion is useful only for
$2\notin\pi$.

The following is a fundamental result.

######  Lemma 4.2.

Let $\chi\in\operatorname{Irr}(G)$ be a good lift, where $G$ is
$\pi$-separable with $2\notin\pi$. If $\chi=\psi^{G}$ with
$\psi\in\operatorname{Irr}(U)$ and $U\leq G$, then $\psi$ is also a good lift.

###### Proof.

It is clear that each vertex pair of $\psi$ is also a vertex pair of $\chi$,
and thus the result follows by Theorem 3.3. ∎

######  Lemma 4.3.

Let $\chi\in\operatorname{Irr}(G)$ be a good lift, where $G$ is
$\pi$-separable with $2\notin\pi$, and let $N\vartriangleleft G$. If
$\theta\in\operatorname{Irr}(N)$ is a $\pi$-factored constituent of
$\chi_{N}$, then $\theta(1)$ is a $\pi$-number. In particular, $\theta$ is a
lift.

###### Proof.

By Lemma 2.8, there exists a normal nucleus $(W,\gamma)$ for $\chi$ such that
$N\leq W$ and $\theta$ lies under $\gamma$. Then
$\gamma\in\operatorname{Irr}(W)$ is $\pi$-factored with $\gamma^{G}=\chi$. Let
$Q$ be a Hall $\pi^{\prime}$-subgroup of $W$ and write
$\delta=(\gamma_{\pi^{\prime}})_{Q}$. By definition, we see that $(Q,\delta)$
is a vertex pair for $\chi$. Since $\chi$ is a good lift, we have
$\delta(1)=1$, and thus $\gamma(1)=\gamma_{\pi}(1)$, which is a $\pi$-number.
Note that $\theta(1)$ divides $\gamma(1)$, so $\theta(1)$ is a $\pi$-number.
In particular, $\theta_{\pi^{\prime}}$ is linear, which implies that
$\theta^{0}=(\theta_{\pi})^{0}\in{\rm I}_{\pi}(N)$ by Lemma 2.3. The proof is
complete. ∎

We now modify the notion of vertex pairs, as mentioned in the Introduction.

######  Definition 4.4.

Let $\chi\in\operatorname{Irr}(G)$, where $G$ is a $\pi$-separable group with
$2\notin\pi$, and suppose that $Q$ is a $\pi^{\prime}$-subgroup of $G$ and
$\delta\in\operatorname{Irr}(Q)$. We say that $(Q,\delta)$ is a $*$-vertex for
$\chi$ if there exist a subgroup $U\leq G$ and a $\pi$-factored character
$\psi\in\operatorname{Irr}(U)$ with $\chi=\psi^{\pi G}$, and such that $Q$ is
a Hall $\pi^{\prime}$-subgroup of $U$ and $\delta=(\psi_{\pi^{\prime}})_{Q}$.

Our motivation for this is the following result (compare with Lemma 1.2). For
the notion of a twisted vertex of a character $\chi\in\operatorname{Irr}(G)$,
we refer the reader to Definition 2.1 and the remark after Lemma 2.2 of [20].

######  Theorem 4.5.

Let $G$ be a $\pi$-separable group with $2\notin\pi$, $Q$ a
$\pi^{\prime}$-subgroup of $G$ and $\delta\in\operatorname{Lin}(Q)$. If
$\chi\in\operatorname{Irr}(G)$ is a good lift, then $\chi$ has twisted vertex
$(Q,\delta)$ if and only if $\chi$ has $*$-vertex $(Q,\delta_{(G,Q)}\delta)$.
In particular, all $*$-vertices for $\chi$ are linear and conjugate in $G$.

###### Proof.

Let $(Q,\delta)$ be any twisted vertex for $\chi$. Then $\delta$ is linear by
Theorem 3.3. By definition, there exist $U\leq G$ and
$\psi\in\operatorname{Irr}(U)$ with $\chi=\psi^{G}$, and such that $Q$ is a
Hall $\pi^{\prime}$-subgroup of $U$, $\psi$ is $\pi$-factored and
$\delta=\delta_{(U,Q)}(\psi_{\pi^{\prime}})_{Q}$. On the other hand, notice
that $\chi=\psi^{G}=(\delta_{(G,U)}\psi)^{\pi G}$ and that
$\delta_{(G,U)}\psi_{\pi^{\prime}}$ is $\pi^{\prime}$-special. It follows that
$(Q,\delta^{*})$ is a $*$-vertex for $\chi$, where
$\delta^{*}=(\delta_{(G,U)}\psi_{\pi^{\prime}})_{Q}$. By Lemma 2.9,
$\delta_{(U,Q)}=\delta_{(G,Q)}(\delta_{(G,U)})_{Q}$, so
$\delta^{*}=\delta_{(G,Q)}\delta$. Therefore,
$(Q,\delta)\mapsto(Q,\delta_{(G,Q)}\delta)$ is a well-defined map between the
set of twisted vertices for $\chi$ and the set of $*$-vertices for $\chi$.
Moreover, it is easy to see that this map is bijective.

Furthermore, since $\chi$ has a linear Navarro vertex, we conclude from
Theorem 3.3 again that all of the twisted vertices for $\chi$ are linear and
conjugate, and hence all of the $*$-vertices of $\chi$ are conjugate in $G$.
This completes the proof. ∎

##  5\. Proofs of Theorem B and Corollary C

We begin by introducing some more notation. Let $G$ be a $\pi$-separable group
with $2\notin\pi$. Suppose that $Q$ is a $\pi^{\prime}$-subgroup of $G$ and
$\varphi\in{\rm I}_{\pi}(G|Q)$, that is, $\varphi\in{\rm I}_{\pi}(G)$ has
vertex $Q$. By Lemma 2.7 and Theorem 4.5, every good lift $\chi$ for $\varphi$
has a $*$-vertex of the form $(Q,\delta)$ for some
$\delta\in\operatorname{Lin}(Q)$. For notational convenience, we will write
$L^{*}_{\varphi}(Q,\delta)$ to denote the set of those good lifts for
$\varphi$ that have $(Q,\delta)$ as a $*$-vertex, so that
$\tilde{L}_{\varphi}=\bigcup_{\delta}L^{*}_{\varphi}(Q,\delta)$, where
$\delta$ runs over a set of representatives of the $N_{G}(Q)$-orbits in
$\operatorname{Lin}(Q)$.

We need to investigate the behavior of characters in
$L^{*}_{\varphi}(Q,\delta)$ with respect to normal subgroups (compare with
Lemma 3.1 of [7]).

######  Lemma 5.1.

Let $\varphi\in{\rm I}_{\pi}(G)$, where $G$ is a $\pi$-separable group with
$2\notin\pi$, and let $Q$ be a $\pi^{\prime}$-subgroup of $G$ with
$\delta\in\operatorname{Lin}(Q)$. Assume that $\chi\in
L^{*}_{\varphi}(Q,\delta)$ and $N\vartriangleleft G$. If every irreducible
constituent of $\chi_{N}$ is $\pi$-factored, then the following hold.

(1) $Q\cap N$ is a Hall $\pi^{\prime}$-subgroup of $N$.

(2) There exists a unique $\pi^{\prime}$-special character $\beta$ of $N$ such
that $\beta_{Q\cap N}=\delta_{Q\cap N}$. In particular, $\beta$ is linear.

(3) There is a $\pi$-special character $\alpha\in\operatorname{Irr}(N)$ such
that $\alpha\beta$ is an irreducible constituent of $\chi_{N}$, where $\beta$
is as in (2). Furthermore $\alpha^{0}=(\alpha\beta)^{0}$ is an irreducible
constituent of $\varphi_{N}$.

(4) Every irreducible constituent of $\chi_{N}$ is a lift for some irreducible
$\pi$-partial character of $N$ with $\pi$-degree, and every irreducible
constituent of $\varphi_{N}$ can be lifted to an irreducible constituent of
$\chi_{N}$.

###### Proof.

By Theorem 4.5, all $*$-vertices for $\chi$ form a single $G$-conjugacy class,
and so there exists a normal nucleus $(W,\gamma)$ of $\chi$ where
$\gamma\in\operatorname{Irr}(W)$ is $\pi$-factored with
$\chi=\gamma^{G}=(\delta_{(G,W)}\gamma)^{\pi G}$, and such that $Q$ is a
$\operatorname{Hall}$ $\pi^{\prime}$-subgroup of $W$ and
$\delta=(\delta_{(G,W)}\gamma_{\pi^{\prime}})_{Q}$. Applying Lemma 2.8, we
have $N\leq W$, and thus $Q\cap N$ is a $\operatorname{Hall}$
$\pi^{\prime}$-subgroup of $N$. This establishes (1).

For (2), let $\beta=(\gamma_{\pi^{\prime}})_{N}$, and note that
$\gamma_{\pi^{\prime}}(1)=\delta(1)=1$, so $\beta$ is a linear
$\pi^{\prime}$-special character of $N$. By Lemma 2.9(2), we see that
$N\leq\operatorname{Ker}(\delta_{(G,W)})$, and hence

$\beta_{Q\cap N}=((\delta_{(G,W)}\gamma_{\pi^{\prime}})_{N})_{Q\cap
N}=((\delta_{(G,W)}\gamma_{\pi^{\prime}})_{Q})_{Q\cap N}=\delta_{Q\cap N}.$

Now the uniqueness of $\beta$ is guaranteed by Lemma 2.2 with the roles of
$\pi$ and $\pi^{\prime}$ interchanged.

To show (3), let $\alpha$ be an irreducible constituent of
$(\gamma_{\pi})_{N}$. Then $\alpha$ is $\pi$-special, so $\alpha\beta$ is
irreducible by Lemma 2.4. It is clear that $\alpha\beta$ is an irreducible
constituent of $\gamma_{N}$, and since $\gamma$ lies under $\chi$, it follows
that $\alpha\beta$ is also an irreducible constituent of $\chi_{N}$. Note that
$\beta\in\operatorname{Lin}(N)$ is $\pi^{\prime}$-special, which implies that
$\beta^{0}\in{\rm I}_{\pi}(N)$ is principal, and thus
$\alpha^{0}=(\alpha\beta)^{0}$ is a constituent of
$(\chi_{N})^{0}=(\chi^{0})_{N}=\varphi_{N}$.

Finally, we establish (4). By (3), we see that $\alpha\beta$ is an irreducible
constituent of $\chi_{N}$ and that it is a lift. Since every irreducible
constituent of $\chi_{N}$ is conjugate to $\alpha\beta$ by Clifford’ theorem,
the first statement follows. This, along the formula
$\varphi_{N}=(\chi^{0})_{N}=(\chi_{N})^{0}$, implies that the second statement
holds. ∎

As an application, we establish a result that is similar to Lemma 3.3 of [7]
for $*$-vertices. Although the proof is similar, we present it here for
completeness.

######  Lemma 5.2.

Let $G$ be $\pi$-separable with $2\notin\pi$, and suppose that $\chi,\psi\in
L^{*}_{\varphi}(Q,\delta)$, where $\varphi\in{\rm I}_{\pi}(G)$ and $Q$ is a
$\pi^{\prime}$-subgroup of $G$ with $\delta\in\operatorname{Lin}(Q)$. If $N$
is a normal subgroup of $G$, then the irreducible constituents of $\chi_{N}$
are $\pi$-factored if and only if the irreducible constituents of $\psi_{N}$
are $\pi$-factored.

###### Proof.

By symmetry, it is no loss to assume that each irreducible constituent of
$\chi_{N}$ is $\pi$-factored. We need to show that the irreducible
constituents of $\psi_{N}$ are also $\pi$-factored.

Let $L\vartriangleleft G$ be maximal with the property that $L\leq N$ and the
irreducible constituents of $\psi_{L}$ are $\pi$-factored. If $L=N$, we are
done, and so we suppose that $L<N$.

Note that the irreducible constituents of $\chi_{L}$ are also $\pi$-factored,
and by Lemma 5.1, there exist $\alpha_{1},\alpha_{2}\in{\rm X}_{\pi}(L)$ and
$\beta\in{\rm X}_{\pi^{\prime}}(L)$ such that $\alpha_{1}\beta$ and
$\alpha_{2}\beta$ are irreducible constituents of $\chi_{L}$ and $\psi_{L}$,
respectively, that $\beta_{Q\cap L}=\delta_{Q\cap L}$, and that both
$(\alpha_{1})^{0}$ and $(\alpha_{2})^{0}$ are irreducible constituents of
$\varphi_{L}$. Then $(\alpha_{1})^{0}$ and $(\alpha_{2})^{0}$ are conjugate in
$G$ by Clifford’s theorem for $\pi$-partial characters (see Corollary 5.7 of
[14]), which implies that $\alpha_{1}$ and $\alpha_{2}$ are $G$-conjugate by
the injection from ${\rm X}_{\pi}(L)\to{\rm I}_{\pi}(L)$ (see Lemma 2.3).

Let $M/L$ be a chief factor of $G$ with $M\leq N$. Then $M/L$ is either a
$\pi$-group or a $\pi^{\prime}$-group, and since we are assuming that
$\chi_{N}$ has $\pi$-factored irreducible constituents, each irreducible
constituent of $\chi_{M}$ is $\pi$-factored, and hence some member of
$\operatorname{Irr}(M|\alpha_{1}\beta)$ must be $\pi$-factored. By Lemma 2.6,
we see that either $\beta$ or $\alpha_{1}$ is $M$-invariant, according as
$M/L$ is a $\pi$-group or a $\pi^{\prime}$-group. Clearly $\alpha_{1}$ is
$M$-invariant if and only if $\alpha_{2}$ (which is $G$-conjugate to
$\alpha_{1}$) is $M$-invariant. In both cases, we conclude that every member
of $\operatorname{Irr}(M|\alpha_{2}\beta)$ is $\pi$-factored by Lemma 2.6
again. Since $\operatorname{Irr}(M|\alpha_{2}\beta)$ contains some irreducible
constituent of $\psi_{M}$, we know that the irreducible constituents of
$\psi_{M}$ are also $\pi$-factored. This contradicts the maximality of $L$,
thus proving the lemma. ∎

The following is part of Theorem 2.1 of [16] in which the whole group $G$ was
originally supposed to be solvable. Actually, it suffices to assume that $G$
is $\pi$-separable for our purpose, and we omit the proof here because there
is no need to repeat the argument word by word.

######  Lemma 5.3.

Let $G$ be a $\pi$-separable group, and suppose that $\varphi\in{\rm
I}_{\pi}(G)$ has vertex $Q$, where $Q$ is a $\pi^{\prime}$-subgroup of $G$.
Let $V$ be a subgroup of $G$ containing $Q$, and write ${\rm
I}_{\varphi}(V|Q)$ to denote the set of irreducible $\pi$-partial characters
of $V$ with vertex $Q$ that induce $\varphi$, that is,

${\rm I}_{\varphi}(V|Q)=\\{\eta\in{\rm I}_{\pi}(V|Q)\,|\,\eta^{G}=\varphi\\}.$

If $G$ and $V$ are chosen so that $|G|+|V|$ is minimal subject to the
condition that

$|{\rm I}_{\varphi}(V|Q)|>|N_{G}(Q):N_{V}(Q)|,$

then $V$ is a nonnormal maximal subgroup of $G$, and $\varphi_{N}$ has a
unique irreducible constituent, where $N$ is the core of $V$ in $G$.

A key ingredient in our proof of Theorem B is the following corollary of Lemma
5.3.

######  Corollary 5.4.

Let $G$ be $\pi$-separable with $2\notin\pi$, and let $Q$ be a
$\pi^{\prime}$-subgroup of $G$. Suppose that $\varphi\in{\rm I}_{\pi}(G|Q)$
and $Q\leq V\leq G$. Then $|{\rm I}_{\varphi}(V|Q)|\leq|N_{G}(Q):N_{V}(Q)|$.

###### Proof.

Assume that the result is false, and let $G$ be a counterexample such that
$|G|+|V|$ is as small as possible. Let $N$ be the core of $V$ in $G$. Applying
Lemma 5.3, we see that $V$ is a maximal subgroup of $G$ with $N<V$, and that
$\varphi_{N}=e\alpha$ where $e$ is a positive integer and $\alpha\in{\rm
I}_{\pi}(N)$. In particular, $\alpha$ is invariant in $G$.

Let $K/N$ be a chief factor of $G$. Then $K\nsubseteq V$ by the definition of
$N$, and the maximality of $V$ forces $KV=G$. Write $D=K\cap V$. Since $G$ is
$\pi$-separable, we know that $K/N$ is either a $\pi$-group or a
$\pi^{\prime}$-group.

Suppose that $K/N$ is a $\pi^{\prime}$-group. Let $\theta\in{\rm I}_{\pi}(K)$
lie under $\varphi$ and over $\alpha$. Since $\alpha$ is $G$-invariant, we
have $\theta_{N}=\alpha$ by Clifford’s theorem for ${\rm I}_{\pi}$-characters
(Corollary 5.7 of [14]), and thus $\theta_{D}$ is irreducible. Then
restriction defines a bijection from ${\rm I}_{\pi}(G|\theta)$ onto ${\rm
I}_{\pi}(V|\theta_{D})$ (see Lemma 5.20 of [14]), which implies that
$\varphi_{V}$ is irreducible, and consequently, $\varphi$ cannot be induced
from $V$. This shows that the set ${\rm I}_{\varphi}(V|Q)$ is empty, a
contradiction. So we are done in this case.

Now suppose that $K/N$ is a $\pi$-group. Then $K/N$ has odd order because
$2\notin\pi$, and hence $K/N$ is solvable by the Feit-Thompson odd-order
theorem. We conclude that $K/N$ is an abelian $p$-group for some odd prime
$p$, which implies that $D=K\cap V$ is normal in $G$, so $D=N$.

We will use ${\rm B}_{\pi}$-characters to derive a contradiction (see [14] for
the definition and properties). Let $\hat{\alpha}\in{\rm B}_{\pi}(N)$ be such
that $(\hat{\alpha})^{0}=\alpha$. Since $\alpha$ and $\hat{\alpha}$ determine
each other, it follows that $\hat{\alpha}$ is also $G$-invariant. Fix
$\xi\in{\rm I}_{\varphi}(V|Q)$. Then $\xi^{G}=\varphi$, which implies that
$\xi$ lies under $\varphi$ (see Lemma 5.8 of [14]), and thus $\xi$ lies over
$\alpha$. Let $\hat{\xi}\in{\rm B}_{\pi}(V)$ be a lift for $\xi$. Since the
irreducible constituents of $\hat{\xi}_{N}$ are still ${\rm
B}_{\pi}$-characters, we see that $\hat{\alpha}$ is an irreducible constituent
of ${\hat{\xi}}_{N}$. Furthermore, observe that
$(\hat{\xi}^{G})^{0}=(\hat{\xi}^{0})^{G}=\xi^{G}=\varphi$, so $\hat{\xi}^{G}$
is irreducible, which is not the case by Theorem 7.21 of [14]. This
contradiction completes the proof. ∎

The following result, which we think is of independent interest, is the key to
the proof of Theorem B in the introduction.

######  Theorem 5.5.

Let $G$ be a $\pi$-separable group with $2\notin\pi$, and suppose that
$\varphi\in{\rm I}_{\pi}(G)$ has vertex $Q$, where $Q$ is a
$\pi^{\prime}$-subgroup of $G$. If $\delta\in\operatorname{Lin}(Q)$, then
$|L^{*}_{\varphi}(Q,\delta)|\leq|N_{G}(Q):N_{G}(Q,\delta)|$.

###### Proof.

We proceed by induction on $|G|$, and assume without loss that
$L^{*}_{\varphi}(Q,\delta)$ is not an empty set. By Lemma 2.8 and Lemma 5.2,
we can fix $N\vartriangleleft G$ such that for each $\chi\in
L^{*}_{\varphi}(Q,\delta)$, $N$ is the unique maximal normal subgroup of $G$
with the property that every irreducible constituent of $\chi_{N}$ is
$\pi$-factored. We will complete the proof by carrying out the following
steps.

Step 1. We may suppose that $\varphi_{N}=e\mu$, where $e$ is an integer and
$\mu\in{\rm I}_{\pi}(N)$.

###### Proof.

By Lemma 6.33 of [14], we can choose an irreducible constituent $\mu$ of
$\varphi_{N}$ such that the Clifford correspondent $\varphi_{\mu}$ of
$\varphi$ with respect to $\mu$ also has vertex $Q$, that is,
$\varphi_{\mu}\in{\rm I}_{\pi}(G_{\mu}|Q)$. Set $T=G_{\mu}$. Consider the
conjugation action of $N_{G}(Q)$ on $\operatorname{Lin}(Q)$, and let
$\\{\delta_{1},\ldots,\delta_{k}\\}$ be a set of representatives of
$N_{T}(Q)$-orbits on the $N_{G}(Q)$-orbit containing $\delta$. We will
construct an injection from $L^{*}_{\varphi}(Q,\delta)$ into
$\bigcup_{i=1}^{k}{\rm L}^{*}_{\varphi_{\mu}}(Q,\delta_{i})$.

To do this, we fix an arbitrary character $\chi\in L^{*}_{\varphi}(Q,\delta)$.
By Lemma 5.1(4), there exists an irreducible constituent $\theta$ of
$\chi_{N}$ such that $\theta$ is $\pi$-factored with $\pi$-degree and
$\theta^{0}=\mu$. Applying the Clifford correspondence for $\pi$-induction
(see Lemma 2.12), we obtain a unique character
$\psi\in\operatorname{Irr}(G_{\theta}|\theta)$ satisfying $\psi^{\pi G}=\chi$.
Clearly, the equality $\theta^{0}=\mu$ implies that $G_{\theta}\leq
G_{\mu}=T$, and so we can write $\eta=\psi^{\pi T}$. Then $\eta^{\pi
G}=(\psi^{\pi T})^{\pi G}=\psi^{\pi G}=\chi$, and thus

$(\eta^{0})^{G}=((\delta_{(G,T)}\eta)^{0})^{G}=((\delta_{(G,T)}\eta)^{G})^{0}=(\eta^{\pi
G})^{0}=\chi^{0}=\varphi,$

which forces $\eta^{0}\in{\rm I}_{\pi}(T)$. On the other hand, since
$N\leq\operatorname{Ker}(\delta_{(T,G_{\theta})})$ by Lemma 2.9, we know that
$\delta_{(T,G_{\theta})}\psi$ lies over $\theta$, and hence
$\eta=(\delta_{(T,G_{\theta})}\psi)^{T}$ lies over $\theta$. So $\eta^{0}$
lies over $\theta^{0}=\mu$, and by the Clifford correspondence for ${\rm
I}_{\pi}$-character, we conclude that $\eta^{0}=\varphi_{\mu}$.

Furthermore, since $\chi$ is a good lift for $\varphi$, it is easy to see that
$\eta$ is also a good lift for $\varphi_{\mu}$. We may therefore assume that
$\eta\in{\rm L}^{*}_{\varphi_{\mu}}(Q,\delta^{\prime})$ for some linear
character $\delta^{\prime}$ of $Q$. Since $\eta^{\pi G}=\chi$, it follows that
$(Q,\delta^{\prime})$ is also a $*$-vertex for $\chi$. Now Theorem 4.5 implies
that $(Q,\delta^{\prime})=(Q,\delta)^{g}$ for some element $g\in G$, so $g\in
N_{G}(Q)$. From this we conclude that $\eta$ has a $*$-vertex that is
$N_{T}(Q)$-conjugate to one of the $(Q,\delta_{i})$ for some
$i\in\\{1,\ldots,k\\}$. Of course this pair $(Q,\delta_{i})$ is itself a
$*$-vertex for $\eta$, and we obtain $\eta\in\bigcup_{i=1}^{k}{\rm
L}^{*}_{\varphi_{\mu}}(Q,\delta_{i})$.

We claim that $\eta$ is determined uniquely by $\chi$. To see this, it
suffices to show that $\eta$ is independent of the choice of $\theta$. Assume
that $\theta^{\prime}\in\operatorname{Irr}(N)$ is a constituent of $\chi_{N}$
with $(\theta^{\prime})^{0}=\mu$. Then $\theta^{\prime}=\theta^{x}$ for some
$x\in G$, and hence
$\mu=(\theta^{\prime})^{0}=(\theta^{x})^{0}=(\theta^{0})^{x}=\mu^{x}$. It
follows that $x\in G_{\mu}=T$. Let
$\psi^{\prime}\in\operatorname{Irr}(G_{\theta^{\prime}}|\theta^{\prime})$ be
such that $(\psi^{\prime})^{\pi G}=\chi$, and let
$\eta^{\prime}=(\psi^{\prime})^{\pi T}$. Then $\psi^{\prime}=\psi^{x}$, and
thus $\eta^{\prime}=\eta^{x}=\eta$, as desired.

Now we have established a well-defined map $\chi\mapsto\eta$ from
$L^{*}_{\varphi}(Q,\delta)$ into $\bigcup_{i=1}^{k}{\rm
L}^{*}_{\varphi_{\mu}}(Q,\delta_{i})$. Since $\eta^{\pi G}=\chi$, this map is
injective, and hence we have

$|L^{*}_{\varphi}(Q,\delta)|\leq\sum_{i=1}^{k}|{\rm
L}^{*}_{\varphi_{\mu}}(Q,\delta_{i})|.$

If $T<G$, then the inductive hypothesis yields

$|{\rm
L}^{*}_{\varphi_{\mu}}(Q,\delta_{i})|\leq|N_{T}(Q):N_{T}(Q,\delta_{i})|.$

Observe that $|N_{T}(Q):N_{T}(Q,\delta_{i})|$ is the orbit size of the
$N_{T}(Q)$-orbit containing $\delta_{i}$ under the action of $N_{T}(Q)$ on the
$N_{G}(Q)$-orbit containing $\delta$, and thus

$|L^{*}_{\varphi}(Q,\delta)|\leq\sum_{i=1}^{k}|N_{T}(Q):N_{T}(Q,\delta_{i})|=|N_{G}(Q):N_{G}(Q,\delta)|.$

The result follows in this case, and we may therefore assume that $G_{\mu}=G$.
That is, $\mu$ is invariant in $G$, so that $\varphi_{N}=e\mu$ for some
integer $e$. ∎

Step 2. There exists a character $\theta\in\operatorname{Irr}(N)$ such that
$\theta$ is $N_{G}(Q,\delta)$-invariant and lies under every character in
$L^{*}_{\varphi}(Q,\delta)$. Furthermore, writing $V=G_{\theta}$, we have

$|L^{*}_{\varphi}(Q,\delta)|\leq|{\rm
I}_{\varphi}(V|Q)||N_{V}(Q):N_{V}(Q,\delta)|,$

where ${\rm I}_{\varphi}(V|Q)$ is the set of those members of ${\rm
I}_{\pi}(V|Q)$ that induce $\varphi$, as in Lemma 5.3.

###### Proof.

By Lemma 5.1, we set $\theta=\alpha\beta$, where
$\alpha\in\operatorname{Irr}(N)$ is the unique $\pi$-special character such
that $\alpha^{0}=\mu$ and $\beta\in\operatorname{Irr}(N)$ is the unique
$\pi^{\prime}$-special character with $\beta_{Q\cap N}=\delta_{Q\cap N}$. Then
$\theta$ is irreducible and $\theta^{0}=\alpha^{0}=\mu$. Furthermore, since
$\mu$ is invariant in $G$ by Step 1, it follows that $\alpha$ is
$G$-invariant, and in particular, we have $G_{\beta}=G_{\theta}=V$. Observe
that $N_{G}(Q,\delta)$ fixes $\delta_{Q\cap N}$, so it leaves $\beta$
unchanged. This shows that $\theta$ is $N_{G}(Q,\delta)$-invariant, i.e.
$N_{G}(Q,\delta)\leq G_{\theta}$. By Lemma 5.1 again, it is easy to see that
every character in $L^{*}_{\varphi}(Q,\delta)$ lies over $\theta$, that is,
$L^{*}_{\varphi}(Q,\delta)\subseteq\operatorname{Irr}(G|\theta)$.

Assume first that $V=G$. Then $\theta$ is $G$-invariant, and by Lemma 2.8, we
have $N=G$. It follows that $L^{*}_{\varphi}(Q,\delta)=\\{\theta\\}$, and the
result trivially holds in this case.

We can therefore assume that $V<G$. For any character $\chi\in
L^{*}_{\varphi}(Q,\delta)$, there exists a unique
$\psi\in\operatorname{Irr}(V|\theta)$ such that $\psi^{\pi G}=\chi$ by the
Clifford correspondence for $\pi$-induction (Lemma 2.12), so that
$\chi\mapsto\psi$ defines an injection from $L^{*}_{\varphi}(Q,\delta)$ into
$\operatorname{Irr}(V|\theta)$. We will show that $\psi^{0}\in{\rm
I}_{\varphi}(V|Q)$.

First, we note that

$\varphi=\chi^{0}=(\psi^{\pi
G})^{0}=((\delta_{(G,V)}\psi)^{G})^{0}=((\delta_{(G,V)}\psi)^{0})^{G}=(\psi^{0})^{G},$

so $\psi^{0}$ is irreducible and induces $\varphi$.

Next, we claim that $(Q,\delta)$ is a $*$-vertex for $\psi$. To see this, let
$(Q^{*},\delta^{*})$ be a $*$-vertex for $\psi$. Since $\theta$ is the unique
irreducible constituent of $\psi_{N}$, we have $\beta_{Q^{*}\cap
N}=\delta^{*}_{Q^{*}\cap N}$ by Lemma 5.1. Also, since $(Q^{*},\delta^{*})$ is
clearly a $*$-vertex for $\chi$, there exists some element $y\in G$ such that
$(Q^{*},\delta^{*})=(Q,\delta)^{y}$ by Theorem 4.5. Now we have

$\beta_{Q^{y}\cap N}^{y}=(\beta_{Q\cap N})^{y}=(\delta_{Q\cap
N})^{y}=\delta^{y}_{Q^{y}\cap N}=\delta_{Q^{*}\cap N}^{*}=\beta_{Q^{*}\cap
N}=\beta_{Q^{y}\cap N}.$

Since $Q^{y}\cap N=(Q\cap N)^{y}$ is a $\operatorname{Hall}$
$\pi^{\prime}$-subgroup of $N$ by Lemma 5.1 again, it follows from Lemma 2.2
that $\beta^{y}=\beta$, and thus $y\in G_{\beta}=V$. This shows that
$(Q,\delta)$ is also a $*$-vertex for $\psi$, as claimed.

Finally, by Lemma 2.7, we see that $\psi^{0}\in{\rm I}_{\pi}(V)$ has vertex
$Q$. Since we have established that $\psi^{0}$ induces $\varphi$, it follows
that $\psi^{0}\in{\rm I}_{\varphi}(V|Q)$, as wanted.

Now let ${\rm I}_{\varphi}(V|Q)=\\{\zeta_{1},\ldots,\zeta_{m}\\}$. Then
$\psi^{0}=\zeta_{i}$ for some $i\in\\{1,\ldots,m\\}$, so that $\psi\in{\rm
L}^{*}_{\zeta_{i}}(Q,\delta)$. It follows that the map $\chi\mapsto\psi$
defines an injection from $L^{*}_{\varphi}(Q,\delta)$ into
$\bigcup_{i=1}^{m}{\rm L}^{*}_{\zeta_{i}}(Q,\delta)$, and we have

$|L^{*}_{\varphi}(Q,\delta)|\leq\sum_{i=1}^{m}|{\rm
L}^{*}_{\zeta_{i}}(Q,\delta)|.$

Since $V<G$, the inductive hypothesis guarantees that $|{\rm
L}^{*}_{\zeta_{i}}(Q,\delta)|\leq|N_{V}(Q):N_{V}(Q,\delta)|$, and hence
$|L^{*}_{\varphi}(Q,\delta)|\leq m|N_{V}(Q):N_{V}(Q,\delta)|=|{\rm
I}_{\varphi}(V|Q)||N_{V}(Q):N_{V}(Q,\delta)|$. ∎

We can now complete the proof of the theorem. By Step 2, we know that
$N_{G}(Q,\delta)\leq V$, so $N_{V}(Q,\delta)=N_{G}(Q,\delta)$. Applying
Corollary 5.4, we have $|{\rm I}_{\varphi}(V|Q)|\leq|N_{G}(Q):N_{V}(Q)|$.
This, together with the inequality in Step 2, yields

$|L^{*}_{\varphi}(Q,\delta)|\leq|N_{G}(Q):N_{V}(Q)||N_{V}(Q):N_{G}(Q,\delta)|=|N_{G}(Q):N_{G}(Q,\delta)|,$

and the proof is now complete. ∎

As before, we prove a more general result, which covers Theorem B by taking
$\pi=\\{2\\}^{\prime}$.

######  Theorem 5.6.

Let $G$ be a $\pi$-separable group with $2\notin\pi$, and suppose that
$\varphi\in{\rm I}_{\pi}(G)$ has vertex $Q$, where $Q$ is a
$\pi^{\prime}$-subgroup of $G$. If $\delta\in\operatorname{Lin}(Q)$, then

$|\tilde{L}_{\varphi}(Q,\delta)|\leq|N_{G}(Q):N_{G}(Q,\delta)|,$

and thus $|\tilde{L}_{\varphi}|\leq|Q:Q^{\prime}|$.

###### Proof.

Fix $\delta\in\operatorname{Lin}(Q)$. By Lemma 4.5, we have
$\tilde{L}_{\varphi}(Q,\delta)=L^{*}_{\varphi}(Q,\delta_{(G,Q)}\delta)$, and
since $N_{G}(Q)$ fixes $\delta_{(G,Q)}$, it follows by Theorem 5.5 that

$|L^{*}_{\varphi}(Q,\delta_{(G,Q)}\delta)|\leq|N_{G}(Q):N_{G}(Q,\delta_{(G,Q)}\delta)|=|N_{G}(Q):N_{G}(Q,\delta)|.$

This proves the first assertion, which implies that
$|\tilde{L}_{\varphi}|\leq|Q:Q^{\prime}|$ (by the remarks preceding the
statement of Theorem B in the introduction). ∎

Finally, we prove Corollary C from the introduction. Recall that a finite
group $G$ is said to be an $M$-group if every $\chi\in\operatorname{Irr}(G)$
is induced from a linear character of some subgroup of $G$. By Theorem 6.23 of
[13], if $G$ is a solvable group with a normal subgroup $N$, such that all
Sylow subgroups of $N$ are abelian and $G/N$ is supersolvable, then each
subgroup of $G$ is an $M$-group. We will prove the following somewhat more
general result, which clearly implies Corollary C.

######  Corollary 5.7.

Let $\varphi\in{\rm I}_{\pi}(G)$ with vertex $Q$, where $G$ is $\pi$-separable
with $2\notin\pi$. Suppose that there exists a normal subgroup $N$ of $G$,
such that $N$ has odd order and each subgroup of $G/N$ is an $M$-group. Then
$\tilde{L}_{\varphi}=L_{\varphi}$, and thus $|L_{\varphi}|\leq|Q:Q^{\prime}|$.

###### Proof.

Fix a character $\chi\in L_{\varphi}$, and note that $N\leq O_{\pi}(G)$ as
$2\notin\pi$. To prove that $\chi\in\tilde{L}_{\varphi}$, by Lemma 3.1 it
suffices to show that each $\pi$-factored character
$\psi\in\operatorname{Irr}(U)$ inducing $\chi$ has odd degree, where $N\leq
U\leq G$ and $\psi_{\pi^{\prime}}$ is primitive. Let
$\beta=\psi_{\pi^{\prime}}$. Then, by definition,
$N\leq\operatorname{Ker}\beta$, and we can view $\beta$ as a character of
$U/N$. By assumption, however, $U/N$ is an $M$-group, so the primitive
character $\beta$ must be linear. It follows that $\psi$ has $\pi$-degree, and
hence $\psi(1)$ is an odd number. Finally, we have
$|L_{\varphi}|\leq|Q:Q^{\prime}|$ by Theorem 5.6. ∎

## Acknowledgements

This work was supported by the NSF of China (12171289) and the NSF of Shanxi
Province (20210302123429 and 20210302124077).

## References

  * [1] J.P. Cossey, A construction of two distinct canonical sets of lifts of Brauer characters of a $p$-solvable group, Arch. Math. 87 (2006) 385-389.
  * [2] J.P. Cossey, Bounds on the number of lifts of a Brauer character in a $p$-solvable group, J. Algebra 312 (2007) 699-708.
  * [3] J.P. Cossey, Vertices of $\pi$-irreducible characters of groups of odd order, Comm. Algebra 36 (2008) 3972-3979.
  * [4] J.P. Cossey, Vertices and normal subgroups in solvable groups, J. Algebra 321 (2009) 2962-2969.
  * [5] J.P. Cossey, Vertex subgroups and vertex pairs in solvable groups, in _Character theory of Finite groups_ , Contemp. Math., AMS, Prov. RI, 524 (2010) 17-32.
  * [6] J.P. Cossey, M.L. Mark, Lifts of partial characters with cyclic defect groups, J. Aust. Math. Soc. 89 (2010) 145-163.
  * [7] J.P. Cossey, M.L. Lewis, Counting lifts of Brauer characters, arXiv:1008.1633 [math.GR], 2010.
  * [8] J.P. Cossey, M.L. Lewis, Inductive pairs and lifts in solvable groups, J. Group Theory 14 (2011) 201-212.
  * [9] J.P. Cossey, M.L. Lewis, G. Navarro, The number of lifts of a Brauer character with a normal vertex, J. Algebra 328 (2011) 484-487.
  * [10] J.P. Cossey, Vertex pairs and normal subgroups in groups of odd order, Rocky Mt. J. Math. 42 (2012) 59-69.
  * [11] J.P. Cossey, M.L. Lewis, Lifts and vertex pairs in solvable groups, Proc. Edinburgh Math. Soc. 55 (2012) 143-153.
  * [12] I.M. Isaacs, Induction and restriction of $\pi$-special characters, Can. J. Math. 38 (1986) 576-604.
  * [13] I.M. Isaacs, Character Theory of Finite Groups, Providence, RI: AMS Chelsea Publishing, 2006.
  * [14] I.M. Isaacs, Characters of Solvable Groups, RI: Amer. Math. Soc., 2018.
  * [15] M.L. Lewis, Obtaining nuclei from chains of normal subgroups, J. Alg. Appl. 5 (2006) 215-229.
  * [16] M.L. Lewis, Inducing $\pi$-partial characters with a given vertex, Ischina group theory 2010, 215-222, World Sci. Publ., Hackensack, NJ, 2012.
  * [17] G. Navarro, Characters and Blocks of Finite Groups, Cambridge: Cambridge University Press, 1998.
  * [18] G. Navarro, Vertices for characters of $p$-solvable groups, Trans. Amer. Math. Soc. 354 (2002) 2759-2773.
  * [19] G. Navarro, Problems on characters: solvable groups, Publ. Mat. 67 (2023) 173-198.
  * [20] L. Wang, P. Jin, The uniqueness of vertex pairs in $\pi$-separable groups, Comm. Algebra (published online); see also arXiv:2212.04846 [math.GR].
  * [21] L. Wang, P. Jin, Navarro vertices and lifts in solvable groups, arXiv:2302.09698 [math.GR], 2023.


# Search of Complex Binary Cellular Automata Using Behavioral Metrics

Juan C. López-González
Wolfram Research
and
Physics and Mathematics in Biomedicine Consortium, UCV
<EMAIL_ADDRESS>
Antonio Rueda-Toicen
Instituto Nacional de Bioingeniería
Universidad Central de Venezuela
and
Physics and Mathematics in Biomedicine Consortium, UCV
<EMAIL_ADDRESS>
###### Abstract

We propose the characterization of binary cellular automata using a set of
behavioral metrics that are applied to the minimal Boolean form of a cellular
automaton’s transition function. These behavioral metrics are formulated to
satisfy heuristic criteria derived from elementary cellular automata.
Behaviors characterized through these metrics are growth, decrease,
chaoticity, and stability. From these metrics, two measures of global behavior
are calculated: 1) a static measure that considers all possible input patterns
and counts the occurrence of the proposed metrics in the truth table of the
minimal Boolean form of the automaton; 2) a dynamic measure, corresponding to
the mean of the behavioral metrics in n executions of the automaton, starting
from n random initial states. We use these measures to characterize a cellular
automaton and guide a genetic search algorithm, which selects cellular
automata similar to the Game of Life. Using this method, we found an extensive
set of complex binary cellular automata with interesting properties, including
self-replication.

##  1 Introduction

Cellular automata with complex behavior exhibit dynamical patterns that can be
interpreted as the movement of particles through a physical medium. These
particles are interpretable as loci for information storage, and their
movement through space is interpretable as information transfer. The
collisions of these particles in the cellular automaton’s lattice are sites of
information processing [1, 2, 3, 4]. Cellular automata with complex behavior
have immense potential to describe physical systems and their study has had
impact in the design of self-assembling structures [5, 6, 7, 8] and the
modelling of biological processes like signaling, division, apoptosis,
necrosis and differentiation [9, 10, 11, 12, 19]. John Conway’s Game of Life
[13] is the most renowned complex binary cellular automaton, and the archetype
used to guide the search methodology for other complex binary cellular
automata that we describe in this work. Previously, complex behavior in binary
cellular automata has been characterized through measures such as entropy [3],
Lyapunov exponents [14, 15], and Kolmogorov-Chaitin complexity [16]. We
propose the characterization of the behavior of $n$-dimensional cellular
automata through heuristic measures derived from the evaluation of their
minimal Boolean forms. This proposed characterization is derived from
heuristic criteria validated in elementary cellular automata with simple
Boolean forms. Table 1 illustrates the rationale for this characterization
showing elementary cellular automata whose Boolean forms are minimally simple,
and whose behavior can be unequivocally identified. Cellular behaviors of
growth, decrease, and chaoticity are characterized by the Boolean operations
OR, AND, and XOR, respectively. The cellular behavior of stability can be
characterized by the absence of a Boolean operator or the use of the NOT
operator.

Rule | Sample Evolution | Boolean Form | Behavior
---|---|---|---
$R_{204}$ |  | q | Stable
$R_{160}$ |  | p AND r | Decreasing
$R_{252}$ |  | p OR q | Growing
$R_{90}$ |  | p XOR q | Chaotic

Table 1: Elementary cellular automata with simple Boolean forms, which are
unequivocally associated to a particular behavior. The Boolean values of the
cells in the neighborhood are $p$ for the left neighbor, $q$ for the central
cell, and $r$ for the right neighbor. Black cells are in 1 state, white cells
are in 0 state.

We define an evaluation criterion to produce metrics that characterize the
behavior of cellular automata whose minimal Boolean expressions are more
complex (i.e. have more terms and the combination of various operators) than
those appearing in Table 1. The produced metrics are used to create static and
dynamic measures of behavior. The static measure of behavior is calculated
from the truth table of the minimal Boolean expression of the cellular
automaton, and the dynamic measure of behavior is derived from the averaged
appearance of the metrics in n executions of the cellular automaton from n
random initial conditions. We use the Euclidean distance of these measures in
a given cellular automaton to the measures of the Game of Life to assess its
capacity for complex behavior, and use this distance as a cost function to
guide the genetic search of $n$-dimensional cellular automata with complex
behavior.

##  2 Definition of binary cellular automaton

A cellular automaton is formally represented by a quadruple $\\{Z,S,N,f\\}$,
where

  * $Z$ is the finite or infinite cell lattice,

  * $S$ is a finite set of states or values for the cells,

  * $N$ is the finite cell neighborhood,

  * $f$ is the local transition function, defined by the state transition rule.

Each cell in the lattice $Z$ is defined by its discrete position (an integer
number for each dimension) and by its discrete state value $S$. In a binary
cellular automaton, $S=\\{0,1\\}$. Time is also discrete. The state of the
cell is determined by the evaluation of the local transition function on the
cell’s neighborhood at time $t$; $t+1$ is the next time step after time $t$.
The neighborhood is defined as a finite group of cells surrounding and/or
including the observed cell.

###  2.1 Lattice, cell and configuration

The global state is the configuration of all the cells that comprise the
automaton, $C\in S^{Z}$. The lattice $Z$ is the infinite cyclic group of
integers $\\{\dots,-1,0,1,2,\dots\\}$. The position of each cell in the
lattice is described by the index position $x\in Z$. Configurations are
commonly written as sequences of characters, such as

$C=\dots c_{-1}c_{0}c_{1}c_{2}\dots$ (1)

The finite global state is a finite configuration $C\in S^{Z}$, where $Z$ is a
finite lattice, indexed with ${0,1,2,3\dots n-1}$ integers,

$C=c_{1}c_{2}\dots c_{x}c_{x+1}\dots c_{n-2}c_{n-1}$ (2)

###  2.2 Neighborhood and local transition function

The set of neighborhood indices $A$ of size $m=|A|$ is defined by the set of
relative positions within the configuration, such that

$A={a_{0},a_{1},\dots,a_{m-2},a_{m-1}}$ (3)

$N_{x}$ is the neighborhood of the observed cell $c_{x}$ that includes the set
$A$ of indices, and is defined as

$N_{x}=c_{x+a_{0}}c_{x+a_{1}}\dots c_{x+a_{m-2}}c_{x}+a_{m-1}$ (4)

this describes the neighborhood as a character string that includes the cells
that are considered neighbors of the observed cell $x$. A compact
representation of the neighborhood value $N_{x}$ is a unique integer, defined
as an $m-$digits, $k-$based number [2]

$N_{x}=\sum_{i=0}^{m-1}k^{m-1-i}c_{x+a_{i}}=c_{x+a_{0}}k^{m-1}+\dots+c_{x+a_{m-1}k}k^{0}$
(5)

The local transition function $f$ yields the value of $c_{x}$ at $t+1$ from
the neighborhood of the cell observed at present time $t$ is expressed by

$f(N_{x}^{t})=c_{x}^{t+1}$ (6)

where $N_{x}^{t}$ specifies the states of the neighboring cells to the cell
$x$ at time $t$. The transition table defines the local transition function,
listing an output value for each input configuration. Table 2 is a sample
transition table for an elementary cellular automaton with a neighborhood of
radius 1, wherein adjacent neighboring cells of $c_{x}$ are $c_{x-1}$ and
$c_{x+1}$, forming a tuple $\\{c_{x-1},c_{x},c_{x+1}\\}$, $S\in\\{0,1\\}$.

$N_{x}^{t}$ | $f(N_{x}^{t})$
---|---
000 | 0
001 | 1
010 | 1
011 | 1
100 | 1
101 | 0
110 | 1
111 | 0
Table 2: Local transition function of $R_{94}$ as a truth table.

###  2.3 Global transition function

The global dynamics of the cellular automaton are described by the global
transition function $F$

$F:S^{N}\rightarrow S^{N}$ (7)

$F$ is the transition between the current global configuration $C^{t}$ and the
next global configuration $C^{t+1}$

$C^{t+1}=F(C^{t})$ (8)

The global transition function $F$ is defined by the local transition function
$f$ as

$F(C_{x})=\dots f(N_{x-1})f(N_{x})f(N_{x+1})\dots$ (9)

##  3 Transformation of the cellular space

We redefine the local transition function to incorporate behavioral knowledge
of the automaton’s evolution, given an input/output pair. This redefined
function is applied to all cells of the automaton at a given evolution step t
to quantify its overall behavior.

###  3.1 Redefined local transition function

The redefined local transition function $g$ calculates the behavioral metric
of a single cell $c_{x}$ evaluating the local transition function $f$ on its
neighborhood $N_{x}^{t}$. Through the local transition function $g$, we define
the transformation $d_{x}^{t+1}$ that yields the next step of the evolution of
cell $c_{x}$ as

$d_{x}^{t+1}=g(f,N_{x}^{t})$ (10)

This transformation is necessary to calculate the measure of dynamic behavior
during the automaton’s evolution, and we propose the inclusion of a metric
characterizing the cell behavior obtained after evaluating a particular input.
Input for the Boolean operators considered may be of the form

$\mathit{Input_{1}<operator>Input_{2}=Output}$ (11)

where $\mathit{<operator>}\,\in\\{\mathit{OR,AND,XOR}\\}$ The behaviors
associated with each binary Boolean operator and its possible inputs and
outputs are shown in Table 3.

$\mathit{Input_{1}}$ | $\mathit{Input_{2}}$ | $\mathit{Output}$ | Behavior | $\mathit{OR}$ | $\mathit{AND}$ | $\mathit{XOR}$
---|---|---|---|---|---|---
0 | 0 | 0 | Stability | X | X |
1 | 0 | 0 | Decrease |  | X |
0 | 1 | 0 | Decrease |  | X |
1 | 1 | 0 | Chaoticity |  |  | X
0 | 0 | 1 | Chaoticity |  |  | X
1 | 0 | 1 | Growth | X |  |
0 | 1 | 1 | Growth |  |  | X
1 | 1 | 1 | Stability | X | X |
Table 3: Behaviors associated to binary Boolean patterns

The behaviors associated with unary patterns are shown in Table 4.

$\mathit{<operator>Input=Output}$ (12)

where $\mathit{<operator>}\,\in\\{\mathit{NOT,NOP}\\}$

$\mathit{Input}$ | $\mathit{Output}$ | Behavior | $\mathit{NOT}$ | $\mathit{NOP}$
---|---|---|---|---
1 | 1 | Stability |  | X
0 | 0 | Stability |  | X
1 | 0 | Stability | X |
0 | 1 | Stability | X |
Table 4: Behavior associated to unary Boolean patterns

where NOP stands for “no operator”. To characterize the automaton’s behavior,
we expand the state space

$g:\\{S^{N},f\\}\rightarrow M,$ (13)

where

$M=\\{0,1,2,3,4,5\\}$ (14)

The different values of $M$ abbreviate the duples of state and behavior shown
in Table 5. Each tuple is obtained from the result of the local transition
function $g$ applied to a particular configuration of the cell $x$ and its
neighborhood $N$.

$M$ | ${\\{S_{x}^{t+1},behavior\\}}$
---|---
0 | $\\{0,\mathit{stable}\\}$
1 | $\\{0,\mathit{decreasing}\\}$
2 | $\\{0,\mathit{chaotic}\\}$
3 | $\\{1,\mathit{chaotic}\\}$
4 | $\\{1,\mathit{growing}\\}$
5 | $\\{1,\mathit{stable}\\}$
Table 5: $M$ code, abbreviation of duples of cell state and behavior obtained
when applying the local transition function $g$.

The $M$ code eases the implementation of an algorithmic search for cellular
automata with interesting behavior using the proposed metrics. According to
the $M$ code, chaotic and stable behaviors may generate 1 or 0 as output from
1 or 0 as input, growing behavior may only generate 1 as output from 0 as
input, and decreasing behavior may only generate 0 as output from 1 as input.

###  3.2 Global transition function

The global behavioral metric of the cellular automaton is characterized as

$G:\\{S^{N},f\\}\rightarrow M^{N}$ (15)

$G$ represents the transition between the current global configuration $C^{t}$
and the next global configuration $C^{t+1}$. We set $D^{0}=(0,f)$ and express
the automaton’s global behavioral metric as

$D^{t+1}=G(C^{t},f)$ (16)

for example, from the initial state,

$C^{0}(initial\,state)$ $C^{1}=F(C^{0})\rightarrow D^{1}=G(C^{0},f)$
$C^{2}=F(C^{1})\rightarrow D^{2}=G(C^{1},f)$ $C^{3}=F(C^{2})\rightarrow
D^{3}=G(C^{2},f)$ $C^{4}=F(C^{3})\rightarrow D^{4}=G(C^{3},f)$ $\vdots$

The redefined global transition function $G$ is expressed as the concatenated
string obtained when the redefined local transition function $g$ is applied to
all of the automaton’s cells $c_{i}$

$G(\dots c_{x-1}c_{x}c_{x+1},f)=\ldots
g(n_{x-1},f)g(n_{x},f)g(n_{x+1},f)\dots$ (17)

###  3.3 Implementation of $g(f,N_{x}^{t})$

The $g$ function incorporates heuristic information that enables the
measurement of behaviors in the automaton’s lattice. The $g$ function performs
the following steps, given a pattern $N_{x}^{t}$ and the transition function
$f$:

  1. 1.

The local transition function $f$ is simplified to its minimal Boolean
expression.

  2. 2.

$f$ is expressed as a binary execution tree.

  3. 3.

$N_{x}^{t}$ is evaluated on the binary execution tree obtained in $2$.

In Table 1 we mentioned the behavioral characterization corresponding to
cellular automata whose minimal expression correspond to a single Boolean
operator. This characterization needs to be extended to describe cellular
automata whose minimal forms have several distinct Boolean operators. To
tackle this problem, we express a cellular automaton’s transition function in
a binary evaluation tree and propose a set of evaluation rules for its nodes
based on heuristic criteria.

We write the transition function of the minimal expression of the automaton’s
rule in a tree graph. We assign to each node of the tree a Boolean operation.
The transition function is evaluated, with input placed at the tree’s leaves,
according to heuristic rules. The result of the evaluation is obtained at the
root node. The heuristics considered are crafted to fit criteria derived from
the characteristic behaviors of several elementary cellular automata.

The proposed heuristic $H$ consists of rules for evaluation of the nodes in
the binary tree. These tree evaluation rules are defined for

${\mathit{term}\,\mathit{<OPERATOR>}\,\mathit{term}}$

and

$\mathit{\mathit{<OPERATOR>}\,\mathit{term}}$

where $\mathit{<OPERATOR>\,\in\,\\{\mathit{AND,OR,XOR,NOT}\\}}$ and
$\mathit{term}$ corresponds to the set $M=\\{0,1,2,3,4,5\\}$

Figure 1 shows the heuristic precedence rules defined for each logical
operator. Figure 2 shows the elementary cellular automata used to define the
heuristic characterization criteria, alongside their minimal Boolean forms.

|
---|---
AND | OR
|
XOR | NOT
Figure 1: Tree Evaluation rules $H$, squares correspond to inputs and circles
to outputs. White corresponds to $M=0=\\{0,\mathit{stable}\\}$; yellow
corresponds to $M=1=\\{0,\mathit{decrease}\\}$; green corresponds to
$M=2=\\{0,\mathit{chaotic}\\}$; red corresponds to
$\mathit{M=3=\\{1,\mathit{chaotic}\\}}$; blue corresponds to
$M=4=\\{1,\mathit{growth}\\}$; black corresponds to
$\mathit{M=5=\\{1,\mathit{stable}\\}}$.

|  |
---|---|---
$R_{90}=$ p XOR r | $R_{128}=$ p AND q AND r |  $R_{150}=$ p XOR q XOR r
|  |
$R_{160}=$ p AND r |  $R_{204}=$ q |  $R_{250}=$ p OR r
|  |
|  $R_{254}=$ p OR q OR r |
Figure 2: Elementary cellular automata used to define the criteria in $H$.

  * Criterion 1 - In the leaf nodes, $S=0$ must be equivalent to $M=0=\\{0,\,\mathit{stable}\\}$ and $S=1$ must be equivalent to $M=5=\\{1,\mathit{stable}\\}$.

  * Criterion 2 - Chaoticity measured in $R_{150}=p\,\mathit{XOR}\,q\,\mathit{XOR}\,r$ must be greater than chaoticity measured in $R_{90}=p\,\mathit{XOR}\,r$.
The proposed heuristic $H$ produces the following behavioral metrics in these
automata:

$R_{150}\,\mathit{chaoticity}=0.375$ $R_{90}\,\mathit{chaoticity}=0.25$

  * Criterion 3 - Chaoticity measured in $R_{90}=p\,\mathit{XOR}\,r$ must be greater than chaoticity measured in $R_{204}=q$.
The proposed heuristic $H$ produces the following behavioral metrics in these
automata:

$R_{90}\,\mathit{chaoticity}=0.25$ $R_{204}\,\mathit{chaoticity}=0$

  * Criterion 4 - Decrease measured in $R_{128}=p\,\mathit{AND}\,q\,\mathit{AND}\,r$ must be greater than decrease measured in $R_{160}=p\,\mathit{AND}\,r$.
The proposed heuristic $H$ produces the following behavioral metrics in these
automata:

$R_{128}\,\mathit{decrease}=0.75$ $R_{160}\,\mathit{decrease}=0.5$

  * Criterion 5 - Decrease measured in $R_{128}=p\,\mathit{AND}\,q\,\mathit{AND}\,r$ must be greater than decrease measured in $R_{160}=p\,\mathit{AND}\,r$.
The proposed heuristic $H$ produces the following behavioral metrics in these
automata:

$R_{160}\,\mathit{decrease}=0.5$ $R_{204}\,\mathit{decrease}=0$

  * Criterion 6 - Growth measured in $R_{254}=p\,\mathit{OR}\,q\,\mathit{OR}\,r$ must be greater than growth measured in $R_{250}=p\,\mathit{OR}\,r$
The proposed heuristic $H$ produces the following behavioral metrics in these
automata:

$R_{254}\,\mathit{growth}=0.75$ $R_{250}\,\mathit{growth}=0.5$

Figure 3 shows percentage of measured behaviors, using the proposed set of
evaluation rules $H$, in the elementary cellular automata considered in the
criteria.

Figure 3: Behavioral percentages in elementary cellular automata considered as
criteria for evaluating the proposed heuristic

###  3.4 Evaluation example with $R_{94}$

The minimal Boolean expression of $R_{94}$,
$f=(q\,\mathit{AND}\,(\mathit{NOT}\,p))\,\mathit{OR}\,\\\
(p\,\mathit{XOR}\,r)$, is placed in a binary evaluation tree, as shown in
Figure 4. Each node in the tree is evaluated using the rules shown in Figure
1. This process is demonstrated in the Steps 1-5 listed below.

Figure 4: Evaluation of the input pattern 101 in $R_{94}$ with the proposed
rules.

  * Step 1. In the leaf nodes, the values $N_{q}^{t=0}$ are $\\{p=1,q=0,r=1\\}$,

are transformed, using the $M$ code mentioned in Section 3.1 as follows:

$S_{M}(p)=\\{1,\mathit{stable}\\}=5$ $S_{M}(q)=\\{0,\mathit{stable}\\}=0$
$S_{M}(r)=\\{1,\mathit{stable}\\}=5$

thus, the input tuple $\\{p=1,q=0,r=1\\}$ is converted into
$\\{p=5,\,q=0,\,r=5\\}$.

  * Step 2. Leaf $p=5$ is evaluated at the $\mathit{NOT}$ node, producing output $0=\\{0,\mathit{stable}\\}$

  * Step 3. Leaf $q=0$ and the result of step 2 are evaluated at the $\mathit{AND}$ node, producing output $0=\\{0,stable\\}$.

  * Step 4. Leaves $p=5$ and $r=5$ are evaluated at the $\mathit{XOR}$ node producing output $2=\\{0,\mathit{chaotic}\\}$.

  * Step 5. The output of step 4 and the output of step 5 are evaluated at the $\mathit{OR}$ node, producing as final output $2=\\{0,\mathit{chaotic}\\}$. The cell $q$ gets assigned to state 0 in $t+1$, and a counter for the occurrence of chaotic behavior in the states of $R_{94}$ would get incremented by one.

##  4 Behavioral characterization

To characterize the overall behavior of a cellular automaton with the proposed
metrics, we consider the correlation between two measures:

1) A static measure, which is the counted occurrence of behaviors associated
to the code $M$, in the output of the truth table of the minimal Boolean
expression of the cellular automaton.

2) A dynamic measure, which is the median occurrence of behaviors associated
to the code $M$ in $n$ executions of the cellular automaton, starting from $n$
random initial states.

###  4.1 Static measure of behavior

The local transition function transition $f$ is expressed as a truth table,
which is converted to $g$ when we include behavioral information. To calculate
the static measure of behavior, we count the occurrence of behaviors
associated with the values of $M$ in the output of the truth table. This
static measure is a vector, with the percentages of chaoticity, stability,
growth and decrease measured in the cellular automaton. This static measure is
represented as a vector, with the percentages of chaoticity, stability, growth
and decrease measured in the cellular automaton.

For example, in $R_{94}$ the rule is characterized using the $M$ code as shown
in Table 6.

$N_{x}^{t}$ | $f(N_{x}^{t})$ | $g(N_{x},f)$
---|---|---
000 | 0 | $M=1$
001 | 1 | $M=4$
010 | 1 | $M=4$
011 | 1 | $M=4$
100 | 1 | $M=4$
101 | 0 | $M=2$
110 | 1 | $M=4$
111 | 0 | $M=2$
Table 6: Truth table of $R_{94}$, with associated $M$ code

To obtain the static measure of $R_{94}$, we count the occurrences of $M$. The
static measure of the rule is the percentage of behavioral occurrence in the
automaton, as shown in Table 7.

Stability | Decrease | Growth | Chaoticity
---|---|---|---
$M=\\{0,5\\}$ | $M=1$ | $M=4$ | $M=\\{2,3\\}$
0% | 12.5% | 62.5% | 25%
Table 7: Behavioral percentages in $R_{94}$, static measure

We express this measure as a vector of percentages.

$M_{E}=\\{stability\,\%,decrease\,\%,growth\,\%,chaoticity\,\%\\}$ (18)

For $R_{94}$, the static measure of behavior is

$M_{E}=\\{0,12.5,62.5,25\\}$

###  4.2 Dynamic measure of behavior

To estimate the dynamic measure of behavior $M_{D}$, we execute the cellular
automaton $n$ times, from $n$ random initial configurations $C_{i}^{t=0}|i\in
n$. We sample occurrences of $M$ in the cell space up to the $k$-th evolution
step, where $k$ is an integer > 0, obtained from a uniform distribution.

$M_{D}(g)=\lim_{x\to\infty}\frac{(M_{D}^{t=k}(g,c_{i}^{t=0}))}{n}$ (19)

We exclude cells at $t=0$ from the sampling. The percentages of behavioral
occurrences are calculated from the mean of samples. Figure 5 shows the
sampling of $R_{94}$ in $k=t=20$.

Figure 5: Evolution of $R_{94}$ from a random initial configuration, yellow
coloring for $M=1$, green coloring for $M=2$ and blue coloring for $M=4$. The
code $M$ was applied to cells in $t\geq 1$. The percentage of cells with $M=1$
(decreasing behavior) is 18.658%, cells with $M=2$ (stable behavior) are
32.467% and cells with $M=4$ (chaotic behavior) occupy 48.874% of the lattice.

##  5 Analysis of the Game of Life

The Game of Life is a complex cellular automaton, class IV according to the
classification proposed by Wolfram [1, 3]. In this cellular automaton, there
is a negative correlation between the static measure of behavior and the
dynamic measure of behavior. Table 11 shows this negative correlation and the
absolute difference between the static measure and the dynamic measure in the
Game of Life.

Some observations pertinent to the measured behavior in the Game of Life:

  * Static measure: chaotic behavior predominates, an important characteristic of class III automata.

  * Dynamic measure: decreasing behavior predominates, an important characteristic of class I automata.

Looking at the transition function $f$ of The Game of Life, one can find
patterns such as

$(\dots)$
$\mathit{NOT}\,x0\,\mathit{AND}\,\mathit{NOT}\,x1\,\mathit{AND}\,\mathit{NOT}\,x2\,\mathit{AND}\,x8$
$\mathit{AND}\,\,\boldsymbol{(x3\,\mathit{XOR}\,x4)}\,\mathit{AND}\,\boldsymbol{(x5\,\mathit{XOR}\,x6)}\,\mathit{OR}$
$\,\mathit{NOT}\,x0\,\mathit{AND}\,\mathit{NOT}\,x1\,\mathit{AND}\,\mathit{NOT}\,x3\,\mathit{AND}\,x8$
$\mathit{AND}\,\boldsymbol{(x2\,\mathit{XOR}\,x4)}\,\mathit{AND}\,\boldsymbol{(x5\,\mathit{XOR}\,x6)}\,\mathit{OR}$
$(\dots)$

| $M_{E}$ | $M_{D}$
---|---|---
Chaoticity | 67.96 | 13.38
Decrease | 4.68 | 75.23
Growth | 27.34 | 11.37
Stability | 0 | 0
Table 8: Static and dynamic measures in the Game of Life, their correlation is
-0.29

It is our hypothesis that the emergence of complex behavior in the Game of
Life is determined by the appearance of islands of chaotic behavior,
surrounded by decreasing patterns. Taking a close look at the boolean
expression of $f$ in the Game of Life, one can observe chaotic sub-expressions
like $\boldsymbol{(x3\,\mathit{XOR}\,x4)}$ being "restricted" with AND-ing by
decreasing sub-expressions such as
$(\mathit{AND}\,\mathit{NOT}\,x2\,\mathit{AND}\,x8)$.

Figure 6: The Game of Life, colored according to behavior

In Figure 6, yellow cells have value $M=1$ (decreasing behavior), and blue
cells have value $M=4$ (growth behavior). Green cells cells have $M=2$,
exhibiting chaotic behavior. Note that in Figure 6, decreasing cells ($M=1$)
cover the largest proportion of the lattice, which corresponds with the
dynamic measure of measure of decrease shown in Table 8. One can also
appreciate how the isolated patterns exhibit a combination of growth ($M=4$)
and chaoticity ($M=2$).

##  6  Search of complex binary cellular automata in two dimensions

The proposed behavioral metrics were crafted using heuristic criteria from
one-dimensional binary cellular automata, yet are applicable to characterize
binary cellular automata with different neighborhoods in lattices of higher
dimensions. To demonstrate this, we developed a genetic search algorithm [17]
of non-totalistic 2D cellular automata in the Moore neighborhood with radius
equal to one. This algorithm searches for automata with behavioral measures
similar to those in the Game of Life in a space of size $2^{512}$. The genetic
algorithm uses a cost function to evaluates each cellular automaton in the
population, with this cost being the Euclidean distance between the behavioral
measures of each cellular automaton with the behavioral measures of the Game
of Life. Another selection condition was added: like the Game of Life, the
selected cellular automaton must have $\mathit{stability}=0$ in both its
static and dynamic measures. We found a large number of cellular automata with
interesting complex behaviors, like gliders, blinkers and self-replicating
patterns.

###  6.1 Tests and results

The proposed genetic search algorithm evolved an initial population of 20
individuals through 5000 generations, each individual being a cellular
automaton with a randomly generated transition function $f$. Each cellular
automaton’s transition function is represented in the population as a
chromosome of 512 Boolean values. One point crossover and random mutation
(with probability 0.01) were applied at each evolution step[18]. The sampling
used to measure dynamic behavior was taken at random intervals at least 10
times for each cellular automaton in the population. In a space of $2^{512}$
possible cellular automata, we generated about 10000 different cellular
automata through crossover and mutation, and selected the 1000 closest to the
behavioral measures of the Game of Life. These automata were qualitatively
evaluated. We found 300 cellular automata in which one can appreciate gliders,
blinkers, and other interesting complex behaviors. Among the cellular automata
with complex behavior found, we identified a self-replicating cellular
automaton, corresponding to Wolfram rule number
$168956220003150428540506549680417619769424995409487733442556\\\
339612333081717128579374366701058219674682166161189003344417\\\
08509286446343520818184926824448$. In this automaton, we can appreciate a
pattern that is replicated twice after 91 steps, as shown in Figure 7.
Curiously, this complex cellular automaton is more distant from the behavioral
measures of the Game of Life than other CA found using the proposed
methodology. However, one characteristic is prevalent in this and the other
found CA: a negative correlation between their static and dynamic behavioral
measures.

---

(a) $t=0$

(b) Replication of the initial state at $t=91$

(c) Persistence of the pattern and its copy at $t=307$

Figure 7: Self replication in cellular automaton with behavioral metrics similar to the Game of Life, the feature vector of behavioral metrics used to find it is shown below. | $M_{E}$ | $M_{D}$
---|---|---
Chaoticity | 61.72 | 5.61
Decrease | 3.32 | 90.63
Growth | 34.96 | 3.77
Stability | 0 | 0
Euclidean distance to the feature vector of behavioral metrics of the Game of
Life is 21.31. The correlation between measures of static and dynamic behavior
in this cellular automaton is -0.45

This self-replicative pattern is a particular kind of localized structure that
moves across the cellular automaton’s lattice. These localized structures, or
"gliders" (which aren’t always self-replicative) can be seen as streaks in
averaged spacetime slices that depict the evolution of the cellular automaton
from random initial conditions. Figure 8 shows the spacetime slices depicting
gliders on the found self replicative CA and on the Game of Life, as
comparison.

|
---|---
Found Self-Replicative CA | Game of Life
Figure 8: Averaged spacetime evolutions, showing gliders as streaks.

We present examples of complex cellular automata found with the proposed
search method111One can execute these cellular automata in Mathematica
replacing  <Rule> with the corresponding rule number
ListAnimate[ArrayPlot[#]&/@CellularAutomaton[
<Rule>,2,1,1, RandomInteger[1,100,100],0,100]]  . Mean spacetime
visualizations of the evolving state of the automaton are provided for each;
the lower rows of the lattice being the latter time steps. A list of 277
selected complex binary cellular automata can be found in the Bitbucket
repository at http://bit.ly/complexbinaryca. A Java implementation of the
genetic search algorithm based on behavioral metrics is available at
http://discoverer.cellular-automata.com/.

Rule: 354830437430697307314658045280649922899653607237
152783088733395073850801752918249535088820853655864680729
189540963997737594766246170112169867440686203456

| $M_{E}$ | $M_{D}$
---|---|---
Chaoticity | 62.11 | 12.06
Decrease | 4.88 | 78.88
Growth | 33.01 | 9.06
Stability | 0 | 0
Table 9: Euclidean distance to the feature vector of behavioral metrics of the
Game of Life is 9.32. The correlation between measures of static and dynamic
behavior in this cellular automaton is -0.34
---
Averaged spacetime evolution
Identified gliders

Rule: 196928112803567351078509513317947776313717639009629
19233419392303723364585678060118178225231534916460395002491
6004629851769274774088586292232688540354568

| $M_{E}$ | $M_{D}$
---|---|---
Chaoticity | 64.45 | 9.28
Decrease | 2.54 | 84.80
Growth | 33.01 | 5.92
Stability | 0 | 0
Table 10: Euclidean distance to the feature vector of behavioral metrics of
the Game of Life is 13.68. The correlation between measures of static and
dynamic behavior in this cellular automaton is -0.40
---
Averaged spacetime evolution
Identified gliders

Rule: 25369628583304459989446065099150613536215022807637650
13218910019118617632623181726351808015804669971129335990123
389394577484439270322287946219773078676008

| $M_{E}$ | $M_{D}$
---|---|---
Chaoticity | 65.63 | 5.53
Decrease | 3.91 | 90.54
Growth | 30.47 | 4.00
Stability | 0 | 0
Table 11: Euclidean distance to the feature vector of behavioral metrics of
the Game of Life is 19.13. The correlation between measures of static and
dynamic behavior in this cellular automaton is -0.42.
---
Averaged spacetime evolution
Identified glider

## Acknowledgements

We wish to thank Jan Baetens, Hector Zenil, Alyssa Adams, and Nima Dehghani
for their helpful comments. We appreciate the support of the Physics and
Mathematics in Biomedicine Consortium. We also wish to thank Todd Rowland for
his encouragement and continued interest in the project

## References

  * [1] S. Wolfram, A New Kind of Science, Wolfram Media, Champaign, IL, 2002.
  * [2] S. Wolfram, "Statistical Mechanics of Cellular Automata," Reviews of Modern Physics, 55(3), 1983, pp. 601-644.
  * [3] S. Wolfram, "Universality and Complexity in Cellular Automata," Physica D: Nonlinear Phenomena, 10(1), 1984, pp. 1-35.
  * [4] A. Adamatzky and J. Durand-Lose, "Collision Based Computing," section of the Handbook of Natural Computing, Springer, 2012, pp. 1949-1978
  * [5] M. Nilsson and S. Rasmussen, "Cellular Automata for Simulating Molecular Self-Assembly," Discrete Mathematics and Theoretical Computer Science, 2003, pp. 31-42.
  * [6] P. Rothemund, N. Papadakis and E. Winfree, "Algorithmic Self-Assembly of DNA Sierpinski Triangles," PLOS Biology, 2004.
  * [7] H. Abelson, D. Allen, D. Coore, C. Hanson, E. Rauch, G. J. Sussman, G. Homsy, J. Thomas F. Knight and R. W. Radhika Nagpal, "Amorphous Computing," Communications of the ACM, 43(5), 2000, pp. 74-82.
  * [8] M. Hirabayashi, S. Kinoshita, S. Tanaka, H. Honda, H. Kojima and K. Oiwa, "Cellular Automata Analysis on Self-Assembly Properties in DNA Tile Computing," Lecture Notes in Computer Science, 7495, 2012, pp. 544-553.
  * [9] M. Hwang, M. Garbey, S. A. Berceli and R. Tran-Son-Tay, "Rule-Based Simulation of Multi-Cellular Biological Systems—A Review of Modeling Techniques," Cellular and Molecular Bioengineering, 2(3), 2009, pp. 285-294.
  * [10] G. B. Ermentrout and L. Edelstein-Keshet, "Cellular Automata Approaches to Biological Modelling," Journal of Theoretical Biology, 160, 1993, pp. 97-133.
  * [11] G. Rozenberg , T. Bäck and J. Kok, (editors), Handbook of Natural Computing, Springer, 2012, pp. 1-287, pp. 1168.
  * [12] L. B. Kier, D. Bonchev and G. A. Buck, "Modeling Biochemical Networks: A Cellular-Automata Approach," Chemistry and Biodiversity, 2(2), 2005, pp. 233-243.
  * [13] M. Gardner, "Mathematical Games - The Fantastic Combinations of John Conway’s New Solitaire Game "Life"," Scientific American, 223, 1970, pp. 120-123.
  * [14] J. M. Baetens and B. De Baets, "Towards the Full Lyapunov Spectrum of Cellular Automata," AIP Conference Proceedings, 1389(1), 2011, pp. 981-986.
  * [15] J.M. Baetens and J. Gravner, "Stability of cellular automata trajectories revisited: branching walks and Lyapunov profiles," 2014. [Online]. Available: http://arxiv.org/pdf/1406.5553.pdf.
  * [16] H. Zenil and E. Villareal-Zapata, "Asymptotic Behaviour and Ratios of Complexity in Cellular Automata," International Journal of Bifurcation and Chaos, 23(9), 2013.
  * [17] M. Mitchell, J. P. Crutchfield and P. T. Hraber, "Evolving Cellular Automata to Perform Computations: Mechanisms and Impediments," Physica D: Nonlinear Phenomena, 75(1), 1994, pp. 361-391.
  * [18] M. Mitchell. An Introduction to Genetic Algorithms. MIT press, 1998
  * [19] J. Wurthner, A. Mukhopadhyay, and Claus-Jürgen Peimann. "A cellular automaton model of cellular signal transduction." Computers in biology and medicine 30(1), 2000, pp. 1-21.