GCD Reconstruction from Subset LCMs: Elementary Identities, Ambiguity and Counting

For a tuple of positive integers, taking the greatest common divisor of all least common multiples of a fixed subset size extracts an order statistic of each prime-exponent list. Starting from this classical observation, we study what can be recovered when the tuple is hidden but its product and labelled subset LCMs are given. We present a pairwise reconstruction identity and a matching worst-case query bound, characterize all possible GCDs for complete fixed-size observations, and count compatible ordered tuples for arbitrary covering query families through a hypergraph independence polynomial. A reduction from independent set shows that a restricted GCD-existence problem remains NP-complete even when a feasible tuple is supplied. The arguments are elementary consequences of valuations, inclusion-exclusion and standard combinatorial constructions. This note makes no claim of priority for these deductions. A companion Python program (verify.py) reproduces finite exhaustive checks.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24316720
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

GCD Reconstruction from Subset LCMs: Elementary Identities, Ambiguity and Counting

Arsh Mishra
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

GCD Reconstruction from Subset LCMs: Elementary Identities, Ambiguity and Counting

Arsh Mishra
preprint en

Abstract

For a tuple of positive integers, taking the greatest common divisor of all least common multiples of a fixed subset size extracts an order statistic of each prime-exponent list. Starting from this classical observation, we study what can be recovered when the tuple is hidden but its product and labelled subset LCMs are given. We present a pairwise reconstruction identity and a matching worst-case query bound, characterize all possible GCDs for complete fixed-size observations, and count compatible ordered tuples for arbitrary covering query families through a hypergraph independence polynomial. A reduction from independent set shows that a restricted GCD-existence problem remains NP-complete even when a feasible tuple is supplied. The arguments are elementary consequences of valuations, inclusion-exclusion and standard combinatorial constructions. This note makes no claim of priority for these deductions. A companion Python program (verify.py) reproduces finite exhaustive checks.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
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