15
$\begingroup$

Let $v_q(n,r)=\sum_{i=0}^r \binom{n}i (q-1)^i$ denote a number of points in a ball of radius $r$ in the Hamming metric on the cube $\Sigma^n$, where $|\Sigma|=q$. What is the maximal number of points in $\Sigma^n$ with mutual distances at least $d$ (later: $d$-distant point sets)? Gilbert's bound says that we may find $M$ such points if $(M-1)\cdot v_q(n,d-1)< q^n$: add points one by one, while we have less than $M$ points, the $(d-1)$-balls centered at them do not cover $\Sigma^n$ and we may add another point. If $q$ is a power of prime, Varshamov's bound improves the previous result by claiming that we may find $q^k$ $d$-distant points whenever $q^{k-1}v_q(n,d-1)<q^n$. For the proof, we identify $\Sigma$ with a finite field and consider the maximal subspace $X$ of $\Sigma^n$ into which all points are $d$-distant. If $\dim X\geqslant k$, we are done, else there exists a point $v$ not covered by $(d-1)$-balls centered at elements of $X$, and the span of $X$ and $v$ is larger $d$-distant subspace.

My question is: is Varshamov's bound true if we do not require that $q$ is a prime power (say, for $q=6$)? This often happens and always does astonish me when arithmetical properties like being prime powers are crucial for purely combinatorial or topological claims, and I wonder what is the situation in this particular case.

$\endgroup$
8
  • $\begingroup$ What is $\Sigma$? A cyclic group? Another abelian group? $\endgroup$
    – Will Sawin
    Jun 11, 2017 at 19:09
  • $\begingroup$ @WillSawin Any set of cardinality $q$. We need no other structure for defining Hamming metric on $\Sigma^n$. $\endgroup$ Jun 11, 2017 at 20:28
  • $\begingroup$ In my answer below I remark that perhaps a more natural question is whether Varshamov's bound holds for non-linear codes. $\endgroup$ Jun 12, 2017 at 8:39
  • $\begingroup$ @Dima what do you mean? The claim "linear code exists" implies a claim "code exists". $\endgroup$ Jun 12, 2017 at 9:05
  • 1
    $\begingroup$ Gilbert bound is true if the code is not linear, but Varshamov bound is true for linear codes. also, binary cyclic codes are better than the Gilbert- Varshamov bound for lengths up to 1023. For the case $q=6$, we must analyse $Z_6$ codes at the first step. $\endgroup$
    – Shahrooz
    Jun 12, 2017 at 10:39

3 Answers 3

9
$\begingroup$

The analogue of the Varshamov inequality need not hold for instance for $\lvert\Sigma\rvert=q=6$: For $n=4$ and $d=3$ it would give a code $C\subseteq\Sigma^4$ with $d(C)\ge3$ and $\lvert C\rvert=36$. But such a code gives a pair of orthogonal Latin squares of order $6$, which is known not to exist (by Tarry's negative answer to Euler's thirty-six officers problem).

(The construction of the orthogonal pair $A,B$ is as follows: Since $d(C)\ge3$, the map $C\to\Sigma^2$, $(i,j,a,b)\mapsto(i,j)$ is bijective. For $(i,j,a,b)\in C$ let $A$ and $B$ have entry $a$ and $b$ in the $i$-th row and $j$-th column, respectively.)

$\endgroup$
2
$\begingroup$

Interesting question.

I hope I haven't misunderstood it but the discussion on p. 315 of Handbook of Coding Theory, Vol. 1, by Brouwer seems to imply that a finite field is necessary since it relies on adding a column to the parity check matrix that is not a linear combination of fewer than $d-1$ columns, so the argument is over a vector space. Having a module over a ring might be problematic in terms of applying this argument in general.

See also the short note "Lengthening and the Gilbert-Varshamov bound" by Edel and Bierbrauer here where the techniques used include orthogonal arrays, but those array parameters come from guarantees on dual distances of codes, thus again rely on vector spaces. I don't know whether there are generic orthogonal array constructions that can be substituted in their place.

$\endgroup$
2
  • 2
    $\begingroup$ It is essential for this particular argument, but is it essential to the claim? $\endgroup$ Jun 12, 2017 at 6:35
  • $\begingroup$ I am not sure whether it is. $\endgroup$
    – kodlu
    Jun 13, 2017 at 2:37
2
$\begingroup$

This is more of a terminological note than an answer.

Historically, Gilbert bound is often called Gilbert-Varshamov bound, adding to the confusion. (Wikipedia articles on it are quite messy too). Gilbert bound does not need linearity of the code (i.e. the collection $C$ of points in $\Sigma^n$ with minimal pairwise Hamming distance $d$), whereas Varshamov's bound does.

IMHO it does not really matter whether $q$ is a prime power; what does matter is whether the minimal distance $d$ code in question is linear or not (i.e. whether $C$ is an affine subspace of $\mathbb{F}_q$ or not). I won't be surprised if a nonlinear code beating Varshamov bound exists. Needless to say, all the codes for $q$ not a prime power are non-linear.

Also there is a closely related asymptotic Gilbert-Varshamov bound. Codes beating the latter are known to exist since the classical work by M.A. Tsfasman, S.G. Vlăduts,Th. Zink and M.A. Tsfasman, where a "layman" exposition (in Russian) of the result it presented. (A translation of the latter is in Problems of Information Transmission, 1982, 18:3, 163–166).

Due to this terminology clash, finding the relevant references is very hard indeed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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