5
$\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$ Commented Apr 29, 2016 at 21:40
  • $\begingroup$ @JasonStarr, yes $\endgroup$ Commented Apr 29, 2016 at 21:42

1 Answer 1

6
$\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
    Commented Apr 30, 2016 at 9:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .