Zeta of x²+y²=1 over finite fields

Wednesday, July 18th, 2012 | Author:

I must admit that I have a weak background in elementary number theory. A few weeks ago I wanted to count the number of points of the affine circle x^2+y^2=1 over finite fields, by counting the point of the completed curve and the points at infinity. There one needs to decide whether a finite field with p^k elements contains roots of -1 or not.

Gaussian integers

When Gauss introduced the Gauss numbers \mathbb{Z}[i] (where i is a root of -1), he observed that a prime integer p might not be prime in the Gauss numbers, but it may factor in a product of primes. He could see that a prime p factors in two primes ("splits completely") exactly if it is congruent to 1 modulo 4, and it stays prime ("is inert") if it is congruent to 3 modulo 4. The cases that a prime is congruent to 0 or 2 modulo 4 doesn't happen that much, because that already implies that the prime is divisible by 2, which can happen only for 2 itself, which is handled separately: it factors as 2=-i(i+1)^2. Because there are multiplicities (the square appearing), one calls this case "ramified" (note that -i is a unit, i.e. invertible in the Gauss numbers, with inverse i).

To calculate some concrete examples, we need to know that i+1 is prime in the Gauss numbers. To see that, we observe that in \mathbb{Z}[i]/(i+1), the number i is both equal to -1 and to a square root of -1, so we have the equation -1 = -1^2 = 1, which implies that the quotient ring has characteristics 2 and is in fact equal to \mathbb{Z}/2\mathbb{Z}, a field. This shows that (i+1) was a maximal ideal, hence a prime ideal, so i+1 is prime.
Similarly, we can compute that 2i+1 and 2i-1 are prime by showing that \mathbb{Z}[i]/(2i\pm 1) is a ring where the equation 4=-1 holds, and indeed is equal to \mathbb{Z}/5\mathbb{Z}, a field. With the same method, you can show 2\pm 3i and 1+4i are prime.
We can also show that 3, 7 and 11 are inert, by proving that \mathbb{Z}[i]/(3), \mathbb{Z}[i]/(7) and \mathbb{Z}[i]/(11) are integral domains (without zero divisors).

Now we can summarize

  •  2 = -i(i+1)^2 (ramified)
  •  3 = 3 (inert)
  •  5 = (1+2i)(1-2i) (splits)
  •  7 = 7 (inert)
  •  11 = 11 (inert)
  •  13 = (2+3i)(2-3i) (splits)
  •  17 = (1+4i)(1-4i) (splits)

one could continue further, but it seems that the pattern is already visible.

One small note aside: One can also write 5 = (2+i)(2-i), but since (1-2i)*i = (i+2) and i is a unit in the Gaussian integers, that doesn't mean we don't have unique factorization (in fact, we do have unique factorization, which can be shown by doing the Euclidean algorithm).

Fermat's theorem on sums of two squares says that an odd prime p (i.e. p \neq 2) can be written as p = x^2+y^2 with integers x and y, if and only if p is congruent to 1 modulo 4. In the Gaussian integers \mathbb{Z}[i], we have i^2 = -1, hence from the binomial law (x+y)(x-y) = x^2-y^2 we can infer (x+iy)(x-iy) = x^2+y^2. Since no integer prime divides another integer prime (by definition), we know that any splitting prime p must split as a product of Gaussian integers which contain an imaginary part. The binomial formula is also the only hope to write an integer prime as product of Gaussian primes, since any product of two different Gaussian primes, which are not conjugate, would have an imaginary part. So we see that the theorem announced before is essentially equivalent to Fermat's theorem on sums of two squares.

Fermat didn't prove this theorem, as usual, but others did. Euler, Goldbach and Lagrange did the first proofs, Gauss and Dedekind also proved it, partly because of their interest in Gaussian integers. Zagier gave a one-sentence proof (it's a rather long sentence), and it seems to puzzle the reader on first sight.

Counting square roots of -1 in finite fields

The ring \mathbb{Z}/n\mathbb{Z} is a field if and only if n is a prime integer. In these cases we write \mathbb{F}_p for the unique field with p elements. Now my question is: for which values of p does such a field contain an element x that squares to -1, i.e. plays the role of i? Such an element is also called quadratic residue. One could also phrase the question as: is -1 a square in \mathbb{F}_p? The same question can be stated without talking about finite fields, just asking whether there exists an integer x such that x^2 \cong -1 (\text{mod } p).

Some examples:

  •  1^2 = 1 \equiv -1 (\text{mod } 2)
  • modulo 3, there is no square root of -1
  •  2^2 = 4 \equiv -1 (\text{mod } 5)
  • modulo 7, there is no square root of -1
  • modulo 11, there is no square root of -1
  •  5^2 = 25 \equiv -1 (\text{mod } 13)
  •  4^2 = 16 \equiv -1 (\text{mod } 17)

and we see already a similar pattern as above.

Theorem: There exists a square root of -1 modulo p if and only if p is even or p is 1 modulo 4.
This theorem is a special case of the more general quadratic reciprocity law.

So we can count the number of square roots of -1 in a finite field with p elements (p prime) to be either 0 (the case p is not 1 modulo 4) or 2 (the case p is 2 or p is 3 modulo 4).

The next thing to do is to consider field extensions of the prime fields \mathbb{F}_p. By adjoining a p-th root of unity to \mathbb{F}_p, we get a field extension of degree p, called \mathbb{F}_{p^2}, with exactly p^2 many elements. Warning: \mathbb{F}_{p^2} \neq \mathbb{Z}/p^2\mathbb{Z}, the latter isn't even a field.
Of course, if \mathbb{F}_p contained a square root of -1, it is still there, and we can't get more, but is it possible that \mathbb{F}_p doesn't contain a square root of -1, while \mathbb{F}_{p^2} does? Yes, indeed.

The general criterion is much simpler than Fermat's sum-of-squares theorem. Since (-1)^2 = 1, any square root x of -1 will satisfy x^4 = 1, so it will be an element of order 4 of the multiplicative group of the field. Observe that -1 is the only element of order 2 in any finite field, since it is the unique solution of X^2-1=0 besides 1 itself. The finite field \mathbb{F}_{p^k} contains p^k many elements and the multiplicative group is just the same set without 0 (remember, in a field, everything besides 0 is invertible), so the unit group has number of elements |\mathbb{F}_{p^k}^\times| = p^k-1. Now Lagrange's theorem in group theory tells us that the order of an element has to divide the order of the group and furthermore, that a group whose order is divided by a certain number contains a subgroup with this number as order. In our case, this means:
The group \mathbb{F}_{p^k}^\times has an element of order 4 if and only if 4 divides p^k-1, in other words: p^k \equiv 1 (\text{mod } 4). In particular, the finite field with n elements has a square root of -1 if and only if n \equiv 1 (\text{mod } 4).

Application to the Zeta function of the affine circle

Let X := \{x^2+y^2=1\} \subset \mathbb{A}^2 be the affine "circle". We can compactify it to \overline{X} := \{x^2+y^2-z^2\} \subset \mathbb{P}^2, then counting the points of \overline{X} and of \overline{X}\setminus X over finite fields yields a computation of the number of points of X. It turns out that this is easy, since we can write down a stereographic projection of \overline{X} to \mathbb{P}^1 which is an isomorphism (try it!) and determine the points of \overline{X}\setminus X by the stuff from above.

The number of points of \mathbb{P}^1 is given by one plus the number of points of \mathbb{A}^1, so in general we have |\mathbb{P}^1(\mathbb{F}_{p^n}| = 1 + p^n.
By the way, this yields the Zeta function

 Z(\mathbb{P}^1,s) = exp \sum_{n=1}^\infty \left(|\mathbb{P}^1(\mathbb{F}_{p^n}|\frac{s^n}{n}\right) = exp(-log(1-s)-log(1-ps)) = \dfrac{1}{(1-t)(1-pt)}.

The number of points of \overline{X} \setminus X is given by the number of solutions of x^2+y^2-z^2=0 such that [x:y:z] is not in the coordinate chart z\neq 0, where all of X lies, in other words we have to count solutions of x^2+y^2 = 0 over \mathbb{F}_{p^n}. This is the same as solutions of \left(\frac{x}{y}\right)^2 = -1, so we can instead count the square roots of -1 over \mathbb{F}_{p^n}. We did that already.

So it turns out that |X(\mathbb{F}_{p^n})| = 1 + p^n - \begin{cases} 2 & n \equiv 1 (\text{mod } 4) \\ 0 & \text{ otherwise } \end{cases}
and we get the Zeta function

 Z(X,s) = exp\left( \sum_{n=1}^\infty (1+p^n)\frac{s^n}{n} - 2 \sum_{k=0}^\infty \frac{s^{4k+1}}{4k+1} \right),

which can be simplified further (using the derivative \frac{d}{ds} log(x) = \frac{1}{x} and the geometric series \sum_{k=1}^\infty x^k = \frac{1}{1-x} for |x|<1 to get log(1-x) = \sum_{k=1}^\infty \frac{x^k}{k}) to

 Z(X,s) = Z(\mathbb{P}^1,s) \cdot exp\left( -tan^{-1}(s) -tanh^{-1}(s) \right)

 = Z(\mathbb{P}^1,s) \cdot \left( \dfrac{1+is}{1-is} \right)^{\frac{i}{2}} \left( \dfrac{1-s}{1+s} \right)^{\frac{1}{2}}

and there I'm not that sure I did all calculations right... so you better check that!

Category: English, Mathematics

Comments are currently closed.