A bunch of things. --Rich ----- Comet: Did anyone else see the comet impact? I was out watching for it the night of July 3. I had my binoculars pointed at the right area, but had picked out the wrong dot as "the comet". I saw one bright flash, lasting perhaps a second, with no obvious center - the whole field flashed. The time was right, within a minute or so. ----- RSA200: [For some reason, this wasn't on the NMBRTHRY list?] The (old) challenge number RSA200 (a 200 digit number) has been factored by F. Bahr, M. Boehm, J. Franke, T. Kleinjung, P. Montgomery, and H. te Riele. Calendar time was about 18 months, Dec 2003 - May 2005. The total work was roughly 75 PC-years on a 2GHz machine. The linear algebra used a cluster of 80 machines. They have since made further improvements to the Lattice Sieve. Sieving is a random-access use of the memory, and it must be tweaked to make the best use of cache and TLB. Google/Wikipedia for RSA200 or RSA-200. Discrete logs are lagging behind, at 130 digits. Joux & Lecier used a 16-processor cluster of 1GHz Alphas for 3 weeks (about 1 GHz PC-year). Individual logs take a few hours. ----- Recent progress related to the twin-prime problem:

From the prime number theorem, the average gap between primes is log(Prime). Goldston, Motohashi, Pintz, and Yildirim have shown that the ratio Gap(Prime(i))/log(Prime(i)) has lim inf = 0. This is a far cry from the "lim inf Gap = 2" required for settling twin primes, but it is progress. http://www.maa.org/news/052505twinprimes.html http://www.aimath.org/preprints.html.

----- Sudoku: Until the 17-clue example from yesterday, I was wondering what all the fuss was about. The 17er actually requires some more interesting reasoning, but no trial. I used things like "these two cells must be {3,4} in some order", and subtracted them from larger sets. Also "since these two are {3,4} (or {4,3}), and they are in the same row, I can exclude 3&4 from other cells in the row". The main work is scanning the array looking for an application of one of the simple rules like "this 3x3 box must have a 7 somewhere, and all but one of the empty cells is excluded by having a 7 elsewhere in an intersecting row or column". The popularity of the game means there are lots of folks who like a kind of mathematical reasoning. Dan's Latin Square estimate deflator should have a coefficient of 2, not 8. D_4 includes horizontal and vertical reflection, already counted in the row & column permutations. Diagonal flipping remains, giving the coefficient 2. There are Latin Cubes! Addition mod N gives a Latin Hypercube of any dimension. ----- Book recommendation: Count Down, by Steve Olson. He follows the US team (6 high schoolers) at the 2001 Math Olympiad. I found the book intersting for the side topics: He examines the rarity of women in the contest. He looks seriously at the very idea of competing, and how it applies to the Olympiad. Apparently mathematics is held in higher regard in other countries. And there's a chapter about Ultimate Frisbee. The Olympiad problems and solutions are sketched. ----- Associative-Commutative Crossover at 406: Fix an integer N. Consider all the N^N^2 binary operations defined on N elements. Are there more Commutative operations (with symmetric operation tables), or Associative operations (semigroups)? Likely answer: For N<=405, commutatives win; for larger N, semigroups. A quick look at OIES shows Commutativity getting off to an impressive early lead over Associativity. (The story's the same if we count tables instead of culling isomorphs.) Semigroups (fron N=0; sans isomorphs & anti-isomorphs): A001423: 1,1,4,18,126,1160,15973,836021,1843120128 Commutatives (from N=0; sans isomorphs): A001425: 1,1,4,129,43968,254429900,30468670170912, 91267244789189735259,8048575431238519331999571800, 24051927835861852500932966021650993560, 2755731922430783367615449408031031255131879354330 Note to NJAS: I think the sequence database is missing abelian semigroups of order 8, 221805. (From the Order 8 paper by Satoh &al.) The trick: For large N, the number of abelian tables is N^(N*(N+1)/2). [Divide by ~N! to discount isomorphs, but it doesn't change the gross order.] Very roughly, (N^N^2)^.5. The semigroups are dominated by the Dull Semigroups, which satisfy the equation A(BC)=(DE)F, or equivalently, XYZ=0. The multiplication table has an L-shaped swath of 0s at the top and left edge; the remaining portion of the table consists of random values <= the thickness of the L. The L that gives the most semigroups solves N = L (2 logL + 1), roughly L ~= N / (2logN). This gives (again very roughly) (N^N^2)^1 tables. Empirically, most semigroups are Dull: 85% of the 7s, and 99% of the 8s. I had a proof of this once, but can't recall it. (Usually a bad sign.) Since 1 > .5, the Semigroups must eventually overtake the Abelians. I wrote a Lisp function to do the estimates. I assumed the crossover would be around N=12, and was surprised it was so large. The crossing is sharp, and isomorphisms don't change it. Rules like Mid-Quartile-Swap, (AB)(CD) = (AC)(BD), one of the Average axioms, have even more tables than the semigroups. They have a sub-population of Dull-4 tables, where any product of four things, in any grouping, equals 0. These tables have an outer L of 0s, like the semigroups, and then an inner L with values <= outer-L-thickness, and then a lower-right square region with values <= outer+inner-L-thickness. These outnumber Dull Semigroups. In fact, because it has no top-level singleton, the MQS rule has an even larger set of Dullish tables, where the 0-region is only a small square in the upper-left corner, and the less-restricted values occupy a big lower-right L. For any Rule where each side has 2 or more operations, (like the ternary Defective Distributive Law for Majority, AB.CDE = ABC.ABD.E), Dull-ness will be a consideration, and will likely dominate the numbers. As the number of operations in the Rule is increased, more nested Ls are added, and the Dulls increase. Dullness can be somewhat counteracted by Commutativity, and is vanquished by Idempotence, or any rule with a singleton on one side. <the end of Dullness>