A linear code with a complementary-dual (an LCD code) was defined in [3] to be a linear code $C$ whose dual code $C^{\perp}$ satisfies $C\cap{C^{\perp}}=\{0\}.$ It was shown in [3] that asymptotically good LCD codes exist and those LCD codes have certain other attractive properties. Yang and Massy showed that the necessary and sufficient condition for a cyclic code of length $n$ to be an LCD code is that the generator polynomial $g(x)$ is self-reciprocal and all the monic irreducible factors of $g(x)$ have the same multiplicity in $g(x)$ and in $x^{n}-1$ (see [4]). In [9], Sendrier indicated that linear code with complementary-duals meet the asymptotic Gilbert-Varshamov bound. Emaeili and Yari discussed in [8] the complementary-dual QC codes, and provided a sufficient condition for an $\rho$-generator QC code $C$ to be an LCD code, and a necessary and sufficient condition under which a given maximal $1$-generator index-$2$ QC code $C$ is LCD.
In recent years, Dinh established the algebrac structure in terms of polynomial generators of all repeated-root constacyclic codes of length $3p^{s}, 4p^{s}, 6p^{s}$ over $F_{p^{m}}$. Using these structures, LCD codes were identified among them (see [5-7]).
The purpose of this paper is to give the algebraic structure in terms of generator polynomials of all complementary-dual $(1-2v)$-constacyclic codes of length $n$ over $F_{p}+vF_{p}$. The necessary background materials on constacyclic codes and a Gray map are given in Section 2. In Section 3, we give the generator polynomials of the complementary-dual cyclic and negacyclic codes of length $n=p^{t}m$ over $F_{p}$, and show an enumeration formula for the complementary-dual cyclic and negacyclic codes of length $n$ over $F_{p}$. In Section 4, Theorem 4.5 provides a necessary and sufficient condition under which a given $(1-2v)$-constacyclic code $C$ of length $n$ over $F_{p}+vF_{p}$ is an LCD. The generator polynomials and enumeration of $(1-2v)$-constacyclic codes length $n$ over $F_{p}+vF_{p}$ are given by Theorem 4.7 under which $C$ is an LCD code of length $n$ over $F_{p}+vF_{p}$.
Throughout this paper, $p$ is an odd prime, $F_{p}$ is a finite field with $p$ elements. Let $R$ be the commutative ring $F_{p}+vF_{p}=\{a+vb|a, b\in F_{p}\}$ with $v^{2}=v$. The ring $R$ is a semi-local ring, it has two maximal ideals $\langle v\rangle=\{a v|a\in F_{p}\}$ and $\langle 1-v\rangle=\{b(1- v)|b\in F_{p}\}$. It is easy to see that both $\frac{R}{\langle v\rangle}$ and $\frac{R}{\langle 1-v\rangle}$ are isomorphic to $F_{p}$. From Chinese remainder theorem, we have $R=\langle v\rangle\oplus\langle1-v\rangle$. We denote $1-2v$ by $\mu$ for simplicity. The following notations for codes over $R$ are also valid for codes over $F_{p}$. A code of length $n$ over $R$ is a nonempty subset of $R^{n}$, and a code is linear over $R$ if it is an $R$-submodule of $R^{n}$. Let $x=(x_{0}, x_{1}, \cdots, x_{n-1})$ and $y=(y_{0}, y_{1}, \cdots, y_{n-1})$ be any two elements of $R^{n}$, we define an inner product over $R$ by $x\cdot y=x_{0}y_{0}+ \cdots+x_{n-1}y_{n-1}$. If $x\cdot y=0$, we say $x$ and $y$ are orthogonal.
The dual code $C^{\perp}$ of $C$ is defined by ${C^ \bot } = \left\{ {x \in {R^n}|x \cdot y = 0{\mkern 1mu} {\mkern 1mu} {\rm{ for}}\;{\rm{all}}\;{\mkern 1mu} {\mkern 1mu} y \in C} \right\}$. It is easy to verify that $C^{\perp}$ is always a linear code over $R$ for any code $C$ code over $R$.
Let $C$ be a code of length $n$ over $R$ (or $F_{p}$) and $P(C)$ be its polynomial representation, i.e.,
Let $\sigma$ and $\gamma$ be maps from $R^{n}$(or $F_{p}^{n}$) to $R^{n}$ (or $F_{p}^{n}$) given by $\sigma(c_{0}, c_{1}, \cdots c_{n-1})=(c_{n-1}, c_{0}, \cdots, c_{n-2})$, and $\gamma(c_{0}, c_{1}, \cdots c_{n-1})=(-c_{n-1}, c_{0}, \cdots, c_{n-2})$, respectively. Then a code $C$ is said to be cyclic if $\sigma(C)= C$, negacyclic if $\gamma(C)= C$.
Let $\tau$ be map from $R^{n}$ to $R^{n}$ given by $\tau(c_{0}, c_{1}, \cdots c_{n-1})=(\mu c_{n-1}, c_{0}, \cdots, c_{n-2})$. Then code $C$ is said to be $\mu$-constacyclic if $\tau(C)= C$.
It is well known that a code $C$ of length $n$ over $R$ (or $F_{p}$) is cyclic if and only if $P(C)$ is an ideal of $\frac{R[x]}{\langle x^{n}-1\rangle}$ (or$\frac{F_{p}[x]}{\langle x^{n}-1\rangle}$), a code $C$ of length $n$ over $R$ (or $F_{p}$) is negacyclic if and only if $P(C)$ is an ideal of $\frac{R[x]}{\langle x^{n}+1\rangle}$ (or$\frac{F_{p}[x]}{\langle x^{n}+1\rangle}$), a code $C$ of length $n$ over $R$ is $\mu-$constacyclic if and only if $P(C)$ is an ideal of $\frac{R[x]}{\langle x^{n}-\mu\rangle}$.
Now we give the definition of the Gray map on $R^n$. Observe that any element $c\in R $ can be expressed as $c=a+vb$, where $a, b\in F_{p}$. The Gray map $\Phi:R\rightarrow F_{p}^{2}$ is given by $\Phi(c)=(-b, 2a+b)$. This map can be extended to $R^n$ in a natrual way:
where $c_{i}=a_{i}+vb_{i}, 0\leq i \leq n-1$.
A code $C$ is a complementary-dual cyclic (or negacyclic) code of length $n$ over $R$ (or $F_{p}$) if it is a cyclic (or negacyclic) and LCD code of length $n$ over $R$ (or $F_{p}$), and a code $C$ is a complementary-dual $\mu$-constacyclic code of length $n$ over $R$ if it is a $\mu$-constacyclic and LCD code of length $n$ over $R$.
We begin with two concepts.
Given a ring $\widetilde{R}$, for a nonempty subset $S$ of $\widetilde{R}$, the annihilator of $S$, denoted by ${\rm ann}($S$)$, is the set ${\rm{ann}}(S) = \left\{ {f|fg = 0{\mkern 1mu} {\mkern 1mu} {\rm{ for}}{\mkern 1mu} \;{\rm{all}}{\mkern 1mu} {\mkern 1mu} g \in S} \right\}$. If, in addition, $S$ is an ideal of $\widetilde{R}$, then ${\rm ann}(S)$ is also an ideal of $\widetilde{R}$.
For any polynomial $f(x)=\sum\limits_{i=0}^{k}a_{i}x^{i}$ of degree $k$ ($a_{k}\neq0)$ over $F_{p}$, let $f^{\ast}(x)$ denote the reciprocal polynomial of $f(x)$ given by $f^{\ast}(x)=x^{k}f(\frac{1}{x})=\sum\limits_{i=0}^{k}a_{k-i}x^{i}$. Note that $(f^{\ast})^{\ast}=f$ if and only if the constant term of $f$ is nonzero, if and only if deg($f$)=deg($f^{\ast}$). Furthermore, by definition, it is easy to see that $(fg)^{\ast}=f^{\ast}g^{\ast}$. We denote $A^{\ast}=\{f^{\ast}(x)|f(x)\in A\}.$ It is easy to see that if $A$ is an ideal, then $A^{\ast}$ is also an ideal. Hereafter, we will use ${\rm ann}^{\ast}(C)$ to denote $({\rm ann}(C))^{\ast}$. The following proposition can be found in [2, 10].
Proposition 3.1 If $C$ is a cyclic (or negacyclic) code of length $n$ over $F_{p}$, then the dual $C^{\perp}$ of $C$ is ${\rm ann}^{\ast}(C)$.
Suppose that $f(x)$ is a monic (i.e., leading coefficient $1$) polynomial of degree $k$ with $f(0)=c\neq0.$ Then by monic reciprocal polynomial of $f(x)$ we mean the polynomial $\widetilde{f}(x)=c^{-1}f^{\ast}(x)$. We recall a result about LCD codes which can be found in [5].
Proposition 3.2 If $g_{1}(x)$ is the generator polynomial of a cyclic code $C$ of length $n$ over $F_{p}$, then $C$ is an LCD code if and only if $g_{1}(x)$ is self-reciprocal $({\rm i.e.}, \widetilde{g}_{1}(x)=g_{1}(x))$ and all the monic irreducible factors of $g_{1}(x)$ have the same multiplicity in $g_{1}(x)$ and in $x^{n}-1$.
Similar to the discussions in [5], we have the following proposition.
Proposition 3.3 If $g_{2}(x)$ is the generator polynomial of a negacyclic code $C$ of length $n$ over $F_{p}$, then $C$ is an LCD code if and only if $g_{2}(x)$ is self-reciprocal (i.e., $\widetilde{g}_{2}(x)=g_{2}(x))$ and all the monic irreducible factors of $g_{2}(x)$ have the same multiplicity in $g_{2}(x)$ and in $x^{n}+1$.
We first investigate the generator polynomials of the complementary-dual cyclic codes over $F_{p}$.
It is well known that each cyclic code over $F_{p}$ is uniquely determined by its generator polynomial, a monic divisor of $x^{n}-1$ over $F_{p}$. In order to describe the generator polynomials of the complementary-dual cyclic codes, we need to know the factorization of the polynomial $x^{n}-1$ over $F_{p}$. Write $n=p^{t}m$, where $t$ is a nonnegative integer depending on $n$ and ${\rm gcd}(m, p)=1.$ Then $x^{n}-1=(x^m-1)^{p^{t}}$.
For any irreducible polynomial dividing $x^{m}-1$ over $F_{p}$, its reciprocal polynomial also divides $x^{m}-1$ over $F_{p}$ and is also irreducible over $F_{p}$. Since ${\rm gcd}(m, p)=1$, the polynomial $x^{m}-1$ factors completely into irreducible factors in $F_{p}[x]$ as
where $\delta\neq0$ in $F_{p}$, $f_{1}(x), f_{2}(x), \cdots, f_{k}(x)$ are irreducible polynomials that are associates to their own reciprocals, and $h_{1}(x), h_{1}^{\ast}(x);\cdots; h_{s}(x), h_{s}^{\ast}(x)$ are pairs of mutually reciprocal irreducible polynomials. Therefore
We can describe the generator polynomials of the complementary-dual cyclic codes as soon as we know the factorization of $x^{n}-1$ over $F_{p}$.
Theorem 3.4 Let $x^{n}-1$ be factorized as in (3.1). A cyclic code $C$ of length $n$ over $F_{p}$ is an LCD code if and only if its generator polynomial is of the form
where $\alpha_{i}\in\{0, p^t\}$ for each $1\leq i \leq k$, and $ \beta_{j}\in\{0, p^t\}$ for each $1\leq j \leq s$.
Proof Let $C$ be a cyclic code of length $n$ over $F_{p}$, and let $g(x)$ be its generator polynomial. We need to show that $C$ is an LCD code if and only if $g(x)$ is of the form as in (3.2).
Suppose that
with leading coefficient 1, where $0 \leq \alpha_{i} \leq p^t$ for each $1\leq i \leq k$, and $0\leq \beta_{j}, \gamma_{j}\leq p^t$ for each $1\leq j \leq s$. Then
Therefore
By Proposition 3.2, $C$ is an LCD code if and only if $g(x)=\widetilde{g}(x)$ and all the monic irreducible factors of $g(x)$ have the same multiplicity in $g(x)$ and in $x^{n}-1$, i.e., $\beta_{j}=\gamma_{j}$ for each $1\leq j \leq s$, $\alpha_{i}\in\{0, p^t\}$ for each $1\leq i \leq k$, and $ \beta_{j}\in\{0, p^t\}$ for each $1\leq j \leq s$.
Therefore, $C$ is an LCD code if and only if its generator polynomial $g(x)$ is of the form as in (3.2).
Obviously, $C=\{0\}$ and $C=F_{p}^{n}$ are complementary-dual cyclic codes, which are called the trivial LCD codes over $F_{p}$.
The following corollary is obvious.
Corollary 3.5 Let $x^{n}-1$ be factorized as in (3.1). Then the number of nontrivial complementary-dual cyclic codes is exactly $2^{k+s}-2.$
Now we discuss the complementary-dual negacyclic codes.
Since $n=p^{t}m$, $gcd(m, p)=1, $ we have $x^{n}+1=(x^m+1)^{p^{t}}$. For any irreducible polynomial dividing $x^{m}+1$ over $F_{p}$, its reciprocal polynomial also divides $x^{m}+1$ over $F_{p}$ and is also irreducible over $F_{p}$. Since ${\rm gcd}(m, p)=1$, the polynomial $x^{m}+1$ factors completely into irreducible factors in $F_{p}[x]$ as
where $\zeta\neq0$ in $F_{p}$, $\overline{f}_{1}(x), \overline{f}_{2}(x), \cdots, \overline{f}_{\overline{k}}(x)$ are irreducible polynomials that are associates to their own reciprocals, and $\overline{h}_{1}(x), \overline{h}_{1}^{\ast}(x);\cdots; \overline{h}_{\overline{s}}(x), \overline{h}_{\overline{s}}^{\ast}(x)$ are pairs of mutually reciprocal irreducible polynomials. Therefore
In light of Proposition 3.3 and (3.3), the following theorem is easy to vertify.
Theorem 3.6 Let $x^{n}+1$ be factorized as in (3.3). A negacyclic code $C$ of length $n$ is LCD code if and only if its generator polynomial is of the form
where $\overline{\alpha}_{i}\in\{0, p^t\}$ for each $1\leq i \leq \overline{k}$, and $ \overline{\beta}_{j}\in\{0, p^t\}$ for each $1\leq j \leq \overline{s}$.
Obviously, $C=0$ and $C=F_{p}^{n}$ are complementary-dual negacyclic codes, which are called the trivial complementary-dual negacyclic codes over $F_{p}$. The following corollary is easy to obtain.
Corollary 3.7 Let $x^{n}+1$ be factorized as in (3.3). Then the number of nontrivial complementary-dual cyclic codes is exactly $2^{\overline{k}+\overline{s}}-2.$
Let $C_{1}, C_{2}$ be codes over $R$. We denote $C_{1}\oplus C_{2}=\{a+b|a\in C_{1}, b\in C_{2}\}.$ For a code $C$ over $R$, let us take
and
It is easy to vertify that $ \mid C \mid=\mid C_{v}\mid\mid C_{1-v}\mid, $ and $C=vC_{1-v}\oplus(1-v)C_{v}.$
The following four lemmas can be found in [1].
Lemma 4.1 Let $C=vC_{1-v}\oplus(1-v)C_{v}$ be a linear code of length $n$ over $R$. Then $C$ is a $\mu$-constacyclic code length $n$ over $R$ if and only if $C_{1-v}$ and $C_{v}$ are negacyclic and cyclic codes of length $n$ over $F_{p}$, respectively.
Lemma 4.2 If $C=vC_{1-v}\oplus(1-v)C_{v}$ is a $\mu$-constacyclic code of length $n$ over $R$, then there is a unique polynomial $g(x)=vg_{1}(x)+(1-v)g_{2}(x)$ such that $C=\langle g(x)\rangle, g(x)|x^{n}-\mu, $ and $\mid C \mid=p^{2n-\deg(g_{1})-\deg(g_{2})}$, where $g_{1}(x)$ and $g_{2}(x)$ are the generator polynomials of $C_{1-v}$ and $C_{v}$ over $F_{p}$, respectively.
Lemma 4.3 Let $C=vC_{1-v}\oplus(1-v)C_{v}$ be a $\mu$-constacyclic code length $n$ over $R$, and $C=\langle vg_{1}(x)+(1-v)g_{2}(x)\rangle$, where $g_{1}(x)$ and $g_{2}(x)$ are the generator polynomials of $C_{1-v}$ and $C_{v}$ over $F_{p}$, respectively. Then $\Phi(C)=\langle g_{1}(x)g_{2}(x)\rangle$, and $\Phi(C^{\perp})=\Phi(C)^{\perp}.$
Lemma 4.4 Let $C=vC_{1-v}\oplus(1-v)C_{v}$ be a $\mu$-constacyclic code length $n$ over $R$. Then its dual code $C^{\perp}$ is also a $\mu$-constacyclic code length $n$ over $R$, and $C^{\perp}=vC_{1-v}^{\perp}\oplus(1-v)C_{v}^{\perp}.$
Theorem 4.5 Let $C=vC_{1-v}\oplus(1-v)C_{v} =\langle vg_{1}(x)+(1-v)g_{2}(x) \rangle$ be a $\mu$-constacyclic code of length $n$ over $R$. Then $C$ is an LCD code of length $n$ over $R$ if and only if $C_{1-v}$ and $C_{v}$ are the complementary-dual negacyclic and cyclic codes of length $n$ over $F_{p}$, respectively.
Proof By Lemma 4.4, we know that $C \cap C^{\perp}=\{0\}$ if and only if $C_{1-v}\cap C_{1-v}^{\perp}=\{0\}$, and $C_{v}=\cap C_{v}^{\perp}=\{0\}$.
Form the above proof, the following corollary can be obtained at once.
Corollary 4.6 Let $C=vC_{1-v}\oplus(1-v)C_{v}$ be a $\mu$-constacyclic code of length $n$ over $R$. Then $C$ is an LCD code of length $n$ over $R$ if and only if $\Phi(C)$ is a complementary-dual cyclic codes of length $2n$ over $F_{p}$.
Proof By Lemma 4.1 and Lemma 4.3, we have $C_{1-v}=\langle g_{1}(x)\rangle$, and $C_{v}=\langle g_{2}(x)\rangle$.
Since $C_{1-v}$ is a complementary-dual negacyclic code, $g_{1}(x)=\widetilde{g}_{1}(x)$ and all the monic irreducible factors of $g_{1}(x)$ have the same multiplicity in $g_{1}(x)$ and in $x^{n}+1$.
Similarly, $g_{2}(x)=\widetilde{g}_{2}(x)$ and all the monic irreducible factors of $g_{2}(x)$ have the same multiplicity in $g_{2}(x)$ and in $x^{n}-1$.
In light of Lemma 4.2, $\Phi(C)=\langle g_{1}(x)g_{2}(x)\rangle$. Write $g(x)=g_{1}(x)g_{2}(x).$ Then
which implies that $\widetilde{g}(x)$ is self-reciprocal.
Let $x^{n}+1=g_{1}(x)h_{1}(x)$, and $x^{n}-1=g_{2}(x)h_{2}(x)$. Then
Therefore all the monic irreducible factors of $g(x)$ have same multiplicity in $g(x)$ have the same multiplicity in $g(x)$ in $x^{2n}-1$.
We summarize the above fact to conclude that $\Phi(C)$ is a complementary-dual cyclic code of length $2n$ over $F_{p}$.
Conversely, if $\alpha\in C\cap C^{\perp}$, i.e., $\alpha\in C$, and $\alpha\in C^{\perp}$, then $\Phi(\alpha)\in\Phi(C)$, and $\Phi(\alpha)\in\Phi(C^{\perp})=\Phi(C)^{\perp}$. Therefore $\Phi(\alpha)\in\Phi(C)\cap \Phi(C)^{\perp}=\{0\}$, i.e., $\Phi(\alpha)=0$. It is implies that $\alpha=0$ since $\Phi$ is bijective from $R^{n}$ to $F_{p}^{2n}.$ Hence $ C\cap C^{\perp}=\{0\}$, i.e., $C$ is a complementary-dual cyclic code of length $n$ over $R$.
By Theorem 3.5, Theorem 3.7, Corollary 3.6 and Corollary 3.8, we get the following statements.
Theorem 4.7 Let $C=vC_{1-v}\oplus(1-v)C_{v}$ be a $\mu$-constacyclic code of length $n$ over $R$, $x^{n}-1$ and $x^{n}+1$ be factorized as in (3.2) and (3.3), respectively. Then
$(1)$ $C$ is an LCD code of length $n$ over $R$ if and only if its generator polynomial is of the form
where $f_{i}(x), \overline{f}_{l}(x), h_{j}(x), h_{j}^{\ast}(x), \overline{h}_{q}(x), \overline{h}_{q}^{\ast}(x)\in F_{p}[x]$, and $\alpha_{i}, \overline{\alpha}_{l}, \beta_{j}, \overline{\beta}_{q} \in\{0, p^{t}\}.$
$(2)$ $\Phi(C)$ is an LCD code of length $2n$ over $F_{p}$ if and only if its generator polynomial is of the form
$(3)$ The number of nontrivial complementary-dual $\mu$-constacyclic codes of length $n$ over $R$ is exactly $2^{k+s+\overline{k}+\overline{s}}-2$.
Now, we give the following two examples to illustrate the above results.
Example 1 In $F_{5}[x]$,
Observe that the polynomials $x-1, x+1, x^{2}+x+1$, and $x^{2}+4x+1$ are irreducible polynomials that are associates to their own reciprocals, and $x+2, 1+2x;x^{2}+2x-1, 1+2x-x^{2}$ are two pairs of mutually reciprocal irreducible polynomials over $F_{5}$. There are $62$ nontrivial complementary-dual $\mu$-constacyclic codes of length $6$ over $R=F_{5}+vF_{5}$, i.e.,
where $\alpha_{i}\in \{0, 1\}$ for $1\leq i\leq6$, and $(\alpha_{1}, \alpha_{2}, \alpha_{3}, \alpha_{4}, \alpha_{5}, \alpha_{6})\neq(0, 0, 0, 0, 0, 0), (1, 1, 1, 1, 1, 1).$
Now we list some optimal codes obtained from complementary-dual $\mu$-constacyclic codes over $R=F_{5}+vF_{5}$ in Table 1.
Example 2 In $F_{7}[x]$,
Observe that the polynomials $x-1, x+1, x^{2}+1, x^{2}-3x+1$, and $x^{2}+3x+1$ are irreducible polynomials that are associates to their own reciprocals, and $x^{2}+x-1, 1+x-x^{2};x^{2}+3x-1, 1+3x-x^{2}$ are two pairs of mutually reciprocal irreducible polynomials over $F_{7}$. There are $126$ nontrivial complementary-dual $\mu$-constacyclic codes of length $8$ over $R=F_{7}+vF_{7}$, i.e.,
where $\beta_{j}\in \{0, 1\}$ for $1\leq j\leq7$, and
Now we list some optimal linear codes obtained from complementary-dual $\mu$-constacyclic codes over $R=F_7+v F_7$ in Table 2.