{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidr4zmnwh2nhsae7uxltnq3bbpyfwjkqauy2su6sngwr22q4pvxti",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkhv4by4nbq2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.22456v1",
  "publishedAt": "2026-04-27T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Dmitry Babichev",
    "Sergey Babichev"
  ],
  "textContent": "**Authors:** Dmitry Babichev, Sergey Babichev\n\nWe 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 a sequence of exact algorithms of complexity $O(n^2)$, $O(n^{3/2}\\log n)$, $O(n^{4/3}\\log n)$, and finally $O(n\\log^3 n)$. The main idea behind the near-linear algorithm is to reduce the geometric summation to a constant-size family of weighted floor sums closed under Euclidean-style affine and reciprocal transformations, and hence evaluable in $O(\\log n)$ time per query. Besides the exact algorithmic result, we also derive a two-term asymptotic expansion, $F(n)=\\frac{4\\log 2-1}{π^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.",
  "title": "Counting All Lattice Rectangles in the Square Grid in Near-Linear Time"
}