Large Discrepancy In Homogenous Quasi-Arithmetic Progressions

We prove that the class of homogeneous quasi-arithmetic progressions has unbounded discrepancy. That is, we show that given any 2-coloring of the natural numbers and any positive integer D, one can find a real number α≥1 and a set of natural numbers of the form {0, [α], [2α], [3α], . . . , [kα]} so that one color appears at least D times more than the other color. This was already proved by Beck in 1983, but the proof given here is somewhat simpler and gives a better bound on the discrepancy.

Authors and Affiliations

1. Department of Computer Science, East Carolina University, Greenville, NC 27858, USA

   Robert Hochberg

Corresponding author

Correspondence to Robert Hochberg.

Reprints and permissions