Parametrized arity gap (Q2376914): Difference between revisions

Let \(A\) and \(B\) be sets. For functions \(f:\;A^n\to B\), \(g:\;A^m\to B\) we write \(g\leq f\) if there exists an assignment \(\alpha:\;\{1,\dots,n\}\to\{1,\dots,m\}\) such that \(g(a_1,\dots,a_m)=f(a_{\alpha(1)},\dots,a_{\alpha(n)})\) for all \(a_1,\dots,a_m\in A\). This defines a quasiorder relation on the set \({\mathcal F}_{AB}\) of all finitary functions \(A^n\to B\). Let \(\operatorname{ess}f\) denote the number of essential variables of the function \(f\in{\mathcal F}_{AB}\). The arity gap of \(f\) is the minimal difference between \(\operatorname{ess}f\) and \(\operatorname{ess}g\) with \(g<f\) (that is, \(g\leq f\) and \(f\not\leq g\)). This concept has been studied in several previous papers. In the present paper the authors introduce and investigate the parametrized arity gap, denoted gap\((f,\ell)\), as the minimal difference between \(\operatorname{ess}f\) and \(\operatorname{ess}g\), where \(f>f_1>\dots>f_{\ell-1}>g\) for some \(f_1,\dots,f_{\ell-1}\). They prove, for instance, that for all \(2\leq\ell\leq q\leq n\) there exists a function \(f\) with \(\operatorname{ess}f=n\), gap\((f,1)=1\) and gap\((f,\ell)=q\).