ON THE GENERALIZED RUN LENGTH-GAP THEOREM

Abstract

We introduce and study \emph{fixed degree addition chains} d≥ 2, a natural generalization of classical (binary) addition chains in which each term may be formed as the sum of at most d earlier terms. After giving a precise formal definition, we develop a four-class step partition (the d-dilate steps and three classes of non-d-dilate steps) that extends the usual doubling/large/medium/small decomposition from the binary case. For this partition, we define the notion of a \emph{run} of step types (a maximal consecutive block of steps of a given type) and derive quantitative run-gap inequalities that relate run lengths and run composition to the absolute difference s_j−s_j−1 between consecutive chain elements; these estimates make the dependence on the degree d and on a slowly varying parameter δ(m)=1/log m explicit.\\ The main structural result, the \emph{generalized run length-gap theorem}, gives simple combinatorial criteria which force unbounded gaps in any infinite sequence whose finite prefixes are fixed-degree chains. Concretely, under mild hypotheses asserting that, for all sufficiently large truncation indices t, the truncation contains runs whose lengths (or the number of large/medium steps they contain) grow at least on the order of ((loglog T_t)/(log d))^1+ϵ for some small ϵ>0, we prove undersetn⟶ ∞limsup(T_n−T_n−1)=∞. We also indicate that the growth hypothesis may be substantially weakened: it suffices that the relevant run length statistics tend to infinity with t.\\ The run length-gap framework clarifies how local patterns govern global gap behaviour, suggests natural density and typical-case questions for fixed-degree chains, and raises algorithmic problems about constructing short chains with a prescribed run structure.

ON THE GENERALIZED RUN LENGTH-DENSITY THEOREM
Theophilus Agama
HAL7 Oct 2026PreprintCC BY-ND 4.0Full textGeneral mathematicsHAL
A finite Livshits theorem and local length spectrum rigidity
Jonathan DeWitt, Spencer Durham, James Marshall Reber +1
arXiv20 Sep 2026PreprintarXiv licenceFull textDynamical systems Geometry & topologyarXiv
An elementary proof of the Artin--Springer theorem for generalized quadratic forms over quaternion algebras
Amir Hossein Nokhodkar
arXiv4 Oct 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Reduction numbers for witnesses to the generalized Loewy length
Richard Bartels, Sarah Dajani, Gabriel Koomson
arXiv3 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
A Generalized L² Division Theorem and the Strong Openness Property of Multiplier Ideal Sheaves
Masakazu Takakura
arXiv29 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{agama2026generalized,
  title = {{ON THE GENERALIZED RUN LENGTH-GAP THEOREM}},
  author = {Theophilus Agama},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  url = {https://hal.science/hal-05784814v1},
  note = {CC BY-ND 4.0},
}

RIS

TY  - UNPB
TI  - ON THE GENERALIZED RUN LENGTH-GAP THEOREM
AU  - Theophilus Agama
PY  - 2026
DA  - 2026/10/07
PB  - HAL
UR  - https://hal.science/hal-05784814v1
AB  - We introduce and study \emph{fixed degree addition chains} d≥ 2, a natural generalization of classical (binary) addition chains in which each term may be formed as the sum of at most d earlier terms. After giving a precise formal definition, we develop a four-class step partition (the d-dilate steps and three classes of non-d-dilate steps) that extends the usual doubling/large/medium/small decomposition from the binary case. For this partition, we define the notion of a \emph{run} of step types (a maximal consecutive block of steps of a given type) and derive quantitative run-gap inequalities that relate run lengths and run composition to the absolute difference s_j−s_j−1 between consecutive chain elements; these estimates make the dependence on the degree d and on a slowly varying parameter δ(m)=1/log m explicit.\\ The main structural result, the \emph{generalized run length-gap theorem}, gives simple combinatorial criteria which force unbounded gaps in any infinite sequence whose finite prefixes are fixed-degree chains. Concretely, under mild hypotheses asserting that, for all sufficiently large truncation indices t, the truncation contains runs whose lengths (or the number of large/medium steps they contain) grow at least on the order of ((loglog T_t)/(log d))^1+ϵ for some small ϵ>0, we prove undersetn⟶ ∞limsup(T_n−T_n−1)=∞. We also indicate that the growth hypothesis may be substantially weakened: it suffices that the relevant run length statistics tend to infinity with t.\\ The run length-gap framework clarifies how local patterns govern global gap behaviour, suggests natural density and typical-case questions for fixed-degree chains, and raises algorithmic problems about constructing short chains with a prescribed run structure.
ER  -

Abstract

Related

Cite