A removal lemma for systems of linear equations over finite fields

By Daniel Král', Oriol Serra, Lluís Vena. 2008

74 citations recorded by the source corpus.

We prove a removal lemma for systems of linear equations over finite fields: let X1, …, Xm be subsets of the finite field Fq and let A be a (k × m) matrix with coefficients in Fq; if the linear system Ax = b has o(qm−k) solutions with xi ∈ Xi, then we can eliminate all these solutions by deleting o(q) elements from each Xi. This extends a result of Green [Geometric and Functional Analysis 15 (2) (2005), 340–376] for a single linear equation in abelian groups to systems of linear equations. In particular, we also obtain an analogous result for systems of equations over integers, a result conjectured by Green. Our proof uses the colored version of the hypergraph Removal Lemma.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/b35ccd728f594a5710d4d99ca020c77e0f3db114

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

The growth rate of tri-colored sum-free sets (2016, background): “2See [13], building upon the combinatorial proof of Green’s result in [18].”
A relative Szemerédi theorem (2013, methodology): “Such an idea was first used by Král’, Serra, and Vena [25] with graphs (instead of hypergraphs).”
Hypergraph containers (2012, methodology): “For the proof of Theorem 1.9 we need a result for equations analogous to the supersaturation theorem for graphs: this is the removal lemma of Král’, Serra and Vena [31, 32].”