Nobel Prize, Vector Magic Squares, Rosser Consistency, Mental Prime Testing Nobel Prize I labeled my remark about the Nobel Prize in Medicine "About Time", and John McKay asked What is your point, Rich? There was no discovery of Helibacter pylori - just recognition that it occurs in the stomach and withstands the acid there. Marshall had one hell of a fight to establish recognition among the medical profession for his results. What analogous mathematical results are you thinking of? The discovery of the true cause of stomach ulcers improved the health of lots of people, and deserves a prize. Most of the recent Medicine prizes have been for more basic science. This could ultimately lead to better health, but it seems pretty long term. Thus my remark about theoreticians. The ulcer discovery had immediate practical results. I think it should have been honored as soon as the results were accepted, or as soon as the health consequences became apparent. I wasn't thinking of any particular mathematical discovery. We don't have a corresponding math prize. The Fields Medal has explicit age discrimination, perhaps preventing the lifetime achievement awards typical of the Nobels. And maybe it's just as well that mathematics recognition is diffused across the profession rather than being decided by a small committee in Stockholm. --- Vector Magic Squares Another way of looking at mul(tiplicatively ma)gic squares is as magic squares whose entries are integer vectors. The vectors are drawn from the first quadrant/octant/orthant/etc.; i.e. the vector entries are nonnegative. We then score minimality by dotting the magic vector sum with the vector of log(primes): (log2, log3, log5, ...). The requirement of using the numbers from 1 to N^2 can be reinterpreted as using a set of vectors that forms a connected polyomino/cube/tess/etc. --- Rosser Consistency
S is a Rosser proof of the formula A iff S is a proof of A and all proofs S' with smaller Godel code than S don't prove not(A).
I was intrigued with this way of patching up a possibly inconsistent logical system. Shorter proofs are better, perhaps more reliable. As if each use of an axiom or rule of logic had some chance of error, so the shorter proof gets more weight than the longer one. However, there's a problem. We could have a situation where A has the shortest proof, but ~A has a somewhat longer proof, and the proof of ~~A is a bit longer still, and then ~~~A and so on. All of A, ~A, ~~A, ... would be regarded as proved, since their literal negations had longer, not shorter, proofs. The obvious fix is to regard A and ~~A as the same proposition. But the logical follow through of this is to require that all propositions logically equivalent to A count as "the same". Some other equivalent propositions are AvA, A&A, ~A -> A, (B->A)&B, ... This is an uncomfortable fix. This is not just splitting hairs: In the startup of the usual Russell-Whitehead axioms for propositional calculus (do they get credit for the system?), there are early lemmas like ~~~P -> ~P, and I think there's even a ~~~~P -> ~~P. And of course the intuitionists would crab about equating P with ~~P. --- Mental Prime Testing I like to factor small numbers mentally. Often I'll get down to a four digit number that seems prime, but requires a fair amount of trial division to confirm. I've recently been using a new technique that requires less work. It works on half the odd numbers, the 4K+1s. A 4K+1 prime has a unique representation as the sum of two squares. If an odd number N is the sum of two squares in exactly one way, and the two squares are relatively prime, N is prime. If I have a good way of splitting N into squares, and I'm sure it covers all possible splits, I can get information about N. If there's no representation, N must have at least one 4K+3 divisor. (If N is a 4K+1, it must be the product of at least two 4K+3 divisors, and "difference of squares" is useful, along with a faster trial division.) If there's a single split into two squares, and the roots are relatively prime, N is prime. If the roots have a common factor, its square divides N. If there are two splits, then both the dot and cross products of the two "root vectors" will share a factor with N. My new (to me) method for mentally splitting N into squares: Suppose N ends in 1 or 9. If N is the sum of two squares, say X2+Y2, what are the last-digit possibilities for X2 and Y2? Answer: One of them must be divisible by 5. So I may assume that, say, X2 ends in either 00 or 25. This is a modest restriction, but it has a useful consequence: The last two digits of the co-square, Y2, can be computed as the last two digits of N or N-25. There is only one potential Y value < 25, whose square has the correct final two digits, and the other possibilities less than 100 are 50-Y, 50+Y, and 100-Y. (The pattern continues if I need to check larger Ys.) So I can try a few Ys, and check if N-Y2 is a square. This is relatively quick, since the difference is either xx00 or xx25; in the former case, xx must be a square; in the latter, of the shape z(z+1) and the hundreds digit one of 0,2,6. Example: The Coconut Number 3121. The low two digits of Y2 are either 21 or 96. The smallest Ys are 11 and 14, then 36 and 39, and then 61 is too big. Checking, 3121-121 = 3000 (not square); 3121-1521 = 1600 (bingo); 3121-196 = 2925 (nope); 3121-1296 = 1825 (nope). 3121 = 1521 + 1600 or 39^2 + 40^2, and 39 & 40 are coprime, so 3121 is prime. If there were no square split, I'd know to look for a 4K+3 divisor. If there are two splits, such as 10001 = 10000 + 1 = 5776 + 4225, I dot (100,1) with (76,65) = 7665 -> 5 * 1553 -> 3 * 511 -> 7 * 73, and 73 divides 10001. What if my number doesn't end in 1 or 9, but instead 3 or 7? Answer: Double it. And then assume X2 ends in 25. Drop the 00 case. Example: 5333. Doubled is 10666, so Y2 ends in 41, and Y = 21,29,71,79; 121 is too big. 10666-441 = 10225 (no), 10666-841 = 9825 (no), 10666-5041 = 5625 (yes), 10666-6241 = 4425 (no). I note that the square roots 71 and 75 are relatively prime, so my original target 5333 is prime. I can recover the split for 5333 from the average and semi-difference of 71 and 75: 5333 = 5329+4 = 73^2 + 2^2. This idea seems extensible to other odd numbers, using the form X2 + 2Y2 for 8K+3, and X2 - 2Y2 for 8K+7. There are some complications though. For the 8K+3 case, there's no guarantee that either X or Y is a multiple of 5. The fixup is to also check 3N. Either N or 3N will have a multiple of 5 somewhere in an X or Y. For 8K+7, the definition of uniqueness needs repair by adding the side condition |X|>|2Y|, or |X|<sqrt(2N). I think the non-multiple- of-5 problem can be fixed either by multiplying N by 7, or allowing the alternate representation N = 2X2 - Y2, or by expanding the range of X some by multiplying X+Ysqrt2 by the unit 1+sqrt2. I'm still investigating this case. Another idea to look at is to replace the roles of 5 and 25 with 7 and 49, or 11 and 121. This has the advantage that 2 is a quadratic residue of 7, and -2 of 11, simplifying the analysis of the X2-2Y2 and X2+2Y2 cases. But there's a big drawback, since my mental arithmetic works best in base 10, while bases 14 and 22 are hard. Rich rcs@cs.arizona.edu