September 2013 - mathfun@mailman.xmission.com

[math-fun] AES cryptosystem contenders... a look back
by Warren D Smith 27 Sep '13

27 Sep '13

In 1999-2000 the US government ran a contest to devise AES (advanced encryption standard) the "best" secret key cryptosystem meeting certain criteria. The ultimate winner is called "Rijndael." The selection process involved a vote conducted using approval voting by the participants at the AES2 conference in March 1999. The results were as follows ("candidates" are the 5 AES finalists): Rijndael: 86 positive, 10 negative Serpent: 59 positive, 7 negative Twofish: 31 positive, 21 negative RC6: 23 positive, 37 negative MARS: 13 positive, 84 negative http://en.wikipedia.org/wiki/Advanced_Encryption_Standard_process Plurality voting would have been likely to fail in this use... This is a case where "range voting" might not have been as good as approval, because with range, there might have been "1-sided strategy" -- that is, there were various voters motivated to vote strategically, and the number of such "pre-biased voters" might have varied considerably depending on the candidate. QUESTION: There was an earlier AES round with 15 candidate systems (later narrowed to the above 5). Were any such votes conducted with those 15 as candidates, and if so what were the results? RC Schroeppel was the only all-American entrant in the contest with his "hasty pudding" system. I can see why they rejected it (messy, not well suited to hardware, largely unanalysed), but it did have some nice features, some of which, as far as I know, no other system has yet replicated: * will encrypt a bit string of any length. (Can even do "fractional bit lengths.") * high efficiency on 64-bit machines (albeit there seemed some dispute about that) * had something RCS called the "spice" (which later authors called "tweak") which enabled rapid key changing provided you only changed the spice not the rest of the key. This was not appreciated at the time but later authors seem to have viewed it as quite useful. * a feature HPC did not have but could have had if RCS had been smarter, was constant runtime independent of data, rendering immune to timing attacks. The winner Rijndael involved 256-byte lookup tables and hence is extremely susceptible to cache-status-based timing attacks, a fact not realized+proven until a few years after the winner was selected :(. RC6 and HPC both involved variable-distance word rotations, which on some machines are time-varying, and HPC had data-dependent memory access pattern, another no-no. However, as I said, RCS if he'd been a bit smarter could easily have designed HPC to avoid those no-no's unlike Rijndael which is inherently stuck with them. Also, designs of HPC's ilk also seem do-able in such a way as to get high resistance to power-measurement attacks. So it might be interesting to redo the HPC design in light of that and other criticisms. QUESTION: RCS contended unsuccessfully that 64-bit machines were where it was at, and performance on other machines was largely irrelevant. I suspect he was wrong, in the sense that a lot of computers like mobile phones and smart cards remain below 64-bit width and I suspect there are good reasons for that (battery life) likely to persist despite Moore's law. But... what do you think? What operations would you now recommend such a system be designed to use & avoid to get high portability and good performance? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] minimal dissection of cube into simplices
by rcs＠xmission.com 27 Sep '13

27 Sep '13

This is from Scott Huddleston <scott.huddleston(a)intel.com> --Rich --- What's the minimum number of pieces for dissecting an n-cube into n-simplices? You can always dissect into n! simplices, but that's not minimal for n>2. This was an open problem when I was in grad school (awhile back). Is there always a minimal dissection that includes a maxvol simplex? - Scott

3 2

[math-fun] maxvol simplex in cube
by Warren D Smith 27 Sep '13

27 Sep '13

>Come to think of it, maybe there's always a simplex of maximum volume whose vertices >are cube vertices. >But there are other simplices of maximum volume. E.g., Conv({(0,0), (1,0), (1/2,1)}). >--Dan --true, the "other" ones arise if some "minor" is exactly 0. But there is always a maxvol simplex with only cube vertices.

3 4

[math-fun] 853
by Veit Elser 26 Sep '13

26 Sep '13

Does anyone in this group know where I can download the 853 connected graphs with seven nodes (as edge lists or adjacency matrices)? -Veit

2 1

[math-fun] maxvol simplex in cube
by Warren D Smith 26 Sep '13

26 Sep '13

This is equivalent to the max-determinant problem for sign matrices, a long-well-studied problem. Regular simplices are not maxvol (but are when Hadamard matrices exist... in 3 mod 4 dimensions...) the maxvol simplex always has simplex vertices=cube vertices, as you can prove by contradiction - otherwise the matrix row that was not all +1 and -1 could be altered to make it all +1 and -1 without decreasing the |determinant|. The maxvol regular simplex, however, need not obey this property.

2 2

[math-fun] Maxvol regular n-simplex inscribed in an n-cube, and "constant weight Hadamard" conjecture
by Warren D Smith 25 Sep '13

25 Sep '13

Attempting to generalize Fred Lunnon's construction of the apparently-largest volume regular 4-simplex inside a unit-side 4-cube with edge length=sqrt(2)... from D=4 dimensions to dimension D = arbitrary multiples of 4.... achieving edge length = sqrt(D/2)...: In 8 dimensions, choose 8 vertices each of shape (1,1,1,0,0,0,0,0) according to a constant-weight code with Hamming distance=4, for example the cyclic cyc(11010000), then add a 9th vertex at (t,t,t,t,t,t,t,t) where t = (sqrt(19) + 1)/6 = 0.8931498242 achieving edge length >= 2 = sqrt(4). In 12 dimensions, choose 12 vertices each of shape (1,1,1,1,1,0,0,0,0,0,0,0) according to a cyclic constant-weight code with Hamming distance=6, specifically cyc(110011000010), then add a 13th vertex at (t,t,t,t,t,t,t,t,t,t,t,t) where t = (sqrt(37) + 5)/12 = 0.9235635442 achieving edge length = sqrt(6). In 16 dimensions, choose 16 vertices each of weight=6 according to a cyclic constant-weight code with Hamming distance=8, cyc(1001000000010111) then add a 17th vertex at (t,t,t,...,t,t,t,t,t,t,t,t,t) where t = (sqrt(17) + 3)/18 = 0.8903882032 achieving edge length = sqrt(8) OR alternatively, choose 16 vertices each of weight=7 according to a cyclic constant-weight code with Hamming distance=8, cyc(1101011000001100 then add a 17th vertex at (t,t...,t,t,t,t,t,t,t,t,t,t) where t = (sqrt(65) + 7)/16 = 0.9413911092 also achieving edge length = sqrt(8). In 20 dimensions, choose 20 vertices each of weight=9 according to a constant-weight code with Hamming distance=10, for example the cyclic cyc(00010001001010011111) then add a 21st vertex at (t,t,t,t,t,...,t,t,t) where t = (sqrt(101) + 9)/20 = 0.9524937810 achieving edge length >= sqrt(10). In 24 dimensions, achieve edge length>= sqrt(12) similarly using weight=10 or 11 (both work). In 28 dimensions, achieve edge length>= sqrt(14) similarly using weight=12 or 13. In 32 dimensions, achieve edge length>= 4 = sqrt(16) similarly using weight=14 or 15. CONJECTURALLY this keeps working forever because a constant weight code of weight=(N-2)/2 and length=N always exists when N is divisible by 4 (here "weight"=number of 1-bits in the N-bit binary word), having Hamming distance >= N/2. Actually, this is equivalent to the conjecture that when N is divisible by 4, an NxN Hadamard matrix always exists having (N-2)/2 "plus ones" in each row (rest minus ones). That probably is a well-studied conjecture, but my mind is currently blanking on that, would need to consult literature. This whole construction seems to be rather near optimal in the sense that edge length sqrt(D/2) only falls short of the optimal sqrt((D+1)/2), which is what is achieved using Hadamard matrix in the case where D mod 4=3, by a little. Hence the D-volume achieved falls short of the optimum "Hadamard bound" by only a factor (1+1/D)^(D/2), which is upper bounded by the constant limit (1+1/D)^(D/2) = exp(1/2) = 1.648721271 at most.

2 2

[math-fun] maxvol polyhedra
by Warren D Smith 25 Sep '13

25 Sep '13

>Allan Wechsler acwacw at gmail.com >I think that in either model of hyperbolic space, any nontrivial polyhedron >with its vertices on the outer sphere has infinite volume. --No! Always has finite volume! To solve in 2 dimensions, the answer is a regular N-gon. The hyperbolic area of an N-gon with all vertices "at infinity" is the same as the area of N-2 triangles with vertices at infinity (glue them together to make N-gon) and the area of a triangle with all angles=0 is pi (since angle deficit = area). Hence maximal hyperbolic area of N-gon is (N-2)*pi. In D dimensional hyperbolic space with N=D+1 answer is always a regular simplex (a result proven by Haagerup & somebody). Albeit note when D=2 every triangle at infinity is congruent to every other so the word "regular" has no meaning in that case. But when D=3, not every tetrahedron with vertices at infinity is congruent to every other... It is quite interesting to find out the maxvol polytopes in hyperbolic D-space... and the volumes are always finite. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Maxvol regular n-simplex inscribed in an n-cube, n mod 4=1 and 2 cases
by Warren D Smith 25 Sep '13

25 Sep '13

Now attempting to work on the cases where the dimension D obeys D mod 4=2 or D mod 4=1. If D mod 4=2 and 2D-2 is the sum of two squares, e.g. D=2: 2D-2=2=1^1+1^1, D=6: 2D-2=10=3^2+1^2, D=10: 2D-2=18=3^2+3^2, D=14: 2D-2=26=5^2+1^2, D=18: 2D-2=34=5^2+3^2, but not D=22: 2D-2=42=you lose! it has been conjectured that there always exists a DxD sign matrix of the form W X Y Z where each block is (D/2)x(D/2) and each block has constant row sums (and constant column sums) and any two different rows of the whole matrix have either dot product = 0 or dot product = 2, and always 0 if the two rows being dotted lie in different halves. Any such configuration achieves maximum possible determinant ("Ehlich-Wojtas bound for Hadamard maximum determinant problem"). Now, any Ehlich-Wojtas configuration in D+1 dimensions (after "normalizing" so the first column is all -1s then omitting it) corresponds to a slightly-non-regular simplex inscribed in a D-cube, having only two edge lengths. If the larger edge lengths are shrunk to equal the smaller, then I presume the resulting shrunk regular simplex still is embedabble in the cube because it is embeddable in its unshrunk version? If so, the result would be CONJECTURE: If D mod 4=1 and 2D is a sum of two squares, then a regular simplex with edge length = sqrt(D/2) will fit inside a unit-side D-cube. EXAMPLE: D=5: edge length = sqrt(5/2) = 1.5811388 which would improve versus Lunnon's 1.511173070871355. And again this would be optimal to within a constant factor for all applicable D. The construction I gave earlier for D a multiple of 4, (using constant weight codes) also can be done when D mod 4 = 2 and shows that when D=6,10,14,18,22,26,30 edge length >= sqrt((D-2)/2) is achieved using a constant weight code with weight= 1, 3, 4, 6, 8, 9, 11 respectively [and Hamming distance = (D-2)/2]. It is not optimal when D=6, because Lunnon achieved the longer edge length sqrt(5/2). But anyway this all seems enough to make us believe the CONJECTURE: In D dimensions, it is always possible to inscribe a regular D-simplex in a D-cube of unit side, with D-simplex volume exceeding a positive constant times the "Hadamard" volume arising from simplex edge length = sqrt((D+1)/2). Another construction could be based on "bi-weight codes" which are N-bit words with A 1-bits in the first M bits, and B 1-bits in the last N-M bits, and then add an extra vertex or two of the form (x,x,x,x,...x,y,y,y,...,y). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] maxvol polyhedra
by Warren D Smith 25 Sep '13

25 Sep '13

a related but more interesting/flexible question is: what is the maximum volume of the convex hull of N points on a unit sphere in D dimensions? Also of interest, same question, but "hyperbolic volume" not euclidean volume. That is the interior of the unit sphere in D-dimensions, can be regarded as hyperbolic D-space (nonEuclidean geometry) there is such a a model where straight Euclidean lines correspond to hyperbolic geodesics. Also, the Poincare disk model has hyperbolic geodesics corresponding to Euclidean circular arcs (perpendicular to the unit sphere where touch it) in which case the "convex hull" faces are no longer pieces of euclidean hyperplanes but rather euclidean sphere pieces. Of course, the maxvol configurations are non-unique via rotation, but the hyperbolic maxvol configurations have an even larger nonuniqueness than that, because any isometry of hyperbolic space can be used, which includes "boosts" (the hyperbolic analogue of a translation) as well as "rotations."

2 1

[math-fun] statistical bias on plates
by Simon Plouffe 23 Sep '13

23 Sep '13

Hello, I live in france now and they have a plate numbering system that puzzles me a little bit. Here are some explanations about a new system : http://en.wikipedia.org/wiki/Vehicle_registration_plates_of_France roughly, the plates are sequenced with letters and digits: in the following way. AA 123 XX where letters are a-z except I O and U for various reasons. There are some specific restrictions on some specific 2 letters combination , but we can consider this factor being negligible. So, they began this numbering scheme in march 2009. Beginnin with AA, for now the letters are at CY, So to make it simple there are 2 types of plates you can encounter by random. 1) the current numbering system 2) the old system + the foreigns plate that we do not count. So , for my car the first letters are CG this means there is about 1 chance out of 72 (rejecting the plates of type 2). that I encounter a car with these same letters. And consequently, there is 1 chance in 72 that I encounter CW or BT etc. Since there are 24 letters for each and they covered 3 letters so far then there are 72 combinations. BUT the problem is the following, this 1 chance out of 72 does not follow statistical distribution at all. , like this morning I encountered 5 vehicles with the prefix CW and I really can't explain why, I calculated that in one day I could see and analyse maybe 100 cars with plate numbers but each day the basic statistics does not add up at all . I am scratching my head and I cannot see why there is a strong statistical bias in the distribution of those 2 letter prefixes. Can anybody ever encountered such bias. By the way, this method of analysis was used during WWII , they where doing reverse engineering on the serial numbers found on tanks and planes to know how many the enemy might have, , they eventualy changed to a more cryptic numbering system. Best regards, Simon Plouffe

5 5