Fri, 12 Mar 2004 12:14:18 -0800 Scott Kim <scott@scottkim.com> Is it possible to create an infinite string made of the three digits 1, 2, 3 such that no sequence of digits is exactly repeated twice consecutively? In other words 11, 1212, 123123 and 12131213 are all illegal subsequences. I vaguely recall seeing a solution to this question -- I'm pretty sure the answer is yes -- but I can't recall where. Dean Hickerson sent the following mail earlier this year. It contains the answer to your question: Date: Tue, 6 Jan 2004 21:02:57 -0800 From: Dean Hickerson <dean@math.ucdavis.edu> Here's a question (worth $60) from Sherman Stein (stein@math.ucdavis.edu). It asks if a certain process, described later, continues forever. I did some computing a few years ago, and found that it runs for at least 30 million steps. I suspect that it stops eventually, but my program wasn't fast enough to find out when. Sherman thinks it'll run forever. We're hoping that someone else can think of either a proof that it runs forever, or a faster algorithm that will determine when it stops. (Some of this is discussed in Sherman's book "How the other half thinks".) We want to construct an infinite string over a finite alphabet which doesn't contain any squares. (A square is a substring of the form XX where X is a nonempty string.) An infinite squarefree string is sometimes called a Thue sequence, because the problem was apparently first posed and solved by Axel Thue in 1912. It's easy to see that there's no Thue sequence over an alphabet with only 2 symbols; in fact every binary string of length 4 contains a square. But with 3 or more symbols, Thue sequences exist. Thue proved this using a method called "expansion". The expansion of a string is obtained by replacing every 0 by 01201, every 1 by 020121, and every 2 by 0212021. It can be shown that if a string has no squares then neither does its expansion. So we can get an infinite squarefree sequence by starting with 0 and repeatedly expanding: 0 -> 01201 -> 01201020121021202101201020121 -> 0120102012102120210120102012101201021202101201020121021202102012101201 0212021020121021202101201021202102012101201020121021202101201020121012 010212021012010201210212021020121 -> ... There are variations on this method, in which 0, 1, and 2 are replaced by different strings. This particular triple of strings has been shown to have the shortest total length among all triples for which the expansion of every squarefree string is squarefree. Sherman wondered if a Thue sequence could be constructed by a greedy algorithm: What if we start with the empty string and repeatedly append the smallest number in {0,1,2} which doesn't create any squares? After 7 steps we get 0102010. But now we're stuck: adding 0 gives the square 00, adding 1 gives 0101 and adding 2 gives 01020102. Even if we use more than 3 symbols, this process always stops. In fact, with n symbols it stops after 2^n - 1 steps. E.g. with 5 symbols we get 0102010301020104010201030102010. Instead of always adding the smallest possible symbol, suppose we alternate between adding the smallest and adding the largest. It turns out that the process again stops after 2^n - 1 steps if we use n symbols. E.g. with 5 symbols we get 0403040204030401040304020403040. We can try other variations: We can use any infinite string of S's and L's to decide whether to append the smallest or largest symbol at each point. So the two algorithms just discussed are represented by the strings SSSS... and SLSLSL... We're mainly interested in periodic SL-strings, so we'll shorten the names of these to just S and SL. Sherman and I experimented with other strings, and eventually conjectured that, with 3 symbols, every periodic SL-string gives only a finite squarefree string. Here are some examples of the lengths that we get for certain strings: S 7 SL 7 SSL 19 SLS 27 SLL 26 SSSL 7 SSLS 56 SSLL 39 SLSS 7 SLLS 79 SLLL 55 SLSLSSLSSLSLSL 1134 (shortest SL-string giving length >= 1000) SLLLLLSLLLSSSSSSLLSL 1706 Given any finite squarefree sequence of 0's, 1's, and 2's, duplicating the last symbol would give a square, so there are at most 2 symbols that can be appended to preserve squarefreeness. Each of these is either the smallest or the largest symbol that can be added, so every Thue sequence on {0,1,2} can be obtained by the algorithm above, for some infinite SL-string. As a consequence, the lengths that we can get from periodic sequences are unbounded. That argument doesn't work if there are more than 3 symbols, and at least some Thue sequences on 4 symbols can't be obtained from an infinite SL-string. In fact we don't know if there's even one Thue sequences that can be obtained that way. When we experimented with more than 3 symbols, we found that most SL-strings still produce finite strings. But some short strings ran for a long time before stopping; for example SSLLL on 6 symbols stops after 2353749 steps. Then we tried SSSSSSL on 4 symbols. This runs for at least 30 million steps, which took my program 3 days. For such a long string, checking to see if a particular symbol can be added is quite time-consuming. If the program only stores the string so far, then it has to check about n/2 possible squares when the length is n. We can speed this up by having the program keep track of additional information. My program also records, for each n, the largest m<n (if any) for which the substring of length 20 ending at position m is identical to the one ending at position n. This greatly reduces the number of possible squares that need to be checked. (I have no theoretical reason for using length 20 here; I just experimented with different values and 20 worked well for the cases I tried.) I'm sure there must be a better algorithm to speed things up even more, but I have no idea what would work best. So if anyone out there gets interested enough to do some thinking and/or computing, here are some questions we'd like to have answered: Is there some periodic SL-string that produces an infinite squarefree string on 3 symbols? If not (as we suspect), then how long a squarefree string can you get from an SL-string of period n? Is there some periodic SL-string that produces an infinite squarefree string on 4 or more symbols? Here the empirical evidence doesn't justify a conjecture about the answer. Does SSSSSSL on 4 symbols run forever? Sherman offers $50 for this, and I'll add $10 more. (If your answer is that it stops after a certain number of steps, based on running a computer program, we'll want a copy of the program and verification that it gets the right answers for some known cases.) What's the most efficient algorithm to do these calculations? Dean Hickerson dean@math.ucdavis.edu _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun