When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?

The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate ² has relative distance at least 12 - O () with high probability. However, it is a major challenge to construct explicit codes with similar parameters. One hope to derandomize the Gilbert--Varshamov construction is with code concatenation: We begin with a (hopefully explicit) outer code Cₒut over a large alphabet, and concatenate that with a small binary random linear code Cᵢn. It is known that when we use independent small codes for each coordinate, then the result lies on the GV bound with high probability, but this still uses a lot of randomness. In this paper, we consider the question of whether code concatenation with a single random linear inner code Cᵢn can lie on the GV bound; and if so what conditions on Cₒut are sufficient for this. We show that first, there do exist linear outer codes Cₒut that are "good" for concatenation in this sense (in fact, most linear codes codes are good). We also provide two sufficient conditions for Cₒut, so that if Cₒut satisfies these, Cₒut Cᵢn will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes Cₒut.