\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{url}
\usepackage{amsmath}

% This is a file of macros and definitions that may come up in
% ANY LATEX paper.  Typically I'll use this file and some other file in the
% directory of the paper, this one for general math things, that one for
% things specific to that paper.
%
% font's used and general paper things.
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\eightrm=cmr8
\font\sevenrm=cmr7
% \font\title=cmbx10 scaled \magstep1 % extra big title font
\font\ss=cmss10 % used by \proof
\font\smallcaps=cmcsc10 % used to label Theorems, etc.
% imhibit black bars on overflows
%
\overfullrule=0pt
%
% today's date
%
%
% English words that I always italizice in papers.
% Some words that appear in math mode alot that I wasn roman
%

\newcommand{\IO}{\exists^\infty}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\newcommand{\into}{{\rightarrow}}
\newcommand{\D}{{\sf D}}
\newcommand{\N}{{\sf N}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\reals}{{\sf R}}
\newcommand{\qd}{{\rm qd}}
\newcommand{\LL}{{\cal{L}}}
\newcommand{\onepe}{1+\epsilon}
\newcommand{\oneme}{1-\epsilon}
\newcommand{\cool}{cool}
\newcommand{\nze}{numzeros}
\newcommand{\non}{numones}
\newcommand{\LR}[2]{ {\rm LR}_{{#2}}({#1})}
\newcommand{\LH}[2]{ {\rm LH}({#1};{#2})}
\newcommand{\bbb}{{\gamma}}
\newcommand{\COL}{{\rm COL}}
\newcommand{\card}[1]{\#(#1)}
\newcommand{\st}{\mathrel{:}}
\newcommand{\fhat}{{\hat{f}}}
\newcommand{\Ahat}{{\hat{A}}}

\begin{document}

\centerline{\bf Homework 01, Morally Due Tue Feb 3, 2026}

\newif{\ifshowsoln}
%\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}

\item
(0 points) But DO IT anyway. 
\begin{enumerate}
\item 
What is your name?  Write it clearly.

\item
When is the midterm scheduled (give Date and Time)?
If you cannot make it in that day/time see me ASAP.

\item
What is the Dead Cat Policy?

\end{enumerate}

\vfill\eject 

\item
(30 point)
\begin{enumerate}
\item
(10 points) 
Let $m\in\N$ with $m\ge 2$. 

Let $\COL \colon \binom{\N}{2}\into [m]$ be 

$$\COL(x,y) = x+y \pmod m$$

For $0\le i\le m-1$ let

$$A_i = \{ x \colon x\equiv i \pmod m \}$$

Every infinite subset of an $A_i$ is an infinite homog set. 

Fill in the XXX in the following statement:

\bigskip

{\it 
The following are equivalent
\begin{itemize}
\item
There is an infinite homog set that is NOT an infinite subset of one of the $A_i$'s. 
\item
$m$ has property XXX. 
\end{itemize}
}

\bigskip


\item
(10 points) 
Let $\COL \colon \binom{\N}{2}\into \N$ be 

$$\COL(x,y) = |x-y|.$$

Find a number $X\in\N$ such that the following is true, and prove it: 

{\it There is a homog set of size $X$ but not of size $X+1$. }

\bigskip

\item
(10 points) 
Let $\COL \colon \binom{\reals\times\reals}{2}\into \reals$ be 

$$\COL(x,y) = d(x,y).$$

($x$ and $y$ are points in the plane and $d(x,y)$ is the distance
between $x$ and $y$.)

\bigskip

So $\COL$ takes two points in the plane and returns the length of the
line between them. 

Find a number $X\in\N$ such that the following is true, and prove it: 

{\it There is a homog set of size $X$ but not of size $X+1$. }
\end{enumerate}


\vfill\eject

\item
(30 points) Let $x_1,x_2,\ldots$ be a sequence of reals. 

{\bf Notation:} When we write $\COL(i,j)$ we assume $i<j$. 

Let $\COL \colon \binom{\N}{2} \into [3]$ be defined by 

\begin{equation}
\COL(i,j) =
\begin{cases}
1 & \text{$x_i<x_j$};\\
2 & \text{$x_i=x_j$};\\
3 & \text{$x_i>x_j$}.\\
\end{cases}
\end{equation} 


\begin{enumerate}
\item
(30 points) 
Fill in the XXX in the following sentence to make it true.

\bigskip

{\it Apply Ramsey's Theorem to $\COL$. This gives a theorem: given any
sequence of reals $x_1,x_2,x_3,\ldots$ there exists a subsequence (the homog set)
such that XXX.}

\bigskip

\item 
(0 points) Think about. Let $x_1,x_2,\ldots$ be a sequence of reals between 0 and 1.
Using Part 1 (so using XXX) what well known theorem can you prove? 
\end{enumerate}


\vfill\eject


\item
(20 points) 
Let $f\colon \Z\into\Z$. 
Show that there exist an infinite $\D\subseteq \Z$ such that
$f$ restricted to $\D$ (with co-domain still $\Z$) 
is NOT onto. 

\vfill\eject 

\item
(20 points)
(This is not a question in Ramsey Theory but it is a prelude to one of our
``Applications.'')

{\bf Notation} $\Z$ is the integers. $\Z[x_1,\ldots,x_n]$ is the
set of all polynomials in $\{x_1,\ldots,x_n\}$ with coefficients in $\Z$. 

For $p(x,y)\in\Z[x,y]$, we view $p$ as a function from $Z\times\Z$ into $\Z$. 

Note that $p(x,y)$ might be onto (e.g., $p(x,y)=x+y+1$) 
or not (e.g., $p(x,y)=x^2 + y^2+10$). 

Prove the following:

\begin{enumerate}
\item
FOR ALL $p(x,y)\in \Z[x,y]$ 
there is an infinite set $\D\subseteq \Z$ such that $p$ restricted to $\D\times \D$
is NOT onto $\Z$ (that is, there is some element of $\Z$ not in the image). 
\item
FOR ALL $p(x,y)\in \Z[x,y]$, if we let 
$q(x,y)=\ceil{p(x,y)^{1/11}}$ (Note that a number has many $11$th roots,
but only one real one. Take the real one.) 
then there is an infinite set $\D\subseteq \Z$ such that $q$ restricted to $\D\times\D$
is NOT onto $\Z$.
\end{enumerate}

\vfill\eject


\item
(EXTRA CREDIT)
Prove or Disprove: FOR ALL function $p\colon \Z\times\Z$ there is 
an infinite set $\D\subseteq\Z$ such that $p$ restricted to $\D\times \D$ 
is NOT onto $\Z$ (that is, there is some element of $\Z$ not in the image). 
\end{enumerate}


\end{document}