Cardinalities of $g$-difference sets

For $\ell\geq 2$ and $h\in \mathbb{Z}[x_1,\dots,x_{\ell}]$ of degree $k\geq 2$, we show that every set $A\subseteq \{1,2,\dots,N\}$ lacking nonzero differences in $h(\mathbb{Z}^{\ell})$ satisfies $|A|\ll_h Ne^{-c(\log N)^{\mu}}$, where $c=c(h)>0$, $\mu=[(k-1)^2+1]^{-1}$ if $\ell=2$, and $\mu=1/2$ if $\ell\geq 3$, provided $h(\mathbb{Z}^{\ell})$ contains a multiple of every natural number and $h$ satisfies certain nonsingularity conditions. We also explore these conditions in ...

Let $(a_n)_{n \geq 1}$ be a sequence of distinct positive integers. In a recent paper Rudnick established asymptotic upper bounds for the minimal gaps of $\{a_n \alpha \bmod 1, 1 \leq n \leq N\}$ as $N \to \infty$, valid for Lebesgue-almost all $\alpha$ and formulated in terms of the additive energy of $\{a_1, \dots, a_N\}$. In the present paper we argue that the metric theory of minimal gaps of such sequences is not controlled by the additive energy, but rather by the cardin...

Suppose that $A$ is a finite, nonempty subset of a cyclic group of either infinite or prime order. We show that if the difference set $A-A$ is ``not too large'', then there is a nonzero group element with at least as many as $(2+o(1))|A|^2/|A-A|$ representations as a difference of two elements of $A$; that is, the second largest number of representations is, essentially, twice the average. Here the coefficient $2$ is the best possible. We also prove continuous and multidime...

For a subset $A \subseteq [N]$, we define the representation function $ r_{A-A}(d) := \#\{(a,a') \in A \times A : d = a - a'\}$ and define $M_D(A) := \max_{1 \leq d < D} r_{A-A}(d)$ for $D>1$. We study the smallest possible value of $M_D(A)$ as $A$ ranges over all possible subsets of $[N]$ with a given size. We give explicit asymptotic expressions with constant coefficients determined for a large range of $D$. We shall also see how this problem connects to a well-known proble...

Which finite sets $P \subseteq \mathbb{Z}^r$ with $|P| \ge 3$ have the following property: for every $A \subseteq [N]^r$, there is some nonzero integer $d$ such that $A$ contains $(\alpha^{|P|} - o(1))N^r$ translates of $d \cdot P = \{d p : p \in P\}$, where $\alpha = |A|/N^r$? Green showed that all 3-point $P \subseteq \mathbb{Z}$ have the above property. Green and Tao showed that 4-point sets of the form $P = \{a, a+b, a+c, a+b+c\} \subseteq \mathbb{Z}$ also have the prop...

We consider the local properties problem for difference sets: we define $g(n, k, \ell)$ to be the minimum value of $\lvert A - A\rvert$ over all $n$-element sets $A \subseteq \mathbb{R}$ with the `local property' that $\lvert A' - A'\rvert \geq \ell$ for all $k$-element subsets $A' \subseteq A$. We view $k$ and $\ell$ as fixed, and study the asymptotic behavior of $g(n, k, \ell)$ as $n \to \infty$. One of our main results concerns the quadratic threshold, i.e., the minimum va...

Let $\Gamma$ be an abelian group and $g \geq h \geq 2$ be integers. A set $A \subset \Gamma$ is a $C_h[g]$-set if given any set $X \subset \Gamma$ with $|X| = k$, and any set $\{ k_1 , \dots , k_g \} \subset \Gamma$, at least one of the translates $X+ k_i$ is not contained in $A$. For any $g \geq h \geq 2$, we prove that if $A \subset \{1,2, \dots ,n \}$ is a $C_h[g]$-set in $\mathbb{Z}$, then $|A| \leq (g-1)^{1/h} n^{1 - 1/h} + O(n^{1/2 - 1/2h})$. We show that for any intege...

Given a finite abelian group $G$ and a subset $J\subset G$ with $0\in J$, let $D_{G}(J,N)$ be the maximum size of $A\subset G^{N}$ such that the difference set $A-A$ and $J^{N}$ have no non-trivial intersection. Recently, this extremal problem has been widely studied for different groups $G$ and subsets $J$. In this paper, we generalize and improve the relevant results by Alon and by Heged\H{u}s by building a bridge between this problem and cyclotomic polynomials with the hel...

Green used an arithmetic analogue of Szemer\'edi's celebrated regularity lemma to prove the following strengthening of Roth's theorem in vector spaces. For every $\alpha>0$, $\beta<\alpha^3$, and prime number $p$, there is a least positive integer $n_p(\alpha,\beta)$ such that if $n \geq n_p(\alpha,\beta)$, then for every subset of $\mathbb{F}_p^n$ of density at least $\alpha$ there is a nonzero $d$ for which the density of three-term arithmetic progressions with common diffe...

Let $(G, +)$ be an abelian group. In 2004, Eliahou and Kervaire found an explicit formula for the smallest possible cardinality of the sumset $A+A$, where $A \subseteq G$ has fixed cardinality $r$. We consider instead the smallest possible cardinality of the difference set $A-A$, which is always greater than or equal to the smallest possible cardinality of $A+A$ and can be strictly greater. We conjecture a formula for this quantity and prove the conjecture in the case that $G...