On the number of popular differences
type: Item
instance of: scholarly article
title: On the number of popular differences
zbMATH Open document ID: 1210.11033
author: Sergei Konyagin
author: Vsevolod F. Lev
published in: Israel Journal of Mathematics
publication date: 2010-06-29T00:00:00Z
review text: The paper shows the existence of a \(c>0\) such that for any set of integers \(A\) with at least two elements, and any \(m<c|A|/\ln |A|\), there are at most \(m\) integers \(b>0\) satisfying \(|(A+b)\setminus A|\leq m\), or equivalently, there are at most \(m\) positive integers possessing \(|A|-m\) (or more) representation as a difference of two elements of \(A\). The result is the best possible in the sense that for each positive integer \(m\) there exists a finite set of integers \(A\) with \(|A|>m \log_2(m/2) \) such that \(|(A+b)\setminus A|\leq m\) holds for \(b=1,2,...,m+1\). For an alternative formulation of the main result, for finite subsets \(A\) and \(B\) of an abelian group write \(\mu_A(B)=\max \{ |(A+b)\setminus A| : b\in B\}\). The alternative formulation is that there is a (small) \(c>0\) such that \(\mu_A(B)\geq |B|\) holds for all finite subsets \(A,B\) of integers with \(|A|>1\) and \(|B|<c |A|/ \ln |A|\). Interestingly, the following, somewhat weaker result follows from Graham's famous g.c.d. conjecture, which was proved by \textit{R. Balasubramanian} and \textit{K. Soundararajan} [Acta Arith. 75, No. 1, 1--38 (1996; Zbl 0853.11002)]: \(\mu_A(B)\geq |B|\) holds for all finite subsets \(A,B\) of integers with \(|B|<c\sqrt{|A|}\).
reviewed by: László A. Székely
Mathematics Subject Classification ID: 11B75
Mathematics Subject Classification ID: 11B13
zbMATH DE Number: 5728350
zbMATH Keywords: representation as a difference
zbMATH Keywords: Graham's conjecture
zbMATH Keywords: partition into arithmetic progressions
MaRDI profile type: Publication
full work available at URL: s11856-010-0029-6
OpenAlex ID: W2057751510
cites work: On the addition of residue classes mod p
cites work: The Rearrangement of Positive Fourier Coefficients
cites work: Q4039929
cites work: Structure theorem for multiple addition and the Frobenius problem
cites work: Linear equations over \(\mathbb F_ p\) and moments of exponential sums.
cites work: Large sum-free sets in \(\mathbb Z/p\mathbb Z\)
cites work: An addition theorem modulo p
cites work: A Generalisation of the Theorem of Cauchy and Davenport
DOI: 10.1007/S11856-010-0029-6
Recommended article: Translation invariance in groups of prime order
Recommended article: Large sets in finite fields are sumsets
Recommended article: On zero-free subset sums
Recommended article: On the number of popular differences in \(\mathbb{Z} / p \mathbb{Z} \)
Recommended article: A Strong Form of a Problem of R. L. Graham
Recommended article: On the size of the set AA+A
Recommended article: Q3484902
Recommended article: On the integers of the form \(p+b\)
Recommended article: On the number of sums and differences
Recommended article: On additive representation functions
description: scientific article; zbMATH DE number 5728350