[Note: This question is closed. It's current content reflects a draft of a potential new question, modified from the original by adding conditions to the premises; see comments]

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$.

[1] Can every cancellative invertible-free monoid be embedded in a group?

[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.

  • $\begingroup$ @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! $\endgroup$ Commented Dec 26, 2020 at 21:53
  • 2
    $\begingroup$ Sorry I deleted my comment about it being true for free monoid because I needed a moment to get the identity preserving fixed $\endgroup$ Commented Dec 26, 2020 at 23:27
  • $\begingroup$ @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? $\endgroup$ Commented Dec 27, 2020 at 1:16
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Dec 27, 2020 at 3:21
  • $\begingroup$ @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. $\endgroup$ Commented Dec 27, 2020 at 13:46

1 Answer 1


This is an answer for the special case of a free monoid where this is somehow a different language for standard facts about transducers and automata although I can’t write an exact reference in this language. I strongly suspect that this case is indeed special and will not generalize but this is too long for a comment so here goes.

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.

  • $\begingroup$ Looks good. Two questions occur to me: Can it be generalized? Does it appear in literature? $\endgroup$ Commented Dec 26, 2020 at 23:51
  • $\begingroup$ I don't really see how to generalize this. Do you know if your conjecture works for free commutative monoids? $\endgroup$ Commented Dec 27, 2020 at 2:04
  • $\begingroup$ Here I need the number of generators to be at least one to get injectivity of $a\mapsto f_a$. $\endgroup$ Commented Dec 27, 2020 at 3:22
  • $\begingroup$ This answer is accepted in lieu of the answer to the original question, which is in the negative for both; the current version of this question is not the original question but rather a draft of a potential future question. In answer to your question, I don't know about the commutative case. $\endgroup$ Commented Dec 27, 2020 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.