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



A question of Ahlswede and Katona: known lower bounds on $\beta(d,n)$?
(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}$.


