5
$\begingroup$

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)

$\endgroup$
2
  • 4
    $\begingroup$ For the second part use Weyl's equidistribution theorem which shows that the limit is $1-\alpha N$. $\endgroup$
    – Lucia
    Aug 27, 2014 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, 2014 at 1:00

1 Answer 1

7
$\begingroup$

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 alternative proof for the first paragraph, since $1-(1-\alpha)=\alpha$.

$\endgroup$
2
  • 1
    $\begingroup$ This is a wonderful explanation. Thank you very much. $\endgroup$
    – Darío G
    Aug 27, 2014 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$ Nov 19, 2014 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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