# Is every invertible-free cancellative monoid action represented by "shifting" certain maps?

Let $$W,X$$ be cancellative invertible-free [1] monoids. A map $$e\colon W\rightarrow X$$ is a homography [2] if it is non-decreasing in the prefix order and $$e(1)=1$$. The shift of a given homography $$e$$ by an element $$w\in W$$ is $$d=e^w$$ satisfying $$e(w \,w') = e(w) \,d(w')$$. (Note this is well-defined and $$d(1)=1$$ by cancellation property, and it exists because e is prefix non-decreasing.) Then $$W$$ acts on $$D=e^W=\{e^w\colon w\in W\}$$ on the right by shift, i.e. $$d \cdot w = d^w$$ for $$d\in D$$ and $$w\in W$$ is a right action, and $$W$$ acts on the set of homographies from $$W$$ to $$X$$ by shift as well.

Is the following a theorem?

Let $$A$$ be a set, $$W$$ a cancellative invertible-free monoid, and $$\cdot\colon A \times W \rightarrow A$$ a cyclic right $$W$$-action generated by an element $$a_0\in A$$, in symbols $$A=\langle a_0\rangle=\{a_0\cdot w\colon w\in W\}$$. Then there exists a cancellative invertible-free monoid $$X$$, set $$B$$ of homographies from $$W$$ to $$X$$, and bijection $$\varphi \colon A \leftrightarrow B$$ such that

• $$B$$ is closed under shift, in symbols $$B^w \subseteq B$$ for all $$w\in W$$, and

• when $$W$$ acts on $$B$$ by shift, $$\varphi$$ is an isomorphism of $$W$$-actions ($$\varphi(a\cdot w) = \varphi(a)^w$$ for all $$a\in A$$ and $$w\in W$$).

To convert this to a conjecture in operator theory, let $$W$$, $$X$$, and $$e$$ be as above, $$R$$ a commutative ring, and $$C=R[e^W]$$ the $$R$$-module of formal linear combinations of elements of $$e^W$$ with coefficients in $$R$$. Then for all $$w\in W$$, precomposition shift by $$w$$ is an $$R$$-linear operator on $$C$$ (when elements of $$C$$ are considered to be maps $$c\colon e^W \rightarrow R$$, this is $$T_{w}\colon C\rightarrow C$$ where $$T_{w}(c)(d)=c(d^w)$$).

Is the following a theorem?

Let $$R$$ be a commutative ring, $$W$$ a cancellative invertible-free monoid, $$F$$ an $$R$$-module, and $$\cdot\colon F\times W\rightarrow F$$ a cyclic $$R$$-linear $$W$$-action linearly generated by $$f_0\in F$$, in symbols $$R\,f_0\cdot W = \{r\,f_0\cdot w\colon r\in R \wedge w\in W\} = F$$ and $$(r\,f + s\,f')\cdot w = r\,(f\cdot w) + s\,(f'\cdot w)$$ for all $$r,s\in R$$, $$f,f'\in F$$, and $$w\in W$$. Then there exists a cancellative invertible-free monoid $$X$$, set $$G$$ of homographies from $$W$$ to $$X$$, and bijective $$R$$-linear map $$U\colon F\leftrightarrow R[G]$$ such that $$U(f\cdot w) = T_w(U(f))$$ for all $$f\in F$$ and $$w\in W$$.

[2] Let a line through the origin of $$W$$ be a subset that contains the identity and is totally ordered by prefix, and let the projective space $$P(W)$$ be the set of lines through the origin of $$W$$. This differs from ordinary usage in that homography refers to a map of the argument of projective space here, whereas a it might have been defined as a map from $$P(W)$$ to $$P(X)$$ induced by an identity-preserving prefix non-decreasing bijection $$e\colon W\leftrightarrow X$$ of cancellative invertible-free monoids, following the Wikipedia article on homography. As defined here, a homography preserves lines through the origin.

• @BenjaminSteinberg Much appreciated. When you say it's true, it begs the following question, Is this entailed by some published theorem, lemma, corollary, exercise, or problem in hardcopy, with editor(s), by an incorporated publisher, etc...? (i.e. not just the internet, not just self-published, not just editor-unreviewed content, and so on?) I'll add +reference-request as a tag. Thank you and may you have a happy holidays! Dec 26, 2020 at 21:53
• Sorry I deleted my comment about it being true for free monoid because I needed a moment to get the identity preserving fixed Dec 26, 2020 at 23:27
• @BenjaminSteinberg No worries. In your answer you say "standard facts about transducers and automata". Do you have a reference in the literature or online for this specifically? Dec 27, 2020 at 1:16
• By the way this is clearly false if W is the trivial monoid since there is only one homography from the trivial monoid to any monoid Dec 27, 2020 at 3:21
• @BenjaminSteinberg Thank you so much for pointing this out. In the interest of saving time, I decided to simply do the obvious modification by adding the cyclic, resp. linearly cyclic conditions to the premises, although officially the problem is now closed, I don't want to spend the time writing up a new question right at the minute. Dec 27, 2020 at 13:46

Let $$F(X)$$ denote the free monoid on a set $$X$$. Given an action of $$F(X)$$ on the right of a set $$A$$, we can associate to each $$a\in A$$ a homography $$f_a\colon F(X)\to F(A)$$ as follows. Put $$f_a(1)=1$$ and put $$f_a(x_1\cdots x_n)$$ equal to the concatenation of the list $$a,ax_1,ax_1x_2,\cdots, ax_1x_2\cdots x_{n-1}$$ of elements of $$A$$ for $$n>0$$. Note the mapping $$a\mapsto f_a$$ is injective since $$f_a(x)=a$$ for any $$x\in X$$. Also one easily checks $$f_{aw}$$ is the shift of $$f_a$$ by $$w$$ as $$f_a(ww’)=f_a(w)f_{aw}(w’)$$ by construction.
I don’t know if something can be done for $$W$$ a free commutative monoid on more than one generator.
• Here I need the number of generators to be at least one to get injectivity of $a\mapsto f_a$. Dec 27, 2020 at 3:22