Qué números hay en el conjunto $S$ ?

Question

Aquí hay un problema que se me ocurrió que me ha estado molestando durante un tiempo, y no he sido capaz de resolverlo.

Dejemos que $S$ sea el conjunto definido por las siguientes reglas:

• $2\in S$ .
• Definir las funciones $\alpha$ y $\beta$ como $$\alpha(n)=n^2$$ $$\beta(n)=\lfloor n/3\rfloor$$ Si $n\in S$ entonces $\alpha(n)\in S$ y $\beta(n)\in S$ .
• Si las dos reglas anteriores no implican que un número $n$ está en $S$ entonces $n\notin S$ .

PREGUNTA: Qué números hay en $S$ ?

Hasta ahora, he verificado que todos los enteros positivos de $1$ a $14$ está en $S$ ya que he encontrado "secuencias de composición" de $\alpha$ y $\beta$ que, cuando se aplica a $2$ para que cada uno de esos números sea el resultado. Por ejemplo, $$3=(\beta^{\circ 4}\circ\alpha^{\circ 3})(2)$$ Las cosas se vuelven un poco locas cuando llego a $n=6$ : $$6=(\beta^{\circ 10}\circ\alpha^{\circ 2}\circ \beta\circ\alpha^{\circ 2})(2)$$ ...y aún más loco en $n=14$ : $$14=(\beta^{\circ 3}\circ \alpha\circ \beta^{\circ 10}\circ \alpha^{\circ 2}\circ \beta\circ \alpha\circ \beta^{\circ 10}\circ \alpha^{\circ 2}\circ\beta^{\circ 2}\circ \alpha^{\circ 3})(2)$$ ¿Alguna idea de cómo demostrar (o refutar) que se puede alcanzar cualquier número entero positivo?

NOTA: Es cierto que todos los enteros positivos están en $S$ si (no si) lo siguiente es cierto:

Blockquote Para cualquier número entero positivo $N$ existen enteros positivos $a,b$ tal que $$N=\bigg\lfloor \frac{2^{2^a}}{3^b}\bigg\rfloor$$

Si alguien descubre cómo demostrarlo, entonces hemos terminado... si es falso, entonces queda trabajo por hacer.

Answer 1

No sé cómo responder a esto, pero permíteme elaborar mis comentarios sobre tu estrategia de prueba propuesta. El punto es que es muy probable que $S$ hace contienen todos los enteros positivos a través de su estrategia, pero es un problema abierto demostrarlo.

Como usted dice, una condición suficiente para $S$ para contener un número entero positivo $N$ es que $N$ puede escribirse de la forma $$N=\bigg\lfloor \frac{2^{2^a}}{3^b}\bigg\rfloor.$$ En términos más generales, si se modifica la definición de $S$ para empezar $x\in S$ y modificar sus funciones para $\alpha(n)=n^y$ y $\beta(n)=\lfloor n/z\rfloor$ para algunos enteros positivos $x,y,$ y $z$ entonces una condición suficiente para $S$ para contener $N$ es que $N$ puede escribirse de la forma $$N=\bigg\lfloor \frac{x^{y^a}}{z^b}\bigg\rfloor.$$

Ahora afirmo que esto es posible para todos los enteros positivos $N$ si toda secuencia finita de dígitos aparece en la base $y$ ampliación de $\log_z x$ . Así que, en su caso, sería la expansión binaria de $\log_3 2$ . La prueba es básicamente "tomar $\log_z$ de todo"; he redactado los detalles a continuación.

La mala noticia es que este tipo de preguntas suelen ser muy difíciles de responder: si se elige un número irracional específico bien definido, suele ser muy difícil decir algo sobre sus expansiones de base. En particular, estoy bastante seguro de que para todos los enteros positivos $x,y,$ y $z$ para lo cual $\log_z x$ es irracional, es un problema abierto si la base $y$ ampliación de $\log_z x$ contiene todas las secuencias finitas.

Por otro lado, si elige un al azar (uniformemente de algún intervalo), entonces con probabilidad $1$ contendrá cada secuencia finita en cada base. Así que se considera extremadamente probable que $\log_z x$ contiene toda secuencia finita en base $y$ pero sería un descubrimiento asombroso si no fuera así. En particular, esto significa que es muy probable que su conjunto $S$ contiene todos los enteros positivos.

Por supuesto, dado que esta condición sólo es suficiente y no necesaria para $S$ para contener todos los enteros positivos, es posible que haya una prueba más fácil que no requiera resolver este problema abierto. Sin embargo, no he podido encontrar ninguna aproximación prometedora que no acabe reduciéndose a una cuestión de este tipo.

---

Bien, aquí está la prueba de la supuesta equivalencia. Escribamos $C=\log_z x$ .

En primer lugar, supongamos que toda secuencia finita de dígitos aparece en la base $y$ ampliación de $C$ y que $N$ sea cualquier número entero positivo. Elija los enteros $m$ y $k$ tal que $$\log_z N<\frac{m}{y^k}<\frac{m+1}{y^k}<\log_z(N+1).$$ Que la cadena $s$ sea la base $y$ ampliación de $m$ con suficientes ceros iniciales añadidos (si es necesario) para que $s$ tiene una longitud mínima de $k$ . Esta cadena $s$ aparece infinitas veces en la base $y$ ampliación de $C$ (ya que toda cadena finita que lo contiene aparece en algún lugar), y en particular aparece en algún lugar a partir del punto decimal. Esto significa que existen enteros positivos $a$ y $b$ tal que la base $y$ ampliación de $y^aC-b$ es idéntica a la de $\frac{m}{y^k}$ hasta el $k$ dígito después del punto decimal. Es decir, $$\frac{m}{y^k}\leq y^aC-b<\frac{m+1}{y^k}.$$ Por nuestra elección de $m$ y $k$ Esto implica que $\lfloor z^{y^aC-b}\rfloor=N$ . Pero $$z^{y^aC-b}=\frac{z^{y^a\log_z x}}{z^b}=\frac{x^{y^a}}{z^b},$$ así que esto es exactamente lo que queríamos.

A la inversa, supongamos que cada $N$ puede escribirse de esta forma, y dejar que $s$ sea una cadena finita de base $y$ dígitos. Obsérvese que existe un número entero positivo $N$ tal que la base $y$ ampliaciones de $\log_z N$ y $\log_z(N+1)$ después del punto decimal, ambos comienzan con $s$ . (Esto es cierto porque la diferencia entre $\log_z N$ y $\log_z(N+1)$ va a $0$ como $N$ se hace grande). Por hipótesis, existen enteros positivos $a$ y $b$ tal que $$N=\bigg\lfloor \frac{x^{y^a}}{z^b}\bigg\rfloor.$$ Esto significa que $$\log_z \frac{x^{y^a}}{z^b}=y^aC-b$$ está entre $\log_z N$ y $\log_z(N+1)$ y, por tanto, su base $y$ la expansión comienza con $s$ después del punto decimal. Esto implica que la cadena $s$ aparece en la base $y$ ampliación de $C$ (a partir de $a$ dígitos después del punto decimal), según se desee.

Answer 2

Utilizaré $[x]$ para el piso de $x\ge 0$ .

Para un verdadero $x\ge0$ y un número entero $b$ tenemos $[[x/3^b]/3] = [x/3^{b+1}]$ .

Por tanto, basta con demostrar que cada número entero $N\ge 2$ puede escribirse de la forma $$ N = \left[\frac {2^{2^a}}{3^b}\right] \ ,$$ para números naturales adecuados $a,b$ . Esta relación anterior es equivalente a la doble desigualdad: $$ N \le \frac {2^{2^a}}{3^b}< N+1\ , $$ que sucesivamente replanteamos de forma equivalente: $$ \log N \le 2^a\log 2- b \log 3 < \log(N+1)\ , $$ $$ \underbrace{\frac {\log N}{\log 3}}_{=:U} \ \le \ 2^a \underbrace{\frac {\log 2}{\log 3}}_{=:s}- b \ < \ \underbrace{\frac{\log(N+1)}{\log 3}}_{=:V}\ . $$ Dejemos que $T$ sea el "toro" (o el "círculo") $\mathbb R/\mathbb Z$ . La multiplicación por $2$ mapa de $\mathbb R$ induce un mapa, también llamado "multiplicación por $2$ " en lo siguiente, $T=\mathbb R/\mathbb Z\overset {\cong}{\to} \mathbb R/2\mathbb Z\to \mathbb R/\mathbb Z=T$ .

El intervalo real $I=(U, V)$ se proyecta a un intervalo $\bar I$ en el toroide $T$ . (Si no hay ningún número entero en $I$ entonces podemos utilizar sin abuso y/o peligro de confusión la "misma notación" $(U,V)$ ... Pero usamos $(U,V)_T:=\bar I$ para tener una pequeña distinción pedante).

Porque $s\not\in \mathbb Q$ (por factorización única en $\mathbb Z$ (una potencia de dos no es una potencia de tres,) el mapa de duplicación ergódica $T\overset{2}{\to} T$ aplicada recursivamente desde el punto de partida $s$ da lugar a una secuencia $(T^as)_{a\in\mathbb N}$ .

Si podemos demostrar que esta secuencia es densa en $T$ entonces existe un $a$ para que $T^a s \in (U,V)_T$ . Esto determina el correspondiente $b$ y la solución.

El mapa de duplicación puede entenderse mejor si escribimos $s$ en representación binaria, $$ s = 0, s_0s_1s_2s_3\dots\ . $$ Los primeros dígitos son los del siguiente fragmento de código:

sage: floor( log(2)/log(3) * 2^20).digits(base=2)[::-1]
[1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1]
sage: print "%.11f" % s
0.63092975357
sage: print "%.11f" % (2^-1 + 2^-3 + 2^-8 + 2^-9 + 2^-14 + 2^-17 + 2^-20 )
0.63092899323

El mapa de duplicación corresponde al desplazamiento $$(s_0, s_1, s_2, s_3,\dots) \to (s_1, s_2, s_3,\dots)\ .$$ La pregunta sigue siendo ahora: Si damos una secuencia finita de dígitos (ceros y/o unos, por ejemplo, los primeros dígitos de $U$ , tomada con la aproximación $(V-U)/2$ ), ¿aparece esta secuencia "en algún lugar" de la representación binaria de nuestro $s$ (en lugares consecutivos)?

Esto es demasiada ergodicidad para mí, tengo que poner una pausa aquí, el tiempo.

(El mapa de duplicación en $\mathbb R\mod 1$ es uno de los primeros ejemplos en cada exposición de sistemas dinámicos, el motor de búsqueda favorito mostrará muchos resultados).

---

Algún experimento:

Utilizando sage podemos implementar lo anterior para los primeros enteros $>2$ . El código es:

R = RealField(100000)

def T(x):
    return (2*x).frac()

for N in [3..64]:

    U = ( R(log(N  )) / R(log(3)) ).frac()
    V = ( R(log(N+1)) / R(log(3)) ).frac()

    s = R(log(2)) / R(log(3))

    if V < U:
        if 1-U > V:    U, V = U, R(1)
        else      :    U, V = R(0), V

    a = 0
    while not( a > N and U <= s and s < V ) and a < 500:
        a += 1
        s = T(s)

    b = floor( ( R(2)^a * log(R(2)) - log(N) ) / log(R(3)) )
    print ( "%s = [ 2^(2^%s) / 3^%s ]"
            % ( floor( exp( R(2)^a * log(R(2)) - b * log(R(3)) ) ), a, b ) )

Resultados:

3 = [ 2^(2^4) / 3^9 ]
4 = [ 2^(2^6) / 3^39 ]
5 = [ 2^(2^8) / 3^160 ]
6 = [ 2^(2^7) / 3^79 ]
7 = [ 2^(2^20) / 3^661576 ]
8 = [ 2^(2^19) / 3^330787 ]
9 = [ 2^(2^10) / 3^644 ]
10 = [ 2^(2^11) / 3^1290 ]
11 = [ 2^(2^17) / 3^82695 ]
12 = [ 2^(2^15) / 3^20672 ]
13 = [ 2^(2^23) / 3^5292620 ]
14 = [ 2^(2^18) / 3^165392 ]
15 = [ 2^(2^25) / 3^21170487 ]
16 = [ 2^(2^69) / 3^372435190163881929150 ]
17 = [ 2^(2^21) / 3^1323153 ]
18 = [ 2^(2^32) / 3^2709822655 ]
19 = [ 2^(2^80) / 3^762747269455630190904380 ]
20 = [ 2^(2^24) / 3^10585242 ]
21 = [ 2^(2^95) / 3^24993702525522090095554811833 ]
22 = [ 2^(2^31) / 3^1354911326 ]
23 = [ 2^(2^60) / 3^727412480788831890 ]
24 = [ 2^(2^48) / 3^177590937692583 ]
25 = [ 2^(2^47) / 3^88795468846290 ]
26 = [ 2^(2^74) / 3^11917926085244221732878 ]
27 = [ 2^(2^63) / 3^5819299846310655140 ]
28 = [ 2^(2^65) / 3^23277199385242620569 ]
29 = [ 2^(2^66) / 3^46554398770485241141 ]
30 = [ 2^(2^71) / 3^1489740760655527716607 ]
31 = [ 2^(2^67) / 3^93108797540970482285 ]
32 = [ 2^(2^53) / 3^5682910006162746 ]
33 = [ 2^(2^37) / 3^86714325042 ]
34 = [ 2^(2^58) / 3^181853120197207970 ]
35 = [ 2^(2^45) / 3^22198867211570 ]
36 = [ 2^(2^68) / 3^186217595081940964573 ]
37 = [ 2^(2^43) / 3^5549716802890 ]
38 = [ 2^(2^41) / 3^1387429200720 ]
39 = [ 2^(2^79) / 3^381373634727815095452188 ]
40 = [ 2^(2^81) / 3^1525494538911260381808762 ]
41 = [ 2^(2^161) / 3^1844209735770936274870220836597588246728413581752 ]
42 = [ 2^(2^158) / 3^230526216971367034358777604574698530841051697716 ]
43 = [ 2^(2^59) / 3^363706240394415943 ]
44 = [ 2^(2^154) / 3^14407888560710439647423600285918658177565731104 ]
45 = [ 2^(2^46) / 3^44397734423143 ]
46 = [ 2^(2^62) / 3^2909649923155327568 ]
47 = [ 2^(2^114) / 3^13103898309700925572018241187760081 ]
48 = [ 2^(2^69) / 3^372435190163881929149 ]
49 = [ 2^(2^148) / 3^225123258761100619490993754467479034024464545 ]
50 = [ 2^(2^96) / 3^49987405051044180191109623668 ]
51 = [ 2^(2^52) / 3^2841455003081371 ]
52 = [ 2^(2^57) / 3^90926560098603983 ]
53 = [ 2^(2^119) / 3^419324745910429618304583718008322701 ]
54 = [ 2^(2^109) / 3^409496822178153924125570037117499 ]
55 = [ 2^(2^107) / 3^102374205544538481031392509279372 ]
56 = [ 2^(2^78) / 3^190686817363907547726092 ]
57 = [ 2^(2^80) / 3^762747269455630190904379 ]
58 = [ 2^(2^157) / 3^115263108485683517179388802287349265420525848856 ]
59 = [ 2^(2^191) / 3^1980205125525243161966916284371100358043128831900396755423 ]
60 = [ 2^(2^82) / 3^3050989077822520763617527 ]
61 = [ 2^(2^350) / 3^1447036516603094510357950642070627639392595028537243195306937714466705813009580996918246268676282514900260 ]
62 = [ 2^(2^162) / 3^3688419471541872549740441673195176493456827163507 ]
63 = [ 2^(2^95) / 3^24993702525522090095554811832 ]
64 = [ 2^(2^231) / 3^2177258560896638515992457337687990263124256995974882712059461472653787 ]

(Por supuesto, para $4, 16, 64$ tenemos mejores soluciones. Todos los cálculos anteriores son no exacto, ya que sage no acepta exponentes demasiado grandes. Así que el signo igual debe ser reemplazado por $\approx$ . (Pero la mejor aproximación ASCII para este signo es el signo de igualdad, lo siento).