# 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}{4}\left(d+1-\frac{2^d}{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}{4}\left(d+1-2^k\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