\documentclass[aspectratio=169]{beamer}
\usetheme{default}
\usenavigationsymbolstemplate{} 
\usepackage{amsmath, amssymb, mathtools, hyperref}
\usepackage{bbm}

\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\SL}{SL}
\newcommand{\eps}{\varepsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\measure}{\operatorname{measure}} % Define the \measure command

\begin{document}
	\begin{frame}{Geometry of Numbers TCC 2024 Exercises}
		
	The motivation for these questions is explained in the  \href{https://urss.warwick.ac.uk/items/show/251}{summer project of Kate Thomas}.
	
	\bigskip
	We are going to study, for a variable $t \in (0,1)$ and a parameter $N>1$ which can be thought of as very large, the quantity
	\begin{multline*}
	I(t,N) =
	\int_{\substack{\alpha\in \Mat^{\Sym}_d(\R)\\ \|\alpha\|<1}} \#\{A,B \in \Mat_{d\times d}(\Z) : \|A\| < N, \|t A \alpha-B\| <1/N\} \\
	=
	\sum_{A,B \in \Mat_{d\times d}(\Z) : \|A\| < N} \measure\{\alpha\in \Mat^{\Sym}_d(\R): \|\alpha\|<1 ,\|tA  \alpha-B\| <1/N\},
	\end{multline*}
	but we'll work up to it by steps.
	\end{frame}


\begin{frame}{Marking}	75\% for submitting solutions to at least three questions (25 each, best three count). Many questions are open-ended or hard. \textbf{I will be looking only for a plausible strategy followed through to its logical conclusion, whether or not it successfully answers the question.} You are welcome to check with me if you're not sure. If between you all questions get answers, we should almost have a theorem!
\end{frame}

	\begin{frame}{Notation}
	For an $m \times n$ real matrix $M$, we define the 2-norm $\|M\| = \sqrt{\sum M_{ij}^2}$. 
	
	\bigskip
	Recall the Smith normal form of $A$,
	\[
	A = U^{-1} \diag(e_1,\ldots,e_d) V^{-1},
	\]
	where $U, V \in \SL_n(\Z)$ and $e_i\in \N$ with $e_1\mid \dotsb \mid e_d$.
	
	\bigskip
	We will use big-O/little-o and Vinogradov $\ll$ notation. You may want to use the ``divisor bound”
		\[
		\{d\in \N: d|m\} \ll_\eps m^\eps (m \in \N).
		\]
		In general, in these questions, when you’re asked for an upper bound it’s always OK for it to be multiplied by $O_\eps((\text{some variable})^\eps)$.
	\end{frame}

\begin{frame}	
\begin{enumerate}
	\item  As a warm-up we’ll count invertible matrices $A$ with $\|A\|<N$, given values of $e_1, \ldots, e_{n-1}$, and $e_n$ in a given range.
	\begin{enumerate}
		\item[(a)] \emph{5 marks.} Let $e \in \N$. Give an upper bound for the number of subgroups of $(\Z/e\Z)^n$ of the form
		\[
		L^{\bmod e}(v) = \{ nv \mod e : 0\leq n < e \}   \qquad\qquad(v \in (\Z/e\Z)^n).
		\]
		(Notice that two different $v$ in $(\Z/e\Z)^n$ may lead to the same subgroup $L^{\bmod e}(v)$.)
	\end{enumerate}
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}

\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[(b)] \emph{5 marks.} Let $d<n$ and let  $e_i\in \N$ with $e_1\mid \dotsb \mid e_d$. Give an upper bound for the number of subgroups of $(\Z/e_d \Z)^n$ of the form
	\begin{multline*}
	L^{\bmod e_d}(e_1 v_1,\dotsc, e_d v_d) =\\
	\{ n_1 e_1 v_1+ \ldots + n_d e_d v_d \mod e_d : 0\leq n_i < e_d/e_i \} \\(v_i \in (\Z/e_de_i^{-1} \Z)^n).    
	\end{multline*}
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}

\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[(c)] \emph{10 marks.} Let $A$ be an $n\times n$ invertible real matrix with columns $a_1, \ldots, a_n$. You are given that, possibly after permuting the columns of $A$,
	\begin{multline*}
	a_n = x_1 a_1+\ldots+x_{n-1} a_{n-1} + v	
	\\
	(x_i\ll_n 1, \|v\| \ll \det(A)/\det (L(a_1,\ldots,a_{n-1})), v\cdot a_i =0).
	\end{multline*}
	(This is proved using ``singular value decomposition", which I will aim to discuss in lectures; it is a special case of the perhaps unenlightening Lemma 5.6 in \href{https://doi.org/10.1007/s00208-022-02547-w}{this paper}.)
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[(c)] \emph{10 marks.} Let $A$ be an $n\times n$ invertible real matrix with columns $a_1, \ldots, a_n$. You are given that, possibly after permuting the columns of $A$,
	\begin{multline*}
	a_n = x_1 a_1+\ldots+x_{n-1} a_{n-1} + v	
	\\
	(x_i\ll_n 1, \|v\| \ll \det(A)/\det (L(a_1,\ldots,a_{n-1})), v\cdot a_i =0).
	\end{multline*}
	Recall that if $\lambda_n(\Lambda) < 1$, then $|\Lambda \cap B(0,1)| \ll_n 1/\det(\Lambda)$.
	
	Let $L\subseteq \Z^n$ be a rank $n$ lattice and let $N,D>1$. Show that the number of a $n\times n$ invertible matrices $A$, with $\|A\|<N$, $|\det A|\leq D$, and columns belonging to $L$, is
	\[
	\ll_n \frac{D}{\det L} (N^n/\det L)^{n-1}.
	\]
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}

\begin{frame}
\end{frame}

\begin{frame}
\bigskip\bigskip
\begin{enumerate}
\item[(d)]\emph{5 marks.} Putting the last two parts together, give an upper bound for the number of invertible integer matrices $A$ with $\|A\|<N$, given values of $e_1, \ldots, e_{n-1}$, and $e_n$ in a given range.
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[2.] This is a continuation of question 1.
	\begin{enumerate}
		\item[(a)] \emph{5 marks.} Fix matrices $A$ and $B$, and let $\det_k(A)$ be the largest $k\times k$ subdeterminant in the first $k$ rows of $A$, that is
		\[
		\det\nolimits_k(A) = \max \{ |\det (A_{ij})_{i\in I, 1\leq j \leq k}| : I\subset \{1,\ldots,n\}, |I|=k \}.
		\]
		Show that
		\begin{multline*}
		\measure\{\alpha\in \Mat^{\Sym}_d(\R): \|tA  \alpha-B\| <1/N\} \ll_n \\ (tN)^{-n(n+1)/2} |\det(A)|^{-1}\prod_{1\leq k<n} \det\nolimits_j(A)^{-1}.
	\end{multline*}
	\end{enumerate}
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}

\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[(b)]\emph{20 marks.} Now let $A, a_i$ and $L$ be as in part 1c again. Show that for $N,D,D_k>1$, the number of an $n\times n$ invertible matrices $A$, with $\|A\|<N$, $|\det A|\leq D$, columns belonging to $L$, and every $k\times k$ subdeterminant in the first $k$ rows of $A$ of size at most $O(D_k)$, is
	\[
	\ll_n \frac{D}{\det L} \prod_{k=1}^{n-1} \frac{N^{n-k}D_k}{\det (L)}.
	\]
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}

\begin{frame}
\end{frame}

\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[3.]
The questions above give some way to count the number of $A$, and to estimate the volume of the $\alpha$'s. It remains to count the number of $B$. This will also reveal why we were concerned with the elementary divisors in question 1.

To simplify the problem, we’ll strengthen the condition $\|tA  \alpha-B\| <1/N$ to $tA \alpha = B$. Suppose $A$ is an invertible $d\times d$ integer matrix. Define
\[
\Lambda_A = ( A^{-1}\Mat_{d\times d}(\Z) )\cap \Mat_d^{\Sym}(\R).
\]
Observe that
\[
\#\{B \in \Mat_{d\times d}(\Z) : \exists \alpha\in \Mat^{\Sym}_d(\R): \|\alpha\|<1 ,tA  \alpha=B\}
=
|\Lambda_A \cap B(0,t)|.
\]
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[3.]
	\begin{enumerate}
		\item[(a)]
	\emph{15 marks.} Suppose that $e_1=\dotsb=e_{d-1}=1$, so that $e_d=\det(A)$.
	Show that
	\[
	A^{-1}\Mat_{d\times d}(\Z) = L(E_{11},\ldots,E_{dd},G)
	\]
	where  $E_{11},E_{12},\ldots,E_{dd}$ is a basis of $\Mat_d^{\Sym}(\Z)$, and $G_{ij} = V_{id}U_{dj}/\det(A)$. [\dots]
\end{enumerate}
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}

\begin{frame}
\bigskip\bigskip
	\begin{enumerate}
		\item[(a)] [\dots]
		\[
		A^{-1}\Mat_{d\times d}(\Z) = L(E_{11},\ldots,E_{dd},G)
		\]
		where  $G_{ij} = V_{id}U_{dj}/\det(A)$.Hence give, in terms of $A$,
		\begin{enumerate}
			\item[i.] an upper bound for the index $[\Lambda_A : \Mat_d^{Sym}(\Z)]$,
			\item[ii.] lower bounds for the Minkowski minima of $\Lambda$, and
			\item[iii.] upper bounds for $|\Lambda_A \cap B(0,t)|$, in terms of $A$.
		\end{enumerate}
	\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}


\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[(b)]  \emph{10 marks.}  Now we will drop the assumption that $e_1=\dotsb=e_{d-1}=1$, so that $e_i$ could be any natural numbers with $e_1\mid \dotsb \mid e_d$ and $e_1 \dotsm e_d = \det(A)$. Give a set of generators for $\Lambda_A$. Hence give bounds (i)-(iii) as above.
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}


\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[4.] This is a continuation of question 3.
	\begin{enumerate}
		\item[(a)] \emph{15 marks.} Let $A$ be an invertible $d\times d$ integer matrix with $\|A\|<N$. Using the results of question 3, what upper bounds can you give for
		\[
		\{B \in \Mat_{d\times d}(\Z) : \exists \alpha \in \Mat^{\Sym}_d(\R) \text{ s.t. } \|t A \alpha-B\|_2 <1/N\}?
		\]
\end{enumerate}
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}


\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[(b)] \emph{10 marks.} Let us think now about matrices in $A^{-1}\Mat_{d\times d}(\Z)$ which are not symmetric, but which are close to a symmetric matrix.
	
	If there is $M \in A^{-1}\Mat_{d\times d}(\Z)$ with $\|M-M^T\| < \|A\|^{-1} N^{-1-\eps}$, what does this say about $A$?
	
	Does it seem that for typical $A$ there is likely to be such an $M$?
	
	Can you improve your bound in part (a)?
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}


\begin{frame}
\bigskip\bigskip
\begin{enumerate}
	\item[5.] \emph{25 marks.} Suppose that $A$ has rank $r<n$, so $A$ is an integer matrix with $\|A\|<N$, $\det(A)=0$, and elementary divisors $e_1\mid \ldots\mid e_r \neq 0$ and $e_{r+1}=\dotsb=e_d=0$. What upper bounds can you give for
	\[
	\{B \in \Mat_{d\times d}(\Z) : \exists \alpha \in \Mat^{\Sym}_d(\R) \text{ s.t. } \|t A \alpha-B\|_2 <1/N\}?
	\]
\end{enumerate}
\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip\bigskip
\end{frame}

\begin{frame}
\end{frame}


\begin{frame}
\end{frame}


\begin{frame}
\end{frame}


\begin{frame}
\end{frame}


\end{document}