5
$\begingroup$

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.

$\endgroup$

2 Answers 2

9
$\begingroup$

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})$.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Igor Rivin
    Feb 4, 2017 at 2:12
4
$\begingroup$

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."


enter image description here


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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