Legendre-symbol construction conjecture for optimal restricted isometry matrices

Fix $\delta>0$. Let $K$, $M$, and $N$ be positive parameters, and let $\Phi$ be the $M\times N$ matrix defined entrywise using the Legendre symbol modulo a prime $p$ by

$$\Phi[m,n]:=\frac{1}{\sqrt{M}}\bigg(\frac{M(n-1)+m}{p}\bigg).$$

Legendre-symbol RIP conjecture. There exists a universal constant $C$ such that for every $\delta>0$, there exist $N_0>0$ and $P_0(N)=O(2^{\operatorname{poly}(N)})$ such that, whenever

$$M\geq(C/\delta^2)K\log(N/K), \qquad N\geq N_0,$$

and $p\geq P_0$ is prime, the matrix $\Phi$ satisfies the $(2K,\delta)$-restricted isometry property.

This conjecture would give the optimal measurement scaling $M=O_\delta(K\log(N/K))$, improving the paper's bound, which scales like $K\log^2K\log N$. It is presented as a possible strengthening of the Legendre-symbol construction and remains open in the supplied text.