January 2006 - mathfun@mailman.xmission.com

[math-fun] Bott periodicity
by Daniel Asimov 08 Jan '06

08 Jan '06

The NY Times just printed an obituary for Raoul Bott, Emeritus of the Harvard math dept. who passed away Dec. 20: <http://www.nytimes.com/2006/01/08/national/08bott.html>. It mentions one of his best-known results, "Bott periodicity", which blew me away when I first learned of it as a grad student. So in case anyone's interested, I thought I'd describe it here for those not already familiar with it. (Some technical details are omitted.) Given a topological space X, there are algebraic invariants which describe its holes, which can come in various dimensions. These include the groups pi_n(X) for each n = 1,2,3,.... We consider only spaces X for which any two points can be connected by a continuous path. As a set, pi_n(X) is all continuous maps of the unit n-sphere S^n into X where a preassigned point of S^n is required to map to a preassigned point (call it *) of X . . . and THEN any two such maps f,g: S^n -> X are considered equivalent if there is a continuous *family* of such maps {h_t, 0 <= t <= 1}, with h_0 = f and h_1 = g. This set is given a group structure, so each pi_n(X) is a group. (The "fundamental" group, pi_1(X), is the only one that can be (and often is) non-abelian; any pi_n(X) for n > 1 is abelian.) For some examples, pi_1(figure-8) is the free group on 2 generators. For any n, pi_n(S^n) is the group Z of integers. ------------------------------------------------------------------------------ A convergent thread starts with the fact that any Euclidean space R^n has its own group of rotations, which is also a topological space such that the group operations are continuous. If we also toss in the isometries of R^n preserving the origin which *reverse* orientation, we get the set of all invertible nxn matrices M such that M-transpose = M-inverse. This topological ("Lie") group is denoted by O(n), the orthogonal group of R^n. (O(n) corresponds to the set of all n-tuples of orthonormal vectors in R^n.) O(n) is locally Euclidean -- i.e., a manifold -- of dimension (n^2 - n)/2. Just as R^n naturally includes in R^(n+1) as the first n coordinates, we may form the matural inclusions O(1) in O(2) in . . . O(n) in O(n+1) in . . .. Using these inclusions we can take the union of all the O(n)'s for n >= 1 to get an all-inclusive group that we call O(oo). ------------------------------------------------------------------------------ Embodying all the symmetry of all Euclidean spaces R^n, O(oo) is a very interesting object. Raoul Bott showed that pi_n(O(oo)) depends only on n mod 8. Here is the table: n mod 8 0 1 2 3 4 5 6 7 ---------------------------------------------------------------------- pi_n(O(oo) Z_2 Z_2 0 Z 0 0 0 Z It is not a coincidence that the dimensions 0,1,3,7 of the non-zero groups mod 8 are the same as the dimensions of the unit spheres in the only normed real division algebras: the reals, complexes, quaternions, octonions; these four division algebras give rise to the existence of non-zero homotopy classes in pi_n(O(oo)). There is much more to Bott periodicity, but this will do for now. --Dan

3 2

[math-fun] Implication chains in Sudoku
by J.P. Grossman 08 Jan '06

08 Jan '06

I avoided Sudoku for as long as possible because I knew what would happen but I finally succumbed, so here is the resulting logic-only (no guessing) Javascript Sudoku helper/solver: http://www.mathstat.dal.ca/~jpg/sudoku/ As far as I can tell this is currently the most powerful online solver. Back in November there was some discussion as to what qualifies as "no guessing"; Bernie Cosell opined that if multiple implication chains are used to establish a single condition then this is a form of guessing since it essentially tries a number antecedents in turn. Sudoku Helper uses implication chains which are of the form (d not in A) => (x1 in X1) => (x2 not in X2) => (x3 in X2) => ... => (d in B) Which simplifies to (d not in A) => (d in B), which is the same as "d is in A or B". Many of the existing strategies are of this form (i.e. they show that a single digit must be in a set of squares and use this fact to eliminate possibilities), so I feel fairly comfortable in classifying this as a logic technique rather than a guessing technique. More generally, any unsolved Soduku puzzle can be turned into formal logic using a set of predicates A_d ("The digit d is in the square A"), and a set of constraints defined by the rules of Sudoku and the current position (e.g. (A_2 v A_3 v A_7)). One could then write a theorem prover whose search algorithm is customized for Sudoku; the theorem prover could also avoid "proof by contradiction". At that point it becomes hard to argue that anything but logic is being used, even if the prover is doing things like merging multiple implication chains in a way that, for a human, would be guessing. It all boils down to semantics, and I would have to say that "guessing" really means "logic that doesn't fit in a human's head". J.P.

1 0

Re: [math-fun] Bott periodicity
by Daniel Asimov 08 Jan '06

08 Jan '06

Fred Lunnon writes: >On 1/8/06, Daniel Asimov <dasimov(a)earthlink.net> wrote: >> The NY Times just printed an obituary for Raoul Bott, Emeritus of the Harvard >> math dept. who passed away Dec. 20: >> <http://www.nytimes.com/2006/01/08/national/08bott.html>. >> It mentions one of his best-known results, "Bott periodicity", which blew me >> away when I first learned of it as a grad student. [etc etc] > >I have to admit I'd kinda assumed that "Bott periodicity" >referred to the fact that the real Clifford algebra Cl(n+8,0) generated >by n+8 square roots of +1 is isomorphic to 16x16 matrices over Cl(n,0), >on no better grounds than that the relevant ur-text is > M.F.Atiyah, R.Bott, A.Shapiro "Clifford Modules" Topology vol.3 (1964). >Was this conclusion entirely unjustified, or is there some connection? ----------------------------------------------------------------------------- I've just learned that this purely algebraic fact is sometimes *also* called "Bott periodicity" -- at least by John Baez in his article on octonions, section 2.3: <http://math.ucr.edu/home/baez/octonions/node6.html>. I believe that with some sophisticated algbraic-topological reasoning, one can show that the dependence of the homotopy group pi_n(O(oo)) only on n mod 8 is closely connected wiith this algebraic periodicity. But Bott's original discovery is the topological fact that pi_(n+8)(O(oo)) = pi_n(O(oo)) for all n = 1,2,3,.... (And similar periodicities for the infinite unitary group U(oo) and thee infinite symplectic group Sp(oo).) --Dan

1 0

RE: [math-fun] the heck with it, simplification challenge
by Pacher Christoph 08 Jan '06

08 Jan '06

Hi, Regarding the last Mma question: >Can some Mma wizard explain how to get Re[ArcSin[2]], e.g., >(c61) realpart(asin(2)) > %pi >(d61) --- > 2 It is as simple as ComplexExpand[Re[ArcSin[2]]] or equivalently Re[ArcSin[2]]//ComplexExpand tested in Mma 5.0 . Chris, not being a real wizard ;-)

1 0

[math-fun] what the heck is this?
by R. William Gosper 08 Jan '06

08 Jan '06

sum((i-a)!*(i-b)!*(i-c)!/((i+a+1)!*(i+b+1)!*(i+c+1)!),i,0,inf) =((-a-1)!*(-b-1)!*(-c-1)!/2)*(((c+b+a)!/((b+a)!*(c+a)!*(c+b)!))-1/(a!*b!*c!)) inf ==== \ (i - a)! (i - b)! (i - c)! > -------------------------------------- = / (i + a + 1)! (i + b + 1)! (i + c + 1)! ==== i = 0 (- a - 1)! (- b - 1)! (- c - 1)! (c + b + a)! 1 -------------------------------- (-------------------------- - --------). 2 (b + a)! (c + a)! (c + b)! a! b! c! E.g., (c78) minfactorial(limit(subst([c = a,b = a],%),a,0)) inf ==== \ 1 (d78) > -------- = zeta(3) / 3 ==== (i + 1) i = 0 Looks like there's a bilateral version, too. --rwg PS: An easy sudoku with a blank row, (auto)morphed from 18 Nov LIFE "magazine": [[8,3,_;_,_,1;9,_,_],[_,7,_;8,4,_;_,_,_],[_,_,6;_,9,_;_,1,3]; [7,9,_;_,_,_;_,_,_],[1,_,_;_,_,_;_,_,2],[_,_,_;_,_,_;_,3,4]; [4,5,_;_,7,_;2,_,_],[_,_,_;_,6,4;_,8,_],[_,_,8;9,_,_;_,7,5]] [ [ 8 3 _ ] [ _ 7 _ ] [ _ _ 6 ] ] [ [ ] [ ] [ ] ] [ [ _ _ 1 ] [ 8 4 _ ] [ _ 9 _ ] ] [ [ ] [ ] [ ] ] [ [ 9 _ _ ] [ _ _ _ ] [ _ 1 3 ] ] [ ] [ [ 7 9 _ ] [ 1 _ _ ] [ _ _ _ ] ] [ [ ] [ ] [ ] ] [ [ _ _ _ ] [ _ _ _ ] [ _ _ _ ] ] [ [ ] [ ] [ ] ] [ [ _ _ _ ] [ _ _ 2 ] [ _ 3 4 ] ] [ ] [ [ 4 5 _ ] [ _ _ _ ] [ _ _ 8 ] ] [ [ ] [ ] [ ] ] [ [ _ 7 _ ] [ _ 6 4 ] [ 9 _ _ ] ] [ [ ] [ ] [ ] ] [ [ 2 _ _ ] [ _ 8 _ ] [ _ 7 5 ] ]

1 4

[math-fun] simulating three inverters with two inverters
by James Propp 06 Jan '06

06 Jan '06

>I've always been curious about the feedback/loops restriction. Does >anyone know how much things can be improved for boolean _functions_ >that are implemented with feedback and/or loops? I suspect that >latency can't be improved, but I suspect that the # of gates can be >improved over the no feedback/loop version. > >(To be clear, I'm thinking about implementing functions using circuits >that might have state, but the initial state is irrelevant to the >output. For example, a boolean circuit might utilize some sort of >hash table lookup to implement an initial guess that is verified before >being output. In this case, the (mean) latency could be improved over >the no-state version.) This reminds me of old puzzle I learned about from Lee Sallows, solved with Bruce Smith, and can no longer remember how to solve: How can you use two NOT-gates, as many AND-gates as you like, and as many OR-gates as you like, in order to create a circuit with three inputs and three outputs that acts like three NOT-gates in parallel? (And why can't this trick be bootstrapped to make two NOT-gates act like four?) If anyone can point me to the write-up of this that appeared in the Mathematical Intelligencer a couple of decades ago, I'd be grateful! (A Google-search failed to reveal it.) Jim Propp

4 4

[math-fun] (no subject)
by Torgerson, Mark D 03 Jan '06

03 Jan '06

Rich, When you heading to Alb next? Mark

1 0

[math-fun] January update of multimagie.com
by Christian Boyer 03 Jan '06

03 Jan '06

The January update of www.multimagie.com/indexengl.htm is now online: - With a new page on the hidden link between Sudokus and bimagic squares, as announced in this forum in November. - With latest results on multiplicative squares from 3x3 to 17x17, including 8x8 and 9x9 additive-multiplicative squares. Thanks again to Don, Edwin and Günter for their checking of the biggest squares. An Excel file can be downloaded including these squares. - And other news (highly multimagic squares, ...) I wish you a happy new year 2006. Christian.

1 0