Strict Half-Singleton Bound, Strict Direct Upper Bound for Linear Insertion-Deletion Codes and Optimal Codes

Let C be an n, k linear code over the finite field Fₐ. Let d₈ (C) denote its insertion-deletion (insdel for short) distance, which characterizes the insdel error-correcting capability of C. To determine the insdel distances of linear codes is a very challenging problem. In this paper we propose a strict half-Singleton upper bound d₈ (C) 2 (n-2k+1) if C does not contain the codeword with all 1s, which generalizes the half-Singleton bound on the insdel distances of linear codes due to Cheng-Guruswami-Haeupler-Li, and a stronger direct upper bound d₈ (C) 2 (d₇ (C) -t) under a weak condition, where t 1 is a positive integer determined by the generator matrix and d₇ (C) denotes the Hamming distance of C. A sufficient condition for a linear code attaining the strict half-Singleton bound is given. We prove that the code length of an optimal binary linear insdel code with respect to the (strict) half-Singleton bound is about twice its dimension and conjecture that optimal binary linear insdel codes have exact parameters 2k, k, 4 or 2k+1, k, 4 with respect to the half-Singleton bound or the strict half-Singleton bound, respectively. Moreover, interestingly explicit optimal linear insdel codes attaining the (strict) half-Singleton bound, with the code length being independent of the finite field size, are given.