1
$\begingroup$

In CLRS it is stated that the class $\mathcal{H}_{p, m} = \{ h_{ab}:\mathbf{Z}_p \to \mathbf{Z}_m \mid a \in \mathbf{Z}_p^*, b \in \mathbf{Z}_p\}$, $h_{ab}(x) = (ax+b) \mod p \mod m$, $m < p$ prime has $p(p-1)$ members. However, I don't see why some of these functions couldn't turn out to be the same. I've investigated on my own, and found that keeping $b$ fixed, all $a \in \mathbf{Z}_p^*$ do indeed give different functions; I take $b = 0$ and then show that if $h_{a0}^{-1}(m\mathbf{Z} \cap \mathbf{Z}_p) = \{x, 2x, \ldots, rx\}$ and $h_{a'0}^{-1}(m\mathbf{Z} \cap \mathbf{Z}_p) = \{y, 2y, \ldots, ry\}$, $r = \lfloor p/m \rfloor$, then since $r < p/2$ and $\mathbf{Z}_p = \{x, 2x, \ldots, rx, (r+1)x, \ldots, px\}$, writing $cx = y$ we'll have some $d$ with $dcx = dy \notin \{x, 2x, \ldots, rx\}$, i.e. sets $\{x, 2x, \ldots, rx\}$ and $\{y, 2y, \ldots, ry\}$ are different, i.e. $h_{a'0} \neq h_{b'0}$. (I apologize for messy shorthand.)

But I have no idea how to extend this to arbitrary $(a, b)$ and $(a', b')$, and somewhat doubt if it's worth it. (Maybe there's a simpler way of looking at this?) Nonetheless I intensely dislike the feeling of having to take such things on faith, and there's maybe something elementary that i'm missing, so I'm asking for help.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

The claim is false in general. If $p=3$ and $m=2$, there are only 3 such functions, as can be found by enumeration. For instance, $h_{1,2}(x) = h_{2,0}(x)$ for all $x$.

It seems very plausible to me that there might exist some constant $c_0$ such that the claim is true for all $p>m>c_0$. I doubt there's a simple proof. Heuristically, we can expect this to be true. There are $m^p$ functions with the signature $\mathbf{Z}_p \to \mathbf{Z}_m$, and $p(p-1)$ choices of $a,b$, so by a birthday paradox style argument, if we heuristically model each function $x \mapsto (ax+b) \bmod p \bmod m$ as a random function with signature $\mathbf{Z}_p \to \mathbf{Z}_m$, then the probability of there existing any collision (any pair of such functions that are identical) is exponentially small once $m$ is large enough. In particular, the probability they are all different is (under this assumption) about

$$p \approx \exp\{-p^2(p-1)^2/(2 \cdot m^p)\},$$

which when $p \ll m^{p/4}$ is about

$$p \approx 1 - {p^2(p-1)^2 \over 2 \cdot m^p}.$$

This is exponentially close to 1, once $m$ is large enough. This is not a proof, this is just a heuristic, as it treats each function as a random function (uniformly distributed across all possible functions of that signature), which is in reality not correct.

I doubt it matters much whether there are exactly $p(p-1)$ such functions or not.

I do want to validate your reactions of dislike having to take things on faith, and your failure to find find a simple way to prove such a claim.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.