¿Hay alguna manera de relacionar los números primos y la transformada de Fourier

Question

Según lo que sé sobre las transformadas de Fourier, cualquier señal periódica continua puede representarse como una combinación de funciones seno y coseno. Para mí, esto parece análogo al "Teorema fundamental de la aritmética" (todo número entero puede representarse como un producto único de primos") [El número entero es la señal y los primos son el seno y el coseno].

¿Alguna idea de cómo conectar la transformada de Fourier con la factorización de primos?

(P.D. He encontrado este documento que hace algo parecido http://arxiv.org/pdf/1410.2054v1.pdf )

Answer 1

La cuestión es bastante amplia, pero he aquí una posible relación entre la transformación de Fourier y los números primos.

Sabemos que el Función zeta de Riemann se define como $$\zeta(s) = \sum_{n=1}^\infty\frac{1}{n^s},$$ para todos $\Re(s)>1$ .

Lo segundo, que la función zeta de Riemann está relacionada con los números primos a través de Fórmula del producto de Euler .

$$\zeta(s)=\sum_{n=1}^\infty\frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1-p^{-s}},$$

para todos $\Re(s)>1$ .

Como generalización de la función zeta de Riemann la Función zeta de Hurwith se define como $$\zeta(s,q) = \sum_{n=0}^\infty \frac{1}{(q+n)^{s}},$$ para todos $\Re(s)>1$ y $\Re(q)>0$ . La función zeta de Riemann es $\zeta(s,1)$ .

Otra forma de generalizar la función zeta de Riemann es utilizando polilogaritmo que se define como

$$\operatorname{Li}_s(z) = \sum_{k=1}^\infty {z^k \over k^s}.$$

Para $\Re(s)>1$ tenemos $\operatorname{Li}_s(1)=\zeta(s)$ . También es verdadero que $\operatorname{Li}_s(-1)= (2^{1-s}-1)\zeta(s)$ .

La secuencia de $N$ números complejos $x_0,x_1,\dots,x_{N-1}$ se transforma con transformación discreta de Fourier en un $N$ -secuencia periódica de números complejos con

$$X_k\ =\ \sum_{n=0}^{N-1} x_n \cdot e^{-i 2 \pi k n / N}, \quad k\in\mathbb{Z}\,.$$

Por supuesto, utilizando Fórmula de Euler también podríamos utilizar funciones trigonométricas.

Aquí viene la conexión. La transformada discreta de Fourier de la función zeta de Hurwitz con respecto a la orden $s$ es el Función chi de Legendre que se define como $$\chi_s(z) = \sum_{k=0}^\infty \frac{z^{2k+1}}{(2k+1)^s}.$$ La función chi de Legendre está relacionada con los polilogaritmos de la siguiente manera. $$\chi_s(z) = \frac{1}{2}\left[\operatorname{Li}_s (z) - \operatorname{Li}_s (-z)\right].$$

Así que también es cierto que

$$\chi_s(1) = (1-2^{-s})\zeta(s),$$

para todos $s>0$ números reales.

Así que si juntamos todo esto.

$$\prod_{p \text{ prime}} \frac{1}{1-p^{-s}} \stackrel{\text{DFT}}{\implies} (1-2^{-s})\prod_{p \text{ prime}} \frac{1}{1-p^{-s}},$$

para todos $s>0$ números reales.

Espero que mi argumento sea correcto, simplemente me ha venido a la mente al leer tu pregunta. Al hacer la DFT al final hemos sustituido $z=1$ en la función Legrende chi.

Answer 2

No es tan lógico representar los primos utilizando directamente la transformada de Fourier. La transformada de Fourier tiene en mente la linealidad y hay cierta linealidad pero no la que se puede explotar fácilmente entre los primos.

Al principio, parece que el cribado, cuando se cruza cada segundo, luego cada tercero, luego cada quinto número y así sucesivamente, es de naturaleza lineal, ¿verdad? Pero esto sólo esconde una dolorosa verdad que $2 \cdot 3 = 6$ y que $2+3$ no está revelando nada respecto a la composición de $5$ .

Si se parte de la base de que todo número puede representarse unívocamente como un producto de primos

$$n=\prod_{k=1}^{\omega(n)}p_{m_k}^{\alpha_k}$$

se obtiene la linealidad prevista utilizando

$$\ln(n)=\sum_{k=1}^{\omega(n)}\alpha_k\ln(p_{m_k})$$

Técnicamente, si se permite $\alpha_k=0$ tienes

$$\ln(n)=\sum_{k=1}^{+\infty}\alpha_k\ln(p_k)$$

donde $\alpha_k=0$ significa que $p_k$ no es un factor de $n$ que $n$ no es divisible por $p_k$ .

Esto, la observación de los números primos usando la escala logarítmica, te lleva a un primo de la transformada de Fourier, que es la transformada de Mellin. Para ilustrarlo, usaremos la función Gamma, la extensión del factorial, así que si $f(x)=e^{-x}$ entonces su transformada Mellin es la función Gamma

$$\Gamma(s) = \int_0^\infty e^{-x}x^{s-1} dx$$

Nosotros puede definir la transformada de Fourier mediante la transformada de Mellin, es cierto, pero inevitablemente se agarra a la escala logarítmica en el proceso.

Para entender por qué Mellin sabe mejor, definimos la función zeta de Riemann como la transformada de Mellin de otra función $f(x)=\frac1{e^x-1}$ es decir:

$$\zeta(s) = \frac1{\Gamma(s)}\int_0^\infty \frac1{e^x-1}x^{s-1} dx$$

Para entender lo íntima que es esta función con los primos, unas cuantas relaciones:

$$\ln\zeta(s) = s\int_0^\infty \frac{\pi(x)}{x(x^s-1)} dx$$

$$\frac{1}{\zeta(s)}=\sum_{n=1}^\infty \frac{\mu(n)}{n^s}$$

$$\zeta^2(s) =\sum_{n=1}^\infty \frac{d(n)}{n^s}$$

$$-\frac{\zeta'(s)}{\zeta(s)} = \sum_{n=1}^\infty \frac{\Lambda(n)}{n^s}$$

$$\frac{\zeta^2(s)}{\zeta(2s)} = \sum_{n=1}^\infty \frac{2^{\omega(n)}}{n^s}$$

donde

$\pi(x)$ es el número de primos hasta $x$

$\mu(n)$ es una función de Möbius igual a $0$ si $n$ es divisible por el cuadrado en caso contrario $1$ si es que tiene par y $-1$ si tiene un número impar de factores primos

$d(n)$ es el número de divisores de $n$

$\Lambda(n)$ es la función de von Mangoldt igual a $\ln(p)$ si el número $n$ es $n=p^k$ De lo contrario, $0$

$\omega(n)$ es el número de factores primos distintos de $n$

y muchas más relaciones como éstas.

De nuevo, no estamos lejos de la transformada de Fourier, sólo estamos escalando para extraer la esencia multiplicativa. La transformada de Fourier pura puede conectar dos relaciones multiplicativas relacionadas con los primos, pero para profundizar en los primos necesitamos la transformada de Mellin relacionada.

En cuanto a la factorización de primos, no hay mucho en lo que la transformada de Fourier esté directamente implicada. El problema es tan complejo que las técnicas rozan los límites matemáticos y no es raro que se recurra a la adivinación y a la heurística, incluso cuando se espera que la factorización sea muy rápida y cuando el algoritmo es bastante preciso y sólido.

Aún así, si se mira la función zeta de Riemann definida anteriormente como

$$\zeta(s)=\sum_{n=1}^{\infty} n^{-s} = \prod_{p \text{ is prime}}\frac1{1-p^{-s}}$$

tienes disponible la factorización de cada $n$ aunque no se puede extraer directamente. Dado que la función zeta de Riemann está íntimamente relacionada con otras funciones aritméticas, lo único que se necesita es poder extraer $n^{th}$ coeficiente de cualquier suma interesante:

$$f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}$$

y eso sería

$$\frac{a_n}{n^{\sigma}} = \lim_{T\to\infty} \frac{1}{2T} \int_{-T}^{T} f(\sigma+ it)n^{it} \mathrm{d}t$$

y se puede obtener suficiente información sobre la factorización para iniciar la factorización real. Esta no es la forma más rápida posible conocida, pero es la forma que está relacionando Fourier, es decir, la transformada Mellin, con el proceso de factorización más directamente que con otros métodos conocidos.