{"ID":2825938,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.20598","arxiv_id":"2512.20598","title":"On the near-tightness of $χ\\leq 2r$: a general $σ$-ary construction and a binary case via LFSRs","abstract":"In the field of compressed string indexes, recent work has introduced suffixient sets and their corresponding repetitiveness measure $χ$. In particular, researchers have explored its relationship to other repetitiveness measures, notably $r$, the number of runs in the Burrows--Wheeler Transform (BWT) of a string. Navarro et al. (2025) proved that $χ\\leq 2r$, although empirical results by Cenzato et al. (2024) suggest that this bound is loose, with real data bounding $χ$ by around $1.13r$ to $1.33r$ when the size of the alphabet is $σ= 4$. To better understand this gap, we present two cases for the asymptotic tightness of the $χ\\leq 2r$ bound: a general construction for arbitrary $σ$ values, and a binary alphabet case, consisting of de Bruijn sequences constructed by linear-feedback shift registers (LFSRs) from primitive polynomials over $\\mathbb{F}_2$. The second is a novel characterization of which de Bruijn sequences achieve the literature run-minimal pattern for the cyclic BWT. Moreover, we show that de Bruijn sequences fail to close the gap for $σ\\geq 3$.","short_abstract":"In the field of compressed string indexes, recent work has introduced suffixient sets and their corresponding repetitiveness measure $χ$. In particular, researchers have explored its relationship to other repetitiveness measures, notably $r$, the number of runs in the Burrows--Wheeler Transform (BWT) of a string. Navar...","url_abs":"https://arxiv.org/abs/2512.20598","url_pdf":"https://arxiv.org/pdf/2512.20598v1","authors":"[\"Vinicius T. V. Date\",\"Leandro M. Zatesko\"]","published":"2025-12-23T18:44:29Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}