# Polynomials and partitions

There is a question I have based on the fact: If you take a quadratic polynomial with integer coefficients, and take the set (1,2,3,4,5,6,7,8), and make a partition A=(1,4,6,7), and B=(2,3,5,8), and then evaluate the polynomial with the elements of each set you got an equality.

If now with a cubic polynomial and the set (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16), how to pick a suitable partition that accomplish the same fact. i mean is there a general formula for bigger degree?

-
Ah, you mean that, for any quadratic polynmial, $p(1)+p(4)+p(6)+p(7)=p(2)+p(3)+p(5)+p(8)$. This doesn't require $p$ to have integer coefficients, it just follows from the cases $p(x)=x$ and $p(x)=x^2$. –  Thomas Andrews Jun 26 '12 at 16:39
(Also, I changed your subject, because the question is not about a "symmetric polynomial", which has a very particular meaning.) –  Thomas Andrews Jun 26 '12 at 16:57
Yeah, don´t require integer coefficients. –  Sebastian Griotberg Jun 26 '12 at 17:08
Another way of describing the general formula. First split the integers in the range $[0,2^k-1]$ into two sets, one containing those with an even number of ones in their binary representation, the other containing those with an odd number of ones. Then add $1$ to all the numbers so that they cover the range $[1,2^k]$ instead. –  Jyrki Lahtonen Jun 27 '12 at 6:57

If I understood the question correctly, the following construction will work. We begin with two sets $A_1=\{1,4\}$ and $B_1=\{2,3\}$ (we might equally well similarly partition the set $\{0,1,2,3\}$, but you seem to asking about this set). We observe that $$\sum_{x\in A_1}x=1+4=5=2+3=\sum_{x\in B_1}x.$$ Because both sets have two elements (or, equivalently, $\sum_{x\in A_1}x^0=\sum_{x\in B_1}x^0$) it follows that for any linear polynomial $f$ we also have $$\sum_{x\in A_1}f(x)=\sum_{x\in B_1}f(x).$$ We want a similar result to hold for quadratic polynomials $f$, too. To that end we must use larger sets and define $$A_2=A_1\cup\{4+x\mid x\in B_1\},\qquad B_2=B_1\cup\{4+x\mid x\in A_1\}.$$ We notice that $A_2\cap B_2=\emptyset$ and $A_2\cup B_2=\{1,2,\ldots,8\}.$ We then get the property described in the question: $$\sum_{x\in A_2}x^k=\sum_{x\in B_2}x^k$$ for all $k=0,1,2$. This is more or less immediate for $k=0,1$. When $k=2$ it follows from the calculation \begin{aligned} \sum_{x\in A_2}x^2&=\sum_{x\in A_1}x^2+\sum_{x\in B_1}(4+x)^2\\ &=\sum_{x\in A_1\cup B_1}x^2+\sum_{x\in B_1}(16+8x)\\ &=\sum_{x\in A_1\cup B_1}x^2+16|B_1|+8\sum_{x\in B_1}x, \end{aligned} and the corresponding calculation \begin{aligned} \sum_{x\in B_2}x^2&=\sum_{x\in B_1}x^2+\sum_{x\in A_1}(4+x)^2\\ &=\sum_{x\in A_1\cup B_1}x^2+\sum_{x\in A_1}(16+8x)\\ &=\sum_{x\in A_1\cup B_1}x^2+16|A_1|+8\sum_{x\in A_1}x. \end{aligned} From our earlier results about sums over sets $A_1$ and $B_1$ it follows that these sums are equal. It then follows that the sums of values of any quadratic polynomials over the sets $A_2$ and $B_2$ agree.

You knew all this, so let's move on. We shall recursively defined two sets $A_k$ and $B_k$ such that $A_k\cap B_k=\emptyset$, $A_k\cup B_k=\{1,2,\ldots,2^{k+1}\}$, and that the power sums are equal $$\sum_{x\in A_k}x^j=\sum_{x\in B_k}x^j$$ for all $j=0,1,2,\ldots, k$.

Assume that we have succeeded in doing the above up to som value of $k$. We then define $$A_{k+1}=A_k\cup\{2^{k+1}+x\mid x\in B_k\},\qquad B_{k+1}=B_k\cup\{2^{k+1}+x\mid x\in A_k\}.$$ I claim that this works. Notice that $A_{k+1}$ contains all of $A_k$ and then some new integers in the range $[2^{k+1}+1,2^{k+2}]$. Similarly for $B_{k+1}$. The integers in this new range are equally divided in the two parts, because by the induction hypothesis they were so divided in the previous step. The power sum equality is proven in the same way. We need the binomial formula. It will introduce lower degree power sums, but these were all covered by the induction hypothesis, so we will be fine. Let's roll, and pick an exponent $j$ in the range $0\le j\le {k+1}$. \begin{aligned} \sum_{x\in A_{k+1}}x^j&=\sum_{x\in A_k}x^j+\sum_{x\in B_k}(2^{k+1}+x)^j\\ &=\sum_{x\in A_k}x^j+\sum_{x\in B_k}\left(\sum_{\ell=0}^j{j\choose\ell}2^{(k+1)(j-\ell)}x^\ell\right)\\ &=\sum_{x\in A_k\cup B_k}x^j+\sum_{x\in B_k}\left(\sum_{\ell=0}^{j-1}{j\choose\ell}2^{(k+1)(j-\ell)}x^\ell\right)\\ \end{aligned} Here in the last line $\ell<j=k+1$, so by the induction hypothesis we can replace $B_k$ with $A_k$, and continue \begin{aligned} &=\sum_{x\in A_k\cup B_k}x^j+\sum_{x\in A_k}\left(\sum_{\ell=0}^{j-1}{j\choose\ell}2^{(k+1)(j-\ell)}x^\ell\right)\\ &=\sum_{x\in B_k}x^j+\sum_{x\in A_k}\left(\sum_{\ell=0}^{j}{j\choose\ell}2^{(k+1)(j-\ell)}x^\ell\right)\\ &=\sum_{x\in B_k}x^j+\sum_{x\in A_k}(2^{k+1}+x)^j\\ &=\sum_{x\in B_{k+1}}x^j, \end{aligned} as claimed. The inductive step is thus valid, and claim proven for all $k$.

You were particularly interested in the sets $A_3$ and $B_3$. Here they are $$A_3=\{1,4,6,7,10,11,13,16\},\qquad B_3=\{2,3,5,8,9,12,14,15\}.$$ The set $A_3$ is the union of $A_2$ and all the numbers gotten by adding $8$ to the elements of $B_2$. Similarly $B_3$ contains all the numbers of $B_2$ as well as those gotten by adding $8$ to an element of $A_2$.

In all the steps knowing that the monomial sums all agree up to a certain degree, of course, implies that the sums of values of any polynomial up to that degree then also agree.

-
So, do you mean that for every partition, it require that the addition of the elements of both has to be the same, is that a generalization for polynomials of degree n and sets of cardinality $2^m$, such that $m=n+1$? –  Sebastian Griotberg Jun 26 '12 at 17:11
Yes. The sums of values of cubic polynomials over $A_3$ agree with those over $B_3$, and those two sets partition the range $1$ through $16$. The sets $A_4$ and $B_4$ partition the range $1$ through $32$ and sums of quartic polynomials over the two parts agree, et cetera. The range is doubled in each step, and the degree of the "allowed" polynomials go up by one in each step. –  Jyrki Lahtonen Jun 26 '12 at 17:14