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$.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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
answered Jan 31, 2010 at 14:49
-
$\begingroup$ When $\delta=1/2,$ the $\gamma$ in the answer is zero. $\endgroup$– kodluCommented May 20, 2015 at 7:03
-
$\begingroup$ 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. $\endgroup$– kodluCommented May 20, 2015 at 7:17