A counterexample to Nagamochi's scoring lemma and a new rectangle packing bound

Abstract

Let s(N) denote the smallest side length of a square containing N unit squares with arbitrary orientations and pairwise disjoint interiors. Nagamochi's Packing Unit Squares in a Rectangle (2005) states a rectangle packing bound from which he deduces two infinite families of exact values: s(k²−1) = k and s(k²−2) = k for every integer k ≥ 2. We construct a family of counterexamples, local to a corner of the container, to the scoring assertion in Nagamochi's Lemma 1. These counterexamples show that the published proof of the rectangle bound is incomplete, but do not disprove the bound itself. We then give an independent proof of a weaker rectangle bound using a strip measure. This recovers s(k²−1) = k for every integer k ≥ 2 and yields an explicit lower bound for s(N) that improves strictly on the area bound for every nonsquare integer N ≥ 8. Our argument does not establish Nagamochi's full rectangle bound or the identity s(k²−2) = k.

A localized packing lemma for sets of bounded VC₂-dimension
C. Terry, J. Wolf
arXiv1 Nov 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematics Logic & foundationsarXiv
Greedy Packing of Nested Rings: Placement Rules, a Golden Counterexample, and a Tribonacci Floor
Javier Aguilar Martín
arXiv15 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Geometry & topologyarXiv
The five vertex model on a rectangle
Jan de Gier, Richard Kenyon, Michael Wheeler +1
arXiv2 Nov 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics Mathematical physicsarXiv
Rationality and Quasipolynomiality of Restricted Rectangle Partitions
Mubin Shaikh
arXiv10 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Voltage and current density in a rectangle with point in- and ejection via Green's functions and q-analysis
P. Van Mieghem
arXiv22 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEs Mathematical physicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{karakus2026counterexample,
  title = {{A counterexample to Nagamochi's scoring lemma and a new rectangle packing bound}},
  author = {Hakan Karakuş},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.37410},
  eprint = {2609.37410},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.37410},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - A counterexample to Nagamochi's scoring lemma and a new rectangle packing bound
AU  - Hakan Karakuş
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.37410
UR  - https://arxiv.org/abs/2609.37410
AB  - Let s(N) denote the smallest side length of a square containing N unit squares with arbitrary orientations and pairwise disjoint interiors. Nagamochi's Packing Unit Squares in a Rectangle (2005) states a rectangle packing bound from which he deduces two infinite families of exact values: s(k^2−1) = k and s(k^2−2) = k for every integer k ≥ 2. We construct a family of counterexamples, local to a corner of the container, to the scoring assertion in Nagamochi's Lemma 1. These counterexamples show that the published proof of the rectangle bound is incomplete, but do not disprove the bound itself. We then give an independent proof of a weaker rectangle bound using a strip measure. This recovers s(k^2−1) = k for every integer k ≥ 2 and yields an explicit lower bound for s(N) that improves strictly on the area bound for every nonsquare integer N ≥ 8. Our argument does not establish Nagamochi's full rectangle bound or the identity s(k^2−2) = k.
ER  -

Abstract

Related

Cite