\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage{ifthen}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, October 23, 2017 09:39:38}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\conncomp}{\operatorname{conncomp}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 4990 Fall 2017 (Darij Grinberg): homework set 4}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 4990 Fall 2017 (Darij Grinberg): homework set 4 [corrected 18 Oct
2017]}

due date: Tuesday 24 Oct 2017 at the beginning of class, or before that by
email or moodle

Please solve \textbf{at most 4} of the 7 exercises!
\end{center}

Two integers $a$ and $b$ are said to be \textit{coprime} if their greatest
common divisor is $1$. (Note that $\gcd\left(  a, 0\right)  = \left|
a\right|  $ for any integer $a$.)

The \textit{Euler totient function }$\phi:\left\{  1,2,3,\ldots\right\}
\rightarrow\mathbb{N}$ is defined by%
\begin{align*}
\phi\left(  n\right)   &  =\left(  \text{the number of all }m\in\left[
n\right]  \text{ that are coprime to }n\right) \\
&  =\left\vert \left\{  m\in\left[  n\right]  \ \mid\ m\text{ is coprime to
}n\right\}  \right\vert .
\end{align*}
More about greatest common divisors and about this function can be found in
\href{https://courses.csail.mit.edu/6.042/fall17/mcs.pdf}{Lehman/Leighton/Meyer}
(Chapter 9). That said, you won't need anything but the definitions in this
homework set.

\begin{exercise}
\label{exe.phi-even}Let $n$ be a positive integer.

\textbf{(a)} Prove that if $m$ is an integer coprime to $n$, then $n-m$ is
also an integer coprime to $n$.

\textbf{(b)} Prove that $\phi\left(  n\right)  $ is even if $n>2$.

[\textbf{Hint:} If you haven't used the $n>2$ requirement, then you must have
missed something. $\phi\left(  2\right)  =1$, which is not even!]
\end{exercise}

\begin{exercise}
\label{exe.maple}A preprint recently posted on the arXiv says (in a proof)
that \textquotedblleft%
\[
1-\sum_{i=2}^{d}\left(  i-1\right)  \dbinom{d}{i}\left(  \dfrac{1}%
{d-1}\right)  ^{i}=0,
\]
the final equality being verified by the computer algebra system Maple (which
itself employs \href{https://www.math.upenn.edu/~wilf/AeqB.html}{an algorithm
of Zeilberger})\textquotedblright. Here, $d$ is assumed to be an integer
$\geq2$.

Prove this equality by hand (but feel free to use a computer to write up your
proof...). More generally, find and prove a sum-less expression for%
\[
\sum_{i=2}^{d}\left(  i-1\right)  \dbinom{d}{i}q^{i}%
\]
where $q$ is an arbitrary rational number (and $d$ is still an integer $\geq2$).
\end{exercise}

\begin{exercise}
\label{exe.screaming-toes}Let $n\in\mathbb{N}$. Consider $n$ people standing
in a circle. Each of them looks down at someone else's feet (i.e., at the feet
of one of the other $n-1$ persons). A bell sounds, and every person
(simultaneously) looks up at the eyes of the person whose feet they have been
ogling. If two people make eye contact, they scream. Show that the probability
that no one screams is%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dfrac{n\left(  n-1\right)  \cdots\left(
n-2k+1\right)  }{\left(  n-1\right)  ^{2k}\cdot2^{k}\cdot k!}.
\]


Combinatorial restatement (feel free to solve this instead): A pair $\left(
i,j\right)  $ of elements of $\left[  n\right]  $ is said to \textit{scream}
at a map $f:\left[  n\right]  \rightarrow\left[  n\right]  $ if it satisfies
$f\left(  i\right)  =j$ and $f\left(  j\right)  =i$. A map $f:\left[
n\right]  \rightarrow\left[  n\right]  $ is \textit{silent} if no pair
$\left(  i,j\right)  \in\left[  n\right]  \times\left[  n\right]  $ screams at
$f$. Prove that the number of all silent maps $f:\left[  n\right]
\rightarrow\left[  n\right]  $ is%
\[
\sum_{k=0}^{n}\left(  -1\right)  ^{k}\dfrac{n\left(  n-1\right)  \cdots\left(
n-2k+1\right)  }{2^{k}\cdot k!}\left(  n-1\right)  ^{n-2k}.
\]

\end{exercise}

\begin{exercise}
\label{exe.peter-identity}Let $i$ and $j$ be positive integers. Prove that%
\[
\sum_{k=\max\left\{  i,j\right\}  }^{i+j}\left(  -1\right)  ^{k}\dfrac{\left(
k-1\right)  !}{\left(  k-i\right)  !\left(  k-j\right)  !\left(  i+j-k\right)
!}=0.
\]


[\textbf{Hint:} Assume that $i\geq j$, and rewrite $\dfrac{\left(  k-1\right)
!}{\left(  k-i\right)  !\left(  k-j\right)  !\left(  i+j-k\right)  !}$ as a
constant (independent of $k$) times a product of two binomial coefficients,
one of which is $\dbinom{i}{k-j}$.]
\end{exercise}

\begin{exercise}
\label{exe.bintra}Let $N\in\mathbb{N}$. Let $\left(  a_{0},a_{1},\ldots
,a_{N}\right)  $ be a list of rational numbers. Define a second list $\left(
b_{0},b_{1},\ldots,b_{N}\right)  $ of rational numbers by setting%
\[
b_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}a_{i}%
\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{  0,1,\ldots,N\right\}  .
\]
Prove that
\[
a_{n}=\sum_{i=0}^{n}\left(  -1\right)  ^{i}\dbinom{n}{i}b_{i}%
\ \ \ \ \ \ \ \ \ \ \text{for each }n\in\left\{  0,1,\ldots,N\right\}  .
\]

\end{exercise}

Now, recall some of the notations for finite differences:

Per se, the words \textquotedblleft map\textquotedblright, \textquotedblleft
mapping\textquotedblright, \textquotedblleft function\textquotedblright,
\textquotedblleft transformation\textquotedblright\ and \textquotedblleft
operator\textquotedblright\ are synonyms in mathematics (they all mean
assignments of values from one set to the elements of another set). But it is
common to use some of these words selectively for certain kinds of maps. We
shall follow the following rules:

\begin{itemize}
\item The word \textquotedblleft map\textquotedblright\ can mean any kind of map.

\item The word \textquotedblleft function\textquotedblright\ shall mean a map
from $\mathbb{Q}$ to $\mathbb{Q}$. Thus, the set of all functions is
$\mathbb{Q}^{\mathbb{Q}}$.

\item The word \textquotedblleft operator\textquotedblright\ shall mean a map
from $\mathbb{Q}^{\mathbb{Q}}$ to $\mathbb{Q}^{\mathbb{Q}}$. Thus, an operator
is a map sending functions to functions.
\end{itemize}

For example, the map%
\[
\mathbb{Q}\rightarrow\mathbb{Q},\ \ \ \ \ \ \ \ \ \ x\mapsto x^{2}%
\]
is a function, whereas the map%
\[
\mathbb{Q}^{\mathbb{Q}}\rightarrow\mathbb{Q}^{\mathbb{Q}}%
,\ \ \ \ \ \ \ \ \ \ f\mapsto f\circ f
\]
(\textquotedblleft apply a function twice\textquotedblright) is an operator.

If $f$ and $g$ are functions, then $f+g$ denotes the pointwise sum of $f$ and
$g$ (that is, the function $\mathbb{Q}\rightarrow\mathbb{Q},\ x\mapsto
f\left(  x\right)  +g\left(  x\right)  $), and $fg$ denotes the pointwise
product of $f$ and $g$ (that is, the function $\mathbb{Q}\rightarrow
\mathbb{Q},\ x\mapsto f\left(  x\right)  g\left(  x\right)  $). We can also
write $f\cdot g$ for $fg$.

If $f$ is a function and $\lambda\in\mathbb{Q}$, then $\lambda f$ denotes the
pointwise product of $\lambda$ with $f$ (that is, the function $\mathbb{Q}%
\rightarrow\mathbb{Q},\ x\mapsto\lambda f\left(  x\right)  $). Thus, the
functions form a $\mathbb{Q}$-vector space (and better yet, a commutative
$\mathbb{Q}$-algebra, because of the multiplication).

The following three operators are particularly important:

\begin{itemize}
\item The identity operator $\operatorname*{id}:\mathbb{Q}^{\mathbb{Q}%
}\rightarrow\mathbb{Q}^{\mathbb{Q}}$. It sends each function $f$ to $f$ itself.

\item The shift operator $S:\mathbb{Q}^{\mathbb{Q}}\rightarrow\mathbb{Q}%
^{\mathbb{Q}}$. It sends each function $f$ to the function $S\left(  f\right)
$ defined by $\left(  S\left(  f\right)  \right)  \left(  x\right)  =f\left(
x+1\right)  $ for all $x\in\mathbb{Q}$. Speaking in terms of function plots,
the operator $S$ shifts a function by $1$ to the left.

\item The difference operator $\Delta:\mathbb{Q}^{\mathbb{Q}}\rightarrow
\mathbb{Q}^{\mathbb{Q}}$. It sends each function $f$ to the function
$\Delta\left(  f\right)  $ defined by $\left(  \Delta\left(  f\right)
\right)  \left(  x\right)  =f\left(  x+1\right)  -f\left(  x\right)  $ for all
$x\in\mathbb{Q}$. Speaking in terms of function plots, the operator $\Delta$
shifts a function by $1$ to the left and subtracts the original function back
from it. Note that $\Delta\left(  f\right)  =S\left(  f\right)  -f$ for each
$f\in\mathbb{Q}^{\mathbb{Q}}$.
\end{itemize}

Here are some examples of what the difference operator $\Delta$ does to
certain functions\footnote{We use the shorthand notation \textquotedblleft%
$\left(  x\mapsto x^{2}\right)  $\textquotedblright\ for the function
$\mathbb{Q}\rightarrow\mathbb{Q},\ x\mapsto x^{2}$, because all of our
functions are from $\mathbb{Q}$ to $\mathbb{Q}^{2}$ anyway.}:%
\begin{align*}
\Delta\left(  x\mapsto1\right)   &  =\left(  x\mapsto1-1\right)  =\left(
x\mapsto0\right)  ;\\
\Delta\left(  x\mapsto x\right)   &  =\left(  x\mapsto\left(  x+1\right)
-x\right)  =\left(  x\mapsto1\right)  ;\\
\Delta\left(  x\mapsto x^{2}\right)   &  =\left(  x\mapsto\left(  x+1\right)
^{2}-x^{2}\right)  =\left(  x\mapsto2x+1\right)  ;\\
\Delta\left(  x\mapsto\dbinom{x}{2}\right)   &  =\left(  x\mapsto\dbinom
{x+1}{2}-\dbinom{x}{2}\right)  =\left(  x\mapsto x\right)  ;\\
\Delta\left(  x\mapsto2^{x}\right)   &  =\left(  x\mapsto2^{x+1}-2^{x}\right)
=\left(  x\mapsto2^{x}\right)  .
\end{align*}
(The last example is not completely kosher, since the function $\mathbb{Q}%
\rightarrow\mathbb{Q},\ x\mapsto2^{x}$ does not actually exist: $2^{x}$ isn't
always rational. To make sense of it, imagine that we are talking about maps
from $\mathbb{Z}$ to $\mathbb{Q}$, or from $\mathbb{R}$ to $\mathbb{R}$,
instead.) Actually, for every $n\in\mathbb{N}$, we have%
\[
\Delta\left(  x\mapsto x^{n}\right)  =\left(  x\mapsto\left(  x+1\right)
^{n}-x^{n}\right)  =\left(  x\mapsto\sum_{k=0}^{n-1}\dbinom{n}{k}x^{k}\right)
\]
and%
\[
\Delta\left(  x\mapsto\dbinom{x}{n}\right)  =\left(  x\mapsto\dbinom{x+1}%
{n}-\dbinom{x}{n}\right)  =\left(  x\mapsto\dbinom{x}{n-1}\right)  .
\]


If our functions were $C^{\infty}$-functions $\mathbb{R}\rightarrow\mathbb{R}$
instead of maps $\mathbb{Q}\rightarrow\mathbb{Q}$, then $\dfrac{d}{dx}$ would
be another operator (sending each function $f$ to its derivative).

\begin{verlong}
Operators are maps, and thus can be composed with each other and applied
multiple times. We shall write $\Delta^{n}$ for the composition
$\underbrace{\Delta\circ\Delta\circ\cdots\circ\Delta}_{n\text{ times}}$ (for
any $n\in\mathbb{N}$).
\end{verlong}

\begin{exercise}
\label{exe.operator-basics}\textbf{(a)} Prove that $S\left(  fg\right)
=S\left(  f\right)  \cdot S\left(  g\right)  $ for any two functions $f$ and
$g$.

\textbf{(b)} Prove that $\Delta\left(  fg\right)  =S\left(  f\right)
\Delta\left(  g\right)  +\Delta\left(  f\right)  g$ for any two functions $f$
and $g$.

\textbf{(c)} Prove that $\Delta\left(  fg\right)  =f\Delta\left(  g\right)
+\Delta\left(  f\right)  S\left(  g\right)  $ for any two functions $f$ and
$g$.

\textbf{(d)} Prove that $\Delta\circ S=S\circ\Delta$.
\end{exercise}

And finally, let's take our tale of periodic tuples and necklaces to its
(temporary) conclusion:\footnote{To remind: You are allowed to use the
exercises from previous problem sets even if you did not solve them.}

\begin{exercise}
\label{exe.periodic.3}This exercise is a continuation of Exercise 7 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw2s.pdf}{homework set \#2}
and of Exercise 6 on
\href{http://www.cip.ifi.lmu.de/~grinberg/t/17f/hw3o.pdf}{homework set \#3}.

Let $p$ be a \textbf{prime} number. Let $X$ be a set.

\textbf{(a)} Let $\mathbf{x}\in X^{p}$ be a $p$-tuple. Prove that:

\begin{itemize}
\item if all entries of $\mathbf{x}$ are equal (that is, if $\mathbf{x}$ has
the form $\left(  \underbrace{x,x,\ldots,x}_{p\text{ times}}\right)  $ for
some $x\in X$), then $\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert
=1$;

\item otherwise, we have $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =p$.
\end{itemize}

[\textit{Example:} If $p=3$, then the $3$-tuple $\mathbf{x}=\left(
5,5,5\right)  $ satisfies $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =1$, while the $3$-tuple $\mathbf{x}=\left(  1,3,1\right)  $
satisfies $\left\vert \left[  \mathbf{x}\right]  _{\sim}\right\vert =3$.]

A $p$-necklace $\left[  \mathbf{x}\right]  _{\sim}$ is said to be
\textit{aperiodic} if $\left\vert \left[  \mathbf{x}\right]  _{\sim
}\right\vert =p$.

\textbf{(b)} Assume that the set $X$ is finite. Prove that the number of all
aperiodic $p$-necklaces (over $X$) is $\dfrac{\left\vert X\right\vert
^{p}-\left\vert X\right\vert }{p}$.

[\textit{Example:} If $p=3$ and $X=\left\{  1,2,3\right\}  $, then the
aperiodic $p$-necklaces over $X$ are%
\begin{align*}
&  \left[  \left(  1,1,2\right)  \right]  _{\sim},\ \left[  \left(
1,1,3\right)  \right]  _{\sim},\ \left[  \left(  1,2,2\right)  \right]
_{\sim},\ \left[  \left(  1,2,3\right)  \right]  _{\sim},\\
&  \left[  \left(  1,3,2\right)  \right]  _{\sim},\ \left[  \left(
1,3,3\right)  \right]  _{\sim},\ \left[  \left(  2,2,3\right)  \right]
_{\sim},\ \left[  \left(  2,3,3\right)  \right]  _{\sim}.
\end{align*}
You can, of course, write them differently: e.g., $\left[  \left(
1,2,3\right)  \right]  _{\sim}$ is also known as $\left[  \left(
2,3,1\right)  \right]  _{\sim}$ (but $\left[  \left(  1,3,2\right)  \right]
_{\sim}$ is different). The $p$-necklaces that are not aperiodic are $\left[
\left(  1,1,1\right)  \right]  _{\sim}$, $\left[  \left(  2,2,2\right)
\right]  _{\sim}$ and $\left[  \left(  3,3,3\right)  \right]  _{\sim}$.]

\textbf{(c)} Prove \textit{Fermat's Little Theorem}, which states that $p\mid
a^{p}-a$ for every integer $a$. [\textbf{Note:} $a$ might be negative.]

\textbf{(d)} Assume that the set $X$ is finite. Prove that the number of all
$p$-necklaces (over $X$) is $\dfrac{\left\vert X\right\vert ^{p}+\left(
p-1\right)  \left\vert X\right\vert }{p}$.
\end{exercise}

We have thus counted $p$-necklaces for a prime number $p$. Counting
$n$-necklaces for $n$ composite is harder; we will learn about this later.


\end{document}