Sharp Transitions in Making Squares (2009)
Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali
Supported by an NSF grant.
Open problems in additive combinatorics (2009)
Ernie Croot, F. Lev, Ernie Croot, Vsevolod F. Lev
Abstract. A brief historical introduction to the subject of additive combinatorics and a list of challenging open problems, most of which are contributed by the leading experts in the area, are...
Sharp Transitions in Making Squares (2009)
Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali
2 Partiellement soutenu par une bourse de la Conseil de recherches en sciences naturelles et en génie du Canada. 3
Sum-product inequalities with perturbation (2009)
Backman, Spencer, Croot, Ernie, Hart, Derrick, Hamel, Mariah
Suppose that A is a set of n real numbers, each at least 1 apart. Define the ``perturbed sum and product sets'' S and P to be the sums a + b + f(a,b) and products (a+g(a,b))(b+h(a,b)), where f, g,...
k-fold sums from a set with few products (2009)
In the present paper we show that if A is a set of n real numbers, and the product set A.A has at most n^(1+c) elements, then the k-fold sumset kA has at least n^(log(k/2)/2 log 2 + 1/2 - f_k(c))...
SUMS OF THE FORM 1/x k 1 + · · · + 1/x k n MODULO A PRIME (2009)
Using a sum-product result due to Bourgain, Katz, and Tao, we show that for every 0 < ɛ ≤ 1, and every integer k ≥ 1, there exists an integer N = N(ɛ, k), such that for every prime p and...
On sums and products in C[x] (2008)
We prove that there exists an absolute constant c > 0 such that for any set S of n monic polynomials of C[x], if the product set S.S has at most n^(1+c), then |S+S| >> n^2. We also prove an analogue...
Sharp Transitions in Making Squares (2008)
Croot, Ernie, Granville, Andrew, Pemantle, Robin, Tetali, Prasad
In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to rapidly determine a subsequence whose product is a square (which we call a...
A NEW PROOF OF ROTH’S THEOREM ON ARITHMETIC PROGRESSIONS (2008)
Abstract. We present a proof of Roth’s theorem that follows a slightly different structure to the usual proofs, in that there is not much iteration. Although our proof works using a type of density...
Borenstein, Evan, Croot, Ernie
In this paper we show that if one has a grid A x B, where A and B are sets of n real numbers, then there can be only very few ``rich'' lines in certain quite small families. Indeed, we show that if...
On a certain generalization of the Balog-Szemeredi-Gowers Theorem (2008)
Croot, Ernie, Borenstein, Evan
In this note, we prove a certain hypergraph generalization of the Balog-Szemeredi-Gowers Theorem. Our result shares some features in common with a similar such generalizsation due to Sudakov,...
Scott Contini, Ernie Croot, E. Shparlinski
Abstract. Given an integer n, how hard is it to find the set of all integers m such that ϕ(m) =n, whereϕ is the Euler totient function? We present a certain basic algorithm which, given the prime...
A new proof of Roth's theorem on arithmetic progressions (2008)
We present a proof of Roth's theorem that follows a slightly different structure to the usual proofs, in that there is not much iteration. Although our proof works using a type of density increment...
On sumsets and spectral gaps (2008)
Suppose that S ⊆ Fp, where p is a prime number. Let λ1,..., λp be the Fourier coefficients of S arranged as follows | ˆ S(0) | = |λ1 | ≥ |λ2 | ≥ · · · ≥ |λp|. Then, as is well known,...
On a certain generalization of the Balog-Szemeredi-Gowers theorem (2008)
The Balog-Szemerédi-Gowers theorem has a rich history, and is one of the most useful tools in additive combinatorics. It began with the a paper by Balog and Szemerédi [2], and then was refined by...
In [3], Erdős and Szemerédi proved the following result, which has led to a remarkable number of profound developments in the field of additive combinatorics: Theorem 1 There is some absolute...
Running time predictions for factoring algorithms (2008)
Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali
Partiellement soutenu par une bourse de la Conseil de recherches en sciences naturelles et en génie du Canada. 3 Supported in part by NSF Grant DMS-01-03635. In 1994, Carl Pomerance proposed the...
On sums and products in C[x] (2008)
Suppose that S is a subset of a ring R (in our case, the real or complex numbers), and define S.S: = {st: s, t ∈ S}, and S + S: = {s + t: s, t ∈ S}.
On sumsets and spectral gaps (2008)
Suppose that S ⊆ Fp, where p is a prime number. Let λ1,..., λp be the absolute values of the Fourier coefficients of S (to be made more precise below) arranged as follows ˆS(0) = λ1 ≥ λ2 ≥...
The structure of critical sets for F_p arithmetic progressions (2007)
Fix a prime p and a density 0 < d [0,1], what can one say about those which assign minimal weight to three-term arithmetic progressions -- that is, the sum of f(a)f(a+x)f(a+2x) is minimal as we sum...
Croot, Ernie, Elsholtz, Christian
It is well-known that any sequence of at least N integers contains a subsequence whose sum is 0 (mod N). However, there can be very few subsequences with this property (e.g. if the initial sequence...
Arithmetic structures in smooth subsets of F_p (2007)
Fix integers a_1,...,a_d satisfying a_1 + ... + a_d = 0. Suppose that f : Z_N -> [0,1], where N is prime. We show that if f is ``smooth enough'' then we can bound from below the sum of...
On Sumsets and Spectral Gaps (2007)
It is well known that if S is a subset of the integers mod p, and if the second-largest Fourier coefficient is ``small'' relative to the largest coefficient, then the sumset S+S is much larger than...
Suppose that f is a function from Z_p -> [0,1] (Z_p is my notation for the integers mod p, not the p-adics), and suppose that a_1,...,a_k are some places in Z_p. In some additive number theory...
Suppose that f : F_p^n -> [0,1] has expected value t in [p^(-n/9),1] (so, the density t can be quite low!). Furthermore, suppose that support(f) has no three-term arithmetic progressions. Then, we...
Arithmetic structures in smooth subsets of Fp (2007)
Suppose S ⊆ ZN: = Z/NZ, where N is a prime. A well-studied question for various types of sets S, is that of whether for a particular sequence of integers a1,..., ad satisfying a1 + · · · + ad =...
1 Introduction On equitable zero sums (2007)
Ernie Croot, Christian Elsholtz
There is a rich literature on conditions guaranteeing that certain sums of
Suppose that f: Fpn → [0, 1] satisfies Σaf(m) = θF ∈ [F 8/9, F], where F = |Fp n | = pn. In this paper we will show the following: Let fj denote the size of the jth largest Fourier coefficient...
On the Decay of the Fourier Transform and Three Term Arithmetic Progressions (2007)
In this paper we prove a basic theorem which says that if the tail of the spectral L 2 norm of a function f: Fpn → [0, 1] is sufficiently small (i.e. the function f is “sufficiently smooth”),...
On the Structure of Sets with Few Three-Term Arithmetic Progressions (2007)
Abstract. Fix a prime p ≥ 3, and a real number 0 < α ≤ 1. Let S ⊂ Fp n be any set with the least number of solutions to x + y = 2z (note that this means that x, z, y is an arithmetic...
On the Structure of Sets with Few Three-Term Arithmetic Progressions (2006)
Fix a density d in (0,1], and let F_p^n be a finite field, where we think of p fixed and n tending to infinity. Let S be any subset of F_p^n having the minimal number of three-term progressions,...
On the Decay of the Fourier Transform and Three Term Arithmetic Progressions (2006)
In this paper we prove a basic theorem which says that if f : F_p^n -> [0,1] has the property that ||f^||_(1/3) is not too ``large''(actually, it also holds for quasinorms 1/2-\delta in place of...
Sharp Transitions in Making Squares (2006)
Ernie Croot, Andrew Granville, Prasad Tetali
In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to determine a subsequence whose product is a square. A good model for how this...
Combinatorial Proof of the Hot Spot Theorem (2006)
A problem which has perplexed mathematicians for a long time, is to decide whether the digits of π are random-looking, or whether they contain some
Sharp Transitions in Making Squares (2006)
Ernie Croot, Andrew Granville, Prasad Tetali
In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to determine a subsequence whose product is a square. A good model for how this...
Smooth Numbers in Short Intervals (2006)
We show that for any ɛ> 0, there exists c> 0, such that for all x sufficiently large, there are x 1/2 (log x) − log 4−o(1) integers n ∈ [x, x + c √ x], all of whose prime factors are...
The Minimal Number of Three-Term Arithmetic Progressions Modulo a Prime Converges to a Limit (2006)
How few three-term arithmetic progressions can a subset S ⊆ ZN:= Z/NZ have if |S | ≥ υN? (that is, S has density at least υ). Varnavides [4] showed that this number of arithmetic-progressions...
Complexity of inverting the Euler function (2006)
Contini, Scott, Croot, Ernie, Shparlinski, Igor E
Given an integer n, how hard is it to find the set of all integers m such that φ(m) = n, where φ is the Euler totient function? We present a certain basic algorithm which, given the prime number...
ARITHMETIC PROGRESSIONS IN SPARSE SUMSETS (2005)
Ernie Croot, Imre Ruzsa, Tomasz Schoen
In this paper we show that sumsets A + B of finite sets A and B of integers, must contain long arithmetic progressions. The methods we use are completely elementary, in contrast to other works, which...
Long Arithmetic Progressions in Critical Sets (2005)
Given a density 0 < σ ≤ 1, we show for all sufficiently large primes p that if S ⊆ Z/pZ has the least number of three-term arithmetic progressions among all sets with at least σp elements,...
The Minimal Number of Three-Term Arithmetic Progressions Modulo a Prime Converges to a Limit (2004)
Given a density t in (0,1], and a prime p, let S be any subset of F_p having at least tp elements, and having the least number of three-term arithmetic progressions mod p among all subsets of F_p...
Complexity of Inverting the Euler Function (2004)
Contini, Scott, Croot, Ernie, Shparlinski, Igor
We present an algorithm to invert the Euler function $\phi(m)$. The algorithm, for a given $n \geq 1$, in polynomial time ``on average'', finds the set $\Psi(n)$ of all solutions $m$ to $\phi(m) =...
Sums of the Form 1/x_1^k + ... + 1/x_n^k Modulo a Prime (2004)
We show that for every $0 < \epsilon \leq 1$ and integer $k\geq 1$, there exists an integer $n = n(\epsilon,k)$ so that for all primes $p$, and integers $0 \leq a \leq p-1$, there exist integers $1...
Long Arithmetic Progressions in Critical Sets (2004)
In this paper we prove: If 0 < d < 1, and p is a sufficiently large prime, then if S is a subset of Z/pZ having the least number of three-term arithmetic progressions among all subsets of Z/pZ having...
k-term Arithmetic Progressions in Sumsets (2004)
In this paper we give a very elementary proof that if A and B are subsets of {1,2,...,N}, each having at least 5N^{1 - (4(k-1))^{-1}} elements, then the sumset A+B has a k-term arithmetic progression.
A Combinatorial Method for Counting Smooth Numbers in Sets of Integers (2003)
In this paper we present a method for producing asymptotic estimates for the number of integers in a given S having only ``small'' prime factors. The conditions that need to be verified are simpler...
Assuming the well-known conjecture that [x,x+x^t] contains a prime for t > 0 and x sufficiently large, we prove: For 0 < r < 1, there exists 0 < s < r < 1, 0 < d < 1, and infinitely many primes q...
Memory Efficient Arithmetic (2003)
In this paper we give an algorithm for computing the mth base-b digit (m=1 is the least significant digit) of an integer n (actually, it finds sharp approximations to n/b^m mod 1), where n is defined...
On Thin Sets of Primes Expressible as Sumsets (2002)
Croot, Ernie, Elsholtz, Christian
Suppose that P is an infinite set of primes such that P = A + B + C, where A,B,C are sets with at least two elements. We show that if P(x) > c x/log^d x (where P(x) = the number of elements of P that...
On Non-intersecting Arithmetic Progressions (2002)
We prove that if one has k non-intersecting arithmetic progressions of integers, with common differences 2
On the Oscillations of Multiplicative Functions Taking Values +/- 1 (2002)
For completely multiplicative functions f(n) taking values 1 and -1, under certain conditions on f(n) we show that f(n) changes sign at least x exp(-7(log log x)sqrt(log x)) times as n runs through...