November 2014 - mathfun@mailman.xmission.com

[math-fun] Divisor runs
by David Wilson 21 Nov '14

21 Nov '14

The number 6 has divisors (1, 2, 3, 6). Thus it has a run of 3 contiguous divisors (1, 2, 3). What is the smallest number N with - A run of at least 5 divisors? - A run of exactly 5 divisors? - A maximum run of exactly 5 divisors?

2 3

Re: [math-fun] "Imitation Game" slanders Turing (Henry Baker)
by Henry Baker 21 Nov '14

21 Nov '14

The Soviets were using "unbreakable" 1-time pads that were never, ever to be used again (Chorus: well, hardly ever!). The amazing thing is that this reuse was discovered and enabled significant decrypts: https://en.wikipedia.org/wiki/Venona_project The BBC did a pretty decent documentary about Tommy Flowers, which used to be available on YouTube, but I wasn't able to readily find it again (the BBC apparently complained to YouTube about this). If you search hard enough, you may be able to find this video on the Internet somewhere, or perhaps on Netflix. It does seem that Flowers is getting screwed by cryptography twice: first during WWII, and now by DRM/DMCA! At 05:10 PM 11/20/2014, Warren D Smith wrote: >Plus, Cairncross (genuine >spy) gave the USSR some decypts so they likely KNEW the UK had >decryption capability for such machines ANYWAY! > >In particular Tommy Flowers, their main computer designer/builder, >was... well, I bet you'd never heard of him. You've heard of guys >like Eckert & Mauchly who probably were a lot lesser.

2 1

[math-fun] Sallows squares
by Keith F. Lynch 21 Nov '14

21 Nov '14

I've done some work on (semi)magic squares whose elements' reciprocals also form (semi)magic squares. I'm calling them Sallows squares, for Lee Sallows, who introduced the idea here on October 12th. Lemma 1: If a+b = c+d and 1/a + 1/b = 1/c + 1/d, a, b, c, and d being different from each other, then two of the four numbers must be the negatives of the other two. Proof: There must exist a non-zero n such that c = a+n and d = b-n. Then 1/a + 1/b = 1/(a+n) + 1/(b-n) = ((a+n)+(b-n)) / (a+n)(b-n) = (a+b)/(a+n)(b-n) = (a+b)/(ab+bn-an-nn) = (a+b)/(ab + n(b-a-n)). 1/a + 1/b = (a+b)/(ab), so (a+b)/(ab) = (a+b)/(ab + n(b-a-n)). If a+b is non-zero, we can take the reciprocal of both sides, then multiply by a+b, to get ab = ab + n(b-a-n), so n(b-a-n) = 0. Since n != 0, b-a-n = 0. But since b-n = d, a must equal d, contradicting the claim that a, b, c, and d were distinct. So a+b must be 0. (And, by symmetry, c+d must also be 0.) QED. Lemma 2: If a+b+c+d = 0 and 1/a + 1/b + 1/c + 1/d = 0, with a, b, c, and d being real and being different from each other, then two of the four numbers must be the negatives of the other two. Proof: Since the sum is zero, the numbers can't all have the same sign. So either one is is one sign and the other three are the other, or it's two and two. Two and two with two of the four numbers not being the negatives of the other two is ruled out by lemma 1, since if, for example a and b are positive and c and d are negative, a+b+c+d = 0 would mean a+b = c+d, and 1/a + 1/b + 1/c + 1/d = 0 would mean 1/a + 1/b = 1/c + 1/d. So that leaves one number with one sign and the other three with the other. Choose any two of the four numbers with opposite signs. If their absolute values are equal, then they're negatives of each other, and since the other two numbers have the same sign as each other, they can't add up to 0. (They can't *be* 0, since 0 has no reciprocal. And also because they would be duplicates.) So the two you chose have different absolute values. Whichever number has the larger absolute value, the remaining two numbers would have to have the opposite sign to make a+b+c+d = 0 work, but would have to have the same sign to make 1/a + 1/b + 1/c + 1/d = 0 work. For instance if the numbers you chose were 1 and -6, to make the latter equation work the other two numbers might be -3 and -2, but to make the former equation work, the other two numbers might be +3 and +2. So one with one sign and three with the other can't work either. QED. Theorem 1: An order-3 semimagic (or magic) Sallows square is impossible. Proof: Consider the semimagic square: ABC DEF GHI A+B+C = A+D+G, and 1/A + 1/B + 1/C = 1/A + 1/D + 1/G, so B+C = D+G, and 1/B + 1/C = 1/D + 1/G, so, by lemma 1, B+C = 0. But, by left- right symmetry, A+B also equals 0. Since A+B = B+C then A=C, violating uniqueness. QED. Theorem 2: A real-number order-4 magic Sallows square is impossible. Proof: Consider the magic square ABCD EFGH IJKL MNOP with sum S. Add the top and bottom rows and the main diagonal, and subtract from that the middle two columns and the other diagonal: (A+B+C+D) + (M+N+O+P) + (A+F+K+P) - ((B+F+J+N) + (C+G+K+O) + (D+G+J+M)) = 0. After canceling, you get (2A + 2P) - (2G + 2J) = 0, i.e. A+P = G+J. But it must also be the case that 1/A + 1/P = 1/G + 1/J, so by lemma 1, A = -P and G = -J. By symmetry, D+M = F+K and 1/D + 1/M = 1/F + 1/K, so D = -M and F = -K. That means the diagonal sums are both 0, so the magic sum is 0. It's easy to construct such a magic square, for instance 1 -5 -3 7 -2 6 4 -8 8 -4 -6 2 -7 3 5 -1 but the reciprocals can't be made to work, except on the diagonals. Consider the top row, A,B,C,D. None of the numbers on that row can be the negative of A, since that value is taken by P. None of the numbers on that row can be the negative of D, since that value is taken by M. So A and D must have different absolute values. As such, B and C can't be negatives of each other, since if they were they'd sum to 0, in which case A+B+C+D wouldn't sum to 0. So lemma 2 shows that there's no solution to that row. QED. (The same argument applies to every row and every column, but it only takes one bad row or column to ruin the square.) I haven't proven that an order-4 magic square in complex numbers is impossible, though I believe it is. Perhaps one of you can extend my proof to cover complex numbers. Note that lemma 1 applies to complex numbers, but lemma 2 does not. I haven't proven that a real order-4 semimagic square is impossible. I've been trying to find one in positive rationals by an extensive search. First, note that if there's a solution in rationals, there's a solution in integers, since the rationals can all be multiplied by their common denominator without disturbing either the magic square or the reciprocal magic square (though it may change their magic sums). My method is, for each positive integer sum, find all possible sets of four numbers that add up to that sum, then find all sets of at least eight such sets whose reciprocal sums are equal to each other. Then I try to assemble eight of them into a semimagic square. Here's the best I've found so far: {100,110,450,1100}, {104,120,288,1248}, {60,408,612,680}, {60,420,560,720}, {60,450,500,750}, {66,231,693,770}, {66,264,440,990}, {70,195,585,910}, {70,234,364,1092}, {72,176,720,792}, {79,180,316,1185}, {80,144,576,960}, {80,180,300,1200}, {85,136,459,1080}, {86,126,645,903}, {90,170,225,1275}, {95,126,342,1197}, {99,121,330,1210}. Those 18 sets of four numbers all sum to 1760, and their reciprocals all sum to 1/45. Good luck finding better; I looked at more than 40 billion sets of four numbers to find those. But it's no good. As with every such set of sets that I've found, each set of four contains at least one number not found in any of the other sets. For instance in {100,110,450,1100} above, only 450 appears in another of the 18 sets of sets. Obviously for any permutation of {100,110,450,1100} to be a row or column of a semimagic square, all four of the numbers must appear in other sets. (At least lemma 1 guarantees that if they do, they'll be in four different sets, which is what we want.) Maybe there's a proof that every such set must contain at least one number not found in any other set. If so, a semimagic order-4 Sallows square in positive rationals is impossible. Or maybe it's just a matter of probabilities, given that those numbers seem to be almost randomly chosen from the numbers less than the target sum S. (There does seem to be a bias toward numbers with lots of divisors (e.g. 47 of the 63 distinct numbers in that set of sets are even). Also, I'm excluding all numbers divisible by a prime greater than S/4, as those can't possibly be part of a Sallows square. Can you see why not?) If it is just a matter of probabilities, then finding such a semimagic square without insights to greatly narrow the search would be almost intractable. I haven't yet searched for a semimagic square in mixed signs, only in positives. I haven't yet done anything with orders greater than four (except for the order-six complex-number semimagic square I posted on October 15th).

2 1

[math-fun] mathway.com
by David Wilson 20 Nov '14

20 Nov '14

Half-decent web interface, but it solves sin(x) = cos(x) incorrectly, and it doesn't even give a numerical approximation for cos(x) = x. The popup brags about the number of problems solved, let's hope it's not homework.

1 0

[math-fun] "Imitation Game" slanders Turing (Henry Baker)
by Warren D Smith 20 Nov '14

20 Nov '14

Since Turing died 60 years ago and no heirs, I daresay nobody can sue. What actually was a much larger problem was the fact that after WW II, Churchill ordered that most of the Bletchley computers be destroyed by chopping into tiny pieces and everybody was sworn to secrecy including about the machines' very existence. This was since there were still Nazi crypto machines floating around, which mostly had been appropriated by, e.g. Russia for use, and Churchill wanted to crack their codes to the extent they kept using those old machines for postwar communication. As a result of this, the careers of what otherwise would have been Computer Pioneers, were almost entirely destroyed, and the advent of computers generally was set back by perhaps 10 years. Was that really worth the "benefit" of being able to listen in on a few Russian communications? Plus, Cairncross (genuine spy) gave the USSR some decypts so they likely KNEW the UK had decryption capability for such machines ANYWAY! In particular Tommy Flowers, their main computer designer/builder, was... well, I bet you'd never heard of him. You've heard of guys like Eckert & Mauchly who probably were a lot lesser.

1 0

[math-fun] vector domination probability problem (insanely annoying)
by Warren D Smith 20 Nov '14

20 Nov '14

I stumbled across this apparently true fact: Choose N random i.i.d. real numbers (from some fixed probability density) then sort them; result is (a,b,c,d,...,z). Do it again independently, result is (A,B,C,D,...,Z). Then what is the chance that a<A, b<B, c<C, ..., and z<Z simultaneously? ("vector domination") My original incorrect answer was 2^(-N). Complete with wrong proof. My new correct answer is 1/(N+1). I proved this for N=1,2,3,4,5,6. It presumably is true for N=7,8,9... too. But what is the proof? Surely something this simple must have a simple proof?

3 3

[math-fun] undecidability of morality
by Warren D Smith 19 Nov '14

19 Nov '14

> http://arxiv.org/abs/1411.2842 > > Logical Limitations to Machine Ethics with Consequences to Lethal Autonomous > Weapons > > Matthias Englert, Sandra Siebert, Martin Ziegler --so apparently the idea is, if there is some killer machine, whose construction and programming is known to you, and you have to make a moral decision about what to do about it -- then since you cannot solve the halting problem, you cannot tell what said machine will do, hence deciding which is more moral among two courses of action can be Turing-undecidable. So lethal autonomous weapons will either be unable to function, or will be unable to be moral.

6 8

[math-fun] vector domination probability problem (insanely annoying)
by Warren D Smith 19 Nov '14

19 Nov '14

> From: Gareth McCaughan <gareth.mccaughan(a)pobox.com> >> WDS: I stumbled across this apparently true fact: >> >> Choose N random i.i.d. real numbers (from some fixed probability >> density) then sort them; >> result is (a,b,c,d,...,z). >> >> Do it again independently, result is (A,B,C,D,...,Z). >> >> Then what is the chance that a<A, b<B, c<C, ..., and z<Z >> simultaneously? >> ("vector domination") > > G.McC: > Put 'em all together and sort them. Now go through them in order > and move north 1 unit when you see an a/b/.../z and east one unit > when you see an A/B/.../Z. The "vector domination" criterion is > the same as saying that you never go below the line x=y (starting, > of course, at the origin). The fact that you chose N of each says > that you end up at (N,N). > > But now we have a familiar problem with a familiar answer. The > number of paths with this property is, e.g., the same as the > number of properly-nested sequences of parentheses: the N'th > Catalan number, which "as every schoolboy knows" is > (2N choose N) / (N+1). There are plenty of proofs of this > around; choose your favourite. --Superb!!! Excellent!! Wow!!! I'd actually just figured out what looked like it was going to be a proof of my own, which was, however, going to be way more horrible than your proof. This is a new kind of "ballot problem"; there is a considerable literature on such problems but I happen to think this particular problem is nicer than most of them. Here's a tutorial by Steven R. Dunbar about various kinds of ballot problems, which is by no means a complete survey... but I did look in a number of such surveys and my problem was not in them... http://www.math.unl.edu/~sdunbar1/ProbabilityTheory/Lessons/BernoulliTrials… In a sense, your "sort 'em all together / north+east" trick converts my continuous kind of ballot problem into one of the old discrete kinds. Your trick should then also solve the version where one sequence of numbers has N elements and the other has k*N (where k=1,2,3,... is fixed) and your line now has slope=k (or 1/k).

1 0

[math-fun] Grothendieck's politics
by dupre＠math.rutgers.edu 19 Nov '14

19 Nov '14

This is just to remind you, in case you have forgotten, or never knew, that Grothendieck intentionally put himself in harm's way when he was lecturing during the US bombing of Hanoi, in a forest on this city's outskirts. I don't know whether it is off-topic on this mailing list to mention the politics, even one as famous as Grothendieck, but among others, this was one of his passions in life, besides his vegetarianism and love of animals. Grothendieck was a great mathematician and even greater man. Art DuPre

5 5

Re: [math-fun] undecidability of morality
by Warren D Smith 19 Nov '14

19 Nov '14

A way occurred to me to try to dodge the "undecidability of morality" theorem... but I think it runs into new different impossibility of morality theorems. Assume all the killer robots are constructed to have algorithms inside, which provably always halt in polynomial time. (You can easily design a programming language in which every program provably halts in polytime, e.g. since there is a cutoff timer initialized after reading input with some polynomial value.) In that case, the robots' behaviors are always decidable, so their impossibility proof fails. However... assuming robots flip coins inside their algorithms, the probability the program halts is #P-complete to compute or approximate. Hence if P < #P, it again is impossible for a polynomially-bounded entity to be moral. Further, it seems to me that if you construct an N-player game, even if each individual player is extremely simple, then the net expected outcome of the game, can be #P-complete to compute. Proof, the game is an N-input logic circuit and the inputs (players) are coin flips and the probability the output is '1' is #P-complete. Also true for "planar logic circuits." So even in a world containing N incredibly simple entities only, besides yourself, you still cannot make predictions about the world N timesteps ahead (hence cannot make moral choices) if you have less than #P computational power. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0