19
$\begingroup$

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

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 MathOverflow).

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.