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

Question

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

Answer 1

(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}$.