BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
A family A of k-subsets of {1,2,…,N} is a Sidon system if the sumsets A+B, A,B∈A are pairwise distinct. We show that the largest cardinality Fk(N) of a Sidon system of k-subsets of [N] satisfies Fk(N)≤(k−1N−1)+N−k and the asymptotic lower bound Fk(N)=Ωk(Nk−1). More precise bounds on Fk(N) are obtained for k≤3. We also obtain the threshold probability for a random system to be Sidon for k≥2.
For any positive integers h≥2 and g≥1, we present a greedy algorithm that provides an infinite Bh[g] sequence with an≤2gnh+(h−1)/g.
We construct a countable infinite graph G that does not contain cycles of length four having the property that the sequence of graphs Gn induced by the first n vertices has minimum degree δ(Gn)>n2−1+o(1).
Bourgain, Konyagin and Shparlinski obtained a lower bound for the size of the product set AB when A and B are sets of positive rational numbers with numerator and denominator less or equal than Q. We extend and slightly improve that lower bound using a different approach.
We study extremal problems about sets of integers that do not contain sumsets with summands of prescribed size. We analyse both finite sets and infinite sequences. We also study the connections of these problems with extremal problems of graphs and hypergraphs.
In the present paper we obtain several new results related to the problem of upper bound estimates for the number of solutions of the congruence xx≡λ(modp);x∈N,x≤p−1, where p is a large prime number, λ is an integer corpime to p. Our arguments are based on recent estimates of trigonometric sums over subgroups due to Shkredov and Shteinikov.
We study the probability that a cycle of length k in the lattice [1, n]^s does not contain more lattice points than the k vertices of the cycle. Then we generalize this problem to other configurations induced by a given graph H, introducting the chromatic zeta fuction of a graph.
We consider the possible visits to visible points of a random walker moving up and right in the integer lattice (with probability α and 1−α, respectively) and starting from the origin. We show that, almost surely, the asymptotic proportion of strings of k consecutive visible lattice points visited by such an α-random walk is a certain constant ck(α), which is actually an (explicitly calculable) polynomial in α of degree 2⌊(k−1)/2⌋. For k=1, this gives that, almost surely, the asymptotic proportion of time the random walker is visible from the origin is c1(α)=6/π2, independently of α.
In this paper, we study (random) sequences of pseudo s-th powers, as introduced by Erdös and Rényi in 1960. In 1975, Goguel proved that such a sequence is almost surely not an asymptotic basis of order s. Our first result asserts that it is however almost surely a basis of order s + x for any x > 0. We then study the s-fold sumset sA = A + ... + A (s times) and in particular the minimal size of an additive complement, that is a set B such that sA + B contains all large enough integers. With respect to this problem, we prove quite precise theorems which are tantamount to asserting that a threshold phenomenon occurs.
We use elementary methods to prove an incidence theorem for points and spheres in Fqn. As an application, we show that any point set of P⊂Fq2 with ∣P∣≥5q determines a positive proportion of all circles. The latter result is an analogue of Beck's Theorem for circles which is optimal up to multiplicative constants.
We study the length of the gaps between consecutive members in the sumset sA when A is a pseudo s-th power sequence, with s>1. We show that, almost surely, limsup (b_{n+1}-b_{n})/log (b_n) = s^s s!/Γ^s(1/s), where b_n are the elements of sA.
We construct a set of positive integers A in {1,..., n} with |A|>> n^{2/3} that does not contain Hilbert cubes of dimension 3. As a consequence we prove that ex(n; K^(3)(2,2,2))>> n^{8/3} where K^(3)(2,2,2) is the simplest complete 3-partite hypergraph. This is the first case of an improvement on the trivial lower bound for ex(n; L) when L is a complete r-partite hypergraph.
We present a new method to obtain infinite Sidon sequences, based on the discrete logarithm. We construct an infinite Sidon sequence A, with A(x)= x^{\sqrt 2-1+o(1)}. Ruzsa proved the existence of a Sidon sequence with similar counting function but his proof was not constructive. Our method generalizes to B_h sequences: For all h\ge 3, there is a B_h sequence A such that A(x)=x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}.
Let k≥1 be an integer. A set A⊂Z is a k-fold Sidon set if A has only trivial solutions to each equation of the form c1x1+c2x2+c3x3+c4x4=0 where 0≤∣ci∣≤k, and c1+c2+c3+c4=0. We prove that for any integer k≥1, a k-fold Sidon set A⊂[N] has at most (N/k)1/2+O((Nk)1/4) elements. Indeed we prove that given any k positive integers c1<⋯<ck, any set A⊂[N] that contains only trivial solutions to ci(x1−x2)=cj(x3−x4) for each 1≤i≤j≤k, has at most (N/k)1/2+O((ck2N/k)1/4) elements. On the other hand, for any k≥2 we can exhibit k positive integers c1,…,ck and a set A⊂[N] with ∣A∣≥(k1+o(1))N1/2, such that A has only trivial solutions to ci(x1−x2)=cj(x3−x4) for each 1≤i≤j≤k.
In this note we consider distinct distances determined by points in an integer lattice. We first consider Erdos's lower bound for the square lattice, recast in the setup of the so-called Elekes-Sharir framework \cite{ES11,GK11}, and show that, without a major change, this framework \emph{cannot} lead to Erdos's conjectured lower bound. This shows that the upper bound of Guth and Katz \cite{GK11} for the related 3-dimensional line-intersection problem is tight for this instance. The gap between this bound and the actual bound of Erdos arises from an application of the Cauchy-Schwarz inequality (which is an integral part of the Elekes-Sharir framework). Our analysis relies on two number-theoretic results by Ramanujan. We also consider distinct distances in rectangular lattices of the form {(i,j)∣0≤i≤n1−α, 0≤j≤nα}, for some 0<α<1/2, and show that the number of distinct distances in such a lattice is Θ(n). In a sense, our proof "bypasses" a deep conjecture in number theory, posed by Cilleruelo and Granville \cite{CG07}. A positive resolution of this conjecture would also have implied our bound.
We construct a set of positive integers A in {1,.., n} with |A|>> n^{2/3} that does not contain Hilbert cubes of dimension 3.
Erdös conjectured the existence of an infinite Sidon sequence of positive integers which is also an asymptotic basis of order 3. We make progress towards this conjecture in several directions. First we prove the conjecture for all cyclic groups Z_N with N large enough. In second place we prove by probabilistic methods that there is an infinite B_2[2] sequence which is an asymptotic basis of order 3. Finally we prove that for all c>0 there is a Sidon sequence which is an asymptotic basis of order 3+c,that is to say, any positive sufficiently large integer n can be written as a sum of 4 elements of the sequence, one of them smaller than n^c.
We study the typical behavior of the least common multiple of the elements of a random subset A⊂{1,…,n}. For example we prove that lcm{a: a∈A}=2n(1+o(1)) for almost all subsets A⊂{1,…,n}.
For h=3 and h=4 we prove the existence of infinite Bh sequences $\B$ with counting function B(x)=x(h−1)2+1−(h−1)+o(1). This result extends a construction of I. Ruzsa for B2 sequences.
We introduce several new methods to obtain upper bounds on the number of solutions of the congruences f(x)≡y(modp) and f(x)≡y2(modp), with a prime p and a polynomial f, where (x,y) belongs to an arbitrary square with side length M. We use these results and methods to derive non-trivial upper bounds for the number of hyperelliptic curves Y2=X2g+1+a2g−1X2g−1+...+a1X+a0 over the finite field $\F_p$ of p elements, with coefficients in a 2g-dimensional cube (a0,...,a2g−1)∈[R0+1,R0+M]×...×[R2g−1+1,R2g−1+M] that are isomorphic to a given curve and give an almost sharp lower bound on the number of non-isomorphic hyperelliptic curves with coefficients in that cube. Furthermore, we study the size of the smallest box that contain a partial trajectory of a polynomial dynamical system over $\F_p$.
We use Sidon sets to present an elementary method to study some combinatorial problems in finite fields, such as sum product estimates, solubility of some equations and distribution of sequences in small intervals. We obtain classic and more recent results avoiding the use of exponential sums, the usual tool to deal with these problems.
When A and B are subsets of the integers in [1,X] and [1,Y] respectively, with ∣A∣≥αX and ∣B∣≥βX, we show that the number of rational numbers expressible as a/b with (a,b) in A×B is ≫(αβ)1+εXY for any ε>0, where the implied constant depends on ε alone. We then construct examples that show that this bound cannot in general be improved to ≫αβXY. We also resolve the natural generalisation of our problem to arbitrary subsets C of the integer points in [1,X]×[1,Y]. Finally, we apply our results to answer a question of Sárközy concerning the differences of consecutive terms of the product sequence of a given integer sequence.
Let A be a set of integers and let h \geq 2. For every integer n, let r_{A, h}(n) denote the number of representations of n in the form n=a_1+...+a_h, where a_1,...,a_h belong to the set A, and a_1\leq ... \leq a_h. The function r_{A,h} from the integers Z to the nonnegative integers N_0 U {\infty} is called the representation function of order h for the set A. We prove that every function f from Z to N_0 U {\infty} satisfying liminf_{|n|->\infty} f (n)\geq g is the representation function of order h for some sequence A of integers, and that A can be constructed so that it increases "almost" as slowly as any given B_h[g] sequence. In particular, for every epsilon >0 and g \geq g(h,epsilon), we can construct a sequence A satisfying r_{A,h}=f and A(x)\gg x^{(1/h)-epsilon}.
A set A of positive integers is called a perfect difference set if every nonzero integer has an unique representation as the difference of two elements of A. We construct dense perfect difference sets from dense Sidon sets. As a consequence of this new approach, we prove that there exists a perfect difference set A such that A(x) >> x^{\sqrt{2}-1-o(1)}. We also prove that there exists a perfect difference set A such that limsup_{x\to \infty}A(x)/\sqrt x\geq 1/\sqrt 2.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.