August 2012 - mathfun@mailman.xmission.com

[math-fun] Update on Warren's go handicap puzzle from way back
by Phil Carmody 28 Aug '12

28 Aug '12

I posed Warren Smith's puzzle to a group of people who play go online, to see if they could improve on his symmetrical answer. Alas, they broke it with a quadruple-ko bombshell which leads to a draw (or an anullment of the game). However, slow progress is being made getting the number back down from astronomical levels: http://www.littlegolem.net/jsp/forum/topic2.jsp?forum=20&topic=340 Alas, I know next-to-bugger-all about go, so can't actually contribute anything to the discussion myself, but can at least mediate the mathematical fun aspects of such a discussion. (Of course, you're welcome to sign up and thrash the pants off me at dots and boxes too.) Phil [Are there archives of this list? I don't keep the old digests, so have no idea exactly which post I should be responding to.] -- () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani]

1 0

Re: [math-fun] Infinite product vector space puzzle
by Michael Reid 27 Aug '12

27 Aug '12

> Let R^oo denote the real vector space that is the countable direct product of copies of the reals. > > I.e., all countable-tuples of reals with componentwise addition. > > Puzzle: What is the dimension of the real vector space R^oo ??? I thought about the same question, in a slightly more general setting a few years ago. Specifically, let k be a field, and let Map(N, k) be the k-vector space of all functions from N (the set of natural numbers) to k . The question I considered, was "what is the dimension of Map(N, k) over k ?" I found it very counterintuitive that the answer depends upon the field k ! I did not solve it in all cases, but I can do Dan's case, in which case the dimension is c = 2^Aleph_0 . In general, the dimension is at least max(|k|, c) . I do not know if this is the right answer if k has cardinality strictly between Aleph_0 and c (in which case CH is false). For x in k , consider the function n |--> x^n . These functions are linearly independent over k , so the dimension is at least |k| . On the other hand, the vector space V = Map(N, k) has cardinality at least c . If k is an infinite field, and B is a basis of V , then |V| = |B| |k| = max(|B|, |k|) . This shows that if |k| < c , then |B| >= c . If k is finite, then it's easy to see that |V| = c , and B must be infinite, in which case |V| = |B| , so the dimension is c . (When k = R , the vector space has cardinality c , so a basis can't have cardinality larger than c .) Michael Reid

4 7

[math-fun] Bill Thurston sphere eversion "Outside In"
by Henry Baker 27 Aug '12

27 Aug '12

FYI -- Very nice 21 minute video about Thurston's sphere inversion "Outside In" http://www.youtube.com/watch?v=wO61D9x6lNY

1 0

[math-fun] Chebfun: Taylor series are obsolete
by Henry Baker 27 Aug '12

27 Aug '12

If you're not aware of the "Chebfun" package developed by Trefethen, et al, at Oxford U., you will be pleasantly surprised. Basically, Chebfun approximates smooth curves over a finite interval to within machine precision. Chebfun also supports piecewise smooth curves by separately Chebbing each piece. Since different smooth curves require different numbers of terms to converge, some of these sums can have 1000 or more terms. As pointed out in the slides & video below, the whole point of this is to provide the flavor of symbolic computation with the efficiency and ease of numeric computation. For example, plotting, derivatives, integrals, root-finding are all relatively easy in this framework. The major success of Chebfun's is in ODE's, both linear & non-linear. It's a pity that Chebfun only works on Matlab; perhaps some student could be motivated to do this in Maxima. After watching the video below, I started to wonder why we bother teaching Taylor series at all. Here's a 1-hour tutorial about Chebfun (850 MBytes): http://downloads.sms.cam.ac.uk/1160831/1160835.mp4 Here are the slides for this talk (1 MByte): http://people.maths.ox.ac.uk/trefethen/chebfun.pdf Some history of Cheb approximations http://people.maths.ox.ac.uk/trefethen/cftalk.pdf

6 12

[math-fun] A215723/215897/003112 circulant max-determinants and Graham-Lehmer sequence
by Warren Smith 27 Aug '12

27 Aug '12

maxdet 37x37 circulant: N=37 grle=-3.39696021397230322e+20 det=5.41106751627075914e+28 circ=--++-+---+---+-++---+++-++-+-++------

1 0

[math-fun] maxdet & other larger numbers -- which am I sure of?
by Warren Smith 26 Aug '12

26 Aug '12

Neil Sloane wanted to know which terms I was "sure of". Well, until I have a rigorous bound for accumulated roundoff error, which I do not, I'm not sure of any term. However, the reason I printed those terms with both integer and float forms, was to enable the reader to estimate how much roundoff error there is. (Such an estimate is not 100% certain, sorry.) I think every determinant of an NxN sign matrix, N<=26, should be exact. I think every number I gave, no matter how large the matrix, ought to be good for 9 significant figures (Sloane may not like approximate answers, but he can get them if he wants). [I stopped trying to enter numbers into the OEIS myself quite a while ago because it was just too damn annoying to use, and plus to add insult to injury it had blown away my login account but nevertheless insisted I use it.]

2 1

[math-fun] A215723/215897/003112 circulant max-determinants and Graham-Lehmer sequence
by Warren Smith 26 Aug '12

26 Aug '12

> From: Joerg Arndt <arndt(a)jjj.de> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Maximum |determinant| for NxN circulant sign > matrix? > Message-ID: <20120826064811.GA3956(a)jjj.de> > Content-Type: text/plain; charset=us-ascii > > I cited you (please correct if necessary), as > > "A215723(n) is divisible by 2^(n-1), indeed the determinant of any n > by n sign matrix is divisible by 2^(n-1). Proof: subtract the first > row from other rows, the result is all rows except for the first are > divisible by 2, hence by using expansion by minors proof > follows. (Warren D. Smith on the math-fun mailing list, Aug 18 2012)" > > See https://oeis.org/A215897 > and https://oeis.org/A215723 > > I also computed more terms (and will compute still more later), --oh. Thanks for doing that. In the meantime I myself had computed more terms. My program presently uses both the gray code trick and the fourier transform trick to cut computation time to O(N) per NxN determinant. However, it does not use the necklace trick (if you have a way to compute necklaces via a "gray code" and not generating the negated and reverse-direction necklaces, that would be best...) Also as a side effect, I computed more terms of the Graham-Lehmer sequence https://oeis.org/A003112 The bad news is, I use 64-bit floating point arithmetic, which is inexact. Hence my numbers are not likely to be exact beyond about N=30, although they still should be accurate to say 9 significant figures. Anyway, for what it is worth, here is my current table. Note for 28<=N<=35 I output each line twice, once using floating point and once using integers. The integers are my program's best guess but become less and less likely to be exact the larger N gets. If you wanted to get exact integer values of the Graham-Lehmer sequence, then by using the fourier transform trick but NOT with a complex Nth root of unity, but rather an integer Nth root of unity inside suitable prime-order finite fields, you could compute exact values modulo P using all-integer arithmetic, for various primes P. Then you could by chinese remaindering reconstruct the exact integer value. I have not implemented that, but it would be easy. If you wanted to get exact integer determinant values you could do that also... and I've provided the matrices so you can do it from them. NxN circulants with max |determinant| and Graham-Lehmer sequence: N= 1 grle= 1 det= 1.00 circ=- N= 2 grle= 0 det= 0.00 circ=-- N= 3 grle= -3 det= 4.00 circ=-+- N= 4 grle= 0 det= 16.00 circ=-+-- N= 5 grle= -5 det= 48.00 circ=-+--- N= 6 grle= 0 det= 128.00 circ=-+---- N= 7 grle= -105 det= 512.00 circ=--++-+- N= 8 grle= 0 det= 2304.00 circ=-+--++++ N= 9 grle= 81 det= 6912.00 circ=-+++-++-+ N=10 grle= 0 det= 22528.00 circ=-+----++-+ N=11 grle= 6765 det= 273408.00 circ=-++----+-+- N=12 grle= 0 det= 2097152.00 circ=-+++++--++-+ N=13 grle= 175747 det= 14929920.00 circ=---+-----+-++ N=14 grle= 0 det= 50331648.00 circ=-+-+--++-----+ N=15 grle= 30375 det= 390905856.00 circ=--++++--+---+-- N=16 grle= 0 det= 1644167168.00 circ=-+--+--+++---+-- N=17 grle= 25219857 det= 12279939072.00 circ=-+--+--++++---+-- N=18 grle= 0 det= 69660573696.00 circ=-+------++----++-+ N=19 grle= 142901109 det= 865782202368.00 circ=----++---+-+++-+--+ N=20 grle= 0 det= 5566277615616.00 circ=--++-++++++--+++-+-+ N=21 grle= 4548104883 det= 41248865910784.00 circ=-++++-++-+++-+---++++ N=22 grle= 0 det= 215055782117376.00 circ=--++--+++-------+-+--+ N=23 grle= -31152650265 det= 2385859554836480.00 circ=-++-++-----++---+---+-+ N=24 grle= 0 det= 25783171861708800.00 circ=--++-++--+++-+-++++-++-- N=25 grle= -5198937484375 det= 146322302697472000.00 circ=----+----++--++-+---+++-+ N=26 grle= 0 det= 1107244165160239104.00 circ=--+--+-+-+------+++--+++-+ N=27 grle= 65230244418933 det= 11063259546716733440.00 circ=-+--++--++++-+++++---+-++-+ N=28 grle= 0 det= 76787161889935196160.00 circ=-+----+------+++-++--+-++--+ N=28 grle= 5.42831757821841165e+00 det= 7.67871618899351962e+19 circ=-+----+------+++-++--+-++--+ N=29 grle= -1300425712598285 det= 668472148627227148288.00 circ=-+-+-++-++-----+++----+---+-- N=29 grle= -1.30042571259702600e+15 det= 6.68472148627227148e+20 circ=-+-+-++-++-----+++----+---+-- N=30 grle= 0 det= 5815090244208379822080.00 circ=-+-+-+-+--+--+-------++++--++- det might also be 5815090244206769209344 N=30 grle= -1.47377310385102646e+02 det= 5.81509024420837982e+21 circ=-+-+-+-+--+--+-------++++--++- N=31 grle= 126691467546591 det= 73063423016988991029248.00 circ=--+-+++-+++---++++++-+-++-+--+- det might also be 73063423016960000000000 N=31 grle= 1.26691467536151578e+14 det= 7.30634230169889910e+22 circ=--+-+++-+++---++++++-+-++-+--+- N=32 grle= 0 det= 607251019096056018239488.00 circ=-+-+++-++--------++----+++--+--+ det might also be 607251019095912136835072 N=32 grle= 6.85369002173049375e+03 det= 6.07251019096056018e+23 circ=-+-+++-++--------++----+++--+--+ N=33 grle= 868088125376401545 det= 6839365759940440694456320.00 circ=-+---+++-++----+-++-++---+-+----- N=33 grle= 8.68088125416532864e+17 det= 6.83936575994044069e+24 circ=-+---+++-++----+-++-++---+-+----- N=34 grle= 0 det= 44960394053012531624017920.00 circ=---++-------+-+--++++---+-+--++--+ N=34 grle= 3.72945646649002098e+05 det= 4.49603940530125316e+25 circ=---++-------+-+--++++---+-+--++--+ N=35 grle= 3307726657734296875 det=573365205894426472008908800.00 circ=-+++-+-+--+--++-----++-+----+---+++ N=35 grle= -1.51390174160995676e+19 det= 5.73365205894426472e+26 circ=-+++-+-+--+--++-----++-+----+---+++ computation ongoing, should reach N=40 in a few days if no crash. And for Toeplitz matrices: NxN Toeplitz matrices with entries +-1 and maximum |determinant| (Matrices specified by stating leftmost column going up, then continuing along top row going right, i.e. "clockwise.") N det example matrix 1 1.00 + 2 2.00 +-- 3 4.00 --+++ 4 16.00 +---+-- 5 48.00 -++++-+++ 6 160.00 +-+++--+--- 7 576.00 -++++-+--++++ 8 2560.00 +-+++---+--+--- 9 12288.00 --+---+++-++-+++- 10 73728.00 ++-++-+++---+--+--- 11 327680.00 +-++++--+++-+-----+-- 12 2097152.00 +-++----+---+-++----+-- 13 14929920.00 -+-+++++-+++--+-+++++-+++ 14 68853760.00 +--+-+-----+++-++-+-+++++-- 15 390905856.00 ---++-+-+++++-+---++-+-+++++- 16 2363752448.00 +-----++-+++--+-+-----+--++---+ 17 14260174848.00 -+++++++--+-+-++--+++++-++---+-++ 18 124581314560.00 ++----+----+-+++-+--++++-++++-+---+ And maxdet for Circulant*BackCirculant matrices (* denotes Hadamard product) (Matrices specified by stating top row of circulant, then of backcirculant.) N det example matrix 1 1.00 -- 2 0.00 +--+ 3 4.00 +++-+- 4 16.00 ++---+-- 5 48.00 ------+--- 6 128.00 +++----+---- 7 512.00 +++++++++-+--- 8 4096.00 ++---+---+------ 9 6912.00 +++++++++++-+++-+- 10 36864.00 +-+++++-+-+++++-++-- 11 273408.00 +++++++++++-+--+++---- 12 -2097152.00 +-+-+--+--+-++-+-++----- 13 14929920.00 +++++++++++++++++-+++--+-+ 14 -50331648.00 ++--+-+--------+-+-+-+-+-+-+ 15 390905856.00 ---------------++-+---++-+-+++ 16 4294967296.00 ++---++-+++-+++--+-+------------ 17 12279939072.00 ++-+++--++-+---+++++++++++++++++++ 18 69660573696.00 +-+-+-+-+-+-+-+-+-+++-+-+++++-+--+--

3 3

[math-fun] Maximum |determinant| for NxN circulant sign matrix?
by Warren Smith 26 Aug '12

26 Aug '12

1. The determinant of any NxN sign matrix is divisible by 2^(N-1). Proof: subtract 1st row from other rows, result is all rows except 1st are divisible by 2, hence by using expansion by minors proof follows. 2. The maximum |determinant| among NxN circulant sign matrices if N is sufficiently large, is at least (c*N)^(N/2) for some constant c>0 which I have not bothered to work out, but c=0.1 should be safe. Proof sketch: Use the FFT-product formula for determinant. Need to prove signs exist causing each of the N |multiplicands| to be >c*sqrt(N). This can be done using a counting argument and central limit theorem - if |c|>0 small enough then at least half the sign-choices survive the kth demand, and due to the unitary nature of the FFT matrix each demand is orthogonal to the previous, hence effects can be reckoned independently. Initially 2^N sign choices, and after N demands at least one remains.

2 1

Re: [math-fun] Chebfun: Taylor series are obsolete
by Henry Baker 25 Aug '12

25 Aug '12

I agree re differentiation being numerically unstable, but I don't know the answer. The video does show a number of examples, but I don't recall this particular issue being addressed. Many of the examples used in the video were combinations of well-known functions -- e.g., sin(x), cos(x), whatever. I don't know if Chebfun calculated all of the approximating functions numerically or symbolically (e.g., using symbolic algebra and known properties of sin, cos, etc.) Trefethen has published widely, so I suspect that most of these issues are covered in his papers: http://people.maths.ox.ac.uk/trefethen/publication/publication.html At 01:22 PM 8/25/2012, Fred lunnon wrote: > Some issues are raised by the slides, one of which lists differentiation >as a built-in functional. Maybe somebody else can clarify these for me? > > Differentiation is numerically unstable; therefore the original function >will have to be recomputed at increasing precision in order to maintain >the prescribed error in higher derivatives. As far as I can see, simply >increasing the number n of interpolating points is insufficient to remedy >the problem, whatever approximations (Taylor, Chebychev or whatever) >are employed. > > Furthermore allowing n to vary dynamically seems to imply that the >user must express his function f as an infinite Chebychev series (or >maybe combination of built-in functions). If for example he possesses >only a functional equation for f, it's unclear how this can be achieved >within the framework supplied. > >Fred Lunnon > >On 8/25/12, Henry Baker <hbaker1(a)pipeline.com> wrote: >> If you're not aware of the "Chebfun" package developed by Trefethen, et al, >> at Oxford U., you will be pleasantly surprised. >> >> Basically, Chebfun approximates smooth curves over a finite interval to >> within machine precision. Chebfun also supports piecewise smooth curves by >> separately Chebbing each piece. >> >> Since different smooth curves require different numbers of terms to >> converge, some of these sums can have 1000 or more terms. >> >> As pointed out in the slides & video below, the whole point of this is to >> provide the flavor of symbolic computation with the efficiency and ease of >> numeric computation. For example, plotting, derivatives, integrals, >> root-finding are all relatively easy in this framework. >> >> The major success of Chebfun's is in ODE's, both linear & non-linear. >> >> It's a pity that Chebfun only works on Matlab; perhaps some student could be >> motivated to do this in Maxima. >> >> After watching the video below, I started to wonder why we bother teaching >> Taylor series at all. >> >> Here's a 1-hour tutorial about Chebfun (850 MBytes): >> >> http://downloads.sms.cam.ac.uk/1160831/1160835.mp4 >> >> Here are the slides for this talk (1 MByte): >> >> http://people.maths.ox.ac.uk/trefethen/chebfun.pdf >> >> Some history of Cheb approximations >> >> http://people.maths.ox.ac.uk/trefethen/cftalk.pdf

1 0

[math-fun] Orchard problem
by Fred lunnon 24 Aug '12

24 Aug '12

TT provides a succinct survey of the orchard problem etc, though currently apparently missing a crucial definition --- which omission will, on past performance, doubtless be repaired in short order. WFL http://terrytao.wordpress.com/2012/08/24/on-sets-defining-few-ordinary-line…

1 0