August 2012 - mathfun@mailman.xmission.com

[math-fun] Asimov's equipopulous max-determinant problem
by Warren Smith 23 Aug '12

23 Aug '12

Dan Asimov wanted the NxN max-|determinant| sign matrix with equal numbers of +1's and -1's. (N necessarily even.) Some answers: N=2: maxdet=0. N=4: maxdet=16, use circulant(+---) then negate 2 rows. N=2^k for N>4: maxdet=N^(N/2) by Sylvester inductive doubling construction (use N/2 size Asimov solution Kronecker-producted with 2x2 Hadamard matrix) N=p+1 where p=prime and N divisible by 4: maxdet=N^(N/2). Use Paley construction of NxN Hadamard matrix by making pXp circulant, bordered by +1's in an extra first row and first column where the first row of the circulant is given by Jacobi symbols mod p, except falsely regard (0|p) as -1. Now negate the last N/4 columns, then finally negate the first row. N=6: maxdet=128. circulant(+-----) then negate 3 rows. This can be proven maximal by using http://www.indiana.edu/~maxdet/spectrum.html The first cases these constructions leave open now are N=10,14,18. You can probably solve these 3 cases but I doubt you will be able to settle this problem for all N. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] William Thurston, Theoretical Mathematician, Dies at 65
by Henry Baker 23 Aug '12

23 Aug '12

FYI -- http://www.nytimes.com/2012/08/23/us/william-p-thurston-theoretical-mathema… William P. Thurston, Theoretical Mathematician, Dies at 65 By LESLIE KAUFMAN Published: August 22, 2012 William P. Thurston, a mathematician who revolutionized understanding of the structure of three-dimensional spaces and won the Fields Medal, often described as the equivalent of the Nobel Prize for mathematics, died on Tuesday in Rochester. He was 65. The cause was cancer, his son Dylan said. Dr. ThurstonÂs fields of expertise were geometry and topology, the study of different possible shapes for multidimensional space. Perhaps his greatest accomplishment in a lifetime of breakthroughs was his Geometrization conjecture, which postulated that all possible three-dimensional spaces are made up of eight types of geometric pieces, a discovery he likened to finding eight outfits that could fit anybody in the world. For most of his professional life, Dr. Thurston was among a very rarefied group in his field that thinks deep theoretical thoughts with no particular practical application, a luxury he reveled in. ÂI donÂt do it for the bottom line,Â Dr. Thurston told The Wall Street Journal in 1983. ÂThe inner force that drives mathematicians isnÂt to look for applications; it is to understand the structure and inner beauty of mathematics.Â John Milnor, co-director of the Institute for Mathematical Sciences at Stony Brook University on Long Island, acknowledged that Dr. Thurston delighted in working in a very esoteric realm. But he added that Dr. ThurstonÂs work had made Âa tremendous difference in the way we look at many problems.Â Without that work, a Russian mathematician, Grisha Perelman, would not have been able in 2003 to solve the PoincarÃ© conjecture, which asserts that the sphere is the only three-dimensional shape in which every loop in its structure can be shrunk to a single point, without ripping or tearing either the loop or the space. The problem had challenged mathematicians for 100 years. In addition, cosmologists have drawn on Dr. ThurstonÂs discoveries in their search for the shape of the universe. On a more unlikely note, his musings about the possible shapes of the universe inspired the designer Issey MiyakeÂs 2010 ready-to-wear collection, a colorful series of draped and asymmetrical forms. The fashion Web site Style.com reported that after the show, the houseÂs designer and Dr. Thurston Âwrapped themselves for the press in a long stretch of red tubing to make the point that something that looks random is actually (according to Thurston) Âbeautiful geometry.Â Â To his colleagues, Dr. ThurstonÂs most unusual gift was his ability to visualize complex shapes and problems. They said he loved nothing more than to sit in a common room and help colleagues or students brainstorm on solutions to vexing issues. ÂHe could look at a problem and see simplicity where nobody else could find it,Â said Jeff Weeks, a mathematician who studied with Dr. Thurston at Princeton. For example, he could think in multiple dimensions. ÂPeople donÂt understand how I can visualize four or five dimensions,Â Dr. Thurston told The Journal. ÂFive-dimensional shapes are hard to visualize Â but it doesnÂt mean you canÂt think about them. Thinking is really the same as seeing.Â William Paul Thurston was born on Oct. 30, 1946, in Washington, to Paul and Margaret Thurston. His father was a Naval engineer. William showed aptitude in math early on, amazing preschool teachers with his ability to add two- and three-digit numbers in his head, his older brother, Robert, recalled. Asked how he did it, he replied that he Âcounted on his fingers in his mind,Â Robert Thurston said. Dr. Thurston received an undergraduate degree at New College in Florida and a Ph.D. in mathematics at the University of California, Berkeley, in 1972. He quickly earned a reputation as an original thinker and caught the attention of PrincetonÂs renowned mathematics department, which recruited him to be a professor at the age of 27. He was in his mid-30s when he received the Fields Medal in 1982 for his work in deepening the connection between geometry and topology. (The medal is awarded every four years by the International Mathematical Union.) He worked longest at Princeton but also held posts at Berkeley and the University of California, Davis. He was most recently at Cornell. Dr. ThurstonÂs first marriage, to Rachel Findley, ended in divorce. In addition to his son Dylan and his brother Robert, he is survived by his wife, Julian Muriel Thurston; their children Hannah Jade and Liam; two children from his first marriage, Nathaniel and Emily; his mother, Margaret; a sister, Jean Baker; a brother, George; and two grandchildren. Dylan Thurston, also a mathematician, said that despite working in a realm of rather cold abstractions, his father was personally very warm. ÂGrowing up there were many beautiful mathematical pictures in the house,Â he said. ÂHe was a very visual thinker; he had powers to see spaces that no one before him could, and he was always drawing pictures of what he could see and doodles in notebooks, and we would talk about it. ÂMath was always very fun for him.Â A version of this article appeared in print on August 23, 2012, on page B15 of the New York edition with the headline: William P. Thurston, 65, Math Innovator, Is Dead.

1 0

[math-fun] The Maxdet problem and why the Hankel*Toeplitz construction *might* be a breakthrough
by Warren Smith 22 Aug '12

22 Aug '12

> 1. Re: Max determinant via Hadamard product of Toeplitz & Hankel > (W. Edwin Clark) >> OK, my searcher has now found matrices of the form >> Toeplitz*Hankel, where * denotes Hadamard elementwise matrix product >> (C=A*B means C_ij=A_ij B_ij) where both A and B are sign matrices, >> which achieve the maximum possible |determinant| among ALL matrices of >> size N >> with entries in [-1,1], for EVERY N=1,2,3,...,13 (and N=16). >> See http://oeis.org/A003433 . >> >> > It follows from your computation that some Hadamard matrices of order can > be factored in this way. > Question: Do all Hadamard > matrices<http://en.wikipedia.org/wiki/Hadamard_matrix>have such a > factorization? I would guess not. --that is basically the $64000 question -- albeit with the slight alteration that we are not interested in the Hadamard matrix itself -- we merely want that one of its "equivalent" forms have a Hank*Toep expression -- and further, even then I merely ask that at least one Hadamard of each size have such an expression, not necessarily every one. Further, I am also interested in "maxdet" matrices of each size -- Hadamards are maxdet matrices only at multiples of 4 as the matrix size, but I am interested in all matrix sizes. =========REVIEW/RECAP ABOUT MAXDET PROBLEM======== It has been a problem open for over 150 years to find the largest determinant that an NxN matrix with |entries|<=1, can have. The current record upper & lower bounds are in this online "hall of fame": http://www.indiana.edu/~maxdet/ the exact answers are known for 1<=N<=21. Many contributions to the current hall of fame were made by Tomas Rokicki. (I played some role too, lesser and earlier.) Now, in all those years, there has never been a reasonably small+simple matrix subclass proposed, which contains the solutions to all maxdet problems for all N. Until now: the Toep*Hank form does the job for each size N=1,2,...,13. So maybe it keeps working forever! That would be spectacular if true. However, I have no great reason to believe it is true aside from fact it works for 1,2,...,13. I have no idea whether it works for N=14 and/or 15. Now if we restrict to N which happen to be 1,2, or divisible by 4, then it is famous open conjecture that a "Hadamard matrix" always exists of size N. That means a matrix with +1 and/or -1 entries, and determinant=N^(N/2) (which necessarily is maximum). Many great mathematicians have tried to investigate that question: J.J. Sylvester, J. Hadamard, R.E.A.C.Paley, John Williamson, and Jennifer Seberry being probably the greatest contributors. Williamson came up with a simple form which for over 50 years everybody conjectured sufficed to yield a Hadamard matrix of every size N=4*n>=4. It is: A B C D -B A -D C -C D A -B -D -C B A where A,B,C,D each are symmetric nXn circulant matrices chosen so it works. But eventually computer hardware & software got good enough to do an exhaustive search for all Williamson-form Hadamards with n<=59. The result of this search was one exists for each n=1,3,5,7,9,...,33 (only odd n need be considered)... plus it works for certain infinite sets of n... therefore "clearly" it keeps going forever... BUT none exist when n=35, 47, 53, and 59. So there is no Williamson-form Hadamard with size N=4*35=140. Oops!! The current guess is that the initial 50 years of thinking were exactly wrong and Williamson form almost never works!! Then Fletcher, Gisin & Seberry in 2001 came up with a new matrix form: -1 -1 j j -1 +1 j -j j' j' A B j' -j' B' -A' where j is an n-vector with all entries +1, the prime' denotes matrix transpose, and A and B are nXn circulant matrices. This if you pick A,B right hopefully yields an NxN Hadamard matrix where N=2n+2. Computers and humans have shown that suitable A,B exist showing this works for: n=prime, 2n+1=prime power, n+1=power of 2, n=(P+2)*P=product of twin primes, n=3,5,7,9,...,55,57,59,61. (Only odd n need be considered.) Therefore, it "clearly" keeps working forever. Well, maybe. Given the fate of the Williamson construction, I'm sure not willing to bet the house on this. You can also use this same form (perhaps lopping off the first one or two rows & columns and now allowing even n) to seek maxdet matrices of any size (not necessarily multiple of 4), something Rokicki has done a lot, and it often works pretty well. However, this then definitely fails to reach the max determinant, no matter what A, B you try, for numerous specific sizes N. So it seems every matrix form that has ever been tried, fails to yield maxdet matrices at at least some sizes. Hence my excitement over the Hank*Toep form, which has successfully yielded a maxdet matrix at every size 1,2,...,13 for which I have been able to complete an exhaustive search over all the Hank*Toeps. So far. Maybe the dream will die at size N=14. If it can be shown to survive up to N=20 then I will start to believe it keeps going forever. But showing it survives up to N=20 (or not) is probably beyond what my current computer can do... the entire internet could probably do it (if harnessed...) so I need to write better code.

2 1

[math-fun] Bill Thurston
by Victor Miller 22 Aug '12

22 Aug '12

It saddens me to report the passing of Bill Thurston, yesterday (August 21), who was also a math-funner. Victor http://oumathclub.wordpress.com/2012/08/22/bill-thurston-1946-2012/

1 0

[math-fun] another quantum factoring of 15
by Henry Baker 22 Aug '12

22 Aug '12

FYI -- http://www.edhat.com/site/tidbit.cfm?nid=98156 Composite Number Factoring updated: Aug 20, 2012, 11:00 AM Source: UCSB Computing prime factors may sound like an elementary math problem, but try it with a large number, say one that contains more than 600 digits, and the task becomes enormously challenging and impossibly time-consuming. Now, a group of researchers at UC Santa Barbara has designed and fabricated a quantum processor capable of factoring a composite number -- in this case the number 15 -- into its constituent prime factors, 3 and 5. Although modest compared to a 600-digit number, the achievement represents a milestone on the road map to building a quantum computer capable of factoring much larger numbers, with significant implications for cryptography and cybersecurity. The results are published in the advance online issue of the journal Nature Physics. "Fifteen is a small number, but what's important is we've shown that we can run a version of Peter Shor's prime factoring algorithm on a solid state quantum processor. This is really exciting and has never been done before," said Erik Lucero, the paper's lead author. Now a postdoctoral researcher in experimental quantum computing at IBM, Lucero was a doctoral student in physics at UCSB when the research was conducted and the paper was written. "What is important is that the concepts used in factoring this small number remain the same when factoring much larger numbers," said Andrew Cleland, a professor of physics at UCSB and a collaborator on the experiment. "We just need to scale up the size of this processor to something much larger. This won't be easy, but the path forward is clear." Practical applications motivated the research, according to Lucero, who explained that factoring very large numbers is at the heart of cybersecurity protocols, such as the most common form of encoding, known as RSA encryption. "Anytime you send a secure transmission -- like your credit card information -- you are relying on security that is based on the fact that it's really hard to find the prime factors of large numbers," he said. Using a classical computer and the best-known classical algorithm, factoring something like RSA Laboratory's largest published number -- which contains over 600 decimal digits -- would take longer than the age of the universe, he continued. A quantum computer could reduce this wait time to a few tens of minutes. "A quantum computer can solve this problem faster than a classical computer by about 15 orders of magnitude," said Lucero. "This has widespread effect. A quantum computer will be a game changer in a lot of ways, and certainly with respect to computer security." So, if quantum computing makes RSA encryption no longer secure, what will replace it? The answer, Lucero said, is quantum cryptography. "It's not only harder to break, but it allows you to know if someone has been eavesdropping, or listening in on your transmission. Imagine someone wiretapping your phone, but now, every time that person tries to listen in on your conversation, the audio gets jumbled. With quantum cryptography, if someone tries to extract information, it changes the system, and both the transmitter and the receiver are aware of it." To conduct the research, Lucero and his colleagues designed and fabricated a quantum processor to map the problem of factoring the number 15 onto a purpose- built superconducting quantum circuit. "We chose the number 15 because it is the smallest composite number that satisfies the conditions appropriate to test Shor's algorithm -- it is a product of two prime numbers, and it's not even," he explained. The quantum processor was implemented using a quantum circuit composed of four superconducting phase qubits -- the quantum equivalents of transistors -- and five microwave resonators. The complexity of operating these nine quantum elements required building a control system that allows for precise operation and a significant degree of automation -- a prototype that will facilitate scaling up to larger and more complex circuits. The research represents a significant step toward a scalable quantum architecture while meeting a benchmark for quantum computation, as well as having historical relevance for quantum information and cryptography. "After repeating the experiment 150,000 times, we showed that our quantum processor got the right answer just under half the time" Lucero said. "The best we can expect from Shor's algorithm is to get the right answer exactly 50 percent of the time, so our results were essentially what we'd expect theoretically." The next step, according to Lucero, is to increase the quantum coherence times and go from nine quantum elements to hundreds, then thousands, and on to millions. "Now that we know 15=3x5, we can start thinking about how to factor larger -- dare I say -- more practical numbers," he said. Other UCSB researchers participating in the study include John Martinis, professor of physics; Rami Barends, Yu Chen, Matteo Mariantoni, and Y. Yin, postdoctoral fellows in physics; and physics graduate students Julian Kelly, Anthony Megrant, Peter O'Malley, Daniel Sank, Amit Vainsencher, Jim Wenner, and Ted White.

4 3

Re: [math-fun] Synthesizing functions over finite fields with polynomials
by Henry Baker 22 Aug '12

22 Aug '12

Thanks, Warren, Mike, Neil. I should have known that. Duh to me! At 09:24 AM 8/22/2012, Neil Sloane wrote: >Sure, use a version of Lagrange interpolation. Make a list (a generalized truth table) >of all the values the function takes at all possible arguments. Then write >a monomial for each term and add them up. E.g. if you want the value 7 at x=3, y=4, z=5, >the monomial is Prod_{a!=3}(x-a) Prod_{b!=4} (y-b) Prod_{c!=5) (z-c) 7/d, where d is the appropriate >constant. > >On Wed, Aug 22, 2012 at 12:06 PM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> It appears that all functions over GF(2) can be synthesized using only polynomials: >> >> E.g., >> >> f()=0, f()=1 >> >> f(x)=0, f(x)=1, f(x)=x, f(x)=1+x >> >> not(x)=1+x, and(x,y)=x*y, or(x,y)=x+y+x*y, etc. >> >> Q: Can all functions over _any_ finite field by synthesized using only >> polynomials, and is there a simple synthesis procedure? > >-- >Dear Friends, I have now retired from AT&T. New coordinates: > >Neil J. A. Sloane, President, OEIS Foundation >11 South Adelaide Avenue, Highland Park, NJ 08904, USA >Phone: 732 828 6098; home page: http://NeilSloane.com >Email: njasloane(a)gmail.com

1 0

[math-fun] Synthesizing functions over finite fields with polynomials
by Henry Baker 22 Aug '12

22 Aug '12

It appears that all functions over GF(2) can be synthesized using only polynomials: E.g., f()=0, f()=1 f(x)=0, f(x)=1, f(x)=x, f(x)=1+x not(x)=1+x, and(x,y)=x*y, or(x,y)=x+y+x*y, etc. Q: Can all functions over _any_ finite field by synthesized using only polynomials, and is there a simple synthesis procedure?

3 2

[math-fun] Max determinant via Hadamard product of Toeplitz & Hankel
by Warren Smith 20 Aug '12

20 Aug '12

OK, my searcher has now found matrices of the form Toeplitz*Hankel, where * denotes Hadamard elementwise matrix product (C=A*B means C_ij=A_ij B_ij) where both A and B are sign matrices, which achieve the maximum possible |determinant| among ALL matrices of size N with entries in [-1,1], for EVERY N=1,2,3,...,13 (and N=16). See http://oeis.org/A003433 . I doubt it will be possible for me to resolve the first open case N=14 by brute force, though; I do not have enough compute power. The largest det it has found so far is 68853760, not reaching 77635584. Richard Brent points out that my property of Toeplitz*Hankel doesn't seem to be invariant under Hadamard equivalence. Indeed, this kind of matrix is rather mysterious to me. Are there fast algorithms for doing stuff (like computing determinant) for matrices of this form? I do not know. This kind of matrix arose naturally in an application of mine (which is too much trouble to tell you about right now). They do have the nice property that any sub-block matrix of a Toep*Hank matrix, also is one. Here are example matrices: (Toeplitz specified by stating leftmost column going up, then continuing along top row going right, i.e. "clockwise"; then Hankel specified by stating top row going right, then continuing along rightmost column going down, also "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 4096.00 ++-+++--+---+---+-+-+--------- 9 14336.00 ---+---+--+++-++--+-+-+-+--------- 10 73728.00 ++-++-+++---+--+---------------------- 11 -327680.00 +-+++--++++-+---+------------------------- 12 2985984.00 ---++--+--+++-++--+++----+---+-+-+-+---+------ 13 14929920.00 +--+-+------++--+-+------------------------------- For N=16, you can use a Circulant*Backcirculant (top rows given) 16 4294967296.00 circ=++---++-+++-+++- back=-+-+------------ which is a special case of Toep*Hank. (Note, this special case, and the plain Toeplitz special case, both are inadequate to get max determinant for N=9. I have not yet investigated the other interesting case where we demand the Toep and Hank be the same.) I actually am quite impressed with this. I had suspected my searcher was not going to find a maxdet example for N=12, and indeed had fantasies that maybe I could prove it impossible using the known fact the size-12 Hadamard matrix is unique with amazing symmetry group (Mathieu). However it duly found it after 9 billion random trials. So now, does anybody dare to conjecture that this very restricted matrix form always suffices to reach max determinant? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 2

[math-fun] x^6+y^10=z^15
by Adam P. Goucher 20 Aug '12

20 Aug '12

We start by pondering a general problem. Suppose a,b,c are fixed positive integers. Under what conditions does the equation x^a + y^b = z^c have positive integer solutions? -------- If gcd(a,b,c) >= 3, then there are none by Fermat's last theorem. Certain other cases can be eliminated by infinite descent, such as (a,b,c) = (4,4,2). If two of gcd(a,b), gcd(b,c) and gcd(c,a) are 1, then we can find infinitely many solutions by applying the Sam Cappleman-Lynes technique. For example, for x^3 + y^6 = z^7, we start with a solution to u^3 + v^6 = w and multiply throughout by w^6 to give (uw^2)^3 + (vw)^6 = w^7. If gcd(a,b) = gcd(b,c) = gcd(c,a) = 2, then we have infinitely many solutions by applying the Sam Cappleman-Lynes technique to Pythagorean triplets. For example, x^6 + y^10 = z^14 has infinitely many solutions. -------- This does not cover all equations. Does x^6 + y^10 = z^15 have solutions in the positive integers? Mathematica 8 cannot do it, nor can it even solve the simple x^2 + y^3 = z^4, which has a small solution of (x,y,z) = (50625,3375,450) by SCLT. Sincerely, Adam P. Goucher

2 1

[math-fun] Fractal architecture
by Henry Baker 20 Aug '12

20 Aug '12

FYI -- http://michael-hansmeyer.com/

1 0