Words that almost commute
share
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