O Moebius fórmula inversão clássico foi introduzido na teoria de números durante a XIX th século por August Ferdinand Moebius . Posteriormente, foi generalizado para outras "fórmulas de inversão de Möbius".
A versão clássica declara que para todas as funções aritméticas f e g , temos
se e somente se f é a transformada de Möbius de g , ou seja ,
onde μ é a função de Möbius e as somas se relacionam a todos os divisores estritamente positivos d de n .
A equivalência permanece verdadeiro se as funções f e g (definido no conjunto de ℕ * inteiros estritamente positivos ) têm valores em um grupo abeliano (visto como ℤ - módulo ).
Colocamo-nos no anel comutativo F das funções aritméticas, definidas a seguir. O conjunto F de funções aritméticas é naturalmente fornecido com uma adição que o torna um grupo abeliano . Ele é fornecido com uma segunda lei interna , a convolução Dirichlet , associando-se com dois elementos de f e g de F a função f ✻ g definida por:
Esta lei em F é associativa , comutativa e distributiva em relação à adição, e existe um elemento neutro : a função observada aqui δ 1 e definida por δ 1 (1) = 1 e para qualquer inteiro n > 1, δ 1 ( n ) = 0.
O grupo de invertíveis ( F × , ✻) deste anel é o grupo abeliano formado por funções f tais que f (1) ≠ 0 (as funções multiplicativas formam um subgrupo ).
Ao observar 1 a função constante 1 ( n ) = 1, a fórmula de inversão é reescrita:
.Esta equivalência resulta da definição de μ como o inverso de 1 para a convolução ✻ :
,o que dá bem:
e
.Estes cálculos permanecem válidas para f e g com os valores de um grupo de abeliano ( L , +) porque o sub-anel de F constituído por os mapeamentos inteiros contém μ e 1 , e os mapeamentos de ℕ * em L formam um certo módulo neste anel, a lei externa sendo a convolução definida pelas mesmas fórmulas.
Uma abordagem combinatória torna possível generalizar o estudo acima. Seja A um conjunto parcialmente ordenado cuja relação de ordem é notada ≤. Definimos as strings por:
Deixe um e b ser dois elementos de um tal modo que uma ≤ b . Para qualquer número natural p , chamamos "cadeia de comprimento p unindo a a b ", qualquer sequência finita ( x 0 , x 1 , ..., x p ) tal que:
e denotamos por c p ( a , b ) o número dessas cadeias.
Supondo que a ordem em A é localmente finita (em) , ou seja, que existe apenas um número finito de elementos localizados entre a e b , Gian-Carlo Rota então constrói uma nova função de Möbius , que ele nota μ A , caracterizada por :
Deixe um e b ser dois elementos de A tal que a < b :
Ele generaliza a função clássica de Möbius μ :
Para A = ℕ *, ordenado por " a ≤ b quando a é um divisor de b ", temos
A função μ A satisfaz a seguinte fórmula de inversão, que generaliza a de μ:
De fato, o produto da convolução de Dirichlet generaliza, tornando possível associar a qualquer ordem localmente finita A sua álgebra de incidência (in) , e μ A é então interpretado como um inverso neste anel unitário . Em última análise, isso fornece uma prova muito curta - semelhante à fornecida acima para μ - da fórmula de inversão acima, mas requer que esta teoria seja desenvolvida primeiro, enquanto um cálculo direto é possível:
Demonstração diretaDe acordo com a caracterização de μ A , os termos da direita são todos zero, exceto se c for igual ab ; a é então também igual ab e μ A ( a , a ) é igual a 1, o que mostra o resultado.
Aplicando esta fórmula a outros conjuntos finitos localmente ordenados parcialmente que não os inteiros estritamente positivos ordenados por divisibilidade, obtemos outras fórmulas de inversão de Möbius, incluindo entre outros o princípio de inclusão-exclusão de Moivre .
Quando a ordem usada é a ordem usual em inteiros naturais diferentes de zero, obtemos a seguinte fórmula, útil em combinatória :
se F e G são duas funções definidas no intervalo [1, + ∞ [ de ℝ com valores complexos e se α e β são duas funções aritméticas inversas entre si para a convolução de Dirichlet (em particular se α = 1 e β = μ ), então
.Exemplos são dados no artigo Função multiplicativa .
O índice de Euler φ verifica :
.A fórmula de inversão, então, fornece:
.A fórmula de inversão de Möbius é válida para qualquer função f de N * em um grupo abeliano. Se este grupo for denotado por multiplicação, a fórmula se torna:
Ao tomar, como um grupo multiplicativo, que de zero não fracções racionais com racionais coeficientes e, como uma função de f , a que se associa com qualquer nero inteiro n > 0 o n ° CYCLOTOMIC polinomial Φ N , obtém-se, em virtude da igualdade
uma maneira de calcular o n º CYCLOTOMIC polinomial:
Essas duas equações especificam as do parágrafo anterior, que correspondem ao grau dos polinômios em jogo.
Alguns códigos corretivos , como códigos cíclicos, são construídos usando o anel de polinômios com coeficientes no corpo finito F q com elementos q e um polinômio irredutível e unitário de grau n , onde n é primo com q . Esta é uma das razões pelas quais estamos interessados no número m n ( q ) de polinômios unitários irredutíveis de grau n com coeficientes em F q . Esta questão é um exemplo de um problema de contagem envolvendo a função de Möbius.
Provamos algebricamente que
Por inversão de Möbius, deduzimos: