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^ (k). (3) If C is a smooth, non-linear 3-LCC with completeness 1 -, then n (k^1{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.