# Decomposition of sets without arithmetic progressions

This is consequence of my earlier post. I am not very happy with earlier replies of my post. I hope, I will get good response for this post. With lot of hope, I am sending the following problem and I want to learn the best from the experts. Please discuss/prove the following one. Thank you.

Let $A$ be a subset of $\{1,2, \dots,8\}$ containing no Arithmetic Progression. Then one of the following Two must be hold:

1. $|A \cap\{3, 5\}|\le 1$ and $|A \cap\{1, 2, 4, 6, 7, 8\}|\le 1$.
2. $|A \cap \{4, 6\}|\le 1$ and $|A \cap\{1, 2, 3, 5, 7, 8\}|\le 1$.

Let A be a subset of $\{1, 2, \dots,10\}$ containing no Arithmetic Progression. Then one of $|A \cap \{1, 2, \dots,7\}|$ and $|A \cap \{4, 5, \dots, 10\}|$ is at most $3$.

Let $A$ be a subset of $\{1,2,\dots,13\}$ containing no Arithmetic Progression. Then one of the following Two must be hold:

1. $|A \cap \{1, 2, 3, 4, 6\}|\le 3$ and $|A \cap \{5, 7, 8, 9, 10, 11, 12, 13\}|\le 4$.
2. $|A \cap\{8, 10, 11, 12, 13\}|\le 3$ and $|A \cap \{1, 2, 3, 4, 5, 6, 7, 9\}|\le 4$.

Thank you all.

-
This is not set theory. I will re-tag. – Gerry Myerson Nov 5 '11 at 2:23
In the last part of your question, don't you mean for $A$ to be a subset of $\lbrace1,2,\dots,13\rbrace$? – Gerry Myerson Nov 5 '11 at 2:26
By the way, you should include a link to your earlier question so we don't reinvent too many wheels here. – Gerry Myerson Nov 5 '11 at 2:29
It is generally a bad idea to use (non standard!) abbreviations in titles: it is impossible to know what the question is about from its title... You saved an infinitessimal amount of time writing «A.P.» and as a consequence lots of people (among who are those that will probably help you!) to lose time: when writing for others, one should be very mindful of their convenience... – Mariano Suárez-Alvarez Nov 5 '11 at 2:31
I am giving my previous post link below: math.stackexchange.com/questions/78474/… – mathew Nov 5 '11 at 8:50

Consider the set $A=\{1,3,7\}$, which admits no arithmetic progression. Then condition (1) is not met, as $A$ contains $1$ and $7$. Additionally, condition (2) is not met, as our set contains both $3$ and $7$. Thus, your first claim is refuted.

For your second claim, we first prove that such a set must contain at most $6$ elements. Of course, this would prove your claim immediately. It may help to arrange the numbers $1$ to $9$ as

$$\left(\begin{matrix} 1& 2& 3 \\4 & 5 & 6 \\ 7 & 8 &9 \end{matrix} \right)$$ A set $A$ without arithmetic progressions must not contain all the elements of any row or column. Thus $A$ contains at most $5$ elements of $1,2\ldots,9$. Our desired result is immediate. With more work, one may show that $A = \{1,2,4,8,9\}$ is a set free of arithmetic progressions with $\#(A \cap \{1,2,\ldots ,9\})=5$, and that it is unique in this respect. Two more (similarly obtained) sets are $B=\{1,2,4,5,10\}$ and $C=\{2,3,5,9,10\}$. These three sets exhaust those with maximal cardinality in $\{1,\ldots, 10\}$, so your necessary conditions in claim (2) could be tightened.

While ad hoc methods (or brute force search) will continue to be effective in these types of problems, I suggest that you formulate known results into `theorems' to make your techniques more wide-reaching. For example, one may readily generalize our work on claim (2) by considering $k \times 3$ matrices. In general, results that relate to the density of arithmetic-progression-free sets will serve you well. It is known that the density of such sets approaches $0$ as they increase in cardinality; this is Szemeredi's theorem. While this won't help you here, more constructive results of the same variety would be very useful.

-
WOW! good explanation, and thank you so much sir. – mathew Nov 5 '11 at 8:29
I don't follow "$A$ contains at most 5 elements of \$1,2,\dots,9." 1, 2, 4, 6, 8, 9 does not contain all the elements of any row or column (or diagonal!), yet it has 6 elements. True, it has an AP or two, but that's beside the point. – Gerry Myerson Nov 5 '11 at 8:42
Also, 1, 2, 4, 8, 9 is not unique; 1, 2, 6, 8, 9 is also a 5-subset of the 9-set free of APs. Also 1, 3, 4, 8, 9, and 1, 2, 6, 7, 9. – Gerry Myerson Nov 5 '11 at 8:45
Gerry Myerson@ Sir, Now I am in full confusion. Could you explain more clearly sir. – mathew Nov 5 '11 at 8:51
@mathew, sure - what would you like me to explain? – Gerry Myerson Nov 6 '11 at 4:43