Removal Lemma for systems of linear equations

Daniel Král

KAM

Abstract

We study algebraic analogues of the (hyper)graph Removal Lemma. In 2005, Green conjectured the following:

For every k x m integral matrix A with rank k and every eps>0, there exists delta>0 such that the following holds for every N and every subset S of {1,...N}: if the number of solutions of A x = 0 with x \in S^m is at most delta N^{m-k}, then it is possible to destroy all solutions x \in S^m of A x = 0 by removing at most eps N elements from the set S.

We prove this conjecture by establishing its analogue for not necessarily homogenous systems of equations over finite fields. The core of our proof is a reduction of the statement to the colored version of hypergraph Removal Lemma for (k+1)-uniform hypergraphs. Independently of us, Shapira obtained the same result using a reduction to the colored version of hypergraph Removal Lemma for O(m^2)-uniform hypergraphs.

Joint work with Oriol Serra and Lluis