4
$\begingroup$

Question

Let $\mathbb{N} = \{0, 1, 2, \dots \}$, $\mathbb{N}^+ = \mathbb{N} - \{0\}$, $m \in \mathbb{N}^+$, $[m] := \{0, 1, \dots, m-1\}$ and define the function $f:[m]\to[m]$ as below

$$f(i) = (a + i \, b) \bmod m,$$

where $a, \, b \in \mathbb{N}$. I want to show that $\big( f(0), f(1), \dots, f(m-1) \big)$ is a permutation of $(0, 1, \dots, m-1)$ provided that $b$ and $m$ are relatively prime.


Motivation

In open address hash tables, hash functions are of the form

$$h:U \times \{0, 1, \dots, m-1\} \to \{0, 1, \dots, m-1\}, \tag{1}$$

where $U$ is the set of all possible keys. It is required that the sequence of probes defined as

$$p(k) := \big(h(k, 0), \, h(k, 1), \dots, \, h(k, m-1)\big) \tag{2}$$

generates a permutation of $(0,1,\dots,m-1)$ for every key $k \in U$, which guarantees that all of the hash table slots will be visited in a probe sequence. One way to get around this is by double hashing. In this method, the hash function is defined as below

$$h(k,i):=f(k) + i \, g(k) \bmod m, \tag{3}$$

where $f$ and $g$ are functions of the form

$$f:U \to \{0, 1, \dots, m-1\}, \qquad g:U \to \{0, 1, \dots, m-1\}.$$

In order to have the permutation property, we have the following theorem.

Theorem. If $g(k)$ and $m$ are relatively prime then $p(k)$ is a permutation of $(0,1,\dots,m-1)$.

$\endgroup$
2
  • 1
    $\begingroup$ So the actual question is not about double hashing but just something like $a + bn \mod m$? $\endgroup$
    – qwr
    Aug 18 at 20:41
  • $\begingroup$ @qwr: Well, the question is motivated by the double hashing concept and the requirement that we want to have a probe sequence which looks at all of the hash table slots . $\endgroup$ Aug 18 at 20:56

2 Answers 2

5
$\begingroup$

This is not true in general, since you haven't put any restrictions on the divisibility properties of $a, b$, and $m$. For example, if $a= 3$ and $b = m$ then $f$ is not a permutation since it just maps everything to $3$.

However, it will be true if $b$ is assumed coprime to $m$. Let's see why.

First, the final step of adding $a$ and then modding by $m$ obviously gives a permutation, and so you only need to check that multiplying by $b$ gives a permutation.

Since $b$ and $m$ are coprime, there are integers $c$ and $d$ such that $cb + dm = 1$. That means that any arbitrary class $f$ modulo $m$ is the same as $(cb + dm)f = b\cdot(cf)$ mod $m$. So multiplication by $b$ is a permutation and multiplication by $c$ is the inverse of it.

$\endgroup$
3
  • $\begingroup$ (I didn't read the motivation before answering the math question but now I see you added the coprime assumption, which is necessary, there.) $\endgroup$
    – hunter
    Aug 18 at 15:29
  • $\begingroup$ (+1), Thanks for your attention. You are right, I just forgot put the coprime condition in the question part. :) $\endgroup$ Aug 18 at 17:19
  • 1
    $\begingroup$ For context, the result about coprime numbers is known as Bezout's Lemma, and can be generalized to rings $\endgroup$
    – qwr
    Aug 18 at 20:36
1
$\begingroup$

If we want to show that $\big(f(0), f(1), \dots, f(m-1)\big)$ is a permutation of $(0,1,\dots,m-1)$, it suffices to show that $f: \{0, 1, \dots , m-1\} \to \{0, 1, \dots , m-1\}$ is a bijection. For $f$ to be an injection we must show

$$f(i) = f(j) \implies i=j.$$

So, let's start with the hypothesis that $f(i)=f(j)$ and use what we have.

\begin{align} (a + i \, b \bmod m) &= (a + \, j \, b \bmod m) \\ a + i \, b &\overset{m}{\equiv} a + j \, b \\ i \, b &\overset{m}{\equiv} j \, b \tag{1}\\ i &\overset{m}{\equiv} j \tag{2}\\ i &= j \tag{3}, \end{align}

where $(2)$ was concluded from $(1)$ because $b$ and $m$ are relatively prime that is $\gcd(b, m) = 1$, and $(3)$ was concluded from $(2)$ because $i, \, j \in \{0, 1, \dots, m-1 \}$. There are two ways to show that $f$ is a surjection.

A. The easy way is to note that $f$ is a map between two finite sets of the same cardinality, and since it is an injection, it also becomes a surjection.

B. The other way is to directly show that $f$ is a surjection, which requires that $$\forall k \in \{0, 1, \dots , m-1\}, \, \exists i \in \{0, 1, \dots, \,m-1\}, (a + i \, b) \bmod m = k.$$ Firstly, note that

\begin{align} a + i \, b &\overset{m}{\equiv} k \\ i \, b & \overset{m}{\equiv} k - a \\ i \, b & \overset{m}{\equiv} \bar k, \end{align}

where $\bar k := k - a$. Now, since $b$ and $m$ are relatively prime, by the Bezout's lemma there exists integers $x$ and $y$ such that $x \, b + y \, m = 1$. Consequently, we have

$$\bar k \overset{m}{\equiv} (x \, b + y \, m) \, \bar k \overset{m}{\equiv} (x \, \bar k) \, b \overset{m}{\equiv} (x \, \bar k \bmod m) \, b. $$

Finally, we set $i:= x \, (k - a) \bmod m$ for the given $k$.

$\endgroup$
2
  • 1
    $\begingroup$ Since it's a map between finite sets of the same cardinality it is not needed to show that it is a surjection once it's an injection. $\endgroup$
    – quid
    Aug 18 at 23:00
  • $\begingroup$ @quid: That's right. :) $\endgroup$ Aug 19 at 10:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.