\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{mathtools}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\newcommand{\NN}{\ensuremath{\mathbb N}}
\newcommand{\QQ}{\ensuremath{\mathbb Q}}
\newcommand{\scA}{{\mathcal A}}
\newcommand{\scF}{{\mathcal F}}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\dfloor}[1]{ \left\lfloor #1 \right \rfloor }
\newcommand{\gpk}{\ensuremath{\text{GP}_k}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\def\modd#1 #2{#1\ ({\rm mod}\ #2)}
\begin{center}
\vskip 1cm
{\LARGE\bf {Sets of Natural Numbers \\
\vskip .1in
with Proscribed Subsets}}
\vskip 1cm
\large
Kevin O'Bryant\footnote{Support for this project was provided by a PSC-CUNY Award,
jointly funded by The Professional Staff Congress and The City
University of New York.}\\
Department of Mathematics \\
College of Staten Island (CUNY)\\
Staten Island, NY 10314\\
USA\\
\href{mailto:kevin@member.ams.org}{\tt kevin@member.ams.org}
\end{center}
\vskip .2 in
\begin{abstract}
Let $\mathcal{A}$ be a set of subsets of the natural numbers, and let
$G_{\mathcal{A} }(n)$ be the maximum cardinality of a subset of
$\{1,2,\dots,n\}$ that does not have any subsets that are in $\mathcal{A}$.
We consider the general problem of giving upper bounds on $G_{\mathcal{A} }(n)$, and give new results for some $\mathcal{A} $ that are closed under dilation. We specifically address some examples, including sets that do not contain geometric progressions of length $k$ with integer ratio, sets that do not contain geometric progressions of length $k$ with rational ratio, and sets of integers that do not contain multiplicative squares, i.e., sets of the form $\{a,a r,a s,a r s\}$.
\end{abstract}
\section{Introduction}
Let $\scA$ be a collection of subsets of the natural numbers
($\NN\coloneqq \{1,2,\dots\}$ and $[n]\coloneqq \{1,2,\dots,n\}$), which we call the
{\em proscribed sets}, and let $S_{\scA}$ be the collection of sets of
natural numbers that do not have any subsets that are an element of $\scA$. Many of the most notorious problems in combinatorial number theory can be expressed as asking for properties of the elements of $S_{\scA}$. For example, let
\[ {\mathcal{AP}}_k \coloneqq \big\{ \{a,a+d,a+2d,\dots,a+(k-1)d\} : a\in \NN, d \in \NN \big \}, \]
and $S_{{\mathcal{AP}}_k}$ is the collection of $k$-free sets of natural numbers. Let
\[{\mathcal {IDON}} \coloneqq \big\{ \{a,b,c,d\} : a**\log_p n$, Theorem~\ref{thm:main2} now gives the bound
\begin{align*}
\frac{G_{\scA}([n])}{n}
&\leq 1 - \sum_{i=1}^{\floor{\log_p(n)}} (1+r_k(i-1)-r_k(i)) \frac{\frac{n}{p^i}\frac{\varphi(p)}{p}+O(1)}{n} \\
&\lesssim 1- \left(1-\frac 1p\right) \sum_{i=1}^\infty \frac{1+r_k(i-1)-r_k(i)}{p^i}.
\end{align*}
Nathanson and O'Bryant \cite{OBryant} showed that this upper bound is asymptotically sharp (fixed $p$, with $n\to\infty$) and, perhaps surprisingly, is provably an irrational number.
We note that a set that avoids $k$-term arithmetic progressions cannot have $k$ consecutive elements, and so $r_k(n) \leq n - \floor{n/k}$, while by Szemer\'{e}di's theorem, $r_k(n)=o(n)$. Therefore, there is a least $n$ with $r_k(n)< n-\floor{k/n}$, and this value gives the improvement over ``easy'' in the above bound. We are not aware of any work explicitly aimed at finding this $n$, and some computations suggest that it depends on the {\em multiplicative} structure of $k$ and $k-1$.
\subsection{Three-term geometric progressions with friable integer ratio, McNew's method}
During preparation of this work, the author became aware of recent work of N. McNew cite{McNew}, a small portion of which fits into this framework. We give here just the facts with little justification, and leave the interested reader to seek out McNew's work.
Let $1=s_10$, and all $r_i\geq 0$. As $x_k=x_1 r^{k-1}\in a_d$, we see that no $r_i >1$. In particular, the sequence of $d$-tuples
$$ \big(v_{p_1}(x_i), v_{p_2}(x_i), \dots, v_{p_d}(x_i) \big),\qquad (1\leq i \leq k)$$
has some coordinates fixed, while the others count in unison from 0 up to $k-1$. That is, they are a combinatorial line in $\{0,1,\dots,k-1\}^d$, and each combinatorial line in $\{0,1\dots,k-1\}^d$ is generated by a geometric progression in $a_d$. As in the Polymath 1 project~\cite{Polymath}, we denote the largest possible size of a subset of $\{0,1\dots,k-1\}^d$ that does not contain a combinatorial line as $c_{d,k}$. To wit,
\[
G_{{\mathcal{GP}}_k}(a_d) = c_{d,k}.
\]
For each value of $\ell$, $\scF_d$ has one member for each $b$ between 1 and $\frac{n}{P_d^{k-1}2^{k(\ell-1)}}$ that is relatively prime to $P_d$. The proportion of numbers relatively prime to $P_d$ is $\varphi(P_d)/P_d$, and so there are
$$
\frac{n}{P_d^{k-1}2^{k(\ell-1)}} \, \frac{\varphi(P_d)}{P_d} + O(P_d) = n \frac{\varphi(P_d)}{P_d^k} \cdot \frac{1}{2^{k(\ell-1)}}+ O(1)
$$
such values of $b$. Summing this over $\ell$, with $M\coloneqq 1+\log_2(n/P_d^{k-1})/k$, yields
\begin{align*}
|\scF_d| &= \sum_{\ell=1}^M \left( n \frac{\varphi(P_d)}{P_d^k} \cdot \frac{1}{2^{k(\ell-1)}}+ O(1) \right) \\
&=n\, \frac{\varphi(P_d)}{P_d^{k}}\sum_{\ell=1}^M \frac{1}{2^{k(\ell-1)}} + O(\log n) \\
&=n \, \frac{\varphi(P_d)}{P_d^{k}} \, \frac{2^k}{2^k-1} + O(\log n).
\end{align*}
Theorem~\ref{thm:main} gives
\[
\frac{G_{{\mathcal{GP}}_k}([n])}{n} \leq 1 - \frac{2^k}{2^k-1} \sum_{d=1}^\infty ( k c_{d-1,k} - c_{d,k}) \frac{\varphi(P_d)}{P_d^{k}}+o(1).
\]
By the density Hales-Jewett theorem infinitely many of the $kc_{d-1,k}-c_{d,k}$ are positive. This bound is superior to any in the literature (the previous best corresponds to taking only the first term of the sum), and so we state it explicitly.
\begin{corollary}
Let $G_{{\mathcal{GP}}_k}([n])$ be the largest possible size of a subset of $[n]$ that does not contain any $k$-term geometric progression with integer ratio. Then
\[
\limsup_{n \to \infty} \frac{G_{{\mathcal{GP}}_k}([n])}{n}
\leq 1 - \frac{2^k}{2^k-1} \sum_{d=1}^\infty ( k c_{d-1,k} - c_{d,k}) \frac{\varphi(P_d)}{P_d^{k}},
\]
where $P_d$ is product of the first $d$ primes, $\varphi$ is Euler's phi function, and $c_{d,k}$ are the density Hales-Jewett numbers.
\end{corollary}
The density Hales-Jewett theorem states that $c_{d,k} = o(k^d)$ (with $k$ fixed, $d\to\infty$), and the recent Polymath project~\cite{Polymath} found $c_{d,3}$ for $d\leq 6$:
\[c_{0,3}=1,c_{1,3}=2, c_{2,3}=6, c_{3,3}=18, c_{4,3}=52, c_{5,3}=150, c_{6,3}=450, 1302\leq c_{7,3} \leq 1348,\]
which is \seqnum{A156989} in the OEIS. Using these values, we get
\[
\limsup_{n \to \infty} \frac{G_{{\mathcal{GP}}_3}([n])}{n}
< 1 - \frac 87 \left(1\, \frac{\varphi(2)}{2^3}+ 2\, \frac{\varphi(2\cdot3\cdot5\cdot 7)}{(2\cdot 3 \cdot 5 \cdot 7)^3}
+ 6 \, \frac{\varphi(2\cdot3\cdot5\cdot 7\cdot 11)}{(2\cdot 3 \cdot 5 \cdot 7\cdot 11)^3} \right) < 0.857131.
\]
Assorted other useful values were also computed \cite{HigherDimDHJ,UpperAndLowerDHJ} for $k>3$:
\[c_{4,4}=183, c_{5,4}\leq 732, c_{4,6}\leq 1079,\]
although these calculations were not subjected to the same scrutiny and should be considered less reliable. They lead to positive, albeit numerically miniscule, improvements on the previously known bounds for $\limsup_n \frac{G_{{\mathcal{GP}}_k}([n])}{n}$ for $k=4$ and $k=6$. By the density Hales-Jewett theorem, infinitely many of the $kc_{d-1,k}-c_{d,k}$ are positive, and so this gives an improvement for all $k$, even though we are unable assess the magnitude of the improvement for $k\not\in \{3,4,6\}$.
\subsection{Geometric progressions with rational ratio}
As ${\mathcal{GP}}_k \subseteq \widehat{\mathcal{GP}}_k$, we know that
\[G_{\widehat{\mathcal{GP}}_k}(X) \leq G_{{\mathcal{GP}}_k}(X) \]
for any $X$, and so the bounds of the previous section apply here, too. We can do a bit better, however, because not every geometric progression with rational ratio in $a_d$ lands on a combinatorial line in $\{0,1,\dots,k-1\}^d$. The appropriate structure is called a geometric line: the $k$ distinct points $x_i \in \{0,1,\dots,k-1\}^d$ are a geometric line if the coordinates fall into three categories, one where the coordinate value never changes, one where the coordinate value counts up from 0 to $k-1$, and one (possibly empty) where the coordinate value counts down from $k-1$ to 0. The largest possible size of a subset of $\{0,1,\dots,k-1\}^d$ that contains no geometric lines is denoted $c'_{d,k}$ and were also studied in the Polymath~\cite{Polymath} project:
\[c'_{0,3}=1,c'_{1,3}=2, c'_{2,3} = 6,c'_{3,3} = 16,c'_{4,3} = 43,c'_{5,3} = 124,c'_{6,3} = 353,\]
which calls this the sequence of Moser numbers \seqnum{A003142}.
\begin{corollary}
Let $G_{{\mathcal{GP}}_k}([n])$ be the largest possible size of a subset of $[n]$ that does not contain any $k$-term geometric progression with integer or rational ratio. Then
\[
\limsup_{n \to \infty} \frac{G_{{\mathcal{GP}}_k}([n])}{n}
\leq 1 - \frac{2^k}{2^k-1} \sum_{d=1}^\infty ( k c'_{d-1,k} - c'_{d,k}) \frac{\varphi(P_d)}{P_d^{k}},
\]
where $P_d$ is product of the first $d$ primes, $\varphi$ is Euler's phi function, and $c'_{d,k}$ are the Moser numbers.
\end{corollary}
With $k=3$, this improves the previous best bound of $6/7$ to
\[
\limsup_{n \to \infty} \frac{G_{\widehat{\mathcal{GP}}_3}([n])}{n} < \frac 67 - \frac{16755239936}{23695945898625} < 0.856436.
\]
We don't know any nontrivial Moser numbers with $k>3$, although the density Hales-Jewett theorem implies that infinitely many of the $k c'_{d-1,k} - c'_{d,k}$ must be positive.
\subsection{Geometric squares}
A geometric square is a set of 4 natural numbers of the form $\{a,ar,as,ars: a,r,s \in \NN\}$; set
\[
\scA=\big\{ a \ast \{1,r,s,rs\} : a,r,s \in \NN, 1 \log_2 n$. In particular, the infinite sum in the statement of the theorem is actually a finite sum.
For each $b\in [n]$, let $\delta(b)$ be the largest $d$ such that there is $A\in \scF_d$ with $b\in A$, and let $A_b$ be the unique set with $b\in A_b \in \scF_{\delta(b)}$. The function $\delta(b)$ is well defined as $b\in \{b\} \in \scF_0$ (condition~\ref{Cond:F_0}), and $\scF_d=\emptyset$ for sufficiently large $d$, and $A_b$ is well-defined as $\scF_{\delta(b)}$ is a collection of disjoint subsets of $[n]$ (condition~\ref{Cond:F_i packs}). Moreover, observe that if $A_b,A_c$ are not identical, then they have no intersection. For otherwise, if $x\in A_b \cap A_c$, then by Condition (\ref{Cond:F_i packs}), $\delta(b)\not= \delta(c)$, say $\delta(b)<\delta(c)$. By the expansion property, $A_c$ is the disjoint union of $k$ members of $\scF_{\delta(c)-1}$, and by induction is the disjoint union of $k^{\delta(c)-\delta(b)-1}$ members of $\scF_{\delta(b)+1}$. One of those members must contain $x$, and so by condition~\ref{Cond:F_i unrefines}, must contain all of $A_b$. In particular, $b \in A_c$, whence $\delta(b)\geq \delta(c)$ and so $A_b=A_c$.
Thus, the family
\[ {\mathcal P} \coloneqq \big\{ A_b : b\in [n] \big\} \]
is a partition of $[n]$. Let $\alpha_i$ be the number of members of ${\mathcal P}$ that are in $\scF_i$. For disjoint sets $X,Y$, we have
\[ G_{\scA}(X \cup Y) \leq G_{\scA}(X) + G_{\scA}(Y). \]
Applying this principle to the partition ${\mathcal P}$, we have
\[ G_{\scA}([n]) \leq \sum_{A \in {\mathcal P}} G_{\scA}(A) \leq \sum_{i=0}^{\log_2 n} \alpha_i R_i, \]
using condition~\ref{Cond:Ramsey}. By high-school algebra, we have
\[ \sum_{i=0}^{\log_2 n} \alpha_i R_i = R_0 \sum_{i=0}^{\log_2 n} k^i \alpha_i- \sum_{i=1}^{\log_2 n} (k R_{i-1}-R_i)\sum_{j=i}^{\log_2 n} k^{j-i} \alpha_j. \]
Note now that
\[ R_0 \leq 1, \qquad \sum_{i=0}^{\log_2 n} k^i \alpha_i = |\scF_0| = n, \qquad \sum_{j=i}^{\log_2 n} k^{j-i} \alpha_j = |\scF_i|, \]
and the Theorem is proved.
\section{Remaining problems}
Aside from the obvious ``sharpen the given bounds'' problems, we single out 3 interesting problems.
Let $r_k(n)$ be the largest possible size of a subset of $\{1,2,\dots,n\}$ that does not have a subset that is a $k$-term arithmetic progression. For each $k$, what is the least $n$ with $r_k(n) < n-\floor{n/k}$?
Is there a subset of $\NN$ that has positive density and does not contain a subset of the form $\{a,ar,as,ars\}$, where $a,r,s$ are natural numbers and $r,s$ are both greater than $1$?
Is there a clean formula for $c_{d,2,2}$, the maximum size of a family of subsets of $[d]$ that does not contain 4 sets $A_1,A_2,A_3,A_4$ with $A_1 \subset A_2 \subset A_4,A_1\subset A_3 \subset A_4$?
\begin{thebibliography}{99}
\bibitem{Beiglbock}
M. Beiglb{\"o}ck, V. Bergelson, N. Hindman, and D. Strauss,
Multiplicative structures in additively large sets, \textit{J. Combin.
Theory Ser. A} \textbf{113} (2006), 1219--1242.
\bibitem{Brown}
B. E. Brown and D. M. Gordon, On sequences without geometric
progressions, \textit{Math. Comp.} \textbf{65} (1996), 1749--1754.
\bibitem{McNew}
N. McNew, On sets of integers which contain no three terms in geometric
progression, preprint, 2014. Available at
\url{http://nathanmcnew.com/GPFsets.pdf}.
\bibitem{Nathanson}
M. B. Nathanson and K. O'Bryant, On sequences without geometric progressions, \textit{Integers} \textbf{13} (2013), Paper A73. Available at
\url{http://www.integers-ejcnt.org/vol13.html}.
\bibitem{OBryant}
M. B. Nathanson and K. O'Bryant, {Irrational numbers associated to sequences without geometric progressions}, \textit{Integers} \textbf{14} (2014), Paper A40.
Available at \url{http://www.integers-ejcnt.org/vol14.html}.
\bibitem{HigherDimDHJ}
D. H. J. Polymath, Higher dimensional DHJ numbers, 2013,
available at \url{http://tinyurl.com/oorlqat}.
\bibitem{UpperAndLowerDHJ}
{D. H. J. Polymath}, {Upper and lower bounds}, 2013, available at \\
\url{http://michaelnielsen.org/polymath1/index.php?title=Upper_and_lower_bounds}.
\bibitem{Polymath}
D. H. J. Polymath, Density Hales-Jewett and Moser numbers, in
\textit{An Irregular Mind}, {Bolyai Soc. Math. Stud.}, Vol.~21,
{J\'{a}nos Bolyai Math. Soc.}, 2010, pp.\ 689--753.
\bibitem{Rankin}
{R. A. Rankin}, {Sets of integers containing not more than a given
number of terms in arithmetical progression}, \textit{Proc. Roy. Soc.
Edinburgh Sect. A} \textbf{65} (1960/1961), 332--344.
\bibitem{Riddell}
J. Riddell, {Sets of integers containing no $n$ terms in geometric
progression}, \textit{Glasgow Math. J.} \textbf{10} (1969), {137--146}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary
11B05; Secondary 11B25, 11B75, 11B83, 05D10.
\noindent \emph{Keywords:} geometric progression-free sequence, Ramsey theory.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A003002},
\seqnum{A003003},
\seqnum{A003004}
\seqnum{A003005},
\seqnum{A003022},
\seqnum{A003142},
\seqnum{A156989},
\seqnum{A208746}, and
\seqnum{A259026}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received October 18 2014;
revised versions received June 12 2015; June 30 2015; July 12 2015.
Published in {\it Journal of Integer Sequences}, July 16 2015.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
**