# How quickly can this function be computed?

I can show that $\lambda (n)=i^{\tau(n^{2})-1}$, where $\lambda (n)$ is the Liouville function, $\tau(n)$ is the divisor function, and $i$ is the imaginary unit.

My question is as stated, and what is the best it could be currently? Does the divisor function make it any easier?

I have little to no experience with computation complexity calculation.

• It's $O(1)$. Maybe you mean to ask about its partial sums? – Qiaochu Yuan May 14 '16 at 0:11
• @Qiaochu Yuan Perhaps. I'm really not clear at all how to measure computing time. This is what I mean to find. I'm curious to know if this form makes computation of the terms any easier than it's usual definition. Or if the summatory function's complexity is improved. – e2theipi2026 May 14 '16 at 0:15
• Oh, you want to know how quickly the function can be computed? I thought you were asking how quickly the function grows. – Qiaochu Yuan May 14 '16 at 0:19
• Lol, yes. As I said, I have no experience in this area. Forgive my ignorance in this area. I'm wondering if its easier to calculate Liouville function for large n with this form. – e2theipi2026 May 14 '16 at 0:20
• No, it's no easier to calculate the Liouville function this way. No matter what you do you can't get around the fact that calculating the Liouville function is at least as hard as determining whether $n$ is prime, which is hard, although now known to be doable in polynomial time (in $\log n$). – Qiaochu Yuan May 14 '16 at 0:25

Usually, the definition is $\lambda (n)=(-1)^{\Omega(n)}$ where $\Omega(n)$ is the number of prime factors of $n$ counted with multiplicity.

If $n =\prod p_n^{k_i}$ then $\Omega(n) =\sum k_i$.

Therefore the time to compute $\Omega(n)$ is at most the time needed to factor $n$, so you can look at articles like this to get an idea of what is currently known:

https://en.wikipedia.org/wiki/Integer_factorization

• Yes, but my version doesn't have bigomega, it has the divisor function. I was wondering if this would make it easier. – e2theipi2026 May 14 '16 at 0:38
• From what I have seen, it doesn't seem to. But nobody seems to know for sure. – marty cohen May 14 '16 at 1:26
• Nobody seems to know for sure? – e2theipi2026 May 14 '16 at 12:20
• They don't know if it is less difficult than factoring. – marty cohen May 14 '16 at 15:44
• Who is "they"? Were you referring to people you were with? – e2theipi2026 May 14 '16 at 19:48