Amount of real numbers, in a given sequence, whose fractional part lies in a given closed interval

Question

Fix an interval $[a,b] \subset [0,1]$ and let $S$ be a given sequence of real numbers. Are there any ad-hoc methods that may be used to estimate $$ T := \#\{ s \in S \ : \ \{s\} \in [a,b]\}? $$ Here $\{s\} := s - \lfloor s \rfloor$ denotes the fractional part of $s$. I have some ideas but I'm not sure these will be useful. Perhaps some of you have seen these things before?

For example suppose that $S = (f(n))_{n \in [1,N] \cap \mathbb{Z}}$ for some smooth function $f : \mathbb{R} \to \mathbb{R}$ (you may think of an easy example for $f$; I'm interested in a general methodology here) and some positive integer $N$. Now $$ T = \sum_{n=1}^N 1_{[a,b]}(\{f(n)\}). $$ A possible direction here (but I don't know if this strategy could work) could be to introduce a smooth bump or cuttoff function $\phi$ supported on $[a,b]$ and approximate $T$ by $$ T_\phi = \sum_{n=1}^N \phi(\{f(n)\}). $$ Since $f,\phi$ are smooth and the function $\{x\}$ is differentiable on $\mathbb{R}\setminus \mathbb{Z}$, then, assuming $f(x) \in \mathbb{Z}$ for only finitely many $x \in [1,N]$, (I think) one could use the Euler-Maclaurin formula to express $T_\phi$ as an integral on $[1,N]$. Then hopefully use what is known about integrals involving the fractional-part function (see here for instance http://www.springer.com/cda/content/document/cda_downloaddocument/9781461467618-c1.pdf?SGWID=0-0-45-1446028-p174908973) to get an estimate. Do you think this approach might work? Have you seen these types of things before? It would be interesting if you know some examples. For instance what cutt-off functions could be useful here? Thanks!

Answer 1

The most common approach is to use Fourier analysis.

Start with your sum $$T_\phi = \sum_{n=1}^N \phi(\{f(n)\}).$$ We may replace $\phi$ by a $1$-periodic function on $\mathbb{R}/\mathbb{Z}$, since the fractional parts function is $1$-periodic. Thus, we wish to estimate $$T_\phi = \sum_{n=1}^N \phi(f(n)).$$ Since $\phi$ is periodic and smooth, it has a Fourier series whose coefficients have nice decay properties. The zero frequency will give the main term, and the nonzero frequencies should contribute to the error term.

Showing the the contribution of the nonzero frequencies is small requires showing the relevant exponential sums are small (i.e. exhibit cancellation). The sums to estimate look like $$\sum_{n=1}^N e^{2\pi i h f(n)},$$ for some $h \neq 0$.

Let's give a sketch of how this works for a specific example. Let $[a,b] \subset [0,1]$ be a fixed interval, and suppose we wish to study $$F := \sum_{n = 1}^N \textbf{1}(a \leq \{\sqrt{n}\} \leq b).$$ We let $\phi$ be a smooth function supported on $[a,b]$ which is equal to $1$ on $[a+\epsilon,b - \epsilon]$, and extend $\phi$ by periodicity. Therefore $\phi$ has a Fourier series $$\phi(x) = \sum_{h \in \mathbb{Z}} c_h e(hx),$$ where $e(y) = e^{2\pi i y}$ and $$c_h = \int_0^1 \phi(t) e(-ht)dt.$$ Integration by parts shows $$|c_h| \ll_j (1+|h|)^{-j}$$ for all $j \geq 0$.

We now return to studying $F$. We have $$F \geq \sum_{n=1}^N \phi(\sqrt{n}),$$ and expanding $\phi$ in its Fourier series yields $$F \geq \widehat{\phi}(0) N + \sum_{h \neq 0} c_h \sum_{n=1}^N e(h \sqrt{n}).$$ We can study the exponential sum $$\sum_{n=1}^N e(h \sqrt{n}), \ \ \ \ \ \ h \neq 0,$$ by Euler-Maclaurin summation. Indeed, we have $$\sum_{n=1}^N e(h \sqrt{n}) = \int_1^N e(h\sqrt{t})dt + 2\pi i h \int_1^N \frac{\{t\}e(h\sqrt{t})}{\sqrt{t}}dt + O(1),$$ which implies $$\sum_{n=1}^N e(h \sqrt{n}) \ll \frac{N^{1/2}}{|h|} + |h| N^{1/2}.$$ Upon summing over $h$ we obtain $$F \geq \widehat{\phi}(0) N + O(N^{1/2}) \geq (b-a-2\epsilon) N + O(N^{1/2}).$$

We may handle an upper bound for $F$ in an entirely similar fashion. Letting $\epsilon \rightarrow 0$ slowly, we get $$F = \sum_{n = 1}^N \textbf{1}(a \leq \{\sqrt{n}\} \leq b) \sim (b-a)N$$ as $N \rightarrow \infty$.

Answer 2

I give a different method not involving Fourier analysis. It is based on mollifiers, which serve to smooth out rough functions such as indicators. For some background on mollifiers see for instance the wiki and these set of notes.

As a way of comparison with the Fourier analytic method described above by Kyle, let us treat again the example with $f(x) = \sqrt{x}$:

Fix real numbers $0\leq a < b < 1$ and consider $$ S := \#\{ 1 \leq n \leq N \ : \ a \leq \{\sqrt{n}\} \leq b\}. $$ Let $\chi$ be the characteristic function of the union $\bigcup_{1 \leq k \leq \sqrt{N}} [k+a, k+b]$ of intervals, where $k$ runs over the integers in $[1,\sqrt{N}]$. Then it is clear that $$ S = \sum_{n=1}^N \chi(\sqrt{n}). $$ For $\delta > 0$, let $\phi_\delta$ be the standard mollifier and let $$ \chi_\delta(x) := (\chi \ast \phi_\delta)(x) = \int_{\mathbb{R}} \chi(y)\phi_\delta(x - y)dy = \sum_{k \leq \sqrt{N}}\int_{k+a}^{k+b} \phi_\delta(x-y) dy $$ be a mollification of $\chi$. Note that $\chi_\delta$ is smooth for each $\delta > 0$, and $\chi_\delta(x)\to \chi(x)$ as $\delta \to 0^+$, for any $x \in \mathbb{R}$. Consequently $$ S_\delta := \sum_{n=1}^N \chi_\delta(\sqrt{n}) \to S $$ as $\delta \to 0^+$. Now since the function $\chi_\delta(\sqrt{x})$ is smooth in $x$ on the interval $[1,N]$, the Euler-Maclaurin summation formula gives \begin{align*} S_\delta &= \int_{1}^N \chi_\delta(\sqrt{x})dx + \dfrac{1}{2}\int_{1}^N \dfrac{\{x\}}{\sqrt{x}}\chi_\delta'(\sqrt{x}) dx + O(1)\\ &= 2\int_1^{\sqrt{N} }t\chi_\delta(t) dt + \int_{1}^{\sqrt{N}} \{t^2\}\chi_\delta'(t) dt + O(1). \end{align*} The $O(1)$ comes from the fact that $\chi_\delta(1) = O(1)$. Indeed, from the definition of $\chi_\delta$ one can show that $|\chi_\delta(c)| \leq 1$ uniformly for every $\delta > 0$ and every $c \in \mathbb{R}$. Since $\chi_\delta$ is absolutely bounded by 1 uniformly in $\delta > 0$, the dominated convergence theorem ensures that the first integral satisfies \begin{equation}\label{eqn: 0} 2\int_1^{\sqrt{N} }t\chi_\delta(t) dt \to 2\int_1^{\sqrt{N} }t\chi(t) dt \end{equation} as $\delta \to 0^+$. We have \begin{align*} 2\int_1^{\sqrt{N} }t\chi(t) dt &= 2\sum_{k \leq \sqrt{N}} \int_{k+a}^{k+b} t dt + O(1) \\ &= \sum_{k \leq \sqrt{N}}(2(b-a)k + b^2 - a^2) + O(1)\\ &= (b-a)N + O(\sqrt{N}). \end{align*}

Consider now the second integral. We have \begin{align*} \int_1^{\sqrt{N}}\{t^2\}\chi_\delta'(t)dt &= \int_1^{\sqrt{N}}\{t^2\}(\chi \ast \phi_\delta')(t)dt\\ &= \int_{1}^{\sqrt{N}} \{t^2\}\sum_{k \leq \sqrt{N}} \int_{k+a}^{k+b} \phi_\delta'(t-y) dy dt\\ &= \sum_{k \leq \sqrt{N}} \int_1^{\sqrt{N}}\{t^2\}(\phi_\delta(t - k - a) - \phi_\delta(t - k - b))dt\\ &= \sum_{k \leq \sqrt{N}} \int_1^{\sqrt{N}}\{t^2\}(\phi_\delta(k+a - t) - \phi_\delta(k+b - t))dt. \end{align*} The last equality uses the symmetry of $\phi_\delta$. Note that for each $k$, $$ \int_1^{\sqrt{N}}\{t^2\}(\phi_\delta(k+a - t) - \phi_\delta(k+b - t))dt = (h \ast \phi_\delta)(k+a) - (h \ast \phi_\delta)(k+b), $$ where $h$ is the function $h(x) = 1_{[1, \sqrt{N}]}(x) \cdot \{x^2\}$. It follows that \begin{align*} \lim_{\delta \to 0^+} \int_1^{\sqrt{N}}\{t^2\}\chi_\delta'(t)dt &= \sum_{k \leq \sqrt{N}} \lim_{\delta \to 0^+}((h \ast \phi_\delta)(k+a) - (h \ast \phi_\delta)(k+b))\\ &= \sum_{k \leq \sqrt{N}}(h(k+a) - h(k+b))\\ &= O(\sqrt{N}). \end{align*} Putting everything together we conclude that $S = (b-a)N + O(\sqrt{N})$.