# Universal hashing (bijection) with multiplication

I came across this question while thinking about a CS problem:

Given a set $S = [a,b]$ , and a string $x \in S^{n}, x = r_1r_2 \cdots r_n$, under what conditions is $H(x) = r_1 * r_2 * \cdots * r_n$ a bijection with $S^{n}$?

CS Background: i.e I have a string of length $n$, with ASCII character codes from $a$ to $b$, and I want to map all permutations of a string to the same place in a hash table, any other string to a different place. I was thinking of when multiplying the ASCII codes out as a hash function would work.

My idea was that if I have a string of two numbers, $x.y$, then $x*y$ will be unique as long as $\frac{x}{k_1}$ and $(x*k_1)$ arent in $S$, and $\frac{y}{k_2}$ and $(y*k_2)$ aren't in $S$, where $k_1$,$k_2$ are the smallest prime factors of $x$ and $y$ respectively.

But then I ran a program to test this with $a=51$, $b=100$. This should give me a bijection by the logic above, since the min element is 51 and 51*2=101 (2 is smallest possible prime factor) is not in the set, but $4104 = 54*76 = 57 * 52$ is a counter-example.

• How interested are you in the specific problem you have asked, versus whatever problem you are actually trying to solve? Anyways, except for some extremely specialized applications (e.g. tables of keywords for compilers) hash functions are pretty much never bijective, especially once you put realistic constraints on them (e.g. indexing into a table of length less than the set of all possible keys). – user14972 Mar 3 '13 at 10:13
• @Hurkyl I'm asking more out of curiosity rather than any practical application at this point. So I'm just interested in the specific problem. – Ankit Soni Mar 3 '13 at 10:37
• It doesn't even have to be practical; e.g. your exposition suggests it's plausible you're more interested in the problem of how to write hash functions that give the same value to all permutations of the input. – user14972 Mar 3 '13 at 13:31

Just fix a different prime number $p(r)$ for each $r\in [a,b]$. Then, the function $$H(\text{"}r_1\ldots r_n\text{"}):=p(r_1)\cdot\ldots\cdot p(r_n)$$ is of the required property. (It is also enough that $p(r)$'s are pairwise coprime.)