💻 computer science

A Calculus of Apartness over Separoids: Effective Convex Representation, Stratified Conservativity, and the Complexity of Entailment

This paper establishes that the finite theory of apartness relations induced by disjoint convex bodies is fully characterized by acyclic separoids, providing an effective rational realization theorem with uniform margins and proving that Boolean entailment is decidable with NP-complete satisfiability while introducing no new atomic apartness beyond separoid closure.

Original authors: Faruk Alpay, Baris Basaran

Published 2026-06-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Faruk Alpay, Baris Basaran

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 collection of distinct, solid objects (like clay blobs, rocks, or floating islands) scattered in a room. You don't care about their exact shape, color, or how heavy they are. You only care about one thing: Can you draw a straight line (or a flat wall) that separates a specific group of these objects from another group?

If you can draw a line that puts Group A on one side and Group B on the other, with no overlap, we say Group A is "apart" from Group B. If the groups are so tangled that no line can separate them, they are "crossing" (or touching).

This paper is a mathematical study of exactly what we can know, prove, and decide when we only have a list of these "separation" facts, without knowing the actual shapes or positions of the objects.

Here is the breakdown of their findings using simple analogies:

1. The Three Golden Rules of Separation

The authors discovered that no matter how complex the shapes are, the "apartness" relationship always follows three simple rules:

Symmetry: If Group A is apart from Group B, then Group B is apart from Group A. (It works both ways).
Subsumption (The "Subset" Rule): If a big group is apart from another big group, then any smaller piece of the first group is automatically apart from any smaller piece of the second group. (If you can separate the whole herd from the wolves, you can certainly separate one sheep from one wolf).
Vacuity (The "Empty" Rule): An empty group is always apart from everything. (You can always draw a line between "nothing" and "something").

The paper proves that these three rules are the only rules needed. If a set of separation facts follows these three laws, it is mathematically guaranteed that there exists a real-world arrangement of shapes that fits that description.

2. The "Magic" of Dimensions

One of the most surprising findings is about the size of the room (the dimension) where these objects live.

The Threshold: Imagine you have $N$ different objects. The paper proves that if you have a room with $N-1$ dimensions (e.g., 2 objects need a line, 3 objects need a plane, 4 objects need 3D space), you can arrange them in any way that the three rules allow.
The Stabilization: If you add more dimensions to the room (making it 4D, 5D, etc.), you don't gain any new possibilities. The rules of separation stop changing. Once you hit that $N-1$ threshold, the "logic" of separation is complete. Adding more space doesn't let you create new separation patterns; it just gives you more room to draw the same patterns.

3. The "Certificate" System

The authors didn't just say "it's possible"; they built a machine to prove it.

They created a method to turn a list of "separation rules" into a specific set of geometric shapes (polygons or polyhedra) with rational coordinates (numbers you can write as fractions).
The "Margin" Safety Net: They proved that these shapes can be built with a built-in "safety buffer." Even if you nudge the shapes slightly or make them slightly larger (like inflating a balloon), the separation facts do not change. The separation is robust. It's not a fragile balance; it's a sturdy wall.

4. The Logic of "Yes" and "No"

The paper also looks at the computer science side: How hard is it to check if a list of separation rules makes sense?

Simple "Yes" questions: If you ask, "Does this rule follow from those rules?" the answer is usually very fast to find. It's like checking if a small box fits inside a big box. If the small box is a subset of the big one, the answer is "Yes."
Hard "No" questions: If you ask, "Is it impossible to arrange these shapes to satisfy this complex mix of rules?" that becomes a much harder problem (specifically, NP-complete). This is because the difficulty comes from the "crossing" (touching) rules, which are the opposite of separation.

5. The "Stratification" (The Safety Lock)

Finally, the paper introduces a concept called "stratification." Think of it as a safety lock on a logic machine.

The paper proves that you can use complex logical reasoning (combining "and," "or," "not") to analyze these separation facts, but you can never create a new separation fact that wasn't already there.
The Metaphor: Imagine you have a set of Lego bricks. You can build a castle, a spaceship, or a house using those bricks. But no matter how cleverly you rearrange them, you cannot create a new brick that wasn't in the original box. The complex logic can only rearrange what is already given; it cannot invent new "separation" truths out of thin air.

Summary

In short, this paper says:

Separation of shapes is governed by three simple, intuitive rules.
If you have enough space (dimensions), you can build shapes to match any set of rules that follows those three laws.
Once you have enough space, adding more doesn't change the rules.
You can build these shapes with a "safety buffer" so they don't fall apart if you wiggle them.
Complex logic can't invent new separation facts; it can only rearrange the ones you already have.

The authors have taken a complex geometric problem and shown that its core logic is surprisingly simple, stable, and predictable.

Technical Summary: A Calculus of Apartness over Separoids

Problem Statement
The paper investigates the logical and combinatorial structure induced by the disjointness of convex hulls of compact convex bodies in Euclidean space. Given a finite set of "sites" $E$ , where each site is associated with a nonempty compact convex body, the study focuses on the binary relation of apartness ( $A \mathbin{\#} B$ ) between disjoint subsets of sites. This relation holds if the convex hulls of the unions of bodies corresponding to $A$ and $B$ are disjoint. The central problem is to determine the extent to which the geometric details of the bodies (dimension, shape, coordinates) can be forgotten while retaining the logical consequences of their separation patterns. Specifically, the paper seeks to axiomatize this relation, provide an effective representation, and classify the complexity of reasoning about it.

Methodology
The authors employ a multi-layered approach combining convex geometry, combinatorial topology, and proof theory:

Axiomatic Foundation: The paper identifies three fundamental laws satisfied by the apartness relation of any scene of convex bodies: Symmetry, Bilateral Subsumption (monotonicity), and Vacuity (the empty set is apart from everything). These laws define a structure called an apartness separoid, which is shown to be cryptomorphic to the acyclic separoids found in existing literature (Strausz et al.), effectively viewing the separation relation from its complementary "Radon partition" side.
Effective Representation: A constructive theorem is developed to realize any finite apartness separoid using rational polytopes. Unlike previous geometric realizations that optimize for minimal dimension, this construction is "proof-readable." It assigns one coordinate to each maximal separation and uses explicit rational coordinates with bounded bit height. The construction ensures a uniform Euclidean margin (at least 2) for all separations, providing robustness against perturbations.
Stability Analysis: Using distance functions and outer parallel bodies, the paper analyzes the stability of the realization. It demonstrates that the apartness relation is invariant under outer parallel enlargement by any radius $r < 1$ and that the bodies can be thickened to full-dimensional $C^{1,1}$ bodies without altering the relation.
Logical Calculus and Complexity: A formal language $L_E$ is defined with atoms representing separation assertions. The paper introduces a positive sequent calculus ( $SC_0$ ) and a Boolean calculus ($ACE$). It analyzes the decision problems of satisfiability, validity, and entailment, establishing their computational complexity.
Stratification: The paper introduces a stratification discipline to prove a conservativity theorem, showing that the Boolean stratum (compound reasoning) is inert with respect to the atomic stratum (positive facts).

Key Contributions and Results

Cryptomorphic Axiomatization: The paper establishes that the three laws (Symmetry, Bilateral Subsumption, Vacuity) completely axiomatize the apartness relation of convex bodies. This confirms that the "forgetting" of geometric details costs nothing regarding the logical consequence relation, provided the ambient dimension is sufficiently high.
Effective Rational Representation (Theorem 4.3): Every finite apartness separoid is realized by a scene of rational polytopes. The construction is output-sensitive:
- Coordinates are indexed by maximal separations.
- All coordinates are rational numbers with explicitly bounded numerator and denominator sizes ( $O(\log n)$ bits).
- The realization guarantees a uniform margin of at least 2 for every bilateral separation.
- The construction allows for the enumeration of maximal separations and minimal Radon partitions from various input formats (full table, generators, or membership oracles) with exponential output cost but no hidden arithmetic blowup.
Stability and Robustness (Theorem 4.13): The realization is stable. If every body in the scene is replaced by its outer parallel body with radius $r < 1$ , the apartness relation remains unchanged. Furthermore, the bodies can be smoothed to have $C^{1,1}$ boundaries while preserving the relation.
Dimension Hierarchy and Threshold (Theorem 4.17): The paper precisely characterizes the hierarchy of consequence relations based on ambient dimension $d$ $d$ .
- For $d < |E| - 1$ , the consequence relations form a strictly decreasing chain: $|=_{0} \supsetneq |=_{1} \supsetneq \dots \supsetneq |=_{|E|-2}$ .
- The hierarchy stabilizes exactly at dimension $d = |E| - 1$ . For all $d \ge |E| - 1$ , the consequence relation is identical to the dimension-free geometric consequence ( $|=_{geo}$ ).
- This threshold is proven to be sharp; dimensions below $|E|-1$ strictly enlarge the set of refutable assertions.
Logical Calculus and Complexity:
- Positive Entailment: Positive entailment collapses to simple subsumption. An assertion follows from a set of premises if and only if it is vacuous or componentwise dominated (possibly after a swap) by a single premise. This check is linear in the input size for sorted encodings.
- Boolean Closure: The Boolean calculus is sound, complete, and decidable. Satisfiability is NP-complete, and validity is coNP-complete.
- Conservativity (Theorem 7.3): A formal stratification condition proves that the Boolean stratum is inert on the atomic stratum. No amount of classical reasoning (negation, disjunction, case analysis) can derive a new positive apartness fact that is not already a subsumption of the atomic data.

Significance and Claims
The paper claims that the "stable core" of separation talk is small, exactly known, and entirely subsumptive. It argues that once the ambient dimension passes the threshold of $|E| - 1$ , the specific geometry of the scene becomes irrelevant to the logical consequences; the relation is fully captured by the three axiomatic laws.

The significance lies in providing a "logical and effective layer" to the existing combinatorial theory of separoids. While previous work focused on universality and homomorphisms, this paper provides:

A quantitative representation theorem with rational margins, making the logical structure inspectable coordinate-by-coordinate.
A precise complexity classification, distinguishing between the triviality of positive entailment and the hardness introduced by Boolean combinations.
A conservativity result that formally separates the "data" (atomic separations) from the "reasoning" (Boolean logic), showing that the latter adds no new geometric constraints.

The paper positions itself not as a discovery of new geometric phenomena, but as a rigorous formalization of the logical limits of convex separation, demonstrating that the "forgetting" of geometric detail is cost-free in terms of logical consequence, provided one stays within the stable, dimension-free regime.