2
$\begingroup$

A huge part of the investigation in the area of additive combinatorics asks for the answer of the following question: given an arithmetic pattern (for instance, $x+y=2z$, or $x+y=z+t$, or $x+y=z$), give the largest size of a subset $A\subseteq [n]$ avoiding the considered configuration. For instance, when dealing with $x+y=2z$ we have the theory starting from Roth's theorem and whose generalization, Szemerédi's theorem, has been a key and very influential result on the area.

My question is the following: which results are known concerning lower bounds for this type of problems when taking subsets of the set of non-negative integers instead of the finite interval?

For instance, in the case of the Sidon equation $x+y=z+t$, the upper and the lower bound ($\sqrt{n}$, up to the error matches): there are explicit constructions reaching the square root value, and it is possible to show that the upper bound must be of the same order. However, concerning lower bounds, in the infinite case the only thing known is that there exists Sidon sets $A$, such that $|A(n)|=|\{a\in A: a\leq n\}|=n^{\sqrt{2}-1+o(1)}$ (this is a very clever result first by Ruzsa, and then by Cilleruelo).

For instance, what is it the best known in the case of the 3-AP equation? In the finite case we have Behrend construction, but I guess (as in the case of Sidon) that this cannot be lifted to an infinite family. I know that the integers which uses 0,1 in their ternary representation defines a 3-AP-free set (hence, density $n^{2/3}$, but not sure if something better is known.

So, in general, what is known for explicit dense infinite families avoiding a given arithmetic pattern?

$\endgroup$
2
  • $\begingroup$ Is $\ [n]\ :=\ \{x\in\mathbb Z:\ 0\le x < n\}\ $ ? $\endgroup$
    – Wlod AA
    Feb 11, 2023 at 7:55
  • $\begingroup$ @Wlod AA: yes, that's right $\endgroup$ Feb 11, 2023 at 9:42

1 Answer 1

2
$\begingroup$

For 3-APs, an infinite Behrend-shape construction was achieved by Moser in 1953. Namely, there is an infinite set $A$ and some absolute constant $C>0$ such that $|A\cap \{1,\dots,N\}| \ge N\exp(-C\sqrt{\log N})$ for all sufficiently large $N$.

I will sketch this below. The same type of argument should work for longer progressions too, to match the Rankin-type bounds (by modifying how $m_t$ grows).

For those familiar with the Behrend, it is not much different. We pick a sequence of moduli $ m_1< m_2 < \dots$ so that $m_t\mid m_{t+1}$ for each $t$. To get a good bound, we should have that $m_{t+1}/m_t$ is of shape $\exp(\Theta(t))$ (so explicitly $m_t:= 10^{t^2}$ would do the trick).

We define $\phi:\Bbb{N}\to \prod_{t=1}^\infty \{0,\dots,m_t-1\}$ so that for $\xi =\phi(n)$, we have $\xi_t := \max\{0,n- m_t\lfloor n/m_t\rfloor\}$. Let $S\subset\Bbb{N}$ be set of $n$ where $\phi(n)_t<m_t/2$ for all $t$, we have that $\phi|_S$ is a Freimann isomorphism. Moreover, it is quite dense, as $|S\cap \{1,\dots,m_t\}| = m_t2^{-t}$ (assuming all moduli are even).

Now, define $S_t \subset (S\cap \{1,\dots,m_t\})$ to be the set of such $n$ where $\phi(n)_{t-1} \ge m_{t-1}/4$. One now has that if $x\in S_{t_1},y\in S_{t_2},z\in S_{t_3}$ satisfy $x+z =2y$, then $t_1=t_2=t_3$.

One can then finish by basically applying Behrend's construction to finding a large 3-AP-free set $A_t\subset S_t$ for each $t$, and taking $A= \bigcup_{t=1}^\infty A_t$ to be our 3-AP-free set as these sets no longer interact (Moser actually does something more clever, which avoids using pigeonhole, but I won't get into this). But the point is that we always have that for $N\in [m_{t-1},m_t]$, that $$(A\cap \{1,\dots,N\}) \supset A_{t-1},$$ whence the density of the LHS is at most $$\frac{m_{t-1}}{m_t} \frac{A_{t-1}}{m_{t-1}} \gg \exp(-O(t+\sqrt{\log m_{t-1}}))\ge \exp(-O(\sqrt{\log N}))$$(assuming $m_t = 10^{t^2}$).

Edit: Actually, I'm overcomplicating things. The main novelty of Moser's proof was the avoidance of pigeonhole; the infinitary aspect is rather trivial.

Basically, just consider the sets $S_t = \{4^t+1,4^t+2,\dots,2 \cdot 4^t\_$. One has that $x\in S_{t_1},y\in S_{t_2},z\in S_{t_3}$ satisfy $x+z=2y$, then $t_1=t_2=t_3$.

Then, we can find a really dense 3-AP-free set $A_t\subset S_t$ via Behrend's construction for each $t\ge 1$. We will have that $A:=\bigcup_{t=1}^\infty A_t$ will still be 3-AP-free, and will also have the same shape of density. It is easy to extend this to longer progressions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.