Gran Lista de Erdős " elemental pruebas

Question

Paul Erdős fue uno de los más grandes matemáticos de todos los tiempos y fue famoso por su elegante pruebas Del Libro. He publicado una pregunta acerca de uno de sus teorema y tiene un de referencia, y tengo otra pregunta quiero saber la respuesta. Pero, en lugar de solicitar una referencia para cada teorema dio con una primaria de la prueba, me he decidido a hacer un hilo para una lista grande de toda su educación primaria de las pruebas.

Estoy emocionado. Vamos a hacer un índice de las páginas del Libro nos muestra !

Por favor, siéntase libre de contribuir.

Para conseguir que los chicos se inició, voy a hacer una lista de deseos de sus teoremas que las referencias que quiero ver. Os animo a añadir a mi lista de deseos, si así lo desean.

Lista de deseos :

• El producto de dos o más enteros positivos consecutivos es nunca un cuadrado o cualquier otro poder superior.
• Un grafo conexo con un grado mínimo $d$ y al menos el $2d+1$ vértices tiene un camino de longitud de, al menos,$2d+1$.
• Deje $d(n)$ el número de divisores de a $n$. A continuación, la serie de $\sum_{n=1}^\infty d(n)/2^n$ converge a un número irracional
• Deje $g(n)$ ser el número mínimo de puntos en la general de la posición en el plano necesarias para asegurar que existe un subconjunto que forma convexa $n$-gon. A continuación, $$2^{n-2} + 1 \leq g(n) \leq \frac{(2n-4)!}{(n-2)!^2} + 1$$
• Erdos-Rado teorema de
• Erdős-Mordell la desigualdad

Answer 1

Creo que esto es digno de publicar aquí, sobre todo porque yo realmente disfrutar de la sencillez de esta prueba, pero también porque no tengo idea de como es bien conocido. El resultado no es profundo e importante, por lo que el interés principal está en la simplicidad del argumento. Erdős demostrado un límite inferior en el número de números primos antes de un entero $n$.

Wacław Sierpiński, en su Teoría Elemental de Números, atribuye a Erdős la siguiente primaria de la prueba de la desigualdad de $$\pi(n)\geq\frac{\log{n}}{2\log{2}}\quad\text{for }n=1,2,\ldots.$$

Por favor, tenga en cuenta que he adaptado el argumento de que el texto del libro para hacer las cosas, en mi opinión, un poco más claro. Tenga en cuenta también que las únicas herramientas que se utilizan en la siguiente prueba son algunos de los básicos de la combinatoria de los hechos y algunos resultados acerca de los cuadrados de los números libres, los cuales pueden, por ejemplo, se demostró con el Teorema Fundamental de la Aritmética.

Deje $n\in\mathbb{N}=\{1,2,3,\ldots\}.$ Considerar el conjunto $$S(n) = \{(k,l)\in\mathbb{N}^{2}:l\text{ is square-free and }k^{2}l\leq n\}.$$ It is a standard fact that every natural number has a unique representation in the form $k^{2}l,$ where $k$ and $l$ are natural numbers and $l$ is square-free. This gives $\lvert S(n)\rvert = n.$

Ahora si tenemos un par de $(k,l)$$k^{2}l\leq n,$, entonces debemos tener $k^{2}\leq n$$l\leq n$, ya que el $k$ $l$ son positivos. Tenga en cuenta que esto da $k\leq\sqrt{n}.$ Desde $l$ es cuadrado-libre, $l$ se puede expresar como un producto de distintos números primos, cada uno de los cuales debe ser no mayor que $n$ desde $l\leq n$. Es decir, $l$ se puede expresar como un producto de los números primos $p_{1},p_{2},\ldots,p_{\pi(n)}.$ Hay $2^{\pi(n)}$ dichos productos.

Por lo tanto, si conocemos $(k,l)\in S(n)$, a continuación, existen en la mayoría de las $\sqrt{n}$ posibilidades de lo $k$ podría ser y en la mayoría de las $2^{\pi(n)}$ posibilidades de lo $l$ podría ser (independiente de $k$, por supuesto). De ello se desprende que $\lvert S(n)\rvert \leq 2^{\pi(n)}\sqrt{n},$ $n\leq2^{\pi(n)}\sqrt{n}.$

Tomando $\log$s y reorganizar da el resultado.

Answer 2

Aquí es una exposición de la prueba que hizo Erdos famoso por David Galvin. Primaria prueba de Bertrand postuladoque afirma que no es un número primo entre todos los $n$$2n$. La esencia de esta prueba está en darse cuenta de que el límite inferior de $$\binom{2n}{n} \geq \frac{4^n}{2n + 1}$$ The binomial expression is the middle term (and the largest) of $(1+x)^{2n}$. The lower bound is the average of the sum of all binomial coefficients. This is obtained by putting $x=1$, and then dividing by the number of terms. This gives us the average. Obviously, the largest term should be bigger than the average. If the postulate does not hold, there is an upper bound that is smaller than this lower bound for large $n$. The postulate can easily be verified for the smaller values of $$ n.

https://www3.nd.edu/~dgalvin1/pdf/bertrand.pdf

Answer 3

Uno muy simple, y sin embargo uno de mis favoritos es el Erdős-Anning teorema:

Deje $ A \subseteq \mathbb C $ ser un conjunto infinito de puntos, de tal manera que

$$ \forall x, y\in A \quad |x-y| \in \mathbb N $$

entonces existe algún $ c,k \in \mathbb C $, de tal manera que todos los $ a \in A $ es de la forma $ a = cx + k $ algunos $ x \in \mathbb R $.

Se probó en 1945 en la American Mathematical Boletín. http://www.ams.org/journals/bull/1945-51-08/S0002-9904-1945-08407-9/S0002-9904-1945-08407-9.pdf

---

Una más colorido formulación es que un infinito de conjuntos de puntos en el Cartesiano plano con la mutua entero distancias debe estar en una línea recta.

Para demostrarlo, tenemos un límite superior en el número de no colineales de puntos posibles en un conjunto integral de las distancias. Más específicamente, si hay un conjunto de no colineales puntos entero distancias, todas en la mayoría de las $d$, en la mayoría de los $4(d + 1)^2$ puntos con el entero de las distancias puede ser añadido al conjunto.

Answer 4

Erdos " prueba de Infinitos números primos

La siguiente prueba es tomada del libro - "las Pruebas DEL LIBRO" por Martin Aigner y Gunter Ziegler. Esta prueba se atribuye a Erdos.

Esto demuestra que existen infinitos números primos y que la serie de la suma de primer medidas recíprocas diverge. Supongamos que la serie infinita $\sum\frac{1}{p}$ donde $p$ indica los números primos es convergente. Luego, debe de existir algún número natural $k$ de manera tal que, $$\sum_{i > k} \frac{1}{p_i} < \frac{1}{2}$$

Para cualquier número natural $N$, obtenemos la desigualdad $$\sum_{i > k} \frac{N}{p_i} < \frac{N}{2}$$

Ahora, hacemos un llamamiento a todos los números primos $p_1, p_2, \dots , p_k$ el pequeño de los números primos, y todos los demás primos de los grandes números primos.

Deje $N_b$ denotar el número de enteros positivos $n \leq N$ que tienen al menos un divisor que es un gran primer. Y $N_s$ denotar el número de enteros positivos a menos de $N$ que solo tienen pequeños primos divisores.

Vamos a mostrar que, para un adecuado $N$, $N_b + N_s < N$, lo cual es una contradicción, porque su suma debe ser igual a $N$.

En primer lugar, calculamos $N_b$ $$N_b \leq \sum_{i > k}\big\lfloor \frac{N}{p_i} \big\rfloor < \frac{N}{2}$$

Ahora, nos fijamos en $N_s$. Escribimos cada $n \leq N$ $a_nb_n^2$ donde $a_n$ es la parte libre de cuadrados. $a_n$ es un producto de diferentes pequeños números primos. Sólo hay $k$ pequeño de los números primos, y cada uno de los prime pueden ser elegidos o no elegidos. Por lo tanto, hay sólo $2^k$ diferentes valores de $a_n$. Además, \begin{align} b_n \leq \sqrt n \leq \sqrt N \\ \text{There are at most %#%#% different values of %#%#%} \\ \implies N_s \leq 2^k\sqrt N \end{align}

Ya, $\sqrt N$ es siempre menor que $b_n$, sólo tenemos que encontrar un valor de $N_b$ tal que $N/2$. Esto sucede cuando $N$. Cuando $N_s \leq N/2$, $N = 2^{2k + 2}$. Esto demuestra nuestra contradicción que $N = 2^{2k + 4}$$, que demuestra que la serie diverge y que existen infinitos números primos.

Answer 5

Erdos' preguntas favoritas. Los siguientes no son trabajos de investigación, pero preguntas populares Erdos utiliza para pedir a los niños.

• Si $n+1$ enteros son elegidos de la primera $2n$ enteros, siempre habrá dos que son co prime.

Habrá dos números consecutivos. Estos dos números son primos relativos. Para ver que esto no es cierto cuando se $n$ enteros son elegidos, sólo tienes que seleccionar todos los números pares.

• Si $n+1$ enteros son elegidos de la primera $2n$ enteros, siempre habrá dos de tal manera que uno divide los otros.

Cada número se puede expresar como el producto de una potencia de dos y un número impar. Sólo hay $n$ números impares en la primera $2n$ enteros. Dos de los números que se multiplican por el mismo número impar. Uno de ellos tiene una menor potencia de dos. Este número se divide el otro. Para mostrar que no es necesariamente cierto para $n$ enteros, elija $n+1,n+2, \dots 2n$.

• Supongamos que tenemos $n$ números naturales, ninguno de los cuales es mayor que $2n$ de manera tal que el mínimo común múltiplo de los dos es mayor que $2n$. Entonces, todos los $n$ números son mayores que las de $2n/3$.