2 Preliminaries

Let $\mathbb {F}_q$ denote the finite field with q elements and let $\mathbb {F}_q^n$ be the set of all vectors of length n over $\mathbb {F}_q$ . For a nonnegative integer t with $t\leq q$ , a t-subset $A\subseteq \mathbb {F}_q$ is called a zero-sum t-subset if $\sum _{a\in A}a=0$ . For a vector $\mathbf {a}\in \mathbb {F}_q^n$ , its support is defined by $\mathrm {supp}(\mathbf {a}) = \{i : a_i \neq 0\}$ . The Hamming weight $w_H(\mathbf {a})$ of $\mathbf {a}$ is the cardinality of its support. A linear code over $\mathbb {F}_q$ of length n, dimension k and minimum Hamming distance $d_H$ is called an $[n,k,d_H]_q$ linear code. Two linear codes over $\mathbb {F}_q$ are considered equivalent if one can be derived from the other by a combination of coordinate permutations and scalar multiplication, where each coordinate is multiplied by a nonzero element in $\mathbb {F}_q$ . It is evident that equivalent codes have the same parameters.

Now we introduce AMDS and NMDS codes.

The next result gives properties of the generator matrix of AMDS and NMDS codes.

There are many known constructions of NMDS codes. Roth–Lempel in [Reference Roth and Lempel24] give a class of NMDS codes as follows. Let n and k be two integers such that $3\leq k\leq n\leq ~q$ . Let $A=\{a_1,\ldots ,a_n\}$ be an n-subset of $\mathbb {F}_q$ . Then an $[n+2,k]$ Roth–Lempel code, $RL(A,k,n+2)$ , over $\mathbb {F}_q$ is defined by the generator matrix

$$ \begin{align*} G_n=\begin{pmatrix} 1&1&\cdots&1&0&0\\ a_1&a_2&\cdots&a_n&0&0\\ a_1^2&a_2^2&\cdots&a_n^2&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ a_1^{k-2}&a_2^{k-2}&\cdots&a_n^{k-2}&0&1\\[3pt] a_1^{k-1}&a_2^{k-1}&\cdots&a_n^{k-1}&1&0 \end{pmatrix}. \end{align*} $$

It has been proved that the linear code $RL(A,k,n+2)$ is an NMDS code if and only if A contains a zero-sum $(k-1)$ -subset [Reference Han and Fan16].

Now we introduce the insdel distance and insdel codes.

It can be confirmed that $d_I(\mathbf {a},\textbf {b})$ is a metric on $\mathbb {F}_q^n$ . Moreover, the insdel distance between any two vectors can be determined by their longest common subsequences.

The insdel distance of a linear insdel code ${\mathcal {C}}$ over $\mathbb {F}_q$ is defined as the minimum insdel distance between any two different codewords in ${\mathcal {C}}$ , that is,

$$ \begin{align*}d_I({\mathcal{C}})=\min_{\mathbf{a},\textbf{b}\in{\mathcal{C}},\mathbf{a}\neq\textbf{b}}\{d_I(\mathbf{a},\textbf{b})\}.\end{align*} $$

It is easy to show that $d_I({\mathcal {C}})\leq 2d_H(C)$ for arbitrary insdel codes. Haeupler–Shahrasbi [Reference Haeupler and Shahrasbi15] gave the direct Singleton bound $d_I({\mathcal {C}})\leq 2(n-2k+1)$ . After that, Chen–Zhang [Reference Chen and Zhang4] improved the direct Singleton bound of linear insdel codes. Further, Cheng et al. [Reference Cheng, Guruswami, Haeupler and Li6] and Chen [Reference Chen5] introduced the half-Singleton bound for linear insdel codes.

According to Lemma 2.5, the linear codes can correct insdel errors only for $n\geq 2k$ . This conclusion was also proposed in [Reference Abdel-Ghaffar, Ferreira and Cheng1]. Recently, Ji et al. [Reference Ji, Zheng, Chen and Wang19] proposed a strict half-Singleton bound on the insdel distance for linear insdel codes without the codeword with all ones.

Lemma 2.6 (Strict half-Singleton bound, [Reference Ji, Zheng, Chen and Wang19]).

Let ${\mathcal {C}}$ be an $[n,k]$ linear code over $\mathbb {F}_q$ with $n>k\geq 1$ . If $\mathbf {1}=(1,\ldots ,1)\notin {\mathcal {C}}$ , then the insdel distance of ${\mathcal {C}}$ satisfies

$$ \begin{align*}d_I({\mathcal{C}})\leq\max\{2(n-2k+1),2\}.\end{align*} $$

3 Upper bound of the insdel distance for AMDS code

In this section, we provide a sufficient condition for the insdel distance of an AMDS code to be bounded by the strict half-Singleton bound. For a positive integer n, we denote $[n]=\{1,2,\ldots ,n\}$ . For a linear $[n,k]_q$ code ${\mathcal {C}}\subset \mathbb {F}_q^n$ , the subset $S=\{i_1,i_2,\ldots ,i_h\}\subset [n]$ of h coordinate positions is called an information free coordinate subset if the natural projection $\phi _S:{\mathcal {C}}\rightarrow \mathbb {F}_q^h$ , defined by $\phi _S((c_1,\ldots ,c_n))=(c_{i_1},\ldots ,c_{i_h})$ , is a surjection. Clearly, $h\leq k$ . When $h=k$ , S is called an information set.

For positive integers n and s with $s\leq n$ , we define $[n]^s$ as the set of all vectors of length s whose coordinates are from $[n]$ . We say that a vector $I=(I_1,I_2,\ldots ,I_s)\in [n]^s$ is an increasing vector if $1\leq I_1<I_2<\cdots <I_s\leq n$ . Let $I\cap J$ be an increasing vector formed by the corresponding equal components of I and J: that is, $I\cap J=(r_1,r_2,\ldots ,r_t),t\leq s$ . Here, $r_i=I_{e_i}=J_{e_i}$ represents the $e_i$ th component of I and J for $1\leq i\leq t$ . Let $|I\cap J|$ denote the length of the vector $I\cap J$ .

Theorem 3.1. Let ${\mathcal {C}}$ be a linear $[n,k]_q$ AMDS code with $n\geq \max \{3k-1,2k+1\}$ . Suppose that there exists a minimum Hamming weight codeword $\textbf {c}\in {\mathcal {C}}$ with k consecutive indices in $\mathrm {supp}(\textbf {c})$ . Then

$$ \begin{align*} d_I({\mathcal{C}})\leq2(n-2k+1). \end{align*} $$

Proof. Let G be a generator matrix of ${\mathcal {C}}$ . Let $J=[n]\setminus \mathrm {supp}(\mathbf {c})$ and let I be the set of k consecutive indices in $\mathrm {supp}(\mathbf {c})$ . We have $|I|=k$ . We discuss the insdel distance of ${\mathcal {C}}$ in two cases.

Case 1. If $\mathrm {rank}(G_I)=k$ , then I is an information set. We can assume that $I=\{i,i+1,\ldots ,i+{k-1}\}$ , where $1\leq i< i+1<\cdots < i+k-1\leq n$ . Since I is an information set, we can find a codeword $\textbf {b}\in {\mathcal {C}}$ satisfying that $\textbf {b}_I=(b_i,b_{i+1},\ldots ,b_{i+k-1})$ with the coordinate values

$$ \begin{gather*} b_{i+1}=b_i+c_i,\\ b_{i+2}=b_{i+1}+c_{i+1},\\ \dots\\ b_{i+k-1}=b_{i+k-2}+c_{i+k-2}. \end{gather*} $$

Here, $b_i$ is an arbitrary element in $\mathbb {F}_{q}$ . Then

$$ \begin{gather*} (\textbf{b}+\textbf{c})_I=(b_i+c_i,\ldots,b_{i+k-1}+c_{i+k-1})=(b_{i+1},\ldots,b_{i+k-1},b_{i+k-1}+c_{i+k-1}),\\ (\textbf{b}+\textbf{c})_J=\textbf{b}_J+\textbf{c}_J=\textbf{b}_J. \end{gather*} $$

We have $l(\textbf {b},\textbf {b}+\textbf {c})\geq l(\textbf {b}_I,(\textbf {b}+\textbf {c})_I)+k=k-1+k=2k-1$ . Therefore,

$$ \begin{align*}d_I({\mathcal{C}})\leq d_I(\textbf{b},\textbf{b}+\textbf{c})=2n-2l(\textbf{b},\textbf{b}+\textbf{c})\leq2(n-2k+1).\end{align*} $$

Case 2. If $\mathrm {rank}(G_I)<k$ , then there exists $\mathbf {0}\neq \mathbf {m}\in \mathbb {F}_q^k$ such that $\mathbf {m}G_I=\mathbf {0}$ . Let $\mathbf {d}=\mathbf {m}G$ . Then $w_H(\mathbf {d})=n-k$ . Since $n\geq 3k-1$ , by the pigeonhole principle, we can guarantee that there is $S\subset [n]\setminus I$ such that S is a consecutive index set with size k. We analyse this case by considering two subcases.

Case 2.1. If $\mathrm {rank}(G_S)=k$ , then S is an information set and the conclusion follows from Case 1.

Case 2.2. If $\mathrm {rank}(G_S)<k$ , since $n\geq \max \{3k-1,2k+1\}$ , we can find a consecutive index set $D\subset [n]\setminus I$ or $ [n]\setminus S$ with size $k+1$ . Assume that $D\subset [n]\setminus S$ . Then we must have a consecutive information set in D because any $k+1$ columns of G have full rank. Then we can complete the proof in a similar way to the proof in Case 1.

If the first or the last k columns of a generator matrix of an AMDS code are linearly dependent, then the bound is also true.

Now we can give two examples of optimal insdel codes with respect to the strict half-Singleton bound from Roth–Lempel codes.

Example 3.3. Let $A=\{0,1,4,2,3\}$ and let $RL(A,3,7)$ be a linear code over $\mathbb {F}_5$ with generator matrix

$$ \begin{align*}G=\begin{pmatrix} 1&1&1&1&1&0&0\\ 0&1&4&2&3&0&1\\ 0&1&1&4&4&1&0 \end{pmatrix}.\end{align*} $$

With the help of MAGMA [23], we can calculate that $RL(A,3,7)$ is an optimal $[7,3]_{5}$ NMDS insdel code with $d_I=4$ . All the MAGMA codes mentioned in this and the following examples are available by contacting the authors.

Example 3.4. Let $q=25$ and let $\omega $ be a primitive element of $\mathbb {F}_q$ . Let ${\mathcal {C}}$ be a linear code over $\mathbb {F}_q$ with generator matrix

$$ \begin{align*}G=\begin{pmatrix} 1&1&1&1&0&1&1&1&0\\ {\omega}&1&{\omega}^2&2&0&3&0&\omega^{11}&0\\ {\omega}^2&1&{\omega}^4&4&0&4&0&\omega^{22}&1\\ {\omega}^3&1&{\omega}^6&3&1&2&0&\omega^{9}&0 \end{pmatrix}.\end{align*} $$

With the help of MAGMA, we can calculate that ${\mathcal {C}}$ is an optimal $[9,4]_{25}$ NMDS insdel code with $d_I=4$ .

In fact, the insdel distance of a linear $[n,k]$ AMDS code is bounded by the strict half-Singleton bound when n is large enough.

From Remark 3.7, we know that we can find optimal two-dimensional NMDS insdel codes with respect to the half-Singleton bound only for $n\leq 5$ . We close this section with an example.

Example 3.8. Let $q=3^{25}$ and let $\omega $ be a primitive element of $\mathbb {F}_q$ . Let

$$ \begin{align*}{\mathcal{C}}=\{(f(\omega),f(\omega^2),f(\omega^4),f(-\omega^2),f(\omega^8))\mid f(x)=a_0+a_1 x^2,a_0,a_1\in\mathbb{F}_q\}.\end{align*} $$

With the help of MAGMA, we can show that ${\mathcal {C}}$ is an optimal $[5,2,d_I=6]_q$ NMDS insdel code with respect to the half-Singleton bound.

4 Constructions of optimal AMDS insdel codes

This section is composed of two subsections. In Section 4.1, we present a class of two-dimensional optimal NMDS insdel codes that achieve the strict half-Singleton bound by employing twisted Reed–Solomon codes. In Section 4.2, we construct optimal AMDS insdel codes with respect to the strict half-Singleton bound for arbitrary dimensions. These results show that the strict half-Singleton bound is tight for AMDS codes that satisfy the conditions of Theorem 3.1.

4.1 Optimal two-dimensional NMDS insdel codes

In this subsection, we focus on two-dimensional NMDS insdel codes. We utilise twisted Reed–Solomon (TRS) codes to construct a class of optimal NMDS insdel codes with respect to the strict half-Singleton bound. Now we introduce the definition of TRS codes.

Let $\mathbf {a}=(\alpha _1,\alpha _2,\ldots ,\alpha _n)$ , where $\alpha _1,\alpha _2,\ldots ,\alpha _n$ are distinct elements in $\mathbb {F}_q$ and $\eta \in \mathbb {F}_q^*$ . Let $\mathbb {F}_q[x]$ be the polynomial ring over $\mathbb {F}_q$ . Consider the TRS code $C_k(\mathbf {a},\eta )$ with length n and dimension k, where

$$ \begin{align*} C_k(\mathbf{a},\eta)=\bigg\{\mathbf{c}_f=(f(\alpha_1),\ldots,f(\alpha_n)) \,\bigg|\, f(x)=\sum_{i=0}^{k-1}a_i x^i+\eta a_{k-1}x^k\in\mathbb{F}_q[x]\bigg\}. \end{align*} $$

Let $S_2=\{\alpha _i+\alpha _j \mid 1\leq i<j\leq n\}.$ Huang et al. [Reference Huang, Yue, Niu and Li17] studied the NMDS property of $C_2(\mathbf {a},\eta )$ .

Lemma 4.1 [Reference Huang, Yue, Niu and Li17].

The code ${\mathcal {C}}_{2}(\mathbf {a},\eta )$ is NMDS if and only if $-\eta ^{-1}\in S_2$ .

To construct our codes, we also need the concept of Sidon sets.

Definition 4.2. A set D of integers is called a Sidon set if all pairwise sums of its elements are distinct. Equivalently, the equation $a+b=c+d$ has only the trivial solution $\{a,b\}=\{c,d\}$ in D.

We use the TRS code to construct a family of two-dimensional insdel NMDS codes. Let $q=l^2$ , where $l=p^e$ is a prime power and $e>1$ is a positive integer. Let $\theta $ be the primitive element of $\mathbb {F}_{l}$ , that is, $\mathbb {F}_{l}=\mathbb {F}_p(\theta )$ . Let $n\geq 5$ be an integer and let $i_1,i_3,i_4,\ldots ,i_n$ be $n-1$ integers such that $0\leq i_1<i_3<\cdots <i_n\leq l-2$ . Choose $\eta \in \mathbb {F}_{l}^*$ such that $1+4\eta \theta ^{i_1}\neq 0$ . Let $\alpha _1,\alpha _2$ be the two roots of the polynomial $x+\eta x^2=\theta ^{i_1}$ and let $\alpha _3,\alpha _4,\ldots ,\alpha _n$ be the roots of the polynomials $x+\eta x^2=\theta ^{i_t}(t=3,4,\ldots ,n)$ , respectively. Obviously, $\alpha _1,\alpha _2\ldots ,\alpha _n$ are distinct elements in $\mathbb {F}_{q}^*$ . Then

$$ \begin{align*} {\mathcal{C}}_2(\mathbf{a},\eta )=\{\mathbf{c}_f=(f(\alpha_1),\ldots,f(\alpha_n)) \mid f(x)=\lambda+\mu(x+\eta x^2),\lambda,\mu\in \mathbb{F}_{q}\} \end{align*} $$

is a two-dimensional TRS code of length n.

The following theorem provides a sufficient condition for the insdel distance of ${\mathcal {C}}_2(\mathbf {a},\eta )$ to achieve the strict half-Singleton bound.

Theorem 4.3. If $D=\{i_1,i_3,\ldots ,i_n\}\subseteq \{0,1,\ldots ,l-2\}$ satisfies:

1. (1) D is a Sidon set; and

2. (2) $i_{n-1}+i_n<e$ ,

then the minimum insdel distance of ${\mathcal {C}}_2(\mathbf {a},\eta )$ is equal to $2n-6$ : that is, ${\mathcal {C}}_2(\mathbf {a},\eta )$ is an optimal NMDS insdel code with respect to the strict half-Singleton bound.

Proof. According to Lemma 4.1, ${\mathcal {C}}_2(\mathbf {a},\eta )$ is a two-dimensional NMDS code since

$$ \begin{align*}-\eta^{-1}=\alpha_1+\alpha_2\in S_2.\end{align*} $$

Moreover, the first two columns of the generator matrix of ${\mathcal {C}}_2(\mathbf {a},\eta )$ are

$$ \begin{align*}\begin{pmatrix} 1\\ \theta^{i_1} \end{pmatrix}, \begin{pmatrix} 1\\ \theta^{i_1} \end{pmatrix}.\end{align*} $$

By Corollary 3.2, $d_I({\mathcal {C}}_2(\mathbf {a},\eta ))\leq 2n-6$ . It remains to show that $d_I({\mathcal {C}}_2(\mathbf {a},\eta ))\geq 2n-6$ .

Let

$$ \begin{align*}f(x)=\lambda_0+\mu_0(x+\eta x^2), g(x)=\lambda_1+\mu _1(x+\eta x^2),\end{align*} $$

where $\lambda _0,\mu _0,\lambda _1,\mu _1\in \mathbb {F}_{q}$ . From Lemma 2.4, it is enough to prove the following claim.

Claim. $l(\textbf {c}_f,\textbf {c}_g)\leq 3$ for any $f(x)\neq g(x)$ .

Suppose that $f(x)\neq g(x)$ with $l(\textbf {c}_f,\textbf {c}_g)\geq 4$ . Then there exist eight integers $k_1,k_2,k_3,k_4,r_1,r_2,r_3,r_4$ with $1\leq k_1<k_2<k_3<k_4\leq n,1\leq r_1<r_2<r_3<r_4\leq n$ such that

$$ \begin{align*} \begin{cases} \lambda_0+\mu_0(\alpha_{k_1}+\eta\alpha_{k_1}^2)=\lambda_1+\mu_1(\alpha_{r_1}+\eta\alpha_{r_1}^2),\\ \lambda_0+\mu_0(\alpha_{k_2}+\eta\alpha_{k_2}^2)=\lambda_1+\mu_1(\alpha_{r_2}+\eta\alpha_{r_2}^2),\\ \lambda_0+\mu_0(\alpha_{k_3}+\eta\alpha_{k_3}^2)=\lambda_1+\mu_1(\alpha_{r_3}+\eta\alpha_{r_3}^2),\\ \lambda_0+\mu_0(\alpha_{k_4}+\eta\alpha_{k_4}^2)=\lambda_1+\mu_1(\alpha_{r_4}+\eta\alpha_{r_4}^2).\\ \end{cases} \end{align*} $$

Then

$$ \begin{align*} \begin{cases} \lambda_0+\mu_0\theta^{i_{k_2}}=\lambda_1+\mu_1\theta^{i_{r_2}},\\ \lambda_0+\mu_0\theta^{i_{k_3}}=\lambda_1+\mu_1\theta^{i_{r_3}},\\ \lambda_0+\mu_0\theta^{i_{k_4}}=\lambda_1+\mu_1\theta^{i_{r_4}},\\ \end{cases} \end{align*} $$

with $k_2<k_3< k_4$ and $r_2<r_3<r_4$ , which is equivalent to saying that

$$ \begin{align*}\begin{pmatrix} \theta^{i_{k_2}}& \theta^{i_{r_2}}&1\\ \theta^{i_{k_3}}& \theta^{i_{r_3}}&1\\ \theta^{i_{k_4}}& \theta^{i_{r_4}}&1 \end{pmatrix}\begin{pmatrix} \mu_0\\ -\mu_1\\ \lambda_0-\lambda_1 \end{pmatrix}=\mathbf{0}.\end{align*} $$

Since $f(x)\neq g(x)$ , we know that $\mu _0,-\mu _1$ and $\lambda _0-\lambda _1$ are not all equal to 0. Thus, we must have

$$ \begin{align*}\begin{vmatrix} \theta^{i_{k_2}}& \theta^{i_{r_2}}&1\\ \theta^{i_{k_3}}& \theta^{i_{r_3}}&1\\ \theta^{i_{k_4}}& \theta^{i_{r_4}}&1 \end{vmatrix}=0.\end{align*} $$

Consider the polynomial

$$ \begin{align*}M(x)=\begin{vmatrix} x^{i_{k_2}}& x^{i_{r_2}}&1\\ x^{i_{k_3}}& x^{i_{r_3}}&1\\ x^{i_{k_4}}& x^{i_{r_4}}&1 \end{vmatrix}=x^{i_{k_2}+i_{r_3}}+x^{i_{k_3}+i_{r_4}}+x^{i_{k_4}+i_{r_2}}-x^{i_{k_2}+i_{r_4}}-x^{i_{k_3}+i_{r_2}}-x^{i_{k_4}+i_{r_3}}.\end{align*} $$

It is clear that $M(x)\in \mathbb {F}_p[x]$ and $M(\theta )=0$ . We want to prove that $M(x)\neq 0$ . Observing that $k_2<k_3<k_4$ and $r_2<r_3<r_4$ , we have

$$ \begin{align*} i_{k_3}+i_{r_4}>\max\{i_{k_2}+i_{r_3},i_{k_2}+i_{r_4}\},\quad i_{k_4}+i_{r_3}>\max\{i_{k_3}+i_{r_2},i_{k_4}+i_{r_3}\},\\ i_{k_2}+i_{r_3}<\min\{i_{k_3}+i_{r_4},i_{k_2}+i_{r_4}\},\quad i_{k_3}+i_{r_2}<\min\{i_{k_4}+i_{r_2},i_{k_4}+i_{r_3}\}. \end{align*} $$

Thus, the term with the maximum degree in the polynomial $M(x)$ is $x^{i_{k_3}+i_{r_4}}$ or $-x^{i_{k_4}+i_{r_3}}$ and the term with the minimum degree in the polynomial $M(x)$ is $x^{i_{k_2}+i_{r_3}}$ or $-x^{i_{k_3}+i_{r_2}}$ . If $M(x)=0$ , then we must have

$$ \begin{align*}i_{k_3}+i_{r_4}=i_{k_4}+i_{r_3}, \quad i_{k_2}+i_{r_3}=i_{k_3}+i_{r_2}.\end{align*} $$

Since D is a Sidon set, this implies that

$$ \begin{align*}\{i_{k_3},i_{r_4}\}=\{i_{k_4},i_{r_3}\}, \quad \{i_{k_2},i_{r_3}\}=\{i_{k_3},i_{r_2}\}.\end{align*} $$

Since $i_{k_2}<i_{k_3}<i_{k_4}$ and $i_{r_2}<i_{r_3}<i_{r_4}$ , it follows that $i_{k_t}=i_{r_t}$ for $t=2,3,4$ . This means that $f(\alpha _{i_{k_t}})=g(\alpha _{i_{k_t}})$ for $t=2,3,4$ , forcing $f(x)=g(x)$ , which is a contradiction. Therefore, we conclude that $M(x)\neq 0$ .

Thus, we have $0\neq M(x)\in \mathbb {F}_p[x]$ with $M(\theta )=0$ . However, since $\theta $ is a primitive element of $\mathbb {F}_{l}=\mathbb {F}_{p^e}$ and $\mathrm {deg} M(x)\leq i_{n-1}+i_n<e$ , we arrive at a contradiction. This completes the proof of the claim $l(\textbf {c}_f,\textbf {c}_g)\leq 3$ for any distinct codewords $\textbf {c}_f,\textbf {c}_g\in {\mathcal {C}}_2(\mathbf {a},\eta )$ .

Consequently, $d_I({\mathcal {C}}_2(\mathbf {a},\eta ))\geq 2n-6$ . This completes the proof.

Remark 4.4. (1) Let $S(n)$ denote the maximum size of a Sidon set D when $D\subset [n]$ . Erdős and Turán [Reference Erdős and Turán13] proved that $S(n)\leq \sqrt {n}+O(n^{{1}/{4}})$ . Thus, we require a field size at least $\Omega (\exp (n^2))$ in Theorem 4.3.

(2) It is easy to check that $\mathbf {1}=(1,\ldots ,1)\in \mathcal {C}_2(\mathbf {a}, \eta )$ . This observation indicates that ${\mathcal {C}}_2(\mathbf {a},\eta )$ does not satisfy the condition presented in Lemma 2.6.

4.2 Optimal AMDS insdel codes

In this subsection, we aim to generalise the idea for optimal two-dimensional NMDS insdel codes and construct optimal AMDS insdel codes for arbitrary dimensions.

Recently, Con et al. [Reference Con, Guo, Li and Zhang8] showed that random Reed–Solomon codes approach the half-Singleton bound with high probability. Let ${\mathcal {C}}$ be an $[n,k]_q$ Reed–Solomon code with generator matrix

$$ \begin{align*}G=(\mathbf{g_1},\mathbf{g_2},\ldots,\mathbf{g_n})\end{align*} $$

that achieves the half-Singleton bound, where $n\geq 2k$ . Let ${\mathcal {C}}_1$ be the linear code spanned by the row vectors of

$$ \begin{align*}G_1=(\mathbf{g_1},G)=(\mathbf{g_1},\mathbf{g_1},\mathbf{g_2},\ldots,\mathbf{g_n}).\end{align*} $$

Lemma 4.5. ${\mathcal {C}}_1$ is an $[n+1,k]_q$ AMDS code.

Proof. Consider the map

$$ \begin{align*} \varphi: {\mathcal{C}} &\rightarrow {\mathcal{C}}_1 \\ (c_1, c_2, \ldots, c_n) &\mapsto (c_1, c_1, c_2, \ldots, c_n). \end{align*} $$

It is clear that $\varphi $ is a bijection, and thus $\dim ({\mathcal {C}}_1)=k$ . Since $G_1$ is the generator matrix of ${\mathcal {C}}_1$ and any k columns of G have full rank, it follows that any $k+1$ columns of $G_1$ have full rank and the first k columns of $G_1$ are linearly dependent. This implies that ${\mathcal {C}}_1$ is an $[n+1,k]_q$ AMDS code according to Lemma 2.2.

Remark 4.6. It is easy to verify that $\textbf {c}=(1,-1,0,\ldots ,0)$ is a codeword of the dual of ${\mathcal {C}}_1$ . This indicates that ${\mathcal {C}}_1$ cannot be an NMDS code when $k\geq 3$ .

According to the bijection $\varphi $ between ${\mathcal {C}}$ and ${\mathcal {C}}_1$ , it is easy to see the following lemma.

Lemma 4.7. For any distinct codewords $\mathbf {a},\textbf {b}\in {\mathcal {C}}_1$ ,

$$ \begin{align*}l(\varphi^{-1}(\mathbf{a}),\varphi^{-1}(\textbf{b}))\leq l(\mathbf{a},\textbf{b})\leq l(\varphi^{-1}(\mathbf{a}),\varphi^{-1}(\textbf{b}))+1.\end{align*} $$

Next, we show that ${\mathcal {C}}_1$ is an optimal AMDS insdel code.

Theorem 4.8. ${\mathcal {C}}_1$ is an $[n+1,k,d_I=2(n+1-2k+1)]_q$ AMDS insdel code. Consequently, ${\mathcal {C}}_1$ is an optimal AMDS code with respect to the strict half-Singleton bound.

Proof. It remains to show that $d_I({\mathcal {C}}_1)=2(n-2k+2)$ . According to Corollary 3.2, we have $d_I({\mathcal {C}}_1)\leq 2(n-2k+2)$ since the first k columns of $G_1$ are linearly dependent.

Suppose that $d_I({\mathcal {C}}_1)\leq 2(n-2k+1)$ . Then there exist two distinct codewords $\mathbf {a},\textbf {b}$ in ${\mathcal {C}}_1$ such that

$$ \begin{align*} l(\mathbf{a},\textbf{b})=\tfrac{1}{2}(2(n+1)-d_I(\mathbf{a},\textbf{b}))\geq 2(n+1)-2(n-2k+1)=2k. \end{align*} $$

From this, $l(\varphi ^{-1}(\mathbf {a}),\varphi ^{-1}(\textbf {b}))\geq l(\mathbf {a},\textbf {b})-1=2k-1$ , which indicates that

$$ \begin{align*}d_I({\mathcal{C}})\leq d_I(\varphi^{-1}(\mathbf{a}),\varphi^{-1}(\textbf{b}))=2n-2l(\varphi^{-1}(\mathbf{a}),\varphi^{-1}(\textbf{b}))\leq 2(n-2k+1).\end{align*} $$

This contradicts $d_I({\mathcal {C}})=2(n-2k+2)$ . Thus, we have $d_I({\mathcal {C}}_1)=2(n-2k+2)$ .