Linear Boolean classification, coding and “the critical problem”

NEW

Problem: Reconstructed statement: for a sequence $S_n\subseteq \mathbb F_2^n$, let

The conjecture asserts that if $m^*(S_n)=\log_2|S_n|+o(n)$, then $S_n$ is contained in the union of $2^{o(n)}$ affine subspaces whose underlying subspaces have size at most $|S_n|$.

Result: The conjecture is false.

Let $n=a+b$, with $a=\lfloor n/2\rfloor$, $b=\lceil n/2\rceil$. Choose a function

and define its graph

Then $|S_f|=2^a$. Projection onto the first $a$ coordinates is linear and injective on $S_f$, so $m^*(S_f)\le a$. Conversely, any injective linear image of $S_f$ has at least $2^a$ points, so its rank is at least $a$. Hence

Now choose $f$ randomly, independently and uniformly at each $x$. Fix an affine subspace $A\subseteq\mathbb F_2^a\times\mathbb F_2^b$ of dimension $d\le a$. If its projection to $\mathbb F_2^a$ has dimension $t$, then every nonempty fiber has size $2^{d-t}$. Thus

with mean $2^{d-b}\le1$. For $L=n^3$,

There are only $2^{O(n^2)}$ affine subspaces of dimension at most $a$, so a union bound gives, with positive probability, that every affine subspace of size at most $2^a=|S_f|$ meets $S_f$ in fewer than $n^3$ points.

Choose such an $f=f_n$. Any cover of $S_{f_n}$ by affine subspaces of size at most $|S_{f_n}|$ then needs at least

members, not $2^{o(n)}$. Thus the hypothesis holds exactly, while the claimed conclusion fails.

Verification audit: the linear compression definition matches the paper’s definition; the covering objects are precisely translates of subspaces of size at most $|S_n|$; no extra assumptions were used.

Citation: No known literature citation for this counterexample. The conjecture appears in Abbe–Alon–Bandeira–Sandon, “Linear Boolean classification, coding and ‘the critical problem’,” arXiv:1401.6528.