Corrections to “Reed Solomon Codes Against Adversarial Insertions and Deletions”

The purpose of this note is to correct an error made by Con et al. (2023), specifically in the proof of Theorem 9. Here we correct the proof but as a consequence we get a slightly weaker result. In Theorem9, we claimed that for integers k and n such that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k \lt n/9$ </tex-math></inline-formula>, there exists an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$[n,k]_{q}$ </tex-math></inline-formula> RS code that can decode from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n-2k+1$ </tex-math></inline-formula> insdel errors where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q = O\left ({{k^{5} \left ({{ \frac {en}{k-1} }}\right)^{4k-4}}}\right)$ </tex-math></inline-formula>. Here we prove the following. Theorem 1: For integers n and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k \lt n/9$ </tex-math></inline-formula>, there exists an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$[n,k]_{q}$ </tex-math></inline-formula> RS-code, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q=O\left ({{k^{4} \cdot \left ({{\frac {4en}{4k-3}}}\right)^{4k-3}}}\right)$ </tex-math></inline-formula> is a prime power, that can decode from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n - 2k + 1$ </tex-math></inline-formula> adversarial insdel errors. Note that the exponent of n is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$4k-3$ </tex-math></inline-formula> whereas in Theorem 9 it is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$4k-4$ </tex-math></inline-formula>. For constant dimensional codes, the field size is of order <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n^{4k-3})$ </tex-math></inline-formula>, and in particular, for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k=2$ </tex-math></inline-formula> the field size is of order <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(n^{5})$ </tex-math></inline-formula>.