Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Construct a string by using only n characters, the string should do not contain any consecutive repeated pattern, in other words, the string must have not any substring matching /(.+)\1/, what is the length l(n) of the longest string S(n)?

n    S(n)    l(n)
1    a       1
2    aba     3
3    ?       ?
4    ?       ?

Edit:
abcabacbabcabacabcac has none consecutive repeated pattern,so l(3)>=20

share|improve this question
1  
Could you explain the code? In your example "aba", it seems that "a" is repeated. –  damiano Aug 26 '10 at 9:16
1  
Another way to say this is that there are no identical consecutive substrings. –  Dan Brumleve Aug 26 '10 at 9:30

3 Answers 3

up vote 4 down vote accepted

A theorem of Thue's (not Thue's theorem!) states that for $n = 3$ (and therefore, also for larger $n$) an infinite sequence of characters (chosen out of $n$) without repeated sub-sequences (a.k.a square-free) exists.

Edit: here's a slightly related reference: J.D. Currie's paper 'There are ternary circular square-free words of length n for n 18.', which at least has a reference to Thue's paper from 1906.

Edit 2: Another reference, with explicit construction of sequences of length 3, 9, 27 and so on: http://arxiv.org/abs/0712.0139. That paper gives the following sequence of length 27: 123213231213123132312132123

share|improve this answer

To find a maximal string for n letters, add a new letter in every other place of a maximal string for n-1 letters. It is still the case that no consecutive identical substrings exist. No more letters can be added because two of them would have to appear consecutively, so this is the best that is possible. The length of the string is 2^n-1.

a bab cbcacbc dcdbdcdadcdbdcd

share|improve this answer
    
Why does No new letters can be added imply that this is the best that is possible? –  anon Aug 26 '10 at 9:50
    
We can't insert more letters into a string than there are spaces between letters in that string (1 more than its length) without two of them being consecutive which isn't allowed –  Dan Brumleve Aug 26 '10 at 10:12
1  
abcabacbabca have not any substring matching /(.+)\1/. so l(3)>=12 –  a boy Aug 26 '10 at 10:27
    
Indeed! I was mistaken to think it had to be built from a largest solution on fewer letters. –  Dan Brumleve Aug 26 '10 at 10:41

Let me apologize, for it's not an answer, but merely an extended comment. I like the problem very much. It sounds very classical, and most likely the answer must be known.

Being reformulated, the problem is as follows: if $X$ is an $n$-letter alphabet, we have a rewriting rule $$ w_1 s s w_2=w_1 s^2 w_2 \to w_1 w_2 $$ where $s$ is nonempty and at least one of $w_1,w_2$ must be nonempty. (In effect, any word that satisfies the condition set by a-boy must be square-free so to speak.) One can also a semigroup with $n$ generators whose relations are determined by the rewriting rule above.

The problem as set asks whether all words over $X$ are reduced to words of certain length $l(n).$ One wonders, however, whether $n=2$ is an exceptional case, and actually there are arbitrary large reduced words. For instance, the following word of length 68 in letters $0,1,2$ is reduced:

12012101201020120212012101202101210201202120121012010201202120121012

For a 4-letter alphabet it is easy to find words of quite large length (I've found by means of computing such words of lenght $\ge 1000.$)

share|improve this answer
    
Haven't seen the answer by yatima2975 (please see below), when writing my comment. He confirmed my suspitions that there must be reduced words of arbitrary large length when $|X| \ge 3.$ –  Olod Aug 26 '10 at 13:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.