La prueba de $\sum_{d|n} {\tau}^3(d)=\left(\sum_{d|n}{\tau}(d)\right)^2$ (no estándar de prueba)

Question

Estoy tratando de demostrar que

$\sum_{d|n} {\tau}^3(d)=\left(\sum_{d|n}{\tau}(d)\right)^2$

sin necesidad de utilizar el hecho de que $\tau$ es multiplicativo y productos/sumas de multiplicativos son funciones son también multiplicativo (aquí usted puede encontrar varios argumentos que muestran este resultado con el uso de tales propiedades).

Mi planteamiento era el siguiente:

LHS cuenta la cardinalidad de los siguientes:

$$\bigcup_{d| n}\big\{(x,y,z,d)\ /\ x,y,z|d \big\} $$

y RHS considera que este es uno

$$\big\{(x,d,y,e)\ / \ x|d; \ y|e; \ d,e|n\big\}$$

Traté de establecer una explícita bijection entre los conjuntos, pero ya he pasado suficiente tiempo y mis mayores esfuerzos, unsuccesful. Cualquier idea o sugerencia que me puedan dar?

Gracias de antemano!

Answer 1

Deje $n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$ ser una factorización prima de $n$. Cada divisor $d=p_1^{l_1}p_2^{l_2}\cdots p_m^{l_m}$ $n$ está asociado con el vector $\left(l_1,l_2,\ldots,l_m\right) \in \left[k_1\right]\times \left[k_2\right]\times \ldots\times \left[k_m\right]=:S$ donde $[t]:=\{0,1,2,\ldots,t\}$ para todos los enteros $t\geq0$. Parcialmente orden de los elementos de $S$ con el orden natural de las $\mathbb{Z}$. En otras palabras, este orden está dado por $\left(l_1,l_2,\ldots,l_m\right)\preceq \left(r_1,r_2,\ldots,r_m\right)$ fib $l_i\leq r_i$ todos los $i=1,2,\ldots,m$. Tenga en cuenta que $S$ es una celosía, y escribiremos $\vee$ para la combinación en $S$. Que es, $$\left(l_1,l_2,\ldots,l_m\right)\vee\left(r_1,r_2,\ldots,r_m\right)=\big(\max\left\{l_1,r_1\right\},\max\left\{l_2,r_2\right\},\ldots,\max\left\{l_m,r_m\right\}\big)\,.$$ (If $d$ and $e$ are divisors of $n$ associated to $$ and $b$ in $S$, respectively, then $\text{lcm}\left(d,e\ \ derecho)$ is the divisor of $n$ associated to $\vee b\in S$.)

Definir $$T:=\left\{(a,b)\in S\times S\,\big|\,a\preceq b\right\}\,.$$ Claramente, $$|T|=\sum_{b\in S}\,\Big|\big\{a\in S\,\big|\,a\preceq b\big\}\Big|=\sum_{d\mid n}\,\tau(d)\,.$$ Queremos contar el número de elementos de a $T\times T$ en dos maneras. La primera es la manera trivial a contar: $$|T\times T|=|T|\cdot |T|=\left(\sum_{d\mid n}\,\tau(d)\right)^2\,.$$ La segunda manera es la siguiente. Para una fija $b\in S$, vamos a $N_b$ el número de $\big((u,v),(x,y)\big)\in T\times T$ tal que $v\vee y=b$. Escribir $u_j$, $v_j$, $x_j$, $y_j$, y $b_j$ $j$- th componentes de $u$, $v$, $x$, $y$, y $b$, respectivamente. Para$j=1,2,\ldots,m$,$\max\left\{v_j,y_j\right\}=b_j$. Hay $\left(1+v_j\right)\left(1+y_j\right)$ posibles pares de $\left(u_j,x_j\right)$ para un determinado par de $\left(v_j,y_j\right)$. Es decir, $$ \begin{align} N_b&=\prod_{j=1}^m\,\left(\sum_{v_j=0}^{b_j-1}\,\left(1+v_j\right)\left(1+b_j\right)+\sum_{y_j=0}^{b_j-1}\,\left(1+b_j\right)\left(1+y_j\right)+\left(1+b_j\right)\left(1+b_j\right)\right) \\ &=\prod_{j=1}^m\,\left(1+b_j\right)\left(2\sum_{r=0}^{b_j-1}\,\left(1+r\right)+\left(1+b_j\right)\right) \\ &=\prod_{j=1}^m\,\left(1+b_j\right)\Big(b_j\left(1+b_j\right)+\left(1+b_j\right)\Big)=\prod_{j=1}^m\,\left(1+b_j\right)^3=\big(\tau(d)\big)^3\,, \end{align}$$ si $d$ es el divisor de $n$ asociado a $b$. Por lo tanto, $$|T\times T|=\sum_{b\in S}\,N_b=\sum_{d\mid n}\,\big(\tau(d)\big)^3\,.$$

Answer 2

Edit: el siguiente es incorrecta, porque Yoneda el lema no puede ser aplicado a los hom functors restringido a subcategorías sin algunas condiciones (que no alcanza aquí). Pero en el espíritu de la combinatoria de las especies, creo categoría de la teoría es la configuración correcta en el que explorar la cuestión de la natural bijections. Tengo algo de nuevo de vuelta-de-la-envoltura ideas que veremos más adelante.

---

Yo sostengo que no es natural bijection entre los dos.

Considerar el finito posets $\Lambda=\{x,y,z,d\}$ $x,y,z\le d$ $\Gamma=\{x,d\}\cup \{y,e\}$ $x\le d$ $y\le e$ y no otras relaciones. Estos son los objetos en la categoría de $\sf Pos$ de posets. Nuestra ecuación establece que $\hom_{\sf Pos}(\Lambda,I)$ $\hom_{\sf Pos}(\Gamma,I)$ son isomorfos en la categoría de $\sf Set$ de conjuntos para cualquier intervalo finito $I$ $(\Bbb N,|)$ - es decir, el positivo naturales ordenado por la divisibilidad. Tenga en cuenta que todos los intervalos finitos $I$ $(\Bbb N,\mid )$ se parece a $[a,b]\cong[1,b/a]$.

Ahora, estos dos homsets están en igualdad de condiciones cuando se está pensando en estos intervalos de $I$, así que vamos a $\cal L$ ser la categoría de parque natural posets isomorfo a un intervalo de $[1,n]$$(\Bbb N,\mid)$. Interpretar $A=\hom_{\sf Pos}(\Lambda,-)$ $B=\hom_{\sf Pos}(\Gamma,-)$ functors $A,B:{\cal L}\to\sf Set$. Hay un isomorfismo natural $A\cong B$?

Si no fueron, a continuación, $A$ $B$ tendría la misma simetría, es decir,${\rm Aut}(A)\cong{\rm Aut}(B)$. Sin embargo, de acuerdo a Yoneda del lexema ${\rm Aut}(A)={\rm Aut}(\Lambda)=S_3$${\rm Aut}(B)={\rm Aut}(\Gamma)=C_2$.

Answer 3

Vamos a tener $x \leq d \leq n$$ y \leq b \leq n$; de alguna manera para encontrar $x,y,z \leq d_1 \leq n $ ... ¿y $d_1 = \mathrm{lcm}(b,d) $$x,y,z \big| d_1$?

A continuación, a partir de $x,y,z \leq d_1 \leq n $ ¿qué es la inversa? $b = \mathrm{lcm}(x,y,z) $ $d = d_1/b$.

---

Añadido 09-17-15

Arthur Benjamin - famoso por la multiplicación de números grandes en su cabeza tiene un par de bijective pruebas de que $(\sum k)^2 = \sum k^3$

Para el caso de perfecta primer poderes, $27$ tiene 4 divisores $1,3,9$ y el sí mismo. En general $\tau(p^k) = k+1$. Vamos a:

\begin{array}{cclclcc} S &=& \{ (a,b,c,d) &:& 0 \leq a,b,c \leq d \leq n & & &\} \\ T &=& \{ \big((x,y),(z,w)\big) &:& 0 \leq x \leq y \leq n & 0 \leq z \leq w \leq n & &\} \end{array}

El bijection depende de si $a < b, a = b, a > b$. Tenemos:

$$ (a,b,c,\color{#64C277}{d})\mapsto \begin{array}{ccc} \Big( (a,b), (c,\color{#64C277}{d})\Big) & \text{if} & a< b \\ \Big( (b,a), (c,\color{#64C277}{d})\Big) & \text{if} & b<a \\ \Big( (b,d),(c,\color{#64C277}{d})\Big) & \text{if} & a= b \\ \end{array}$$

Podemos levantar esta prueba a la identidad en el divisor de la función $\tau (d)$:

\begin{array}{cclclcc} S &=& \{ (a,b,c,d) &:& a,b,c|d & d|n& &\} \\ T &=& \{ \big((x,y),(z,w)\big) &:& x|y, y |n, & z|w, w |n & &\} \end{array}

El bijection explits en dos partes, con $(a,b)$ $(c,d)$ comportándose por separado:

$$ (a,b,c,d) \mapsto \Big(\mathrm{gcd}(a,b), \mathrm{lcm}(a,b)\Big), \Big( c,d \Big)$$