Counting Lattice Rectangles in $O(n\log n)$ Operations

Let $F(n)$ be the number of rectangles, not necessarily axis-parallel, whose vertices belong to the $n\times n$ square grid of lattice points. We give an exact algorithm that computes one prescribed value $F(n)$ in $O(n\log n)$ arithmetic operations and $O(n^{3\mathrm{/}4})$ arithmetic words of working memory. The algorithm decomposes the count into Möbius divisor layers, partitions weighted floor-moment queries by a truncated Euclidean coefficient-cone recursion, and reuses uniform marker grids along common coefficient paths. Each marker requires only its uniform cell and constant-size corrections at nearby boundaries, which select an exact precompiled cell operator. All integer operands have $O(\log n)$ bits. An exact 128-bit C++ implementation for the reported input range is compared experimentally with the previous $O(n{\log }^{2}n)$ algorithm.