An alternating colouring function on strings

Jonathan Garbe Lund University · 2024

Read An alternating colouring function on strings by Jonathan Garbe Lund University (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00562.txt.

Description

A 2024 arXiv research paper by Jonathan Garbe Lund University. An alternating colouring function is defined on strings over the alphabet \crl ​ \bm ​ 0 , \bm ​ 1 \crl{\bm 0,\bm 1} . It divides the strings in colourable and non-colourable ones. The points in the subshift of finite type defined by forbidding all non-colourable strings of a certain length alternate between states of one colour and states of the other colour. In other words, the points in the 2 nd power shifts all have the same colour.

Catalog record

CREATORJonathan Garbe Lund University
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-00562

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An alternating colouring function on strings Jonathan Garbe Lund University Abstract An alternating colouring function is defined on strings over the alphabet \crl ​ \bm ​ 0 , \bm ​ 1 \crl{\bm 0,\bm 1} . It divides the strings in colourable and non-colourable ones. The points in the subshift of finite type defined by forbidding all non-colourable strings of a certain length alternate between states of one colour and states of the other colour. In other words, the points in the 2 nd power shifts all have the same colour. The number K n K_{n} of non-colourable strings of length n ≥ 2 n\geq 2 is shown to be 2 ⋅ \p ​ J n − 2 + 1 2\cdot\p{J_{n-2}+1} where J J is the sequence of Jacobsthal numbers. The number of sources and sinks in the de Bruijn graph of dimension n ≥ 3 n\geq 3 with non-colourable edges removed is shown each to be K n − 4 K_{n}-4 . \SmartPairedDelimiter hopen[) \defineshorthand ” \babelhyphen nobreak \useshorthands ” † † titlehead: \addsec Preface This paper is an extract from my master thesis ( Garbe 2020 ) that I wrote during the spring semester 2020. As many will remember, that was when the covid-19 pandemic hit the world. I was lucky that all I had left to complete my major was the thesis while fellow students struggled with improvised online teaching as even Swedish universities closed their doors to mitigate the spread of the virus. I started with a research question in the area of dynamical systems that I tried to tackle by looking at de Bruijn sequences. (They are named after Nicolaas Govert de Bruijn who de Bruijn 1946 published his famous result regarding their number.) After a time however I noticed some symmetries of de Bruijn graphs that I tried to formalise. In particular, I noticed that by deleting palindromes I could categorise the remaining edges such that in any path an edge of one category would follow an edge of the other. In the following weeks I was able to formalise that notion by defining the function \psi . Theorem \zarabicsection.\zarabicthrm shows it actually has the property I was looking for. It can therefore be seen as the most important result, but it is not surprising as \psi was made to fulfil that property. However, observation \zarabicsection.\zarabicthrm came as a disappointment: The set of strings that \psi does not assign a colour to is identical with the set of palindromes only up to a string length of 5 and theorem \zarabicsection.\zarabicthrm shows that the definition of \psi cannot easily be improved. Corollary \zarabicsection.\zarabicthrm instead shows that in the limit \frac{1}{6} of all strings are not colourable. Surprisingly however, the number of non-colourable strings of certain length turns out to be an integer sequence so far unknown even to the On-Line Encyclopedia of Integer Sequences ( OEIS Community 2024 ) that had been a great help in finding that sequence. While for strings of even length the definition of \psi is rather straight-forward, for strings of odd length the definition first requires two other functions \phi and \xi . Those two functions feature some remarkable relations. Theorem \zarabicsection.\zarabicthrm , which establishes a relation between \phi and \xi being equal to zero, to me is the most surprising result of my master thesis. For personal reasons some time has passed between my master thesis and this paper. I beg pardon for the delay. I am grateful for my supervisor Jörg Schmeling for having introduced me into the subject and especially for my examiner Tomas Persson who has put more effort in supporting the production of my thesis and this paper than I would have dared to ask for. Cologne, Autumn 2024 Jonathan Garbe \zarabic section Notation Notation . Define † † margin: – l , r , m , R , C , T , CT l,r:\mathcal{A}_{2}^{\geq 1}\to\mathcal{A}_{2}^{*},m:\mathcal{A}_{2}^{\geq 2}\to\mathcal{A}_{2}^{*},R,C:\mathcal{A}_{2}^{*}\to\mathcal{A}_{2}^{*},T,CT:\N\to\mathcal{A}_{2}^{*} by \displaystyle l\p w \displaystyle=w_{[0,\#w-1)} \displaystyle r\p w \displaystyle=w_{[1,\#w)} \displaystyle m \displaystyle=l\circ r \displaystyle R\p{w_{0}\dots w_{\#w-1}} \displaystyle=w_{\#w-1}\dots w_{0} \displaystyle C\p{w_{0}\dots w_{\#w-1}} \displaystyle=C\p{w_{0}}\dots C\p{w_{\#w-1}}\text{, where }C\p\bm 0=\bm 1\land C\p\bm 1=\bm 0 \displaystyle T^{n} \displaystyle=\begin{cases}\upepsilon&\text{if }n=0\\ T^{n-1}\bm 0&\text{if }n\text{ odd}\\ T^{n-1}\bm 1&\text{if }n\text{ even}>0\end{cases} \displaystyle CT^{n} \displaystyle=C\p{T^{n}}. Remark . l\p w,r\p w are prefix and suffix with length \#w-1 of w . m\p w is the proper infix of length \#w-2 . R\p w is the reverse of w (meaning that w is a palindrome if and only if R\p w=w ) while C\p w is its complement. T^{n},CT^{n} are the strings of length n starting with \bm 0,\bm 1 respectively and alternating between \bm 0 and \bm 1 . Example . \displaystyle l\p{\bm{0010110}} \displaystyle=\bm{001011} \displaystyle r\p{\bm{0010110}} \displaystyle=\bm{010110} \displaystyle m\p{\bm{0010110}} \displaystyle=\bm{01011} \displaystyle R\p{\bm{0010110}} \displaystyle=\bm{0110100} \displaystyle C\p{\bm{0010110}} \displaystyle=\bm{1101001} \displaystyle T^{7} \displaystyle=\bm{0101010} \displaystyle CT^{7} \displaystyle=\bm{1010101} Observation \zarabic section. \zarabic thrm . \displaystyle l\circ r \displaystyle=r\circ l ( \zarabic section- \zarabic equation) \displaystyle l\circ m=m\circ l \displaystyle\land r\circ m=m\circ r ( \zarabic section- \zarabic equation) \displaystyle R\circ l=r\circ R \displaystyle\land R\circ r=l\circ R ( \zarabic section- \zarabic equation) \displaystyle R\circ m \displaystyle=m\circ R ( \zarabic section- \zarabic equation) \displaystyle C\circ l=l\circ C \displaystyle\land C\circ r=r\circ C ( \zarabic section- \zarabic equation) \displaystyle C\circ m \displaystyle=m\circ C ( \zarabic section- \zarabic equation) \displaystyle R\circ C \displaystyle=C\circ R ( \zarabic section- \zarabic equation) \zarabic section The function \xi Definition . † † margin: – the function \xi \xi :\mathcal{A}_{2}^{*}\to\crl{-1,0,1} is defined recursively by \displaystyle\xi\p w \displaystyle=\begin{cases}0&\text{if }w=\upepsilon\\ 1&\text{if }w\in\crl T^{\mathrm{even}\geq 0}\\ -1&\text{if }w\in\crl{CT}^{\mathrm{even}\geq 0}\\ \sgn\p{\xi\p{l\p w}+\xi\p{r\p w}}&\text{else}.\end{cases} w \upepsilon \bm 0 \bm 1 \bm{00} \bm{01} \bm{10} \bm{11} \xi\p w 0 0 0 0 1 -1 0 w \bm{000} \bm{001} \bm{010} \bm{011} \bm{100} \bm{101} \bm{110} \bm{111} \xi\p w 0 1 0 1 -1 0 -1 0 Table \zarabic table: \xi\p w for w\in\mathcal{A}_{2}^{\leq 3} Remark . The function \xi tells on which side of the vertical axis a vertex appears in a de Bruijn graph when drawn as is done in the examples given in this thesis. In figures \zarabicfigure to \zarabicfigure the background is coloured according to the value of \xi evaluated on the vertices. The vertices w for which \xi\p w=0 are found in the centre. The letter \xi was chosen with the word x-axis in mind. Figure \zarabic figure: The 1 -dimensional de Bruijn graph. The vertex \bm 0 and the edge \bm{10} are coloured red indicating that \phi\p\bm 0=\phi\p{\bm{10}}=-1 while the vertex \bm 1 and the edge \bm{01} are coloured blue indicating \phi\p\bm 1=\phi\p{\bm{01}}=1 . The edges \bm{00},\bm{11} and the background are coloured green because \xi\p\bm 0=\xi\p\bm 1=\phi\p{\bm{00}}=\phi\p{\bm{11}}=0 . Figure \zarabic figure: The 2 -dimensional de Bruijn graph. The vertices and edges are coloured red if \phi=-1 , green if \phi=0 and blue if \phi=1 . The background of the vertex \bm{10} is painted red because \xi\p{\bm{10}}=-1 . In the centre the background is green because \xi\p{\bm{00}}=\xi\p{\bm{11}}=0 and for the vertex \bm{01} it is blue because \xi\p{\bm{01}}=1 . Figure \zarabic figure: The 3 -dimensional de Bruijn graph. The vertices and edges are coloured red if \phi=-1 , green if \phi=0 and blue if \phi=1 . The background of the vertices is painted red where \xi=-1 , green where \xi=0 and blue where \xi=1 . Note that since the vertices have odd length, none

Read the complete text