Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
3  
For the second part use Weyl's equidistribution theorem which shows that the limit is $1-\alpha N$. –  Lucia Aug 27 at 0:57
1  
@Lucia: I just wrote the same. But you probably beat me by a minute or so. –  GH from MO Aug 27 at 1:00

1 Answer 1

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|improve this answer
    
This is a wonderful explanation. Thank you very much. –  user27454 Aug 27 at 2:40
1  
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 at 6:03

Your Answer

 
discard

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.