Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs

We prove that any linear $3$-query locally correctable code C F₂ᵏ → F₂ⁿ with constant correction radius must have length n ≥ 2Ω(√k). This improves on the prior best lower bound of 2Ω(√k/log k), due to [AG24], and shows that the folklore construction of linear $3$-LCCs from Reed-Muller codes, which achieve length n = 2O(√k), is optimal up to constant factors in the exponent. Our proof builds on the approach of [KM24a], further refined in [Yan24,KM24b], that uses "chain derived equations" in combination with Kikuchi graphs. The crux of our argument is to show that a certain edge-coloured Kikuchi graph has a unique colour cycle: a cycle in which some colour is used exactly once. We do this by controlling the distribution of colours at each vertex in the graph using a random walk mixing argument and a novel hypergraph decomposition based on edge expansion of the hypergraph's "flattening" into a graph.