In their original paper, Storing a sparse table with O(1) worst case access time (Fredman, Kolmos and Szemeredi, Proc. FOCS '82, IEEE, 1982), the authors show that a perfect hash function must exist, provided that the table is the square of the number of elements in the key space.

The key part of the proof bounds the number of possible keys that can produce a particular collision.

Namely, given positive natural numbers, $p$, $s < p$, $a < s$, $b < s$, where $p$ is prime, the authors claim that there are fewer than $(p-1)/s$ solutions to

$$a' \equiv b' \pmod s\,,$$ where $a', b' \in \mathbb{N}_p$, $a' \equiv a\pmod p$, and $b' \equiv b \pmod p$.

This is done by asserting that if $k$ is a solution, then $k(a-b)$ must be congruent, mod $p$, to exactly one of $\{s, 2s, ..., p-s, p-2s, ... \}$.

I do not understand this argument. Could someone please elaborate?

  • $\begingroup$ What do you mean by "$k$ is a solution"? A solution is a pair $a',b'$. Also, what is $\mathbb{N}_p$? $\endgroup$ – Yuval Filmus Sep 5 '17 at 8:57
  • $\begingroup$ If you refer to Lemma 1, then the given bound is actually $2(p-1)/s$. $\endgroup$ – Yuval Filmus Sep 5 '17 at 9:00
  • 2
    $\begingroup$ Please make your question self-contained and accurate. $\endgroup$ – Yuval Filmus Sep 5 '17 at 9:00

Your Answer

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

Browse other questions tagged or ask your own question.