Random linear-size fingerprint code exists nonuniformly

Fix distinct $x,y$. In each coordinate, the independent random bits $E_i(x),E_i(y)$ disagree with probability $1\mathrm{/}2$, independently across the $32n$ coordinates. Thus their Hamming distance $S$ is a sum of independent Bernoulli$(1\mathrm{/}2)$ variables with mean $16n$. By [F1] with $\alpha =1\mathrm{/}2$, $\mathrm{Pr}(S\le 8n)\le e^{-2n}$.

Order the $2^n$ inputs lexicographically and index the $\left(\genfrac{}{}{0px}{}{2^n}{2}\right)<2^{2n}$ unordered pairs by $x<y$. For each such pair, let $B_{xy}$ be the event that its distance is below $8n$. On every codebook, the indicator of ${\bigcup }_{x<y}{B}_{xy}$ is at most ${\sum }_{x<y}{\mathbf{1}}_{B_{xy}}$; summing this pointwise inequality against the finite probability weights in [F2] gives the union bound $\mathrm{Pr}({\bigcup }_{x<y}{B}_{xy})\le {\sum }_{x<y}\mathrm{Pr}(B_{xy})$. By step 1.1 this is at most $2^{2n}{e}^{-2n}=e^{(2\ln 2-2)n}<1$, since $\ln 2={\int }_1^{2}du\mathrm{/}u<1$. Hence some finite codebook has every pairwise distance at least $8n$, which is relative distance at least $1\mathrm{/}4$. For each $n$, order all finite codebooks lexicographically and choose the first one with this property; this defines a nonuniform family without an arbitrary-choice axiom. The exhaustive selection gives no polynomial-time construction or efficient uniform encoder.