Today I Learned

June 3rd

Today I learned an example of spectral graph theory doing something of number-theoretic interest, from THE BOOK. Here is the statement we are building towards.

Note that $\FF_p^\times$ acts on the solutions $(x,y,z)$ by multiplication because $k\cdot(x,y,z)=(kx,ky,kz)$ still satisfies $(kx)^2+(ky)^2+(kz)^2\equiv k^2\left(x^2+y^2+z^2\right)$ will still $0$ out when $x^2+y^2+z^2\equiv0.$ We say because the orbit of $(0,0,0)$ has size $1$ ($(0k,0k,0k)=(0,0,0)$) the nonzero points $(x,y,z)$ have size $p-1$ (the nonzero coordinate has full image).

So because the zero point is poorly behaved, we show that there are $p^2-1$ nonzero points satisfying $x^2+y^2+z^2\equiv0.$ In fact, we will want to leverage the linear algebra structure of $\FF_p^3$ later in life, so we will show that\[\frac{\{(x,y,z)\in\FF_p^3\setminus\{0\}:x^2+y^2+z^2\equiv0\}}{\FF_p^\times}\stackrel?=\frac{p^2-1}{p-1}=p+1.\]That is, we need to show there are $p+1$ orbits of the nonzero points on $x^2+y^2+z^2\equiv0.$ Noticing the linear algebra structure on $\FF_p^3,$ these orbits are really one-dimensional subspaces generated by a nonzero vector, say $v=(x,y,z),$ which looks\[\{kv:k\in\FF_p\}=\FF_p^\times v\cup\{0\}.\]So instead we are now counting the number of one-dimensional subspaces $L$ of $\FF_p^3$ whose representatives $(x,y,z)\in L$ satisfy $x^2+y^2+z^2\equiv0,$ and we need there to be $\frac{p^2-1}{p-1}=p+1$ of them because there are $p-1$ elements in each orbit.

Now we bring in the spectral graph theory, and for this we need a graph $G_p.$ Our vertices will be the one-dimensional subspaces as represented by\[V(G_p)=\frac{\FF_p^3\setminus\{0\}}{\FF_p^\times}.\]We quickly remark that there are $\frac{p^3-1}{p-1}=p^2+p+1$ total vertices. We would like to rig our graph to detect $x^2+y^2+z^2\equiv0$ in some nice way, and the clever way to do this is to write\[E(G_p)=\big\{\{L_1,L_2\}\subseteq V(G_p):\langle v_1,v_2\rangle=0\text{ for all }v_1\in L_1,v_2\in L_2.\big\}.\]Here, $\langle(x_1,y_1,z_1),(x_2,y_2,z_2)\rangle:=x_1x_2+y_1y_2+z_1z_2$ is the usual dot product. (Despite using the notation, we are not calling $\langle,\rangle$ an inner product because it is not positive-definite.) We note that the edge connection is well-defined after picking up any representative $v\in L\setminus\{0\}.$ Indeed, if $\langle v_1,v_2\rangle=0$ for $v_1\in L_1\setminus\{0\}$ and $v_2\in L_2\setminus\{0\}$ and then we choose different representatives $k_1v_1\in L_1$ and $k_2v_2\in L_2,$ then still\[\langle k_1v_1,k_2v_2\rangle=k_1k_2\langle v_1,v_2\rangle=0.\]Anyways, the point of using the dot product for edge connections is to say\[x^2+y^2+z^2=\langle(x,y,z),(x,y,z)\rangle\]vanishes if and only if $(x,y,z)$ has a loop to itself. Letting $A_p$ be the adjacency matrix of $G_p,$ it suffices for the following.

We have now moved theoretically far away from the original statement, but we are only a single trick away from being done. Anyways, we are going to compute $\op{trace}A_p$ by computing its eigenvalues, cementing the statement we are doing spectral graph theory.

The main idea, now, is that $A_p$ might be difficult to analyze, but $A_p^2$ is not. Indeed, given two one-dimensional subspaces $L_1,L_2\in V(G_p),$ the entry $\left(A_p^2\right)_{v_1,v_2}$ counts the number of the paths from $L_1$ to $L_2$ of length two. Fix any $v_1\in L_1\setminus\{0\}$ and $v_2\in L_2\setminus\{0\}.$

Well by definition of our graph, we are counting the number of one-dimensional subpsaces $L$ satisfying\[\langle v,v_1\rangle=\langle v,v_2\rangle=0\]for some nonzero representative $v\in L\setminus\{0\}.$ (Recall that edge-connection is well-defined, so our choice of representative is irrelevant.) But now we might as well be asking for the number of $v$ satisfying\[\underbrace{\begin{bmatrix} - & v_1 & - \\ - & v_2 & -\end{bmatrix}}_Mv=\begin{bmatrix}0 \\ 0\end{bmatrix}.\]So, roughly speaking, we want the dimension of $\ker M.$ We have two cases. Now, the set $L_1^\perp$ of vectors $v$ such that $\langle v,v_1\rangle=0$ is two-dimensional, for the map $v\mapsto\langle v,v_2\rangle$ has one-dimensoinal image. But now\[\dim\ker M=\dim(L_1^\perp\cap L_2^\perp)=\dim L_1^\perp+\dim L_2^\perp-\dim(L_1^\perp+L_2^\perp)=4-\dim(L_1^\perp+L_2^\perp).\]We have two cases.

• If $L_1\ne L_2,$ then $L_1^\perp\ne L_2^\perp$ (recall $L^{\perp\perp}=L$ by, say, counting dimensions and building a basis). Thus, $L_2^\perp$ has a vector not in $L_1^\perp$ because they have the same size, so \[L_1^\perp+L_2^\perp\supsetneq L_1^\perp.\] Thus, $\dim(L_1^\perp+L_2^\perp) \gt \dim L_1^\perp=2,$ meaning that it must have dimension $3.$ So $\dim\ker M=1,$ and there is a single one-dimensional subspace to go around.

• If $L_1=L_2,$ then $L_1^\perp=L_2^\perp,$ so $\dim(L_1^\perp+L_2^\perp)=2.$ Thus, $\dim\ker M=2,$ implying that it has $p^2-1$ nonzero points and $\frac{p^2-1}{p-1}=p+1$ one-dimensional subspaces.

We remark briefly that we are working with one-dimensional subspaces instead of points because the condition $L_1=L_2$ creates fewer complications than $\FF_p^\times v_1=\FF_p^\times v_2.$

Anyways, it follows that the adjacency matrix looks like\[A_p^2=\begin{bmatrix} p+1 & 1 & \cdots & 1 & 1 \\ 1 & p+1 & \cdots & 1 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & \cdots & p+1 & 1 \\ 1 & 1 & \cdots & 1 & p+1\end{bmatrix}.\]All that remains is computation. We are interested in the eigenvalues of $A_p$ (to sum them), so we now ask for the eigenvalues of $A_p^2$ as above. Subtracting out $p$ times the identity, which will merely add $p$ to all eigenvalues, we want the eigenvalues of\[A_p^2-pI=\begin{bmatrix} 1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1\end{bmatrix}.\]Recalling that there are $\frac{p^3-1}{p-1}=p^2+p+1$ vertices, we need to find $p^2+p+1$ eigenvalues. Well, the image of this matrix lives in the one-dimensional subspace defined by $\langle1,\ldots,1\rangle$ and has a nonzero element (throw $\langle1,0,\ldots0\rangle$ in there), so the image does in fact have size $1.$

On one hand, this means that the kernel has dimension $p^2+p+1-1=p^2+p,$ so there are $p^2+p$ eigenvectors with eigenvalue $0.$ On the other hand, the vector $\langle1,\ldots,1\rangle$ maps to\[\begin{bmatrix} 1 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 1\end{bmatrix}\begin{bmatrix}1 \\ \vdots \\ 1\end{bmatrix}=\begin{bmatrix}p^2+p+1 \\ \vdots \\ p^2+p+1\end{bmatrix}\]and so has eigenvalue $p^2+p+1.$ Because we can only have $p^2+p+1$ total eigenvectors, this must be our last eigenvector.

Bringing this together, we see that $A_p^2$ has $p^2+p$ eigenvectors of eigenvalue $0+p=p$ and one eigenvector of eigenvalue $p^2+p+1+p=(p+1)^2.$ Taking the square-root ($A_p$ is diagonalizable because it has real entries and is symmetric because the graph is undirected), $A_p$ has one eigenvector of eigenvalue $\pm(p+1)$ and (say) $a$ eigenvectors of eigenvalue $\sqrt p$ and $b$ eigenvectors of eigenvalue $-p$ with $a+b=p^2+p.$ Thus,\[\op{trace}A_p=\pm(p+1)+a\sqrt p-b\sqrt p.\]Surely, $\op{trace}A$ is an integer, and $\sqrt p$ is irrational, so we must have $a=b$ to cover for this. So $\op{trace}A_p=\pm(p+1).$ But also surely $\op{trace}A_p$ is positive, so we must have $\op{trace}A_p=p+1.$ (In fact, $\langle1,\ldots,1\rangle$ has eigenvalue $p+1.$) This finishes. $\blacksquare$

It is proofs like these that make me certain I will never be a mathematician. This is pure magic. If I had to guess, the number-theoretic statement came out of other graph-theory studies, but I have no idea where the graph construction came from. Anyways, I am under the impression that this method can be generalized.

For example, we probably have the following.

The structure for even dimension seems more difficult. For example, even with $d=2,$ are computing the number of $(x,y)\in\FF_p^2$ for which $x^2+y^2\equiv0.$ In particular, the existence of nonzero solutions is equivalent to the existence of a $\sqrt{-1}\in\FF_p$ after rearranging.