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. 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$.  QuestionsIs 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).
Weighted Hamming distance
co.combinatorics;randomness