4
$\begingroup$

Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on the same theme. The continuous question is the one I'd really like to know the answer to, but the discrete question feels more "mainstream" and tractable and the two are clearly related.

Discrete Question:

Let $S$ be a subset of the $N \times N$ grid such that no three distinct points of $S$ (including collinear points) form an isosceles triangle. How big can $|S|$ be? Can it be as large as $N^{2-\epsilon}$?

Continuous Question:

For $\beta > 0$, we say a triangle in Euclidean space is $\beta$-isosceles if some vertex is within distance $\beta$ of the line equidistant between the other two vertices.

Let $S$ be a finite subset of $[0,1]^d$ such that no three distinct points of $S$ form a $\beta$-isosceles triangle. What is the minimum possible value of the Hausdorff distance between $S$ and $[0,1]^d$? In other words, what is the largest $\alpha$ such that there must be a ball of radius $\alpha$ containing no points of $S$?

This is a question I was going to pose as a challenge in a paper I'm writing arising from a problem in data science. I realized it might be a good idea to check with people here as to whether anything is already known about it!

Of course, the 1-dimensional versions of these questions have to do with sets with no 3-term arithmetic progressions, which are the subject of a large literature. But I don't immediately see how to leverage those results to say anything about these problems, except to say that the answer to the discrete problem has to be $o(N^2)$. Is there a version of Behrend's construction that applies to the higher-dimensional case?

$\endgroup$
  • $\begingroup$ You do not need Roth's theorem to derive $o(N^2)$ bound. It also follows from the fact that the number of distances occurring in this grid is $o(N^2)$. Indeed, fix a point $p\in S$ and consider the distances of the remaining points to $p$. $\endgroup$ – Boris Bukh Mar 12 at 1:12
  • $\begingroup$ Oh good point! I was thinking "there are about N^2 distances" but are you making the point that only o(N^2) of the integers of the appropriate size are sums of two squares? $\endgroup$ – JSE Mar 12 at 2:27
  • $\begingroup$ Yes, that is what I meant. By the way, this also shows that in $3$ dimensions, we can save a polynomial factor, and it suggests that the same might be true in $2$ dimensions. A natural approach is, like in Roth's theorem, to look at $\sum S(n)S(n+x)S(n+y)K(x,y)$ where $K(x,y)$ is nonzero iff $|x|=|y|$, pass to the Fourier side and use the decay properties of $K(x,y)$ to show that nbd of $0$ contributes most. The continuous version looks nicer since the corresponding integral is $\int S(p)S(p+rx)S(p+ry)d\sigma(x)\,d\sigma(y)$ where $\sigma$ is the measure on the unit circle (and $r\gg \beta$). $\endgroup$ – Boris Bukh Mar 12 at 18:25
  • $\begingroup$ (cont'd) Here $S$ is a smoothened characteristic function of the set (e.g. by placing small balls around each point). For any value of $p$ and any $r\gg \beta$, the integral is at most about $\beta^2$. Then integrating $r$ against an appropriate measure, then passing to the Fourier side, and using decay of $\hat{\sigma}(\xi)$ should get something non-trivial. $\endgroup$ – Boris Bukh Mar 12 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.