'Obvious' Remarks

This page contains explanations pertaining to the "'Obvious Remarks'" section of Roth's paper.

Alternative definition of A-set

$A(x)$ is equal to the greatest number of integers that can be selected from $x$ consecutive terms of an arithmetic progression to form an $\mathcal{A}$-set

This is easy to see by taking $x$ consecutive terms in arithmetic progression:

(1)

\begin{align} \mathcal{A}_1 = \left\{ a+bu_1, a+bu_2, \ldots, a+bu_x \right\} \end{align}

and corresponding them to $x$ consecutive integers

(2)

\begin{align} \mathcal{A}_2 = \left\{ u_1, u_2, \ldots, u_x\right\}. \end{align}

Then as $(a+bu_k) - (a+bu_l) = b(u_k-u_l)$ we see that a three-term sequence in $\mathcal{A}_1$ is arithmetic if and only if the corresponding three term sequence in $\mathcal{A}_2$ is arithmetic.

A(x+y) is less than A(x)+A(y)

For any two positive integers $x$ and $y$ we have that $A(x+y) \leq A(x) + A(y)$.

First we recall the definition of $A(x+y)$:

(3)

\begin{align} A(x+y) = \max \{ |S| \mid S \subset \{1, 2, \ldots, x+y\}, S \text{ a } \mathcal{A}\text{-set} \} \end{align}

and similarly

(4)

\begin{align} A(x) = \max \{ |S| \mid S \subset \{1, 2, \ldots, x\}, S \text{ a } \mathcal{A}\text{-set} \}. \end{align}

We now apply the alternative definition of $A(y)$ to write

(5)

\begin{align} A(y) = \max \{ |S| \mid S \subset \{x+1, x+2, \ldots, x+y\}, S \text{ a } \mathcal{A}\text{-set} \}. \end{align}

Now let $S_1$ be a subset of $\{1, 2, \ldots, x+y\}$ that is a maximal $\mathcal{A}$-set, so that $|S_1| = A(x+y)$. Now a subset of an $\mathcal{A}$-set is definitely still an $\mathcal{A}$-set (if a set contains no three-term arithmetic progression, a subset of it cannot contain any either). We therefore have $S_1 \cap \{1, 2, \ldots, x\}$ being an $\mathcal{A}$-set contained in $\{1, 2, \ldots, x\}$. Therefore, from the definition of $A(x)$ we have

(6)

\begin{align} |S_1 \cap \{1, 2, \ldots, x\}| \leq A(x). \end{align}

Similarly, we have $S_1 \cap \{x+1, x+2, \dots, x+y\}$ being an $\mathcal{A}$-set contained in $\{x+1, x+2, \ldots, x+y\}$. From the alternative definition of $A(y)$ given in 5 we obtain

(7)

\begin{align} |S_1 \cap \{x+1, x+2, \ldots, x+y\}| \leq A(y). \end{align}

Finally we can combine 6 and 7 to get

(8)

\begin{eqnarray} A(x+y) &=& |S_1| \\ &=& |S_1 \cap \{1, \ldots, x\}| + |S_1 \cap \{x+1, \ldots, x+y\}|\\ &\leq& A(x) + A(y), \end{eqnarray}

as required.

A(x*y) is less than x*A(y)

For any two positive integers $x$ and $y$ we have $A(x \cdot y) \leq x \cdot A(y)$.

From the above lemma we know that

(9)

\begin{align} A(x \cdot y) \leq A(y) + A((x-1) \cdot y), \end{align}

and repeating $x$ times we see that

(10)

\begin{align} A(x \cdot y) \leq x \cdot A(y). \end{align}

Some upper bounds on A(x)

For any two positive integers $x$ and $y$ we have $A(x) \leq A\left( \left( \left[ \frac{x}{y} \right] \right) + 1 \right) \leq \frac{x+y}{y} \cdot A(y)$.

The first inequality follows as for positive $y$ we have

(11)

\begin{align} x \leq \left( \left[ \frac{x}{y}\right] + 1 \right) \cdot y \end{align}

and the function $A$ is non-decreasing.

The second inequality is a direct consequence from the above corollary upon noting that

(12)

\begin{align} \left( \left[ \frac{x}{y} \right] + 1 \right) \leq \frac{x+y}{y}. \end{align}

a(x*y) is less than a(y)

For any two positive integers $x$ and $y$ we have $a(x \cdot y) \leq a(y)$.

We now utilize the definition of the function $a(x)$ and the above corollary:

(13)

\begin{align} a(x \cdot y) = \frac{A(x \cdot y)}{x \cdot y} \leq \frac{x \cdot A(y)}{x \cdot y} = \frac{A(y)}{y} = a(y). \end{align}

An upper bound on a(x)

For any two positive integers $x$ and $y$ we have $a(x) \leq \left( 1 + \frac{y}{x} \right) \cdot a(y)$.

We now apply the upper bound on $A(x)$ to get

(14)

\begin{eqnarray} a(x) = \frac{A(x)}{x} &\leq& \frac{1}{x} \cdot \left( \frac{x+y}{y} \cdot A(y) \right)\\ &=& \left( \frac{1}{y} + \frac{1}{x} \right) \cdot A(y)\\ &=& \left(1 + \frac{y}{x} \right) \cdot \frac{A(y)}{y} = \left( 1 + \frac{y}{x} \right) \cdot a(y). \end{eqnarray}

A trivial bound on a(x)

For any positive integer $x$ we have $\frac{1}{x} \leq a(x) \leq 1$.

From the definition of $A(x)$ we see that $A(x)$ is the size of a non-empty subset of $\{1, 2, \ldots, x\}$ and so

(15)

\begin{align} 1 \leq A(x) \leq x. \end{align}

But we have $A(x) = x \cdot a(x)$ and so

(16)

\begin{align} 1 \leq x \cdot a(x) \leq x \end{align}

which, on division by the positive $x$, gives the desired result:

(17)

\begin{align} \frac{1}{x} \leq a(x) \leq 1. \end{align}