Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is not necessarily Theoretical Computer Science but I think similar things come up sometimes, for instance in randomness extraction.


$d(x,y)=$ the Hamming distance between binary strings $x$ and $y$ of length $n$, $=$ the cardinality of $\{k: x(k)\ne y(k)\}$.

For a set of strings $A$,

$d(x,A)=\min \{ d(x,y): y\in A\}$.

The $r$-fold boundary of $A\subseteq \{0,1\}^n$ is

$$\{x\in\{0,1\}^n: 0 < d(x,A)\le r\}.$$

Balls centered at $0$ are given by

$$ B(p)=\{x: d(x,0)\le p\}, $$ where $0$ is the string of $n$ many zeroes.

A Hamming-sphere is a set $H$ with $B(p)\subseteq H\subseteq B(p+1)$. (So it's more like a ball than a sphere, but this is the standard terminology...)

Now, Harper in 1966 showed that for each $k$, $n$, $r$, one can find a Hamming-sphere that has minimal $r$-fold boundary among sets of cardinality $k$ in $\\{0,1\\}^n$. So a ball is a set having minimal boundary -- just like in Euclidean space.

The cardinality of $B(p)$ is ${n\choose 0}+\cdots {n\choose p}$.

The $r$-fold boundary of $B(p)$ is just the set $B(p+r)\setminus B(p)$, which then has cardinality ${n\choose p+1}+\cdots+{n\choose p+r}$.

So far, so good. But now suppose we replace $d$ by a different metric $D$: first let $d_j(x,y)$ be the Hamming distance between the prefixes of $x$ and $y$ of length $j$, and then $$ D(x,y)=\max_{j\le n}\ \frac{d_j(x,y)}{f(j) }$$ where $0\le f(j)\le j$. (For example we could have $f(j)=\sqrt{j}$, or $f(j)=j/\log j$.)

This is supposed to make $D(x,y)$ small if the differences of $x$ and $y$ do not clump together at small values of $j$.


Is the minimum $r$-fold boundary (under $D$) realized by a $D$-ball?

Is there a better definition of $D$?

Under the metric $D$, what's the minimum size of the $r$-fold boundary of a subset of $\\{0,1\\}^n$ having cardinality $k$? (A reasonable lower bound would be nice.)

(Cross-posted on MathOverflow).



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.