June 2003 - mathfun@mailman.xmission.com

[math-fun] What's your proof?
by David Wilson 12 Jun '03

12 Jun '03

Prove the following: If a polygon in R^2 has an odd number of equal-length sides, it has a nonrational vertex (not in Q^2). I just wanted to know if there was a proof very different from my own.

4 11

Re: Correction Re: [math-fun] Problem about tiling regular 2n-gon with rhombi
by reid＠math.arizona.edu 12 Jun '03

12 Jun '03

> > PUZZLE: > > Given a rhombus tiling of a 2n-gon (so that each polygon edge is a rhombus > > edge), show that the number of rhombi is determined by n. > >> > > As Michael Kleber and George Hart have (perhaps inadvertently) pointed out, I > neglected to mention (except in the Subject line) that the 2n-gon is supposed > to be regular. > > For a straightforward generalization to parallelograms, one need only assume > that the 2n-gon is convex and has n pairs of parallel sides. i think you need to say "n pairs of parallel *and equal* sides". mike

2 1

Correction Re: [math-fun] Problem about tiling regular 2n-gon with rhombi
by asimovd＠aol.com 11 Jun '03

11 Jun '03

I wrote: << > PUZZLE: > Given a rhombus tiling of a 2n-gon (so that each polygon edge is a rhombus > edge), show that the number of rhombi is determined by n. >> As Michael Kleber and George Hart have (perhaps inadvertently) pointed out, I neglected to mention (except in the Subject line) that the 2n-gon is supposed to be regular. For a straightforward generalization to parallelograms, one need only assume that the 2n-gon is convex and has n pairs of parallel sides. --Dan

1 0

RE: [math-fun] of graphs and grogs
by Andy Latto 11 Jun '03

11 Jun '03

Interesting problem! I think I have a deterministic construction, although the proof that it satisfies (c) involves a huge amount of hand-waving. It satisfies (a), (b), (c), and (d), though not (e) or the "grog condition". I agree that it should be possible to satisfy the grog condition as well, though I'm less sure about (e); the sort of construction I use would result in "crystal defects" in what is mostly a square lattice. Want to get together for lunch sometime? If you're willing to travel up here (near the Burlington Mall), there's a nice Thai place. Andy

1 0

RE: [math-fun] What's your proof?
by Andy Latto 11 Jun '03

11 Jun '03

> -----Original Message----- > From: John Conway [mailto:conway@Math.Princeton.EDU] > Sent: Wednesday, June 11, 2003 4:40 PM > To: math-fun > Subject: Re: [math-fun] What's your proof? > > > On Wed, 11 Jun 2003, Fred W. Helenius wrote: > > > At 09:26 AM 6/11/03, John McCarthy wrote: > > >A polygon can be scaled to have vertices at lattice points > if and only > > >if all its angles have rational tangents. > > > > I don't think so. That would mean there was a lattice-point regular > > octagon, but there isn't, as JHC has just confirmed. For another > > example, consider a parallelogram with angles that are alternately > > arctan(2) and arctan(-2), and with sides alternately 1 and pi. The > > tangents are rational, but lattice-point distances can't be in the > > ratio 1:pi. > > But the angle of a regular octagon DOESN'T have a rational tangent. > > The "rational tangents" condition is exactly right. I think words are being used in two different ways. If ABCDEFGH is a regular octagon, the angle ABC is 3pi/4, which has tangent -1, which is rational. But the angle ABD, for example, does not have a rational tangent, which shows that triangle ABD, and therefore the octagon, cannot be scaled to lattice points. I think the intended criterion is that a set of points can be scaled to be lattice points just if the angle formed by any 3 of them has a rational tangent. Fred's example fails to meet this criterion because the angle formed by a side and a diagonal of the parallelogram has an irrational tangent. Andy Latto andy.latto(a)pobox.com

1 0

[math-fun] of graphs and grogs
by James Propp 11 Jun '03

11 Jun '03

What is known about plane graphs (i.e., graphs with a specified imbedding in the plane) with the following properties? (a) The graph is connected. (b) The number of vertices within Euclidean distance R of the origin grows like a constant times R^2. (c) As the Euclidean distance between vertices goes to infinity, the ratio between the Euclidean distance and the graph-theoretic ("Kevin Bacon") distance goes to 1. Property (c) is the important one. Properties (a) and (b) are included only to rule out trivial examples that aren't in keeping with the underlying spirit of the question (which is to find a discrete plane graph from which the Euclidean metric of R^2 can be reconstructed, at least in the large --- what one might call an "asymptotically Euclidean" plane graph). My guess is that there are random constructions that yield such a graph with probability 1, but that deterministic constructions that look like they do the job are harder to come by, and that deterministic constructions that can be _proved_ to do the job are harder still to come by. I suspect that one can find such a graph that also satisfies the following two conditions: (d) There is a universal bound on the Euclidean distance between two vertices that are connected to each other. (e) The vertices form an infinite square lattice. A more difficult problem would be to find an infinite graph of this kind that admits a finite-state local construction procedure. Let me not be too precise about what I mean by this, since there are several possible definitions, and I'm not 100% sure that they're equivalent. But the idea, on an informal level, is to build up an asymptotically Euclidean network of "sessile grogs", starting from just one sessile grog, where a sessile grog (1) lives in the plane, (2) can't move, (3) has limited computational power, (4) has limited-range telepathy, and (5) can create other sessile grogs nearby, each of which also satisfies (1)-(5). If one could do this, one might liberate the grogs from the plane and give a completely non-geometric version of grog-life in which abstract grogs, starting from one Ur-Grog, create a network whose large-scale metric properties are just like those of R^2. (By the way, "Sessile Grogs" are inhabitants of Larry Niven's fictional "Known Space" universe.) Jim Propp

1 0

[math-fun] 3 notes from Victor Miller
by Richard Schroeppel 11 Jun '03

11 Jun '03

Victor Miller accidentally sent these to the old Math-Fun address. I disabled forwarding to the new address a few months ago, because of too much spam. The posting address is math-fun(a)mailman.xmission.com Rich ---------------------- To: math-fun(a)CS.Arizona.EDU Subject: Name for a classical invariant From: victor(a)idaccr.org (Victor S. Miller) Date: Mon, 09 Jun 2003 16:49:05 -0400 The well-known structure theorem for finite abelian groups (due, I found, to Kronecker) says that to every such group there are a unique set of elementary divisors 1 ne e_1 | e_2 | ... | e_t. The question is what is t -- the number of elementary divisors -- called? I had been calling it the "rank", but that can't be right, since rank is reserved for the number of generators of infinite order in a finitely generated abelian group. Alternatively t is also max_p dim (A/pA), where dim denotes the vector space dimension over GF(p). Victor ---------------------- To: math-fun(a)CS.Arizona.EDU Subject: Re: [math-fun] a prime in each row? From: victor(a)idaccr.org (Victor S. Miller) Date: Tue, 10 Jun 2003 12:11:03 -0400 As pointed out by others, even assuming the Riemann Hypothesis, one can't prove that intervals like [x,x+C \sqrt{x}] contain any primes. However, there are positive results in this area. One of the most interesting is by Pat Gallagher, "On the distribution of primes in short intervals", Mathematika v. 23 (1976) pp 4-9. In this paper he proves that if one assumes a uniform version of the Hardy-Littlewood prime d-tuple conjecture (given d_1, ..., d_r, there is a constant C_d such that the number of n <= X for which n+d_1, ..., n+d_r are all prime is asymptotic to C_d X/(log X)^r) that prime gaps are Poisson distributed. That is, if P_k(h,N) = the number of intervals [n,n+h] with n <= N containing exactly k primes, then P_k(h,N) is asymptotic to N exp(-\lambda) \lambda^k/k! where h is asymptotic to \lambda log(N). There are also results (I forget where right now), that if one defines an x to be "bad" if [x,x+sqrt{x}] contains fewer than 0.5 * sqrt{x}/log(x) primes, then the number of bad x <= X is o(X) (there's something more specific known here, but I don't recall what it is). -- Victor S. Miller | " ... Meanwhile, those of us who can compute can hardly victor(a)idaccr.org | be expected to keep writing papers saying 'I can do the CCR, Princeton, NJ | following useless calculation in 2 seconds', and indeed 08540 USA | what editor would publish them?" -- Oliver Atkin ---------------------- To: math-fun(a)CS.Arizona.EDU Subject: Re: [math-fun] a prime in each row? From: victor(a)idaccr.org (Victor S. Miller) Date: Tue, 10 Jun 2003 12:28:26 -0400 I should also add that a great paper to read on this is by Andrew Granville "Harald Cramer and the distribution of prime numbers" available at http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer… It is also published in the Scandanavian Actual Journal, but that seems a bit obscure. It gives a comprehensive survey of what's known in the field about distribution of primes in short intervals. -- Victor S. Miller | " ... Meanwhile, those of us who can compute can hardly victor(a)idaccr.org | be expected to keep writing papers saying 'I can do the CCR, Princeton, NJ | following useless calculation in 2 seconds', and indeed 08540 USA | what editor would publish them?" -- Oliver Atkin

2 1

[math-fun] Borromean Rings
by David Wilson 10 Jun '03

10 Jun '03

I thought it was kind of neat that Borromean rings cannot be formed using circular rings (of equal or differing sizes). A related question: Given three rigid rings which are not all circular and are reasonably smooth locally, is it always possible to form Borromean rings? I was inclined to think this was true, but then I thought it might not be possible if the rings were sufficiently tangled up that any attempt to form Borromean rings would result in a more complicated linkage. Is this question easier if we require the rings to be planar?

1 0

[math-fun] A005186
by David Wilson 10 Jun '03

10 Jun '03

I believe I have identified the 1.264 mentioned in the formula for A005186. Let c be the Collatz function, that is c(n) = n/2 if n even 3n+1 if n odd We then have c^-1(n) = {2n} if n == 0, 1, 2, 3, or 5 (mod 6) {2n, (n-1)/3} if n == 4 (mod 6) Assume that in a large set of positive integers == 4 (mod 6), (n-1)/3 will be congruent to 1, 3, or 5 (mod 6) with equal likelihood. Then, if S is a large set of positive integers, and if v_k (0 <= k <= 5) is the number of integers in S congruent to k (mod 6), and M is the 6x6 matrix 1 0 0 1 0 0 0 0 0 0 1/3 0 0 1 0 0 1 0 0 0 0 0 1/3 0 0 0 1 0 0 1 0 0 0 0 1/3 0 and w = M v, then w_k should give a reasonable approximation to the number of integers == k (mod 6) in c^-1(S). This means that for large n, we might expect A005186(n+1)/A005186(n) to be near the large eigenvalue of M. By brute force, I found the large eigenvalue of M is about 1.26376261582, close to the reported 1.264. I believe that this is in truth (3+sqrt(21)/6 (thanks to Plouffe's inverter), but I don't have the matrix weaponry to prove it.

2 1

Re: [math-fun] Car talk puzzler
by Dan Hoey 10 Jun '03

10 Jun '03

I wrote: > I haven't got a proof, but I suspect 2N-3 crossings is always best. I still haven't proved anything, but I wrote a brute-force program, and I'm beginning to suspect there's less here than meets the eye! Namely, that for N>1 there are essentially floor((N-2)/2) strategies, depending on how many of a_(n-1), a_(n-3), ..., a_(3 or 4) are greater than 2a_2 - a_1. Then you do 1 and 2 across, 1 back, two largest across, 2 back, that many times, and 1 and largest across, 1 back for the rest, plus a final 1 and 2 across. I've been trying to figure out a way of making this nontrivial, but it starts getting baroque. You have N guys and a (J,K) litter--a litter that holds J guys and needs K other guys to carry it, traveling at the speed of the slowest bearer.... Dan

1 0