Resumen de A proof of Green's conjecture regarding the removal properties of sets of linear equations

Asaf Shapira

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