October 2005 - mathfun@mailman.xmission.com

Re: [math-fun] Ratio of two Bessel function values
by jdb＠math.arizona.edu 05 Oct '05

05 Oct '05

Dear Bill, There is a paper of D.H. Lehmer that may interest you: Continued fractions containing arithmetic progressions, Scripta Math., 29, (1973), 17-24. The results involve ratios of Bessel functions. Best, John PS By the way, I'm afraid I didn't make clear what I was asking before about computing the discriminant of a polynomial. What I was asking was how computer systems compute this, such as Macsyma. I was particularly interested in some systems that allow symbolic manipulation. I presume that Sylvester's determinant is involved in any case. I was interested in particular in a slick way to find the discriminant of the nth polynomial of a sequence of orthogonal polynomials given by a Favard recursion.

2 1

[math-fun] Nobel Prize, Vector Magic Squares, Rosser Consistency, Mental Prime Testing
by Network UPS Tools 05 Oct '05

05 Oct '05

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(a)cs.arizona.edu

2 1

[math-fun] Ratio of two Bessel function values
by Richard Guy 04 Oct '05

04 Oct '05

I recently asked, on one of these networks, about the number whose continued fraction is {1,2,3,4,...} and someone was kind enough to provide an explicit answer, which I've stupidly deleted. Can it be repeated? Incidentally, is there a more general result, that a continued fraction whose partial quotients form an arithmetic progression (or a set of APs) can be expressed in terms of Bessel functions? There are a few examples which are rational functions of e. R.

3 2

[math-fun] Information content of on a surface
by Henry Baker 04 Oct '05

04 Oct '05

In playing with my GPS system (Garmin GPS V) and the mapping functions, I became curious about how to minimize the data stored for the various streets. In particular, I was thinking only about the paths of the streets themselves, not the ancillary data about street names, etc. I noticed that the encoded streets do not always follow the actual streets, and I understand that this is a data compression problem, not a data gathering problem. Navtek, which gathers the data, drives all the streets, and collects data to within the error of the satellite GPS system, which in most cases is within 20-30 feet. While this is good enough to distinguish between two sides of a freeway, it isn't good enough to distinguish one lane of the freeway from the next. Nevertheless, the streets encoded within Garmin's digital maps are not stored to this degree of precision, and in several cases, the Garmin unit thinks that you have left the road even when you haven't. I have then compared the "bread crumb" trails of the GPS points with an actual paper map, and found that the paper map (and the trail of bread crumbs) was more accurate. While the problem is very similar to the encoding of data in a waveform (Shannon, etc.), it isn't exactly the same, since the goal in GPS encoding is to minimize the error distance from the actual road rather than minimizing "bandwidth". In particular, I would imagine that the usual "ripple" problems of polynomials won't matter, so long as the absolute value of the error is within bounds. Chebychev (sp?) approximations can be very high quality, but I'm not aware of any _information theoretic_ analysis of them. I.e., is anyone aware of any theory/theorems that would govern the number of bits required to stay within a particular error bound of a given continuous function?

1 0

Re: [math-fun] Counting problem
by Christian G.Bower 04 Oct '05

04 Oct '05

I think A059576 if read as a square array rather than as a triangle. This is essentially compositions (ordered partitions) of two colored objects. Think of a compartment of i white objects and j black objects as being i indices of a and j indices of b that are equal. Christian ID Number: A059576 URL: http://www.research.att.com/projects/OEIS?Anum=A059576 Sequence: 1,1,1,2,3,2,4,8,8,4,8,20,26,20,8,16,48,76,76,48,16,32,112, 208,252,208,112,32,64,256,544,768,768,544,256,64,128,576, 1376,2208,2568,2208,1376,576,128,256,1280,3392,6080,8016, 8016,6080,3392,1280,256 Name: Summatory Pascal triangle T(n,k) (0 <= k <= n) read by rows. Top entry is 1. Each entry is the sum of the parallelogram above it. Comments: We may also relabel the entries as U(0,0), U(1,0), U(0,1), U(2,0), U(1,1), U(0,2), U(3,0), ... U(n,k)=Sum_{i<n,j<k} U(i,j)= 2U(n-1,k) + Sum_{i<k} U(n,i). Also U(n,k)=Sum_{j=0..n+k} C(n,j-k+1)*C(k,j-n+1)*2^j - Jon Stadler (jstadler(AT)capital.edu) Apr 30 2003 U(n,k) is the number of ways of writing the vector (n,k) as an ordered sum of vectors, equivalently, the number of paths from (0,0) to (n,k) in which steps may be taken from (i,j) to (p,q) provided (p,q) is to the right and/or above (i,j). - Jon Stadler (jstadler(AT)capital.edu) Apr 30 2003 Links: Index entries for triangles and arrays related to Pascal's triangle Formula: G.f. U(z,w) = Sum_{n >= 0, k >= 0} U(n,k)*z^n*w^k = Sum{n >= 0, k >= 0} T(n,k)*z^(n-k)*w^k = (1-z)*(1-w)/(1-2*w-2*z+2*z*w). Maple code gives another explicit formula for U(n,k). T(n,k)=2*(T(n-1,k-1)+T(n-1,k))-(2-0^(n-2))*T(n-2,k-1) for n>1 and 1<k<n, T(n,0)=T(n,n)=2*T(n-1,0) for n>0, T(0,0)=1. - Reinhard Zumkeller (reinhard.zumkeller(AT)lhsystems.com) Dec 03 2004 Example: 1; 1,1; 2,3,2; 4,8,8,4; ... T(5,2) is the sum of the elements above it in the parallelogram bordered by T(0,0), T(3,0), T(2,2) and T(5,2). Maple: A059576 := proc(n,k) local b,t1; t1 := min(n+k-2,n,k); add( (-1)^b * 2^(n+k-b-2) * (n+k-b-2)! * (1/(b! * (n-b)! * (k-b)!)) * (-2 * n-2 * k+2 * k^2+b^2-3 * k * b+2 * n^2+5 * n * k-3 * n * b), b=0..t1); end; See also: Cf. A035002, A059226, A008288, A059283. First diagonals give A000079, A001792. T(2n, n) gives A052141. Row sums give A003480. Keywords: easy,nonn,tabl,nice Offset: 0 Author(s): Floor van Lamoen (f_DOT_v_DOT_lamoen_AT_wxs_DOT_nl), Jan 23 2001 ------ Original Message ------ Received: Mon, 03 Oct 2005 04:03:20 PM PDT From: "David Wilson" <davidwwilson(a)comcast.net> To: "Math-Fun" <math-fun(a)mailman.xmission.com> Subject: [math-fun] Counting problem > Suppose we have m numbers a_1 <= a_2 <= ... <= a_m, and n numbers b_1 <= b2 > <= ... <= b_n. > > How many different ways can the a_i and b_i be related with < and = ? > > For example, if m = 2 and n = 2, two possible arrangements are > > a1 < a2 = b1 < b2 (considered equivalent to a1 < b1 = a2 < b2) > b1 < a1 = a2 = b2 > > -------------------------------- > - David Wilson >

1 0

[math-fun] Nominee was rescued from a math major
by Thane Plambeck 04 Oct '05

04 Oct '05

I'm probably reading this wrong, but this is from a profile of the new Supreme court nominee, in today's New York Times: * * * She majored in math at Southern Methodist, but instead chose to go to law school, she has said, after a lawyer stepped in and organized her family's financial situation when her father was disabled by a stroke. "There's no question that the family owes a tremendous debt to that lawyer," [her sister-in-law] told the Dallas newspaper... -- Thane Plambeck http://www.plambeck.org/ehome.htm

1 0

[math-fun] So kill me
by David Wilson 04 Oct '05

04 Oct '05

I know this is off-topic. Just wanted to tell people here that my employment situation is critical, and any help would be appreciated. -------------------------------- - David Wilson

2 1

[math-fun] Multiplicative squares
by Christian Boyer 04 Oct '05

04 Oct '05

Website updated this morning! Go to <http://www.multimagie.com/indexengl.htm> www.multimagie.com/indexengl.htm: in the News of October 2005, there is a new page on multiplicative squares, including the results sent past week. The 10 first magic products should be sufficient for the site, but I send to Neil the 30 first terms of each order (3x3, 4x4, and 5x5) for his EIS. You will see that I've finally found a paper -published in 1983- already proving that the minimum product for 3x3 and 4x4 squares are 216 and 5040. But, Rich, your nice and short proof on 216 is in my new page! Christian.

2 2

[math-fun] Proof, the movie
by Thane Plambeck 04 Oct '05

04 Oct '05

I went to see the movie "Proof" last night and enjoyed it quite a bit, even if it upholds the long-standing cinematic tradition of finding mathematicians interesting only if they are also insane, or about to be insane, or recovering from having been insane. http://www.miramax.com/proof/ I've read some lukewarm reviews so thought I offer an endorsement up against that. -- Thane Plambeck http://www.plambeck.org/ehome.htm

3 2

[math-fun] Counting problem
by David Wilson 03 Oct '05

03 Oct '05

Suppose we have m numbers a_1 <= a_2 <= ... <= a_m, and n numbers b_1 <= b2 <= ... <= b_n. How many different ways can the a_i and b_i be related with < and = ? For example, if m = 2 and n = 2, two possible arrangements are a1 < a2 = b1 < b2 (considered equivalent to a1 < b1 = a2 < b2) b1 < a1 = a2 = b2 -------------------------------- - David Wilson

1 0