1
$\begingroup$

Let $n\in\mathbb{N}$ and let $q\in[n,2n]$ be a prime number.

In addition, let $s,s':\mathbb{F}_q\to\mathbb{F}_q$ be polynomials of degree $\sqrt{n}$ such that $s\neq s'$.

From the Schwartz–Zippel lemma (or simply because $s-s'$ is also a polynomials of degree $\sqrt{n}$, thus is has at most $\sqrt{n}$ roots) we know that $$\Pr_{r\in \mathbb{F}_q}[s(r)=s'(r)]\leq\frac{\sqrt{n}}{q}\leq\frac{1}{\sqrt{n}}$$

What is the best upper bound I can give for the probability over $r$ which is uniformly picked out of $\{1,\ldots,\sqrt{n}\}$ ? That is $$\Pr_{r\in \{1,\ldots,\sqrt{n}\}}[s(r)=s'(r)]\leq\quad?$$

1 Answers 1

2

It seems to me that we are at liberty to choose the polynomials $s$ and $s'$. So let's select $s'=0$ and $$s(x)=(x-1)(x-2)\cdots(x-[\sqrt{n}]).$$ Then $s(r)=s'(r)$ for all $r$ in the given range,and both these polynomials meet your bound on their degree. Thus the upper bound $Pr()\le 1$ can be attained, and is therefore the best bound.

Or did you want to ask something else?

  • 0
    Of course, foolish of me. Thanks !2011-10-04