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.

Improve this question
$\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$
    – Benjamin Steinberg
    Commented Jul 27, 2021 at 14:28
  • $\begingroup$ For commutative semigroups this is easy to make fail but for monoids this seems harder. $\endgroup$
    – Benjamin Steinberg
    Commented 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$
    – Benjamin Steinberg
    Commented 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
    Commented Jul 27, 2021 at 23:29

1 Answer 1

Reset to default
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).$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .