# Lower bound for the Schwartz–Zippel lemma in Polynomial Hashing

$$\newcommand{\bigparen}[1]{\Bigl ( #1 \Bigr )}$$

I'm working with polynomial hashes $$H$$ defined by the pair $$(B, M)$$ (base, modulo):

$$H_{B, M}(s) \equiv \sum_{i=0}^{n-1} B^{n-1-i} \cdot conv(s_i) \, (mod \, M)$$

The conversion function is conv(c) = c - 'a' + 1 (work only with lowercase letters). I work with strings of different lengths.

The scheme I use to guarantee a small enough collision probability takes a fixed modulo (in this case the largest Mersenne prime that fits in $$8$$ bytes, $$2^{61} - 1$$), and chooses one uniformly random base from the set $$\{26 + 1, ..., 2 ^ {61} - 2\}$$.

The probability for any two different strings $$s$$, $$t$$:

$$P\bigparen{H(s) \equiv H(t) \, (mod \, M)} = P\bigparen{\sum_{i=0}^{n-1} B^{n-1-i} \cdot (conv(s_i) - conv(t_i)) \equiv 0 \, (mod \, M)} \leq \frac{n-1}{M}$$

Since the left side is a $$n-1$$-degree polynomial in a randomly chosen variable, the base $$B$$ (Schwartz–Zippel lemma).

At one point in my algorithm I'm sorting $$n \log_2 n$$ hashes, so an upper bound for the probability of collision would be:

$$1 - \bigparen{1 - \frac{n - 1}{M}} ^ {\lceil n \log_2 n \rceil \choose 2}$$

That is too high (for $$n = 10^5$$ it's $$22\%$$). In order to get a good bound with this scheme, I need to randomly pick two distinct bases. I'd rather not do this because of the noticeable slowdown in memory access times.

However, in practice, I would expect the probability that two hashes would collide to be much closer to $$\frac{1}{M}$$ (uniform spread over the codomain) than $$\frac{n-1}{M}$$.

Supposing that I can pick $$B$$ such that $$B^i \not\equiv B^j \, (mod \, M) \,\, \forall \,\, 0 \leq i \lt j \lt n$$, could there be a better upper bound out there for the probability of the hashes ($$H_{B, M}, B$$ chosen randomly, $$M$$ fixed and prime) of any two strings colliding than $$\frac{n-1}{M}$$? Maybe some other initial conditions could help.

Thank you.

I think a pragmatic approach would be to use a PRF (see also here) instead of a polynomial hash, because then you can say that the collision probability is $$1/M$$ (unless someone figures out how to break the crypto). Or, alternatively, to use a 128-bit hash rather than a 64-bit hash; maybe Poly1305.
I wouldn't set your hopes too high on proving a better bound. My intuition is that the collision probability is probably more like $$(n-1)/M$$, not $$1/M$$, as a random polynomial of degree $$n-1$$ has on average about $$n-1$$ unique roots modulo $$M$$. Note that the hashes can still be uniformly distributed across the codomain: it is the difference between the probability distribution with respect to a random choice of $$B$$, vs the probability distribution with respect to a random choice of input string.