La función Mobius se define como , si tiene un factor primo cuadrado, y si todos los primos son diferentes. ¿Es posible calcular sin calcular la factorización prima de ?
comp-number-theory
Craig Feinstein
fuente
fuente
Respuestas:
Una no respuesta a su pregunta es que SQUARE-FREE (es un número libre de cuadrados) en sí mismo no se sabe que está en P, y calcular la función de Möbius resolvería este problema (ya que un número libre de cuadrados tiene )μ(n)≠0
fuente
Para otra no respuesta, puede estar interesado en la conjetura de Sarnak (ver, por ejemplo , http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/ , http: //rjlipton.wordpress .com / 2011/02/23 / the-depth-of-the-mobius-function / , /mathpro/57543/walsh-fourier-transform-of-the-mobius-function ), que básicamente establece que la función de Möbius no está correlacionada con ninguna función booleana "simple". No es irracional esperar que se cumpla cuando "simple" se interpreta como tiempo polinómico. Lo que sabemos hasta ahora es que la conjetura es válida para funciones 0 (probadas porBen Green) y todas las funciones monótonas (probadas porJean Bourgain).AC0
fuente
Una de las fórmulas recursivas que relacionan los valores de la función mobious es∑m≤n⌊nm⌋μ(m)=1.
Pero para encontrar el
μ(n) necesitamos conocer los valores mobious param<n . Por lo tanto
μ(n)=1−∑m<n⌊nm⌋μ(m).
Aquí estamos dividiendon entre los enteros positivos más pequeñosm<n , ¡no tenemos que saber si son factores den cuandom tiene un factor cuadrado! (μ(m)=0 ), ¡¡¡Pero aún tenemos que conocer los factores dem para concluir esto !! Por lo tanto tenemos:
μ(n)=+−1−∑a1<n⌊na1⌋∑a1<n⌊na1⌋∑a2<a1⌊a1a2⌋∑a1<n⌊na1⌋∑a2<a1⌊a1a2⌋∑a3<a2⌊a2a3⌋+⋯
Consulte este documento:https://projecteuclid.org/euclid.mjms/1513306829para obtener la prueba de la fórmula.
fuente
Dejarn = p1... pk , dónde pagj son primos distintos. Luego
Here's an analogy: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.
Whenn is divisible by a square, you don't have to compute the prime factorization of n . But you do have to find a nontrivial factor of n : If n is square, in order to determine that it is square, you have to take its square root, in which you find a nontirival factor of n . A fortiori, if n is not a square but is still not squarefree, in order to determine that μ(n)=0 , it is necessary to find a nontrivial factor of n .
fuente