Chronicles of Harry

...OK, this has absolutely nothing to do with INTERCAL, that's just what the word "interleave" called to mind.

Table now goes to 16. And with that, I'm going to stop this nonsense. These things take too long to compute and aren't actually very useful. I am going to continue with my classification, of course, and the results will take the form of large tables, but they'll be tables that don't take so damn long to compute, and will be heavily compressed compared to these enormous ones.

-Harry

3+3+2=5+1+1+1=8, 4*4*3=6*2*2*2=48.

Well, I probably shouldn't be wasting my time on *lower* bounds on A_k(x) anyway... unfortunately I don't really have time to continue my computations right now, as I have an enormous amount of grading to do...

OK, actually, I think I've got a fix for the problem from my previous entry. Unfortunately, rather than α≤1/2, it requires α<1/2.

...you know, the reason I originally suggested changing our definition of the A_k is so that I could use steps of size α_1, rather than some size arbitrarily close to α_1. But, that won't help here. It's just annoying, you know? That no matter how you pick your step size, there's a better one? (Well, OK, that's probably not exactly so, as using step sizes closer to 1/2 would result in more exceptions to keep track of. But still.)

Essentially the idea is just that as long as α<1/2, we can look *two* steps back for the addition step rather than 1 step back, without breaking things. With introducing more exceptions, to be sure, but those shouldn't be a big problem.

I think I'll try a step size of 1/3 first, for convenience...

-Harry

EDIT next day: Two small addenda within.
EDIT 18:17 that day: Sorry, changing A back to its old 1-including definition... the statements would need to be modified otherwise. (Well, the only change would be that you'd need to also union in A_kα+S_(k+1)α and A_αT_α.) Similarly modifying the definition of B to fit this (namely, excluding 3 from it).
EDIT 19:30 Feb 13: Sorry, I forgot about an earlier slight improvement I had made to addition - namely in the definition of S_x - since it hadn't been relevant previously... it's actually not really relevant here either, but I want to remind myself of it.

OK. A few days ago Josh sent me an email with an observation on our recursive construction of A_kα. You may recall that it contained a multiplication by A_α^*, where by "*" I mean "multiplicative closure". This was annoying for multiple reasons, but one in particular was that in order to actually compute A_k, I had to use step size at most d(2)=2-3log_3(2), which lies inbetween 1/10 and 1/9. (Thought: Perhaps I should start using a different variable for step size, instead of α. Typing that all the time is getting annoying. Maybe h or something. Oh well, I'll stick with α for now.)

Anyway Josh pointed out - we don't really need products of arbitrarily many elements of A_α. When you consider that powers of 3 can basically be ignored, and everything else has a defect of at least d(2), you only need about 10 or so.

"Holy crap this is AMAZING" I responded. The argument is really simple but we had somehow managed to miss it until now. Indeed, I realized, it could be refined - you didn't need 10 or so, you only needed 1 (with one exception). The fundamental idea here was not that the minimal nonzero defect is d(2); the fundamental idea here was tracking the defect at all. (At first, I thought this would actually allow us to use α≥1, but this isn't right because the addition step still requires α<1.)

That one exception (which I'll get to shortly) would annoy me for the next few days, but even by itself, his refinement was enough to finally prove a conjecture we've had for a while - I think Josh suggested it initially - that A_r(x)=Θ((log x)^⌊r⌋+1). (The lower bound we already had; it suffices to check it for integers, for which just note that if you take numbers of the form "sums of r+1 distinct powers of 3", these all have defect at most r.)[0]

Anyway Josh thinks that he can actually analyze the constants to the point of being able to actually prove f(n) is not asymptotic to 3log_3(n) (his original motivation for introducing this line of thinking in the first place, you'll recall). I looked at that a bit and it didn't look very promising, but, we'll see. ADDENDUM next day: Having presumably analyzed it rather more than I did, Josh now says the constants really aren't good enough for that. Oh well.

Anyway! Let me state my refinement of Josh's big improvement.

No, wait, first, let me restate some definitions. I've been kind of fiddling with these - I no longer see any real reason to include 1 in A_α for α<1; and I've decided that some of the tricks we've used should be explicitly incorporated into them. Also I'm defining "B_k" to make my "factoring out 3s" trick (which I don't think I've discussed here) work formally. EDIT later: OK, I've changed it back to having 1 in A_α for α<1; perhaps it really shouldn't be, but it simplifies this statement, so I'm leaving it in here for now.

So: Take 0<α<1. Define A_x={n∈N: n=1 or d(n)<x}. Define B_x={n∈A_x: 3 does not divide n, or f(n)≠3+f(n/3) and n≠3}, so that A_x={3}^*B_x (where again * means multiplicative closure). Define S_x={b∈N: f(b)<x+3log_3(2), and b does not have a minimal representation as a sum} (so in particular S_x is finite). Finally define T_α={m∈N: m<2/(3^((1-α)/3)-1)+1, and either m=1 or f(m)=f(m-1)+1}. (So as α<1, T_α is finite.)

Then: A_2α ⊆ (A_α)^3 ∪ A_α(A_α+S_α) ∪ A_αT_α;
and for k≥2, A_(k+1)α ⊆ (∪^k_i=2 A_iαA_(n+2-i)α) ∪ A_α(A_kα+S_(k+1)α) ∪ A_αT_α.

Similarly, B_2α ⊆ (B_α)^3 ∪ B_α(A_α+S_α) ∪ B_αT_α;
and for k≥2, B_(k+1)α ⊆ (∪^k_i=2 B_iαB_(n+2-i)α) ∪ B_α(A_kα+S_(k+1)α) ∪ B_αT_α.

(It's really the latter we want to use for determining the order of A_k(x), as it has powers of 3 factored out for us, to avoid redundancy. The "annoying exception" was the case k=1, passing from 1 to 2, which as you see I stated separately. ADDENDUM next day: Also I forgot to mention that Josh said he had a further refinement to the multiplication part, but I guess he doesn't have it fully worked out yet.)

So if we start from the fact that for α<1, B_α is a finite set, i.e., B_α(x)=O(1), and we repeatedly apply A_k={3}^*B_k and the fact about B_k above, we quickly see that B_(kα)(x)=O((log x)^(k-1)) and A_(kα)(x)=O((log x)^k). Then our conjecture follows immediately - given r, take α=r/(⌊r⌋+1), k=⌊r⌋+1, and... well, there you go. (Again, the lower bound we already had.)

OK. But as I said earlier, we don't actually need my refinements to prove that - Josh's original observation sufficed for that. So, what are my refinements good for? Well, for one thing, maybe proving f(n) not asymptotic to 3log_3(n), Josh suggests; but also, they could potentially speed up my explicit computations of A_k a huge amount.

Here I've been, crawling along d(2) at a time - and now I can potentially work with α much larger! How large? Arbitrarily close to 1? Well, for reasons I'd rather not get into right now I think I want to keep α≤1/2, but if that does work, from d(2)<1/9 to 1/2 is a huge improvement! The program I was writing, I never did finish; I think I should probably still do that, especially seeing as I think it was close to done. But, if I can go in steps of 1/2 at a time, quite possibly I won't need it! (Remember, it breaks down at 2; to make it go further than that would require serious rethinking of the algorithm.)

We're not, of course, any closer to a general proof that f(2^n)=2n, because the addition step is still nasty. (Also, Josh says that by some advanced number theory stuff, the fact that for any m there exists a K such that if we let M=3^K, then f(M*3^k)=f(M)+3k for any k means proving f(2^n)=2n should be very hard.) (Also, Josh hasn't improved his upper bounds any in a while, last I asked.) Also FWIW I still have little idea about proving that the set of defects is well-ordered.

So, yay for actually bothering to track the defect involved in that "arbitrary" product.

-Harry

[0]The distinctness condition can probably be relaxed, which if you care about it at that level would get you a better lower bound - but even asymptotically speaking I don't think you'd actually improve the constant any. If you do want to be as general as possible, I think the restriction you want is just that the largest power of 3 involved is distinct from the others, but, well, I don't really care.

(Also: My computing account with Uchicago, and hence that email address, is now defunct. Oh well...)

EDIT: Emily points out that the above is mistaken.

(Also also: Right now it seems I can only play Dominion at all decently if I can get combo cards. Need to learn how to better handle games where those don't exist.)

So let's take a moment for me to explain the computations I've been doing.

So let's let f(n) be complexity of n, define d(n)=f(n)-3log_3(n) (d stands for "defect"), and A_k={n:d(n)<k.} (Yes, this used to be a nonstrict inequality. I've decided I like the strict inequality better. You'll see why.) Recall, some time ago Josh proved that for any k, A_k(x) is polylogarithmic in x. He did this by showing that A_k satisfied a... what would you call it, a sub-recurrence? A_(k+1) is contained in something that depends on A_k. Although he didn't actually use step size 1, he used step size 1/10. Really any step size at most d(2)=2-3log_3(2) would work. (I'm going to call that number α₁... I think I've said that before. Actually, no, I'm just going to call it d(2), because that's much easier to write here.) In fact, any step size less than 1 would work, but we didn't realize this till later. However I'm going to continue to talk just about using a step size of d(2), for reasons you'll see.

So I asked, is this good enough to explicitly compute A_k beyond what we already know? Unfortunately, well, it wasn't. But I'm going to skip over how we got to where we did, seeing as I don't remember the chronology very well and much of it involved us doing stuff that was a bit dumb (i.e. trying to use a step size of 1.) (Basically, I tried to use a step size of 1, and concluded I couldn't do it. Then Josh tried to fix what I did by just using a strict inequality instead (at that point we were generally using nonstrict inequalities). But when I looked over his argument, it didn't quite work. While trying to repair it and failing, somewhere I realized the whole issue would go away if we just used a step size of less than 1. D'oh.)

Anyway, eventually Josh got an improvement on the addition part and I got an improvement on the multiplication part that allowed us to get that linear bound on the power of the logarithm; but also to start actually computing A_k. Let's say we pick a step size of &alpha, and let A_α^* denote the multiplicative closure of A_α (which is polylogarithmic iff α<1); then an element of A_(k+1)α is an element of A_α^* times one of the following: A product of an element of A_iα and A_jα where i+j=k+2; or an element of A_kα plus an element of of a finite set which depends on (k+1)α; or an element of a finite set that depends on α.

Is *this* good enough to explicitly compute A_k? Almost! We need two things. Firstly, we need to pick a step size at most d(2). Otherwise, A_α contains 2, meaning A_α^* contains all powers of 2; and if we knew how to handle powers of 2, well, we probably wouldn't be doing all this. But if α≤d(2) then we just have to deal with powers of 3. Secondly, we need to use an additional clever argument of Josh's that improves the addition case a bit - if k<3, we can take the finite set we're adding from to just be {1}.

OK. So procedure is now as follows: 1/10<d(2)<1/9, and we already know A_1 from stuff I'd done previously; what's more, we explicitly know the defects of all those numbers, so we know A_kd(2) for k≤9.(Actually, this procedure is good enough we could start from the bottom and recompute this! We don't need to use the stuff I did earlier.) So say we want to carry out the first step and compute A_10d(2). (We also want to compute the defects of all its elements, so we can determine A_k for any k≤10d(2).) Well, we take products of elements from A_id(2) and A_jd(2), where i+j=11. And we take elements of A_9d(2), and add 1 to them. Then, we compute f of these numbers. How? Well, upper bounds are easy; and for lower bounds, we use the fact that we know that these numbers are not in A_9d(2). Well, if they're not. If they are, then we already know their defects. So having computed f, we now know d of these numbers, and so in particular we know which ones have defect less than 10d(2). Yay! Repeat until you hit kd(2)>3 and you have to rethink your method (because now 1 is not the only number you might have to add), or until you get sick of it.

I have currently, by hand, gone up to 14d(2) (a little over 3/2), and most of this was looking quite automatable. The lower bounds on f I was doing a bit adhocly at first, but actually it's not too hard to prove that - so long as the number's not one you already have - they work out to be what you want them to. The only sticky part, that I couldn't think of how to automate, was how do you check if the numbers *are* ones you already have? We're dealing with infinite families of numbers here.

Of course, these infinite families of numbers are all of forms like a*3^n+b*3^m+c*3^k, but somehow it didn't occur to me till recently that I should just write everything in ternary. Suddenly it's so much easier - I can check it pretty much by eye! Indeed, it seemed automatable... and now I'm quite certain it is, and that's what I'm working on right now. This shouldn't take too long; it's much simpler than that previous monstrosity I wrote.

Unfortunately, what I'm writing up right now will necessarily break down when we hit 2 (i.e. when we hit 19d(2)). You see, the numbers 3^n+1 all have defect less than 1; so numbers (3^n+1)(3^m+1) will all have defect less than 2. And that infinite family is not one that the program as I'm writing it can handle. It's quite possibly doable, but I'll think about that afterwards.

Hm, perhaps I should upload my table of summarized results so far... note not everything in the initial note will be comprehensible as this was originally just intended to show to Josh (and due to its nature as something only partially completed, I'm not going to fix that right now). Here it is! The reason it includes 14d(2) itself is because we can get that as a freebie, already knowing it from elsewhere.

ADDENDUM: I just realized I never explained why strict inequalities make things better! The reason for this is that if you use nonstrict inequalities, then 2∈A_d(2), and so you can't actually compute A_k using steps of size d(2), you'd have to use steps of size less than d(2). So that is way more trouble. Especially since determining things of defect exactly k*d(2) is (in cases so far) pretty easy (the freebie mentioned above), so truly nothing is lost.

-Harry

So: d(n)<10(2-3log_3(2)) iff n is of one of the following forms: 2^a*3^k, a≤9; 5*2^a*3^k, a≤4; 7*2^a*3^k, a≤3; 19*2^a*3^k, a≤2; 13*3^k; 55*3^k; or (3^m+1)3^k.

With this, and our previous stuff (not all of which has appeared here, mind you :P ) it's not too hard to show that f(2^20*3^k)=40+3k.

Why do I get the distinct suspicion that it will, in fact, turn out that A_(k-ε)(x)=Θ((log x)^k) for k an integer, as Josh suggested? Or at least when k=2? And that these won't get too much more complicated until I pass k=2 so I should be able to push up to about 29 or 30 or so?

-Harry

So not only does the linear bound given in the last entry actually work, but the actual construction behind it suggests a method for proving f(2^a3^b)=2a+3b for fixed a, one that doesn't cap out, uh, anywhere. Unfortunately it seems terribly tedious. So far I've just used it to go up to a=19, one past what we already had. Past that I can no longer rely on nice explicit descriptions. Hopefully something will generalize?

Also another quick addendum: Also, yes, that infimum is achieved; for n≥1, A_n(x)=O((log x)^K) where K=3n/(5-3log_3(5)).

-Harry

So while I've written a bunch about what Josh and I have done with integer complexity, it's been rather scattered and contextless. So I thought I would take some time to write up a big summary of what's already known, what the numerical data suggests, what we've actually proven, and where we are now, that should hopefully be accessible to everybody. No proofs, just statements and some relations between them. However I'm going to go into what is probably excessive detail in the "background etc." section, just for the sake of completeness/explanation. The "results etc." section will be more sketchy.

( Background, data, immediate questions )
( Results, resulting questions, where we are now )
( Stuff we're not touching )

Anyway I think that more or less sums things up.

-Harry

So, more on integer complexity. Let's recall I'm using f(n) to denote the complexity of n, and g(k) to denote the highest number of complexity k. f(n)≥3log₃n; the smallest differences occur when n is of the form g(k) for some k, i.e. it's of the form 2^a*3^k with a≤2, and after those the smallest differences occur when n is what I called a "canopy number", which are of the form 2^a*3^k with a≤10 or 2^a(2^b*3^m+1)3^k with a+b≤2.

So let's define A_k={n∈N: f(n)-3log₃(x)≤k} (we may also want to always throw in 1 even if k<1), and let's recall that Josh proved that A_k(x)=O((log x)^K) for some K depending on k. (Actually, have I stated that before? Well, he proved it a while ago. In particular, it follows that f(n)-3log₃n is unbounded, which was the original motivation.)

Notice that if we define L(x)=min k such that g(k)≥x, this is bounded away from 3log_3(x), so the statement is equivalent with L(x) in place of 3log_3(x). Or instead we might use, say, ⌈3log_3(x)⌉, or l(x), defined by l(x)=max k such that g(k)≤ x. (Note l(x)=L(x)-1 unless x=g(k) for some k, then l(x)=L(x)=k.)

Regardless, I'm going to think about this difference, between f and whatever-function-that's-close-to-3log_3-we're using, as a "defect".

Now, here's the thing about Josh's proof: When I defined A_k, note I never required k to be an integer, and if we're going to be using actual logs, then, well, that would kind of be a silly requirement. And so Josh's proof works, inducting on k, increasing it 1/10 at a time. (Actually 2-3log₃2-ε, but it's easier to just say "1/10".)

This is perfectly good if all you want to do is prove that A_k(x) is polylogarithmic, but if you want good bounds on what the exponent is, it stinks. We start with an exponent of 1 for A_0 as our base case; this gets us an exponent of 2^(10k) for A_k. An exponent of 1024 for A_1. The actual minimal exponent for A_1 is 2 (this follows from what I did earlier).

Why 1/10? Because 2-3log_3(2) is the minimal nonzero defect that can occur. So I had an idea, if we use a different function in place of 3log_3, that gives us a larger minimal nonzero defect - say, 1, because the function will always be an integer - we could get much better bounds. Indeed, I even found a way to bring K down from exponential in k all the way down to linear in k - but this specifically used the fact that we were dealing with integers. And not only that, but the actual concrete methods that led to these bounds, I thought, could potentially prove the 2^a*3^b conjecture for higher a - for a short time I thought I had (nearly) proved it for a≤29.

But apparently there were some major holes in what I'd done.

You see, while the bad thing about Josh's proof is its small minimal nonzero defect, the good thing - that makes it work, unlike my attempts at variants of it - is just what happens at zero defect. You don't want there to be many things of zero defect - rather, you don't want there to be many elements in the multiplicative closure of the set of zero-defect numbers. If we're just using 3log_3, we get powers of 3, which are already closed under multiplication. Pretty good.

But suppose we use L instead - then you get all the canopy numbers. Because of that pesky +1, these are far from closed under multiplication. I'm not sure exactly how best to estimate how many products of canopy numbers are at most x, but I don't think it's polylogarithmic, and assuming that's correct, it makes it useless for this. Using the stricter ⌈3log_3⌉ doesn't help any.

Ah, but what if instead I use l? For a while, I thought this fixed it - then the numbers of defect 0 are the g(k), which, while not closed under multiplication, yield just numbers of the form 2^a*3^b when you close it up - logarithm squared, that's perfectly fine. But the problem is, unlike the functions above, l doesn't satisfy l(ab)≤l(a)+l(b), which is, SFAICT, quite necessary for the induction.

So we don't have 2^a*3^b for a≤29, we don't have that you can just use K=2k or 3k-1 or even just 2^k or 2^(k+1)-1; what we have, that works, is just Josh's original proof, that gets you K=2^(10k). (Unless I'm wrong about products of canopy numbers.)

...well, at least this'll make writing everything up quite a bit easier.

-Harry

OK. I cleaned up that horrid mess of code. Well, for the most part I left the code untouched, I just added lots of comments, but in a few places going back over it so that I could understand it so that I could explain it, I noticed there were a few mistakes, or redundancies, and I took care of them.

So I've got the whole thing there. Since in my writeup I start with the concrete version of the algorithm, then abstracted it, and then finally abstracted it further to the thorough version that tells us everything, I had it do all three. Let's test all three modes. Concrete mode... OK, I was about to say it works fine, but apparently it runs into problems with gamma3? That's odd, that shouldn't be happening... well, when it returns, it seems to work fine, and that shouldn't be too hard to fix. Abstract mode... matches my data perfectly. Good. Thorough mode... doesn't return. Crap. Evidently there was an additional way of generating these infinite families which I missed because my code, with some errors in it, missed it. Gah.

ADDENDUM Oct 1: There wasn't. It was just a really stupid programming error. In fact, the corrected version hit *less* than the previous version, because the previous version for some reason included one or two things that were in those infinite families anyway, somehow.

Tomorrow, I say. Tomorrow I shall finish this. Hopefully.

(Ignoring, of course, the whole part where Josh and I try to put our work together into something coherent. But this part will be done, I'll have something I can upload somewhere and show you...)

-Harry