14 votos

Deducir la fórmula para la función de Möbius?

Hay una rica y hermosa teoría en la combinatoria en la que se aborda el Möbius funciones de posets y llega a la "Clásica" de la fórmula de la función de Möbius. Vamos a olvidar todo acerca de él, ya que estoy con la esperanza de encontrar una solución primaria.

Quiero llegar a la fórmula de la clásica función de Möbius $\mu$ (que se define como $1$ en $1$, $0$ no cuadrados de los números libres, y como $(-1)^k$ para la plaza libre de los números con exactamente $k$ primer divisores) a partir de la siguiente fórmula:

$$\sum_{d|n}\mu(d)=\cases{1, & n=1;\\ 0, & n>1.}$$

Así que vamos a suponer que me ha dado esta fórmula y nada más (sobre todo no es un pre-conocimiento de la definición de $\mu$) - hay una manera simple de derivar la definición estándar, sin necesidad de utilizar más profundo de la teoría o "insight"?

5voto

GmonC Puntos 114

Aunque la pregunta exige olvidarse de posets, lo voy a resumir el enfoque general de Möbius inversión aquí, ya que no es menos elemental de un "directo", no se basa en la penetración profunda, y de hecho es bastante indoloro.

Supongamos $(P,\preceq))$ son un conjunto $P$ y un orden parcial $\preceq$ $P$ (por ejemplo,$P=\mathbb N_{\geq1}$, e $x\preceq y$$x\mid y$), y supongamos que para cada una de las $y\in P$ hay sólo un número finito $x\in P$$x\preceq y$, por lo que nuestro sumatorias por debajo de sentido. Queremos una función $\mu(x,y)$ $P^2$ con la propiedad $$ \sum_{y\preceq z}\mu(x,y)=\delta_{x,z}. $$ para todos los $x,z\in P$. Esta ecuación define a $\mu(x,z)$ una vez que todos los otros $\mu(x,y)$ que se producen son conocidos, por lo que los valores de $\mu(x,y)$ está definida únicamente por esta ecuación, como puede ser fija $x$ por la fuerte inducción en $y$ a lo largo de los pedidos parciales $\preceq$ (o a lo largo de cualquier orden total de la ampliación, si se prefiere). Esta muestra en particular que $\mu(x,y)=0$ siempre $x\not\preceq y$, e $\mu(x,x)=1$ todos los $x$.

En nuestro ejemplo vamos a obtener $\mu(x,y)=\mu(y/x)$ $\mu$ ahora denotando la clásica (la aritmética) función de Möbius. De hecho, para $x=1$ la ecuación se convierte en la habitual $\sum_{y\mid z}\mu(1,y)=\delta_{1,z}$, y para $x>1$ uno puede comprobar fácilmente que $\mu(x,y)=\mu(1,y/x)$ para todos los múltiplos $y$$x$. Es algo desquiciando que la configuración general requiere de una función de dos argumentos, en lugar de una, pero la configuración no proporciona ningún medio para expresar algo como el cociente de la operación utilizado para reducir a un único argumento; sin embargo, en situaciones concretas, a menudo hay una similar función simple de $x$ $y$ en términos de que $\mu(x,y)$ está definido. Observe que la ecuación está pidiendo $\mu(x,y)$ a los coeficientes de la matriz inversa de la matriz $M$, con filas y columnas indexadas por los elementos de a $P$, dado por $M_{x,y}=1$ si $x\preceq y$ $M_{x,y}=0$ lo contrario. Desde la izquierda inversa es también derecho inversa, en este punto de vista nos permite replantear la ecuación anterior como $$ \sum_{x\preceq y\preceq z}\mu(y,z)=\delta_{x,z}. $$ Pero basta de teoría general.

Si $\preceq$ es en realidad un total de pedidos en $P$, lo que significa que (dada la finitud de la condición) que $P$ es isomorfo a un segmento inicial de $\mathbb N$ (possiblement todos los de $\mathbb N$), entonces es fácil ver que uno ha $\mu(x,y)=\epsilon(y-x)$ donde $\epsilon:\mathbb Z\to\{-1,0,1\}$ satisface $\epsilon(i)=(-1)^i$ si $i\in\{0,1\}$ $\epsilon(i)=0$ lo contrario. Esta casi trivial cálculo permiten deducir importantes Möbius funciones, incluyendo la clásica función de Möbius, con el siguiente

Teorema. Si $(P_i,\preceq_i)$ son apropiados posets para $i\in I$, e $(P,\preceq)$ es el producto poset (restringido si $I$ es infinito), entonces la función de Möbius para $P$ es el producto de Möbius funciones para el posets $P_i$: uno ha $\mu((x_i)_{i\in I},(y_i)_{i\in I})=\prod_{i\in I}\mu_i(x_i,y_i)$.

Aquí un producto poset es el producto Cartesiano $\prod_{i\in I}P_i$ con un componente sabio orden parcial: $(x_i)_{i\in I}\leq(y_i)_{i\in I}$ si y sólo si $x_i\leq y_i$ $P_i$ todos los $i\in I$. También "restringido" significa restricción para el subconjunto del producto Cartesiano de los $(x_i)_{i\in I}$ tal que $x_i$ es el mínimo elemento de $P_i$ para todos, pero finitiely muchos índices $i$; esta restricción es necesaria para asegurarse de que hay sólo un número finito de elementos por debajo de cualquier elemento de $P$, por lo que su Möbius función está bien definida. El ejemplo que nos interesará es con $I$ el conjunto $\mathrm{Pr}$ de los números primos, y cada una de las $(P_i,\preceq_i)$ una copia de $(\mathbb N,\leq)$; entonces los elementos de a $P$ son colecciones $(m_p)_{p\in\mathrm{Pr}}$ $m_p\in\mathbb N$ $m_p=0$ para todos, pero finitiely muchos $p$. Un elemento puede estar asociado al producto $\prod_{p\in\mathrm{Pr}}p^{m_p}$, que es un bijection de $P$ para el conjunto de $\mathbb N_{\geq1}$, en virtud de la cual bijection el orden parcial $\preceq$ $P$ corresponde a la relación de divisibilidad en $\mathbb N_{\geq1}$. Así vemos que el teorema se describen, en particular, la clásica función de Möbius. De hecho, se da $\mu(x,y)=\prod_{p\in\mathrm{Pr}}\epsilon(m_p(y)-m_p(x))$ donde $m_p(x)$ denota la multiplicidad de la prime $p$ en la factorización de $x$; el producto es igual a $\prod_{p\in\mathrm{Pr}}\epsilon(m_p(y/x))$ siempre $x\mid y$, que es la definición habitual de $\mu(y/x)$.

Prueba. Esto es simplemente formal de la verificación de que la propuesta de Möbius función de $P$ satifies la necesaria ecuación. Deje $x=(x_i)_{i\in I}$ $z=(z_i)_{i\in I}$ ser elementos de $P$, y deje $J=\{i_1,\ldots,i_n\}$ ser un conjunto finito que contiene todos los índices para que $z_i$ no es mínima. Entonces $$ \begin{align} \sum_{y\preceq z}\mu(x,y) &=\sum_{y_{i_1}\preceq z_{i_1}}\cdots\sum_{y_{i_n}\preceq z_{i_n}} \mu_{i_1}(x_{i_1},y_{i_1})\cdots\mu_{i_n}(x_{i_n},y_{i_n}) \\ & =\prod_{j\in J}\,\sum_{y_j\preceq z_j}\mu_j(x_j,y_j) =\prod_{j\in J}\delta_{x_j,z_j} =\delta_{x,z}.\quad\mbox{QED}\\ \end{align} $$

3voto

user21783 Puntos 11

Establecimiento $n=1$ deducimos $\mu(1)=1$ podríamos continuar con n=p prime para obtener $\mu(1)+\mu(p)=0 \implies \mu(p)=-1$, pruebe el producto de dos números primos para obtener $\mu(p\cdot q)=1$ y así sucesivamente...

Podríamos también definir la aritmética de la función u : u(k)=1 para todo k y reescribir su definición como $\mu * u = I$ (por supuesto esto es sólo un acceso directo para $\sum_{d|n}\mu(d) u(\frac{n}{d})=I(n)$ $I$ la función de n se define en la parte derecha de la ecuación).
Este e $\mu(1)=1$ es suficiente para demostrar la Möbius de la inversión de la fórmula (detalles en el Apostol de la excelente introducción a la A. N. T. página 30 de 32 : las pruebas no sólo requieren de su definición). Usted podría probar que u y yo estamos multiplicativo ($f(m n)=f(m)f(n)$ si $\gcd(m,n)=1$) por lo que el $\mu$ también se multiplicativo (usar/probar el Teorema 2.16 página 36). Por supuesto, esto es sólo el borrador de un plan de acción y voy a dejar a usted o a otros concretar! :-)

2voto

Adriano Varoli Piazza Puntos 3008

Sí, lo hay. Se demuestra de la misma manera de demostrar la Möbius de la inversión de la fórmula:

Ir directamente a partir de la fórmula que le dan, es claro que $$ \mu(1) = 1, \mu(p) = -1 \text{ for $p$ a prime}. $$ En general, para la plaza libre de números, podemos mostrar la formula elegida por el principio de inclusión-exclusión. Por ejemplo, para $n = pq, p, q$ primos, tenemos $$ \mu(pq) = \sum_{d|pq} \mu(d) - \sum_{d|p} \mu(d) - \sum_{d|q} \mu(d) + \sum_{d|1} \mu(d) = 1 $$ y para tres de los números primos, $$ \mu(pqr) = \left (\sum_{d|pqr} - \sum_{d|pq} - \sum_{d|qr} - \sum_{d|pr} + \sum_{d|p} + \sum_{d|q} + \sum_{d|r} - \sum_{d|1} \right )\mu(d) = -1. $$ Ahora el PASTEL de obras para el caso general, así. Si $n = p_1^{e_1} \cdots p_s^{e_s}$, vamos a $m = p_1^{e_1 - 1 } \cdots p_s^{e_s -1}$, es decir, $n$ dividido por la plaza de la parte libre. Entonces tenemos que $$\small \mu(n) = \sum_{d|n} \mu(d) - \sum_{p_1|n} \left( \sum_{d|n/p_1} \mu(d) \right ) + \sum_{p_1, p_2 |n, p_1 \neq p_2} \left ( \sum_{d|n/(p_1 p_2)} \mu(d) \right ) -\cdots + (-1)^s \sum_{d|m} \mu(d) = 0 $$ si $m \neq 1$, como se desee.

2voto

Matt Dawdy Puntos 5479

He aquí otra solución con el uso de Dirichlet de la serie. Considerar el anillo de secuencias de $a_n, n \in \mathbb{N}$ bajo de Dirichlet de convolución $$a_n * b_n = \sum_{d | n} a_d b_{n/d}.$$

Este anillo tiene la identidad de la secuencia de $a_1 = 1, a_n = 0, n \ge 2$. Se nos pide hallar la inversa de la secuencia de $a_n = 1$ en este anillo. Una observación fundamental es que el mapa $$a_n \mapsto \sum_{n \in \mathbb{N}} \frac{a_n}{n^s}$$

es un anillo homomorphism (donde el producto en poder de la serie es el producto estándar). La secuencia de $a_n = 1$ es la de Riemann zeta función $$\zeta(s) = \sum_{n \in \mathbb{N}} \frac{1}{n^s}.$$

Otro básico de la observación, la traducción de la serie de Dirichlet del producto poset de observación en Marc van Leeuwen la respuesta, es que la función zeta tiene un producto de Euler $$\zeta(s) = \prod_{p \text{ prime}} \left( \frac{1}{1 - p^{-s}} \right)$$

y por lo tanto su inversa tiene Euler producto $$\zeta(s)^{-1} = \sum_{n \in \mathbb{N}} \frac{\mu(n)}{n^s} = \prod_{p \text{ prime}} \left( 1 - \frac{1}{p^s} \right).$$

La conclusión se deduce por la expansión de los RHS.

1voto

Joshdan Puntos 31

De hecho, se puede derivar.

Así, desde el primer caso de la fórmula, vemos que

$\mu(1)=1$.

Esto prueba la primera condición de la función de Möbius. Sea p un primo.

$\sum_{d|p}\mu(d)=0$ a partir del 2 de caso de la fórmula.

Por lo tanto, $\mu(1)+\mu(p)=0$. es decir, $ 1+ \mu(p)=0$ por lo tanto $\mu(p)=-1$ para cualquier prime.

Además, $\sum_{d|p^2}\mu(d)=0$ $\mu(1)+\mu(p)+\mu(p^2)=0$ por lo tanto $1-1+\mu(p^2)=0$$\mu(p^2)=0$.

Para $k>2$, una simple inducción con $k=3$ como caso base será suficiente.

Considere la posibilidad de $n={p^k}{q^l}$$k,l>2$.

$\sum_{d|{p^k}{q^l}}\mu(d)=\sum_{d|{p^k}}\mu(d)+\sum_{d|{q^l}}\mu(d)+\mu({p^k}{q^l})=0,$

Por lo tanto $\mu({p^k}{q^l})=0$. Una simple inducción será suficiente para demostrar la cosa para el producto de $k$ primer poderes. Por lo tanto, la función de Möbius es cero para cualquier número divisible por el cuadrado. Esto demuestra la segunda condición de la función de Möbius.

Ahora, considere la posibilidad de dos números primos $p$$q$.

$\sum_{d|pq}\mu(d)=0$, lo $\mu(1)+\mu(p)+\mu(q)+\mu(pq)=0$ es decir $1-1-1+\mu(pq)=0$; por lo tanto,

$\mu(pq)=1$.

Por lo tanto, para que un producto de dos primos $p$$q$,$\mu(pq)=(-1)^2$.

Además, para el producto de la $k$ primos, tenemos

$\sum_{d|{\prod_{i=1}^k p_i}}\mu(d)=\sum_{i=1}^k \binom{k}{i}\mu(p_1p_2\cdots p_i)=0=(1-1)^k=\sum_{i=1}^k \binom{k}{i}{(-1)^i}$.

Por lo tanto, obtenemos $\mu(p_1p_2\cdots p_k)=(-1)^k$. Esto demuestra la tercera condición para la función de Möbius, y hemos terminado.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X