Words that almost commute

Abstract: The emph{Hamming distance}

e x t h a m (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 emph{conjugates} if there exist non-empty words

x, y

such that

u = x y

and

v = y x

. The smallest value

e x t h a m (x y, y x)

can take on is

0

, when

x

and

y

commute. But, interestingly, the next smallest value

e x t h a m (x y, y x)

can take on is

2

and not

1

. In this paper, we consider conjugates

u = x y

and

v = y x

where

e x t h a m (x y, y x) = 2

. More specifically, we provide an efficient formula to count the number

h (n)

of length-

n

words

u = x y

over a

k

-letter alphabet that have a conjugate

v = y x

such that

e x t h a m (x y, y x) = 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)

.

This page was built for publication: Words that almost commute