To save content items to your account,
please confirm that you agree to abide by our usage policies.
If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account.
Find out more about saving content to .
To save content items to your Kindle, first ensure no-reply@cambridge.org
is added to your Approved Personal Document E-mail List under your Personal Document Settings
on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part
of your Kindle email address below.
Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations.
‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi.
‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Let $W\subseteq \mathbb Z$ be bounded below and normalised by $\inf W=1$, and put $\overline W=\mathbb Z_{>0}\setminus W$. Nathanson asked whether infinite sets of integers admit minimal additive complements. Chen and Yang [‘On a problem of Nathanson related to minimal additive complements’, SIAM J. Discrete Math.26 (2012), 1532–1536] proved that the two-sided case is positive and that sufficiently large consecutive gaps in $\overline W$ force nonexistence in the one-sided case. Chen and Ding [‘On a problem of Nathanson on nonminimal additive complements’, Bull. Aust. Math. Soc.114, 6–13] isolated a sparse-hole condition under which no ordinary minimal complement exists. We prove a finite-fold version of this sparse-hole obstruction. For an integer $h\geq 1$, write $hC=C+\cdots +C$. We show that if $\overline W$ contains a sequence $a_1<a_2<\cdots $ such that $a_{t+1}-a_t\to \infty $ and the four-neighbourhoods $(a_{t-2},a_{t+2})$ contain at most K elements of $\overline W$ for all sufficiently large t, then there is no set $C\subseteq \mathbb Z$ which is minimal subject to $hC+W=\mathbb Z$. This result recovers and broadens the Chen–Ding nonexistence theorem as the special case $h=1$.
In a recent work, Nathanson proved that, for $K=\mathbb {R}$ or $\mathbb {C}$, the set of $B_h$-vectors in $K^n$ is open and dense. Leonetti later extended this to $B_h[g]$-vectors. In this note, we isolate a finite linear functional principle behind these results. Namely, if $\mathcal F$ is a finite family of pairwise distinct linear functionals on $K^n$, then the set of points at which no value is assumed by more than g members of $\mathcal F$ is open and dense in $K^n$. As consequences, we recover the theorems of Nathanson and Leonetti for $B_h[g]$-vectors and obtain the following variant: for every linear form $L(x_1,\ldots ,x_h)=c_1x_1+\cdots +c_hx_h$, with nonzero integer coefficients, the corresponding set of $L[g]$-vectors, evaluated on distinct variables, is open and dense in $K^n$.
where $1 \leq n_1\lt\cdots\lt n_k$ are pairwise distinct integers. In their 1980 monograph, Erdős and Graham asked for quantitative estimates on the growth of v(k) and suggested the lower bound $v(k)\gg k!$. In this paper we give the first known improvement and show that there exists an absolute constant $c\gt0$ such that the inequality
An $S_k$-set in a group $\Gamma $ is a set $A\subseteq \Gamma $ such that $\alpha _1\dots \alpha _k=\beta _1\dots \beta _k$ with $\alpha _i,\beta _i\in A$ implies $(\alpha _1,\ldots ,\alpha _k)=(\beta _1,\ldots ,\beta _k)$. An $S_k'$-set is a set such that $\alpha _1\beta _1^{-1}\dots \alpha _k\beta _k^{-1}=1$ implies that there exists i such that $\alpha _i=\beta _i\text { or }\beta _i=\alpha _{i+1}$. We give explicit constructions of large $S_k$-sets in the groups $\mathrm {Sym}(n)$ and $\mathrm {Alt}(n)$ and $S_2$-sets in $\mathrm {Sym}(n)\times \mathrm {Sym}(n)$ and $\mathrm {Alt}(n)\times \mathrm {Alt}(n)$. We give probabilistic constructions which yield large $S_2'$-sets in $\mathrm {Sym}(n)$. We also give upper bounds on the size of $S_k$-sets in certain groups, improving the trivial bound by a constant multiplicative factor. We describe some connections between $S_k$-sets and extremal graph theory. In particular, we determine up to a constant factor the minimum outdegree of a digraph which guarantees even cycles with certain orientations. As applications, we improve the upper bound on Hamilton paths which pairwise create a two-part cycle of given length, and we show that a directed version of the Erdős–Simonovits compactness conjecture is false.
Let A be a subset of an additive abelian semigroup S and let $hA$ be the h-fold sumset of A. The following question is considered. Let $(A_q)_{q=1}^{\infty }$ be a strictly decreasing sequence of sets in S and let $A = \bigcap _{q=1}^{\infty } A_q$. When does one have
$$ \begin{align*} hA = \bigcap_{q=1}^{\infty} hA_q \end{align*} $$
It is an open problem in additive number theory to compute and understand the full range of sumset sizes of finite sets of integers, that is, the set $ \mathcal R_{\mathbf Z}(h,k) = \{|hA|:A \subseteq \mathbf Z \text { and } |A|=k\}$ for all integers $h \geq 3$ and $k \geq 3$. This article constructs certain infinite families of finite sets of size k, computes their h-fold sumset sizes, and obtains explicit finite arithmetic progressions of sumset sizes in $ \mathcal R_{\mathbf Z}(h,k)$.
Let A be a set of natural numbers. A set B of natural numbers is an additive complement of the set A if all sufficiently large natural numbers can be represented in the form $x+y$, where $x\in A$ and $y\in B$. We establish that if $A=\{a_i: i\in \mathbb {N}\}$ is a set of natural numbers such that $a_i<a_{i+1} $ for $i \in \mathbb {N}$ and $\liminf _{n\rightarrow \infty } (a_{n+1}/a_{n})>1$, then there exists a set $B\subset \mathbb {N}$ such that $B\cap A = \varnothing $ and B is a sparse additive complement of the set A.
Let $K = \mathbf {R}$ or $\mathbf {C}$. An n-element subset A of K is a $B_h$-set if every element of K has at most one representation as the sum of h not necessarily distinct elements of A. Associated with the $B_h$-set $A = \{a_1,\ldots , a_n\}$ are the $B_h$-vectors $\mathbf {a} = (a_1,\ldots , a_n)$ in $K^n$. This article proves that “almost all” n-element subsets of K are $B_h$-sets in the sense that the set of all $B_h$-vectors is a dense open subset of $K^n$.
A class of sequences called L-sequences is introduced, each one being a subsequence of a Collatz sequence. Every ordered pair $(v,w)$ of positive integers determines an odd positive integer P such that there exists an L-sequence of length n for every positive integer n, each term of which is congruent to P modulo $2^{v+w+1}$. The smallest possible initial term of such a sequence is described. If $3^v>2^{v+w}$ the L-sequence is increasing. Otherwise, it is decreasing, except if it is the constant sequence P. A central role is played by Bezout’s identity.
We study linear random walks on the torus and show a quantitative equidistribution statement, under the assumption that the Zariski closure of the acting group is semisimple.
It was asked by E. Szemerédi if, for a finite set $A\subset {\mathbb {Z}}$, one can improve estimates for $\max \{|A+A|,|A\cdot A|\}$, under the constraint that all integers involved have a bounded number of prime factors, that is, each $a\in A$ satisfies $\omega (a)\leq k$. In this paper we show that this maximum is at least of order $|A|^{\frac {5}{3}-o_\epsilon (1)}$ provided $k\leq (\log |A|)^{1-\varepsilon }$ for any $\varepsilon \gt 0$. In fact, this will follow from an estimate for additive energy which is best possible up to factors of size $|A|^{o(1)}$.
The triangle removal states that if G contains $\varepsilon n^2$ edge-disjoint triangles, then G contains $\delta (\varepsilon )n^3$ triangles. Unfortunately, there are no sensible bounds on the order of growth of $\delta (\varepsilon )$, and at any rate, it is known that $\delta (\varepsilon )$ is not polynomial in $\varepsilon $. Csaba recently obtained an asymmetric variant of the triangle removal, stating that if G contains $\varepsilon n^2$ edge-disjoint triangles, then G contains $2^{-\operatorname {\mathrm {poly}}(1/\varepsilon )}\cdot n^5$ copies of $C_5$. To this end, he devised a new variant of Szemerédi’s regularity lemma. We obtain the following results:
• We first give a regularity-free proof of Csaba’s theorem, which improves the number of copies of $C_5$ to the optimal number $\operatorname {\mathrm {poly}}(\varepsilon )\cdot n^5$.
• We say that H is $K_3$-abundant if every graph containing $\varepsilon n^2$ edge-disjoint triangles has $\operatorname {\mathrm {poly}}(\varepsilon )\cdot n^{\lvert V(H)\rvert }$ copies of H. It is easy to see that a $K_3$-abundant graph must be triangle-free and tripartite. Given our first result, it is natural to ask if all triangle-free tripartite graphs are $K_3$-abundant. Our second result is that assuming a well-known conjecture of Ruzsa in additive number theory, the answer to this question is negative.
Our proofs use a mix of combinatorial, number-theoretic, probabilistic and Ramsey-type arguments.
Erdös and Selfridge first showed that the product of consecutive integers cannot be a perfect power. Later, this result was generalized to polynomial values by various authors. They demonstrated that the product of consecutive polynomial values cannot be the perfect power for a suitable polynomial. In this article, we consider a related problem to the product of consecutive integers. We consider all sequences of polynomial values from a given interval whose products are almost perfect powers. We study the size of these powers and give an asymptotic result. We also define a group theoretic invariant, which is a natural generalization of the Davenport constant. We provide a non-trivial upper bound of this group theoretic invariant.
A linear equation $E$ is said to be sparse if there is $c\gt 0$ so that every subset of $[n]$ of size $n^{1-c}$ contains a solution of $E$ in distinct integers. The problem of characterising the sparse equations, first raised by Ruzsa in the 90s, is one of the most important open problems in additive combinatorics. We say that $E$ in $k$ variables is abundant if every subset of $[n]$ of size $\varepsilon n$ contains at least $\text{poly}(\varepsilon )\cdot n^{k-1}$ solutions of $E$. It is clear that every abundant $E$ is sparse, and Girão, Hurley, Illingworth, and Michel asked if the converse implication also holds. In this note, we show that this is the case for every $E$ in four variables. We further discuss a generalisation of this problem which applies to all linear equations.
For a subset $A$ of an abelian group $G$, given its size $|A|$, its doubling $\kappa =|A+A|/|A|$, and a parameter $s$ which is small compared to $|A|$, we study the size of the largest sumset $A+A'$ that can be guaranteed for a subset $A'$ of $A$ of size at most $s$. We show that a subset $A'\subseteq A$ of size at most $s$ can be found so that $|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$. Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling $\kappa$ is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets $A,B$ of $\mathbb{F}_p$ of size at most $\alpha p$ for an appropriate constant $\alpha \gt 0$, one only needs three elements $b_1,b_2,b_3\in B$ to guarantee $|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$. Allowing the use of larger subsets $A'$, we show that for sets $A$ of bounded doubling, one only needs a subset $A'$ with $o(|A|)$ elements to guarantee that $A+A'=A+A$. We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset.
In our paper, we study multiplicative properties of difference sets $A-A$ for large sets $A \subseteq {\mathbb {Z}}/q{\mathbb {Z}}$ in the case of composite q. We obtain a quantitative version of a result of A. Fish about the structure of the product sets $(A-A)(A-A)$. Also, we show that the multiplicative covering number of any difference set is always small.
For a nonempty set A of integers and an integer n, let $r_{A}(n)$ be the number of representations of n in the form $n=a+a'$, where $a\leqslant a'$ and $a, a'\in A$, and $d_{A}(n)$ be the number of representations of n in the form $n=a-a'$, where $a, a'\in A$. The binary support of a positive integer n is defined as the subset S(n) of nonnegative integers consisting of the exponents in the binary expansion of n, i.e., $n=\sum_{i\in S(n)} 2^i$, $S(-n)=-S(n)$ and $S(0)=\emptyset$. For real number x, let $A(-x,x)$ be the number of elements $a\in A$ with $-x\leqslant a\leqslant x$. The famous Erdős-Turán Conjecture states that if A is a set of positive integers such that $r_A(n)\geqslant 1$ for all sufficiently large n, then $\limsup_{n\rightarrow\infty}r_A(n)=\infty$. In 2004, Nešetřil and Serra initially introduced the notation of “bounded” property and confirmed the Erdős-Turán conjecture for a class of bounded bases. They also proved that, there exists a set A of integers satisfying $r_A(n)=1$ for all integers n and $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A$. On the other hand, Nathanson proved that there exists a set A of integers such that $r_A(n)=1$ for all integers n and $2\log x/\log 5+c_1\leqslant A(-x,x)\leqslant 2\log x/\log 3+c_2$ for all $x\geqslant 1$, where $c_1,c_2$ are absolute constants. In this paper, following these results, we prove that, there exists a set A of integers such that: $r_A(n)=1$ for all integers n and $d_A(n)=1$ for all positive integers n, $|S(x)\bigcup S(y)|\leqslant 4|S(x+y)|$ for $x,y\in A$ and $A(-x,x) \gt (4/\log 5)\log\log x+c$ for all $x\geqslant 1$, where c is an absolute constant. Furthermore, we also construct a family of arbitrarily spare such sets A.
with initial data $(x_1,x_2,x_3)=(0,x,1)$, is eventually constant, and that its transit time and limit functions (of x) are unbounded and continuous, respectively. In this paper, we prove that for the slightly modified recursion
A finite set of integers A tiles the integers by translations if $\mathbb {Z}$ can be covered by pairwise disjoint translated copies of A. Restricting attention to one tiling period, we have $A\oplus B=\mathbb {Z}_M$ for some $M\in \mathbb {N}$ and $B\subset \mathbb {Z}$. This can also be stated in terms of cyclotomic divisibility of the mask polynomials $A(X)$ and $B(X)$ associated with A and B.
In this article, we introduce a new approach to a systematic study of such tilings. Our main new tools are the box product, multiscale cuboids and saturating sets, developed through a combination of harmonic-analytic and combinatorial methods. We provide new criteria for tiling and cyclotomic divisibility in terms of these concepts. As an application, we can determine whether a set A containing certain configurations can tile a cyclic group $\mathbb {Z}_M$, or recover a tiling set based on partial information about it. We also develop tiling reductions where a given tiling can be replaced by one or more tilings with a simpler structure. The tools introduced here are crucial in our proof in [24] that all tilings of period $(pqr)^2$, where $p,q,r$ are distinct odd primes, satisfy a tiling condition proposed by Coven and Meyerowitz [2].