2002/10/03 by Greg Martin, Kevin O’Bryant, Martin, Greg +2
Computer Science · Mathematics · #11P70 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT) #math.CO #math.NT #msc:11P70
paper · pdf · doi:10.48550/arxiv.math/0210041
66 pages, 8 figures, 3 tables; formatting improved
openalex publication_date 2002/10/03 · arxiv created 2002/10/05 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A symmetric subset of the reals is one that remains invariant under some reflection x --> c-x. Given 0 < x < 1, there exists a real number D(x) with the following property: if 0 < d < D(x), then every subset of [0,1] with measure x contains a symmetric subset with measure d, while if d > D(x), then there exists a subset of [0,1] with measure x that does not contain a symmetric subset with measure d. In this paper we establish upper and lower bounds for D(x) of the same order of magnitude: for example, we prove that D(x) = 2x - 1 for 11/16 < x < 1 and that 0.59 x2 < D(x) < 0.8 x2 for 0 < x < 11/16. This continuous problem is intimately connected with a corresponding discrete problem. A set S of integers is called a B*[g] set if for any given m there are at most g ordered pairs (s1,s2) ∈ S × S with s1+s2=m; in the case g=2, these are better known as Sidon sets. We also establish upper and lower bounds of the same order of magnitude for the maximal possible size of a B*[g] set contained in 1,...,n, which we denote by R(g,n). For example, we prove that R(g,n) < 1.31 √(gn) for all n > g > 1, while R(g,n) > 0.79 √(gn) for sufficiently large integers g and n. These two problems are so interconnected that both continuous and discrete tools can be applied to each problem with surprising effectiveness. The harmonic analysis methods and inequalities among various Lp norms we use to derive lower bounds for D(x) also provide uniform upper bounds for R(g,n), while the techniques from combinatorial and probabilistic number theory that we employ to obtain constructions of large B*[g] sets yield strong upper bounds for D(x).