the ABC conjecture

Both Pour la Science and La Recherche, two French science magazines, had an entry this month on the abc conjecture! However, ABC being a common accronym, it is alas unrelated with my research theme. The abc conjecture is a number theory conjecture that states that if a and b are integers with no common factor and a small number of prime dividers, this does not hold for c=a+b. This is the abc triplet. (More precisely, the conjecture states that the quality of the triplet abc:

is larger than 1+ε for a finite number of triplets abc.) A proof of the conjecture by Shinichi Mochizuki was recently proposed, hence the excitment in the community. In La Recherche, I read that this conjecture is associated with an interesting computing challenge, namely to find the exhaustive collection of triplets with a quality more than a given bound 1+ε.

genetics

Today, I was reading in the science leaflet of Le Monde about a new magnitude in sequencing cancerous tumors (wrong link, I know…). This made me wonder whether the sequence of (hundreds of) mutations leading from a normal cell to a cancerous one could be reconstituted in the way a genealogy is. (This reminds me of another exciting genetic article I read in the Eurostar back from London on Thursday, in the Economist, about the colonization of Madagascar by 30 women from the Malay archipelago: “The island was one of the last places on Earth to be settled, receiving its earliest migrants in the middle of the first millennium AD…“)

As a double coincidence, I was reading La Recherche yesterday in the métro to Dauphine, which central theme this month is about heredity beyond genetics. (Double because this also connected with the meeting in London.) The keyword is epigenetics, namely the activation or inactivation of a gene and the hereditary transmission of this character w/o a genetic mutation. This is quite interesting as it implies the hereditability of some adopted traits, i.e. forces one to reconsider the nature versus nurture debate. (This sentence is another input due to Galton!) It also implies that a much faster rate of species differentiation due to environmental changes (than the purely genetic one) is possible, which may sound promising in the light of the fast climate changes we are currently facing. However, what I do not understand is why the journal included a paper on the consequences of epigenetics on the Darwinian theory of evolution and… intelligent design. Indeed, I do not see why the inclusion of different vectors in the hereditary process would contradict Darwin’s notion of natural selection. Or even why considering a scientific modification or replacement of the current Darwinian theory of evolution would be an issue. Charles Darwin wrote his book in 1859, prior to the start of genetics, and the immense advances made since then led to modifications and adjustments from his original views. Without involving any irrational belief in the process.

2012, Turing year

Buying the special issue of La Recherche on “La révolution des mathématiques”, I discovered that this is the Alan Turing Year in celebration of the 100th anniversary of Turing‘s birth. The math department at the University of Leeds has a webpage on all the events connected with this celebration. From all over the World. (There is even a Turing relay in Cambridge, unfortunately it is not open to the general public… Unless you are attending the Isaac Newton Institute at the time.) Quite fitting a tribute. (Given Turing’s contributions to Bayesian analysis, as depicted e.g. in the theory that would not die, ISBA could have included a special session in the ISBA 2012 meeting in Kyoto. I will certainly dedicate the session I co-organise there on parallel computing to his memory.)

How quickly does randomness appear?

This was the [slightly off-key]  title of the math column in the November issue of La Recherche, in any case intriguing enough for me to buy this general public science magazine on the metro platform and to read it immediately while waiting for an uncertain train, thanks to the nth strike of the year on my train line… But this was the occasion for an exposition of the Metropolis algorithm in a general public journal! The column actually originated from a recently published paper by Persi Diaconis, Gilles Lebeaux, and Laurent Michel,  Geometric analysis for the Metropolis algorithm on Lipschitz domain, in Inventiones Mathematicae [one of the top pure math journals]. The column in La Recherche described the Metropolis algorithm (labelled there a random walk on Markov chains!), alluded to the use of MCMC methods in statistics, told the genesis of the paper [namely the  long-term invitation of Persi Diaconis in Nice a few years ago] and briefly explained the convergence result, namely the convergence of the Metropolis algorithm to the stationary measure at a geometric rate, with an application to the non-overlapping balls problem.

If you take a look at the paper, you will see it is a beautiful piece of mathematics, establishing a spectral gap on the Markov operator associated with the Metropolis algorithm and deducing a uniformly geometric convergence [in total variation] for most regular-and-bounded-support distributions. A far from trivial and fairly general result. La Recherche however fails to mention the whole corpus of MCMC convergence results obtained in the 1990’s and 2000’s, by many authors, incl. Richard Tweedie, Gareth Roberts, Jeff Rosenthal, Eric Moulines, Gersende Fort, Randal Douc, Kerrie Mengersen, and others…

Robin Ryder’s interview

Robin Ryder—with whom I am sharing an office at CREST, and who is currently doing a postdoc on ABC methods—, got interviewed in the March issue of La Recherche. (The interviewer was Philippe Pajot who wrote “Parcours de mathématiciens”, reviewed in a recent post.) The interview is reproduced on Robin’s blog (in French) and gives in a few words the principles of Bayesian linguistics. This two-page interview also includes a few lines of a technical entry to MCMC (called Monte Carlo Markov chains rather than Markov chain Monte Carlo) that focus on the exploration of huge state-spaces associated with trees. Overall, a very good advertising for MCMC methods for the general public through the highly attractive story of the history of languages…

Truly random [again]

“The measurement outputs contain at the 99% confidence level 42 new random bits. This is a much stronger statement than passing or not passing statistical tests, which merely indicate that no obvious non-random patterns are present.” arXiv:0911.3427

As often, I bought La Recherche in the station newsagent for the wrong reason! The cover of the December issue was about “God and Science” and I thought this issue would bring some interesting and deep arguments in connection with my math and realism post. The debate is very short, does not go in any depth. reproduces the Hawking’s quote that started the earlier post, and recycles the same graph about cosmology I used last summer in Vancouver! However, there are alternative interesting entries about probabilistic proof checking in Mathematics and truly random numbers… The first part is on an ACM paper on the PCP theorem by Irit Dinur, but is too terse as is (while the theory behind presumably escapes my abilities!). The second part is about a paper in Nature published by Pironio et al. and arXived as well. It is entitled “Random numbers certified by Bell’s Theorem” and also is one of the laureates of the La Recherche prize this year. I was first annoyed by the French coverage of the paper, mentioning that “a number was random with a probability of 99%” (?!) and that “a sequence of numbers is  perfectly random” (re-?!). The original paper is however stating the same thing, hence stressing the different meaning associated to randomness by those physicists, “the unpredictable character of the outcomes” and “universally-composable security”. The above “probability of randomness” is actually a p-value (associated with the null hypothesis that Bell’s inequality is not violated) that is equal to 0.00077. (So the above quote is somehow paradoxical!) The huge apparatus used to produce those random events is not very efficient: on average, 7 binary random numbers are detected per hour… A far cry from the “truly random” generator produced by Intel!

Ps-As a concidence, Julien Cornebise pointed out to me that there is a supplement in the journal about “Le Savoir du Corps” which is in fact handled by the pharmaceutical company Servier, currently under investigation for its drug Mediator… A very annoying breach of basic journalistic ethics in my opinion!

Truly random?!

Having purchased the September edition of La Recherche because of its (disappointing!) coverage on black matter, I came by a short coverage on an Intel circuit producing “truly random” numbers… I already discussed this issue in an earlier post, namely that there is no reason physical generators are “more” random than congruential pseudo-random generators, but this short paper repeats the same misunderstanding on the role of “random” generators. The paper mentions dangers of pseudo-random generators for cryptography (but this is only when you know the deterministic function and the sequence of seeds used so far), while it misses the essential aspect of valid generators, namely that their distribution is exactly known (e.g., uniform) and, in the case of parallel generations, which seems to be the case for this circuit, that the generators are completely independent. La Recherche mentions that the entropy of the generator is really high, but this is more worrying than reassuring, as the Intel engineers do not have a more elaborate way to prove uniformity than a Monte Carlo experiment…

There is actually a deeper entry found on Technology Review. (Which may have been the source for the paper in the technology tribune of La Recherche.) The article mentions that the generator satisfied all benchmarks of “randomness” maintained by NIST. Those statistical tests sound much more reassuring than the entropy check mentioned by La Recherche, as they essentially reproduce Marsaglia’s DieHard benchmark… I remain rather skeptical about physical devices, as compared with mathematical functions, because of (a) non-reproducibility which is a negative feature despite what the paper says and of (b) instability of the device, which means that proven uniformity at time t does not induce uniformity at time t+1. Nonetheless, if the gains in execution are gigantic, it may be worth the approximation for most applications. But please stop using “true” in conjunction with randomness!!!