Partition Regular Systems

of Linear Inequalities

Meike Schäffler^{1}

Received: Nov. 5, 1997 Revised: July 24, 1998

Communicated by Günter M. Ziegler

Introduction

In 1930 Ramsey published his paper On a problem in formal logic [12]. He established a result, nowadays known as Ramsey’s Theorem:

Let k and r be positive integers. Then for every r-coloring of the k-element subsets of ω there exists an infinite subset S ⊆ ω such that all k-element subsets of S are colored the same.

Already in 1927 van der Waerden published his theorem on arithmetic progressions [15]. He proved that for every coloring of the natural numbers with finitely many colors there exists a monochromatic arithmetic progression of given length. Van der Waerden’s result can be seen in the context of Schur’s investigations [14] on the distribution of quadratic residues and nonresidues. Schur knew about the existence of monochromatic solutions of x + y = z. He worked on such problems in order to resolve Fermat’s conjecture, which was proved by Wiles in 1994.

The above mentioned work of Ramsey [12] and van der Waerden [15] gave rise to the part of discrete mathematics, known as Ramsey Theory or Partition Theory. An important contribution was made by Rado [10] in 1933. Working on his dissertation, supervised by Schur, he was able to prove a common generalization of Schur’s and van der Waerden’s results by introducing the concept of regularity: A system of linear equations Ax⃗ = 0 is called regular over a ring R if it has monochromatic solutions for every coloring of R with finitely many colors. In his Studien zur Kombinatorik (1933) [10] Rado gave a complete characterization of all regular systems of linear equations over the rational numbers. The property Rado used in order to describe regular systems of linear equations is an syntactical property of the matrix. It is characterized by certain linear dependences of the columns of the matrix A and is called column property.

1For this work, the author has been awarded with the Richard-Rado-Preis 1998, which is granted every two years for outstanding dissertations in discrete mathematics by the Fachgruppe Diskrete Mathematik of the Deutsche Mathematiker-Vereinigung.

Documenta Mathematica 3 (1998) 149–187

It is possible to generalize the concept of regularity to systems of linear inequalities. We call a system of linear inequalities Ax⃗ ≤ 0 partition regular if for every coloring of the natural numbers with finitely many colors there exists a monochromatic solution of Ax⃗ ≤ 0. Rado considered systems of linear inequalities only incidentally. He stated the following proposition which is easy to prove:

Let the system ∑_{j=1}^{n} a_{ij}x_{j} = 0, 1 ≤ i ≤ m be partition regular and assume that the following system of inequalities has a solution in the natural numbers:

(∗) ∑_{j=1}^{n} a_{ij}x_{j} \{ \begin{matrix}= 0 & for & 1 ≤ i ≤ m_{1}, \\ > 0 & for & m_{1} < i ≤ m. \end{matrix}

Then also (∗) is partition regular.

Of course this observation is far away from being a characterization of partition regular systems of inequalities but it can be taken as a starting point for our investigations.

The characterization of all partition regular systems of linear inequalities is a central goal of this paper. In the first chapter we define a generalized column property called cpi, which can be used to characterize partition regular systems of linear inequalities. It is an interesting feature of Rado’s proof that the linear system Ax⃗ = 0 is already regular if there exists a monochromatic solution with respect to one (number theoretic) type of coloring. Systems of inequalities let things tend to be more difficult.

Several years after finishing his Studien zur Kombinatorik, Rado [11] considered systems of linear equations with coefficients in ℝ and he also extended the set of partitioned numbers to the field of real numbers. It turned out that it is possible to carry over the previous results from the natural numbers to the reals. We will show in chapter 1 that our arguments can also be used if we consider real systems of inequalities partitioning the set of reals.

As well as for homogeneous systems the column property can be used to describe partition regularity of inhomogeneous systems of inequalities. We will give a complete characterization of those systems which are partition regular, over the natural numbers, over the set of integers and over the rationals.

The column property for systems of inequalities as well as the column property in the sense of Rado is a syntactical property of the matrix and does not explicitly refer to the set of solutions of the system. In 1973 Deuber [1] gave a semantical characterization of partition regular systems of equations. The approach is by a description of the arithmetic structure of the sets of solutions of regular linear systems Ax⃗ = 0. The central notion is the one of (m, p, c)−sets. He proved the following theorem:

A system Ax⃗ = 0 is partition regular if and only if there exist positive integers m, p, c such that every (m, p, c)−set contains a solution of Ax⃗ = 0.

In chapter two we will show that (m, p, c)−sets can also be used to characterize solution spaces of partition regular systems of linear inequalities.

Starting with results of Erdös and Rado [4] another part of partition theory was developed, which is nowadays known as Canonical Ramsey Theory. In Canonical Ramsey Theory one considers colorings with no restriction on the number of colors. The first result is a canonical version of Ramsey’s theorem. Later Erdös and Graham [3] proved a generalization of van der Waerden’s theorem:

For every coloring Δ of the natural numbers with arbitrary many colors there exists an arithmetic progression, which is colored monochromatic or injective with respect to Δ.

A canonical analogue of the Rado-Deuber-Theorem on regular systems of equations and (m, p, c)-sets was proved by Lefman [7]. His result states:

Let Ax⃗ = 0 be a partition regular system of linear equations. For every coloring Δ of the natural numbers with arbitrary many colors there exists a solution of the system Ax⃗ = 0 such that Δ restricted to this solution is either monochromatic, injective or a block-coloring.

The third case is related to the partitioning of the columns of A into blocks, corresponding to the column property and to the rows of the (m, p, c)-sets. In chapter 3. we prove a canonical partition theorem for systems of inequalities.

Acknowledgment: I would like to thank Prof. Dr. Walter Deuber for his encouragement and guidance and Dr. Wolfgang Thumser for helpful discussions.

1. Systems of Homogeneous, Linear Inequalities

Notations By ℕ = {1, 2, 3, …} we denote the set of positive integers; [n] = {1, 2, …, n} is the set of the natural numbers less or equal than n. A matrix A with m rows and n columns is denoted by A = (a_{ij})_{1≤i≤m,1≤j≤n}, where a_{ij} is the entry of A which belongs to the ith row and jth column. For i, j ≤ n the jth column of a matrix A is denoted by a^{(j)} the ith row by a_{(i)}. For a matrix A = (a_{ij})_{1≤i≤m,1≤j≤n} the system

∑_{j=1}^{n} a_{ij}x_{j} ≤ 0, 1 ≤ i ≤ m

is abbreviated as Ax⃗ ≤ 0. For a given matrix A = (a_{ij})_{1≤i≤m,1≤j≤n}, k ≤ n and ϵ > 0 by A^{k}(ϵ) = (a_{ij}^{k}(ϵ))_{1≤i≤m,1≤j≤n} we denote the following matrix:

( \begin{matrix}a_{11} & … & a_{1k−1} & a_{1k} − ϵ & a_{1k+1} & … & a_{1n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{m1} & … & a_{mk−1} & a_{mk} − ϵ & a_{mk+1} & … & a_{mn} \end{matrix} ) ,

obtained from A by subtracting ϵ in column k.

For k, l ∈ [n], k < l and ϵ > 0 the matrix

( \begin{matrix}a_{11} & … & a_{1k−1} & a_{1k} − ϵ & a_{1k+1} & … & a_{1l−1} & a_{1l+1} & … & a_{1n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{m1} & … & a_{mk−1} & a_{mk} − ϵ & a_{mk+1} & … & a_{ml−1} & a_{ml+1} & … & a_{mn} \end{matrix} )

obtained by deleting column l in A^{k}(ϵ), is denoted by A_{l}^{k}(ϵ) and the matrix

( \begin{matrix}a_{11} & … & a_{1k−1} & a_{1k} + a_{1l} − ϵ & a_{1k+1} & … & a_{1l−1} & a_{1l+1} & … & a_{1n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{m1} & … & a_{mk−1} & a_{mk} + a_{ml} − ϵ & a_{mk+1} & … & a_{ml−1} & a_{ml+1} & … & a_{mn} \end{matrix} ) ,

obtained from A^{k}(ϵ) by adding the kth and the lth column, is denoted by A^{(k)+(l)}(ϵ).

Rado considered systems of linear equations over ℚ. In his paper, published in 1933 [10], Rado gives a characterization of all systems of linear homogeneous equations which have for every coloring of the natural numbers with finitely many colors a solution in one color class. Rado called those systems regular. The central definition in this context is the following:

Definition 1.1. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a matrix with m rows an n columns and with entries a_{ij} ∈ ℤ. A has the column property if there exists l ∈ ℕ and a partition [n] = I_{0} ∪ I_{1} ∪ … I_{l} of the column indices such that

1. for all 1 ≤ i ≤ m we have ∑_{j∈I_{0}} a_{ij} = 0 and

2. for all k < l, j ∈ ∪_{s≤k}I_{s} there exist c_{k}, c_{kj} ∈ ℕ such that for all 1 ≤ i ≤ m we

have

∑_{j∈∪_{s≤k}I_{s}} c_{jk}a_{ij} + c_{k} ∑_{j∈I_{k+1}} a_{ij} = 0.

Rado proved the following theorem:

Theorem 1.1. (Rado 1933) A system of homogeneous linear equations Ax⃗ = 0 is regular if and only if A has the column property.

In the following we will consider systems of linear inequalities rather than systems of linear equations. First we define partition regularity for systems of inequalities.

Definition 1.2. Let A = (a_{ij})_{1≤i≤m1≤j≤n} be a rational matrix and let b⃗ = (b_{1}, …, b_{m}) ∈ ℚ^{m}. The system

(∗)  ∑_{j=1}^{n} a_{ij}x_{j} ≤ b_{i}, 1 ≤ i ≤ m

is called partition regular over ℕ if for every c ∈ ℕ and every c-coloring of the natural numbers Δ : ℕ → [c] there exists a solution x⃗ = (x_{1}, … x_{n}) ∈ ℕ^{n} of (∗) such that Δ |_{{x_{1},...,x_{n}}} = const.

In the following section we will give a characterization of all systems of homogeneous linear inequalities which are partition regular over ℕ. It turns out that a natural generalization of Rado’s column property can be used to describe these systems.

Definition 1.3. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix. A has the column property for systems of inequalities (abbreviated as cpi ) over ℕ if there exists l ∈ ℕ and a partition [n] = I_{0} ∪ I_{1} … ∪ I_{l} such that

1. for all 1 ≤ i ≤ m we have ∑_{j∈I_{0}} a_{ij} ≤ 0 and

2. for all k < l, j ∈ ∪_{s≤k}I_{s} there exist c_{k}, c_{jk} ∈ ℕ such that for all 1 ≤ i ≤ m we

have

∑_{j∈∪_{s≤k}I_{s}} c_{kj}a_{ij} + c_{k} ∑_{j∈I_{k+1}} a_{ij} ≤ 0.

If a matrix A has the column property (in the sense of Rado) [10] the system Ax⃗ ≤ 0 obviously is partition regular. But there are many other systems of inequalities which are partition regular without A having Rado’s column property. For example the matrix

( \begin{matrix}−1 & 0 & 0 \\ −1 & 0 & 0 \end{matrix} )

has cpi but not the column property.

Theorem 1.2. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix. The system of inequalities (∗) Ax⃗ ≤ 0 is partition regular over ℕ if and only if A has cpi over ℕ.

Both implications stated in theorem 1.5. are not completely trivial to prove. We start by showing that cpi implies partition regularity. This part of the proof proceeds along the general lines of the corresponding proof for systems of equations [10]. The following lemma combines arithmetic progressions and partition regular systems of linear inequalities:

Lemma 1.1. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix, Ax⃗ ≤ 0 a partition regular system of inequalities and let p ∈ ℕ. Then for every c ∈ ℕ and every ccoloring Δ : ℕ → [c] there exists x⃗ = (x_{1}, …, x_{n}) ∈ ℕ^{n} and d ∈ ℕ such that

1. Ax⃗ ≤ 0 and

2. for all i, j ≤ n, for all k, l ≤ p we have Δ(x_{i} + ld) = Δ(x_{j} + kd).

Proof of lemma 1.1.: Ax⃗ ≤ 0 is partition regular. Thus by compactness [6] for every c ∈ ℕ there exists N^{∗} = N^{∗}(c) ∈ ℕ such that for every c-coloring Δ : [N^{∗}] → [c] there exists a monochromatic solution x⃗ = (x_{1} … x_{n}) of Ax⃗ ≤ 0 such that for all 1 ≤ i ≤ n we have x_{i} ≤ N^{∗}.

Let Δ : ℕ → [c] be an arbitrary c-coloring. Define the following coloring Δ^{∗} : ℕ → [r^{N^{∗}}] by

Δ^{∗}(x) = (Δ(ix))_{1≤i≤N^{∗}}.

By van der Waerden’s theorem [15] there exists a “long” arithmetic progression which is monochromatic with respect to Δ^{∗}, i. e. there exist a′, d′ ∈ ℕ such that for all l ≤ pN^{∗^{n−1}} we have Δ^{∗}(a′ + ld′) =const. Define Δ^{∗∗} : ℕ → [c] by

Δ^{∗∗}(x) = Δ(a′x).

By the choice of N^{∗} there exists a solution x⃗′ = (x′_{1}, …, x′_{n}) ∈ [N^{∗}]^{n} of Ax⃗ ≤ 0 which is monochromatic for Δ^{∗}. For all i ≤ n let x_{i} = x′_{i}a′. By homogeneity x⃗ = (x_{1}, … x_{n}) is a solution of Ax⃗ ≤ 0 and because of the definition of Δ^{∗∗} for all i, j ≤ n we have Δ(x_{i}a′) = Δ(x_{j}a′). Let d = d′x′_{1} … x′_{n}. Then for i ≤ n and l ≤ p we have:

x′_{i}a′ + ld = x′_{i}(a′ + ld′x′_{1} … x′_{i−1}x′_{i+1} … x′_{n}).

Hence by the definition of a′, d′ and Δ^{∗} for all l ≤ p we have Δ(x′_{i}a′ + ld) =const. □_{lemma 1.6.}

Proof of theorem 1.2. (first part): First we show that if A has cpi over ℕ then (∗) is partition regular. We know by assumption that there is some l ∈ ℕ and a partition [n] = I_{0} ∪ I_{1} ∪ … ∪ I_{l} such that

1. for all 1 ≤ i ≤ m we have ∑_{j∈I_{0}} a_{ij} ≤ 0 and

2. for all k < l, for all j ∈ ∪_{s≤k}I_{s} there exist c_{kj}, c_{k} ∈ ℕ, such that for all 1 ≤ i ≤ m

we have

∑_{j∈∪_{s≤k}I_{s}} c_{kj}a_{ij} + c_{k} ∑_{j∈I_{k+1}} a_{ij} ≤ 0.

To prove that (∗) is partition regular we will use a double induction. We proceed by main induction on the number of colors c and by subsidiary induction on l, the number of column classes.

Let A_{k} = (a_{ij})_{1≤i≤m,j∈∪_{s≤k}I_{s}} be the submatrix of A which only consists of the columns belonging to block 1 up to k. We will show by induction that for all k ≤ l A_{k} is partition regular.

For k = 0 there is nothing to show because every singleton forms a solution of the system A_{0}x⃗ ≤ 0. Assume that A_{k}x⃗ ≤ 0 is partition regular for some k ≥ 0 (which will be kept fix by now), i. e. (by compactness) for every c ∈ ℕ there exists R(c, A_{k}) ∈ ℕ such that for every c-coloring Δ : [R(c, A_{k})] → [c] there exists a monochromatic solution (x_{j})_{j∈∪_{s≤k}I_{s}}, such that A_{k}x⃗ ≤ 0 and for all j ∈ ∪_{s≤k}I_{s} we have x_{j} ≤ R(c, A_{k}). We will show that A_{k+1} is partition regular, i. e. for all c ∈ ℕ there exists R(c, A_{k+1}) ∈ ℕ First we observe that x_{j} = c_{jk} for j ∈ ∪_{s≤k}I_{s} and x_{j} = c_{k} for j ∈ I_{k+1} form a solution of the system A_{k+1}x⃗ ≤ 0. So we are done if only one color is used for the coloring, i. e. there exists R(1, A_{k+1}). Now assume that R(c, A_{k+1}) exists for some (fixed) c ≥ 1. We will show that R(c + 1, A_{k+1}) exists.

Let Δ : ℕ → [c + 1] be an arbitrary (c+1)-coloring. Use lemma 1.6. for the (by assumption) partition regular system A_{k}x⃗ ≤ 0 with p = R(c, A_{k+1}) · (max_{j∈∪_{s≤k}I_{s}}{c_{kj}}). Hence there exists (y_{j})_{j∈∪_{s≤k}I_{s}}, such that for all 1 ≤ i ≤ m we have

∑_{j∈∪_{s≤k}I_{s}} a_{ij}y_{j} ≤ 0

and there exists d ∈ ℕ such that for all j ∈ ∪_{s≤k}I_{s} and t ≤ p we have

Δ(y_{j} + td) = const.

for all 1 ≤ i ≤ m and t ∈ [R(c, A_{k+1})] it follows

\begin{aligned}& ∑_{j∈∪_{s≤k}I_{s}}(y_{j} + c_{kj}td)a_{ij} + ∑_{j∈I_{k+1}} c_{k}tda_{ij} \\ = & ∑_{j∈∪_{s≤k}I_{s}} y_{j}a_{ij} + td( ∑_{j∈∪_{s≤k}I_{s}} c_{kj}a_{ij} + c_{k} ∑_{j∈I_{k+1}} a_{ij}) & ≤ 0. \end{aligned}

Further for all j ∈ ∪_{s≤k}I_{s} and t ≤ p we have

Δ(y_{j} + c_{kj}td) = const.

Say Δ(y_{j} + c_{kj}td) = c + 1.

We distinguish the following cases:

1. There exist t ∈ [R(c, A_{k+1})] such that Δ(c_{k}td) = c + 1. Then we are done.

2. For all t ∈ [R(c, A_{k+1})] the relation Δ(c_{k}td) ∈ [c] holds. Then consider the c-coloring: Δ′ : [R(c, A_{k+1})] → [c] which is defined by

Δ′(x) = Δ(c_{k}xd).

By definition of R(c, A_{k+1}) there exists a solution (t_{j})_{j∈∪_{s≤k}I_{s}} of the system A_{k+1}x⃗ ≤ 0 which is monochromatic for Δ′. Hence (c_{k}dt_{j})_{j∈∪_{s≤k+1}I_{s}} forms a solution of A_{k+1}x⃗ ≤ 0 which is monochromatic with respect to Δ.

□_{theorem 1.2.(first part)}

In order to demonstrate the structure of the proof of the second part of theorem 1.5. we will give a short overview. For his characterization of regular systems of linear equations Rado [10] had to prove that for each systems Ax⃗ = 0, which is regular, A has the column property. It is an interesting feature of Rado’s proof that a system Ax⃗ = 0 is regular if there exists a monochromatic solution with respect to one type of coloring. For systems of linear inequalities Ax⃗ ≤ 0 with A having only two columns there also exists a certain type of coloring such that Ax⃗ ≤ 0 is partition regular if it has a monochromatic solution with respect to this type of coloring. In lemma 1.12. we will show, that a system (∗) a ≤ \frac{x_{1}}{x_{2}} ≤ b, where a, b ∈ ℚ and 1 < a ≤ b, is not partition regular. It is easy to see that essentially each system Ax⃗ ≤ 0 with A having only two columns can be transformed into a system (∗) for suitable a and b. If such a system is partition regular this means that one of the following cases holds:

1. a ≤ 0 and b > 0 or

2. a ≤ 1 and b ≥ 1.

It is not difficult to see that these conditions exactly lead to cpi. If we visualize a partition regular system

(∗∗) \{ \begin{matrix}a_{11}x_{1} + a_{12}x_{2} ≤ 0 \\ a_{21}x_{1} + a_{22}x_{2} ≤ 0 \end{matrix}

geometrically then obviously the solutions are bounded by two straight lines. Three typical cases occur, i.e. one of the axes is a limiting line or the diagonal is contained in the solution space:

We will prove theorem 1.5. by induction on the number of columns of A. In order to start the induction we described the situation for n = 2. Let us consider a rational matrix A with n columns. Assume that the system

Ax⃗ ≤ 0 (∗ ∗ ∗)

is partition regular. Under certain assumptions we can transform the system Ax⃗ ≤ 0 for each choice of k, l with 1 ≤ k < l ≤ n into the following system:

−\frac{a_{sl}}{a_{sk}} − ∑_{j=1,j≠l,k}^{n} \frac{a_{sj}}{a_{sk}} \frac{x_{j}}{x_{l}} ≤ \frac{x_{k}}{x_{l}} ≤ −\frac{a_{tl}}{a_{tk}} − ∑_{j=1,j≠l,k}^{n} \frac{a_{tj}}{a_{tk}} \frac{x_{j}}{x_{l}}

for all s with a_{sk} < 0 and for all t with a_{tk} > 0. Thus we have a similar situation as in (∗) except that the fraction \frac{x_{k}}{x_{l}} is not bounded by constant terms a and b but by terms which depend on x_{1} … x_{k−1}, x_{k−2}, … x_{n}. Thus we cannot directly apply lemma 1.12. Consider this situation for fixed k and l. Assume that there are colorings of the natural numbers with finitely many colors such that for each monochromatic solution x_{1}, … x_{n} of the system (∗ ∗ ∗) either

1. there exists ϵ_{1} > 0 and r ∈ ℕ such that 1 + ϵ_{1} ≤ \frac{x_{k}}{x_{l}} ≤ r or

2. there exists ϵ_{2} > 0 and ϵ_{3} > 0 such that ϵ_{2} ≤ \frac{x_{k}}{x_{l}} ≤ 1 − ϵ_{3}.

Then again by lemma 1.12. (∗∗∗) cannot be partition regular. To avoid such situations the terms −\frac{a_{sl}}{a_{sk}} − ∑_{j=1,j≠l,k}^{n} \frac{a_{sj}}{a_{sk}} \frac{x_{j}}{x_{l}} and −\frac{a_{tl}}{a_{tk}} − ∑_{j=1,j≠l,k}^{n} \frac{a_{tj}}{a_{tk}} \frac{x_{j}}{x_{l}} have to fulfill certain conditions for every coloring. This is what is shown in lemma 1.13. With this kind of arguments it is possible to show that for every choice of k and l with 1 ≤ k < l ≤ n either for all ϵ > 0 the system A_{l}^{k}(ϵ) is partition regular or for all ϵ > 0 the system A_{k}^{l}(ϵ) is partition regular, if the system Ax⃗ ≤ 0 is partition regular. By induction we can conclude that either for all ϵ > 0 the matrix A_{l}^{k}(ϵ) has cpi or for all ϵ > 0 the matrix A_{k}^{l}(ϵ) has cpi. Therefore we define:

Definition 1.4. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix. A has the ϵ-property if the following conditions are satisfied:

1. The system Ax⃗ ≤ 0 has a solution in the natural numbers and

2. For all 1 ≤ k < l ≤ n one of the following conditions is satisfied:

(a) For all ϵ > 0 the matrix A^{k}(ϵ) has cpi over ℕ,

(b) for all ϵ > 0 the matrix A^{l}(ϵ) has cpi over ℕ,

i.e. for at most one r with 1 ≤ r ≤ n there is an ϵ_{0} > 0 such that A^{r}(ϵ_{0}) has not cpi.

Note that if the matrix A^{k}(ϵ_{0}) has cpi for some ϵ_{0} > 0 then for all ϵ ≥ ϵ_{0} A^{k}(ϵ) has cpi.

Remark 1.1. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix, such that Ax⃗ ≤ 0 has a solution in ℕ. Let 1 ≤ k < l ≤ n.

1. If the matrix A_{l}^{k}(ϵ) has cpi then A^{k}(ϵ) has cpi.

A_{l}^{k} has cpi. Let I_{0}, …, I_{r} be the corresponding partition of the column indices. Define I_{r+1} = {l}. Then I_{0}, …, I_{r+1} is a partition of [n] which proves cpi for A^{k}(ϵ).

2. If the matrix A^{(k)+(l)}(ϵ) has cpi then the matrices A^{k}(ϵ) and A^{l}(ϵ) have cpi.

Let the blocks for A^{(k)+(l)}(ϵ) be I′_{0}, …, I′_{q} and assume that the column

a^{(k′)}(ϵ) = ( a_{1k} + a_{1l} − ϵ ; a_{2k} + a_{2l} − ϵ ; ⋮ ; a_{mk} + a_{ml} − ϵ )

belongs to the block I′_{p}. Then A^{k}(ϵ) and A^{l}(ϵ) have cpi with the corresponding blocks being I_{r} = I′_{r} for r ≠ p and I_{p} = I′_{p} − {k′} ∪ {k, l}.

Up to now we did not succeed in proving that A has cpi, but we know that if we transform A only a little then the transformed matrix has cpi and it is possible to do this transformations in nearly each column. What we will show in lemma 1.9. is that the property cpi is continuous in a certain manner.

Lemma 1.2. If A = (a_{ij})_{1≤i≤m,1≤j≤n} is a rational matrix, which satisfies the ϵproperty, then A has cpi.

In order to prove lemma 1.9. we need the following lemma: Lemma 1.3. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix such that for all 1 ≤ i ≤ m the entries of row i sum up to zero, i.e. ∑_{j=1}^{n} a_{ij} = 0. Let s_{1}, …, s_{m} ∈ ℚ. For all ϵ > 0 let A′(ϵ) = (a′_{ij}(ϵ))_{1≤i≤m,1≤j≤n+1}, be the matrix with entries a′_{ij}(ϵ) = a_{ij} for 1 ≤ i ≤ m, 1 ≤ j ≤ n and a_{in+1} = s_{i} − ϵ for 1 ≤ i ≤ m. Further let A′ = A′(0). If for all ϵ > 0 the system A′(ϵ)x⃗ ≤ 0 has a solution in ℕ, then the system A′x⃗ ≤ 0 has a solution in ℕ.

Proof of lemma 1.3.: Let A, A′(ϵ) and A′ be as in the assumptions of lemma 1.10. Assume that for all 1 ≤ i ≤ m we have ∑_{j=1}^{n} a_{ij} = 0. Thus the system Ax⃗ ≤ 0 can be transformed into the following system

(∗)  ∑_{j=1}^{n−1} a_{ij}(x_{j} − x_{n}) ≤ 0, 1 ≤ i ≤ m,

which will be abbreviated in the following as A^{∗}y⃗ ≤ 0, where A^{∗} = (a_{ij})_{1≤i≤m,1≤j≤n−1}, and y_{j} = x_{j} − x_{n} for 1 ≤ j ≤ n − 1. The system Ax⃗ ≤ 0 (resp. Ax⃗ < 0) has a solution in ℕ if and only if (∗) (resp. A^{∗}y⃗ < 0) has a solution in ℤ.

In the following we will consider A^{∗} instead of A. (The entries of A^{∗} will be denoted without ∗.) Assume that the set of rows of A^{∗} is linear independent over ℚ. Then there exists y⃗ = (y_{1}, … y_{n−1}) ∈ ℚ^{n−1} such that A^{∗}y⃗ < 0. Multiplication with the least common multiple of the denominators of y_{j} yields a solution y′ = (y′_{1} … y′_{n−1}) ∈ ℤ^{n−1} of the system A^{∗}y⃗ < 0. Thus the system Ax⃗ < 0 has a solution in ℕ and therefore A′x⃗ ≤ 0 has a solution in ℕ. Hence we are done in this case.

Next we consider the case where the set of rows of A^{∗} is not linear independent. Assume that A^{∗} consists of the rows a_{(1)}, … a_{(k)}, b_{(k+1)}, …, b_{(m)} for some k ≥ 0, where a_{(1)}, …, a_{(k)} are linear independent and for all k + 1 ≤ i ≤ m we have b_{(i)} = ∑_{s=1}^{k} c_{s}^{i}a_{(s)} for suitable c_{s}^{i} ∈ ℚ.

We will prove the lemma by induction on k. If k = 0 then A^{∗} is the zero-matrix. Hence A is the zero-matrix and therefore the system A′(ϵ)x⃗ ≤ 0 has a solution in ℕ if and only if for all 1 ≤ i ≤ m we have s_{i} − ϵ ≤ 0. This is true for all ϵ > 0 by assumption and therefore for all 1 ≤ i ≤ m we have s_{i} ≤ 0. If k = 1 for all 2 ≤ i ≤ m we have b_{(i)} = c_{1}^{i}a_{(i)} for suitable c_{1}^{i} ∈ ℚ. We distinguish the following cases:

1. for all 2 ≤ i ≤ m we have c_{1}^{i} > 0.

If a_{(1)}y⃗ < 0 holds then for all 2 ≤ i ≤ m we have b_{(i)}y⃗ < 0. Because a_{(1)} is not the zero-vector there exists a solution y⃗ ∈ ℤ^{n} such that A^{∗}y⃗ < 0 and hence we are done in this case.

2. There exists i such that c_{1}^{i} = 0.

In this case we have b_{(i)} = 0 and the system A′(ϵ)x⃗ ≤ 0 has a solution only if s_{i} − ϵ ≤ 0. Because this is true for every ϵ > 0, we have s_{i} ≤ 0. Hence (b_{(i)}s_{i})x⃗ ≤ 0 is true for every choice of x⃗ where x_{n+1} ≥ 0. Therefore the matrix keeps its properties if we omit the row b_{(i)}.

3. There exists i such that c_{1}^{i} < 0.

Let i be arbitrary with c_{1}^{i} < 0. By assumption we know that for every ϵ > 0 the system A′(ϵ)x⃗ ≤ 0 has a solution. Let x⃗(ϵ) = (x_{1}(ϵ), …, x_{n}(ϵ)), x(ϵ) be one specific solution of the system A′(ϵ)x⃗ ≤ 0, i. e.

a_{(1)}x⃗(ϵ) + (s_{1} − ϵ)x(ϵ) ≤ 0,

which is equivalent to

∑_{j=1}^{n} a_{1j}x_{j}(ϵ) ≤ −(s_{1} − ϵ)x(ϵ)

and correspondingly we have

b_{(i)}x⃗(ϵ) + (s_{i} − ϵ)x(ϵ) ≤ 0,

which is equivalent to

c_{1}^{i}(∑_{j=1}^{n} a_{1j}x_{j}(ϵ)) ≤ −(s_{i} − ϵ)x(ϵ)

Dividing by c_{1}^{i} > 0 we obtain

∑_{j=1}^{n} a_{1j}x_{j}(ϵ) ≥ −\frac{s_{i} − ϵ}{c_{1}^{i}}x(ϵ).

Hence a solution x_{1}(ϵ), …, x_{n}(ϵ) exists if and only if

−\frac{s_{i} − ϵ}{c_{1}^{i}} ≤ s_{1} − ϵ,

which means

s_{i} ≤ −c_{1}^{i}s_{i} + (c_{1}^{i} − 1)ϵ.

This is true for all ϵ > 0 and hence

s_{i} ≤ −c_{1}^{i}s_{1}

holds.

Thus the statement is true for k = 1.

Assume that our statement is true for some (fixed) k ≥ 1. Let A^{∗} consist of the rows a_{(1)}, …, a_{(k+1)}, b_{(k+2)}, …, b_{(m)}, where a_{(i)} are linear independent and for k + 1 ≤ i ≤ m let

b_{(i)} = ∑_{s=1}^{k+1} c_{s}^{i}a_{(s)}

for suitable c_{s}^{i} ∈ ℚ. Further assume that for every ϵ > 0 the system A′(ϵ)x⃗ ≤ 0 has a solution in ℕ. We distinguish the following cases:

1. There exists 1 ≤ s ≤ k + 1 such that for all k + 2 ≤ i ≤ m we have c_{s}^{i} > 0.

Let c = max_{k+1<i<m,1≤l≤k,l≠s}|c_{l}^{i}|. a_{(1)}, …, a_{(k+1)} are linearly independent by assumption. Hence there exists y⃗ = (y_{1}, …, y_{n}) such that for all 1 ≤ i ≤ k we have a_{(i)}y⃗ < 0 and

min_{k+1≤i≤m}|c_{s}^{i}(a_{(s)}y⃗)| > c · (max_{1≤l≤k,l≠s}|a_{(l)}y⃗|)(k − 1).

Then y_{1}, … y_{n−1} form a solution for the whole system A^{∗}y⃗ < 0 and hence A′x⃗ ≤ 0 has a solution.

2. There exists s such that for all k + 1 ≤ i ≤ m we have c_{s}^{i} ≥ 0 and c_{s}^{i} = 0 for at least one i.

Without loss of generality let s = 1 and c_{1}^{i} > 0 for k + 1 ≤ i ≤ l and c_{1}^{i} = 0 for l < i ≤ m. Then the matrix which consists of the rows a_{(1)}, …, a_{(k+1)}, b_{(k+2)}, …, b_{(l)} is dealt within case 1. But the rows b_{(l+1)} up to b_{(m)} only depend on the k − 1 generators a_{(2)} up to a_{(k+1)}. Hence by induction we obtain a solution y_{1}, …, y_{n} for the rows a_{(2)}, …, a_{(k+1)}, b_{(k+2)}, …, b_{(m)} which are independent of a_{(1)}. Thus we also obtain a solution for the whole system.

3. For a ≤ i ≤ k + 1 we define

c_{j}^{i} = \{ \begin{matrix}1 & for & j = i \\ 0 & for & j ≠ i. \end{matrix}

Then it remains to consider the case where there exist 1 ≤ i_{1}, i_{2} ≤ m and there exists 1 ≤ s ≤ k + 1 such that c_{s}^{i_{1}} > 0 and c_{s}^{i_{2}} < 0. Without loss of generality let s = 1. Further we can divide the entries of each row i by |c_{1}^{i}|, if |c_{1}^{i}| ≠ 0, such that we may assume that |c_{1}^{i}| = 1 for each i, where |c_{1}^{i}| ≠ 0. For every ϵ > 0 the system A^{∗}(ϵ)′x⃗ ≤ 0 has a solution. Let y^{ϵ} = (y_{1}^{ϵ}, …, y_{n−1}^{ϵ}), x^{ϵ} be such a solution, i. e.

∑_{s=1}^{k+1} c_{s}^{i}(a_{(s)}y^{ϵ}) + (s_{i} − ϵ)x^{ϵ} ≤ 0 for k + 2 ≤ i ≤ m

and

a_{(i)}y^{ϵ} ≤ −(s_{i} − ϵ)x^{ϵ} for 1 ≤ i ≤ k + 1.

Thus we have

∑_{s=2}^{k+1} c_{s}^{i}(a_{(s)}y⃗)^{ϵ} + (s_{i} − ϵ)x^{ϵ} ≤ −c_{1}^{i}a_{(1)}y^{ϵ}.

Dividing by −c_{1}^{i} leads to

∑_{s=2}^{k+1} c_{s}^{r}(a_{(s)}y^{ϵ}) + (s_{r} − ϵ)x^{ϵ} ≤ a_{(1)}y^{ϵ} ≤ − ∑_{s=2}^{k+1} c_{s}^{j}(a_{(s)}y^{ϵ}) − (s_{j} − ϵ)x^{ϵ}

for all r with c_{1}^{r} = −1 and j with c_{1}^{j} = 1. Further we know that a_{(1)}y⃗ ≤ −(s_{1} − ϵ)x^{ϵ}. Hence we additionally obtain:

∑_{s=2}^{k+1} c_{s}^{r}(a_{(s)}y^{ϵ}) ≤ −(s_{1} − ϵ)x^{ϵ}

for all i satisfying c_{1}^{i} = −1 and

∑_{s=2}^{k+1} c_{s}^{i}(a_{(s)}y^{ϵ}) ≤ −(s_{i} − ϵ)x^{ϵ}

for all i satisfying c_{1}^{i} = 0. Transforming these inequalities we get the following system of inequalities:

(∗ ∗ ∗) \{ \begin{matrix}a_{(i)}y^{ϵ} + (s_{i} − ϵ)x^{ϵ} ≤ 0 & 2 ≤ i ≤ k + 1 \\ (∑_{s=2}^{k+1} c_{s}^{i}(a_{(s)}y^{ϵ})) + (s_{i} − ϵ)x^{ϵ} ≤ 0 & for all i with \\ & c_{1}^{i} = 0 \\ (∑_{s=2}^{k+1} c_{s}^{i}(a_{(s)}y^{ϵ})) + (s_{i} + s_{1} − 2ϵ)x^{ϵ} ≤ 0 & for all i with \\ & c_{1}^{i} = −1 \\ (∑_{s=2}^{k+1}(c_{s}^{i} + c_{s}^{j})(a_{(s)}y^{ϵ})) + (s_{i} + s_{j} − 2ϵ)x^{ϵ} ≤ 0 & for all i, j with \\ & c_{1}^{i} = −1, c_{1}^{j} = 1 \end{matrix}

By assumption we know that for all ϵ > 0 the system A^{∗}(ϵ)′x⃗ ≤ 0 has a solution. Hence the system (∗ ∗ ∗) has a solution for every ϵ > 0. In system (∗ ∗ ∗) only k row vectors are linear independent, namely a_{(2)}, …, a_{(k+1)}. Thus we can use induction to show that the system (∗ ∗ ∗) has a solution for ϵ = 0. Thus the system A′x⃗ ≤ 0 has a solution in ℕ.

□_{lemma 1.2.}

Claim 1.1. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix which has cpi with the first block being I_{0}^{A} = {1, … k} and ∑_{j=1}^{k} a_{ij} = 0. Let

B = ( \begin{matrix}b_{11} & b_{12} & … & b_{1n} \\ b_{21} & b_{22} & … & b_{2n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ b_{l1} & b_{l2} & … & b_{ln} \end{matrix} ; A )

such that for all 1 ≤ i ≤ l the relation ∑_{j=1}^{k} b_{ij} < 0 holds. Then B has cpi.

Proof of claim 1.1.: Obviously I_{0}^{B} = {1, …, k} satisfies the first condition of cpi. Let I_{0}^{A}, …, I_{v}^{A} be the partition of columns of A and for 1 ≤ r < v, j ∈ ∪_{s≤r}I_{s} let c_{rj}^{A}, c_{r}^{A} ∈ ℕ be the corresponding coefficients . Let the parameters b(r), δ, B(r), c(r) 1 ≤ r ≤ v be “big enough”, in particular we define:

\begin{aligned}b(r) & = & max_{1≤i≤l}\{ ∑_{j∈I_{r+1}^{A}} b_{ij}, \} \\ δ & = & max_{1≤i≤l}\{∑_{j=1}^{k} b_{ij}\} (< 0), \\ B(r) & = & max_{1≤i≤l}\{ ∑_{j∈∪_{w≤r}I_{w}^{A}} |b_{ij}|\}, \\ c(r) & = & max_{j∈∪_{w≤r}I_{w}^{A}}\{c_{rj}^{A}, c_{r}^{A}\}. \end{aligned}

and let a(r) ∈ ℕ be minimal such that

a(r)δ ≤ −(c(r)B(r) + c_{r}b(r)).

Such an a=a(r) exists because δ is negative. Let c_{rj}^{B} = c_{rj}^{A} + a if j ≤ k and c_{rj}^{B} = c_{rj} otherwise. For 1 ≤ r ≤ v let c_{r}^{B} = c_{r}^{A} and I_{r}^{B} = I_{r}^{A}. Then for all 1 ≤ i ≤ l we have:

∑_{j=1}^{k}(a + c_{rj})b_{ij} + ∑_{j∈∪_{w≤r}I_{w}^{A},j>k} c_{rj}b_{ij} + c_{r} ∑_{j∈I_{r+1}^{A}} b_{ij}

= a ∑_{j=1}^{k} b_{ij} + ∑_{j=1}^{k} c_{rj}b_{ij} + ∑_{j∈∪_{w≤r}I_{w}^{A},j>k} c_{rj}b_{ij} + c_{r} ∑_{j∈I_{r+1}^{A}} b_{ij}

≤ aδ + c(r)B(r) + c_{r}b(r) ≤ 0.

Further for all 1 ≤ i ≤ l we have:

\begin{aligned}∑_{j=1}^{k}(a + c_{ij})a_{ij} & = (∑_{j=1}^{k} c_{rj}a_{ij}) + a(∑_{j=1}^{k} a_{ij}) \\ & = ∑_{j=1}^{k} c_{rj}a_{ij}. \end{aligned}

Hence B has cpi. □_{claim 1.1.}

Proof of lemma 1.2.: Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix which has the ϵ-property, i. e. for all 1 ≤ k < l ≤ n either A^{k}(ϵ) or A^{l}(ϵ) has cpi for every ϵ > 0. We will prove that A has cpi. If the matrix A^{k}(ϵ) has cpi for some k ≤ n, let I_{0}^{k}, …, I_{l_{k}}^{k} be a partition of columns of A^{k}(ϵ), which certifies cpi. We can assume that the partition of [n] into blocks does not depend on ϵ because there are only finitely many possibilities of partitioning [n] into blocks. By the pigeonhole principle at least one partition has to occur for arbitrary small ϵ > 0. But if a matrix A^{k}(ϵ_{0}) has cpi with blocks I_{0}^{k}(ϵ_{0}), … I_{l_{k}}^{k}(ϵ_{0}) then for all ϵ > ϵ_{0} the matrix A^{k}(ϵ) has cpi with the same blocks.

We will prove lemma 1.3. by a downward induction on the size of the block I_{0}^{k} which is maximal for k ≤ n, for which the matrix A^{k}(ϵ) has cpi for all ϵ > 0. To illustrate the main idea of the proof we first show the theorem for matrices with one and two columns.

n = 1 :

A = ( a_{11} ; a_{21} ; ⋮ ; a_{m1} ) .

The system Ax⃗ ≤ 0 has a solution x ∈ ℕ. Therefore we have a_{i1} ≤ 0 and thus A has cpi with I_{0} = {1}.

n = 2:

A = ( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \\ ⋮ & ⋮ \\ a_{m1} & a_{m2} \end{matrix} )

There are only three (finitely many) possibilities to arrange the columns of A into blocks. Hence we can assume that there is an ϵ_{0} > 0 such that for all ϵ < ϵ_{0} the partition of the columns of A^{i}(ϵ) into blocks is the same.

1. I_{0}^{1} = {1} or I_{0}^{2} = {2} resp.

For all 1 ≤ i ≤ m and all ϵ > 0 we have a_{i1} − ϵ ≤ 0. Hence for all 1 ≤ i ≤ m the relation a_{i1} ≤ 0 holds. So the first condition of cpi is satisfied with I_{0} = {1}.

Further by the definition of the ϵ-property the system Ax⃗ ≤ 0 has a solution in ℕ, Let x_{1}^{∗}, x_{2}^{∗} be such a solution. Then the second condition is fulfilled with c_{11} = x_{1}^{∗} and c_{1} = x_{2}^{∗}, i. e. for all 1 ≤ i ≤ m we have c_{11}a_{i1} + c_{1}a_{i2} ≤ 0. Hence A has cpi.

2. I_{0}^{1} = {1, 2}

In this case for all 1 ≤ i ≤ m and for all ϵ > 0 we have a_{i1} + a_{i2} − ϵ ≤ 0. Hence for all 1 ≤ i ≤ m we have a_{i1} + a_{i2} ≤ 0. Therefore A has cpi with I_{0} = {1, 2}.

Now we will prove the lemma for matrices of arbitrary size.

A = ( \begin{matrix}a_{11} & a_{12} & … & a_{1n} \\ a_{21} & a_{22} & … & a_{2n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{m1} & a_{m2} & … & a_{mn} \end{matrix} )

Let 1 ≤ k < l ≤ n. We know by assumption that for all ϵ > 0 either A^{k}(ϵ) or A^{l}(ϵ) has cpi. As mentioned above we can assume that the partition of [n] into blocks does not depend on ϵ. In order to start the induction we consider the case where we can find some 1 ≤ k ≤ n such that A^{k}(ϵ) has cpi for every ϵ > 0 and |I_{0}^{k}|=n, i. e. the sum over all columns of A^{k}(ϵ) is less of equal to zero. In this case for all 1 ≤ i ≤ m and every ϵ > 0 we have

a_{i1} + a_{i2} + … + a_{in} − ϵ ≤ 0.

Hence for all 1 ≤ i ≤ m we have

a_{i1} + a_{i2} + … + a_{in} ≤ 0

and therefore A has cpi with I_{0} = [n]. Next we consider the case where we can find some k, 1 ≤ k ≤ n such that A^{k}(ϵ) has cpi for every ϵ > 0 and |I_{0}^{k}| = n − 1. First assume that k ∈ I_{0}^{k}. Then for all 1 ≤ i ≤ m and all ϵ > 0 we have:

( ∑_{j∈I_{0}^{k}} a_{ij}) − ϵ ≤ 0.

In this case for all 1 ≤ i ≤ m we obtain

∑_{j∈I_{0}^{k}} a_{ij} ≤ 0.

If k ∉ I_{0}^{k} for all 1 ≤ i ≤ m we also have

∑_{j∈I_{0}^{k}} a_{ij} ≤ 0.

Thus in both cases the first condition of cpi is satisfied choosing I_{0} = I_{0}^{k}. Let I_{1} = [n] − I_{0}. Note that |I_{1}| = 1 and assume p ∈ I_{1}. We know that the system Ax⃗ ≤ 0 has a solution in ℕ. Let x_{1}^{∗}, … x_{n}^{∗} be such a solution. Then for all 1 ≤ i ≤ m we have

∑_{j∈I_{0}} c_{1j}a_{ij} + c_{1}a_{ip} ≤ 0,

if we choose c_{1j} = x_{j}^{∗} for j ∈ I_{0} and c_{1} = x_{p}^{∗}.

Assume inductively that the following is true for some (fixed) k ≤ n − 1: Let A be a rational matrix with m rows and n columns which has the ϵ- property. If there exists a column s, such that for all ϵ > 0 A^{s}(ϵ) has cpi and |I_{0}^{s}| ≥ k, then A has cpi.

In the following we will show that if A is a rational matrix which has the ϵ-property and there exists a column s, such that for all ϵ > 0 A^{s}(ϵ) has cpi and |I_{0}^{s}| = k − 1, then A has cpi. Without loss of generality we can assume that I_{0}^{s} = {1, … k − 1} for some (fixed) s. For k − 1 ≤ n − 2, we have |[n] − I_{0}^{s}| ≥ 2. A has the ϵ- property, therefore either A^{k}(ϵ) or A^{k+1}(ϵ) has cpi for all ϵ > 0. Without loss of generality we can assume that A^{k}(ϵ) has cpi. We will consider several cases:

1. I_{0}^{k} ⊈ I_{0}^{s}.

In this case for all ϵ > 0 and all 1 ≤ i ≤ m we have

(∑_{j=1}^{k−1} a_{ij}) − ϵ ≤ 0

and therefore

∑_{j=1}^{k−1} a_{ij} ≤ 0.

Further for all 1 ≤ i ≤ m we have

∑_{j∈I_{0}^{k}} a_{ij} ≤ 0.

We distinguish the following cases:

(a) I_{0}^{k} ∩ I_{0}^{s} = ∅

Then we have

∑_{j∈I_{0}^{k}∪I_{0}^{s}} a_{ij} ≤ 0.

Let I_{0} = I_{0}^{k} ∪ I_{0}^{s} and I_{l} = I_{l}^{k} − I_{0}^{s}. Because of the definition of I_{l}^{k} for all ϵ > 0 and for all j ∈ ∪_{s≤l}I_{s}^{k} there exists c_{lj}^{k}(ϵ) and c_{l}^{k}(ϵ) such that for all 1 ≤ i ≤ m we have

∑_{j∈∪_{s≤l}I_{s}^{k}} c_{lj}^{k}(ϵ)a_{ij}^{k}(ϵ) + c_{l}^{k}(ϵ) ∑_{j∈I_{l+1}^{k}} a_{ij}^{k}(ϵ) ≤ 0

and therefore

∑_{j∈∪_{s≤l}I_{s}^{k}} c_{lj}^{k}(ϵ)a_{ij}^{k}(ϵ) + ∑_{j∈(I_{0}^{s}−I_{l+1}^{k})} a_{ij}^{k}(ϵ) + ∑_{j∈I_{0}^{s}∩I_{l+1}^{k}}(1 + c_{l}^{k}(ϵ))a_{ij}^{k}(ϵ)+

∑_{j∈(I_{l+1}^{k}−I_{0}^{s})} c_{l}(ϵ)a_{ij}^{k}(ϵ) ≤ 0.

Hence we conclude that we can choose I_{0} = I_{0}^{k} ∪ I_{0}^{s} to prove cpi and |I_{0}| > |I_{0}^{s}| = k − 1. So we are done by induction.

(b) I_{0}^{k} ∩ I_{0}^{s} ≠ ∅

Without loss of generality we can assume that I_{0}^{k} ∩ I_{0}^{s} = {1, …, l}. Consider the matrix

B = ( \begin{matrix}2a_{11} & 2a_{12} & … & 2a_{1l} & a_{1l+1} & … & a_{1n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 2a_{m1} & 2a_{m2} & … & 2a_{ml} & a_{ml+1} & … & a_{mn} \end{matrix} ) = (b_{ij})_{1≤i≤m,1≤j≤n}.

We claim that B has the ϵ-property. This is true because

(i) the system A′x⃗ ≤ 0 has a solution in ℕ for if x_{1}, …, x_{n} is a solution of Ax⃗ ≤ 0, then x_{1}, …, x_{l}, 2x_{l+1}, …, 2x_{n} forms a solution of Bx⃗ ≤ 0.

(ii) Let 1 ≤ p ≤ n such that A^{p}(ϵ) has cpi for every ϵ > 0 with blocks I_{0}^{p}, I_{1}^{p}, . . .. Let I_{0}^{′p} = I_{0}^{k} ∪ I_{0}^{s}. Then for all 1 ≤ i ≤ m the following is true:

0 ≥ ∑_{j∈I_{0}^{k}} a_{ij}^{k}(ϵ) + ∑_{j∈I_{0}^{s}} a_{ij}^{s}(ϵ) = ∑_{j∈I_{0}^{′p}} b_{ij}^{p}(ϵ).

Let I_{r}^{′p} = I_{r−1}^{p} − (I_{0}^{k} ∪ I_{0}^{s}). A^{p}(ϵ) has cpi for every ϵ > 0. Hence there exist c_{r−1j}^{p} = c_{r−1j}^{p}(ϵ), c_{r−1}^{p} = c_{r−1}^{p}(ϵ) such that for all 1 ≤ i ≤ m we have

∑_{j∈∪_{q≤r−1}I_{q}^{p}} c_{r−1j}a_{ij}^{p}(ϵ) + c_{r−1} ∑_{j∈I_{r}^{p}} a_{ij}^{p}(ϵ) ≤ 0.

Hence we have

∑_{j=1}^{l} b_{ij}^{p}(ϵ) + ∑_{j∈I_{0}^{′p}−{1,...,l}} 2b_{ij}^{p}(ϵ) + ∑_{j∈∪_{q≤r−1}I_{q}^{p}∩(I_{0}^{k}∪I_{0}^{s})} c_{r−1j}2b_{ij}^{p}(ϵ)+

∑_{j∈(∪_{q≤r−1}I_{q}^{p})−(I_{0}^{k}∪I_{0}^{s})} c_{r−1j}2b_{ij}^{p}(ϵ) + ∑_{j∈I_{r}^{p}∩(I_{0}^{k}∪I_{0}^{s})} c_{r−1}2b_{ij}^{p}(ϵ) + ∑_{j∈I_{r}^{′p}} c_{r−1}2b_{ij}^{p}(ϵ)

≤ 0.

Hence B^{p}(ϵ) has cpi if A^{p}(ϵ) has cpi. Therefore B has the ϵ-property and |I_{0}^{′p}| ≥ k. Hence B has cpi by induction.

We claim that if B has cpi then A has cpi.

Let the partition into blocks for B be I_{0}^{B}, I_{1}^{B}, …, I_{v}^{B}. Let I_{0} = {1, …, k − 1}. We know that

∑_{j=1}^{k−1} a_{ij} ≤ 0.

Let I_{1} = (I_{0}^{k}∪I_{0}^{s})−{1, …, k−1}, let c_{01} = … = c_{0l} = 2, c_{0l+1} = … = c_{0k−1} = 1 and c_{0} = 1. Then for all 1 ≤ i ≤ m we have

∑_{j∈I_{0}} c_{j0}a_{ij} + c_{0} ∑_{j∈I_{1}} a_{ij} ≤ 0.

Let I_{r} = I_{r−2}^{B} − (I_{0}^{k} ∪ I_{0}^{s}). We know that there exist c_{r−2j}^{B}, c_{r−2}^{B} such that we have

∑_{j∈∪_{w≤r−3}I_{w}^{B}} c_{r−2j}^{B}b_{ij} + c_{r−2}^{B} ∑_{j∈I_{r−2}^{B}} b_{ij} ≤ 0

and thus

∑_{j=1}^{l} 2a_{ij} + ∑_{j∈(I_{0}^{k}∪I_{0}^{s})−{1,...,l}} a_{ij} + ∑_{j∈(∪_{w≤r−3}I_{w}^{B})−(I_{0}^{k}∪I_{0}^{s})} c_{r−2j}^{B}a_{ij}+

∑_{j∈(∪_{w≤r−3}I_{w}^{B})∩(I_{0}^{k}∪I_{0}^{s})} c_{r−2j}^{B}a_{ij} + c_{r−2}^{B} ∑_{j∈I_{r−2}^{B}∩(I_{0}^{k}∪I_{0}^{s})} a_{ij} + c_{r−2}^{B} ∑_{j∈I_{r}} a_{ij}

≤ 0.

Hence A has cpi.

2. I_{0}^{k} ⊆ I_{0}^{s} = {a^{(1)}, … a^{(k−1)}}.

(If I_{0}^{s} ⊂ I_{0}^{k}, we would have |I_{0}^{k}| ≥ k and we were done by induction.)

Without loss of generality we can assume that I_{0}^{k} = I_{0}^{s}, because otherwise it is possible to choose I_{0}^{k} as the first block for the matrix A^{s}(ϵ). We distinguish the following cases:

(a) k ∉ I_{1}^{k} In this case there exist c_{1j} ∈ ℕ, c_{1} ∈ ℕ such that for all 1 ≤ i ≤ m we have

∑_{j∈I_{0}^{k}} c_{1j}a_{ij} + c_{1} ∑_{j∈I_{1}^{k}} a_{ij} ≤ 0.

Consider the following matrix B = (b_{ij})_{1≤i≤m,1≤j≤n}, where for all

1 ≤ i ≤ m b_{ij} is defined by

b_{ij} = \{ \begin{matrix}c_{1j}a_{ij} & for & 1 ≤ j ≤ k − 1 \\ c_{1}a_{ij} & for & j ∈ I_{1}^{k} \\ a_{ij} & & otherwise. \end{matrix}

We claim that B has the ϵ-property.

(i) The system Bx⃗ ≤ 0 has a solution, for if x_{1}, … x_{n} is a solution of the system Ax⃗ ≤ 0, then define a solution of the system By⃗ ≤ 0, y⃗ = (y_{1}, …, y_{n}) by

y_{j} = \{ \begin{matrix}\frac{1}{c_{1j}} x_{j} & if & 1 ≤ j ≤ k − 1 \\ \frac{1}{c_{1}} x_{j} & if & j ∈ I_{1}^{k} \\ x_{j} & & otherwise. \end{matrix}

If we multiply y⃗ by the least common multiple of c_{1j}, c_{1} we obtain a solution of the system Bx⃗ ≤ 0 in ℕ. (ii) Let 1 ≤ p ≤ n be given such that for every ϵ > 0 A^{p}(ϵ) has cpi and let I_{0}^{p}, …, I_{l}^{p} be the blocks and c_{rj}^{p}(ϵ), c_{r}^{p}(ϵ) the corresponding coefficients, such that for all 1 ≤ i ≤ m we have

∑_{j∈I_{0}^{p}} a_{ij}^{p}(ϵ) ≤ 0

and

∑_{j∈∪_{w≤r}I_{w}^{p}} c_{rj}^{p}(ϵ)a_{ij}^{p}(ϵ) + c_{r}^{p}(ϵ) ∑_{j∈I_{r+1}^{p}} a_{ij}^{p}(ϵ) ≤ 0.

Now we will show that B^{p}(ϵ) has cpi for all ϵ > 0. Let I_{0}^{′p} = I_{0}^{k} ∪ I_{1}^{k} and I_{r}^{′p} = I_{r−1}^{p} − I_{0}^{′p}. Then for all 1 ≤ i ≤ m we have

∑_{j∈I_{0}^{′p}} b_{ij} ≤ 0

and

∑_{j∈∪_{w≤r−1}I_{w}^{p}} c_{r−1j}^{p}(ϵ)a_{ij}^{p}(ϵ) + c_{r−1}^{p}(ϵ) ∑_{j∈I_{r}^{p}} a_{ij}^{p}(ϵ) ≤ 0.

It follows that

\begin{matrix}∑_{j∈I_{0}^{′p}} b_{ij}^{p}(ϵ) + ∑_{j∈((∪_{w≤r−1}I_{w}^{p})∩I_{0}^{′p})} c_{r−1j}^{p}(ϵ)a_{ij}^{p}(ϵ) + ∑_{j∈I_{r−1}^{p}∩I_{0}^{p}} c_{r}^{p}(ϵ)a_{ij}^{p}(ϵ)+ \\ ∑_{j∈(∪_{w≤r−1}I_{w}^{p})−I_{0}^{′p}} c_{r−1j}^{p}(ϵ)a_{ij}^{p}(ϵ) + ∑_{j∈I_{r}^{′p}} c_{r}^{p}(ϵ)a_{ij}^{p}(ϵ) ≤ 0. \end{matrix}

Hence B has the ϵ-property. Thus B has cpi by induction. Let the corresponding partition of blocks be I_{0}^{B}, …, I_{l}^{B} and let c_{rj}^{B}, c_{r}^{B} be the corresponding coefficients. We claim that A has cpi. Let I_{0} = I_{0}^{k}, I_{1} = I_{1}^{k}, I_{r} = I_{r−2}^{B} − (I_{0}^{k} ∪ I_{1}^{k}). Obviously for all 1 ≤ i ≤ m we have

∑_{j∈I_{0}} a_{ij} ≤ 0.

For 2 ≤ r ≤ l − 1, for all 1 ≤ i ≤ m we have

∑_{j∈∪_{w≤r−2}I_{w}^{B}} c_{r−2j}^{B}b_{ij} + c_{r−1}^{B}( ∑_{j∈I_{r−1}^{B}} b_{ij}) ≤ 0.

Thus for all 1 ≤ i ≤ m the following is true

∑_{j∈I_{0}^{k}} a_{ij} + ∑_{j∈I_{1}^{k}} a_{ij} + ∑_{j∈(∪_{w≤r−2}I_{w}^{B}∩(I_{0}^{k}∪I_{1}^{k}))} c_{r−2j}^{B}b_{ij}

+ ∑_{j∈I_{r−1}^{B}∩(I_{0}^{k}∪I_{1}^{k})} c_{r−2}^{B}b_{ij} + ∑_{j∈∪_{w≤r−2}I_{w}^{B}−(I_{0}^{k}∪I_{1}^{k})} c_{r−2j}^{B}b_{ij} + c_{r−2}^{B}( ∑_{j∈I_{r+1}} b_{ij})

≤ 0.

Hence A has cpi.

(b) k ∈ I_{1}^{k}. Without loss of generality we can assume that I_{1}^{k} = {k, …, r}. For all 1 ≤ i ≤ m we know that ∑_{j=1}^{k−1} a_{ij} ≤ 0. It is no restriction to assume that

∑_{j=1}^{k} a_{ij} \{ \begin{matrix}= 0 & for & 1 ≤ i ≤ m_{1} \\ < 0 & for & m_{1} < i ≤ m \end{matrix}

for some m_{1} ≤ m. In claim 1.11. we have shown that it is enough to consider the first m_{1} rows of A. Let

B = (a^{(1)}, …, a^{(k−1)})

be the matrix which consists of the first k − 1 columns of A. Let

B′(ϵ) = ( \begin{matrix}a_{11} & … & a_{1k−1} & (∑_{j=k}^{r} a_{1j} − ϵ) \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{m_{1}1} & … & a_{m_{1}k−1} & (∑_{j=k}^{r} a_{m_{1}j} − ϵ) \end{matrix} ) .

Obviously adding up the columns of B we get the zero vector. Further for all ϵ > 0 the system B′(ϵ)x⃗ ≤ 0 has a solution. Hence we can apply lemma 1.10. to show that the system B′(0)x⃗ ≤ 0 has a solution in ℕ. Assume that c_{11}, …, c_{1k−1}, c_{1} is such a solution, hence for all 1 ≤ i ≤ m we have

∑_{j=1}^{k−1} a_{ij}c_{1j} + c_{1} ∑_{k}^{r} a_{ij} ≤ 0.

Then we consider the matrix B = (b_{ij})_{1≤i≤m,1≤j≤n}

b_{ij} = \{ \begin{matrix}c_{1j}a_{ij} & for & 1 ≤ j ≤ k − 1 \\ c_{1}a_{ij} & for & k ≤ j ≤ r \\ a_{ij} & & otherwise. \end{matrix}

As in case a) it is now possible to show that B has the ϵ-property. Then by induction B has cpi which again implies as in case a) that A has cpi.

□_{lemma 1.3.}

Lemma 1.4. Let a, b ∈ ℚ and let the following system of inequalities be given:

(∗) a ≤ \frac{x_{1}}{x_{2}} ≤ b.

Let 1. 1 < a ≤ b or

2. 0 < a ≤ b < 1.

Then (∗) is not partition regular over ℕ.

Proof of lemma 1.4.:

1. Assume that 1 < a ≤ b.

Let n ∈ ℕ be minimal such that a^{n} > b. Consider the following coloring: Δ^{a,b} : ℕ → [n + 1] which is defined by

(∗∗) Δ^{a,b}(x) = (⌊log_{a}(x)⌋mod(n + 1)) + 1.

In the following we will show that (∗) has no monochromatic solution for Δ^{a,b}.

Assume on the contrary that x_{1}, x_{2} form a solution of (∗) which is monochromatic with respect to Δ^{a,b}. Let log_{a}(x_{1}) = μ_{x_{1}} and log_{a}(x_{2}) = μ_{x_{2}}. Then we have

μ_{x_{1}} ≡ μ_{x_{2}}mod(n + 1).

Say μ_{x_{1}} = k_{x_{1}}(n + 1) + r and μ_{x_{2}} = k_{x_{2}}(n + 1) + r for some 0 ≤ r ≤ n. Because x_{1}, x_{2} forms a solution of (∗) we have

a ≤ \frac{x_{1}}{x_{2}} ≤ b

and thus

a ≤ \frac{x_{1}}{x_{2}} < \frac{a^{μ_{x_{1}} +1}}{a^{μ_{x_{2}}}} = a^{(k_{x_{1}} −k_{x_{2}} )(n+1)+1}.

Therefore we have

(k_{x_{1}} − k_{x_{2}})(n + 1) + 1 > 1

and hence

k_{x_{1}} − k_{x_{2}} > 0.

On the other hand we have:

a^{n} > b ≥ \frac{x_{1}}{x_{2}} ≥ \frac{a^{μ_{x_{1}}}}{a^{μ_{x_{2}} +1}} = a^{(k_{x_{1}} −k_{x_{2}} )(n+1)−1},

which implies

(k_{x_{1}} − k_{x_{2}})(n + 1) − 1 < n

and hence

k_{x_{1}} − k_{x_{2}} < 1.

which is in contradiction to (∗∗).

2. Assume that 0 < a ≤ b < 1. Consider the following system of inequalities which is equivalent to (∗):

\frac{1}{a} ≥ \frac{x_{2}}{x_{1}} ≥ \frac{1}{b}.

Then we have 1 < \frac{1}{b} ≤ \frac{1}{a} and we can follow the arguments of case 1.

□_{lemma 1.4.}

Lemma 1.5. Let z ∈ ℕ be given. Let n ≥ 2 and let f_{i}(x_{2}, …, x_{n}) : ℝ^{n−1} → ℝ, g_{i}(x_{2}, …, x_{n}) : ℝ^{n−1} → ℝ for 1 ≤ i ≤ z be given. Consider the following system of inequalities:

f_{i}(x_{2}, …, x_{n}) ≤ \frac{x_{1}}{x_{2}} ≤ g_{i}(x_{2}, …, x_{n}). (∗)

Let (∗) satisfy the following conditions:

1. ∃i_{1}, 1 ≤ i_{1} ≤ z, ∃ϵ_{1}, 0 < ϵ_{1} < 1, ∃c_{1} ∈ ℕ and ∃Δ^{1} : ℕ → [c_{1}] such that (∗) has no solution x_{1}, …, x_{n} which is monochromatic with respect to Δ^{1} and

f_{i_{1}}(x_{2}, …, x_{n}) ≤ ϵ_{1}.

2. ∃i_{2}, 1 ≤ i_{2} ≤ z, ∃ϵ_{2}, ϵ_{3}, 0 < ϵ_{2}, ϵ_{3} < 1, ∃c_{2} ∈ ℕ and ∃Δ^{2} : ℕ → [c_{2}] such that (∗) has no solution x_{1}, …, x_{n} which is monochromatic with respect to Δ^{2} and

f_{i_{2}}(x_{2}, …, x_{n}) ≤ 1 + ϵ_{2}

or there is no solution x_{1}, …, x_{n} which is monochromatic with respect to Δ^{2} and

g_{i_{2}}(x_{1}, …, x_{n}) ≥ ϵ_{3}.

3. ∃k ∈ ℕ, ∃c_{3} ∈ ℕ and ∃Δ^{3} : ℕ → [c_{3}] such that (∗) has no solution x_{1}, …, x_{n} which is monochromatic with respect to Δ^{3} and

\frac{x_{1}}{x_{2}} ≥ k.

Then there exists c^{∗} ∈ ℕ and a coloring Δ^{∗} : ℕ → [c^{∗}], such that (∗) has no solution which is monochromatic for Δ^{∗}.

Proof of lemma 1.5.: Let ϵ_{1}, ϵ_{2}, ϵ_{3}, k, c_{1}, c_{2}, c_{3} and Δ^{1}, Δ^{2}, Δ^{3} be defined as in the assumptions of lemma 1.13. Consider colorings of the form Δ^{a,b} which are defined as in the proof of lemma 1.11. (∗∗) with appropriate a and b, namely:

Δ^{4} = Δ^{\frac{1}{1−ϵ_{3}} , \frac{1}{ϵ_{1}}} : ℕ → [c_{4}],

where c_{4} ∈ ℕ is minimal such that \frac{1}{1−ϵ_{3}} ^{(c_{4}−1)} > \frac{1}{ϵ_{1}} and

Δ^{5} = Δ^{1+ϵ_{2},k} : ℕ → [c_{5}],

where c_{5} ∈ ℕ is minimal such that (1 + ϵ_{2})^{(c_{5}−1)} > k. Then define Δ^{∗} as follows:

Δ^{∗} : ℕ → ∏_{j=1}^{5}[c_{j}],

Δ^{∗}(x) = (Δ^{1}(x), Δ^{2}(x), Δ^{3}(x), Δ^{4}(x), Δ^{5}(x)).

We claim that (∗) has no solution which is monochromatic for Δ^{∗}. Assume on the contrary that x_{1}, …, x_{n} is a solution of (∗) which is monochromatic with respect to Δ^{∗}. Because x_{1}, …, x_{n} is monochromatic for Δ^{∗} it is monochromatic for Δ^{1}. Hence we have

f_{i_{1}}(x_{2}, …, x_{n}) ≥ ϵ_{1},

which implies

\frac{x_{1}}{x_{2}} ≥ ϵ_{1}. (1)

Besides x_{1}, …, x_{n} is monochromatic for Δ^{2}. Hence we have

f_{i_{2}}(x_{2}, …, x_{n}) ≥ 1 + ϵ_{2}

or

g_{i_{2}}(x_{2}, …, x_{n}) ≤ 1 − ϵ_{3},

which implies

\frac{x_{1}}{x_{2}} ≥ 1 + ϵ_{2} (2)

or

\frac{x_{1}}{x_{2}} ≤ 1 − ϵ_{3}. (3)

Finally x_{1}, …, x_{n} is monochromatic for Δ_{3} and therefore we have:

\frac{x_{1}}{x_{2}} ≤ k. (4)

If we put together (1) and (3) and (2) and (4) respectively, we obtain:

ϵ_{1} ≤ \frac{x_{1}}{x_{2}} ≤ 1 − ϵ_{3} (5)

or

1 + ϵ_{2} ≤ \frac{x_{1}}{x_{2}} ≤ k. (6)

By lemma 1.12. (5) has no monochromatic solution for Δ^{4} and (6) has no monochromatic solution for Δ^{5}. Hence x_{1}, …, x_{n} is not monochromatic for Δ^{∗}. That is in contradiction to our assumption.

□_{lemma 1.13.}

Now we are able to prove the second part of theorem 1.5., i.e. A has cpi if the system Ax⃗ ≤ 0 is partition regular.

Proof of theorem 1.3. (second part): We will prove the theorem by induction on the number of columns of A. Note that a system, which is partition regular, necessarily has a solution. n = 1 :

A = ( a_{11} ; a_{21} ; ⋮ ; a_{m1} )

The system (a_{i1}x_{1} ≤ 0)_{1≤i≤m} is partition regular. Hence it has a solution in ℕ, therefore for all 1 ≤ i ≤ m we have a_{i1} ≤ 0 and thus A has cpi with I_{0} = {1}. In order to demonstrate the idea of the proof we additionally consider the case n = 2 :

A = ( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \\ ⋮ & ⋮ \\ a_{m1} & a_{m2} \end{matrix} )

We distinguish the following cases:

1. For each row I 1 ≤ i ≤ m the first entry is less or equal zero, i.e. a_{i1} ≤ 0.

Let I_{0} = {1} and I_{1} = {2}. Assume that y_{1}, y_{2} ∈ ℕ form a solution of the system Ax⃗ ≤ 0. Then for all 1 ≤ i ≤ m we have

∑_{j∈I_{0}} c_{1j}a_{ij} + c_{1} ∑_{j∈I_{1}} a_{ij} = c_{11}a_{i1} + c_{1}a_{i2} ≤ 0

if we choose c_{11} = y_{1} and c_{1} = y_{2}.

2. For each row i 1 ≤ i ≤ m the first entry is greater or equal zero, i.e. a_{i1} ≥ 0.

In this case for all 1 ≤ i ≤ 0 we have a_{i2} ≤ 0

Then A has cpi with blocks I_{0} = {2} and I_{1} = {1}.

3. There exist s, t ∈ [m] such that a_{s1} < 0 and a_{t1} > 0.

Then the system Ax⃗ ≤ 0 can be transformed as follows:

−\frac{a_{t2}}{a_{t1}} ≤ \frac{x_{1}}{x_{2}} ≤ −\frac{a_{s2}}{a_{s1}}

for all t with a_{t1} < 0 and for all s with a_{s1} > 0 and

a_{t2}x_{2} ≤ 0 for all t with a_{t1} = 0.

By lemma 1.12. we know that one of the following cases holds:

(a) −\frac{a_{t2}}{a_{t1}} ≤ 0 for all t with a_{t1} < 0 and −\frac{a_{s2}}{a_{s1}} ≥ 0 for all s with a_{s1} > 0 and (obviously) a_{t2} ≤ 0 for all t with a_{t1} = 0. In this case for all 1 ≤ i ≤ m we obtain

a_{t2} ≤ 0.

Thus A has cpi with blocks I_{0} = {2} and I_{1} = {1}.

(b) −\frac{a_{t2}}{a_{t1}} ≤ 1 for all t with a_{t1} < 0 and −\frac{a_{s2}}{a_{s1}} ≥ 1 for all s with a_{s1} > 0 and hence for all 1 ≤ t ≤ m with a_{t1} ≠ 0 we have

a_{t1} + a_{t2} ≤ 0

and obviously for all 1 ≤ t ≤ m with a_{t1} = 0 we have

a_{t2} ≤ 0

and hence

a_{t1} + a_{t2} ≤ 0.

Thus A has cpi with I_{0} = {1, 2} in this case.

Hence we are done in the case n = 2. Let us assume that the theorem is true for all matrices A with less than n columns for some (fixed) n ≥ 2. Let

A = ( \begin{matrix}a_{11} & a_{12} & … & a_{1n} \\ a_{21} & a_{22} & … & a_{2n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{n1} & a_{n2} & … & a_{nm} \end{matrix} ) .

To prove the theorem we distinguish the following cases:

1. There exists 1 ≤ j^{∗} ≤ n such that for all 1 ≤ i ≤ m the j^{∗}th entry satisfies a_{ij^{∗}} < 0.

In this case let I_{0} = {j^{∗}} and I_{1} = [n] − {j^{∗}} and choose c_{1j^{∗}} > max_{1≤i≤m}\{^{\frac{∑_{s=1,s≠j^{∗}}^{n} |a_{is}|}{|a_{ij^{∗}} |}}\}, c_{1} = 1.

2. There exists 1 ≤ j^{∗} ≤ n such that for all 1 ≤ i ≤ m the j^{∗}th entry satisfies a_{ij^{∗}} ≤ 0.

Without loss of generality assume j^{∗} = 1 and a_{i1} < 0 for 1 ≤ i ≤ m_{1} and a_{i1} = 0 for m_{1} < i ≤ m for some m_{1} ≤ m. Then we have:

A = ( \begin{matrix}a_{11} < 0 ; ⋮ ; a_{1m_{1}} < 0 & ∗ \\ 0 ⋮ 0 & A′ \end{matrix} ) .

Hence A is partition regular if and only if A′ is partition regular. By induction A′ has cpi. Let the corresponding blocks be I′_{0}, … I′_{r} for a suitable r ∈ ℕ and for 1 ≤ k ≤ r and for j ∈ ∪_{s≤k}I_{s} let the coefficients be c′_{kj}, c′_{k}. Then A has cpi with blocks I_{0} = {1}, I_{s} = I′_{s−1} for 1 ≤ s ≤ r and coefficients

c_{k1} = \frac{max_{1≤i≤m_{1}}\{∑_{j∈∪_{s≤k}I′_{s}} c′_{kj}a_{ij} + c′_{k} ∑_{j∈I′_{k+1}} a_{ij}\}}{min_{1≤i≤m_{1}}|a_{1i}|}

for 2 ≤ k ≤ r and

c_{11} = \frac{max_{1≤i≤m_{1}} ∑_{j∈I′_{1}} a_{ij}}{min_{1≤i≤m_{1}}|a_{1i}|} ,

c_{1} = 1 and c_{kj} = c′_{k−1j} for all j ≠ 1 and all 1 ≤ k ≤ r.

Documenta Mathematica 3 (1998) 149–187

3. There exists j^{∗} such that for all 1 ≤ i ≤ m we have a_{ij^{∗}} ≥ 0.

In this case obviously A′ = A − {a^{(j^{∗})}}, the matrix which we obtain from A by omitting the column j^{∗}, is partition regular and has cpi by induction. Let the blocks of A′ be I′_{0}, … I′_{r} and define for all 1 ≤ s ≤ r I_{s} = I′_{s} and I_{r+1} = {j^{∗}}. Further let y_{1}, …, y_{n} ∈ ℕ be a solution of the system Ax⃗ ≤ 0. Then A has cpi with coefficients c_{rj} = y_{j} for j ≠ j^{∗}, and c_{r} = y_{j^{∗}}.

4. Each column has both positive and negative entries.

Let 1 ≤ k < l ≤ n be given. Then the system Ax⃗ ≤ 0 can be transformed as follows:

(∗) \{ \begin{matrix}−\frac{a_{sk}}{a_{sl}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{sj}}{a_{sl}} \frac{x_{j}}{x_{k}} ≤ \frac{x_{l}}{x_{k}} ≤ −\frac{a_{tk}}{a_{tl}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{sj}}{a_{sl}} \frac{x_{j}}{x_{k}} \\ for all s, t with a_{sl} < 0 and a_{tl} > 0, \\ ∑_{j=1,j≠l}^{n} a_{ij}x_{j} ≤ 0 \\ for all i with a_{il} = 0. \end{matrix}

By lemma 1.13. we know that one of the following cases holds:

(a) For all ϵ > 0 the following system of inequalities is partition regular:

−\frac{a_{sk}}{a_{sl}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{sj}}{a_{sl}} \frac{x_{j}}{x_{k}} ≤ ϵ for all s with a_{sl} < 0

−\frac{a_{tk}}{a_{tl}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{tj}}{a_{tl}} \frac{x_{j}}{x_{k}} ≥ 0 for all t with a_{tl} > 0

and

∑_{j=1,j≠l}^{n} a_{ij}x_{j} ≤ 0 for all i with a_{il} = 0.

That means that for every ϵ > 0 the system

A_{l}^{k}(ϵ)y⃗ ≤ 0

is partition regular and has cpi by induction. Hence by remark 1.8. A^{k}(ϵ) has cpi for all ϵ > 0.

(b) For all r > 0 and each coloring of the natural numbers with finitely many colors the system (∗) has a monochromatic solution x_{1}, …, x_{n} such that

\frac{x_{l}}{x_{k}} > r,

which is equivalent to

\frac{x_{k}}{x_{l}} < \frac{1}{r}.

We transform the system Ax⃗ ≤ 0 as in (∗) exchanging k and l. Then we obtain:

−\frac{a_{sl}}{a_{sk}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{sj}}{a_{sk}} \frac{x_{j}}{x_{l}} ≤ \frac{x_{k}}{x_{l}} ≤ −\frac{a_{tl}}{a_{tk}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{tj}}{a_{tk}} \frac{x_{j}}{x_{l}}

for all s, t with a_{sk} < 0 and a_{tk} > 0 and

∑_{j=1,j≠k}^{n} a_{ij}x_{j} ≤ 0

for all i with a_{ik} = 0. Therefore the following system is partition regular for each r > 0 :

−\frac{a_{sl}}{a_{sk}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{sj}}{a_{sk}} \frac{x_{j}}{x_{l}} ≤ \frac{1}{r}
for all 1 ≤ s ≤ m with a_{sk} < 0
−\frac{a_{tl}}{a_{tk}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{tj}}{a_{tk}} \frac{x_{j}}{x_{l}} ≥ 0
for all 1 ≤ t ≤ m with a_{tk} > 0 and
∑_{j=1,j≠k}^{n} a_{ij}x_{j} ≤ 0
for all 1 ≤ i ≤ m with a_{ik} = 0.

Hence the system A_{k}^{l}(\frac{1}{r}) is partition regular for every r > 0 and has cpi by induction. Therefore by remark 1.8. the system A^{l}(\frac{1}{r}) has cpi for every r > 0.

(c) For all ϵ > 0 the following system is partition regular:

(∗) \{ \begin{matrix}−\frac{a_{sk}}{a_{sl}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{sj}}{a_{sl}} \frac{x_{j}}{x_{k}} ≤ 1 + ϵ \\ for all 1 ≤ s ≤ m with a_{sl} < 0 \\ −\frac{a_{tk}}{a_{tl}} − ∑_{j=1,j∉\{k,l\}}^{n} \frac{a_{tj}}{a_{tl}} \frac{x_{j}}{x_{k}} ≥ 1 − ϵ \\ for all 1 ≤ t ≤ m with a_{tl} > 0 \\ ∑_{j=1,j≠l}^{n} a_{ij}x_{j} ≤ 0 \\ for all 1 ≤ i ≤ m with a_{il} = 0. \end{matrix}

Then for every ϵ > 0 the system A^{(k)+(l)}y⃗ ≤ 0 is partition regular and has cpi by induction, therefore by remark 1.8. A^{l}(ϵ) and A^{k}(ϵ) have cpi.

The system Ax⃗ ≤ 0 has a solution in ℕ because otherwise it could not be partition regular and hence A has the ϵ-property. Therefore by lemma 1.9. A has cpi.

□_{theorem 1.5.}

In the following we will generalize the set of partitioned numbers. We will first state results over ℤ and ℚ and finally we will consider real matrices and generalize the set of partitioned numbers to the reals.

Definition 1.5. Let K ⊂ ℝ − {0} be a set. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a matrix with entries in ℝ. A has the column property for systems of inequalities (cpi) over K if there exists l ∈ ℕ and a partition [n] = I_{0} ∪ I_{1} ∪ … ∪ I_{l} of the column indices such that

1. There exists c ∈ K such that for all 1 ≤ i ≤ m we have c ∑_{j∈I_{0}} a_{ij} ≤ 0 and

2. for all k < l, j ∈ ∪_{s≤k}I_{s} there exist c_{k}, c_{kj} ∈ K such that for all 1 ≤ i ≤ m we

have

∑_{j∈∪_{s≤k}I_{s}} c_{jk}a_{ij} + c_{k} ∑_{j∈I_{k+1}} a_{ij} ≤ 0.

And correspondingly we define:

Definition 1.6. Let K ⊂ ℝ − {0} be a set. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a real matrix. Let b⃗ = (b_{1}, …, b_{n}) ∈ ℝ^{n}. The system Ax⃗ ≤ b⃗ is called partition regular over K, if for every c ∈ ℕ and every c-coloring of K Δ : K → [c] there exists a solution x_{1}, … x_{n} ∈ K of Ax⃗ ≤ b⃗ such that Δ |_{{x_{1}...x_{n}}} = const.

Lemma 1.6. Let K ⊂ ℝ − {0} and K = K_{1} ∪ K_{2} such that K_{1} ∩ K_{2} = ∅. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a real matrix. Then the following statements are equivalent:

1. The system Ax⃗ ≤ 0 is partition regular over K.

2. The system Ax⃗ ≤ 0 is partition regular over K_{1} or the system is partition regular over K_{2}.

Proof of lemma 1.6.: If the system Ax⃗ ≤ 0 is partition regular over K_{1} or over K_{2} then it is clearly partition regular over K. For the opposite direction assume that the system Ax⃗ ≤ 0 is neither partition regular over K_{1} nor over K_{2}, i. e. there exists c_{1} ∈ ℕ and a coloring Δ_{1} : K_{1} → [c_{1}] and there exists c_{2} ∈ ℕ and a coloring Δ_{2} : K_{2} → [c_{2}], such that Ax⃗ ≤ 0 has no monochromatic solution in K_{1} for Δ_{1} and no monochromatic solution in K_{2} with respect to Δ_{2}. Define the following coloring: Δ : K → [max{c_{1}, c_{2}}] × [2] by

Δ(x) = \{ \begin{matrix}(Δ_{1}(x), 1) & if & x ∈ K_{1} \\ (Δ_{2}(x), 2) & if & x ∈ K_{2}. \end{matrix}

Obviously the system Ax⃗ ≤ 0 has no monochromatic solution with respect to the coloring Δ which is a contradiction to the partition regularity.

□_{lemma 1.6.}

If we use lemma 1.16. together with theorem 1.5. we obtain the following theorem:

Theorem 1.4. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix. The system Ax⃗ ≤ 0 is partition regular over ℤ − {0} if and only if A has cpi either over ℤ^{+} − {0} or over ℤ^{−} − {0}.

Proof of theorem 1.4.: By lemma 1.16. we know that the system Ax⃗ ≤ 0 is partition regular over ℤ − {0} iff it is either partition regular over ℤ^{+} − {0} or over ℤ^{−} − {0}. The first case is equivalent to A having cpi over ℕ by theorem 1.5. In the second case consider (∗) −Ax⃗ ≤ 0 where −A = (−a_{ij})_{1≤i≤m,1≤j≤n}. Ax⃗ ≤ 0 is partition regular over ℤ^{−} − {0} iff −Ax⃗ ≤ 0 is partition regular over ℕ. This is equivalent to −A having cpi over ℕ, which is equivalent to A having cpi over ℤ^{−}−{0}.

□_{theorem 1.4.}

Theorem 1.5. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix. Then the following statements are equivalent:

1. The system Ax⃗ ≤ 0 is partition regular over ℚ − {0}.

2. A has cpi over ℚ^{+} − {0} or over ℚ^{−} − {0}.

3. A has cpi over ℤ^{+} − {0} or over ℤ^{−} − {0}.

Proof of theorem 1.5. :

1. implies 2.: It is enough to show that if Ax⃗ ≤ 0 is partition regular over ℚ^{+} − {0} then it has cpi over ℚ^{+} − {0}. This can be shown following the arguments of the second part of the proof of theorem 1.5. using Q^{+} − {0} instead of ℕ.

2. implies 3.: Assume that A has cpi over ℚ^{+} − {0}, i. e. there exists a partition of the columns of A into blocks [n] = I_{0} ∪ … ∪ I_{l} such that

1. There exists q ∈ ℚ^{+} − {0} such that for all 1 ≤ i ≤ m we have q ∑_{j∈I_{0}} a_{ij} ≤ 0, i. e. ∑_{j∈I_{0}} a_{ij} ≤ 0.

2. For k < l, j ∈ ∪_{s≤k}I_{s} there exist c_{kj}, c_{k} ∈ ℚ^{+} − {0} such that for all 1 ≤ i ≤ m

we have

∑_{j∈∪_{s≤k}I_{s}} c_{kj}a_{ij} + c_{k} ∑_{j∈I_{k+1}} a_{ij} ≤ 0.

By multiplying the above inequality with the common divisor of c_{kj}, c_{k} we obtain positive integer coefficients.

3. implies 1.: If A has cpi over ℤ^{+} − {0} or over ℤ^{−} − {0} then by theorem 1.17. the system Ax⃗ ≤ 0 is partition regular over ℤ − {0}. Hence it is partition regular over ℚ − {0}.

□_{theorem 1.5.}

Theorem 1.6. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a real matrix. Then the following statements are equivalent:

1. The system Ax⃗ ≤ 0 is partition regular over ℝ − {0}.

2. A has cpi over ℝ^{+} − {0} or over ℝ^{−} − {0}.

Proof of theorem 1.6. :

1. implies 2.: It is enough to show that if the system Ax⃗ ≤ 0 is partition regular over ℝ^{+} −{0} then A has cpi over ℝ^{+} − {0}. This can be shown following the arguments of the second part of the proof of theorem 1.5. using ℝ^{+} − {0} instead of ℕ.

2. implies 1. : Again it is enough to show that if A has cpi over ℝ^{+} − {0} then the system Ax⃗ ≤ 0 is partition regular over ℝ^{+} − {0}. To prove this we employ a generalized environment lemma using the multidimensional version of van der Waerden’s Theorem which is due independently to Gallai (see [10]) and Witt [16] instead of van der Waerden’s Theorem [15]:

Lemma 1.7. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a real matrix such that the system Ax⃗ ≤ 0 is partition regular over R^{+} − {0}. Let t ∈ ℕ and W ⊂ ℝ, W = {w_{1}, … w_{t}} be given. Let c ∈ ℕ. Then for every c-coloring Δ : ℝ^{+} − {0} → [c] there exists x⃗ = (x_{0}, …, x_{n}) ∈ (ℝ^{+} − {0})^{n} and there exists r ∈ R^{+} − {0} such that

1. Ax⃗ ≤ 0 and

2. For all j, k with 1 ≤ j ≤ n, 1 ≤ k ≤ t we have Δ(x_{j} + rw_{k}) = const.

Proof of lemma 1.7.: Assume that A is partition regular. Hence by compactness [6] there exists a finite set V = V (A, c) ⊂ ℝ^{+} − {0} such that for every c-coloring of V there exists a monochromatic solution of the system Ax⃗ ≤ 0 in V. Let V = {v_{1}, …, v_{t}}. Let Δ : ℝ^{+}−{0} → [c] be an arbitrary coloring. Define a coloring Δ^{∗} : ℝ^{+}−{0} → [c^{t}] by

Δ^{∗}(x) = (Δ(xv_{i}))_{1≤i≤t}.

Define a finite set W = {w|w = ∏_{s=1}^{n} v_{j_{s}}, j_{s} ∈ [t]}. By Gallai-Witt’s Theorem there exists a homothetic copy of the set W which is monochromatic with respect to Δ^{∗}, say W′ = a′ + r′W = {a′ + r′w|w ∈ W }. Consider another coloring Δ^{∗∗} :V→ [c] which is defined by Δ^{∗∗}(x) = Δ(a′x). By definition of V there exists a monochromatic solution of the system Ax⃗ ≤ 0 in V with respect to Δ^{∗∗}, say x′_{1}, …, x′_{n}. Then (x′_{1}a′, …, x′_{n}a′) is a solution and for all 1 ≤ j ≤ n we have Δ(x′_{j}a′) = const. Let r = r′x′_{1} … x′_{n}. Then we have:

x′_{i}a′ + rv_{j} = x′_{i}(a′ + r′v_{j}x′_{1} · . . . · x′_{i−1}x′_{i+1} · . . . · x′_{n})

and by the definition of W

(v_{j}x′_{1} · . . . · x′_{i−1}x′_{i+1} · . . . · x′_{n}) ∈ W.

Hence for all 1 ≤ i ≤ n, 1 ≤ j ≤ t we finally have

Δ(x′_{i}a′) = Δ(x′_{i}a′ + rv_{j}).
□_{lemma 1.7.}

Now we are able to prove the second part of theorem 1.19.:

Let A be a real matrix which has cpi over ℝ^{+} − {0}. Let [n] = I_{0} ∪ … ∪ I_{l} be the corresponding partition. We prove theorem 1.19. by main induction over the number of colors and by subsidiary induction over the number of blocks. In both cases the start of the induction is easy to obtain: The system Ax⃗ ≤ 0 has a solution (just take the coefficients c_{jl−1}, c_{l}). If only one color is used every solution is monochromatic. If l = 0 every singleton provides a solution.

Let A_{k} = (a^{(j)}|j ∈ ∪_{j≤k}I_{k}) be the submatrix of A which only consists of the columns belonging to the first k blocks. Assume that A_{k} is partition regular over ℝ^{+} − {0} for some k ≥ 0 and assume that for every coloring with c − 1 colors the system (∗) A_{k+1}x⃗ ≤ 0 has a monochromatic solution, i. e. by compactness there exists a finite set V_{c−1} ⊂ ℝ^{+} − {0} such that for every (c − 1)-coloring (∗) has a monochromatic solution in V_{c−1}.

Let Δ : ℝ^{+} − {0} → [c] be an arbitrary coloring. We define W, a finite subset of ℝ, by W = {w = vu|v ∈ V, u ∈ {c_{jk}, c_{k}|1 ≤ j ≤ n, 1 ≤ k < l}}. We apply lemma 1.20. to A_{k} and W. Thus there exists a solution (y_{i})_{i∈∪_{s≤k}I_{s}} of the system A_{k}y⃗ ≤ 0 and r ∈ ℝ^{+} − {0} such that for all i ∈ ∪_{s≤k}I_{s} and all w ∈ W we have Δ(y_{i} + rw) = const. Combining cpi and the fact that the y_{i} form a solution for every v ∈ V we obtain:

∑_{j∈∪_{s≤k}I_{s}} a_{ij}(y_{j} + c_{kj}rv) + ∑_{j∈I_{k+1}} a_{ij}c_{k}rv ≤ 0.

Without loss of generality we may assume that Δ(y_{i} + rc_{kj}v) = c for all i ∈ ∪_{s≤k}I_{s} and v ∈ V. If now one of the numbers c_{k}rv is also colored in c we have found a monochromatic solution of the system A_{k+1}x⃗ ≤ 0. Otherwise the coloring

Δ^{∗} : V → [c − 1]

defined by

Δ^{∗}(x) = Δ(xrc_{k})

is well defined. Therefore by induction on the number of colors and the definition of V there exists a monochromatic solution of A_{k+1}x⃗ ≤ 0 with respect to Δ^{∗}, say (x_{i}^{∗})_{i∈∪_{s≤k+1}I_{s}}. Then (x_{i}^{∗}rc_{k})_{i∈∪_{s≤k+1}I_{s}} forms a solution which is monochromatic with respect to Δ.

□_{theorem 1.6.}

In his dissertation [10] Rado also considered systems of inhomogeneous equations. As well as for homogeneous systems the columns property plays an important role for the characterization of partition regular systems of inhomogeneous inequalities. We are able to give a complete characterization of those systems which are partition regular over the natural numbers, over the set of integers and over the rationals.

Theorem 1.7. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix, let b⃗ = (b_{1}, …, b_{m}) ∈ ℚ^{m}. The system of inequalities Ax⃗ ⊆ 0 is partition regular over ℕ if and only if one of the following conditions is satisfied:

1. There exists a ∈ ℕ such that A ( a ; ⋮ ; a ) ≤ \overrightarrow{b}

2. A has cpi and there exists \overrightarrow{x} = (x_{1}, …, x_{n}) ∈ ℕ^{n} and there exists I ⊆ [m],

such that ∑_{j=1}^{n} a_{ij}x_{j} \{ \begin{matrix}< 0 & for & i ∈ I \\ ≤ 0 & for & i ∈ [m] − I. \end{matrix}

and there exists a ∈ ℤ such that for all i ∈ [m] − I we have ∑_{j=1}^{n} a_{ij}a ≤ b_{i}

The proof of theorem 1.21 is a little bit tricky and in its main parts very technical. The interested reader can find the complete proof in [17].

Theorem 1.8. Set A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix and b⃗ = (b_{1}, …, b_{m}) ∈ ℚ^{m}. The system Ax⃗ ≤ b⃗ is partition regular over ℚ − {0} if and only if Ax⃗ ∈ b⃗ is partition regular over ℕ or the system −A⃗x⃗ ≤ b⃗ with −A = (−a_{ij})_{1≤i≤m,1≤j≤n} is partition regular over ℕ.

If we partition the set ℚ − {0} the situation is different:

Theorem 1.9. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix, let b⃗ = (b_{1}, …, b_{n}) ∈ ℚ^{n}. The system (x)Ax⃗ ≤ b⃗ is partition regular over ℚ if and only if one of the following cases is valid:

1. There exists a^{∗} ∈ ℚ such that for all 1 ≤ i ≤ m we have ∑_{j=1}^{n} a_{ij}a^{∗} ≤ b_{i}

2. There exists I ⊆ [m] such that b_{i} ≥ 0 for i ∈ I, b_{i} > 0 for i ∈ [m]J − I and the matrix A_{I} = (a_{ij})_{i∈I,1≤j≤n} has cpi over ℚ^{+} − {0}.

3. A has cpi over ℚ^{+} − {0} and there exists I ⊆ [m] and there exists x⃗(x_{1} − x_{n}) ∈ (ℚ^{+} − {0}^{n} such that

∑_{j=1}^{n} a_{ij}x_{j} \{ \begin{matrix}< 0 & for & i ∈ I \\ ≤ 0 & for & i ∈ [m] − I. \end{matrix}

and there exists a^{x} ∈ ℚ^{+}−{0} such that for all i ∈ [m]−I we have ∑_{j=1}^{n} a_{ij}a^{∗} ≤ b_{i}.

4. −A = (−a_{ij})_{1≤i≤m,1≤j≤n} fulfills condition 1, 2, or 3.

2. (m, p, c)-sets

In 1973 Deuber [1] gave a semantical characterization of partition regular system of linear equations. The nature of this characterization is somewhat different form Rado’s approach. Deuber described the arithmetic structure of the sets of solutions of partition regular linear systems Ax⃗ = 0. The central definition is that of (m, p, c,)- sets, which are m-fold arithmetic progressions together with c-fold differences:

Definition 2.1. Let m, p, c ∈ ℕ. A set D ⊆ ℕ is an (m, p, c)-set if there exist d_{0}, …, d_{m} ∈ ℕ such that D = D_{p,c}(d_{0} … d_{m}) consists of all numbers of the following list:

cd_{0} + l_{1}d_{1} + l_{2}d_{2} + … + l_{m}d_{m},
cd_{1} + l_{2}d_{2} + … + l_{m}d_{m},
cd_{2} + … + l_{m}d_{m},
⋮
cd_{m},

where l_{i} ∈ [−p, p], i. e.

D_{p,c}(d_{0}, …, d_{m}) = {cd_{i} + ∑_{j=i+1}^{m} l_{j}d_{j}|i ≤ m, l_{j} ∈ [−p, p]}.

In particular a (1, k, c)-set is a (2k + 1)-term arithmetic progressions together with its differences. Deuber proved the following theorem [1]:

Theorem 2.1. (Deuber 1973) A linear system Ax⃗ = 0 is partition regular if and only if there exist positive integers m, p, c such that every (m, p, c)−set D contains a solution of Ax⃗ = 0.

(m, p, c)-sets not only describe the arithmetic structure of sets of solutions of partition regular systems of linear equations but they can also be used to characterize sets of solutions of systems of linear inequalities.

Theorem 2.2. Let A = (a_{ij})_{1≤i≤l,1≤j≤n} be a rational matrix. Let Ax⃗ ≤ 0 be a partition regular system of linear inequalities. Then there exist m, p, c ∈ ℕ such that every (m, p, c)-set contains a solution of the system Ax⃗ ≤ 0.

Proof of Theorem 2.2.: By theorem 1.5. we know that A has cpi, i. e. there exists m ∈ ℕ and a partition I_{0} ∪ … ∪ I_{m} = [n] such that

1. for all 1 ≤ i ≤ l we have ∑_{j∈I_{0}} a_{ij} ≤ 0 and

2. for k ≤ m and j ∈ ∪_{s≤k}I_{s} there exist c_{kj}, c_{k} ∈ ℕ such that for every k < m and for all 1 ≤ i ≤ l we have

∑_{j∈∪_{s≤k}I_{s}} c_{kj}a_{ij} + c_{k} ∑_{j∈I_{k+1}} a_{ij} ≤ 0.

Let c be the least common multiple of {c_{k}|1 ≤ k < m}. Multiply each inequality by \frac{c}{c_{k}} such that for all 1 ≤ i ≤ l we have

∑_{j∈∪_{s≤k}I_{s}} c′_{kj}a_{ij} + c ∑_{j∈I_{k+1}} a_{ij} ≤ 0.

Further let p = max_{1≤i≤l,1≤k<m}|c′_{kj}|. We claim that these m, p, c have the desired properties. Let A_{k} = (a_{ij})_{1≤i≤m,j∈∪_{s≤k}I_{s}} be the submatrix of A which only consists of the columns of A belonging to the blocks one up to k. We will prove the claim by induction on m. Let m = 0. Hence A = A_{0}, i. e. for all 1 ≤ i ≤ l we have ∑_{j=1}^{n} a_{ij} ≤ 0. Thus every singleton forms a solution of the system Ax⃗ ≤ 0 and D_{pc}(d_{0}) = {cd_{0}} ≠ ∅. Assume that the statement is true for some k ≥ 0. Consider a (k + 1, p, c)-set D = D_{p,c}(d_{0}, …, d_{k+1}). By induction we know that the (k, p, c)-set D_{p,c}(d_{0}, …, d_{k}) contains a solution of the system A_{k}x⃗ ≤ 0. Let (y_{i})_{i∈∪_{s≤k}I_{s}} be such a solution, i. e. y_{i} ∈ D_{p,c}(d_{0}, …, d_{k}) and for all 1 ≤ i ≤ l we have

∑_{j∈∪_{s≤k}I_{s}} a_{ij}y_{j} ≤ 0,

which implies

\underbrace{∑_{j∈∪_{s≤k}I_{s}} a_{ij}y_{j}}_{≤0} + \underbrace{d_{k+1}( ∑_{j∈∪_{s≤k}I_{s}} c_{kj}a_{ij} + c ∑_{j∈I_{k+1}} a_{ij})}_{≤0} ≤ 0.

Hence for all 1 ≤ i ≤ l we have

∑_{j∈∪_{s≤k}I_{s}} a_{ij}(y_{j} + d_{k+1}c_{kj}) + ∑_{j∈I_{k+1}} cd_{k+1}a_{ij} ≤ 0.

For y_{j} ∈ D_{p,c}(d_{0}, …, d_{k}) and |c_{kj}| ≤ p we have

y_{i} + c_{kj}d_{k+1} ∈ D_{p,c}(d_{0}, …, d_{k+1}) and
cd_{k+1} ∈ D_{p,c}(d_{0}, …, d_{k+1}).

Hence we found a solution of the system A_{k+1}x⃗ ≤ 0 in the arbitrary chosen (k+1, p, c)- set D_{p,c}(d_{0}, …, d_{k+1}). □_{T heorem 2.2.}

Theorem 2.3. Let A = (a_{ij})_{1≤i≤m,1≤j≤n} be a rational matrix. If there exist m, p, c ∈ ℕ such that every (m, p, c)−set contains a solution of the system Ax⃗ ≤ 0 then the system Ax⃗ ≤ 0 is partition regular.

Proof of Theorem 2.3.: Let m, p, c ∈ ℕ be given such that every (m, p, c)−set contains a solution of the system Ax⃗ ≤ 0. By Deuber’s theorem [1] we know that for every coloring Δ of the natural numbers with finitely many colors there exist d_{0} … d_{m} such that the (m, p, c)-set D = D_{p,c}(d_{0}, …, d_{m}) is monochromatic with respect to Δ. For every (m, p, c)-set contains a solution of the system Ax⃗ ≤ 0, so does D and hence Ax⃗ ≤ 0 is partition regular.

□_{theorem 3.4.}

Deuber [1] also proved a partition theorem for (m, p, c)−sets in order to resolve the following conjecture Rado stated 1933 [10].

Call a subset S ⊆ ℕ partition regular if every partition regular system of linear equations can be solved in S. Rado conjectured that coloring a partition regular set S there is one color class which is again partition regular.

Theorem 2.4. (Deuber 1973) Let m, p, c and r be positive integers. Then there exist positive integers n, q, d such that for every (n, q, d)-set D ⊆ ℕ and every rcoloring Δ → [r] there exists a monochromatic (m, p, c)−set D′ ⊆ D.

We can enlarge the definition of a partition regular set [1] to systems of linear inequalities:

Definition 2.2. Call a subset S ⊆ ℕ partition regular for systems of inequalities (pri) if every partition regular system of inequalities Ax⃗ ≤ 0 can be solved in S.

Note that for matrices A and B having cpi over ℕ also the direct sum

( \begin{matrix}A & 0 \\ 0 & B \end{matrix} )

has cpi over ℕ.

Theorem 2.5. For every coloring of a pri set with finitely many colors at least one of the color classes again is partition regular for inequalities.

Proof of Theorem 2.5.: Assume that the statement is false, i. e. there exists a set S ⊆ ℕ which is pri and there exists r ∈ ℕ and a coloring Δ : S → [r] such that no color class of Δ is pri. Thus for each color class i there exists a matrix A_{i} such that the system A_{i}x⃗ ≤ 0 is partition regular but has no solution in Δ^{−1}(i). Consider the system

(∗)  ( \begin{matrix}A_{1} & 0 & 0 & … & 0 \\ 0 & A_{2} & 0 & … & 0 \\ ⋮ & & ... & & ⋮ \\ 0 & … & & ... & 0 \\ 0 & … & & 0 & A_{r} \end{matrix} ) x⃗ ≤ 0.

(∗) is partition regular therefore there exist m, p, c ∈ ℕ such that every (m, p, c)−set contains a solution of (∗). By Deuber’s theorem [1] there exist n, q, d ∈ ℕ such that each coloring of an arbitrary (n, q, d)−set with finitely many colors contains a monochromatic (m, p, c)−set. For S is pri, it contains a (n, q, d)−set. Hence there is some (m, p, c)−set in S which is monochromatic with respect to Δ and thus there exists a monochromatic solution of (∗) in S which contradicts the definition of (∗).

□_{theorem 2.5.}

3. Canonical Results

In this chapter we want to extend our considerations to colorings with an unlimited number of colors. Call a coloring Δ of a set S canonical if Δ is either 1. monochromatic, i. e. for all s, t ∈ S it holds Δ(s) = Δ(t) or

2. distinct, i.e. for all s, t ∈ S with s ≠ t it holds Δ(s) ≠ Δ(t).

In 1950 Erdös and Rado [4] proved a canonical version of Ramsey’s theorem:

Theorem 3.1. (Erdös, Rado 1950) If an infinite set S is colored then some infinite subset T is canonically colored. For all k ∈ ℕ if |S| > (k − 1)^{2} + 1 and S colored there exists a subset T ⊆ S, |T | = k which is canonically colored.

Later Erdös and Graham [3] proved a canonical version of van der Waerden’s theorem, i. e. for every k ∈ ℕ and every coloring of the positive integers there exists a canonically colored k-term arithmetic progression. In 1986 Lefmann [7] extended the Erdös-Graham canonical theorem for arithmetic progressions to a canonical partition theorem for (m, p, c)−sets and partition regular systems of linear equations.

Let D = D_{p,c}(d_{0}, …, d_{m}) = {cd_{i} + ∑_{j=i+1}^{m} l_{j}d_{j}|i ≤ m, l_{j} ∈ [−p, p]}. Say that the elements of the form cd_{i}+l_{i+1}d_{i+1}+…+l_{m}x_{m} belong to the ith row of the (m, p, c)−set D_{p,c}(d_{0}, …, d_{m}). Let us further say that Δ : D_{p,c}(d_{0}, …, d_{m}) → ω is a row-coloring provided that any two numbers a, b ∈ D_{p,c}(d_{0}, …, d_{m}) are colored the same if and only if they belong to the same row of D_{p,c}(d_{0}, …, d_{m}). Lefmann proved the following theorem [7]:

Theorem 3.2. (Lefmann 1986) Let m, p, c ∈ ℕ. Then there exists a least positive integer L(m, p, c) with the following property: For every coloring Δ : [L(m, p, c)] → ω there exists a (m, p, c)-set D_{p,c}(d_{0}, …, d_{m}) ⊆ [L(m, p, c)] such that Δ |_{D_{p,c}(d_{0},...,d_{m})} either is a canonical coloring or a row-coloring.

As a corollary Lefmann [7] proved a canonical version of Rado’s theorem:

Corollary 3.1. (Lefmann) Let A = (a_{ij})_{1≤i≤l,1≤j≤n} be an integer valued matrix having the column property, i. e. the system of linear equations Ax⃗ = 0 is partition regular. Let I_{0} ∪ … ∪ I_{m} = [n] be the corresponding partition of the columns of A into blocks. Then there exists a positive integer N ∈ ℕ such that for every coloring Δ : [N] → ω there exists a solution x⃗ = (x_{1} … x_{n}) such that one of the following cases holds:

1. Δ |_{{x_{1},...,x_{n}}} is a canonical coloring.

2. Each two elements x_{i}, x_{j} of {x_{1}, …, x_{n}} are colored the same if and only if {i, j} ⊆ I_{k} for some k ≤ m.

In the following we will prove a canonical theorem for systems of linear inequalities, which is similar to the above canonical version of Rado’s theorem.

Theorem 3.3. Let A = (a_{ij})_{1≤i≤l,1≤j≤n} be a rational matrix and let the system Ax⃗ ≤ 0 be partition regular, i. e. A has cpi. Let I_{0}∪…∪I_{m} = [n] be the corresponding partition of the columns of A into blocks. Then for every coloring Δ : ℕ → ω of the natural numbers there exists a solution x⃗ = (x_{1} …, x_{n}) ∈ ℕ^{n} such that one of the following cases is valid:

1. Δ |_{{x_{1},...,x_{n}}} is a canonical coloring

2. Δ(x_{i}) = Δ(x_{j}) for some i, j ∈ [n] if and only if there exists some k ≤ m such that i, j ∈ I_{k}.

Proof of theorem 3.3.: The system Ax⃗ ≤ 0 is partition regular. Thus by theorem 3.3. there exist positive integers m, p, c such that every (m, p, c)−set contains a solution of the system Ax⃗ ≤ 0. In the proof of lemma 3.3. in chapter 3 we saw that a solution of Ax⃗ ≤ 0 in an arbitrary (m, p, c)−set D can be constructed in such a way that for i ∈ I_{l} x_{i} comes from the lth row of D. Let Δ : ℕ → ω be given. Theorem 4.2. gives us a (m, p, c)−set D_{p.c}(d_{0}, …, d_{m}) such that Δ |_{D_{p,c}(d_{0},...,d_{m})} either is a canonical or a row-coloring. Let y⃗ = (y_{1} … y_{n}) be a solution of the system Ax⃗ ≤ 0 such that for all 1 ≤ i ≤ n we have y_{i} ∈ D_{p,c}(d_{0}, …, d_{m}) and for i ∈ I_{k} y_{i} belongs to the kth row of D_{p,c}(d_{0}, …, d_{m}). If D_{p,c}(d_{0}, …, d_{m}) is canonically colored then Δ |_{{y_{1},...,y_{n}}} is a canonical coloring and if Δ |_{D_{p,c}(d_{0},...,d_{m})} is a row coloring then Δ(y_{i}) = Δ(y_{j}) if and only if y_{i} and y_{j} belong to the same row of D_{p,c}(d_{0}, …, d_{m}), i. e. if and only if i and j belong to the same block I_{k} for some k ≤ m.

□_{theorem 3.3.}

References

[1] W. Deuber: Partitionen und lineare Gleichungssysteme, Math. Z. 133, 1973, 109-123.

[2] W. Deuber: Developments Based on Rado’s Dissertation ‘Studien zur Kombinatorik’, London Math. Soc. Lecture Note Ser. 141, Surv. in Comb., 1989, 52-74.

[3] P. Erdös, R. L. Graham: Old and New Problems and Results in Combinatorial Number Theory, L’Enseign. Math., Geneve 1980.

[4] P. Erdös, R. Rado: A Combinatorial Theorem, J. London Math. Soc., 25, 1950, 245-255.

[5] R. L. Graham, K. Leeb, B. L. Rothschild: Ramsey’s Theorem for a Class of Categories, Adv. in Math. 8, 1972.

[6] R. L. Graham, B. L. Rothschild and J. H. Spencer: Ramsey Theory, John Wiley, New York, 1980.

[7] H. Lefmann: A Canonical Version for Partition Regular Systems of Linear Equations, J. Combin. Theory Ser. A. 41, 1986, 95-104.

[8] H. J. Prömel, B. Voigt: Aspects of Ramsey-Theory I: Sets, Report No 87495-OR, Forschungsinstitut für diskrete Mathematik, Rheinische Friedrich-Wilhelms-Universität Bonn, 1989 [9] H. J. Prömel, B. Voigt: Aspects of Ramsey-Theory II: Arithmetic Progressions,

Report No 87497-OR, Forschungsinstitut für diskrete Mathematik, Rheinische Friedrich-Wilhelms-Universität Bonn, 1989

[10] R. Rado: Studien zur Kombinatorik, Math. Z. 36, 1933, 424-480.

[11] R. Rado: Note on Combinatorial Analysis, Proc. London Math. Soc. 48, 1943, 122-160.

[12] F. P. Ramsey: On a Problem of Formal Logic, Proc. London Math. Soc. 30, 1930, 264-286.

[13] S. Shelah: A Finite Partition Theorem with Double Exponential Bounds, Institute of Math., Hebrew University Jerusalem, 1994.

[14] I. Schur: Über die Kongruenz x^{m} + y^{m} = z^{m}(modp), J.ber. d. Dt. Math.-Verein. 25, 1917, 114-117.

[15] B. L. van der Waerden: Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk. 15, 1927, 212-216.

[16] E. Witt: Ein Kombinatorischer Satz der Elementargeometrie, Math. Nachr. 6, 1951, 261-262.

[17] Meike Schäffler: Partition Regular Systems of Linear Inequalities, Dissertation Fakultät für Mathematik Universität Bielefeld, 1997. Cf. SFB 343, Diskrete Strukturen in der Mathematik, Preprintreihe, Ergänzungsreihe 97 - 002, Universität Bielefeld.

Meike Schäffler

Am Schormanns Busch 34 32107 Bad Salzuflen Germany 188

Documenta Mathematica 3 (1998)