Suppose $C \subset \lbrace 0,1\rbrace^{n}$ is a binary code with distance $\delta * n$, for $1/2 < \delta < 1$. Can $C$ be arbitrarily large (if I allow n to be arbitrarily large)? Note that the Hadamard code gives you $\delta = 1/2$.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
No. If we take $\{1/\sqrt n,1/\sqrt n\}^n$ instead of $\{0,1\}^n$, the problem reduces to asking if we can have many unit vectors $v_j$ with pairwise scalar products $\gamma$ or less where $\gamma>0$ is a fixed number. But if we have $N$ such vectors, then the square of the norm of their sum is at most $N\gamma N(N1)$. Since this square must be nonnegative, we get $N1\le\gamma^{1}$ regardless of the dimension. 


Gama doesn't have to be negative, in fact if delta is smaller than 1/2 gamma will be positive. It's known for Hadamard codes that arbitrarily large codes exist, and it seems intuitive that if the distance between vectors should be smaller then large codes should exist still, but I don't have a proof 

