main.rs
21.7 kB · rust · 577 lines
1mod census;2mod collide;3mod counts;4mod tile;5mod witness;67use census::{8 cross_anatomy, rectangle_set, side_eight, side_four, side_nine, side_six, two_radix_lines,9 word_twelve, CrossAnatomy, SideSix,10};11use collide::{collisions, partners, residue_tile, self_power};12use counts::{line_brute, reducible_at, tile_total};13use num_bigint::BigUint;14use std::collections::{BTreeMap, BTreeSet};15use tile::{16 chain, cuts, factorisations, irreducible, kron, mask_tile, separable, split, totally_ordered,17 Tile,18};19use witness::{20 antidiagonal, from_cells, identity, line_closure, line_commuting, profiles_text, twelve_sweep,21};2223fn tally(map: &BTreeMap<usize, usize>) -> String {24 map.iter()25 .map(|(key, value)| format!("{key}:{value}"))26 .collect::<Vec<_>>()27 .join(" ")28}2930fn pair_tally(map: &BTreeMap<(usize, usize), usize>) -> String {31 map.iter()32 .map(|((a, b), value)| format!("({a},{b}):{value}"))33 .collect::<Vec<_>>()34 .join(" ")35}3637fn set_text(list: &[usize]) -> String {38 format!(39 "{{{}}}",40 list.iter()41 .map(|value| format!("{value}"))42 .collect::<Vec<_>>()43 .join(",")44 )45}4647fn alphabet() {48 println!("CODE FACTORISATION");49 println!("base-2 plane codes 1..15 render 0/1 2 x 2 tiles and base-3 codes 1..511 render 0/1 3 x 3 tiles, bit i of a code the cell (i / base, i mod base)");50 println!("a word folds by the Kronecker product, first letter outermost, so its composite is one 0/1 tile at side the product of the letter sides");51 let mut letters = 0usize;52 for (base, total) in [(2usize, 15u128), (3usize, 511u128)] {53 for code in 1..=total {54 let truth = mrlymath::bang::factory::create(code, base, 2, base, 1).unwrap();55 let mine = mask_tile(code as u64, base);56 for r in 0..base {57 for c in 0..base {58 assert_eq!(truth.get(&[r, c]) == 1, mine.at(r, c), "letter render");59 }60 }61 letters += 1;62 }63 }64 let mut products = 0usize;65 for a in 1u128..16 {66 let left = mrlymath::bang::factory::create(a, 2, 2, 2, 1).unwrap();67 let mine_left = mask_tile(a as u64, 2);68 for b in 1u128..512 {69 let right = mrlymath::bang::factory::create(b, 3, 2, 3, 1).unwrap();70 let truth = left.kron(&right);71 let mine = kron(&mine_left, &mask_tile(b as u64, 3));72 for r in 0..6 {73 for c in 0..6 {74 assert_eq!(truth.get(&[r, c]) == 1, mine.at(r, c), "product render");75 }76 }77 products += 1;78 }79 }80 println!("{letters} letters and all {products} shape-(2,3) products agree cell for cell with mrlymath::bang::factory::create and mrlycore::Tensor::kron");81 println!();82}8384fn block_test() {85 println!("THE BLOCK TEST");86 println!("a tile C of side N cuts at d | N when every nonzero d-block of C is one tile B, and then C = A (x) B with A the 0/1 indicator of the nonzero blocks");87 println!("the test is exact integer comparison, it names both factors outright, and it never touches a rearrangement singular value");88 let four = side_four();89 println!(90 "side 4: {} ordered pairs of the 15 base-2 codes, {} distinct products, largest preimage {}",91 four.products, four.distinct, four.max_preimage92 );93 println!(94 "side 4 by the block test over all 65535 nonempty masks: {} reducible, and the two sets are equal: {}",95 four.by_block.len(),96 four.by_block == four.by_product97 );98 assert_eq!(four.by_block, four.by_product);99 let total = 65535usize;100 println!(101 "side 4: reducible {}, irreducible {}, reducible share {:.6}%",102 four.distinct,103 total - four.distinct,104 100.0 * four.distinct as f64 / total as f64105 );106 println!();107}108109fn side_six_report(six: &SideSix, anatomy: &CrossAnatomy) {110 println!("SIDE 6");111 println!(112 "shape (2,3): {} products, {} distinct, {} internal collisions",113 15 * 511,114 six.image23.len(),115 six.collisions23116 );117 println!(118 "shape (3,2): {} products, {} distinct, {} internal collisions",119 511 * 15,120 six.image32.len(),121 six.collisions32122 );123 assert_eq!(six.collisions23, 0);124 assert_eq!(six.collisions32, 0);125 println!("cross-shape, a tile in both images: {}", six.cross.len());126 let universe = tile_total(6);127 let reducible = BigUint::from(six.reducible.len());128 println!(129 "reducible {} + {} - {} = {} of {}, de-duplicated once before printing; irreducible {}",130 six.image23.len(),131 six.image32.len(),132 six.cross.len(),133 six.reducible.len(),134 universe,135 &universe - &reducible136 );137 assert_eq!(138 six.reducible.len(),139 six.image23.len() + six.image32.len() - six.cross.len()140 );141 println!(142 "reducible share {:.7}%",143 100.0 * six.reducible.len() as f64 / 68719476735.0144 );145 println!(146 "the {}: axis-separable {}, not separable {}",147 six.cross.len(),148 anatomy.separable,149 anatomy.non_separable150 );151 println!(152 "the {}: commutations {}, rewritings {}",153 six.cross.len(),154 anatomy.commuting,155 anatomy.rewriting156 );157 println!(158 "not separable and not commuting {}, not separable and commuting {}, the second exactly the diagonal and the antidiagonal",159 anatomy.non_separable_non_commuting,160 anatomy.non_separable_commuting.len()161 );162 println!("fill over the 171: {}", tally(&anatomy.fills));163 println!(164 "fill over the 50 not separable: {}",165 tally(&anatomy.fills_non_separable)166 );167 println!(168 "outer-fill signature of the 50, sorted pair: {}",169 pair_tally(&anatomy.outer_fills)170 );171 println!(172 "a one-cell letter anywhere in a reading, over the 171: {}; over the 50: {}",173 tally(&anatomy.one_cell_any),174 tally(&anatomy.one_cell_any_non_separable)175 );176 println!(177 "a one-cell OUTER factor, over the 171: {}; over the 50: {}",178 tally(&anatomy.one_cell_outer),179 tally(&anatomy.one_cell_outer_non_separable)180 );181 println!(182 "three readings of 48 over the 50, not one statistic: not commuting {}, a one-cell letter in at least one reading {}, a one-cell outer factor in at least one reading {}, and the three sets are equal: {}",183 anatomy.set_non_commuting.len(),184 anatomy.set_one_any.len(),185 anatomy.set_one_outer.len(),186 anatomy.set_non_commuting == anatomy.set_one_any187 && anatomy.set_one_any == anatomy.set_one_outer188 );189 assert_eq!(anatomy.set_non_commuting, anatomy.set_one_any);190 assert_eq!(anatomy.set_one_any, anatomy.set_one_outer);191 println!();192}193194fn two_radix(anatomy: &CrossAnatomy) {195 println!("THE TWO-RADIX LINES");196 let lines = two_radix_lines();197 let text: Vec<String> = lines.iter().map(|line| set_text(line)).collect();198 println!(199 "a line of side 6 is a subset of {{0..5}}; {} of the 63 nonempty subsets factor in both radix orders: {}",200 lines.len(),201 text.join(" ")202 );203 let rectangles = rectangle_set();204 println!(205 "the {} axis-separable tiles are exactly the products R x C of two such lines, checked as set equality: {}",206 anatomy.separable,207 rectangles == anatomy.separable_set208 );209 assert_eq!(rectangles, anatomy.separable_set);210 println!(211 "so {} = {} x {} is arithmetic with a checked bijection behind it, never a numeric coincidence",212 anatomy.separable,213 lines.len(),214 lines.len()215 );216 println!();217}218219fn commutation(anatomy: &CrossAnatomy) {220 println!("COMMUTATION");221 let pairs: Vec<String> = anatomy222 .commuting_pairs223 .iter()224 .map(|(a, b)| format!("({a},{b})"))225 .collect();226 println!(227 "the {} commuting (base-2, base-3) code pairs: {}",228 anatomy.commuting,229 pairs.join(" ")230 );231 let odd: Vec<String> = anatomy232 .non_separable_commuting233 .iter()234 .map(|(a, b)| format!("c{a} (x) c{b}.q3"))235 .collect();236 println!(237 "9 of them are a commuting row line against a commuting column line, 3 x 3, and the other 2 are {}, the diagonal and the antidiagonal",238 odd.join(" and ")239 );240 let partnered: BTreeSet<u32> = anatomy.commuting_pairs.iter().map(|(a, _)| *a).collect();241 let orphans: Vec<String> = (1u32..16)242 .filter(|code| !partnered.contains(code))243 .map(|code| format!("{code}"))244 .collect();245 println!(246 "base-2 codes {} have no commuting base-3 partner, so the carpet code itself does not commute",247 orphans.join(", ")248 );249 println!("one-cell letters commute exactly when a(n-1) = b(m-1), which gives gcd(m-1,n-1)+1 singleton pairs and, where no common power exists, gcd(m-1,n-1)+2 commuting pairs in one dimension");250 println!("m n singletons gcd+1 commuting gcd+2");251 for (m, n) in [252 (2usize, 3usize),253 (3, 5),254 (4, 7),255 (5, 9),256 (3, 7),257 (5, 7),258 (4, 5),259 (6, 11),260 (5, 13),261 (3, 9),262 ] {263 let found = line_commuting(m, n);264 let singles = found265 .iter()266 .filter(|(a, b)| a.count_ones() == 1 && b.count_ones() == 1)267 .count();268 let g = tile::gcd(m - 1, n - 1);269 println!("{m} {n} {singles} {} {} {}", g + 1, found.len(), g + 2);270 }271 let a = from_cells(3, &[(1, 1)]);272 let b = from_cells(5, &[(2, 2)]);273 let left = kron(&a, &b);274 let right = kron(&b, &a);275 println!(276 "the cells [3]{{(1,1)}} and [5]{{(2,2)}} commute at side 15, both readings giving {}: {}",277 left.text(),278 left == right279 );280 assert_eq!(left, right);281 println!("neither is a corner cell, a full row, a full column, the full tile, a diagonal or an antidiagonal, so the side-6 picture of four corner cells is an artifact of gcd(1,2) = 1");282 println!();283}284285fn higher_sides() {286 println!("SIDE 8 AND SIDE 9");287 let eight = side_eight();288 println!(289 "side 8, shape (2,4): {} tiles; shape (4,2): {} tiles; intersection {}",290 eight.image24, eight.image42, eight.intersection291 );292 println!(293 "the intersection is exactly the set of triple products X (x) Y (x) Z of nonempty base-2 codes: {}, so 3375 = 15^3 is associativity and nothing more",294 eight.triples_match295 );296 assert!(eight.triples_match);297 let universe8 = tile_total(8);298 let reducible8 = BigUint::from(eight.image24 + eight.image42 - eight.intersection);299 println!(300 "side 8: reducible {} + {} - {} = {} of {}, irreducible {}",301 eight.image24,302 eight.image42,303 eight.intersection,304 reducible8,305 universe8,306 &universe8 - &reducible8307 );308 let nine = side_nine();309 let universe9 = tile_total(9);310 let reducible9 = BigUint::from(nine.distinct);311 println!(312 "side 9: {} ordered base-3 pairs, {} distinct, {} collisions; reducible {} of {}, irreducible {}",313 nine.products,314 nine.distinct,315 nine.collisions,316 nine.distinct,317 universe9,318 &universe9 - &reducible9319 );320 assert_eq!(nine.collisions, 0);321 println!("3375 never stands beside 171: 8 is a prime power, where no order of the sides can change, and the two counts measure different things");322 println!();323}324325fn prime_powers() {326 println!("COUNTING AT PRIME-POWER SIDE");327 println!("at a prime-power side the divisors form a chain, factorisation is unique, and the irreducible series is I = T/(1+T) over the grading");328 for (prime, power) in [(2usize, 2usize), (2, 3), (3, 2), (2, 4), (5, 2)] {329 let side = prime.pow(power as u32);330 println!(331 "side {side} = {prime}^{power}: reducible {}",332 reducible_at(prime, power, true)333 );334 }335 let square = BigUint::from(33554431u64) * BigUint::from(33554431u64);336 println!(337 "side 25 reads (2^25 - 1)^2 = 33554431^2 = {square}, which is not 65535^2 = 4294836225"338 );339 assert_eq!(square, reducible_at(5, 2, true));340 println!("one dimension, the same series against exhaustive brute force:");341 for (prime, power) in [(2usize, 2usize), (2, 3), (2, 4), (3, 2)] {342 let side = prime.pow(power as u32);343 let formula = reducible_at(prime, power, false);344 let brute = BigUint::from(line_brute(side));345 println!(346 "N = {side}: formula {formula}, brute force {brute}, agree {}",347 formula == brute348 );349 assert_eq!(formula, brute);350 }351 println!();352}353354fn report_chains(name: &str, tile: &Tile) {355 let words = factorisations(tile);356 let chains: Vec<String> = words.iter().map(|word| set_text(&chain(word))).collect();357 let mut union: BTreeSet<usize> = BTreeSet::new();358 for word in &words {359 union.extend(chain(word));360 }361 let ordered = totally_ordered(&union);362 println!(363 "{name}: cut chains {}, union {} totally ordered by divisibility {}, so the readings share no common refinement",364 chains.join(" and "),365 set_text(&union.iter().copied().collect::<Vec<usize>>()),366 ordered367 );368 assert!(!ordered);369}370371fn witnesses(six: &SideSix) {372 println!("WITNESSES");373 let w1 = from_cells(6, &[(0, 0), (2, 2)]);374 let (a2, b3) = split(&w1, 2).unwrap();375 let (x3, y2) = split(&w1, 3).unwrap();376 println!(377 "W1 {}: cut at 2 gives ({} = c{}, {} = c{}.q3); cut at 3 gives ({} = c{}.q3, {} = c{})",378 w1.text(),379 a2.text(),380 a2.pack(),381 b3.text(),382 b3.pack(),383 x3.text(),384 x3.pack(),385 y2.text(),386 y2.pack()387 );388 println!(389 "W1: the four factors are irreducible {} {} {} {}; axis-separable {}; in the cross-shape 171 {}; cut set {}",390 irreducible(&a2),391 irreducible(&b3),392 irreducible(&x3),393 irreducible(&y2),394 separable(&w1),395 six.cross.contains(&w1.pack()),396 set_text(&cuts(&w1))397 );398 assert!(irreducible(&a2) && irreducible(&b3) && irreducible(&x3) && irreducible(&y2));399 assert!(!separable(&w1));400 assert!(six.cross.contains(&w1.pack()));401 report_chains("W1", &w1);402 let w2 = from_cells(12, &[(0, 0), (3, 3)]);403 println!("W2 {}: profiles {}", w2.text(), profiles_text(&w2));404 let inner4 = from_cells(4, &[(0, 0), (3, 3)]);405 let words = factorisations(&w2);406 let lengths: BTreeSet<usize> = words.iter().map(|word| word.len()).collect();407 println!(408 "W2: the side-4 factor {} is irreducible {}; cut set {}, which holds 2 and 3 and not 6, so cut sets are not closed under lcm",409 inner4.text(),410 irreducible(&inner4),411 set_text(&cuts(&w2))412 );413 println!(414 "W2: lengths {:?} and side multisets {{2,2,3}} and {{3,4}}, so neither the length nor the side multiset is an invariant of the tile; axis-separable {}",415 lengths,416 separable(&w2)417 );418 assert!(irreducible(&inner4));419 assert_eq!(lengths.len(), 2);420 assert!(!separable(&w2));421 report_chains("W2", &w2);422 println!("W2 is minimal: every side below 12 is a prime power, where factorisation is unique, or a product of two distinct primes, where every factorisation has prime-side factors only");423 let mut family = 0usize;424 for (m, n) in [425 (2usize, 3usize),426 (3, 2),427 (2, 5),428 (3, 5),429 (4, 3),430 (5, 7),431 (2, 9),432 ] {433 let (im, in_) = (identity(m), identity(n));434 let (em, en) = (antidiagonal(m), antidiagonal(n));435 assert_eq!(kron(&im, &in_), identity(m * n));436 assert_eq!(kron(&in_, &im), identity(m * n));437 assert_eq!(kron(&em, &en), antidiagonal(m * n));438 assert_eq!(kron(&en, &em), antidiagonal(m * n));439 family += 1;440 }441 println!("the infinite family: I_m (x) I_n = I_mn = I_n (x) I_m and E_m (x) E_n = E_mn = E_n (x) E_m, checked at {family} side pairs, so the failure is not a side-6 accident but lives at every side with two distinct prime factors");442 let d2 = from_cells(2, &[(0, 0)]);443 let d3 = from_cells(3, &[(1, 1)]);444 let e2 = from_cells(2, &[(1, 1)]);445 let e3 = from_cells(3, &[(0, 0)]);446 let one = kron(&d2, &d3);447 let two = kron(&e3, &e2);448 println!(449 "not a trace monoid: {} (x) {} = {} = {} (x) {}, four pairwise distinct irreducible letters, so the relation is no commutation of a letter pair: {}",450 d2.text(),451 d3.text(),452 one.text(),453 e3.text(),454 e2.text(),455 one == two456 );457 assert_eq!(one, two);458 println!();459}460461fn cut_sets(six: &SideSix) {462 println!("CUT SETS");463 println!("L(C) is the set of d | N at which C cuts; two factorisations share a common refinement exactly when the union of their cut chains is a divisor chain");464 let line = line_closure(20);465 let (side, mask, list) = line.first_lcm.clone().unwrap();466 println!(467 "one dimension, every nonempty subset of {{0..N-1}} at N = 1..20: {} failures of gcd closure, {} of lcm closure",468 line.gcd_violations, line.lcm_violations469 );470 assert_eq!(line.gcd_violations, 0);471 let diagonal = 0b1001u128;472 println!(473 "the first lcm failure is at N = {side} on {} with L = {}, and the line {} that lifts to W2 carries the same cut set {}",474 tile::line_text(mask, side),475 set_text(&list),476 tile::line_text(diagonal, 12),477 set_text(&tile::line_cuts(diagonal, 12))478 );479 assert_eq!(tile::line_cuts(diagonal, 12), list);480 let sweep = twelve_sweep(&six.reducible);481 println!(482 "two dimensions, the {} side-12 composites of three-letter plane-code words counted above: {} failures of gcd closure, {} of lcm closure",483 sweep.tiles, sweep.gcd_violations, sweep.lcm_violations484 );485 assert_eq!(sweep.gcd_violations, 0);486 println!(487 "on the same family the criterion holds with {} mismatches: a tile carries two or more irreducible factorisations exactly when L(C) holds two incomparable divisors",488 sweep.mismatches489 );490 assert_eq!(sweep.mismatches, 0);491 println!(492 "{} of them carry two or more factorisations, {} carry factorisations of unequal length, and the largest number of irreducible factorisations is {}",493 sweep.multiple, sweep.unequal_length, sweep.max_factorisations494 );495 println!("gcd closure of L(C) is Conjecture and is the one missing structural fact; lcm closure is Refuted outright by the N = 12 witness above");496 println!();497}498499fn word_census() {500 println!("THE WORD CENSUS AT SIDE 12");501 println!("words over the plane-code alphabet only, a strictly smaller universe than the reducible side-12 tiles, because every plane code has prime side");502 let w2 = from_cells(12, &[(0, 0), (3, 3)]);503 let census = word_twelve(&w2);504 println!(505 "each of the three shapes (2,2,3), (2,3,2), (3,2,2) holds {} words with {} {} {} distinct composites",506 census.per_shape, census.distinct[0], census.distinct[1], census.distinct[2]507 );508 println!(509 "pairwise {} {} {}, triple {}, union {}, and {} = 15 x 171",510 census.pairs[0],511 census.pairs[1],512 census.pairs[2],513 census.triple,514 census.union,515 census.pairs[0]516 );517 assert_eq!(census.pairs[0], 15 * 171);518 println!(519 "W2 lies in the (2,2,3) image {} and in the other two {} {}, because its length-2 reading needs the irreducible side-4 letter [4]{{(0,0),(3,3)}}, which is no plane code",520 census.witness_shapes[0], census.witness_shapes[1], census.witness_shapes[2]521 );522 assert!(census.witness_shapes[0] && !census.witness_shapes[1] && !census.witness_shapes[2]);523 println!("so length and the side multiset are invariants inside the magic-word submonoid, where every letter has prime side, and both fail in the full tile monoid");524 println!();525}526527fn render_collisions() {528 println!("RENDER COLLISIONS");529 println!("a base-2 code and a base-3 code render one tile at side n when the two residue rules agree cell for cell; the universe is 15 x 511 = 7665 code pairs per side");530 let mut rows: Vec<String> = Vec::new();531 for side in [2usize, 3, 4, 5, 6, 7, 8, 9, 12, 18] {532 let found = collisions(side);533 rows.push(format!("{side}:{}", found.len()));534 if side >= 4 {535 assert_eq!(found, vec![(15u32, 511u32)]);536 }537 }538 println!("collisions by side: {}", rows.join(" "));539 println!("480 = 15 x 2^5 at side 2, one per nonempty base-2 code at side 3, and only the full tile (15, 511) at every side from 4 up");540 let match_list = partners(7, 3);541 let text: Vec<String> = match_list.iter().map(|code| format!("{code}")).collect();542 println!(543 "the carpet code 7 has match list [{}] at side 3, a unique partner of fill {}",544 text.join(","),545 residue_tile(495, 3, 3).fill()546 );547 assert_eq!(match_list, vec![495u32]);548 let carpet9 = residue_tile(7, 2, 9);549 let residue9 = residue_tile(495, 3, 9);550 let power9 = self_power(495, 3, 2);551 println!(552 "at side 9 the three readings separate: carpet residue fill {}, c495 residue fill {}, c495 self-power fill {}, and the three tiles are pairwise distinct: {}",553 carpet9.fill(),554 residue9.fill(),555 power9.fill(),556 carpet9 != residue9 && residue9 != power9 && carpet9 != power9557 );558 assert!(carpet9 != residue9 && residue9 != power9 && carpet9 != power9);559 println!("the two self-power ladders 2, 4, 8, 16 and 3, 9, 27 share no side, so the pure fractal reading carries no collision at all");560 println!();561}562563fn main() {564 alphabet();565 block_test();566 let six = side_six();567 let anatomy = cross_anatomy(&six);568 side_six_report(&six, &anatomy);569 two_radix(&anatomy);570 commutation(&anatomy);571 higher_sides();572 prime_powers();573 witnesses(&six);574 word_census();575 cut_sets(&six);576 render_collisions();577}