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