User - MathOverflow

Answer by davidcary for How to shuffle a deck by parts?

2010-07-22T00:15:16Z

Assuming you want a practical answer to "I have too many cards to hold in my hands at once; how do I shuffle them reasonably well in a relatively short amount of time?", you might want to consider a "parallel shuffle", distributing the work over several players in hopes that we can get an adequately shuffled deck in less wall-clock minutes than a single-person shuffle, even if it requires more total operations and player-minutes than a single-person shuffle.

I am reminded of the "FFT butterfly diagram" used in digital signal processing and the "Omega Network" used in some computer clusters, based on the "perfect shuffle interconnection".

http://www.ece.ucsb.edu/~kastner/ece15b/project1/fft_description_files/image032.jpg

http://github.com/vijendra/Omega-network/raw/master/16X16.png

Parallel shuffle-deal-shuffle algorithm: (for $k \le n$)

somehow give k players n cards each (either grab a block of n cards off the top for each player, or evenly deal the cards to the k players)
shuffle: each of the k players uniformly shuffles their sub-deck of n cards
deal: each of the k players evenly deals -- face down -- her sub-deck to the k other players (including herself). Equivalently, each player breaks her sub-deck into k equal sub-sub-decks, and distributes one sub-sub-deck to each player (including herself). After all the players have dealt, each player gathers her cards (a few from each player, including herself) into one sub-deck of n cards.
shuffle: (as above)

By this stage (1 round), we have done the equivalent to randomizing each row of a matrix, then each column. Any particular single card could be anywhere after one round of shuffle-deal-shuffle, with equal probability. Alas, at this stage, there are still a few permutations that have probability zero. For example, the possible permutations equivalent to a rotation by shear (RBS) ("how do I rotate a bitmap?") require 3 shears. The closest that a single round of shuffle-deal-shuffle can produce is 2 shears, which is not enough to produce those permutations. So we continue with the second round:

deal: (as above)
shuffle: (as above)
gather all the sub-decks into one large full deck

The full 2-round shuffle-deal-shuffle-deal-shuffle algorithm can produce any possible permutation, but each permutation does not have exactly the same probability.

Each of the two "deal" steps mixes at least as well as a single riffle shuffle of the entire kn cards. The paper -- by Dave Bayer and Persi Diaconis -- that David Speyer mentioned proves that $m = \frac{3}{2} \log_2 (kn) + \theta$ riffle shuffles are sufficient.

Answer by davidcary for What are some mathematical sculptures?

2010-07-20T05:05:01Z

I like the 4 dimensional mathematical sculptures by Bathsheba Grossman, such as the 24-cell:

http://www.bathsheba.com/math/24cell/24cell_new_th.jpg

Are the cryptographic sculptures by Jim Sanborn -- Cyrillic Projector, etc. -- close enough to a "mathematical sculpture"?

http://www.ncarts.org/images/afsb_art/workpix/14.jpg

Answer by davidcary for Grid with nice mathematical properties

2010-07-01T20:50:27Z

Unfortunately, the sphere is not a "developable surface". This fact has annoyed map-makers for more than a millennium.

I find your focus on "cells" fascinating. Most people seem fixated on trying to get points on the globe to correspond with points on a flat image, and don't seem concerned about dividing it up into areas. The simplest way to convert (lat,long) coordinates to standardized areas is the "Natural Area Code", but it has the same problems near the poles as latitude and longitude.

Your "too many close grid cells" and "Distance between a cell and a point" criteria reminds me of the "Thomson problem". I suspect you're trying to rule-out map projections like the Gall–Peters projection that, while they do have nice "equal area" properties, end up having a hundred little squares at the top and bottom of the on the map projected to a hundred long, narrow pie-slices that all touch a pole of the globe.

Perhaps you could pick one of the known solutions to the "Thomson problem" to build a nice grid. Most of those solutions look similar to a geodesic sphere -- but there are a few exceptions.

Perhaps the most famous application for "almost equal" patches is the Cosmic Background Explorer (COBE), which has inspired several mappings:

the COBE sky cube (quadrilateralized spherical cube) -- an equal-area projection of the sphere onto a cube -- the 6 large squares divide easily into a nice square grid.
An icosahedron-based method for pixelizing the celestial sphere -- an equal-area projection of the sphere onto an icosahedron -- the 20 large equilateral triangles divide easily into a nice equilateral triangle grid; or into a nice regular hexagonal grid.
the HEALPix projection

The COBE "bins" are, as far as I can tell, a synonym for your "cells".

Are those COBE-inspired mappings adequate for you?

Answer by davidcary for Is there a generalisation of the "sunflower spiral" to higher dimensions?

2010-07-01T04:57:15Z

One possible way to fill R³ is to divide up R³ into onion-layers, and use some sort of "generalized spiral points" to fill each onion-layer -- kind of like winding a string from N pole to S pole to N pole to S pole.

In each layer, the spiral starts at the North pole and spirals out something like the "sunflower spiral", eventually crosses the equator. The Southern equator is (more or less) identical to the Northern equator. After the path crosses the equator, it spirals in smaller and tighter curves until it reaches the South pole. The whole spiral is vaguely similar to Sphere Spirals by M.C. Escher. This spiral is one solution to the "place n equally-spaced points on a sphere" problem -- it may not be "the best way to pixelize a sphere", it may not be the best solution to the "Thomson problem", but there is no one "best way to pixelize a sphere". Then you move out an onion-layer and start spiralling back from South to north.

Going at it from another direction: perhaps somehow number the spheres used to form Waterman polyhedra? That gives a much more regular and close-packed set of points (sphere centers) -- but it's not obvious to me if there is any nice formula to convert from sphere-number to xyz coordinates.