3
$\begingroup$

Let $\Sigma$ be an alphabet of size $s$, with which we build strings of length $n$.

The Hamming ball of radius $d$ centered at $x\in\Sigma^n$ is the set $B(x, d)$ of words in $\Sigma^n$ that differ from $x$ in at most $d$ positions.

Similarly, the Hamming circle of radius $d$ centered at $x\in\Sigma^n$ is the set $C(x, d)$ of words in $\Sigma^n$ that differ from $x$ in exactly $d$ positions (note: "Hamming ball" is a standard term, but I do not know whether the expression "Hamming circle" exists at all).

Are there closed expressions for $|B(x, d_1)\cap B(y, d_2)|$ and $|C(x, d_1)\cap C(y, d_2)|$, given any two distinct strings $x,y\in\Sigma^n$ and any two $d_1,d_2\in\mathbb{N}$?

  • 2
    I would use the term "Hamming sphere" instead of "Hamming circle", as the term sphere is used in the context of metric spaces.2010-11-09
  • 0
    Thanks for the suggestion, but a quick Google search indicates that many authors already confuse those terms: "spheres" and "circles" are in some cases used for what I refer to as "balls". Another example however gives "Hamming sphere" yet another meaning: http://mathoverflow.net/questions/38221/geometry-in-a-hamming-box2010-11-09
  • 2
    your *Hamming circle* is a what everyone calls a sphere in the metric space of words with the Hamming metric. So usin the word *sphere* is the only sensible thing, independently of how people confuse balls and spheres.2010-11-09

1 Answers 1

3

To get started, let us work on the circle intersection where the distances are the same: $|C(x,d)\cap C(y,d)|$. Let the distance between $x$ and $y$ be $m$. Then we pick $i$ places of the disagreement where we agree with $x$, have to have $i$ of the disagreement that we agree with $y$, and $d-i$ of the others where we have to disagree with both to get the correct distance. Each of those $d-i$ can have $s-2$ choices, as they have to disagree with $x$ and $y$, as can the $m-2i$ that we didn't choose to agree with x or y. So $$|C(x,d)\cap C(y,d)|=\sum_{i=0}^{\frac{m}{2}} \binom{m}{i} \binom{m-i}{i} \binom{n-m}{d-i} (d+m-3i)^{(s-2)}$$ If you can sum this, you are better than I. For the ball, we can just sum over $m$.