# Hausdorff and box dimension bounds for subfractals induced by $S$-gap shifts

Elizabeth Sattler  Lawrence University, 711 E John St, Appleton, WI 54911
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we consider subsets of an attractor of an iterated function
system in which each point is associated with an allowable word from an
$S$-gap shift. The main result shows that bounds for the box dimension and
Hausdorff dimension of a subfractal induced by an $S$-gap shift are given by
the zeros of the upper and lower topological pressure functions.

###### Key words and phrases:

Hausdorff dimension, box dimension, subfractal, $S$-gap shift

###### 1991 Mathematics Subject Classification:

Primary 28A80; Secondary 37B10

##  1\. Introduction

Symbolic spaces are often used as a tool in fractal geometry. For an iterated
function system (IFS) of the form $\\{K;f_{1},f_{2},\ldots f_{p}\\}$, we
consider the alphabet $\\{1,2,\ldots,p\\}$ and the set of all one-sided
infinite words from the alphabet. Each point in the attractor of the IFS is
associated with an infinite word. In this paper, we will consider subfractals
induced by a specific type of subshift; that is, we only consider points in an
attractor that are associated with allowable words from a subshifts.

Fractal dimension computations for attractors of IFSs exist for several
different types of IFSs: self-similar IFSs [5, 4], non-self-similar attractors
of hyperbolic IFSs [2], and recurrent IFSs with hyperbolic maps [7]. In the
latter two on this list, the authors consider a subset of the full attractor
of the IFS. Expanding on this idea, subfractals induced by subshifts are
introduced in [8]. In that article, computations for bounds on the fractal
dimensions of a subfractal induced by a subshift are produced by modifying
techniques used to compute the entropy of the underlying sofic subshift from
[6]. The proofs rely heavily on the existence of an adjacency matrix for the
subshift, which is only guaranteed for a sofic subshift. For non-sofic
subshifts, there is no unified approach for entropy calculations.

For an IFS $\\{K;f_{1},\ldots,f_{p}\\}$ and a sofic subshift $Y$, let
$\mathcal{F}_{Y}$ denote the attractor consisting only of points associated
with allowable words in $Y$. Assume for each $1\leq i\leq p$ there exist
constants $0<c_{i}\leq\bar{c}_{i}<1$ such that $f_{i}$ satisfies
$c_{i}d(x,y)\leq d(f_{i}(x),f_{i}(y))\leq\bar{c}_{i}d(x,y)$. In both [7] and
[8], a topological pressure function of the form
$P(t)=\lim_{n\to\infty}\frac{1}{n}\log\left(\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\right)$
is used, where $\mathcal{L}_{n}$ denotes the allowable words of length $n$,
and a function $\bar{P}(t)$ is defined similarly using $\bar{c}_{i}$. In [8],
it is shown that Hausdorff and box dimensions of $\mathcal{F}_{Y}$ are bounded
by the zeros of $P(t)$ and $\bar{P}(t)$.

Using a similar approach, we consider subfractals induced by $S$-gap shifts in
this paper. An $S$-gap shift is a subshift on the alphabet
$\mathcal{A}=\\{0,1\\}$ defined by a set $S\subseteq\mathbb{N}_{0}$ where
elements in $S$ describe the allowable number of 0s that can separate two 1s.
Although some $S$-gap shifts are sofic, we cannot guarantee the existence of a
finite graph presentation to help us understand the structure of an $S$-gap
shift. Instead, we consider a decomposition of the language to establish
bounds on the growth rate of finite words. Techniques for decomposing the
language of an $S$-gap shift and finding growth rate bounds are given in [1].

In the main theorem of this article, we prove that similar bounds for the
Hausdorff and box dimension hold for subfractals induced by $S$-gap shifts:

######  Theorem.

Let $h$, $H$ be the unique values such that $P(h)=0=\bar{P}(H)$. Then,

$h\leq\dim_{H}(\mathcal{F}_{X(S)})\leq H$,
$h\leq\underline{\dim}_{B}(\mathcal{F}_{X(S)})\leq H$, and
$h\leq\overline{\dim}_{B}(\mathcal{F}_{X(S)})\leq H$.

Although the assertions are similar, the proofs require a major departure from
those in [7, 8]. The novelty in the proof is the introduction of an auxillary
function, $Q(t)$, that enables us to incorporate structural properties of
$S$-gap shifts in computations involving the topological pressure function. In
section 3, we reveal a clearer connection between the fractal dimension of
such an attractor and the entropy of the underlying shift space. In [9], it is
shown that the entropy of an $S$-gap shift is given by $\log(\lambda^{-1})$,
where $\lambda$ satisfies

$\sum_{s\in S}\lambda^{s+1}=1.$

In this paper, we show that the values of $h$, $H$ for which
$P(h)=0=\bar{P}({H})$ are the same values for which

$\sum_{s\in S}c_{0}^{sh}c_{1}^{h}=1\text{ and }\sum_{s\in
S}\bar{c}_{0}^{sH}\bar{c}_{1}^{H}=1.$

Given a set $S$, this allows us to either compute or estimate $h$ and $H$,
depending on the set $S$. There is no uniform approach to entropy computations
of non-sofic shift spaces; these bounds provide a technique for fractal
dimension computations for subfractals induced by non-sofic $S$-gap shifts,
such as the prime gap shift.

##  2\. Background and definitions

Let $\mathcal{A}=\\{0,1\\}$ and
$X=\\{\omega_{1}\omega_{2}\omega_{3}\ldots\mathrel{\mathop{\mathchar
58\relax}}\omega_{i}\in\mathcal{A}\text{ for all }i\geq 1\\}$ be the compact
metric space of all one-sided infinite words from letters in $\mathcal{A}$
equipped with the metric $d_{X}$ defined by $d_{X}(\omega,\tau)=\frac{1}{k}$,
where $k=\min\\{i\mathrel{\mathop{\mathchar
58\relax}}\omega_{i}\neq\tau_{i}\\}$ . We consider the shift space
$(X,\sigma)$, where the shift map $\sigma\mathrel{\mathop{\mathchar
58\relax}}X\to X$ is defined by
$\sigma(\omega_{1}\omega_{2}\omega_{3}\ldots)=\omega_{2}\omega_{3}\omega_{4}\ldots$.

A subshift is a subset of $X$ that is both $\sigma$-invariant and closed.
There are several classes of well-studied subshifts, such as subshifts of
finite type (SFTs) and sofic subshifts. In this paper, we will focus on
another class of subshifts called $S$-gap shifts. An $S$-gap shift is defined
using a subset $S\subset\mathbb{N}_{0}$. $S$-gap shifts are usually defined as
a subset of double-sided infinite words, where consecutive 1s are separated by
$m$ 0s, where $m\in S$. For our purpose of defining subfractals we will use
one-sided infinite strings, and so an $S$-gap shift, denoted $X_{S}$, will be
defined as the closure of the set

$\\{0^{n}10^{s_{1}}10^{s_{2}}1\ldots\mathrel{\mathop{\mathchar
58\relax}}s_{i}\in S\text{ for all }i\geq 1\text{ and }n\in\mathbb{N}_{0}\\}.$

Here, we are assuming that $S$ is infinite; if $S$ is finite, we restrict the
first block of 0s with $0\leq n\leq\max\\{s\mathrel{\mathop{\mathchar
58\relax}}s\in S\\}$. Sofic shifts include all SFTs; however, many $S$-gap
shifts are not sofic.

To better understand the structure of a subshift and the construction of a
subfractal, we will focus on the allowable finite words in a subshift. Let
$\mathcal{L}_{n}(X)$ denote the collection of all words from $\mathcal{A}$ of
length $n$, and $\mathcal{L}(X)=\bigcup_{n=1}^{\infty}\mathcal{L}_{n}$. We
call $\mathcal{L}(X)$ the language of $X$. Similarly, for a subshift $Y\subset
X$, we will use $\mathcal{L}_{n}(Y)$ to denote the collection of finite words
of length $n$ that appear in some infinite string in $Y$ and $\mathcal{L}(Y)$
will denote the language of $Y$. If the subshift is understood in context, we
will just use $\mathcal{L}_{n}$ and $\mathcal{L}$.

It will be helpful for us to consider special decompositions of a language. We
say a language $\mathcal{L}$ admits a decomposition of the form
$\mathcal{L}=\mathcal{C}^{p}\mathcal{G}\mathcal{C}^{s}$ if every
$\omega\in\mathcal{L}$ can be written as $\omega=\alpha_{1}\gamma\alpha_{2}$
where $\alpha_{1}\in\mathcal{C}^{p}$, $\gamma\in\mathcal{G}$, and
$\alpha_{2}\in\mathcal{C}^{s}$. We can think of $\mathcal{C}^{p}$ and
$\mathcal{C}^{s}$ as prefix and suffix sets respectively, and $\mathcal{G}$ as
a core set.

Let $\mathcal{K}\subset\mathbb{R}^{n}$ be a compact set and let
$\\{\mathcal{K};f_{0},f_{1}\\}$ denote an iterated function system (IFS) with
$f_{i}\colon\mathcal{K}\to\mathcal{K}$ for $i=0,1$. We will assume that the
IFS is hyperbolic, meaning that there exist $0<c_{i}\leq\bar{c_{i}}<1$ such
that

$c_{i}d(x,y)\leq d(f_{i}(x),f_{i}(y))\leq\overline{c_{i}}d(x,y)$

for all $x,y\in\mathcal{K}$ and for $i=0,1$. Let $\mathcal{F}$ denote the
attractor of this hyperbolic IFS. Given this IFS, we consider the alphabet
$\mathcal{A}=\\{0,1\\}$, where $0$ corresponds to $f_{0}$ and $1$ to $f_{1}$.
For a finite word $\omega\in\mathcal{L}_{n}$, we adopt the following
notations:

$\displaystyle f_{\omega}$ $\displaystyle=f_{\omega_{n}}\circ
f_{\omega_{n-1}}\circ\cdots f_{\omega_{1}}$ $\displaystyle c_{\omega}$
$\displaystyle=c_{\omega_{1}}c_{\omega_{2}}\cdots c_{\omega_{n}}$
$\displaystyle\bar{c}_{\omega}$
$\displaystyle=\bar{c}_{\omega_{1}}\bar{c}_{\omega_{2}}\cdots\bar{c}_{\omega_{n}}$

Define the associated coding map $\pi\colon X\to\mathcal{F}$ by
$\pi(\omega)=\lim_{n\to\infty}f_{\omega|_{n}}(\mathcal{K})$, where
$\omega|_{n}=\omega_{1}\omega_{2}\ldots\omega_{n}$. For any IFS of the form
$\\{\mathcal{K};f_{1},\ldots f_{p}\\}$ and a subshift $Y\subset
X=\mathcal{A}^{\mathbb{N}}$, we define a subfractal of $\mathcal{F}$ by only
considering points associated with a word from $Y$. More formally, we define
$\mathcal{F}_{Y}=\\{\pi(\omega)\mathrel{\mathop{\mathchar 58\relax}}\omega\in
Y\\}$. We will assume the IFS satisfies the open set condition (OSC), which
means that there exists an open set $V\subset\mathcal{K}$ such that
$\cup_{i=1}^{p}f_{i}(V)\subset V$, where the union is disjoint.

The main result of this paper involves Hausdorff and box dimensions, which we
define here. Let $\mathcal{K}\subset\mathbb{R}^{n}$ be a compact set,
$E\subset\mathcal{K}$, and $\mathcal{O}$ be the collection of all open
$\varepsilon$-covers of $E$. For $s\geq 0$, if
$\overline{\mathcal{H}}_{\varepsilon}^{s}(E)=\inf_{\mathcal{U}\in\mathcal{O}}\sum_{U\in\mathcal{U}}(\text{diam}(U))^{s}$
then the $s$-dimensional Hausdorff outer measure is defined by
$\mathcal{H}^{s}(E)=\lim_{\varepsilon\to
0}\overline{\mathcal{H}}^{s}_{\varepsilon}(E)$. We restrict the outer measure
to $\overline{\mathcal{H}}^{s}$-measurable sets to define the $s$-dimensional
Hausdorff measure, denoted $\mathcal{H}^{s}$. The Hausdorff dimension of $E$,
denoted $\dim_{H}(E)$ is the unique value of $s$ such that

$\mathcal{H}^{r}(E)=\begin{cases}0,&r>s\\\ \infty,&r<s\end{cases}$

Let $N_{r}(E)$ be the smallest number of sets of diameter $r$ that can cover
$E$. The lower and upper box dimensions of $E$ are defined, respectively, as:

$\underline{\dim}_{B}(E)=\liminf_{r\to 0}\frac{\log N_{r}(E)}{-\log r}\text{
and }\overline{\dim}_{B}(E)=\limsup_{r\to 0}\frac{\log N_{r}(E)}{-\log r}$

The following relationship between the these fractal dimensions are well-known
[4]:

$\dim_{H}(E)\leq\underline{\dim}_{B}(E)\leq\overline{\dim}_{B}(E)$

##  3\. Topological pressure function for subshifts

Topological pressure functions are sometimes considered to be generalizations
of topological entropy. For subshifts, the topological entropy is given by

$h(Y)=\lim_{n\to\infty}\frac{1}{n}\log(\\#\mathcal{L}_{n}(Y)).$

Computations for the topological entropy of SFTs, sofic subshifts, and $S$-gap
shifts are known [6, 9]. Following [7, 8] we define the following topological
pressure function.

######  Definition 3.1.

Let $Y$ be a subshift. The lower topological pressure function of
$\mathcal{F}_{Y}$ is given by
$P(t)=\lim_{n\to\infty}\frac{1}{n}\log\left(\sum_{\omega\in\mathcal{L}_{n}(Y)}c_{\omega}^{t}\right)$.
Similarly, the upper topological pressure is defined by
$\bar{P}(t)=\lim_{n\to\infty}\frac{1}{n}\log\left(\sum_{\omega\in\mathcal{L}_{n}(Y)}\bar{c}_{\omega}^{t}\right)$.

In [8], it is shown that both topological pressure functions are strictly
decreasing, convex, and continuous on $\mathbb{R}$, and there are unique
values $h,H\in[0,\infty)$ such that $P(h)=0=\bar{P}(H)$ where $h\leq H$.
Determining the zeros of a topological pressure function is a difficult
process in general; it will be helpful for us to consider other closely
related functions that will make it easier for us to find values of $h$ and
$H$.

To define these new functions, we will utilize a suitable decomposition of the
language of an $S$-gap shift, which is used in [1]. We define a core set,
prefix set, and suffix set as follows:

$\displaystyle\mathcal{G}$ $\displaystyle=\\{0^{s_{1}}10^{s_{2}}1\ldots
0^{s_{k}}1\mathrel{\mathop{\mathchar 58\relax}}s_{i}\in S\text{ for }1\leq
i\leq k\\}$ $\displaystyle\mathcal{C}^{p}$
$\displaystyle=\\{0^{n}1\mathrel{\mathop{\mathchar 58\relax}}n\notin S\\}$
$\displaystyle\mathcal{C}^{s}$
$\displaystyle=\\{0^{n}\mathrel{\mathop{\mathchar
58\relax}}n\in\mathbb{N}_{0}\\}$

Given an $S$-gap shift $X(S)$, notice that every word in $\mathcal{L}(X(S))$
can be written in the form $0^{m}\omega 0^{n}$ where $m,n\in\mathbb{N}_{0}$
and $\omega\in\mathcal{G}$, and so we can write
$\mathcal{L}(X(S))=\mathcal{C}^{p}\mathcal{G}\mathcal{C}^{s}$. Similar to the
notation for languages, we will use $\mathcal{G}_{n}$, $\mathcal{C}^{p}_{n}$
and $\mathcal{C}^{s}_{n}$ to denote the subsets consisting of words of length
$n$. Note that we have assumed $S$ is infinite; if $S$ is finite, then we
restrict $n$ in both $\mathcal{C}^{p}$ and $\mathcal{C}^{s}$ with
$n\leq\max(S)$.

Using the core set $\mathcal{G}$ defined above, we define two functions:

$Q(t)=\limsup_{n\to\infty}\frac{1}{n}\log\left(\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}\right)\text{
and
}\bar{Q}(t)=\limsup_{n\to\infty}\frac{1}{n}\log\left(\sum_{\omega\in\mathcal{G}_{n}}\bar{c}_{\omega}^{t}\right)$

Our goal is to show that $P(t)=Q(t)$ and $\bar{P}(t)=\bar{Q}(t)$ for $t$
values near the zeros of these functions. We begin by establishing bounds on
$\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}$ and
$\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}$. The techniques are modified
from the ideas used to establish bounds on the growth rates of
$\mathcal{L}_{n}$ and $\mathcal{G}_{n}$ in [1]. All proofs will be presented
using $P(t)$ and $Q(t)$ with constants $c_{i}$, and proofs for the same
results using $\bar{Q}(t)$ and $\bar{P}(t)$ with constants $\bar{c}_{i}$ are
identical.

######  Lemma 3.2.

For any $n\in\mathbb{N}$,

$\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}\leq e^{nP(t)}.$

###### Proof.

First, we notice that $(\mathcal{G}_{n})^{k}\subset\mathcal{L}_{nk}$. Using
this and some algebra, we obtain
$\frac{1}{nk}\log\left(\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}\right)^{k}\leq\frac{1}{nk}\log\left(\sum_{\omega\in\mathcal{L}_{nk}}c_{\omega}^{t}\right)$.
This implies that

$\frac{1}{n}\log\left(\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}\right)\leq\lim_{k\to\infty}\frac{1}{nk}\log\left(\sum_{\omega\in\mathcal{L}_{nk}}c_{\omega}^{t}\right)=P(t),$

and so $\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}\leq e^{nP(t)}$. ∎

######  Lemma 3.3.

For any $n\in\mathbb{N}$ and $t$ in a neighborhood of $h$,

$e^{nP(t)}\leq\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\leq
K_{1}e^{nP(t)},$

where $K_{1}$ is a constant.

###### Proof.

First, using the fact that $\mathcal{L}_{nk}\subset(\mathcal{L}_{n})^{k}$, we
obtain

$\frac{1}{nk}\log\left(\sum_{\omega\in\mathcal{L}_{nk}}c_{\omega}^{t}\right)\leq\frac{1}{nk}\log\left(\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\right)^{k}=\frac{1}{n}\log\left(\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\right).$

Letting $k\to\infty$, we obtain
$P(t)\leq\frac{1}{n}\log\left(\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\right)$,
and so $e^{nP(t)}\leq\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}$.

To find an upper bound, we will work with the language decomposition of
$\mathcal{L}$. Recall that $\mathcal{C}_{n}^{p}=\\{0^{n-1}1\\}$ or $\emptyset$
and $\mathcal{C}_{n}^{s}=\\{0^{n}\\}$. Therefore,
$\sum_{\omega\in\mathcal{C}^{p}_{n}}c_{\omega}^{t}=c_{0}^{(n-1)t}c_{1}^{t}$
when $n-1\notin S$ and
$\sum_{\omega\in\mathcal{C}^{s}_{n}}c_{\omega}^{t}=c_{0}^{nt}$.

Next, recall that $P(t)$ is a continuous function and $P(h)=0$, so there
exists a neighborhood $N_{\alpha}(h)$ such that $\log(c_{0}^{t})<P(t)$ and
$\log(c_{1}^{t})<P(t)$ for $t\in N_{\alpha}(h)$. Therefore, we can find
$\varepsilon>0$ such that both $\log(c_{0}^{t})\leq P(t)-\varepsilon$ and
$\log(c_{1}^{t})\leq P(t)-\varepsilon$. This implies that $c_{0}^{tn}\leq
e^{n(P(t)-\varepsilon)}$ and $c_{1}^{t}\leq e^{P(t)-\varepsilon}$.

Now, we use this fact with Lemma 3.2 to obtain

$\displaystyle\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}$
$\displaystyle\leq\sum_{i+j+k=n}\left(\sum_{\omega\in\mathcal{C}_{i}^{p}}c_{\omega}^{t}\right)\left(\sum_{\tau\in\mathcal{G}_{j}}c_{\tau}^{t}\right)\left(\sum_{\gamma\in\mathcal{C}_{k}^{s}}c_{\gamma}^{t}\right)$
$\displaystyle\leq\sum_{i+j+k=n}c_{0}^{(i+k-1)t}c_{1}^{t}e^{jP(t)}$
$\displaystyle\leq\sum_{i+j+k=n}e^{(i+k)(P(t)-\varepsilon)}e^{jP(t)}$
$\displaystyle=e^{nP(t)}\sum_{i+j+k=n}e^{-\varepsilon(i+k)}$
$\displaystyle=e^{nP(t)}\sum_{m=0}^{n}\sum_{i=0}^{m}e^{-m\varepsilon}$
$\displaystyle\leq e^{nP(t)}\sum_{m=0}^{\infty}(m+1)e^{-m\varepsilon}$

Since $\sum_{m=0}^{\infty}(m+1)e^{-m\varepsilon}$ converges, we can find
$K_{1}$ such that $\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\leq
K_{1}e^{nP(t)}$. ∎

######  Corollary 3.4.

Let $h$ be the unique value such that $P(h)=0$. Then, there exists constant
$K_{2}$ such that

$1\leq\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{h}\leq K_{2}.$

######  Corollary 3.5.

Let $H$ be the unique value such that $\bar{P}(H)=0$. Then, there exists
constant $L_{2}$ such that

$1\leq\sum_{\omega\in\mathcal{L}_{n}}\bar{c}_{\omega}^{H}\leq L_{2}.$

######  Lemma 3.6.

There exist constants $K_{3}>0$ and $N\in\mathbb{N}$ such that for every
$n\in\mathbb{N}$, there exists $l$ satisfying $n-N\leq l\leq n$ such that

$K_{3}e^{lP(t)}\leq\sum_{\omega\in\mathcal{G}_{l}}c_{\omega}^{t}$

for $t$ in a neighborhood of $h$.

###### Proof.

By Lemma 3.3, there exists a constant $K_{1}$ with
$\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\leq K_{1}e^{nP(t)}$. For
$j\in\mathbb{N}$, let
$a_{j}=e^{-jP(t)}\sum_{\tau\in\mathcal{G}_{j}}c_{\tau}^{t}$. Choose
$\varepsilon>0$ as in the proof of Lemma 3.3 and following a similar approach,
we find that

$\displaystyle e^{nP(t)}\leq\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}$
$\displaystyle\leq\sum_{i+j+k=n}\left(\sum_{\omega\in\mathcal{C}^{p}_{i}}c_{\omega}^{t}\right)\left(\sum_{\tau\in\mathcal{G}_{j}}c_{\tau}^{t}\right)\left(\sum_{\gamma\in\mathcal{C}^{s}_{k}}c_{\gamma}^{t}\right)$
$\displaystyle\leq\sum_{i+j+k=n}e^{(i+k)(P(t)-\varepsilon)}\sum_{\tau\in\mathcal{G}_{j}}c_{\tau}^{t}$

By dividing both sides by $e^{nP(t)}$, we get

$\displaystyle 1$
$\displaystyle\leq\sum_{i+j+k=n}e^{-jp(t)}e^{(i+k)(-\varepsilon)}\sum_{\tau\in\mathcal{G}_{j}}c_{\tau}^{t}$
$\displaystyle=\sum_{i+j+k=n}e^{(i+k)(-\varepsilon)}a_{j}$
$\displaystyle\leq\sum_{m=0}^{n}(m+1)e^{-m\varepsilon}a_{n-m}$

Choose $N$ large enough such that
$1-\sum_{m=N}^{\infty}(m+1)e^{-m\varepsilon}>0$, and let
$M=\max\\{(m+1)e^{-m\varepsilon}\mathrel{\mathop{\mathchar
58\relax}}m\in\mathbb{N}\\}$. Using the inequalities above and Lemma 3.2, we
get

$1\leq\sum_{m=0}^{N-1}Ma_{n-m}+\sum_{m=N}^{\infty}(m+1)e^{-m\varepsilon}.$

By rearranging, we obtain:

$M\sum_{m=0}^{N-1}a_{n-m}\geq 1-\sum_{m=N}^{\infty}(m+1)e^{-m\varepsilon}>0.$

This implies that there exists an $l$ with $n-N\leq l\leq n$ satisfying
$NMa_{l}\geq 1-\sum_{m=M}^{\infty}(m+1)e^{-m\varepsilon}$, and so

$\sum_{\omega\in\mathcal{G}_{l}}c_{\omega}^{t}\geq\frac{1-\sum_{m=N}^{\infty}e^{-m\varepsilon}}{MN}e^{lP(t)}.$

∎

######  Proposition 3.7.

For $t$ in a neighborhood of $h$, $Q(t)=P(t)$.

###### Proof.

For any $n\in\mathbb{N}$, $\mathcal{G}_{n}\subset\mathcal{L}_{n}$, and so
$\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}\leq\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}$.
It follows that $Q(t)\leq P(t)$.

Next, using Lemma 3.6 we find constants $K_{3}$ and $N$ to construct a
sequence $(l_{n})$ for which $n-N\leq l_{n}\leq n$ and
$K_{3}e^{l_{n}P(t)}\leq\sum_{\omega\in\mathcal{G}_{l_{n}}}c_{\omega}^{t}$.
Using this with Lemma 3.3, we obtain the inequality

$\frac{K_{3}}{K_{1}e^{NP(t)}}\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\leq
K_{3}e^{(n-N)P(t)}\leq
K_{3}e^{l_{n}P(t)}\leq\sum_{\omega\in\mathcal{G}_{l_{n}}}c_{\omega}^{t}.$

Building off of this inequality, we obtain

$\displaystyle P(t)$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\log\left(\frac{K_{3}}{K_{1}e^{NP(t)}}\sum_{\omega\in\mathcal{L}_{n}}c_{\omega}^{t}\right)$
$\displaystyle\leq\lim_{n\to\infty}\frac{1}{n}\log(\sum_{\omega\in\mathcal{G}_{l_{n}}}c_{\omega}^{t})$
$\displaystyle\leq\lim_{n\to\infty}\frac{1}{l_{n}}\log(\sum_{\omega\in\mathcal{G}_{l_{n}}}c_{\omega}^{t})$
$\displaystyle\leq\limsup_{n\to\infty}\frac{1}{n}\log(\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t})=Q(t).$

Therefore, $Q(t)=P(t)$. ∎

An analogous argument proves the following.

######  Proposition 3.8.

For $t$ in a neighborhood of $h$, $\bar{Q}(t)=\bar{P}(t)$.

In the next section, we will show that the values $h$ and $H$ for which
$P(h)=0$ and $\bar{P}(H)=0$ give bounds for the box and Hausdorff dimension of
the attractor, and so we are interested in $Q(h)=0$ and $\bar{Q}(H)=0$. This
leads us to our next proposition that will provide a better computational tool
for finding these special values for $h$ and $H$.

######  Proposition 3.9.

For real number $h>0$, $Q(h)=0$ if and only if $\sum_{s\in
S}c_{0}^{sh}c_{1}^{h}=1$.

###### Proof.

First, we let $Q(h)=0$ and consider the series $\sum_{n\geq
1}\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}$. If $t<h$, then
$\limsup_{n\to\infty}(\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t})^{1/n}=e^{Q(t)}>1$,
so by the root test, $\sum_{n\geq
1}\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}$ diverges. Similarly, if
$t>h$, then $\sum_{n\geq}\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}$
converges. Next, notice that

(1) $\displaystyle\sum_{n\geq
1}\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}=\sum_{k\geq 1}(\sum_{s\in
S}c_{0}^{st}c_{1}^{t})^{k},$

and $\sum_{k\geq 1}(\sum_{s\in S}c_{0}^{st}c_{1}^{t})^{k}$ converges when
$\sum_{s\in S}c_{0}^{st}c_{1}^{t}<1$ and diverges when $\sum_{s\in
S}c_{0}^{st}c_{1}^{t}>1$. Therefore, $\sum_{s\in S}c_{0}^{sh}c_{0}^{h}=1$
where $h$ satisfies $Q(h)=0$.

Next, assume that $\sum_{s\in S}c_{0}^{sh}c_{1}^{h}=1$. Notice that
$\sum_{s\in S}c_{0}^{st}c_{1}^{t}$ is decreasing with respect to $t$ and so
$\sum_{k\geq 1}(\sum_{s\in S}c_{0}^{st}c_{1}^{t})^{k}$ converges for $t>h$ and
diverges for $t<h$. Therefore, $\sum_{n\geq
1}\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}$ converges for $t>h$ and
diverges for $t<h$. Because
$e^{Q(t)}=\limsup_{n\to\infty}(\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t})^{1/n}$
is strictly decreasing, we can consider all possible outcomes for the root
test applied to $\sum_{n\geq 1}\sum_{\omega\in\mathcal{G}_{n}}c_{\omega}^{t}$
and find that it must be the case the $e^{Q(h)}=1$ and so $Q(h)=0$. ∎

Again, an analogous argument proves the following.

######  Proposition 3.10.

For real number $H>0$, $\bar{Q}(H)=0$ if and only if $\sum_{s\in
S}\bar{c}_{0}^{sH}\bar{c}_{1}^{H}=1$.

##  4\. Main Theorem

To establish the lower bound for the Hausdorff dimension of a subfractal
induced by an $S$-gap shift, we must find a suitable Borel probability measure
that is supported on the subfractal that will satisfy the Mass Distribution
Principle [3]. For that purpose, we define a measure on the symbolic space.
For $\omega\in\mathcal{L}(X)$, let $[\\![\omega]\\!]=\\{\tau\in
X\mathrel{\mathop{\mathchar 58\relax}}\tau_{i}=\omega_{i}\text{ for }1\leq
i\leq\ell(\omega)\\}$ denote the cylinder set of $\omega$. We fix $h$ to be
the unique value such that $P(h)=0$, let $\omega\in\mathcal{L}(X(S))$ and
define

$\nu_{n}([\\![\omega]\\!])=\frac{\sum_{\omega\tau\in\mathcal{L}_{n+\ell(\omega)}}c_{\omega\tau}^{h}}{\sum_{\tau\in\mathcal{L}_{n+\ell(\omega)}}c_{\tau}^{h}}.$

Next, notice that for $n\geq 1$ and any $\omega\in\mathcal{L}$, by Corollary
3.4 we have

$0\leq\frac{\sum_{\omega\tau\in\mathcal{L}_{n+\ell(\omega)}}c_{\omega\tau}^{h}}{K_{2}}\leq\nu_{n}([\\![\omega]\\!])\leq\frac{c_{\omega}^{h}\sum_{\tau\in\mathcal{L}_{n}}c_{\tau}^{h}}{\sum_{\tau\in\mathcal{L}_{n+\ell(\omega)}}c_{\tau}^{h}}\leq
K_{2}c_{\omega}^{h}<\infty.$

Therefore, we can use the Banach limit to define
$\nu([\\![\omega]\\!])=\operatorname{Lim}_{n\to\infty}\nu_{n}([\\![\omega]\\!])$.
Next, notice that :

$\displaystyle\sum_{i=1}^{p}\nu([\\![\omega i]\\!])$
$\displaystyle=\operatorname{Lim}_{n\to\infty}\sum_{i=1}^{p}\frac{\sum_{\omega
i\tau\in\mathcal{L}_{n+\ell(\omega i)}}c_{\omega
i\tau}^{h}}{\sum_{\tau\in\mathcal{L}_{n+\ell(\omega i)}}c_{\tau}^{h}}$
$\displaystyle=\operatorname{Lim}_{n\to\infty}\frac{\sum_{\omega\tau\in\mathcal{L}_{n+1+\ell(\omega)}}c_{\omega\tau}^{h}}{\sum_{\tau\in\mathcal{L}_{n+1+\ell(\omega)}}c_{\tau}^{h}}=\nu([\\![\omega]\\!])$

By the Kolmogorov Extension Theorem, we can extend $\nu$ to a unique Borel
probability measure $\xi$ on all of $X(S)$. We can use this measure to define
a measure $\mu_{h}=\xi\circ\pi^{-1}$, where $\pi$ is the coding map
$\pi\mathrel{\mathop{\mathchar 58\relax}}X(S)\to\mathbb{R}^{n}$. The measure
$\mu_{h}$ is supported on $\mathcal{F}_{X(S)}$.

For the proof of our main theorem, we will use a special cover of the
subfractal $\mathcal{F}_{X(S)}$. For $0<r<1$, we define the cover
$\mathcal{U}_{r}=\\{f_{\omega}(\mathcal{K})\mathrel{\mathop{\mathchar
58\relax}}\mathinner{\\!\left\lvert
f_{\omega}(\mathcal{K})\right\rvert}<r\leq\mathinner{\\!\left\lvert
f_{\omega^{-}}(\mathcal{K})\right\rvert}\\}$, where
$\omega^{-}=\omega_{1}\omega_{2}\ldots\omega_{n-1}$ if
$\omega\in\mathcal{L}_{n}$. From [8], we know that for
$x\in\mathcal{F}_{X(S)}$, the open ball $B(x,r)$ intersects at most $M$
elements of $\mathcal{U}_{r}$, where $M$ is independent of $r$. This gives us
the last tool we need to complete the proof of the main theorem.

######  Theorem 4.1.

Let $h$ and $H$ be the unique values such that $P(h)=0=\bar{P}(H)$. Then,
$h\leq\dim_{H}(\mathcal{F}_{X(S)})\leq H$,
$h\leq\underline{\dim_{B}}(\mathcal{F}_{X(S)})\leq H$, and
$h\leq\overline{\dim_{B}}(\mathcal{F}_{X(S)})\leq H.$

###### Proof.

We will utilize the following well-known relationships between Hausdorff and
box dimension [4]:

$\dim_{H}(\mathcal{F}_{X(S)})\leq\underline{\dim}_{B}(\mathcal{F}_{X(S)})\leq\overline{\dim}_{B}(\mathcal{F}_{X(S)}).$

We start by proving $h$ is a lower bound for the Hausdorff dimension. Next,
let $x\in\mathcal{F}_{X(S)}$ and consider the open ball $B(x,r)$ for some
$0<r<1$ and the cover
$\mathcal{U}_{r}=\\{f_{\omega}(\mathcal{K})\mathrel{\mathop{\mathchar
58\relax}}\mathinner{\\!\left\lvert
f_{\omega}(\mathcal{K})\right\rvert}<r\leq\mathinner{\\!\left\lvert
f_{\omega^{-}}(\mathcal{K})\right\rvert}\\}$. We know at most $M$ elements of
$\mathcal{U}_{r}$ intersect $B(x,r)$, so let
$\mathcal{U}_{M}=\\{f_{\omega}(\mathcal{K})\in\mathcal{U}_{r}\mathrel{\mathop{\mathchar
58\relax}}f_{\omega}(\mathcal{K})\cap B(x,r)\neq\emptyset\\}$ and let
$\mathcal{L}_{M}=\\{\omega\mathrel{\mathop{\mathchar
58\relax}}f_{\omega}(\mathcal{K})\in\mathcal{U}_{M}\\}$. Notice that for any
$f_{\omega}(\mathcal{K})\in\mathcal{U}_{M}\subseteq\mathcal{U}_{r}$ and
corresponding $\omega\in\mathcal{L}_{M}$,

(2) $\displaystyle
c_{\omega}\mathinner{\\!\left\lvert\mathcal{K}\right\rvert}$
$\displaystyle\leq\mathinner{\\!\left\lvert
f_{\omega}(\mathcal{K})\right\rvert}<r\text{ and }$ (3)
$\displaystyle\nu([\\![\omega]\\!])$
$\displaystyle=\operatorname{Lim}_{n\to\infty}\frac{\sum_{\omega\tau\in\mathcal{L}_{n+\ell(\omega)}}c_{\omega\tau}^{h}}{\sum_{\tau\in\mathcal{L}_{n+\ell(\omega)}}c_{\tau}^{h}}\leq\operatorname{Lim}_{n\to\infty}\frac{c_{\omega}^{h}\sum_{\tau\in\mathcal{L}_{n}}c_{\tau}^{h}}{\sum_{\tau\in\mathcal{L}_{n+\ell(\omega)}}c_{\tau}^{h}}\leq
K_{2}c_{\omega}^{h}.$

Using (2) and (3), we find that

$\displaystyle\frac{\mu_{h}(B(x,r))}{r^{h}}$
$\displaystyle\leq\frac{\sum_{\omega\in\mathcal{L}_{M}}\mu_{h}(f_{\omega}(\mathcal{K}))}{r^{h}}=\frac{\sum_{\omega\in\mathcal{L}_{M}}\nu([\\![\omega]\\!])}{r^{h}}$
$\displaystyle\leq\frac{\sum_{\omega\in\mathcal{L}_{M}}K_{2}c_{\omega}^{h}}{r^{h}}\leq\frac{MK_{2}r^{h}}{r^{h}\mathinner{\\!\left\lvert\mathcal{K}^{h}\right\rvert}}$
$\displaystyle=\frac{MK_{2}}{\mathinner{\\!\left\lvert\mathcal{K}\right\rvert}^{h}}$

This inequality holds for all $0<r<1$, and so $\limsup_{r\to
0}\frac{\mu_{h}(B(x,r))}{r^{h}}\leq\frac{MK_{2}}{\mathinner{\\!\left\lvert\mathcal{K}\right\rvert}^{h}}$.
By the Mass Distribution Principle, it follows that
$\mathcal{H}^{h}(\mathcal{F}_{X(S)})\geq\frac{\mu_{h}(\mathcal{F}_{X(S)})\mathinner{\\!\left\lvert\mathcal{K}\right\rvert}^{h}}{MK_{2}}>0$.
Hence, $h\leq\dim_{H}(\mathcal{F}_{X(S)})$ and so $h$ is also a lower bound
for the box dimensions of $\mathcal{F}_{X(S)}$.

It remains to show that $\overline{\dim}_{B}(\mathcal{F}_{X(S)})\leq H$. To
construct covers with minimal overlap, we start with an open set $V$ as in the
definition of the OSC and consider its closure $\operatorname{cl}(V)$. Let
$0<\delta<1$ and consider the cover
$\mathcal{U}_{\delta}=\\{f_{\omega}(\operatorname{cl}(V))\mathrel{\mathop{\mathchar
58\relax}}\mathinner{\\!\left\lvert
f_{\omega}(\operatorname{cl}(V))\right\rvert}<\delta\leq\mathinner{\\!\left\lvert
f_{\omega^{-}}(\operatorname{cl}(V))\right\rvert}\\}$ and the collection of
associated finite words
$\mathcal{L}_{\delta}=\\{\omega\mathrel{\mathop{\mathchar
58\relax}}f_{\omega}(\operatorname{cl}(V))\in\mathcal{U}_{\delta}\\}$. For
$k=\min\\{\ell(\omega)\mathrel{\mathop{\mathchar
58\relax}}\omega\in\mathcal{L}_{\delta}\\}$, we define another cover
$\mathcal{U}_{k}=\\{f_{\omega}(\operatorname{cl}(V))\mathrel{\mathop{\mathchar
58\relax}}\omega\in\mathcal{L}_{k}\\}$. Notice that
$\cup_{U\in\mathcal{U}_{\delta}}U\subseteq\cup_{U\in\mathcal{U}_{k}}U$. Using
this fact with Corollary 3.5, it follows that

(4)
$\displaystyle\sum_{\omega\in\mathcal{L}_{\delta}}\mathinner{\\!\left\lvert
f_{\omega}(\operatorname{cl}(V))\right\rvert}^{H}\leq\sum_{\omega\in\mathcal{L}_{k}}\mathinner{\\!\left\lvert
f_{\omega}(\operatorname{cl}(V))\right\rvert}^{H}\leq\sum_{\omega\in\mathcal{L}_{k}}\bar{c}_{\omega}^{H}\mathinner{\\!\left\lvert\operatorname{cl}(V)\right\rvert}^{H}\leq
L_{2}\mathinner{\\!\left\lvert\operatorname{cl}(V)\right\rvert}^{H}$

The cover $\mathcal{U}_{\delta}$ contains finitely many elements, so there
must exist some $\tau\in\mathcal{L}_{\delta}$ associated with the element of
smallest diameter. Specifically, let $\tau$ be the word such that
$\mathinner{\\!\left\lvert
f_{\tau}(\operatorname{cl}(V))\right\rvert}\leq\mathinner{\\!\left\lvert
f_{\omega}(\operatorname{cl}(V))\right\rvert}$ for all
$\omega\in\mathcal{L}_{\delta}$. For this $\tau$ and using the definition of
$\mathcal{U}_{\delta}$, we obtain

(5)
$\displaystyle\sum_{\omega\in\mathcal{L}_{\delta}}\mathinner{\\!\left\lvert
f_{\omega}(\operatorname{cl}(V))\right\rvert}^{H}\geq\mathinner{\\!\left\lvert
f_{\tau}(\operatorname{cl}(V))\right\rvert}^{H}\mathinner{\\!\left\lvert\mathcal{L}_{\delta}\right\rvert}\geq\mathinner{\\!\left\lvert
f_{\tau^{-}}(\operatorname{cl}(V))\right\rvert}^{H}c_{min}^{H}\mathinner{\\!\left\lvert\mathcal{L}_{\delta}\right\rvert}\geq\delta^{H}c_{min}^{H}\mathinner{\\!\left\lvert\mathcal{L}_{\delta}\right\rvert}.$

Let $N_{\delta}(\mathcal{F}_{X(S)})$ denote the smallest number of sets of
diameter at most $\delta$ that cover $\mathcal{F}_{X(S)}$. Using (4) and (5),
we obtain

$L_{2}\mathinner{\\!\left\lvert\operatorname{cl}(V)\right\rvert}^{H}\geq\delta^{H}c_{min}^{H}\mathinner{\\!\left\lvert\mathcal{L}_{\delta}\right\rvert}\geq\delta^{H}c_{min}^{H}N_{\delta}(\mathcal{F}_{X(S)}).$

Therefore,
$N_{\delta}(\mathcal{F}_{X(S)})\leq\frac{L_{2}\mathinner{\\!\left\lvert\operatorname{cl}(V)\right\rvert}^{H}}{\delta^{H}c_{min}^{H}}$.
Using this we find that

$\frac{\log(N_{\delta}(\mathcal{F}_{X(S)}))}{-\log\delta}\leq\frac{\log(L_{2}\mathinner{\\!\left\lvert\operatorname{cl}(V)\right\rvert}^{H})-\log(c_{min}^{H})-H\log\delta}{-\log\delta}$

Therefore, by letting $\delta\to 0$, we find that

$\overline{\dim}_{B}(\mathcal{F}_{X(S)})=\limsup_{\delta\to
0}\frac{\log(N_{\delta}(\mathcal{F}_{X(S)}))}{-\log\delta}\leq H.$

It follows that $H$ is also an upper bound for the Hausdorff dimension and
lower box dimension. ∎

######  Example 4.2.

Let $X_{F}$ denote the Golden Mean shift, a subshift of finite type on
$\mathcal{A}=\\{0,1\\}$ with forbidden word list $F=\\{11\\}$. We can also
view $X_{F}$ as an $S$-gap shift with set $S=\mathbb{N}$. Let
$\mathcal{F}_{X_{F}}$ denote the subfractal induced by $X_{F}$, where
$\mathcal{F}$ is an attractor of an IFS with maps $f_{0}$, $f_{1}$ and these
maps have lower and upper contractive bounds of $c_{0}$, $\bar{c_{0}}$,
$c_{1}$, $\bar{c_{1}}$, respectively. Using the results above, we see that
both the Hausdorff and box dimension of $\mathcal{F}_{X_{F}}$ is bounded by
$h$ and $H$, where $P(h)=\bar{P}(H)=0$. Using Proposition 3.9, we find that

$1=\sum_{s\in
S}c_{0}^{sh}c_{1}^{h}=\sum_{n=1}^{\infty}c_{0}^{nh}c_{1}^{h}=\frac{c_{1}^{h}c_{0}^{h}}{1-c_{0}^{h}},$

and a similar result involving $H$. Therefore, we are interested in the values
of $h$ and $H$ for which $c_{0}^{h}+c_{0}^{h}c_{1}^{h}=1$ and
$\bar{c}_{0}^{H}+\bar{c}_{0}^{H}\bar{c}_{1}^{H}=1.$
We can also compute these bounds using techniques from [8] by viewing $X_{F}$
as an SFT. In this approach, we must compute the maximal eigenvalue of
$\begin{bmatrix}c_{0}^{t}&c_{1}^{t}\\\ c_{0}^{t}&0\end{bmatrix}$ which is
$\rho(t)=\frac{1}{2}(c_{0}^{t}+\sqrt{c_{0}^{2t}+4c_{0}^{t}c_{1}^{t}})$. We are
interested in the value $h$ for which $\rho(h)=1$, and with some algebra we
find that $c_{0}^{h}+c_{0}^{h}c_{1}^{h}=1$. Through a similar process, we also
find $H$ by $\bar{c}_{0}^{H}+\bar{c}_{0}^{H}\bar{c}_{1}^{H}=1$.

##  5\. Acknowledgments

The author thanks Doğan Çömez and Scott Corry for their helpful feedback and
suggestions on this work.

## References

  * [1] Vaughn Climenhaga and Daniel Thompson.  Intrinsic ergodicity beyond specification: $\beta$-shifts, $s$-gap shifts, and their factors.  Israel J. Math., 192(2):785–817, 2012.
  * [2] David B. Ellis and Michael G. Branton.  Non-self-similar attractors of hyperbolic iterated function systems.  In Dynamical systems (College Park, MD, 1986–87), volume 1342 of Lecture Notes in Math., pages 158–171. Springer, Berlin, 1988.
  * [3] Kenneth Falconer.  Techniques in fractal geometry.  John Wiley & Sons, Ltd., Chichester, 1997.
  * [4] Kenneth Falconer.  Fractal geometry.  John Wiley & Sons, Ltd., Chichester, third edition, 2014.  Mathematical foundations and applications.
  * [5] John E. Hutchinson.  Fractals and self-similarity.  Indiana Univ. Math. J., 30(5):713–747, 1981.
  * [6] Douglas Lind and Brian Marcus.  An introduction to symbolic dynamics and coding.  Cambridge University Press, Cambridge, 1995.
  * [7] Mrinal Kanti Roychowdhury.  Hausdorff and upper box dimension estimate of hyperbolic recurrent sets.  Israel J. Math., 201(2):507–523, 2014.
  * [8] Elizabeth Sattler.  Fractal dimensions of subfractals induced by sofic subshifts.  Monatsh. Math., 183(3):539–557, 2017.
  * [9] Christoph Spandl.  Computing the topological entropy of shifts.  MLQ Math. Log. Q., 53(4-5):493–510, 2007.


#  On the number of $q$-ary quasi-perfect codes with covering radius 2

Alexander M. Romanov Sobolev Institute of Mathematics, 630090 Novosibirsk,
Russia. Supported by the program of fundamental scientific researches of the
SB RAS I.5.1, project N 0314-2019-0017.

###### Abstract

In this paper we present a family of $q$-ary nonlinear quasi-perfect codes
with covering radius 2. The codes have length $n=q^{m}$ and size $M=q^{n-m-1}$
where $q$ is a prime power, $q\geq 3$, $m$ is an integer, $m\geq 2$. We prove
that there are more than $q^{q^{cn}}$ nonequivalent such codes of length $n$,
for all sufficiently large $n$ and a constant $c=\frac{1}{q}-\varepsilon$.

##  1 Introduction

Let $\mathbb{F}_{q}^{n}$ be a vector space of dimension $n$ over the finite
field $\mathbb{F}_{q}$, where $q$ is a prime power. An arbitrary subset
${\mathcal{C}}$ of $\mathbb{F}_{q}^{n}$ is called a _$q$ -ary error correcting
code_ (briefly a $q$-ary code). The _length_ of a code
${\mathcal{C}}\subseteq\mathbb{F}_{q}^{n}$ is the dimension of the vector
space $\mathbb{F}_{q}^{n}$. We assume that the all-zero vector ${\bf 0}$
always belongs to the code, unless otherwise specified. A code is called
_linear_ if it is a subspace of $\mathbb{F}_{q}^{n}$. Otherwise, the code is
called _nonlinear_. The _dimension_ of a linear code is the dimension of the
subspace, denoted by $\text{dim}({\cal C})$. The vectors belonging to a code
${\cal C}$, we will call _codewords_. The _Hamming weight_ of a vector ${\bf
x}\in\mathbb{F}_{q}^{n}$ is the number of nonzero coordinate positions of
${\bf x}$, denoted by $wt(\bf x)$. The _Hamming distance_ between two vectors
${\bf x}$, ${\bf y}\in\mathbb{F}_{q}^{n}$ is the number of coordinate
positions in which they differ, denoted by $d({\bf x},{\bf y})$. The _minimum
distance_ of a code $\mathcal{C}$ is the smallest Hamming distance between two
different codewords of $\mathcal{C}$, denoted by $d(\mathcal{C})$.

Define the _packing radius_ $e({\mathcal{C}})$ of a code ${\cal
C}\subseteq\mathbb{F}_{q}^{n}$. Let
$e({\mathcal{C}})={\lfloor{(d-1)}/{2}\rfloor}$, where $d$ is the minimum
distance of ${\mathcal{C}}$. We also define the _covering radius_
$\rho({\mathcal{C}})$ of a code ${\mathcal{C}}$. Let

$\rho({\mathcal{C}})=\max\limits_{{\bf
x}\in\mathbb{F}_{q}^{n}}\min\limits_{{\bf c}\in{\mathcal{C}}}d({\bf x},{\bf
c}).$

A code ${\cal C}\subseteq\mathbb{F}_{q}^{n}$ is called _perfect_ if
$\rho({\mathcal{C}})=e({\mathcal{C}})$. If
$\rho({\mathcal{C}})=e({\mathcal{C}})+1$, then ${\mathcal{C}}$ is called
_quasi-perfect_. See [9, p. 19].

Two codes ${\mathcal{C}}_{1},{\mathcal{C}}_{2}\subseteq\mathbb{F}_{q}^{n}$ are
said to be _equivalent_ if there exists a vector ${\bf
v}\in\mathbb{F}_{q}^{n}$ and a $n\times n$ monomial matrix $M$ over
$\mathbb{F}_{q}$ such that

${\mathcal{C}}_{2}=\\{({\bf v}+{\bf c}M)\,\,|\,\,{\bf
c}\in{\mathcal{C}}_{1}\\}.$

A codeword ${\bf c}=(c_{1},c_{2},\ldots,c_{n})$ is called _even_ if
$\sum_{i=1}^{n}c_{i}=0$. A code is called _even_ if it contains only even
codewords.

We will use the standard notation $(n,M,d;\rho)_{q}$ to denote a $q$-ary code
of length n, size $M$, minimum distance $d$, and covering radius $\rho$.

In [14] Vasil’ev used the switching construction to construct a family of
binary nonlinear perfect codes with packing radius $e=1$ and length
$n=2^{m}-1$ , $m\geq 4$. In [14] Vasil’ev proved that there are more than
$q^{q^{cn}}$ nonequivalent such codes of length $n$, for all sufficiently
large $n$ and a constant $c=\frac{1}{2}-\varepsilon$. In [6] Etzion and Vardy
used the switching construction to construct binary nonlinear perfect codes of
full-rank. In [11] Phelps and Villanueva used the switching construction to
construct $q$-ary nonlinear perfect codes with ranks of different sizes.

In this paper we use the switching construction to construct a family of
$q$-ary nonlinear quasi-perfect codes with covering radius $\rho=2$. The codes
we offer are of length $n=q^{m}$ and size $M=q^{n-m-1}$ where $q$ is a prime
power, $q\geq 3$, $m$ is an integer, $m\geq 2$. In this paper we prove that
there are more than $q^{q^{cn}}$ nonequivalent such codes of length $n$, for
all sufficiently large $n$ and a constant $c=\frac{1}{q}-\varepsilon$.

In [12], using the concatenation construction, a family of $q$-ary even quasi-
perfect codes with covering radius $\rho=2$ was constructed. The codes
proposed in [12] have length $n=q^{m}$ and size $M=q^{n-m-1}$ where $q$ is a
prime power, $q\geq 3$, $m$ is an integer, $m\geq 4$. It was shown [12] that
there are more than $q^{q^{cn}}$ nonequivalent such codes of length $n$, for
all sufficiently large $n$ and a constant $c$.

For $q=2$, the construction from [12] is the concatenation construction of
binary extended perfect codes proposed by Phelps in [10].

##  2 Generalized Reed-Muller codes

Let $\mathbb{F}_{q}[X_{1},X_{2},\ldots,X_{m}]$ be the algebra of polynomials
in $m$ variables over the field $\mathbb{F}_{q}$. Let a polynomial $f$ be in
$\mathbb{F}_{q}[X_{1},X_{2},\ldots,X_{m}]$, then by $\text{deg}(f)$ we denote
its total degree. Let $AG(m,q)$ be the $m$-dimensional affine space over the
field $\mathbb{F}_{q}$. Let $n=q^{m}$ and the points
$P_{1},P_{2},\ldots,P_{n}$ of $AG(m,q)$ be arranged in some fixed order. Let
$r$ be an integer such that $0\leq r\leq(q-1)m$. Then the generalized Reed-
Muller code [7] of order $r$ over the field $\mathbb{F}_{q}$ is the following
subspace:

${RM}_{q}(r,m)=\big{\\{}(f(P_{1}),f(P_{2}),\ldots,f(P_{n}))\,\big{|}\,f\in\mathbb{F}_{q}[X_{1},X_{2},\ldots,X_{m}],\text{deg}(f)\leq
r\big{\\}}.$

The code ${RM}_{q}(r,m)$ has the following parameters ([7], [1, Theorem 5.5]):

  1. 1.

the length is $q^{m}$;

  2. 2.

the dimension is

$\sum_{k=0}^{m}{(-1)}^{k}{m\choose k}{m+r-kq\choose r-kq};$ (1)

  3. 3.

the minimum distance is

$(q-b)q^{m-a-1},$ (2)

where $r=(q-1)a+b$ and $0\leq b<q-1$.

In what follows, we are only interested in the generalized Reed-Muller codes
${RM}_{q}((r,m)$ of order $r=(q-1)m-2$. In the binary case, the code
${RM}_{q}((r,m)$ of order $r=(q-1)m-2$ is the extended Hamming code of length
$n=2^{m}$. The dimension of the extended Hamming code of length $n=2^{m}$ is
$n-m-1$ and the minimum distance is $4$.

###### Proposition 1

Let $q\geq 3$, $m\geq 1$, and $n=q^{m}$. Then the dimension of the generalized
Reed-Muller code ${RM}_{q}((q-1)m-2,m)$ is ${n-m-1}$ and the minimum distance
is $3$.

Proof.  If a code $\cal C$ belongs to the class of generalized Reed-Muller
codes, then the dual code ${\cal C}^{\perp}$ also belongs to this class [3].
Assume that the length of a code $\cal C$ is $n$. Then

$\text{dim}({\cal C})+\text{dim}({\cal C}^{\perp})=n.$ (3)

From [1, Theorem 5.8], for $r<(q-1)m$, we have

${{RM}_{q}(r,m)}^{\perp}={RM}_{q}((q-1)m-1-r,m).$

Therefore, the order of the code dual to the code ${RM}_{q}((q-1)m-2,m)$ is 1.
By formulas (1) and (3), the dimension of the code ${RM}_{q}((q-1)m-2,m)$ is
${n-m-1}$.

Now we show that for all $m\geq 1$ the minimum distance of the generalized
Reed-Muller code ${RM}_{q}((q-1)m-2,m)$ is $3$. Since

$r=(q-1)m-2=(q-1)a+b\,\,\,\text{and}\,\,\,0\leq b<q-1,$

for $q\geq 3$, we have $a=m-1$ and $b=q-3$. Therefore, by the formula (2), the
minimum distance of the generalized Reed-Muller code ${RM}_{q}((q-1)m-2,m)$ is
$3$.

###### Proposition 2

The generalized Reed-Muller code ${RM}_{q}((q-1)m-2,m)$ is a $q$-ary quasi-
perfect code with covering radius $\rho=2$.

Proof.  The first order generalized Reed-Muller code is a linear two-weight
code [3]. According to [2, Theorem 5.10], the code dual to a linear two-weight
code has covering radius $\rho=2$. Therefore, the generalized Reed-Muller
codes of order $(q-1)m-2$ are quasi-perfect codes with covering radius
$\rho=2$.

From [13, Theorem 3.11] it follows that linear quasi-perfect codes are
uniformly packed codes. Uniformly packed codes attain the Johnson bound and
are optimal codes [13, Theorem 1.3].

##  3 Switching construction

The parity-check matrix $H$ of ${RM}_{q}((q-1)m-2,m)$ is $(m+1)\times q^{m}$
matrix that contains the all-unity vector of length $n=q^{m}$ and all
transposed vectors of $\mathbb{F}_{q}^{m}$, see [3]. Let $H=\left[{\bf
h}_{1},{\bf h}_{2},\ldots,{\bf h}_{n}\right]$, where ${\bf h}_{1},{\bf
h}_{2},\ldots,{\bf h}_{n}$ are columns of the matrix $H$. The affine space
$AG(m,q)$ will be regarded as the incidence geometry. Points
$P_{1},P_{2},\ldots,P_{n}$ of the affine space $AG(m,q)$ correspond to the
coordinates of the vector space $\mathbb{F}_{q}^{n}$.

Let ${\bf x}=(x_{1},x_{2},\dots,x_{n})\in\mathbb{F}_{q}^{n}$, then the
_support_ of the vector ${\bf x}$ is the set

$supp({\bf x})=\\{i\,\,|\,\,x_{i}\neq 0\\}.$

By Proposition 1, the minimum distance of the code ${RM}_{q}((q-1)m-2,m)$ is
$3$ if $q\geq 3$. A codeword of weight $3$ of the code ${RM}_{q}((q-1)m-2,m)$
we will call a _triple_. Let ${\bf c}=(c_{1},c_{2},\ldots,c_{n})$ be a triple
and $supp({\bf c})=\\{i,j,k\\}$. Then

  1. 1.

the triple ${\bf c}$ lies on a line $l$ if $\\{P_{i},P_{j},P_{k}\\}\subseteq
l$;

  2. 2.

the corresponding columns ${\bf h}_{i},{\bf h}_{j},{\bf h}_{k}$ are linearly
dependent, i.e.,

$c_{i}{\bf h}_{i}+c_{j}{\bf h}_{j}+c_{k}{\bf h}_{k}=\bf 0.$

Let $i\in\\{1,\dots,n\\}$, then by ${\cal R}_{i}$ we denote a subspace spanned
by the set of all triples of ${RM}_{q}((q-1)m-2,m)$ having $1$ in the $i$th
coordinate. By definition, the minimum distance of ${\cal R}_{i}$ is 3.

###### Proposition 3

Let $q\geq 3$, $m\geq 1$, and $n=q^{m}$. Let ${\cal
R}_{i}\subseteq{RM}_{q}((q-1)m-2,m)$. Then for any $i\in\\{1,2,\ldots,n\\}$
the dimension of ${\cal R}_{i}$ is $n-[m]_{q}-1$, where $[m]_{q}$ is the
$q$-analogue of the natural number $m$.

Proof.  For $q\geq 3$, every line of the affine space $AG(m,q)$ is in
${RM}_{q}((q-1)m-2,m)$, see [3, 8]. The generalized Reed-Muller code
${RM}_{q}((q-1)m-2,m)$ is spanned by its minimum-weight vectors [3, 4]. In an
affine space $AG(m,q)$, each point has $\frac{n-1}{q-1}$ lines passing through
it, and each line contains $q$ points. For every two distinct points, there is
exactly one line that contains both points. Thus, for each line, there are
$q-2$ linear independent triples that lie on this line. Therefore, the number
of linear independent triples that generate ${\cal R}_{i}$ is
$(q-2)\frac{n-1}{q-1}=n-[m]_{q}-1$.

For $m=1$, generalized Reed-Muller codes are extended Reed-Solomon codes [9,
p. 296]. For $m=1$, the affine space $AG(1,q)$ is a line, and for ${\cal
R}_{i}\subseteq{RM}_{q}(q-3,1)$,

$\text{dim}({RM}_{q}(q-3,1))=\text{dim}({\cal R}_{i})=q-2.$

###### Proposition 4

Let $q\geq 3$, $m\geq 1$. Let ${\bf c}$ be a triple and ${\bf c}\in{\cal
R}_{i}\subseteq{RM}_{q}((q-1)m-2,m)$. Then ${\bf c}$ lies on a line passing
through the point $P_{i}$.

Proof.  If the triples lie on same line, then their linear combination lies on
the same line. In an affine space $AG(m,q)$, the intersection of any two
distinct lines contains exactly one point. Therefore, triples that lie on
distinct lines passing through the point $P_{i}$ have only one common point
$P_{i}$ and their linear combination contains more than three points. By
Proposition 2, the code ${RM}_{q}((q-1)m-2,m)$ is a $q$-ary quasi-perfect code
with covering radius $\rho=2$. For a given code ${RM}_{q}((q-1)m-2,m)$ and
$t=0,1,2$, define

${RM}_{q}^{(t)}((q-1)m-2,m)=\big{\\{}{\bf
x}\in\mathbb{F}_{q}^{n}\,\,\big{|}\,\,d\big{(}{\bf
x},{RM}_{q}((q-1)m-2,m)\big{)}=t\big{\\}}.$

The sets ${RM}_{q}^{(t)}((q-1)m-2,m)$ are called the _subconstituents_ of
${RM}_{q}((q-1)m-2,m)$.

###### Proposition 5

Let $q\geq 3$, $m\geq 2$. Let ${\bf x}\in{RM}_{q}^{(2)}((q-1)m-2,m)$, $wt({\bf
x})=2$, and $supp({\bf x})=\\{j,k\\}$. Let $i\neq j$, $i\neq k$, and the
points $P_{i},P_{j},P_{k}$ are collinear. Then there is a triple ${\bf
c}\in{\cal R}_{i}\subset{RM}_{q}((q-1)m-2,m)$ such that $supp({\bf
c})=\\{i,j,k\\}$ and $d({\bf c},{\bf x})=2$.

Proof.  Consider ${\bf
x}=(x_{1},x_{2},\ldots,x_{n})\in{RM}_{q}^{(2)}((q-1)m-2,m)$, $n=q^{m}$. Let
$wt({\bf x})=2$ and $supp({\bf x})=\\{j,k\\}$. Then there are $q-2$ linear
independent triples that lie on a line $l$ passing through the points $P_{j}$
and $P_{k}$. Let $i\neq j$, $i\neq k$, and the points $P_{i},P_{j},P_{k}$ are
collinear. Then there is a triple ${\bf c}=(c_{1},c_{2},\ldots,c_{n})$ lies on
the line $l$ such that $supp({\bf c})=\\{i,j,k\\}$. For some scalar
$\lambda\in\mathbb{F}_{q}\setminus\\{0\\}$, either $x_{j}=\lambda c_{j}$ or
$x_{k}=\lambda c_{k}$, and $d({\bf x},\lambda{\bf c})=2$.

Let ${\bf e}_{i}$ denote the vector of length $n$ having all components equal
to zero, except the $i$th component which contains a one. Let ${\bf
x}\in{RM}_{q}((q-1)m-2,m)$, $\lambda\in\mathbb{F}_{q}\setminus\\{0\\}$. Let
${\cal R}_{i}+{\bf x}+\lambda{\bf e}_{i}$ be a translate of ${\cal R}_{i}+{\bf
x}$. We shall define a _switching_ to be the process of the replacing the
coset ${\cal R}_{i}+{\bf x}$ with the translate ${\cal R}_{i}+{\bf
x}+\lambda{\bf e}_{i}$.

###### Theorem 6

Let $q\geq 3$, $m\geq 2$, and $n=q^{m}$. Let ${\cal R}_{i}+{\bf
x}\subset{RM}_{q}((q-1)m-2,m)$. Then

${\cal C}^{\prime}=\Big{(}{RM}_{q}((q-1)m-2,m)\setminus({\cal R}_{i}+{\bf
x})\Big{)}\cup\Big{(}{\cal R}_{i}+{\bf x}+\lambda{\bf e}_{i}\Big{)}$

is a $q$-ary nonlinear quasi-perfect code with parameters
$(n,q^{n-m-1},3;2)_{q}$, for any $\lambda\in\mathbb{F}_{q}\setminus\\{0\\}$
and for any $i\in\\{1,2,\ldots,n\\}$.

Proof.  It is easy to show that ${\cal C}^{\prime}$ is nonlinear. Let us show
that $d({\cal C}^{\prime})=3$. Let ${\bf y}\in({\cal R}_{i}+{\bf x})$ and
${\bf z}\in{RM}_{q}((q-1)m-2,m)\setminus({\cal R}_{i}+{\bf x})$. Assume that
$d({\bf y}+\lambda{\bf e}_{i},{\bf z})=2$. Then $d(\lambda{\bf e}_{i},{\bf
z}-{\bf y})=2$. Thus, ${\bf z}-{\bf y}$ is a triple that lies on a line
passing through the point $P_{i}$. So $({\bf z}-{\bf y})\in{\cal R}_{i}$ and
${\bf z}\in{\cal R}_{i}+{\bf x}$. We obtained a contradiction. Therefore, the
minimum distance of the code ${\cal C}^{\prime}$ is 3.

Now let us show that $\rho({\cal C}^{\prime})=2$. Let ${\bf
y}\in{RM}_{q}^{(1)}((q-1)m-2,m)$. In this case, it is obvious that there
exists ${\bf c}\in{\cal C}^{\prime}$ such that $d({\bf c},{\bf y})\leq 2$.

Let ${\bf y}\in{RM}_{q}^{(2)}((q-1)m-2,m)$. Then there exists ${\bf
c}\in{RM}_{q}((q-1)m-2,m)$ such that $d({\bf c},{\bf y})=2$. If ${\bf
c}\in{RM}_{q}((q-1)m-2,m)\setminus({\cal R}_{i}+{\bf x})$, then ${\bf
c}\in{\cal C}^{\prime}$. Let ${\bf c}\in{\cal R}_{i}+{\bf x}$. Since $wt({\bf
y}-{\bf c})=2$, let $supp({\bf y}-{\bf c})=\\{j,k\\}$.

  1. 1.

If the points $P_{i},P_{j},P_{k}$ are not collinear, then, by Proposition 4,
there exists a triple ${\bf c}^{\prime}\notin{\cal R}_{i}$ such that $d({\bf
y},{\bf c}^{\prime}+{\bf c})=2$.

  2. 2.

If the points $P_{i},P_{j},P_{k}$ are collinear. If $i=j$ or $i=k$, then it is
obvious that there is a triple ${\bf c}^{\prime}\in{\cal R}_{i}$ such that
$d({\bf y},{\bf c}^{\prime}+{\bf c}+\lambda{\bf e}_{i})=2$. If $i\neq j$,
$i\neq k$, then, by Proposition 5, there exists a triple ${\bf
c}^{\prime}\in{\cal R}_{i}$ such that $d({\bf y},{\bf c}^{\prime}+{\bf
c}+\lambda{\bf e}_{i})=2$.

###### Theorem 7

Let $q\geq 3$, $m\geq 2$, and $n=q^{m}$. Let ${\cal R}_{i}+{\bf
x}_{t}\subset{RM}_{q}((q-1)m-2,m)$, $1\leq t\leq q^{[m]_{q}-\,m}$, $({\cal
R}_{i}+{\bf x}_{t_{1}})\cap({\cal R}_{i}+{\bf x}_{t_{2}})=\varnothing$ for all
$1\leq t_{1}\leq q^{[m]_{q}-m}$, $1\leq t_{2}\leq q^{[m]_{q}-m}$, $t_{1}\neq
t_{2}$. Then

${\cal C}^{\prime}=\bigcup_{t=1}^{q^{[m]_{q}-m}}({\cal R}_{i}+{\bf
x}_{t}+\lambda_{t}{\bf e}_{i})$

is a $q$-ary quasi-perfect code with parameters $(n,q^{n-m-1},3;2)_{q}$,
$\lambda_{t}\in\mathbb{F}_{q}$, $i\in\\{1,2,\ldots,n\\}$.

Proof.  The number of cosets ${\cal R}_{i}+{\bf x}_{t}$ is $q^{[m]_{q}-m}$.
The cosets ${\cal R}_{i}+{\bf x}_{t}$ form a partition of
${RM}_{q}((q-1)m-2,m)$. Let us show that $d({\cal C}^{\prime})=3$. Let ${\bf
y}\in({\cal R}_{i}+{\bf x}_{t_{1}}+\lambda_{t_{1}}{\bf e}_{i})$, ${\bf
z}\in({\cal R}_{i}+{\bf x}_{t_{2}}+\lambda_{t_{2}}{\bf e}_{i})$, and $({\cal
R}_{i}+{\bf x}_{t_{1}})\cap({\cal R}_{i}+{\bf x}_{t_{2}})=\varnothing.$ Since

$({\bf y}-\lambda_{t_{2}}{\bf e}_{i})\in({\cal R}_{i}+{\bf
x}_{t_{1}}+(\lambda_{t_{1}}-\lambda_{t_{2}}){\bf e}_{i}),$ $({\bf
z}-\lambda_{t_{2}}{\bf e}_{i})\in({\cal R}_{i}+{\bf
x}_{t_{2}})\subset{RM}_{q}((q-1)m-2,m)\setminus({\cal R}_{i}+{\bf
x}_{t_{1}}),$

by Theorem 6 we have $d(({\bf y}-\lambda_{t_{2}}{\bf e}_{i}),({\bf
z}-\lambda_{t_{2}}{\bf e}_{i}))\geq 3.$

Now let us show that $\rho({\cal C}^{\prime})=2$. Let ${\bf
y}\in{RM}_{q}^{(2)}((q-1)m-2,m)$. Then there exists ${\bf
c}\in{RM}_{q}((q-1)m-2,m)$ such that $d({\bf c},{\bf y})=2$. Let ${\bf
c}\in{\cal R}_{i}+{\bf x}_{t}$. Since $wt({\bf y}-{\bf c})=2$, let $supp({\bf
y}-{\bf c})=\\{j,k\\}$. Assume that the points $P_{i},P_{j},P_{k}$ are
collinear. If $i=j$ or $i=k$, then it is obvious that there is a triple ${\bf
c}^{\prime}\in{\cal R}_{i}$ such that $d({\bf y},{\bf c}^{\prime}+{\bf
c}+\lambda_{t}{\bf e}_{i})=2$ and ${\bf c}^{\prime}+{\bf c}\in{\cal
R}_{i}+{\bf x}_{t}$ . If $i\neq j$, $i\neq k$, then, by Proposition 5, there
exists a triple ${\bf c}^{\prime}\in{\cal R}_{i}$ such that $d({\bf y},{\bf
c}^{\prime}+{\bf c}+\lambda_{t}{\bf e}_{i})=2$ and ${\bf c}^{\prime}+{\bf
c}\in{\cal R}_{i}+{\bf x}_{t}$ .

If points $P_{i},P_{j},P_{k}$ are not collinear, then, by Proposition 4, there
exists a triple ${\bf c}^{\prime}\notin{\cal R}_{i}$ such that $d({\bf y},{\bf
c}^{\prime}+{\bf c})=2$ and ${\bf c}^{\prime}+{\bf c}\notin{\cal R}_{i}+{\bf
x}_{t}$.

##  4 Lower bound

###### Theorem 8

Let $q\geq 3$, $m\geq 2$, and $n=q^{m}$. Then there are more than
$q^{q^{[m]_{q}-m}-\,n(m+2)}$ nonequivalent $q$-ary quasi-perfect codes with
parameters $(n,q^{n-m-1},3;2)_{q}$.

Proof.  The number of words of length $q^{[m]_{q}-m}$ over $\mathbb{F}_{q}$ is
$q^{q^{[m]_{q}-m}}$. Hence, by Theorem 7, the number of different quasi-
perfect codes with parameters $(n,q^{n-m-1},3;2)_{q}$ is $q^{q^{[m]_{q}-m}}$.
The number of monomial matrices of size $n\times n$ over $\mathbb{F}_{q}$ is
$(q-1)^{n}n!$. Any equivalence class contains not more than $(q-1)^{n}n!\cdot
q^{n}$ different quasi-perfect codes with parameters $(n,q^{n-m-1},3;2)_{q}$.
Therefore, there are more than $q^{q^{[m]_{q}-m}-\,n(m+2)}$ nonequivalent
$q$-ary quasi-perfect codes with parameters $(n,q^{n-m-1},3;2)_{q}$.

###### Corollary 9

Let $q\geq 3$, $m\geq 2$, and $n=q^{m}$. Then there are more than $q^{q^{cn}}$
nonequivalent $q$-ary nonlinear quasi-perfect codes with parameters
$(n,q^{n-m-1},3;2)_{q}$ for all sufficiently large $n$ and a constant
$c=\frac{1}{q}-\varepsilon$.

## References

  * [1] Assmus E. F., Key J. D.: Polynomial codes and finite geometries. In: Pless V. S., Huffman W. C., Brualdi R. A. (eds.) Handbook of Coding Theory, vol. II, pp. 1269–1344. Elsevier, Amsterdam (1998).
  * [2] Delsarte P.: An Algebraic Approach to the Association Schemes of Coding Theory. Philips Res. Rep. Suppl., 10 (1973).
  * [3] Delsarte P., Goethals J. M., MacWilliams F. J.: On generalized Reed-Muller codes and their relatives. Inform. Contr, 16, 403–442 (1970).
  * [4] Ding P., Key J. D.: Minimum-weight codewords as generators of generalized Reed-Muller codes. IEEE Trans. Inf. Theory, 46, 2152–2157 (2000).
  * [5] Goethals J. M., van Tilborg H. C. A.: Uniformly Packed Codes. Philips Res. Rep., 30, 9–36 (1975).
  * [6] Etzion T., Vardy A.: Perfect binary codes: Constructions, properties, and enumeration. IEEE Trans. Inf. Theory, 40, 754–763 (1994).
  * [7] Kasami T., Lin S., Peterson W. W.: New generalizations of the Reed-Muller codes. Part I: Primitive codes. IEEE Trans. Inf. Theory, 14, 189–199 (1968).
  * [8] Kasami T., Lin S., Peterson W. W.: Polynomial codes. IEEE Trans. Inf. Theory, 14, 807–814 (1968).
  * [9] MacWilliams F. J., Sloane N. J. A.: The Theory of Error-Correcting Codes. North-Holland Publishing Co., Amsterdam (1977).
  * [10] Phelps K. T.: A general product construction for error correcting codes. SIAM J. Algebraic Discrete Methods, 5, 224–228 (1984).
  * [11] Phelps K. T., Villanueva M.: Ranks of $q$-ary 1-perfect codes. Des. Codes Cryptogr., 27, 139–144 (2002).
  * [12] Romanov A. M.: On perfect and Reed-Muller codes over finite fields. Probl. Inf. Transm., 57, 199–211 (2021).
  * [13] van Tilborg H. C. A.: Uniformly Packed Codes. PhD Thesis, University of Tech., Eindhoven (1976).
  * [14] Vasil’ev Yu. L.: On nongroup close-packed codes. Probl. Kybern., 8, 337–339 (1962).


# A Predictable Incentive Mechanism for TrueBit

Julia Koch
<EMAIL_ADDRESS>Christian Reitwießner
<EMAIL_ADDRESS>
###### Abstract

TrueBit [TR17] is a protocol that uses interactive verification to allow a
resource-constrained computation environment like a blockchain to perform much
larger computations than usual in a trusted way. As long as a single honest
participant is present to verify the computation, an invalid computation
cannot get accepted.

In TrueBit, the presence of such a verifier is incentivised by randomly
injected forced errors. Additionally, in order to counter sybil attacks, the
reward for finding an error drops off exponentially with the number of
challengers.

The main drawback of this mechanism is that it makes it very hard to predict
whether participation will be profitable or not.

To even out the rewards, we propose to randomly select multiple solvers from a
pool and evenly share the fees among them, while still allowing outside
challengers. Furthermore, a proof of independent execution will make it harder
to establish computation pools which share computation results.

##  1 Introduction

Due to their consensus construction, it is very hard to inject invalid
computations into a blockchain. This is in part achieved by the fact that
every computation is checked by everyone else participating in the system.
This of course creates a scalability problem and thus the amount of
computation per unit of time is limited.

TrueBit [TR17] is a mechanism to get around this problem: Only the result of a
computation is submitted to the blockchain. Parties interested in this
computation can (but not all parties involved in the blockchain have to) re-
compute it and challenge the submitter in case they obtain a different result.
The challenge leads to an interactive binary search over the steps in the
computation exposing a faulty step which is then checked by the blockchain
itself.

Apart from timeouts, it is impossible for an incorrect result to withstand
such a challenge. Because of that, TrueBit has so-called “unanimous
consensus”, since it only takes a single honest person to expose the error.

This means the main problem to solve is how to ensure that such an honest
person actually participates. If we assume a certain minimum percentage of
honesty, it is sufficient to ensure that a certain number of participants
checked the computation, but it is an open problem how to prove that you
checked a computation, especially in the case that it was correct.

Fully homomorphic encryption can be used so that both the input and the
computation is encrypted to a key unknown to the verifier. The verifier then
performs the computation on encrypted data and submits the solution. After the
solution has been submitted, the private key is published and everyone can
compare the results. This method of course has the drawback that fully
homomorphic encryption is not yet practical, but it can also be attacked if
the verifier somehow can get access to the private key prior to the
computation.

TrueBit tackles the problem of finding out whether a computation was actually
checked by randomly injecting invalid computations and rewarding people if
they detect it. Because of that, every computational task has a certain
probability to contain a so-called “forced error”, which creates an incentive
to verify it. The problem with this is the way the rewards are paid out: In
order to protect against sybil attacks, the total payout is proportional to
$2^{-k}$ in case there were $k$ participants. The formula is the result of the
requirement that your total reward decreases if you create an additional sybil
account to report from.

In this article, we propose two changes to the protocol proposed in TrueBit
[TR17]:

  1. 1.

Instead of a single solver, a certain number of multiple solvers are selected
from a pool of idle and bonded solvers. If there is no disagreement, the
reward is split evenly. Verification games are played if the solvers disagree,
but we alse allow outside challengers. Succeeding outside challengers are
still rewarded with exponential dropoff.

  2. 2.

Together with the solution, solvers are required to submit a so-called “proof
of independent execution” [Dra18]: The root of a Merkle tree of state
snapshots at each step which also contain a private secret, plus a Merkle
proof for a random leaf. This functions as a protection against pooling and
sharing results and replaces the probabilistic forced error and jackpot
mechanism.

In a sense, the difference between the original Truebit protocol and our
version mirrors the difference between miners’ behaviour in Bitcoin vs.
Ethereum: Miners in Bitcoin only need to include transactions and should check
their validity, but might be tempted not to do so, the so-called verifier’s
dilemma [LTKS15], whereas in Ethereum not checking is not an option since a
miner has to include a post state root and simply giving a random one would be
detected very easily. In the same spirit, simply not checking solutions might
be tempting for a verifier in the original version of Truebit, while in our
version each chosen solver has to submit something and cannot simply not
react.

##  2 Protocol

We assume familiarity with the TrueBit protocol and general terms and
definitions used in computer science and the blockchain space.

There is always a minimum of two solvers chosen for every task; if a task
giver wishes to obtain a result with a higher level of security, they can opt
to have a larger number of solvers.

To make sure that the solvers do calculate the solution independently, they
have to deliver a personalized proof of independent execution [Dra18].

######  Definition 2.1.

A _solver_ is a participant in the protocol with a bonded deposit $D$.
A solver is called _available_ if they are not currently participating in
solving a task or a verification game. An account is _slashed_ by destroying
its deposit.

######  Protocol 2.2.

We propose the following protocol, where $H$ is a hash function.

_Step 1:_ Task giver provides task $T$ (computable in $n$ steps) and desired
number of solvers $k\geq 2$

_Step 2:_ A set of $k$ solvers $S$ is chosen randomly from the available
solvers. In the following, “solver” only refers to any of these selected
solvers.

_Step 3:_ Within a certain timeout, each solver, identified by their address
$s$, selects a private random string $p$ and computes the solution to $T$.
While computing the solution, each solver creates hashes of state snapshots
$s_{1},\dots,s_{n}$ and a Merkle tree with leaves $L_{1},\dots,L_{n}$,
$L_{i}=H(s_{i},H(s,p))$ and root $r$. The values $H(s,p,y),r,pr(r)$ are
submitted to the blockchain, where $y$ is the solution and $pr(r)$ is a Merkle
proof to the leaf $L_{1+r\%n}$. The smart contract verifies the Merkle proof
and only stores $H(s,p,y)$ and the leaf $L_{1+r\%n}$.

_Step 4:_ The first challenge period begins: everybody can stake a deposit and
reveal a solver’s private randomness $H(s,p)$ resulting in the solver being
slashed if correct.

_Step 5:_ After the timeout and another timeout to avoid potential rollbacks,
each solver in $S$ submits their own $p,y$.

_Step 6:_ All solutions are compared. If they disagree, verification games are
played tournament-style between solvers with different solutions (randomly
selecting one if there are multiple with the same solution) until only one
solution remains. At the same time, another challenge period starts: anyone
can stake a deposit and initiate a verfication game by challenging the
correctness of either a solution or of the intermediate state stored in the
submitted Merkle leaf.

_Step 7:_ If a solution remains that was not successfully challenged, it is
accepted after a centain time of inactivity. If all solvers are slashed, the
protocol restarts from step 2.

#### Time-out:

If a solver does not act within a given period of time, they lose their
deposit and a new solver is chosen.

#### Rewards:

Someone who can guess a solver’s private randomness receives half of their
deposit. Each non-slashed solver receives $X$ from the task giver. Each non-
slashed outside challenger receives $\frac{k\cdot D}{2^{n}}$, where $n$ is the
total number of non-slashed outside challengers and $k$ the number of
participants slashed in verification games.

#### Penalties:

At the end of a verification game, the losing party loses their deposit $D$.

Remaining funds are burned.

To sum up, the deposit of a solver or outside challenger is slashed in any of
the following situations:

  * •

someone can guess their private randomness before the end of the submission
timeout (only solvers)

  * •

the Merkle proof is invalid (only solvers)

  * •

they lose a verification game

  * •

they do not send a required message before a timeout occurs

We admit the possibility of an “outside” challenger as a line of defense
against cartels: If all solvers chosen for a task conspire to deliver an
incorrect solution, the dominant strategy for every single participant in this
conspiracy is to challenge the incorrect solution as an outside challenger
(with an account that the other conspirators do not know to belong to her) to
obtain (at least a percentage of) the slashed deposits of the conspirators.
Forming a cartel can thus never be a Nash equilibrium.

The Merkle proof is given together with the root to help other participants to
check the correctness of the Merkle root after the private randomness has been
revealed: If there is no Merkle proof, the verifier has to read the full state
snapshots from disk and create the Merkle root. If the Merkle proof is given
right away, only a single state snapshot has to be retrieved from disk. Note
that the Fiat-Shamir heuristic [FS87] is used to determine which Merkle proof
to provide. This ensures that the full Merkle tree has been created and the
leaf is not fabricated.

##  3 Security

In the following, we analyse the security of the protocol. We distinguish mere
deviations from the protocol which try to reduce personal costs and actual
attacks which aim for an invalid solution being accepted.

###  3.1 Possible Deviations from the Protocol

#### Sharing Solutions

If multiple solvers collaborate to avoid parallel execution, it is not enough
to just share the solution, because each solver has to provide an individual
Merkle proof. We conjecture that there is no way to generate a correct Merkle
proof without either knowing the private randomness or the full sequence of
state snapshots. Both pieces of information have to be on the same computer to
form a correct Mekle proof. Since we assume that transmitting the state
snapshots is costly compared to computing them, the only reasonable way is to
transmit the private randomness (or directly generate it at the executing
computer), in which case the executing party can slash the benefiting solver.
Furthermore, slashing can be done pseudonymously, which is important in the
case where more than two solvers collaborate.

#### Pooling Execution

One of the main problems in TrueBit is the impossibility to disincentivize
participants from forming pools.

As long as they form a “lazy cartel”, i.e. a pool that agrees on sharing
solutions (in our version)/not challenging each others’ solutions (in the
original version), but still every member of the pool conducts their
calculations honestly, this is per se not a problem for the trustworthiness of
the system (though it skews the effort/reward ratio in favour of those who
pool and might thus demotivate other participants over the course of time, and
a pool that controls a certain percentage of all participants could very well
threaten the integrity of the system). The risk is obviously that one member
hands in a wrong solution and the others copy this solution/do not challenge
it.

Note that handing in a wrong solution will be punished in our version, while
simply not challenging is not, so the “copying solver” bears a slightly higher
risk; but the fundamental problem that such a wrong solution simply might not
be detected remains.

We further believe that our version removes one of the main motivations behind
forming pools, though: Prospect Theory [KT79] shows that human beings usually
pick a strategy that delivers a predictable reward reliably over one that
delivers even a greater expected value but bears a higher risk. Since the
default strategy in our version of the protocol is of the former type, the
need to “spread the risk” via some kind of “insurance pools” is removed.

Moreover, even in the case where solvers take the risk to be slashed by
collaborating, it is not profitable to share the execution of tasks unless the
number of collaborating solvers is a large percentage of all solvers: The
number of computations can only be reduced if those accounts are selected for
the same tasks at the same time. In addition to that, someone has to create
and maintain specialized software and pay for computing capacity for the pool.

###  3.2 Possible Attacks

In the original version of TrueBit, a wrong solution given by a solver will be
detected if and only if at least one honest verifier is checking this
solution.

In our version, a wrong solution given by a solver will be detected if another
(honest) solver for the same task gives the correct (differing) solution, or
if an outside challenger challenges the solution (in the case of no honest
solver within those chosen for the task).

We calculate the security for our protocol: Assume that an attacker controls
$q$ entities of the $n$ active participants in the solver pool. If the task-
giver chooses to have $k\geq 2$ solvers for their task, the attacker can get
away with a wrong solution if and only if they get randomly chosen for all $k$
roles. The probability for this is

$\frac{\binom{q}{k}}{\binom{n}{k}}=\frac{q\cdot(q-1)\cdot\dots\cdot(q-k+1)}{n\cdot(n-1)\cdot\dots\cdot(n-k+1)}.$

If an attacker controls at most $\frac{1}{r}$th of all solver accounts and a
task giver chooses to have $k$ solvers, the attacker can thus run a successful
attack with a probability of

$\frac{\binom{q}{k}}{\binom{rq}{k}}=\frac{q\cdot(q-1)\cdot\dots\cdot(q-k+1)}{rq\cdot(rq-1)\cdot\dots\cdot(rq-k+1)}\leq\frac{q\cdot(q-1)\cdot\dots\cdot(q-k+1)}{rq\cdot(rq-r)\cdot\dots\cdot(rq-r(k-1))}=\frac{1}{r^{k}}.$

If we take the same assumption as in the original paper, i.e., the attacker
controls at most $\frac{1}{6}$ of all solver accounts, this hence yields a
probability of a successful attack of

$\frac{\binom{q}{2}}{\binom{6q}{2}}=\frac{q\cdot(q-1)}{6q\cdot(6q-1)}\leq\frac{1}{36}\approx
2.8\%$

in the basic case of two solvers, and a probability of less than $0.46\%$ in
the case of three solvers. Note that this is at least as secure as the
original protocol, especially if taking into account that the number of active
verifiers for a task will decrease if the mechanism described in the security
patch in [TR17], A1 “Incorrect secondary solution” is implemented.

We would furthermore like to stress that our protocol does not need any
assumptions on (global) tax rates, but each task giver can choose their
preferred level of security independently for every single task by adjusting
the number of solvers.

#### Availability Engineering.

As explained above, it is necessary to have control over all selected solvers
in order to get an invalid solution accepted. Since selected solvers need to
be available, one strategy would be to tweak the availability of solvers.

A solver can transition from available to unavailable either by being selected
or by acting as an outside challenger. Unavailable solvers can get available
by the task or verification game under consideration ending.

The unavailability of solvers not under control can be extended by challenging
them, but this will result in a deposit being slashed (apart from the unlikely
event that they actually are in error).

Another strategy would be to issue bogus tasks and hope that other solvers get
selected and only solvers under control remain, but the probability for this
happening is similar to just being selected in the original pool.

Making solvers under control unavailable such that they get available again at
a certain time could be another strategy, but the only way a solver can get
unavailable in a predictable way is by acting as an outside challenger, which
will result in being slashed unless there is an actual error, which is
unlikely. Producing an error on purpose also likely results in a deposit being
slashed.

#### Delays.

An attacker can delay a task being resolved by continously acting as an
outside challenger. Since a challenger can lose the verification game even if
the challenged solution is wrong, this might be a strategy to “bore” other
potential challengers. An unsuccessful challenge always leads to slashing,
though, and thus is way too expensive.

###  3.3 Tradeoffs

When comparing our proposed protocol with the original Truebit version, we see
the following tradeoffs:

  * •

Our version removes the need for forced errors, thus making jackpots, taxes,
and, finally, even having a native Truebit token obsolete. It is thus a
simpler, more intuitive protocol.

  * •

Our version allows each task giver to choose their preferred level of security
(by stating the number of solvers they wish) and pay accordingly. In the
original version, the level is the same for each and any task and is
determined by the tax rate.

  * •

Psychology research suggests that our version would make it less attractive
for participants to form pools: We conjecture that the highly unpredictable
nature of payouts in the original Truebit protocol makes “insurance pools”
that distribute the jackpot payouts (and especially the risk of not getting
one) more evenly on a larger number of participants. Since our version yields
lower, but steady income for solvers, this need is removed.

  * •

If pools do form nevertheless, they might be more dangerous in our version
since it does not usually encourage verifiers to double-check the solvers’
solutions. If a pool gets “openly” dishonest (i.e., in the sense of all pool
members knowing that incorrect solutions will be given), our provision for
outside challengers makes betraying the pool the dominant strategy, but this
is not neccesarily a measure of security against “lazy” pools with a pool
administrator gone rogue.

  * •

Our version makes it more costly for a solver to hand in a solution (and thus
also more costly for a task giver) since they need to run not only the
calculation to solve the task itself, but also those necessary for the proof
of independent execution. Note, though, that we do not need taxes, and that
e.g. the security calculation in [TR17], p. 31, assumes that the tax rate
supports 6 verifiers per task – which would correspond to 7 solvers in our
version of the protocol. To reach a similar level of security, we only need 3
solvers as shown on p. 5. Furthermore, the subdivision into elementary steps
and they way the Merkle tree is defined leaves open several parameters which
need to be tuned in practice and can heavily influence the computational
resources needed.

The psychological/economic nature of these questions makes it hard to
impossible to prove superiority of one protocol over another; we think that
only empirical observation can show which one should be chosen finally.

## References

  * [Dra18] Justin Drake.  Proof of independent execution.  https://ethresear.ch/t/proof-of-independent-execution/1988, 2018\.
  * [FS87] Amos Fiat and Adi Shamir.  How to prove yourself: Practical solutions to identification and signature problems.  In Proceedings on Advances in cryptology—CRYPTO ’86, pages 186–194. Springer-Verlag, 1987.
  * [KT79] Daniel Kahneman and Amos Tversky.  Prospect theory: An analysis of decision under risk.  Econometrica, 47(2):263–291, 1979.
  * [LTKS15] Loi Luu, Jason Teutsch, Raghav Kulkarni, and Prateek Saxena.  Demystifying incentives in the consensus computer.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15, pages 706–719. ACM, 2015.
  * [TR17] Jason Teutsch and Christian Reitwiessner.  A scalable verification solution for blockchains.  https://people.cs.uchicago.edu/~teutsch/papers/truebit.pdf, 2017\.