Estimating $\#\{\{\alpha k\} < 1/\sqrt{k} : k \leq n\}$ for irrational $\alpha$ Suppose $\{\alpha n\}$ is the fractional part of $\alpha n$. Put
$$A_{\alpha}(n) = \#\{\{\alpha k\} < 1/\sqrt{k} : k \leq n\}.$$
If $\alpha$ is irrational, can I find some constant $K$ such that $A_{\alpha}(n) < K \sqrt{n}$ for all $n$? Does the order of $A_{\alpha}(n)$ depend on $\alpha$? Suppose $1/\sqrt{k}$ is replaced by some function $f(k)$. What can I say about the number of $\{\alpha n\}$ less than $f(n)$ as $n$ tends to infinity?
 A: The Weyl equidistribution theorem says that for irrational $\alpha$ and sufficiently many $k$, the fractional parts $\{\alpha k\}$ will be equidistributed in the interval $[0,1]$.
To apply this to your particular problem, consider a large interval $k\in[N,2N]$. Because of equidistribution, the numbers $k$ will "hit" the condition $\{\alpha k\} < 1/\sqrt{N}$ roughly $1/\sqrt{N}$ of the time, i.e. there will be roughly $N·1/\sqrt{N} = \sqrt{N}$ numbers $k$ from the interval that fulfill the condition.
Of course, we are actually interested in the condition $\{\alpha k\} < 1/\sqrt{k}$, so we have overestimated things a bit, but it will still work out.
Now, piecing intervals together by choosing $N=2^M$ as a sequence of powers of two, we obtain an estimate along the lines of
$$A_\alpha(n=2^M) \lesssim \sqrt{1} + \sqrt{2^1} + \sqrt{2^2} + .. + \sqrt{2^{M-1}} \leq K \sqrt{2}^M = K\sqrt{n} $$
as desired. You might have to fill in some epsilons and stuff to make the proof precise, but this is the core argument.
In the general case, a similar argument will yield a good bound as long as the function $f(k)$ doesn't vanish too fast. If it does vanish very fast, then it can only get better, though a better bound might be harder to prove.
