On colouring integers avoiding t-AP distance-sets
In this paper, we investigate the structure of sets with bounded number of pairs with certain gaps.
Збережено в:
| Дата: | 2016 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2016
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/155741 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On colouring integers avoiding t-AP distance-sets / T. Ahmed // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 1-10. — Бібліогр.: 1 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-155741 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1557412019-06-18T01:25:17Z On colouring integers avoiding t-AP distance-sets Ahmed, T. In this paper, we investigate the structure of sets with bounded number of pairs with certain gaps. 2016 Article On colouring integers avoiding t-AP distance-sets / T. Ahmed // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 1-10. — Бібліогр.: 1 назв. — англ. 1726-3255 2010 MSC:Primary 05D10. http://dspace.nbuv.gov.ua/handle/123456789/155741 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this paper, we investigate
the structure of sets with bounded number of pairs with certain gaps. |
| format |
Article |
| author |
Ahmed, T. |
| spellingShingle |
Ahmed, T. On colouring integers avoiding t-AP distance-sets Algebra and Discrete Mathematics |
| author_facet |
Ahmed, T. |
| author_sort |
Ahmed, T. |
| title |
On colouring integers avoiding t-AP distance-sets |
| title_short |
On colouring integers avoiding t-AP distance-sets |
| title_full |
On colouring integers avoiding t-AP distance-sets |
| title_fullStr |
On colouring integers avoiding t-AP distance-sets |
| title_full_unstemmed |
On colouring integers avoiding t-AP distance-sets |
| title_sort |
on colouring integers avoiding t-ap distance-sets |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2016 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/155741 |
| citation_txt |
On colouring integers avoiding t-AP distance-sets / T. Ahmed // Algebra and Discrete Mathematics. — 2016. — Vol. 22, № 1. — С. 1-10. — Бібліогр.: 1 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT ahmedt oncolouringintegersavoidingtapdistancesets |
| first_indexed |
2025-07-14T07:58:59Z |
| last_indexed |
2025-07-14T07:58:59Z |
| _version_ |
1837608406102310912 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 22 (2016). Number 1, pp. 1–10
© Journal “Algebra and Discrete Mathematics”
On colouring integers
avoiding t-AP distance-sets
Tanbir Ahmed
Communicated by V. A. Artamonov
Abstract. A t-AP is a sequence of the form a, a + d, . . . ,
a+(t−1)d, where a, d ∈ Z. Given a finite set X and positive integers
d, t, a1, a2, . . . , at−1, define ν(X, d) = |{(x, y) : x, y ∈ X, y > x,
y − x = d}|, (a1, a2, . . . , at−1; d) = a collection X s.t. ν(X, d ·i) > ai
for 1 6 i 6 t − 1.
In this paper, we investigate the structure of sets with bounded
number of pairs with certain gaps. Let (t − 1, t − 2, . . . , 1; d) be
called a t-AP distance-set of size at least t. A k-colouring of inte-
gers 1, 2, . . . , n is a mapping {1, 2, . . . , n} → {0, 1, . . . , k − 1} where
0, 1, . . . , k − 1 are colours. Let ww(k, t) denote the smallest posi-
tive integer n such that every k-colouring of 1, 2, . . . , n contains a
monochromatic t-AP distance-set for some d > 0. We conjecture
that ww(2, t) > t2 and prove the lower bound for most cases. We also
generalize the notion of ww(k, t) and prove several lower bounds.
1. Introduction
A t-AP is a sequence of the form a, a + d, . . . , a + (t − 1)d, where
a, d ∈ Z. For example, 3, 7, 11, 15 is a 4-AP with a = 3 and d = 4.
Given a finite set X and positive integers d, t, a1, a2, . . . , at−1, define
ν(X, d) = |{(x, y) : x, y ∈ X, y > x, y − x = d}|,
(a1, a2, . . . , at−1; d) = a collection X s.t. ν(X, d · i) > ai for 16 i6 t−1.
2010 MSC: Primary 05D10.
Key words and phrases: distance sets, colouring integers, sets and sequences.
2 On colouring integers avoiding t-AP distance-sets
The t-AP {x, x + d, . . . , x + (t − 1)d} (say T ) has ν(T, d · i) = t − i for
1 6 i 6 t − 1. On the other hand, a set (t − 1, t − 2, . . . , 1; d) (say Y ) has
ν(Y, d · i) > t − i for 1 6 i 6 t − 1, but not necessarily contains a t-AP.
A k-colouring of integers 1, 2, . . . , n is a mapping {1, 2, . . . , n} →
{0, 1, . . . , k − 1} where 0, 1, . . . , k − 1 are colours. Let ww(k, t) denote the
smallest integer n such that every k-colouring of 1, 2, . . . , n contains a
monochromatic set (t − 1, t − 2, . . . , 1; d) for some d > 0. Here, (t − 1, t −
2, . . . , 1; d) is a t-AP distance-set of size at least t. The existence of ww(k, t)
is guaranteed by van der Waerden’s theorem [1]. Given positive integers k,
t, and n, a good k-colouring of 1, 2, . . . , n contains no monochromatic t-AP
distance set. We call such a good k-colouring, a certificate of the lower
bound ww(k, t) > n. We write a certificate as a sequence of n colours each
in {0, 1, . . . , k − 1}, where the i-th (i ∈ {1, 2, . . . , n}) colour corresponds
to the colour of the integer i.
A certificate of lower bound ww(k, t) > n that avoids a monochro-
matic arithmetic progression, may still be invalid, since it may contain a
monochromatic distance set. For example, while looking for a certificate
of lower bound of ww(2, 4), if the set X = {1, 2, 3, 5, 9, 10} (which does
not contain a 4-AP) is monochromatic, then the colouring is “bad” as
ν(X, 1) = 3, ν(X, 2) = 2, and ν(X, 3) = 1.
In this paper, we perform computer experiements to observe the
patterns of certificates of ww(k, t) > n. We conjecture that ww(2, t) > t2
and prove the lower bound for most cases. We also generalize the notion
of ww(k, t) and provide several lower bounds.
2. Some values and bounds
With a primitive computer search algorithm, we have computed the
following values and bounds of ww(k, t). Theorem 1 gives a lower bound
for ww(k, t). A computed lower bound is presented only if it improves
over the bound given by Theorem 1.
Theorem 1. Given k > 2, t > 3, if t 6 2k + 1, then
ww(k, t) > k(t − 1)(t − 2).
Proof. Let n = k(t − 1)(t − 2) and consider the colouring
f : {1, 2, . . . , n} → {0, 1, . . . , k − 1}.
Let Xi = {x ∈ X : f(x) = i}. Take the certificate
(0t−11t−1 · · · (k − 1)t−1)t−2.
T. Ahmed 3
Table 1. ww(k, t)
k/t 3 4 5 6 7 8
2 9 19 33 43 64 85
3 17 39 > 56 > 67 > 97 > 121
4 33 > 70 > 85 > 102 > 134
5 > 44 > 86 > 135 > 141 > 181 > 242
6 > 56 > 106 > 175 > 221 > 254 > 287
7 > 73 > 142 > 214 > 278 > 298 > 380
8 > 91 > 168 > 246 > 338 > 390 > 484
9 > 115 > 198 > 302 > 398 > 478 > 567
10 > 127 > 233 > 365 > 464 > 558 > 691
11 > 146 > 275 > 417 > 581 > 672 > 806
12 > 157 > 315 > 474 > 649 > 769 > 927
13 > 174 > 337 > 550 > 760 > 840 > 1085
14 > 198 > 405 > 594 > 828 > 949 > 1220
15 > 229 > 434 > 666 > 904 > 1087 > 1334
16 > 230 > 493 > 784 > 1015 > 1236 > 1517
17 > 270 > 525 > 849 > 1082 > 1375 > 1676
18 > 298 > 589 > 932 > 1211 > 1509 > 1841
19 > 337 > 629 > 988 > 1338 > 1635 > 2027
20 > 348 > 689 > 1098 > 1445 > 1850 > 2249
21 > 364 > 756 > 1179 > 1561 > 2014 > 2487
22 > 401 > 824 > 1288 > 1701 > 2153 > 2632
23 > 422 > 890 > 1354 > 1868 > 2249 > 2820
24 > 476 > 948 > 1459 > 1952 > 2563 > 3107
25 > 500 > 1033 > 1592 > 2125 > 2746 > 3284
We show that for each d, there exists j with 1 6 j 6 t − 1 such that
ν(Xi, d · j) < t − j for each i ∈ {0, 1, . . . , k − 1}. The largest difference
between two monochromatic numbers in the certificate is
n − (k − 1)(t − 1) − 1 = (t − 1)(k(t − 2) − k − 1) − 1 < k(t − 1)(t − 3).
Since the existence of a monochromatic set (t − 1, t − 2, . . . , 1; d) in X
requires ν(Xi, d · (t − 1)) > 1, we have d < k(t − 3). We have the following
cases:
(a) 1 6 d 6 k − 1: Take x, y ∈ {1, 2, . . . , n} such that y = x + d(t − 1).
But by our choice of d, we have f(y) = (f(x) + d) mod k 6= f(x), that
is, x and y cannot be monochromatic. So, ν(Xi, (t − 1) · d) = 0 < 1 for
each i ∈ {0, 1, . . . , k − 1}.
(b) k 6 d 6 t − 3: Take x, y ∈ {1, 2, . . . , n} such that y = x + d(t − a)
where a is such that (t − 3)(t − a) 6 (t − 1)(k − 1) and k(t − a) > k, which
4 On colouring integers avoiding t-AP distance-sets
gives us a bound
t −
(t − 1)(k − 1)
t − 3
6 a 6 t − k.
Such an a exists since
(t − 1)(k − 1)
t − 3
= k − 1 +
2(k − 1)
t − 3
> k − 1 +
2(k − 1)
(2k + 1) − 3
> k.
(c) d = t − 2: In each block of t − 1 colours, there is one pair of
integers at distance t − 2, and there are t − 2 such blocks for each colour.
So, ν(Xi, 1 · d) = ν(X, t − 2) = t − 2 < t − 1 for each i ∈ {0, 1, . . . , k − 1}.
(d) (t − 1) 6 d 6 (k − 1)(t − 1): Take x, y ∈ {1, 2, . . . , n} such that
y = x + d = x + q(t − 1) + r where 1 6 q 6 k − 1 and 0 6 r 6 t − 2.
Suppose x = qx(t − 1) + rx with 0 6 rx 6 t − 2. Then
f(x) = qx mod k;
f(y) = (f(x) + q + ⌊(r + rx)/(t − 1)⌋) mod k.
If r > 0, then q 6 k−2, which implies q+⌊(r+rx)/(t−1)⌋ 6 (k−2)+1 =
k − 1. If r = 0, then q 6 k − 1, which implies q + ⌊(0 + rx)/(t − 1)⌋ 6
(k − 1) + 0 = k − 1. Therefore, f(y) 6= f(x); and x and y cannot be
monochromatic. So, ν(Xi, d · 1) = 0 < t − 1 for each i ∈ {0, 1, . . . , k − 1}.
Since t 6 2k + 1, we have
d < k(t − 3) = kt − 3k = (kt − k − 2k)
6 (kt − k − (t − 1)) = (k − 1)(t − 1).
Hence, we are done and there is no monochromatic t-AP distance set
in X.
Conjecture 1. For t > 3, ww(2, t) > t2.
Lemma 1. For t > 3 and t 6= 2u with u > 2, ww(2, t) > t2.
Proof. Let t = 2u + v with 1 6 v 6 2u − 1. Let n = t2 − 1 and X =
{1, 2, . . . , n}, and consider the colouring f : X → {0, 1}. Let m = n − 1 −
(t − 1) = q · 2u + r with 0 6 r 6 2u − 1.
Now, take the certificate
{
01t−1(02u
12u
)q/20r, if q ≡ 0 (mod 2);
01t−1(02u
12u
)⌊q/2⌋02u
1r, if q ≡ 1 (mod 2).
T. Ahmed 5
We need to show that for each d, there exists j with 1 6 j 6 t − 1
such that ν(X, d · j) < t − j. Since the existence of a monochromatic
set (t − 1, t − 2, . . . , 1; d) in X requires ν(X, d · (t − 1)) > 1, we have
d(t − 1) < t2 − 1, that is, 1 6 d 6 t. Let Xi = {x ∈ X : f(x) = i}.
Suppose q ≡ 0 (mod 2). Then we have the following two cases:
(a) d ≡ 1 (mod 2): Take x, y ∈ X such that y = x + d · 2u.
(a1) v + 1 6 x < y 6 n − r: Since f(x) ∈ {0, 1} and f(x + 1 · 2u) =
(f(x) + 1) mod 2 6= f(x), we have f(y) = f(x + d · 2u) 6= f(x). So, two
monochromatic integers cannot both be in {v + 1, v + 2, . . . , n − r}.
(a2) 2 6 x 6 v and y 6 n − r: Since f(x) = 1 and f(x + 1 · 2u) =
1 = f(x), we have f(y) = (x + d · 2u) = f(x). So, there are exactly v − 1
pairs of integers with colour 1 at distance d · 2u.
(a3) x = 1 and y 6 n − r: Since f(x) = 0, f(x + 1 · 2u) = 1 6= f(x),
and 1 + 2u > v, using case (i) we have 0 pair of integers with colour 0 at
distance d · 2u.
(a4) x > 1 and n − r + 1 6 y 6 n: Since f(y) = 0 and r < 2u, we
have f(y − 1 · 2u) = 1, which implies f(y − d · 2u) = 1 6= f(y). That is,
adding r trailing zeros does not change the number of monochromatic
pairs at distance d · 2u.
Therefore, for each i ∈ {0, 1}, we have ν(Xi, d·2u) 6 v−1 < v = t−2u.
(b) d ≡ 0 (mod 2): Let d = 2w · do, with do being an odd num-
ber and w > 1. Then ν(Xi, d · 2u−w) = ν(Xi, do · 2u) 6 v − 1 < v =
t − 2u (by case (i)) for each i ∈ {0, 1}.
The case q ≡ 1 (mod 2) is similar.
Lemma 2. Suppose t = 2u for some u > 2 and t − 1 is prime. Then for
each r ∈ {1, 2, . . . , u} and for each do ∈ {1, 3, . . . , 2u−r − 1}, there exists
s ∈ {1, 2, 3, . . . , do − 1} such that do divides s(t − 1) − 2u−r.
Proof. Since t − 1 is prime, we have gcd(t − 1, do) = 1, and hence the
linear congruence (t − 1)s ≡ 2u−r (mod do) has a solution. Extended
Euclid Algorithm yields x, y ∈ Z such that (t − 1) · x + do · y = 1. Then
s = (x · 2u−r) mod do. Since do 6 |x and do 6 |2u−r, we have s 6= 0. Hence
s ∈ {1, 2, . . . , do − 1}.
Lemma 3. If t = 2u for u > 2 with t − 1 prime, then ww(2, t) > t2.
Proof. Take the certificate 0(1t−10t−1)t/21t−2. We have the following two
cases:
(a) d ≡ 1 (mod 2): Take x, y ∈ X such that y = x + d · (t − 1).
6 On colouring integers avoiding t-AP distance-sets
(a1) 2 6 x 6 t2 − t + 1 = n − (t − 2): Since f(x) ∈ {0, 1} and
f(x + 1 · (t − 1)) = (f(x) + 1) mod 2 6= f(x), we have f(y) = f(x +
d · (t − 1)) 6= f(x). So, two monochromatic integers cannot both be in
{2, 3, . . . , n − (t − 2)}.
(a2) x = 1 and y 6 n− (t−2): Since f(x) = 0, f(x+1 · (t−1)) = 1 6=
f(x), using case (i) we have 0 pair of integers with colour 0 at distance
d · (t − 1).
(a3) x > 1 and n − (t − 2) + 1 6 y 6 n: Since f(y) = 0, we have
f(y − 1 · (t − 1)) = 1, which implies f(y − d · (t − 1)) = 1 6= f(y). That is,
adding t − 2 trailing ones does not change the number of monochromatic
pairs at distance d · (t − 1).
Therefore, for each i ∈ {0, 1}, we have ν(Xi, d · (t − 1)) = 0 < 1.
(b) d ≡ 0 (mod 2): For d ∈ {2, 4, . . . , t} and j ∈ {1, 2, . . . , t − 1},
2 6 d · j 6 t(t − 1) = t2 − t.
For a given d ∈ {2, 4, . . . , t}, we show that there exists (j, w) with
j ∈ {1, 2, . . . , t−1} and w ∈ {1, 3, 5, . . . , t−1} such that d·j = w(t−1)−1.
In that case, since d ·j 6 t(t−1), we have w 6 t; and also since d ·j is even,
w(t − 1) is odd, which implies w is odd, that is, w ∈ {1, 3, 5, . . . , t − 1}.
Let d = 2rdo with 1 6 r 6 u and odd number do ∈ {1, 3, . . . , 2u−r −1}
(since d 6 t = 2u). For a w to exist and satisfy d ·j = w(t−1)−1, we need
2rdo · j = w(t − 1) − 1 = wt − (w + 1),
that is, 2r divides w + 1 (since 2r divides wt = w2u). Let w = s · 2r − 1
with s ∈ {1, 2, . . . , do −1}. The chosen s requires to satisfy that do divides
(w(t − 1) − 1)/2r = s(t − 1) − 2u−r. By Lemma 2, such an s exists.
It can be observed that for a given d ∈ {2, 4, . . . , t}, if d · j1 = w1 · (t −
1) − 1 for some j1 ∈ {1, 2, 3, . . . , t − 1} and w1 ∈ {1, 3, 5, . . . , t − 1}, then
d · j2 = w2 · (t − 1) + 1,
with j1 + j2 = t − 1 and w1 + w2 = d. We claim that ν(X1, d · ti) < t − ji
for at least one i ∈ {1, 2}. If ν(X1, d · j1) < t − j1, then we are done.
Suppose
ν(X1, d · j1) = ν(X1, w1(t − 1) − 1) =
t
2
−
w1 − 1
2
> t − j1,
which implies t/2 + (w1 − 1)/2 6 j1. Now,
ν(X1, d · j2) = ν(X1, w2(t − 1) + 1) =
t
2
−
w2 − 1
2
=
t
2
−
d − w1 − 1
2
=
t
2
+
w1 − 1
2
+1−
d
2
6 j1+1−
d
2
= t−1−j2+1−
d
2
< t−j2.
T. Ahmed 7
Similarly, we can show that ν(X0, d·j)<t−j for some j ∈{1, 2, . . . , t − 1}.
3. Generalized distance-sets
Here we consider variants of ww(k, t) with different variations of
parameters in a distance set.
Let gww(k, t; a1, a2, . . . , at−1) (with ai > 1) denote the smallest posi-
tive integer n such that any k-colouring of 1, 2, . . . , n contains monochro-
matic set (a1, a2, . . . , at−1; d) for some d > 0. In this definition,
gww(k, t; t − 1, t − 2, . . . , 1) = ww(k, t).
Observation 1. Let us write gww(2, t; a1, a2, . . . , at−1) as gww(2, t, r),
where ai = r for 1 6 i 6 t − 1. It is trivial that gww(2, t, t−1) > ww(2, t).
Table 2 contains a few computed values of gww(2, t, r).
Table 2. gww(2, t, r)
t/r 1 2 3 4 5 6 7 8
3 9 13
4 13 21 29
5 33 37 41 49
6 41 45 57 65 74
7 49 53 69 85 92 > 96
8 57 61 85 105 114 > 118 > 123
9 129 133 137 > 140 > 144 > 148 > 152 > 156
10 145 149 153
11 161 165 169
12 177 181 185
13 193 197 > 200
14 209 213 > 216
15 225 229 > 232
16 241 245 > 248
17 513 > 516
33 > 2048 > 2052
65 > 8192
Lemma 4. For u > 1 and 1 6 v 6 2u,
gww(2, 2u + v, 1) > (2u + v − 1)2u+1 + 1.
Proof. Consider t = 2u+v (t > 5) and let n = (2u+v−1)2u+1 = (t−1)2u+1
and X = {1, 2, . . . , n}. Consider the colouring f : X → {0, 1} and take
the certificate (02u
12u
)t−1.
8 On colouring integers avoiding t-AP distance-sets
Let Xi = {x ∈ X : f(x) = i}. We claim that this 2-colouring of X
does not contain a monochromatic set (1, 1, . . . , 1; d) for any d > 0, that
is, for each d with 1 6 d < 2u+1 and for each i ∈ {0, 1}, there exists
j ∈ {1, 2, . . . , t − 1} such that ν(Xi, d · j) = 0.
(a) d ≡ 1 (mod 2): Take x, y ∈ X such that y = x + d · 2u. Since
d is odd, if f(x) = 0, then f(x + d · 2u) = 1 and vice-versa. Hence,
ν(Xi, d · 2u) = 0 for each i ∈ {0, 1}
(b) d ≡ 0 (mod 2): Let d = 2w · do, with do being an odd number and
w > 1. Then for each i ∈ {0, 1},
ν(Xi, d · 2u−w) = ν(Xi, do · 2u) = 0 (by case (a)).
So, X does not contain a monochromatic set (1, 1, . . . , 1; d) for any d > 0.
Conjecture 2. For u > 1 and 1 6 v 6 2u,
gww(2, 2u + v, 1) = (2u + v − 1)2u+1 + 1.
Lemma 5. For u > 2 and 1 6 v 6 2u,
gww(2, 2u + v, 2) > (2u + v − 1)2u+1 + 5.
Proof. Let t = 2u + v (t > 5), n = (2u + v − 1)2u+1 + 4 = (t − 1)2u+1 + 4,
and X = {1, 2, . . . , n}. Consider the colouring f : X → {0, 1} and
take the certificate 000(102u−311012u−300)t−2(102u−311)(012u−3)011. We
show that this colouring of X does not contain a monochromatic set
(2, 2, . . . , 2; d) for any d > 0, that is, for each d with 1 6 d 6 2u+1 and for
each i ∈ {0, 1}, there exists j ∈ {1, 2, . . . , t − 1} such that ν(Xi, d · j) 6 1.
Note that the largest difference between two integers with colour 0 in
the colouring is (n − 2) − 1 = n − 3 = (t − 1) · 2u+1 + 1 = p (say); and
the largest difference between two integers with colour 1 in the colouring
is n − 4 = (t − 1) · 2u+1 = p − 1.
(a) d = 2u+1: Note that d · (t − 1) = (t − 1)2u+1 = n − 4 = p − 1. The
only pair (x, y) with f(x) = f(y) = 0 and y = x + d · (t − 1) is (1, n − 3)
and the only pair (x, y) with f(x) = f(y) = 1 and y = x + d · (t − 1) is
(4, n). Hence, we have ν(Xi, d · (t − 1)) = 1 for each i ∈ {0, 1}.
(b) d ≡ 1 (mod 2): Write the certificate as
000A0A1 . . . A2t−5, A2t−4C11,
where Ai = 102u−311 if i ≡ 0 (mod 2), Ai = 012u−300 if i ≡ 1 (mod 2),
and C = 012u−30. Take x, y ∈ {4, 5, . . . , n−2u −2} such that y = x+d ·2u
T. Ahmed 9
for some odd d < 2u+1 + 1. Suppose x = 3 + i · 2u + j, that is, f(x) is the
j-th (1 6 j 6 2u) bit in Ai. Then y = 3 + (i + d) · 2u + j, that is, f(y) is
the j-th bit in Ai+d. If i ≡ 1 (mod 2), then (i + d) ≡ 0 (mod 2) (since d
is odd), and vice-versa. Therefore, f(x) 6= f(y). So, two monochromatic
integers at distance d · 2u cannot both be in {4, 5, . . . , n − 2u − 2}.
Now, take x, y ∈ {4, 5, . . . , n−2} such that y = x+d ·2u and y ∈ {n−
2u−1, n−2u, . . . , n−2}. Since |C| < 2u, x must be in {4, 5, . . . , n−2u−2}.
With similar reasoning as above, it can be shown that two monochromatic
integers at distance d · 2u cannot both be in {4, 5, . . . , n − 2}. Following
are the remaining cases:
(b1) If x = 1, then x+d·2u = 3+d·2u−2 = 3+(d−1)·2u+(2u−2) = y
(say). We have f(x) = 0. Again (2u − 2)-th bit in Ad−1 is also zero since
d is odd and Ad−1 = 102u−311.
(b2) If x = 2, 3 (where f(x) = 0), then with similar reasoning as
above, f(x + d · 2u) = 1.
(b3) If y = n − 1 (where f(y) = 1), then
y − d · 2u = (t − 1)2u+1 + 3 − d · 2u
= 3 + (2t − 3 − d)2u + 2u = x (say).
Since d is odd, 2t − 3 − d is even, that is, A2t−3−d = 102u−311. The 2u-th
element in A2t−3−d is one, that is f(x) = 1.
(b4) If y = n (where f(y) = 1), then
y − d · 2u = (t − 1)2u+1 + 4 − d · 2u
= 3 + (2t − 2 − d)2u + 1 = x (say).
Since d is odd, 2t − 2 − d is odd, that is, A2t−2−d = 012u−300. The 1-st
element in A2t−2−d is zero, that is f(x) = 0.
Hence ν(Xi, d · 2u) 6 1 for each i ∈ {0, 1}.
(c) Otherwise (d 6= 2u+1 and d ≡ 0 (mod 2)): Let d = 2w · do, with
do being an odd number and w > 1. Then for each i ∈ {0, 1},
ν(Xi, d · 2u−w) = ν(Xi, do · 2u) 6 1 (by case (b)).
Therefore, X does not contain a monochromatic set (2, 2, . . . , 2; d) for
any d > 0.
Conjecture 3. For r > 2 and t > 2r + 1,
gww(2, t, r) = (t − 1)2⌊log
2
(t−1)⌋+1 + 2r + 1.
10 On colouring integers avoiding t-AP distance-sets
Observation 2. We observe the following experimental results:
(a) Primitive search gives gww(2, 10, 9) > 186;
(b) Using the certificate
{
01t+1(0t−11t−1)t/2+1, if t ≡ 0 (mod 2);
01t+1(0t−11t−1)⌊t/2⌋+10t−1, if t ≡ 1 (mod 2),
we obtain the following lower bounds with 12 6 t 6 48:
gww(2, 12, 11) > 168, gww(2, 14, 13) > 224, gww(2, 17, 16) > 323,
gww(2, 18, 17) > 360, gww(2, 20, 19) > 440, gww(2, 24, 23) > 624,
gww(2.30, 29) > 960, gww(2, 32, 31) > 1088, gww(2, 33, 32) > 1155,
gww(2, 38, 37) > 1520, gww(2, 42, 41) > 1848, gww(2, 44, 43) > 2024.
(c) 035(118018)2120017(119018)511901712001014 proves gww(2, 19, 18) > 399.
(d) 041121021(122021)10115 proves gww(2, 22, 21) > 528.
Conjecture 4. For t > 4, gww(2, t, t − 1) > (t + 1)2.
Conjecture 5. For t > 5, gww(2, t, t − 1) < 2t+1.
We do not have enough data to make stronger upper bound conjecture
for gww(2, t, t − 1), but it may be possible that gww(2, t, t − 1) < t3.
Acknowledgements
The author would like to thank Hunter Snevily (deceased) for sug-
gesting the problem, Clement Lam and Srecko Brlek for their support,
and Andalib Parvez for carefully reading the manuscript.
References
[1] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Archief voor
Wiskunde, 15 (1927), 212–216.
Contact information
T. Ahmed Laboratoire de Combinatoire et d’Informatique
Mathématique, UQAM, Montréal, Canada
E-Mail(s): tanbir@gmail.com
Received by the editors: 05.10.2015
and in final form 15.01.2016.
|