PaperlayerView exact revision on arXiv

Source-linked AI summary

Certificate-Governed CRT Sparse FFT: Verified Global-Label Candidate Construction under Explicit Decoding Models

Aaron R. Flouro, Shawn P. Chadwick

arXiv:2609.34086v1eess.SPcs.DS

TL;DR

Exact sparse Fourier recovery is sought for noiseless, on-grid spectra of known sparsity, under a design-selected transform length. The paper builds a deterministic CRT candidate pipeline with a one-sided shift screen and a sound residual verifier. Its hybrid returns exact spectra within the stated model, while sparse-path completion and cost depend on additional conditions and the decoding model.

Abstract

from arXiv · show

We present a deterministic CRT-based sparse Fourier architecture for exact recovery of noiseless, on-grid, at-most-\(k\)-sparse spectra with an engineered transform length. The transform length \(N\) is selected as an exact product of small pairwise-coprime stage primes, allowing each stage to use transforms whose size scales with the sparsity rather than the ambient dimension. Three co-prime-increment time shifts provide a one-sided singleton-consistency screen: every genuine singleton passes, while passing collision bins remain provisional candidates. Each candidate bin is mapped by a total label-emission rule to at most one global frequency label, and per-stage label sets are intersected, yielding a deterministic \(O(k)\) candidate bound for every input. Candidate construction uses \(O(k\log N)\) samples. In a comparison real-RAM model with exact arithmetic and exact phase evaluation but without unit-cost root-index decoding, it requires \(O(k\log^2 N/\log k)\) arithmetic operations; in a stronger root-index-oracle model the arithmetic cost is \(O(k\log N)\). Under all-stage genuine-singleton survival, the candidate set contains the true support. Exactness, however, does not depend on that survival condition: a consecutive-sample residual verifier accepts a sparse reconstruction only when it is exact, and all failures route to a dense FFT. The resulting hybrid algorithm therefore returns the exact spectrum for every input in the stated noiseless, on-grid, at-most-\(k\)-sparse model, with \(O(N\log N)\) worst-case runtime. The verified sparse path additionally incurs an \(O(k^2)\) verifier cost in the root-index-oracle model. Neither computational model is a bit-complexity model.

I. INTRODUCTION

The paper targets deterministic exact recovery for known, very-low-sparsity, noiseless on-grid spectra with a design-selected transform length. It combines sparsity-sized CRT stages and a one-sided shift screen with global-label candidates and verifier-gated fallback, extending deterministic CRT methods into this regime under explicit operating and cost models.

A. Relationship to Prior Work

  • The deterministic CRT construction complements, rather than dominates, prior methods: it targets very low sparsity and exact noiseless on-grid recovery, with a conditional sparse fast path and dense fallback.Compared with Merhi et al., it requires a design-selected exact-product length and targets exact recovery rather than near-best approximation.Source: A. Relationship to Prior Work · p. 2

B. Contribution and Scope

  • The transform length is design-selected as an exact product of pairwise-coprime stage primes, giving Θ(k)-sized stage transforms and a one-sided co-prime-shift screen.Passing bins remain provisional; each candidate emits at most one global label and per-stage label sets are intersected.Source: §I · p. 1, B. Contribution and Scope · p. 2
  • The O(k) candidate bound holds for every input, while support containment and sparse-path completion require all-stage genuine-singleton survival.The verified sparse path has O(k log N) samples and O(k log N) + O(k^2) arithmetic in the root-index-oracle model.Source: B. Contribution and Scope · p. 3
  • A sound final verifier makes exact recovery unconditional within the stated model, routing failed sparse attempts to a dense FFT with O(N log N) worst-case runtime.The sparse-path cost depends on the declared decoding model; the comparison real-RAM bound is O(k log^2 N / log k), while the root-index-oracle bound is O(k log N).Source: §I · p. 1, B. Contribution and Scope · p. 3

C. Roadmap

  • The paper’s roadmap proceeds from the operating envelope and algorithm through screening and verification to cost analysis, fallback, and limitations.It also identifies the superseded residue-tuple analysis and appendices containing deferred analysis and worked traces.Source: C. Roadmap · p. 4

II. PROBLEM STATEMENT AND OPERATING ENVELOPE

  • The intended engineering regime is 3 ≤ k < 20, but this is not a theorem cutoff; all-stage genuine-singleton survival becomes more demanding as k rises.The formal results cover every k ≥ 3 under the engineered exact-product model.Source: B. Contribution and Scope · p. 3, §II · p. 5
  • The recovery task is exact reconstruction of an unknown at-most-k-sparse on-grid spectrum from noiseless samples, with provable correctness rather than high-probability success.The formal signal model assumes known k and exact arithmetic.Source: §II · pp. 4–5

A. Detection vs Avoidance

The framework allows collisions in decimated spectra and screens bins using co-prime time shifts rather than claiming to prevent collisions. Because a passing collision can mimic a singleton, the screen only proposes candidates; global-label emission and residual verification determine whether sparse recovery completes.

A. Detection vs Avoidance

  • The method allows decimated-spectrum collisions; bins failing geometric tests emit no label, while a surviving phantom is rejected by the residual verifier if used in reconstruction.The algorithm makes no claim to bypass the Fredman-Komlós bound as a generic lower bound; aborted sparse attempts use the dense fallback.Source: A. Detection vs Avoidance · p. 6
  • Coprime increments make it impossible for two distinct colliding frequencies each to satisfy both phase-increment congruences, but their phasor sum can still mimic a singleton on a measure-zero coefficient slice.Thus the screen is one-sided: genuine singletons pass, but a passing bin is only a candidate.Source: A. Detection vs Avoidance · p. 6

A. Discrete Fourier Transform

  • The shifted-decimated spectrum is a stage-size DFT of shifted, decimated samples; the listed shift values define the observations used for magnitude and phase-ratio statistics.The notation itself assigns no screening status; the formal screen and implementation surrogates are defined separately.Source: A. Discrete Fourier Transform · pp. 6–7
  • Phase unwrapping and its linear-regression R² test are finite-precision implementation surrogates, not the formal modular phase-ratio test.The formal test uses exact unit-modulus rotations for the two increment ratios.Source: A. Discrete Fourier Transform · p. 7

B. Key Notation

The notation distinguishes CRT stages, within-stage shifts, and appendix-only views, while defining the per-stage global-label sets and their intersection. The algorithm uses an engineered exact-product length and bounded candidate construction, with sparse output accepted only after verification.

IV. ALGORITHM OVERVIEW

  • The primary architecture has L CRT stages, three shifts per stage, and one view; “view” refers only to the appendix extension.The per-stage global-label sets are intersected, rather than forming residue tuples.Source: §IV · pp. 7–8

A. Algorithm Structure

  • An engineered length N is the exact product of pairwise-coprime stage primes, each in [k, ck], with L = Θ(log_k N) for fixed c.The available primes constrain L; the interval [k, 2k] suffices when it contains enough primes, otherwise the interval can widen.Source: A. Algorithm Structure · pp. 8–9
  • Each candidate-singleton emits at most one global frequency label, and intersecting the per-stage label sets gives a deterministic O(k) candidate set.The candidate bound does not imply every emitted label is true; support containment requires all-stage genuine-singleton survival.Source: A. Algorithm Structure · p. 9
  • The algorithm returns a sparse reconstruction only after the sound residual verifier passes; otherwise it uses the dense O(N log N) FFT fallback.The verifier reads k + |G| consecutive residual samples.Source: A. Algorithm Structure · pp. 9–10
  • In the illustrative k = 8 trace, each of four stages emits g = 67, yielding G = {67} with |G| = 1 = O(k); the sound final verifier certifies x̂ = x exactly.Verification adds O(k^2) in model (a), or O(k^2 + k log N) in model (b).Source: A. Algorithm Structure · pp. 10–11

B. Modular Decimation

Modular decimation maps each frequency to its residue class, so a sparse spectrum remains sparse in the decimated view.

B. Modular Decimation

  • A frequency f maps to residue r = f mod M, and bin r is a singleton exactly when one supported frequency maps there.Decimation sorts frequencies into residue bins; it does not create more bins occupied by frequencies than the original support size.Source: B. Modular Decimation · p. 11
  • A k-sparse spectrum has at most k non-zero bins in every decimated spectrum.Each of at most k frequencies maps to one residue, although multiple frequencies can share a residue.Source: B. Modular Decimation · p. 11

C. Decimated Sampling Operator under Divisor Compatibility

When each stage prime divides N, the sampling operator yields an exact modular-decimation view using pℓ samples per shift. This supports Θ(k)-scale stage transforms and the stated sparse-path cost; arbitrary lengths require compatible moduli, engineered acquisition, or dense fallback.

C. Decimated Sampling Operator under Divisor Compatibility

  • When pℓ divides N, each stage samples pℓ uniformly spaced time entries per shift, and its pℓ-point DFT is the decimated frequency view.The exact aliasing identity applies under this divisor-compatibility condition.Source: C. Decimated Sampling Operator under… · p. 11
  • At zero shift, a singleton-bin coefficient is recovered by scaling its decimated observation by N/pℓ; nonzero shifts require conjugate-phase de-rotation.The shift phase is unity at σ = 0.Source: C. Decimated Sampling Operator under… · p. 11
  • With three shifts and L = O(log_k N) stages, candidate construction uses O(k log N) samples and arithmetic in the root-index-oracle model.Without unit-cost root-index decoding, the comparison real-RAM arithmetic cost is O(k log^2 N / log k) on the same O(k log N) samples.Source: C. Decimated Sampling Operator under… · p. 12
  • The candidate-construction cost bound does not itself guarantee exact recovery: a candidate is returned only after verifier PASS, while failure routes to dense O(N log N) FFT.The verifier reads k + |G| consecutive residual samples; its soundness is established separately from the cost bound.Source: C. Decimated Sampling Operator under… · p. 12
  • For arbitrary N outside divisor compatibility, the stated options are compatible moduli, an engineered acquisition length, or dense FFT fallback.The sparse-path cost theorem applies only within the divisor-compatibility envelope; zero-padding a fixed arbitrary-length problem generally breaks the on-grid sparsity assumption.Source: C. Decimated Sampling Operator under… · pp. 12–13

V. SINGLETON SCREENS AND CORE LEMMAS

For a genuine singleton, shifting changes the observation's phase but not its magnitude, and two coprime shift increments recover its global frequency label. The screen can admit collision bins, so its passing candidates are provisional rather than proof of singleton status.

V. SINGLETON SCREENS AND CORE LEMMAS

  • The section distinguishes the occupied equal-magnitude pre-screen, the total label-emission rule, and their conjunction, the full exact emission predicate.A screen pass alone certifies nothing, and the final verifier is the backstop for accepted false labels.Source: §V · p. 13

A. True-Singleton Shifted-Observation Identity

  • For a genuine singleton, shifted observations have equal positive magnitudes and their phase changes encode the tone's frequency.The identity applies when the tone is the only support frequency in its decimated bin.Source: A. True-Singleton Shifted-Observation… · p. 13

B. Exact Phase-Ratio Recovery of the Global Label

  • Coprime increments 31 and 32 combine the two phase ratios into ω^f, uniquely identifying the singleton's global frequency label.The B́ezout phase rule recovers the label from the three shifted observations.Source: B. Exact Phase-Ratio Recovery of the… · pp. 13–14

C. The One-Sided Exact Screen

The multi-stage CRT pipeline screens and labels candidate frequencies, then uses a sound residual verifier to gate sparse outputs. When sparse completion fails, dense fallback preserves exact recovery within the stated model.

C. The One-Sided Exact Screen

  • Every genuine singleton passes with zero false negatives and emits its true label; for each collision multiplicity m ≥ 2, Lebesgue-almost-every coefficient choice on fixed support fails, but admissible measure-zero slices can emit provisional phantom labels.Source: C. The One-Sided Exact Screen · pp. 14–15

D. Phantoms and the Verifier Backstop

VI. CONDITIONAL FAST-PATH COMPLEXITY AND UNCONDITIONAL CORRECTNESS

  • The multi-stage engine constructs candidates in O(k log N) oracle-model arithmetic, while verifier-gated completion and dense fallback give unconditional correctness with O(N log N) worst-case runtime.The sparse candidate count is O(k) for every input, but candidate construction alone does not establish the exactness of the returned spectrum.Source: §VI · p. 15, B. Sound Final Verifier · pp. 17–18

A. Standing Envelope and the Two Cost Models

  • A per-bin label read costs O(log N) in the comparison real-RAM model and O(1) in the root-index-oracle model; neither is a bit-complexity model.The oracle model assumes unit-cost root-index decoding primitives.Source: A. Standing Envelope and the Two Cost… · p. 16

B. Sound Final Verifier

  • A verifier checks k + |G| consecutive residual samples, and a PASS forces exact recovery even when |G| < k.Its soundness does not require the true support to be contained in the candidate set.Source: B. Sound Final Verifier · p. 17

C. Global-Label Engine: Deterministic O(k) Candidate Count

The global-label engine maps each passing bin to at most one full frequency label and intersects stage sets, proving a deterministic O(k) candidate bound without requiring singleton truth. Support containment is conditional on all-stage singleton survival; a sound verifier and dense fallback preserve exact recovery when sparse candidates are insufficient or incorrect.

C. Global-Label Engine: Deterministic O(k) Candidate Count

  • Each passing bin emits at most one full frequency label, and intersecting stage sets avoids the Cartesian-product growth of residue stitching.The total rule is defined for true singletons and screen-passing collision bins, which may emit one label or none.Source: C. Global-Label Engine: Deterministic… · p. 18
  • For every input, the per-stage label sets and their intersection contain at most ck = O(k) labels, without assuming passing bins are genuine singletons.Each stage has at most pℓ bins, and pℓ ≤ ck; intersection cannot exceed the size of any stage set.Source: C. Global-Label Engine: Deterministic… · p. 19
  • A true tone that is a singleton at every stage passes the screen and survives each intersection.This is the completeness direction of the candidate construction; it does not establish that every candidate label is genuine.Source: C. Global-Label Engine: Deterministic… · p. 19
  • Every support frequency that remains a genuine singleton at every stage is included in the candidate-set intersection.A frequency that collides at any stage is not guaranteed to enter the candidate set and is handled by the dense path.Source: C. Global-Label Engine: Deterministic… · p. 19
  • Screen-passing phantom labels do not inflate the O(k) count, but the engine does not certify which labels are true support frequencies.If a phantom is used in a reconstruction, the sound verifier rejects the incorrect result and the dense fallback recovers the input.Source: C. Global-Label Engine: Deterministic… · pp. 19–20

D. Conditional Sparse-Path Candidate-Construction Cost

Candidate construction uses O(k log N) samples and has an arithmetic cost of O(k log N) with unit-cost root-index decoding, or O(k log^2 N / log k) without it. These bounds concern candidate construction; support containment requires all-stage singleton survival, while the verified sparse path and dense fallback provide the broader exact-recovery guarantee.

D. Conditional Sparse-Path Candidate-Construction Cost

  • O(k log N) arithmetic operations and O(k log N) samples suffice for candidate construction in the root-index-oracle model.The constructed set has O(k) labels for every input, or the sparse attempt dispatches to fallback within the same construction-cost bound.Source: D. Conditional Sparse-Path… · pp. 20–21
  • L = O(log_k N) stages of Θ(k)-sized FFTs contribute O(k log N) total transform work in the root-index-oracle accounting.Each stage costs O(k log k); the engineered transform family uses pairwise-coprime primes in [k, ck].Source: D. Conditional Sparse-Path… · p. 20
  • A fallback triggered during candidate construction incurs no more than the full sparse-attempt budget of O(k log N) samples and arithmetic operations before the dense path begins.The attempt stops after a partial sum of the same input-independent per-stage charges.Source: D. Conditional Sparse-Path… · p. 21
  • O(k log^2 N / log k) arithmetic operations and O(k log N) samples bound candidate construction in the comparison real-RAM model without unit-cost root-index decoding.The repeated exact root-index search and evaluation costs O(log N) per candidate-singleton and dominates the remaining arithmetic terms.Source: D. Conditional Sparse-Path… · p. 21
  • The cost bounds do not establish support containment: that requires all-stage genuine-singleton survival, and neither decoding model is a bit-complexity model.The verified sparse path adds O(k^2) arithmetic in the root-index-oracle model; the hybrid has O(N log N) worst-case runtime.Source: D. Conditional Sparse-Path… · pp. 20–21

E. Hybrid Unconditional Correctness

For every noiseless, on-grid input with at most k tones, the deterministic hybrid returns the exact spectrum via a verified sparse path or dense FFT fallback. The parameter-selection section constructs an exact-product transform length from pairwise-coprime stage primes.

E. Hybrid Unconditional Correctness

  • Every noiseless, on-grid input with at most k tones is recovered exactly by one of two deterministic branches, with O(N log N) worst-case runtime.A verifier PASS returns an exact sparse reconstruction; otherwise the algorithm uses the dense FFT.Source: E. Hybrid Unconditional Correctness · pp. 21–22
  • A sparse reconstruction is returned only after the verifier passes; verifier failure, an aborted attempt, or an out-of-envelope input routes to the exact dense FFT.The verifier checks k + |G| consecutive residual samples, and PASS implies the reconstruction equals the spectrum.Source: E. Hybrid Unconditional Correctness · p. 22
  • All-stage genuine-singleton survival is needed for true-support containment and sparse-path completion, but not for the hybrid algorithm’s exactness guarantee.The dense fallback covers failed sparse attempts, while the verifier certifies any accepted sparse output.Source: E. Hybrid Unconditional Correctness · pp. 22–23
  • Candidate construction uses O(k log N) samples and costs O(k log N) arithmetic in the root-index-oracle model or O(k log^2 N / log k) in the comparison model.The verified sparse path adds O(k^2) verifier cost in the oracle model; its completion remains conditional on the operating envelope.Source: E. Hybrid Unconditional Correctness · pp. 22–23

A. Parameter Selection for Multi-Stage Algorithm

  • The parameter rule chooses pairwise-coprime primes in [k, ck] and sets the engineered transform length to their exact product; implementation batching may use 64pℓ lengths.The formal per-stage transform remains the pℓ-point DFT, and the 64 factor is an implementation choice outside the theorem’s cost bound.Source: A. Parameter Selection for Multi-Stage… · pp. 23–24
  • For k = 50, four primes 53, 59, 61, and 67 yield engineered length Neng = 12,780,049, exceeding the illustrative target Ntarget = 10^6.The example reports candidate-construction costs of O(k log Neng) in the oracle model and O(k log^2 Neng / log k) in the comparison model, with O(k log Neng) samples.Source: A. Parameter Selection for Multi-Stage… · p. 24
  • For k = 15, widening the prime interval to [15, 45] supplies five stage primes and gives Neng = 6,678,671.The reported candidate-construction costs are O(k log Neng) in the oracle model and O(k log^2 Neng / log k) in the comparison model, with O(k log Neng) samples.Source: A. Parameter Selection for Multi-Stage… · p. 24

B. Shift Count Selection

The section specifies implementation choices for the shift screen, deterministic set intersection, root-index decoding, and memory use, then illustrates how a collision is handled. The example’s rejection is specific to its computed root-membership failure.

B. Shift Count Selection

  • Three shifts, {0, ∆1, ∆1 + ∆2} with gcd(∆1, ∆2) = 1, provide the formal noiseless screen; larger shift counts are left uncharacterized for noisy or off-grid operation.The formal screen uses S = 3; S ∈ [4, 8] is an implementation-time design parameter.Source: B. Shift Count Selection · p. 24

C. Deterministic Set Intersection

  • Sorted per-stage label arrays are intersected by a merge pass in O(k) comparisons per stage, totaling O(kL) across L stages.The bound follows from each operand having O(k) labels; sorting costs are absorbed by the per-stage transform charge.Source: C. Deterministic Set Intersection · p. 24

D. Root-Index Decoding

  • The per-bin root-index read costs O(1) with the unit-cost oracle and O(log N) in the comparison model, producing the gap between the stated candidate-construction bounds.The passage says a fielded implementation uses the comparison model unless it supplies those unit-cost primitives.Source: D. Root-Index Decoding · p. 24

E. Memory Complexity

  • Sequential operation uses O(k + log N / log k) working memory, versus O(k log N / log k) when all stages run concurrently.Sequential processing reuses buffers; concurrent stages each retain an O(k) transform buffer and label set.Source: E. Memory Complexity · p. 25

A. Adversarial-Support Example: A Collision that Passes the nMAD Surrogate and is Rejected at Root-Membership

  • In the worked collision, the computed Bèzout combination has modulus about 8.4305, so exact root-membership rejects the bin before it emits a label.If the total rule is bypassed and a rounded guess is forced into the candidate set, the verifier fails the reconstruction and routes it to the dense FFT; this example does not prove that every adversarial collision is rejected by the screen.Source: A. Adversarial-Support Example: A… · pp. 25–26

B. Exact Emission-Predicate-Passing Phantom and nMAD Surrogate False Accept

An exact two-tone collision can pass the formal screen and emit a phantom label, so the paper relies on a final verifier and dense fallback for exactness. The conclusion states the model, guarantees, costs, and remaining scope limits.

B. Exact Emission-Predicate-Passing Phantom and nMAD Surrogate False Accept

  • A two-tone witness passes the exact screen and emits a phantom label; if it survives intersection and enters the reconstruction, the residual verifier rejects it and triggers dense fallback.This is an exact algebraic identity, not a finite-precision event.Source: B. Exact Emission-Predicate-Passing… · p. 26

A. Current Limitations

  • The candidate set is not phantom-free: a measure-zero screen-passing phantom can survive intersection, so exactness is verifier-secured rather than screen-secured.A deterministic per-bin rule excluding such phantoms remains an open direction, but correctness does not depend on resolving it.Source: 1) Phantom Exclusion: Correctness is… · p. 27

2) Finite-Precision Verification: the Exact-Arithmetic Requirement:

  • The verifier’s soundness is an exact-arithmetic, noiseless property; a fixed absolute floating-point residual threshold is unsound for arbitrary complex coefficients.The passage recommends exact or rational residual arithmetic, or coefficient-normalized, condition-aware thresholds.Source: 2) Finite-Precision Verification: the… · p. 27

3) All-Stage-Survival Specialization of the Fast Path:

  • The O(k log N) sparse path requires genuine-singleton survival at every stage; collisions can exclude true tones or produce labels that lead to dense fallback.Recovery from partial singleton appearances is left open, and correctness remains unaffected by fallback.Source: 3) All-Stage-Survival Specialization… · p. 27

4) Noiseless On-Grid Model:

  • The formal model assumes noiseless observations and integer-grid frequencies; noise and off-grid frequencies are not characterized.The passage notes that fractional frequencies disrupt singleton isolation, residue rounding, and the linear phase relation.Source: 4) Noiseless On-Grid Model · p. 27

B. Future Research Directions

  • Future directions include partial-stage recovery, finite-precision and noise analysis, off-grid refinement, arbitrary lengths, empirical validation, and reduced-sample verifiers.These are research directions, not specified algorithms or performance promises.Source: B. Future Research Directions · pp. 27–28

X. CONCLUSION

  • The hybrid returns exact spectra within the noiseless, on-grid, at-most-k model, with O(N log N) worst-case runtime; sparse candidate construction costs O(k log^2 N / log k) in the comparison model or O(k log N) with the root-index oracle.The candidate set is O(k) for every input, while support containment requires all-stage genuine-singleton survival; the verifier cost is reported separately.Source: §X · p. 28
  • The conclusion identifies the oracle-model decoding assumption, surviving phantoms, narrow operating model, and lack of finite-precision, noise, off-grid, and empirical validation as remaining boundaries.The comparison-model bound is the default proved candidate-construction figure without the root-index oracle.Source: §X · p. 28

APPENDIX A WHY UNLABELED RESIDUE-TUPLE INTERSECTION FAILS:

The appendix contrasts a superseded Cartesian residue-tuple cascade with global-label intersection. Tuple counts can multiply across stages, while per-bin recovery bounds candidate count but does not guarantee soundness.

APPENDIX A WHY UNLABELED RESIDUE-TUPLE INTERSECTION FAILS:

  • The superseded residue-tuple cascade forms a Cartesian product of screened bins, whose count multiplies across stages and can exceed the candidate budgets.The global-label engine instead emits per-bin full-frequency labels and intersects stage sets, yielding an O(k) bound without forming a product.Source: Appendix A · pp. 28–29

A. The Cartesian Residue-Tuple Cascade (Superseded)

  • With two screened bins at each stage, the final tuple count is at least 2^L; at k = 8 and c = 4, the maximal L = 7 instance has at least 128 tuples, exceeding the chain-end budget k = 8.The tuple cascade also admits mixed CRT combinations that are not true tones.Source: A. The Cartesian Residue-Tuple Cascade… · pp. 29–30

B. Per-Bin B´ezout Recovery and the Measure-Zero Phantom (Superseded Path)

  • Per-bin Bézout recovery can emit a phantom on a measure-zero coefficient slice of collisions, so its O(k) count bound does not itself establish soundness.A surviving phantom is rejected downstream by the sound residual verifier if it enters the reconstructed candidate.Source: B. Per-Bin B´ezout Recovery and the… · pp. 30–31

GENERICITY, AND ESCALATION

Coprime increments give a pairwise uniqueness guarantee for on-grid frequencies, while the three-shift screen rejects generic collisions but remains one-sided. Candidate construction and collision screening therefore do not certify exact recovery on their own; the verifier and dense fallback secure correctness.

A. B´ezout Co-Primality and Intuition

  • For on-grid frequencies, simultaneous congruence under two coprime increments forces the frequencies to be equal, without a hypothesis relating the increments to N.This is a componentwise pairwise result, not a guarantee against every multi-tone phasor-sum match.Source: A. B´ezout Co-Primality and Intuition · pp. 31–32
  • The multi-stage construction intersects global labels to narrow candidates to O(k), but true-support containment requires all-stage genuine-singleton survival.Outside that condition, surplus labels or screen-passing phantoms may remain; a failed verifier routes to the dense fallback.Source: A. B´ezout Co-Primality and Intuition · p. 32

B. Generic Collision Rejection

  • For the operative shift triple, fixed supports with at least two tones pass the exact screen only on a measure-zero set of coefficient vectors.The screen is one-sided: generic collisions fail, but exceptional passing collisions remain, so final exactness is verifier-gated.Source: B. Generic Collision Rejection · pp. 32–33

GENERICITY, AND ESCALATION

  • Arithmetic-shift Hankel/Prony escalation is optional, requires a separate sample acquisition, and is outside the primary algorithm and its cost theorems.The appendix says no guarantee of the paper depends on this escalation.Source: B. Generic Collision Rejection · p. 33

C. Screen-Passing Phantoms: Measure-Zero Witnesses at Every Multiplicity

Screen-passing phantoms exist at every collision multiplicity of at least two, though the examples are exceptional coefficient configurations. The co-prime-increment triple is a one-sided phase-consistency screen, distinct from arithmetic-shift Hankel/Prony rank testing and its optional escalation.

C. Screen-Passing Phantoms: Measure-Zero Witnesses at Every Multiplicity

  • A two-tone bin can exactly pass the screen and emit a false phantom label; such a measure-zero adversarial configuration is the minimum-multiplicity false accept.The example uses tones {0, 24,679} and emits phantom 49,358.Source: C. Screen-Passing Phantoms:… · pp. 33–34
  • For every m ≥3, an admissible instance has a colliding bin with all coefficients nonzero that passes the exact screen and emits a phantom frequency.These constructions establish existence across multiplicities, not within one fixed N.Source: C. Screen-Passing Phantoms:… · pp. 34–35

D. Shift-Triple Design and Arithmetic-Shift Prony Escalation

  • For the triple {0, ∆1, ∆1 + ∆2}, unless ∆2 = ∆1 it is not an arithmetic progression, so classical Hankel/Prony rank-one testing does not apply; screening instead uses exact ratio/root conditions.The rank-one specialization is for singleton detection only when arithmetic shifts {0, ∆, 2∆} are deployed.Source: D. Shift-Triple Design and… · pp. 35–36
  • Optional arithmetic-shift Prony escalation uses a separate acquisition and is not invoked by Algorithm 1 or covered by its cost theorems.If enabled, the implementation must re-derive its cost bounds; deterministic correctness remains with the final verifier.Source: D. Shift-Triple Design and… · p. 36

E. Magnitude and Phase Surrogate Lemmas (Implementation Commentary)

The implementation commentary distinguishes exact singleton magnitude and phase properties from their computational surrogates, and separates the operative co-prime screen from optional or non-operative collision analyses. Across stages, CRT counting rules out a pair colliding at every stage, but not at every subset of stages.

E. Magnitude and Phase Surrogate Lemmas (Implementation Commentary)

  • A noiseless on-grid singleton has exactly equal shifted magnitudes, while its unwrapped phase is affine in the shift.Principal-value phase is affine only modulo 2π, so its affine reading is an implementation surrogate rather than a formal screen condition.Source: E. Magnitude and Phase Surrogate… · p. 37

F. Collision Behavior Across Stages

  • The keyed multi-view collision-rejection idea and per-residue pairing-uniqueness claim are design history and future work, not required for the core theorem.The exact Cartesian tuple-count obstruction is recorded separately.Source: F. Collision Behavior Across Stages · p. 37

1) Multi-Tone Bin Behavior:

  • Consecutive shifts can create deterministic magnitude-only blind spots, whereas the co-prime shifts reject generic collisions under the stated nondegeneracy assumptions.Every true singleton passes the stated noiseless, on-grid screen; generic multi-tone collisions fail at least one phase-consistency test.Source: 1) Multi-Tone Bin Behavior · p. 37

2) Multi-Stage Collision Rejection:

  • No distinct pair can collide in all L stages when the pairwise-coprime stage-prime product reaches N, but a pair may collide in a proper subset of stages.The counting bound does not ensure that a tone enters the candidate set; stage labels require screening and emission, and true-tone containment requires genuine-singleton survival.Source: 2) Multi-Stage Collision Rejection · pp. 37–38

G. Verifier Scope and a Reduced-Sample Variant

The verifier’s soundness is confined to exact arithmetic in the noiseless, on-grid setting, while an alternative reduced-sample CRT verifier requires a divisor-compatible separating family. A worked example traces one frequency through per-stage labeling and intersection to an exact verifier-certified reconstruction.

G. Verifier Scope and a Reduced-Sample Variant

  • Verifier soundness is an exact-arithmetic, noiseless, on-grid property; no robustness to noise is claimed, and a fixed absolute floating-point tolerance is unsound for arbitrary complex coefficients.Nonzero residuals can be scaled below any fixed tolerance, and coherent cancellation can further shrink checked samples.Source: G. Verifier Scope and a Reduced-Sample… · p. 38
  • The alternative CRT verifier is sound with a 2k-separating family, but worst-case families need Θ(k log_k N) divisor-moduli views, which may not fit the engineered transform length.It is retained only when a divisor-compatible separating family is engineered into N; the consecutive-sample verifier is preferred for the unconditional guarantee.Source: G. Verifier Scope and a Reduced-Sample… · p. 38

APPENDIX C DETAILED GLOBAL-LABEL WORKED EXAMPLE:

  • At each stage, ratios from shifts 0, 31, and 63 recover the same global phase label g = 67; checking g modulo that stage’s pℓ admits it into Gℓ.Source: Appendix C · p. 39
  • In the N=46,189, k=8 trace, four stage-label sets intersect to G={67}, |G|=1=O(k), without forming a residue tuple.The example is a single-frequency trace, not a full k=8 support example.Source: Appendix C · pp. 38–39
  • The zero-shift observation estimates the coefficient, and a PASS on k+|G| consecutive residual samples certifies the example’s sparse reconstruction as exact.A phantom label would yield a nonzero residual, rejection, and routing to the dense O(N log N) fallback.Source: Appendix C · pp. 39–40

APPENDIX D COST MODELS: FURTHER DISCUSSION

The cost discussion makes the root-index decoding assumptions behind the sparse-path bounds explicit and distinguishes them from bit-level implementation costs. It also separates the core stage-and-shift method from adaptive-view design directions that are not formal results.

APPENDIX D COST MODELS: FURTHER DISCUSSION

  • The appendix expands the two decoding-cost models without changing the cost theorems stated in the body.It covers the per-bin procedure, model assumptions, and practical decoding consequences.Source: Appendix D · p. 40

B. The Comparison Model: Disclosure and the IKP Concession

  • The comparison real-RAM model is not a bit-complexity model: it retains exact real arithmetic and exact arg evaluation, with no finite representation or precision bound supplied.The paper leaves a genuine bit-complexity account open; unlike the cited IKP work, it does not discharge the root-index assumption.Source: B. The Comparison Model: Disclosure… · p. 40

A. The Costed Decoding Procedure in Full

C. Root-Index Decoding in Practice

  • The rounded phase index is only a candidate: exact root-membership and residue checks decide emission, while precomputing all N roots costs Θ(N) preprocessing and storage.The declared model allows O(1) storage beyond the samples.Source: C. Root-Index Decoding in Practice · pp. 40–41

FUTURE WORK)

  • The keyed multi-view theorems were withdrawn as unproven; the retained CRT observations establish triple injectivity and exclude two frequencies colliding in all three views, not per-view injectivity.The paper makes no soundness claim based on view count, and the extension is design history rather than part of the core engine.Source: FUTURE WORK) · p. 41
  • The adaptive-view schedule and occupancy figures are illustrative design targets outside the engineered divisor-compatibility envelope, so formal cost and correctness statements do not apply.The targets rely on a uniform-residue occupancy heuristic and exclude association, verification, fallback, and implementation costs.Source: FUTURE WORK) · p. 41
Loading 2609.34086v1…