Popular products and continued fractions
- PDF / 386,265 Bytes
- 29 Pages / 429.408 x 636.768 pts Page_size
- 81 Downloads / 180 Views
POPULAR PRODUCTS AND CONTINUED FRACTIONS
BY
Nikolay Moshchevitin Steklov Mathematical Institute, Gubkina 8, Moscow 119991, Russia e-mail: [email protected]
AND
Brendan Murphy School of Mathematics, University of Bristol University Walk, Bristol BS8 1TW, UK e-mail: [email protected]
AND
Ilya Shkredov Steklov Mathematical Institute, Gubkina 8, Moscow 119991, Russia e-mail: [email protected]
ABSTRACT
We prove bounds for the popularity of products of sets with weak additive structure, and use these bounds to prove results about continued fractions. Namely, considering Zaremba’s set modulo p, that is the set of all a such that ap = [a1 , . . . , as ] has bounded partial quotients, aj M , we obtain a sharp upper bound for the cardinality of this set.
Received August 21, 2018 and in revised form July 31, 2019
1
2
N. MOSHCHEVITIN, B. MURPHY AND I. SHKREDOV
Isr. J. Math.
1. Introduction This paper is about a variation of the sum-product problem, and the application of such results to problems on continued fractions. 1.1. The sum-product problem. The aim of the sum-product problem is to show quantitatively that a finite subset of a ring cannot be approximately closed under addition and multiplication, unless it is approximately a subring. Originally, Erd˝ os and Szemer´edi [15] considered a finite set A of integers and asked if A must grow under either addition or multiplication. More precisely, they considered the sum set A + A = {a + a : a, a ∈ A} and product set AA = {aa : a, a ∈ A} and asked if we must have max(|A + A|, |AA|) |A|1+δ for some δ > 0. Our first type of result shows that if the sum-set of A and B A + B = {a + b : a ∈ A, b ∈ B} is small, then the sum-set of the set of reciprocals A−1 with any other set C A−1 + C = {a−1 + c : a ∈ A, c ∈ C} must be large. These results work when B and C are much smaller than A. Theorem 1: Let A, B, and C be subsets of Fp . There is a constant b0 > 1 such that for all ε > 0, if δ = min(|B|, |C|) pε , then for all sufficiently large p we have |A + B| + |A−1 + C| min( p|A|, |A|pδ ).
1 −1/ε 4 b0
and
In fact, if we write W = (A + B) ∪ (A−1 + C), then we have (1)
|A| ≤
|W |2 + C∗ |W |p−δ(k) , p
where C∗ ≥ 6 is an absolute constant and δ(k) = 2−(k+2) , where k logmin(|B|,|C|) p. Similar results were proved in [49], and other results about sums of reciprocals were proved in [1] and [37].
Vol. TBD, 2020
POPULAR PRODUCTS AND CONTINUED FRACTIONS
3
Theorem 1 implies a bound for popular products. That is, if A + B is small, where B may be much smaller than A, then for all ρ = 0, |A ∩ ρA−1 | = |{(a, a ) ∈ A × A : aa = ρ}| = o(|A|). Corollary 2: There is a constant b0 > 1 such that the following holds for all −1/ε ε > 0 and δ = 14 b0 . Suppose that A, B ⊆ Fp , |A + B| ≤ σ|A|, and |B| ≥ pε . If ρ = 0, then σ 2 |A|2 σ|A| , δ . |A ∩ ρA−1 | max p p We prove a variant of Theorem 1 that applies when B and C are very small, but with the added requirement that B and C are intervals of consecutive numbers. Theorem 3: There is an absolute
Data Loading...
