Shangguan's generic Vandermonde full-rank conjecture

From papers

Let [t]={1,,t}[t]=\{1,\ldots,t\} and let J1,,Jt[n]J_1,\ldots,J_t\subseteq[n] satisfy, for every S[t]S\subseteq[t],

iSJiiSJi(S1)k.\sum_{i\in S}|J_i|-\left|\bigcup_{i\in S}J_i\right|\leqslant (|S|-1)k.

Assume also that the corresponding inequality is an equality for S=[t]S=[t]. Let GG be a generic (n,k)(n,k)-Vandermonde matrix, and let MG,(J1,,Jt)M_{G,(J_1,\ldots,J_t)} be the matrix defined in the source from GG and these subsets.

Shangguan's full-rank conjecture. The matrix MG,(J1,,Jt)M_{G,(J_1,\ldots,J_t)} has full column rank.

The conjecture is formulated as a rank criterion whose resolution would imply that generic Reed–Solomon codes achieve list-decoding capacity. The source does not provide evidence of a resolution, so its status is open.

Progress summary

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

Sources & referencesView supporting material

Primary source

Joshua Brakensiek, Sivakanth Gopi and Visu Makam, “Generic Reed-Solomon Codes Achieve List-decoding Capacity”, arXiv:2206.05256 (2024).

Solutions 0

No solutions have been posted yet.