# New Bounds on the Size of Permutation Codes With Minimum Kendall
$\tau$-distance of Three

A. Abdollahi  Department of Pure Mathematics, Faculty of Mathematics and
Statistics, University of Isfahan, Isfahan 81746-73441, Iran.  School of
Mathematics, Institute for Research in Fundamental Sciences (IPM), 19395-5746
Tehran, Iran<EMAIL_ADDRESS>,  J. Bagherian  Department of Pure
Mathematics, Faculty of Mathematics and Statistics, University of Isfahan,
Isfahan 81746-73441, Iran<EMAIL_ADDRESS>,  F. Jafari  Department of
Pure Mathematics, Faculty of Mathematics and Statistics, University of
Isfahan, Isfahan 81746-73441, Iran<EMAIL_ADDRESS>,  M. Khatami
Department of Pure Mathematics, Faculty of Mathematics and Statistics,
University of Isfahan, Isfahan 81746-73441, Iran<EMAIL_ADDRESS>,
F. Parvaresh  Department of Electrical Engeenering, University of Isfahan,
Isfahan 81746-73441, Iran.  School of Mathematics, Institute for Research in
Fundamental Sciences (IPM), 19395-5746 Tehran, Iran<EMAIL_ADDRESS>and  R. Sobhani  Department of Applied Mathematics and Computer Science,
Faculty of Mathematics and Statistics, University of Isfahan, Isfahan
81746-73441, Iran<EMAIL_ADDRESS>
###### Abstract.

We study $P(n,3)$, the size of the largest subset of the set of all
permutations $S_{n}$ with minimum Kendall $\tau$-distance $3$. Using a
combination of group theory and integer programming, we reduced the upper
bound of $P(p,3)$ from $(p-1)!-1$ to
$(p-1)!-\lceil\frac{p}{3}\rceil+2\leq(p-1)!-2$ for all primes $p\geq 11$. In
special cases where $n$ is equal to $6,7,11,13,14,15$ and $17$ we reduced the
upper bound of $P(n,3)$ by $3,3,9,11,1,1$ and $4$, respectively.

###### Key words and phrases:

Rank modulation, Kendall $\tau$-distance, permutation codes.

###### 2010 Mathematics Subject Classification:

94B25; 94B65; 68P30

Corresponding Author: A. Abdollahi

F. Parvaresh is supported by in part by grant No. 1401680050.

##  1\. Introduction

Rank modulation was proposed as a solution to the challenges posed by flash
memory storages[8]. In the rank modulation framework, codes are permutation
codes, where by a permutation code (PC) of length $n$ we simply mean a non-
empty subset $\mathcal{C}$ of $S_{n}$, the set of all permutations of
$[n]:=\\{1,2,\ldots,n\\}$. Given a permutation
$\pi:=[\pi(1),\pi(2),\ldots,\pi(i),\pi(i+1),\ldots,\pi(n)]\in S_{n}$, an
adjacent transposition, $(i,i+1)$, for some $1\leq i\leq n-1$, applied to
$\pi$ will result in the permutation
$[\pi(1),\pi(2),\ldots,\pi(i+1),\pi(i),\ldots,\pi(n)]$. For two permutations
$\rho,\pi\in S_{n}$, the Kendall $\tau$-distance between $\rho$ and $\pi$,
$d_{K}(\rho,\pi)$, is defined as the minimum number of adjacent transpositions
needed to transform $\rho$ into $\pi$. Under the Kendall $\tau$-distance a PC
of length $n$ with minimum distance $d$ can correct up to $\frac{d-1}{2}$
errors caused by charge-constrained errors [8].

The maximum size of a PC of length $n$ and minimum Kendall $\tau$-distance $d$
is denoted by $P(n,d)$. Several researchers have presented bounds on $P(n,d)$
(see [1, 2, 8, 10, 11, 12]), some of these results are shown in Table 1. It is
known that $P(n,1)=n!$ and $P(n,2)=\frac{n!}{2}$. Also it is known that if
$\frac{2}{3}\binom{n}{2}<d\leq\binom{n}{2}$, then $P(n,d)=2$ (see [2, Theorem
10]). However, determining $P(n,d)$ turns out to be difficult for
$3<d\leq\frac{2}{3}\binom{n}{2}$. In this paper, we study the upper bound of
$P(n,3)$. By sphere packing bound (see [8, Theorems 17 and 18])
$P(n,3)\leq(n-1)!$. It is proved that if $n>4$ is a prime number or $4\leq
n\leq 10$, then $P(n,3)\neq(n-1)!$ (see [5, Corollary 2.5 and Theorem 2.6] or
[2, Corollary 2]).

$n$ | 6 | 7 | 11 | 13
---|---|---|---|---
LB | 102 [10] | 588 [2] |  $11!/20$ [1] |  $13!/24$ [1]
UB | $5!-1^{a}$ | $6!-1^{a}$ | $10!-1^{a}$ | $12!-1^{a}$
UB | $5!-4$ | $6!-4$ | $10!-10$ | $12!-12$
$n$ | 14 | 15 | 17 | prime $n\geq 19$
LB |  $2\times 12!$ [8] |  $15!/28$ [1] |  $2\times 15!$ [8] |  $2\times(n-2)!$ [8]
UB |  $13!$ [8] |  $14!$ [8] | $16!-1^{a}$ | $(n-1)!-1^{a}$
UB | $13!-1$ | $14!-1$ | $16!-5$ | $(n-1)!-\lceil\frac{n}{3}\rceil+2$
Table 1.  Some results on bounds of $P(n,3)$. The superscripts shows the
references from which the upper bound is taken, where “a” is [2, 5], and gray
color shows our main results.

There are several works which uses optimization techniques to bound the size
of permutation codes under various distance metrics (Hamming, Kendall, Ulam)
(see [6, 9, 10]). In Section II of this paper, we show that for any non-
trivial subgroup of $S_{n}$, we can derive an integer programming where the
optimal value of the objective function gives an upper bound on $P(n,3)$. In
Section III, by considering Young subgroups (see Definition 3.1, below) of
$S_{n}$, we can improve the upper bound of $P(n,3)$ as shown in Table 1.

##  2\. Preliminaries

Let $G$ be a finite group and denote by $\mathbb{C}[G]$ the complex group
algebra of $G$. The elements of $\mathbb{C}[G]$ are of the formal sum

(2.1) $\sum_{g\in G}a_{g}g,$

where $a_{g}\in\mathbb{C}$. The complex group algebra is a
$\mathbb{C}$-algebra with the following addition, multiplication and scaler
product:

$\sum_{g\in G}a_{g}g+\sum_{g\in G}b_{g}g=\sum_{g\in G}(a_{g}+b_{g})\sigma,$
$\big{(}\sum_{g\in G}a_{g}g\big{)}\big{(}\sum_{g\in G}b_{g}g\big{)}=\sum_{g\in
G}\big{(}\sum_{g=g_{1}g_{2}}a_{g_{1}}b_{g_{2}}\big{)}g,$ $\lambda\sum_{g\in
G}a_{g}g=\sum_{g\in G}(\lambda a_{g})g,$

where $\lambda\in\mathbb{C}$ and $\sum_{g\in G}b_{g}g\in\mathbb{C}[G]$. If
$a_{g}=0$ for some $g$, the term $a_{g}g$ will be neglected in 2.1 and
$\sum_{g\in G}a_{g}g$ is written as $a_{1}g_{1}+\cdots+a_{k}g_{k}$, where
$\\{g\;|\;a_{g}\neq 0\\}=\\{g_{1},\dots,g_{k}\\}$ is non-empty and otherwise
$\sum_{g\in G}a_{g}g$ is denoted by $0$.
For a non-empty subset $X$ of $G$, we denote by $\widehat{X}$ the element
$\sum_{x\in X}x$ of $\mathbb{C}[G]$.

Let $G$ be a finite group and $S$ be a non-empty inverse closed subset of $G$
not-containing the identity element $1$ of $G$. Consider the Cayley graph
$\Gamma:=Cay(G,S)$ whose vertices are elements of $G$ and two vertices $g,h$
are adjacent if $gh^{-1}\in S$. Now we have a metric $d_{\Gamma}$ on $G$
defined by $\Gamma$ which is the length of a shortest path between two
vertices in $Cay(G,S)$. For example if $G=S_{n}$ and
$S=\\{(1,2),(2,3),\dots,(n-1,n)\\}$, the metric $d_{\Gamma}$ is the Kendall
$\tau$-metric on $S_{n}$. Also if $G=S_{n}$ and $S=T\cup T^{-1}$, where
$T:=\\{(a,a+1,\ldots,b)\;|\;a<b,a,b\in[n]\\}$, the metric $d_{\Gamma}$ is the
Ulam metric on $S_{n}$.

######  Definition 2.1.

For a positive ineteger $r$ and an element $g\in G$, the ball of radius $r$ in
$G$ under the metric $d_{\Gamma}$ is denoted by $B_{r}^{\Gamma}(g)$ defined by
$B_{r}^{\Gamma}(g)=\\{h\in G\;|\;d_{\Gamma}(g,h)\leq r\\}$.

######  Remark 2.2.

Note that $B_{r}^{\Gamma}{(g)}=(S^{r}\cup\\{1\\})g$, where
$S^{r}:=\\{s_{1}\cdots s_{r}\;|\;s_{1},\dots,s_{r}\in S\\}$. Also note that
since $S$ is inverse closed, $B_{r}^{\Gamma}{(g)}=S^{r}g$ for all $r\geq 2$.
It follows that $|B_{r}^{\Gamma}(g)|=|B_{r}^{\Gamma}(1)|=|S^{r}\cup\\{1\\}|$
for all $g\in G$.

######  Proposition 2.3.

Let $G$ be a finite group and $d_{\Gamma}$ be the metric induced by the metric
$Cay(G,S)$. Then a subset $C$ of $G$ is a code with
$min\\{d_{\Gamma}(x,y)\,|\,x,y\in C\\}\geq 3$ if and only if there exists
$Y\subset G$ such that

(2.2) $\widehat{(S\cup\\{1\\})}\widehat{C}=\widehat{G}-\widehat{Y},$

###### Proof.

Let $Y=G\setminus\cup_{c\in C}B_{1}^{\Gamma}(c)$. So $G=\cup_{c\in
C}B_{1}^{\Gamma}(c)\cup Y$ and hence Remark 2.2 implies
$\widehat{G}=\widehat{(S\cup\\{1\\})C}+\widehat{Y}$. Now the result follows
from the fact that for any two distinct elements $c,c^{\prime}$ in $C$,
$(S\cup\\{1\\})c\cap(S\cup\\{1\\})c^{\prime}=\varnothing$ since otherwise
$d_{\Gamma}(c,c^{\prime})\leq 2$ that is a contradiction. This completes the
proof. ∎

Let $G$ be a finite group and $d_{\Gamma}$ be the metric induced by the metric
$Cay(G,S)$. For a positive integer $r$, an $r$-perfect code or a perfect code
of radius $r$ of $G$ under the metric $d_{\Gamma}$ is a subset $C$ of $G$ such
that $G=\cup_{c\in C}B_{r}^{\Gamma}(c)$ and $B_{r}^{\Gamma}(c)\cap
B_{r}^{\Gamma}(c^{\prime})=\varnothing$ for any two distinct $c,c^{\prime}\in
C$. By a similar argument as the proof of Proposition 2.3, it can be seen that
if $C$ is an $r$-perfect code, then
$\widehat{(S^{r}\cup\\{1\\})}\widehat{C}=\widehat{G}$. We note that according
to Remark 2.2 $C$ is an $r$-perfect code if and only if
$|C||S^{r}\cup\\{1\\}|=|G|$.

Let $\rho$ be any (complex) representation of a finite group $G$ of dimension
$k$ for some positive integer $k$, i.e., any group homomorphism from $G$ to
the general linear group $GL_{k}(\mathbb{C})$ of $k\times k$ invertible
matrices over $\mathbb{C}$. Then by the universal property of $\mathbb{C}[G]$,
$\rho$ can be extended to an algebra homomorphism $\hat{\rho}$ from
$\mathbb{C}[G]$ to the algebra $Mat_{k}(\mathbb{C})$ of $k\times k$ matrices
over $\mathbb{C}$ such that $g^{\hat{\rho}}=g^{\rho}$ for all $g\in G$. Thus
the image of $\widehat{X}$ for any non-empty subset $X$ of $G$ under
$\hat{\rho}$ is the element $\sum_{x\in X}x^{\rho}$ of $Mat_{k}(\mathbb{C})$.
In particular by applying $\hat{\rho}$ on the equality 2.2, we obtain

(2.3) $\big{(}\sum_{s\in S^{r}\cup\\{1\\}}s^{\rho}\big{)}\big{(}\sum_{c\in
C}c^{\rho}\big{)}=\sum_{g\in G}g^{\rho}-\sum_{y\in Y}y^{\rho},$

where the latter equality is between elements of $Mat_{k}(\mathbb{C})$.

######  Remark 2.4.

Given a group $G$ and a non-empty set $X$, recall that we say $G$ acts on $X$
(from the right) if there exists a function $X\times G\rightarrow X$ denoted
by $(x,g)\mapsto x^{g}$ for all $(x,g)\in X\times G$ if $(x^{g})^{h}=x^{gh}$
and $x^{1}=x$ for all $x\in X$ and all $g,h\in G$, where $1$ denotes the
identity element of $G$. For any $x\in G$ The set $Stab_{G}(x):=\\{g\in
G\;|\;x^{g}=x\\}$ is called the stabilizer of $x$ in $G$ which is a subgroup
of $G$. If the action is transitive (i.e., for any two elements $x,y\in X$,
there exists $g\in G$ such that $x^{g}=y$), all stabilizers are conjugate
under the elements of $G$, more precisely $Stab_{G}(x)^{g}=Stab_{G}(y)$
whenever $x^{g}=y$, where $Stab_{G}(x)^{g}=g^{-1}Stab_{G}(x)g$.
Now suppose that $G$ acts on $X$ and $|X|=k$ is finite. Fix an arbitrary
ordering on the elements of $X$ so that $x_{i}<x_{j}$ whenever $i<j$ for
distinct elements $x_{i},x_{j}\in X$. Denote by $\rho_{X}^{G}$ the map from
$G$ to $GL_{k}(\mathbb{Z})$ defined by $g\mapsto P_{g}$, where $P_{g}$ is the
$|X|\times|X|$ matrix whose $(i,j)$ entry is $1$ if $x_{i}^{g}=x_{j}$ and $0$
otherwise. Note that the definitions of $\rho_{X}^{G}$ depends on the choice
of the ordering on $X$, however any two such representations of $G$ are
conjugate by a permutation matrix.

Let $H$ be a subgroup of a finite group $G$ and $X$ be the set of right cosets
of $H$ in $G$, i.e., $X:=\\{Hg\,|\,g\in G\\}$. Then $G$ acts transitively on
$X$ via $(Hg,g_{0})\longrightarrow Hgg_{0}$. We note that, it is known that
$X$ partitions $G$, i.e., $G=\cup_{x\in X}{x}$ and $x\cap
x^{\prime}=\varnothing$ for all distinct elements $x$ and $x^{\prime}$ of $X$,
and $|X|=|G|/|H|$.

######  Lemma 2.5.

Let $H$ be a subgroup of a finite group $G$ and $X=\\{Ha_{1},\ldots,Ha_{m}\\}$
be the set of right cosets of $H$ in $G$. If $\mathcal{Y}\subset G$, then by
fixing the ordering $Ha_{i}<Ha_{j}$ whenever $i<j$, the $(i,j)$ entry of
$\sum_{y\in\mathcal{Y}}y^{\rho_{X}^{G}}$ is
$|\mathcal{Y}\cap{a_{i}}^{-1}Ha_{j}|$.

###### Proof.

Clearly, for any $y\in\mathcal{Y}$, the $(i,j)$ entry of $y^{\rho_{X}^{G}}=1$
if $Ha_{i}y=Ha_{j}$ and $0$ otherwise. So the $(i,j)$ entry of
$y^{\rho_{X}^{G}}=1$ if $a_{i}y{a_{j}}^{-1}\in H$ and therefore
$y\in{a_{i}}^{-1}Ha_{j}$. Hence the $(i,j)$ entry of the
$\sum_{y\in\mathcal{Y}}y^{\rho_{X}^{G}}$ is equal to
$|\\{y\in\mathcal{Y}\,|\,y\in{a_{i}}^{-1}Ha_{j}\\}|$. This completes the
proof. ∎

######  Theorem 2.6.

Let $G$ be a finite group and $d_{\Gamma}$ be the metric induced by the metric
$Cay(G,S)$. Also Let $C$ be a code in $G$ with
$min\\{d_{\Gamma}(c,c^{\prime})\,|\,c,c^{\prime}\in C\\}\geq 3$. If $H$ is a
subgroup of $G$ and $\mathcal{Z}$ is the set of right cosets of $H$ in $G$,
then the optimal value of the objective function of the following integer
programming gives an upper bound on $|C|$

Maximize $\displaystyle\quad\sum_{i=1}^{|\mathcal{Z}|}{x_{i}},$ subject to
$\displaystyle\quad\widehat{(S\cup\\{1\\})^{\rho_{\mathcal{Z}}^{G}}}(x_{1},\ldots,x_{|\mathcal{Z}|})^{T}\leq|H|\mathbf{1},$
$\displaystyle\quad x_{i}\in\mathbb{Z},\,\,x_{i}\geq
0,\,\,i\in\\{1,\ldots,|\mathcal{Z}|\\},$

where 1 is a column vector of order $|\mathcal{Z}|\times 1$ whose entries are
equal to $1$.

###### Proof.

By Proposition 2.3, there exists $Y\subset G$ such that

(2.4) $\big{(}\sum_{s\in
S\cup\\{1\\}}s^{\rho_{\mathcal{Z}}^{G}}\big{)}\big{(}\sum_{c\in
C}c^{\rho_{\mathcal{Z}}^{G}}\big{)}=\sum_{g\in
G}g^{\rho_{\mathcal{Z}}^{G}}-\sum_{y\in Y}y^{\rho_{\mathcal{Z}}^{G}},$

Suppose that $\mathcal{Z}=\\{Ha_{1},\ldots,Ha_{m}\\}$. Without loss of
generality, we may assume that $a_{1}=1$. We fix the ordering $Ha_{i}<Ha_{j}$
whenever $i<j$. By Lemma 2.5, the $(i,j)$ entry of $\sum_{g\in
G}g^{\rho_{\mathcal{Z}}^{G}}$ is equal to $|G\cap{a_{i}}^{-1}Ha_{j}|$ and
since ${a_{i}}^{-1}Ha_{j}\subseteq G$, the $(i,j)$ entry of $\sum_{g\in
G}g^{\rho_{\mathcal{Z}}^{G}}$ is equal to $|{a_{i}}^{-1}Ha_{j}|=|H|$, for all
$i,j\in\\{1,\ldots,|\mathcal{Z}|\\}$. So if $B$ is a column of $\sum_{g\in
G}g^{\rho_{\mathcal{Z}}^{G}}$, then $B=|H|\mathbf{1}$. Let $\mathcal{C}$ be
the first column of $\sum_{c\in C}c^{\rho_{\mathcal{Z}}^{G}}$. Then Lemma 2.5
implies that for all $1\leq i\leq|\mathcal{Z}|$, $i$-th row of $\mathcal{C}$,
denoted by $c_{i}$, is equal to $|C\cap Ha_{i}|$. Since $C=C\cap
G=\cup_{i=1}^{|\mathcal{Z}|}(C\cap Ha_{i})$ and $(C\cap Ha_{i})\cap(C\cap
Ha_{j})=\varnothing$ for all $i\neq j$, $\sum_{i=1}^{|\mathcal{Z}|}c_{i}=|C|$.
We note that by Lemma 2.5, all entries of matrix
$\widehat{F^{\rho_{\mathcal{Z}}^{G}}}$, $F\in\\{C,G,Y,(S\cup\\{1\\})\\}$, are
integer and non-negative. Therefore $\mathcal{C}$ is an integer solution for
the following system of inequalities

$\widehat{(S\cup\\{1\\})^{\rho_{\mathcal{Z}}^{G}}}(x_{1},\ldots,x_{|\mathcal{Z}|})^{T}\leq|H|\mathbf{1}$

such that $\sum_{i=1}^{|\mathcal{Z}|}c_{i}=|C|$ and this completes the proof.
∎

##  3\. Results

Let $G=S_{n}$ and $S=\\{(i,i+1)\,|\,1\leq i\leq n-1\\}$, then the metric
induced by $Cay(G,S)$ on $S_{n}$ is the Kendall $\tau$\- metric. In this
section, by using the result in Section II, we improve the upper bound of
$P(n,3)$ when $n\in\\{6,14,15\\}$ or $n\geq 7$ is a prime number.

Usual traditional with well-developed candidate for $\mathcal{B}$ is the set
of Young tabloids of a given shape which we are going to recall them [7].

######  Definition 3.1.

By a number partition $\lambda$ of $n$ (with the length $m$) we mean an
$m$-tuple $(\lambda_{1},\dots,\lambda_{m})$ of positive integers such that
$\lambda_{1}\geq\cdots\geq\lambda_{m}$ and $n=\sum_{i=1}^{m}\lambda_{i}$.
Given a number partition $\lambda$ of $n$, by a Young tabloid of shape
$\lambda$ we mean an $m$-tuple $(\mathfrak{n}_{1},\dots,\mathfrak{n}_{m})$ of
non-empty subsets of $[n]$ consisting a set partition for $[n]$ with
$|\mathfrak{n}_{i}|=\lambda_{i}$ for all $i=1,\dots,m$. We denote by
$\mathcal{YT}_{n}(\lambda)$ the set of all Young tabloids of shape $\lambda$
of $n$. With a Young tabloid
$\mathfrak{n}=(\mathfrak{n}_{1},\dots,\mathfrak{n}_{m})$ of shape $\lambda$,
we associate a Young subgroup $S_{\mathfrak{n}}$ of $S_{n}$ by taking
$S_{\mathfrak{n}}=S_{\mathfrak{n}_{1}}\times\cdots\times
S_{\mathfrak{n}_{m}}$.

######  Remark 3.2.

The action of $S_{n}$ on $\mathcal{YT}_{n}(\lambda)$ is defined by
$(\mathfrak{n}_{1},\dots,\mathfrak{n}_{m})^{\sigma}=(\mathfrak{n}_{1}^{\sigma},\dots,\mathfrak{n}_{m}^{\sigma})$
for all $\sigma\in S_{n}$. Fix an arbitrary ordering of the elements of
$\mathcal{YT}_{n}(\lambda)$. The representation
$\rho_{\mathcal{YT}_{n}(\lambda)}^{S_{n}}$ is equivalent to the representation
$\rho_{X}^{S_{n}}$, where $X$ is the set of right cosets of the Young subgroup
$S_{\mathfrak{n}}$ in $S_{n}$ for some Young tabloid
$\mathfrak{n}=(\mathfrak{n}_{1},\dots,\mathfrak{n}_{m})$ of shape $\lambda$.
Note that if $\mathfrak{n}$ and $\mathfrak{n}^{\prime}$ are two Young tabloids
of the same shape $\lambda$, the corresponding Young subgroups are conjugate
in $S_{n}$ and so the representations $\rho_{X}^{S_{n}}$ and
$\rho_{X^{\prime}}^{S_{n}}$, where $X$ and $X^{\prime}$ are the set of right
cosets of Young subgroups $S_{\mathfrak{n}}$ and $S_{\mathfrak{n}^{\prime}}$
in $S_{n}$, respectively, are equivalent (i.e., a matrix $U$ exists such that
$U^{-1}\rho_{X}^{S_{n}}(\sigma)U=\rho_{X^{\prime}}^{S_{n}}(\sigma)$ for all
$\sigma\in S_{n}$) so that we use Young tabloid
$[\\{1,\ldots,\lambda_{1}\\},\\{\lambda_{1}+1,\ldots,\lambda_{1}+\lambda_{2}\\},\ldots,\\{n-\lambda_{m}+1,\ldots,n\\}]$
for considering Young subgroup corresponding to the partition
$\lambda=(\lambda_{1},\ldots,\lambda_{m})$, as we are studying these
representations up to equivalence.

######  Lemma 3.3.

Let $H$ be Young subgroup of $S_{n}$ corresponding to the partition
$\lambda:=(n-1,1)$ and $X$ be the set of right cosets of $H$ in $S_{n}$. If
$S=\\{(i,i+1)\,|\,1\leq i\leq n-1\\}$, then
$\widehat{(S\cup\\{1\\})^{\rho_{X}^{S_{n}}}}$ is a conjugate by a permutation
matrix of the following matrix

$\begin{pmatrix}n-1&1&0&0&\dots&0\\\ 1&n-2&1&0&\dots&0\\\ 0&1&n-2&1&0&0\\\
\vdots&\dots&\ddots&\ddots&\ddots&\vdots\\\ 0&0&\dots&1&n-2&1\\\
0&0&\dots&0&1&n-1\end{pmatrix}.$

###### Proof.

Let $T:=S\cup\\{1\\}$. Without loss of generality we may assume that $\lambda$
is the partition $\\{\\{1\\},\\{2,\ldots,n\\}\\}$ of $n$ and therefore
$H=Stab_{S_{n}}(1)$. If $i\neq j$, then $H(1,i)\cap H(1,j)=\varnothing$ since
otherwise $(1,i,j)\in H$ that is a contradiction. So we can let
$X=\\{H(1,i)\,|\,1\leq i\leq n\\}$, where we are using the convention
$H(1,1):=H$. We Fixing the ordering $H(1,i)<H(1,j)$ if $i<j$. By Lemma 2.5,
the $(i,j)$ entry of $\widehat{T^{\rho_{X}^{S_{n}}}}$ is equal to
$|T\cap(1,i)H(1,j)|$. If $i=j$, then Remark 2.4 imply
$(1,i)H(1,i)=Stab_{S_{n}}(i)$ and hence
$T\cap(1,i)H(1,i)=T\setminus\\{(i-1,i),(i,i+1)\\}$ if $2\leq i\leq n-1$,
$T\cap(1,n)H(1,n)=T\setminus\\{(n,n-1)\\}$ and $T\cap
H=T\setminus\\{(1,2)\\}$. Now suppose that $i\neq j$. Clearly
$(1,i)(i,j)(1,j)=(i,j)$. Let $h\in H$. Then $\sigma:=(1,i)h(1,j)=\pi(1,j,i)$,
where $\pi=(1,i)h(1,i)\in Stab_{S_{n}}(i)$. Since $\pi(i)=i$, $\sigma(j)=i$
and therefore $\sigma$ is an transposition if and only if $h=(i,j)$. Hence, if
$j=i+1$ and $i-1$, then $T\cap(1,i)H(1,j)$ is equal to $\\{(i,i+1)\\}$ and
$\\{(i-1,i)\\}$, respectively, and otherwise $T\cap(1,i)H(1,j)=\varnothing$.
This completes the proof. ∎

######  Theorem 3.4.

Let $p\geq 7$ be a prime number and consider the $p\times p$ matrix

$M=\begin{pmatrix}p-1&1&0&0&\dots&0\\\ 1&p-2&1&0&\dots&0\\\ 0&1&p-2&1&0&0\\\
\vdots&\dots&\ddots&\ddots&\ddots&\vdots\\\ 0&0&\dots&1&p-2&1\\\
0&0&\dots&0&1&p-1\end{pmatrix}.$

Consider the system of inequalities $M{\mathbf{x}}\leq(p-1)!\mathbf{1}$ with
$\mathbf{x}\geq\mathbf{0}$ and $x_{i}$ are integers. Let
$x_{\max}:=\max\\{x_{i}\;|\;i=1,\dots,p\\}$. Then

  1. (1)

$|\\{i\in[p]\;|\;x_{i}\leq\frac{(p-1)!}{p}\\}|\geq\lceil\frac{p}{3}\rceil$.

  2. (2)

If $\sum_{i=1}^{p}x_{i}=(p-1)!-k$, then $|\\{i\;|\;x_{i}=x_{\max}\\}|\geq
p-k-2$.

  3. (3)

$\sum_{i=1}^{p}x_{i}\leq(p-1)!-\lceil\frac{p}{3}\rceil+2$

###### Proof.

Let $\mathcal{A}:=\\{i\in[p]\;|\;x_{i}\leq\frac{(p-1)!}{p}\\}$ and
$\mathcal{B}:=\\{i\;|\;x_{i}=x_{\max}\\}$. Consider the partition
$\\{\\{1,2\\},\\{3,4,5\\},\\{6,7,8\\},\dots,\\{p-2,p-1,p\\}\\}$ of $[p]$ if
$p\equiv 2\mod 3$ and the partition
$\\{\\{1,2\\},\\{3,4,5\\},\\{6,7,8\\},\dots,\\{p-4,p-3,p-2\\},\\{p-1,p\\}\\}$
if $p\equiv 1\mod 3$. Each member of partitions corresponds to an obvious
inequality, e.g. $\\{1,2\\}$ and $\\{p-2,p-1,p\\}$ are respectively
corresponding to $(p-1)x_{1}+x_{2}\leq(p-1)!$ and
$x_{p-2}+(p-2)x_{p-1}+x_{p}\leq(p-1)!$. Each inequality corresponding to a
member $P$ of partitions forces $x_{i}\leq(p-1)!/p$ for some $i\in P$, where
$x_{i}=\min\\{x_{j}\;|\;j\in P\\}$. Since the size of both partitions is the
same $\lceil\frac{p}{3}\rceil$, $|\mathcal{A}|\geq\lceil\frac{p}{3}\rceil$.

Let $\ell\in[p]$ be such that $x_{\ell}=x_{\max}$. Thus
$\sum_{i=1,i\neq\ell-1,\ell+1}^{p}(x_{\ell}-x_{i})=x_{\ell-1}+(p-2)x_{\ell}+x_{\ell+1}-\sum_{i=1}^{p}x_{i}\leq(p-1)!-((p-1)!-k)$.
Thus $\sum_{i=1,i\neq\ell-1,\ell+1}^{p}(x_{\ell}-x_{i})\in\\{0,1,\dots,k\\}$.
It follows that $|\\{i\;|\;x_{i}<x_{\max}\\}|\leq k+2$ and so
$|\mathcal{B}|\geq p-k-2$.

Let $\sum_{i=1}^{p}x_{i}=(p-1)!-k$ and suppose, for a contradiction, that
$k<\lceil\frac{p}{3}\rceil-2$. So $|\mathcal{B}|\geq
p-\lceil\frac{p}{3}\rceil+1$ and therefore

$|\mathcal{A}\cap\mathcal{B}|\geq|\mathcal{A}|+|\mathcal{B}|-p\geq\lceil\frac{p}{3}\rceil+p-\lceil\frac{p}{3}\rceil+1-p\geq
1.$

Hence $\mathcal{A}\cap\mathcal{B}\neq\varnothing$ and $x_{\max}\leq(p-1)!/p$.
Since $p$ is prime, by Wilson theorem [4, P. 27] $(p-1)!\equiv-1\mod p$. Since
$x_{\max}$ is integer, we have that $x_{i}\leq\frac{(p-1)!+1}{p}-1$ for all
$i\in[p]$. Therefore

$\sum_{i=1}^{p}x_{i}=(p-1)!-k\leq p(\frac{(p-1)!+1}{p}-1)=(p-1)!+1-p$

and so

$p\leq k+1<\lceil\frac{p}{3}\rceil-1,$

which is a contradiction. So we must have $k\geq\lceil\frac{p}{3}\rceil-2$.
This completes the proof. ∎

######  Corollary 3.5.

For all primes $p\geq 11$,
$P(p,3)\leq(p-1)!-\lceil\frac{p}{3}\rceil+2\leq(p-1)!-2$.

###### Proof.

The result follows from Theorems 2.6, 3.4 and Lemma 3.3. ∎

######  Theorem 3.6.

If $n$ is equal to $6$, $7$, $11$, $13$ and $17$, then $P(n,3)$ is less than
or equal to $116$, $716$, $10!-10$, $12!-12$ and $16!-5$, respectively.

###### Proof.

Let $S:=\\{(i,i+1)\,|\,1\leq i\leq n-1\\}$. In view of Theorem 2.6, we have
used a CPLEX software [3] to determine the upper bound for $P(n,3)$ obtained
from solving the integer programming corresponding to the subgroup $H$ of
$S_{n}$, where $H$ is the Young subgroup corresponding to the partition
$(2,2,2)$, when $n=6$, $(5,1,1)$, when $n=7$, $(9,2)$, when $n=11$, $(11,2)$,
when $n=13$ and $(16,1)$, when $n=17$. ∎

######  Theorem 3.7.

There are no $1$-perfect codes under the Kendall $\tau$-distance in $S_{n}$
when $n\in\\{14,15\\}$.

###### Proof.

Let $S=\\{(i,i+1)\,|\,1\leq i\leq n-1\\}$ and $T:=S\cup\\{1\\}$. We are using
techniques in [5] for proving this theorem. By [5, Theorem 2.2], if $S_{n}$
contains a subgroup $H$ such that $n\nmid|H|$ and
$\widehat{(T)^{\rho_{X}^{S_{n}}}}$ is invertible, where $X$ is the set of
right cosets of $H$ in $S_{n}$, then $S_{n}$ contains no $1$-perfect codes
under the kendall $\tau$-distance. In the case $n=14$, we consider Young
subgroup $H$ corresponding to the partition $(6,6,2)$. By a software check the
matrix $\widehat{(T)^{\rho_{X}^{S_{14}}}}$ is invertible.
In the case $n=15$, we consider Young subgroup $H$ corresponding to the
partition $(4,4,4,3)$ in $S_{15}$. By [7, Corollary 2.2.22], if for all
$\lambda\in\\{(15),(14,1),(13,2),(13,1,1),(12,3),(12,2,1),(11,4),(8,7),\\\
(10,5),(11,2,2),(9,6),(11,3,1),(7,7,1),(5,5,5),(10,4,1),\\\
(10,3,2),(9,5,1),(8,6,1),(9,3,3),(9,2,2,2),(6,6,3),(9,4,2),\\\
(4,4,4,3),(7,6,2),(7,4,4),(6,5,4),(8,5,2),(8,4,3),(7,5,3),\\\
(6,3,3,3),(8,3,2,2),(5,4,4,2),(7,3,3,2),(5,5,3,2),(6,5,2,2),\\\
(7,4,2,2),(6,4,3,2)\\}$, $\widehat{T^{\rho_{\lambda}}}$ is invertible, where
$\rho_{\lambda}$ is the irreducible representation of $S_{15}$ corresponding
to $\lambda$, then $\widehat{T^{\rho_{X}^{S_{15}}}}$ is invertible. By
software check all these matrices are invertible. This completes the proof. ∎

######  Conjecture 3.8.

If $H$ is the Young subgroup corresponding to the partition $(p-1,p-1,2)$ of
$S_{2p}$, where $p\geq 3$ is a prime number, and $X$ is the set of right
cosets of $H$ in $S_{2p}$, then $\widehat{(S\cup\\{1\\})^{\rho_{X}^{S_{2p}}}}$
is invertible. In particular, there is no $1$-perfect permutation code of
length $2p$ with respect to the Kendall $\tau$-distance.

##  4\. Conclusion

Due to the applications of PCs under the Kendall $\tau$-distance in flash
memories, they have attracted the attention of many researchers. In this
paper, we consider the upper bound of the size of the largest PC with minimum
Kendall $\tau$-distance 3. Using Group theory, corresponding to any non-
trivial subgroup of $S_{n}$, we formulate an integer programming where the
optimal value of the objective function gives an upper bound on $P(n,3)$.
After that, by solving the integer programming corresponding to some subgroups
of $S_{n}$, when $n\geq 7$ is a prime number or $n\in\\{6,14,15\\}$, we can
improve the upper bound on $P(n,3)$.

## References

  * [1] A. Barg and A. Mazumdar, Codes in permutations and error correction for rank modulation, IEEE Trans. Inform. Theory, 56 (2010), No. 7, 3158-3165.
  * [2] S. Buzaglo and T. Etzion, Bounds on the size of permutation codes with the Kendall $\tau$-metric, IEEE Trans. Inform. Theory, 61 (2015), No. 6, 3241-3250.
  * [3] The CPLEX Group, Version 12.10, (2019) www.ibm.com/products/ilog-cplex-optimization-studio.
  * [4] U. Dudley, A Guide to Elementary Number Theory, The Dolciani Mathematical Expositions, 41. MAA Guides, 5. Mathematical Association of America, Washington, DC, 2009.
  * [5] P. H. Edelman and D. White, Codes, transforms and the spectrum of the symmetric group, Pacific J. Math., 143 (1990), 47-67.
  * [6] F. Göloǧlu, J. Lember, A.-E. Riet, and V. Skachek, New bounds for permutation codes in Ulam metric, in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2015, pp. 1726-1730.
  * [7] G. James and A. Kerber, The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, 16, Addison-Wesley Publishing Co., Reading, Mass., 1981.
  * [8] A. Jiang, R. Mateescu, M. Schwartz, and J. Bruck, Rank modulation for flash memories, IEEE Trans. Inform. Theory, 55 (2009), 2659-2673.
  * [9] H. Tarnanen, Upper bounds on permutation codes via linear programming, Eur. J. Combinat., 20 (1999), 101-114.
  * [10] S. Vijayakumaran, Largest permutation codes with the Kendall $\tau$-metric in $S_{5}$ and $S_{6}$, IEEE Comm. Letters, 20 (2016), No. 10, 1912-1915.
  * [11] X. Wang, Y. Zhang, Y. Yang and G. Ge, New bounds of permutation codes under Hamming metric and Kendall’s $\tau$-metric, Des. Codes Cryptogr., 85 (2017), No. 3, 533-545.
  * [12] X. Wang, Y. Wang, W. Yin and F-W. Fu, Nonexistence of perfect permutation codes under the Kendall $\tau$-metric, Des. Codes Cryptogr., 89 (2021), No. 11, 2511-2531.


# On the regular sum-free sets⋆

Zhi-xiong Wen  ,  Jie-meng Zhang  and  Wen Wu† School of Mathematics and
Statistics, Huazhong University of Science and Technology, Wuhan 430074, P.R.
China<EMAIL_ADDRESS>(Z.-X. Wen<EMAIL_ADDRESS>(J.-M.
Zhang) Department of Mathematics, Hubei University, Wuhan 430062, P.R. China
<EMAIL_ADDRESS><EMAIL_ADDRESS>(W. Wu)

###### Abstract.

Cameron introduced a bijection between the set of sum-free sets and the set of
all zero-one sequences. In this paper, we study the sum-free sets of natural
numbers corresponding to certain zero-one sequences which contain the Cantor-
like sequences and some substitution sequences, etc. Those sum-free sets
considered as integer sequences are $2$-regular. We also prove that sequences
corresponding to certain sum-free sets are automatic.

###### Key words and phrases:

Sum-free set, $k$-regular sequence, Cantor-like sequence, Thue-Morse sequence,
Automatic sequence

###### 2010 Mathematics Subject Classification:

11B75, 11B85

$\star$ This work is supported by NSFC (Grant Nos. 11401188,11371156).
$\dagger$ Wen Wu is the corresponding author. _E-mail_<EMAIL_ADDRESS>
##  1\. Introduction

A set of integers, denoted by $S$, is called a _sum-free set_ if
$S\cap(S+S)=\emptyset$, where $S+S$ denotes the set of pairwise sums, i.e.,
$S+S=\\{x+y:x,y\in S\\}$. Thus, for any sum-free set $S$, there do not exist
$x,y,z\in S$ for which $x+y=z$. It is natural to arrange the elements of a
sum-free set $S$ in ascending order, so $S=(S_{n})_{n\geq 0}$ can also be
treated as an integer sequence.

Cameron and Erdős [11, 12] studied the number of sum-free sets which are
contained in the first $n$ integers. They showed that the number of sum-free
subsets of $\\{\frac{n}{3},\frac{n}{3}+1,\cdots,n\\}$ is $O(2^{\frac{n}{2}})$.
Calkin [4] showed that the Hausdorff dimension of the sum-free sets is at most
$0.599$. Calkin [5] proved that the number of the sum-free subsets of
$\\{1,2,\cdots,n\\}$ is $\emph{o}(2^{n(1/2+\epsilon)})$ for every
$\epsilon>0$. Łuczak and Schoen [15] studied the properties of $k$-sum-free
sets with precise upper density.

There are several methods to construct infinite sum-free sets. One of them is
to construct such a set directly using its definition; that is, to construct
it from numbers which are not the sum of two earlier numbers. Another way is
to construct the sum-free set from an infinite zero-one sequence. This method
was introduced by Cameron. Cameron [9] defined a natural bijection between
$\Sigma$ and $\mathfrak{S}$, where $\Sigma$ and $\mathfrak{S}$ denote the set
of all zero-one sequences and the set of all sum-free sets respectively.

###  1.1. The bijection between $\Sigma$ and $\mathfrak{S}$.

Let $S\in\mathfrak{S}$ be a sum-free set and $\mathbf{v}$ be a ternary
sequence defined as follow:

$v_{n}=\left\\{\begin{array}[]{ll}1,&\hbox{if $n\in S$;}\\\ \ast,&\hbox{if
$n\in S+S$;}\\\ 0,&\hbox{otherwise.}\end{array}\right.$ (1.1)

By deleting all the $\ast$’s in $\mathbf{v}$, we obtain a unique zero-one
sequence $\mathbf{v}^{\prime}$. This process introduces a mapping from
$\mathfrak{S}$ to $\Sigma$. Calkin [6] showed that this mapping is a bijection
and denoted its inverse by $\theta$. Thus $\theta:\mathbf{v}^{\prime}\mapsto
S$ is a bijection from $\Sigma$ to $\mathfrak{S}$.

Since there is a one-to-one correspondence between the set of zero-one
sequences and the set of sum-free sets (of positive integers), one would like
to know the connection between these two.

###  1.2. Periodicity of $S$

A sum-free set $S$ is said to be _ultimately periodic_ if there exist positive
integers $m,n_{0}$ such that for all $n>n_{0}$, $n\in S$ if and only if
$n+m\in S$. If $n_{0}=0$, then $S$ is _periodic_. It is not easy to show
whether a given sum-free set is periodic or not.

In [10], Cameron observed that if a sum-free set is (ultimately) periodic, the
corresponding zero-one sequence is also (ultimately) periodic. This was proved
by Calkin and Finch in [6]. Conversely, Cameron [6] also asked whether sum-
free sets corresponding to (ultimately) periodic zero-one sequences are
(ultimately) periodic or not. This question is still open. With the help of a
computer, Calkin and Finch [6] presented some sum-free sets, which correspond
to periodic zero-one sequences, and appear to be aperiodic (aperiodicity
checked up to $10^{7}$). There is no proof to show whether such sum-free sets
are periodic or aperiodic. Calkin and Erdős [7] showed that a class of
aperiodic sum-free sets $S$ is incomplete, i.e., $\mathbb{N}\backslash(S+S)$
is an infinite set. Later, Calkin, Finch and Flowers [8] introduced the
concept of difference density which can be used to test whether specific sets
are periodic or not. These tests produced further evidence that certain sets
are not ultimately periodic. Payne [16] studied the properties of some sum-
free sets over an additive group.

###  1.3. Main results.

Motivated by Cameron’s question, in this paper, we will investigate the
regularity of $S$. We would like to know what kind of zero-one sequences will
lead to $k$-regular sum-free sets?

######  Definition 1.

A sum-free set $S$ is called a _$k$ -regular sum-free set_ if the sequence
$(S_{n})_{n\geq 0}$ is $k$-regular111For the definition of $k$-regular
sequences, refer to Definition 3 in Section 2. for some $k\in\mathbb{N}$.

Let $\mathbf{c}=c_{0}c_{1}c_{2}\cdots$ be a zero-one sequence with $c_{0}=1$.
Let $\mu_{n}$ denote the number of zeros between the $n$-th and the $(n+1)$-th
ones in $\mathbf{c}$. An equivalent definition of $\mu_{n}$ is in Definition
2. The sum-free set corresponding to $\mathbf{c}$ is denoted by $S$. Our
results are stated as follows:

Main results I. _Suppose the integer sequence $(\mu_{n})_{n\geq 1}$ is
$2$-regular and satisfies the conditions_

$\left\\{\begin{array}[]{l}\mu_{2^{m}}>\sum_{i=1}^{2^{m}-1}\mu_{i}+2^{m}+\frac{3^{m}-1}{2},\\\
\mu_{2^{m}+k}=\mu_{k},\quad\forall~{}0<k<2^{m},\end{array}\right.$ (1.2)

_for all $m\geq 1$, then $S$ is a $2$-regular sum-free set._

For any fixed $l_{1}\geq 0,~{}l_{2}\geq 0$ and $l_{3}\geq 3$, let
$\sigma(l_{1},l_{2},l_{3})$ be a substitution over the alphabet $\\{0,1\\}$
given by

$1\mapsto 1\overbrace{0\cdots 0}^{l_{1}}1\overbrace{0\cdots 0}^{l_{2}},\quad\
\ \ 0\mapsto\overbrace{0\cdots 0}^{l_{3}}.$ (1.3)

The sequence

$\displaystyle\mathbf{c}_{l_{1},l_{2},l_{3}}$ $\displaystyle=$
$\displaystyle\sigma(l_{1},l_{2},l_{3})^{\infty}(1)$ (1.4) $\displaystyle=$
$\displaystyle 10\cdots 010\cdots 010\cdots 01\cdots$

is called a _Cantor-like sequence._ In particular, $\mathbf{c}_{1,0,3}$ is the
Cantor sequence. In the rest of this paper, since $l_{1},l_{2},l_{3}$ are
fixed in the context, we will simply use $\mathbf{c}$ to denote such Cantor-
like sequences. It is worth pointing out that Cantor-like sequences contain a
class of automatic sequences and a class of non-automatic substitution
sequences.

Main results II. _Let_ $\mathbf{c}$_be a Cantor-like sequence satisfying the
assumption in Main results $I$. Then the corresponding sum-free set $S$ modulo
$2$ is the Thue-Morse sequence222The Thue-Morse sequence beginning by $1$ is
the infinite sequence $\mathbf{t}=t_{0}t_{1}\cdots\in\\{0,1\\}^{\mathbb{N}}$
satisfying the following relations: $t_{0}=1,t_{2n}=t_{n},t_{2n+1}=1-t_{n}$.
beginning by $1$ up to a coding._

We also investigate the zero-one sequences corresponding to a class of sum-
free sets generated from the set $(bn+1)_{n\geq 0}$ through base changing
where $b\in\mathbb{N}$ and $b\geq 2$. For example, let
$S=\\{1,3,5,7,\cdots\\}$ where $S_{n}=(2n+1)_{n\geq 0}$. Suppose
$n=\sum_{i=1}^{k}n_{i}\cdot 2^{i-1}$, with$~{}n_{i}\in\\{0,1\\}$ for any
$1\leq i\leq k$, denote $S_{n}^{\prime}:=\sum_{i=1}^{k}n_{i}\cdot 3^{i}+1$.
Then $S^{\prime}=\\{1,4,10,13,28,31,37,40,\cdots\\}$ is also sum-free.
Moreover, the corresponding zero-one sequence of $S^{\prime}$ is the Cantor
sequence (see Remark 6).

Main results III. _Suppose $b\geq 2$, let $S$ be the sum-free set given by
$S_{n}=\sum_{i=1}^{k}n_{i}(2b-1)^{i}+1$ where $n=\sum_{i=1}^{k}n_{i}2^{i-1}$
with $n_{i}\in\\{0,1\\}$ , then $\theta^{-1}(S)$ is an automatic sequence._

This paper is organized as follows. In Section 2, we introduce some
definitions and auxiliary lemmas which are useful in the proof of Theorem 1.
In Section 3, we give the explicit value of the sum-free set $S$ corresponding
to $\mathbf{c}$ and discuss the regularity of $S$. A class of sum-free sets
$S$ corresponding to Cantor-like sequences is investigated in Section 4. In
the last section, we discuss the automaticity of zero-one sequences
corresponding to certain sum-free sets.

##  2\. Preliminary

###  2.1. $m$-complement of nonnegative integers.

For $b\in\mathbb{N}$, let $\Sigma_{b}:=\\{0,1,\cdots,b-1\\}$. Let
$\Sigma_{b}^{k}$ be the set of words of length $k$ over $\Sigma_{b}$ and
$\Sigma_{b}^{\ast}=\bigcup_{k\geq 0}\Sigma_{b}^{k}$. The _$b$ -ary expansion_
of $n$ is denoted by

$(n)_{b}:=\epsilon_{k}\epsilon_{k-1}\cdots\epsilon_{1}\in\Sigma_{b}^{k},$

where $\epsilon_{k}\neq 0$. The _$b$ -ary number_ of
$\mathbf{w}=w_{k}w_{k-1}\cdots w_{1}\in\Sigma_{b}^{k}$ is given by

$[\mathbf{w}]_{b}:=\sum_{i=1}^{k}w_{i}\cdot b^{i-1}.$

For $\mathbf{w}=w_{k}w_{k-1}\cdots w_{1}\in\Sigma_{2}^{k}$, the _complement_
of $\mathbf{w}$ is the word

$\bar{\mathbf{w}}=\bar{w}_{k}\bar{w}_{k-1}\cdots\bar{w}_{1},$

where $\bar{\epsilon}=1-\epsilon$ for any $\epsilon\in\Sigma_{2}$.

Let $m\in\mathbb{N}$ be fixed and
$n=\epsilon_{m}2^{m-1}+\cdots+\epsilon_{1}2^{0}<2^{m}$ with
$\epsilon_{i}\in\Sigma_{2}$. In this case,
$\epsilon_{m}\epsilon_{m-1}\cdots\epsilon_{1}$ is a $2$-ary representation of
$n$ of length $m$ which allows leading zeros, denoted by $(n)_{2,m}$. The _$m$
-complement_ of $n$, denoted by $\bar{n}$, is given by

$\bar{n}=\left[\overline{(n)}_{2,m}\right]_{2}=\bar{\epsilon}_{m}2^{m-1}+\cdots+\bar{\epsilon}_{1}2^{0}.$

For example, when $m=3$, then $\bar{1}=1\cdot 2^{2}+1\cdot 2^{1}+0\cdot
2^{0}=6$, $\bar{3}=2^{2}=4$. We also use notation ‘$0n$’ and ‘$1n$’ in form,
which denote integers of $2$-ary representation
‘$0\epsilon_{m}\epsilon_{m-1}\cdots\epsilon_{1}$’ and
‘$1\epsilon_{m}\epsilon_{m-1}\cdots\epsilon_{1}$’ respectively. In fact,

$0n=n,\quad 1n=2^{m}+n.$

###  2.2. Two auxiliary bijections

Let $(h(i))_{i\geq 1}$ be a strictly increasing positive integer sequence.
Define the mapping $f:\Sigma_{2}^{m}\times\Sigma_{2}^{m}\rightarrow\mathbb{N}$
by

$(x,y)\mapsto f(x,y)=\sum_{i=1}^{m}(x_{i}+y_{i})h(i)+2.$

Let $\sim$ be the equivalence relation on $\Sigma_{2}^{m}\times\Sigma_{2}^{m}$
induced by $f$, i.e.,

$(x,y)\sim(x^{\prime},y^{\prime})\textrm{ if and only if
}f(x,y)=f(x^{\prime},y^{\prime}).$

Denote $\widetilde{\Sigma}^{m}:=(\Sigma_{2}^{m}\times\Sigma_{2}^{m})/{\sim}$
for simplicity. Hence, we have defined an injection

$f:\widetilde{\Sigma}^{m}\rightarrow\mathbb{N}.$

For any $m\geq 0$, define two mappings $\varphi_{m},~{}\psi_{m}$ as follows:
for any $(u,v)\in\widetilde{\Sigma}^{m}$,

$\displaystyle(u,v)$ $\displaystyle\mapsto$
$\displaystyle\varphi_{m}(u,v)=(\bar{u},\bar{v}),$ $\displaystyle(u,v)$
$\displaystyle\mapsto$ $\displaystyle\psi_{m}(u,v)=(0u,1v).$

Notice that

$\displaystyle f\circ\varphi_{m}(u,v)$ $\displaystyle=$ $\displaystyle
f(\bar{u},\bar{v})$ (2.1) $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}(\bar{u}_{i}+\bar{v}_{i})h(i)+2$ $\displaystyle=$
$\displaystyle 2\sum_{i=1}^{m}h(i)-f(u,v)+4,$

and

$f\circ\psi_{m}(u,v)=f(0u,1v)=f(u,v)+h(m+1).$ (2.2)

By (2.1) and (2.2),

$(\bar{u},\bar{v})\sim(\bar{u}^{\prime},\bar{v}^{\prime})\Longleftrightarrow(u,v)\sim(u^{\prime},v^{\prime})\Longleftrightarrow(0u,1v)\sim(0u^{\prime},1v^{\prime}).$

Thus $\varphi_{m}$ and $\psi_{m}$ are well-defined injections.

But these two mappings are not always bijections. Additional conditions are
needed to ensure that. Before this, we need the following notation: for any
$0\leq k<2^{m}$ with $k=\epsilon_{m}2^{m-1}+\cdots+\epsilon_{1}2^{0}$ and
$\epsilon_{i}\in\Sigma_{2}$, denote

$M_{k}:=\sum_{i=1}^{m}\epsilon_{i}h(i)+1,~{}~{}M_{2^{m}+k}:=M_{k}+h(m+1).$
(2.3)

Note that $M_{2^{m}-1}=\sum_{i=1}^{m}h(i)+1$. Moreover, for any $m\geq 0,0\leq
k<2^{m}$, let

$\displaystyle L_{m}$ $\displaystyle:=$
$\displaystyle\\{(u,v)\in\widetilde{\Sigma}^{m}:~{}f(u,v)\leq M_{2^{m}-1}\\},$
$\displaystyle R_{m}$ $\displaystyle:=$
$\displaystyle\\{(u,v)\in\widetilde{\Sigma}^{m}:M_{2^{m}-1}+1<f(u,v)\leq
2M_{2^{m}-1}\\},$ $\displaystyle L(k)$ $\displaystyle:=$
$\displaystyle\\{(u,v)\in\widetilde{\Sigma}^{m}:~{}M_{k}<f(u,v)<M_{k}+K\\},$
$\displaystyle R(k)$ $\displaystyle:=$
$\displaystyle\\{(0u,1v)\in\widetilde{\Sigma}^{m+1}:~{}M_{2^{m}+k}<f(0u,1v)<M_{2^{m}+k}+K\\},$

where $K=\mu_{k}+\alpha_{k}+1$, and $(\mu_{i})_{i\geq
0},~{}(\alpha_{i})_{i\geq 0}$ are positive integer sequences.

######  Lemma 1.

$\varphi_{m}|_{L_{m}}$ is a bijection from $L_{m}$ to $R_{m}$.

###### Proof.

By (2.1), $f(\bar{u},\bar{v})=2M_{2^{m}-1}-f(u,v)+2.$ Hence, if $(u,v)\in
L_{m}$, then

$M_{2^{m}-1}+2\leq f(\bar{u},\bar{v})\leq 2M_{2^{m}-1},$

which implies $\varphi_{m}(u,v)=(\bar{u},\bar{v})\in R_{m}$.

Note that $\varphi_{m}(\bar{u},\bar{v})=(u,v)$. To show $\varphi_{m}$ is a
surjection, we only need to show $(\bar{u},\bar{v})\in L_{m}$ for any
$(u,v)\in R_{m}$. In fact, if $(u,v)\in R_{m}$, then

$f(\bar{u},\bar{v})=2M_{2^{m}-1}-f(u,v)+2<M_{2^{m}-1}+1.$

∎

######  Lemma 2.

For any $0\leq k<2^{m}$, $\psi_{m}|_{L(k)}$ is a bijection from $L(k)$ to
$R(k)$.

###### Proof.

Note that $M_{2^{m}+k}=h(m+1)+M_{k}$. By (2.2), $(u,v)\in L(k)$ if and only if

$M_{2^{m}+k}<f(0u,1v)=f(u,v)+h(m+1)<M_{2^{m}+k}+K.$

Thus $\psi_{m}|_{L(k)}$ is a bijection. ∎

######  Remark 1.

By Lemma 1 and Lemma 2, for $0\leq k<2^{m}$,

$\textrm{Card}~{}L_{m}=\textrm{Card}~{}R_{m},~{}\textrm{Card}~{}L(k)=\textrm{Card}~{}R(k).$

##  3\. Regularity of $S$

Let $\mathbf{w}$ be a zero-one sequence beginning by $1$, and
$S=\theta(\mathbf{w})$ be the corresponding sum-free set. In this section, we
will characterize $S$ using the properties of $S+S$.

###  3.1. Elementary observations of $S$

Now assume that $\mathbf{v}=(v_{n})_{n\geq 0}$ is the sequence generated from
$S$ by (1.1). In fact, $\mathbf{v}$ labels all the natural numbers by $0,1$ or
$*$. And only those integers belonging to $S$ are labeled by $1$. When we just
care about the number of integers labeled by $0$ or $*$, we will use “the
number of $0$’s (or $*$’s)” rather than “the number of integers labeled by
$0$’s (or $*$’s)”. This abuse of language does not cause any ambiguity in the
paper.

######  Definition 2.

For any $n\geq 1$, denote by $\mu_{n}$ (resp. $\alpha_{n}$), the number of
$0$’s (resp. $*$’s) between $S_{n-1}$ and $S_{n}$. In detail,

$\displaystyle\mu_{n}:=\textrm{Card}~{}\\{i\in\mathbb{N}:v_{i}=0,S_{n-1}<i<S_{n}\\};$
$\displaystyle\alpha_{n}:=\textrm{Card}~{}\\{i\in\mathbb{N}:v_{i}=*,S_{n-1}<i<S_{n}\\}.$

######  Remark 2.

$(1)$ For any $n\geq 1$,

$S_{n}-S_{n-1}=\mu_{n}+\alpha_{n}+1.$

Thus to study $S$, we need to study the properties of $(\mu_{n})_{n\geq 1}$
and $(\alpha_{n})_{n\geq 1}$.

$(2)$ Since $\mathbf{v}$ converts to $\mathbf{w}$ by deleting all the $*$’s,
$\mu_{n}$ represents the number of $0$’s between the $n$-th and $(n+1)$-th
‘$1$’ in $\mathbf{w}$, i.e.,

$\mathbf{w}=1\overbrace{0\cdots 0}^{\mu_{1}}1\overbrace{0\cdots
0}^{\mu_{2}}1\overbrace{0\cdots 0}^{\mu_{3}}1\cdots.$

During the proof of Theorem 1, we need the following two notation: for any
$n\geq 1$,

$\displaystyle g(n)$ $\displaystyle:=$ $\displaystyle\mu_{n}+\alpha_{n},$
(3.1) $\displaystyle h(n)$ $\displaystyle:=$
$\displaystyle\left(\sum_{i=1}^{2^{n-1}}g(i)\right)+2^{n-1}.$ (3.2)

Thus $S_{n}=S_{n-1}+g(n)+1$ and $h(n)$ is strictly increasing.

######  Lemma 3.

Suppose $g(2^{k}+i)=g(i)$ for $0\leq k<m,~{}0<i<2^{k}$. Then

$h(m+1)=\sum_{i=1}^{m}h(i)+g(2^{m})+1.$

###### Proof.

By (3.2),

$\displaystyle h(k+1)-h(k)$ $\displaystyle=$
$\displaystyle\left(\sum_{i=1}^{2^{k}}g(i)+2^{k}\right)-h(k)$ $\displaystyle=$
$\displaystyle\left(\sum_{i=1}^{2^{k-1}-1}\big{(}g(i)+g(2^{k-1}+i)\big{)}+g(2^{k-1})+g(2^{k})+2^{k}\right)-h(k)$
$\displaystyle=$ $\displaystyle h(k)+g(2^{k})-g(2^{k-1}).$

Add the last equation up from $k=1$ to $m$. The result follows. ∎

######  Theorem 1.

Let $\mathbf{c}:=1\overbrace{0\cdots 0}^{\mu_{1}}1\overbrace{0\cdots
0}^{\mu_{2}}1\cdots$. Denote its corresponding sum-free set by
$S=(S_{n})_{n\geq 0}$. If the sequence $(\mu_{n})_{n\geq 1}$ satisfies
$(\ref{hm})$, then for every integer $n\geq 1$, we have

  1. (1)

if $n=2^{k}(2j+1)$ for some $k,j\geq 0$, then

$\alpha_{n}=\frac{3^{k}+1}{2};$ (3.3)

  2. (2)

if $(n)_{2}=\epsilon_{m}\epsilon_{m-1}\cdots\epsilon_{1}$, then

$S_{n}=1+\sum_{i=1}^{m}\epsilon_{i}h(i).$

###### Proof of Theorem 1.

We prove this theorem by induction on $n$.
Step1: Since $\alpha_{1}=1,~{}S_{1}=\mu_{1}+3$, the conclusion is true for
$n=1$.
Step2: Assume the result is true for $n<2^{m}$; that is, if $n=2^{k}(2j+1)$,
then $\alpha_{n}=\frac{3^{k}+1}{2}$. Thus
$\alpha_{2^{p}+q}=\alpha_{q},\forall~{}0<q<2^{p},0<p<m$. Moreover, if
$(n)_{2}=\epsilon_{m}\epsilon_{m-1}\cdots\epsilon_{1}$, then
$S_{n}=1+\sum_{i=1}^{m}\epsilon_{i}h(i)$.

Hence, it suffices to show that the result is also true for $2^{m}\leq
n<2^{m+1}$.

Step2.1 Let $n=2^{m}$. By the induction hypothesis and (3.3), we have

$\displaystyle\sum_{i=1}^{2^{m}-1}\alpha_{i}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{2^{m-1}-1}\alpha_{i}+\alpha_{2^{m-1}}+\sum_{i=1}^{2^{m-1}-1}\alpha_{2^{m-1}+i}=2\sum_{i=1}^{2^{m-1}-1}\alpha_{i}+\alpha_{2^{m-1}}$
(3.4) $\displaystyle=$ $\displaystyle
2^{2}\sum_{i=1}^{2^{m-2}-1}\alpha_{i}+2\alpha_{2^{m-2}}+\alpha_{2^{m-1}}\cdots=\sum_{i=1}^{m}2^{i-1}\alpha_{2^{m-i}}$
$\displaystyle=$ $\displaystyle\frac{3^{m}-1}{2}.$

Now we will evaluate $\alpha_{2^{m}}$. By (3.4) and (1.2),

$\displaystyle S_{2^{m}-1}$ $\displaystyle=$ $\displaystyle
S_{0}+\sum_{i=1}^{2^{m}-1}(\mu_{i}+\alpha_{i})+2^{m}-1$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{2^{m}-1}\mu_{i}+2^{m}+\frac{3^{m}-1}{2}<\mu_{2^{m}}.$

Thus for $i,j\leq 2^{m}-1$,

$S_{i}+S_{j}\leq 2S_{2^{m}-1}<S_{2^{m}-1}+\mu_{2^{m}}.$ (3.5)

Thus to evaluate $\alpha_{2^{m}}$, we only need to count the number of
$\ast$’s between $S_{2^{m}-1}$ and $2S_{2^{m}-1}$. It is easy to see that
$S_{0}+S_{2^{m}-1}=S_{2^{m}-1}+1$ is one of such $\ast$’s. Denote

$\displaystyle\widetilde{L}_{m}$ $\displaystyle:=$ $\displaystyle\\{x\in
S+S:S_{0}<x<S_{2^{m}-1}\\},$ $\displaystyle\widetilde{R}_{m}$
$\displaystyle:=$ $\displaystyle\\{x\in S+S:S_{2^{m}-1}+1<x<2S_{2^{m}-1}\\}.$

Then

$\alpha_{2^{m}}=\textrm{Card}~{}\widetilde{R}_{m}+1.$

Since $f$ is an injection and
$\widetilde{L}_{m}=f(L_{m}),~{}\widetilde{R}_{m}=f(R_{m})$, by Lemma 1, we
have

$\textrm{Card}~{}\widetilde{L}_{m}=\textrm{Card}~{}\widetilde{R}_{m}.$

Hence,

$\displaystyle\alpha_{2^{m}}$ $\displaystyle=$
$\displaystyle\textrm{Card}~{}\widetilde{L}_{m}+1$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}2^{m-i}\alpha_{2^{i-1}}+1$ $\displaystyle=$
$\displaystyle\frac{3^{m}+1}{2}.$

Now we will give the expression of $S_{2^{m}}$. By (1.2) and (3.3), for
$0<j<m$ and $0<k<2^{j}$,

$g(2^{j}+k)=\alpha_{2^{j}+k}+\mu_{2^{j}+k}=\alpha_{k}+\mu_{k}=g(k).$

Let $(2^{m})_{2}=1\overbrace{0\cdots
0}^{m}=:\epsilon_{m+1}(2^{m})\epsilon_{m}(2^{m})\cdots\epsilon_{1}(2^{m})$. By
Lemma 3 and the induction assumption, we have

$\displaystyle S_{2^{m}}$ $\displaystyle=$ $\displaystyle
S_{2^{m}-1}+g(2^{m})+1$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{m}h(k)+g(2^{m})+2$ $\displaystyle=$ $\displaystyle
h(m+1)+1$ $\displaystyle=$ $\displaystyle
1+\sum_{k=1}^{m+1}\epsilon_{k}(2^{m})h(k).$

Step2.2: Now we prove the results for $2^{m}<n<2^{m+1}$. Let $n=2^{m}+k$ where
$1\leq k<2^{m}$, and we prove the results by induction on $k$. For $1\leq
k<2^{m}$, assume the result is true for $n<2^{m}+k$. We will prove the results
for $n=2^{m}+k$.

Firstly, we need to determine the value of $S_{2^{m}+k}$. Denote
$\Xi_{2^{m}+k-1}:=\\{x\in S:x\leq S_{2^{m}+k-1}\\}$. Then

$\Xi_{2^{m}+k-1}+\Xi_{2^{m}+k-1}=\mathcal{S}_{1}\cup\mathcal{S}_{2}\cup\mathcal{S}_{3},$

where

$\displaystyle\mathcal{S}_{1}:=$ $\displaystyle\\{S_{i}+S_{j}:$ $\displaystyle
i,j<2^{m}\\},$ $\displaystyle\mathcal{S}_{2}:=$ $\displaystyle\\{S_{i}+S_{j}:$
$\displaystyle i<2^{m},2^{m}\leq j\leq 2^{m}+k-1\\},$
$\displaystyle\mathcal{S}_{3}:=$ $\displaystyle\\{S_{i}+S_{j}:$ $\displaystyle
2^{m}\leq i,j\leq 2^{m}+k-1\\}.$

In fact, if $i,j<2^{m}$, then by (3.5) we have $S_{i}+S_{j}<S_{2^{m}}$. Thus
$\max\mathcal{S}_{1}<S_{2^{m}}$. Note that by the induction hypothesis,
$S_{2^{m}+k-1}=h(m+1)+S_{k-1}$ and $S_{2^{m}}=h(m+1)+1$. Since $(S_{n})_{n\geq
1}$ is strictly increasing, we have for $i,j\geq 2^{m}$,

$\displaystyle S_{i}+S_{j}$ $\displaystyle>$ $\displaystyle S_{k}+S_{2^{m}}-1$
$\displaystyle=$ $\displaystyle(S_{k-1}+\mu_{k}+\alpha_{k}+1)+(h(m+1)+1)-1$
$\displaystyle=$ $\displaystyle S_{2^{m}+k-1}+\mu_{k}+\alpha_{k}+1=:s.$

Therefore $\min\mathcal{S}_{3}>s$. Note that $s=h(m+1)+S_{k}$. Set $K=g(k)+1$,
then $S_{k}=S_{k-1}+K$ and $s=S_{2^{m}+k-1}+K$. Let

$\displaystyle\widetilde{L}(k):=\\{x\in S+S:S_{k-1}<x<S_{k}\\},$
$\displaystyle\widetilde{R}(k):=\\{x\in S+S:S_{2^{m}+k-1}<x<s\\}.$

Clearly $f(L(k))=\widetilde{L}(k)$ and $f(R(k))\subset\widetilde{R}(k)$. Now
we will show that $f(R(k))=\widetilde{R}(k)$. Since $f$ is an injection, by
Lemma 2, we have

$\textrm{Card}~{}\widetilde{R}(k)\geq\textrm{Card}~{}\widetilde{L}(k)=\alpha_{k}.$

Suppose $S_{2^{m}+k}<s$. The way that we construct $S$ from a zero-one
sequence implies that there are $\mu_{k}$ $0$’s, at least $\alpha_{k}$
$\ast$’s and at least one $1$ between $S_{2^{m}+k-1}$ and $s$. However there
are only $g(k)$ integers between $S_{2^{m}+k-1}$ and $s$, which is a
contradiction. Therefore $S_{2^{m}+k}\geq s$. In this case,
$f(R(k))=\widetilde{R}(k)$. Hence

$\textrm{Card}~{}\widetilde{R}(k)=\alpha_{k}.$

And the number $s$ must be labeled by $\ast$ or $1$, i.e., $v_{s}=\ast\textrm{
or }1$. Since $\max\mathcal{S}_{1}<S_{2^{m}}$ and $\min\mathcal{S}_{3}>s$,
then $s\in\mathcal{S}_{2}$ if $v_{s}=\ast$. That is,

$\exists~{}i<2^{m},j\geq 2^{m},\textrm{ s.t., }s=S_{i}+S_{j}.$

Then there exist $i^{\prime},j^{\prime}<2^{m}$ satisfying
$i=0i^{\prime},j=1j^{\prime}$, and

$\displaystyle
s=S_{k}+h(m+1)=S_{i}+S_{j}=S_{i^{\prime}}+S_{j^{\prime}}+h(m+1).$

Thus $S_{k}=S_{i^{\prime}}+S_{j^{\prime}}$ which contradicts the construction
of $S_{k}$.

Therefore $v_{s}=1$ and $s=S_{2^{m}+k}$. Combining this fact with (1.2),
$\alpha_{k}=\alpha_{2^{m}+k}$. The proof is completed. ∎

######  Remark 3.

$(h(n))_{n\geq 1}$ is a numeration system (for detail, refer to [3, Chapter
3]. In fact, by Lemma 3, for any $j\geq 1$, $\sum_{i=1}^{j-1}h(i)<h(j)$.

######  Definition 3 (Allouche and Shallit [1]).

A sequence $(t(n))_{n\geq 0}$ is called _$k$ -regular_ if there exist $m$
subsequences of $n$, say $\\{n_{l}^{(j)}\\}_{l\geq 0}$ $(0\leq j\leq m-1)$,
which satisfy for any $i\geq 0$ and $0\leq b<k^{i}$, the subsequence
$(t(k^{i}n+b))_{n\geq 0}$ is a $\mathbb{Z}$-linear combination of
$t(n_{l}^{(j)})$.

######  Lemma 4 (Allouche and Shallit [1]).

If $(u_{n})_{n\geq 1}$ and $(v_{n})_{n\geq 1}$ are both $k$-regular, then
$(u_{n}+v_{n})_{n\geq 1}$ and $(\sum_{i=1}^{n}u_{i})_{n\geq 1}$ are also
$k$-regular.

######  Theorem 2.

If $(\mu_{n})_{n\geq 1}$ is $2$-regular and (1.2) holds, then the sequence
$(S_{n})_{n\geq 0}$ is $2$-regular.

###### Proof.

Since $(\mu_{n})_{n\geq 1}$ is $2$-regular, by Lemma 4, so is
$(\sum_{i=1}^{n}\mu_{i})_{n\geq 1}$. And (3.3) in Theorem 1 implies that

$\left\\{\begin{array}[]{l}\alpha_{2n}=3\alpha_{n}-1,\\\
\alpha_{2n+1}=1.\end{array}\right.$

Thus $(\alpha_{n})_{n\geq 1}$ is $2$-regular. By Lemma 4,
$(\sum_{i=1}^{n}\alpha_{i})_{n\geq 1}$ is $2$-regular. Note that $(n+1)_{n\geq
1}$ is also $2$-regular, so by Lemma 4,

$S_{n}=\sum_{i=1}^{n}\mu_{i}+\sum_{i=1}^{n}\alpha_{i}+(n+1)$

is $2$-regular. ∎

##  4\. Examples

Let $\Sigma_{2}^{\ast}$ be the set of finite words over alphabet $\\{0,1\\}$.
For any $w\in\Sigma_{2}^{\ast}$, the length of $w$ is denoted by $|w|$. Denote
by $|w|_{0}$ and $|w|_{1}$ the number of $0$’s and $1$’s in $w$ respectively.

The following lemma completely characterizes the gap between two adjacent
$1$’s in the Cantor-like sequence $\mathbf{c}$.

######  Lemma 5.

For any $l_{1}\geq 0,~{}l_{2}\geq 0,~{}l_{3}\geq 3$ and all $n\geq 1$,

$\mu_{n}=\frac{l_{2}(l_{3}^{k}-1)}{l_{3}-1}+l_{1}l_{3}^{k}$ (4.1)

where $n=2^{k}(2j+1)$ for some $k,j\geq 0$.

###### Proof.

Let $\sigma:=\sigma(l_{1},l_{2},l_{3})$. It is easy to see that
$|\sigma^{m}(1)|_{1}=2^{m}$ and
$|\sigma^{m}(0)|=|\sigma^{m}(0)|_{0}=l_{3}^{m}$ for any $m\geq 0$.

Now, we prove this result by induction on $n$. It is clear that
$\mu_{1}=l_{1}$. Assume that the result is true for all $n<2^{m}$; we prove it
for $2^{m}\leq n<2^{m+1}$. Since $\sigma^{\infty}(1)$ begins with
$\sigma^{m+1}(1)$ and $|\sigma^{m+1}(1)|_{1}=2^{m+1}$, in order to evaluate
$\mu_{n}$ for $2^{m}\leq n<2^{m+1}$, we only need to investigate
$\sigma^{m+1}(1)$. Note that $\sigma^{m}(1)$ begins with ‘$1$’ and

$\displaystyle\sigma^{m+1}(1)$ $\displaystyle=$
$\displaystyle\sigma^{m}(\sigma(1))=\sigma^{m}(1\overbrace{0\cdots
0}^{l_{1}}1\overbrace{0\cdots 0}^{l_{2}})$ (4.2) $\displaystyle=$
$\displaystyle\sigma^{m}(1)\overbrace{\sigma^{m}(0)\cdots\sigma^{m}(0)}^{l_{1}}\sigma^{m}(1)\overbrace{\sigma^{m}(0)\cdots\sigma^{m}(0)}^{l_{2}}$
$\displaystyle=$ $\displaystyle\sigma^{m-1}(1\overbrace{0\cdots
0}^{l_{1}}1\overbrace{0\cdots
0}^{l_{2}})\overbrace{\sigma^{m}(0)\cdots\sigma^{m}(0)}^{l_{1}}\sigma^{m}(1)\overbrace{\sigma^{m}(0)\cdots\sigma^{m}(0)}^{l_{2}}$
$\displaystyle=$
$\displaystyle\sigma^{m-1}(1)\overbrace{\sigma^{m-1}(0)\cdots\sigma^{m-1}(0)}^{l_{1}}\sigma^{m-1}(1)\overbrace{\sigma^{m-1}(0)\cdots\sigma^{m-1}(0)}^{l_{2}}$
$\displaystyle\overbrace{\sigma^{m}(0)\cdots\sigma^{m}(0)}^{l_{1}}\sigma^{m}(1)\overbrace{\sigma^{m}(0)\cdots\sigma^{m}(0)}^{l_{2}};$

then we have

$\mu_{2^{m}}=\sum_{i=0}^{m-1}l_{2}l_{3}^{i}+l_{1}l_{3}^{m}=\frac{l_{2}(l_{3}^{m}-1)}{l_{3}-1}+l_{1}l_{3}^{m}.$
(4.3)

From (4.2) and the fact $|\sigma^{m+1}(1)|_{1}=2^{m+1}$, we know that the
block of consecutive zeros between $n$-th and $(n+1)$-th ‘1’ will appear in
the second $\sigma^{m}(1)$ of $\sigma^{m+1}(1)$ and for all $0<i<2^{m}$,

$\mu_{2^{m}+i}=\mu_{i}.$ (4.4)

Since for any $i=2^{k}(2j+1)$ where $0<k<m$, we have
$2^{m}+i=2^{k}(2j^{\prime}+1)$. Equation (4.4) implies that for all
$0<i<2^{m}$,

$\mu_{2^{m}+i}=\mu_{i}=\frac{l_{2}(l_{3}^{k}-1)}{l_{3}-1}+l_{1}l_{3}^{k}.$
(4.5)

Therefore the result follows from (4.3) and (4.5). ∎

######  Theorem 3.

Let $\mathbf{c}$ be the Cantor-like sequence satisfying $7l_{3}\geq
4(l_{1}+l_{2})+17$ and $l_{1}(l_{3}-1)+l_{2}>3$ , and $S$ be the sum-free set
corresponding to $\mathbf{c}$. Then the sequence $(S_{n})_{n\geq 0}$ is
$2$-regular.

###### Proof.

According to Theorem 2, we only need to show that the gap sequence
$(\mu_{n})_{n\geq 1}$ of $\mathbf{c}$ is $2$-regular and satisfies (1.2). By
Lemma 5, we have

$\left\\{\begin{array}[]{l}\mu_{2n}=l_{3}\mu_{n}+l_{2},\\\
\mu_{2n+1}=l_{1},\end{array}\right.$ (4.6)

which implies $(\mu_{n})_{n\geq 1}$ is $2$-regular.

Now we will show that $(\mu_{n})_{n\geq 1}$ satisfies (1.2). By (4.6), for all
$m\geq 1$,

$\displaystyle\sum_{i=1}^{2^{m}-1}\mu_{i}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{2^{m-1}-1}\mu_{2i+1}+\sum_{i=1}^{2^{m-1}-1}\mu_{2i}$
$\displaystyle=$ $\displaystyle
2^{m-1}l_{1}+l_{3}\sum_{i=1}^{2^{m-1}-1}\mu_{i}+(2^{m-1}-1)l_{2}.$

Thus

$l_{3}\sum_{i=1}^{2^{m-1}-1}\mu_{i}=\sum_{i=1}^{2^{m}-1}\mu_{i}-2^{m-1}(l_{1}+l_{2})+l_{2}.$
(4.7)

By (4.4), we know that $(\mu_{n})_{n\geq 1}$ satisfies the second equation of
(1.2). We will show the first equation of (1.2) by induction. Since
$\mu_{2}=l_{3}l_{1}+l_{2}>l_{1}+3=\mu_{1}+2+\frac{3-1}{2}$, the first equation
of (1.2) holds. Now suppose
$\mu_{2^{m}}>\sum_{i=1}^{2^{m}-1}\mu_{i}+2^{m}+\frac{3^{m}-1}{2}$. Then by
(4.6) and (4.7), we have

$\displaystyle\mu_{2^{m+1}}$ $\displaystyle=$ $\displaystyle
l_{3}\mu_{2^{m}}+l_{2}$ (4.8) $\displaystyle\geq$ $\displaystyle
l_{3}(\sum_{i=1}^{2^{m}-1}\mu_{i}+2^{m}+\frac{3^{m}-1}{2}+1)+l_{2}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{2^{m+1}-1}\mu_{i}-2^{m}(l_{1}+l_{2})+l_{3}(2^{m}+\frac{3^{m}+1}{2})+2l_{2}.$

Since $7l_{3}\geq 4(l_{1}+l_{2})+17$, we have $l_{3}-l_{1}-l_{2}\geq
2-\frac{3(l_{3}-3)}{4}$. Then

$\displaystyle 2^{m}(l_{3}-l_{1}-l_{2})+l_{3}\frac{3^{m}+1}{2}$ (4.9)
$\displaystyle>$ $\displaystyle
2^{m}\left(2-\frac{3(l_{3}-3)}{4}\right)+l_{3}\frac{3^{m}}{2}$
$\displaystyle\geq$ $\displaystyle
2^{m+1}+3^{m}\left(\frac{l_{3}}{2}-\frac{3}{4}\left(\frac{2}{3}\right)^{m}(l_{3}-3)\right)$
$\displaystyle\geq$ $\displaystyle
2^{m+1}+3^{m}\left(\frac{l_{3}}{2}-\frac{1}{2}(l_{3}-3)\right)=2^{m+1}+\frac{3^{m+1}}{2}.$

By (4.8) and (4.9), we know that $(\mu_{n})_{n\geq 1}$ satisfies (1.2). ∎

In the following, we give two examples to illustrate Theorem 3. Example 1
gives a sum-free set corresponding to a zero-one sequence generated by a
substitution of constant length. Example 2 gives a sum-free set corresponding
to a sequence generated by a substitution of non-constant length.

######  Example 1.

Take $\sigma:=\sigma(3,0,5)$, that is, $\sigma:~{}1\rightarrow
10001,~{}0\rightarrow 00000$. The sum-free set corresponding to
$\sigma^{\infty}(1)=100010000000000000001000100000\cdots$ is

$S=\\{1,6,24,29,110,115,133,138,528,533,551,556,637,642,660,665,\cdots\\}.$

According to Theorem 3, $S$ is $2$-regular.

######  Example 2.

Take $\sigma:=\sigma(1,1,5)$, that is $\sigma:~{}1\rightarrow
1010,~{}0\rightarrow 00000$. The sum-free set corresponding to

$\sigma^{\infty}(1)=10100000010100000000000000000000000000000001010101000000\cdots$

is

$S=\\{1,3,15,17,69,71,83,85,333,337,349,353,415,417,431,435,\cdots\\}.$

According to Theorem 3, $S$ is $2$-regular.

From Theorem 3, we have the following two results. In the following, the
symbol $\equiv$ means equality modulo $2$.

######  Corollary 1.

Let $(S_{n})_{n\geq 0}$ be the sum-free set in Theorem 3. For $0\leq j\leq 3$,
the subsequence $(S_{4n+j})_{n\geq 0}$ is either periodic or the Thue-Morse
sequence up to a coding.

###### Proof.

Recall that by (3.4), we have

$\sum_{i=1}^{2^{n}-1}\alpha_{i}=\frac{3^{n}-1}{2}.$

Using (4.7) several times, we have

$\displaystyle\sum_{i=1}^{2^{n}-1}\mu_{i}$ $\displaystyle=$ $\displaystyle
l_{3}\sum_{i=1}^{2^{n-1}-1}\mu_{i}+[2^{n-1}(l_{1}+l_{2})-l_{2}]$
$\displaystyle=$ $\displaystyle
l_{3}^{2}\sum_{i=1}^{2^{n-2}-1}\mu_{i}+l_{3}[2^{n-2}(l_{1}+l_{2})-l_{2}]+[2^{n-1}(l_{1}+l_{2})-l_{2}]$
$\displaystyle=$ $\displaystyle\cdots$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}l_{3}^{i-1}[2^{n-i}(l_{1}+l_{2})-l_{2}]$
$\displaystyle=$
$\displaystyle\frac{l_{1}+l_{2}}{l_{3}-2}(l_{3}^{n}-2^{n})-l_{2}\frac{l_{3}^{n}-1}{l_{3}-1}.$

By (3.3), (4.1) and the previous two equations, we have

$\displaystyle\sum_{i=1}^{2^{n-1}}(\mu_{i}+\alpha_{i})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{2^{n-1}-1}(\mu_{i}+\alpha_{i})+\mu_{2^{n-1}}+\alpha_{2^{n-1}}$
$\displaystyle=$
$\displaystyle\frac{l_{1}+l_{2}}{l_{3}-2}(l_{3}^{n-1}-2^{n-1})-l_{2}\frac{l_{3}^{n-1}-1}{l_{3}-1}+\frac{3^{n-1}-1}{2}$
$\displaystyle+(\mu_{2^{n-1}}+\alpha_{2^{n-1}})$ $\displaystyle=$
$\displaystyle\frac{(l_{1}+l_{2})(l_{3}^{n-1}-2^{n-1})}{l_{3}-2}+l_{1}l_{3}^{n-1}+3^{n-1}.$

Now by (3.2), we obtain

$\displaystyle h(n)$ $\displaystyle=$
$\displaystyle\left(\sum_{i=1}^{2^{n-1}}(\mu_{i}+\alpha_{i})\right)+2^{n-1}$
(4.10) $\displaystyle=$
$\displaystyle\frac{(l_{1}+l_{2})(l_{3}^{n-1}-2^{n-1})}{l_{3}-2}+l_{1}l_{3}^{n-1}+3^{n-1}+2^{n-1}.$

Since
$\frac{l_{3}^{n-1}-2^{n-1}}{l_{3}-2}=\sum_{i=0}^{n-2}l_{3}^{i}2^{n-2-i}\equiv
l_{3}$ ($n\geq 3$), then

$\displaystyle h(n)$ $\displaystyle\equiv$
$\displaystyle\frac{(l_{1}+l_{2})(l_{3}^{n-1}-2^{n-1})}{l_{3}-2}+l_{1}l_{3}+1$
$\displaystyle\equiv$ $\displaystyle(l_{1}+l_{2})l_{3}+l_{1}l_{3}+1$
$\displaystyle\equiv$ $\displaystyle 1+l_{2}l_{3}.$

Let $(j)_{2}:=j_{2}j_{1}$ where $0\leq j\leq 3$. Then

$\displaystyle S_{4n+j}$ $\displaystyle=$ $\displaystyle
1+\sum_{i=1}^{m}\epsilon_{i}h(i+2)+j_{2}h(2)+j_{1}h(1)$ (4.11)
$\displaystyle\equiv$ $\displaystyle
1+(1+l_{2}l_{3})t_{n}+j_{2}h(2)+j_{1}h(1),$

where $t_{n}$ is the $n$-th term of the Thue-Morse sequence. By (4.11), when
$1+l_{2}l_{3}\equiv 0$, $(S_{4n+j})_{n\geq 0}$ modulo $2$ is a constant
sequence. When $1+l_{2}l_{3}\equiv 1$, $(S_{4n+j})_{n\geq 0}$ modulo $2$ is
the Thue-Morse sequence up to a coding. ∎

######  Example 3.

According to Corollary 1, the sum-free set $S$ (modulo $2$) in Example 1 is
the Thue-Morse sequence beginning by $1$. For the sum-free set $S$ in Example
2, the subsequences $(S_{2n})_{n\geq 0}$ and $(S_{2n+1})_{n\geq 0}$ modulo $2$
are both the Thue-Morse sequence beginning by $1$.

######  Corollary 2.

Let $S$ be the sum-free set corresponding to the sequences of Cantor type
(i.e., the fixed point of $\sigma(l,0,l+2)\ (l\geq 2)$ beginning by $1$).

  1. (1)

When $l$ is odd, then $(S_{n})_{n\geq 0}$ modulo $2$ is the Thue-Morse
sequence $(1-t_{n})_{n\geq 0}$.

  2. (2)

When $l$ is even, then $(S_{2n})_{n\geq 0}\equiv(S_{2n+1})_{n\geq 0}$ modulo
$2$, and they are both the Thue-Morse sequence $(1-t_{n})_{n\geq 0}$.

###### Proof.

In this case, $l_{1}=l,l_{2}=0$ and $l_{3}=l+2$. Thus by (4.10),
$h(1)=l+2\equiv l$ and

$h(n)=l^{2}+3l+3^{n-1}\equiv 1,\ \ \ \forall~{}n>1.$

When $l\equiv 1$, by (4.11),

$\displaystyle S_{4n+j}$ $\displaystyle\equiv$ $\displaystyle
1+t_{n}+j_{2}+j_{1}$ $\displaystyle\equiv$ $\displaystyle
1+(\sum_{i=1}^{m}\epsilon_{i}+j_{2}+j_{1})$ $\displaystyle\equiv$
$\displaystyle 1+t_{4n+j}.$

Thus for any $n\geq 0$, $S_{n}\equiv 1+t_{n}.$

When $l\equiv 0$, for $n\geq 0$ and $j=0,1$,

$\displaystyle S_{2n+j}$ $\displaystyle=$ $\displaystyle
1+\sum_{i=1}^{m}\epsilon_{i}h(i+1)+jh(1)$ $\displaystyle\equiv$ $\displaystyle
1+\sum_{i=1}^{m}\epsilon_{i}\equiv 1+t_{n}.$

Thus for any $n\geq 0$, $S_{2n}\equiv S_{2n+1}\equiv 1+t_{n}.$ ∎

While $\mu_{n}$ increases fast, the corresponding sum-free set is not
complicated. In fact, we have

######  Proposition 1.

Suppose the sequence $(\mu_{n})_{n\geq 1}$ is increasing and

$\mu_{n+1}>2\sum_{i=1}^{n}\mu_{i}.$ (4.12)

Let $S_{0}=1$. Then for any $n\geq 1$,

$S_{n}=\sum_{i=1}^{n}\mu_{i}+\frac{(n+1)(n+2)}{2}.$

###### Proof.

By Lemma 1, for every $n\geq 1$, we have $\alpha_{n+1}=\alpha_{n}+1$ and

$\alpha_{n}=\alpha_{n-1}+1=\alpha_{n-2}+1+1=\cdots=\alpha_{1}+(n-1)=n,$

since $\alpha_{1}=1$. Hence

$S_{n}=S_{0}+\sum_{i=1}^{n}\mu_{i}+\sum_{i=1}^{n}\alpha_{i}+n=\sum_{i=1}^{n}\mu_{i}+\frac{(n+1)(n+2)}{2}.$

∎

######  Remark 4.

$(1)$ The growth order of $\mu_{n}$ is larger than $O(3^{n}).$ In fact, if
$\mu_{n}=2\sum_{i=1}^{n-1}\mu_{i}$ for any $n\geq 3$, then
$\mu_{n}=3\mu_{n-1}$, and $\mu_{2}=2\mu_{1}$. Hence $\mu_{n}=2\times
3^{n-2}\mu_{1}.$

$(2)$ The coefficient $2$ in $(\ref{munn})$ is not crucial.

######  Remark 5.

Assume $(S_{n})_{n\geq 0}$ is a sequence given by
$S_{n}=1+\sum_{i=1}^{m}\epsilon_{i}h(i)$ where
$(n)_{2}:=\epsilon_{m}\cdots\epsilon_{1}$ and $(h(i))_{i\geq 1}$ is a positive
integer sequence. If $h(i)\equiv 1$ for $i\geq 0$, then $(S_{n})_{n\geq 0}$
modulo $2$ is the Thue-Morse sequence. If $h(i)\equiv 0$ for $i\geq 0$, then
$S_{n}\equiv 1$.

######  Example 4.

Let $h(i)=2^{i}$, then $S$ is sum-free. Moreover, $S=\\{1,3,5,7,9,\cdots\\}$
and it is periodic of period $2$.

######  Example 5.

Let $h(i)=(i+1)!$, then $S$ is sum-free. Moreover,

$S=\\{1,3,7,9,25,27,31,33,\cdots\\}$

and it is periodic of period $4$.

##  5\. Base changing

The mapping $\theta:\Sigma\rightarrow\mathfrak{S}$ is bijective, so it is
natural to study the properties of the corresponding zero-one sequences of
some sum-free sets. In this section, we will show that the corresponding zero-
one sequences of the sum-free sets defined below are automatic.

######  Definition 4.

For any $b\geq 2,~{}n\geq 0$, let $S=(S_{n})_{n\geq 0}$ be the sum-free set
given by $S_{n}=[(n)_{b}1]_{2b-1}$.

######  Definition 5 (Allouche and Shallit [3]).

Let $\mathcal{A}$ be a set of non-negative integers. Then we say that
$\mathcal{A}$ is a $k$_-automatic set_ if its characteristic sequence

$a_{n}=\left\\{\begin{array}[]{ll}1,&\hbox{if $n\in\mathcal{A}$;}\\\
0,&\hbox{otherwise,}\end{array}\right.$

defines a $k$-automatic sequence.

######  Lemma 6.

The set $S$ in Definition 4 is sum-free and $(2b-1)$-automatic.

###### Proof.

By the definition of $S_{n}$, it is clear that for any integer $n\geq 0$,
$(S_{n})_{2b-1}\in\Sigma_{b}^{\ast}1$. Hence, for any integers $m,~{}n\geq 0$,
$(S_{m}+S_{n})_{2b-1}\in\Sigma_{2b-1}^{\ast}2$, which implies that
$S_{m}+S_{n}\not\in S$. Thus, the set $S$ is sum-free.

Let $(a_{n})_{n\geq 0}$ be the characteristic sequence of $S$. Then

$a_{n}=\left\\{\begin{array}[]{ll}1,&\hbox{if
$(n)_{2b-1}\in\Sigma_{b}^{\ast}1$;}\\\ 0,&\hbox{otherwise.}\end{array}\right.$

Thus the sequence $(a_{n})_{n\geq 0}$ can be generated by the
$(2b-1)$-automaton in Figure 1, which implies that the sequence
$(a_{n})_{n\geq 0}$ is $(2b-1)$-automatic.

$q_{0}/0$start$q_{1}/1$$q_{2}/0$1$b,\cdots,2b-2$$0,2,\cdots,b-1$$b,\cdots,2b-2$$0,2,\cdots,b-1$1$0,1,\cdots,2b-2$
Figure 1. Automaton generating the set $(a_{n})_{n\geq 0}$ in Lemma 6.

∎

######  Theorem 4.

The zero-one sequence $\mathbf{c}$ corresponding to the sum-free set $S$ in
Definition 4 is $(2b-1)$-automatic.

###### Proof.

Recall that the zero-one sequence $\mathbf{c}$ is obtained by deleting all the
$\ast$’s of the sequence $\mathbf{v}=(v_{n})_{n\geq 1}$. For any $n\geq 1$, we
claim that

  1. (1)

$v_{n}=1\Leftrightarrow(n)_{2b-1}\in\Sigma_{b}^{\ast}1,$

  2. (2)

$v_{n}=\ast\Leftrightarrow(n)_{2b-1}\in\Sigma_{2b-1}^{\ast}2,$

  3. (3)

$v_{n}=0\Leftrightarrow(n)_{2b-1}\in\Sigma_{2b-1}^{\ast}\backslash(\Sigma_{b}^{\ast}1\cup\Sigma_{2b-1}^{\ast}2).$

The third assertion is an immediate consequence of the first one and the
second one, and the first assertion follows directly from the definitions of
$S$ and $v_{n}$ in (1.1). Therefore it suffices to prove the second assertion.

Since $v_{n}=\ast\Leftrightarrow n\in S+S$, we need to show that

$S+S=(2b-1)\mathbb{N}+2.$ (5.1)

For any $S_{n}\in S$, then $S_{n}=(2b-1)([(n)_{b}]_{2b-1})+1.$ Hence, for any
integer $m,n\geq 1$, we have

$S_{m}+S_{n}=(2b-1)([(m)_{b}]_{2b-1}+[(n)_{b}]_{2b-1})+2\in(2b-1)\mathbb{N}+2.$

Conversely, for any $n\geq 0$, assume $(n)_{2b-1}:=a_{k}a_{k-1}\cdots a_{1}$.
Hence, for any $1\leq i\leq k$, there exist $b_{i},d_{i}\in\Sigma_{b}$ such
that $a_{i}=b_{i}+d_{i}$. Thus, there exist two integers

$\displaystyle n_{1}$ $\displaystyle=$ $\displaystyle[b_{k}b_{k-1}\cdots
b_{1}]_{2b-1},$ $\displaystyle n_{2}$ $\displaystyle=$
$\displaystyle[d_{k}d_{k-1}\cdots d_{1}]_{2b-1},$

such that $n=n_{1}+n_{2}$ and
$(n_{1})_{2b-1},(n_{2})_{2b-1}\in\Sigma_{b}^{\ast}.$ Moreover,

$\displaystyle(2b-1)n+2$ $\displaystyle=$
$\displaystyle((2b-1)n_{1}+1)+((2b-1)n_{2}+1)$ $\displaystyle=$ $\displaystyle
S_{[b_{k}b_{k-1}\cdots b_{1}]_{b}}+S_{[d_{k}d_{k-1}\cdots d_{1}]_{b}}\in S+S.$

This implies (5.1) holds.

Now, we will show that $\mathbf{c}$ is $(2b-1)$-automatic. By (5.1),
$v_{(2b-1)n+2}=\ast$ for $n\geq 0$. Hence, $\mathbf{c}=c_{0}c_{1}\cdots$
satisfies

$\left\\{\begin{array}[]{lll}c_{(2b-2)n}&=&v_{(2b-1)n+1};\\\
c_{(2b-2)n+i}&=&v_{(2b-1)n+i+2},\end{array}\right.$ (5.2)

where $1\leq i\leq 2b-3.$ By Lemma 6, $S$ is $(2b-1)$-automatic. Its
characteristic sequence $(a_{n})_{n\geq 0}$ is a $(2b-1)$-automatic sequence.
By Theorem 6.8.1 in [3], $(a_{(2b-1)n+i})_{n\geq 0}$ is $(2b-1)$-automatic for
$0\leq i\leq 2b-2$. Note that $v_{n}=a_{n}$ for any $n\notin$
$(2b-1)\mathbb{N}+2$, then $(v_{(2b-1)n+i})_{n\geq 0}$ is $(2b-1)$-automatic
for $0\leq i\leq 2b-2$ and $i\neq 2$. Thus $(c_{(2b-2)n+i})_{n\geq 0}$ is
$(2b-1)$-automatic for $0\leq i\leq 2b-3$. By Theorem 6.8.2 in [3],
$\mathbf{c}$ is $(2b-1)$-automatic. ∎

######  Remark 6.

$(1)$ $(2b-1)$ in Theorem 4 cannot be replaced by $p$, where $p>2b-1$, since
there do not exist $x,y\in\mathbb{N}$ such that $S+S=x\mathbb{N}+y$.
$(2)$ From Theorem 4, if $b=2$, then the sequence $\mathbf{c}$ is the Cantor
sequence

$101000101000000000101000101\cdots$

$(3)$ If we replace $S_{n}=[(n)_{b}1]_{2b-1}$ by $S_{n}=[(n)_{b}w]_{2b-1}$
where $w\in\Sigma_{b}^{\ast}$, then the corresponding zero-one sequence is
also automatic.

Acknowledgements  We would like to thank Professor Jacques Peyrière for
introducing us to this topic, and we gratefully acknowledge of his many
helpful suggestions. We would also like to thank the anonymous referee for
many helpful comments.

## References

  * [1] Jean-Paul Allouche and Jeffrey Shallit, _The ring of $k$-regular sequences_, Theoret. Comput. Sci. 98 (1992), 163-197.
  * [2] Jean-Paul Allouche and Jeffrey Shallit, _The ring of $k$-regular sequences, II_, Theoret. Comput. Sci. 307 (2003), 3-29.
  * [3] Jean-Paul Allouche and Jeffrey Shallit, _Automatic sequences, Theory, Applications, Generalizations_ , Cambridge University Press, New York, 2003.
  * [4] Neil J. Calkin, _Sum-free sets and measure spaces_ , PhD thesis, University of Waterloo, 1988.
  * [5] Neil J. Calkin, _On the number of sum-free sets_ , Bull. London Math. Soc. 22 (1990), 141-144.
  * [6] Neil J. Calkin and Steven R. Finch, _Conditions on periodicity for sum-free sets_ , Exp. Math. 5 (2) (1996), 131-137.
  * [7] Neil J. Calkin and Paul Erdős, _On a class of aperiodic sum-free sets_ , Math. Proc. Camb. Phil. Soc. 120 (1996), 1-5.
  * [8] Neil J. Calkin, Steven R. Finch and Timothy B. Flowers, _Difference density and aperiodic sum-free sets_ , Electronic J. Comb. Number Theory, 5 (2) (2005).
  * [9] Peter J. Cameron, _Cyclic automorphisms of a countable graph and random sum-free sets_ , Graphs and Combin. 1 (1985), 129-135.
  * [10] Peter J. Cameron, _Portrait of a typical sum-free set_ , In C. Whitehead, editor, Surveys in Combinatorics 1987, volume 123 of London Mathematical Society Lecture Notes, pages 13-42, Cambridge University Press, 1987.
  * [11] Peter J. Cameron and Paul Erdős, _On the number of sets of integers with various properties_ , In Number theory (R. A. Mollin, ed.), Walter de Gruyter, Berlin, (1990), 61-79.
  * [12] Peter J. Cameron and Paul Erdős, _Notes on sum-free and related sets_ , Recent trends in combinatorics (Mátraháza, 1995), Combin. Probab. Comput. 8 (1999), 95-107.
  * [13] Alan Cobham, _Uniform tag sequences_ , Math. Systems Theory, 6 (1972), 164-192.
  * [14] Richard K. Guy, _Unsolved Problems in Number Theory_ , Springer Verlag, 1980.
  * [15] Tomasz Łuczak and Tomasz Schoen, _On infinite sum-free sets of natural numbers_ , J. Number Theory, 66 (1997), 211-224.
  * [16] Garth Payne, _A solution to a problem of Cameron on sum-free complete sets_ , J. Comb. Theory, Series A, 70 (1995), 305-312.


# Weights for $\pi$-partial characters of $\pi$-separable groups

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

The aim of this paper is to confirm an inequality predicted by Isaacs and
Navarro in 1995, which asserts that for any $\pi^{\prime}$-subgroup $Q$ of a
$\pi$-separable group $G$, the number of $\pi^{\prime}$-weights of $G$ with
$Q$ as the first component always exceeds that of irreducible $\pi$-partial
characters of $G$ with $Q$ as their vertex. We also give some sufficient
condition to guarantee that these two numbers are equal, and thereby
strengthen their main theorem on the $\pi$-version of the Alperin weight
conjecture.

###### Key words and phrases:

weight; vertex; $\pi$-separable group; $\pi$-partial character

##  1\. Introduction

Let $p$ be a prime, and let $G$ be a finite group. Recall that a $p$-weight of
$G$ is a pair $(Q,\tau)$, where $Q$ is a $p$-subgroup of $G$ and
$\tau\in\operatorname{Irr}(\operatorname{\bf N}_{G}(Q)/Q)$ has $p$-defect
zero, i.e., whose degree has the same $p$-part as $|\operatorname{\bf
N}_{G}(Q):Q|$. The Alperin weight conjecture (often abbreviated AWC) asserts
that the number of $G$-conjugacy classes of $p$-weights coincides with the
number of conjugacy classes of $p^{\prime}$-elements of $G$.

The first complete published proof of the AWC for $p$-solvable groups was
given by Isaacs and Navarro [4] in 1995 by introducing many new techniques to
the $\pi$-theory of characters of $\pi$-separable groups for a set $\pi$ of
primes, and in fact, they established a $\pi$-version of this conjecture.
Specifically, they defined a $\pi^{\prime}$-weight of a $\pi$-separable group
$G$ to be an ordered pair $(Q,\tau)$, where $Q$ is a $\pi^{\prime}$-subgroup
of $G$ and $\tau\in\operatorname{Irr}(\operatorname{\bf N}_{G}(Q)/Q)$ has
$p$-defect zero for every prime $p\in\pi^{\prime}$, and then proved the
following result, which appears in [4] as Theorem A and reduces to the
$p$-solvable case of AWC by taking $\pi=p^{\prime}$, the complement of the
prime $p$.

######  Theorem 1.1 (Isaacs-Navarro).

Let $G$ be a $\pi$-separable group, and assume that the Hall $\pi$-complements
of $G$ are nilpotent. Then the number of $G$-conjugacy classes of
$\pi^{\prime}$-weights is equal to the number of conjugacy classes of
$\pi$-elements of $G$.

Furthermore, they defined the vertices for every irreducible $\pi$-partial
character of a $\pi$-separable group $G$, and showed that the set of vertices
for an irreducible $\pi$-partial character of $G$ forms a single conjugacy
class of $\pi^{\prime}$-subgroups of $G$. We will review the relevant
definitions and properties in the next section. Now let $Q$ be a
$\pi^{\prime}$-subgroup of $G$, and write $\operatorname{I_{\pi}}(G|Q)$ for
the set of irreducible $\pi$-partial characters of $G$ with vertex $Q$. It is
easy to show that $|\operatorname{I_{\pi}}(\operatorname{\bf N}_{G}(Q)|Q)|$ is
exactly the number of $\pi^{\prime}$-weights of $G$ with first component $Q$;
see Lemma 6.28 of [3] or Lemma 2.4 below. Using the notion of vertices, Isaacs
and Navarro obtained a strengthened version of Theorem 1.1, and they also
weakened the nilpotency condition on $Q$; see Theorem C and Theorem 6.3 of
[4].

######  Theorem 1.2 (Isaacs-Navarro).

Let $G$ be $\pi$-separable, and let $Q\leq G$ be a solvable
$\pi^{\prime}$-subgroup with the property that whenever $Q\leq X<Y\leq G$,
where $Y$ is a $\pi^{\prime}$-subgroup, we have $X<\operatorname{\bf
N}_{Y}(X)$. Then
$|\operatorname{I_{\pi}}(G|Q)|=|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)|Q)|$.

The main purpose of this paper is to confirm an inequality predicted by Isaacs
and Navarro at the end of [4], which asserts that for any
$\pi^{\prime}$-subgroup $Q$ of a $\pi$-separable group $G$, the number of
$\pi^{\prime}$-weights of $G$ with $Q$ as the first component always exceeds
that of irreducible $\pi$-partial characters of $G$ with $Q$ as their vertex
or, equivalently, that $|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)|Q)|\geq|\operatorname{I_{\pi}}(G|Q)|$.

######  Theorem A.

Let $G$ be a $\pi$-separable group, and let $Q$ be a $\pi^{\prime}$-subgroup
of $G$. Then

$|\operatorname{I_{\pi}}(G|Q)|\leq|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)|Q)|.$

Our proof of Theorem A was inspired by the techniques developed by Navarro and
Sambale in [7]. Actually, they explored nilpotent $\pi^{\prime}$-weights in
$\pi$-separable groups and gave a generalization of Theorem 1.1.

Using the same argument as in the proof of Theorem A, we obtain a strong form
of Theorem 1.2.

######  Theorem B.

Let $G$ be a $\pi$-separable group, and suppose that $Q\leq G$ is a
$\pi^{\prime}$-subgroup with the property that $Q<\operatorname{\bf N}_{X}(Q)$
for every $\pi^{\prime}$-subgroup $X$ of $G$ that properly contains $Q$. Then

$|\operatorname{I_{\pi}}(G|Q)|=|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)|Q)|.$

The following is an immediate consequence of Theorem B in which
$\operatorname{X}_{\pi}(G)$ denotes the set of $\pi$-special characters of $G$
(for the definition, see Section 2 below).

######  Corollary C.

Let $G$ be a $\pi$-separable group and let $Q$ be a Hall $\pi$-complement of
$G$. Then

  1. (a)

$|\operatorname{I_{\pi}}(G|Q)|=|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)|Q)|$, and

  2. (b)

$|\operatorname{X}_{\pi}(G)|=|\operatorname{Irr}(\operatorname{\bf
N}_{G}(Q)/Q)|$.

We mention that part (b) in the above corollary is a deep result due to Wolf,
which appears in [9] as Corollary 1.16.

All groups considered in this paper are finite, and the notation and
terminology are mostly taken from Isaacs’ books [1] and [3].

##  2\. Preliminaries

In this section, we will review some necessary materials and most of them are
taken from [3].

###  2.1. $\pi$-Partial characters and vertices

Let $G$ be a $\pi$-separable group for a set $\pi$ of primes, and let $G^{0}$
be the set of $\pi$-elements of $G$. For any complex character $\chi$ of $G$,
we say that the restriction $\chi^{0}$ of $\chi$ on $G^{0}$ is a $\pi$-partial
character of $G$. If a $\pi$-partial character $\varphi$ of $G$ cannot be
written as a sum of two $\pi$-partial characters of $G$, then we say that
$\varphi$ is an irreducible $\pi$-partial character of $G$. We use
$\operatorname{I_{\pi}}(G)$ to denote the set of irreducible $\pi$-partial
characters of $G$. Note that if $\pi=p^{\prime}$, the complement of a single
prime $p$, then $\operatorname{I_{\pi}}(G)=\operatorname{IBr}_{p}(G)$ by the
Fong-Swan theorem for $p$-solvable groups, and if $\pi$ is the set of all
primes, then $\operatorname{I_{\pi}}(G)=\operatorname{Irr}(G)$.

Recall that an irreducible complex character $\chi\in\operatorname{Irr}(G)$ is
$\pi$-special if $\chi(1)$ is a $\pi$-number and the determinantal order
$o(\theta)$ is a $\pi$-number, where $\theta$ is any irreducible constituent
of $\chi_{S}$ for every subnormal subgroup $S$ of $G$. Denote by
$\operatorname{X}_{\pi}(G)$ for the set of all $\pi$-special characters of
$G$.

The following is essential in the study of $\pi$-partial characters.

######  Lemma 2.1 ([3, Theorem 3.14]).

Let $G$ be $\pi$-separable. Then the map $\chi\mapsto\chi^{0}$ defines a
bijection from $\operatorname{X}_{\pi}(G)$ onto the set of those irreducible
$\pi$-partial characters of $G$ whose degree is a $\pi$-number.

Now let $Q$ be a $\pi^{\prime}$-subgroup of $G$. We say that $Q$ is a vertex
for an irreducible $\pi$-partial character
$\varphi\in\operatorname{I_{\pi}}(G)$ if there exists a subgroup $U$ of $G$
and $\theta\in\operatorname{I_{\pi}}(U)$, such that $\varphi=\theta^{G}$,
$\theta(1)$ is a $\pi$-number and $Q$ is a Hall $\pi^{\prime}$-subgroup of
$U$. As mentioned in the introduction, we write $\operatorname{I_{\pi}}(G|Q)$
for the set of irreducible $\pi$-partial characters of $G$ with vertex $Q$.

######  Lemma 2.2 ([3, Corollary 5.18]).

Let $G$ be $\pi$-separable and let $\varphi\in\operatorname{I_{\pi}}(G)$. If
$\varphi\in\operatorname{I_{\pi}}(G|Q)$, then
$\varphi(1)_{\pi^{\prime}}|Q|=|G|_{\pi^{\prime}}$. In particular, if $Q$ is a
Hall $\pi^{\prime}$-subgroup of $G$, then
$\varphi\in\operatorname{I_{\pi}}(G|Q)$ if and only if $\varphi(1)$ is a
$\pi$-number.

Also, we say that $\chi\in\operatorname{Irr}(G)$ has $\pi^{\prime}$-defect
zero if $\chi(1)_{\pi^{\prime}}=|G|_{\pi^{\prime}}$ or equivalently, if $\chi$
has $p$-defect zero for every $p\in\pi^{\prime}$. Write $\operatorname{dz}(G)$
for the set of irreducible complex characters of $G$ having
$\pi^{\prime}$-defect zero, so a pair $(Q,\tau)$ is a $\pi^{\prime}$-weight of
$G$ if $Q$ is a $\pi^{\prime}$-subgroup of $G$ and
$\tau\in\operatorname{dz}(\operatorname{\bf N}_{G}(Q)/Q)$.

We need two basic facts on vertices and weights.

######  Lemma 2.3 ([3, Theorem 5.17]).

Let $G$ be a $\pi$-separable group and let
$\varphi\in\operatorname{I_{\pi}}(G)$. Then all vertices for $\varphi$ is a
single conjugacy class of $\pi^{\prime}$-subgroups of $G$.

######  Lemma 2.4 ([3, Lemma 6.28]).

Let $G$ be a $\pi$-separable group and let $Q$ be a $\pi^{\prime}$-subgroup of
$G$. Then the number of $\pi^{\prime}$-weights of $G$ with first component $Q$
is equal to $|\operatorname{I_{\pi}}(\operatorname{\bf N}_{G}(Q)|Q)|$.
Actually, $\tau\mapsto\tau^{0}$ defines a canonical bijection
$\operatorname{dz}(\operatorname{\bf
N}_{G}(Q)/Q)\to\operatorname{I_{\pi}}(\operatorname{\bf N}_{G}(Q)|Q)$.

###  2.2. The Clifford correspondence for $\pi$-partial characters

Let $K\leq G$ and $\theta\in\operatorname{I_{\pi}}(K)$. We say that
$\varphi\in\operatorname{I_{\pi}}(G)$ lies over $\theta$ or equivalently, that
$\theta$ lies under $\varphi$ if $\theta$ is an irreducible constituent of
$\varphi_{K}$. We use $\operatorname{I_{\pi}}(G|\theta)$ to denote the set of
all irreducible $\pi$-partial characters of $G$ lying over $\theta$. It is
natural to define $\theta^{G}$ by the usual formula for induced characters but
applied only to $\pi$-elements of $G$, so that $\theta^{G}$ is also a
$\pi$-partial character of $G$.

Furthermore, if $K\vartriangleleft G$, then
$\theta^{g}\in\operatorname{I_{\pi}}(K)$ for all $g\in G$, where $\theta^{g}$
is defined by $\theta^{g}(x^{g})=\theta(x)$ for $x\in K^{0}$. Then $G$ acts on
the set $\operatorname{I_{\pi}}(K)$ via conjugation, and we write $G_{\theta}$
for the stabilizer of $\theta$ in $G$.

Now we can state the Clifford correspondence for $\pi$-partial characters.

######  Lemma 2.5 ([3, Theorem 5.11]).

Suppose that $\theta\in\operatorname{I_{\pi}}(N)$, where $N\vartriangleleft G$
and $G$ is $\pi$-separable. Then induction $\alpha\mapsto\alpha^{G}$ defines a
bijection
$\operatorname{I_{\pi}}(G_{\theta}|\theta)\to\operatorname{I_{\pi}}(G|\theta)$.
Also, if $\varphi=\alpha^{G}$, then $\alpha$ is the unique irreducible
$\pi$-partial character of $G_{\theta}$ that lies under $\varphi$ and over
$\theta$, and in this case, we often write $\alpha=\varphi_{\theta}$ and call
it the Clifford correspondent of $\varphi$ over $\theta$.

Following Navarro-Sambale [7], we write
$\operatorname{I_{\pi}}(G|Q,\tau)=\operatorname{I_{\pi}}(G|Q)\cap\operatorname{I_{\pi}}(G|\tau)$,
where $Q$ is a $\pi^{\prime}$-subgroup of a $\pi$-separable group $G$ and
$\tau\in\operatorname{I_{\pi}}(N)$ for some $N\vartriangleleft G$.

######  Lemma 2.6 ([3, Lemma 6.33]).

Let $G$ be a $\pi$-separable group and let
$\varphi\in\operatorname{I_{\pi}}(G|Q)$, where $Q$ is a
$\pi^{\prime}$-subgroup of $G$, and let $K\vartriangleleft G$.

  1. (a)

There exists a unique $\mathbf{N}_{G}(Q)$-orbit of some
$\theta\in\operatorname{I_{\pi}}(K)$ such that
$\varphi_{\theta}\in\operatorname{I_{\pi}}(G_{\theta}|Q)$.

  2. (b)

If $\tau\in\operatorname{I_{\pi}}(K)$ is $Q$-invariant and
$G=G_{\tau}\operatorname{\bf N}_{G}(Q)$, then induction of $\pi$-partial
characters defines a bijection
$\operatorname{I_{\pi}}(G_{\tau}|Q,\tau)\to\operatorname{I_{\pi}}(G|Q,\tau)$.

The following corollary tells us how to count the quantity
$|\operatorname{I_{\pi}}(G|Q)|$ “over a normal subgroup”.

######  Corollary 2.7.

Let $G$ be a $\pi$-separable group with $K\vartriangleleft G$, and suppose
that $Q$ is a $\pi^{\prime}$-subgroup of $G$. Let $\mathscr{A}$ be a set of
representatives for the $\operatorname{\bf N}_{G}(Q)$-orbits of $Q$-invariant
members of $\operatorname{I_{\pi}}(K)$. Then

$|\operatorname{I_{\pi}}(G|Q)|=\sum_{\tau\in\mathscr{A}}|\operatorname{I_{\pi}}(G_{\tau}|Q,\tau)|.$

Sometimes we need to work in quotient groups modulo normal
$\pi^{\prime}$-subgroups when studying $\pi$-partial characters and vertices.

######  Lemma 2.8 ([3, Theorem 3.10 and Lemma 5.31]).

Let $G$ be a $\pi$-separable group and let $N\vartriangleleft G$ be a
$\pi^{\prime}$-subgroup. Write $\bar{G}=G/N$. Then

  1. (a)

There is a bijection $\varphi\mapsto\bar{\varphi}$ from
$\operatorname{I_{\pi}}(G)$ onto $\operatorname{I_{\pi}}(\bar{G})$, where
$\bar{\varphi}(\bar{x})=\varphi(x)$ for all $x\in G^{0}$.

  2. (b)

If $\varphi\in\operatorname{I_{\pi}}(G|Q)$, where $Q$ is a
$\pi^{\prime}$-subgroup of $G$, then $N\leq Q$ and
$\bar{\varphi}\in\operatorname{I_{\pi}}(\bar{G}|\bar{Q})$. In particular, we
have ${\bf O}_{\pi^{\prime}}(G)\leq Q$.

######  Lemma 2.9 ([3, Theorem 6.31]).

Let $G$ be a $\pi$-separable group and let $K\vartriangleleft G$ be a
$\pi$-subgroup. Also, let $Q\leq G$ be a $\pi^{\prime}$-subgroup, and let
$L\vartriangleleft G$, where $L\leq Q$. Let $\theta\in\operatorname{Irr}(K)$
be $G$-invariant, and write $\bar{G}=G/L$. Then
$|\operatorname{I_{\pi}}(G|Q,\theta)|=|\operatorname{I_{\pi}}(\bar{G}|\bar{Q},\bar{\theta})|$,
where $\bar{\theta}\in\operatorname{Irr}(\bar{K})$ corresponds to $\theta$ via
the natural isomorphism $K\to KL/L$.

###  2.3. Vertices and character-triple isomorphisms

By a character triple $(G,N,\theta)$, we mean that $G$ is a group,
$N\vartriangleleft G$ and $\theta\in\operatorname{Irr}(N)$ is $G$-invariant.
For the definition and properties of character-triple isomorphisms, see
Chapter 1 of [3] or Chapter 11 of [1].

######  Lemma 2.10 ([3, Lemma 3.11]).

Let $(G,N,\theta)$ be a character triple, where $G$ is a group and $N$ is a
$\pi$-subgroup. Then there exists a character triple
$(G^{*},N^{*},\theta^{*})$ such that $N^{*}\leq\mathbf{Z}(G^{*})$ is also a
$\pi$-subgroup and $(G^{*},N^{*},\theta^{*})$ is isomorphic to $(G,N,\theta)$.

The irreducible $\pi$-partial characters behave very well under the
isomorphism of character triples.

######  Lemma 2.11 ([3, Lemmas 6.21 and 6.32]).

Let $(G,N,\theta)$ and $(G^{*},N^{*},\theta^{*})$ be isomorphic character
triples, where $G$ and $G^{*}$ are $\pi$-separable and $N$ and $N^{*}$ are
$\pi$-groups. Then

  1. (a)

There exists a unique bijection $\varphi\mapsto\varphi^{*}$ from
$\operatorname{I_{\pi}}(G|\theta)$ onto
$\operatorname{I_{\pi}}(G^{*}|\theta^{*})$ such that if $\chi$ is a lift of
$\varphi$ in $\operatorname{Irr}(G|\theta)$ and
$\chi^{*}\in\operatorname{Irr}(G^{*}|\theta^{*})$ corresponds to $\chi$ under
the character-triple isomorphism, then $\chi^{*}$ is a lift of $\varphi^{*}$.
In particular, we have
$\varphi(1)_{\pi^{\prime}}=\varphi^{*}(1)_{\pi^{\prime}}$.

  2. (b)

Let $Q\leq G$ and $Q^{*}\leq G^{*}$ be $\pi^{\prime}$-groups, and assume that
the intermediate subgroups $NQ$ and $N^{*}Q^{*}$ correspond via the character-
triple isomorphism. Then $\varphi\in\operatorname{I_{\pi}}(G|Q,\theta)$ if and
only if $\varphi^{*}\in\operatorname{I_{\pi}}(G^{*}|Q^{*},\theta^{*})$. In
particular, we have
$|\operatorname{I_{\pi}}(G|Q,\theta)|=|\operatorname{I_{\pi}}(G^{*}|Q^{*},\theta^{*})|$.

###  2.4. Above the Glauberman-Isaacs correspondence

The following deep theorem was proved by Dade and Puig in the case where $Q$
is solvable, which is thoroughly explained in [8] as mentioned at the end of
page 2532 of [7]. If $Q$ is not solvable, then it must have even order by the
Feit-Thompson theorem, and thus $K$ has odd order. In this case, Lewis [5]
showed that the result also holds.

######  Lemma 2.12 (Dade-Puig-Lewis).

Let $G$ be an arbitrary group with $K\vartriangleleft G$ and $Q\leq G$, and
assume that $KQ\vartriangleleft G$ and that $(|K|,|Q|)=1$. Let
$\theta\in\operatorname{Irr}(K)$ be $Q$-invariant, and write
$\theta^{*}\in\operatorname{Irr}(\operatorname{\bf C}_{K}(Q))$ for its
Glauberman-Isaacs correspondent. Then $(G_{\theta},K,\theta)$ and
$(\operatorname{\bf N}_{G}(Q)_{\theta^{*}},\operatorname{\bf
C}_{K}(Q),\theta^{*})$ are isomorphic character triples.

###  2.5. Weights and vertices

One of essential ingredients in our proofs of Theorems A and B is Theorem 2.14
below, whose proof relies on the following lemma.

######  Lemma 2.13 ([3, Lemma 6.30]).

Let $K\vartriangleleft G$, where $G$ is $\pi$-separable and $K$ is a
$\pi$-subgroup, and suppose $Q\leq G$ is a $\pi^{\prime}$-subgroup such that
$KQ\vartriangleleft G$. Let $\theta\in\operatorname{Irr}(K)$ be $Q$-invariant
and $\varphi\in\operatorname{I_{\pi}}(G|\theta)$. Then the following hold.

  1. (a)

There exists a vertex $P$ of $\varphi$ such that $Q\leq P\leq\operatorname{\bf
N}_{G}(Q)$. In particular, $Q$ is a vertex for $\varphi$ if and only if
$\varphi(1)_{\pi^{\prime}}=|G:Q|_{\pi^{\prime}}$.

  2. (b)

Furthermore, any two of such vertices $P$ for $\varphi$ are $\operatorname{\bf
N}_{G}(Q)$-conjugate.

######  Theorem 2.14.

Let $K\vartriangleleft G$, where $G$ is $\pi$-separable and $K$ is a
$\pi$-subgroup, and suppose $Q\leq G$ is a $\pi^{\prime}$-subgroup such that
$KQ\vartriangleleft G$. For any $Q$-invariant character
$\tau\in\operatorname{Irr}(K)$, we have

$|\operatorname{I_{\pi}}(G|Q,\tau)|=|\operatorname{I_{\pi}}({\bf
N}_{G}(Q)|Q,\tau^{*})|$

where $\tau^{*}$ is the image of $\tau$ under the Glauberman-Isaacs
correspondence $\operatorname{Irr}_{Q}(K)\to\operatorname{Irr}({\bf
C}_{K}(Q))$.

###### Proof..

By the Frattini argument, we have $G=K{\bf N}_{G}(Q)=G_{\tau}{\bf N}_{G}(Q)$,
and by Lemma 2.6(b), we see that
$|\operatorname{I_{\pi}}(G|Q,\tau)|=|\operatorname{I_{\pi}}(G_{\tau}|Q,\tau)|$.
Also, since ${\bf N}_{G}(Q)_{\tau^{*}}={\bf N}_{G}(Q)_{\tau}$, the same reason
yields

$|\operatorname{I_{\pi}}({\bf
N}_{G}(Q)|Q,\tau^{*})|=|\operatorname{I_{\pi}}({\bf
N}_{G}(Q)_{\tau}|Q,\tau^{*})|=|\operatorname{I_{\pi}}({\bf
N}_{G_{\tau}}(Q)|Q,\tau^{*})|.$

To complete the proof, therefore, we can assume without loss that $\tau$ is
$G$-invariant. Then, by Lemma 2.12, the character triples $(G,K,\tau)$ and
$({\bf N}_{G}(Q),{\bf C}_{K}(Q),\tau^{*})$ are isomorphic, and by Lemma
2.11(a), the map $\varphi\mapsto\varphi^{*}$ defines a bijection
$\operatorname{I_{\pi}}(G|\tau)\to\operatorname{I_{\pi}}({\bf
N}_{G}(Q)|\tau^{*})$ such that
$\varphi(1)_{\pi^{\prime}}=\varphi^{*}(1)_{\pi^{\prime}}$. In this case, Lemma
2.13(a) tells us that $Q$ is a vertex for $\varphi$ if and only if

$\varphi(1)_{\pi^{\prime}}=|G:Q|_{\pi^{\prime}}=|{\bf
N}_{G}(Q):Q|_{\pi^{\prime}},$

and this is equivalent to saying that $\varphi^{*}(1)_{\pi^{\prime}}=|{\bf
N}_{G}(Q):Q|_{\pi^{\prime}}$. Thus
$\varphi\in\operatorname{I_{\pi}}(G|Q,\tau)$ if and only if
$\varphi^{*}\in\operatorname{I_{\pi}}({\bf N}_{G}(Q)|Q,\tau^{*})$, which
implies that the above map $\varphi\mapsto\varphi^{*}$ is also a bijection
from $\operatorname{I_{\pi}}(G|Q,\tau)$ onto $\operatorname{I_{\pi}}({\bf
N}_{G}(Q)|Q,\tau^{*})$, and the result follows. ∎

##  3\. Proof of Theorems A and B

In this section, we will establish Theorems A and B simultaneously from the
introduction. As usual, we need to prove the following “relative version”,
which clearly includes Theorems A and B (by taking $Z=1$).

######  Theorem 3.1.

Let $G$ be a $\pi$-separable group, and let $Q$ be a $\pi^{\prime}$-subgroup
of $G$. Suppose that $Z$ is a normal $\pi$-subgroup of $G$ and that
$\lambda\in\operatorname{Irr}(Z)$ is invariant in $G$. Then the following
hold.

  1. (a)

$|\operatorname{I_{\pi}}(G|Q,\lambda)|\leq|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(QZ)|Q,\lambda)|$.

  2. (b)

Equality holds in (a) if $Q$ has the property that whenever $Q<X$, where $X$
is a $\pi^{\prime}$-subgroup of $G$, then $Q<\operatorname{\bf N}_{X}(Q)$.

###### Proof..

We proceed by induction on $|G:Z|$.

_Step 1. We may assume that $Z\leq{\bf Z}(G)$, so that $\operatorname{\bf
N}_{G}(QZ)=\operatorname{\bf N}_{G}(Q)$._

By Lemma 2.10, we can choose a character triple $(G^{*},Z^{*},\lambda^{*})$
isomorphic to $(G,Z,\lambda)$, where $Z^{*}\leq{\bf Z}(G^{*})$ is a
$\pi$-subgroup. Since $G^{*}/Z^{*}\cong G/Z$ and $G$ is $\pi$-separable, we
see that $G^{*}$ is also $\pi$-separable.

For each $\pi^{\prime}$-subgroup $X$ of $G$, we know that the intermediate
subgroup $XZ$ corresponds to $(XZ)^{*}$ via the isomorphism
$XZ/Z\cong(XZ)^{*}/Z^{*}$, and since $XZ/Z\cong X$ is a $\pi^{\prime}$-group
and $Z^{*}$ is central in $(XZ)^{*}$, there exists a unique
$\pi^{\prime}$-subgroup $X^{*}$ of $G^{*}$ such that $(XZ)^{*}=X^{*}\times
Z^{*}$. It follows that $X\mapsto X^{*}$ defines a surjective map from the set
of $\pi^{\prime}$-subgroups of $G$ onto that of $G^{*}$.

For (a), we conclude by Lemma 2.11(b) that
$|\operatorname{I_{\pi}}(G|Q,\lambda)|=|\operatorname{I_{\pi}}(G^{*}|Q^{*},\lambda^{*})|$
and

$|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(QZ)|Q,\lambda)|=|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G^{*}}(Q^{*}Z^{*})|Q^{*},\lambda^{*})|.$

So, it suffices to prove (a) in $G^{*}$.

For (b), if $Q<X$, then $QZ<XZ$, which implies that
$Q^{*}Z^{*}=(QZ)^{*}<(XZ)^{*}=X^{*}Z^{*}$ and hence $Q^{*}<X^{*}$. Using the
natural isomorphism $X\cong XZ/Z$, it is easy to see that $Q<\operatorname{\bf
N}_{X}(Q)$ if and only if $QZ/Z<\operatorname{\bf N}_{XZ/Z}(QZ/Z)$, and this
is equivalent to saying that

$(QZ)^{*}/Z^{*}<\operatorname{\bf
N}_{(XZ)^{*}/Z^{*}}((QZ)^{*}/Z^{*})=\operatorname{\bf
N}_{X^{*}Z^{*}/Z^{*}}(Q^{*}Z^{*}/Z^{*}),$

which again happens if and only if $Q^{*}<\operatorname{\bf
N}_{X^{*}}(Q^{*})$. So, we may also work in $G^{*}$ to establish (b). To
complete the proof, therefore, we may assume without loss that $Z\leq{\bf
Z}(G)$.

_Step 2. We may assume that ${\bf O}_{\pi^{\prime}}(G)=1$._

Let $L={\bf O}_{\pi^{\prime}}(G)$ and write $\bar{G}=G/L$. Suppose first that
$L\not\leq Q$. Then Lemma 2.8(b) tells us that
$\operatorname{I_{\pi}}(G|Q,\lambda)$ is empty, and (a) follows. For (b), we
need to prove that $\operatorname{I_{\pi}}(N|Q,\lambda)$ is also empty. To do
this, write $N=\operatorname{\bf N}_{G}(Q)$, and since $L\cap N\leq{\bf
O}_{\pi^{\prime}}(N)$, it suffices to show that $L\cap N\not\leq Q$. Note that
$Q<LQ$, and by the assumption on $Q$, we have

$Q<\operatorname{\bf N}_{LQ}(Q)=\operatorname{\bf N}_{L}(Q)Q=(L\cap N)Q$

and thus $L\cap N\not\leq Q$. This proves the theorem in the case where
$L\not\leq Q$.

Now suppose that $L\leq Q$. By Lemma 2.9, we can deduce that

$|\operatorname{I_{\pi}}(G|Q,\lambda)|=|\operatorname{I_{\pi}}(\bar{G}|\bar{Q},\bar{\lambda})|\quad\text{and}\quad|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)|Q,\lambda)|=|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{\bar{G}}(\bar{Q})|\bar{Q},\bar{\lambda})|.$

So, it is no loss to work in $\bar{G}=G/L$, and thus we may assume that $L=1$
(note that $\operatorname{\bf O}_{\pi^{\prime}}(G/L)=1$).

_Step 3. We may assume that $|G:K|<|G:Z|$, where $K=\operatorname{\bf
O}_{\pi}(G)$._

Note that $Z\leq K$, so we need to show that $Z<K$. Suppose that $Z=K$, so
that $K$ is central in $G$ by Step 1. Since $\operatorname{\bf
O}_{\pi^{\prime}}(G)=1$ by Step 2, the Hall-Higman Lemma 1.2.3 (see Theorem
3.21 of [2] for example) implies that $G=\operatorname{\bf C}_{G}(K)\leq K$.
It follows that $G$ is a $\pi$-group, and in this case, the result is trivial.
Thus we may assume that $Z<K$.

_Step 4. Complete the proof._

Let $\mathscr{A}$ be a set of representatives of $\operatorname{\bf
N}_{G}(Q)$-orbits in the set of $Q$-invariant characters in
$\operatorname{Irr}(K|\lambda)$. Since $\lambda$ is $G$-invariant, it follows
by Corollary 2.7 that

$|\operatorname{I_{\pi}}(G|Q,\lambda)|=\sum_{\tau\in\mathscr{A}}|\operatorname{I_{\pi}}(G_{\tau}|Q,\tau)|.$

Furthermore, let $\mathscr{A}^{*}$ be the image of $\mathscr{A}$ under the
Glauberman-Isaacs correspondence from $\operatorname{Irr}_{Q}(K)$ to
$\operatorname{Irr}({\bf C}_{K}(Q))$. Then $\mathscr{A}^{*}$ is clearly a set
of representatives of $\operatorname{\bf N}_{G}(Q)$-orbits in
$\operatorname{Irr}({\bf C}_{K}(Q)|\lambda)$. As before, we have

$|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)|Q,\lambda)|=\sum_{\tau\in\mathscr{A}}|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)_{\tau}|Q,\tau^{*})|.$

Note that $K\operatorname{\bf N}_{G}(Q)_{\tau}=\operatorname{\bf
N}_{G_{\tau}}(KQ)$, and by Theorem 2.14, we have

$|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G_{\tau}}(KQ)|Q,\tau)|=|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)_{\tau}|Q,\tau^{*})|,$

for all $\tau\in\mathscr{A}$. To complete the proof, therefore, it suffices to
show that

$|\operatorname{I_{\pi}}(G_{\tau}|Q,\tau)|\leq|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G_{\tau}}(KQ)|Q,\tau)|$

with equality if $Q$ has the property described in (b). This follows by the
inductive hypothesis applied in $G_{\tau}$ since then $|G_{\tau}:K|<|G:Z|$ by
Step 4, and the proof is complete. ∎

The following is Corollary C in the introduction, which we restate here for
convenience.

######  Corollary 3.2.

Let $G$ be a $\pi$-separable group, and let $Q$ be a Hall $\pi$-complement of
$G$. Then

  1. (a)

$|\operatorname{I_{\pi}}(G|Q)|=|\operatorname{I_{\pi}}(\operatorname{\bf
N}_{G}(Q)|Q)|$ and

  2. (b)

$|\operatorname{X}_{\pi}(G)|=|\operatorname{Irr}(\operatorname{\bf
N}_{G}(Q)/Q)|$.

###### Proof..

(a) is clear by Theorem B. To prove (b), we use Lemmas 2.1 and 2.2 to deduce
that

$|\operatorname{X}_{\pi}(G)|=|\operatorname{I_{\pi}}(G|Q)|\;\text{and}\;|\operatorname{X}_{\pi}(\operatorname{\bf
N}_{G}(Q))|=|\operatorname{I_{\pi}}(\operatorname{\bf N}_{G}(Q)|Q)|,$

and by (a), we obtain
$|\operatorname{X}_{\pi}(G)|=|\operatorname{X}_{\pi}(\operatorname{\bf
N}_{G}(Q))|$. By definition, it is easy to see that all normal
$\pi^{\prime}$-subgroups of a $\pi$-separable group are contained in the
kernel of each $\pi$-special character, and thus we may identify
$\operatorname{X}_{\pi}(\operatorname{\bf N}_{G}(Q))$ with
$\operatorname{X}_{\pi}(\operatorname{\bf N}_{G}(Q)/Q)$. But
$\operatorname{\bf N}_{G}(Q)/Q$ is a $\pi$-group, so all irreducible
characters of $\operatorname{\bf N}_{G}(Q)/Q$ are $\pi$-special, that is,
$\operatorname{Irr}(\operatorname{\bf
N}_{G}(Q)/Q)=\operatorname{X}_{\pi}(\operatorname{\bf N}_{G}(Q)/Q)$. It
follows that
$|\operatorname{X}_{\pi}(G)|=|\operatorname{Irr}(\operatorname{\bf
N}_{G}(Q)/Q)|$, as desired. ∎

## Acknowledgements

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

## References

  * [1] I.M. Isaacs, Character Theory of Finite Groups, Academic Press, New York, 1976.
  * [2] I.M. Isaacs, Finite Group Theory, Amer. Math. Soc., Providence, RI, 2008.
  * [3] I.M. Isaacs, Characters of Solvable Groups, Amer. Math. Soc., Providence, RI, 2018.
  * [4] I.M. Isaacs and G. Navarro, Weights and vertices for characters of $\pi$-separable groups, J. Algebra 177 (1995) 339-366.
  * [5] M. Lewis, Characters, coprime actions, and operator groups. Arch. Math. 69 (1997) 455-460.
  * [6] G. Navarro, Vertices for characters of $p$-solvable groups, Trans. AMS. 365 (2002) 2759-2773.
  * [7] G. Navarro and B. Sambale, Weights and nilpotent subgroups, Int. Math. Res. Not. 2021 (2021) 2526-2538.
  * [8] A. Turull, Above the Glauberman correspondence, Adv. Math. 217 (2008) 2170-2205.
  * [9] T. Wolf, Variations on McKay’s character degree conjecture, J. Algebra 135 (1990) 123-138.