September 2008 - mathfun@mailman.xmission.com

Re: [math-fun] A new 3d space filling curve?
by Thomas Colthurst 19 Sep '08

19 Sep '08

On Thu, Sep 18, 2008 at 11:37 PM, Steve Witham <sw(a)tiac.net> wrote: > From: "Thomas Colthurst" <thomaswc(a)gmail.com> >> >> Body-diagonal tours are only impossible if you use dyadic subdivision >> of the cube. For example, if you break up the square into 9 subsquares, >> you can do a tour like >> >> \/\ >> /\/ >> \/\ >> >> where the subsquares are visited in the order >> >> 123 >> 654 >> 789 >> > > If \ looks like this up close: > > --------+ > | > +-------+ > | > +-------- > > (which is what your larger square is doing), > and you put little gaps between the \/'s, > then that's the Peano curve. You are completely right: what I described above is the Peano curve. > > > This can be lifted to a 3d pattern where the 27 subcubes >> get visited in the order >> >> 1 2 3 | 12 11 10 | 25 26 27 >> 6 5 4 | 13 14 15 | 24 23 22 >> 7 8 9 | 16 17 18 | 19 20 21 >> > > Do you mean > > 1 2 3 | 18 17 16 | 19 20 21 > 6 5 4 | 13 14 15 | 24 23 22 > 7 8 9 | 12 11 10 | 25 26 27 > > ? Yes. Sorry for messing that up. -Thomas C > > --Steve >

1 0

Re: [math-fun] A new 3d space filling curve?
by Steve Witham 19 Sep '08

19 Sep '08

>From: "Thomas Colthurst" <thomaswc(a)gmail.com> > >Body-diagonal tours are only impossible if you use dyadic subdivision >of the cube. For example, if you break up the square into 9 subsquares, >you can do a tour like > >\/\ >/\/ >\/\ > >where the subsquares are visited in the order > >123 >654 >789 If \ looks like this up close: --------+ | +-------+ | +-------- (which is what your larger square is doing), and you put little gaps between the \/'s, then that's the Peano curve. >This can be lifted to a 3d pattern where the 27 subcubes >get visited in the order > >1 2 3 | 12 11 10 | 25 26 27 >6 5 4 | 13 14 15 | 24 23 22 >7 8 9 | 16 17 18 | 19 20 21 Do you mean 1 2 3 | 18 17 16 | 19 20 21 6 5 4 | 13 14 15 | 24 23 22 7 8 9 | 12 11 10 | 25 26 27 ? --Steve

1 0

Re: [math-fun] Hilbert curves
by Steve Witham 19 Sep '08

19 Sep '08

Found this page: http://people.csail.mit.edu/jaffer/Geometry/HSFC Pretty much searching for "Butz Hilbert". Jaffer complains that the existing implementations of Butz's multi-dimensional Hilbert curve algorithm 1) are hard to read, 2) take the number of bits of precision as an argument (instead of letting it be whatever the arguments require), and 3) are limited by the precision of the representations they use for distance-along-curve, for instance to 32 bits, for the product (number of dimensions x bits of resolution in each). So, he develops a Scheme algorithm that uses bignums and works "in terms of higher level constructs: Gray-code, lamination, rotation and reflection." This sounds like the right approach to me (although it might need optimizing/obfuscating again in the end), but I'm still having problem 1) at the moment. Here's the main routine (mainly to show its length): (define (integer->hilbert-coordinates scalar rank . nbits) (define igry (integer->gray-code scalar)) (define rnkmsk (lognot (ash -1 rank))) (define rnkhib (ash 1 (+ -1 rank))) (define rank*nbits (if (null? nbits) (let ((rank^2 (* rank rank))) (* (quotient (+ -1 rank^2 (integer-length scalar)) rank^2) rank^2)) (* rank (car nbits)))) (do ((bdxn (- rank rank*nbits) (+ rank bdxn)) (chnk (ash igry (- rank rank*nbits)) (logxor rnkhib (logand (ash igry (+ rank bdxn)) rnkmsk))) (rotation 0 (modulo (+ (log2-binary-factors chnk) 2 rotation) rank)) (flipbit 0 (ash 1 rotation)) (lst '() (cons (logxor flipbit (rotate-bit-field chnk rotation 0 rank)) lst))) ((positive? bdxn) (map gray-code->integer (delaminate-list rank (reverse lst)))))) Further rationale: http://people.csail.mit.edu/jaffer/Geometry/RFMDSFF Also, He develops a Peano-curve-based method that fills all space instead of just a >=0 corner. He measures distance on the curve vs. Euclidean distance for various curves. --Steve

1 0

[math-fun] polynomial questions of Dan Asimov
by James Buddenhagen 19 Sep '08

19 Sep '08

In another thread Dan Asimov asks: << QUESTION: By the way, is there some nice estimate for the maximum value among all real roots, of all monic integer polynomials of degree <= d, having coefficients of absolute value <= N ??? Call this M(d, N). Any good estimates, or asymptotic ones? >> I only looked a little at this, but the polynomial: x^d - N x^(d-1) - N x^(d-2) - ... - Nx - N (all terms negative but the first) has a real root very near N+1 and that may be as large as the real root can be. Note that subtracting 1 from this polynomial only changes the roots a little but the resulting polynomial has (x - (N+1)) as a factor. Dan later asks a similar question regarding the difference between the largest and smallest real roots. For that, consider: x^d - N x^(d-1) - N x^(d-2) + N x^(d-3) - N x^(d-4) + ... (first 2 terms after leading term are negative after which terms alternate in sign, last term is + or - N depending on parity of d). This polynomial has roots near -2 and N+1 suggesting the largest spread of real roots is around n+3. I did not try to prove these are best possible, but they may be. Jim Buddenhagen

1 0

[math-fun] A new 3d space filling curve?
by Thomas Colthurst 18 Sep '08

18 Sep '08

Inspired by the recent thread on Hilbert curves, I decidedto think about cube filling curves that used a face diagonal as their basic move. For those of you who like to play along at home, here's an elementary formulation of the problem: Given 8 identical cubes, each marked with a line from (0,0,0) to (1,1,0), can you put them together into the [0,2]^3 cube in such a way that the marked lines form a path from (0,0,0) to (2,2,0) ? [intentional white space to hide solution] In the list below, I've identified Cubes by their vertex closest to the origin. Cube Path Start Path End ----------------------------------------- (0,0,0) (0,0,0) (1,0,1) (1,0,0) (1,0,1) (1,1,0) (0,1,0) (1,1,0) (1,2,1) (0,1,1) (1,2,1) (0,1,1) (0,0,1) (0,1,1) (1,0,1) (1,0,1) (1,0,1) (2,1,1) (1,1,1) (2,1,1) (1,2,1) (1,1,0) (1,2,1) (2,2,0) I would be interested if anyone could come up with something more pretty, either in terms of symmetry or in having fewer junction points where the path touches itself. Also, has anyone seen this space filling curve before? -Thomas C

4 4

Re: [math-fun] A new 3d space filling curve?
by Dan Asimov 18 Sep '08

18 Sep '08

Fred Lunnon writes: << . . . A similar tour based on body-diagonals --- rather than face-diagonals or edges --- is easily seen to be impossible. But exactly why should this be so; and what is the corresponding situation for d-space? >> And what about similar tours in the n-torus R^n / Z^n ? --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] "Very linear" lambda calculus
by Mike Stay 18 Sep '08

18 Sep '08

I haven't seen any questions like this on the list before, but I thought I'd try: Is there a nice characterization of the lambda terms in the span of B = \xyz.x(yz) and I = \x.x (where \ means lambda)? Both of these are linear (every input is used exactly once) and do not permute the order of their inputs, but it's not clear to me how to show that all such lambda terms are in the span. If all such terms are not in the span, what extra restrictions are there on the form of the terms? -- Mike Stay - metaweta(a)gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com

1 0

Re: [math-fun] Combinatorial Designs, maybe
by Dan Asimov 18 Sep '08

18 Sep '08

P.S. Um, it seems clear that the collections of subsets R, C are maximal w.r.t. the symmetry I asked about, since any permutations P_r, P_c, and P_rc determines uniquely a permutation P of the set S. _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Combinatorial Designs, maybe
by Dan Asimov 18 Sep '08

18 Sep '08

Ed's post reminded me of one huge area of ignorance of mine (among many): Given a set S having n^2 elements, we can of course arrange them in an n x n square and pick out two collections R, C, of subsets of size n: the rows and the columns. These have the nice property that for any permutations P_r and P_c of R and C, respectively, AND for any (i.e., either) permutation P_rc of {R,C}, there is a permutation P of S that simultaneously implements P_r, P_c and P_rc (meaning the composition of these). ***QUESTION: For a given n, are the collections R and C *maximal* with respect to this kind of symmetry? Or a bit more flexibly, is 2 the largest number of collections of subsets of S of size n that can have this kind of hierarchical symmetry? (E.g., can there be 3 collections of subsets of S: (X_1, X_2, X_3} such that for any permutations P_1, P_2, P_3 of X_1, X_2, X_3, respectively -- AND any permutation of {X_1, X_2, X_3} (among 6) -- then there is a permutation P of S that simultaneously implements these ?) (Similar questions can be asked of a set of size n^k -- arrange its elements as an n^k cube and start with the symmetry of all k subsets of parallel row-analogues (with n^(k-1) in each set) -- . . . and even go further with k^(n-r) subsets of orthogonally oriented parallel r-cubes, of size k^r -- but I'll restrain myself.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] a(n) = PrimePi(a(n+1))
by Eric Angelini 17 Sep '08

17 Sep '08

> In fact, it's http://www.research.att.com/~njas/sequences/A007097 ... Oh yes, Michael -- thanks ! (me = wrong hit due to my leading zero)

1 0