27
$\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$
18
  • 4
    $\begingroup$ What kind of convergence do you want for this sum? $\endgroup$
    – user44191
    Jan 3, 2019 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$ Jan 3, 2019 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, 2019 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$ Jan 4, 2019 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, 2019 at 16:36

5 Answers 5

24
$\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. It is not open, cf. Santi Spadaro's comment below, or Péter Komjáth's answer.

$\endgroup$
6
  • 1
    $\begingroup$ "... and that such a representation for $exp(xy)$ implies CH". $\endgroup$
    – Nik Weaver
    Jan 5, 2019 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$ Jan 5, 2019 at 16:50
  • 1
    $\begingroup$ I edited my answer and added an interesting reference. $\endgroup$ Jan 5, 2019 at 17:04
  • 2
    $\begingroup$ Counterexample in the initial question definitely should differ from $\exp(xy)=\sum x^ny^n/n! $ $\endgroup$ Jan 5, 2019 at 20:12
  • 1
    $\begingroup$ In his paper number 675 Shelah proved that Martin’s Axiom for sigma-centered posets implies that every function has a weak representation, so this property is not equivalent to CH. Furthermore, in paper number 686 with Roslanowski he proved that the property is not equivalent to MA(sigma-centered). $\endgroup$ Mar 18, 2021 at 11:56
16
$\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$
6
  • $\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, 2019 at 17:02
  • 1
    $\begingroup$ @YiFan: "it is consistent" means that "it cannot be disproved within ZFC". $\endgroup$
    – GH from MO
    Jan 5, 2019 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, 2019 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$ Jan 5, 2019 at 20:15
  • 1
    $\begingroup$ @FedorPetrov: Thanks for the correction! (I usually assume that ZFC is consistent.) $\endgroup$
    – GH from MO
    Jan 5, 2019 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$
2
  • $\begingroup$ Although not meant as an answer, this is worthy of an upvote because it tackles the challenging case raised by Somos. $\endgroup$ Jan 4, 2019 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, 2019 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$
3
  • $\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, 2019 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$ Jan 6, 2019 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, 2019 at 15:57
3
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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