×

On discrete analogues of convex functions. (Russian) Zbl 1201.41005

From the text: Let \(I_N=\{1,2,\dots,N\}\) and for an arbitrary function \(f\colon[0,1)\to[0,1)\) let \[ \Delta_1(f\colon x,y)=\frac{f(x)-f(y)}{x-y}, \quad\text{and}\quad\Delta_2(f\colon x,y,z)=\frac{\Delta_1(f\colon x,y)-\Delta_1(f\colon y,z)}{x-z}, \] \(x\neq y\), \(x\neq z\), \(y\neq z\). We define classes of convex functions satisfying a 1-Lipschitz condition and its outer discrete analogue and inner discrete analogue in the following way: \(M_2=\{f\colon[0,1)\to[0,1); |\Delta_1(f\colon x,y)|\leq 1\), \(\Delta_2(f\colon x,y,z)\geq 0\}\), \[ \hat M^N_2=\bigg\{f\colon I_N\to I_N;\;\exists g\in M_2\;\forall x\in I_N, f(x)=\bigg\lfloor Ng\bigg(\frac{x+1/2}{N}\bigg)\bigg\rfloor\bigg\}, \]
\[ M^N_2=\bigg\{g\colon I_N\to I_N;\;|g(x)-g(y)|\leq|x-y|,\;g(y)\leq\bigg\lceil\frac{y-x}{z-x}g(z)+\frac{z-y}{z-x}g(x)\bigg\rceil,\;x<y<z\bigg\}. \]
By a discrete convex function we mean a function \(h\colon I_N\to I_N\) satisfying \(h(y)\leq((z-y)h(x)+(y-x)h(z))/(z-x)\), \(x<y<z\). We prove some properties of these classes. For example, if \(N\to\infty\) then \(\log_2|V_N|\sim(2\pi\sqrt{\frac23}\log_2e)\sqrt N\), where \(|V_N|\) denotes the cardinality of the class \(V_N\) of all discrete convex functions \(f\colon I_N\to I_N\).

MSC:

41A46 Approximation by arbitrary nonlinear expressions; widths and entropy
26A51 Convexity of real functions in one variable, generalizations
PDFBibTeX XMLCite