1
$\begingroup$

Motivation. In computer science, hash functions are maps that convert binary strings of arbitrary length to a fixed-length binary string. In symbols, we have a map $h:\{0,1\}^* \to \{0,1\}^n$ for some fixed $n\in\newcommand{\N}{\mathbb{N}}\N$. A requirement for $h$ that we see in real life is: if an input bit gets flipped, then the resulting output ("hash") has a large Hamming distance to the hash of the original input. This is called the "avalance effect". The avalanche effect can be obtained with a simple construction: send inputs with an odd number of bits set to $1$ to the constant $1$-vector, and send the other inputs to the constant $0$-vector. However, things get more involved if we ask for $h$ to be surjective.

Formalization. We identify the collection of binary sequences of length $n$ with ${\cal P}([n])$ where $[n]:=\{1,\ldots,n\}$. Moreover, we identify the collection of finite binary sequences of arbitrary length with the collection of finite subsets of $\N$, denoted by $\newcommand{\Pf}{{\cal P}_{\text{fin}}(\N)}\Pf$. For $A, B\in \Pf$, their Hamming distance is given by $d_H(A,B) = \big|(A \setminus B)\cup (B\setminus A)\big|$.

Question. Given any positive integer $n$ there a surjective map $h:\Pf\to{\cal P}\big([2n]\big)$ such that whenever $A,B\in \Pf$ with $d_H(A,B) = 1$, then $d_H\big(h(A), h(B)\big) \geq n$?

Improve this question
$\endgroup$
1
  • $\begingroup$ I think the following "silly example" works: begin with the map $h_0$ sending odd-size sets $[2n]$ and even-size sets to $\emptyset$. Then, enumerate the subsets of $[2n]$ of size at most $n$ as $S_1,\ldots,S_m$ and the subsets of $[2n]$ of size greater than $n$ as $T_1,\ldots,T_{m'}$. Finally, define $h$ to be $h_0$ except that $h([6k])=S_k$ and $h([6\ell+3])=T_\ell$ for each $k\in[m]$ and $\ell\in[m']$. $\endgroup$
    – Carl Schildkraut
    Commented 9 hours ago

1 Answer 1

Reset to default
3
$\begingroup$

Let $k = 2n-1$. The $k$-distance graph on $\{0,1\}^{2n}$ possesses a Hamiltonian cycle $c$. So, define $h(A) = c(|A| \bmod 2^{2n})$ .

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .