New orientable sequences
Chris J. Mitchell, Peter R. Wild · 2025
Read New orientable sequences by Chris J. Mitchell, Peter R. Wild (2025) 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-2507-02526.txt.
Introduction
Chris Mitchell and Peter Wild wrote a 2025 mathematics paper on sequences that can be read in both directions with no clash. A sequence of this kind has one rule: no short run in it, of a set length, may appear twice in one period, in one direction or the reverse. They were introduced in the early nineteen nineties for position-sensing work. Their best length was a live gap: the best built and the proved cap sat far apart.
The pair first tightens the cap on how long such a sequence can run. They then give a new construction method, from parts of a known graph with special properties, in two forms. The constructions meet the new cap for the short lengths, and for length four with an odd symbol count. For lengths up to eight, some constructions beat all previous ones.
Catalog record
| CREATOR | Chris J. Mitchell, Peter R. Wild |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-02526
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New orientable sequences Chris J. Mitchell, Peter R. Wild Abstract Orientable sequences of order n n are infinite periodic sequences with symbols drawn from a finite alphabet of size k k with the property that any particular subsequence of length n n occurs at most once in a period in either direction . They were introduced in the early 1990s in the context of possible applications in position sensing. Bounds on the period of such sequences and a range of methods of construction have been devised, although apart from very small cases a significant gap remains between the largest known period for such a sequence and the best known upper bound. In this paper we first give improved upper bounds on the period of such sequences. We then give a new general method of construction for orientable sequences involving subgraphs of the de Bruijn graph with special properties, and describe two different approaches for generating such subgraphs. This enables us to construct orientable sequences with periods meeting the improved upper bounds when n n is 2 or 3, as well as n = 4 n=4 and k k odd. For 4 ≤ n ≤ 8 4\leq n\leq 8 , in some cases the sequences produced by the methods described have periods larger than for any previously known sequences. 1 Introduction 1.1 Orientable sequences Orientable sequences were introduced in the early 1990s [ 3 , 4 , 5 ] in the context of possible applications in position sensing. An orientable sequence of order n is an infinite periodic sequence with symbols drawn from a finite alphabet — typically \mathbb{Z}_{k} for some k — with the property that any particular subsequence of length n , referred to throughout as an n -tuple, occurs at most once in a period in either direction . That is, if anyone reading the sequence observes n consecutive symbols, they can deduce both the direction in which they are reading and their position within one period of the sequence. Gabrić and Sawada [ 8 ] provide an interesting discussion of further possible applications as well as their relationship to strings relevant to DNA computing. The early work referred to above focussed on the binary case, i.e. where k=2 ; Dai et al. [ 5 ] provided both an upper bound on the period for this case and a method of construction yielding sequences with asymptotically optimal periods. More recently, Mitchell and Wild [ 11 ] showed how the Lempel homomorphism [ 10 ] could be applied to recursively generate binary orientable sequences with periods a large fraction of the optimal value. In 2024, Gabrić and Sawada [ 6 , 7 ] described a highly efficient method of generating binary orientable sequences with the largest known periods. In 2024, Alhakim et al. [ 2 ] studied the general alphabet case, i.e. where k>2 . They gave an upper bound on the period of orientable sequences for all n and k , and also described a range of methods of construction using the Alhakim and Akinwande generalisation of the Lempel homomorphism to arbitrary finite alphabets [ 1 ] . Since then a range of construction methods have been proposed [ 8 , 12 , 13 ] ; of particular interest is the method of Gabrić and Sawada [ 8 ] , who showed how to construct sequences with asymptotically optimal period for any n and k>2 using a cycle-joining approach. In this paper we first give new upper bounds on the period of an orientable sequence, which improve on the previous bounds for n\geq 3 . We also describe a novel general approach to the construction of orientable sequences for any k and n . This approach involves showing, using graph-theoretic arguments, that a subset of n -tuples with special properties can always be ‘joined’ to create an orientable sequence. Two methods for generating sets of n -tuples with the appropriate set of properties are described. The orientable sequences obtained have optimal periods for n=2 , n=3 and n=4 when k is odd. For 4\leq n\leq 8 , for some values of k the sequences generated have longer period than any previously known sequences, although sequences generated by the method of Gabrić and Sawada [ 8 ] have the largest known period for larger values of n . 1.2 Basic definitions In this paper we consider periodic sequences (s_{i}) with elements from \mathbb{Z}_{k} for some k , which we refer to as k -ary. For a sequence S=(s_{i}) and n\geq 1 we write \mathbf{s}_{n}(i)=(s_{i},s_{i+1},\ldots,s_{i+n-1}) , i.e. a string of n consecutive symbols occurring in the sequence at positions i,i+1,\ldots,i+n-1 . We refer to such strings as n -tuples. Since we are interested in tuples occurring either forwards or backwards in a sequence, we also introduce the notion of a reversed tuple, so that if \mathbf{u}=(u_{0},u_{1},\ldots,u_{n-1}) is a k -ary n -tuple then \mathbf{u}^{R}=(u_{n-1},u_{n-2},\ldots,u_{0}) is its reverse . We are also interested in negating all the elements of a tuple, and hence if \mathbf{u}=(u_{0},u_{1},\ldots,u_{n-1}) is a k -ary n -tuple, we write -\mathbf{u} for (-u_{0},-u_{1},\ldots,-u_{n-1}) . Definition 1.1 ( [ 2 ] ) . A k -ary n -window sequence S=(s_{i}) is a periodic sequence of elements from \mathbb{Z}_{k} ( k>1 , n>1 ) with the property that no n -tuple appears more than once in a period of the sequence, i.e. with the property that if \mathbf{s}_{n}(i)=\mathbf{s}_{n}(j) for some i,j , then i\equiv j\pmod{m} where m is the period of the sequence. A k -ary de Bruijn sequence of order n is then simply an n -window sequence in which every k -ary n -tuple appears once in a period, i.e. an n -window sequence of maximal period. Following Alhakim et al. [ 2 ] we also introduce the de Bruijn digraph. For positive integers n and k greater than one, let \mathbb{Z}_{k}^{n} be the set of all k^{n} vectors of length n with entries from the group \mathbb{Z}_{k} of residues modulo k . The order n de Bruijn digraph, B_{k}(n) , is a directed graph with \mathbb{Z}^{n}_{k} as its vertex set in which, for any two vectors \textbf{x}=(x_{0},x_{1},\ldots,x_{n-1}) and \textbf{y}=(y_{0},y_{1},\ldots,y_{n-1}) , the pair (\textbf{x},\textbf{y}) is an edge if and only if y_{i}=x_{i+1} for every i ( 0\leq i<n-1 ). We label such an edge with the (n+1) -tuple (x_{0},x_{1},\ldots,x_{n-1},y_{n-1}) . Note that we have defined two ways of specifying an edge in B_{k}(n) , namely as either a pair of vertices (\textbf{a},\textbf{b}) , where \textbf{a},\textbf{b} are k -ary n -tuples, or as a single k -ary (n+1) -tuple x . Note that, in this case, the (n+1) -tuple \textbf{x}^{R} denotes the same edge as (\textbf{b}^{R},\textbf{a}^{R}) . It is straightforward to verify that there is a correspondence between a k -ary de Bruijn sequence of order n and a directed Eulerian circuit in B_{k}(n-1) , in which consecutive edges in the circuit correspond to consecutive n -tuples in the sequence. Definition 1.2 ( [ 2 ] ) . A k -ary n -window sequence S=(s_{i}) is said to be an orientable sequence of order n , an \mathcal{OS}_{k}(n) , if \mathbf{s}_{n}(i)\neq\mathbf{s}_{n}(j)^{R} , for any i,j . 1.3 This paper The remainder of this paper is structured as follows. We