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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

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

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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

$\displaystyle N_d(f)$ $\displaystyle = \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'}),$    
  $\displaystyle \qquad\qquad x_i \in \mathbb{F}_{q^d}, y_j \in \mathbb{F}_q\}.$    

Heuristically (for suitable $ f$), we expect

$\displaystyle 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

$\displaystyle \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

$\displaystyle \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

$\displaystyle \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

$\displaystyle 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,

$\displaystyle \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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

$\displaystyle \sigma:X^d$ $\displaystyle \to X^d$    
$\displaystyle (x^{(1)},\dots,x^{(d)})$ $\displaystyle \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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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.