Skip to content

Instantly share code, notes, and snippets.

@jcmckeown
Last active March 12, 2019 19:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jcmckeown/54f9b011acaa5d35b84301e662ca5376 to your computer and use it in GitHub Desktop.
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).
/**
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
}
<!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