# Can nonnegative functions $f(x,y,z)$ be written as a product of pairwise functions $u(x,y) v(y,z) w(x, z)$?

In my course on probabilistic graphical models, my professor made a claim which I find a little sus. In discussing the equivalence between Markov Random Fields and Factor Graphs, the following example was given:

An MRF over 3 variables was drawn as a triangle graph (3-cycle). This admits density function like $$\psi(x, y, z)$$. Naturally, an equivalent factor graph can be drawn by having only one factor connected to all three variables, $$p(x,y,z) \propto f(x, y, z)$$. However the example where a factor graph with three factors, one along each edge, was also considered, which admits a density like $$p(x,y,z) \propto f_1(x,y) \cdot f_2(y,z) \cdot f_3(x,z)$$.

The question was posed that all three graphical models are equivalent for the appropriate choice of factors. Formally, the claim is as follows:

For any nonnegative function $$f(x,y,z)$$, there exists nonnegative functions $$u, v, w$$ such that $$f(x,y,z)=u(x,y)\cdot v(y,z)\cdot w(x,z)$$. We can assume that $$x,y,z \in \{0,1\}$$.

My guess at a counterexample would be a function along the lines of $$f(x,y,z) = xy + yz + xz$$, but I'm stuck at finding a way to prove that this cannot be written as a product of pairwise factors.

Intuitively, for a binary alphabet, $$f(x,y,z)$$ can be encoded using 8 values, where each of $$u,v,w$$ need 4 values, leaving 8 degrees of freedom versus 12. But this intuition seems weak to me.

• Take $\log$ of every function. Then you are looking for a representation of the form $f(x,y,z)=u(x,y)+v(y,z)+w(x,z)$. This looks like a simple linear algebra problem then. Jan 31 at 16:22
• That said, $x,y,z\in \{0,1\}$ is essential because the claim is obviously false for $x,y,z\in \mathbb{R}$. Jan 31 at 16:23
• @PeterKravchuk, re, one has to be a little careful with the linear algebra, since the log-ified functions might take the value $-\infty$. Jan 31 at 16:37
• If I'm not mistaken, then your example $f(x, y, z) = x y + y z + x z$ can be achieved on $\{0, 1\}^3$ with each of $u$, $v$, and $w$ vanishing at $(0, 0)$, $v(1, 1) = 3$, $w(0, 1) = 1/3$, and $u$, $v$, and $w$ being otherwise $1$. Jan 31 at 16:54
• Not exactly what is asked but somewhat relevant: en.wikipedia.org/wiki/… Feb 1 at 5:42

Let $$f(x,y,z)=x^2+y^2+z^2$$ for $$(x,y,z) \in \mathbb{R}^3$$. The only zero of $$f$$ is $$(0,0,0)$$.

If we had three functions $$u,v,w$$ such that $$f(x,y,z)=u(x,y)v(y,z)w(z,x)$$ for every $$(x,y,z) \in \mathbb{R}^3$$, at least one of the functions $$u,v,w$$ would vanish at $$(0,0)$$, so $$f$$ would vanish on a whole line.

This argument also works on $$\{0,1\}^3$$.

• Thanks! This is a really cute counterexample! Jan 31 at 17:10

This is not true. If $$f(x,y,z)$$ has such a factorization, then

$$f(a,a,a) f(a,b,b) f(b,a,b) f(b,b,a) = f(b,b,b) f(b,a,a) f(a,b,a) f(a,a,b).$$

A generic three-input function won't obey this.

Your intuition about $$8$$ versus $$12$$ parameters is a good place to start. Indeed, if you switch from binary inputs to $$n$$-ary inputs, then you have $$n^3$$ versus $$3 n^2$$, so you have to fail once $$n^3 > 3 n^2$$, in other words $$n>3$$.

For $$n=2$$, looking at dimensions makes it seem likely such a representation exists, but the dimensionality isn't enough to resolve the issue. Switching to $$\log$$-coordinates, you have a linear map $$\mathbb{R}_{\geq 0}^{12} \to \mathbb{R}_{\geq 0}^{8}$$ and you want to know if it is surjective. When you write out the actual linear map, it turns out to be only rank $$7$$; the equation above is the equation of the image (put back in multiplicative coordinates).

• And more generally, a necessary condition is $$f(a,b,c)f(a,b',c')f(a',b,c')f(a',b',c)=f(a',b,c)f(a,b',c)f(a,b,c')f(a',b',c')$$ for every real numbers $a,b,c,a',b',c'$. Jan 31 at 18:41
• Wouldn't multiplicative coördinates give you a map $\mathbb R_{\ge 0}^{12} \to \mathbb R_{\ge 0}^8$, and log coördinates give you a map $(\mathbb R \cup \{-\infty\})^{12} \to (\mathbb R \cup \{-\infty\})^8$ (which restricts to a linear map $\mathbb R^{12} \to \mathbb R^8$)? Jan 31 at 19:08

A simple counterexample is the function $$\exp{xyz}$$. This follows from the criterion given below since the appropriate third derivative of its logarithm $$xyz$$ is $$1$$.

As noted already, you can use logarithms to reduce to the corresponding problem for sums. But if $$f$$ has such a representation, then $$\frac{\partial^3 f}{\partial x \partial y \partial z}=0.$$

Per request: the following discrete version is also a necessary condition: $$f(x_0,y_0,z_0)-f(x_1,y_0,z_0)-f(x_0,y_1,z_0)-f(x_0,y_0,z_1)+f(x_0,y_1,z_1)+f(x_1,y_0,z_1)+f(x_1,y_1,z_0)-f(x_1,y_1,z_1)=0$$ for any choices of the variables.

Both of these equations can be transformed into suitable ones for the the original problem by applying them to $$\log f$$.

In fact, a quick computation suggests that these necessary conditions are also sufficient but this should be regarded as conjectural—I haven't sat down to write out proofs.

• This argument should be discretized (replacing the derivatives with rates of variations) to work with non differentiable functions. Jan 31 at 18:39