2025/11/15 by Dvořáková, Lubomíra, Pelantová, Edita
#68R15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2511.12358
The factor complexity \mathcal C\mathbf u of a sequence \mathbf u = u0u1u2 ⋯ over a finite alphabet counts the number of factors of length n occurring in \mathbf u, i.e., \mathcal C\mathbf u(n) = #\mathcal Ln(\mathbf u), where \mathcal Ln(\mathbf u)= \uiui+1⋯ ui+n-1: i ∈ \mathbb N\. Two factors of \mathcal Ln(\mathbf u) are said to be equivalent if one factor is the reversal of the other one. Recently, Allouche et al. introduced the reflection complexity r\mathbf u which counts the number of non-equivalent factors of Ln(\mathbf u). They formulated the following conjecture: a sequence \mathbf u is eventually periodic if and only if r\mathbf u(n+2) = r\mathbf u(n) for some n ∈ \mathbb N. Here we prove the conjecture and characterize the sequences for which r\mathbf u(n+2) = r\mathbf u(n)+1 for every n ∈ \mathbb N and also the sequences for which the equality is satisfied for every sufficiently large n ∈ \mathbb N.