\Question{Error-Detecting Codes}
Suppose Alice wants to transmit a message of $n$ symbols, so that Bob
is able to \textit{detect} rather than \textit{correct} any errors that have
occured on the way. That is, Alice wants to find an encoding so that Bob, upon
receiving the code, is able to either
\begin{enumerate}[(I)]
\item tell that there are no errors and decode the message, or
\item realize that the transmitted code contains at least one error, and throw away the
message.
\end{enumerate}
Assuming that we are guaranteed a maximum of $k$ errors, how should Alice extend
her message (i.e. by how many symbols should she extend the message, and how
should she choose these symbols)? You may assume that we work in
$\mathrm{GF}(p)$ for very large prime $p$. Show that your scheme works, and that
adding any lesser number of symbols is not good enough.
\nosolspace{4cm}
%\Question{Error-Detecting Codes} In the realm of error-correcting codes, we usually want to recover the original message if we detect any errors, and we want to provide a guarantee of being able to do this even if there are $k$ general errors. Suppose that instead we are satisfied with detecting whether there is any error at all and do not care about the original message if we detect any errors. In class you saw that for recovering from at most $k$ general errors when transmitting a message of length $n$ you need to extend your message by $2k$ symbols and send a message of length $n+2k$. But since we don't require recovering the original message, it is conceivable that we might need less symbols.
%Formally, suppose that we have a message consisting of $n$ symbols that we want to transmit. We want to be able to detect whether there is any error if we are guaranteed that there can be at most $k$ general errors. That is, your receiver should be able to say either 'this message is completely correct' and decode it, or say 'this message has at least one error' and throw it away. How should we extend our message (i.e. by how many symbols should we extend, and how should we get those symbols) in order to be able to detect whether our message has been corrupted on its way? You may assume that we work in $GF(p)$ for a very large prime number $p$. Show that your scheme works, and that adding any lesser number of symbols is not good enough.
\nosolspace{4cm}
% \ffsol{We claim that we need to extend our message by $k$ symbols in order to be able to detect up to $k$ errors. Suppose that the message is extended to $m_1,m_2,\dots,m_k,m_{k+1},\dots,m_{k+n}$. The encoding procedure is exactly the same as what we saw in the lecture. We do the following detection algorithm. Find the unique polynomial of degree $n-1$ that passes through points $(1,m_1)$ up to $(n,m_n)$. Call this polynomial to be $P$. If all of the points corresponding to the extended symbols $(n+1,m_{n+1})$ up to $(n+k,m_{n+k})$ lie on $P$ then we declare that there is no errors. Otherwise the message is corrupted. Now we prove that if we extend the message by any number of symbols less than $k$, then the adversary can perturb the symbols such that the detector does not find it out. Suppose that the message is extended by $k-1$ symbols, $m_{n+1}$ up to $m_{n+k-1}$. Then the adversary can change symbol $m_n$ to $\tilde{m}_n$, find the polynomial that passes through the points $(1,m_1)$ up to $(n,\tilde{m}_n)$. Let this polynomial be $\tilde{P}$. Then the adversary can change the extended symbols such that all of the points $(n+1,\tilde{m}_{n+1})$ up to $(n+k-1,\tilde{m}_{n+k-1})$ lie on $\tilde{P}$. (Note that the adversary can perturb up to $k$ symbols) Therefore, the detector cannot detect that the message is corrupted. This shows that we need at least $k$ extra symbols to detect $k$ errors.
% }
\Question{Berlekamp-Welch Algorithm with Fewer Errors}
% written by Davis Yang
In class we derived how the Berlekamp-Welch algorithm can be used to correct $k$ general errors, given $n+2k$ points transmitted. In real life, it is usually difficult to determine the number of errors that will occur. What if we have less than $k$ errors? This is a follow up to the exercise posed in the notes.
Suppose Alice wants to send $1$ message to Bob and wants to guard against $1$ general error. She decides to encode the message with $P(x)=4$ (on $\operatorname{GF}(7)$) such that $P(0)=4$ is the message she want to send. She then sends $P(0), P(1), P(2) = (4, 4, 4)$ to Bob.
\begin{Parts}
\Part Suppose Bob receives the message $(4, 5, 4)$. Without performing Gaussian elimination explicitly, find $E(x)$ and $Q(x)$.
\Part Now, suppose there were no general errors and Bob receives the original message $(4, 4, 4)$. Show that the $Q(x), E(x)$ that you found in part (a) still satisfies $Q(i)=r_i E(i)$ for all $i=0, 1, 2$.
\Part Verify that $E(x)=x$, $Q(x)=4x$ is another possible set of polynomials that satisfies $Q(i)=r_i E(i)$ for all $i=0, 1, 2$.
\Part Suppose you're actually trying to decode the received message $(4, 4, 4)$. Based on what you showed in the previous two parts, what will happen during row reduction when you try to solve for the unknowns?
\Part Prove that no matter what the solution of $Q(x)$ and $E(x)$ are though, the recovered $P(x)$ will always be the same.
\end{Parts}
\Question{Counting Cartesian Products}
For two sets $A$ and $B$, define the cartesian product as $A \times B = \{(a,b) : a \in A, b \in B \}$.
\begin{Parts}
\Part Given two countable sets $A$ and $B$, prove that $A \times B$ is countable.
\Part Given a finite number of countable sets $A_1, A_2, \dots, A_n$, prove that
$$A_1 \times A_2 \times \cdots \times A_n$$
is countable.
\Part Consider an infinite number of countable sets: $B_1, B_2, \dots$. Under what
condition(s) is \\$B_1 \times B_2 \times \cdots$ countable? Prove that if this
condition is violated, $B_1 \times B_2 \times \cdots$ is uncountable.
\end{Parts}
\Question{Counting Tools}
Are the following sets countable or uncountable? Please prove your claims.
\begin{Parts}
%\Part $A \times B$, where $A$ and $B$ are both countable.
\Part $\bigcup_{i\in A} B_i$, where $A, B_i$ are all countable.
\Part The set of all functions $f$ from $\N$ to $\N$ such that $f$ is
non-decreasing. That is, $f(x) \leq f(y)$ whenever $x \leq y$.
\Part The set of all functions $f$ from $\N$ to $\N$ such that $f$ is
non-increasing. That is, $f(x) \geq f(y)$ whenever $x \leq y$.
%\Part The set of all injective functions from $\N$ to $\N$.
%\Part The set of all surjective functions from $\N$ to $\N$.
\Part The set of all bijective functions from $\N$ to $\N$.
\end{Parts}
\Question{Fixed Points}
Consider the problem of determining if a function $F$ has any fixed points; that is, we want to know if there is any input $x$ such that $F(x)$ outputs $x$. Prove that this problem is undecidable.
\nosolspace{1in}
\Question{Kolmogorov Complexity}
Compression of a bit string $x$ of length $n$ involves creating a program shorter than $n$ bits that
returns $x$. The Kolmogorov complexity of a string $K(x)$ is the length of shortest program that
returns $x$ (i.e. the length of a maximally compressed version of $x$).
\begin{Parts}
\Part
Explain why "the smallest positive integer not definable in under 100 characters" is paradoxical.
\nosolspace{0.5in}
\Part
Prove that for any length $n$, there must be at least one bit string that cannot be compressed.
\nosolspace{0.5in}
\Part
Imagine you had the program $K$, which outputs the Kolmogorov complexity of string. Design a program
$P$ that when given integer $n$ outputs the bit string of length $n$ with the highest Kolmogorov
complexity. If there are multiple strings with the highest complexity, output the lexicographically
first (i.e. the one that would come first in a dictionary).
\nosolspace{1in}
\Part
Suppose the program $P$ you just wrote can be written in $m$ bits. Show that $P$
and by extension, K, cannot exist, for a sufficiently large input $n$.
\nosolspace{1in}
%\Part
%Consider the program $I$, which can be written in $m$ bits, that when given any input string $x$
%returns true if $x$ is incompressible and returns false otherwise. Show that such a program
%cannot exist.
%\nosolspace{1in}
\end{Parts}