May 2014 - mathfun@mailman.xmission.com

[math-fun] Closed form question
by David Wilson 20 May '14

20 May '14

If you considered f(n, x) = SUM(n = 0..inf, 1 / (x^n + 1)) to be a closed form, could we find a closed form for f(a, b) = SUM(n = 0..inf, 1 / (a^n + b^n))?

1 0

[math-fun] Discrete Logarithm Problem Partly Solved -- Time To Drop Some Crypto Methods?
by Ray Tayek 20 May '14

20 May '14

http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-… <http://beta.slashdot.org/%7ESoulskill>Soulskill posted yesterday | from the now-let's-be-paranoid-that-the-NSA-solved-it-years-ago dept. <http://beta.slashdot.org/index2.pl?fhfilter=math> Math <http://beta.slashdot.org/index2.pl?fhfilter=math> <http://science-beta.slashdot.org/story/14/05/16/2339204/discrete-logarithm-…>97 An anonymous reader points out this Science Daily report: "Researchers ... have solved one aspect of the <http://modular.math.washington.edu/edu/124/lectures/lecture8/html/node5.html>discrete logarithm problem. This is considered to be one of the 'holy grails' of algorithmic number theory, on which the security of many cryptographic systems used today is based. They have <http://www.sciencedaily.com/releases/2014/05/140515163739.htm>devised a new algorithm that calls into question the security of one variant of this problem, which has been closely studied since 1976. The result ... discredits several cryptographic systems that until now were assumed to provide sufficient security safeguards. Although this work is still theoretical, it is likely to have repercussions especially on the cryptographic applications of smart cards, RFID chips , etc." --- co-chair http://ocjug.org/

7 8

Re: [math-fun] Stupid Cayley-Hamilton question
by Henry Baker 20 May '14

20 May '14

I agree with the first part "it is necessary and sufficient that M(B,x) divide C(A,x)", but not the second part "the multiplicity in B cannot exceed the multiplicity in A". See this Maxima script: Maxima 5.28.0-2 http://maxima.sourceforge.net using Lisp GNU Common Lisp (GCL) GCL 2.6.8 (a.k.a. GCL) Distributed under the GNU Public License. See the file COPYING. Dedicated to the memory of William Schelter. The function bug_report() provides bug reporting information. (%i1) A:diag_matrix(a,b,c); [ a 0 0 ] [ ] (%o1) [ 0 b 0 ] [ ] [ 0 0 c ] (%i2) B:diag_matrix(a,b,b); [ a 0 0 ] [ ] (%o2) [ 0 b 0 ] [ ] [ 0 0 b ] (%i3) Ap:charpoly(A,z),expand; 3 2 2 2 (%o3) - z + c z + b z + a z - b c z - a c z - a b z + a b c (%i4) Bp:charpoly(B,z),expand; 3 2 2 2 2 (%o4) - z + 2 b z + a z - b z - 2 a b z + a b (%i5) -B.B.B+(a+b+c)*B.B-(a*b+a*c+b*c)*B+a*b*c*ident(3),expand; [ 0 0 0 ] [ ] (%o5) [ 0 0 0 ] [ ] [ 0 0 0 ] (%i6) At 08:15 AM 5/20/2014, Eugene Salamin wrote: >Let C(A,x) and M(A,x) be the characteristic and minimal polynomials of A. Matrix B satisfies M(B,x) = 0. In order that B also satisfy C(A,x) = 0, it is necessary and sufficient that M(B,x) divide C(A,x). This requires that each eigenvalue of B must be an eigenvalue of A, and the multiplicity in B cannot exceed the multiplicity in A. > > -- Gene >>________________________________ >> From: Henry Baker <hbaker1(a)pipeline.com> >>To: math-fun(a)mailman.xmission.com >>Sent: Tuesday, May 20, 2014 7:46 AM >>Subject: [math-fun] Stupid Cayley-Hamilton question >> >> >>Cayley-Hamilton tells us that a square matrix A >>satisfies its own characteristic polynomial. >> >>Any square B with a subset of A's eigenvalues >>should also satisfy A's characteristic polynomial. >>(Note that B could be larger or smaller than A, >>and may have repeated eigenvalues.) >> >>Are there any other B's that would satisfy A's >>characteristic polynomial ?

2 1

[math-fun] Stupid Cayley-Hamilton question
by Henry Baker 20 May '14

20 May '14

Cayley-Hamilton tells us that a square matrix A satisfies its own characteristic polynomial. Any square B with a subset of A's eigenvalues should also satisfy A's characteristic polynomial. (Note that B could be larger or smaller than A, and may have repeated eigenvalues.) Are there any other B's that would satisfy A's characteristic polynomial ?

2 1

[math-fun] Penrose local isomorphism theorem
by James Propp 20 May '14

20 May '14

Can anyone provide a reference for Penrose's "local isomorphism theorem", asserting that every Penrose tiling looks like every other? I seem to recall hearing a strong version of this stated once, to the effect that if you have a pattern of diameter n in one Penrose tiling, and you look for that pattern in a second Penrose tiling, you won't have to travel further than distance 2n. Jim Propp

5 4

[math-fun] discrete log problem advance -- the source
by Warren D Smith 18 May '14

18 May '14

Going by the abstract alone, this seems to me to be theoretically devastating, and should in my view kill all DLP cryptosystems over fields with small characteristic. "Kill" meaning nobody should want to use them anymore. --- http://link.springer.com/chapter/10.1007%2F978-3-642-55220-5_1 Advances in Cryptology – EUROCRYPT 2014 Lecture Notes in Computer Science Volume 8441, 2014, pp 1-16 A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thome ABSTRACT The difficulty of computing discrete logarithms in fields GF(q^k) depends on the relative sizes of k and q. Until recently all the cases had a sub-exponential complexity of type L(1/3), similar to the factorization problem. In 2013, Joux designed a new algorithm with a complexity of L(1/4 + epsilon) in small characteristic. In the same spirit, we propose in this article another heuristic algorithm that provides a quasi-polynomial complexity when q is of size at most comparable with k. By quasi-polynomial, we mean a runtime of N^O(logN) where N is the bit-size of the input... Complexity results in this article rely on heuristics which have been checked experimentally.

1 0

[math-fun] Answers to recent questions
by Warren D Smith 18 May '14

18 May '14

1. yes you can get n-hole tori as quotients of hyperbolic plane, discussed in Thurston's book. You just use a regular hyperbolic N-gon with the correct N and the correct side-identifications. 2. that discrete log crypto development sounds important. It in fact was a highly discussed direction to use fields of order 2^k for k large, allegedly for efficiency reasons; the other main direction was p^1 for prime p large. Presumably we should now discard the first of these approaches.

1 0

[math-fun] melancholia in math: black holes?
by Warren D Smith 18 May '14

18 May '14

sounded pretty silly -- magic squares and black holes. Durer probably rolling in his grave. Which leads me to my question -- just what DID Klainerman say about black holes? Is somebody seriously disputing their existence, I thought there was enough experimental evidence that it was hard to do so anymore?

1 0

[math-fun] Quotients of hyperbolic planes that give n-holed toruses?
by Mike Stay 18 May '14

18 May '14

Klein's quartic can be formed by taking a quotient of the {7,3} tiling of the hyperbolic plane, with 24 heptagons in all. The result is a 3-holed torus. Is there a general way to get n-holed toruses (n>2) from quotients of the hyperbolic plane? -- Mike Stay - metaweta(a)gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com

2 1

[math-fun] New thoughts on sorting algorithms
by Warren D Smith 18 May '14

18 May '14

In the old days, one would analyse a sorting algorithm to try to understand C(N) and M(N) and S(N): the number of element-comparisons, number of element-moves, and number of extra storage locations, respectively required to sort an array of N elements. One tried to make C(N) and M(N) approach the theoretical lower bounds of lg(N!) =approx= N*lg(N) - 1.443*N, and N, respectively, while keeping S(N)=o(N), which I will call an "in-place" sorting method, as opposed to method with order N extra storage needs, such as merge sort. But in the modern era, this is inadequate. It seems to me we should instead consider: B(N) = number of compares used for branching and hence likely to led to misprediction of the branch, causing computer's pipelines to stall and have to be cleared out. C(N) = number of compares used in non-branching manners, i.e. such that no prediction is needed and getting prediction wrong does not matter R0(N) and R1(N) = number of reads of array elements W0(N) and W1(N) = number of writes where the 0 and 1 refer to within and outside of "cache." Finally, there also is additional bookkeeping work. The point is the branch-mispredicted comparisons can cost a lot more than ordinary comparisons. (How much this matters depends how expensive a comparison is; if sorting plain 1-word integers it matters a lot; if sorting "a collection of chess positions" it matters little.) And inside-cache accesses cost a lot less than outside cache. All this changes one's perspective considerably. If we restrict attention to in-place, fairly simply-describable sort methods with O(N*lgN) runtime, then in the old days the main competitors were quicksort, heapsort, shellsort, and sorting networks. Here I am being generous by pretending shellsort has O(NlgN) runtime. The usual old claim was quicksort was the best, albeit with shellsort the best for small enough arrays. This is due to the simplicity of their inner loops; and quicksort will approach N*lgN comparisons (optimal leading term) if good pivot elements are used, although it will use order N*lgN moves, and you have to be careful about the details otherwise quadratic runtime will happen with certain not-too-implausible inputs. In the modern era, this thinking may change. Quicksort: good cache behavior, will only perform about const/L fraction out-of-cache moves and compares, where L is the cardinality of a cache line. This is optimal. Poor branching behavior in the sense that almost every compare is branched. Heapsort: Excellent branching behavior in the sense that you can code it in such a way that there are only O(N) branched comparisons while the remaining O(N*lgN) compares can be coded in a manner where misprediction does not matter. O(N*lgN) compares and branches even for worst case. Cache behavior is pessimally bad; almost all the accesses will be out of cache asymptotically. Shellsort: Assuming increment sequence which increases, very roughly, exponentially, the cache behavior is pessimally bad; like heapsort almost all the accesses will be out of cache asymptotically. Further, the compares are almost all branching, which also is pessimally bad. However, if instead of coding shellsort using "insertion sort with size-h-strides" you re-coded it using "repeatedly find the max" sort using h-strides, this might allow you to code it in a way in which almost all the compares were non-branching. Repeatedly finding the max and moving it to the top of the array (array keeps shrinking) is a better quadratic-time sort than insertion sort in the sense that the comparisons can be done nonbranching. On the other hand, in insertion sort you can accurately predict comparisons almost always (i.e. as you walk linearly down the sorted part of the array, asking "should I stop now" the answer is almost always "no"). If you take that view then insertion sort runs in order N^2 steps but only O(N) mispredicted branches. In that view, shellsort is already coded fine and does not need recoding. Shellsort's worst and average case runtimes both are hard to analyse. Sorting networks: a sorting network based on "sort2 modules" is optimal in the sense that every compare+move can be done using "conditional move" with no branching at all ever. The entire program is "data oblivious". Its cache behavior and runtime depend on the network used but probably the cache behavior is going to be bad. CONCLUSION: these theoretical thoughts predict 1. that heapsort should be superior to quicksort if N is small enough that going outside the cache is not an issue. I have done experiments, following up on earlier experiments by Paul Hsieh, which seem to confirm this prediction; my heapsort is the fastest among {heap, shell, quick} for all array sizes 30-3000 tried, sorting either 32-bit integers, or 64-bit reals. To achieve this you have to code heapsort in a way that avoids branching. However, it is possible one could code quicksort better than Hsieh and I did... has anybody got some good quicksort codes in C? 2. that for large N, quicksort will win due to better cache behavior versus the others, but its branching behavior sucks. This suggests seeking a way to recode quicksort to reduce the number of branching compares and branch mispredictions. Vladimir Yaroslavskiy http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf recently invented "dual pivot quicksort" which employs two pivot elements and partitioning of array into three parts. He and other testers found this was 10% faster than plain quicksort. Why? It is plainly stupid by the old view in the sense it uses more comparisons to sort. Shrinu Kushagra, Alejandro Lopez-Ortiz, J. Ian Munro, Aurick Qiao http://epubs.siam.org/doi/abs/10.1137/1.9781611973198.6 went further than Yaroslavskiy devising a 3-pivot quicksort partitioning array into 4 parts. This was found to be faster than the dual-pivot and single-pivot quicksort variants tried. But both these new kinds of quicksort use MORE comparisons and MORE moves than classic quicksort (beating it on runtime for sorting plain 1-words integers, though)! Why? Well, first of all, it seems that, although I said quicksort was excellent about the cache with only a fraction c/L of accesses out-of-cache, c=constant, L=cache line size, these new algorithms are even more excellent about the cache in the sense they achieve smaller c. So the new methods would be predicted to win unless we have very expensive comparison operations. Also, which those authors did not perceive, you can code it in a way which causes the comparisons to be more predictable than in single-pivot quicksort, precisely *because* they are "unbalanced" i.e. poor in an info-theoretic sense. E.g. suppose we had a "good" sorting method in which each comparison was 50:50, you had no idea what the result was going to be. You get 1 bit of info from each compare but it costs you 0.5 mispredicts per compare -- which if we crudely model predicted branches as "free," means your cost is 0.5 per bit. Now compare with a "bad" sorting method in which the compares are 90:10 predictable. Now you get only 0.1*lg(10)+0.9*lg(10/9) = 0.469 bits of info per compare, but it only costs you 0.1 mispredicts. Hence the fact you have to perform 2.13 times the number of comparisons to extract the same amount of information, is more than paid for (in this crude model) by the fact you are paying 5 times less per comparison! That gets even more dramatic with a 127:1 predictable comparison, which gives you only about 1/16 of a bit but costs only 1/128. "Bad" sorting methods are actually better than "good" sorting methods, in this sense! Very bizarre! To quantify that insight, suppose a mispredicted compare costs you B while a predicted one costs 1, where B>1. Your best strategy is to employ comparisons with R:1 ratio of right:wrong predictions where R>1 (as opposed to 1:1 for a "perfect" comparison). The optimum value of R is the one which minimizes (B+R) / (log(R+1)+R*log(1+1/R)) which is approximately the same thing as minimizing (B+R) / (1 + log(R+1)) If B-->infinity then the optimum R also -->infinity. But for fixed B such as B=10, you get finite R>1, and the best R approximately obeys R=B/ln(B). This is a quite large bias. 3. A new algorithm for in-place array sorting using (2+o(1))*N*lgN compares and (13+o(1))*N moves in worst case, both optimal up to constant factors [shell, heap, networks, and quick all used order N*lgN moves or more; mergesort used O(N) moves but was not in-place] is here: GIANNI FRANCESCHINI & VILIAM GEFFERT: An In-Place Sorting with O(n log n) Comparisons and O(n) Moves, JACM 52,4 (2005) 515-537 I now am going to describe a vastly simpler sorting method than theirs which also achieves O(NlogN) compares worst case, O(N) moves worst case, both optimal, but unlike them I allow myself o(N) bits of auxiliary storage, note the lowercase o. They had to be more complicated since they only allowed themselves o(1) words of extra storage, which is about O(logN) reckoned in bits. An approximately evenly-spaced sorted subsample S of the N elements, containing M elements, is used. Basically, a random sample would work, except where it does not, and where it does not you can "split" the long gaps approximately in half, using linear-time median-finding algorithms, until it does. Also the other kind of flaw in a random sample, too-close guys, can be fixed by discarding one of the guys. Non-even-spacing flaws in this sample can be dynamically repaired in this way as we proceed. In practice I would just use a "slightly improved random sample" since with optimal M it is extremely unlikely any fixes will be needed; but if you insist on genuine worst-case performance bounds determinstically, then you would need to worry about repairs. Phase I: If we are willing to store o(N) extra bits we can now using binary search mentally insert each of the N elements into the correct post office box (boxes delineated by the samples) without actually moving anything, purely keeping track of the COUNTS in each box. Then with the counts known and stored in the auxialiary o(N) bits (note the lowercase o) we can now make a second mass of binary searches now, with actual moves, since we now know where to move them. That works provided M=o(N/logN). (If M were larger than that, then the auxiliary storage for the counts would be too large.) As a result we now have an almost-sorted array of N elements, where each element is at most distance O(N/M) away from correct final destination and every element in correct "post office box" where there are M+1 boxes with M known "walls" (the sample S, now already in final locations). Phase II: We now sort each box in succession using, for example, list-merge-sort or array-merge-sort. The auxiliary storage each merge-sort needs is at most O(N/M) pointers, each O(logN) bits wide, if we use list merge. Or at most O(N/M) extra array elements, if we use array merge. So this works provided logN=o(M). Other methods than merge sort could also be used, anything with linear move-count and O(NlogN) compare-count will do, where linear or even somewhat superlinear auxiliary storage is permitted. I'm cheating here because array-merge does order NlogN moves in sorting N items. List merge really does use only O(N) moves, but uses order NlogN pointer-rewrites, which it is kind of cheating to claim are "not moves." Yes, they are not item-moves; but they are pointer-moves. Another approach is to use heapsort with a large radix (tree branching factor) instead of radix=2. That is what Franceschini and Geffert did. This kind of heapsort has fewer moves but more comparisons. Specifically with radix=R, 1<R<N, heapsort will employ order N*log(N)/log(R) moves and order R*N*log(N)/log(R) compares to sort N items. Using heapsort also has the minor extra advantage of not requiring auxiliary storage. If you use mergesort, the best tradeoff for my auxiliary memory needs seems to be making M be of order sqrt(N). Then you use O(sqrt(N)) words of auxiliary storage, each O(logN) bits wide. Then I claim this sorting method can then be made to employ at most (2+o(1))*N*lgN comparisons, expected, and perform about 4*N moves, where I have not really computed the constant 4. The comparisons will all be in cache provided cache size exceeds about sqrt(N). The moves will generally be out of cache but no sorting algorithm can escape having order N out-of-cache moves so that doesn't bother me. If you use radix=R heapsort, then M must be chosen to be of order N/(logN)^c where c>1 is a suitable positive constant chosen to optimize performance, while R is of order logN. So in conclusion, this kind of sort algorithm is optimal in terms of comparisons, moves, "in place" nature (in my sense), and cache behavior re the comparisons if cache is larger than about sqrt(N), all simultaneously. It is possible to do the binary searches in phase I in a branchless manner (use conditional load of pointer-increments), so those comparisons do not face branch-prediction issues. Array merge-sort can be done using conditional load of pointers and increments, again branchless. However list-merge-sort comparisons seem to have prediction issues. Heapsort can be done with all but order N comparisons branchless. Also, one final remark. Franceschini and Geffert left it as open whether a "stable" sorting method with these properties can be devised. Stable means, if two equal elements were in some order in the input, they stay in that order in the output. With my sorting method, you can afford to store, in phase I, the original positions of the items in sample S. Thus you can during phase I binary search agree to always go the right direction to preserve stability. Also, in phase II, we can use a stable sorting method such as merge sort. Also S needs to be sorted itself using a stable method, but S is small enough we can afford to use merge sort. So therefore, provided you accept sublinear (but a lot larger than O(1)) auxiliary storage, this too is solved. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1