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

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

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

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

#Background: geometry in the Hamming cube#
Harper (1966) showed that for each $k$, one can find a Hamming-sphere that has minimal $r$-fold boundary among sets of cardinality $k$ in $\{0,1\}^n$. Here the $r$-fold boundary of $A\subseteq \{0,1\}^n$ is $$ \{x\in\{0,1\}^n: 0<d(x,A)\le r\} $$ and $d(x,y)$ is the Hamming distance between $x$ and $y$, i.e., the cardinality of $\{n: x(n)\ne y(n)\}$; and a "Hamming-sphere" is a set $H$ with $B(p)\subseteq H\subseteq B(p+1)$ where $$ B(p)=\{x: d(x,0)\le p\}, $$ where $0$ is the constant zero function.

#A modification#
Replace $d$ by a different metric $D$: let $d_j(x,y)$ be the Hamming distance between the prefixes of $x$ and $y$ of length $j$, and let $$ D(x,y)=\max_{j\le n}\ \frac{d_j(x,y)}{f(j) } $$ where $0\le f(j)\le j$, for instance, $f(j)=j/\log j$. #Idea#
$D(x,y)$ being small captures the fact that the differences of $x$ and $y$ do not clump together at small values of $j$. Under this metric the Hamming cube perhaps looks more like a box than a cube.

Under the metric $D$, what is the minimum cardinality of the $r$-fold boundary of a subset of $\{0,1\}^n$ of cardinality $k$?

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