Baron Münchhausen and the Riemann Hypothesis

by Tanya Khovanova, Konstantin Knop, Alexey Radul and Peter Sarnak

Let n coins weighing 1, 2, … n be given. Baron Münchhausen knows which coin weighs how much, but his audience does not. Define a(n) to be the minimum number of weighings the Baron must conduct on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins.

In the paper Baron Münchhausen’s Sequence, three of us completely described the Baron’s sequence. In particular, we proved that a(n) ≤ 2. Here we would like to outline another proof idea, which is interesting in part because it touches the Riemann hypothesis.We denote the total weight of coins in some set A as |A|.

Lemma. Numbers n that can be represented as Ti + Tj + Tk = 3n, where i ≤ j < k, such that there is a subset A of coins from j + 1 to k such that n = Tj + |A|, can be done in two weighings.

Proof. Suppose Ti + Tj + Tk = 3n and there is a subset A of coins from j + 1 to k such that n = Tj + |A|. We propose the two weighings

[1…j] + A = n

and

[1…i] + B = n + A,

where B is the complement of A in {j + 1, j + 2, … , k}.

If we sum up twice the first weighing with the second weighing we get

3[1…i] + 2[(i + 1)…j] + 2A + B = 3n + A.

In other words, three times the weight of the coins that were on the left side in both weighings, plus twice the weight of the coins that were on the left side in only the first weighing, plus the weight of the coins that were moved from the left cup to the right cup plus the weight of the coins on the left cup in only the second weighing equals three times the weight of the coin on the right cup in both weighings. Hence three times the weight of the coin on the right cup in both weighings can’t be less than the weight of the k other coins that participated plus the weight of the j coins that were on the left cup in the first weighing and weren’t moved to the right cup, plus the weight of the i coins that were one the left cup in both the first and the second weighing. But because Ti + Tj + Tk = 3n, then 3n is the smallest possible weight of any set of i plus j plus k coins, the coin on the right cup in both weighings has to be the n-coin.

We checked that any number up to 600,000 except 20 can be represented so as to satisfy the Lemma. To show how to solve 20 coins in two weighings is easy, and, as usual, is left as an exercise for the reader. Next, we want to look at the following lemma.

Lemma. Given a set of consecutive numbers {(j + 1), … , k}, if k > 2j + 2, then it is possible to find a subset in the set that sums up to any number in the range from j + 1 to (j + k + 1)(k – j)/2 – j – 1.

We won’t prove the lemma, but it means that if k is about twice larger than j, then we have a lot of flexibility for building our set A in the weighing above. For moderately large n (where 600000 >> “moderately large”), it is not hard to prove that this flexibility is sufficient.

Now the question becomes: can we find such a decomposition into triangular numbers? It is enough to find a representation Ti + Tj + Tk = 3n, where Tk is at least 81% of 3n.

We know that decompositions into triangular numbers are associated with decompositions into squares. Namely, if Ti + Tj + Tk = 3n, then (2i + 1)2 + (2j + 1)2 + (2k + 1)2 = 24n + 3. If the largest square is at least 81% of 24n + 3, then the largest triangular number in the decomposition of 3n is at least 81%.

There is a theorem (W. Duke, Hyperbolic distribution problems and half-integral weight Maass forms, in Inventiones Math 92 (1988) p.73-90) that states that in the limit the decompositions of numbers into three squares are equidistributed. That is, if we take some region on the unit sphere x2 + y2 + z2 = 1 (for example, the region |z| > 0.8) and view decompositions of 24n + 3 into squares as points on the sphere x2 + y2 + z2 = 24n + 3, then, as n grows, decompositions whose projections fall into our chosen region are guaranteed to appear.

This theorem is great, because it tells us that for large enough n we will always be able to find a decomposition of 24n + 3 into triangle numbers where one of the triangle numbers will be much bigger than the others, and it will be possible to prove the weight of the n coin in two weighings. Unfortunately, this summary, as stated, does not tell us how large that n needs to be. So we need some exact estimates.

The number of decompositions of m into sums of three squares is about the square root of m. More precisely, it is possible to compute a number N, such that for any number m > N, with at most one exception, the number of decompositions is at least Cm1/2−1/30, where C is a known constant.

The more specific statement of Duke’s theorem is that if the number of solutions to the quadratic x2 + y2 + z2 = 24n + 3 is large, for a computable value of “large”, then the solutions are equidistributed. More precisely, let us denote 3n by m and fix an area Ω on the unit sphere. Then the number of solutions (x, y, z) such that the unit vector (x, y, z)/|(x, y, z)| belongs to Ω is

1/(4π) Ωh(8m+3) + E(m),

where h(8m+3) is the total number of solutions of x2 + y2 + z2 = 24n + 3, and E(m) is an error term, which starting from some number satisfies the inequality: E(m) ≤ 1000m1/2-1/7.

That’s pretty good, because combining these two lets us, at least in principle, actually calculate an N such that for all n > N except maybe one a(n) = 2. After that we hoped to write a program to exhaustively search smaller numbers by computer.

This situation is still somewhat annoying, because that possible exception must then be propagated into the proof, and if we are not careful, possibly into the final theorem. (“No matter how many coins the Baron has, he can prove the weight of one in at most two weighings, except maybe one number of coins, and we don’t know which…”) This is where the Riemann Hypothesis comes in. If the Riemann Hypothesis is true, then that exception isn’t there, and all is sunlight and flowers.

The beauty of the Baron’s puzzle is such that we actually do not need the Riemann hypothesis. As we can use unbalanced weighings, it is enough to find a good decomposition for one out of the four numbers 3n, 3n-1, 3n-2, or 3n-3.

Instead of finding all these exact estimates we found a different elementary proof of our theorem. But we are excited that methods that are used in very advanced number theory can be used to solve a simple math problem that can be described to middle school children.

It would be great if someone decided to finish this proof.

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

8 Comments

  1. Xamuel:

    Very cool sequence.

    I found a minor inconsistency in the paper. In section 2, you list the first few terms as 0,1,1,1,2,1,1,1. Later on, at the bottom of section 4.2, you list the “positions of 1’s” as 1,2,3,4,6,7,8,10,11,… It seems there’s some ambiguity: when the baron has 1 coin, does he need one weighing or zero weighings? You apparently chose the latter answer in section 2 and the former in 4.2.

    I guess you “officially” went with the latter version because that’s how you submitted it to the Online Encyclopedia of Integer Sequences…

  2. Tanya Khovanova:

    Xamuel,

    Thank you for finding this. We will look into it.

  3. andrews:

    SOLVED THE VIII HILBERT PROBLEM- FINALLY A PROOF OF THE RIEMANN HYPOTHESIS.
    Finally a proof of the Riemann Hypothesis by the Italian mathematician Onofrio Gallo (b. may 13, 1946 in Cervinara, Caudina Valley- Italy) Of the 23 problems of Hilbert (Paris, 1900), the Riemann Hypothesis (or RH) is the eighth and “was” one of the most difficult to resolve.No coincidence that I wrote “was” because there are now well two proofs of (RH), both by the mathematician Onofrio Gallo (b. 1946 in Cervinara, Caudina Valley – Italy): the first (“indirect “or RH THEOREM OF GALLO and the second (“direct” or RH-MIRABILIS THEOREM OF GALLO Both demonstrations were deposited at the Norwegian Academy of Sciences and Letters . Therefore, from April 14, 2010, all books on RH, given the double Riemann hypothesis demonstration by the Italian mathematician Onofrio Gallo, must be updated. Both demonstrations obtained by Onofrio Gallo are based on its original mathematical discoveries The Gallo’s “indirect” Gallo proof of the RH dates back to 2004 is based on the function “fi” of Gallo, on the Gallo’s Principle of Unidentical , on the Second Principle of General Knowledge (in this case the principle of identity of polynomials), coded for the first time by the same Gallo and on the Mirabilis Theorem of Gallo by which the Italian mathematician December 27, 1993 (Rome) had obtained the first demonstration of such “direct” worldwide in just six pages, by a single author of the equally famous Fermat’s Last Theorem (FLT), where failed even to themselves A.J.Wiles and R.Taylor, authors of a “indirect” proof of the FLT, published in May 1995. The second proof of the RH-MIRABILIS THEOREM by Onofrio Gallo consists of just seven lines, so that its author said he had succeeded in coping with the ‘mystery of mysteries” (of the RH or Riemann hypothesis) using the “simplest of the simplest” of the theorems of mathematics. The elegant and surrounded by lightning demonstration of the RH-MIRABILIS THEOREM of Gallo gives ample reasons to those who have long predicted the likely demonstration dell’RH not part of a team of mathematicians, but most likely by a single mathematician who made use of new ideas, new theories and new theorems and that places itself as a true outsider against common lines of research directed to solving the ‘mystery of mysteries’. The RH-THEOREM mirabilis Gallo uses a well-known symmetry properties of Riemann nontrivial zeros of the Riemann zeta function (by some called “the monster”). Be right for the Riemann “monster”, Onofrio Gallo built the Gallo complex function of symmetry from a general solution or non-trivial zero of the “monster”, showing that any non-trivial complex zero z = x + iy (x, y “, real non-zero) of the Riemann zeta function (“the monster”) must be of the type z = 1 / 2 + iy, ie that for each such z, the real part of z must lie on the so-called Riemann “critical line” x = 1 / 2. The “impossible” undertaking was therefore made by the mathematician cervinarese by applying a “double symmetry. The first already discovered by Riemann in 1859 (if ζ (s) = 0, ζ (1-s) = 0, with s-s and a complex non-trivial zeros of Riemann). The second finding himself Onofrio Gallo in 1993 (Mirabilis Theorem Gallo, Dec 27, 1993, Rome). Personally I have never seen a mathematical revolution of this magnitude and I will help to spread the news of the news! Andrews, mathematician.

  4. sunkhirous:

    I’ve solved it, ck utube under (Euler zeta) my fist page of six pages.

  5. Dr.Kathrine Martinez-Martignoni:

    Can anybody say something new concerning this presumed demonsrtation of the Riemann hypothesis made by the italian mathematician Onofrio Gallo?
    I am not a mathemacian but I haven`t read nothing al all on this…but if this thing is real it is really an historic achievement not only for mathematics but also for all the sciences in general (In fact,I believe that the Riemann hypothesis (when it will be definitively confirmed) will be very important in physics,too!!!).
    So,please,if anybody knows anything interesting concerning this possible demostration of the Riemann hypothesis,let me know something.
    Best wishes from Switzerland,
    Dr.Kathrine M.

  6. paul:

    The proof of the Riemann Hypothesis now RH-Mirabilis Theorem of Gallo (special case of Z-Mirabilis Theorem of Gallo) is deposited in Oslo at one of the world’s most prestigious academies in the field of mathematics You can visit topdocumentaryfilms.com / Fermats-last-theorem / and see what you think of the results obtained by the Italian mathematician Onofrio Gallo. Paul

  7. andrews:

    THE GALLO’s CHARACTERISTIC THEOREM ON THE RIEMANN’S NON TRIVIAL ZEROS
    This theorem solves in a way simple and elegant the following original problem of Gallo: “It ‘s possible to represent complex non-trivial zeros of the Riemann zeta function on the real axis in terms of symmetry and how?” This problem was solved by the Italian mathematician Onofrio Gallo (born May 13, 1946 at Cervinara, Valle Caudina) immediately after the proof of the Riemann Hypothesis (Gallo’s RH-Mirabilis Theorem , released on the Web April 14, 2010.
    By virtue of the Gallo’s RH-Mirabilis Theorem every non-trivial zero s = x + yi of the Riemann‘s zeta function is such that Re (z) = x = 1 / 2 = 0.5, for which both s = 0.5 + yi and its conjugated 1-s = 0.5-yi are nontrivial solutions of the Riemann’s zeta function. These zeros s and 1-s are infinite and are located symmetrically in relation to the “center of symmetry of Riemann” R0 = (1 / 2, 0) on the so-called critical line of the Riemann x = 1 /2. The proposed problem will be solved as soon as they were identified: a) a center of symmetry G0 = (xG, 0) on the real axis of the abscissa (y = 0), with appropriate xG ; b) a function g of symmetry of Gallo which involving biunivocally to any pair (s, (1 – s)) of non-trivial zeros of the Riemann’s zeta function the pair of real values of Gallo (g1, g2) , with g1 = g (s) and g2 = g (1-s) symmetrical to the real center of symmetry G0 of Gallo. This problem is solvable if and only if, the Hermitian matrix G of Gallo (which is an element of the overall group of grade 2 or GL2) is introduced consisting of the elements a11 = a22 = 1, a12 = 0.5 + s = yi , a22 = 1-s = 0.5-yi. Therefore, the Gallo characteristic polynomial associated with the G is given by the complex algebraic second-degree polynomial G (x, s) = x ^ 2-2x + (s ^ 2-s +1), 2 being the value of the trace of G. The solutions of the Gallo characteristic polynomial are the real zeros of Gallo g1= 1+ H and g2 = 1 – H with H = (√ (1 +4 yì2)) / 2 . It follows that, if we establish the two biunivocal correspondences: c1 : s complex number to g1 real number and c2 : s complex number to g2 real number, the problem is completely solved. In this way, in fact, the Gallo’s Hermitian operator G , by the roto-translation (π / 2, +1 / 2), means that the critical line of the Riemann x = 1 / 2 and the origin R0 =(1 / 2,0) of the symmetry of the Riemann’s non-trivial zeros and s 1-s they turn into, respectively, the real axis of the abscissa y = 0 (or the real line of Gallo) and the origin G0 = (1, 0) of the symmetry of Gallo real zeros g1 and g2.
    And in fact c1 is such that to the nontrivial zeros of Riemann s = 0.5 + yi associates the Gallo’s real zeros g1 = 1 + H which are to the right of G0, while to non-trivial zeros of Riemann’s 1-s= 0.5 – yi the c2 associates the Gallo’s real zeros g2 = 1-H which are at the left of G0. For example to value s1=0.5 +i 14.134725… (first nontrivial zero of Riemann) the c1 associates biunivocally the first Gallo’s real zero G1 = 15. 143 565 7 …, while the to symmetric of s, i.e. 1-s = 0.5- i 14.134725 …, the c2 associates biunivocally the symmetric to G0 of the first Gallo’s real zero, ie G’1 = -13.143 565 7 … and, therefore, in general is g1=s +1 and g2 = – (s-1).
    In light of the above, there is thus the following: THE CHARACTERISTIC THEOREM OF GALLO (on non-trivial zeros of Riemann)
    “The non-trivial complex numbers s = x + yi and 1-s = x-yi are non-trivial zeros of the Riemann zeta function if, and only if, their corresponding on the Gallo real line are, respectively, g1 = 1+H and g2 = 1-H with H = (√ (1 +4 y^2)) / 2, i.e. the zeros of the Gallo characteristic polynomial G (x, s) = x ^ 2-2x + (s ^ 2-s +1), associated with the Gallo Hermitian matrix G.”
    (The proof of this theorem, as we have shown, it is immediate from Re (s) = Re (1-s) = 1 / 2, which is true from the Gallo RH-Mirabilis Theorem ). Andrews courtesy of the author.

  8. andrews:

    ERROR REPORTING ON THE GALLO’s CHARACTERISTIC THEOREM ON THE RIEMANN’S NON TRIVIAL ZEROS ERRATA “in general is g1=s +1 and g2 = – (s-1).” CORRIGE: “… and, therefore, in general it appears that the integer part of g1 and g2 are given, respectively, from the greatest integer contained in Im (s) +1 and Im (s-1) +1.” I apologize for the error. Andrews

Leave a comment