Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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})$. –  André Nicolas Sep 1 '12 at 13:50

2 Answers 2

Here's how one obtains $O(\sqrt n)$ in the orignal problem with the quarter circle: By identifying $\langle a, b\rangle$ with $[a,a+1]\times[b,b+1]$, you see that the squares belonging to points of $A$ cover the quarter circle's area $\frac\pi4 n$. On the other hand, by identifying $\langle a, b\rangle$ with $[a-1,a]\times[b-1,b]$, you see that the squares belonging to points of $A$ are contained in an area of $\frac\pi4 n + 2\sqrt n + 1$ (adding a strip of width 1 at the left and lower edge). Hence $\frac \pi4 n\le |A|\le \frac \pi4 n + 2\sqrt n + 1$. We made use of the fact that $x\mapsto \sqrt{n-x^2}$ is strictly decreasing.

share|improve this answer

The general problem you are formulating is actually a classical field of mathematics; it's called diophantine geometry, and there are lots of books dealing with it. This already is proof that there can be no simple general method to determine the cardinality of sets $A$ considered in your question.

In particular it is one of the most famous unolved problems to get the "optimal" error term in the estimation of the number of integer points in the disk $D_r:= \bigl\{(x,y)\bigm|x^2+y^2\leq r^2\bigr\}$.

share|improve this answer
    
Well, I do not claim there exists an algorithm to determine the cardinality of any set. I'm rather asking to show me how to obtain some approximation by applying the tools I mentioned (to the given example for instance). That's because I know of those methods, but have never used them myself and lack some practice. –  Quintofron Sep 2 '12 at 10:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.