Tuesday, August 17, 2010

Conservapedia, P=NP, and the Fields Medal

Conservapedia, the right-wing, Christian alternative to Wikipedia has once again broken new ground. In previous entries we've discussed Conservapedia's founder Andrew Schlafly self-Godwining and Conservapedia's interesting take on Popperian falsifiability. Others have discussed Conservapedia's objections to special and general relativity. Now, Conservapedia is at it again.

Apparently, Conservapedia has taken a recent interest in mathematics. First, they added to their mainpage a take on the recent reports that Deolalikar had proven that P ≠ NP . Conservapedia announced:

University professors pile on against a non-professor's claim to have solved one of the millennium problems. MIT Assistant Professor Scott Aaronson declares, "Vinay Deolalikar still hasn’t retracted his P≠NP claim, but a clear consensus has emerged that the proof, as it stands, is fatally flawed." He absurdly adds, with a cite to Richard Dawkins, "the only miracle in life is that there are no miracles, neither in mathematics nor in anything else."

But the best of the public, aided by the internet, will inevitably solve more problems than liberal colleges will - just as Grigori Perelman solved another millennium problem. The future belongs to the conservative public.
(internal links and fonts suppressed)

Apparently, Aaronson's decision to quote Richard Dawkins meant that math must be evil. I'll leave it as an exercise to the reader to note some of the other more glaring errors. However, this was not the end of Conservapedia's attack on establishment math for being just too liberal. Shortly after this declaration, an addition about the Fields Medal went up. The Fields Medal, awarded every four years, is for mathematics roughly equivalent to a Noble Prize(there is no Nobel in math). Conservapedia announced a "Conservapedia exclusive":

[T]his Thursday liberals will likely give the coveted Fields Medal -- math's highest honor -- to an underachieving woman and to a communist-trained mathematician from Vietnam. Is the lamestream media holding back stories about this to create a bigger splash on Thursday?
(internal links and fonts suppressed)

It is not clear what "underachieving woman" Conservapedia is thinking of, but apparently the "communist-trained mathematician" is a reference to Ngo Bao Chau, who made headlines last year for proving the Fundamental Lemma of the Langlands program. Apparently Conservapedia believes that the general media cares so much about mathematics that a failure to speculate on who will win the Fields Medal is a sign of a media conspiracy. Why a "communist-trained" mathematician would be a big deal is not clear given thatabout half of the Fields Medal winners have been either from the USSR or trained in the USSR.

Also, apparently Conservapedia is unhappy that after Terence Tao got the Fields Medal four years ago he then endorsed Barack Obama for President, Finally, we come to the detail that forced me to write this blog entry. To deal with this apparent liberal bias and affirmative action in the Fields Medal, Conservapedia is starting its own award for mathematicians, the "ConservaMath Medal." According to the website this Medal is "the merit-based alternative to the Fields Medal, with winners announced at the same time so that real achievement is recognized." I'll let that speak for itself.

Friday, August 6, 2010

Integer Complexity: An Upper Bound Update

It looks like I may have a final upper bound on the integer complexity problem. Recall we defined f(n) to be the minimum number of 1s needed to represent n as a product or sum of 1s. Thus, f(6)=5 because we can write 6=(1+1)(1+1+1). Harry Altman and I have been working on improving the lower and upper bounds on this function. Prior posts about this problem can be found under the label integer complexity. Harry has a large number of posts on the subject also, but they aren't all tagged so I'll just direct readers to the most recent one.

I'm writing this post to announce that we have a tight upper bound for f(n). Prior to our work, it was known that if n ≥ 2, we have 3log2 n ≥ f(n) ≥ 3log3 n. It is clear that the lower bound is hit infinitely often (whenever n is a power of 3). We (and by we I mean mostly Harry) have worked on understanding what n have close to the lowest possible value, and using this to understand other conjectures about f, such as the conjecture that if n=2^a*3^b then the most efficient representation for n is the obvious one. However, I've been also working on improving the upper bound, and whenever I've thought that I've been done improving the upper bound, I've then realized another way to tweak my proof to reduce the upper bound slightly. However, at this point, I'm confident that cannot happen anymore using the techniques in question, barring substantially new insight. Thus, I'm now announcing the new upper bound. We have for n ≥ 2, f(n) ≤ αlog2 n where α = 70/(log_2 102236160)= 2.630853... Note that this constant is just small enough for us to also state the weaker but prettier result that f(n) ≤ (19/5) log n. Unfortunately, the proof in question is very ugly, involving a large amount of case checking as well as nasty calculation of inequalities. I'm in the process of writing up the last bit. If readers are interested I can email people a draft of the proof when it is fully written.