PaperlayerView exact revision on arXiv

Source-linked AI summary

Aperiodic Structures Never Collapse: Fibonacci Hierarchies for Lossless Compression

Roberto Tacconelli

arXiv:2603.14999v2cs.ITmath.COmath.DS

TL;DR

The paper asks whether an aperiodic hierarchy can improve lossless compression where periodic hierarchies collapse at finite depth. It analyzes Fibonacci quasicrystal and Sturmian structure, implements the resulting hierarchy in Quasicryth, and reports persistent theoretical and empirical advantages over periodic alternatives. The headline comparison reaches 11,089,469 B over Period-5 at 1 GB, with deeper levels providing positions unavailable to the periodic baseline.

  • Problem

    The paper studies whether aperiodic parsing structures can provide a structural advantage over periodic alternatives whose hierarchies collapse after finitely many levels.

  • Method

    The paper combines Fibonacci substitution, Perron-Frobenius and Pisot-Vijayaraghavan analysis, Sturmian factor complexity, and a ten-level Quasicryth implementation with deep n-gram lookup selection.

  • Results

    11,089,469 B is the measured aperiodic advantage over Period-5 at 1 GB, while 89-gram and 144-gram levels provide deep hits unavailable to periodic tilings.

  • Takeaways & Limitations

    Fibonacci quasicrystal structure preserves dictionary reuse across hierarchy depths and supports lower coding entropy and super-exponentially declining redundancy under the stated source conditions.

  • Takeaways & Limitations

    At enwik8, both deep levels record zero empirical hits because effective codebook formation requires a corpus scale much larger than the basic activation estimate.

Abstract

from arXiv · show

We study whether an aperiodic hierarchy can provide a structural advantage for lossless compression over periodic alternatives. We show that Fibonacci quasicrystal tilings avoid the finite-depth collapse that affects periodic hierarchies: usable $n$-gram lookup positions remain non-zero at every level, while periodic tilings collapse after $O(\log p)$ levels for period $p$. This yields an aperiodic hierarchy advantage: dictionary reuse remains available across all scales instead of vanishing beyond a finite depth. Our analysis gives four main consequences. First, the Golden Compensation property shows that the exponential decay in the number of positions is exactly balanced by the exponential growth in phrase length, so potential coverage remains scale-invariant with asymptotic value $W\varphi/\sqrt{5}$. Second, using the Sturmian complexity law $p(n)=n+1$, we show that Fibonacci/Sturmian hierarchies maximize codebook coverage efficiency among binary aperiodic tilings. Third, under long-range dependence, the resulting hierarchy achieves lower coding entropy than comparable periodic hierarchies. Fourth, redundancy decays super-exponentially with depth, whereas periodic systems remain locked at the depth where collapse occurs. We validate these results with Quasicryth, a lossless text compressor built on a ten-level Fibonacci hierarchy with phrase lengths ${2,3,5,8,13,21,34,55,89,144}$. In controlled A/B experiments with identical codebooks, the aperiodic advantage over a Period-5 baseline grows from $36{,}243$ B at 3 MB to $11{,}089{,}469$ B at 1 GB, explained by the activation of deeper hierarchy levels. On enwik9, Quasicryth achieves $225{,}918{,}349$ B $(22.59\%)$, with $20{,}735{,}733$ B saved by the Fibonacci tiling relative to no tiling.

1. Introduction

The paper proposes Fibonacci quasicrystal tilings as a parsing structure that avoids the finite-depth collapse of periodic hierarchies. It develops theoretical efficiency and entropy advantages, then validates them through Quasicryth and scale-dependent experiments.

  • Aperiodic parsing structure: Fibonacci tilings provide n-gram lookup positions at phrase lengths from 2 to 144 words while avoiding hierarchy collapse.The hierarchy is generated by the Fibonacci substitution and sustains both tile types at every scale.
  • Aperiodic parsing structure: The Fibonacci hierarchy is characterized as preserving dictionary reuse at all depths while combining scale-invariant coverage and bounded parsing overhead.The central theorem presents these properties as consequences of the same Fibonacci quasicrystal structure.
  • Codebook efficiency: Fibonacci levels have exactly F_m+1 tile-type patterns, yielding codebook coverage efficiency C_m/(F_m+1), maximal among binary aperiodic tilings.This follows from the Sturmian complexity law p(n)=n+1.
  • Scale-invariant coverage: Potential word coverage remains asymptotically Wφ/√5 at every hierarchy level because position decay and phrase-length growth cancel exactly.The cancellation follows from φ^2=φ+1 and Binet’s formula; variation therefore comes from codebook hit rate.
  • Information-theoretic consequences: For long-range phrase-dependent sources, Fibonacci coding entropy is strictly lower than that of periodic tilings collapsed before depth m.The paper also states that natural-language corpora satisfy the relevant dependence condition for phrase lengths up to at least 144 words.
  • Empirical validation: At 1 GB, the advantage over Period-5 reaches 11,089,469 B as the 89-gram and 144-gram levels activate, contributing 5,369 and 2,026 deep hits.The same controlled comparison reports a 36,243 B advantage at 3 MB.

2. Related Work

Quasicryth differs from classical byte-level and word-level compressors by using a deterministic quasicrystalline hierarchy to parse phrase structure. The paper positions this as a structural compression approach based on Fibonacci substitution tilings.

  • Classical and word-level compression: Classical compressors exploit byte-level structure, block transformations, or local repetition, whereas Quasicryth exploits hierarchical phrase structure.Quasicryth is word-level and uses phrase parsing determined by a quasicrystalline tiling.
  • Classical and word-level compression: Word-based models improve natural-language compression by exploiting lexical structure, but Quasicryth determines parsing through quasicrystalline tiling.Its static multi-level codebooks are built from the full input.
  • Quasicrystals and aperiodic tilings: The Fibonacci tiling is an aperiodic two-tile cut-and-project quasicrystal with an irrational frequency ratio.The paper identifies it as the canonical one-dimensional quasicrystal example.
  • Quasicrystals and aperiodic tilings: The paper presents Quasicryth as the first compressor using a quasicrystalline substitution hierarchy as its primary parsing mechanism.It also claims a provable structural advantage over periodic alternatives with bounded period.
  • Quasicryth’s structural approach: Quasicryth uses a deterministic quasicrystalline structure to expose phrase-level contexts instead of many parallel adaptive bit-level models.The hierarchy context supplies specialised arithmetic-coding sub-models without bitstream cost.

3. Method

Quasicryth tokenizes text into words, builds frequency-ranked Fibonacci-length codebooks, and selects phrase positions from multiple irrational tilings. It then encodes the selected events with adaptive arithmetic coding, caching, context models, LZ77, and an LZMA-compressed escape stream.

  • Input and codebooks: The pipeline tokenizes and lowercases input words while separately encoding case information.On enwik9, the word-token sequence contains 298,263,298 tokens and case coding contributes approximately 2.04% of the original.
  • Input and codebooks: Eleven frequency-ranked codebooks cover phrase lengths from 1 through 144 words using the first eleven Fibonacci numbers.Long n-gram counters are pruned periodically, and the serialized codebook is LZMA-compressed.
  • Quasicrystalline tiling: Each tiling assigns L or S by an irrational cut-and-project rule, with L representing a bigram and S a unigram position.Adjacent S tiles are merged into an L tile to enforce the matching rule.
  • Quasicrystalline tiling: The compressor evaluates 36 irrational tilings and selects the tiling maximizing its scoring function.The set includes golden-ratio tilings and additional candidates found through greedy optimization.
  • Hierarchy construction: Inverse Fibonacci substitution builds the hierarchy, and a position qualifies for level-k lookup only when it is the leftmost child of super-L tiles through that level.Deep matches from all tilings are collected and greedily selected with deepest matches preferred.
  • Event encoding: The payload encoder combines order-2 level contexts, context-conditioned indices, recency caches, two-tier unigram coding, and word-level LZ77.Out-of-vocabulary words are stored as raw-byte escapes and compressed with LZMA.

4. Theoretical Analysis

The theoretical analysis proves that Fibonacci hierarchies retain both tile types at every depth, unlike periodic hierarchies that collapse after logarithmic depth. It derives scale-invariant coverage, maximal aperiodic codebook efficiency, bounded overhead, and coding advantages under stated dependence assumptions.

  • Scale-invariant coverage: Potential coverage satisfies C(m) = P(m) · F_m → Wφ/√5, so dictionary reuse capacity remains constant across depth.The result balances exponentially fewer positions against exponentially longer phrases.
  • Codebook efficiency: Sturmian complexity p(n) = n + 1 yields F_m+1 tile-type patterns at level m and maximal coverage efficiency η_m = C_m/(F_m+1) among aperiodic tilings.The paper characterizes Fibonacci as the only aperiodic sequence combining non-collapse with maximum efficiency at every level.
  • Information-theoretic consequence: For long-range phrase dependencies extending beyond periodic collapse, Fibonacci has strictly lower coding entropy than the collapsed periodic alternative.The theorem states the comparison for m-LRPD sources.
  • Redundancy and dictionary value: Coding redundancy decays as O(e^-φ^m/λ) for Fibonacci versus fixed Ω(e^-F_m*/λ) for periodic tilings.The analysis also states that per-entry dictionary value grows as Ω(φ^m) without a periodic equivalent.
  • Non-collapse: Fibonacci supertile sequences contain both L and S types at every hierarchy level, preserving lookup positions for all depths.Periodic tilings collapse within O(log p) levels and then have zero deep positions.
  • Deflation dynamics: Fibonacci level counts shrink by 1/φ per deflation while the L-to-S ratio remains exactly φ.The count vector remains proportional to the Perron-Frobenius eigenvector at every level.

4.5 Theorem: All Periodic Tilings Collapse

The periodic-collapse analysis attributes failure to the irrational eigenstructure mismatch between periodic rational frequencies and the Fibonacci ratio. Deflation amplifies the mismatch until one tile type disappears, while irrational rotations remain equidistributed at every hierarchy level.

  • Collapse theorem: Every periodic tiling with period p collapses by a finite level k* ≤ ⌈log_φ p⌉, after which one tile type is absent.The level-k* supertile sequence contains only one tile type.
  • Eigenvector mechanism: Any periodic rational L-frequency has a nonzero component along the expanding eigenvector, so deflation eventually drives the hierarchy to collapse.The irrational Fibonacci frequency is the unique case with zero coefficient for that component.
  • Period-5 example: For Period-5, collapse is predicted near level 3.3 and experimentally completes at level 4.The trajectory reaches all-L at level 3 and all-S at level 4.
  • Period-5 example: At level 4, Period-5 has zero positions for 13-, 21-, 34-, 55-, 89-, and 144-gram lookups.The collapse follows from its rational frequency 3/5 differing from φ.
  • Irrational versus rational rotations: Fibonacci supertile sequences remain irrational rotations, so equidistribution and uniform tile density persist at every hierarchy level.Periodic rational rotations visit finitely many points and lose equidistribution beyond their period.
  • Sturmian structure: Sturmian balance and minimal factor complexity provide broad lookup coverage with exactly n + 1 distinct length-n factors.Periodic sequences cannot satisfy both aperiodicity and this minimal complexity behavior.

4.10 Theorem: Sturmian Codebook Efficiency

Fibonacci hierarchies achieve maximal codebook coverage efficiency because their Sturmian structure has the minimum aperiodic factor complexity, p(n)=n+1, at every level.

  • Sturmian structure: p(n)=n+1 is the minimum factor complexity for any aperiodic binary sequence and characterizes Sturmian sequences.The Morse–Hedlund theorem links aperiodicity to p(n)≥n+1, with equality throughout defining Sturmian structure.
  • Codebook efficiency: A codebook of C_m entries achieves coverage efficiency C_m/(F_m+1), strictly exceeding the bound for non-Sturmian aperiodic tilings.Non-Sturmian sequences have at least F_m+2 patterns, yielding efficiency at most C_m/(F_m+2).
  • Sturmian structure: At hierarchy level m, Fibonacci tilings have exactly F_m+1 distinct tile-type patterns, minimizing structural diversity among aperiodic sequences.This minimality persists under deflation because every hierarchy level remains Sturmian.
  • Codebook efficiency: Fibonacci tilings preserve non-collapse and maximum codebook efficiency simultaneously at every hierarchy depth.Periodic sequences collapse, while higher-complexity aperiodic sequences sacrifice coverage efficiency.
  • Scale-invariant coverage: Periodic tilings contribute zero at all levels beyond collapse, whereas Fibonacci levels retain nonzero potential coverage.The periodic contribution is zero regardless of corpus size after collapse.
  • Scale-invariant coverage: The Golden Compensation property makes potential coverage asymptotically Wφ/√5 and approximately 0.724W, independent of hierarchy level.Position-count decay and phrase-length growth cancel exponentially across levels.

4.13 Theorem: Level Activation Threshold

The activation threshold determines when a Fibonacci n-gram level begins contributing useful codebook hits; newly activated levels increase the advantage over collapsed periodic baselines.

  • Activation threshold: A Fibonacci level contributes when its expected hit count, based on available positions and hit rate, reaches the required threshold T_m.The threshold follows by counting candidate super-L positions, applying hit rate r_m, and solving for corpus size.
  • Activation threshold: The 89-gram and 144-gram codebooks are empty at enwik8 but active at enwik9 because repeated occurrences are needed for codebook formation.The practical formation threshold is much larger than the one-hit threshold, with effective T_m on the order of hundreds to thousands.
  • Advantage growth: Between activation thresholds, the aperiodic advantage is linear in corpus size; each newly active level increases the slope.The resulting advantage is piecewise-linear and convex with monotonically increasing slopes.
  • Advantage growth: The advantage jump from 100 MB to 1 GB is 33× because two new linear terms activate, not because existing terms grow superlinearly.The newly active levels are 89-gram and 144-gram; growth between earlier thresholds is slightly sub-linear.
  • Overhead: Fibonacci flag overhead is bounded by 1/φ≈0.618 bits per word even with infinitely many active levels.The bound follows from a convergent geometric series of position counts.

4.16 Theorem: Strict Coding Entropy for Long-Range Sources

For sources with long-range phrase dependencies, Fibonacci hierarchies exploit longer contexts and achieve strictly lower coding entropy than periodic hierarchies that collapse at finite depth.

  • Entropy inequality: For an m-LRPD source with m beyond the periodic collapse level, H_fib(P)<H_per(P) in the limit of sufficient codebook capacity.The strict gap follows from the Fibonacci hierarchy’s access to longer predictive contexts.
  • Entropy inequality: Fibonacci lookup positions support F_m-word contexts, giving coding cost no worse than the corresponding conditional entropy h_Fm(P).Contexts at multiple Fibonacci scales let the coder select the best available context at each position.
  • Long-range dependence: Long-range dependence makes h_Fm(P) strictly lower than the entropy available at the periodic collapse scale.The m-LRPD condition states that longer context carries additional predictive information.
  • Long-range dependence: A periodic tiling cannot exploit contexts longer than F_m* because it has no super-L positions beyond its collapse level.Its coding entropy is therefore bounded below by h_Fm*(P).
  • Empirical implication: On Wikipedia-class corpora, nonzero hits through 144-word phrases support long-range dependence at those scales, with a reported enwik9 advantage of 1,349,371 B.The byte-level advantage is attributed to the entropy gap accumulated over approximately 298 million word positions.
  • Scope: If longer contexts add no information beyond a finite scale, the two tilings achieve equal coding entropy under the stated condition.The structural advantage can remain distinct from the information-theoretic advantage.

Redundancy Bound

Fibonacci hierarchy redundancy decays super-exponentially with depth under exponential mixing, while a periodic hierarchy remains fixed at its collapse-scale redundancy.

  • Redundancy decay: Under exponential mixing, Fibonacci redundancy decays super-exponentially in hierarchy index m, exponentially in φ^m.The rapid decay follows from Fibonacci phrase lengths growing exponentially with m.
  • Redundancy decay: Redundancy falls from 17.5 bits at F_4=3 to 0.024 bits at F_11=89, a 700× reduction.At F_12=144, redundancy is effectively zero, below 0.002 bits.
  • Periodic comparison: A periodic tiling collapsing at m*=4 remains at R_3(P)≤17.5 bits of residual redundancy per word.It cannot access deeper contexts after collapse.
  • Periodic comparison: Each Fibonacci level removes an exponentially larger slice of residual redundancy than the previous level.The periodic system is permanently locked at its collapse-scale residual redundancy.
  • Dictionary efficiency: Per-entry compression gain grows approximately with F_m because bounded codebook-addressing cost becomes negligible for long phrases.At the 89-gram level, each hit saves approximately 438 bits; deeper hits remain strongly net-positive.
  • Dictionary efficiency: The 144-gram level has per-entry gain E_9≈144h̄−6.6 bits, about 72× the bigram gain.The comparison uses F_9/F_1=72.

5. Experimental Setup

The evaluation uses text files ranging from 152,089 bytes to 1 GB and compares Quasicryth with standard compressors and controlled parsing baselines. The controlled A/B tests hold codebooks, escapes, and arithmetic models constant so payload differences isolate parsing strategy.

  • Datasets: The benchmark spans alice29.txt, enwik8 subsets, enwik8, and enwik9, from 152,089 bytes to 1,000,000,000 bytes.The largest file contains 298,263,298 word tokens.
  • Baselines: The baselines include gzip -9, bzip2 -9, xz -9, All-unigram QTC, and Period-5 QTC.Period-5 uses the same L/S ratio as Fibonacci to isolate the aperiodic advantage.
  • Implementation: Quasicryth v5.6 is an ANSI C99 single-core implementation using 24-bit arithmetic coding and LZMA for escape and codebook compression.The codebase is approximately 4,000 lines and uses no SIMD or hardware-specific optimizations.
  • Controlled comparison: The A/B test compares three parsing strategies with codebooks built once from the input and identical escape streams.All strategies escape the same out-of-vocabulary words.
  • Controlled comparison: Only payload bytes differ in the controlled comparison, because codebooks, escape streams, and arithmetic coding models are identical.This design attributes payload-size differences solely to parsing strategy.

6. Results

Quasicryth improves compression through deep Fibonacci and multi-structure hierarchy positions that remain unavailable to collapsed periodic alternatives. At larger scales, newly activated levels increase deep hits, savings, and compression-side cost while decompression remains comparatively stable.

  • Compression performance: 225,918,349 B (22.59%) is Quasicryth’s enwik9 multi-structure result, surpassing bzip2 on all benchmarks and approaching xz.Fibonacci-only reaches 234,560,637 B (23.46%) on enwik9.
  • Deep hierarchy hits: 2,512,927 deep hierarchy hits occur on enwik9, whereas Period-5 provides zero hits at levels 4–9 after hierarchy collapse.Levels 8–9 first activate at enwik9 scale.
  • Deep hierarchy hits: 23× more total deep hits arise from enwik8 to enwik9 as existing levels scale with W and levels 8–9 add 7,570 new hits.The files increase by 10× in size.
  • Multi-structure distribution: 55-gram, 34-gram, and 21-gram hits increase by 56%, 20%, and 18% on enwik8 as multi-structure tilings redistribute matches toward deeper levels.A 55-gram hit encodes 55 words with one arithmetic-coding symbol versus 4.2 average words for a 13-gram.
  • Tiling families: 9,777,069 deep positions on enwik8 come from the golden-ratio family, while non-golden and optimized additions contribute 19.0% and 2.6%.The 36-tiling engine comprises 12 golden-ratio, 6 original non-golden, and 18 optimized tilings.
  • Tiling families: 181% and 169% of golden baselines are reached by 21-gram and 34-gram greedy-selected counts as optimized alphas redistribute shallower matches.The trigram line peaks at α = 0.502 before declining as positions move upward to deeper levels.
  • Timing: 33× is the enwik9 compression/decompression asymmetry, driven by 89-gram and 144-gram frequency counting, while decompression remains roughly 22 MB/s.Decompression regenerates the tiling without search or n-gram counting and performs one sequential pass.

7. Ablation Study

Ablations attribute Quasicryth’s gains to its multi-level aperiodic parsing structure and deeper matches rather than to codebook or escape-stream differences. The deepest hierarchy levels matter primarily on sufficiently large inputs, while several alternative designs add overhead or lose effectiveness.

  • Fibonacci versus no tiling: 2.07% of the original file size is saved by QC tiling on enwik9 as deeper hierarchy levels activate with input size.The comparison uses identical codebooks and escape streams.
  • Fibonacci versus Period-5: 36,243 B at 3 MB grows to 11,089,469 B at 1 GB for Fibonacci over Period-5 in the controlled payload comparison.Period-5 uses the same L/S ratio as Fibonacci, with identical codebooks and escape streams.
  • Multi-structure ablation: 778,933 B (−3.57%) at enwik8 and 8,642,288 B (−4.56%) at enwik9 are payload reductions from multi-structure over Fibonacci-only.Escape streams, codebooks, and case flags remain identical; only the arithmetic-coded payload differs.
  • Scale effects: 8.9× growth in aperiodic advantage accompanies a 10× file-size increase from 100 MB to 1 GB.The superlinear increase occurs as the 89-gram and 144-gram levels activate at enwik9 scale.
  • Version progression: 89-gram and 144-gram levels do not improve alice29.txt compression because 36K words provide insufficient repetitions to populate those codebooks.Their contribution is visible only at enwik9 scale.
  • Rejected approaches: The adaptive online codebook was abandoned because its cold-start penalty outweighed savings on medium-sized inputs, making QC contribution negative on small files.All-L also lacked the multi-level hierarchy needed for trigram and higher-order positions.

8. Conclusion

The paper combines a proof of Fibonacci hierarchy non-collapse with measurements showing aperiodic payload gains over periodic and no-tiling baselines. Its conclusion is that deep, structurally determined positions drive the advantage, especially as larger files activate new levels.

  • Conclusion: 11,089,469 B at enwik9 is the measured Fibonacci advantage over Period-5, growing superlinearly as 89-gram and 144-gram levels activate.Period-5 achieves zero deep positions because its hierarchy collapses at level 4.
  • Conclusion: 2,512,927 deep hierarchy positions are exploited at enwik9, while Period-5 exploits none at levels 4–9.This empirical contrast matches the predicted collapse behavior.
  • Conclusion: The 36-tiling engine combines 12 golden-ratio, 6 original non-golden, and 18 optimized tilings.The optimized search identifies α = 0.502 as providing complementary trigram and 5-gram coverage.
  • Conclusion: 26.25% is achieved on enwik8, a 0.78 percentage-point improvement over Fibonacci-only.The full system also uses word-level LZ77 preprocessing, LZMA escape compression, and a variable-context model.
  • Conclusion: The paper identifies Quasicryth as the first compressor claimed to show a provable, structurally motivated, empirically quantified aperiodic advantage over periodic alternatives.The claimed contribution is grounded in the Fibonacci quasicrystal’s shared mathematical structure.
Loading 2603.14999v2…