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