Minimum sparsity of $S$-decoding polynomials

Ghasemi and Kopparty proved that $k+1$ nonzero coefficients are necessary when the modulus is a product of $k$ distinct primes, and posed the matching-construction problem. The new work gives a conditional affirmative answer for every constant $k$.

Known results

• Efremenko obtained sparsity $3$ for $m=7\times 73=511$ over $\mathbb{F}_{512}$.
• Later work achieved sparsity $3^{k/2}$ for suitable products of an even number $k$ of primes, assuming a number-theoretic conjecture.
• Ghasemi and Kopparty established the lower bound $k+1$.

Conditional construction, July 2026

Assuming Conjecture $1.1$, the paper constructs, for every constant $k$, a suitable product $m$ of $k$ primes and an $S^{*}_{m}$-decoding polynomial with exactly $k+1$ nonzero coefficients. It also claims unconditional validity for all $s\le 15$, though the transcript does not specify its precise relation to $k$. The theorem and proof are reported as discovered by OpenAI’s GPT-5.5 Pro; the mathematical claim remains conditional and independently unverified.

Current status (as of July 2026): The lower bound is matched conditionally for every constant $k$ and reportedly unconditionally in a limited parameter range, but the unrestricted minimum-sparsity question remains open.