Words that almost commute

10/03/2021
by   Daniel Gabric, et al.
0

The Hamming distance ham(u,v) between two equal-length words u, v is the number of positions where u and v differ. The words u and v are said to be conjugates if there exist non-empty words x,y such that u=xy and v=yx. The smallest value ham(xy,yx) can take on is 0, when x and y commute. But, interestingly, the next smallest value ham(xy,yx) can take on is 2 and not 1. In this paper, we consider conjugates u=xy and v=yx where ham(xy,yx)=2. More specifically, we provide an efficient formula to count the number h(n) of length-n words u=xy over a k-letter alphabet that have a conjugate v=yx such that ham(xy,yx)=2. We also provide efficient formulae for other quantities closely related to h(n). Finally, we show that there is no one easily-expressible good bound on the growth of h(n).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset