# Sequences of linear codes where the
rate times distance grows rapidly

Faezeh Alizadeh, S. P. Glasby and Cheryl E. Praeger  Shahid Rajaee Teacher
Training University, Tehran, Iran.
Email<EMAIL_ADDRESS>Centre for the Mathematics of Symmetry and
Computation, University of Western Australia, 35 Stirling Highway, Perth 6009,
Australia.
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

For a linear code $C$ of length $n$ with dimension $k$ and minimum distance
$d$, it is desirable that the quantity $kd/n$ is large. Given an arbitrary
field $\mathbb{F}$, we introduce a novel, but elementary, construction that
produces a recursively defined sequence of $\mathbb{F}$-linear codes
$C_{1},C_{2},C_{3},\dots$ with parameters $[n_{i},k_{i},d_{i}]$ such that
$k_{i}d_{i}/n_{i}$ grows quickly in the sense that
$k_{i}d_{i}/n_{i}>\sqrt{k_{i}}-1>2i-1$. Another example of quick growth comes
from a certain subsequence of Reed-Muller codes. Here the field is
$\mathbb{F}=\mathbb{F}_{2}$ and $k_{i}d_{i}/n_{i}$ is asymptotic to
$3n_{i}^{c}/\sqrt{\pi\log_{2}(n_{i})}$ where $c=\log_{2}(3/2)\approx 0.585$.

Keywords: Linear code, parameters, Reed-Muller, rate.
2010 Math Subject Classification: 94B65, 94B05, 94B15. Date: .

##  1\. Introduction

Let $\mathbb{F}$ be an arbitrary field and let $\mathbb{F}^{n}$ denote the
space of all vectors of length $n$ over $\mathbb{F}$. An $\mathbb{F}$-linear
code $C$ of length $n$ is a subspace of the vector space $\mathbb{F}^{n}$, see
[Huffman]*Section 1.2, and elements of $C$ are called _codewords_. Denote the
dimension of $C$ by $k$. Given a codeword $x\in C$, the _(Hamming) weight_ of
$x$, denoted by $\mathrm{wt}(x)$, is the number of non-zero coordinates in
$x$. The _(minimum) distance_ of $C$, denoted $d$ or $d(C)$, is
$d(C)=\min\\{d(x,y)\ |\ x,y\in C,x\neq y\\}$ where $d(x,y)=\mathrm{wt}(x-y)$
is the number of coordinate entries where $x$ and $y$ differ. An
$\mathbb{F}$-linear code of length $n$, dimension $k$ and distance $d$ is
abbreviated an $[n,k,d]$-linear code. The _(information) rate_ of an
$[n,k,d]$-linear code $C$ is $R(C)=k/n$. We henceforth consider only linear
codes.

Let $C_{1},C_{2},C_{3},\dots$ be a sequence of $\mathbb{F}$-linear codes where
$C_{i}$ has parameters $[n_{i},k_{i},d_{i}]$. We are interested in the
question: How quickly can $k_{i}d_{i}/n_{i}$ approach infinity? It is easiest
to understand the growth as a function of one variable, such as $k_{i}$,
$d_{i}$ or $n_{i}$. Since
$k_{i}d_{i}/n_{i}\leqslant\min\\{k_{i},d_{i}\\}\leqslant n_{i}$ such functions
will be at most linear. Asymptotically good code sequences are ones which
satisfy both $k_{i}/n_{i}\geqslant c$ and $d_{i}/n_{i}\geqslant c$ for some
constant $c>0$, see [EKL]*(1.1) and [ShiWuSole], and hence these code
sequences achieve linear growth in $n_{i}$ since $k_{i}d_{i}/n_{i}\geqslant
c^{2}n_{i}$. Such code sequences have been known to exist since [CPW], but
they are not well understood, and the existence of asymptotically good
_cyclic_ codes has been a long standing open problem [MW, ShiWuSole] related
to the uncertainty principle [EKL]. Other code sequences with reasonably good
growth rates include the quadratic residue codes, see [Huffman]*Section 6.6.
These have parameters $[p,(p+1)/2,d]$ where $p$ is a prime, and
$d\geqslant\sqrt{p}$ by [MacS]*p. 483, Theorem 1 so $kd/n$ is at least
$O(\sqrt{n})$. In Example 2.1, we describe a subsequence of Reed-Muller codes
over $\mathbb{F}_{2}$ (_c.f._ [L]) with faster growth _viz._
$kd/n=O(n^{\log_{2}(3/2)})$. On the other hand, we might ask about ‘non-
examples’, that is, code sequences for which $k_{i}d_{i}/n_{i}$ does not grow.
There are such examples even among well-known code families. For example, for
any fixed prime-power $q$, there is an $\mathbb{F}_{q}$-linear Reed-Solomon
code [QBC] with parameters $[n,k,n-k+1]$ provided $q\geqslant n$. The family
of all such codes has $kd/n$ bounded as $kd/n\leqslant\min\\{k,d\\}\leqslant
n\leqslant q$.

We want $k$ to be large (relative to $n$) to transmit a lot of information,
and $d$ to be large to correct many errors, see Section 2 for more details.
For linear codes over a finite field, the Singleton bound ($d\leqslant n-k+1$)
exhibits the tension between $k$ and $d$, and Maximum Distance Separable (MDS)
codes have $d=n-k+1$, see [San]. In Theorem 1.1 we exhibit an explicit
construction for a sequence $C_{1},C_{2},C_{3},\dots$ of $\mathbb{F}$-linear
codes, where $\mathbb{F}$ is a fixed but arbitrary field, and where $C_{i}$
has parameters $[n_{i},k_{i},d_{i}]$ and $k_{i}d_{i}/n_{i}=O(\sqrt{k_{i}})$.

######  Theorem 1.1.

For each field $\mathbb{F}$, there exists an infinite sequence
$C_{1},C_{2},C_{3},\dots$ of $\,\mathbb{F}$-linear codes such that $C_{i}$ has
parameters $[n_{i},k_{i},d_{i}]$ that satisfy

$\displaystyle\frac{k_{i}d_{i}}{n_{i}}=2i>\sqrt{k_{i}}-1>2i-1\qquad\textup{
for $i\geqslant 1$}.$

The codes $C_{1},C_{2},C_{3},\dots$ in Theorem 1.1 are described in
Definitions 4.4 and 4.6. They involve a novel construction described in
Section 3, and their parameters $[n_{i},k_{i},d_{i}]$ are determined in
Theorem 4.7. The codes are $\mathbb{F}$-linear, where $\mathbb{F}$ is an
arbitrary field, and their limiting properties are similar to the well-known
Reed-Muller codes, see Example 2.1.

New codes can also be constructed from old codes via “direct sums” and
“repetition”. Both of these constructions fix the quantity $kd/n$, for suppose
that $C$ is an $\mathbb{F}$-linear code with parameters $[n,k,d]$, and $s$ is
a positive integer. The direct sum code
$\bigoplus_{i=1}^{s}C\leqslant\mathbb{F}^{ns}$ has parameters $[ns,ks,d]$, and
the quantity $(ks)d/(ns)=kd/n$ is independent of $s$. Similarly, the
repetition code $\textup{diag}(\bigoplus_{i=1}^{s}C)=\\{(u,\dots,u)\mid u\in
C\\}$ has parameters $[ns,k,ds]$, and again $k(ds)/(ns)=kd/n$ is independent
of $s$. By contrast, repeated application of the construction introduced to
prove Theorem 4.7 allows $kd/n$ to grow without bound.

##  2\. Further remarks

We represent the vectors in $\mathbb{F}^{n}$ by $n$-dimensional column vectors
over $\mathbb{F}$. Let $C$ be an $[n,k,d]$-linear code in $\mathbb{F}^{n}$ and
let $B=(a_{1},\dots,a_{k})$ be an ordered basis of $C$. Let
$H=[a_{1},\dots,a_{k}]$ be the $n\times k$ matrix formed by this basis. Then
the code $C$ is equal to the set $\\{Hx\mid x\in\mathbb{F}^{k}\\}$, and we
regard an element $x\in\mathbb{F}^{k}$ as an information vector which is
encoded as a codeword $Hx$. As $H$ has rank $k$, by permuting the coordinates
of $\mathbb{F}^{n}$ if necessary, we will assume that the $k\times k$ sub-
matrix formed by the first $k$ rows of $H$ is invertible. Thus the information
vector $x$ is uniquely determined by the first $k$ entries of the associated
codeword $Hx$ and the last $n-k$ entries of $Hx$ may be regarded as redundancy
added to enable transmission errors to be corrected.

The proportion $k/n$ is called the _rate_ $R(C)$ of $C$, and is a measure of
the efficiency of $C$ in encoding information. The third parameter, the
minimum distance $d$ of $C$ is directly related to the error correction
capability of $C$: if strictly less than $d/2$ entries in a codeword are
changed during transmission then the received $n$-tuple is closer (in the
Hamming metric) to the original codeword transmitted than to any other
codeword, and hence these ‘errors’ can be corrected and the correct codeword
determined. A high value of $d$ relative to $n$ denotes high reliability in
transmitting information correctly.

Both $k/n$ and the _relative distance_ $d/n$ are less than $1$: the larger the
rate $k/n$ the more efficient is the code, while the larger the relative
distance $d/n$ the more reliable is the code. The question addressed in this
paper is: How quickly can the quantity $k_{i}d_{i}/n_{i}$ approach infinity?
Our construction demonstrates that this quantity $kd/n$ can grow as fast as
$\sqrt{k}$ for codes over any field $\mathbb{F}$.

######  Example 2.1.

A Reed-Muller code $\textup{RM}(m,r)$ is an $\mathbb{F}_{2}$-linear code, with
parameters $[2^{m},\sum_{j=0}^{r}\binom{m}{j},2^{m-r}]$ by [Huffman]*Theorem
1.10.1. Thus $k_{r}d_{r}/n_{r}=2^{-r}\sum_{j=0}^{r}\binom{m}{j}$ for
$\textup{RM}(m,r)$. The subsequence $(\textup{RM}(2r+1,r))_{r\geqslant 1}$ has
$\dim(\textup{RM}(2r+1,r))=k_{r}=\sum_{j=0}^{r}\binom{2r+1}{j}=2^{2r}$ and
parameters $[2^{2r+1},2^{2r},2^{r+1}]$. Therefore
$k_{r}d_{r}/n_{r}=\sqrt{k_{r}}=O(\sqrt{n_{r}})$. It turns out that the Reed
Muller codes $\textup{RM}(2r+1,r)$, and the codes $C_{r}$ in the Theorem 4.7
have $k_{r}d_{r}/n_{r}=O(\sqrt{k_{r}})$, and the quadratic residue codes have
$k_{r}d_{r}/n_{r}$ at least $\sqrt{k_{r}}$.

A faster growing subsequence is
$(\textup{RM}(m,\lfloor\frac{m}{3}\rfloor+1))_{m\geqslant 1}$. It follows from
[GP]*Theorem 2 that the parameters $[n_{m},k_{m},d_{m}]$ of
$\textup{RM}(m,\lfloor\frac{m}{3}\rfloor+1)$ satisfy $k_{m}d_{m}/n_{m}$ is
asymptotic to

$\frac{3}{\sqrt{\pi
m}}\left(\frac{3}{2}\right)^{m}=O\left(\frac{n_{m}^{\log_{2}(3/2)}}{\sqrt{\log_{2}(n_{m})}}\right)\qquad\textup{
where $n_{m}=2^{m}$ and $\log_{2}\left(\frac{3}{2}\right)\approx 0.585$}.$

##  3\. Bounded linear codes

In this section we present, and investigate, a construction which, given a
linear code as input, produces a linear code with strictly larger length,
dimension and minimum distance. We will be concerned with the extent to which
the construction preserves the property of being bounded, which is defined as
follows.

######  Definition 3.1.

Let $u$ be a positive integer, $C$ an $\mathbb{F}$-linear $[n,k,d]$-code, and
$B=(a_{1},\dots,a_{k})$ an ordered basis for $C$. Then $C$ is said to be _$u$
-bounded relative to $B$_ if the following three conditions hold:

  1. (i)

$\mathrm{wt}(a_{j})=u$ for each $j$;

  2. (ii)

$\mathrm{wt}(\sum_{j=1}^{k}a_{j}$)=$d$; and

  3. (iii)

$u\geqslant d(1+k^{-1})$.

We say that $C$ is _bounded_ if there exist $u$ and $B$ such that $C$ is
$u$-bounded relative to $B$.

###  3.1. The construction

Here we present the construction applied to an arbitrary linear code, and
examine when the boundedness property is preserved.

######  Construction 3.2.

We have the following input an output.
Input: Let $C$ an $\mathbb{F}$-linear $[n,k,d]$-code in $\mathbb{F}^{n}$ with
ordered basis $B=(a_{1},\dots,a_{k})$.
Output: The $\mathbb{F}$-linear code ${\sf Code}(B)$ in $\mathbb{F}^{n(k+1)}$
which is the $\mathbb{F}$-linear span of the sequence ${\sf
Basis}(B)=(a_{1}^{\prime},\dots a_{k+1}^{\prime})$, where

$a_{1}^{\prime}=\begin{bmatrix}0\\\ a_{1}\\\ a_{2}\\\ \vdots\\\
a_{k}\end{bmatrix},\ a_{2}^{\prime}=\begin{bmatrix}a_{k}\\\ 0\\\ a_{1}\\\
\vdots\\\ a_{k-1}\end{bmatrix},\ \dots,\
a_{k+1}^{\prime}=\begin{bmatrix}a_{1}\\\ a_{2}\\\ \vdots\\\ a_{k}\\\ 0\\\
\end{bmatrix},$

and $0$ denotes the zero vector in $\mathbb{F}^{n}$.

We show that the output ${\sf Basis}(B)$ from Construction 3.2 is linearly
independent, determine the parameters of the code ${\sf Code}(B)$, and find
conditions under which ${\sf Code}(B)$ is bounded relative to ${\sf
Basis}(B)$.

######  Proposition 3.3.

Let $\mathbb{F},C,n,k,d,B$ be as in Construction 3.2.

  1. (a)

Then ${\sf Basis}(B)$ is an ordered basis for ${\sf Code}(B)$, and ${\sf
Code}(B)$ is an $\mathbb{F}$-linear $[n^{\prime},k^{\prime},d^{\prime}]$-code,
where

$n^{\prime}=(k+1)n,\quad k^{\prime}=k+1\quad\text{and $d^{\prime}$
satisfies}\quad d^{\prime}\geqslant kd.$

  2. (b)

Further, if $C$ is $u$-bounded relative to $B$, then $d^{\prime}=(k+1)d$, and,
setting $u^{\prime}=ku$, ${\sf Code}(B)$ is $u^{\prime}$-bounded relative to
${\sf Basis}(B)$ if and only if $u\geqslant d(1+2k^{-1})$.

###### Proof.

(a) By Construction 3.2, ${\sf Code}(B)$ has length $n^{\prime}=(k+1)n$.
Further, the fact that the $a_{j}$ are linearly independent implies that the
$a_{j}^{\prime}$ are linearly independent, so ${\sf Basis}(B)$ is an ordered
basis for ${\sf Code}(B)$, and therefore ${\sf Code}(B)$ has dimension
$k^{\prime}=k+1$. It remains to bound the minimum distance $d^{\prime}$. An
arbitrary non-zero codeword $w$ in ${\sf Code}(B)$ has the form
$w=\sum_{j=1}^{k+1}c_{j}a_{j}^{\prime}$ for elements $c_{j}\in\mathbb{F}$, not
all zero. We will prove that $\mathrm{wt}(w)\geqslant kd$, whence
$d^{\prime}\geqslant kd$. Write

$w=\begin{bmatrix}w_{1}\\\ w_{2}\\\ \vdots\\\ w_{k+1}\end{bmatrix},$

where each $w_{i}\in\mathbb{F}^{n}$. Then by the definition of the
$a_{j}^{\prime}$ in Construction 3.2,

(1) $w_{i}=\sum_{j=1}^{k}c_{i-j}a_{j},\quad\mbox{for $i=1,\dots,k+1$, reading
subscripts modulo $k+1$}.$

In particular each $w_{i}$ is a codeword of $C$. Thus if each of the $w_{i}$
is nonzero, then
$\mathrm{wt}(w)=\sum_{i=1}^{k+1}\mathrm{wt}(w_{i})\geqslant(k+1)d$. Suppose
now that, for some $i$, $w_{i}=0$. Since the $a_{j}$ are linearly independent,
it follows from (1) that $c_{i-j}=0$ for $j=1,\dots,k$. Then since $w\neq 0$,
we must have $c_{i}\neq 0$ so $w=c_{i}a_{i}^{\prime}$, and hence

(2)
$\mathrm{wt}(w)=\mathrm{wt}(a_{i}^{\prime})=\sum_{j=1}^{k}\mathrm{wt}(a_{j})\geqslant
kd$

since each $a_{i}$ is a codeword of $C$ and so has weight at least $d$. This
proves part (a).

(b) Now assume that $C$ is $u$-bounded relative to $B$. Let
$w=\sum_{j=1}^{k+1}c_{j}a_{j}^{\prime}$ be an arbitrary non-zero codeword in
${\sf Code}(B)$, and define the $w_{i}$ as above so that
$\mathrm{wt}(w)=\sum_{i=1}^{k+1}\mathrm{wt}(w_{i})$, and equation (1) holds.
If each of the $w_{i}$ is nonzero then $\mathrm{wt}(w)\geqslant(k+1)d$. On the
other hand if some $w_{i}=0$, then we showed above that equation (2) holds, so
$\mathrm{wt}(w)=\sum_{j=1}^{k}\mathrm{wt}(a_{j})$. In this case, by Definition
3.1(i), we have $\mathrm{wt}(a_{j})=u$ for each $j$, and hence
$\mathrm{wt}(w)=ku$. Further, by Definition 3.1(iii), $u\geqslant
d(1+k^{-1})$, and hence $\mathrm{wt}(w)=ku\geqslant(k+1)d$. Thus the minimum
distance $d^{\prime}$ of ${\sf Code}(B)$ satisfies
$d^{\prime}\geqslant(k+1)d$. To see that equality holds, consider the the
codeword $w$ obtained by taking $c_{1}=\dots=c_{k+1}=1$. For each $i$,
equation (1) shows that $w_{i}=\sum_{j=1}^{k}a_{j}$, and hence
$\mathrm{wt}(w_{i})=d$ by Definition 3.1(ii). Therefore, for this codeword $w$
we have $\mathrm{wt}(w)=\sum_{i=1}^{k+1}\mathrm{wt}(w_{i})=(k+1)d$, and we
conclude that $d^{\prime}=(k+1)d$.

Now set $u^{\prime}=ku$. First, from the definition of the $a_{j}^{\prime}$ we
have $\mathrm{wt}(a_{j}^{\prime})=\sum_{i=1}^{k}\mathrm{wt}(a_{i})$, which is
equal to $ku=u^{\prime}$ by Definition 3.1(i). Second, we showed in the
previous paragraph that
$\mathrm{wt}(\sum_{i=1}^{k+1}a_{i}^{\prime})=(k+1)d=d^{\prime}$. Third, since
$u^{\prime}=ku$ and
$d^{\prime}(1+(k^{\prime})^{-1})=(k+1)d(1+(k+1)^{-1})=d(k+2)$, it follows that
$u^{\prime}\geqslant d^{\prime}(1+(k^{\prime})^{-1})$ if and only if
$u\geqslant d(k+2)/k=d(1+2k^{-1})$. Thus, by Definition 3.2, ${\sf Code}(B)$
is $u^{\prime}$-bounded relative to ${\sf Basis}(B)$ if and only if
$u\geqslant d(1+2k^{-1})$. This completes the proof. ∎

###  3.2. Recursive applications of the construction

By Proposition 3.3(a), the output code ${\sf Code}(B)$ of Construction 3.2 is
always a linear code with ordered basis ${\sf Basis}(B)$, and hence
Construction 3.2 may be applied repeatedly, producing larger and larger codes.
Moreover, Proposition 3.3(b) implies that, provided the parameter $u$ is
sufficiently large, ${\sf Code}(B)$ is bounded relative to ${\sf Basis}(B)$.
We investigate how many times we may apply Construction 3.2 recursively and
still obtain a bounded code. To keep track of these repeated applications of
Construction 3.2 we introduce some natural notation for the output codes and
bases.

######  Definition 3.4.

Let $i$ be a positive integer, and let $C$ be an $\mathbb{F}$-linear code with
an ordered basis $B$. In terms of the output of Construction 3.2 applied
repeatedly to $C,B$, for $i=1$, let

${\sf Code}(B,1)={\sf Code}(B)\quad\text{and}\quad{\sf Basis}(B,1)={\sf
Basis}(B),$

and for $i\geqslant 2$, define recursively,

${\sf Code}(B,i)={\sf Code}({\sf Basis}(B,i-1))\quad\text{and}\quad{\sf
Basis}(B,i)={\sf Basis}({\sf Basis}(B,i-1)).$

We examine the parameters and boundedness of ${\sf Code}(B,i)$ for various
values of $i$.

######  Proposition 3.5.

Let $i$ be a positive integer, and let $C$ be an $\mathbb{F}$-linear
$[n,k,d]$-code with an ordered basis $B$.

  1. (a)

Then ${\sf Code}(B,i)$ is an $\mathbb{F}$-linear $[n_{i},k_{i},d_{i}]$-code,
where

$n_{i}=n\prod_{j=1}^{i}(k+j),\quad k_{i}=k+i,\quad d_{i}\geqslant
d\prod_{j=1}^{i}(k+j-1).$

  2. (b)

Further, suppose that $C$ is $u$-bounded relative to $B$, and $u\geqslant
d(1+ik^{-1})$, that is $i\leqslant k(ud^{-1}-1)$. Then the minimum distance
$d_{i}$ of ${\sf Code}(B,i)$ is

$d_{i}=d\prod_{j=1}^{i}(k+j),\quad\mbox{and setting}\quad
u_{i}=u\prod_{j=1}^{i}(k+j-1),$

${\sf Code}(B,i)$ is $u_{i}$-bounded relative to ${\sf Basis}(B,i)$ if and
only if $u\geqslant d(1+(i+1)k^{-1})$.

###### Proof.

(a) Our proof is by induction on $i$. It follows from Proposition 3.3(a) that
${\sf Code}(B,1)$ is an $\mathbb{F}$-linear $[n_{1},k_{1},d_{1}]$-code where
$n_{1}=n(k+1),k_{1}=k+1$ and $d_{1}\geqslant dk$. Suppose that $i\geqslant 2$
and assume that the assertions of part (a) hold for ${\sf Code}(B,i-1)$.
Proposition 3.3(a) implies that $n_{i}=n_{i-1}(k_{i-1}+1),k_{i}=k_{i-1}+1$ and
$d_{i}\geqslant d_{i-1}k_{i-1}$. Hence the assertions of part (a) hold for
also for ${\sf Code}(B,i)$.

(b) Now suppose that $C$ is $u$-bounded relative to the ordered basis $B$.
Then $u\geqslant d(1+k^{-1})$ by Definition 3.1(iii), and by Proposition
3.3(b), the minimum distance $d_{1}$ of ${\sf Code}(B,1)$ is $d_{1}=d(k+1)$;
also ${\sf Code}(B,1)$ is $u_{1}$-bounded, where $u_{1}=ku$, if and only if
$u\geqslant d(1+2k^{-1})$. Thus part (b) holds for $i=1$. Assume now that
$i\geqslant 2$ and $i\leqslant k(ud^{-1}-1)$, and also that part (b) holds for
${\sf Code}(B,i-1)$, that is,

$d_{i-1}=d\prod_{j=1}^{i-1}(k+j),\quad\mbox{and setting}\quad
u_{i-1}=u\prod_{j=1}^{i-1}(k+j-1),$

${\sf Code}(B,i-1)$ is $u_{i-1}$-bounded relative to ${\sf Basis}(B,i-1)$ if
and only if $u\geqslant d(1+ik^{-1})$. Since we are assuming that the
inequality $u\geqslant d(1+ik^{-1})$ holds, we conclude that ${\sf
Code}(B,i-1)$ is $u_{i-1}$-bounded relative to ${\sf Basis}(B,i-1)$. Thus
applying Proposition 3.3(b) to ${\sf Code}(B,i-1)$ with ${\sf Basis}(B,i-1)$,
shows that $d_{i}=d_{i-1}(k_{i-1}+1)$ and that ${\sf Code}(B,i)$ is
$(u_{i-1}k_{i-1})$-bounded relative to ${\sf Basis}(B,i)$ if and only if
$u_{i-1}\geqslant d_{i-1}(1+2k_{i-1}^{-1})$. Since $k_{i-1}+1=k+i$ by part
(a), we conclude that $d_{i}$ is as in part (b). Also, since
$u_{i-1}k_{i-1}=u\prod_{j=1}^{i}(k+j-1)$ is equal to $u_{i}$, ${\sf
Code}(B,i)$ is $u_{i}$-bounded relative to ${\sf Basis}(B,i)$ if and only if
the inequality $u_{i-1}\geqslant d_{i-1}(1+2k_{i-1}^{-1})$ holds. Substituting
the values above for $u_{i-1},d_{i-1},k_{i-1}$, this inequality is

$u\prod_{j=1}^{i-1}(k+j-1)\geqslant\left(d\prod_{j=1}^{i-1}(k+j)\right)\frac{k+i+1}{k+i-1},$

that is, $u\geqslant dk^{-1}(k+i+1)=d(1+(i+1)k^{-1})$. Thus part (b) is proved
by induction. ∎

######  Remark 3.6.

We note that, the quantity mentioned in the introduction, namely the rate
times the minimum distance, grows slowly with the number $i$ of applications
of Construction 3.2: for $1\leqslant i\leqslant k(ud^{-1}-1)$ we have, by
Proposition 3.5, that

$\frac{k_{i}d_{i}}{n_{i}}=\frac{(k+i)d}{n}=\frac{kd}{n}+\frac{id}{n}.$

##  4\. Explicit instances of the construction

In this section we construct a family of linear codes which are defined as
column spaces of a certain family of square matrices. First we introduce the
matrices.

###  4.1. A family of matrices

As always $\mathbb{F}$ denotes an arbitrary field. We introduce an infinite
family of matrices over $\mathbb{F}$, and explore some of their properties. We
denote the space of $m\times n$ matrices over $\mathbb{F}$ by
$\mathbb{F}^{m\times n}$; we denote the zero matrix in this ring by
$0_{m\times n}$, or sometimes just by $0$; and if $m=n$ we denote the identity
matrix by $I_{m}$, and the determinant of $\mathcal{A}\in\mathbb{F}^{m\times
m}$ by $\det(\mathcal{A})$. For a matrix $\mathcal{A}\in\mathbb{F}^{m\times
n}$, its $ij$-entry is denoted $\mathcal{A}_{ij}$, and its _transpose_
obtained by interchanging rows and columns is denoted $\mathcal{A}^{T}$, that
is $(\mathcal{A}^{T})_{ij}=\mathcal{A}_{ji}$ for all $i,j$. For simplicity of
the exposition we will sometimes represent matrices as block matrices where
some $(a\times b$)-block may be an _empty matrix_ , that is $a=0$ or $b=0$ are
allowed.

######  Definition 4.1.

For a positive integer $i$, we define matrices $\mathcal{A}_{i}$ and
$\mathcal{B}_{i}$ as follows. For $i=1$, these are

$\mathcal{A}_{1}=\begin{bmatrix}0&-1\\\
1&0\end{bmatrix},\quad\text{and}\quad\mathcal{B}_{1}=\begin{bmatrix}1&-1\\\
-1&1\end{bmatrix},$

and recursively, for $i\geqslant 1$, if $\mathcal{A}_{i},\mathcal{B}_{i}$ have
been defined, then we let

$\mathcal{A}_{i+1}=\begin{bmatrix}\mathcal{A}_{1}&\mathcal{B}_{i}\\\
-\mathcal{B}_{i}^{T}&\mathcal{A}_{i}\end{bmatrix},\quad\text{and}\quad\mathcal{B}_{i+1}=\begin{bmatrix}\mathcal{B}_{1}&\mathcal{B}_{i}\end{bmatrix}.$

Our first observations about the family are given in this lemma. The idea
behind the proof of Lemma 4.2 we found in [Silvester]*Section 5,
Acknowledgements.

######  Lemma 4.2.

Let $i$ be a positive integer and $\mathcal{A}_{i},\mathcal{B}_{i}$ be as in
Definition 4.1. Then

  1. (a)

$\mathcal{B}_{i}=[\mathcal{B}_{1}\cdots\mathcal{B}_{1}]\in\mathbb{F}^{2\times
2i}$; for $a\in\\{1,2\\}$ and $b\in\\{1,\dots,2i\\}$ we have
$(\mathcal{B}_{i})_{ab}=(-1)^{a+b}$ and
$\mathcal{B}_{i}^{T}\mathcal{A}_{1}\mathcal{B}_{i}=\mathcal{B}_{i}^{T}\mathcal{A}_{1}^{-1}\mathcal{B}_{i}=0_{2\times
2}$.

  2. (b)

$\mathcal{A}_{i}\in\mathbb{F}^{2i\times 2i}$ satisfies
$\det(\mathcal{A}_{i})=1$.

###### Proof.

(a) A straightforward inductive argument, based on the definition of
$\mathcal{B}_{i+1}$ in Definition 4.1 shows that
$\mathcal{B}_{i}=[\mathcal{B}_{1}\cdots\mathcal{B}_{1}]\in\mathbb{F}^{2\times
2i}$ for each $i\geqslant 1$. Then it is easy to see that
$(\mathcal{B}_{i})_{ab}=(-1)^{a+b}$ for all $a,b$. It follows from
$\mathcal{B}_{i}=[\mathcal{B}_{1}\cdots\mathcal{B}_{1}]$ that
$\mathcal{B}_{i}^{T}\mathcal{A}_{1}\mathcal{B}_{i}=\sum_{j=1}^{i}\mathcal{B}_{1}^{T}\mathcal{A}_{1}\mathcal{B}_{1}$,
and computing we see that
$\mathcal{B}_{1}^{T}\mathcal{A}_{1}\mathcal{B}_{1}=\mathcal{B}_{1}\mathcal{A}_{1}\mathcal{B}_{1}=0_{2\times
2}$. Hence $\mathcal{B}_{i}^{T}\mathcal{A}_{1}\mathcal{B}_{i}=0_{2\times 2}$,
and the final assertion
$\mathcal{B}_{i}^{T}\mathcal{A}_{1}^{-1}\mathcal{B}_{i}=0_{2\times 2}$ follows
from the fact that $\mathcal{A}_{1}^{-1}=-\mathcal{A}_{1}$.

(b) It is easy to see that $\det(\mathcal{A}_{1})=1$, and
$\mathcal{A}_{i}\in\mathbb{F}^{2i\times 2i}$ for each $i\geqslant 1$. Assume
that $i\geqslant 1$, assume inductively that $\det(\mathcal{A}_{i})=1$, and
consider $\mathcal{A}_{i+1}$ as defined in Definition 4.1. Modifying an idea
from [Silvester]*Section 5, we see by direct computation that

$\begin{bmatrix}\mathcal{A}_{1}&\mathcal{B}_{i}\\\
-\mathcal{B}_{i}^{T}&\mathcal{A}_{i}\end{bmatrix}\begin{bmatrix}I_{2}&-\mathcal{A}_{1}^{-1}\mathcal{B}_{i}\\\
0_{2i\times 2}&I_{2i}\end{bmatrix}=\begin{bmatrix}\mathcal{A}_{1}&0_{2\times
2i}\\\
-\mathcal{B}_{i}^{T}&\mathcal{B}_{i}^{T}\mathcal{A}_{1}^{-1}\mathcal{B}_{i}+\mathcal{A}_{i}\end{bmatrix}=\begin{bmatrix}\mathcal{A}_{1}&0_{2\times
2i}\\\ -\mathcal{B}_{i}^{T}&\mathcal{A}_{i}\end{bmatrix}$

where the last equality follows from part (a). Since the second matrix on the
left side has determinant 1, it follows that
$\det(\mathcal{A}_{i+1})=\det(\mathcal{A}_{1})\det(\mathcal{A}_{i})=1$ where
the last equality uses the inductive hypothesis. Thus part (b) follows by
induction. ∎

The next lemma looks at properties of the columns of the $\mathcal{A}_{i}$.

######  Lemma 4.3.

Let $i$ be a positive integer, and let
$\mathcal{A}_{i}=[a_{1},a_{2},\dots,a_{2i}]$ be as in Definition 4.1, where
$a_{j}$ is the $j$th column of $\mathcal{A}_{i}$. Then

  1. (a)

$\mathrm{wt}(a_{j})=2i-1$ for $j\in\\{1,\dots,2i\\}$,

  2. (b)

$a_{2j-1}+a_{2j}=[0_{1\times 2(j-1)},-1,1,0_{1\times
2(i-j)}]^{T}\in\mathbb{F}^{2i\times 1}$ for $j\in\\{1,\dots,i\\}$,

  3. (c)

$\sum_{j=1}^{2i-1}a_{j}=[0,\dots,0,1]^{T}\in\mathbb{F}^{2i\times 1}$, and in
particular, $\mathrm{wt}(\sum_{j=1}^{2i-1}a_{j})=1$.

###### Proof.

(a) Part (a) follows immediately from Definition 4.1.

(b) We use induction on $i$. For $i=1$, $a_{1}+a_{2}=[-1,1]^{T}$ by Definition
4.1, so (b) holds in this case (as $i=j=1$ and the first and last entries in
this vector in (b) are empty matrices). Now let $i\geqslant 1$ and assume
inductively that (b) holds for $\mathcal{A}_{i}=[a_{1},\dots,a_{2i}]$, and
consider $\mathcal{A}_{i+1}=[a_{1}^{\prime},\dots,a_{2i+2}^{\prime}]$. By
Definition 4.1 and the structure of $\mathcal{B}_{i}$ given by Lemma 4.2(a),
it follows that $a_{1}^{\prime}+a_{2}^{\prime}=[-1,1,0_{1\times
2i}]^{T}\in\mathbb{F}^{2(i+1)\times 1}$. For $j\in\\{2,\dots,i+1\\}$, it
follows from Definition 4.1 that

$a_{2j-1}^{\prime}+a_{2j}^{\prime}=\begin{bmatrix}0_{2\times 1}\\\
a_{2j-3}+a_{2j-2}\end{bmatrix}.$

Hence the structure of $a_{2j-1}^{\prime}+a_{2j}^{\prime}$ follows from the
inductive hypothesis. Thus part (b) is proved by induction.

(c) This part is also proved by induction on $i$. The case $i=1$ follows from
the definition of $\mathcal{A}_{1}$. So assume that $i\geqslant 1$ and that
part (c) holds for $\mathcal{A}_{i}$, that is
$b:=\sum_{\ell=1}^{2i-1}a_{\ell}=[0,\dots,0,1]^{T}\in\mathbb{F}^{2i\times 1}$.
Suppose that $\mathcal{A}_{i}$ and $\mathcal{A}_{i+1}$ have columns $a_{j}$
and $a^{\prime}_{j}$ as in the proof of part (b). Using the structure of
$\mathcal{B}_{i}$ from Lemma 4.2(a), the form of
$a_{1}^{\prime}+a_{2}^{\prime}$ above, and the inductive hypothesis, we have

$\sum_{j=1}^{2i+1}a_{j}^{\prime}=(a_{1}^{\prime}+a_{2}^{\prime})+\begin{bmatrix}1\\\
-1\\\ \sum_{\ell=1}^{2i-1}a_{\ell}\end{bmatrix}=\begin{bmatrix}-1\\\ 1\\\
0_{2i\times 1}\end{bmatrix}+\begin{bmatrix}1\\\ -1\\\ b\end{bmatrix}=[\ 0,\
\dots\ ,\ 0,\ 1\ ]^{T}\in\mathbb{F}^{2(i+1)\times 1}.$

Part (c) follows by induction. ∎

###  4.2. Codes constructed from matrices

We now construct $\mathbb{F}$-linear codes from the matrices in Subsection
4.1, noting that the columns of $\mathcal{A}_{i}$ are linearly independent by
Lemma 4.2(b) .

######  Definition 4.4.

Let $i$ be a positive integer, let
$\mathcal{A}_{i}=[a_{1},a_{2},\dots,a_{2i}]\in\mathbb{F}^{2i\times 2i}$ be as
in Definition 4.1, where $a_{j}$ is the $j$th column of $\mathcal{A}_{i}$, and
let $C(i)$ be the $\mathbb{F}$-linear code in $\mathbb{F}^{2i}$ with ordered
basis $B(i)=(a_{1},\dots,a_{2i-1})$.

We use the results from Subsection 4.1 to determine the properties of $C(i)$,
and the results from Section 3 to study the codes obtained using Proposition
3.5.

######  Proposition 4.5.

For a positive integer $i$, let $C(i)$ and $B(i)$ be as in Definition 4.4.

  1. (a)

For $i\geqslant 2$, the code $C(i)$ is an $\mathbb{F}$-linear
$[2i,2i-1,1]$-code which is $(2i-1)$-bounded relative to the ordered basis
$B(i)$.

  2. (b)

For $1\leqslant j\leqslant 4i^{2}-6i+1$, the code ${\sf Code}(B(i),j)$, as
defined in Definition 3.4, is an $\mathbb{F}$-linear
$[n_{j},k_{j},d_{j}]$-code that is $u_{j}$-bounded relative to the ordered
basis ${\sf Basis}(B(i),j)$, where

$n_{j}=2i\prod_{\ell=1}^{j}(2i-1+\ell),\quad k_{j}=2i-1+j,\quad
d_{j}=\prod_{\ell=1}^{j}(2i-1+\ell),\ \mbox{and}\
u_{j}=(2i-1)\prod_{\ell=1}^{j}(2i-2+\ell).$

###### Proof.

(a) By Lemma 4.2(b), $B(i)$ is an ordered basis for $C(i)$. Thus $C(i)$ has
length $2i$ and dimension is $2i-1$. Moreover, $d(C(i))=1$ as
$[0,\dots,0,1]^{T}\in C(i)$ by Lemma 4.3(c). By Lemma 4.3(a),
$\mathrm{wt}(a_{j})=2i-1$ for each $j\leqslant 2i-1$, and
$\mathrm{wt}(\sum_{j=1}^{2i-1}a_{j})=1$. To see that $C(i)$ is
$(2i-1)$-bounded relative to $B(i)$ for each $i\geqslant 2$ we use Definition
3.1 and note that $2i-1\geqslant 1+(2i-1)^{-1}$ holds (this is true for
$i\geqslant 2$). This proves part (a).

(b) We apply Proposition 3.5(b) to $C(i)$ and $B(i)$. By part (a) the
parameters $n,u,k,d$ of that result are: $n=2i,u=k=2i-1,d=1$, and we wish to
apply Proposition 3.5(b) with a positive integer parameter $j$ satisfying
$u\geqslant d(1+(j+1)k^{-1})$, or equivalently $j+1\leqslant
k(ud^{-1}-1)=(2i-1)(2i-2)=4i^{2}-6i+2$. This latter inequality is our
assumption on $j$, so we may therefore apply Construction 3.2 $j$ times and
conclude, by Proposition 3.5(b), that ${\sf Code}(B(i),j)$ is an
$\mathbb{F}$-linear $[n_{j},k_{j},d_{j}]$-code that is $u_{j}$-bounded
relative to the ordered basis ${\sf Basis}(B(i),j)$, where the parameters
$n_{j},k_{j},d_{j},u_{j}$ are as in the statement. This proves part (b). ∎

In Proposition 4.5(b) we have $n_{j}=2id_{j}$ and $u_{j}(2i+j-1)=(2i-1)d_{j}$,
respectively. Note that setting $j=0$ in the expressions for
$n_{j},k_{j},d_{j},u_{j}$ in Proposition 4.5(b), we obtain the parameters
$n,k,d,u$, respectively, for the code $C(i)$ examined in Proposition 4.5(a).
Thus if we set ${\sf Code}(B(i),0):=C(i)$, then all the assertions of
Proposition 4.5(b) hold with $j=0$. Thus we have constructed explicitly a two-
parameter family of bounded linear codes over an arbitrary field $\mathbb{F}$,
namely:

${\sf Code}(B(i),j)$ for all $i\geqslant 2$ and all integers $j$ satisfying
$0\leqslant j\leqslant 4i^{2}-6i+1$.

We write ${\sf Code}_{\,\mathbb{F}}(B(i),j)$ and ${\sf
Basis}_{\,\mathbb{F}}(B(i),j)$ if we wish to emphasize the field $\mathbb{F}$
of scalars. To prove our main result we investigate a one-parameter subfamily
of these codes, choosing, for each value of $i$, the code with the largest
value of $j$. We now replace $i$ with $i+1$.

######  Definition 4.6.

For a field $\mathbb{F}$ of scalars, and each $i\geqslant 1$, define

$C_{i}:={\sf
Code}_{\,\mathbb{F}}(B(i+1),4i^{2}-2i-1)\quad\textup{and}\quad\mathcal{B}_{i}:={\sf
Basis}_{\,\mathbb{F}}(B(i+1),4i^{2}-2i-1).$

The following theorem follows immediately from Proposition 4.5.

######  Theorem 4.7.

Given a field $\mathbb{F}$ and an integer $i\geqslant 1$, the code $C_{i}$ is
a linear $[N_{i},K_{i},D_{i}]$-code over $\mathbb{F}$, which is
$U_{i}$-bounded relative to its ordered basis $\mathcal{B}_{i}$, where

$N_{i}=2(i+1)\prod_{\ell=1}^{4i^{2}-2i-1}(2i+1+\ell),\quad K_{i}=4(i+1)i,\quad
D_{i}=\prod_{\ell=1}^{4i^{2}-2i-1}(2i+1+\ell),\ $

and $U_{i}=(2i+1)\displaystyle\prod_{\ell=1}^{4i^{2}-2i-1}(2i+\ell)$.
Moreover, $\displaystyle{\frac{K_{i}D_{i}}{N_{i}}=2i}$ grows linearly with
$i$.

###### Proof.

The first assertions follow immediately from Proposition 4.5 by replacing $i$
with $i+1$. Finally, from these parameters we see that
$\displaystyle{\frac{K_{i}D_{i}}{N_{i}}=\frac{4(i+1)i}{2i}=2i}$. ∎

###### Proof of Theorem 1.1.

By Proposition 4.7 there are $[n_{i},k_{i},d_{i}]$-codes $C_{i}$, $i\geqslant
1$, where $k_{i}d_{i}/n_{i}=2i$ and $k_{i}=4(i+1)i$. A simple calculation
shows that

$2i>\sqrt{4i(i+1)}-1>\sqrt{4i^{2}}-1=2i-1.\qed$

## Acknowledgement

The authors thank Patrick Solé for his remarks and for alerting us to
[ShiWuSole]. The first author is grateful to UWA and the Centre for the
Mathematics of Symmetry and Computation, and also to Shahid Rajaee Teacher
Training University for their financial support when she was a visiting
scholar. The second and third authors acknowledge support from the Australian
Research Council Discovery Project DP190100450.

## References

  * [1]
ChenC. L.PetersonW. W.WeldonJr.E. J.Some results on quasi-cyclic
codesInformation and Control151969407–423ISSN 0019-9958@article{CPW, author =
{Chen, C. L.}, author = {Peterson, W. W.}, author = {Weldon, E. J., Jr.},
title = {Some results on quasi-cyclic codes}, journal = {Information and
Control}, volume = {15}, date = {1969}, pages = {407–423}, issn = {0019-9958}}

  * [3]
EvraShaiKowalskiEmmanuelLubotzkyAlexanderGood cyclic codes and the uncertainty
principleEnseign. Math.6320173-4305–332ISSN 0013-8584@article{EKL, author =
{Evra, Shai}, author = {Kowalski, Emmanuel}, author = {Lubotzky, Alexander},
title = {Good cyclic codes and the uncertainty principle}, journal = {Enseign.
Math.}, volume = {63}, date = {2017}, number = {3-4}, pages = {305–332}, issn
= {0013-8584}}

  * [5]
GlasbyS. P.PasemanG. R.On the maximum of the weighted binomial sum
$2^{-r}\sum_{i=0}^{r}\binom{m}{i}$https://arxiv.org/abs/2109.11396@article{GP,
author = {Glasby, S.\,P.}, author = {Paseman, G.\,R.}, title = {On the maximum
of the weighted binomial sum
\texorpdfstring{$2^{-r}\sum_{i=0}^r\binom{m}{i}$}{}}, note =
{\url{https://arxiv.org/abs/2109.11396}}}

  * [7]
HuffmanW. C.PlessV.Fundamentals of error-correcting codesCambridge University
Press, Cambridge2003@article{Huffman, author = {W. C. Huffman}, author = {V.
Pless}, title = {Fundamentals of Error-Correcting Codes}, journal = {Cambridge
University Press, Cambridge}, date = {2003}}

  * [9]
LachaudGillesProjective reed-muller codesEnglish, French summarytitle={Coding
theory and applications}, address={Cachan}, date={1986}, series={Lecture Notes
in Comput. Sci.}, volume={311}, publisher={Springer, Berlin},
1988125–129@article{L, author = {Lachaud, Gilles}, title = {Projective Reed-
Muller codes}, language = {English, French summary}, conference =
{title={Coding theory and applications}, address={Cachan}, date={1986}, },
book = {series={Lecture Notes in Comput. Sci.}, volume={311},
publisher={Springer, Berlin}, }, date = {1988}, pages = {125–129}}

  * [11]
MacWilliamsF. J.SloaneN. J. A.The theory of error-correcting codes. iNorth-
Holland Mathematical Library, Vol. 16North-Holland Publishing Co., Amsterdam-
New York-Oxford1977i–xv and 1–369ISBN 0-444-85009-0@book{MacS, author =
{MacWilliams, F. J.}, author = {Sloane, N. J. A.}, title = {The theory of
error-correcting codes. I}, series = {North-Holland Mathematical Library, Vol.
16}, publisher = {North-Holland Publishing Co., Amsterdam-New York-Oxford},
date = {1977}, pages = {i–xv and 1–369}, isbn = {0-444-85009-0}}

  * [13]
Martínez-PérezConchitaWillemsWolfgangIs the class of cyclic codes
asymptotically good?IEEE Trans. Inform. Theory5220062696–700ISSN
0018-9448@article{MW, author = {Mart\'{\i}nez-P\'{e}rez, Conchita}, author =
{Willems, Wolfgang}, title = {Is the class of cyclic codes asymptotically
good?}, journal = {IEEE Trans. Inform. Theory}, volume = {52}, date = {2006},
number = {2}, pages = {696–700}, issn = {0018-9448}} LingSanXingChaopingCoding
theory: a first courseCambridge University Press, Cambridge2004xii+222ISBN
0-521-52923-9@book{San, author = {Ling, San}, author = {Xing, Chaoping}, title
= {Coding theory: a first course}, publisher = {Cambridge University Press,
Cambridge}, date = {2004}, pages = {xii+222}, isbn = {0-521-52923-9}}

  * [16]
QuintinGuillaumeBarbierMorganChabotChristopheOn generalized reed-solomon codes
over commutative and noncommutative ringsIEEE Trans. Inform.
Theory5920135882–5897ISSN 0018-9448@article{QBC, author = {Quintin,
Guillaume}, author = {Barbier, Morgan}, author = {Chabot, Christophe}, title =
{On generalized Reed-Solomon codes over commutative and noncommutative rings},
journal = {IEEE Trans. Inform. Theory}, volume = {59}, date = {2013}, pages =
{5882–5897}, issn = {0018-9448}}

  * [18]
ShiMinjiaWuRongshengSoléPatrickAsymptotically good additive cyclic codes
existIEEE Communications Letters22(10)20181980–1983@article{ShiWuSole, author
= {Minjia Shi}, author = {Rongsheng Wu}, author = {Patrick Solé}, title =
{Asymptotically Good Additive Cyclic Codes Exist}, journal = {IEEE
Communications Letters}, volume = {22(10)}, date = {2018}, pages =
{1980–1983}}

  * [20]
SilvesterJ.R.Determinants of block matricesThe Mathematical
Gazette842000460–467@article{Silvester, author = {J.R. Silvester}, title =
{Determinants of block matrices}, journal = {The Mathematical Gazette}, volume
= {84}, date = {2000}, pages = {460–467}}

  * [22]