# 2019-22 Prime divisors of polynomial iterates

Let $$f = X^n + a_{n-1}X^{n-1} + \dots + a_0\in \mathbb{Z}[X]$$ be a polynomial with integer coefficients, and let $$m\in \mathbb{Z}$$.

Consider the sequence $f_0,f_1,f_2,\dots$

where $$f_0:=m$$, and $$f_i:=f(f_{i-1})$$ for all $$i\ge 1$$.

Let $$S:=\{p\in \mathbb{P}: p \text{ divides } f_i \text{ for some } i\ge 0\}$$ be the set of prime divisors of the sequence $$f_0,f_1,f_2,\dots$$.

Assume that $$S$$ is finite, but $$\{f_i\mid i\ge 0\}$$ is infinite. Show that $$f=X^n$$.

GD Star Rating

# 2019-21 Approximate isometry

Let $$A$$ be an $$m \times n$$ matrix and $$\delta \in (0, 1)$$. Suppose that $$\| A^T A – I \| \leq \delta$$. Prove that all singular values of $$A$$ are contained in the interval $$(1-\delta, 1+\delta)$$.

GD Star Rating

# 2019-20 Presentation complex

Let $$G = (S | R)$$ be a group presentation where S is a set of generators and R is a set of relators. Given any subset S’ of S, we set R’ to be the subset of R which consists of words only in the elements of S’. Then the presentation $$S’|R’$$ is called a sub-presentation of $$S|R$$.

The presentation complex for the presentation $$S|R$$ is a cell complex constructed as follows: start with a single vertex v. For each element s of S, we attach an oriented edge labelled by s to v by identifying both endpoints of the edge with v. In this way, we get a wedge of circles where the circles are in 1-1 correspondence with the generating set S. For each element r of R, we attach a closed disk to the wedge of circles we obtained so that the boundary of the disk after gluing can be read using the labels of the edges to be the word r we started with.

For instance, consider the following presentation of a group $$x, y| xyx^{-1}y^{-1}$$. We get a wedge of two circles first labelled by x and y. Then we add one disk so that the boundary reads as $$xyx^{-1}y^{-1}$$. It is easy to see that the resulting space is homeomorphic to the torus. As one sees from this example, the presentation complex is a cell complex whose fundamental group is the group with the given presentation. For a group presentation $$(S|R)$$, let $$K(S|R)$$ denote the presentation complex.

Suppose we have a group presentation $$(S|R)$$ such that any continuous map $$f: S^2 \to K(S|R)$$ is homotopic to a constant map where $$S^2$$ is the 2-sphere. Prove or find a counter-example to that every sub-presentation of $$(S|R)$$ has the same property, i.e., for any sub-presentation $$(S|R)$$, every continuous map $$h: S^2 \to K(S’|R’)$$ is homotopic to a constant map.

GD Star Rating

# 2019-19 Balancing consecutive squares

Find all integers $$n$$ such that the following holds:

There exists a set of $$2n$$ consecutive squares $$S = \{ (m+1)^2, (m+2)^2, \dots, (m+2n)^2 \}$$ ($$m$$ is a nonnegative integer) such that $$S = A \cup B$$ for some $$A$$ and $$B$$ with $$|A| = |B| = n$$ and the sum of elements in $$A$$ is equal to the sum of elements in $$B$$.

GD Star Rating

# 2019-18 Matrix Game

Nubjook and Kai are playing a game. First, they take an empty 2019×2019 matrix and take turns to write numbers in each entry. Once the matrix is completely filled, Nubjook wins if the determinant is nonzero and Kai wins otherwise. If Nubjook does the first move, who has a winning strategy?

• Due to the delay of the problem announcement this time, we set the due date for this problem to be November 18th.
GD Star Rating

# 2019-17 0.7?

Let $$n \in \mathbb{Z}^+$$ and $$x, y \in \mathbb{R}^+$$ such that $$x^n + y^n = 1$$. Prove that
$(1-x)(1-y) \left( \sum_{k=1}^n \frac{1+x^{2k}}{1+x^{4k}} \right) \left( \sum_{k=1}^n \frac{1+y^{2k}}{1+y^{4k}} \right) < \frac{7}{10}.$

GD Star Rating

# 2019-16 Groups with abundant quotients

Suppose a group $$G$$ has a finite index subgroup that maps onto the free group of rank 2. Show that every countable group can be embedded in one of the quotient groups of $$G$$.

GD Star Rating

# 2019-15 Singular matrix

Let $$A, B$$ be $$n \times n$$ Hermitian matrices. Find all positive integer $$n$$ such that the following statement holds:

“If $$AB – BA$$ is singular, then $$A$$ and $$B$$ have a common eigenvector.”

GD Star Rating
A group $$G$$ is called residually finite if for any nontrivial element $$g$$ of $$G$$, there exists a finite group $$K$$ and a surjective homomorphism $$\rho: G \to K$$ such that $$\rho(g)$$ is a nontrivial element of $$K$$.
Suppose $$G$$ is a finitely generated residually finite group. Show that any surjective homomorphism from $$G$$ to itself is an isomorphism.