Zero-Error Online Memory under Blind Overwrites: Global One-Write Saturation, Sharp Storage Gaps, and Syndrome Compatibility

Abstract

We investigate the exact memory complexity of zero-error online encoding under blind coordinate overwrites. A finite-state encoder maintains a binary record through successive assignments, while a decoder reconstructs erased coordinates using the stored state and the remaining visible coordinates. Our analysis establishes a general lower bound on online state complexity through incidence counting and extremal binary coding theory. For an update horizon T and an erasure budget q, write s = T + q, and let A(n,s) denote the maximum size of a binary code of length n and minimum distance at least s. The resulting state-complexity bound is K ≥ 2^n(s + 1) / (A(n,s) + s). This leads to an exact saturation theorem: when T ≥ 1 and s ≥ ⌈n/2⌉ + 1, the optimal online memory requirement reaches n bits. We establish an explicit infinite family exhibiting a sharp logarithmic separation between online and static memory. For n = 4(2^k − 1), T = 1, and q = n/2, the optimal online memory requirement is n bits, while the static optimum is n − k bits. The resulting separation is exactly k = log₂(n/4 + 1). A column-completion construction extends logarithmic separation to all sufficiently large block lengths, yielding a gap of at least (2/3)log₂n − O(log log n). Further results include horizon-uniform memory bounds, multiround pair-amplification inequalities, and exact compatibility-graph colorings for syndrome encoders constructed through affine-subspace deletion from Hamming parity-check matrices. These results connect the state complexity of online information maintenance with extremal coding theory and algebraic graph coloring.