# A question of Ahlswede and Katona: known lower bounds on $\beta(d,n)$?

Given a set $$S\subseteq \{0,1\}^d$$ of the Boolean hypercube of dimension $$d$$, define the average distance of $$S$$ as $$\bar{d}(S) = \frac{1}{\lvert S\rvert^2} \sum_{x,y\in S} d_H(x,y)\tag{1}$$ where $$d_H$$ denotes the Hamming distance. For any $$1\leq n \leq 2^d$$, define the minimum average distance as $$\beta(d,n) = \min_{\substack{S\subseteq \{0,1\}^d\\ \lvert S\rvert = n}} \bar{d}(S)\tag{2}$$

In [1], Ahlswede and Katona asked $$\beta(d,n)$$ for arbitrary $$n$$. Ahlswede and Althöfer, in [2], provided asymptotically tight (in $$d$$) lower bounds on $$\beta(d,n)$$, when $$n \geq\binom{d}{\alpha d}$$ for constant $$\alpha \in(0,1/2)$$: $$\liminf_{d\to\infty} \frac{\beta(d,n)}{d} \geq 2\alpha(1-\alpha)\tag{3}$$

In [3], Althofer and Sillke also showed the general bound $$\beta(d,n) \geq \frac{1}{2}\left(d+1-\frac{2^{d-1}}{n}\right) \tag{4}$$

Besides that, there is some work showing optimal bounds for some cases of the form $$n= 2^{d-1}\pm O(1)$$ (see e.g. [4]), and it seems most of the more recent work is focused on those, and the structure of optimal large sets achieving these bounds.

So it looks like, for $$n= 2^{d-k}$$, the cases $$k=\Theta(d)$$ (via (3)) and $$k=O(1)$$ are rather well-understood; but for the general case, (4) only gives $$\beta(d,n) \geq \frac{1}{2}\left(d+1-2^{k-1}\right) \tag{5}$$ while the other cases seem to hint at a behavior more like $$\beta(d,n) \approx d-k$$.

Is there anything better than (4) known for the "intermediary regime" where $$n=2^{d-k}$$ with $$1 \ll k \ll d$$ (e.g., $$k = \log d$$, or $$k = \sqrt{d}$$)?

[1] R. Ahlswede and G.O.H. Katona, “Contributions to the geometry of hamming spaces”, Discrete Mathematics, vol. 17, 1977, pp. 1-22.

[2] R. Ahlswede and I. Althöfer, “The asymptotic behavior of diameters in the average”, Journal of Combinatorial Theory, Series B, vol. 61, 1994, pp. 167-177.

[3] Ingo Althöfer, Torsten Sillke, 1992, 'An “average distance” inequality for large subsets of the cube', Journal of Combinatorial Theory, Series B, vol. 56, no. 2, pp. 296-301

[4] André Kündgen, 2002, 'Minimum average distance subsets in the hamming cube', Discrete Mathematics, vol. 249, no. 1-3, pp. 149-165

(0) Preliminaries:

(a) factors: above you should change the factors $$\frac{1}{4}$$ on the rhs of your equations (4) and (5) to $$\frac{1}{2}$$ (Kündgens distance is half the distance of Ahlswede/Katona)).

(b) notation: in the sequel I use $$n$$ for the dimension , $$s$$ for the size of the set $$S$$, $$w_H$$ for the Hamming weight, and $$B_{n,r}:=\{ x\in \mathbb{F}_2^n\,:\,w_H(x)\leq r\}$$ denotes the set of bit vectors of Hamming weight $$\leq r$$ (the Hamming sphere of radius $$r$$ around $$0$$).

(c) convention: in the sequel always $$s\leq 2^{n-1}$$.

(1) A simple lower bound for the minimum average distance $$\beta(n,s)$$ is the average Hamming weight in a set of $$s$$ Hamming-smallest bit vectors of length $$n$$ (see the remark after proposition 1 in [4]. I am not aware of other/better bounds.)
Using that it is not difficult to show that $$\beta(n,s)=\frac{n}{2}-o(n)$$ for the intermediate cardinalities $$s=2^{n-o(n)}$$.

Sketch: for any $$r$$ with $$2r\leq n$$ the average Hamming weight in $$B_{n,r}$$ is very close to $$r$$. $$B_{n,r}$$ contains $$b_{n,r}:=\sum_{j=0}^r{n\choose j} \leq 2^{n\,h(\tfrac{r}{n})}$$ elements, where $$h(p)=-p\log_2(p)-(1-p)\log_2(1-p)$$ denotes the binary entropy function.
If $$b_{n,r}=2^{n-k}$$ we therefore have $$n\big(1-h(\tfrac{r}{n})\big)\leq k$$ Recalling that $$1-h(p)\geq \frac{(1-2p)^2}{2\log(2)}$$ now gives $$(1-2\tfrac{r}{n})\leq \sqrt{2\log(2)\tfrac{k}{n}},\;\mbox{ that is } r\geq \frac{n}{2}-\frac{1}{2}\sqrt{2\log(2)\,k\,n}$$

(2) In the light of the above the right question for the intermediate domain seems to be:
how much can $$\bar{d}(S)$$ go below $$\frac{n}{2}$$?

Since Hamming spheres are frequently near-optimal (and always optimal up to a factor of $$2$$) one will look at Hamming spheres for a first orientation.

Computation shows: $$\bar{d}(B_{n,r})=\frac{n}{2}\big(1-f_{n,r}^2)\big)$$ where $$f_{n,r}=\frac{{n-1 \choose r}}{\sum_{j=0}^r {n \choose j}}$$. Using well known properties of the binomial distribution one then finds:

(1) if $$r,n\longrightarrow \infty$$ s.th. $$\frac{n-2r}{\sqrt{n}}\longrightarrow \alpha\in [0,\infty)$$ $$\bar{d}(B_{n,r})\approx \frac{n}{2} - \frac{1}{2}\,\frac{\phi(2\alpha)^2}{\Phi(-2\alpha)^2}$$

(2) if $$r,n\longrightarrow \infty$$ s.th. $$\frac{n-2r}{\sqrt{n}}\longrightarrow \infty$$ and $$\frac{r}{n} \longrightarrow 0$$ $$\bar{d}(B_{n,r})\approx \frac{n}{2} -\frac{1}{2}\frac{(n-2r)^2}{n}$$

(3) if $$r,n\longrightarrow \infty$$ s.th. $$\frac{r}{n} \longrightarrow \alpha\in (0,\tfrac{1}{2})$$ $$\bar{d}(B_{n,r})\approx \frac{n}{2}\big(1-(1-2\alpha)^2\big)$$

(3) if $$\frac{r}{n} \longrightarrow 0$$ $$\bar{d}(B_{n,r})\approx 2r$$ (in fact for $$2r\leq n$$ always $$\bar{d}(B_{n,r})\leq 2r(1-\frac{r}{n})$$)

So, for Hamming spheres $$B_{n,r}$$ the answer is: $$\bar{d}(B_{n,r})$$ is of order $$(n-2r)^2/n$$ smaller than $$n/2$$. Assuming that this behaviour is near-optimal, and typical, one may conjecture that in sets $$S$$ of size $$s=2^{n-k}$$ the average distance can only be of order $$k$$ smaller than $$\frac{n}{2}$$.

• @Clement C.:I'm surprised that you didn't correct the factor $\tfrac{1}{4}$ in (4) and (5) (you can easily check that in [3] Althöfer/Sillke use definition (1) and give the inequality with factor $\tfrac{1}{2}$). Let me know if I can improve the answer to something useful, in particular if anything is unclear, false, or too succinct. – esg Feb 28 '19 at 17:14
• Thank you for the answer! I'll go over it carefully over the weekend (I'm swamped right now),... sorry for the delay in seeing this. – Clement C. Mar 1 '19 at 18:46
• Take your time. No reason to hurry. – esg Mar 2 '19 at 14:10
• Thanks a lot for your answer! That even matches what I hoped/needed... – Clement C. Mar 3 '19 at 23:24