A Survey on the Arity Gap

The arity gap of a function of several variables is defined as the minimum decrease in the number of essential variables when essential variables of the function are identified. We present a brief survey on the research done on the arity gap, from the first studies of this notion up to recent developments.

I. Introduction

Let and be arbitrary nonempty sets. A function of several variables from to is a map for some integer called the arity of . If , then we speak of operations on . Operations on the two-element set {0,1} are called Boolean functions.