Computational study of irrational rotations via exact discontinuity tracking
Hannah Kravitz · 2025
Read Computational study of irrational rotations via exact discontinuity tracking by Hannah Kravitz (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-2511-13879.txt.
Introduction
Hannah Kravitz presents a computing tool for studying irrational rotations, a classic topic in number theory. A certain running sum built from fractional parts tracks how evenly a rotation spreads points, but direct calculation is plagued by rounding error and missed jumps. Her algorithm instead defines the sum exactly through its discontinuities.
With that approach, values can be computed with errors near machine precision in fast linear time, and the full probability distribution follows soon after. Kravitz offers the method as a tool for experimental mathematics. Plots made with it reveal extreme behavior tied to how well the rotation number is approximated by fractions, including a spiked trapezoidal pattern that slowly degrades.
Catalog record
| CREATOR | Hannah Kravitz |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13879
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computational study of irrational rotations via exact discontinuity tracking Hannah Kravitz Abstract The discrepancy sum D N ( x , ρ ) D_{N}(x,\rho) for irrational rotations has been of interest to mathematicians for over a century. While historically studied in an “almost-everywhere” or asymptotic sense, D N D_{N} for finite N N is increasingly an object of interest for its highly nontrivial properties that depend on the Diophantine properties of ρ \rho . This behavior is typically periodic in N N with respect to the quotients of the continued fraction convergents, which can grow quite quickly for some irrationals. Thus the stable computation of the sum is necessary for forming conjectures about particular properties. However, computing the exact value of the sum and its corresponding probability density function ( pdf ) is notoriously difficult due to numerical instability inherent in the sum itself and the failure of sampling methods to capture the structure of its jump discontinuities. This paper presents a novel computational algorithm that fully defines the discrepancy function and its associated pdf through its discontinuities. This allows the calculation of D N ( x , ρ ) D_{N}(x,\rho) to machine precision with minimal storage in O ( N ) O(N) time. This vast improvement in computability over the O ( N 2 ) O(N^{2}) naive version enables, for the first time, the direct computation of the exact pdf up to machine precision in O ( N log N ) O(N\log N) time, and with it, some key properties of the discrepancy: ‖ D N ‖ ∞ ||D_{N}||_{\infty} (half of the support of the pdf ), ‖ D N ‖ 2 2 ||D_{N}||_{2}^{2} (the variance of the pdf ), and the kurtosis of the pdf . A key strength of the discontinuity-tracking algorithm lies in its ability to produce clear, exact figures, allowing the development of mathematical intuition and the quick testing of conjectures. As an example, a newly conjectured pattern is presented: when ρ \rho is well-approximated by rational p n q n \frac{p_{n}}{q_{n}} , the pdf exhibits a predictable spiked-trapezoidal pattern when N = k q n N=kq_{n} . These shapes degrade eventually as k k increases, with the degradation speed depending on how well p n q n \frac{p_{n}}{q_{n}} approximates ρ \rho . 1 Introduction The study of uniform distribution modulo one is a classic topic in number theory. A key object of interest is the discrepancy sum for a rotation, defined as D_{N}(x,\rho)=\sum_{k=1}^{N}\left[(x+k\rho)\mod{1}-\frac{1}{2}\right]. (1) with x\in[0,1) , \rho (typically irrational) \in[0,1) , and N\in\mathbb{N} . D_{N} , a particular example of a Birkhoff sum, quantifies deviations of the sequence’s average from its expected mean of \frac{1}{2} [ 2 , 16 ] . Theoretical work spanning nearly a century has analyzed the growth rates, extrema, asymptotic behavior, and other properties of D_{N}(x,\rho) (see, for example, [ 1 , 4 , 8 , 14 , 15 , 16 , 18 , 20 , 21 , 22 , 24 , 25 , 28 , 27 , 29 ] ) yet many questions still remain unanswered. A primary reason for this enduring interest is that this simple function exhibits highly complex self-similar patterns that evolve and change, determined by the Diophantine properties of \rho and the choice of N . However, these features grow finer as N increases, making them difficult to resolve computationally using standard methods. This creates a significant barrier to using numerical exploration for testing conjectures. Furthermore, the theoretical literature on this topic is often presented without figures, obscuring the fascinating geometric patterns the mathematics reveal. The computational challenges are threefold: • First, the naive summation in Equation 1 is notoriously prone to numerical instability; the repeated use of the \text{mod }{1} operation on large terms runs a high risk of catastrophic cancellation (loss of nearly all significant digits from subtracting two nearby numbers) [ 6 , 12 ] . • Second, the function’s structure consists of up to N branches with jump discontinuities. For irrational \rho , a uniform sampling of x\in[0,1) is guaranteed to miss the branch endpoints, which are fundamental to the structure of the probability density function ( pdf ). As N varies, D_{N} presents intricate fine-scale features for irrational \rho that sampling is also nearly guaranteed to miss, like very short branches and branches that are nearly (but never exactly) aligned. • Third, resolving this complex structure to even roughly discern some features is computationally prohibitive itself, requiring O(N^{2}) time and O(N^{2}) storage. This makes even familiar rotation numbers like \rho=\pi-3 difficult to study, as the most interesting behavior typically occurs when N is a multiple of the denominator of a continued fraction convergent; the fourth such partial quotient for \pi-3 is N=33,102 . In this paper, we overcome all three of these barriers by introducing an efficient and stable algorithm that computes the discrepancy function D_{N} exactly, to machine precision. By developing a novel method to track the N discontinuities directly, our algorithm achieves what was unattainable using naive sampling: it runs in O(N) time, operates with machine precision (bypassing the numerical instabilities inherent in the summation and avoiding large sampling errors), and requires only O(N) storage. A direct consequence of this algorithm is the ability to exactly compute the probability density function ( pdf ) associated with D_{N}(x,\rho) in O(N\log N) time, with O(N) storage, at machine precision. This new computation enables, for the first time, the exact calculation of the fundamental statistical properties of the pdf : ||D_{N}||_{\infty} (half of the support of the pdf ), ||D_{N}||_{2}^{2} (the variance of pdf ), the kurtosis. It also allows the rapid generation of highly accurate figures to help guide mathematical intuition. 1.1 Discrepancy Equation 1 may be rewritten in a form more stable to double-precision arithmetic errors: D_{N}(x,\rho)=Nx+\frac{N(N+1)}{2}\rho-\frac{N}{2}-\sum_{k=1}^{N}\lfloor x+k\rho\rfloor (2) where \lfloor\cdot\rfloor is the floor function. This formulation also reveals the structure of D_{N} as piecewise-linear with branches of slope N . For irrational \rho , the jumps between segments caused by the floor function will have height exactly 1, while the length of the segments vary. As N increases, the plots of D_{N} reveal a self-similar structure with intricacies determined by the Diophantine properties of \rho . Figure 1 shows D_{N} for \displaystyle\rho=L=\sum_{k=1}^{\infty}\frac{1}{10^{k!}}\approx 0.1100010000000000 , Liouville’s constant for several N to show both the capabilities of the algorithm and the behavior of the function. The first row shows very short branches, even for small N . As N increases in the second and third rows, a self-similar structure emerges, with branches grouped in blocks with periodic properties. Figure 1: This figure shows the plot of D_{N}(x,L) for different N . The three rows show different levels of a self-similar structure changing with N . 1.2 Probability density function and its statistical properties We find the probability density function \text{pdf}(y) using the standard formula for a non-monotonic transformation on a uniform distribution [ 19 ] , in this case D_{N}(x,\rho):[0,1)\rightarrow\mathbb{R} , with \rho fixed: \text{pdf}(y)=\sum_{x\in D_{N}^{-1}(y)}\frac{1}{|D_{N}^{\prime}(x,\rho)|}=\sum_{x\in D_{N}^{-1}(y)}\frac{1}{N}=\frac{\#\left\{x\in D_{N}^{-1}(y)\right\}}{N} (3) where D_{N}^{-1}(y) is the preimage of y and \#\left\{\cdot\right\} is the cardinality of a set. The structure of \text{pdf}(y) is piecewise-constant, with segments becoming extremely short as N grows large. While this distribution