22
$\begingroup$

For a continuous function $f : [0,1]^2 \to \mathbb{R}$, let us say $f$ is a sum of products (SOP) if there exist an integer $n > 0$ and continuous functions $g_1, \dots, g_n, h_1, \dots, h_n : [0,1] \to \mathbb{R}$ such that $$f(x,y) = g_1(x) h_1(y) + \dots + g_n(x) h_n(y)$$ for all $x,y \in [0,1]$.

How can I show there exists a continuous $f$ which is not an SOP?

I think this should be easy, but for some reason I don't see how to proceed.

Note that the Stone-Weierstrass theorem says that every continuous function on $[0,1]^2$ is a uniform limit of SOPs. I want to see that you can't drop the limit.

Is the same true if we replace $[0,1]$ by an arbitrary infinite compact Hausdorff space?

$\endgroup$
7
  • $\begingroup$ Why not sin(xy) $\endgroup$
    – user217285
    Jul 9, 2015 at 16:24
  • $\begingroup$ I was going to suggest $e^{xy}$, @Nitin. $\endgroup$ Jul 9, 2015 at 16:25
  • 4
    $\begingroup$ Fine, but how do I prove they are not SOPs? $\endgroup$ Jul 9, 2015 at 16:25
  • 2
    $\begingroup$ @Nitin: I don't see how that helps. The Taylor series for $f(x,y) = e^x$ also has infinitely many terms, but it is an SOP. $\endgroup$ Jul 9, 2015 at 16:27
  • 5
    $\begingroup$ The confusion might be that some people require $g_i$ and $h_i$ to be polynomials while the OP suggested just continuous functions. $\endgroup$ Jul 9, 2015 at 16:28

2 Answers 2

21
$\begingroup$

Let's call $f$ an $n$-SOP if we can write

$$f(x,y) = \sum_{k = 1}^n g_k(x)\cdot h_k(y)$$

with continuous functions $g_k, h_k \colon [0,1] \to \mathbb{R}$. If $f$ is an $n$-SOP, for every family $x_1 < x_2 < \dotsc < x_r$ of $r > n$ points in $[0,1]$, the set

$$\left\{ \begin{pmatrix} f(x_1,y) \\ f(x_2,y) \\ \vdots \\ f(x_r,y)\end{pmatrix} : y \in [0,1]\right\}$$

is contained in an $n$-dimensional linear subspace of $\mathbb{R}^r$.

But

$$\begin{pmatrix} \exp (x_1\cdot 0/r) & \exp (x_1\cdot 1/r) & \cdots & \exp (x_1 \cdot (r-1)/r) \\ \exp (x_2 \cdot 0/r) & \exp (x_2 \cdot 1/r) & \cdots & \exp (x_2 \cdot (r-1)/r) \\ \vdots & \vdots & & \vdots \\ \exp (x_r\cdot 0/r) & \exp (x_r\cdot 1/r) & \cdots & \exp (x_r \cdot (r-1)/r)\end{pmatrix}$$

is a Vandermonde matrix, hence has rank $r$. Therefore $(x,y) \mapsto e^{xy}$ is not an $n$-SOP.

$\endgroup$
1
  • 1
    $\begingroup$ That's a great answer. $\endgroup$ Jul 9, 2015 at 17:28
2
$\begingroup$

We have a writing $f(x,y) =\sum_{i=1}^n g_i(x) h_i(y)$, equivalently $$f(\cdot, y) = \sum_{i=1}^n h_i(y) g_i(\cdot)$$ means that the system of function $(f(\cdot, y))_y$ is contained in the span of n functions $g_i(\cdot)$, $i=1, \ldots, n$, equivalently, this system of functions $(f(\cdot, y))_y$ has rank at most $n$ ( remember: functions are "vectors" ).

But for a general function $f(x,y)$ ( analytic, not a polynomial) the system $(f(\cdot, y))_y$ is infinite dimensional ($e^{x y}$ (@Daniel Fischer: answer), $\frac{1}{x+y}$, $\sqrt{x+y}$, $\frac{1}{1-x y}$ $\&$ c.)

It's worth looking at $f(x,y)$ as an infinite matrix indexed by $x$, $y$. There exists such a writing if and only if the matrix has rank $\le n$, that is, if and only if every minor $$\det (f(x_i, y_j))_{i,j=1, n+1}=0$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .