Nonsingularity conjecture for t-wise intersection matrices

At least 5 years old · documented by

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=1t∣Ii∣−∣⋃i=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:j∈J)\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 t≥3t\geq3, the subsets I1,…,It⊆[n]I_1,\ldots,I_t\subseteq[n] satisfy

wt⁡(IJ)≤(∣J∣−1)k\operatorname{wt}(I_J)\leq (|J|-1)k

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

wt⁡(I[t])=(t−1)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.

References

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.