Wan: Partial Counting of Rational Points over Finite Fields

We are motivated by the following problem. Let $\mathbb{F}_{q^d}=\mathbb{F}_q[\alpha]/h(\alpha)$, where $h$ is irreducible of degree $d>1$ over $\mathbb{F}_q$. We look at the group

$$G=\langle a-\alpha:a \in \mathbb{F}_q \rangle =(\mathbb{F}_{q^d}^*)^I \subset \mathbb{F}_{q^d}^*,$$

where $I=[\mathbb{F}_{q^d}^*:G]$. When does $I=1$, for example?

Let $D \mid (q^d-1)$, and let

$$N=\char93 \{(x,y):x-\alpha=y^D,x \in \mathbb{F}_q,y \in \mathbb{F}_{q^d}\}.$$

By a character sum argument counting, you can write this as

$$N=\sum_{\substack{\phi:\mathbb{F}_{q^d}^* \to \mathbb{C}^* \phi^D=1}} \sum_{x \in \mathbb{F}_q} \phi(x-\alpha).$$

By the Riemann hypothesis (Weil), we have $\vert N-q\vert \leq (D-1)(d-1)\sqrt{q}$. Therefore we have seen:

Proposition. Let $S \subset \mathbb{F}_q$. Let $G_S=\langle a-\alpha:a \in S \rangle =(\mathbb{F}_{q^d}^*)^{I_S}$. Then

$$(\char93 S)I_S \leq N \leq q+(I_S-1)(d-1)\sqrt{q}.$$

If $(\char93 S) > (d-1)\sqrt{q}$, then

$$I_S \leq \frac{q-(d-1)\sqrt{q}}{(\char93 S)-(d-1)\sqrt{q}}.$$

In particular, if $(\char93 S)=q$, then $I_S=1$ and $G=\mathbb{F}_{q^d}^*$.

Therefore we consider the problem: Can we compute $N$ in time polynomial in $d$, $D$, and $\log q$?

The general setup: Let $f(x_1,\dots,x_n) \in \overline{\mathbb{F}_q}[x_1,\dots,x_n]$, and $d_1,\dots,d_n \geq 1$. We want to count

$$N_{d_1,\dots,d_n}(f)=\char93 \{(x_1,\dots,x_n):f(x_1,\dots,x_n)=0, x_i \in \mathbb{F}_q^{d_i}\}.$$

Can we compute $N_{d_1,\dots,d_n}(f)$, or at least estimate it? How does this quantity vary when the $d_i$ vary?

For example, we consider the Artin-Schreier hypersurface. Let

$$f(x_1,\dots,x_n,y_1,\dots,y_{n'}) \in \mathbb{F}_q[x_1,\dots,x_n,y_1,\dots,y_{n'}],$$

where $n,n' \geq 1$. For each $d \geq 1$, we consider

$$N_d(f) = \char93 \{(x_0,\dots,x_n,y_1,\dots,y_{n'}):x_0^p-x_0=f(x_1,\dots,x_n,y_1,\dots,y_{n'}),$$

$$\qquad\qquad x_i \in \mathbb{F}_{q^d}, y_j \in \mathbb{F}_q\}.$$

Heuristically (for suitable $f$), we expect

$$N_d(f)=q^{dn+n'}+O(q^{(dn+n')/2})$$

where the constant depends on $p$, $f$, and $d$.

Theorem. [Deligne] Write $f=f_m+f_{m-1}+\dots+f_0$, where $f_i$ are homogeneous of degree $i$. Assume $f_m$ defines a smooth projective hypersurface in $\mathbb{P}^{n+n'-1}_{\mathbb{F}_q}$, and that $p \nmid m$, $d=1$. Then

$$\vert N_1(f)-q^{n+n'}\vert \leq (p-1)(m-1)^{n+n'} q^{(n+n')/2}.$$

What about $d>1$?

Definition. If $d \geq 1$, we define the $d$th fibred sum of $f$ to be

$$\textstyle{\bigoplus}_y^d f=f(x_{11},\dots,x_{1n},y_1,\dots,y_{n'})+\dots+f(x_{d1},\dots,x_{dn},y_1,\dots,y_{n'}).$$

Theorem. [Fu-W] Write $f=f_m+\dots+f_0$, and assume that $\bigoplus_y^d f_m$ is smooth in $\mathbb{P}^{dn+n'-1}_{\mathbb{F}_q}$ and $p \nmid m$. Then

$$\vert N_d(f)-q^{dn+n'}\vert \leq (p-1)(m-1)^{dn+n'}q^{(dn+n')/2}.$$

Example. In the case that we can write

$$f(x,y)=f_{1m}(x_1,\dots,x_n)+f_{2m}(y_1,\dots,y_{n'})+f_{\leq m-1}(x,y),$$

and $f_{1m}$ is smooth in $\mathbb{P}_{\mathbb{F}_q}^{n-1}$, $f_{2m}$ is smooth in $\mathbb{P}^{n'-1}_{\mathbb{F}_q}$. Then $\bigoplus_y^d f_m$ is smooth in $\mathbb{P}_{\mathbb{F}_q}^{dn+n'-1}$ if and only if $p \nmid d$.

Since the condition that the fibred sum be smooth is Zariski open, we have shown it is nonempty if $p \nmid d$ and therefore there exist many examples of such $f$ to which the theorem applies.

Definition. Let $M_d$ be the set of $f$ over $\overline{\mathbb{F}_q}$ such that $\bigoplus_y^d f_m$ is smooth. Then $M_d$ is Zariski open in the set of all $f$ over $\overline{\mathbb{F}_q}$ with $\deg f \leq m$.

Theorem. [Gao-W] $M_d$ is Zariski dense if and only if $p \nmid d$. In fact,

$$\bigcap_{\substack{d=1 p \nmid d}}^{\infty} M_d=\bigcap_{\substack{d=1 p \nmid d}}^{p^{(m-1)^n}} M_d$$

and this intersection is Zariski open and dense.

Problem. What about Kummer hypersurfaces

$$x_0^D=f(x_1,\dots,x_n,y_1,\dots,y_n')$$

where $x_i \in \mathbb{F}_{q^d}$ and $y_j \in \mathbb{F}_q$?

Remark. We expect $\vert N_d-q^{dn+n'}\vert=O(q^{(dn+n')/2})$, but one can get the weaker estimate $O(q^{dn/2+n'-1/2})$ in many cases (Katz).

Now we consider partial zeta functions over $\mathbb{F}_q$. Let $f(x_1,\dots,x_n) \in \mathbb{F}_q[x_1,\dots,x_n]$, $d_1,\dots,d_n \geq 1$. Define

$$Z_{d_1,\dots,d_n}(f,T)=\exp\left(\sum_{k=1}^{\infty} N_{d_1,\dots,d_n,k} \frac{T^k}{k} \right)$$

where

$$N_{d_1,\dots,d_n,k}=\char93 \{(x_1,\dots,x_n):f(x_1,\dots,x_n)=0,x_i \in \mathbb{F}_{q^{d_ik}}\}.$$

Without loss of generality, we may assume $\gcd(d_1,\dots,d_n)=1$, since otherwise we can just enlarge the ground field $\mathbb{F}_q$.

Proposition.

1. If $d_1 \mid \dots \mid d_n$, then $Z_{d_1,\dots,d_n}(f,T) \in \mathbb{Q}(T)$.

2. (Faltings) $Z_{d_1,\dots,d_n}(f,T)=\prod_{i=1}^d P_i(T)^{\zeta_d^i}$, where $d={\mathrm{lcm}}(d_1,\dots,d_n)$ and $\zeta_d$ is a primitive $d$th root of unity, $P_i(T) \in \overline{\mathbb{Q}}(T)$, and $P_i(0)=1$.

By exponentiation to a root of unity, we mean the formal binomial expansion. From a counting point of view, this is `as good as rational'.

Theorem. In all cases, $Z_{d_1,\dots,d_n}(f,T) \in \mathbb{Q}(T)$.

Proof. Let $X^d=\underbrace{X \times \dots \times X}_d$. We have a map

$$\sigma:X^d \to X^d$$

$$(x^{(1)},\dots,x^{(d)}) \mapsto (x^{(d)},x^{(1)},\dots,x^{(d-1)})$$

Faltings constructs a large subvariety $Y_{d_1,\dots,d_n} \hookrightarrow X^d$ which is stable under $\sigma$. Then

$$N_{d_1,\dots,d_n}(f)=\char93 \textup{Fix}(\sigma \circ {\mathrm{F... ...} (-1)^i {\mathrm{Tr}}(\sigma \circ {\mathrm{Frob}}\vert H^i_c(\overline{Y})).$$

Note $\sigma \circ {\mathrm{Frob}}_q={\mathrm{Frob}}_q \circ \sigma$. This implies Faltings' `near' rationality as in the proposition.

Now $Z_{d_1,\dots,d_n}(f,T) \in 1+T\mathbb{Q}[[T]]$. We refine the above argument as follows. First, for $\gcd(a,d)=1$, you have

$$N_{d_1,\dots,d_n}(f)=\char93 {\mathrm{Fix}}(\sigma^a \circ {\mathrm{Frob}}_q\vert Y(\overline{\mathbb{F}_q})).$$

We consider $Y \to Y/G$, where $G=\langle \sigma \rangle \cong \mathbb{Z}/d\mathbb{Z}$. We have a character $\chi:G \to \mathbb{C}^*$, and define the $L$-function

$$L(\chi,T)=\exp\left(\sum_{k=1}^{\infty} \frac{T^k}{k}\left(\frac{... ...\tau \circ {\mathrm{Frob}}_q^k\vert Y(\overline{\mathbb{F}_q}))\right)\right).$$

By Grothendieck, $L(\chi,T) \in \mathbb{Q}(\zeta_d)(T)$. This implies that

$$Z_{d_1,\dots,d_n}(f,T)^{\phi(d)}=\prod_{\chi \in \widehat{G}} L(\chi,T)^{\sum_{\gcd(a,d)=1}\chi(\sigma)^a} \in \mathbb{Q}(\zeta_d)(T)$$

so $Z_{d_1,\dots,d_n}(f,T) \in \mathbb{Q}(T)$ (essentially by unique factorization). $\qedsymbol$

Open problem: can you bound the total degree of $Z_{d_1,\dots,d_n}(f,T)$? The best bound we have is $3 \cdot 2^{d+1}(3+dm)^{d_1+\dots+d_n+1}$, $m=\deg f$. Can this be improved to $O(d)^{O(1)}$? Yes, if $d_1=\dots=d_r=d$ and $d_{r+1}=\dots=d_n=1$ (Fu-W).

Back to the main index for Future directions in algorithmic number theory.