Random Fibonacci Tilings
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Random Fibonacci Tilings".
Emmy: Here's the gist of the paper. The paper studies a randomization of the Fibonacci spiral construction where attachment axes alternate deterministically and direction is chosen by fair coin flips to investigate when a growing rectangle covers a lattice point and how this expected covering time depends on its location Randomization of the Construction The study introduces a randomization of the square-joining rule where the attachment axis alternates deterministically, while fair coin flips determine direction The main question is when the growing rectangle first covers a given lattice point Tracking the rectangle’s boundary reduces this question to random subset sums of even- and odd-indexed Fibonacci numbers For d ≥ 2, the expected covering time grows logarithmically with distance from the initial block, while the variance remains uniformly bounded Exponential tail bounds for the delay beyond the earliest feasible covering stage are obtained.
Ada: Covering Time Analysis in d Dimensions The analysis extends to d dimensions where coordinate subsequences are super-increasing, allowing for exact covering probabilities and formulas for expectation and variance For fixed d ≥ 2, the expected covering time is given by E
T(a): = log δ∞(a) log ρd + Od(1) as δ∞(a) → ∞.
Emmy: The variance remains bounded, and the mean grows logarithmically with distance while the variance remains bounded.
Ada: Weighted Subset Sums and Canonical Ordering The covering problem is simplified by tracking the rectangle’s boundary, which reduces it to random subset sums of fixed weights The coordinate-weight sequences are superincreasing, which orders the subset sums and yields exact covering probabilities, expectations, and variances.
Paper summary: Ada: So we're talking about this paper called Random Fibonacci Tilings. It looks at taking that standard construction of Fibonacci squares and adding some randomness to it, specifically alternating the attachment axis deterministically while using coin flips for direction.
Emmy: Right, so the main idea is studying when a growing rectangle covers a specific lattice point in this randomized setup, and how long that takes on average. It seems like they're looking at something that started with the Fibonacci sequence and now has this probabilistic twist <ref:2611.08317#pg2>.
Kolya: The big question here is when does the rectangle first cover a given lattice point, and how does that expected covering time behave based on where you are? That sounds like a problem about how fast things spread out in this random arrangement <ref:2611.08317#pg3>.
Ada: Exactly. The paper claims that for dimensions d greater than or equal to two, the expected covering time grows logarithmically with the distance from your starting block, and the variance stays bounded <ref:2611.08317#pg3>.
Emmy: They also get exponential tail bounds for how long it takes beyond the very first stage where covering is even possible. That means there are some rare, very long waiting times that they can bound <ref:2611.08317#pg3>.
Kolya: If we're talking about the results, what does that logarithmic growth in distance mean for the practical application? Is it saying that even if you move quite far away, you don't get stuck waiting forever?
Ada: It means the time to cover a point scales with the logarithm of its distance from the starting region, which is pretty slow growth compared to linear or polynomial growth <ref:2611.08317#pg3>. The variance stays bounded, which is good because it suggests that most of the time, the waiting time is close to that average logarithmic value.
Emmy: And they get this exact formula for the mean covering time, E
T(a): equals log delta infinity of a times log rho d plus a term that's at most one <ref:2611.08317#pg3>. That term is what the authors call Od(one) <ref:2611.08317#pg2>.
Kolya: What is delta infinity of a, and what's rho d? I need to understand the mechanics behind that formula to see if it holds up when we move beyond two dimensions.
Ada: delta infinity of a is defined as the maximum of zero and minus ar, zero less than or equal to r less than d where ar is the r coordinate of your target point a <ref:2611.08317#pg3>. And rho d is the positive root of x to the power d minus x to the power d minus one minus one, which is a specific constant related to that dimension <ref:2611.08317#pg3>.
Paper summary: Emmy: It’s interesting how they define delta infinity based on those coordinates, making it dependent on the target point a itself <ref:2611.08317#pg3>. This dependency is what allows them to get these exact formulas for expectation and variance in d dimensions where coordinate subsequences are super-increasing <ref:2611.08317#pg3>.
Kolya: So, the core mechanism seems to be that by tracking the rectangle's boundary, they reduce this complex covering problem to random subset sums of even and odd indexed Fibonacci numbers <ref:2611.08317#pg2>. That simplifies things a bit from the perspective of a probabilistic bound <ref:2611.08317#pg2>.
Ada: Yes, tracking the boundary helps simplify the problem to random subset sums because those coordinate-weight sequences are super-increasing <ref:2611.08317#pg3>. This ordering lets them get exact covering probabilities and formulas for expectation and variance <ref:2611.08317#pg3>.
Emmy: They even define a canonical threshold word based on the most significant bit order, which leads to exact finite time covering probabilities for each coordinate <ref:2611.08317#pg4>. That level of precision is quite high for this kind of random structure.
Kolya: If we look at the distribution of that covering time, they find that the independence between coordinate delays leads to a probability formula P(T less than or equal to n) equals Y r in I one minus Fr(n) <ref:2611.08317#pg4>. What does that tell us about the typical waiting time versus the maximum possible time?
Ada: It shows that because the delays of the coordinates are independent, you can calculate how likely it is to cover a point within a certain time n, and this leads directly back to those expected covering times we discussed earlier <ref:2611.08317#pg4>.
Emmy: Now, I want to shift gears a bit and look at the second part of the paper they present. It extends the construction itself to a square by square one using circular arcs and quintic connectors <ref:2611.08317#pg5>.
Kolya: That sounds like it’s trying to build a more geometrically continuous version of this random spiral, maybe something that looks more like the actual Fibonacci spiral we see in nature rather than just a set of discrete squares <ref:2611.08317#pg5>.
Ada: Exactly. They use one step lookahead and get a continuously differentiable parametrization for this new construction, which recovers the standard Fibonacci spiral when you use the correct rules <ref:2611.08317#pg5>. It’s a starting point for geometric study rather than just a final physical model <ref:2611.08317#pg5>.
Emmy: The resulting curve is globally C one, meaning it’s smooth, and within each nonstandard segment, the quintic and circular arc meet with two continuity <ref:2611.08317#pg5>. That level of smoothness is important for geometric analysis <ref:2611.08317#pg5>.
Kolya: So, to summarize what we've heard about the Random Fibonacci Tilings paper, it tackles a randomized version of the Fibonacci spiral construction and provides precise mathematical tools to analyze how quickly that growing shape covers lattice points in higher dimensions <ref:2611.08317#pg3>.
Paper summary: Ada: Right, so the key findings are that while the mean covering time grows logarithmically with distance, it remains well-behaved because the variance is bounded and they have exponential tails for delays beyond early stages <ref:2611.08317#pg3>.
Emmy: And they use tools like super-increasing sequences and canonical threshold words to get exact probabilities for covering coordinates in d dimensions <ref:2611.08317#pg4>. This gives a very concrete view of the probabilistic structure behind the geometry <ref:2611.08317#pg4>.
Kolya: It feels like this work connects discrete combinatorial objects, like subset sums of Fibonacci numbers, to continuous geometric patterns in a way that is hard to see from just looking at the spiral itself <ref:2611.08317#pg2>.
Ada: That connection is what makes it interesting. It’s not just about the geometry; it’s about using number theory, specifically Fibonacci numbers, as a way to understand random growth processes <ref:2611.08317#pg2>.
Emmy: And when we look at the conclusion of this paper, they frame it around several open geometric questions like containment and simplicity for these random spirals <ref:2611.08317#pg5>. They also state that the dominant root rho d determines the macroscopic scale through that expected covering time formula <ref:2611.08317#pg3>.
Kolya: So, for someone just listening to this, what does it ultimately mean about the world? Does this tell us anything about how complex patterns emerge in random growth systems generally?
Ada: It suggests that even when you introduce randomness into a seemingly simple iterative construction like the Fibonacci tiling, you can still apply rigorous number theoretic tools to get precise information about its covering properties <ref:2611.08317#pg2>.
Emmy: The implication is that the structure of these random processes is governed by underlying algebraic properties, specifically those related to super-increasing sequences and subset sums <ref:2611.08317#pg4>. This points toward a deeper structural organization in how these patterns form <ref:2611.08317#pg4>.
Kolya: I see it as showing that the complexity of covering a point isn't just random noise; it follows a predictable logarithmic law related to the dimension and the geometry of the sequence <ref:2611.08317#pg3>.
Ada: So, to wrap up this discussion on Random Fibonacci Tilings, it’s about using number theory to give us a rigorous understanding of how random choices affect geometric growth patterns in higher dimensions <ref:2611.08317#pg2>.
Emmy: And the authors leave us with these big open questions about the actual shapes these randomized spirals can take, like whether they stay contained or how simple they are <ref:2611.08317#pg5>.
Kolya: It’s a lot of math, but it’s trying to map out the behavior of things that grow randomly based on Fibonacci rules, and it does that with some very strong quantitative results <ref:2611.08317#pg3>.
Conclusion: Ada: So we've been looking at how random choices affect growing shapes based on Fibonacci rules, and now we're talking about what this paper, "Random Fibonacci Tilings," actually says about it.
Emmy: It’s a study by the authors focusing on how you randomize the way those squares attach—alternating deterministically but flipping a coin for the direction—and how that affects when your growing rectangle covers a specific spot on a grid.
Kolya: The main thing they show is that even with this randomness, if you're in more than two dimensions, the time it takes to cover a point grows logarithmically with how far away you are from your starting area.
Ada: Logarithmic growth means that as you move farther out, the waiting time gets longer, but not dramatically so—it’s a slow crawl compared to faster growth rates.
Emmy: And they nail down the exact formula for this expected time, which depends on how far away the point is and a specific constant related to that dimension.
Kolya: The interesting part for me is that they get bounds on the variance, meaning while it gets longer, it doesn't become wildly unpredictable; there’s a constant control over how much it fluctuates around the average time.
Ada: They also found exponential tail bounds for those very long waiting times, which tells us that while most points are covered relatively quickly according to that logarithmic law, there are some rare instances where you could wait a very long time before it happens.
Emmy: It sounds like they’ve built a bridge between the discrete math of Fibonacci numbers and the continuous geometry of these growing shapes.
Kolya: I think this is important because it shows that even when you introduce randomness into something that seems so rigid, the underlying structure still dictates a predictable scaling behavior based on those dimensions.
Ada: Exactly, and they also look at extending this to a smoother construction using circular arcs and quintic connectors, which gives us a geometric picture of what these random spirals actually look like.
Emmy: That smooth version is interesting because it recovers the standard Fibonacci spiral when you use the right rules, giving us a baseline for comparison.
Kolya: So, they've given us both a precise way to calculate when things cover points in discrete setups and a geometric idea of what these random paths look like in continuous space.
Department of Mathematics, University of Maryland and Department of Mathematics, Williams College and Department of Mathematics, Missouri State University and Department of Mathematics, University of Rochester and Department of Mathematics, University of Rhode Island
math.PR
Submitted: 2026-11-05
Updated: 2026-11-05
Comments: 33 pages, 6 figures
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 79/100
The gist: The paper studies a randomization of the Fibonacci spiral construction where attachment axes alternate deterministically and direction is chosen by fair coin flips to investigate when a growing…
Key concepts
- Randomization of Construction
- The construction uses alternating deterministic attachment axes and random coin flips to determine direction. This randomization simplifies the problem of tracking a rectangle's boundary into analyzing random subset sums of Fibonacci numbers, allowing for probabilistic analysis.
- Covering Time Analysis
- This measures how long it takes for a growing rectangle to first enclose a target lattice point. In $d$ dimensions, the expected time grows logarithmically with distance from the starting block, while the variance remains bounded. This is analyzed using coordinate subsequences that are super-increasing.
- Weighted Subset Sums
- The covering problem is simplified by viewing it as a random subset sum of fixed weights derived from the rectangle's boundary. Since these weight sequences are super-increasing, they can be ordered canonically, which allows for exact calculation of covering probabilities and expectations.
- Random Fibonacci Spiral Construction
- This extends the standard spiral to a square-by-square tiling using circular arcs and quintic connectors. This construction provides a geometrically continuous version of the Fibonacci spiral, serving as a starting point for further geometric investigation.
Terminology
Summary
The paper studies a randomization of the Fibonacci spiral construction where attachment axes alternate deterministically and direction is chosen by fair coin flips to investigate when a growing rectangle covers a lattice point and how this expected covering time depends on its location
Randomization of the Construction
The study introduces a randomization of the square-joining rule where the attachment axis alternates deterministically, while fair coin flips determine direction The main question is when the growing rectangle first covers a given lattice point Tracking the rectangle’s boundary reduces this question to random subset sums of even- and odd-indexed Fibonacci numbers For d ≥ 2, the expected covering time grows logarithmically with distance from the initial block, while the variance remains uniformly bounded Exponential tail bounds for the delay beyond the earliest feasible covering stage are obtained.
Covering Time Analysis in d Dimensions
The analysis extends to d dimensions where coordinate subsequences are super-increasing, allowing for exact covering probabilities and formulas for expectation and variance For fixed d ≥ 2, the expected covering time is given by E[T(a)] = log δ∞(a) log ρd + Od(1) as δ∞(a) → ∞. The variance remains bounded, and the mean grows logarithmically with distance while the variance remains bounded. p. 2
Weighted Subset Sums and Canonical Ordering
The covering problem is simplified by tracking the rectangle’s boundary, which reduces it to random subset sums of fixed weights The coordinate-weight sequences are superincreasing, which orders the subset sums and yields exact covering probabilities, expectations, and variances. A canonical threshold word is defined based on the most-significant-bit order This leads to exact finite-time covering probabilities for each coordinate. p. 9
Covering Time Distribution and Limiting Behavior
The covering time distribution for a target point a is determined by the independence of coordinate delays, leading to P(T ≤ n) = Y r∈I 1 − Fr(n). For fixed d ≥ 2 and I(a) ≠ ∅, the expected covering time is E[T] = logρd δ∞(a) + Od(1), Var(T) = Od(1), uniformly over targets with I(a) ≠ ∅. p. 0 The variance is bounded and the expectation tends to infinity as the target moves away from the initial hypercube. p. 0
Random Fibonacci Spiral Construction
The construction is extended to a squareby-square construction using circular arcs and quintic connectors, which uses one-step lookahead and admits a continuously differentiable parametrization This construction recovers the Fibonacci spiral for the standard tiling. The resulting curve is globally C 1 with each segment contained in its assigned square, and within each nonstandard segment, the quintic and circular arc meet with C 2 continuity. p. 0 The construction should be viewed as a starting point rather than a final geometric model. p. 1
Geometric Questions and Conclusion
The paper outlines several open geometric questions regarding the random spiral, including containment, simplicity, winding, and optimality of the resulting curves. The exact expected covering time is given by a complex formula involving phase sums over active-coordinate subsets. p. 0 The dominant root ρd determines the macroscopic scale through E[T] = logρd δ∞(a) + Od(1). p. 6 The centered fluctuations have exponential tails and moments bounded uniformly over the target. p. 2 The random-spiral construction gives a geometric companion to the covering theory. p. 1
References
[Boo05] C. de Boor. “Divided differences”. In: Surveys in Approximation Theory 1 (2005), pp. 46–69
[Cor+96] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth On the Lambert W function
. In: Advances in Computational Mathematics 5 (1996), pp 329–359
[EM26] Douglas Larsson Engholm and Steven J. Miller “The Fibonacci Rectangle Game: Two First-Move Classes and a Triangle-Induced Choice”. p. 3 In: The Fibonacci Quarterly (2026)
[HS64] V. C. Harris and C. p. 4 C. Styles “A generalization of Fibonacci numbers”. p. 0 In: The Fibonacci Quarterly 2 (1964), pp 277–289
[Kos01] T. Koshy Fibonacci and Lucas Numbers with Applications New York Wiley Interscience 2001
[MOV96] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone Handbook of Applied Cryptography Linked PDF Chapter 8 Boca Raton CRC Press 1996
[OEI] OEIS Foundation Inc The On-Line Encyclopedia of Integer Sequences entry A000930 Narayana’s cows sequence https://oeis.org/A000930 Accessed September 1, 2026
[arXiv:2611.08317v1] math. p. 0
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved covering time estimation for lattice points in d dimensions: The system can determine that
the expected covering time grows logarithmically with distance from the initial block, while the variance remains uniformly bounded
for d greater than or equal to 2 (Theorem 5.2). -
Enhanced statistical analysis of target location uncertainty: The AI can provide an estimate for the deviation of the covering time from its deterministic threshold, stating that
E[T − B(a) q] = Od,q(1)
uniformly over the target (Theorem 5.10). -
Precise calculation of covering time distribution bounds: The system can calculate the probability that a target is covered by a given move count using the formula "P(T > n) = Y r∈I 1 − Fr(n)" (Theorem 4.3).
-
Accurate prediction of maximum coordinate delay: For any fixed active coordinate r, the system can determine the expected number of updates required for coverage is
E[τr] = mr + 2κr
and its variance isVar(τr) = 6κr − 4κ squared r
(Corollary 3.5). -
Calculation of global covering time moments: The system can calculate the exact second moment of the covering time using the formula
E[T 2] = M2,fin + X∅̸=J⊆I (−1)J+1 RJ z m∗ J 2dm∗HJ + KJ 1 − zJ + 2dzJHJ (1 − zJ) 2
(Theorem 4.6). -
Simulation of random Fibonacci spiral construction: The AI can generate a globally C 1 curve by following the rule
The usual Fibonacci spiral joins quarter-circles drawn in successive squares of the standard tiling,
while usinga quintic connector followed by a smaller quarter-circle
for nonstandard transitions (Theorem 6.5). -
Analysis of geometric segment properties: The system can verify that segments in the random spiral construction satisfy
Fn ≤ elln ≤ 1 + π/4 Fn
(Proposition 6.7) and that the resulting curve is simple (Theorem 6.5).
Sources
- Divided Differences
- The Fibonacci Rectangle Game: Two First-Move Classes and a Triangle-Induced Choice
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves