All integer cycles must have k=ceil(x log_2(3))?

General
1

Since we are only interested in positive cycles, we know that 2^k>3^x, and if we show that 2^k<2\cdot3^x than we have k=\lceil x \log_23\rceil. One way would be to show that the smallest integer element of the cycle a_0>\frac{x}{3} and use this.

The high cycle staircase is constructed with the rule that we “climb” only if \frac{y_{i}}{2}< y_0 (all y_j\in \mathbb{Q}[(2)]) so that y_{max}=\frac{3y_i+1}{2}<3y_0+\frac{1}{2} which implies that in an integer high cycle (a_0=y_0), x<a_{max}\leqslant3a_0 so we have k=\lceil x \log_23\rceil

In a 1-cycle a_0=\frac{3^{x}a_0+(3^x-2^x)}{2^{k}} we already know that 2^k-3^x\leqslant (2^k-3^x)a_0=3^x-2^x<3^x or 2^k<2\cdot3^x, and in an integer cycle we can also use the fact that a_0\geqslant 2^x-1>\frac{x}{3}.

Note that any integer cycle starting with at least j>\log_2(\frac{x}{3}+1) consecutive “1” in the parity vector of its a_0 can use a_0\geqslant 2^j-1>\frac{x}{3} to show that k=\lceil x \log_23\rceil

If integer high cycles and 1-cycles must have k=\lceil x \log_23\rceil can’t we use this fact to show that all (intermediate) integer cycles have k=\lceil x \log_23\rceil ? And since both types were proven to not exist, can’t we exploit this for those intermediate cycles ?

1 Like
2

This is my first time hearing about the bound a_0 > \frac{x}{3} and it’s really interesting. It seems that the 1-cycle and the high cycle are especially restrictive, and that the least restrictive cases are the ones in the middle. However, 2^j-1>\frac{x}{3} is way overkill for circuits and covers tons of cycle shapes - if not with initial consecutive odd steps like you mentioned, then with another run of consecutive odd steps that occurs not too much higher than a_0. In fact, consecutive runs of any repeating pattern have the potential to raise a_0 over \frac{x}{3}, and even the worst case cycle shapes must have at least some repetition. I would say “if integers then k = \lceil x \log_2{3} \rceil” seems easier to satisfy than “no integers” for a given class of cycle shapes, but it’s interesting how close the high cycle a_0 cuts the \frac{x}{3} bound.

3

@Collag3n It’s a very interesting idea that proving l(v) = \lceil s(v) \log_2 3 \rceil for an integer cycle is a “way station” on the road to proving v can’t be an integer cycle at all.

For example, above you’ve got a condition where there are \log_2 (s(v)/3 + 1) ones at the start of a_0, the smallest member of v … and that’s enough to require l(v) = \lceil s(v) \log_2 3 \rceil.

If we strengthen that to 16 \log_2 s(v) initial ones, we can rule out the integer cycle altogether.

Let v = 1^y w be a parity vector of length l(v) with s(v) > 13 and y > 16 \log_2 s(v).

Let a_0 be the rational start number that, following v, returns to a_0.

Critically, a_0 must also be the smallest member of its cycle.

Then, a_0 is not an integer.

\beta(v) = 3^{s(w)}(3^y-2^y) + 2^y \beta(w)
= 3^{s(v)} - 2^y 3^{s(w)} + 2^y \beta(w)

If a_0 = \cfrac{\beta(v)}{2^{l(v)}-3^{s(v)}} is an integer, then so is

\cfrac{\beta(v)}{2^{l(v)}-3^{s(v)}} + 1

= \cfrac{\beta(v)+2^{l(v)}-3^{s(v)}}{2^{l(v)}-3^{s(v)}}

= \cfrac{2^{l(v)} - 2^y 3^{s(w)} + 2^y \beta(w)}{2^{l(v)}-3^{s(v)}}

= \cfrac{2^y \left(2^{l(w)} - 3^{s(w)} + \beta(w)\right)}{2^{l(v)}-3^{s(v)}}

and therefore so is

\cfrac{2^{l(w)} - 3^{s(w)} + \beta(w)}{2^{l(v)}-3^{s(v)}}

However, this quantity will be less than 1, provided the just-canceled 2^y is large enough.

\cfrac{2^{l(w)} - 3^{s(w)} + \beta(w)}{2^{l(v)}-3^{s(v)}}

= \cfrac{\frac{\beta(v)}{2^{l(v)}-3^{s(v)}}+1}{2^y}\ \ \ \text{(from equality above)}

= \cfrac{1}{2^y} \left[ \cfrac{\beta(v)}{2^{l(v)}-3^{s(v)}}+1 \right]

< \cfrac{1}{2^y} \left[ \cfrac{3^{s(v)} \frac{s(v)}{3}}{2^{l(v)}-3^{s(v)}}+1 \right] (from this bound)

<\cfrac{1}{2^y} \left[ \cfrac{3^{s(v)} \frac{s(v)}{3}}{\frac{3^{s(v)}}{250\ s(v)^{13.3}}}+1 \right] \text{(from Rhin's bound)}

= \cfrac{1}{2^y} \left[ 84\ s(v)^{14.3} + 1 \right]

< \cfrac{1}{2^{16 \log s(v)}} \left[ 84\ s(v)^{14.3} + 1 \right] \ \text{because}\ \ y > 16 \log s(v)

= \cfrac{1}{s(v)^{16}} \left[ 84\ s(v)^{14.3} + 1 \right]

= 84\ s(v)^{-1.7} + s(v)^{-16}

< 1 … for all s(v)>13, ruling out an integer cycle.

At least, I think that’s right.

4

Sounds right. I just wonder how you got \frac{3^{s(v)}}{250\ s(v)^{13.3}}coming from here?
Shouldn’t this be more something like \frac{3^{s(v)}}{457\ s(v)^{13.3}}?

5

For sure, you are right. I got that constant wrong at some point and can’t seem to shake it!

6

For a_0 to maintain its lowest-member status, maybe it needs a long initial 1-run to launch it into space? It certainly has to start with at least two 1s, otherwise it will go below itself right away, and not be the minimal member of the cycle after all.

There are plenty of exceptions, though, like 1101111101000, which is the \beta minimal rotation.

Here’s a table with LRS length (in columns), and initial 1-run length of minimal \beta rotation (in rows), for the 312k+ distinct cycles with l=27, s=17.

The first column gives (for example) a histogram of initial 1-run lengths among the cycles with minimal LRS (“deBruijn-like cycles”). Points for spotting the circuit and the high cycle!

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2 422 8234 16566 13240 9040 5180 2610 1366 707 293 191 99 44 20 16 4 3 2 2 0 1
3 618 7955 15321 14929 8673 4896 2768 1399 673 407 216 84 56 23 13 4 3 1 1 0 0
4 618 8016 16200 13959 8981 4884 2642 1320 722 366 145 99 52 19 12 2 0 2 0 1 0
5 452 6323 13749 11403 7094 3748 1987 921 464 252 94 42 59 14 3 0 1 0 1 0 0
6 946 6841 9952 7735 4822 2459 1267 616 284 126 66 26 17 17 0 0 0 0 0 0 0
7 0 7327 6840 4449 2561 1359 647 293 156 42 23 33 1 0 10 0 0 0 0 0 0
8 0 0 9999 2517 1290 644 305 109 36 31 13 2 9 0 1 4 0 0 0 0 0
9 0 0 0 7723 620 291 106 53 13 8 9 2 0 5 0 0 1 0 0 0 0
10 0 0 0 0 4635 127 32 14 14 2 0 4 0 0 1 0 0 0 0 0 0
11 0 0 0 0 0 2393 17 12 2 4 0 0 1 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 1100 5 0 0 1 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 0 446 2 0 0 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 156 0 0 0 0 0 0 0 0 0 0 0 0
15 0 0 0 0 0 0 0 0 0 44 0 0 0 0 0 0 0 0 0 0 0
16 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0
17 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

A general question is how many of the cycles are below some O(\log s) cutoff, to be brutally ruled out as integer cycles.

In other words, while almost no (l, s)-vectors start with a long 1-run, maybe a larger proportion of minimal-\beta vectors do.

7

I tried to formalize the idea from the post k<457a_0 based on “roots” to catch more cycles (from the 1-cycle side and from the high cycle side) but it seems I overlooked the fact that some “roots” can go as low as 2a_0/3.

I couldn’t do better then k<304a_0 (sorry, I used the notations of my previous paper)

From that we can say that integer cycles starting with at least j>\log_2(\frac{x}{304}+1) consecutive “1” in the parity vector of its a_0 can use a_0\geqslant 2^j-1>\frac{x}{304} to show that k=\lceil x \log_23\rceil (1-cycle side), and x<a_{max}\leqslant304a_0 also have k=\lceil x \log_23\rceil (high cycle side), something like using a_{max}<(\frac{3^x}{2^x})a_0<304a_0 so that consecutive “climbs” can be more than 2

1 Like
8

Updated the paper k<304a_0 (no big changes, but I had to mention I was only talking about positive integer cycles).

2 Likes