12
$\begingroup$

Here is a problem that I came up with that has been bothering me for a while, and I haven't been able to solve it.

Let $S$ be the set defined by the following rules:

  • $2\in S$.
  • Define the functions $\alpha$ and $\beta$ as $$\alpha(n)=n^2$$ $$\beta(n)=\lfloor n/3\rfloor$$ If $n\in S$, then $\alpha(n)\in S$ and $\beta(n)\in S$.
  • If the previous two rules do not imply that a number $n$ is in $S$, then $n\notin S$.

QUESTION: What numbers are in $S$?

So far, I've verified that every positive integer from $1$ to $14$ is in $S$, since I've found "composition sequences" of $\alpha$ and $\beta$ that, when applied to $2$, yield each of those numbers. For example, $$3=(\beta^{\circ 4}\circ\alpha^{\circ 3})(2)$$ Things get a little crazy when I get to $n=6$: $$6=(\beta^{\circ 10}\circ\alpha^{\circ 2}\circ \beta\circ\alpha^{\circ 2})(2)$$ ...and even crazier at $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)$$ Any ideas how to prove (or disprove) that any positive integer can be reached?

NOTE: It is true that all positive integers are in $S$ if (not iff) the following is true:

Blockquote For any positive integer $N$, there exist positive integers $a,b$ such that $$N=\bigg\lfloor \frac{2^{2^a}}{3^b}\bigg\rfloor$$

If someone figures out how to prove this, then we're done... if it's false, then there remains some work to be done.

$\endgroup$
  • 1
    $\begingroup$ Your final question is closely related to the binary expansion of $\log_2 3$ (it is equivalent to every finite sequence of binary digits appearing somewhere in it). $\endgroup$ – Eric Wofsey Apr 21 '18 at 23:24
  • $\begingroup$ @EricWofsey ...which is equivalent to $\log_2(3)$ being a normal number, right? $\endgroup$ – Franklin Pezzuti Dyer Apr 21 '18 at 23:24
  • 1
    $\begingroup$ No, that is weaker than normality, but it is related. $\endgroup$ – Eric Wofsey Apr 21 '18 at 23:26
  • $\begingroup$ Er, sorry, it's the binary expansion of $1/\log_2 3$, not the binary expansion of $\log_2 3$. $\endgroup$ – Eric Wofsey Apr 21 '18 at 23:30
  • 1
    $\begingroup$ Anyways, my understanding is that this is the sort of question whose answer is almost certainly yes, but also no one has any idea how to answer it. (But I might be wrong about the latter.) $\endgroup$ – Eric Wofsey Apr 21 '18 at 23:36
4
+75
$\begingroup$

I don't know how to answer this, but let me elaborate on my comments about your proposed proof strategy. The punchline is that it is very likely that $S$ does contain all positive integers via your strategy, but it is an open problem to prove this.

As you say, a sufficient condition for $S$ to contain a positive integer $N$ is that $N$ can be written in the form $$N=\bigg\lfloor \frac{2^{2^a}}{3^b}\bigg\rfloor.$$ More generally, if you modify your definition of $S$ to start with $x\in S$ and modify your functions to $\alpha(n)=n^y$ and $\beta(n)=\lfloor n/z\rfloor$ for some positive integers $x,y,$ and $z$, then a sufficient condition for $S$ to contain $N$ is that $N$ can be written in the form $$N=\bigg\lfloor \frac{x^{y^a}}{z^b}\bigg\rfloor.$$

I now claim that this is possible for all positive integers $N$ iff every finite sequence of digits appears in the base $y$ expansion of $\log_z x$. So, in your case, that would be the binary expansion of $\log_3 2$. The proof is basically "take $\log_z$ of everything"; I've written up the details below.

Now, the bad news is that questions like this are typically very hard to answer: if you pick some specific nicely defined irrational number, it is usually very difficult to say much about its base expansions. In particular, I'm pretty sure that for all positive integers $x,y,$ and $z$ for which $\log_z x$ is irrational, it is an open problem whether the base $y$ expansion of $\log_z x$ contains all finite sequences.

On the other hand, if you pick a random number (uniformly from some interval), then with probability $1$ it will contain every finite sequence in every base. So it is considered extremely likely that $\log_z x$ contains every finite sequence in base $y$; it would be an amazing discovery if it didn't. In particular, this means it is extremely likely that your set $S$ contains all positive integers.

Of course, since this condition is only sufficient and not necessary for $S$ to contain all positive integers, it is possible that there is an easier proof which does not require solving this open problem. I haven't been able to find any promising approach that doesn't end up reducing to a question of this sort, though.


OK, now here's the proof of the claimed equivalence. Let's write $C=\log_z x$.

First, suppose every finite sequence of digits appears in the base $y$ expansion of $C$, and let $N$ be any positive integer. Choose integers $m$ and $k$ such that $$\log_z N<\frac{m}{y^k}<\frac{m+1}{y^k}<\log_z(N+1).$$ Let the string $s$ be the base $y$ expansion of $m$, with enough initial zeroes added (if necessary) so that $s$ has length at least $k$. This string $s$ appears infinitely many times in the base $y$ expansion of $C$ (since every finite string containing it appears somewhere), and in particular it appears somewhere starting after the decimal point. This means that there exist positive integers $a$ and $b$ such that the base $y$ expansion of $y^aC-b$ is identical to that of $\frac{m}{y^k}$ up to the $k$th digit after the decimal point. That is, $$\frac{m}{y^k}\leq y^aC-b<\frac{m+1}{y^k}.$$ By our choice of $m$ and $k$, this implies that $\lfloor z^{y^aC-b}\rfloor=N$. But $$z^{y^aC-b}=\frac{z^{y^a\log_z x}}{z^b}=\frac{x^{y^a}}{z^b},$$ so this is exactly what we wanted.

Conversely, suppose every $N$ can be written in this form, and let $s$ be a finite string of base $y$ digits. Note that there exists a positive integer $N$ such that the base $y$ expansions of $\log_z N$ and $\log_z(N+1)$ after the decimal point both start with $s$. (This is true because the difference between $\log_z N$ and $\log_z(N+1)$ goes to $0$ as $N$ gets large.) By hypothesis, there exist positive integers $a$ and $b$ such that $$N=\bigg\lfloor \frac{x^{y^a}}{z^b}\bigg\rfloor.$$ This means that $$\log_z \frac{x^{y^a}}{z^b}=y^aC-b$$ is between $\log_z N$ and $\log_z(N+1)$, and thus its base $y$ expansion starts with $s$ after the decimal point. This implies that the string $s$ appears in the base $y$ expansion of $C$ (starting $a$ digits after the decimal point), as desired.

$\endgroup$
1
$\begingroup$

I will use $[x]$ for the floor of $x\ge 0$.

For a real $x\ge0$ and an integer $b$ we have $[[x/3^b]/3] = [x/3^{b+1}]$.

So it is enough to show that each integer number $N\ge 2$ can be written in the form $$ N = \left[\frac {2^{2^a}}{3^b}\right] \ ,$$ for suitable natural numbers $a,b$. This relation above is equivalent to the double inequality: $$ N \le \frac {2^{2^a}}{3^b}< N+1\ , $$ that we successively restate equivalently: $$ \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}\ . $$ Let $T$ be the "torus" (or the "circle") $\mathbb R/\mathbb Z$. The multiplication by $2$ map from $\mathbb R$ induces a map, also called "multiplication by $2$" in the following, $T=\mathbb R/\mathbb Z\overset {\cong}{\to} \mathbb R/2\mathbb Z\to \mathbb R/\mathbb Z=T$.

The real interval $I=(U, V)$ projects to an interval $\bar I$ in the torus $T$. (If there is no integer in $I$, then we can use without abuse and/or danger of confusion the "same notation" $(U,V)$... But we use $(U,V)_T:=\bar I$ to have a small pedant distinction.)

Because $s\not\in \mathbb Q$, (by unique factorization in $\mathbb Z$, a power of two is not a power of three,) the ergodic doubling map $T\overset{2}{\to} T$, applied recursively from the starting point $s$, gives rise to a sequence $(T^as)_{a\in\mathbb N}$.

If we can show this sequence is dense in $T$, then there exists an $a$, so that $T^a s \in (U,V)_T$. This determines the corresponding $b$, and the solution.

The doubling map can be better understood if we write $s$ in binary representation, $$ s = 0, s_0s_1s_2s_3\dots\ . $$ The first digits are as in the following code snippet:

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

The doubling map corresponds to the shift $$(s_0, s_1, s_2, s_3,\dots) \to (s_1, s_2, s_3,\dots)\ .$$ The question remains now: If we give a finite sequence of digits (zeros and/or ones, e.g. the first digits of $U$, taken with the approximation $(V-U)/2$), does this sequence appear "somewhere" in the binary representation of our $s$ (on consecutive places)?

This is too much ergodicity for me, have to put a break here, time.

(The doubling map on $\mathbb R\mod 1$ is one of the first examples in each exposition of dynamical systems, the favorite search engine will exhibit many hits.)


Some experiment:

Using sage we can implement the above for the first few integers $>2$. The code is:

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 ) )

Results:

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 ]

(Of course, for $4, 16, 64$ we have better solutions. All the above computations are not exact, since sage does not accept too big exponents. So the equal sign should be replaced by $\approx$. (But the best ASCII approximation for this sign is the equal sign, sorry.))

$\endgroup$
  • $\begingroup$ Also, $3$ can be written simpler as $$\bigg\lfloor\frac{2^{2^3}}{3^4}\bigg\rfloor$$ $\endgroup$ – TheSimpliFire Apr 27 '18 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.