That IACR preprint
38 minutes ago
Sunday, May 29, 2011
Harry Potter and the Methods of Rationality
I've mentioned Harry Potter and the Methods of Rationality before. It is a Harry Potter fanfiction written by Eliezer Yudkowsky. The central premise of the work is that Harry instead of having abusive step-parents has loving step-parents and his step-father is a scientist. Young Harry grows up learning all about the scientific method, critical thinking, and cognitive biases. HPMR does have its positives and negatives. Overall it is hilarious but there are times when Harry is didactic and Yudkowsky has clear difficulty in making his characters sound like eleven year olds. But overall, it is worth reading. I am recommending the fiction now for two reasons. The fiction has recently become the most reviewed fanfiction on fanfiction.net. Second, for the last Vericon masquerade a friend and I cosplayed as the versions of Harry and Hermione from HPMR. Pictures can be found at her blog. Note that the costumes were not made entierly by us. The badges were made by Ellen Dimiduk who does excellent costuming work. Now, Yudkowksy has a policy that people who make cool artwork about the story get cameos in the story. So the latest chapter of HPMR mentions two Hogwarts students, Katarina and Joshua, who helped make costumes for Hogwarts students. So of course people need to go read it now since I'm a character! So if you aren't reading it yet, go and read.
Friday, May 20, 2011
A brief note on the Rapture
Michael Hartell of the Sentinel and Enterprise interviewed me in my capacity as a spokesentity for the Boston Skeptics talking about the Rapture. Hartell's article focuses on Harold Camping's prediction that the Rapture will take place tomorrow. His article is worth reading, although there are a few things that didn't get into the final article that I think are worth mentioning: First, the entire "Rapture" doctrine as it exists in modern times is only a few centuries old and only became at all popular due to the preaching of John Darby in the early part of the 19th century. Second, this is a good example of the sort of serious damage that erroneous beliefs can create. The New York Times article on the same subject focuses on the Haddad family where the parents believe the Rapture will occur tomorrow and the children do not. In that article, the Haddads have stopped saving up for college for their children because they believe that it will never happen. The children will suffer when the Rapture doesn't take place and they then can't afford to get good educations. These parents are not going to risk their childrens' lives in the same way that parents who refuse to vaccinate are actively endangering their lives, but the basic problem is the same: hideously inaccurate beliefs about reality are hurting bystanders.
Tuesday, May 17, 2011
Multiplicative functions and almost division
A function f(n) with range in the integers is said to be multiplicative if f(ab)=f(a)f(b) whenever a and b are relatively prime. A function is said to be completely multiplicative if this applies for all a and b whether or not a and b are relatively prime. Some of my prior posts have discussed multiplicative functions (e.g. this post on Mersenne primes and perfect numbers). An important thing to note is that a multiplicative function is determined by its values at prime powers, while a completely multiplicative function is determined by its values at primes.
Let f and g be two functions from the positive integers to the integers. Let K(f,g)(x) be the number of n less than x such that f(n) does not divide g(n). We say that f almost always divides g if f(n) divides g(n) for almost all n if K(f,g)(x) = o(x) (or to put it another way, the set of exceptions has density zero). Obviously, almost divisibility is weaker than divisibility. Almost divisibility shares many of the properties of divisibility; it is a transitive relation. One important difference between divisibility and almost divisibility is that among positive functions, divisibility is an anti-symmetric relation (that is, if fg, and gf then f=g). This is not true for almost divisibility, but is true for almost divisibility if we restrict our attention to multiplicative functions.
Are there interesting examples of non-trivial almost divisibility where one doesn't have divisibility? Yes. Let σ(n) be the sum of the positive divisors of n, and let τ(n) be the number of positive divisors of n. Erdos showed that τ almost divides σ and showed through similar logic that τ almost divides the Euler φ function.
Why am I thinking about these functions? I noticed that some multiplicative functions divide a positive completely multiplicative function. Thus, for example φ divides the completely multiplicative f such that for any prime p, f(p)=p(p-1). However, other cases don't have such examples. It isn't too hard to show that there's no such completely multiplicative function for τ or σ. But, the situation changes drastically in the case of almost divisibility. We in fact have that for any function f from the natural number to the natural numbers, there is a completely multiplicative function g such that f almost divides g. We shall call such a g, a "completely multiplicative almost multiple" (or CMAM) Moreover, we can construct such a function explicitly.
Proposition: Let f(n) be a function from N to N, and let g(n) be the completely multiplicative function defined by g(p) = is the least common multiple of f(1),f(2),f(3)...f(2^p). Then g is a completely multiplicative almost multiple of f.
In order to prove this result, we need another notion, that of normal order. Often, to describe the behavior of a poorly behaved function, number theorists like to show that it asymptotic to a well behaved function in the sense that the limit of their ratios is 1. Thus, for example, the prime number theorem says that the poorly behaved function π(n) that counts the number of primes that are at most n is asymptotic to n/log n. But for many functions we care about this sort of statement is much too strong. Let ω(n) be the number of distinct prime divisors of n, and let Ω(n) be the total number of prime factors. Then these functions hit 1 infinitely often and so clearly are not asymptotic to any nice functions. However, ω and Ω possess a normal order, in the sense that for any ε > 0, we have that excepting a set of density 0, (1-ε) log log n < ω(n) < (1+ε) log log n and the same holds for Ω(n). (More refined estimates exist but we don't need them for these remarks.) An important heuristic that stems from this result is that most numbers look very close to square free in the sense that they have a lot of prime factors and very few of the prime factors occur more than once.
Now, to prove our result, we observe that excepting a set of density zero, we have Ω(n) < 2 log log n . So ignoring a set of density zero, the largest prime factor of n, call it p, is at least n^(1/(2 log log n)), and so f(n) appears as a term in g(p).
Obviously, for any f, the constructed CMAM grows very fast. However, this doesn't need to be the case, and it might be that in specific contexts one can substantially reduce this growth rate. So, this leaves me with three questions, one broad and two specific:
1) How much can we improve on reducing the growth rate of the CMAM for a function f? There are obvious steps to take in the construction but they still make it grow very quickly.
2) Let g(n) be a CMAM for σ. Does it follow that g(n) is not O(n^k) for any k? I strongly suspect this is true but don't see how to prove it.
3) One can through more careful work show that there is a CMAM for τ that is 0(x). What is the best possible growth rate for such a function?
While I've seen individual papers that have discussed specific functions being almost divisible by each other, I'm not aware any substantial work on their general structure. I don't know if this is due to my ignorance of the literature, the fault of almost divisibility being too weak a property to be interesting, or some other cause.
Let f and g be two functions from the positive integers to the integers. Let K(f,g)(x) be the number of n less than x such that f(n) does not divide g(n). We say that f almost always divides g if f(n) divides g(n) for almost all n if K(f,g)(x) = o(x) (or to put it another way, the set of exceptions has density zero). Obviously, almost divisibility is weaker than divisibility. Almost divisibility shares many of the properties of divisibility; it is a transitive relation. One important difference between divisibility and almost divisibility is that among positive functions, divisibility is an anti-symmetric relation (that is, if fg, and gf then f=g). This is not true for almost divisibility, but is true for almost divisibility if we restrict our attention to multiplicative functions.
Are there interesting examples of non-trivial almost divisibility where one doesn't have divisibility? Yes. Let σ(n) be the sum of the positive divisors of n, and let τ(n) be the number of positive divisors of n. Erdos showed that τ almost divides σ and showed through similar logic that τ almost divides the Euler φ function.
Why am I thinking about these functions? I noticed that some multiplicative functions divide a positive completely multiplicative function. Thus, for example φ divides the completely multiplicative f such that for any prime p, f(p)=p(p-1). However, other cases don't have such examples. It isn't too hard to show that there's no such completely multiplicative function for τ or σ. But, the situation changes drastically in the case of almost divisibility. We in fact have that for any function f from the natural number to the natural numbers, there is a completely multiplicative function g such that f almost divides g. We shall call such a g, a "completely multiplicative almost multiple" (or CMAM) Moreover, we can construct such a function explicitly.
Proposition: Let f(n) be a function from N to N, and let g(n) be the completely multiplicative function defined by g(p) = is the least common multiple of f(1),f(2),f(3)...f(2^p). Then g is a completely multiplicative almost multiple of f.
In order to prove this result, we need another notion, that of normal order. Often, to describe the behavior of a poorly behaved function, number theorists like to show that it asymptotic to a well behaved function in the sense that the limit of their ratios is 1. Thus, for example, the prime number theorem says that the poorly behaved function π(n) that counts the number of primes that are at most n is asymptotic to n/log n. But for many functions we care about this sort of statement is much too strong. Let ω(n) be the number of distinct prime divisors of n, and let Ω(n) be the total number of prime factors. Then these functions hit 1 infinitely often and so clearly are not asymptotic to any nice functions. However, ω and Ω possess a normal order, in the sense that for any ε > 0, we have that excepting a set of density 0, (1-ε) log log n < ω(n) < (1+ε) log log n and the same holds for Ω(n). (More refined estimates exist but we don't need them for these remarks.) An important heuristic that stems from this result is that most numbers look very close to square free in the sense that they have a lot of prime factors and very few of the prime factors occur more than once.
Now, to prove our result, we observe that excepting a set of density zero, we have Ω(n) < 2 log log n . So ignoring a set of density zero, the largest prime factor of n, call it p, is at least n^(1/(2 log log n)), and so f(n) appears as a term in g(p).
Obviously, for any f, the constructed CMAM grows very fast. However, this doesn't need to be the case, and it might be that in specific contexts one can substantially reduce this growth rate. So, this leaves me with three questions, one broad and two specific:
1) How much can we improve on reducing the growth rate of the CMAM for a function f? There are obvious steps to take in the construction but they still make it grow very quickly.
2) Let g(n) be a CMAM for σ. Does it follow that g(n) is not O(n^k) for any k? I strongly suspect this is true but don't see how to prove it.
3) One can through more careful work show that there is a CMAM for τ that is 0(x). What is the best possible growth rate for such a function?
While I've seen individual papers that have discussed specific functions being almost divisible by each other, I'm not aware any substantial work on their general structure. I don't know if this is due to my ignorance of the literature, the fault of almost divisibility being too weak a property to be interesting, or some other cause.
Monday, May 2, 2011
Osama bin Laden's death, Barack Obama, and the Judeo-Christian heritage of the United States: A response to my brother
In the last 24 hours, everyone has been talking about Osama bin Laden's death. Last night, after the President's speech, people around the country celebrated. Here in Boston, this apparently became another excuse for college students to get drunk. I heard well into the night screams of "USA! USA!" and at one point an attempt to sing "America, Fuck Yeah!" from Team America.
There were more measured responses including a piece in the Huffington Post by my brother Nathaniel. Unfortunately, many of the more measured responses, including this one, are misguided.
Nathaniel listed five aspects of the President's remarks which in his view stood out:
I don't have any significant problems with the second or fifth points, but the other three are problematic.
In his first point, Nathaniel portrays as a positive that which isn't. He also confuses a variety of different issues. Targeting high ranking terrorists and killing them is distinct from whether or not people such as Khalid Shaikh Mohammed should get civilian trials once they are in our custody. But we can direct our military against targets at the same time that we use civllian trials for those who are captured. The first World Trade Center bombers and the Oklahoma City bombers were both tried successfully in civil courts. Being at war does not mean we need to ignore due process.
Nathaniel's third point is deeply wrong. The Judeo-Christian heritage of this country is deeply exaggerated. The US Constitution bears almost no signs of Judeo-Christian values. There are only three signs of such religious influence in the Constitution, and all are comparatively minor. First, laws presented to the President become law in 10 days after presentation to the President, excepting Sundays. Second, the treason clause requires two witnesses of an overt act to convict or a confession in court. This requirement echos the Old Testament rule for conviction of severe crimes which requires testimony of two witnesses. Third, the Constitution is dated "in the year of our Lord," a conventional phrase at the time.
Moreover, Nathaniel's statement portrays the Judeo-Christian heritage in the worst light possible. I'm proud of my Jewish heritage. But there's something deeply wrong when that heritage's primary lesson is an endorsement of retributive justice. It is noteworthy that the most substantial impact of the Bible on the text of the Constitution is to make conviction and punishment more difficult, not to endorse retribution. Indeed, it is a common theme in that heritage that we understand that even our enemies are people who can suffer. At the Passover Seder, even as the deliverance of the Israelites is celebrated, we remove a drop of wine from the cup for each of the Ten Plagues, remembering the Egyptian suffering.
Most troubling of all is the notion that mentioning God constitutes a " welcome shift from the president who went out of his way to give a nod to "non-believers" in his inaugural address." Approximately 10% of the people in United States self-identify as having no religion, and about 2% of the U.S. population identifies as either atheist or agnostic. Non-believers in the US have ranged from Carl Sagan to George Clooney, from Neil deGrasse Tyson to Bill Gates. Non-believers are an important part of the United States, intertwined with everything that makes America a great nation. All citizens deserve the same respect, whether they are differ by skin color, politics, or religious beliefs.
Nathaniel's fourth point is also misguided. The building of the transcontinental railroad was a triumph of the American spirit. And yes, America is really in a decline when our example of "we can do everything" is to kill our enemies. We are the only nation that has ever sent people to the moon. Yet, no one has walked on the moon in forty years. The shuttle will soon no longer be operational, and the US will need to rely on Russia for space flight. We are in a decline. No speech can hide that. And pretending otherwise is not a good thing. We must fight that decline. But we cannot fight it if we do not acknowledge the threat.
Nathaniel ended his piece by saying that he was proud of the troops and proud of the President. I can understand being proud of the troops. They risked their lives. We should be thankful to those soldiers who put their lives on the line to protect what we hold dear. This is not a good reason to be proud of the Ppresident. Nothing he did substantially impacted this result. It is possible that actual policy changes by Obama somehow lead to these events by making it easier to track down Osama. But I've seen no indication of that. Let's not give him credit that he isn't due. It is likely that in the 2012 election I will vote to reelect Obama, but that has almost nothing to do with these events, and it shouldn't. Instead of responding to these recent events, we should all vote for whichever candidate we think will be the most competent President with the policies that are best.
There were more measured responses including a piece in the Huffington Post by my brother Nathaniel. Unfortunately, many of the more measured responses, including this one, are misguided.
Nathaniel listed five aspects of the President's remarks which in his view stood out:
1) Obama emphasized that America and al Qaeda are "at war." This is an important shift from the president who wanted to try Khalid Shaikh Mohammed in a civilian court in New York, and who vowed to shut down Gitmo during the 2008 campaign. The tone here tonight was clear: The terrorists who plot against the United States are (illegal) combatants who deserve the full front of our military fury, not our legal rights.
2) The president gave a nod to his predecessor, in an acknowledgment that America has never been, nor ever will be, at war with Islam. This took class and grace, and Obama merits credit for it.
3) This speech was traditional. From the inclusion of "under God" in his closing remarks, to the references to retributive "justice," Obama channeled the Judeo-Christian values that still define our nation -- again, a welcome shift from the president who went out of his way to give a nod to "non-believers" in his inaugural address.
4) Somehow, Obama managed to take this moment to combat feelings of American declinism. The memo: We can do anything we set out to do. Compare this simple yet effective message to his recent flop of a State of the Union speech, in which the example of our greatness was the fact that "America is the nation that built the transcontinental railroad." This moment disproves those who sing the song of the "fall of American Empire," resolve, and spirit.
5) Most importantly, Obama tonight reaffirmed America's role as a force for good in the world, a force that extends beyond our borders. After U.S. troops took a backseat in NATO operations against Muammar Gaddafi, many (including me) worried that our will to "oppose any foe" in the defense of liberty played second fiddle to the whims of the UN, EU, and the Arab League. Thankfully and surprisingly, Obama reaffirmed our commitment to be a "shining beacon on a hill" to light the world.
I don't have any significant problems with the second or fifth points, but the other three are problematic.
In his first point, Nathaniel portrays as a positive that which isn't. He also confuses a variety of different issues. Targeting high ranking terrorists and killing them is distinct from whether or not people such as Khalid Shaikh Mohammed should get civilian trials once they are in our custody. But we can direct our military against targets at the same time that we use civllian trials for those who are captured. The first World Trade Center bombers and the Oklahoma City bombers were both tried successfully in civil courts. Being at war does not mean we need to ignore due process.
Nathaniel's third point is deeply wrong. The Judeo-Christian heritage of this country is deeply exaggerated. The US Constitution bears almost no signs of Judeo-Christian values. There are only three signs of such religious influence in the Constitution, and all are comparatively minor. First, laws presented to the President become law in 10 days after presentation to the President, excepting Sundays. Second, the treason clause requires two witnesses of an overt act to convict or a confession in court. This requirement echos the Old Testament rule for conviction of severe crimes which requires testimony of two witnesses. Third, the Constitution is dated "in the year of our Lord," a conventional phrase at the time.
Moreover, Nathaniel's statement portrays the Judeo-Christian heritage in the worst light possible. I'm proud of my Jewish heritage. But there's something deeply wrong when that heritage's primary lesson is an endorsement of retributive justice. It is noteworthy that the most substantial impact of the Bible on the text of the Constitution is to make conviction and punishment more difficult, not to endorse retribution. Indeed, it is a common theme in that heritage that we understand that even our enemies are people who can suffer. At the Passover Seder, even as the deliverance of the Israelites is celebrated, we remove a drop of wine from the cup for each of the Ten Plagues, remembering the Egyptian suffering.
Most troubling of all is the notion that mentioning God constitutes a " welcome shift from the president who went out of his way to give a nod to "non-believers" in his inaugural address." Approximately 10% of the people in United States self-identify as having no religion, and about 2% of the U.S. population identifies as either atheist or agnostic. Non-believers in the US have ranged from Carl Sagan to George Clooney, from Neil deGrasse Tyson to Bill Gates. Non-believers are an important part of the United States, intertwined with everything that makes America a great nation. All citizens deserve the same respect, whether they are differ by skin color, politics, or religious beliefs.
Nathaniel's fourth point is also misguided. The building of the transcontinental railroad was a triumph of the American spirit. And yes, America is really in a decline when our example of "we can do everything" is to kill our enemies. We are the only nation that has ever sent people to the moon. Yet, no one has walked on the moon in forty years. The shuttle will soon no longer be operational, and the US will need to rely on Russia for space flight. We are in a decline. No speech can hide that. And pretending otherwise is not a good thing. We must fight that decline. But we cannot fight it if we do not acknowledge the threat.
Nathaniel ended his piece by saying that he was proud of the troops and proud of the President. I can understand being proud of the troops. They risked their lives. We should be thankful to those soldiers who put their lives on the line to protect what we hold dear. This is not a good reason to be proud of the Ppresident. Nothing he did substantially impacted this result. It is possible that actual policy changes by Obama somehow lead to these events by making it easier to track down Osama. But I've seen no indication of that. Let's not give him credit that he isn't due. It is likely that in the 2012 election I will vote to reelect Obama, but that has almost nothing to do with these events, and it shouldn't. Instead of responding to these recent events, we should all vote for whichever candidate we think will be the most competent President with the policies that are best.
Subscribe to:
Posts (Atom)
