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.
 A: 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})$.
A: This is not an answer to your (interesting) question, but instead mentions a possibly related question.

Cardinal, Jean, and Udo Hoffmann. "Recognition and complexity of point visibility graphs." Discrete & Computational Geometry 57.1 (2017): 164-178.
  (earlier arXiv version.)

Perhaps their ~30 references, or the ~10 subsequent citations, might lead somewhere...? 

"We study the recognition problem for point visibility graphs: given a simple undirected graph, decide whether it is the visibility graph of some point set in the plane. We show that the problem is complete for the existential theory of the reals."
  



