February 2014 - mathfun@mailman.xmission.com

[math-fun] Fwd: numberphile.com
by rcs＠xmission.com 02 Mar '14

02 Mar '14

It looks like MSRI is getting into serious outreach. Bob Baillie passed along the url http://www.numberphile.com I haven't looked at the insides yet, but the front page looks tasty. Rich

13 25

[math-fun] a contfrac riddle
by Joerg Arndt 01 Mar '14

01 Mar '14

Define A(x) by A(x) = 1 + x / A(x^2), so A(x) = 1+x/(1+x^2/(1+x^4/(1+x^8/(1+ ...)))). Define F(x) by F(x) = 1 + x / (1 - x^2 / F(x^2) ), so F(x) = 1+x/ (1-x^2/ (1+x^2/ (1-x^4/ (1+x^4 /(1-x^8/ (1+x^8/ (1-x^16/ ... ))))))). The following took me a while: Show that F(x) - x = A(x^3) Spoiler below. I am asking because I'd like to know how you'd rate it in difficulty and time this should/did take. Regards, jj ... on to the spoiler ... on to the spoiler ... on to the spoiler ******************** SPOILER ********************** Set G(x) = F(x) - x observe that G(x) = 1 + x^3/G(x^2) = 1 + x^3/(1 + x^6 / G(x^2) ) = ... = 1 + x^3/(1 + x^6 / (1 + x^12 / (1 + x^24 / (...) ) ) ) = A(x^3). Cf. https://oeis.org/draft/A238429 (expansion of F), https://oeis.org/draft/A218031 (expansion of A)

2 1

[math-fun] 12th degree radicals?
by Bill Gosper 28 Feb '14

28 Feb '14

In http://mathworld.wolfram.com/SquareDissection.html, x₂ satisfies 6 - 4 √2 + (-24 + 16 √2) x + (28 - 20 √2) x^2 + (-8 + 8 √2) x^3 - 2 x^4 + x^6, whereat my sextic solver chokes on the √2s. Does anybody know if x comes out in radicals? --rwg

3 4

[math-fun] A quality function for creating multiwinner voting systems
by Warren D Smith 27 Feb '14

27 Feb '14

A quality function for creating multiwinner voting systems ===============Warren D. Smith=====Feb 2014=============== One way to design a multiwinner voting system is to define a "quality function" which examines the votes, voters, candidates, and winners, and outputs a number. Then the voting system could simply be to choose the winner-set yielding maximum quality. (Finding that best subset might be computationally infeasible, but we ignore computational complexity issues for the moment.) We here will propose a quite general class of possible quality functions, which immediately yields an infinite set of new PR (proportional representation) multiwinner voting systems. OPEN QUESTIONS: A. Which among our functions is "the best"? B. Is it possible to generalize this still further in some reasonable way so that not only PR, but also TPC (Toby Pereira's Condition, see below) is satisfied? ----- Let C=#candidates, V=#voters, W=#winners, 0<W<C<V, and let S[v,c] be the real-valued score given by voter v to candidate c on her ballot. Then here is a highly general class of quality measures Q: Q = SUM(v=1..V) F( SUM(j=1..W) (jth greatest S[v,c] among winning c) * A[j] ) where A[1], A[2], A[3], ... are real numbers specified by voting system designer, and F(x) is a function specified by voting system designer. [Incidentally if F(x)=x, and A[1]=1 and A[j]=0 for j>1, then this quality measure would be maximizable in polynomial time.] If F(x)=x, then "proportional representation" (PR) will be assured by choosing A[j] = 1/(j+RealConstant). PR means: if all voters and candidates are different "colors" and each voter scores each same-color candidate 1, rest 0, then the proportion of color-X winners will come out the same as the proportion of color-X voters, for all X, up to at most constant additive errors in #winners. If A[j]=1 for all j, then we can instead obtain PR by using F(x)=K1+K2*log(x+K3) where K1,K2,K3 are any real constants with K2>0. But those were only two special cases. More generally, we can assure PR by choosing the A[j]>0 and F() such that SUM(j=1..m) F(A[j]) = K1+K2*log(m+K3) to good enough approximation. It seems intuitively preferable for the A[j] to be nonincreasing with j and F(x) to be increasing with x so below I'll only give examples obeying those. Then an infinite number of further examples include: 1. A[j] = j^(-P) for any fixed real P with 0<=P<1, and F(x) = log(x). 2. A[j] = j^(-1) and F(x) = x. 3. A[j] = 1/(j*ln(j+1)) and F(x) = exp(x) 4. A[j] = (1/j)*ln(j+1)^(P-1) for any fixed real P with 0<P, and F(x) = x^(1/P). Can any argument be made that some one among the above is "best" or anyhow better than others? But none of these examples, and apparently no quality function of this class, satisfies Toby Pereira's condition (TPC): AFTER universally-liked candidates win, then there must be proportionality about the remaining winners. So I think there is a theorem lurking here (conjecture for present) that no quality function of this quite-wide-seeming class, is capable of both PR and Pereira's post-universally-liked-winners criterion TPC. Which leads us to the question: is it even possible for ANY quality measure, or ANY voting system, to satisfy both criteria? (Pereira thinks he has one, but I doubt it.) One crude try would be something like this. 2-stage voting system. In its first stage, essentially you use a single-winner voting system like range voting to elect winners one at a time. You keep going until the next proposed winner drops below some threshold ("not universally liked enough"). Then you switch to a PR voting system for all the remaining candidates (who have not yet won). BUT this idea would still clearly fail a more-refined form of Toby Pereira's condition: After candidates universally liked among Pink voters only win, then the subfactions of the Pinks should then get proportional representation about future Pink winners. Another try (which technically works) would be to observe that the definition of "PR" is very silly and only applies when voters & candidates are split exactly into disjoint factions; and Pereira's definition of "universal winner" also is very silly ("silly" meaning, in reality, these requirements would essentially never be satisfied) and it is possible to exploit/abuse that silliness because the silly situations where these definitions apply do not overlap and hence cannot contradict. But the kind of quality measure Q proposed above does not exploit this silliness and hence cannot particularly abuse it, and then we conjecturally get a contradiction & impossibility. Can we generalize somehow Q further to try to satisfy TPC? One attempt might involve summation over PAIRS of candidates (and/or voters), not just single ones.

1 0

[math-fun] Surely not new?
by rkg 26 Feb '14

26 Feb '14

Sorry if this is well known to those who well know it, but the following seem not to be in OEIS: 1, 1, 2, 7, 35, 191, 1304, ... 1, 2, 5, 18, 89, 492, 3359, ... Presumably because I've made a stupid mistake in my hand clculations. They are the numerators and denominators of the convergents to the negative continued fraction 1 - 1/(2 - 1/(3 - 1/(4 - ...))) R.

2 2

[math-fun] quantum entangled clock network? Ultra-accurate?
by Warren D Smith 26 Feb '14

26 Feb '14

I'm unsure whether this idea is completely insane: https://www.sciencenews.org/article/quantum-timekeeping

6 8

[math-fun] Stupid question about hash functions
by Henry Baker 26 Feb '14

26 Feb '14

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?

3 3

[math-fun] Changing photos into matrices
by James Propp 26 Feb '14

26 Feb '14

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

4 5

[math-fun] Graphic artists subvert/illuminate the golden ratio
by Alex Bellos 26 Feb '14

26 Feb '14

some fun (phun?) pictures from a book I was involved with, in which 55 graphic designers were asked to 'communicate' the golden ratio http://www.theguardian.com/science/alexs-adventures-in-numberland/gallery/2… background here: http://www.theguardian.com/science/alexs-adventures-in-numberland/2014/feb/… alex

2 1

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

25 Feb '14

The problem with the probabilities output from the permutation function is that they are "too" good: the probabilities themselves are ok, but the standard deviations are too small. Now the real question is how many bits is this worth, and the answer might be "not very many". The information content of a permuter is about n*logn-n = n*[(logn)-1] bits, whereas the information content of a random function is n*logn. So the difference is perhaps n bits. If logn >> 1, then this isn't going to hurt very much, whereas the existence of collisions will hurt a lot. At 02:30 PM 2/25/2014, Cordwell, William R wrote: >Interesting idea. So, if we project a permutation, the range probabilities are certainly uniformly distributed. Not quite so with a projected random function (what the distribution actually is sounds like another interesting question). But if we start with, say {0,1}^256 as the domain and range (permutation output) of our input space, and if we choose something plausible to project to, such as {0,1}^40, then there are 2^216 "unprojected" points for every projected point, from which to sample. If we also sample 2^40 times, reaching into the bag and picking out values, it seems awfully close to sampling with replacement, so one might expect the sample to look like a random function output on {0,1}^40. I suspect that it gets closer to that behavior, the larger the initial value for n. > >If we could claim that permuting with a random permutation first, then truncating is a hash function, vs. truncating the result of a random function (which is also a hash function), then I think that we might be done (left-over hash lemma?). > >-----Original Message----- >From: math-fun-bounces(a)mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Henry Baker >Sent: Tuesday, February 25, 2014 2:00 PM >To: math-fun >Subject: Re: [math-fun] [EXTERNAL] Stupid question about hash functions > >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?

1 0