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})$. |
|||||
|
|
This is not an answer to your (interesting) question, but instead mentions a possibly related question.
Perhaps their ~30 references, or the ~10 subsequent citations, might lead somewhere...?
|
||||
|
|
