# Functions over monoids which factor in two different ways

This is a follow-up question to this MO question, which was asked by Richard Stanley in a comment to my answer there.

Let $$S$$ be a commutative monoid and $$f(x_1, \dots, x_n)$$ be a function from $$S^n$$ to $$S$$. Given a partition $$\alpha$$ of $$[n]$$, we say that $$f$$ factors with respect to $$\alpha$$, if for each $$A \in \alpha$$ there exists a function $$f_A$$ (which only depends on the variables $$x_i$$ for $$i \in A$$) such that $$f=\prod_{A \in \alpha} f_A$$. Given two partitions $$\alpha$$ and $$\beta$$ of $$[n]$$, $$a \wedge b$$ is the partition of $$[n]$$ whose sets are the non-empty sets of the form $$A \cap B$$ for $$A \in \alpha$$ and $$B \in \beta$$.

Question. Is it true that if $$f$$ factors with respect to both $$\alpha$$ and $$\beta$$, then $$f$$ also factors with respect to $$\alpha \wedge \beta$$?

My answer to the linked question shows that the answer is yes if $$S$$ is a group, but the proof uses the fact that inverses exist. My proof also works for non-abelian groups (as long as you are careful what factoring means), but for this question I am happy to assume that $$S$$ is commutative.

• My guess is if you take a commutative monoid where the product of any 4 nonidentity elements is 0 you might be able to avoid a complete factorization Jul 27, 2021 at 14:28
• For commutative semigroups this is easy to make fail but for monoids this seems harder. Jul 27, 2021 at 15:01
• If you take the semigroup $\langle x\mid x^4=x^5\rangle$ then $f(a,b,c,d)=abc$ has two factorizations but no complete factorization. But if you add an identity then you can get around this obstacle Jul 27, 2021 at 15:37
• Thanks for your comments! Yes, for monoids, a minimal counterexample should depend on all the variables. If $f(x_1, \dots, x_n)$ does not depend on $x_n$, then $f$ factors as $g(x_1, \dots, x_{n-1}) g(x_n)$, where $g(x_n)$ is the map that sends everything to the identity. Jul 27, 2021 at 23:29

Take $$S$$ to be the monoid on the set $$\{0,2,3,4,5,6\}$$ with operation $$x\oplus y=\min(x+y,6).$$
Let $$g:\{0,1\}^3\to S$$ be the function $$(x,y,z)\mapsto \min(x+y+z+4,6).$$ Using any surjective $$h:S\to \{0,1\}$$ this can be converted to $$f(x,y,z)=g(h(x),h(y),h(z)).$$ I'll just work with $$g.$$
$$g$$ factors with respect to $$12,3$$ and $$1,23$$: $$g(x,y,z)=(x+y+2)\oplus(z+2)=(x+2)\oplus(y+z+2).$$
But $$g$$ does not factor with respect to $$1,2,3.$$ Suppose for contradiction that $$g(x,y,z)=f_1(x)\oplus f_2(y)\oplus f_3(z)$$ for all $$x,y,z.$$ We must have $$f_i(1)=f_i(0)+1$$ for each $$i,$$ because $$g(0,0,1)=g(0,1,0)=g(1,0,0)=5$$ and $$g(0,0,0)=4.$$ This implies $$f_i(0)\geq 2.$$ But then $$f_1(0)\oplus f_2(0)\oplus f_3(0)\geq 6> g(0,0,0).$$