June 2006 - mathfun@mailman.xmission.com

[math-fun] Q-factorials
by Schroeppel, Richard 29 Sep '06

29 Sep '06

I've been playing with Q-factorials: QF(0) == 1 QF(N+1) == QF(N) * (1 + Q + Q^2 + ... + Q^N). When Q=1, this gives QF(N) = N!. The degree of QF(N) is Triangle(N-1) = N(N-1)/2. Q-binomials seem to be polynomials: QB(A,B) = QF(A+B) / (QF(A) QF(B)). The degree of QB(A,B) is AB. The degree of QB(A,B,C) = QF(A+B+C) / (QF(A)QF(B)QF(C)) is AB+AC+BC. Etc. Perhaps we can use some of our standard bag of tricks for defining QF(N) for non-integer N. Put QF(Z) ~= Q ^ [ Z(Z-1)/2 ] for RealPart(Z) large, and divide by (Q^Z-1)/(Q-1) to go from Q(Z) to Q(Z-1). There's a set of functional equations similar to X! (X+1/2)! = (2X+1)! * stuff. Presumably there's also a reflection equation with QF(Z) QF(-Z) = more-stuff that looks like pi Z / sin(pi Z). Rich

5 7

P.S. Re: [math-fun] Chinese Mathematicians Prove Poincare Conjecture
by dasimov＠earthlink.net 08 Sep '06

08 Sep '06

P.S. I did not see this in the Ximhua press release, but the Asian Journal of Mathematics says (in the link provided by Ray) that the article in question finishes the proof of the Thurston Geometrization Conjecture (of which the Poincare conjecture is just one of many important consequences). Up to now, a few media (Scientific American in 1994, New York Times in the past year) have claimed the Poincare conjecture has been proved, although no respectable professional journal has reported any such thing (only comments like "time will tell.") And not even media outlets have reported that the Geometrization conjecture was proved. Hmm. I guess time will tell. --Dan

13 19

[math-fun] Abelian group puzzle
by dasimov＠earthlink.net 07 Jul '06

07 Jul '06

Let P denote the direct product of countably many copies of the integers Z. E.g., the set {f: Z+ --> Z | f is a function} under addition of functions. Puzzle: Is P a free abelian group? Prove your answer. --Dan

5 7

[math-fun] Logic puzzle
by franktaw＠netscape.net 05 Jul '06

05 Jul '06

It is well known that the first-order theory of the non-negative integers with only addition available is decideable, while the theory with addition and multiplication is not. Suppose we have addition and the number of divisors function (often called d(n) or tau(n)). Is the theory then decideable or not? Proof requested. Franklin T. Adams-Watters

1 2

[math-fun] Sudoku levels
by Henry Baker 02 Jul '06

02 Jul '06

I've since extended my program to what I call "level 2" -- propagating forcing constraints a bit further: If a digit in a _row_ can only appear in 2 or 3 positions within the same 3x3 block, then that digit is eliminated from the rest of the block. If the digit can appear in multiple blocks, then we can't eliminate it. Ditto for columns. For blocks, the rule is more complicated. If a digit can only appear within a single row or column within a block, then it can be eliminated from the rest of the row or column, respectively. These new rules, together with the previous set of forcing rules, appears sufficient to solve the LATimes Sudoku's called "Moderate", while the previous set of rules were sufficient for those called "Gentle". However, my "level 2" is not sufficient for LATimes "Diabolical", nor for the Sudoku's in "Sudoku Genius". It would appear that the LATimes _does_ have a precise definition of what it means to be "Gentle" (~ level 1), "Moderate" (~ level 2), and "Diabolical". Since "level 2" appears to be exhausting the notion of what can be done with only local rules & "force fields" (the information propagating on rows, columns & blocks), I would suggest that level 2 captures the notion of "non-backtracking". --- BTW, I mentioned that my bit representation produced "surprises" in that some squares "accidentally" produced singleton sets. However, because these singletons were "accidental", they didn't get a chance to propagate their "first-class" status and suppress the same digit in rows, columns and blocks. While this problem is automatically fixed by level 2, this constraint really belongs to level 1, and so my level 1 program has to have an extra check just for this constraint. "The representation giveth, and the representation taketh away."

3 4

Re: [math-fun] Re: genetics-fun question -- another one
by dasimov＠earthlink.net 30 Jun '06

30 Jun '06

Just a few months ago my sister mentioned to me that her husband's U.S. ancestors all descended from just one married couple, who came to the U.S. around 1650, before having any children. She asked me how many living descendants (whether or not still in the U.S.) that family has today . I had nothing else to go on, so it was a rough seat-of-the-pants blue-sky back-of-the-envelope ballpark guesstimate. Just for fun I'd like to ask anyone interested in coming up with their own estimate to send it to me without posting it to math-fun. On Monday or so I'll post everyone's estimate (including mine). --Dan

1 0

Re: [math-fun] Sudoku levels
by Henry Baker 30 Jun '06

30 Jun '06

Dear Joshua & Mike: I see now what you're saying. No, I implemented a strictly weaker rule, but your rule is more elegantly stated. I'll run some tests. If it can solve "Diabolical" level Sudoku's, then it would be too strong. The intuition of your rule is that if one square isn't strong enough on its own (singleton set) to lay down suppressing fire & kill off pretenders to the digit, then groups of squares might be able to suppress some pretenders. At 08:51 AM 6/30/2006, Joshua Zucker wrote: >I'm not clear from your description of level 1 whether you look at >every set of k cells -- if a set of k cells out of 9 includes at most >k different digits, then those k digits can't appear anywhere else in >the set of 9. (I was very pleased when I realized that this rule with >k = 1 and k = 8 covered the two usual simplest rules, "if a cell can >contain only one digit..." and "if a digit can appear in only one >cell...") > >--Joshua Zucker

1 0

[math-fun] Re: genetics-fun question
by James Propp 30 Jun '06

30 Jun '06

>So figuring out who's mother and who's daughter is as easy as labelling >their genomes a,b and c,d and noticing which of them has the property >that, eg, ccccccccccccc is the same as aaaabbbaabbbb. Neat! (And not even all that subtle; if I'd thought a bit harder about what I supposedly learned in high school, I could've figured it out.) This fact about the asymmetry of the parent-child relationship suggests a more general question: How much can you deduce about the precise way in which two blood-relatives are related simply from looking at their genes? This can be a real-world issue ("And is it your sworn testimony before this court, as an expert in the field of genetics, that this man cannot possibly be the nephew of Howard Hughes?"), but I could imagine it also giving rise to some mathematically amusing albeit unrealistic puzzles ("Assume an infinite genome..."). Michael? Jim

6 7

Re: [math-fun] Sudoku levels
by Henry Baker 30 Jun '06

30 Jun '06

Dear Joshua: I don't understand the description of your rule. Do you mean _any_ k cells, whether or not they're in rows, columns or blocks? Furthermore, what do you mean by "at most k" ? At 08:51 AM 6/30/2006, Joshua Zucker wrote: >I'm not clear from your description of level 1 whether you look at >every set of k cells -- if a set of k cells out of 9 includes at most >k different digits, then those k digits can't appear anywhere else in >the set of 9. (I was very pleased when I realized that this rule with >k = 1 and k = 8 covered the two usual simplest rules, "if a cell can >contain only one digit..." and "if a digit can appear in only one >cell...") > >--Joshua Zucker

1 0

[math-fun] New? multiplicaiton of GF2 polynomials
by Schroeppel, Richard 30 Jun '06

30 Jun '06

Before log tables were invented, there were a couple of other tricks that were useful for multiplication. One way was to use trig identities like cosX * cosY = (cos(X+Y) + cos(X-Y))/2. Another was to use a table of triangular numbers, T(x) = x(x+1)/2 x * y = T(x+y) - T(x) - T(y) or Quarter-Squares, Q(N) = floor[N^2 / 4] x * y = Q(x+y) - Q(x-y). The key idea in each case is to use a table that's a function of one variable in a clever way to compute a two-variable result. (I'm skeptical about these actually being used much, since the required tables are still pretty big. But I've never actually looked over Mr. Fibonacci's shoulder.) I'm looking for an appropriate generalization for GF2 polynomial multiplication. (Multiplication of polynomials where the coefficients are reduced mod 2.) Each of the methods above uses division by 2, so some minor variation is necessary. There are about six different ways to do GF2 polynomial products. I'm wondering if the scheme below is new. Define F(X), a kind of T-surrogate, as follows. Represent X as a block of bits: X = t^3 + t^2 + 1 --> 1101. For each pair of 1 bits, accumulate the product (using xor), into a total. This total is F(X). In the example, the terms to be xored are 1000 * 1, 100 * 1, and 1000 * 100. The total is 101100. (Representing t^5 + t^3 + t^2.) Then it appears that X * Y = (X&Y)^2 + F(XvY) + F(X&Y) + F(X&~Y) + F(Y&~X). The logic operators & v ~ are to be used on right-justified bit patterns. The squaring operation is fast in GF2, simply spread out the bits, interleaving with 0s. (Squaring is a linear operator in GF2.) Has anyone seen anything like this? Rich

5 6