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.

Posted in Uncategorized | Leave a Comment »

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.

Posted in Uncategorized | Leave a Comment »