Proof that a random linear code is "good" As we know Hadamard code is an extremly usefull code in computer science and maths.
We wanna say something interesting about random linear codes.
Let $A \in \{0,1\}^{n\times k}$ a random matrix.
Lets define the linear code $ C(x) = Ax $ for $ x \in \{0,1\}^k$.
How can we show that with high probability (lets say $0.99$) C has a relative distance of at least $1/2 - \epsilon$ for some $\epsilon > 0$, meaning a random code is almost as good as Hadamard code.
A direction i was going with was estimating $Pr[\frac {hw(C(x))} n \lt 1/2 - \epsilon] $ (where hw is the hamming distance function) and from there using union bound to bound $min(hw(C(x)) $ foreach $x \ne 0$ but i seem to get stuck.
Anyone has a better idea?
 A: Note that Hadamard code (first order Reed-Muller) is not good in the sense that its rate goes to zero.
Let $G=[\mathbf{g}_1|\cdots|\mathbf{g}_k]$ be the generator matrix with $\mathbb{g}_i \in \mathbb{F}_2^n$ chosen independently and uniformly at random. If any of the columns are nonzero just draw a replacement at random. Each codeword in this linear code $C$ with parameters $[n,k]$ is given by
$$
c(m)=\sum_{i=1}^k m_i \mathbf{g}_i,\quad m_i \in \mathbb{F}_2,1\leq i\leq k.
$$
The $2^k$ codewords (being chosen uniformly at random and independently) form a random incidence process where we say that the code is $d-$good if the Hamming weight of all the codewords are $\geq d.$
The volume of the Hamming ball with radius $d-1$ obeys
$$
\#\{x \in \mathbb{F}_2^n: w_H(x)\leq d-1\}=\sum_{j\leq d-1} \binom{n}{j}\leq 2^{n [H_2(d/n)+o(1))]},
$$
for $n$ large enough. See for example the answer to this question. Those bounds are on a single binomial coefficient but the sums of binomial coefficients are superincreasing for $j<n/3,$ i.e.,
$$
\sum_{j\leq d} \binom{n}{j}\leq \binom{n}{j+1}
$$
so I will restrict the answer to Hamming distances less than $n/3$ for simplicity. From the volume bound above we get that for each codeword $c$ in $C$ the probability that its Hamming distance is $\leq d-1$ is upper bounded by
$$
P_{bad}(c)=\frac{\#\{x \in \mathbb{F}_2^n: w_H(x)\leq d-1\}}{2^n}\leq 2^{-n(1-H_2(\delta)-o(1))},\quad \delta:=d/n.
$$
Taking $n$ large enough to ignore the $o(1)$ in the exponent, we have that the probability that the code has Hamming distance at least $d$ is
$$
(1-P_{bad}(c))^{2^k}\geq\left(1-\frac{1}{2^{n(1-H_2(\delta))}}\right)^{2^k}.
$$
Now, note that for $a>0,b>0$ going to infinity together
$$
\left(1-\frac{1}{a}\right)^b=\left[\left(1-\frac{1}{a}\right)^a\right]^{b/a}\sim \exp(-b/a)
$$
So as long as $b/a>0$ we have $\exp(-b/a)>0.$
Fix $\epsilon>0,$ and choose the rate $k$ such that $$k=n(1-H_2(\delta)-\epsilon)$$
where you can round $k$ down if needed. Then the code we obtained randomly has
Hamming distance $\geq d$ with fixed positive probability since the probability it has distance $\leq d-1$ is itself strictly below $1.$
