Chronicles of Harry

"You should come to our meetup this week, it's going to be a movie night, we're showing Contact!"
"Contact? What's Contact?"
"Well it's about a scientist, she works at SETI, and then they get a message from aliens--"
"Oh, and then like she has to translate? I know that movie!"
"Ah, well, I think you're thinking of Arrival. That is also a movie about a female scientist who makes first contact with aliens, but it is a different movie."

An argument I've gotten into several times on the internet regards why psychological trauma occurs. There's a common idea you see that psychological trauma consists of some sort of damage to the brain's system, the result of an input that is simply too far out of range in some regard (too negative-valance, e.g.). I have often replied that this can't be right -- for one thing, out-of-range inputs may cause errors, but they do not cause damage to systems.

Well, I still maintain that I am correct regarding psychological trauma -- it fundamentally doesn't seem like that sort of thing -- but I must correct the record on the more general point -- systems can absolutely be damaged by out-of-range inputs.

The reason I thought this couldn't happen was because I was used to digital systems. In digital systems, where numbers are represented symbolically -- assuming everything is fixed-length for now -- there is simply no mechanism by which an out-of-range input could, on its own, cause damage. Now it can certainly cause a logic error, if the programmer did not think to account for such inputs. And it could also cause other problems, not due to any error in logic but simply due to the problem that it may not be clear what to do with an input that is out-of-range, such that there isn't truly such a thing as a valid response. And it is also true that, depending on what output devices such code is hooked up to, if that output device has no protection on it, then overlarge inputs that make it this far could cause damage. But even in this case, the overlarge input is not itself causing damage; rather it is a matter of the programming.

However, analog systems are different. When numbers are represented not symbolically, but rather directly by physical quantities -- positions, forces, voltages -- if that quantity grows too great it can indeed cause damage as it now violates the physical assumptions the device is engineered around. Too heavy a weight can damage a scale, for instance. An arbitrarily loud sound will shake apart a microphone. Now what you can attempt to do is to clamp the input value to a manageable range. The problem is that this is itself a place where damage can occur. Physically, to implement clamping, there must be something to *push* on the analog value to keep it in the desired range, and the more out-of-range the input, the harder it has to push. Eventually, it will break -- the out-of-range input has now damaged your clamp.

And really, digital systems aren't entirely free of this either. If they're purely digital they're fine, but if a system has to take input from the real world, that necessitates some sort of analog-to-digital conversion, which means some sort of mechanism to keep the input within range. However this sensor is implemented, whatever sort of clamp you put on it, at the interface with the real world, there is the potential for damage. (As mentioned above, output devices also allow a potential for damage, but in that case, I'd consider it the programmer's fault if that occurs, rather than the problem being intrinsic to the output device.)

(A related problem is the arbiter problem aka Buridan's principle; as Leslie Lamport wrote, "A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time." This raises the specter of an analog-to-digital conversion having problems -- and perhaps even being damaged -- not by an input that is too large or too negative, but one that is too in-the-middle.)

Now, there is one assumption here I've been making about digital systems that is not always warranted. I've been assuming that all quantities are fixed-length. Now, the number of bits needed to represent a quantity digitally grows only logarithmically with its value; as such, overlong quantities in digital systems are harder to make happen than overlarge quantities in analog systems. (This is the power of representing thing symbolically, rather than with direct physical quantities!) However, not everything in computing is fixed-length, and overlong inputs would really be the true digital analogue of overlarge inputs in analog systems. Could an overlong input to a digital system cause damage, somehow, in a way that's independent of programmer error? (E.g., if the programmer fails to create any mechanism by which computation could be limited or the computation interrupted.) Well, no, I don't think so. Ultimately it is still the programmer's responsibility to handle overlong input, it can't damage your machine directly.

Now as regards the original question, that of the brain, it is worth noting that the brain is evolved rather than designed. Such a system, even if digital, might not have ever evolved the protections on outputs that a designed system would (hopefully) have. And so in such a case overlarge input could potentially cause damage due to what, if it were a designed system, would be considered programmer error. So if we are considering evolved systems then perhaps this mechanism that I dismissed earlier should not be ignored.

Nonetheless psychological trauma does not seem like such damage, I just don't think any of those are what's going on there. Still, I was mistaken to dismiss the possiblity on purely general grounds rather than ones specific to the phenomenon.

-Harry

So when Kappa unpacked her boxes of books last year, there's two boxes she didn't open.

These two boxes weren't books she'd packed away -- they were two boxes of books sent to her by her uncle, quite some time ago; just books he thought she'd like. She'd never opened them, though, and didn't know what was inside. Well, this past weekend, she finally did that, and on doing so found that she only wanted a few of them. Thus, part 2 of the great enbookening: the other 47 went on the giveaway shelves.

It's an odd collection that we've now added. A bunch of it seems to be pulp fantasy and historical fiction, I guess? But in particular, one of the two boxes was filled almost entirely with murder mysteries set in ancient Egypt. And yeah, by a variety of authors, not just one, although there are some repeat authors in there. But we now have both "The Anubis Slayings" and "Murder in the Place of Anubis". :P (No, those aren't by the same author.)

So, that raised the count from 80 to 127. It's now back down to 124. But as these books are probably going to be less appealing than the books from the first round, it may be quite a while before it gets back down that far again...

It's out!

Look, I've talked about this here before, that I don't feel a need to recap its contents. (Edit: Oops, turns out my previous post on the matter didn't explain it either. Oh well.) But, y'know... we prove Juan Arias de Reyna's conjecture 8 on the self-similarity of the defect set, and also, we show that when if a is a stable number, then ||a3^k+1||=||a||+3k+1 for all sufficiently large k, and other related statements. There's a lot. And while I can hope not, this might end up being the best paper I'll ever write, so, yeah. If you care about integer complexity, you should go take a look.

Meanwhile, I've got another new paper up on arXiv, although really, this one is mostly Paolo Lipparini's work. It arose out of discussions he had with me, though, so he thought I deserved credit. And I did make a few alterations to the paper -- for instance, I added a mention of Norton's alterate multiplication on games, to help make that better-known. :P

OK, I realize I could say a lot more here, especially about the big paper with Arias de Reyna, but I'm tired right now, so I'm going to leave it there. Go take a look at the actual papers!

So joshuazelinsky recently sent me a link to this paper and wow!

This paper contains just two theorems but both are huge advances in integer complexity; one on the upper bound, one on the lower bound.

First the upper bound. Let's review -- what upper bounds are known on integer complexity? If one wants a bound that works for all n, well, there's the naive bound ||n||≤3log₂n, and then there's Josh's improvements on that, and that's it. The empirical maximum of ||n||/(log n) occurs at n=1439, but these bounds aren't good enough to prove that that value is indeed the maximum; they're substantial overestimates. What if you just want bounds that work for all but finitely many n, bounds on the lim sup? Sorry, we don't have any of those that aren't bounds for all n.

But we do know of better results if you just want bounds that work for almost all n, bounds on what in this post I called lim sup ap ||n||/(log n), which are obtained by the averaging method; these bounds are good enough to break the 1439 barrier, but of course they don't bound the actual lim sup. And we know of even better bounds if your idea of "almost all" only requires logarithmic density 1, rather than natural density 1; this is what I've now been denoting lim sup ap* ||n||/(log n), and the bounds come from Steinerberger and Shriver's method. The current best bounds for both of these categories come, to my knowledge, from Kazuyuki Amano's work.

Well. Konyagin and Oganesyan claim that they have shown that the averaging method actually yields an upper bound on lim sup ||n||/(log n)! Indeed, more than that -- you should just go click through to their paper and read their inequality. They have well and truly broken the 1439 barrier, proving that only finitely many numbers can have a complexity that high. Although, of course, their actual inequality comes with an error term, and having asked them, they say the error term is bad enough that their theorem doesn't currently prove that 1439 is the actual maximum. But wow! This is a massive improvement on the state of the art.

But wait, their next theorem is equally impressive. For a long time, nobody's been able to get a nontrivial lower bound on lim sup ||n||/(log n) either. By "nontrivial" here I mean "better than the known liminf, 3/(log 3)". It was an open question whether ||n|| was asymptotic to 3log₃n, and some people thought it was, even though this would mean that ||2^k||=2k would have to fail for large k! Well, Konyagin and Oganesyan say they've now done it -- they've proven a lower bound on lim sup ||n||/(log n) that is larger than the trivial one, showing that ||n|| is not asymptotic to 3log₃n after all.

Except, they're actually claiming something much stronger. Getting a lower bound on the lim sup would mean showing that infinitely many n have ||n||/(log n) above the bound. They say they've shown that in fact, almost all n do.

So this isn't just a lower bound on the lim sup -- it's a lower bound on the lim inf ap! That's basically as good as you could do!

Their proof here is actually based on my work with joshuazelinsky on the defect. At a high level, their approach is to first use our iterative classification theorem -- yes, the original one, they're not using low-defect polynomials -- to establish upper bounds on how many leaders below x have defect in the range (k-1)σ to kσ, where σ is the variable they're using to denote their step size (they pick σ=0.48), with these upper bounds, importantly, being uniform in both x and k. (This is the hard part.) Once they've done that, they apply this to count how many numbers n below a bound x have ||n||<(3+γ)log₃n, where γ is a number they've picked for this to work (they pick γ=0.06), and compute that, oh look, it's o(x). Therefore, almost all numbers have ||n||/(log n) above this bound. Tada!

Josh and I actually worked on a similar idea many years ago (ours didn't require picking a step size below 1; we were looking at defects inbetween the integers k-1 and k, and of course were working based on low-defect polynomials), although I'm unsure if Josh's method would have been good enough to show that it worked for almost all n rather than just infinitely many; if it was, we didn't realize it. But ultimately it didn't work out because we couldn't prove those uniform bounds we needed. But Konyagin and Oganesyan say they've done it!

I do have to wonder about the choice of σ. I would expect larger values of σ to yield better results, so it's surprising to me that they picked it so far below what it could have been. I have asked them about this, however, and they are of the opinion that larger σ would probably not yield much better results. Still, we'll see if anyone manages to do any better with their ideas.

(It's possible they picked σ<½ so that they could start with B_σ and B_2σ both already known, using Josh's and my work classifying numbers with defect less than 1. Of course, my algorithms can be used to compute all numbers with defect less than 2, but maybe they didn't know about this. I've since sent them the output of such a calculation, just in case they can make use of it. Like I said, their opinion was that larger σ wouldn't be much better, but we'll see.)

Now the question becomes, is it all correct? Unfortunately, their arguments are quite analysis-heavy, and so I am not the best person to evaluate them. So right now my answer can only be "I don't know". But I'm hopeful!

-Harry

Someone else has written about Snake!

You might remember my webpage on the problem, which unfortunately they don't seem to have turned up in their lit review (I guess that's what happens when you don't publish properly :P ).

But these people are studying the same problem and have turned up some cool new results!

One thing to beware of, they numbered their theta graphs differently than I did. Their Θ(2,2,k) is my Θ_1,1,k-1.

But: They showed that if G is bipartite with an odd number of vertices, then the only way it can be winnable is to include some Θ_1,1,k as a spanning subgraph. As a consequence, they derive that determining winnability is NP-hard!

Moreover, they showed that if a winnable graph does not have a Hamilton cycle, it must have girth at most 6, something I certainly never thought of! They also have an example to show that this is tight, but the example seems incorrect, in that it seems to have a Hamilton cycle? Regardless though the bound is tight, as is shown by Θ_2,2,2.

Note that while I didn't put it on the webpage, I also had an inequality about cycles, only mine was about the largest cycle. I've probably written about it here before, but: Let c(G) be the length of the largest cycle, and let k(G) be the size of the largest clique that can be found at the end of a Hamilton path. Then for a winnable graph G with n vertices, k(G)+c(G)≥n, meaning in particular that c(G)≥n/2. But I never looked at the smallest cycle!

Anyway yeah cool results! Obviously I've written to them. :)

-Harry

People keep needlessly adding vowels to things, and I think it'd be better if they didn't.

The other day my roommate Geoff received a package via the US Postal Service -- the USPS. He decidedly to jokingly pronounce this initialism as if it were a word -- "uspis", he said. (Sorry, no, I'm not going to bother with IPA or anything here.)

Except... "uspis"? No. That should be "usps". One syllable. There isn't a need to add an additional vowel between the "p" and the "s"; not only is it perfectly pronounceable as-is, but that combination of sounds even occurs in such common English words as "wasps". It shouldn't be any sort of phonotactic problem for an English speaker.

I see this sort of thing commonly and it bugs me -- people adding vowels and syllables where they just don't need to. Now I realize that adding vowels requires less thinking -- it's easier to just separate consonants with vowels than think about how to form them into clusters -- and that in many cases there just isn't any reason for people to put in that extra effort, because, they're, y'know, just trying to pronounce something quickly. (Although it seems to me that there are many cases where people add vowels even when no effort is required!) But when you're doing it deliberately for humor value then you'd want to try to optimize that, right? And consonant clusters are funnier than extra vowels! Like, "snunch" is funnier than "sanunnich", right? Sure, an Italian would have trouble with it, but this is English; we're known for our weird consonant clusters, they shouldn't be difficult for us.

Let's consider the exampe of "Fblthp". "Fblthp" is the name of a character from Magic: The Gathering, introduced in 2013 in the flavor text of the card Totally Lost. He's a homunculus, and his name has no vowels on it. People found the flavor text funny and so Fblthp reappeared and eventually got his own card. This also led to a more general pattern in Magic of homunculi receving names with no vowels in their spellings -- Zndrsplt, Vnxwt. But let's focus on Fblthp.

People generally tend to pronounce the name "Fblthp" as "fibble-thip" (yes sorry no IPA). And "fibble-thip" is a pretty funny name! But what would be funnier is reading "Fblthp" as it is written, which is totally doable. "Fb" is the onset; "l" is the nucleus; "thp" is the coda. One syllable, no vowels. Yeah not all of those clusters are permitted in English -- but that's part of what makes it funny! And look -- I'm not actually a linguist, y'know? Hell, I'm not even actually a conlanger -- I'm just a guy who reads about linguistics or conlanging sometimes. I'm a monolingual English speaker. There's all *sorts* of clusters that occur in other languages that I can't pronounce. I can't say "Gbagbo" or "Nguyen". Hell, I still can't tell an aspirated consonant from an unaspirated one. But I can say "Fblthp" no problem -- no vowels.

I want to break this down a bit more -- part of the humor is the fact that the name is so alien, right? Not having vowels (or at least none in the spelling) is an alien feature. If you pronounce it as "fibble-thip", you're making it less alien and less humorous. Don't add vowels!

Now for "Zndrsplt" or "Vnwxt" I have no idea how you do that. For those I have to add at least some vowels. Still it bugs me how people add more vowels/syllables than they need to -- like, "Vnwxt" generally gets rendered as three syllables, when it only needs to be two. People pronounce that "wxt" as if it were "wixit", but it could easily be "wixt". Again, this consonant cluster occurs in English words like "betwixt" -- an English speaker should be able to say it no problem! Why are people acting like they can't?

(Another common example is "Cthulhu". Why add a vowel between the "c" and the "th"? Yes, it's an unusual consonant cluster... but that's what makes it sound alien! And like it's not even *that* alien, it occurs in the word "cthonic" for instance. I can say "cth" a hell of a lot easier than I can say "gb" (which I basically just can't), as I noted above. Go with the more alien-sounding pronunciation! I like to draw the syllable break between the "l" and the "h" -- "Cthul-hu". Most people leave the second "h" silent. Bah. What's the point of it then? Anyway I think my way sounds cooler. :P )

Point is, consonant clusters are cool, complex consonant clusters are cooler, people should use more of them in their made-up words; adding extra vowels to break them up is lame and people should do less of that.

-Harry

We're down to just 120 books left! And the origami supplies are all gone, too...

I never properly wrote about this question here -- only obliquely referred to it here with the text "proving it seems annoying" -- but now it has an answer!

This is a question about automatic sets, so I should probably explain what those are, since a lot of you won't know. A b-automatic set is a set of whole numbers which is given by, you have some DFA on the alphabet {0,...,b-1}, you write numbers in base b and run them through the DFA, and the numbers it accepts are the ones it accepts. (And an automatic set is a b-automatic set for some b. There are also automatic sequences, where instead of just accept/reject, the DFA returns some other output. But we'll stick to sets here.)

Now, there's a number of questions you might have here about the details, but the concept is actually quite robust to small modifications and so precisely how you handle the details in your definition is just not going to matter. For instance, do you write numbers little-endian or big-endian? It doesn't matter, because regular languages are closed under reversal.

For the purposes of this question, though, that particular detail will matter: We're going to assume numbers are fed into the machine little-end first.

So let's say we have a b-automatic set, and it's given by a machine M when the numbers are written from the little end. And let's suppose that M has a particular property: That from every state, it is possible to reach a "sink state" -- a state that only ever loops back to itself. In this case, we can meaningfully ask the question, if we feed into M a uniformly random string of digits, with what probability does it accept? Since with probability 1, it will always hit a sink state eventually, and then we can judge acceptance or rejection by that. Let's call this probability p(M).

The question, then, is: Say S is the automatic set determined by M. Is d(S), the natural density of S, equal to p(M)?

It sure seemed like the answer should be yes, because both can be thought of as plugging random digits into M. But I couldn't prove it! And surprisingly, I couldn't find any results on this in the literature, either. Now I'm no expert on automatic sets, so I could have missed something, but still, I couldn't find it. People said the problem sounded easy -- and then produced proofs that were incorrect. No correct ones.

Well, I asked around, I asked on MathOverflow, and now, a year and a half later, I finally got an answer, due to Alex Mennen. Yes it's true, and it turns out it really wasn't that hard after all! I'm just not much of an analyst. :P

(On MathOverflow, after feedback from Jeffrey Shallit, I ended up reformulating the question a bit; but the version I posted is in fact equivalent to my original version, and also, my original version is what Mennen ended up proving.)

But, the problem as stated above wasn't really what I wanted. Let's throw in some complications.

Complication #1: Multidimensional sets. One can define multidimensional b-automatic sets, subsets of N^k, where the alphabet is {0,...,b-1}^k. Does it still work here?

Complication #2: The set I cared about wasn't actually a b-automatic set at all, but a Fibonacci-automatic set, where the input is in Zeckendorf! (So, some parts of the setup above have to be appropriately modified; the distribution on digit strings is no longer uniform, for instance.) Can we get it to work here?

Complication #3: Actually, it was a 2-dimensional Fibonacci-automatic set.

Fortunately I was able to modify Mennen's proof to handle these complications (going to multiple dimensions is easy; handling Fibonacci required slightly more work). So yay, it's true!

But, there's more we could ask about. Like, what about other numeral systems? Yeah, I don't want to go there. (Handling bijective base-b I'm pretty sure should work the same by the same proof. I expect dual Zeckendorf should also work, but I haven't tried. But those are minor variations.)

And the other question I have to wonder about is... what about the big end? If we feed in numbers from the big end, then it's easy to come up with counterexamples; but maybe it would work if instead of natural density we used logarithmic density? (Recall, logarithmic density isn't really a separate quantity from natural density -- it just exists more often.) The failures I've seen in the big-endian case have always been of the form "the natural density doesn't exist", not "the natural density exists but has the wrong value". I'm guessing it's probably true! But again, I don't really want to be the one to do it.

Jeff says I should write this up as a paper along with Alex Mennen, which, yeah, I guess I should. Kind of annoying, because it'll push other things back. But, oh well, one more thing for the backlog I guess. Still, first I think I might ask around a bit more, see if anyone knows of a result like this already out there. If it's just something I can cite, great! But my guess is that even if someone has done it for base b, they probably wouldn't have done it for Fibonacci...

-Harry

The "numbers rant" is someting I've posted various places on the internet in the past, but it seems like I've never posted it here. Figured made sense to get it down here. So, sure. Here we go.

People who haven't seriously studied mathematics might reasonably assume that mathematicians have a unified notion of "number". There are numbers, you can add them, you can subtract them, you can multiply them, you can divide them (except by 0). Sometimes you might restrict to a particular subset of the numbers, like the integers or the real numbers.

The way people learn about numbers in elementary and high school reinforces this. First you learn about whole numbers; then fractions; then negative numbers; at some point you learn there are irrational numbers, implicitly passing from rational numbers to real numbers without learning just what that really means; and then finally you add in complex numbers. And that's all the numbers.

(If you're a bit more into mathematics, you maybe hear that there's some sort of infinities or something, like ℵ₀ and ℵ₁ or something? You don't learn that in school, but you hear about it elsewhere, and you're not sure how it fits into the above picture, but surely it does.)

This picture is wrong, and moreover, I think it encourages some bad ways of thinking. There is no unified notion of "number" in mathematics. Rather, mathematicians use different systems of numbers -- the integers, the rational numbers, the real numbers, the complex numbers -- depending on context. Some of these systems embed into larger ones; the integers embed into the real numbers, for instance. But the integers can also be considered separately from the real numbers.

OK, so what, you might stay. It still sounds like the complex numbers are all the numbers, and sometimes we just focus on subsets of them. Well, they're not.

One way this is false is that you can expand further on the complex numbers -- like, the 2-dimensional complex numbers embed in the 4-dimensional quaternions. But that's sort of a silly way this is false. If that were the only reason this were false, then it would just be the case that the quaternions were all the numbers. But they aren't! And no, not just because you can expand on them to the octonions, etc.

Rather the key point here is that there are distinct number systems that are entirely incompatible with one another. We've already mentioned an example above -- cardinal numbers. Cardinal numbers include (and are therefore compatible with) the whole numbers; but they're incompatible with negative numbers, let alone real numbers or complex numbers. How do you add ℵ₀+½? You don't! This is a nonsense sum, because you're trying to add two numbers from entirely different systems. You have to work within some specified system of numbers; there isn't some overall general thing called "numbers" where you can take any two of them and add them together.

There are many more systems of numbers; for instance, there are the p-adic numbers, which is not one system but a family of systems, one for every prime p (the 2-adic numbers, the 3-adic numbers, etc). The p-adic numbers (for some fixed p) can be thought of as base-p expansions, except that, whereas in the real numbers, base-p expansions can go finitely far to the left and infinitely far to the right, p-adic numbers can go infinitely far to the left and finitely far to the right. (Note that, as mentioned above, different values of p yield different, incompatible systems; this is in contrast to the real numbers, where, regardless of what base you write it in, it's still the real numbers.) How do you add a p-adic number to a real number? You don't! These are incompatible systems. Now, the p-adic numbers always contain the rational numbers; so if the p-adic number and the real number you're adding are both rational numbers, then sure you could perform the addition within the rational numbers; but there is no more general system that contains both the p-adics and the reals and allows you to add one to the other without special additional knowledge, they're not compatible.

So, there is no unified mathematical notion of "number". Or as I sometimes put it, there's no such thing as a number.

There's something else that bothers me about the way number systems are taught, beyond just that it's wrong, though. It's that if you present things as if complex numbers are all the numbers, it puts the focus on complex numbers as the most fundamental type of numbers. It's like, complex numbers, that's the real meaning of numbers, why would we focus on silly particular subsets like the integers? Presenting the complex numbers as "all the numbers" devalues number theory. It suggests complex numbers as the most fundamental thing, when of course, in reality, whole numbers are the most fundamental thing; other number systems are built on top of the whole numbers, and much of what they do is in a sense just reflecting on and elucidating properties of the whole numbers.

(It's also worth noting that it's important to pick the correct number system for your application. Many people use the real numbers without thinking about it because they're not aware of other possibilities. To be fair, the real numbers are indeed very useful and frequently the right answer, but it's still worth thinking about.)

Annoyingly, there's no formal mathematical definition of a "number system" -- most things we might consider "number systems" are rings or at least semirings, but some fail these criteria (ordinals with their usual arithmetic are just a near-semiring). And of course plenty of rings and semirings are of things we wouldn't normally consider "numbers". Still -- numbers come in systems; different systems are used for different purposes, so pick one that matches your purpose; and there's no such thing as "all the numbers".

That's the numbers rant!

-Harry

PS: If you want a semi-trollish take, one could argue that p-adic numbers are numbers, but complex numbers aren't, because only systems lacking nontrivial automorphisms should be deemed systems of numbers. :P (Because a number should have some sort of absolute meaning, and if there's a nontrivial automorphism, then it doesn't.)