CS Paper Radar

Spectrum of the refined Diophantine exponent

Quang-Khai Nguyen

cs.FL math.COmath.DSmath.NT ·submitted 2026-08-20 15:49 UTC · v2

Abstract

The refined Diophantine exponent, recently introduced by the author, is a quantity that measures the periodicity of an infinite word. In this article, we study this exponent from combinatorial and topological viewpoints. First, we show that, over a ternary alphabet, the spectrum of the refined Diophantine exponent is $[1,\infty]$. Second, we show that this exponent has topological properties similar to those of the set of Liouville numbers. Finally, we provide concrete examples with the Champernowne, Rudin--Shapiro, and Thue--Morse words, words coming from coding a rotation by intervals, and bracket words.

Comment
Reorganize the paper, fix the argument in Section 5, remove and add some questions

Closest papers

Nearest neighbours by meaning across the whole index.

Shuffle squares in smooth binary words and the Kolakoski sequence

cs.FL math.CO ·2026-10-01 ·Kory Kilpatrick
similarity 0.53
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 lattice of antichains of intervals: Dyck paths, level sets, and sweep dimension

cs.DM math.CO ·2026-10-30 ·Paolo Boldi, Sebastiano Vigna
theory similarity 0.52
Abstract

The Clarke-Cormack-Burkowski lattice $\mathcal{E}_n$ is the lattice of antichains of intervals of the chain $\{0,1,\dots,n-1\}$, the algebraic structure underlying minimal-interval semantics, a query semantics used in information retrieval. We give an explicit, elementary anti-isomorphism between $\mathcal{E}_n$ minus its top element and the Stanley lattice of Dyck words of semilength $n+1$ (an anti-isomorphism whose existence is implicit in work of Ferrari and Munarini), under which the rank of an antichain is $\binom{n+1}{2}$ minus the area of the associated Dyck word. Hence the rank generating function of $\mathcal{E}_n\setminus\{\top\}$ is the reverse of the Carlitz-Riordan $q$-Catalan polynomial. Using a local limit theorem for the area of random-walk excursions, we confirm unconditionally an asymptotic formula of Takács: the size $λ_n$ of the largest level set of $\mathcal{E}_n$ satisfies $λ_n\simκ\,4^{n+1}/(n+1)^3$, where $κ\approx1.0807$. Finally, for the antichains of intervals of an arbitrary finite poset $P$ we study the sweep dimension, the minimum number of linear orders needed to separate every interval from every element outside it. It equals the Dushnik-Miller dimension of the lattice of convex subsets of $P$, it is the least $k$ for which $P$ maps into $\mathbb{R}^k$ so that every interval is the preimage of an upper orthant, and it lies between $\max(2,w)$ and $2w$, where $w$ is the width of $P$, both bounds being tight. Antichains of intervals embed, preserving joins, into $k$-dimensional staircase regions.

0.13

Rotating-Memory Fibonacci Numbers and Periodic Tilings

cs.DM math.CO ·2026-09-11 ·Walid Abdelaidoum, El-Mehdi Mehiri, Hacène Belbachir
similarity 0.52
Abstract

We introduce and study the rotating-memory Fibonacci numbers, a periodic variable-order analogue of the Fibonacci sequence in which the number of preceding terms used in the recurrence changes cyclically with the index. Despite this varying memory, the resulting sequences exhibit a remarkably rigid structure. We derive closed forms, rational generating functions, arithmetic properties, and exact growth behavior, and show that the sequence decomposes naturally into geometric subsequences. We also develop combinatorial interpretations in terms of periodically constrained tilings, and restricted compositions, including bijective explanations for the multiplicative structure of the sequence. In addition, the first two nonclassical periods admit natural geometry-driven realizations: the period-2 sequence arises from monomer--dimer tilings of a triangular chain, while the period-3 sequence is related to tilings of a double hexagon strip by single and double hexagons. These connections provide geometric interpretations of the rotating recurrence in which the periodic behavior is induced by the underlying structures themselves, and suggest a broader problem of constructing analogous models for higher periods.

0.25

A generalized monoid of infinite words: asymptotic prefix-suffix quotients and algebraic structure

cs.FL math.GR ·2026-08-20 ·A. Alvarez Cruz, E. A. Alvarez Gutierrez
similarity 0.51
Abstract

A generalized monoid of words tilde{Sigma}* is constructed as the quotient of moderate nets of finite words by an asymptotic equivalence relation based on a bidirectional prefix-suffix metric. The main algebraic result is that this quotient is a monoid containing Sigma* faithfully, with a reversal involution, a natural divisibility preorder, failure of cancellation, and nontrivial idempotents. The construction is designed so that any functional depending only on a logarithmic prefix descends to the quotient, yielding a well-defined action of logarithmic-prefix functionals. Finite scalar values arise only after applying an additional renormalization functional, which depends on the chosen mould and window. With respect to the fixed truncation injection, the monoid strictly enlarges the classical set Sigma^{infty}: an explicit oscillating net is exhibited that has no limit in the Cantor space but defines a genuine element of tilde{Sigma}* not coming from a finite or right-infinite word under that injection.

0.50

Repetition Avoidance in Curling-Number Transforms

cs.DM math.COcs.FL ·2026-08-16 ·Geoffrey Caveney, Haoxuan, Dong, Jeffrey Shallit
similarity 0.51
Abstract

We study repetition avoidance in a word ${\bf w}$ and its curling-number transform $C({\bf w})$. For alphabets of sizes $2$, $3$, and $4$, we use Thue-Morse-based morphic constructions and exhaustive finite searches. A ternary word for which both ${\bf w}$ and $C({\bf w})$ are overlap-free has length at most $84$, whereas over four letters an infinite example exists. Hence $4$ is the smallest alphabet size admitting simultaneous infinite overlap-freeness. The infinite constructions are verified in Walnut; the finite maxima are obtained by exhaustive breadth-first search and checked independently.

0.04

Boxes in Infinite Words: Complexity, Automata, and Point Modules

cs.FL math.LOmath.RA ·2026-11-16 ·Jason Bell
theory similarity 0.51
Abstract · 23 pages

Motivated by the geometry of point modules over monomial algebras, we introduce a box-counting function associated to a right-infinite word over a finite alphabet. An extendable box is a family of finite words obtained by choosing letters independently at each position, subject to the condition that all choices admit a common infinite right continuation in the associated subshift. We prove several results for these functions for words of linearly bounded complexity. For $k$-automatic words, we show using techniques from first-order logic that the total box-counting function is $k$-regular. Finally, we apply our results to prove eventual affine growth of the number of positive-dimensional irreducible components in finite projections of point-module spaces associated to semiprime monomial algebras of at most quadratic growth.

0.35

Lengths and Counting of Palindromic Prefixes of Standard Sturmian Words

cs.FL math.CO ·2026-11-15 ·Jasem Hamoud
similarity 0.51
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$.

0.30

Cycle Counting and Character Expectations Using Alternating Structures

cs.FL math.GR ·2026-08-27 ·Noam Ta Shma
theory similarity 0.51
Abstract · 59 pages, 22 figures

Recently, two related papers [arXiv:2412.13941, arXiv:2409.03626] found a connection between two subjects: the w-cycle theorem, which is a theorem about counting appearances of cycles reading out a word w in certain graphs, and character expectations on word measures. The w-cycle theorem was proven independently by [arXiv:1410.2540] using stackings and by [arXiv:1410.2579] using bislim structures. In the current work, we generalize stackings and bislim structures to alternating stackings and alternating bislim structures. We show how this significantly strengthens the w-cycle theorem for words admitting such alternating structures, and as a result, also strengthens the recent results of [arXiv:2412.13941] and [arXiv:2409.03626]. We show that generic words admit alternating bislim structures, and therefore, the strengthened results hold for generic words. Using our new machinery, we address conjectures of Wilton, of Hanany-Puder and of Puder-Shomroni. We prove that all three conjectures hold for generic words, but we also find counterexamples for the first two.

0.30