# Cyclic and BCH Codes whose Minimum Distance Equals their Maximum BCH bound
††thanks: This work was partially supported by MINECO (Ministerio de Economía
y Competitividad), (Fondo Europeo de Desarrollo Regional) project
MTM2012-35240, Programa Hispano Brasileño de Cooperación Universitaria
PHB2012-0135, and Fundación Séneca of Murcia. The second author has been
supported by Departamento Administrativo de Ciencia, Tecnología e Innovación
de la República de Colombia

José Joaquín Bernal1, Diana H. Bueno-Carreño2 and Juan Jacobo Simón1.

1Departamento de Matemáticas
Universidad de Murcia, 30100 Murcia, Spain.
Email: {josejoaquin.bernal<EMAIL_ADDRESS>2Departamento de Ciencias Naturales
y Matemáticas
Pontificia Universidad Javeriana, Cali, Colombia
Email<EMAIL_ADDRESS>
###### Abstract

In this paper we study the family of cyclic codes such that its minimum
distance reaches the maximum of its BCH bounds. We also show a way to
construct cyclic codes with that property by means of computations of some
divisors of a polynomial of the form $x^{n}-1$. We apply our results to the
study of those BCH codes $C$, with designed distance $\delta$, that have
minimum distance $d(C)=\delta$. Finally, we present some examples of new
binary BCH codes satisfying that condition. To do this, we make use of two
related tools: the discrete Fourier transform and the notion of apparent
distance of a code, originally defined for multivariate abelian codes.

##  I Introduction

The computation of the minimum distance of a cyclic code, or a lower bound for
it, is one of the main problems on abelian codes (see, for example, [3, 6,
7]). The oldest lower bound for the minimum distance of a cyclic code is the
BCH bound [5, p. 151]. The study of this bound and its generalizations is a
classical topic which includes the study of the very well-known family of BCH
codes. In particular, an interesting problem is to determine when the maximum
of the BCH bounds of a given cyclic code equals its minimum distance (see [2,
6]). This is our interest.

In this paper we deal with three problems related to the study of the BCH
bound. The first one is how to give necessary and sufficient conditions for a
cyclic code to insure that the maximum of its BCH bounds equals its minimum
distance. The second problem is how to construct such cyclic codes. Our third
problem is related to construction techniques of BCH codes for which its
designed distance, its maximum BCH bound and its minimum distance coincide.

To solve our first problem, we make use of two related tools: the discrete
Fourier transform and the notion of apparent distance of a code, originally
defined for multivariate abelian codes in [1]. These tools and the notation
needed are given in Section 2. In Section 3, we characterize those cyclic
codes for which its minimum distance reaches the maximum of its BCH bounds
(problem 1). Then we study how to construct cyclic codes with that property by
means of computations of divisors of a polynomial of the form $x^{n}-1$
(problem 2). Section 4 is devoted to solve our third problem. We apply our
results to the study of those BCH codes $C$, with designed distance $\delta$,
that have minimum distance $d(C)=\delta$ (see [6, Section 9.2]). In this
paper, some examples of construction techniques and examples of new binary BCH
codes whose minimum distance equals its designed distance are presented. We
point out that all computations were done by using the GAP4r7 program [4] with
the cooperation of Alexander Konovalov. The authors are indebted to him.

##  II Notation and preliminaries

We will use standard terminology from coding theory (see for example [6,
Chapter 7] or [2, Section 2]). We denote by $q$ a power of the prime number
$p$ and by $\mathbb{F}_{q}$ the field of $q$ elements. Let $n$ be a positive
integer which is coprime to $q$. We denote by $R_{n}$ the set of $n$-th roots
of unity and by $U_{n}$ the set of primitive $n$-th roots of unity.

We denote by $\mathbb{F}_{q}[x]$ the ring of polynomials with coefficients in
$\mathbb{F}_{q}$. For any $g=g(x)\in\mathbb{F}_{q}[x]$ we denote by $\deg(g)$
its degree, by $supp(g)$ its support and by $\omega(g)=\left|supp(g)\right|$
its weight. For any positive integer $n$, we consider the quotient ring
$\mathbb{F}_{q}[x]/(x^{n}-1)$ which will be denoted by $\mathbb{F}_{q}(n)$. As
usual, we identify the elements $g\in\mathbb{F}_{q}(n)$ with polynomials; so
we may take $g\in\mathbb{F}_{q}(n)$ and then write $g\in\mathbb{F}_{q}[x]$
(where $\deg(g)<n$). For any $f\in\mathbb{F}_{q}[x]$ we denote by
$\overline{f}$ its image under the canonical projection onto
$\mathbb{F}_{q}(n)$.

As in [7], a cyclic code $C$ of length $n$ in the alphabet $\mathbb{F}_{q}$
will be identified with the corresponding ideal in $\mathbb{F}_{q}(n)$ (up to
permutation equivalence). Then, by a cyclic code we mean an ideal of
$\mathbb{F}_{q}(n)$. It is well known that if $\gcd(n,q)=1$ then the quotient
ring $\mathbb{F}_{q}(n)$ is semisimple and then every cyclic code has a unique
monic generator polynomial [6, Theorem 7.1] and a unique idempotent generator
[6, Theorem 8.1]. We always assume that $\gcd(n,q)=1$.

We denote by ${\mathbb{Z}}_{n}$ the integers modulo $n$ and we identify any
class in ${\mathbb{Z}}_{n}$ with its canonical representative. It is well-
known that every cyclic code $C$ in $\mathbb{F}_{q}(n)$ is totally determined
by its set of zeros (or its root set), which is defined as
$Z(C)=\left\\{\alpha\in R_{n}\;\mid\;c(\alpha)=0,\;\text{ for all }\;c\in
C\right\\}$; thus, for any polynomial $f\in\mathbb{F}_{q}(n)$, we have that
$f\in C$ if and only if $f(\alpha)=0$ for all $\alpha\in Z(C)$. Fixed
$\alpha\in U_{n}$, we denote the defining set of $C$ with respect to $\alpha$
as $D_{\alpha}(C)=\left\\{i\in{\mathbb{Z}}_{n}\;\mid\;\alpha^{i}\in
Z(C)\right\\}$ (see [6, p. 199]). It is well-known that, when $\gcd(n,q)=1$,
defining sets are partitioned in $q$-cyclotomic cosets modulo $n$ [6, p. 104],
which are defined as follows: given any element $a\in{\mathbb{Z}}_{n}$, the
$q$-cyclotomic coset of $a$ modulo $n$ is the set
$C_{q}(a)=\\{a,qa,\dots,q^{n_{a}-1}a\\}(\mod n)$, where $n_{a}$ is the
smallest positive integer such that $q^{n_{a}}a\equiv a\mod n$. We recall that
the notions of set of zeros and defining set are also applied to polynomials
in $\mathbb{F}_{q}(n)$ in the obvious way.

For any code $C$, we denote its minimum distance by $d(C)$. The BCH bound
states that for any cyclic code in $\mathbb{F}_{q}(n)$ that has a string of
$\delta-1$ consecutive powers of some $\alpha\in U_{n}$ as zeros, the minimum
distance of the code is at least $\delta$ [6, Theorem 7.8]. In terms of
defining sets, if there is a string of $\delta-1$ consecutive integers modulo
$n$ in $D_{\alpha}(C)$, for some $\alpha\in U_{n}$, then $d(C)\geq\delta$.
Note that different roots of unity may yield different defining sets and
consequently different lower bounds. For any cyclic code $C$ the maximum of
its BCH bounds will be denoted by $\Delta(C)$. Sometimes it is called the BCH
(lower) bound of the code (see [1, p. 22] and [2, p. 984]).

The following Remark shows that in order to compute the maximum $\Delta(C)$ we
do not need to consider all the elements in $U_{n}$. This fact will be used
later.

######  Remark 1.

Let $C_{q}(a_{1}),\dots,C_{q}(a_{h})$ be the $q$-cyclotomic cosets modulo $n$
and fix a complete set of representatives $\\{a_{1},\dots,a_{h}\\}$. Suppose
we have chosen $\alpha\in U_{n}$ to get a defining set $D_{\alpha}(C)$. We
want to identify the elements $\beta\in U_{n}$ satisfying that
$D_{\beta}(C)\neq D_{\alpha}(C)$. Then, $\beta$ must satisfy the equality
$\beta^{a_{i}q^{j}}=\alpha$ for some representative $a_{i}$ with
$\gcd(n,a_{i})=1$ and $j\in{\mathbb{Z}}$. In this case
$D_{\beta}(C)=a_{i}\cdot D_{\alpha}(C)$, where the multiplication has the
obvious meaning. We define

$A(n)=\\{a_{i}\;\mid\;\gcd(a_{i},n)=1\\}.$ (1)

It is easy to see that $O_{n}(q)=|C_{q}(a_{i})|$ for any $a_{i}\in A(n)$. In
addition, since
$D_{\beta^{a_{i}}}(C)=D_{\beta^{a_{i}q^{j}}}(C)=D_{\beta^{a_{i}q^{j^{\prime}}}}(C)$
($j,j^{\prime}\in{\mathbb{Z}}$), we conclude that we have to consider at most
$\frac{\phi(n)}{O_{n}(q)}$ distinct defining sets or elements in $U_{n}$ to
get $\Delta(C)$.

For example, set $n=41$ and $q=2$. The $2$-cyclotomic cosets are
$C_{2}(0),\,C_{2}(1)$ and $C_{2}(3)$. So $A(41)=\\{1,3\\}$. Fixed $\alpha\in
U_{41}$, let $C$ be the cyclic code with defining set
$D_{\alpha}(C)=C_{2}(1)$. Some BCH bounds for $C$ with respect to $\alpha$ are
$\delta_{1}=3$ by considering $\\{1,2\\}\subset D_{\alpha}(C)$, and
$\delta_{2}=4$ by considering $\\{8,9,10\\}\subset D_{\alpha}(C)$. Now we also
have to consider $D_{\beta}(C)=3\cdot D_{\alpha}(C)=C_{2}(3)$ and compute the
corresponding BCH bounds. We find $\delta_{3}=6$ by considering
$\\{11,12,13,14,15\\}\subset D_{\beta}(C)$. In this case, $\Delta(C)=6$. It is
worth to mention that in the binary and ternary cases for $n\leq 70$ we have
that $\frac{\phi(n)}{O_{n}(q)}\leq 6$ and for $n\leq 90$ we have that
$\frac{\phi(n)}{O_{n}(q)}\leq 8$.

A cyclic code $C$ in $\mathbb{F}_{q}(n)$, with generator polynomial $g(x)$, is
a BCH code of designed distance $\delta$ if there exists $\alpha\in U_{n}$ and
$b\in\\{0,\dots,n-1\\}$ such that $g(x)$ is the polynomial with the lowest
degree over $\mathbb{F}_{q}$ such that
$\left\\{\alpha^{b+j}\;\mid\;j=0,\dots,\delta-2\right\\}\subseteq Z(C)$ (see
[6, p. 202]). Equivalently, $C$ is a BCH code if for any cyclotomic coset
$Q\subseteq D_{\alpha}(C)$ we have that
$Q\cap\left\\{b+j\;\mid\;j=0,\dots,\delta-2\right\\}\neq\emptyset$. As it is
known, this implies that $C$ is the cyclic code with highest dimension such
that its set of zeros satisfies the inclusion mentioned above. We denote such
a code by $B_{q}(\alpha,\delta,b)$. The Bose distance of a BCH code
$C=B_{q}(\alpha,\delta,b)$ is defined as the largest $\delta^{\prime}$ such
that $C=B_{q}(\alpha^{\prime},\delta^{\prime},b^{\prime})$, for some
$b^{\prime}\in\\{0,\dots,n-1\\}$ and some $\alpha^{\prime}\in U_{n}$. We note
that for a BCH code it may happen that its Bose distance is less than
$\Delta(B_{q}(\alpha,\delta,b))$, as we shall see in the next example.

Let $\mathbb{L}|\mathbb{F}_{q}$ be an extension field. For any element
$a\in\mathbb{L}$ we denote by $\mathrm{min}_{q}(a)$ the minimal polynomial of
$a$ in $\mathbb{F}_{q}[x]$. In the case $q=2$ we only write $\mathrm{min}(a)$.

######  Example 2.

Set $q=2$, $n=21$ and fix $\alpha\in U_{21}$ such that
$\mathrm{min}(\alpha)=x^{6}+x^{5}+x^{4}+x^{2}+1$. Let $C=B_{2}(\alpha,4,6)$ be
the BCH code generated by
$\mathrm{lcm}\\{\mathrm{min}(\alpha),\mathrm{min}(\alpha^{3}),\mathrm{min}(\alpha^{7})\\}$.
Consider the 2-cyclotomic cosets modulo $21$, $C_{2}(0)=\\{0\\}$,
$C_{2}(1)=\\{1,2,4,8,11,16\\}$, $C_{2}(3)=\\{3,6,12\\}$,
$C_{2}(5)=\\{5,10,13,17,19,20\\}$, $C_{2}(7)=\\{7,14\\}$ and
$C_{2}(9)=\\{9,15,18\\}$. One may check that the defining set of the code $C$
with respect to $\alpha$ is $D_{\alpha}(C)=C_{2}(1)\cup C_{2}(3)\cup
C_{2}(7)=C_{2}(6)\cup C_{2}(7)\cup C_{2}(8)$. In this case $A(21)=\\{1,5\\}$
so we also have to consider the element $\beta\in U_{21}$ such that
$\beta^{5}=\alpha$. Then $D_{\beta}(C)=5\cdot D_{\alpha}(C)=C_{2}(5)\cup
C_{2}(7)\cup C_{2}(9)$. One may see that the Bose distance is $\delta=4$,
given by considering $\\{6,7,8\\}\subset D_{\alpha}(C)$ and
$\\{13,14,15\\}\subset D_{\beta}(C)$. However $\Delta(C)=5$, because
$\\{1,2,3,4\\}\subset D_{\alpha}(C)$ and $\\{17,18,19,20\\}\subset
D_{\beta}(C)$. But $\\{1,2,3,4\\}\subset C_{2}(1)\cup C_{2}(3)$ and
$\\{17,18,19,20\\}\subset C_{2}(5)\cup C_{2}(9)$, so that $C$ cannot be a BCH
code of designed distance $\delta=5$. Hence the Bose distance is less than the
maximum of all possible BCH bounds (or simply the BCH bound, $\Delta(C)$).

Let $\mathbb{L}|\mathbb{F}_{q}$ be an extension field such that
$U_{n}\subseteq\mathbb{L}$ and fix $\alpha\in U_{n}$. The  (discrete) Fourier
transform of a polynomial $f\in\mathbb{F}_{q}(n)$ with respect to $\alpha$
(also called Mattson-Solomon polynomial), that we denote by
$\varphi_{\alpha,f}$ is defined as

$\varphi_{\alpha,f}(x)=\sum_{j=0}^{n-1}f(\alpha^{j})x^{j}.$

Clearly, $\varphi_{\alpha,f}\in\mathbb{L}(n)$; moreover, the function Fourier
transform may be viewed as an isomorphism of algebras
$\varphi_{\alpha}:\mathbb{L}(n)\longrightarrow(\mathbb{L}^{n},\star)$, where
the multiplication “$\star$” in $\mathbb{L}^{n}$ is defined coordinatewise
(see [1, Section 2.2] or [6, § 8.6]). Then we may see $\varphi_{\alpha,f}$ as
a vector in $\mathbb{L}^{n}$ or as a polynomial in $\mathbb{L}(n)$. The
inverse of the Fourier transform is given by
$\varphi^{-1}_{\alpha,g}(x)=\frac{1}{n}\sum_{i=0}^{n-1}g(\alpha^{-i})x^{i}$,
where $g\in\mathbb{L}(n)$ (see for example [1, 2, 6]). For any
$i\in\\{0,\dots,n-1\\}$ we denote $\varphi_{\alpha,f}[i]=f(\alpha^{i})$, the
coefficient (or coordinate) corresponding to $x^{i}$.

######  Remark 3.

For any $\alpha\in U_{n}$, $f\in\mathbb{F}_{q}(n)$ and $g\in\mathbb{L}(n)$ we
have that:

  1. 1.

$supp\left(\varphi_{\alpha,f}\right)=\left\\{i\in\\{0,\dots,n-1\\}\;\mid\;f\left(\alpha^{i}\right)\neq
0\right\\}$ and hence ${\mathbb{Z}}_{n}\setminus
supp\left(\varphi_{\alpha,f}\right)=D_{\alpha}(f)$, the defining set of $f$.

  2. 2.

Since $f=\varphi^{-1}_{\alpha,\varphi_{\alpha,f}}(x)$ then
$supp(f)=\left\\{i\in\\{0,\dots,n-1\\}\;\mid\;\varphi_{\alpha,f}\left(\alpha^{-i}\right)\neq
0\right\\}$, so that $|supp(f)|=n-|Z\left(\varphi_{\alpha,f}\right)|$.

  3. 3.

$\varphi^{-1}_{\alpha,g}\in\mathbb{F}_{q}(n)$ if and only if
$\left(g\left(\alpha^{j}\right)\right)^{q}=g\left(\alpha^{j}\right)$ for any
$j\in\\{0,\dots,n-1\\}$.

  4. 4.

$\varphi^{-1}_{\alpha,g}\in\mathbb{F}_{q}(n)$ if and only if
$\varphi^{-1}_{\beta,g}\in\mathbb{F}_{q}(n)$ for all $\beta\in U_{n}$.

The first two assertions come directly from the definition of the discrete
Fourier transform together with the fact that it is an isomorphism. The third
one comes directly from the well-known property that an element
$a\in\mathbb{L}$ satisfies that $a\in\mathbb{F}_{q}$ if and only if $a^{q}=a$.
Finally to see the last assertion observe that if we take another primitive
root of unity $\beta\neq\alpha$ the coefficients of $\varphi^{-1}_{\beta,g}$
are obtained by permuting those of $\varphi^{-1}_{\alpha,g}$.

The following lemma, related with the discrete Fourier transform, will play an
important role later.

######  Lemma 4.

Let $g\in\mathbb{L}(n)$. If $\varphi^{-1}_{\alpha,g}\in\mathbb{F}_{q}(n)$ for
any $\alpha\in U_{n}$ then $supp(g)$ is a union of cyclotomic cosets. If $g$
is an idempotent in $(\mathbb{L}^{n},\star)$ the converse holds; that is, if
$supp(g)$ is union of $q$-cyclotomic cosets then
$\varphi^{-1}_{\alpha,g}\in\mathbb{F}_{q}(n)$.

###### Proof.

First, suppose that $\varphi^{-1}_{\alpha,g}\in\mathbb{F}_{q}(n)$. Observe
that for any $f(x)\in\mathbb{F}_{q}(n)$,
$\varphi_{\beta,f}^{q}(x)=\sum_{j=0}^{n-1}\left(f\left(\beta^{j}\right)\right)^{q}x^{j}=\sum_{j=0}^{n-1}\left(f\left(\beta^{q}\right)\right)^{j}x^{j}=\varphi_{\beta^{q},f}(x)$.
So the defining set of $\varphi^{-1}_{\alpha,g}$ is a union of cyclotomic
cosets. Since $supp(g)={\mathbb{Z}}_{n}\setminus
D_{\alpha}(\varphi^{-1}_{\alpha,g})$ we are done.

We first note that any idempotent in $(\mathbb{L}^{n},\star)$ verifies that
its coordinates (or coefficients) are only 1 or 0. Now, suppose that
$g\in(\mathbb{L}^{n},\star)$ is an idempotent and $supp(g)$ is a union of
$q$-cyclotomic cosets. Then there exists an idempotent $e\in\mathbb{F}_{q}(n)$
such that $D_{\alpha}(e)={\mathbb{Z}}_{n}\setminus supp(g)$; in fact, $e$ is
the idempotent generator of the code over $\mathbb{F}_{q}$ with defining set
${\mathbb{Z}}_{n}\setminus supp(g)$ with respect to $\alpha$. Since $e$ is an
idempotent in $\mathbb{F}_{q}(n)$ we have that $\varphi_{\alpha,e}$ is an
idempotent in $(\mathbb{L}^{n},\star)$ and also
$supp(\varphi_{\alpha,e})=supp(g)$. Then $\varphi_{\alpha,e}=g$ and hence
$\varphi^{-1}_{\alpha,g}\in\mathbb{F}_{q}(n)$. ∎

Let us recall some definitions in [1, Chapter 3] related to the computation of
the BCH bound. The context of these definitions is the study of multivariate
polynomials. We only need the univariate polynomials version.

######  Definition 5.

Let $\mathbb{L}$ be a field. For any element $g\in\mathbb{L}(n)$ we define the
apparent distance of $g$, that we denote by $d^{\ast}(g)$, as follows

  1. 1.

If $g=0$ then $d^{\ast}(0)=0$.

  2. 2.

If $g\neq 0$ then

$d^{\ast}(g)=\max\left\\{n-\deg\left(\overline{x^{h}g}\right)\;\mid\;0\leq
h\leq n-1\right\\}.$

It is easy to see that one may compute the apparent distance of a polynomial
$0\neq g\in\mathbb{L}(n)$ as follows. Suppose that $g=\sum a_{i}x^{i}$. If we
associate to the polynomial its coefficient vector
$M(g)=\left(a_{0},\dots,a_{n-1}\right)$ then the apparent distance
$d^{\ast}(g)$ is the length of the biggest chain of consecutive zeros (modulo
$n$) in $M(g)$ plus $1$.

######  Example 6.

Let $f=1+x+x^{4}\in\mathbb{F}_{2}(5)$. Compute $\overline{x^{0}f}=1+x+x^{4}$,
$\overline{xf}=1+x+x^{2}$; $\overline{x^{2}f}=x+x^{2}+x^{3}$;
$\overline{x^{3}f}=x^{2}+x^{3}+x^{4}$; $\overline{x^{4}f}=1+x^{3}+x^{4}$. Then
$d^{\ast}(f)=5-\deg(\overline{xf})=3$.

If we take $M(f)=(1\;1\;0\;0\;1)$ then $d^{\ast}(f)=2+1=3$.

Let $f\in\mathbb{L}(n)$. It is clear that the polynomials $f$ and
$\overline{x^{h}f}$ have the same set of zeros (or root set). Hence,
$\deg\left(\overline{x^{h}f}\right)\geq|D_{\alpha}(f)|$, for any $\alpha\in
U_{n}$, where $D_{\alpha}(f)$ denotes the defining set of $f$. Therefore
$d^{\ast}(f)\leq n-|D_{\alpha}(f)|$ for any $\alpha\in U_{n}$.

Now, by the definition of the inverse Fourier transform (see Remark 3), we
have that

$\omega(f)=n-|D_{\alpha}(\varphi_{\alpha,f})|.$ (2)

Hence,

$d^{\ast}(\varphi_{\alpha,f})\leq
n-|D_{\alpha}(\varphi_{\alpha,f})|=\omega(f),\;\;\text{ for all
}\;\;f\in\mathbb{F}_{q}(n)\;\;\text{ and }\;\;\alpha\in U_{n}.$ (3)

This implies that the minimum of the apparent distances of the images of the
nonzero codewords of a cyclic code is a lower bound for its minimum distance.
Camion’s definition of apparent distance of an abelian code comes from these
ideas. In our case, we present that definition as follows.

######  Definition 7.

Let $C$ be a cyclic code in $\mathbb{F}_{q}(n)$ and consider $\alpha\in
U_{n}$. The apparent distance of $C$ with respect to $\alpha$ is
$d^{\ast}_{\alpha}(C)=\min_{c\in C,\,c\neq
0}\\{d^{\ast}(\varphi_{\alpha,c})\\}$ and the apparent distance of $C$ is

$d^{\ast}(C)=\max_{\alpha\in U_{n}}\\{d^{\ast}_{\alpha}(C)\\}.$

We also define the set of optimal roots of $C$ as

$\mathcal{R}(C)=\left\\{\beta\in
U_{n}\;\mid\;d_{\beta}^{\ast}(C)=d^{\ast}(C)\right\\}.$

For the paragraph prior Definition 7 we have that $d^{\ast}(C)\leq d(C)$ for
any cyclic code $C$. In [1, p. 22] Camion shows that for any cyclic code $C$
the equality $d^{*}(C)=\Delta(C)$ holds.

Note that the value $d^{\ast}(\varphi_{\alpha,c})$ depends on the support of
$\varphi_{\alpha,c}$; that is, it depends on the distribution of the zeros of
$c$ with respect to $\alpha$; so, the minimum $d^{\ast}_{\alpha}(C)$ depends
on the distribution of $D_{\alpha}(C)$. Hence, in order to compute the maximum
$d^{\ast}(C)$ we need to look at the different defining sets of $C$, for each
$\alpha\in U_{n}$. As we have seen in Remark 1, if we fix $\alpha\in U_{n}$
and $\\{a_{1},\dots,a_{h}\\}$, a complete set of representatives of the
$q$-cyclotomic cosets modulo $n$, to consider the different defining sets of
$C$ we only need to consider the roots $\beta\in U_{n}$ such that
$\beta^{a_{i}}=\alpha$ for some $a_{i}$ coprime with $n$. Then, for any
$\alpha\in U_{n}$ we define the set

$\mathcal{R}_{\alpha}=\\{\beta\in U_{n}\;\mid\;\beta^{a}=\alpha,\,\,a\in
A(n)\\}.$ (4)

where $A(n)$ was defined in (1).

Therefore, in practice, to compute the apparent distance of a cyclic code $C$
in $\mathbb{F}_{q}(n)$ it is enough to fix $\alpha\in U_{n}$ and compute
$d^{\ast}(C)=\max\\{d^{\ast}_{\beta}(C)\;\mid\;\beta\in\mathcal{R}_{\alpha}\\}.$

Let $e,g\in C$ be the idempotent generator and the generator polynomial of
$C$, respectively. If $f,h\in\mathbb{F}_{q}(n)$ then
$supp\left(\varphi_{\beta,fh}\right)\subseteq
supp\left(\varphi_{\beta,f}\right)$ because
$\varphi_{\beta,fh}=\varphi_{\beta,f}\star\varphi_{\beta,h}$, and then, for
any $c\in C$, and any $\beta\in U_{n}$, we have that
$supp\left(\varphi_{\beta,c}\right)\subseteq
supp\left(\varphi_{\beta,g}\right)=supp\left(\varphi_{\beta,e}\right)$; so
that,
$d^{\ast}\left(\varphi_{\beta,g}\right)=d^{\ast}\left(\varphi_{\beta,e}\right)\leq
d^{\ast}\left(\varphi_{\beta,c}\right)$. Hence,
$d^{\ast}_{\beta}(C)=d^{\ast}\left(\varphi_{\beta,e}\right)$ and

$\Delta(C)=d^{\ast}(C)=d^{\ast}\left(\varphi_{\beta,e}\right)=d^{\ast}\left(\varphi_{\beta,g}\right)\leq
d(C),\quad\forall\beta\in\mathcal{R}(C).$ (5)

(see [1, p. 22]).

######  Example 8.

Set $q=2$, $n=17$ and take $a_{1}=0,a_{2}=1,a_{3}=3$ as representatives of the
$2$-cyclotomic cosets in ${\mathbb{Z}}_{17}$. Then $A(17)=\\{1,3\\}$. Let $C$
be the cyclic code with defining set
$D_{\alpha}(C)=C_{2}(1)=\\{1,2,4,8,9,13,15,16\\}$ with respect to $\alpha\in
U_{17}$, such that $\mathrm{min}(\alpha)=x^{8}+x^{7}+x^{6}+x^{4}+x^{2}+x+1$.
The reader may check that $e=x^{16}+x^{15}+x^{13}+x^{9}+x^{8}+x^{4}+x^{2}+x+1$
is the idempotent generator of $C$, and
$M(\varphi_{\alpha,e})=(1\,0\,0\,1\,0\,1\,1\,1\,0\,0\,1\,1\,1\,0\,1\,0\,0)$.
Then $d^{\ast}\left(\varphi_{\alpha,e}\right)=3$. Taking $\beta$ such that
$\beta^{3}=\alpha$, one may check that
$d^{\ast}\left(\varphi_{\beta,e}\right)=4$. Hence
$\Delta(C)=d^{\ast}(C)=d^{\ast}\left(\varphi_{\beta,e}\right)=4$.

As an immediate consequence of (5) we have the following corollary.

######  Corollary 9.

Let $C$ be a cyclic code in $\mathbb{F}_{q}(n)$ and let $e,g\in C$ be the
idempotent generator and the generator polynomial of $C$, respectively. For
$f\in\\{e,g\\}$ we have that if $d^{\ast}(\varphi_{\alpha,f})=\omega(f)$ for
some $\alpha\in U_{n}$ then $d(C)=\Delta(C)$ and $\alpha\in\mathcal{R}(C)$.

###### Proof.

By hypothesis, $d^{\ast}(\varphi_{\alpha,f})=\omega(f)\geq d(C)$. Now, if
$\beta\in\mathcal{R}(C)$ then $d^{\ast}(\varphi_{\alpha,f})\leq
d^{\ast}(\varphi_{\beta,f})$ and so (5) get us the result. ∎

In the following table we list non trivial cyclic codes of lenght at most 31,
satifying the conditions of the corollary above; that is,
$d^{*}\varphi_{\alpha,f}=\omega(f)$ for some $\alpha\in U_{n}$. Here,
$\overline{D(C)}={\mathbb{Z}}_{n}\setminus D(C)$. Computations were done by
using GAP4r7.

$\begin{array}[]{|c|c|c|c|}\hline\cr\text{Lenght}&\overline{D(C)}&\dim_{\mathbb{F}}(C)&d(C)\\\
\hline\cr 7&C_{2}(3)&3&4\\\ \hline\cr&C_{2}(1)&3&4\\\ \hline\cr&C_{2}(0)\cup
C_{2}(3)&4&3\\\ \hline\cr&C_{2}(0)\cup C_{2}(1)&4&3\\\ \hline\cr
9&C_{2}(3)&2&6\\\ \hline\cr&C_{2}(0)\cup C_{2}(3)&3&3\\\
\hline\cr&C_{2}(1)&6&2\\\ \hline\cr\end{array}$

$\begin{array}[]{|c|c|c|c|}\hline\cr\text{Lenght}&\overline{D(C)}&\dim_{\mathbb{F}}(C)&d(C)\\\
\hline\cr 15&C_{2}(5)&2&10\\\ \hline\cr&C_{2}(0)\cup C_{2}(5)&3&5\\\
\hline\cr&C_{2}(1)&4&8\\\ \hline\cr&C_{2}(7)&4&8\\\ \hline\cr&C_{2}(0)\cup
C_{2}(3)&5&3\\\ \hline\cr&C_{2}(0)\cup C_{2}(7)&5&7\\\ \hline\cr&C_{2}(0)\cup
C_{2}(1)&5&7\\\ \hline\cr&C_{2}(3)\cup C_{2}(5)&6&6\\\ \hline\cr&C_{2}(0)\cup
C_{2}(5)\cup C_{2}(7)&7&5\\\ \hline\cr&C_{2}(1)\cup C_{2}(3)&8&4\\\
\hline\cr&C_{2}(3)\cup C_{2}(7)&8&4\\\ \hline\cr&C_{2}(3)\cup C_{2}(7)&8&4\\\
\hline\cr&C_{2}(1)\cup C_{2}(5)\cup C_{2}(7)&10&2\\\ \hline\cr
21&C_{2}(7)&2&14\\\ \hline\cr&C_{2}(3)&3&12\\\ \hline\cr&C_{2}(9)&3&12\\\
\hline\cr&C_{2}(0)\cup C_{2}(7)&3&7\\\ \hline\cr&C_{2}(0)\cup C_{2}(3)&4&9\\\
\hline\cr&C_{2}(0)\cup C_{2}(9)&4&9\\\ \hline\cr&C_{2}(3)\cup C_{2}(7)&5&10\\\
\hline\cr&C_{2}(7)\cup C_{2}(9)&5&10\\\ \hline\cr&C_{2}(0)\cup C_{2}(3)\cup
C_{2}(9)&7&3\\\ \hline\cr&C_{2}(1)\cup C_{2}(7)&8&6\\\ \hline\cr&C_{2}(5)\cup
C_{2}(7)&8&6\\\ \hline\cr&C_{2}(1)\cup C_{2}(9)&9&4\\\ \hline\cr&C_{2}(3)\cup
C_{2}(5)&9&4\\\ \hline\cr&C_{2}(0)\cup C_{2}(5)\cup C_{2}(9)&10&5\\\
\hline\cr&C_{2}(0)\cup C_{2}(1)\cup C_{2}(3)&10&5\\\ \hline\cr&C_{2}(5)\cup
C_{2}(7)\cup C_{2}(9)&11&6\\\ \hline\cr&C_{2}(0)\cup C_{2}(1)\cup C_{2}(7)\cup
C_{2}(9)&12&3\\\ \hline\cr 25&C_{2}(3)\cup C_{2}(5)&5&5\\\ \hline\cr
27&C_{2}(9)&2&18\\\ \hline\cr&C_{2}(3)&5&6\\\ \hline\cr&C_{2}(1)&18&2\\\
\hline\cr&C_{2}(0)\cup C_{2}(9)&3&9\\\ \hline\cr 31&C_{2}(1)&5&16\\\
\hline\cr&C_{2}(5)&5&16\\\ \hline\cr&C_{2}(15)&5&16\\\ \hline\cr&C_{2}(0)\cup
C_{2}(1)&6&15\\\ \hline\cr&C_{2}(0)\cup C_{2}(15)&6&15\\\
\hline\cr&C_{2}(3)\cup C_{2}(7)&10&6\\\ \hline\cr&C_{2}(5)\cup
C_{2}(11)&10&10\\\ \hline\cr&C_{2}(1)\cup C_{2}(3)\cup C_{2}(15)&15&6\\\
\hline\cr&C_{2}(1)\cup C_{2}(5)\cup C_{2}(11)&15&6\\\ \hline\cr&C_{2}(1)\cup
C_{2}(7)\cup C_{2}(15)&15&6\\\ \hline\cr&C_{2}(5)\cup C_{2}(9)\cup
C_{2}(15)&15&6\\\ \hline\cr&C_{2}(0)\cup C_{2}(1)\cup C_{2}(3)\cup
C_{2}(7)&16&5\\\ \hline\cr&C_{2}(0)\cup C_{2}(1)\cup C_{2}(11)\cup
C_{2}(15)&16&5\\\ \hline\cr&C_{2}(0)\cup C_{2}(1)\cup C_{2}(5)\cup
C_{2}(15)&16&5\\\ \hline\cr&C_{2}(0)\cup C_{2}(3)\cup C_{2}(5)\cup
C_{2}(11)&16&5\\\ \hline\cr&C_{2}(0)\cup C_{2}(5)\cup C_{2}(7)\cup
C_{2}(11)&16&5\\\ \hline\cr&C_{2}(0)\cup C_{2}(3)\cup C_{2}(5)\cup
C_{2}(11)&16&5\\\ \hline\cr\end{array}$

Let us comment how these results allow us to construct cyclic codes and to
compute its apparent distance (or the BCH bound). First, let us observe that
for any cyclic code $C$ generated by $e=e^{2}\in\mathbb{F}_{q}(n)$ one has
that $\varphi_{\alpha,e}$ is an idempotent in $(\mathbb{L},\star)$. So,
$\varphi_{\alpha,e}[i]=e(\alpha^{i})=0$ if $i\in D_{\alpha}(C)$ and $1$
otherwise.

Now, let $\\{a_{1},\dots,a_{h}\\}$ be a complete set of represantives of the
$q$-cyclotomic cosets modulo $n$. For each choice
$D=\cup_{j=1}^{t}C_{q}(a_{i_{j}})$, with $i_{j}\in\\{1,\dots,h\\}$ and $1\leq
t\leq h$, we denote by $F_{D}\in\mathbb{F}_{q}^{n}$ the vector such that
$F_{D}[i]=0$ if $i\in D$ and $1$ otherwise. Then $F_{D}$ may be viewed as the
image under the Fourier transform of the idempotent generator of a cyclic code
$C$ in $\mathbb{F}_{q}(n)$ such that $D=D_{\alpha}(C)$ with respect to some
$\alpha\in U_{n}$. That is, if $C$ is the cyclic code with defining set
$D_{\alpha}(C)=D$, with respecct to $\alpha\in U_{n}$, and $e^{2}=e$ is its
idempotent generator then we have that
$F_{D}=\varphi_{\alpha,e}\in\mathbb{F}_{q}^{n}$. To compute the apparent
distance $d^{\ast}(C)$ we first consider the set
$A(n)=\\{a_{i_{1}},\dots,a_{i_{k}}\\}\subseteq\\{a_{1},\dots,a_{h}\\}$. Then,
for every $j=1,\dots,k$, let $\beta_{j}\in U_{n}$ be such that
$\beta_{j}^{a_{i_{j}}}=\alpha$; recall that this implies
$D_{\beta_{j}}(C)=a_{i_{j}}\cdot D_{\alpha}(C)$. The apparent distance of
$\varphi_{\beta_{j},e}$ is the length of the biggest chain of consecutive
zeros (modulo $n$) in $F_{D_{\beta_{j}}(C)}$ plus $1$. So, $\displaystyle
d^{\ast}(C)=\max_{j=1,\dots,k}d^{\ast}(F_{D_{\beta_{j}}(C)})$.

######  Example 10.

Set $n=21$, $q=2$ and $A(21)=\\{1,5\\}$. Consider the $2$-cyclotomic cosets:
$C_{2}(0)$, $C_{2}(1)$, $C_{2}(3)$, $C_{2}(5)$, $C_{2}(7)$, $C_{2}(9)$ listed
in Example 2. Choose $D=C_{2}(1)\cup C_{2}(3)\cup C_{2}(7)$. Then

$\displaystyle F_{D}$ $\displaystyle=$
$\displaystyle\left(1\,0\,0\,0\,0\,1\,0\,0\,0\,1\,1\,0\,0\,1\,0\,1\,0\,1\,1\,1\,1\right).$

Let $C=\left\langle e\right\rangle$ be the cyclic code such that
$D_{\alpha}(C)=D$ for some $\alpha\in U_{21}$. Then
$d^{\ast}(\varphi_{\alpha,e})=5$. We only need to consider $\beta\in U_{21}$
such that $\beta^{5}=\alpha$. In that case, $D_{\beta}(C)=5\cdot
D_{\alpha}(C)=C_{2}(5)\cup C_{2}(9)\cup C_{2}(7)$. Then

$\displaystyle F_{D_{\beta}(C)}$ $\displaystyle=$
$\displaystyle\left(1\,1\,1\,1\,1\,0\,1\,0\,1\,0\,0\,1\,1\,0\,0\,0\,1\,0\,0\,0\,0\right).$

So $d^{\ast}(F_{D_{\beta}(C)})=5$ too. Hence $d^{\ast}(C)=5$ and
$\mathcal{R}(C)=\\{\beta,\beta^{5}\\}$. The reader may check that $C$ has four
BCH bounds, $\delta=2,3,4,5$.

##  III The minimum distance and the BCH bound

For an arbitrary element $g\in\mathbb{L}(n)$, which we may view as a
polynomial with $\deg(g)\leq n-1$, it is easy to see that the equality
$\gcd(g,x^{n}-1)=\gcd(x^{h}g,x^{n}-1)$ holds for any $h\in\\{0,\dots,n-1\\}$
as $x^{h}$ and $x^{n}-1$ are relatively prime polynomials; so, we may write

$m_{g}=\gcd(x^{h}g,x^{n}-1)$ (6)

as $m_{g}$ does not depend on $h$. For any $h\in\\{0,\dots,n-1\\}$ we also
write

$x^{h}g=(x^{n}-1)f_{g,h}+\overline{x^{h}g}$ (7)

where $0\leq\deg(\overline{x^{h}g})<n$. Note that if $g\neq 0$ then
$\overline{x^{h}g}\neq 0$ because $\deg(g)<n$. By using results in [1] and [3]
(see also [6, Theorem 8.6.31]) we obtain the following result.

######  Lemma 11.

Consider $g\in\mathbb{L}(n)$ and let $m_{g}$ be as above. Then

  1. 1.

$d^{\ast}(g)\leq n-\deg(m_{g})$.

  2. 2.

If $g\mid x^{n}-1$ then $d^{\ast}(g)=n-\deg(g)$.

###### Proof.

(1) It comes from the fact that $m_{g}\mid\overline{x^{h}g}$ for any $0\leq
h\leq n-1$, and from Definition 5. (2) By the definition of $d^{\ast}(g)$ we
have that $d^{\ast}(g)\geq n-\deg(g)$. To get the converse inequality note
that $g=sm_{g}$, for some $s\in\mathbb{F}_{q}$, and apply (1). ∎

Now let $C$ be a cylic code in $\mathbb{F}_{q}(n)$ and let $c\in C$ be any
codeword. By (3) we have that $d^{\ast}(\varphi_{\alpha,c})\leq\omega(c)$. We
wonder if the equality may occur. Next result will be helpful to find an
answer (see [1, Theorem 4.1] and [3, Theorem 2]).

######  Lemma 12.

Let $C$ be a cyclic code in $\mathbb{F}_{q}(n)$ and $c\in C$. Then
$n-\deg\left(m_{\varphi_{\alpha,c}}\right)=\omega(c)$, for all $\alpha\in
U_{n}$.

###### Proof.

We have that
$n-\deg\left(m_{\varphi_{\alpha,c}}\right)=|\\{\alpha^{j}\;\mid\;\varphi_{\alpha,c}(\alpha^{j})\neq
0\\}|$. By Remark 3 and (2) we are done. ∎

Note that by Lemma 11 we have that the apparent distance of any
$f\in\mathbb{L}(n)$ is less than or equal to the number of nonzeros of
$m_{f}$. The following result shows us when the equality holds.

######  Proposition 13.

Consider $f\in\mathbb{L}(n)$ and let $m_{f}$ be as in (6). Then
$d^{\ast}(f)=n-\deg(m_{f})$ if and only if there exists
$h\in\\{0,\dots,n-1\\}$ such that $\overline{x^{h}f}\mid x^{n}-1$
(equivalently, $\overline{x^{h}f}$ and $m_{f}$ are associated polynomials in
$\mathbb{L}[x]$).

###### Proof.

Suppose first that the equality holds. By definition of apparent distance we
know that there exists $h\in\\{0,\dots,n-1\\}$ such that
$d^{\ast}(f)=n-\deg\left(\overline{x^{h}f}\right)$. Hence
$\deg\left(\overline{x^{h}f}\right)=\deg\left(m_{f}\right)$. By (6) and (7) we
have that $m_{f}$ and $\overline{x^{h}f}$ have exactly the same set of zeros
and hence they are associated polynomials, or equivalently,
$\overline{x^{h}f}\mid x^{n}-1$.

Conversely, suppose that there exists $h\in\\{0,\dots,n-1\\}$ such that
$\overline{x^{h}f}\mid x^{n}-1$. Again by (7) and (6), $\overline{x^{h}f}$ and
$m_{f}$ must be associated polynomials. By definition of apparent distance we
have that $d^{\ast}(f)=d^{\ast}\left(\overline{x^{h}f}\right)$ and by Lemma
11(2),
$d^{\ast}\left(\overline{x^{h}f}\right)=n-\deg\left(\overline{x^{h}f}\right)$.
The result follows immediately. ∎

Now we deal with our first problem. We are going to present some results that
give theoretical characterizations for a given cyclic code to satisfy the
equality $d(C)=\Delta(C)$.

######  Theorem 14.

Let $n$ be a positive integer, $p$ a prime number and $q$ a power of $p$.
Assume that $\gcd(n,q)=1$. Consider the field $\mathbb{F}_{q}$ and an
extension $\mathbb{L}|\mathbb{F}_{q}$ such that $U_{n}\subseteq\mathbb{L}$.
Let $C$ be a cyclic code in $\mathbb{F}_{q}(n)$. Then $d(C)=\Delta(C)$ if and
only if there exists a polynomial $f\in\mathbb{L}(n)$, such that

  1. 1.

$d^{\ast}(f)=d^{\ast}(C)$.

  2. 2.

$d^{\ast}(f)=n-\deg(m_{f})$.

  3. 3.

$\varphi^{-1}_{\alpha,f}\in C$, for some $\alpha\in\mathcal{R}(C)$.

Moreover, in this case, there exists $h\in\\{0,\dots,n-1\\}$ such that
$\overline{x^{h}f}\mid x^{n}-1$.

###### Proof.

First, suppose that $d(C)=\Delta(C)$. Then we have that $d(C)=d^{\ast}(C)$.
Let $c\in C$ such that $\omega(c)=d(C)$, consider $\alpha\in\mathcal{R}(C)$
and set, as in (6), $m_{\varphi_{\alpha,c}}=\gcd(\varphi_{\alpha,c},x^{n}-1)$.
By definition of apparent distance and by applying results above, we have that

$\omega(c)\geq d^{\ast}(\varphi_{\alpha,c})\geq
d^{\ast}_{\alpha}(C)=d^{\ast}(C)=d(C)=\omega(c)=n-\deg\left(m_{\varphi_{\alpha,c}}\right).$

Hence $d^{\ast}(\varphi_{\alpha,c})=d^{\ast}(C)$, since
$d^{\ast}\left(\varphi_{\alpha,c}\right)=n-\deg\left(m_{\varphi_{\alpha,c}}\right)$.
So, $f=\varphi_{\alpha,c}$ satisfies all required conditions.

Conversely, suppose there exists $f\in\mathbb{L}(n)$ satisfying conditions (1
– 3) of the statement. By Lemma 12 and the definition of minimum distance, we
have that $d^{\ast}(f)=\omega(\varphi^{-1}_{\alpha,f})\geq d(C)$. Then by
Condition (1), $d^{\ast}(C)\geq d(C)$, and hence by (5), $\Delta(C)=d(C)$.

The final assertion follows directly from Proposition 13. ∎

So, to check if a code satisfies the conditions in the theorem above,
Proposition 13 shows us that we have to focus on properties of some divisors
of $x^{n}-1$. After Corollary 16 we will make some comments about complexity
in order to consider those divisors.

######  Corollary 15.

Let $C$ be a cyclic code in $\mathbb{F}_{q}(n)$. Then $d(C)=\Delta(C)$ if and
only if there exist $k\in\\{0,\dots,n-1\\}$ and a divisor $g\mid x^{n}-1$, in
$\mathbb{L}[x]$, such that setting $f=\overline{x^{k}g}$, the following
conditions hold

  1. 1.

$d^{\ast}(f)=d^{\ast}(C)$ .

  2. 2.

$\varphi^{-1}_{\alpha,f}\in C$, for some $\alpha\in\mathcal{R}(C)$.

###### Proof.

Set $h=n-k$. Then $g=\overline{x^{h}f}$ and the result follows from
Proposition 13 and the theorem above. ∎

We note that, in the setting of the previous corollary, it may happen that
there exist $\alpha,\beta\in U_{n}$ such that $\varphi^{-1}_{\alpha,f}\in C$
but $\varphi^{-1}_{\beta,f}\notin C$.

We may rewrite the condition (3) in Theorem 14 or (2) in Corollary 15, as
follows.

######  Corollary 16.

Let $C$ be a cyclic code in $\mathbb{F}_{q}(n)$. Then $d(C)=\Delta(C)$ if and
only if there exist $k\in\\{0,\dots,n-1\\}$ and a divisor $g\mid x^{n}-1$, in
$\mathbb{L}[x]$, such that the following conditions hold.

  1. 1.

$d^{\ast}(g)=d^{\ast}(C)$, and setting $f=\overline{x^{k}g}$,

  2. 2.

$supp(f)\subseteq{\mathbb{Z}}_{n}\setminus D_{\alpha}(C)$, for some
$\alpha\in\mathcal{R}(C)$,

  3. 3.

$(f(\alpha^{j}))^{q}=f(\alpha^{j})$, for any $j\in\\{0,\dots,n-1\\}$.

###### Proof.

From Remark 3, it comes immediately that condition (2) in Corollary 15 holds
if and only if conditions (2)+(3) of this corollary hold. ∎

Given a linear code $C$ of length $n$, we wonder about how difficult is to
check the equality $\Delta(C)=d(C)$; in other words, using our previous
results, how difficult is to find a polynomial satisfying the required
conditions?

To apply any of the corollaries above we have to compute the divisors $g\mid
x^{n}-1$ in $\mathbb{L}[x]$ with $\deg(g)=n-\Delta(C)$. This means that we
have to check at most $h\cdot\binom{n}{n-\Delta(C)}$ polynomials, where
$h=|A(n)|$. Clearly, if $\Delta(C)$ is not a “big” number we may check all
divisors in $\mathbb{L}[x]$. In case that $\Delta(C)$ was a “big” number, we
could reduce it by taking an intermediate field,
$\mathbb{F}_{q}\subset\mathbb{K}\subset\mathbb{L}$, where the number of
divisors of $x^{n}-1$ (in $\mathbb{K}[x]$) is smaller. However, in that case,
our searching of codes would not be exhaustive.

For example, consider the binary cyclic code $C$ of length $45$ with
$D_{\alpha}(C)=C_{2}(3)\cup C_{2}(5)$, for some $\alpha\in U_{45}$. One may
see that $\Delta(C)=3$ and $\dim(C)=35$. Consider $A(45)=\\{1,7\\}$. To check
any of our corollaries above we have to consider $2\binom{45}{42}$-polynomials
(note that $2^{14}<2\binom{45}{42}<2^{15}$) so our method works. On the other
hand, for codes with apparent distance greater than $5$, we might choose to
consider the factors of $x^{45}-1$ in an intermediate ring. For example, in
$\mathbb{F}_{2^{4}}[x]$ there are 15 factors of degree 1 and 10 factors of
degree 3. No more than 50 computations. Essentially the same happens in
$\mathbb{F}_{2^{6}}[x]$.

Now we give another sufficient condition to characterize cyclic codes whose
apparent distance reaches its minimum distance.

######  Corollary 17.

Let $C$ be a cyclic code in $\mathbb{F}_{q}(n)$ with generator idempotent
$e\in C$. If there exist $h\in\\{0,\dots,n-1\\}$ and $\alpha\in U_{n}$ such
that $\overline{x^{h}\varphi_{\alpha,e}}\mid x^{n}-1$ then $d(C)=\Delta(C)$
and $\alpha\in\mathcal{R}(C)$.

###### Proof.

From Proposition 13 and Lemma 12 we may deduce that
$d^{\ast}\left(\varphi_{\alpha,e}\right)=n-\deg\left(m_{\varphi_{\alpha,e}}\right)=\omega(e)$.
So, the result follows directly from Corollary 9. ∎

The previous results give us conditions for a cyclic code $C$ to satisfy the
equality $d(C)=\Delta(C)$. Now we deal with our second problem, that is, the
construction of such kind of codes.

######  Corollary 18.

Consider an intermediate field
$\mathbb{F}_{q}\subseteq\mathbb{K}\subseteq\mathbb{L}$, let
$g\in\mathbb{K}[x]$ be a divisor of $x^{n}-1$ and $\beta\in U_{n}$. If
$\varphi^{-1}_{\beta,_{\overline{x^{k}g}}}$ belongs to $\mathbb{F}_{q}(n)$,
for some $k\in\\{0,\dots,n-1\\}$, then the family of permutation equivalent
cyclic codes
$\left\\{C_{\alpha}=\left(\varphi^{-1}_{\alpha,_{\overline{x^{k}g}}}\right)\;\mid\;\alpha\in
U_{n}\right\\}$ satisfies $\Delta(C_{\alpha})=d(C_{\alpha})$ for all
$\alpha\in U_{n}$. Moreover, in this case,
$\dim_{\mathbb{F}_{q}}(C_{\alpha})=|supp(g)|$, for all $\alpha\in U_{n}$.

###### Proof.

Fix $\alpha\in U_{n}$. Set $f=\overline{x^{k}g}$ and let
$e\in\mathbb{F}_{q}(n)$ be the idempotent generator of the ideal
$C=\left(\varphi^{-1}_{\alpha,f}\right)$ in $\mathbb{F}_{q}(n)$ (see Remark
3(4)). It is easy to check that
$supp(\varphi_{\alpha,e})=supp(f)={\mathbb{Z}}_{n}\setminus D_{\alpha}(C)$ and
hence, $d^{\ast}(\varphi_{\alpha,e})=d^{\ast}(f)$. On the one hand, by
Proposition 13 and Lemma 12 one has that
$d^{\ast}f=n-deg(m_{f})=\omega\left(\varphi^{-1}_{\beta,f}\right)\geq d(C)$.
On the other hand, by (5),
$d^{\ast}f=d^{\ast}\left(\varphi_{\alpha,e}\right)\leq
d^{\ast}_{\alpha}(C)\leq d^{\ast}(C)\leq d(C)$. So we are done. ∎

Then, in order to construct codes with the desired property we need to find a
divisor $g$ of $x^{n}-1$ satisfying the condition (2) in Corollary 15.
However, in the case $\mathbb{K}=\mathbb{F}_{2}$, it is clear that
$g\in(\mathbb{F}_{2}^{n},\star)$ is always an idempotent, and so, we only have
to check that $supp(g)$ is union of $2$-cyclotomic cosets (see Lemma 4).

Let us show by an example how the combination of Corollary 16 and Corollay 18
works.

######  Example 19.

Set $q=2$, $n=45$. In this case $A(45)=\\{1,7\\}.$ Take
$g=x^{40}+x^{39}+x^{38}+x^{36}+x^{35}+x^{32}+x^{30}+x^{25}+x^{24}+x^{23}+x^{21}+x^{20}+x^{17}+x^{15}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{2}+1$.
One may check that $g\mid x^{45}-1$ in $\mathbb{F}_{2}[x]$ (so that
$\mathbb{K}=\mathbb{F}_{2}$). To find the parameter $k$ mentioned in the
corollary above, we may analize the vector $M(g)$ or we may fix $\beta\in
U_{45}$ (as instance, such that $\mathrm{min}(\beta)=x^{12}+x^{3}+1$) and
compute $g(1)$ and $g(\beta^{3})$, because
$D_{\beta}(g)={\mathbb{Z}}_{45}\setminus\left(C_{2}(0)\cup C_{2}(3)\right)$.
Let us choose the last alternative. Since $g(1)=1$ and
$g(\beta^{3})=\beta^{30}$ then $k=5$ will work because setting $f=x^{5}g$ we
have that $f(1)=1$,
$f\left(\beta^{3}\right)=(\beta^{3})^{5}\beta^{30}=\beta^{45}=1$ and then
$f\left(\beta^{6}\right)=f\left(\beta^{12}\right)=f\left(\beta^{24}\right)=1$,
as $C_{2}(3)=\\{3,6,12,24\\}$. So that,
$\varphi^{-1}_{\alpha,f}\in\mathbb{F}(45)$, for all $\alpha\in U_{45}$. Now
set $C=(\varphi^{-1}_{\beta,f})$. Then $D_{\beta}(C)=C_{2}(1)\cup C_{2}(3)\cup
C_{2}(9)\cup C_{2}(21)={\mathbb{Z}}_{45}\setminus supp(M(f))$ and, by
analizing $M(g)$ or $M(f)=F_{D_{\beta}(C)}$ as in Example 10, we have that
$5=d(C)=\Delta(C)$ and $\dim(C)=21$.

As $supp(x^{5}g)={\mathbb{Z}}_{45}\setminus D_{\beta}(C)$, one may see that
there are three subsets that determines $d^{\ast}(C)$; to wit,
$\\{1,2,3,4\\}$, $\\{16,17,18,19\\}$ and $\\{31,32,33,34\\}$. We choose
$\\{1,2,3,4\\}\subset D_{\beta}(C)$ and construct the code $C^{\prime}$ such
that $D_{\beta}(C^{\prime})=D_{\beta}(C)\setminus C_{2}(21)$. Note that $C$ is
a subcode of $C^{\prime}$, because $D_{\beta}(C^{\prime})\subset
D_{\beta}(C)$. Now one has that $C^{\prime}$ satisfies the conditions in
Corollary 15, because $d^{\ast}(C)=5=d^{\ast}(f)$ and
$\varphi^{-1}_{\alpha,f}\in C\subset C^{\prime}$, so that
$5=d(C^{\prime})=\Delta(C^{\prime})$ and $\dim(C^{\prime})=25$, that is,
$C^{\prime}$ has better parameters than $C$.

In the next section (see, as instance, Example 25) we will refine this type of
construction to obtain BCH codes $C$ such that $\Delta(C)=d(C)$. Now we
continue with the construction of codes $C$ satisfying that $\Delta(C)=d(C)$.

######  Corollary 20.

Consider an intermediate field
$\mathbb{F}_{q}\subseteq\mathbb{F}_{q^{\prime}}\subseteq\mathbb{L}$, let $h$
be an irreducible factor of $x^{n}-1$ in $\mathbb{F}_{q^{\prime}}[x]$ with
defining set $D_{\alpha}(h)$ for some $\alpha\in U_{n}$. Set $g=(x^{n}-1)/h$.
If there are positive integers $j,t$ such that $g(\alpha^{j})=\alpha^{t}$ and
$\gcd\left(j,\frac{n}{\gcd(q-1,n)}\right)\mid t$ then there exists a $q$-ary
code of length $n$ whose BCH bound equals its minimum distance.

###### Proof.

By hypothesis, the congruence (in $X$),

$\frac{q-1}{\gcd(q-1,n)}jX\equiv-\frac{q-1}{\gcd(q-1,n)}t\mod\frac{n}{\gcd(q-1,n)}$

has a solution $X=k$, with $0\leq k\leq\frac{n}{\gcd(q-1,n)}$. Then
$(q-1)(jk+t)\equiv 0\mod n$, which means that $q(jk+t)\equiv jt+k\mod n$, and
hence $\overline{x^{k}g}(\alpha^{j})=\alpha^{jk+t}\in\mathbb{F}_{q}$. Clearly,
for any $jq^{\prime a}\in D_{\alpha}(h)$ we have $jq^{\prime a}k+tq^{\prime
a}\equiv q^{\prime a}(jk+t)\equiv jk+t\mod n$, so that
$\overline{x^{k}g}(\alpha^{jq^{\prime a}})\in\mathbb{F}_{q}$. As
$\overline{x^{k}g}(\alpha^{i})=0$ for all $i\in{\mathbb{Z}}_{n}\setminus
D_{\alpha}(h)$, we may apply Corollary 18 to get the desired result. More
precisely, the code
$C=\left(\varphi^{-1}_{\alpha,\overline{x^{k}g}}\right)\subseteq\mathbb{F}_{q}(n)$
satisfies the required conditions. ∎

######  Corollary 21.

Let $n=2^{m}-1$, for some $m\in{\mathbb{N}}$. There exist at least
$\frac{\phi\left(n\right)}{m}$ binary codes of length $n$ whose BCH bound
equals its minimum distance.

###### Proof.

We are going to apply the corollary above with $2=q=q^{\prime}$. Take
$\mathbb{L}=\mathbb{F}_{2^{m}}$. For each $0<j<n$, coprime with $n$, we
consider the $2$-cyclotomic coset $C_{2}(j)$, which has exactly $m$ elements.
Consider $\alpha\in U_{n}$. Let $h|x^{n}-1$ be the polynomial in
$\mathbb{F}_{q}[x]$, such that $D_{\alpha}(h)=C_{2}(j)$ and
$g_{j}=(x^{n}-1)/h$. By hypothesis, $\alpha$ is a primitive element for
$\mathbb{L}$, so that $g_{j}(\alpha^{j})=\alpha^{k}$ for some
$k\in{\mathbb{Z}}_{n}$. The condition $\gcd\left(j,n\right)\mid k$ holds
obviously. So that there exists a binary code of length $n$ whose BCH bound
equals its minimum distance. Moreover, by Corollary 18 the family of codes
$\\{C_{j}=\left(\varphi^{-1}_{\alpha,\overline{x^{k}g_{j}}}\right)\mid\gcd(j,n)=1\\}$
satisfies that $d(C_{j})=\Delta(C_{j})$ for any $j$. To compute the number of
different codes in that family we consider the set
$B=\\{C_{2}(j)\;\mid\;j\in{\mathbb{Z}}_{n},\gcd(j,n)=1\\}$. One may check that
$|B|=\frac{\phi\left(n\right)}{m}$. Let $C_{q}(j)\neq C_{q}(j^{\prime})\in B$.
If $\alpha\in U_{n}$ and $h,h^{\prime}$ are the divisors of $x^{n}-1$ with
$D_{\alpha}(h)=C_{q}(j)$ and $D_{\alpha}(h^{\prime})=C_{q}(j^{\prime})$ then
$g_{j}=(x^{n}-1)/h$ and $g_{j^{\prime}}=(x^{n}-1)/h^{\prime}$ have the same
degree, and hence $supp(g_{j})\neq supp(g_{j^{\prime}})$ because they are
binary polynomials. Since $D(C_{j})=supp(\overline{x^{k}g_{j}})$ the result
comes immediately. ∎

######  Example 22.

Set $q=2$, $n=15$. Then $A(15)=\\{1,7\\}$. By Corollary 21 there exist at
least two codes such that its BCH bound equals its minimum distance (they will
be determined by the polynomials $g_{3}$ and $g_{4}$ defined below). Denote
the irreducible factors of $x^{15}-1$ in $\mathbb{F}_{2}[x]$, by
$h_{1}=\Phi_{2}$, $h_{2}=\Phi_{3}$, $h_{3}=x^{4}+x+1$, $h_{4}=x^{4}+x^{3}+1$
and $h_{5}=\Phi_{5}$, where $\Phi_{j}$ denotes the $j$-th cyclotomic
polynomial. Setting $g_{i}=\frac{x^{n}-1}{h_{i}}$, $i=1,\dots,5$, we apply the
corollaries above (with $\mathbb{K}=\mathbb{F}_{2}$) as follows.

Consider the factor $g_{2}$. Then one may check that in this case
$\varphi^{-1}_{\alpha,{\overline{xg_{2}}}}=x^{10}+x^{5}\in\mathbb{F}_{2}(15)$,
for all $\alpha\in U_{15}$. The cyclic code $C$ generated by $x^{10}+x^{5}$
satisfies $\dim(C)=10$ and $\Delta(C)=2=d(C)$. Now let us fix $\alpha\in
U_{15}$ such that $h_{3}=\mathrm{min}(\alpha)$ and
$h_{4}=\mathrm{min}(\alpha^{13})$, where $\mathrm{min}(\alpha^{t})$ denotes
the minimal polynomial of $\alpha^{t}$ in $\mathbb{F}_{2}[x]$. Then
$\varphi^{-1}_{\alpha,{\overline{xg_{3}}}}=x^{14}+x^{13}+x^{11}+x^{7}\in\mathbb{F}_{2}(15)$
and
$\varphi^{-1}_{\alpha,{\overline{x^{3}g_{4}}}}=x^{8}+x^{4}+x^{2}+x\in\mathbb{F}_{2}(15)$.
This gives us the table

$\begin{array}[]{|l|l|l|}\hline\cr\text{Generator}&\text{Dimension}&\Delta=d\\\
\hline\cr\varphi^{-1}_{\alpha,{\overline{xg_{2}}}}&10&2\\\
\hline\cr\varphi^{-1}_{\alpha,{\overline{xg_{3}}}}&8&4\\\
\hline\cr\varphi^{-1}_{\alpha,{\overline{x^{3}g_{4}}}}&8&4\\\
\hline\cr\end{array}$

The polynomial $g_{1}$ gets an improper code. In the case of $g_{5}$, as
$D_{\alpha}(g_{5})={\mathbb{Z}}_{15}\setminus C_{2}(3)$, it happens that,
$g_{5}\left(\alpha^{3}\right)=\alpha^{14}$, so the conditions of Corollary 20
are not satisfied.

After inspecting the divisors of $x^{15}-1$ in $\mathbb{F}_{2}[x]$ we find
more interesting codes. For instance, one may check that the polynomial
$h_{2}h_{3}h_{5}$ satisfies the conditions of Corollary 18, with $k=0$, and
hence it yields a code, say $C^{\prime}$, such that
$\Delta(C^{\prime})=d(C^{\prime})=5$ and $\dim(C^{\prime})=7$.

######  Example 23.

Set $q=2$ and $n=21$. Denote the irreducible factors of $x^{21}-1$ in
$\mathbb{F}_{2}[x]$ by $h_{1}=\Phi_{2}$, $h_{2}=\Phi_{3}$, $h_{3}=x^{3}+x+1$,
$h_{4}=x^{3}+x^{2}+1$, $h_{5}=x^{6}+x^{4}+x^{2}+x+1$ and
$h_{6}=x^{6}+x^{5}+x^{4}+x^{2}+1$.

Set $g_{i}=\frac{x^{n}-1}{h_{i}}$, $i=1,\dots,6$, and fix $\alpha\in U_{21}$
such that $\mathrm{min}(\alpha)=h_{6}$. We apply Corollary 20 as above (with
$\mathbb{K}=\mathbb{F}_{2}$) to get the following table of binary codes of
length 21 whose BCH bound equals its minimum distance. We complete with
another one satisfying the conditions of Corollary 18.

$\begin{array}[]{|l|l|l|}\hline\cr\text{Generator}&\text{Dimension}&\Delta=d\\\
\hline\cr\varphi_{\alpha,\overline{xg_{2}}}^{-1}&14&2\\\
\hline\cr\varphi_{\alpha,g_{3}}^{-1}&12&3\\\
\hline\cr\varphi_{\alpha,\overline{x^{3}g_{4}}}^{-1}&12&3\\\
\hline\cr\varphi_{\alpha,\overline{xg_{5}}}^{-1}&8&6\\\
\hline\cr\varphi_{\alpha,\overline{x^{5}g_{6}}}^{-1}&8&6\\\
\hline\cr\varphi_{\alpha,\overline{h_{1}h_{3}h_{5}h_{6}}}^{-1}&10&5\\\
\hline\cr\end{array}$

##  IV Applications: Constructing BCH codes whose minimum distance equals
their apparent distance

The following result allows us to construct BCH codes $B_{q}(\alpha,\delta,b)$
for which $d(B_{q}(\alpha,\delta,b))=\Delta(B_{q}(\alpha,\delta,b))=\delta$.
We recall that the ideal generated by a polynomial $g\in\mathbb{F}_{q}(n)$ is
denoted by $(g)$.

######  Theorem 24.

Let $n$ be a positive integer, $p$ a prime number, $q$ a power of $p$ and
$U_{n}$ the set of primitive $n$-th roots of unity. Assume that $\gcd(n,q)=1$.
Consider the fields $\mathbb{F}_{q}\subseteq\mathbb{K}\subseteq\mathbb{L}$
such that $U_{n}\subset\mathbb{L}$. Let $g\in\mathbb{K}[x]$ be a divisor of
$x^{n}-1$. If there exist $k\in\\{0,\dots,n-1\\}$ and $\beta\in U_{n}$ such
that $\varphi^{-1}_{\beta,{\overline{x^{k}g}}}\in\mathbb{F}_{q}(n)$ then there
exists a family of permutation equivalent BCH codes
$\\{C_{\alpha}=B_{q}(\alpha,\delta,b)\;\mid\;\alpha\in U_{n}\\}$ with
$\delta=n-\deg(g)$ and $b\in{\mathbb{Z}}_{n}$, such that
$\delta=\Delta(C_{\alpha})=d(C_{\alpha})$ and
$\varphi^{-1}_{\alpha,{\overline{x^{k}g}}}\in C_{\alpha}$.

###### Proof.

Set $g=\sum_{i=0}^{n-1}a_{i}x^{i}$ and suppose that there there exist
$k\in\\{0,\dots,n-1\\}$ and $\beta\in U_{n}$ such that
$\varphi^{-1}_{\beta,{\overline{x^{k}g}}}\in\mathbb{F}_{q}(n)$. Let
$f=\overline{x^{k}g}$ and consider $\alpha\in U_{n}$. By Lemma 11,
$d^{\ast}(g)=n-\deg(g)$. Clearly $m_{f}=g$ and $d^{\ast}(f)=d^{\ast}(g)$. We
collect $T=\bigcup_{j=\deg(g)+k+1}^{n+k-1}C_{q}(\overline{j})$, where
$\overline{j}$ is the canonical representative of $j$ module $n$, and
$\varepsilon=\sum_{i=0}^{n-1}r_{i}x^{i}$ such that $r_{i}=0$ if $i\in T$ and
$1$, otherwise.

We claim that $d^{\ast}(g)=d^{\ast}(\varepsilon)$. From the definition of
$\epsilon$ one has that $d^{\ast}(g)\leq d^{\ast}(\varepsilon)$. We are going
to see the reverse inequality. By Remark 3(3), as
$\varphi^{-1}_{\beta,{f}}\in\mathbb{F}_{q}(n)$ we have that
$supp\left(f\right)$ is union of $q$-cyclotomic cosets modulo $n$. So, for any
$j\in\\{\deg(g)+k+1,\dots,n+k-1\\}$ we have that $C_{q}(\overline{j})\cap
supp\left(f\right)=\emptyset$ and hence $T\subseteq{\mathbb{Z}}_{n}\setminus
supp\left(f\right)$, which means that $supp\left(f\right)\subseteq
supp\left(\varepsilon\right)$ and hence $d^{\ast}(g)=d^{\ast}(f)\geq
d^{\ast}(\varepsilon)$.

By construction, $supp(\varepsilon)$ is union of $q$-cyclotomic cosets, so
$\varphi^{-1}_{\alpha,\varepsilon}\in\mathbb{F}_{q}(n)$ (see Lemma 4). We set
$C=\left(\varphi^{-1}_{\alpha,\varepsilon}\right)$ in $\mathbb{F}_{q}(n)$. We
are going to see that $C$ satisfies the conditions (1) and (2) of Corollary
15.

(1) We have already seen that $d^{\ast}(f)=d^{\ast}(g)=d^{\ast}(\varepsilon)$.
Now, by Proposition 13 and Lemma 12 one has that
$d^{\ast}f=n-deg(m_{f})=\omega\left(\varphi^{-1}_{\alpha,f}\right)\geq d(C)$.
On the other hand, by (5),
$d^{\ast}f=d^{\ast}(\epsilon)=d^{\ast}\left(\varphi_{\alpha,\varphi^{-1}_{\alpha,\epsilon}}\right)\leq
d^{\ast}_{\alpha}(C)\leq d^{\ast}(C)\leq d(C)$.Therefore
$d^{\ast}(C)=d^{\ast}(f)$.

(2) Since $supp(f)\subseteq supp(\varepsilon)$, we have that
$f\star\varepsilon=f$, and then
$\varphi^{-1}_{\alpha,f}\cdot\varphi^{-1}_{\alpha,\varepsilon}=\varphi^{-1}_{\alpha,f}$,
which means that
$\varphi^{-1}_{\alpha,f}\in(\varphi^{-1}_{\alpha,\varepsilon})=C$ (see also
Remark 3(4)). So that, conditions of Corollary 15 are satisfied, and hence
$d(C)=\Delta(C)$.

Finally, to see that $C$ is a BCH code with designed distance
$\delta=\Delta(C)$, we note that, any $q$-cyclotomic coset $Q\subseteq
supp(\varepsilon)=D_{\alpha}(C)$ verifies that
$Q\cap\\{deg(g)+k+1,\dots,n+k-1\\}\neq\emptyset$. So, as we mentioned in
Section II, this means that $C$ is a BCH code with $b=deg(g)+k+1$ and designed
distance $\delta=\Delta(C)=n-deg(g)$. ∎

The theorem above gives us a method to transform a given cyclic code $C=(g)$,
with $d(C)=\Delta(C)$ into another code with higher dimension; in fact, we can
get a new BCH code. The key idea is to consider as generator $\varepsilon$
instead of $g$ via the definition of $T$. This definition may be done in
different ways that can drives us to different BCH codes. All these ideas are
shown in the next example.

######  Example 25.

We continue with the code $C$ showed in Example 19. Recall that $q=2$, $n=45$
and $C$ is the cyclic code with $D_{\beta}(C)=C_{2}(1)\cup C_{2}(3)\cup
C_{2}(9)\cup C_{2}(21)$, where $\beta\in U_{45}$ is such that
$\mathrm{min}(\beta)=x^{12}+x^{3}+1$. Following the proof of the previous
theorem we have that $T=C_{2}(1)\cup C_{2}(3)$ and set
$\varepsilon=\sum_{i\not\in T}x^{i}$. Then
$C^{\prime\prime}=\left(\varphi^{-1}_{\beta,\varepsilon}\right)$ has
$D_{\beta}(C^{\prime\prime})=C_{2}(1)\cup C_{2}(3)$; so that it is the BCH
code $B_{2}(\beta,5,1)$ of dimension $29$ such that
$d(C^{\prime\prime})=\Delta(C^{\prime\prime})=5$. This code has even better
parameters than $C^{\prime}$ (see Example 19).

It is also possible to obtain, from the code $C^{\prime}$, the BCH code
$B_{2}(\beta,5,16)$ with $d(B_{2}(\beta,5,16))=\Delta(B_{2}(\beta,5,16))=5$
and dimension $29$, by taking $T^{\prime}=C_{2}(1)\cup C_{2}(9)$.

The following theorem is a classical result on the theory of BCH codes.

######  Theorem 26 ([6]).

Let $h,m\in{\mathbb{N}}$. A BCH code $C$ of length $n=q^{m}-1$ and designed
distance $\delta=q^{h}-1$ over $\mathbb{F}_{q}$ satisfies that
$d(C)=\Delta(C)$.

Now let us show some examples of construction of new BCH codes.

######  Example 27.

Set $q=2$ and $n=15$. Consider the polynomial $g=g_{3}$ in Example 22; that is
$g=x^{11}+x^{8}+x^{7}+x^{5}+x^{3}+x^{2}+x+1$. Then, its coefficient vector is

$M(g)=(1,1,1,1,0,1,0,1,1,0,0,1,0,0,0)$

and we may check that $d^{\ast}(g)=4$. We know that
$\varphi^{-1}_{\alpha,g}\not\in\mathbb{F}_{2}(n)$ for all $\alpha\in U_{15}$,
because $C_{2}(7)$ is not contained in $supp(g)$ (see Lemma 4). However, the
polynomial $\overline{xg}$ with coefficient vector

$M(\overline{xg})=(0,1,1,1,1,0,1,0,1,1,0,0,1,0,0)$

satisfies that $\varphi^{-1}_{\alpha,_{\overline{xg}}}\in\mathbb{F}_{2}(n)$
for all $\alpha\in U_{15}$. Let us fix $\alpha\in U_{15}$. Then
$C=(\varphi^{-1}_{\alpha,_{\overline{xg}}})$ is a binary code with
$d(C)=d^{\ast}(C)=4$ and $\dim_{\mathbb{F}_{2}}(C)=8$ (see Corollary 18). But,
$C$ is not a BCH code. Following the ideas in Theorem 24 we may replace $0$’s
by $1$’s in the suitable places to get the vector

$M(\varepsilon)=(0,1,1,1,1,1,1,0,1,1,1,0,1,0,0)$

such that $C^{\prime}=\left(\varphi^{-1}_{\alpha,\varepsilon}\right)$ is a BCH
code in $\mathbb{F}_{2}(n)$, with
$d(C^{\prime})=d^{\ast}(C^{\prime})=\delta=4$ and
$\dim_{\mathbb{F}_{2}}(C^{\prime})=10$. Clearly, this code cannot be
considered in Theorem 26.

We finish by extending Corollary 20 to BCH codes.

######  Corollary 28.

Consider an intermediate field
$\mathbb{F}_{q}\subseteq\mathbb{F}_{q^{\prime}}\subseteq\mathbb{L}$, let $h$
be an irreducible factor of $x^{n}-1$ in $\mathbb{F}_{q^{\prime}}[x]$ with
defining set $D_{\alpha}(h)$ for some $\alpha\in U_{n}$ and $g=(x^{n}-1)/h$.
If there are positive integers $j,t$ such that $g(\alpha^{j})=\alpha^{t}$ and
$\gcd\left(j,\frac{n}{\gcd(q-1,n)}\right)\mid t$ then there exists a BCH code
of designed distance $\delta$, $C=B_{q}(\alpha,\delta,b)$, such that
$\delta=\Delta(C)=d(C)=\deg(h)$, for certain $b\in{\mathbb{Z}}_{n}$.

###### Proof.

Comes immediately from Corollary 20 together with Theorem 24. ∎

######  Example 29.

We continue with the codes determined by the polynomials $g_{2}$, $g_{3}$ and
$g_{4}$ in Example 22. Recall that in this case $\alpha\in U_{15}$ satisfies
that $\mathrm{min}(\alpha)=h_{3}$. By applying the ideas contained in the
proof of Theorem 24, one may obtain the following BCH codes whose minimum
distance equals the maximum of their BCH bounds.

It is possible to modify the defining set, w.r.t. $\alpha$, of a cyclic code
in order to obtain a defining set for a new code with higher dimension. In
this case we will say that the original one was dimensional-extended to the
new one. For example, $\left(\varphi^{-1}_{\alpha,{\overline{xg_{2}}}}\right)$
in $\mathbb{F}_{q}(15)$ has dimension 10 and it can be dimensional-extended to
the codes $B_{2}(\alpha,2,0)$ of dimension $14$ and $B_{2}(\alpha,2,3t)$ of
dimension $11$, for $t=1,2,3$. The cyclic code determined by $g_{3}$, that is
$\left(\varphi^{-1}_{\alpha,{\overline{xg_{3}}}}\right)$ in
$\mathbb{F}_{q}(15)$, has dimension 8 and it may be dimensional-extended to
$B_{2}(\alpha,4,13)$ of dimension $10$. Finally, from
$\left(\varphi^{-1}_{\alpha,\overline{x^{3}g_{4}}}\right)$, with dimension 8,
we get $B_{2}(\alpha,4,0)$ of dimension $10$.

Note that the dimensional-extended BCH codes associated to $g_{2},g_{3}$ and
$g_{4}$ are not considered in the classical result 26. There is another
interesting code which has not been considered: the code
$\left(\varphi_{\alpha,\overline{h_{1}h_{2}h_{3}h_{5}}}^{-1}\right)$, where
$h_{1},h_{2},h_{3},h_{5}$ were defined in Example 22, is the code
$B_{2}(\alpha,5,11)$ of dimension $10$.

######  Example 30.

We also also show how to extend the dimension of the codes in Example 23. We
recall that $q=2$, $n=21$ and $\alpha$ satisfies that
$\mathrm{min}(\alpha)=h_{6}$. In this case, we have the following BCH codes
whose minimum distance and apparent distance coincide.

It is possible to modify the set
$D_{\alpha}\left(\varphi_{\alpha,\overline{xg_{2}}}^{-1}\right)$ in three
different ways. The biggest dimensional-extended code that we can obtain is
$B_{2}(\alpha,2,0)$ of dimension $20$. In the case of
$\left(\varphi_{\alpha,g_{3}}^{-1}\right)$, it determines two BCH codes. The
first one is $B_{2}(\alpha,3,19)$ of dimension $15$ and the second one is
$B_{2}(\alpha,3,12)$ of dimension $12$. The code
$\left(\varphi_{\alpha,\overline{x^{3}g_{4}}}^{-1}\right)$ may be dimensional-
extended to $B_{2}(\alpha,3,15)$ of dimension $12$, and $B_{2}(\alpha,3,1)$ of
dimension $15$. The code
$\left(\varphi_{\alpha,\overline{xg_{5}}}^{-1}\right)$ may be dimensional-
extended to $B_{2}(\alpha,6,17)$ of dimension $11$. In the case of
$\left(\varphi_{\alpha,\overline{x^{5}g_{6}}}^{-1}\right)$, we obtain
$B_{2}(\alpha,6,0)$ of dimension $11$. Finally,
$\left(\varphi_{\alpha,\overline{h_{1}h_{3}h_{5}h_{6}}}^{-1}\right)$ is the
BCH code $B_{2}(\alpha,10,17)$ of dimension $10$.

We finish with an example of a binary BCH code of length $33$ whose minimum
distance equals the maximum of their BCH bounds. We have not found in the
literature any binary BCH code satisfying that condition and having this
length and dimension.

######  Example 31.

Set $q=2$, $n=33$ and $\alpha\in U_{33}$ such that
$\mathrm{min}(\alpha)=x^{10}+x^{7}+x^{5}+x^{3}+1$ and
$g=\mathrm{min}(\alpha)\mathrm{min}(\alpha^{3})\mathrm{min}(\alpha^{5})$. One
may check that $g$ verifies the conditions of Theorem 24 with $k=0$ and
$T=C_{2}(1)$; in fact $\varphi^{-1}_{\alpha,g}=x^{22}+x^{11}+1$. Hence, it
determines $B_{2}(\alpha,3,31)$ of dimension $23$.

Acknowledgement. The authors are grateful to the referees for many suggestions
which contributed to improve this paper.

## References

  * [1] P. Camion, Abelian Codes, MRC Tech. Sum. Rep. 1059, Univ. of Wisconsin, Madison, 1970.
  * [2] Charpin, P., Open Problems on Cyclic Codes. in V. S. Pless, W. C. Huffman and R. A. Brualdi (editors) _Handbook of Coding Theory_ vol. I. North-Holland, Amsterdam, 1998.
  * [3] R. T. Chien and D. M. Chow, Algebraic Generalization of BCH-Goppa-Helgert Codes, IEEE Trans. Inform. Theory, vol. 21, no. 1, 1975.
  * [4] GAP - Groups, Algorithms, Programming - a System for Computational Discrete Algebra. http://www.gap-system.org/
  * [5] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge, 2003.
  * [6] F.J. Macwilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, 1977.
  * [7] J. H. Van Lint and R. M. Wilson, On the Minimum Distance of Cyclic Codes,IEEE Trans. Inform. Theory, vol. 32, no. 1, 1986.

Received xxxx 20xx; revised xxxx 20xx.