pith. sign in

arxiv: 2605.21866 · v1 · pith:OR2AZPN5new · submitted 2026-05-21 · 🧮 math.CO · cs.DM· math.NT

Graphs from quadratic forms and vector spaces over finite fields

Jean Godard , Lucas Reis This is my paper

Pith reviewed 2026-05-22 05:23 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.NT
keywords quadratic formsfinite fieldsvector spacesundirected graphsclique numbergraph connectednesscharacter sums
0
0 comments X

The pith

Quadratic forms making graphs on finite field subspaces undirected are only XY, X²±Y² and X²+bXY+Y² for b≠0.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper classifies all nonzero quadratic forms Q over finite fields of odd prime power q such that the graph Γ(Q,V) defined via the condition Q(X,Y)∈V is undirected for every proper F_q-subspace V inside F_{q^n} with n≥2. A sympathetic reader would care because the undirected property turns an algebraic membership condition into a symmetric relation whose combinatorial consequences, such as connectedness or clique size, can then be studied in detail. The classification recovers the earlier XY case and adds the forms X²±Y² together with the family X²+bXY+Y², b≠0. Subsequent analysis shows a sharp structural split: the first two families produce disconnected graphs whose cliques can reach size equal to #V, while the Q_b family produces connected diameter-2 graphs once #V is at least q^{3n/4} and often has clique number o(#V). The proofs rely on character-sum estimates supplemented by algebraic and combinatorial arguments.

Core claim

We determine all quadratic forms Q for which Γ(Q,V) is undirected for every V. Besides the case Q(x,y)=XY, studied earlier, this essentially leads to the forms X²±Y² and the family Q_b(X,Y):=X²+bXY+Y², b≠0. We then study connectedness and clique number for the corresponding graphs. Our results reveal a clear contrast between these cases: the graphs Γ(X²±Y²,V) are well structured, disconnected and their clique number can be as large as #V, while the family Q_b yields less structured graphs that are connected (in fact of diameter 2) if #V≥q^{3n/4} and, in many cases, whose clique number is o(#V).

What carries the argument

The graph Γ(Q,V) whose adjacency is governed by whether the quadratic form Q(X,Y) lies inside the chosen proper F_q-subspace V; the central work is to find exactly which Q make this adjacency relation symmetric for every V.

If this is right

  • Graphs arising from X²±Y² are disconnected for every V and admit cliques of cardinality equal to #V.
  • Graphs arising from any Q_b are connected with diameter exactly 2 whenever #V ≥ q^{3n/4}.
  • For the Q_b family the clique number is o(#V) in many cases.
  • Character-sum estimates together with a few algebraic identities suffice to establish both the classification and the contrasting combinatorial properties.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same classification technique could be tried for higher-variable or higher-degree forms that define graphs via polynomial membership in subspaces.
  • Direct enumeration on small q and small n would give an independent check of the diameter-2 and o(#V) claims.
  • The structural contrast between the two regimes suggests possible constructions of graphs with prescribed clique-size bounds inside finite geometries.

Load-bearing premise

The classification and all subsequent structural statements assume an odd prime power q together with nonzero quadratic forms in two variables over the degree-n extension field for n at least 2.

What would settle it

Exhibiting one quadratic form outside the listed families for which Γ(Q,V) is nevertheless undirected for every proper V, or exhibiting a specific V that makes one of the listed forms produce a directed edge, would disprove the classification.

read the original abstract

Let $q$ be an odd prime power, let $n\ge 2$, and let $V\subsetneq \mathbb F_{q^n}$ be a proper $\mathbb F_q$-vector subspace. Given a nonzero quadratic form $Q(X,Y)\in \mathbb F_{q^n}[X,Y]$, we consider the graph $\Gamma(Q,V)$ that naturally arises from the condition $Q(X,Y)\in V$. We determine all quadratic forms $Q$ for which $\Gamma(Q,V)$ is undirected for every $V$. Besides the case $Q(x,y)=XY$, studied earlier by the second author, this essentially leads to the forms $X^2\pm Y^2$ and the family $Q_b(X, Y):=X^2+bXY+Y^2, b\ne 0$. We then study connectedness and clique number for the corresponding graphs. Our results reveal a clear contrast between these cases. The graphs $\Gamma(X^2\pm Y^2, V)$ are well structured, disconnected and their clique number can be as large as $\# V$. On the other hand, the family $Q_b$ seems to yield less structured graphs: the graphs are connected (in fact, of diameter $2$) if $\# V\ge q^{3n/4}$ and, in many cases, their clique number is $o(\# V)$. Our proofs are mainly based on character sums, while requiring a few algebraic and combinatorial ideas. We end the paper with some open problems and remarks, including a short discussion of the complementary case where $q$ is even.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript classifies all nonzero quadratic forms Q(X,Y) in F_{q^n}[X,Y] (q odd prime power, n≥2) such that the graph Γ(Q,V) with vertices in F_{q^n} and edges when Q(x,y) lies in a proper F_q-subspace V is undirected for every such V. This holds precisely for the forms XY, X²±Y², and the family Q_b(X,Y)=X²+bXY+Y² (b≠0). The paper then analyzes connectedness and clique numbers for the associated graphs, establishing that those from X²±Y² are disconnected with clique number up to |V|, while those from Q_b are connected of diameter 2 when |V|≥q^{3n/4} and often have clique number o(|V|). Proofs rely on character sums together with algebraic and combinatorial arguments, and the even-characteristic case is left open.

Significance. If the results hold, the work contributes a clean algebraic classification of quadratic forms yielding undirected graphs over finite fields and provides explicit contrasting examples of connectivity and clique behavior. The direct verification via linear dependence of Q(x,y) and Q(y,x) is a strength, as is the application of character sums to obtain diameter and clique estimates. These constructions may be of interest for further study in algebraic graph theory and finite geometry.

major comments (2)
  1. [Connectedness section] § on connectedness for Q_b: the diameter-2 claim when #V ≥ q^{3n/4} depends on a character-sum estimate whose error term is not stated explicitly. Without the precise bound (e.g., from Weil estimates or the specific character sum employed), it is difficult to confirm that the given threshold suffices uniformly for all n≥2 and all b≠0.
  2. [Classification section] Classification theorem: while direct substitution rules out other coefficient triples, the manuscript should include a short exhaustive case analysis on the possible ratios c/a for the general form aX²+bXY+cY² to make the completeness of the listed families fully transparent.
minor comments (2)
  1. [Introduction] The introduction would benefit from one or two additional references to prior work on graphs defined by bilinear or quadratic conditions over finite fields.
  2. [Structural results] Notation for the graph Γ(Q,V) and the undirected condition should be restated briefly at the start of the structural-results section for reader convenience.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments. We address each of the major comments below and indicate the revisions we plan to make.

read point-by-point responses

  1. Referee: [Connectedness section] § on connectedness for Q_b: the diameter-2 claim when #V ≥ q^{3n/4} depends on a character-sum estimate whose error term is not stated explicitly. Without the precise bound (e.g., from Weil estimates or the specific character sum employed), it is difficult to confirm that the given threshold suffices uniformly for all n≥2 and all b≠0.

    Authors: We thank the referee for pointing this out. Upon review, we agree that explicitly stating the error term in the character sum estimate would improve the clarity of the proof. In the revised manuscript, we will include the precise bound obtained from the relevant character sum estimates (based on Weil's theorem) and show that it guarantees the diameter-2 property for the specified threshold uniformly across all n ≥ 2 and b ≠ 0. revision: yes

  2. Referee: [Classification section] Classification theorem: while direct substitution rules out other coefficient triples, the manuscript should include a short exhaustive case analysis on the possible ratios c/a for the general form aX²+bXY+cY² to make the completeness of the listed families fully transparent.

    Authors: We agree that adding an exhaustive case analysis on the ratios c/a would make the classification more transparent. We will incorporate a brief case-by-case analysis in the classification section, considering the possible values of c/a and demonstrating how they correspond to the forms XY, X² ± Y², and Q_b, or are excluded. revision: yes

Circularity Check

0 steps flagged

Minor self-citation for XY case; classification via direct algebraic dependence check

full rationale

The paper classifies all nonzero quadratic forms Q in F_{q^n}[X,Y] (q odd, n≥2) such that Γ(Q,V) is undirected for every proper F_q-subspace V. This holds precisely when Q(x,y) and Q(y,x) are F_q-linearly dependent for every x,y. The listed forms satisfy the condition by direct verification: XY by equality, Q_b by identical polynomials, and X²±Y² by Q(y,x)=±Q(x,y) with the scalar in F_q. Other coefficient triples are ruled out by explicit pairs where the ratio lies outside F_q. The sole self-reference is the note that the XY case was studied earlier by the second author; this does not bear the load of the new classification, connectedness results, or clique-number bounds, which rest on character sums and algebraic/combinatorial arguments that are independent of the prior work and externally verifiable. The derivation is therefore self-contained with no reduction to fitted inputs, self-definitions, or unverified self-citations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies entirely on standard finite-field arithmetic and character-sum estimates; no free parameters are fitted and no new entities are postulated.

axioms (1)
  • standard math Quadratic forms over finite fields of odd characteristic admit the usual associated bilinear forms and character-sum evaluations.
    Invoked to define the graph and to count edges and cliques.

pith-pipeline@v0.9.0 · 5819 in / 1140 out tokens · 51229 ms · 2026-05-22T05:23:22.121064+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Ahmadi and A

    O. Ahmadi and A. Mohammadian. Sets with many pairs of orthogonal vectors over finite fields.Finite Fields Appl.37: 179–192, 2016

    work page 2016

  2. [2]

    Akbari and A

    S. Akbari and A. Mohammadian. Zero-divisor graphs of non-commutative rings.Jour- nal of Algebra296:462–479, 2006

    work page 2006

  3. [3]

    D. F. Anderson and P. S. Livingston. The zero-divisor graph of a commutative ring. Journal of Algebra217:434–447, 1999

    work page 1999

  4. [4]

    D. F. Anderson, M. C. Axtell, and J. A. Stickles. Zero-divisor graphs in commutative rings. InCommutative Algebra, pages 23–45. Springer, 2011

    work page 2011

  5. [5]

    L. Babai. Spectra of Cayley graphs.Journal of Combinatorial Theory, Series B27:180– 189, 1979. 12 JEAN GODARD AND LUCAS REIS

    work page 1979

  6. [6]

    A. Cayley. On the theory of groups.American Journal of Mathematics11 (2):139–157, 1889

    work page

  7. [7]

    I. Beck. Coloring of commutative rings.Journal of Algebra116:208–226, 1988

    work page 1988

  8. [8]

    Bourgain and A

    J. Bourgain and A. A. Glibichuk. Exponential sum estimate over subgroup in an ar- bitrary finite field,J. d’Analyse Math.115: 51–70, 2011

    work page 2011

  9. [9]

    S. Cohen. Clique numbers of Paley graphs.Quaestiones Math., 11: 225–231, 1988

    work page 1988

  10. [10]

    Godsil and G

    C. Godsil and G. Royle.Algebraic Graph Theory. Springer, 2001

    work page 2001

  11. [11]

    Gyarmati, A

    K. Gyarmati, A. S´ ark¨ ozy, Equations in finite fields with restricted solution sets. I (Character sums).Acta Math. Hung.118: 129–148, 2008

    work page 2008

  12. [12]

    G. A. Jones. Paley and the Paley Graphs. In: Jones G., Ponomarenko I., ˇSir´ aˇ n J.(eds) Isomorphisms, Symmetry and Computations in Algebraic Graph Theory. WAGT 2016. Springer Proceedings in Mathematics and Statistics 305, pp. 155–183, Springer, Cham

    work page 2016

  13. [13]

    S. Kim, C. H. Yip, and S. Yoo.f-Diophantine sets over finite fields via quasi-random hypergraphs from multivariate polynomials.Mathematika72:e70096, 2026

    work page 2026

  14. [14]

    Lidl and H

    R. Lidl and H. Niederreiter.Finite Fields.(Encyclopedia of Mathematics and its Applications). Cambridge: Cambridge University Press, 1996

    work page 1996

  15. [15]

    B. Mans, M. Sha, J. Smith, and D. Sutantyo. On the equational graphs over finite fields.Finite Fields and Their Applications64:101667, 2020

    work page 2020

  16. [16]

    Mattarei

    S. Mattarei. Inverse-closed additive subgroups of fields.Israel J. Math.159:343–348, 2007

    work page 2007

  17. [17]

    Podest´ a and D.E

    R.A. Podest´ a and D.E. Videla. The Waring’s problem over finite fields through gen- eralized Paley graphs.Discrete Math344: 112324, 2021

    work page 2021

  18. [18]

    L. Reis. Character sums over affine spaces and applications.Finite Fields Appl.83: 102067, 2023

    work page 2023

  19. [19]

    L. Reis. Paley-like graphs over finite fields from vector spaces.Finite Fields Appl.88: 102171, 2023

    work page 2023

  20. [20]

    Schneider and A.C

    C. Schneider and A.C. Silva. Cliques and colorings in generalized Paley graphs and an approach to synchronization.J. Algebra Appl.14(6) 1550088, 2015

    work page 2015

  21. [21]

    Terras.Fourier Analysis on Finite Groups and Applications

    A. Terras.Fourier Analysis on Finite Groups and Applications. Cambridge University Press, Cambridge, 1999

    work page 1999

  22. [22]

    C.H. Yip. On the clique number of Paley graphs of prime power order.Finite Fields Appl.77: 101930, 2022

    work page 2022

  23. [23]

    C. H. Yip and S. Yoo.F-Diophantine sets over finite fields.International Journal of Number Theory21(5):1043–1050, 2025

    work page 2025

  24. [24]

    Liu and S

    X. Liu and S. Zhou. Eigenvalues of Cayley graphs.Electronic Journal of Combina- torics29(2):P2.9, 2022. Departamento de Matem´atica, Universidade Federal de Minas Gerais, UFMG, Belo Horizonte, MG, 31270-901, Brazil Email address:jgodard@ufmg.br Departamento de Matem´atica, Universidade Federal de Minas Gerais, UFMG, Belo Horizonte, MG, 31270-901, Brazil E...

    work page 2022