CS Paper Radar

Lengths and Counting of Palindromic Prefixes of Standard Sturmian Words

Jasem Hamoud

cs.FL math.CO ·submitted 2026-11-15 19:42 UTC · v1

Abstract

Every standard Sturmian word $c_\mathbf{d}$ is determined by a directive sequence $\mathbf{d}=(d_i)_{i\ge 1}$ of positive integers, and its palindromic prefixes are obtained by iterated palindromic closure. We describe the lengths of these prefixes by the numbers $j\,\ell_{i-1}+\ell_{i-2}-2$, where $\ell_n$ is the length of the $n$-th standard word and $1\le j\le d_i$, and we show that each nonzero length is attained by exactly one pair $(i,j)\neq(1,1)$. For a purely periodic directive sequence of period $k$ we then prove that the number $π_\mathbf{d}(N)$ of nonempty palindromic prefixes of length at most $N$ satisfies \[ π_\mathbf{d}(N)\sim\frac{d_1+\cdots+d_k}{\logλ_\mathbf{d}}\,\log N, \] where $λ_\mathbf{d}$ is the largest eigenvalue of the matrix $M(d_1)\cdots M(d_k)$. For the Fibonacci word this gives $π_\mathbf{d}(N)\sim\log N/\log\varphi$, where $\varphi=(1+\sqrt5)/2$.

Closest papers

Nearest neighbours by meaning across the whole index.

The Parameterized Periodicity Lemma

cs.DS cs.DM ·2026-08-22 ·Rikuya Hamai, Yuto Nakashima, Shunsuke Inenaga
published similarity 0.63
Abstract · Accepted for SPIRE 2026

Fine and Wilf [Proc. Amer. Math. Soc. 1965] showed that any string of length at least $p+q-d$ with periods $p$ and $q$ also has period $d=\gcd(p,q)$. For parameterized strings, Apostolico and Giancarlo [Discrete Appl. Math. 2008] proved an analogue with length bound $p+q$, assuming that the two induced bijections commute. Ideguchi et al. [SPIRE 2023] removed this assumption and gave the bound $p+q+\min(p,q)(σ-1)$, where $σ$ is the number of distinct letters. This was later improved by Hamai et al. [SPIRE 2024] to $p+q+\min(p,q)(σ-2)$, which was used to bound the number of non-equivalent parameterized squares. In this paper, we establish the optimal Fine--Wilf type bound for parameterized strings. Namely, if a string $s$ containing $σ$ distinct letters has parameterized periods $p$ and $q$ and satisfies $|s| \ge p+q+(σ-3)d+1$, where $d=\gcd(p,q)$, then $d$ is also a parameterized period of $s$. We also give matching lower-bound instances, proving that our bound is optimal for any $σ\geq 2$.

0.31

Quadratic reset bounds for finite maximal prefix codes

cs.FL ·2026-11-03 ·Samrath Singh Chadha
theory similarity 0.56
Abstract

Let $C$ be a finite maximal prefix code of maximum codeword length $k\ge2$. We prove that, whenever the literal decoder of $C$ is synchronizing, it has a reset word of length at most $(k-1)(4k-5)$. The bound is independent of the alphabet and the number of decoder states. Its main ingredient is a short-detection theorem: a linear observation of the decoder, with terminal weight constant on states of depth $k-1$, is either identically zero or nonzero on a word of length at most $2k-3$. The proof uses a first-return decomposition in noncommuting variables and cancellation of a highest-degree coefficient. For codes whose codeword lengths are $k-1$ and $k$, we prove the sharper bound $2(k-1)^2-1$ and characterize equality. The binary code with the single short word $a^{k-1}$ attains this bound for every $k\ge2$; an age representation and a potential on circular arcs give the matching lower bound. Both upper bounds yield polynomial-time constructions in the explicit code size. The mathematical results and the algorithms are formalized in Lean, with polynomial work bounds in a specified binary cost model.

0.12

Shuffle squares in smooth binary words and the Kolakoski sequence

cs.FL math.CO ·2026-10-01 ·Kory Kilpatrick
similarity 0.56
Abstract · Includes an exact finite certificate and standalone Python verifier. Research, computation, and writing performed by GPT-5.6 Sol and GPT-6-A…

A binary word is a shuffle square if its positions can be partitioned into two identical subsequences. A finite word over $\{1,2\}$ is smooth if repeated finite run-length differentiation remains binary until the empty word is reached. This paper proves that every smooth binary word in which both letters have even multiplicity is a shuffle square once its length is at least $18$. There are exactly $34$ exceptions, all of length at most $16$. The infinite part of the proof is a parity-return atom induction: a smooth even-Parikh word factors uniquely into smooth parity atoms, and every such atom has length at most $8$. A finite, independently checkable certificate handles lengths $18$ through $40$. As a consequence, a nonempty prefix of the classical Kolakoski sequence is a shuffle square if and only if both symbols occur an even number of times and its length is not $4$ or $8$. There are infinitely many such prefixes. In fact, the entire infinite Kolakoski sequence can be partitioned into two identical infinite subsequences with monochromatic blocks of uniformly bounded length.

0.54

The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture

cs.IT math.CO ·2026-10-22 ·Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
theory similarity 0.53
Abstract

For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.

0.20

Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters

cs.IT math.CO ·2026-09-19 ·Arman Nilforoushan, Farzad Parvaresh
theory similarity 0.53
Abstract · Submitted to IEEE Transactions on Information Theory

Data stored in synthetic DNA is retrieved by shotgun sequencing, which returns short subsequences rather than the stored word itself. A natural abstraction of this readout is the $k$-deck of a word: the vector recording how often each word of length $k$ occurs as a subsequence. Two stored words are distinguishable from their readouts exactly when their $k$-decks differ, so the number $D_{q,k}(n)$ of distinct $k$-decks of words of length $n$ over an alphabet of size $q$ measures what a length-$k$ readout retains. We analyse the degrees of freedom remaining in a $k$-deck once all shorter decks are fixed. Within each class of words having prescribed letter multiplicities, the length-$k$ entries are confined to an affine subspace whose dimension is exactly the number of Lyndon words with the same multiplicities, which we give in closed form as a Möbius sum. Writing $L_q(j)$ for the number of Lyndon words of length $j$ over an alphabet of size $q$, we deduce the improved upper bound \[ D_{q,k}(n)=O\!\left(n^{E_q(k)}\right),\qquad E_q(k)=\sum_{j=1}^{k}j\,L_q(j)-1 . \] In the case of a binary alphabet this bound satisfies $D_{2,k}(n)=O\!\left(n^{4\cdot 2^{k-1}}\right)$. We then prove matching lower bounds in the first two nontrivial cases: $D_{q,2}(n)=Θ\!\left(n^{q^2-1}\right)$ for every alphabet size $q$, and $D_{2,3}(n)=Θ(n^{9})$ for the binary alphabet. The latter confirms, for $q=2$ and $k=3$, our conjecture that the upper bound has the correct degree for every $q$ and $k$.

0.28

Exact Net-Occurrence Counts in Purely Morphic Regular Epistandard Words

cs.FL ·2026-10-03 ·Simone Faro, Arianna Pavone
theory similarity 0.53
Abstract

Finite Fibonacci words have recently been shown to contain exactly three net occurrences---occurrences of repeated factors whose one-letter left and right extensions are unique. This unexpectedly small constant raises a natural question: is it peculiar to the Fibonacci recurrence, or part of a broader morphic phenomenon? We study a family over the alphabet $\{0,1,\ldots,d-1\}$ determined by positive integers $e_0,\ldots,e_{d-1}$. For each letter $a$, let $L_a$ be the morphism that fixes $a$ and maps every other letter $b$ to $ab$; we consider the finite approximants $S_m=μ^m(0)$ generated by $μ=L_0^{e_0}\cdots L_{d-1}^{e_{d-1}}$. These words are the period-aligned finite approximants of the purely morphic regular epistandard family considered here. We prove a sharp dichotomy: for every $m\ge2$, $S_m$ has exactly three net occurrences when $e_{d-1}=1$, and exactly two when $e_{d-1}\ge2$; the initial approximant is also completely classified. The proof combines palindromic prefixes, return-word factorizations, and overlapping net-occurrence covers. As a consequence, when all exponents are equal to one---the standard $d$-bonacci case---every noninitial period-aligned finite approximant has exactly three net occurrences, placing the Fibonacci phenomenon in a wider epistandard framework.

0.31

Coding for Multiple Reverse-Complement and Palindromic Duplications

cs.IT ·2026-09-01 ·Aryeh Lev Zabokritskiy
theory similarity 0.53
Abstract · 33 pages

Reverse-complement (RC) and palindromic (PAL) duplications insert a reversed copy of a length-$k$ block immediately after the block; an RC duplication also applies a fixed involutive complement to the inserted symbols. We study $q$-ary codes correcting $t$ such operations applied in sequence, where later operations may copy inserted symbols. For fixed $q\geq2$ and $k,t\geq1$, we prove that every length-$n$ code $C$ for either channel has redundancy $n-\log_q|C|\geq t\log_q n-O_{q,k,t}(1)$; for fixed $q,k$ and $1\leq t=t(n)=o(n)$ the lower bound is $t\log_q(n/t)-O_{q,k}(t)$. For fixed $k$, known codes for one length-$k$ insertion burst attain redundancy $\log_q n+O_{q,k}(1)$ for a single duplication of either type. For every even $k$ and any involutive complement, we show that the two channels are equivalent for every number of errors: the bijection complementing every other coordinate turns each RC duplication into a PAL duplication. This bijection therefore converts any $t$-error-correcting RC code into a PAL code of the same size, and conversely, with linear-time transfer of encoders and decoders. For every even $k$, we also determine the maximum number of descendants of one word under exactly two errors; by the bijection, it is the same for both channels. For fixed even $k$, a direct count using this maximum proves the existence of two-error-correcting PAL and RC codes with redundancy at most $4\log_q n+O_{q,k}(1)$. A known existence bound for two deletion bursts transfers to insertions with the same leading term as ours and a larger additive constant. For two errors, the converse gives $2\log_q n-O_{q,k}(1)$, a factor of two below these existence bounds.

0.31

Substring Complexity in BWT-Runs Bounded Space

cs.DS ·2026-10-29 ·Johannes Fischer
similarity 0.52
Abstract

Given a string $T[1..n]$, its substring complexity is defined as $δ=\max_k d_k/k$, where $d_k$ is the number of its distinct substrings of length $k$ in $T$. We show how to compute it in $O(n+r\log r)$ time, using only $O(r)$ words of space, where $r$ denotes the number of runs in the Burrows-Wheeler transform.

0.30