Left Cancellation of Block Maps

An H-block is a sequence bx ...bn where bte Z2 for 1 ^ i ^ n, and an M-block map is a function from the set of n-blocks to the ring Z2 . The n-block maps form the ring GF (2)[xl5..., xn | xf = 1] (see [5, §19]). These block maps have applications to the generation of feedback shift register sequences [3]. Also each block map / generates an endomorphism fx of the shift dynamical system on the set of doubly infinite sequences on {0,1}. Then ( / og)^ — fx og^, where on the left the operation is polynomial substitution and on the right the operation is composition of endomorphisms [1]. The composition / o g is also associated with the cascade connection of two feedback shift registers whose characteristic polynomials are / and g (see [4]). For these applications, an understanding of factorization with respect to polynomial substitution is desired. For linear homogeneous block maps a factorization theory follows from the factorization theory for GF (2)[x]. The group of automorphisms of the 2-shift is too large and complicated for one to be able to contemplate a factorization theory for all block maps. However, some progress has been made on a factorization theory for block maps of the form xx +(f>(x2,..., xn), including some understanding of commutativity [1,6] . The set S£x of these block maps includes all characteristic polynomials of feedback shift registers, and the endomorphisms associated with it have many useful properties [5]. A polynomial / o g is in S£x if and only if both / and g are in «2\ (see [2, Lemma 3.10] or [6, Lemma 4.1]). Right cancellation follows from Lemma 2.10 of [1]. If h is in ^ and / o h = g o h then / = g. The problem of left cancellation is much deeper and has been a stumbling block for some time. In [6] a condition on the form of the polynomial / o g is given which ensures that fog = f oh implies that g and h differ by at most a constant. One should note that the only block maps in <£x which generate automorphisms of the shift dynamical system are the block maps xx and 1 + xx (see [2, Theorem 2.5]); and it is easy to find block maps / such that fog = f o(l+xx)og = / o ( l +g) for all block maps g. In this note I prove that if / o g = / o h is in £fx then g and h differ by at most a constant. Similar results under other conditions are also given. Finally, the maps / for which fog = f o (1 +g) are characterized. For the main results we need the concept of the principal vector of a block map [6]. The set !Fn is the set of all n-block maps. The map / e J ^ is defined by l{xx) = xx. If fe&H then Tfe^n+X is defined by T/(0B) = Tf(lB) = f(B). Also Qife&n-i and RJe&n_h 1 ^ i ^ n, are defined by QJ{B) = f(0-0B) + f(0~lB) and RJ{B) = /(0'J5). Here 0' denotes a block of zeros of length i. A block map / is said to be linear in the first r-1 variables if and