Chronicles of Harry

Over a decade later, joshuazelinsky finally posted to arXiv his paper with his upper bound on integer complexity!

...the exposition isn't the best because he decided it was more important to just get it up there than to spend more time revising it. But hey! It's up! Go, know about it! Use it and cite it, it's up there! :)

Here it is.

For now, I'm going to skip a long explanation of the contents of this paper. Perhaps I'll come back and do it later, but I'm guessing a lot of the people reading this already know a fair bit about it.

But goddamn what a relief it is to finally have this done. I mean it's not done, of course, I'm sure there will be changes necessary for publication. But it's up. It's out there.

We weren't sure whether to include section 5, and in particular the "off-by-one" theorem, but, ultimately, we included it. Otherwise it would have had to be a separate paper, which just makes for more headache, you know? (There is other stuff that got cut for length -- by which I mean, never actually written -- that will have to be a separate paper, but, that was never realistically making it in here.)

I actually haven't said as much on the internet about the contents of this paper as I have about previous paper... really, a lot of the stuff regarding integer complexity that the ideas in here led to, I just haven't really talked about so much. Well, I should remedy that. Maybe in the coming days or weeks I'll go back, and post about some of that stuff, that Arias de Reyna and I have coming down the pipeline in the wake of this. I mean, I imagine it'll be a while before those get written up properly, but I'd like to talk about it some.

But like the thing about this paper, that I've wanted to get this out there so bad is that like... I think this is kind of the best paper I've written, y'know? And it might well be the best one I write for a long time. Not in terms of the strength of the results (we've got stronger ones coming), or the quality of the exposition, but in terms of, tying things together. This paper just really ties everything together really nicely -- answering simultaneously what look like two unrelated conjectures -- and solves problems rather than raises them. It does raise new problems, of course, but ones that don't seem as essential as the ones it solves. And it finally resolves all of Arias de Reyna's old conjectures!

So, that's it. It's up. And I'm going to stop here now. Maybe more on this later.

So, two entries ago, I discussed some variants on the Mahler-Popken problem. I'd like here to return to the original Mahler-Popken problem and discuss a different variant. Namely: What is the second-largest number we can make with k x's?

First, though, we should talk about the answer to the original problem in more detail. As before, I'm going to focus on what happens when k is sufficiently large, and how large k needs to be may depend on x.

So, as mentioned in the previous entry, to make the largest possible number from k x's, we want to group them into groups of m and then multiply them together. How large is m?

Well, m is the m that maximizes (mx)^1/m. This is approximately e/x; indeed, e/x would be the maximum if we allowed m to vary continuously, but since that's not possible, m will be either the floor or the ceiling of this. The value of m changes over at the values m^m-1/(m-1)^m. Or, more specifically, m^m-1/(m-1)^m is the largest value of x where m is the group size, and (m+1)^m/m^m+1 is the smallest. (Throughout, I'm going to think of x as decreasing from ∞ towards 0.) As previously mentioned, at the changeover point (m+1)^m/m^m+1, both groups of size m and of size m+1 work.

So. When k is divisible by m, we group things into groups of m, yielding (mx)^k/m. When x is on a boundary, x=(m+1)^m/m^m+1, then for any k sufficiently large we can make k using groups of m and m+1, yielding ((m+1)/m)^k; divisibility conditions don't even come into it.

But what about when m is well-defined but k is not divisible by m? Let's say k is r mod m, 0<r<m. In this case, we'll need to use some groups of size either m+1 or m-1 to make the congruence come out right. But which one?

This is where it gets really neat. Mahler and Popken found that, if x is larger, you want to use groups of m-1; and if x is smaller, you want to use groups of m+1. The changeover point, where both give the same
result, is at

m^m-1/(m-1)^m ((m²-1)/m²)^r

Let's denote this number by x(m,r). There's several really neat things about this:

1. Let's note that occurrence of m^m-1/(m-1)^m. We've already seen that quantity before, as the value where m itself changes over, from m-1 to m. And here it's what we get if we were to plug in r=0 -- which doesn't make sense, but if you plug it in anyway, that's what you get. So, the changeover point from m-1 to m is x(m,0).

2. For a fixed m, x(m,r) is monotonically decreasing in r.

So as x decreases, the congruence classes change over from using (m-1)'s to using (m+1)'s, one at a time, in order. At first, when we first hit x(m,0), when we first start using this specific value of m, all the congruence classes (other than 0, of course) are using (m-1)'s. Then we hit x(m,1), and now, the r=1 congruence class changes over. Then we hit x(m,2), and the r=2 congruence class changes over. Etc. Until... well, obviously, after x(m,m-1), all the congruence classes have changed over and are using (m+1)'s (except, once again, 0, obviously). But what happens if we plug in r=m? What's x(m,m)?

3. If we plug in r=m, we get (m+1)^m/m^m+1 -- the point where we change over to the next m! That is to say, x(m,m)=x(m+1,0).

In addition, for fixed m, x(m,r) is exponential in r. Like, literally exactly exponential, not approximately. Meaning that... like, say we've already divided up the positive real line based on the value of m we get, right? With the dividing points being the numbers x(m,0), for m≥1. Let's call those the major dividing points. Now we want to divide it up further based on just on the value of m, but on the more detailed eventual behavior, based on which congruence classes are using (m-1)'s or (m+1)'s. Well now we're putting additional dividing points -- let's call them "minor dividing points" -- at the values x(m,r).

Then for any two adjacent major dividing points, the minor dividing points between them are evenly spaced if use use a log scale!

I think that's really neat! :D

But OK, what about the second-largest?

Well, unfortunately, the answer there is considerably more complicated, and I'm not going to detail it all here. I'll tell you the answer when r=0. If x≥x(m,1), you want to use m groups of size m-1 (in addition to your groups of size m). If x≤x(m,m-1), you want to use m groups of size m+1. When x is inbetween, you want to use one group of size m+1 and one group of size m-1. (This is assuming m≥2. If m=1, then you make the second-highest by throwing in a group of size 2.)

It's nicely symmetric. Unfortunately the general answer is not. Here's another example where I can tell you the full answer: Say x is on a boundary, x=x(m+1,0), so you can make the largest out of groups of size m and m+1. To make the second-largest, you'll also want to throw in a group of size m+2.

(These are actually the only two cases I need to know about for the original motivation; the hard case, when m is well-defined but does not divide k, is not actually necessary for this. But I did it anyway. :P )

Anyway, like I said, I'm not going to detail the hard case here. The hard case actually needs to be divided into several subcases, depending on whether r=1, r=m-1, both (i.e. r=1 and m=2), or (the usual case) neither. I'll just say that it can involve such things as:

• Using 2m-r groups of size m-1
  
• Using m-r+1 groups of size m-1, and a group of size m+1
  
• Using r groups of size m+1 when this is merely the second-largest
  
• Using m-r groups of size m-1 when this is merely the second-largest
  
• Using r-2 groups of size m+1, and a group of size m+2
  
• Using m+r groups of size m+1
  

I'll also note that not all the changeover points are at x(m,r) for integral 0<r<m now. Now, in some cases, there can be changeover points at x(m,½) or x(m,m-½) -- meaning, yes, we can get irrational changeover points! We can also get some changeover points which are rational but can't nicely be expressed in the form x(m,r), not unless we're willing to allow r to be irrational.

There's also the issue of discontinuity. M_k(x) is necessarily continuous in x -- after all, it's the maximum of finitely many polynomials in x. Or, you know, on a graph, in order for it to switch over from one polynomial of x to another, well, the two potential maxima have to meet, and at the point where they meet both are equal, and there's no discontinuity.

But that doesn't apply for the second-largest. Because there's two ways that the second-largest could switch. One is that the current second swaps with the current third. Then yeah, they meet, they're equal, no discontinuity.

But the other way is that it swaps with the current first, becoming the largest. Then at the point where the two meet, both are equal... meaning they're both the largest. Neither is second-largest. Instead, the next-best candidate, which to either side is third, is for an instant exposed to the world as second. You have a discontinuity.

So, above I talked about "changeover points", but I should be clear it's now no longer not always a smooth changeover -- sometimes it is, but when you're considering k that's r mod m, and the changeover point under consideration is x(m,r) itself, that point will have its own special behavior that doesn't match either what's above or what's below it.

And there's one case I want to point out that's particularly weird, and that's what happens when m=2, r=1, and you look at the discontinuity at x=x(2,1)=3/2. Because this case doesn't fall under one of the possibilities I listed above. It can't even be described as group-and-multiply!

Because, you see, while mostly you want to use groups of 2, what you want to do with your remaining 3 x's isn't to make, say, one group of 3 (for a value of 3x), or three groups of 1 (for a value of x³), but rather, to use them to make x²+x. Which, again, then gets multiplied by a bunch of groups of 2.

Isn't that crazy??

Like, I can prove all this. I can definitely prove that this happens when x=3/2 and not for any other x. But I have no good heuristic explanation of it.

By "irresponsible speculation", I mean "speculation without having done my homework first", i.e., without having even tried to look at the existing literature beyond this paper or actually really tried anything at all.

So, Juan Arias de Reyna recently pointed out to me the following paper: Commuting Probabilities of Finite Groups, by Sean Eberhard.

EDIT DEC 1: The paper has been updated; the following refers to the original version of the paper. See the comments for discussion of the updated version.

So: If you have a finite group, you can consider the probability that a randomly chosen ordered pair of elements from it commutes. You could then consider the set of all probabilities obtained this way; this is some set of rational numbers between 0 and 1.

In this paper, Eberhard shows that this set is in fact reverse well-ordered! Its order type is of the form ω^α where 2≤α≤ω². (Though Juan Arias de Reyna points out that it's not too hard to find examples that show that in fact α≥ω, so the order type is at least ω^ω.) He also shows that all the limit points of this set are rational. I think it should be pretty obvious why I'm interested in this! (Even though I have no plans to actually study this, my hands are full as it is.)

Now for the irresponsible speculation:

1. Instead of just doing finite groups, one could generalize to compact groups; one can consider probabilities there as well. How would this affect the set? It would be really nice if this just gave you the closure of the probability set for finite groups! Though Arias de Reyna tells me it's conjectured that the finite group commuting probability set is closed in (0,1], so that would be saying that using general compact groups only gives you 0 in addition. (I mean, it certainly does give you 0 in addition!)

2. I'm reminded of some work of John Wiltshire-Gordon and Gene Kopp. They considered probabilities of randomly chosen elements from a compact group satisfying some general word; the case of commuting probabilities is the case where the word w is aba^-1b^-1. I wonder if the same phenomenon might be seen for other words.

Probably it would be best to first look at words in one variable. Obviously using w=a generates an ω if we stick to finite groups and an ω+1 if we allow general compact groups -- not ω^ω, but still well-ordered. As for a² or a³... well, I don't know, and I don't really intend to work on it as I said above, but it seems vaguely plausible and it's an interesting question!

So yeah that's basically all I have to say on the matter.

-Harry

And so today I turned in the final version of my thesis and got my certificate of completion. If there are any more mistakes in there, I'm not fixing them. At least, not until I try to get Chapters 4 and 5 published (though Jeff tells me Chapter 5 will need to be split before it can be published).

It's going on ProQuest of course but also I figure I may as well just upload it to my website at UMich? (Hm, that should really be updated.) There's no reason it shouldn't be freely available. I'll also finally put the code up, for those of you who want it. A warning -- the code is far from readable; I didn't really have time to go back and make it readable, and since it wasn't officially submitted to the school, I didn't really have to. I did at least take the time to document all the functions, but I didn't take the time to put them in a sensible order. (Juan Arias de Reyna, meanwhile, tells me that he may rewrite the whole thing in Python.) Well -- I'll post an update here once I've done that.

EDIT: OK, website is updated, with the thesis and code. You wanted to see how awful my code is, Mickey? :)

Anyway, hooray! Now I actually have some free time for a bit. Will I actually write here more often? Uh, maybe...

-Harry

So! Juan Arias de Reyna and Jan Van de Lune recently posted to arXiv their paper "Algorithms for Determining integer complexity". In it, they A. improve the known bounds on time complexity for computing ||n||, and B. get a new bound on ||n|| that works for almost all n.

(Hey, I'm blogging about things adjacent to my work again! Well, a little, anyway. More will have to wait.)

To review -- a big problem in integer complexity is determining the limsup of ||n||/(log n), which I'll denote C_max. Certainly C_max≤3/(log 2), or about 4.328, since ||n||≤3log₂n for all n≥1; this bound follows from writing n in base 2. And Josh Zelinsky, in a paper he still needs to write, has lowered this to ||n||≤27log₁₂₆₀n for all n≥1, so C_max≤27/(log 1260), or about 3.782. The highest known value of ||n||/(log n) occurs at n=1439, for a value of 26/(log 1439), or about 3.576. This seems to be a unique occurrence, so one ought to have C_max<26/(log 1439), but the current best upper bounds have not beaten this milestone.

For comparison, if it is indeed the case that ||2^k||=2k for all k≥1, then one would have C_max≥2/(log 2), which is about 2.885; Josh has previously suggested that perhaps the limsup is exactly this number. (Though Iraids et al suggested that perhaps it's even larger.) However, at present, nobody's even been able to prove that the limsup is any greater than the liminf, which is 3/(log 3), or about 2.731 (and which is also an absolute lower bound). And indeed, various people have suggested that perhaps the limsup simply is the liminf[0]. Josh and I attempted a while ago to show it was at least slightly larger, but that ended up not working out, though I'm of the opinion it's worth re-exploring.

Anyway. So the state of C_max is not good. But we can also define a number I'll call C_avg: We'll define C_avg to be the inf of all C such that ||n||≤Clog(n) for almost all n, i.e., on a set of density 1. (So certainly 3/(log 3)≤C_avg≤C_max). And it's here that Arias de Reyna and Van de Lune have made an improvement. (But first a bit more history, if you don't mind.)

A number of people have noted that based on writing n in base 2, one can show C_avg≤5/(2log2), or about 3.607. (Already this is better than Josh's bound.) Richard Guy and John Isbell took this a step further and tried writing n in base 24, yielding a bound of C_avg≤265/(24log24), or about 3.474. (This is even better than 26/(log 1439), which the current C_max bounds are not!) Well, now, based on writing n in base 2⁹3⁶, they've shown that in fact

C_avg≤15903451/(2⁹3⁶log(2⁹3⁶))

which is about 3.321. Quite an improvement, in my opinion!

(As for the true value of C_avg, who knows. Maybe it and C_max are both equal to 2/(log 2). Well -- if C_max is at most 2/(log 2), then so is C_avg, and if C_max is equal to 3/(log 3), then so is C_avg; and if either is true, then even this new bound on C_avg is quite a ways away from the true value. Still. A substantial improvement.)

So what's going on here? How did they do this? Well, it's the same method as Richard Guy and John Isbell used, just applied with a much higher base with the help of a bit of automation. Let's go into a bit more detail.

Let's define D(b,r), as Arias de Reyna and Van de Lune do, to be the smallest number of ones needed to turn a number x into the number bx+r. That's not a formal definition, but it's not too hard to write one down; you can write down a recursion similar to that for integer complexity, allowing you to compute it algorithmically. For r=0, D(b,r) will simply be ||b||. (And for b=0, D(b,r) will simply be ||r||, though we won't care about that here.) We'll only be considering here D(b,r) for 0≤r<b, though one can consider it for r≥b as well. Note, by the way, that (excluding r=0 or b=0) one always has D(b,r)≥max(||b||,||r||). (Actually, so long as r>0, one has D(b,r)>||b||, and so long as b>0, one has D(b,r)>||r||.)

With this language, we can make some nice statements. The method of getting upper bounds on C_max by writing numbers in different bases simply becomes the statement that, for any b≥2,

C_max ≤ max_0≤r<b D(b,r)/(log b)

...or does it? It's possible I'm neglecting some subtleties with the initial digit here. Well -- it's ultimately irrelevant, because so far nobody's ever found a base that does better than base 2 for getting an upper bound on C_max! And in base 2 one does not have to worry about such things.

But what certainly is true, and much more useful, is that

C_avg ≤ avg_0≤r<b D(b,r)/(log b);

this is the method of writing things in base b to get upper bounds on C_avg. Well, Arias de Reyna and Van de Lune have done this with b=2⁹3⁶, and gotten a pretty nice bound.

But -- and now we get to part A -- this isn't the only thing they've done with the values D(b,r)! They present also in their paper an algorithm for computing ||n||, which is apparently due to Martin Fuller. Now, we already knew that you could do better than O(n²) in terms of the time required to compute ||n||; Srinivas and Shankar presented an algorithm that showed that the exponent 2 could be lowered to log₂3, or about 1.585.

Arias de Reyna and Van de Lune present a time analysis of Fuller's algorithm, and show that it runs in time O(n^α), where α is about 1.246. Interestingly, their time analysis depends on the numbers D(b,r) -- once again, you pick a base b, do computations involving D(b,r) for 0≤r<b, and get out a bound. In this case, the computation involved is rather more complicated than just taking an average, and doesn't yield a number that can be written down in a nice short exact form, but it still is a computation based on D(b,r) for 0≤r<b. The best base they found for this problem was 6⁶, which yielded the above value of α.

So, pretty neat! A little different from what I'm mostly working on, but, it's not like integer complexity is a widely-studied thing. And it shows that the numbers D(b,r) have more than one purpose, and may be worth further study.

-Harry

[0]Indeed, if instead of the integer complexity one considers the addition chain length l(n), which is similar in a number of ways (which reminds me, I've never really posted here about any of my work regarding addition chains; I should probably get around to that sometime), one has that the liminf and limsup of l(n)/(log n) are both equal to each other, both being equal to 1/(log 2).

Here's a link.

For those of you that are just tuning in: Let's define ||n|| to be the complexity of n, by which in this context we mean the smallest number of 1s needed to write n using any combination of addition and multiplication. (Note that this is the number 1, not the decimal digit 1. Allowing you to write "11" and say you've only used two 1s would just be silly.)

Then we can define the defect of n, denoted δ(n), to be the quantity ||n||-3log₃n; and we can then consider the set of all defects δ(n), as n ranges over all natural numbers. Surprisingly, this set is well-ordered, and its order type is ω^ω.

...OK, this won't be surprising to you if you've spoken to me anytime in, say, the past several years. But it should be a surprise to almost everyone else. And it's pretty damned neat regardless.

Thanks are of course due to Joshua Zelinsky -- who, after all, defined the object of study of this paper in the first place (defect, that is, not complexity) -- and to Juan Arias de Reyna who not only helped a lot with the editing but also helped organize several of the ideas in the paper in the first place. And other people, but, well, you can check the acknowledgements if you really care about that.

We'll see where I can get this published. In the meantime, this should be quite a bit more readable than the old draft sitting around on my website.

Now I guess it's on to the next paper (for now)... or rather, it already has been for a while...

So. As you probably know, I'm currently writing a paper in which I prove that a certain subset of the real numbers is well-ordered with order type ω^ω. And yes it should have been done like a month ago (or probably earlier). Real life has introduced some delays.

Anyway. The point is, in order to do this, I need to cite various set theory/order theory/point set topology stuff, to handle ordinals embedded in larger totally ordered sets (which here is always the reals). I have a section of the paper where I introduce all the stuff I need from there. I'd held off on actually writing it until pretty recently though. I didn't actually know where I'd cite the stuff from; I figured it wouldn't be too hard to find.

So Jeff suggested I ask Andreas Blass where I might find citations for these things. His response on hearing just what I wanted was, yes, that's certainly easy, but I'm actually not certain you'll find it in the literature. Try the following really old books; they cared a lot about this sort of thing around the turn of the century.

So I got the books Andreas suggested out from the library, and, unfortunately, they mostly didn't help. So, I'm having to write most of the proofs myself.

Anyway. The point of this entry was a particular thing. Say we have an ordinal α, and we let β be the set of all limit ordinals less than α. How can we express β in terms of α? Sounds easy, right? I mean it's basically just "dividing by ω", right?

Well basically yes, but if you actually want the order type on the nose, well, it's surprisingly easy to screw up. Now actually all I really need is that if α<ωⁿ⁺¹ (n finite), then β<ωⁿ, so I don't need to prove a whole formula. (Actually, I guess if you just replaced n+1 with 1+n, this statement would still be true for n infinite.) But today I sat down and figured out just what the correct formula was (because you know I coudln't find this listed anywhere) so I thought I'd record it here for reference.

First off, if α is finite, there are no limit points. Otherwise...

Say α has Cantor normal form ω^γ_ka_{γ_k} + ... + ω^γ_0a_{γ_0}, and assume that γ_0=0 (we're going to allow the a_i to be 0). Define α/ω (this may have a standard meaning but I forget, oh well) to mean ω^(γ_k)-1a_{γ_k} + ... + ω^(γ_1)-1a_{γ_1}. (When I write γ-1 for an ordinal γ, I mean subtracting the 1 off the beginning. So for a finite ordinal this is subtracting 1, and for an infinite ordinal it does nothing.)

Then the order type of β is α/ω-1 if a_0=0, and is (α/ω-1)+1 if a_0>0. (Yeah, that notation is kind of crappy -- it looks like (γ-1)+1 should just be γ (and often it is). But we're subtracting 1 off the beginning, not the end, so rather we have 1+(γ-1)=γ, while (γ-1)+1 is only γ if γ is finite. I guess what we need here is some additive equivalent of the \ that gets used for division-on-the-left in certain contexts. Oh well.

-Harry

Good (if expected) news! (Though not expected this soon, at least not by me.)

Josh's and my paper, "Numbers with Integer Complexity Close to the Lower Bound", has been accepted for publication in INTEGERS (assuming we fix two typos). And then do a proofreading pass, which I guess one of us will have to actually do.

I guess it's now a bit different than whatever the last version I uploaded to my UMich website was, but, eh, not going to bother fixing that; when it's actually published I'll just change the link...

-Harry

What with the conclusion of writing this first paper (gods willing) -- and the end of classes -- I have some brief time to actually do some *thinking* about integer complexity again before Jeff makes me get started on writing the next one[0]. (I believe much of what I am thinking about has already been solved by Juan Arias de Reyna, but I will read his solutions later; first I want to think on this myself some more.) Sorry, no details right now -- well, unless you think you can infer them from the rest of this post!

In earlier drafts (that included material we definitely did not have time to cover in this first paper) I defined a class of ternary families I called "primary ternary families". I am thinking now this was not such a good name. (Also, people keep telling me "ternary family" is a terrible name, and I assume they're probably right, but since right now I'm just talking about naming things for the purposes of my own thinking, I'm going to ignore that right now.)

Rather I am thinking that would be a better name for a slightly more general class of ternary families. (The old meaning is still important, but slightly less so.) But I've used this name long enough that I would have trouble switching it over in my mind. And perhaps a more suggestive term could be used, anyway.

The intutition is that these "primary" ternary families are somehow bulky or substantial. And with the more restricted meaning, they're even more bulky. I like the idea of calling "bulky" what previously I called "primary". But what about the more general class? "Substantial ternary family" is a bit of a mouthful. "Meaty?" No, that's a little too out there. "Solid?" Unfortunately, we ended up using "solid number" to refer to additively irreducible numbers, so that's out. Though maybe we can still change that back to the term we were using previously -- we called such numbers "chunks". I still like this better. Actually, so did Josh, but Jeff had problems with it and we decided it was more important to get the thing done than to bikeshed about the term. But I suspect Jeff slightly misunderstood how we intended to use the term, so perhaps if that is made clear he will change his mind.

Yeah, I think I'll stick with "substantial". (Anyway, these things might well end up as polynomials, and "substantial polynomial" is not so bad to say.)

-Harry

[0]Also some time to do some more coding on the classifier, which is most of what I've been doing. The core of it has been done for a long time, of course, but it still needs to be changed to use exact arithmetic, and I'd also like to add some additional output capabilities. Like maybe, "enter a real number (in a format I can work with), get back the order type of defects up to that real number". I don't know if I'll actually implement that one. Computing order type is straightforward from the existing core tools, of course; it's the reading in a real number in a potentially quite general format I find daunting. :P But I guess I can always just implement the actual function itself, and then say "open the program up with ghci if you want to use these additional features"...