# Discrepancy of arithmetic progressions in grids

Jacob Fox and Max Wenqiang Xu and Yunkun Zhou  Department of Mathematics,
Stanford University, Stanford, CA, USA
<EMAIL_ADDRESS>
###### Abstract.

We prove that the the discrepancy of arithmetic progressions in the
$d$-dimensional grid $\\{1,\dots,N\\}^{d}$ is within a constant factor
depending only on $d$ of $N^{\frac{d}{2d+2}}$. This extends the case $d=1$,
which is a celebrated result of Roth and of Matoušek and Spencer, and removes
the polylogarithmic factor from the previous upper bound of Valkó from about
two decades ago. We further prove similarly tight bounds for grids of
differing side lengths in many cases.

Fox is supported by a Packard Fellowship and by NSF award DMS-1855635.
Xu is supported by the Cuthbert C. Hurd Graduate Fellowship in the
Mathematical Sciences, Stanford.
Zhou is supported by NSF GRFP Grant DGE-1656518.

##  1\. Introduction

Given a finite set $\Omega$, a coloring of $\Omega$ is a map
$\chi:\Omega\to\\{1,-1\\}$, and $\chi(A)=\sum_{x\in A}\chi(x).$ For a family
$\mathcal{A}$ of subsets of $\Omega$, the discrepancy of $\mathcal{A}$ is
defined to be

$\operatorname{disc}(\mathcal{A}):=\min_{\chi}\max_{A\in\mathcal{A}}|\chi(A)|,$

where the minimum is over all colorings of $\Omega$. Let $\mathcal{A}_{1}$ be
the family of arithmetic progressions contained in $[N]:=\\{1,\ldots,N\\}$.
Roth [9] showed using Fourier analysis that there is an absolute constant
$c>0$ such that

$\operatorname{disc}(\mathcal{A}_{1})\geq cN^{\frac{1}{4}}.$

In the other direction, Beck [2] proved that

$\operatorname{disc}(\mathcal{A}_{1})\leq CN^{\frac{1}{4}}(\log
N)^{\frac{5}{2}}$

for some absolute constant $C$, thereby showing that Roth’s lower bound is
sharp up to a polylogarithmic factor. Finally, Matoušek and Spencer [8]
removed the polylogarithmic factor and resolved this problem of determining
the discrepancy up to a constant factor.

It is natural to study the generalization of this problem to higher
dimensions. An arithmetic progression in $d$ dimensions is a set of the form

$\operatorname{AP}_{d}(\mathbf{a},\mathbf{b},l):=\\{\mathbf{a}+i\mathbf{b}:i=0,1,\dots,l-1\\}$

where $\mathbf{a},\mathbf{b}\in\mathbb{Z}^{d}$ with
$\mathbf{b}\not=\mathbf{0}$, and $l\in\mathbb{N}$. Here $\mathbf{b}$ is the
common difference of the arithmetic progression. Let $\mathcal{A}_{d}$ be the
set of arithmetic progressions in $d$ dimensions that are subsets of
$[N]^{d}$. The quantity we are interested in is

$\operatorname{disc}(\mathcal{A}_{d}):=\min_{\chi:[N]^{d}\to\\{1,-1\\}}\max_{A\in\mathcal{A}_{d}}|\chi(A)|,$

where $\chi(A)=\sum_{x\in A}\chi(x)$. Valkó [10] proved that there exist
constants $c=c(d),C=C(d)$ such that

$cN^{\frac{d}{2d+2}}\leq\text{disc}(\mathcal{A}_{d})\leq
CN^{\frac{d}{2d+2}}(\log N)^{\frac{5}{2}}.$

Valkó’s proof of the lower bound extends Roth’s proof, while the upper bound
adapts Beck’s proof. The problem of estimating the discrepancy of higher
dimensional arithmetic progressions is further discussed in [5]. In this
paper, we remove the polylogarithmic factor in the upper bound and thus
determine the quantity up to a constant factor dependent on $d$.

######  Theorem 1.1.

For all positive integers $N$ and $d$, we have

$\operatorname{disc}(\mathcal{A}_{d})=\Theta_{d}(N^{\frac{d}{2d+2}}).$

The general proof strategy is similar to that in the paper by Matoušek and
Spencer [8]. However, new ideas are needed to make the strategy work. In
particular, we need to overcome some difficulties arising from geometric
aspects which requires delicate analysis and tools like Minkowski’s theorem
and the Lenstra-Lenstra-Lovász basis reduction algorithm.

It is natural to study the generalization of the problem to the discrepancy of
arithmetic progressions in grids of side lengths that are not necessarily
equal. Given positive integers $N_{1},\dots,N_{d}$, let
$\Omega=[N_{1}]\times\cdots\times[N_{d}]\subseteq\mathbb{Z}^{d}$ and
$\mathcal{A}_{\mathbf{N}}$ be the set of arithmetic progressions in $d$
dimensions that are subsets of $\Omega$, where
$\mathbf{N}=(N_{1},\dots,N_{d})$. The discrepancy is defined in a similar way,

$\operatorname{disc}(\mathcal{A}_{\mathbf{N}}):=\min_{\chi:\Omega\to\\{1,-1\\}}\max_{A\in\mathcal{A}_{\mathbf{N}}}|\chi(A)|.$

In the proof of Theorem 1.1, we shall see that we will have to consider more
generally grids with side lengths of comparable size (see (1.1)).

######  Theorem 1.2.

For any positive integer $d$ and positive integers $N_{1},\dots,N_{d}$, if
$\delta>0$ satisfies that

$N_{1}\cdots N_{d}\leq\left(\min_{1\leq i\leq d}N_{i}\right)^{d+1-\delta},$
(1.1)

then there exist positive constants $c_{d},C_{d}$ such that for
$\mathbf{N}=(N_{1},\dots,N_{d})$,

$c_{d}\left(N_{1}\cdots
N_{d}\right)^{\frac{1}{2d+2}}\leq\operatorname{disc}(\mathcal{A}_{\mathbf{N}})\leq
C_{d}\cdot\frac{1}{\delta}\left(N_{1}\cdots N_{d}\right)^{\frac{1}{2d+2}}.$

We remark that Theorem 1.2 implies Theorem 1.1 by choosing $\delta=1$ and
$N_{1}=N_{2}=\cdots=N_{d}=N$.

The lower bound in Theorem 1.2 holds even without condition (1.1). Theorem 1.3
gives a more general lower bound, and a matching upper bound up to a sub-
logarithmic factor for general grids of differing side lengths. The lower
bound in Theorem 1.3 implies the lower bound in Theorem 1.2 by taking $I=[d]$
in the maximum. The proof of lower bound uses Fourier analytic tools.

######  Theorem 1.3.

For any positive integer $d$ and $\mathbf{N}=(N_{1},\dots,N_{d})$ where the
$N_{i}$’s are positive integers whose product is at least three, there exist
positive constants $c_{d},C_{d}$ such that

$c_{d}\max_{I\subseteq[d]}\left(\prod_{i\in
I}N_{i}\right)^{\frac{1}{2|I|+2}}\leq\operatorname{disc}(\mathcal{A}_{\mathbf{N}})\leq
C_{d}\frac{\log(N_{1}\cdots N_{d})}{\log\log(N_{1}\cdots
N_{d})}\cdot\max_{I\subseteq[d]}\left(\prod_{i\in
I}N_{i}\right)^{\frac{1}{2|I|+2}}.$ (1.2)

Here by convention if $I=\emptyset$ then $\prod_{i\in I}N_{i}=1$.

######  Remark.

Since $\operatorname{disc}(\mathcal{A}_{\mathbf{N}})$ does not depend on the
order of the $N_{i}$’s, we may assume without loss of generality that
$N_{1}\geq N_{2}\geq\cdots\geq N_{d}$. In this case

$\max_{I\subseteq[d]}\left(\prod_{i\in
I}N_{i}\right)^{\frac{1}{2|I|+2}}=\max_{1\leq k\leq
d}\left(\prod_{i=1}^{k}N_{i}\right)^{\frac{1}{2k+2}}.$

Organization. In Section 2, we show how to efficiently decompose arithmetic
progressions into “canonical” arithmetic progressions and provide an upper
bound on the number of such canonical arithmetic progressions with a given
size. This implies that a coloring which has low discrepancy in canonical
arithmetic progressions of each possible size also achieves low discrepancy
for all arithmetic progressions (see Lemma 2.1 for details). We prove the
upper bound in Theorem 1.2 in Section 3 by showing the existence of a coloring
which has low discrepancy in canonical arithmetic progressions of each
possible size. In the proof we use an improved bound on the number of
canonical arithmetic progressions with each given size, the proof of which is
deferred to Section 4. We finally study the case of grids with different side
lengths in the last three sections. We prove the lower bound of Theorem 1.3 in
Section 5 and the upper bound of Theorem 1.3 in Section 6. Finally, we have
some concluding remarks in Section 7, including a conjecture that the lower
bound for the the discrepancy for grids in Theorem 1.3 is tight up to the
constant factor.

######  Notations.

Throughout the paper, all logarithms are base $e$ unless specified. We
generally assume that $d$ is fixed, except in Section 4 where the proof relies
on an induction argument on $d$. We use symbols $c,c_{1},c_{2},C_{0},C,C^{*}$
to denote positive absolute constants, and $c_{d},C_{d}$ to denote those that
only depend on $d$. We use notation $f=O_{d}(g)$ if there exists a positive
constant $C_{d}$ so that $f\leq C_{d}g$.

##  2\. Decomposition

Let $N_{1},\dots,N_{d}$ be positive integers,
$\Omega=[N_{1}]\times\cdots\times[N_{d}]$, and
$\mathbf{N}=(N_{1},\dots,N_{d})$.

To find a coloring giving low discrepancy, the general idea is to apply a
partial coloring lemma (specifically Lemma 3.1, whose proof uses the entropy
method) to repeatedly partially color $\Omega$ until we get a full coloring of
$\Omega$ with low discrepancy. At each stage, we color a constant fraction of
the remaining uncolored elements, until we get a full coloring of $\Omega$
with low discrepancy. To accomplish this, we show that for any
$X\subseteq\Omega$, there is a partial coloring of $X$ with low discrepancy.
Once we have this statement, we may apply this with $X$ as $\Omega$ in the
initial iteration to get a partial coloring of $\Omega$, and then pick $X$ as
the set of uncolored elements of $\Omega$ in later iterations. Hence more
generally the set family we need to consider is $(X,\mathcal{A}_{X})$ where
$\mathcal{A}_{X}:=\\{A\cap X:A\in\mathcal{A}_{\mathbf{N}}\\}.$

The family of sets $\mathcal{A}_{X}$ is too large if we want to apply Lemma
3.1 on $(X,\mathcal{A}_{X})$ directly. Instead we apply it to a small
subfamily $\mathcal{C}_{X}\subseteq\mathcal{A}_{X}$ so that any set in
$\mathcal{A}_{X}$ can be efficiently decomposed into sets in
$\mathcal{C}_{X}$. For each
$\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$, we may partition
elements in $X$ into congruence classes modulo $\mathbf{b}$. For each
congruence class $I=\\{\mathbf{x}\in
X:\mathbf{x}\equiv\mathbf{a}\pmod{\mathbf{b}}\\}$, since distinct elements in
$I$ differ by nonzero multiples of $\mathbf{b}$, and their dot products with
$\mathbf{b}$ differ by nonzero multiples of $\|\mathbf{b}\|^{2}\neq 0$, we may
order elements in $I$ by their dot products with $\mathbf{b}$. Write
$I=\\{\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{l}\\}$, where the
subscripts respect the ordering and $l=|I|$. Now any set in $\mathcal{A}_{X}$
can be written as $\\{\mathbf{x}_{u}:i\leq u\leq j\\}$ for some
$(\mathbf{b},I,i,j)$. We use the following decomposition. For each
$\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$ and congruence class
$I$ modulo $\mathbf{b}$, we consider sets of the form
$\\{\mathbf{x}_{u}:(j-1)s+1\leq u\leq js\\}$ where $s=2^{t}$ is a power of
$2$, and $1\leq j\leq\lfloor l/s\rfloor$. Let $\mathcal{C}_{X}$ be the
collection of such sets for all $(\mathbf{b},I)$. All sets in
$\mathcal{C}_{X}$ are of sizes powers of $2$.

######  Lemma 2.1.

Let $b:\mathbb{N}\to(0,\infty)$ be a function. If $\chi$ is a partial coloring
of $X$ so that

$|\chi(S)|\leq b(|S|)$

for all $S\in\mathcal{C}_{X}$, then

$|\chi(A)|\leq 2\sum_{s:s=2^{t}}b(s)$

for all $A\in\mathcal{A}_{X}$.

###### Proof.

For any $A\in\mathcal{A}_{X}$, we know that it can be written as $A_{0}\cap X$
for some arithmetic progression $A_{0}\in\mathcal{A}_{\mathbf{N}}$. Let
$\mathbf{b}$ be the common difference of $A_{0}$, and let $I$ be intersection
of $X$ and the congruence class mod $\mathbf{b}$ containing $A_{0}$. Then $A$
is a subset of $I$. Moreover, as we describe in the procedure above, if we
order elements in $I=\\{\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{l}\\}$
by their dot product with $\mathbf{b}$, we know that $A$ must be in the form
$\\{\mathbf{x}_{u}:i\leq u\leq j\\}$. We write $A=A_{1}\setminus A_{2}$ where
$A_{1}=\\{\mathbf{x}_{u}:1\leq u\leq j\\}$ and $A_{2}=\\{\mathbf{x}_{u}:1\leq
u\leq i-1\\}$. Then we know that $A_{1}$ can be written as a disjoint union of
sets in $\mathcal{C}_{X}$ of different sizes $A_{1}=S_{1}\cup
S_{2}\cup\dots\cup S_{t}$ using the binary representation of $j$, where $t$ is
the number of digits $1$ in the representation. Also note that all sets in
$\mathcal{C}_{X}$ are of sizes powers of $2$, so we have

$|\chi(A_{1})|=\left|\sum_{k=1}^{t}\chi(S_{k})\right|\leq\sum_{k=1}^{t}|\chi(S_{k})|\leq\sum_{s:s=2^{t}}b(s).$

We may prove the similar inequality for $\chi(A_{2})$ by replacing $j$ with
$i-1$. Combining them we get

$|\chi(A)|=|\chi(A_{1})-\chi(A_{2})|\leq 2\sum_{s:s=2^{t}}b(s).$

∎

To apply the partial coloring lemma, Lemma 3.1, to $(X,\mathcal{C}_{X})$, we
need to estimate the number of sets of each size, and pick each $\Delta_{S}$
appropriately. Let $s=2^{t}$ be any power of $2$, we define $f(s,X)$ to be the
number of sets of size $s$ in $\mathcal{C}_{X}$. Note that $f(1,X)=|X|$.

For a positive integer $s$, a finite set $X\subseteq\mathbb{Z}^{d}$ and a
vector $\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$, let
$U^{d}(X,\mathbf{b},s)$ denote the set of all $x\in X$, whose residue class
mod $\mathbf{b}$ contains at least $s$ elements in $X$, or formally
$\\{x^{\prime}\in X:x^{\prime}\equiv x\pmod{\mathbf{b}}\\}$ is of size at
least $s$. The following inequality shows how these sets $U^{d}$ relate to the
quantity $f(s,X)$.

######  Lemma 2.2.

Let $X\subseteq\Omega$, and $s$ be a power of $2$. Then

$f(s,X)\leq\frac{1}{s}\sum_{\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}|U^{d}(X,\mathbf{b},s)|.$
(2.1)

###### Proof.

We would like to estimate the number of sets in $\mathcal{C}_{X}$ of size $s$.
For each $\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$, we partition
$X$ into the congruence classes modulo $\mathbf{b}$ which we denote by
$I_{1},\dots,I_{t}$. By definition, $U^{d}(X,\mathbf{b},s)$ is the disjoint
union of all $I_{k}$ that contains at least $s$ elements. Each set of size $s$
in $\mathcal{C}_{X}$ lies entirely in some $I_{k}$ for some appropriate choice
of $\mathbf{b}$ and $I_{k}$. The number of such sets in $I_{k}$ is at most
$\lfloor|I_{k}|/s\rfloor$. Therefore if we sum over all congruence classes,
the number of sets in $\mathcal{C}_{X}$ of size $s$ for any fixed $\mathbf{b}$
is

$\sum_{k=1}^{t}\lfloor|I_{k}|/s\rfloor\leq\sum_{k:|I_{k}|\geq
s}\frac{|I_{k}|}{s}=\frac{|U^{d}(X,\mathbf{b},s)|}{s}.$

Summing over all possible common differences
$\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$, we obtain (2.1). ∎

Hence we need to estimate the sum of the numbers of elements in these $U^{d}$
sets. We have the following simple upper bound.

######  Lemma 2.3.

For any $s\geq 2$ and $X\subseteq[N_{1}]\times\cdots\times[N_{d}]$, we have

$\sum_{\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}|U^{d}(X,\mathbf{b},s)|\leq|X|\cdot\prod_{i=1}^{d}\left(4\frac{N_{i}}{s}+1\right).$

###### Proof.

We focus on those $\mathbf{b}$ for which $U^{d}(X,\mathbf{b},s)$ is nonempty.
If $U^{d}(X,\mathbf{b},s)$ is nonempty, then we know that for each $i$, the
$i$-th coordinate of $\mathbf{b}$ is in the interval
$(-\frac{N_{i}}{s-1},\frac{N_{i}}{s-1})$. Therefore, the number of nonempty
$U^{d}(X,\mathbf{b},s)$ is at most

$\prod_{i=1}^{d}\left(\frac{2N_{i}}{s-1}+1\right)\leq\prod_{i=1}^{d}\left(4\frac{N_{i}}{s}+1\right).$

Applying the trivial bound $|U^{d}(X,\mathbf{b},s)|\leq|X|=m$, we get the
desired inequality. ∎

By combining Lemma 2.2 and Lemma 2.3 above, the following upper bound on
$f(s,X)$ holds.

######  Corollary 2.4.

For any $1\leq s\leq\min_{1\leq i\leq d}N_{i}$, we have

$f(s,X)\leq 5^{d}\frac{N_{1}\cdots N_{d}}{s^{d+1}}|X|.$

###### Proof.

When $s=1$, we have $f(1,X)=|X|$ and the inequality clearly holds. In the
remaining cases, $2\leq s\leq\min_{1\leq i\leq d}N_{i}$, we would like to
apply Lemma 2.2 and Lemma 2.3. As $s\leq N_{i}$ for each $1\leq i\leq d$, it
follows that

$f(s,X)\leq\frac{1}{s}\cdot|X|\prod_{i=1}^{d}\left(4\frac{N_{i}}{s}+1\right)\leq
5^{d}\frac{N_{1}\cdots N_{d}}{s^{d+1}}|X|.$

∎

We remark that in Section 4 we prove Lemma 3.5 which, together with Lemma 2.2,
gives a better upper bound on $f(s,X)$ than Corollary 2.4 for a certain range
of $s$.

##  3\. Proof of the upper bound in Theorem 1.2

We use the following version of the partial coloring lemma which was first
proved by Matoušek and Spencer in [8], to show the existence of a partial
coloring that colors a constant fraction of elements of a set system with low
discrepancy.

######  Lemma 3.1 (Section 4.6 in [7]).

Let $(\Omega,\mathcal{C})$ be a set system on $n$ elements, and let a number
$\Delta_{S}>0$ be given for each set $S\in\mathcal{C}$. Suppose that

$\sum_{S\in\mathcal{C}:S\neq\emptyset}g\left(\frac{\Delta_{S}}{\sqrt{|S|}}\right)\leq\frac{n}{5}$
(3.1)

where

$g(\lambda)=\begin{cases}10e^{-\lambda^{2}/4}&\textrm{if }\lambda\geq 2,\\\
10\log(1+2\lambda^{-1})&\textrm{if }0<\lambda<2.\end{cases}$ (3.2)

Then there exists a partial coloring $\chi$ that assigns $\pm 1$ to at least
$n/10$ variables (and $0$ to the rest), satisfying $|\chi(S)|\leq\Delta_{S}$
for each $S\in\mathcal{C}$.

We apply Lemma 3.1 to the set system $(X,\mathcal{C}_{X})$ defined in Section
2. In (3.2) we intentionally choose $g$ to be monotonically decreasing. We
further show the following property of $g$.

######  Lemma 3.2.

Let $d\in\mathbb{N}$ and $c=10d+2400$. Let $K$ be a positive real number, and
let $b:\mathbb{N}\to(0,\infty)$ be defined as

$b(s)=\begin{cases}c\sqrt{s}\cdot\left(sK^{-\frac{1}{d+1}}\right)^{-1}&\mbox{if
}s\geq K^{\frac{1}{d+1}}\\\
c\sqrt{s}\cdot\left(sK^{-\frac{1}{d+1}}\right)^{-0.1}&\mbox{if
}s<K^{\frac{1}{d+1}}\end{cases}.$ (3.3)

Then for $g$ as defined in (3.2), we have

$\sum_{i=0}^{\infty}\frac{K}{2^{i(d+1)}}g\left(\frac{b(2^{i})}{2^{i/2}}\right)\leq
1.$

###### Proof.

Let $s_{i}=2^{i}$ and $\tau_{i}=2^{i}K^{-\frac{1}{d+1}}$, where $i$ takes
nonnegative integer values. Now we may rewrite

$\frac{b(2^{i})}{2^{i/2}}=\begin{cases}c\tau_{i}^{-1}&\mbox{if }\tau_{i}\geq
1\\\ c\tau_{i}^{-0.1}&\mbox{if }\tau_{i}<1\end{cases}.$

Since the right hand side only depends on $\tau_{i}$, we denote it as
$\lambda(\tau_{i})$. Therefore we have

$\sum_{i=0}^{\infty}\frac{K}{2^{i(d+1)}}g\left(\frac{b(2^{i})}{2^{i/2}}\right)=\sum_{i=0}^{\infty}\tau_{i}^{-d-1}g(\lambda(\tau_{i}))=\sum_{\tau_{i}<1}\tau_{i}^{-d-1}g(c\tau_{i}^{-0.1})+\sum_{\tau_{i}\geq
1}\tau_{i}^{-d-1}g(c\tau_{i}^{-1}).$ (3.4)

We bound two terms on the right hand side of (3.4) separately. For the first
term, note that $\\{\tau_{i}<1\\}$ can be seen as a geometric sequence with
ratio $1/2$. For any $x>0$ and positive integer $t$, we have
$e^{x}\geq\frac{x^{t}}{t!}$. Thus by setting $x=\tau_{i}^{-0.2}$ and $t=5d+10$
we get that the series

$\sum_{\tau_{i}<1}\tau_{i}^{-d-1}e^{-\tau_{i}^{-0.2}}\leq\sum_{\tau_{i}<1}\tau_{i}^{-d-1}\cdot(5d+10)!\tau_{i}^{0.2\cdot(5d+10)}=(5d+10)!\sum_{\tau_{i}<1}\tau_{i}\leq
2(5d+10)!.$

We denote $c_{1}=2(5d+10)!$. Note that $c=10d+2400$ satisfies
$c^{2}/4>1+\log(20c_{1})$. For $\tau<1$, we have $c\tau^{-0.1}>2$, so
$g(c\tau^{-0.1})$ uses the branch $g(\lambda)=10e^{-\lambda^{2}/4}$. Therefore

$g(c\tau^{-0.1})=10e^{-\frac{c^{2}\tau^{-0.2}}{4}}\leq
10e^{-(1+\log(20c_{1}))\tau_{i}^{-0.2}}\leq 10e^{-\tau^{-0.2}-\log
20c_{1}}=\frac{1}{2c_{1}}e^{-\tau^{-0.2}}.$

Using this, we may bound the first term on the right hand side of (3.4) as
following

$\sum_{\tau_{i}<1}\tau_{i}^{-d-1}g(c\tau_{i}^{-0.1})\leq\sum_{\tau_{i}<1}\tau_{i}^{-d-1}\cdot\frac{1}{2c_{1}}e^{-\tau_{i}^{-0.2}}\leq\frac{1}{2c_{1}}\cdot
c_{1}=\frac{1}{2}.$ (3.5)

Now we bound the second term on the right hand side of (3.4). As
$\\{\tau_{i}\geq 1\\}$ forms a geometric sequence with ratio $2$ and
$\log(1+2\tau_{i})\leq 3\tau_{i}$ when $\tau_{i}\geq T>1$, we have for
$T=240$,

$\sum_{\tau_{i}>T}\tau_{i}^{-d-1}\log(1+2\tau_{i})\leq\sum_{\tau_{i}>T}\tau_{i}^{-d-1}\cdot
3\tau_{i}=3\sum_{\tau_{i}>T}\tau_{i}^{-d}\leq
3\sum_{\tau_{i}>T}\tau_{i}^{-1}\leq\frac{6}{T}=\frac{1}{40}.$

For any $c=c(d)>1$ and $\tau\geq T$, as $g$ is monotonically decreasing, we
have $g(c\tau^{-1})\leq g(\tau^{-1})=10\log(1+2\tau)$ where we use the branch
$g(\lambda)=10\log(1+2\lambda^{-1})$ as $\tau^{-1}<2$. Hence

$\sum_{\tau_{i}\geq T}\tau_{i}^{-d-1}g(c\tau_{i}^{-1})\leq\sum_{\tau_{i}\geq
T}\tau_{i}^{-d-1}\cdot 10\log(1+2\tau_{i})\leq
10\cdot\frac{1}{40}=\frac{1}{4}.$ (3.6)

Finally, for $\tau_{i}<T$, we have $g(c\tau^{-1})\leq g(cT^{-1})$. As
$g(10)\leq\frac{1}{8}$ and $c>2400=10T$, $g(cT^{-1})\leq\frac{1}{8}$.
Consequently,

$\sum_{1\leq\tau_{i}<T}\tau_{i}^{-d-1}g(c\tau_{i}^{-1})\leq\sum_{1\leq\tau_{i}<T}\tau_{i}^{-d-1}\cdot\frac{1}{8}<\frac{1}{4}.$
(3.7)

Here in the last inequality we use that $\\{\tau_{i}:1\leq\tau_{i}<T\\}$ forms
a geometric series with ratio $2$ and the initial term is at least $1$.

Substituting the bounds (3.5), (3.6), and (3.7) into (3.4), we obtain the
desired inequality.

∎

We choose the function $b$ of the form specified in Lemma 3.2 as it has a good
summation property over powers of $2$. This is illustrated by the following
lemma.

######  Lemma 3.3.

Let $d$ be a positive integer, and $c,K$ be positive real numbers. Let
$b:\mathbb{N}\to(0,\infty)$ be the function defined in (3.3). Suppose that
$u<v$ are positive real numbers. Then

$\sum_{s:s=2^{t}\in[u,v]}b(s)\leq
5cK^{\frac{1}{2d+2}}\min\left(\left(vK^{-\frac{1}{d+1}}\right)^{0.4},\left(uK^{-\frac{1}{d+1}}\right)^{-0.5}\right).$

###### Proof.

Here we assume that $s$ takes value over powers of $2$. Note that

$b(s)=\min\left(c\sqrt{s}\cdot\left(sK^{-\frac{1}{d+1}}\right)^{-1},c\sqrt{s}\cdot\left(sK^{-\frac{1}{d+1}}\right)^{-0.1}\right).$

Using that $b(s)\leq c\sqrt{s}\cdot\left(sK^{-\frac{1}{d+1}}\right)^{-0.1}$,
we get

$\sum_{u\leq s\leq v}b(s)\leq cK^{\frac{1}{10(d+1)}}\sum_{u\leq s\leq
v}s^{0.4}\leq cK^{\frac{0.1}{d+1}}v^{0.4}\left(\sum_{j\leq
0}2^{0.4j}\right)\leq
5cK^{\frac{1}{2d+2}}\left(vK^{-\frac{1}{d+1}}\right)^{0.4}.$

Similarly using $b(s)\leq
c\sqrt{s}\cdot\left(sK^{-\frac{1}{d+1}}\right)^{-1}$, we have

$\sum_{u\leq s\leq v}b(s)\leq cK^{\frac{1}{d+1}}\sum_{u\leq s\leq
v}s^{-0.5}\leq cK^{\frac{1}{d+1}}u^{-0.5}\left(\sum_{j\geq
0}2^{-0.5j}\right)\leq
5cK^{\frac{1}{2d+2}}\left(uK^{-\frac{1}{d+1}}\right)^{-0.5}.$

∎

Combining the lemmas above with Corollary 2.4, we derive below Proposition
3.4, which is slightly weaker than what we need to prove Theorem 1.1. Indeed,
if we iteratively apply Proposition 3.4 to the remaining uncolored elements,
we get $\operatorname{disc}(\mathcal{A}_{d})=O_{d}(N^{\frac{d}{2d+2}}\log N)$.

######  Proposition 3.4.

Let $d\in\mathbb{N}$ and $c=500d+10^{6}$. For any $X\subseteq[N]^{d}$, there
exists a partial coloring $\chi:X\to\\{-1,0,1\\}$ that assigns $\pm 1$ to at
least $|X|/10$ elements in $X$ such that

$\max_{A_{0}\in\mathcal{A}_{d}}|\chi(A_{0}\cap X)|\leq cN^{\frac{d}{2d+2}}.$

###### Proof.

Here we treat $d$ as a constant. Suppose that $|X|=m$. Let
$b:\mathbb{N}\to(0,\infty)$ be determined later. We want to apply Lemma 3.1 to
the set system $(X,\mathcal{C}_{X})$ to find a partial coloring
$\chi:X\to\\{0,\pm 1\\}$ that assigns $\pm 1$ to at least $m/10$ elements, and
that $|\chi(S)|\leq b(|S|)$ for any $S\in\mathcal{C}_{X}$. By Lemma 3.1, it
suffices to ensure that $b$ satisfies the inequality

$\sum_{s:s=2^{t}\leq N}f(s,X)g\left(\frac{b(s)}{\sqrt{s}}\right)\leq m/5.$
(3.8)

By Corollary 2.4, we know that $f(s,X)\leq 5^{d}\frac{N^{d}m}{s^{d+1}}.$ It
now suffices to show

$\sum_{s:s=2^{t}\leq
N}5^{d}\frac{N^{d}m}{s^{d+1}}g\left(\frac{b(s)}{\sqrt{s}}\right)\leq m/5.$
(3.9)

Let $K=5^{d+1}N^{d}$. By Lemma 3.2, if we set $b$ as in (3.3) with
$c_{1}=10d+2400$

$b(s)=\begin{cases}c_{1}\sqrt{s}\cdot\left(sK^{-\frac{1}{d+1}}\right)^{-1}&\mbox{if
}s\geq K^{\frac{1}{d+1}}\\\
c_{1}\sqrt{s}\cdot\left(sK^{-\frac{1}{d+1}}\right)^{-0.1}&\mbox{if
}s<K^{\frac{1}{d+1}}\end{cases},$ (3.10)

then (3.9) is satisfied. Therefore by Lemma 3.1, we know that there exists a
partial coloring $\chi$ that assigns $\pm 1$ to at least $m/10$ elements, and
that $|\chi(S)|\leq b(|S|)$ for any $S\in\mathcal{C}_{X}$. By Lemma 2.1, we
know that for any $A\in\mathcal{A}_{X}$, $|\chi(A)|\leq
2\sum_{s:s=2^{t}}b(s)$. Now we have

$2\sum_{s:s=2^{t}\leq N}b(s)\leq
2\sum_{s:s=2^{t}\in[1,K^{\frac{1}{d+1}}]}b(s)+2\sum_{s:s=2^{t}\in[K^{\frac{1}{d+1}},N+1]}b(s)\leq
20c_{1}K^{\frac{1}{2d+2}}.$

In the second inequality above we use Lemma 3.3 for
$(u,v)=(1,K^{\frac{1}{d+1}})$ and $(u,v)=(K^{\frac{1}{d+1}},N)$ respectively.
Note that
$K^{\frac{1}{2d+2}}=5^{\frac{d+1}{2d+2}}N^{\frac{d}{2d+2}}=\sqrt{5}N^{\frac{d}{2d+2}}$.
Hence we conclude that we can always find partial coloring $\chi$ that assigns
$\pm 1$ to at least $m/10$ elements in $X$, and satisfies

$\max_{A_{0}\in\mathcal{A}_{d}}|\chi(A_{0}\cap
X)|=\max_{A\in\mathcal{A}_{X}}|\chi(A)|\leq cN^{\frac{d}{2d+2}},$

where $c=20\sqrt{5}c_{1}<500d+10^{6}$. ∎

Not surprisingly, to improve on the bound above, we need to improve on
Corollary 2.4. In particular, we will show in Section 4 that the following
holds.

######  Lemma 3.5.

There exists an absolute constant $C_{0}$ such that the following holds. Let
$d$ be a positive integer. Given positive integers $N_{1},N_{2},\dots,N_{d}$
satisfying $N_{1}\cdots N_{d}\leq(\min_{1\leq i\leq d}N_{i})^{d+1-\delta}$ for
some $\delta\in(0,1]$, suppose that
$X\subseteq[N_{1}]\times\cdots\times[N_{d}]$ is of size $m$. Letting
$\rho=\frac{m}{N_{1}\cdots N_{d}}$, if integer $s$ satisfies $(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\leq s\leq(\min_{1\leq
i\leq d}N_{i})\rho^{\beta}$ for some $\beta\in(0,1/2)$, then

$\sum_{\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}|U^{d}(X,\mathbf{b},s)|\leq
C_{0}2^{d^{3}}5^{d}\frac{mN_{1}N_{2}\cdots
N_{d}}{s^{d}}\cdot\rho^{\frac{\min(\beta,\delta)}{4^{d}\cdot(d+2)!}}.$ (3.11)

Assuming Lemma 3.5, we prove the following improvement on Proposition 3.4.

######  Proposition 3.6.

Let $d$ be a positive integer. There exist constants $C_{d}$ and $c_{d}$ such
that the following holds. Let $N_{1},N_{2},\dots,N_{d}$ be positive integers
satisfying $N_{1}\cdots N_{d}\leq(\min_{1\leq i\leq d}N_{i})^{d+1-\delta}$ for
some $\delta\in(0,1]$. For any nonempty
$X\subseteq[N_{1}]\times\cdots\times[N_{d}]$, there exists a partial coloring
$\chi:X\to\\{-1,0,1\\}$ that assigns $\pm 1$ to at least $|X|/10$ elements in
$X$, and

$\max_{A_{0}\in\mathcal{A}_{\mathbf{N}}}|\chi(A_{0}\cap X)|\leq
C_{d}(N_{1}\cdots N_{d})^{\frac{1}{2d+2}}\cdot\left(\frac{|X|}{N_{1}\cdots
N_{d}}\right)^{c_{d}\delta}.$

###### Proof.

The general proof strategy is the same as in the proof of Proposition 3.4.
Without loss of generality we may assume $N_{1}\leq\cdots\leq N_{d}$. We would
like to find a function $b:\mathbb{N}\to(0,\infty)$ such that

$\sum_{s:s=2^{t}\leq
N_{d}}f(s,X)g\left(\frac{b(s)}{\sqrt{s}}\right)\leq|X|/5.$ (3.12)

Here we sum only over $s\leq N_{d}$ as there is no congruence class of
$X\subseteq[N_{1}]\times\cdots\times[N_{d}]$ of length greater than $N_{d}$.
To estimate $f(s,X)/|X|$, we know that Corollary 2.4 gives an upper bound for
$1\leq s\leq N_{1}$. For $N_{1}<s\leq N_{d}$, we apply Lemma 2.2 and Lemma 2.3
and get that

$\frac{f(s,X)}{|X|}\leq\frac{1}{s}\prod_{i=1}^{d}\left(4\frac{N_{i}}{s}+1\right)\leq\frac{1}{s}\cdot
5\frac{N_{d}}{s}\cdot\prod_{i=1}^{d-1}5\frac{N_{i}}{N_{1}}=\frac{5^{d}N_{1}\cdots
N_{d}}{N_{1}^{d-1}}\cdot\frac{1}{s^{2}}.$ (3.13)

Here we use the inequalities $4\frac{N_{d}}{s}+1\leq 5\frac{N_{d}}{s}$ as
$s\leq N_{d}$, and $4\frac{N_{i}}{s}+1\leq 5\frac{N_{i}}{N_{1}}$ as $s>N_{1}$
and $N_{i}\geq N_{1}$. Now combining with Lemma 3.5 applied with
$\beta=\frac{\delta}{4(d+1)^{2}}$, we derive the following inequality:

$\frac{f(s,X)}{|X|}\leq\begin{cases}\frac{1}{s^{2}}\frac{5^{d}N_{1}\cdots
N_{d}}{N_{1}^{d-1}}&\mbox{if }N_{1}<s\leq N_{d}\\\
\frac{1}{s^{d+1}}5^{d}N_{1}\cdots N_{d}&\mbox{if }1\leq s<(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\mbox{ or
}N_{1}\rho^{\frac{\delta}{4(d+1)^{2}}}<s\leq N_{1}\\\
\frac{1}{s^{d+1}}C_{d}N_{1}\cdots
N_{d}\rho^{\frac{\delta}{4^{d+1}(d+1)^{2}\cdot(d+2)!}}&\mbox{if }(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\leq s\leq
N_{1}\rho^{\frac{\delta}{4(d+1)^{2}}}\end{cases}$ (3.14)

for $\rho:=\frac{|X|}{N_{1}\cdots N_{d}}$. Here we applied (3.13) on the first
range, Corollary 2.4 on the second, and Lemma 3.5 on the third with
$C=C_{0}2^{d^{3}}5^{d}$ for some absolute constant $C_{0}$.

We denote $K_{1}=15\frac{5^{d}N_{1}\cdots N_{d}}{N_{1}^{d-1}}$, $K_{2}=15\cdot
5^{d}N_{1}\cdots N_{d}$, and $K_{3}=15CN_{1}\cdots
N_{d}\rho^{\frac{\delta}{4^{d+1}(d+1)^{2}\cdot(d+2)!}}$ for simplicity.
Applying Lemma 3.2 three times, if we define with $c_{1}=2410$ and
$c_{2}=10d+2400$

$b_{1}(s)=\begin{cases}c_{1}\sqrt{s}\cdot\left(sK_{1}^{-\frac{1}{2}}\right)^{-1}&\mbox{if
}s\geq K_{1}^{\frac{1}{2}}\\\
c_{1}\sqrt{s}\cdot\left(sK_{1}^{-\frac{1}{2}}\right)^{-0.1}&\mbox{if
}s<K_{1}^{\frac{1}{2}}\end{cases},$ (3.15)

and for $i=2$ and $3$

$b_{i}(s)=\begin{cases}c_{2}\sqrt{s}\cdot\left(sK_{i}^{-\frac{1}{d+1}}\right)^{-1}&\mbox{if
}s\geq K_{i}^{\frac{1}{d+1}}\\\
c_{2}\sqrt{s}\cdot\left(sK_{i}^{-\frac{1}{d+1}}\right)^{-0.1}&\mbox{if
}s<K_{i}^{\frac{1}{d+1}}\end{cases},$ (3.16)

then as $s$ taking values in powers of $2$, we have the following three
inequalities:

$\displaystyle\sum_{N_{1}<s\leq
N_{d}}\frac{K_{1}}{s^{2}}g\left(\frac{b_{1}(s)}{\sqrt{s}}\right)$
$\displaystyle\leq 1,$ (3.17) $\displaystyle\sum_{1\leq s<(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}}\frac{K_{2}}{s^{d+1}}g\left(\frac{b_{2}(s)}{\sqrt{s}}\right)+\sum_{N_{1}\rho^{\frac{\delta}{4}}<s\leq
N_{1}}\frac{K_{2}}{s^{d+1}}g\left(\frac{b_{2}(s)}{\sqrt{s}}\right)$
$\displaystyle\leq 1,$ (3.18) $\displaystyle\sum_{(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\leq s\leq
N_{1}\rho^{\frac{\delta}{4}}}\frac{K_{3}}{s^{d+1}}g\left(\frac{b_{3}(s)}{\sqrt{s}}\right)$
$\displaystyle\leq 1.$ (3.19)

If we apply (3.14) to (3.17), (3.18), and (3.19), we derive that

$\displaystyle\sum_{N_{1}<s\leq
N_{d}}\frac{f(s,X)}{|X|}g\left(\frac{b_{1}(s)}{\sqrt{s}}\right)$
$\displaystyle\leq\frac{1}{15},$ (3.20) $\displaystyle\sum_{1\leq
s<(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}}\frac{f(s,X)}{|X|}g\left(\frac{b_{2}(s)}{\sqrt{s}}\right)+\sum_{N_{1}\rho^{\frac{\delta}{4(d+1)^{2}}}<s\leq
N_{1}}\frac{f(s,X)}{|X|}g\left(\frac{b_{2}(s)}{\sqrt{s}}\right)$
$\displaystyle\leq 1,$ (3.21) $\displaystyle\sum_{(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\leq s\leq
N_{1}\rho^{\frac{\delta}{4(d+1)^{2}}}}\frac{f(s,X)}{|X|}g\left(\frac{b_{3}(s)}{\sqrt{s}}\right)$
$\displaystyle\leq 1.$ (3.22)

Therefore, we may define $b$ in terms of $b_{1},b_{2},b_{3}$ as following so
that (3.12) is satisfied:

$b(s)=\begin{cases}b_{1}(s)&\mbox{if }N_{1}<s\leq N_{d}\\\ b_{2}(s)&\mbox{if
}1\leq s<(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\mbox{ or
}N_{1}\rho^{\frac{\delta}{4(d+1)^{2}}}<s\leq N_{1}\\\ b_{3}(s)&\mbox{if
}(N_{1}\cdots N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\leq s\leq
N_{1}\rho^{\frac{\delta}{4(d+1)^{2}}}\end{cases}.$ (3.23)

Hence by Lemma 3.1, we conclude that there exists $\chi:X\to\\{-1,0,1\\}$ that
assigns $\pm 1$ to at least $|X|/10$ elements in $X$ such that $|\chi(S)|\leq
b(|S|)$ for any $S\in\mathcal{C}_{X}$. By Lemma 2.1, we know that
$|\chi(A)|\leq 2\sum_{s}b(s)$ for any $A\in\mathcal{A}_{X}$. We shall estimate
$\sum_{s}b(s)$ on five intervals using Lemma 3.3:

$\displaystyle\sum_{N_{1}<s\leq N_{d}}b_{1}(s)$ $\displaystyle\leq
5c_{1}K_{1}^{\frac{1}{2}}N_{1}^{-\frac{1}{2}},$ (3.24)
$\displaystyle\sum_{1\leq s<(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}}b_{2}(s)$
$\displaystyle\leq 5c_{2}K_{2}^{\frac{1}{10d+10}}(N_{1}\cdots
N_{d})^{\frac{2}{5d+5}}\rho^{\frac{2\delta}{5\cdot 4^{d}(d+1)}},$ (3.25)
$\displaystyle\sum_{N_{1}\rho^{\frac{\delta}{4(d+1)^{2}}}<s\leq
N_{1}}b_{2}(s)$ $\displaystyle\leq
5c_{2}K_{2}^{\frac{1}{d+1}}N_{1}^{-\frac{1}{2}}\rho^{-\frac{\delta}{8(d+1)^{2}}},$
(3.26) $\displaystyle\sum_{(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\leq
s<K_{3}^{\frac{1}{d+1}}}b_{3}(s)$ $\displaystyle\leq
5c_{2}K_{3}^{\frac{1}{2d+2}},$ (3.27)
$\displaystyle\sum_{K_{3}^{\frac{1}{d+1}}\leq s\leq
N_{1}\rho^{\frac{\delta}{4(d+1)^{2}}}}b_{3}(s)$ $\displaystyle\leq
5c_{2}K_{3}^{\frac{1}{2d+2}}.$ (3.28)

Note that $N_{1}\geq(N_{1}\cdots N_{d})^{\frac{1}{d+1-\delta}}$. As $X$ is
nonempty, we have $\rho\geq\frac{1}{N_{1}\cdots N_{d}}$. For (3.24) we have

$5c_{1}K_{1}^{\frac{1}{2}}N_{1}^{-\frac{1}{2}}\leq
5^{\frac{d}{2}+2}c_{1}(N_{1}\cdots
N_{d})^{\frac{1}{2}\left(1-\frac{d}{d+1-\delta}\right)}\leq
5^{\frac{d}{2}+2}c_{1}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\rho^{\frac{d\delta}{2(d+1)(d+1-\delta)}}.$ (3.29)

Here in the first inequality we use $\sqrt{15\cdot 5^{d}}\leq
5^{\frac{d}{2}+1}$ and $N_{1}\geq(N_{1}\cdots N_{d})^{\frac{1}{d+1-\delta}}$,
and in the second we use $\rho\geq\frac{1}{N_{1}\cdots N_{d}}$. Similarly we
can estimate the right hand sides of (3.25), (3.26), (3.27), (3.28) as
follows:

$5c_{2}K_{2}^{\frac{1}{10d+10}}=5c_{2}\cdot(5^{d}15)^{\frac{1}{10d+10}}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\rho^{\frac{2\delta}{5\cdot 4^{d}(d+1)}}\leq
10c_{2}(N_{1}\cdots N_{d})^{\frac{1}{2d+2}}\rho^{\frac{2\delta}{5\cdot
4^{d}(d+1)}},$ (3.30)
$\begin{split}5c_{2}K_{2}^{\frac{1}{d+1}}N_{1}^{-\frac{1}{2}}\rho^{\frac{-\delta}{8(d+1)^{2}}}&\leq
50c_{2}(N_{1}\cdots N_{d})^{\frac{1}{2d+2}}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}-\frac{1}{2d+2-2\delta}}\rho^{\frac{-\delta}{8(d+1)^{2}}}\\\
&\leq 50c_{2}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\rho^{\frac{\delta}{2(d+1)(d+1-\delta)}-\frac{\delta}{8(d+1)^{2}}}\\\
&\leq 50c_{2}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\rho^{\frac{\delta}{4(d+1)^{2}}},\end{split}$ (3.31)
$5c_{2}K_{3}^{\frac{1}{2d+2}}\leq 10c_{2}C^{\frac{1}{2d+2}}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\rho^{\frac{\delta}{2\cdot
4^{d+1}(d+1)^{3}\cdot(d+2)!}}.$ (3.32)

Now we define $c_{d}=\frac{1}{2\cdot 4^{d+1}(d+1)^{3}\cdot(d+2)!}$. The
exponents of $\rho$ in (3.29), (3.30), (3.31) and (3.32) are at least
$c_{d}\delta$. Putting (3.29) into (3.24), (3.30) into (3.25), (3.31) into
(3.26), and (3.32) into (3.27) and (3.28) and summing them together, we derive
that

$\sum_{s}b(s)\leq\left(5^{\frac{d}{2}+2}c_{1}+10c_{2}+50c_{2}+10c_{2}C^{\frac{1}{2d+2}}+10c_{2}C^{\frac{1}{2d+2}}\right)\cdot(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\rho^{c_{d}\delta}.$

Hence if we set
$C_{d}=2\left(5^{\frac{d}{2}+2}c_{1}+60c_{2}+20c_{2}C^{\frac{1}{2d+2}}\right)$,
then for any $X$ there exists $\chi:X\to\\{-1,0,1\\}$ that assigns $\pm 1$ to
at least $|X|/10$ elements in $X$ such that

$\max_{A_{0}\in\mathcal{A}_{\mathbf{N}}}|\chi(A_{0}\cap
X)|=\max_{A\in\mathcal{A}_{X}}|\chi(A)|\leq C_{d}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\left(\frac{|X|}{N_{1}\cdots
N_{d}}\right)^{c_{d}\delta},$

as desired. ∎

######  Remark.

The argument gives $C_{d}=2^{O(d^{2})}$ and $c_{d}=2^{-O(d\log d)}$.

######  Corollary 3.7.

Let $d$ be a positive integer. There exist constants $C_{d}$ and $c_{d}$ such
that the following holds. Let $N_{1},N_{2},\dots,N_{d}$ be positive integers
satisfying $N_{1}\cdots N_{d}\leq(\min_{1\leq i\leq d}N_{i})^{d+1-\delta}$ for
some $\delta\in(0,1]$. For any nonempty
$X\subseteq[N_{1}]\times\cdots\times[N_{d}]$, there exists a coloring
$\chi:X\to\\{-1,1\\}$ with

$\max_{A_{0}\in\mathcal{A}_{\mathbf{N}}}|\chi(A_{0}\cap X)|\leq
C_{d}\frac{1}{\delta}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\cdot\left(\frac{|X|}{N_{1}\cdots
N_{d}}\right)^{c_{d}\delta}.$

###### Proof.

Let $C_{d}^{\prime},c_{d}^{\prime}$ be the constants in Proposition 3.6. Then
we set $c_{d}=\min(c_{d}^{\prime},1)$. Starting from $X_{1}=X$, for each
$i\geq 0$, we partially color $X_{i}$ by using Proposition 3.6 and let
$X_{i+1}$ be the set of uncolored points. Suppose that we do this for $K$
iterations such that $X_{K+1}=\emptyset$. Since $|X_{i}|\leq(0.9)^{i-1}|X|$ it
follows that the total discrepancy of this coloring is at most

$\sum_{i=1}^{K}C_{d}^{\prime}(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\left(\frac{|X_{i}|}{N_{1}\cdots
N_{d}}\right)^{c_{d}\delta}\leq(N_{1}\cdots
N_{d})^{\frac{1}{2d+2}}\left(\frac{|X|}{N_{1}\cdots
N_{d}}\right)^{c_{d}\delta}\cdot
C_{d}^{\prime}\sum_{i=1}^{K}\left((0.9)^{c_{d}\delta}\right)^{i-1}.$

Finally noting that $\delta\leq 1$, we have
$1-(0.9)^{c_{d}\delta}\geq\frac{c_{d}\delta}{10}$ as $c_{d}\delta\in(0,1]$.
Therefore we have

$\sum_{i=1}^{K}\left((0.9)^{c_{d}\delta}\right)^{i-1}\leq\frac{1}{1-(0.9)^{c_{d}\delta}}\leq\frac{10}{c_{d}\delta}.$

We may set $C_{d}=\frac{10C_{d}^{\prime}}{c_{d}}$ to get the desired
inequality. ∎

###### Proof of the upper bound of Theorem 1.2.

By using Corollary 3.7 and taking $X=[N_{1}]\times\cdots\times[N_{d}]$, we
have $\operatorname{disc}(\mathcal{A}_{\mathbf{N}})\leq
C_{d}\frac{(N_{1}\cdots N_{d})^{\frac{1}{2d+2}}}{\delta}$ for some
$C_{d}=2^{O(d^{2})}$ which proves Theorem 1.2. ∎

##  4\. A better estimate on the number of sets in the decomposition

In this section, we prove Lemma 3.5, which improves upon Lemma 2.3. Recall
that $U^{d}(X,\mathbf{b},s)$ is the set of elements in $X$ for which there are
at least $s$ elements of $X$ in the same residue class mod $\mathbf{b}$.

To prove Lemma 3.5, we induct on $d$. We need the following two results
regarding lattice points.

######  Lemma 4.1 (Minkowski’s theorem, see e.g. Section III.2.2 in [4]).

Let $X\subseteq\mathbb{R}^{d}$ be a point set of volume $V(X)$ which is
symmetric about the origin and convex. Let $\Gamma\subseteq\mathbb{R}^{d}$ be
a $d$-dimensional lattice of determinant $\det(\Gamma)$. If
$V(X)>2^{d}\det(\Gamma)$, then $X\cap\Gamma$ contains a pair of distinct
points $\pm\mathbf{x}$.

######  Lemma 4.2 (Lenstra-Lenstra-Lovász Basis Reduction [6]).

Let $\Gamma\subseteq\mathbb{R}^{d}$ be a $d$-dimensional lattice of
determinant $\det(\Gamma)$. There exists a basis
$\mathbf{x}_{1},\dots,\mathbf{x}_{d}$ of $\Gamma$ such that

$\det(\Gamma)\leq\prod_{i=1}^{n}\|\mathbf{x}_{i}\|_{2}\leq
2^{\frac{d(d-1)}{4}}\det(\Gamma).$

######  Remark.

The inequality above is true for any reduced basis (see [6, Proposition 1.6]);
the existence of which is guaranteed by an algorithm which transforms any
given basis to a reduced one (see [6, Proposition 1.26]). It will not be
important for us what the definition of a reduced basis is.

######  Corollary 4.3.

Let $\Gamma\subseteq\mathbb{R}^{d}$ be a $d$-dimensional lattice. Suppose that
$V_{0}>0$ is a real number such that the following holds: for every set
$P\subseteq\mathbb{R}^{d}$ of volume $V_{d}(P)>V_{0}$ that is symmetric about
the origin and convex, $P\cap\Gamma$ contains a nonzero point. Then there
exists a basis $\mathbf{x}_{1},\dots,\mathbf{x}_{d}$ of $\Gamma$ such that

$\prod_{i=1}^{n}\|\mathbf{x}_{i}\|_{2}\leq 2^{\frac{d(d-1)}{4}-d}V_{0}.$

###### Proof.

Let $\mathbf{y}_{1},\dots,\mathbf{y}_{d}$ be a basis of $\Gamma$. Note that
the fundamental parallelepiped of $\Gamma$ defined as
$\\{\mathbf{a}\cdot\mathbf{y}:\mathbf{a}\in(0,1)^{d-1}\\}$ where
$\mathbf{y}:=(\mathbf{y}_{1},\dots,\mathbf{y}_{d})$ contains no nonzero vector
of $\Gamma$. By translation, there is no nonzero vector of $\Gamma$ in
$P:=\\{\mathbf{a}\cdot\mathbf{y}:\mathbf{a}\in(-1,1)^{d-1}\\}$, and from the
condition we know that $V_{d}(P)\leq V_{0}$. Note that
$V_{d}(P)=2^{d}\det(\Gamma)$, so $\det(\Gamma)\leq 2^{-d}V_{0}$. By Lemma 4.2,
there exists a basis $\mathbf{x}_{1},\dots,\mathbf{x}_{d}$ such that

$\prod_{i=1}^{n}\|\mathbf{x}_{i}\|_{2}\leq
2^{\frac{d(d-1)}{4}}\det(\Gamma)\leq 2^{\frac{d(d-1)}{4}-d}V_{0},$

which completes the proof. ∎

Before we start to prove Lemma 3.5, we introduce some standard notation. For a
map $\phi:X\to Y$ and subsets $A\subseteq X$ and $B\subseteq Y$, let $\phi(A)$
be the set of images $\\{\phi(a):a\in A\\}\subseteq Y$, and let $\phi^{-1}(B)$
be the set of preimages $\\{x\in X:\phi(x)\in B\\}\subseteq X$.

We next prove a geometric lemma which shows that, given a vector
$\mathbf{b}\in\mathbb{Z}^{d}$ whose coordinates have greatest common divisor
$1$, there is a linear map from $\mathbb{Z}^{d}$ to $\mathbb{Z}^{d-1}$ which
has full rank with null space generated by $\mathbf{b}$, and maps a grid into
another grid with similar size.

######  Lemma 4.4.

Let $d\geq 2$ be a positive integer, and $N_{1},N_{2},\dots,N_{d}$ be positive
integers. Suppose that $\mathbf{b}=(b_{1},\dots,b_{d})\in\mathbb{Z}^{d}$ is a
nonzero vector satisfying that $\operatorname{gcd}(b_{1},\dots,b_{d})=1$ and
$|b_{i}|\leq N_{i}$ for all $1\leq i\leq d$. Then there exists a linear map
$f_{\mathbf{b}}:\mathbb{Z}^{d}\to\mathbb{Z}^{d-1}$ so that the following two
conditions holds.

  1. (1)

For any $\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{Z}^{d}$,
$f_{\mathbf{b}}(\mathbf{x}_{1})=f_{\mathbf{b}}(\mathbf{x}_{2})$ if and only if
$\mathbf{x}_{1}-\mathbf{x}_{2}=k\mathbf{b}$ for some $k\in\mathbb{Z}$.

  2. (2)

There exist positive integers
$N_{1}^{*},N_{2}^{*},\dots,N_{d-1}^{*}\geq\min_{1\leq i\leq d}N_{i}$ so that

$\frac{1}{2}N_{1}\cdots N_{d}\cdot\left(\max_{1\leq i\leq
d}\frac{|b_{i}|}{N_{i}}\right)\leq N_{1}^{*}\cdots N_{d-1}^{*}\leq
2^{d^{2}}N_{1}\cdots N_{d}\cdot\left(\max_{1\leq i\leq
d}\frac{|b_{i}|}{N_{i}}\right)$ (4.1)

and
$f_{\mathbf{b}}([N_{1}]\times\cdots\times[N_{d}])\subseteq[N_{1}^{*}]\times\cdots\times[N_{d-1}^{*}]$.

###### Proof.

We may write $f_{\mathbf{b}}(\mathbf{x})=M\mathbf{x}+\mathbf{v}$ for some
$M\in\mathbb{Z}^{(d-1)\times d}$ and $\mathbf{v}\in\mathbb{Z}^{d-1}$ to be
chosen later. Condition (1) says that $M$ is full rank, with null space
generated by $\mathbf{b}$.

We regard the rows of $M$ as vectors
$\mathbf{r}_{1},\dots,\mathbf{r}_{d-1}\in\mathbb{Z}^{d}$. For each $1\leq
j\leq d-1$, if we write $\mathbf{r}_{j}=(r_{j1},\dots,r_{jd})$, then we define
$\mathbf{r}^{*}_{j}:=(r_{j1}N_{1},\dots,r_{jd}N_{d})\in\Lambda$ where
$\Lambda:=N_{1}\mathbb{Z}\times\cdots\times N_{d}\mathbb{Z}$. Condition (1) is
equivalent to saying that the vectors $\mathbf{r}_{j}$ in $\mathbb{Z}^{d}$ for
$1\leq j\leq d-1$ are linearly independent and
$\mathbf{r}_{j}\cdot\mathbf{b}=0$ for all $1\leq j\leq d-1$. In terms of
$\mathbf{r}^{*}_{j}$, this is equivalent to
$\mathbf{r}^{*}_{j}\cdot\mathbf{b}^{*}=0$ for
$\mathbf{b}^{*}:=(\frac{b_{1}}{N_{1}},\dots,\frac{b_{d}}{N_{d}})$, and
$\mathbf{r}^{*}_{1},\dots,\mathbf{r}^{*}_{d-1}$ are linearly independent
vectors. The following claim allows us to find these vectors whose product of
$\ell_{2}$-norms is small.

######  Claim 1.

There exists linearly independent vectors
$\mathbf{r}^{*}_{1},\dots,\mathbf{r}^{*}_{d-1}\in\Lambda$ that satisfy
$\mathbf{r}^{*}_{j}\cdot\mathbf{b}^{*}=0$ for each $1\leq j\leq d-1$, and

$\prod_{j=1}^{d-1}\|\mathbf{r}^{*}_{j}\|_{2}\leq
2^{\frac{(d-1)(d-2)}{4}}\cdot\|\mathbf{b}^{*}\|_{2}N_{1}N_{2}\cdots N_{d},$
(4.2)

###### Proof of Claim 1.

Consider the subspace of $\mathbb{R}^{d}$ defined by
$\langle\mathbf{b}^{*}\rangle^{\perp}:=\\{\mathbf{x}\in\mathbb{R}^{d}:\mathbf{x}\cdot\mathbf{b}^{*}=0\\}$
which has dimension $d-1$. The intersection
$\Lambda^{*}:=\Lambda\cap\langle\mathbf{b}^{*}\rangle^{\perp}$ is a lattice in
$\langle\mathbf{b}^{*}\rangle^{\perp}$. As $\mathbf{b}\in\mathbb{Z}^{d}$ is a
nonzero vector with integer entries, there exist linearly independent vectors
$\mathbf{r}_{1},\dots,\mathbf{r}_{d-1}\in\mathbb{Z}^{d}$ that satisfy
$\mathbf{r}_{j}\cdot\mathbf{b}=0$ for each $1\leq j\leq d-1$. Hence we can
find $d-1$ linearly independent vectors
$\mathbf{r}_{j}^{*}\in\Lambda\cap\langle\mathbf{b}^{*}\rangle^{\perp}$ defined
by $\mathbf{r}_{j}^{*}=(r_{j1}N_{1},\dots,r_{jd}N_{d})$ where
$\mathbf{r}_{j}=(r_{j1},\dots,r_{jd})$ for $1\leq j\leq d-1$. The linear
independence of $\\{\mathbf{r}_{j}^{*}\\}_{j=1}^{d-1}$ follows from the linear
independence of $\\{\mathbf{r}_{j}\\}_{j=1}^{d-1}$, while
$\mathbf{r}_{j}^{*}\cdot\mathbf{b}^{*}=\mathbf{r}_{j}\cdot\mathbf{b}=0$ for
each $1\leq j\leq d-1$. Thus we conclude that $\Lambda^{*}$ is a
$(d-1)$-dimensional lattice.

We next consider some geometric properties of $\Lambda^{*}$ as a subset of the
$(d-1)$-dimensional Euclidean space $\langle\mathbf{b}^{*}\rangle^{\perp}$.
Let $P$ be a subset of $\langle\mathbf{b}^{*}\rangle^{\perp}$ that is
symmetric about the origin and convex. Now we consider the set
$X:=\\{\mathbf{p}+a\mathbf{b}^{*}:\mathbf{p}\in
P,a\in(-1/\|\mathbf{b}\|_{2}^{2},1/\|\mathbf{b}\|_{2}^{2})\\}$. We could
equivalently phrase this as: $X$ contains all the point $\mathbf{x}$ that
satisfies $\mathbf{x}\cdot\mathbf{b}^{*}\in(-1,1)$, and the projection of
$\mathbf{x}$ onto the hyperspace $\langle\mathbf{b}^{*}\rangle$ is in $P$.
Therefore from this geometric interpretation we know that
$V_{d}(X)=\frac{2}{\|\mathbf{b}\|_{2}}V_{d-1}(P)$ where $V_{d}$ denotes the
$d$-dimensional volume. Meanwhile, we see that as $P$ and
$\\{a\mathbf{b}^{*}:a\in(-1/\|\mathbf{b}\|_{2}^{2},1/\|\mathbf{b}\|_{2}^{2})\\}$
are both convex and symmetric about the origin, their Minkowski sum $X$ is
also convex and symmetric about the origin. By Minkowski’s theorem, Lemma 4.1,
if $V_{d}(X)>2^{d}\det(\Lambda)$, then there is a nonzero point
$\mathbf{x}\in\Lambda\cap X$. Note that any point $\mathbf{x}\in\Lambda$
satisfies that $\mathbf{x}\cdot\mathbf{b}^{*}$ is an integer, while any point
$\mathbf{b}\in X$ satisfies that $\mathbf{b}\cdot\mathbf{b}^{*}\in(-1,1)$, we
know that if $\mathbf{x}\in\Lambda\cap X$, then
$\mathbf{x}\in\langle\mathbf{b}^{*}\rangle^{\perp}$. Note that
$\Lambda^{*}=\Lambda\cap\langle\mathbf{b}^{*}\rangle^{\perp}$ and
$P=X\cap\langle\mathbf{b}^{*}\rangle^{\perp}$, this means
$\mathbf{x}\in\Lambda^{*}\cap P$. In summary, if
$V_{d-1}(P)>2^{d-1}\|\mathbf{b}\|_{2}\det(\Lambda)=2^{d-1}\|\mathbf{b}\|_{2}N_{1}\cdots
N_{d}$, then $P\cap\Lambda^{*}$ contains a nonzero point.

Therefore we may apply Corollary 4.3 with dimension $d-1$, lattice $\Gamma$,
and $V_{0}=2^{d-1}\|\mathbf{b}\|_{2}N_{1}\cdots N_{d}$, and we obtain that
there exists a basis $\mathbf{r}_{1}^{*},\dots,\mathbf{r}_{d-1}^{*}$ such that

$\prod_{j=1}^{d-1}\|\mathbf{r}^{*}_{j}\|_{2}\leq
2^{\frac{(d-1)(d-2)}{4}}\cdot\|\mathbf{b}^{*}\|_{2}N_{1}N_{2}\cdots N_{d},$

so we have these linearly independent vectors as expected. ∎

From the set of vectors $\\{\mathbf{r}_{j}^{*}\\}_{j=1}^{d-1}$ whose existence
is guaranteed by Claim 1, we obtain the set of vectors
$\\{\mathbf{r}_{j}\\}_{j=1}^{d-1}$, which are the row vectors of $M$. Then
condition (1) is satisfied, since they are $d-1$ linearly independent vectors
in $\mathbb{Z}^{d}$ and satisfy that $\mathbf{r}_{j}^{*}\cdot\mathbf{b}^{*}=0$
for each $1\leq j\leq d-1$.

For each $1\leq j\leq d-1$, we know that for any
$\mathbf{x}=(x_{1},\dots,x_{d})\in\mathbb{Z}^{d}$,
$(M\mathbf{x})_{j}=\mathbf{r}_{j}\cdot\mathbf{x}$. Note that
$\mathbf{r}_{j}=(r_{j1},\dots,r_{jd})$. We have that whenever
$\mathbf{x}\in[N_{1}]\times\cdots\times[N_{d}]$,

$|\mathbf{r}_{j}\cdot\mathbf{x}|=\left|\sum_{i=1}^{d}r_{ji}x_{i}\right|\leq\sum_{i=1}^{d}|r_{ji}N_{i}|=\|\mathbf{r}^{*}_{j}\|_{1}.$
(4.3)

Let $N_{j}^{*}=3\|\mathbf{r}^{*}_{j}\|_{1}$ and
$\mathbf{v}=(2\|\mathbf{r}^{*}_{j}\|_{1})_{j=1}^{d-1}$. Observe that this
choice of parameters together with (4.3) ensures that
$f_{\mathbf{b}}([N_{1}]\times\cdots\times[N_{d}])\subseteq[N_{1}^{*}]\times\cdots\times[N_{d-1}^{*}]$.
For each $1\leq j\leq d-1$, as $\mathbf{r}_{j}\in\mathbb{Z}^{d}$ is nonzero,
we have $r_{ji}$ is nonzero for some $i$, and hence
$N^{*}_{j}\geq\|\mathbf{r}^{*}_{j}\|_{1}\geq|r_{ji}N_{i}|\geq
N_{i}\geq\min_{1\leq i\leq d}N_{i}$.

Also, by condition (1), elements in $f_{\mathbf{b}}^{-1}(\mathbf{x}^{*})$
differ by multiples of $\mathbf{b}$. Note that there are at most
$\frac{1}{\|\mathbf{b}^{*}\|}+1\leq\frac{2}{\|\mathbf{b}^{*}\|}$ such elements
in $[N_{1}]\times\cdots\times[N_{d}]$ for each fixed
$\mathbf{x}^{*}\in[N_{1}^{*}]\times\cdots\times[N_{d-1}^{*}]$. We have

$\frac{2}{\|\mathbf{b}^{*}\|}N_{1}^{*}\cdots N_{d-1}^{*}\geq N_{1}\cdots
N_{d}.$

It remains to show the other half of the inequality in (4.1). With $N_{j}^{*}$
as above, we have

$N_{1}^{*}\cdots
N_{d-1}^{*}=\prod_{j=1}^{d-1}3\|\mathbf{r}^{*}_{j}\|_{1}\leq\prod_{j=1}^{d-1}3\sqrt{d}\|\mathbf{r}^{*}_{j}\|_{2}\leq
3^{d-1}(\sqrt{d})^{d-1}2^{\frac{(d-1)(d-2)}{4}}\|\mathbf{b}^{*}\|_{2}N_{1}N_{2}\cdots
N_{d}.$

Using that $\|\mathbf{b}^{*}\|_{2}\leq\sqrt{d}\|\mathbf{b}^{*}\|_{\infty}$, we
have

$3^{d-1}(\sqrt{d})^{d-1}2^{\frac{(d-1)(d-2)}{4}}\|\mathbf{b}^{*}\|_{2}N_{1}N_{2}\cdots
N_{d}\leq 2^{d^{2}}N_{1}N_{2}\cdots N_{d}\|\mathbf{b}^{*}\|_{\infty},$

so condition (2) is also satisfied. Here we use that
$3^{d-1}(\sqrt{d})^{d}2^{\frac{(d-1)(d-2)}{4}}\leq 2^{d^{2}}$ for $d\geq 2$.∎

For any
$\mathbf{b}=(b_{1},\dots,b_{d})\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$
whose entries are not coprime, we may apply the lemma above to
$\mathbf{b}/\operatorname{gcd}(b_{1},\dots,b_{d})$ instead. This gives the
following corollary.

######  Corollary 4.5.

Let $d\geq 2$ be an integer, and $N_{1},N_{2},\dots,N_{d}$ be positive
integers. Suppose that $\mathbf{b}=(b_{1},\dots,b_{d})\in\mathbb{Z}^{d}$ is a
nonzero vector satisfying that $\lambda=\lambda(\mathbf{b}):=\max_{1\leq i\leq
d}\frac{|b_{i}|}{\operatorname{gcd}(b_{1},\dots,b_{d})N_{i}}\leq 1$. Then
there exists a linear map $f_{\mathbf{b}}\in\mathbb{Z}^{(d-1)\times d}$ so
that the following two conditions holds.

  1. (1)

For any $\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{Z}^{d}$,
$f_{\mathbf{b}}(\mathbf{x}_{1})=f_{\mathbf{b}}(\mathbf{x}_{2})$ if and only if
$\mathbf{x}_{1}-\mathbf{x}_{2}=k\mathbf{b}$ for some $k\in\mathbb{Q}$.

  2. (2)

There exist positive integers
$N_{1}^{*},N_{2}^{*},\dots,N_{d-1}^{*}\geq\min_{1\leq i\leq d}N_{i}$ so that
$\frac{1}{2}\leq\frac{N_{1}^{*}\cdots N_{d-1}^{*}}{\lambda N_{1}\cdots
N_{d}}\leq 2^{d^{2}}$ and
$f_{\mathbf{b}}([N_{1}]\times\cdots\times[N_{d}])\subseteq[N_{1}^{*}]\times\cdots\times[N_{d-1}^{*}]$.

The linear map in the corollary above is the main tool for reduction from
$\mathbb{Z}^{d}$ to $\mathbb{Z}^{d-1}$. We have the following simple relation
between $f_{\mathbf{b}}$ and $U^{d}(X,\mathbf{b},s)$.

######  Lemma 4.6.

Let $d\geq 2$ be an integer, and $N_{1},\dots,N_{d}$ be positive integers. Let
$X\subseteq[N_{1}]\times\cdots\times[N_{d}]$, let
$\mathbf{b}=(b_{1},\dots,b_{d})\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$
with $\lambda=\lambda(\mathbf{b}):=\max_{1\leq i\leq
d}\frac{|b_{i}|}{\operatorname{gcd}(b_{1},\dots,b_{d})N_{i}}\leq 1$. Let
$s\leq\min_{i}N_{i}$ be a positive integer. Suppose that
$f_{\mathbf{b}}:\mathbb{Z}^{d}\to\mathbb{Z}^{d-1}$ is a linear map satisfying
(1) in Corollary 4.5. Then each element in
$f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s))$ has at least $s$ and at most
$\frac{2}{\lambda}$ preimages under $f_{\mathbf{b}}$ in
$U^{d}(X,\mathbf{b},s)$.

###### Proof.

as $f_{\mathbf{b}}$ satisfies (1), we know that if
$f_{\mathbf{b}}(\mathbf{x}_{1})=f_{\mathbf{b}}(\mathbf{x}_{2})$, then
$\mathbf{x}_{1}-\mathbf{x}_{2}$ is a multiple of
$\mathbf{b}/\operatorname{gcd}(b_{1},\dots,b_{d})$. From the definition of
$\lambda$, we see that each element in $\mathbb{Z}^{d-1}$ has at most
$\frac{1}{\lambda}+1\leq\frac{2}{\lambda}$ preimages in
$U^{d}(X,\mathbf{b},s)\subseteq[N_{1}]\times\cdots\times[N_{d}]$.

Note that each element in $U^{d}(X,\mathbf{b},s)$ is in a residue class mod
$\mathbf{b}$ of size at least $s$. Again by condition (1), elements in the
residue class mod $\mathbf{b}$ get mapped to the same element by
$f_{\mathbf{b}}$. Therefore, every element in
$f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s))$ has at least $s$ preimages. ∎

Using Lemma 4.6 we derive the following lemma, which bounds the size of the
intersection of two $U^{d}$ sets.

######  Lemma 4.7.

Let $d\geq 2$ be a positive integer, and $N_{1},\dots,N_{d}$ be positive
integers. Let $X\subseteq[N_{1}]\times\cdots\times[N_{d}]$, let
$\mathbf{b}=(b_{1},\dots,b_{d})\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}$
with $\lambda=\lambda(\mathbf{b}):=\max_{1\leq i\leq
d}\frac{|b_{i}|}{\operatorname{gcd}(b_{1},\dots,b_{d})N_{i}}\leq 1$. Let
$s^{*}\leq s\leq\min_{i}N_{i}$ be positive integers. Suppose that
$f_{\mathbf{b}}:\mathbb{Z}^{d}\to\mathbb{Z}^{d-1}$ satisfies condition (1) in
Corollary 4.5, and $\mathbf{b}^{\prime}\in\mathbb{Z}^{d}$ satisfies that
$f_{\mathbf{b}}(\mathbf{b}^{\prime})\neq f_{\mathbf{b}}(\mathbf{0})$. Then

$|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|\leq\frac{s^{*}-1}{s}|U^{d}(X,\mathbf{b}^{\prime},s)|+\frac{2}{\lambda}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}),s^{*})|.$
(4.4)

###### Proof.

For simplicity let $X_{1}=U^{d}(X,\mathbf{b},s)$. Note that
$f_{\mathbf{b}}(X_{1})$ is a subset of $\mathbb{Z}^{d-1}$.

Partition the set $U^{d}(X,\mathbf{b}^{\prime},s)$ into nonempty residue
classes mod $\mathbf{b}^{\prime}$. By definition, we know that each such
residue class contains at least $s$ elements, so there are at most
$\frac{1}{s}|U^{d}(X,\mathbf{b}^{\prime},s)|$ such residue classes. For each
such residue class, there are two cases:

  * •

the residue class contains at most $s^{*}-1$ elements in $X_{1}\cap
U^{d}(X,\mathbf{b}^{\prime},s)$;

  * •

the residue class contains at least $s^{*}$ elements in $X_{1}\cap
U^{d}(X,\mathbf{b}^{\prime},s)$.

We next upper bound the size of $X_{1}\cap U^{d}(X,\mathbf{b}^{\prime},s)$.
The number of elements in $X_{1}\cap U^{d}(X,\mathbf{b}^{\prime},s)$ contained
in a residue class of the first case is at most
$\frac{s^{*}-1}{s}|U^{d}(X,\mathbf{b}^{\prime},s)|$. It remains to estimate
the number of elements contained in a residue class of the second case.

We first show that, if $\mathbf{x}$ is an element of $X_{1}\cap
U^{d}(X,\mathbf{b}^{\prime},s)$, whose residue class mod $\mathbf{b}^{\prime}$
contains at least $s^{*}$ elements in $X_{1}\cap
U^{d}(X,\mathbf{b}^{\prime},s)$, then

$f_{\mathbf{b}}(\mathbf{x})\in
U^{d-1}(f_{\mathbf{b}}(X_{1}),f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}),s^{*}).$
(4.5)

Let $I=\\{\mathbf{x}_{1},\dots,\mathbf{x}_{k}\\}$ be the residue class mod
$\mathbf{b}^{\prime}$ of $X_{1}\cap U^{d}(X,\mathbf{b}^{\prime},s)$ with
$\mathbf{x}=\mathbf{x}_{1}$. Suppose that $I$ contains at least $s^{*}$
elements. Note that if $\mathbf{x}_{i}=t\mathbf{b}^{\prime}+\mathbf{x}_{j}$
for some integer $t\neq 0$, then
$f_{\mathbf{b}}(\mathbf{x}_{i})=f_{\mathbf{b}}(\mathbf{x}_{j})+t(f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}))$.
As $f_{\mathbf{b}}(\mathbf{b}^{\prime})\neq f_{\mathbf{b}}(\mathbf{0})$, we
know that $f_{\mathbf{b}}(I)=\\{f_{\mathbf{b}}(\mathbf{x}_{i}):1\leq i\leq
k\\}$ consists of $k\geq s^{*}$ distinct elements, whose pairwise differences
are multiples of
$(f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}))$. In
particular, there are at least $k\geq s^{*}$ elements in
$f_{\mathbf{b}}(X_{1})$ that are congruent to $f_{\mathbf{b}}(\mathbf{x})$ mod
$(f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}))$. This
proves (4.5).

Note that by Lemma 4.6, each element in
$U^{d-1}(f_{\mathbf{b}}(X_{1}),f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}),s^{*})$
has at most $\frac{2}{\lambda}$ preimages in $X_{1}\cap
U^{d}(X,\mathbf{b}^{\prime},s)$. Therefore, the number of elements contained
in a residue class of the second case is at most
$\frac{2}{\lambda}|U^{d-1}(f_{\mathbf{b}}(X_{1}),f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}),s^{*})|$.
Putting these together, we have (4.4). ∎

######  Lemma 4.8.

Let $d\geq 2$ be a positive integer and $N_{1},\dots,N_{d},s$ be positive
integers with $\min_{1\leq i\leq d}N_{i}>s\geq 2$. Let
$X\subseteq[N_{1}]\times\cdots\times[N_{d}]$,
$\lambda_{0}\in(0,\frac{1}{s-1})$ and
$B\subseteq[-\frac{N_{1}}{s-1},\frac{N_{1}}{s-1}]\times\cdots\times[-\frac{N_{d}}{s-1},\frac{N_{d}}{s-1}]$
such that each $(b_{1},\dots,b_{d})\in B$ is a nonzero integer point
satisfying that $\lambda_{0}\leq\max_{1\leq i\leq
d}\frac{|b_{i}|}{\operatorname{gcd}(b_{1},\dots,b_{d})N_{i}}$. Let
$\mathbf{b}$ be an integer point in $B$, and
$f_{\mathbf{b}}:\mathbb{Z}^{d}\to\mathbb{Z}^{d-1}$ be a map satisfying
condition (1) in Corollary 4.5, and $s^{*}\leq s$ be a positive integer. Then
we have

$\begin{split}\sum_{\mathbf{b}^{\prime}\in B}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|&\leq\frac{4}{s\lambda_{0}}|U^{d}(X,\mathbf{b},s)|+\frac{s^{*}-1}{s}\sum_{\mathbf{b}^{\prime}\in
B}|U^{d}(X,\mathbf{b}^{\prime},s)|\\\
&\quad+\frac{12}{s\lambda_{0}^{2}}\sum_{\mathbf{b}^{*}\in\mathbb{Z}^{d-1}\setminus\\{\mathbf{0}\\}}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),\mathbf{b}^{*},s^{*})|.\end{split}$
(4.6)

###### Proof.

Let us denote $\mathbf{b}=(b_{1},\dots,b_{d})$. We first give an upper bound
on the number of elements $\mathbf{b}^{\prime}\in B$ with
$f_{\mathbf{b}}(\mathbf{b}^{\prime})=f_{\mathbf{b}}(\mathbf{0})$. By condition
(1), we know that all such $\mathbf{b}^{\prime}$ are given by
$k\mathbf{b}/\operatorname{gcd}(b_{1},\dots,b_{d})$ for $k\in\mathbb{Z}$. If
$k\mathbf{b}/\operatorname{gcd}(b_{1},\dots,b_{d})$ is contained in
$B\subseteq[-\frac{N_{1}}{s-1},\frac{N_{1}}{s-1}]\times\cdots\times[-\frac{N_{d}}{s-1},\frac{N_{d}}{s-1}]$,
then we know that
$\frac{|k|\cdot|b_{i}|}{\operatorname{gcd}(b_{1},\dots,b_{d})}\leq\frac{N_{i}}{s-1}$
for all $i$. Hence each choice of $k$ with
$k\mathbf{b}/\operatorname{gcd}(b_{1},\dots,b_{d})\in B$ satisfies that

$|k|\leq\min_{1\leq i\leq
d}\frac{N_{i}\operatorname{gcd}(b_{1},\dots,b_{d})}{|b_{i}|(s-1)}\leq\frac{1}{(s-1)\lambda_{0}}\leq\frac{2}{s\lambda_{0}}.$

Therefore, the number of such $\mathbf{b}^{\prime}\in B$ is at most
$\frac{4}{s\lambda_{0}}$ (noting that $k\neq 0$). Thus we have

$\sum_{\mathbf{b}^{\prime}\in
B:f_{\mathbf{b}}(\mathbf{b}^{\prime})=f_{\mathbf{b}}(\mathbf{0})}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|\leq\sum_{\mathbf{b}^{\prime}\in
B:f_{\mathbf{b}}(\mathbf{b}^{\prime})=f_{\mathbf{b}}(\mathbf{0})}|U^{d}(X,\mathbf{b},s)|\leq\frac{4}{s\lambda_{0}}|U^{d}(X,\mathbf{b},s)|.$
(4.7)

Now we consider the summation over all $\mathbf{b}^{\prime}\in B$ with
$f_{\mathbf{b}}(\mathbf{b}^{\prime})\neq f_{\mathbf{b}}(\mathbf{0})$. For each
such $\mathbf{b}^{\prime}$, by Lemma 4.7,

$|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|\leq\frac{s^{*}-1}{s}|U^{d}(X,\mathbf{b}^{\prime},s)|+\frac{2}{\lambda}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}),s^{*})|.$
(4.8)

Observe that

$\sum_{\mathbf{b}^{\prime}\in B:f_{\mathbf{b}}(\mathbf{b}^{\prime})\neq
f_{\mathbf{b}}(\mathbf{0})}|U^{d}(X,\mathbf{b}^{\prime},s)|\leq\sum_{\mathbf{b}^{\prime}\in
B}|U^{d}(X,\mathbf{b}^{\prime},s)|.$

Now, note that $\mathbf{b}^{\prime}\in
B\subseteq[-\frac{N_{1}}{s-1},\frac{N_{1}}{s-1}]\times\cdots\times[-\frac{N_{d}}{s-1},\frac{N_{d}}{s-1}]$.
Thus, by a similar argument as above, for each
$\mathbf{b}^{*}\in\mathbb{Z}^{d-1}\setminus\\{\mathbf{0}\\}$, the number of
$\mathbf{b}^{\prime}\in B$ with
$f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0})=\mathbf{b}^{*}$
is at most $\frac{2}{(s-1)\lambda_{0}}+1\leq\frac{6}{s\lambda_{0}}$. Therefore
we have

$\sum_{\mathbf{b}^{\prime}\in B:f_{\mathbf{b}}(\mathbf{b}^{\prime})\neq
f_{\mathbf{b}}(\mathbf{0})}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),f_{\mathbf{b}}(\mathbf{b}^{\prime})-f_{\mathbf{b}}(\mathbf{0}),s^{*})|\leq\frac{6}{s\lambda_{0}}\cdot\sum_{\mathbf{b}^{*}\in\mathbb{Z}\setminus
0}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),\mathbf{b}^{*},s^{*})|.$

We sum (4.8) over all $\mathbf{b}^{\prime}\in B$ with
$f_{\mathbf{b}}(\mathbf{b}^{\prime})\neq f_{\mathbf{b}}(\mathbf{0})$.
Combining it with (4.7), we have

$\begin{split}\sum_{\mathbf{b}^{\prime}\in B}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|&=\sum_{\mathbf{b}^{\prime}\in
B:f_{\mathbf{b}}(\mathbf{b}^{\prime})=f_{\mathbf{b}}(\mathbf{0})}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|\\\ &\quad+\sum_{\mathbf{b}^{\prime}\in
B:f_{\mathbf{b}}(\mathbf{b}^{\prime})\neq
f_{\mathbf{b}}(\mathbf{0})}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|\\\
&\leq\frac{4}{s\lambda_{0}}|U^{d}(X,\mathbf{b},s)|+\frac{s^{*}-1}{s}\sum_{\mathbf{b}^{\prime}\in
B}|U^{d}(X,\mathbf{b}^{\prime},s)|\\\
&\quad+\frac{12}{s\lambda_{0}^{2}}\sum_{\mathbf{b}^{*}\in\mathbb{Z}^{d-1}\setminus\\{\mathbf{0}\\}}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),\mathbf{b}^{*},s^{*})|.\end{split}$
(4.9)

This establishes the desired inequality (4.6). ∎

Lemma 4.8 is a useful bound for those $\mathbf{b}$ for which
$\lambda(\mathbf{b})$ (as defined in Lemma 4.7) is not too small. The
following lemma shows that there are not many choices of $\mathbf{b}$ for
which $\lambda(\mathbf{b})$ is small.

######  Lemma 4.9.

Let $d\geq 2$ be a positive integer, $n_{1},\dots,n_{d}\in\mathbb{N}$ and
$\epsilon\in(0,1)$. If $\frac{1}{\epsilon}\leq n_{i}$ for all $1\leq i\leq d$,
then there are at most $6^{d}\epsilon n_{1}\cdots n_{d}$ nonzero points
$(b_{1},b_{2},\dots,b_{d})\in[-n_{1},n_{1}]\times\cdots\times[-n_{d},n_{d}]$
with $|b_{i}/\operatorname{gcd}(b_{1},\dots,b_{d})|\leq\epsilon n_{i}$ for all
$1\leq i\leq d$.

###### Proof.

For each $i$, the number of tuples with $b_{i}=0$ is given by

$\prod_{j\neq i}(2n_{j}+1)\leq 3^{d}n_{1}\cdots n_{d}\cdot\frac{1}{n_{i}}\leq
3^{d}\epsilon n_{1}\cdots n_{d}.$

Hence the number of such tuples with at least one zero entry is at most
$3^{d}d\epsilon n_{1}\cdots n_{d}$.

We may next only consider the tuples with nonzero entries. Suppose that
$\operatorname{gcd}(b_{1},\dots,b_{d})=k$. For any given $k$, we know that
$b_{i}^{\prime}=b_{i}/k$ satisfies that $|b_{i}^{\prime}|\leq n_{i}/k$. From
the problem condition, we further know that $|b_{i}^{\prime}|\leq\epsilon
n_{i}$. Hence when $k$ is fixed, the number of such tuples is at most
$(2\epsilon)^{d}n_{1}\cdots n_{d}$ if $k\leq\frac{1}{\epsilon}$, and
$(2/k)^{d}n_{1}\cdots n_{d}$ if $k>\frac{1}{\epsilon}$. Thus summing over $k$,
we know that the number of such tuples $(b_{1},b_{2},\dots,b_{d})$ is at most

$\sum_{1\leq k\leq\frac{1}{\epsilon}}2^{d}\epsilon^{d}n_{1}\cdots
n_{d}+\sum_{\frac{1}{\epsilon}<k}2^{d}\frac{n_{1}\cdots n_{d}}{k^{d}}\leq
2^{d}\epsilon^{d-1}n_{1}\cdots n_{d}+2^{d}\cdot 2\epsilon^{d-1}n_{1}\cdots
n_{d}=3\cdot 2^{d}\epsilon^{d-1}n_{1}\cdots n_{d}.$

Therefore the total number of such tuples is at most

$3^{d}d\epsilon n_{1}\cdots n_{d}+3\cdot 2^{d}\epsilon^{d-1}n_{1}\cdots
n_{d}\leq 6^{d}\epsilon n_{1}\cdots n_{d}.$

∎

If $s\geq 2$ and $U^{d}(X,\mathbf{b},s)$ is nonempty, then
$\mathbf{b}\in[-\frac{N_{1}}{s-1},\frac{N_{1}}{s-1}]\times\cdots\times[-\frac{N_{d}}{s-1},\frac{N_{d}}{s-1}]$.
In the lemma above we pick $n_{i}=\frac{N_{i}}{s-1}$. Then the lemma above
gives an upper bound on the number of nonzero points $\mathbf{b}$ whose
$\lambda$ value (as defined in Lemma 4.7) is at most $\frac{\epsilon}{s-1}$.

Finally, we need the following lemma.

######  Lemma 4.10.

Let $X$ be a set of size $m>0$. Let $\\{A_{i}\\}_{i\in I}$ be a family of
subsets of $X$ over indices $i\in I$. Then we have

$\sum_{i,j\in I}|A_{i}\cap A_{j}|\geq\frac{1}{m}\left(\sum_{i\in
I}|A_{i}|\right)^{2}.$

###### Proof.

We count the number of tuples in $T=\\{(x,i,j)\in X\times I\times I:x\in
A_{i}\cap A_{j}\\}$. Note that if we fix $i$ and $j$, the number of choices
for $x$ is exactly $|A_{i}\cap A_{j}|$. Hence we have $|T|=\sum_{i,j\in
I}|A_{i}\cap A_{j}|.$

For each $x\in X$, let $m_{x}=|\\{i\in I:x\in A_{i}\\}|$, the number of sets
$A_{i}$ that contain $x$. First we see that $\sum_{x\in X}m_{x}=\sum_{i\in
I}|A_{i}|$. Moreover, when counting $X$, once we fix $x\in X$, the number of
choices for $(i,j)$ is $m_{x}^{2}$, so we have $|T|=\sum_{x\in X}m_{x}^{2}.$
By the Cauchy-Schwarz inequality, we have

$m\sum_{i,j\in I}|A_{i}\cap A_{j}|=m|T|=|X|\left(\sum_{x\in
X}m_{x}^{2}\right)\geq\left(\sum_{x\in X}m_{x}\right)^{2}=\left(\sum_{i\in
I}|A_{i}|\right)^{2}.$

This gives the desired inequality. ∎

We next prove Lemma 3.5. The proof is by induction on $d$. The following
proposition handles the base case $d=1$ and is due to Matoušek and Spencer
[8].

######  Proposition 4.11 (Proposition 4.1 in [8]).

There exists an absolute constant $C$ such that the following holds. For
positive integers $N$ and $m$, if $X\subseteq[N]$ is a subset of size $m$ and
$s\geq 5\sqrt{m}$, then

$\sum_{b\in\mathbb{Z}\setminus\\{0\\}}|U^{1}(X,b,s)|\leq
C\frac{N^{\frac{1}{2}}m^{\frac{3}{2}}}{s}.$

Now we have all the tools to set up the proof of Lemma 3.5. We first describe
the proof idea. Let us consider a fixed $d\geq 2$ with the induction
hypothesis that the statement holds for $d-1$. Since we are to run an
induction, the crux of the proof is to apply the induction hypothesis.
Corollary 4.5 enables us to project the $d$-dimensional set
$X\subseteq[N_{1}]\times\cdots\times[N_{d}]$ to a $(d-1)$-dimensional set
$X^{*}\subseteq[N_{1}^{*}]\times\cdots\times[N_{d-1}^{*}]$ for some set
$X^{*}$ and integers $N_{j}^{*}$ for $1\leq j\leq d-1$. Let
$\rho=\frac{|X|}{N_{1}\cdots N_{d}}$ and
$\rho^{*}=\frac{|X^{*}|}{N_{1}^{*}\cdots N_{d-1}^{*}}$ be the densities of the
sets in the grids that they are subsets of. Fix $\epsilon=\rho^{\gamma}$ where
$\gamma$ is chosen to be the exponent of $\rho$ in (3.11). As Lemma 4.9 says
that only $O_{d}(\epsilon)$-fraction of $\mathbf{b}$’s satisfy
$\lambda(\mathbf{b})<\frac{\epsilon}{s}$, it allows us to only focus on
$\mathbf{b}$ with $\lambda(\mathbf{b})$ roughly $\frac{1}{s}$, off by a factor
of at most $O_{d}(\epsilon)=O_{d}(\rho^{\gamma})$. It follows that we can
estimate both $N_{1}^{*}\cdots N_{d-1}^{*}$ and
$X^{*}=f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s))$ within a factor of
$\rho^{O_{d}(\gamma)}$ by applying Corollary 4.5 and Lemma 4.6 respectively.
Thus we can estimate $\rho^{*}$ within a factor of $\rho^{O_{d}(\gamma)}$.
Finally we would like to apply Lemma 4.8 and combine that with Lemma 4.10 to
get the desired bound. Together these two lemmas give us an upper bound on the
sum of the sizes of the $U^{d}(X,\mathbf{b},s)$ over all $\mathbf{b}$ in a
carefully chosen set $B\subseteq\mathbb{Z}^{d}$ in which the $i$-th coordinate
is at most $N_{i}/(s-1)$ in absolute value for each $i$.

In the bound in Lemma 4.8, it is not hard to see that the first term on the
right hand side is of lower order. By choosing $s^{*}=s\rho^{\gamma}$, we can
save a factor of $\rho^{\gamma}$ in the second term. For the third term, we
apply the induction hypothesis to save a factor of $(\rho^{*})^{\gamma^{*}}$
(where the bound is expressed in terms of $|X^{*}|$, $N_{1}^{*}\cdots
N_{d-1}^{*}$ and $\rho^{*}$). Since we can estimate each of them within a
factor of $\rho^{O_{d}(\gamma)}$, we conclude that we save a factor of
$\rho^{\gamma^{*}-O_{d}(\gamma)}$ in the third term. We can make $\gamma$
small enough so that $\gamma^{*}-O_{d}(\gamma)\geq\gamma$. In summary we save
a factor of $O_{d}(\rho^{\gamma})$ in all three terms, which is exactly what
we need in Lemma 3.5.

We next recall the statement of Lemma 3.5 and prove it. See 3.5

###### Proof of Lemma 3.5.

Let $C_{0}>1$ be an absolute constant that satisfies Proposition 4.11. We
prove by induction on $d$ that the statement holds for $C=C_{0}\cdot
5^{d}\cdot 2^{d^{3}}$. We may assume $N_{1}=\min_{1\leq i\leq d}N_{i}$.

If $m=0$ or if $N_{1}=\cdots=N_{d}=1$, then the statement trivially holds.
Hence we may assume that $m\geq 1$ and $N_{1}\cdots N_{d}>1$. Therefore,
noting that $\frac{1}{d+1}-\frac{\delta}{4^{d}(d+1)}>0$, we have that $s$
satisfies

$s\geq(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}=(N_{1}\cdots
N_{d})^{\frac{1}{d+1}-\frac{\delta}{4^{d}(d+1)}}m^{\frac{\delta}{4^{d}(d+1)}}\geq(N_{1}\cdots
N_{d})^{\frac{1}{d+1}-\frac{\delta}{4^{d}(d+1)}}.$ (4.10)

It follows that $s\geq 2$. Also note that $\rho\leq 1$. We know that $2\leq
s\leq\min_{1\leq i\leq d}N_{i}$. Hence we have

$\sum_{\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}|U^{d}(X,\mathbf{b},s)|\leq|X|\cdot\prod_{i=1}^{d}\left(4\frac{N_{i}}{s}+1\right)\leq
m\cdot\prod_{i=1}^{d}5\frac{N_{i}}{s}=5^{d}\frac{mN_{1}\cdots N_{d}}{s^{d}}$
(4.11)

by Lemma 2.3. Therefore the statement holds if
$C\rho^{\frac{\min(\beta,\delta)}{4^{d}(d+2)!}}\geq 5^{d}$. Hence we may
assume that
$\rho^{\frac{\min(\beta,\delta)}{4^{d}(d+2)!}}<\frac{5^{d}}{C}=2^{d^{3}}C_{0}<2^{d^{3}}$,
or equivalently $\rho<2^{-\frac{(d+2)!\cdot
4^{d}d^{3}}{\min(\beta,\delta)}}=:\rho_{0}$.

We prove the base case $d=1$ using Proposition 4.11. Note that
$\frac{\delta}{4^{d}(d+1)}=\frac{\delta}{8}\leq 1/8$ and
$\frac{\min(\beta,\delta)}{4^{d}(d+2)!}\leq 1/24$. As we assumed that
$\rho\leq\rho_{0}=2^{-\frac{24}{\min(\beta,\delta)}}<5^{-\frac{8}{3}}$, we
have
$\sqrt{N_{1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\geq\sqrt{N_{1}\rho}\rho^{-\frac{3}{8}}\geq
5\sqrt{m}.$ If $s\geq\sqrt{N_{1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\geq
5\sqrt{m}$, then by Proposition 4.11 we have the desired inequality for $d=1$

$\sum_{b\in\mathbb{Z}\setminus\\{\mathbf{0}\\}}|U^{1}(X,b,s)|\leq
C_{0}\frac{mN_{1}}{s}\rho^{\frac{1}{2}}\leq
C\frac{mN_{1}}{s}\rho^{\frac{\min(\beta,\delta)}{4^{d}\cdot(d+2)!}}.$

We next show the desired bound for $d\geq 2$, assuming the induction
hypothesis for $d^{*}=d-1$. Let
$\gamma=\frac{\min(\beta,\delta)}{4^{d}\cdot(d+2)!}$ and
$\epsilon=\rho^{\gamma}$. As $|U^{d}(X,\mathbf{b},s)|$ is zero if $\mathbf{b}$
is not a nonzero integer point in
$[-\frac{N_{1}}{s-1},\frac{N_{1}}{s-1}]\times\cdots\times[-\frac{N_{d}}{s-1},\frac{N_{d}}{s-1}]$,
we may ignore these points in the summation. Let $B_{0}$ be the set of nonzero
integer points in
$[-\frac{N_{1}}{s-1},\frac{N_{1}}{s-1}]\times\cdots\times[-\frac{N_{d}}{s-1},\frac{N_{d}}{s-1}]$.
Let $B_{1}$ be the set of points $\mathbf{b}=(b_{1},\dots,b_{d})$ in $B_{0}$
for which
$|b_{i}/\operatorname{gcd}(b_{1},\dots,b_{d})|\leq\epsilon\frac{N_{i}}{s-1}$
for all $1\leq i\leq d$. Let $B_{2}$ be the set of nonzero integer points
$\mathbf{b}$ in $B_{0}\setminus B_{1}$ for which
$|U^{d}(X,\mathbf{b},s)|\leq\epsilon m$. Let $B=B_{0}\setminus(B_{1}\cup
B_{2})$. Therefore

$\sum_{\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}|U^{d}(X,\mathbf{b},s)|=\sum_{\mathbf{b}\in
B_{1}}|U^{d}(X,\mathbf{b},s)|+\sum_{\mathbf{b}\in
B_{2}}|U^{d}(X,\mathbf{b},s)|+\sum_{\mathbf{b}\in B}|U^{d}(X,\mathbf{b},s)|.$
(4.12)

We estimate each term on the right hand side of (4.12). As $s\leq
N_{1}\rho^{\beta}\leq N_{i}\rho^{\beta}$, we have
$n_{i}:=\frac{N_{i}}{s-1}\geq\rho^{-\beta}\geq\rho^{-\gamma}=\frac{1}{\epsilon}$.
Hence we may apply Lemma 4.9 and conclude that

$|B_{1}|\leq 6^{d}\epsilon n_{1}\cdots n_{d}=6^{d}\epsilon\frac{N_{1}\cdots
N_{d}}{(s-1)^{d}}\leq 12^{d}\epsilon\frac{N_{1}\cdots
N_{d}}{s^{d}}=12^{d}\rho^{\gamma}\frac{N_{1}\cdots N_{d}}{s^{d}}.$

For each $\mathbf{b}\in B_{1}$, we have $U^{d}(X,\mathbf{b},s)\subseteq X$, so
$|U^{d}(X,\mathbf{b},s)|\leq m$. It follows that

$\sum_{\mathbf{b}\in B_{1}}|U^{d}(X,\mathbf{b},s)|\leq|B_{1}|m\leq
12^{d}\rho^{\gamma}\frac{mN_{1}\cdots N_{d}}{s^{d}}.$ (4.13)

As
$B_{0}\subseteq[-\frac{N_{1}}{s-1},\frac{N_{1}}{s-1}]\times\cdots\times[-\frac{N_{d}}{s-1},\frac{N_{d}}{s-1}]$
and $s\leq N_{1}\rho^{\beta}\leq N_{i}$, we have

$|B_{0}|\leq\prod_{i=1}^{d}\left(2\frac{N_{i}}{s-1}+1\right)\leq\prod_{i=1}^{d}\left(4\frac{N_{i}}{s}+1\right)\leq
5^{d}\frac{N_{1}\cdots N_{d}}{s^{d}}.$

Therefore as $B_{2}\subseteq B_{0}$, we have that

$\sum_{\mathbf{b}\in B_{2}}|U^{d}(X,\mathbf{b},s)|\leq|B_{2}|\cdot\epsilon
m\leq 5^{d}\frac{N_{1}\cdots N_{d}}{s^{d}}\cdot\epsilon
m=5^{d}\rho^{\gamma}\frac{mN_{1}\cdots N_{d}}{s^{d}}.$ (4.14)

Observe that $B\subseteq B_{0}$, and it follows

$|B|\leq|B_{0}|\leq 5^{d}\frac{N_{1}\cdots N_{d}}{s^{d}}.$ (4.15)

Here (4.14) gives an upper bound on the second term in (4.12). Finally we
bound the third term. By Lemma 4.10, noting that
$\\{U^{d}(X,\mathbf{b},s)\\}_{\mathbf{b}\in B}$ is a family of subsets of $X$,
we have

$\sum_{\mathbf{b}\in B}\sum_{\mathbf{b}^{\prime}\in
B}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|\geq\frac{1}{m}\left(\sum_{\mathbf{b}\in
B}|U^{d}(X,\mathbf{b},s)\right)^{2}.$ (4.16)

We next give an upper bound on $\sum_{\mathbf{b}^{\prime}\in
B}|U^{d}(X,\mathbf{b},s)\cap U^{d}(X,\mathbf{b}^{\prime},s)|$ for fixed
$\mathbf{b}\in B$ by Lemma 4.8. Before we can apply it, we need to make a few
preparations to ensure that the conditions are satisfied.

Since we have excluded elements in $B_{1}$, for any
$\mathbf{b}=(b_{1},\dots,b_{d})\in B$ there exists some index $i$ for which
$|b_{i}/\operatorname{gcd}(b_{1},\dots,b_{d})|>\epsilon
n_{i}=\epsilon\frac{N_{i}}{s-1}$. This implies that

$\lambda_{\mathbf{b}}:=\max_{1\leq i\leq
d}\frac{|b_{i}|}{\operatorname{gcd}(b_{1},\dots,b_{d})N_{i}}\geq\frac{\epsilon}{s-1}>\frac{\epsilon}{s}.$
(4.17)

Meanwhile, as $|b_{i}|\leq\frac{N_{i}}{s-1}$ for each $i$, we know that
$\lambda_{\mathbf{b}}\leq\frac{1}{s-1}\leq\frac{2}{s}$. Therefore
$\lambda_{\mathbf{b}}\in(\frac{\epsilon}{s},\frac{2}{s}]$ for all
$\mathbf{b}\in B$. Hence $B$ satisfies the conditions in Lemma 4.8 for
$\lambda_{0}:=\frac{\epsilon}{s}$.

We fix an arbitrary $\mathbf{b}\in B$. By Corollary 4.5 there exists a linear
map $f_{\mathbf{b}}:\mathbb{Z}^{d}\to\mathbb{Z}^{d-1}$ that satisfies
conditions (1) and (2). Let $s^{*}=\lceil\epsilon s\rceil$. Now we know that
$\mathbf{b}$, $f_{\mathbf{b}}$, and $s^{*}$ satisfy the conditions in Lemma
4.8. We apply it and get

$\begin{split}\sum_{\mathbf{b}^{\prime}\in B}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|&\leq\frac{4|U^{d}(X,\mathbf{b},s)|}{s\lambda_{0}}+\frac{s^{*}-1}{s}\sum_{\mathbf{b}^{\prime}\in
B}|U^{d}(X,\mathbf{b}^{\prime},s)|\\\
&\quad+\frac{12}{s\lambda_{0}^{2}}\sum_{\mathbf{b}^{*}\in\mathbb{Z}^{d-1}\setminus\\{\mathbf{0}\\}}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),\mathbf{b}^{*},s^{*})|.\end{split}$
(4.18)

For the third term on the right hand side of (4.18), we would like to apply
the induction hypothesis. To do this, we need to verify the various conditions
in the statement by proving following claims.

As $f_{\mathbf{b}}$ satisfies condition (2) in Corollary 4.5, there exist
positive integers $N_{1}^{*},\dots,N_{d-1}^{*}$ such that
$f_{\mathbf{b}}([N_{1}]\times\cdots\times[N_{d}])\subseteq[N_{1}^{*}]\times\cdots\times[N_{d-1}^{*}]$,

$\frac{1}{2}\lambda_{\mathbf{b}}N_{1}\cdots N_{d}\leq N_{1}^{*}\cdots
N_{d-1}^{*}\leq 2^{d^{2}}\lambda_{\mathbf{b}}N_{1}\cdots N_{d},$ (4.19)

Let $M:=\min_{1\leq i\leq d-1}N_{i}^{*}\geq N_{1}$. As
$\lambda_{\mathbf{b}}\in(\frac{\epsilon}{s},\frac{2}{s}]$, we have

$\frac{\epsilon}{2s}N_{1}\cdots N_{d}\leq N_{1}^{*}\cdots
N_{d-1}^{*}\leq\frac{2^{d^{2}+1}}{s}N_{1}\cdots N_{d}.$ (4.20)

Let $X^{*}=f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s))$. As $f_{\mathbf{b}}$
satisfies (2) in Corollary 4.5, we have
$X^{*}\subseteq[N_{1}^{*}]\times\cdots\times[N_{d-1}^{*}]$. Let
$m^{*}:=|X^{*}|$ and $\rho^{*}:=m^{*}/(N_{1}^{*}\cdots N_{d-1}^{*})$.

The following claims allow us to apply the induction hypothesis to
$(N_{j}^{*})_{j=1}^{d-1}$, $X^{*}$, and $s^{*}$.

######  Claim 2.

$N_{1}^{*}\cdots N_{d-1}^{*}\leq M^{d-\delta/3}.$

###### Proof of Claim 2.

Note that $N_{1}\leq M$, so we have that

$N_{1}\cdots N_{d}\leq N_{1}^{d+1-\delta}\leq M^{d+1-\delta}.$ (4.21)

Since $m\geq 1$, we know that $M^{d+1}\geq N_{1}\cdots
N_{d}\geq\frac{1}{\rho}>2^{\frac{(d+2)!\cdot 4^{d}d^{3}}{\min(\beta,\delta)}}$
and so $M\geq 2^{\frac{16(d+2)d^{3}}{\delta}}>2^{\frac{12(d^{2}+1)}{\delta}}$.
Combining (4.21) with (4.10) and (4.20), we have

$N_{1}^{*}\cdots N_{d-1}^{*}\leq 2^{d^{2}}\lambda_{\mathbf{b}}N_{1}\cdots
N_{d}\leq 2^{d^{2}+1}(N_{1}\cdots
N_{d})^{\frac{d}{d+1}+\frac{\delta}{4^{d}(d+1)}}\leq
2^{d^{2}+1}M^{\frac{d+1-\delta}{d+1}(d+\frac{\delta}{4^{d}})}.$ (4.22)

For the exponent of $M$ on the right hand side in (4.22), we know that

$\frac{d+1-\delta}{d+1}\left(d+\frac{\delta}{4^{d}}\right)=d+\frac{\delta}{4^{d}}-\delta\frac{d+\frac{\delta}{4^{d}}}{d+1}<d+\frac{\delta}{4}-\frac{\delta}{2}=d-\frac{\delta}{3}-\frac{\delta}{12}.$

Therefore, we can simplify (4.22) and get

$N_{1}^{*}\cdots N_{d-1}^{*}\leq
2^{d^{2}+1}M^{d-\frac{\delta}{3}-\frac{\delta}{12}}\leq
M^{d-\frac{\delta}{3}}$

as expected, where in the last inequality we use that $M\geq
2^{\frac{12(d^{2}+1)}{\delta}}$. ∎

By Claim 2, we can apply the induction hypothesis to
$X^{*}\subseteq[N_{1}^{*}]\times\cdots\times[N_{d-1}^{*}]$ and
$\delta^{*}=\delta/3$. It remains to show that $s^{*}$ is also in the desired
range.

######  Claim 3.

$(N_{1}^{*}\cdots
N_{d-1}^{*})^{\frac{1}{d}}(\rho^{*})^{\frac{\delta/3}{4^{d-1}d}}\leq s^{*}\leq
M(\rho^{*})^{\beta}.$

###### Proof of Claim 3.

By Lemma 4.6, we have

$\frac{\lambda_{\mathbf{b}}}{2}|U^{d}(X,\mathbf{b},s)|\leq
m^{*}\leq\frac{1}{s}|U^{d}(X,\mathbf{b},s)|.$ (4.23)

Note that $\epsilon=\rho^{\gamma}$ and that $\rho=\frac{m}{N_{1}\cdots
N_{d}}$. As $|U^{d}(X,\mathbf{b},s)|\leq m$, combining with (4.20), we have

$\rho^{*}=\frac{m^{*}}{N_{1}^{*}\cdots
N_{d-1}^{*}}\leq\frac{\frac{m}{s}}{\frac{\epsilon}{2s}N_{1}\cdots
N_{d}}=\frac{2}{\epsilon}\frac{m}{N_{1}\cdots N_{d}}=2\rho^{1-\gamma}.$ (4.24)

Recall that
$\gamma=\frac{\min(\beta,\delta)}{4^{d}\cdot(d+2)!}\leq\frac{\delta}{12\cdot
4^{d}d}$, and so

$\frac{\delta}{3\cdot 4^{d-1}d}(1-\gamma)>\frac{\delta}{3\cdot
4^{d-1}d}-\gamma=\frac{\delta}{4^{d}d}+\frac{\delta}{3\cdot
4^{d}d}-\gamma\geq\frac{d+1}{d}\cdot\frac{\delta}{4^{d}(d+1)}+\gamma+\frac{\delta}{6\cdot
4^{d}d}.$

As a result, raising both sides of $(N_{1}\cdots
N_{d})^{\frac{1}{d+1}}\rho^{\frac{\delta}{4^{d}(d+1)}}\leq s$ to the
$\frac{d+1}{d}$-th power, we have

$s\rho^{\gamma}\geq s^{-\frac{1}{d}}\cdot(N_{1}\cdots
N_{d})^{\frac{1}{d}}\rho^{\frac{d+1}{d}\frac{\delta}{4^{d}(d+1)}+\gamma}\geq
2^{-\frac{d^{2}+1}{d}-\frac{\delta}{3\cdot
4^{d-1}d}}\rho^{-\frac{\delta}{6\cdot
4^{d}d}}\left(\frac{2^{d^{2}+1}}{s}N_{1}\cdots
N_{d}\right)^{\frac{1}{d}}(2\rho^{1-\gamma})^{\frac{\delta}{3\cdot
4^{d-1}d}}.$

Note that $s^{*}\geq\epsilon s=\rho^{\gamma}s$. By (4.24), we have
$\rho^{*}\leq 2\rho^{1-\gamma}$. Combining these with (4.20), we have

$s^{*}\geq s\rho^{\gamma}\geq 2^{-\frac{d^{2}+1}{d}-\frac{\delta}{3\cdot
4^{d-1}d}}\rho^{-\frac{\delta}{6\cdot 4^{d}d}}(N_{1}^{*}\cdots
N_{d-1}^{*})^{\frac{1}{d}}(\rho^{*})^{\frac{\delta}{3\cdot
4^{d-1}d}}\geq(N_{1}^{*}\cdots
N_{d-1}^{*})^{\frac{1}{d}}(\rho^{*})^{\frac{\delta}{3\cdot 4^{d-1}d}}.$ (4.25)

Here in the last inequality we use that $\rho^{-\frac{\delta}{6\cdot
4^{d}d}}\geq\rho^{-2\gamma}\geq 2^{2d^{3}}\geq
2^{\frac{d^{2}+1}{d}+\frac{\delta}{3\cdot 4^{d-1}d}}$. Note that from our
choice of $\mathbf{b}\in B$, $|U^{d}(X,\mathbf{b},s)|$ is at least $\epsilon
m$. Therefore combining with (4.23) we have
$m^{*}\geq\frac{\epsilon}{2}\lambda_{\mathbf{b}}m$. Combining this with (4.19)
and $\epsilon=\rho^{\gamma}$, we have

$\rho^{*}=\frac{m^{*}}{N_{1}^{*}\cdots
N_{d-1}^{*}}\geq\frac{\frac{\epsilon}{2}\lambda_{\mathbf{b}}m}{2^{d^{2}}\lambda_{\mathbf{b}}N_{1}\cdots
N_{d}}\geq 2^{-d^{2}-1}\cdot\epsilon\rho=2^{-d^{2}-1}\rho^{1+\gamma}.$ (4.26)

By (4.10), we know that $\epsilon
s\geq\rho^{\gamma}\cdot(m/\rho)^{\frac{1}{d+1}-\frac{\delta}{4^{d}(d+1)}}\geq\rho^{-\frac{1}{d+1}+\frac{\delta}{4^{d}(d+1)}+\gamma}$.
As $\frac{\delta}{4^{d}(d+1)}+\gamma<\frac{1}{d+1}$ and $\rho<1$, we have
$\epsilon s>1$, so $s^{*}=\lceil\epsilon s\rceil\leq 2\epsilon s$. Note that
$s\leq N_{1}\rho^{\beta}\leq M\rho^{\beta}$. Therefore, we have

$s^{*}\leq 2\epsilon s\leq
2\rho^{\gamma}M\rho^{\beta}=2^{1+\beta(d^{2}+1)}\rho^{\gamma-\beta\gamma}M(2^{-d^{2}-1}\rho^{1+\gamma})^{\beta}\leq
M(\rho^{*})^{\beta},$ (4.27)

where in the last inequality we use (4.26) and that
$\rho^{-\gamma+\beta\gamma}\geq\rho^{\gamma/2}>2^{d^{3}/2}>2^{1+\beta(d^{2}+1)}$
for $d\geq 2$. ∎

We conclude that the conditions for the induction hypothesis are satisfied by
$d^{*}=d-1$, $(N_{i}^{*})_{i=1}^{d-1}$, $\delta^{*}=\delta/3$,
$\beta^{*}=\beta$, $X^{*}=f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s))$, and
$s^{*}=\lceil\epsilon s\rceil$. Applying the induction hypothesis we get

$\sum_{\mathbf{b}^{*}\in\mathbb{Z}^{d-1}\setminus\\{\mathbf{0}\\}}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),\mathbf{b}^{*},s^{*})|\leq
C^{*}\frac{N_{1}^{*}\cdots
N_{d-1}^{*}m^{*}}{(s^{*})^{d-1}}(\rho^{*})^{\frac{\min(\beta,\delta/3)}{4^{d-1}(d+1)!}},$
(4.28)

where $C^{*}=C_{0}\cdot 5^{d-1}\cdot 2^{(d-1)^{3}}$. Using (4.20), (4.23),
(4.24), and that $s^{*}\geq\rho^{\gamma}s$, we have

$C^{*}\frac{N_{1}^{*}\cdots
N_{d-1}^{*}m^{*}}{(s^{*})^{d-1}}(\rho^{*})^{\gamma^{*}}\leq
C^{*}\frac{2^{d^{2}+1}N_{1}\cdots
N_{d}}{\rho^{(d-1)\gamma}s^{d+1}}\rho^{(1-\gamma)\gamma^{*}}|U^{d}(X,\mathbf{b},s)|$
(4.29)

where for simplicity we denote
$\gamma^{*}:=\frac{\min(\beta,\delta/3)}{4^{d-1}\cdot(d+1)!}\geq\frac{\min(\beta,\delta)}{3\cdot
4^{d-1}\cdot(d+1)!}=\frac{4(d+2)}{3}\gamma$. Note that exponent of $\rho$ on
the right hand side of (4.29) satisfies
$(1-\gamma)\gamma^{*}-(d-1)\gamma=\gamma^{*}-(d-1+\gamma^{*})\gamma>3\gamma$.
Combining this with the inequalities (4.28) and (4.29), we have

$\sum_{\mathbf{b}^{*}\in\mathbb{Z}^{d-1}\setminus\\{\mathbf{0}\\}}|U^{d-1}(f_{\mathbf{b}}(U^{d}(X,\mathbf{b},s)),\mathbf{b}^{*},s^{*})|\leq
2^{d^{2}+1}C^{*}\rho^{3\gamma}\frac{N_{1}\cdots
N_{d}}{s^{d+1}}|U^{d}(X,\mathbf{b},s)|.$ (4.30)

Put this into (4.18). Note that
$\lambda_{0}=\frac{\epsilon}{s}=\rho^{\gamma}/s$ and that
$\frac{s^{*}-1}{s}\leq\frac{\epsilon s}{s}=\rho^{\gamma}$. We have

$\begin{split}\sum_{\mathbf{b}^{\prime}\in B}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|&\leq
4\rho^{-\gamma}|U^{d}(X,\mathbf{b},s)|+\rho^{\gamma}\sum_{\mathbf{b}^{\prime}\in
B}|U^{d}(X,\mathbf{b}^{\prime},s)|\\\ &+12\cdot
2^{d^{2}+1}C^{*}\rho^{\gamma}\frac{N_{1}\cdots
N_{d}}{s^{d}}|U^{d}(X,\mathbf{b},s)|.\end{split}$ (4.31)

We sum (4.31) over $\mathbf{b}\in B$. Recall that
$\gamma=\frac{\min(\beta,\delta)}{4^{d}\cdot(d+2)!}<\frac{\beta}{4}$. We have

$\frac{N_{1}\cdots
N_{d}}{s^{d}}\geq\frac{N_{1}^{d}}{s^{d}}\geq\rho^{-d\beta}>\rho^{-2\gamma},$

and it follows that $\rho^{-\gamma}<\rho^{\gamma}\frac{N_{1}\cdots
N_{d}}{s^{d}}$. Using this and (4.15), we have

$\begin{split}\sum_{\mathbf{b},\mathbf{b}^{\prime}\in
B}|U^{d}(X,\mathbf{b},s)\cap
U^{d}(X,\mathbf{b}^{\prime},s)|&\leq\left(4\rho^{-\gamma}+\rho^{\gamma}|B|+12\cdot
2^{d^{2}+1}C^{*}\rho^{\gamma}\frac{N_{1}\cdots
N_{d}}{s^{d}}\right)\sum_{\mathbf{b}\in B}|U^{d}(X,\mathbf{b},s)|\\\
&\leq\left(4+5^{d}+12\cdot
2^{d^{2}+1}C^{*}\right)\rho^{\gamma}\frac{N_{1}\cdots
N_{d}}{s^{d}}\sum_{\mathbf{b}\in B}|U^{d}(X,\mathbf{b},s)|.\end{split}$

Combine this with (4.16), we have

$\sum_{\mathbf{b}\in B}|U^{d}(X,\mathbf{b},s)|\leq\left(4+5^{d}+12\cdot
2^{d^{2}+1}C^{*}\right)\rho^{\gamma}\frac{N_{1}\cdots N_{d}}{s^{d}}m.$ (4.32)

Substituting in the bounds (4.13), (4.14), and (4.32) into (4.12), we have

$\sum_{\mathbf{b}\in\mathbb{Z}^{d}\setminus\\{\mathbf{0}\\}}|U^{d}(X,\mathbf{b},s)|\leq\left(12^{d}+5^{d}+4+5^{d}+12\cdot
2^{d^{2}+1}C^{*}\right)\rho^{\gamma}\frac{mN_{1}\cdots N_{d}}{s^{d}}.$

Finally, we show that the sum of the additive constant above is at most $C$.
Recall that $C^{*}=C_{0}\cdot 5^{d-1}\cdot 2^{(d-1)^{3}}$ and $C=C_{0}\cdot
5^{d}\cdot 2^{d^{3}}$, we know that $24\cdot
2^{d^{2}}C^{*}\leq\frac{3}{5}\cdot 5\cdot 2^{3d^{2}-3d+1}C^{*}=\frac{3C}{5}$
as $d\geq 2$. For other terms, we have $4\leq 5^{d}\leq 12^{d}\leq
2^{d^{3}}=\frac{C}{5^{d}C_{0}}\leq\frac{C}{25}$ and it follows that
$12^{d}+5^{d}+4+5^{d}+12\cdot
2^{d^{2}+1}C^{*}\leq\frac{4}{25}C+\frac{3}{5}C<C$. Thus the statement holds
for $d$. Therefore we conclude that the statement holds for all positive
integer $d$.∎

##  5\. A proof of the lower bound in Theorem 1.3

We prove the following result, which is the lower bound on the discrepancy in
Theorem 1.3.

######  Theorem 5.1.

For any positive integer $d$, there exists a constant $c_{d}>0$ such that the
following holds. For positive integer $N_{1},\ldots,N_{d}$, letting
$\mathbf{N}=(N_{1},\dots,N_{d})$, we have

$\operatorname{disc}(\mathcal{A}_{\mathbf{N}})\geq
c_{d}\max_{I\subseteq[d]}\left(\prod_{i\in I}N_{i}\right)^{\frac{1}{2|I|+2}}.$

Here by convention if $I=\emptyset$ then $\prod_{i\in I}N_{i}=1$.

Roth [9] proved the case $d=1$, and Valkó [10] proved the case that the
$N_{i}$’s are equal. Similar to these previous results, our proof uses Fourier
analysis. We first set up some notations. Let
$f,g:\mathbb{Z}^{d}\to\mathbb{C}$ be two functions that each has finite
support. The Fourier transform $\widehat{f}:[0,1]^{d}\to\mathbb{C}$ is given
by
$\widehat{f}(\mathbf{r})=\sum_{\mathbf{x}\in\mathbb{Z}^{d}}f(\mathbf{x})e^{-2\pi
i\mathbf{x}\cdot\mathbf{r}}$. The convolution
$f*g:\mathbb{Z}^{d}\to\mathbb{C}$ is given by
$f*g(\mathbf{x})=\sum_{\mathbf{r}\in\mathbb{Z}^{d}}f(\mathbf{r})g(\mathbf{x}-\mathbf{r})$,
which also has finite support. With these notations, we have the convolution
identity $\widehat{f*g}=\widehat{f}\cdot\widehat{g}$ and Parseval’s identity

$\sum_{\mathbf{x}\in\mathbb{Z}^{d}}f(\mathbf{x})\overline{g(\mathbf{x})}=\int_{[0,1]^{d}}\widehat{f}(\mathbf{r})\overline{\widehat{g}(\mathbf{r})}\,d\mathbf{r}.$

In the proof of Theorem 5.1 below, for a vector $\mathbf{x}\in\mathbb{Z}^{d}$,
we let $\mathbf{x}_{i}$ denote the $i^{\textrm{th}}$ coordinate of
$\mathbf{x}$.

###### Proof of Theorem 5.1.

We take $c_{d}=\frac{6^{-d/2}}{2}$ Let
$\Omega=[N_{1}]\times\cdots\times[N_{d}]\subseteq\mathbb{Z}^{d}$. Fix any
$\chi:\Omega\to\\{1,-1\\}$. Let
$T=\max_{A\in\mathcal{A}_{\mathbf{N}}}|\chi(A)|$. It suffices to show that
$T\geq c_{d}\max_{I\subseteq[d]}\left(\prod_{i\in
S}N_{i}\right)^{\frac{1}{2|I|+2}}$.

For $\chi:\Omega\to\\{1,-1\\}$, we may extend it to a function
$\chi:\mathbb{Z}^{d}\to\\{-1,0,1\\}$ by assigning $0$ to
$\mathbb{Z}^{d}\setminus\Omega$. Clearly $\chi$ takes nonzero values on
$N_{1}\cdots N_{d}$ points. Hence we may apply Parseval’s identity and get

$\int_{[0,1]^{d}}\widehat{\chi}(\mathbf{r})\overline{\widehat{\chi}(\mathbf{r})}\,d\mathbf{r}=\sum_{\mathbf{x}\in\mathbb{Z}^{d}}\chi(\mathbf{x})\overline{\chi(\mathbf{x})}=N_{1}\cdots
N_{d}.$ (5.1)

Let $L$ be a positive integer and $D_{1},\dots D_{d}$ be nonnegative integers
to be determined later. For each
$\mathbf{b}\in\mathbb{Z}^{d}\setminus\mathbf{0}$ satisfying that
$\mathbf{b}_{i}\in[-D_{i},D_{i}]$ for $1\leq i\leq d$, let
$g_{\mathbf{b}}:\mathbb{Z}^{d}\to\mathbb{C}$ be the indicator function of the
set $\\{0,\mathbf{b},\dots,(L-1)\mathbf{b}\\}$. Now we have for each
$\mathbf{x}\in\mathbb{Z}^{d}$,

$g_{\mathbf{b}}*\chi(\mathbf{x})=\sum_{t=0}^{L-1}\chi(\mathbf{x}-t\mathbf{b})=\chi(\Omega\cap\\{\mathbf{x}-t\mathbf{b}:0\leq
t<L\\}).$

Since $\Omega\cap\\{\mathbf{x}-t\mathbf{b}:0\leq t<L\\}$ is an arithmetic
progression contained in $\Omega$, it is a set in $\mathcal{A}_{\mathbf{N}}$,
so $|g_{\mathbf{b}}*\chi(\mathbf{x})|\leq T$. This is true for all
$\mathbf{x}\in\mathbb{Z}^{d}$. Also note that
$|g_{\mathbf{b}}*\chi(\mathbf{x})|$ is nonzero only when
$\mathbf{x}-t\mathbf{b}\in\Omega$ for some $0\leq t<L$. In this case we have
$\mathbf{x}_{i}\in[1-LD_{i},N_{i}+LD_{i}]$ for each $1\leq i\leq d$.
Therefore, $g_{\mathbf{b}}*\chi$ is nonzero on at most
$\prod_{i=1}^{d}(N_{i}+2LD_{i})$ points in $\mathbb{Z}^{d}$. We have

$\sum_{\mathbf{x}\in\mathbb{Z}^{d}}{g_{\mathbf{b}}*\chi}(\mathbf{x})\overline{{g_{\mathbf{b}}*\chi}(\mathbf{x})}=\sum_{\mathbf{x}\in\mathbb{Z}^{d}}\left|{g_{\mathbf{b}}*\chi}(\mathbf{x})\right|^{2}\leq
T^{2}\prod_{i=1}^{d}(N_{i}+2LD_{i}).$ (5.2)

By the convolution identity and Parseval’s identity, we have

$\sum_{\mathbf{x}\in\mathbb{Z}^{d}}{g_{\mathbf{b}}*\chi}(\mathbf{x})\overline{{g_{\mathbf{b}}*\chi}(\mathbf{x})}=\int_{[0,1]^{d}}\widehat{g_{\mathbf{b}}*\chi}(\mathbf{r})\overline{\widehat{g_{\mathbf{b}}*\chi}(\mathbf{r})}\,d\mathbf{r}=\int_{[0,1]^{d}}\widehat{g_{\mathbf{b}}}(\mathbf{r})\widehat{\chi}(\mathbf{r})\overline{\widehat{g_{\mathbf{b}}}(\mathbf{r})\widehat{\chi}(\mathbf{r})}\,d\mathbf{r}$
(5.3)

Combining (5.2) and (5.3), we get that for any nonzero
$\mathbf{b}\in[-D_{1},D_{1}]\times\dots\times[-D_{d},D_{d}]$

$\int_{[0,1]^{d}}\left|\widehat{g_{\mathbf{b}}}(\mathbf{r})\right|^{2}\widehat{\chi}(\mathbf{r})\overline{\widehat{\chi}(\mathbf{r})}\,d\mathbf{r}\leq
T^{2}\prod_{i=1}^{d}(N_{i}+2LD_{i}).$ (5.4)

Let $A$ be the set of integer points in $[0,D_{1}]\times\cdots\times[0,D_{d}]$
and $B$ be the set of nonzero integer points in
$[-D_{1},D_{1}]\times\cdots\times[-D_{d},D_{d}]$. Clearly any two distinct
points in $A$ have their difference in $B$. The number of points in $B$ is at
most $\prod_{i=1}^{d}(2D_{i}+1)$. Hence if we sum over $\mathbf{b}\in B$ in
(5.4), we get

$\int_{[0,1]^{d}}\left(\sum_{\mathbf{b}\in
B}\left|\widehat{g_{\mathbf{b}}}(\mathbf{r})\right|^{2}\right)\widehat{\chi}(\mathbf{r})\overline{\widehat{\chi}(\mathbf{r})}\,d\mathbf{r}\leq
T^{2}\prod_{i=1}^{d}(N_{i}+2LD_{i})(2D_{i}+1)$ (5.5)

Fix any $\mathbf{r}\in[0,1]^{d}$. By the pigeonhole principle, there exists
two distinct $\mathbf{a},\mathbf{a}^{\prime}\in A$ such that the fractional
parts of $\mathbf{a}\cdot\mathbf{r}$ and $\mathbf{a}^{\prime}\cdot\mathbf{r}$
differ by at most $1/|A|$. Hence for any $\mathbf{r}$ we can find
$\mathbf{b}^{\prime}\in B$ (we shall take
$\mathbf{b}^{\prime}=\mathbf{a}-\mathbf{a}^{\prime}$ or
$\mathbf{b}^{\prime}=\mathbf{a}^{\prime}-\mathbf{a}$) such that the fractional
part of $\mathbf{b}^{\prime}\cdot\mathbf{r}$ is in $[0,1/|A|]$. If
$L\leq\frac{|A|}{2}=\frac{1}{2}\prod_{i=1}^{d}(D_{i}+1)$, then for any
$\mathbf{r}\in[0,1]^{d}$,

$\sum_{\mathbf{b}\in
B}\left|\widehat{g_{\mathbf{b}}}(\mathbf{r})\right|^{2}\geq\left|\widehat{g_{\mathbf{b}^{\prime}}}(\mathbf{r})\right|^{2}=\left|\sum_{t=0}^{L-1}e^{-t2\pi
i\mathbf{b}^{\prime}\cdot\mathbf{r}}\right|^{2}\geq\frac{4}{\pi^{2}}L^{2}.$

Put this into (5.5) and combine with (5.1). We conclude that for any positive
integer $L$ and nonnegative integers $D_{1},\dots,D_{d}$ such that
$L\leq\frac{(D_{1}+1)\cdots(D_{d}+1)}{2}$, then

$T^{2}\prod_{i=1}^{d}(N_{i}+2LD_{i})(2D_{i}+1)\geq\frac{4}{\pi^{2}}L^{2}\prod_{i=1}^{d}N_{i}.$
(5.6)

Let $R=\max_{I\subseteq[d]}\left(\prod_{i\in
I}N_{i}\right)^{\frac{1}{2|I|+2}}$. If $R\leq 2$, the statement is trivial as
$c_{d}=\frac{6^{-d/2}}{2}\leq 1/2$. Therefore we may assume that $R>2$ and the
maximum in the definition of $R$ is achieved by some nonempty $I\subseteq[d]$.
For each $j\in I$, we have $R\geq\left(\prod_{i\in
I\setminus\\{j\\}}N_{i}\right)^{\frac{1}{2|I|}}$, so $N_{j}\geq R^{2}$. With
these properties, we may now choose the values of $L$ and $D_{1},\dots,D_{d}$.
We set $L=\lfloor R^{2}/2\rfloor$, $D_{i}=\lfloor\frac{N_{i}}{R^{2}}\rfloor$
for $i\in I$, and $D_{j}=0$ for each $j\notin I$. Since

$\frac{(D_{1}+1)\cdots(D_{d}+1)}{2}\geq\frac{\prod_{i\in
I}N_{i}}{2R^{2|I|}}=\frac{R^{2}}{2}\geq L,$

we can apply (5.6) to these variables. For $j\notin I$, as $D_{j}=0$, we have
$(N_{j}+2LD_{j})(2D_{j}+1)=N_{j}$. For $i\in I$, since $N_{i}\geq R^{2}$, we
have $N_{i}/R^{2}\geq D_{i}\geq 1$, so

$(N_{i}+2LD_{i})(2D_{i}+1)\leq\left(N_{i}+2\cdot\frac{R^{2}}{2}\cdot\frac{N_{i}}{R^{2}}\right)\cdot
3\frac{N_{i}}{R^{2}}=6\frac{N_{i}^{2}}{R^{2}}.$

Put these into (5.6). Note that $L\geq\frac{R^{2}}{2}$. We have

$T^{2}\prod_{i\in I}6\frac{N_{i}^{2}}{R^{2}}\cdot\prod_{j\notin
I}N_{j}\geq\frac{R^{4}}{4}\prod_{i=1}^{d}N_{i}.$

Also note that $\prod_{i\in I}N_{i}=R^{2|I|+2}$. We conclude that
$T\geq\frac{6^{-\frac{|I|}{2}}}{2}R\geq c_{d}R$. ∎

##  6\. A proof of the upper bound in Theorem 1.3

In this section, we aim to generalize the upper bound in Theorem 1.2 to all
grids of differing side lengths. The following lemma allows us to remove
dimensions of short side lengths.

######  Lemma 6.1.

Let $d\geq 2$ be a positive integer and $N_{1},\dots,N_{d}$ be positive
integers. Then for $\mathbf{N}=(N_{1},\dots,N_{d})$ and
$\mathbf{N}^{\prime}=(N_{1},\dots,N_{d-1})$, we have

$\operatorname{disc}(\mathcal{A}_{\mathbf{N}})\leq\max\left(\operatorname{disc}(\mathcal{A}_{\mathbf{N}^{\prime}}),\sqrt{6N_{d}\log(2N_{1}\cdots
N_{d})}\right).$

###### Proof.

Firstly we may choose an optimal coloring $\chi^{\prime}$ for the grid
$[N_{1}]\times\cdots\times[N_{d-1}]$ that achieves discrepancy
$\operatorname{disc}(\mathcal{A}_{\mathbf{N}^{\prime}})$.

We extend this coloring to a coloring
$\chi:[N_{1}]\times\cdots\times[N_{d}]\to\\{1,-1\\}$ by the following
procedure. Take $N_{d}$ i.i.d. Rademacher random variables $v(i)$ for $1\leq
i\leq N_{d}$ (i.e. $\Pr(v(i)=1)=\Pr(v(i)=-1)=\frac{1}{2}$). Now we set
$\chi(x_{1},\dots,x_{d})=\chi^{\prime}(x_{1},\dots,x_{d-1})v(x_{d})$ for any
$(x_{1},\dots,x_{d})\in[N_{1}]\times\cdots\times[N_{d}]$.

Now we analyze $\chi(S)$ for $S\in\mathcal{A}_{\mathbf{N}}$. Let
$(k_{1},\dots,k_{d})$ be the common difference of arithmetic progression $S$.
If $k_{d}=0$, then all elements in $S$ share the same $d$-th coordinate
$x_{d}$, so we may write $S$ as $S^{\prime}\times\\{x_{d}\\}$, where
$S^{\prime}$ is also an arithmetic progression with common difference
$(k_{1},\dots,k_{d-1})$. By our construction of $\chi$, we have
$|\chi(S)|=|\chi^{\prime}(S^{\prime})v(x_{d})|\leq\operatorname{disc}(\mathcal{A}_{\mathbf{N}^{\prime}})$.

Otherwise if $k_{d}\neq 0$, then all elements in $S$ have distinct $d$-th
coordinates, and $|S|\leq N_{d}$. Since $\chi^{\prime}$ is deterministic, we
know that $\chi(S)$ is a summation of $|S|$ i.i.d. Rademacher random
variables. Now by the Chernoff bound (e.g. see Theorem A.1.1 and Corollary
A.1.2 in [1]), we have

$\Pr(|\chi(S)|>\sqrt{6N_{d}\log(2N_{1}\cdots N_{d})})\leq
2e^{-\frac{6N_{d}\log(2N_{1}\cdots N_{d})}{2|S|}}\leq\frac{1}{4}(N_{1}\cdots
N_{d})^{-3}<(N_{1}\cdots N_{d})^{-3},$

where in the last inequality we use that $|S|\leq N_{d}$. Finally we apply the
union bound on all $S$ with $k_{d}\neq 0$. Clearly there are $N_{1}\cdots
N_{d}$ ways to pick the first element in the arithmetic progression, and at
most $N_{1}\cdots N_{d}$ ways to pick the last element, and at most $N_{d}$
ways to choose $|S|$ (as $1\leq|S|\leq N_{d}$). Once these are chosen, then
clearly $S$ is determined as the common difference in the last coordinate is
determined. Hence the total number of distinct $S$ in
$\mathcal{A}_{\mathbf{N}}$ with $k_{d}\neq 0$ is at most $(N_{1}\cdots
N_{d})^{3}$. By union bound, we conclude that there exists a choice of $v$
such that $|\chi(S)|\leq\sqrt{6N_{d}\log(2N_{1}\cdots N_{d})}$ for all
$S\in\mathcal{A}_{\mathbf{N}}$ with distinct $d$-th coordinates.

In summary, we conclude that there is a choice of
$\chi:[N_{1}]\times\cdots\times[N_{d}]\to\\{1,-1\\}$ so that

$\max_{S\in\mathcal{A}_{\mathbf{N}}}|\chi(S)|\leq\max\left(\operatorname{disc}(\mathcal{A}_{\mathbf{N}^{\prime}}),\sqrt{6N_{d}\log(2N_{1}\cdots
N_{d})}\right).$

Note that $\operatorname{disc}(\mathcal{A}_{\mathbf{N}})$ is defined as the
minimum over all $\chi$, so we have the desired inequality. ∎

###### Proof of the upper bound in Theorem 1.3.

Suppose that $N_{1}\geq N_{2}\geq\cdots\geq N_{d}\geq 1=:N_{d+1}$. Assume that
$N_{1}$ is sufficiently large to avoid triviality.

Let $R_{i}=\left(\prod_{j=1}^{i}N_{j}\right)^{\frac{1}{i+1}}$ for $1\leq i\leq
d$. Clearly

$\max_{I\subseteq[d]}\left(\prod_{i\in
I}N_{i}\right)^{\frac{1}{|I|+1}}=\max_{1\leq i\leq d}R_{i}.$

Now we take $t$ to be the first index $1\leq i\leq d$ such that
$R_{i}>\frac{N_{i+1}}{(\log(N_{1}\cdots N_{d}))^{\frac{1}{2}}}$. By repeatedly
applying Lemma 6.1, for $\mathbf{N}^{\prime}=(N_{1},\dots,N_{t})$, we have

$\operatorname{disc}(\mathcal{A}_{\mathbf{N}})\leq\max\left(\operatorname{disc}(\mathcal{A}_{\mathbf{N}^{\prime}}),4\sqrt{N_{t+1}\log(N_{1}\cdots
N_{d})}\right).$ (6.1)

By our choice of $t$, we have $4\sqrt{N_{t+1}\log(N_{1}\cdots N_{d})}\leq
4\sqrt{R_{t}}(\log(N_{1}\cdots N_{d}))^{\frac{3}{4}}$.

Also we have $N_{t}\geq R_{t-1}(\log(N_{1}\cdots N_{d}))^{\frac{1}{2}}$, so
$N_{t}\geq R_{t}(\log(N_{1}\cdots N_{d}))^{\frac{t}{2(t+1)}}\geq
R_{t}(\log(N_{1}\cdots N_{d}))^{\frac{1}{4}}$. Consequently, we may pick
$\delta=O\left(\frac{\log(N_{1}\cdots N_{d})}{\log\log(N_{1}\cdots
N_{d})}\right)$ so that $N_{t}^{t+1-\delta}=R_{t}^{t+1}$. By Theorem 1.2 we
have

$\operatorname{disc}(\mathcal{A}_{\mathbf{N}^{\prime}})=O_{d}\left(\sqrt{R_{t}}\frac{\log(N_{1}\cdots
N_{d})}{\log\log(N_{1}\cdots N_{d})}\right).$

This completes the proof by invoking (6.1). ∎

######  Remark.

The above proof gives that we can take $C_{d}=2^{O(d^{3})}$ in Theorem 1.3.

##  7\. Concluding remarks

Theorem 1.3 determines $\operatorname{disc}(\mathcal{A}_{\mathbf{N}})$ up to a
constant factor for many $\mathbf{N}$’s. However, even when $d=2$, there is a
regime where the upper and lower bounds are not within a constant factor. As a
special case, let $\mathbf{N}=(N,\sqrt{N}(\log N)^{k})$ for $k\geq\frac{3}{2}$
and large $N$. Theorem 1.3 yields a lower bound of
$\Omega(N^{\frac{1}{4}}(\log N)^{\frac{k}{6}})$ and an upper bound of
$O(N^{\frac{1}{4}}{(\log N)^{\frac{k}{6}+1}}{(\log\log N)^{-1}})$. If we apply
Lemma 6.1 and the Matoušek-Spencer theorem in one dimension [8], we get a
weaker upper bound of $O(N^{\frac{1}{4}}(\log N)^{\frac{k+1}{2}})$. In some
other regimes, such as when $0<k<\frac{3}{2}$ in the above example, Lemma 6.1
and [8] gives a better upper bound than Theorem 1.3, yet it is still not
within a constant factor from the lower bound.

It is interesting to know if the sub-logarithmic factor in the upper bound of
Theorem 1.3 can be removed or not. We conjecture that it can be and the lower
bound is tight.

######  Conjecture 7.1.

For any integer $d\geq 1$, let $\mathbf{N}=(N_{1},N_{2},\cdots,N_{d})$ where
$N_{1},\dots,N_{d}$ are positive integers. Then

$\operatorname{disc}(\mathcal{A}_{\mathbf{N}})=\Theta_{d}\left(\max_{I\subseteq[d]}\left(\prod_{i\in
I}N_{i}\right)^{\frac{1}{2|I|+2}}\right).$

## References

  * [1] N. Alon and J. H. Spencer, The probabilistic method, 4th ed. Wiley, Hoboken, NJ, 2016.
  * [2] J. Beck, Roth’s estimate of the discrepancy of integer sequences is nearly sharp, Combinatorica 1 (1981), 319-325.
  * [3] J. Beck and W. W. L Chen, Irregularities of distribution, Cambridge Tracts in Mathematics, 89. Cambridge University Press, Cambridge, 1987.
  * [4] J. W. Cassels, An introduction to the geometry of numbers, corrected reprint of the 1971 edition, Springer-Verlag, Berlin, 1997.
  * [5] B. Doerr, A. Srivastav and P. Wehr, Discrepancy of Cartesian products of arithmetic progressions. Electron. J. Combin. 11 (2004), no. 1
  * [6] A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515-534.
  * [7] J. Matoušek, Geometric Discrepancy: An Illustrated Guide, Algorithms Combin. 18, Springer, Berlin, 1999.
  * [8] J. Matoušek and J. Spencer, Discrepancy in arithmetic progressions, J. Amer. Math. Soc. 9 (1996), 195-204.
  * [9] K. F. Roth, Remark concerning integer sequences, Acta Arith. 9 (1964), 257-260.
  * [10] B. Valkó, Discrepancy of arithmetic progressions in higher dimensions, J. Number Theory 92 (2002), 117-130.