Linear Boolean classification, coding and “the critical problem”

NEW

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

$$m^*(S_n)=\min\{\operatorname{rank}T:T:\mathbb F_2^n\to \mathbb F_2^m\text{ linear and injective on }S_n\}.$$

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

$$f:\mathbb F_2^a\to\mathbb F_2^b$$

and define its graph

$$S_f=\{(x,f(x)):x\in\mathbb F_2^a\}\subseteq\mathbb F_2^n .$$

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

$$m^*(S_f)=a=\log_2|S_f|.$$

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

$$|A\cap S_f|\sim \operatorname{Bin}\bigl(2^t,2^{d-t-b}\bigr),$$

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

$$\Pr(|A\cap S_f|\ge L)\le (e/L)^L.$$

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

$$\frac{|S_{f_n}|}{n^3}=2^{a-O(\log n)}=2^{n/2-o(n)}$$

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.