On the complexity of finding and counting solution-free sets of integers

Given a linear equation L, a set of A integers is L-free if does not contain any ‘non-trivial’ solutions to L. This notion incorporates many central topics in combinatorial number theory such as sum-free and progression-free sets. In this paper we initiate the study of (parameterised) complexity questions involving L-free sets of integers. The main questions we consider involve deciding whether a finite set of integers A has an L-free subset of a given size, and counting all such L-free subsets. We also raise a number of open problems.