Don’t be a Square (but count them)

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 $ {Q}$ from a vector space $ {V}$ over a field $ {\mathbb{F}}$ to $ {\mathbb{F}}$ is a quadratic form if it satisfies $ {Q(kx) = k^2 Q(x)}$ for $ {k \in \mathbb{F}}$ and all $ {x \in V}$ and $ {B(x, y) = Q(x+y) – Q(x) – Q(y)}$ is a bilinear form. Think of $ {Q(x) = x_1^2 + \ldots + x_n^2}$ and $ {B(x, y) = x_1y_1 + \ldots + x_ny_n}$.

Now suppose that the characteristic of $ {\mathbb{F}}$ is not two. We can write $ {Q(x) = x^T M x}$ for a real symmetric matrix $ {M}$. Then $ {B(x, y) = (x+y)^T M (x+y) – x^TMx – y^TMy = 2x^TMy}$. That means that we can reconstruct $ {Q}$ from $ {B}$ (this does not work in even characteristic). The form $ {Q}$ is nondegenerate if $ {\det(Q) := \det(M) \neq 0}$ and degenerate if $ {\det(Q) = 0}$. Think of $ {Q(x_1, x_2) = x_1^2 + x_2^2}$ as an example of a nondegenerate quadratic form and $ {Q(x_1, x_2) = x_1^2}$ as an example for a degenerate quadratic form (both for $ {n=2}$). Being degenerate is equivalent to the existence of a non-zero vector $ {x}$ such that $ {B(x, y) = 0}$ for all $ {y \in V}$.

2. Counting on a Line

Now let $ {\mathbb{F}}$ be the finite field with $ {q}$ elements.

Consider the case $ {n=2}$, so $ {Q(x_1, x_2) = a_{11} x_1^2 + a_{12} x_1x_2 + a_{22} x_2^2}$. For simplicity, we assume that $ {a_{12} = 0}$. (You can rewrite $ {Q}$ in that way by some basis transformation. Note that $ {\det(Q)}$ stays a square or non-square while doing this — we will implicitely assume this later.) Projectively, for $ {n=2}$ we have a line with $ {q+1}$ points, so we limit ourselves to the representatives of the points of the form $ {(1, x_2)}$ and $ {(0, 1)}$. Then $ {Q(x) = 0}$ can have these numbers of solutions:

1. $ {q+1}$ if $ {a_{11} = a_{22} = 0}$. Then $ {Q}$ is degenerate. (Case A)
2. $ {q}$ if $ {a_{11} = 1}$ and $ {a_{22} = 0}$. Then $ {Q}$ is also degenerate. (Case B)
3. $ {2}$ if $ {-a_{11}/a_{22}}$ is a square. (Case C)
4. $ {0}$ if $ {-a_{11}/a_{22}}$ is a non-square. (Case D)

A projective points $ {\langle x \rangle}$ is called singular if $ {Q(x) = 0}$. We see that the number of singular projective points $ {\langle (x_1, x_2) \rangle}$ (here $ {x_1 \neq 0}$ or $ {x_2 \neq 0}$), is (in the same ordering as above) $ {q+1}$, $ {1}$, $ {2}$, or $ {0}$. 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 $ {Q(x_1, x_2)}$ being a square (or a non-square). Note that because of $ {Q(\lambda x) = \lambda^2 Q(x)}$, it does not matter which representative we choose for a projective point $ {\langle x \rangle}$. Squares stay squares, non-squares stay non-squares. Here we will choose our $ {Q}$ such that the calculations are convenient. One can always achieve this with a suitable basis transform.

Obviously, $ {Q = 0}$ for Case A. For Case B, we take $ {Q(x) = a_{11} x_1^2}$. For Case C, $ {Q(x) = x_1x_2}$ is a good choice. For Case D, we identify $ {\mathbb{F}_q^2}$ with $ {\mathbb{F}_{q^2}}$ and take the norm map $ {Q(x) = N(x) = x^{q+1}}$. This is a quadratic form as for $ {k \in \mathbb{F}}$, $ {N(kx) = k^{q+1} x^{q+1} = k^2 x^{q+1}}$. Now let us count for how many projective points we have that $ {Q(x)}$ is a non-zero square.

We have the following cases:

1. $ {0}$ in Case A.
2. $ {q}$ if $ {a_{11}}$ is a square in Case B.
3. $ {0}$ if $ {a_{11}}$ is a non-square in Case B. Conceptionally, choosing a nice basis $ {\{ e, f \}}$ such that $ {Q(e) = 0}$ and $ {B(e, f) = 0}$ is probably nicer. Then we see that $ {Q(e+tf) = Q(e) + t^2Q(f) = t^2Q(f)}$ is a square (for $ {t \neq 0}$) if and only if $ {Q(f)}$ is a square.
4. $ {(q-1)/2}$ for Case C: For $ {x_1=1}$, we have $ {x_2}$ a non-zero square which happens $ {(q-1)/2}$ times.
5. $ {(q+1)/2}$ for Case D: Count all $ {x}$ with $ {N(x) = 1}$. It is easy to see that one has $ {q+1}$ solutions (write $ {\mathbb{F}_{q^2}^*}$ 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 $ {2}$.

We that (in the same ordering as above) that a projective line contains $ {0}$, $ {q}$, $ {0}$, $ {(q-1)/2}$, and $ {(q+1)/2}$ non-zero square points. The numbers are $ {0}$, $ {0}$, $ {q}$, $ {(q-1)/2}$, and $ {(q+1)/2}$ 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 $ {n}$ is odd, then it is $ {(q^n-1)/(q-1)}$. If $ {n}$ is even, then it is $ {(q^{n/2-1}+\varepsilon)(q^{n/2} – \varepsilon)/(q-1)}$. Here $ {\varepsilon = 1}$ if $ {\det(Q)}$ is a square and $ {\varepsilon=-1}$ if it is a non-square. Let us call the number of singular points $ {\alpha}$.

For a vector $ {x}$, the space $ {x^\perp := \{ y: B(x, y) = 0 \}}$ is also well understood. Here we only care about the case $ {Q(x) \neq 0}$. Then $ {Q_{|x^\perp}}$ is nondegenerate. It has $ {(q^{n-1}-1)/(q-1)}$ singular points if $ {n}$ is even and $ {(q^{n/2-1} + \delta )(q^{n/2} – \delta)/(q-1)}$ if $ {n}$ is odd, where $ {\delta}$ solely depends on $ {\det(Q)}$ square and $ {Q(x)}$ square (more precisely, $ {\det(Q) = Q(x)\det(Q_{|x^\perp})}$). Here, we do not care too much about particular numbers, so let us simply denote the number of singular points in $ {x^\perp}$ by $ {\beta}$. Note that for $ {y \in x^\perp}$, $ {\langle x, y \rangle}$ is a tangent if and only if $ {Q(y) = 0}$.

We conclude this blog post by counting all non-zero square points. Suppose that $ {Q(x) = 1}$. Then there are $ {\gamma = (q^{n-1}-1)/(q-1)}$ lines through $ {x}$. Of these $ {\beta}$ lines are tangents and $ {\tfrac{\alpha-\beta}{2}}$ are secants, so $ {\gamma – \tfrac{\alpha+\beta}{2}}$ lines through x are exterior lines. Hence, for the total number of non-zero square points in our space we obtain

$ \displaystyle 1 + \tfrac{q-3}{2}\alpha + (q-1)\beta + \tfrac{q-1}{2} (\gamma – \tfrac{\alpha+\beta}{2}). $

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 $ {q^n}$ vectors of $ {\mathbb{F}_q^n}$ as vertices with two vertices $ {x,y}$ adjacent if $ {Q(x-y)}$ is a non-zero square. If $ {n}$ 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 $ {VNO^\varepsilon_n(q)}$ 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).