Goppa's conjecture on the binary Gilbert–Varshamov bound

About 20 years old · traced to

For a binary linear code C[n,k,d]C[n,k,d], let R:=knR:=\frac{k}{n} be its information rate and let δ:=dn\delta:=\frac{d}{n} be its relative minimum distance. The Gilbert–Varshamov bound is the lower bound

α2(δ)≥1−xlog⁡2(1)+xlog⁡2(x)+(1−x)log⁡2(1−x),\alpha_2(\delta) \geq 1-x\log_2(1)+x\log_2(x)+(1-x)\log_2(1-x),

where α2(δ)\alpha_2(\delta) denotes the asymptotic achievable rate at relative minimum distance δ\delta.

Goppa's conjecture. The Gilbert–Varshamov bound is tight in the binary case; equivalently, the asymptotic achievable rate equals the Gilbert–Varshamov bound.

This conjecture asserts that the classical Gilbert–Varshamov lower bound gives the exact asymptotic rate–distance tradeoff for binary linear codes. The source provides no evidence of resolution, so its status is open.

References

Primary source

Nigel Boston and Jing Hao, “The Weight Distribution of Quasi-quadratic Residue Codes”, arXiv:1705.06413 (2017).

Additional references

2 papers in this index state this conjecture (2006–2017). The statement above is taken from the most recent of them; the others are arXiv:math/0609562.

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.