# Showing convexity of a discrete function

1. Jun 14, 2014

### TaPaKaH

Suppose we have a function $f:\mathbb{N}\times\mathbb{N}\to\mathbb{R}_+$ that is
• increasing: $f(x+e_i)\geq f(x)$ for any $x\in\mathbb{N}^2$ and $i\in\{1,2\}$;
• convex: $f(x+2e_i)-f(x+e_i)\geq f(x+e_i)-f(x)$ for any $x\in\mathbb{N}^2$ and $i\in\{1,2\}$.
How could one show that a function $g(x):=cf(x)-\max\{c_1\left(f(x)-f(x-e_1)\right),c_2\left(f(x)-f(x-e_2)\right)\}$ for $c=\max\{c_1,c_2\}$ ($c_1,c_2\geq0$) is also convex wrt definition above?

2. Jun 14, 2014

### verty

Have you tried substituting g into that convexity inequality?

3. Jun 16, 2014

### TaPaKaH

So far I did case-by-case analysis branching on terms, at which maxima for $f(x+2e_i)$, $f(x+e_i)$ and $f(x)$ are achieved. Six of eight cases went rather smooth, but two cases are giving me problems.

Case 1:
Case 2:
I guess the proof lies in rearranging the terms in a smart way and then applying the assumptions and properties. One can also use that $f$ is also supermodular, that is $f(x+e_1+e_2)+f(x)\geq f(x+e_1)+f(x+e_2)$ for any $x\in\mathbb{N}^2$.