Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, for example in randomness extraction.
Define:
$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$.
Questions
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 CSTheory).
