22
$\begingroup$

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\}$.

$\endgroup$
  • 3
    $\begingroup$ What kind of convergence do you want for this sum? $\endgroup$ – user44191 Jan 3 at 18:37
  • $\begingroup$ @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$. $\endgroup$ – John Bentin Jan 3 at 18:56
  • 2
    $\begingroup$ @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. $\endgroup$ – user44191 Jan 3 at 22:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Nate Eldredge Jan 4 at 15:56
  • 2
    $\begingroup$ The OP's question is undecidable within ZFC. This follows from the answers of Nate Eldredge and Charles Valentin. $\endgroup$ – GH from MO Jan 5 at 16:36
14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "... and that such a representation for $exp(xy)$ implies CH". $\endgroup$ – Nik Weaver Jan 5 at 16:41
  • 3
    $\begingroup$ @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. $\endgroup$ – Charles Valentin Jan 5 at 16:50
  • $\begingroup$ Ah, you are right. $\endgroup$ – Nik Weaver Jan 5 at 16:53
  • 1
    $\begingroup$ I edited my answer and added an interesting reference. $\endgroup$ – Charles Valentin Jan 5 at 17:04
  • 1
    $\begingroup$ Counterexample in the initial question definitely should differ from $\exp(xy)=\sum x^ny^n/n! $ $\endgroup$ – Fedor Petrov Jan 5 at 20:12
12
$\begingroup$

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.)

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

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.

$\endgroup$
  • $\begingroup$ Although not meant as an answer, this is worthy of an upvote because it tackles the challenging case raised by Somos. $\endgroup$ – John Bentin Jan 4 at 9:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Nik Weaver Jan 5 at 16:51
6
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nik Weaver Jan 5 at 14:43
  • $\begingroup$ @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). $\endgroup$ – Fedor Petrov Jan 6 at 7:58
  • $\begingroup$ 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$? $\endgroup$ – Nik Weaver Jan 6 at 15:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.