Fórmula de inversão de Möbius

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Relação entre pares de funções aritméticas

Em matemática, a clássica fórmula de inversão de Möbius é uma relação entre pares de funções aritméticas, cada uma definida a partir da outra por somas sobre divisores. Foi introduzido na teoria dos números em 1832 por August Ferdinand Möbius.

Uma grande generalização desta fórmula se aplica à soma sobre um conjunto arbitrário localmente finito parcialmente ordenado, com Möbius' fórmula clássica aplicada ao conjunto dos números naturais ordenados por divisibilidade: ver álgebra de incidência.

Declaração da fórmula

A versão clássica afirma que se $g$ e $f$ são funções aritméticas que satisfazem

{displaystyle g(n)=sum _{dmid n}f(d)quad {text{for every integer }}ngeq 1}

então

{displaystyle f(n)=sum _{dmid n}mu (d)gleft({frac {n}{d}}right)quad {text{for every integer }}ngeq 1}

Onde? $μ$ é a função Möbius e as somas se estendem sobre todos os divisores positivos $D$ de $n$ (indicado por ${displaystyle dmid n}$ nas fórmulas acima). Com efeito, o original $f (n)$ pode ser determinado dado $g (n)$ usando a fórmula de inversão. Dizem que as duas sequências são Möbius transforma um do outro.

A fórmula também está correta se $f$ e $g$ são funções dos inteiros positivos em algum grupo abeliano (visto como um módulo $Z$ ).

Na linguagem das convoluções de Dirichlet, a primeira fórmula pode ser escrita como

{displaystyle g={mathit {1}}*f}

onde $*$ denota a convolução de Dirichlet e $1$ é a função constante $1 (n) = 1$ . A segunda fórmula é então escrita como

f=mu * g.

Muitos exemplos específicos são dados no artigo sobre funções multiplicativas.

O teorema segue porque $*$ é (comutativo e) associativo, e $1 * μ = ε$ , onde $ε$ é a função de identidade para a convolução de Dirichlet, assumindo os valores $ε (1) = 1$ , $ε (n) = 0$ para todos os $n > 1$ . Por isso

{displaystyle mu *g=mu *({mathit {1}}*f)=(mu *{mathit {1}})*f=varepsilon *f=f}

Existe uma versão de produto da fórmula de inversão de Möbius baseada em soma declarada acima:

{displaystyle g(n)=prod _{d|n}f(d)iff f(n)=prod _{d|n}gleft({frac {n}{d}}right)^{mu (d)},forall ngeq 1.}

Relações em série

Deixe

a_n=sum_{dmid n} b_d

para que

b_n=sum_{dmid n} muleft(frac{n}{d}right)a_d

é sua transformação. As transformadas são relacionadas por meio de séries: a série de Lambert

{displaystyle sum _{n=1}^{infty }a_{n}x^{n}=sum _{n=1}^{infty }b_{n}{frac {x^{n}}{1-x^{n}}}}

e a série de Dirichlet:

{displaystyle sum _{n=1}^{infty }{frac {a_{n}}{n^{s}}}=zeta (s)sum _{n=1}^{infty }{frac {b_{n}}{n^{s}}}}

onde $ζ (s)$ é a função zeta de Riemann.

Transformações repetidas

Dada uma função aritmética, pode-se gerar uma sequência bi-infinita de outras funções aritméticas aplicando repetidamente o primeiro somatório.

Por exemplo, se alguém começar com a função totiente de Euler $φ$ e aplicar repetidamente o processo de transformação, um obtém:

$φ$ a função totient
$φ * 1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Eu...$ , onde $Eu... (n) = n$ é a função de identidade
$Eu... * 1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = σ 1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = σ$ , a função divisor

Se a função inicial for a própria função Möbius, a lista de funções é:

$μ$ , a função Möbius
$μ * 1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ε$ Onde? $1end{cases}}}" display="block" xmlns="http://www.w3.org/1998/Math/MathML">ε ε (n)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(1,sen= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =10,sen>1{displaystyle varepsilon (n)={begin{cases}1,&{text{if }}n=1\0,&{text{if }}n>1end{cases}}}1end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-display" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98ad09dc0f65cc3578fc29154bae9abc1ad72f43" style="vertical-align: -2.505ex; width:21.607ex; height:6.176ex;"/>$ é a função da unidade
$ε * 1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1$ , a função constante
$1 * 1 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = σ 0 = d = d = ?$ , onde $D = ?$ é o número de divisores de $n$ , (ver função divisor).

Ambas as listas de funções se estendem infinitamente em ambas as direções. A fórmula de inversão de Möbius permite que essas listas sejam percorridas para trás.

Como exemplo, a sequência que começa com $φ$ é:

<math alttext="{displaystyle f_{n}={begin{cases}underbrace {mu *ldots *mu } _{-n{text{ factors}}}*varphi &{text{if }}n0end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">fn= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(μ μ ∗ ∗ ...... ∗ ∗ μ μ ? ? - Sim. - Sim. nfatores∗ ∗ φ φ sen<0φ φ sen= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0φ φ ∗ ∗ 1∗ ∗ ...... ∗ ∗ 1? ? nfatoressen>0Não. f_{n}={begin{cases}underbrace {mu *ldots *mu } _{-n{text{ factors}}}*varphi &{text{if }}n0end{cases}}}<img alt="{displaystyle f_{n}={begin{cases}underbrace {mu *ldots *mu } _{-n{text{ factors}}}*varphi &{text{if }}n0end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18220333c3e2775d67fff05a360acda8f57659f2" style="vertical-align: -8.838ex; width:31.822ex; height:18.843ex;"/>

As sequências geradas talvez possam ser mais facilmente compreendidas considerando a série de Dirichlet correspondente: cada aplicação repetida da transformada corresponde à multiplicação pela função zeta de Riemann.

Generalizações

Uma fórmula de inversão relacionada mais útil em combinatória é a seguinte: suponha $F (x)$ e $G (x)$ são funções de valor complexo definidas no intervalo $[1, \infty)$ tal que

{displaystyle G(x)=sum _{1leq nleq x}Fleft({frac {x}{n}}right)quad {mbox{ for all }}xgeq 1}

então

{displaystyle F(x)=sum _{1leq nleq x}mu (n)Gleft({frac {x}{n}}right)quad {mbox{ for all }}xgeq 1.}

Aqui as somas abrangem todos os inteiros positivos $n$ que são menores ou iguais a $x$ .

Este, por sua vez, é um caso especial de uma forma mais geral. Se $α (n)$ é uma função aritmética que possui uma inversa de Dirichlet $α -1 (n)$ , então se alguém define

{displaystyle G(x)=sum _{1leq nleq x}alpha (n)Fleft({frac {x}{n}}right)quad {mbox{ for all }}xgeq 1}

então

{displaystyle F(x)=sum _{1leq nleq x}alpha ^{-1}(n)Gleft({frac {x}{n}}right)quad {mbox{ for all }}xgeq 1.}

A fórmula anterior surge no caso especial da função constante $α (n) = 1$ , cujo Dirichlet o inverso é $α -1 (n) = μ (n)$ .

Uma aplicação particular da primeira dessas extensões surge se tivermos funções (com valores complexos) $f (n)$ e $g (n)$ definidos nos inteiros positivos, com

g(n) = sum_{1 le m le n}fleft(leftlfloor frac{n}{m}rightrfloorright)quadmbox{ for all } nge 1.

Definindo $F (x) = f (⌊ x ⌋)$ e $G (x) = g (⌊ x ⌋)$ , deduzimos que

f(n) = sum_{1 le m le n}mu(m)gleft(leftlfloor frac{n}{m}rightrfloorright)quadmbox{ for all } nge 1.

Um exemplo simples do uso desta fórmula é contar o número de frações reduzidas $0 < a / b < 1$ , onde $a$ e $b$ são coprimos e $b \leq n$ . Se deixarmos $f (n)$ ser este número, então $g (n)$ é o número total de frações $0 < a / b < 1$ com $b \leq n$ , onde $a$ e $b$ não são necessariamente primos. (Isso ocorre porque cada fração $a / b$ com $gcd(a, b) = d$ e $b \leq n$ pode ser reduzido à fração $a / d / b / d$ com $b / d \leq n / d$ e vice-versa.) Aqui é fácil determinar $g (n) = n (n - 1) / 2$ , mas $f (n)$ é mais difícil de calcular.

Outra fórmula de inversão é (onde assumimos que as séries envolvidas são absolutamente convergentes):

g(x) = sum_{m=1}^infty frac{f(mx)}{m^s}quadmbox{ for all } xge 1quadLongleftrightarrowquad f(x) = sum_{m=1}^infty mu(m)frac{g(mx)}{m^s}quadmbox{ for all } xge 1.

Como acima, isso se generaliza para o caso em que $α (n)$ é uma função aritmética que possui uma inversa de Dirichlet $α -1 (n)$ :

g(x) = sum_{m=1}^infty alpha(m)frac{f(mx)}{m^s}quadmbox{ for all } xge 1quadLongleftrightarrowquad f(x) = sum_{m=1}^infty alpha^{-1}(m)frac{g(mx)}{m^s}quadmbox{ for all } xge 1.

Por exemplo, há uma prova bem conhecida relacionando a função zeta de Riemann à função zeta principal que usa a forma baseada em série de Inversão de Möbius na equação anterior quando $s=1$ . Nomeadamente, pela representação do produto Euler de $zeta (s)$ para $1}" xmlns="http://www.w3.org/1998/Math/MathML">R R (S)>1(s)>1} 1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9ea5968732ea35f67b36093364400e0fd8ca23bf" style="vertical-align: -0.838ex; width:9.085ex; height:2.843ex;"/>$

1.}" xmlns="http://www.w3.org/1998/Math/MathML">log⁡ ⁡ ζ ζ (S)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. Gerenciamento Gerenciamento ppREu...melog⁡ ⁡ (1- Sim. - Sim. 1pS)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Gerenciamento Gerenciamento k≥ ≥ 1P(kS)k⟺ ⟺ P(S)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Gerenciamento Gerenciamento k≥ ≥ 1μ μ (k)klog⁡ ⁡ ζ ζ (kS),R R (S)>1.{displaystyle log zeta (s)=-sum _{pmathrm { prime} }log left(1-{frac {1}{p^{s}}}right)=sum _{kgeq 1}{frac {P(ks)}{k}}iff P(s)=sum _{kgeq 1}{frac {mu (k)}{k}}log zeta (ks),Re (s)>1.}1.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/193b5a8a8dcc89a51e5cfec797adca13384af0a9" style="vertical-align: -3.338ex; width:88.854ex; height:7.176ex;"/>

Essas identidades para formas alternativas de inversão de Möbius são encontradas em. Uma teoria mais geral das fórmulas de inversão de Möbius parcialmente citadas na próxima seção sobre álgebras de incidência é construída por Rota em.

Notação multiplicativa

Como a inversão de Möbius se aplica a qualquer grupo abeliano, não faz diferença se a operação de grupo é escrita como adição ou como multiplicação. Isso dá origem à seguinte variante de notação da fórmula de inversão:

{displaystyle {mbox{if }}F(n)=prod _{d|n}f(d),{mbox{ then }}f(n)=prod _{d|n}Fleft({frac {n}{d}}right)^{mu (d)}.}

Provas de generalizações

A primeira generalização pode ser provada da seguinte forma. Usamos a convenção de Iverson de que [condição] é a função indicadora da condição, sendo 1 se a condição for verdadeira e 0 se for falsa. Usamos o resultado que

{displaystyle sum _{d|n}mu (d)=varepsilon (n),}

Isso é, ${displaystyle 1*mu =varepsilon }$ , onde $varepsilon$ é a função da unidade.

Temos o seguinte:

{displaystyle {begin{aligned}sum _{1leq nleq x}mu (n)gleft({frac {x}{n}}right)&=sum _{1leq nleq x}mu (n)sum _{1leq mleq {frac {x}{n}}}fleft({frac {x}{mn}}right)\&=sum _{1leq nleq x}mu (n)sum _{1leq mleq {frac {x}{n}}}sum _{1leq rleq x}[r=mn]fleft({frac {x}{r}}right)\&=sum _{1leq rleq x}fleft({frac {x}{r}}right)sum _{1leq nleq x}mu (n)sum _{1leq mleq {frac {x}{n}}}left[m={frac {r}{n}}right]qquad {text{rearranging the summation order}}\&=sum _{1leq rleq x}fleft({frac {x}{r}}right)sum _{n|r}mu (n)\&=sum _{1leq rleq x}fleft({frac {x}{r}}right)varepsilon (r)\&=f(x)qquad {text{since }}varepsilon (r)=0{text{ except when }}r=1end{aligned}}}

A prova no caso mais geral em que $α (n)$ substitui 1 é essencialmente idêntica, assim como o segunda generalização.

Em poses

Para uma poset $P$ , um conjunto dotado de uma relação de ordem parcial $leq$ , definir a função Möbius $mu$ de $P$ recursivamente por

<math alttext="{displaystyle mu (s,s)=1{text{ for }}sin P,qquad mu (s,u)=-sum _{sleq t<u}mu (s,t),quad {text{ for }}sμ μ (S,S)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1paraS∈ ∈ P,μ μ (S,u)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. Gerenciamento Gerenciamento S≤ ≤ )<uμ μ (S,)),paraS<uemP.{displaystyle mu (s,s)=1{text{ for }}sin P,qquad mu (s,u)=-sum _{sleq t<u}mu (s,t),quad {text{ for }}s<u{text{ in }}P.}<img alt="{displaystyle mu (s,s)=1{text{ for }}sin P,qquad mu (s,u)=-sum _{sleq t<u}mu (s,t),quad {text{ for }}s

(Aqui se assume que as somas são finitas.) Então, ${displaystyle f,g:Pto K}$ , onde $KK$ é um anel comutativo, temos

{displaystyle g(t)=sum _{sleq t}f(s)qquad {text{ for all }}tin P}

se e somente se

{displaystyle f(t)=sum _{sleq t}g(s)mu (s,t)qquad {text{ for all }}tin P.}

(Consulte Enumerative Combinatorics de Stanley, Vol 1, Seção 3.7.)

Contribuições de Weisner, Hall e Rota

A declaração da fórmula geral de inversão Möbius [para conjuntos parcialmente ordenados] foi dada pela primeira vez independentemente por Weisner (1935) e Philip Hall (1936); ambos os autores foram motivados por problemas de teoria do grupo. Nenhum autor parece estar ciente das implicações combinatórias de seu trabalho e nem desenvolveu a teoria das funções de Möbius. Em um artigo fundamental sobre funções de Möbius, a Rota mostrou a importância desta teoria em matemática combinatória e deu um tratamento profundo disso. Ele observou a relação entre temas como inclusão-exclusão, número clássico teorético Möbius inversão, colorir problemas e fluxos em redes. Desde então, sob a forte influência da Rota, a teoria da inversão de Möbius e tópicos relacionados tornou-se uma área ativa da combinatória.

Contenido relacionado

Más resultados...