4
$\begingroup$

Let $X $ be a smooth affine subvariety of $(\overline{\mathbb{F}_q})^n$ defined by a prime ideal $I$. Let $f$ $\in \mathbb{F}_q[x_1,\ldots,x_n]$ be a polynomial such that $f \notin I$.

Let $r_1, \ldots, r_m$ be selected independenty and uniformly among all $\mathbb{F}_{q^k}$-rational points of $X$ for some big $k$.

Is it true that $\Pr[f(r_1)=0, \ldots, f(r_m) =0]$ is small for rather big $m$?

It would be a generalization of
Schwartz-Zippel lemma:

Lemma (Schwartz, Zippel).
Let $P\in F[x_1,x_2,\ldots,x_n]$ be a non-zero polynomial of total degree $d \geq 0$ over a field, $F$. Let $S$ be a finite subset of $F$ and let $r_1, r_2, \dots, r_n$ be selected at random independently and uniformly from $S$.
Then $\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$

UPD: I think I have understood why this must be true: $f \cap V$ is the variety with smaller dimension than $V$ and it has much smaller $\mathbb{F}_{q^k}$-rational points than $V$ (Number of rational points in a non-smooth variety). However I can not get an explicit estimation...

$\endgroup$
2
  • $\begingroup$ Just to clarify, "Pr" means "probability"? $\endgroup$ – Jason Starr Apr 29 '16 at 21:40
  • $\begingroup$ @JasonStarr, yes $\endgroup$ – Alexey Milovanov Apr 29 '16 at 21:42
5
$\begingroup$

Let $d=\dim(X)$ and let $Y=X\cap\{f=0\}$, so $\dim(Y)=d-1$. Then the Lang-Weil estimate says that $\#X(\mathbb F_{q^k})=q^{dk} + O(q^{k(d-1/2)})$, and applying it to each irreducible component of $Y$ gives $\#Y(\mathbb F_{q^k})=O(q^{(d-1)k})$. Your probability is the ratio $\#Y(\mathbb F_{q^k})^m/\#X(\mathbb F_{q^k})^m$, if I understand correctly, which equals $O(C^mq^{-mk})$, which is indeed small when $m$ is large, provided you choose $k$ large enough. If you want to include an error term, which would of course depend on the ideal defining $X$ and the function $f$ defining $Y$, then the big-$O$ constant may be taken to be the number of components $\nu(Y)$ of $Y$, i.e., something like $\text{Prob}\le \nu(Y)^mq^{-mk}+O(q^{-(m+1/2)k})$

$\endgroup$
1
  • 1
    $\begingroup$ If one needs to fix $q$, one can also use the following standard bound for the number of $\mathbf F_q$ points of a closed subscheme $X$ of $\mathbf P^n$: $\mathop{\rm Card}(X(\mathbf F_q))\leq \deg(X) \mathop{\rm Card}(\mathbf P^{\dim(X)}(\mathbf F_q)$. (Applied to $Y$, whose degree is $\deg(f)\deg(X)$ and dimension $\dim(X)-1$. This requires to know that $X(\mathbf F_q)$ is larger enough, as in Schwartz-Zippel's lemma.) $\endgroup$ – ACL Apr 30 '16 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.