# How many convex functions are there in $[0,1]^2$?

Consider the square $[0,1]^2$. Assume that this region is divided into $N=K^2$ equispaced grid points. How many convex curves can be drawn in terms of $K$?

The points $(0,1)$ and $(1,0)$ are known to be on the convex curve. I am interested in the answer of this questions due to two reasons:

$1.$ I would like to consider $K\rightarrow \infty$ and compare the total number of convex functions to the total number of other types of functions for example (decreasing, etc.)

$2.$ Later I would like to write a program to realize all such discrete convex functions in order to perform optimization over all these functions (for a specific $K$).

I would be also happy to hear any ideas about how to realize this algorithmically.

Here is an example, where one can see examples of three different convex functions:

In this example there are altogether $N=121$ grid points and the distance between each neighboring pair of grid points both in $x$ and $y$ direction is $0.1$.

So, for every value on the $x$ axis, there will be a corresponding value on the $y$ axis.

ADDED (15.07.2018): I programmed and obtained the grid. Using this approach it is impossible to get all convex functions as $N\rightarrow \infty$. I bet we are not even near. Consider the convex function which linearly decreases from $(0,1)$ to $(0.4,0.2)$ and again linearly decreases from $(0.4,0.2)$ to $(1,0)$. It is impossible to get this function with this approach. No mater how fine the grid is, there are infinitely many other functions which are not achieved.

• Can you provide some positive and negative examples of such functions? Or even better a drawing? – Jsevillamol Jun 17 '18 at 19:28
• yes I can. Just a second please. I also forgot that $(0,1)$ and $(1,0)$ should be on the convex function. – Seyhmus Güngören Jun 17 '18 at 20:08
• The function in your diagram does not appear to be convex; the curve bends down at $(0.3, 0.5)$. – Henning Makholm Jun 19 '18 at 15:48
• (Oh, and you have $121$ grid points rather than $100$). – Henning Makholm Jun 19 '18 at 15:49
• @HenningMakholm you are right. so just a fast illustration without any care about anything. Let $(0.2,0.5)$ and $(0.3,0.4)$ be the related points. As you can see, my drawing is also horrible:) – Seyhmus Güngören Jun 19 '18 at 15:52

I am not sure that this is what you want, but here is my thinking about it:

If $n$ is the number of divisions of unity ($n=10$ in your drawing), and $x_i, i=1,2,\ldots n$ is the number of divisions traveled downwards by each segment of your curve (for the green curve $x_1,\ldots ,x_{10}$ would be $5,2,1,1,1,0,0,0,0,0$), then your problem could be formulated as the number of solutions of the following integer equation:

$x_1+x_2+\ldots+x_n=n$

subject to:

$x_1\ge x_2\ge\ldots\ge x_n\ge 0$

We can observe that each solution of this integer equation can be put in $1:1$ correspondence with a partition of $n$ (by ignoring the zeros). For the green line, this is:

$10=5+2+1+1+1$

So the number of convex functions equals $p(n)$, which is the number of partitions of $n$.

Unfortunately, $p(n)$ does not have a nice closed-form formula, but you can see the Wikipedia page Partition_(number_theory) for more details, recurrences, asymptotics, etc.

EDIT: To address OP's question about comparing $p(n)$ with the number of non-increasing functions:

If $q(n)$ is the number of non-increasing functions (not necessarily convex), then by reusing the previous notation, we get that $q(n)$ is the number of integer solutions of the following equation:

$x_1+x_2+\ldots+x_n=n$

subject to:

$x_1, x_2,\ldots, x_n\ge 0$

This is a classic Stars and bars problem (theorem two), whose solution is:

$q(n)= {n + n - 1 \choose n - 1}={2n-1\choose n-1}$

A quick check on Wolfram Alpha shows that $\frac{q(n)}{p(n)}\to\infty$, so $p(n)=o(q(n))$

• It would be nice to come up with a recursive formula to count them in exponential time. And I think it should be able to reduce it to a polynomial in time solution using dynamic programming. – Hashimoto Jul 3 '18 at 4:26
• How would you represent a curve consisting of two straight lines, going from $(0,1)$ to $(0.3,0.3)$ and then to $(1,0)$? – Peter Košinár Jul 4 '18 at 14:01
• @Hashimoto the recursive formula can be found in the Wikipedia link referenced above or Wolfram MathWorld (see (11) and (20)). However, the asymptotic formula is $p(n)\sim\frac{1}{4n\sqrt{3}}e^{\pi\sqrt{2n/3}}$, which suggests that OP's question 2 is pretty much hopeless (generating all partitions and optimization by brute force) – Momo Jul 4 '18 at 22:58
• @Peter Košinár I have only considered the lines which pass through each division of the grid, as illustrated in OP's picture. – Momo Jul 4 '18 at 23:03
• Would you mind addressing the issue of comparison between the total number of all increasing functions to the only convex ones over the same grid approach? – Seyhmus Güngören Jul 5 '18 at 21:26