-0.5cm

# Optimal bounds on the polynomial Schur’s theorem

Jaehoon Kim<EMAIL_ADDRESS>Department of Mathematical Sciences,
KAIST, Daejeon 34141, Republic of Korea  ,  Hong Liu<EMAIL_ADDRESS>Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic
Science (IBS), Daejeon, South Korea.  and  Péter Pál Pach
<EMAIL_ADDRESS>Department of Computer Science and Information Theory,
Budapest University of Technology and Economics, Műegyetem rkp. 3., H-1111
Budapest, Hungary;
MTA-BME Lendület Arithmetic Combinatorics Research Group, ELKH, Műegyetem rkp.
3., H-1111 Budapest, Hungary.

###### Abstract.

Liu, Pach and Sándor recently characterized all polynomials $p(z)$ such that
the equation $x+y=p(z)$ is $2$-Ramsey, that is, any $2$-coloring of
$\mathbb{N}$ contains infinitely many monochromatic solutions for $x+y=p(z)$.
In this paper, we find asymptotically tight bounds for the following two
quantitative questions.

  * •

For $n\in\mathbb{N}$, what is the longest interval $[n,f(n)]$ of natural
numbers which admits a $2$-coloring with no monochromatic solutions of
$x+y=p(z)$?

  * •

For $n\in\mathbb{N}$ and a $2$-coloring of the first $n$ integers $[n]$, what
is the smallest possible number $g(n)$ of monochromatic solutions of
$x+y=p(z)$?

Our theorems determine $f(n)$ up to a multiplicative constant $2+o(1)$, and
determine the asymptotics for $g(n)$.

J.K. was supported by the Fulbright Visiting Scholar Fellowship and by the
National Research Foundation of Korea (NRF) grant funded by the Korean
government(MSIT) No. RS-2023-00210430. H.L. was supported by IBS-R029-C4.
P.P.P. was supported by the Lendület program of the Hungarian Academy of
Sciences (MTA) and by the National Research, Development and Innovation Office
NKFIH (Grant Nr. K146387).

##  1\. Introduction

Ramsey theory is a study about finding largest possible orders in chaotic
systems. It has a long history dating back to the following remarkable theorem
by Schur [19] in 1916: the equation $x+y=z$ (or equivalently the tuple of the
form $(x,y,x+y)$) is _Ramsey_ , which means that any finite coloring of
$\mathbb{N}$ contains infinitely many tuples $(x,y,z)$ satisfying the equation
$x+y=z$ (or equivalently $(x,y,z)=(x,y,x+y)$). These tuples satisfying the
equation are called _monochromatic solutions_ of the equation. Another
classical theorem regarding Ramsey equation is van der Waerden’s theorem [22]
which states that the arithmetic progression $(x,x+d,\dots,x+(t-1)d)$ is
Ramsey for any $d\in\mathbb{N}$. Later, Rado [14] completely determined all
Ramsey linear equations. Starting with these results, many extensions have
been considered. Just to state a few, the Phytagorean equation
$x^{2}+y^{2}=z^{2}$ was shown to be 2-Ramsey by Heule-Kullmann-Marek [10]
using computer assistance, a polynomial extension of van der Waerden’s theorem
was shown by Bergelson-Leibman [2], Moreira [12] proved that $(x,x+y,xy)$ is
Ramsey, and Bowen-Sabok [3] proved that $(x,y,x+y,xy)$ is Ramsey in the
rationals.

Recently, there have been exciting developments on the polynomial extension of
Schur’s theorem. Csikvári-Gyarmati-Sárközy [6] proved that $x+y=z^{2}$ is not
$16$-Ramsey, meaning that there exists a coloring of $\mathbb{N}$ with $16$
colors containing no monochromatic solutions for $x+y=z^{2}$ other than the
trivial solution $(x,y,z)=(2,2,2)$. Green-Lindqvist [9] used a Fourier
analytic argument to show that the equation $x+y=z^{2}$ is $2$-Ramsey but not
$3$-Ramsey. The third author of this paper [13] found a shorter combinatorial
proof for the $2$-Ramseyness of the equation $x+y=z^{2}$. The second and third
authors of this paper together with Sándor [11] proved the polynomial Schur’s
theorem which completely determines the Ramseyness of the equation $x+y=p(z)$
for all polynomials $p$. The equations of the form $ax+by=p(z)$ for certain
choices of $a,b,p(z)$ were further considered in [1].

A modification of the $3$-coloring given by Green-Lindqvist [9] shows that
$x+y=p(z)$ is not $3$-Ramsey for any polynomial $p(z)$ of degree at least two,
and the following theorem determines all polynomials $p$ for which the
equation $x+y=p(z)$ is $2$-Ramsey.

######  Theorem 1.1 (Polynomial Schur’s theorem [11]).

For a polynomial $p(z)$ of degree $d\geq 1$ with a positive leading
coefficient, the equation $x+y=p(z)$ is $2$-Ramsey if and only if $p(z)$ is a
non-odd polynomial.

Here, a polynomial is _odd_ if it only attains odd values on $\mathbb{N}$ and
_non-odd_ otherwise. It is easy to see that if the polynomial $p(z)$ is odd,
then coloring all integers according to their parity will avoid any
monochromatic solutions. Theorem 1.1 shows that this ‘parity constraint’ is
the only obstruction for the $2$-Ramseyness of the equation $x+y=p(z)$. Note
that it is sufficient to consider the polynomials with a positive leading
coefficient as we only consider colorings of the positive integers.

As this result completely settles the Ramsey problem for the equation
$x+y=p(z)$, it is natural to ask its quantitative aspect. In Ramsey theory,
finding the correct quantitative bounds tends to be much more challenging than
just proving the existence. For example, in the (hyper)graph Ramsey theory,
the existence of the Ramsey number was completely resolved [15] already in
1930. However, the correct quantitative bounds still remain elusive. Even for
the simplest $2$-uniform (graph) Ramsey numbers, there is an exponential gap
between the best known lower bound [21] and the best known upper bound and
improving this exponential gap to a smaller one in the recent breakthrough by
Campos-Griffiths-Morris-Sahasrabudhe [5] took almost 90 years.

Regarding the polynomial extension of Schur’s theorem, one can ask two natural
quantitative questions. How long can we avoid the monochromatic solutions and
how many monochromatic solutions we must encounter in a $2$-coloring of
$[n]:=\\{1,2,\ldots,n\\}$? For the first question, considering colorings from
$1$ to a number $m$ avoiding monochromatic solutions makes little sense as
such a number $m$ will always be a finite number. Hence, we should rather look
at colorings of numbers that are at least as large as some number $n$.
Formally, we study the following two quantitative questions regarding the
$2$-Ramseyness of the equation $x+y=p(z)$ for non-odd polynomials $p(z)$.

  * (1)

For $n\in\mathbb{N}$, what is the largest $f(n)$ such that one can 2-color the
interval $[n,f(n)]$ so that it does not contain any monochromatic solutions of
$x+y=p(z)$?

  * (2)

What is the smallest possible number $g(n)$ of monochromatic solutions of
$x+y=p(z)$ inside the set $[n]$ over all $2$-colorings of $[n]$?

The second question of counting monochromatic solutions have been considered
for linear equations. Frankl, Graham and Rödl [8] in the 80s proved an optimal
quantitative Rado’s theorem. More precise counting result for the specific
equation $x+y=z$ was later obtained independently by Schoen [18] and Robertson
and Zeilberger [16], another proof was given by Datskovsky [7]. Results on
counting monochromatic solutions of systems of linear equations on more
general groups than $\mathbb{Z}$ were also obtained, see [4, 20]. However, for
non-linear equations, only a few counting results are known for very specific
types of equations. For example, diagonal Diophantine equations were
considered using the Hardy–Littlewood circle method, see e.g. [17]. In
general, determining the answers of these quantitative questions for a fairly
substantial class of non-linear equations is very difficult.

For equation $x+y=p(z)$ of our interest, there are constructions yielding
natural bounds. For the first question, this natural bound is
$f(n)=\Omega(n^{d^{2}})$. Assuming that both numbers $p(n)$ and
$p(\frac{1}{2}p(n))$ are even numbers, consider the coloring of the interval
$[n,\frac{1}{2}p(\frac{1}{2}p(n))-1]$ as follows. We color the numbers in the
first interval $[n,\frac{p(n)}{2}-1]$ by the color $+1$ and the rest of the
numbers in $[\frac{p(n)}{2},\frac{1}{2}p(\frac{1}{2}p(n))-1]$ by $-1$. Then
any $x,y,z$ with color $+1$ satisfies $p(z)\geq p(n)>x+y$ while any $x,y,z$
with color $-1$ satisfies $p(z)\geq p(\frac{1}{2}p(n))>x+y$, thus no
monochromatic solutions exist. This shows that
$f(n)\geq\frac{1}{2}p(\frac{1}{2}p(n))-1=\Omega(n^{d^{2}})$.

Regarding the second question for the equation $x+y=p(z)$, the following
construction shows that $g(n)=O(n^{2/d^{2}})$. Given $n$, consider two numbers
$a=\min\\{x:p(x)>2n\\}$ and $b=\min\\{x:p(x)>2a\\}$ satisfying
$a=\Theta(n^{1/d})$ and $b=\Theta(n^{1/d^{2}})$. By coloring the numbers
$[b-1]\cup[a,n]$ with color $+1$ and $[b,a-1]$ with color $-1$, we can avoid
all monochromatic solutions $(x,y,z)$ with $x,y\geq b$. As all monochromatic
solution $(x,y,z)$ lies in $[b-1]$, the number of monochromatic solutions is
at most $b^{2}=O(n^{2/d^{2}})$, showing that $g(n)=O(n^{2/d^{2}})$.

In this paper, we almost completely resolve both questions. The first theorem
below answers the first question by determining the value of $f(n)$ up to a
multiplicative constant $2+o(1)$.

######  Theorem 1.2.

Let $p(z)\in\mathbb{Z}[z]$ be a non-odd polynomial of degree $d\geq 2$ with a
positive leading coefficient, then there exists an integer $n_{0}$ such that
the following holds for all $n\geq n_{0}$. For any $2$-coloring $\phi$ of
$[n,p(\lceil\frac{1}{2}p(n)\rceil)]$, there exists monochromatic numbers
$x,y,z\in[n,p(\lceil\frac{1}{2}p(n)\rceil)]$ satisfying $x+y=p(z)$.

Our second theorem determines the asymptotics for the answer of the second
question, showing that the number $2/d^{2}$ in the exponent is tight.

######  Theorem 1.3.

Let $p(z)\in\mathbb{Z}[z]$ be a non-odd polynomial of degree $d\geq 2$ with a
positive leading coefficient. Let $\phi$ be a $2$-coloring of $[n]$. Then
there are at least $n^{2/d^{2}-o(1)}$ monochromatic solutions
$(x,y,z)\in[n]^{(3)}$ of $x+y=p(z)$.

By closely examining our proof, one can measure the above $o(1)$-term more
precisely. Theorem 1.3 yields $\Omega(\frac{n^{2/d^{2}}}{\log(n)})$
monochromatic solutions if $d\geq 3$, and
$n^{\frac{2}{d^{2}}-O(\frac{1}{\log\log n})}$ monochromatic solutions if
$d=2$. We note that the multiplicative $\Omega(\frac{1}{\log n})$-term for
$d\geq 3$ comes from Lemma 3.4 and the multiplicative $n^{-O(\frac{1}{\log\log
n})}$-term for $d=2$ comes from Lemma 3.1.

##  2\. Preliminaries

For given natural numbers $n,a,b\in\mathbb{N}$, we define
$[n]:=\\{1,2,\dots,n\\}$ and $[a,b]:=\\{a,a+1,\dots,b\\}$. We write $a=b\pm c$
if $b-c\leq a\leq b+c$. All logarithms in this paper are the logarithms with
the base two. If we claim that a result holds whenever we have $0<a\ll b\ll
c,d<1$, it means that there exists functions $f,g$ such that the result holds
as long as $a<f(b)$ and $b<g(c,d)$. We will not compute these functions
explicitly. In many cases, we treat large numbers as if they are integers by
omitting floor and ceiling if it does not affect the argument. For a number
$c$ and sets $A,B\subseteq\mathbb{N}$ of numbers, we write $A+c=\\{a+c:a\in
A\\}$, $c-A=\\{c-a:a\in A\\}$, $A-c=\\{a-c:a\in A\\}$, $cA=\\{ca:a\in A\\}$,
$A+B=\\{a+b:a\in A,b\in B\\}$ and $A-B=\\{a-b:a\in A,b\in B\\}$. Furthermore,
if $A$ is a finite set of numbers, we write $\min(A)$ and $\max(A)$ to denote
the minimum and the maximum number in the set $A$. For a given sequence
$a_{1},\dots,a_{t}$, we say that a number $Q$ is an _integral combination_ of
the sequence $a_{i}$’s if $Q=\sum_{i\in[t]}b_{i}a_{i}$ for some integers
$b_{1},\dots,b_{t}\in\mathbb{Z}$. If all $b_{i}$’s are non-negative, then $Q$
is a _non-negative integral combination_ of the sequence of $a_{i}$’s.

We say that a polynomial $p(z)\in\mathbb{Z}[z]$ is _odd_ if $p(z)$ is odd for
all $z\in\mathbb{Z}$ and _non-odd_ otherwise. Throughout the paper, we fix a
non-odd polynomial

$p(z)=a_{d}z^{d}+\dots+a_{1}z+a_{0}\in\mathbb{Z}[z]$

of degree $d\geq 2$ with positive leading coefficient $a_{d}$. We write
$\|p\|$ to denote $d+\sum_{i=0}^{d}|a_{i}|$. We also assume that a
$2$-coloring $\phi:\mathbb{N}\rightarrow\\{-1,1\\}$ is given. We say that a
triple $(x,y,z)$ is a _monochromatic solution_ if it satisfies $x+y=p(z)$ and
$x,y,z$ all have the same color. We consider $(x,y,z)$ and $(y,x,z)$ as two
distinct solutions. For two functions $f,g$, we write $f(x)=O(g(x))$ if
$|f(x)|\leq C|g(x)|$ for some $C$ which depends only on $\|p\|$. We also
define the expression $f(x)=\Theta(g(x))$ and $f(x)=\Omega(g(x))$ in a similar
way.

For a given $2$-coloring $\phi$, Let $\Phi^{+},\Phi^{-}$ denote the set of
natural numbers with colors $+1$ and $-1$, respectively. We say that a number
$k$ is a _switch_ if $\phi(k)\neq\phi(k+1)$, and it is a _positive switch_ if
$\phi(k)=+1$ and $\phi(k+1)=-1$. Suppose that we have fixed a large number $k$
with $1/k\ll 1/\|p\|$ which is a positive switch. We may assume this as
otherwise either we obtain many monochromatic solutions or we can swap the
colors $+1$ and $-1$ to obtain such a $k$.

For each $s\in\mathbb{N}$, we write

$m_{s}(k):=p(k+s)-p(k).$

As $1/k\ll 1/\|p\|$ holds, we have $m_{s}(k)>0$. We consider the following two
important numbers:

$k_{1}:=\max\Big{\\{}t:p(t)<\frac{1}{2}p(k)\Big{\\}}\enspace\text{and}\enspace
k_{0}:=\max\\{t:p(t)<2p(k)-4m_{1}(k)\\}.$

With this definition, we can estimate the value of $k_{1},k_{0}$ as
$k_{1}=(2^{-1/d}\pm o(1))k\text{ and }k_{0}=(2^{1/d}\pm o(1))k$, where the
$o(1)$ term tends to zero as $k$ grows. We say that the switch $k$ is
_isolated_ if all numbers in $[k+1,k_{0}]$ has color $-1$, otherwise it is
_non-isolated_.111 Note that this definition is slightly different from [11]
as we do not care how $[k/2,k]$ looks like.

We say that a pair $\\{a,b\\}$ of two numbers is _$(k,s)$ -bad_ (or simply
_bad_) for $s\in[k]$ if

$b=a+m_{s}(k),\enspace\phi(k+s)=-1,\enspace\text{and}\enspace\phi(a)>\phi(b).$

Since $\phi$ only takes values in $\\{-1,1\\}$, the above inequality
$\phi(a)>\phi(b)$ fixes the colors of $a$ and $b$ as $\phi(a)=+1$ and
$\phi(b)=-1$. This concept of bad pair plays an important role in this paper
because it provides many monochromatic solutions as follows.

######  Lemma 2.1.

Suppose that $p(z)\in\mathbb{Z}[z]$ is a polynomial with positive leading
coefficient of degree $d\geq 2$, and $\phi:\mathbb{N}\rightarrow\\{-1,1\\}$.
Suppose that $k$ is a positive switch with $0<1/k\ll 1/\|p\|<1$. If we have
$t$ pairwise disjoint bad sets, then we obtain at least $t$ distinct
monochromatic solutions.

###### Proof.

Assume that $\\{a,b\\}$ is a $(k,s)$-bad set with $b=a+m_{s}(k)$, then
$\phi(a)=+1$ and $\phi(b)=-1$. As $1/k\ll 1/\|p\|$, we know that $m_{s}(k)>0$.

If $p(k)-a$ is colored $+1$, then $(a,p(k)-a,k)$ forms a monochromatic
solution with color $+1$. If $p(k)-a$ is colored $-1$, then
$(b,p(k)-a,k+s)=(b,p(k+s)-b,k+s)$ forms a monochromatic solution with color
$-1$. Hence, we obtain a monochromatic solution of the form $(a,p(k)-a,k)$ or
$(b,p(k)-a,k+s)$.

Assume that we have pairwise disjoint sets
$\\{a_{1},b_{1}\\},\dots,\\{a_{t},b_{t}\\}$ such that each $\\{a_{i},b_{i}\\}$
is a $(k,s_{i})$-bad set. For each $i\in[t]$, the above argument shows that
either $(a_{i},p(k)-a_{i},k)$ or $(b_{i},p(k)-a_{i},k+s_{i})$ is a
monochromatic solution. As two solutions $(x,y,z)$ and $(y,x,z)$ are different
and $\\{a_{1},b_{1}\\},\dots,\\{a_{t},b_{t}\\}$ are all pairwise distinct,
those solutions are all distinct and provide $t$ distinct monochromatic
solutions. ∎

###  2.1. Proof ideas

In this section, we describe the ideas for the proofs of our theorems. Assume
that our task is to find many monochromatic solutions. As Lemma 2.1
demonstrates, this task boils down to finding many pairwise disjoint bad
pairs. Using a lemma in [11] (see Lemma 3.1), we can assume that there is a
number $k$ which is an isolated switch, i.e. $[k+1,k_{0}]\subseteq\Phi^{-}$.
Exploiting this assumption, we will pursue the following strategy.

As $[k+1,k_{0}]\subseteq\Phi^{-}$, for some number $z\in\Phi^{-}$, the
interval $p(z)-[k+1,k_{0}]$ mostly consists of numbers with color $+1$, as
otherwise we obtain many monochromatic solutions $(x,p(z)-x,z)$ with
$x\in[k+1,k_{0}]$. Similar argument yields that for $z^{\prime}\in\Phi^{+}$,
$p(z^{\prime})-(p(z)-[k+1,k_{0}])$ mostly consists of the numbers with the
color $-1$. Exploiting these arguments, we will be able to find intervals $P$
of mostly positive colored numbers and intervals $N$ of mostly negative
colored numbers satisfying $\max(P)<\min(N)$. This provides many pairs
$(a,b)\in P\times N$ satisfying $a<b$, $\phi(a)=+1$ and $\phi(b)=-1$. Based on
this choice, we will write the number $b-a$ as a non-negative integral
combinations of the numbers $m_{1}(k),\dots,m_{k_{0}-k}(k)$. For example, if
$b-a=2m_{1}(k)+2m_{2}(k)$, then we may consider a sequence

$a,~{}a+m_{1}(k),~{}a+m_{1}(k)+m_{2}(k),~{}a+m_{1}(k)+2m_{2}(k),~{}a+2m_{1}(k)+2m_{2}(k)=b.$

As the $\phi$-value on this sequence starts with $+1$ and ends with $-1$ and
$k+s\in\Phi^{-}$ for $s\in[2]$, there must be two consecutive numbers $x,y$ in
the sequence with $\phi(x)>\phi(y)$ and $y=x+m_{s}(k)$ for some $s\in[2]$.
This provides a bad pair $\\{x,y\\}$. This strategy suggests that it is
important to determine the numbers $Q=b-a$ that can be written as a non-
negative integral linear combination of $m_{s}(k)$.

Suppose that the above procedure yields a bad pair
$\\{x,y\\}=\\{a+m_{1}(k),a+m_{1}(k)+m_{2}(k)\\}$, and we wish to find more bad
pairs disjoint from $\\{x,y\\}$. In order to obtain such bad pairs, we
consider another sequence

$a,~{}a+m_{2}(k),~{}a+2m_{2}(k),~{}a+m_{1}(k)+2m_{2}(k),~{}a+2m_{1}(k)+2m_{2}(k)=b.$

Note that this sequence lacks of consecutive numbers of the form $a+m_{1}(k)$
and $a+m_{1}(k)+m_{2}(k)$. As before, this sequence yields a new bad pair.
However, whichever new bad pair we obtain, it has a different form than
$\\{a+m_{1}(k),a+m_{1}(k)+m_{2}(k)\\}$ due to the choice of this new sequence.
In general, having different forms does not necessarily imply disjointness as
one number can be expressed as two different non-negative integral
combinations of $m_{s}(k)$. Nonetheless, we can show that the numbers
$m_{s}(k)$ admit some ‘independence’ (see Proposition 2.6). Using this
independence and expressing the number $b-a$ as integral combinations of only
a restricted number of terms $m_{s}(k)$, we can prove that the new bad pair is
indeed disjoint from the previous bad pairs.

Finding a sequence avoiding one such a bad pair is easy. However, if there are
many bad pairs given, finding one new sequence avoiding all those is non-
trivial. However, such a problem can be reduced to a graph theory problem
regarding graph expansion. Indeed, there is a natural correspondence between
such a sequence and a path in a certain ‘grid-like’ directed graph avoiding
given vertices. Exploiting this correspondence and solving this graph problem,
we will prove Lemma 3.4 which is a key technical lemma for the proof of
Theorem 1.3. We give a slightly more detailed sketch on these ideas right
before the statement of Lemma 3.4.

###  2.2. Approximating a number with integral combinations of $m_{s}(k)$

In order to find a desired integral combination for a given number $Q$, it is
convenient to define the following infinite vectors and their inner product:

$\displaystyle\mathbf{m}^{k}$ $\displaystyle:=(m_{1}(k),m_{2}(k),\dots),$
$\displaystyle\mathbf{id}^{s}$
$\displaystyle:=(1^{s},2^{s},\dots)\enspace\text{and}$
$\displaystyle\mathbf{b}^{t,s}$
$\displaystyle:=(\underbrace{0,\dots,0}_{s-1\text{
zeros}},-\binom{t}{1},\underbrace{0,\dots,0}_{s-1\text{
zeros}},(-1)^{2}\binom{t}{2},\dots\dots,(-1)^{t}\binom{t}{t},0,0,\dots).$

If we consider a finite vector $(x_{i}:i\in S)$ for $S\subseteq\mathbb{N}$, we
naturally identify it with an infinite vector $(x_{i}:i\in\mathbb{N})$ by
letting $x_{i}=0$ if $i\notin S$. This allows us to define inner product for
two vectors with different lengths. In other words, for two vectors
$\mathbf{x}$ and $\mathbf{y}$, we define

$\mathbf{x}\cdot\mathbf{y}=\sum_{i\in\mathbb{N}}x_{i}y_{i}.$

For a given vector $\mathbf{x}$ and a set $S\subseteq\mathbb{N}$, we let
$\mathbf{x}\mathord{\upharpoonright}_{S}:=(x_{i}\mathbf{1}_{S}(i))_{i\in\mathbb{N}}$
be the vector we obtain where $\mathbf{1}_{S}(i)=1$ if $i\in S$ and $0$ if
$i\notin S$.

In fact, later we will choose a number $a$ from an interval $P=[x,x+c]$ and a
number $b$ from an interval $N=[x^{\prime},x^{\prime}+c]$ and express $b-a$ as
an integral combination of the numbers $m_{s}(k)$. In this scenario, if any
number between $x^{\prime}-x+c$ and $x^{\prime}-x-c$ can be expressed as a
non-negative integral combination of the $m_{s}(k)$’s, then we obtain a
monochromatic solution. Hence, for some number $Q=x^{\prime}-x$, finding a
non-negative integral combinations of $m_{s}(k)$ whose value is roughly $Q$ is
sufficient. In other words, we wish to find a non-negative vector $\mathbf{v}$
such that $\mathbf{v}\cdot\mathbf{m}^{k}=Q\pm c$.

As this number $Q$ is obtained from the intervals of our choice, we have some
control on the value of $Q$. In particular, we can take $Q$ to be very large.
With such a large number $Q$, we can reduce our problem to finding an integral
vector $\mathbf{v}^{\prime}$, which need not be non-negative.

Indeed, if $Q$ is sufficiently large, then we can find a large number $q$ so
that $Q^{\prime}=Q-q\sum_{s\in[k_{0}-k]}m_{s}(k)$ is still positive. Then if
we can find another vector $\mathbf{v}^{\prime}\in[-q,q]^{k_{0}-k}$ such that
$\mathbf{v}^{\prime}\cdot\mathbf{m}^{k}=Q^{\prime}\pm c$, then the non-
negative vector $(q,\dots,q)+\mathbf{v}^{\prime}$ provides a desired non-
negative integral combination. The following lemma allows us to express a
given number $Q^{\prime}$ as an integral combination whose coefficients are
allowed to be negative while having small absolute values, hence providing
such a vector $\mathbf{v}^{\prime}$. In addition, we can restrict the support
of such a vector and this fact will be also important for our application.

######  Lemma 2.2.

Suppose
$0<\frac{1}{k}\ll\frac{1}{\ell}\ll\frac{1}{q}\ll\frac{1}{\|p\|},\frac{1}{d}\leq\frac{1}{2}$.
For a given positive integer $Q^{\prime}$ at most $qk^{d-1}$, there exists an
integer vector $\mathbf{v}^{\prime}\in[-\ell,\ell]^{k_{0}-k}$ satisfying

$\mathbf{v}^{\prime}\cdot\mathbf{m}^{k}=Q^{\prime}\pm\ell$

and $\mathbf{v}^{\prime}_{i}=0$ for all $i\notin\\{t2^{j}:t\in[d-1],1\leq
j\leq q+\frac{1}{2}\log{k}\\}$.

In order to prove this lemma, we collect several useful propositions. First,
note that expressing a number $Q$ as a non-negative integral combination of a
geometric series $1,t,t^{2},\dots$ is easy. We simply take the largest $i$ and
$c\in[t-1]$ such that $ct^{i}\leq Q$ and reduce the problem to the problem of
expressing $Q-ct^{i}$ as a non-negative integral combination of
$1,t,t^{2},\dots$. In fact, this greedy approach works with other series as
long as the series does not grow too fast. The following proposition confirms
this. As the proof is just what we described, we omit the proof.

######  Proposition 2.3.

Let $t>1$ be an integer and $c_{1},\dots,c_{m}$ be a sequence of positive
numbers satisfying $c_{i}<c_{i+1}<tc_{i}$ for all $i\in[m-1]$. If $Q$ is a
positive number at most $tc_{m}$, then there exist numbers
$b_{1},\dots,b_{m}\in[0,t-1]$ satisfying $\sum_{i=1}^{m}b_{i}c_{i}=Q\pm
c_{1}$.

As we wish to express a number $Q$ as an integral combination of the numbers
$m_{s}(k)$, it is useful to know the properties of the numbers $m_{s}(k)$. In
fact, if we compute $m_{s}(k)=p(k+s)-p(k)$ term by term, we obtain the
following $k$-ary expansion.

$\displaystyle
m_{s}(k)=\sum_{i=0}^{d-1}\left(\sum_{r=i+1}^{d}a_{r}\binom{r}{i}s^{r-i}\right)k^{i}~{}\text{
and
}~{}\mathbf{m}^{k}=\sum_{i=0}^{d-1}\left(\sum_{r=i+1}^{d}a_{r}\binom{r}{i}\mathbf{id}^{r-i}\right)k^{i}$
(2.1)

Based on this, if $1/k\ll 1/\ell\ll 1/d,1/\|p\|$ and $s\leq 2^{2q}k^{1/2}$, we
have

$\displaystyle m_{s}(k)=a_{d}sdk^{d-1}\pm\ell k^{d-3/2}.$ (2.2)

In order to prove Lemma 2.2, we plan to use the vectors $\mathbf{b}^{t,s}$.
The following proposition allows us to understand the $k$-ary expansion of
$\mathbf{m}^{k}\cdot\mathbf{b}^{t,s}$.

######  Proposition 2.4.

Suppose $0<\frac{1}{q}\ll\frac{1}{\|p\|},\frac{1}{d}<1$ and $t\in[d]$. Then
there exist integers $h_{t,0},h_{t+1,0},$
$h_{t+1,1},h_{t+2,0},\dots,h_{d,d-t}\in[-q,q]$ satisfying the following for
all $s,k\in\mathbb{N}$.

$\displaystyle\mathbf{m}^{k}\cdot\mathbf{b}^{t,s}=\sum_{i=0}^{d-t}\sum_{r=t+i}^{d}h_{r,i}s^{r-i}k^{i}.$
(2.3)

Moreover, $h_{d,d-t}$ is always non-zero. If $t\leq d-1$, then $h_{d,d-t-1}$
is also non-zero.

###### Proof.

We first collect the following three standard facts. As these are elementary
facts, we state them without proofs.

First, it is well-known that
$\mathbf{id}^{1}\mathord{\upharpoonright}_{[t]},\dots,\mathbf{id}^{t-1}\mathord{\upharpoonright}_{[t]}$
are linearly independent vectors in $\mathbb{R}^{t}$. Second, the following
holds for each $i\in[t-1]$.

$\displaystyle\mathbf{id}^{i}\cdot\mathbf{b}^{t,s}=0.$ (2.4)

Third, for each $i\geq t$, the vector
$\mathbf{id}^{i}\mathord{\upharpoonright}_{[t]}$ is not a linear combination
of
$\mathbf{id}^{1}\mathord{\upharpoonright}_{[t]},\dots,\mathbf{id}^{t-1}\mathord{\upharpoonright}_{[t]}$.

The first fact and (2.4) with $s=1$ together imply that ${\rm
Span}(\mathbf{id}^{1}\mathord{\upharpoonright}_{[t]},\dots,\mathbf{id}^{t-1}\mathord{\upharpoonright}_{[t]})$
is the orthogonal complement of the vector $\mathbf{b}^{t,1}$ in
$\mathbb{R}^{t}$. Thus the third fact implies that, for each $i\in[t,d]$, the
vector $\mathbf{id}^{i}\mathord{\upharpoonright}_{[t]}$ does not lie in the
orthogonal complement of $\mathbf{b}^{t,1}$ in $\mathbb{R}^{t}$. In other
words, we have

$\displaystyle\mathbf{id}^{i}\cdot\mathbf{b}^{t,s}=(\mathbf{id}^{i}\cdot\mathbf{b}^{t,1})s^{i}=\left\\{\begin{array}[]{ll}0&\text{if
}i\in[t-1]\\\ \text{$c^{\prime}(t,i)s^{i}$}&\text{if
}i\in[t,d]\end{array}\right.$ (2.7)

for some non-zero integer $c^{\prime}(t,i)$ with $|c^{\prime}(t,i)|\leq
q^{1/2}$ as $1/q\ll 1/d.$ By using (2.1), the following equality is
straightforward for each $t\in[d]$.

$\mathbf{m}^{k}\cdot\mathbf{b}^{t,s}=\sum_{i=0}^{d-1}\left(\sum_{r=i+1}^{d}a_{r}\binom{r}{i}(\mathbf{id}^{r-i}\cdot\mathbf{b}^{t,s})\right)k^{i}.$

However, (2.7) implies that $\mathbf{id}^{r-i}\cdot\mathbf{b}^{t,s}$ is zero
for $r-i<t$ and is $c^{\prime}(t,r-i)s^{r-i}$ otherwise. So we obtain

$\mathbf{m}^{k}\cdot\mathbf{b}^{t,s}=\sum_{i=0}^{d-t}\left(\sum_{r=t+i}^{d}a_{r}\binom{r}{i}c^{\prime}(t,r-i)s^{r-i}\right)k^{i}.$

By letting

$h_{r,i}=a_{r}\binom{r}{i}c^{\prime}(t,r-i)$

for each $r\in[t,d]$ and $i\in[0,d-t]$, we obtain the desired inequality
$|h_{r,i}|\leq q$ as $|c^{\prime}(t,r-i)|\leq q^{1/2}$ and $1/q\ll 1/\|p\|$.

Furthermore, because (2.7) implies that $c^{\prime}(t,i)$ is nonzero for
$i\geq t$, the number $h_{d,d-t}=a_{d}\binom{d}{d-t}c^{\prime}(t,t)$ is also
nonzero. If $t\leq d-1$, then (2.7) implies that $c^{\prime}(t,t+1)$ is non-
zero, so the number $h_{d,d-t-1}=a_{d}\binom{d}{d-t-1}c^{\prime}(t,t+1)$ is
also a nonzero number, confirming the moreover part of the statement. This
proves the proposition. ∎

The previous proposition provides a $k$-ary expression of a number
$\mathbf{m}^{k}\cdot\mathbf{b}^{t,s}$ with small coefficients. To prove Lemma
2.2, we will find our desired vector $\mathbf{v}^{\prime}$ as a sum of several
$\mathbf{b}^{t,s}$, then Proposition 2.4 provides a better prediction on the
value of $\mathbf{m}^{k}\cdot\mathbf{v}^{\prime}$.

###### Proof of Lemma 2.2.

We plan to define several vectors
$\mathbf{c}^{d-1,1},\mathbf{c}^{d-1,2},\dots,\mathbf{c}^{d-1,w_{d-1}},\mathbf{c}^{d-2,1},\dots\mathbf{c}^{1,w_{1}}$
in such a way that $c_{t,i}:=\mathbf{c}^{t,i}\cdot\mathbf{m}^{k}$ forms a
sequence satisfying the conditions of Proposition 2.3. This would give us
appropriate numbers $b_{d-1,1},\dots,b_{1,w_{1}}$ in such a way that $\sum
b_{t,i}c_{t,i}=Q\pm\ell$ holds, then the vector $\mathbf{v}^{\prime}=\sum
b_{t,i}\mathbf{c}^{t,i}$ will be our desired vector with
$\mathbf{v}^{\prime}\cdot\mathbf{m}^{k}=\sum_{i}b_{t,i}c_{t,i}=Q\pm\ell$.

For this purpose, for each $t\in[d-1]$ and $i\in\mathbb{N}$, we choose
$\mathbf{c}^{t,i}$ to be either

$\mathbf{b}^{t,2^{q(i+1)}}-2^{qt}\mathbf{b}^{t,2^{qi}}\text{ or
}-(\mathbf{b}^{t,2^{q(i+1)}}-2^{qt}\mathbf{b}^{t,2^{qi}})$

in such a way that $c_{t,i}:=\mathbf{c}^{t,i}\cdot\mathbf{m}^{k}$ is non-
negative. Note that $\mathbf{c}^{t,i}$ has nonzero values only on its $j$-th
coordinate for
$j\in\\{t2^{j^{\prime}}:t\in[d-1],j^{\prime}\in\\{qi,q(i+1)\\}\\}$.

We now verify that these choices ensure that the sequence $c_{t,i}$ satisfies
the conditions of the Proposition 2.3. By Proposition 2.4, we have the
following equality with some integers $h_{r,j}$ satisfying $|h_{r,j}|\leq q$.

$\displaystyle c_{t,i}$ $\displaystyle=$
$\displaystyle\left|\sum_{j=0}^{d-t}\sum_{r=t+j}^{d}h_{r,j}2^{q(i+1)(r-j)}k^{j}-2^{qt}\cdot\sum_{j=0}^{d-t}\sum_{r=t+j}^{d}h_{r,j}2^{qi(r-j)}k^{j}\right|$
(2.8) $\displaystyle=$
$\displaystyle\left|\sum_{j=0}^{d-t-1}\sum_{r=t+j+1}^{d}h_{r,j}(2^{q(r-j)}-2^{qt})2^{qi(r-j)}k^{j}\right|.$

The final equality holds as the term for $r=t+j$ vanishes because
$2^{q(r-j)}-2^{qt}$ is zero when $r=t+j$. Moreover, if $k$ is much bigger than
$q$, then the term with highest exponent in $k$ becomes much bigger than all
other terms. The following claim provides this fact.

######  Claim 2.5.

If $i\in\mathbb{N}$ satisfies $2^{q(i-1)}\leq k^{1/2}$, then we have

$\displaystyle c_{t,i-1}<c_{t,i}\leq 2^{2qd}c_{t,i-1}\enspace\text{ and
}\enspace q2^{qi(t+1)}k^{d-t-1}<c_{t,i}<q2^{q(i+1)(t+1)}k^{d-t-1}.$ (2.9)

###### Proof.

Note that $1/k\ll 1/q\ll 1/\|p\|$ implies $d^{2}q2^{2qd}<k^{1/8}$. As
$|h_{r,j}|\leq q$, we have

$\displaystyle\left|\sum_{j=0}^{d-t-2}\sum_{r=t+j+1}^{d}h_{r,j}(2^{q(r-j)}-2^{qt})2^{qi(r-j)}k^{j}\right|$
$\displaystyle\leq$
$\displaystyle\sum_{j=0}^{d-t-2}\sum_{r=t+j+1}^{d}q2^{qd}2^{qi(t+1+r-t-j-1)}k^{j}$
$\displaystyle\leq$
$\displaystyle\sum_{j=0}^{d-t-2}\sum_{r=t+j+1}^{d}q2^{2qd}2^{qi(t+1)}2^{q(i-1)(r-t-j-1)}k^{j}$
$\displaystyle\leq$
$\displaystyle\sum_{j=0}^{d-t-2}\sum_{r=t+j+1}^{d}d^{-2}2^{qi(t+1)}k^{(r-t-j-1)/2+j+1/8}$
$\displaystyle\leq$ $\displaystyle 2^{qi(t+1)}k^{d-t-5/4}.$

Here, the second inequality holds as $r-t-j-1\leq d$ and the final inequality
holds as $(r-t-j-1)/2+j\leq d-t-3/2$ for $j\leq d-t-2$ and $r\leq d$. As
$t\in[d-1]$, the number $h_{d,d-t-1}$ is non-zero by Proposition 2.4, so we
obtain

$\displaystyle c_{t,i}$ $\displaystyle=$
$\displaystyle\left|h_{d,d-t-1}(2^{q(t+1)}-2^{qt})2^{qi(t+1)}(k^{d-t-1}\pm
k^{d-t-5/4})\right|.$

Moreover, $h_{d,d-t-1}$ is a non-zero integer in $[-q,q]$ and $1/k\ll
1/q,1/\|p\|$ and $q<2^{q(t+1)}-2^{qt}\leq 2^{q(t+1)}$, the above equality
yields the second desired inequality as follows:

$\displaystyle q2^{qi(t+1)}k^{d-t-1}<c_{t,i}<q2^{q(i+1)(t+1)}k^{d-t-1}.$

As this inequality holds for $i-1$ as well, this implies that

$c_{t,i-1}<q2^{qi(t+1)}k^{d-t-1}<c_{t,i}<q2^{q(i+1)(t+1)}k^{d-t-1}<2^{2q(t+1)}c_{t,i-1}\leq
2^{2qd}c_{t,i-1}$

and proves the claim. ∎

Let $w_{1}$ be the number satisfying $2^{q(w_{1}-1)}\leq k^{1/2}<2^{qw_{1}}$.
Then Claim 2.5 with this choice of $w_{1}$ implies that
$c_{1,1},\dots,c_{1,w_{1}}$ is a sequence satisfying (2.9). Moreover, we
obtain

$c_{1,w_{1}}>q2^{2qw_{1}}k^{d-2}\geq qk^{d-1}.$

For $t\geq 2$, assume that we have defined $w_{t-1}$. Consider the number
$w^{\prime}$ satisfying $2^{q(w^{\prime}-1)}\leq k^{1/2}\leq 2^{qw^{\prime}}$.
Then Claim 2.5 with this choice implies that

$c_{t,w^{\prime}}>q2^{qw^{\prime}(t+1)}k^{d-t-1}\geq qk^{(t+1)/2}k^{d-t-1}\geq
qk^{d-t}>2^{-2qd}c_{t-1,1}.$

Here, the final inequality holds by (2.9). Now let $w_{t}$ be the smallest
number such that $c_{t,w_{t}}\leq c_{t-1,1}\leq 2^{qd}c_{t,w_{t}}$. By the
definition of $w_{t}$ and the above inequality, $w_{t}$ exists and it has
value at most $w^{\prime}$. Hence, Claim 2.5 applies for all $i\leq w_{t}$,
thus the sequence $c_{t,1},\dots,c_{t,w_{t}}$ satisfies (2.9). Repeating this
yields the sequence

$c_{d-1,1},\dots,c_{d-1,w_{d-1}},c_{d-2,1},\dots,c_{1,w_{1}}$

satisfying that a term in the sequence is bigger than the previous term and at
most $2^{2qd}$ times the previous term. Furthermore, $c_{d-1,1}$ can be
written as a function of $q,d$ and the coefficients of the polynomial $p(z)$,
the hierarchy $1/\ell\ll 1/q,1/\|p\|$ implies $c_{d-1,1}\leq\ell$.

Proposition 2.3 implies that there exists numbers $b_{t,i}\in[2^{2qd}]$
satisfying

$\sum_{t\in[d-1]}\sum_{i\in[w_{t}]}b_{t,i}c_{t,i}=Q\pm\ell.$

Let $\mathbf{v}^{\prime}=\sum_{i\in[w_{t}]}b_{t,i}\mathbf{c}_{t,i}$. Then it
is easy to see that each coordinate of $\mathbf{c}_{t,i}$ has absolute value
at most $\ell$ as $1/\ell\ll 1/q,1/\|p\|$. Moreover, by our choices of
$\mathbf{c}_{t,i}$ it is easy to see that $\mathbf{v}_{i}=0$ for all
$i\notin\\{t2^{j}:t\in[d-1],1\leq j\leq q+\frac{1}{2}\log{k}\\}$. This proves
the lemma. ∎

The following proposition establishes an ‘independence’ over the numbers
$m_{s}(k)$, by showing that any nontrivial integral combination of $t<d$
numbers $m_{1}(k),m_{2}(k),\dots,m_{t}(k)$ is far from zero.

######  Proposition 2.6.

Suppose $0<1/k\ll 1/q\ll 1/\|p\|,1/d\leq 1/2$ and $t\in[d-1]$. For any nonzero
vector $(c_{1},\dots,c_{d-1})\in[-\frac{k}{q},\frac{k}{q}]^{t}$, we have
$|\sum_{i\in[t]}c_{i}\cdot m_{i}(k))|>\frac{1}{2}k^{d-t}$.

###### Proof.

For each $i\in\mathbb{N}$, let $\mathbf{v}^{i}\in[-q,q]^{d}$ be an integer
vector such that for each $0\leq j\leq d-1$, the $(j+1)$-th coordinate of the
vector $\mathbf{v}^{i}$ is

$(\mathbf{v}^{i})_{j+1}=\sum_{r=j+1}^{d}a_{r}\binom{r}{j}i^{r-j}.$

Note the resemblance of this vector with the ‘$k$-ary expansion’ of $m_{s}(k)$
in the expression (2.1).

We will first show that at least one of the last $t$ coordinates of
$\sum_{i\in[t]}c_{i}\mathbf{v}^{i}$ has a non-zero absolute value. Let $U$ be
a $d\times t$ matrix whose columns are
$\mathbf{v}^{1},\mathbf{v}^{2},\dots,\mathbf{v}^{t}$. Let $U_{1},\dots,U_{d}$
be the rows of $U$ and let $U^{\prime}$ be the submatrix of $U$ with rows
$U_{d-t+1},\dots,U_{d}$. Then for each $0\leq j\leq d-1$, we have

$\displaystyle U_{j+1}$
$\displaystyle=\sum_{r=j+1}^{d}a_{r}\binom{r}{j}\left(1^{r-j},2^{r-j},\dots,t^{r-j}\right)=a_{d}\binom{d}{j}\mathbf{id}^{d-j}_{[t]}+\sum_{r=j+1}^{d-1}a_{r}\binom{r}{j}\mathbf{id}^{r-j}_{[t]}.$

Hence $U_{j+1}$ is a linear combination of
$\mathbf{id}^{d-j}_{[t]},\dots,\mathbf{id}^{1}_{[t]}$, with the coefficient of
$\mathbf{id}^{d-j}_{[t]}$ being nonzero. It is a standard fact that
$\\{\mathbf{id}^{t}_{[t]},\dots,\mathbf{id}^{1}_{[t]}\\}$ forms a basis of
$\mathbb{R}^{t}$. Using this basis, the above inequality implies that
$U^{\prime}$ is row-equivalent to an upper triangular matrix with nonzero
diagonals, hence $U^{\prime}$ is a full rank $t\times t$ matrix. Thus, for any
nonzero $(c_{1},\dots,c_{t})$, at least one of the last $t$ coordinates of
$\sum_{i=1}^{t}c_{i}\mathbf{v}^{i}$ is nonzero. Assume that $r\in[d-t,d-1]$ is
the largest number such that the $(r+1)$-th coordinate of
$\sum_{i=1}^{t}c_{i}\mathbf{v}^{i}$ is nonzero. As we have
$m_{i}(k)=\sum_{j=0}^{d-1}(\mathbf{v}^{i})_{j+1}k^{j}$, we conclude that

$\Big{|}\sum_{i=1}^{t}c_{i}\cdot
m_{i}(k))\Big{|}=\Big{|}\sum_{j=0}^{d-1}\sum_{i=1}^{t}c_{i}(\mathbf{v}^{i})_{j+1}k^{j}\Big{|}\geq
k^{r}-\sum_{i=0}^{r-1}qk^{i}>\frac{1}{2}k^{d-t}.$

Here, the penultimate inequality holds as $1/q\ll 1/\|p\|$. ∎

###  2.3. Other tools

The following proposition is also useful for identifying the structure of a
coloring with no bad pairs.

######  Proposition 2.7.

Let $n,m,Q$ be integers with $Q\geq 2n+4m$ where $m$ is odd. Let
$\phi:[n,Q-n]\rightarrow\\{-1,1\\}$ be a coloring satisfying the following for
any $a,b\in[n,Q-n]$.

  1. (A1)

$\phi(a)\leq\phi(a+m)$ for all $a\in[n,Q-n-m]$.

  2. (A2)

If $a+b=Q$, then at least one of $a,b$ has color $-1$.

  3. (A3)

If $a+b=Q+m$, then at least one of $a,b$ has color $+1$.

Then any number in $[Q+m+1,2Q-2n-2m]$ can be written as a sum of two numbers
of color $+1$ and any number in $[2n+2m,Q-1]$ can be written as a sum of two
numbers of color $-1$.

###### Proof.

For each $j\in\mathbb{N}$, consider the arithmetic sequence $\mathbf{a}^{j}$
of difference $m$ containing all numbers in $[n,Q-n]$ which are congruent to
$j$ modulo $m$. Then it is easy to see that $\min(\mathbf{a}^{j})\leq n+m$ and
$\max(\mathbf{a}^{j})\geq Q-n-m$.

Assume $Q\equiv j_{*}$ (mod $m$) for some $j_{*}\in\mathbb{Z}_{m}$. Let $A$ be
the set of those $j\in\mathbb{Z}_{m}$ for which the sequence $\mathbf{a}^{j}$
does not contain any number $x$ of color $-1$ satisfying $x>Q/2$. Similarly,
let $B$ be the set of those $j\in\mathbb{Z}_{m}$ for which the sequence
$\mathbf{a}^{j}$ does not contain any number $x$ of color $+1$ satisfying
$x<Q/2+m/2$.

We now claim that $|A|>m/2$. To show this, suppose that neither $j$ nor
$j_{*}-j$ is in $A$ for some $j\in\mathbb{Z}_{m}$. Then $\mathbf{a}^{j}$
contains a number $b>Q/2$ of color $-1$ and $\mathbf{a}^{j_{*}-j}$ contains a
number $b^{\prime}>Q/2$ of color $-1$. Then we have $b+b^{\prime}>Q$ and
$b+b^{\prime}\equiv j_{*}\equiv Q$ (mod $m$), so $b+b^{\prime}\geq Q+m$. On
the other hand, by (A1), any number in $\mathbf{a}^{j}$ smaller than or equal
to $b$ has color $-1$ and any number in $\mathbf{a}^{j_{*}-j}$ smaller than or
equal to $b^{\prime}$ has color $-1$. Hence the sums
$b+b^{\prime},(b-m)+b^{\prime},b+(b^{\prime}-m),\dots,\min(\mathbf{a}^{j})+\min(\mathbf{a}^{j_{*}-j})$
yield all numbers in $b+b^{\prime},b+b^{\prime}-m,\dots,2n+2m+j_{*}$ and this
contains $Q+m$ because $2n+2m+j_{*}\leq Q+m\leq b+b^{\prime}$. This
contradicts (A3). Hence, at least one of $j$ and $j_{*}-j$ must belong to $A$.
As $m$ is an odd number, this implies $|A|>m/2$.

Furthermore, we also claim that $|B|>m/2$. Similarly as before, suppose that
neither $j$ nor $j_{*}-j$ is in $B$ for some $j\in\mathbb{Z}_{m}$. Then
$\mathbf{a}^{j}$ contains a number $b<Q/2+m/2$ of color $+1$ and
$\mathbf{a}^{j_{*}-j}$ contains a number $b^{\prime}<Q/2+m/2$ of color $+1$.
Thus $b+b^{\prime}<Q+m$ and $b+b^{\prime}\equiv j_{*}\equiv Q$ (mod $m$), thus
$b+b^{\prime}\leq Q$. On the other hand, by (A1), any number in
$\mathbf{a}^{j}$ bigger than or equal to $b$ has color $+1$ and any number in
$\mathbf{a}^{j_{*}-j}$ bigger than or equal to $b^{\prime}$ has color $+1$.
Hence, the sums
$b+b^{\prime},(b+m)+b^{\prime},b+(b^{\prime}+m),\dots,\max(\mathbf{a}^{j})+\max(\mathbf{a}^{j_{*}-j})$
yield all numbers in $b+b^{\prime},b+b^{\prime}+m,\dots,2Q-3m+j_{*}$ and this
contains $Q$ because $b+b^{\prime}\leq Q\leq 2Q-2n-3m$. This contradicts (A2).
Hence at least one of $j$ and $j_{*}-j$ must belong to $B$. As $m$ is an odd
number, this implies $|B|>m/2$.

As both $A$ and $B$ contains more than $m/2$ numbers in $\mathbb{Z}_{m}$, it
is easy to see the following

$A+A=\mathbb{Z}_{m}=B+B.$

Hence, for any number $x\in[Q+m+1,2Q-2n-2m]$, there exist $j,j^{\prime}\in A$
with $x\equiv j+j^{\prime}$ (mod $m$). Let $b$ be the smallest number of color
$+1$ in $\mathbf{a}^{j}$ and $b^{\prime}$ be the smallest number of color $+1$
in $\mathbf{a}^{j^{\prime}}$. As $j,j^{\prime}\in A$, those numbers $b$ and
$b^{\prime}$ exist and satisfy $b\leq Q/2+m$ and $b^{\prime}\leq Q/2+m$. Thus
$b+b^{\prime}\leq Q+2m$, and $b+b^{\prime}\equiv x$ (mod $m$). This implies
that the sums
$b+b^{\prime},(b+m)+b^{\prime},b+(b^{\prime}+m),\dots,\max(\mathbf{a}^{j})+\max(\mathbf{a}^{j^{\prime}})$
yield all numbers in $[Q+m+1,2Q-2n-2m]$ which are congruent to $x$ modulo $m$.
Here, we used the fact that
$\max(\mathbf{a}^{j})+\max(\mathbf{a}^{j^{\prime}})\geq 2Q-2n-2m$. As this
contains $x$, (A1) implies that the number $x$ can be written as a sum of two
numbers of color $+1$.

Similarly, for any number $y\in[2n+2m,Q-1]$, there exist $j,j^{\prime}\in B$
with $y\equiv j+j^{\prime}$ (mod $m$). Let $b$ be the largest number of color
$-1$ in $\mathbf{a}^{j}$ and $b^{\prime}$ be the largest number of color $-1$
in $\mathbf{a}^{j^{\prime}}$. As $j,j^{\prime}\in B$, those numbers $b$ and
$b^{\prime}$ exist and satisfy $b\geq Q/2-m/2$ and $b^{\prime}\geq Q/2-m/2$.
Thus $b+b^{\prime}\geq Q-m$ and $b+b^{\prime}\equiv y$ (mod $m$). This implies
that the sums
$b+b^{\prime},(b-m)+b^{\prime},b+(b^{\prime}-m),\dots,\min(\mathbf{a}^{j})+\min(\mathbf{a}^{j^{\prime}})$
yield all numbers in $[2n+2m,Q-1]$ which are congruent to $y$ modulo $m$.
Here, we used the fact that
$\min(\mathbf{a}^{j})+\min(\mathbf{a}^{j^{\prime}})\leq 2n+2m$. Thus this
contains $y$, (A1) implies that the number $y$ can be written as a sum of two
numbers of color $-1$. ∎

Consider the following _grid digraph_ $G(n)$ with the vertex set
$[0,n]\times[0,n]$ and the arc set consisting of the directed edges from
$(i,j)$ to $(i,j+1)$ and from $(i,j)$ to $(i+1,j)$. Furthermore, let $G(n;m)$
be the induced subgraph of $G(n)$ induced by the set of all the vertices
$(i,j)\in[0,n]\times[0,n]$ with $|i-j|\leq m$. We call $G(n;m)$ a _reduced
grid digraph_ and we write $L_{s}$ to denote the set of all vertices $(i,j)$
in $G(n;m)$ with $i+j=s$, and call this set _level $s$_ of the graph $G(n;m)$.
Note that $|L_{s}|\leq m+1$ in $G(n;m)$ for any $s\in[0,2n]$. We write
$L(s,t)=\bigcup_{i\in[s,t]}L_{i}$ for the set of all vertices of level $j$ for
all $s\leq j\leq t$. Then the following lemma says that if a vertex set $Z$ is
small and ‘thin’, then we can find a path from $(0,0)$ to $(n,n)$ avoiding the
vertices of $Z$.

######  Lemma 2.8.

Suppose $0<1/n\ll\eta\ll 1/\ell\ll 1$ and let $m=\eta^{2}n$ be an integer. Let
$Z\subseteq G(n;m)$ be a set of vertices satisfying the following.

  1. (G1)

$|Z|\leq\frac{1}{10}m$.

  2. (G2)

For each $i\leq\frac{m}{\ell}$, both sets $L(0,i\ell)$ and $L(2n-i\ell,2n)$
contains at most $(i-1)$ vertices of $Z$.

Then $G(n;m)$ contains a directed path $P$ from the vertex $(0,0)$ to the
vertex $(n,n)$ which does not intersect $Z$.

###### Proof.

We first prove the following claim.

######  Claim 2.9.

For $i\in[2n]$ and a nonempty set $A\subseteq L_{i}$, its out-neighborhood
$N^{+}(A)$ in the graph $G(n;m)$ satisfies the following.

  1. (a)

If $i<m$, then $|N^{+}(A)|\geq|A|+1$.

  2. (b)

If $m\leq i\leq n-1$ and $i$ has different parity from $m$, then
$|N^{+}(A)|\geq|A|+1$.

  3. (c)

If $m\leq i\leq n-1$ and $i$ has the same parity as $m$, then
$|N^{+}(A)|\geq|A|-1$.

###### Proof.

If $i<m$ or $i$ has different parity from $m$, then we consider

$A_{0}=\\{(i+1,j):(i,j)\in A\\}\enspace\text{and}\enspace
A_{1}=\\{(i,j+1):(i,j)\in A\\}.$

For such a number $i$, it is easy to see that these two sets have the same
size as $A$ and they are not identical, we have $|N^{+}(A)|=|A_{0}\cup
A_{1}|\geq|A|+1$, yielding (a) and (b).

If $m\leq i\leq n-1$ and $i$ has the same parity as $m$, then $A_{0}$ has size
at least $|A|-1$, so (c) holds. ∎

For each $i\in[2n]$, let $Z_{i}=Z\cap L_{i}$ be the set of vertices in $Z$
which belong to the $i$-th level. Consider the graph $G^{\prime}=G(n;m)-Z$.
For each $i\in[m]$, let $S_{i}$ be the set of vertices $v$ at level $i$ such
that $G^{\prime}$ contains a directed path from $(0,0)$ to $v$. Note that for
$S\subseteq(L_{i}\setminus Z)$, we have

$N^{+}_{G^{\prime}}(S)=N^{+}_{G(n;m)}(S)\setminus Z_{i+1}.$

Note that (G2) with $i=1$ implies that $L(0,\ell)$ does not contain any
vertices of $Z$. Thus we have $|S_{\ell}|=\ell+1$. For $t\in[m-\ell]$, we can
apply Claim 2.9 (a) $t$ times to obtain the sizes of the $t$-th out-
neighborhood of $S_{\ell}$ in the digraph $G^{\prime}=G(n;m)-B$ to conclude

$|S_{\ell+t}|\geq\ell+t-\sum_{i\in[t]}|Z_{\ell+i}|\geq\ell+t-\frac{t}{\ell}\geq\ell+(1-\frac{1}{\ell})t.$

Indeed, this shows that the set $S_{\ell+t}$ never become an empty set for
$t\in[m-\ell]$, thus we can again apply Claim 2.9 to obtain the inequality for
$t+1$ and so on. From this, we conclude that
$|S_{m}|\geq\ell+(1-\frac{1}{\ell})m\geq\frac{4}{5}m$.

Again, we apply Claim 2.9 (b) and (c) repeatedly to the vertex set $S_{m}$ to
obtain the size of the $t$-th out-neighborhood $S_{m+t}$ of $S_{m}$ in
$G^{\prime}$ for $t\in[n-m]$. As $|Z|\leq\frac{1}{10}m$, we have

$|S_{n}|\geq\frac{4}{5}m-1-|Z|\geq\frac{2}{3}m.$

Similarly, we consider paths towards the vertex $(n,n)$. A symmetric argument
again gives that there are at least $\frac{2}{3}m$ vertices $v$ in $S_{n}$
which admit a path from $v$ to $(n,n)$ in $G^{\prime}$. As $|L_{n}|\leq
m+1<\frac{2}{3}m+\frac{2}{3}m$, there exists a vertex $v\in L_{n}$ such that
$G^{\prime}$ admits a path from $(0,0)$ to $v$ and from $v$ to $(n,n)$. These
two paths together yield a desired path. ∎

Finally, we need the following inequality.

######  Lemma 2.10.

For $m,n\in\mathbb{N}$, let $x_{1},\dots,x_{n}$ be a sequence satisfying
$\sum_{j\in[i]}jx_{j}\leq(i-1)m$ for all $i\in[n]$. Then we have
$\sum_{j\in[n]}x_{j}\leq 2m(1+\log n)$.

###### Proof.

Suppose $\sum_{j\in[n]}x_{j}>2m(1+\log n)$. For each $0\leq i\leq\log n$
consider the intervals $I_{i}=[2^{i},2^{i+1}]$. By averaging, there exists
$0\leq i\leq\log n$ satisfying $\sum_{j\in I_{i}}x_{j}>2m.$ However, this
implies

$\sum_{j\leq 2^{i+1}}jx_{j}\geq\sum_{j\in I_{i}}2^{i}x_{j}>2^{i+1}m,$

which contradicts the assumption of the lemma. This proves the lemma. ∎

##  3\. Counting monochromatic solutions

Throughout this section, we assume that a non-odd polynomial $p(z)$ of degree
$d\geq 2$ with a positive leading coefficient and a $2$-coloring
$\phi:\mathbb{N}\rightarrow\\{-1,1\\}$ are given. We also assume that $k$ is a
positive switch and the numbers $\eta,\varepsilon\in(0,1)$ and
$q,\ell\in\mathbb{N}$ are chosen according to the following hierarchy:

$\displaystyle
0<\frac{1}{k}\ll\eta\ll\varepsilon\ll\frac{1}{\ell}\ll\frac{1}{q}\ll\frac{1}{\|p\|},\quad\frac{1}{d}\leq\frac{1}{2}.$
(3.1)

As $k$ is sufficiently large, we have that $m_{s}(k)>0$ for all $s\geq 1$.
Recall that we have defined $(k,s)$-bad pair $\\{a,b\\}$ and Lemma 2.1 yields
that many pairwise disjoint bad pairs provide many monochromatic solutions.

Recall that we have defined two numbers $k_{1}$ and $k_{0}$, and we further
define $k_{2}$ as follows.

$k_{2}:=\frac{1}{q}k,\enspace
k_{1}:=\max\\{t:p(t)<\frac{1}{2}p(k))\\}\enspace\text{and}\enspace
k_{0}:=\max\\{t:p(t)<2p(k)-4m_{1}(k)\\}.$

As $1/k\ll\varepsilon$, we can estimate that $k_{1}=(2^{-1/d}\pm\varepsilon)k$
and $k_{0}=(2^{1/d}\pm\varepsilon)k$. As $k$ is sufficiently large, we may
assume that $p(z)$ is a strictly increasing function on $[k_{2},\infty)$.

The following lemma allows us to deal with the case where $k$ is a non-
isolated switch.

######  Lemma 3.1 ([11]).

If $k$ is a non-isolated switch, then the interval $[p(k)]$ contains at least
$k^{1-o(1)}$ distinct monochromatic solutions.

As we will use this lemma to deal with the case when $k$ is a non-isolated
switch, we will deal with the case where $k$ is an isolated switch in the rest
of this section. Under this assumption, $a\in\Phi^{+}$ and $b\in\Phi^{-}$ such
that the difference $b-a$ is $m_{s}(k)$ for some $s<k_{0}-k$ will yield a bad
pair $\\{a,b\\}$.

###  3.1. Utilizing nested pairs of almost monochromatic intervals

In this subsection, we present a key lemma, Lemma 3.4, which provides many
monochromatic solutions utilizing a sequence of nested pairs of almost
monochromatic intervals of opposite colors. Let us warm up with a single pair
of intervals.

Assume that we have an interval $P$ mostly consisting of numbers from
$\Phi^{+}$ and another interval $N$ mostly consisting of numbers from
$\Phi^{-}$ with $\min(P)<\min(N)$. By expressing $\min(N)-\min(P)$ as an
integral combination of the numbers $m_{s}(k)$ and considering a sequence as
we explained in Section 2.1, we may obtain many monochromatic solutions. The
following lemma proves this.

######  Lemma 3.2.

Suppose that $k$ is an isolated switch and two intervals
$P,N\subseteq[1,p(k)-k]$ satisfy the following.

  1. (P1)

$|P|=|N|=r<m_{1}(k)$.

  2. (P2)

$\min(N)-\min(P)\geq\ell^{2}k^{d-1/2}$.

  3. (P3)

$|P\cap\Phi^{+}|+|N\cap\Phi^{-}|\geq\frac{5}{4}r.$

Then, there exists at least $r/4-2\ell$ distinct monochromatic solutions in
$[p(k)]$.

###### Proof.

As $k$ is an isolated switch, every pair $\\{a,b\\}\subseteq[p(k)]$ with
$b=a+m_{s}(k)$, $s\in[k_{0}-k]$ and $\phi(a)>\phi(b)$ forms a bad pair. Let
$T=\min(N)-\min(P)$. Let $I:=\\{t2^{j}:t\in[d-1],1\leq j\leq
q+\frac{1}{2}\log{k}\\}$ and

$M:=\sum_{i\in I}\ell\cdot m_{i}(k).$

As it is easy to see $m_{i}(k)\leq 2^{2q}k^{d-1}$ for each $i\in I$ from
(2.1), this choice of $M$ yields $M<\ell^{2}k^{d-1/2}.$ Let $s$ be the maximum
non-negative integer such that

$sm_{1}(k)\leq T-M.$

The maximality of $s$ ensures $T-M-sm_{1}(k)\leq m_{1}(k)\leq qk^{d-1}$.
Hence, Proposition 2.2 together with (3.1) implies that there exists a vector
$\mathbf{v}\in[-\ell,\ell]^{k}$ such that $\mathbf{m}^{k}\cdot\mathbf{v}=T-M-
sm_{1}(k)\pm\ell$. This yields

$\displaystyle\mathbf{m}^{k}\cdot(\mathbf{v}+\ell\mathbf{1}_{I})+sm_{1}(k)=T\pm\ell.$
(3.2)

Note that we have $\mathbf{v}+\ell\mathbf{1}_{I}\in[2\ell]^{k}$. Let
$w_{1},\dots,w_{t}$ be an arbitrary sequence such that for each $i\in I$, the
term $m_{i}(k)$ occurs exactly $\mathbf{v}_{i}+\ell$ times in the sequence and
$m_{1}(k)$ occurs exactly $s$ times. Note that $1\notin I$.

For each $x\in P$ and $j\in[0,t]$, let

$u_{j}(x):=x+\sum_{i\in[j]}w_{i}.$

Together with (P1) and (3.2), we conclude that for all numbers
$x\in[\min(P)+\ell,\max(P)-\ell]\cap\Phi^{+}$,

$\displaystyle u_{t}(x)\in N.$ (3.3)

However, (P3) implies that there are at least $r/4-2\ell$ choices of such $x$
satisfying that $\phi(x)=+1$ and $\phi(u_{t}(x))=-1$. This means that the
sequence $u_{0}(x),u_{1}(x),\dots,u_{t}(x)$ contains a bad pair. As two
distinct choices of $x,x^{\prime}$ gives us pairwise disjoint sequences, we
can choose at least $r/4-2\ell$ pairwise disjoint bad pairs, hence Lemma 2.1
implies that there are at least $r/4-2\ell$ distinct monochromatic solutions.
∎

We can use Lemma 3.2 to derive the following lemma for the case of $d=2$.

######  Lemma 3.3.

Suppose that $d=2$ and $k$ is an isolated switch. Then $[p(k)]$ contains at
least $\varepsilon^{2}k$ distinct monochromatic solutions.

###### Proof.

As $k$ is an isolated switch, all numbers in $[k+1,k_{0}]$ are colored with
$-1$. We consider the following two cases.

Case 1. There exists a number $x\in[k_{2},(1-\varepsilon)k_{1}]$ colored with
$-1$. Let

$P:=p(x)-[k+1,k_{0}]\text{ and }N:=p(k)-P.$

As all numbers in $[k+1,k_{0}]$ has color $-1$, if $y\in P=p(x)-[k+1,k_{0}]$
has the color $-1$, then $(y,p(x)-y,x)$ forms a monochromatic solution. Hence,
we may assume that $P$ contains less than $\varepsilon^{2}k$ numbers of color
$-1$. In particular,

$|P\cap\Phi^{+}|\geq k_{0}-k-\varepsilon^{2}k\geq(1-\varepsilon)|P|.$

Then we conclude that

$|N\cap\Phi^{-}|\geq(1-2\varepsilon)|N|,$

as otherwise we obtain at least $\varepsilon|N|\geq\varepsilon^{2}k$
monochromatic solutions of the form $(y,p(k)-y,k)$ with $y\in P\cap\Phi^{+}$
and $p(k)-y\in N\cap\Phi^{+}$. Now we verify that these intervals $P$ and $N$
satisfy the conditions (P1)–(P3) of Lemma 3.2 As $P,N$ are two intervals of
length $k_{0}-k$ and at least $(1-2\varepsilon)$-fraction of the numbers in
$P$ are colored $+1$ and at least $(1-2\varepsilon)$-fraction of the numbers
in $N$ are colored $-1$, (P3) holds. Moreover, as $k$ is sufficiently large,
the definition of $k_{1}$ implies

$p(x)\leq p((1-\varepsilon)k_{1})<(1-\varepsilon)\frac{p(k)}{2},$

hence

$P\subseteq\Big{[}\frac{(1-\varepsilon^{2})p(k)}{2}\Big{]}\text{ and
}N\subseteq\Big{[}\frac{(1+\varepsilon^{2})p(k)}{2},p(k)\Big{]}.$

As $\varepsilon^{2}p(k)>\ell^{2}k^{d-1/2}$, (P2) also holds. As
$|P|=|N|=k_{0}-k\leq m_{1}(k)$, (P1) holds as well. Thus Lemma 3.2 implies
that there are at least $\varepsilon k$ distinct monochromatic solutions in
$[p(k)]$.

Case 2. All the numbers in $[k_{2},(1-\varepsilon)k_{1}]$ has color $+1$. Let

$P^{\prime}:=[k_{2},(1-\varepsilon)k_{1}]\text{ and
}N^{\prime}:=\Big{[}\frac{p(k)-|P^{\prime}|}{2},\frac{p(k)+|P^{\prime}|}{2}\Big{]}.$

Then, at least $0.4$-fraction of the numbers in $N^{\prime}$ have color $-1$,
as otherwise there are $\varepsilon k$ monochromatic solutions of the form
$(y,p(k)-y,k)$ where both $y$ and $p(k)-y$ are in $N^{\prime}$ and colored
$+1$. Hence, $P^{\prime},N^{\prime}$ are two intervals of length
$(1-\varepsilon)k_{1}-k_{2}\geq k/10$ which are at least
$p(k)/4-k_{1}\geq\ell^{2}k^{d-1/2}$ apart, thus (P2) and (P3) both hold. As
$|P^{\prime}|=|N^{\prime}|\leq m_{1}(k)$, Lemma 3.2 implies that there are at
least $\varepsilon k$ distinct monochromatic solutions in $[p(k)]$. ∎

The above lemma is sufficient for us to deal with the case $d=2$, but for
larger values of $d$, it is not sufficient as we need to obtain more
monochromatic solutions. For $d\geq 3$, we will take many interval pairs of
opposite colors and repeatedly apply Lemma 3.2 to those interval pairs
$(P_{i},N_{i})$. If the sets $[\min(P_{i}),\max(N_{i})]$ form disjoint
intervals, then repeated applications of Lemma 3.2 yield disjoint bad pairs.
However, we will only be able to obtain intervals in a nested way as follows.

$[\min(P_{1}),\max(N_{1})]\subseteq[\min(P_{2}),\max(N_{2})]\subseteq\dots\subseteq[\min(P_{\eta
k}),\max(N_{\eta k})]$

As these interval pairs will be nested, application of Lemma 3.2 to the pair
$P_{i_{*}+1},N_{i_{*}+1}$ may yield some new bad pairs within
$[\min(P_{i_{*}}),\max(N_{i_{*}})]$, which could intersect with old bad pairs
obtained in previous pairs of intervals. Hence, we need to ensure that many of
these new bad pairs are disjoint from the old bad pairs.

As explained in Section 2.1, for each $x\in P$, we will choose a sequence from
$x\in P_{i_{*}+1}$ to $y\in N_{i_{*}+1}$ which avoids old bad pairs. Let
$B_{i_{*}}$ be the set of all numbers in an old bad pair. We will restrict our
choice of sequences to certain ‘good’ sequences. Then for each $x\in
P_{i_{*}+1}$, we consider the set $B^{x}$ of all possible numbers $b\in
B_{i_{*}}$, which may be included in some ‘good’ sequence from $x$. By
appropriately designing a ‘good’ sequence to make it compatible with
Proposition 2.6, we can ensure that $B^{x}$ and $B^{x^{\prime}}$ are pairwise
disjoint for all $x\neq x^{\prime}\in P_{i_{*}}$. As we have controls on the
size of $B_{i_{*}}$, this disjointness allows us to choose a large subset
$P^{\prime}\subseteq P_{i_{*}}$ of numbers $x$ such that $B^{x}$ is small and
‘thin’. Furthermore, exploiting the ‘goodness’ of the sequence and using the
fact that $B^{x}$ is small and ‘thin’ for those $x\in P^{\prime}$, we can
transform this into a graph problem regarding paths and utilize Lemma 2.8 to
find an appropriate sequence from $x$ to $y\in N_{i_{*}+1}$ which does not
contain any numbers in $B_{i_{*}}$. The following lemma will encapsulate these
ideas.

######  Lemma 3.4.

Suppose $d\geq 3$ and $k$ is an isolated positive switch and $Q$ is a number
with $\frac{1}{\ell}p(k)\leq Q\leq p(k)$. Suppose that the intervals
$P_{1},\dots,P_{\eta k},N_{1},\dots,N_{\eta k}$ in $[Q]$ satisfy the following
for each $i\in[\eta k]$.

  1. (PN1)

$\varepsilon k<|P_{i}|=|N_{i}|<k/2$ and $N_{i}=Q-P_{i}$.

  2. (PN2)

$\max(P_{i})-\max(P_{i+1})\geq 10\ell m_{1}(k)$,

  3. (PN3)

$\max(N_{1})-\min(P_{1})\geq\frac{1}{\ell}Q$.

  4. (PN4)

$|P_{i}\cap\Phi^{+}|+|N_{i}\cap\Phi^{-}|\geq\frac{5}{4}|P_{i}|.$

Then, there exists at least $\frac{\eta^{3}k^{2}}{2\log{k}}$ distinct
monochromatic solutions in $[p(k)]$.

As Lemma 3.4 is rather involved, we defer its proof to the end of this
section. Lemma 3.4 can be used to prove Lemma 3.5 below to handle all higher
degree polynomials.

######  Lemma 3.5.

If $k$ is an isolated positive switch, and $d\geq 3$, then $[k_{2},p(k)]$
contains at least $\frac{\eta^{3}k^{2}}{2\log{k}}$ distinct monochromatic
solutions.

###### Proof.

As $k$ is an isolated positive switch, every $\\{a,b\\}\subseteq[p(k)]$ with
$b=m_{s}(k)$ for some $s\in[k_{0}-k]$ and $\phi(a)>\phi(b)$ forms a bad set.
Assume for a contradiction that

there are less than $\frac{\eta^{3}k^{2}}{2\log{k}}$ monochromatic solutions.
(3.4)

The following notations will be convenient for us. Let
$k^{\prime}:=\min\\{[k_{1},k]\cap\Phi^{-}\\}$ be the smallest number of color
$-1$ in the interval $[k_{1},k]$ if exists. For each $i\in[k_{2},k]$, let

$\displaystyle\begin{split}A_{i}&:=p(i)-[k+1,k_{0}],\enspace
A^{\prime}_{i}:=p(k)-A_{i},\\\ B_{i}&:=p(i)-[k_{2},k_{1}],\enspace
B^{\prime}_{i}:=p(k+1)-B_{i}\enspace\text{ and }\enspace
B^{\prime\prime}_{i}:=p(k^{\prime})-B_{i}.\end{split}$ (3.5)

We consider the following three cases.

Case 1. $|\Phi^{-}\cap[k_{2},k_{1}]|>3\varepsilon k$.

For each $i\in\Phi^{-}\cap[k_{2},k_{1}]$, if $y\in A_{i}$ satisfies
$\phi(y)=-1$, then $(y,p(i)-y,i)$ forms a monochromatic solution, because
$p(i)-y\in[k+1,k_{0}]\subseteq\Phi^{-}$ is colored $-1$ as $k$ is an isolated
switch. Hence, if more than $\varepsilon k$ elements
$i\in\Phi^{-}\cap[k_{2},k_{1}]$ satisfy $|A_{i}\cap\Phi^{-}|\geq 2\varepsilon
k$, then we obtain at least $2\varepsilon^{2}k^{2}$ distinct monochromatic
solutions, a contradiction to (3.4). Hence, there is
$I\subseteq\Phi^{-}\cap[k_{2},k_{1}]$ with

$\displaystyle|I|\geq|\Phi^{-}\cap[k_{2},k_{1}]|-\varepsilon k\geq
2\varepsilon k\enspace\text{such that}\enspace|A_{i}\cap\Phi^{-}|\leq
2\varepsilon k\text{ for each $i\in I$}.$ (3.6)

Again, for $i\in I$, if more than $3\varepsilon k$ elements $y$ in
$A^{\prime}_{i}$ satisfy $\phi(y)=+1$, then there are at least $3\varepsilon
k-|A_{i}\cap\Phi^{-}|\geq\varepsilon k$ choices of $y\in
A^{\prime}_{i}\cap\Phi^{+}$ satisfying $p(k)-y\in A_{i}\cap\Phi^{+}$ and forms
a monochromatic solution $(y,p(k)-y,k)$. Hence, by the same logic as above, in
order to avoid obtaining $\varepsilon^{2}k^{2}$ monochromatic solutions, we
conclude that there is $I^{\prime}\subseteq I$ with

$\displaystyle|I^{\prime}|\geq|I|-\varepsilon k\geq\varepsilon
k\enspace\text{such that}\enspace|A^{\prime}_{i}\cap\Phi^{+}|\leq 3\varepsilon
k\text{ for each $i\in I^{\prime}$}.$ (3.7)

Let $i_{\eta k}<i_{\eta k-1}<\dots<i_{1}$ be the numbers in $I^{\prime}$ which
are smaller than $k_{1}-2\varepsilon k/3$ such that for each $j\in[\eta k]$,

$\displaystyle i_{j}>i_{j+1}+\ell^{2}.$ (3.8)

Indeed, such numbers exists as $\ell^{2}\eta k<2\varepsilon k/3$. Moreover, as
the polynomial $p$ has degree $d\geq 2$, we know $p(i_{1})\leq
p(k_{1}-2\varepsilon
k/3)=((1-2\varepsilon/3)^{d}+o(1))p(k_{1})<(1-\varepsilon)p(k)/2$. For each
$j\in[\eta k]$, let

$P_{j}:=A_{i_{j}}\enspace\text{and}\enspace N_{j}:=A^{\prime}_{i_{j}}.$

By (3.5), this choice satisfies (PN1) with $Q=p(k)$. As $k_{2}>k/q$, the
equation (3.8), (2.2) and the definition (3.5) of sets $A_{i},A^{\prime}_{i}$
imply that (PN2) holds. Also the fact that $p(i_{1})\leq(1-\varepsilon)p(k)$
implies (PN3), furthermore (3.6) and (3.7) imply (PN4). Hence, we can apply
Lemma 3.4 to conclude that there are at least $\frac{\eta^{3}k^{2}}{2\log{k}}$
distinct monochromatic solutions in this case, a contradiction to the
assumption (3.4).

Case 2. $|\Phi^{-}\cap[k_{2},k_{1}]|\leq 3\varepsilon k$ and
$|\Phi^{+}\cap[k_{1},k]|>3\varepsilon k$.

Consider a number $i\in\Phi^{+}\cap[k_{1},k]$. If $|B_{i}\cap\Phi^{+}|\geq
4\varepsilon k$, then we obtain at least $4\varepsilon
k-|\Phi^{-}\cap[k_{2},k_{1}]|\geq\varepsilon k$ distinct solutions of the form
$(y,p(i)-y,i)$ where $y\in[k_{2},k_{1}]\cap\Phi^{+}$ and $p(i)-y\in
B_{i}\cap\Phi^{+}$. Thus, by the assumption (3.4), at most $\varepsilon k$
numbers $i$ in $\Phi^{+}\cap[k_{1},k]$ satisfy $|B_{i}\cap\Phi^{+}|\geq
4\varepsilon k$. This implies that there exists
$J\subseteq\Phi^{+}\cap[k_{1},k]$ such that

$\displaystyle|J|\geq|\Phi^{+}\cap[k_{1},k]|-\varepsilon k\geq 2\varepsilon
k\enspace\text{such that}\enspace|B_{i}\cap\Phi^{+}|\leq 4\varepsilon k\text{
for each $i\in J$}.$ (3.9)

Again, for each $i\in J$, if more than $5\varepsilon k$ elements $y$ in
$B^{\prime}_{i}$ satisfy $\phi(y)=-1$, (3.9) ensures monochromatic solutions
of the form $(y,p(k)-y,k+1)$ for at least $5\varepsilon
k-|B_{i}\cap\Phi^{+}|\geq\varepsilon k$ choices of $y$. Hence, similarly as
above, at least $\varepsilon k$ choices of $i$ would contradict the assumption
(3.4), we conclude that there exists a set $J^{\prime}\subseteq J$ with

$\displaystyle|J^{\prime}|\geq|J|-\varepsilon k\geq\varepsilon
k\enspace\text{such that}\enspace|B^{\prime}_{i}\cap\Phi^{-}|\leq 5\varepsilon
k\text{ for each $i\in J^{\prime}$}.$ (3.10)

Let $j_{1}<j_{2}<\dots<j_{\eta k}$ be the numbers in $J^{\prime}$ bigger than
$k_{1}+2\varepsilon k/3$ such that for each $i\in[\eta k]$,

$\displaystyle j_{i+1}>j_{i}+\ell^{2}.$ (3.11)

Indeed, such numbers exist as $\ell^{2}\eta k<\varepsilon k/3$. Moreover, as
the polynomial $p$ has degree $d\geq 2$, we have
$p(j_{1})>p(k_{1}+2\varepsilon k/3)\geq
a_{d}(1+2d\varepsilon/3)k_{1}^{d}-q\varepsilon^{2}k_{1}^{d}\geq\frac{1}{2}p(k_{1})+\frac{3}{5}\varepsilon
p(k)$.

For each $i\in[\eta k]$, let

$P_{i}:=B^{\prime}_{j_{i}}\enspace\text{and}\enspace N_{i}:=B_{j_{i}}.$

By (3.5), this choice satisfies (PN1) with $Q=p(k^{\prime})$. By (3.11), (2.2)
and the definition (3.5) of sets $B_{i},B^{\prime}_{i}$, (PN2) hold. Also as
$p(j_{1})\geq\frac{1}{2}p(k_{1})+\frac{3}{5}\varepsilon p(k)$, we also have
(PN3). Finally, (3.9) and (3.10) imply (PN4). Therefore, we can apply Lemma
3.4 to obtain at least $\frac{\eta^{3}k^{2}}{2\log{k}}$ distinct monochromatic
solutions, a contradiction to the assumption (3.4).

Case 3. $|\Phi^{-}\cap[k_{2},k_{1}]|\leq 3\varepsilon k$ and
$|\Phi^{+}\cap[k_{1},k]|\leq 3\varepsilon k$.

In this final case, at most $3\varepsilon k$ numbers in $[k_{1},k]$ are
colored $+1$, so $k^{\prime}$ exists as in (3.5) and it is between $k_{1}$ and
$k_{1}+3\varepsilon k+1$.

Consider a number $i\in\Phi^{+}\cap[k_{2},k_{1}]$. If $|B_{i}\cap\Phi^{+}|\geq
4\varepsilon k$, then we obtain at least $4\varepsilon
k-|\Phi^{-}\cap[k_{2},k_{1}]|\geq\varepsilon k$ distinct solutions of the form
$(y,p(i)-y,i)$ where $y\in[k_{2},k_{1}]\cap\Phi^{+}$ and $p(i)-y\in
B_{i}\cap\Phi^{+}$. Hence, again by (3.4), there are at most $\varepsilon k$
choices of such a number $i$. Thus there exists
$L\subseteq\Phi^{+}\cap[k_{2},k_{1}]$ such that

$\displaystyle|L|\geq k_{1}-k_{2}-|\Phi^{-}\cap[k_{2},k_{1}]|-\varepsilon
k\geq k_{1}-k_{2}-4\varepsilon
k\enspace\text{and}\enspace|B_{i}\cap\Phi^{+}|<4\varepsilon k,~{}~{}\forall
i\in L.$ (3.12)

Again, for a number $i\in L$, if more than $5\varepsilon k$ elements $y$ in
$B^{\prime\prime}_{i}$ satisfy $\phi(y)=-1$, then
$(y,p(k^{\prime})-y,k^{\prime})$ forms a monochromatic solution for at least
$5\varepsilon k-|B_{i}\cap\Phi^{+}|\geq\varepsilon k$ choices of $y\in
B_{i}\cap\Phi^{-}$ and $p(k^{\prime})-y\in B^{\prime\prime}_{i}\cap\Phi^{-}$.
Hence, by the same logic as above, (3.4) implies that there are at most
$\varepsilon k$ choices of such $i$. Thus there is a set $L^{\prime}\subseteq
L$ with

$\displaystyle|L^{\prime}|\geq|L|-\varepsilon k\geq k_{1}-k_{2}-5\varepsilon
k\enspace\text{such that}\enspace|B^{\prime\prime}_{i}\cap\Phi^{-}|\leq
5\varepsilon k\text{ for each $i\in L^{\prime}$}.$ (3.13)

Let $b_{1}<b_{2}<\dots<b_{\eta k}$ be the numbers in $L^{\prime}$ which are
bigger than $k_{1}-6\varepsilon k$ such that for each $i\in[\eta k]$,

$\displaystyle b_{i+1}>b_{i}+\ell^{2}.$ (3.14)

Indeed, such numbers exist as at least $\varepsilon k>\ell^{2}\eta k$ numbers
in $L^{\prime}$ are bigger than $k_{1}-6\varepsilon k$. Moreover, as
$\varepsilon\ll 1/d$ and $k^{\prime}\leq k_{1}+3\varepsilon k$, we have
$p(b_{1})>p(k^{\prime}-9\varepsilon k)\geq\frac{2}{3}p(k^{\prime})$. For each
$i\in[\eta k]$, let

$P_{i}:=B^{\prime\prime}_{b_{i}}\enspace\text{and}\enspace N_{i}:=B_{b_{i}}.$

By the definitions in (3.5), the condition (PN1) is satisfied with
$Q=p(k^{\prime})$. As $k>k_{1}$, $\frac{1}{2}p(k)\leq Q\leq p(k)$ holds. By
(3.14) and (2.2), (PN2) holds. Moreover, as we have
$p(b_{1})-(p(k^{\prime})-p(b_{\eta k}))\geq\frac{1}{3}p(k^{\prime})$, (PN3)
holds and (3.12) and (3.13) imply (PN4). Hence, we can apply Lemma 3.4 to
obtain at least $\frac{\eta^{3}k^{2}}{2\log{k}}$ distinct monochromatic
solutions, a contradiction to (3.4). As we have exhausted all three cases,
this proves the lemma. ∎

###  3.2. Putting things together

We need one more lemma for the proof of Theorem 1.3. As we assume that $k$ is
an isolated switch, all the numbers in $[k+1,k_{0}]$ are colored $-1$. These
consecutive numbers of the same color was very useful for obtaining
monochromatic solutions in the lemmas before. In fact, if we have a much
longer such interval $[k+1,r]$, then we can utilize this to obtain even more
solutions as follows.

######  Lemma 3.6.

Suppose that $k$ is a positive switch and $10qm_{1}(k)\leq
r\leq\frac{1}{2}p(k_{2})$ and $[k+1,r]\subseteq\Phi^{-}$. Then $[p(k)]$
contains at least $\frac{\eta^{2}rk}{m_{1}(k)}$ distinct monochromatic
solutions.

###### Proof.

We consider the following two cases depending on the colors of the numbers in
the smaller interval $[k_{2},k_{1}]$.

Case 1. There exists $x\in[k_{2},k_{1}]$ with color $-1$. For this choice of
$x$, as $x\geq k_{2}$, we have

$r\leq\frac{1}{2}p(k_{2})\leq\frac{1}{2}p(x).$

Consider two intervals

$P:=p(x)-[k+1,r]\text{ and }N:=p(k)-P.$

As $r<p(x)/2$ and $p(x)\leq p(k_{1})\leq\frac{1}{2}p(k)$, we have
$P\subseteq[p(k_{1})-k-1]\subseteq[\frac{1}{2}p(k)-k-1]$. Each $y\in P$ with
color $-1$ yields a monochromatic solution of the form $(y,p(x)-y,x)$ because
$p(x)-y\in[k+1,r]$ is colored with $-1$. Thus we may assume that at least
$(1-\varepsilon)$-fraction of the numbers in $P$ have color $+1$, otherwise we
already obtain at least $\varepsilon r\geq\frac{\eta^{2}rk}{m_{1}(k)}$
distinct monochromatic solutions as $d\geq 2$.

Moreover, at least $(1-2\varepsilon)$-fraction of the number in $N$ has color
$-1$, as otherwise we obtain at least
$\varepsilon(r-k)\geq\frac{\eta^{2}rk}{m_{1}(k)}$ monochromatic solutions of
the form $(y,p(k)-y,k)$ where both $y\in P$ and $p(k)-y\in N$ are colored with
$+1$.

Let $T:=\min(N)-\min(P)$, then as $P\subseteq[\frac{1}{2}p(k)-k-1]$ we have
$r\leq T\leq p(k)$. As $k$ is sufficiently large,
$m_{1}(k)<m_{2}(k)<\dots<m_{k_{0}}(k)$ is an increasing sequence. Furthermore,
from (2.1), we can deduce that for each $i\in[k_{0}-k]$,

$m_{i+1}(k)-m_{i}(k)=a_{d}dk^{d-1}+O(k^{d-2})\text{ and
}m_{1}(k)=a_{d}dk^{d-1}+O(k^{d-2}).$

As $k$ is sufficiently large, this implies $m_{i+1}(k)-m_{i}(k)\leq qm_{1}(k)$
for all $i\in[k_{0}-k]$. Also, the definition of $k_{0}$ yields that

$m_{k_{0}-k}(k)=p(k_{0})-p(k)\geq p(k)-qm_{1}(k).$

From these facts, we conclude that the union of intervals
$\bigcup_{s\in[k_{0}-k]}[m_{s}(k)-qm_{1}(k),m_{s}(k)+qm_{1}(k)]$ covers the
interval $[p(k)]$, hence there exists $s\in[k_{0}-k]$ such that $m_{s}(k)=T\pm
qm_{1}(k)$.

For this choice of $s$, we have $|(m_{s}(k)+P)\cap
N|\geq(r-k)-qm_{1}(k)\geq(\frac{1}{2}+4\varepsilon)r$. As
$(1-2\varepsilon)$-fraction of $P$ has color $+1$ and
$(1-2\varepsilon)$-fraction of $N$ has color $-1$, we obtain at least
$(r-k)/2$ many $(k,s)$-bad sets $\\{a,b\\}$ with $a\in P$ and $b\in N$. Hence,
Lemma 2.1 implies that there are at least
$\frac{r-k}{2}\geq\frac{\eta^{2}rk}{m_{1}(k)}$ distinct monochromatic
solutions.

Case 2. All the numbers in $[k_{2},k_{1}]$ have the color $+1$. Let

$x:=\min\\{y\in[k_{1}+1,k+1]:\phi(y)=-1\\}-1.$

As $\phi(k+1)=-1$, the integer $x$ must exist and every $i\in[k_{2},x]$ is
colored with the color $+1$.

Let $I$ be the set of those numbers $i\in[k_{2},x]$ for which the interval
$p(i)-[k_{2},k_{1}]$ contains at least $\varepsilon k$ numbers of color $+1$.
Note that for each $i\in I$ and the number $y\in p(i)-[k_{2},k_{1}]$ of color
$+1$, we obtain a monochromatic solution $(y,p(i)-y,i)$. As this yields at
least $|I|\times\varepsilon k$ distinct monochromatic solutions, we may assume
that we have $|I|\leq\frac{\eta r}{m_{1}(k)}$. Hence, there are at least
$\frac{r}{4m_{1}(k)}$ numbers between $k-\frac{r}{2m_{1}(k)}$ and $k$ that
does not belong to $I$. Let $J$ be the set of these numbers. Consider a number
$j\in J$. As $r\leq\frac{1}{2}p(k_{2})$, using (2.1) we can check that
$k-j\leq q\eta k$. Thus using (2.1), we have

$k\leq p(k+1)-p(j)=a_{d}d(k-j+1\pm\ell\eta)k^{d-1}\leq(k-j+2)m_{1}(k).$

This implies

$p(j)-[k_{2},k_{1}]\subseteq p(k+1)-[k,k_{1}+(k-j+2)m_{1}(k)]\subseteq
p(k+1)-[k,r].$

Here, the final containment holds as $k-\frac{r}{2m_{1}(k)}\leq j\leq k$ and
$r\geq 10qm_{1}(k)$. Thus for each $y\in p(j)-[k_{2},k_{1}]$ with
$\phi(y)=-1$, we have $p(k+1)-y\in[k,r]\subseteq\Phi^{-1}$, hence
$(y,p(k+1)-y,k+1)$ forms a monochromatic solution of color $-1$. As $j\notin
I$, there are at least $k_{1}-k_{2}-\varepsilon k$ such choices of $y$ for
each $j\in J$. Therefore, we obtain at least

$\frac{r}{2m_{1}(k)}(k_{1}-k_{2}-\varepsilon
k)\geq\frac{\eta^{2}rk}{m_{1}(k)}$

distinct monochromatic solutions. This proves the lemma. ∎

Now, we have collected all the lemmas and we are ready for the proof of
Theorem 1.3.

###### Proof of Theorem 1.3.

Fix a number $q$ with $0<1/n\ll 1/q\ll 1/d,1/\|p\|$ and two constants
$c_{1},c_{2}<1$ with $1/q<a_{d}(10c_{1})^{d}<c_{2}<1/(10a_{d})$ and assume $n$
is sufficiently large. We consider an interval
$I=[c_{1}n^{1/d^{2}},c_{2}n^{1/d}]$. As $n$ is sufficiently large, the
polynomial $p(z)$ is strictly increasing for $z\geq c_{1}n^{1/d^{2}}$.
Moreover, by the choice of $c_{1},c_{2}$, we have

$\displaystyle 2p(2c_{1}n^{1/d^{2}})<c_{2}n^{1/d}\quad\text{ and }\quad
2p(c_{2}n^{1/d})<n.$

Thus if $I$ is monochromatic, we obtain at least $\Omega(n^{2/d^{2}})$
monochromatic solutions of the form $(x,y,z)$ with
$z\in[c_{1}n^{1/d^{2}},2c_{1}n^{1/d^{2}}]$ and $x,y\in I$ as desired.
Otherwise, take the largest switch $k\in I$.

If $k$ is not an isolated switch, there must be another switch $k^{*}$ larger
than $k$ and $p(k^{*})<2p(k)-4m_{1}(k)$ by the definition of an isolated
switch. In particular, $k^{*}<2k$. But the maximality of $k$ implies that such
a switch must not be in $I$. Hence, $c_{2}n^{1/d}<k^{*}<2k$, meaning that
$k>\frac{1}{2}c_{2}n^{1/d}$. Now Lemma 3.1 implies that there are at least
$k^{1-o(1)}=\Omega(n^{1/d-o(1)})>n^{2/d^{2}-o(1)}$ distinct monochromatic
solutions. Thus we may assume that $k$ is an isolated switch.

Case 1. $d\geq 3$. As $k$ is an isolated switch, Lemma 3.5 implies that there
are at least $k^{2-o(1)}\geq n^{2/d^{2}-o(1)}$ distinct monochromatic
solutions.

Case 2. $d=2$. As $k$ is an isolated switch, all numbers in $I$ bigger than
$k$ are colored $-1$.

If $c_{2}n^{1/d}\leq 10qm_{1}(k)$, then as $m_{1}(k)\leq da_{d}k+q$, we have
$k\geq q^{-2}n^{1/d}$. Hence Lemma 3.3 implies that there are at least
$\Omega(k)=\Omega(n^{1/d})\geq\Omega(n^{2/d^{2}})$ distinct monochromatic
solutions.

If $c_{2}n^{1/d}\geq 10qm_{1}(k)$, then $m:=\frac{1}{2}p(\frac{1}{q}k)\leq
c_{2}n^{1/d}$ as $1/q<c_{2}$. Moreover, $m=\Omega(k^{2})=\Omega(n^{2/d^{2}})$
as $k>c_{1}n^{1/d^{2}}$. Thus Lemma 3.6 with $m$ playing the role of $r$
yields at least $\Omega(\frac{mk}{m_{1}(k)})=\Omega(m)=\Omega(n^{2/d^{2}})$
distinct monochromatic solutions. This proves the theorem. ∎

###  3.3. Proof of the key lemma, Lemma 3.4

As $k$ is an isolated positive switch, every pair $\\{a,b\\}\subseteq[p(k)]$
with $b=a+m_{s}(k)$ for some $s\in[k_{0}-k]$ and $\phi(a)>\phi(b)$ forms a bad
pair. We will inductively construct pairwise disjoint bad sets. For each
$i\in[\eta n-1]$, let

$\displaystyle S_{i}$ $\displaystyle:=[\min(P_{i+1}),\min(P_{i})-1],$
$\displaystyle T_{i}$ $\displaystyle:=[\max(N_{i})+1,\max(N_{i+1})]\text{ and
}$ $\displaystyle R$ $\displaystyle:=[\min(P_{1}),\max(N_{1})].$

These sets provide a partition of the intervals $[\min(P_{\eta
k}),\max(N_{\eta k})]$.

Assume that for some $i_{*}\in\\{0,1,\dots,\eta k\\}$, we have a collection
$\mathcal{B}_{i_{*}}$ of pairwise disjoint bad pairs with
$B_{i_{*}}:=\bigcup_{\\{a,b\\}\in\mathcal{B}_{i_{*}}}\\{a,b\\}$ satisfying the
following.

  1. (Ind1)

${}_{i_{*}}$ $\displaystyle B_{i_{*}}\subseteq
R\cup\bigcup_{i\in[i_{*}]}(S_{i}\cup
T_{i})\enspace\text{and}\enspace|B_{i_{*}}|=\frac{\eta^{2}k}{\log{k}}\cdot\max\\{i_{*}-\eta
k/2,0\\}.$

  2. (Ind2)

${}_{i_{*}}$ For each $j\in[i]$, we have
$\displaystyle\Big{|}B_{i_{*}}\cap\bigcup_{i={i_{*}}-j+1}^{i_{*}-1}(S_{i}\cup
T_{i})\Big{|}\leq\frac{(j-1)\eta^{2}k}{\log{k}}.$

Note that the empty collection $\mathcal{B}_{i}=\emptyset$ satisfies both
(Ind1)${}_{i_{*}}$ and (Ind2)${}_{i_{*}}$ for $i_{*}\leq\eta k/2$. We assume
that we have a collection $\mathcal{B}_{i_{*}}$ satisfying (Ind1)${}_{i_{*}}$
and (Ind2)${}_{i_{*}}$ with $\eta k/2\leq i_{*}\leq\eta k$ and we will show
that we can construct $\mathcal{B}_{i_{*}+1}$ satisfying (Ind1)${}_{i_{*}+1}$
and (Ind2)${}_{i_{*}+1}$ from the given $\mathcal{B}_{i_{*}}$. This shows that
we can inductively build the collections
$\mathcal{B}_{1},\dots,\mathcal{B}_{\eta k}$ and the final set
$\mathcal{B}_{\eta k}$ will be our desired collection of pairwise disjoint bad
pairs.

As explained before, we plan to find a sequence
$\mathbf{u}(x)=u_{0},u_{1},\dots,u_{m}$ of copies of $m_{s}(k)$s for some
$x\in P_{i_{*}+1}\cap\Phi^{+}$ where $x$ and $x+\sum_{i\in[m]}u_{i}\in
N_{i_{*}+1}\cap\Phi^{-}$. This will yield a bad pair. In order to make sure
that this bad pair is disjoint from the ones in $\mathcal{B}_{i_{*}}$, we will
carefully choose this sequence. First, we need to decide how many $m_{s}(k)$
we have to put in $\mathbf{u}$ to ensure $x+\sum_{i\in[m]}u_{i}\in
N_{i_{*}+1}$.

Let $T:=\min(N_{i_{*}+1})-\min(P_{i_{*}+1})$, then $T$ is our target value for
$\sum_{i\in[m]}u_{i}$. Note that $T$ is a large number with $Q/(2\ell)\leq
T\leq Q$ from (PN1) and (PN3). Furthermore, from (PN1), we have

$\displaystyle\min(P_{i_{*}+1})+\frac{1}{2}|P_{i_{*}+1}|+\frac{1}{2}T=\frac{1}{2}Q.$
(3.15)

Let

$I:=\\{t2^{j}:t\in[d-1],1\leq j\leq q+\frac{1}{2}\log{k}\\}\text{ and
}M:=\sum_{i\in I}\ell~{}m_{i}(k).$

Any number $i\in I$ satisfies $i\leq 2^{2q}k^{1/2}$ and (2.2) implies that
$\frac{1}{2}ia_{d}dk^{d-1}\leq m_{i}(k)\leq iqk^{d-1}$. Hence we have

$\displaystyle\ell k^{d-1/2}<M<\ell^{2}k^{d-1/2}\leq\eta Q.$ (3.16)

Let $t$ be the maximum number such that

$t(m_{1}(k)+m_{2}(k))\leq T-M\leq T-\eta Q.$

As $m_{1}(k)+m_{2}(k)<\eta Q$, the maximality of $t$ implies

$\displaystyle t(m_{1}(k)+m_{2}(k))=T\pm\eta Q.$ (3.17)

Furthermore, as $Q/(2\ell)\leq T\leq p(k)\leq km_{1}(k)$ and $Q>p(k)/\ell$,
this implies

$\displaystyle k/\ell^{3}\leq t\leq k.$ (3.18)

By the maximality of $t$, we have

$T-M-t\sum_{s\in[2]}m_{s}(k)\leq\sum_{s\in[2]}m_{s}(k)\leq qk^{d-1},$

so Proposition 2.2 implies that there exists a vector
$\mathbf{v}\in[-\ell,\ell]^{k}$ satisfying
$\mathbf{m}^{k}\cdot\mathbf{v}=T-M-t\sum_{s\in[2]}m_{s}(k)\pm\ell$ with
$\mathbf{v}_{i}=0$ for all $i\notin I$. This yields the following non-negative
integral combination of $m_{s}(k)$ as desired.

$\displaystyle\mathbf{m}^{k}\cdot(\mathbf{v}+\ell\mathbf{1}_{I})+t\sum_{s\in[2]}m_{s}(k)=T\pm\ell.$
(3.19)

We know that $\mathbf{v}+\ell\mathbf{1}_{I}\in[2\ell]^{k}$. We fix an
arbitrary sequence $w_{1},\dots,w_{t^{\prime}}$ such that, for each $s\in I$,
$m_{s}(k)$ occurs exactly $\mathbf{v}_{s}+\ell$ times in the sequence and no
other terms appear in the sequence. As the $i$-th coordinate of
$\mathbf{v}+\ell\mathbf{1}_{I}$ is zero for all $i\notin I$, the definition of
$I$ yields

$\displaystyle t^{\prime}=\|\mathbf{v}+\ell\mathbf{1}_{I}\|_{1}\leq
2\ell|I|\leq 3d\ell\log{k}.$ (3.20)

For each $s\in[t^{\prime}]$, let

$w^{\prime}_{s}=\sum_{i\in[s]}w_{i}\enspace\text{and}\enspace
W^{\prime}=\\{w^{\prime}_{s}:s\in[0,t^{\prime}]\\}.$

In particular, $W^{\prime}$ contains zero as $w^{\prime}_{0}$ is zero. As
$m_{s}(k)\leq\ell k^{d-1/2}$ for all $s\in I$, (3.20) implies

$\displaystyle w^{\prime}_{t^{\prime}}\leq\ell^{3}k^{d-1/2}\log k\leq\eta Q.$
(3.21)

For each $x\in P_{i_{*}+1}$, let

$y(x):=x+\mathbf{m}^{k}\cdot(\mathbf{v}+\ell\mathbf{1}_{I})+t\sum_{s\in[2]}m_{s}(k).$

As (3.19) ensures that this value is $x+T\pm\ell$, we have $y(x)\in
N_{i_{*}+1}$ for all $x\in P_{i_{*}+1}$ with $\min(P_{i_{*}+1})+\ell\leq
x\leq\max(P_{i_{*}+1})-\ell$. Let

$P:=\\{x\in P_{i_{*}+1}:y(x)\in N_{i_{*}+1},\phi(x)=+1\text{ and
}\phi(y(x))=-1\\}.$

Then (PN4) and (3.19) implies

$|P|\geq\frac{1}{4}|P_{i_{*}+1}|-2\ell\geq\frac{1}{5}\varepsilon k.$

For each $x\in P$, we aim to construct a sequence
$\mathbf{r}(x)=r_{1},\dots,r_{2t}$ which contains exactly $t$ copies of
$m_{1}(k)$ and exactly $t$ copies of $m_{2}(k)$. After obtaining this, we will
insert the terms $w_{1},\dots,w_{t^{\prime}}$ in the middle of this sequence
as follows to obtain our desired sequence $\mathbf{u}(x)$

$\mathbf{u}(x):=(u_{1},\dots,u_{2t+t^{\prime}}):=(r_{1},r_{2},\dots,r_{t},w_{1},\dots,w_{t^{\prime}},r_{t+1},\dots
r_{2t}).$

With this choice, the sequence

$x+\mathbf{u}(x):=(x,x+u_{1},x+u_{1}+u_{2},\dots,x+\sum_{i\in[2t+t^{\prime}]}u_{i})$

will be our final desired sequence which starts at $x\in\Phi^{+}$ and ends at
$y(x)\in\Phi^{-}$ and all consecutive terms differ by $m_{s}(k)$ for some
$s\in I\cup\\{1,2\\}\subseteq[k_{0}-k]$.

We will make sure that the sequence $\mathbf{r}(x)$ chosen for this $x$ is
constructed so that the above sequence $x+\mathbf{u}(x)$ does not intersect
with $B_{i_{*}}$ for all $x\in P^{\prime}$ where $P^{\prime}$ is a not so
small subset of $P$.

We call a sequence $\mathbf{r}=(r_{1},\dots,r_{2t})$ _admissible_ if the
number of occurrences of $m_{1}(k)$ and $m_{2}(k)$ in the first $j$ terms
differ by at most $\eta^{2}t$ for all $j\in[2t]$. As admissible sequences are
nice to work with, we will choose our sequence $\mathbf{r}(x)$ among the
admissible sequences.

If a sequence $r_{1},\dots,r_{2t}$ is admissible, then (3.17) and (3.15) imply
the following.

$\displaystyle\begin{split}\sum_{i\in[t]}r_{i}&=(\frac{1}{2}\pm\eta^{2})t\sum_{s\in[2]}m_{s}(k)=\frac{1}{2}(T\pm
2\eta Q)\pm\eta Q=\frac{1}{2}Q-\min(P_{i_{*}+1})\pm 4\eta Q\\\
&=(\frac{1}{2}\pm 4\eta)Q-\min(P_{i_{*}+1}).\end{split}$ (3.22)

Our desired sequence $\mathbf{u}(x)$ is different from $\mathbf{r}(x)$ as we
insert the terms $w_{1},\dots,w_{t^{\prime}}$ in the middle of the sequence.
As the sequence $\mathbf{r}(x)$ consists of only $m_{1}(k)$ and $m_{2}(k)$, it
is simpler. So we want to focus on the sequence $\mathbf{r}(x)$. We define the
following set $B$ so that we only have to focus on avoiding $B$ in the
sequence

$x+\mathbf{r}(x):=(x,x+r_{1},x+r_{1}+r_{2},\dots,x+\sum_{i\in[2t]}r_{i}),$

instead of worrying about whether the sequence $x+\mathbf{u}(x)$ intersects
$B_{i_{*}}$. Let

$\displaystyle B$ $\displaystyle:=B_{\rm down}\cup B_{\rm mid}\cup B_{\rm
up}\enspace\text{ with }$ $\displaystyle B_{\rm down}$ $\displaystyle:=\\{b\in
B_{i_{*}}:b<(\frac{1}{2}-\varepsilon)Q\\},$ $\displaystyle B_{\rm mid}$
$\displaystyle:=\\{b\in B_{i_{*}}:(\frac{1}{2}-\varepsilon)Q\leq
b\leq(\frac{1}{2}+\varepsilon)Q\\}-W^{\prime},$ $\displaystyle B_{\rm up}$
$\displaystyle:=\\{b\in
B_{i_{*}}:b>(\frac{1}{2}+\varepsilon)Q\\}-w^{\prime}_{t^{\prime}}.$

In other words, $B_{\rm down}$ consists of all the numbers in $B_{i_{*}}$
which are smaller than $(\frac{1}{2}-\varepsilon)Q$, and $B_{\rm mid}$
consists of all numbers of the form $b-w^{\prime}_{s}$ for some $b\in
B_{i_{*}}$ with $b=(\frac{1}{2}\pm\varepsilon)Q$ and $s\in[0,t^{\prime}]$, and
$B_{\rm up}$ consists of all numbers of the form $b-w^{\prime}_{t^{\prime}}$
for some $b\in B_{i_{*}}$ with $b>(\frac{1}{2}+\varepsilon)Q$.

The following claim shows that this set is indeed the set that we need to
avoid intersecting with $x+\mathbf{r}(x)$.

######  Claim 3.7.

For a number $x\in P$ and an admissible sequence
$\mathbf{r}(x)=r_{1},\dots,r_{2t}$, if $x+\sum_{i\in[s]}r_{i}\notin B$ for all
$s\in[2t]$, then $x+\sum_{i\in[s]}u_{i}\notin B_{i_{*}}$ for any
$s\in[2t+t^{\prime}]$.

###### Proof.

Suppose not. Then there exists $b\in B_{i_{*}}$ such that
$b=x+\sum_{i\in[s]}u_{i}$ for some $s\in[2t+t^{\prime}]$.

If $b<(\frac{1}{2}-\varepsilon)Q$, then $b\in B_{i_{*}}$ implies that $b\in
B_{\rm down}$. Using (3.22) yields

$b<(\frac{1}{2}-\varepsilon)Q<\min(P_{i_{*}+1})+\frac{1}{2}Q-\min(P_{i_{*}+1})-5\eta
Q\leq x+\sum_{i\in[t]}r_{i}.$

Hence, $s$ must be at most $t$ in this case and this yields

$x+\sum_{i\in[s]}u_{i}=b\in B_{\rm down}\subseteq B,$

which contradicts the assumption of the claim.

If $b>(\frac{1}{2}+\varepsilon)Q$, then (3.21) and (3.22) with $c=t^{\prime}$
ensures that

$b\geq(\frac{1}{2}+\varepsilon)Q>\min(P_{i_{*}+1})+k+\frac{1}{2}Q+5\eta
Q-\min(P_{i_{*}+1})\geq x+\sum_{i\in[t]}r_{i}+w^{\prime}_{t^{\prime}}.$

Hence we have $s\geq t+t^{\prime}$. As $b\in B_{i_{*}}$ and
$b>(\frac{1}{2}+\varepsilon)Q$, we have $b-w^{\prime}_{t^{\prime}}\in B_{\rm
up}$. As $s\geq t+t^{\prime}$, we have

$x+\sum_{i\in[s-t]}r_{i}=b-w^{\prime}_{t^{\prime}}\in B_{\rm up}\subseteq B,$

which contradicts the assumption of the claim.

Finally, consider the case of $b=(\frac{1}{2}\pm\varepsilon)Q$. If $s\leq t$,
then we have $x+\sum_{i\in[s]}r_{i}=b\in(B_{i_{*}}\cap U)\subseteq B_{\rm
mid}$ as $0\in W^{\prime}$. If $s\geq t+t^{\prime}$, then we have
$b-w^{\prime}_{t^{\prime}}\in B_{i_{*}}-w^{\prime}_{t^{\prime}}\subseteq
B_{\rm mid}$ as $w^{\prime}_{t^{\prime}}\in W^{\prime}$. Thus
$x+\sum_{i\in[s-t^{\prime}]}r_{i}=b-w^{\prime}_{t^{\prime}}\in B_{\rm
mid}\subseteq B$, a contradiction to the assumption of the claim.

If $t<s\leq t+t^{\prime}$, then $w^{\prime}_{s-t}=\sum_{i\in[s-t]}u_{t+i}\in
W^{\prime}$, thus

$x+\sum_{i\in[t]}r_{i}=b-w^{\prime}_{s-t}\in B_{\rm mid}\subseteq B,$

which contradicts the assumption of the claim. This proves the claim. ∎

This claim ensures that we only have to worry about whether the sequence
$x+\mathbf{r}(x)$ hits $B$ or not. For each $x\in P$, we consider the
following reduced grid digraph $G_{x}$ isomorphic to $G(t;\eta^{2}t)$ with the
vertex set $V_{x}$ where

$\displaystyle V_{x}$ $\displaystyle:=\\{(x,s_{1},s_{2})\in
P\times[t]^{2}:|s_{1}-s_{2}|\leq\eta^{2}t\\}\text{ and }V=\bigcup_{x\in
P^{\prime}}V_{x}.$

Consider a map $\alpha:V\rightarrow[Q]$ such that
$\alpha(x,s_{1},s_{2})=x+s_{1}m_{1}(k)+s_{2}m_{2}(k)$. This map $\alpha$ sends
each vertex to a number of the form $x+s_{1}m_{1}(k)+s_{2}m_{2}(k)$, thus a
directed path in the grid graph $G_{x}$ naturally corresponds to a sequence of
the form $x+\mathbf{r}(x)$. We claim that $\alpha$ is an injective function.

######  Claim 3.8.

$\alpha$ is an injective function.

###### Proof.

Suppose not, then there exist
$(x,s_{1},s_{2})\neq(x^{\prime},s^{\prime}_{1},s^{\prime}_{2})\in V$ and
$b\in[Q]$ with

$b=x+s_{1}m_{1}(k)+s_{2}m_{2}(k)=x^{\prime}+s^{\prime}_{1}m_{1}(k)+s^{\prime}_{2}m_{2}(k).$

Assume $x\geq x^{\prime}$. By the definition of $V$, we have
$s_{2}=s_{1}\pm\eta^{2}t$, so

$(s_{1}-\eta^{2}t)(m_{1}(k)+m_{2}(k))\leq b-x\leq
b-x^{\prime}\leq(s^{\prime}_{1}+\eta^{2}t)(m_{1}(k)+m_{2}(k)).$

This implies that $|s_{1}-s^{\prime}_{1}|\leq 2\eta^{2}t$ and similarly we
obtain $|s_{2}-s^{\prime}_{2}|\leq 2\eta^{2}t$. As

$x-x^{\prime}=(s^{\prime}_{1}-s_{1})m_{1}(k)+(s^{\prime}_{2}-s_{2})m_{2}(k),$

Proposition 2.6 with $d=3$ and $t=2$ implies
$s^{\prime}_{1}-s_{1}=s^{\prime}_{2}-s_{2}=0$ or $|x-x^{\prime}|>k/2$. As both
$x$ and $x^{\prime}$ are in $P$, (PN1) implies $|x-x^{\prime}|<k/2$, thus we
must have $(s_{1},s_{2})=(s^{\prime}_{1},s^{\prime}_{2})$. However, in such a
case, we obtain $x-x^{\prime}=0$, thus
$(x,s_{1},s_{2})=(x^{\prime},s^{\prime}_{1},s^{\prime}_{2})$. This proves that
$\alpha$ is an injective function. ∎

As $\alpha$ is an injective function, the sets $\alpha(V_{x})$ are pairwise
disjoint over the choices of $x\in P$. Note that $\alpha(V_{x})$ is the set of
all numbers in $[Q]$ which may belong to the sequence $x+\mathbf{r}(x)$ for an
admissible sequence $\mathbf{r}(x)$.

For each $x\in P$, let $L_{x}(a,b)$ be the set of vertices at level $j$ for
some $a\leq j\leq b$ in the digraph $G_{x}$. Now, based on our choice of $B$,
we can prove the following bounds on how it is distributed over the level sets
in the graphs $G_{x}$.

######  Claim 3.9.

We have $|B|\leq\ell^{2}\eta^{3}k^{2}$. Moreover, for each
$i\in[\eta^{2}t/\ell]$, $\bigcup_{x\in P}\alpha(L_{x}(0,i\ell))$ and
$\bigcup_{x\in P}\alpha(L_{x}(2t-i\ell,2t))$ contains at most
$\frac{2(i-1)\eta^{2}k}{\log k}$ numbers in $B$.

###### Proof.

By (Ind1)${}_{i_{*}}$ and the definition of $B$, (3.20) implies

$|B|\leq(|W^{\prime}|+1)|B_{i_{*}}|\leq(1+3d\ell\log k)\frac{\eta^{3}k}{2\log
k}\leq\ell^{2}\eta^{3}k^{2}.$

For all $i\in[\eta^{2}t/\ell]$, $x\in P$ and $v\in L_{x}(0,i\ell)$, we have

$\alpha(v)\leq x+2i\ell m_{2}(k)\leq\max(P_{i_{*}+1})+5i\ell m_{1}(k),$

hence $i_{*}\geq\eta k/2>\eta^{2}k$ and (PN2) ensure that $\alpha(v)$ belongs
to $\bigcup_{j=i_{*}-i+1}^{i_{*}-1}S_{j}$ and all such numbers are smaller
than $(\frac{1}{2}-\varepsilon)Q$ by (PN3). Thus we conclude that

$\bigcup_{x\in
P}\alpha(L_{x}(0,i\ell))\subseteq\bigcup_{j=i_{*}-i+1}^{i_{*}-1}S_{j}.$

As $B\cap\bigcup_{j=i_{*}-i+1}^{i_{*}-1}S_{j}$ belongs to $B_{\rm
down}\subseteq B_{i_{*}}$ and $\alpha$ is injective, (Ind2)${}_{i_{*}}$
implies that the set $\alpha(\bigcup_{x\in P}L_{x}(0,i\ell))$ contains at most
$\frac{(i-1)\eta^{2}k}{\log k}$ numbers in $B$.

Similarly, we can show that for all $i\in[\eta^{2}t/\ell]$, $x\in P$ and $v\in
L_{x}(2t-i\ell,2t)$, we have

$\alpha(v)\geq y(x)-2\ell im_{2}(k)\geq\min(N_{i_{*}+1})-5\ell im_{1}(k).$

By the definition of $\mathbf{u}(x)$ and the fact that $y(x)\in N_{i_{*}+1}$,
(PN2) implies that $\bigcup_{x\in P}\alpha(L_{x}(2t-i\ell,2t))$ belong to
$\left(\bigcup_{j=i_{*}-i+1}^{i_{*}-1}T_{j}\right)-w^{\prime}_{t^{\prime}}$
and all numbers in $\left(\bigcup_{j=i_{*}-i+1}^{i_{*}-1}T_{j}\right)$ are
larger than $(\frac{1}{2}+\varepsilon)Q$. So, $\alpha(v)$ is never in $B_{\rm
down}$ or $B_{\rm mid}$. Applying (Ind2)${}_{i_{*}}$ again yields that
$\bigcup_{x\in P}\alpha(L_{x}(2t-i\ell,2t))$ contains at most
$\frac{(i-1)\eta^{2}k}{\log k}$ numbers of $B_{\rm up}$. This proves the
lemma. ∎

Now, we consider the following pairwise disjoint sets over the choices of
$x\in P$.

$B^{x}=B\cap\alpha(V_{x}).$

Let $P^{\prime}$ be the set of all $x\in P$ satisfying the following two
properties.

  1. (E1)

$|B^{x}|\leq\frac{\eta^{2}t}{10}$.

  2. (E2)

For each $i\in[\eta^{2}t/\ell]$, each set $\alpha(L_{x}(0,i\ell))$ and
$\alpha(L_{x}(2t-i\ell,2t))$ contains at most $(i-1)$ numbers in $B^{x}$.

We claim the following.

######  Claim 3.10.

$|P^{\prime}|\geq\varepsilon k/6$.

###### Proof.

Let $P^{(0)}$ be the set of $x\in P$ which does not satisfy (E1). For each
$i\in[\eta^{2}t/\ell]$, we let $P^{(i)}$ be the set of all $x\in
P\setminus\bigcup_{j\in[0,i-1]}P^{(j)}$ that does not satisfy (E2) for the
index $i$.

First, by Claim 3.9, we have $|B|\leq\ell^{2}\eta^{3}k^{2}$. By the definition
of $P^{(0)}$, the set $\bigcup_{x\in P^{(0)}}\alpha(V_{X})$ contains at least
$\frac{\eta^{2}t}{10}|P^{(0)}|$ numbers in $B$. Hence we have

$\frac{\eta^{2}t}{10}|P^{(0)}|\leq\ell^{2}\eta^{3}k^{2},$

implying $|P^{(0)}|\leq\varepsilon^{2}k$ from (3.18).

Now, consider $i\in[\eta^{2}t/\ell]$. For each $x\in\bigcup_{j\in[i]}P^{(j)}$
and $j\in[i]$ the definition of $P^{(j)}$ ensures that

$\bigcup_{x\in P^{(j)}}\alpha(L_{x}(0,i\ell))\supseteq\bigcup_{x\in
P^{(j)}}\alpha(L_{x}(0,j\ell))$

contains at least $j|P^{(j)}|$ numbers in $B$. Because $P^{(1)},\dots,P^{(i)}$
are pairwise disjoint by definition and $\alpha$ is injective,
$\sum_{j\in[i]}j|P^{(j)}|$ is at most the number of elements of $B$ inside
$\bigcup_{j\in[i]}\bigcup_{x\in P^{(j)}}\alpha(L_{x}(0,i\ell))$, which is at
most $\frac{2(i-1)\eta^{2}k}{\log k}$ by Claim 3.9. Hence we obtain the
following for all $i\in[\eta^{2}t/\ell]$,

$\sum_{j\in[i]}j|P^{(j)}|\leq\frac{2(i-1)\eta^{2}k}{\log k}.$

By Lemma 2.10, this implies

$\sum_{i\in[\eta^{2}t/\ell]}|P^{(j)}|\leq\frac{4\eta^{2}k}{\log
k}\cdot\log(\eta^{2}t/\ell)\leq 4\eta^{2}k.$

Therefore, the set

$P^{\prime}=P\setminus\bigcup_{i\in[0,\eta^{2}t]}P^{(i)}$

has size at least $\varepsilon k/5-\varepsilon^{2}k-2\eta^{2}k\geq\varepsilon
k/6$. ∎

For each $x\in P^{\prime}$, consider the reduced grid digraph $G_{x}$ with the
set $Z_{x}:=\alpha^{-1}(B^{x})$. By (E1)–(E2), for $x\in P^{\prime}$, the
graph $G_{x}=G(t;\eta^{2}t)$ and the set $Z_{x}$ satisfy the assumption of
Lemma 2.8 with $\eta^{2},t$ playing the roles of $\eta^{2},n$, respectively.
Thus there exists a path $P_{x}$ in $G_{x}-Z_{x}$ from $(x,0,0)$ to $(x,t,t)$.
As each vertex $(x,s_{1},s_{2})$ in $G_{x}$ corresponds to a number
$\alpha(x,s_{1},s_{2})=x+s_{1}m_{1}(k)+s_{2}m_{2}(k)$, such a path $P_{x}$
yields a sequence $\alpha(P_{x})$ of numbers starting from $x$ and ending at
$x+t(m_{1}(k)+m_{2}(k))$. For such a path $P_{x}=(p_{1},\dots,p_{2t})$, let
$\mathbf{r}(x)$ be the sequence

$\mathbf{r}(x)=(\alpha(p_{1})-x,\alpha(p_{2})-\alpha(p_{1}),\dots,\alpha(p_{2t})-\alpha(p_{2t-1})).$

Then this sequence naturally yields a new sequence

$\mathbf{u}(x)=(r_{1},\dots,r_{t},w_{1},\dots,w_{t^{\prime}},r_{t+1},\dots,r_{2t}).$

As $P_{x}$ avoids the vertices in $Z_{x}=\alpha^{-1}(B^{x})$, the set of
numbers in the sequence

$x+\mathbf{r}(x)=(x,x+r_{1},\dots,x+\sum_{i\in[2t]}r_{i})$

does not intersect $B$. By Claim 3.7, this implies that the sequence

$x+\mathbf{u}(x)=(x,x+u_{1},\dots,x+\sum_{i\in[2t+t^{\prime}]}u_{i})$

from $x$ to $y(x)$ does not intersect $B_{i_{*}}$. As this sequence starts
with $x\in\Phi^{+}$ and ends at $y(x)\in\Phi^{-}$ and the differences between
two consecutive terms are all $m_{s}(k)$ for some $s\in
I\cup\\{1,2\\}\subseteq[k_{0}-k]$, it contains two consecutive terms which
form a bad pair. As this new bad pair belongs to the sequence
$x+\mathbf{u}(x)$, it is disjoint from $B_{i_{*}}$. Same logic applies for all
$x\in P^{\prime}$, and we obtain $\varepsilon k/6$ new bad pairs. As $\alpha$
is injective and each bad pair from the sequence $\mathbf{u}(x)$ belongs to
$\alpha(V_{x})$, those bad pairs obtained from different choices of $x\in
P^{\prime}$ are pairwise disjoint.

Among them we choose exactly $\eta^{2}k/\log{k}\leq\varepsilon
k/6\leq|P^{\prime}|$ pairwise disjoint bad pairs and add them to
$\mathcal{B}_{i_{*}}$ to obtain $\mathcal{B}_{i_{*}+1}$. Then, by
construction, $\mathcal{B}_{i_{*}+1}$ satisfies (Ind1)${}_{i_{*}+1}$.
Moreover, (Ind2)${}_{i_{*}}$ together with this construction of new bad pairs,

$|\bigcup_{i_{*}-j+1}^{i=i_{*}}(S_{i}\cup T_{i})\cap
B_{i_{*}+1}|\leq|\bigcup_{i_{*}-j+1}^{i=i_{*}-1}(S_{i}\cup T_{i})\cap
B_{i_{*}}|+\frac{\eta^{2}k}{\log{k}}.$

This implies (Ind2)${}_{i_{*}+1}$. Hence, we can keep repeating this until
$i_{*}=\eta k/2$, then we obtain at least $\frac{\eta^{3}k^{2}}{2\log{k}}$
pairwise disjoint bad pairs, and Lemma 2.1 implies that there are
$\frac{\eta^{3}k^{2}}{2\log{k}}$ distinct monochromatic solutions. This proves
Lemma 3.4.

##  4\.  Proof of Theorem 1.2

Again, for a given large number $k$, we write $k_{0}$ to denote the largest
number with $p(k_{0})<2p(k)-4m_{1}(k)$. Let $m^{\prime}(k)$ be the smallest
integer satisfying $p(m^{\prime}(k))\geq 4m_{1}(k)$, then we have
$m^{\prime}(k)=\Theta(k^{(d-1)/d})$ for sufficiently large $k$. We first
collect the following lemma.

######  Lemma 4.1.

Let $p(z)\in\mathbb{Z}[z]$ be a non-odd polynomial of degree $d\geq 2$ with a
positive leading coefficient. Let $k$ be a sufficiently large number. A
$2$-coloring $\phi:[n,p(k)-n]\rightarrow\\{-1,1\\}$ is given where $k$ is a
positive switch in this coloring. Assume that it has no monochromatic
solutions. Let $n^{\prime}=\max\\{n,m^{\prime}(k)\\}$ and let

$I_{-1}=[k+1,k_{0}]\text{ and }I_{1}=[n^{\prime},k].$

Then for each $i\in\\{-1,1\\}$, all numbers in the interval $I_{i}$ has color
$i$.

###### Proof.

As $k$ is a positive switch, we have $\phi(k)=+1$ and $\phi(k+1)=-1$. Let
$m_{1}:=m_{1}(k)$ and $m^{\prime}=m^{\prime}(k)$. As $p(z)$ is a non-odd
polynomial, we know that $m_{1}$ is an odd number. By the lack of
monochromatic solutions, Lemma 2.1 implies that

for every $a\in[n,p(k)-n-m_{1}]$, $\phi(a)\leq\phi(a+m_{1})$. (4.1)

We want to apply Proposition 2.7 with $m_{1},n^{\prime},Q$ playing the roles
of $m,n,p(k)$, respectively. For this, condition (A1) is satisfied by (4.1)
and as $\phi(k)=+1$ and $\phi(k+1)=-1$ and $p(k+1)=p(k)+m_{1}$, the lack of
monochromatic solutions implies (A2) and (A3). As $k$ is large, we have
$m^{\prime}<\frac{1}{10}m_{1}$, the application of Proposition 2.7 deduces
that any number in $[p(k)+m_{1}+1,2p(k)-4m_{1}]$ can be written as a sum of
two numbers of color $+1$. As $p(k+1)=p(k)+m_{1}$ and $p(k_{0})\leq
2p(k)-4m_{1}$, all numbers $p(x)$ with $x\in I_{-1}$ can be written as a sum
of two numbers of color $1$. Hence, the lack of monochromatic solutions
implies that all numbers in $I_{-1}$ has color $-1$.

Similarly, Proposition 2.7 deduces that any number in $[4m^{\prime},p(k)-1]$
can be written as a sum of two numbers of color $-1$. As $p(k-1)<p(k)$ and
$p(n^{\prime})\geq p(m^{\prime}(k))\geq 4m_{1}$, the number $p(y)$ can be
written as a sum of two numbers with color $-1$ for all numbers $y$ in
$I_{1}$. Hence the lack of monochromatic solutions yields that all the numbers
in $I_{1}$ are colored $+1$. Therefore, all numbers in $I_{-1}$ are colored
$-1$ and all numbers in $I_{1}$ are colored $+1$ and this proves the lemma. ∎

Now, for sufficiently large $n$, we choose numbers $q,\ell$ so that

$0<1/n\ll 1/\ell\ll 1/q\ll 1/\|p\|<1.$

We consider a coloring
$\phi:[n,p(\lceil\frac{p(n)}{2}\rceil)]\rightarrow\\{-1,1\\}$ and assume that
there are no monochromatic solutions. If the interval
$[n,\lceil\frac{p(n)}{2}\rceil]$ is monochromatic, then we obtain a
monochromatic solution
$(\lfloor\frac{p(n)}{2}\rfloor,\lceil\frac{p(n)}{2}\rceil,n)$, so we are done.

Otherwise, we choose the largest switch $k\in[n,\lceil\frac{p(n)}{2}\rceil]$.
Without loss of generality, assume that $k$ is a positive switch, i.e.
$\phi(k)=+1$ and $\phi(k+1)=-1$. As $k\leq\lceil\frac{p(n)}{2}\rceil$, we have
$p(k)\leq p(\lceil\frac{p(n)}{2}\rceil)$ and we have $p(k_{0})\leq
2p(\lceil\frac{p(n)}{2}\rceil)-4m_{1}(\lceil\frac{p(n)}{2}\rceil)$. Moreover,
Lemma 4.1 implies that $k$ is an isolated switch with all numbers in
$[k+1,k_{0}]$ colored $-1$ and all numbers in $[\max\\{n,m^{\prime}(k)\\},k]$
are colored $+1$.

Thus, by Lemma 2.1 and the assumption that there is no monochromatic solution,
the following holds.

If $b=a+m_{s}(k)$ for some $s\in[k_{0}-k]$, then $\phi(a)\leq\phi(b)$. (4.2)

Case 1. $k\geq n+4\ell$. In this case, we claim that $[k-4\ell,k]$ is
monochromatic with color $+1$. As $1/n\ll 1/\ell$ and $k\geq n$, we have
$p(k-4\ell)\geq\ell^{2}m_{1}(k)$ by (2.2). Hence, $m^{\prime}(k)\leq k-4\ell$
and Lemma 4.1 implies that all numbers in $[k-4\ell,k]$ must have color $+1$.

Let $I:=\\{t\cdot 2^{j}:t\in[q],1\leq j\leq q+\frac{1}{2}\log{k}\\}$. Let $s$
be the smallest number such that

$T:=\frac{p(k)}{2}-k+2\ell-\mathbf{m}^{k}\cdot(q^{q}\mathbf{1}_{I})-sm_{1}(k)$

is smaller than $qk^{d-1}$. Such an integer exists as $2m_{1}(k)<qk^{d-1}$.

By Proposition 2.2, there exists a vector
$\mathbf{v}+q^{q}\mathbf{1}_{I}\in[2q^{q}]^{k}$ such that
$|\mathbf{v}\cdot\mathbf{m}^{k}|=T\pm\ell$ and
$\mathbf{v}+q^{q}\mathbf{1}_{I}$ has nonzero $i$-th coordinate only when $i\in
I$. In particular, $i\in I$ implies that
$i\in[q^{q}k^{1/2}]\subseteq[k_{0}-k]$. Consider the vector
$\mathbf{x}=\mathbf{v}+q^{q}\mathbf{1}_{I}+s\mathbf{1}_{\\{1\\}}$, and for
each $i\in[k_{0}-k]$, choose $\mathbf{x}_{i}$ copies of the numbers $m_{i}(k)$
and list them in an arbitrary way. Let $w_{1},w_{2},\dots,w_{t}$ be the
obtained list of numbers, then each $w_{i}$ is $m_{i}(k)$ for some
$i\in[k_{0}-k]$ and

$Q:=\sum_{i\in[t]}w_{i}=\frac{p(k)}{2}-k+2\ell\pm\ell.$

Hence, this with (4.2) implies that all numbers in $[k-4\ell,k]+Q$ must have
color $+1$. On the other hand, by the choice of $Q$, at least $3\ell$ numbers
in $[k-4\ell,k)+Q$ lies in the interval
$[\frac{p(k)}{2}-2\ell,\frac{p(k)}{2}+2\ell]$. Hence, more than half of the
numbers in the interval $[\frac{p(k)}{2}-2\ell,\frac{p(k)}{2}+2\ell]$ has
color $+1$, and this yields a monochromatic solution of the form
$(\frac{p(k)}{2}-y,\frac{p(k)}{2}+y,k)$ with color $+1$.

Case 2.  $n\leq k<n+4\ell$. In this case, maximality of $k$ implies that
$[n+4\ell+1,\lceil p(n)/2\rceil]$ is monochromatic with color $-1$. Then we
have $k+4\ell+1<k+m_{1}(k)<\lceil p(n)/2\rceil$, hence
$\phi(k)=1>\phi(k+m_{1}(k))=-1$, thus this contradicts (4.2).

This proves Theorem 1.2.

## References

  * [1] Zs. Baja, D. Dobák, B. Kovács, P. P. Pach, D. Pigler,  Towards characterizing the 2-Ramsey equations of the form $ax+by=p(z)$, Discrete Mathematics 346 (5) (2023) 113324
  * [2] V. Bergelson and A. Leibman,  Polynomial extensions of van Der Warden’s and Szemerédi’s theorems, J. Am. Math. Soc. 9 (3) (1996) 725–753.
  * [3] M. Bowen and M. Sabok,  Monochromatic products and sums in the rationals, arXiv:2210.12290.
  * [4] P. Cameron, J. Cilleruelo and O. Serra,  On monochromatic solutions of equations in groups, Revista Matemática Iberoamericana 23.1 (2007) 385–395.
  * [5] M. Campos, S. Griffiths, R. Morris and J. Sahasrabudhe,  An exponential improvement for diagonal Ramsey, arXiv:2303.09521.
  * [6] P. Csikvári, K. Gyarmati and A.Sárközy,  Density and Ramsey type results on algebraic equations with restricted solution sets, Combinatorica 32 (2012) 425–449.
  * [7] B. Datskovsky,  On the number of monochromatic Schur triples, Advances in Applied Math, 31 (2003), 193–198.
  * [8] P. Frankl, R. L. Graham and V. Rödl,  Quantitative Theorems for Regular Systems of Equations, J. Comb. Theor. Ser. A, 47, (1988) 246–261.
  * [9] B. Green and S. Lindqvist,  Monochromatic solutions to $x+y=z^{2}$ Can. J. Math. 71 (3) (2019) 579–605.
  * [10] M. J.H. Heule, O. Kullmann and V. W. Marek,  Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer. In Theory and Applications of Satisfiability Testing – SAT (2016) pp. 228–245.
  * [11] H. Liu, P. P. Pach, Cs. Sándor,  Polynomial Schur’s theorem, Combinatorica 42 (2) (2022) 1357–1384.
  * [12] J. Moreira,  Monochromatic sums and products in $\mathbb{N}$, Ann. of Math. 185 (2017), 1069–1090.
  * [13] P. P. Pach,  Monochromatic solutions to $x+y=z^{2}$ in the interval $[N,cN^{4}]$. Bull. Lond. Math. Soc. 50 (6) (2018) 1113–1116.
  * [14] R. Rado,  Studien zur Kombinatorik, Math. Z. 36 (1933) 424–70
  * [15] F. P. Ramsey,  On a problem of formal logic, Proc. Lond. Math. Soc. 30 (1930) 264–286.
  * [16] A. Robertson and D. Zeilberger,  A 2-coloring of $[1,N]$ can have $(1/22)N^{2}+O(N)$ monochromatic Schur triples, but not less!, Elect. J. Combinatorics, 5 (1998), R19.
  * [17] S. Prendiville,  Counting Monochromatic Solutions to Diagonal Diophantine Equations, Discret. Anal. 2021:14.
  * [18] T. Schoen,  The Number of Monochromatic Schur Triples, Europ. J. Combinatorics (1999) 20, 855–-866.
  * [19] I. Schur,  Über die Kongruenz $x^{m}+y^{m}\equiv z^{m}$ (mod $p$), Jahresber. Dtsch. Matah.-Ver. 14 (1916) 114–117.
  * [20] O. Serra and L. Vena,  On the number of monochromatic solutions of integer linear systems on Abelian groups European J. Combin., 35 (2014) pp. 459–473.
  * [21] J. Spencer,  Ramsey’s theorem - a new lower bound, J. Comb. Theor. Ser. A 18 (1975) 108–115.
  * [22] B.L. van der Werden,  Beweis einer baudeutschen Vermutung, Nieuw. Arch. Wink. 15 (1927) 212–216.