Sets of Natural Numbers with Proscribed Subsets

Kevin O’Bryant^{1} Department of Mathematics College of Staten Island (CUNY) Staten Island, NY 10314 USA

                 kevin@member.ams.org

Abstract

Let A be a set of subsets of the natural numbers, and let G_{A}(n) be the maximum cardinality of a subset of {1, 2, …, n} that does not have any subsets that are in A. We consider the general problem of giving upper bounds on G_{A}(n), and give new results for some 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, ar, as, ars}.

1 Introduction

Let A be a collection of subsets of the natural numbers (ℕ := {1, 2, … } and [n] := {1, 2, …, n}), which we call the proscribed sets, and let S_{A} be the collection of sets of natural numbers that do not have any subsets that are an element of A. Many of the most notorious problems in combinatorial number theory can be expressed as asking for properties of the elements of S_{A}. For example, let

AP_{k} := {{a, a + d, a + 2d, …, a + (k − 1)d} : a ∈ ℕ, d ∈ ℕ},

1Support for this project was provided by a PSC-CUNY Award, jointly funded by The Professional Staff Congress and The City University of New York.

and S_{AP_{k}} is the collection of k-free sets of natural numbers. Let

IDON := {{a, b, c, d} : a < b ≤ c < d, a + d = b + c},

and S_{IDON} is the collection of Sidon sets. Although there are exceptions, most of the problems of this sort that have been studied over the past 50 years concern affinely invariant A, i.e., if A ∈ A, then so is d ∗ A + t = {da + t : a ∈ A}.

Recently, a number of works concerning sets that do not contain any k-term geometric progressions have appeared. Specifically, let

GP_{k} := {a ∗ {1, r, r^{2}, …, r^{k−1}} : a ∈ ℕ, 1 ≠ r ∈ ℕ}

and

ĜP_{k} := {a ∗ {1, r, r^{2}, …, r^{k−1}} : a ∈ ℕ, 1 ≠ r ∈ ℚ_{+}}.

Further, for each set X ⊆ ℕ define

G_{A}(X) := max{|A| : A ∈ S_{A}, A ⊆ X}.

Some examples are already in the OEIS. The sequence of least N with G_{AP_{k}}([N]) = n, which we call a Szemerédi number, is given in \underline{A003002}, \underline{A003003}, \underline{A003004}, \underline{A003005} for various k. The least N for which G_{IDON} ([N]) = n is \underline{A003022}. We will generate upper bounds on G_{GP_{k}}([n]) and G_{ĜP_{k}}([n]) (sequences \underline{A259026} and \underline{A208746} for k = 3) in terms of other well-known Ramsey numbers, including Szemerédi numbers, density Hales-Jewett numbers (\underline{A156989}) and Moser numbers (\underline{A003142}). Then, we turn our attention to some other forbidden sets.

2 Statement of main result

We call F_{0}, F_{1}, F_{2}, … a grading of [n] if

1. F_{0} = {{1}, {2}, …, {n}} is the collection of all singletons,

2. each F_{i} is a collection of pairwise disjoint subsets of [n],

3. for each i, and for each f_{i} ∈ F_{i}, f_{i+1} ∈ F_{i+1}, either f_{i} ⊆ f_{i+1} for f_{i} ∩ f_{i+1} = ∅,

4. for each i, and for each f, g in F_{i}, we have G_{A}(f) = G_{A}(g).

If additionally

5. for each i, each f ∈ F_{i+1} is the disjoint union of exactly k members of F_{i},

then we say that the grading has expansion k. If instead 6. for each i and each f_{i+1} ∈ F_{i+1}, there is f_{i} ∈ F_{i} and r distinct elements with f_{i+1} = f_{i}∪

{x_{1}, …, x_{r}}, and none of x_{1}, …, x_{r} are contained in any member of any of F_{1}, …, F_{i},

then we say that the grading has growth r. Whenever we set a particular grading, we assume that F_{0} is what Condition (1) requires, and that F_{d} = ∅ for any d we don’t expressly set.

Theorem 1. Let A be a collection of proscribed sets, and let F_{0}, F_{1}, … be a grading of [n] with expansion k ≥ 2, and let R_{i} ≥ G_{A}(f_{i}) for f_{i} ∈ F_{i}. Then

\frac{G_{A}([n])}{n} ≤ 1 − ∑_{i=1}^{∞}(kR_{i−1} − R_{i}) \frac{|F_{i}|}{n}.

Theorem 2. Let A be a collection of proscribed sets, and let F_{0}, F_{1}, … be a grading of [n] with growth r ≥ 1, and let R_{i} ≥ G_{A}(f_{i}) for f_{i} ∈ F_{i}. Then

\frac{G_{A}([n])}{n} ≤ 1 − ∑_{i=1}^{∞}(r + R_{i−1} − R_{i}) \frac{|F_{i}|}{n}.

Observe that if a grading has expansion greater than 2 or growth greater than 1, then F_{d} = ∅ for sufficiently large d. Consequently, the infinite sums in the above theorems are, for each particular n, actually finite. Also, observe that the quantities kR_{i−1} − R_{i} and r + R_{i−1} − R_{i} are guaranteed to be nonnegative under the hypotheses of the theorems, so that the upper bounds in the above theorems are valid even if the infinite sums are truncated.

3 Corollaries

3.1 Geometric progressions with prime-power ratio

Let p be a prime, and k ≥ 3, and let

A = {a ∗ {1, p^{s}, p^{2s}, …, p^{(k−1)s}} : a ∈ ℕ, s ∈ ℕ},

the geometric progressions of length k whose ratio is a power of p. Let

F_{i} = {b ∗ {1, p, …, p^{i}} : (p, b) = 1, 1 ≤ b ≤ n/p^{i}}.

This is a grading of [n] with growth 1. As a geometric progression in {b, pb, …, p^{i}b} is an arithmetic progression in the exponents 0, 1, …, i, we have G_{A}(f) = r_{k}(i+1) for each f ∈ F_{i}, where r_{k}(n) is the maximum size of a subset of [n] that does not contain k-term arithmetic progressions. As |F_{i}| = \frac{n}{p^{i}} \frac{φ(p)}{p} + O(1) for 1 ≤ i ≤ log_{p} n, and |F_{i}| = 0 for i > log_{p} n, Theorem 2 now gives the bound

\frac{G_{A}([n])}{n} ≤ 1 − ∑_{i=1}^{⌊log_{p}(n)⌋}(1 + r_{k}(i − 1) − r_{k}(i)) \frac{\frac{n}{p^{i}} \frac{φ(p)}{p} + O(1)}{n}

≲ 1 − (1 − \frac{1}{p}) ∑_{i=1}^{∞} \frac{1 + r_{k}(i − 1) − r_{k}(i)}{p^{i}}.

Nathanson and O’Bryant [5] showed that this upper bound is asymptotically sharp (fixed p, with n → ∞) 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) ≤ n − ⌊n/k⌋, while by Szemerédi’s theorem, r_{k}(n) = o(n). Therefore, there is a least n with r_{k}(n) < n − ⌊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 multiplicative structure of k and k − 1.

3.2 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 citeMcNew, 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_{1} < s_{2} < … be the natural numbers whose prime factors are among 2 = p_{1}, p_{2}, …, p_{d} (the first d prime numbers, with product P_{d}). Let A^{(d)} be the set of 3-term geometric progressions whose ratio is among s_{2}, s_{3}, . . .. McNew takes

F_{i} = {b ∗ {s_{1}, s_{2}, …, s_{i+1}} : (b, P_{d}) = 1, 1 ≤ b ≤ n/s_{i+1}},

which defines a grading with growth 1. As

|F_{i}| ≈ \frac{φ(P_{d})}{P_{d}} \frac{n}{s_{i+1}} ,

Theorem 2 gives

\frac{G_{A^{(d)}}([n])}{n} ≲ 1 − \frac{φ(P_{d})}{P_{d}} ∑_{i=1}^{∞} \frac{1 + R_{i−1} + R_{i}}{s_{i+1}} ,

where R_{i} is the largest possible size of a subset of {1, s_{2}, s_{3}, …, s_{i+1}} that does not contain any 3-term geometric progression. McNew shows further that this bound is asymptotically sharp, and that as d → ∞ this bound approaches the answer to the problem in the next subsection (for k = 3).

3.3 Geometric progressions with integer ratio

Consider A = GP_{k}, k ≥ 3, and let

F_{1} = {a ∗ {1, 2, 2^{2}, …, 2^{k−1}} : 1 ≤ a ≤ n/2^{k−1}, (a, 2) = 1},

Then R_{0} = 1, R_{1} = G_{GP_{k}}({1, 2, 2^{2}, …, 2^{k−1}}) = k − 1, |F_{1}| = ⌊n/2^{k} + 1/2⌋, and Theorem 1 gives

\frac{G_{GP_{k}}([n])}{n} ≤ 1 − (k − (k − 1))\frac{⌊n/2^{k} + 1/2⌋}{n} ≤ 1 − 2^{−k} + o(1).

This replicates the bound given by Brown [2].

Let

F_{1} = \{a2^{k(ℓ−1)} ∗ \{1, 2, 2^{2}, …, 2^{k−1}\} : 1 ≤ ℓ ≤ \frac{1 + log_{2} n}{k}, 1 ≤ a ≤ n/2^{kℓ−1}, (a, 2) = 1\}.

As above, we have R_{0} = 1, R_{1} = k − 1, and

|F_{1}| = ∑_{ℓ=1}^{(1+log_{2} n)/k} ⌊\frac{n}{2^{kℓ}} + \frac{1}{2}⌋ = \frac{n}{2^{k} − 1} + O(log n),

whence Theorem 1 gives

\frac{G_{GP_{k}}([n])}{n} ≤ 1 − \frac{1}{2^{k} − 1} + o(1).

This replicates the bound given by Riddell [10], and rediscovered by Beiglböck et al. [1].

Now, we go further, providing the first example of the power of Theorem 1 and giving our first original corollary. Denote the sequence of prime numbers as 2 = p_{1} < p_{2} < p_{3} < …, and let P_{d} := ∏_{i=1}^{d} p_{i} and

a_{d} := {∏_{i=1}^{d} p_{i}^{e_{i}} : 0 ≤ e_{i} < k} .

We set up our grading with expansion k as follows: F_{0} = {{b} : 1 ≤ b ≤ n}, and for d ≥ 1

F_{d} := \{2^{k(ℓ−1)}b ∗ a_{d} : 1 ≤ ℓ ≤ 1 + \frac{log_{2}(n/P_{d}^{k−1})}{k}, 1 ≤ b ≤ \frac{n}{P_{d}^{k−1}2^{k(ℓ−1)}} , (b, P_{d}) = 1\} .

Before continuing, we must establish that this is actually a grading. Condition (1) is immediate. The smallest element of 2^{k(ℓ−1)}b ∗ a_{d} is 2^{k(ℓ−1)}b ≥ 1 and the largest element is

2^{k(ℓ−1)}bP_{d}^{k−1} ≤ 2^{k(ℓ−1)} · \frac{n}{P_{d}^{k−1}2^{k(ℓ−1)}} P_{d}^{k−1} = n,

which establishes that every member of F_{d} is a subset of [n]. Fix d ≥ 1, and suppose that

x ∈ 2^{k(ℓ_{1}−1)}b_{1} ∗ a_{d} ∩ 2^{k(ℓ_{2}−1)}b_{2} ∗ a_{d}.

Let v_{p}(x) be the highest exponent of p that divides x. As x ∈ 2^{k(ℓ_{1}−1)}b_{1} ∗ a_{d}, we see that k(ℓ_{1} − 1) ≤ v_{2}(x) < k(ℓ_{1} − 1) + k − 1, and likewise k(ℓ_{2} − 1) ≤ v_{2}(x) < k(ℓ_{2} − 1) + k. Therefore, ℓ_{1} = ℓ_{2}, and so we have

\frac{x}{2^{k(ℓ−1)}} = b_{1} ∏_{i=1}^{d} p_{i}^{e_{i}} = b_{2} ∏_{i=1}^{d} p_{i}^{e′_{i}}.

As (b, P_{d}) = 1, we observe that b_{1} = b_{2}, and then that e_{i} = e′_{i} for each i. In other words, the members of F_{d} are pairwise disjoint, confirming condition (2). Conditions (3) and (5) are both settled by the observation that

2^{k(ℓ−1)}b ∗ a_{d} = ⋃_{i=0}^{k−1} 2^{k(ℓ−1)}(bp_{d}^{i}) ∗ a_{d−1},

and so each member of F_{i+1} is the disjoint union of exactly k members of F_{i}. Condition (4) follows from the observation that GP_{k} is closed under dilation, and so

G_{GP_{k}}(2^{k(ℓ−1)}b ∗ a_{d}) = G_{GP_{k}}(a_{d}).

Suppose that x_{1}, …, x_{k} is a geometric progression in a_{d}, with integer ratio

r = \frac{x_{2}}{x_{1}} = ∏_{i=1}^{d} p_{i}^{r_{i}}

with at least one r_{i} > 0, and all r_{i} ≥ 0. As x_{k} = x_{1}r^{k−1} ∈ a_{d}, we see that no r_{i} > 1. In particular, the sequence of d-tuples

(v_{p_{1}}(x_{i}), v_{p_{2}}(x_{i}), …, v_{p_{d}}(x_{i})), (1 ≤ i ≤ 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, …, k − 1}^{d}, and each combinatorial line in {0, 1 …, k − 1}^{d} is generated by a geometric progression in a_{d}. As in the Polymath 1 project [8], we denote the largest possible size of a subset of {0, 1 …, k − 1}^{d} that does not contain a combinatorial line as c_{d,k}. To wit,

G_{GP_{k}}(a_{d}) = c_{d,k}.

For each value of ℓ, F_{d} has one member for each b between 1 and _{\frac{n}{P_{d}^{k−1}2^{k(ℓ−1)}}} that is relatively prime to P_{d}. The proportion of numbers relatively prime to P_{d} is φ(P_{d})/P_{d}, and so there are

\frac{n}{P_{d}^{k−1}2^{k(ℓ−1)}} \frac{φ(P_{d})}{P_{d}} + O(P_{d}) = n\frac{φ(P_{d})}{P_{d}^{k}} · \frac{1}{2^{k(ℓ−1)}} + O(1)

such values of b. Summing this over ℓ, with M := 1 + log_{2}(n/P_{d}^{k−1})/k, yields

|F_{d}| = ∑_{ℓ=1}^{M} (n\frac{φ(P_{d})}{P_{d}^{k}} · \frac{1}{2^{k(ℓ−1)}} + O(1))

= n \frac{φ(P_{d})}{P_{d}^{k}} ∑_{ℓ=1}^{M} \frac{1}{2^{k(ℓ−1)}} + O(log n)

= n \frac{φ(P_{d})}{P_{d}^{k}} \frac{2^{k}}{2^{k} − 1} + O(log n).

Theorem 1 gives

\frac{G_{GP_{k}}([n])}{n} ≤ 1 − \frac{2^{k}}{2^{k} − 1} ∑_{d=1}^{∞}(kc_{d−1,k} − c_{d,k})\frac{φ(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.

Corollary 3. Let G_{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

lim sup_{n→∞} \frac{G_{GP_{k}}([n])}{n} ≤ 1 − \frac{2^{k}}{2^{k} − 1} ∑_{d=1}^{∞}(kc_{d−1,k} − c_{d,k})\frac{φ(P_{d})}{P_{d}^{k}},

where P_{d} is product of the first d primes, φ is Euler’s phi function, and c_{d,k} are the density Hales-Jewett numbers.

The density Hales-Jewett theorem states that c_{d,k} = o(k^{d}) (with k fixed, d → ∞), and the recent Polymath project [8] found c_{d,3} for d ≤ 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 ≤ c_{7,3} ≤ 1348,

which is \underline{A156989} in the OEIS. Using these values, we get

lim sup_{n→∞} \frac{G_{GP_{3}}([n])}{n} < 1 − \frac{8}{7} (1 \frac{φ(2)}{2^{3}} + 2 \frac{φ(2 · 3 · 5 · 7)}{(2 · 3 · 5 · 7)^{3}} + 6 \frac{φ(2 · 3 · 5 · 7 · 11)}{(2 · 3 · 5 · 7 · 11)^{3}}) < 0.857131.

Assorted other useful values were also computed [6, 7] for k > 3:

c_{4,4} = 183, c_{5,4} ≤ 732, c_{4,6} ≤ 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 lim sup_{n} \frac{G_{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 ∉ {3, 4, 6}.

3.4 Geometric progressions with rational ratio

As GP_{k} ⊆ ĜP_{k}, we know that

G_{ĜP_{k}}(X) ≤ G_{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, …, k − 1}^{d}. The appropriate structure is called a geometric line: the k distinct points x_{i} ∈ {0, 1, …, 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, …, k − 1}^{d} that contains no geometric lines is denoted c′_{d,k} and were also studied in the Polymath [8] 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 \underline{A003142}.

Corollary 4. Let G_{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

lim sup_{n→∞} \frac{G_{GP_{k}}([n])}{n} ≤ 1 − \frac{2^{k}}{2^{k} − 1} ∑_{d=1}^{∞}(kc′_{d−1,k} − c′_{d,k})\frac{φ(P_{d})}{P_{d}^{k}},

where P_{d} is product of the first d primes, φ is Euler’s phi function, and c′_{d,k} are the Moser numbers.

With k = 3, this improves the previous best bound of 6/7 to

lim sup_{n→∞} \frac{G_{ĜP_{3}}([n])}{n} < \frac{6}{7} − \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 kc′_{d−1,k} − c′_{d,k} must be positive.

3.5 Geometric squares

A geometric square is a set of 4 natural numbers of the form {a, ar, as, ars : a, r, s ∈ ℕ}; set

A = {a ∗ {1, r, s, rs} : a, r, s ∈ ℕ, 1 < r < s}.

We note that for each n, the set

(n ∗ (\frac{1}{6}, 1]) ∩ ℕ

does not contain any geometric squares, and is a subset of [n] with cardinality ∼ (5/6)n.

Let 2 = p_{1} < p_{2} < ⋯ be the prime numbers, P_{d} := ∏_{i=1}^{d} p_{i}, and set

a_{d} := {∏_{i=1}^{d} p_{i}^{e_{i}} : 0 ≤ e_{i} ≤ 1} .

We now define the grading (leaving the details to the reader)

F_{d} := {b4^{i} ∗ a_{d} : (b, P_{d}) = 1, 1 ≤ b ≤ n/(P_{d} · 4^{i}), 0 ≤ i ≤ log_{4}(n/P_{d})}.

This grading has expansion 2 and

|F_{d}| = ∑_{i=0}^{log_{4}(n/P_{d})} (\frac{n}{P_{d} · 4^{i}} \frac{φ(P_{d})}{P_{d}} + O(1))

= n\frac{φ(P_{d})}{P_{d}^{2}} \frac{4}{3} + O(log n).

The Ramsey numbers G_{A}(a_{d}), which we will denote as c_{d,2,2}, deserved to have been studied before, but we are not aware of any such computation. In particular, c_{d,2,2} is the greatest number c for which there is a family of c subsets of [d], no four of which have the relations A_{1} ⊂ A_{2} ⊂ A_{4}, A_{1} ⊂ A_{3} ⊂ A_{4}. More generally, we would set c_{d,s,2} would be the maximum cardinality of a family of subsets of [d] that does not contain a sub-family that is lattice isomorphic to the power set of [s]. Sperner’s theorem is equivalent to the assertion that c_{d,1,2} = \binom{d}{⌊d/2⌋}. Even more generally, c_{d,s,k} is the maximum cardinality of a subset of [k]^{d} that does not contain a combinatorial space with dimension s.

We report the following values:

c_{0,2,2} = 1, c_{1,2,2} = 2, c_{2,2,2} = 3, c_{3,2,2} = 6, c_{4,2,2} = 11, c_{5,2,2} = 21.

Theorem 1 now gives us a clean bound.

Corollary 5. Let G_{A}([n]) be the largest possible size of a subset of [n] that does not contain any subset of the form {a, ar, as, ars} with a, r, s being natural numbers with 1 < r < s. Then

\frac{5}{6} ≤ lim sup_{n→∞} \frac{G_{A}([n])}{n} ≤ \frac{3699337}{4002075} < 1 − \frac{4}{3} ∑_{d=1}^{∞}(2c_{d−1,2,2} − c_{d,2,2})\frac{φ(P_{d})}{P_{d}^{2}},

where P_{d} is product of the first d primes, φ is Euler’s phi function, and c_{d,2,2} are the generalized Sperner numbers defined above.

We are unaware if there a subset of ℕ that avoids A and has positive density.

4 Proof of main result

We prove Theorem 1, and leave the similar, and slightly easier, proof of Theorem 2 to the reader. First, note that since the grading has expansion at least 2, every member of F_{d} must have size at least 2^{d} and be subsets of [n]; thus F_{d} = ∅ for d > log_{2} n. In particular, the infinite sum in the statement of the theorem is actually a finite sum.

For each b ∈ [n], let δ(b) be the largest d such that there is A ∈ F_{d} with b ∈ A, and let A_{b} be the unique set with b ∈ A_{b} ∈ F_{δ(b)}. The function δ(b) is well defined as b ∈ {b} ∈ F_{0} (condition 1), and F_{d} = ∅ for sufficiently large d, and A_{b} is well-defined as F_{δ(b)} is a collection of disjoint subsets of [n] (condition 2). Moreover, observe that if A_{b}, A_{c} are not identical, then they have no intersection. For otherwise, if x ∈ A_{b} ∩ A_{c}, then by Condition (2), δ(b) ≠ δ(c), say δ(b) < δ(c). By the expansion property, A_{c} is the disjoint union of k members of F_{δ(c)−1}, and by induction is the disjoint union of k^{δ(c)−δ(b)−1} members of F_{δ(b)+1}. One of those members must contain x, and so by condition 3, must contain all of A_{b}. In particular, b ∈ A_{c}, whence δ(b) ≥ δ(c) and so A_{b} = A_{c}.

Thus, the family

P := {A_{b} : b ∈ [n]}

is a partition of [n]. Let α_{i} be the number of members of P that are in F_{i}. For disjoint sets X, Y, we have

G_{A}(X ∪ Y) ≤ G_{A}(X) + G_{A}(Y).

Applying this principle to the partition P, we have

G_{A}([n]) ≤ ∑_{A∈P} G_{A}(A) ≤ ∑_{i=0}^{log_{2} n} α_{i}R_{i},

using condition 4. By high-school algebra, we have

∑_{i=0}^{log_{2} n} α_{i}R_{i} = R_{0} ∑_{i=0}^{log_{2} n} k^{i}α_{i} − ∑_{i=1}^{log_{2} n}(kR_{i−1} − R_{i}) ∑_{j=i}^{log_{2} n} k^{j−i}α_{j}.

Note now that

R_{0} ≤ 1,  ∑_{i=0}^{log_{2} n} k^{i}α_{i} = |F_{0}| = n,  ∑_{j=i}^{log_{2} n} k^{j−i}α_{j} = |F_{i}|,

and the Theorem is proved.

5 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, …, 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 − ⌊n/k⌋?

Is there a subset of ℕ 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} ⊂ A_{2} ⊂ A_{4}, A_{1} ⊂ A_{3} ⊂ A_{4}?

References

[1] M. Beiglböck, V. Bergelson, N. Hindman, and D. Strauss, Multiplicative structures in additively large sets, J. Combin. Theory Ser. A 113 (2006), 1219–1242.

[2] B. E. Brown and D. M. Gordon, On sequences without geometric progressions, Math. Comp. 65 (1996), 1749–1754.

[3] N. McNew, On sets of integers which contain no three terms in geometric progression,

preprint, 2014. Available at http://nathanmcnew.com/GPFsets.pdf.

[4] M. B. Nathanson and K. O’Bryant, On sequences without geometric progressions, Integers 13 (2013), Paper A73.

[5] M. B. Nathanson and K. O’Bryant, Irrational numbers associated to sequences without geometric progressions, Integers 14 (2014), Paper A40.

[6] D. H. J. Polymath, Higher dimensional DHJ numbers, 2013, available at

http://tinyurl.com/oorlqat.

[7] D. H. J. Polymath, Upper and lower bounds, 2013, available at

http://michaelnielsen.org/polymath1/index.php?title=Upper_and_lower_bounds.

[8] D. H. J. Polymath, Density Hales-Jewett and Moser numbers, in An Irregular Mind, Bolyai Soc. Math. Stud., Vol. 21, János Bolyai Math. Soc., 2010, pp. 689–753.

[9] R. A. Rankin, Sets of integers containing not more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A 65 (1960/1961), 332–344.

[10] J. Riddell, Sets of integers containing no n terms in geometric progression, Glasgow Math. J. 10 (1969), 137–146.

2010 Mathematics Subject Classification: Primary 11B05; Secondary 11B25, 11B75, 11B83, 05D10. Keywords: geometric progression-free sequence, Ramsey theory.

(Concerned with sequences \underline{A003002}, \underline{A003003}, \underline{A003004} \underline{A003005}, \underline{A003022}, \underline{A003142}, \underline{A156989}, \underline{A208746}, and \underline{A259026}.)

Received October 18 2014; revised versions received June 12 2015; June 30 2015; July 12 2015. Published in Journal of Integer Sequences, July 16 2015.

Return to Journal of Integer Sequences home page.