New bounds for the optimal density of covering single-insertion codes via the Turán density
For coding theorists, this provides tighter bounds on the optimal density of covering codes for insertions, though the improvements are incremental.
The paper improves lower and upper bounds on the optimal density of covering single-insertion codes over an n-symbol alphabet, showing the density cannot be smaller than 1/r + δ_r (improving the previous 1/(r+1)) and, for large r, the asymptotic upper bound is improved from 7/(r+1) to 4.911/(r+1).
We prove that the density of any covering single-insertion code $C\subseteq X^r$ over the $n$-symbol alphabet $X$ cannot be smaller than $1/r+δ_r$ for some positive real $δ_r$ not depending on $n$. This improves the volume lower bound of $1/(r+1)$. On the other hand, we observe that, for all sufficiently large $r$, if $n$ tends to infinity then the asymptotic upper bound of $7/(r+1)$ due to Lenz et al (2021) can be improved to $4.911/(r+1)$. Both the lower and the upper bounds are achieved by relating the code density to the Turán density from extremal combinatorics. For the last task, we use the analytic framework of measurable subsets of the real cube $[0,1]^r$.