This month's topics:
In 1736-1737 Benjamin Franklin constructed a number of 8 by 8 "magic squares" and one of size 16 by 16. The method he used seems still not to be known, but the total number of his type of 8 by 8 square has recently been calculated. Dawn Walton told the story in the story in "Magic math mystery solved at last" (Toronto Globe and Mail, March 3, 2006). There are, it turns out, several kinds of magic squares, even if we stick to the natural n by n squares in which every number from 1 to n2 appears once :
Diagonals: main (a), broken (b) and bent (c).
In the modern taxonomy, Franklin's squares are not magic. Nevertheless "how many permutations are possible under his distinct mathematical design" has "stumped mathematicians ever since," according to Walton. M. M. Ahmed in 2004 had given an upper bound of 228,881,701,845,346, but now "a trio of Canadian number crunchers have used modern-day technology" to pin the answer down quite a bit lower: "Using Franklin's rules, there are 1,105,920 variations of his magic square." The result is due to Peter Loly (Physics and Astronomy, Manitoba) and two graduate students, Daniel Schindel and Matthew Rempel. In their paper (available online) they describe their method: using an efficient algorithm to generate all the Franklin squares, and keeping an accurate tally. Remarkably, as they report, one third of the Franklin squares they found were also pandiagonal, and 368,640 is exactly what had been calculated in 1998 as the number of 8 by 8 complete squares. They show that this is not a coincidence by giving an algorithm for transforming one type to the other.
Franklin was very proud of his 16 by 16 square; he described it in his autobiography as "the most magically magical of any magic square ever made by any magician." (See Franklin's Magic Squares at Mathpages.com, which also gives the square itself). Unfortunately, it does not look like the Loly team's method, which involved searching (albeit efficiently) through 64! permutations, will be able to crack the 16 by 16 problem; 256! is a much bigger number.Chaos in the deep
"Reduced mixing generates oscillations and chaos in the oceanic deep chlorophyll maximum" appeared in the January 19 2006 Nature. The authors, an Amsterdam-Honolulu collaboration led by Jef Huisman and Nga N. Pham Thi, investigated the stability of deep chlorophyll maxima (DCMs) -layers of high concentration of phytoplankton who flourish where there are sufficient nutrients welling up from the bottom and sufficient light filtering down from the top. The point of the article: "we extend recent phytoplankton models to show that the phytoplankton populations of DCMs can show sustained fluctuations." The authors set up a mathematical model, a reaction-advection-diffusion equation for the phytoplankton population density P coupled to a partial differential equation for the nutrient availability N. A common parameter in both equations is the "turbulent diffusivity" κ , the coefficient of the second-derivative terms. If κ is sufficiently large, "nutrients in the top layer are gradually depleted by the phytoplankton. The nutricline moves downwards, tracked by the phytoplankton population, until the population settles at a stable equilibrium at which the downward flux of consumed nutrients equals the upward flux of new nutrients." To investigate the behavior for lower κ, the authors ran "numerous simulations using a wide range of turbulent diffusivities." "The model simulations predict that the DCM becomes unstable when turbulent diffusivity is in the lower end of the realistic range. By a cascade of period doublings, reduced turbulent mixing can even generate chaos in the DCM."
The numerical solution of the coupled P-N differential equations shows bifurcation and eventually chaos as the mixing parameter is decreased. This is a close-up picture of the evolution of the local maxima and minima of the phytoplankton population as a function of turbulent diffusivity, near the low end of the realistic range 0.1 < κ < 1. Image from Nature 439 324, used with permission.
Their explanation for the periodic behavior: if κ is low, the phytoplankton sink faster than the nutrients are welling up; without sufficient light their numbers decline. This lets more nutrients through up to more luminous layers, and "fuels the next peak in the DCM." An ominous note: "Climate models predict that global warming will reduce vertical mixing in the oceans."The differential geometry of quantum computation
"Quantum computers have the potential to solve efficiently some problems that are considered intractable on conventional classical computers." This is the start of "Quantum Computation as Geometry," a report in the February 4 2006 issue of Science. The authors are four members of the School of Physical Sciences, University of Queensland; a team led by Michael Nielsen. They continue: "Despite this great promise, as yet there is no general method for constructing good quantum algorithms, and very little is known about the potential power (or limitations) of quantum computers." What they propose in this report is an alternative approach to understanding the difficulty of an n-qubit computation, i.e. the complexity of the quantum algorithm that would be needed to carry it out. Such a computation corresponds to a unitary operator U (a 2n x 2n matrix with complex entries). The authors' definition of difficulty is the length d(I,U) of the shortest path from the indentity matrix to U, where length is measured in a metric which penalizes all computational moves which require gates with more than two inputs. They show that this distance is is "essentially equivalent to the number of gates required to synthesize U." "Our result allows the tools of Riemannian geometry to be applied to understand quantum computation. In particular we can use a powerful tool --the calculus of variation-- to find the geodesics of the space." They remark that thinking of an algorithm as a geodesic "is in contrast with the usual case in circuit design, either classical or quantum, where being given part of an optimal circuit does not obviously assist in the design of the rest of the circuit." Finally they show how "to construct explicitly a quantum circuit containing a number of [one and two-cubit] gates that is polynomial in d(I,U) and which approximates U closely."
Comments: Email Webmaster