Subtree Compositions on Three-Armed Trees: Arithmetic classifications, cancellation, and composition fibers

This paper studies vertex-label reconstruction on a known three-armed tree from connected-subtree compositions. It completely classifies sum reconstruction on every S₁,ₖ,ℓ over finite alphabets with at least two symbols. Full reconstruction is classified whenever min(k, ℓ) is odd, and on every S₁,₂,ℓ, S₁,₃,ℓ, and S₁,₄,ℓ. For distinct odd k < ℓ, the full criterion is gcd(k, ℓ) = 1 and gcd(k + 1, ℓ + 1) = 2; sum reconstruction additionally excludes ℓ = 2k − 1. Every ambiguity on S₁,₂,ℓ is classified, with exact counts and linear-time partner recognition. Reciprocal identities reduce sum ambiguities to polynomial seeds; circular-run parity gives the mixed-parity criterion. Quadratic moments yield further full-positive, sum-negative families, including S₁,ₖ,₃ₖ₊₁ for every even k ≥ 4. For fixed distinct short arms a < b, sum reconstruction is periodic modulo M = lcm(a, b, a + 1, b + 1) beyond length 4M. Common divisors produce explicit ambiguities, and interleaving yields unbounded fibers on three arms. Binary testing suffices for non-equilateral shapes; ternary testing always suffices. Unique factorization classifies center-containing data and, separately, ordinary data supplemented by that profile. The supplemented criterion also characterizes ordinary reconstruction when the center symbol occurs nowhere else. A sufficiently long unchanged arm prevents cancellation and reduces reconstruction to a classified two-arm joint profile. The proofs are analytical; exact computations supplement them. Counterexamples show that two moments do not determine full compositions, even for distinct arm lengths, and that ordinary data do not determine the center-containing profile. General ordinary full reconstruction remains open, including residual shorter-even mixed-parity cases and the equal-arm orientation problem. The supplemented, unique-center-symbol, and unchanged-arm results retain their observation or labeling hypotheses. Further questions concern individual fibers beyond S₁,₂,ℓ, sharp fiber bounds, and incomplete observations. The project includes editable sources, figures, algebraic tools, verification reports, and a separate account of corrections and scope.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-14
DOI
https://doi.org/10.5281/zenodo.24237839
Primary Topic
semigroups and automata theory
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Subtree Compositions on Three-Armed Trees: Arithmetic classifications, cancellation, and composition fibers

K. Fathi
Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
article

Subtree Compositions on Three-Armed Trees: Arithmetic classifications, cancellation, and composition fibers

K. Fathi
article en

Abstract

This paper studies vertex-label reconstruction on a known three-armed tree from connected-subtree compositions. It completely classifies sum reconstruction on every S₁,ₖ,ℓ over finite alphabets with at least two symbols. Full reconstruction is classified whenever min(k, ℓ) is odd, and on every S₁,₂,ℓ, S₁,₃,ℓ, and S₁,₄,ℓ. For distinct odd k < ℓ, the full criterion is gcd(k, ℓ) = 1 and gcd(k + 1, ℓ + 1) = 2; sum reconstruction additionally excludes ℓ = 2k − 1. Every ambiguity on S₁,₂,ℓ is classified, with exact counts and linear-time partner recognition. Reciprocal identities reduce sum ambiguities to polynomial seeds; circular-run parity gives the mixed-parity criterion. Quadratic moments yield further full-positive, sum-negative families, including S₁,ₖ,₃ₖ₊₁ for every even k ≥ 4. For fixed distinct short arms a < b, sum reconstruction is periodic modulo M = lcm(a, b, a + 1, b + 1) beyond length 4M. Common divisors produce explicit ambiguities, and interleaving yields unbounded fibers on three arms. Binary testing suffices for non-equilateral shapes; ternary testing always suffices. Unique factorization classifies center-containing data and, separately, ordinary data supplemented by that profile. The supplemented criterion also characterizes ordinary reconstruction when the center symbol occurs nowhere else. A sufficiently long unchanged arm prevents cancellation and reduces reconstruction to a classified two-arm joint profile. The proofs are analytical; exact computations supplement them. Counterexamples show that two moments do not determine full compositions, even for distinct arm lengths, and that ordinary data do not determine the center-containing profile. General ordinary full reconstruction remains open, including residual shorter-even mixed-parity cases and the equal-arm orientation problem. The supplemented, unique-center-symbol, and unchanged-arm results retain their observation or labeling hypotheses. Further questions concern individual fibers beyond S₁,₂,ℓ, sharp fiber bounds, and incomplete observations. The project includes editable sources, figures, algebraic tools, verification reports, and a separate account of corrections and scope.

Zenodo (CERN European Organization for Nuclear Research)
semigroups and automata theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Subtree Compositions on Three-Armed Trees: Arithmetic classifications, cancellation, and composition fibers — K. Fathi · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS