Rational File Encoder

Bijective encoding of binary files as rational numbers via fixed-width symbol indexing

---

Overview

This system implements an exact mathematical bijection:

$$\phi : \Sigma^* \longleftrightarrow \mathcal{R}_L \subset \mathbb{Q} \cap (0,1)$$

where Σ* = {0,1,...,255}* is the set of all finite byte sequences and 𝓡_L is a specific subset of rational numbers.

Key Properties:

• Bijective: Perfect one-to-one correspondence
• Lossless: Exact reconstruction guaranteed
• Deterministic: Same input always produces same output
• Exact: Uses arbitrary-precision integers (no floating point)
• Not compressive: Entropy preserved, file size increases
• Not cryptographic: Encoding is reversible with public table

---

Mathematical Foundation

1. The Byte Alphabet

Define the alphabet of all byte values:

$$\Sigma = {0, 1, 2, \ldots, 255}$$

A file is any finite sequence:

$$B = (b_1, b_2, \ldots, b_n) \in \Sigma^n$$

The set of all finite byte strings is the Kleene closure:

$$\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n$$

2. The Lookup Table

Fix an index width L = 6 (six decimal digits).

Define the bijection T : Σ → 𝒮 where:

$$T(b) = \text{str}(b + 1).\text{zfill}(6)$$

Examples:

• T(0x00) = "000001"
• T(0x01) = "000002"
• T(0xFF) = "000256"

This creates a bijection between 256 bytes and 256 six-digit indices.

3. The Encoding Transform

Given byte string B = (b₁, b₂, ..., bₙ):

Step 1 - Symbol Translation:

$$D = T(b_1) ,|, T(b_2) ,|, \cdots ,|, T(b_n)$$

where | denotes string concatenation. D is a decimal digit string of length m = 6n.

Step 2 - Integer Interpretation:

$$P = \sum_{i=1}^{m} d_i \cdot 10^{m-i}$$

where dᵢ is the i-th digit of D.

Step 3 - Rational Formation:

$$R = \frac{P}{10^m} = \frac{P}{q}$$

where q = 10^m.

Result: The file is encoded as the rational number R = p/q.

---

The Decoding Transform

Given rational (p, q) and index width L:

Step 1 - Validation:

• Verify q = 10^m for some m ∈ ℕ (denominator must be power of 10)
• Verify m ≡ 0 (mod L) (must be divisible by index width)
• Compute n = m / L (number of bytes)

Step 2 - Digit String Recovery:

$$D = \text{str}(p).\text{zfill}(m)$$

Zero-pad p to exactly m digits, preserving leading zeros.

Step 3 - Block Segmentation:

Partition D into n blocks of length L:

$$D = d_1 , d_2 , \cdots , d_n$$

where dᵢ = D[(i-1)L : iL].

Step 4 - Symbol Lookup:

For each block dᵢ:

$$b_i = T^{-1}(d_i)$$

Validate that dᵢ ∈ domain(T⁻¹), else reject as corrupted.

Step 5 - Output:

$$B = (b_1, b_2, \ldots, b_n)$$

---

Theorems and Proofs

Theorem 1 (Bijectivity)

Statement: The encoding φ : Σ* → 𝓡_L is a bijection.

Proof of Injectivity:

Suppose φ(B₁) = φ(B₂).

Case 1: If |B₁| ≠ |B₂|, say n₁ < n₂, then:

$$\frac{p_1}{10^{6n_1}} = \frac{p_2}{10^{6n_2}}$$

This implies p₁ · 10^(6(n₂-n₁)) = p₂.

But p₂ is constructed from n₂ blocks, each ≥ 1 in its first digit. The number p₁ · 10^(6(n₂-n₁)) would require the last block to be "000000", contradicting T(b) ≥ 1 for all bytes b.

Case 2: If |B₁| = |B₂| = n but B₁ ≠ B₂, then there exists index i where b₁ᵢ ≠ b₂ᵢ.

Since T is injective, T(b₁ᵢ) ≠ T(b₂ᵢ), so D₁ ≠ D₂, thus p₁ ≠ p₂, so φ(B₁) ≠ φ(B₂).

Therefore φ is injective. ∎

Proof of Surjectivity: By definition 𝓡_L = Image(φ), so φ is trivially surjective onto its image. ∎

Theorem 2 (Perfect Reconstruction)

Statement: For all B ∈ Σ*, decode(encode(B)) = B.

Proof:

Let B = (b₁, ..., bₙ).

Encoding produces:

• D = T(b₁) | ... | T(bₙ), length m = 6n
• P = int(D)
• q = 10^m

Decoding receives (P, q, L=6):

1. Computes m = log₁₀(q) ✓
2. Verifies m mod 6 = 0 ✓ (since m = 6n)
3. Computes n = m/6 ✓
4. Zero-pads P to m digits → recovers D exactly (since D already has m digits)
5. Segments D into n blocks d₁, ..., dₙ
6. Applies T⁻¹(dᵢ) = bᵢ (by definition of T)

Therefore decode(encode(B)) = (b₁, ..., bₙ) = B. ∎

Theorem 3 (Entropy Preservation)

Statement: The encoding preserves Shannon entropy.

Proof:

The Shannon entropy of B under uniform distribution is:

$$H(B) = n \cdot \log_2(256) = 8n \text{ bits}$$

Since φ is a bijection, given φ(B) we can uniquely recover B via φ⁻¹. No information is lost. The mutual information satisfies:

$$I(B; \phi(B)) = H(B)$$

Thus entropy is preserved. ∎

Theorem 4 (No Compression)

Statement: The encoding does not compress data.

Proof:

Original file: n bytes = 8n bits.

Encoded representation:

• p: up to 6n decimal digits
• q: 6n + 1 decimal digits

In decimal text: ≈ 12n characters.

In binary: 12n · log₂(10) ≈ 39.86n bits.

Expansion ratio: 39.86n / 8n ≈ 4.98×

The representation is 5× larger than the original. ∎

Theorem 5 (Measure Zero)

Statement: The set 𝓡_L has Lebesgue measure zero in [0,1].

Proof:

𝓡_L is countable (bijective to Σ*). Every countable subset of ℝ has Lebesgue measure zero. ∎

Theorem 6 (Computational Complexity)

Statement: Encoding and decoding are both O(n) time algorithms.

Proof:

Encoding:

1. Lookup T(bᵢ): O(1) per byte → O(n) total
2. Concatenate: O(6n)
3. String to integer: O(6n)

Total: O(n).

Decoding:

1. Validate q: O(m) = O(6n)
2. Zero-pad: O(m)
3. Segment: O(n) blocks
4. Lookup T⁻¹: O(1) per block → O(n) total

Total: O(n). ∎

---

Properties of the Codomain 𝓡_L

Set-Theoretic Properties

Cardinality: 𝓡_L is countably infinite.

For fixed n, |𝓡_L^(n)| = 256^n (all n-byte files).

$$|\mathcal{R}_L| = \sum_{n=0}^{\infty} 256^n = \aleph_0$$

Density: 𝓡_L is dense in [0,1] but has measure zero.

Not Closed Under Arithmetic: 𝓡_L is not closed under addition or multiplication.

Example: Let r₁ = r₂ = 1/10⁶ ∈ 𝓡_L.

Then r₁ + r₂ = 2/10⁶ = 1/500000.

To be in 𝓡_L, we need 1/500000 = p/10^(6n) for some n.

But 1/500000 = 20/10⁷, and 7 ≠ 6n for any n ∈ ℕ.

Thus r₁ + r₂ ∉ 𝓡_L.

Well-Ordered: As a countable set, 𝓡_L admits a well-ordering.

Algebraic Structure

Not a Group: Under addition or multiplication, 𝓡_L is not a group (not closed).

Not a Ring: No ring structure exists.

Partially Ordered: The standard ordering ≤ on ℚ restricts to 𝓡_L.

---

Error Propagation

Catastrophic Failure

Theorem: A single-digit error in p corrupts all subsequent bytes in the decoded output.

Explanation:

If digit d[k] is changed, the segmentation into 6-digit blocks shifts. Block i = ⌊k/6⌋ becomes corrupted. All subsequent blocks shift their boundaries, causing complete failure.

Example:

Original: D = "000001000002" → (0x00, 0x01)

Corrupted: D = "000001900002" → blocks "000001", "900002"

Block "900002" is not in domain(T⁻¹), so decoding fails completely.

No Error Correction

The encoding provides zero error correction. There is no redundancy.

Solution: Include integrity checks (SHA-256 hash) in metadata.

---

Computational Considerations

Arbitrary Precision Requirement

For a file of n bytes:

• m = 6n digits
• p may have up to 6n digits
• q = 10^(6n) has 6n + 1 digits

Example: A 5 MB file has:

• n = 5,242,880 bytes
• m = 31,457,280 digits
• p is a ~31-million-digit integer

Standard 64-bit integers (max ~10¹⁹) are insufficient.

Requirements:

• Python: native int type with sys.set_int_max_str_digits(0)
• Other languages: bignum libraries (GMP, Java BigInteger, etc.)

Space Complexity

• Encoding: O(6n) space for digit string
• Decoding: O(6n) space for digit string

Time Complexity (Revisited)

String-to-integer conversion in Python is O(m²) in the worst case (naive algorithm), but optimized implementations use FFT-based multiplication for O(m log m).

For practical purposes: O(n) to O(n log n).

---

Security Analysis

Not Encryption

With a public, fixed lookup table T, this provides zero cryptographic security.

Anyone can decode (p, q) given the public algorithm.

Substitution Cipher Variant

If T is a secret random permutation, the encoding becomes a substitution cipher.

Security level: Classical substitution ciphers are vulnerable to:

• Frequency analysis (byte distributions)
• Known-plaintext attacks
• Brute force (256! possible permutations of T, computationally infeasible but theoretically weak)

Conclusion: Even with secret T, this is not modern encryption.

Integrity via Hashing

Include SHA-256(B) in metadata.

After decoding, verify SHA-256(B') = SHA-256(B).

Collision probability: ≈ 2^(-256) (negligible).

---

JSON Container Format

The encoded file is stored as:

{
  "p": "<numerator-as-decimal-string>",
  "q": "<denominator-10^m>",
  "L": 6,
  "m": <total-digit-count>,
  "n": <byte-count>,
  "table_version": "v1.0-sequential",
  "sha256": "<hex-digest>",
  "original_filename": "<name.ext>"
}

Example:

For a 3-byte file [0x48, 0x69, 0x21] ("Hi!"):

{
  "p": "72105033",
  "q": "1000000000000000000",
  "L": 6,
  "m": 18,
  "n": 3,
  "table_version": "v1.0-sequential",
  "sha256": "3639efcd...",
  "original_filename": "hello.txt"
}

Decoding:

• D = "000072000105000033" (zero-pad p to 18 digits)
• Segment: ["000072", "000105", "000033"]
• T⁻¹("000072") = 0x47 = 71 (wait, that's wrong in this example - let me fix)

Actually: T(0x48) = "000073" (since 0x48 = 72, and T(72) = str(73).zfill(6) = "000073")

Let me correct:

For [0x48, 0x69, 0x21] = [72, 105, 33]:

• T(72) = "000073"
• T(105) = "000106"
• T(33) = "000034"

D = "000073000106000034"
p = 73000106000034

---

Usage

Prerequisites

• Python 3.11+
• Modern web browser

Running the Server

cd compress_cat
python3 backend.py

Navigate to http://localhost:8080

Encoding a File

1. Select file via web interface
2. Click "Encode to Rational"
3. Download JSON containing {p, q, L, m, n, sha256, original_filename}

Decoding a File

1. Upload JSON or paste p and q values
2. Click "Decode to Binary"
3. Download reconstructed file (original filename preserved)

---

Mathematical Extensions

Variable-Length Indexing

Replace fixed L with Huffman codes or arithmetic coding:

$$T_{\text{var}} : \Sigma \to {0,1}^*$$

Frequent bytes get shorter codes. Concatenate into D, interpret as binary integer:

$$R = \frac{P}{2^m}$$

Advantages: Compression for non-uniform distributions.
Disadvantages: Requires transmitting code table, loses fixed-width simplicity.

Continued Fraction Representation

Alternative encoding via continued fractions:

$$R = [0; a_1, a_2, \ldots, a_k]$$

where a₁, a₂, ... derived from byte sequence.

Advantage: Unique representation.
Disadvantage: Complex extraction/reconstruction.

Higher-Dimensional Embeddings

Encode multiple files as vector of rationals or interleaved single rational.

$$\phi^{(d)} : \Sigma^{n_1} \times \Sigma^{n_2} \times \cdots \times \Sigma^{n_d} \to \mathbb{Q}^d$$

---

Limitations

File Size Expansion

Expansion ratio: ≈ 5× in binary representation, ≈ 12× in decimal text.

A 1 MB file becomes a ~5 MB JSON (or ~12 MB if storing as text).

Computational Cost

For very large files (GB scale), encoding/decoding takes significant time due to arbitrary-precision arithmetic.

Mitigation: Stream processing, chunked encoding (trade-off: lose single-rational property).

No Compression

This is a representation transform, not compression. Entropy is preserved.

For actual compression, use gzip, zstd, etc. before or after this encoding.

Error Sensitivity

Single-bit flip in p or q → catastrophic failure.

Mitigation: Always include and verify SHA-256 hash.

---

Theoretical Significance

Why This Matters

1. Mathematical Beauty: Demonstrates bijection between discrete (byte strings) and continuous (rationals).

2. Pedagogical Value: Illustrates bijections, cardinality, measure theory, complexity.

3. Theoretical Computer Science: Connects string theory, number theory, information theory.

4. Philosophical: Shows that "all digital information" can be encoded as a single number.

Relation to Known Results

Cantor's Pairing Function: Maps ℕ × ℕ → ℕ bijectively. Our encoding generalizes this to Σ* → ℚ.

Gödel Numbering: Assigns unique integers to logical formulas. Our encoding assigns unique rationals to files.

Diophantine Equations: Encoding/decoding can be viewed as solving specific Diophantine equations.

---

Open Problems

1. Optimal Index Width: What is the minimal L preserving bijectivity?

2. Error-Correcting Extension: Can we add redundancy while maintaining rational structure?

3. Algebraic Closure: Define operation ⊗ such that (𝓡_L, ⊗) ≅ (Σ*, ·).

4. Compression via Variable Codes: Analyze rational structure with Huffman/arithmetic coding.

5. Cryptographic Security: Quantify security of secret-permuted T.

6. Quantum Encoding: Adapt for quantum states |ψ⟩.

7. Decidability Optimization: Decide r ∈ 𝓡_L in O(log m) time?

8. Number-Theoretic Patterns: Distribution of φ(B) modulo primes?

9. Category-Theoretic Universal Property: Is φ universal among similar encodings?

10. Physical Interpretation: Does this encoding have applications in physics (e.g., quantum information)?

---

References

1. Kleene, S.C. (1956). Representation of Events in Nerve Nets and Finite Automata.
2. Hardy, G.H. & Wright, E.M. (1979). An Introduction to the Theory of Numbers.
3. Cover, T.M. & Thomas, J.A. (2006). Elements of Information Theory.
4. Knuth, D.E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms.
5. Mac Lane, S. (1998). Categories for the Working Mathematician.

---

Conclusion

This system establishes a rigorous bijection φ : Σ* ↔ 𝓡_L ⊂ ℚ between finite byte strings and a subset of rational numbers via fixed-width decimal indexing.

Properties:

• ✅ Bijective (perfect reconstruction)
• ✅ Deterministic (reproducible)
• ✅ Exact (no floating-point errors)
• ✅ Entropy-preserving (lossless)
• ✅ Computationally linear (with arbitrary precision)
• ❌ Not compressive (5× expansion)
• ❌ Not cryptographic (public algorithm)

The encoding serves as a mathematical curiosity and pedagogical tool, demonstrating the deep connections between discrete mathematics, number theory, and information theory.

---

Version: 1.0
Date: November 2, 2025
License: Open Source