🔢 mathematics

A Linear-Size Block-Partition Fibonacci Encoding for Gödel Numbering

This paper introduces a linear-size, injective encoding for finite strings into natural numbers using a block-partitioned Fibonacci sequence that achieves optimal $\Theta(m)$ growth while avoiding the exponential blowup inherent in Rosko's binary carryless pairing method.

Original authors: Zoltán Sóstai

Published 2026-03-27

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Zoltán Sóstai

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 giant, infinite library of numbers, but you want to turn any sentence you write (like "Hello World" or a complex math formula) into a single, unique number. This is called Gödel numbering, named after a famous logician who realized that if you can turn words into numbers, you can use math to study logic itself.

The problem with the old ways of doing this is that the numbers get huge very quickly. If you write a short sentence, the resulting number might have hundreds of digits. It's like trying to store a single letter in a warehouse the size of a city.

This paper introduces a new, much smarter way to do this using Fibonacci numbers (the sequence where each number is the sum of the two before it: 1, 1, 2, 3, 5, 8, 13...).

Here is the simple breakdown of the author's invention:

1. The Problem with the "Old Way" (Rosko's Method)

The author compares their new method to an older technique by a researcher named Rosko.

The Analogy: Imagine you are packing boxes. Rosko's method is like taking two boxes, putting them inside a bigger box, then taking that bigger box and putting it inside an even bigger one, and so on.
The Result: Every time you add a new letter to your sentence, you have to "nest" the whole thing inside a new, massive container. If your sentence has 10 letters, the number you get is roughly $2^{10}$ times bigger than it needs to be. If you have 50 letters, the number is so huge it would take more atoms than exist in the universe to write it down. This is an exponential explosion.

2. The New Solution: "Block Partitioning"

The author's new method is like organizing a hotel instead of nesting boxes.

The Hotel Analogy:
- Imagine a hotel with infinite floors.
- Instead of putting every guest in one giant room, we divide the hotel into blocks of rooms.
- Block 1 is for the 1st letter of your sentence.
- Block 2 is for the 2nd letter.
- Block 3 is for the 3rd letter.
- The Magic Gap: Between Block 1 and Block 2, we leave a gap (an empty hallway). Between Block 2 and Block 3, we leave another gap.
How it works:
- If your first letter is "A", you pick a specific room in Block 1.
- If your second letter is "B", you pick a specific room in Block 2.
- Because of the gaps between the blocks, you are guaranteed that the room you picked for "A" and the room you picked for "B" are never right next to each other.
Why the gap matters:
- In the world of Fibonacci numbers, there is a special rule (Zeckendorf's Theorem) that says: If you pick numbers that are never next to each other in the sequence, there is only ONE way to add them up to get a specific total.
- Because our "gaps" ensure the rooms are never neighbors, the sum of the room numbers (the Fibonacci numbers) creates a unique code. No two different sentences can ever result in the same total number.

3. The Result: Linear Growth

This is the big win.

Old Way (Rosko): Adding one letter doubles the size of the number. (Exponential growth).
New Way (Block Partition): Adding one letter just adds a fixed, small amount of "space" to the number.
- If a 1-letter word makes a 2-digit number, a 10-letter word makes a 20-digit number.
- If a 100-letter word makes a 200-digit number.
- It grows linearly. It's like adding one brick to a wall for every new letter, rather than rebuilding the whole wall twice as big.

4. Why This Matters

The author proves that this method is nearly as efficient as theoretically possible. You can't really do much better than this without using a different base system (like standard binary), but since this uses Fibonacci numbers, it has special mathematical properties that might be useful for advanced logic and computer science later on.

In a nutshell:
The author built a "Fibonacci Hotel" with strict rules about empty hallways between floors. This ensures that every sentence gets a unique, compact room number that doesn't explode in size as the sentence gets longer, solving a problem that previous methods made much worse.

1. Problem Statement

The paper addresses the problem of Gödel numbering: the injective mapping of finite strings (syntactic objects like formulas or proofs) over a fixed alphabet $\Sigma$ to natural numbers.

Context: Gödel's incompleteness theorems rely on such encodings. Traditional methods, such as the prime-power encoding ( $2^{a_1+1} \cdot 3^{a_2+1} \cdots$ ), produce numbers with super-linear growth (often hundreds of digits for short strings), making them computationally unwieldy.
Existing Alternatives: Rosko (2025) proposed using Zeckendorf representations (sums of non-consecutive Fibonacci numbers) with a "carryless pairing" function. However, the paper identifies a critical flaw in the standard application of this method: right-nesting binary pairings for sequences results in exponential growth in the number of digits ( $\Theta(2^m)$ ), which is inefficient.
Goal: Construct an encoding that is injective, allows for length recovery, and achieves linear growth in the number of digits ( $\Theta(m)$ ) relative to the string length $m$ , matching the information-theoretic lower bound up to a constant factor.

2. Methodology: Block-Partition Encoding

The author proposes a novel construction based on partitioning the Fibonacci sequence into contiguous blocks, separated by gaps.

Core Definitions

Alphabet: A finite alphabet $\Sigma = \{\sigma_0, \dots, \sigma_{k-1}\}$ with symbol codes $c \in \{0, \dots, k-1\}$ .
Block Size: Defined as $\beta = k + 1$ .
Block Partition: The Fibonacci sequence indices are divided into blocks $B_i$ $B_{i}$ for each string position $i \ge 0$ $i \geq 0$ .
- Block $B_i$ contains indices: $\{2 + i\beta, 2 + i\beta + 1, \dots, 2 + i\beta + (k-1)\}$ .
- Gap: The index $2 + i\beta + k$ is left unused. This gap ensures that the largest index in block $B_i$ and the smallest in $B_{i+1}$ are separated by at least 2 indices.
Encoding Rule: For a string $s = s_1 \dots s_m$ with symbol codes $c_1, \dots, c_m$ :
$\ulcorner s \urcorner = \sum_{i=0}^{m-1} F_{2 + i\beta + c_{i+1}}$
Each symbol at position $i$ selects exactly one Fibonacci number from its dedicated block $B_i$ .

Theoretical Foundation

The encoding relies on Zeckendorf's Theorem, which states that every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers.

Non-Adjacency: The construction guarantees that selected indices are never consecutive. Within a block, only one index is chosen. Between blocks, the gap ensures a separation of at least 2.
Uniqueness: Because the sum of non-consecutive Fibonacci numbers is unique (Zeckendorf's theorem), the resulting sum uniquely determines the set of selected indices, and thus the original string.

3. Key Contributions

Linear-Size Construction: The paper introduces the first Zeckendorf-based encoding that achieves linear digit growth ( $\Theta(m)$ ) for sequence encoding, avoiding the exponential blowup of nested pairing methods.
Injectivity and Decodability:
- Injectivity: Proven via the uniqueness of Zeckendorf representations. Distinct strings map to distinct sums.
- Length Recovery: The length of the original string $m$ can be directly recovered from the code $n$ by counting the number of terms in its Zeckendorf support ( $|Z(n)| = m$ ).
- Decoding: A greedy algorithm can reconstruct the string by identifying the block index and the symbol code for each term in the sum.
Complexity Analysis:
- Code Length: The number of digits grows as $\Theta(m)$ . Specifically, for a 10-symbol alphabet, the overhead is approximately 2.3 digits per symbol.
- Optimality: The construction is asymptotically optimal, matching the information-theoretic lower bound ( $\Omega(m)$ ) up to a constant factor.
Critique of Nested Pairing: The paper rigorously proves that the natural right-nested application of Rosko's binary carryless pairing results in $\Theta(2^m)$ digit growth, demonstrating why the block-partition approach is superior for sequence encoding.

4. Results

Theorem 5.1 (Linear Code Length): For any string of length $m$ , the worst-case digit count is $\Theta(m)$ .
Theorem 5.2 (Asymptotic Optimality): The encoding is optimal up to a constant factor. For $k=10$ , the constant factor is roughly 2.3 compared to the theoretical minimum.
Proposition 5.3 (Exponential Blowup): Right-nested carryless pairing yields codes with $\Theta(2^m)$ $Θ (2^{m})$ digits.
- Example: A length-5 string encoded via block partition uses a maximum Fibonacci index of 55. The same string encoded via nested pairing uses an index of 245, illustrating the rapid divergence.
Comparison: The paper provides a table comparing four methods:
- Prime-power (Gödel): Super-linear.
- Base-k positional: Linear (optimal constant).
- Right-nested carryless pairing (Rosko): Exponential ( $\Theta(2^m)$ ).
- Block partition (This paper): Linear ( $\Theta(m)$ ).

5. Significance

Efficiency: This encoding offers a practical, compact alternative to prime-power Gödel numbering, significantly reducing the magnitude of the numbers required to represent syntactic objects.
Theoretical Insight: It clarifies the limitations of "carryless pairing" for sequence encoding, showing that while useful for pairs, naive nesting leads to exponential inefficiency.
Future Applications: The additive nature of this encoding (sum of independent terms) suggests potential utility in bounded arithmetic and systems lacking multiplication, potentially aiding in the definition of syntactic predicates ( $\Delta_0$ -definability) or incompleteness proofs in weaker logical systems.
Distinction: The author explicitly distinguishes this from standard "Fibonacci coding" used in data compression, noting that while both use Zeckendorf representations, this method encodes strings as single numbers rather than integers as binary strings.

In summary, Sóstai presents a mathematically elegant and computationally efficient solution to the Gödel numbering problem, leveraging the structural properties of the Fibonacci sequence to achieve linear complexity where previous Zeckendorf-based attempts failed.