Register to reply

Computing the Möbius function

by CRGreathouse
Tags: computing, function, möbius
Share this thread:
CRGreathouse
#1
Sep17-08, 04:13 PM
Sci Advisor
HW Helper
P: 3,684
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
An interesting glimpse into how future state-of-the-art electronics might work
Tissue regeneration using anti-inflammatory nanomolecules
C2D2 fighting corrosion
CRGreathouse
#2
Sep22-08, 03:31 PM
Sci Advisor
HW Helper
P: 3,684
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
#3
Sep22-08, 11:42 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
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
#4
Sep23-08, 12:11 AM
Sci Advisor
HW Helper
P: 3,684
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