Source-linked AI summary
Packing Tails of Reciprocal Rectangles into Squares of Equal Area
Yu Jiang
TL;DR
The original problem of packing the full sequence of rectangles 1/n × 1/(n + 1), starting at n = 1, remains open. The proof recursively decomposes rectangular gaps, controls geometric space and index load separately, and passes from finite-prefix packings to an infinite packing by compactness. Every sufficiently late tail has an infinite packing in an equal-area square, obtained from finite-prefix packings through compactness.
Problem
The original problem of packing the full sequence of rectangles 1/n × 1/(n + 1), starting at n = 1, remains open.
Source: Introduction · p. 1Method
The proof recursively decomposes rectangular gaps, controls geometric space and index load separately, and passes from finite-prefix packings to an infinite packing by compactness.
Source: §1.1 · pp. 3–4Results
Every sufficiently late tail has an infinite packing in an equal-area square, obtained from finite-prefix packings through compactness.
Source: §1 · p. 3, §1.1 · p. 4Takeaways & Limitations
The equal-area packing theorem applies to sufficiently late tails of reciprocal rectangles.
Source: Introduction · p. 1, §1 · p. 3The proof does not claim that m = 1 works or that its sufficient threshold is optimal.
Source: §13 · p. 37
Abstract
from arXiv · showhide
The Meir--Moser rectangle-packing problem asks whether all rectangles with side lengths \(1/n\) and \(1/(n+1)\), for \(n\ge1\), can be packed into the unit square with pairwise disjoint interiors. We establish a tail version of this problem. Let \(R_n\) denote the rectangle with these side lengths. We prove that there exists an integer \(m_0\) such that, for every \(m\ge m_0\), the family \(\{R_n:n\ge m\}\) admits a packing, by translations and right-angle rotations, into a square of side length \(m^{-1/2}\), with pairwise disjoint interiors. The area of the square equals the sum of the areas of all the rectangles. The geometric construction recursively decomposes rectangular gaps, while local randomized quotas and random permutations assign subsequent integer indices. We separately control the total area of waiting gaps and the assignment load at each index. The proof is organized in six steps: a finite-prefix reduction, geometric row decompositions, an area bootstrap, a sharp source-load estimate, control of the actual adaptive construction, and a compactness limit. For every finite time horizon, the probability of failure has a bound that is independent of the horizon and can be made arbitrarily small. The adaptive step uses a permanent load ledger, actual fresh height queries, and a one-sided comparison with a frozen source experiment. Compactness then yields an infinite packing. The final packing statements have been checked in Lean 4. A sufficient threshold is \(m_0=10^{1000}\). This result applies only to sufficiently late tails and does not resolve the original Meir--Moser rectangle-packing problem for the full sequence starting at \(n=1\), which remains open.
Introduction
The paper proves an equal-area packing theorem for sufficiently late tails of reciprocal rectangles, while the full sequence starting at n = 1 remains unresolved. Its proof separates geometric space control from index-allocation control before using compactness to obtain an infinite packing.
1 Main theorem, conventions, and parameters
- For every sufficiently large m, the rectangles R_n with n ≥ m have an interior-disjoint packing in the square Q_m of side m^-1/2.The original problem for the full sequence starting at n = 1 remains open.Source: Introduction · p. 1, §1 · p. 3
1.1 Proof overview: six steps and their purpose
- The proof separates geometric space control from index-allocation control, then connects finite-prefix packings to an infinite packing by compactness.The six steps include row decompositions, area estimates, source-load estimates, and control of the adaptive construction.Source: §1.1 · pp. 3–4
- A row leaves principal and endpoint gaps for later rectangles, while local randomized quotas assign eligible indices to inherited jobs.The geometric construction and index allocation are treated as distinct requirements.Source: §1.1 · p. 3
1.2 Objects, two ledgers, and indexing
- The geometric ledger tracks current regions, whereas the permanent demand ledger retains registered jobs and can over-count their future index demand.The two ledgers serve different bounds and the demand ledger is not a list of currently empty regions.Source: §1.2 · p. 4
1.3 Fixed parameters and uniformity
- Uniform estimates and fixed parameters are chosen independently of the finite construction horizon, with m increased to keep error terms within fixed margins.The comparison constants and convergence assertions are uniform over finite histories satisfying the geometric conditions.Source: §1.3 · p. 5
2 Admissible index intervals and full-height row geometry
The section specifies which indices can fit a row of a given height and shows that any admissible set of indices can be placed within the row. This yields an exact decomposition into tiles and rectangular gaps.
2 Admissible index intervals and full-height row geometry
- For small row height H, the admissible interval I(H) is nonempty and its indices are determined by whether a tile leaves a suitable gap beneath it.The interval is defined by the bounds f_A(i) ≤ H ≤ f_B(i).Source: §2 · pp. 5–6
- Any k(W,H) distinct admissible indices fit side by side in the row, even when the selected indices are not consecutive.The endpoint retains positive width after placement.Source: §2 · p. 7
- The row decomposes into the selected rectangles, a principal gap below each tile, and an endpoint gap, with interiors disjoint.Each principal gap is itself an inherited job satisfying the same shape condition.Source: §2 · p. 8
3 Endpoint splitting and the total boundary budget
Endpoint splitting preserves the geometric conditions needed for recursive packing and provides a finite boundary budget. The key contraction appears over two generations rather than after a single split.
3 Endpoint splitting and the total boundary budget
- Endpoint children satisfy the inherited-job shape condition and have shorter sides at most three quarters of the parent’s height.This closure permits the row-fitting lemma to be applied recursively.Source: §3 · pp. 8–9
- The sum of endpoint-job shorter sides grows by at most a factor of 1 + η in one generation, but contracts by factor r over two generations.The two-generation contraction is the useful bound for the endpoint forest.Source: §3 · pp. 8–9
- An ordinary row and all its endpoint descendants use less than 18H total cut-parent height and create less than 55H total endpoint semiperimeter.The bounds also apply to truncated finite trees, without assuming future assignments are feasible.Source: §3 · p. 10
4 Local integer quotas
The section converts fractional job demands into integer assignments while preserving each job’s total demand. Bin capacity bounds then allow a random permutation to assign distinct indices and retain main positions.
4 Local integer quotas
- Randomized cumulative rounding produces nonnegative integer quotas whose sum equals each job’s total demand exactly.The quota in any one bin changes by at most one as the job’s uniform random mark varies.Source: §4 · pp. 10–11
- When a bin’s total quota is within capacity, a uniform permutation assigns distinct indices to jobs and leaves at least 0.1 of its positions as main positions.The construction uses independent permutations in different bins.Source: §4 · p. 11
- The randomized quotas in different bins of one job are dependent because they share a random mark, while marks are independent across jobs.Permutations remain independent across bins conditional on all quotas.Source: §4 · pp. 10–11
5 The geometry of main rows
Main rows turn unassigned main positions into strips cut from the primary rectangle. Their membership is settled before the row height is sampled, supporting predictable geometry and later load estimates.
5 The geometry of main rows
- Each main position is an index left unassigned to inherited jobs, used to start a strip in the primary rectangle.The row's membership is fixed before its height is randomized.Source: §5 · p. 12
- The row procedure selects the longest initial segment satisfying the prescribed width condition, then samples its height from a shrunken interval around the reference index.The sampled height is H = 1/(z + 1) + U z^-p, with U uniform on [A + εz, B − εz].Source: §5 · p. 12
- The main-row size and height lemma supplies the selected row's bounds, while the construction separately proves its span is O(S^q) and its batch size is comparable to S.The span argument uses the availability of main positions within bins; q > 1/2 ensures enough width before a bin is exhausted.Source: §5 · p. 12
- A main row is placed in a full strip removed from the primary rectangle, leaving principal gaps and an endpoint that is split into two jobs.The strip spans the primary rectangle's shorter side.Source: §5 · pp. 12–13
- If the primary rectangle has aspect ratio at most 2 and the strip height is at most half its shorter side, removing the strip preserves that aspect-ratio bound.The side lengths may be interchanged after the cut.Source: §5 · p. 13
6 An area bound for waiting principal gaps
The section bounds the area of small principal gaps deterministically, without assumptions about how gaps are generated or how their heights depend on their indices.
6 An area bound for waiting principal gaps
- The deterministic area estimate considers principal gaps satisfying the stated profile, with at most one gap per index, and sums the area of gaps whose heights are at most t.It uses an integral comparison after enlarging the sum to include all eligible indices.Source: §6 · p. 13
- The proof bounds each eligible gap's area using its height and index, then divides the sum at the scale where the two terms in the bound meet.Rounding contributes only an extra term of size O(t/a).Source: §6 · p. 13
- The bound permits arbitrary dependence between gap heights and indices and remains valid after deleting gaps already filled or not yet generated.It therefore does not rely on independence, gap-generation density, or successful future assignments.Source: §6 · pp. 13–14
7 Area accounting and the geometric bootstrap
An exact area ledger tracks the primary rectangle, waiting gaps, and reserved future tiles. Area and endpoint-budget estimates then show that the primary rectangle retains enough space for subsequent rows.
7 Area accounting and the geometric bootstrap
- The construction replaces each started parent with row positions, principal gaps, and endpoint children while maintaining disjoint regions; the primary rectangle loses a strip only when a main row starts.The permanent endpoint account adds cut heights and created endpoint semiperimeters without subtracting old parents.Source: §7 · p. 14
- Before index N, the remaining area is exactly 1/N, partitioned among the primary rectangle, waiting principal and endpoint jobs, and reserved rectangle positions.The identity follows from the exact region decomposition, rather than an assumption about future success.Source: §7 · p. 14
- Reserved rectangles not yet used lie in an index interval of length O(N^3/4), so their total area is at most K N^-5/4.The delay before geometrically starting a row keeps its reserved-index span lower order.Source: §7 · p. 15
- For sufficiently large m, the two endpoint budgets stay below Π/2 throughout every finite horizon, while the primary rectangle keeps aspect ratio at most 2 and sufficient area for new rows.The first-failure argument includes a newly generated row in the budget count, ruling out a first budget violation.Source: §7 · pp. 15–16
- The endpoint-area and semiperimeter bounds, combined with Lemmas 6.1 and 7.1 and exact area identity (7.1), yield (7.2), strictly stronger than inductive lower bound (7.3).A main row has height O(1/N) = o(wN), so its strip fits.Source: §7 · p. 16
8 Principal-gap load for a fixed input pool
The fixed-input-pool analysis bounds principal-gap load by combining deterministic support and mean estimates with concentration bounds for quota marks and bin permutations. It then separately controls actual main-height queries before giving the source-only tail bound.
8 Principal-gap load for a fixed input pool
- 3e^-κsN^7/50 bounds the probability that a working bin reaches 0.90ℓb occupancy or the fixed-pool observable ZN reaches 0.83.The constants and large-scale threshold are uniform over the considered pools.Source: §8 · p. 16
8.1 A single output gap and its deterministic support
- The exact gap profile shows that every source index with nonzero contribution belongs to a deterministic interval; consequently, all contributing indices have size comparable to S, i ≍ S.Source: §8.1 · p. 17
8.2 A deterministic mean envelope for main positions
- The main-position mean estimate uses the shared height within each row and linearity of conditional expectation, not independence among positions.A buffered union of bins covers actual source positions that can contribute to the target.Source: §8.2 · pp. 17–18
8.3 The mean contribution of one inherited row job
- For an inherited row job, the eligible integer positions are counted within its retained window, and formal mean output remains meaningful even when quotas are excessive.Jobs with zero output may still occupy quota copies and displace main-position weight.Source: §8.3 · pp. 18–19
8.4 A nonnegative mass partition and the coefficient 1/p
- The mass partition assigns exactly one unit of total mass to every index, yielding an unweighted leading mean coefficient 1/p and a fixed weighted margin.The verified numerical margin keeps the weighted mean below 0.81.Source: §8.4 · pp. 19–20
8.5 Fluctuations caused by the quota marks
- Quota-mark fluctuations are bounded using independent job marks and bounded differences, without conditioning on quota success.The analysis counts O(S) relevant jobs from the input-load bound.Source: §8.5 · p. 20
8.6 Permutation fluctuations conditional on valid quotas
- With valid quotas fixed, a permutation-exposure martingale controls permutation fluctuations while accounting for dependence among positions in the same bin.The argument does not assume those positions are independent.Source: §8.6 · p. 20
8.7 Actual main queries and their comparison weight
- Actual main-height requests are controlled in their real query filtration by comparing each query's load with its used comparison weight.The estimate is uniform in finite physical horizons and applies to actual runs, including paths that later stop.Source: §8.7 · p. 21
9 Endpoint-load estimates
The section bounds the expected and maximum fractional load contributed by a fresh endpoint cut, then applies these estimates to cuts in their actual creation order.
9 Endpoint-load estimates
- The two children of a fresh cut have total expected fractional load at most (20 + o(1))H, hence at most 21H for sufficiently large N.If neither child can be eligible, the expectation is zero.Source: §9 · pp. 22–23
- A fresh cut contributes at most KN^-11/20 to the endpoint load, including simultaneous eligibility of both children.The bound also covers demand k = 1 and partial intersection of the eligible interval with the density support.Source: §9 · p. 23
- For actual endpoint cuts, combining both children into one increment lets the total cut-height budget control predictable means and the permanent endpoint ledger.The cited proof bounds total predictable mean by 0.0021 and pads later increments with zero if the process stops early.Source: §9 · pp. 22–23
10 Revelation order in the recursive construction
The construction schedules random information so that jobs are created before relevant data are revealed. It then compares the actual adaptive run with a frozen source experiment without conditioning on a particular continuous-valued history.
10.1 Random coordinates and physical operations
- The program distinguishes physical cursor time from program-step time and reveals only coordinates needed for the current operations.Job quota marks are first revealed at the leftmost complete bin; bin permutations are then revealed independently, and the same job mark is reused for later quotas.Source: §10 · p. 23, §10.1 · p. 23
- A job’s geometry is registered before its quota is revealed, and allocation certificates are checked before geometry is activated at an assigned index.The ordering makes data for complete bins available before the verification deadline; certificates do not use rejection sampling or resampling.Source: §10.1 · pp. 23–24
10.2 Source bands and the actual freezing time
- At the freeze, the relevant source pool is complete while its quota and working-permutation coordinates remain unread.The source bands and timing margins ensure that relevant jobs are created before the freeze and their shared quota marks are requested later.Source: §10.2 · p. 25
10.3 Applying a fixed-pool estimate at a random history
- The random-history argument partitions freeze histories into countably many cases, retains their probabilities, and applies the fixed-pool bound without conditioning on a specific real-valued history.The unread source-coordinate block has its full joint law on each case, including dependencies from shared job marks; summing weighted bounds introduces no query-count or pool-count factor.Source: §10.3 · p. 26
11 Actual obstructions and finite-prefix existence
This section turns fixed-time source estimates into bounds for the actual adaptive construction, then proves finite-prefix existence uniformly in the terminal index. The construction terminates deterministically, while successful samples may differ between finite horizons.
11 Actual obstructions and finite-prefix existence
- A least-obstruction argument makes the source input good using smaller indices, while the order in which cached certificates are used does not define the probability events.On the resulting event, comparison positions have good input and already cached working bins have good certificates.Source: §11 · p. 27, §11.1 · p. 27
11.1 Events indexed by the detected integer
- The obstruction events separate load violations from good-input occupancy failures and use the least overloaded index without conditioning random marks on that event.The event definition distinguishes a bin with bad input from a good-input occupancy obstruction.Source: §11.1 · p. 27
11.2 The actual load comparison, one step at a time
- A one-sided ledger comparison bounds actual principal load by frozen source cost plus actual main-query excess, including on stopped paths.Committed main rows, inherited rows, and used main weight are charged without counting a row twice or treating unread labels as final.Source: §11.2 · pp. 28–29
11.3 Persistent detection and the principal tail
- The actual reduced principal-load tail is bounded uniformly over finite terminal indices by combining the frozen-source estimate with persistent detection.The persistent-event argument applies fixed-time bounds to events that occur at every sufficiently late time, not to a one-time occurrence.Source: §11.3 · p. 29
11.4 Endpoint and bin events
- Endpoint and bin obstructions are controlled using actual cut queries and unread quota marks at a past freeze, with bad-input caches charged to their original tested indices.The cut budget is checked before sampling, and the endpoint ledger is permanent.Source: §11.4 · pp. 29–30
11.5 Termination, the union bound, and finite existence
- For one sufficiently large m, every finite prefix from R_m through R_L packs into the same square Q_m, because the obstruction probability is below one uniformly in L and the program terminates.The successful sample may depend on L; the section does not assert a single infinite successful random trajectory.Source: §11.5 · pp. 31–32
12 A compactness limit and the area identity
Finite-prefix packings in one closed square yield an infinite packing by compactness. The area argument then shows that the union of the rectangles has the square’s area.
12 A compactness limit and the area identity
- Nested nonempty closed sets of finite-prefix placements in a compact product space have a common point satisfying every tile and pairwise constraint.Non-strict separation inequalities preserve boundary contact in the limit.Source: §12 · p. 32
- The countable union of rectangle boundaries has area zero, so the union’s area equals the sum of the rectangle areas and its complement in Q_m has area zero.The proof applies countable additivity first to the disjoint open interiors, then adds back the zero-area boundaries.Source: §12 · p. 33
13 Selection of a single threshold m0
The proof selects one sufficient threshold by imposing finitely many uniform conditions and a convergent-series tail condition. At that threshold, every finite-horizon construction has positive probability of success, and the infinite packing follows without increasing the threshold.
13 Selection of a single threshold m0
- The threshold is chosen by fixing the numerical parameters and margins, then increasing m to satisfy the geometric, area, and probability requirements.The requirements include complete bins, nonempty height intervals, endpoint budgets below Π/2, and a tail sum below 1/2.Source: §13 · p. 33
- A finite list of threshold conditions and one condition on a convergent-series tail can be combined by taking their maximum.The estimates are verified uniformly over finite terminal indices, and the numerical threshold is not optimized.Source: §13 · pp. 33, 37
- m0 = 101000 is a sufficient threshold: every finite-horizon construction has positive probability of success, and the infinite packing requires no larger threshold.The section states that the exponent 1000 is chosen for convenience, not optimality.Source: §13 · p. 37
Appendix A Two probability inequalities
Appendix A gives finite-horizon concentration inequalities for the proof's probability estimates. It presents a bounded-differences bound and a predictable-mean-budget bound for sequential nonnegative increments.
Appendix A Two probability inequalities
- The appendix restricts applications to finite horizons and does not apply these inequalities directly to an infinite random process.The finite adaptive histories and their conditional expectations are defined on the stated measurable sample space.Source: Appendix A · p. 38
- The bounded-differences inequality controls an upper tail when changing one independent input changes the output by at most its assigned amount.The proof derives the bound using a Doob martingale formed by revealing independent coordinates in sequence.Source: Appendix A · p. 38
- The predictable-mean-budget inequality applies to nonnegative random variables revealed sequentially, with conditional means bounded by a total budget.Stopped increments are set to zero, allowing the finite-horizon statement to cover steps that may not be performed.Source: Appendix A · pp. 38–39