Inapproximability results for equations over infinite groups

An equation over a group G is an expression of form w1…wk=1G, where each wi is either a variable, an inverted variable, or a group constant and 1G denotes the identity element; such an equation is satisfiable if there is a setting of the variables to values in G such that the equality is realized (Engebretsen et al. (2002) [10]).In this paper, we study the problem of simultaneously satisfying a family of equations over an infinite group G. Let EQG[k] denote the problem of determining the maximum number of simultaneously satisfiable equations in which each equation has occurrences of exactly k different variables. When G is an infinite cyclic group, we show that it is NP-hard to approximate EQ1G[3] to within 48/47−ϵ, where EQ1G[3] denotes the special case of EQG[3] in which a variable may only appear once in each equation; it is NP-hard to approximate EQ1G[2] to within 30/29−ϵ; it is NP-hard to approximate the maximum number of simultaneously satisfiable equations of degree at most d to within d−ϵ for any ϵ; for any k≥4, it is NP-hard to approximate EQG[k] within any constant factor. These results extend Håstad’s results (Håstad (2001) [17], ) and results of (Engebretsen et al. (2002) [10]), who established the inapproximability results for equations over finite Abelian groups and any finite groups respectively.