For $x$ irrational, define $a_{n} :=\sum_{k=1}^{n}(-1)^{⌊kx⌋}$. Can you prove that $\left\{a_n\right\}$ is unbounded?

I feel that it is not easy to treat every irrational $x$.

I have asked in S.E. and it seems that it is an advanced question. Thus I go for help here.

  • 5
    $\begingroup$ I must confess that it's not obvious to me that it's unbounded for any irrational $x$. Can someone set me straight? $\endgroup$ – Todd Trimble Apr 26 '20 at 1:38
  • 2
    $\begingroup$ I am a little bit curious where is this question coming from? $\endgroup$ – Paata Ivanishvili Apr 26 '20 at 5:04
  • 6
    $\begingroup$ @ToddTrimble If the infimum of $q^2|x-\frac{p}{q}|$ over all rational approximations $\frac{p}{q}$ with $q$ odd is zero, then this sum is unbounded. (For each fixed integer $k$, consider $\displaystyle\sum_{i=m}^{m+kq-1}(-1)^{\lfloor ix\rfloor}$ for large $q$ and "generic" $m$.) Almost every $x$ (in the sense of Lebesgue measure) satisfies this - this follows from the Duffin-Schaeffer conjecture (now the Koukoulopoulos-Maynard theorem), but I'm sure that's massive overkill. $\endgroup$ – dhy Apr 26 '20 at 5:50
  • 4
    $\begingroup$ It's a very natural question from the point of view of ergodic theory. One has the dynamical system $u:t\mapsto t+x$ on the circle 𝐑/2𝐙. In turn 𝑢 induces an operator 𝑇 on functions or measures by $𝑇(𝑓(𝑡))=𝑓(𝑢(𝑡))=𝑓(𝑡+𝑥)$. In ergodic theory it's natural to estimate the average $\mathcal{A}_nT=\frac1n\sum_{i=1}^nT^n$ in various ways. Here the question is just evaluating $(\mathcal{A}_nT)g$ at $0$, for $g=\mathbb{1}_{[0,1]}-\mathbb{1}_{[1,2]}$ (namely asking if it's 𝑂(1/𝑛) or not). $\endgroup$ – YCor Apr 26 '20 at 8:14
  • 1
    $\begingroup$ Here's a related reference: pdfs.semanticscholar.org/9cb4/… The case they mention as settled ($g(x)=\{2x\}$ sounds at least as hard as the current case. So I believe the result is true and known. $\endgroup$ – YCor Apr 26 '20 at 8:35

It's indeed unbounded for every irrational $x$.

Let me identify points of $\mathbb{R}/\mathbb{Z}$ with their representatives on $[0,1)$, and order it by the usual order $<$ of $\mathbb{R}$ applied to the representatives.

Replace $x$ by $y = x/2$, and the question becomes whether for all $m$ there exists $k$ such that the orbit of $0$ in the irrational rotation on $\mathbb{R}/\mathbb{Z}$ by $y$ is in $[0,1/2)$ at least $m$ more times than in $[1/2,1)$, in the first $k$ time steps $y,2y,3y,...,ky$; or that this happens with $[0,1/2)$ and $[1/2,1)$ interchanged.

Since the irrational rotation by $2y$ is topologically transitive, we can find odd $k$ with $ky > 0$ arbitrarily small. For odd $k$ the set $Y_k = \{y,2y,...,ky\}$ has to intersect either $[0,1/2)$ or $[1/2, 1)$ more times than the other. Let's suppose the first case happens for infinitely many $k$. (The other case is symmetric, and one happens by the pigeonhole principle.)

Let now $P_m$ be the statement that there are $ky > 0$ arbitrarily small such that $[0,1/2)$ contains $m$ more elements of $Y_k$ than $[1/2,1)$ does. We have that $P_1$ holds. Observe that if $P_m$ holds and $k$ is as in the definition, then $[0, 1/2)$ also contains $m$ more elements of $Y_{k,a} = \{a+y,a+2y,...,a+ky\}$ than $[1/2,1)$ whenever $a$ is small enough, because $Y_k$ is disjoint from $\{0,1/2\}$.

Let now $m \geq 1$ be any integer such that $P_m$ holds. Let $\epsilon > 0$ be arbitrary and pick $k$ such that $0 < ky < \epsilon/2$ and $[0,1/2)$ contains at least $m$ more elements of $Y_k$ than $[1/2,1)$ does. Let $a$ be as in the previous paragraph.

Using $P_m$ again, take $0 < k'y < \min(\epsilon/2, a)$ such that $[0, 1/2)$ contains $m$ more elements of $Y_{k'} = \{y,2y,...,k'y\}$ than $[1/2,1)$ does. Then $[0,1/2)$ contains $2m$ more elements of $Y_{k'+k}$ than $[1/2,1)$. We have $0 < (k+k')y < \epsilon$, so $P_{2m}$ holds.

Thus $P_m$ holds for all $m$, and the claim follows.

  • 2
    $\begingroup$ Nice argument. I guess you can make things a little quantitative to show that $c_x=\limsup |a_n|/\log(n)>0$, and even $\inf_xc_x>0$ when $x$ ranges over irrationals. Also it should work without change for $\lfloor ix\rfloor$ replaced with $\lfloor ix+x'\rfloor$ (that the irrational arithmetic progression passes through 0 plays no role). $\endgroup$ – YCor Apr 26 '20 at 15:04
  • 9
    $\begingroup$ I had similar thoughts, but didn't have time to work more on it. (My main job ATM is changing diapers.) $\endgroup$ – Ville Salo Apr 26 '20 at 15:18
  • $\begingroup$ Two stupid questions: 1) Why should $k'$ presumably distinct from $k$ in the last paragraph exist should $k$ exist? 2)Why does "$[0,1/2)$ contains $2m$ more elements of $Y_{k'+k}$ than $[1/2,1)$. We have $0 < (k+k')y < \epsilon$"? Is it because for any $iy, jy\in[0,\frac12)$, $(i+j)y\in[0,\frac12)$? That does not seem right. $\endgroup$ – Hans Apr 27 '20 at 22:13
  • $\begingroup$ Regarding 1) Maybe you assume as part of the mathematical induction there are infinitely many $k$'s such that $P_m$ holds and $k'$ denotes any other such natural number. But then how do you conclude that there is always such $k'$ in that set that satisfies $k'<\min(\frac\epsilon2,a)$. 3) Why do we need $ky<\frac\epsilon2$ for an arbitrarily given positive $\epsilon$ in the first place? $\endgroup$ – Hans Apr 28 '20 at 3:01
  • $\begingroup$ 1) $k'$ can be the same as $k$ for all I care. It exists by $P_m$. In any case, the definition is $P_m \iff \forall \epsilon > 0: \exists k > 0: 0 < ky < \epsilon$, and this implies that there are infinitely many such $k$, by picking smaller $\epsilon$. $\endgroup$ – Ville Salo Apr 28 '20 at 5:51

We have

Theorem. Let $\psi(x)$ and $\varphi(x)$ be positive increasing functions such that $$\int_1^\infty \frac{dx}{\psi(x)}=+\infty,\qquad \int_1^\infty \frac{dx}{\varphi(x)}<+\infty.$$ Then for almost all $\alpha\in(0,1)$ we have $$\Omega(\log N\cdot \psi(\log\log N))\le\sup_{n\le N}\sum_{j=1}^n(-1)^{\lfloor j\alpha\rfloor}=O(\log N\cdot \varphi(\log\log N)).$$

This is proved in my paper with Jan van de Lune On Some oscillating sums, Uniform Distribution Theory 3 (2008) 35--72.

In this paper it is contained an algorithm to compute the sums. We obtain for example $$S_{\sqrt{2}}(10^{1000})=-10,\quad S_{\sqrt{2}}(10^{10000})=166,\quad S_{\pi}(10^{10000})=11726.$$ With $S_\alpha(N)=\sum_{j=1}^n(-1)^{\lfloor j\alpha\rfloor}$.

  • 2
    $\begingroup$ So this answers the question for almost all irrational number, but not for all, right? $\endgroup$ – domotorp Apr 26 '20 at 10:03
  • 2
    $\begingroup$ @domotorp In the paper we show also that the sums are not bounded for any irrational. $\endgroup$ – juan Apr 26 '20 at 12:15
  • $\begingroup$ @pisoir Thanks for the edits $\endgroup$ – juan Apr 26 '20 at 18:13

Here is an argument essentially due to fedja I learned about thirteen years ago on artofproblemsolving.com.

Proposition: if $f$ is $2$-periodic Riemann integrable such that $\sup_{n \geq 1} \left|\sum_{k=1}^{n}f(kx)\right|<C<\infty$ for some irrational $x \in \mathbb{R} \setminus \mathbb{Q}$ then necessarily $$ \sum_{m\neq 0}\, \left| \frac{\hat{f}(m)}{e^{i \pi m x}-1}\right|^{2}<2C^{2}. \quad (1) $$.

Notice that the proposition solves the question. Indeed, $f(t)=(-1)^{\lfloor{t}\rfloor}$ is 2-periodic with Fourier coefficients $\hat{f}(m) = \left| \frac{1}{2}\int_{0}^{2}f(t)e^{-i\pi m x}dx \right| \approx \frac{1}{m}$ for $m$ odd, and $\hat{f}(m)=0$ for even $m$. There are infinitely many odd numbers $m$ such that $\mathrm{dist}\left(mx, 2\mathbb{Z}\right) < \frac{C'}{m}$ (it does not follow directly from Dirichlet's rational approximation theorem, however, I think it is not difficult to adapt it here or use Minkowski's theorem on product of two linear forms). Therefore, in the left hand side of (1) there are infinitely many terms comparable to 1 so we get a contradiction.

Proof of the proposition:

Let me first assume that $f$ is continuous and then I will explain later what to do in the arbitrary case. Let $S_{m} = \sum_{k=1}^{m-1}f(kx)$. Then the boundedness of $|S_{M+n}-S_{M}|$ implies $$ |\sum_{k=0}^{n-1} f(Mx+kx)|<2C \quad \text{for all} \quad M>1 \quad (2) $$ and all $n\geq 1$. By density of the sequence $\{Mx\, \mathrm{mod}\, (2)\}_{M>1}$ in $[0,2)$ we conclude $$ |\sum_{k=0}^{n-1} f(t+kx)|\leq 2C \quad \text{for all} \quad t \in [0,2). \quad (3) $$ Let us convolve $f$ with Fejer Kernel so that the new function $F$ is now a trigonometric polynomial with almost the same Fourier coefficients, and clearly it also satisfies the inequality (3). After expanding $F$ into its Fourier series $F(s) = \sum_{m} \hat{F}(m) e^{i\pi m s}$ (finite sum), and using (3) for $F$ we obtain $$ \left| \sum_{m} \hat{F}(m)e^{i \pi m t} \, \frac{e^{i \pi m n x} -1}{e^{i \pi m x} -1} \right| <2C $$ In particular its $L^{2}$ norm is bounded, i.e., $$ \sum_{m\neq 0} \left|\hat{F}(m)\, \frac{e^{i \pi m n x} -1}{e^{i \pi m x} -1}\right|^{2} <4C^{2}\quad (4) $$ Invoking the density of the sequence $\{n x\, \mathrm{mod}\, (2)\}_{n \geq 1}$ again we can replace $nx$ by an arbitrary $s \in [0,2)$, after that we integrate (4) with respect to $s$ over the interval $[0,2]$, and we use the identity $\int_{0}^{2} |e^{i \pi m s} -1|^{2}ds=4$, hence, we conclude (1) for $F$. Finally it remains to remove the convolution with Fejer kernel to conclude (1) for $f$ (we have nonnegative terms in the sum on the left hand side of (1), so we can just cut the sum and take the limit $\hat{F}(m) \to \hat{f}(m)$)

In general, if $f$ is not continuous, let $K_{N}$ be the Fejer kernel. Split $Mx=M_{1}x+M_{2}x$ in (2), multiply (2) by $K_{N}(M_{1}x)$ and take the average in $M_{1}$ and use the Riemann integral criteria for equidistribution of $\{M_{1} x\, \mathrm{mod}\, (2)\}_{M_{1}\geq 1}$ to conclude $\left| \sum_{k=0}^{n-1} F(M_{2}x + kx)\right|<2C$ and now due to continuity of $F$ and density of $\{M_{2} x\}$ we conclude (3) for $F$ and the rest of the argument proceeds in the same way. $\square$


As Ville Salo already wrote in his answer, your question can be phrased in terms of the difference between the number of elements of the sequence $y, 2y, \dots, ky$ which are contained in $[0,1/2]$, and $k$ times the length of $[0,1/2]$. Here $y = x/2$. In the language of discrepancy theory, you are asking whether the interval $[0,1/2]$ is a so-called bounded remainder set of the sequence $(n y~\text{mod}~1)_{n \geq 1}$. However, it is known that it is not: the only intervals with bounded remainder are those whose length is in $\mathbb{Z} + y \mathbb{Z}$, and since $y$ is irrational in your question the length of $[0,1/2]$ is not of such type. Bounded remainder sets were classified in this paper: H. Kesten, On a conjecture of Erdös and Szüsz related to uniform distribution mod 1, Acta Arith. 12(1966), 193–212.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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