Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation

A pointwise-unbiased one-bit compressor reconstructs every real input in expectation while transmitting one bit. For a scalar source P with CDF F, mean m, and mathcal J(P)=intmathbb R√F(r)(1-F(r)),dr, we prove that the infimum of the source-averaged reconstruction second moment over all public-coin one-bit codes unbiased on mathbb R is m2+mathcal J(P)2. For regular full-support sources, a distribution-centered random-threshold code attains this value; a converse over arbitrary randomized binary encoders and an equality analysis characterize every attaining code up to null sets, bit relabeling, and public-seed refinement. For the Gaussian location family mathcal N(μ,σ2) with |μ|≤ cσ, the equal prior on the endpoint means is least favorable and the minimax value is σ2Lambdac2. Exact Gaussian minimax optimality forces a critical heavy tail: at the endpoint means, absolute moments are finite exactly for p<3, and Pr(W>t)=Theta(t-3/√log t). A Cauchy-mixture robustification inflates the second moment by at most 1/(1-η) while making every positive-order absolute moment finite. Finite-support public randomness with finite decoder means cannot achieve exact unbiasedness on mathbb R, but a bounded-output approximation using exactly R shared random bits has explicit bias and second-moment bounds converging to the minimax constant. Finally, coordinate allocation communicates exactly B bits per Gaussian-gradient query. On Kim's continuous quadratic hard family, the expected optimization guarantee matches the lower bound in its dependence on (σ,d,B,varepsilon), and a finite-variance high-probability bound incurs only a logarithmic confidence factor.