A morphic word is obtained by iterating a morphism to generate an infinite word, and then applying a coding. We characterize morphic words with polynomial growth in terms of a new type of infinite word called a @math . A zigzag word is represented by an initial string, followed by a finite list of terms, each of which repeats for each @math in one of three ways: it grows forward [ @math , backward [ @math ], or just occurs once [ @math ]. Each term can recursively contain subterms with their own forward and backward repetitions. We show that an infinite word is morphic with growth @math iff it is a zigzag word of depth @math . As corollaries, we obtain that the morphic words with growth @math are exactly the ultimately periodic words, and the morphic words with growth @math are exactly the multilinear words.
A previous characterization of morphisms with polynomial growth is due to @cite_9 , who introduce the notion of the rank'' of letters under a morphism. They show that a string @math has rank @math under a morphism @math iff @math is the minimal degree of a polynomial @math such that for every @math , @math . We make use of this result in proving the equivalence between morphic words of polynomial growth and zigzag words.
@cite_9
2313549751
The determinantal complexity of a polynomial f is defined here as the minimal size of a matrix M with affine entries such that f = det M. This function gives a minoration of the more traditional size of an arithmetical formula. Consider the polynomial “permanent” perm d of a d × d matrix with entries X i,j . A conjecture in complexity theory says that the determinantal complexity (dc) of perm d should not be polynomial in d. In this article we prove that dc(permd)≥d2 2, improving the previously known minoration, 2d. We also begin a systematic study of the function dc, and compute it for the homogeneous polynomials of degree 2.