# Is this a known question about the expression of a function on $\Bbb R^2$ as an infinite sum of products?

The question below was posted on Mathematics Stack Exchange. It received no answer, and I do not expect any direct answer to it here. However, the question seems to me a natural one. Thus I wonder whether it has been posed before and, if so, whether there is any history to it. The question is:

Is there any function $$f:\Bbb R^2\to\Bbb R$$ which has no representation in the following form?

$$f(x,y)=\sum_{n=1}^{\infty} g_n(x)h_n(y)\quad(x,y\in \Bbb R).$$As a candidate for such a function, I suggest $$f(x,y)=\min\{x,y\}$$.

• What kind of convergence do you want for this sum? – user44191 Jan 3 '19 at 18:37
• @user44191 : Pointwise convergence would be fine. There are no conditions on any of the functions $f$, $g_n$, or $h_n$ ($n=1,2,...$ ) other than that the limit of the sum is defined and the equality holds for each $x,y\in\Bbb R$. – John Bentin Jan 3 '19 at 18:56
• @Somos I'm pretty sure that has a representation. The question can be equivalently considered about functions on the Cantor set (and its square), using a bijection to the real numbers; then set $g_1 = h_1 = 1$, and cancel out each non-diagonal block one at a time (i.e. choose $g_i, h_i$ so that the product is $-1$ on that block, and $0$ elsewhere). The only elements not contained in any non-diagonal block are diagonal elements. – user44191 Jan 3 '19 at 22:36
• For future reference, when you crosspost from MSE to MO or vice versa, it is good to ensure that each post has a link to the other. Otherwise someone might spend a lot of time studying one without realizing that the other has already been answered. You already did the MO -> MSE direction, so I have just added a comment on the MSE post with a link here. – Nate Eldredge Jan 4 '19 at 15:56
• The OP's question is undecidable within ZFC. This follows from the answers of Nate Eldredge and Charles Valentin. – GH from MO Jan 5 '19 at 16:36

In "Representation of functions of two variables as sums of rectangular functions, I", Roy O. Davies shows that under the continuum hypothesis every function has a representation of this form.

More precisely, he shows that we can get a representation with the additional property that for all $$x,y$$, the sum has only finitely many non-zero terms. Conversely, he proves that if there is a representation with this additional property for $$(x,y) \mapsto e^{xy}$$, then the continuum hypothesis holds.

In his survey Set Theoretic Real Analysis(p. 18), Krzysztof Ciesielski mentions this problem (and a lot of interesting similar results), it seems that it is open whether or not the continuum hypothesis is equivalent to the existence of weak representations.

• "... and that such a representation for $exp(xy)$ implies CH". – Nik Weaver Jan 5 '19 at 16:41
• @NikWeaver Be careful, the representation that Davies talks about is stronger than the one of John Bentin: Davies requires that for all $x,y$, the sum has only finitely many non-zero terms. – Charles Valentin Jan 5 '19 at 16:50
• Ah, you are right. – Nik Weaver Jan 5 '19 at 16:53
• I edited my answer and added an interesting reference. – Charles Valentin Jan 5 '19 at 17:04
• Counterexample in the initial question definitely should differ from $\exp(xy)=\sum x^ny^n/n!$ – Fedor Petrov Jan 5 '19 at 20:12

At least, assuming sufficient large cardinals, it's consistent that there is a function without any such representation.

Note that any function of the form $$\sum_{n=1}^\infty g_n(x) h_n(y)$$ is measurable with respect to the product $$\sigma$$-algebra $$\mathcal{P}(\mathbb{R}) \otimes \mathcal{P}(\mathbb{R})$$. However, as explained in product of power sets, assuming large cardinals, it's consistent that $$\mathcal{P}(\mathbb{R}) \otimes \mathcal{P}(\mathbb{R}) \ne \mathcal{P}(\mathbb{R}^2)$$. If that's so, then if $$A \in \mathcal{P}(\mathbb{R}^2) \setminus (\mathcal{P}(\mathbb{R}) \otimes \mathcal{P}(\mathbb{R}))$$, the function $$f(x,y) = 1_A(x,y)$$ has no representation as a sum of products.

This may be huge overkill, and there could still be an easy ZFC counterexample, but at least it suggests that people can stop looking for a ZFC proof that every function has a sum-of-products representation.

Under the continuum hypothesis (or various other axioms, e.g. MA), on the other hand, we actually do have $$\mathcal{P}(\mathbb{R}) \otimes \mathcal{P}(\mathbb{R}) = \mathcal{P}(\mathbb{R}^2)$$. Together with the multiplicative system theorem (or functional monotone class theorem or similar), that would imply something close to the opposite answer: there is no nontrivial vector subspace of functions on $$\mathbb{R}^2$$ that contains all the products $$g(x) h(y)$$ and is closed under pointwise convergence. (Roughly speaking, you should allow not only pointwise limits of sums of products, but limits of limits of limits of ..., iterated up to $$\omega_1$$-many times.)

• Nice answer, but if you restrict to some narrower class (continuous? Analytic?) is the answer positive? Presumably, there should be a construction (if affirmative). – Igor Rivin Jan 4 '19 at 17:02
• @YiFan: "it is consistent" means that "it cannot be disproved within ZFC". – GH from MO Jan 5 '19 at 16:13
• Your answer and Charles Valentin's answer below show that the OP's question is undecidable within ZFC. – GH from MO Jan 5 '19 at 16:23
• @GHfromMO rigorously speaking, consistency means "it can be disproved within ZFC if and only if $0=1$ can be proved within ZFC". – Fedor Petrov Jan 5 '19 at 20:15
• @FedorPetrov: Thanks for the correction! (I usually assume that ZFC is consistent.) – GH from MO Jan 5 '19 at 21:13

This is not meant as an answer, but as a too-long-for-comment response to a comment.

I claim that $$f(x, y) = \begin{cases} 1 & x = y \\ 0 & \text{else} \end{cases}$$ can be represented in this form.

Consider the Cantor set $$\mathcal{C}$$ as the space of all (one-way infinite) bitstrings. Let $$a: \mathbb{R} \rightarrow \mathcal{C}$$ be any bijection. Let $$q_i$$ be an enumeration of finite bit-strings (e.g., $$q_0$$ is the blank string, $$q_1 = \text{"0"}$$, $$q_2 = \text{"1"}$$, $$q_3 = \text{"00"}$$, …). Then let $$g_1 = h_1 \equiv 1$$; let $$g_{2i}(x) = \begin{cases} 1 & \text{a(x) starts with q_i+\text{"0"}} \\ 0 & \text{else,} \end{cases}$$ $$h_{2i}(y) = \begin{cases} -1 & \text{a(y) starts with q_i+\text{"1"}} \\ 0 & \text{else,} \end{cases}$$ $$g_{2i+1} = h_{2i}$$, and $$h_{2i+1} = g_{2i}$$ (where the "+" denotes concatenation of strings, e.g. $$"101" + "0" = "1010"$$).

If $$x = y$$, then only $$g_1$$, $$h_1$$ affect the sum, so the sum is $$1$$. If $$x \ne y$$, then there is a unique longest bitstring that both $$a(x)$$, $$a(y)$$ start with; then either $$g_{2i} h_{2i}$$ or $$g_{2i+1} h_{2i+1}$$ will "cancel" the $$+1$$ of $$g_1 h_1$$. The other $$g_j h_j$$ will be $$0$$ at $$(x, y)$$, so the total will be $$0$$. Therefore, the sum is $$1$$ on the diagonal, and $$0$$ elsewhere.

• Although not meant as an answer, this is worthy of an upvote because it tackles the challenging case raised by Somos. – John Bentin Jan 4 '19 at 9:47
• I wouldn't say it's a challenging case --- it's easy to start with a square and subtract a sequence of smaller squares leaving just the diagonal. Then you can take care of the entire diagonal of $\mathbb{R}^2$ by interleaving a sequence of such procedures. – Nik Weaver Jan 5 '19 at 16:51

This is rather a comment to Nate Eldredge's answer, which reduces the (negative) answer to the existence of a set $$\Omega\subset \mathbb{R}^2$$ which is not a countable intersection of countable unions of products: $$\Omega\ne \cap_{n=1}^\infty \cup_{k=1}^\infty B_{n,k}\times C_{n,k}.$$

Call a set $$A\subset \mathbb{R}^2$$ kind-of-open, if it is a countable union of product sets: $$A=\cup_{n=1}^\infty B_n\times C_n,\quad B_n,C_n\subset \mathbb{R}$$ (open sets are kind-of-open). A finite intersection and a countable union of kind-of-open sets is kind-of-open. Maybe there is some standard name for such sets?

Define a finite rank function $$f\colon \mathbb{R}^2\to \mathbb{R}$$ as a finite sum $$f(x,y)=\sum_{n=1}^N g_n(x)h_n(y)$$.

Note that if $$f$$ is a finite rank function and $$U\subset \mathbb{R}$$ is open, the preimage $$f^{-1}(U)$$ is kind-of-open. Indeed, $$f^{-1}(U)=\cup (\cap_{n=1}^N g_n^{-1}(\Delta_n))\times (\cap_{n=1}^N h_n^{-1}(\delta_n))$$ where the union is taken over all tuples of rational intervals $$\Delta_1,\dots,\Delta_n,\delta_1,\dots,\delta_n$$ satisfying the inclusion $$\sum_{n=1}^N \Delta_n\cdot \delta_n\subset U$$.

Note that an infinite sum $$f=\sum_{n=1}^\infty g_n(x)h_n(y)$$ is a pointwise limit of finite rank functions $$f_n$$ (namely, partial sums).

Now let $$\Omega\subset \mathbb{R}^2$$ be any set. Assume that the characteristic function $$f$$ of $$\Omega$$ is a pointwise limit of finite rank functions $$f_n$$. Then $$W_n=f_n^{-1}(1/2,\infty)$$ is a kind-of-open set and so is $$V_n=\cup_{k\geqslant n} W_k$$, and $$V_1\supset V_2\supset V_3\dots$$. We have $$\Omega=\cap_n V_n$$. So it remains to find a set which is not a countable intersection of kind-of-open sets (kind-of-$$G_\delta$$ set).

• Since $\mathbb{R}$ contains a subset of cardinality $\aleph_1$, it would suffice to find a counterexample in $\aleph_1\times\aleph_1$. My guess is $\{(\alpha,\beta): \alpha < \beta\}$ --- it's hard to believe this is a countable intersection of countable unions of rectangles --- but I don't quite see how to prove this. – Nik Weaver Jan 5 '19 at 14:43
• @NikWeaver but if $\aleph_1=c$, Davies shows that it is. It would be nice to get a counterexample assuming negation of CH (and so proving that the statement is equivalent to CH). – Fedor Petrov Jan 6 '19 at 7:58
• Right, according to Davies the statement is true for $\aleph_1$ (and this is why it holds for $\mathbb{R}$ under CH). Maybe there is a counterexample for $\aleph_2$? – Nik Weaver Jan 6 '19 at 15:57

I think this is solved in Shelah's 675-th paper: http://shelah.logic.at/files/675.pdf