Minor complexity of discrete functions

The complexity of finite operations is still one of the fundamental tasks in the theory of computation and besides classical methods like substitution or degree arguments a bunch of combinatorial, and algebraic techniques have been introduced to tackle this extremely difficult problem.

A logic gate is a physical device that realizes a Boolean function. A logic circuit is a direct acyclic graph in which all vertices except input vertices carry the labels of gates. When realizing n-variable k-valued functions the circuit is called the $(k,n)$-circuit or Multi-Valued Logic circuit (MVL-circuit).

To move from logical circuits to MVL-circuits, researchers attempt to adapt CMOS (complementary metal oxide semiconductor), I²L (integrated injection logic) and ECL (emitter-coupled logic) technologies to implement the many-valued and fuzzy logics gates. The MVL-circuits offer more potential opportunities for the improvement of present VLSI circuit designs. For instance, MVL-circuits are well-applied in memory technology as flash memory, dynamic RAM, and in algebraic circuits [4].

In this paper we investigate a method for reduction of finite valued functions, namely by their identification minors. This method is a basic model of computing with MVL-circuits corresponding to collapsing of some inputs in the circuits. We, also study the computational complexity of this method and classify the functions in finite algebras for small values of k and n under such complexity.

Computational complexity is examined in concrete and abstract terms. The concrete analysis is based on models that capture the exchange of space for time. It is also performed via the knowledge about circuit complexity of functions. The abstract analysis is done via complexity classes, the classification of data structures, functions etc. by the time and/or space they need.

There are two key methods for reduction (computing) of the k-valued functions which are realized by assigning constants or variables to their inputs. Then the resulting objects are: subfunctions or minors, respectively. These reductions are also naturally suited to complexity measures, which illustrate “difficulty” of computing as the number of subfunctions, separable sets, and minors of the functions.

Another topic in complexity theory is to classify finite functions by their complexity such that the functions are grouped into equivalence classes with same evaluations of the corresponding complexities. Each equivalence relation in the algebra $Pkn$ of k-valued functions determines a transformation group whose orbits are the equivalence classes (see [8,10,12]. Using the lattice of Restricted Affine Groups (RAG) in [15] we have obtained upper bounds of different combinatorial parameters of several natural equivalences in $Pkn$ for small values of k and n. In the present paper we follow this line to study assigning (not necessarily unique) variable names to some of the input variables in a function f. This method of computing consists of equalizing the values of several inputs of f.

Section 2 introduces the basic definitions and notation of separable sets, subfunctions, minors, arity gap, etc. An important result, namely if a function has non-trivial arity gap then all its sets of essential variables are separable, complements this section. Section 3 examines the ordered decision diagrams (ODD), minor decomposition trees (MDTs) and minor decision diagrams (MDDs) of k-valued functions. In Section 3.3 we treat the minor complexities of functions with their classifications by the transformation groups. Section 4 is an illustration of the results in the paper applied to the simplest case of Boolean functions. In the Appendix we provide a classification of all ternary Boolean functions with respect to the minor complexity.

A discrete function f is defined as a mapping: $f:A→B$ where the domain $A=×i=1nAi$ and the range B are non-empty finite or countable sets. Let $X={x1,x2,…}$ be a countable set of variables and let $Xn={x1,x2,…,xn}$ denote the set of the first n variables in X. Let k be a natural number with $k⩾2$⁠. Let $Zk$ denote the set $Zk={0,1,…,k−1}$⁠. The operations addition “$⊕$” and product “.” modulo k constitute $Zk$ as a ring. An n-ary k-valued function (operation) on $Zk$ is a mapping $f:Zkn→Zk$ for some natural number n, called the arity of f. $Pkn$ denotes the set of all n-ary k-valued functions and $Pk=∪n=1∞Pkn$ is called the algebra of k-valued logic. It is well-known fact that there are $kkn$ functions in $Pkn$⁠. For simplicity, let us assume that throughout the paper we shall consider k-valued functions, only.

For a given variable x and $α∈Zk,xα$ is defined as follows:

The ring-sum expansion (RSE) of a function f is the sum modulo k of a constant and products of variables $xi$ or $xiα$⁠, (for $α,α∈Zk$⁠) of f. For example, $1⊕x1x22$ is a RSE of the function f in the algebra $P32$⁠, with $f(1,2)=2,f(2,2)=0$ and $f=1$⁠, otherwise. Any k instances of the same product in the RSE can be eliminated since they sum to 0. Throughout the present paper, we shall use RSE-representation of functions.

Let $f∈Pkn$ and let $var(f)={x1,…,xn}$ be the set of all variables, which occur in f. We say that the i-th variable $xi∈var(f)$ is essential in f, or f essentially depends on $xi$⁠, if there exist values $a1,…,an,b∈Zk$⁠, such that

The set of all essential variables in the function f is denoted $Ess(f)$ and $ess(f)=|Ess(f)|$⁠. The variables from $var(f)$ which are not essential in $f∈Pkn$ are called inessential or fictive.

Let $xi$ be an essential variable in f and let c be a constant from $Zk$⁠. The function $g=f(xi=c)$ obtained from $f∈Pkn$ by assigning the constant c to the variable $xi$ is called a simple subfunction of f (sometimes termed a cofactor or a restriction). When g is a simple subfunction of f we write $f≻g$⁠. The transitive closure of $≻$ is denoted $⪰¯$⁠. $Sub(f)={g|f⪰¯g}$ is the set of all subfunctions of f and $sub(f)=|Sub(f)|$⁠.

Let $f⪰¯g,c¯=(c1,…,cm)∈Zkm$ and let $M={x1,…,xm}⊂X$ with $f=gm≻gm−1≻…≻g1≻g$⁠, $g=g1(x1=c1)$⁠, and $gi=gi+1(xi+1=ci+1)$ for $i=1,…,m−1$⁠. Then we write $f⪰¯Mc¯g$ or equivalently, $g=f(x1=c1,…,xm=cm)$⁠. For brevity, sometimes we shall also use the notation $f⪰¯Mg$ or $f⪰¯g$⁠.

We say that each subfunction g of f is a reduction to f via the subfunction relationship.

The theory of separable sets (TSS) has been developed in the work of many mathematicians since the middle of the last century – K. Chimev [2], A. Salomaa [11], J. Denev, I. Gyudzhenov [7], Sl. Shtrakov [3] etc. TSS is important to avoid any redundancies when computing discrete functions and other structures as graphs [2], terms [14], etc.

Let $xi$ and $xj$ be two distinct essential variables in f. The function h is obtained from $f∈Pkn$ by identifying (collapsing) the variables $xi$ and $xj$⁠, if

for all $(a1,…,an)∈Zkn$⁠.

Briefly, when h is obtained from f, by identifying the variable $xi$ with $xj$⁠, we write $h=fi←j$ and h is called a simple identification minor of f. Clearly, $ess(fi←j)<ess(f)$⁠, because $xi∉Ess(fi←j)$⁠, but it has to be essential in f. When h is a simple identification minor of f we write $f≻h$⁠. The transitive closure of $≻$ is denoted $⪰¯$⁠. $Mnr(f)={h|f⪰¯h}$ is the set of all distinct minors of f and $mnr(f)=|Mnr(f)|$⁠. Let $h,f⪰¯h$ be an identification minor of f. The natural number $r=ess(f)−ess(h),r⩾1$ is called the order of the minor h of f.

We say that each minor h of f is a reduction to f via the minor relationship.

Let $Mnrm(f)$ denote the set $Mnrm(f)={g|g∈Mnr(f)&ess(g)=m}$ and let $mnrm(f)=|Mnrm(f)|$⁠, for all $m,m<n$⁠.

Let $f∈Pkn$ be an n-ary k-valued function. The essential arity gap (shortly arity gap or gap) of f is defined as follows

Let $2⩽p⩽m$⁠. We let $Gp,km$ denote the set of all k-valued functions which essentially depend on m variables whose arity gap is equal to p, i.e.

We say that the arity gap of f is non-trivial if $gap(f)⩾2$⁠. It is natural to expect that the functions with “huge” gap, have to be more simple for realization by MVL-circuits and functional schemas when computing by identifying variables.

An upper bound of $gap(f)$ for Boolean functions is found in K. Chimev [2] and A. Salomaa [11], showing that $gap(f)⩽2$⁠. In [18] R. Willard also proved that if a function $f:An→B$ depends on n variables and $k<n$⁠, where $k=|A|$ then $gap(f)⩽2$⁠. It is clear that $gap(f)⩽n$⁠. Thus in all cases $gap(f)⩽min(n,k)$⁠.

A complete description of Boolean functions with non-trivial arity gap is presented in [13]. In [16] these results are extended including the functions of k-valued logic, $k⩾2$⁠. In [17], a special class of functions - namely the class of symmetric k-valued functions with non-trivial arity gap, is investigated.

Definition 2.2. Two functions g and h are called equivalent (non-distinct as mappings) (written $g≡h$⁠) if g can be obtained from h by permutation of variables, introduction or deletion of inessential variables.

As mentioned earlier, there are two general ways for reduction of functions - by subfunctions or by minors. The complexities of these processes we call the subfunction or minor complexities, respectively.

An obvious difference between these concepts is the following: Each identification minor can be decomposed into subfunctions, but there are subfunctions which can not be decomposed into minors. For example, we have

for all $f,f∈Pkn$⁠, where $f≻f(xi=m,xj=m)$ and $f≻fi←j$⁠.

Let $f=x1⊕x2⊕x3$ be a Boolean function. It is easy to see that the subfunction $f(x1=1)=x2⊕x3⊕1$ can not be decomposed into any minors of f.

Roughly spoken, the complexity of functions, is a mapping (evaluation) $Val:Pkn→N$ with $Val(x)=c$ for all $x∈X$ and for some natural number $c∈N$⁠, called the initial value of the complexity, and $Val(f)⩾c$ for all $f∈Pkn$⁠.

The concept of complexity of functions is based on the “difficulties” when computing several resulting objects as subfunctions, implementations, separable sets, values, superpositions, minors, etc.

As mentioned, the computational complexities $sub(f),imp(f)$ and $sep(f)$ are used in [15] to classify the functions from the algebra $Pkn$⁠. These complexities are invariants under the action of the suitable transformation groups.

Many computations, constructions, processes, translations, mappings and so on, can be modeled as stepwise transformations of objects known as reduction systems. Abstract Reduction Systems (ARS) play an important role in various areas such as abstract data type specification, functional programming, automated deductions, etc. [9] The concepts and properties of ARS also apply to other rewrite systems such as string rewrite systems (Thue systems), tree rewrite systems, graph grammars, etc. For more detailed facts about ARS we refer to J.W. Klop and Roel de Vrijer [9]. An ARS in $Pkn$ is a structure $W=〈Pkn,{→i}i∈I,〉$⁠, where ${→i}i∈I$ is a family of binary relations on $Pkn$⁠, called reductions or rewrite relations. For a reduction $→i$ the transitive and reflexive closure is denoted $↠i$⁠. A function $g∈Pkn$ is a normal form if there is no $h∈Pkn$ such that $g→ih$⁠. In all different branches of rewriting two basic concepts occur, known as termination (guaranteeing the existence of normal forms) and confluence (securing the uniqueness of normal forms).

A reduction $→i$ has the unique normal form property (UN) if whenever $t,r∈Pkn$ are normal forms obtained by applying the reductions $→i$ on a function $f∈Pkn$ then t and r are equivalent (non-distinct as mappings).

The computations on functions proposed in the present paper can be regarded as an ARS, namely: $W=〈Pkn,{≻,≻}〉$⁠. Next, we show that $≻$ completes the reduction process with unique normal form, whereas $≻$ has not unique normal form property.

A reduction $→$ is terminating (or strongly normalizing SN) if every reduction sequence $f→f1→f2…$eventually must terminate. A reduction $→$ is weakly confluent (or has weakly Church-Rosser property WCR) if $f→r$ and $f→v$ imply that there is $w∈Pkn$ such that $r↠w$ and $v↠w$⁠.

Proof. (i) (SN) If $f≻g$ then $ess(f)>ess(g)$⁠. Since the number of essential variables $ess(fi)$ of the functions $fi$ in any reduction sequence $f≻f1≻…≻fi≻…$ strongly decrease, it follows that the sequence eventually must terminate, i.e. the reduction is terminating.

(WCR) Let f be a function and $f≻g$⁠, and $f≻h$⁠. Let t and r be normal forms such that $g⪰¯t$ and $h⪰¯r$⁠. Note that each normal form is a resulting minor obtained by collapsing all the essential variables in f. Hence, $ess(t)⩽1$ and $ess(r)⩽1$⁠. Then we have $t=f(xj,…,xj)$⁠, for some $xj∈Ess(f)$ and $r=f(xi,…,xi)$⁠, for some $xi∈Ess(f)$⁠, and hence,

Now, (i) follows from Newman’s Lemma (Theorem 1.2.1. [9]), which states that WCR & SN $⇒$ UN.

(ii) Clearly, each value of a function f with $ess(f)>0$ is an its subfunction normal form and each subfunction of f which is not a constant is not a normal form. Hence $≻$ is SN. Every non-constant functions have at least two values (normal forms), which shows that $≻$ is not WCR and UN. □

Thus, for each function $f(x1,…,xn)$ that depends on all its variables, the function $f(x,…,x)$ is the identification minor normal form of f.

An essential variable $xi$ in a function $f∈Pkn$ is called a strongly essential variable in f if there is a constant $ci$ such that $Ess(f(xi=ci))=Ess(f)\{xi}$⁠. The set of all strongly essential variables in f is denoted $SEss(f)$⁠.

The following lemma is independently proved by K. Chimev [2] and A. Salomaa [11] in different variations.

Lemma 2.5. Let $N∈Sep(f)$. If there exist m constants $c1,…,cm∈Zk$ such that $N∩Ess(gi)=Ø$ where $gi=f(xi=ci)$ for $1⩽i⩽m$ then $M∪N∈Sep(f)$ for all $M≠Ø,M⊆{x1,…,xm}$.

Proof. It suffices to look only at the set $M={x1,…,xm}$⁠. First, assume that $M∩N=Ø$ and without loss of generality let us assume $N={xm+1,…,xs},m<s⩽n$⁠. Since $N∈Sep(f)$⁠, there exists a vector of constants, say $d¯=(ds+1,…,dn)∈Zkn−s$ such that $N⊆Ess(g)$⁠, where

Let us fix an arbitrary variable from N, say the variable $xs∈N$⁠. Then there exist $s−m−1$ constants $dm+1,…,ds−1∈Zk$ such that $xs∈Ess(h)$ where

We have to prove that $M⊆Ess(h)$⁠. Let us suppose the opposite, i.e. there is a variable, say $x1∈M$ which is inessential in h. Since $x1∈{x1,…,xm}$⁠, there is a value $c1∈Zk$ such that $N∩Ess(t)=Ø$ where $t=f(x1=c1)$⁠. Our supposition shows that $h=h(x1=c1)$ and hence, $N∩Ess(h)=Ø$⁠, i.e. $xs∉Ess(h)$⁠, which is a contradiction. Consequently, $M=Ess(h)$⁠. Then $g⪰¯h$ implies $M⊆Ess(g)$ and hence, $M∪N=Ess(g)$ which establishes that $M∪N∈Sep(f)$⁠.

Second, let $M∩N≠Ø$⁠. Then we can pick $P=M\N$ and hence, $P⊆{x1,…,xm},P∩N=Ø$⁠, and $N∈Sep(f)$⁠. As shown, above $P∪N∈Sep(f)$ and $M∪N∈Sep(f)$⁠, as desired. □

Corollary 2.6. Let $xi$ and $xj$ be two distinct essential variables in f. If there is a constant $c,c∈Zk$ such that $f(xi=c)$ does not essentially depend on $xj$ then ${xi,xj}∈Sep(f)$.

Definition 2.7. Let M be an inseparable set in f. A subset $M1$ of M is called a maximal separable subset of M in f, if $M1$ is separable in f and for each $M2$⁠, $M1⊂≠M2⊆M$ it is held $M2∉Sep(f)$⁠.

The set of all maximal separable subsets of M in a function f is denoted by $Max(M,f)$⁠.

Definition 2.8. Let $M1,M1∈Max(M,f)$ be a maximal separble subset of the inseparable set M in f. The essential variable $xi$ in f is called an essential conjugate of the set $M1$ in f if for each subfunction $g,f≻m2g$⁠, where $M2=M\M1$ we have $M1∈Sep(g)$ and $xi∈Ess(g)$⁠.

Example 2.9. Let f be the following function $f=x10x21⊕x20x31x42(mod3)$⁠. It is easy to see that $M={x1,x3,x4}∉Sep(f)$ and $Max(M,f)={{x1},{x3,x4}}$⁠. Clearly, $x2$ is an essential conjugate of both ${x1}$ and ${x3,x4}$ in f.

The next theorem was proven by K. Chimev, and it is an important step to achieve a series of results concerning identification minors of functions [2,3].

Lemma 2.11. Let M be a non-empty inseparable set of essential variables in $f,L=Ess(f)\M$ and let $M1∈Max(M,f)$. Then there exists a subfunction $g,f⪰¯Lg$ such that $M1¬⊆Ess(g)$.

Proof. Without loss of generality let us assume that

Indeed, suppose this were not the case. Then $M1⊆Ess(g)$ for each $c¯,c¯∈Zkn−m−p$⁠. Since the variable $xm+1$ is essential in f, there is a vector of constants $b¯=(bm+p+1,…,bn)∈Zkn−m−p$⁠, such that $xm+1∈Ess(t)$⁠, where

Let $a¯=(am+2,…,am+p)∈Zkp−1$ be a vector of constants from $Zk$ such that $xm+1∈Ess(v)$⁠, where

Theorem 2.10 implies $M1⊆Ess(v)$⁠. Clearly, $Ess(v)⊆M1∪{xm+1}$⁠. Hence $Ess(v)=M1∪{xm+1},Ess(v)⊆Ess(f)$ and $M1⊆Ess(v)⊆M$ with $M1≠Ess(v)≠M$ which contradicts $M1∈Max(M,f)$⁠. Consequently, there is a vector $c¯∈Zks$ of constants from $Zk$ such that $M1¬⊆Ess(g)$ where $f⪰¯Lc¯g$⁠. □

The next theorem is a slight improvement of Theorem 2.10.

Proof. Without loss of generality let us assume $Ess(f)={x1,…,xn},M1={x1,…,xm}andM={x1,…,xm+p}.$

According to Lemma 2.11 there exists a vector $c¯=(cm+p+1,…,cn)∈Zkn−p$ such that $M1¬⊆Ess(g)$⁠, where $g=f(xm+p+1=cm+p+1,…,xn=cn).$

Since M₁ is separable in f there exists a vector $b¯=(bm+p+1,…,bn)∈Zkn−p$ such that $M1∈Sep(h)$⁠, where $h=f(xm+p+1=bm+p+1,…,xn=bn).$

Let $s,1⩽s⩽n−m−p$ be the minimal natural number for which $M1∈Sept(t)$⁠, where

and $M1∉Ess(u)$⁠, where $u=t(xm+p+s=cm+p+s).$ The number s must exist because $M1¬⊆Ess(g)$ and $M1∈Sep(h)$⁠.

First, let $s<n−m−p$⁠. Then $M1∈Sep(t)$ implies that there exist constants $dm+p+s,…,dn∈Zk$⁠, such that $M1∈Sep(t1)$ and $M1¬⊆Ess(t2)$ where

and

Pick

Clearly, $M1∈Sep(v)$ and $xm+p+s∈Ess(v)$⁠. If $(M\M1)∩Ess(v)=Ø$ then we are clearly done. Next, suppose with no loss of generality that

with $1⩽r⩽p$⁠. Then L must be inseparable in v and $M1∈Max(L,v)$⁠. Now, Theorem 2.10 shows that $xm+p+s$ is an essential conjugate of M₁ in v and f.

Second, let as assume $s=n−m−p$⁠. Then we can pick $z=f(xm+p+1=cm+p+1,…,xn−1=cn−1)$ with $M1∈Sep(z)$ and $M1¬⊆Ess(z(xn=cn))$⁠. The rest of the proof that $xn$ is an essential conjugate of $M1$ in z and f is left to the reader. □

The improvement of Theorem 2.10 consists in the fact that we might choose the variable $xi$ before the choice of the subfunction $g,f⪰¯M2g$⁠.

A natural question to ask is there an “universal” essential conjugate $xi∈Ess(f)\M$ for all maximal separable subsets of M, i.e. is it possible to choose the variable in Theorem 2.12 before the choice of the set $M1∈Max(M,f)?$ The next example shows that the answer is negative.

Let us turn our attention to the following:

• 1. Each simple minor obtained by collapsing pairs of variables belonging to distinct maximal separable subsets of M depends on possible maximal number of essential variables. Thus we have $ess(f2←1)=ess(f3←1)=ess(f3←2)=5$⁠. For instance, $f2←1=x1x4x50⊕x1x40x6⊕x3x5x60$⁠.

• 2. The simple minors obtained by pairs of essential conjugates essentially depend on four variables, for instance, $f5←4=x2x40x6⊕x3x5x60$⁠.

Next, we turn our attention to relationship between essential arity gap and separable sets in functions.

Proof. Let M be an arbitrary non-empty set of essential variables in f. We prove that $M∈sep(f)$ by considering cases. The theorem is given to be true if $n⩽2$⁠. Next we assume $n>2$⁠.

Case 1: $gap(f)=2,n⩾3$ and $k=2$⁠.

If $n=3$ then Theorem 3.2 [13] implies that $f=x3α(x10x21⊕x11x20)⊕x1βx2β$ or $f=x3α(x10x20⊕x11x21)⊕x3¬(α)(x10x21⊕x11x20)$⁠, where $α,β∈{0,1}$⁠. Clearly, each set of essential variables in f is separable.

If $n=4$ then according to Theorem 3.3 [13] we have $f=x40.g(x1,x2,x3)⊕x41.h(x1,x2,x3)$⁠, with $g=x3α(x10x20⊕x11x21)⊕x3¬(α)(x10x21⊕x11x20)$⁠, and $h=x3¬(α)(x10x20⊕x11x21)⊕x3α(x10x21⊕x11x20)$⁠, for some $α,α∈{0,1}$ (here $¬(α)$ means negation of $α$⁠). Clearly, each set of essential variables in f is separable.

Let $n⩾5$ From Theorem 3.4 in [13] it follows that

Thus we have $Ess(f)=Xn$⁠. Suppose, with no loss of generality that $M={x1,⋯,xm},m<n$ and

Let $c1,⋯,cn∈Zk$ and $c1⊕⋯⊕cn=1$⁠. We can pick $g=f(xm+1=cm+1,⋯,xn=cn)$ and $r=cm+1⊕⋯⊕cn$⁠. Assume without loss of generality that $r=1$⁠. Then we have

It must be shown that $M=Ess(g)$⁠. By symmetry, it is enough to show that $x1∈Ess(g)$⁠. Let $c2,⋯,cm∈Zk$ with $c2⊕⋯⊕cm=0$⁠. Then we have

which proves that $x1∈Ess(g)$⁠.

Case 2: $gap(f)=2,2<k<n$⁠.

Theorem 2.1 [18] implies that f is a symetric function which essentially depends on all of its n variables. Theorem 4.1 [17] states that: If f is a symmetric function with non-trivial arity gap, then each set of essential variables in f is separable, which completes the proof of this case.

Case 3: $gap(f)=2,n=3andk⩾3$⁠.

Lemma 5.1 [16] states that if $f∈G2,k3$ then $ess(fi←j)=1$ for all $i,j∈{1,2,3},i≠j$⁠, which shows that each subset of $X3$ is separable in f.

Case 4: $gap(f)=2,4⩽n⩽k$⁠.

If f is a symmetric function then we are done because of Theorem 4.1 [17] and if f is not a symmetric function then according to Theorem 4.2 [16] there exist $n−2$ variables $yl1,⋯,yln−2∈Xn$ such that $f=h⊕g$⁠,where $Ess(h)={yl1,⋯,yln−2}$ and $g∈Gn,kn$⁠. Moreover $gi←j=0$ for all $1⩽i,j⩽n$ with $i≠j$⁠. Now, the proof can be done as in Case 6:, for $p=2$⁠, given below.

Case 5: $gap(f)=n,3⩽n⩽k$⁠.

From Theorem 3.1 [16] it follows that f is presented in the following form:

where $Eqks={γ∈Zks|∃i,j,1⩽i<j⩽s,γi=γj}$⁠, $γ=γ1⋯γs,xγ=x1γ1x2γ2⋯xsγs$ and $Disks=Zks\Eqks$⁠, for $s,s⩾2$⁠. Moreover, there exist at least two distinct numbers among $ar∈Zk$ for $r=0,1,⋯,kn−1$⁠.

It is easy to see that $Ess(f)=Xn$⁠. We have to show that $M∈Sep(f)$⁠. Without loss of generality let us assume that $M={x1,⋯,xm},1⩽m⩽n$⁠. If $m=n$ or $m=1$ we are clearly done. Let $1<m<n$ and let $r=∑i=1nβikn−i$ be a natural number such that $ar≠0$⁠. Then we have $g=f(xm+1=βm+1,⋯,xn=βn)=a0[⊕δ∈Eqkmxδ]⊕[⊕σ∈Diskmajxσ],$

where $j=∑i=1nσikn−i$ with $σi=βi$ for $i=m+1,⋯,n$⁠, and there are at least two distinct numbers among $aj$⁠. Clearly, g essentially depends on all of its variables, i.e. $Ess(g)=M$ and hence $M∈Sep(f)$⁠.