1 Introduction
Let
$\mathbb {E}^n$
denote n-dimensional Euclidean space, that is,
${\mathbb {R}}^n$
equipped with the Euclidean metric. Given finite sets
$X_1, X_2, \dots , X_r \subset {\mathbb {E}}^n$
, we write
$\mathbb {E}^n \rightarrow (X_1, X_2, \dots , X_r)$
if every r-coloring of
${\mathbb {E}}^n$
contains a copy of
$X_i$
in color i for some i, where a copy for us will always mean an isometric copy. Conversely,
$\mathbb {E}^n \nrightarrow (X_1, X_2, \dots , X_r)$
means that there is some r-coloring of
${\mathbb {E}}^n$
which does not contain a copy of
$X_i$
in color i for any i. The Euclidean Ramsey problem, the study of which goes back to fundamental work of Erdős et al. [Reference Erdős, Graham, Montgomery, Rothschild, Spencer and Straus5–Reference Erdős, Graham, Montgomery, Rothschild, Spencer and Straus7] in the 1970s, asks for a determination of those
$X_1, X_2, \dots , X_r \subset {\mathbb {E}}^n$
for which
$\mathbb {E}^n \rightarrow (X_1, X_2, \dots , X_r)$
.
In the particular case, where
$X_1 = X_2 = \dots = X_r = X$
, we simply write
$\mathbb {E}^n \rightarrow (X)_r$
to denote that every r-coloring of
${\mathbb {E}}^n$
contains a monochromatic copy of X. Following Erdős et al. [Reference Erdős, Graham, Montgomery, Rothschild, Spencer and Straus5], we say that X is Ramsey if for every r there exists n such that
$\mathbb {E}^n \rightarrow (X)_r$
. The problem of determining those X which are Ramsey is perhaps the most notorious question in this area and there are two rival conjectures for a characterization.
The first conjecture, already made by Erdős et al. in their first paper [Reference Erdős, Graham, Montgomery, Rothschild, Spencer and Straus5] on the subject, says that a finite set X is Ramsey if and only if it is spherical, meaning that it can be embedded in the surface of a sphere of some dimension. That being spherical is a necessary condition was already proved in [Reference Erdős, Graham, Montgomery, Rothschild, Spencer and Straus5] and subsequent results such as that of Frankl and Rödl [Reference Frankl and Rödl8] saying that all non-degenerate simplices are Ramsey and that of Kříž [Reference Kříž11] saying that regular polygons are Ramsey appear to add further weight.
However, as pointed out by Leader et al. [Reference Leader, Russell and Walters13], all examples which are known to be Ramsey have the stronger property that they are subtransitive, in the sense that they are subsets of finite sets which are transitive under the action of an appropriate group of isometries. This and other considerations then led them to make the rival conjecture that a finite set X is Ramsey if and only if it is subtransitive. As there are finite sets which are spherical but not subtransitive (a non-obvious fact proved in [Reference Leader, Russell and Walters12, Reference Leader, Russell and Walters13]), this is a strictly stronger conjecture, but, unlike the spherical sets conjecture, both directions of this conjecture remain open.
A result of Conlon and Fox [Reference Conlon and Fox2] says that, under the axiom of choice, a finite set X is Ramsey if and only if for every natural number d and every fixed finite set
$K \subset \mathbb {E}^d$
, there exists n such that
$\mathbb {E}^n \rightarrow (X, K)$
. That is, the problem of determining which sets are Ramsey can be recast in a somewhat simpler form. Conlon and Wu [Reference Conlon and Wu3] conjectured an even simpler characterization, that a finite set X is Ramsey if and only if for every natural number m, there exists n such that
$\mathbb {E}^n \rightarrow (X, \ell _m)$
, where
$\ell _m$
is the set consisting of m points on a line with consecutive points at distance one. One direction of this conjecture, that if X is Ramsey and m is a natural number, then there exists n such that
$\mathbb {E}^n \rightarrow (X, \ell _m)$
, follows from the result of Conlon and Fox (though the idea for this part of their result is essentially due to Szlam [Reference Szlam14]). However, the other direction remains open. Here, we make some progress by proving the opposite direction for non-spherical sets. This verifies another conjecture made explicitly by Conlon and Wu [Reference Conlon and Wu3] and would settle their original conjecture in full if the spherical sets conjecture is true.
Theorem 1 For every finite non-spherical set X, there exists a natural number m such that
$\mathbb {E}^n \nrightarrow (X, \ell _m)$
for all n.
The main result of [Reference Conlon and Wu3] was a proof of this conjecture in the particular case where X is taken to be
$\ell _3$
, the simplest non-spherical set, which already answered a question raised independently by Conlon and Fox [Reference Conlon and Fox2] and by Arman and Tsaturian [Reference Arman and Tsaturian1]. Their proof is probabilistic and shows that one may take
$m \leq 10^{50}$
. Through more explicit constructions, this bound has subsequently been improved, first by Führer and Toth [Reference Führer and Tóth9] to
$m \leq 1177$
and then by Currier et al. [Reference Currier, Moore and Yip4] to
$m \le 20$
. Both of these papers also proved certain further special cases of Theorem 1, though it remained wide open in full generality. Our construction here is again explicit, but the proof that it works makes use of some tools on equidistribution, namely, Weyl’s equidistribution theorem and the Erdős–Turán–Koksma inequality.
2 Proof of Theorem 1
2.1 The construction
By a result of Erdős et al. [Reference Erdős, Graham, Montgomery, Rothschild, Spencer and Straus5, Lemma 14], there exist
$c_1, \dots , c_s \in {\mathbb {R}}$
and
$B> 0$
such that every copy
$\{x_1, \dots , x_s\}$
of the non-spherical configuration X satisfies
$\sum _{j=1}^s c_j |x_j|^2=B$
. Without loss of generality, we can assume that
$1\not \in \langle c_1,...,c_s \rangle _{\mathbb {Q}}$
, as otherwise we can rescale the equation by a factor
$\mu \not \in \langle c_1,...,c_s \rangle _{\mathbb {Q}}$
. Now, let
$b_1,...,b_r$
be a
$\mathbb {Q}$
-basis for
$\langle c_1,...,c_s \rangle _{\mathbb {Q}}$
and let
$q_{j,k}\in \mathbb {Q}$
be such that
$c_j=\sum _{k=1}^rq_{j,k}b_k$
. Let
$M\in \mathbb {N}$
be such that
${B':=MB>\sum _{j=1}^s\sum _{k=1}^r|q_{j,k}|}$
and let
$a_j:=Mb_j$
. We may then recast the equation for copies of X as
$$ \begin{align} \sum_{j=1}^s\sum_{k=1}^rq_{j,k}a_k|x_j|^2=B'. \end{align} $$
We can also assume that all the
$q_{j,k}$
are integral, as otherwise we can multiply the equation by their least common multiple. Let p be a prime with
$p>2B'$
. We now color each point
$x\in \mathbb {E}^n$
red if
$\lfloor a_k|x|^2\rfloor \equiv 0$
(mod p) for all
$k\in [1,r]$
and blue otherwise.
2.2 No red copy of X
Assume that
$x_1,...,x_s$
are red points satisfying (2.1). Then
$$ \begin{align*}\sum_{j=1}^s\sum_{k=1}^rq_{j,k}\lfloor a_k|x_j|^2\rfloor \equiv 0 \text{\;\;(mod }p\text{)}.\end{align*} $$
On the other hand,
$$ \begin{align*} \left| \sum_{j=1}^s\sum_{k=1}^rq_{j,k}a_k|x_j|^2-\sum_{j=1}^s\sum_{k=1}^rq_{j,k}\lfloor a_k|x_j|^2\rfloor \right|< \sum_{j=1}^s\sum_{k=1}^r|q_{j,k}| <B' \end{align*} $$
and therefore
$$ \begin{align*}\sum_{j=1}^s\sum_{k=1}^rq_{j,k}\lfloor a_k|x_j|^2\rfloor\in (0,2B')\subseteq (0,p),\end{align*} $$
which is a contradiction.
2.3 No blue copy of
$\ell _m$
Let
$L = \{w_1, \dots , w_m\}$
be a copy of
$\ell _m$
. It was shown in [Reference Conlon and Wu3, Section 3] that there exist
$\beta , \gamma \in {\mathbb {R}}$
depending on the choice of L such that
$y_j = |w_j|^2$
can be written in the form
$y_j:=j^2+\beta j+\gamma $
for all
$j = 1, \dots , m$
. Consider the sequence
$$ \begin{align*}Z:=(z_j)_{j\in[m]}:=\left(\left(\frac{a_1y_j}{p},...,\frac{a_ry_j}{p}\right)\right)_{j\in[m]}\end{align*} $$
in
$(\mathbb {R}/\mathbb {Z})^r$
. Note here that
$w_j$
is red if and only if
$z_j\in [0,1/p)^r$
. For m sufficiently large and, crucially, independent of the choice of
$\beta $
and
$\gamma $
, we will show that
$\{z_j\}_{j\in [m]}\cap [0,1/p)^r\neq \emptyset $
, which implies that there is no blue copy of
$\ell _m$
in our construction.
Let
$D_m(Z)$
be the discrepancy of Z in
$(\mathbb {R}/\mathbb {Z})^r$
, the supremum over all axis-aligned boxes
$B = \prod _{i=1}^r [a_i, b_i)$
of
$$ \begin{align*}\left|\frac{A(B;Z)}{m} - \mu(B)\right|,\end{align*} $$
where
$A(B; Z)$
counts the number of points of Z in B and
$\mu (\cdot )$
is the Lebesgue measure on
$(\mathbb {R}/\mathbb {Z})^r$
. The key claim is as follows.
Lemma 1
$$ \begin{align*}D_m(Z)< \frac{1}{p^r}.\end{align*} $$
In particular,
$\{z_j\}_{j\in [m]}\cap [0,1/p)^r\neq \emptyset $
.
In order to prove this, we make use of the Erdős–Turán–Koksma inequality [Reference Koksma10].
Lemma 2 (Erdős–Turán–Koksma)
For every positive integer N,
$$ \begin{align*}D_m(Z)\leq C_r\left(\frac{1}{N} +\sum_{1 \leq ||h||_\infty \leq N} \frac{1}{c(h)}\left| \frac{1}{m} \sum_{j=1}^m e(\langle h,z_j\rangle) \right| \right),\end{align*} $$
where
$c(h) = \prod _{i=1}^r \max \{1, |h_i|\}$
for
$h = (h_1, \dots , h_r) \in \mathbb {Z}^r$
and
$e(x)=\exp (2\pi i x)$
.
To estimate the
$\sum _{j=1}^m e(\langle h,z_j\rangle )$
term, we use the following special case of Weyl’s equidistribution theorem [Reference Weyl15, Satz 9].
Lemma 3 (Weyl)
Let
$P(x)= a x^2 + b x + c \in \mathbb {R}[x]$
be a quadratic polynomial with irrational leading coefficient a. Then,
$$ \begin{align*}\left|\sum_{j=1}^m e(P(j)) \right|=o_{a}(m),\end{align*} $$
where the o term does not depend on b or c.
Note now that
$\langle h,z_j\rangle $
describes a quadratic polynomial in
$\mathbb {R}[j]$
with irrational leading coefficient
$\sum _{k=1}^r h_{k}a_{k}/p$
, where we use that
$1\not \in \langle c_1,...,c_s \rangle _{\mathbb {Q}}=\langle a_1,...,a_r \rangle _{\mathbb {Q}}$
. Therefore, we have the following immediate corollary of Lemma 3.
Corollary 1
$$ \begin{align*}\left|\sum_{j=1}^m e(\langle h,z_j\rangle) \right|=o_h(m).\end{align*} $$
We are now in a position to prove Lemma 1.
Acknowledgements
The authors thank Manuel Hauke for helpful conversations regarding equidistribution.
