lattice polynomial

A lattice polynomial, informally, is an expression involving a finite number of variables x,y,z,, two symbols ,, and sometimes the parentheses (,) in a meaningful manner. Loosely speaking, whenever p and q are lattice polynomials, the only lattice polynomials that can be formed from p,q,, are pq and pq. We will explain formally what meaningful manner is a little later. Some examples of lattice polynomials are x(xx), (yx)x, and (xy)(yz)(zx), while x, xyyz, z)( are not lattice polynomials.

To formally define what a lattice polynomial is, we resort to model theoryMathworldPlanetmath. To begin with, we have a countable set of variables V={x,y,z,}, a set of binary function symbols F={,}. We define pairwise disjoint sets S0,S1,,Sn, recursively, as follows:

  • S0=V,

  • Sk+1={(pq),(pq)p,qSk}Sk.

Then we set S=i=0Si. An element of S is called a lattice polynomial.

Note that in the above definition, ((xy)z) is a lattice polynomial while (xyz) is not, for any variables x,y,zV. To reduce the number of parentheses in a lattice polynomial, we typically identify (pq) with pq and (pq) with pq. In additionPlanetmathPlanetmath, since the meet and join operationsMathworldPlanetmath are associative in any latticeMathworldPlanetmath, it is a common practice to further reduce the number of parentheses in a lattice polynomial by identifying both (p(qr)) and ((pq)r) with pqr, and (p(qr)) and ((pq)r) with pqr.

Another thing that can be said about the above construction of is that any given lattice polynomial can be constructed from S0 in a finite number of steps. If pSn-Sn-1, n1, then p can be constructed in exactly n steps. The minimum number of variables (in S0) that is required to construct p is called the arity of p. For example, if p=((xy)x) then the arity of p is 2. If an n-ary lattice polynomial p can be constructed from x1,,xn, we often write p=p(x1,,xn).

One more important number associated with a lattice polynomial p is its weight, defined recursively as w(p)=1 if pS0, and w(pq)=w(pq)=w(p)+w(q).

Given any n-ary lattice polynomial p and any lattice L, we can associate p with an m-ary lattice polynomial function f:LmL defined by

f(a1,,am):=p(a1,,an), where mn and aiL.

The expression p(a1,,an) is the evaluation of p at (a1,,an). That is, we substitute each xi for ai, and we interpret and in p as the join and meet operations in L.

Two lattice polynomials p,q of arities m,n, where mn, are said to be equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath if their corresponding m-ary lattice polynomial functions evaluate to the same values in any lattice. For example, xy and yx are equivalent. Similarly, x, xx, xx, and x(yx) are equivalent lattice polynomials.

Remark. Similarly, one can define a Boolean polynomial by enlarging the set F of function symbols to include the unary operator , and Sk+1={(pq),(pq),(p)p,qSk}Sk. Then a Boolean polynomial is just an element of S=i=0Si. The weight of a Boolean polynomial is similarly defined, with the additional w(p)=w(p).

Title lattice polynomial
Canonical name LatticePolynomial
Date of creation 2013-03-22 16:30:53
Last modified on 2013-03-22 16:30:53
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Definition
Classification msc 06B25
Defines lattice polynomial function
Defines equivalent lattice polynomials
Defines weight of a lattice polynomial
Defines arity of a lattice polynomial
Defines Boolean polynomial