Green’s Conjecture and Testing Linear Invariant PropertiesAsaf Shapira 
Abstract
Given a set of linear equationsMx=b, we say that a set of integersSis (M; b)-free if
it contains no solution to this system of equations. Motivated by questions related to testing
linear-invariant Boolean functions, as well as recent investigations in additive number theory, the
following conjecture was raised (implicitly) by Green and by Bhattacharyya, Chen, Sudan and
Xie: we say that a set of integersS [n], is†-far from being (M; b)-free if one needs to remove
at least†nelements fromSin order to make it (M; b)-free. The conjecture was that for any
system of homogeneous linear equationsMx= 0 and for any† >0 there is aconstanttime
algorithm that can distinguish with high probability between sets of integers that are (M;0)-
free from sets that are†-far from being (M;0)-free. Or in other words, that for anyMthere
is an e–cient testing algorithm for the property of being (M;0)-free. In this paper we conflrm
the above conjecture by showing that such a testing algorithm exists even for non-homogeneous
linear equations. As opposed to most results on testing Boolean functions, which rely on algebraic
and analytic arguments, our proof relies on results from extremal hypergraph theory, such as the
recent removal lemmas of Gowers, R˜odl et al. and Austin and Tao.
Georgia Institute of Technology.1