Suppose we have a function $f(x_1 ,x_2 ,x_3 ,x_4).$ We know that we can factor it in two ways as $f(x_1 ,x_2 ,x_3 ,x_4)=\phi_1 (x_1 ,x_2 )\phi_2(x_3 ,x_4 )=\psi_1 (x_1,x_3)\psi_2(x_2,x_4)$

Show that we can completely factor the function as: $f(x_1 ,x_2 ,x_3 ,x_4)=\varphi_1(x_1)\varphi_2(x_2)\varphi_3(x_3)\varphi_4(x_4).$

I stumbled a little bit on this elementary problem as the proof is not as immediate as I think. But eventually I can prove this.

Here the overlap of partition {{1,2} {3,4}} and {{1,3},{2,4}} is {{1},{2},{3},{4}} and indeed satisfying the first two partition implies that we can factor by the overlap of both partitions.

I wonder if there is a general statement/theory of this.

  • $\begingroup$ Just to clarify: you mean a real-valued function right? $\endgroup$
    – R.P.
    Oct 16, 2020 at 9:07
  • 2
    $\begingroup$ Indeed this makes sense for any function into a set endowed with a binary law $(M,\cdot)$. It would be useful to be more precise on what's assumed on $(M,\cdot)$: the answer below seems OK if $M$ is a group, or if $M$ has an absorbing element $0$ such that $M-\{0\}$ is a group. $\endgroup$
    – YCor
    Oct 16, 2020 at 16:38
  • 1
    $\begingroup$ Also the origin set seems to be $X_1\times X_2\times X_3\times X_4$ for arbitrary sets $X_1,\dots,X_4$ without assuming the sets $X_i$ equal, if I don't miss anything. Then to read the answers it can be practical to write $\phi_{12},\phi_{34},\psi_{13},\psi_{24}$ rather than $\phi_1,\phi_2,\psi_1,\psi_2$. $\endgroup$
    – YCor
    Oct 16, 2020 at 16:41

2 Answers 2


Here is a fairly straightforward proof which also proves various generalizations of your problem. Choose $c,d$ such that $\phi_2(c,d) \neq 0$. If no such $c,d$ exist, then $f$ is identically $0$ and can be completely factored trivially. Now, $$\phi_1(x_1, x_2)=\psi_1(x_1, c)\psi_2(x_2, d) \phi_2(c,d)^{-1},$$ for all $x_1$, $x_2$. Similarly, choosing $a$, $b$ such that $\phi_1(a,b) \neq 0$, we have $$\phi_2(x_3, x_4)=\psi_1(a, x_3)\psi_2(b, x_4) \phi_1(a,b)^{-1},$$ for all $x_3$, $x_4$. Thus, $$f(x_1 ,x_2 ,x_3 ,x_4)=\phi_1(a,b)^{-1}\phi_2(c,d)^{-1}\psi_1(x_1, c)\psi_2(x_2, d) \psi_1(a, x_3)\psi_2(b, x_4), $$ for all $x_1,x_2,x_3,x_4$. $\Box$

The same proof also proves the following generalization. Given a partition $\alpha$ of $[n]$, we say that $f(x_1, \dotsc, x_n)$ 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(x_1, \dotsc, x_n)=\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$.

Lemma. Let $\alpha$ and $\beta$ be partitions of $[n]$. If $f(x_1, \dotsc, x_n)$ factors with respect to both $\alpha$ and $\beta$, then $f(x_1, \dotsc, x_n)$ factors with respect to $\alpha \wedge \beta$.

Note that I am only using the fact that the function takes values in some field or some group. I am not sure if the result still holds if inverses do not exist (this was asked by Richard Stanley in the comments below).

Update. The above lemma does not always hold for monoids, as shown by Harry West in an answer to Functions over monoids which factor in two different ways.

  • 5
    $\begingroup$ Does the result hold in any commutative monoid (so inverses may not exist)? $\endgroup$ Oct 16, 2020 at 14:03
  • 2
    $\begingroup$ In the lattice of set partitions {1}{2}{3}{4} is the meet of {1,2}{3,4} and {1,3}{2,4}. So does it generalise to an arbitrary pair of partitions and their meet? $\endgroup$ Oct 16, 2020 at 14:13
  • $\begingroup$ @RichardStanley Good question! I have to think about it. $\endgroup$
    – Tony Huynh
    Oct 16, 2020 at 14:21
  • $\begingroup$ @BrendanMcKay Yes, the proof seems to work for an arbitrary pair of partitions whose meet is $\{1\} \dots \{n\}$. $\endgroup$
    – Tony Huynh
    Oct 16, 2020 at 14:22
  • 3
    $\begingroup$ I don't think the condition that the meet is discrete is essential. The same logic says that if it factors with respect to two partitions then it factors with respect to their meet. $\endgroup$ Oct 17, 2020 at 2:32

Your problem can be recast into the language of factor graphs as follows: you have two factor graphs $G_1$, $G_2$ for the same function that are both comprised of two isolated edges, with vertex sets the partitions you indicate. These two factor graphs must have a common refinement, i.e., there must be a common factor graph $G_{12}$ and graph morphisms $g_j : G_{12} \rightarrow G_j$.

In your example, the only way that can happen is if the vertex set of $G_{12}$ is $\{1,2,3,4\}$, i.e., if $f$ factorizes completely.

  • 4
    $\begingroup$ +1. But why must the two graphs have a common refinement? What is the theorem (or set of theorems) behind this? $\endgroup$
    – R.P.
    Oct 17, 2020 at 8:03

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.