{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:55:45Z","timestamp":1787324145307,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Motivated by questions in property testing, we search for linear error-correcting codes that have the \u201csingle local orbit\u201d 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 \u201csparse\u201d binary code whose coordinates are indexed by elements of $\\mathbb{F}_{2^n}$ for prime $n$ and whose symmetry group includes the group of nonsingular affine transformations of $\\mathbb{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. 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 $\\mathbb{F}_{2^n}$ for prime $n$ are locally testable. If, in addition to $n$ being prime, $2^n-1$ does not have large divisors, then we get that every sparse cyclic-invariant code also has the single local orbit. In particular this implies that BCH codes of such length are generated by a single low-weight codeword and its cyclic shifts.<\/jats:p>","DOI":"10.1137\/100818364","type":"journal-article","created":{"date-parts":[[2012,11,15]],"date-time":"2012-11-15T10:37:23Z","timestamp":1352975843000},"page":"1618-1634","source":"Crossref","is-referenced-by-count":4,"title":["Succinct Representation of Codes with Applications to Testing"],"prefix":"10.1137","volume":"26","author":[{"given":"Elena","family":"Grigorescu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tali","family":"Kaufman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,11,15]]},"reference":[{"key":"atyp_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856958"},{"key":"atyp_ref2","doi-asserted-by":"publisher","DOI":"10.1109\/18.135638"},{"key":"atyp_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"atyp_ref4","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-05-00476-5"},{"key":"atyp_ref5","first-page":"99","author":"Bourgain J.","year":"2007","journal-title":"Berlin"},{"key":"atyp_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2006.01.022"},{"key":"atyp_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0451-1"},{"key":"atyp_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S1631-073X(03)00281-4"},{"key":"atyp_ref9","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-57-02406-7"},{"key":"atyp_ref10","unstructured":"10.\u2002P. Charpin, <i>Open problems on cyclic codes<\/i> in Handbook of Coding Theory, vol. 1, North-Holland, Amsterdam, 1998."},{"key":"atyp_ref11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055435"},{"key":"atyp_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atyp_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"atyp_ref14","unstructured":"14.\u2002E. Grigorescu, <i>Symmetries in Algebraic Property Testing<\/i> Ph.D. thesis, MIT, Cambridge, MA, 2010."},{"key":"atyp_ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2167739"},{"key":"atyp_ref16","first-page":"534","author":"Grigorescu E.","year":"2009","journal-title":"Algorithms and Techniques"},{"key":"atyp_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20262"},{"key":"atyp_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.16"},{"key":"atyp_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/11617983_28"},{"key":"atyp_ref20","first-page":"788","author":"Kaufman T.","year":"2011","journal-title":"Proceedings of the Annual IEEE Symposium on Foundations of Computer Science"},{"key":"atyp_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445615"},{"key":"atyp_ref22","first-page":"590","author":"Kaufman T.","year":"2007","journal-title":"Proceedings of the Annual IEEE Symposium on Foundations of Computer Science"},{"key":"atyp_ref23","first-page":"403","author":"Kaufman T.","year":"2008","journal-title":"Proceedings of the Annual ACM Symposium on Theory of Computing"},{"key":"atyp_ref24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011220817609"},{"key":"atyp_ref25","unstructured":"25.\u2002F. J. MacWilliams and N. J. A. Sloane, <i>The Theory of Error-Correcting Codes<\/i> Elsevier\/North-Holland, Amsterdam, 1981."},{"key":"atyp_ref26","unstructured":"26.\u2002R. M. Roth, <i>Introduction to Coding Theory<\/i> Cambridge University Press, Cambridge, UK, 2006."},{"key":"atyp_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"atyp_ref28","unstructured":"28.\u2002D. Shanks, <i>Solved and Unsolved Problems in Number Theory<\/i> vol. 1, Spartan Books, Washington, DC, 1962."},{"key":"atyp_ref29","doi-asserted-by":"crossref","unstructured":"29.\u2002H. Stichtenoth, <i>Algebraic Function Fields and Codes<\/i> 2nd ed., in Grad. Texts in Math. 254,    Springer-Verlag,  Berlin, 2009.","DOI":"10.1007\/978-3-540-76878-4"},{"key":"atyp_ref30","doi-asserted-by":"crossref","unstructured":"30.\u2002J. H. van Lint, <i>Introduction to Coding Theory<\/i> 3rd ed., Grad. Texts in Math. 86, Springer-Verlag, Berlin, 1999.","DOI":"10.1007\/978-3-642-58575-3"},{"key":"atyp_ref31","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1983-0679454-X"},{"key":"atyp_ref32","unstructured":"32.\u2002A. Weil, <i>Sur les courbes alg\u00e9briques et les vari\u00e9t\u00e9s qui s'en d\u00e9duisent<\/i> Vol. 1,  Actualit\u00e9s Sci. Indust., Hermann, Paris, 1948."},{"key":"atyp_ref33","unstructured":"33.\u2002Wikipedia, <i>Lenstra-Pomerance-Wagstaff Conjecture<\/i> http:\/\/en.wikipedia.org\/wiki\/Mersenne_ conjectures  (30 Aug. 2012)."},{"key":"atyp_ref34","first-page":"119","volume":"2","year":"1991","journal-title":"Commun. Comput."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100818364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:22Z","timestamp":1787321962000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100818364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/100818364"],"URL":"https:\/\/doi.org\/10.1137\/100818364","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}