Density of Ham- and Lee- non-isometric k-ary Words

Abstract

Isometric k-ary words have been defined referring to the Hamming and the Lee distances. A word is non-isometric if and only if it has a prefix at distance 2 from the suffix of same length; such a prefix is called 2-error overlap. The limit density of isometric binary words based on the Hamming distance has been evaluated by Klavzar and Shpectorov, obtaining that about 8% of all binary words are isometric. In this paper, the issue is addressed for k-ary words and referring to the Hamming and the Lee distances. Actually, the only meaningful case of Lee-isometric k-ary words is when k=4. It is proved that, when the length of words increases, the limit density of quaternary Ham-isometric words is around 17%, while the limit density of quaternary Lee-isometric words is even bigger, it is about 30%. The results are obtained using combinatorial methods and algorithms for counting the number of k-ary isometric words.