24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just to clarify: you mean a real-valued function right? $\endgroup$ – RP_ Oct 16 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 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 at 16:41
24
$\begingroup$

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, \dots, 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, \dots, 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, \dots, x_n)$ factors with respect to both $\alpha$ and $\beta$, then $f(x_1, \dots, 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).

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Does the result hold in any commutative monoid (so inverses may not exist)? $\endgroup$ – Richard Stanley Oct 16 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$ – Brendan McKay Oct 16 at 14:13
  • $\begingroup$ @RichardStanley Good question! I have to think about it. $\endgroup$ – Tony Huynh Oct 16 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 at 14:22
  • 2
    $\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$ – Brendan McKay Oct 17 at 2:32
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ +1. But why must the two graphs have a common refinement? What is the theorem (or set of theorems) behind this? $\endgroup$ – RP_ Oct 17 at 8:03

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.