🔢 mathematics

Constant time testability of first-order logic with modulo counting on finitary graphs

This paper establishes that first-order logic with modulo counting (FOMOD) is testable in constant time on finitary graphs (bounded degree and component size) by adapting Hanf normal form and introducing a novel number-theoretic "patchability" condition, thereby resolving an open question regarding constant-time testability for monadic second-order logic with counting on such classes.

Original authors: Isolde Adler, Jenny Stimpson

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Isolde Adler, Jenny Stimpson

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 a quality control inspector for a massive factory that produces millions of tiny, disconnected Lego structures. You have a strict rule: you cannot look at the whole factory. The factory is too big, and checking every single brick would take forever. Instead, you are only allowed to peek at a tiny, random handful of these structures to decide if the whole batch is "good" or "bad."

This is the world of Property Testing. The goal is to make a decision about a giant system by looking at only a tiny, constant number of pieces, regardless of how huge the system actually is.

The Problem: The "Too Big to Read" Dilemma

In the past, researchers found a way to check certain rules on these Lego factories quickly, but only if the factories had a specific shape (like a tree with limited branches). Even then, the checking process took a little bit of time that grew as the factory got bigger.

The big question was: Can we check these rules instantly? Can we look at just a few pieces and say, "Yes, this batch is fine," or "No, this batch is broken," without the time increasing even if the factory has a billion pieces?

The Solution: The "Small Room" Factory

The authors of this paper say yes, but with a specific condition. They focused on factories where every single Lego structure is tiny. Specifically, no connected group of Lego bricks can be bigger than a fixed size (let's say, no bigger than a 10-brick cluster).

Think of it like a warehouse full of small, isolated islands. Each island is small (bounded size), and no island is too crowded (bounded degree).

How They Did It: The "Patchwork Quilt" Trick

The authors developed a clever method to check if these tiny islands follow a complex set of rules (written in a language called First-Order Logic with Modulo Counting). Here is the analogy of their process:

The Snapshot: The inspector picks a few random spots on the factory floor and looks at the immediate neighborhood. Because the islands are small, looking at a neighborhood is the same as seeing the whole island.
The Histogram (The Counting Sheet): They create a simple checklist.
- Rare Types: "Are there any islands that look like a specific, weird shape?" (e.g., a triangle with a dot). The rule might say, "There must be exactly 0, 1, or 2 of these."
- Frequent Types: "Are there islands that look like squares?" The rule might say, "There must be a huge number of them, and that number must be divisible by 3."
The "Patchability" Check (The Magic Math): This is the paper's biggest innovation.
- Imagine the inspector sees a few islands and thinks, "Okay, I see 2 triangles and 5 squares."
- The rule says, "You need 2 triangles and a number of squares that is a multiple of 3."
- The inspector knows the total number of bricks in the entire factory (the input size $n$ ).
- They ask: "If I fill the rest of the factory with more squares, can I make the total count work out perfectly?"
- They use a mathematical trick (related to the Frobenius Coin Theorem, which is like asking: "Can I make any large enough number of dollars using only $3 and $5 bills?") to prove that if the factory is big enough, the inspector can always "patch" the missing pieces to satisfy the rule, unless the rule is fundamentally broken.

The Result

If the factory is huge and the islands are small:

The inspector takes a tiny, constant number of samples.
They do a quick math check to see if the "missing pieces" can be logically filled in to satisfy the rule.
They declare the batch "Pass" or "Fail" in constant time. This means it takes the same amount of time whether the factory has 1,000 islands or 1,000,000,000 islands.

Why This Matters (According to the Paper)

It's a stepping stone: This proves that for "small island" factories, we can check complex rules instantly.
It solves a specific puzzle: It answers a question left open by previous researchers about whether we could speed up these checks from "very fast" to "instant."
The limitation: The paper admits this only works for graphs where the connected parts are small. It doesn't solve the problem for giant, sprawling networks (like the entire internet), but it's a major step toward understanding how to check rules on complex data quickly.

In short: The paper shows that if you have a massive collection of small, disconnected puzzles, you can instantly tell if they follow a complex set of instructions by looking at just a few pieces and doing a little bit of mental math to see if the rest of the puzzle could fit together.

Technical Summary: Constant Time Testability of First-Order Logic with Modulo Counting on Finitary Graphs

Problem Statement
The paper addresses the challenge of property testing in the bounded-degree graph model, specifically seeking algorithmic meta-theorems that guarantee constant running time (independent of the input size $n$ ). While previous work by Adler and Harwath (2018) established that Monadic Second-Order Logic with counting (CMSO) is testable with polylogarithmic running time on graph classes with bounded degree and bounded treewidth ( $C^w_d$ ), it remained an open question whether this could be improved to constant time.

This paper investigates this question on finitary graph classes ( $C^c_d$ ), defined as the class of all graphs where the maximum degree is bounded by $d$ and the size of every connected component is bounded by a constant $c$ . The authors aim to determine if properties expressible in First-Order Logic with modulo counting (FOMOD), and subsequently CMSO, are testable with constant running time on these classes.

Methodology
The authors employ a combination of logical normal forms, probabilistic sampling, and number-theoretic techniques to construct constant-time testers.

Tailored Hanf Normal Form:
The proof relies on a specific version of Hanf normal form for FOMOD formulas. The authors adapt Hanf's Locality Theorem to the setting of finitary graphs. They show that any FOMOD sentence $\phi$ on $C^c_d$ can be transformed into a Disjunctive Normal Form (DNF) where the atomic formulas describe the existence of specific connected component types (isomorphism types of size $\le c$ ) with specific counts.
- Crucially, the quantifiers are unified to a single radius ( $c-1$ ) and a uniform "cap" $k$ .
- The satisfaction of the formula is reduced to checking whether the graph's component histogram vector satisfies specific constraints.
Capped Component Histogram Vectors (k-CCHV):
The authors define a $k$ -capped component histogram vector $a$ indexed by the isomorphism types of connected components. For each type $t$ , the entry $a[t]$ specifies a constraint on the number of occurrences of $t$ in the graph:
- Rare types: The count is exactly an integer between $0$ and $k-1$ .
- Frequent types: The count is at least $k$ and satisfies a specific congruence condition ( $\equiv j \pmod m$ ).
  The main logical result (Lemma 14) states that a graph in $C^c_d$ satisfies an FOMOD sentence if and only if its component histogram vector satisfies at least one vector from a finite set $X$ derived from the sentence.
Algorithmic Strategy:
The proposed tester operates in two phases:
- Sampling: The algorithm samples a constant number of vertices (determined by $\epsilon, c, d$ ) and explores their connected components to estimate the frequency of component types.
- Verification:
  - If any "rare" component type (required to be absent or present in small numbers) is detected in the sample, the algorithm rejects.
  - If no rare types are detected, the algorithm performs an arithmetic check. It verifies if the total number of vertices $n$ allows for the construction of a graph satisfying the histogram constraints. This involves checking divisibility conditions derived from the Frobenius Coin Theorem. Specifically, it checks if the remaining vertices (after accounting for required rare components and minimal frequent components) can be filled by a conical combination of the sizes of the frequent component types.
Number-Theoretic "Patchability":
A key technical contribution is the use of the Frobenius Coin Theorem. To prove correctness, the authors show that if a graph is "far" from satisfying the property, one can construct a "patched" graph $G'$ that satisfies the property and is $\epsilon$ -close to the input. This construction involves "planting" the required rare components and filling the remainder of the graph with copies of frequent components. The Frobenius number ensures that for sufficiently large $n$ , the remaining vertex count can always be expressed as a sum of the sizes of the frequent components, provided the necessary modular arithmetic conditions are met.

Key Contributions and Results

Main Theorem (Theorem 16): Every property definable in FOMOD is testable with constant running time on the class $C^c_d$ (graphs with degree $\le d$ and component size $\le c$ ).
Corollary (Corollary 17): Since FOMOD and CMSO have the same expressive power on finitary graph classes, every CMSO-definable property is also testable with constant running time on $C^c_d$ .
Extension to Relational Structures (Theorem 18): The result generalizes to bounded-degree relational structures with bounded component size.

Significance and Claims
The paper claims that its results represent a significant step toward resolving the open problem of whether CMSO is constant-time testable on classes of bounded degree and bounded treewidth.

Natural Step: The authors note that finitary classes are exactly the intersection of bounded degree and bounded treedepth (a stronger condition than treewidth). Thus, this work provides a "natural step" toward the broader open problem.
Foundation for Hyperfinite Graphs: Since finitary graphs are central to the definition of hyperfinite graphs (which are known to have constant-time testable properties), this work serves as a "corner stone" for exploring constant-time testability on larger, more complex graph classes.
Independence of "Patchability": The authors highlight that the number-theoretic "patchability" condition they exhibit—allowing global inference from local samples via arithmetic checks—may be of independent interest.
Limitations: The paper modestly acknowledges that the question remains open for general bounded treewidth classes (where component sizes are not uniformly bounded). The difficulty arises specifically when the number of vertices cannot be modified to satisfy the property, a constraint inherent in the standard bounded-degree model.

The paper does not claim to solve the general bounded treewidth case but establishes that the transition from polylogarithmic to constant time is achievable when component sizes are uniformly bounded, leveraging the interplay between local sampling and global arithmetic constraints.