On properties of multiaffine predicates on a finite set

Abstract

We consider predicates on a finite set that are invariant with respect to an affine operation f _G , where G is some Abelian group. Such predicates are said to be multiaffine for the group G. Special attention is paid to predicates that are affine for a group G _q of addition modulo q=p ^s , where p is a prime number and s=1. We establish the predicate multiaffinity criterion for a group G _q . Then we introduce disjunctive normal forms (DNF) for predicates on a finite set and obtain properties of DNFs of predicates that are multiaffine for a group G _q . Finally we show how these properties can be used to design a polynomial algorithm that decides satisfiability of a system of predicates which are multiaffine for a group G _q , if predicates are specified by DNF.