A long cubefree word with a cubefree curling number transform

[Geoffrey Caveney]

Gijswijt introduced the concept of the "curling number" of a word or sequence in creating the sequence that bears his name (A090822). He also proposed the idea of applying the curling number analysis to other words and sequences, which is called the "curling number transform" of the other word or sequence. A few examples appearing in OEIS include A093914 (the transform of the Thue-Morse sequence), A093921 (the transform of the Kolakoski sequence), A094840 (the transform of the Linus sequence), and A094916 (the transform of the Fibonacci word). For an audience that is not familiar with Gijswijt's sequence or with the concept of a curling number, such a transform might be described as the pattern of terms that don't form squares and terms that form squares, cubes, etc.

As Gijswijt observed in his original paper (https://cs.uwaterloo.ca/journals/JIS/VOL10/Sloane/sloane55.html), any squarefree sequence has the trivial curling number transform 1111.... Cubefree sequences such as Thue-Morse and Kolakoski produce binary curling number transforms containing only 1's and 2's. However, the pattern-avoiding property of those original cubefree sequences does not carry over to their curling number transforms: Even if one disregards the initial a(1)=1 in A093914 and A093921, which is not itself a curling number of the original sequence properly speaking, these transforms contain long repeated blocks of 2's in particular. Thus, these curling number transforms are not pattern-avoiding cubefree sequences themselves.

I was curious to investigate the possibility of a cubefree word or sequence with the property that its curling number transform is also cubefree itself. Such a sequence might be described as a cubefree word with a cubefree pattern of terms that form squares and terms that do not. I am not aware of any such examples appearing in OEIS to date.

It turns out that a brute force examination shows that there does not exist any binary cubefree word of length >= 18 that has a cubefree curling number transform. The binary cubefree words that require 18 terms to produce a cube in their transforms begin 00110100110010110, and now either 0 or 1 as the 18th term creates the cube pattern ...212212212 in the curling number transform.

However, it appears quite possible to produce an indefinitely long ternary cubefree word that has a cubefree curling number transform. I do not yet have a proof of the existence of an infinite cubefree ternary word with a cubefree transform, but I consider it very likely to exist, based on my work in constructing a very long word with this property.

My aim is to find the lexicographically earliest infinite cubefree ternary word with a cubefree curling number transform. The best example I can find begins

00100120010022011010010020010012001002201101001012001001200100220110100102...

and its curling number transform begins

(1)12112211211212112112212211211221121121211211221221121122112112121121122121...

It is interesting that the first 22 (or 23) terms of the latter sequence match a block of terms that occurs multiple times near the beginning of A282317, the lexicographically earliest infinite cubefree binary word, e.g. at terms (a(8))a(9)...a(30). (Naturally A282317 contains 0's and 1's rather than 1's and 2's.) But the rest of the sequences do not match.

I have extended the word and its transform out to 1041 terms. Text files of the long cubefree ternary word and its cubefree curling number transform are attached for those who are interested in examining these sequences. The word is mainly constructed in blocks of 25 or 24 terms each, with small variations at the ends of blocks to avoid repetitions that would produce a cube in the curling number transform. Occasional short blocks of 8 or 7 terms are inserted for the same purpose at a(297)...a(304), a(678)...a(685), and a(763)...a(769). 

There is an exceptional block of 27 terms at a(355)...a(381): Term a(370) must be 2, because here the term 1 as in similar blocks would lead to a long cube in the curling number transform from a(301)...a(375). The first 381 terms are repeated exactly for the next 381 terms, followed by a short block of 7 terms, after which the order of block endings must be changed slightly, for example at a(842).

Question 1: Is my word, as intended, indeed the lexicographically earliest cubefree ternary word with a cubefree curling number transform, or can an improvement be found that I have overlooked?

Question 2: Can the existence of an infinite cubefree ternary word with a cubefree curling number transform be proven?

Geoffrey Caveney

[Neil Sloane]

Just for the record, I believe I invented the terms "curling number" and "curling number transform" when I was analyzing the sequence that Dion Gijswijt submitted to the OEIS back in 2004. When he submitted it, 4 was the largest known term.

Fokko van der Bult and I independently - and on the same weekend! - showed that 5 does appear, but not until roughly 10^(10^23) terms.

 

Best regards

Neil 

Neil J. A. Sloane, Chairman, OEIS Foundation.

Also Visiting Scientist, Math. Dept., Rutgers University, 

Email: njas...@gmail.com

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFhKorXobyHG%3De0C8oZEm1P6khscj_1P_Vi2CU%3DtfMOpoCxnYA%40mail.gmail.com.

[Jeffrey Shallit]

I can answer one of your two questions:  yes, there is an infinite cubefree sequence over {0,1,2} such that its curling number sequence is also cubefree.

Here is how to do it:  Take the Thue-Morse sequence 01101001.... and apply the morphism that maps 0 to 011010 and 1 to 121122.  The resulting word

U = 01101012112212112201101012112201101001101012112212 ...

has the property you want; its curling number sequence is

C = 11211221121211221211211221121211211221211221121211 ...

and is cubefree.

The construction itself was found by ChatGPT 5.6 Pro. Once you know it, you can easily check its correctness with Walnut as follows:

morphism m "0->011010 1->121122":

# define the morphism

image U m T:  

# apply it to the Thue-Morse word, defining U

eval cubef "~Ei,n n>=1 & At (t<2*n) => U[i+t]=U[i+n+t]":

# check that U is cubefree; it answers TRUE

def curl "Ei,c c>=1 & i+2*c=n+1 & At (t<c) => U[i+t]=U[i+t+c]":

# determine if the prefix of U of length n+1 (for n>=0) ends with a square

def nocurl "~Ei,c c>=1 & i+2*c=n+1 & At (t<c) => U[i+t]=U[i+t+c]":

# determine if the prefix of U of length n+1 does NOT end with a square

combine C curl=2 nocurl=1:

# make a DFAO to compute the sequence C

eval tmp "~Ei,n n>=1 & At (t<2*n) => C[i+t]=C[i+t+n]":

# check that there are no cubes in C, it answers TRUE

Hope this is useful to you.

Jeffrey Shallit

On Thu, Aug 6, 2026 at 5:45 PM Geoffrey Caveney <geoffre...@gmail.com> wrote:

[Geoffrey Caveney]

Thank you Jeffrey! This is very interesting, and the construction by means of a morphism mapped from the Thue-Morse sequence is elegant.

I observe that the curling number sequences in both of our examples appear to have a tendency toward a greater density of 1's than 2's: My long sequence has 587 1's and 454 2's (1's have density ~0.564) and the beginning of Shallit's infinite sequence has 29 1's and 21 2's (1's have density 0.58).

The most well-known cubefree binary words, on the other hand, are the Thue-Morse sequence with equal density of 0's and 1's, and the Kolakoski sequence with apparent equal density of 1's and 2's (although this has not been proven).

The lexicographically earliest infinite cubefree binary word, A282317, naturally has a tendency toward a greater density of 0's than 1's by design; its first 10,001 terms contain 5,921 0's and 4,080 1's (0's have density ~0.592). Perhaps not coincidentally, I also find it not at all difficult to construct a long cubefree ternary word that has a curling number sequence matching A282317.

All of this raises a new question: What is the minimal possible density of 1's in a cubefree curling number sequence of a long cubefree ternary word? Is it possible to construct a cubefree word with a cubefree curling number sequence with an equal density of 1's and 2's? I conjecture that the latter is not possible.

On a smaller scale, what is the longest possible string within such a cubefree curling number sequence containing an equal density of 1's and 2's? In Shallit's example, the string a(6)...a(25) of length 20 has such equal density: 22112121122121121122. In my example, the string a(20)...a(49) of length 30 has equal density: 221221121122112112121121122122. Much later in my example, the string a(730)...a(775) of length 46 has equal density of 1's and 2's: 2212211211221121121211221122121122122121121122. The underlined term a(763) is exceptional: this curling number is 2 because the ternary word has the long string a(2)...a(382) repeated exactly at a(383)...a(763). Without this exceptional term, the equal density string would still have length 30.

Geoffrey Caveney

[DONG HAOXUAN]

Hi Geoffrey,

I had a go at your question, and I think I now have a surprisingly short explicit infinite construction, together with a rigorous proof.

Let (T) be the Thue–Morse word and define
[
H(0)=011010,\qquad H(1)=121122.
]
If (W=H(T)) and the first symbol of (W) is deleted to give (V), then I can prove that both (V) and its curling-number transform are cubefree. The result also survives the alternative convention where an initial 1 is prepended to the transform.

I have independently checked the finite data as well, and found a few other results around the binary case and the lexicographic question. I’m still doing some deeper checking and trying to see how far the result can be strengthened before writing everything up formally.

Since this comes directly from the problem you raised, I wanted to ask whether you would be interested in collaborating on a paper about it. I’d be very happy to send you the full proof, code, and computational results once I’ve finished tidying them up.

Best,
Jason

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAAOnSgRU4VvwtjeSJyhDkYkA05Wb3jwtAFnZS_N-ZxuzYK7A6Q%40mail.gmail.com.

[jpallouche.math]

Hi

This is precisely Shallit's construction given yesterday.
(Btw if I m not mistaken, the sequence obtained without 
deleting the first symobl can be obtained directly as a
fixed point of an 8-uniform morphism.)

best
jp

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CABbU%3D%2BXESYNjAkkLVfsW_YdYD-HsMNMgurdo2%2BJQ_d6dOya2Og%40mail.gmail.com.

[DONG HAOXUAN]

Hi Jean-Paul,

Thank you for pointing this out. I hadn’t yet caught up with Jeffrey Shallit’s message when I sent mine, so I had not realised that the morphism I found was exactly the same construction. I’m glad you flagged it, and of course I won’t present that construction as an independent new result.

What I have mentioned on SeqFan so far is actually only a part of what I have found while investigating the problem — probably less than half of the material at this stage. Some of the later results go in rather different directions, and I’m currently checking them carefully, including their relation to existing work, before saying too much publicly.

Thank you also for the observation about the 8-uniform morphism. I’ll take a closer look at that.

Best wishes,

Jason Dong

To view this discussion visit https://groups.google.com/d/msgid/seqfan/cbcb9f44-4c45-4cf7-822e-180ae351036e%40gmail.com.

[Geoffrey Caveney]

Thank you Jason. Your work sounds very interesting. I will be happy to discuss it with you further off-list.

Geoffrey

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CABbU%3D%2BVvEyDw6O8wG0Tg7Zwe8sOAhpmaD8byohmxjyMU0N5Q7Q%40mail.gmail.com.

[Jeffrey Shallit]

Here's something else.  The construction is from ChatGPT, the proof is from Walnut.

ChatGPT produced the following example of a cubefree ternary sequence whose curling sequence is overlap-free.

Start with TM t = 01101001...

Slide a window of size 2 over t, one step at a time, and evaluate the adjacent pairs of symbols as a 2-bit base
2 number:

01 = 1
11 = 3
10 = 2
01 = 1
10 = 2
00 = 0
... and so forth.  This gives the sequence 132120...

Now apply the morphism

0->0020201001002022 
1->0010012001202010 
2->0100202202122121 
3->0100202200202010

to this sequence, getting

001001200120201001002022002020100100202202122121...
with curling sequence

121122...

which is (t(3) t(4) t(5)....) + 1 and hence overlap-free.

Here is the proof in Walnut:

def p00 "T[n]=@0 & T[n+1]=@0":
def p01 "T[n]=@0 & T[n+1]=@1":
def p10 "T[n]=@1 & T[n+1]=@0":
def p11 "T[n]=@1 & T[n+1]=@1":

combine P p00=0 p01=1 p10=2 p11=3:

morphism h "0->0020201001002022 1->0010012001202010 2->0100202202122121 
3->0100202200202010":

image B h P:

eval cubef "~Ei,n n>=1 & At (t<2*n) => B[i+t]=B[i+n+t]":

def curl "Ei,c c>=1 & i+2*c=n+1 & At (t<c) => B[i+t]=B[i+t+c]":
def nocurl "~$curl(n)":
combine D curl=2 nocurl=1:

eval check "An (T[n+3]=@0 <=> D[n]=@1)":

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFhKorVKahwRpDQVYH0RbpuhuXyYOuCE-k0VrFXDbfcJTgTghQ%40mail.gmail.com.

[Geoffrey Caveney]

Amazing! In essence, you have repeated every term of the Thue-Morse sequence except the first term ( 011110011000011... ), then applied a 16-digit morphism on each 2-digit pair of the resulting sequence, such that applying the curling number transform to the morphism reproduces the Thue-Morse sequence itself (with the first three terms omitted). This is an astounding and elegant construction.

I am surprised that you found an overlap-free curling sequence, which is binary, rather than an overlap-free ternary word.

The natural next question is whether there exists an infinite overlap-free ternary word, which has a cubefree curling sequence.