Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

2 Answers 2

up vote 13 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|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|improve this answer

Your Answer

 
discard

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.