- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Fwd: Cutting a pie ...
by James Propp 29 Dec '17

29 Dec '17

>From Warren Smith: ---------- Forwarded message ---------- From: Warren D Smith <warren.wds(a)gmail.com> Date: Thu, Dec 21, 2017 at 2:27 AM Subject: Re: [math-fun] Cutting a pie ... To: James Propp <jamespropp(a)gmail.com> OK, think I see how to rigorize my claim F(n) < K * n^2 / log(n). Specifically THEOREM: If K>1, then for all sufficiently large n F(n) < K*(n^2) / (2*ln(n)). PROOF: Essentially, here is the argument. Let L(n) = LCM(1,2,3,...,n) = exp([1+o(1)]*n). Choose a subset of {0,1,2,...,L(n)-1} of cardinality=F(n) at random. Sort it. Let S denote the F(n) consecutive-element differences [modulo L(n)] in that subset. Hence the elements of S sum to L(n), which will be the total size of the pie. Now consider all possible ways to k-color the elements of S. Do this for each k=2,3,...,n, the result being a "coloring tuple" (i.e the elements of the coloring tuple are: the 2-coloring, the 3-coloring, ..., the n-coloring) and we are considering the full set of all possible coloring tuples. If the k-coloring has the property that the k different monochromatic sums of S-elements all happen to be equal, then S provides a cake-cutting suitable for k players. If the full coloring tuple does that for k=2,3,...,n all simultaneously, then it was a suitable cake cutting. Ask: what is the expected number of coloring tuples that are thus-suitable? The answer is lower bounded by n!^F(n) * L(n)^(-(n-1)*n/2). Now: if this expectation exceeds 1, that proves a suitable coloring-tuple MUST EXIST, i.e. a suitable cake-cutting must exist. Taking logs, we see that happens if F(n)*log(n!) >= (n-1)*n/2 * n * [1+o(1)] That happens if F(n) >= [1+o(1)] * (n-1)*n/(2*log(n)) using natural log. Q.E.D. This is a nice application of "Erdos's method." -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 9

[math-fun] Who wrote this?
by James Propp 29 Dec '17

29 Dec '17

I'm facing an embarrassing attribution mystery: I really like a quote, and I'm hoping to use it in some of my writing, but I don't know whom to attribute it to! (Maybe one of you wrote it?) Here's the passage I found in my collection of miscellaneous ideas and quotations related to my blog (unfortunately lacking any indication of where I lifted the passage from): The freedom of mathematics is that we can define conceptual structures of all kinds, as long as the rules governing them are clear and free of contradiction. [(The preceding sentence was in my article on tropical semirings.] And even when two such structures seem to be incompatible, there is often a way of viewing them together. This is simplest when the two systems are nested one inside the other, the way the real number system sits inside the tropical semiring (whichever one you like), which in turn sits inside the extended real number line. But even in cases where the two systems seem incompatible, like Euclidean two-dimensional geometry and non-Euclidean two-dimensional geometry, there is typically a higher point of view that reconciles them. If we insist on a literal point of view of what math is telling us, then we can't believe in both Euclidean geometry and non-Euclidean geometry; they appear to be making contradictory assertions about space. But that's an example of what Buddhist teacher Alan Watts called eating the menu instead of the dinner. Once we understand that geometrical postulates and theorems are making assertions about the possibilities of the notion of space, and not about the physical space we inhabit, then we can see a context in which Euclidean and non-Euclidean geometry, far from being mutually undermining, are in fact mutually supporting. I tried Googling the opening sentence, but it's not in the Google database. It's possible that parts of this are mine and parts aren't. But I strongly suspect that the sentence about Alan Watts isn't mine, since I've never read anything by Alan Watts (though I have read books by people who quote, Alan Watts, so who knows?). Jim Propp

1 0

[math-fun] Triple intersections
by James Propp 29 Dec '17

29 Dec '17

I either need Sage help, or math help, in order to figure out whether all these fun facts about pairwise intersections extend to triple (and higher order) intersections. In one-dimension, I can show that the expected length of the intersection of k unit intervals, conditional upon the intersection being nonempty, is 1/k. It follows (via the additivity of expected values of random variables and the multiplicativity of expected values of independent random variables) that if you take the intersection of k a-by-b rectangles, conditional upon the intersection being nonempty, the intersection has expected perimeter (2a+2b)/k and expected area (ab)/k^2. This extends easily to parallelograms and parallelohedra, but where I get stuck is thinking about centrosymmetric hexagons. Can anyone see how to prove (or disprove) that if you take the intersection of three translates of a centrosymmetric hexagon, conditioned upon the intersection being nonempty, the expected perimeter is P/3 and the expected area is A/9, where P and A are the perimeter and area of the hexagon? Alternatively, can anyone tell me why the following Sage code (for computing the expected number of vertices of the triple intersection) doesn't work? v = [] h = 866/1000 for i in range(10): s=4*floor(1000000*random())/1000000-2 t=4*floor(1000000*random())/1000000-2 u=4*floor(1000000*random())/1000000-2 v=4*floor(1000000*random())/1000000-2 p1=Polyhedron(vertices=[[-1,0],[-1/2,h],[1/2,h],[1,0],[1/2,-h],[-1/2,-h]]) p2=Polyhedron(vertices=[[-1+s,0+t],[-1/2+s,h+t],[1/2+s,h+t],[1+s,0+t],[1/2+s,-h+t],[-1/2+s,-h+t]]) p3=Polyhedron(vertices=[[-1+u,0+v],[-1/2+u,h+v],[1/2+u,h+v],[1+u,0+v],[1/2+u,-h+v],[-1/2+u,-h+v]]) p12=p1.intersection(p2) if len(p12.f_vector())>1: p123=p12.intersection(p3) if len(p123.f_vector())>1: v.append((p123.f_vector())[1]) sum(v)/len(v) If I knew how to fix the bug, I think I'd be able to do numerical experiments regarding perimeter and area as well. Thanks, Jim Propp

1 3

[math-fun] Riddle
by David Wilson 28 Dec '17

28 Dec '17

What has tusks and a determinant of -1 or -1? [scroll down] A warthogonal matrix.

3 2

Re: [math-fun] Riddle
by Dan Asimov 28 Dec '17

28 Dec '17

And why must it be orthogonal? Plenty of matrices with |determinant| = 1 are not orthogonal. Like (1 10^(10^10)) ( ) (0 1) —Dan > Not perhaps the easiest creature on the planet to love, >but why must it be so negative? Let's hear it for Phacochoerus >africanus with determinant +1 ! WFL > >On 12/29/17, David Wilson <davidwwilson(a)comcast.net> wrote: >> What has tusks and a determinant of -1 or -1? >> [scroll down] >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> A warthogonal matrix. >> >> >> >> >> >> >> >> >> >> >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > >_______________________________________________ >math-fun mailing list >math-fun(a)mailman.xmission.com >https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] replay-proof protocols: the double helix model of 2-party protocols
by Henry Baker 28 Dec '17

28 Dec '17

[I hope that I'm not simply demonstrating my abject ignorance in the following paragraphs.] I recall from my graduate school days that many communicating process mathematical proofs (virtually) passed the entire (linear) communications history back and forth; but this was several years prior to serious public research into crypto protocols. It occurred to me that using modern crypto primitives -- e.g., crypto quality hash functions -- one needn't pass the history itself, but merely the *hash* of the communications history, so the history need no longer be a merely "virtual" history, but a real parameter made of solid bits. Since a crypto quality hash can't be faked, and since we do have industrial-grade crypto, the *only* way to extend the communication history is by allowing parties A & B to *alternately* extend this communications history. Thus, we have a simplified version of a *blockchain* problem, where A & B *must* alternate, and *only* A can extend a history most recently produced by B, and *only* B can extend a history most recently produced by A. In essence, we're simultaneously building *two* blockchains: A's blockchain, which can fully "see" the items added by A but only dimly see (observe only hashed bits) those added by B, and B's blockchain, which can fully "see" the items added by B but only dimly see those added by A. [I have thought a lot about exactly what goes into the "state" of A and the "state" of B, as well as what should be included in the parameter packets added by A and B, but I thought I would start with the bare blockchain history idea.]

1 0

[math-fun] (<2)D Heighway Dragons self-cross
by Bill Gosper 27 Dec '17

27 Dec '17

Fred: (intolerably,) no attachments in math-"fun". Nicer version: gosper.org/drinkle5.gif not responding ... But host is prone to multiminute outages. Date: 2017-12-22 16:33 From: Fred Lunnon <fred.lunnon(a)gmail.com> To: math-fun <math-fun(a)mailman.xmission.com> Reply-To: math-fun <math-fun(a)mailman.xmission.com> Please attach original post! gosper.org/drinkle3.gif not responding ... WFL On 12/22/17, Allan Wechsler <acwacw(a)gmail.com> wrote: > What it *looks* like is that there is a small range of angles just short of > pi/2, the curve self-crosses. > > Prove to me that this is *not* happening on a microscopic scale for angles > short of that small range. Allan, I don't get it. drinkle3 (etc) massively self collides. Are you referring the apparent self-graze of a triadic dragon I sent off-list? --rwg > On Fri, Dec 22, 2017 at 5:14 PM, Bill Gosper <billgosper(a)gmail.com> wrote: > >> Sounds familiar--I probably heard and forgot. Somebody probably even >> knows >> the minimal D. >> gosper.org/drinkle3.gif --rwg >> (Picture credit: Julian's software.) >>

3 3

[math-fun] (<2)D Heighway Dragons self-cross
by Bill Gosper 26 Dec '17

26 Dec '17

Sounds familiar--I probably heard and forgot. Somebody probably even knows the minimal D. gosper.org/drinkle3.gif --rwg (Picture credit: Julian's software.)

3 3

[math-fun] One more reciprocal
by rcs＠xmission.com 23 Dec '17

23 Dec '17

This is mostly for the old-timers. Once upon a time, roughly <1965, division was expensive. Some computers even came without a Divide instruction, and had to use a subroutine. With floating point numbers, the division X/Y was sometimes done as X times 1/Y. A programming trick from that era came to be known as "one more reciprocal". The idea of 1MR is to replace several reciprocal operations with a single one, minimizing the total execution time. The magic formula: Assume you need to compute 1/X and 1/Y. Compute R = 1/(XY), and then 1/X = RY and 1/Y = RX. The idea extends to more reciprocals; potentially an arbitrary number of reciprocals can be replaced with a single one. Each avoided reciprocal costs an extra three multiplications. Whether this is worthwhile depends on the relative cost of Divide versus Multiplication, and some side costs: code complexity, storage, concern for over/underflow, and a slight loss of accuracy. As division has cheapened, 1MR has mostly fallen out of use. 1MR is still used in modular arithmetic, where the relative costs favor it. Peter Montgomery introduced it for elliptic curve calculations c. 1985. It's also usable for matrices, if you are careful about non-commutativity. There was a brief vogue for possible generalizations, perhaps when computing several square roots, or several multiplications -- a multiply can be replaced with two squarings. AFAIK, these didn't go anywhere. I'm looking for some mention of 1MR, either in print or old memories. Google is unhelpful, and my Numerical Recipes is too recent. Rich

6 6

[math-fun] What squeals and has a determinant of 1 or -1?
by David Wilson 22 Dec '17

22 Dec '17

A warthogonal matrix. Merry Christmas.

1 0