Tuesday, June 30, 2015

Just Who Do We Think We Are?

That was the jarring question posed by Chief Justice John Roberts in his vehement Obergefell dissent (one of the court cases I discussed in my earlier post). The question punctuated his argument that since he could not find for the plaintiffs on constitutional grounds, their fate ought to be left with the states. In his conclusion, Roberts forcefully distinguished between public policy and constitutional law:
If you are among the many Americans—of whatever sexual orientation—who favor expanding same-sex marriage, by all means celebrate today’s decision. Celebrate the achievement of a desired goal. Celebrate the opportunity for a new expression of commitment to a partner. Celebrate the availability of new benefits. But do not celebrate the Constitution. It had nothing to do with it.
Those last two sentences appeared gratuitous to some observers, and I have to agree, if only because it seemed to me that Roberts never really tackled Kennedy's core argument head-on. Instead of dismantling the majority's approach, he championed alternatives to it and raised concerns about its implications. Points taken—and the dissent may live on in some fashion in Fourteenth Amendment jurisprudence. But without a more direct assault on Kennedy's reasoning, the dissent doesn't fully earn such a categorical conclusion.

While I've been following the legal back-and-forth pretty closely over the past year or two, I realize that same-sex marriage isn't just a question of the finer points of law. Obergefell has major life implications for real people. As far as that goes, I understand why progressives are happy about the decision. What I don't understand is why more conservatives aren't happy about it. Andrew Sullivan has been making the conservative case for marriage equality for decades. And there is a "live and let live" aspect to the Obergefell decision that makes it a victory for small-government conservatives, too; see, for example, this essay on the libertarian website Reason.com. (Maybe anti-government conservatives actually have a soft spot for government power after all, as long as it's state and local goverments that are wielding it.)

The elephant in the room for the Obergefell decision is bias. Bigotry against gay people is widespread, even among elected officials. A state senator in North Dakota, Rep. Dwight Kiefert, recently posted this to his Facebook page:

The article continues:
Kiefert said in the interview that his post was not a "public statement," but merely a request that people to look into the issue.
"There's a lot of question marks," he said."Was what I read true? I don't know.
"The bottom line is: Through my faith, I have to oppose it," Kiefert, who is Christian, said of homosexuality.
He added that his viewpoints have earned him threats in the past.
"I just hope people respect me for who I am," he said
Ironic, that last. In any case, I haven't addressed hatred or bias at any length because the Supreme Court in Obergefell didn't address it either. The plaintiffs weren't alleging bias, the states weren't admitting to bias, and the justices didn't explore the issue in any depth. However, some of the lower court decisions did consider the issue of bias; here is the blunt language of the Seventh Circuit:
Our pair of cases is rich in detail but ultimately straightforward to decide. The challenged laws discriminate against a minority defined by an immutable characteristic, and the only rationale that the states put forth with any conviction—that same-sex couples and their children don’t need marriage because same-sex couples can’t produce children, intended or unintended—is so full of holes that it cannot be taken seriously.
(The author of this decision was judge Richard Posner; he offered his take on the Obergefell case here.)

As Rep. Kiefert helpfully reminds us, the other major consideration here is religion. Probably a fair number of conservative politicians are saying what they're saying about same-sex marriage not because same-sex marriage particularly bothers them, but because they can't afford to lose the support of people who vote on the basis of religious views.

In the wake of Obergefell, I suspect we'll be seeing more court cases about the limits of religious freedom under the Constitution. Like all rights, First Amendment rights are not absolute, but enumerated rights in the constitution do receive a lot of deference in law. Some county clerks are currently refusing to issue marriage licenses for reasons of religious conscience. The First Amendment guarantees the free exercise of religion, and many of the people quoted in the linked article sound sincere. Nevertheless, it seems to me that those clerks aren't freely exercising their religion—they're forcing their religion on others using the power of the State. I don't think that will hold up legally under the First Amendment.

Some people seem to feel that we Americans means us Christians. That concept doesn't make us a country, though—it makes us a folk. For myself, I think that what we are as countrymen has less to do with cultural things like religion or language, which we inherited from Europe, and everything to do with the Constitution, which set us apart from Europe.

Who do we think we are? The question Roberts posed to his brethren applies to the rest of us as well. Since the Obergefell decision was handed down, I haven't been able to get this question out of my mind. With due respect to the Chief Justice—and applying only the capacities for reason and reflection that all citizens must use to make up their minds—I'm pretty well convinced on the merits that the Supreme Court has just overthrown an unconstitutional law. That is worth celebrating.

Saturday, June 27, 2015

The Perimeter Puzzle Under an Additional Constraint

A reader sent this configuration for the perimeter puzzle:

This suggests a new version of the puzzle:

Maximize perimeter among configurations like the one above, namely: (1) The boundary doesn't self-intersect; and (2) there are no "holes."

(Requirement (1) is saying that we don't allow "kitty-corner" shaded squares, that is, two shaded squares that touch corners, with the other two squares meeting at that corner being unshaded.)

I tried my hand at this and was unable to improve on the reader's example, which has perimeter 40. Here are my best attempts, which also have perimeter 40:

Is 40 maximal? Well, it is not hard to see that a tame shape cannot have perimeter greater than 46. To see this, consider that if any of the 8 unshaded squares had 4 shaded neighbors, then because of the no-kitty-corner constraint, that unshaded square would have to be fully surrounded by shaded squares, that is, the unshaded square would be a hole. But by assumption there are no holes, hence each unshaded square must have 3 or fewer shaded neighbors. Moreover, at least one unshaded square must touch the boundary of the grid, or else the 8 unshaded squares would form a great big hole. So it follows by algorithm (1)–(3) of my last post that the perimeter must be less than or equal to \(8\times 3 + 19 + 4 = 47\). But the perimeter has to be even, so the perimeter must be less than or equal to 46.

I don't actually think there is a tame configuration with perimeter 46—the greatrest value attained seems to be 40.

For what it's worth, I wrote some computer code to identify the tame configurations among the 30 million or so in the full space. (It might have been easier to chuck my old work and build up the tame configurations from scratch, but I had a body of commands sitting there, so....) First I culled the kitty-corner cases, and then because it was easy I culled the single-square holes. For the remaining configurations, I wrote a function to convert the boundary into a graph-theoretic object, and then I used a built-in function to determine whether that graph was a single connected component. A total of 1,512,395 configurations survived the sorting process. Of these, 143,920 had perimeter 40, and none had perimeter greater than 40. So if my code does what it's supposed to do, then this is the maximum value.

Just for interest, here are some randomly chosen maximizers from the computer run:

Friday, June 26, 2015

Reading Judicial Opinions

Judicial opinions, while densely written, can be fascinating to read—even inspiring, because of the exemplars they offer of rigorous textual analysis, fair and disciplined debate, and rational reasoning applied to human affairs. Judges' opinons can also impress with their rhetoric and style. As a non-expert, I usually have to skip over some of the jargon and procedural matters, but after reading enough of these things, you even begin to understand how some of that stuff works.

Here are some notable examples of the genre.

1) No fireworks, but solid: the May 7, 2015 decision that struck down the bulk data collection component of the NSA's domestic spying program. Most of the public debate about the program revolves around constitutional rights, like freedom from unreasonable searches. However, the court case was decided purely on the basis of statutory interpretation. Contrary to the government's claims, the judge agreed with the ACLU that the Patriot Act as written had never authorized the bulk data collection program in the first place. I thought the decision paid very careful attention to the text under dispute. I also admired the way the judge was able to represent the claims of the losing party and give them their due.

2) The challenger: the November 6, 2014 decision that found same-sex marriage bans constitutional, teeing up the June 26, 2015 Supreme Court decision that ultimately ruled otherwise. Judge Sutton's decision was a very sophisticated piece of writing. Knowing that his decision would immediately undergo Supreme Court review, the author threw everything at the wall so that he could attract as many of the justices' votes as possible. The Supreme Court ruled 5-4 against him, but it seems to me that he earned at least the Chief Justice's dissenting vote with his argument that this decision should lie with the people rather than with the courts. Sutton also made the best case one could possibly make for the rational basis of same-sex marriage bans. I thought the greatest weakness of Sutton's decision was that it paid only light attention to the actual injuries of the plaintiffs seeking the relief of his court. Any court case is foremost about the specific conflict occurring among the particular individuals named in the suit; by turning the decision back to "the people," Judge Sutton largely waved away the injuries of the specific people who were seeking redress in his courtroom.

3) The interpreter: Chief Justice John Roberts's majority opinion in the June 25, 2015 decision upholding tax credits in Federally created health care exchanges. This was another statutory interpretation case. The first key to the decision is Roberts's conclusion that the sentence under dispute is actually ambiguous. The second key is the conclusion that the court cannot defer to the Executive branch for resolving the ambiguity, because the ambiguity does not concern a mere detail or technicality but rather the main thrust of the legislation at hand. The decision is interesting because it rejects not only the stunted, literalist textualism of Scalia but also the "tea leaves" approach of divining legislative intent. The key word in the decision is "plan." Roberts bases his decision not on a mysterious divination of legislative intent, but on a simple apperception of the legislative plan, as expressed plainly through a reading of the text as a whole. (More on this angle here.) Finally, I thought this decision was remarkable for the deceptively breezy style of its writing—the work, it seems to me, of both a talented writer and a formidable intellect.

4) Roberts's dissent in the June 26 Supreme Court decision ruling that same-sex marriage bans are unconstitutional. Roberts adopts Sutton's position on the role of the judiciary and combines it with a vehement concern about the implications of Kennedy's new jurisprudence of "dignity." Roberts makes a strong case. He remedies the major weakness of Sutton's decision by stressing the harms to the plaintiffs, and I also thought he put the best possible face on "the argument from definition" (the view, more or less, that the plaintiffs are asking for something that is, if not impossible for them to have, nevertheless reasonable for them not to have, because marriage means a union of a man and a woman). Roberts notes that had the case been about the denial of tangible benefits to same-sex couples, he might have ruled in the plaintiffs' favor; instead, the plaintiffs sought a right that he cannot find in the Constitution. Roberts's real concern seems to be about the expansiveness of the concept of dignity as a constitutional right. Law professor Jeffrey Rosen also highlighted this issue after hearing the oral arguments in the case.

5) The majority decision itself. Stylistically, I have to agree with Scalia that the prose is often overwrought (but occasionally magnificent). The logic of the decision seems to be that if you look carefully at Supreme Court precedents about marriage, you can discover four things that make marriage a fundamental right under the Constitution. Then, you can observe that none of those things are special to opposite-sex unions. Therefore, it is reasonable to conclude that the fundamental right to marriage as accreted through Supreme Court jurisprudence actually includes, in fact substantively always has included, access by couples of the same sex. This decision was Kennedy's life work as a jurist. As Scalia famously predicted, this decision flows from his earlier decisions in Lawrence, Romer, and Windsor, which built the edifice of his concept of dignity in the Constitution.

One last comment on today's decision. I think that two factors made this result inevitable—if not today, then soon enough. One is that Scalia's concept of homosexual acts lost out to Kennedy's concept of homosexual persons. The state can attack actions in law, but the state can't attack persons. Second, although the defenders of same-sex marriage bans did their rhetorical best, once you take away religious justifications for these bans, you aren't left with enough reasoning firepower to win the day. Today's decision is going to be painful for many precisely because it underscores that we are a nation of secular laws, not religious doctrine. Roberts even perceived a subtle hostility to religion in Kennedy's decision, noting that Kennedy left room for religious people to "advocate" and "teach" their views, but said nothing about "exercising" them, which is the First Amendment's verb of choice. Presumably, Kennedy's reply to this would be just as strongly grounded in the Constitution: the exercise of religion is for citizens, not for the government.

The Supreme Court, August 2014

Tuesday, June 23, 2015

Solution to Perimeter Puzzle

On a six-by-six grid, shade 28 squares so that the perimeter of the resulting shape is (a) as small as possible (b) as large as possible.

This puzzle was my Father's Day indulgence. To maximize the perimeter, I intuitively created a "checkerboard" design inside the grid:

The perimeter of this shape is 56—and in fact, 56 is the greatest possible perimeter. To see this, consider any shading of 28 squares whatsoever, leaving 8 squares unshaded. One way to compute the perimeter of the resulting shape is as follows:

(1) For each unshaded square, count +1 for each neighbor that is shaded.

(2) For each shaded square on the boundary of the grid, count +1.

(3) For each shaded corner, count an additional +1.

The total for (1) must be less than or equal to 8 \(\times\) 4 = 32, because there are 8 unshaded squares and an unshaded square can have at most 4 shaded neighbors. Meanwhile, there are 20 boundary squares, so the total for (2) must be less than or equal to 20. And there are 4 corners, so the total for (3) must be less than or equal to 4. Hence, the total perimeter must be less than or equal to 32 + 20 + 4 = 56. QED

The smallest possible perimeter is 22. I found this value intuitively by creating a 5-by-5 block with 3 squares left over. I couldn't think of an optimality proof, so I wrote a computer program to analyze all 30,260,340 possible ways to shade 28 squares on a six-by-six grid. Sure enough, the smallest possible perimeter is 22, attained in the following distinct ways:

After that, I thought some more about how to find the minimum perimeter in some other way besides brute force. You can convert the problem to a quadratic integer program by assigning a variable \(x_i = 0, 1\) to each square and implementing the perimeter computation using algorithm (1)-(3) above. But I wanted an insightful approach. 

It seemed that what I wanted to know was the minimum perimeter of an orthogonal polygon of given area. Googling this question got me nowhere, however.

So by generalizing my simple-minded \(28 = 5\times 5 + 3\) approach, I conjectured that the minimum perimeter would be \(2({\rm Fl}(\sqrt{n})+n\,{\rm div}\,{\rm Fl}(\sqrt{n})+1^*)\), where \(n\) is the number of squares in the polygon, \({\rm Fl}(\cdot)\) is the Floor function, and the asterisk on the 1 means that you only add the 1 if \({\rm Fl}(\sqrt{n}) (n\,{\rm div}\,{\rm Fl}(\sqrt{n})) < n\). This conjecture just says that you can find the minimal perimeter by arranging the shaded squares in a nice rectangular shape, with the extra tiles stacked nicely on the side.

For \(n=1,2,3,\dots\) you get the sequence 4, 6, 8, 8, 10, 10, 12, 12, 12, 14, 14, 14, ....  I figured it couldn't hurt to search for this sequence in the Online Encylopedia of Integer Sequences. And what do you know? It was the minimal perimeter sequence that I was looking for!

The citation given for this result is Harary and Harborth (1976), "Extremal Animals," Journal of Combinatorics, Information & System Sciences 1(1), pp. 1–8. I don't find a PDF freely available online, but the second citation can be downloaded here. A simpler formula for the sequence is \(2{\rm Cl}(2\sqrt{n})\), where \({\rm Cl}(\cdot)\) denotes the Ceiling function. Harary and Harborth found this result by building an optimal configuration in a spiral pattern.

I see now that I would have had better luck at the outset if I'd googled "minimal perimeter polyomino." The first result for that search is this 2005 paper by Kurz, which extends Harary and Harborth by counting the number of optimal configurations. The formula for the number of optimal configurations is pretty complicated, but I think that for the case \(n=28\) there are supposed to be 6 distinct configurations with minimal perimeter 22. However, I only saw 5 distinct optimal configurations during my exhaustive search. I assume the discrepancy arises from the fact that Kurz will have counted the 4-by-7 polyomino, which has perimeter 22 (and hence is optimal too) but which doesn't fit inside the six-by-six grid that constrained our puzzle.

Just for fun, I'll end with a histogram showing how often each perimeter value occurs among the 30,260,340 possible configurations:

The most common perimeter value is 40, attained for example by this configuration:

Postscript: The Online Encyclopedia of Integer Sequences was recently the subject of a newspaper item in The Guardian; read it here. OEIS is supported by donations—having used the tool to such good advantage here, I have donated to them today.

Sunday, June 21, 2015

Perimeter Puzzle

On a six-by-six grid, shade 28 squares so that the perimeter of the resulting shape is (a) as small as possible (b) as large as possible.

Friday, June 19, 2015

Begins With (But Isn't) - Some Answers

1) Think of a word that begins with SUN, even though the word has nothing to do with the Sun in either its meaning or its history.


2) Think of a word that begins with BAD, even though the word has nothing to do with badness in either its meaning or its history.


3) (Challenge) Think of a word that begins with UP, even though the word has nothing to do with the adverb up in either its meaning or its history.


Saturday, June 13, 2015

Begins With (But Isn't)

1) Think of a word that begins with SUN, even though the word has nothing to do with the Sun in either its meaning or its history.

2) Think of a word that begins with BAD, even though the word has nothing to do with badness in either its meaning or its history.

3) (Challenge) Think of a word that begins with UP, even though the word has nothing to do with the adverb up in either its meaning or its history.

Saturday, June 6, 2015

Pronoun Trouble

I don't often write about current events, but since I've been doing grammar posts lately, I thought I'd write about Caitlyn Jenner and the said-he/said-she controversy. What moved me to write was this sentence from an a recent article by Emma Green in The Atlantic:
Calling Jenner "he" versus "she" has important implications for the speaker's understanding of gender identity.
Does calling Jenner "he" versus "she" tell us something about the speaker's understanding of gender identity? It might, or it might not. Myself, I would never address Caitlyn Jenner in anything other than the way she wants to be addressed, but that doesn't have anything to do with my understanding of gender identity. It just has to do with my understanding of manners. If you're introduced to somebody at a party and the person says "Call me Caitlyn," wouldn't it be quite rude of you not to do that? ("Hold on now! I know who you really are, and I'm going to call you...Bruce!") What kind of an asshole would do something like that?

Well, this guy, for one, although I did see that he later apologized.

Much of Twitter might not exist if more people had had better upbringing. I don't think anybody in my family would ever behave the way that guy did, because our mother raised us better than that. She might or might not have celebrated sex-change operations altogether (I never asked her about it), but as a well raised Southerner, she probably would have shaken Caitlyn Jenner's hand at a party and said "I'm pleased to meet you, Caitlyn."

Years ago when I was studying at the Mathematical Institute in Oxford, there was a male researcher who dressed in women's clothes. Or at any rate, I judged it likely that he was male, and people referred to him by a masculine name. I also judged it likely that he was wearing women's clothes, however questionable may have been his habit of wearing thick white socks with open-toed pumps. Anyway, nobody cared. Almost a hundred percent of all mental activity occuring at the Institute was directed toward proving theorems. Maybe Twitter is what it is in part because the effort required to send a Tweet is too small to interfere with the doing of more important things.

Friday, June 5, 2015

Why Is the Sky Blue?

Physicists are often asked to explain such topics as Schrodinger's Cat or the theory of relativity. Once, I was asked what would happen to an astronaut suspended in space midway between two identical black holes. Let's just say it's not a situation you want to find yourself in.

One of the most common questions about the natural world is the question of why the sky is blue. In case you've ever wondered about this, a detailed physics answer for laypersons can be found here.

The Tyndall effect, Rayleigh scattering, and the electromagnetic spectrum—all of this is great physics, but doing justice to it can be difficult at a cocktail party. So what I usually say is this: "The sky is blue because air is blue." This reply captures a lot of the reality in just a few words, so it's efficient that way. It also gives me time to drink my drink while the questioner considers it.

I wonder what Socrates would make of that answer. I thought of him just now because of the following conversation in the Meno. Here Socrates and Meno are discussing color:
MENO: And how do you define color?
SOCRATES: [Flirts with Meno a little, and then says:] Would you like an answer à la Gorgias, such as you would most readily follow?
MENO: Of course I should.
SOCRATES: You and he believe in Empedocles' theory of effluences, do you not?
MENO: Wholeheartedly.
SOCRATES: And passages to which and through which the effluences make their way?
MENO: Yes.
SOCRATES: Some of the effluences fit into some of the passages, whereas others are too coarse or too fine.
MENO: That is right.
SOCRATES: Now you recognize the term 'sight'?
MENO: Yes.
SOCRATES: From these notions, then, 'grasp what I would tell,' as Pindar says. Color is an effluence from shapes commensurate with sight and perceptible by it.
MENO: That seems to me an excellent answer.
SOCRATES: No doubt it is the sort you are used to. ... Yes, it's a high-sounding answer, so you like it....
The Empedoclean explanation of color resembles the physics answer to the question of why the sky is blue, in the sense that both are mechanistic causal explanations given in terms of theoretical entities. Socrates isn't mocking the Empedoclean explanation so much as mocking people like Gorgias and Meno who are so impressed by it. Meno is eager for impressive explanations of things he can't even define. Disappointingly, in the Meno we never do get to hear Socrates' definition of color. And if anybody ever asked Socrates why the sky is blue, I'm not aware of it.

This morning I had an interesting dialogue with my kids about the color of the sky. It went like this:
DAD: ...about why the sky is blue.
ABIGAIL: I know why the ocean is blue!
CLAIRE: Because the ocean reflects the sky.
ABIGAIL: No fair! I was supposed to say it!
DAD: Well, the sky is blue because it's made of air, and air is blue.
ABIGAIL: Sometimes the sky is red.
DAD: Good point.
CLAIRE: No, air is clear. I know it because at night you can see through it to space.
DAD: Well that's true too.
My kids made some interesting points here. Maybe the next time somebody asks me why the sky is blue, I'll just say what Abigail said today: "Sometimes it's red." It's only three words, and it'll give me time to drink my drink.