# Complexity of computing the number of visible points

A visible point is a point $(a, b)\in \mathbb{Z}^2,$ with $gcd(a,b)=1$. It is well-known that the number $V(N)$ of visible points with $0<a, b \leq N$ is asymptotic to $N^2/\zeta(2)$, but suppose I really want to compute it exactly. Can it be done in polynomial time (polynomial in $\log N,$ that is)?

If one wants to be more modest, can it be computed in time sublinear in $N?$ Or even linear in $N?$ It can be computed in time $O(N^{1+\epsilon})$, for any $\epsilon>0$, since we can compute the totient function in sub-polynomial time.

There is an algorithm for computing $F(N) = \# \{ (a,b) : 1 \leq a, b \leq N, \gcd(a,b) = 1 \}$ in time $O(N^{5/6 + \epsilon})$. This relies on the algorithm of Deleglise and Rivat (see their paper here) that computes $M(x) = \sum_{n \leq x} \mu(n)$ in time $O(x^{2/3} (\log \log x)^{1/3})$.

The idea is to use $$F(N) = \sum_{a=1}^{N} \sum_{b=1}^{N} \sum_{d | \gcd(a,b)} \mu(d) = \sum_{d=1}^{N} \mu(d) \left\lfloor \frac{N}{d}\right\rfloor^{2}.$$ Now, break this sum up into the terms with $1 \leq d \leq N^{\alpha}$ and the terms with $N^{\alpha} < d \leq N$. The first term $$\sum_{d=1}^{N^{\alpha}} \mu(d) \left\lfloor \frac{N}{d} \right\rfloor^{2}$$ can be computed easily in time $O(N^{\alpha + \epsilon})$, since all $\mu(d)$ for $d \leq N^{\alpha}$ can be computed in time $O(N^{\alpha} \log \log(N))$ (see this preprint). For the range $N^{\alpha} < d \leq N$, let $k = \lfloor N/d \rfloor$. We get the sum $$\sum_{k=1}^{\lfloor N^{1-\alpha} \rfloor} k^{2} \sum_{\substack{e \\ \lfloor N/e \rfloor = k}} \mu(e) = \sum_{k=1}^{\lfloor N^{1-\alpha} \rfloor} k^{2} (M(b_{k}) - M(a_{k})).$$ Here $a_{k}$ and $b_{k}$ are the smallest and largest positive integers $N$ for which $\lfloor N/e \rfloor = k$, respectively. There are $O(N^{1-\alpha})$ terms in the sum above, and each can be computed in time $O(N^{2/3+\epsilon})$. The total running time $O(N^{\alpha + \epsilon} + N^{5/3 - \alpha + \epsilon})$ is minimized when $\alpha = 5/6$ and gives $O(N^{5/6 + \epsilon})$.

• That's very cool! I assume that this is the best known, but will wait a bit before accepting, in case some other wisdom materializes... Feb 4, 2017 at 2:12