×

A partition of the non-negative integers, with applications. (English) Zbl 1104.11009

The paper discusses explicit colourings of the non-negative integers and van der Waerden type questions.
Let \(A=\{a_1, a_2, \dots , a_n \}\) with \(a_1 < a_2 < \ldots < a_n\) be a set of non-negative integers. Let \(gs (A)= \max (a_{j+1}-a_j: 1 \leq j \leq n-1)\) be the largest gap size. Decompose the binary representation of \(n\) as follows: \(n= \sum_{i \text{ odd}} 2^i + \sum_{ i \text{ even}} 2^i\). Define a colouring of the integers by \(f(n)=\sum_{i \text{ odd}} 2^i\), where the empty sum corresponds to \(0\).
The author proves: for every finite set of non-negative integers \(A\): \[ \frac{1}{4} \sqrt{\frac{| A |}{gs (A)} } < | f(A)| < 4 \sqrt{ | A | gs (A) }. \] It follows that for the above colouring \(f\) there do not exist a fixed \(d\) and arbitrarily large sets \(A\) with gap size \(d\) on which \(f\) is either constant or takes \(| A |\) distinct values.

MSC:

11B25 Arithmetic progressions
05D10 Ramsey theory
PDFBibTeX XMLCite
Full Text: EuDML EMIS