Nonsingularity conjecture for t-wise intersection matrices

For a positive integer nn, write [n]={1,,n}[n]=\{1,\ldots,n\}. For subsets I1,,It[n]I_1,\ldots,I_t\subseteq[n], define their weight by

wt(I1,,It)=i=1tIii=1tIi,\operatorname{wt}(I_1,\ldots,I_t)=\sum_{i=1}^t|I_i|-\left|\bigcup_{i=1}^t I_i\right|,

and write wt(IJ)=wt(Ij:jJ)\operatorname{wt}(I_J)=\operatorname{wt}(I_j:j\in J) for J[t]J\subseteq[t]. Let Mk,(I1,,It)M_{k,(I_1,\ldots,I_t)} denote the associated tt-wise intersection matrix. Nonsingularity conjecture for t-wise intersection matrices. If t3t\geq3, the subsets I1,,It[n]I_1,\ldots,I_t\subseteq[n] satisfy

wt(IJ)(J1)k\operatorname{wt}(I_J)\leq (|J|-1)k

for every nonempty J[t]J\subseteq[t], and

wt(I[t])=(t1)k,\operatorname{wt}(I_{[t]})=(t-1)k,

then Mk,(I1,,It)M_{k,(I_1,\ldots,I_t)} is nonsingular over every finite field. This conjecture is the key algebraic condition underlying the capacity conjecture for Reed–Solomon list decoding, but remains unresolved.

Sources & referencesView supporting material

Primary source

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo and Mary Wootters, “Improved List-Decodability of Reed–Solomon Codes via Tree Packings”, arXiv:2011.04453 (2023).

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.