Discrete 2-convex functions

We focus on a new class of integrally convex functions which we call discrete 2-convex functions. Discrete 2-convexity generalizes known classes of integrally convex functions such as the well-established M-/M\({}^\natural \)-convex and L-/L\({}^\natural \)-convex functions by Murota et al., the recently investigated globally/locally discrete midpoint convex functions by Moriguchi, Murota, Tamura, and Tardella, the directed discrete midpoint convex functions by Tamura and Tsurumi, and BS\({}^*\)-convex and UJ-convex functions by one of the authors. We provide a unifying view of all these functions within the class of integrally convex functions having discrete 2-convexity. We also introduce a new subclass of discrete 2-convex functions, called signed discrete 2-convex functions and we consider signed discrete 2-convex functions with a locally hereditary orientation property. We show that parallelogram inequalities, scalability, and proximity hold for such signed discrete 2-convex functions, which include globally/locally discrete midpoint convex functions and directed discrete midpoint convex functions. Hence, our results extend similar results recently established by Moriguchi, Murota, Tamura, and Tardella and by Tamura and Tsurumi.

1. It is mentioned in [17] that the concept of directed discrete midpoint convexity was suggested by Fabio Tardella.

2. The extension of a function f on \({\mathbb {Z}}^n\) based on the simplicial division \(\mathcal S\) is a piecewise affine function on \({\mathbb {R}}^n\) obtained by interpolating f affinely on each simplex in \(\mathcal S\).

3. For example, if \(A_k\cap S^+=\emptyset \) for some \(k\in [m]\), then \(A_{k'}\cap S^+=\emptyset \) for all \(k'\) such that \(k\le k'\le m\). Also we may have \(A_k\cap S^+=A_{k'}\cap S^+\) for some distinct \(k, k'\in [m]\).

We are grateful to the two anonymous reviewers for their useful comments which helped us to find some errors and improved the presentation of our paper. S. Fujiishige’s work was supported by the Research Institute for Mathematical Sciences, an International Joint Usage/Research Center located in Kyoto University.

Authors and Affiliations

1. Research Institute for Mathematical Sciences, Kyoto University, Kyoto, 606-8502, Japan

   Satoru Fujishige

2. Department of Information Engineering, University of Florence, 50139, Florence, Italy

   Fabio Tardella

Corresponding author

Correspondence to Satoru Fujishige.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

S. Fujishige’s work is supported by JSPS KAKENHI Grant Number JP19K11839.

Signed decomposition

For any given \(x, y\in {\mathbb {Z}}^n\) put \(z=x-y\). Suppose that we are given a sign function \(\sigma : [n]\rightarrow \{+,-\}\). According to (19) and (20) we have

and

Without loss of generality suppose that \(m\equiv \max \{|z(i)|\mid i\in [n]\}\ge 1\) and \(S\cup T=[n]\).

The way of decomposing z with respect to \(\sigma \) is determined by the disjoint subsets \(S^+\), \(S^-\), \(T^-\), and \(T^+\) of [n] as follows. Note that \(A_i\) and \(B_i\) appearing in (21)–(29) can be expressed as \(A_i=A_i^+\cup A_i^-\) and \(B_i=B_i^+\cup B_i^-\) in terms of \(A_i^+, A_i^-, B_i^+, B_i^-\) defined below.

(Case \(S^+\)): For each \(i\in [m]\) define \(A^{+}_i\subseteq S^{+}\) by

Then we have a non-increasing sequence of subsets \(A^+_i\) \((i\in [m])\) of \(S^+\) as follows.

Hence if \(A^{+}_k=\emptyset \) for some \(k\in [m]\), then \(A^{+}_\ell =\emptyset \) for all \(\ell \in [k,m]\). Note that we have

where \(z^{S^+}\) is the restriction of z on \(S^+\) and we regard \(\chi _{A_i^{+}}\) as the characteristic vector of a subset of \(S^+\). Recall that the expression of \(z^{S^+}\) as (56) with the non-increasing sequence (55) of subsets of \(S^+\) is essentially the well-known expression (or the decomposition) of vectors appearing in Edmonds’ greedy algorithm or the Lovász extension of set functions (or the Choquet integral) (see, e.g., [5]). Here the decomposition is expressed by the use of m characteristic vectors of sets \(A^+_i\) \((i\in [m])\) with possible repetitions. This makes it easy to obtain the expression of the components \(\chi _{A_i}-\chi _{B_i}\) \((i\in [m])\) of the signed decomposition (21) of \(z=x-y\) by pasting the components, one for each of \(z^{S^+}\), \(z^{S^-}\), \(z^{T^-}\), and \(z^{T^+}\), together as will be seen below.

(Case \(S^-\)): For each \(i\in [m]\) define \(A^{-}_i\subseteq S^{-}\) by

Then we have a non-decreasing sequence of subsets \(A^-_i\) \((i\in [m])\) of \(S^-\) as follows.

Hence if \(A^{-}_k=\emptyset \) for some \(k\in [m]\), then \(A^{-}_\ell =\emptyset \) for all \(\ell \in [k]\). Note that we have

where \(z^{S^-}\) is the restriction of z on \(S^-\) and we regard \(\chi _{A_i^{-}}\) as the characteristic vector of a subset of \(S^-\). It should be noted that the ways of determining the sequences \(A^+_i\) \((i\in [m])\) in (54) and \(A^-_i\) \((i\in [m])\) in (57) are the same except for the indexing: i for \(A^+_i\) corresponds to \(m-i+1\) for \(A^-_i\).

(Case \(T^-\)): For each \(i\in [m]\) define \(B^{-}_i\subseteq T^{-}\) by

Then we have a non-increasing sequence of subsets of \(T^-\) as follows.

Hence if \(B^{-}_k=\emptyset \) for some \(k\in [m]\), then \(B^-_\ell =\emptyset \) for all \(\ell \in [k,m]\). Note that we have

where \(z^{T^-}\) is the restriction of z on \(T^-\) and we regard \(\chi _{B_i^{-}}\) as the characteristic vector of a subset of \(T^-\). It should be noted that the negative of the expression (62) corresponds to the expression (56) for \(-z^{T^-}\) in (Case \(S^+\)) by interchanging the roles of \(S^+\) and \(T^-\).

(Case \(T^+\)): For each \(i\in [m]\) define \(B^{+}_i\subseteq T^{+}\) by

Then we have a non-decreasing sequence of subsets \(B^+_i\) \((i\in [m])\) of \(T^+\) as follows.

Hence if \(B^{+}_k=\emptyset \) for some \(k\in [m]\), then \(B^{+}_\ell =\emptyset \) for all \(\ell \in [k]\). Note that we have

where \(z^{T^+}\) is the restriction of z on \(T^+\) and we regard \(\chi _{B_i^{+}}\) as the characteristic vector of a subset of \(T^+\). It should be noted that the negative of the expression (65) corresponds to the expression (59) for \(-z^{T^+}\) in (Case \(S^-\)) by interchanging the roles of \(S^-\) and \(T^+\).

Now the direct sum of \(z^{S^+}\), \(z^{S^-}\), \(z^{T^-}\), and \(z^{T^+}\) gives us the expression (21) of the signed decomposition of \(z=x-y\) as follows.

where recall (21)–(29) and note that \(A_i=A^+_i\cup A^-_i\) and \(B_i=B^+_i\cup B^-_i\) (disjoint unions) for \(i\in [m]\). It should be noted that the way of indexing i plays a crucial role in pasting \(\chi _{A^+_i}\), \(\chi _{A^-_i}\), \(-\chi _{B^-_i}\), and \(-\chi _{B^+_i}\) together for each \(i\in [m]\) to obtain the signed decomposition of z with respect to the given sign function \(\sigma \), as (66).

Example: Consider \(x, y\in {\mathbb {Z}}^5\) such that \(x-y=(1,-2,1,2,-1)\) and \(\sigma =(+,+,+,-,-)\). Then we have \(m=2\) and

Hence we obtain the signed decomposition of \(z=x-y\) as

\(\square \)

Reprints and permissions