TR09-043 Authors: Elena Grigorescu, Tali Kaufman, Madhu Sudan

Publication: 18th May 2009 15:00

Downloads: 1488

Keywords:

Motivated by questions in property testing, we search for linear

error-correcting codes that have the ``single local orbit'' property:

i.e., they are specified by a single local

constraint and its translations under the symmetry group of the

code. 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

{\em 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.

The interest in the ``single local orbit'' property comes

from the recent result of Kaufman and Sudan (STOC 2008) that

shows that the duals of codes that have the single local

orbit property under the

affine symmetry group are locally testable.

When combined with our main result, this shows that all

sparse affine-invariant codes over the coordinates F_{2^n}

for prime n are locally testable.

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 {\em 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.

In retrospect, the single local orbit property has been central

to most previous results in algebraic property testing.

However, in the previous cases, the single local property was

almost ``evident'' for the code in question (the single local

constraint was explicitly known, and it is a simple

algebraic exercise to show that its translations under the symmetry

group completely characterize the code). Our work gives an alternate

proof of the single local orbit property, effectively by counting,

and its effectiveness is demonstrated by the fact that we are

able to analyze it in cases where even the local constraint is

not ``explicitly'' known.

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.