8
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Jul 27, 2021 at 14:28
  • $\begingroup$ For commutative semigroups this is easy to make fail but for monoids this seems harder. $\endgroup$ Jul 27, 2021 at 15:01
  • $\begingroup$ 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 $\endgroup$ Jul 27, 2021 at 15:37
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Jul 27, 2021 at 23:29

1 Answer 1

4
+50
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nice example! Enjoy the bounty. $\endgroup$
    – Tony Huynh
    Aug 12, 2021 at 4:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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