27

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

John Bentin
  • 2,427
  • 4
    What kind of convergence do you want for this sum? – user44191 Jan 03 '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 03 '19 at 18:56
  • $f(x,y)=1$ if $x=y$ else $0$. – Somos Jan 03 '19 at 22:21
  • 2
    @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 03 '19 at 22:36
  • @Somos The demonstration was too long to post as a comment; I have posted it as an answer. – user44191 Jan 03 '19 at 23:14
  • If $f$ is locally integrable then $(f \ast m^2\psi(m.)) \psi(./m)$ is $C^\infty_c$ so it is equal to the inverse Fourier transform integral of its FT, integral that can be $\epsilon$ approximated by a Riemann sum which is in the form you want. Letting $m \to \infty$ and $\epsilon \to 0$ means adding more Riemann sums, the whole thing is in the form you want and converges to $f$ in $L^1_{loc}$ – reuns Jan 03 '19 at 23:23
  • @reuns Doesn't that only give pointwise convergence almost everywhere, rather than pointwise convergence everywhere? – user44191 Jan 04 '19 at 00:18
  • If $f$ is continuous then it converges locally uniformly. So it suffices to write your function as the pointwise and $L^1_{loc}$ limit of a sequence of continuous functions to get a sequence converging $L^1_{loc}$ as well as pointwise. – reuns Jan 04 '19 at 00:58
  • 1
    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 04 '19 at 15:56
  • $\min(x,y)=x\cdot \chi_{x< y}+y\cdot (1-\chi_{x<y})$. All summands are expressable in the desired way (characteristic function of the open set is the sum of characteristic functions of disjoint dyadic boxes contained in it). – Fedor Petrov Jan 05 '19 at 11:41
  • @FedorPetrov : How do you express $\chi_{x<y}$ in the form $f(y)$? – John Bentin Jan 05 '19 at 12:17
  • @JohnBentin $\chi_{x<y}$ is expressed as $\sum_{n=1}^\infty f_n(x)g_n(y)$ as a characteristic function of the open set. – Fedor Petrov Jan 05 '19 at 12:34
  • @FedorPetrov : Sorry to be so ignorant, but—if it's not too complicated to do within the bounds of a comment—could you write out an explicit definition of $f_n(\cdot)$ (or $g_n(\cdot)$), please? – John Bentin Jan 05 '19 at 13:10
  • @JohnBentin let's agree about lemmata: the set of representable functions 1) contains polynomials; 2) contains characteristic functions of open sets; 3) is a subalgebra of the algebra of all functions. If you ask about 2), it is not so explicit to write 'formula', but follows from the representation of any open set as a disjoint union of the products of dyadic semi-intervals $[a/2^n,(a+1)/2^n)\times [b/2^n,(b+1)/2^n)$. – Fedor Petrov Jan 05 '19 at 14:27
  • 2
    The OP's question is undecidable within ZFC. This follows from the answers of Nate Eldredge and Charles Valentin. – GH from MO Jan 05 '19 at 16:36
  • @FedorPetrov I don't see why 3) must be true, as the convergence here doesn't always allow the sums to interchange. It also doesn't seem necessary for what you are doing, because you are multiplying by something that is a function of $x$ alone. In other words, I think I would accept that it is a module over the algebra of finitely-representable functions. – user44191 Jan 05 '19 at 17:11
  • @user44191 Yes, here the weaker statement is sufficient, but actually I think that the order of summation $(a_1+a_2+\dots)(b_1+b_2+\dots)=a_1b_1+a_2b_1+a_2b_2+a_1b_2+a_3b_1+a_3b_2+a_3b_3+b_3a_1+b_3a_2+\dots$ proves that it is a subalgebra. – Fedor Petrov Jan 05 '19 at 17:28
  • @FedorPetrov I don't think that is true; I made a chat (https://chat.stackexchange.com/rooms/87883/convergence-chat). – user44191 Jan 05 '19 at 18:19

5 Answers5

24

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.

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

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

Nate Eldredge
  • 29,204
7

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.

user44191
  • 4,961
  • Although not meant as an answer, this is worthy of an upvote because it tackles the challenging case raised by Somos. – John Bentin Jan 04 '19 at 09:47
  • 1
    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 05 '19 at 16:51
6

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

Fedor Petrov
  • 102,548
  • 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 05 '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 06 '19 at 07: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 06 '19 at 15:57
3

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

Péter Komjáth
  • 7,315