Polynomially larger deletion codes by linear hashing of substring counts

We show that binary codes of length $n$ correcting two deletions exist with redundancy $3{\log }_{2}n+O({\log }_2{\log }_{2}n)$. The previous best upper bound had leading coefficient $4$, unchanged since 1965, while the best known lower bound has coefficient $2$. More generally, codes correcting $t\ge 2$ deletions exist with redundancy $(2t-1){\log }_{2}n+O_t({\log }_2{\log }_{2}n)$, improving the coefficient $2t$. We extract a code from one label class of a random linear hash of substring counts, with about $n$ times fewer labels than a direct construction. Confusable words that still share a label are separated by a two-colouring after discarding the words in components with odd cycles, and these are few because an odd cycle forces the edits along it to overlap.