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. Tha$n$ks !2011-10-04