Representación de números no enteros, con base a los pocos (pero posiblemente negativa) distinto de cero dígitos

Question

De fondo

En una reciente pregunta acerca de los números de Fibonacci, se afirmó que

cada número entero se puede escribir en la forma $\sum_{i=1}^6 \epsilon_i F_{n_i}$$\epsilon_i \in \{0,-1,1\}$. El límite superior de la suma no es un error tipográfico: cada número es la suma/diferencia de en la mayoría de las 6 de fibonacci.

Creo que esto es falso, incluso para los más grandes (pero finito) los valores de $6$:

Primero de todo, sin pérdida de generalidad, podemos suponer que las representaciones que no se repita ningún número Fibonacci (es decir, el $n_i$s son distintos) y, además, no contienen cualquiera de los dos números de Fibonacci consecutivos (es decir, $n_i \ne n_j+1$). Podemos llegar a una representación mediante las siguientes simplificaciones en varias ocasiones:

• Si dos días consecutivos de números de Fibonacci aparecen con signos opuestos, simplificar la expansión con la identidad de $F_n - F_{n-1} = F_{n-2}$.
• Si dos consecutivos de Fibonacci aparecen los números con el mismo signo, simplificar la expansión con la identidad de $F_n + F_{n-1} = F_{n+1}$.
• Si el mismo número Fibonacci aparece con signos opuestos, simplemente cancelar los dos términos.
• Si el mismo número Fibonacci aparece con el mismo signo, a continuación, utilizar la identidad de $F_n + F_n = F_{n-2} + F_{n-1} + F_n = F_{n-2} + F_{n+1}$ a reemplazarlos con dos personas que no son idénticos números de Fibonacci.

Las tres primeras operaciones de reducir el número de términos en la expansión y por lo tanto estrictamente simplificar la expresión (en términos de cuántos términos hay), pero el último puede ser necesario utilizar varias veces antes de que se "simplifica" la expresión (por ejemplo, en términos de cuántos repiten términos hay). No obstante, esta simplificación del procedimiento termina, como es imposible quedar atrapado en un bucle infinito con la última operación solo. (Prueba: podemos suponer que el $n_i$ son positivos. A continuación, todas las operaciones de reducir el número de términos, o las hojas que se modifican y se reduce a la suma de los $n_i$.)

Ahora, supongamos que tenemos una representación (no idénticos términos, no hay términos consecutivos) y supongamos que el mayor número de Fibonacci aparecen en el $F_n$. A continuación, el siguiente mayor plazo (en valor absoluto) que puede aparecer es $F_{n-2}$, el siguiente más grande después de que $F_{n-4}$, y así sucesivamente. Con todo, la suma de los términos excluyendo $F_n$ es en la mayoría de las $F_{n-2} + F_{n-4} + \cdots \le F_{n-1}$ (prueba por inducción: agregar $F_n$ a ambos lados). Por la desigualdad de triángulo, la suma de todos los términos deben ser de al menos $F_n - F_{n-1} = F_{n-2}$. El punto de este cálculo es que si usted desea representar un número inferior a $F_{n-2}$, no puede usar los términos que se $F_n$ o mayor.

Esto nos lleva a la contradicción. Considerar los números enteros entre el$0$$F_{n-2}-1$. Cuántos posibles representaciones de los números en este rango? Bien, tenemos seis términos que son 0 o $\pm F_k$ $k\lt n$ (a partir de la discusión anterior), por lo que tenemos en la mayoría de las $(2n+1)^6$ representaciones que podría caer en el rango. (Estamos sobre-contar aquí porque no me importa y es más fácil.) Sin embargo, hay claramente $F_{n-2}$ diferentes números enteros en el rango dado. Supongamos por contradicción que fueron siempre es posible representar números como la suma/diferencia de en la mayoría de las 6 de Fibonacci. A continuación, se habría

$$ (2n+1)^6 \ge F_{n-2}. $$

Finalmente, debido a que el lado izquierdo crece exponencialmente mientras que el lado derecho crece de manera exponencial, lo suficientemente grande como valor de $n$ va a producir una contradicción.

Mis preguntas

1. Es la prueba anterior correcta? (Si no, y el original de la reclamación es correcta, me puede dar una representación del número 5473?) Edit: por Favor, consulte Michael Lugo respuesta para un papel que se encuentra la representación con la menor cantidad de dígitos distintos de cero en este "firmado Fibonacci base". Por favor, considere la siguiente la pregunta aquí:

2. Suponiendo que la prueba es correcta, es la afirmación original de verdad para otros no-entero bases? A lo que me refiero es la siguiente:

¿Existe un número natural $k$ y un número real $b>1$ de manera tal que cada entero tiene una representación como $\sum_{i=1}^k \epsilon_i \lfloor b^{n_i} + \frac12 \rfloor$? Es decir, cada número tiene una representación en la "base de $b$" $b$ es probablemente irracional, redondeamos $b^n$ al entero más cercano) con en la mayoría de las $k$ cero "dígitos", pero donde los "dígitos" puede ser $\pm 1$?

Tenga en cuenta que la demanda original es un ejemplo de esto: $k=6$$b=\varphi = \frac{1+\sqrt 5}{2}$.

No creo que mi prueba de obras directamente debido a que utiliza las propiedades especiales de los $\varphi$/los números de Fibonacci. Es posible quitar esta dependencia? En particular, el segundo paso de la prueba muestra que no es "útil" para tener grandes números de Fibonacci en la representación de un pequeño número. Es la misma verdad para cada base $b$?

Nota: si los dígitos no se les permitió ser negativo, entonces mi prueba iba a ir a través de. La cuestión principal es si o no $\pm b^n$ grandes $n$ puede cancelar y producir pequeñas cantidades.

Gracias!

Answer 1

En un artículo reciente en números Enteros, Hannah Alpert demuestra que "todo número entero puede escribirse de forma única como suma de números de Fibonacci y sus inversos aditivos, de tal forma que cada dos términos de un mismo signo se diferencian en el índice por al menos 4 y cada una de las dos términos de diferente signo se diferencian en el índice por al menos 3. Además, no hay manera de usar el menor número de términos para escribir un número como una suma de números de Fibonacci y sus inversos aditivos." Alpert fue en el área de Duluth REU mencionado por Kevin O''Bryant en su comentario; sospecho que esto es el documento de referencia y el resultado fue que en algún momento miscommunicated.

El procedimiento Alpert da para encontrar un representaiton da, por ejemplo, 5473 = 6765 - 1597 + 377 - 89 + 21 - 5 + 1. Creo que 5473 es el número más pequeño que necesita de siete términos.

Answer 2

Esta es una respuesta a tu "pregunta" (2), basándose en algunas de las ideas de Douglas Zare la respuesta.

Lema 1: Supongamos que $0 < r < 1$. Deje $S=\lbrace \epsilon r^i : \epsilon = \pm 1 \text{ and } i \in \mathbb{Z}_{\ge 0} \rbrace$. Fix $k \ge 1$. Deje $S_k$ el conjunto de las sumas de la forma $s_1+\cdots+s_k$ tal que $s_i \in S$ $|s_1|=1$ y no hay ningún subconjunto no vacío $I \subset \lbrace 1,\ldots,k \rbrace$$\sum_{i \in I} s_i = 0$. A continuación, $0$ no está en el cierre de $S_k$.

Prueba: el Uso de la inducción en $k$. El caso base es trivial: $S_1=\lbrace -1,1\rbrace$. Ahora supongamos $k \ge 2$. Si una secuencia $(x_i)$ $S_k$ converge a $0$, entonces la más pequeña sumando en la suma de dar a $x_i$ debe tender a $0$, desde el límite inferior de los valores absolutos de los sumandos reglas que todos, excepto un número finito de elementos de $S_k$, los cuales son todos distintos de cero. El descarte de la un número finito de $x_i$ para que los más pequeños sumando es $\pm 1$ y la eliminación de los más pequeños sumando de cada uno de los restantes $x_i$ los rendimientos de una secuencia $(y_i)$ $S_{k-1}$ tendiendo a $0$, contradiciendo la hipótesis inductiva.

Ahora fix$b>1$$k$. Deje $T=\lbrace \epsilon \lfloor b^n + 1/2 \rfloor : \epsilon = \pm 1 \text{ and } n \in \mathbb{Z}_{\ge 0} \rbrace$. Deje $T_k$ el conjunto de las sumas de la forma$t_1+\cdots+t_k$$t_i \in T$.

Lema 2: Cada una de las $t=t_1+\cdots+t_k \in T_k$ es igual a $u_1+\cdots+u_\ell+\delta$ algunos $\ell \le k$ y algunos $u_i \in T$$u_i = O(t)$$\delta = O(1)$.

Prueba: Examinar los poderes de $b$ utilizado en el $t_i$. Si alguno no vacío subsum (con signos) de estos poderes es igual a $0$, el correspondiente $t_i$ total $O(1)$. Si $b^n$ es el más grande de energía que queda después de la eliminación de todos subsums, divida el resto de las $t_i$$b^n$, y aplicar el Lema 1 con $r=1/b$ a ver que $|t|/b^n$ se apartó de $0$, de modo que todos estos restante $t_i$, que se $O(b^n)$, se $O(t)$.

Corolario: El número de elementos de a $T_k$ de valor absoluto menos de $B$$O((\log B)^k)$$B \to \infty$.

Corolario: $T_k \ne \mathbb{Z}$.

Answer 3

La idea clave en la prueba de obras para otras bases, y otros números de dígitos.

Lema: no Hay un límite basado en el $k$ $b$ por el mayor poder de la $b$, lo que podría ser necesaria en una representación de un número real con una magnitud en $1$ como un polinomio en $b$, las magnitudes de cuyos coeficientes se suman a la mayoría de las $k$.

Prueba: Editar: Mi primera prueba de intento fue defectuosa. Yo quería evitar la inducción en $k$. Voy a tratar de corregir más adelante.

Deje que esta enlazado ser $p(b,k)$. Cuando se cuenta con las sumas de las potencias de $b$, lo que podría ser utilizado para representar un número a a $n$, sólo se necesita considerar los poderes de $b$$\log_b(n+k) + p(b,k)$. Así se puede conseguir en la mayoría de los $(1+2 log_b(n+p))^k$ representable números de $n$, y para las grandes $n$, algunos números no pueden ser representados.

Answer 4

La prueba se ve bien para mí. Como un pequeño ejemplo, un número con una representación de Zeckendorf con 7 términos es 609 = 377 + 144 + 55 + 21 + 8 + 3 + 1 (tenga en cuenta que 609 = 610 - 1); yo creo que es imposible representar 609 como una suma de números de Fibonacci, como se describe en el resultado está siendo desafiada.

No he probado su análisis sobre otras bases, sin embargo.