July 2014 - mathfun@mailman.xmission.com

Re: [math-fun] Tarski and Multiplication
by Henry Baker 07 Jul '14

07 Jul '14

You might try the book that is referenced: Tarski, Alfred; Jan Tarski (24 March 1994). Introduction to Logic and to the Methodology of Deductive Sciences (4 ed.). USA: OUP. ISBN 978-0-19-504472-0 Or you might try to contact the wikipedia article editor. At 10:15 AM 7/7/2014, Scott Fenton wrote: >Hi all, > >In Tarski's "Introduction to Logic", he gave a nice little set of eight >axioms that he says uniquely define the real numbers ( >http://en.wikipedia.org/wiki/Tarski%27s_axiomatization_of_the_reals) He >further said that, using less than, cuts, and addition, you could define >multiplication in this system. Does anyone here know if he published >anything else on this system? I can't seem to dig anything up, and I'd like >to know how he defined things. > >Thanks, >-Scott

2 1

[math-fun] Tarski and Multiplication
by Scott Fenton 07 Jul '14

07 Jul '14

Hi all, In Tarski's "Introduction to Logic", he gave a nice little set of eight axioms that he says uniquely define the real numbers ( http://en.wikipedia.org/wiki/Tarski%27s_axiomatization_of_the_reals) He further said that, using less than, cuts, and addition, you could define multiplication in this system. Does anyone here know if he published anything else on this system? I can't seem to dig anything up, and I'd like to know how he defined things. Thanks, -Scott

1 0

[math-fun] (no subject)
by Bill Gosper 07 Jul '14

07 Jul '14

Whoa, how are you getting these? Convergence is absent or useless. WDS> h(n) = (-1)^(parity of bit-sum of binary representation of n) f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large] ln(x+1) S=-log(2)/2 ln(x+2) S = -0.1379330125 ln(x+3) -0.07070756527 x^j 0 for any fixed integer j>=0 1/(x+1) 0.398761088108 [http://isc.carma.newcastle.edu.au/advancedCalc identifies this as 3^(1/6)/Zeta[3]^(5/237)/3 . I'm surprised you didn't notice.] 1/(x+2) 0.1049709156499 sqrt(x) -0.63407426 1/sqrt(x+1) 0.1983140804979 -- Warren D. Smith With f(x):= 2^(x+1), the quantities (1+S)/2 and (1-S)/2 are the only solutions t to Peano[t] = {t,1}. I.e., in the square-fill, they map straight to the top edge. --rwg

3 2

[math-fun] Some Wilsonian sums
by Warren D Smith 07 Jul '14

07 Jul '14

h(n) = (-1)^(parity of bit-sum of binary representation of n) f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large] ln(x+1) S=-log(2)/2 ln(x+2) S = -0.1379330125 ln(x+3) -0.07070756527 x^j 0 for any fixed integer j>=0 1/(x+1) 0.398761088108 1/(x+2) 0.1049709156499 sqrt(x) -0.63407426 1/sqrt(x+1) 0.1983140804979 -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 5

[math-fun] Thue-Morse sums
by Bill Gosper 07 Jul '14

07 Jul '14

[Adding subject; fixing bug.] Whoa, how are you getting these? Convergence is absent or useless. WDS> h(n) = (-1)^(parity of bit-sum of binary representation of n) f(x) S=SUM[ f(n) * h(n), for n=0..2^k-1 with k large] ln(x+1) S=-log(2)/2 ln(x+2) S = -0.1379330125 ln(x+3) -0.07070756527 x^j 0 for any fixed integer j>=0 1/(x+1) 0.398761088108 [http://isc.carma.newcastle.edu.au/advancedCalc identifies this as 3^(1/6)/Zeta[3]^(5/237)/3 . I'm surprised you didn't notice.] 1/(x+2) 0.1049709156499 sqrt(x) -0.63407426 1/sqrt(x+1) 0.1983140804979 -- Warren D. Smith With f(x):= 2^-(x+1), the quantities (1+S)/2 and (1-S)/2 are the only solutions t to Peano[t] = {t,1}. I.e., in the square-fill, they map straight to the top edge. --rwg

1 0

[math-fun] Flanelle history and the solution of Wilson's sqrt(2) problem
by Warren D Smith 07 Jul '14

07 Jul '14

Consulting http://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence , the section about "The Prouhet-Tarry-Escott problem" I see that "Flanelle's theorem" was discovered previously by Eugene Prouhet in 1851. Also, "my" closed form WIlsonian sum for C^n, also was known previously, I infer from http://mathworld.wolfram.com/Thue-MorseConstant.html Indeed this paper Jean-Paul Allouche and Jeffrey Shallit: The ubiquitous Prouhet-Thue-Morse sequence, Sequences and their applications, Proceedings of SETA'98 (Springer 1999) pages 1-16 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.476&rep=rep1&t… discusses that, and in section 52, it gives the solution to David Wilson's sqrt(2)/2 problem, which was proved by David Robbins in problem E2692, Amer. Math'l Monthly 86 (1979) 394-395 solving a puzzle posed by D.R.Woods in AMM 85 (1978) 48 and also solved by Allouche in 1987 as explained in this paper with a short proof. On the other hand, the Flanelle(P) generalization might be new, anyhow was not mentioned in these sources, and the more general problem of compiling a table of "Wilsonian sums" -- which we now see ought to be called "Thue-Morse sums" or "Prouhet sums" -- also might be new (by the same criterion).

1 1

Re: [math-fun] Numerical integration & summation using Flanelle(P)
by Adam P. Goucher 06 Jul '14

06 Jul '14

Warren, Flanelle(P) is a beautiful result. What follows is a more rigorous proof, and one that doesn't even require P to be prime. Let P be a positive integer, and operate in the following quotient ring F: F = C[X]/(1 + X + X^2 ... + X^(P - 1)); I claim the following result holds: -------- Theorem 1 (P-Flanelle's theorem): Let f(z) be a polynomial of degree at most k-1. Then the following sum is zero: f(a) X^h_P(0) + f(a + d) X^h_P(1) + f(a + 2d) X^h_P(2) + ... + f(a + (P^k - 1)d) X^h_P(P^k - 1) where h_P(n) = digit sum of n in base P. -------- This is, by definition of F, equivalent to your idea of `all colour classes have the same sum'. Note that I've made a (trivially equivalent) generalisation to any arithmetic progression of length P^k, rather than the specific progression {0, 1, 2, ..., P^k - 1}. We will induct on the value of k. Suppose P-Flanelle's theorem is true for all polynomials of degree <= k - 2, and let f(z) be a polynomial of degree k - 1. Define g(z) = f(z) + f(z + d) X + f(z + 2d) X^2 + ... + f(z + (P - 1)d) X^(P - 1). We want to show that g(z) has degree <= k - 2 (over z), and then apply the inductive hypothesis to g with an initial term of a and common difference Pd (i.e. P times the original common difference). Now, by linearity, it suffices to consider the case f(z) = z^(k-1). Then we have: g(z) = z^(k-1) + (z + d)^(k-1) X + (z + 2d)^(k-1) X^2 + ... + (z + (P - 1)d)^(k-1) X^(P - 1). Binomially expand each of the coefficients (when viewed as a polynomial in X) and consider only the coefficient in z^(k-1) (when viewed as a polynomial in z). This is given by: z^(k-1) + z^(k-1) X + z^(k-1) X^2 + ... + z^(k-1) X^(P - 1) = z^(k-1) (1 + X + X^2 + ... + X^(P - 1)) = 0. The result follows. QED. -------- As for your integration result, I suspect that indeed works very nicely. Unlike the Chebyshev nodes, the P-Flanelle nodes are distributed roughly uniformly (i.e. one in each of the intervals of width Pd). In fact, why should I merely *suspect* that it works very nicely? It's much more fun to *verify* it. Now, suppose we want to sample 7^3 points in the interval [0, 1] to approximate the integral f(z) = exp(z) + log(z + 1). I get the following results: Actual result: 2.1045761895789358542 Flanelle(7,4): 2.1045761682153800491 Midpoint rule: 2.1045757581112380408 So, Flanelle(7,4) has an error of 2 * 10^-8, whereas the midpoint rule with the same number of samples (7^3) has an error of 4 * 10^-7. That is to say: *** Flanelle integration is 20 times better than midpoint rule ***. Now, let's see what happens with other functions (P = 7, k = 4): Exp[z] + Log[z] + z^3: Flanelle is 34 times better. 1/(z + 1): Flanelle is 27 times better. Zeta[z + 2]: Flanelle is 26 times better. Now let's try P = 5, k = 6, and a few polynomials: z^2: Flanelle is 25 times better. z^3: Flanelle is 25 times better. ... z^8: Flanelle is 25 times better. z^16: Flanelle is 24 times better. z^32: Flanelle is 27 times better. z^40: Flanelle is 44 times better. z^48: Flanelle is 1976 times better. z^56: Flanelle is 34 times better. z^64: Flanelle is 15 times better. z^72: Flanelle is 9 times better. z^80: Flanelle is 6 times better. (versus the midpoint rule with P^(k-1) samples, i.e. the same number as Flanelle is taking.) In conclusion, this is really awesome!!! -------- Sincerely, Adam P. Goucher > Sent: Sunday, July 06, 2014 at 4:04 AM > From: "Warren D Smith" <warren.wds(a)gmail.com> > To: "Adam P. Goucher" <apgoucher(a)gmx.com> > Subject: Numerical integration & summation using Flanelle(P) > > Google found > http://cp4space.wordpress.com/2013/08/14/polynomials-and-hamming-weights/ > > Suppose we want to integrate f(x) dx from x=0 to x=1. > Or, we want to sum f(n) from n=0 to n=2^k-1. > For large k these two problems are essentially the same problem. > > Via Flanelle, we can, as you noted, 2-color the set {0,1,...,2^k-1} > so that the red subset has the same (0,1,2,...,k-1)th moments > as the blue subset. I point out that this moment demand is EXACTLY what > was wanted by Chebyshev in devising methods for numerical integration > with equally weighted nodes, with specified degree of exactness. So if we > only sum on the red summands, we get an approximation of (half) the > full sum, via > half the work, which for any summand-function f(n) which happened to be > a polynomial of degree<=k-1, would be exact. > > What is the proof of Flanelle's Theorem? My answer is:David Wilson's > binary tree , > and noting that the kth difference of any polynomial of degree<=k-1, is zero... > which in turn follows inductively from the fact that the jth > difference is a polynomial of degree max(k-j,0). > QED. > > Great. So now, to generalize this: suppose we do not want to 2-color, > we want to P-color, the summands, so that every color class has the same > {0,1,2,...,k-1}th moments. Here I will let P be any prime. > > Define the function hP(n) to be: sum the digits of the radix-P > expansion of integer n, > modulo P. Let wP be a Pth root of unity. > Can we then claim that for any polynomial f(n) of degree<k, > Sum[ wP^hP(n) * f(n), n=0..P^k-1 ] > is always zero? > > I think the answer is "yes" using a P-ary tree in place of the binary > tree in the proof. > > Call this the "P-Flanelle theorem." > > I think it follows from the P-Flanelle theorem that the obvious P-coloring > works, except there are a few (presumably rare) special values of P > that might not work. I think it works if the Pth roots of unity all > are linearly independent over the integers, aside > from the obvious linear relation that their sum is 0. > > Anyhow, assuming I have not fucked up, this seems very cool, no? In this way > we get very nifty numerical integration and summation rules -- do 1/P > of the work to get a pretty accurate answer. > > This is a bit like "Monte Carlo integration," except nonrandom and satisfying > some nice guarantees, and it is incredibly simple. > > (Maybe you can inform me of how deranged I might be...) > -- > Warren D. Smith > http://RangeVoting.org <-- add your endorsement (by clicking > "endorse" as 1st step) >

2 1

Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle
by Henry Baker 06 Jul '14

06 Jul '14

Isn't this Archimedes's Hatbox Theorem ? BTW, since the Roman Pantheon is a hemisphere of radius r on top of a cylinder of radius r and height r (i.e., if you put a sphere of radius r inside the Pantheon, it would touch the entire hemispherical ceiling and also touch the cylindrical floor, I think that the Pantheon is an ancient ode to A's Hatbox Theorem. At 07:15 PM 7/5/2014, Eugene Salamin via math-fun wrote: >If you allow the use of area elements, yes, there's a proof.Ã Circumscribe a cylinder about the sphere of unit radius tangent at the equator.Ã Project the sphere outward to the cylinder from the axis, i.e. the lines of projection are parallel to the equatorial plane.Ã An area element at latitude ÃÂ» is located distance cosÃÂ» from the axis, so it gets expanded by projection by factor 1/cosÃÂ».Ã But the normal to theÃ element on the sphere is inclined to the line of projection by angle ÃÂ», and so it gets foreshortened by factor cosÃÂ».Ã So projection preserves area, independent of latitude. Ã --Ã Gene >________________________________ > From: Dan Asimov <dasimov(a)earthlink.net> >To: math-fun <math-fun(a)mailman.xmission.com> >Sent: >Subject: Re: [math-fun] Gary Antonick is edging away from the following bonus puzzle > > >Gene, is there a rigorous proof of that using just Eucidean solid geometry, without calculus? > >--Dan > > >----- >That z is uniform in [-1,+1] is a consequence of the solid geometry theorem >that the area of a sphere between two parallel planes depends only on >the separation between the planes, and is independent of what part of >the sphere lies between the planes.

1 0

[math-fun] Binary tree of divisions of natural numbers (was: Problem I never solved)
by Warren D Smith 06 Jul '14

06 Jul '14

Adam P. Goucher: It's equivalent to showing that the limit of the series: Sum[(-1)^h(n) (log(2n + 1) - log(2n + 2))] (where n ranges from 0 to infinity) is -log(2)/2, where h(n) is the Hamming weight of n. Interestingly, there is a similar result on polynomials (known as Flanelle's theorem, and rather easy to prove): Sum[(-1)^h(n) p(n)] (where n ranges from 0 to 2^k - 1) = 0 for any polynomial p(n) of degree at most k-1. Can we use Flanelle's theorem together with Weierstrass approximation to prove anything? --WDS: Fascinating. It seems a bit simpler to phrase it as S(N) = Sum[ (-1)^h(n) * log(3+n), for n=0...N] Well, first of all, this is a DIVERGENT SERIES i.e. most definitely S(N) has no limit as N-->infinity. Although Goucher's version is less divergent, it is not completely clear to me that it converges. Second, we CAN use "Flanelle's theorem" (which also sounds fascinating & I am taking it from APG on trust -- I'd never heard of it) to prove that the limit of S(N) DOES exist if we take N-->infinity ALONG the sequence 1,3,7,15,31,63,... which, by the way, is what is "equivalent" to Wilson's ask. To prove that: use as a lemma, the fact that the function ln(1+x) has a degree-k polynomial approximation which, within the interval 0<x<1, has maximum |error| of order <= 3^(-k). To prove the lemma, use the Taylor series based at x=1.5. (Actually, by using the Chebyshev series, which also is known is closed form, we could prove an exponential multiplication factor smaller than 1/3, but we shall not need to.) Now use Flanelle to see that the subsum from n=2^k to 2^(k+1)-1, is equal to zero, plus an error term. The zero arises from the polynomial approximation of the ln, via Flanelle. The error arises from summing the error in that approximation. This summed error is of order (2/3)^k and hence the sequence of subsums has exponentially dying absolute values, proving convergence. QED. This also allows you (with a bit more trouble) to write explicit error bounds, which would allow you via a finite computation to prove the alleged equality with -ln(2)/2 is FALSE (if it is) or to prove it is "true within +-0.00001" (if it is). ------------------------------Re the revised title of this post: Write the numbers 3 4 5 6 7 ... on a line. Regard them as the leaves of an infinite balanced binary tree. Each node of the tree has value a/b, where a is its left child and b its right child. David Wilson's problem is to prove or disprove that the sequence of values along the leftmost path in this tree, converges (as we walk along path away from the leaf "3") to sqrt(2)/2. With any other operator {*, +, -} in place of "/", understanding this sequence would be trivial. Adam P Goucher's observation was that the sequence of logs of these values is the (k-1)th value of S2(N) = Sum[(-1)^h(n) (log(2n + 1) - log(2n + 2))] summed from n=1 to 2^k. My simpler (?) version of same observation involves S1(N) = Sum[ (-1)^h(n) * log(n+3) ]. We can also go in the other direction, e.g. S4(N) = Sum[(-1)^h(n) (log(4n - 1) - log(4n) - log(4n+1) + log(4n+2))]. This last version has the advantage that this series really is manifestly obviously convergent. And if we go further in this "direction," we would get more-rapidly-convergent formulations S8(N) etc, albeit with more complicated summands.

1 0

[math-fun] A curious theorem
by Eugene Salamin 05 Jul '14

05 Jul '14

If a finite group has odd order h, and k conjugacy classes, then h = k mod 16. Morris Newman, "Matrix Representations of Groups", p. 46. -- Gene

1 0