Title

In Property Testing the goal is to quickly distinguish objects that satisfy a property from objects that need to be changed in a large fraction of places in order to satisfy the property. In this context, Locally Testable Codes (LTCs) are error-correcting codes for which membership can be decided from reading only a small section of the input. Recent studies of LTCs focus on identifying what attributes of codes allow them to be testable by local inspection. In particular, the ``symmetries of a code seem to play an important role in providing sufficient conditions for testing. Kaufman and Sudan supported this view by showing that the duals of linear codes that have the ``single local orbit property under the affine symmetry group are locally testable. A code has the single local orbit property if it is specified by a single local constraint and its translations under the symmetry group of the code.

In this talk I will present a result motivated by questions arising in previous studies of LTCs regarding error-correcting codes that have the single local orbit property. We show that the dual of every ``sparse'' binary code whose coordinates are indexed by elements of F_{2^n} for prime n, and whose symmetry group includes the group of non-singular affine transformations of F_{2^n}, has the single local orbit property. (A code is said to be sparse if it contains polynomially many codewords in its block length.) In particular this class includes the dual-BCH codes for whose duals (i.e., for BCH codes) simple bases were not known. Our result gives the first short (O(n)-bit, as opposed to the natural exp(n)-bit) description of a low-weight basis for BCH codes.

If, in addition to n being prime, if 2^n-1 is also prime (i.e., 2^n-1 is a Mersenne prime), then we get that every sparse cyclic code also has the single local orbit. In particular this implies that BCH codes of Mersenne prime length are generated by a single low-weight codeword and its cyclic shifts.

Our techniques involve the use of recent results from additive number theory to prove that the codes we consider, and related codes emerging from our proofs, have high distance. We then combine these with the MacWilliams identities and some careful analysis of the invariance properties to derive our results.

[Joint work with Tali Kaufman and Madhu Sudan.]