## Archive for February, 2011

### Changing the measure

February 27, 2011

Roth’s function $g(n)$ is defined as the largest size of a subset of $\lbrace 1,2, \ldots ,n \rbrace$ without arithmetic progressions. We may “force” the arithmetic progressions into the measure, and instead of taking the usual measure $\mu(A)=|A|$ we may consider $\nu(A)=|A|-\begin{displaystyle}\sum_{T\in{\cal T}}c_T1_{T \subseteq A}\end{displaystyle}$ where $\cal T$ denotes the set of all AP’s in $\lbrace 1,2, \ldots ,n \rbrace$ and $1_{T \subseteq A}$ equals $1$ if $T \subseteq A$, $0$ otherwise, and the $c_T$ are constants. The advantage of doing this is that we now have an optimization problem on all subsets of $\lbrace 1,2, \ldots ,n \rbrace$ instead of the subsets without APs.
For example, we may take all the $c_T$‘s equal to $1$, but the extremal subsets (those which maximize $\nu$) do not appear to exhibit a very interesting structure. Perhaps there are better choices for the $c_T$ constants.

### Decomposing sets without arithmetic progressions

February 23, 2011

Let $A$ be a subset of $\lbrace 1,2, \ldots ,8 \rbrace$ containing no arithmetic progressions. Then one of the following two must hold :

(1) $|A \cap \lbrace 3,5 \rbrace | \leq 1$ and $|A \cap \lbrace 1,2,4,6,7,8 \rbrace | \leq 1$.

(2) $|A \cap \lbrace 4,6 \rbrace | \leq 1$ and $|A \cap \lbrace 1,2,3,5,7,8 \rbrace | \leq 1$.

Let $A$ be a subset of $\lbrace 1,2, \ldots ,10 \rbrace$ containing no arithmetic progressions. Then one of $|A \cap \lbrace 1,2, \ldots ,7 \rbrace|$ and $|A \cap \lbrace 4,5, \ldots ,10 \rbrace|$ is at most $3$.

Let $A$ be a subset of $\lbrace 1,2, \ldots ,13 \rbrace$ containing no arithmetic progressions. Then one of the following two must hold :

(1) $|A \cap \lbrace 1,2,3,4,6 \rbrace | \leq 3$ and $|A \cap \lbrace 5,7,8,9,10,11,12,13 \rbrace | \leq 4$.

(2) $|A \cap \lbrace 8,10,11,12,13 \rbrace | \leq 3$ and $|A \cap \lbrace 1,2,3,4,5,6,7,9 \rbrace | \leq 4$.