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 Klavzˇar 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.
isometric if and only if for any integer d ≥ | f | and any pair of words u and v of length d which do not contain the factor f , u can be transformed in v by exchanging one by one the bits on which they differ and generating only words which do not contain f . Differently saying, this transformation is composed by single steps transforming a word in another at Hamming distance 1. We will call it an f -free Ham-transformation and the resulting isometric words, Ham-isometric words. When moving from binary to k-ary alphabets, with k ≥ 2, the hypercubes are replaced by the k-ary n-cubes where the vertices are k-ary words of length n. In this case, the distance between two vertices is no more captured by the Hamming distance, but by the Lee distance.
been introduced; see [
The notion of isometric word combines the distance notion with the property that a word does
not appear as factor in other words. Note that this property is important in combinatorics as well
as in the investigation on similarities, or distances, on DNA sequences, where the avoided factor
is referred to as an absent or forbidden word [
Deciding whether a word is Ham-isometric (Lee-isometric, resp.) can be efficiently done using the characterization of Ham-non-isometric (Lee-non-isometric, resp.) words as the ones showing a particular overlap with errors, called 2-Ham-error overlap (2-Lee-error overlap, resp.). A 2-Ham-error overlap (2-Lee-error overlap, resp.) of a word f is a prefix of f whose Hamming (Lee, resp.) distance from the suffix of same length is exactly 2. This is a similar concept as the overlap, or border, of a word, i.e. a prefix which is equal to the suffix of same length. Words having no overlap are known in the literature as the non bifix-free words or unbordered words. Such notions play a crucial role both in combinatorics of words and in pattern matching (with or without errors).
In [
In this paper we extend such results by proving that Ham- and Lee- isometric words over a k-ary alphabet, with k > 2, can be even more than in the binary case. The density of Hamisometric k-ary words is investigated for any k; upper and lower bounds are given depending on k and on the length n of words for which the density can be explicitely computed. Here, the computation has been carried on for k = 4 and n = 3, ..., 16, and the values are collected in a table. In an analogous way, the density of Lee-isometric words has been lower and upper bounded. Recall that there are no Lee-isometric words for k > 5, and that Lee-isometric words are exactly the Ham-isometric words, when k = 2, 3. So the results concern the unique meaningful case of k = 4. In the quaternary case, the density of Ham-isometric and Lee-isometric words has been explicitely evaluated and compared. There are about the 17% of Ham-isometric quaternary words, whereas about 30% of Lee-isometric quaternary words. Remarkably, there are strictly more Lee-isometric quaternary words than the Ham- ones. The motivation of this claim has been explored.
The computation of explicit values of the density of Ham- and Lee- isometric quaternary words
for small lenghts has been carried on using an algorithm to efcfiiently check whether a word
is isometric. A first cubic time algorithm for deciding isometricity and providing evidence and
further information about it was given in [
n
∑ min(|xi − yi|, k − | xi − yi|).
i=1
Let us recall some definitions and notation given in [
Let Σ be an alphabet and |Σ| = k. Throughout the paper, Σ will be identified with Zk = {0, 1, . . . , k − 1}, the ring of integers modulo k. A word (or string) f ∈ Σ∗ of length n is f = x1x2 · · · xn, where x1, x2, . . . , xn are symbols in Σ. The set of words over Σ of length n is denoted Σn. Let f [i] denote the symbol of f in position i, i.e. f [i] = xi. Then, f [i.. j] = xi · · · x j, for 1 ≤ i ≤ j ≤ n, is a factor of f . A word s ∈ Σ∗ is said f -free if it does not contain f as a factor. The prefix of f of length l is prel( f ) = f [1..l]; while the suffix of f of length l is su fl( f ) = f [n − l + 1..n]. When prel( f ) = su fl( f ) then prel( f ) is referred to as an overlap, or border, of f of length l.
Let u, v ∈ Σ∗ be two words of the same length. The Hamming distance distH (u, v) between u and v is the number of positions at which u and v differ.
The Lee distance between two words u, v ∈ Zkn, u = x1 · · · xn and v = y1 · · · yn is distL(u, v) = In the sequel, Σ will denote a generic alphabet of cardinality k, while ∆ denote the quaternary alphabet ∆ = {A,C, T, G}, referred to as the genetic alphabet. Symbols A and T (C and G, resp.) will be called complementary symbols, in analogy to the Watson-Crick complementary bases they represent. The alphabet ∆ will be identified with Z4, in such a way that A, C, T , and G will be identified with 0, 1, 2, and 3, respectively. Therefore, pairs of complementary symbols have Lee distance 2, whereas pairs of distinct non-complementary symbols have Lee distance 1.
Let us now recall the definitions of Ham and Lee-isometric words [
A Ham-transformation (Lee-transformation, resp.) of length h from u to v is a sequence of f : f : x i x r + i y j y r + j r l = n − r r words w0, w1, . . . , wh such that w0 = u, wh = v, and for any i = 0, 1, . . . , h − 1, distH (wi, wi+1) = 1 (distL(wi, wi+1) = 1, resp.). If for any i = 0, 1, . . . , h, the word wi is f -free, then the Hamtransformation (Lee-transformation, resp.) is said f -free.
A word f ∈ Σn is Ham-isometric (Lee-isometric, resp.) if for all d ≥ n, and f -free words u, v ∈ Σd, there is an f -free Ham-transformation (Lee-transformation, resp.) from u to v of length equal to distH (u, v) (distL(u, v), resp.). A word is Ham-non-isometric (Lee-non-isometric, resp.) if it is not Ham-isometric (Lee-isometric, resp.).
Example 1. Let ∆ be the quaternary genetic alphabet, f = ACT , u = ACCCT , and v = ACGCT . Observe that distL(u, v) = 2, since they differ in their third position only and distL(C, G) = 2.
transformations from u to v of length equal to distL(u, v) = 2; they are not f -free. Hence, no f -free Lee-transformation exists from u to v. This shows that ACT is Lee-non-isometric.
Let us recall the following definitions (see Figure 1) of Ham- and Lee-error overlap.
The word f has a q-Ham-error overlap (q-Lee-error overlap, resp.) of length l, 1 ≤ l ≤ n − 1, if distH (prel( f ), su fl( f )) = q (distL(prel( f ), su fl( f )) = q, resp.). Its error positions are the q (m, 1 ≤ m ≤ q, resp.) positions in prel( f ) where it differs from su fl( f ).
Remark 1. Using the notations in the previous definition, if f has a q-Lee-error overlap of length l, then 1 ≤ m ≤ l, q.
In particular, when k = 4 and q = 2, then m = 1 or m = 2. The case m = 1 holds if prel( f ) and su fl( f ) differ in exactly one position and the error is given by a pair of complementary symbols. For example, f = AGAC ∈ ∆4 has a 2-Lee-error overlap of length l = 2. Indeed, m = 1 and distL(AG, AC) = 2. If m = 2 then prel( f ) and su fl( f ) differ in two different positions i and j and the errors are given by pairs of non-complementary symbols.
Theorem 1, proved in [
Theorem 1 ([
Example 2. Let f = 0201 ∈ Σ∗ with Σ = Z3 = {0, 1, 2}. The word f has no 2-Ham-error overlap and thus it is Ham-isometric, by Theorem 1. Consider now f = ATC ∈ ∆∗ . The word f has no
theorem, f = ATC is Ham-non-isometric, since it has a 2-Ham-error overlap.
Next result allows us to restrict the domain of strings to be considered when looking for Lee-isometric words. For example, when the alphabet is ∆, it is sufficient to take into account words starting with A.
Let Σ = {0, 1, . . . , k − 1}, f = f1 f2 · · · fn be a word over Σ, u, v ∈ Σd be f -free words, and h, j ∈ Σ. The reverse of f is f R = fn · · · f2 f1. The h-shift of j is jS(h) = ( j + h) mod k, while the h-shift of f is f S(h) = f1S(h) f2S(h) · · · fnS(h). When k = 2, the 1-shift of f is its complement. Lemma 1. Let Σ be a k-ary alphabet and f ∈ Σ∗ . Then • f is Lee-isometric if and only if f R is Lee- isometric • for any h ∈ Σ, f is Lee-isometric if and only if f S(h) is Lee-isometric.
The density of Ham-isometric binary words has been studied in [
The values in the table show that the density is not a monotone sequence. That is why we will separately consider the density of words with a “long" 2-error overlap, and of words with a “short" 2-error overlap.
Let H k,n be the set of all k-ary words of length n having a 2-Ham-error overlap. Let H skh,nort be
the set of all words in H k,n which have a 2-Ham-error overlap of length l ≤ n/2, H lko,nng be the set
of all words in H k,n which have a 2-Ham-error overlap of length l > n/2. A word in H skh,nort is
called split (as in [
Clearly, H k,n = H skh,nort ∪ H lko,nng, but H skh,nort ∩ H lko,nng is not necessarily empty. In particular, |H k,n| ≤ |
H skh,nort | + |H lko,nng|. Also note that Hk,n \ Hks,hnort ⊆
Hkl,onng. 3 4 5 6 7 8 9 10 11 12 13 14 15 hn 36 168 804 3228 13404 54516 216756 875052 3490236 13994460 55909620 223809540 894723276 0,59375 0,609375
Example 3. Let ∆ = {A,C, T, G} be the genetic alphabet and f = AAGATAA in ∆7. The word f is Ham-non-isometric. It has a 2-Ham-error overlap of length l = 3 that involves error positions i = 1 and j = 3 with distH(AAG, TAA) = 2. Since l ≤ n/2, then f ∈ H s4h,7ort. Furthermore, f has also a 2-Ham-error overlap of length l = 4 that involves error positions i = 2 and j = 3 with distH(AAGA, ATAA) = 2. Since l > n/2, then f ∈ H l4o,7ng. Therefore, f belongs to both sets
Let us denote hk,n = |Hk,n|, sk,n = |Hks,hnort| and lk,n = |Hkl,onng|. From |H k,n| ≤ | H skh,nort|+|H lko,nng|, it follows hk,n ≤ sk,n + lk,n. Further denote by αk,n, σk,n, and λk,n the density of words in H k,n, H skh,nort, and H lko,nng, respectively, among all words of length n, i.e., αk,n = hkkn,n , σk,n = skkn,n , and λk,n = lk,n .
kn
Let us start by counting the number of words with a 2-Ham-error-overlap of fixed length. Denote by hk,n(d) the number of words in H k,n that have a 2-Ham-error overlap of length d, for some 2 ≤ d ≤ n − 1; by sk,n(d) the number of words in H skh,nort that have a 2-Ham-error overlap of length d, for some 2 ≤ d ≤ ⌊ n/2⌋; and by lk,n(d) the number of words in H lko,nng that have a 2-Ham-error overlap of length d, for some ⌊n/2⌋ < d ≤ n − 1.
Lemma 2. Let Σ be a k-ary alphabet. Then, hk,n(d) = d(d2− 1) (k − 1)2kn− d.
Proof. Let f be a k-ary word of length n that has a 2-error overlap of length d, for some 2 ≤ d ≤ n − 1. The word f is fully specified by three informations: the bits in the last n − d positions of f , the 2 locations of the “errors” within pre fd( f ) and by the symbols in these error positions, which can be chosen in k − 1 ways each. The number of choices of 2 positions within the d positions in pre fd( f ) is (︁ d2)︁ . Hence, hk,n(d) = kn− d(︁ d2)︁ (k − 1)2 = d(d2− 1) (k − 1)2kn− d. Remark 2. Note that a k-ary word f of length n may have 2-Ham-error overlaps of different n− 1 lengths. This implies that |H k,n| = hk,n ≤ ∑ hk,n(d). Similar reasonings show that |Hks,hnort | = d=2 sk,n ≤ ⌊n/2⌋ ∑ sk,n(d) and that |Hkl,onng| = lk,n ≤ d=2 n(n − 1)2. Therefore, and limn→∞ λk,n = 0.
Contrarily to the case of the sequence αk,n, the following result holds for σk,n. Proposition 2. Let Σ be a k-ary alphabet. The sequence σk,n is monotonically increasing and bounded from above by 1. In particular, it has a limit σk ≤ 1.
Proof. Let us show that for any n ≥ 1, sk,n+1 ≥ ksk,n so that σk,n+1 = skkn,n++11 ≥ skkn,n = σk,n. Consider the mapping ϕ : Σn+1 → Σn defined by erasing the bit in position ⌊︂ n2 ⌋︂ + 1. Now, if f ∈ Σn+1 and ϕ( f ) has a 2-error overlap of some length d ≤ ⌊︂ n2 ⌋︂, then f has also a 2-error overlap of the same length d. Therefore, ϕ− 1(H skh,nort ) ⊆ H skh,no+rt1 and the claim follows noting that every f ∈H skh,nort is the image of k different elements in H skh,no+rt1.
Proposition 3. Let Σ be a k-ary alphabet. The sequence αk,n converges to the same limit value σk, as σk,n.
Proof. According to Proposition 1, the sequence λk,n tends to zero. Hence both σk,n and σk,n +λk,n converge to the same limit, σk. On the other hand, clearly, σk,n ≤ αk,n ≤ σk,n + λk,n, since Hks,hnort ⊆ Hk,n ⊆ Hks,hnort ∪ Hkl,onng. So the claim follows.
Let us estimate σk, the limit value of both density sequences σk,n and αk,n.
Theorem 2. Let Σ be a k-ary alphabet. The limit value σk of the density of Ham-non-isometric k-ary words is
σk,2m ≤ σk ≤ σk,2m + f (k, m) where, for any integer m ≥ 1,
∞ i(i + 1) f (k, m) = ∑ i=m 2ki− 1 .
Proof. Using Proposition 2, the sequence σk,n is monotonically increasing, hence, for any n ≥ 2, σk,n ≤ σk. Furthermore, sk,2m+1 = ksk,2m and then σk,2m+1 = σk,2m, so that we only need to consider even n = 2m.
Let tk,n be the number of non-split words of length n, i.e., tk,n = |Σn \ Hks,hnort |. If w is such a word then inserting two new symbols in the middle produces a word of length n + 2 which is either again non-split or it has a 2-error overlap of length exactly m + 1. The number of words of the latter sort is km+1(︁ m+1)︁ (k − 1)2, because we can choose m + 1 symbols arbitrarily and then the second half 2 must be the same as the first half but with two positions changed in k − 1 ways each. Therefore, k2tk,n ≤ tk,n+2 + km+1(︁ m+21)︁ (k − 1)2 and, dividing by kn+2, tkk,nn ≤ tkk,nn++22 + (k − 12)k2mm+(1m + 1) .
Referring to the densities µk,n = tkk,nn of non-split k-ary words of length n, one has µk,n+2 ≥ (k − 1)2m(m + 1) µk,n − 2km+1 .
(k − 1)2m(m + 1) Since σk,n = 1 − µk,n, we get σk,n+2 ≤ σk,n + 2km+1 Combining these relations from n to n + p, we obtain ≤ σk,n + m(m + 1)
2km− 1 . σk,n+2p ≤ σk,n + m+p− 1 i(i + 1) i∑=m 2ki− 1 . n ≥ 2, n = 2m, σk,n ≤ σk ≤ σk,n + ∑∞ i(i + 1)
i=m 2ki− 1 .
Therefore, the following upper bound for σk follows: σk ≤ σk,n + ∑∞ i(i + 1) i=m 2ki− 1 . Hence, for any evaluation can be obtained
Let us now evaluate i∑=∞m i(2ik+i− 11) . Note that i∑=∞m i(2ik+i− 11) = 2k i∑=∞m(︁ ki2i + kii ︁) .
∞ ∞ m− 1 Setting x = 1/k in classical formulas for ∑ i2xi, m∑−1 i2xi, ∑ ixi, and ∑ ixi, the following i=1 i=1 i=1 i=1 ∞ i(i + 1) ∑ i=m 2ki− 1 = (m2 + m)k2 − (2m2 − 2)k + (m2 − m) 2(k − 1)3km− 2 . 3.2. Density of Lee-isometric words In order to evaluate the density of Lee-isometric quaternary words some of the results regarding Ham-isometric words must be properly modified.
Remember that the only significant case is now the case of a quaternary alphabet. Let ∆ = {A,C, T, G} be the alphabet with k = |∆| = 4. The main difference is that a word f ∈ ∆∗ has a 2-Lee-error-overlap when, for some d ≤ n − 1, pre fd( f ) differs from su fd( f ) in either 2 positions which contain different non-complementary symbols or 1 position which contains two complementary symbols.
In analogy to the case of the Hamming distance, let us state the following notations. Note that the value k = 4 is understood.
Let Ln be the set of all words in ∆∗ of length n having a 2-Lee-error overlap.
Let Lnshort be the set of all words in Ln which have a 2-Lee-error overlap of length l ≤ n/2, while Llnong be the set of all words in Ln which have a 2-Lee-error overlap of length l > n/2. A word in Lskh,nort is called L-split. Let us denote ˆh︁n = |Ln|, sˆ︁n = |Lnshort |, ˆl︁n = |Lnlong|, and by αˆ︁n, σˆ︁n, and ˆλ︁n the density of words in Ln, Lsnhort , and Llnong, respectively, among all words of length n, i.e., αˆ︁n = ˆhk︁nn , σˆ︁n = kˆ︁nn , and ˆλ︁n = ˆ︁n .
s l
kn
Finally, let ˆh︁n(d) be the number of words in Ln that have a 2-Lee-error overlap of length d, for some 2 ≤ d ≤ n − 1; sˆ︁n(d) be the number of words in Lsnhort that have a 2-Lee-error overlap of length d, for some 2 ≤ d ≤ ⌊ n/2⌋; and ˆl︁n(d) be the number of words in Llnong that have a 2-Lee-error overlap of length d, for some ⌊n/2⌋ < d ≤ n − 1.
Lemma 3. The number of words in ∆∗ of length n that have a 2-Lee-error overlap of length d, is ˆh︁n(d) = (︁ 2d2 − d︁) 4n− d.
Proof. Let f be a word in ∆n that has a 2-Lee-error overlap of length d, for some 1 ≤ d ≤ n − 1. Then pre fd( f ) and su fd( f ) differ either in two positions, and the errors are given by a pair of non-complementary symbols, or in one position, and the error is given by a pair of complementary symbols. Therefore, in the first case, f is fully specified by three informations: the bits in the last n − d positions of f , the 2 locations of the errors within pre fd( f ) and by the pairs of symbols in these error positions, which can be chosen in 4 different ways. In the second case, the word f is fully specified by two informations: the bits in the last n − d positions of f and the location of the error within pre fd( f ). Hence, ˆh︁n(d) = 4n− d[︁ 4(︁ d)︁ + d]︁ = (︁ 2d2 − d︁) 4n− d.
2 Proposition 4. The density of words in Llnong converges to 0 as n goes to infinity, i.e.
nl→im∞ˆλ︁n = 0.
Proof. Let ˆl︁n(d) be the number of words ∈ ∆n that have a 2-Lee-error overlap of length exactly d, for some ⌊n/2⌋ < d ≤ n − 1. From Lemma 3, we have
n− 1 ˆl︁n ≤ ∑ 4n− d(︁ 2d2 − d︁) . Then, d=⌊n/2⌋+1
n− 1 ˆl︁n ≤ 2 · 4n/2 ∑ d=⌊n/2⌋+1
l Therefore, ˆλ︁n = ˆ︁n 4n ≤ and limn→∞ˆλ︁n = 0.
(n − 1)2 ≤ 4n/2n(n − 1)2.
The following propositions can be proved similarly to Propositions 2 and 3.
Let us estimate the limit density σˆ︁ of both sequences σˆ︁n and αˆ︁n.
Theorem 3. The limit value σˆ︁ of the density of Lee-non-isometric words in ∆∗ is σˆ︁2m ≤ σˆ︁ ≤ σˆ︁2m + f (m) where, for any integer m ≥ 1,
∞ 2i2 + 3i + 1 f (m) = i∑=m 4i+1 = .
Proof. Using Proposition 5, the sequence σˆ︁n is monotonically increasing, hence, for any n ≥ 2, σˆ︁n ≤ σˆ︁. Furthermore, sˆ︁2m+1 = 4sˆ︁2m and then σˆ︁2m+1 = σˆ︁2m, so that we only need to consider even n = 2m.
Let ˆt︁n be the number of non-L-split words of length n. If w is such a word then inserting two new symbols in the middle produces a word of length n + 2 which is either again non-L-split or it has a 2-Lee-error overlap of length exactly m + 1. The number of words of the latter sort is 4m+1[︁ 4(︁ m+1)︁ + m + 1]︁ , because we can choose m + 1 symbols arbitrarily and, then, the second 2 half must be the same as the first half but either with two positions changed in 2 ways each (if the errors are given by a pair of non-complementary symbols) or with one position changed in exactly one way (if the error is given by a pair of complementary symbols). tn Therefore 42 ˆt︁n ≤ ˆt︁n+2 + 4m+1[︁ 4(︁ m+1)︁ + m + 1]︁ and, dividing by 4n+2, one obtains 4ˆ︁n ≤ 2
Referring to the densities µn, one has ˆµ︁n+2 ≥ ˆµ︁n − 4m1+1 (︁ 2m2 + 3m + 1)︁ . Since σˆ︁n = 1 − ˆµ︁n, we get σˆ︁n+2 ≤ σˆ︁n + 4m1+1 (︁ 2m2 +ˆ︁3m + 1)︁ . Combining these relations from n to n + p, one has σˆ︁n+2p ≤ σˆ︁n + m+p− 1 2i2 + 3i + 1 i∑=m 4i+1
.
∞ 2i2 + 3i + 1 n ≥ 2, n = 2m, σˆ︁n ≤ σˆ︁ ≤ σˆ︁n + i∑=m 4i+1 ∞ 2i2 + 3i + 1 Therefore, the following upper bound for σˆ︁ follows: σˆ︁ ≤ σˆ︁n + i∑=m 4i+1 . The sum can be evaluated by using classical . Hence, for any formulas as in the proof of Theorem 2 ∞ 2i2 + 3i + 1 i∑=m 4i+1 =
Let us now compare the density of Ham- and Lee- isometric words in the unique significant
case, that is when the alphabet has cardinality k = 4. Hence, in this section the value of k
will be understood. It turns out that there are more Lee- isometric words than Ham-isometric
words. Observe that the result is not obvious. In fact, the set of all Ham-isometric words is not
inclusion-wise comparable with the set of Lee-isometric words. Examples are given in [
Denote H n the set of quaternary words of length n having a 2-Ham-error overlap and Ln the corresponding set for the Lee distance case.
Proposition 7. Let f ∈ ∆n. Then • f ∈ H n ∩ Ln iff f has both a 2-Ham-error overlap and a 2-Lee-error overlap • f ∈ H n \ Ln iff f has a 2-Ham-error overlap and every 2-Ham-error overlap involves pairs of non-complementary symbols, only • f ∈ Ln \ H n iff f has a 2-Lee-error overlap and every 2-Lee-error overlap has only one error position that involves a pair of complementary symbols.
Proposition 8. Let n ≥ 2 be an integer. Then • if d = 1 then ˆh︁n(d) = 4n− 1 and hn(d) = 0 • If d ≥ 2 then ˆh︁n(d) = hn(d) − (5d − 7)/2 Proof. No 2-Ham-error overlap may have length 1; hence hn(1) = 0. On the other hand, a 2-Lee-error overlap may have length 1. In this case the first and the last symbol in the word are complementary ones. Hence, a word of length n with a 2-Lee-error overlap of length 1 is specified by the first symbol, in 4 ways, and the next n − 2 symbols. Then, ˆh︁n(d) = 4n− 1. Finally, if d ≥ 2, the claim follows from Lemmas 2 and 3.
Unfortunately, as already observed, the previous result cannot be extended to ˆh︁n or hn. The ifrst values of ˆh︁n and hn have been calculated and collected in Table 1. In particular, note that ˆh︁n ≤ hn, for any 3 ≤ n ≤ 16.
Similar calculations show that the density sequences αˆ︁n and αn are not monotonically increasing, already for n ≤ 16, see Table 1. Let us compare the limit values σˆ︁ and σ. The two following results are consequences of Theorems 2 and 3.
Corollary 1. The limit value σ of the density of Ham-non-isometric quaternary words is
Proof. Taking m = 8, n = 16, the formula of previous theorem becomes σˆ︁16 ≤ σˆ︁ ≤ σˆ︁16 +
0.000843. Adapting efficient algorithms as in [
The two previous results together allow to compare the limit values σ and σˆ︁ of the densities of Ham- and Lee-non-isometric quaternary words.
Proposition 9. 0.705357 ≤ σˆ︁ ≤ σ ≤ 0.836195.
Let us conclude that the Lee-isometric quaternary words are considerably more than the Hamisometric ones. In fact, for large n, the number of Ham-isometric words is approximately 17% of all words of that length, whereas the corresponding number for Lee-isometric words is about 30%.
Isometric words are at the crossroads of several areas of computer science. They were introduced in the framework of hypercubes and then characterized in terms of overlaps with errors in a word. They can also be defined referring to transformations on words that avoid factors. In this paper, we investigated the density of isometric words defined with respect to Hamming and Lee distances, considering alphabets of any cardinality. Clearly, the results can be restated in terms of the other equivalent characterizations. As a future work, it would be worthwhile to carry out a similar study on the density of isometric words also referring to other distances, as the aforementioned distance based on swap and mismatch operations.
The authors acknowledge support by INdAM-GNCS Project 2022, FARB Project ORSA229894 of University of Salerno, PNRR MUR Project ITSERR CUP B53C22001770006 of University of Palermo, TEAMS Project and PNRR MUR Project PE0000013-FAIR of University of Catania.