Generalizations of Świerczkowski’s lemma and the arity gap of finite functions

Świerczkowski’s lemma–as it is usually formulated–asserts that if f:An→Af:An→A is an operation on a finite set AA, n≥4n≥4, and every operation obtained from ff by identifying a pair of variables is a projection, then ff is a semiprojection. We generalize this lemma in various ways. First, it is extended to BB-valued functions on AA instead of operations on AA and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Świerczkowski’s lemma. Moreover, we explicitly classify all pseudo-Boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of BB-valued functions on arbitrary finite sets AA.