[math-fun] imminent world shortage of Hadamard matrices?
The Hadamard matrix conjecture holds that such matrices exist for all orders that are divisible by 4. After surveying what’s been done on the classification/enumeration of Hadamard matrices (e.g. http://neilsloane.com/hadamard/) I’ve felt that what’s humbling about the conjecture is that we lack the knowledge to prove the existence of even a single Hadamard (at each possible order) when the evidence points to a very rapid growth in their number. Now I’m not so sure. Let x = log_2(N), N = order of Hadamard (a multiple of 4), and y = (1/N^2)log_2(num(N)), where num(N) is the number of Hadamard matrices of order N. Sequence A206711 gives num(N) for N = 1, … , 32. If you plot y vs. x you get a very straight line: y = 0.78785 - 0.09458 x. Taking this literally, there should be a maximum in the number of Hadamard matrices at order N = 196, and beyond that the number plummets, vanishing at around N = 322. The available constructions (beyond this number) would then represent isolated points. -Veit
Years ago Paul Leopardi told me (to my surprise) "I think the Hadamard matrix conjecture is wrong". Here is another such phenomenon (a type of object where the apparent initial growth is misleading): Costas arrays See https://oeis.org/A001441 and other sequences found via https://oeis.org/search?q=name%3A%22costas+array%22&sort=&language=&go=Searc... Best regards, jj * Veit Elser <ve10@cornell.edu> [Sep 07. 2016 18:02]:
The Hadamard matrix conjecture holds that such matrices exist for all orders that are divisible by 4. After surveying what’s been done on the classification/enumeration of Hadamard matrices (e.g. http://neilsloane.com/hadamard/) I’ve felt that what’s humbling about the conjecture is that we lack the knowledge to prove the existence of even a single Hadamard (at each possible order) when the evidence points to a very rapid growth in their number. Now I’m not so sure.
Let x = log_2(N), N = order of Hadamard (a multiple of 4), and y = (1/N^2)log_2(num(N)), where num(N) is the number of Hadamard matrices of order N. Sequence A206711 gives num(N) for N = 1, … , 32. If you plot y vs. x you get a very straight line: y = 0.78785 - 0.09458 x. Taking this literally, there should be a maximum in the number of Hadamard matrices at order N = 196, and beyond that the number plummets, vanishing at around N = 322. The available constructions (beyond this number) would then represent isolated points.
-Veit _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Wow; what an intriguing observation! Jim Propp On Wed, Sep 7, 2016 at 10:57 AM, Veit Elser <ve10@cornell.edu> wrote:
The Hadamard matrix conjecture holds that such matrices exist for all orders that are divisible by 4. After surveying what’s been done on the classification/enumeration of Hadamard matrices (e.g. http://neilsloane.com/hadamard/) I’ve felt that what’s humbling about the conjecture is that we lack the knowledge to prove the existence of even a single Hadamard (at each possible order) when the evidence points to a very rapid growth in their number. Now I’m not so sure.
Let x = log_2(N), N = order of Hadamard (a multiple of 4), and y = (1/N^2)log_2(num(N)), where num(N) is the number of Hadamard matrices of order N. Sequence A206711 gives num(N) for N = 1, … , 32. If you plot y vs. x you get a very straight line: y = 0.78785 - 0.09458 x. Taking this literally, there should be a maximum in the number of Hadamard matrices at order N = 196, and beyond that the number plummets, vanishing at around N = 322. The available constructions (beyond this number) would then represent isolated points.
-Veit _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Very interesting (as J.P. wrote). It may not help anything, but I like to think of an Hadamard matrix geometrically. Consider the n-cube as [-1,1]^n. Then the rows (or columns) of an order-n Hadamard matrix are n vertices of the n-cube whose directions from the origin are perpendicular. —Dan
On Sep 7, 2016, at 7:57 AM, Veit Elser <ve10@cornell.edu> wrote:
The Hadamard matrix conjecture holds that such matrices exist for all orders that are divisible by 4. After surveying what’s been done on the classification/enumeration of Hadamard matrices (e.g. http://neilsloane.com/hadamard/) I’ve felt that what’s humbling about the conjecture is that we lack the knowledge to prove the existence of even a single Hadamard (at each possible order) when the evidence points to a very rapid growth in their number. Now I’m not so sure.
Let x = log_2(N), N = order of Hadamard (a multiple of 4), and y = (1/N^2)log_2(num(N)), where num(N) is the number of Hadamard matrices of order N. Sequence A206711 gives num(N) for N = 1, … , 32. If you plot y vs. x you get a very straight line: y = 0.78785 - 0.09458 x. Taking this literally, there should be a maximum in the number of Hadamard matrices at order N = 196, and beyond that the number plummets, vanishing at around N = 322. The available constructions (beyond this number) would then represent isolated points.
In about a hundred seconds of assiduous research on the Internet, I wasn't able to find any accounts of people searching for an order-668 example. Is nobody looking? Or are the searchers being secretive, and not sharing search strategies in the hopes of being first? Or (most likely) is there an active, collegial search going on, and I simply failed to find it? I can think of a bunch of strategies involving hill-climbing and annealing-like processes. I'm guessing these all fail spectacularly. On Wed, Sep 7, 2016 at 10:14 PM, Dan Asimov <dasimov@earthlink.net> wrote: > Very interesting (as J.P. wrote). > > It may not help anything, but I like to think of an Hadamard matrix > geometrically. > > Consider the n-cube as [-1,1]^n. > > Then the rows (or columns) of an order-n Hadamard matrix are n vertices of > the n-cube whose directions from the origin are perpendicular. > > —Dan > > > > On Sep 7, 2016, at 7:57 AM, Veit Elser <ve10@cornell.edu> wrote: > > > > The Hadamard matrix conjecture holds that such matrices exist for all > orders that are divisible by 4. After surveying what’s been done on the > classification/enumeration of Hadamard matrices (e.g. > http://neilsloane.com/hadamard/) I’ve felt that what’s humbling about the > conjecture is that we lack the knowledge to prove the existence of even a > single Hadamard (at each possible order) when the evidence points to a very > rapid growth in their number. Now I’m not so sure. > > > > Let x = log_2(N), N = order of Hadamard (a multiple of 4), and y = > (1/N^2)log_2(num(N)), where num(N) is the number of Hadamard matrices of > order N. Sequence A206711 gives num(N) for N = 1, … , 32. If you plot y vs. > x you get a very straight line: y = 0.78785 - 0.09458 x. Taking this > literally, there should be a maximum in the number of Hadamard matrices at > order N = 196, and beyond that the number plummets, vanishing at around N = > 322. The available constructions (beyond this number) would then represent > isolated points. > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
Not specifically about n = 668, but you may want to contact Richard Brent (he is a very friendly guy and knows quite a bit about this topic). Our WDS has (IIRC) published something with Brent about Hadamard matrices. Best regards, jj * Allan Wechsler <acwacw@gmail.com> [Sep 08. 2016 19:05]: > In about a hundred seconds of assiduous research on the Internet, I wasn't > able to find any accounts of people searching for an order-668 example. Is > nobody looking? Or are the searchers being secretive, and not sharing > search strategies in the hopes of being first? Or (most likely) is there an > active, collegial search going on, and I simply failed to find it? > > I can think of a bunch of strategies involving hill-climbing and > annealing-like processes. I'm guessing these all fail spectacularly. > > On Wed, Sep 7, 2016 at 10:14 PM, Dan Asimov <dasimov@earthlink.net> wrote: > > > Very interesting (as J.P. wrote). > > > > It may not help anything, but I like to think of an Hadamard matrix > > geometrically. > > > > Consider the n-cube as [-1,1]^n. > > > > Then the rows (or columns) of an order-n Hadamard matrix are n vertices of > > the n-cube whose directions from the origin are perpendicular. > > > > —Dan > > > > > > > On Sep 7, 2016, at 7:57 AM, Veit Elser <ve10@cornell.edu> wrote: > > > > > > The Hadamard matrix conjecture holds that such matrices exist for all > > orders that are divisible by 4. After surveying what’s been done on the > > classification/enumeration of Hadamard matrices (e.g. > > http://neilsloane.com/hadamard/) I’ve felt that what’s humbling about the > > conjecture is that we lack the knowledge to prove the existence of even a > > single Hadamard (at each possible order) when the evidence points to a very > > rapid growth in their number. Now I’m not so sure. > > > > > > Let x = log_2(N), N = order of Hadamard (a multiple of 4), and y = > > (1/N^2)log_2(num(N)), where num(N) is the number of Hadamard matrices of > > order N. Sequence A206711 gives num(N) for N = 1, … , 32. If you plot y vs. > > x you get a very straight line: y = 0.78785 - 0.09458 x. Taking this > > literally, there should be a maximum in the number of Hadamard matrices at > > order N = 196, and beyond that the number plummets, vanishing at around N = > > 322. The available constructions (beyond this number) would then represent > > isolated points. > > > > _______________________________________________ > > math-fun mailing list > > math-fun@mailman.xmission.com > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Allan Wechsler -
Dan Asimov -
James Propp -
Joerg Arndt -
Veit Elser