\documentclass[12pt]{article}

\usepackage{comment}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid

\newcommand{\D}{{\mathbb D}}
\newcommand{\G}{{\mathbb G}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Q}{{\mathbb Q}}


\begin{document}


\centerline{Homework 03, MORALLY Due Feb 24}

\begin{enumerate}
\item
(25 points)
For this problem FIRST write the program and make conjectures THEN
look up whats true. 

\begin{enumerate}
\item
(0 points) 
Write a program that does the following:
For every $1\le n\le 5000$:
\begin{itemize}
\item
Using the Dynamic Prog Method (Leo will tell you about that in recitation)
to determine natural numbers $(x_1,x_2,\ldots,x_k)$ such that 
$x_1^4 + \cdots + x_k^4=n$, with $k$ as small as possible. 
\item
Below I have the some rows of the output (I didn't use the first $x$ rows since they are boring). 
\end{itemize}


\begin{tabular}{|l|l|l|}
\hline
 $n$ &  $k$ & $x_i$'s \cr
\hline
10           & 10& $10=10\times 1^4$   \cr
11           & 11& $11=11\times 1^4$ \cr
12           & 12& $12=12\times 1^4$  \cr
13           & 13& $13=13\times 1^4$  \cr
14           & 14& $14=14\times 1^4$  \cr
15           & 15& $15=14\times 1^4$  \cr
16           & 1 & $16=1\times 2^4$  \cr
17           & 2& $17=1\times 2^4 + 1\times 1^4$  \cr
18           & 3& $18=1\times 2^4+2\times 1^4$  \cr
19           & 4& $19=1\times 2^4+3\times 1^4$ \cr
20           & 5& $20=1\times 2^4+4\times 1^4$  \cr
21           & 6& $21=1\times 2^4+5\times 1^4$  \cr
22           & 7& $22=1\times 2^4+6\times 1^4$  \cr
\hline
\end{tabular}

\bigskip

DO NOT hand in the program or the output. 

\vfill

\centerline{\bf GO TO NEXT PAGE FOR THE REST OF THIS PROBLEM}

\newpage

\item
(10 points)
Create a table that shows how many numbers $\leq 5000$ require 1 fourth-power, 2 fourth-powers, 
3 powers, and so on.  Below is a sample table (THIS DOES NOT CONTAIN THE CORRECT ANSWER):
\begin{center}
    \begin{tabular}{|c|c|c|}
     \hline  $\# $ of fourth powers\\ \hline
        1 & 3 & 8 \\
        2 & 4 & 2 \\
        3 & 28 & 17 \\
        \vdots & \vdots &\vdots \\ \hline
    \end{tabular}
\end{center}
\item 
(10 points) Based on this data make conjectures of the following forms:

\begin{enumerate}
\item 
Every $n$ is the sum of $\le XXX$ fourth powers. 
Write your conjecture in quantifiers. 
\item
All but a finite number of $n$ is the sum of $\le XXX$ fourth powers. 
Write your conjecture in quantifiers. 
\end{enumerate}
\item
(5 points) 
Look on the web and/or use AI to determine what is known and what is conjectured
about these problems.
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage



\item
(25 points) 
\begin{enumerate}
\item
(10 points)
View the input $x,y,z$ as the number in binary $xyz$ which we denote $(xyz)$. 
For example, $100$ is 4. 

Write a Truth Table for the following function with 3 inputs $x,y,z$ and 1 outputs $b$. 

\begin{equation*}
f(x,y,z) = 
\begin{cases}
0  & \hbox{if $(xyz)$ is NOT PRIME.} \cr
1  & \hbox{if $(xyz)$ is PRIME.} \cr
\end{cases}
\end{equation*} 

(NOTE: 0 and 1 are NOT primes. We will discuss this more carefully later.) 

\item
(15 points) 
Convert your truth table into formulas and give it to us. 
DO NOT SIMPLIFY.

\item
(0 points- DO NOT HAND IN)
Draw a circuit that computes that truth table. 
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(25 points)
(In this problem we will guide you through a proof that $N(\alpha\beta)=N(\alpha)N(\beta)$.)

\newcommand{\ov}[1]{\overline{#1}}

Let $d\in\Z$ and $d\ge 2$. Let $\D_d = \{ a+b\sqrt{d} \colon a,b\in\Z\}$. 

Let $\alpha\in \D_d$, $\alpha = a+b\sqrt{d}$. Let $\ov \alpha = a-b\sqrt{d}$. 

Let $N(\alpha)=\alpha\ov \alpha$. By calculation $N(\alpha)= (a+b\sqrt{d})(a-b\sqrt{d})=a^2-db^2.$

For the questions below let $\alpha=a+b\sqrt{d}$ and $\beta = e+f\sqrt{d}$. 

\begin{enumerate}
\item
(0 points-Do Not Hand In Anything)
What is $\ov{\alpha\beta}$ in terms of $a,b,d,e,f$. 
\item
(0 points-Do Not Hand In Anything)
What is $\ov \alpha \ov \beta $ in terms of $a,b,d,e,f$. 
\item
(0 points-Do Not Hand In Anything)
If you did part a a and b correctly then you showed that
$$\ov{\alpha\beta}=\ov \alpha  \ov \beta .$$

\item
(25 points) 
Show that $N(\alpha\beta)=N(\alpha)N(\beta)$

Hint1: Use $N(x)=x\ov x$. 

Hint2: Use $\ov{\alpha\beta}=\ov{\alpha}\ov{\beta}$. 

Hint3: Do not use $a,b,d,e,f$. 

\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE} 

\newpage


\item 
(25 points) 
Let $\D_d = \{ a+b\sqrt{d} \colon a,b\in\Z\}$

\begin{enumerate}
\item 
Give an infinite number of units of $\D_3$. 

\item 
Give an infinite number of units of $\D_5$. 

\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE} 

\newpage

\item
(0 point-Extra Credit- Graded separately). 

Consider the following problem:

{\it COUNTSAT: Given a formula $\phi$ determine how many satisfying assignments it has.}

Clearly if COUNTSAT can be solved quickly then SAT can be solved quickly. 

How about the converse? 

Is the following true: If SAT can be solved quickly then COUNTSAT can be solved quickly. 

LOOK UP what is known about this and give me a WELL WRITTEN writeup of what is known
including formal definitions and statement of theorems. 

\end{enumerate}

\end{document}
\item






\end{enumerate}

\end{document}