Shangguan's generic Vandermonde full-rank conjecture

About 4 years old · traced to

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],

∑i∈S∣Ji∣−∣⋃i∈SJi∣⩽(∣S∣−1)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.

References

Primary source

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

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.