April 2008 - mathfun@mailman.xmission.com

Re: [math-fun] a perplexing asymmetry
by James Propp 08 Apr '08

08 Apr '08

I wrote >Naively, one would expect the difference between f(n) and n/2 >to be positive as often as it is negative. Taking one step beyond naive arguments, I can make up a sort of half-convincing story about the asymmetry: Take a snapshot of the system after t steps, and let a_n be the number of sites occupied by exactly n particles. For r = -1, 0, and 1, let A(r) be the sum of a_n for all n congruent to r mod 3. If t is on the order of log n or larger, we'll see a_1 > a_2 > a_3 > ..., so A(1) = a_1 + a_4 + a_7 + ... > a_2 + a_5 + a_8 + ... = A(-1), which means that the rounding down of numbers of the form k + 1/3 has more impact that the rounding up of numbers of the form k - 1/3, so there's an extra rightward bias, and less mass disappears from the system than one might expect from the mass-flow approximation. But this story can't be *that* true, since sometimes f(n) *does* equal n/2. So how come f(n) is never less than than n/2? (Or maybe one does get f(n) < n/2 for larger values of n than I've looked at.) The n/2 cut-off is still quite mysterious to me! Here are some other things I'd like to know: (1) How big can |f(n) - n/2| be? I suspect it's O(log n). (For n up through 500, f(n) - n/2 ranges between 0 and 7/2.) (2) For how many consecutive n's can f(n) take on the same value? Conversely, for how many consecutive n's can f(n) steadily increase by 1? (It's easy to show that f(n+1) is either f(n) or f(n)+1.) (3) What's the best way to compute f(n)? It would be good to know ahead of time two numbers L(n) and T(n) such that if you replace the infinite one-dimensional lattice {1,2,3,...} by the finite interval {1,2,3,...,L(n)} and run the arithmetic rule for T(n) steps, with particles that leave 1 going leftward being absorbed at 0 and particles that leave L(n) going rightward being ignored, then f(n) is just n minus the number of particles that have been absorbed at 0 by time T(n). It would also be good to have a proof of the empirical assertion that if the number of particles at 0 remains constant for three successive time steps, it never changes again. I wrote a twelve-line recursive Mathematica program to compute f(n), but it wasted too much time recomputing things, and when I replaced "f[n_] := ..." by "f[n_] := f[n] = ..." the way you're supposed to, it introduced all kinds of flakey behavior that I don't understand, so I eventually gave up in defeat --- though it's painful to have spent time coming up with a really meaty Mathematica expression like Join[Drop[Map[Function[x, Round[x/3]], L], 1], {0, 0}] + Prepend[Map[Function[x, Round[(2*x)/3]], L], 0] and then find out you can't fix the program that houses that meaty expression at its center! If any of you want to tinker with my code and get it to work, I'd be glad to send it to you. Incidentally, if n is a power of 2, f(n) has a nice interpretation in terms of modeling of random walk on a finite-precision binary computer. To see this, let's look at the case n = 8 again, but this time we'll add an extra column at the left to keep track of the particles absorbed at 0, and we'll divide all the entries in the table by n = 8: 0 1 0 0 0 ... 3/8 0 5/8 0 0 ... 3/8 1/4 0 3/8 0 ... 1/2 0 1/4 0 1/4 ... ........................... We can understand this as an attempt to simulate the exact mass-flow 0 1 0 0 0 ... 1/3 0 2/3 0 0 ... 1/3 2/9 0 4/9 0 ... 11/27 0 8/27 0 8/27 ... ............................... using three-bit fixed-point binary arithmetic. And this mass flow is precisely the mass-flow associated with a biased random walk in which one steps to the right with probability 2/3 and to the left with probability 1/3. (If you're wondering how I came up with this numerical dynamical system, now you know: I was studying round-off error for this kind of numerical simulation of heat/mass/probability flow.) Jim Propp

1 0

[math-fun] a perplexing asymmetry
by James Propp 08 Apr '08

08 Apr '08

Here's a sequence I'd like to know more about: (*) 1,1,2,3,3,4,4,4,5,6,6,7,8,8,9,9,9,... It arises from a simple numerical dynamical sytem that describes how a sharply concentrated distribution of particles spreads out as it drifts off to the right. The nth term (which I'll call f(n)) is about n/2, but there's an asymmetry in the behavior of f(n) - n/2 that tells us something about the ways in which which round-off errors can build up instead of cancelling out. To find the nth term, put n particles at location 1 and then start moving particles on {1,2,3,...}, according to the rule that at each discrete time step, nearly 2/3 of the particles at any given location move one step to the right and nearly 1/3 move one step to the left --- where "nearly" means "rounded to the nearest integer". More specifically, if a site has 3k+i particles, with i = -1, 0, or 1, then 2k+i of those particles move one step to the right and k of them move one step to the left. Important special case: Particles that move to the left from *1* fall out of the system, or if you prefer, get absorbed at 0. It can be shown that eventually none of the sites 1,2,3,... has more than 1 particle, and all these particles move in lock-step forever after, each moving one step to the right at each time-step. Define f(n) as the number of particles forming this train. Then (*) is just the sequence f(1),f(2),f(3),... For instance, here's how we compute that f(8) = 4: 8 0 0 0 0 0 0 0 0 ... 0 5 0 0 0 0 0 0 0 ... 2 0 3 0 0 0 0 0 0 ... 0 2 0 2 0 0 0 0 0 ... 1 0 2 0 1 0 0 0 0 ... 0 2 0 1 0 1 0 0 0 ... 1 0 1 0 1 0 1 0 0 ... 0 1 0 1 0 1 0 1 0 ... 0 0 1 0 1 0 1 0 1 ... ................................................. If fractional particles were allowed, and if every particle were to split into 2/3 of a particle moving to the right and 1/3 of a particle moving to the left (in this case, it makes sense to switch to a mass-flow metaphor), then it is not hard to show that over time, exactly half of the mass disappears from the system (by disappearing to the left) while half of the mass travels off to the right. So, we expect f(n) to be close to n/2; and by and large, it is. But to me, the big surprise about f(n) is that it never falls short of n/2 (at least not for values of n up through 500)! Indeed, the only values of n up to n=500 for which f(n) equals n/2 are 2, 8, 48, 50, and 200; for all other n up to 500, f(n) is strictly greater than n/2. Naively, one would expect the difference between f(n) and n/2 to be positive as often as it is negative. So, what's going on here? Jim Propp

1 0

[math-fun] Space-filling curves
by Jason 08 Apr '08

08 Apr '08

I think I have a new integer sequence for the OEIS (although please tell me if it seems insufficiently interesting). But first, a question: Is there a standard way to encode the cardinal directions as integers? I picked mine since it's both the standard clockwise N,E,S,W and because in this particular case it encodes the first three directions as 1,2,3. Encode up=1, right=2, down=3, left=4. The sequence is the directions of travel of a Hilbert curve as it leaves the origin. I rather arbitrarily used this as the shape of the second iteration. Here again, maybe someone can tell me if there's a more conventional form. p m l k o n i j b c h g a d e f ^ Given these two conventions, the sequence would begin: 1,2,3,2,2,1,4,1,2,1,4,4,3,4,1,... [a->b c d e f g h i j k l m n o p] Can somebody point me at the right vocabulary for thinking about the mappings of 1234 to NESW? It's rather arbitrary, and if your compass is rotated from mine so that you think 2341=NESW, 3412=NESW and 4123=NESW, you'll still get a Hilbert curve, but if you use 1324=NESW, your lines won't connect when you use my sequence. So, there's a relationship inherent in those rotations such that 3=-1 and 2=-4, and that makes me think that group theory ought to be involved. What about sequences of symbols which are totally, er, unrelated? Unordered? That is, assume I have a sequence a,b,c,b,b,d,a that I consider equivalent to the set of all sequences f(a),f(b),f(c),f(b),f(b),f(d),f(a) in which f() is a bijection from {a,b,c,d}->{a,b,c,d}. (In other words, totally arbitrarily chosen symbols.) Would it make sense to want an Online Encyclopedia of such sequences in which the symbols don't have a relationship like the integers do? Or is there a way to canonicalize such sequences so that we can express them uniquely as integers? Perhaps we could force the convention that the symbols must be numbered in order, so that 1 is always the first number to appear in the sequence and that the next non-1 symbol must be 2, etc.? (Sorry if this is an excessivly elementary subject to be asking about)

3 2

[math-fun] separable diffeqs
by James Propp 07 Apr '08

07 Apr '08

A standard method taught in calculus classes is the method of solving separable differential equations; namely, we solve dy/dx = f(x) g(y) by writing it as (1/g(y)) dy = f(x) dx and then writing / / \ (1/g(y)) dy = \ f(x) dx / / But does anyone know of an appropriately general THEOREM that validates this method? That is, can anyone point me to a theorem (whose statement should be accessible to bright first-year college students) saying that if f and g are functions satisfying certain conditions, then there is a one-parameter family of solutions to dy/dx = f(x) g(y) obtained by the formula y = H^{-1}(F(x)+C), where F is an antiderivative of f, C is an arbitrary constant, and H is an antiderivative of 1/g(y)? Note that if the antiderivative of 1/g(y) isn't invertible, then we're in trouble since H^{-1} won't exist. Though now that I think of it, that won't happen if g(y) is continuous and stays away from 0. I'd like to tell my students a correct theorem, not just give them a hocus-pocus that works (or usually works). Come to think of it: does anyone know of any examples for which naive application of separation of variables gives wrong results, say by introducing spurious solutions or neglecting valid ones? A correct theorem would attend to domains of existence, and maybe would include a uniqueness claim as well. I've been using one of Stewart's calculus texts, and on the whole I've approved of his compromises between the need for accessibility and the need for rigor, but on the topic of separable differential equations he seems to be throwing up his hands and just saying "Here's how you solve it, kids". Jim Propp

3 2

Re: [math-fun] separable diffeqs
by James Propp 07 Apr '08

07 Apr '08

Thanks, Gareth! >This all seems rather pedestrian. You probably had something >subtler in mind... Not necessarily. I just didn't want to spend time re-inventing the wheel when smart folks who lived a century ago probably spent some time figuring out what theorem along these lines strikes the best (i.e. most useful) compromise between strong-hypothesis-and- strong-conclusion and weak-hypothesis-and-weak-conclusion. Jim

1 0

[math-fun] 2p + 3q, 2p - 3q prime infinitely often
by Robert Baillie 05 Apr '08

05 Apr '08

the april american mathematical monthly has an article "prime number patterns" by andrew granville with lots of interesting stuff in it. my favorite result from the article is that there are infinitely many primes p and q such that q are also prime. this is the first result like this that i've ever heard of. it's expected based on computations, of course, but i think it's pretty amazing that this can now be proven. unfortunately, things like this are still too difficult to prove: there are infinitely many primes p such that 2p + 1 is also prime there are infinitely many primes p such that p + 2 is also prime a preliminary version of the paper is here: http://www.dms.umontreal.ca/~andrew/PDF/PrimePattMonthly.pdf the result i quoted above is in section 5. bob baillie

2 2

[math-fun] Five enigmas
by Christian Boyer 05 Apr '08

05 Apr '08

In my paper just published in Pour La Science, the French edition of Scientific American, I offer 100 euros + a bottle of champagne on each of these 5 enigmas. Who can construct, or prove the impossibility: 1) 3x3 magic square using 7 or more squared integers different of this only known example (and of its rotations, symmetries and k² multiples): 373² 289² 565² 360721 425² 23² 205² 527² 222121 2) 5x5 bimagic square (using distinct integers) 3) 3x3 semi-magic square of cubes (using distinct positive cubed integers) 4) 4x4 magic square of cubes (using distinct positive cubed integers) 5) ?x?x? multiplicative magic cube using ?^3 distinct integers all smaller than 364. The value of ? is free. Christian. PS on 1): nobody knows a 3x3 magic square of squares. This sub-problem and prize offered since 2005 in the Math Intelligencer should be "easier". PS on 3): "semi-magic" means that we don't take care of the diagonals. PS on 3) and 4): 3x3 magic square of cubes proved impossible.

1 0

[math-fun] Divisors of polynomials
by Dan Asimov 04 Apr '08

04 Apr '08

Playing around with the cyclotomic polynomial P(n) = n^2 + n + 1 I noticed that there are many primes that cannot divide this quantity for any n (e.g., 5, 11). I suppose this is probably related to quadratic reciprocity. Can it be determined just which primes can't divide n^2 + n + 1 for any n ? What about other polynomials, cyclotomic and otherwise? --Dan E.g.: For 5, the residues of P(n) are 1,-2 (twice each) and 2 (once). For 11, the residues of P(n) are 1,2,3,-1,-4 (twice each) and -2 (once). Why these funny patterns? _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

Re: [math-fun] Topology of the universe
by Dan Asimov 04 Apr '08

04 Apr '08

Making some big assumptions -- ignoring possible singularities in spacetime, and assuming that spacetime has a spatial cross-section -- then the idea of a spatial universe might make sense. As long as it's locally 3-dimensional, then globally it would be what's called a 3-manifold (which is to 3 dimensions what a surface is to 2 dimensions). If further the universe is finite and without boundary, this would be a "compact" 3 manifold; if it's all in once piece, then it would even be "connected". Otherwise, it's just some 3-manifold. Taking your assumption of "uniform at large scales" to mean geometrically homogeneous, then the universe would be modeled on one of the 8 geometries in Bill Thurston's Geometrization conjecture, now apparently a theorem as proved by Grigori Perelman. If further the universe is geometrically isotropic, I think that would imply it has approximately constant (sectional) curvature. The 3-manifolds of constant positive curvature and constant 0 curvature have been fully classified. The 3-manifolds of constant negative curvature -- the "hyperbolic" ones -- are by any standard the most numerous among these three possibilities, and there are many books and papers devoted to them. --Dan --------------------------- Dave Dyer wrote: << I was thinking about a simulated 3-d map of the universe, based on Hubble deep field images, and it occurred to me that a 3-d map can't really be right, based on established cosmological models. If the universe is uniform at large scales, and we are not serindipitously located near the center, then the overall topology of the universe must be some strange non-intuitive thing. What are the possible maths of such a thing? >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] More trig sums & prods over a period
by Bill Gosper 04 Apr '08

04 Apr '08

rwg>It's pretty clear that any product or sum over a period of a rational function of trigs comes out in closed form. You can interconvert such products and sums via trig, calculus, and generating function hacks. The key identity is just prod(a-b*%e^(2*%i*%pi*k/n),k,1,n) = a^n-b^n; n 2 %i %pi k /===\ ---------- | | n n n | | (a - b %e ) = a - b , | | k = 1 from which follows prod(%e^(4*%i*%p i*k/n)*r-%e^(2*%i*%pi*k/n)*q+p,k,1,n) = -(sqrt(q^2-4*p*r)+q)^n/2^n-(q -sqrt(q^2-4*p*r))^n/2^n+r^n+p^n; n 4 %i %pi k 2 %i %pi k /===\ ---------- ---------- | | n n | | (%e r - %e q + p) = | | k = 1 2 n 2 n (sqrt(q - 4 p r) + q) (q - sqrt(q - 4 p r)) n n - ----------------------- - ----------------------- + r + p . n n 2 2 Identities so constructed can then be extended via my nonlocal derangement formulae, which blend each term with all the rest, along with an additional, essentially arbitrary sequence, which, if also trigonometric, invites reduction to closed form via the regular polygon formulae. The devil is in the details. Using just c_k := cos(a + 2 pi k/n) for the arbitrary sequence, the derangement of the easy result sum(sec(2*%pi*k/n+a),k,1,n) = n*sin(%pi*n/2)^2*cot((%pi/2-a)*n/2)*cs c((a*n+%pi*n/2)/2)^2/2; n ==== \ 2 %pi k > sec(------- + a) = / n ==== k = 1 %pi %pi n (--- - a) n a n + ----- 2 %pi n 2 2 2 n sin (-----) cot(-----------) csc (-----------) 2 2 2 ------------------------------------------------ 2 required deriving the identity prod(cos(4*%pi*j/n+2*a)/2-b*cos(2*%pi*j/n+a)+3/2,j,1,n) = cos(2*a *n)/2^(2*n-1)-chebyshev_t[n]((sqrt(2-b)-sqrt(b+2))/2) *chebyshev_t[n]((sqrt(b+2)+sqrt(2- b))/2)*cos(a*n)/2^(2*n-3)+ (chebyshev_t[n](sqrt(4-b^2)+1)+chebyshev_t[n](1-sqrt(4-b^2))+ 1)/2^(2*n-1) n 4 %pi j /===\ cos(------- + 2 a) | | n 2 %pi j 3 | | (------------------ - b cos(------- + a) + -) = | | 2 n 2 j = 1 cos(2 a n) sqrt(2 - b) - sqrt(b + 2) ---------- - T (-------------------------) 2 n - 1 n 2 2 sqrt(b + 2) + sqrt(2 - b) 2 n - 3 T (-------------------------) cos(a n)/2 n 2 2 2 T (sqrt(4 - b ) + 1) + T (1 - sqrt(4 - b )) + 1 n n + -----------------------------------------------, 2 n - 1 2 which, at least in my state of dotage, was *ridiculously* hard. (Three Macsyma notebooks, thousands of steps, mostly into intractable algebra, spread over several weeks.) Yet it is clear that this result could be generalized to arbitrary constants replacing, 1/2, 3/2, 2a, and even to more addends with 6 pi j and 8 pi j ... . Much less clear is how, while avoiding tsunamis of algebraic uglitude on the rhs. Anyway, applying this to the sec sum gives, for n > 1, the somewhat homely sum(sin(2*%pi*k/n+a)*(4* chebyshev_t[n](-(sqrt(cos(2*%pi*k/n+a)+2)-sqrt(2-cos(2*%pi*k/n+a)))/2) *chebyshev_t[n]((sqrt(cos(2*%pi*k/n+a)+2) +sqrt(2-cos(2*%pi*k/n+a)))/2)*cos(a*n) -chebyshev_t[n](sqrt(4-cos(2*% pi*k/n+a)^2)+1) -chebyshev_t[n](1-sqrt(4-cos(2*%pi*k/n+a)^2))),k,1,n) = n^2*sin(%pi*n/2)^2*sin(2*a*n)*cot((a-%pi/2)*n/2)*csc((a+%pi/2)*n/2)^2/2 n ==== \ 2 %pi k > sin(------- + a) (4 cos(a n) / n ==== k = 1 2 %pi k 2 %pi k sqrt(cos(------- + a) + 2) - sqrt(2 - cos(------- + a)) n n T (- -------------------------------------------------------) n 2 2 %pi k 2 %pi k sqrt(cos(------- + a) + 2) + sqrt(2 - cos(------- + a)) n n T (-------------------------------------------------------) n 2 2 2 %pi k - T (sqrt(4 - cos (------- + a)) + 1) n n 2 2 %pi k - T (1 - sqrt(4 - cos (------- + a)))) n n %pi %pi (a - ---) n (a + ---) n 2 2 %pi n 2 2 2 n sin (-----) sin(2 a n) cot(-----------) csc (-----------) 2 2 2 = ------------------------------------------------------------. 2 So we get sums/prods over periods of some algebraic functions of trigs as well as rational. --rwg (Reminder: T_n(x) = cos(n acos x) = cosh(n acosh x) = 2 x T_n-1 - T_n-2, T_0(x)=1, T_1(x)=x. T_n(T_m(x)) = T_nm(x), so, e.g. T_(n/2)(x) := T_n(sqrt((x+1)/2)) = sqrt((T_n(x)+1)/2) .) --------------------------------- You rock. That's why Blockbuster's offering you one month of Blockbuster Total Access, No Cost.

3 3