🔢 mathematics

Graphs from quadratic forms and vector spaces over finite fields

This paper classifies quadratic forms over finite fields that generate undirected graphs based on subspace conditions, revealing a stark contrast between the highly structured, disconnected graphs arising from forms like $X^2 \pm Y^2$ and the connected, less structured graphs produced by the family $X^2 + bXY + Y^2$ , with proofs relying primarily on character sums.

Original authors: Jean Godard, Lucas Reis

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jean Godard, Lucas Reis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are in a vast, high-dimensional city called Finite Field City. This city has a strange rule: it only has a specific number of buildings (let's call this number $q^n$ ), and the streets are laid out in a very rigid, mathematical grid.

In this paper, two mathematicians, Jean Godard and Lucas Reis, are playing a game of "connect the dots" using a special set of rules. They want to build a map (a graph) where the buildings are the dots, and they draw a line between two buildings if a specific mathematical condition is met.

Here is the breakdown of their adventure, explained simply:

1. The Rules of the Game

The mathematicians have a "magic formula" (a quadratic form) that takes two buildings, let's call them $X$ and $Y$ , and spits out a number.

The Condition: They draw a line between building $X$ and building $Y$ if the result of their magic formula lands inside a specific "neighborhood" (a vector subspace $V$ ) of the city.
The Goal: They want to know:
1. Is the map fair? (If $X$ is connected to $Y$ , is $Y$ connected to $X$ ?)
2. Is the city one big neighborhood? (Can you walk from any building to any other building?)
3. How big is the biggest party? (What is the largest group of buildings where everyone is connected to everyone else? This is called a clique.)

2. The "Fairness" Test (Undirected Graphs)

First, they asked: "Which magic formulas make the map fair?"

If the formula is $XY$ (multiplying the two numbers), the map is fair.
If the formula is $X^2 + Y^2$ or $X^2 - Y^2$ , the map is fair.
If the formula is $X^2 + bXY + Y^2$ (a mix of squares and a product), the map is fair only if the mix is just right.

They discovered that almost all other formulas make the map unfair (like a one-way street), so they decided to ignore those and focus on the four "fair" types.

3. The Two Different Worlds

Once they picked the fair formulas, they found that the city splits into two very different worlds with totally different personalities.

World A: The "Split City" ( $X^2 \pm Y^2$ )

Imagine a city built on a checkerboard.

Disconnected: This city is broken up. You cannot walk from one side of the city to the other. The city is divided into many isolated islands.
The Parties: On these islands, you can throw huge parties. If your neighborhood is big, the party can be almost as big as the neighborhood itself. The size of the party is directly tied to how many "perfect squares" exist in that neighborhood.
The Vibe: Very structured, predictable, but isolated.

World B: The "Connected Web" ( $X^2 + bXY + Y^2$ )

Imagine a city where everyone is connected by a giant spiderweb.

Connected: If the neighborhood is big enough (specifically, if it covers at least 3/4 of the city's "density"), the whole city becomes one big connected web. You can get from any building to any other building in just two steps.
The Parties: The parties here are small. Even if the neighborhood is huge, the biggest group of people who all know each other is surprisingly small (much smaller than the neighborhood size).
The Vibe: Chaotic, highly connected, but with no large cliques.

4. How They Solved It

The mathematicians didn't just guess; they used a powerful tool called Character Sums.

The Analogy: Imagine trying to count how many people in a crowd are wearing red hats, but you can't see them directly. Instead, you use a special "magic sensor" (a mathematical wave) that vibrates differently depending on the hats. By analyzing the vibrations, they could count the red hats and figure out the structure of the city without walking every street.
They used this "sensor" to prove that in World B, the connections are so dense that you can't get lost (diameter 2), but the groups of mutual friends are surprisingly small.

5. The "What If" Scenarios

The paper ends by asking what happens in different scenarios:

What if the city is smaller? If the neighborhood is tiny, the "Connected Web" might break apart again.
What if the city has "Even" rules? The paper briefly mentions that if the city's math rules change to "Even Characteristic" (like binary code), the whole game changes. The "Split City" becomes a very simple, boring set of identical islands, and the "Connected Web" rules no longer work.

Summary

The paper is a study of how different mathematical recipes for connecting points in a finite world create two distinct types of social structures:

The Isolated Giants: Where you have huge groups of friends, but you can't travel between groups.
The Small-World Web: Where everyone is close to everyone else, but you can't find a massive group of mutual friends.

They used advanced math (character sums) to prove exactly when the city is connected and how big the friend groups can get, revealing a sharp contrast between these two types of mathematical formulas.

Technical Summary: Graphs from Quadratic Forms and Vector Spaces over Finite Fields

Problem Statement
This paper investigates the structural properties of directed graphs $\Gamma(Q, V)$ defined over finite fields $\mathbb{F}_{q^n}$ , where $q$ is an odd prime power and $n \ge 2$ . The graph is constructed using a nonzero quadratic form $Q(X, Y) \in \mathbb{F}_{q^n}[X, Y]$ and a proper $\mathbb{F}_q$ -vector subspace $V \subsetneq \mathbb{F}_{q^n}$ . The vertex set is $\mathbb{F}_{q^n}$ , and a directed edge $x \to y$ exists if $x \neq y$ and $Q(x, y) \in V$ .

The primary objective is to classify the quadratic forms $Q$ for which $\Gamma(Q, V)$ is undirected (i.e., $x \to y \iff y \to x$ ) for every choice of the subspace $V$ . Following this classification, the authors analyze the connectedness and clique number $\omega(Q, V)$ of these graphs, specifically contrasting the behavior of different quadratic forms. This work extends previous studies on the specific case $Q(X, Y) = XY$ (studied in [19]) to a broader class of quadratic forms.

Methodology
The proofs rely heavily on techniques from algebraic combinatorics and number theory over finite fields:

Character Sums: The authors utilize additive and multiplicative characters to derive bounds on the number of solutions to equations involving quadratic forms. Specifically, they employ:
- Poisson Summation Formula: To express the indicator function of vector subspaces via additive characters (Lemma 2.3).
- Weil's Bound: To estimate additive character sums over polynomials (Lemma 2.6).
- Gyamarti and Sárközy's Bound: To bound multiplicative character sums over affine subspaces (Lemma 2.4).
Algebraic Structure: The analysis involves examining the equivalence relations induced by the quadratic forms and the distribution of squares within vector subspaces and their translates.
Combinatorial Arguments: The paper uses the Pigeonhole Principle to classify the forms and analyzes the diameter of the graphs by counting paths between vertices.

Key Contributions and Results

1. Classification of Undirected Graphs
The paper provides a complete characterization of quadratic forms $Q(X, Y) = aX^2 + bXY + cY^2$ such that $\Gamma(Q, V)$ is undirected for all subspaces $V$ .

Theorem 1.2: $\Gamma(Q, V)$ is undirected for every $V$ if and only if $a = c$ or ( $b = 0$ and $a = -c \neq 0$ ).
Up to scalar multiplication, this reduces the study to four families:
- $Q^*(X, Y) = XY$ (previously studied).
- $Q^+(X, Y) = X^2 + Y^2$ .
- $Q^-(X, Y) = X^2 - Y^2$ .
- $Q_b(X, Y) = X^2 + bXY + Y^2$ with $b \neq 0$ .

2. Structural Analysis of $Q^+$ and $Q^-$
The graphs arising from $X^2 \pm Y^2$ exhibit highly structured, disconnected behavior.

Connectedness: For $Q = Q^+$ $Q = Q^{+}$ and $Q = Q^-$ $Q = Q^{-}$ , the graphs are always disconnected (Theorem 1.3(i)).
- For $Q^-$ , the connected components correspond to equivalence classes defined by $x \sim y \iff x^2 - y^2 \in V$ . If $|V| > q^{n/2}$ , the number of components is exactly $q^n / |V|$ .
Clique Number:
- For $Q^+$ , $\omega(Q^+, V) = N(0, V)$ (the number of $z$ such that $z^2 \in V$ ), unless $V$ contains no non-zero squares, in which case $\omega = 2$ . If $n$ is odd, $\omega(Q^+, V) = |V|$ .
- For $Q^-$ , $\omega(Q^-, V) = \max_{u} N(u^2, V)$ . If $n$ is odd, $\omega(Q^-, V) \ge |V|$ .
Contrast: In these cases, the clique number can be as large as $|V|$ , and the graphs are inherently disconnected.

3. Structural Analysis of $Q_b$
The family $Q_b(X, Y) = X^2 + bXY + Y^2$ ( $b \neq 0$ ) yields less structured graphs with different connectivity properties.

Connectedness: Unlike the $Q^\pm$ $Q^{\pm}$ cases, these graphs are often connected.
- Theorem 1.5: If $|V| \ge q^{3n/4}$ , then $\Gamma(Q_b, V)$ has diameter 2 (and is thus connected).
Clique Number:
- Theorem 1.3(iv): For any $b \neq 0$ , $\omega(Q_b, V) \le q^{n/2} + 2$ .
- This bound implies that for large subspaces (dimension $> n/2$ ), the clique number is significantly smaller than $|V|$ (specifically, $\omega(Q_b, V) / |V| = O(q^{-1/2})$ ).
- The paper notes that this bound is essentially sharp when $V$ is a subfield.

Significance and Claims
The authors highlight a "clear contrast" between the two classes of quadratic forms:

Structure vs. Randomness: The graphs for $X^2 \pm Y^2$ are "well structured," disconnected, and support large cliques (proportional to the subspace size). Conversely, the $Q_b$ family produces graphs that are connected (with small diameter under size constraints) and possess significantly smaller cliques relative to the subspace size.
Methodological Limits: The proof of the diameter 2 result for $Q_b$ relies on character sums. The authors observe that their current method requires $|V| \ge q^{3n/4}$ and suggests that breaking this barrier to prove connectivity for smaller $|V|$ (e.g., near the natural threshold $n/2$ ) would require new techniques, as the character sum approach alone is insufficient.
Open Problems: The paper concludes by identifying gaps in the current understanding, particularly regarding:
- Nontrivial estimates for the clique number of $Q_b$ when $|V| < q^{n/2}$ .
- Determining the precise threshold $s(n)$ for the connectedness of $\Gamma(Q_b, V)$ .
- Extending these results to fields of even characteristic, where the behavior of $X^2 + Y^2$ becomes trivial and the conditions for character sum bounds are violated.

The paper does not claim to solve the general problem of clique numbers for all subspace sizes or to provide a complete classification of connectedness thresholds, but rather establishes the dichotomy between the "structured" $X^2 \pm Y^2$ cases and the "less structured" $Q_b$ cases, providing specific bounds and thresholds where possible.