MINIMUM AVERAGE DISTANCE

SUBSETS IN THE HAMMING CUBE

André Kündgen

August 12, 1999

Abstract. In 1977, Ahlswede and Katona proposed the following isoperimetric problem: find a set S of n points in {0, 1}^{k} whose average Hamming distance is minimal – or equivalently find an n-vertex subgraph of the hypercube Q_{k} whose average distance is minimal.

We report on some recent results and conjecture that S can be chosen to be the set of all points in {0, 1}^{k} that are distance at most r from some point c ∈ ℝ^{k}. We show that these “discrete balls” include all known good constructions and we provide additional evidence supporting the conjecture.

1. Discrete isoperimetric problems

The classic isoperimetric problem consists of showing that in Euclidean space ℝ^{k} (originally only for k = 2), the (convex) body with smallest surface area, given a fixed volume, is the sphere. See Santaló [S] for a comprehensive book on related geometric questions.

The discrete isoperimetric problem (solved by Harper [H] and Katona [Ka1]) asks the corresponding question for the Hamming space {0, 1}^{k}: find a set of n points, so that the boundary is minimal. Not surprisingly the answer is the Hamming sphere. For a short proof see Frankl and Füredi [FF]. The survey of Bezrukov [Bz] discusses various discrete isoperimetric problems.

In 1918, Blaschke [Bl] solved another isoperimetric problem in ℝ^{2} by showing that the convex body of smallest mean distance, given a fixed volume, is the disk. In 1977, Ahlswede and Katona [AK] proposed the discrete analog of Blaschke’s problem: find a set S of n points in Hamming space {0, 1}^{k} whose average Hamming distance is minimal. Or equivalently, find an n-vertex subgraph of the hypercube Q_{k} with minimal average distance. This problem has been recently investigated by several authors [AA, AS, F, FWY, XF]. Up to a constant factor the Hamming sphere achieves the minimum, but it is not necessarily best possible. It is the aim of this paper to suggest an analog of the sphere for the discrete case: the discrete ball. We conjecture that the optimum is always achieved by a discrete ball and we provide some supporting evidence.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 05D05, 05C12, 90C05.

Key words and phrases. discrete isoperimetric problem, minimum average distance, discrete ball, hamming distance, hypercube.

2. Definitions and known results

Definition 1. The Hamming distance between two points x, y ∈ {0, 1}^{k}, denoted by d(x, y), is the number of coordinates in which they differ,

d(x, y) := ∑_{1≤i≤k} |x_{i} − y_{i}|.

The weight of a point x ∈ {0, 1}^{k} is its number of non-zero entries, w(x) := d(0, x), where 0 is the zero vector. The distance-sum of a set S ⊂ {0, 1}^{k} is given as

d(S) := ∑\{d(x, y) : \{x, y\} ∈ \binom{S}{2}\}.

The weight of a coordinate i of a set S is the number of ones in that coordinate among the points in S

w_{i}(S) := ∑_{x∈S} x_{i}.

A fundamental observation is that

(1)  d(S) = ∑_{i=1}^{k} w_{i}(S)(|S| − w_{i}(S)).

Indeed, both sums count the number of triples (x, y, i) with x_{i} = 1 and y_{i} = 0.

The problem of Ahlswede and Katona [AK] amounts to determining, for all 2 ≤ n ≤ 2^{k},

f(n, k) := min{d(S) : S ⊂ {0, 1}^{k}, |S| = n}.

Any set S achieving f(n, k) will be called extremal. In general, the structure of extremal sets seems elusive since there are two different configurations that are optimal in a number of cases: the (Hamming) sphere and the (sub)cube. We will define both notions for general n.

Definition 2. The Hamming sphere of radius r ≥ 0 centered at x ∈ {0, 1}^{k} is defined as

B(x, r) = {y ∈ {0, 1}^{k} : d(x, y) ≤ r}.

Every set S ⊂ {0, 1}^{k}, for which there is a t such that B(0, t − 1) ⊂ S ⊂ B(0, t) will be called a (generalized Hamming) sphere. The generalized Hamming sphere in which we pick the lexicographically smallest vectors for weight t will be denoted by B_{k}(n).

The set consisting of the n lexicographically smallest vectors in {0, 1}^{k} is the subcube Q_{k}(n). We frequently drop the subscripts in B_{k}(n) and Q_{k}(n).

For example Q_{5}(5) = {00000, 00001, 00010, 00011, 00100} is not a sphere since it contains a vector of weight 2, but misses some vectors of weight 1. It can be seen that B_{k}(n) = Q_{k}(n) if and only if n ≤ 3 or n ≥ 2^{k} − 3. Note that if we denote the binary expansion of m by b(m), that is m = ∑_{i=1}^{k} b(m)_{i}2^{k−i}, then Q(n) = {b(0), b(1), …, b(n − 1)}.

Although there seem to be no closed formulas for d(B_{k}(n)) or d(Q(n)), d(Q(n)) can be computed efficiently with the following recurrence relation.

Proposition 1. d(Q(n)) = ⌊n^{2}/4⌋ + 2d(Q(⌊n/2⌋)) + 2d(Q(⌈n/2⌉)), so that

d(Q(n)) = \frac{1}{4}n^{2} lg n + O(n^{2}),

where lg denotes the base 2 logarithm.

Proof. If we abbreviate w_{i}(Q(n)) = q(n), then

[q(⌊n/2⌋) + q(⌈n/2⌉)][n − q(⌊n/2⌋) − q(⌈n/2⌉)]
= q(⌊n/2⌋)[⌊n/2⌋ − q(⌊n/2⌋)] + q(⌊n/2⌋)[⌈n/2⌉ − q(⌈n/2⌉)]
+ q(⌈n/2⌉)[⌊n/2⌋ − q(⌊n/2⌋)] + q(⌈n/2⌉)[⌈n/2⌉ − q(⌈n/2⌉)]
= 2q(⌊n/2⌋)[⌊n/2⌋ − q(⌊n/2⌋)] + 2q(⌈n/2⌉)[⌈n/2⌉ − q(⌈n/2⌉)].

The last equality clearly holds if q(⌈n/2⌉) = q(⌊n/2⌋). Otherwise we observe that we must have q(⌈n/2⌉) = q(⌊n/2⌋) + 1 and ⌈n/2⌉ = ⌊n/2⌋ + 1, so that the equation also follows easily. Furthermore, note that

\begin{aligned}\{x ∈ \{0, 1\}^{k−1} : (x_{1}, x_{2}, …, x_{k−1}, 1) ∈ Q_{k}(n)\} & = Q_{k−1}(⌊n/2⌋), and \\ \{x ∈ \{0, 1\}^{k−1} : (x_{1}, x_{2}, …, x_{k−1}, 0) ∈ Q_{k}(n)\} & = Q_{k−1}(⌈n/2⌉), \end{aligned}

so that

d(Q(n)) − ⌊n^{2}/4⌋ = ∑_{i=1}^{k} w_{i}(Q_{k}(n))[n − w_{i}(Q_{k}(n))] − ⌊n^{2}/4⌋

= ∑_{i=1}^{k−1}[w_{i}(Q_{k−1}(⌊n/2⌋)) + w_{i}(Q_{k−1}(⌈n/2⌉))]×

× [n − w_{i}(Q_{k−1}(⌊n/2⌋)) − w_{i}(Q_{k−1}(⌈n/2⌉))]

= 2 ∑_{i=1}^{k−1} q(⌊n/2⌋)[⌊n/2⌋ − q(⌊n/2⌋)] + 2 ∑_{i=1}^{k−1} q(⌈n/2⌉)[⌈n/2⌉ − q(⌈n/2⌉)]

= 2d(Q(⌊n/2⌋)) + 2d(Q(⌈n/2⌉)).

For the asymptotics observe that d(Q(n)) ≤ ⌊n^{2}/4⌋⌈lg n⌉ is immediate since at most ⌈lg n⌉ of the w_{i}(Q(n)) are nonzero. So it suffices to prove that for n ≥ 1, d(Q(n)) ≥ (n^{2}/4) lg n. This is true for n ≤ 3, so that we can proceed by induction on n. If n ≥ 4 is even, then

d(Q(n)) = \frac{n^{2}}{4} + 4d(Q(n/2)) ≥ \frac{n^{2}}{4} + (n/2)^{2} lg(n/2) = \frac{n^{2}}{4} lg n.

If x > 0 and x + c > 0 then lg(x + c) ≥ lg x + \frac{c}{(x+c) ln 2}, so that for odd n ≥ 5,

d(Q(n)) = \frac{n^{2} − 1}{4} + 2d(Q((n − 1)/2)) + 2d(Q((n + 1)/2))

≥ \frac{n^{2} − 1}{4} + \frac{(n − 1)^{2}}{8} lg((n − 1)/2) + \frac{(n + 1)^{2}}{8} lg((n + 1)/2)

= −\frac{1}{2} + \frac{(n − 1)^{2}}{8} lg(n − 1) + \frac{(n + 1)^{2}}{8} lg(n + 1)

= −\frac{1}{2} + \frac{n^{2} + 1}{8} lg(n^{2} − 1) + \frac{n}{4}(lg(n + 1) − lg(n − 1))

≥ −\frac{1}{2} + \frac{n^{2} + 1}{8}(lg n^{2} − \frac{1}{(n^{2} − 1) ln 2}) + \frac{n}{4}(\frac{2}{(n + 1) ln 2})

= \frac{n^{2}}{4} lg n + \frac{lg n}{4} − \frac{1}{2} + \frac{4n(n − 1) − (n^{2} + 1)}{8(n^{2} − 1) ln 2} ≥ \frac{n^{2}}{4} lg n. □

It is left as an exercise that for any Hamming sphere S, with |S| = n

(2)  \frac{n}{2} w(S) ≤ f(n, k) ≤ d(S) ≤ n w(S),

where w(S) = ∑_{i=1}^{k} w_{i}(S) is a lower bound on the distance sum from a fixed point x, ∑_{y∈S} d(x, y). Hence the Hamming spheres are optimal up to a factor of 2. However, deciding which Hamming sphere has the smallest distance sum seems as hard a problem as determining f(n, k). In general, B_{k}(n) has a small distance sum, but for example if k + 5 ≤ n ≤ 2k then picking the n − (k + 1) vectors of weight 2 so that they all have a 1 in a fixed position is uniquely optimal.

Definition 3. For x ∈ {0, 1}^{k} we let r_{i}(x) = (x_{1}, …, x_{i−1}, 1 − x_{i}, x_{i+1}, …, x_{k}) and say that r_{i}(S) = {r_{i}(x) : x ∈ S} is a zero-one swap in coordinate i. Let r(x) := r_{1}(r_{2}(… (r_{k}(x)) …)) denote the unique vector with d(x, r(x)) = k. For example j⃗ = r(0) is the all ones vector. We define r(S) := r_{1}(r_{2}(… (r_{k}(S)) …)) similarly.

Furthermore, let s_{ij}(x) = y be the vector with y_{i} = x_{j}, y_{j} = x_{i} and y_{ℓ} = x_{ℓ} for ℓ ≠ i, j. The corresponding s_{ij}(S) is a coordinate swap.

We say that two subsets of {0, 1}^{k} are isomorphic if one can be obtained from the other by a sequence of coordinate swaps and zero-one swaps. By (1) isomorphic sets have the same distance-sum.

The first exact values, and extremal configurations, were found by Jaeger, Khelladi and Mollard:

Theorem 1 [JKM]. f(4, k) = d(Q(4)) = 8, f(8, k) = d(Q(8)) = 48, whereas f(n, k) = (n − 1)^{2} is achieved by a sphere for k ≥ n − 1, n ≠ 4, 8. The extremal sets are unique, up to isomorphism, unless 5 ≤ n ≤ 7, when both Q_{k}(n) and B_{k}(n) are extremal.

Jaeger, Khelladi and Mollard where actually interested in a matroid theoretical question suggested by Tarsi [T], who already stated the values for n ≤ 8 in Theorem 1 without proof. Jamshy and Tarsi [JT] established the cases n ≥ 9 by a short inductive argument (omitting the base case), and stated that Alon also obtained Theorem 1 independently. Another independent proof of Theorem 1 can be found in Kündgen [K].

Next, Althöfer and Sillke proved the following isoperimetric inequality

Theorem 2 [AS]. If S ⊂ {0, 1}^{k} and |S| = n, then

d(S) ≥ \frac{n}{4}(n(k + 1) − 2^{k}),

with equality only for S ≃ Q(2^{k−1}), Q(2^{k}).

This yields f(2^{k−1}, k) and again a subcube is the unique optimal configuration. Fu [F] found a different proof of Theorem 2 that yields a slightly better inequality. Xia and Fu improved Theorem 2 in the case that n is odd and very recently Fu, Wei and Yeung improved the bounds even further. Altogether, their theorems imply

Theorem 3 [XF,FWY]. The subcube is extremal if n = 2^{k−1} ± 1, 2^{k−1} ± 2, 2^{k−2} or 2^{k−2} ± 1.

Notice that the previous bounds are only useful when n is at least of size about 2^{k}/k. For the case when n grows rather like c^{k} for some 1 < c < 2, Ahlswede and Althöfer determined f(n, k) asymptotically

Theorem 4 [AA]. For any constant 0 < a < 1/2,

\binom{k}{⌊ak⌋}^{−2}f(\binom{k}{⌊ak⌋}, k) = ka(1 − a) − o(k).

Theorem 4 is asymptotically achieved by taking all x ∈ {0, 1}^{k} with weight w(x) = ⌊ak⌋. Although this suggests that in this range of n suitable Hamming spheres are extremal, this is far from certain.

2. Structure of extremal configurations

Definition 4. A set S ⊂ {0, 1}^{k} is a down-set (respectively up-set) if x ∈ S with x_{i} = 1 (x_{i} = 0) implies that r_{i}(x) ∈ S. Down-sets are also called ideals.

We say S is right-shifted (respectively left-shifted) if x ∈ S with x_{i} = 1 and x_{j} = 0 for some i < j (i > j) implies s_{ij}(x) ∈ S.

If w_{1}(S) ≤ w_{2}(S) ≤ ⋯ ≤ w_{k}(S) ≤ |S|/2, then S is in standard form.

If S is a down-set, then w_{i}(S) ≤ |S|/2 and if S is right-shifted, then w_{i}(S) ≤ w_{i+1}(S), and thus every right-shifted down-set is in standard form. We will first reduce our problem to right-shifted down-sets.

Proposition 2. Let S ⊂ {0, 1}^{k} be an extremal set.

a) S is in standard form if and only if S is a right-shifted down-set.

b) S is isomorphic to a unique S′ in standard form.

c) If S is in standard form with 0 ≤ a_{1} < a_{2} < ⋯ < a_{ℓ} = |S|/2, so that for k_{j} coordinates w_{i}(S) = a_{j} and ∑ k_{j} = k, then there are exactly

\frac{k! 2^{k−k_{ℓ}}}{k_{1}! k_{2}! ⋯ k_{ℓ}!}

extremal sets isomorphic to S.

Proof. Suppose that S is an extremal set in standard form. S must be a down-set, since otherwise there is x ∈ S and y ∉ S with x_{j} = 1, y_{j} = 0 and x_{i} = y_{i}, for i ≠ j. But (1) implies that

d(S) − d(S − x + y) = |S| − 2w_{j}(S) + 1 > 0.

Similarly if S is not right-shifted, there is x ∈ S and y ∉ S with x_{j} = y_{ℓ} = 1, x_{ℓ} = y_{j} = 0, (for j < ℓ) and x_{i} = y_{i}, for i ≠ j, ℓ. Again

d(S) − d(S − x + y) = 2(w_{ℓ}(S) − w_{j}(S) + 1) > 0

contradicting the extremality of S and finishing the proof of a).

b) Using zero-one swaps in coordinates of weight greater than |S|/2 and then arranging the coordinates in an increasing fashion we see that S is isomorphic to some S′. To see that S′ is unique it suffices to see that swapping coordinates of equal weight and zero-one swapping coordinates of weight |S|/2 doesn’t change S′. Indeed suppose that x ∈ S′ and w_{i}(S′) = w_{j}(S′) with i < j. Now s_{ij}(x) = x, unless exactly one of x_{i}, x_{j} is zero. However, if x_{i} = 1 and x_{j} = 0, then x ∈ S′ since S′ is rightshifted, and the same holds if x_{i} = 0 and x_{j} = 1, since otherwise w_{i}(S′) < w_{j}(S′). If x ∈ S′, then changing x_{k} from one to zero results in a vector in S′, since S′ is a down-set, and changing a zero to a one does also, unless w_{k}(S′) < |S′|/2. Part c) is now obvious. □

So from now on we can assume that optimal sets are in standard form. Next we investigate complements of extremal sets.

Proposition 3. Let S ⊂ \{0, 1\}^{k} and \overline{S} = \{0, 1\}^{k} \ S.

a) d(\overline{S}) = d(S) + k2^{k−1}(2^{k−1} − |S|).

b) f(k, 2^{k} − n) = f(k, n) + k2^{k−1}(2^{k−1} − n).

c) The complement of an extremal set for f(n, k) is extremal for f(2^{k} − n, k).

d) If S is a down-set (up-set, right-shifted, left-shifted) then \overline{S} and r(S) are upsets (down-sets, left-shifted, right-shifted).

e) If S is a standard extremal set, then r(\overline{S}) = \overline{r(S)} is a standard extremal set.

Proof. a) Let |S| = n. Then

\begin{aligned}d(\overline{S}) & = ∑_{i=1}^{k} w_{i}(\overline{S})(2^{k} − n − w_{i}(\overline{S})) = ∑_{i=1}^{k}(2^{k−1} − w_{i}(S))(2^{k−1} − n + w_{i}(S)) \\ & = ∑_{i=1}^{k} (w_{i}(S)(n − w_{i}(S)) + 2^{2k−2} − n2^{k−1}) = k2^{k−1}(2^{k−1} − n) + d(S). \end{aligned}

Now b) and c) follow immediately, since d(\overline{S}) is minimal exactly when d(S) is. Finally d) follows from the definitions and implies e). □

So from now on, since there is a correspondence between sets and their complement (and since the central case n = 2^{k}/2 has been solved), we may assume that n < 2^{k−1}.

We also observe that the cubes and spheres (if we pick the “right” points of weight t) meet the basic requirements for extremal sets in standard form: they are right-shifted down-sets. Also, the complement of a sphere is a sphere centered at 111 … 1 and thus isomorphic to a sphere, for example \overline{B_{k}(n)} = r(B_{k}(2^{k} − n)), and

\overline{Q(n)} = \{b(n), b(n + 1), …, b(2^{k} − 1)\}
= r({b(2^{k} − 1 − n), b(2^{k} − 1 − (n + 1)), …, b(0)})
= r(Q(2^{k} − n)) ≃ Q(2^{k} − n).

3. Discrete balls

We will now give the main definition,

Definition 5. For x, y ∈ ℝ^{k} let d_{p}(x, y) := ∥x − y∥_{p} be their L_{p}-distance, where for 1 ≤ p < ∞ the L_{p}-norm is defined by

∥x∥_{p} := (∑_{i=1}^{k} |x_{i}|^{p})^{1/p} .

For c ∈ ℝ^{k}, r ≥ 0 and 1 ≤ p we can define the discrete L_{p}-ball

B_{p}(c, r) := {x ∈ {0, 1}^{k} : d_{p}(c, x) ≤ r}.

Also for y ∈ ℝ let f_{p}(y) := |1 − y|^{p} − |y|^{p}; for example f_{2}(y) = 1 − 2y.

The L_{p}-distance is a natural extension of the Hamming distance, so that every Hamming sphere is a discrete L_{p}-ball, B(x, r) = B_{p}(x, r^{1/p}) (for x ∈ {0, 1}^{k} and r ≥ 0). It is easy to see that all discrete L_{∞}-balls, where ∥x∥_{∞} := max{|x_{i}| : 1 ≤ i ≤ k}, are isomorphic to subcubes Q(2^{i}) for some i. This is not interesting for us, so throughout we will assume that 1 ≤ p < ∞.

The following simple observation is essential in our study of the properties of discrete balls.

Observation. If c ∈ ℝ^{k} and x ∈ {0, 1}^{k}, then

(3)  d_{p}(c, x)^{p} = ∥c∥_{p}^{p} + ∑_{x_{i}=1} f_{p}(c_{i}).

The following theorem will show, perhaps somewhat surprisingly, that the collection of L_{p}-balls is independent of p.

Theorem 5. For all c ∈ ℝ^{k}, r ≥ 0, such that B_{p}(c, r) ≠ ∅ a) B_{p}(c, r) = B_{2}(\overline{c}, \overline{r}), where \overline{c}_{i} = \frac{1}{2}(1 − f_{p}(c_{i})) and \overline{r} = \sqrt{r^{p} − ∥c∥_{p}^{p} + ∥\overline{c}∥_{2}^{2}}.

b) If c ∈ [0, 1]^{k}, then B_{2}(c, r) = B_{1}(c, \overline{r}), where \overline{r} = r^{2} − ∥c∥_{2}^{2} + ∥c∥_{1}.

c) B_{2}(c, r) = B_{2}(\overline{c}, \overline{r}) for some \overline{c} ∈ [0, 1]^{k}, \overline{r} ∈ ℝ.

Proof. a) follows from the observation that for any x ∈ {0, 1}^{k},

d_{p}(c, x)^{p} − ∥c∥_{p}^{p} = ∑_{x_{i}=1} f_{p}(c_{i}) = ∑_{x_{i}=1} f_{2}((1 − f_{p}(c_{i}))/2) = d_{2}(\overline{c}, x)^{2} − ∥\overline{c}∥_{2}^{2}.

For b) note that if 0 ≤ y ≤ 1, then f_{1}(y) = f_{2}(y), so that we conclude similarly that d_{2}(c, x)^{2} − ∥c∥_{2}^{2} = d_{1}(c, x) − ∥c∥_{1}.

For c), fix m > 0, and set c′_{i} = \frac{1}{2m}(m − 1 + 2c_{i}) and

r′ = \frac{1}{m}\sqrt{mr^{2} − m∥c∥_{2}^{2} + m^{2}∥c′∥_{2}^{2}}.

We will show that B_{2}(c, r) = B_{2}(c′, r′). From this the result will follow by choosing m sufficiently large – note that as an additional bonus we can choose \overline{c} as close to (1/2, …, 1/2) as we wish. Indeed,

\begin{aligned}d_{2}(c, x)^{2} − ∥c∥_{2}^{2} & = ∑_{x_{i}=1} f_{2}(c_{i}) = ∑_{x_{i}=1}(1 − 2c_{i}) = ∑_{x_{i}=1} m(1 − 2c′_{i}) \\ & = m ∑_{x_{i}=1} f_{2}(c′_{i}) = m(d_{2}(c, x)^{2} − ∥c′∥_{2}^{2}). □ \end{aligned}

Remarks. By observing that f_{q} is invertible when 1 < q, we could have replaced B_{2} in a) by B_{q} which would have shown that all p are equivalent. Even so, we know that we don’t lose any generality by restricting our attention to p = 1, 2. So from now on we will simply refer to discrete balls, and only specify p if necessary. Furthermore we can assume that c ∈ [0, 1]^{k}.

We will now investigate the properties of discrete balls. Let q be the vector with q_{i} = 2^{−i}.

Proposition 4.

a) The isomorphic image of a discrete ball is a discrete ball

b) For a discrete ball B = B_{2}(c, r) the following are equivalent:

i) B is a right-shifted down-set, ii) B is in standard form, and iii) we can assume that (0 ≤)c_{1} ≤ c_{2} ≤ ⋯ ≤ c_{k} ≤ 1/2.

c) \overline{B_{2}(c, r)} = B_{2}(\overline{c}, \overline{r}), where \overline{c} = j⃗ − c and \overline{r}^{2} = ∥c∥_{2}^{2} + ∥\overline{c}∥_{2}^{2} − r^{2} − ε for some ε > 0.

d) For 0 ≤ m ≤ 1 and 0 ≤ ε ≤ 2m

d_{1}(mj⃗ − εq, b(n)) = mk − ε(1 − 2^{−k}) + (1 − 2m)w(b(n)) + εn2^{1−k}.

e) Q(n) = B_{1}(c, r), with c = \frac{1}{2}j⃗ − q and r = d_{1}(c, b(n − 1)).

f) B(n) = B_{1}(c, r), with c = \frac{1}{4}j⃗ − \frac{1}{2}q and r = d_{1}(c, y) for y the lexicographically biggest vector of weight t in B(n).

Proof. a) Since d_{p}(c, x) = d_{p}(r_{i}(c), r_{i}(x)) it follows that r_{i}(B_{p}(c, r)) = B_{p}(r_{i}(c), r) and s_{ij}(B_{p}(c, r)) = B_{p}(s_{ij}(c), r).

For b), i) implies ii) is immediate. To see that iii) implies i), assume that c_{1} ≤ ⋯ ≤ c_{k} ≤ 1/2. Since c_{i} ≤ 1/2 and x_{i} = 1 implies that d_{2}(c, x) ≥ d_{2}(c, r_{i}(x)), B is a down-set. Similarly, if for i < j, x_{i} = 1 and x_{j} = 0, then

d_{2}(c, x)^{2} − d_{2}(c, s_{ij}(x))^{2} = f_{2}(c_{i}) − f_{2}(c_{j}) = 2(c_{j} − c_{i}) ≥ 0,

so that B is right-shifted. For ii) implies iii) suppose that w_{1}(B) ≤ w_{2}(B) ≤ ⋯ ≤ w_{k}(B) ≤ |B|/2. By Theorem 5 we can assume that c ∈ [0, 1]^{k} and B = B_{1}(c, \overline{r}). Suppose c_{i} ≥ 1/2. Then x ∈ B with x_{i} = 0 implies r_{i}(x) ∈ B, so that w_{i}(B) ≥ |B|/2 ≥ w_{i}(B). So equality must hold and therefore x ∈ B exactly when r_{i}(x) ∈ B. We see that B = B_{1}(c′, \overline{r}) where c′_{i} = 1/2 and c′_{j} = c_{j} for j ≠ i. Indeed, if x ∈ B, x_{i} = 0, then

\overline{r} ≥ d_{1}(c, x) ≥ d_{1}(c′, x) = d_{1}(c′, r_{i}(x)),

and if x ∉ B, x_{i} = 1, then

\overline{r} < d_{1}(c, x) ≤ d_{1}(c′, x) = d_{1}(c′, r_{i}(x)).

Furthermore, if c_{i} ≥ c_{j} for i < j, then x ∈ B with x_{i} = 0 and x_{j} = 1 implies that s_{ij}(x) ∈ B, so that w_{i}(B) ≥ w_{j}(B) ≥ w_{i}(B). Again we conclude that x ∈ B exactly when s_{ij}(x) ∈ B. So B = B_{1}(c′, \overline{r}) where c′_{i} = c′_{j} = (c_{i} + c_{j})/2 and c′_{ℓ} = c_{ℓ} for ℓ ≠ i, j. Indeed, ∥c∥_{1} = ∥c′∥_{1} and

f_{1}(c_{i}) + f_{1}(c_{j}) = 2(1 − c_{i} − c_{j}) = f(c′_{i}) + f(c′_{j}),

so that d_{1}(c, x) = d_{1}(c′, x) unless x_{i} ≠ x_{j}. Finally, if x ∈ B, x_{i} = 0, x_{j} = 1, then

\overline{r} ≥ d_{1}(c, x) ≥ d_{1}(c′, x) = d_{1}(c′, s_{ij}(x)),

and if x ∉ B, x_{i} = 1, x_{j} = 0, then

\overline{r} < d_{1}(c, x) ≤ d_{1}(c′, x) = d_{1}(c′, s_{ij}(x)).

This finishes the proof of b). For the proof of c) pick ε > 0 such that B_{2}(c, r) = B_{2}(c, \sqrt{r^{2} + ε}). This can be done since for all x ∉ B_{2}(c, r), d_{2}(c, x) > r. Note that

d_{2}(c, x)^{2} − ∥c∥_{2}^{2} = ∑_{x_{i}=1}(1 − 2c_{i}) = ∑_{x_{i}=1}(2\overline{c}_{i} − 1) = ∥\overline{c}∥_{2}^{2} − d_{2}(\overline{c}, x)^{2},

so that d_{2}(c, x) ≤ r implies d_{2}(\overline{c}, x)^{2} ≥ ∥\overline{c}∥_{2}^{2} + ∥c∥_{2}^{2} − r^{2} and thus x ∉ B_{2}(\overline{c}, r). Furthermore, d_{2}(c, x) > \sqrt{r^{2} + ε} implies that d_{2}(\overline{c}, x)^{2} < ∥\overline{c}∥_{2}^{2} + ∥c∥_{2}^{2} − r^{2} − ε and thus x ∈ B_{2}(\overline{c}, r).

For d) an easy calculation yields ∥mj⃗ − εq∥_{1} = mk − ε(1 − 2^{−k}), so that the formula follows from

\begin{aligned}d_{1}(mj⃗ & − εq, b(n)) − ∥mj⃗ − εq∥_{1} = ∑_{b(n)_{i}=1} f_{1}(mj⃗ − εq) = ∑_{b(n)_{i}=1}(1 − 2m + ε2^{1−i}) \\ & = (1 − 2m)w(b(n)) + ε2^{1−k} ∑_{b(n)_{i}=1} 2^{k−i} = (1 − 2m)w(b(n)) + ε2^{1−k}n. \end{aligned}

e) follows from d) by setting m = 1/2 and ε = 1, since then d_{1}(c, x) = ∥c∥_{1} +n2^{1−k}, which is increasing in n. For f) setting m = 1/4 and ε = 1/2, we obtain d_{1}(c, x) = ∥c∥_{1} + \frac{1}{2}[w(b(n)) + n2^{−k}]. Since n < 2^{k} for all b(n) ∈ \{0, 1\}^{k}, we have x ∈ B if w(x) < t and x ∉ B if w(x) > t. If w(x) = t, then x ∈ B if and only if it is lexicographically no bigger than y. □

So discrete balls have all the properties we expect of a candidate for extremal sets. In fact, we

Conjecture. For every (n, k) some extremal set is a discrete ball.

So far every known good construction is a discrete ball and discrete balls are also the solutions to other isoperimetric problems, like those in [AK, BL, H, Ht, Ka2]. There are product constructions that in some cases beat both the cube and the sphere, but even those are discrete balls.

Definition 6. For S ⊂ {0, 1}^{j} and T ⊂ {0, 1}^{k−j} we define their cartesian product S × T ⊂ {0, 1}^{k} as {(s_{1}, s_{2}, …, s_{j}, t_{1}, t_{2}, …, t_{k−j}) : s ∈ S, t ∈ T }.

Proposition 5.

a) d(S × T) = |T |^{2}d(S) + |S|^{2}d(T).

b) Q_{k−j}(n) × {0, 1}^{j} = Q_{k}(n2^{j}) and {0_{j}} × Q_{k−j}(n) = Q_{k}(n).

c) For c ∈ ℝ^{k−j}, B_{1}(c, r)×\{0, 1\}^{j} = B_{1}(\overline{c}, r+j/2), where \overline{c}_{i} = c_{i} if i ≤ k−j and \overline{c}_{i} = 1/2 if k − j < i ≤ k. The k-dimensional ball is a right-shifted down-set if and only if the (k − j)-dimensional one is. d) For c ∈ [0, 1/2]^{k−j}, \{0_{j}\} × B_{1}(c, r) = B_{1}(\overline{c}, r) if and only if r < ∥c∥_{1} + 1,

where \overline{c}_{i} = c_{i} if j < i ≤ k and \overline{c}_{i} = 0 if i ≤ j. The k-dimensional ball is a right-shifted down-set if and only if the (k − j)-dimensional one is.

Proof. a) follows from (1) and b) is straight forward. For c) we observe that for x ∈ \{0, 1\}^{k}, d_{1}(\overline{c}, x) = d_{1}(c, (x_{1}, … x_{k−j})) + j/2. The second parts of c) and d) follow from Proposition 4b). For d) note that for x ∈ {0, 1}^{j} and y ∈ {0, 1}^{k−j}, d_{1}(\overline{c}, (x, y)) = w(x)+d_{1}(c, y). Thus if w(x) = 0, then (x, y) ∈ B_{1}(\overline{c}, r) exactly when y ∈ B_{1}(c, r). If w(x) > 0, then d_{1}(\overline{c}, (x, y)) ≥ 1 + ∥c∥_{1}, so that (x, y) ∉ B_{1}(\overline{c}, r) exactly if r < ∥c∥_{1} + 1.

For example, if S = B((0, 0, 0, 0, 0, 0, 0, 0, 1/2, 1/2), 2) = B_{8}(9) × {0, 1}^{2}, then d(S) = 4^{2} · 64 + 9^{2} · 8 = 1672, whereas d(Q_{10}(36)) = 1736 and d(B_{10}(36)) = 1730. It can also be shown that no other generalized Hamming sphere has distance sum at most 1672, so that this product beats both the sphere and the cube.

4. Recognizing discrete balls

To decide whether a given set is a discrete ball, we first bring it into standard form. Then we can determine its set of generators and solve a system of linear inequalities as described in this section to determine whether it is indeed a discrete ball.

Definition 7. The right-shifted down-set generated by a set G ⊂ {0, 1}^{k}, denoted by RD(G), is the smallest right-shifted down-set containing G. It can be found as the intersection of all right-shifted down-sets containing G. LU(G) is defined similarly.

The generator for a set S, denoted by G(S), is the set of all x ∈ S, such that x ∉ RD(S − x). We similarly define G^{+}(S) for LU.

It can be seen that RD(G(S)) = RD(S) and that G(S) is the unique minimal set generating RD(S). Furthermore, S is a right-shifted down-set if and only if S = RD(S) and RD(G) = ⋃_{g∈G} RD({g}). Since G^{+}(S) = r(G(r(S))), similar statements hold for left-shifted up-sets.

Theorem 6. The following are equivalent a) S is a discrete ball in standard form

b) The system of linear inequalities

∑_{x_{i}=1} z_{i} ≤ 1 for all x ∈ G(S)

∑_{x_{i}=1} z_{i} > 1 for all x ∈ G^{+}(\overline{S})

has a solution with z_{1} ≥ z_{2} ≥ ⋯ ≥ z_{k} ≥ 0.

Proof. If S is a discrete ball in standard form, then 0 ∈ S and we can assume that 0 ≤ c_{1} ≤ c_{2} ≤ ⋯ ≤ c_{k} ≤ 1/2. Thus r ≥ d_{1}(0, c) = ∥c∥_{1}, and by an argument like in the proof of Proposition 4c) we can assume that the inequality is strict. Now set

z_{i} := \frac{1 − 2c_{i}}{r − ∥c∥_{1}} .

Certainly z_{1} ≥ z_{2} ≥ ⋯ ≥ z_{k} ≥ 0 and the remaining inequalities correspond to

∑_{x_{i}=1} f_{1}(c_{i}) ≤ r − ∥c∥_{1} for all x ∈ G(S) ⊂ S

∑_{x_{i}=1} f_{1}(c_{i}) > r − ∥c∥_{1} for all x ∈ G^{+}(\overline{S}) ⊂ \overline{S}

which are also satisfied.

Conversely, suppose that the inequalities in b) have the specified solution. It suffices to show that S = B_{2}(c, r), where c_{i} = (1 − z_{i})/2 and r = \sqrt{1 + ∥c∥_{2}^{2}}. For all x ∈ {0, 1}^{k}

d_{2}(x, c)^{2} − ∥c∥_{2}^{2} = ∑_{x_{i}=1} f_{2}(c_{i}) = ∑_{x_{i}=1} z_{i}.

For every x ∈ S there is a y ∈ G(S) with x ∈ RD(y). So if {i : x_{i} = 1} = {i_{1}, i_{2}, … i_{r}} and {j : y_{j} = 1} = {j_{1}, j_{2}, … j_{s}}, then i_{ℓ} ≥ j_{ℓ} for all 1 ≤ ℓ ≤ r. Hence

d_{2}(x, c)^{2} − ∥c∥_{2}^{2} = ∑_{x_{i}=1} z_{i} = ∑_{1≤ℓ≤r} z_{i_{ℓ}} ≤ ∑_{1≤ℓ≤r} z_{j_{ℓ}} ≤ ∑_{y_{j}=1} z_{j} ≤ 1,

and x ∈ B_{2}(c, r). Similarly, for x ∈ \overline{S} there is a y ∈ G^{+}(\overline{S}) with x ∈ LU(y). Here, in the notation from above, i_{ℓ} ≤ j_{ℓ} for all 1 ≤ ℓ ≤ s. So

d_{2}(x, c)^{2} − ∥c∥_{2}^{2} = ∑_{x_{j}=1} z_{j} ≥ ∑_{1≤ℓ≤s} z_{i_{ℓ}} ≥ ∑_{1≤ℓ≤s} z_{j_{ℓ}} = ∑_{y_{i}=1} z_{i} > 1,

and x ∉ B_{2}(c, r). □

We can now easily see that for example S = RD(110000, 001111) is not a discrete ball. We observe that \overline{S} = LU(010011) and S is in standard form, so that it is a discrete ball if and only if the system

\begin{aligned}z_{1} + z_{2} & ≤ 1 \\ z_{3} + z_{4} + z_{5} + z_{6} & ≤ 1 \\ z_{2} + z_{5} + z_{6} & > 1 \end{aligned}

has a solution with z_{1} ≥ z_{2} ≥ z_{3} ≥ z_{4} ≥ z_{5} ≥ z_{6} ≥ 0. However, this would imply that z_{2} ≤ 1/2 and z_{5} + z_{6} ≤ 1/2, a contradiction. Note that S is not an extremal set.

4. Small values

It follows from Theorem 1 that if n ≤ 8, then f(n, k) = (n − 1)^{2}, except that f(4, k) = 8 and f(8, k) = 48. Furthermore, Q_{k}(n) is an extremal set and the only other standard extremal sets in this range are B_{k}(n) for 5 ≤ n ≤ 7 and n ≤ k + 1. By complementation the corresponding statements hold for n ≥ 2^{k} − 8, so that for k ≤ 4 the situation is fully characterized. Also recall that Q_{k}(n) = B_{k}(n) if and only if n ≤ 3 or n ≥ 2^{k} − 3.

Table 1 lists all the values of f(n, k) for 9 ≤ n ≤ 18. The subscript indicates the number of extremal sets in standard form – if there is no subscript then the extremal set is unique. For example, there are exactly 5 distinct standard extremal sets achieving f(11, 7) = 112. Note that for k ≥ 17 ≥ n, f(n, k) = f(n, 16), and that f(18, k) = 289 for k ≥ 17.

\begin{matrix}n \ k & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ 9 & 68 & 68 & 68 & 68_{2} & 64 & 64 & 64 & 64 & 64 & 64 & 64 & 64 & 64 \\ 10 & 89 & 89_{2} & 89_{2} & 89_{3} & 86 & 81 & 81 & 81 & 81 & 81 & 81 & 81 & 81 \\ 11 & 112_{2} & 112_{2} & 112_{3} & 112_{5} & 110 & 106 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ 12 & 136 & 136 & 136_{2} & 136_{2} & 136_{4} & 133 & 128 & 121 & 121 & 121 & 121 & 121 & 121 \\ 13 & 164 & 164 & 164 & 164_{2} & 164_{3} & 162_{2} & 158 & 152 & 144 & 144 & 144 & 144 & 144 \\ 14 & 193 & 193 & 193 & 193_{2} & 193_{2} & 193_{3} & 190_{2} & 185 & 178 & 169 & 169 & 169 & 169 \\ 15 & 224 & 224 & 224 & 224 & 224 & 224 & 224_{2} & 220_{2} & 214 & 206 & 196 & 196 & 196 \\ 16 & 256 & 256 & 256 & 256 & 256 & 256 & 256 & 256 & 252_{2} & 245 & 236 & 225 & 225 \\ 17 & − & 304 & 304 & 304 & 304 & 298 & 298_{2} & 296 & 292 & 286_{2} & 278 & 268 & 256 \\ 18 & − & 353 & 353 & 353 & 353_{2} & 337 & 337 & 337_{2} & 334 & 329 & 322_{2} & 313 & 302 \end{matrix}

Table 1: Values of f(n, k) for 9 ≤ n ≤ 18.

n  Q^{k}(n)  B^{k}(n)  Generators for other standard extremal sets
9  k ≤ 7  k ≥ 7  none
10  k ≤ 7  k ≥ 7  U_{5}, U_{6}, U_{7}
11  k ≤ 7  k ≥ 7  {e_{k−3} + e_{k−2}}(k ≤ 7), T_{6}^{1}, T_{7}^{1}, T_{7}^{2}
12  k ≤ 8  k ≥ 8  U_{6}, U_{7}, U_{8}, T_{8}^{1}
13  k ≤ 8  k ≥ 9  T_{7}^{1}, T_{8}^{1}, T_{8}^{2}, T_{9}^{1}
14  k ≤ 9  k ≥ 10  U_{7}, U_{8}, U_{9}, T_{9}^{1}, T_{10}^{1}
15  k ≤ 10  k ≥ 11  T_{10}^{1}, T_{11}^{1}
16  k ≤ 11  k ≥ 12  T_{12}^{1}
17  k ≤ 8  k ≥ 13  T_{k}^{1}(9 ≤ k ≤ 13), T_{10}^{2}
18  k ≤ 8  k ≥ 14  {00000111, 10000001}, U_{9}, U_{10}, U_{11}, T_{k}^{1}(11 ≤ k ≤ 14)

Table 2: Standard extremal sets for 9 ≤ n ≤ 18.

Table 2 lists all standard extremal sets corresponding to the entries in Table 1. As usual, let e_{i} := r_{i}(0) denote the standard basis vectors. For simplicity, define the following generators in {0, 1}^{k}:

U_{k}(n) = {e_{k} + e_{k+1−n/2}} for even n ≤ 2k,
T_{k}^{r}(n) = {e_{r}, e_{k} + e_{2k+2−r−n}} for 1 ≤ r < 2k + 2 − r − n < k.

For example T_{8}^{2}(13) = {01000000, 00100001}, and we can drop the argument since there is no ambiguity.

Observe that the extremal set for (18, 8) is the smallest such set that is neither a sphere nor a cube – however, it is the discrete ball B_{1}((0, 0, 0, 0, 0, 1/4, 1/4, 1/2), 2). Although it is true that for k ≥ n − 1 spheres are extremal, Table 2 is misleading since in general it is not the case that for small k cubes are extremal: By Proposition 3 and Theorem 1 the cube is not extremal for n = 2^{k} − 9 if k ≥ 8. We believe that for k ≤ 7 the cube is optimal for all n ≤ 2^{k}.

5. Choosing the center

Although there are fewer discrete balls than right-shifted down-sets, there are still many of them. Maybe the conjecture can be sharpened by requiring additional properties of the discrete balls, like its center is of the form mj⃗ − εq as suggested by Proposition 4d)-f).

Definition 8. The centroid of a set S ⊂ {0, 1}^{k} is defined as

c(S) := |S|^{−1} ∑_{x∈S} x = (w_{1}(S)/|S|, w_{2}(S)/|S|, …, w_{k}(S)/|S|).

The set S is called a good ball if S = B_{1}(c(S), r) for some r ≥ 0, or equivalently by Theorem 5b), if S = B_{2}(c(S), r) for some r ≥ 0.

Proposition 6.

a) d(S) = |S|^{2}c(S) · (j⃗ − c(S)).

b) If S is a good ball, then r_{i}(S), s_{ij}(S) and \overline{S} are good balls.

c) B(0, r) is a good ball.

Proof. a) is just a rewriting of (1). By observing that r_{i}(c(S)) = c(r_{i}(S)) and s_{ij}(c(S)) = c(s_{ij}(S)), the first two assertions in b) follow from the proof of Proposition 4a). If we define for any set S and x ∈ {0, 1}^{k}

S(x) = ∑_{x_{i}=0} w_{i}(S) + ∑_{x_{i}=1}(|S| − w_{i}(S)),

then a quick calculation yields \overline{S}(x) = k2^{k−1} − S(x) and d_{1}(x, c(S)) = S(x)/|S|. So if S = B_{1}(c(S), r), where r ≥ 0 is such that S = B_{1}(c(S), r − ε) for some ε > 0, then it follows easily, that \overline{S} = B_{1}(c(\overline{S}), (k2^{k−1} − r|S|)/(2^{k} − |S|).

The proof of c) is straight forward, since c(B(0, r)) = yj⃗ with 0 ≤ y ≤ r/k. □

It is also worth noting that all standard extremal sets mentioned in Section 4 and Theorems 1-3 are good balls. In short, all known extremal sets are good balls. However, not all discrete balls are good balls: S = RD(e_{2}, e_{7} + e_{8}) ⊂ {0, 1}^{9} has \overline{S} = LU(e_{1}, e_{6}+e_{9}, e_{7}+e_{8}+e_{9}) and is a discrete ball, since the corresponding system has a solution (z_{1} = 2, z_{2} = ⋯ = z_{6} = 1 and z_{7} = z_{8} = z_{9} = 1/2). Its centroid is c(S) = \frac{1}{12}(0, 1, 1, 1, 1, 1, 3, 3, 3) and d(c(S), e_{7} + e_{8}) = 26/12 = d(c(S), e_{1}), so that S is not a good ball.

Question. Is some/every extremal set achieving f(n, k) a good ball?

Acknowledgments. The author is grateful to Mitch Harris and Jeff Erickson, who suggested looking at discrete balls, and Levon Khachatrian, Ken Zeger, Radhika Ramamurthi and Zoltán Füredi for helpful remarks. The computer program that generated the values for the tables was written by Christian Deppe.

References

[AA] R. Ahlswede, I. Althöfer, The asymptotic behaviour of diameters in the average, J. Combin. Theory Ser. B 61 (1994), 167–177.

[AK] R. Ahlswede, G. O. H. Katona, Contributions to the geometry of Hamming spaces, Discrete Math. 17 (1977), 1–22.

[AS] I. Althöfer, T. Sillke, An “average distance” inequality for large subsets of the cube, J. Combin. Theory Ser. B 56 (1992), 296–301.

[Bz] S. L. Bezrukov, Isoperimetric problems in discrete spaces, Bolyai Soc. Math. Stud. 3 (1994), 59–91.

[Bl] W. Blaschke, Eine isoperimetrische Eigenschaft des Kreises, Math. Z. 1 (1918), 52–57.

[BL] B. Bollobas, I. Leader, Maximal sets of given diameter in the grid and the torus, Discrete Math. 122 (1993), 15–35.

[FF] P. Frankl, Z. Füredi, A short proof for a theorem of Harper about Hamming-spheres, Discrete Math. 34 (1981), no. 3, 311–313.

[F] F. Fu, On the improvements of Althöfer-Sillke inequality, J. Math. Res. Exposition 16 (1996), no. 3, 325–328.

[FWY] F. Fu, V. R. Wei, R. W. Yeung, On the minimum average distance of binary codes: Linear programming approach, preprint (1999).

[H] L. H. Harper, Optimal numberings and isoperimetric problems, J. Combinatorial Theory 1 (1966), 385–393.

[Ht] S. Hart, A note on the edges of the n-cube, Discrete Math. 14 (1976), 157–163.

[JKM] F. Jaeger, A. Khelladi, M. Mollard, On shortest cocyle covers of graphs, J. Combin. Theory Ser. B 39 (1985), 153–163.

[JT] U. Jamshy, M. Tarsi, Cycle covering of binary matroids, J. Combin. Theory Ser. B 46 (1989), 154–161.

[Ka1] G. O. H. Katona, The Hamming-sphere has minimum boundary, Studia Sci. Math. Hungar. 10 (1975), no. 1–2, 131–140.

[Ka2] G. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar 15 (1964), 329–337.

[K] A. Kündgen, Covering cliques with spanning bicliques, J. Graph Theory 27 (1998), no. 4, 223–227.

[S] L. A. Santaló, Integral geometry and geometric probability, Encyclopedia of Mathematics and its Applications, Vol.1, Addison-Wesley Publishing Co., Reading,Mass.-London-Amsterdam, 1976.

[T] M. Tarsi, Nowhere zero flow and circuit covering in regular matroids, J. Combinatorial Theory, Ser. B 39 (1985), 346–352.

[XF] S. Xia, F. Fu, On the average Hamming distance for binary codes, Discrete Appl. Math. 89 (1998), 269–276.

Department of Mathematics, University of Illinois, Urbana, Illinois 61801 E-mail address: kundgen@member.ams.org