On the dimension of additive sets

We improve the well-known Szemer\'edi-Trotter incidence bound for proper 3--dimensional point sets (defined appropriately)

We show that for all $A, B \subseteq \{0,1,2\}^{d}$ we have $$ |A+B|\geq (|A||B|)^{\log(5)/(2\log(3))}. $$ We also show that for all finite $A,B \subset \mathbb{Z}^{d}$, and any $V \subseteq\{0,1\}^{d}$ the inequality $$ |A+B+V|\geq |A|^{1/p}|B|^{1/q}|V|^{\log_{2}(p^{1/p}q^{1/q})} $$ holds for all $p \in (1, \infty)$, where $q=\frac{p}{p-1}$ is the conjugate exponent of $p$. All the estimates are dimension free with the best possible exponents. We discuss applications to vari...

In this paper we prove some lower bounds on the Hausdorff dimension of sets of Furstenberg type. Moreover, we extend these results to sets of generalized Furstenberg type, associated to doubling dimension functions. With some additional growth conditions on the dimension function, we obtain a lower bound on the dimension of "zero dimensional" Furstenberg sets.

We provide quantitative estimates for the supremum of the Hausdorff dimension of sets in the real line which avoid $\varepsilon$-approximations of arithmetic progressions. Some of these estimates are in terms of Szemer\'{e}di bounds. In particular, we answer a question of Fraser, Saito and Yu (IMRN, 2019) and considerably improve their bounds. We also show that Hausdorff dimension is equivalent to box or Assouad dimension for this problem, and obtain a lower bound for Fourier...

We give a new lower bound for the minimal dispersion of a point set in the unit cube and its inverse function in the high dimension regime. This is done by considering only a very small class of test boxes, which allows us to reduce bounding the dispersion to a problem in extremal set theory. Specifically, we translate a lower bound on the size of $r$-cover-free families to a lower bound on the inverse of the minimal dispersion of a point set. The lower bound we obtain matche...

The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be $\Theta(n)$, it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we expl...

This paper considers an extremal version of the Erd\H{o}s distinct distances problem. For a point set $P \subset \mathbb R^d$, let $\Delta(P)$ denote the set of all Euclidean distances determined by $P$. Our main result is the following: if $\Delta(A^d) \ll |A|^2$ and $d \geq 5$, then there exists $A' \subset A$ with $|A'| \geq |A|/2$ such that $|A'-A'| \ll |A| \log |A|$. This is one part of a more general result, which says that, if the growth of $|\Delta(A^d)|$ is restric...

We prove new bounds on the dimensions of distance sets and pinned distance sets of planar sets. Among other results, we show that if $A\subset\mathbb{R}^2$ is a Borel set of Hausdorff dimension $s>1$, then its distance set has Hausdorff dimension at least $37/54\approx 0.685$. Moreover, if $s\in (1,3/2]$, then outside of a set of exceptional $y$ of Hausdorff dimension at most $1$, the pinned distance set $\{ |x-y|:x\in A\}$ has Hausdorff dimension $\ge \tfrac{2}{3}s$ and pack...

We show that intersection graphs of compact convex sets in R^n of bounded aspect ratio have asymptotic dimension at most 2n+1. More generally, we show this is the case for intersection graphs of systems of subsets of any metric space of Assouad-Nagata dimension n that satisfy the following condition: For each r,s>0 and every point p, the number of pairwise-disjoint elements of diameter at least s in the system that are at distance at most r from p is bounded by a function of ...

We study dimensions of sumsets and iterated sumsets and provide natural conditions which guarantee that a set $F \subseteq \mathbb{R}$ satisfies $\overline{\dim}_\text{B} F+F > \overline{\dim}_\text{B} F$ or even $\dim_\text{H} n F \to 1$. Our results apply to, for example, all uniformly perfect sets, which include Ahlfors-David regular sets. Our proofs rely on Hochman's inverse theorem for entropy and the Assouad and lower dimensions play a critical role. We give several app...