Is primality essential in Varshamov's bound?

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.