A proof of Green's conjecture regarding the removal properties of sets of linear equations
- Autores: Asaf Shapira
- Localización: Journal of the London Mathematical Society, ISSN 0024-6107, Vol. 81, Nº 2, 2010, págs. 355-373
- Idioma: inglés
- DOI: 10.1112/jlms/jdp076
- Enlaces
-
Resumen
A system of linear equations in p unknowns Mx = b is said to have the removal property if every set S �º {1, . . . , n} that contains o(np.) solutions of Mx = b can be turned into a set S containing no solution of Mx = b by the removal of o(n) elements. Green (Geom. Funct.
Anal. 15 (2005) 340.376) proved that a single homogenous linear equation always has the removal property, and conjectured that every set of homogenous linear equations has the removal property. In this paper we confirm Green�fs conjecture by showing that every set of linear equations (even non-homogenous) has the removal property. We also discuss some applications of our result in theoretical computer science and, in particular, use it to resolve a conjecture of Bhattacharyya, Chen, Sudan and Xie related to algorithms for testing properties of boolean functions.
