%%%% THIS FILE IS AUTOMATICALLY GENERATED %%%% DO NOT EDIT THIS FILE DIRECTLY, %%%% ONLY EDIT THE SOURCE, tom-46/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{corn}{Corollary to Lemma 1} \newtheorem{lemma}{Lemma} \newtheorem*{sub}{Sublemma} \newtheorem{thm}{Theorem} \newtheorem*{prop}{Proposition} \newtheorem{q}{Problem} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{fact}{Fact} \newtheorem*{claim}{Claim} \newtheorem{remark}{Remark} \newtheorem*{remarkk}{Remark} \newtheorem*{app}{Applications} \newtheorem*{conj}{Conjecture} \newcommand{\diam}[1]{\textup{Diam} #1} \title{Some Quantitative Aspects of Szemer\'edi's Theorem Modulo $n$} \author{T. C. Brown} \date{} \maketitle \begin{center}{\small {\bf Citation data:} T.C. Brown, \emph{Some quantitative aspects of Szemer\'edi's theorem modulo $n$}, congressus Numerantium \textbf{43} (1984), 169--174.}\bigskip\end{center} \begin{abstract} The multiset $P = \{a_1,\dots,a_k\}$ is a $k$-term arithmetic progression modulo $n$ if $a_1 \not\equiv a_2$ (mod $n$) and $a_2 - a_1 \equiv a_3 - a_2 \equiv \cdots \equiv a_k -a_{k-1}$ (mod $n$). For $k$ odd and $k \geq 3$, we find explicit constnats $\varepsilon_k< 1 - 1/k$ such that for any $n \ne k$ and for any subset $A$ of $[0,n-1]$, if $|A| > \varepsilon_k n$ then $A$ contains a $k$-term arithmetic progression modulo $n$. ($\varepsilon_3 =.5$ and $\varepsilon_5$ is about .77.) \end{abstract} \section{Introduction} \label{sec: 1} For each real number $\varepsilon > 0$ and positive integers $k$ and $n_0$, let $S(\varepsilon, k, n_0)$ denote the following statement. $S(\varepsilon, k, n_0)$: For every $n \geq n_0$, and for every subset $A$ of $[0,n-1]$, if $|A| > \varepsilon n$ then $A$ contains a $k$-term arithmetic progression. Then Szemer\'{e}di's theorem~\cite{szemeredi1975} asserts that for every $\varepsilon > 0$ and $k$, there exists a least positive integer $n_0 = n_0(\varepsilon,k)$ such that $S(\varepsilon,k,n_0)$ holds. One can ask the following quantitative questions. (Answering them, of course, is something else!) (a) Given $\varepsilon > 0$ and $k$, what is $n_0(\varepsilon, k)$, that is, what is the smallest $n_0$ such that $S(\varepsilon, k , n_0)$ holds? (b) Given $k$ and $n_0$, what is the smallest $\varepsilon$ such that $S(\varepsilon , k ,n_0)$ holds? (We may denote this smallest $\varepsilon$ by $\varepsilon (k, n_0)$.) These questions appear to be simplified if for a given $n$ and a given subset $A$ of $[0,n-1]$ we enlarge the set of arithmetic progressions under consideration. Thus we say that $A$ contains a \emph{$k$-term arithmetic progression modulo $n$} if $A$ contains elements $a_0,\dots,a_{k - 1}$ (not necessarily distinct) such that \[ a_j \equiv a_0 + jd \quad (\textup{mod }n), \quad 0 \leq j \leq k - 1, \] for some integer $d$ with \[ d \not\equiv 0 (\textup{mod }n). \] We can replace statement $S(\varepsilon, k , n_0)$ by the corresponding statement $M(\varepsilon', k, n_0')$, for any real number $\varepsilon'>0$ and positive integers $k$ and $n_0'$, as follows. $M(\varepsilon', k, n_0')$: For every $n \geq n_0'$, and for every subset $A$ of $[0,n-1]$, if $|A| > \varepsilon' n$ then $A$ contains a $k$-term arithmetic progression modulo $n$. One can then ask the following questions. (a') Given $\varepsilon ' > 0$ and $k$, what is $n_0'(\varepsilon , k)$, the smallest $n_0'$ such that $M(\varepsilon', k, n_0')$ holds? (b') Given $k$ and $n_0'$, what is $\varepsilon'(k,n_0')$, the smallest $\varepsilon '$ such that $M(\varepsilon', k, n_0')$ holds? In this note we obtain bounds what appear to be the easiest cases of these latter two questions. Given a small $\varepsilon > 0$ (namely $\varepsilon \leq \frac{1}{2}$) and arbitrary $k$, we find a lower bound for $n_0'(\varepsilon, k)$. (Theorem~\ref{thm: 1} below). Given a small $n_0'$ (namely $n_0' = k + 1$) and arbitrary \emph{odd} $k$, we find an upper bound for $\varepsilon' (k, n_0')$. (Theorem~\ref{thm: 2} below). \begin{remark} \label{remark: 1} It has been observed in~\cite{brown+buhler1984} that Szemer\'{e}di's theorem is equivalent to the following statemtn: For every $\varepsilon ' > 0$ and $k$, there exists a least positive integer $n_0'$ such that $M(\varepsilon', k, n_0')$ holds. \end{remark} (In fact, \[ n_0' (\varepsilon , k) \leq n_0 (\varepsilon , k) \leq \frac{1}{2} n_0'(\varepsilon/2, k) + \frac{1}{2}. \] To obtain the second inequality, let $2m \geq n_0'(\varepsilon/2, k)$, and let $A$ be any subset of $[0,m-1]$ such that $|A| > \varepsilon m = (\varepsilon/2)(2m)$. Then regarding $A$ as a subset of $[0,2m - 1]$ it follows from the choice of $2m$ that $A$ contains a $k$-term arithmetic progression modulo $2m$. Since $A$ is a subset of $[0,m-1]$, this $k$-term arithmetic progression modulo $2m$ is in fact a $k$-term arithmetic progression. Hence $n_0(\varepsilon, k) \leq m$.) \begin{remark} \label{remark: 2} It is trivial that for any $k $ and $n_0'$, $\varepsilon'(k,n_0') \leq 1 - 1/k$. \end{remark} (For if $A \subset [0,n-1]$ and $|A| > (1 - 1/k)n$, then the average value of $|A \cap [i, i + k - 1]|$ is greater than $1 - 1/k$, hence for some $i$, $A$ contains $i,i + 1, \dots,i + k - 1$ (modulo $n$). Note, however, that this argument fails for $\varepsilon(k,n_0)$: $A = \{0,1,3\} \subset [0,3]$ and $|A| > (1 - 1/3)\cdot 4$, but $A$ contains no $3$-term arithmetic progression.) \section{Results} \label{sec: 2} From now on, we abbreviate ``$k$-term arithmetic progression" to ``$k$-progression". \begin{thm} \label{thm: 1} For $s \geq 2, k \geq 3$, \begin{equation} n_0'(1/s,k) > \sqrt{2}s^{k/2} - 2s + 1. \label{eq: 1} \end{equation} \end{thm} \begin{proof} Fix $s \geq 2, k \geq 3$, and consider the $(m + 1)$-element subsets of $[0,ms]$. Note that $m + 1> (1/s)(ms + 1)$, so that if one of these subsets contains no $k$-progression modulo $ms + 1$, then $n_0'(1/s, k) > ms + 1$. Given a fixed $k$-progression $P$ (modulo $ms + 1$) in $[0,ms]$, the number of $(m + 1)$-element subsets of $[0,ms]$ which contain $P$ is at most $\binom{ms + 1 - k}{m + 1 - k}$. The total number of distinct $k$-progressions $P$ (modulo $ms + 1$) in $[0,ms]$ is at most $(ms + 1)(ms)/2$. Therefore \begin{equation} \binom{ms + 1 - k}{m + 1 - k}(ms + 1)(ms)/2 < \binom{ms + 1}{m + 1} \label{eq: 2} \end{equation} implies \begin{equation} n_0'(1/s,k) > ms + 1. \label{eq: 3} \end{equation} When $m + 1 \geq k$,~(\ref{eq: 2}) is equivalent to \begin{equation} m(m + 1) < 2\cdot \left(\frac{ms - 1}{m - 1} \right) \left( \frac{ms - 2}{m - 2} \right) \cdot \left( \frac{ms - k + 2}{m - k + 2} \right), \label{eq: 4} \end{equation} and each factor on the right hand side of~(\ref{eq: 4}) is greater than $s$. Therefore when $m + 1 \geq k$,~(\ref{eq: 2}) holnds provided $m (m + 1) \leq 2\cdot s^{k-2}$, which in turn holds provided $(m + 1)^2 \leq 2\cdot s^{k-2}$, or \begin{equation} m \leq \sqrt{2} s^{k/2 - 1} - 1. \label{eq: 5} \end{equation} Now when $k \leq \sqrt{2}s^{k/2 - 1}$, we can find an integer $m$ such that $k \leq m + 1 \leq \sqrt{2} s^{k/2 - 1}$ and $m > \sqrt{2} s^{k/2 - 1} -2$, which gives~(\ref{eq: 1}). Only a small number of pairs $(s,k)$ have $k > \sqrt{2}s^{k/2 - 1}$ (namely $(s,k) = (2,3)$, $(2,4)$, $(2,5)$, $(2,6)$, $(3,3)$, $(4,3))$, and these can be checked separately, giving~(\ref{eq: 1}) in all cases. \end{proof} \begin{thm} \label{thm: 2} Define the numbers $\varepsilon_k$, for odd $k \geq 3$, as follows. Let $\varepsilon_3 = 1/2$. For $k = 2m + 1$, $m\geq 2$, let \begin{equation} \varepsilon_k = 1 - \frac{k + 1}{k + 2} \left( \sqrt{m^2 + \frac{k + 2}{k + 1}} - m \right). \label{eq: 6} \end{equation} Then $\varepsilon_k < 1 - 1/k$, and for every $n \ne k$ and every subset $A$ of $[0,n-1]$, if $|A| > \varepsilon_k n$ then $A$ contains a $k$-progression modulo $n$. \end{thm} \begin{lemma} \label{lemma: 1} In proving Theorem~\ref{thm: 2}, we may assume that $n > k$. \end{lemma} \begin{proof}[Proof of Lemma~\ref{lemma: 1}] For $k = 3$, the assertion of the lemma is obviously true. For $k > 3$, one can check that $\varepsilon_k > 1 - 1/(k - 1)$. From this it follows that if $n < k$ and $A$ is any subset of $[0,n-1]$ such that $|A| > \varepsilon_k n$, then $A = [0,n-1]$ and hence $A$ contains a $k$-progression modulo $n$. \end{proof} \begin{lemma} \label{lemma: 2} In proving Theorem~\ref{thm: 2}, we may assume that $n$ is prime. \end{lemma} \begin{proof}[Proof of Lemma~\ref{lemma: 2}] Assume that if $p$ is prime, $A \subset [0,p-1]$, $|A| > \varepsilon_k p $, then $A$ contains a $k$-progression modulo $p$. Now let $n$ be arbitrary, let $A \subset [0,n-1]$, $|A| > \varepsilon_k n$, and let $p$ be a prime divisor of $n$. Identify $[0,n-1]$ with the cyclic group $Z_n$. Then $Z_n$ contains a copy $H$ of $Z_p$, and for some coset $a + H$ of $H$, $|A \cap (a + H)| > \varepsilon_kH$, or \begin{equation} |(A - a) \cap H| > \varepsilon_k p. \label{eq: 7} \end{equation} Therefore $A - a$ contains a $k$-progression as a subset of $H$; since $H$ is a subgroup of $Z_n$, this $k$-progression is a $k$-progression as a subset of $Z_n$. \end{proof} \begin{remarkk} The same argument shows that in Theorem~\ref{thm: 2}, $Z_n$ can be replaced by an arbitrary abelian group, except for $Z_p \times \cdots \times Z_p$ when $k = p = $prime. In particular, Theorem~\ref{thm: 2} is true even for $n = k$, provided $k $ is not prime. \end{remarkk} \begin{proof}[Proof of Theorem~\ref{thm: 2}] \begin{proof}[Case 1. The case $k = 3$] Let $p$ be prime, $p > 3$, $A \subset [0,p-1]$, $|A| = \alpha p$, and assume that $A$ contains no 3-progression modulo $p$. We need to show that $\alpha \leq 1/2$. For each pair $x,x + y$ ($y \ne 0$) of elements of $A$, the (distinct) elements $w_1 = x - y$, $w_2 = x + 2y$ are excluded from $A$, since $A$ contains no 3-progression modulo $p$. (All arithmetic operations here are modulo $p$.) Also, given distinct elements $w_1,w_2$ in $[0,p-1]$, there are unique $x,y$ ($y \ne 0$) in $[0,p-1]$ such that $x -y = w_1$ and $x + 2y = w_2$. It easily follows that each excluded pair $\{w_1,w_2\}$ is excluded only once, so that the $\binom{\alpha p}{2}$ pairs of elements of $A$ exclude $\binom{\alpha p }{2}$ distinct pairs $\{w_1,w_2\}$ from $A$. The union of these $\binom{\alpha p}{2}$ distinct pairs of elements has at least $\alpha p$ elements. Thus $\alpha p = |A| \leq p - \alpha p$, and $\alpha \leq 1/2$, as required. \end{proof} \begin{proof}[Case 2. The case $k > 3$] From now on, for convenience, we abbreviate ``$k$-progression modulo $p$" to ``$k$-progression". Let $k = 2m + 1$, $m \geq 2$. Let $p$ be prime, $p > k$, $A \subset [0,p -1]$, $|A| = \alpha p$, and assume that $A$ contains no $k$-progression. We need to show that $\alpha \leq \varepsilon_k$. (One can check directly that $\varepsilon_k < 1 - 1/k$. $\varepsilon_5$ is about 0.77.) The argument proceeds essentially as in the case $k = 3$: Each $(k - 1)$-progression contained in $A$ eliminates a pair $\{w_1,w_2\}$ of elements from $A$, and each eliminated pair $\{w_1,w_2\}$ is eliminated exactly once. Let $t$ be the number of $(k - 1)$-progressions contained in $A$. Then the union of the $t$ excluded pairs $\{w_1,w_2\}$ has at least $w$ elements, where $w$ is the smallest integer such that $\binom{w}{2} \geq t$. Then $w > \sqrt{2t}$, so that $\alpha p = |A| < p - \sqrt{2t}$, or \begin{equation} (1 - \alpha)^2 p^2 > 2t. \label{eq: 8} \end{equation} Now we estimate $t$ from below. The set $[0,p - 1] - A$ contains $(1 - \alpha)p$ elements, and each of these belong to exactly $m(p - 1)$ $(k-1)$-progressions. Thus $[0,p - 1] - A$ meets at most $(1-\alpha)pm(p - 1)$ $(k-1)$-progressions. Since the total number of $(k - 1)$-progressions contained in $[0, p -1]$ is exactly $p(p - 1)/2$, it follows that \[ t \geq p(p - 1)/2 - p(p - 1)(1 - \alpha) m, \] or \begin{equation} 2t \geq p( p -1)(1 - (1-\alpha)2m). \label{eq: 9} \end{equation} Combining~(\ref{eq: 9}) and~(\ref{eq: 8}) gives \begin{equation} \frac{(1 - \alpha)^2}{1 - (1 - \alpha)2m} > 1 - 1/p. \label{eq: 10} \end{equation} Since $p \geq k + 2 = 2m + 3$, this gives \begin{equation} \frac{(1 - \alpha)^2}{1 - (1 - \alpha)2m} > 1 - \frac{1}{2m + 3}. \label{eq: 11} \end{equation} Using $\alpha \leq 1$, it follows from~(\ref{eq: 11}) that $\alpha \leq \varepsilon_k$ as required. \end{proof} \end{proof} (When $k$ is even, all of the above remains valid except for $\varepsilon_k < 1 - 1/k$. Hence, according to Remark~\ref{remark: 2} above, the application of this method for even $k$ gives no result. Perhaps some modified version of this method will work for even $k$.) \bibliographystyle{amsplain} \bibliography{tom-all} \end{document}