Good Locally Testable Codes with Small Alphabet and Small Query Size

Ben-Sasson, Goldreich and Sudan showed that a binary error correcting code admitting a $2$-query tester cannot be good, i.e., it cannot have both linear distance and positive rate. The same holds when the alphabet is a finite field F, the code is F-linear, and the $2$-query tester is F-linear. We show that those are essentially the only limitations on the existence of good locally testable codes (LTCs). That is, there are good $2$-query LTCs on any alphabet with more than $2$ letters, and good $3$-query LTCs with a binary alphabet. Similarly, there are good $3$-query F-linear LTCs, and for every F-vector space V of dimension greater than $1$, there are good $2$-query LTCs with alphabet V whose tester is F-linear. This completely solves, for every q≥ 2 and alphabet (resp. F-vector space) $Σ$, the question of whether there is a good q-query LTC (resp. F-LTC) with alphabet $Σ$. Our proof builds on the recent good $2$-query F-LTCs of the first author and Kaufman, by establishing a general method for reducing the alphabet size of a low-query LTC.