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.
Збережено в:
| Опубліковано в: : | Algebra and Discrete Mathematics |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2016
|
| Онлайн доступ: | https://nasplib.isofts.kiev.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 |
nasplib_isofts_kiev_ua-123456789-155741 |
|---|---|
| record_format |
dspace |
| spelling |
Ahmed, T. 2019-06-17T11:37:31Z 2019-06-17T11:37:31Z 2016 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. https://nasplib.isofts.kiev.ua/handle/123456789/155741 In this paper, we investigate the structure of sets with bounded number of pairs with certain gaps. The author would like to thank Hunter Snevily (deceased) for suggesting the problem, Clement Lam and Srecko Brlek for their support,and Andalib Parvez for carefully reading the manuscript. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On colouring integers avoiding t-AP distance-sets Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
On colouring integers avoiding t-AP distance-sets |
| spellingShingle |
On colouring integers avoiding t-AP distance-sets Ahmed, T. |
| 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 |
| author |
Ahmed, T. |
| author_facet |
Ahmed, T. |
| publishDate |
2016 |
| language |
English |
| container_title |
Algebra and Discrete Mathematics |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| description |
In this paper, we investigate
the structure of sets with bounded number of pairs with certain gaps.
|
| issn |
1726-3255 |
| url |
https://nasplib.isofts.kiev.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 назв. — англ. |
| work_keys_str_mv |
AT ahmedt oncolouringintegersavoidingtapdistancesets |
| first_indexed |
2025-11-24T16:49:07Z |
| last_indexed |
2025-11-24T16:49:07Z |
| _version_ |
1850486962369069056 |
| 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.
|