Archive:
Subtopics:
Comments disabled |
Sun, 03 Dec 2023 Over the weekend a Gentle Reader sent me an anecdote about getting lost in a Czech zoo. He had a map with a compass rose, and the points of the compass were labeled SVZJ. Gentle Reader expected that S and V were south and west, as they are in many European languages. (For example, Danish has syd and vest; English has “south” and “vvest” — sorry, “west”. Unfortunately in Czech, S and V are sever, “north”, and východ, east. Oops. A while back I was thinking about the names of the cardinal directions in Catalán because I was looking at a Catalán map of the Sagrada Família, and observed that the Catalán word for east, llevant is a form of _llevar, which literally means “to rise”, because the east is where the sun rises. (Llevar is from Latin levāre and is akin to words like “levity” and “levitate”.) Similarly the Latin word for “east” is oriēns, from orior, to get up or to arise. I looked into the Czech a little more and learned that východ, “east”, is also the Czech word for “exit”: “Aha,” I said. “They use východ for “east” not because that's where the sun comes up but because that's where it enters…” “…” “Uh…” No. Entrance is not exit. Východ is exit. Entrance is vchod. I dunno, man. I love the Czechs, but this is a little messed up. Addenda
[Other articles in category /lang/etym] permanent link Sat, 02 Dec 2023Content warning: grumpy complaining. This was a frustrating month. Need an intuitive example for how "P is necessary for Q" means "Q⇒P"?This kind of thing comes up pretty often. Why are there so many ways that the logical expression !!Q\implies P!! can appear in natural language?
Strange, isn't it? !!Q\land P!! is much simpler: “Both !!Q!! and !!P!! are true” is pretty much it. Anyway this person wanted an intuitive example of “!!P!! is necessary for !!Q!!” I suggested:
Again this follows the principle that rule enforcement is a good thing when you are looking for intuitive examples. Keeping ticketless people off the train is something that the primate brain is wired up to do well. My first draft had “board a train” in place of “board a certain train”. One commenter complained:
I was (and am) quite disgusted by this pettifogging.
OP had only asked for an example, not some universal principle. Does ...999.999... = 0?This person is asking one of those questions that often puts Math StackExchange into the mode of insisting that the idea is completely nonsensical, when it is actually very close to perfectly mundane mathematics. (Previously: [1] [2] [3] ) That didn't happen this time, which I found very gratifying. Normally, decimal numerals have a finite integer part on the left of the decimal point, and an infinite fractional part on the right of the decimal point, as with (for example) !!\frac{13}{3} = 4.333\ldots!!. It turns out to work surprisingly well to reverse this, allowing an infinite integer part on the left and a finite fractional part on the right, for example !!\frac25 = \ldots 333.4!!. For technical reasons we usually do this in base !!p!! where !!p!! is prime; it doesn't work as well in base !!10!!. But it works well enough to use: If we have the base-10 numeral !!\ldots 9999.0!! and we add !!1!!, using the ordinary elementary-school right-to-left addition algorithm, the carry in the units place goes to the tens place as usual, then the next carry goes to the hundreds place and so on to infinity, leaving us with !!\ldots 0000.0!!, so that !!\ldots 9999.0!! can be considered a representation of the number !!-1!!, and that means we don't need negation signs. In fact this system is fundamental to the way numbers are represented in computer arithmetic. Inside the computer the integer !!-1!! is literally represented as the base-2 numeral !!11111111\;11111111\;11111111\;11111111!!, and when we add !!1!! to it the carry bit wanders off toward infinity on the left. (In the computer the numeral is finite, so we simulate infinity by just discarding the carry bit when it gets too far away.) Once you've seen this a very reasonable next question is whether you can have numbers that have an infinite sequence of digits on both sides. I think something goes wrong here — for one thing it is no longer clear how to actually do arithmetic. For the infinite-to-the-left numerals arithmetic is straightforward (elementary-school algorithms go right-to-left anyway) and for the standard infinite-to-the-right numerals we can sort of fudge it. (Try multiplying the infinite decimal for !!\sqrt 2!! by itself and see what trouble you get into. Or simpler: What's !!4.666\ldots \times 3!!?) OP's actual question was: If !!\ldots 9999.0 !! can be considered to represent !!-1!!, and if !!0.9999\ldots!! can be considered to represent !!1!!, can we add them and conclude that !!\ldots 9999.9999\ldots = 0!!? This very deserving question got a good answer from someone who was not me. This was a relief, because my shameful answer was pure shitpostery. It should have been heavily downvoted, but wasn't. The gods of Math SE karma are capricious. Why define addition with successor?Ugh, so annoying. OP had read (Bertrand Russell's explanation of) the Peano definition of addition, and did not understand it. Several people tried hard to explain, but communication was not happening. Or, perhaps, OP was more interested in having an argument than in arriving at an understanding. I lost a bit of my temper when they claimed:
I didn't say:
although I wanted to at first. The reply I did make is still not as measured as I would like, and although it leaves this point implicit, the point is still there. I did at least shut up after that. I had answered OP's question as well as I was able, and carrying on a complex discussion in the comments is almost never of value. Why is Ramanujan considered a great mathematician?This was easily my best answer of the month, but the question was deleted, so you will only be able to see it if you have enough Math SE reputation. OP asked a perfectly reasonable question: Ramanujan gets a lot of media hype for stuff like this: $${\sqrt {\phi +2}}-\phi ={\cfrac {e^{{-2\pi /5}}}{1+{\cfrac {e^{{-2\pi }}}{1+{\cfrac {e^{{-4\pi }}}{1+{\cfrac {e^{{-6\pi }}}{1+\,\cdots }}}}}}}}$$ which is not of any obvious use, so “why is it given such high regard?” OP appeared to be impugning a famous mathematician, and Math SE always responds badly to that; their heroes must not be questioned. And even worse, OP mentioned the notorious non-fact that $$1+2+3+\ldots =-\frac1{12}$$ which drives Math SE people into a frothing rage. One commenter argued:
I think this is fatuous. OP is right here, and the commenter is wrong. Mathematicians are not considered great because they produce wacky and impractical equations. They are considered great because they solve problems, invent techniques that answer previously impossible questions, and because they contribute insights into deep and complex issues. Some blockhead even said:
Bullshit. Mathematics is about trying to understand stuff, not about taping a banana to the wall. I replied:
My answer to OP elaborated on this point:
I then discussed Hardy's book on the work he did with Ramanujan and Hardy's own estimation of Ramanujan's work:
So if OP wanted a substantive and detailed answer to their question, that would be the first place to look. I also did an arXiv search for “Ramanujan” and found many recent references, including one with “applications to the Ramanujan !!τ!!-function”, and concluded:
The question was closed as “opinion-based” (a criticism that I think my answer completely demolishes) and then it was deleted. Now if someone else trying to find out why Ramanujan is held in high regard they will not be able to find my factual, substantive answer. Screw you, Math SE. This month we both sucked. [Other articles in category /math/se] permanent link Fri, 01 Dec 2023
Obsolete spellings and new ligatures in the names of famous persons
There's this technique you learn in elementary calculus called l'Hospital's rule or l'Hôpital's rule, depending on where and when you learned it. It's named for Guillaume l'Hospital or Guillaume l'Hôpital. In modern French the ‘s’ is silent before certain consonants, and sometime in the 18th century it became standard to omit it, instead putting a circumflex over the preceding vowel to show that the ‘s’ was lurking silently. You can see the same thing in many French words, where the relationship with English becomes clear if you remember that the circumflex indicates a silent letter ‘s’. For example
and of course
But the spelling change from ‘os’ to ‘ô’ didn't become common until the 18th century and l'Hôpital, who died in 1704, spelled his name the old way, as “l'Hospital”. The spelling with the circumflex is in some sense an anachronism. I've always felt a little funny about this. I suppose the old spelling looks weird to francophones but I'm not a francophone and it seems weird to me to spell it in a way that l'Hospital himself would not have recognized. For a long time I felt this way about English names also, and spelled Shakespeare's name “Shakspere”. I eventually gave up on this, because I thought it would confuse people. But I still think about the question every time I have to spell it and wonder what Shakespeare would have thought. Perhaps he would have thought nothing of it, living as he did in a time of less consistent orthography. To find out the common practice, I went to the German Wikipedia page for Karl Gauss, for whom there a similar issue arises. They spell it the modern way, “Gauß”. But now another issue intrudes: They spell it “Carl” and not “Karl”! If the name were completely modernized, wouldn't it be “Karl Gauß” and not “Carl Gauß”? Is “Carl” still a thing in German? Gauss is glowering down at me from his picture on an old ten-mark banknote I keep on my wall, so I checked just now and Deutsche Bundesbank also spells it ”Carl Gauß”. (The caption sprouts forth from his left shoulder.) Now I wonder why I checked the German Wikipedia for Gauss before checking the French Wikipedia for l'Hôpital. Pure stupidity on my part. French Wikipedia uniformly spells it the modern way, with the circumflex. I suppose I will have to change my practice, and feel the same strangeness whenever I write “Gauß” or “l'Hôpital” as I do when I write “Shakespeare”. Addenda
[Other articles in category /lang] permanent link Mon, 27 Nov 2023
Uncountable sets for seven-year-olds
I was recently talking to a friend whose seven-year old had been reading about the Hilbert Hotel paradoxes. One example: The hotel is completely full when a bus arrives with 53 passengers seeking rooms. Fortunately the hotel has a countably infinite number of rooms, and can easily accomodate 53 more guests even when already full. My friend mentioned that his kid had been unhappy with the associated discussion of uncountable sets, since the explanation he got involved something about people whose names are infinite strings, and it got confusing. I said yes, that is a bad way to construct the example, because names are not infinite strings, and even one infinite string is hard to get your head around. If you're going to get value out of the hotel metaphor, you waste an opportunity if you abandon it for some weird mathematical abstraction. (“Okay, Tyler, now let !!\mathscr B!! be a projection from a vector bundle onto a compact Hausdorff space…”) My first attempt on the spur of the moment involved the guests belonging to clubs, which meet in an attached convention center with a countably infinite sequence of meeting rooms. The club idea is good but my original presentation was overcomplicated and after thinking about the issue a little more I sent this email with my ideas for how to explain it to a bright seven-year-old. Here's how I think it should go. Instead of a separate hotel and convention center, let's just say that during the day the guests vacate their rooms so that clubs can meet in the same rooms. Each club is assigned one guest room that they can use for their meeting between the hours of 10 AM to 4 PM. The guest has to get out of the room while that is happening, unless they happen to be a member of the club that is meeting there, in which case they may stay. If you're a guest in the hotel, you might be a member of the club that meets in your room, or you might not be a member of the club that meets in your room, in which case you have to leave and go to a meeting of one of your clubs in some other room. We can paint the guest room doors blue and green: blue, if the guest there is a member of the club that meets in that room during the day, and green if they aren't. Every door is now painted blue or green, but not both. Now I claim that when we were assigning clubs to rooms, there was a club we missed that has nowhere to meet. It's the Green Doors Club of all the guests who are staying in rooms with green doors. If we did assign the Green Doors Club a guest room in which to meet, that door would be painted green or blue. The Green Doors Club isn't meeting in a room with a blue door. The Green Doors Club only admits members who are staying in rooms with green doors. That guest belongs to the club that meets in their room, and it isn't the Green Doors Club because the guest's door is blue. But the Green Doors Club isn't meeting in a room with a green door. We paint a door green when the guest is not a member of the club that meets in their room, and this guest is a member of the Green Doors Club. So however we assigned the clubs to the rooms, we must have missed out on assigning a room to the Green Doors Club. One nice thing about this is that it works for finite hotels too. Say you have a hotel with 4 guests and 4 rooms. Well, obviously you can't assign a room to each club because there are 16 possible clubs and only 4 rooms. But the blue-green argument still works: you can assign any four clubs you want to the four rooms, then paint the doors, then figure out who is in the Green Doors Club, and then observe that, in fact, the Green Doors Club is not one of the four clubs that got a room. Then you can reassign the clubs to rooms, this time making sure that the Green Doors Club gets a room. But now you have to repaint the doors, and when you do you find out that membership in the Green Doors Club has changed: some new members were admitted, or some former members were expelled, so the club that meets there is no longer the Green Doors Club, it is some other club. (Or if the Green Doors Club is meeting somewhere, you will find that you have painted the doors wrong.) I think this would probably work. The only thing that's weird about it is that some clubs have an infinite number of members so that it's hard to see how they could all squeeze into the same room. That's okay, not every member attends every meeting of every club they're in, that would be impossible anyway because everyone belongs to multiple clubs. But one place you could go from there is: what if we only guarantee rooms to clubs with a finite number of members? There are only a countably infinite number of clubs then, so they do all fit into the hotel! Okay, Tyler, but what happens to the Green Door Club then? I said all the finite clubs got rooms, and we know the Green Door Club never gets a room, so what can we conclude? It's tempting to try to slip in a reference to Groucho Marx, but I think it's unlikely that that will do anything but confuse matters. [ Previously ] [ Update: My friend said he tried it and it didn't go over as well as I thought it might. ] [Other articles in category /math] permanent link Sun, 26 Nov 2023
A Qmail example of dealing with unavoidable race conditions
[ I recently posted about a race condition bug reported by Joe Armstrong and said “this sort of thing is now in the water we swim in, but it wasn't yet [in those days of olde].” This is more about that. ] I learned a lot by reading everything Dan Bernstein wrote about
the design of (I know someone wants to ask what about Postfix? At the time Qmail was released, Postfix was still called ‘VMailer’. The ‘V’ supposedly stood for “Venema” but the joke was that the ‘V’ was actually for “vaporware” because that's what it was.) A few weeks ago I was explaining one of Qmail's data structures to a junior programmer. Suppose a local user queues an outgoing message that needs to be delivered to 10,000 recipients in different places. Some of the deliveries may succeed immediately. Others will need to be retried, perhaps repeatedly. Eventually (by default, ten days) delivery will time out and a bounce message will be delivered back to the sender, listing the recipients who did not receive the delivery. How does Qmail keep track of this information? 2023 junior programmer wanted to store a JSON structure or something. That is not what Qmail does. If the server crashes halfway through writing a JSON file, it will be corrupt and unreadable. JSON data can be written to a temporary file and the original can be replaced atomically, but suppose you succeed in delivering the message to 9,999 of the 10,000 recipients and the system crashes before you can atomically update the file? Now the deliveries will be re-attempted for those 9,999 recipients and they will get duplicate copies. Here's what Qmail does instead. The file in the queue directory is in the following format:
where ■ represents a zero byte. To 2023 eyes this is strange and uncouth, but to a 20th-century system programmer, it is comfortingly simple. When Qmail wants to attempt a delivery to If delivery does succeed, Qmail updates the
The update of a single byte will be done all at once or not at all. Even writing two bytes is riskier: if the two bytes span a disk block boundary, the power might fail after only one of the modified blocks has been written out. With a single byte nothing like that can happen. Absent a catastrophic hardware failure, the data structure on the disk cannot become corrupted. Mail can never be lost. The only thing that can go wrong here is if the local system crashes in between the successful delivery and the updating of the byte; in this case the delivery will be attempted again, to that one user. Addenda
[Other articles in category /prog] permanent link Sat, 25 Nov 2023
Puzzling historical artifact in “Programming Erlang”?
Lately I've been reading Joe Armstrong's book Programming Erlang, and today I was brought up short by this passage from page 208:
Can you guess the obscure bug? I don't think I'm unusually skilled at concurrent systems programming, and I'm certainly no Joe Armstrong, but I thought the problem was glaringly obvious:
I scratched my head over this for quite some time. Not over the technical part, but about how famous expert Joe Amstrong could have missed this. Eventually I decided that it was just that this sort of thing is now in the water we swim in, but it wasn't yet in the primeval times Armstrong was writing about. Sometimes problems are ⸢obvious⸣ because it's thirty years later and everyone has thirty years of experience dealing with those problems. Another exampleI was reminded of a somewhat similar example. Before the WWW came, a sysadmin's view of network server processes was very different than it is now. We thought of them primarily as attack surfaces, and ran as few as possible, as little as possible, and tried hard to prevent anyone from talking to them. Partly this was because encrypted, authenticated communications
protocols were still an open research area. We now have When the Web came along, every sysadmin was thrust into a terrifying new world in which users clamored to write network services that could be talked to at all times by random Internet people all over the world. It was quite a change. [ I wrote more about system race conditions, but decided to postpone it to Monday. Check back then. ] [Other articles in category /prog] permanent link Fri, 24 Nov 2023
Math SE report 2023-09: Sense and reference, Wason tasks, what is a sequence?
Proving there is only one proof?OP asks:
This was actually from back in July, when there was a fairly substantive answer. But it left out what I thought was a simpler, non-substantive answer: For a given theorem !!T!! it's actually quite simple to prove that there is (or isn't) only one proof of !!T!!: just generate all possible proofs in order by length until you find the shortest proofs of !!T!!, and then stop before you generate anything longer than those. There are difficult and subtle issues in provability theory, but this isn't one of them. I say “non-substantive” because it doesn't address any of the possibly interesting questions of why a theorem would have only one proof, or multiple proofs, or what those proofs would look like, or anything like that. It just answers the question given: is it possible to prove that there is only one shortest proof. So depending on what OP was looking for, it might be very unsatisfying. Or it might be hugely enlightening, to discover that this seemingly complicated question actually has a simple answer, just because proofs can be systematically enumerated. This comes in handy in more interesting contexts. Gödel showed that arithmetic contains a theorem whose shortest proof is at least one million steps long! He did it by constructing an arithmetic formula !!G!! which can be interpreted as saying:
If !!G!! is false, it can be proved (in less than one million steps) and our system is inconsistent. So assuming that our axioms are consistent, then !!G!! is true and either:
Which is it? It can't be (1) because there is a proof of !!G!!: simply generate every single proof of one million steps or fewer, and check at the last line of each one to make sure that it is not !!G!!. So it must be (2). What counts as a sequence, and how would we know that it isn't deceiving?This is a philosophical question: What is a sequence, really? And:
And several other related questions that are actually rather subtle: Is a sequence defined by its elements, or by some external rule? If the former how can you know when a sequence is linear, when you can only hope to examine a finite prefix? I this is a great question because I think a sequence, properly construed, is both a rule and its elements. The definition says that a sequence of elements of !!S!! is simply a function !!f:\Bbb N\to S!!. This definition is a sort of spherical cow: it's a nice, simple model that captures many of the mathematical essentials of the thing being modeled. It works well for many purposes, but you get into trouble if you forget that it's just a model. It captures the denotation, but not the sense. I wouldn't yak so much about this if it wasn't so often forgotten. But the sense is the interesting part. If you forget about it, you lose the ability to ask questions like
If all you have is the denotation, there's only one way to answer this question:
and there is nothing further to say about it. The question is pointless and the answer is useless. Sometimes the meaning is hidden a little deeper. Not this time. If we push down into the denotation, hoping for meaning, we find nothing but more emptiness:
We could keep going down this road, but it goes nowhere and having gotten to the end we would have seen nothing worth seeing. But we do ask and answer this kind of question all the time. For example:
Are sequences !!S_1!! and !!S_2!! the same sequence? Yes, yes, of course they are, don't focus on the answer. Focus on the question! What is this question actually asking? The real essence of the question is not about the denotation, about just the elements. Rather: we're given descriptions of two possible computations, and the question is asking if these two computations will arrive at the same results in each case. That's the real question. Well, I started this blog article back in October and it's still not ready because I got stuck writing about this question. I think the answer I gave on SE is pretty good, OP asked what is essentially a philosophical question and the backbone of my answer is on the level of philosophy rather than mathematics. [ Addendum: On review, I am pleasantly surprised that this section of the blog post turned out both coherent and relevant. I really expected it to be neither. A Thanksgiving miracle! ] Can inequalities be added the way that equations can be added?OP says:
I have a theory that if someone is having trouble with the intuitive meaning of some mathematical property, it's a good idea to turn it into some questions involving allocation of resources, or who has more of some commodity, because human brains are good at monkey tasks like seeing who got cheated when the bananas were shared out. About ten years ago someone asked for an intuitive explanation of why you could add !!\frac a2!! to both sides of !!\frac a2 < \frac b2!! to get !!\frac a2+\frac a2 < \frac a2 + \frac b2!!. I said:
I tried something similar this time around:
Then the baker trades your bag !!b!! for a bigger bag !!d!!.
Someday I'll write up a whole blog article about this idea, that puzzles in arithmetic sometimes become intuitively obvious when you turn them into questions about money or commodities, and that puzzles in logic sometimes become intuitively obvious when you turn them into questions about contract and rule compliance. I don't remember why I decided to replace the djinn with a baker this time around. The cookies stayed the same though. I like cookies. Here's another cookie example, this time to explain why !!1\div 0.5 = 2!!. What is the difference between "for all" and "there exists" in set builder notation?This is the same sort of thing again. OP was was asking about $$B = \{n \in \mathbb{N} : \forall x \in \mathbb{N} \text{ and } n=2^x\}$$ but attempting to understand this is trying to swallow two pills at once. One pill is the logic part (what role is the !!\forall!! playing) and the other pill is the arithmetic part having to do with powers of !!2!!. If you're trying to understand the logic part and you don't have an instantaneous understanding of powers of !!2!!, it can be helpful to simplify matters by replacing the arithmetic with something you understand intuitively. In place of the relation !!a = 2^b!! I like to use the relation “!!a!! is the mother of !!b!!”, which everyone already knows. Are infinities included in the closure of the real set !!\overline{\mathbb{R}}!!This is a good question by the Chip Buchholtz criterion: The answer is much longer than the question was. OP wants to know if the closure of !!\Bbb R!! is just !!\Bbb R!! or if it's some larger set like !![-\infty, \infty]!!. They are running up against the idea that topological closure is not an absolute notion; it only makes sense in the context of an enclosing space. I tried to draw an analogy between the closure and the complement of a set: Does the complement of the real numbers include the number !!i!!? Well, it depends on the context. OP preferred someone else's answer, and I did too, saying:
I try to make things very explicit, but the downside of that is that it makes my answers longer, and shorter is generally better than longer. Sometimes it works, and sometimes it doesn't. Vacuous falsehood - does it exist, and are there examples?I really liked this question because I learned something from it. It brought me up short: “Huh,” I said. “I never thought about that.” Three people downvoted the question, I have no idea why. I didn't know what a vacuous falsity would be either but I decided that since the negation of a vacuous truth would be false it was probably the first thing to look at. I pulled out my stock example of vacuous truth, which is:
This is true, because all rubies are red, but vacuously so because I don't own any rubies. Since this is a vacuous truth, negating it ought to give us a vacuous falsity, if there is such a thing:
This is indeed false. And not in the way one would expect! A more typical false claim of this type would be:
This is also false, in rather a different way. It's false, but not vacuously so, because to disprove it you have to get my belts out of the closet and examine them. Now though I'm not sure I gave the right explanation in my answer. I said:
But is this the right analogy? I could have gone the other way:
Ah well, this article has been drying out on the shelf for a month now, I'm making an editorial decision to publish it without thinking about it any more. [Other articles in category /math/se] permanent link Mon, 23 Oct 2023Katara is taking a Data Structures course this year. The most recent assignment gave her a lot of trouble, partly because it was silly and made no sense, but also because she does not yet know an effective process for writing programs, and the course does not attempt to teach her. On the day the last assignment was due I helped her fix the remaining bugs and get it submitted. This is the memo I wrote to her to memorialize the important process issues that I thought of while we were working on it.
Something we discussed that I forgot to include in the memo that we discussed is: After you fix something significant, or add significant new functionality, make a checkpoint copy of the entire source code. This can be as simple as simply copying it all into separate folder. That way, when you are fixing the next thing, if you mess up and break everything, it's easy to get back to a known-good state. The computer is really clumsy to use for many tasks, but it's just great at keeping track of information, so exploit that when you can. I think CS curricula should have a class that focuses specifically on these issues, on the matter of how do you actually write software? But they never do. [Other articles in category /prog] permanent link When I first set up this blog I didn't know how long I would do it, so instead of thinking about how I wanted it to look, I just took the default layout that came with Blosxom, and figured that I would change it when I got around to it. Now I am getting around to it. The primary problem is that the current implementation (with nested tables!) performs badly, especially on mobile devices and especially on pages with a lot of MathJax. A secondary issue is that it's troublesome to edit. People sometimes laugh at how it looks like a 2006 design (which it is). I don't much care about this. I like the information-dense layout, which I think is distinctive and on-brand. I would like a redesign that fixes these two problems. The primary goal is to get rid of the nested tables and replace the implementation with something that browsers can handle better, probably something based on CSS Flexbox. It doesn't have to look very different, but it does need to be straightforward enough that I can make the next ten years of changes without a lot of research and experimentation. If you know someone interested in doing this, please email me a referral or have them get in touch with me. If you are interested in doing it yourself, please send me a proposal. Include a cost estimate, as this would be paid work. Please do not advertise this on Hacker News, as that would run the risk of my getting 100 proposals, and that would be 50 times as many as I need. Thanks. [Other articles in category /meta] permanent link Sun, 22 Oct 2023We used to have a cat named Chase. To be respectful we would sometimes refer to him as “Mr. Cat”. And sometimes I amused myself by calling him “Señor Gato”. Yesterday I got to wondering: Where did Spanish get “gato”, which certainly sounds like “cat”, when the Latin is fēles or fēlis (like in “feline’)? And similarly French has chat. Well, the real question is, where did Latin get fēles? Because Latin also has cattus, which I think sounds like a joke. You're in Latin class, and you're asked to translate cat, but you haven't done your homework, so what do you say? “Uhhhh… ‘cattus’?” But cattus is postclassical Latin, replacing the original word fēles no more than about 1500 years ago. The word seems to have wandered all over Europe and Western Asia and maybe North Africa, borrowed from one language into another, and its history is thoroughly mixed up. Nobody is sure where it came from originally, beyond “something Germanic”. The OED description of cat runs to 600 words and shrugs its shoulders. I learned recently that such words (like brinjal, the eggplant) are called Wanderworts, wandering words. [Other articles in category /lang/etym] permanent link Sat, 21 Oct 2023The other day I was looking into vindaloo curry and was surprised to learn that the word “vindaloo” is originally Portuguese vin d'alho, a wine and garlic sauce. Amazing. In Japanese, squashes are called kabocha. (In English this refers to a specific type of squash associated with Japan, but in Japanese it's more generic.) Kabocha is from Portuguese again. The Portuguese introduced squashes to Japan via Cambodia, which in Portuguese is Camboja. [Other articles in category /lang/etym] permanent link Fri, 20 Oct 2023
The discrete logarithm, shorter and simpler
I recently discussed the “discrete logarithm” method for multiplying integers, and I feel like I took too long and made it seem more complicated and mysterious than it should have been. I think I'm going to try again. Suppose for some reason you found yourself needing to multiply a lot of powers of !!2!!. What's !!4096·512!!? You could use the conventional algorithm: $$ \begin{array}{cccccccc} & & & & 4 & 0 & 9 & 6 \\ × & & & & & 5 & 1 & 2 \\ \hline % & & & & 8 & 1 & 9 & 2 \\ & & & 4 & 0 & 9 & 6 & \\ & 2 & 0 & 4 & 8 & 0 & & \\ \hline % & 2 & 0 & 9 & 7 & 1 & 5 & 2 \end{array} $$ but that's a lot of trouble, and a simpler method is available. You know that $$2^i\cdot 2^j = 2^{i+j}$$ so if you had an easy way to convert $$2^i\leftrightarrow i$$ you could just convert the factors to exponents, add the exponents, and convert back. And all that's needed is a simple table: \begin{array}{rr} 0 & 1\\ 1 & 2\\ 2 & 4\\ 3 & 8\\ 4 & 16\\ 5 & 32\\ 6 & 64\\ 7 & 128\\ 8 & 256\\ 9 & 512\\ 10 & 1\,024\\ 11 & 2\,048\\ 12 & 4\,096\\ 13 & 8\,192\\ 14 & 16\,384\\ 15 & 32\,768\\ 16 & 65\,536\\ 17 & 131\,072\\ 18 & 262\,144\\ 19 & 524\,288\\ 20 & 1\,048\,576\\ 21 & 2\,097\,152\\ \vdots & \vdots \\ \end{array} We check the table, and find that $$4096\cdot512 = 2^{12}\cdot 2^9 = 2^{12+9} = 2^{21} = 2097152.$$ Easy-peasy. That is all very well but how often do you find yourself having to multiply a lot of powers of !!2!!? This was a lovely algorithm but with very limited application. What Napier (the inventor of logarithms) realized was that while not every number is an integer power of !!2!!, every number is an integer power of !!1.00001!!, or nearly so. For example, !!23!! is very close to !!1.00001^{313\,551}!!. Napier made up a table, just like the one above, except with powers of !!1.00001!! instead of powers of !!2!!. Then to multiply !!x\cdot y!! you would just find numbers close to !!x!! and !!y!! in Napier's table and use the same algorithm. (Napier's original table used powers of !!0.9999!!, but it works the same way for the same reason.) There's another way to make it work. Consider the integers mod !!101!!, called !!\Bbb Z_{101}!!. In !!\Bbb Z_{101}!!, every number is an integer power of !!2!!! For example, !!27!! is a power of !!2!!. It's simply !!2^7!!, because if you multiply out !!2^7!! you get !!128!!, and !!128\equiv 27\pmod{101}!!. Or: $$\begin{array}{rcll} 14 & \stackrel{\pmod{101}}{\equiv} & 10\cdot 101 & + 14 \\ & = & 1010 & + 14 \\ & = & 1024 \\ & = & 2^{10} \end{array} $$ Or: $$\begin{array}{rcll} 3 & \stackrel{\pmod{101}}{\equiv} & 5844512973848570809\cdot 101 & + 3 \\ & = & 590295810358705651709 & + 3 \\ & = & 590295810358705651712 \\ & = & 2^{69} \end{array} $$ Anyway that's the secret. In !!\Bbb Z_{101}!! the silly algorithm that quickly multiplies powers of !!2!! becomes more practical, because in !!\Bbb Z_{101}!!, every number is a power of !!2!!. What works for !!101!! works in other cases larger and more interesting. It doesn't work to replace !!101!! with !!7!! (try it and see what goes wrong), but we can replace it with !!107, 797!!, or !!297779!!. The key is that if we want to replace !!101!! with !!n!! and !!2!! with !!a!!, we need to be sure that there is a solution to !!a^i=b\pmod n!! for every possible !!b!!. (The jargon term here is that !!a!! must be a “primitive root mod !!n!!”. !!2!! is a primitive root mod !!101!!, but not mod !!7!!.) Is this actually useful for multiplication? Perhaps not, but it does have cryptographic applications. Similar to how multiplying is easy but factoring seems difficult, computing !!a^i\pmod n!! for given !!a, i, n!! is easy, but nobody knows a quick way in general to reverse the calculation and compute the !!i!! for which !!a^i\pmod n = m!! for a given !!m!!. When !!n!! is small we can simply construct a lookup table with !!n-1!! entries. But if !!n!! is a !!600!!-digit number, the table method is impractical. Because of this, Alice and Bob can find a way to compute a number !!2^i!! that they both know, but someone else, seeing !!2^i!! can't easily figure out what the original !!i!! was. See Diffie-Hellman key exchange for more details. [ Also previously: Percy Ludgate's weird variation on this ] [Other articles in category /math] permanent link |