On the records and zeros of a deterministic random walk
Henk Bruin and Robbert Fokkink · 2025
Read On the records and zeros of a deterministic random walk by Henk Bruin and Robbert Fokkink (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11734.txt.
Introduction
Bruin and Fokkink settle open questions about a number sequence in a 2025 paper. The sequence comes from a walk that moves by fixed rules yet looks random. Two questions about its records and zeros were posed on a public integer sequence site. A related guess by other scholars is partly solved as well.
The pair widen the frame to automatic sequences and linear recurrences. Their results hint at a deeper tie among these structures than was known. They close with a fresh guess: the records of such walks may follow a pattern tied to a square-root-type rotation number. The paper serves readers in number theory and sequence studies.
Catalog record
| CREATOR | Henk Bruin and Robbert Fokkink |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-11734
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the records and zeros of a deterministic random walk Henk Bruin and Robbert Fokkink Abstract . We settle two questions on sequence A120243 in the OEIS that were raised by Clark Kimberling and partly solve a conjecture of Van de Lune and Arias de Reyna. We extend Kimberling’s questions to the framework of deterministic random walks, automatic sequences, and linear recurrences. Our results indicate that there may be a deeper connection between these structures. In particular, we conjecture that the records of deterministic random walks are ξ \xi -Ostrowski automatic for a quadratic rotation number ξ \xi . 2020 Mathematics Subject Classification 11B85, 11K38, 60J15 Sequence A120243 in the OEIS consists of numbers n such that the fractional part \{n\sqrt{2}\} is less than \frac{1}{2} . Its complementary sequence, denoted as b(n) , is A120749 . The table below presents the first eighteen elements of these sequences: a(n) 1 3 5 6 8 10 13 15 17 18 20 22 25 27 29 30 32 34 b(n) 2 4 7 9 11 12 14 16 19 21 23 24 26 28 31 33 36 38 Table 1. The first eighteen numbers from A120243 and A120749 These sequences were entered into the OEIS by Clark Kimberling, who posed the question of whether the difference b(n)-a(n) is positive for all n and whether, for each integer k , there exist infinitely many values of n such that b(n)-a(n)=k . We confirm both of these properties. Kimberling’s questions relate to the rotation of the unit circle by \sqrt{2} , which is often an initial case leading to broader mathematical results, such as in [ 4 ] . Our analysis of the sequences a(n) and b(n) extends to the more general framework of automatic sequences and ergodic theory. We could also have described the sequences A120243 and A120749 by the parity of \lfloor 2n\sqrt{2}\rfloor . The sequence a corresponds to the even numbers, and b corresponds to the odd numbers. Or alternatively, if instead of parity we use signs by putting (-1)^{\lfloor 2n\sqrt{2}\rfloor} , then we can think of the sequences a and b as the steps in the positive direction and the negative direction, respectively, in what is known as, rather curiously, a deterministic random walk (1) S_{n}(\xi)=\sum_{j=1}^{n}(-1)^{\lfloor j\xi\rfloor}, for \xi=2\sqrt{2} . If we move from fractional parts \{n\xi\} to deterministic random walks S_{n}(2\xi) , then we double \xi . Kimberling’s question whether b(n)-a(n) is positive is equivalent to the question whether S_{n}(2\sqrt{2}) is non-negative. This problem closely resembles Problem B6 from the 81st William Lowell Putnam Mathematical Competition, which requires proving that S_{n}(\sqrt{2}-1) is non-negative, see [ 5 ] . A number n is a record of the deterministic random walk if none of the previous partial sums (including zero) is equal to S_{n}(\xi) . Sequence A123737 in the OEIS contains the partial sums of the deterministic random walk for \xi=\sqrt{2} . In a comment on A123737, Václav Kotěšovec asked if the records satisfy a certain recurrence relation. Van de Lune and Arias de Reyna [ 13 ] conjecture that there is a system of recurrence relations for the records of the deterministic random walk S_{n}(\xi) for all quadratic irrationals \xi . Their work extends earlier results of O’Bryant et al [ 15 ] . We confirm Kotěšovec’s recurrence and settle some instances of the conjecture. A number n is a zero of the deterministic random walk if S_{n}(\xi)=0 . Deterministic random walks S_{n}(\xi)=\sum_{j=1}^{n}(-1)^{\lfloor x+j\xi\rfloor} (with offset x\in[0,1) ) were introduced by Aaronson and Keane [ 1 ] , and their primary interest was an estimate of the asymptotic number of zeros as n goes to infinity for a generic number x . More specifically, if N_{n} is the number of zeros up to n , then it can be interpreted as a random variable depending on a uniformly random x . The asymptotic mean and variance of N_{n} remain a subject of ongoing research [ 2 , 7 ] . 1. Irrational rotations and automata The sequences a and b arise from an irrational rotation of the unit circle. The number a(n) marks the n -th return to the semi-circle [0,\frac{1}{2}) under the rotation x\mapsto x+\sqrt{2} , starting from x=0 , and b(n) is the n -th return to its complement [\frac{1}{2},1) . According to the ergodic theorem, both \lim\frac{a(n)}{n} and \lim\frac{b(n)}{n} equal two, which is suggested already by the first eighteen entries in Table 1 . Given this, the next point of interest is the behavior of the differences a(n)-2n and b(n)-2n . Such deviations from the mean are known as discrepancies , which is a significant topic in the study of sequences [ 8 ] . Kimberling’s question regarding whether b-a assumes every positive number infinitely often falls within this topic. His other question on the signature of b-a is equivalent to asking whether a(n)-2n is negative and b(n)-2n is non-negative. For N\in\mathbb{N} an interval I\subset(0,1) and \xi\in(0,1) , let \ell(I) be the length of I and let N(\xi,I) be the cardinality of \{n\colon\{n\xi\}\in I,\ n\leq N\} . Kesten [ 12 ] famously proved that (2) \limsup_{N\to\infty}|N(\xi,I)-\ell(I)\cdot N|<\infty if and only if \ell(I)=\{m\xi\} for some m\in\mathbb{N} . If we apply this to \xi=\{\sqrt{2}\} and I=[0,\frac{1}{2}) , then we get that the difference between N/2 and the number of \{n\xi\}<\frac{1}{2} up to N is unbounded. This implies that a(n)-2n and b(n)-2n are both unbounded. Sós [ 19 ] observed that the discrepancy N(\xi,I)-\ell(I)\cdot N may be bounded on one side and unbounded on the other. Recall the (regular) continued fraction of a real number \xi \xi=a_{0}+\cfrac{1}{a_{1}+\cfrac{1}{a_{2}+\cfrac{1}{a_{3}+\cfrac{1}{\ddots}}}} The coefficients a_{i} are the partial quotients and the finite expansions \frac{p_{n}}{q_{n}} are the convergents, starting from \frac{p_{0}}{q_{0}}=\frac{a_{0}}{1} . Dupain and Sós [ 9 ] gave a necessary and sufficient condition on I=[0,\beta) and \xi for one-sided boundedness, for \xi with bounded partial quotients (such as quadratic irrationals). Boshernitzan and Ralston [ 6 ] found an elegant condition for nonnegative discrepancy in terms of the convergents of \xi . Theorem 1 (Boshernitzan and Ralston) . Let I=[0,\frac{h}{k}) and let \frac{p_{n}}{q_{n}} be the convergents of \xi . The discrepancy N(\xi,I)-\ell(I)\cdot N is nonnegative if and only if k\ |\ q_{2n+1} for all n . In particular, if the odd convergents q_{2n+1} of \xi are even then the number of \{n\xi\} in [0,\frac{1}{2}) up to N exceeds, or is equal to, the number of \{n\xi\} in [1/2,1) . This is equivalent to the non-negativity of S_{n}(2\xi) . The denominators q_{n} of the convergents of \sqrt{2} , starting from q_{0}=1 , are the Pell numbers 1,2,5,12,\ldots , entry A000129 in the OEIS. The q_{n} are even for odd n and so the discrepancy is nonnegative by Theorem 1 . For each N at least half of the iterates \{n\sqrt{2}\} are in [0,\frac{1}{2}) . It follows that a(n)-2n is negative and b(n)-2n is nonnegative for all n , and therefore b-a is positive. This settles one of the two questions of Kimberling. Corollary 2 . The sequence b-a is positive. The odd convergents are even if and only if the odd partial quotients a_{2n+1} are even. Problem B6 of the 2021 Putnam Competition asks one to prove that S_{n}(\sqrt{2}-1) is non-negative. The continued fraction expansion of \frac{\sqrt{2}-1}{2} is