Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs

We give improved lower bounds for binary $3$-query locally correctable codes (3-LCCs) C \0,1\ᵏ → \0,1\ⁿ. Specifically, we prove: (1) If C is a linear design 3-LCC, then n ≥ 2(1 - o(1))√k. A design 3-LCC has the additional property that the correcting sets for every codeword bit form a perfect matching and every pair of codeword bits is queried an equal number of times across all matchings. Our bound is tight up to a factor √8 in the exponent of $2$, as the best construction of binary $3$-LCCs (obtained by taking Reed-Muller codes on F₄ and applying a natural projection map) is a design $3$-LCC with n ≤ 2√8 k. Up to a √8 factor, this resolves the Hamada conjecture on the maximum F₂-codimension of a $4$-design. (2) If C is a smooth, non-linear $3$-LCC with near-perfect completeness, then, n ≥ kΩ(log k). (3) If C is a smooth, non-linear $3$-LCC with completeness 1 - ε, then n ≥ Ω̃(k1/2ε). In particular, when ε is a small constant, this implies a lower bound for general non-linear LCCs that beats the prior best n ≥ Ω̃(k³) lower bound of [AGKM23] by a polynomial factor. Our design LCC lower bound is obtained via a fine-grained analysis of the Kikuchi matrix method applied to a variant of the matrix used in [KM23]. Our lower bounds for non-linear codes are obtained by designing a from-scratch reduction from nonlinear $3$-LCCs to a system of "chain polynomial equations": polynomial equations with similar structure to the long chain derivations that arise in the lower bounds for linear $3$-LCCs [KM23].