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)

  • 3
    $\begingroup$ For the second part use Weyl's equidistribution theorem which shows that the limit is $1-\alpha N$. $\endgroup$ – Lucia Aug 27 '14 at 0:57
  • 1
    $\begingroup$ @Lucia: I just wrote the same. But you probably beat me by a minute or so. $\endgroup$ – GH from MO Aug 27 '14 at 1:00

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$.

| cite | improve this answer | |
  • $\begingroup$ This is a wonderful explanation. Thank you very much. $\endgroup$ – Darío G Aug 27 '14 at 2:40
  • 1
    $\begingroup$ 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. $\endgroup$ – Kevin O'Bryant Nov 19 '14 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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