%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-37/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem*{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{fact}{Fact}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{remark}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}


\title{The Uniform Density of Sets of Integers and Fermat's Last Theorem}
\author{Tom C. Brown and Allen R. Freedman}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown and A.R. Freedman, \emph{The uniform density of sets of integers and Fermat's Last
  Theorem}, C.R. Math. Rep. Acad. Sci. Canad. \textbf{12} (1990), 1--6.}\bigskip\end{center}

\section{Introduction} \label{sec: 1}

In this note we take a ``density theory" approach to the problem of measuring certain sets of integers including the set of exponents for which Fermat's Last Theorem is true. It is proved that this last set has \emph{uniform} density equal to one. This is a slightly stronger statement than has been previously made about this set. The method is particularly simple and transparent and is applied to finding the uniform densities of other sets of integers from Number Theory.

\section{Density concepts} \label{sec: 2}

Let $B$ be a set of positive integers and write $B(x,y)$ for the number of elements in $B \cap [x,y]$. The lower and upper uniform densities are defined as follows. Let 
\[ \beta_s = \liminf_{t \to \infty} B(t + 1,t + s). \]
That is, $\beta_s$ is the smallest number which occurs infinitely often as the number of elements of $B$ which lie in an interval of length $s$. It is not hard to show that $\lim_{ s \to \infty} \beta_s/s$ exists, and this is the \emph{lower uniform density} of $B$, denoted by $\underline{u}(B)$:
\[ \underline{u}(B) = \lim_{s \to \infty} \frac{1}{s} \liminf_{t \to \infty} B(t + 1, t + s). \]
Similarly, with 
\[ \beta^s = \limsup_{t \to \infty} B(t + 1, t + s), \]
the \emph{upper uniform density} of $B$ is $\overline{u}(B) = \lim_{s \to \infty} \beta^s/s$, or 
\[ \overline{u}(B) = \lim_{s \to \infty} \frac{1}{s} \limsup_{t \to \infty} B(t + 1, t + s). \]
If $\underline{u}(B) = \overline{u}(B) = u(B)$, then $u(B)$ is the \emph{(natural) uniform density} of $B$.

With this notation the definitions of the \emph{lower asymptotic density} $\underline{d}(B)$ and the \emph{upper asymptotic density} $\overline{d}(B)$ are respectively 
\[ \underline{d}(B) = \liminf_{s \to \infty} \frac{1}{s} B(1,s), \]
and 
\[ \overline{d}(B) = \limsup_{s \to \infty} \frac{1}{s} B(1,s). \]
If $\underline{d}(B)= \overline{d}(B) = d(B)$, then $d(B)$ is the \emph{(natural) asymptotic density} of $B$/

It's clear that 
\[ \underline{u}(B) \leq \underline{d}(B) \leq \overline{d}(B) \leq \overline{u}(B) \]
for any set $B$, and it is easy to produce an example of a set $B$ with $d(B) = 1$ and $\underline{u}(B) = 0$, and a set $C$ with $d(C) = 0$ and $\overline{u}(C) = 1$. Thus the statement that a set has uniform density $1$ (or uniform density $0$) is in fact stronger than the corresponding statement about asymptotic density. As another example, let $S$ be the set of square-free integers. It is well known that $d(S) = 6/\pi^2$ while it can easily be shown that $\underline{u}(S) = 0$ and $\overline{u}(S) = d(S)$.

We mention three important properties of these densities which can be proved without difficulty directly from the definitions: 1) If $A \subset B$, then $\delta(A) \leq \delta(B)$ where $\delta$ stands for any of the density functions defined above. 2) For either upper density, $\bar{\delta}$, and any sets $A$ and $B$, $\bar{\delta}(A \cup B) \leq \bar{\delta}(A) + \bar{\delta}(B)$. 3) If $B$ is a union of disjoint arithmetic progressions, 
\[ B= \bigcup_{i=1}^n \{a_it + i: t = 0,1,2,\dots\}, \]
then $u(B)$ exists and equals $\frac{1}{a_1} + \frac{1}{a_2} + \cdots + \frac{1}{a_n}$.

\section{Three lemmas} \label{sec: 3} 

Let $P = \{p_1 < p_2 < p_3 < \cdots\}$ be the set of prime numbers and let $N_k = \{x: x$ is not divisible by $p_1,p_2,\dots,p_k\}$. More generally, if $Q = \{q_1,q_2,\dots,q_k\}$ is a set of distinct primes, then let $N_Q = \{x: x$ is not divisible by $q_1,q_2,\dots,q_k\}$. For any set $S$ and integer $n$ write $S_n$ for the set of all $x \in S$ which are divisible by $n$. We begin with a well known computation.

\begin{lemma} \label{lemma: 1} 
$u(N_Q) = (1 - \frac{1}{q_1})(1 - \frac{1}{q_2}) \cdots (1 - \frac{1}{q_k})$.
\end{lemma}

\begin{proof} Let $R = q_1q_2\cdots q_k$. Evidently, $N_Q$ is the disjoint union of the arithmetic progressions $\bigcup_a\{Rt + a\}$ where $a$ ranges over the $\phi(R)$ elements of $[1,R]$ which are prime to $R$. Hence 
\[ u(N_Q) = \frac{\phi(R)}{R} = (1 - \frac{1}{q_1})(1 - \frac{1}{q_2})\cdots (1 - \frac{1}{q_k}). \qedhere \]
\end{proof}

\begin{lemma} \label{lemma: 2}
Let $Q = \{q_1,q_2,q_3,\dots\}$ be a set of primes for which
\begin{equation} \sum \frac{1}{q_i} = \infty. \label{eq: 1} \end{equation}
Let $S$ be a set of positive integers and suppose that $u(S_q) = 0$ for each prime $q$ in $Q$. Then $u(S) = 0$.
\end{lemma}

\begin{proof} Let $Q_k = \{q_1,q_2,\dots,q_k\}$. Then, for each $k$,
\[ S \subset N_{Q_k} \cup S_{q_1} \cup S_{q_2} \cup \cdots \cup S_{q_k}. \]
Hence,
\begin{align*} \overline{u}(S) &\leq \overline{u}(N_{Q_k}) + \overline{u}(S_{q_1}) + \cdots + \overline{u}(S_{q_k}) = \overline{u}(N_{Q_k}) \\
&= (1 - \frac{1}{q_1})(1 - \frac{1}{q_2}) \cdots (1 - \frac{1}{q_k}).
\end{align*}
As the last product tends to zero as $k \to \infty$, the lemma is proved.
\end{proof}

\begin{lemma} \label{lemma: 3}
$u(S) = 0$ if and only if there exists a set of primes $Q$ with infinite reciprocal sum, such that for any sequence $(q_1,q_2,\dots)$ of distinct elements of $Q$, $u(S_{q_1q_2\cdots q_k}) = 0$ for some $k$.
\end{lemma}

\begin{proof} If $u(S) = 0$, the conclusion is obvious with $Q = P$. On the other hand, if $\overline{u}(S) > 0$ and $Q$ is any set of primes satisfying~(\ref{eq: 1}), then, using Lemma~\ref{lemma: 2}, we can find $q_1$ in $Q$ such that $\overline{u}(S_{q_1}) > 0$. Again, since $(S_p)_q = S_{pq}$ for distinct primes $p$ and $q$, and using Lemma~\ref{lemma: 2}, we can find $q_2$ in $Q - \{q_1\}$ such that $\overline{u}(S_{q_1q_2}) > 0$. Continuing in this mander we construct the required infinite sequence such that $\overline{u}(S_{q_1q_2\cdots q_k}) > 0$ for all $k$.
\end{proof}

\section{Applications} \label{sec: 4}

Before moving on to Fermat's last theorem we prove striking properties concerning the number of prime factors of a ``typical" integer (cf.~\cite{hardy+wright1960} Sections 22.11, 22.12).

\begin{thm} \label{thm: 1}
$u(P) = 0$.
\end{thm}

\begin{proof} Take $S = P$ in Lemma~\ref{lemma: 2}. Each $S_p$ is a singleton.
\end{proof}

\begin{thm} \label{thm: 2}
Let $G^t = \{x: x$ is the product of no more than $t$ prime numbers (counting multiplicities)$\}$. Then $u(G^t) = 0$.
\end{thm}

\begin{proof} $G^1 = P \cup \{1\}$ and so $u(G^1) = 0$. Proceeding inductively, 
\[ (G^{t + 1})_p = pG^t \quad \textup{and so} \quad u((G^{t + 1})_p) = 0. \]
By Lemma~\ref{lemma: 2} $u(G^{t + 1}) = 0$. (Here we use $kA = \{kx: x \in A \}$ and the fact that $\overline{u}(kA) = \frac{1}{k}\overline{u}(A)$.)
\end{proof}

Using Lemma~\ref{lemma: 3} we can prove the more difficult result presented in the next theorem.

\begin{thm} \label{thm: 3} 
Let $H^t = \{x: x$ has $t$ or fewer prime divisors$\}$. Then $u(H^t) = 0$.
\end{thm}

\begin{proof} Fix $t$, take $Q = P$, and let $q_1,q_2,\dots,q_{t + 1}$ be any $t + 1$ distinct primes. Clearly, $(H^t)_{q_1q_2\cdots q_{t + 1}}$ is empty and we may apply Lemma~\ref{lemma: 3}.
\end{proof}

Finally, we prove that the set of exponents, $F$, for whic Fermat's Last Theorem is \emph{false} has uniform density zero. Faltings' Theorem~\cite{faltings1983} implies that for each odd prime $p$ the equation $x^p + y^p = z^p$ has only \emph{finitely many} primitive solutions, and recently Heath-Brown~\cite{heath-brown1985} and Granville~\cite{granville1985} have shown independently as a corollary to Faltings' Theorem that the set $T$ of exponents $n$ for which $x^n + y^n = z^n$ has \emph{no} primitive solution (and hence no solution at all in positive integers) has \emph{natural asymptotic} density 1. Of course, the idea behind our proof is also the use of Faltings' Theorem for prime exponents $p$. Both Heath-Brown and Granville attribute this idea to Filaseta~\cite{filaseta1984}.

\begin{thm} \label{thm: 4}
Let $F$ be the set of all $n$ such that $x^n + y^n = z^n$ has a solution. Then $u(F) = 0$.
\end{thm}

\begin{proof} Fix any odd prime $p$. Then for each $n \geq 3$, 
\[ \left\{ \begin{matrix} \textup{$p$ divides $n$} \\ a^n + b^n = c^n \\ (a,b,c) = 1 \end{matrix} \right\} \Rightarrow \left\{ \begin{matrix} (a^{n/p})^p + (b^{n/p})^p = (c^{n/p})^p \\ (a^{n/p}, b^{n/p}, c^{n/p}) = 1 \end{matrix} \right\}, \]
and so, by Faltings' Theorem, each odd prime $p$ divides only finitely many elements of $F$ (since $a^{n/p}$ must assume at most finitely many values with $a > 1$). Therefore $F_p$ is finite and so, by Lemma~\ref{lemma: 2}, $F$ has uniform density $0$.
\end{proof}

It is apparently still unknown whether or not Fermat's Last Theorem is true for an infinite set of prime exponents. Filaseta proved that for any $n \geq 3$, Fermat's Last theorem is true for exponent $kn$ for all large $k$. The proof of this can be gleened from the proof of Theorem~\ref{thm: 4}. It is interesting to note that with this result we can easily construct a sequence of products of two primes, $q_1q_2, q_3q_4, q_5q_6,\dots$, such that Fermat's Last Theorem is true for each member of the sequence and each prime $p$ equals exactly one $q_i$.


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}