Two Erdős problems on lacunary sequences: chromatic number and Diophantine approximation

Abstract: Let

n_{k}

be an increasing lacunary sequence, i.e.,

n_{k + 1} / n_{k} > 1 + r

for some

r > 0

. In 1987, P. Erdos asked for the chromatic number of a graph

G

on the integers, where two integers

a, b

are connected by an edge iff their difference

| a - b |

is in the sequence

n_{k}

. Y. Katznelson found a connection to a Diophantine approximation problem (also due to Erdos): the existence of

x

in

(0, 1)

such that all the multiples

n_{j} x

are at least distance

d e l t a (x) > 0

from the set of integers. Katznelson bounded the chromatic number of

G

by

C r^{- 2} | l o g r |

. We apply the Lov'asz local lemma to establish that

d e l t a (x) > c r | l o g r |^{- 1}

for some

x

, which implies that the chromatic number of

G

is at most

C r^{- 1} | l o g r |

. This is sharp up to the logarithmic factor.

Recommendations

Cited in

(17)

This page was built for publication: Two Erdős problems on lacunary sequences: chromatic number and Diophantine approximation