Can a de Bruijn cycle be populated by integers?

General
1

Every parity sequence like 11010 (up-up-down-up-down) represents a rational Collatz cycle – only one rational number m returns to itself following that sequence.

If the rational number m is also an integer, then the sequence is a Collatz counterexample.

Sequences with 1s before 0s, like 1111111100000 (circuits), never have integer m.

Sequences with 1s spread evenly among 0s, like 1101101011010 (high cycles), never have integer m.

One reason covers both circuits and high cycles, which is they always have a longest repeated substring (LRS) that’s at least half the length k. (LRS includes wrap-around sequences.)

The hardest sequences from this LRS-point of view are the de Bruijn sequences, like 11101000, where there’s no long LRS.

Standard de Bruijn sequences have length k=2^n, with x=2^{n-1} ones, so k=2x.

They are designed to have very low |LRS|= \log_2 k - 1.

For example, 11101000 has LRS of length 2, because no 3-gram repeats itself.

In fact, every distinct subsequence of length n=\log_2 k (000, 001, \ldots, 111) appears exactly once in a de Bruijn sequence.

There are two de Bruijn cycles of length 8 (11101000 and 11100010), sixteen of length 16, and 2048 of length 32.

Can we show that none of these cycles have integer m?

I can’t, but maybe someone can?

Well, technically, I can – because no cycle with k=2x is an integer cycle, as these two posts point out.

But that doesn’t take advantage of the “de Bruijn-ness” of the cycle – just the fact that k=2x.

The reason we want to use “de Bruijn-ness” is to have a hope of covering “deBruijn-like” cycles, where k \approx x \log_2 3 but still guarantee no repetition of any subsequence of length greater than c \lceil \log_2 k \rceil. Almost all sequences have an LRS of log(k)-ish length.

One interesting feature of de Bruijn cycles is that every member of a cycle v has a distinct residue (mod k).

For example, the de Bruijn cycle 11101000 goes \frac{197}{13}, \frac{383}{13}, \frac{662}{13}, \frac{331}{13}, \frac{584}{13}, \frac{292}{13}, \frac{146}{13}, \frac{73}{13}, \frac{197}{13}, where the numerators are congruent to 5, 7, 6, 3, 0, 4, 2, and 1 (mod 8), respectively.

Maybe this can be leveraged.

(Note de Bruijn cycle members are not necessarily pairwise co-prime, since sometimes they share a factor with 2^k-3^x.)

So, is there something about de Bruijn cycle (shapes) that tells us none of them can be populated by integers, as is known to be the case for circuit (shapes)?

2

Talking about height-2 tricots where affine factors are odd, which is the case for reduced Collatz:

There is a bijection between the residue mod 2^n of a number and the n first terms of its trajectory: in a cycle where the LRS is of length L, all numbers will have different residues mod 2^{L}. In the case of De Bruijn, L=log_2(k), so the residues are different mod k.

If we are talking about bruijnish cycles, the residues are still going to be different mod 2^L but this time we can’t simplify it to k (as k<2^L)

The way I would explore it:
Consider a potential integer bruijnish cycle, of length l, of LRS L (so l<2^L but not by a lot). Let’s assume it contains only “big” integers (the smallest being orders of magnitudes bigger than l)
Then we can approximate the whole cycle as a multiplication by 3^a/2^l (where a is the number of 1s in our cycle). This cycle would then require that a is close to l*log_3(2), which could contradict being bruijnish requiring that a is close to l/2.

3

@Failix thanks – I see this holds for all height-2 tricots with odd affine factors. And for 3n+1 , the members of a de Bruijn cycle v of length k=8 have parity vectors 000…, 001…, 010…, etc. Each member is valued \cfrac{\beta(v_{rot})}{2^k-3^x}, where \beta(000y_0) = 8 \beta(y_0), while \beta(001y_1) = 8 \beta(y_1) + (3^{x-1}4) , etc.

Your suggestion and the summary post here work very well for ruling out any integer cycle with k \approx 2x (where x = total odds), whether de Bruijinish or not.

I can see your idea is to push away from k \approx 2x first, then afterward exploit the low-LRS-length property of de Bruijnish cycles … I’ll keep wondering about that.

1 Like
4

How many rational cycles of length k have members whose numerators are all distinct mod k?

k # of cycles w/distinct numerators mod k
2 1
4 1
8 2
10 2
14 6
16 16
20 32
… …

Here’s one of the six length 14 cycles: 11110100010010.

Cycle members are: 39748/14197, 19874/14197, 9937/14197, 22004/14197, 11002/14197, 5501/14197, 15350/14197, 7675/14197, 18611/14197, 35015/14197, 59621/14197, 96530/14197, 48265/14197, 79496/14197.

Numerators mod 14 are: 2, 8, 11, 10, 12, 13, 6, 3, 5, 1, 9, 0, 7, 4.

(The 16 cycles of length 16 are the de Bruijn cycles.)

5

Consider all circular strings of length k with longest repeated substring (LRS) of length a=\lfloor \log_2 k \rfloor.

What’s the maximum weight (number of ones) of any such string, in terms of k?

Any stringologists know any bounds or formulas?

Of more interest to Collatz, what’s the maximum \beta(v)? (a.k.a., the largest member of any rational cycle of length k with short LRS)

k sample weight-maximizing v weight/k \beta(v)
3 011 66.67 10
4 0111 75.00 38
5 00111 60.00 76
6 000111 50.00 152
7 0010111 57.14 412
8 00101111 62.50 1364
9 001101111 66.67 3700
10 0001101111 60.00 7400
11 00110101111 63.64 15772
12 000110101111 58.33 31544
13 0001001101111 53.85 65032
14 00001001101111 50.00 130064
15 000101001101111 53.33 277624
16 0011101011011111 68.75 1381772
17 00011101011011111 64.71 2763544
18 000101100111011111 61.11 5614568
19 0010110100111011111 63.16 11307868
20 00010101100111011111 60.00 23875448
21 000110101100111011111 61.90 52002424
22 0000110101100111011111 59.09 104004848
23 00000110101100111011111 56.52 208009696
24 000110100101100111011111 58.33 391927400
25 0000110100101100111011111 56.00 783854800
26 00011010010101100111011111 57.69 1625813816
27 000011010010101100111011111 55.56 3251627632
28 0000101000110101100111011111 53.57 6834874448
6

Unless I am misunderstanding something, that’s the same as asking how many distinct rational cycles of length (strictly) k exist at all (because of the unicity of trajectories).

I had a formula for it at some point, there is a funny Moebius inversion to do, but the result is still relatively complicated.

From what I remember (there may be some calculation errors):

  • let’s note s(k) the number of binary sequences of length k that doesn’t repeat themselves.
  • There are 2^k possible binary sequences of length k (including those that repeat)
  • For every d that divides k, you can associate the s(d) binary sequences of length d that doesn’t repeat with s(d) sequences of length k that repeat k/d times.
  • Thus, s(k) = 2^k - \sum_{d|k}{s(d)}, or 2^k-s(k) = \sum_{d|k}{s(d)}.

Through Moebius inversion we get that s(k) = \sum_{d|k}{\mu(d)(2^{k/d}-s(k/d))}
(where \mu is the moebius function (Möbius function - Wikipedia))

7

I mean distinct mod k, not mod 2^k …

8

Here was my misunderstanding then.
I gave it another look but I’m not sure it’s going anywhere:

So, we are looking for rational cycles. The rational that corresponds to the cycle \alpha_0\alpha_1...\alpha_{k-1} is
r_0 = \frac {\sum_{i=0}^{k-1}{\alpha_i2^i3^{\sum_{j=i+1}^{k-1}{\alpha_j}}(3^{\alpha_i}-2)}}{3^S-2^k}
where S is the sum of the \alpha_i.

Let’s say by convention that \alpha_{k+i}=\alpha_i, so we can note that any rational in the same cycle can be noted
r_n = \frac {\sum_{i=0}^{k-1}{\alpha_{i+n}2^i3^{\sum_{j=i+1}^{k-1}{\alpha_{j+n}}}(3^{\alpha_{i+n}}-2)}}{3^S-2^k}
with n between 0 and k-1.

r_n-r_m = \frac {\sum_{i=0}^{k-1}{\alpha_{i+n}2^i3^{\sum_{j=i+1}^{k-1}{\alpha_{j+n}}}(3^{\alpha_{i+n}}-2)}}{3^S-2^k} - \frac {\sum_{i=0}^{k-1}{\alpha_{i+m}2^i3^{\sum_{j=i+1}^{k-1}{\alpha_{j+m}}}(3^{\alpha_{i+m}}-2)}}{3^S-2^k}
= \frac {\sum_{i=n}^{k-1+n}{\alpha_{i}2^i3^{\sum_{j=i+1-n}^{k-1}{\alpha_{j+n}}}(3^{\alpha_{i}}-2)} - \sum_{i=m}^{k-1+m}{\alpha_{i}2^i3^{\sum_{j=i+1-m}^{k-1}{\alpha_{j+m}}}(3^{\alpha_{i}}-2)}} {3^S-2^k}
(let’s assume n<m)
= \frac {\sum_{i=n}^{m-1}{\alpha_{i}2^i3^{\sum_{j=i+1-n}^{k-1}{\alpha_{j+n}}}(3^{\alpha_{i}}-2)} - \sum_{i=k+n}^{k-1+m}{\alpha_{i}2^i3^{\sum_{j=i+1-m}^{k-1}{\alpha_{j+m}}}(3^{\alpha_{i}}-2)} + \sum_{i=m}^{k-1+n}{\alpha_{i}2^i(3^{\sum_{j=i+1-n}^{k-1}{\alpha_{j+n}}} - 3^{\sum_{j=i+1-m}^{k-1}{\alpha_{j+m}}})(3^{\alpha_{i}}-2)}} {3^S-2^k}
= \frac {\sum_{i=n}^{m-1}{\alpha_{i}2^i3^{\sum_{j=i+1-n}^{k-1}{\alpha_{j+n}}}(3^{\alpha_{i}}-2)} - \sum_{i=n}^{m-1}{\alpha_{i+k}2^{i+k}3^{\sum_{j=i+k+1-m}^{k-1}{\alpha_{j+m}}}(3^{\alpha_{i+k}}-2)} + \sum_{i=m}^{k-1+n}{\alpha_{i}2^i(3^{\sum_{j=i+1}^{k-1+n}{\alpha_{j}}} - 3^{\sum_{j=i+1}^{k-1+m}{\alpha_{j}}})(3^{\alpha_{i}}-2)}} {3^S-2^k}
= \frac {\sum_{i=n}^{m-1}{\alpha_{i}2^i3^{\sum_{j=i+1-n}^{k-1}{\alpha_{j+n}}}(3^{\alpha_{i}}-2)} - \sum_{i=n}^{m-1}{\alpha_{i}2^{i+k}3^{\sum_{j=i+k+1-m}^{k-1}{\alpha_{j+m}}}(3^{\alpha_{i}}-2)} - \sum_{i=m}^{k-1+n}{\alpha_{i}2^i(3^{\sum_{j=k+n}^{k+m-1}{\alpha_{j}}})(3^{\alpha_{i}}-2)}} {3^S-2^k}
= \frac {\sum_{i=n}^{m-1}{\alpha_{i}2^i(3^{\alpha_{i}}-2)(3^{\sum_{j=i+1-n}^{k-1}{\alpha_{j+n}}}}-2^k3^{\sum_{j=i+k+1-m}^{k-1}{\alpha_{j+m}}}) - \sum_{i=m}^{k-1+n}{\alpha_{i}2^i(3^{\sum_{j=n}^{m-1}{\alpha_{j}}})(3^{\alpha_{i}}-2)}} {3^S-2^k}
= \frac {\sum_{i=n}^{m-1}{\alpha_{i}2^i(3^{\alpha_{i}}-2)(3^{\sum_{j=i+1}^{k+n-1}{\alpha_{j}}}}-2^k3^{\sum_{j=i+1}^{m-1}{\alpha_{j}}}) - \sum_{i=m}^{k-1+n}{\alpha_{i}2^i(3^{\sum_{j=n}^{m-1}{\alpha_{j}}})(3^{\alpha_{i}}-2)}} {3^S-2^k}
= \frac {\sum_{i=n}^{m-1}{\alpha_{i}2^i3^{\sum_{j=i+1}^{m-1}{\alpha_{j}}}(3^{\alpha_{i}}-2)(3^{\sum_{j=m}^{k+n-1}{\alpha_{j}}}}-2^k) - \sum_{i=m}^{k-1+n}{\alpha_{i}2^i(3^{\sum_{j=n}^{m-1}{\alpha_{j}}})(3^{\alpha_{i}}-2)}} {3^S-2^k}

So, for your condition to be filled you need the numerator of that thing to never (for any n and m different from each other) be a multiple of k. Not sure it helps.

1 Like