Induced arithmetic removal and arithmetic property testing

Induced arithmetic removal and arithmetic property testing

-
Jonathan Tidor, MIT
Fine Hall 224

In-Person Talk 

The triangle removal lemma of Ruzsa and Szemerédi is a fundamental application of Szemerédi's graph regularity lemma. Later generalized to the graph removal lemma and the induced graph removal lemma, these results and techniques are also a key step in Alon and Shapira's classification of testable graph properties. Analogously, one can also prove arithmetic removal lemmas from an appropriate arithmetic regularity lemma. Intriguingly, it is known that the techniques of arithmetic regularity are not capable of proving an induced arithmetic removal lemma (specifically over F_p^n for p>2). We develop a novel Ramsey-inspired technique called "patching" that allows us to overcome this difficulty and prove an induced arithmetic removal lemma. As an application of this result, we resolve a central problem in arithmetic property testing by classifying the testable linear-invariant properties. Based on joint work with Jacob Fox and Yufei Zhao.