Two words *u* and *v* commute (that is, *uv=vu*) if and only if they have the same primitive root. This means that there is a primitive word *t* and integers *i,j* such that *u=t*^{i} and *u=t*^{j}.

This is the most simple form of the following stronger statement:

- Two words commute if and only if they satisfy a nontrivial relation. This, in turn, is the GraphLemma for two words.

Yet more general is the following fact which is connected to the PeriodicityLemma:

- Let
*w*and_{u}*w*be two words generated by_{v}*u*and*v*, where*w*starts with_{u}*u*and*w*starts with_{v}*v*. If*w*and_{u}*w*have a common prefix of length at least_{v}*|u|+|v|-GCD(|u|,|v|)*, then*u*and*v*commute.

-- StepanHolub - 10 Sep 2011

Edit | Attach | ~~Watch~~ | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r1 - 2011-09-10 - StepanHolub

Copyright © 2008-2023 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback