MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
up vote 14 down vote accepted

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(N-1)$. Since this square must be non-negative, we get $N-1\le\gamma^{-1}$ regardless of the dimension.

share|cite|improve this answer

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

share|cite|improve this answer
When $\delta=1/2,$ the $\gamma$ in the answer is zero. – kodlu May 20 '15 at 7:03
Moreover, if $\delta<1/2$ then the OP's stated requirement is not satisfied. As for Hadamard codes, their size is $M=\log_2(n)$ which is not large at all, but logarithmic in the length. – kodlu May 20 '15 at 7:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.