# Functions so that image of min (resp. max) is a positive definite kernel

I am trying to determine the functions $\phi : \mathbb{R}^+ \to \mathbb{R}$ such that:

Pb 1: $K(s, t) = \phi( \mathrm{min} (s,t))$ is a positive definite kernel on $\mathbb{R}^+$.

Pb 2: $K(s, t) = \phi( \mathrm{max} (s,t))$ is a positive definite kernel on $\mathbb{R}^+$.

(NB: The 2 problems are independent, I am not trying to find functions statisfying BOTH conditions)

For Pb1, since min is a p.d. kernel, I have found that all $\phi$ admitting a power series expansion on $\mathbb{R}^+$ with positive coefficients will work (e.g. polynoms with positive coeffs, exponential). By Cauchy-Schwarz inequality, I also found that $\phi$ must be increasing.

For Pb2, Cauchy-Schwarz gives that $\phi$ must be decreasing. It must also take positive values. I have found that positive constant functions work, and I wonder if they are the only ones.

Any hints?

It appears that the increasing (resp. decreasing) condition, along with $\phi$ taking positive values, is sufficient for Pb 1 (resp Pb 2).

I have found 2 proofs. The first one is quite technical and involves semi-characters of ($\mathbb{N}$, max, Id). The second one is a bit clever and I'll write it here:

Let $\phi$ such that $K(s, t) = \phi(\mathrm{min}(s, t))$ is a positive definite kernel on $\mathbb{R}_+^2$.

For all $x \in \mathbb{R}_+, \phi(x) = K(x, x) \geq 0$ so $\phi$ must take positive values.

$K$ must satisfy Cauchy-Schwarz inequality. Let $x, y \in \mathbb{R}_+$ such that $x \leq y$. We must have $K(x, y) ^2 \leq K(x, x) K(y, y)$, that is $\phi(x)^2 \leq \phi(x) \phi(y)$.

If $\phi(x) = 0$, then $\phi(y) \geq 0 = \phi(x)$.

Else, $\phi(x) > 0$ and we can divide the inequality by $\phi(x)$, which yields $\phi(x) \leq \phi(y)$. So $\phi(x) \leq \phi(y)$ in any case. So $\phi$ must be increasing.

Conversely, let $\phi$ be an increasing function taking positive values. Let $n \in \mathbb{N}^*$, let $a_1, ..., a_n \in \mathbb{R}$, let $t_1, ... , t_n \in \mathbb{R}_+$. Up to a reordering, assume $t_1 \leq ... \leq t_n$.

We want to show that $\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} a_i a_j \phi(\mathrm{min}(t_i, t_j)) \geq 0$

Here we use a trick: for any $x \geq 0, x = \int_0^{\infty} \mathbb{1}_{\{ s \leq x\}}. \mathrm{ds}$

So the desired quantity is equal to $\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n}\int_0^{\infty} a_i a_j \mathbb{1}_{\{ s \leq \phi(\mathrm{min}(t_i, t_j))\}}$

And since $\phi$ is increasing, $\mathbb{1}_{\{ s \leq \phi(\mathrm{min}(t_i, t_j))\}} = \mathbb{1}_{\{ s \leq \phi(t_i)\}} \mathbb{1}_{\{ s \leq \phi(t_j)\}}$

So our quantity is equal to $\int_0^{\infty} \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{n} a_i a_j \mathbb{1}_{\{ s \leq \phi(t_i)\}} \mathbb{1}_{\{ s \leq \phi(t_j)\}}$

which is just $\int_0^{\infty} \left( \sum\limits_{i = 1}^{n} a_i \mathbb{1}_{\{ s \leq \phi(t_i)\}} \right)^2$ and this is a positive number.