# Bounds on $\sum {n ((\alpha n))}$ where $((x))$ is the sawtooth function

Let the sawtooth function $((x)) = x-\lfloor x \rfloor - 1/2$ if x is not an integer, 0 if it is.

For an arbitrary irrational $\alpha$ are there good bounds for $\sum_{i=0}^n i((i \alpha))$?

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.

-

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

-
If you want explicit bounds, I would say that Erdos-Turan, is the keyword. –  maks Mar 5 '10 at 0:48

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.

A reference is Kuipers and Niederreiter, Uniform Distribution of Sequences.

-

Here is an approach which may give some better estimates for particular values of $\alpha$:

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

So, if you can estimate

$$\sup_{\substack{x\in (0,1) \\\ M \le N}} \bigg|\sum_{k=0}^{M} ((x-k\alpha))\bigg|,$$

then you can crudely multiply by $N$ to get an estimate for $|\sum i((i\alpha))|$.

Specifically, my guess is that for quadratic irrationals $\alpha$, there is an upper bound for

$$\bigg|\sum_{k=0}^M ((x-k\alpha))\bigg|$$

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

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 A064831 (+) and A059840 (-)), 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.

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

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

-