Combinatorial and Additive Number Theory

In 1845, Bertrand conjectured that for all integers x ≥ 2, there exists at least one prime in (x∕2, x]. This was proved by Chebyshev in 1860 and then generalized by Ramanujan in 1919. He showed that for any n ≥ 1, there is a (smallest) prime R _n such that \(\pi (x) -\pi (x/2) \geq n\) for all x ≥ R _n . In 2009 Sondow called R _n the nth Ramanujan prime and proved the asymptotic behavior R _n  ∼ p _2n (where p _m is the mth prime). He and Laishram proved the bounds p _2n  < R _n  < p _3n , respectively, for n > 1. In the present paper, we generalize the interval of interest by introducing a parameter c ∈ (0, 1) and defining the nth c-Ramanujan prime as the smallest integer R _c, n such that for all x ≥ R _c, n , there are at least n primes in (cx, x]. Using consequences of strengthened versions of the Prime Number Theorem, we prove that R _c, n exists for all n and all c, that \(R_{c,n} \sim p_{ \frac{n} {1-c} }\) as n → ∞, and that the fraction of primes which are c-Ramanujan converges to 1 − c. We then study finer questions related to their distribution among the primes and see that the c-Ramanujan primes display striking behavior, deviating significantly from a probabilistic model based on biased coin flipping. This model is related to the Cramer model, which correctly predicts many properties of primes on large scales but has been shown to fail in some instances on smaller scales.

We consider multiplicative monoids of the positive integers defined by a single congruence. If a and b are positive integers such that a ≤ b and \(a^{2} \equiv a\mod b\), then such a monoid (known as an arithmetic congruence monoid or an ACM) can be described as \(M_{a,b} = (a + b\mathbb{N}_{0}) \cup \{ 1\}\). In lectures on elementary number theory, Hilbert demonstrated to students the utility of the proof of the Fundamental Theorem of Arithmetic for \(\mathbb{Z}\) by considering the arithmetic congruence monoid with a = 1 and b = 4. In M _1, 4, the element 441 has a nonunique factorization into irreducible elements as 9 ⋅ 49 = 21². ACMs have appeared frequently in the mathematical literature over the last decade. While their structures can be understood merely with rational number theory, their multiplicative behavior can become quite complex. We show that all ACMs fall into one of three mutually exclusive classes: regular (relating to a = 1), local (relating to \(\gcd (a,b) = p^{k}\) for some rational prime p), and global (\(\gcd (a,b)\) is not a power of a prime). In each case, we examine the behavior of various invariants widely studied in the theory of nonunique factorizations. Our principal tool will be the construction of transfer homomorphisms from the M _a, b to monoids with simpler multiplicative structure.

Martin Kneser proved the following addition theorem for every abelian group G. If A, B ⊆ G are finite and nonempty, then \(\vert A + B\vert \geq \vert A + K\vert + \vert B + K\vert -\vert K\vert \) where \(K =\{ g \in G\mid g + A + B = A + B\}\). Here we give a short proof of this based on a simple intersection union argument.

We consider a partition of the subsets of the natural numbers \(\mathbb{N}\) into two classes, the lower class and the upper class, according to whether the representation function of such a subset A, counting the number of pairs of elements of A whose sum is equal to a given integer, is bounded or unbounded. We give sufficient criteria for two subsets of \(\mathbb{N}\) to be in the same class and for a subset to be in the lower class or in the upper class.

In the paper introducing the celebrated Falconer distance problem, Falconer proved that the Lebesgue measure of the distance set is positive, provided that the Hausdorff dimension of the underlying set is greater than \(\frac{d+1} {2}\). His result is based on the estimate where μ is a Borel measure satisfying the energy estimate \(I_{s}(\mu ) =\int \int \vert x - y\vert ^{-s}\) d μ(x)d μ(y) < ∞ for \(s > \frac{d+1} {2}\). An example due to Mattila ([15], Remark 4.5; [14]) shows in two dimensions that for no \(s < \frac{3} {2}\) does I _s (μ) < ∞ imply (1). His construction can be extended to three dimensions, but not to dimensions four and higher. Mattila’s example, as well as Falconer’s result, readily applies to the case when the Euclidean norm in (1) is replaced by a norm generated by a convex body with a smooth boundary and nonvanishing Gaussian curvature.

In this paper we prove, for all d ≥ 2, that for no \(s < \frac{d+1} {2}\) does I _s (μ) < ∞ imply (1) or the analogous estimate where the Euclidean norm is replaced by the norm generated by a particular convex body B with a smooth boundary and everywhere nonvanishing curvature. We also study the analog of the single distance problem in vector spaces over \(\mathbb{Z}_{q}\), the integers modulo q, and obtain a new geometric incidence result. Our constructions involve extending a two-dimensional combinatorial construction due to Valtr [20] who previously used to establish sharpness of some classical results in geometric combinatorics.

We review the basic theory of more sums than differences (MSTD) sets, specifically their existence, simple constructions of infinite families, the proof that a positive percentage of sets under the uniform binomial model are MSTD but not if the probability that each element is chosen tends to zero, and “explicit” constructions of large families of MSTD sets. We conclude with some new constructions and results of generalized MSTD sets, including among other items results on a positive percentage of sets having a given linear combination greater than another linear combination, and a proof that a positive percentage of sets are k-generational sum-dominant (meaning A, A + A, \(\ldots\), \(kA = A + \cdots + A\) are each sum-dominant).

By intersective set we mean a set H ⊂ Z having the property that it intersects the difference set A − A of any dense subset A of the integers. By analogy between the integers and the ring of polynomials over a finite field, the notion of intersective sets also makes sense in the latter setting. We give a survey of methods used to study intersective sets, known results and open problems in both settings.

We establish, utilizing the Hardy-Littlewood circle method, an asymptotic formula for the number of pairs of primes whose differences lie in the image of a fixed polynomial. We also include a generalization of this result where differences are replaced with any integer linear combination of two primes.

The sumset is one of the most basic and central objects in additive number theory. Many of the most important problems (such as Goldbach’s conjecture and Fermat’s last theorem) can be formulated in terms of the sumset S + S = { x + y: x, y ∈ S} of a set of integers S. A finite set of integers A is sum-dominant if | A + A |  >  | A − A | . Though it was believed that the percentage of subsets of \(\{0,\ldots,n\}\) that are sum-dominant tends to zero, in 2006 Martin and O’Bryant proved a very small positive percentage are sum-dominant if the sets are chosen uniformly at random (through the work of Zhao we know this percentage is approximately 4. 5 ⋅ 10⁻⁴). While most sets are difference-dominant in the integer case, this is not the case when we take subsets of many finite groups. We show that if we take subsets of larger and larger finite groups uniformly at random, then not only does the probability of a set being sum-dominant tend to zero but the probability that | A + A |  =  | A − A | tends to one, and hence a typical set is balanced in this case. The cause of this marked difference in behavior is that subsets of \(\{0,\ldots,n\}\) have a fringe, whereas finite groups do not. We end with a detailed analysis of dihedral groups, where the results are in striking contrast to what occurs for subsets of integers.

A beautiful theorem of Zeckendorf states that every integer can be written uniquely as a sum of nonconsecutive Fibonacci numbers \(\{F_{n}\}_{n=1}^{\infty }\); Lekkerkerker proved that the average number of summands for integers in [F _n , F _n+1) is \(n/(\varphi ^{2} + 1)\), with φ the golden mean. Interestingly, the higher moments seem to have been ignored. We discuss the proof that the distribution of the number of summands converges to a Gaussian as n → ∞, and comment on generalizations to related decompositions. For example, every integer can be written uniquely as a sum of the ± F _n ’s, such that every two terms of the same (opposite) sign differ in index by at least 4 (3). The distribution of the numbers of positive and negative summands converges to a bivariate normal with computable, negative correlation, namely \(-(21 - 2\varphi )/(29 + 2\varphi ) \approx -0.551058\).

This paper surveys some classical results about growth in finitely generated semigroups and applies results from additive number theory to construct families of finitely generated linear semigroups with intermediate growth.

We provide a solution to an open problem of Melvyn Nathanson, concerning the Grothendieck group associated to solutions of functional equations arising from multiplication of quantum integers, when the fields of coefficients of such solutions are of characteristic zero.

In this expository article we present an overview of the Plünnecke–Ruzsa inequality: the known proofs, some of its well-known applications and possible extensions. We begin with the graph-theoretic setting in which Plünnecke and later Ruzsa worked in. The more purely combinatorial proofs of the inequality are subsequently presented. In the concluding sections we discuss the sharpness of the various results presented thus far and possible extensions of the inequality to the non-commutative setting.

The Fermat quotient \(q_{p}(a):= (a^{p-1} - 1)/p\), for prime p∤ a, and the Wilson quotient \(w_{p}:= ((p - 1)! + 1)/p\) are integers. If p∣w _p , then p is a Wilson prime. For odd p, Lerch proved that \((\sum\nolimits_{a=1}^{p-1}q_{p}(a) - w_{p})/p\) is also an integer; we call it the Lerch quotient ℓ _p . If p∣ℓ _p we say p is a Lerch prime. A simple Bernoulli number test for Lerch primes is proven. There are four Lerch primes 3, 103, 839, 2237 up to 3 × 10⁶; we relate them to the known Wilson primes 5, 13, 563. Generalizations are suggested. Next, if p is a non-Wilson prime, then \(q_{p}(w_{p})\) is an integer that we call the Fermat-Wilson quotient of p. The GCD of all \(q_{p}(w_{p})\) is shown to be 24. If \(p\mid q_{p}(a)\), then p is a Wieferich prime base a; we give a survey of them. Taking a = w _p , if \(p\mid q_{p}(w_{p})\) we say p is a Wieferich-non-Wilson prime. There are three up to 10⁷, namely, 2, 3, 14771. Several open problems are discussed.

A generalized central trinomial coefficient T _n (b, c) is the coefficient of x ⁿ in the expansion of \((x^{2} + bx + c)^{n}\) with \(b,c \in \mathbb{Z}\). In this paper we investigate congruences and series for sums of terms related to central binomial coefficients and generalized central trinomial coefficients. The paper contains many conjectures on congruences related to representations of primes by certain binary quadratic forms, and 62 proposed new series for 1∕π motivated by congruences and related dualities.