11
$\begingroup$

Question: What is the size of the largest subset of $[n]^2$ containing no three point configurations of the form $(x,y), (x,y+d), (x+d,y')$ with $d \neq 0$? In particular, is it at most $O(n)$?

Recall that the corners theorem of Ajtai and Szemerédi says that the largest subset of $[n]^2$ containing no three point configuration $(x,y), (x,y+d), (x+d,y)$ with $d \neq 0$ has size $o(n^2)$. In addition, there is a lower bound on this quantity of $n^{2-o(1)}$, which can be obtained by taking the set of points lying on a set of slope-$1$ lines whose $y$-intercepts contain no nontrivial $3$-term arithmetic progressions (for example).

The difference between the corners problem and the above question is that I forbid not only the third point of the corner $(x+d, y)$, but all points on the entire vertical line through this point. This is stronger, so the answer is $o(n^2)$ by the corners theorem. This is the best upper bound I know, although it seems like my condition is much stronger. The only lower bounds I know are linear. For example, you can take $S = \{(1,y), (n,y) : y \in [n-1]\}$, which shows that the answer is at least $2(n-1)$. This is not exactly optimal though; for example, for $n=10$ the largest such set has size $24$, shown by the set of blue points in the below picture.

enter image description here

Improve this question
$\endgroup$
1
  • $\begingroup$ Neither version seems to be in OEIS: $$1,3,6,10,14,20,25,32,39,48$$ $$1,2,4,6,9,10,16,17,22,24$$ $\endgroup$
    – RobPratt
    Commented Jul 28, 2023 at 0:45

1 Answer 1

Reset to default
12
$\begingroup$

It is not $O(n)$. You may take all primes $p_1,\ldots,p_d$ between 1 and $n$ and mark points $(p_i,kp_i)$ for all positive integers $k\leqslant n/p_i$. This gives about $n\log \log n$ points. Since $p_j-p_i$ is not a multiple of $p_i$ for $i\ne j$, there is no your corner with marked vertices.

Improve this answer
$\endgroup$
11
  • $\begingroup$ "a factor" should be "a multiple", right? $\endgroup$
    – fedja
    Commented Jul 27, 2023 at 16:52
  • $\begingroup$ Also it looks like taking all products of 2 distinct primes will give an even better lower bound, then triples can improve upon that, etc., so I suspect that the truth is around $n\log n$ but cannot prove it yet... $\endgroup$
    – fedja
    Commented Jul 27, 2023 at 17:05
  • 1
    $\begingroup$ One can reach $n \log n / \log\log n$ by taking $m \sim \log n$ so that $\prod_{p \leq m} p < n$, then for each $p \leq m$ and $i=1,\dots,p-1$ using the Chinese remainder theorem to selecting $a_{p,i}$ to equal $i \hbox{ mod } p$ and $0 \hbox{ mod } p'$ for all other $p' \leq m$. The points $(a_{p,i}, k p)$ for $k \leq n/p$ then avoid the generalized corners and have cardinality $\sim n \log n / \log\log n$. $\endgroup$
    – Terry Tao
    Commented Jul 27, 2023 at 17:40
  • 1
    $\begingroup$ @TerryTao does not taking all products of exactly $k$ primes (where $k$ is most popular) instead of $p_i$ give $n\log n/\sqrt{\log \log n}$ by Erdős-Kac? $\endgroup$
    – Fedor Petrov
    Commented Jul 27, 2023 at 18:25
  • 1
    $\begingroup$ @fedja I only know the upper bound of $n^2/(\log \log n)^{0.013..}$ which holds for the corners problem. I'd be curious to know any improvement to this, especially if it's simpler. $\endgroup$
    – Kevin
    Commented Jul 29, 2023 at 13:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .