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@gmail.com> To: "Adam P. Goucher" <apgoucher@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)