Bounds on $\sum {n ((\alpha n))}$ where $((x))$ is the sawtooth function - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:34:19Z http://mathoverflow.net/feeds/question/17132 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17132/bounds-on-sum-n-alpha-n-where-x-is-the-sawtooth-function Bounds on $\sum {n ((\alpha n))}$ where $((x))$ is the sawtooth function Deinst 2010-03-04T20:35:36Z 2010-03-07T18:32:10Z <p>Let the sawtooth function $((x)) = x-\lfloor x \rfloor - 1/2$ if x is not an integer, 0 if it is. </p> <p>For an arbitrary irrational $\alpha$ are there good bounds for $\sum_{i=0}^n i((i \alpha))$?</p> <p>Experiment seems to indicate something of the the form $O(n^{1+\epsilon})$, and that would be great, but anything better than $O(n^2)$ would be nice. Explicitly computable constants depending on $\alpha$ would be great as well. </p> http://mathoverflow.net/questions/17132/bounds-on-sum-n-alpha-n-where-x-is-the-sawtooth-function/17141#17141 Answer by Gerry Myerson for Bounds on $\sum {n ((\alpha n))}$ where $((x))$ is the sawtooth function Gerry Myerson 2010-03-04T22:26:59Z 2010-03-04T22:26:59Z <p>For $\alpha$ irrational, the sequence $i\alpha$ is uniformly distributed modulo 1. A theorem of Weyl says that if $u_n$ is uniformly distributed in $[0,1)$ and $f$ is Riemann-integrable then $\lim_{N\to\infty}(1/N)\sum_1^Nf(u_n)=\int_0^1f(x)dx$. There's a quantitative version of this theorem that says the difference between the sum and the integral is bounded by the discrepancy of the sequence times the variation of the function. The discrepancy of the sequence $i\alpha$ (modulo 1) is well-understood. Maybe this gives an approach. </p> <p>A reference is Kuipers and Niederreiter, Uniform Distribution of Sequences. </p> http://mathoverflow.net/questions/17132/bounds-on-sum-n-alpha-n-where-x-is-the-sawtooth-function/17149#17149 Answer by maks for Bounds on $\sum {n ((\alpha n))}$ where $((x))$ is the sawtooth function maks 2010-03-05T00:46:59Z 2010-03-05T00:46:59Z <p>Here is how to obtain the $o(N^2)$ bound. If $\alpha$ is irrational then by Weyl's bound (as the previous poster remarked) we have $\sum_{n \leq N} ((n\cdot\alpha)) = o(N)$. Now note that that $$\sum_{i \leq N} i\cdot ((i\cdot\alpha)) = N\sum_{n \leq N} ((n\cdot\alpha)) - \int_{1}^{N} \sum_{n \leq t} ((n \cdot \alpha)) \text{d}t$$ For irrational $\alpha$ by Weyl's bound both terms are $o(N^2)$. You can certainly improve on the $o(N^2)$ but if you want a very good improvement you may need to know more about $\alpha$.</p> http://mathoverflow.net/questions/17132/bounds-on-sum-n-alpha-n-where-x-is-the-sawtooth-function/17176#17176 Answer by Douglas Zare for Bounds on $\sum {n ((\alpha n))}$ where $((x))$ is the sawtooth function Douglas Zare 2010-03-05T12:43:00Z 2010-03-07T18:32:10Z <p>Here is an approach which may give some better estimates for particular values of $\alpha$:</p> <p>$$\sum_{i= 1}^N i((i\alpha)) = \sum_{i=1}^N \sum_{j=i}^N ((j \alpha)) = \sum_{i=1}^N \sum_{k=0}^{N-i}((N\alpha -k\alpha))$$.</p> <p>So, if you can estimate </p> <p>$$\sup_{\substack{x\in (0,1) \\ M \le N}} \bigg|\sum_{k=0}^{M} ((x-k\alpha))\bigg|,$$ </p> <p>then you can crudely multiply by $N$ to get an estimate for $|\sum i((i\alpha))|$.</p> <p>Specifically, my guess is that for quadratic irrationals $\alpha$, there is an upper bound for </p> <p>$$\bigg|\sum_{k=0}^M ((x-k\alpha))\bigg|$$</p> <p>which is $O (\log M)$, which would give you a bound of $O(N \log N)$, and more generally that there is a bound in terms of the coefficients of the simple continued fraction for $\alpha$, so that if those are bounded, then you still get $O(N \log N)$. </p> <p>For the particular value $\phi = (\sqrt5 + 1)/2$, $\sum_{i=0}^{M} ((i \phi))$ has logarithmic growth $c + (5\sqrt5 - 11)/4 \log_\phi M$ (achieved at indices in the sequences <a href="http://www.research.att.com/~njas/sequences/A064831" rel="nofollow">A064831</a> (+) and <a href="http://www.research.att.com/~njas/sequences/A059840" rel="nofollow">A059840</a> (-)), which suggests that $\sup \sum_{i=0}^M ((x-i\phi))$ also has logarithmic growth, which would give an $N \log N$ bound for the sum. </p> <hr> <p>In the opposite direction, for all $\alpha \not\in \frac 12\mathbb Z$, $$\limsup \bigg(\log_N \bigg|\sum_{i=0}^N i((i\alpha))\bigg|\bigg) \ge 1$$ since there are terms proportional to $N$.</p> <p>The sum can be greater than $N^{2-\epsilon}$ infinitely often by choosing $\alpha$ so that it is extremely well approximated by infinitely many rational numbers. When $\alpha$ is very closely approximated by $p/q$, then for $N$ a small multiple of $q$ (where "small" is relative to how well $p/q$ approximates $\alpha$), about $1/q$ of the terms can be moved past integers with a small perturbation of $\alpha$ to $\alpha'$, which causes a jump of about $N^2/q$ in the sum. So, either the sum for $\alpha$ or $\alpha'$ is large. We can choose a sequence $p_n/q_n$ which converges to an $\alpha$ which produces large sums infinitely often, so that for these $\alpha,$ $$\limsup \bigg(\log_N \bigg|\sum_{i=0}^N i((i\alpha))\bigg|\bigg) = 2$$.</p>