# Smallest set such that all arithmetic progression will always contain at least a number in a set

Let $$S= \left\{ 1,2,3,...,100 \right\}$$ be a set of positive integers from $$1$$ to $$100$$. Let $$P$$ be a subset of $$S$$ such that any arithmetic progression of length 10 consisting of numbers in $$S$$ will contain at least a number in $$P$$. What is the smallest possible number of elements in $$P$$ ?

Denote $$|P|$$ as the number of elements in $$P$$. We shall find the smallest possible value of $$|P|$$.

For $$|P|=16$$, we have the answer by @RobertIsrael below.

However, for $$|P|<16$$, I can neither find such set $$P$$ nor prove that $$|P|$$ cannot be less than $$16$$. So my question is:

Is it true that $$|P| \geq 16$$? How can I prove it? If not, what is the minimum amount of elements in $$P$$ ?

Also, I am wondering that:

If we replace 10 with an even number $$n$$,and $$100$$ with $$n^2$$, can we find the minimum of $$|P|$$ ?

Any answers or comments will be appreciated. If this question should be closed, please let me know. If this forum cannot answer my question, I will delete this question immediately.

• it is not too unusual that questions here get answered, say, after a year, and not immediately. Jun 27 '19 at 6:24
• @DimaPasechnik Thanks. I just afraid that my question will be forgotten and cannot be answered. Jun 27 '19 at 7:02
• good questions don't get forgotten. they pop up in searches, etc. Jun 27 '19 at 8:21
• This can be considered as a set-covering problem. Although set covering is NP-complete, I suspect this one is within the reach of current technology. Jun 27 '19 at 12:37
• For the last question (replacing 10 with $n$), have you computed the optimal number for $n\le 9$ and checked the OEIS? Jun 27 '19 at 14:44

Considering the complement of $$P$$ in $$[1,100]$$, you are asking how large can a subset of $$[1,100]$$ be given that it does not contain any $$10$$-term arithmetic progression. The more general question

How large can a subset of $$[1,N]$$ be given that it does not contain any $$k$$-term arithmetic progression?

is one of the central problems in combinatorial number theory. There is no chance to give a precise answer, as an "explicit" function of $$N$$ and $$k$$, and it quite likely that this is impossible already in your special situation where $$N=n^2$$ and $$k=n$$.

Here is an argument showing that if $$P\subset[1,n^2]$$ meets every $$n$$-term progression contained in $$[1,n^2]$$, then $$|P|>n+n^{0.5+o(1)}$$. (See also the paragraph at the very end for the estimate $$|P|\ge 12$$ in your special case where $$P\subset[1,100]$$ and we want to block all $$10$$-term progressions.) It would be interesting to improve these estimates or at least to decide whether $$|P|>Cn$$ holds true with an absolute constant $$C>1$$.

Write $$K:=|P|$$, $$\Delta:=K-n$$, and $$P=\{p_1,\dotsc,p_K\}$$ where $$1\le p_1<\dotsb. Notice that $$p_1\le n$$ and $$p_K\ge n^2-(n-1)$$, whence $$p_K-p_1\ge(n-1)^2$$.

For any $$d\in[1,n]$$, the set $$P$$ contains an element from every residue class modulo $$d$$, and it follows that there are at most $$K-d$$ pairs of consecutive elements of $$P$$ with the difference equal to $$d$$; also, if $$d>n$$, then there are no such pairs at all. Let $$a$$ and $$r$$ be defined by \begin{align*} K-1 &= \Delta+(\Delta+1)+\dotsb+(\Delta+(a-1))+r \\ &= a\Delta+\frac{a(a-1)}2 + r,\quad 0\le r<\Delta+a. \tag{1} \end{align*} Since there are totally $$K-1$$ pairs of consecutive elements of $$P$$, of them at most $$\Delta$$ pairs at distance $$n$$, at most $$\Delta+1$$ pairs at distance $$n-1$$, etc, we conclude that \begin{align*} p_K-p_1 &\le n\Delta+(n-1)(\Delta+1)+\dotsb+(n-(a-1))(\Delta+(a-1))+(n-a)r \\ &= \Delta na+(n-\Delta)\cdot\frac{a(a-1)}2-\frac{a(a-1)(2a-1)}{6}+(n-a)r. \end{align*} Recalling the estimate $$p_K-p_1\ge(n-1)^2$$, and using ($$1$$), we get \begin{align*} (n-1)^2 &\le \Delta na+(n-\Delta)\cdot\frac{a(a-1)}2-\frac{a(a-1)(2a-1)}{6}+(n-a)r \\ &= n\Big(a\Delta+\frac{a(a-1)}2 + r\Big) - \Delta\cdot\frac{a(a-1)}2 - \frac{a(a-1)(2a-1)}{6} - ar \\ &= n(K-1) - \Delta\cdot\frac{a(a-1)}2 - \frac{a(a-1)(2a-1)}{6} - ar. \tag{2} \end{align*}

We now assume, aiming at a contradiction, that $$\Delta with an absolute constant $$0. From (1) we get then $$K-1 \ge \Delta a + \frac{a(a-1)}2 \ge \frac12\,a^2 - 1$$ implying $$a\le\sqrt{2K}$$; hence, $$\Delta a=O(n^{0.5+c})$$ and $$r=a+\Delta=O(n^{0.5})$$. As a result, $$\frac12\,a^2 = K-1+\frac12\,a-\Delta a - r > K - O(n^{0.5+c}),$$ leading to $$a>(1-o(1))\sqrt{2K}$$.

With these estimates in mind, from (2) we obtain $$n^2 + O(n) \le nK - \frac12\,\Delta a^2 - \frac13\,a^3;$$ that is, $$\Delta n \ge \frac12\,\Delta a^2 + \frac13\,a^3 + O(n).$$ Consequently, $$n^{1+c} \ge \Delta n \ge \frac13\,a^3 + O(n) \ge (1-o(1))(2K)^{1.5} + O(n) > n^{1.5} + O(n),$$ a contradiction.

As an illustration of this approach, let's show that one needs at least $$12$$ elements to block every $$10$$-term progression in $$[1,100]$$. Suppose for a contradiction that $$P\subset[1,100]$$ is an $$11$$-element set blocking all such progressions. There are $$|P|-1=10$$ pairs of consecutive elements of $$P$$. Of these ten pairs, there is at most one pair with distance $$10$$ between its two elements, at most two pairs with distance $$9$$, at most three pairs with distance $$8$$, and at most four pairs with distance $$7$$. Therefore the largest element of $$P$$ exceeds the smallest one by at most $$1\cdot 10+2\cdot 9 + 3\cdot 8 + 4\cdot 7=80$$. It follows that either the smallest element of $$P$$ is at least $$11$$, or its largest element is at most $$90$$; but then $$P$$ does not block at least one of the progressions $$[1,10]$$ and $$[91,100]$$, a contradiction.

Using a tabu search procedure, I have found a solution for $$|P|=17$$, namely $${1, 11, 18, 25, 31, 32, 33, 36, 44, 51, 58, 65, 69, 70, 77, 84, 91}$$. I don't know if this is optimal.

EDIT: Found a solution for $$|P|=16$$, namely $$10, 15, 22, 29, 36, 43, 53, 55, 56, 57, 58, 68, 73, 74, 84, 91$$

• I'm working on $|P|=16$. So far I've found a $P$ with $|P|=16$, namely $\{9, 18, 28, 29, 31, 40, 42, 51, 53, 56, 65, 69, 70, 77, 84, 91\}$, that intersects all but one of these arithmetic progressions, the exception being $({36, 43, 50, 57, 64, 71, 78, 85, 92, 99})$. Jun 27 '19 at 16:50
• I'm using a tabu search over sets of a given size to maximize the number of a.p.'s that intersect the set. Possible moves consist of replacing a member of the set with a nonmember. Jun 27 '19 at 17:00
• Thank you. Your answer is correct. How long did it take to find those numbers? Can you find the boundary of $|P|$? Jun 28 '19 at 8:00
• So is 16 optimal?
– EGME
Jun 28 '19 at 20:43
• My brute-force confirms that there no 15. Jul 2 '19 at 5:19