February 2013 - mathfun@mailman.xmission.com

[math-fun] Fun with maps
by Keith F. Lynch 21 Feb '13

21 Feb '13

I typed in a list of which US states border which other US states, so I can write programs to do various things with it. For instance by creating an adjacency matrix and raising it to successive powers, I was able to determine which states are furthest apart in the sense that you have to cross the most borders to get between them without leaving the US. (Maine to either Washington or Oregon requires at least 12 state border crossings. That's the record, unless you count the two states that can't be reached at all.) I thought I had found the record in-alphabetic-order trip, IA IL IN KY MO TN VA WV, until I realized that I was doing alphabetic order by state *abbreviation*. Oops! The longest trips by alphabetic order are shorter than that. I'll leave them to others to rediscover -- or to try longest trip by states in order of population, area, or anything else quantifiable. I only ran into trouble when attempting to verify that the list was correct. Well, not correct, necessarily, but consistent. Of course I made sure that if A borders B then B border A, and that no state borders itself. But what about impossible maps? Or, to put it in mathematical terms, a non-planar graph? This turns out to be surprisingly hard. I'm familiar with Kuratowski's theorem, but I estimate it would take at least a month of CPU time to test every possible set of 5 or 6 states. (No, applying it only to states that border each other is invalid.) And for larger maps, it would be completely infeasible. Of course I want any software I write to work with any map, not just with this map. My first thought was that the states that border a given state should always be able to be put into a circular order. If A borders B, there should always be exactly two states that border both A and B. If I start with one of them and look at states that border A and this new state, I should keep getting a succession of different states that border A, until I return to B, and there should be no bordering states unaccounted for or duplicated. For instance Tennessee (which is tied for the record of most bordering states) borders my home state of Virginia. Those two states border Kentucky. Tennessee and Kentucky both border Missouri. Tennessee and Missouri both border Arkansas. Tennessee and Arkansas both border Mississippi. Tennessee and Mississippi both border Alabama. Tennessee and Alabama both border Georgia. Tennessee and Georgia both border North Carolina. Tennessee and North Carolina both border Virginia, and we're back where we started, with no states listed as bordering Tennessee unaccounted for, nor any appearing twice. Of course we run into a problem with a state on the border of the country. But we can create a new "state," the Exterior. I also added Lake Michigan and Four Corners as "states," so that every border ends on another border. It didn't work. Sometimes the same state shows up twice when going around the border of a state. For instance Virginia borders Maryland twice, once on each side of DC. New York borders the Exterior twice. Whenever that happens, it can only be because one or more states are enclosed by state A and the twice-bordering state B. Maryland and Virginia enclose DC. New York and the Exterior enclose all the New England states. To find these enclosed states, I zero the rows and columns representing the two enclosing states from the adjacency matrix, completely delete the rows and columns representing Alaska and Hawaii, and raise the matrix to successive powers. If all the zeros (other than in the two rows and columns I zeroed) go away, then there's an inconsistency, a "tunnel" from the enclosed states to the rest of the world. Otherwise, I regard the states which have more than half of their rows as persistent zeros as being enclosed. (Since there are an even number of states, I could in principle get a tie, where exactly half the states are on one side of the "wall" created by the two states in question and exactly half are on the other. In that case every row would be exactly half zeros and I'd have to make an arbitrary choice which is inside and which is outside. I don't want to privilege the Exterior; I'd prefer to treat every state the same. Anyhow, the Exterior may be one of the two enclosing states.) (It just occured to me that in principle there could be any number of enclosures by the two states in question, and if there are enough of them they could all be very small. Sigh.) This works. But sometimes *three* states enclose a set of states. And doing the same thing with three states doesn't work. For instance it claims that Maryland, Virginia, and West Virginia surround DC, and that's not the case, as West Virginia does not border DC. I think I can make it work if I keep track of what any two of those three states enclose, and deal with that somehow. But what a pain. Anyhow, I'm not at all convinced that what I'm doing would prove consistency anyway, rather than just finding one possible failure mode. Here's my list, if anyone else wants to play with it: AK: EX AL: EX FL GA MS TN AR: LA MO MS OK TN TX AZ: CA EX FC NM NV UT CA: AZ EX NV OR CO: FC KS NE NM OK UT WY CT: EX MA NY RI DC: MD VA DE: EX MD NJ PA EX: AK AL AZ CA CT DE FL GA HI ID LA MA MD ME MI MN MS MT NC ND NH NJ NM NY OH OR PA RI SC TX VA VT WA WI FC: AZ CO NM UT FL: AL EX GA GA: AL EX FL NC SC TN HI: EX IA: IL MN MO NE SD WI ID: EX MT NV OR UT WA WY IL: IA IN KY LM MO WI IN: IL KY LM MI OH KS: CO MO NE OK KY: IL IN MO OH TN VA WV LA: AR EX MS TX LM: IL IN MI WI MA: CT EX NH NY RI VT MD: DC DE EX PA VA WV ME: EX NH MI: EX IN LM OH WI MN: EX IA ND SD WI MO: AR IA IL KS KY NE OK TN MS: AL AR EX LA TN MT: EX ID ND SD WY NC: EX GA SC TN VA ND: EX MN MT SD NE: CO IA KS MO SD WY NH: EX MA ME VT NJ: DE EX NY PA NM: AZ CO EX FC OK TX NV: AZ CA ID OR UT NY: CT EX MA NJ PA VT OH: EX IN KY MI PA WV OK: AR CO KS MO NM TX OR: CA EX ID NV WA PA: DE EX MD NJ NY OH WV RI: CT EX MA SC: EX GA NC SD: IA MN MT ND NE WY TN: AL AR GA KY MO MS NC VA TX: AR EX LA NM OK UT: AZ CO FC ID NV WY VA: DC EX KY MD NC TN WV VT: EX MA NH NY WA: EX ID OR WI: EX IA IL LM MI MN WV: KY MD OH PA VA WY: CO ID MT NE SD UT (Watch out that your mail reader doesn't break the long line "EX.") Also feel free to post other "maps" in the same format, either maps of real places or perverse maps designed to stress-test software, perhaps with hidden inconsistencies.

13 21

Re: [math-fun] Fermat's Last Theorem question
by Adam P. Goucher 20 Feb '13

20 Feb '13

Yes, I can believe that FLT can be proved in ZF without AC. PA, on the other hand, is pretty rubbish (it can't even manage the well-ordering of epsilon_0). I would be highly surprised to see an elementary (provable in PA alone) proof of FLT. Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Dan Asimov > Sent: 02/20/13 07:02 PM > To: math-fun > Subject: Re: [math-fun] Fermat's Last Theorem question > > Let me add another sentence from that Science News article, > since not quite knowing what either "finite order arithmetic" > or "simple type theory" means, this clarified things for me: > > ----- > McLarty recently showed that Fermat’s Last Theorem can be proven using the ordinary axioms of mathematics, and even a bit less. > ----- > > The article's author seems to say that the ordinary axioms of mathematics means "set theory", > which I take to mean the ZF axioms, apparently without AC. > > --Dan > > > > On 2013-02-20, at 10:04 AM, Fred W. Helenius wrote: > > > On 2/19/2013 10:54 AM, Henry Baker wrote: > >> Q about the proof of FLT: > >> > >> I realize that Fermat himself wouldn't recognize Wiles's proof, but would Fermat recognize the assumptions? > >> > >> I.e., does the Wiles proof require any "exotic" assumptions -- e.g., axiom of choice, generalized Riemann hypothesis, etc. ? > > > > When I answered this yesterday, I cited a 2010 article by Colin > > McLarty. He's been busy since, and my newsfeed this morning > > contained a headline from Science News about his work: "A > > mathematician puts Fermat's Last Theorem on an axiomatic diet" > > (http://www.sciencenews.org/view/generic/id/348403/description/A_mathematici…) > > It's a fluffy article based on work McLarty announced at the > > recent Joint Meetings; here's the abstract for that talk, > > "Grothendieck's cohomology founded on finite order > > arithmetic": > > > > Despite rumors to the contrary, Grothendieck and others > > published proofs using Grothendieck universes, which are > > sets so large that ZF does not prove they exist. Number > > theorists to this day cite those published proofs. More > > conservative references avoid universes but still use far > > stronger set theory than the number theory requires, such > > as large amounts of replacement. We describe the issues and > > show how to formalize the entire Grothendieck apparatus at > > the strength of finite order arithmetic (simple type theory > > with infinity) and describes progress towards yet weaker > > foundations. (Received September 18, 2012) > > > > So he claims to have shown that Grothendieck's universes are not > > needed, but he's still a long way from Peano arithmetic. > > > > -- > > Fred W. Helenius > > fredh(a)ix.netcom.com > > > > > > _______________________________________________ > > math-fun mailing list > > math-fun(a)mailman.xmission.com > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 1

[math-fun] Siebeck's Theorem (was Q re ellipses in the complex plane)
by Dan Asimov 20 Feb '13

20 Feb '13

My point is that the ellipses for c > 0 do not approach the line segment [-1,1]. They approach the line segment [-sqrt(⅓), sqrt(⅓)]. --Dan From: Henry Baker <hbaker1(a)pipeline.com> Subject: Re: [math-fun] Q re ellipses in the complex plane Date: 18 February, 2013 5:19:14 PM PST ----- . . . I hadn't thought it possible that an ellipse could approach a line segment while still keeping its foci away from the line segment ends, but I was wrong! . . . ----- On 2013-02-19, at 4:33 PM, Henry Baker wrote: > Re: "This is not what happens": > > Tell that to Maxima. P(z) has roots at +-1, +ci. > > P'(z) has roots at +ci/3+-sqrt(3-c^2)/3 = +-1/sqrt(3) when c=0. > > (%i1) declare(z,complex); > (%o1) done > (%i2) P(z):=(z-1)*(z+1)*(z-%i*c); > (%o2) P(z) := (z - 1) (z + 1) (z - %i c) > (%i3) solve(P(z),z); > (%o3) [z = %i c, z = - 1, z = 1] > (%i4) solve(diff(P(z),z),z); > 2 2 > sqrt(3 - c ) - %i c sqrt(3 - c ) + %i c > (%o4) [z = - -------------------, z = -------------------] > 3 3 > (%i5) %,c=0; > 1 1 > (%o5) [z = - -------, z = -------] > sqrt(3) sqrt(3) > (%i6) %,numer; > (%o6) [z = - 0.57735026918963, z = 0.57735026918963] > > I.e., these numbers are not +-1. > > At 03:33 PM 2/19/2013, Dan Asimov wrote: >> This is not what happens. >> >> The limit of the ellipse as c -> 0 is indeed a degenerate ellipse that is precisely the line segment between its foci, +-sqrt(â…“). >

2 1

Re: [math-fun] Marden^H^H^H^H^H^HSiebeck's Theorem
by Henry Baker 20 Feb '13

20 Feb '13

But you missed the original question: As the triangle collapses, _why_ does the ellipse collapse to [-1,1]/sqrt(3) instead of to [-1,1] ? After all, the ellipse gets thinner & thinner; why not get thin enough to move the foci all the way into the triangle's base vertices ? --- Interestingly, as an equilateral triangle collapses to smaller & smaller isosceles triangles, the ellipse foci start together at the center of the triangle, and then move downwards on either side in a _circular_ locus to hit the base of the triangle at +-1/sqrt(3), where the radius of the circle is r=1/sqrt(3). This would be an interesting quiz problem, as I would never have guessed the circularity of the locus. At 04:40 PM 2/19/2013, Dan Asimov wrote: >My point is that the ellipses for c > 0 >do not approach the line segment [-1,1]. > >They approach the line segment [-sqrt(â), sqrt(â)]. > >On 2013-02-19, at 4:33 PM, Henry Baker wrote: > >> Re: "This is not what happens": >> >> Tell that to Maxima. P(z) has roots at +-1, +ci. >> >> P'(z) has roots at +ci/3+-sqrt(3-c^2)/3 = +-1/sqrt(3) when c=0. >> >> (%i1) declare(z,complex); >> (%o1) done >> (%i2) P(z):=(z-1)*(z+1)*(z-%i*c); >> (%o2) P(z) := (z - 1) (z + 1) (z - %i c) >> (%i3) solve(P(z),z); >> (%o3) [z = %i c, z = - 1, z = 1] >> (%i4) solve(diff(P(z),z),z); >> 2 2 >> sqrt(3 - c ) - %i c sqrt(3 - c ) + %i c >> (%o4) [z = - -------------------, z = -------------------] >> 3 3 >> (%i5) %,c=0; >> 1 1 >> (%o5) [z = - -------, z = -------] >> sqrt(3) sqrt(3) >> (%i6) %,numer; >> (%o6) [z = - 0.57735026918963, z = 0.57735026918963] >> >> I.e., these numbers are not +-1. >> >> At 03:33 PM 2/19/2013, Dan Asimov wrote: >>> This is not what happens. >>> >>> The limit of the ellipse as c -> 0 is indeed a degenerate ellipse that is precisely the line segment between its foci, +-sqrt(ÃÂ¢ÂÂ¦Ã¢ÂÂ).

2 2

[math-fun] Adjacency matrices (was Re: Fun with maps)
by Keith F. Lynch 20 Feb '13

20 Feb '13

I've been composing a "Fun with maps" followup, but it has grown to unwieldy length. So I'm budding off one part of it, my musings on adjacency matrices, into this email. An adjacency matrix for a graph has a[i][j] = 1 iff vertices i and j are adjacent, i.e. are separated by a single edge. The Nth power of an adjacency matrix gives the number of length-N walks (paths with possible duplication of vertices and edges) between each pair of vertices. To determine whether a set of vertices splits the graph into two (or more) separate pieces when removed, I zero the rows and columns for the vertices in the set, raise the resulting adjacency matrix to successive powers, and take the sum of all the powers. If any entries other than in the rows and columns representing the set of vertices I removed remain zero, then I know the graph has become disconnected. How do I know when to stop taking successive powers? When the number of zeros stops going down. That means I have to count them each time. I've been using this to see whether any states are completely surrounded by another state, whether any states are nestled between two states, and whether any states are hiding in the corner where three states would otherwise meet. I've been doing matrix multiplication in the obvious way. There are faster ways to multiply matrices, but they're only slightly faster, except for matrices far larger than 50 on a side. For a matrix that small, those methods may even be slower. Then I realized that there were ways I could speed things up greatly. I don't actually care how many walks there are between two vertices. All I care is whether there's at least one path, of any length. In fact, those big numbers vex me, since the number of walks can easily exceed the size of a 32-bit integer and wrap around. So I replaced: a[i][k] += b[i][j] * c[j][k]; with a[i][k] |= b[i][j] & c[j][k]; which is much faster. For those who can't read C notation, wherever I was multiplying, I'm ANDing, and wherever I was adding, I'm ORing. Also, instead of adding together the successive powers, I'm ORing them together. Is there a name for this matrix operation? It can't be original with me. Can it? Also, instead of "multiplying" matrices to get higher and higher powers, I can repeatedly "square" them. That way I don't have to count the zeros. If I "square" it six times, that's the 64th power, and since there are fewer than 64 vertices, that has to have found all possible paths. But will the sum of the 1st, 2nd, 4th, 8th, 16th, 32nd, and 64th powers necessarily find all paths? It's only finding all walks of length 1, 2, 4, 8, etc. Depending on the graph, there could be some vertices that can only be reached by a walk with certain lengths. And not just with contrived graphs. I'm pretty sure the DC Metro system is an example. Since it's a bichromatic graph (I wonder if I'm the only person ever to notice that), any round trip will contain an even number of edges. About half the stations can only be reached with a "walk" of odd length. Then I realized that there was a simple solution. Make the main diagonal of the matrix all ones, i.e. create an edge from each vertex to itself. That will ensure that anything that can be reached with a walk of length N can be reached with a walk of length N+1. And I can completely skip the summation steps, and simply use the 64th "power" of the adjacency matrix. ("Power" is in quotes because, as I said, I'm no longer multiplying, I'm ANDing and ORing.) I've coded and tested all of the above, but not what's in the remainder of this message. Also, since those are bitwise operations, I can pack each row of the matrix into a single 64-bit integer, and do a whole row's worth of operations in a single operation. Yes, I supposedly have to read down columns, too, but keep in mind that these matrices are all symmetrical, so whenever I'm supposed to look at the Jth column, I can cheat and use the Jth row instead. Those matrix tricks should give me enough speedup that searching a 50-vertex map for K_5 and K_3,3 would be feasible (assuming I wanted to do that, which I probably don't). Maybe it would run over a weekend instead of running for a year. (Keep in mind that searching for K_5 doesn't mean searching for five vertices each of which are adjacent to the other four, a search which would be very quick. It means searching for five vertices each of which has a path to the other four that doesn't go through any of the other three. (That last sentence should be taken out and shot.) Analogously with K_3,3.)

2 1

[math-fun] big meteor blasts no longer escape notice
by Bill Gosper 20 Feb '13

20 Feb '13

wds> http://ntrs.nasa.gov/search.jsp?R=20110016611 is about the previous largest blast before Chelyabinsk, about 70 kilotons worth of bang near Sulawesi Indonesia. Nobody appears to have directly noticed it, but a worldwide network of "infrasound" detectors did, and apparently every blast of this nature will be detected by same from here on out. ---------- I think NASA should surf harder: https://www.youtube.com/watch?v=iAtqySUimdo --rwg More recent, less convincing: https://www.youtube.com/watch?v=05kzqyg2hEI There's also a bunch of vids on a 26 Sep 11 Argentine fatality. http://www.youtube.com/watch?v=XsWOnTMZaBg Here's a vid by a Russian kid pretty clearly showing the zinc plant not failing until the arrival of the sonic boom: http://www.youtube.com/watch?v=SRSrdOfbnHI Presumably, compression of the domed roof blew out the wall(s): http://rt.com/files/news/meteorite-crash-urals-chelyabinsk-283/photo-user-3… Could the lack of big pieces indicate it was just a big, dirty snowball? Or could the fragmentation of a big rock entail positive feedback? E.g., with a hammer, it's a lot easier to break small rocks than big rocks. (And essentially impossible to break hunks of iron.)

1 0

Re: [math-fun] Q re ellipses in the complex plane
by Henry Baker 20 Feb '13

20 Feb '13

Thanks, Rich! Perhaps I should generalize my question: are there any interesting uses of _ellipses_ (not just circles) in the _complex_ plane ? At 01:28 PM 2/12/2013, rcs(a)xmission.com wrote: >No. >Elliptic functions have two periods, with a non-real ratio. >The periods define a "period parallelogram". >The input is usally scaled so that one period is real, >typically either 1 or 2pi. Interesting special cases arise when >one period is 1 and the other is i or w = 1/2 + i sqrt3 /2. >If I remember correctly, each pargrm must have either two poles >or a double pole (at least) and a matching number of zeros. >Salamin's the expert at this. Abramowitz & Stegun is an OK >beginning introduction. I don't know about DLMF. > >Rich > >--- >Quoting Henry Baker <hbaker1(a)pipeline.com>: > >>Are elliptical regions (those conic sections with 2 foci) in the >>complex plane particularly interesting in the study of "elliptic >>functions" ?? >> >>I don't know enough about elliptic functions to have any insights here.

3 7

[math-fun] Sequence relating to the Erdős–Straus conjecture
by Allan Wechsler 20 Feb '13

20 Feb '13

Let A(n) be the number of ways of expressing 4/n as the sum of three integer reciprocals, where the mere permutation of a sum is regarded as not making a difference. Plainly 4/1 = 4 cannot be expressed as the sum of three reciprocals, so A(1) = 0. 4/2 = 2 = 1/1 + 1/2 + 1/2, and there are no other solutions, so A(2) = 1. 4/3 = 1 + 1/4 + 1/12 = 1+ 1/6 + 1/6 = 1/2 + 1/2 + 1/3; I am pretty sure that A(3) = 3. The Erdős–Straus conjecture is that A(n) > 0 for all n > 1. Of course I wanted to know if A was in OEIS. I calculated a few more terms, and what I had was 0, 1, 3, 3, 2, 8 ... I was pretty confident in my enumeration, so I calculated enough entries, and discovered to my surprise that the sequence was missing. Then I searched for "Straus", and quickly found A192787, which claims to be my A. The trouble is, A192787(4) = 4, and I say A(4) = 3. Bear with me while I list my solutions, and then somebody tell me what I missed. 4/4 = 1, so the problem is to partition 1 into three reciprocals. I have the following solutions: 1/2 + 1/3 + 1/6 1/2 + 1/4 + 1/4 1/3 + 1/3 + 1/3 A192787 seems to be claiming that I missed one. Charles R. Greathouse IV was the sequence author, and I think he's a funster, so, Charles, if you're listening, can you tell me the missing dissection?

6 7

[math-fun] big meteor blasts no longer escape notice
by Warren Smith 19 Feb '13

19 Feb '13

http://ntrs.nasa.gov/search.jsp?R=20110016611 is about the previous largest blast before Chelyabinsk, about 70 kilotons worth of bang near Sulawesi Indonesia. Nobody appears to have directly noticed it, but a worldwide network of "infrasound" detectors did, and apparently every blast of this nature will be detected by same from here on out.

1 0

[math-fun] A192787 (Re: Sequence relating to the Erdős–Straus conjecture)
by Robert Munafo 19 Feb '13

19 Feb '13

Charles, in case you haven't seen this question yet... Replies suggested that 4/4 = 1/1 should be eligible, and if so then 4/4=1/2+1/2 should also; but they miss the requirement that there have to be three terms in the sum. I also think A[4] should be 3. At the very least A192787 should have more explicit examples in the example section. Perhaps we could supply PARI code that actually enumerates the combinations by adding some sort of print statement inside the "if(denominator(c)==1&&c>=b,s++)". ---------- Forwarded message ---------- From: Allan Wechsler Date: Tue, Feb 19, 2013 at 4:36 PM Subject: [math-fun] Sequence relating to the Erdős–Straus conjecture To: math-fun <math-fun(a)mailman.xmission.com> Let A(n) be the number of ways of expressing 4/n as the sum of three integer reciprocals, where the mere permutation of a sum is regarded as not making a difference. Plainly 4/1 = 4 cannot be expressed as the sum of three reciprocals, so A(1) = 0. 4/2 = 2 = 1/1 + 1/2 + 1/2, and there are no other solutions, so A(2) = 1. 4/3 = 1 + 1/4 + 1/12 = 1+ 1/6 + 1/6 = 1/2 + 1/2 + 1/3; I am pretty sure that A(3) = 3. The Erdős–Straus conjecture is that A(n) > 0 for all n > 1. Of course I wanted to know if A was in OEIS. I calculated a few more terms, and what I had was 0, 1, 3, 3, 2, 8 ... I was pretty confident in my enumeration, so I calculated enough entries, and discovered to my surprise that the sequence was missing. Then I searched for "Straus", and quickly found A192787, which claims to be my A. The trouble is, A192787(4) = 4, and I say A(4) = 3. Bear with me while I list my solutions, and then somebody tell me what I missed. 4/4 = 1, so the problem is to partition 1 into three reciprocals. I have the following solutions: 1/2 + 1/3 + 1/6 1/2 + 1/4 + 1/4 1/3 + 1/3 + 1/3 A192787 seems to be claiming that I missed one. Charles R. Greathouse IV was the sequence author, and I think he's a funster, so, Charles, if you're listening, can you tell me the missing dissection? -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com

1 0