arxiv: 2604.22456 · v2 · submitted 2026-04-24 · 💻 cs.CG

Recognition: unknown

Counting All Lattice Rectangles in the Square Grid in Near-Linear Time

Dmitry Babichev , Sergey Babichev

Authors on Pith no claims yet

Pith reviewed 2026-05-08 08:41 UTC · model grok-4.3

classification 💻 cs.CG

keywords lattice rectanglescounting algorithmsfloor sumsasymptotic expansionsquare gridprimitive directionsdivisor layerscomputational geometry

0 comments

The pith

A divisor-layer algorithm counts every lattice rectangle in the n-by-n grid, tilted or not, in O(n log squared n) time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops exact algorithms for counting all lattice rectangles inside the square [0,n) by [0,n), including those that are not axis-aligned. Starting from the usual parametrization by a primitive direction vector and two side lengths, the problem is reduced to families of weighted floor sums that stay closed under affine and reciprocal transformations. This yields a sequence of algorithms culminating in a divisor-layer method of complexity O(n log squared n), an all-values routine up to N in O(N to the 3/2), and a two-term asymptotic formula for the total count F(n) with an explicit second coefficient B.

Core claim

The central claim is that the exact count F(n) of all lattice rectangles in [0,n) x [0,n) admits an O(n log squared n) algorithm obtained by reducing the geometric summation to constant-size families of weighted floor sums closed under Euclidean-style affine and reciprocal transformations, together with the independent asymptotic F(n) = ((4 log 2 - 1)/pi squared) n to the fourth log n plus B n to the fourth plus o(n to the fourth) whose explicit B confirms large-n numerical results.

What carries the argument

The divisor-layer algorithm that processes constant-size families of weighted floor sums closed under affine and reciprocal transformations.

Load-bearing premise

The geometric counting reduces to constant-size families of weighted floor sums closed under affine and reciprocal transformations without missing or overcounting any rectangles.

What would settle it

For n equal to 20, run the divisor-layer algorithm and compare its output to an exhaustive enumeration of all candidate rectangles generated from every primitive direction pair and every valid side length.

read the original abstract

We study the exact counting problem for all lattice rectangles contained in the square $[0,n)\times[0,n)$, including non-axis-parallel ones. Starting from the standard parametrization by a primitive direction $(u,v)$ and two side lengths, we derive several exact algorithms: the classical $O(n^2)$ sweep, decompositions of complexity $O(n^{3/2}\log n)$ and $O(n^{4/3}\log n)$, a ten-moment weighted-floor-sum reduction of complexity $O(n\log^3 n)$, and a divisor-layer algorithm with the complexity $O(n\log^2 n)$. We also give an all-values algorithm that computes $F(1),\ldots,F(N)$ in $O(N^{3/2})$ arithmetic operations. The main idea behind the near-linear one-value algorithms is to reduce the geometric summation to constant-size families of weighted floor sums closed under Euclidean-style affine and reciprocal transformations. Besides the exact algorithmic results, we derive a two-term asymptotic expansion, $F(n)=\frac{4\log 2-1}{\pi^2}n^4\log n+B\,n^4+o(n^4)$ with the explicit formula for $B$, which provides an independent consistency check for the large-$n$ numerical data produced by the algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a concrete O(n log² n) exact algorithm for counting lattice rectangles via closed families of weighted floor sums, plus an explicit two-term asymptotic, but the completeness of the reduction is the part that needs close checking.

read the letter

This paper's main contribution is a divisor-layer algorithm that counts all lattice rectangles in an n by n grid in O(n log² n) time, plus a two-term asymptotic expansion with an explicit constant B that serves as a consistency check. The work starts from the usual parametrization using primitive directions (u,v) and side lengths. It reduces the problem to a constant number of families of weighted floor sums that are closed under affine and reciprocal transformations. From there it builds the faster algorithms, including the O(n log³ n) ten-moment version and the better divisor one. They also give a way to compute the function for all values up to N in O(N^{3/2}) time. The asymptotic F(n) = ((4 log 2 -1)/π²) n⁴ log n + B n⁴ + o(n⁴) is derived independently and used to verify large-n runs. What stands out is how they leverage the closure property to get near-linear time. That is a clear step past the classical sweep and the earlier decompositions they cite. The explicit B is useful for anyone who wants to understand the leading terms without running the code. The potential weak point is whether the reduction really captures every rectangle exactly once. The transformations have to map the sums back into the same families without omissions or duplicates for all possible (u,v) and lengths. If there is any direction where an extra base case appears or where the affine map takes it outside the closed set, the exact count would be off. The paper asserts the closure, and the numerical match with the asymptotic gives some reassurance, but a referee would want to see the full case analysis for the families. This is aimed at computational geometers who care about exact enumeration of lattice objects or fast methods for floor sums. Someone implementing a counter for moderate n or studying the growth rate will find it directly useful. It is solid enough to deserve peer review; the algorithmic claims are specific and the approach is grounded in standard techniques, even if the closure argument needs careful checking.

Referee Report

2 major / 2 minor

Summary. The manuscript presents exact algorithms for counting all lattice rectangles (axis-parallel and tilted) in the square [0,n)×[0,n). Starting from the standard parametrization by primitive directions (u,v) and side lengths, it derives a classical O(n²) sweep, decompositions of O(n^{3/2} log n) and O(n^{4/3} log n), a ten-moment weighted-floor-sum reduction of O(n log³ n), a divisor-layer algorithm of O(n log² n), and an all-values algorithm computing F(1)…F(N) in O(N^{3/2}) operations. It also derives the two-term asymptotic F(n)=(4 log 2 -1)/π² n⁴ log n + B n⁴ + o(n⁴) with explicit B, used as an independent consistency check.

Significance. If the central reduction to constant-size families of weighted floor sums closed under Euclidean affine and reciprocal transformations is complete and duplication-free, the work would constitute a significant advance in exact geometric counting, delivering near-linear single-n algorithms together with a subquadratic all-values procedure and an explicit asymptotic that cross-validates large-n outputs. The explicit formula for B and the reduction to closed floor-sum families (if fully verified) are particular strengths.

major comments (2)

[ten-moment weighted-floor-sum reduction and divisor-layer algorithm] The reduction from primitive (u,v) parametrization to constant-size closed families of weighted floor sums (detailed in the ten-moment reduction and divisor-layer sections) is load-bearing for both the O(n log³ n) and O(n log² n) claims; the manuscript asserts completeness and absence of overcounting but must supply an explicit case analysis showing that every tilted rectangle is captured exactly once and that no sum escapes the closed families under the transformations.
[asymptotic expansion] The two-term asymptotic expansion is presented as an independent derivation, yet the explicit formula for the constant B is given without the intermediate steps of the summation; these steps should be included so that the coefficient can be independently verified against the numerical outputs of the algorithms.

minor comments (2)

The O(n^{3/2} log n) and O(n^{4/3} log n) decompositions are mentioned only briefly; a short outline of their geometric partitioning would improve readability without lengthening the paper substantially.
Numerical tables comparing algorithm outputs to the asymptotic for large n should include the observed difference scaled by n⁴ to make the o(n⁴) term visible.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below. Both suggestions can be incorporated by expanding the relevant sections, which will strengthen the rigor of the presentation without altering the core results.

read point-by-point responses

Referee: [ten-moment weighted-floor-sum reduction and divisor-layer algorithm] The reduction from primitive (u,v) parametrization to constant-size closed families of weighted floor sums (detailed in the ten-moment reduction and divisor-layer sections) is load-bearing for both the O(n log³ n) and O(n log² n) claims; the manuscript asserts completeness and absence of overcounting but must supply an explicit case analysis showing that every tilted rectangle is captured exactly once and that no sum escapes the closed families under the transformations.

Authors: We agree that an explicit case analysis is required to rigorously demonstrate completeness and the absence of overcounting or omissions. The manuscript describes the reduction to constant-size closed families under Euclidean affine and reciprocal transformations but does not enumerate all cases in detail. In the revised manuscript we will add a dedicated subsection to the ten-moment reduction section that provides a complete case analysis: we will enumerate all primitive (u,v) pairs up to the relevant bounds, classify them according to the transformation orbits, and verify that each tilted rectangle (defined by its direction and side lengths) maps to exactly one weighted floor sum in the closed families, with no duplication and no sums left outside the families. This will directly support the correctness of both the O(n log³ n) and O(n log² n) algorithms. revision: yes
Referee: [asymptotic expansion] The two-term asymptotic expansion is presented as an independent derivation, yet the explicit formula for the constant B is given without the intermediate steps of the summation; these steps should be included so that the coefficient can be independently verified against the numerical outputs of the algorithms.

Authors: We acknowledge that the derivation of the constant B is stated without the intermediate summation steps. The manuscript gives the two-term asymptotic with an explicit B but omits the detailed evaluation of the series. In the revised version we will expand the asymptotic analysis section to include the full derivation: we will show the summation over the lattice points in the square, the separation into the logarithmic and constant terms, the explicit evaluation of the resulting zeta-function and divisor sums that produce the coefficient (4 log 2 - 1)/π² for the n⁴ log n term, and the closed-form expression for B obtained from the remaining constant series. This will enable independent verification against the large-n outputs of the algorithms. revision: yes

Circularity Check

0 steps flagged

No circularity: independent derivation of algorithms and asymptotic from standard parametrization

full rationale

The paper begins from the standard primitive (u,v) parametrization of lattice rectangles and derives both the sequence of algorithms (including the O(n log² n) divisor-layer method via reduction to closed families of weighted floor sums) and the two-term asymptotic F(n) = ((4 log 2 - 1)/π²) n⁴ log n + B n⁴ + o(n⁴) as separate mathematical steps. The asymptotic is explicitly positioned as an independent consistency check on the algorithms' large-n outputs rather than being fitted from them or defined in terms of the algorithmic results. No load-bearing step reduces by construction to its own inputs, no self-citation chain is invoked for uniqueness or closure, and the claimed closure under affine/reciprocal transformations is presented as a derived property of the floor-sum families rather than a renaming or tautology. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard lattice geometry and number-theoretic summation techniques; the abstract supplies no free parameters, invented entities, or non-standard axioms beyond the initial parametrization.

axioms (1)

domain assumption All lattice rectangles inside the square are captured exactly once by the parametrization using a primitive direction (u,v) and two side lengths.
Explicitly stated as the starting point for deriving all algorithms and the asymptotic.

pith-pipeline@v0.9.0 · 5531 in / 1312 out tokens · 85972 ms · 2026-05-08T08:41:25.656568+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 1 canonical work pages

[1]

Beck and S

M. Beck and S. Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, 2nd ed., Undergraduate Texts in Mathematics, Springer, New York, 2015

2015
[2]

R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd ed., Addison--Wesley, Reading, MA, 1994

1994
[3]

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, Oxford, 2008

2008
[4]

H. L. Montgomery and R. C. Vaughan, Multiplicative Number Theory I: Classical Theory, Cambridge University Press, Cambridge, 2007

2007
[5]

Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, 3rd ed., Graduate Studies in Mathematics, Vol

G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, 3rd ed., Graduate Studies in Mathematics, Vol. 163, American Mathematical Society, Providence, RI, 2015

2015
[6]

NIST Digital Library of Mathematical Functions, release 1.2.4, F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds., https://dlmf.nist.gov/25.12.E12
[7]

Beck and S

M. Beck and S. Robins, Dedekind sums: a combinatorial-geometric viewpoint, in Unusual Applications of Number Theory, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 64, Amer. Math. Soc., Providence, RI, 2004, pp. 25--35

2004
[8]

M. N. Huxley and W. G. Nowak, Primitive lattice points in convex planar domains, Acta Arith. 76 (1996), 271--283

1996
[9]

P a tra s cu, Farey statistics in time n^ 2/3 and counting primitive lattice points in polygons, arXiv:0708.0080, 2007

M. P a tra s cu, Farey statistics in time n^ 2/3 and counting primitive lattice points in polygons, arXiv:0708.0080, 2007

work page arXiv 2007
[10]

Zagier, Higher dimensional Dedekind sums, Math

D. Zagier, Higher dimensional Dedekind sums, Math. Ann. 202 (1973), 149--172

1973
[11]

Brandolini, L

L. Brandolini, L. Colzani, B. Gariboldi, G. Gigante, and A. Monguzzi, Euler--MacLaurin summation formula on polytopes and expansions in multivariate Bernoulli polynomials, J. Fourier Anal. Appl. 29 (2023), Art. 33

2023
[12]

Baldoni, N

V. Baldoni, N. Berline, J. A. De Loera, M. K\"oppe, and M. Vergne, How to integrate a polynomial over a simplex, Math. Comp. 80 (2011), 297--325

2011
[13]

G. E. Andrews and K. Eriksson. Integer Partitions. Cambridge University Press, 2004

2004
[14]

The On-Line Encyclopedia of Integer Sequences, accessed April 2026

OEIS Foundation Inc., A085582: Number of rectangles (orthogonal or not) with corners on an n n grid of points. The On-Line Encyclopedia of Integer Sequences, accessed April 2026

2026
[15]

Radcliffe

D. Radcliffe. Table and Python script for OEIS A085582. Linked from the OEIS entry A085582, accessed April 2026

2026