GAP vs. PAG

We propose a parametrized version of arity gap. The parametrized arity gap gap(f, ℓ) of a function f: Aⁿ → B measures the minimum decrease in the number of essential variables of f when ℓ consecutive identifications of pairs of essential variables are performed. We determine gap(f, ℓ) for an arbitrary function f and a positive integer ℓ. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions.

I. Introduction

Let and be arbitrary nonempty sets. We investigate a variant of the so-called arity gap of functions . The study of arity gap goes back to the 1963 paper by Salo-maa [13], where he addressed the question how the number of essential variables of a function is affected by substitution of constants for variables or by identification of variables.