Timeline for A variant of the corners problem
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 1, 2023 at 13:44 | vote | accept | Kevin | ||
| Jul 29, 2023 at 13:25 | comment | added | Kevin | @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. | |
| Jul 28, 2023 at 3:54 | comment | added | Terry Tao | There seems to be some analogy here with Nikodym sets en.wikipedia.org/wiki/Nikodym_set , which gives a three-dimensional subset of ${\bf R}^2 \times {\bf R}^2$ that avoids these generalized corners. | |
| Jul 27, 2023 at 23:21 | comment | added | fedja | @Kevin "Would you happen to have any idea how to show an upper bound even of $n^{1.99}$, say?" There is a shameful upper bound $n^2/\log\log n$, but I'm not sure you would be interested in that weak quantification of $o(n^2)$. So it seems like we'll have to think a bit more... | |
| Jul 27, 2023 at 21:38 | comment | added | fedja | @TerryTao The random choice of non-empty columns gives $cn\log n$ from below, which I suspect to be the truth, indeed. Unfortunately, I have no good upper bound yet. | |
| Jul 27, 2023 at 19:38 | comment | added | Kevin | Thanks, this is very helpful! I'll wait a little bit longer before accepting an answer. Would you happen to have any idea how to show an upper bound even of $n^{1.99}$, say? | |
| Jul 27, 2023 at 19:28 | comment | added | Terry Tao | Hmm, that does seem to work, nice! | |
| Jul 27, 2023 at 18:25 | comment | added | Fedor Petrov | @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? | |
| Jul 27, 2023 at 17:40 | comment | added | Terry Tao | 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$. | |
| Jul 27, 2023 at 17:22 | comment | added | Fedor Petrov | Yes, any collection of numbers not dividing each other works. I bet this was studied what is the maximal density. Say, square free numbers with exactly $\lceil \log\log n\rceil$ prime divisors have quite high density. | |
| Jul 27, 2023 at 17:13 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
added 2 characters in body
|
| Jul 27, 2023 at 17:05 | comment | added | fedja | 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... | |
| Jul 27, 2023 at 16:52 | comment | added | fedja | "a factor" should be "a multiple", right? | |
| Jul 27, 2023 at 16:30 | history | answered | Fedor Petrov | CC BY-SA 4.0 |