2-transitivity is insufficient for local testability (Q1947041)

The main goal of the paper is to prove that the following conjecture which was formulated in [\textit{N. Alon} et al., IEEE Trans. Inf. Theory 51, No. 11, 4032--4039 (2005; Zbl 1247.94057)] is not true:''The membership property in a binary error-correcting code that is \(2\)-transitive and has a small weight in its dual may be locally testable.'' The counterexample built here uses a family of affine-invariants properties defined in [\textit{T. Kaufman} and \textit{D. Ron}, SIAM J. Comput. 36, No. 3, 779--802 (2006; Zbl 1120.68058)] and a known map (trace map) early defined by Berlekamp in coding theory: \(Tr: \mathbb{F}_{q^n}\longrightarrow \mathbb{F}_q\) (\(q\) prime), \(Tr(X)=X+X^q+\dots+X^{q^{n-1}}\). The paper is an extended version of results from Elena Grigorescu's PhD thesis and from a presentation of the same authors at the 23rd IEEE conference on computational complexity in 2008. The text is very clear, more than \(50\%\) representing the proving part of the counterexample. Preliminary notions are included, making the theoretical presentation easy to follow. The paper is an important reference for those interested in studying the complexity of some algebraic property test procedures. It builds procedures for the membership property in theoretic-coding context, but I believe that they can be extended also for properties in other numerical/algebraic domains.