One of the structures investigated in finite geometry are related to quadratic forms over finite fields (see below for definitions). Knowledge on the geometry of singular points of quadratic forms is very common and covered in many textbooks on finite geometry, but one cannot say the same for the geometry on non-singular points. This short post tries to amend this a little.
(This is no surprise as the geometry with singular points is much nicer than the geometry associated with various types of non-singular points. Also, everything in the following is well-known for decades. It is simply a bit more obscure than other facts about finite quadrics. Lastly, my title is a terrible pun on slang from the mid-20th century (and Pulp Fiction).)
1. Quadratic Forms and Quadrics
First a very abridged introduction to quadratic forms. There are many places for proper introductions to the topic, for instance Akihiro Munemasa’s notes.
A map from a vector space over a field to is a quadratic form if it satisfies for and all and is a bilinear form. Think of and .
Now suppose that the characteristic of is not two. We can write for a real symmetric matrix . Then . That means that we can reconstruct from (this does not work in even characteristic). The form is nondegenerate if and degenerate if . Think of as an example of a nondegenerate quadratic form and as an example for a degenerate quadratic form (both for ). Being degenerate is equivalent to the existence of a non-zero vector such that for all .
2. Counting on a Line
Now let be the finite field with elements.
Consider the case , so . For simplicity, we assume that . (You can rewrite in that way by some basis transformation. Note that stays a square or non-square while doing this — we will implicitely assume this later.) Projectively, for we have a line with points, so we limit ourselves to the representatives of the points of the form and . Then can have these numbers of solutions:
- if . Then is degenerate. (Case A)
- if and . Then is also degenerate. (Case B)
- if is a square. (Case C)
- if is a non-square. (Case D)
A projective points is called singular if . We see that the number of singular projective points (here or ), is (in the same ordering as above) , , , or . We call these lines singular, tangents, secants, and exterior lines.
Of course all we did so far is to state something which you know since high-school: quadratic equations have 0, 1, or 2 solutions.
Now (to go beyond high-school math) we can do the same for being a square (or a non-square). Note that because of , it does not matter which representative we choose for a projective point . Squares stay squares, non-squares stay non-squares. Here we will choose our such that the calculations are convenient. One can always achieve this with a suitable basis transform.
Obviously, for Case A. For Case B, we take . For Case C, is a good choice. For Case D, we identify with and take the norm map . This is a quadratic form as for , . Now let us count for how many projective points we have that is a non-zero square.
We have the following cases:
- in Case A.
- if is a square in Case B.
- if is a non-square in Case B. Conceptionally, choosing a nice basis such that and is probably nicer. Then we see that is a square (for ) if and only if is a square.
- for Case C: For , we have a non-zero square which happens times.
- for Case D: Count all with . It is easy to see that one has solutions (write as a cyclic group to see this), but projectively each two of these solutions correspond to the same point, so we have to divide by .
We that (in the same ordering as above) that a projective line contains , , , , and non-zero square points. The numbers are , , , , and for non-square points.
So now we can count square and non-square points on lines. Particularly, note that a tangent either contains only square or only non-square non-singular points.
3. Counting in the Whole Space
Now let us go back to the whole space. The number of singular points of a nondegenerate quadratic form is well-known. If is odd, then it is . If is even, then it is . Here if is a square and if it is a non-square. Let us call the number of singular points .
For a vector , the space is also well understood. Here we only care about the case . Then is nondegenerate. It has singular points if is even and if is odd, where solely depends on square and square (more precisely, ). Here, we do not care too much about particular numbers, so let us simply denote the number of singular points in by . Note that for , is a tangent if and only if .
We conclude this blog post by counting all non-zero square points. Suppose that . Then there are lines through . Of these lines are tangents and are secants, so lines through x are exterior lines. Hence, for the total number of non-zero square points in our space we obtain
This is actually a nice number, but the sole purpose of this post is to point out that counting squares and non-squares in quadratic spaces is straightforward.
4. Strongly Regular Graphs
Researchers in the literature either know a variation of the above and consider it trivial. In the second case, they simply write down the result of their counts of square or non-square without elaborating on the details. This then puzzles researchers in the first category, as they feel that any proof or explanation is missing. It is tricky to find a good compromise. This work on some cliquefree pseudorandom graphs is aimed at extremal combinatorialists who on average do not know any of the above. Our solution was that we refered to earlier (probably, hard to read) work with the exact details, but we included a short sketch of the above, so that (hopefully) the readers believe our claims on the number of squares.
The above construction also plays a role in this paper by me and Akihiro Munemasa on graph switching. But there our audience are experts in strongly regular graphs, so we did not feel the need to explain details. (Indeed, the graphs considered in Section 6 of the paper with Akihiro Munemasa are include all graphs which are constructed in the cliquefree pseudorandom graphs paper, just in a very different notation.)
But, to get to the header of this section, historically, these counts are relevant to construct strongly regular graphs. Let us get to that. Define a graph with all vectors of as vertices with two vertices adjacent if is a non-zero square. If is even, then this defines a strongly regular graph. This was remarked by Calderbank and Kantor as example FE1 in their seminal paper “The geometry of two-weight codes” from 1986 in the context of a much more general method for constructing strongly regular graphs. To see that their construction is correct, you need to be able to count non-zero square points. The purpose of the discussion above is to illustrate that this is very straightforward. This family of graphs is denoted as by Brouwer in his tables online, in his survey for the Handbook of Combinatorial Designs, and in his upcoming book on strongly regular graphs (together with van Maldeghem).