Welcome to the Alpha build of TypeGG! For the best user experience, we recommend playing
with an account. Login
Combinatorics on Words
by M. Lothaire
⇥ Before starting the proof, it will be interesting to note the difference between the relations (2.4.1) and (2.4.2). For the congruence defined by (2.4.1), two distinct words can be congruent only if both contain at least one pth power, for p = min(m,n). On the contrary, two distinct square-free words may be congruent for ~. Indeed, the defining relations allow introduction of squares and then dropping of other ones. We give now a nontrivial illustration of this situation by verifying that x~y with x = bacbcabc and y = bacabc. Both x and y are square-free words, and they are also equivalent. Indeed, note first that with u = abcaca, we have (boldfaced factors are those to be reduced) uy = abcacabacabc~abcacabc~abcabc~abc whence x = (bacbc)abc~bacbcuy = vy for v = bacbcu.⏎⇥ Next, for r = bcabacbcacbcbac, we have⏎ ⏎ xr = bacbcabcbcabacbcacbcbac⏎ ~bacbcabacbcacbcbac⏎ ~bacbcacbcbac~bacbcbac~bacbac~bac⏎ whence⏎ y = bacabc~xrabc~xs⏎ with s = rabc. Finally,⏎ x~vy~vyy~xy~xxs~xs~y,⏎ which proves the claim.🏁
Submitted by zero - 01/21/2026
Academia Educational 7.67 Ranked
Global Leaderboard
| # | Player | Time | Duration | Accuracy | WPM | pp | ||
|---|---|---|---|---|---|---|---|---|
| 1 | ||||||||
| 2 | ||||||||
| 3 | ||||||||
| 4 | ||||||||
| 5 | ||||||||
| 6 | ||||||||
| 7 | ||||||||
| 8 | ||||||||
| 9 | ||||||||
| 10 |
Combinatorics on Words
by M. Lothaire
⇥ Before starting the proof, it will be interesting to note the difference between the relations (2.4.1) and (2.4.2). For the congruence defined by (2.4.1), two distinct words can be congruent only if both contain at least one pth power, for p = min(m,n). On the contrary, two distinct square-free words may be congruent for ~. Indeed, the defining relations allow introduction of squares and then dropping of other ones. We give now a nontrivial illustration of this situation by verifying that x~y with x = bacbcabc and y = bacabc. Both x and y are square-free words, and they are also equivalent. Indeed, note first that with u = abcaca, we have (boldfaced factors are those to be reduced) uy = abcacabacabc~abcacabc~abcabc~abc whence x = (bacbc)abc~bacbcuy = vy for v = bacbcu.⏎⇥ Next, for r = bcabacbcacbcbac, we have⏎ ⏎ xr = bacbcabcbcabacbcacbcbac⏎ ~bacbcabacbcacbcbac⏎ ~bacbcacbcbac~bacbcbac~bacbac~bac⏎ whence⏎ y = bacabc~xrabc~xs⏎ with s = rabc. Finally,⏎ x~vy~vyy~xy~xxs~xs~y,⏎ which proves the claim.🏁
Submitted by zero - 01/21/2026
Academia Educational 7.67 Ranked