Characterizing the integer points in 2-decomposable polyhedra by closedness under operations

Kei Kimura, Kazuhisa Makino, Shota Yamada, and Ryo Yoshizumi

Abstract

Characterizing the solution sets in a problem by closedness under operations is recognized as one of the key aspects of algorithm development, especially in constraint satisfaction. An example from the Boolean satisfiability problem is that the solution set of a Horn conjunctive normal form (CNF) is closed under the minimum operation, and this property implies that minimizing a nonnegative linear function over a Horn CNF can be done in polynomial time. In this paper, we focus on the set of integer points (vectors) in a polyhedron, and study the relation between these sets and closedness under operations from the viewpoint of 2-decomposability. By adding further conditions to the 2-decomposable polyhedra, we show that important classes of sets of integer vectors in polyhedra are characterized by 2-decomposability and closedness under certain operations, and in some classes, by closedness under operations alone. The most prominent result we show is that the set of integer vectors in a unit-two-variable-per-inequality polyhedron can be characterized by closedness under the median and directed discrete midpoint operations, each of these operations was independently considered in constraint satisfaction and discrete convex analysis.

1 Introduction

In this paper, we study the set of integer points (vectors) in a polyhedron, where a polyhedron is defined as a set of real vectors satisfying a system of linear inequalities. Polyhedra have been intensively studied in mathematical optimization and computer science, where they arise as constraints in (integer) linear programming problems [18, 20]. Since integer feasibility for a given polyhedron, i.e., determining whether there exists an integer vector in the polyhedron, is NP-hard, a special attention has been paid to polyhedra described by a system of linear inequalities of special form. A typical example is polyhedra described by a difference constraint (DC) system (which we call DC polyhedra), where each inequality is of the form $x_{i}-x_{j}\geq c$ or $\pm x_{i}\geq c$ for some integer $c$ . Integer feasibility for DC polyhedra is known to be solvable in polynomial time by, e.g., the Bellman-Ford algorithm for the shortest path problem [1, 5]. Also, the set of integer vectors in a DC polyhedron coincides with a so called L^♮-convex set in discrete convex analysis and can be characterized by closedness under certain operations (see, e.g., [14] and Theorem 4.1 in Section 4). For more examples, see Related Work below. In this paper, we push the investigation of such a characterization further.

We focus on the set of integer vectors in a polyhedron, and study the relation between these sets and closedness under operations from the viewpoint of 2-decomposability. 2-decomposability is a concept proposed for the constraint satisfaction problem (CSP) studied in artificial intelligence and computer science, which is the computational problem of determining whether it is possible to assign values to variables while satisfying all given constraints. Intuitively, we say that the set $S$ of integer vectors is 2-decomposable if, whenever each two-dimensional projection of a vector is in the corresponding projection of $S$ , it is in $S$ . By definition, a 2-decomposable set of integer vectors can be written by constraints on two variables (although the converse does not hold in general). Therefore, problems with 2-decomposability have attracted attention as an easy-to-handle class in the CSP.

2-decomposability has attracted attention for other reasons as well. In particular, it has become clear that 2-decomposability is associated with closedness under operations, an important tool in analyzing the computational complexity of the CSP. Intuitively, a set is closed under an operation when any vector obtained by applying the operation to multiple vectors in the set is also in the set. Jeavons, Cohen, and Cooper showed that it is equivalent for all sets generated by applying certain relational operations from set $S$ to be 2-decomposable and for $S$ to be closed under a majority operation [8] (see also Theorem 2.8 in Section 2). Here, a majority operation is a ternary operation that, whenever two arguments have the same value, then that value must be returned by the operation; in all other cases any value may be returned.

While the set of integer vectors in a polyhedron with 2-decomposability does not correspond exactly to the set of integer vectors closed under a majority operation, we show that by adding further conditions important classes of sets of integer vectors in polyhedra are characterized by 2-decomposability and closedness under certain operations, and in some classes, by closedness under certain operations alone. The most prominent result we show is that the set of integer vectors in a unit-two-variable-per-inequality (UTVPI) polyhedron can be characterized by closedness under the median and directed discrete midpoint operations, each of these operations was independently considered in the CSP and discrete convex analysis. Here, a polyhedron is called UTVPI if each inequality is of the form $\pm x_{i}\pm x_{j}\geq c$ or $\pm x_{i}\geq c$ for some integer $c$ . We have also clarified the relationship with the classes treated in discrete convex analysis such as integrally convex sets.

We further characterize 2-decomposability itself. As noted above, in the known result in order to capture 2-decomposability by closedness under operations, it is necessary to assume 2-decomposability with respect to the infinite set generated by $S$ . We observe that, in fact, closedness under operations cannot directly characterize 2-decomposability. We then show that 2-decomposability can be characterized by introducing partial operations and suitable closedness under such operations.

Related work

In the CSP, the relationship between representation of the solution set and its closedness under operations is well studied, especially when the domain is finite. In the finite domain Boolean case, the problem is a generalization of Boolean satisfiability problem (SAT), and the following results are known. Let $n$ be a positive integer.

•

A subset of $\{0,1\}^{n}$ is the solution set of a CNF where each clause has at least one negated (resp., unnegated) variable if and only if it is closed under the zero (resp., one) operation.
•

A subset of $\{0,1\}^{n}$ is the solution set of a Horn (resp., dual-Horn) CNF if and only if it is closed under the minimum (resp., maximum) operation [11, 6].
•

A subset of $\{0,1\}^{n}$ is the solution set of a 2-CNF if and only if it is closed under the majority operation [17].
•

A subset of $\{0,1\}^{n}$ is the solution set of a system of linear equations over GF(2) if and only if it is closed under the affine operation [17].

Here, a conjunctive normal form (CNF) is conjunction of one or more clauses, a clause is a disjunction of literals, and a literal is an unnegated or negated variable. A solution of a CNF is a truth assignment to the variables such that every clause has at least one true literal. As is often done in the area of SAT, we identify true value with one and false value with zero. The zero (resp., one) operation is a unary operation that always returns zero (resp., one). A CNF is called Horn (resp., dual-Horn) if each clause of it has at most one unnegated (resp., negated) variable. A CNF is called a 2-CNF if each clause of it has at most two variables. The affine operation ${\rm aff}_{2}:\{0,1\}^{3}\to\{0,1\}$ is define as ${\rm aff}_{2}(x,y,z)=x-y+z\pmod{2}$ .

In the finite domain non-Boolean case, the following results are known. Let $D$ be a finite set.

•

A subset of $D^{2}$ is 0/1/all if and only if it is closed under the dual discriminator operation [7].
•

When $D$ is a totally ordered set, a subset of $D^{2}$ is the solution set of a conjunctions of $(x_{1}\geq d_{1})\vee(x_{2}\geq d_{2})$ , $(x_{1}\geq d_{1})\vee(x_{2}\leq d_{2})$ , $(x_{1}\leq d_{1})\vee(x_{2}\geq d_{2})$ , $(x_{1}\leq d_{1})\vee(x_{2}\leq d_{2})$ , and $(x_{i}\leq d_{1})\vee(x_{i}\geq d_{2})$ ( $i=1,2$ ) if and only if it is closed under the median operation [8, 4].
•

When $D$ is a totally ordered set, a subset of $D^{n}$ is the solution set of a conjunctions of the form $(x_{1}<d_{1})\vee(x_{2}<d_{2})\vee\dots\vee(x_{r}<d_{r})\vee(x_{i}>d_{i})$ if and only if it is closed under the minimum operation [9].
•

When $D=\{0,1,\dots,p-1\}$ for some prime $p$ , a subset of $D^{n}$ is the solution set of a system of linear equations over GF( $p$ ) if and only if it is closed under the affine operation [7].

Here, a subset $S$ of $D^{2}$ is called 0/1/all if, for each $d\in D$ , $|\{d^{\prime}\in D\,:\,(d,d^{\prime})\in S\}|$ equals either $0,1$ , or $|\pi_{2}(S)|$ , and symmetrically, for each $d\in D$ , $|\{d^{\prime}\in D\,:\,(d^{\prime},d)\in S\}|$ equals either $0,1$ , or $|\pi_{1}(S)|$ , where $\pi_{i}$ is a projection on the $i$ th coordinate. The dual discriminator operation $\theta$ is a ternary operation $\theta:D^{3}\to D$ such that $\theta(d_{1},d_{2},d_{3})=d_{1}$ if $d_{1}=d_{2}$ and $\theta(d_{1},d_{2},d_{3})=d_{3}$ otherwise. The median operation will be defined in Section 2. The affine operation ${\rm aff}_{p}:D^{3}\to D$ is define as ${\rm aff}_{p}(x,y,z)=x-y+z\pmod{p}$ .

In the infinite domain case, not much research has been done. It is worth noting that in the infinite case, no discussion about representation is possible without specifying how the constraints are given. The following results are known.

•

A semilinear set of ${\mathbb{Q}}^{n}$ is the solution set of semilinear Horn formula if and only if it is closed under the maximum operation [3].
•

A semilinear set of ${\mathbb{Q}}^{n}$ is the solution set of semilinear tropically convex formula if and only if it is closed under the maximum operation and $+q$ operation for all $q\in{\mathbb{Q}}$ [3].
•

A semilinear set of ${\mathbb{Q}}^{n}$ is the solution set of a conjunction of bends if and only if it is closed under the median operation [2].
•

A subset of ${\mathbb{Z}}^{n}$ is the solution set of a DC system if and only if it is closed under $g(x,y)=\lceil\frac{x+y}{2}\rceil$ and $h(x,y)=\lfloor\frac{x+y}{2}\rfloor$ [14].
•

A subset of ${\mathbb{Z}}^{n}$ is the solution set of a system of linear inequalities of the form $x_{i}-x_{j}\geq c$ if and only if it is closed under the maximum, minimum, +1, and -1 operations [14].

Here, a subset of ${\mathbb{Q}}^{n}$ is semilinear if it is a finite union of finite intersections of (open or closed) linear half spaces. A semilinear Horn formula is a finite conjunction of semilinear Horn clauses, this is, finite disjunctions of the form $\bigvee_{i=1}^{m}(a^{(i)})^{T}x\succ_{i}c_{i}$ where $a^{(1)},\dots,a^{(m)}\in{\mathbb{Q}}^{n}$ and there exists a $k\leq n$ such that $a^{(i)}_{j}\geq 0$ for all $i$ and $j\neq k$ , $\succ_{i}\in\{\geq,>\}$ , and $c_{1},\dots c_{m}\in{\mathbb{Q}}$ . A semilinear tropically convex formula is a finite conjunction of basic semilinear tropically convex formula, this is, finite disjunctions of the form $\bigvee_{i=1}^{m}(a^{(i)})^{T}x\succ_{i}c_{i}$ where $a^{(1)},\dots,a^{(m)}\in{\mathbb{Q}}^{n}$ and there exists a $k\leq n$ such that $a^{(i)}_{j}\geq 0$ for all $i$ and $j\neq k$ , $\succ_{i}\in\{\geq,>\}$ , $c_{1},\dots c_{m}\in{\mathbb{Q}}$ , and $\sum_{j}a^{(i)}_{j}=0$ for all $i$ . For each $q\in{\mathbb{Q}}$ , the $+q$ operation takes $x\in{\mathbb{Q}}$ as input and outputs $x+q$ . A bend is a formula of the form $(x\circ_{1}d_{1})\vee(a_{1}x+a_{2}y\circ c)\vee(y\circ_{2}d_{2})$ where $\circ\in\{\leq,<\}$ , $\circ_{1},\circ_{2}\in\{\leq,<,\geq,>\}$ , $a_{1},a_{2}\in{\mathbb{Q}}\setminus\{0\}$ , and $c,d_{1},d_{2}\in{\mathbb{Q}}\cup\{-\infty,+\infty\}$ are such that $\circ_{i}\in\{\leq,<\}$ if and only if $a_{i}>0$ for $i=1,2$ .

In summary, previous research has mainly been concerned with the representation of sets closed under a majority, the minimum (maximum), and the affine operations.

Outline

The rest of the paper is organized as follows. Section 2 introduces the various definitions used in the paper. In Section 3, we analyze the relationship between 2-decomposability and closure properties. In Section 4, we investigate the relationship between the sets of integer vectors in 2-decomposable polyhedra and closedness under operations. In Section 5, we characterize 2-decomposability by a certain closedness under partial operations. Finally, we conclude the paper in Section 6.

2 Preliminaries

Let $\mathbb{Z}$ and $\mathbb{R}$ denote the sets of integers and reals, respectively. We assume that $n$ is an integer greater than one throughout the paper. We also assume that $k$ is a positive integer, unless otherwise specified, throughout the paper.

We will analyze the relationship between polyhedral representations of a set of integer vectors and closedness under operations in terms of 2-decomposability.

First, we define 2-decomposability of a set $S\subseteq{\mathbb{Z}}^{n}$ . For $\{i_{1},\dots,i_{\ell}\}\subseteq\{1,\dots,n\}$ and a vector $x=(x_{1},\dots,x_{n})\in{\mathbb{Z}}^{n}$ , the projection $\pi_{i_{1},\dots,i_{\ell}}(x)$ is defined to be the $\ell$ -dimensional vector $(x_{i_{1}},\dots,x_{i_{\ell}})$ . Moreover, for a set $S\subseteq{\mathbb{Z}}^{n}$ , let $\pi_{i_{1},\dots,i_{\ell}}(S)=\{\pi_{i_{1},\dots,i_{\ell}}(x)\,:\,x\in S\}$ . For $S_{i,j}\subseteq{\mathbb{Z}}^{2}$ ( $1\leq i<j\leq n$ ), the join $\Join_{1\leq i<j\leq n}S_{i,j}\subseteq{\mathbb{Z}}^{n}$ is defined as $\Join_{1\leq i<j\leq n}S_{i,j}=\{x\in{\mathbb{Z}}^{n}\,:\,\pi_{i,j}(x)\in S_{i,j}(1\leq i<j\leq n)\}$ .

Definition 2.1 (2-decomposability [8]).

A set $S\subseteq{\mathbb{Z}}^{n}$ is said to be $2$ -decomposable if it contains all vectors $x$ such that $\pi_{i,j}(x)\in\pi_{i,j}(S)$ for all $\{i,j\}\subseteq\{1,\dots,n\}$ , or equivalently, $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ .

For any ( $k$ -ary) operation $f:\mathbb{Z}^{k}\to\mathbb{Z}$ and any $x^{(1)},\dots,x^{(k)}\in\mathbb{Z}^{n}$ , where $x^{(i)}=(x_{1}^{(i)},\dots,x_{n}^{(i)})$ , define $f(x^{(1)},\dots,x^{(k)})$ to be $(f(x_{1}^{(1)},\dots,x_{1}^{(k)}),\dots,f(x_{n}^{(1)},\dots,x_{n}^{(k)}))\in{\mathbb{Z}}^{n}$ . Namely, $f(x^{(1)},\dots,x^{(k)})$ is obtained by a componentwise application of $f$ to $x^{(1)},\dots,x^{(k)}$ . We will characterize a subset $S\subseteq\mathbb{Z}^{n}$ in terms of closedness under operations.

Definition 2.2 (Closedness under operation).

Let $S$ be a subset of $\mathbb{Z}^{n}$ and $f:\mathbb{Z}^{k}\to\mathbb{Z}$ be an operation. We say $S$ is closed under $f$ , or $f$ -closed for short, if for all $x^{(1)},\dots,x^{(k)}\in S$ ,

\displaystyle f(x^{(1)},\dots,x^{(k)})\in S.

We particularly focus on the following operations. The following one is introduced in [19].

Definition 2.3.

The directed discrete midpoint operation $\mu:\mathbb{Z}^{2}\rightarrow\mathbb{Z}$ is defined as follows. For each $x,y\in{\mathbb{Z}}$ ,

\displaystyle\mu(x,y)=\begin{cases}\lceil\frac{x+y}{2}\rceil&\text{if $x\geq y$}\\ \lfloor\frac{x+y}{2}\rfloor&\text{if $x<y$}.\end{cases}

Namely, if the average $\frac{x+y}{2}$ of $x$ and $y$ is an integer, then $\mu$ outputs the integer, and otherwise, it outputs one of the two integers obtained by rounding $\frac{x+y}{2}$ that is “close” to $x$ .

Definition 2.4.

A ternary operation $f:\mathbb{Z}^{3}\rightarrow\mathbb{Z}$ is called a majority operation, if for all $x,y\in\mathbb{Z}$ ,

\displaystyle f(x,x,y)=f(x,y,x)=f(y,x,x)=x.

Definition 2.5.

The median operation ${\rm median}:\mathbb{Z}^{3}\rightarrow\mathbb{Z}$ is defined as follows. Let $x,y,z\in\mathbb{Z}$ . Choose $u,v,w\in\mathbb{Z}$ such that $\{u,v,w\}=\{x,y,z\}$ and $u\leq v\leq w$ . Then ${\rm median}$ is defined by

\displaystyle{\rm median}(x,y,z)=v.

Namely, ${\rm median}$ outputs the median value of its three arguments.

By definition, the median operation is a majority operation.

Definition 2.6.

For a set $S\subseteq\mathbb{Z}^{n}$ and an operation $f:\mathbb{Z}^{k}\to\mathbb{Z}$ , we define the $f$ -closure ${\rm cl}_{f}(S)$ of $S$ as an intersection of all sets that include $S$ and are $f$ -closed.

We remark that ${\rm cl}_{f}(S)$ itself includes $S$ and is closed under $f$ . Hence, ${\rm cl}_{f}(S)$ is the (inclusion-wise) smallest set which includes $S$ and is closed under $f$ . Moreover, ${\rm cl}_{f}$ is indeed a closure operator, namely, it is extensive (i.e., $S\subseteq{\rm cl}_{f}(S)$ ), monotone (i.e., $S_{1}\subseteq S_{2}$ implies ${\rm cl}_{f}(S_{1})\subseteq{\rm cl}_{f}(S_{2})$ ), and idempotent (i.e., ${\rm cl}_{f}({\rm cl}_{f}(S))={\rm cl}_{f}(S)$ ).

Definition 2.7.

For a set $S\subseteq\mathbb{Z}^{n}$ , we define a convex closure ${\rm cl}_{{\rm conv}}(S)$ of $S$ as an intersection of all convex sets that include $S$ . For a set $S\subseteq\mathbb{Z}^{n}$ , we define a closed convex closure ${\rm cl}_{\overline{{\rm conv}}}(S)$ of $S$ as an intersection of all (topologically) closed convex sets that include $S$ .

It is well known that ${\rm cl}_{{\rm conv}}$ and ${\rm cl}_{\overline{{\rm conv}}}$ are closure operators.

The following theorem shown in [8] connects 2-decomposability with closedness under operations¹¹1Theorem 2.8 is originally shown for a set $S\subseteq D^{n}$ for a finite set $D$ in [8]. However, in Subsection 4.4 in the same paper, it is mentioned that the result also holds for an infinite set $D$ .. Several operations over the subsets of ${\mathbb{Z}}^{n}$ in the theorem are not defined here, since we only use the direction that (1) implies (2) in this paper.

Theorem 2.8.

For a set $S\subseteq{\mathbb{Z}}^{n}$ , the following conditions are equivalent:

(1)

$S$ is closed under a majority operation.
(2)

Every $R$ in $S^{+}$ is 2-decomposable. In particular, $S$ is 2-decomposable.

Here, $S^{+}$ is the family of all subsets that can be obtained from $S$ using some sequence of (i) Cartesian product, (ii) equality selection, and (iii) projection operation.

Now, we provide some definitions for polyhedra.

Definition 2.9 (Polyhedron).

A set $P\subseteq\mathbb{R}^{n}$ is called a polyhedron if there exist $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^{m}$ such that $P=\{x\in\mathbb{R}^{n}\,:\,Ax\geq b\}$ holds.

It is known that any polyhedron is a closed convex set.

Definition 2.10.

Let $A\in\mathbb{R}^{m\times n}$ be a matrix.

•

$A$ is said to be quadratic if each row of A contains at most two nonzero elements.
•

$A$ is said to be linear if each row of A contains at most one nonzero element.
•

$A$ is said to be unit if each element of $A$ is either $0,-1$ , or $+1$ .
•

$A$ is said to be difference if each row of A contains at most one $+1$ and at most one $-1$ .

Definition 2.11.

Let $P$ be a subset of $\mathbb{R}^{n}$ .

•

$P$ is called a TVPI (two-variable-per-inequality) polyhedron if there exist quadratic matrix $A\in\mathbb{R}^{m\times n}$ and vector $b\in\mathbb{R}^{m}$ such that $P=\{x\in\mathbb{R}^{n}\,:\,Ax\geq b\}$ holds.
•

$P$ is called a UTVPI (unit-two-variable-per-inequality) polyhedron if there exist unit quadratic matrix $A\in\{0,-1,+1\}^{m\times n}$ and vector $b\in\mathbb{R}^{m}$ such that $P=\{x\in\mathbb{R}^{n}\,:\,Ax\geq b\}$ holds.
•

$P$ is called a DC polyhedron if there exist difference matrix $A\in\{0,-1,+1\}^{m\times n}$ and vector $b\in\mathbb{R}^{m}$ such that $P=\{x\in\mathbb{R}^{n}\,:\,Ax\geq b\}$ holds.
•

$P$ is called a SVPI (single-variable-per-inequality) polyhedron if there exist linear matrix $A\in\{0,-1,+1\}^{m\times n}$ and vector $b\in\mathbb{R}^{m}$ such that $P=\{x\in\mathbb{R}^{n}\,:\,Ax\geq b\}$ holds.

Note that a SVPI polyhedron is a DC polyhedron, a DC polyhedron is a UTVPI polyhedron, and a UTVPI polyhedron is a TVPI polyhedron.

Definition 2.12 (Representability).

A set $S\subseteq\mathbb{Z}^{n}$ is said to be representable by a TVPI (resp, UTVPI, DC, SVPI) system if $S=P\cap\mathbb{Z}^{n}$ for some TVPI (resp, UTVPI, DC, SVPI) polyhedron. In this case, we say $P\cap\mathbb{Z}^{n}$ is a TVPI (resp, UTVPI, DC, SVPI) representation of $S$ .

Definition 2.13.

For a set $S\subseteq{\mathbb{Z}}^{n}$ , we define a UTVPI closure ${\rm cl}_{{\rm UTVPI}}(S)$ as an intersection of all subsets of ${\mathbb{Z}}$ that include $S$ and are representable by UTVPI systems.

We remark that ${\rm cl}_{{\rm UTVPI}}(S)$ itself includes $S$ and is representable by a UTVPI system. Hence, ${\rm cl}_{{\rm UTVPI}}(S)$ is the (inclusion-wise) smallest set which includes $S$ and is representable by a UTVPI system. Indeed, ${\rm cl}_{{\rm UTVPI}}$ is a closure operator.

Proposition 2.14 ([2, Theorem 3.2]).

Let $S$ be a subset of $\mathbb{Z}^{n}$ . If $S$ is representable by a TVPI system, then $S$ is closed under the median operation.

Remark 2.15.

Proposition 2.14 can be easily generalized to the case where $S$ is representable by an infinite set of two-variable inequalities, i.e., $S=\{x\in\mathbb{Z}^{n}\,:\,a_{i1}x_{j_{i}}+a_{i2}x_{k_{i}}\geq b_{i}(\forall i\in I)\}$ for an infinite set $I$ , where $a_{i1},a_{i2},b_{i}\in\mathbb{R}$ for each $i\in I$ .

We now introduce notions from discrete convex analysis.

Definition 2.16 (Integer neighborhood).

For vector $x\in\mathbb{R}^{n}$ , its integer neighborhood $N(x)\subseteq\mathbb{Z}^{n}$ is defined as $N(x)=\{z\in\mathbb{Z}^{n}\,:\,|z_{j}-x_{j}|<1\ (j=1,\dots,n)\}$ .

Definition 2.17 (Midpoint-neighbor-closedness).

A set $S\subseteq\mathbb{Z}^{n}$ is said to be midpoint-neighbor-closed if for each $x,y\in S$ , the integer neighborhood of $\frac{x+y}{2}$ is contained in $S$ , i.e. $N(\frac{x+y}{2})\subseteq S$ .

Definition 2.18 (Integral convexity).

A set $S\subseteq\mathbb{Z}^{n}$ is said to be integrally convex if the convex closure of $S$ coincides with the union of the convex closures of $S\cap N(x)$ over $x\in\mathbb{R}^{n}$ , i.e., if, for any $x\in\mathbb{R}^{n}$ , $x\in{\rm cl}_{{\rm conv}}(S)$ implies $x\in{\rm cl}_{{\rm conv}}(S\cap N(x))$ .

Theorem 2.19 (Theorem 2.1 in [15]).

A set $S\subseteq{\mathbb{Z}}^{n}$ is integrally convex if and only if

\displaystyle\frac{x+y}{2}\in{\rm cl}_{{\rm conv}}\left(S\cap N(\frac{x+y}{2})\right)

(1)

for every $x,y\in S$ with $||x-y||_{\infty}\geq 2$ .

Proposition 2.20 (Proposition 2.1 in [13]).

A set $S\subseteq\mathbb{Z}^{2}$ is an integrally convex set if and only if $S$ is representable by a UTVPI system.

3 2-decomposability and closure properties

In this section, we investigate the relationships between 2-decomposability and closure properties, which will be used in Section 4.

Lemma 3.1.

Let $S$ be a subset of $\mathbb{Z}^{n}$ and $f:\mathbb{Z}^{k}\to\mathbb{Z}$ be an operation.

(i)

If $S$ is $f$ -closed, then for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is $f$ -closed.
(ii)

If for each $1\leq i<j\leq n$ , $S_{i,j}\subseteq{\mathbb{Z}}^{2}$ is $f$ -closed, then $\Join_{1\leq i<j\leq n}S_{i,j}$ is $f$ -closed.

It follows that, if $S$ is $f$ -closed, then $\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ is also $f$ -closed.

Proof.

$(i)$

For any $(a^{(1)},b^{(1)}),\dots,(a^{(k)},b^{(k)})\in\pi_{i,j}(S)$ , there exists $x^{(1)},\dots,x^{(k)}\in S$ such that $\pi_{i,j}(x^{(\ell)})=(a^{(\ell)},b^{(\ell)})$ for $1\leq\ell\leq k$ . Since $S$ is $f$ -closed, $f(x^{(1)},\dots,x^{(k)})\in S$ . Thus, $f((a^{(1)},b^{(1)}),\dots,(a^{(k)},b^{(k)}))=\pi_{i,j}(f(x^{(1)},\dots,x^{(k)}))\in\pi_{i,j}(S)$ .
$(ii)$

Take any $x^{(1)},\dots,x^{(k)}\in\Join_{1\leq i<j\leq n}S_{i,j}$ . Then, for any $1\leq\ell\leq k$ and $1\leq i<j\leq n$ , $\pi_{i,j}(x^{(\ell)})\in S_{i,j}$ . Since each $S_{i,j}$ is $f$ -closed, $f(\pi_{i,j}(x^{(1)}),\dots,\pi_{i,j}(x^{(k)}))\in S_{i,j}$ . Since $\pi_{i,j}(f(x^{(1)},\dots,x^{(k)}))=f(\pi_{i,j}(x^{(1)}),\dots,\pi_{i,j}(x^{(k)}))$ for each $i$ and $j$ , we have $f(x^{(1)},\dots,x^{(k)})\in\Join_{1\leq i<j\leq n}S_{i,j}$ .

∎

Lemma 3.2.

Let $f:\mathbb{Z}^{k}\to\mathbb{Z}$ be an operation. Then the operator that takes $S\subseteq\mathbb{Z}^{n}$ as input and outputs $\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))(\subseteq\mathbb{Z}^{n})$ is a closure operator.

Proof.

To show this, we check the following three conditions.

$(i)$

Firstly, we show $S\subseteq\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))$ . For any $x\in S$ and for any $1\leq i<j\leq n$ , it is clear that $\pi_{i,j}(x)\in\pi_{i,j}(S)\subseteq{\rm cl}_{f}(\pi_{i,j}(S))$ . Thus, $x\in\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))$ .
$(ii)$

Secondly, we show that if $S_{1}\subseteq S_{2}$ then $\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S_{1}))\subseteq\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S_{2}))$ . Since $\Join_{1\leq i<j\leq n},{\rm cl}_{f},$ and $\pi_{i,j}$ are monotonically increasing in terms of set inclusion, the composition $\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(\cdot))$ is also monotonically increasing.

(iii)

Finally, we show $\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))))=\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))$ . By (ii), $\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))))\supseteq\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))$ . Thus, we show the inverse inclusion, that is

\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))))\subseteq\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S)).

It suffices to show that for each $1\leq i^{\prime}<j^{\prime}\leq n$

{\rm cl}_{f}(\pi_{i^{\prime},j^{\prime}}(\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S))))\subseteq{\rm cl}_{f}(\pi_{i^{\prime},j^{\prime}}(S)).

By minimality of ${\rm cl}_{f}$ , it suffices to show that

\pi_{i^{\prime},j^{\prime}}(\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S)))\subseteq{\rm cl}_{f}(\pi_{i^{\prime},j^{\prime}}(S)).

Now, $\pi_{i^{\prime},j^{\prime}}(\Join_{1\leq i<j\leq n}{\rm cl}_{f}(\pi_{i,j}(S)))\subseteq\pi_{i^{\prime},j^{\prime}}(\pi_{i^{\prime},j^{\prime}}^{-1}({\rm cl}_{f}(\pi_{i^{\prime},j^{\prime}}(S))))={\rm cl}_{f}(\pi_{i^{\prime},j^{\prime}}(S))$ .

∎

Theorem 3.3 (2-decomposability and general closure property).

Let $S$ be a subset of $\mathbb{Z}^{n}$ . Let $\bf{P}$ be a property for subsets of $\mathbb{Z}^{k}$ which has closure operator ${\rm cl}_{\bf P}$ (for each $k=1,2,\dots$ ). Consider the following properties.

(i)

$S$ is closed under some majority operation and closed in terms of $\bf{P}$ , i.e., $S={\rm cl}_{\bf P}(S)$ .
(ii)

$S$ is closed under some majority operation and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is closed in terms of $\bf{P}$ , i.e., $\pi_{i,j}(S)={\rm cl}_{\bf P}(\pi_{i,j}(S))$ .
(iii)

$S$ is 2-decomposable, i.e., $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ , and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is closed in terms of $\bf{P}$ , i.e., $\pi_{i,j}(S)={\rm cl}_{\bf P}(\pi_{i,j}(S))$ .
(iv)

$S=\Join_{1\leq i<j\leq n}{\rm cl}_{\bf P}(\pi_{i,j}(S))$ .

Then we have a chain of implications: (ii) $\Rightarrow$ (iii) $\Rightarrow$ (iv). Moreover, (i) is incomparable to any other properties in general.

Proof.

(ii) $\Rightarrow$ (iii) follows by Theorem 2.8. For (iii) $\Rightarrow$ (iv), since $\pi_{i,j}(S)={\rm cl}_{\bf P}(\pi_{i,j}(S))$ for each $1\leq i<j\leq n$ , we have $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)=\Join_{1\leq i<j\leq n}{\rm cl}_{\bf P}(\pi_{i,j}(S))$ . ∎

Theorem 3.4 (2-decomposability and closure property induced by operations).

Let $S$ be a subset of $\mathbb{Z}^{n}$ and $g:\mathbb{Z}^{k}\to\mathbb{Z}$ be an operation. Consider the following properties.

(i)

$S$ is closed under some majority operation and $g$ .
(ii)

$S$ is closed under some majority operation, and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is $g$ -closed.
(iii)

$S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ , and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is $g$ -closed.
(iv)

$S=\Join_{1\leq i<j\leq n}{\rm cl}_{g}(\pi_{i,j}(S))$ .

Then we have a chain of implications: (i) $\Leftrightarrow$ (ii) $\Rightarrow$ (iii) $\Leftrightarrow$ (iv).

Proof.

(i) $\Rightarrow$ (ii) directly follows by Lemma 3.1 (i). For (ii) $\Rightarrow$ (i), since $S$ is closed under some majority operation, it is 2-decomposable, i.e., $S=\Join_{1\leq i<j\leq n}(\pi_{i,j}(S))$ . Then $S$ is $g$ -closed from Lemma 3.1 (ii). (ii) $\Rightarrow$ (iii) and (iii) $\Rightarrow$ (iv) follow from Theorem 3.3.

Now, we show (iv) $\Rightarrow$ (iii). In general, we have $S\subseteq\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ and $\Join_{1\leq i<j\leq n}\pi_{i,j}(S)\subseteq\Join_{1\leq i<j\leq n}{\rm cl}_{g}(\pi_{i,j}(S))$ . Hence, $S=\Join_{1\leq i<j\leq n}{\rm cl}_{g}(\pi_{i,j}(S))$ implies $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ . From Lemma 3.1 (ii), $S$ is $g$ -closed. Then from Lemma 3.1 (i), for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is $g$ -closed. This completes the proof. ∎

Theorem 3.5 (2-decomposability and closure property induced by special operations).

Let $S$ be a subset of $\mathbb{Z}^{n}$ and $g:\mathbb{Z}^{k}\to\mathbb{Z}$ be an operation. Assume that there exists a majority operation $h$ such that for any $R\subseteq\mathbb{Z}^{2}$ if $R$ is $g$ -closed then it is $h$ -closed. Then the following are equivalent.

(i)

$S$ is closed under some majority operation and $g$ .
(ii)

$S$ is closed under some majority operation, and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is $g$ -closed.
(iii)

$S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ , and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is $g$ -closed.
(iv)

$S=\Join_{1\leq i<j\leq n}{\rm cl}_{g}(\pi_{i,j}(S))$ .

Proof.

By Theorem 3.4, it suffices to show that (iv) $\Rightarrow$ (i). Assume $S=\Join_{1\leq i<j\leq n}{\rm cl}_{g}(\pi_{i,j}(S))$ . For each $1\leq i<j\leq n$ , ${\rm cl}_{g}(\pi_{i,j}(S))$ is closed under majority operation $h$ by assumption. Hence, $S$ is $h$ -closed and $g$ -closed by Lemma 3.1, implying that (i) holds. ∎

Remark 3.6.

Contrast to Theorem 3.5, in Theorem 3.4 (iii) does not imply (ii) for general operation $g$ . For example, when $g$ is a projection, (iii) means $S$ is 2-decomposable and (ii) means $S$ is closed under some majority operation, which are not equivalent (see Section 5).

Theorem 3.7 (2-decomposability and closure property induced by ${\rm cl}_{\overline{{\rm conv}}}(\cdot)\cap\mathbb{Z}^{n}$ ).

Let $S$ be a subset of $\mathbb{Z}^{n}$ . Consider the following properties.

(i)

$S$ is closed under some majority operation and closed in terms of ${\rm cl}_{\overline{{\rm conv}}}(\cdot)\cap\mathbb{Z}^{n}$ , i.e., $S={\rm cl}_{\overline{{\rm conv}}}(S)\cap\mathbb{Z}^{n}$ .
(ii)

$S$ is closed under some majority operation, and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is closed in terms of ${\rm cl}_{\overline{{\rm conv}}}(\cdot)\cap\mathbb{Z}^{2}$ , i.e., $\pi_{i,j}(S)={\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{2}$ .
(iii)

$S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ , and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)$ is closed in terms of ${\rm cl}_{\overline{{\rm conv}}}(\cdot)\cap\mathbb{Z}^{2}$ , i.e., $\pi_{i,j}(S)={\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{2}$ .
(iv)

$S=\Join_{1\leq i<j\leq n}({\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{2})$ .

Then we have a chain of implications: (ii) $\Leftrightarrow$ (iii) $\Rightarrow$ (iv) $\Rightarrow$ (i).

Proof.

By Theorem 3.3, it suffices to show that (iii) $\Rightarrow$ (ii) and (iv) $\Rightarrow$ (i).

For (iii) $\Rightarrow$ (ii), assume that $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ , and for each $1\leq i<j\leq n$ , $\pi_{i,j}(S)={\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{2}$ . Then, each $\pi_{i,j}(S)$ is represented as a TVPI system with possibly infinitely many inequalities, and thus it is closed under the median operation (see Remark 2.15). It follows from Lemma 3.1 (ii) that $S$ is closed the median operation. Hence (ii) holds.

We then show that (iv) $\Rightarrow$ (i). (iv) means that $S$ is represented as a TVPI system with possibly infinitely many inequalities. Hence, $S$ is closed under the median operation (see Remark 2.15). Moreover, since $S$ is the set of integer vectors in an intersection of closed convex sets, we have $S={\rm cl}_{\overline{{\rm conv}}}(S)\cap\mathbb{Z}^{n}$ . ∎

Proposition 3.8 (Hierarchy of closedness in 2-dimension).

For a subset $S\subseteq\mathbb{Z}^{2}$ , consider the following properties.

(i)

$S$ is midpoint-neighbor-closed.
(ii)

$S$ is closed under $g(x,y)=\lceil\frac{x+y}{2}\rceil$ and $h(x,y)=\lfloor\frac{x+y}{2}\rfloor$
(iii)

$S$ is $\mu$ -closed.
(iii)’

$S$ is integrally convex.
(iv)

$S={\rm cl}_{\overline{{\rm conv}}}(S)\cap\mathbb{Z}^{2}$ .
(v)

$S$ is closed under the median operation.
(vi)

$S$ is closed under some majority operation.

Then we have a chain of implications: (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Leftrightarrow$ (iii)’ $\Rightarrow$ (iv) $\Rightarrow$ (v) $\Rightarrow$ (vi).

Proof.

(i) $\Rightarrow$ (ii) is clear. (ii) $\Rightarrow$ (iii) is shown in shown in [19, Corollary 2]. (iii) $\Rightarrow$ (iii)’ is also shown in [19] (see also Lemma 4.7).

For (iii)’ $\Rightarrow$ (iii), from Proposition 2.20, if $S\subseteq\mathbb{Z}^{2}$ is integrally convex, then it can be represented by a UTVPI system. Then, $S$ is $\mu$ -closed from Proposition 4.10 in Section 4.

For (iii) $\Rightarrow$ (iv), since $S$ is $\mu$ -closed, it can be represented by a UTVPI system by Lemma 4.13. Since a polyhedron is convex and topologically closed, (iv) holds. (iv) $\Rightarrow$ (v) follows from Remark 2.15. (v) $\Rightarrow$ (vi) is clear since the median operation is a majority operation. ∎

4 Polyhedral representation and closedness under operations

We here analyze the relationship between the set of integer vectors in 2-decomposable polyhedra and closedness under operations using the results in Section 3.

4.1 Main results

Using Theorems 3.5, 3.7 and 3.8, we obtain the following. The proof of (iii) is based on the results in Subsection 4.2, which constitutes the most technical part in this paper.

Theorem 4.1.

Let $S$ be a subset of $\mathbb{Z}^{n}$ .

(i)

$S$ is representable by a SVPI system if and only if $S$ is midpoint-neighbor-closed.
(ii)

$S$ is representable by a DC system if and only if $S$ is closed under $g(x,y)=\lceil\frac{x+y}{2}\rceil$ and $h(x,y)=\lfloor\frac{x+y}{2}\rfloor$ , and from Theorem 3.5, these are equivalent to, say, $S=\Join_{1\leq i<j\leq n}{\rm cl}_{g,h}(\pi_{i,j}(S))$ .
(iii)

$S$ is representable by a UTVPI system if and only if $S$ is closed under some majority operation and $\mu$ , and from Theorem 3.5, these are equivalent to, say, $S=\Join_{1\leq i<j\leq n}{\rm cl}_{\mu}(\pi_{i,j}(S))$ .
(iv)

$S$ is representable by a TVPI system with possibly infinitely many inequalities if and only if $S=\Join_{1\leq i<j\leq n}{\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{n}$ .
(v)

$S$ is closed under the median operation if and only if $S=\Join_{1\leq i<j\leq n}{\rm cl}_{{\rm median}}(\pi_{i,j}(S))$ .
(vi)

$S$ is closed under some majority operation if and only if $S=\Join_{1\leq i<j\leq n}{\rm cl}_{g}(\pi_{i,j}(S))$ for some majority operation $g:\mathbb{Z}^{3}\to\mathbb{Z}$ .

Proof.

(i): We first show the only-if part. Assume that $S$ is representable by a SVPI system. Take any $x,y\in S$ . Since $S$ is representable by a SVPI system, interval $[x\wedge y,x\vee y]_{\mathbb{Z}}$ is contained in $S$ , i.e., $[x\wedge y,x\vee y]_{\mathbb{Z}}\subseteq S$ . Since for each $z\in N(\frac{x+y}{2})$ , $z\in[x\wedge y,x\vee y]_{\mathbb{Z}}$ holds, $S$ is midpoint-neighbor-closed.

We then show the if part. Assume that $S$ is midpoint-neighbor-closed. Then $S$ (and each $\pi_{i,j}(S)$ ) is also closed under $g(x,y)=\lceil\frac{x+y}{2}\rceil$ and $h(x,y)=\lfloor\frac{x+y}{2}\rfloor$ . Thus, by (ii) shown below, $S$ (and each $\pi_{i,j}(S)$ ) is representable by a DC system. It follows that $S$ is 2-decomposable, i.e., $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ , by Propositions 2.14 and 2.8. Then it suffices to show that each $\pi_{i,j}(S)$ is representable by a SVPI system. Fix a DC representation of $\pi_{i,j}(S)$ and denote it by $Ax\geq b$ . Let $x_{i}-x_{j}\geq c$ be a difference inequality in $Ax\geq b$ . We show that $x_{i}-x_{j}=c$ intersects $\pi_{i,j}(S)$ at less than two points, which implies that removing $x_{i}-x_{j}\geq c$ from $Ax\geq b$ and appropriately adding $x_{i}\geq c_{1}$ and $-x_{j}\geq c_{2}$ to it result in a representation of $\pi_{i,j}(S)$ with less difference inequalities than $Ax\geq b$ . Assume otherwise that $x_{i}-x_{j}=c$ intersects $\pi_{i,j}(S)$ at two (distinct) points, say, $p$ and $q$ . We can assume that $(p_{i}.p_{j})=(q_{i}+1,q_{j}+1)$ . Since $\pi_{i,j}(S)$ is midpoint-neighbor-closed, each $z\in N(\frac{p+q}{2})$ is in $\pi_{i,j}(S)$ . Then $\lfloor\frac{p_{i}+q_{i}}{2}\rfloor-\lceil\frac{p_{j}+q_{j}}{2}\rceil<\frac{p_{i}+q_{i}}{2}-\frac{p_{j}+q_{j}}{2}=c$ . Thus $z:=(\lfloor\frac{p_{i}+q_{i}}{2}\rfloor,\lceil\frac{p_{j}+q_{j}}{2}\rceil)$ violates inequality $x_{i}-x_{j}\geq c$ . However, $z$ is in $N(\frac{p+q}{2})$ , a contradiction. Similarly, we can remove $x_{j}-x_{i}\geq c$ from $Ax\geq b$ . Hence, $\pi_{i,j}(S)$ is representable by a SVPI system.

(ii) is a well-known result in discrete convex analysis; see, e.g., Equation (5.20) in [14].

(iii): We first show the only-if part. If $S$ is representable by a UTVPI system, by Theorem 4.9 (or Proposition 4.10), $S$ is closed under $\mu$ and ${\rm median}$ . Moreover, the ${\rm median}$ operation is a majority operation.

We then show the if part. Assume that $S$ is closed under some majority operation and $\mu$ . Then $S$ is 2-decomposable, i.e., $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ by Theorem 2.8. Since each $\pi_{i,j}(S)$ is closed under $\mu$ by Lemma 3.1, each $\pi_{i,j}(S)$ can be represented by a UTVPI system from Lemma 4.13. Hence, $S$ is representable by a UTVPI system.

(iv): We first show the only-if part. Assume that $S$ is representable by a TVPI system with possibly infinitely many inequalities. This implies that $S=\{x\in\mathbb{Z}^{n}\,:\,a_{k1}^{(i,j)}x_{i}+a_{k2}^{(i,j)}x_{j}\geq b_{k}^{(i,j)}(1\leq i<j\leq n,k\in I_{i,j})\}$ for some $a_{k1}^{(i,j)},a_{k2}^{(i,j)},b_{k}^{(i,j)}\in\mathbb{R}$ and a (possibly infinite) set $I_{i,j}$ of indices. For each $1\leq i<j\leq n$ , let $S_{ij}=\{x\in\mathbb{Z}^{2}\,:\,a_{k1}^{(i,j)}x_{i}+a_{k2}^{(i,j)}x_{j}\geq b_{k}^{(i,j)}(k\in I_{i,j})\}$ . Then, for $x\in\mathbb{Z}^{n}$ , $x\in S$ if and only if $(x_{i},x_{j})\in S_{ij}$ for $1\leq i<j\leq n$ . This implies that $S=\Join_{1\leq i<j\leq n}S_{ij}$ . Now, $S_{ij}={\rm cl}_{\overline{{\rm conv}}}(S_{ij})\cap\mathbb{Z}^{2}$ . Hence, $S=\Join_{1\leq i<j\leq n}{\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{n}$ holds.

We then show the if part. Note that $S=\Join_{1\leq i<j\leq n}{\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{n}$ is equivalent to the following condition:

•

for $x\in\mathbb{Z}^{n}$ , $x\in S$ if and only if $(x_{i},x_{j})\in{\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{2}$ for $1\leq i<j\leq n$ .

Each ${\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{2}$ can be represented as ${\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\cap\mathbb{Z}^{2}=\{x\in\mathbb{Z}^{2}\,:\,a_{k1}^{(i,j)}x_{i}+a_{k2}^{(i,j)}x_{j}\geq b_{k}^{(i,j)}(k\in I_{i,j})\}$ for some $a_{k1}^{(i,j)},a_{k2}^{(i,j)},b_{k}^{(i,j)}\in\mathbb{R}$ and a (possibly infinite) set $I_{i,j}$ of indices, since ${\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))$ is the intersection of all the closed half-spaces containing $\pi_{i,j}(S)$ (see [16, Corollary 11.5.1]). Hence, for $x\in\mathbb{Z}^{n}$ , $x\in S$ if and only if $a_{k1}^{(i,j)}x_{i}+a_{k2}^{(i,j)}x_{j}\geq b_{k}^{(i,j)}(1\leq i<j\leq n,k\in I_{i,j})$ . This implies that $S=\{x\in\mathbb{Z}^{n}\,:\,a_{k1}^{(i,j)}x_{i}+a_{k2}^{(i,j)}x_{j}\geq b_{k}^{(i,j)}(1\leq i<j\leq n,k\in I_{i,j})\}$ . Hence, $S$ is representable by a TVPI system with possibly infinitely many inequalities.

(v) follows from Theorems 3.5 and 3.8.

(vi) follows from Theorem 3.5. ∎

Combining Theorem 4.1 and the following proposition, we can characterize some closure operators.

Proposition 4.2.

Let $\bf{Q}$ be a property for a subset of ${\mathbb{Z}}^{n}$ which has closure operator ${\rm cl}_{\bf Q}$ , and $\bf{P}$ be a property for a subset of $\mathbb{Z}^{2}$ which has closure operator ${\rm cl}_{\bf P}$ . Then the following are equivalent.

(i)

For any $S\subseteq\mathbb{Z}^{n}$ , ${\bf{Q}}(S)\iff S=\Join_{1\leq i<j\leq n}{\rm cl}_{\bf P}(\pi_{i,j}(S))$
(ii)

For any $S\subseteq\mathbb{Z}^{n}$ , ${\rm cl}_{\bf{Q}}(S)=\Join_{1\leq i<j\leq n}{\rm cl}_{\bf P}(\pi_{i,j}(S))$ .

Proof.

We first show (i) $\Rightarrow$ (ii). By (a generalization of) Lemma 3.2, ${\rm cl}_{\bf Q}$ and $\Join_{1\leq i<j\leq n}{\rm cl}_{\bf P}(\pi_{i,j}(\cdot))$ are both closure operators. Then, (i) means that the families of the closed set defined by these closure operators are the same. Thus, these closure operators are the same and (ii) holds. We then show (ii) $\Rightarrow$ (i). Assume that (ii) is true. Then, ${\bf Q}(S)\Leftrightarrow S={\rm cl}_{\bf{Q}}({S}){\Leftrightarrow}S=\Join_{1\leq i<j\leq n}{\rm cl}_{\bf P}(\pi_{i,j}(S))$ . ∎

From Theorems 4.1 and 4.2, we see, for example, that ${\rm cl}_{{\rm median},\mu}$ is the same as $\Join_{1\leq i<j\leq n}{\rm cl}_{\mu}(\pi_{i,j}(\cdot))$ (see also Theorem 4.9 below).

We mention the following.

Proposition 4.3.

Let $S$ be a subset of $\mathbb{Z}^{n}$ . $S$ is representable by a UTVPI system if and only if it is integrally convex and 2-decomposable.

Proof.

We first show the only-if part. From Theorem 4.1, $S$ is closed under some majority operation and $\mu$ . Hence, $S$ is 2-decomposable and integrally convex by Theorems 2.8 and 4.7, respectively.

We then show the if part. Since $S$ is 2-decomposable, $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ . Moreover, it is known that the projection of an integrally convex set is integrally convex [12, Theorem 3.1]. Hence, each $\pi_{i,j}(S)$ is integrally convex. Then each $\pi_{i,j}(S)$ can be represented by a UTVPI system (see Proposition 2.20). Hence, $S$ is representable by a UTVPI system. ∎

Remark 4.4.

When $S$ is a subset of ${\mathbb{Z}}^{2}$ , the following are equivalent: (i) $S$ is representable by a UTVPI system, (ii) $S$ is $\mu$ -closed, and (iii) $S$ is integrally convex. The equivalence of (i) and (iii) follows from Proposition 2.20, and that of (ii) and (iii) follows from Proposition 3.8.

When $S$ is a subset of $\{0,1\}^{n}$ , the following are equivalent: (i) $S$ is representable by a UTVPI system, (ii) $S$ is representable by a TVPI system, (iii) $S$ is ${\rm median}$ -closed, and (iv) $S$ is closed under some majority operation. To see this, it suffices to show that (iv) implies (i). Assume that $S$ is closed under some majority operation. Notice that there exists the unique majority operation over $\{0,1\}$ , and $S$ is representable by a 2-CNF from [17]. Since 2-CNF can be formulated as a UTVPI system, (i) holds.

We also remark that any subset $S$ of $\{0,1\}^{n}$ is $\mu$ -closed and integrally convex. To see this, it suffices to show that any subset $S$ of $\{0,1\}^{n}$ is $\mu$ -closed. Take any $S\subseteq\{0,1\}^{n}$ . One can verify that for any $x,y\in\{0,1\}^{n}$ , $\mu(x,y)=x$ . Therefore, $S$ is $\mu$ -closed.

Remark 4.5.

We remark that property $S={\rm cl}_{\overline{{\rm conv}}}(S)\cap\mathbb{Z}^{n}$ is not preserved by projection. Namely, an analog of Lemma 3.1 does not hold. Consider the following example.

Let $S\subseteq{\mathbb{Z}}^{3}$ be a set defined as

S=\{(0,0,0),(2,2,3)\}.

Then, in the figure below, $S$ is the black points and ${\rm cl}_{\overline{{\rm conv}}}(S)\subseteq{\mathbb{R}}^{3}$ is the black line segment.

Thus, we have $S={\rm cl}_{\overline{{\rm conv}}}(S)\cap{\mathbb{Z}}^{3}$ . However, the projection $\pi_{1,2}(S)$ does not satisfy this condition. In fact, since the projection $\pi_{1,2}(S)=\{(0,0),(2,2)\}\subseteq{\mathbb{Z}}^{2}$ , the convex closure ${\rm cl}_{\overline{{\rm conv}}}(\pi_{1,2}(S))=\{(x_{1},x_{2})\in{\mathbb{R}}^{2}~{}|~{}0\leq x_{1}=x_{2}\leq 2\}$ . Thus, ${\rm cl}_{\overline{{\rm conv}}}(\pi_{1,2}(S))\cap{\mathbb{Z}}^{2}=\{(0,0),(1,1),(2,2)\}$ . Therefore, we have $\pi_{1,2}(S)\neq{\rm cl}_{\overline{{\rm conv}}}(\pi_{1,2}(S))\cap{\mathbb{Z}}^{2}$ .

Remark 4.6.

We also remark that, if a set $S\subseteq\mathbb{Z}^{n}$ is representable by a TVPI system, then it is ${\rm median}$ -closed by Proposition 2.14. However, even if $S$ is ${\rm median}$ -closed and representable by a linear-inequality system (i.e., $S$ is the integer vectors in a polyhedron), it is not representable by a TVPI system in general as Example 4.15 in Subsection 4.3 shows.

4.2 Remaining proofs

The following lemma is shown in [19] for a more general function variant, but a proof is given here for readability.

Lemma 4.7.

Let $S$ be a subset of $\mathbf{Z}^{n}$ . If $S$ is $\mu$ -closed, then it is integrally convex.

Proof.

From Theorem 2.19, it suffices to show that $\frac{x+y}{2}\in{\rm cl}_{{\rm conv}}(S\cap N(\frac{x+y}{2}))$ for any $x,y\in S$ . Since $S$ is closed under $\mu$ , we have $\mu(x,y),\mu(y,x)\in S$ . It is clear that $\mu(x,y),\mu(y,x)\in N(\frac{x+y}{2})$ . Now, since $\mu(x,y)+\mu(y,x)=x+y$ , we have $\frac{x+y}{2}=\frac{\mu(x,y)+\mu(y,x)}{2}\in{\rm cl}_{{\rm conv}}(\{\mu(x,y),\mu(y,x)\})\subseteq{\rm cl}_{{\rm conv}}(S\cap N(\frac{x+y}{2}))$ . Hence, $S$ is integrally convex. ∎

We have proved that any $S\subseteq\mathbb{Z}^{n}$ closed under $\mu$ is integrally convex. The converse, however, does not hold in general as the following example shows.

Example 4.8.

Let $S=\{(-1,1,1),(0,0,1),(0,1,0),(1,0,0)\}\subseteq\{-1,0,1\}^{3}$ . The points in $S$ lies on the plane $x_{1}+x_{2}+x_{3}=1$ in three-dimension. One can verify that

\displaystyle{\rm cl}_{{\rm conv}}(S)={\rm cl}_{{\rm conv}}(\{(-1,1,1),(0,0,1),(0,1,0)\})\cup{\rm cl}_{{\rm conv}}(\{(0,0,1),(0,1,0),(1,0,0)\})

and $S$ is integrally convex. On the other hand, as $\mu((-1,1,1),(1,0,0))=(0,1,1)\notin S$ , S is not closed under $\mu$ . Hence, integral convexity does not imply $\mu$ -closedness in general.

We now show the key result to show Theorem 4.1 (iii).

Theorem 4.9.

A set $S\subseteq\mathbf{Z}^{n}$ is representable by a UTVPI system if and only if it is closed under $\mu$ and ${\rm median}$ .

Theorem 4.9 is divided into Propositions 4.10 and 4.14.

Proposition 4.10.

Let $S$ be a subset of $\mathbf{Z}^{n}$ . If $S$ is representable by a UTVPI system, then it is closed under $\mu$ and ${\rm median}$ .

Proof.

Since a UTVPI polyhedron is a TVPI polyhedron, it follows that $S$ is closed under ${\rm median}$ by Proposition 2.14. Thus we show that $S$ is closed under $\mu$ in what follows.

Assume that $S$ is represented by a UTVPI system $Ax\geq b$ for some matrix $A$ and vector $b$ , i.e., $S=\{x\in{\mathbb{Z}}^{n}\,:\,Ax\geq b\}$ . Without loss of generality, we assume that $b$ is an integer vector. Let $p,q\in S$ . We show that $\mu(p,q)\in S$ by showing that $A\mu(p,q)\geq b$ holds. For each $i=1,\dots,m$ , let $A_{i}$ be the $i$ th row of $A$ . We have to show that $A_{i}\mu(p,q)\geq b_{i}$ for each $i=1,\dots,m$ . Since $Ax\geq b$ is a UTVPI system, each $A_{i}x\geq b_{i}$ is one of the forms of $x_{j}+x_{k}\geq b_{i}$ , $x_{j}-x_{k}\geq b_{i}$ , $-x_{j}+x_{k}\geq b_{i}$ , $-x_{j}-x_{k}\geq b_{i}$ , $x_{j}\geq b_{i}$ , or $-x_{j}\geq b_{i}$ for some $j,k\in\{1,\dots,n\}$ with $j\neq k$ . We use the fact that $A_{i}p\geq b_{i}$ and $A_{i}q\geq b_{i}$ (since $p$ and $q$ are in $S$ ) in what follows.

We only show the cases where $A_{i}x=x_{j}+x_{k}$ and $A_{i}x=x_{j}-x_{k}$ . The other cases can be shown similarly and thus are omitted.

Case 1: $A_{i}x=x_{j}+x_{k}$ .

We show that $\mu(p_{j},q_{j})+\mu(p_{k},q_{k})\geq b_{i}$ . Note that from $p_{j}+p_{k}\geq b_{i}$ and $q_{j}+q_{k}\geq b_{i}$ we have $p_{j}+p_{k}+q_{j}+q_{k}\geq 2b_{i}$ , implying that $\frac{p_{j}+q_{j}}{2}+\frac{p_{k}+q_{k}}{2}\geq b_{i}$ .

Case 1.1: $p_{j}+q_{j}$ and $p_{k}+q_{k}$ are even.

In this case, we have $\mu(p_{j},q_{j})=\frac{p_{j}+q_{j}}{2}$ and $\mu(p_{k},q_{k})=\frac{p_{k}+q_{k}}{2}$ . Thus, we have

\displaystyle\mu(p_{j},q_{j})+\mu(p_{k},q_{k})=\frac{p_{j}+q_{j}}{2}+\frac{p_{k}+q_{k}}{2}\geq b_{i}.

Case 1.2: $p_{j}+q_{j}$ is even and $p_{k}+q_{k}$ is odd.

In this case, $p_{j}+p_{k}+q_{j}+q_{k}\geq 2b_{i}$ implies that $p_{j}+p_{k}+q_{j}+q_{k}\geq 2b_{i}+1$ since the left-hand side is odd. Thus, we have $\frac{p_{j}+q_{j}}{2}+\frac{p_{k}+q_{k}}{2}-\frac{1}{2}\geq b_{i}$ . Since $\mu(p_{j},q_{j})=\frac{p_{j}+q_{j}}{2}$ and $\mu(p_{k},q_{k})\geq\frac{p_{k}+q_{k}}{2}-\frac{1}{2}$ , we have

\displaystyle\mu(p_{j},q_{j})+\mu(p_{k},q_{k})\geq\frac{p_{j}+q_{j}}{2}+\frac{p_{k}+q_{k}}{2}-\frac{1}{2}\geq b_{i}.

Case 1.3: $p_{j}+q_{j}$ is odd and $p_{k}+q_{k}$ is even.

We can show $\mu(p_{j},q_{j})+\mu(p_{k},q_{k})\geq b_{i}$ in a similar way as in Case 1.2.

Case 1.4: $p_{j}+q_{j}$ and $p_{k}+q_{k}$ are odd.

We further divide into the cases of $p_{j}>q_{j}$ , $p_{k}>q_{k}$ , or ( $p_{j}\leq q_{j}$ and $p_{k}\leq q_{k}$ ).

If $p_{j}>q_{j}$ , then $\mu(p_{j},q_{j})=\frac{p_{j}+q_{j}}{2}+\frac{1}{2}$ since $p_{j}+q_{j}$ is odd. Moreover, $\mu(p_{k},q_{k})\geq\frac{p_{k}+q_{k}}{2}-\frac{1}{2}$ . Hence, we have

\displaystyle\mu(p_{j},q_{j})+\mu(p_{k},q_{k})\geq\frac{p_{j}+q_{j}}{2}+\frac{1}{2}+\frac{p_{k}+q_{k}}{2}-\frac{1}{2}\geq b_{i}.

If $p_{k}>q_{k}$ , then $\mu(p_{k},q_{k})=\frac{p_{k}+q_{k}}{2}+\frac{1}{2}$ since $p_{k}+q_{k}$ is odd. Moreover, $\mu(p_{j},q_{j})\geq\frac{p_{j}+q_{j}}{2}-\frac{1}{2}$ . Hence, we have

\displaystyle\mu(p_{j},q_{j})+\mu(p_{k},q_{k})\geq\frac{p_{j}+q_{j}}{2}-\frac{1}{2}+\frac{p_{k}+q_{k}}{2}+\frac{1}{2}\geq b_{i}.

Finally, consider the case of $p_{j}\leq q_{j}$ and $p_{k}\leq q_{k}$ . We have $2p_{j}\leq p_{j}+q_{j}$ , and thus $p_{j}\leq\frac{p_{j}+q_{j}}{2}$ . Since $p_{j}$ is an integer we have $p_{j}\leq\lfloor\frac{p_{j}+q_{j}}{2}\rfloor=\mu(p_{j},q_{j})$ . Similarly, we have $p_{k}\leq\mu(p_{k},q_{k})$ Therefore, we have

\displaystyle\mu(p_{j},q_{j})+\mu(p_{k},q_{k})\geq p_{j}+p_{k}\geq b_{i}.

Case 2: $A_{i}x=x_{j}-x_{k}$ .

We show that $\mu(p_{j},q_{j})-\mu(p_{k},q_{k})\geq b_{i}$ . Note that from $p_{j}-p_{k}\geq b_{i}$ and $q_{j}-q_{k}\geq b_{i}$ we have $p_{j}-p_{k}+q_{j}-q_{k}\geq 2b_{i}$ , implying that $\frac{p_{j}+q_{j}}{2}-\frac{p_{k}+q_{k}}{2}\geq b_{i}$ . Then the proof goes similarly to that of Case 1.

Now, we have shown that $\mu(p.q)$ satisfies each inequality $A_{i}x\geq b_{i}$ ( $i=1,\dots,m$ ). Hence, $\mu(p.q)\in S$ holds. Therefore, $S$ is closed under $\mu$ . This completes the proof. ∎

As a corollary of the Proposition 4.10, we have the following result.

Corollary 4.11.

For a set $S\subseteq\mathbb{Z}^{n}$ , the directed discrete midpoint closure ${\rm cl}_{\mu}(S)$ of $S$ is included in the UTVPI closure ${\rm cl}_{{\rm UTVPI}}(S)$ of $S$ .

Proof.

Since ${\rm cl}_{{\rm UTVPI}}(S)$ is representable by a UTVPI system, by Proposition 4.10, ${\rm cl}_{{\rm UTVPI}}(S)$ is closed under $\mu$ . Now, ${\rm cl}_{\mu}(S)$ is the (inclusion-wise) smallest set that is closed under $\mu$ and includes $S$ . Therefore, ${\rm cl}_{\mu}(S)\subseteq{\rm cl}_{{\rm UTVPI}}(S)$ . ∎

We note that there exists a TVPI polyhedron where its integer vectors are not $\mu$ -closed.

Example 4.12.

Consider the following TVPI system.

\displaystyle\left\{\begin{array}[]{l}x_{1}+2x_{2}\geq 2\\ 0\leq x_{1},x_{2}\leq 2.\end{array}\right.

(4)

The set $S$ of integer vectors satisfying the system is

\displaystyle S=\{(0,1),(0,2),(1,1),(1,2),(2,0),(2,1),(2,2)\}.

Since $\mu((2,0),(0,1))=(\mu(2,0),\mu(0,1))=(1,0)\notin S$ , $S$ is not $\mu$ -closed.

We now show the opposite direction of Proposition 4.10. The following is a key lemma to show our result.

Lemma 4.13.

Let $S$ be a subset of $\mathbf{Z}^{2}$ . If $S$ is $\mu$ -closed, then $S$ is representable by a UTVPI system.

Proof.

See Remark 4.4. ∎

Proposition 4.14.

If a set $S\subseteq\mathbf{Z}^{n}$ is closed under $\mu$ and ${\rm median}$ , then it is representable by a UTVPI system.

Proof.

First, since $S$ is ${\rm median}$ -closed, it is 2-decomposable, i.e., $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ . Since each $\pi_{i,j}(S)$ is two-dimensional and $\mu$ -closed by Lemma 3.1, it is representable by a UTVPI system $A^{(ij)}(x_{i},x_{j})^{T}\geq b^{(ij)}$ by Lemma 4.13. Then, clearly, $S=\{x\in\mathbb{Z}^{n}\,:\,A^{(ij)}(x_{i},x_{j})^{T}\geq b^{(ij)}(\forall i,j)\}$ ). Hence, $S$ is representable by a UTVPI system. ∎

Proof of Theorem 4.9.

It follows from Propositions 4.10 and 4.14. ∎

4.3 TVPI representability cannot be characterized by median-closedness

One may expect that if the set of integer vectors in a polyhedron is ${\rm median}$ -closed, then it is representable by a TVPI system (i.e., the opposite of Proposition 2.14). However, this is not the case, as the following example shows.

Example 4.15.

Let

\displaystyle A=\begin{pmatrix}2&0&-1\\ 0&2&-1\\ -2&-2&3\\ 0&0&-1\\ \end{pmatrix}\ and\ b=\begin{pmatrix}0\\ 0\\ 0\\ 2\end{pmatrix}.

Consider a set $S\subseteq\mathbb{Z}^{3}$ defined as

S:=\{x\in\mathbb{Z}^{3}\,:\,Ax\geq b\}\ (=\{(0,0,0),(1,1,2),(2,1,2),(1,2,2)\}).

Then $S$ is the black points in the figure below.

We now show that $S$ is ${\rm median}$ -closed, whereas it is not representable by a TVPI system.

First we see that $S$ is ${\rm median}$ -closed. Indeed, it is trivial when at least two of three arguments of ${\rm median}$ are the same. Otherwise, we have

	$\displaystyle{\rm median}((0,0,0),(1,1,2),(2,1,2))=(1,1,2)\in S,$
	$\displaystyle{\rm median}((0,0,0),(1,1,2),(1,2,2))=(1,1,2)\in S,$
	$\displaystyle{\rm median}((0,0,0),(2,1,2),(1,2,2))=(1,1,2)\in S,$
	$\displaystyle{\rm median}((1,1,2),(2,1,2),(1,2,2))=(1,1,2)\in S.$

Thus, $S$ is ${\rm median}$ -closed.

We next show that $S$ is not representable by a TVPI system. Assume otherwise that we have a TVPI representation $S=\{x\in\mathbb{Z}^{3}\,:\,A^{\prime}x\geq b^{\prime}\}$ . Then the following equality holds.

S=\pi_{1,2}^{-1}({\rm cl}_{\overline{{\rm conv}}}({\pi_{1,2}(S)}))\cap\pi_{1,3}^{-1}({\rm cl}_{\overline{{\rm conv}}}(\pi_{1,3}(S)))\cap\pi_{2,3}^{-1}({\rm cl}_{\overline{{\rm conv}}}(\pi_{2,3}(S)))\cap\mathbb{Z}^{3}

(5)

Indeed, since $S\subseteq\pi_{i,j}^{-1}(\pi_{i,j}(S))\subseteq\pi_{i,j}^{-1}({\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S)))$ , the left-hand side of $(2)$ is included in the right-hand side. Conversely, letting $p=(p_{1},p_{2},p_{3})$ be a vector in the right-hand side of $(2)$ , we show that $p\in S$ . It suffices to show that any two-variable inequality $a_{1}x_{i}+a_{2}x_{j}\geq b_{1}$ of $A^{\prime}x\geq b^{\prime}$ is satisfied by $p$ , i.e., $a_{1}p_{i}+a_{2}p_{j}\geq b_{1}$ . Since, $p\in\pi_{i,j}^{-1}({\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S)))$ , we have $\pi_{i,j}(p)\in{\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))$ . Moreover, since $\pi_{i,j}(S)\subseteq\{(x_{i},x_{j})\in\mathbb{R}^{2}\,:\,a_{1}x_{i}+a_{2}x_{j}\geq b_{1}\}$ , we have ${\rm cl}_{\overline{{\rm conv}}}(\pi_{i,j}(S))\subseteq\{(x_{i},x_{j})\in\mathbb{R}^{2}\,:\,a_{1}x_{i}+a_{2}x_{j}\geq b_{1}\}$ . Hence, we have $a_{1}p_{i}+a_{2}p_{j}\geq b_{1}$ .

Now, ${\rm cl}_{\overline{{\rm conv}}}(\pi_{1,2}(S))$ , ${\rm cl}_{\overline{{\rm conv}}}(\pi_{1,3}(S))$ , and ${\rm cl}_{\overline{{\rm conv}}}\pi_{2,3}(S))$ are the following grayed out subsets where the black circles are the projection of the points in $S$ , and the squares are integer points in the grayed out subset that are not in the projection of the points in $S$ .

We see that $(1,1,1)$ is included in the right-hand side of $(\ref{eq:ofS})$ . But $(1,1,1)\notin S$ which means $S$ is not representable by a TVPI system.

5 Characterizing 2-decomposability

We now turn our attention to characterizing 2-decomposability.

Definition 5.1 (Partial operation).

An operation $D\to{\mathbb{Z}}$ , where $D\subseteq{\mathbb{Z}}^{k}$ , is called a ( $k$ -ary) partial operation (over ${\mathbb{Z}}$ ). $D$ is called the domain of $f$ and denoted by ${\rm dom}(f)$ . If $x\in D$ , then we say $f(x)$ is defined, and otherwise (i.e., if $x\notin D$ ) undefined.

Since a partial operation is not defined for some inputs, we can define closedness under such operation in several ways.

Definition 5.2.

Let $S$ be a subset of $\mathbb{Z}^{n}$ . Let $f:D\to{\mathbb{Z}}$ , where $D\subseteq{\mathbb{Z}}^{k}$ , be a partial operation.

(i)

We say $S$ is strongly closed under $f$ (or, strongly $f$ -closed) if for any $x^{(1)},\dots,x^{(k)}\in S$ , there exists $x\in S$ that satisfies $f(x^{(1)}_{i},\dots,x^{(k)}_{i})=x_{i}$ for each $1\leq i\leq n$ such that $f(x^{(1)}_{i},\dots,x^{(k)}_{i})$ is defined.
(ii)

We say $S$ is weakly closed under $f$ (or, weakly $f$ -closed) if for any $x^{(1)},\dots,x^{(k)}\in S$ such that $f(x^{(1)}_{i},\dots,x^{(k)}_{i})$ is defined for all $1\leq i\leq n$ , we have $f(x^{(1)},\dots,x^{(k)})\in S$ .

Definition 5.3.

Let $S$ be a subset of ${\mathbb{Z}}^{n}$ . Let $f_{i}:{\mathbb{Z}}^{n}\to{\mathbb{Z}}$ be an operation associated with the $i$ th coordinate for each $1\leq i\leq n$ . We say $S$ is closed under $(f_{i})_{1\leq i\leq n}$ (or, $(f_{i})_{1\leq i\leq n}$ -closed) if for any $x^{(1)},\dots,x^{(k)}\in S$

\displaystyle(f_{1}(x^{(1)}_{1},\dots,x^{(k)}_{1}),\dots,f_{n}(x^{(1)}_{n},\dots,x^{(k)}_{n}))\in S.

Definition 5.4.

The partial majority operation ${\rm maj}_{p}:{\rm dom}({\rm maj}_{p})\rightarrow\mathbb{Z}$ is defined as follows. Firstly, its domain ${\rm dom}({\rm maj}_{p})=\{(x,x,y)\,:\,x,y\in\mathbb{Z}\}\cup\{(x,y,x)\,:\,x,y\in\mathbb{Z}\}\cup\{(y,x,x)\,:\,x,y\in\mathbb{Z}\}\subseteq\mathbb{Z}^{3}$ . Then, for all $x,y\in\mathbb{Z}$ ,

\displaystyle{\rm maj}_{p}(x,x,y)={\rm maj}_{p}(x,y,x)={\rm maj}_{p}(y,x,x)=x.

We first summarize the relationships between 2-decomposability and closedness under (partial) operations.

Proposition 5.5.

For a subset $S\subseteq\mathbb{Z}^{n}$ , consider the following properties.

(i)

$S$ is closed under some majority operation.
(ii)

We can associate a majority operation $f_{i}$ for each coordinate $i$ of $S$ and $S$ is $(f_{i})_{i}$ -closed.
(iii)

$S$ is strongly closed under the partial majority operation.
(iv)

$S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ (i.e., $S$ is 2-decomposable).
(v)

$S$ is weakly closed under the partial majority operation.

For each property, we also consider the hereditary version of it, denoted by $(\cdot)^{h}$ , which requires that every projection of $S$ satisfies the property. Then we have a chain of implications: (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (iv) $\Rightarrow$ (v). We also have the following equivalences: (i) $\Leftrightarrow$ $(i)^{h}$ , (ii) $\Leftrightarrow$ $(ii)^{h}$ , and (iii) $\Leftrightarrow$ $(iii)^{h}$ $\Leftrightarrow$ $(iv)^{h}$ $\Leftrightarrow$ $(v)^{h}$ .

Proof.

For (i) $\Rightarrow$ (ii), if $S$ is closed under majority operation $f$ , we can take $f_{i}:=f$ for all $1\leq i\leq n$ . For (ii) $\Rightarrow$ (iii), consider arbitrary $x^{(1)},x^{(2)},x^{(3)}\in S$ . We know that $(f_{1}(x^{(1)}_{1},x^{(2)}_{1},x^{(3)}_{1}),\dots,f_{n}(x^{(1)}_{n},x^{(2)}_{n},x^{(3)}_{n})\in S$ . Moreover, for each $1\leq i\leq n$ such that $(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})\in{\rm dom}({\rm maj}_{p})$ we have ${\rm maj}_{p}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})=f_{i}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})$ since $f_{i}$ is a majority operation. Hence, $S$ is strongly closed under ${\rm maj}_{p}$ .

For (iii) $\Rightarrow$ (iv), it is clear that $S\subseteq\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ . Thus, we show the inverse inclusion. This is trivial when $n=2$ . Assume that $n\geq 3$ in the following. Take $x\in\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ . Now, for $3\leq\ell\leq n$ , we show for any subset $I\subseteq[n]$ of cardinality $\ell$ there exists $y\in S$ such that $x_{i}=y_{i}$ for all $i\in I$ . We show this by induction on $\ell$ . First, consider the case of $\ell=3$ . Without of loss generality, we consider $I=\{1,2,3\}$ . Since $x\in\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ , there exist $x^{(1,2)},x^{(1,3)},x^{(2,3)}\in S$ such that $\pi_{1,2}(x^{(1,2)})=\pi_{1,2}(x)$ , $\pi_{1,3}(x^{(1,3)})=\pi_{1,3}(x)$ , and $\pi_{2,3}(x^{(2,3)})=\pi_{2,3}(x)$ . Therefore, for each $i\in I$ , ${\rm maj}_{p}(x^{(1,2)}_{i},x^{(1,3)}_{i},x^{(2,3)}_{i})$ is defined and equal to $x_{i}$ . Since $S$ is strongly closed under ${\rm maj}_{p}$ , there exists $y\in S$ such that $y_{i}={\rm maj}_{p}(x^{(1,2)}_{i},x^{(1,3)}_{i},x^{(2,3)}_{i})$ for all $i\in I$ . This shows the case of $\ell=3$ . For $\ell>3$ , Without of loss generality, we consider $I=\{1,\dots,\ell\}$ . By induction hypothesis for $I_{1,2}=\{1,2,4,\dots,\ell\},I_{1,3}=\{1,3,4,\dots,\ell\}$ , and $I_{2,3}=\{2,3,4,\dots,\ell\}$ , we can take $x^{(1,2)},x^{(1,3)},x^{(2,3)}\in S$ such that $x^{(j,k)}_{i}=x_{i}$ for all $i\in I_{j,k}$ where $(j,k)=(1,2),(1,3),(2,3)$ . It follows that for all $i\in I$ we have ${\rm maj}_{p}(x^{(1,2)}_{i},x^{(1,3)}_{i},x^{(2,3)}_{i})=x_{i}$ . Since $S$ is strongly closed under ${\rm maj}_{p}$ , there exists $y\in S$ such that $y_{i}={\rm maj}_{p}(x^{(1,2)}_{i},x^{(1,3)}_{i},x^{(2,3)}_{i})$ for all $i\in I$ . This shows the case of general $\ell$ . Therefore, $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ .

We then show (iv) $\Rightarrow$ (v). We assume $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ . For any $x^{(1)},x^{(2)},x^{(3)}\in S$ such that $(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})\in{\rm dom}({\rm maj}_{p})$ for all $1\leq i\leq n$ , let $y:={\rm maj}_{p}(x^{(1)},x^{(2)},x^{(3)})$ . By the definition of $y$ , for each $1\leq i<j\leq n$ , $\pi_{i,j}(y)$ is equal to at least one of $\pi_{i,j}(x^{(1)}),\pi_{i,j}(x^{(2)}),$ and $\pi_{i,j}(x^{(3)})$ . Thus, $\pi_{i,j}(y)\in\pi_{i,j}(S)$ . Since $S=\Join_{1\leq i<j\leq n}\pi_{i,j}(S)$ , we have $y\in S$ . Hence, $S$ is weakly closed under ${\rm maj}_{p}$ .

For the relationships with the hereditary versions, it is clear that $(\cdot)^{h}$ implies $(\cdot)$ . Hence, it suffices to show that (i) $\Rightarrow$ (i $)^{h}$ , (ii) $\Rightarrow$ (ii $)^{h}$ , (iii) $\Rightarrow$ (iii $)^{h}$ , and (v $)^{h}$ $\Rightarrow$ (iii $)^{h}$ .

For (i) $\Rightarrow$ (i $)^{h}$ , we can show that closedness under operations is preserved by projection in a similar way as Lemma 3.1.

For (ii) $\Rightarrow$ (ii $)^{h}$ , let $I\subseteq\{1,\dots,n\}$ and take $x^{(1)},x^{(2)},x^{(3)}\in\pi_{I}(S)$ . Then for each $j=1,2,3$ there exists $y^{(j)}\in S$ such that $\pi_{I}(y^{(j)})=x^{(j)}$ . By assumption, $y:=(f_{1}(y^{(1)}_{1},y^{(2)}_{1},y^{(3)}_{1}),\dots,f_{n}(y^{(1)}_{n},y^{(2)}_{n},y^{(3)}_{n}))\in S$ . Therefore, $(f_{i}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i}))_{i\in I}=\pi_{I}(y)\in\pi_{I}(S)$ .

For (iii) $\Rightarrow$ (iii $)^{h}$ , let $I\subseteq\{\ 1,\dots,n\}$ and take $x^{(1)},x^{(2)},x^{(3)}\in\pi_{I}(S)$ . Then for each $j=1,2,3$ there exists $y^{(j)}\in S$ such that $\pi_{I}(y^{(j)})=x^{(j)}$ . By assumption, there exists $y\in S$ that satisfies $y_{i}={\rm maj}_{p}(y^{(1)}_{i},y^{(2)}_{i},y^{(3)}_{i})$ for all $1\leq i\leq n$ such that ${\rm maj}_{p}(y^{(1)}_{i},y^{(2)}_{i},y^{(3)}_{i})$ is defined. Then $\pi_{I}(y)$ satisfies that $y_{i}={\rm maj}_{p}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})$ for all $i\in I$ such that ${\rm maj}_{p}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})$ is defined.

Finally, for (v $)^{h}$ $\Rightarrow$ (iii $)^{h}$ , it suffices to show that (v $)^{h}$ $\Rightarrow$ (iii) (since we have shown (iii) $\Rightarrow$ (iii $)^{h}$ ). Take $x^{(1)},x^{(2)},x^{(3)}\in S$ . Let $I=\{i\in\{1,\dots,n\}\,:\,{\rm maj}_{p}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})\text{ is defined}\}$ . By assumption, $\pi_{I}(S)$ is weakly ${\rm maj}_{p}$ -closed. Therefore, there exists $y\in\pi_{I}(S)$ such that $y_{i}={\rm maj}_{p}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})$ for all $i\in I$ . Then there exists $x\in S$ such that $x_{i}=y_{i}$ for all $i\in I$ . This $x$ satisfies that $x_{i}={\rm maj}_{p}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})$ for all $i\in I$ such that ${\rm maj}_{p}(x^{(1)}_{i},x^{(2)}_{i},x^{(3)}_{i})$ is defined. ∎

We note that none of the properties in Proposition 5.5 other than (iv) can characterize (iv), i.e., 2-decomposability. We observe in the following example that it is indeed not possible to characterize 2-decomposability by closedness under operations by showing that 2-decomposability is not preserved by projection. Note that closedness under operations is preserved by projection, which can be shown in a similar way as Lemma 3.1 (i).

Example 5.6.

Let $S=\{(0,0,1,2),(0,1,0,3),(1,0,0,4)\}$ . Then $S$ is 2-decomposable. To see this, take $x\in\Join_{1\leq i<j\leq 4}\pi_{i,j}(S)$ . First, assume that $\pi_{1,4}(x)=(0,2)$ . As $\pi_{1,2}(x)\in\pi_{1,2}(S)$ and $\pi_{1,3}(x)\in\pi_{1,3}(S)$ , we must have $x=(0,0,1,2)$ . Hence, we have $x\in S$ . We can similarly show $x\in S$ in the cases of $\pi_{1,4}(x)=(0,3)$ and $\pi_{1,4}(x)=(1,4)$ . Hence, $S$ is 2-decomposable. On the other hand, $S^{\prime}:=\pi_{1,2,3}(S)$ , which equals $\{(0,0,1),(0,1,0),(1,0,0)\}$ , is not 2-decomposable, since $(0,0,0)\in\Join_{1\leq i<j\leq 3}\pi_{i,j}(S^{\prime})\setminus S^{\prime}$ . Hence, 2-decomposability is not preserved by projection in general.

While 2-decomposability cannot be characterized by closedness under operations, we show that it can be indeed characterized by weak closedness under infinitely many partial operations. Intuitively, we prepare all the partial operations that correspond to the condition of 2-decomposability. Concretely, assume that $S\subseteq\mathbb{Z}^{4}$ is 2-decomposable. Then $S$ contains all vectors $x=(x_{1},x_{2},x_{3},x_{4})$ such that $\pi_{i,j}(x)\in\pi_{i,j}(S)$ for all $1\leq i<j\leq 4$ . The latter condition can be rewritten as $(x_{1},x_{2},*,*)$ , $(x_{1},*,x_{3},*)$ , $(x_{1},*,*,x_{4})$ , $(*,x_{2},x_{3},*)$ , $(*,x_{2},*,x_{4})$ , $(*,*,x_{3},x_{4})\in S$ , where $*$ can be any (distinct) integer. Then the condition $x\in S$ is guaranteed by weak closedness under the partial operation $f:\mathbb{Z}^{6}\to\mathbb{Z}$ such that $f(y_{1},y_{1},y_{1},*,*,*)=y_{1}$ , $f(y_{2},*,*,y_{2},y_{2},*)=y_{2}$ , $f(*,y_{3},*,y_{3},*,y_{3})=y_{3}$ , and $f(*,*,y_{4},*,y_{4},y_{4})=y_{4}$ for all $y_{1},y_{2},y_{3},y_{4}\in{\mathbb{Z}}$ , where $*$ can be any (distinct) integer, and $f$ is undefined for the other inputs. In this way, we prepare partial operations that correspond to each dimension to characterize 2-decomposability by weak closedness under operations.

Now, we formally state the above intuition. For each integer $k\geq 2$ , we will define a partial operation $f^{(k)}$ over ${\mathbb{Z}}$ with ${\rm dom}(f^{(k)})\subseteq{\mathbb{Z}}^{\binom{k}{2}}$ . We first define ${\rm dom}(f^{(k)})$ . Let $T_{k}$ be the set of two-element subsets of $[k]:=\{1,\dots,k\}$ , that is

T_{k}:=\{\{\ell,m\}\subseteq[k]\,:\,\ell\neq m\}.

Thus, we have $|T_{k}|=\binom{k}{2}$ . We identify ${\mathbb{Z}}^{T_{k}}$ with ${\mathbb{Z}}^{\binom{k}{2}}$ below. Then, we define a family $\mathscr{S}_{k}\subseteq{\rm Pow}(T_{k})$ as $\mathscr{S}_{k}:=\{S_{1},\dots,S_{k}\}$ where each $S_{\ell}$ is defined as

S_{\ell}:=\{\{p,q\}\in T_{k}~{}|~{}\ell\in\{p,q\}\}.

By definition, we have $|S_{\ell}|=k-1$ , and for different $\ell,m$ , we have $S_{\ell}\cap S_{m}=\{\{\ell,m\}\}$ .

Then, for each $d\in{\mathbb{Z}}$ and $S_{\ell}\in\mathscr{S}_{k}$ , we define $Q_{d}(S_{\ell})\subseteq{\mathbb{Z}}^{T_{k}}$ as

Q_{d}(S_{\ell}):=\{(x_{\{p,q\}})_{\{p,q\}\in T_{k}}\in{\mathbb{Z}}^{T_{k}}\,:\,x_{\{\ell,m\}}=d~{}{\rm for}~{}m\in[k]\setminus\{\ell\}\}.

Now, taking union of all of the above set for $d\in{\mathbb{Z}},S_{\ell}\in\mathscr{S}_{k}$ , we obtain ${\rm dom}(f^{(k)})\subseteq{\mathbb{Z}}^{T_{k}}$ , that is

{\rm dom}(f^{(k)}):=\bigcup_{d\in{\mathbb{Z}},S_{\ell}\in\mathscr{S}_{k}}Q_{d}(S_{\ell}).

Note that if $(x_{\{p,q\}})_{\{p,q\}\in T_{k}}\in Q_{d}(S_{\ell})\cap Q_{d^{\prime}}(S_{m})$ , we have $d=x_{\{\ell,m\}}=d^{\prime}$ . Therefore, for $(x_{\{p,q\}})_{\{p,q\}\in T_{k}}\in{\rm dom}(f^{(k)})$ , we define $f^{(k)}((x_{\{p,q\}})_{\{p,q\}\in T_{k}}):=d$ where $d\in{\mathbb{Z}}$ is the unique element such that $(x_{\{p,q\}})_{\{p,q\}\in T_{k}}\in Q_{d}(S_{\ell})$ for some $\ell$ .

Then we define a set $F$ of partial operations as

F:=\{f^{(k)}\,:\,k\geq 2\}.

Now we are ready to show our result that characterizes 2-decomposability.

Theorem 5.7.

Let $S$ be a subset of $\mathbb{Z}^{n}$ . $S$ is 2-decomposable if and only if $S$ is weakly $f$ -closed for each $f\in F$ .

Proof.

For the if part, take any $x\in\Join_{i,j}\pi_{i,j}(S)$ . It suffices to show that $x\in S$ . For each $1\leq i<j\leq n$ , there exists $s^{(i,j)}\in S$ such that $\pi_{i,j}(x)=\pi_{i,j}(s^{(i,j)})$ . Now, applying $f^{(n)}$ to vectors $s^{(i,j)}$ $(1\leq i<j\leq n)$ , we obtain $x$ . Since $S$ is weakly $f^{(n)}$ -closed, we have $x\in S$ . Therefore, $S$ is 2-decomposable.

We then show the only-if part. Assume that $S$ is 2-decomposable. We show that $S$ is weakly $f^{(k)}$ -closed for each $f^{(k)}\in F$ . Fix $k\geq 2$ and take any (multi-)set $\{s^{(\ell,m)}\,:\,\{\ell,m\}\in T_{k}\}$ of elements of $S$ on which $f^{(k)}$ is defined. For $1\leq i\leq n$ , define $r^{(i)}\in{\mathbb{Z}}^{T_{k}}$ as

r^{(i)}_{\{\ell,m\}}:=s^{(\ell,m)}_{i}.

Then we have $r^{(i)}\in{\rm dom}(f^{(k)})$ for each $i$ . Moreover, by definition, we have $f^{(k)}((s^{(\ell,m)})_{\{\ell,m\}\in T_{k}})=(f^{(k)}(r^{(i)}))_{i\in[n]}$ . Hence, it suffices that $(f^{(k)}(r^{(i)}))_{i\in[n]}\in S$ . For each $i\in[n]$ , arbitrarily take $d_{i}\in{\mathbb{Z}}$ and $\ell_{i}\in[k]$ such that $r^{(i)}\in Q_{d_{i}}(S_{\ell_{i}})$ . Then we have $\pi_{i,j}((f^{(k)}(r^{(i)}))_{i\in[n]})=(f^{(k)}(r^{(i)})),f^{(k)}(r^{(j)}))=(d_{i},d_{j})$ . On the other hand, when $\ell_{i}\neq\ell_{j}$ , we have $s^{(\ell_{i},\ell_{j})}_{i}=r^{(i)}_{\{\ell_{i},\ell_{j}\}}=d_{i}$ and $s^{(\ell_{i},\ell_{j})}_{j}=r^{(j)}_{\{\ell_{i},\ell_{j}\}}=d_{j}$ , implying that $\pi_{i,j}(s^{(\ell_{i},\ell_{j})})=(d_{i},d_{j})\in\pi_{i,j}(S)$ . Moreover, when $\ell_{i}=\ell_{j}$ , by taking arbitrary $\ell\in[n]\setminus\{\ell_{i}\}$ , we have $s^{(\ell_{i},\ell)}_{i}=r^{(i)}_{\{\ell_{i},\ell\}}=d_{i}$ and $s^{(\ell_{i},\ell)}_{j}=r^{(j)}_{\{\ell_{i},\ell\}}=d_{j}$ , implying that $\pi_{i,j}(s^{(\ell_{i},\ell)})=(d_{i},d_{j})\in\pi_{i,j}(S)$ . Therefore, $\pi_{i,j}((f^{(k)}(r^{(i)}))_{i\in[n]})\in\pi_{i,j}(S)$ for each $i,j$ , and since $S$ is 2-decomposable, we have $(f^{(k)}(r^{(i)}))_{i\in[n]}\in S$ . This completes the proof. ∎

Remark 5.8.

Theorem 5.7 is true even if ${\mathbb{Z}}$ is replaced with any set, since we do not use the property of ${\mathbb{Z}}$ in the proof.

6 Conclusion and future work

We have analyzed the relationship between polyhedral representations of a set of integer vectors and closedness under operations in terms of 2-decomposability. We especially show that the set of integer vectors is representable by a UTVPI system if and only if it is closed under the median operation and the directed discrete midpoint operation. We also characterize 2-decomposability by weak closedness under partial operations.

Investigating other relationship between polyhedral representations and closedness under operations seems an interesting future direction. One candidate would be the relationship between Horn polyhedra (i.e., each inequality has at most one positive coefficient in the defining system) and the minimum operation. It is known that the set of integer vectors in a Horn polyhedron is closed under the minimum operation (see, e.g., [10]), but it is not known whether the converse is true.

Acknowledgments

The authors thank Akihisa Tamura for helpful comments and suggestions to improve presentation of the paper. The first author was partially supported by JST, ACT-X Grant Number JPMJAX200C, Japan, and JSPS KAKENHI Grant Number JP21K17700. The third author was supported by JST CREST Grant Number JPMJCR22M1. The fourth author was supported by WISE program (MEXT) at Kyushu University.

References

[1] Richard Ernest Bellman. On a routing problem. Quarterly Applied Mathematics, 16:87–90, 1958.
[2] Manuel Bodirsky and Marcello Mamino. A polynomial-time algorithm for median-closed semilinear constraints. arXiv: 1808.10068v2, 2018.
[3] Manuel Bodirsky and Marcello Mamino. Tropically convex constraint satisfaction. Theory of Computing Systems, 62:481–509, 2018.
[4] David Cohen, Peter Jeavons, Peter Jonsson, and Manolis Koubarakis. Building tractable disjunctive constraints. Journal of the ACM, 47:826–853, 2000.
[5] Lester Randolph Ford. Network flow theory. Technical report, The Rand Corporation, Santa Monica, 1956.
[6] Alfred Horn. On sentences which are true of direct unions of algebras. The Journal of Symbolic Logic, 16:14–21, 1951.
[7] Peter Jeavons, David Cohen, and Marc Gyssens. A unifying framework for tractable constraints. In Proceedings of the First International Conference on Principles and Practice of Constraint Programming, pages 276–291.
[8] Peter G. Jeavons, David A. Cohen, and Martin C. Cooper. Constraints, consistency and closure. Artificial Intelligence, 101:251–265, 1998.
[9] Peter G. Jeavons and Martin C. Cooper. Tractable constraints on ordered domains. Artificial Intelligence, 79:327–339, 1995.
[10] H. van Maaren and C. Dang. Simplicial pivoting algorithms for a tractable class of integer programs. Journal of Combinatorial Optimization, 6(2):133–142, 2002.
[11] J. C. C. McKinsey. The journal of symbolic logic. Discrete Applied Mathematics, 8:61–76, 1943.
[12] Satoko Moriguchi and Kazuo Murota. Projection and convolution operations for integrally convex functions. Discrete Applied Mathematics, 255:283–298, 2019.
[13] Satoko Moriguchi, Kazuo Murota, Akihisa Tamura, and Fabio Tardella. Scaling, proximity, and optimization of integrally convex functions. Mathematical Programming, 175:119–154, 2019.
[14] Kazuo Murota. Discrete Convex Analysis. Society for Industrial and Applied Mathematics, 2003.
[15] Kazuo Murota and Akihisa Tamura. Recent progress on integrally convex functions. Japan Journal of Industrial and Applied Mathematics, 40:1445–1499, 2023.
[16] R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, New Jersey, USA, 1970.
[17] Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th annual ACM Symposium on Theory of Computing, pages 216–226, 1978.
[18] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons Ltd, Chichester, 1986.
[19] Akihisa Tamura and Kazuya Tsurumi. Directed discrete midpoint convexity. Japan Journal of Industrial and Applied Mathematics, 38:1–37, 2021.
[20] Robert J. Vanderbei. Linear Programming: Foundations and Extensions. Springer, fifth edition, 2020.

Appendix

A More Direct Proof of Lemma 4.13 in Subsection 4.2

Our proof of Lemma 4.13 in Subsection 4.2 heavily relies on previous work, but we provide a more direct proof here for readability of the paper.

Lemma 4.13.

Let $S$ be a subset of $\mathbf{Z}^{2}$ . If $S$ is $\mu$ -closed, then $S$ is representable by a UTVPI system.

Basic observations

Lemma 6.1.

Let $S$ be a subset of $\mathbb{Z}^{2}$ . If $S$ is representable by a UTVPI system, then so are the following sets:

(i)

the reflection of $S$ over the $x_{1}$ -axis, i.e., $\{(x_{1},-x_{2})\,:\,(x_{1},x_{2})\in S\}$ ,
(ii)

the reflection of $S$ over the $x_{2}$ -axis, i.e., $\{(-x_{1},x_{2})\,:\,(x_{1},x_{2})\in S\}$ ,
(iii)

the reflection of $S$ over the line $x_{1}=x_{2}$ , i.e., $\{(x_{2},x_{1})\,:\,(x_{1},x_{2})\in S\}$ ,
(iv)

the reflection of $S$ over the line $x_{1}=-x_{2}$ , i.e., $\{(-x_{2},-x_{1})\,:\,(x_{1},x_{2})\in S\}$ , and
(v)

the translation of $S$ by an integer vector $(a_{1},a_{2})$ , i.e., $\{(x_{1}+a_{1},x_{2}+a_{2})\,:\,(x_{1},x_{2})\in S\}$ .

Proof.

Since $S$ is represented by a UTVPI system, there exist a unit quadratic matrix $A$ and a vector $b$ such that $S=\{x\in\mathbb{Z}^{2}\,:\,Ax\geq b\}$ . We use the fact that for a surjection $f:\mathbb{Z}^{2}\to\mathbb{Z}^{2}$ , if there exist a matrix $A^{\prime}$ and a vector $b^{\prime}$ such that $Ax\geq b$ if and only if $A^{\prime}f(x)\geq b^{\prime}$ for $x\in\mathbb{Z}^{2}$ , then the image $f(S)$ is equal to $\{x\in\mathbb{Z}^{2}\,:\,A^{\prime}x\geq b^{\prime}\}$ . In fact, for any $y\in f(S)$ there exists an element $x\in S$ such that $f(x)=y$ , and since $Ax\geq b$ if and only if $A^{\prime}y\geq b^{\prime}$ , we have $y\in\{x\in\mathbb{Z}^{2}\,:\,A^{\prime}x\geq b^{\prime}\}$ . Conversely, for any $y\in\{x\in\mathbb{Z}^{2}\,:\,A^{\prime}x\geq b^{\prime}\}$ , since $f$ is surjective there exists an $x\in\mathbb{Z}^{2}$ such that $f(x)=y$ . Now, since $Ax\geq b$ if and only if $A^{\prime}y\geq b^{\prime}$ , this $x$ is in $S$ which means $y\in f(S)$ . Using this fact, we show the lemma as follows.

(i)

Let $A_{1}$ be a unit quadratic matrix whose the first column is the same as that of $A$ and the second column is $(-1)$ times that of $A$ . Then clearly $A\binom{x_{1}}{x_{2}}\geq b$ if and only if $A_{1}\binom{x_{1}}{-x_{2}}\geq b$ , and thus, $\{x\in\mathbb{Z}^{2}\,:\,A_{1}x\geq b\}$ is a UTVPI representation of the reflection of $S$ over the $x_{1}$ -axis.
(ii)

Let $A_{2}$ be a unit quadratic matrix whose the first column is $(-1)$ times that of $A$ and the second column is the same as that of $A$ . Then clearly $A\binom{x_{1}}{x_{2}}\geq b$ if and only if $A_{2}\binom{-x_{1}}{x_{2}}\geq b$ , and thus, $\{x\in\mathbb{Z}^{2}\,:\,A_{2}x\geq b\}$ is a UTVPI representation of the reflection of $S$ over the $x_{2}$ -axis.
(iii)

Let $A_{3}$ be a unit quadratic matrix obtained by permuting the first and second column of $A$ . Then clearly $A\binom{x_{1}}{x_{2}}\geq b$ if and only if $A_{3}\binom{x_{2}}{x_{1}}\geq b$ , and thus, $\{x\in\mathbb{Z}^{2}\,:\,A_{3}x\geq b\}$ is a UTVPI representation of the reflection of $S$ over the line $x_{1}=x_{2}$ .
(iv)

Since the reflection of $S$ over the line $x_{1}=-x_{2}$ can be obtained by a sequence of the reflection over the line $x_{1}=x_{2}$ , the reflection over the $x_{1}$ -axis, and the reflection over the $x_{2}$ -axis, the reflection of $S$ over the line $x_{1}=-x_{2}$ is representable by a UTVPI system by (i)-(iii).
(v)

Since $A\binom{x_{1}}{x_{2}}\geq b$ if and only if $A\binom{x_{1}+a_{1}}{x_{2}+a_{2}}\geq b+A\binom{a_{1}}{a_{2}}$ , $\{x\in\mathbb{Z}^{2}\,:\,Ax\geq b+A\binom{a_{1}}{a_{2}}\}$ is a UTVPI representation of the translation of $S$ by $(a_{1},a_{2})$ .

∎

Lemma 6.2.

Let $S$ be a subset of $\mathbb{Z}^{2}$ . If $S$ is $\mu$ -closed, then so are the following sets:

(i)

the reflection of $S$ over the $x_{1}$ -axis, i.e., $\{(x_{1},-x_{2})\,:\,(x_{1},x_{2})\in S\}$ ,
(ii)

the reflection of $S$ over the $x_{2}$ -axis, i.e., $\{(-x_{1},x_{2})\,:\,(x_{1},x_{2})\in S\}$ ,
(iii)

the reflection of $S$ over the line $x_{1}=x_{2}$ , i.e., $\{(x_{2},x_{1})\,:\,(x_{1},x_{2})\in S\}$ ,
(iv)

the reflection of $S$ over the line $x_{1}=-x_{2}$ , i.e., $\{(-x_{2},-x_{1})\,:\,(x_{1},x_{2})\in S\}$ , and
(v)

the translation of $S$ by an integer vector $(a_{1},a_{2})$ , i.e., $\{(x_{1}+a_{1},x_{2}+a_{2})\,:\,(x_{1},x_{2})\in S\}$ .

Proof.

We use the easy-to-prove fact that if a map $f:\mathbb{Z}^{2}\to\mathbb{Z}^{2}$ satisfies $\mu(f(x),f(y))=f(\mu(x,y))$ for $x,y\in\mathbb{Z}^{2}$ , then the image $f(S)$ is also $\mu$ -closed. In fact, for all $x^{\prime},y^{\prime}\in f(S)$ there exist $x,y\in S$ such that $f(x)=x^{\prime},f(y)=y^{\prime}$ . Since $S$ in $\mu$ -closed, $\mu(x,y)\in S$ , and thus, $\mu(x^{\prime},y^{\prime})=\mu(f(x),f(y))=f(\mu(x,y))\in f(S)$ .

(i)

Since $\lfloor-a\rfloor=-\lceil a\rceil$ for $a\in\mathbb{R}$ , $\mu(-x,-y)=-\mu(x,y)$ for $x,y\in\mathbb{Z}$ . Thus, we have $\mu(\binom{x_{1}}{-x_{2}},\binom{y_{1}}{-y_{2}})=\binom{\mu(x_{1},y_{1})}{-\mu(x_{2},y_{2})}$ . Hence the reflection of $S$ over the $x_{1}$ -axis is also $\mu$ -closed.
(ii)

This can be similarly proven as (i).
(iii)

This is followed by $\mu(\binom{x_{2}}{x_{1}},\binom{y_{2}}{y_{1}})=\binom{\mu(x_{2},y_{2})}{\mu(x_{1},y_{1})}$ .
(iv)

The reflection of $S$ over the $x_{1}=-x_{2}$ is a composition of the reflection of $S$ over the $x_{1}$ -axis, the $x_{2}$ -axis, and the line $x_{1}=x_{2}$ . Thus, it follows from (i)-(iii).
(v)

It follows from $\mu(\binom{x_{1}+a_{1}}{x_{2}+a_{2}},\binom{y_{1}+a_{1}}{y_{2}+a_{2}})=\mu(\binom{x_{1}}{x_{2}},\binom{y_{1}}{y_{2}})+\binom{a_{1}}{a_{2}}$ .

∎

Another proof of Lemma 4.13

Given the basic observations in Basic observations, we are ready to prove Lemma 4.13 in a more self-contained manner.

Proof of Lemma 4.13.

Assume that $S$ is $\mu$ -closed. By Proposition 2.20, it suffices to show that $S$ is integrally convex. Let $x\in{\rm cl}_{{\rm conv}}(S)$ . We show $x\in{\rm cl}_{{\rm conv}}(S\cap N(x))$ in the following. By Carathéodory’s theorem there exist three elements $t_{1},t_{2},t_{3}\in S$ such that $x\in{\rm cl}_{{\rm conv}}(\{t_{1},t_{2},t_{3}\})$ .

Now we will show the $\mu$ -closure ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})$ of $\{t_{1},t_{2},t_{3}\}$ is equal to the UTVPI hull ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ of it. First we show a similar equality for two-point case, i.e., ${\rm cl}_{\mu}(\{t_{1},t_{2}\})={\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ . By Corollary 4.11, ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ is included in ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ . If a line $\ell$ through $t_{1},t_{2}$ is parallel to $x_{1}$ -axis, $x_{2}$ -axis, the line $x_{1}=x_{2}$ , or the line $x_{1}=-x_{2}$ , it is clear that ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ consists of all integer points between $t_{1}$ and $t_{2}$ on $\ell$ and ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ is also the same set, and thus, ${\rm cl}_{\mu}(\{t_{1},t_{2}\})={\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ . If not, from Lemma 6.1 and Lemma 6.2, by reflecting and translating ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ and ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ appropriately, it suffices to show the case of $t_{1}=(0,0)$ and $t_{2}=(p,q)$ where $q>p>0$ . In this case, ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ consists integer points $(x_{1},x_{2})$ that satisfy

0\leq x_{1}\leq p,x_{1}\leq x_{2}\leq x_{1}+q-p.

By ${\rm cl}_{\mu}(\{t_{1},t_{2}\})\subseteq{\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ , all points in ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ also satisfy these inequalities.

First we will show $(0,q-p)\in{\rm cl}_{\mu}(\{t_{1},t_{2}\})$ . If we show some point $(0,r)$ is in ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ where $0<r\leq q-p$ , we retake $t_{1}=(0,r),t_{2}=(p,q)$ and by induction on $q$ , we have $(0,q-p)\in{\rm cl}_{\mu}(\{t_{1},t_{2}\})$ . And if we show there exists $(\tilde{p},\tilde{q})\in{\rm cl}_{\mu}(\{t_{1},t_{2}\})$ that satisfies $\tilde{q}>\frac{q}{p}\tilde{p}$ , then, since $\tilde{p}<p$ , by induction on $p$ , we have $(0,r)\in{\rm cl}_{\mu}(\{t_{1},t_{2}\})$ . Thus, we will show that such $(\tilde{p},\tilde{q})$ is in ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ . When $p,q$ are both even, $\mu(p,q)=(\frac{p}{2},\frac{q}{2})\in{\rm cl}_{\mu}(\{t_{1},t_{2}\})$ and by repeating halving the point, we have a $(p^{\prime},q^{\prime})\in{\rm cl}_{\mu}(\{t_{1},t_{2}\})$ such that at least one of $p^{\prime}$ or $q^{\prime}$ is odd number. First we consider the case when $p^{\prime}$ is odd. Then $\mu((0,0),(p^{\prime},q^{\prime}))=(\frac{p^{\prime}}{2}-\frac{1}{2},\lfloor\frac{q^{\prime}}{2}\rfloor)$ and

\lfloor\frac{q^{\prime}}{2}\rfloor\geq\frac{q^{\prime}}{2}-\frac{1}{2}=\frac{q}{p}(\frac{p^{\prime}}{2}-\frac{1}{2})+\frac{1}{2}(\frac{q}{p}-1)>\frac{q}{p}(\frac{p^{\prime}}{2}-\frac{1}{2})

which means we obtain desirable $(\tilde{p},\tilde{q})=(\frac{p^{\prime}}{2}-\frac{1}{2},\lfloor\frac{q^{\prime}}{2}\rfloor)$ . Otherwise; $p^{\prime}$ is even and $q^{\prime}$ is odd, and $\mu((p^{\prime},q^{\prime}),(0,0))=(\frac{p^{\prime}}{2},\frac{q^{\prime}}{2}+\frac{1}{2})$ . Here

\frac{q^{\prime}}{2}+\frac{1}{2}>\frac{q}{p}\cdot\frac{p^{\prime}}{2}

and we again obtain desirable $(\tilde{p},\tilde{q})=(\frac{p^{\prime}}{2},\frac{q^{\prime}}{2}+\frac{1}{2})$ . Hence $(0,q-p)$ is in ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ . Now, $(p,p)$ is also in ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ , since it is obtained by translating $(0,q-p)$ by $(-p,-q)$ and reflect it over $x_{1}$ -axis and $x_{2}$ -axis. Thus, all vertices of ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ is in ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ . Now, since the boundary of ${\rm cl}_{{\rm UTVPI}}$ is parallel to $x_{1}$ -axis, $x_{2}$ -axis, the line $x_{1}=x_{2}$ , or the line $x_{1}=-x_{2}$ , all points on the boundaries are in ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ . Finally, any inner point $(x_{1},x_{2})\in{\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ lies on the line segment that connects $(x_{1},x_{1})$ and $(x_{1},x_{1}+q-p)$ which are on the boundaries, implying that $(x_{1},x_{2})$ is in ${\rm cl}_{\mu}(\{t_{1},t_{2}\})$ . Therefore, we have ${\rm cl}_{\mu}(\{t_{1},t_{2}\})={\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2}\})$ .

Next, we show ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})={\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ . By Corollary 4.11, ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})\subseteq{\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ , and by the same argument of the two points case, it is enough to show any vertex $v$ of ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ is in ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})$ . When $v$ coincides with one of $t_{1},t_{2},t_{3}$ , $v$ is trivially in ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})$ . Thus, we assume $v$ equals none of $t_{1},t_{2},t_{3}$ . If necessary, by retaking the indexes of $t_{1},t_{2},t_{3}$ , $v$ is the intersection of boundary through $t_{1}$ and that through $t_{2}$ . Let $\theta$ be the angle between the two boundaries. Then, $\theta$ is one of $\frac{1}{4}\pi,\frac{1}{2}\pi,$ or $\frac{3}{4}\pi$ , but we show that $\theta$ must be $\frac{3}{4}\pi$ . In fact, assume $\theta=\frac{1}{4}\pi$ . By Lemma 6.1 and Lemma 6.2, we may assume $v=(0,0)$ , $t_{1}$ lies on the positive part of $x_{1}$ -axis, and $t_{2}$ lies on the line $x_{1}=x_{2}$ and is in the first quadrant. Then, $t_{1},t_{2},t_{3}$ satisfy $x_{1}\geq 1$ , and thus, $v=(0,0)$ is not in ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ , a contradiction. Moreover, let $\theta=\frac{1}{2}\pi$ . Again we may assume (i) $v=(0,0)$ , and $t_{1}$ and $t_{2}$ lie on the positive parts of $x_{1}$ -axis and $x_{2}$ -axis, respectively or (ii) $v=(0,0)$ , $t_{1}$ lies on the line $x_{1}=x_{2}$ and is in the first quadrant, and $t_{2}$ lies on the line $x_{1}=-x_{2}$ and is in the forth quadrant. In case (i) $t_{1},t_{2},t_{3}$ satisfy $x_{1}+x_{2}\geq 1$ , in case (ii) $t_{1},t_{2},t_{3}$ satisfy $x_{1}\geq 1$ , and thus, in both cases $v=(0,0)$ is not in ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ , a contradiction. Hence $\theta=\frac{3}{4}\pi$ . We assume $v=(0,0)$ , $t_{1}=(a,0)$ , and $t_{2}=(-b,b)$ where $a,b$ are positive integers. Then by the case of two points, $v=(0,0)\in{\rm cl}_{\mu}(\{t_{1},t_{2}\})\subseteq{\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})$ . Therefore, all vertices of ${\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ are in ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})$ . Therefore, we have ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})={\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ .

Now $x\in{\rm cl}_{{\rm conv}}(\{t_{1},t_{2},t_{3}\})\subseteq{\rm cl}_{{\rm conv}}({\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\}))$ . By ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})={\rm cl}_{{\rm UTVPI}}(\{t_{1},t_{2},t_{3}\})$ and Proposition 2.20, ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})$ is integrally convex and thus $x\in{\rm cl}_{{\rm conv}}({\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})\cap N(x))$ . Since $S$ is $\mu$ -closed, ${\rm cl}_{\mu}(\{t_{1},t_{2},t_{3}\})\subseteq S$ and thus $x\in{\rm cl}_{{\rm conv}}(S\cap N(x))$ . Therefore, $S$ is integrally convex. ∎

Characterizing the integer points in 2-decomposable polyhedra by closedness under operations

Abstract

1 Introduction

Related work

Outline

2 Preliminaries

Definition 2.1 (2-decomposability [8]).

Definition 2.2 (Closedness under operation).

Definition 2.3.

Definition 2.4.

Definition 2.5.

Definition 2.6.

Definition 2.7.

Theorem 2.8.

Definition 2.9 (Polyhedron).

Definition 2.10.

Definition 2.11.

Definition 2.12 (Representability).

Definition 2.13.

Proposition 2.14 ([2, Theorem 3.2]).

Remark 2.15.

Definition 2.16 (Integer neighborhood).

Definition 2.17 (Midpoint-neighbor-closedness).

Definition 2.18 (Integral convexity).

Theorem 2.19 (Theorem 2.1 in [15]).

Proposition 2.20 (Proposition 2.1 in [13]).

3 2-decomposability and closure properties

Lemma 3.1.

Proof.

Lemma 3.2.

Proof.

Theorem 3.3 (2-decomposability and general closure property).

Proof.

Theorem 3.4 (2-decomposability and closure property induced by operations).

Proof.

Theorem 3.5 (2-decomposability and closure property induced by special operations).

Proof.

Remark 3.6.

Theorem 3.7 (2-decomposability and closure property induced by clconv¯​(⋅)∩ℤn{\rm cl}_{\overline{{\rm conv}}}(\cdot)\cap\mathbb{Z}^{n}).

Proof.

Proposition 3.8 (Hierarchy of closedness in 2-dimension).

Proof.

4 Polyhedral representation and closedness under operations

4.1 Main results

Theorem 4.1.

Proof.

Proposition 4.2.

Proof.

Proposition 4.3.

Proof.

Remark 4.4.

Remark 4.5.

Remark 4.6.

4.2 Remaining proofs

Lemma 4.7.

Proof.

Example 4.8.

Theorem 4.9.

Proposition 4.10.

Proof.

Case 1: Ai​x=xj+xkA_{i}x=x_{j}+x_{k}.

Case 1.1: pj+qjp_{j}+q_{j} and pk+qkp_{k}+q_{k} are even.

Case 1.2: pj+qjp_{j}+q_{j} is even and pk+qkp_{k}+q_{k} is odd.

Case 1.3: pj+qjp_{j}+q_{j} is odd and pk+qkp_{k}+q_{k} is even.

Case 1.4: pj+qjp_{j}+q_{j} and pk+qkp_{k}+q_{k} are odd.

Case 2: Ai​x=xj−xkA_{i}x=x_{j}-x_{k}.

Corollary 4.11.

Proof.

Example 4.12.

Lemma 4.13.

Proof.

Proposition 4.14.

Proof.

Proof of Theorem 4.9.

4.3 TVPI representability cannot be characterized by median-closedness

Example 4.15.

5 Characterizing 2-decomposability

Definition 5.1 (Partial operation).

Definition 5.2.

Definition 5.3.

Theorem 3.7 (2-decomposability and closure property induced by ${\rm cl}_{\overline{{\rm conv}}}(\cdot)\cap\mathbb{Z}^{n}$ ).

Case 1: $A_{i}x=x_{j}+x_{k}$ .

Case 1.1: $p_{j}+q_{j}$ and $p_{k}+q_{k}$ are even.

Case 1.2: $p_{j}+q_{j}$ is even and $p_{k}+q_{k}$ is odd.

Case 1.3: $p_{j}+q_{j}$ is odd and $p_{k}+q_{k}$ is even.

Case 1.4: $p_{j}+q_{j}$ and $p_{k}+q_{k}$ are odd.

Case 2: $A_{i}x=x_{j}-x_{k}$ .