🔢 mathematics

A Rank-Count Theory for the Combinatorial Discretizable Distance Geometry Problem

This paper develops an algebraic rank-count theory for the Combinatorial Discretizable Distance Geometry Problem, proving that under mirror-separated parameters, the feasible binary branch codes form an affine space over $\mathbb{F}_2$ whenever a viable reference solution exists.

Original authors: Michael Souza, Wagner da Rocha, Carlile Lavor

Published 2026-07-31

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Souza, Wagner da Rocha, Carlile Lavor

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 detective trying to reconstruct a crime scene, but you don't have a camera. Instead, you only have a list of distances between clues: "The gun was 5 feet from the lamp," "The lamp was 3 feet from the sofa," and so on. Your job is to figure out exactly where every object is sitting in the room. This is the essence of the Distance Geometry Problem. It's a puzzle that scientists use to solve real-world mysteries, like figuring out the 3D shape of a protein (which helps cure diseases) or locating sensors in a forest without GPS. Usually, there are infinite ways to arrange these objects to match the distances, making the puzzle impossible to solve by just guessing.

However, there's a special trick to make this puzzle solvable: Discretization. Imagine you build the scene one piece at a time, starting with a fixed foundation. For every new piece you add, you know its distance to the three pieces already placed. In 3D space, if you know the distance to three points, the new piece can only be in one of two specific spots (like a mirror image of itself across the wall formed by the first three). This turns the infinite, continuous puzzle into a finite tree of choices, like a "Choose Your Own Adventure" book where every page splits into two paths. The goal is to count how many valid endings (realizations) exist that satisfy all the distance rules.

This paper tackles a specific, tricky version of this puzzle called the Combinatorial Discretizable Distance Geometry Problem. In this version, the rules for placing new pieces are a bit more chaotic than the standard "Choose Your Own Adventure" book. The pieces you need to reference aren't always the ones you just placed; they might be scattered around the room. This makes it incredibly hard to count the valid endings because the "mirror" choices for one piece can mess up the distances for pieces placed much later. The authors, Michael Souza, Wagner da Rocha, and Carlile Lavor, have developed a new mathematical method to count these solutions without having to physically walk through every single path in the book.

The Paper's Discovery: Counting Without Walking

The authors' main finding is a clever algebraic formula that acts like a shortcut to count the number of valid solutions. They prove that, under certain conditions (which they call "mirror-separated parameters"), the valid ways to flip these mirror choices form a structured pattern known as an affine space over the field F2.

To understand this, imagine the "mirror choices" as a series of light switches. Some switches are locked in place because flipping them would break a distance rule (like making a sofa too far from a lamp). Other switches are free to be flipped. The paper shows that the "locked" switches aren't just randomly stuck; they are stuck in a very specific, predictable pattern. If you know one valid arrangement of switches (a reference solution), you can find all other valid arrangements by flipping specific groups of switches together.

The authors introduce a system of "generators" and "violation matrices" to map this out. Think of the generators as the keys that can unlock groups of switches, and the violation matrix as a security guard that checks if flipping a group of switches breaks any distance rules.

The Generators: These represent the basic moves you can make. Some moves affect a whole chain of future pieces (cone generators), while others are tied to specific groups of reference pieces (base generators).
The Violation Matrix: This is a grid that tracks which moves break which rules. If a move flips a switch that changes a distance it shouldn't, the matrix marks it as a "violation."

The magic happens when they look at the "kernel" of this matrix—the set of moves that result in zero violations. They prove that the number of valid solutions is determined by a simple rank formula:
$|\Xi| = 2^{f + \text{rank}([M; V]) - \text{rank}(V)}$
Here, $f$ represents the number of completely free switches (those that don't affect any rules), and the rest of the formula calculates how many combinations of the "locked" switches actually work.

What They Rule Out and How Sure They Are

The paper explicitly argues against the idea that counting these solutions is impossible or requires a brute-force search through the entire tree of possibilities. While previous methods suggested that without a strict, orderly sequence of pieces, the number of solutions could depend on the exact numerical values of the distances (making it a messy, continuous problem), the authors prove that for this specific "Combinatorial" version, the count is actually a clean, discrete number determined by the structure of the connections, not the specific numbers.

They are very sure of their results. The paper presents a mathematical proof (Theorem 1) that establishes this relationship. They don't just simulate it; they prove that if a valid solution exists and the parameters are "mirror-separated" (meaning no accidental, weird geometric coincidences occur where a wrong move happens to look right), then the number of solutions is exactly given by their formula. They also provide a worked example with 7 vertices to demonstrate the math in action, showing how the formula correctly predicts 8 solutions.

The "Mirror-Separated" Caveat

There is one important condition for this shortcut to work: the "mirror-separated" assumption. The authors define this as a state where the distances are "generic" enough that no accidental geometric coincidences happen. In plain English, this means we assume the room isn't set up in a weird, perfectly symmetrical way where a wrong move accidentally lands on the right spot by pure luck. They argue that in the real world, such lucky accidents are so rare (mathematically, they happen on a set of "measure zero") that we can safely ignore them. If the parameters are mirror-separated, the algebraic formula holds true.

Why This Matters

This work is a big deal because it turns a problem that usually requires a computer to guess and check millions of possibilities into a problem that can be solved with linear algebra (the math of grids and vectors). Instead of building a massive tree and pruning the dead branches one by one, you can now build a matrix and calculate the answer. This could lead to much faster algorithms for figuring out protein structures or locating sensors, saving time and computing power.

The authors conclude that their framework opens a new path for designing efficient solvers. By shifting the focus from combinatorial searching to linear operations over a simple field (F2, which is just math with 0s and 1s), they provide a foundation for tools that can detect impossible paths early, bypassing expensive calculations. It's a shift from "trying every door" to "reading the blueprint" to know exactly which doors are open.

Technical Summary: A Rank-Count Theory for the Combinatorial Discretizable Distance Geometry Problem

Problem Statement
The Distance Geometry Problem (DGP) seeks a geometric realization of a weighted graph $G=(V, E)$ in $\mathbb{R}^K$ such that Euclidean distances between vertices match given edge weights. When a specific vertex order exists where every non-seed vertex has $K$ predecessors inducing a clique, the problem becomes the Combinatorial Discretizable Distance Geometry Problem (Combinatorial DDGP). In this subclass, the continuous search space is discretized via $K$ -lateration into a binary search tree. While the number of realizations is generically $2^{n-K}$ in the absence of additional constraints, determining the exact number of solutions when additional distance constraints (pruning edges) are present has remained an open challenge. Existing methods rely on algorithmic tree traversal (Branch-and-Prune), which does not yield a direct counting formula, and purely combinatorial counting fails because the lack of contiguous predecessors makes the search space weight-dependent in general cases.

Methodology
The authors develop an algebraic rank-count theory that models feasible branch decisions as an affine space over the finite field $\mathbb{F}_2$ . The methodology proceeds through the following steps:

Decomposition of Branch Codes: The set of branch decisions $B$ is partitioned into constrained branches $B_c$ (those influencing pruning edges) and free branches $B_f$ . The total number of realizations is $2^{|B_f|} \times |\Xi_F|$ , where $\Xi_F$ is the set of feasible constrained codes.
Generator Construction: The authors define two types of graph-derived generators to represent branch transformations:
- Cone generators ( $g_q$ ): Associated with each constrained vertex $q$ , representing the propagation of a branch decision through its dependency cone.
- Base generators ( $g_C$ ): Associated with unique predecessor cliques $C$ , aggregating the effects of all vertices sharing that clique.
  These generators are encoded in a Mask Matrix $M$ , mapping generator coefficients to branch masks in $\mathbb{F}_2^{|B_c|}$ .
Labeled Violation Matrix: To handle pruning constraints, the authors introduce a Labeled Violation Matrix $V$ . Unlike standard binary violation checks, entries are indexed by pairs $(e, C)$ , where $e$ is an active pruning edge and $C$ is the mirror clique of the generator. A generator violates an edge if the edge crosses the reflection boundary and the fixed endpoint does not lie on the mirror hyperplane defined by $C$ .
Algebraic Feasibility: The space of feasible branch shifts is defined as $K_F = M(\ker V)$ . A shift is feasible if it can be generated by a linear combination of generators that results in zero net labeled violations.
Mirror-Separation Hypothesis: The theory assumes "mirror-separated parameters," a generic condition ensuring that no accidental geometric coincidences allow a branch shift outside the algebraic kernel $K_F$ to preserve all distances.

Key Contributions

Algebraic Decomposition: The paper decomposes branch decisions into constrained and free bits, representing constrained transformations using cone and base generators derived from the graph structure.
Labeled Violation Framework: It introduces a labeled violation matrix that separates incompatibilities by mirror clique, enabling the algebraic cancellation of violations only when they occur within the same mirror context.
Rank-Count Theorem: The central result proves that, under mirror-separated parameters and assuming at least one viable reference solution exists, the set of feasible constrained branch codes forms an affine coset $s^*_c \oplus K_F$ .
Exact Counting Formula: The paper derives a precise formula for the total number of realizations:
$|\Xi| = 2^{f + \text{rank}_{\mathbb{F}_2}\left[\begin{smallmatrix} M \\ V \end{smallmatrix}\right] - \text{rank}_{\mathbb{F}_2}(V)}$
where $f = |B_f|$ . This allows the solution count to be determined via linear algebra over $\mathbb{F}_2$ without traversing the binary search tree.

Results
The authors validate the theory with a worked 7-vertex example in $\mathbb{R}^2$ . The example demonstrates:

The construction of cone and base generators.
The formation of the labeled violation matrix and the identification of the kernel $\ker V$ .
The projection of the kernel through the mask matrix to obtain the feasible shift space $K_F$ .
A geometric realization showing how algebraic shifts (e.g., simultaneous reflections of dependent vertices) preserve pruning distances while isolated shifts violate them.
The example confirms that the rank formula correctly predicts the number of solutions (8 in the specific case), accounting for both constrained symmetries and free branch decisions.

Significance
The paper claims to resolve the conflict between the tractability of order construction and the difficulty of solution counting in the Combinatorial DDGP. By establishing that feasible branch codes form an affine space over $\mathbb{F}_2$ , the work provides a unified algebraic explanation for solution counting that decouples the combinatorial structure of the discretization graph from numerical edge weights (under generic conditions).

The authors state that this framework offers a foundation for more efficient distance geometry algorithms. By shifting the focus from exponential tree traversal to linear algebraic operations over $\mathbb{F}_2$ , the approach allows for the potential detection of infeasible branches at early stages without expensive coordinate computations. The paper suggests that future work will focus on exploiting the sparsity of the matrices $M$ and $V$ to solve these systems efficiently for large-scale networks, potentially reducing the computational complexity of spatial reconstruction problems.

The Paper's Discovery: Counting Without Walking

What They Rule Out and How Sure They Are

The "Mirror-Separated" Caveat

Why This Matters

Technical Summary: A Rank-Count Theory for the Combinatorial Discretizable Distance Geometry Problem

More like this