Search

In 2005 Bourgain gave the first explicit construction of a two-source extractor family with min-entropy rate less than . His approach combined Fourier analysis with innovative but inefficient tools from arithmetic combinatorics and yielded an unspecified min-entropy rate which was greater than . This remained essentially the state of the art until a 2015 breakthrough by Chattopadhyay and Zuckerman in which they gave an alternative approach which produced extractors with arbitrarily small min-entropy rate. In the current work, we revisit the Fourier analytic approach. We give an improved analysis of one of Bourgain’s extractors which shows that it in fact extracts from sources with min-entropy rate near Moreover, we construct a variant of this extractor which we show extracts from sources with min-entropy rate near While this min-entropy rate is inferior to Chattopadhyay and Zuckerman’s construction, our extractors have the advantage of exponential small error, which is important in some applications. The key ingredient in these arguments is recent progress connected to the restriction theory of the finite field paraboloid by Rudnev and Shkredov. This in turn relies on a Rudnev’s point–plane incidence estimate, which in turn relies on Kollar’s generalization of the Guth–Katz incidence theorem.

Using GCD sums, we show that the set of the primes has small common multiplicative energy with an arbitrary exponentially big integer set $S$ and, in particular, size of any arithmetic progression in $S$ having the beginning at zero, is at most $O(\log |S| \cdot \log \log |S|)$. This result can be considered as an integer analogue of Vinogradov's question about the least quadratic non--residue. The proof rests on a certain repulsion property of the function $f(x)=\log x$. Also, we consider the case of general $k$--convex functions $f$ and obtain a new incidence result for collections of the curves $y=f(x)+c$., 15 pages

In this paper, we present a variant of the Balog-Szemer\'edi-Gowers theorem for the Vinogradov system. We then use our result to deduce a higher degree analogue of the sum-product phenomenon., Comment: To appear in Transactions of the American Mathematical Society. 31 pages

Given $d \in \mathbb{N}$, we establish sum-product estimates for finite, non-empty subsets of $\mathbb{R}^d$. This is equivalent to a sum-product result for sets of diagonal matrices. In particular, let $A$ be a finite, non-empty set of $d \times d$ diagonal matrices with real entries. Then for all $\delta_1 < 1/3 + 5/5277$, we have \[ |A+A| + |A\cdot A| \gg_{d} |A|^{1 + \delta_{1}/d}. \] In this setting, the above estimate quantitatively strengthens a result of Chang., Comment: A revised version will appear in Bulletin of the Australian Mathematical Society. 9 pages

We show that if \(h(x,y)=ax^2+bxy+cy^2\in \mathbb {Z}[x,y]\) satisfies \(\varDelta (h)=b^2-4ac\ne 0,\) then any subset of \(\{1,2,\ldots ,N\}\) lacking nonzero differences in the image of h has size at most a constant depending on h times \(N\exp (-c\sqrt{\log N})\), where \(c=c(h)>0\). We achieve this goal by adapting an \(L^2\) density increment strategy previously used to establish analogous results for sums of one or more single-variable polynomials. Our exposition is thorough and self-contained, in order to serve as an accessible gateway for readers who are unfamiliar with previous implementations of these techniques.

We investigate the relationships between several classical notions in arithmetic combinatorics and geometry including: the presence (or lack of) arithmetic progressions (or patches in dimensions $\geq 2$); the structure of tangent sets; and the Assouad dimension. We begin by extending a recent result of Dyatlov and Zahl by showing that a set cannot contain arbitrarily large arithmetic progressions (patches) if it has Assouad dimension strictly smaller than the ambient spatial dimension. Seeking a partial converse, we go on to prove that having Assouad dimension equal to the ambient spatial dimension is equivalent to having weak tangents with non-empty interior and to `asymptotically' containing arbitrarily large arithmetic patches. We present some applications of our results concerning sets of integers, which include a weak solution to the Erdos-Turan conjecture on arithmetic progressions.

We show how multiplicatively syndetic sets can be used in the study of partition regularity of dilation invariant systems of polynomial equations. In particular, we prove that a dilation invariant system of polynomial equations is partition regular if and only if it has a solution inside every multiplicatively syndetic set. We also adapt the methods of Green-Tao and Chow-Lindqvist-Prendiville to develop a syndetic version of Roth's density increment strategy. This argument is then used to obtain bounds on the Rado numbers of configurations of the form $\{x, d, x + d, x + 2d\}$., Comment: 29 pages. v3. Referee comments incorporated, accepted for publication in Acta Arithmetica

Let p be a large enough prime number. When A is a subset of Fp\{0} of cardinality |A|>(p+1)∕3, then an application of the Cauchy–Davenport theorem gives Fp\{0}⊂A(A+A). In this note, we improve on this and we show that |A|≥0.3051p implies A(A+A)⊇Fp\{0}. In the opposite direction we show that there exists a set A such that |A|>(18+o(1))p and Fp\{0}⊈A(A+A).

We prove an arithmetic regularity lemma for stable subsets of finite abelian groups, generalising our previous result for high-dimensional vector spaces over finite fields of prime order. A qualitative version of this generalisation was recently obtained by the first author in joint work with Conant and Pillay, using model-theoretic techniques. In contrast, the approach in the present paper is highly quantitative and relies on several key ingredients from arithmetic combinatorics.

Let $H$ be a multiplicatively written monoid with identity $1_H$ (in particular, a group). We denote by $\mathcal P_{\rm fin,\times}(H)$ the monoid obtained by endowing the collection of all finite subsets of $H$ containing a unit with the operation of setwise multiplication $(X,Y) \mapsto \{xy: x \in X, y \in Y\}$; and study fundamental features of the arithmetic of this and related structures, with a focus on the submonoid, $\mathcal P_{\text{fin},1}(H)$, of $\mathcal P_{\text{fin},\times}(H)$ consisting of all finite subsets $X$ of $H$ with $1_H \in X$. Among others, we prove that $\mathcal{P}_{\text{fin},1}(H)$ is atomic (i.e., each non-unit is a product of irreducibles) iff $1_H \ne x^2 \ne x$ for every $x \in H \setminus \{1_H\}$. Then we obtain that $\mathcal{P}_{\text{fin},1}(H)$ is BF (i.e., it is atomic and every element has factorizations of bounded length) iff $H$ is torsion-free; and show how to transfer these conclusions to $\mathcal P_{\text{fin},\times}(H)$. Next, we introduce "minimal factorizations" to account for the fact that monoids may have non-trivial idempotents, in which case standard definitions from Factorization Theory degenerate. Accordingly, we obtain conditions for $\mathcal P_{\text{fin},\times}(H)$ to be BmF (meaning that each non-unit has minimal factorizations of bounded length); and for $\mathcal{P}_{\text{fin},1}(H)$ to be BmF, HmF (i.e., a BmF-monoid where all the minimal factorizations of a given element have the same length), or minimally factorial (i.e., a BmF-monoid where each element has an essentially unique minimal factorization). Finally, we prove how to realize certain intervals as sets of minimal lengths in $\mathcal P_{\text{fin},1}(H)$. Many proofs come down to considering sumset decompositions in cyclic groups, so giving rise to an intriguing interplay with Arithmetic Combinatorics., Comment: 23 pp., 1 figure (on p. 4). Fixed minor details and added Sect. 2.4 and Remarks 4.2 and 4.6. To appear in Pacific Journal of Mathematics

We establish partition regularity of the generalised Pythagorean equation in five or more variables. Furthermore, we show how Rado's characterisation of a partition regular equation remains valid over the set of positive $k$th powers, provided the equation has at least $(1+o(1))k\log k$ variables. We thus completely describe which diagonal forms are partition regular and which are not, given sufficiently many variables. In addition, we prove a supersaturated version of Rado's theorem for a linear equation restricted either to squares minus one or to logarithmically-smooth numbers., Comment: v2. Funding updated

We extend a few fundamental aspects of the classical theory of non-unique factorization, as presented in Geroldinger and Halter-Koch's 2006 monograph on the subject, to a non-commutative and non-cancellative setting, in the same spirit of Baeth and Smertnig's work on the factorization theory of non-commutative, but cancellative monoids [J. Algebra 441 (2015), 475-551]. Then, we bring in power monoids and, applying the abstract machinery developed in the first part, we undertake the study of their arithmetic. More in particular, let $H$ be a multiplicatively written monoid. The set $\mathcal P_{\rm fin}(H)$ of all non-empty finite subsets of $H$ is naturally made into a monoid, which we call the power monoid of $H$ and is non-cancellative unless $H$ is trivial, by endowing it with the operation $(X,Y) \mapsto \{xy: (x,y) \in X \times Y\}$. Power monoids are, in disguise, one of the primary objects of interest in arithmetic combinatorics, and here for the first time we tackle them from the perspective of factorization theory. Proofs lead to consider various properties of finite subsets of $\mathbf N$ that can or cannot be split into a sumset in a non-trivial way, which gives rise to a rich interplay with additive number theory., 34 pp., no figures. Final version to appear in Journal of Algebra

This is an expository survey on recent sum-product results in finite fields. We present a number of sum-product or “expander” results that say that if \(|A| > p^{2/3}\), then some set determined by sums and product of elements of A is nearly as large as possible, and if \(|A

We define a necessary and sufficient condition on a polynomial $h\in \mathbb{Z}[x]$ to guarantee that every set of natural numbers of positive upper density contains a nonzero difference of the form $h(p)$ for some prime $p$. Moreover, we establish a quantitative estimate on the size of the largest subset of ${1,2,\dots,N}$ which lacks the desired arithmetic structure, showing that if deg$(h)=k$, then the density of such a set is at most a constant times $(\log N)^{-c}$ for any $c, Error in statement of Lemma 9 corrected, revision of published version

In this survey we review some old and new results on character sums and their applications to various problems in analytic number theory, e.g., smallest quadratic nonresidues, Dirichlet L-function, Linnik’s problem. We also discuss open problems in this area. Some of the techniques involved belong to arithmetic combinatorics. One may hope for these methods to lead to further progress.

This paper surveys and develops links between polynomial invariants of finite groups, factorization theory of Krull domains, and product-one sequences over finite groups. The goal is to gain a better understanding of the multiplicative ideal theory of invariant rings, and connections between the Noether number and the Davenport constants of finite groups.

For a given r -uniform hypergraph ${\cal F}$ **image** we study the largest blow-up of ${\cal F}$ **image** which can be guaranteed in every large r -uniform hypergraph with many copies of ${\cal F}$ **image** . For graphs this problem was addressed by Nikiforov, who proved that every n -vertex graph that contains Ω(nl) copies of the complete graph Kl must contain a complete l -partite graph with Ω(log n) vertices in each class. We give another proof of Nikiforov's result, make very small progress towards that problem for hypergraphs, and consider a Ramsey-type problem related to a conjecture of Erdős and Hajnal.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 (Part of this work was carried out at the Institute of Advanced Studies in Princeton during the special semester on Arithmetic Combinatorics in Fall 2007 organized by J. Bourgain and V. Vu.)

There is a parallelism between growth in arithmetic combinatorics and growth in a geometric context. While, over $\mathbb{R}$ or $\mathbb{C}$, geometric statements on growth often have geometric proofs, what little is known over finite fields rests on arithmetic proofs. We discuss strategies for geometric proofs of growth over finite fields, and show that growth can be defined and proven in an abstract projective plane -- even one with weak axioms., 10 pages

For a polynomial \({f\in{\mathbb {F}}_p[X]}\) , we obtain upper bounds on the number of points (x, f (x)) modulo a prime p which belong to an arbitrary square with the side length H. Our results in particular are based on the Vinogradov mean value theorem. Using these estimates we obtain results on the expansion of orbits in dynamical systems generated by nonlinear polynomials and we obtain an asymptotic formula for the number of visible points on the curve \({f(x)\equiv y\, ({\rm mod}\, p)}\) , where \({f\in{\mathbb {F}}_p[X]}\) is a polynomial of degree d ≥ 2. We also use some recent results and techniques from arithmetic combinatorics to study the values (x, f (x)) in more general sets.

The aim of this paper is to investigate the size properties of a planar set whose distance set has some prescribed arithmetic combinatorics. Such research is motivated by the conjecture that the disk has no more than 3 orthogonal exponentials. By proving a shifted version of Erdos-Solymosi’s theorem on the distance sets, we give some grounds on the conjecture. The results obtained here extend the corresponding results of Iosevich and Jaming in a simple manner.

Let $H$ be a commutative semigroup with unit element such that every non-unit can be written as a finite product of irreducible elements (atoms). For every $k \in \mathbb N$, let $\mathscr U_k (H)$ denote the set of all $\ell \in \mathbb N$ with the property that there are atoms $u_1, \ldots, u_k, v_1, \ldots, v_{\ell}$ such that $u_1 \cdot \ldots \cdot u_k = v_1 \cdot \ldots \cdot v_{\ell}$ (thus, $\mathscr U_k (H)$ is the union of all sets of lengths containing $k$). The Structure Theorem for Unions states that, for all sufficiently large $k$, the sets $\mathscr U_k (H)$ are almost arithmetical progressions with the same difference and global bound. We present a new approach to this result in the framework of arithmetic combinatorics, by deriving, for suitably defined families of subsets of the non-negative integers, a characterization of when the Structure Theorem holds. This abstract approach allows us to verify, for the first time, the Structure Theorem for a variety of possibly non-cancellative semigroups, including semigroups of (not necessarily invertible) ideals and semigroups of modules. Furthermore, we provide the very first example of a semigroup (actually, a locally tame Krull monoid) that does not satisfy the Structure Theorem., 34 pages, no figures; fixed minor details and made editorial changes; to appear in Journal of Algebra and its Applications

Additive combinatorics is the branch of combinatorics where the objects of study are subsets of the integers or of other abelian groups, and one is interested in properties and patterns that can be expressed in terms of linear equations. More generally, arithmetic combinatorics deals with properties and patterns that can be expressed via additions and multiplications. In the past ten years, additive and arithmetic combinatorics have been extremely successful areas of mathematics, featuring a convergence of techniques from graph theory, analysis and ergodic theory. They have helped prove long-standing open questions in additive number theory, and they offer much promise of future progress. Techniques from additive and arithmetic combinatorics have found several applications in computer science too, to property testing, pseudorandomness, PCP constructions, lower bounds, and extractor constructions. Typically, whenever a technique from additive or arithmetic combinatorics becomes understood by computer scientists, it finds some application. Considering that there is still a lot of additive and arithmetic combinatorics that computer scientists do not understand (and, the field being very active, even more will be developed in the near future), there seems to be much potential for future connections and applications.

We discuss a new direction in which the use of some methods from arithmetic combinatorics can be extended. We consider functions taking values in Euclidean space and supported on subsets of {1, 2, . . ., N}. In this context we present a proof of a natural generalization of Szemerédi's theorem. We also prove a similar generalization of a theorem of Sárkőzy using a vector-valued Fourier transform, adapting an argument of Green and obtaining effective bounds.

The main objective of this thesis is to present and prove Plünnecke's Inequality, a theorem that gives bounds for sumsets in commutative groups. An introduction to the theory of set addition is presented. Three different proofs of Plünnecke's Inequality are presented, two of them relying strongly on graph theory, the third being more elementary. Some other tools and techniques are introduced to obtain generalizations of Plünnecke's Inequality. The most important are the Plünnecke-Ruzsa Inequality, that gives bounds to general sum-and-difference sets in commutative groups, and some generalizations to the non-commutative case, related to Tao's Theorem. Some other generalizations involve the sum of different sets. The results are used to prove an important structural result.

It has been close to ten years since the publication of Green's influential survey Finite field models in additive combinatorics, in which the author championed the use of high-dimensional vector spaces over finite fields as a toy model for tackling additive problems concerning the integers. The path laid out by Green has proven to be a very successful one to follow. In the present article we survey the highlights of the past decade and outline the challenges for the years to come.

We present a unified framework to asymptotically count the number of sets, with a given cardinality, free of certain configurations. This is done by combining the hypergraph containers methodology joint with arithmetic removal lemmas. Several applications involving linear configurations are described, as well as some applications in the random sparse setting.

In this paper we establish new estimates on sum-product sets and certain exponential sums in finite fields of prime order. Our first result is an extension of the sum-product theorem from [8] when sets of different sizes are involed. It is shown that if [Formula: see text] and pε < |B|, |C| < |A| < p1-ε, then |A + B| + |A · C| > pδ (ε)|A|. Next we exploit the Szemerédi–Trotter theorem in finite fields (also obtained in [8]) to derive several new facts on expanders and extractors. It is shown for instance that the function f(x,y) = x(x+y) from [Formula: see text] to [Formula: see text] satisfies |F(A,B)| > pβ for some β = β (α) > α whenever [Formula: see text] and |A| ~ |B|~ pα, 0 < α < 1. The exponential sum ∑x∈ A,y∈Bεp(axy+bx2y2), ab ≠ 0 ( mod p), may be estimated nontrivially for arbitrary sets [Formula: see text] satisfying |A|, |B| > pρ where ρ < 1/2 is some constant. From this, one obtains an explicit 2-source extractor (with exponential uniform distribution) if both sources have entropy ratio at last ρ. No such examples when ρ < 1/2 seemed known. These questions were largely motivated by recent works on pseudo-randomness such as [2] and [3]. Finally it is shown that if pε < |A| < p1-ε, then always |A + A|+|A-1 + A-1| > pδ(ε)|A|. This is the finite fields version of a problem considered in [11]. If A is an interval, there is a relation to estimates on incomplete Kloosterman sums. In the Appendix, we obtain an apparently new bound on bilinear Kloosterman sums over relatively short intervals (without the restrictions of Karatsuba's result [14]) which is of relevance to problems involving the divisor function (see [1]) and the distribution ( mod p) of certain rational functions on the primes (cf. [12]).