Counting dyadic equipartitions of the unit square

Jeffrey C. Lagarias, Joel H. Spencer, Jade P. Vinson

Research output: Contribution to journalArticlepeer-review

Abstract

A dyadic interval is an interval of the form [j/2k,(j+ 1)/2k], where j and k are integers, and a dyadic rectangle is a rectangle with sides parallel to the axes whose projections on the axes are dyadic intervals. Let un count the number of ways of partitioning the unit square into 2n dyadic rectangles, each of area 2-n. One has u0 = 1, u1 = 2 and un = 2un-1 2 - un-24. This paper determines an asymptotic formula for a solution to this nonlinear recurrence for generic real initial conditions. For almost all real initial conditions there are real constants ω and β (depending on u0, u1) with ω > 0 such that for all sufficiently large n one has the exact formula un = ω2ng(βλn), where λ = 2√5 - 4 ≈ 0.472, and g(z) = ∑j=0 cjzj, in which c0 = (-1 + √5)/2, c1 = (2 - √5)/2, all coefficients cj lie in the field (√5), and the power series converges for z < 0.16. These results apply to the initial conditions u0 = 1, u1 = 2 with ω ≈ 1.845 and β ≈ 0.480. The exact formula for un then holds for all n ≥ 2. The proofs are based on an analysis of the holomorphic dynamics of iterating the rational function R(z) = 2 - 1/z2.

Original languageEnglish (US)
Pages (from-to)481-499
Number of pages19
JournalDiscrete Mathematics
Volume257
Issue number2-3
DOIs
StatePublished - Nov 28 2002

Keywords

  • Asymptotic enumeration
  • Holomorphic dynamics

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Counting dyadic equipartitions of the unit square'. Together they form a unique fingerprint.

Cite this