Simulating a coin with irrational bias using rational arithmetic

An arXived paper by Luis Mendo adresses the issue of simulating coins with irrational probabilities from a fair coin, somehow connected with one of the latest riddles. Where I realised only irrational coins could be simulated in a fixed and finite number of throws! The setting of the paper is however similar to the one of a Bernoulli factory in that an unlimited number of coins can be generated (but it relies on a  fair coin). And the starting point is a series representation of the irrational ζ as a sum of positive and rational terms. As well as an earlier paper by the Warwick team of Łatuszyński et al. (2011). The solution is somewhat anticlimactic in that the successive draws of the fair coin lead to a sequence of intervals with length divided by 2 at each step. And stopping when a certain condition is met, requiring some knowledge on the tail error of the series. The paper shows further that the number of inputs used by its algorithm has an exponential tail. The examples provided therein are Euler’s constant

where B(j) is the number of binary digits of j, and π/4 which can be written as an alternating series. An idle question that came to me while reading this paper is the influence of the series chosen to represent the irrational ζ as it seems that a faster decrease in the series should lead to fewer terms being used. However, the number of iterations is a geometric random variable with parameter 1/2, therefore the choice of the series curiously does not matter.

Le Monde puzzle [#809]

Another number theory puzzle, completed in the plane to Hamburg:

Integers n are called noble if they can be decomposed as a sum n=a+b+… of distinct integers such that 1/a+1/b+…=1. They are called bourgeois if they are not noble but can be decomposed as a sum n=a+b+… of integers, some of them identical, such that 1/a+1/b+…=1. If neither noble nor bourgeois, they are called villeins. Find all nobles less than 60. And characterise villeins.

Again a case where writing a brute-force R code seems harder than solving the problem on a piece of paper… However, a mix could make the best of both worlds. It is rather straightforward to see that if n is not a villein, then 2n+2 is not a villein (moving from 1/2+1/2=1 to 1/2(1/n)+1/2=1). Similarly for 3n+6 (9=3+3+3), 4n+6 (10=4+4+2), 6n+5 (2+3+6=11). Each new decomposition brings a whole series of non-villeins. Another path is to remark that products keep the property: if a and b are non-villeins, so is ab, a², b², 2(a+b), and actually all products of the form m(m+a-1) for any integer m.  Starting with the most basic solutions (1,4,9,10,11), we can then repeat the application of all those rules until no new non-villein is exposed.

Here is my R code for finding some decompositions with 4 and 5 terms (since there are only one or two decompositions with one (1), two (2+2) and three (2+3+6, 3+3+3): I first define a function checking for a decomposition with no numerical error [(sum(1/deco)==1) does not work!]:

inva=function(deco){
  numerat=0
  for (i in 1:length(deco))
    numerat=numerat+prod(deco[-i])
  return((numerat==prod(deco)))}

then check for 4

reve4=NULL
a=c(2,2,2,2)
while ((a[1]<5)&&(sum(a)<626)){
 while ((sum(1/a[-4])>=1)&&(sum(a)<626))
 a[3:4]=rep(a[3]+1,2)
 a[4]=max(a[3],trunc(1/(1-sum(1/a[-4])))-1)
 while ((sum(1/a)>1)&&(sum(a)<626)) a[4]=a[4]+1
 if (inva(a)) reve4=rbind(reve4,a)
 if ((sum(1/a[-4])+1/a[3]>1)&&(sum(a)<625)){
  a[3:4]=rep(a[3]+1,2)}else{
  b=rep(a[2]+1,3)
  if (a[1]+sum(b)<625){
   a=c(a[1],b)}else{a=rep(a[1]+1,4)
   }}
 }

and 5 term decompositions:

reve5=NULL
a=rep(2,5)
while ((a[1]<5)&&(sum(a)<626)){
 while ((sum(1/a[-5])>=1)&&(sum(a)<626)) a[4:5]=rep(a[4]+1,2)
 a[5]=max(a[4],trunc(1/(1-sum(1/a[-5])))-1)
 while ((sum(1/a)>1)&&(sum(a)<626)) a[5]=a[5]+1
  if (inva(a)) reve5=rbind(a,reve5)
  if ((sum(1/a[-5])+1/a[4]>1)&&(sum(a)<624)){
   a[4:5]=rep(a[4]+1,2)}else{
   b=rep(a[3]+1,3)
   if (sum(a[1:2])+sum(b)<625){a=c(a[1:2],b)}else{
    b=rep(a[2]+1,4)
    if (a[1]+sum(b)<625){a=c(a[1],b)}else{
       a=rep(a[1]+1,5)
   }}}
}

From there, we have a basis on which we can fill a 25×25 table of further non-villeins, applying the above rules:

nob=rep(0,25^2)
nob[c(1,4,9,10,11,16,24)]=1
nob[apply(reve4,1,sum)]=1
nob[apply(reve5,1,sum)]=1
ref=1
newref=sum(nob)
while (newref>ref){
 for (i in (1:25^2)[nob==1]){
 if (i<26) nob[i^2]=1
 if (2*i+2<625) nob[2*i+2]=1
 if (2*i+9<626) nob[2*i+9]=1
 if (3*i+6<626) nob[3*i+6]=1
 if (4*i+6<626) nob[4*i+6]=1
 if (6*i+5<626) nob[6*i+5]=1
 for (m in 2:25)
   if (m*(m+i-1)<626) nob[m*(m+i-1)]=1}
 ref=newref;newref=sum(nob)
 image(1:25,1:25,matrix(nob,25))}

This produces two false villeins, namely 47 and 103, since all numbers larger than 24 are non-villeins: Since both 47 and 103 are prime numbers, using other product rules would not change anything to the result. An extra R code looking at all possible decompositions of those numbers into sums would show them as false villeins. Or moving to 6 term decompositions since 47 = 3+4+8+8+12+12. Here is a small random search:

a=c(3,rep(2,23))
N=47
while (!inva(a)){
  b=sample(2:N,1)
  a0=c(b,N-sum(b))
  while (sum(1/a0)<1){
    b=sample(2:(N-sum(a0[-length(a0)])),1)
    a0=c(a0[-length(a0)],b)
    a0=c(a0,N-sum(a0))}
  a=a0}

which returns 47 =4+6+20+6+5. And 103=40+35+8+14+2+4

Interesting features of this problem are that (a) it appears fairly frequently in the mathematical games literature, like the Olympiads, see e.g. this resolution incl. the proof about 24 as the upper limit to the existence of villeins, (b) the name of those integers varies from case to case, like good integers, and (c) the denomination of noble integers is used in mathematics for “irrational numbers having a continued fraction representation that becomes an infinite sequence of 1s at some point“. (There was also a very similar question on stack exchange a few weeks ago but I cannot trace it…)

irrationals [guest post/book review]

When I received The irrationals: A story of the numbers you can’t count on by Julian Havil for reviewing for CHANCE, Pierre Alquier happened to be in my office at CREST and I proposed him to write the review, which he did within a few weeks (and thus prior to the book publication!). Here is his nice and comprehensive review:

This book is intended to be a short history of irrational numbers, since the discovery of the first irrational, √3, by the ancient Greeks until the first rigorous definitions of real numbers by Cantor and Dedekind. In addition to the historical aspect, the author does not hesitate to go into mathematical details and to provide some of the most remarkable proofs in the history of irrationals.

The book is essentially organized around the emergence of key mathematical concepts, rather than based on a strict chronological order. Thanks to the historical perspective, we learn a lot about some famous mathematicians like Pythagoras, Euclid, Gauss or Euler. The book is also full of amazing anecdotes. For example, it reveals the way to find the tomb of Roger Apéry, who proved that ζ(3) is irrational, in the labyrinth of Père Lachaise cemetery in Paris. All of this make the reading of this book a real enjoyment. The appendix contains more involved mathematical developments. The only weak point that I would like to point out is the absence of bibliography that would allow the interested reader to go further into the history of number theory, or into number theory itself.

The book can roughly be divided into 4 parts: (1) the discovery of irrationals and the first calculus with square roots, in chapters 1 and 2, (2) the proof that some remarkable numbers like π and e are irrationals in Chapters 3, 4 and 5, (3) some classification of the irrationals based on approximations by rationals, and the discovery of transcendental numbers (Chapters 6, 7 and 8) and, finally, (4) the proper definition of the real numbers by several mathematicians, including Dedekind (9 and 10).

Chapters 1 and 2 deal with the antique world: the proof of the irrationality of √3, the influence of the Pythagoras and Euclid, and the first algebraic manipulations of the irrationals by the Arabs, the Hindus, and European mathematicians like Fibonacci in the early Renaissance. A lot of information is provided about several Greeks mathematicians and philosophers and the reader might sometimes get lost. However, both chapters contain valuable historical information, as well as some nice proofs based on geometry.

Chapters 3, 4 and 5 give the proof of the irrationality of some remarkable numbers. The method of continued fractions is explained in Chapter 3, leading to the irrationality of e. A simpler proof due to Fourier is given in Chapter 4. The proof of the irrationality of π² (and thus of π) by Hermite is also given in details in that Chapter. Chapter 5 takes the reader to the seventies: it provides the striking proof of that ζ(3) is irrational by Roger Apéry. Surprisingly enough, unlike most recent mathematical proofs, this one only requires a knowledge of elementary mathematics to be understood.

Chapter 6 is one of the most remarkable parts of the book, because of the number of results given there, and the elegance of the proofs. It focuses on approximations of irrationals by rationals. It is obvious that, given any number x and an integer q, one can find another integer p with |x-p/q|<1/q. However, is it possible to find infinitely many p and q such that |x-p/q|<1/q^1+ε for a given ε>0? One of the striking facts proved in this chapter is that for ε=1, the answer is yes if, and only if, x is irrational. In Chapter 7, a classification of irrationals based on various values for ε is described. The idea is to define a number x to be “more irrational” if the property still holds for larger values of ε. This leads to the introduction of a new family of irrationals: the transcendentals, studied in Chapters 7 and 8. Actually, if the property holds for ε>1, then x is a transcendental number. It’s been conjectured for a long time that π and e are transcendentals. However, the first number L to be proved to be transcendental was specially designed by Liouville to fit the results of Chapter 6. This construction is explained in Chapter 7: L is build such that, for any ε>0, there are infinitely many p and q such that |L-p/q|<1/q^1+ε, and this proves that L is transcendental.

Finally, Chapter 9, 10 and 11 deal with more recent questions such as the problem of randomness in the decimal expansion of irrational numbers, and the first rigorous definitions of the set R of real numbers by Kossak, Cantor, Heine and Dedekind. Dedekind’s definition of a real number as a cut of the set of rationals became the classical one, but it is known that the other constructions are equivalent. The chapter about randomness is a bit short and unfortunately the recent approaches to define random sequences by Chaitin, Solovay and Martin-Löf are not mentioned. This part ends with some conclusion on the role of irrationals in modern mathematics.

This book contains a lot of fun for whoever likes mathematics. As it goes into details, I would recommend The irrationals: A story of the numbers you can’t count on particularly to students or to mathematicians non specialized in number theory, who would like to learn about its history – or just to enjoy some remarkably elegant proofs. From that perspective, some chapters like Chapters 6 and 10 are particularly successful.

As a side note, here is a terrific biography of Roger Apéry by his son, who is also a mathematician. When I was a student in Caen, Apéry was famous, both for his result and for having once forgotten his son (the same one?) on his motocycle in the parking lot of the university when supposedly driving him to school. (I [even more personally] find most interesting the description of the competition between the young ENS students, Roger Apéry and Jacqueline Lelong-Ferrand, for the first position at the agrégation final exam, since I had the privilege of having Madame Lelong-Ferrand as my professor of differential geometry in Paris 6, circa 1983…)