Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Exact cost of narrow k-bonacci windows

Abstract

Complete literal windows acquire monochromatic initial phase labels at exact cost.

Fix k at least two and a positive complete word width m. Words are read from left to right, with the first position having the lowest weight. The original weights G_i are dbonacci k (i+2): the first k weights are powers of two, and each later weight is the sum of the preceding k weights. Values and their sums below belong to ZMod 2. Every zero bit advances the position. The scanner records the consecutive final ones and rejects on the kth consecutive one. Rejection, written none, is distinct from both scalar values and is absorbing.

A hidden source is an actual finite literal history w of length divisible by m. On acceptance its joint coordinates are its scalar value, its length modulo T=k+1, and its actual final run of ones. These coordinates arise from the same word. The selector receives only the free initial endpoint output and the chronological archive H of complete issued words and their endpoint outputs. Its two choices are to stop with a label or to append one complete m-position word. No initial length, phase, or tail is available to the selector.

Execution E uses a natural bound d on the number of issued words. At bound zero a stop succeeds and a further action fails. Every issued word contributes one unit, even when it is all zero, has a constant endpoint, or contains only padding. The hidden history grows by literal concatenation. The initial phase label is retained as the correctness target throughout these destructive updates.

Here a=true restricts actions to words internally avoiding k consecutive ones, while a=false allows every complete Boolean word. Both execute the actual scanner across seams. F(a,lambda,r,v,d) requires one selector to be correct on every accepted initial history with free value v and compatible initial phase, with total cost at most d. It also returns the prescribed initial rejection label r at zero cost on every initially rejected history. The index j identifies the initial phase -jg modulo T; the target lambda(j) is independent of the initial tail.

Theorem 1.1 (Least uniform budget for monochromatic windows).

Proof. Machine-checked in Lean as D5/S3/ObserverMemory/Algorithms/KBonacciAcquisition/NarrowWindowCost.narrow_window_cost (✓ std3). ∎

Source. Repository-derived.

Commentary.

The baseline is A=lambda(0). The index J is the largest index whose label differs from A, with J=0 for a constant target. In each interval t*u<j<=(t+1)*u, restricted to j<=J, all nonbaseline labels must agree. Labels are otherwise arbitrary: different windows can carry different labels, and a label can recur in several windows. Empty windows are included.

For the upper bound, issue B_t at the tth step until an endpoint differs from the initial value, or until D words have been issued. The complete word B_t has a one exactly at the displayed selected positions; every other position is zero. Its first bit is zero, distinct ones are at least g positions apart, and its final tail is at most one. It therefore accepts from every initial tail, and the next first zero protects each actual seam.

The original coefficient sequence modulo two has support at residues zero and k modulo T. A selected absolute position jg-1 contributes one exactly for initial phase -jg. Thus the scalar increment of B_t is one precisely for the nonbaseline indices in its own window. Before the first such increment all endpoints equal the initial value. A changed endpoint determines the common window label; after D unchanged endpoints the label is A. Every empty window and the final partial window still use one complete paid word.

The lower bound permits all adaptive selectors and all actions. Joint initial histories with any prescribed value, compatible phase, and tail are obtained by a simultaneous congruence construction: choose a sufficiently large length N divisible by m in the prescribed residue class modulo T, use a first correction bit, then zeros, then the prescribed final ones. The correction bit compensates the scalar contribution of the final ones.

When J>0, two different initial labels with tail k-1 force the first action to start with zero: a leading one would reject both and make every subsequent endpoint identical. Now take tail-zero initial histories of phases zero and -Jg with the same free value. For d<D, their first d*m continuation positions miss Jg-1 and Jg, and miss T-1. The sole phase-zero position at zero is suppressed by that first zero.

Every common continuation of at most d complete words therefore has equal scalar increments for the two sources. Their scanners have the same current tail and hence the same acceptance or rejection. Induction on the chronological archive forces the same later actions, including arbitrary leading ones, and the same terminal answer. Their different initial labels preclude success within d words.

The conclusion includes J=0, single-index windows u=1, empty windows, repeated labels, both free values, and both action alphabets. It places no condition Dm<T on the final padding: for k=9 and m=6, g=2, p=5, u=3, and J=4 give D=2 and Dm=12>T=10. Positions after the last selected pulse remain actual zero positions.

References