MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\alpha$ be an irrational with $0<\alpha<1$. Consider the function given by \begin{align*} f: &\mathbb{N}\longrightarrow \mathbb{N}\\ &x\longmapsto [ \alpha\cdot x]\end{align*} where $[r]$ is the largest integer that is less than or equal to $r$ for $r\in\mathbb{R}$.

Let $N=\left[\frac{1}{\alpha}\right]$ be the integer part of $\frac{1}{\alpha}$, and consider the following numbers:

$A_1(n)=\#\{k\leq n : f(k)<f(k+1)\}$

$A_2(n)=\#\{k\leq n : f(k)=f(k+N)\}$

The questions are the following:

1) Is it true that $\displaystyle{\lim_{n\to\infty} \dfrac{A_1(n)}{n}=\alpha}$?

2) What is the value of $\displaystyle{\lim_{n\to\infty} \dfrac{A_2(n)}{n}}$, if it exists?

The problem above came out when I was trying to find examples of classes of finite ordered structures that satisfies strong conditions on their definable sets (for my Ph.D. Thesis). I translated the problem in simple terms, and I would really appreciate any help.

(If it is too easy, a hint will be good. If the problem is related with something in number theory, combinatorics, ergodic theory or anything else, I would also appreciate if you tell me how)

share|cite|improve this question
For the second part use Weyl's equidistribution theorem which shows that the limit is $1-\alpha N$. – Lucia Aug 27 '14 at 0:57
@Lucia: I just wrote the same. But you probably beat me by a minute or so. – GH from MO Aug 27 '14 at 1:00
up vote 6 down vote accepted

The answer to the first question is: yes. The function $f(x)$ jumps $0$ or $1$ at every integer (because $0\leq\alpha\leq 1$), and also $f(0)=0$, hence $A_1(n)=f(n+1)$. Therefore $$\frac{A_1(n)}{n}=\frac{[(n+1)\alpha]}{n}=\frac{n\alpha+O(1)}{n}=\alpha+O\left(\frac{1}{n}\right)=\alpha+o(1). $$

Regarding the second question: the limit exists and equals $1-N\alpha$. Indeed, $f(k+N)=[k\alpha+N\alpha]$, hence $f(k)=f(k+N)$ means that the fractional part of $k\alpha$ is less than $1-N\alpha$. Here we used that $0<N\alpha<1$. As $\alpha$ is irrational, the fractional parts of $k\alpha$ are equidistributed in $(0,1)$ by Weyl's theorem, hence the density of $k$'s with $f(k)=f(k+N)$ equals the length of the interval $(0,1-N\alpha)$ which is $1-N\alpha$.

More generally, if $1\leq M\leq N$ is fixed, then the density of $k$'s with $f(k)=f(k+M)$ equals $1-M\alpha$. In particular, the case $M=1$ yields an alternate proof for the first paragraph, since $1-(1-\alpha)=\alpha$.

share|cite|improve this answer
This is a wonderful explanation. Thank you very much. – Wore Aug 27 '14 at 2:40
The sequence $[n\alpha]$ is known as a Beatty sequence; the indicator function of a Beatty sequence (with irrational $\alpha$) is known as a Sturmian word. There are hundreds of papers working out properties of Beatty sequences. – Kevin O'Bryant Nov 19 '14 at 6:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.