3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – esg Feb 28 '19 at 17:14
  • $\begingroup$ 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. $\endgroup$ – Clement C. Mar 1 '19 at 18:46
  • $\begingroup$ Take your time. No reason to hurry. $\endgroup$ – esg Mar 2 '19 at 14:10
  • $\begingroup$ Thanks a lot for your answer! That even matches what I hoped/needed... $\endgroup$ – Clement C. Mar 3 '19 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.