Density of constant radius normal binary covering codes

A binary code with covering radius R   is a subset CC of the hypercube Qn={0,1}nQn={0,1}n such that every x∈Qnx∈Qn is within Hamming distance R   of some codeword c∈Cc∈C, where R   is as small as possible. For a fixed coordinate i∈[n]i∈[n], define Cb(i) to be the set of codewords with a b in the i  th position. Then CC is normal   if there exists an i∈[n]i∈[n] such that for any v∈Qnv∈Qn, the sum of the Hamming distances from vv to C0(i) and C1(i) is at most 2R+12R+1. We newly define what it means for an asymmetric covering code to be normal, and consider the worst-case asymptotic densities ν*(R)ν*(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 ν*(R)⩽e(RlogR+logR+loglogR+4) and ν+*(R)⩽e(RlogR+logR+loglogR+4)ν+*(1), giving evidence that minimum size constant radius covering codes could still be normal.