Pairwise coprime CRT modulus candidate-growth conjecture

Let NN be the signal length, and let m1m_1, m2m_2, and m3m_3 be pairwise coprime moduli satisfying m1,m2,m3=Θ(N)m_1,m_2,m_3=\Theta(\sqrt{N}). For a kk-sparse signal, apply 3-view CRT gating and denote the resulting candidate set by candidates\text{candidates}. Pairwise coprime candidate-growth conjecture. For any such triple of moduli, there exist kk-sparse signals for which

candidates=ω(k).|\text{candidates}|=\omega(k).

The claim predicts superlinear candidate growth even when the moduli are pairwise coprime, extending the adversarial phenomenon beyond the divisibility condition used in the preceding construction. The source provides no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Aaron R. Flouro and Shawn P. Chadwick, “Safety-Certified CRT Sparse FFT: Ω(k^2) Lower Bound and O(N N) Worst-Case”, arXiv:2604.18911 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.