OctoInformBeta

OpenAI preprint, September 2026 · §4. An exponential bound for order-reversing images · §4.2

§4.2 (setting): the target bound D(h): The target bound D(h)=2⌊(h−2)/127⌋D(h) = 2^{\lfloor (h-2)/127 \rfloor}, exponential in hh, satisfies D(h)=2D(h−127)D(h) = 2D(h-127) for every h≥129h \ge 129

The exponential target bound and its doubling step.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

One part of the exponential state lower bound for complementing two-way nondeterministic finite automata aims at an explicit target: a power of two D(h)D(h) in a natural number hh, exponential in hh. The question for this item is how far hh has to move for D(h)D(h) to double.

The Target Bound

The target bound D(h)D(h) of a natural number hh is the power of two D(h)=2⌊(h−2)/127⌋.D(h) = 2^{\lfloor (h-2)/127 \rfloor}.(1)✦

The Claim

Theorem 1. Let hh be a natural number with h≥129h \ge 129. Then D(h)=2D(h−127).D(h) = 2\,D(h-127).(2)✦

In the paper, the result reads: with t=64t = 64, the target bound is D(h)=2⌊(h−2)/(2t−1)⌋D(h) = 2^{\lfloor (h-2)/(2t-1) \rfloor} for h≥2h \ge 2.

What Is Checked

The claim is stated over the target bound DD of (1), at every natural number h≥129h \ge 129.