🔢 mathematics

Finite rank kernel varieties: A variant of Hilbert's Nullstellensatz for graphons and applications to Hadamard matrices

This paper establishes a variant of Hilbert's Nullstellensatz for finite-rank graphons by constructing a polynomial representation of quantum graphs, thereby defining kernel varieties as Zariski-closed sets and revealing deep connections between Algebraic Geometry and Graphon Theory with applications to Hadamard matrices.

Original authors: Madelyn Andersen

Published 2026-05-18

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Madelyn Andersen

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 have a giant, infinite library of all possible networks (like social networks, road maps, or neural connections). In mathematics, these are called graphs. But what happens when these networks get so huge and complex that they become continuous, smooth shapes rather than just dots and lines? Mathematicians call these smooth shapes graphons. Think of a graphon as a "fuzzy blueprint" for a massive network, where instead of saying "A is connected to B," it says "A has a 70% chance of being connected to B."

This paper by Madelyn Andersen is like a new set of tools for organizing and understanding this library of fuzzy blueprints. Here is the breakdown using simple analogies:

1. The Problem: How do we sort these fuzzy blueprints?

Usually, to check if two networks are similar, mathematicians count how many times small patterns (like triangles or squares) appear inside them. This is called homomorphism density.

However, the author wanted to treat these graphons like objects in algebraic geometry (a branch of math that studies shapes defined by equations). In that world, you find shapes by looking for "zero-sets"—places where an equation equals zero.

The Challenge: Standard counting methods don't work perfectly here because of a quirk: the "empty network" and the "single dot network" both count as "1" in standard math, but they are very different. If you just use standard counting, your equations get messy.
The Solution: The author created a normalized map. Think of this as a special translator that converts the complex language of networks into a clean, standardized language of polynomials (equations with variables). This translator ensures that the "empty" and "single dot" cases cancel each other out correctly, just like they should in the real world.

2. The New System: "Kernel Zero-Sets" and "Ideals"

Once the translator is set up, the author treats groups of graphons like gardens.

The Garden (Zero-Set): Imagine you have a list of rules (equations). A "kernel zero-set" is the specific collection of graphons that follow all those rules perfectly (where the result is zero). It's like a garden where only flowers that meet a specific height requirement are allowed to grow.
The Fence (Ideal): If you want to keep a specific garden, you need a fence. In math, this fence is called an ideal. It's a list of all the "forbidden" patterns that, if they appear, mean a graphon doesn't belong in that garden.
The Result: The paper proves that these gardens and fences behave nicely. If you combine two gardens, you get a new valid garden. If you look at the intersection of many gardens, it's still a valid garden. This allows mathematicians to put a "topology" (a map of closeness and connection) on these infinite networks, similar to how you map cities on a globe.

3. The "Hadamard" Example: A Specific Case Study

To prove the system works, the author tested it on a very specific, rigid type of network called a Hadamard graphon.

The Analogy: Imagine a checkerboard where the squares are either black or white, arranged in a very strict, symmetrical pattern (like a Hadamard matrix).
The Finding: The author calculated exactly which patterns (like triangles or paths) would vanish (become zero) on this specific checkerboard. They found a direct formula: the "fuzzy" probability of a pattern appearing on the graphon is exactly the same as a simple counting formula on the checkerboard. This confirmed that their new algebraic tools could accurately describe these complex shapes.

4. The Big Takeaway

The paper establishes a bridge between network theory (graphs) and algebraic geometry (shapes defined by equations).

It shows that you can define "shapes" of networks based on what patterns they lack.
It proves that these shapes follow the same logical rules as geometric shapes (like circles or spheres).
It provides a way to translate complex network problems into polynomial equations, which are often easier to solve.

What the Paper Does Not Do

It is important to note what this paper is not about, based on the text:

It does not propose new algorithms for training AI or classifying social media networks (even though the introduction mentions these exist).
It does not offer medical or clinical applications.
It does not claim to solve the problem of how to perfectly reconstruct a network from limited data.

Instead, it is a theoretical foundation. It builds the mathematical "grammar" needed to talk about these infinite networks in a precise, algebraic way, setting the stage for future mathematicians to ask deeper questions about the structure of complex systems.

Technical Summary: Kernel Zero-sets, Quantum Graph Ideals, and Hadamard Graphons

Problem Statement
While graphons (symmetric measurable functions on $[0,1]^2$ ) are well-established as limiting objects for dense graph sequences and have found applications in network classification, signal processing, and mean field games, their algebraic study remains relatively unexplored. Existing literature has addressed the semigroup structure of graphons and their probabilistic properties, but there is a lack of systematic connection between graphons and the fundamental objects of algebraic geometry: zero loci, ideals, and polynomial varieties. This paper seeks to bridge that gap by establishing an algebraic framework for graphons, specifically investigating the structure of sets of kernels defined by vanishing homomorphism densities.

Methodology
The paper constructs an algebraic framework by mapping the space of quantum graphs (formal linear combinations of loopless multigraphs with complex coefficients) to invariant polynomial rings.

Quantum Graphs and Homomorphism Density: The authors utilize the complex algebra $A = \mathbb{C}G_0$ spanned by unlabeled loopless multigraphs. The homomorphism density $t(F, W)$ is extended linearly to quantum graphs $g \in A$ .
Normalized Polynomial Representation: To address the specific requirement that kernel zero-sets are defined by $t(g, W) = 0$ , the authors employ a normalized homomorphism-density polynomial map $\theta_q: A \to R_q$ . Here, $R_q$ is the ring of symmetric polynomials invariant under the symmetric group $S_q$ acting on the entries of a symmetric $q \times q$ matrix. The normalization factor $q^{-|V(F)|}$ is crucial; it ensures that $\theta_q(K_0 - K_1) = 0$ , matching the identity $t(K_0 - K_1, W) = 0$ for all kernels, a property the unnormalized homomorphism-number polynomial fails to satisfy.
Vanishing Ideals and Zero-Sets: For a fixed ambient class of kernels $\Omega \subseteq \mathcal{W}$ , the paper defines the kernel zero-set $V_\Omega(Q)$ for a subset of quantum graphs $Q$ and the corresponding vanishing ideal $I_A(Y)$ for a subset of kernels $Y$ . The image of these ideals under $\theta_q$ yields ideals in the invariant ring $R_q$ .

Key Contributions and Results

Algebraic Structure of Vanishing Sets: The paper proves that for any fixed ambient class $\Omega$ , the set of quantum graphs vanishing on a subset $Y \subseteq \Omega$ forms an ideal in the algebra $A$ . Consequently, their images in the invariant ring $R_q$ also form ideals. This relies on the multiplicativity of homomorphism density under disjoint union ($t(gh, W) = t(g, W)t(h, W)$).
Zariski-Type Topology: The authors demonstrate that the algebraic subsets of $\Omega$ (zero-sets of quantum graphs) are closed under finite unions and arbitrary intersections. This allows for the definition of a Zariski-type topology on the space of kernels, where the closed sets are the kernel zero-sets.
Nullstellensatz-Style Results:
- The paper establishes a correspondence between the closure of a set in the Zariski topology and its vanishing ideal: $V_\Omega(I_A(Y)) = Y$ for any algebraic set $Y$ .
- A Nullstellensatz-style theorem is proven for the invariant ring $R_q$ . Specifically, if a polynomial $f \in R_q$ vanishes on the zero-set of an ideal $\mathfrak{a} \subseteq R_q$ , then $f$ belongs to the radical $\sqrt{\mathfrak{a}}$ . This result is derived by extending the ideal to the full polynomial ring, applying the classical Hilbert's Nullstellensatz, and contracting back to the invariant ring.
- An irreducibility criterion is provided: a nonempty algebraic kernel set $V$ is irreducible if and only if its vanishing ideal $I_A(V)$ is a prime ideal.
Application to Hadamard Graphons: The framework is applied to Hadamard graphons, which arise from symmetric Hadamard matrices. The authors derive an explicit probability formula $P(B, g)$ that computes the homomorphism density $t(g, U_B)$ for a Hadamard graphon $U_B$ . They prove that the vanishing ideal of a Hadamard graphon is exactly the set of quantum graphs for which this probability formula vanishes. Furthermore, it is shown that if a symmetric Hadamard matrix has a $+1$ on the diagonal, no ordinary multigraph has a vanishing density on the associated graphon.

Significance and Limitations
The paper claims to provide the first systematic algebraic study of graphons by connecting them to zero loci and ideals, thereby importing tools from algebraic geometry into the theory of graph limits. The significance lies in defining a topology on kernel spaces and establishing ideal-theoretic characterizations of these spaces.

However, the paper is modest regarding the limitations of the polynomial representation. It explicitly notes that the map $\theta_q$ is not necessarily injective. Consequently, equality of polynomial images does not guarantee equality of the underlying kernel zero-sets. The authors illustrate this with an example where two distinct quantum graphs map to the same polynomial for $q=1$ but yield different homomorphism densities for rank-one kernels. The paper concludes by identifying future work not as an extension of the ideal theorems (which hold generally without finite-rank assumptions), but as an investigation into how different choices of the ambient class $\Omega$ affect the resulting topology and how much information is retained when passing to the finite- $q$ polynomial quotient.