Id: palomar/PALOMAR-2026-11-16-000025 Url: https://github.com/chinmayhegde/fourier-tree-rip-palomar/tree/d35425b021e53164165e9916fc26f80cec6303a1 Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-16-000025-v1.json Repo: https://github.com/chinmayhegde/fourier-tree-rip-palomar Tags: math.NA, cs.IT, msc:42B05, msc:94A12 Score: 0 Title: A Quadratic Lower Bound for Fourier RIP with Tree-Structured Sparsity Trust: high Domain: math.NA Source: palomar Authors: Chinmay Hegde Reviews: 0 Subject: math.NA Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-16 Formalized: true Formalizes: title=A Quadratic Lower Bound for Fourier RIP with Tree-Structured Sparsity identifier= relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-16-000025 Lean 4 formalization of an explicit lower bound for uniformly row-subsampled discrete Fourier transforms acting on canonical binary-heap tree-sparse vectors. With constant distortion, at least half of frequency sequences violate tree-RIP when 20000 m <= k min(k, log_2(N/k)), with an explicit quadratic corollary. The proof uses broom supports, Fejer-kernel concentration, simultaneous Diophantine approximation, and finite counting. A full-DFT isometry theorem checks the normalization and nonvacuity of the definitions.