Computing the Möbius function


by CRGreathouse
Tags: computing, function, möbius
CRGreathouse
CRGreathouse is offline
#1
Sep17-08, 04:13 PM
Sci Advisor
HW Helper
P: 3,680
From the Mathematica documentation:
SquareFreeQ[n] checks to see if n has a square prime factor. This is done by computing MoebiusMu[n] and seeing if the result is zero; if it is, then n is not squarefree, otherwise it is. Computing MoebiusMu[n] involves finding the smallest prime factor q of n. If n has a small prime factor (less than or equal to 1223), this is very fast. Otherwise, FactorInteger is used to find q.

How does this work? I can't think of a way to compute mu(n) faster than:
* finding a small p for which p^2 | n, or
* finding that n is prime, or
* checking that for all p < (n)^(1/3), p^2 does not divide n
* factoring n, which can be faster than the third option for large n


Edit: I checked my copy of "Open problems in number theoretic complexity, II", which has O8: Is SQUAREFREES in P? Assuming that this is still open, any algorithm known would either be superpolynomial or of unproven complexity. But even an exponential-time improvement on the naive algorithm would be of interest.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
CRGreathouse
CRGreathouse is offline
#2
Sep22-08, 03:31 PM
Sci Advisor
HW Helper
P: 3,680
The interesting line, to me, is this:
If n has a small prime factor (less than or equal to 1223), this is very fast.

This seems a fairly strong claim. In particular, it would mean that the "very fast" algorithm could distinguish between n = 2pq and n = 2pq^2 for large p and q.

I saw a reference to this at http://www.marmet.org/louis/sqfgap/ :
A faster algorithm is used by "Mathematica" to determine if a number is square-free. The method is quite interesting (see: http://documents.wolfram.com/v5/Add-...Functions.html )
Hurkyl
Hurkyl is offline
#3
Sep22-08, 11:42 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
The implication cannot be true, because it would mean that if N doesn't have a small factor, that we could compute [itex]\mu(N) = -\mu(3N)[/itex], where the latter can be done rapidly.

CRGreathouse
CRGreathouse is offline
#4
Sep23-08, 12:11 AM
Sci Advisor
HW Helper
P: 3,680

Computing the Möbius function


Yeah, I figured as much, thanks.

So factoring n is pretty much the fastest way to find mu(n), right? Except in the special cases I outlined above?


Register to reply

Related Discussions
Computing the range for a rational function involving absolute value Precalculus Mathematics Homework 8
möbius mappings Calculus 7
computing distance as a function of time General Math 1
A very special Möbius Strip Differential Geometry 8
Möbius transformations. General Math 1