Wednesday, April 29, 2009

Generalization of the Four Fours Problem

A common middle school and early high school puzzle is the “four fours problem.” The problem is to find a way to represent a given natural number using four fours. Thus, for example one might represent 9 by 4+4+(4/4) or represent 15 as 4*4-(4/4) and so on. The problem as generally phrased leaves deliberately open what operations are allowed. Thus, there may be clever solutions involving factorials or square roots. When I was in 9th grade I antagonized one teacher by solving problems of this sort using more obscure number theoretic functions such as, σ(n), the sum of the positive divisors of a number. Since σ(4)=7, σ(σ(4))=σ(7)=8 and σ(σ(σ(4)))=15, many of these problems become more or less trivial if one is allowed to use this function. Similarly, one cute puzzle is to represent π using four fours; the only solutions I am aware of all involve either inverse trigonometric functions or even more esoteric functions such as the gamma function or the Riemann zeta function. A similar game involves rolling 4 dice and then everyone trying to find a way to represent the number 24 with the numbers on all four dice (variants exist involving drawing cards from a deck as well). One can however ask a more well-defined question: Given, some set of n, ks and and some fixed set of allowed operations can we represent a given m? Or, for a given m, can we produce easy bounds on how many ks we need to represent m? How small can we choose n if we want to be able to represent all m less than some given x using up to n ks?

Assume for a moment that are allowed operations are addition, multiplication, subtraction and division. Define gk(n) to be the minimum number of ks we need to represent n . Thus, for example g1(6)=5 since 6=(1+1)*(1+1+1) and it t is not hard to show that we in fact require 5 1s for 6. Now, for any given k we may write 1 as k/k and may write k=1+1+1…+1 Thus, we have gk(n) ≤ 2 g1(n) and g1(x) ≤ kg1(n). It is thus natural to just think about g1(n). However, even this is a very difficult function to work with. So it is natural to try to understand g1(n) by thinking about the slightly easier function f(n) which is exactly the same as g1(n) but we only allow multiplication and addition as operations.

For the remainder of this post we are going to work with f(n) which is the minimum number of 1s needed to represent n where we can only use multiplication and addition. What can we say about f(n)? It is not hard to show that for all x, f(n) ≤ 1 + 3log2n. To see this, observe that f(1)=1, f(2)=2 and for any given n if we can represent n with k 1s then we can represent 2n and 2n+1 with at most k+3 1s since We have 2n=(1+1)*n and 2n+1=(1+1)*n+1. Thus, f(2n) ≤ f(n)+3, f(2n+1) ≤ f(n)+3 and so the desired result follows by induction. It is also not hard to prove that f(n) ≥ 3log3 n. Despite the highly elementary nature of these bounds, substantially better bounds on f are difficult to come by. Richard Guy’s “Unsolved Problems in Number Theory” last updated as of 2003 does not give substantially better bounds.

There are many questions about representations of these forms that are still unsolved. For example, it is conjectured that if p is prime f(p)=1+f(p-1). That is, if p is a prime the most efficient representation comes from taking a representation of p-1 and then adding 1. For example, f(1)=7 from the representation 7=(1+1)*(1+1+1+1+1) and f(11)=8 which we get from 11=(1+1)*(1+1+1+1+1)+1. Better bounds on f and similar functions turn out to be related to open problems in complexity theory including the P=NP problem. Entry F26 in Guy’s aforementioned book which gives a summary of what is known about this and related problems along with a bibliography. These simple questions about the behavior of f are good examples of why number theory is such an interesting area of mathematics. One can ask very simple, naïve questions which are unsolved. Moreover, those questions often turn out to be related to deep, difficult mathematics.

Sunday, April 19, 2009

Gay Marriage and Gratuitous Promotion of Family Members

My twin has a piece up at the Huffington Post on three lessons progressives should take away from the Vermont legislature's gay marriage decisions. His lessons are 1) Federalism can be progressive 2) Legislatures can enforce rights and 3) Paying attention to the details matter. Points one and two seem to me to be a bit intertwined insofar as unless legislatures are doing things there are few outlets for progressive federalism (for lack of a better term). He makes strong, succinct cases for all three points. Go check it out.

Thursday, April 16, 2009

Horcruxes and Halacha

One of the most iconic creatures in Dungeons and Dragons is the lich. The lich is a powerful mage who has transformed himself into an undead creature and placed his soul or life-force into a small object called a phylactery. Until the object is destroyed, the lich cannot die; if his physical body is destroyed, he simply forms a new body later. D&D is not the only setting with creatures like this. Variants exist in old mythologies as well as appearing in various fantasy books. For example, in Loyd Alexander’s Chronicles of Prydain, an evil wizard breaks off one of his fingers and imbues his soul into it and so cannot be killed until the finger bone is broke. Another recent example is a primary plot element in J.K. Rowling’s Harry Potter series. In those books, evil wizards can make an object called a horcrux by killing someone and then splitting one’s own soul and storing fragment of the soul in the horcrux. This post will examine the ramifications of becoming a lich or of creating a horcrux under halacha(the system of laws kept by Orthodox Jews).

Assuming that magic as described in D&D existed for real, can one halachically become a lich? First, we must ask can one become a wizard or sorcerer? The quick and superficial answer is no since the Torah specifically forbids magic use. However, closer inspection reveals that the answer is not so clear.

Maimonides argued that the Torah actually forbids trickery where one claims to be doing magic. To Maimonides, “magic” in any meaningful sense doesn’t exist. So the abilities of a D&D style wizard would be simply talents that are difficult to explain. Thus, becoming a wizard would be fine as long as one didn’t call them magic except as something like a possible shorthand for a Clarke’s Third Law class of technology . Even if one disagrees with Maimonides and thinks that there is some class of abilities which constitute magic, it still isn’t clear that D&D magic is a problem. Just because we call something magic does not mean that that it was the Torah was referring to when it talked about magic. The standard system of magic used in D&D (not counting 4th edition) uses a so-called Vancian system of magic. In this system, named after science fiction writer Jack Vance, spells must be prepared beforehand and the spells are then stored in the mind. The gestures and arcane words merely release the stored spell. The Vancian system bears little similarity to magic as described in the Torah or Talmud.

Becoming a wizard is probably ok. Assuming one can become a wizard, can one become a lich? This seems much more halachically problematic but a case can be made that the answer is yes. First, in many descriptions, the process to become a lich involves killing others to fuel ones transformation. If one is using such a process, this is obviously not ok. Second, the process seems to involve killing oneself. Killing oneself is not halachically ok. However, we may get away with this if we examine the halachic notion of death. There is a disagreement in the Talmud over how we determine if someone is dead. The two opinions given are whether the person is breathing and whether the person has a heartbeat. However, it isn’t clear if these are descriptive statements or whether they are normative tests of life. For example, the Talmud makes clear that everyone agrees that at decapitation a person is considered dead instantaneously even if the heart and lungs continue to function for a short period of time. If the test (whether breath or heartbeat) are normative descriptions of when someone is alive then one cannot become a lich. Unfortunately, for our prospective frum lich, the opinion that these are normative tests of life and not proxies is not a rare one. If however, heart and lung activity are merely proxies, then it isn’t unreasonable to declare that a lich walking around is halachically alive.

The only remaining issue is that in some editions of D&D, becoming a lich also requires making supplications to dark gods which would be a problem. However, most editions do not have that requirement so for most forms of D&D magic this is not an issue. Thus, one can become a lich.

We can extend this analysis without much effort to the creation of horcruxes. The analysis of J. K. Rowling’s magical system follows through almost identically. However, murdering others to create a horcrux raises halachic problems. But it isn’t clear precisely what constitutes a murder for purposes of a creating a horcrux. If killing someone in any form is sufficient then killing someone during wartime or if carrying out a valid execution would be halachically acceptable routes to creating a horcrux. There’s really no halachic problem with splitting one’s soul. Halacha takes no standpoint on the existence or nature of a soul. Since souls cannot be manipulated by normal means, they are not covered under any halachic rulings. Thus, although the Harry Potter books describe the process of splitting a soul to be profoundly evil, it does not raise any halachic issues. Moreover, since someone with a horcrux is still living (unlike a lich) the entire set of issues about killing oneself can be bypassed. Whether or not halacha allows you to become a lich, it almost certainly allows you to create a horcrux.

Now, astute readers may recall the other definition of the word “phylactery.” The word actually means a small box containing an object of religious or mystical significance. The word is most commonly used in the plural form as a translation for tefillin, the objects traditionally worn by religious Jews in weekday morning prayers. I do own tefillin. This raises an additional question: If I do become a lich, may I use my phylacteries as a phylactery?

Monday, April 13, 2009

Glenn Beck on Harold Koh: Idiocy of the First Degree

Harold Koh is a respected legal theorist. He served as an Assistant Secretary of State under Bill Clinton and was Dean of the Yale Law School. Recently, he has been nominated by President Obama to serve as State Department Legal Adviser, the highest legal position in the State Department. Certain elements of the right have decided that Koh is unacceptable. There are various ludicrous claims circulating, including that he wants to implement Sharia. Glenn Beck had this to say:

There’s so much wrong with this statement that I don’t know where to begin. Beck apparently thinks that the notion that law change over time dates to “the 1920s” in response to “Darwinian evolution.” I can’t tell if this is some sort of garbled critique of judicial activism since Beck doesn’t seem to object only to changes brought by a judiciary but all changes, even those coming from the legislature.

In any event, Beck, here is a quick history lesson: Most legal systems rely on systems of precedent and as, the precedents change, the controlling law changes. This isn’t new at all. One sees this in the Talmud. The basic system of Common Law used in Great Britain and the United States dates back to the Middle Ages, hundreds of years before Darwin. As much as the religious right likes to blame everything on evolution, this has nothing to do with that.

I’m also puzzled by Beck’s statement at another level: Even if we grant him his bizarrely counterfactual claim about the nature of law, does that mean he would rather we have all laws stay as they were in the 1920s? Should we keep anti-miscegenation laws? Should we have no regulations to govern new technologies such as the internet and airplanes?

Jay Sekulow does not come across very well in this segment either. He gives a more measured, somewhat rational critique of Koh. However when Beck asks Sekulow whether Beck is correct, Sekulow says “yes” and then gives his measured statement. I’d have a lot more respect for Sekulow if he had said “no” and then made the same statement.

Beck’s ignorance is made all the more glaring by the fact that he then calls for the firing of people at the New York Times for not, in his opinion, having sufficient understanding of what “transnationalism” means. The arrogance here is so stunning that I’m forced to conclude that this is an example of the Dunning-Kruger effect in action.

I’ve interacted with Koh in the past and he’s clearly a very bright guy; I know personally Dean Koh and his family. He was a trustee of the high school I attended. My twin brother Aaron has been his student at the Yale Law School and is now his research assistant. Thus, it annoys me that this idiot Beck would be given a show on a major news channel to spout such garbage. There is a bright side to this: any sane person can look at what Beck and his allies are saying about Koh. If this is the worst they can come up with, then it makes it all the more clear that Koh is the right man for the job.

Saturday, April 11, 2009

Tweenbots:Robots Use Human Goodwill to Navigate

Tweenbots are a project by Kacie Kinzer to use crowdsourcing to help little robots navigate Manhattan. The robots are small little box shaped things about 6 inches high. The Tweenbots each have a cardboard outside with a smiley face drawn on them. Each robot has a flag attached that explains where the robot is trying to go and asks people to direct it in the right direction. The bots can only travel in straight lines and so they rely on people pointing them in the right directions. Kinzer drops the bot off in one area and then sees how long it takes the bot to get where it is supposed to go.

In the first trial run, it took the robot 42 minutes to get from one corner of Washington Square Park to the opposite corner. Kinzer concealed a video camera in her purse and tailed the bot from far away enough that people would not connect her to the robot.

Kinzer intially expected the bots to be highly disposable given normal attitudes about assisting others as well as worries about terrorism and other issues. However, so far not a single bot has been lost. This speaks surprisingly well of people. Also, these are just cool.

Kinzer's website has pictures and video. Go check it out.

Saturday, April 4, 2009

The American Family Association and Evolution

I just finished my preliminary qualifier exams. Algebra went well aside from a minor brain fart while analysis did not go very well. My brain is a bit of mush right now. Moreover, I realized afterwords that I had made a number of silly mistakes. Lucky for me, I have been saved from feeling stupid by an email I just received from the American Family Association. The AFA has apparently branched out from their usual focus on how homosexuals and Jews are destroying America. The email was primarily a link to advertise some video about animals that somehow "defy" evolution.

According to the advertisement, the movie "enters the fascinating world of animals to reveal sophisticated and complex designs that shake the traditional foundations of evolutionary theory."

According to the website, the video will answer such interesting questions as:

- Are there really creatures that produce fire to defend themselves?

- How does a giraffe get a drink without causing lethal blood pressure to his brain?

- How can Geckos walk upside down, even on glass and not fall?

- How can birds navigate over thousands of miles of ocean and never get lost?

- How do fireflies and glowworms create light that generates no heat?

- How do great whales dive to the bottom of the ocean without the pressure causing them to implode?

- What creature was the inspiration for the helicopter?
- How can some creatures be cut in half and still regenerate themselves? Some can even grow a new head!

- What kind of bird can kill a lion with a single kick?

- How can some dogs know that a storm is coming before it appears, or can sense when their masters are about to experience a seizure?

- Which creature perlexes scientists because of its amazing ability to heal itself, even when it sustains horrendous injuries?

- How do Emperor Penguins go two and a half months without eating or drinking?
This is entire video is apparently an example of the golly-gee-wilikers-that's-so-complicated-it-must-be-made-by-God argument. Some aspects of the advertisement suggest that the video might at times become slightly more sophisticated. The comment about giraffes suggests that the video may also use the frequently rebutted creationist whinings about how the giraffe could have evolved its long neck.

However, there are two entries which stand out. The entry about dogs is most interesting. First, many animals and even some people can tell if a storm is coming due to the change in air pressure. Better hearing also allows some animals to hear thunder when it is far away. I'm genuinely perplexed at what the AFA people thought was complicated about this. It seems like they think that any ability that humans lack must be extraordinairy and difficult to explain. This entry is also interesting because even most young earth creationists agree that dogs evolved from wolves. So the evolution of capabilities is supposedly a problem even when they agree that evolution occurred to give them those capabilities?

The other entry of note is the entry on fireflies. This entry manages to demonstrate even more ignorance than the entry on dogs. Whoever wrote this doesn't understand that their are many examples of phenomena which produce light and little to no heat. Moreover, the mechanism that fireflies use to produce light is very simple, relying on a protein (a type of luciferase), and ATP, the universal energy exchange found in every living cell. This is a well-understood, very simple mechanism. To paraphrase Abe Lincoln, there's not even a ghost of a homeopathic dilution of irreducible complexity here. How fireflies light themselves is understood by young children who have the minimal curosity to wonder how fireflies light themselves. Moreover, this fact is simple enough to explain in even further detail, that when I was a little kid, I had at least two separate books which explained this process in some detail. When I was 12 years old I had strong Young Earth Creationist sympathies, and if you had stated this argument then, I would have likely laughed in your face. Congratulations, AFA, you've shown that you are more ignorant than many little kids.

Thank you AFA. When I opened my email an hour ago, I felt stupid. Now, having seen an example of extreme stupidity and willful ignorance, and am relieved. I have seen the face of idiocy, and not passing an analysis qualifier is not it.

Wednesday, April 1, 2009

Wikipedia's Fascinating Facts

The English Wikipedia has a section on the main page called "Did you know..."(generally abbreviated DYK) which includes interesting facts from recently started or recently expanded Wikipedia articles. Today's DYK is reproduced below:

... that a 1631 Bible commanded readers to commit adultery?
... that Sonia Chang-Díaz won a seat in the Massachusetts Senate after her opponent was accused of stuffing her bra?
... that in 1825, the Court of Exchequer declared all contracts by hobbits illegal and void in England?
... that if you go to a local store three weeks from today, you can probably find Asher Roth asleep in the bread aisle?
... that Caviar, Chardonnay, and Hot Cocoa compete for the love of Ray J?
... that baseball Hall of Famer Rogers Hornsby had his first plate appearance against King Lear?
... that both Egypt and the Holy Land were originally settled by Germans?
... that Sir Winston Churchill competed in the Tall Ships Race with an all-female crew?
... that Wikipedia now has an article about everything?