🔢 mathematics

Farey-Recursive Shortest Completions and Universal Spectra in Rational Balance Languages

This paper establishes a cross-parameter Ordered Farey Recursion that decomposes the shortest-completion profiles of rational balance languages via explicit index maps, revealing that their local dynamics correspond to classical Christoffel paths and their global structure yields universal completion spectra derived from unimodular coordinate transformations.

Original authors: Alp Eren Bütün

Published 2026-09-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Alp Eren Bütün

Original paper licensed under CC BY 4.0 (https://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

In the vast landscape of mathematics, there is a quiet corner dedicated to the study of balance. Imagine a system where two different things, like two types of coins or two kinds of steps, must be combined in a specific ratio to reach a state of perfect equilibrium. If you have a pile of items that is slightly off-balance, a natural question arises: what is the smallest, most efficient way to add more items to fix it? This is not just a puzzle about counting; it is a fundamental problem about how numbers relate to one another when they are forced to stay positive. Mathematicians have long known that these relationships often follow hidden patterns, much like the way the branches of a tree grow in a predictable, repeating order. When the ratio between the two items is a simple fraction, the patterns are well understood. But when the system becomes more complex, involving a specific demand for how many of each item are needed to restore balance, the path to the solution can become a tangled web of possibilities. Understanding the shortest path to that balance is crucial for fields ranging from computer science, where machines must process data efficiently, to cryptography, where secure codes rely on the properties of numbers.

A researcher named Alp Eren Bütün has recently mapped out this tangled web with surprising clarity. The work begins with a specific type of machine, a kind of digital processor that reads a stream of zeros and ones. This machine keeps a running tally of how far it is from being "balanced," a state where the count of ones and zeros satisfies a precise mathematical rule. When the machine stops, it often finds itself in a state of imbalance, holding a specific "debt" or "surplus" that needs to be paid off. The core question is simple: given this debt, what is the absolute smallest number of zeros and ones required to pay it off? The researcher calls this the "shortest completion." While finding the answer for a single, isolated debt is straightforward, the true discovery lies in looking at the entire family of debts at once. Bütün discovered that if you line up the solutions for every possible debt, they do not appear random. Instead, they form a highly structured, ordered sequence that follows a strict set of rules, revealing a deep connection between the way numbers balance and the way fractions are built from simpler ones.

The heart of this discovery is a method of building complex solutions from simpler ones, a process that mirrors the way a family tree grows. In mathematics, there is a famous way of organizing all possible fractions, called the Stern-Brocot tree, where every new fraction is created by combining two "parent" fractions. Bütün found that the solutions for the shortest completions behave exactly the same way. If you know the list of shortest solutions for two parent fractions, you can construct the entire list for their child fraction without doing any new calculations. The child's list is simply a rearrangement of the parents' lists. One part of the child's list is a direct copy of the first parent's solutions, while the other part is a slightly shifted version of the second parent's solutions. These two lists are interleaved, or woven together, in a precise pattern determined by the numbers themselves. This means that the entire infinite family of balance problems is not a collection of separate puzzles, but a single, recursively generated system where every complex solution is built from the ground up using the solutions of simpler ancestors.

This recursive structure is driven by a simple, local rule that governs how the solution changes as the debt increases by just one unit. As the required balance shifts, the shortest solution jumps in one of two specific directions. These two directions are determined by the "parents" of the current fraction. The solution either adds a specific pair of zeros and ones, or it subtracts a different pair, effectively correcting the balance. This local movement is so regular that if you were to watch the solutions evolve, you would see them trace a path that looks like a straight line drawn on a grid, a pattern mathematicians have studied for centuries. However, the novelty of this work is not in the local movement itself, but in the global connection. The paper proves that the entire sequence of solutions for a complex fraction is a direct, mathematical offspring of the sequences for its parents. This allows the researcher to predict the behavior of the system at any level of complexity simply by knowing the structure of its roots.

Perhaps the most striking finding is what happens when you ignore the specific details of the zeros and ones and look only at the total number of items needed to fix the balance. When you combine the solutions for positive debts and negative debts, a universal pattern emerges that does not depend on the specific ratio of the fraction at all. For any pair of numbers that add up to a total sum, the collection of all possible solution lengths forms a perfect, unbroken set of numbers. It is as if the specific identity of the fraction disappears, leaving behind a universal spectrum of lengths that is identical for every fraction with the same total sum. This means that while the specific way to balance the system changes depending on the ratio, the total "cost" of balancing follows a rigid, predictable law that is the same for the entire family. This universality suggests that the underlying arithmetic of these balance problems is far more unified than previously thought, with the specific details of the fraction acting only as a filter that rearranges a single, fundamental set of possibilities.

The researcher arrived at these conclusions through rigorous symbolic proof, ensuring that every step of the logic holds up under mathematical scrutiny. To verify the findings, extensive computer checks were performed on thousands of different number pairs, ranging from small numbers to very large ones. In every single case tested, the predicted patterns held true, confirming that the recursive rules and the universal spectra are not just theoretical curiosities but robust mathematical facts. The work does not rely on simulations or approximations; it establishes a definitive link between the structure of fractions and the efficiency of balancing systems. By showing that the shortest completions are organized by a recursive tree and that their total lengths follow a universal law, the paper provides a complete map of this mathematical territory. It transforms a problem that might seem like a collection of isolated calculations into a coherent, interconnected system, revealing that the path to balance is always guided by the same deep, recursive principles that govern the structure of numbers themselves.

Problem Statement

The paper investigates the arithmetic structure of the shortest nonnegative integer completion vectors for the linear Diophantine equation:
$px - qy = r$
where $p$ and $q$ are coprime positive integers, $r \in \mathbb{Z}$ is a residual, and the objective is to minimize the $\ell_1$ norm $x + y$ subject to $x, y \in \mathbb{Z}_{\ge 0}$ .

This problem is motivated by the "shortest right completion" in rational balance languages $L_{p,q} = \{w \in \{0, 1\}^* : qN_1(w) = pN_0(w)\}$ . For a word $w$ with residual $\rho(w) = qN_1(w) - pN_0(w)$ , a suffix with $x$ zeros and $y$ ones balances the word if $px - qy = \rho(w)$ . The minimizing pair $(x, y)$ is denoted $\mu_{p,q}(r)$ , and its length is $L_{p,q}(r) = x+y$ .

While individual instances of this minimization are isolated optimization problems, the paper argues that the ordered family of solutions $\{\mu_{p,q}(r)\}_{r \in \mathbb{Z}}$ possesses a highly structured, recursive organization governed by the Farey decomposition of the ratio $q/p$ .

Methodology

The analysis relies on unimodular arithmetic, Farey sequences, and the Stern–Brocot tree. The core methodology involves:

Canonical Strip Characterization: The unique minimizer $\mu_{p,q}(r)$ is identified as the unique nonnegative solution lying within specific "canonical strips" (e.g., $0 \le y < p$ for $r \ge 0$ ).
Farey-Parent Decomposition: For a proper coprime pair $(p, q)$ , the paper utilizes the oriented Farey-parent decomposition:
$(p, q) = (c, u) + (v, d)$
normalized such that $pu - qc = 1$, $qv - pd = 1$, and $uv - cd = 1$.
Local Dynamics: The evolution of the solution vector as the residual $r$ increments is analyzed. The paper demonstrates that consecutive solutions differ by one of two specific "kernel-equivalent unit lifts": $(u, c)$ or $(-d, -v)$ .
Global Recursion: The paper constructs a mapping between the solution profile of a Farey mediant and the profiles of its parents using explicit floor/ceiling index maps.
Scalar Projection: The vector results are projected onto the scalar length $L_{p,q}(r)$ to analyze spectral properties, connecting the results to Beatty sequences and Dedekind sums.

Key Contributions and Results

1. Local Unit-Lift Dynamics

The paper establishes that the shortest completion path evolves via a "unit-residual lift" followed by a "canonical kernel reduction."

Theorem 4.1: For $0 \le r < p$ $0 \leq r < p$ , the transition from $\mu(r)$ $μ (r)$ to $\mu(r+1)$ $μ (r + 1)$ is determined by the second coordinate $y_r$ $y_{r}$ :
- If $0 \le y_r < v$ , the step is $(u, c)$ .
- If $v \le y_r < p$ , the step is $(-d, -v)$ .
Recovery: The local jump vectors uniquely determine the oriented Farey parents $(c, u)$ and $(v, d)$ .
Geometric Interpretation: After a unimodular change of coordinates, this local walk corresponds to a classical rational mechanical path (Christoffel word), though the paper emphasizes that the novelty lies in the cross-parameter recursion, not the mechanical coding itself.

2. Cross-Parameter Ordered Farey Recursion (Main Theorem)

Theorem 5.3 is the principal result. It states that the entire residual-indexed completion profile of a Farey mediant $(p, q)$ is reconstructed from the profiles of its parents $(c, u)$ and $(v, d)$ via explicit, complementary index maps:

Left Parent Inheritance: The profile of $(c, u)$ populates a specific subset of indices in the child profile unchanged.
Right Parent Translation: The profile of $(v, d)$ populates the complementary indices, shifted by a fixed vector $(u, c)$ .
Partitioning: The index sets are defined by floor/ceiling functions (e.g., $\lfloor pr/c \rfloor$ and $\lfloor ps/v \rfloor + 1$ ) and form a disjoint partition of the child's residual range. This creates a recursively coherent family of profiles over the Stern–Brocot tree.

3. Universal Scalar Spectra

While the vector geometry depends on the ratio $p:q$ , the scalar spectrum depends only on the sum $m = p + q$ .

Fundamental Spectrum: The combined multiset of positive and negative fundamental completion lengths is:
$S^+ \uplus S^- = \{0, 0, 2, 3, \dots, m-1\}$
Universal Shells: For any higher residual shell $k$ , the combined spectrum is an affine translate of the fundamental set: $\{k, k, k+2, \dots, k+m-1\}$ .
Moments: Consequently, all combined shell power moments depend solely on $m$ .

4. Connections to Classical Structures

The paper demonstrates how classical arithmetic objects arise as projections of this vector theory:

Beatty Sequences: The scalar lengths correspond to finite rational Beatty partitions.
Christoffel Words: The local jump sequence encodes a rational mechanical word.
Dedekind Sums: The paper derives the classical Dedekind reciprocity law by analyzing the ratio-dependent splitting of the second moment of the spectrum.

Significance and Claims

The author positions the work with specific modesty regarding novelty boundaries:

Not Novel: The paper explicitly states it does not claim novelty for Diophantine strip reduction, Bézout/Farey unit steps, modular inverses, mechanical/Christoffel coding, or Dedekind reciprocity in isolation. These are well-established classical results.
Principal Novelty: The core contribution is the Cross-Parameter Ordered Farey Recursion (Theorem 5.3). This is a vector-valued identity that compares the canonical minimizer sections of a Farey mediant with those of its parents. It identifies specific interleaved subsequences of the child profile with an unshifted parent profile and a fixed translate of the other.
Context: The author notes that while the local walk is equivalent to a classical mechanical path, the global reconstruction of the child profile from two distinct parent profiles via index shuffling has not been found in the surveyed literature on digital lines or Christoffel words.

Validation

All mathematical results are proved symbolically. The paper includes computational audits (covering coprime pairs up to $p, q \le 200$ and randomized pairs up to 5000) which served as independent consistency checks for the formulas and index partitions, finding no counterexamples. These computations are not premises for the proofs but serve as validation of the derived identities.

In conclusion, the paper organizes the family of shortest-completion profiles for rational balance languages into a single Farey-recursive system, characterized by locally recoverable parent data and universal scalar spectra, bridging the gap between automata-theoretic completion demands and deep number-theoretic structures.