Representación de un número cercano a 1, con un suma de los recíprocos de los números naturales

Question

Para enteros positivos $n_1, \ldots, n_k$, vamos a $H(n_1, \ldots, n_k)$ denotar $1/n_1 + \ldots + 1/n_k$. Deje $V(N)$ ser el valor más grande posible de $H(n_1, \ldots, n_k)$ que es menor que 1, sujeto a la condición de que $n_1 + \ldots +n_k \le N$. Por lo $V(5) = 5/6$, se dio cuenta de como $1/2 + 1/3$. Mi pregunta es, ¿cómo $1/(1-V(N))$ crecer como una función de la $N$? En particular, hay un $C$ y un $k$ tal que $$ \frac 1{1-V(N)} \le C N^k\ $$ para todos los $N$?

Answer 1

$K(N) := 1 / (1 - V(N))$ crece más rápido que cualquier potencia de $N$.

Esto puede ser visto por encontrar para cada una de las $k$ una identidad $$ \sum_{i=1}^m \frac{A_i x + B_i}{C_i x + D_i} = 1 - c x^{-(2k+1)} + O(x^{-(2k+2)}) $$ donde los coeficientes $A_i,B_i,C_i,D_i$ son enteros con $A_i, C_i > 0$ e $c$ es un número racional positivo (y el lado derecho es una expansión de Taylor acerca de la $x=\infty$). Una vez que tenemos una identidad, que podemos tomar para $x$ un entero grande (en particular, suficientemente grande como para que los denominadores $C_i x + D_i$ y numeradores $A_i x + B_i$ son todas positivas), y escribe cada término $(A_i x + B_i) \, / \, (C_i x + D_i)$ como una suma de $A_i x + B_i$ copias de el recíproco de $C_i x + D_i$. Entonces como $x\rightarrow\infty$ la suma de $N$ de los denominadores, que crece como un múltiplo de $x^2$, mientras que $1/(1-H)$ crece como $x^{2k+1}$, que es más rápido que el $N^k$.

La identidad que necesitamos es fácil de construir porque las condiciones en los coeficientes son lineales en el $B_i$ (y también en el $A_i$, pero no hacemos uso de este). Por ejemplo, fijar distintas racionales $\delta_i$ positivos y racionales $\alpha_i$ con $\sum_{i=1}^m \alpha_i = 1$, y, a continuación, encontrar racional $\beta_i$ tal que $$ \sum_{i=1}^m \frac{\alpha_i x + \beta_i}{x + \delta_i} = 1 + O(x^{-(2k+1)}); $$ eso es $2k$ independiente de ecuaciones lineales en $m$ incógnitas, de modo que existe una solución de una vez $m \geq 2k$. A continuación, escribir cada plazo $(\alpha_i x + \beta_i) / (x + \delta_i)$ como $(A_i x + B_i) \, / \, (C_i x + D_i)$ con coeficientes enteros. Debemos mostrar que hay una selección de $\alpha_i$ e $\delta_i$ que hace que el $x^{-(2k+1)}$ coeficiente distinto de cero; pero esto es fácil, por ejemplo, porque de otra manera que el coeficiente de desaparecerían, de forma idéntica, incluso si se nos permite compleja $\alpha_i$ e $\delta_i$, y que la contradice (por $m=2k+1$) por el parcial de la fracción de descomposición de la función racional $X^{2k+1} / (X^{2k+1} - 1)$. Jeremy Kahn insiste en que el $x^{-(2k+1)}$ coeficiente de ser negativo, pero si nuestro receta pasa a producir un coeficiente positivo, entonces podemos obtener una negativo por el cambio de cada una de las $B_i$ e $D_i$ a $-B_i$ e $-D_i$ respectivamente (es por eso que hemos utilizado un exponente impar $2k+1$).

Puede ser razonable esperar que las $K(N)$ crece casi tan rápido como el número de particiones $(n_1,\ldots,n_k)$ de % de$N$, es decir, $\log K(N)$ debe ser asintótica algún múltiplo de $\sqrt{N}$ (o, en todo caso debe crecer o no mucho más lento de lo $\sqrt{N})$, porque hay un montón de particiones para que $\sum_{i=1}^k 1/n_i < 1$. Computación numérica parece corroborar esta conjetura; aquí está el registro los valores de $K(N)$ para $2 \leq N \leq 72$, seguido por el número total de particiones y el número de particiones con $\sum_{i=1}^k 1/n_i < 1$:

 N     K(N)        #      #1
 2      2          2       2
 5      6          7       3
10     12         42       7
11     20         56       9
12     42         77      13
17     60        297      26
19    120        490      39
23    156       1255      79
29    168       4565     194
30    231       5604     230
31   1320       6842     265
44   3740      75175    1519
49   5040     173525    2754
57  23100     614154    6832
67  34807.5  2679689   20372
70  47058    4087968   27744

Curiosamente $K(N)$ es siempre un número entero en esta gama, excepto para $K(N) = 34807\!\frac12 = 2^{-1} \, 3^2 \, 5 \; 7 \; 13 \; 17$ para $67 \leq N \leq 69$. Aquí está el gp de código que genera este tipo de datos (en unos 10 minutos):

S(v) = sum(i=1,#v,1/v[i])

{
K(n, v,p,c) =
  v = partitions(n);
  p = #v;
  v = vecsort(vector(p,i,S(v[i])));
  c = 1;
  while(v[c]<1,c++);
  [n, 1. / (1-v[c-1]), p, c]
}

\p 9
allocatemem(2^31)
#
for(n=2,72,print(K(n)))

AÑADE DESPUÉS: Aquí un poco más de datos computacional. El uso de gp-2.6's nueva función forpart en lugar de particiones, y la eliminación de la innecesario ordenar, evita el uso de $p(n)$ espacio; también podemos ahorrar tiempo no se trata de cualquier partición con $n_1=1$. Esto nos permite ampliar el cálculo de a $N=100$ en alrededor de media hora. Aquí están los registros (ahora incluyendo dos más no integral a los valores de $74 \leq N \leq 79$), junto con todas las particiones que conseguirlos:

 N        K     n_i
 2        2     2
 5        6     2, 3
10       12     3, 3, 4
11       20     2, 4, 5
12       42     2, 3, 7
17       60     3, 4, 5, 5
19      120     3, 3, 5, 8
21      """     2, 5, 6, 8
23      156     3, 3, 4, 13
25      """     2, 4, 6, 13
29      168     3, 4, 7, 7, 8
30      231     2, 3, 11, 14
32      420     2, 4, 5, 21
33      """     3, 4, 5, 7, 14
38     1320     2, 5, 8, 11, 12
40     """"     4, 5, 6, 6, 8, 11
44     3740     2, 4, 10, 11, 17
47     """"     4, 5, 5, 5, 11, 17
49     5040     3, 4, 7, 9, 10, 16
56     """"     2, 7, 9, 10, 12, 16
57    23100     3, 4, 7, 7, 11, 25
64    """""     2, 7, 7, 11, 12, 25
66    """""     4, 6, 6, 7, 7, 11, 25
67    34807.5   3, 5, 7, 9, 13, 13, 17
70    47058     2, 3, 11, 23, 31
74    59690.4   2, 4, 11, 17, 19, 21
75    """""""   3, 4, 7, 11, 14, 17, 19
79    91162.5   3, 5, 5, 11, 13, 17, 25
80   200970     3, 5, 7, 7, 11, 18, 29
83   """"""     5, 6, 7, 7, 9, 9, 11, 29
89   """"""     5, 6, 6, 7, 7, 11, 18, 29
92   239085     5, 5, 7, 7, 7, 11, 23, 27
96   405720     2, 5, 8, 9, 23, 49

y aquí está la gp-2.6 código:

\\ gp-2.6
S(v) = sum(i=1,#v,1/v[i])

{
K(n, p,p1,c,c1) =
  c = 0;
  p = [];
  forpart(p1=n, c1=S(p1); if((c1<1) && (c1>=c),
    if(c==c1, p=concat(p,[Vec(p1)]), c=c1; p=[Vec(p1)])
  ), [2,n]);
[n, 1./(1-c), p]
}

\p 10
#
for(n=2,100,print(K(n)))

Answer 2

Mayor detalle sobre el contexto de la pregunta. Thurston (ver Doaudy y Hubbard) considera ramificada cubierta $f\colon S^2 \to S^2$ tal que $P_f \equiv \{ f^n(c) \mid c \in C_f$ es finito (donde $C_f$ es el conjunto de puntos críticos de $f$). Se define un mapa de $\sigma_f$ de $\operatorname{Teich}(S^2, P_f)$ a sí mismo tirando hacia atrás de estructuras complejas (hasta mapas isotópica para la identificar rel $P_f$) por $f$. Los puntos fijos para $\sigma_f$ son exactamente racional de los mapas que son "combinatoria" equivalente a $f$. Por otra parte, la prueba de que en el caso genérico de $f$, el mapa de $\sigma_f$ es uniformemente contratante en subconjuntos compactos de $M(S^2, P_f)$, que es el espacio de los mapas de $P_f$ dentro de la esfera de Riemann, hasta la transformación de Moebius.

Por otra parte entendemos el mapa de $\sigma_f$ hasta un almacén de error como el siguiente. Deje $WA(S^2, P_f)$ ser el espacio real de sumas ponderadas de los distintos curvas (no trivial y nonperipheral, y hasta homotopy) en $S^2 \setminus P_f$. Podemos definir un mapa de $W \colon \operatorname{Teich}(S^2, P_f) \rightarrow WA(S^2, P_f)$ por la ponderación de cada curva por el módulo de los asociados que cubren el anillo, y luego de descartar las curvas de peso de menos de 1. Por otra parte, podemos demostrar lo fundamental estimar que $$ W(\sigma_f(X)) = f^*W(X) + O(1) $$ para todos los $X \in \operatorname{Teich}(S^2, P_f)$ donde $f^*\colon WA(S^2, P_f) \to WA(S^2, P_f)$ está definido por $$ f^*\gamma = \sum_{f(\eta) = \gamma} \frac1{\operatorname{grados} f|_\eta} \eta. $$ Aquí la constante de la junta(1) sólo depende de la $\operatorname{deg} f$ e $|P_f|$.

Ahora supongamos que $\alpha$ es una "invariante multicurvos", lo que significa que $f^{-1}(\alpha) \subset \alpha$. A continuación, $f^*\colon \mathbb R^\alpha \to \mathbb R^\alpha$ es una transformación lineal positiva (o al menos no negativa) y por lo que tiene un líder positivo autovalor $\lambda_\alpha$. Si $\lambda_\alpha > 1$ es fácil probar que $\sigma_f^nX \to \infty$ as $n \to \infty$, para cualquier punto de partida $X$. Resulta que el mismo también se aplica en el caso de $\lambda_\alpha = 1$.

Si $\lambda_\alpha = 1 - 1/K$ se espera tomar alrededor de $K$ iteraciones de $\sigma_f$ para llegar a un lugar donde la cubierta anillos han módulo sobre $K$. En particular, si $\alpha$ es una sola curva, a continuación, vamos a tener $$ W_\alpha(\sigma_f X) = (1-1/K) W_\alpha(X) + O(1) $$ donde el $O(1)$ término es positivo y converge en el curso de la iteración.

Ahora bien, debemos ser capaces de construir un ramificada cubierta $f$ de grado acerca de la $N$ (con $|P_f| = 4$) y de una sola curva de $\alpha$ a $S^2 \setminus P_f$ tal que $f^*\colon \mathbb R^\alpha \to \mathbb R^\alpha$ es la multiplicación por $1 - 1/K(N)$, y luego por Noam Elkies " estimación nos encontramos con que el número de iteraciones de $\sigma_f$ obtener cerca del punto fijo (a partir de un punto de partida razonable) puede crecer superpolynomially en $\operatorname{deg} f$ e $|P_f|$. Así que la iteración de $\sigma_f$ no es un polinomio de tiempo de algoritmo para encontrar el punto fijo de $\sigma_f$ (que es el único racional mapa representando $f$).

Answer 3

Usted puede ser que desee comprobar hacia fuera las referencias en el artículo de la Wikipedia en Fracciones Egipcias.

Answer 4

Un determinado documento que viene a la mente es "En Engel y Sylvester de la serie" por Erdos, Renyi, y Szusz. Está disponible aquí. La Sylvester de la serie es el así llamado "Codiciosos Egipcio fracción". Dejamos $x=\frac {1} {Q_1(x)}+\frac {1}{Q_2(x)}+\cdots$ ser la Sylvester serie de $x \in (1,\infty)$. Que demostrar (Teorema 6) que para casi todos los $x$

$$ \lim_{n \to \infty} \frac {\log Q_n(x)} {2^n} $$

existe y es finito. Utilizan métodos probabilísticos para llegar a este resultado. Ellos también se llega a un resultado similar para Engel de la serie. Este es definitivamente diferente de lo que usted está buscando, pero a mí me parece algo similar en que usted todavía está tratando de llegar a asymptotics que provienen de este tipo de expansiones. Así que tal vez hay algunas técnicas que utilizan?