# A Multidimensional Rado Theorem

Aaron Robertson

###### Abstract

We extend Deuber’s theorem on $(m,p,c)$-sets to hold over the multidimensional
positive integer lattices. This leads to a multidimensional Rado theorem where
we are guaranteed monochromatic multidimensional points in all finite
colorings of $\left(\mathbb{Z}^{+}\right)^{d}$ where the $i^{\mathrm{th}}$ set
of coordinates satisfies the $i^{\mathrm{th}}$ given linear Rado system.

title = A Multidimensional Rado Theorem, author = Aaron Robertson, keywords =
Ramsey theory, Rado’s Theorem,

[classification=text]

##  1 Introduction

Rado’s Theorem [8] completely characterizes which linear systems have the
property that any finite coloring of $\mathbb{Z}^{+}$ admits a monochromatic
solution to the linear system. In some sense, this makes such a linear system
“unbreakable” via partitioning. This characterization of linear systems is
given in the following definition.

######  Definition 1 (Columns Condition).

Let $A$ be an $\ell\times k$ matrix with column vectors
$\mathbf{c}_{1},\mathbf{c}_{2},\dots,\mathbf{c}_{k}$. We say that $A$
satisfies the columns condition if, after renumbering if necessary, there
exist indices $i_{0}=0<i_{1}<i_{2}<\cdots<i_{m}=k$ such that, for

$\mathbf{s}_{j}=\sum_{i=i_{j-1}+1}^{i_{j}}\mathbf{c}_{i},\qquad 1\leq j\leq
m,$

the following hold:

  1. 1.

$\mathbf{s}_{1}=\mathbf{0}\in\mathbb{Z}^{\ell}$;

  2. 2.

for $2\leq j\leq m$ we can write $\mathbf{s}_{j}$ as a linear combination over
$\mathbb{Q}$ of $\mathbf{c}_{1},\dots,\mathbf{c}_{i_{j-1}}$.

With this definition, we can state Rado’s Theorem.

######  Theorem 2 (Rado’s Theorem [8]).

Let $r\in\mathbb{Z}^{+}$ and let $A\mathbf{v}=\mathbf{0}$ be a system of
equations, where $A$ is a matrix with integer coefficients. Any $r$-coloring
of $\mathbb{Z}^{+}$ admits a monochromatic solution to the system if and only
if $A$ satisfies the columns condition.

A linear system $A\mathbf{v}=\mathbf{0}$ for which $A$ satisfies the columns
condition will be referred to as being a Rado system. For example,
$A=[1\,\,1\dots 1\,\,-1]$, which corresponds to the single-equation system
$\sum_{i=1}^{k-1}x_{i}=x_{k}$, is a Rado system and is often referred to as
the generalized Schur equation (Schur’s Theorem, which predates Rado’s result,
deals with the case $x_{1}+x_{2}=x_{3}$).

Recently, Balaji, Lott, and Rice [1] extended the generalized Schur’s Theorem
(see [11], [2], [10]) to hold over multidimensional positive integer lattices
by considering solutions to $\sum_{i=1}^{k-1}x_{i}=x_{k}$ with
${x_{i}}\in[1,n]^{d}$ instead of $[1,n]$, where $[1,n]=\\{1,2\dots,n\\}$. Can
this be extended to different linear systems? Moreover, could we possibly have
different sets of coordinates satisfy different linear systems and still
guarantee monotonicity?

We do know that van der Waerden’s Theorem [13], which states that any finite
coloring of $\mathbb{Z}^{+}$ admits arbitrarily long monochromatic arithmetic
progressions, has a multidimensional analog (in [9], Rado gives credit to
Grünwald, the last name of Gallai at the time; see also [12]) along with a
multidimensional polynomial analog [3]. Key to the proof of the
multidimensional van der Waerden Theorem is the translation-invariant property
of arithmetic progressions. In this sense, this multidimensional analog is
more geometric and less about the linear system.

Our goal here is about generalizing linear systems to multidimensional space.
As a motivating question, consider the following.

######  Question.

Does there exist a minimum integer $n$ such that for every $2$-coloring of
$[1,n]\times[1,n]$ there exist $a,b,x,d\in\mathbb{Z}^{+}$ with
$(a,x),(b,x+d),$ and $(a+b,x+2d)$ all the same color?

Notice that we are asking for the first coordinates to form a Schur triple and
for the second coordinates to form a 3-term arithmetic progression. In one
dimension, by considering the system of equations
$\\{x_{1}+x_{2}-x_{3}=0,x_{5}-x_{4}-d=0,x_{6}-x_{5}-d=0\\}$ (with $d$ a
variable), Rado’s Theorem informs us that we can guarantee a monochromatic
Schur triple and monochromatic 3-term arithmetic progression of the same color
under any finite coloring of $\mathbb{Z}^{+}$. However, there does not seem to
be a bijection $\mathbb{Z}^{+}\times\mathbb{Z}^{+}\rightarrow\mathbb{Z}^{+}$
that preserves the linear system’s solutions with well-defined colorings; such
a bijection would guarantee an answer to our question in $2$-dimensions via an
appeal to Rado’s Theorem.

In general, we investigate here which linear systems have the Rado property
under partitioning, not of $\mathbb{Z}^{+}$, but of
$\left(\mathbb{Z}^{+}\right)^{d}$. To discuss the multidimensional situation,
we will use the following notation and language to distinguish from the
classical (1-dimensional) case.

Notation. For $X\\!=\\![x_{ij}]$ a $d\times k$ matrix, we refer to
$\mathbf{p}_{j}=(x_{1j},x_{2j},\dots,x_{dj})^{\intercal}\in\left(\mathbb{Z}^{+}\right)^{d}$
as points and to
$\mathbf{x}_{i}=(x_{i1},x_{i2},\dots,x_{ik})\in\left(\mathbb{Z}^{+}\right)^{k}$
as the $i^{\mathit{th}}$ coordinates vector. To generalize a linear system to
address the motivating question above, we seek to find, for given matrices
$A_{i}$, a set of $k$ monochromatic points $\mathbf{p}_{j}$ such that

$A_{i}\mathbf{x}_{i}^{\intercal}={\mathbf{0}}\mbox{ for all
$i\in\\{1,2,\dots,d\\}$}.$ (1)

In other words, the $i^{\mathrm{th}}$ row of $X$ satisfies the linear system
$A_{i}{\mathbf{v}}=0$. We will refer to (1) as a $d$-dimensional linear vector
system or simply a linear vector system if the dimensionality is clear. In the
situation where $A_{1}=A_{2}=\cdots=A_{d}=A$, the equations in (1) can be
written as $AX^{\intercal}={\mathbf{0}}$, which we will refer to as a diagonal
linear vector system.

Example. For our motivating question, use $d=2$ and $k=4$ along with the
systems’ matrices $A_{1}=\begin{bmatrix}1&1&-1&0\\\ \end{bmatrix}$ and
$A_{2}=\begin{bmatrix}-1&1&0&-1\\\ 0&-1&1&-1\\\ \end{bmatrix}$ to see that we
seek monochromatic 2-dimensional points
$\mathbf{p}_{j}=[a_{j}\,b_{j}]^{\intercal}$, $1\leq j\leq 4$, such that
$a_{1}+a_{2}=a_{3}$ (the first coordinates vector) and $b_{1},b_{2},b_{3}$
(the second coordinates vector) are in arithmetic progression. Note that
$a_{4}$ is a dummy variable to make the lengths of the coordinates vectors
equal and that the common difference ($b_{4}$) of the arithmetic progression
is not needed to answer our motivating question, but is necessary for the
system.

We start our investigation with diagonal linear vector systems so that the
same system is to be satisfied by each $i^{\mathit{th}}$ coordinates vector.
Clearly, if we can guarantee a monochromatic solution in $\mathbb{Z}^{+}$,
when considering points in $\left(\mathbb{Z}^{+}\right)^{d}$ we need only
consider the points with all coordinates equal since they are in bijection
with $\mathbb{Z}^{+}$ and we are (trivially) done. But can we guarantee
solutions if we disallow such solutions? In the case of the generalized
Schur’s Theorem, as stated above the answer is yes [1].

Regarding monochromatic solutions to the generalized Schur equation, we are
moving from solutions in $[1,n]$ to solutions in $[1,n]^{d}$, and we see that
if we restrict our $r$-coloring of $[1,n]^{d}$ to just the points on the
diagonal, $\\{(i,i,\dots,i):1\leq i\leq n\\}$, we trivially have monochromatic
solutions to $\sum_{i=1}^{k-1}\mathbf{p}_{i}=\mathbf{p}_{k}$ with the
$\mathbf{p}_{j}\in[1,n]^{d}$ via (the obvious) bijection to $[1,n]$ coupled
with Rado’s Theorem.. Such a solution is an example of what we will call a
degenerate solution (defined later; see Definition 5). In [1], via use of the
Vandermonde matrix properties and Ramsey’s Theorem, it is proved that non-
degenerate solutions exist in the following sense.

######  Theorem 3.

([1]) Let $d,k,r\in\mathbb{Z}^{+}$. Every $r$-coloring of the points in
$\left(\mathbb{Z}^{+}\right)^{d}$ admits a monochromatic solution to
$\sum_{i=1}^{k-1}\mathbf{p}_{i}=\mathbf{p}_{k}$,
$\mathbf{p}_{j}\in\left(\mathbb{Z}^{+}\right)^{d}$ for $1\leq j\leq k$, with
$\mathbf{p}_{1},\mathbf{p}_{2},\dots,\mathbf{p}_{d}$ linearly independent
(over $\mathbb{Q}$) provided $d\leq k-1$.

As motivation for the main result in this paper, in the next section we extend
Balaji, Lott, and Rice’s [1] proof method, which relies on the Vandermonde
matrix, to show similar results for other equations. In the third section, we
give conditions for the existence of monochromatic solutions not directly
implied by Theorem 2 to systems of linear vector equations under $r$-colorings
of $\left(\mathbb{Z}^{+}\right)^{d}$. We end by answering our motivating
question.

##  2 More Motivation

In this section we extend Theorem 3 to a larger family of equations via the
following observation, which follows easily from the proof of Theorem 3 as
found in [1]

######  Observation 4.

Let $d,k,\ell,r\in\mathbb{Z}^{+}$ with $d\geq 2$. Every $r$-coloring of the
points in $\left(\mathbb{Z}^{+}\right)^{d}$ admits a monochromatic solution to
the linear vector equation

$\sum_{i=1}^{k}\mathbf{p}_{i}=\sum_{i=1}^{\ell}\mathbf{q}_{i}$

with $\mathbf{p}_{i},\mathbf{q}_{i}\in\left(\mathbb{Z}^{+}\right)^{d}$ and
$\mathbf{p}_{1},\mathbf{p}_{2},\dots,\mathbf{p}_{d}$ linearly independent
(over $\mathbb{Q}$) provided $d\leq k-1$ and
$\mathbf{q}_{1},\mathbf{q}_{2},\dots,\mathbf{q}_{d}$ linearly independent
provided $d\leq\ell-1$. Moreover, for such a solution we can have
$\\{\mathbf{p}_{1},\mathbf{p}_{2},\dots,\mathbf{p}_{k-1}\\}\cap\\{\mathbf{q}_{1},\mathbf{q}_{2},\dots,\mathbf{q}_{\ell-1}\\}=\emptyset$.

###### Proof.

Let $n=R(k+\ell;r)$ be the Ramsey number so that every $r$-coloring of the
edges of $K_{n}$ admits a $K_{k+\ell}$ subgraph with all edges the same color.
Let $\chi$ be an arbitrary $r$-coloring $[1,n]^{d}$ .

Consider the complete graph on vertex set
$\\{(i,i^{2},\dots,i^{d}):i\in[1,n]\\}$. Color the edge connecting vertex
$(i,i^{2},\dots,i^{d})$ and $(j,j^{2},\dots,j^{d})$, with $j>i$, by
$\chi((j-i,j^{2}-i^{2},\dots,j^{d}-i^{d}))$. By Ramsey’s Theorem we have a
monochromatic subgraph on vertex set
$\\{(i_{j},i_{j}^{2},\dots,i_{j}^{d}):1\leq j\leq k+\ell\\}$. Assume that
$i_{1}<i_{2}<\dots<i_{k+\ell}$ so that, under $\chi$, for every pair $s<t$,
the points $(i_{t}-i_{s},i_{t}^{2}-i_{s}^{2},\dots,i_{t}^{d}-i_{s}^{d})$ are
all identically colored. Label these points $P(s,t)$.

Let
$\mathbf{p}_{1}=P(1,2),\mathbf{p}_{2}=P(2,3),\dots,\mathbf{p}_{k-1}=P(k-1,k),\mathbf{p}_{k}=P(k,k+\ell)$
and
$\mathbf{q}_{1}=P(k+1,k+2),\mathbf{q}_{2}=P(k+2,k+3),\dots,\mathbf{q}_{\ell-1}=P(k+\ell-1,k+\ell),\mathbf{q}_{\ell}=P(1,k+1)$.
It is easy to check that
$\sum_{i=1}^{k}\mathbf{p}_{i}=\sum_{i=1}^{\ell}\mathbf{q}_{i}$ and the
argument using the Vandermonde matrix as found in [1] proves the linear
independence claim.

To see that
$\\{\mathbf{p}_{1},\mathbf{p}_{2},\dots,\mathbf{p}_{k-1}\\}\cap\\{\mathbf{q}_{1},\mathbf{q}_{2},\dots,\mathbf{q}_{\ell-1}\\}=\emptyset$,
assume otherwise and consider $P(s,s+1)=P(k+t,k+t+1)$ for some $s\in[1,k-1]$
and $t\in[1,\ell-1]$. Note that $s+1<k+t$. Since the first coordinates are
equal (by assumption), we have $i_{s+1}-i_{s}=i_{k+t+1}-i_{k+t}$. We now look
at the second coordinates. First, we have
$i^{2}_{k+t+1}-i^{2}_{k+t}=(i_{k+t+1}-i_{k+t})(i_{k+t+1}+i_{k+t})$. Using the
equality of the first coordinates, this means that
$i^{2}_{k+t+1}-i^{2}_{k+t}=(i_{s+1}-i_{s})(i_{k+t+1}+i_{k+t})>(i_{s+1}-i_{s})(i_{s+1}+i_{s})=i^{2}_{s+1}-i^{2}_{s}$,
so that the second coordinates do not agree. Hence, $P(s,s+1)\neq
P(k+t,k+t+1)$. ∎

We now see that there are linear equations other than the generalized Schur
equation for which we can guarantee monochromatic solutions in
multidimensional spaces not implied by the classical case. This suggests the
question: Can we get a similar result for any Rado system?

##  3 Generic Linear Homogeneous Vector Systems

When considering solutions to a generic linear homogeneous vector equation
$\sum_{i=1}^{k}a_{i}\mathbf{v}_{i}=\mathbf{0}$ we lose Ramsey’s Theorem and
the Vandermonde matrix as a tool to prove linear independence. However, it is
not clear that linear independence is the correct property to use in general.
What we do seek is to show that there are monochromatic solutions in
$\left(\mathbb{Z}^{+}\right)^{d}$ that cannot be obtained by direct
application of Rado’s Theorem (and a bijection with the diagonal of
$\left(\mathbb{Z}^{+}\right)^{d}$).

######  Definition 5 (Degenerate).

For $\mathbf{v},\mathbf{w}\in\left(\mathbb{Z}^{+}\right)^{d}$, let
$\mathbf{v}\circ\mathbf{w}=(v_{1}w_{1},v_{2}w_{2},\dots,v_{d}w_{d})$ denote
the Hadamard product (also known as, coincidentally, the Schur product). We
say a finite set of points $P\subseteq\left(\mathbb{Z}^{+}\right)^{d}$ is
degenerate if there exists $\mathbf{v}\in\left(\mathbb{Z}^{+}\right)^{d}$ such
that $P\subseteq\\{\mathbf{v}\circ(i,i,\dots,i):1\leq i\leq n\\}$ for some
$n\in\mathbb{Z}^{+}$. Otherwise, we say that $P$ is non-degenerate.

Note that degenerate solutions are solutions that can be obtained by an
obvious bijection to $[1,n]$ and direct application of Rado’s Theorem, while
non-degenerate solutions do not appear to be. Hence, we strive to prove that
monochromatic non-degenerate solutions exist in colorings of multidimensional
spaces.

We start by proving a multidimensional Deuber theorem. Toward this end, we
will use the following definition in order to state Deuber’s Theorem [5].

######  Definition 6 ($(m,p,c)$-set).

Let $m,p,c\in\mathbb{Z}^{+}$. A set $M\subseteq\mathbb{Z}^{+}$ is called an
$(m,p,c)$-set if there exist generators
$g_{1},g_{2},\dots,g_{m}\in\mathbb{Z}^{+}$ such that

$M=\bigcup_{i=1}^{m}\left\\{cg_{i}+\sum_{j=i+1}^{m}\lambda_{j}g_{j}:\lambda_{j}\in\mathbb{Z}\cap[-p,p]\mbox{
for }1\leq j\leq m\right\\},$

where we take the empty sum to equal 0.

Note that we have the integers $\lambda_{j}$ taking on negative values but
that the set $M$ must be a set of positive integers.

######  Theorem 7 (Deuber’s Theorem).

Let $m,p,c,r\in\mathbb{Z}^{+}$ be fixed. Then there exist
$M,P,\mu\in\mathbb{Z}^{+}$ so that every $r$-coloring of any
$(M,P,c^{\mu})$-set admits a monochromatic $(m,p,c)$-set.

The applicability of Deuber’s Theorem comes from the fact that for any
$\ell\times m$ matrix $A$ that satisfies the columns conditions, there exist
$p,c\in\mathbb{Z}^{+}$ such that every $(m,p,c)$-set contains a solution to
$A\mathbf{v}=\mathbf{0}$. Hence, Deuber’s Theorem implies one direction of
Rado’s Theorem since $\mathbb{Z}^{+}$ contains every $(M,P,c^{\mu})$-set.

Notation. When referring to the quantities in Theorem 7 we will say that
$(m,p,c)$ is realized by $M,P,c^{\mu}$ and write
$(M,P,c^{\mu})\vDash_{r}(m,p,c)$, where we may omit $r$ if the number of
colors in context is clear. The following easy lemma will prove useful.

######  Lemma 8.

The following hold:

  1. 1.

Let $r<s$ be positive integers. If $(M,P,c^{\mu})\vDash_{s}(m,p,c)$, then
$(M,P,c^{\mu})\vDash_{r}(m,p,c)$.

  2. 2.

Let $M^{\prime}\geq M$ and $P^{\prime}\geq P$. If
$(M,P,c^{\mu})\vDash_{r}(m,p,c)$, then
$(M^{\prime},P^{\prime},c^{\mu})\vDash_{r}(m,p,c)$.

  3. 3.

Let $t>\mu$. If $(M,P,c^{\mu})\vDash_{r}(m,p,c)$, then
$(M,c^{t-\mu}P,c^{t})\vDash_{r}(m,p,c)$.

###### Proof.

For (1), note that an $r$-coloring is an $s$-coloring where some colors are
not used. For (2), just take a subset of the generators and a subsets of the
$\lambda$ values. We prove (3) by showing that we always have an
$(M,P,c^{\mu})$-set contained in any $(M,c^{t-\mu}P,c^{t})$-set. Let
$g_{1},g_{2},\dots,g_{M}$ be generators of an $(M,c^{t-\mu}P,c^{t})$-set. Set
$h_{i}=c^{t-\mu}g_{i}$ for $1\leq i\leq M$ and consider them as generators of
an $(M,P,c^{\mu})$-set. It is easy to see that this $(M,P,c^{\mu})$-set is a
subset of the $(M,c^{t-\mu}P,c^{t})$-set. Since every $r$-coloring of any
$(M,P,c^{\mu})$-set admits a monochromatic $(m,p,c)$-set, we have a
monochromatic $(m,p,c)$-set inside any $r$-coloring of an
$(M,c^{t-\mu}P,c^{t})$-set. ∎

###  3.1 A Multidimensional Deuber Theorem

There is already a multidimensional analog of Deuber’s Theorem due to
Bergelson, Johnson, and Moreira [4]. In their result, one of their goals is to
replace the “$p$” in $(m,p,c)$-sets with a family of multidimensional
polynomial functions and “$c$” by an additive homomorphism and letting the
generators be vectors. While being a strong multidimensional polynomial
generalization of Deuber’s Theorem, it does not correlate with non-degenerate
solutions of a linear vector system in any way that they present in [4] or
that this author could determine. They do present a generalization applying to
systems of equations, which generalizes coloring $\mathbb{Z}^{+}$ to coloring
any countable commutative semigroup with identity 0 (and also with a
restriction on how the columns condition is satisfied). Hence, their
generalization holds over $\left(\mathbb{Z}^{\geq 0}\right)^{d}$, but not
$\left(\mathbb{Z}^{+}\right)^{d}$, which is a small, but quite significant
difference. Another difference is with their use of idempotent ultrafilters in
the Stone-Čech compactification of the positive integers, as the existence of
such idempotents assumes that every filter on $\mathbb{R}$ can be extended to
an ultrafilter [6], a recent result of Di Nasso and Tachtsis that is a
strictly weaker assumption than the Axiom of Choice (which until their result
was needed to prove the existence of idempotent ultrafilters).

We start by defining multidimensional $(m,p,c)$-sets.

######  Definition 9.

Let $d,m,p,c\in\mathbb{Z}^{+}$. Let $M_{1},M_{2},\dots,M_{d}$ each be an
$(m,p,c)$-set. We call $M_{1}\times M_{2}\times\cdots\times M_{d}$ a
$d$-dimensional $(m,p,c)$-set.

######  Remark 10.

There are less than $(2p+1)^{md}$ elements in a $d$-dimensional $(m,p,c)$-set.

######  Theorem 11 (A Multidimensional Deuber Theorem).

Let $d,m,p,c,r\in\mathbb{Z}^{+}$. There exist $M,P,\mu\in\mathbb{Z}^{+}$ such
that every $r$-coloring of any $d$-dimensional $(M,P,c^{\mu})$-set admits a
monochromatic $d$-dimensional $(m,p,c)$-set.

###### Proof.

Using the result and notation of Theorem 7, we start by giving notation for
the existence of $M,P,$ and $\mu$. We let ${\mathcal{D}}_{d}(m,p,c;r)$
represent the statement

$\begin{array}[]{rl}{\mathcal{D}}_{d}(m,p,c;r):&\mbox{ there exists
$M,P,\mu\in\mathbb{Z}^{+}$ so that every $r$-coloring of a\, }\\\ &\mbox{
$d$-dimensional $(M,P,c^{\mu})$-set admits a monochromatic}\\\ &\mbox{
$d$-dimensional $(m,p,c)$-set}.\end{array}$

We will prove that ${\mathcal{D}}_{d}(m,p,c;r)$ is true for all
$d,m,p,c,r\in\mathbb{Z}^{+}$ by induction on $d$. With a slight abuse of
notation, we will use

$(M_{d}(r),P_{d}(r),c^{\mu_{d}(r)})\vDash{\mathcal{D}}_{d}(m,p,c;r)$

for the quantities that realize ${\mathcal{D}}_{d}(m,p,c;r)$.

The base case for our induction, $d=1$, is Theorem 7 so we assume that
${\mathcal{D}}_{d}(m,p,c;r)$ is true for all $m,p,c,r$ and will show that
${\mathcal{D}}_{d+1}(m,p,c;r)$ is true for all $m,p,c,r$.

Let $\chi$ be an $r$-coloring of an arbitrary $(d+1)$-dimensional
$(M^{\prime},P^{\prime\prime},c^{t};r)$-set, say $S_{1}\times
S_{2}\times\cdots\times S_{d+1}$, where $M^{\prime},P^{\prime\prime},$ and $t$
are given below.

Let

$r^{\prime}=r^{(2P_{d}(r)+1)^{dM_{d}(r)}}$

so that

$\left(M_{1}(r^{\prime}),P_{1}(r^{\prime}),c^{\mu_{1}(r^{\prime})}\right)\vDash{\mathcal{D}}_{1}(m,p,c;r^{\prime}).$

From Lemma 8, with $M^{\prime}=\max(M_{1}(r^{\prime}),M_{d}(r))$ and
$P^{\prime}=\max(P_{1}(r^{\prime}),P_{d}(r))$, we see
that$\left(M^{\prime},P^{\prime},c^{\mu_{1}(r^{\prime})}\right)\vDash{\mathcal{D}}_{1}(m,p,c;r^{\prime}).$

Let $t=\max(\mu_{1}(r^{\prime}),\mu_{d}(r))$,
$\mu=\min(\mu_{1}(r^{\prime}),\mu_{d}(r))$, and
$P^{\prime\prime}=c^{t-\mu}P^{\prime}$. By Lemma 8 again, we see that

$(M^{\prime},P^{\prime\prime},c^{t})\vDash{\mathcal{D}}_{1}(m,p,c;r^{\prime}),$

and by applying Lemma 8 to each dimension of a $d$-dimensional
$(M,P,c^{\mu})$-set, we obtain

$(M^{\prime},P^{\prime\prime},c^{t})\vDash{\mathcal{D}}_{d}(m,p,c;r).$ (2)

We claim that

$(M^{\prime},P^{\prime\prime},c^{t})\vDash{\mathcal{D}}_{d+1}(m,p,c;r).$

Define an $r^{\prime}$-coloring $\gamma$ of $S_{1}$ as follows. For $s\in
S_{1}$, let $\gamma(s)$ be the $r$-coloring of the set

$\\{\chi(s,x_{2},x_{3},\dots,x_{d+1}):x_{i}\in S_{i}\mbox{ for }2\leq i\leq
d+1\\}$

(with any fixed ordering of elements). From Remark 10, we see that this is
well-defined (where we may not need all $r^{\prime}$ colors).

Since ${\mathcal{D}}_{1}(m,p,c;r^{\prime})$ holds, there exists a
$\gamma$-monochromatic $(m,p,c)$-set $T_{1}$ so that the sets

$\\{\chi((t,x_{2},x_{3},\dots,x_{d+1}):x_{i}\in S_{i}\mbox{ for }2\leq i\leq
d+1\\}$

are identically $r$-colored for any $t\in T_{1}$; that is
$\chi((s,x_{2},x_{3},\dots,x_{d+1})=\chi((t,x_{2},x_{3},\dots,x_{d+1})$ for
any $s,t\in T_{1}$ and all $x_{i}\in S_{i}$. Let this $r$-coloring be $\tau$.
Now consider $S_{2}\times S_{3}\times\cdots\times S_{d+1}$ under $\tau$. By
the inductive hypothesis and Statement (2), there exists a
$\tau$-monochromatic $d$-dimensional $(m,p,c)$-set $T_{2}\times
T_{3}\times\cdots\times T_{d+1}$. Hence, under $\chi$, our original arbitrary
$r$-coloring, we see that $T_{1}\times T_{2}\times\cdots\times T_{d+1}$ is a
monochromatic $(d+1)$-dimensional $(m,p,c)$-set, completing the inductive step
and the proof. ∎

###  3.2 A Multidimensional Rado Theorem

We now are in a situation where we can apply the following result due to
Frankl, Graham, and Rödl [7] on the number of monochromatic solutions to Rado
systems. Their method is to choose $n$ much larger than $M$ so that there are
many $(M,P,c^{\mu})$-sets in $[1,n]$. By considering generators
$g_{1},g_{2},\dots,g_{M}$ with $g_{i}\equiv(2P+1)^{i}\pmod{(2P+1)^{M}}$, they
prove the following.

######  Theorem 12 ([7]).

Let $A\mathbf{v}=\mathbf{0}$ be a linear system with $A$ an $\ell\times k$
matrix of rank $\ell$ satisfying the columns condition. For any
$r\in\mathbb{Z}^{+}$, there exists a constant $c=c(A,r)>0$ such that any
$r$-coloring of $[1,n]$ contains at least $cn^{k-\ell}(1+o(1))$ monochromatic
solutions.

Applying Theorem 12 to each coordinate of a $d$-dimensional
$(M,P,c^{\mu})$-set, we can now state the following result.

######  Theorem 13.

Consider the linear vector system $A\mathbf{v}=\mathbf{0}$ with $A$ an
$\ell\times k$ scalar matrix of rank $\ell$ satisfying the columns condition.
Let $r\in\mathbb{Z}^{+}$. There exists a constant $c=c(A,d,r)>0$ such that any
$r$-coloring of $[1,n]^{d}$ admits at least $cn^{d(k-\ell)}(1+o(1))$
monochromatic solutions to $A\mathbf{v}=\mathbf{0}$.

######  Remark 14.

For a linear system $A\mathbf{v}=\mathbf{0}$ with $A$ an $\ell\times k$ matrix
of full rank satisfying the columns condition there are $\Omega(n^{k-\ell})$
solutions to the system in $[1,n]$. Since there are $n^{d}$ points in
$[1,n]^{d}$, recalling Definition 5 we see that there are $O(n^{d}\cdot
n^{k-\ell})=O(n^{k-\ell+d})$ degenerate monochromatic solutions in any
$r$-coloring of $[1,n]^{d}$.

Our main result is next and shows that in most situations we can guarantee
monochromatic solutions that are not directly implied by Rado’s Theorem.

######  Theorem 15 (A Multidimensional Rado Theorem).

Let $r,d\in\mathbb{Z}^{+}$. Consider the linear vector system
$A\mathbf{v}=\mathbf{0}$. If $A$ is an $\ell\times k$ matrix of rank $\ell\leq
k-2$ that satisfies the columns condition, then every $r$-coloring of
$\left(\mathbb{Z}^{+}\right)^{d}$ admits a monochromatic non-degenerate
solution.

###### Proof.

Let $n\in\mathbb{Z}^{+}$ be sufficiently large. From Remark 14 we see that for
some $c_{1}>0$ there are at most $c_{1}n^{k-\ell+d}(1+o(1))$ monochromatic
degenerate solutions in any $r$-coloring of $[1,n]^{d}$. From Theorem 13 we
have a total of at least $c_{2}n^{d(k-\ell)}(1+o(1))$ monochromatic solutions.
Hence, we have at least $c_{3}n^{(d-1)(k-\ell)-d}(1+o(1))$ non-degenerate
monochromatic solutions. By ensuring that the exponent is strictly greater
than 0, we see that for $d>2$, it suffices to have $k-\ell\geq 2$; however,
for $d=2$ the counting argument requires $k-\ell\geq 3$ to have non-degenerate
monochromatic solutions. Hence, to complete the proof, we will show via a
different argument that for $d=2$ and $k-\ell=2$ we can also guarantee non-
degenerate monochromatic solutions.

For a $(k-2)\times k$ linear vector system in two dimensions, we will
enumerate degenerate solutions. From Theorem 13, we know there are
$c_{1}n^{4}(1+o(1))$ monochromatic solutions in any $r$-coloring of
$[1,n]^{2}$ for some $c_{1}>0$. We will complete the argument by showing that
there are $o(n^{4})$ (not necessarily monochromatic) degenerate solutions.

In a $(k-2)\times k$ linear system (in one dimension) of full rank, we have 2
free variables, from which the values of all other variables are determined by
the system. Let $x$ and $y$ be the free variables (for the one dimension
situation) and note that when extended to more dimensions, all coordinates of
the variable point corresponding to the free variable are free. Hence, we can
consider $(x_{1},x_{2})$ and $(y_{1},y_{2})$ to be the free variables.

For a degenerate solution in two dimensions we have
$(x_{1},x_{2})=\frac{p}{q}(y_{1},y_{2})$ for some $p,q\in\mathbb{Z}^{+}$,
where we may assume that $\gcd(p,q)=1$. Let $q$ be fixed. Then both $y_{1}$
and $y_{2}$ must be divisible by $q$. Hence, there are at most
$\left(\frac{n}{q}\right)^{2}$ choices for $(y_{1},y_{2})$. Now, we require
$p\leq nq$ to ensure that $x_{1},x_{2}\leq n$. Thus, for each $q$, we have at
most $\frac{n^{3}}{q}$ possibilities for
$(x_{1},x_{2})=\frac{p}{q}(y_{1},y_{2})$. Summing over all possible values of
$q$ gives at most

$\sum_{q=1}^{n}\frac{n^{3}}{q}=n^{3}\sum_{q=1}^{n}\frac{1}{q}<2n^{3}\log n$

possibilities for $(x_{1},x_{2})$ and $(y_{1},y_{2})$. Since the values of the
other variables are determined by the free variables’ values, we find that,
since $2n^{3}\log n=o(n^{4})$, there must be a non-degenerate monochromatic
solution for $d=2$ and $k-\ell=2$. ∎

###  3.3 More Flexible Multidimensional Deuber and Rado Theorems

Recall that for $\mathbf{v},\mathbf{w}\in\left(\mathbb{Z}^{+}\right)^{d}$, we
defined $\mathbf{v}\circ\mathbf{w}=(v_{1}w_{1},v_{2}w_{2},\dots,v_{d}w_{d})$
and consider

$\begin{bmatrix}1\\\ 1\\\ \end{bmatrix}\circ\begin{bmatrix}x_{1}\\\ x_{2}\\\
\end{bmatrix}+\begin{bmatrix}1\\\ 1\\\
\end{bmatrix}\circ\begin{bmatrix}y_{1}\\\ y_{2}\\\
\end{bmatrix}=\begin{bmatrix}1\\\ 2\\\
\end{bmatrix}\circ\begin{bmatrix}z_{1}\\\ z_{2}\\\ \end{bmatrix}.$

In this vector equation we seek points $(x_{1},x_{2}),(y_{1},y_{2})$, and
$(z_{1},z_{2})$ of the same color such that $x_{1},y_{1},z_{1}$ is a Schur
triple $(x_{1}+y_{1}=z_{1}$) while $x_{2},z_{2},y_{2}$ is a 3-term arithmetic
progression. Can we guarantee that this occurs?

In this subsection we show that multidimensional $(m,p,c)$-sets offer more
flexibility than what is stated in Theorem 15. In particular, we will show
that the coordinates can be required to satisfy separate systems. We need a
definition with some notation to be more explicit in this situation.

######  Definition 16 ($(\mathbf{m},\mathbf{p},\mathbf{c})$-set).

Let $d\in\mathbb{Z}^{+}$ and let
$\mathbf{m},\mathbf{p},\mathbf{c}\in\left(\mathbb{Z}^{+}\right)^{d}$. We say
that $S_{1}\times S_{2}\times\cdots\times S_{d}$ is an
$(\mathbf{m},\mathbf{p},\mathbf{c})$-set if $S_{j}$ is an
$(m_{j},p_{j},c_{j})$-set for every $j\in[1,d]$.

Following the proof of Theorem 11, the following generalization can be shown.

######  Theorem 17.

Let $d,r\in\mathbb{Z}^{+}$ and let
$\mathbf{m},\mathbf{p},\mathbf{c}\in\left(\mathbb{Z}^{+}\right)^{d}$. There
exists $\mathbf{M},\mathbf{P},\mathbf{C}\in\left(\mathbb{Z}^{+}\right)^{d}$
such that every $r$-coloring of any $(\mathbf{M},\mathbf{P},\mathbf{C})$-set
admits a monochromatic $(\mathbf{m},\mathbf{p},\mathbf{c})$-set.

###### Proof.

Using the notation from the proof of Theorem 11, we offer a terse proof as it
is essentially the same proof. We let
${\mathcal{D}}_{d}(\mathbf{m},\mathbf{p},\mathbf{c};r)$ represent the
statement

$\begin{array}[]{rl}{\mathcal{D}}_{d}(\mathbf{m},\mathbf{p},\mathbf{c};r):&\mbox{
there exists
$\mathbf{M},\mathbf{P},\mathbf{C}\in\left(\mathbb{Z}^{+}\right)^{d}$ so that
every $r$-coloring of a\, }\\\ &\mbox{ ($d$-dimensional)
$(\mathbf{M},\mathbf{P},\mathbf{C})$-set admits a monochromatic}\\\ &\mbox{
($d$-dimensional) $(\mathbf{m},\mathbf{p},\mathbf{c})$-set}.\end{array}$

Using induction on $d$, with $d=1$ being Deuber’s Theorem, we will use

$(\mathbf{M}(d;r),\mathbf{P}(d;r),\mathbf{C}(d;r))\vDash{\mathcal{D}}_{d}(\mathbf{m},\mathbf{p},\mathbf{c};r)$

Let $\chi$ be an $r$-coloring of an arbitrary $(d+1)$-dimensional
$(\mathbf{M^{\prime}},\mathbf{P^{\prime}},\mathbf{C^{\prime}};r)$-set, say
$S_{1}\times S_{2}\times\cdots\times S_{d+1}$, where
$\mathbf{M^{\prime}},\mathbf{P^{\prime}}$, and $\mathbf{C^{\prime}}$ are given
below.

Since there are at most $e=\prod_{i=1}^{d}(2P_{i}(r)+1)^{M_{i}(r)}$ elements
in an $(\mathbf{M}(d;r),\mathbf{P}(d;r),\break\mathbf{C}(d;r))$-set, let
$r^{\prime}=r^{e}$ so that
$\left(M(1;r^{\prime}),P(1;r^{\prime}),C(1;r^{\prime})\right)\vDash{\mathcal{D}}_{1}(m_{1},p_{1},c_{1};r^{\prime}).$
By Lemma 8, since $r^{\prime}>r$, we have
$\left(M(1;r^{\prime}),P(1;r^{\prime}),C(1;r^{\prime})\right)\vDash{\mathcal{D}}_{1}(m_{1},p_{1},c_{1};r)$.
Let $\mathbf{M^{\prime}}=M(1;r^{\prime})\times\mathbf{M}(d;r)$,
$\mathbf{P^{\prime}}=P(1;r^{\prime})\times\mathbf{P}(d;r)$, and
$\mathbf{C^{\prime}}=C(1;r^{\prime})\times\mathbf{C}(d;r)$.

Using the $r^{\prime}$-coloring $\gamma$ from the proof of Theorem 11 and the
argument therein completes the inductive step and proof. ∎

We can consider Theorem 17 to be an off-diagonal multidimensional Deuber’s
Theorem. This opens up monochromatic sets of points in
$\left(\mathbb{Z}^{+}\right)^{d}$ with interesting mixed Rado properties: By
applying Theorems 12 and 17 we get the following result.

######  Theorem 18 (An Off-Diagonal Multidimensional Rado Theorem).

Let $d,r\in\mathbb{Z}^{+}$. For $1\leq j\leq d$, let $A_{j}$ be an
$\ell_{j}\times k$ matrix of rank $\ell_{j}$ satisfying the columns condition.
There exists a constant $c=c(A_{1},\dots,A_{d},d,r)>0$ such that any
$r$-coloring of $[1,n]^{d}$ admits at least
$cn^{\sum_{i=1}^{d}(k-\ell_{i})}(1+o(1))$ monochromatic sets of $k$ points
$\mathbf{p}_{i}$ such that row $\mathbf{r}_{j}$ of the $d\times k$ matrix
$B=[\mathbf{p}_{1}\,\mathbf{p}_{2}\,\dots,\mathbf{p}_{k}]$ satisfies
$A_{j}\mathbf{r}_{j}^{\intercal}=\mathbf{0}$ for each $j\in[1,d]$; that is,
the $j^{\mathit{th}}$ coordinates vector of $B$ satisfies the
$j^{\mathit{th}}$ system.

######  Remark 19.

Systems with different numbers of variables can all be made to have $k$
variables, for some $k$, by introducing dummy variables.

Note that degenerate solutions no longer make sense if the systems are not
equivalent, but we can now consider coloring the points in multidimensional
space and guaranteeing the existence of many interesting monochromatic
configurations, like in the next example.

Example. For any $r$-coloring of $\mathbb{Z}^{3}$ there exist
$a,d,x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}\in\mathbb{Z}^{+}$ such that the
points

$\begin{pmatrix}x_{1}\\\ y_{1}\\\ a\\\ \end{pmatrix},\begin{pmatrix}x_{2}\\\
y_{2}\\\ a+d\\\ \end{pmatrix},\begin{pmatrix}x_{3}\\\ y_{3}\\\ a+2d\\\
\end{pmatrix},\begin{pmatrix}x_{1}+x_{2}+x_{3}\\\ y_{3}+y_{2}-y_{1}\\\ a+3d\\\
\end{pmatrix}.$

are monochromatic. Note that the first coordinates vector satisfies the
generalized Schur equation, the second coordinates vector satisfies $u-v=w-x$,
and the third coordinates vector are a 4-term arithmetic progression.

By applying Theorem 18 we can now answer, in particular, our motivating
question at the beginning of this article about Schur triples and 3-term
arithmetic progressions in the affirmative. In fact, a simple backtracking
computer calculation (or tedious pencil and paper work) provides us with the
following result.

######  Theorem 20.

The minimum integer $n$ such that for every $2$-coloring of $[1,n]\times[1,n]$
there exist $a,b,x,d\in\mathbb{Z}^{+}$ with $(a,x),(b,x+d),$ and $(a+b,x+2d)$
all the same color, is $n=9$.

Acknowledgement. The author thanks Tom Brown, Bruce Landman, and Neil Hindman
for helpful comments in earlier drafts.

## References

  * [1] V. Balaji, A. Lott, and A. Rice, Schur’s theorem in integer lattices, Integers 22 (2022), #A62, 8pp.
  * [2] A. Beutelspacher and W. Brestovansky, Generalized Schur Numbers, Lecture Notes in Mathematics, 969 (1982), 30-38.
  * [3] V. Bergelson, and A. Leibman, Polynomial extensions of van der Waerden’s and Szemeredi’s theorems, Journal of AMS 9 (1996), 725-753.
  * [4] V. Bergelson, J. H. Johnson Jr., and J. Moreira, New polynomial and multidimensional extensions of classical partition results, J. Combin. Theory, Series A 147 (2017), 119-154.
  * [5] W. Deuber, Partitionen und lineare gleichungssysteme, Math. Zeitschrift 133 (1973), 109-123.
  * [6] M. Di Nasso and E. Tachtsis, Idempotent ultrafilters without Zorn’s Lemma, Proc. A.M.S 146 (2018), 397-411.
  * [7] P. Frankl, R. Graham, and V. Rödl, Quantitative theorems for regular systems of equations, J. Combin. Theory, Series A 47 (1988), 246-261.
  * [8] R. Rado, Studien zur kombinatorik, Math. Z. 36 (1933), 424-480.
  * [9] R. Rado, Note on combinatorial analysis, Proc. London Math. Soc. 48 (1943), 122-160.
  * [10] A. Robertson and D. Schaal, Off-diagonal generalized Schur numbers, Adv. Applied Math. 26 (2001), 252-257.
  * [11] I. Schur, Über die kongruenz $x^{m}+y^{m}=z^{m}\pmod{p}$, Jahresbericht der Deutschen Mathematiker-Vereinigung 25 (1916), 114-117.
  * [12] E. Witt, Ein kombinatorischer satz der elementargeometrie, Math. Nach. 6 (1952), 261-262.
  * [13] B. L. van der Waerden, Beweis einer Baudetschen vermutung, Nieuw Archief voor Wiskunde 15 (1927), 212-216.

[AR] Aaron Robertson
Department of Mathematics
Colgate University
Hamilton, New York
<EMAIL_ADDRESS>
http://math.colgate.edu/$\sim$aaron