Coefficients of Polynomials Corresponding to Sums of Powers of Natural Numbers Sum to 1.

September 6, 2012

This post has a pretty weird title, but the problem is easy to state and uses a few interesting mathematical concepts.  It’s worth going through.  Let’s start with the basics.

Problem 1.  Let $S_{\alpha}(n) = 1^{\alpha} + 2^{\alpha} + \dots + n^{\alpha}$.  Show that $S_{\alpha}(n)$ is a polynomial for each $\alpha\in {\mathbb N}$ and that the degree of the polynomial is $\alpha + 1$.

Indeed, for example, we have  that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$, as we learned in Calculus, and this is a polynomial of degree 2.  Similarly, $1^{2} + 2^{2} + \dots + n^{2} = \frac{n(n+1)(2n+1)}{6}$, which is a polynomial of degree 3.  In the same respect, $1^{3} + 2^{3} + \dots + n^{3} = \frac{(n(n+1))^{2}}{4}$, which is a polynomial of degree 4.

The associated polynomials in this case are given by Faulhaber’s formula:

Theorem (Faulhaber).  For $\alpha\in {\mathbb N}$ we have $\displaystyle \sum_{k=1}^{n}k^{\alpha} = \frac{1}{1 + \alpha}\sum_{j=0}^{\alpha}(-1)^{j}\binom{\alpha + 1}{j}B_{j}n^{\alpha + 1 - j}$.

This formula looks terrifying, but it is not hard to apply in practice.  You may be wondering, though, what the $B_{j}$‘s in this formula stand for.  These are the strange and wonderful Bernoulli numbers, of course!  I always enjoy seeing these creatures, because they unexpectedly pop up in the strangest problems.  There are a number of ways to define these numbers, one of which is to just write them out sequentially, starting with $B_{0}$:

$1, -\frac{1}{2}, \frac{1}{6}, 0, -\frac{1}{30}, 0, \frac{1}{42}, 0, -\frac{1}{30}, 0, \dots$

But in this case it is not so easy to guess the next value.  The clever reader will notice that all of the odd numbered Bernoulli numbers (except the first) are zero, but other than that there does not seem to be a clear pattern.  Fortunately, we can construct a function which generates the values as coefficients; we’ll call this function (surprise!) a generating function.

Definition.  We define the sequence $\{B_{j}\}_{j=0}^{\infty}$ by

$\displaystyle \frac{t}{e^{t} - 1} = \sum_{j=0}^{\infty}B_{j}\frac{t^j}{j!}$.

Notice that this will, in fact, generate the $B_{j}$ as coefficients times $\frac{1}{j!}$.  Neat.  In practice, you can use a program like Mathematica to compute $B_{j}$ for pretty large values of $j$; but, of course, there are lists available.  We can now use Faulhaber’s formula above, which gives us (assuming we have proven that the formula holds!) that the sums of powers of natural numbers form polynomials of degree $\alpha + 1$.

But something else happens that’s pretty interesting.  Let’s look at some of the functions.

$\begin{array}{|c|c|}\hline \alpha & \mbox{Polynomial}\\\hline &\\ 1 & \frac{1}{2}n^{2} + \frac{1}{2}n\\ &\\ 2 & \frac{1}{3}n^{3} + \frac{1}{2}n^{2} + \frac{1}{6}n\\ & \\ 3 & \frac{1}{4}n^{4} + \frac{1}{2}n^{3} + \frac{1}{4}n^{2} \\ & \\ 4 & \frac{1}{5}n^{5} + \frac{1}{2}n^{4} + \frac{1}{3}n^{3} - \frac{1}{30}n\\ & \\ \hline \end{array}$

Look at the coefficients in each of these polynomials.  Anything strange about them?  Consider them for a bit.

Problem.  Look at the coefficients.  What do you find interesting about them?  Note that, in particular, for a fixed $\alpha$, the coefficients of the associated polynomial sum to 1.  Convince yourself that this is probably true (do some examples!) and then prove that it is true.  Do this before reading the statements below.

Anecdote.  I spent quite a while trying to write down the "general form" of a polynomial with elementary symmetric polynomials and roots to try to see if I could prove this fact using some complex analysis and a lot of terms canceling out.  This morning, I went into the office of the professor to ask him about what it means that these coefficients sum up to 1.  He then gave me a one-line (maybe a half-line) proof of why this is the case.

Hint.  What value would we plug in to a polynomial to find the sum of the coefficients?  What does plugging in this value mean in terms of the sum?

Pointwise Convergent Sequence of Polynomials.

August 7, 2012

An interesting question came up during my studying today which made me think about some of the different ways we can think about polynomials.  The solution to this problem was not immediately obvious to me, and, in fact, it wasn’t until I looked up a completely unrelated problem (in a numerical methods book!) that some solution became clear.

Question:  Suppose that $\{f_{n}\}$ is a sequence of polynomials with $f_{n}:{\mathbb R}\to {\mathbb R}$ each of degree $m > 1$ and suppose $f_{n}\to f$ pointwise.  Show that $f$ is also a polynomial of degree no more than $m$

Some interesting points come up here.  First is that we only have pointwise convergence — it wasn’t even immediately obvious to me how to prove the resulting limit was continuous, let alone a polynomial of some degree.  Second, we know very little about the polynomials except for what degree they are.  This should be an indication that we need to characterize them with respect to something degree-related.

Indeed, polynomials can be represented in a few nice ways.  Among these are:

• In the form $f(x) = a_{0} + a_{1}x + \cdots + a_{n}x^{n}$ where it is usually stated that $a_{n}\neq 0$.
• In terms of their coefficients.  That is, if we have a list of polynomials of degree 3 to store on a computer, we could create an array where the first column is the constant, the second is the linear term, and so forth.  This is sort of like decimal expansion.
• Where they send each point.  That is, if we know what $f(x)$ is equal to for each $x$, we could recover it.
• If a polynomial is of degree $m$ then, somewhat surprisingly, we can improve upon the previous statement: if we know the value of $f$ for $m + 1$ distinct points, then we can find $f$, and $f$ is the unique such polynomial of that degree which has those values.  (Note that if we were to have $m+1$ points and a polynomial of degree $k > m$, then many polynomials of this degree could fit the points.  Consider, for example, $m = 0$ and $k = 1$.  Then we have one points and we want to fit line through it.  Clearly this can be done in infinitely many ways.)

This last one is going to be useful for us.  So much so that it might be a good idea to prove it.

Lemma.  Let $x_{1}, \dots, x_{m+1}$ be $m + 1$ distinct points in ${\mathbb R}$, and let $y_{1}, \dots, y_{m+1}$ be distinct points in ${\mathbb R}$.  Then there is a unique polynomial of degree at most $m$ such that $f(x_{i}) = y_{i}$ for each $i$ considered here.

Proof.  This is an exercise in linear algebra.  We need to solve the system of linear equations

$\displaystyle \sum_{n = 1}^{m} a_{n}x_{i}^{n} = y_{i}$

where $i$ spans $1, \dots, m+1$, for the constants $a_{n}\in {\mathbb R}$.  Notice that this is simply plugging $x_{i}$ into a general polynomial of degree $m$.  Notice that the matrix that this forms will be a Vandermonde matrix.  Since each $x_{i}$ is distinct, the determinant of this matrix is nonzero, which implies that there is a unique solution.  This gives us our coefficients, and note that this is a polynomial not necessarily of degree exactly $m$, since some coefficients may be 0, but it is at most $m$$\diamond$

[Note: For those of you who forgot your linear algebra, the end of this goes like this: if we let our coefficients be denoted by the column matrix $b$ and our Vandermonde matrix is denoted by $A$, then we want to solve $Ab = Y$ where $Y$ is the column vector with entries $y_{i}$.  If $A$ has non-zero determinant, then it is invertible, and so we have that $b = A^{-1}y$ gives us our coefficients.]

Neato.  But now we need to specialize this somewhat for our proof.

Corollary.  Let the notation and assumptions be as in the last lemma.  For $I\in \{1, \dots, m+1\}$, let $g_{i}$ be the unique polynomial of degree at most $m$ with $g_{i}(x_{j}) = \delta_{i,j}$ (where $\delta_{i,j} = 0$ if $i\neq j$ and $\delta_{i,i} = 1$).  Then every polynomial $f$ of degree at most $m$ is of the form $\displaystyle f(x) = \sum_{i = 1}^{m+1}f(x_{i})g_{i}(x)$ for each $x\in {\mathbb R}$.

This might be a bit more cryptic, so let’s do an example.  Let’s let $m = 1$ so that we have two points.  Let’s say $x_{1} = 0$ and $x_{2} = 1$.  Then we have $g_{1}$ is the unique polynomial of degree at most 1 such that $g_{1}(0) = 1$ and $g_{2}(1) = 0$.  Of course, this function will be $g_{1}(x) = -x + 1$.  Now $g_{2}(0) = 0$ and $g_{2}(1) = 1$; this gives us that $g_{2}(x) = x$.  The theorem now states that any polynomial of degree at most $1$ can be written in the form

$f(x) = f(0)g_{1}(x) + f(1)g_{2}(x)$

$= f(0)(-x+1)+ f(1)x = (f(1) - f(0))x + f(0)$.

For example, let $f(x) = 2x + 1$.  Then the lemma says $f(x) = (3(1) - 1)x + 1 = 2x + 1$, as we’d expect.  The power of this lemma will become clear when we use this in the solution.  The proof of this corollary is just a specialization of the previous lemma, so we exclude it.

Solution.  Recall, just for notation, that our sequence $\{f_{k}\}\to f$ pointwise.  Let’s let $x_{1}, \dots, x_{m+1}$ be our distinct points, as usual.  In addition, let’s let $g_{1}, \dots, g_{m+1}$ be defined as in the corollary above. Represent each $f_{k}$ as follows:

$\displaystyle f_{k}(x) = \sum_{j = 1}^{m+1}f_{k}(x_{j})g_{j}(x)$

for each $x\in {\mathbb R}$.  Here comes the magic: let $k\to\infty$ and note that $f_{n} \to f$ at every point, so, in particular, on each $x_{i}$ and on $x$.  We obtain

$\displaystyle f(x) = \sum_{j = 1}^{m+1}f(x_{j})g_{j}(x)$

for each $x\in {\mathbb R}$.  But this is the sum of polynomials of degrees at most $m$, which gives us that $f$ is itself a polynomial of degree at most $m$$\Box$

I’ll admit, I did a bit of digging around after finding the lemma above; in particular, this corollary representation of polynomials seems to be a nice way to represent a polynomial if we do not know the coefficients but do know the values at a certain number of points and have that its degree is bounded below that number of points.

Exercise: Try to write out this representation for $m = 2$ and $m = 3$.  If you’re a programmer, why not make a program that allows you to input some points and some values and spits out the polynomial from the corollary above?

A Very Basic Introduction to the Sylow Theorems.

May 18, 2012

[Note: It’s been a while!  I’ve now completed most of my pre-research stuff for my degree, so now I can relax a bit and write up some topics.  This post will be relatively short just to “get back in the swing of things.”]

In Group Theory, the big question used to be, “Given such-and-such is a group, how can we tell which group it is?”

The Sylow Theorems (proved by Ludwig Sylow, above) provide a really nice way to do this for finite groups using prime decomposition.  In most cases, the process is quite easy.  We’ll state the theorems here in a slightly shortened form, but you can read about them here.  Note that subgroup which is of order $p^{\beta}$ for some $\beta$ is unsurprisingly called a $p$-subgroup. A $p$-subgroup of maximal order in $G$ is called a Sylow $p$-subgroup.

Theorem (Sylow).  Let $G$ be a group such that $|G| = p^{\alpha}m$ for $p\not| m$.  Then,

1. There exists at least one subgroup of order $p^{\alpha}$.
2. The Sylow $p$-subgroups are conjugate to one-another; that is, if $P,Q$ are Sylow $p$-subgroups, then there is some $g\in G$ such that $gPg^{-1} = Q$.  Moreover, for all $g\in G$, we have that $gPg^{-1}$ is a Sylow $p$-subgroup.
3. The number of Sylow $p$-subgroups of $G$, denoted by $n_{p}$, is of the form $n_{p} \equiv 1\mbox{ mod } p$.  In other words, $n_{p}$ divides $m$.

This first part says that the group of Sylow $p$-subgroups of $G$ is not empty if $p$ divides the order of $G$.  Note that this is slightly abbreviated (the second part is actually more general, and the third part has a few extra parts) but this will give us enough to work with.

Problem: Given a group  $|G| = pq$ for $p,q$ prime and $p < q$, is $G$ ever simple (does it have any nontrivial normal subgroups)?  Can we say explicitly what $G$ is?

We use the third part of the Sylow theorems above.  We note that $n_{q} | p$ and $n_{q} \equiv 1\mbox{ mod } q$, but $p < q$ so this immediately implies that $n_{q} = 1$ (why?).  So we have one Sylow $q$-subgroup; let’s call it $Q$.  Once we have this, we can use the second part of the Sylow theorem: since for each $g\in G$ we have $gQg^{-1}$ is a Sylow $q$-subgroup, but we’ve shown that $Q$ is the only one there is!  That means that $gQg^{-1} = Q$; this says $Q$ is normal in $G$.  We have, then, that $G$ isn’t simple.  Bummer.

On the other hand, we can actually say what this group is.  So let’s try that.  We know the Sylow $Q$-subgroup, but we don’t know anything about the Sylow $P$-subgroups.  We know that $n_{p} \equiv 1\mbox{ mod }p$ and $n_{p} | q$, but that’s about it.  There are two possibilities: either $n_{p} = 1$ or $n_{p} = q$.

For the first case, by using the modular relation, if $p$ does not divide $q-1$ then this forces $n_{p} = 1$; this gives us a unique normal Sylow $p$-subgroup $P$.  Note that since the orders of our normal subgroups multiply up to the order of the group, we have $PQ \cong P\times Q \cong G$; in other words, $G \cong {\mathbb Z}_{p}\times {\mathbb Z}_{q}$.

For the second case, $n_{p} = q$.  We will have a total of $q$ subgroups of order $p$ and none of these are normal.   This part is a bit more involved (for example, see this post on it), but the punch line is that it will be the cyclic group ${\mathbb Z}_{pq}$.

I’ll admit that the last part is a bit hand-wavy, but this should at least show you the relative power of the Sylow theorems.  They also come in handy when trying to show something either does or does not have a normal subgroup.  Recall that a simple group has no nontrivial normal subgroups.

Question.  Is there any simple group with $|G| = 165$?

I just picked this number randomly, but it works pretty well for this example.  We note that $|G| = 165 = 3\cdot 5\cdot 11$.  Let’s consider, for kicks, $n_{11}$.  We know $n_{11}$ must divide $3\cdot 5 = 15$ and it must be the case that $n_{11} \equiv 1\mbox{ mod } 11$; putting these two facts together, we get $n_{11} = 1$.  This immediately gives us a normal subgroup of order 11, which implies there are no simple groups of order 165.

Question.  Is there any simple group with $|G| = 777$?

Alas, alack, you may say that 777 is too big of a number to do, but you’d be dead wrong.  Of course, $777 = 3\cdot 7\cdot 37$.  Use the same argument as above to show there are no simple groups of this order.

Question.  Is there any simple group with $|G| = 28$?

Note that $28 = 2^{2}\cdot 7$ so we need to do a little work, but not much.  Just for fun, let’s look at $n_{7}$.  We must have that it is 1 modulo 7 and it must divide $2^{2} = 4$.  Hm.  A bit of thinking will give you that $n_{7} = 1$, which gives us the same conclusion as above.

Of course, there are examples where this doesn’t work nicely.  Think about the group of order 56, for example.  In order to work with these kinds of groups, one must do a bit more digging.  We will look into more of this later.

Uncountable Subset A of [0,1] with A – A empty.

December 20, 2011

I’m going through a few books so that I can start doing lots and lots of problems to prepare for my quals.  I’ll be posting some of the “cuter” problems.

Here’s one that, on the surface, looks strange.  But ultimately, the solution is straightforward.

Problem.  Find an uncountable subset $A\subseteq [0,1]$ such that $A - A = \{a - b\,\mid\,\,a,b\in A\}$ has empty interior.