# Questions

## Table of Contents

## 1 Questions

### 1.1 Analysis

- Find all (complex) solutions to the equation \( 6z^5 + 15z^4 + 20z^3 + 15z^2 + 6z + 1= 0 \).
- Consider the function \( f : \mathcal{P}(\mathbb{N}) \to \mathbb{N} \) defined by:

let \( p_n \) be the nth prime number, and let \( S = \{n_1, n_2, n_3, ...\} \) then \( f \) is given by:

\( f(S) = p_1^{n_1} * p_2^{n_2} * ... \)

We claim this implies there is a injection from the powerset of naturals to the naturals and so we provide a counterexample to Cantor's Theorem. Where is the mistake?

- Find a closed form for \( \sum^n_{k=1} k \cos(kx) \).
- Prove or give a counterexample: if a function \( f: \mathbb{R} \to \mathbb{R} \) is infinitely differentiable, and is nonzero somewhere on its domain, then it has countably many roots.
- Show \( n! \) is not elementary.

### 1.2 Algebra

- Show that the Fundamental Theorem of Algebra and the statement that a polynomial of degree \( n \) has exactly \( n \) complex roots (including multiplicity), are equivalent.
- Show that if \( G \) and \( H \) are groups of cardinality \( p \) where \( p \) is prime, then \( G \) and \( H \) are isomorphic.
- Show that if \( R \) is a finite integral domain, then it is also a field (Wedderburn's little theorem).
- Given any prime \( p \), show that \( \mathbb{F}_{p} \) is not algebraically closed.
- Do the 32 bit integers under two's complement form a group under addition? If not what structure do they form?
- Show the algebraic numbers form a subring of \( \mathbb{C} \). Do they form a field?

### 1.3 Linear Algebra

- Show that a matrix is singular iff it has 0 as an eigenvalue.
- Show that if \( M \) is an invertible matrix in some field \( K \), and has entries all in some subfield \( J \subseteq K \), then \( M^{-1} \) also has all of its entries in \( J \). What if \( J \) is not a field?
- Let \( R \) denote the set of rows of a matrix \( A \), and \( C \) the set of columns. Prove or find a counterexample to: if \( R = C \) then \( A \) is symmetric.

### 1.4 Number Theory

- Show that there are no solutions to the diophantine equation \( a^2 + b^2 = c^2 \) if both \( a \) and \( b \) are odd.
- Show that \( \liminf\limits_{n \to \infty} \frac{\phi(n)}{n} = 0 \)
- I choose a positive integer \( n \le 10000 \), your task is to determine whether or not this number is prime by "asking" a number \( k \), to which I will say "yes" if \( k \) is a divisor of \( n \), or "no" if it is not. What is the fewest number of "asks" needed so that you are guarenteed to know whether or not \( n \) is prime?
- The powers of two \( \{ 2^0, 2^1, 2^2... \} \) are a very special sequence, any positive integer can be written as a sum of unique powers of two in exactly one way. Prove the powers of two are the only strictly increasing positive integer sequence with this property.

### 1.5 Graph Theory

- Show that \( \chi(C_{2n + 1}) = 3 \ \forall n \in \mathbb{Z}^+ \).
- How many trees are there of size \( n \) up to isomorphism?

### 1.6 Computation

- Find the smallest integer \( n \) such that \( n\ln{n} + n > 3^{197} \)
- How many palindromes are there beneath \( 10^{100} \)? What about \( 100! \) ?
- Let \( P_n = \{ s \in "([|])\{2n\}" : \text{s is parenthetically closed} \} \) show that \( P = \cup_{n \in \mathbb{N}} P_n \) is not a regular language.
- Describe a list implementation (\( \text{append}(e: E): \text{unit}, \ \text{get}(idx): E, \ \text{remove}(idx): \text{unit} \)) with \( O(1) \) appends and removals.
- What are the differences (if any) between the return values of these two functions:

def append1(x: List, y: List): x = x + [y] return x def append2(x: List, y: List): x.append(y) return x