November 2012 - mathfun@mailman.xmission.com

[math-fun] Factorizations of 1 + n + n^2
by Allan Wechsler 18 Nov '12

18 Nov '12

At least for the first few positive n, the factorization of 1 + n + n^2 contains a prime larger than n. The first counterexample is at n=16; here 1 + n + n^2 = 273 = 3*7*13. I've only explored the question by hand, but so far I've found no counterexamples for the special case when n is prime. Can somebody with a few free minutes find one?

4 4

Re: [math-fun] when and why was it agreed that > 0.999...=1?
by Phil Carmody 18 Nov '12

18 Nov '12

From: John Galt <acwacw(a)gmail.com> > GAH! I committed a similar mistake -- they are easy to make. And I > misread Senator Carmody's critique, which I now believe to be wrong. On > top of that, I'm misattributing everything in sight. Please be kind and > ignore me. Apparently waves of chaos can occasionally propagate in such a fashion. I apologise for my part and shall hunt for a new pair of eyes on eBay; alas I fear what I may end up buying... Phil

2 1

[math-fun] elliptic λ*
by Bill Gosper 18 Nov '12

18 Nov '12

What, exactly, is an "elliptic integral singular value"? Weisstein (http://mathworld.wolfram.com/EllipticIntegralSingularValue.html) when converted from modulus- to parameterspeak, says it's a value m=ModularLambda[√r] such that EllipticK[1-m]/EllipticK[m] ==√r, where r seems to be restricted to a positive rational. E.g., "the seventh singular value": ModularLambda[I Sqrt[7]] == 1/16 (8 - 3 Sqrt[7]) EllipticK[1/16 (8 - 3 Sqrt[7])] == Gamma[1/7] Gamma[2/7] Gamma[4/7]/(4 7^(1/4) π) EllipticK[1/2 + 3 Sqrt[7]/16]/ EllipticK[1/16 (8 - 3 Sqrt[7])] == Sqrt[7] Why rational r? Why √ ? Why positive? E.g., ModularLambda[2 I E^(-I π/6)] == -7 + 4 Sqrt[3] EllipticK[-7 + 4 Sqrt[3]] == 3^(1/4) Sqrt[2 + Sqrt[3]] Gamma[1/3]^3/(8 2^(1/3) π) EllipticK[8 - 4 Sqrt[3]]/EllipticK[-7 + 4 Sqrt[3]] == 2 E^(-I π/6) But things can get weird: ModularLambda[4 (-1)^(1/3)] == (-2 + Sqrt[2] - Sqrt[3] + Sqrt[6])^4 This is the same m as ModularLambda[2 I Sqrt[3]] == (-2 + Sqrt[2] - Sqrt[3] + Sqrt[6])^4 i.e., the "twelfth singular value" instead of period ratio 4 E^(-I π/6). EllipticK[(-2 + Sqrt[2] - Sqrt[3] + Sqrt[6])^4] == 3^(1/4) (1 + 2 Sqrt[2] - Sqrt[3]) (10 - 6 Sqrt[2] - 5 Sqrt[3] + 4 Sqrt[6]) Gamma[1/3]^3/ (16 2^(5/6) π) (Not quite the same as yesterday's.) EllipticK[1 - (-2 + Sqrt[2] - Sqrt[3] + Sqrt[6])^4]/ EllipticK[(-2 + Sqrt[2] - Sqrt[3] + Sqrt[6])^4] == 2 Sqrt[3] Even weirder: ModularLambda[I 3 E^(-I π/6)] == 1/2 (1 - Sqrt[1 - 4 (16001 - 6350 2^(1/3) (1 - I Sqrt[3]) - 5040 2^(2/3) (1 + I Sqrt[3]))]) EllipticK[1/2 (1 - Sqrt[ 1 - 4 (16001 - 6350 2^(1/3) (1 - I Sqrt[3]) - 5040 2^(2/3) (1 + I Sqrt[3]))])] == ((-1)^(1/12) 3^(1/4) Sqrt[5/9 + (2 2^(1/3))/9 - (2 I 2^(1/3))/(3 Sqrt[3])] Gamma[1/3]^3)/(4 2^(1/3) π) EllipticK[ 1/2 + 1/2 Sqrt[1 - 4 (16001 - 6350 2^(1/3) (1 - I Sqrt[3]) - 5040 2^(2/3) (1 + I Sqrt[3]))]]/ EllipticK[ 1/2 - 1/2 Sqrt[1 - 4 (16001 - 6350 2^(1/3) (1 - I Sqrt[3]) - 5040 2^(2/3) (1 + I Sqrt[3]))]] == Sqrt[7] E^(I ArcCot[3 Sqrt[3]]) instead of 3 E^(-I π/6) ! And sadly, ModularLambda[I GoldenRatio] seems transcendental. --rwg Elsewhere I said *rwg>I'm having no luck finding a table of special values of EllipticE. This may be due to a simpler formula than above to produce them from EllipticK. It looks like they're something K + something/K.* Indeed, see (40) and (41) of http://mathworld.wolfram.com/EllipticIntegralSingularValue.html . This requires the elliptic α function. But closed forms require finding 𝜗' for particular q, which is equivalent to the problem I was attacking with "logderiveta".

1 1

[math-fun] The Halting Problem Seuss'ified
by Henry Baker 18 Nov '12

18 Nov '12

FYI -- I wonder how many math proofs down through the centuries have been put into verse? http://m-phi.blogspot.nl/2012/03/geoff-pullum-seusses-out-halting.html Wednesday, 21 March 2012 Pullum S(e)usses Out the Halting Problem Since 2012 is the Turing Centenary Year, and since incompleteness/diagonalization has been the dominant theme on M-Phi of late, I thought it would be both fun and appropriate to repost Geoff Pullum's delightful Seussification of Turing's proof of the undecidabilty of the halting problem. (H/t to John Baez over on Google+.) Scooping the Loop Snooper No program can say what another will do. Now, I wonÂt just assert that, IÂll prove it to you: I will prove that although you might work til you drop, You canÂt predict whether a program will stop. Imagine we have a procedure called P That will snoop in the source code of programs to see There arenÂt infinite loops that go round and around; And P prints the word ÂFine!Â if no looping is found. You feed in your code, and the input it needs, And then P takes them both and it studies and reads And computes whether things will all end as they should (As opposed to going loopy the way that they could). Well, the truth is that P cannot possibly be, Because if you wrote it and gave it to me, I could use it to set up a logical bind That would shatter your reason and scramble your mind. HereÂs the trick I would use Â and itÂs simple to do. IÂd define a procedure Â weÂll name the thing Q Â That would take any program and call P (of course!) To tell if it looped, by reading the source; And if so, Q would simply print ÂLoop!Â and then stop; But if no, Q would go right back to the top, And start off again, looping endlessly back, Til the universe dies and is frozen and black. And this program called Q wouldnÂt stay on the shelf; I would run it, and (fiendishly) feed it itself. What behaviour results when I do this with Q? When it reads its own source, just what will it do? If P warns of loops, Q will print ÂLoop!Â and quit; Yet P is supposed to speak truly of it. So if QÂs going to quit, then P should say, ÂFine!Â Â Which will make Q go back to its very first line! No matter what P would have done, Q will scoop it: Q uses PÂs output to make P look stupid. If P gets things right then it lies in its tooth; And if it speaks falsely, itÂs telling the truth! IÂve created a paradox, neat as can be Â And simply by using your putative P. When you assumed P you stepped into a snare; Your assumptions have led you right into my lair. So, how to escape from this logical mess? I donÂt have to tell you; IÂm sure you can guess. By reductio, there cannot possibly be A procedure that acts like the mythical P. You can never discover mechanical means For predicting the acts of computing machines. ItÂs something that cannot be done. So we users Must find our own bugs; our computers are losers! _______ Pullum, Geoffrey K. (2000) ÂScooping the loop snooper: An elementary proof of the undecidability of the halting problem.Â Mathematics Magazine 73.4 (October 2000), 319-320.

3 3

[math-fun] undecidability -- shortest-ness versus halting-ness
by Warren Smith 18 Nov '12

18 Nov '12

[I apologize in advance for the fact this post does not rhyme.] Henry Cejtin told me one time that the halting problem was not as cool a foundation for undecidability as this: OPTIMAL-KOLMOGOROV-COMPLEXITY DECISION PROBLEM: Given a program P, decide whether P is shortest-possible. PROOF (BY G.CHAITIN) THIS IS UNDECIDABLE: Assume for a contradiction, that some "is it shortest possible?" decidion-procedure D existed. Modify D (by adding a constant number C of lines of code to it) so that the resulting program D' enumerates all possible computer programs X, until it finds one which is longer than length(D)+C, and which is shortest possible; then D' runs X. Note that D' is now a program shorter than, but equivalent to, X. This contradicts the fact X was shortest possible. Q.E.D.

1 0

Re: [math-fun] The Halting Problem Seuss'ified
by Henry Baker 18 Nov '12

18 Nov '12

Fabulous! This sounds like a perfect song for the MIT Logarhythms All-Male A Cappella Group ! http://mitlogs.com/ At 08:53 AM 11/18/2012, Andy Latto wrote: >On Sun, Nov 18, 2012 at 9:22 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: >> FYI -- I wonder how many math proofs down through the centuries have been put into verse? > >I think it will be hard to beat this one: >(http://math.uchicago.edu/~wald/lit/pi_proof.txt) > >Kevin Wald: The Pi Proof of Penzance. > >A proof of the irrationality of pi, to a well-known tune. >(First presented to my calculus class a short while ago, >in a slightly different version.) > >Note: the actual mathematical content of this work is based >on a proof I saw posted to sci.math a while back. > >---------------------------------------------------------------- >That pi must be irrational, I claim, is demonstratable: >Assume that with a quotient of whole numbers it's equatable >-- Say, m o'er n. Define a_k, by fiat dictatorial, >For every natural k to be one over k factorial >Times integral from naught to pi of (n times (t)(pi - t)) >To power k, times sine (or for you Latin scholars, _sinus_) t, >dt. These a's are *positive*, with *finite sum* (indeed, it e- >Quals integral exp(n times (t)(pi - t)) sin t dt). > >Chorus: It's integral exp(n times (t)(pi - t)) sin t dt! > It's integral exp(n times (t)(pi - t)) sin t dt! > It's integral exp(n times (t)(pi - t)) sin t dt, dt! > >But integrate by parts -- each a's the sum of the preceding two >Times integers, a_naught is 2, a_1's 4n, thus leading to >(since *all* must then be integers) a contradiction statable, >And thus that pi's irrational, you see, is demonstratable! > >Chorus: Since *all the a's are integers*, a contradiction's statable, > And thus that pi's irrational, we see, is demonstratable! > >> http://m-phi.blogspot.nl/2012/03/geoff-pullum-seusses-out-halting.html >> >> Wednesday, 21 March 2012 >> >> Pullum S(e)usses Out the Halting Problem >> >> Since 2012 is the Turing Centenary Year, and since incompleteness/diagonalization has been the dominant theme on M-Phi of late, I thought it would be both fun and appropriate to repost Geoff Pullum's delightful Seussification of Turing's proof of the undecidabilty of the halting problem. (H/t to John Baez over on Google+.) >> >> Scooping the Loop Snooper >> >> No program can say what another will do. >> Now, I wonÂt just assert that, IÂll prove it to you: >> I will prove that although you might work til you drop, >> You canÂt predict whether a program will stop. >> >> Imagine we have a procedure called P >> That will snoop in the source code of programs to see >> There arenÂt infinite loops that go round and around; >> And P prints the word ÂFine!Â if no looping is found. >> >> You feed in your code, and the input it needs, >> And then P takes them both and it studies and reads >> And computes whether things will all end as they should >> (As opposed to going loopy the way that they could). >> >> Well, the truth is that P cannot possibly be, >> Because if you wrote it and gave it to me, >> I could use it to set up a logical bind >> That would shatter your reason and scramble your mind. >> >> HereÂs the trick I would use Â and itÂs simple to do. >> IÂd define a procedure Â weÂll name the thing Q Â >> That would take any program and call P (of course!) >> To tell if it looped, by reading the source; >> >> And if so, Q would simply print ÂLoop!Â and then stop; >> But if no, Q would go right back to the top, >> And start off again, looping endlessly back, >> Til the universe dies and is frozen and black. >> >> And this program called Q wouldnÂt stay on the shelf; >> I would run it, and (fiendishly) feed it itself. >> What behaviour results when I do this with Q? >> When it reads its own source, just what will it do? >> >> If P warns of loops, Q will print ÂLoop!Â and quit; >> Yet P is supposed to speak truly of it. >> So if QÂs going to quit, then P should say, ÂFine!Â Â >> Which will make Q go back to its very first line! >> >> No matter what P would have done, Q will scoop it: >> Q uses PÂs output to make P look stupid. >> If P gets things right then it lies in its tooth; >> And if it speaks falsely, itÂs telling the truth! >> >> IÂve created a paradox, neat as can be Â >> And simply by using your putative P. >> When you assumed P you stepped into a snare; >> Your assumptions have led you right into my lair. >> >> So, how to escape from this logical mess? >> I donÂt have to tell you; IÂm sure you can guess. >> By reductio, there cannot possibly be >> A procedure that acts like the mythical P. >> >> You can never discover mechanical means >> For predicting the acts of computing machines. >> ItÂs something that cannot be done. So we users >> Must find our own bugs; our computers are losers! >> _______ >> >> Pullum, Geoffrey K. (2000) ÂScooping the loop snooper: An elementary proof of the undecidability of the halting problem.Â Mathematics Magazine 73.4 (October 2000), 319-320. >-- > Andy.Latto(a)pobox.com

1 0

[math-fun] poisoned wine bottles: perfect-union codes
by Warren Smith 18 Nov '12

18 Nov '12

> EXPONENTIAL GROWTH THEOREM: > M(n) > 2^(0.3333 + 0.07558*n). Veit Elser: This is interesting (still have to check the details). Any idea how to find the smallest n for which M(n)>n ? --well, to do that, you would want to find theorems giving upper bounds on M(n). If you had good enough lower & upper bounds you might solve this smallest-n problem, but even if not good enough for that, then its still a good thing. SIDE REMARKS: 1. my lower bound, since it was quite simple, can probably be improved. (I'm sure it is correct with some constants, although I could have screwed up the precise constants.) 2. the name "perfect union codes" sucks because the word "perfect" seems uncalled for. Just "union codes" would be a better name, albeit maybe not best. OK, so now let me try to produce an upper bound. Given 4 subsets A,B,C,D of the n-set, clearly AuB is different from CuD, because otherwise A would be a subset of CuD, which is forbidden by definition of perfect-union-code. Also note AuB differs from AuC since otherwise B would be contained in AuC. The number of set-pairs is m*(m-1)/2 where m=M(n), and they must all have unions which (i) differ and (ii) are subsets of {1,2,3,...,n} and (iii) are nonempty. Hence m*(m-1)/2 <= 2^n - 1. Hence UPPER BOUND THEOREM: M(n) < (-1/2) + 2^((n+1)/2). This also has exponential growth but the point is, it has only sqrt(2) not 2 as the growth factor. You could do a bit better by noting AuB must differ from CuD in at least 2 places... sort of... (several cases to treat) this should improve the bound, but not its growth factor.

2 2

[math-fun] when and why was it agreed that 0.999...=1?
by Gary Antonick 18 Nov '12

18 Nov '12

Hi all, I'm wondering if anyone knows when and why it was agreed that 0.999...=1. That is, the expression meant its limit of 1 and not something that got closer and closer to 1. I've asked several people and have gotten some big pieces but not quite the whole story: Keith Devlin (last week): before Cantor mathematicians considered "0.999..." to mean a *growing sequence* of 9's after the decimal. After Cantor it was decided that the expression meant the *limit* of this sequence: an infinite number of 9's after the decimal all at once. Steven Strogatz (this afternoon) suggested talking to John Stillwell John Stillwell (a couple hours ago) seemed to indicate the shift in perspective happened gradually, with Zeno arguing for the growing sequence (which would never get to 1) and everyone after the Axiom of Choice agreeing that the expression was referring to its limit. -400 Zeno: 1/2 + 1/4 + 1/8 etc will never get to 1 -350 Aristotle: 1/2 + 1/4 + 1/8 etc eventually gets to 1 -300 Euclid: 1/4 + 1/4^2 + 1/4^3 + etc eventually gets to 1/3 1585 Stevin: 0.999... = 1 1671 Newton: 0.999... = 1 1858 Dedekind cuts 1880? Cantor 1904 Zermelo: Axiom of Choice Does anyone have more precise timing for this shift from thinking? All the best, Gary

16 42

Re: [math-fun] 0.9999... = 1 and all that
by Dan Asimov 18 Nov '12

18 Nov '12

A colleague who's an algebraist in the UC-Berkeley math dept. assures me that for N any integer >= 2, "multiplication is certainly continuous in the standard topology on the N-adic integers, since this is the inverse limit of the discrete topologies on the rings Z/N^k, under which multiplication is certainly continuous." So as I had read somewhere, there is indeed a natural multiplication on the N-adic integers which is continuous relative to the topology induced by the N-adic metric. Even though for N composite the N-adic integers do have zero-divisors. --Dan Daniel Asimov Visiting Scholar Department of Mathematics University of California Berkeley, California

1 0

[math-fun] poisoned wine bottles: perfect-union codes
by Warren Smith 17 Nov '12

17 Nov '12

Veit: I'm starting to see why we need so many bottles before this puzzle is interesting! We can bound the number of rejected bottles R by R <= 2 ceiling( 1000/M(10) ) --Hey, the letter R was already taken! Use U (for unsafe) or B (for bad bottle)? where M(10) is the maximum size "perfect union code" on 10 symbols. I'm making up the name of these codes, which I believe are very interesting. Here's the definition: Describe binary codewords of length N in terms of subsets of N symbols. A "perfect union code" is a set of codewords such that if A, B, C are any distinct codewords in the code, then it never happens that A is contained in the union of B and C. The maximum sizes of perfect union codes starts out being very boring: M(3) = 3 M(4) = 4 M(5) = 5 M(6) = 6 These codes are just the N singleton subsets. But we can do better for large N... --ok, let me produce a general theorem about perfect-union-codes using a randomizing argument. Simply select from n items, random subsets of cardinality q each. Keep going until you've selected m such subsets. The chance that a particular subset A is contained in the union of two particular others B,C, is chance = 2q * (2q-1) * (2q-2) *...* (q+1) / ( n * (n-1) * (n-2) *...* (n+1-q) ) and hence the expected number of violations is expectednumber = m * (m-1) * (m-2) * chance / 2 hence if expectednumber < 1 then there must exist a random-choice-configuration with actually zero violations, i.e. a perfect-union code. So M(n) obeys M(n)>=m if m^3 * (2*q)^q < 2 * (n+1-q)^q that is if 3 * log(m) < log(2) + q * log(n-q) - q * log(2*q) choose q=0.1358*n to find EXPONENTIAL GROWTH THEOREM: M(n) > 2^(0.3333 + 0.07558*n).

2 1