Exponential 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}^k → {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_4 and applying a natural projection map) is a design 3-LCC with n ≤ 2^{√8 k}. Up to a factor of 8, this resolves the Hamada conjecture on the maximum F_2-codimension of a 4-design. 2) If C is a smooth, non-linear, adaptive 3-LCC with perfect completeness, then, n ≥ 2^Ω(k^1/5). 3) If C is a smooth, non-linear, adaptive 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 Alrabiah-Guruswami-Kothari-Manohar 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 the work of Kothari and Manohar (2023). Our lower bounds for non-linear codes are obtained by designing a from-scratch reduction from nonlinear 3-LCCs to a system of 'chain XOR equations' - polynomial equations with a similar structure to the long chain derivations that arise in the lower bounds for linear 3-LCCs of Kothari and Manohar.