Juan Arias de Reyna's conjecture 8, revisited

(There is no "part 2"; the "part 1" was just to signal that more was coming.)

In this entry I will consider Juan Arias de Reyna's conjecture 8, and some variants thereof (some of which are almost certainly false).

Note: To make things easier, I will phrase everything in terms of defects rather than ratios.

Let's start with some definitions. Define a natural number n to be stable if for all k, ||n*3^k||=||n||+3k. Define a stable defect to be the defect of a stable number. (If two numbers have the same defect and one is stable then so is the other, so there is no problem there.)

I will use "D" to mean the set of all defects. (In the paper we will use a curly D.) Ď will indicate the set of all stable defects. (Because it's more convenient to type in HTML than some of the other alternatives.) I will use "cl" for topological closure. "D^a" will indicate the set {d(n): n≡a (mod 3), n≠1}, and Ď^a will be used similarly. Since all of these are well-ordered sets with order type ω^ω, I will use S_α to mean the α'th element of S. (Except in one special case which... well, you'll see.) Also, in this entry, N will include 0.

So. Conjecture 8 deals with the self-similarity of the set of defects. We know it has order type ω^ω; conjecture 8 says that left-multiplication by ω roughly corresponds to a numerical increase of 1. Of course, we have to be careful how we formalize this.

Last time I discussed conjecture 8, I actually messed it up slightly. Let me begin with a slight variant / reformulation of that form:

Version 1: For k≥1, lim_{β→ω^k(α+1)} D_β = D_α+k. Furthermore, lim_{β→ω^k(α+1)} D^a+k_β = D^a_α+k.

Unfortunately, this version is almost certainly false; unstable numbers really wreck it. Which is why what Arias de Reyna actually conjectured is a bit different.

Version 2: For k≥1, lim_{β→ω^k(α+1)} Ď_β = Ď_α+k. Furthermore, lim_{β→ω^k(α+1)} Ď^a+k_β = Ď^a_α+k.

(His original conjecture is the "furthermore", in the case k=1. The rest is some natural extensions / variants of it.) This seems to work! But it's a bit of an ugly statement. Granted, it can be prettified a bit, in particular in the case k=1. (In fact, the case k=1 implies the general case, so that's all that's needed. Why do I insist on stating it for larger k? Well, you'll see.) For instance, we could write the nicer-looking

Version 2.1: lim_n→∞ Ď_ωα+n = Ď_α+1. Furthermore, lim_n→∞ Ď^a+1_ωα+n = Ď^a_α+1.

This is equivalent, but looks nicer, and is also closer to the form Arias de Reyna originally wrote it in. But let's keep looking! Let's see if we can find some other similar, plausible statements. (Which may or may not be equivalent.)

Why is instability a problem? Well, if r is a defect, r+1 may or may not be a defect. Restricting to stable defects gets rid of this problem by ensuring that r+1 is not under consideration regardless. But how about solving this problem the opposite way? Instead of throwing r+1 out when it appears, let's try throwing it in when it doesn't... by considering cl(D) instead of D. This, too, is a well-ordered set with order type ω^ω. And it should be equal to D+N=Ď+N, though I can't currently prove this. But more importantly right now, it's a closed set, and the order topology on it coincides with the subspace topology, which makes the language a lot nicer. (This is true in general for closed subsets of linear continua.) I do not know whether or not it is equivalent to version 2 above, but looking at the numbers strongly suggests the following:

Version 3: cl(D)_ωα=cl(D)_α+1.

Now that looks nice, doesn't it? Except it isn't quite right. After all, as written, it implies that 0=1! Rather, this appears to be correct, so long as we 1-index cl(D). So:

Notational convention: Closed well-ordered subsets of R will be taken to be 1-indexed. Other well-ordered subsets of R will be taken to be 0-indexed, as usual. (Trying to 1-index D itself, e.g., seems to be a bad idea.)

If we read version 3 with this notational convention, then it does appear to be a correct and very nice statement. (I mean, look at that self-similarity! Just look at it!) And with this one, it's truly immediately obvious that the k=1 version implies the same for higher k. Also note that this version doesn't require a special exception for k=0. Of course, in the above, I've left out the versions for D^a. So let's include those:

Version 3.1: cl(D)_ωα=cl(D)_α+1. Furthermore, cl(D^a+1)_ωα=cl(D^a)_α+1.

Pretty nice, no? Now that is some self-similarity. (Offhand, cl(D^a) ought to be equal to (D^a+3N)∪(D^a-1+3N+1)∪(D^a-2+3N+2), as well as being equal the same thing with D replaced by Ď.)

Now wait, what about cl(Ď) and cl(Ď^a)? These are probably just equal to cl(D) and cl(D^a) and so already covered.

Unfortunately there remains the problem of actually proving any of this. Version 1 is presumably false, of course, but versions 2 and 3 are probably true. Well, I'm not working on it right now -- I have too much else to do, most notably actually writing up the first of these 3 papers -- but I do have an idea for an approach. If it works, this idea will require proving it for all k simultaneously rather than just for k=1, which is why I made sure to state it for higher k above. Also, I suspect that version 2 (Arias de Reyna's original conjecture, pretty much) is the one that should be tackled first; from what little I've done, it seems to be the easier one to get a handle on. I think, however, that if one can prove version 2, one will also be able to derive version 3, as well as the rest of the statements above (at least, the ones that are actually true). This idea, if it works, may also have implications for some generalizations of Arias de Reyna's conjecture 2; unfortunately, it would probably not get us anything close to conjecture 2 itself.

As for what this idea actually is, I will write about that when it is more than just a bit of mindfuzz. Which will not be for a while, because I don't have time to work on it right now. So now you are all roughly up to date on what Josh and I have been doing with integer complexity.

-Harry

Integer complexity update, part 1

About time I got around to writing this. This is going to be a pretty brief overview, I can go into more detail if people want.

(Reminder: Tags now work; one can go here to see only my entries about integer complexity.)

The main thing that is being done now is rewriting. Need to rewrite this draft into something readable. Again, many thanks to Juan Arias de Reyna for his help there. Current plan is to split it into 3 papers. First one will introduce the notion of defect, prove Arias de Reyna's conjecture 1, introduce Josh's method, compute up to 12d(2), prove 2^a 3^b works for a≤21, prove my formulae for E_r(k), and prove that A_r(x)=Θ(log x)^⌊r⌋+1. Second will introduce ternary families, reprove that last bit using ternary families, and prove well-ordering of defects, and generally include the relevant bits that got cut for length. The third will cover new material that we've come up with since getting back the referee report, which is what I intend to tell you about here.

(Note that when I said "3 papers", that's excluding Josh's work on upper bounds on ||n||. Which by the way he says he's finally going to get around to writing up!)

The third paper will introduce what was section 10 in the old long draft -- what happens when you take a ternary family, and restrict to those numbers below a fixed defect? Well, sort of -- actual defect is a little unpredictable, so instead we consider cutting off based on a sort of "expected" defect, which is still quite useful. The conclusion of section 10 was that when you do this, you still get ternary families.

What I did not realize at the time was that this was exactly the missing step needed to turn Josh's method into an actual algorithm! I wrote up some Haskell code to run the computations, and it has proved that 2^a 3^b works for a≤37. (Well, probably -- floating point arithmetic was used, and I thought it was arbitrary-precision when it wasn't. So, I'll have to go back and close that gap.) Why stop at 37? Well, 37=28+9, and above 28d(2), one starts having to consider +6s. Well, not exactly -- in reality they don't become relevant till long after that, but I wanted to avoid relying on such special-case reasoning. But in fact, it's not hard to get the algorithm to work beyond +1s; I just haven't bothered to do it yet because A. I initially didn't realize it would work in those cases, so I wrote the +1-only version first and B. I have a ton of other stuff to do so I haven't gotten around to writing it yet. It's a pretty simple modification, though; so when I actually have time, we can start proving this for even higher values of a. Point is, it can do in minutes what took me months by hand. And yes, the algorithm verified that I got my hand computations right... but the table is wrong, because I made some mistakes when copying my results into there.

(In actual fact, the algorithm can't do everything my hand computations could; in fact, the part that caused them to take so long is one of the things it doesn't bother doing. So much of the speedup comes from it not doing things that are irrelevant for its purposes. But what it does do, it does quite well.)

But we can use this result for much more than just computation! Previously, we could only put upper bounds on A_r(x) by building up a larger set that contained it; sure, we could attempt to filter out the things that didn't belong, but who could say what the result would look like? Now we can actually get a rough idea. So at last we can prove, for k a natural number:

A_k(x) ≤ (k+1)^(k-2)/k!^2 (log₃x)^k+1 + O_k((log x)^k)

...and my 19-case generalization thereof. Of course, we'd like to have that ≤ be an =, but getting lower bounds would require some sort of "small intersection" theorem. I believe I can prove some special cases of this, actually, but, unfortunately, not the relevant cases.

Unfortunately, if we want to prove that ||n|| is not asymptotic to 3log₃n, the above isn't good enough -- it's got an O_k in it, and we need to know the dependence on k. Our attempts to determine the dependence on k have generally concluded that it's not good enough to make things work. But I don't think Josh has taken a detailed look at it yet, and he's rather better at this sort of thing than me. I'm not optimistic, but we'll see.

We can also use this method to make some conclusions about order type, allowing finally a proof of the connection betwen integral defect and order type. Basically we can prove a lot of my old conjectures from section 11 of the old long draft.

There's still the question of Arias de Reyna's conjecture 8, which still seems to be out of reach; but more on that later.

-Harry