On the Existence of Asymptotically Good Linear Codes in Minor-Closed Classes
Peter Nelson, Stefan H. M. van Zwam · IEEE Transactions on Information Theory · 2015
Let C = (C1, C2, ...) be a sequence of codes such that each Ciis a linear [ni, ki, di]-code over some fixed finite field F, where niis the length of the code words, kiis the dimension, and diis the minimum distance. We say that C is asymptotically good if, for some ε > 0 and for all i ∈ ℤ>0, we have ni≥ i and min(ki/ni, di/ni) ≥ ε. Sequences of asymptotically good codes exist. We prove that if C is a class of GF(pn)-linear codes (where p is prime and n ≥ 1), closed under puncturing and shortening, and if C contains an asymptotically good sequence, then C must contain all GF(p)-linear codes. Our proof relies on a powerful new result from matroid structure theory.