Ir al contenido

Documat


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.


Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno