\documentclass{beamer}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{matrix,arrows,backgrounds,shapes.misc,shapes.geometric,fit}
\usepackage{etex}
\usepackage{amsthm}
\usepackage{color}
\usepackage[all]{xy}
\usepackage{textpos}
\usetikzlibrary{calc,through,backgrounds}
%\CompileMatrices

\definecolor{grau}{rgb}{.5 , .5 , .5}
\definecolor{dunkelgrau}{rgb}{.35 , .35 , .35}
\definecolor{schwarz}{rgb}{0 , 0 , 0}
\definecolor{violet}{RGB}{143,0,255}
\definecolor{forestgreen}{RGB}{34, 100, 34}

\newcommand{\red}{\color{red}}
\newcommand{\grey}{\color{grau}}
\newcommand{\green}{\color{forestgreen}}
\newcommand{\violet}{\color{violet}}
\newcommand{\blue}{\color{blue}}

\newcommand{\bIf}{\textbf{If} }
\newcommand{\bif}{\textbf{if} }
\newcommand{\bthen}{\textbf{then} }

\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\QQ}{{\mathbb Q}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\CC}{{\mathbb C}}
\newcommand{\PP}{{\mathbf P}}
\newcommand{\OO}{\operatorname {O}}
\newcommand{\id}{\operatorname {id}}
\newcommand{\Sym}{\operatorname {Sym}}
\newcommand{\Nm}{\operatorname {N}}
\newcommand{\Stab}{\operatorname {Stab}}
\newcommand{\Orb}{{\mathcal O}}
\newcommand{\GL}{\operatorname {GL}}
\newcommand{\SL}{\operatorname {SL}}
\newcommand{\Or}{\operatorname {O}}
\newcommand{\im}{\operatorname {Im}}
\newcommand{\Iso}{\operatorname {Iso}}
\newcommand{\rad}{\operatorname {rad}}
\newcommand{\zero}{\mathbf{0}}



\usepackage{url}%this line and the next are related to hyperlinks
%\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blur]{hyperref}

\usepackage{color}

%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

\usefonttheme[onlylarge]{structurebold}
\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
\setbeamertemplate{navigation symbols}{}
%\setbeamertemplate{section in head/foot shaded}[default][60]
%\setbeamertemplate{subsection in head/foot shaded}[default][60]
\beamersetuncovermixins{\opaqueness<1>{0}}{\opaqueness<2->{15}}

%\usepackage{beamerthemesplit}
\usepackage{epsfig,amsfonts,bbm,mathrsfs}
\usepackage{verbatim} 



\newcommand{\STRUT}{\vrule width 0pt depth 8pt height 0pt}
\newcommand{\ASTRUT}{\vrule width 0pt depth 0pt height 11pt}


\theoremstyle{plain}
\newtheorem{conj}[theorem]{Conjecture}


\setbeamertemplate{headline}{}
%This removes a black stripe from the top of the slides.


\author{Darij Grinberg}
\title[Integral-valued polynomials]{Integral-valued polynomials}

\date{14 October 2013, Storrs \\ {\red \url{http://www.cip.ifi.lmu.de/~grinberg/storrs2013.pdf}}}


\begin{document}

\frame{\titlepage}

\begin{frame}
\frametitle{\ \ \ \ What is an integral-valued polynomial?}


This talk is about polynomials: $2x^4 + 5x, \ 3x^7 - \sqrt{2}x + 17, \dots$.

\vspace{.2cm}

Call a polynomial $P(x)$ {\bf integral-valued} if $P(n) \in \ZZ$ for all $n \in \ZZ$.  

\vspace{.2cm}


{\bf Example}: If every coefficient of $P(x)$ is an integer, then $P(x)$ is integral-valued, {\it e.g.}, $P(x) = 2x^4 + 5x$.

\vspace{.2cm}


\pause

The converse is {\it false}: $P(x)$ can be integral-valued without having integral coefficients! 

\vspace{.2cm}


{\bf Example}: $\displaystyle P(x) = \frac{1}{2}x^2- \frac{1}{2}x = \frac{x(x-1)}{2}$.  For $n \in \ZZ$, $n$ or $n-1$ is even, so $\displaystyle \frac{n(n-1)}{2} \in \ZZ$.

\vspace{.2cm}

\pause

Integral-valued polynomials occur in several areas of math, such as combinatorics, commutative algebra, and 
algebraic topology.

\vspace{.2cm}

Our goal: find a nice description of all integral-valued polynomials.



\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Background: polynomials and their values}

A polynomial is determined by ``sufficiently many" of its values.

\begin{itemize}

\item \bIf $P(x)$ and $Q(x)$ are polynomials such that $P(x) = Q(x)$ for infinitely many numbers $x$, \bthen $P(x) = Q(x)$ for {\bf all} $x$.  

\textit{For instance}, a polynomial is completely determined by knowing its values at all $x > 0$.

\item \bIf $P(x)$ and $Q(x)$ are polynomials of degree $d$ such that $P(x) = Q(x)$ for $d + 1$ choices of $x$, \bthen $P(x) = Q(x)$ for {\bf all} $x$.  

\textit{For instance}, a quadratic polynomial is completely determined by knowing its values at (any) three choices of $x$.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Background: polynomials and their values}

A polynomial is determined by ``sufficiently many" of its values.

\begin{itemize}

\item \bIf $P(x)$ and $Q(x)$ are polynomials of degree $d$ such that $P(x) = Q(x)$ for $d + 1$ choices of $x$, \bthen $P(x) = Q(x)$ for {\bf all} $x$.  


\end{itemize}

{\bf Example}.  To verify the identity $x^3 - 1 = (x-1)(x^2 + x + 1)$ for all $x$, it is enough to check both sides are equal at 4 numbers:  both sides are polynomials of degree 3, so if they agree at 4 numbers then they agree everywhere.  At $x = 0, 1, 2, 3$, both sides take the same values ($-1, 0, 7$, and 26).

\hfill

This method can be used in other cases to prove polynomial identities combinatorially: when $x$ is an integer, the two sides of the identity could count the same thing in two different ways.  And equality at enough integers forces equality everywhere. 


\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Background: polynomials and their values}

A polynomial is determined by ``sufficiently many" of its values.

\begin{itemize}

\item \bIf a polynomial $P(x)$ satisfies $P(r) \in \mathbb Q$ for all $r \in \mathbb Q$, \bthen all coefficients of $P(x)$ lie in $\mathbb Q$.

\pause

\item \bIf a polynomial $P(x)$ satisfies $P(n) \in \mathbb Z$ for all $n \in \mathbb Z$, \bthen the coefficients \textbf{need not} all lie 
in $\ZZ$. 

\begin{enumerate}
\item
$\displaystyle {\color{blue}P(x) = \frac{x^2-x}{2}} \left(\text{since } \frac{n(n-1)}{2} \in \ZZ \text{ for all } n \in \ZZ\right)$.

\vspace{.1cm}

\item
$\displaystyle {\color{blue}P(x) = \frac{x^2+x}{2}} \left(\text{since } \frac{n(n+1)}{2} \in \ZZ \text{ for all } n \in \ZZ\right)$.

\vspace{.1cm}

\item 
{\bf not} $\displaystyle P(x) = \frac{x^4-x}{4} \left(\text{since } \displaystyle P(2) = \frac{7}{2}\right)$. 
\end{enumerate}

\end{itemize}




\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Integral-valued polynomials}

Call a polynomial $P(x)$ \textbf{integral-valued} if $P(n) \in \mathbb Z$ for all $n \in \mathbb Z$.
\mbox{} \\
\pause
\mbox{} \\

{\bf Examples}.

\begin{itemize}

\item A polynomial with integer coefficients, of course. :)

\pause

\item ${\blue P(x) = \dfrac{1}{p}(x^p-x)}$ for all primes $p$. (Fermat's little theorem.)

\pause

\item ${\blue P(x) = \dfrac16 x (x+1) (2x+1)}$, because\\
\pause $P(n) = 1^2 + 2^2 + \cdots + n^2 \in \ZZ$ \pause for $n \geq 0$,\\
$P(n) = -(1^2 + 2^2 + \cdots + (n'-1)^2) \in \ZZ$ for $n = -n' < 0$.

\end{itemize}

\end{frame}



\begin{frame}
\frametitle{\ \ \ \ Integral-valued polynomials}

Call a polynomial $P(x)$ \textbf{integral-valued} if $P(n) \in \mathbb Z$ for all $n \in \mathbb Z$.
\mbox{} \\

\mbox{} \\

{\bf Further example}.
$$
{\blue P(x) = \dbinom{x}{m} := \dfrac{x(x-1)\cdots (x-m+1)}{m!}}
$$
for integers $m \geq 0$. The first few of these polynomials are 
$$
\binom{x}{0} = 1, \  \binom{x}{1} = x, \ \binom{x}{2} = \frac{x(x-1)}{2}, \  \binom{x}{3} = \frac{x(x-1)(x-2)}{6}.
$$
\pause

Indeed, for $n \geq 0$, the number $\dbinom{n}{m}$ {\bf counts} the number of $m$-element subsets of $\left\{1,2,\dots,n\right\}$ (``sampling balls from urns").

\pause 

For $n = -N < 0$, we have $\dbinom{n}{m}  = \left(-1\right)^m \dbinom{N+m-1}{m} \in \ZZ$.



\end{frame}


\begin{frame}
\frametitle{\ \ \ \ Integral-valued polynomials}

Call a polynomial $P(x)$ \textbf{integral-valued} if $P(n) \in \mathbb Z$ for all $n \in \mathbb Z$.
\mbox{} \\

\mbox{} \\

{\bf Further example}.


$$
{\blue P(x) = \dfrac{1}{m} \sum\limits_{d\mid m} \phi\left(\dfrac{m}{d}\right) x^d}
$$
for integers $m \geq 1$, 
where $\phi(k)$ is the number of integers among $1,2,\dots,k$ that are relatively prime to $k$.  The first few are 
$$
x, \ \ \frac{1}{2}(x^2+x), \ \ \frac{1}{3}(x^3+2x), \ \ \frac{1}{4}(x^4+x^2+2x).
$$
\pause

For $n \geq 1$, $\displaystyle \dfrac{1}{m} \sum\limits_{d\mid m} \phi\left(\dfrac{m}{d}\right) n^d$ {\bf counts} the number of necklaces with $m$ beads of colors $1,2,\dots,n$ up to a cyclic rotation (MacMahon 1892).  It is {\bf not} clear why it's in $\ZZ$ for $n < 0$. Will see why later! 


\end{frame}



\begin{frame}
\frametitle{\ \ \ \ Integral-valued polynomials}

Call a polynomial $P(x)$ \textbf{integral-valued} if $P(n) \in \mathbb Z$ for all $n \in \mathbb Z$.
\mbox{} \\

\mbox{} \\

{\bf Further examples}.  If $P(x)$ is an integral-valued polynomial, so are 

\begin{itemize}

\item $P(-x)$, 

\item $P(x+b)$ for $b \in \ZZ$, 

\item 
$P(Q(x))$ for any other integral-valued polynomial $Q(x)$, 

\pause

\item 
$aP(x) + bQ(x) + cR(x)$, where $Q(x)$ and $R(x)$ are integral-valued polynomials and $a, b, c \in \ZZ$. 

\end{itemize}

\pause

What kind of nice description could there be of {\bf all} such polynomials?

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials}

\begin{theorem}[Polya, 1915]
Let $N\in\mathbb N$. The integral-valued polynomials of degree $\leq N$ are exactly the polynomials that can be written as 
$${\blue a_0 \dbinom{x}{0} + a_1 \dbinom{x}{1} + \cdots+ a_N \dbinom{x}{N}}$$ for some integers $a_0,a_1,\dots,a_N$. 
Moreover, an integral-valued polynomial can be written in this form in exactly one way. 
\end{theorem}

\vspace{.2cm}

We will explain where this formula for integral-valued polynomials comes from (not its uniqueness) using the method of finite differences, which is a discrete analogue of derivatives.

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials: Examples}

Recall that 
$$
{\color{blue}\binom{x}{0} = 1, \  \binom{x}{1} = x, \ \binom{x}{2} = \frac{x(x-1)}{2}, \  \binom{x}{3} = \frac{x(x-1)(x-2)}{6}}.
$$

\vspace{.2cm}

In terms of these, integral-valued polynomials seen earlier are 
\begin{eqnarray*}
\frac{1}{2}(x^2+x) & = & \dbinom{x}{2} + \dbinom{x}{1}, \\
\frac{1}{6}x(x+1)(2x+1) & = & 2\dbinom{x}{3} + 3\dbinom{x}{2} + \dbinom{x}{1}, \\
\frac{1}{3}(x^3+2x) &  = &  2\dbinom{x}{3} + 2\dbinom{x}{2} + \dbinom{x}{1},  \\
\frac{1}{4}(x^4+x^2+2x) & =  & 6\dbinom{x}{4} + 9\dbinom{x}{3} + 4\dbinom{x}{2} + \dbinom{x}{1}.
\end{eqnarray*}


\end{frame}



\begin{frame}
\frametitle{\ \ \ \ [Motivation for proof] Finite differences of $x^2$}

Start with a polynomial $P$.

\begin{itemize}

\item Write the values $P(0), P(1), P(2), \ldots$ in a line.

\item Write the successive differences $P(1) - P(0), P(2) - P(1), \ldots$ on the next line.

\item Write the successive differences of these successive differences on the next line.

\item Etc.

\end{itemize}

Here is $P(x) = x^2$.

$$
\begin{array}{ccccccccccccc}
0 & &1 & & 4 & & 9 & & 16& & 25 & & 36 \\
 & 1 & & 3 & & 5 & & 7  & & 9& & 11 & \\
  & & 2 & & 2 & & 2 & & 2 & & 2 & & \\
& & & 0 & & 0 & & 0 & & 0 & & \\
& & &  & &  & &  & &  & &
\end{array}
$$

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ [Motivation for proof] Finite differences of $3x^2-x+7$}

Start with a polynomial $P$. 

\begin{itemize}

\item Write the values $P(0), P(1), P(2), \ldots$ in a line.

\item Write the successive differences $P(1) - P(0), P(2) - P(1), \ldots$ on the next line.

\item Write the successive differences of these successive differences on the next line.

\item Etc.

\end{itemize}

Here is $P(x) = 3x^2-x+7$.

$$
\begin{array}{ccccccccccccc}
7 & & 9 & & 17 & & 31 & & 51& & 77 & & 109 \\
 & 2 & & 8 & & 14 & & 20  & & 26& & 32 & \\
 & & 6  & & 6 & & 6 & & 6 & & 6 & & \\
& & & 0 & & 0 & & 0 & & 0 & & \\
& & &  & &  & & & &  & &
\end{array}
$$

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ [Motivation for proof] Finite differences of $x^3$}

Start with a polynomial $P$. 

\begin{itemize}

\item Write the values $P(0), P(1), P(2), \ldots$ in a line.

\item Write the successive differences $P(1) - P(0), P(2) - P(1), \ldots$ on the next line.

\item Write the successive differences of these successive differences on the next line.

\item Etc.

\end{itemize}

Here is $P(x) = x^3$.

$$
\begin{array}{ccccccccccccc}
0 & &1 & & 8 & & 27 & &64 & & 125 & & 216 \\
 & 1 & & 7 & & 19& & 37 & & 61& & 91 & \\
 & & 6 & & 12& & 18 & & 24 & & 30 & & \\
 & & &  6 & & 6 & & 6 & & 6 & & & \\
 & & & & 0 & & 0 & & 0
\end{array}
$$

\end{frame}


\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials: proof}

Why does it always boil down to zeroes? \pause \mbox{}\\
\mbox{} \\
\textbf{Main lemma:} {\it If $P(x)$ is a polynomial of degree $N \geq 1$ then $P(x+1) - P(x)$ is a polynomial of degree $N-1$}.\\


\pause
\mbox{}\\

\textit{Special case:} $P(x) = x^N$. 

To show $(x+1)^N - x^N$ is a polynomial of degree $N-1$, the binomial theorem says
$$
(x+1)^N = x^N + \dbinom{N}{1} x^{N-1} + \dbinom{N}{2} x^{N-2} + \cdots  + 1.
$$
Subtracting the $x^N$ term leaves only terms of degree $\leq N-1$ on the right hand side,
and the term $\dbinom{N}{1}x^{N-1} = Nx^{N-1}$ has degree $N-1$.

%\mbox{}\\
%(Alternatively: use geometric series.)

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials: proof}

Why does it always boil down to zeroes? \mbox{}\\
\mbox{} \\
\textbf{Main lemma:} {\it If $P(x)$ is a polynomial of degree $N \geq 1$ then $P(x+1) - P(x)$ is a polynomial of degree $N-1$}.\\
\mbox{}\\  \pause

\textit{General case:} Set $P(x) = {\red a_0} + {\blue a_1 x^1} + \cdots+ {\green a_N x^N}$, $a_N \not= 0$. Then
\begin{align*}
&P(x+1) - P(x) \\
&= ({\red a_0} + {\blue a_1 (x+1)^1} + \cdots + {\green a_N (x+1)^N}) \\
&- ({\red a_0} + {\blue a_1 x^1} + \cdots + {\green a_N x^N}) \\
&= {\red a_0 \underbrace{(1- 1)}_{\substack{\text{vanishes} \\ \text{}}}} + {\blue a_1\underbrace{((x+1)^1 - x^1)}_{\substack{\text{degree }0 \\ \text{(by special case)}}}} + \cdots + {\green a_N \underbrace{((x+1)^N - x^N)}_{\substack{\text{degree }N-1 \\ \text{(by special case)}}}}.
\end{align*}

Since $a_N \not= 0$, $P(x+1) - P(x)$ has degree $N-1$.  After enough successive differences the polynomial becomes constant, and at the next step all successive differences are 0.

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials: proof}

We are now ready to prove the theorem (minus the ``exactly one way'' claim) by induction on $N$. 

For polynomials of degree $\leq 0$, $P(x) = a_0 = a_0\dbinom{x}{0}$, where $a_0 = P(0) \in \ZZ$.  So we can take $N \geq 1$.\\
\mbox{} \\
Let $P(x)$ be an integral-valued polynomial of degree $\leq N$. \\ % and not constant. \\
\mbox{} \\
By main lemma, $P(x+1) - P(x)$ is a polynomial of degree $\leq N-1$, and is integral-valued of course. Hence by induction hypothesis,
$$
P(x+1) - P(x) = {\red b_0 \dbinom{x}{0}} + {\blue b_1 \dbinom{x}{1}} + \cdots + {\green b_{N-1} \dbinom{x}{N-1}}
$$
for some integers ${\red b_0}, {\blue b_1} ,\dots, {\green b_{N-1}}$. \pause \\
\mbox{}\\

Using $P(x) - P(0)$ in place of $P(x)$, 
WLOG $P(0) = 0$ (subtracting constant term can't hurt).

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials: proof}

Using a telescoping sum, for every $n\geq 1$ we have
$$
\sum_{k=0}^{n-1} (P(k+1) - P(k)) = P(n) - \underbrace{P(0)}_{=0} = P(n).
$$
\pause
Since 
$$
P(x+1) - P(x) = {\red b_0 \dbinom{x}{0}} + {\blue b_1 \dbinom{x}{1}} + \cdots + {\green b_{N-1} \dbinom{x}{N-1}}
$$
we set $x = k$ and get 
$$
P(k+1) - P(k) = {\red b_0 \dbinom{k}{0}} + {\blue b_1 \dbinom{k}{1}} + \cdots + {\green b_{N-1} \dbinom{k}{N-1}}.
$$
Substituting this above,
\pause
$$
\sum_{k=0}^{n-1} \left({\red b_0 \dbinom{k}{0}} + {\blue b_1 \dbinom{k}{1}} + \cdots + {\green b_{N-1} \dbinom{k}{N-1}}\right) = P(n).
$$

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials: proof}

So for $n \geq 1$ 
\begin{align*}
P(n) &= \sum_{k=0}^{n-1} \left({\red b_0 \dbinom{k}{0}} + {\blue b_1 \dbinom{k}{1}} + \cdots + {\green b_{N-1} \dbinom{k}{N-1}}\right) \\
&= {\red b_0 \sum_{k=0}^{n-1} \dbinom{k}{0}} + {\blue b_1 \sum_{k=0}^{n-1} \dbinom{k}{1}} + \cdots + {\green b_{N-1} \sum_{k=0}^{n-1} \dbinom{k}{N-1}}.\\
&\phantom{= {\red b_0 \dbinom{n}{1}} + {\blue b_1 \dbinom{n}{2}} + \cdots + {\green b_{N-1} \dbinom{n}{N}},}
\end{align*}
%
%\pause \mbox{} \\
%
%\mbox{} \\
%
%\mbox{} \\

But the hockey-stick identity says for every $j \geq 0$ that 
\begin{align*}
\sum_{k=0}^{n-1} \dbinom{k}{j} = \dbinom{n}{j+1}
\end{align*}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials: proof}

So for $n \geq 1$
\begin{align*}
P(n) &= \sum_{k=0}^{n-1} \left({\red b_0 \dbinom{k}{0}} + {\blue b_1 \dbinom{k}{1}} + \cdots + {\green b_{N-1} \dbinom{k}{N-1}}\right) \\
&= {\red b_0 \sum_{k=0}^{n-1} \dbinom{k}{0}} + {\blue b_1 \sum_{k=0}^{n-1} \dbinom{k}{1}} + \cdots + {\green b_{N-1} \sum_{k=0}^{n-1} \dbinom{k}{N-1}} \\
&= {\red b_0 \dbinom{n}{1}} + {\blue b_1 \dbinom{n}{2}} + \cdots + {\green b_{N-1} \dbinom{n}{N}},
\end{align*}

since the hockey-stick identity says for all $j \geq 0$ that 
\begin{align*}
\sum_{k=0}^{n-1} \dbinom{k}{j} = \dbinom{n}{j+1}.
\end{align*}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Classification of integral-valued polynomials: proof}

So
\begin{align*}
P(n) = {\red b_0 \dbinom{n}{1}} + {\blue b_1 \dbinom{n}{2}} + \cdots + {\green b_{N-1} \dbinom{n}{N}}
\end{align*}
for all $n \geq 1$.  \pause Setting 
$$
Q(x) = {\red b_0 \dbinom{x}{1}} + {\blue b_1 \dbinom{x}{2}} + \cdots + {\green b_{N-1} \dbinom{x}{N}}, 
$$
the polynomials $P(x)$ and $Q(x)$ have $P(n) = Q(n)$ for all $n \geq 1$. 
Since a polynomial is determined by its values at infinitely many numbers, $P(x) = Q(x)$ for all $x$, so 
\begin{align*}
P(x) = {\red b_0 \dbinom{x}{1}} + {\blue b_1 \dbinom{x}{2}} + \cdots + {\green b_{N-1} \dbinom{x}{N}}.
\end{align*}
\pause
\qed

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Summary}

We have now proven the existence part of 

\begin{theorem}
Let $N\in\mathbb N$. The integral-valued polynomials of degree $\leq N$ are exactly the polynomials that can be written as 
$${\blue a_0 \dbinom{x}{0} + a_1 \dbinom{x}{1} + \cdots+ a_N \dbinom{x}{N}}$$ for some integers $a_0,a_1,\dots,a_N$. 
Moreover, an integral-valued polynomial can be written in this form in exactly one way. 
\end{theorem}

\pause 

A polynomial of degree $\leq N$ is determined by its values at $0$, $1$, $\dots, N$, and our proof only needed such values, so 
we proved  

\begin{corollary}
If a polynomial $P(x)$ of degree $\leq N$ satisfies $P(n) \in \ZZ$ for $n = 0, 1, \dots, N$ then $P(n) \in \ZZ$ for all $n \in \ZZ$.
\end{corollary}

Therefore if $P(n) \in \ZZ$ for $n \geq 0$, $P(n) \in \ZZ$ for all $n \in \ZZ$.


\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Coefficients}

If $P(x)$ is integral-valued, how can we find $a_0,a_1,\dots ,a_N$ such that 
$$
P(x) = a_0 \dbinom{x}{0} + a_1 \dbinom{x}{1} + \cdots+ a_N \dbinom{x}{N}?
$$
\pause
%
\textbf{Ans:}  Use higher-order differences.  
Set ${\blue (\Delta P)(x)\!=\!P(x+1)\!-\!P(x)}$, and for $j \geq 1$ set 
${\blue (\Delta^{j+1}P)(x)  =  (\Delta^jP)(x+1) - (\Delta^jP)(x)}$. 
Think of $(\Delta^j P)(x)$ as discrete analogue of $j$th derivative $P^{(j)}(x)$. (Compare $P(x+1) - P(x)$ to $P'(x) = \lim\limits_{h\to 0}\dfrac{P(x+h)-P(x)}{h}$.) \pause  

\vspace{.2cm} 

{\bf Example}.  If $P(x) = 3x^2 - x+ 7$ then 
\begin{eqnarray*}
(\Delta P)(x)  & = &  P(x+1) -  P(x) \\
& = & 6x+2, \\
(\Delta^2P)(x) & = & (\Delta P)(x+1) - (\Delta P)(x) \\
& = & 6, 
\end{eqnarray*}
and $(\Delta^jP)(x) = 0$ for $j > 2$. 

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Coefficients}

{\bf Theorem}. {\it For any polynomial $P(x)$ of degree $\leq N$, 
$$
P(x) = a_0 \dbinom{x}{0} + a_1 \dbinom{x}{1} + \cdots+ a_N \dbinom{x}{N}
$$
where ${\blue a_j = (\Delta^jP)(0)} = \sum\limits_{i=0}^{j} (-1)^{j-i}\dbinom{j}{i}P(i)$.  That is,} 
$$\displaystyle {\blue P(x) = \sum\limits_{j=0}^{\deg P} (\Delta^jP) (0)\dbinom{x}{j}}.$$  \pause 
This is a discrete analogue of Taylor's formula 
$$
\displaystyle {\blue P(x) = \sum\limits_{j=0}^{\deg P} P^{(j)}(0) \dfrac{x^j}{j!}}.
$$
%So $(\Delta^jP)(x)$ is really analogous to $P^{(j)}(x)/j!$ rather than $P^{(j)}(x)$. 

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Coefficients}

We have seen several integral-valued polynomials $P(x)$ earlier, and how they 
are written as ${\blue a_0 \dbinom{x}{0} + a_1 \dbinom{x}{1} + \cdots + a_N \dbinom{x}{N}}$:
\begin{eqnarray*}
\frac{1}{2}(x^2+x) & = & \dbinom{x}{2} + \dbinom{x}{1}, \\
\frac{1}{6}x(x+1)(2x+1) & = & 2\dbinom{x}{3} + 3\dbinom{x}{2} + \dbinom{x}{1}, \\
\frac{1}{3}(x^3+2x) &  = &  2\dbinom{x}{3} + 2\dbinom{x}{2} + \dbinom{x}{1},  \\
\frac{1}{4}(x^4+x^2+2x) & =  & 6\dbinom{x}{4} + 9\dbinom{x}{3} + 4\dbinom{x}{2} + \dbinom{x}{1}.
\end{eqnarray*}
All coefficients on the right can be found using the higher-order difference formula $(\Delta^jP)(0) = \sum_{i=0}^{j} (-1)^{j-i}\binom{j}{i}P(i)$ for the coefficient of $\binom{x}{j}$. Let's look at other examples. 


\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Coefficients of $(x^p-x)/p$.}

For prime $p$, $\displaystyle \frac{1}{p}(x^p-x)$ is integral-valued.  How does it look in Polya's theorem?

\begin{itemize}

\item ${\blue \dfrac12 (x^2-x)} = \dbinom{x}{2}$. \pause

\item ${\blue \dfrac13 (x^3-x)} =  2\dbinom{x}{3} + 2\dbinom{x}{2}$. \pause

\item ${\blue \dfrac15 (x^5-x)} = 24\dbinom{x}{5} + 48\dbinom{x}{4} + 30\dbinom{x}{3} +  6\dbinom{x}{2}$. \pause

\item ${\blue \dfrac{1}{p} (x^p-x)} = \sum\limits_{j=2}^{p} \dfrac{j!}{p} \left\{\begin{matrix} p \\ j \end{matrix}\right\} \dbinom{x}{j}$, 
where the curly braces denote Stirling numbers of the second kind.  

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Coefficients for sums of powers}

Famous identities: for any integer $n \geq 1$, 
\begin{eqnarray*}
1 + 2 + \cdots + n & = & \frac{1}{2}n(n+1), \\
1^2 + 2^2 + \cdots + n^2 & = & \frac{1}{6}n(n+1)(2n+1).
\end{eqnarray*}
For any $k \geq 1$, $1^k + 2^k + \cdots + n^k = S_k(n)$ for a polynomial $S_k(x)$ of degree $k+1$.

\begin{itemize}

\item ${\blue \dfrac12 x(x+1)} = \dbinom{x}{2} + \dbinom{x}{1}$. 

\item ${\blue \dfrac16 x (x+1) (2x+1)} = 2 \dbinom{x}{3} + 3 \dbinom{x}{2} + \dbinom{x}{1}$.

\item ${\blue S_k(x) }= \sum\limits_{j=1}^{k+1} (j-1)! \left\{\begin{matrix} k+1 \\ j \end{matrix}\right\} \dbinom{x}{j}$, where the curly braces denote Stirling numbers of the second kind.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Coefficients: binomial coefficients I}

\begin{itemize}

\item ${\blue \dbinom{x}{m}} = \dbinom{x}{m}$, duh. \pause

\item ${\blue \dbinom{x+1}{m}} = \dbinom{x}{m-1} + \dbinom{x}{m}$.

\item ${\blue \dbinom{x+2}{m}} = \dbinom{x}{m-2} + 2\dbinom{x}{m-1} + \dbinom{x}{m}$.

\item ${\blue \dbinom{x+\ell}{m}} = \sum\limits_{k=0}^m \dbinom{\ell}{m-k} \dbinom{x}{k}$ for $\ell \geq 0$. \pause \\
\mbox{} \\
This is the Chu-Vandermonde convolution identity. To prove it, it suffices to show that $\dbinom{n+\ell}{m} = \sum\limits_{k=0}^m \dbinom{\ell}{m-k} \dbinom{n}{k}$ for $n\in\mathbb N$, or even just for $0 \leq n \leq m$. There is a balls-and-urns argument.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Coefficients: binomial coefficients II}

\begin{itemize}

\item ${\blue \dbinom{kx}{m}} = \sum\limits_{j=0}^m a_{j,k,m} \dbinom{x}{j}$ for $k\geq 1$, \\ where $a_{j,k,m}$ is the number of $0,1$-matrices of size $k\times j$ with entry sum $m$ without zero columns. (Thanks to Gjergji Zaimi.)

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{\ \ \ \ Bonus: a question}

For each $m \geq 1$, let 
\begin{eqnarray*}
{\blue P_m(x)} & = & {\blue \dfrac{1}{m!} \prod\limits_{i=0}^{m-1} (x^m - x^i)} \\
& = & \frac{1}{m!}(x^m-1)(x^m-x)(x^m-x^2)\cdots (x^m-x^{m-1}).
\end{eqnarray*}
Why is $P_m(x)$ integral-valued?\\

\pause \mbox{} \\

There is a slick proof that $P_m(p) \in \mathbb Z$ for \textbf{prime} $p$. (Namely: The symmetric group $S_m$ embeds into $\operatorname*{GL}_m\left(\mathbb Z / p\mathbb Z\right)$.) This generalizes to $P_m(p^r) \in \ZZ$ for \textbf{prime powers} $p^r$. But this is not enough to ensure $P_m(n) \in \mathbb Z$ for all integers $n$! (Yet, this holds.)

\pause

\vspace{.3cm}

Thanks to Keith Conrad and Tom Roby for help.

\textbf{Thank you for listening!}
\end{frame}

\begin{frame}
\frametitle{\ \ \ \ References}

\begin{itemize}

\item Wikipedia, \textit{Integer-valued polynomial}.
{\red \url{http://en.wikipedia.org/wiki/Integer-valued_polynomial}}
and references therein.

\item Manjul Bhargava, \textit{The Factorial Function and Generalizations},
American Mathematical Monthly, vol. 107, Nov. 2000, pp. 783-799.
{\red \url{http://www.maa.org/sites/default/files/pdf/upload_library/22/Hasse/00029890.di021346.02p0064l.pdf}}

\item Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, \textit{Concrete Mathematics}, 2nd edition, 1994.

\item {\red \url{http://mathlinks.ro/viewtopic.php?t=421474}},
{\red \url{http://mathlinks.ro/viewtopic.php?t=299793}}

\end{itemize}



\end{frame}

\begin{frame}
\frametitle{\ \ \ \ References (more technical)}

\begin{itemize}

\item Qimh Ritchey Xantcha, \textit{Binomial rings: axiomatisation, transfer, and classification}, arXiv:1104.1931v3.
{\red \url{http://arxiv.org/abs/1104.1931v3}}

\item Manjul Bhargava, \textit{On P-orderings, rings of integer-valued polynomials, and ultrametric analysis}, Journal of the AMS, vol. 22, no. 4, Oct. 2009, pp. 963-993.
{\red \url{http://www.ams.org/journals/jams/2009-22-04/S0894-0347-09-00638-9/S0894-0347-09-00638-9.pdf}}

\end{itemize}

and many others (``binomial rings", $\lambda$-rings, etc.).

\end{frame}

\end{document}

