Assuming IEEE 754 64-bit floats, and that the calculations are set up to have no cancellation (no intermediate numbers above the total), it's accurate below 2^53. But maybe only some intermediate smaller number is calculated inexactly, I don't know. Charles Greathouse Analyst/Programmer Case Western Reserve University On Sun, Aug 26, 2012 at 8:35 PM, Neil Sloane <njasloane@gmail.com> wrote:
Warren, it is bit hard to tell from your message which of your terms you are sure of (and I don't think you gave the terms of A003112 that you found), so could you please update all those sequences (with the terms that you are sure of)? Thanks! Neil
On Sun, Aug 26, 2012 at 7:30 PM, Warren Smith <warren.wds@gmail.com> wrote:
From: Joerg Arndt <arndt@jjj.de> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Maximum |determinant| for NxN circulant sign matrix? Message-ID: <20120826064811.GA3956@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 +-+-+-+-+-+-+-+-+-+++-+-+++++-+--+--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- 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@gmail.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun