2
$\begingroup$

Let me take the following set as an example:

\[ A = \lbrace \langle a,b \rangle \in \mathbb{N} \times \mathbb{N} : a^2 + b^2 \leq n \rbrace . \]

One approach would be to notice that $A$ is the set of all points with natural coordinates inside a quarter of the circle $O((0,0), \sqrt{n})$. If we equate each point with a unit square with its bottom left corner exactly in that point, then the cardinality of $A$ equals $\lfloor \pi n /4\rfloor = \pi n /4 + O(1)$ plus the number of squares intersecting the perimeter. Here I don't know how to justify that the number of "extra" squares is $O(\sqrt{n})$. (Any idea?)

My point though is that I suspect problems of this kind can be solved by a more general method involving either the Euler-Maclaurin summation formula

\[ \sum_{k=a}^{b-1} f(k) = \int_a^b f(x) dx - \dfrac{1}{2} f(x) \bigg|_a^b + \int_a^bB_1(x \bmod 1)f'(x)dx\]

or the estimation that holds for a non-negative function $f$ that is weakly increasing (decreasing) over an interval of $\langle a-1, b+1 \rangle$:

\[ \int_{a-1}^b f \leq (\geq) \sum_{k=a}^b f(k) \leq (\geq)\int_a^{b+1} f.\]

If the given set didn't have such a simple geometric interpretation (yet we could describe it with a functional (in-)equation), the knowledge of how to apply the aforementioned methods would be of much use. I have seen hardly any examples with these methods in action though and I'm having some difficulties applying any of them here.

I'd be grateful for a complete, step-by-step derivation of the estimation of the cardinality of $A$ using this general approach.

It will be much appreciated if you could also show me the extension of these methods to 3-dimensional space. Recently I have come across a similar problem - the task is to estimate

\[ |\lbrace \langle a, b, c \rangle \in \mathbb{N_+^3} : abc \leq n \rbrace| \]

with the relative error $o(1)$ (in another thread on SE). The margin of error seems to be the killing part, so a less accurate estimation (although revealing the application of the methods above) is fine as well.

  • 1
    For the circle problem: Set up the squares as you did. The number of squares is $\lt$ the area of a circle of radius $\sqrt{n}+2$ (since all the squares are fully contained in that circle), and $\gt$ the area of a circle of radius $\sqrt{n}-2$ (we can get away with a constant $\lt 2$). But the difference between the areas of these circles is $O(\sqrt{n})$.2012-09-01

2 Answers 2