A função Mobius é definida como μ ( 1 ) = 1 , μ ( n ) = 0 se n tiver um fator primordial ao quadrado e μ ( p 1 … p k ) = ( - 1 ) k se todos os primos p 1 , … , p k são diferentes. É possível calcular μ ( sem calcular a fatoração primária de n?
comp-number-theory
Craig Feinstein
fonte
fonte
Respostas:
Uma não resposta à sua pergunta é que o SQUARE-FREE (é um número livre de quadrados) não é conhecido por estar em P, e calcular a função Möbius resolveria esse problema (já que um número livre de quadrados possui )μ(n)≠0
fonte
Para outra não resposta, você pode estar interessado na conjectura de Sarnak (consulte, por exemplo , http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/ , http: //rjlipton.wordpress .com / 2011/02/23 / função da profundidade da mobius / , /mathpro/57543/walsh-fourier-transform-of-the-mobius-function ), que basicamente afirma que a função Möbius não está correlacionada com nenhuma função booleana "simples". Não é irracional esperar que isso ocorra quando "simples" é interpretado como tempo polinomial. O que sabemos até agora é que a conjectura vale para -Funções (comprovadas porBen Verde), e todas as funções monótonas (comprovadas porJean Bourgain).A C0 0
fonte
Uma das fórmulas recursivas que relacionam valores da função mobious é∑m≤n⌊nm⌋μ(m)=1.
Mas, para encontrar o
μ(n) , precisamos conhecer os valores de mobious param<n . Portanto
μ(n)=1−∑m<n⌊nm⌋μ(m).
Aqui estamos dividindon pelos números inteiros positivos menoresm<n , não precisamos saber se são fatores den quandom tem um fator quadrado! (μ(m)=0 ), mas ainda temos que conhecer os fatores dem para concluir isso !! Portanto, temos:
μ(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 obter a prova da fórmula.
fonte
Aqui está uma analogia: para saber se há um número ímpar ou par de jujubas em uma jarra, é preciso contar as jujubas. É por isso que você deve calcular a fatoração primária de um número para calcular sua função Mobius, quando não é divisível por um quadrado. Mas, para saber que há mais de uma jujuba em uma jarra, não é necessário examinar nenhuma das jujubas na jarra. Pode-se apenas agitar a jarra e ouvir que há mais de uma jujuba. É por isso que você não precisa fatorar um número para saber que ele é composto. Algoritmos como o pequeno teorema de Fermat permitem "aumentar o número" para saber que ele é composto.
Quandon divisível por um quadrado, você não precisa calcular a fatoração primária de n . Mas você precisa encontrar um fator não trivial den : E se n é quadrado, para determinar se é quadrado, você deve obter a raiz quadrada, na qual você encontra um fator não rival de n . A fortiori, sen não é um quadrado, mas ainda não é um quadrado, para determinar se μ ( n ) = 0 , é necessário encontrar um fator não trivial de n .
fonte