# On the union of arithmetic progressions

10 April 2014, a general meeting of AMU was held, which was addressed by Prof. Rom Pinchasi from Israel Institute of Technology with a report “On the union of arithmetic progressions”.

Abstract: We show that for every $$\varepsilon>0$$ there is an absolute constant $$c(\varepsilon)>0$$ such that the following is true: The union of any n arithmetic progressions, each of length n, with pairwise distinct differences must consist of at least $$c(\varepsilon)n^{2-\varepsilon}$$ elements. We show also that this type of bound is essentially best possible, as we observe $$n$$ arithmetic progressions, each of length n, with pairwise distinct differences such that their cardinality of their union is $$o(n^2)$$.

We develop some number theoretical tools that are of independent interest. In particular we give almost tight bounds on the following question: Given $$n$$ distinct integers $$a_1,…,a_n$$ at most how many pairs satisfy $$a_j/a_i\in [n]$$? More tight bounds on natural related problems will be presented.

This is joint work with Shoni Gilboa.

This entry was posted in Sessions. Bookmark the permalink.