💻 computer science

Extending the Ginsburg-Spanier Theorem to Functions and Mixed Arithmetic

This paper extends the Ginsburg-Spanier theorem by providing purely algebraic characterizations of definable functions and sets across three additive theories, proving that definable functions in integer and real theories are piecewise linear, while those in the mixed theory are "piecewise-simple," and establishing the equivalence between semi-polinear and mixed-linear sets.

Original authors: Alain Finkel, Jérôme Leroux

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alain Finkel, Jérôme Leroux

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 cartographer trying to map out the "shape" of mathematical rules. For a long time, mathematicians have known how to draw maps for three specific types of worlds:

The World of Whole Numbers (Integers: 1, 2, 3...).
The World of Smooth Continuity (Real Numbers: 1.5, $\pi$ , 3.14159...).
The Mixed World (A blend of both, where you can have whole numbers and decimals interacting).

For decades, we knew what the "territories" (sets of numbers) looked like in these worlds, but we didn't have a clear, simple rulebook for the "paths" (functions) that connect them. This paper is like a new atlas that finally draws those paths clearly for all three worlds, using only geometry and algebra, without needing complex machines or computers to do the work.

Here is a breakdown of their discoveries using simple analogies:

1. The Three Worlds and Their Maps

The authors study three different "logics" (rules for thinking about numbers):

World A (Integers): You can only count whole steps.
World B (Reals): You can walk any distance, even tiny fractions.
World C (Mixed): You can walk whole steps and fractional steps, but they behave differently.

The Old Problem:
We already knew how to describe the shapes of the territories in these worlds.

In the Integer world, shapes are like LEGO structures (built from repeating blocks).
In the Real world, shapes are like smooth clay sculptures (polyhedra).
In the Mixed world, the shapes were a bit of a mystery, with a previous map that had a few errors.

The New Discovery:
The authors figured out how to describe the functions (the rules that turn an input number into an output number) in these same simple geometric terms.

2. The "Piecewise" Concept: The Patchwork Quilt

The central idea in this paper is "Piecewise."

Imagine you have a giant quilt. It's not made of one single pattern. Instead, it's made of different patches.

In Patch 1, the pattern is a straight line.
In Patch 2, the pattern is a different straight line.
In Patch 3, it's another straight line.

As long as the quilt is made of a finite number of these "straight-line patches," it counts as a "Piecewise Linear" function.

3. The Three Main Results

Here is what the paper claims for each world:

A. The Integer World (Presburger Arithmetic)

The Old View: We knew these functions could be built by "counter machines" (like a robot counting steps).
The New View: The authors prove that any function you can define in this world is simply a Piecewise Linear function.
The Analogy: If you are walking on a grid of whole numbers, any rule you follow is just a series of straight lines connected at corners. You don't need a complex robot to describe it; you just need to say, "Walk straight here, then turn and walk straight there."

B. The Real World (Real Additive Theory)

The Old View: We knew the shapes were smooth clay sculptures.
The New View: Just like the integer world, any function here is also Piecewise Linear.
The Analogy: Even though you can walk on decimals, the rules governing your movement are still just a collection of straight-line segments. If you zoom in close enough on any part of the rule, it looks like a straight line.

C. The Mixed World (The Tricky One)

This is the most complex world, where whole numbers and decimals mix.

The Correction: The authors found a mistake in a famous previous map (by Weispfenning). The old map tried to describe these shapes using "subgroups" (like a pattern that repeats infinitely in both directions). The authors corrected this to use "submonoids" (patterns that only repeat in one direction, like counting up).
The New Shape: They introduced a new shape called "Semi-polinear."
- Think of a number as having two parts: the Whole Part (the integer) and the Fractional Part (the decimal, like 0.75).
- A "Semi-polinear" set is a shape where the Whole Part follows a LEGO-like pattern (repeating blocks) and the Fractional Part follows a smooth clay pattern.
The New Function: They discovered that functions in this mixed world are "Piecewise-Simple."
- The Analogy: Imagine a machine that takes a number, splits it into its "Whole" and "Fractional" parts, and then applies two different straight-line rules to each part separately.
- For example, the rule might say: "Take the whole number part and multiply it by 2, but take the decimal part and multiply it by 0.5."
- This is different from the other worlds because the "slope" (steepness) of the line can be different for the whole part and the decimal part.

4. Why This Matters (According to the Paper)

Simplicity: The authors didn't use complex computer programs or automata (machines) to prove this. They used pure algebra and geometry, like solving a puzzle with blocks.
Unification: They put all three worlds (Integers, Reals, and Mixed) into a single framework. Before, we had different names and tools for each; now, we see they are all variations of "straight lines on different types of patches."
Correction: They fixed a specific error in a 1990s paper regarding how the "Mixed World" shapes are built, ensuring future maps are accurate.

Summary

The paper says: "If you can write a rule for numbers using addition and order in these three specific worlds, that rule is always just a collection of straight lines. In the mixed world, these lines might treat the 'whole number' part and the 'decimal' part differently, but they are still just straight lines."

They have provided a clean, geometric dictionary to translate complex logical rules into simple, visual shapes.

Technical Summary: Extending the Ginsburg–Spanier Theorem to Functions and Mixed Arithmetic

Problem Statement
The paper addresses a gap in the characterization of functions definable in three decidable additive theories: the integer additive theory $\text{FO}(\mathbb{Z}, +, \leq)$ (Presburger arithmetic), the real additive theory $\text{FO}(\mathbb{R}, +, \leq)$ , and the mixed additive theory $\text{FO}(\mathbb{R}, \mathbb{Z}, +, \leq)$ . While the definable sets in these logics are well-characterized (semi-linear sets for integers, polyhedral convex sets for reals, and mixed-linear sets for the mixed case), the definable functions had previously been described only via operational models (e.g., counter automata) or logical normal forms. A direct, purely geometric/algebraic characterization of these functions was missing from the literature.

Methodology
The authors employ a purely algebraic approach, relying on linear algebra and the classical Ginsburg–Spanier theorem, avoiding references to automata theory or quantifier elimination procedures in their proofs. The core methodology involves:

Stability Analysis: Utilizing the property of "stability by addition" (where $f(\vec{a}_1 + \vec{a}_2) = f(\vec{a}_1) + f(\vec{a}_2)$ ) to demonstrate that stable functions with rational graphs are linear.
Graph Decomposition: Decomposing the graph of a definable function into finite unions of geometric primitives (linear sets, polyhedral convex sets, or polinear sets) and analyzing the linearity of the function restricted to these primitives.
Density Arguments: Using the density of rational points within polyhedral convex sets to extend linearity results from rational domains to real domains.
Structural Induction: For the mixed theory, proving that the class of semi-polinear sets is closed under logical operations (intersection, complement, projection) to establish their equivalence with definable sets.

Key Contributions and Results

Characterization of $\text{FO}(\mathbb{Z}, +, \leq)$ Functions:
The paper proves that a function is definable in Presburger arithmetic if and only if it is piecewise linear on a Presburger partition of its domain (Theorem 4.2). Specifically, the graph of such a function decomposes into a finite union of linear sets, and on each set, the function acts as a linear map (affine transformation). This result is derived directly from the Ginsburg–Spanier theorem and a stability lemma, providing a direct algebraic normal form distinct from prior operational characterizations involving flat or reversal-bounded counter automata.
Characterization of $\text{FO}(\mathbb{R}, +, \leq)$ Functions:
The authors show that functions definable in the real additive theory are exactly the piecewise linear functions (Theorem 3.4). The proof establishes that stable functions with rational graphs are linear, and since definable sets are finite unions of polyhedral convex sets, the function must be piecewise linear.
Extension to the Mixed Theory ( $\text{FO}(\mathbb{R}, \mathbb{Z}, +, \leq)$ ):
- Semi-polinear Sets: The authors introduce semi-polinear sets as the correct analogue of semi-linear sets for the mixed theory. A polinear set is defined as $C + b + M$ , where $C$ is a polyhedral convex set in $[0, 1)^n$ , $b$ is an integer vector, and $M$ is a finitely generated monoid in $\mathbb{Z}^n$ . They prove that the class of semi-polinear sets coincides exactly with the class of mixed-linear sets (Theorem 5.4).
- Correction of Prior Work: The paper identifies and corrects an error in Weispfenning's [17] description of mixed-linear sets, noting that the periodic component must be a submonoid (e.g., $p\mathbb{N}$ ) rather than a subgroup (e.g., $p\mathbb{Z}$ ) to correctly capture sets like $\mathbb{N}$ .
- Piecewise-Simple Functions: The paper defines a new class of functions called piecewise-simple. A function is simple if it is linear in the fractional part of the argument and linear in the integer part, potentially with different coefficients for each. The main result (Theorem 5.9) states that a function is definable in $\text{FO}(\mathbb{R}, \mathbb{Z}, +, \leq)$ if and only if it is piecewise-simple.

Significance and Claims
The authors claim the significance of their work lies in several areas:

Unification: The results unify the three additive theories under a single geometric framework, completing the "algebraic row" in the characterization of these logics (as illustrated in Table 1 of the paper).
Directness: The proofs are self-contained, short, and rely solely on standard linear algebra and the Ginsburg–Spanier theorem, making the results accessible and easy to verify without invoking complex automata constructions.
Novelty: Despite the maturity of the field, the explicit statement of piecewise-linear and piecewise-simple characterizations as theorems with direct algebraic proofs is presented as a new contribution.
Independence: The definitions of piecewise-linear and piecewise-simple functions are independent of logic or automata, making them potentially useful in verification, synthesis, and constraint solving.
Correction: The paper provides a necessary correction to the structural description of mixed-linear sets found in the only prior comprehensive work on the subject (Weispfenning [17]).

The paper concludes by noting that the algebraic characterization of functions in $\text{FO}(\mathbb{Z}, +, V_p)$ (Presburger arithmetic extended with $p$ -adic valuation) remains an open problem.