Bounded Hamming distance

Question

Definition 1. For each $n\in\mathbb{Z}^+$, the $n$-dimensional Hamming cube is the set of ordered $n$-tuples of $\lbrace 0,1\rbrace$, denoted by $\lbrace 0,1\rbrace ^n$.

Definition 2. The binary operation that turns $\lbrace 0,1\rbrace ^n$ into a group is $\oplus$ (XOR), which is bitwise addition reduced modulo $2$.

Definition 3. The sum of the digits of an element of $\lbrace 0,1\rbrace ^n$ is its Hamming weight. The Hamming weight of the XOR of two elements is the Hamming distance $h$ between them. In fact, $h$ is a metric on $\lbrace 0,1\rbrace ^n$.

Question. Given integers $0\le a\le b\le n$, what is known regarding maximal subsets $S$ of $\lbrace 0,1\rbrace^n$ such that: $\forall x,y\in S: a\le h(x,y)\le b$ ? Specifically, is anything known about bounds on cardinality, or exact cardinality, or even construction of these maximal sets?

I expect that the full answer is not known but I would be happy to read replies about, or receive direction toward resources for, special cases. For example, if $n$ is even and if $a=b=\frac{n}{2}$, then we turn to Hadamard matrices.

Answer 1

I think you're assuming $x \not= y$ when you say "for any $x, y \in S$." In any case, your question seems like a mix of coding theory and design theory.

If you find the case when $a = b = \frac{n}{2}$ interesting, a $q$-ary code $\mathcal{C} \subset \mathbb{F}_q^n$ is said to be equidistant if for any pair $\boldsymbol{c}, \boldsymbol{c}' \in \mathcal{C}$, $\boldsymbol{c}\not=\boldsymbol{c}'$, of distinct codewords, the Hamming distance $h(\boldsymbol{c}, \boldsymbol{c}')$ is $d$. Your example is the special case when the code is binary and of equidistance $d = \frac{n}{2} (= a = b)$. We focus on the binary case for the moment.

Any equidistant code $\mathcal{C}$ can be transformed into a constant-weight equidistant code $\mathcal{D} \subset \mathbb{F}_2^n$ of size $\vert \mathcal{C} \vert -1$, where $\operatorname{wt}(\boldsymbol{d}) = \operatorname{wt}(\boldsymbol{d}')$ for any $\boldsymbol{d}, \boldsymbol{d}' \in \mathcal{D}$ (see the references given below (or some references therein) for the proof if you need it). Hence, essentially we only need to consider the case when a code is both constant-weight and equidistant. Let $\operatorname{ex}(n,d,w)$ be the number of codewords of a largest binary code of lenght $n$, equidistance $d$, and constant-weight $w$ (i.e., no other constant-weight, equidistant code of the same parameters has more codewords). Then the classical result by Stinson and van Rees states that

$$\operatorname{ex}(4k+1,2k,2k) \leq 4k$$ with equality if and only if $k=\frac{u^2+u}{2}$ for some integer $u$ if there exists a $(2u^2+2u+1, u^2, \frac{u^2-u}{2})$ symmetric balanced incomplete block design (BIBD). They also proved that

$$\operatorname{ex}(4k+1,2k,2k) \geq 4k-1$$ if there exists a $(4k-1,2k,k)$-SBIBD. If you don't know what symmetric designs are, you can find the definition in your favorite design theory textbook or, better yet, the original article

D. R. Stinson, G. H. J. van Rees, The equivalence of certain equidistant binary codes and symmetric BIBDs, Combinatorica, 4 (1984) 357-362

and also another article

J. H. van Lint, On equidistant binary codes of lengthn $=4k+1$ with distanced $=2k$, Combinatorica, 4 (1984) 321-323) in the same issue.

There are more interesting direct connections between codes and designs when it comes to equidistant codes, and this is true for the non-binary case as well. If I remember correctly, the book chapter

V. D. Tonchev, `Codes and designs', in Handbook of Coding Theory Vol II, edited by V. S. Pless and W. C. Human (North Holland, Amsterdam, 1998) Chap. 15, pp. 1229-1268

has a section for equidistant codes and their relations to combinatorial designs. Basically, the optimal $q$-ary equidistant codes are equivalent to resolvable designs in the language of design theory.

Now getting back to the binary case, if you're also interested in the case when there's a slight gap between $a$ and $b$, you can still employ design theory. In fact, such codes achieving the Johson bound can be constructed rather easily for $a+1 = b$ by using almost difference sets and whatnot straightforwardly. Basically, you try to construct a design that is nearly symmetric but not quite. Almost difference sets are quite important for synchronization and many other problems. You should be able to find many results if you look around. You can widen the gap a bit more, too. I'll explain how in the remainder of this post by giving a construction for the case when $a+2=b$ (Basically the same idea also works for $a+1=b$ etc.).

For instance, a Steiner $2$-design of order $v$ and block size $k$ is a pair $(V, \mathcal{B})$ of finite sets, where $\mathcal{B}$ is a set of $k$-subsets of $V$ of cardinality $\vert V \vert = v$ such that any distinct pair $a, b \in V$ is contained in exactly one element of $\mathcal{B}$. If you regard each element $B \in \mathcal{B}$ as the support of a codeword of a binary code of length $v$, you get a code in which any pair of distinct codewords is of distance $2k$ or $2(k-1)$. This code attains the Johnson bound with equality because a Steiner $2$-design packs all pairs into the elements of $\mathcal{B}$ without duplicates. Wilson's Fundamental Existence Theory asserts that you can construct Steiner $2$-designs for all sufficiently large orders (as long as certain necessary conditions by a counting argument are met). So it's a good source of optimal examples of $a+2=b$. This idea generally works for packings, Steiner $t$-designs, and the like, so you can get more examples or increase the gap between $a$ and $b$ more. Since there is a well-developed existence theory for these kinds of combinatorial designs, you can prove the existence of optimal examples and actually construct them.

By the way, the latest issue of the Journal of Combinatorial Theory A contains a paper on the asymptotic existence of $2$-designs, and this result can be directly used exactly the same way I explained above for your purpose:

Y. M. Chee, C. J. Colbourn, A. C. H. Ling, R. M. Wilson, Covering and packing for pairs, J. Combin. Theory Ser. A 120 (2013) 1440–1449

Edit: Oops, I forgot to mention this, but when a binary code is not equidistant, you may not be able to turn it into a constant-weight one with one less codeword. So the latter half of this post is assuming that the actual bound is probably the same or not far away from the Johnson bound (which is a bound on the number of codewords of a constant-wight code) if $a$ and $b$ are pretty close. Also, I'm not familiar with the case when $b$ is large (compared to $a$). If you impose a condition such as the code must be linear and have a pair of codewords of distance $b = n$, then I think you can find results if you google "linear self-complementary codes."

Answer 2

My previous answer is already too long, and this is too much to include in a comment. But I found a paper that studies the problem you asked here:

R. M. Roth, G. Seroussi, Bounds for binary codes with narrow distance distributions, IEEE Transactions on Information Theory 58 (2007) 2760-2768

It seems a lot of interesting things are proved here. Among others, one of their propositions states that

Let $\mathcal{C}$ be an $(n,M,d)$ binary code of length $n$ and minimum distance $d$ with exactly $M$ codewords. Assume that the largest Hamming distance between two codewords $\boldsymbol{c}, \boldsymbol{c}' \in \mathcal{C}$ is $d_{\text{max}}$. Denote by $d_a$ and $d_g$ the arithmetic and geometric means respectively, of $d$ and $d_{\text{max}}$, i.e.,

$$d_a = \frac{d+d_{\text{max}}}{2} \quad \text{and} \quad d_g = \sqrt{dd_{\text{max}}}.$$ Then

$$1-\frac{1}{M} \leq \begin{cases} \left(1-\frac{1}{n}\right)\left(\frac{d_a}{d_g}\right)^2 \quad &\text{if }\ 2d_a \not\in \{n+1, n+2\},\\\\ \frac{n}{d_g^2}\left(d_a- \frac{n+1}{4}\right) &\text{if }\ 2d_a \in \{n+1, n+2\}.\end{cases}$$

They also study equidistant codes, constant-weight codes, and self-complementary codes.

If you don't have access to the journal, a preprint is available on the first author's website:

http://www.cs.technion.ac.il/~ronny/PUB/2007/variance.pdf

Answer 3

It seems, especially in the light of @Yuichiro answer, that it makes sense for me to share here with you my original constant weight codes, which I have discovered in 1977-78 but just absolutely couldn't believe that they were not known. Only years later I got clear evidence that they were still unknown to the public (only then I posted them on pl.sci.matematyka, and I informed about them Neil Sloan and his co-maintainer of the ECC tables--both worked at Bell Labs at the time; I didn't get any feedback from them though).

My construction mostly doesn't care about the finiteness. Let $K$ be an arbitrary field, let $L$ be an arbitrary proper subfield of $K$.   Let   $P(K)\ \ P(L)$   be their projective lines (1-dim projective spaces); we may assume that   $P(L)\subset P(K)$ -- it's a harmless abuse. Let   $G\ H$   be the projective groups of   $P(K)\ P(L)$   respectively. Let   $\Gamma := \Gamma(K\ L)$   be the family of all images of   $P(L)$   under the projective maps from   $G$:

$$\Gamma := \{f(P(L)) : f\in P(K)\}$$

That's it. We may call the members of   $\Gamma$   to be circles. For every three different points   $x\ y\ z\in P(K)$   there exists exactly one circle which contains all three of them. When   $K$   is a finite field then   $\Gamma$   is the best possible (even perfect or similar terminology) constant-weight code--instead of considering the binary sequences we deal equivalently with subsets of $P(K)$, or here simply with circles.

Let's say that   $|K|=p^n$   and   $|L|=p^m$,   where   $p$   is a prime, and   $0 < m < n$   are two natural numbers. Thus   $w:=p^m+1$, while @sams'   $n$   is   $p^n+1$   here  (sorry for that). The minimal distance between the codes is   $a := 2\cdot (p^m-1)$. And that's what is important for the standard theory, while the maximal distance between the codes is   $b:=2\cdot (p^m+1) = a+4$.

Of course $$|\Gamma|\ \ =\ \ \frac{\binom \nu 3}{\binom \mu 3}$$ where $$\nu := p^n+1\qquad\quad \mu=p^m+1$$

The property of circles (exactly one circle passing through any three different points) follows from the exact 3-transitivity of $G$, and the identification   $H\subset G$.

Edit: I rushed. Of course $p^n$ must be a power of $p^m$, i.e. $n$ must be a multiple of $m$.