Last active
March 12, 2019 19:51
-
-
Save jcmckeown/54f9b011acaa5d35b84301e662ca5376 to your computer and use it in GitHub Desktop.
A Sketch in Processing to draw a rigidified picture of the POSet of Order Ideals of the binary n-cube (for small n, at least).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
We want to construct the set of order-ideals in | |
the product partial-order on the binary n-cube (2^n); | |
we want to do this in such a way that the containment order (I < J) | |
is easy to calculate, and in particular such that the *atomic* moves | |
are easily recognized. | |
Now, an order-ideal in a *successor* binary cube (2^{n+1}) can be | |
construed as a pair (I and J) of order-ideals in the n-cube, such that J <= I. | |
Then, two such pairs (I1 >= J1) and (I0 >= J0) are *ordered* (I1>=J1)<(I0>=J0) | |
exactly when (I1 =< I0) and (J1 =< J0). Furthermore, the ordering is *atomic* ("<|") | |
exactly when either ( (I1 = I0) & (J1 <| J0) ) | ( (I1 <| I0) & (J1 = J0) ). | |
*** see also http://oeis.org/A000372 | |
the author was interested in these structures in connection with Homotopy Theory --- the poset of order ideals gives the | |
Canonical Resolution of a Commutative Cube into (generalized) pasting diagram of Pullback Cubes. Having pictures of them | |
was thought a pleasant exercise, if not terribly useful. | |
*** | |
sketch-global variables: | |
float theAxesX[], theAxesY[], theAngles[] //--- don't bother them! these are only used INSIDE the bigArray.drawMe() and only adjusted by ***[Pp]erturb(); | |
bigArray ba // --- eventually, the one we draw pictures of. | |
int depth // tweakable, within reason: depth=5 wants more than 1GB in the sandbox and is rather slow; growth with depth is superexponential, but slower than repeated squaring | |
float turnPerFrame, bumpPerFrame // tweakable --- turnEachFrame sets the overall scale for the theAngles[] of the turns from frame to frame, | |
// and bumpPerFrame the size of the random per-frame adjustment made to theAngles[] ; | |
of course one can saveframe(), but this will slow things down | |
bigArray.bigArray(void) returns a copy of the poset 0 < 1; | |
bigArray.bigArray(bigArray prev) returns a copy of the poset square of prev --- there are no other bigArray(...) functions; much guaranteed structure follows | |
anglePerturb() adjusts theAxes[2^n] according to the angles in theAngles[] --- and enforces an orthonormality condition (which is why it's called before the first draw) | |
--- and then randomly perturbs theAngles[] | |
span() ( called at the end of anglePerturb() ) propagates the condition of theAxes*[2^n], normalizing all the rest of theAxes*[] ... | |
the orderIdeals Poset is a *graded* poset (graded by Ideal Cardinality); apart from this, every *atomic* inquality is Parallel to a unique atomic inequality under a | |
*principal* ideal--- that is, every ideal is the union of the principal ideals of its maximal elements. | |
the unique atomic step down from any nontrivial principal ideal belongs to a maximal k-cube whose other edges are all parallel to *singleton* principal ideals | |
--- which, by induction, correspond to theAxes*[2^n]; the whole collection of directions, then, are rigidified by asking that these cubes have a | |
*/ | |
float theAxesX[]; | |
float theAxesY[]; | |
class bigArray { | |
private | |
int count; // how many actual nodes in the order | |
int corners; // how many directions possible for an Atomic Move : this is equal to the number of Principal Ideals, which is 2^k, starting with k=0 | |
int dim; | |
int orderDetails[][]; // promise this is actually int[count][count]; | |
int atomicMoves[][]; | |
public | |
bigArray(){ | |
dim = 0; | |
corners = 1; | |
count = 2; | |
orderDetails = new int[2][2]; | |
atomicMoves = new int[2][2]; | |
orderDetails[0][0] = orderDetails[1][1] = 0; | |
atomicMoves[0][0] = atomicMoves[1][1] = atomicMoves[1][0] = -1; | |
orderDetails[0][1] = 1; | |
atomicMoves[0][1] = 0; | |
orderDetails[1][0] = -3; | |
} | |
bigArray (bigArray prev) { | |
dim = 1 + prev.dim; | |
corners = 2 * prev.corners; | |
count = 0; | |
for (int j = 0 ; j < prev.count ; j++ ){ | |
for (int k = 0; k < prev.count ; k++ ){ | |
if (prev.orderDetails[k][j] >= 0) count++; | |
} | |
} | |
println( "my dimension is " + dim + " and my size is " + count ); | |
orderDetails = new int[count][count]; | |
atomicMoves = new int[count][count]; | |
int countLeft = 0; | |
for (int j = 0 ; j < prev.count ; j++ ){ | |
for (int k = 0; k < prev.count ; k++ ){ | |
if ( prev.orderDetails[k][j] >= 0) { | |
int countRight = 0; | |
for (int jj = 0; jj < prev.count ; jj++) { | |
for (int kk = 0; kk < prev.count ; kk++) { | |
if ( prev.orderDetails[kk][jj] >= 0 ) { | |
// only such pairs were counted above; only these count now) | |
int total = prev.orderDetails[j][jj] + prev.orderDetails[k][kk]; | |
if (total < 0) { orderDetails[countLeft][countRight] = -3 ; atomicMoves[countLeft][countRight] = -1; } // one of ( [j] > [jj] or [k]>[kk] ) | |
else if (total == 0) { orderDetails[countLeft][countRight] = 0; atomicMoves[countLeft][countRight]=-1; } // only if j==jj, k==kk, countLeft==countRight | |
else if (total == 1) { orderDetails[countLeft][countRight] = 1; | |
atomicMoves[countLeft][countRight] = ( k == kk ) ? 2 * prev.atomicMoves[j][jj] : 2 * prev.atomicMoves[k][kk] + 1 ; | |
} // an atomic move... | |
else { orderDetails[countLeft][countRight] = 2; | |
atomicMoves[countLeft][countRight] = -1; } | |
countRight++; | |
} else {} | |
} | |
} | |
countLeft++; | |
} | |
} | |
} | |
} | |
void printMe(){ | |
int preCount = count-1; | |
int cur = -1; | |
println("The ordering Relation"); | |
for (int j = 0; j< count ; j++ ) { | |
print( "" + j + " : [" ) ; | |
for (int k = 0; k < count; k++) { | |
cur = orderDetails[k][j]; | |
print(" " + (cur >=0 ? cur : "-") + ( k == preCount ? "]" : ",") ); | |
} | |
println(); | |
} | |
println("The array of Atomic Moves w/ direction"); | |
for (int j = 0; j < count ; j++) { | |
print( " [" ); | |
for (int k = 0 ; k < count; k++) { | |
cur = atomicMoves[k][j]; | |
print(" " + ( cur >= 0 ? cur : "-" ) + ( k == preCount ? " ]" : ",")); | |
} | |
println(); | |
} | |
} | |
void drawRough(){ /* just draw the two big arrays as color-maps */ | |
int i, j; | |
int colorMap[] = { 0 , 0 , 0 , 1 , 2 , 5 } ; | |
loadPixels(); | |
color orderColours[] = { color(100,0,0) , color(20) , color(40) , color(60) , color(80), color(100) }; | |
for (i = 0 ; i < count ; i++){ | |
for( j = 0; j < count ; j++) { | |
pixels[width * i + j] = orderColours [ colorMap [ 3 + orderDetails[j][i] ]] ; | |
pixels[width * i + count + 10 + j] = color( 100 * (1 + atomicMoves[j][i]) / corners ); | |
updatePixels(); | |
} | |
} | |
} | |
void drawMe( ){ | |
float size = 2 * min(height, width) / ( 1 + corners ); | |
float theXVals[] = new float[count]; | |
float theYVals[] = new float[count]; | |
theXVals[0] = width/2 - size * theAxesX[0] * corners /2; | |
theYVals[0] = height/2 - size * theAxesY[0] * corners /2; | |
for (int i = 1 ; i < count; i ++ ){ | |
int j = i; // and then find the most-recent atomic-previous index j... | |
do { j-- ; } while (atomicMoves[j][i] < 0 ); | |
theXVals[i] = theXVals[j] + size * theAxesX[ atomicMoves[j][i]]; | |
theYVals[i] = theYVals[j] + size * theAxesY[ atomicMoves[j][i]]; | |
} | |
for (int i = 0; i < count ; i++ ) { | |
for (int j = i ; j < count ; j++ ){ | |
if (atomicMoves[i][j] >= 0) line(theXVals[i],theYVals[i],theXVals[j],theYVals[j]); | |
} | |
} | |
} | |
} | |
bigArray ba; | |
void span(){ | |
int theLog = ba.dim; | |
int thePower = 1; | |
theAxesX[0] = 0; | |
theAxesY[0] = 0; | |
for ( int j = 0; j < theLog; j++ ) { | |
theAxesX[0] += theAxesX[thePower]; | |
theAxesY[0] += theAxesY[thePower]; | |
thePower *= 2; | |
} | |
theAxesX[0] /= theLog; | |
theAxesY[0] /= theLog; | |
thePower = 1; | |
if ( ba.corners > 2 ){ | |
thePower = 4; | |
for ( int i = 3 ; i < ba.corners ; i++ ){ | |
if (i == thePower) { thePower *= 2; } else { | |
theAxesX[i] = theAxesX[0]; | |
theAxesY[i] = theAxesY[0]; | |
for ( int j = 1 ; j <= i ; j *= 2 ){ | |
if ( (j & i) != 0) { | |
theAxesX[i] += theAxesX[j] - theAxesX[0]; | |
theAxesY[i] += theAxesY[j] - theAxesY[0]; | |
} | |
} | |
} | |
} | |
} | |
} | |
float theAngles[]; | |
float turnPerFrame = 3.0 / 57.3; // about three degrees | |
float bumpPerFrame = 1.0 / 300.0; // about 1/6th of a degree... | |
void anglePerturb(){ | |
/* The angles, a short list of Euler Angles, should be Small, about two degrees. | |
We perturb them by about half a degree | |
*/ | |
float resize = (turnPerFrame)/(turnPerFrame + bumpPerFrame); | |
for (int j = 0 ; j < ba.dim ; j++ ){ | |
theAngles[j] += (random(2) - 1) * bumpPerFrame ; // previously: (rand(2)-1)/ 600 ; | |
theAngles[j] *= resize; // previously , resize = .95 , and turnPerFrame was left implicit // *= resize ; | |
} | |
float nx, ny, s, c; | |
int sc = 1; | |
int shortstop = ba.dim-1; | |
for (int j = 0; j < shortstop ; j++){ | |
s = sin(theAngles[j]); | |
c = cos(theAngles[j]); | |
nx = theAxesX[sc] * c + theAxesX[sc*2] * s; | |
ny = theAxesX[sc*2] * c - theAxesX[sc] * s; | |
theAxesX[sc] = nx; theAxesX[sc*2] = ny; | |
nx = theAxesY[sc] * c + theAxesY[sc*2]*s; | |
ny = theAxesY[sc*2]*c - theAxesY[sc] * s; | |
theAxesY[sc] = nx; | |
theAxesY[sc*2] = ny; | |
sc *= 2; | |
} | |
s = sin(theAngles[shortstop]) ; c = cos(theAngles[shortstop]); | |
nx = theAxesX[sc] * c + theAxesX[1] * s; | |
ny = theAxesX[1] * c - theAxesX[sc] * s; | |
theAxesX[sc] = nx; theAxesX[1] = ny; | |
nx = theAxesY[sc] * c + theAxesY[1] * s; | |
ny = theAxesY[1] * c - theAxesY[sc] * s; | |
theAxesY[sc] = nx; theAxesY[1] = ny; | |
nx = 0 ; // as r; | |
for (sc = 1; sc < ba.corners; sc *= 2){ | |
nx += theAxesX[sc]*theAxesX[sc]; | |
} | |
nx = sqrt(nx); | |
for (sc = 1; sc < ba.corners; sc *=2){ | |
theAxesX[sc] /= nx; | |
} | |
nx = 0; // as inner-product <axesX . axesY> | |
for (sc = 1; sc < ba.corners; sc *= 2){ | |
nx += theAxesX[sc] * theAxesY[sc]; | |
} | |
for (sc = 1; sc < ba.corners; sc *= 2){ | |
theAxesY[sc] -= nx * theAxesX[sc]; | |
} | |
nx = 0; | |
for (sc = 1; sc < ba.corners; sc *= 2){ | |
nx += theAxesY[sc] * theAxesY[sc]; | |
} | |
nx = sqrt(nx); | |
for (sc = 1; sc < ba.corners; sc *= 2){ | |
theAxesY[sc] /= nx; | |
} | |
span(); | |
} | |
int depth = 4; | |
void setup(){ | |
// fullScreen(); | |
size(1000 , 720); | |
smooth(8); | |
stroke(0); | |
noFill(); | |
// noLoop(); | |
ba = new bigArray(); | |
for (int c = 0 ; c < depth ; c++) ba = new bigArray(ba); | |
theAxesX = new float[ba.corners]; | |
theAxesY = new float[ba.corners]; | |
theAngles = new float[ba.dim]; | |
for (int c = 1 ; c < ba.corners ; c *=2 ){ | |
theAxesX[c] = random(2)-1; | |
theAxesY[c] = random(2)-1; | |
} | |
for (int c = 0 ; c < ba.dim ; c++ ){ | |
theAngles[c] = (random(2)-1) * turnPerFrame; | |
} | |
anglePerturb(); | |
} | |
void draw(){ | |
background(200); | |
ba.drawMe(); | |
anglePerturb(); | |
// saveFrame("wobblywander_####.png"); // in case a film of them should amuse | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<body> | |
<script src="https://raw.githubusercontent.com/processing-js/processing-js/master/processing.min.js"></script> | |
<canvas data-processing-sources="drawThePosetOfOrderIdeals.pde"></canvas> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment