On another thread, I sorted through parity vectors with different LRSs, plotting which of them can be ruled out by the difference method, which rules out a cycle if the difference between two designated members is shown not to be an integer.
Below is the same thing if we sort(l, s)-vectors into m-cycle bins, for various m.
The circuit is a 1-cycle. A 2-cycle has two direction reversals (two 10 substrings of the circular string), such as 11{\color{red}10}001{\color{red}10}0. All the way up to (l-s)-cycles, which have no consecutive zeroes.
For each bin, we plot the most “diabolical” vector, the one with the largest min-odd-\beta-difference, or mobd(v).
As with LRS, we get an inverted-U shape, with cycles having the smallest and largest values of m being most amenable to falling “under the dashed line”, that is, ruled out as integer cycles.
In more concise math, we’re saying we can rule out an entire collection of vectors V as Collatz counterexample cycles if
\max_{v \in V} \min_{w, u \in rot(v)} \text{odd}(|\beta(w)-\beta(u)|) < \delta(v)
where
\beta(v) is the parity numerator, \delta(v) = 2^{l(v)} - 3^{s(v)}, l(v) is the length of v, s(v) is the weight, and
odd(n) removes the powers of 2 from n.
Collections we might investigate include
V = {v : l(LRS(v)) > 0.38\ l(v)}
V = {v : v is a 2-cycle}
V = {v : v is a deBruijn sequence}
It seems good enough for some V, but not good enough for others. Maybe there are extensions to the method that would improve it.
This method increasingly resembles a breakthrough. To see why, we could try to quantify the progress made.
The previous “classical” method was to compare \delta(v) for v \in V with {\rm MMB}(V) = \max_{v \in V} \min_{w \in rot(v)} \beta(w)
instead of {\rm MMOBD}(V) = \max_{v \in V} \min_{w, u \in rot(v)} \text{odd}(|\beta(w)-\beta(u)|).
The minimal \beta(w) in {\rm MMB}(V) is reached when starting from the smallest term of the cycle.
If we consider the set V of all vectors of length l and weight s for a fixed pair (l,s) such that s \simeq (\log_3 2)l, it is expected that {\rm MMB}(V) \simeq s 3^{s-1},
the worst case being the high cycle.
According to your figures, {\rm MMOBD}(V) lies somewhere between 3^s and 3^s/l, which is also what is expected for \delta when assuming an optimal lower bound at Roth’s level as recently discussed in this thread. It is getting really tight. And this could be sufficient to rule out cycles for an infinite set of lengths l.
But turning this numerical study into a rigorous proof will not be easy. So I like your proposition of settling the case of smaller collections V first.
Studying the case of de Bruijn parity vectors is questionable: They are easily ruled out as cycle candidates due to the trivial property that, for those vectors, l(v) = 2s(v). Hence, it can be shown that the smallest term is lower than 1 and cannot be an integer, unless we consider the trivial cyle whose parity vector 10 is the smallest de Bruijn sequence.
A more relevant collection to study might be the set V of those vectors v such that
s(v) = \lfloor (\log_3 2) \, l(v)\rfloor, so that \delta is minimal (and positive)
LRS(v) = k
there is no vector longer than v holding the two above properties (for maximality)
where k is a fixed integer.
For example, when k=2, we get two vectors of length 7 and weight 4 1110100 1110010
and their rotations.
In a sense, it is a generalization of de Bruijn sequences with an extra constraint on the ones-ratio s(v)/l(v), which has probably been studied already. References are welcome.
What about rotations? As you move along the cycle of rotations, the β value updates in a very Collatz-esque way (a two branch affine rule with the same word as its branch code and with an additive constant D(u)). That means “β on rotations” makes its own collatz-like orbit. You can do combinatorics on that system, or you could try to push the gcd idea (either every rotation’s β is divisible by D or none are).
You are right. And that’s why we consider \beta differences and LRS. As soon as LRS(v) is large, then we know that at least two \beta rotations will be sufficiently close (2-adically) to produce a large cancellation. In many cases, we end up with a numerator smaller than \delta(v) and we don’t have to worry on the exact value of the gcd.
Pushing the gcd idea is fine when studying a small number of cycle candidates, but when we embrace a huge number of them, a combinatorial approach is more amenable.
The title refers to necklaces (cyclic sequences) containing exactly once every binary words of length n and weight at most d (for density) with d \leq n (classical de Bruijn sequences corresponds to n=d). The full length is easy to express as a sum of binomial coefficients. The full weight of the sequence is also a function of n and d. In the paper, the focus is on finding efficient algorithms to generate this family of necklaces.
Not clear if this collection of vectors could match the desired definition when adjusting the value of d. Otherwise, this might be another interesting collection to investigate.
Probably we should consider the complement to get a minimal density instead of maximal.
When setting n=3 and d=2, we get the necklaces
0001011
0001101
which contain every words of length 3 except 111 upon rotation.
As @oros notes, the numbers in the last column are much smaller. The theoretical problem is to bound all the values in this table in terms of arbitrary l, s, m, |LRS|, etc. To a minor degree, this is already accomplished—for example, no matter what l and s are, the high cycle has a simple 1 in the last column. But particularly as l and s increase, the diabolical nature of these max’s becomes apparent. Even here, nature gives us the max 2-cycle 1111100001110, which isn’t necessarily something you might have guessed. Upper-bounding these max’s means wrangling nature’s diabolical … er … nature.
It is striking that the high cycle is both the black sheep in the penultimate column and the most favorable case in the last, when subtracting \beta values and canceling the powers of 2. A drastic change of category.
I think @mathkook 's method can be further improved by canceling out the powers of 3 as well, since \delta is coprime to 3.
For example, if I take your worst case for the set V of vectors v such that LRS(v)=4, which is v=0110111101010, by considering rotations u=1010011011110 and w=1111010100110, I find that \beta(w) - \beta(u) = 22302 = 2 \cdot 3^3 \cdot 7 \cdot 59.
Hence, by keeping only the part coprime to 6, I end up with the integer 7 \cdot 59 = 413, which seems to be minimal among all beta differences for this vector and smaller than 571. It is also the worst case for all cycles with l=13 and s=8 by this method. So it is the new “black sheep” for this length.
For the set V of 2-cycles, I find that the worst-case v=1111100001110 has 2 rotations u and w such that \beta(w) - \beta(u) =2 \cdot 3^2 \cdot 401
leading to 401 instead of 533. Surprisingly, it is not far from the black sheep, which is a 4-cycle (compare 401 vs 413). I didn’t check whether it is still the worst-case or not among all 2-cycles, but I guess it is.
Absolutely, the worst offenders might not be as bad as we think As @X0rr0 previously pointed out, you can switch from cancelling 2s (when w and u have a shared prefix) to cancelling 3s (when they have a shared suffix), or you can mix (when they have both).
@oros mentions more powerful cases of 2- and 3-canceling, which don’t necessarily have anything to do with shared prefixes or suffixes.
These often feel kinda “unpredictable” or “accidental” to me, or at least even harder to model that what we already have in front of us. But it’s great to realize there is more headroom if it comes to a crunch.
One of my favorite cases of “accidental” canceling is ruling out a particular circuit, here with a twist on the single-member method:
If circuit v = 1111111100000 is an integer cycle, then its bottom member \cfrac{3^8 - 2^8}{2^{13} - 3^8} is an integer.
In that case, 31 \cfrac{3^8 - 2^8}{2^{13} - 3^8} + 206 is also an integer.
But 31 \cfrac{3^8 - 2^8}{2^{13} - 3^8} + 206 \cfrac{2^{13} - 3^8}{2^{13} - 3^8} happens to equal \cfrac{3^{12}}{2^{13} - 3^8}, which is not an integer.
Agreed, except for one thing: the 3-canceling is also (largely) predictable based on shared suffix. Very likely, the idea came to me after reading @X0rr0 's post.
It can be helpful to write it down as follows:
Consider two rotations with shared prefix A and shared suffix B: v_1 = A u B v_2 = A w B
Then we have \beta(v_2) -\beta(v_1) = 2^{l(A)} 3 ^{s(B)} (\beta(w) - \beta(u)).
Hence, when having a redundant part C, we can freely split this part as C= BA in such a way that 2^{l(A)} 3 ^{s(B)} is maximized. However, the remaining part \beta(w) - \beta(u) does not change!
So you are right, the improvement comes from an extra 3 factor in the difference \beta(w) - \beta(u), which is rather accidental. But this seems to occur quite often since it happened for every worst cases in you mentioned (except of course in the circuit and high cycle cases).
As a simple (yet still hard) analytical problem in this vein, consider “Among cycles of length l(v) that have minimal LRS, how large can \beta(v) be?”
Here’s a motivating table built by exhaustive analysis.
We could further restrict s(v) \approx 0.63\ l(v), though that might make this sample analytical problem harder (though closer to realistic). We can also produce similar tables for odd-\beta-difference, instead of straight \beta, getting even more realistic (like the graphs posted earlier), though again harder to grapple with.
But I like this simplified problem.
The task here is to (provably, tightly) upper-bound \max-\beta as a function of l. What makes it hard is how diabolically the max-\beta string decides to spread the 0s and 1s.
Clearly, you want log(l) 1s on the right, and log(l) 0s on the left, but what’s going on in the middle? Edit: sorry, even that is not so clear!
This is pretty interesting. I don’t know how far the method can be pushed, but the concept is whispering something - I’m not sure exactly what it is yet, but am thinking through the broader class of defects as primary objects. Have we worked through paired groups of differences? (2, 4, etc.)?
For sure, @stargazer07817 … as implied here and here, I’ve looked at linear combinations of multiple cycle members’ betas, where the number of members included 1, 2, 3, 4 and l itself.
While I’ve poked around a fair amount in this area, probably I’ve been digging in the hedges and missed the spaceship buried in the backyard.
With the idea you mention, you can certainly do better at small l, bringing more vectors under the dashed \delta line. But I haven’t found any pattern that generalizes.
For example, you might guess every cycle has some “signed sum of odd members’ betas” (linear combination with coefficients restricted to 1 or -1) of the form 2^i 3^j y, where always y < \delta(v). This works great for small l, but you eventually reach counter-examples like
The simple difference-method, as it exists, is at least understood in terms of the shared prefix between w and u, so we know something about how and where it works at large l. Maybe it would help to think logically about what happens when more than two vectors’ betas get combined.
Also, counter-examples to any proposal (like the one above) might appear, but then might eventually disappear, at higher l, overwhelmed by the rocketing 2^l - 3^s. We currently have almost no grasp on the asymptotics.
I just went down a rabbit hole on Minkowski’s theorem, which seems to deal with pretty much this. Well, it doesn’t shave off 2^i3^j, but there might be a way to make it do that. My guess is that LRS ultimately loses to diabolical vectors, and that while linear combinations might favor these diabolical vectors, there are vectors that are diabolical in a different way to linear combinations (the counter-examples you mention). The thing about Minkowski’s theorem though (if it applies and if I understand it at all), is that it gives you an actual bound. The most fundamental part I don’t really understand though is what you would plug in for the determinant. I mean there’s a lot I don’t understand. I just spent a lot of time googling. My takeaway though is that LRS can give you impressive results, but trying to push LRS to maximize cycle shape coverage might just be a less efficient way of reinventing arithmetic geometry. Who knows though maybe collatz stringology is a unique case still open for more elementary discovery. I don’t have any interest in going rogue with this, I just couldn’t help googling in the absence of answers, particularly on the question of how “promising” the methods in this thread are.
As 
