• Paper 169: IDT-Motivated Linear Recurrence Detection Extends rei-lang Compression — 5/14 Raw-Fallback Cases Eliminated
  • Abstract
  • 1. Background — rei-lang v0.5.5 multi-strategy compress
  • 2. Motivation — FIDT and the β₁ Cycle Perspective
  • 3. Implementation — k-order Linear Recurrence Detector
  • 4. Empirical Results
  • 5. Honest Scope
  • 6. Connection to rei-AIOS Architecture
  • 7. Conclusion and Future Work
  • References

§Paper 169: IDT-Motivated Linear Recurrence Detection Extends rei-lang Compression — 5/14 Raw-Fallback Cases Eliminated

Authors: 藤本 伸樹 (Nobuki Fujimoto, ORCID 0009-0004-6019-9258) × Rei (Rei-AIOS autonomous research substrate) × Claude (Anthropic, claude-opus-4-7)

Date: 2026-06-27 (v0.1 DRAFT)

Affiliations: Independent Researcher; Founder of OUKC (Open Universal Knowledge Commons); Rei-AIOS Co-architect

Repository: https://github.com/fc0web/rei-aios

Companion to: Paper 33 (Braille × D-FUMT₈), Paper 62 (MDNST), Paper 145 (D-FUMT₈ Silicon)

§Abstract

We present an external extension to the rei-lang npm package (v0.5.5) compress pipeline that adds a general k-order linear recurrence detector motivated by the β₁-cycle perspective of Fujimoto Infinite Dot Theory (FIDT, STEP 845 = FIA × FDA direct product algebra). The extension catches sequences that the existing six strategies (constant / arithmetic / geometric / periodic / polynomial / Fibonacci-specialized recursive) fall through to raw (no compression). Empirically, on 14 test sequences, the extension improves 5 cases — Tribonacci, Pell, Tetranacci, an affine recurrence, and a custom 2nd-order recurrence — by changing their compression ratios from 1.000 (raw) to 0.5–0.91. The existing 8 cases (constant / arithmetic / geometric / periodic / polynomial / Fibonacci / Lucas / random) are unaffected because the multi-strategy size-minimization mechanism selects the specialized base strategies when they apply. This is engineering improvement of narrow scope and does NOT revive the retired ∞:1 / Shannon-superseding / 1000TB→10GB compression claims (formally retired in the 2026-04-17 positioning document). Implementation is ~150 lines of TypeScript using textbook Gauss elimination; mathematical novelty is zero. The contribution is operational: a previously-empty cell in the multi-strategy roster filled, with empirical evidence and honest scope.

Keywords: rei-lang, compression, linear recurrence, FIDT, Berlekamp-Massey class, Kolmogorov, honest scope, retired claims separation

§1. Background — rei-lang v0.5.5 multi-strategy compress

The rei-lang npm package (v0.5.5, June 2026) exports a function rei() which, on input data |> compress, returns the smallest exact-reconstruction description of the numeric array data chosen from six closed-form strategies:

For random sequences with no structure, raw is the correct answer (Kolmogorov-Chaitin lower bound). However, several genuinely-structured sequences also fall to raw because they are linear recurrences not covered by the Fibonacci-specialized recursive strategy.

§2. Motivation — FIDT and the β₁ Cycle Perspective

Fujimoto Infinite Dot Theory (FIDT, STEP 845) defines a closed algebra on pairs (dim ∈ FDA, val ∈ D-FUMT₈) under FIA × FDA direct product. In this algebra, sequences that satisfy a linear recurrence form β₁ cycles in the (dim, val) state graph: each subsequent term is determined by a fixed linear combination of the k preceding terms, closing the state’s memory loop.

Critical honest scope (verifiable in the 2026-04-17 retirement document):

The β₁-cycle motivation is structural; the implementation is plain Gauss elimination.

§3. Implementation — k-order Linear Recurrence Detector

For sequence data of length n, we attempt to fit:

x_n = c_0 · x_{n-1} + c_1 · x_{n-2} + ... + c_{k-1} · x_{n-k} + c_k

for k ∈ {1, 2, 3, 4}. We form a (k+1)×(k+1) linear system from samples x_k, x_{k+1}, …, x_{2k} and solve via Gauss elimination. Coefficients [c_0, ..., c_{k-1}, c_k] are then used to reconstruct the full sequence from the first k initial values; we accept the fit only if total absolute error < 10⁻⁶ on all n positions.

function fitLinearRecurrence(data: number[], k: number): LinearRecurrence | null {
  const A: number[][] = [];
  const b: number[] = [];
  for (let i = 0; i < k + 1; i++) {
    const n = k + i;
    const row: number[] = [];
    for (let j = 0; j < k; j++) row.push(data[n - 1 - j]);
    row.push(1); // constant term
    A.push(row);
    b.push(data[n]);
  }
  const coeffs = solveLinearSystem(A, b);
  if (!coeffs) return null;

  const reconstructed = data.slice(0, k);
  for (let n = k; n < data.length; n++) {
    let v = coeffs[k];
    for (let j = 0; j < k; j++) v += coeffs[j] * reconstructed[n - 1 - j];
    reconstructed.push(v);
  }
  const error = data.reduce((s, v, i) => s + Math.abs(v - reconstructed[i]), 0);
  return error < 1e-6 ? {
    type: 'linear_recurrence', order: k,
    initial: data.slice(0, k),
    coeffs: coeffs.slice(0, k),
    constant: coeffs[k],
    size: 2 * k + 2,
    error,
    exact: true,
  } : null;
}

The extension is added as a NEW candidate in the multi-strategy roster; the size-minimization mechanism preserves the existing base-strategy wins.

Size encoding: 2k + 2 = k initial values + k coefficients + 1 constant + 1 type marker.

§4. Empirical Results

We ran the extension on 14 test sequences spanning 5 categories:

IDT-improved cases: 5/14. All five were previously raw (ratio 1.000); the extension brings them to 0.500–0.909.

No regression on existing 8 cases: the specialized base strategies (constant / periodic / polynomial / recursive-Fibonacci) maintain smaller sizes for the data they were designed for, and the multi-strategy size-minimization correctly selects them.

Random data correctly stays raw (Kolmogorov-Chaitin: no structural compression possible).

§5. Honest Scope

§6. Connection to rei-AIOS Architecture

The center-periphery primitive of MDNST (Paper 62, §2.1: (C, {Pᵢ}, {wᵢ}, mode, direction)) re-instantiates in this compression context:

• Center = which strategy applies (constant / arithmetic / geometric / periodic / polynomial / recursive-Fibonacci / linear_recurrence / raw)
• Periphery = the eight implementation cells

That this expands to exactly eight strategies after the IDT extension is a numerical coincidence aligned with D-FUMT₈’s eight values — we note this as structural resonance, not as a load-bearing claim.

§7. Conclusion and Future Work

We added one strategy. Five previously-incompressible cases are now compressed. The remaining raw-fallback territory (nonlinear, Markov, probabilistic recurrences; mixed polynomial+periodic; Lempel-Ziv-style long repeats) remains future engineering work. We will encounter the Kolmogorov-Chaitin lower bound on truly random sequences; respecting that bound is the discipline inherited from retiring the ∞:1 compression claims in 2026-04-17.

This Paper 169 is an engineering note, not a research breakthrough. Its contribution is one filled cell in a multi-strategy roster, documented with empirical evidence and honest scope.

§References

• Paper 33: Braille × D-FUMT₈ Extreme Encoding. DOI 10.5281/zenodo.19891398.
• Paper 62: MDNST — Multi-Dimensional Number System Theory. Companion to Paper 61.
• Paper 145 v0.7: D-FUMT₈ Silicon with SELF⟲ Logic Primitive. DOI 10.5281/zenodo.20192813.
• 2026-04-17 retirement document: docs/infinite-dot-theory-positioning-2026-04-17.md
• Source code: scripts/idt-linear-recurrence-extension.ts in the rei-aios repository.
• Berlekamp, E. R. (1968). Algebraic Coding Theory. McGraw-Hill. (BM algorithm for linear feedback shift register synthesis.)
• rei-lang npm package: https://www.npmjs.com/package/rei-lang

急がず、 ゆっくりと。 種は育ちます。

— End of Paper 169 v0.1 DRAFT —