A Counterexample to Affine-Subspace Union Stability under Small Deletions

Primarily AI-generated textHuman understanding: no partscs.CC — Computational Complexity

Contributed by YURAN XIU ↗

Version 1 / Oct 18, 2026 / CC BY 4.0

Abstract

We construct a family of affine coordinate subspaces of

\mathbb{F}_2^N

whose union is the entire space, but for which deleting a

1/N

fraction from each member removes a fraction larger than

N^{-c}

from the union, for every fixed

c>0

and arbitrarily large

N

. Each subspace has codimension

\log_2 N

, and the family has at most

2N^2

members. The construction uses all monochromatic coordinate conditions of size

k

on

2k

distinguished coordinates, where

N=2^k

, and deletes their common intersection with the middle Hamming layer. The exact global loss is

\binom{2k}{k}/4^k

. This disproves the affine-union conjecture of Alekseev and Gaevoy, already for their fixed parameters

q=2

and

r=1

. The all-exponent, arbitrarily-large-dimension counterexample has been formalized and checked in Lean 4. HAL deposit: hal-05800246v1.

Yaroslav Alekseev and Nikita Gaevoy. New Polynomial-Depth Res(+) Lower Bounds. Electronic Colloquium on Computational Complexity , Report TR26-007, 2026. https://eccc.weizmann.ac.il/report/2026/007/. Conjectures 1.4 and 4.2.link