Density of normal binary covering codes

Original · EN

A binary code with covering radius R is a subset C of the hypercube Qₙ={0,1}ⁿ such that every x∈ Qₙ is within Hamming distance R of some codeword c∈ C, where R is as small as possible. For a fixed coordinate i∈[n], define C(b,i), for b=0,1, to be the set of codewords with a b in the ith position. Then C is normal if there exists an i∈[n] such that for any v∈ Qₙ, the sum of the Hamming distances from v to C(0,i) and C(1,i) is at most 2R+1. We newly define what it means for an asymmetric covering code to be normal, and consider the worst case asymptotic densities ν*(R) and ν*+(R) of constant radius R symmetric and asymmetric normal covering codes, respectively. Using a probabilistic deletion method, and analysis adapted from previous work by Krivelevich, Sudakov, and Vu, we show that both are bounded above by e(R R + R + R+4), giving evidence that minimum size constant radius covering codes could still be normal.