Computing All Lattice-Rectangle Counts by Rational Staircase Sums

2026/07/20 by Dmitry Babichev, Denis Pinchuk · 1 citation
#cs.CG

paper · pdf

Abstract

Let F(n) be the number of rectangles, not necessarily axis-parallel, whose vertices belong to the n× n square grid of lattice points. We compute the complete table F(1),…,F(N) exactly in O(M(N)log N) coefficient-ring operations and O(Nlog N) ring elements of working memory, where M(N) is a regular bound for multiplying degree-N polynomials. The ring-level statement assumes that 6 is invertible; over \mathbb Z the only division is instead performed exactly in the elementary boundary term. With quasi-linear polynomial multiplication the arithmetic bound is O(Nlog² N). The algorithm applies a square-root cover before coefficient extraction and evaluates the resulting rational wedge and triangular sums by a local-denominator divide-and-conquer recursion. Primitive directions are recovered coefficientwise by Möbius inversion, followed by five prefix sums. A modular number-theoretic-transform (NTT) implementation with certified Chinese-remainder (CRT) recovery is evaluated experimentally against the O(N^3/2) all-values algorithm.

Citations

• Counting Lattice Rectangles in O(nlog n) Operations
• An algorithm for the machine calculation of complex Fourier series

Cited by

• Counting Lattice Rectangles in O(nlog n) Operations

Related

• Counting Lattice Rectangles in O(nlog n) Operations
• Explicit and efficient formulas for the lattice point count in rational polygons using Dedekind-Rademacher sums
• Explicit Formula for Counting Lattice Points of Polyhedra
• Pourchet's theorem in action: decomposing univariate nonnegative polynomials as sums of five squares
• On the error term of a lattice counting problem