Function of $(x_1,x_2,x_3,x_4)$ that factors in two ways as $\phi_1 (x_1 ,x_2 )\phi_2(x_3 ,x_4 )=\psi_1 (x_1,x_3)\psi_2(x_2,x_4)$ 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.
 A: 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.
A: 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.
