The arity gap of finite functions and generalizations of \'Swierczkowski's lemma
by
Erkko Lehtonen
University of Waterloo, Tampere University of Technology
Coauthors: Miguel Couceiro (University of Luxembourg)

The arity gap of a function f : Aⁿ → B of several variables is defined as the minimum decrease in the number of essential variables when pairs of essential variables of f are identified. The study of this notion goes back to the 1963 paper by Salomaa [4] who showed that the arity gap of any Boolean function is at most 2. This called for a classification of Boolean functions according to their arity gap, which we established in [1]. Willard [6] extended Salomaa's result to functions on arbitrary finite domains and codomains by showing that the same upper bound holds for the arity gap of any function f : Aⁿ → B with A and B finite, provided that n > |A |.

To complement these previous results, we determine the arity gap of functions f : Aⁿ → B with a small number of essential variables, i.e., when n ≤ |A |, and we obtain a classification of functions according to their arity gap in terms of so-called quasi-arity and determinability by oddsupp (see [2]). Furthermore, an explicit classification of pseudo-Boolean functions according to their arity gap is obtained.

We also discuss how our results on the arity gap can be used to generalize \'Swierczkowski's lemma [5], which essentially asserts that given an operation f : Aⁿ → A, if every operation obtained from f by identifying a pair of variables is a projection, then f is a semiprojection, i.e., f(a₁, ..., a_n) = a_t for some 1 ≤ t ≤ n whenever a_i = a_j for some 1 ≤ i < j ≤ n.

References

[1] M. Couceiro, E. Lehtonen, On the effect of variable identification on the essential arity of functions on finite sets, Int. J. Found. Comput. Sci. 18 (2007) 975-986.
[2] M. Couceiro, E. Lehtonen, Generalizations of \'Swierczkowski's lemma and the arity gap of finite functions, arXiv:0712.1753v1.
[3] M. Couceiro, M. Pouzet, On a quasi-ordering on Boolean functions, Theoret. Comput. Sci. (2008), doi:10.1016/j.tcs.2008.01.025.
[4] A. Salomaa, On essential variables of functions, especially in the algebra of logic, Ann. Acad. Sci. Fenn. Ser. A I. Math. 339 (1963) 3-11.
[5] S. \'Swierczkowski, Algebras which are independently generated by every n elements, Fund. Math. 49 (1960) 93-104.
[6] R. Willard, Essential arities of term operations in finite algebras, Discrete Math. 149 (1996) 239-259.

PDF

Paper reference: math.CO/0701332 , arXiv:0712.1753, arXiv:math.CO/0601218,

Date received: May 26, 2008