The Universe of Discourse

Rooks

Yesterday I mentioned the rook:

Wikipedia also tells me that the rook is also named from the sound it makes.

This is the “rook” that is a sort of crow, C. frugilegus. It is not related to the rooks in chess. That word is from Arabic (and earlier, Persian) rukh, which means a chariot. Before the game came to Europe, the rooks were chariots. Europeans didn't use chariots, so when they adopted the game, they changed the chariots to castles. (Similarly the elephants turned into bishops.)

Okay, I've known all this for years, but today I had another thought. Why were there chariots in the Persian form of the game? The Persians didn't use chariots either. Chariots had been obsolete since the end of the Bronze Age, thousands of years, and chess is nothing like that old.

The earliest forerunner of chess was played in India. But I confirmed with Wikipedia that it didn't overlap with chariots:

Chess is believed to have originated in Eastern India, c. 280–550, in the Gupta Empire, where its early form in the 6th century was known as chaturaṅga (Sanskrit: चतुरङ्ग), literally four divisions [of the military] – infantry, cavalry, elephants, and chariotry, represented by the pieces that would evolve into the modern pawn, knight, bishop, and rook, respectively.

Were the Guptas still using chariots in the 6th century? (And if so, why?) I think they weren't, but I'm not sure. Were the chariots intentionally anachronistic, even at the time the game was invented, recalling a time of ancient heroes?

[Other articles in category /tech] permanent link

Corax

Katara just read me the story she wrote in Latin, which concerns two men who chase after a corax. “What kind of animal is corax?” I asked.

“It's a raven.”

“Awesome,” I said. “I bet it's onomatopoeic.”

So I looked into it, and yup! It's from Greek κόραξ. Liddell and Scott's Greek-English lexicon says (p. 832):

The Root is to be found in the onomatop. words κράζω, κρώζω, croak, etc.

κράζω (krazo) and κρώζω (krozo) mean “to croak”. “Croak” itself is also onomatopoeic. And it hadn't occurred to me before that English “crow” is also onomatopoeic. Looking into it further, Wikipedia also tells me that the rook is also named from the sound it makes.

(J.R.R. Tolkien was certainly aware of all of this. In The Hobbit has has a giant raven named Roäc, the son of Carc.)

Liddell and Scott continues:

The same Root often appears in the sense of curved, cf. κορ-ώνη … Karin cur-vus, etc.

κορώνίς (koronis) means “curved”, and in particular a “corona” or crown. Curvus of course means curved, and is akin to Latin corvus, which again means a crow.

The raven's beak does not look so curved to me, but the Greeks must have found it striking.

[Other articles in category /lang/etym] permanent link

More about the happy numeric coincidence

[ Previously ]

Observing three small examples where the digital sum of !!n^k!! was equal to !!n!!, I said:

I supposed that there were few other examples, probably none … Still I hoped there might be one or two…

but in fact there are a great many; for example the digital sum of !!217^{22}!! is !!217!!.

Dave McKee asked what my intuition was. It was something like this. Fix !!n!! and consider the sequence !!n^2, n^3, …!!. The elements become increasingly sparse, and for their digital sum to equal !!n!! requires increasingly improbable coincidences. For example, taking !!n=3!!, we would need to have !!k!! such that $$3^k = 2·10^p + 1.$$ While I can't immediately rule out this possibility, it seems extremely unlikely. This also resembles the Catalan conjecture, which is that the only nontrivial solution of $$ \left\lvert2^i - 3^j\right\rvert = 1$$ is !!i=3, j=2!!. The Catalan conjecture is indeed true, but it was an open problem for 158 years.

[ Addendum 20190205: I have since learned that the Catalan conjecture actually concerns the more general claim about the equation !! \left\lvert a^i - b^j\right\rvert = 1!!. The special case of !!a=2, b=3!! turns out to be elementary. ]

I was quite mistaken, so what went wrong? First, there is one nontrivial solution to the Catalan conjecture, and here we have not one sequence of !!n^k!! but an infinite family, each of which might have an exceptional solution or two. And second, the case of !!n=3!! is atypically bleak. For !!3^k!! to have a digital sum of !!3!! is a tough order because there are very few sequences of digits whose sum is 3. But the number of sequences of !!d!! digits whose sum is !!n!! grows quite rapidly with !!n!!, and for small !!n!! is very misleading.

[Other articles in category /math] permanent link

A happy numeric coincidence

A couple of days ago I was pleased to notice the following coincidence:

I supposed that there were few other examples, probably none, and that at least I could prove that there were only a finite number of examples. My expected proof of this didn't work, but I still supposed that there would be no further examples. Still I hoped there might be one or two, so I set the computer to look for them if there were.

My first run produced:

\begin{array}{rcr} 17^3 &=& 4\;913 \\ 18^3 &=& 5\;832\\ 22^4 &=& 234\;256\\ 25^4 &=& 390\;625\\ 26^3 &=& 17\;576\\ 27^3 &=& 19\;683\\ 28^4 &=& 614\;656\\ 36^4 &=& 1\;679\;616\\ \end{array}

Well, that was a happy surprise.

Wait a minute, though:

\begin{array}{rcr} 18 ^{ 6 } &=& 34\;012\;224 \\ 18 ^{ 7 } &=& 612\;220\;032 \\ 27 ^{ 7 } &=& 10\;460\;353\;203 \\ 28 ^{ 5 } &=& 17\;210\;368 \\ 31 ^{ 7 } &=& 27\;512\;614\;111 \\ 34 ^{ 7 } &=& 52\;523\;350\;144 \\ 35 ^{ 5 } &=& 52\;521\;875 \\ 36 ^{ 5 } &=& 60\;466\;176 \\ 43 ^{ 7 } &=& 271\;818\;611\;107 \\ 45 ^{ 6 } &=& 8\;303\;765\;625 \\ 46 ^{ 5 } &=& 205\;962\;976 \\ 46 ^{ 8 } &=& 20\;047\;612\;231\;936 \\ 53 ^{ 7 } &=& 1\;174\;711\;139\;837 \\ 54 ^{ 6 } &=& 24\;794\;911\;296 \\ 54 ^{ 8 } &=& 72\;301\;961\;339\;136 \\ 54 ^{ 9 } &=& 3\;904\;305\;912\;313\;344 \\ 58 ^{ 7 } &=& 2\;207\;984\;167\;552 \\ 63 ^{ 8 } &=& 248\;155\;780\;267\;521 \\ 64 ^{ 6 } &=& 68\;719\;476\;736 \\ 68 ^{ 7 } &=& 6\;722\;988\;818\;432 \\ 71 ^{ 9 } &=& 45\;848\;500\;718\;449\;031 \\ 81 ^{ 9 } &=& 150\;094\;635\;296\;999\;121 \\ 82 ^{ 10 } &=& 13\;744\;803\;133\;596\;058\;624 \\ 85 ^{ 10 } &=& 19\;687\;440\;434\;072\;265\;625 \\ 94 ^{ 10 } &=& 53\;861\;511\;409\;489\;970\;176 \\ 97 ^{ 10 } &=& 73\;742\;412\;689\;492\;826\;049 \\ 106 ^{ 10 } &=& 179\;084\;769\;654\;285\;362\;176 \\ 117 ^{ 10 } &=& 480\;682\;838\;924\;478\;847\;449 \\ \end{array}

Oh my.

\begin{array}{rcr} 20 ^{ 13 } &=& 81\;920 & · 10^{12} \\ 40 ^{ 13 } &=& 671\;088\;640 & · 10^{12} \\ 80 ^{ 17 } &=& 225\;179\;981\;368\;524\;800 & · 10^{15} \\ \hline 80 ^{ 19 } &=& 1\;441\;151\;880\;758\;558\;720 & · 10^{18} \\ 86 ^{ 13 } &=& 14\;076\;019\;706\;120\;526\;112\;710\;656 \\ 90 ^{ 19 } &=& 13\;508\;517\;176\;729\;920\;890 & · 10^{18} \\ \hline 90 ^{ 20 } &=& 1\;215\;766\;545\;905\;692\;880\;100 & · 10^{18} \\ 90 ^{ 21 } &=& 109\;418\;989\;131\;512\;359\;209 & · 10^{21} \\ 90 ^{ 22 } &=& 9\;847\;709\;021\;836\;112\;328\;810 & · 10^{21} \\ \hline 90 ^{ 28 } &=& 5\;233\;476\;330\;273\;605\;372\;135\;115\;210 & · 10^{27} \\ 91 ^{ 14 } &=& 2\;670\;419\;511\;272\;061\;205\;254\;504\;361 \\ 98 ^{ 11 } &=& 8\;007\;313\;507\;497\;959\;524\;352 \\ \hline 103 ^{ 13 } &=& 146\;853\;371\;345\;156\;431\;381\;127\;623 \\ 104 ^{ 13 } &=& 166\;507\;350\;731\;038\;802\;170\;609\;664 \\ 106 ^{ 13 } &=& 213\;292\;826\;014\;568\;334\;917\;410\;816 \\ \hline 107 ^{ 11 } &=& 21\;048\;519\;522\;998\;348\;950\;643 \\ 107 ^{ 13 } &=& 240\;984\;500\;018\;808\;097\;135\;911\;707 \\ 107 ^{ 15 } & = & 2\;759\;031\;540\;715\;333\;904\;109\;053\;133 & & \\ & & 443 & & \\ \hline 108 ^{ 11 } &=& 23\;316\;389\;970\;546\;096\;340\;992 \\ 108 ^{ 12 } &=& 2\;518\;170\;116\;818\;978\;404\;827\;136 \\ 118 ^{ 14 } &=& 101\;472\;439\;712\;019\;470\;540\;189\;876\;224 \\ \hline 126 ^{ 13 } &=& 2\;017\;516\;459\;574\;609\;153\;391\;845\;376 \\ 127 ^{ 14 } &=& 283\;956\;682\;347\;124\;706\;942\;551\;243\;009 \\ 133 ^{ 16 } & = & 9\;585\;753\;470\;490\;322\;141\;591\;520\;062 & & \\ & & 265\;281 & & \\ \hline 134 ^{ 13 } &=& 4\;491\;199\;828\;872\;408\;503\;792\;328\;704 \\ 134 ^{ 15 } & = & 80\;643\;984\;127\;232\;967\;094\;095\;054\;209 & & \\ & & 024 & & \\ 135 ^{ 13 } &=& 4\;946\;966\;739\;525\;117\;513\;427\;734\;375 \\ \hline 135 ^{ 14 } &=& 667\;840\;509\;835\;890\;864\;312\;744\;140\;625 \\ 136 ^{ 15 } & = & 100\;712\;557\;719\;971\;285\;024\;106\;952\;523 & & \\ & & 776 & & \\ 140 ^{ 25 } &=& 449\;987\;958\;058\;483\;731\;145\;152\;266\;240 & · 10^{24} \\ \hline 142 ^{ 16 } & = & 27\;328\;356\;228\;554\;426\;163\;172\;505\;624 & & \\ & & 313\;856 & & \\ 143 ^{ 17 } & = & 4\;372\;327\;021\;734\;283\;642\;004\;853\;327 & & \\ & & 592\;915\;343 & & \\ 152 ^{ 15 } & = & 534\;138\;422\;146\;939\;893\;094\;821\;310\;496 & & \\ & & 768 & & \\ \hline 154 ^{ 14 } & = & 4\;219\;782\;742\;781\;494\;680\;756\;610\;809 & & \\ & & 856 & & \\ 154 ^{ 15 } & = & 649\;846\;542\;388\;350\;180\;836\;518\;064\;717 & & \\ & & 824 & & \\ 155 ^{ 19 } & = & 413\;335\;079\;574\;020\;313\;162\;122\;296\;733 & & \\ & & 856\;201\;171\;875 & & \\ \hline 157 ^{ 19 } & = & 527\;343\;255\;303\;841\;790\;870\;720\;812\;082 & & \\ & & 050\;804\;460\;293 & & \\ 160 ^{ 28 } & = & 51\;922\;968\;585\;348\;276\;285\;304\;963\;292 & & \\ & & 200\;960 & · 10^{27} & \\ 163 ^{ 16 } & = & 248\;314\;265\;639\;726\;167\;358\;751\;235\;626 & & \\ & & 296\;641 & & \\ \hline 169 ^{ 16 } & = & 442\;779\;263\;776\;840\;698\;304\;313\;192\;148 & & \\ & & 785\;281 & & \\ 169 ^{ 22 } & = & 10\;315\;908\;977\;942\;302\;627\;204\;470\;186 & & \\ & & 314\;316\;211\;062\;255\;002\;161 & & \\ 170 ^{ 31 } & = & 1\;392\;889\;173\;388\;510\;144\;614\;180\;174 & & \\ & & 894\;677\;204\;330 & · 10^{30} & \\ \hline 170 ^{ 33 } & = & 40\;254\;497\;110\;927\;943\;179\;349\;807\;054 & & \\ & & 456\;171\;205\;137 & · 10^{33} & \\ 171 ^{ 17 } & = & 91\;397\;407\;411\;741\;874\;683\;083\;843\;738 & & \\ & & 640\;173\;291 & & \\ 171 ^{ 19 } & = & 2\;672\;551\;590\;126\;744\;157\;608\;054\;674 & & \\ & & 761\;577\;307\;202\;131 & & \\ \hline 172 ^{ 18 } & = & 17\;358\;494\;027\;033\;103\;736\;099\;033\;196 & & \\ & & 316\;709\;617\;664 & & \\ 173 ^{ 19 } & = & 3\;333\;311\;951\;341\;729\;629\;204\;978\;703 & & \\ & & 084\;632\;004\;627\;637 & & \\ 181 ^{ 18 } & = & 43\;472\;473\;122\;830\;653\;562\;489\;222\;659 & & \\ & & 449\;707\;872\;441 & & \\ \hline 181 ^{ 19 } & = & 7\;868\;517\;635\;232\;348\;294\;810\;549\;301 & & \\ & & 360\;397\;124\;911\;821 & & \\ 181 ^{ 20 } & = & 1\;424\;201\;691\;977\;055\;041\;360\;709\;423 & & \\ & & 546\;231\;879\;609\;039\;601 & & \\ 189 ^{ 19 } & = & 17\;896\;754\;443\;176\;031\;520\;198\;514\;559 & & \\ & & 819\;163\;143\;441\;509 & & \\ \hline 193 ^{ 22 } & = & 191\;540\;580\;003\;116\;921\;429\;323\;712\;183 & & \\ & & 642\;218\;614\;831\;262\;597\;249 & & \\ 199 ^{ 21 } & = & 1\;887\;620\;149\;539\;230\;539\;058\;375\;534 & & \\ & & 310\;517\;606\;114\;631\;604\;199 & & \\ 207 ^{ 20 } & = & 20\;864\;448\;472\;975\;628\;947\;226\;005\;981 & & \\ & & 267\;194\;447\;042\;584\;001 & & \\ \hline 211 ^{ 25 } & = & 12\;795\;621\;425\;112\;113\;141\;935\;148\;247 & & \\ & & 655\;082\;376\;252\;275\;523\;500\;373\;035\;251 & & \\ 217 ^{ 22 } & = & 2\;524\;144\;100\;572\;738\;110\;818\;511\;483 & & \\ & & 976\;079\;134\;636\;146\;367\;057\;489 & & \\ 221 ^{ 25 } & = & 40\;719\;913\;064\;560\;249\;818\;128\;041\;081 & & \\ & & 360\;346\;218\;088\;750\;603\;039\;104\;925\;501 & & \\ \hline 225 ^{ 22 } & = & 5\;597\;774\;487\;475\;881\;147\;025\;802\;420 & & \\ & & 102\;991\;163\;730\;621\;337\;890\;625 & & \\ 234 ^{ 23 } & = & 3\;104\;307\;401\;943\;398\;225\;947\;002\;752 & & \\ & & 118\;451\;297\;846\;365\;869\;366\;575\;104 & & \\ 236 ^{ 25 } & = & 210\;281\;019\;656\;164\;214\;863\;109\;519\;134 & & \\ & & 145\;127\;118\;463\;502\;897\;144\;582\;373\;376 & & \\ \hline 250 ^{ 40 } & = & 827\;180\;612\;553\;027\;674\;871\;408\;692\;069 & & \\ & & 962\;853\;565\;812\;110\;900\;878\;906\;250 & · 10^{39} & \\ 265 ^{ 28 } & = & 70\;938\;903\;323\;020\;164\;041\;464\;952\;207 & & \\ & & 191\;804\;150\;246\;813\;586\;391\;508\;579\;254 & & \\ & & 150\;390\;625 & & \\ \end{array}

Holy cow.

I should have been able to foresee some of those, like !!20^{13} = 8192·10^{13}!!, which in hindsight is obvious. But seriously, !!163^{16}!!?

(It rather looks like !!265^{28}!! might be the last one where !!n!! is not a multiple of !!10!!, however. Or maybe that is a misleading artifact of the calculating system I am using? I'm not sure yet.)

Happy new year, all.

[ Addendum 20190102: Several readers have confirmed that there are many examples past !!265^{28}!!. I am probably running into some mismatch between the way the computer represents numbers and the way they actually work. ]

[ Addendum 20190102: Dave McKee asked why I thought there would be few examples. ]

[Other articles in category /math] permanent link

I figured out that context manager bug!

A couple of days ago I described a strange bug in my “Greenlight” project that was causing Git to fail unpredictably, saying:

    fatal: this operation must be run in a work tree

The problem seemed to go away when I changed

    with env_var("GIT_DIR", self.repo_dir):
        with env_var("GIT_WORK_TREE", self.work_dir):
            result = subprocess.run(command, ...)

to

    with env_var("GIT_DIR", self.repo_dir, "GIT_WORK_TREE", self.work_dir):
        result = subprocess.run(command, ...)

but I didn't understand why. I said:

This was so unexpected that I wondered if the real problem was nondeterministic and if some of the debugging messages had somehow perturbed it. But I removed everything but the context manager change and ran another test, which succeeded. By then I was five and half hours into the debugging and I didn't have any energy left to actually understand what the problem had been. I still don't know.

The problem re-manifested again today, and this time I was able to track it down and fix it. The context manager code I mentioned above was not the issue.

That subprocess.run call is made inside a git_util object which, as you can see in the tiny excerpt above, has a self.work_dir attribute that tells it where to find the working tree. Just before running a Git command, the git_util object installs self.work_dir into the environment to tell Git where the working tree is.

The git_util object is originally manufactured by Greenlight itself, which sets the work_dir attribute to a path that contains the current process ID number. Just before the process exits, Greenlight destroys the working tree. This way, concurrent processes never try to use the same working tree, which would be a mess.

When Greenlight needs to operate on the repository, it uses its git_util object directly. It also creates a submission object to represent the submitted branch, and it installs the git_util object into the submission object, so that the submission object can also operate on the repository. For example, the submission object may ask its git_util object if it needs to be rebased onto some other branch, and if so to please do it. So:

• Greenlight has a submission.
• submission.git is the git_util object that deals with Git.
• submission.git.work_dir is the path to the per-process temporary working tree.

Greenlight's main purpose is to track these submission objects, and it has a database of them. To save time when writing the initial implementation, instead of using a real database, I had Greenlight use Python's “pickle” feature to pickle the list of submissions.

Someone would submit a branch, and Greenlight would pickle the submission. The submission contained its git_util object, and that got pickled along with the rest. Then Greenlight would exit and, just before doing so, it would destroy its temporary working tree.

Then later, when someone else wanted to approve the submission for publication, Greenlight would set up a different working tree with its new process ID, and unpickle the submission. But the submission's git.work_dir had been pickled with the old path, which no longer existed.

The context manager was working just fine. It was setting GIT_WORK_TREE to the work_dir value in the git_util object. But the object was obsolete and its work_dir value pointed to a directory that had been destroyed!

Adding to the confusion:

1. Greenlight's own git_util object was always fresh and had the right path in it, so Git commands run directly by Greenlight all worked properly.

2. Any new submission objects created by Greenlight would have the right path, so Git commands run by fresh submissions also worked properly.

3. Greenlight doesn't always destroy the working tree when it exits. If it exits abnormally, it leaves the working tree intact, for a later autopsy. And the unpickled submission would work perfectly if the working tree still existed, and it would be impossible to reproduce the problem!

Toward the end of the previous article, I said:

I suspect I'm being sabotaged somewhere by Python's weird implicit ideas of scope and variable duration, but I don't know. Yet.

For the record, then: The issue was indeed one of variable duration. But Python's weird implicit ideas were, in this instance, completely blameless. Instead the issue was cause by a software component even more complex and more poorly understood: “Dominus”.

This computer stuff is amazingly complicated. I don't know how anyone gets anything done.

[Other articles in category /prog/bug] permanent link

Necklaces and bracelets

There are combinatorial objects called necklaces and bracelets and I can never remember which is which.

Both are finite sequences of things (typically symbols) where the start point is not important. So the bracelet ABCDE is considered to be the same as the bracelets BCDEA, CDEAB, DEABC, and EABCD.

One of the two also disregards the direction you go, so that ABCDE is also considered the same as EDCBA (and so also DCBAE, etc.). But which? I have to look it up every time.

I have finally thought of a mnemonic. In a necklace, the direction is important, because to reverse an actual necklace you have to pull it off over the wearer's head, turn it over, and put it back on. But in a bracelet the direction is not important, because it could be on either wrist, and a bracelet on the left wrist is the same as the reversed bracelet on the right wrist.

Okay, silly, maybe, but I think it's going to work.

[Other articles in category /math] permanent link

Another day, another bug. No, four bugs.

I'm working on a large and wonderful project called “Greenlight”. It's a Git branch merging service that implements the following workflow:

1. Submitter submits a branch to Greenlight (greenlight submit my-topic-branch)
2. Greenlight analyzes the branch to decide if it changes anything that requires review and signoff
3. If so, it contacts the authorized reviewers, who then inform Greenlight that they approve the changes (greenlight approve 03a46dc1)
4. Greenlight merges the branch to master and publishes the result to the central repository

Of course, there are many details elided here.

Multiple instances of Greenlight share a local repository, but to avoid confusion each has its own working tree. In Git you can configure these by setting GIT_DIR and GIT_WORK_TREE environment variables, respectively. When Greenlight needs to run a Git command, it does so like this:

    with env_var("GIT_DIR", self.repo_dir):
        with env_var("GIT_WORK_TREE", self.work_dir):
            result = subprocess.run(command, ...)

The env_var here is a Python context manager that saves the old environment, sets the new environment variable, and then when the body of the block is complete, it restores the environment to the way it was. This worked in testing every time.

But the first time a beta tester ran the approve command, Greenlight threw a fatal exception. It was trying to run git checkout --quiet --detach, and this was failing, with Git saying

fatal: this operation must be run in a work tree

Where was the GIT_WORK_TREE setting going? I still don't know. But in the course of trying to track the problem down, I changed the code above to:

    with env_var("GIT_DIR", self.repo_dir, "GIT_WORK_TREE", self.work_dir):
        result = subprocess.run(command, ...)

and the problem, whatever it was, no longer manifested.

But this revealed a second bug: Greenlight no longer failed in the approval phase. It went ahead and merged the branch, and then tried to publish the merge with git push origin .... But the push was rejected.

This is because the origin repository had an update hook that ran on every push, which performed the same review analysis that Greenlight was performing; one of Greenlight's main purposes is to be a replacement for this hook. To avoid tying up the main repository for too long, this hook had a two-minute timeout, after which it would die and reject the push. This had only happened very rarely in the past, usually when someone was inadvertently trying to push a malformed branch. For example, they might have rebased all of master onto their topic branch. In this case, however, the branch really was legitimately enormous; it contained over 2900 commits.

“Oh, right,” I said. “I forgot to add the exception to the hook that tells it that it can immediately approve anything pushed by Greenlight.” The hook can assume that if the push comes from Greenlight, it has already been checked and authorized.

Pushes are happening via SSH, and Greenlight has its own SSH identity, which is passed to the hook itself in the GL_USERNAME variable. Modifying the hook was easy: I just added:

      if environ["GL_USERNAME"] == 'greenlight':
            exit(0)

This didn't work. My first idea was that Greenlight's public SSH key had not been installed in the authorized_keys file in the right place. When I grepped for greenlight in the authorized_keys file, there were no matches. The key was actually there, but in Gitlab the authorized_keys file doesn't have actual usernames in it. It has internal userids, which are then mapped to GL_USERNAME variables by some other entity. So I chased that wild goose for a while. Eventually I determined that the key was in the right place, but that the name of the Greenlight identity on the receiving side was not greenlight but bot-greenlight, which I had forgotten.

So I changed the exception to say:

      if environ["GL_USERNAME"] == 'bot-greenlight':
            exit(0)

and it still didn't work. I eventually discovered that when Greenlight did the push, the GL_USERNAME was actually set to mjd.

“Oh, right,” I said. “I forgot to have Greenlight use its own SSH credentials in the ssh connection.”

The way you do this is to write a little wrapper program that obtains the correct credentials and runs ssh, and then you set GIT_SSH to point to the wrapper. It looks like this:

    #!/usr/bin/env bash

    export -n SSH_CLIENT SSH_TTY SSH_AUTH_SOCK SSH_CONNECTION
    exec /usr/bin/ssh -i $HOME/.ssh/identity  "$@"

But wait, why hadn't I noticed this before? Because, apparently, every single person who had alpha-tested Greenlight had had their own credentials stored in ssh-agent, and every single one had had agent-forwarding enabled, so that when Greenlight tried to use ssh to connect to the Git repository, SSH duly forwarded their credentials along and the pushes succeeded. Amazing.

With these changes, the publication went through. I committed the changes to the SSH credential stuff, and some other unrelated changes, and I looked at what was left to see what had actually fixed the original bug. Every change but one was to add diagnostic messages and logging. The fix for the original bug had been to replace the nested context managers with a single context manager. This was so unexpected that I wondered if the real problem was nondeterministic and if some of the debugging messages had somehow perturbed it. But I removed everything but the context manager change and ran another test, which succeeded. By then I was five and half hours into the debugging and I didn't have any energy left to actually understand what the problem had been. I still don't know.

If you'd like to play along at home, the context manager looks like this, and did not change during the debugging process:

    from contextlib import contextmanager

    @contextmanager
    def env_var(*args):

        # Save old values of environment variables in `old`
        # A saved value of `None` means that the variable was not there before
        old = {}
        for i in range(len(args)//2):
            (key, value) = (args[2*i : 2*i+2])
            old[key] = None
            if key in os.environ:
                old[key] = os.environ[str(key)]

            if value is None: os.environ.pop(str(key), "dummy")
            else:
                os.environ[str(key)] = str(value)

        yield

        # Undo changes from versions saved in `old`
        for (key, value) in old.items():
            if value is None: os.environ.pop(str(key), "dummy")
            else:             os.environ[str(key)] = value

I suspect I'm being sabotaged somewhere by Python's weird implicit ideas of scope and variable duration, but I don't know. Yet.

This computer stuff is amazingly complicated. I don't know how anyone gets anything done.

[ Addendum 20181204: I figured it out. ]

[Other articles in category /prog/bug] permanent link

How many kinds of polygonal loops? (part 2)

I recently asked about these:

And I said I thought there were nine analogous figures with six points.

Rahul Narain referred me to a recent discussion of almost this exact question on Math Stackexchange. (Note that the discussion there considers two figures different if they are reflections of one another; I consider them the same.) The answer turns out to be OEIS A000940. I had said:

… for !!N=6!!, I found it hard to enumerate. I think there are nine shapes but I might have missed one, because I know I kept making mistakes in the enumeration …

I missed three. The nine I got were:

And the three I missed are:

I had tried to break them down by the arrangement of the outside ring of edges, which can be described by a composition. The first two of these have type !!1+1+1+1+2!! (which I missed completely; I thought there were none of this type) and the other has type !!1+2+1+2!!, the same as the !!015342!! one in the lower right of the previous diagram.

I had ended by saying:

I would certainly not trust myself to hand-enumerate the !!N=7!! shapes.

Good call, Mr. Dominus! I considered filing this under “oops” but I decided that although I had gotten the wrong answer, my confidence in it had been adequately low. On one level it was a mistake, but on a higher and more important level, I did better.

I am going to try the (Cauchy-Frobenius-)Burnside-(Redfield-)Pólya lemma on it next and see if I can get the right answer.

Thanks again to Rahul Narain for bringing this to my attention.

[Other articles in category /math] permanent link

How many kinds of polygonal loops?

Take !!N!! equally-spaced points on a circle. Now connect them in a loop: each point should be connected to exactly two others, and each point should be reachable from the others. How many geometrically distinct shapes can be formed?

For example, when !!N=5!!, these four shapes can be formed:

(I phrased this like a geometry problenm, but it should be clear it's actually a combinatorics problem. But it's much easier to express as a geometry problem; to talk about the combinatorics I have to ask you to consider a permutation !!P!! where !!P(i±1)≠P(i)±1!! blah blah blah…)

For !!N<5!! it's easy. When !!N=3!! it is always a triangle. When !!N=4!! there are only two shapes: a square and a bow tie.

But for !!N=6!!, I found it hard to enumerate. I think there are nine shapes but I might have missed one, because I know I kept making mistakes in the enumeration, and I am not sure they are all corrected:

It seems like it ought not to be hard to enumerate and count these, but so far I haven't gotten a good handle on it. I produced the !!N=6!! display above by considering the compositions of the number !!6!!:

(Actually it's the compositions, modulo bracelet symmetries — that is, modulo the action of the dihedral group.)

But this is fraught with opportunities for mistakes in both directions. I would certainly not trust myself to hand-enumerate the !!N=7!! shapes.

[ Addendum: For !!N=6!! there are 12 figures, not 9. For !!N=7!!, there are 39. Further details. ]

[Other articles in category /math] permanent link

60-degree angles on a lattice

A couple of years back I was thinking about how to draw a good approximation to an equilateral triangle on a piece of graph paper. There are no lattice points that are exactly the vertices of an equilateral triangle, but you can come close, and one way to do it is to find integers !!a!! and !!b!! with !!\frac ba\approx \sqrt 3!!, and then !!\langle 0, 0\rangle, \langle 2a, 0\rangle,!! and !!\langle a, b\rangle!! are almost an equilateral triangle.

But today I came back to it for some reason and I wondered if it would be possible to get an angle closer to 60°, or numbers that were simpler, or both, by not making one of the sides of the triangle perfectly horizontal as in that example.

So okay, we want to find !!P = \langle a, b\rangle!! and !!Q = \langle c,d\rangle!! so that the angle !!\alpha!! between the rays !!\overrightarrow{OP}!! and !!\overrightarrow{OQ}!! is as close as possible to !!\frac\pi 3!!.

The first thing I thought of was that the dot product !!P\cdot Q = |P||Q|\cos\alpha!!, and !!P\cdot Q!! is super-easy to calculate, it's just !!ac+bd!!. So we want $$\frac{ad+bc}{|P||Q|} = \cos\alpha \approx \frac12,$$ and everything is simple, except that !!|P||Q| = \sqrt{a^2+b^2}\sqrt{c^2+d^2}!!, which is not so great.

Then I tried something else, using high-school trigonometry. Let !!\alpha_P!! and !!\alpha_Q!! be the angles that the rays make with the !!x!!-axis. Then !!\alpha = \alpha_Q - \alpha_P = \tan^{-1} \frac dc - \tan^{-1} \frac ba!!, which we want close to !!\frac\pi3!!.

Taking the tangent of both sides and applying the formula $$\tan(q-p) = \frac{\tan q - \tan p}{1 + \tan q \tan p}$$ we get $$ \frac{\frac dc - \frac ba}{1 + \frac dc\frac ba} \approx \sqrt3.$$ Or simplifying a bit, the super-simple $$\frac{ad-bc}{ac+bd} \approx \sqrt3.$$

After I got there I realized that my dot product idea had almost worked. To get rid of the troublesome !!|P||Q|!! you should consider the cross product also. Observe that the magnitude of !!P\times Q!! is !!|P||Q|\sin\alpha!!, and is also $$\begin{vmatrix} a & b & 0 \\ c & d & 0 \\ 1 & 1 & 1 \end{vmatrix} = ad - bc$$ so that !!\sin\alpha = \frac{ad-bc}{|P||Q|}!!. Then if we divide, the !!|P||Q|!! things cancel out nicely: $$\tan\alpha = \frac{\sin\alpha}{\cos\alpha} = \frac{ad-bc}{ac+bd}$$ which we want to be as close as possible to !!\sqrt 3!!.

Okay, that's fine. Now we need to find some integers !!a,b,c,d!! that do what we want. The usual trick, “see what happens if !!a=0!!”, is already used up, since that's what the previous article was about. So let's look under the next-closest lamppost, and let !!a=1!!. Actually we'll let !!b=1!! instead to keep things more horizonal. Then, taking !!\frac74!! as our approximation for !!\sqrt3!!, we want

$$\frac{ad-c}{ac+d} = \frac74$$

or equivalently $$\frac dc = \frac{7a+4}{4a-7}.$$

Now we just tabulate !!7a+4!! and !!4a-7!! looking for nice fractions:

Each of these gives us a !!\langle c,d\rangle!! point, but some are much better than others. For example, in line 3, we have take !!\langle 5,25\rangle!! but we can use !!\langle 1,5\rangle!! which gives the same !!\frac dc!! but is simpler. We still get !!\frac{ad-bc}{ac+bd} = \frac 74!! as we want.

Doing this gives us the two points !!P=\langle 3,1\rangle!! and !!Q=\langle 1, 5\rangle!!. The angle between !!\overrightarrow{OP}!! and !!\overrightarrow{OQ}!! is then !!60.255°!!. This is exactly the same as in the approximately equilateral !!\langle 0, 0\rangle, \langle 8, 0\rangle,!! and !!\langle 4, 7\rangle!! triangle I mentioned before, but the numbers could not possibly be easier to remember. So the method is a success: I wanted simpler numbers or a better approximation, and I got the same approximation with simpler numbers.

To draw a 60° angle on graph paper, mark !!P=\langle 3,1\rangle!! and !!Q=\langle 1, 5\rangle!!, draw lines to them from the origin with a straightedge, and there is your 60° angle, to better than a half a percent.

There are some other items in the table (for example row 18 gives !!P=\langle 18,1\rangle!! and !!Q=\langle 1, 2\rangle!!) but because of the way we constructed the table, every row is going to give us the same angle of !!60.225°!!, because we approximated !!\sqrt3\approx\frac74!! and !!60.225° = \tan^{-1}\frac74!!. And the chance of finding numbers better than !!\langle 3,1\rangle!! and !!\langle 1, 5\rangle!! seems slim. So now let's see if we can get the angle closer to exactly !!60°!! by using a better approximation to !!\sqrt3!! than !!\frac 74!!.

The next convergents to !!\sqrt 3!! are !!\frac{19}{11}!! and !!\frac{26}{15}!!. I tried the same procedure for !!\frac{19}{11}!! and it was a bust. But !!\frac{26}{15}!! hit the jackpot: !!a=4!! gives us !!15a-26 = 34!! and !!26a-15=119!!, both of which are multiples of 17. So the points are !!P=\langle 4,1\rangle!! and !!Q=\langle 2, 7\rangle!!, and this time the angle between the rays is !!\tan^{-1}\frac{26}{15} = 60.018°!!. This is as accurate as anyone drawing on graph paper could possibly need; on a circle with a one-mile radius it is an error of 20 inches.

Of course, the triangles you get are no longer equilateral, not even close. That first one has sides of !!\sqrt{10}, \sqrt{20}, !! and !!\sqrt{26}!!, and the second one has sides of !!\sqrt{17}, \sqrt{40}, !! and !!\sqrt{53}!!. But! The slopes of the lines are so simple, it's easy to construct equilateral triangles with a straightedge and a bit of easy measuring. Let's do it on the !!60.018°!! angle and see how it looks.

!!\overrightarrow{OP}!! has slope !!\frac14!!, so the perpendicular to it has slope !!-4!!, which means that you can draw the perpendicular by placing the straightedge between !!P!! and some point !!P+x\langle -1, 4\rangle!!, say !!\langle 2, 9\rangle!! as in the picture. The straightedge should have slope !!-4!!, which is very easy to arrange: just imagine the little squares grouped into stacks of four, and have the straightedge go through opposite corners of each stack. The line won't necessarily intersect !!\overrightarrow{OQ}!! anywhere great, but it doesn't need to, because we can just mark the intersection, wherever it is:

Let's call that intersection !!A!! for “apex”.

The point opposite to !!O!! on the other side of !!P!! is even easier; it's just !!P'=2P =\langle 8, 2\rangle!!. And the segment !!P'A!! is the third side of our equilateral triangle:

This triangle is geometrically similar to a triangle with vertices at !!\langle 0, 0\rangle, \langle 30, 0\rangle,!! and !!\langle 15, 26\rangle!!, and the angles are just close to 60°, but it is much smaller.

Woot!

[Other articles in category /math] permanent link

I love the dodecahedron

I think I forgot to mention that I was looking recently at hamiltonian cycles on a dodecahedron. The dodecahedron has 30 edges and 20 vertices, so a hamiltonian path contains 20 edges and omits 10. It turns out that it is possible to color the edges of the dodecahedron in three colors so that:

• Every vertex is incident to one edge of each color
• The edges of any two of the three colors form a hamiltonian cycle

Marvelous!

(In this presentation, I have taken one of the vertices and sent it away to infinity. The three edges with arrowheads are all attached to that vertex, off at infinity, and the three faces incident to it have been stretched out to cover the rest of the plane.)

Every face has five edges and there are only three colors, so the colors can't be distributed evenly around a face. Each face is surrounded by two edges of one color, two of a second color, and only one of the last color. This naturally divides the 12 faces into three classes, depending on which color is assigned to only one edge of that face.

Each class contains two pairs of two adjacent pentagons, and each adjacent pair is adjacent to the four pairs in the other classes but not to the other pair in its own class.

Each pair shares a single edge, which we might call its “hinge”, shown here as dotted lines. Each pair has 8 vertices, of which two are on its hinge, four are adjacent to the hinge, and two are not near of the hinge. These last two vertices are always part of the hinges of the pairs of a different class.

I could think about this for a long time, and probably will. There is plenty more to be seen, but I think there is something else I was supposed to be doing today, let me think…. Oh yes! My “job”! So I will leave you to go on from here on your own.

[ Addendum 20181203: David Eppstein has written a much longer and more detailed article about triply-Hamiltonian edge colorings, using this example as a jumping-off point. ]

[Other articles in category /math] permanent link

How do you make a stella octangula?

Yesterday Katara asked me out of nowhere “When you make a stella octangula, do you build it up from an octahedron or a tetrahedron?” Stella octangula was her favorite polyhedron eight years ago.

“Uh,” I said. “Both?”

Then she had to make one to see what I meant. You can start with a regular octahedron:

Then you erect spikes onto four of the octahedron's faces; this produces a regular tetrahedron:

Then you erect spikes onto the other four of the octahedron's faces. Now you have a stella octangula.

So yeah, both. Or instead of starting with a unit octahedron and erecting eight spikes of size 1, you can start with a unit tetrahedron and erect four spikes of size ½. It's both at once.

[Other articles in category /math] permanent link