Polynomial hyperforms (Q762525)

Let V be a variety of algebras of type \(\Phi\), and let C be the set of operations obtainable by composition from the elements of \(\Phi\) and projections. C becomes a graded algebra with composition as a multi-ary operation. The author defines an n-ary clone term \(t=t(x_ 1,...,x_ n)\) as follows: the expression \(x_ i\) is an n-ary clone term for \(1\leq i\leq n\), if p is an m-ary operation symbol and \(t_ 1,...,t_ m\) are n- ary clone terms then the expression \(p(t_ 1,...,t_ m)\) is an n-ary clone term. By replacing each \(x_ i\) by the i-th projection and regarding the other operation symbols as variables, t may be thought of as a term in the first-order language of the theory of clones. An n-ary hyperform \(h=h(x_ 1,...,x_ n)\) is an n-ary clone term in which no operation symbol appears more than once. h is said to hold in a variety V if the sentence \[ \forall p\exists p_ 1,...,p_ k (p(x_ 1,...,x_ n)=h(x_ 1,...,x_ n)) \] holds in the clone of V, where \(p_ 1,...,p_ k\) are the opertion symbols appearing in h. Thus a hyperform is a sort of normal form for clone terms, bearing approximately the same relationship to ordinary normal forms that hyperidentities bear to ordinary identities. An example is the hyperform \(p_ 1(p_ 2(x_ 1,x_ 2),x_ 3)\) which holds in the theory of abelian groups, since any ternary polynomial can be formed by multiplying an appropriate polynomial in the first two variables by a power of the third variable. Of particular interest are hyperforms called compressions, designated \(c_{m,k,n}\) for \(0<m<k<n\) and defined as follows: \[ c_{m,k,n}=p_ 0(p_ 1(x_ 1,...,x_ k),p_ 2(x_ 1,...,x_ k),...,p_ m(x_ 1,...,x_ k),x_{k+1},x_{k+2},...,x_ n). \] The author now defines two hierarchies on varieties which will be linked with hyperforms in the first theorem. If V is a variety and X is a set, let \(F_ v(X)\) denote the V-free algebra generated by the elements of X. A variety V will be said to have the k-generation property if the following holds for any disjoint infinite sets X and Y: for any element b in \(F_ v(X\cup Y)\) there is a subset S of \(F_ v(X)\) of size at most k such that b is generated by \(S\cup F_ v(Y)\). The variety of abelian groups, for example, has the 1-generation property. The second hierarchy is obtained by regarding a polynomial in an algebra as a value to be computed by a machine, which inputs the variables of the polynomial and acts on them by applying operations from the clone of the algebra. The machine involved is a slightly bizarre combination of simplicity and sophistication which we call a one-pass parallel processor. It has a finite number of registers \(r_ 1,...,r_ k\) each of which can hold an element of an algebra (in particular, of \(F_ v(X))\). The machine can be programmed to perform a fixed series of steps, each of which is either an input step or an operation step. The output of the program is defined to be the content of register \(r_ 1\) after the last step of the program. Each program thus defines a polynomial in its input arguments; the program is then said to compute that polynomial in parallel space k. This paper studies these concepts.