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

Shapira, Asaf
April 2010
Journal of the London Mathematical Society;Apr2010, Vol. 81 Issue 2, p355
Academic Journal
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's 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.


Related Articles

  • A Genetic Algorithm Approach for Solving Fuzzy Linear and Quadratic Equations. Mashinchi, M. Hadi; Mashinchi, M. Reza; Shamsuddin, Siti Mariyam H. J. // International Journal of Applied Mathematics & Computer Sciences;2007, Vol. 3 Issue 4, p185 

    In this paper a genetic algorithms approach for solving the linear and quadratic fuzzy equations Ãx̃ = B̃ and Ãx̃² + B̃x̃ = C̃, where Ã, B̃, C̃ and x̃ are fuzzy numbers is proposed by genetic algorithms. Our genetic based method initially starts with a set...

  • Entire functions sharing one polynomial with their derivatives. Xiao-Min Li; Cun-Chen Gao // Proceedings of the Indian Academy of Sciences: Mathematical Scie;Feb2008, Vol. 118 Issue 1, p13 

    In this paper,we study the growth of solutions of a k-th order linear differential equation and that of a k+1-th order linear differential equation. From this we affirmatively answer a uniqueness question concerning a conjecture given by Brück in 1996 under the restriction of the hyper order...

  • Discussion on α-ψ Contractions on Generalized Metric Spaces. Karapınar, Erdal // Abstract & Applied Analysis;2014, p1 

    We discuss the existence and uniqueness of fixed points of α - ψ contractive mappings in complete generalized metric spaces, introduced by Branciari. Our results generalize and improve several results in the literature.

  • Design and Modeling to Generalized Linear Elements in a Vector Formatted Cartographic. González Crespo, Rubén; Lorenzo Romero, Wenceslao; Sajuan Martínez, Oscar; Montenegro-Marín, Carlos Enrique // International Journal of Advancements in Computing Technology;May2014, Vol. 6 Issue 3, p96 

    This paper shows a computer application designed to generalize linear elements in a vector formatted cartographic set by through of two methods; Douglas-Peucker simplification and Bézier curves based smoothing. Regarding codification, the simultaneous treatment of different lineal geometry...

  • Optimal and Efficient Parallel Tridiagonal Solvers Using Direct Methods. Santos, Eunice E. // Journal of Supercomputing;Nov2004, Vol. 30 Issue 2, p97 

    The problem of solving tridiagonal linear systems on parallel distributed-memory environments is considered in this paper. In particular, two common direct methods for solving such systems are considered: odd-even cyclic reduction and prefix summing. For each method, a variety of lower bounds on...

  • Technology of construction the unique solution to sensor location problem. Pilipchuk, L. A.; Vishnevetskaya, T. S. // AIP Conference Proceedings;Dec2013, Vol. 1570 Issue 1, preceding p499 

    We investigate the sparse underdetermined system of linear algebraic equations that arise in applications to the traffic in the network. We consider the technological and informational aspects of building a general and unique solution of the sparse linear systems in the Sensor Location Problem...

  • STRUCTURE-PRESERVING ALGORITHMS FOR DYNAMICAL SYSTEMS. Sun, Geng // Journal of Computational Mathematics;Nov2002, Vol. 20 Issue 6, p619 

    Presents a study which examined the structure-preserving algorithms to phase space volume for linear dynamical systems. Preservation of phase space volume for source-free dynamical systems; Description of a volume-preserving scheme for linear system with canonical form; Information on...

  • Ensemble Fuzzy Clustering for Mixed Numeric and Categorical Data. Suguna, J.; Selvi, M. Arul // International Journal of Computer Applications;Mar2012, Vol. 42, p19 

    In data mining, clustering is one of the major tasks and aims at grouping the data objects into meaningful classes (clusters) such that the similarity of objects within clusters is maximized, and the similarity of objects between clusters is minimized. The dataset sometimes may be in mixed...

  • Unknown Input High Gain Observer for Fault Detection and Isolation of Uncertain Systems. Mondal, Sharifuddin; Chakraborty, G.; Bhattacharyya, K. // Engineering Letters;2009, Vol. 17 Issue 2, p121 

    An unknown input high gain observer (UIHGO) based component fault detection and isolation (FDI) technique is presented. First, a reduced order UIHGO is derived for a linear system whose parameters are uncertain to some extent. The observer gain is determined by solving the well-known algebraic...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics