Return to Answer

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 set 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)}$. It would be interesting to improve this estimate 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<p_K\le n^2$. 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 form 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 make the simplifying assumption $r=0$ and, for a contradiction, assume also that $\Delta<n^c$ with an absolute constant $0<c<0.5$. From (1) we get then $$ K-1 = \Delta a + \frac{a(a-1)}2 >\frac12\,a^2 - 1 $$ implying $a<\sqrt{2K}$; hence, $\Delta a=O(n^{0.5+c})$. As a result, $$ \frac12\,a^2 = K-1+\frac12\,a-\Delta a > 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.

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<p_K\le n^2$. 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<n^c$ with an absolute constant $0<c<0.5$. 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.

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

How large can a set $A\subset[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 which seems to show that if $P\subset[1,n^2]$ meets every $n$-term progression contained in $[1,n^2]$, then $|P|>n+n^c$ with a positive absolute constant $c$. It would be interesting to improve this estimate to something like $|P|>(1+c)n+O(1)$.

Write $K:=|P|$ and $P=\{p_1,\dotsc,p_K\}$ where $1\le p_1<\dotsb<p_K\le n^2$. We have $p_1\le n$ and $p_K\ge n^2-(n-1)$, whence $p_K-p_1\ge(n-1)^2$. Next, for any $d\in[1,n]$, the set $P$ contains an element form 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 $\Delta:=K-n$, and let $a>0$ 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$, we get $$ \Delta na+(n-\Delta)\cdot\frac{a(a-1)}2-\frac{a(a-1)(2a-1)}{6}+(n-a)r \ge (n-1)^2. \tag{2} $$ This leads to the following optimization problem: find the smallest $\Delta=\Delta(n)$ such that, with $K=n+\Delta$, the quantities $a$ and $r$ defined by (1) satisfy (2). It certainly should be possible to solve it, but the solution can be rather messy. I have at least investigated this problem numerically, and the results look quite amazing to me (which even makes me suspect that there can be a mistake in my calculations or programming). Specifically, here is the graph of $\log \Delta(n) /\log n$:

I absolutely cannot see any reason for the graph to be that steep for $n$ small and then flat for $n$ large, but anyway, the quotients seem to converge to a limit $c\approx 0.44$ (I have in fact made the computations for $n$ up to $10^5$). If everything is correct, this means that $K=|P|>n+n^c$.

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 set 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)}$. It would be interesting to improve this estimate 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<p_K\le n^2$. 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 form 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 make the simplifying assumption $r=0$ and, for a contradiction, assume also that $\Delta<n^c$ with an absolute constant $0<c<0.5$. From (1) we get then $$ K-1 = \Delta a + \frac{a(a-1)}2 >\frac12\,a^2 - 1 $$ implying $a<\sqrt{2K}$; hence, $\Delta a=O(n^{0.5+c})$. As a result, $$ \frac12\,a^2 = K-1+\frac12\,a-\Delta a > 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.

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

How large can a set $A\subset[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 which seems to show that if $P\subset[1,n^2]$ meets every $n$-term progression contained in $[1,n^2]$, then $|P|>n+n^c$ with a positive absolute constant $c$. It would be interesting to improve this estimate to something like $|P|>(1+c)n+O(1)$.

Write $K:=|P|$ and $P=\{p_1,\dotsc,p_K\}$ where $1\le p_1<\dotsb<p_K\le n^2$. We have $p_1\le n$ and $p_K\ge n^2-(n-1)$, whence $p_K-p_1\ge(n-1)^2$. Next, for any $d\in[1,n]$, the set $P$ contains an element form each 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 $\Delta:=K-n$, and let $a>0$ 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$, we get $$ \Delta na+(n-\Delta)\cdot\frac{a(a-1)}2-\frac{a(a-1)(2a-1)}{6}+(n-a)r \ge (n-1)^2. \tag{2} $$ This leads to the following optimization problem: find the smallest $\Delta=\Delta(n)$ such that, with $K=n+\Delta$, the quantities $a$ and $r$ defined by (1) satisfy (2). The solution should certainly be possible, but messy. I have at least investigated this problem numerically, and the results look quite amazing to me (which even makes me suspecting that there can be a mistake in my calculations or programming). Specifically, here is the graph of $\log \Delta /\log n$:

I absolutely cannot see any reason for the graph to be that steep for $n$ small and then flat for $n$ large, but anyway, the quotients seem to converge to a limit $c\approx 0.44$ (I have in fact made the computations for $n$ up to $10^5$). If everything is correct, this means that $K=|P|>n+n^c$.

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

How large can a set $A\subset[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 which seems to show that if $P\subset[1,n^2]$ meets every $n$-term progression contained in $[1,n^2]$, then $|P|>n+n^c$ with a positive absolute constant $c$. It would be interesting to improve this estimate to something like $|P|>(1+c)n+O(1)$.

Write $K:=|P|$ and $P=\{p_1,\dotsc,p_K\}$ where $1\le p_1<\dotsb<p_K\le n^2$. We have $p_1\le n$ and $p_K\ge n^2-(n-1)$, whence $p_K-p_1\ge(n-1)^2$. Next, for any $d\in[1,n]$, the set $P$ contains an element form 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 $\Delta:=K-n$, and let $a>0$ 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$, we get $$ \Delta na+(n-\Delta)\cdot\frac{a(a-1)}2-\frac{a(a-1)(2a-1)}{6}+(n-a)r \ge (n-1)^2. \tag{2} $$ This leads to the following optimization problem: find the smallest $\Delta=\Delta(n)$ such that, with $K=n+\Delta$, the quantities $a$ and $r$ defined by (1) satisfy (2). It certainly should be possible to solve it, but the solution can be rather messy. I have at least investigated this problem numerically, and the results look quite amazing to me (which even makes me suspect that there can be a mistake in my calculations or programming). Specifically, here is the graph of $\log \Delta(n) /\log n$:

I absolutely cannot see any reason for the graph to be that steep for $n$ small and then flat for $n$ large, but anyway, the quotients seem to converge to a limit $c\approx 0.44$ (I have in fact made the computations for $n$ up to $10^5$). If everything is correct, this means that $K=|P|>n+n^c$.