February 2014 - mathfun@mailman.xmission.com

Re: [math-fun] [EXTERNAL] Stupid question about hash functions
by Henry Baker 25 Feb '14

25 Feb '14

Suppose U={0,1}^n. Then we can _project_ h(x) onto some smaller # of bits to compute a smaller hash function. But as we project further & further, the probabilities become more & more suspect, because the expected deviations aren't there. At 11:47 AM 2/25/2014, Cordwell, William R wrote: >Detect by means other than having enough values so that not having a collision is suspect? > >-----Original Message----- >From: math-fun-bounces+cordwell=sandia.gov(a)mailman.xmission.com [mailto:math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com] On Behalf Of Henry Baker >Sent: Tuesday, February 25, 2014 12:17 PM >To: math-fun(a)mailman.xmission.com >Subject: [EXTERNAL] [math-fun] Stupid question about hash functions > >Suppose we have a hash function h(x)=y, x,y in universe U, n=|U|. > >(We have a simplified situation in which the domain = range.) > >"Collisions" in hash functions are really bad, due to the Birthday Paradox, so we want h to be 1-1, which in this case means a permutation of U. > >But permutations are a vanishingly small % of all the functions from U -> U; i.e., n! << n^n > >n!/n^n ~ sqrt(2 pi n)/exp(n) > >Shouldn't it get easier & easier to detect a non-random function from U -> U as n increases? > >Shouldn't this lack of randomness be exploitable?

2 1

Re: [math-fun] Changing photos into matrices
by Dave Dyer 25 Feb '14

25 Feb '14

One thing you should be aware of is that - because jpeg images are lossy - the grayscale values you get from it have only a general relationship to what they were supposed to represent. If you were expecting anything like a smooth curve, because that's what your images were supposed to represent, you're going to be very disappointed.

1 0

Re: [math-fun] Changing photos into matrices
by Henry Baker 25 Feb '14

25 Feb '14

What you want is a so-called "bitmap" image, with no compression whatsoever. On Windows machines this is a ".bmp" image. There is another issue, which is the "color space" issue. Even after converting into individual pixels, you still need to know how these pixels map into colors. Luckily, your image is grayscale only, so you shouldn't have to worry about that. Most "bitmapped" images have 8 bits of grayscale, which may not be sufficient to represent finely shaded images. As a result, you could get "contouring" where the gray scale values change integrally. This can be fixed (at some loss of resolution) by "halftoning". Alternatively, there are so-called "raw" bitmap formats for modern cameras which can represent more than 8 bits of grayscale per pixel. I believe that the free "gimp" software will do this (and a lot more). http://www.gimp.org/ At 11:54 AM 2/25/2014, James Propp wrote: >Does anyone know a way to turn black and white jpeg images >into rectangular arrays of pixel-by-pixel grayscale levels? > >My Mac has Adobe Photoshop CS6 and Mathematica, but I can't figure out a >way to get either of them to do it. > >The reason I want to do this has to do with this year's Gathering for >Gardner, so I believe it (just barely) qualifies as a math-fun topic. > >Jim Propp

2 1

[math-fun] "Ansatz" & physics papers
by Thane Plambeck 25 Feb '14

25 Feb '14

Whenever I read a physics paper and the word "Ansatz" appears, I get queasy. Depending upon the Teutonic God being summoned in the mind of the scientist, it seems to variously mean "hypothesis", "starting point", "guess", "unproven theorem", or maybe sometimes something else. It also has an annoying way of always appearing early in the paper, too, just when I'm full of enthusiasm and hoping I'll be able to actually understand the paper. I just looked it up in my Langenscheidt. Ansatz can also mean extension, shoulder, neck, appendage, peg, mouthpiece, deposit, sediment, crust, disposition, start, (math) statement, rate, charge, appropriation, attachment, .... (i got tired of typing these words end so I'll stop here). -- Thane Plambeck tplambeck(a)gmail.com http://counterwave.com/

7 7

[math-fun] "hyperuniform" random patterns in chicken's eyes
by Warren D Smith 25 Feb '14

25 Feb '14

http://www.princeton.edu/main/news/archive/S39/32/02E70/

1 0

Re: [math-fun] Changing photos into matrices
by Adam P. Goucher 25 Feb '14

25 Feb '14

ImageData[] Sincerely, Adam P. Goucher > ----- Original Message ----- > From: James Propp > Sent: 02/25/14 07:54 PM > To: math-fun > Subject: [math-fun] Changing photos into matrices > > Does anyone know a way to turn black and white jpeg images > into rectangular arrays of pixel-by-pixel grayscale levels? > > My Mac has Adobe Photoshop CS6 and Mathematica, but I can't figure out a > way to get either of them to do it. > > The reason I want to do this has to do with this year's Gathering for > Gardner, so I believe it (just barely) qualifies as a math-fun topic. > > Jim Propp > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] convergence speed of continued fractions
by Warren D Smith 25 Feb '14

25 Feb '14

WDS: Usually you can find the answer by viewing CFs as infinite product of 2x2 matrices, and considering the eigenvalues of those matrices in the limit. RWG:S Warren, before wading into your generous followup, I have a stupid question: Scaling a matrix scales the eigenvalues, but doesn't change the value of the C.F. What gives? --scaling matrix does not change the eigenvalue RATIO (2x2 matrix, so unique ratio) which is what matters. OK, since it was not clear enough, let me explain a bit more. (As far as I know I'm the one who invented this, but quite likely not.) A CF (continued fraction) can also be viewed as a product of 2x2 matrices because of Wallis's recurrence relations among the truncated-CF numerators & denominators. Any linear recurrence relation is viewable as a matrix product, times an initial-state vector. The final result vector is then used to compute the final numerator & denominator of the (fully computed) CF. Now. If the CF-matrices happened to all be the SAME, then this matrix product would in fact be merely a matrix POWER, and we could thus express everything (all CF n-deck truncations, as function of n) in closed form, and the matrix nth power is expressible using its two eigenvalue powers. If you multiply a high matrix power times a vector M^n v then what generically happens is, the result is L^n w + tiny error where L is the eigenvalue with max absolute value, and w is the component of v inthat eigenvector's direction (well, if the two eigenvectors happen to be orthogonal) and the error is for large n relatively exponentially small, with shrink factor proportional to the eigenvalue ratio. Some slightly funnier stuff can happen in nongeneric cases, and with non-orthogonal eigenvectors, though... really one should use Schur vectors, which are orthogonal... Now for GENERAL CFs where the matrices are not all the same, often the Nth matrix is a "smooth" function of N and the eigenvectors and eigenvalues change slowly enough as N-->infinity, that it is sufficiently approximately valid to approximate the matrix product via the eigenvalue product. (One can prove this in any particular case by bounding the errors.) Then the convergence-error is proportional to the product of the small eigenvalues so the asymptotic eigenvalue RATIO is what governs the convergence speed. More generally a long time ago in a paper I never finished, I discovered my own version of a lot of Gosperian matrix-product stuff, and had a general purpose convergence theorem in that paper related to matrix products generally via asymptotic eigenvalue connection.

1 0

[math-fun] Hardin 'nuff for you?
by Fred Lunnon 25 Feb '14

25 Feb '14

Hardin 'nuff for you? ********************* As a result of a serendipitous misunderstanding, I have recently derived much enjoyment from investigating this topic. In an effort to bring its puzzle aspects to a wider audience, convince everybody what a brilliant mathematician I am, and delay the looming necessity to write the results up properly, I have prepared the following sketch. Solutions to (some of) the numbered problems may be forthcoming should suspicion subsequently arise that anybody else gives a stuff. A `Hardin array' is defined to be a binary assignment to the nodes of a rectangular m x n grid, such that every 2 x 2 square has some diagonal given equal values; that is, no square is permitted to belong to the set C C C D D C D D D D C D D C C C [Circumventing proportional spacing propels the aliases C = 0 , D = 1 .] I am interested in evaluating T(m, n) = half the number of distinct m x n Hardin arrays, and in estimating its asymptotic behaviour for large m, n . It is not difficult to establish that there is a constant c such that as m, n -> oo , in a rough sense T(m, n) approximates c^(m n) -- rather more precisely, log T(m, n) ~ m n log c . Extrapolation via Aiken delta^2, Wynn rho, suggests (optimistically) that maybe c = 1.5396... . Easy combinatorial constructions establish the rigorous elementary bounds sqrt2 = 1.414213... < c < 1.618034... = tau . ((1)) For more refined bounds which approach the actual value, develop linear recurrences for small fixed m via classical Markov process analysis, then apply Fekete subadditivity (and stop dropping names). For example at m = 5 , we find that f(n) = T(m, n) satisfies f(n) - 16 f(n-1) + 65 f(n-2) - 92 f(n-3) + 48 f(n-4) - 8 f(n-5) = 0 , whence numerically f(n) = (1.39119...) (10.6829...)^n + (smaller terms ...) . Since any m x n Hardin array can be decomposed into roughly m/5 of these arrays, we deduce the upper bound c < 1.6060 = (10.6829)^(1/5) , improving on the earlier elementary bound. Applying similar methods at m = 20 yields tighter bounds 1.504113 < c < 1.555473 . ((2)) The polynomials associated with the recurrences apparently have unexpected properties, the least bizarre being irreducibility; all roots real; all roots positive (upper). ((3)) I'm not going to show you more of these polynomials here. At m = 17 say, they have degree 2123 , with some components over 1300 decimal digits! Establishing lower bounds involves instead a subset of Hardin arrays: those `bordered' with C along all four edges, and counted by S(m, n) . The border acts as cement, allowing m x n bordered arrays to be tiled together (borders overlapping), so building larger arrays of size (k m - k + 1) x (l n - l + 1) . A key stage in the recurrence construction involves characterising those distinct binary columns requiring consideration, leading to the following `accessibility' problem: Develop an algorithm to decide, in time and space linear in m , whether a given m-vector can occur as a column in a bordered m x n Hardin array (for sufficiently large n ). ((4)) For example with m = 15 columns CDDDDDDDDDDDDDC and CDDCCDDCDDCCDDC are accessible (via columns bordered by C...C) from an initial CCCCCCCCCCCCCCC ; however CDDCCCCCCCCCCCC is not. This puzzle has a wonderfully compact and elegant solution. Once you get it right, after the fourth or fifth fumble, that is. But having finally cracked it, count the number a(m) of accessible vectors, compared to the total number b(m) = 2^(m-2) of bordered vectors: m 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... a(m) 1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, ... b(m) 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... [I blush to confess that I went searching for a(m) in OEIS ; even then, I couldn't at first get my head around what it kept trying to tell me.] But amazingly, these seem to be simply the central binomial coefficients (Conjecture) a(m) = (m-1)_C_[(m-1)/2] ?! ((5)) though I have at present no idea why. Anyway on this assumption, Stirling's approximation yields a welcome reduction factor a(m)/b(m) ~ 1.595770 / sqrt(m) in the number of columns required -- a saving which squares up in space, a(m) representing the order of a rather hefty matrix. I mentioned previously the (presumed) conjecture -- mentioned [??] cryptically under OEIS A078099 -- to the effect that Hardin arrays correspond to grid-colourings of the same-size using three colours: here P, Q, R . Note that nodes sharing an edge are assigned distinct colours; and the top-left node of both grids remains constant, C and P resp. Specify a bijective mapping between m x n Hardin arrays and grid three- colourings. ((6)) While this is trickier than might be expected, there awaits again a solution both short and sweet. Appendix:: sample 9 x 9 Hardin array, together with corresponding grid 3-colouring: C D C C D C C C C P R P Q R Q P Q P D C C C C C D C D R P Q P Q P R P R C C D C C C C D D P Q R Q P Q P R Q C D D D C D C C D Q R P R Q R Q P R D D C D D C D C C R P Q P R Q R Q P ; D D D C D D D D C P R P Q P R P R Q C D D D D D D C C Q P R P R P R Q P D D D D C D C C C P R P R Q R Q P Q D D D D D C C D C R P R P R Q P R P and a bordered 8 x 8 Hardin array, illustrating some of 35 distinct accessible columns (or rows): C C C C C C C C C C D C D C C C C C C D C C C C C C D D D C D C C D D D C C C C C C D D D C C C C C C D C C C C C C C C C C C C Short tables -- best viewed sans pesky proportional spacing -- of T(m, n) , counting m x n Hardin arrays with C at top-left: m\n 1 2 3 4 5 6 7 1 1 2 4 8 16 32 64 2 2 6 18 54 162 486 1458 3 4 18 82 374 1706 7782 35498 4 8 54 374 2604 18150 126534 882180 5 16 162 1706 18150 193662 2068146 22091514 6 32 486 7782 126534 2068146 33865632 554916090 7 64 1458 35498 882180 22091514 554916090 13956665236 and S(m, n) , counting m x n Hardin arrays with C around border: m\n 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 2 3 5 8 13 21 34 4 1 1 3 7 17 41 99 239 577 5 1 1 5 17 64 235 870 3211 11867 6 1 1 8 41 235 1322 7479 42267 238958 7 1 1 13 99 870 7479 64914 562213 4876632 8 1 1 21 239 3211 42267 562213 7474305 99480399 9 1 1 34 577 11867 238958 4876632 99480399 2033739170 Fred Lunnon Maynooth 22/02/14

6 13

Re: [math-fun] "Ansatz" & physics papers
by Henry Baker 25 Feb '14

25 Feb '14

"Queasy" may be an understatement... http://en.wikipedia.org/wiki/Glossary_of_Nazi_Germany Ansatz (attack) - First World War military term, used in National Socialist vocabulary in the same ways as the word Einsatz, though less frequently; one referred to bringing a piece of equipment, troops or a weapon "zum Ansatz" (into attack, or play). Anschluss (AnschluÃ) Â annexation, in particular the annexation of Austria in March, 1938. Ondonner, Onblitzen: http://songmeanings.com/songs/view/3530822107859015590/ At 09:05 AM 2/25/2014, Thane Plambeck wrote: >Whenever I read a physics paper and the word "Ansatz" appears, I get queasy.

1 0

Re: [math-fun] Synthesizing functions over finite fields with polynomials
by Henry Baker 25 Feb '14

25 Feb '14

OK, let's now look specifically at functions which are _permutations_. Suppose I have a finite field GF(p^k), which can be represented as k-element vector with elements [0..p-1]. Is there any characterization of these Lagrange interpolations that happen to generate only permutations? I.e., let P={x|x=[x0,x1,x2,...,x(k-1)] and 0<=xi<p and i/=j => xi/=xj}, then f(p)=q for p,q in P. Alternately, which algebraic constructions generate _only_ and _all_ permutations of [0..p-1]. Obviously additions and multiplications by constants generate some of the permutations, but not all of them. What else do we need to get all of the permutations? 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

2 3