In Judaism, many communal prayers require a minimum of ten people. This quorum is called a "minyan" which is often also used to mean a service in general. (In Orthodox Judaism, only Jewish adult males count for a minyam while in Conservative Judaism all Jewish adults count). However, certain liturgical elements on fast days (such as a Torah reading at the afternoon prayer) require not just ten present, but ten who are actually fasting.
However, people may not wish to advertise that they are not fasting even if they are willing to assist with the minyan. Moreover, even a very observant individual might have a reason not to fast and would not want people to know about it (such as a medical condition). This leads to the following problem: How do we determine how many people are fasting without requiring people to disclose whether or not they are fasting?
In a recent minyan I attended, this question was handled by the gabbai (the person in charge of running the minyan) asking everyone to close their eyes and hold up one hand if they were fasting. This is obviously unsatisfactory since the gabbai finds out who is fasting. One could suggest slips of paper or the like. but they could be easily connected to particular individuals. To make this problem interesting, it is helpful to assume that everyone knows the identity of the sender of any communication they receive. Is there a solution under which individuals' statuses remain private while the minyan is assured of 10 fasters?
Curiously the answer is yes albeit the solution is a bit cumbersome. Here's how: The gabbai picks a random integer (the distribution doesn't matter although in practice one might want a reasonable distribution that approximates a bell curve or an exponential distribution or something similar). The gabbai takes this integer and adds 1 to it if he is fasting. The gabbai whispers this number to another person. That person adds 1 to the total if he is fasting and similarly passes it on to another person. The last person gives his number to the gabbai. The gabbai now subtracts the random integer that they initially added. The total the gabbai has is the number of people fasting.
A few notes about this algorithm. First, it is important that, when the gabbai is picking a random integer, that every integer has some non-zero probability of being chosen. Consider, for example, what would happen if the gabbai was known to only pick positive integers. If the gabbai picks 1, the next person can tell if the gabbai is not fasting. Thus, the gabbai can never pick 1. But then, by the same logic, the gabbai won't be able to pick 2. Or 3. And so on. This problem is avoided if the gabbai can pick any integer whether or not it is positive.
There is also a degenerate case of if only the gabbia is fasting or only the gabbai is not fasting. In those cases, the exceptional individual can work out the status of everyone else.
The algorithm also assumes that people are not going out of their way to obtain information. If two people bracket a third and cooperate, they can figure out the middle person's status as a faster.
In fact, it turns out that it is possible to make a more sophisticated protocol that would prevent this and similar tricks. This would be a variation of an anonymous voting algorithm. However, these algorithms rely on clever cryptography with large prime numbers which is only believed to work rather than proven to work. Implementation also would require much more computation than can be done by hand.
Less intensive algorithms can be used to increase the number of people who must cooperate. It is, for example, an interesting exercise to construct a variation of the above such that finding out someone's status requires the cooperation of at least three people.
This algorithm in practice is cumbersome. Moreover, the goal it seeks to accomplish is minor since, if the fast day liturgy is used, those sections of the services actually need to be performed by people who are fasting. Thus, the gabbai will need to know the status of at least a few people. However, this algorithm has the slight advantage that, if there are not enough people to recite the fast day liturgy, then no one will know which people cause the deficiency.
Monday, January 4, 2010
Wednesday, December 30, 2009
Integer Complexity: Why Blogging is Fun
A while back I wrote a blog entry about a generalization of the four fours problem. That entry focused on the function f(n) defined as the minimum number of 1s needed to represent n using just addition and multiplication. So for example, f(6)=5 since 6 = (1+1)(1+1+1) and there's no way to represent 6 with four or fewer 1s. Surprisingly little is known about the general behavior of f.
After that blog entry, two commentators, Etienne and Harry, took up examining f in more detail. Harry and I together produced new work on the behavior of f that will likely turn into a paper.
I will attempt here to briefly summarize what was known and how we've improved it. (Reading my original blog entry and my previous follow-up will probably help matters).
It was known that f(n) satisfied the inequalities 3log3 n ≤ f(n) ≤ 3log2 n for n greater than 1. We've improved the upper bound somewhat, replacing 3log2 n with 2.64log2 n. We've also shown that f(n) - 3log3 n is unbounded (that is one can make it as large as one wants if one chooses suitable n). We did this by defining what we call the "defect" of d(n)= f(n) - 3log3 n. We defined Ak to be the set of numbers with defect at most k. Then, we were able to show that each set Ak was way too small to contain every natural number. More technically, we showed that if one defines Ak(x) to be the number of elements in Ak that are at most x, then Ak(x) = O( (log x)^c) with c a function of k.
Also, it was conjectured that if one had a number of the form n=2^a3^b that f(2^a3^b)=2a+3b (aside from the trivial case when a=b=0). Essentially this conjecture stated that the most efficient representation for n arose from the obvious one, that is writing n = (1+1)(1+1)...(1+1) * (1+1+1)(1+1+1)...(1+1+1). Harry, was able to prove that this conjecture held for all such n as long as a was at most 10. Since then, we've been able to improve that bound to a at most 19.
It turns out that for much of the behavior of f, including both of the two problems discussed above, the sets of Ak and some closely related sets are natural objects to consider. Thus, we tried to work on making c as small as we could in the equation Ak(x) = O( (log x)^c). The initial proof gave a very poor bound on c (being able to take c=1024^k). After a series of improvements, primarily by Harry, he was able to take c=4^k and then using a combination
of ideas from the two of us, we got a linear bound. In particular, one can take c=3k/(5- 3log_3 5). Note how this bound grows much slower than the previous bounds. However, we do know that A1(x) is in fact of order log(x)^2 so there's some realm for improvement in that this proof gives an upper bound for c of about 4.96 for A1(x). One thing to note: While these results were proved using induction arguments (as one would expect), one cannot induct on Ak with k a positive integer. One actually needs to induct on Aαk for fixed α less than 1. A good choice of what alpha to use then becomes very important.
Harry has on his blog a long post that summarizes what we have accomplished and discusses them in more detail. See his posts here and here and the other posts he links to.
The moral to this story is that you don't know what interesting things will happen when you blog, especially when you have readers that are as smart or smarter than you.
After that blog entry, two commentators, Etienne and Harry, took up examining f in more detail. Harry and I together produced new work on the behavior of f that will likely turn into a paper.
I will attempt here to briefly summarize what was known and how we've improved it. (Reading my original blog entry and my previous follow-up will probably help matters).
It was known that f(n) satisfied the inequalities 3log3 n ≤ f(n) ≤ 3log2 n for n greater than 1. We've improved the upper bound somewhat, replacing 3log2 n with 2.64log2 n. We've also shown that f(n) - 3log3 n is unbounded (that is one can make it as large as one wants if one chooses suitable n). We did this by defining what we call the "defect" of d(n)= f(n) - 3log3 n. We defined Ak to be the set of numbers with defect at most k. Then, we were able to show that each set Ak was way too small to contain every natural number. More technically, we showed that if one defines Ak(x) to be the number of elements in Ak that are at most x, then Ak(x) = O( (log x)^c) with c a function of k.
Also, it was conjectured that if one had a number of the form n=2^a3^b that f(2^a3^b)=2a+3b (aside from the trivial case when a=b=0). Essentially this conjecture stated that the most efficient representation for n arose from the obvious one, that is writing n = (1+1)(1+1)...(1+1) * (1+1+1)(1+1+1)...(1+1+1). Harry, was able to prove that this conjecture held for all such n as long as a was at most 10. Since then, we've been able to improve that bound to a at most 19.
It turns out that for much of the behavior of f, including both of the two problems discussed above, the sets of Ak and some closely related sets are natural objects to consider. Thus, we tried to work on making c as small as we could in the equation Ak(x) = O( (log x)^c). The initial proof gave a very poor bound on c (being able to take c=1024^k). After a series of improvements, primarily by Harry, he was able to take c=4^k and then using a combination
of ideas from the two of us, we got a linear bound. In particular, one can take c=3k/(5- 3log_3 5). Note how this bound grows much slower than the previous bounds. However, we do know that A1(x) is in fact of order log(x)^2 so there's some realm for improvement in that this proof gives an upper bound for c of about 4.96 for A1(x). One thing to note: While these results were proved using induction arguments (as one would expect), one cannot induct on Ak with k a positive integer. One actually needs to induct on Aαk for fixed α less than 1. A good choice of what alpha to use then becomes very important.
Harry has on his blog a long post that summarizes what we have accomplished and discusses them in more detail. See his posts here and here and the other posts he links to.
The moral to this story is that you don't know what interesting things will happen when you blog, especially when you have readers that are as smart or smarter than you.
Sunday, December 27, 2009
Three Religions Meme
James McGrath has recently tagged me (well. really a very large set of people) with the meme of naming three religions you find fascinating of which you are not or have not been a member.
I'm going to place a few additional restrictions on my choices:
First, I am not going to pick any purely fictitious religions. Thus, for example, I'm not going to pick any religions from Brandon Sanderson's Mistborn series (although there is a very large temptation to try to pick some of those). Similarly, I'm not going to pick any religion
that started as a fictional religion and then became real. Thus, Melkorism and Cthulhu worship are both out. Finally, I'm not going to pick any parody religions. Thus, Invisible Pink Unicornism and Flying Spaghetti Monsterism are both out although I will note that IPUism was around long before FSMism which is a sad little upstart in comparison (I mean, c’mon. It doesn't even have an oxymoron in its title.).
So of the real, non-parody religions, what will I choose are Cargo Cults, Roman Catholicism and Bahai in no particular order.
Cargo cultism is a religion with which some may not be familiar. It is also as far as I am aware the only example where nearly identical religions arose independently which already makes it very interesting. However, where and how cargo cults arose explains this feature. At the same time, it makes them all the more fascinating. During World War II, the United States used islands whose populations previously had had little or no contact with the outside world. Many people in Western and other civilizations believe in forms of sympathetic magic or the like, but small tribal groups often take this to an extreme. In these cases, the tribes saw the US soldiers doing apparently ritualistic activity that included marching in formation, talking to themselves on pieces of wire, and clearing out large fields. The tribes further saw the immediate responses to this activity: Airplanes came and dropped cargo to the soldiers, including food, medicine and clothing. The tribal members concluded that if they could engage in the same ritualistic behavior, they might get the same or even better results.
Thus, the cargo cults were born.
When the soldiers left, the tribes assigned priests who talked to spirits on the radio which would generally consist of a few pieces of wire. They cleared out or kept clear airplane landing fields. And they wore uniforms and conducted drills. These religions were derisively labeled "cargo cults." These remained strong through the mid 1970s. Members retained their beliefs and practices even when confronted with more features of modern civilization and explanations of what US soldiers had been actually doing. Cargo cults still exist in limited numbers today, seventy years after World War II.
The second religion is Roman Catholicism. The Church has been and remains a fascinating set of contradictions. On the one hand, it is hard to reconcile the gilded architecture and massive hierarchy with the ascetic messages preached by Jesus. The Church has a history of encouraging violence from the Crusades to the Inquisition. When the Church has not encouraged war and killing for its own ends, it has been silent when speaking up could save lives. The Church has also actively persecuted individuals such as Galileo who disagreed with the Church. On the other hand, the Church helped preserved learning that would otherwise be lost. The Church was a bastion of knowledge against the tides of ignorance (tides possibly encouraged by aspects of the Church. but still) The Church has provided shelter and relief to the poor for centuries. In the last fifty years, the Church has strived to modernize and reconcile its beliefs with science while many other religions have gone out of their way to attack science.
The Roman Catholic Church is the Church of Torquemada But it is also the Church of George Coyne and J. R. R. Tolkien. Whether the Church survives this next century and whether it embraces modernity or not will be some of the major questions impacting this century.
The third is the Bahai. The Bahai are the youngest of the major Abrahamic religions. They have consistently embraced reason over dogma and thus far have a history of being the least persecutory of the Abrahamic religions (although how much this is due to their still small numbers remains to be seen). If I had to name a single religion that I might be comfortable with drastically increasing in size over the next few centuries, I would likely name the Bahai.
Edit: It was pointed out to me by multiple people that I neglected to tag this meme for anyone. So I'll tag Kurt because he hasn't blogged much since he got married, Apikores because I'm just curious what he has to say, and Kat because she commented on this post already so hey, why not? And I suppose anyone else who has enough free time who reads this blog regularly and has a blog can consider themselves tagged.
I'm going to place a few additional restrictions on my choices:
First, I am not going to pick any purely fictitious religions. Thus, for example, I'm not going to pick any religions from Brandon Sanderson's Mistborn series (although there is a very large temptation to try to pick some of those). Similarly, I'm not going to pick any religion
that started as a fictional religion and then became real. Thus, Melkorism and Cthulhu worship are both out. Finally, I'm not going to pick any parody religions. Thus, Invisible Pink Unicornism and Flying Spaghetti Monsterism are both out although I will note that IPUism was around long before FSMism which is a sad little upstart in comparison (I mean, c’mon. It doesn't even have an oxymoron in its title.).
So of the real, non-parody religions, what will I choose are Cargo Cults, Roman Catholicism and Bahai in no particular order.
Cargo cultism is a religion with which some may not be familiar. It is also as far as I am aware the only example where nearly identical religions arose independently which already makes it very interesting. However, where and how cargo cults arose explains this feature. At the same time, it makes them all the more fascinating. During World War II, the United States used islands whose populations previously had had little or no contact with the outside world. Many people in Western and other civilizations believe in forms of sympathetic magic or the like, but small tribal groups often take this to an extreme. In these cases, the tribes saw the US soldiers doing apparently ritualistic activity that included marching in formation, talking to themselves on pieces of wire, and clearing out large fields. The tribes further saw the immediate responses to this activity: Airplanes came and dropped cargo to the soldiers, including food, medicine and clothing. The tribal members concluded that if they could engage in the same ritualistic behavior, they might get the same or even better results.
Thus, the cargo cults were born.
When the soldiers left, the tribes assigned priests who talked to spirits on the radio which would generally consist of a few pieces of wire. They cleared out or kept clear airplane landing fields. And they wore uniforms and conducted drills. These religions were derisively labeled "cargo cults." These remained strong through the mid 1970s. Members retained their beliefs and practices even when confronted with more features of modern civilization and explanations of what US soldiers had been actually doing. Cargo cults still exist in limited numbers today, seventy years after World War II.
The second religion is Roman Catholicism. The Church has been and remains a fascinating set of contradictions. On the one hand, it is hard to reconcile the gilded architecture and massive hierarchy with the ascetic messages preached by Jesus. The Church has a history of encouraging violence from the Crusades to the Inquisition. When the Church has not encouraged war and killing for its own ends, it has been silent when speaking up could save lives. The Church has also actively persecuted individuals such as Galileo who disagreed with the Church. On the other hand, the Church helped preserved learning that would otherwise be lost. The Church was a bastion of knowledge against the tides of ignorance (tides possibly encouraged by aspects of the Church. but still) The Church has provided shelter and relief to the poor for centuries. In the last fifty years, the Church has strived to modernize and reconcile its beliefs with science while many other religions have gone out of their way to attack science.
The Roman Catholic Church is the Church of Torquemada But it is also the Church of George Coyne and J. R. R. Tolkien. Whether the Church survives this next century and whether it embraces modernity or not will be some of the major questions impacting this century.
The third is the Bahai. The Bahai are the youngest of the major Abrahamic religions. They have consistently embraced reason over dogma and thus far have a history of being the least persecutory of the Abrahamic religions (although how much this is due to their still small numbers remains to be seen). If I had to name a single religion that I might be comfortable with drastically increasing in size over the next few centuries, I would likely name the Bahai.
Edit: It was pointed out to me by multiple people that I neglected to tag this meme for anyone. So I'll tag Kurt because he hasn't blogged much since he got married, Apikores because I'm just curious what he has to say, and Kat because she commented on this post already so hey, why not? And I suppose anyone else who has enough free time who reads this blog regularly and has a blog can consider themselves tagged.
Sunday, December 13, 2009
Off-Topic Lovecraftian Horrors: Adventures of the Squamous and Rugose
Here are two marginally related videos that I could not resist sharing:
First, we have the adventures of Lil' Cthulhu. It's a new day and the stars are right. It's time to play. Wake up Lil' Cthulhu!
This is an excellent video for those who want their children to be inducted into the ceremonies and blasphemous, mind-shattering secrets of the Great Old Ones from a young age. Starting early is important!
And following this, we have Heartache Over Innsmouth. This is a moving romantic song, about a man who has fallen in love with a girl who joins the cult of Dagon.
As far as I am aware, Dagon is the only deity in Lovecraft which actually appears in the Bible. Dagon was a common Semitic agricultural deity. For many centuries, commentators(such as Rashi) noted the similarity between Dagon and the Hebrew word for fish, dag. This lead them to believe that Dagon was some sort of oceanic or fish deity. Laboring under this belief, Lovecraft chose Dagon as the name of the horrific creature under the ocean which rules over the Deep Ones. Some later writers have attempted to retcon this discrepancy by suggesting that Dagon was not that horrific being's name but rather was a name given to it by the cultists as they needed a name. They thus chose that name due to their own mistaken belief that Dagon in the Bible was a fish deity.
First, we have the adventures of Lil' Cthulhu. It's a new day and the stars are right. It's time to play. Wake up Lil' Cthulhu!
This is an excellent video for those who want their children to be inducted into the ceremonies and blasphemous, mind-shattering secrets of the Great Old Ones from a young age. Starting early is important!
And following this, we have Heartache Over Innsmouth. This is a moving romantic song, about a man who has fallen in love with a girl who joins the cult of Dagon.
As far as I am aware, Dagon is the only deity in Lovecraft which actually appears in the Bible. Dagon was a common Semitic agricultural deity. For many centuries, commentators(such as Rashi) noted the similarity between Dagon and the Hebrew word for fish, dag. This lead them to believe that Dagon was some sort of oceanic or fish deity. Laboring under this belief, Lovecraft chose Dagon as the name of the horrific creature under the ocean which rules over the Deep Ones. Some later writers have attempted to retcon this discrepancy by suggesting that Dagon was not that horrific being's name but rather was a name given to it by the cultists as they needed a name. They thus chose that name due to their own mistaken belief that Dagon in the Bible was a fish deity.
Monday, December 7, 2009
Virgin Galactic, Star Trek and Retconning
Virgin Galactic has unveiled their newest model of spaceship, SpaceShipTwo. Virgin Galactic, part of Richard Branson's Virgin Group, is trying to make affordable space tourism. Where by affordable, we mean affordable if you have $200,000 to burn. And all you get is a quick sub-orbital hop. We are at the dawn of private space travel, and one could easily spend much time discussing the long-term political, social and religious implications. I'm not going to do that.
Instead, I'm going to focus on the names of the ships. The first ship will be named the VSS Enterpise. VSS stands for "Virgin Space Ship." The second ship according to some reports will be the VSS Voyager. Yes. Enterprise and Voyager. As in from Star Trek.
Officially, the VSS Enterprise is named not just after the fictional ships but also the real ships that have been given that name, including the space shuttle Enterprise.
Now here's where things get complicated. The space shuttle Enterprise was named after the USS Enterprise (NCC-1701), commanded by James Tiberius Kirk; the real shuttle Enterprise is named after the fictional ship. But it gets better. The writers of Star Trek retconned in the existence of the Enterprise space shuttle into their universe. That is, in the Star Trek universe, the Enterprise shuttle is now one of the long line of ships that existed before the Federation ships. But the Enterprise shuttle in the Star Trek universe is not named after the starship USS Enterprise because in the Star Trek universe, Star Trek never occurred as a 20th century television show. There has even been a Star Trek novel which had a plot focusing on the space shuttle Enterprise finally getting a chance to fly (in both the Star Trek universe and in our own universe the Enterprise was used a test shuttle but never flew into space). I've been unable to track down this novel although I did read it many years ago. If anyone can track down the novel I'd be very grateful.
I suspect that in a few years we will see the same thing for Branson's ship. That is, there will be official Star Trek material which includes Branson's ship as a ship that existed in the Star Trek universe.
I'm hoping that the ships three and four are named Serenity and the Millennium Falcon. Star Wars at least has the advantage of having occurred a long, long time ago, in a galaxy, far far away. So they won't have to deal with the oddity of incorporating into the universe real ships that were named after ships from their universe.
Instead, I'm going to focus on the names of the ships. The first ship will be named the VSS Enterpise. VSS stands for "Virgin Space Ship." The second ship according to some reports will be the VSS Voyager. Yes. Enterprise and Voyager. As in from Star Trek.
Officially, the VSS Enterprise is named not just after the fictional ships but also the real ships that have been given that name, including the space shuttle Enterprise.
Now here's where things get complicated. The space shuttle Enterprise was named after the USS Enterprise (NCC-1701), commanded by James Tiberius Kirk; the real shuttle Enterprise is named after the fictional ship. But it gets better. The writers of Star Trek retconned in the existence of the Enterprise space shuttle into their universe. That is, in the Star Trek universe, the Enterprise shuttle is now one of the long line of ships that existed before the Federation ships. But the Enterprise shuttle in the Star Trek universe is not named after the starship USS Enterprise because in the Star Trek universe, Star Trek never occurred as a 20th century television show. There has even been a Star Trek novel which had a plot focusing on the space shuttle Enterprise finally getting a chance to fly (in both the Star Trek universe and in our own universe the Enterprise was used a test shuttle but never flew into space). I've been unable to track down this novel although I did read it many years ago. If anyone can track down the novel I'd be very grateful.
I suspect that in a few years we will see the same thing for Branson's ship. That is, there will be official Star Trek material which includes Branson's ship as a ship that existed in the Star Trek universe.
I'm hoping that the ships three and four are named Serenity and the Millennium Falcon. Star Wars at least has the advantage of having occurred a long, long time ago, in a galaxy, far far away. So they won't have to deal with the oddity of incorporating into the universe real ships that were named after ships from their universe.
Sunday, December 6, 2009
Excessive Executive Compensation, Health Care and More Gratuitous Promotion of Family Members
My twin has a piece up at the Huffington Post in which he examines the sections of the proposed health care reform that concern compensation for insurance executives. Under current regulations, corporations can easily deduct executive compensation. This legislation will substantially restrict such deduction by health insurance companies. Aaron argues that the proposed caps on such compensation do not go far enough. In particular, there is no good reason to have such restrictions for insurance companies and not other companies. He makes a good case and also explains in detail the relevant regulations that govern the status quo. My one nitpick is that in many locations a game of Ms. Pacman costs more than a quarter. Go and read.
Tuesday, December 1, 2009
Westboro Baptist Church at Boston University
Readers are likely familiar with the Westboro Baptist Church as the strange cult run by Fred Phelps which is devoted to telling the world that God hates them. A lot. They are most known for the slogans "God Hates America" and "God Hates Fags." Pretty much there is no group they don't hate. They even have a song about called God Hates the World, to the tune of "We Are the World." They have a fascinating eschatology in which in the end time God will ask them what should be done with the rest of humanity and they'll gleefully tell God to send humanity to hell. Some people who don't know much about the Church have speculated that the Church exists really just to make the right-wing look bad.
Why am I thinking of the Westboro Baptist Church? Today they came to Boston University to protest. I think this time they were nominally protesting Jews. Or something like that. Apparently they had signs attacking a lot of different groups.
Unfortunately, I had office hours when they were protesting. This isn't fun. When Ray Comfort was distributing his version of Origin of Species to a hundred universities across the nation, he neglected to include Boston University and I was unable to get to Harvard or MIT where there was distribution.
I've concluded that there is a God. God is taunting me by dangling interesting groups just close enough that I'm aware of them but not so close as to actually get to talk to them. God probably sees me as sort of like a cat and sees the various crazies as akin to a laser pointer.
Just my luck, Neturei Karta will probably come to campus and I'll miss them also.
Why am I thinking of the Westboro Baptist Church? Today they came to Boston University to protest. I think this time they were nominally protesting Jews. Or something like that. Apparently they had signs attacking a lot of different groups.
Unfortunately, I had office hours when they were protesting. This isn't fun. When Ray Comfort was distributing his version of Origin of Species to a hundred universities across the nation, he neglected to include Boston University and I was unable to get to Harvard or MIT where there was distribution.
I've concluded that there is a God. God is taunting me by dangling interesting groups just close enough that I'm aware of them but not so close as to actually get to talk to them. God probably sees me as sort of like a cat and sees the various crazies as akin to a laser pointer.
Just my luck, Neturei Karta will probably come to campus and I'll miss them also.
Subscribe to:
Posts (Atom)
