Additive Number Theory (eBook)

Preface 6
Contents 10
Addictive Number Theory 14
A True Story 14
Remarks on Some of My Articles 15
References 19
Sum-Product Theorems and Applications 22
Introduction 22
0 Sum-Product Theorem in Fp 23
1 Preliminaries from Additive Combinatorics 23
2 Some Tools from Graph Theory: The Balog--Szemerédi--Gowers Theorem 27
3 Exponential Sum Estimate 29
4 Additive Relations in Multiplicative Groups 34
5 Multilinear Exponential Sums 38
6 Extensions to 'Almost Groups' 
39 
7 Sum-Product Theorem and Gauss Sums in Arbitrary Finite Fields 39
8 The Case of General Polynomial (mod p) 40
9 The Sum-Product in Zq =Z/qZ 42
10 Exponential Sums in Finite Commutative Rings 44
11 Euclidean Algorithm in Algebraic Number Fields 45
12 Application to QUE 47
References 50
Can You Hear the Shape of a Beatty Sequence? 52
1 Introduction 52
2 Proofs 55
2.1 Proof of Theorem 1 55
2.2 Proof of Theorem 2 56
2.3 Proof of Theorem 3 58
2.4 Rasmussen's Approach to Conjecture 1 60
2.5 Proof of Theorem 4 62
3 Open Questions Concerning Generalized Polynomials 64
References 65
Variance of Signals and Their Finite Fourier Transforms 66
1 Eigenvalue and Eigenvectors of the Finite Fourier Matrix 66
1.1 McClellan Basis 68
1.2 Carlitz/Morton Basis 69
1.3 Dickinson--Steiglitz or Hofstatder Basis 70
2 Discrete Analogs 72
3 Theta Function Expressions for the Fourier Eigenvectors 72
4 Variational Principles for the Determination of Eigenfunctions of the Discrete Fourier Transform 
76 
5 Discrete Uncertainty Principle 79
6 Explicit expressions for the matrix Mw2 in the Discrete 
 
80 
7 Theta Function Bounds for Minimal Eigenvalues 
 
82 
8 Numerical Evaluation of the Minimal Eigenvalues in the Discrete Uncertainty Principle 
85 
9 Extensions of the Heisenberg-Weyl Inequality in the Continuous and Discrete Cases 
85 
9.1 The Dickenson-Steiglitz Basis as Derived from Variational Principles 
88 
References 88
Sparse Sets in Time and Frequency Related to Diophantine Problems and Integrable Systems 90
The Hilbert Matrix and Related Operators 90
General Prolate Functions 91
General Prolate Functions and Commuting Differential Operators 
93 
Szego Problem and Concentrated Polynomials 
94 
Hilbert Matrix and a Commuting Differential Operator 96
Szego Problem and Arbitrary Unions of Intervals 
97 
Garnier Isomonodromy Deformation Equations 98
Explicit Expressions for the Non-Linear Darboux Transform 100
Darboux Transformation for m = 3 Case 
103 
Generalized Prolate Functions and Another Isomonodromy Problem 
104 
Generalized Prolate Matrices 104
Eigenvalue Problems for Hankel Matrices and Fourth Order Differential Equations 
105 
Variational Principles and q: Difference Equations 108
References 110
Addition Theorems in Acyclic Semigroups 112
1 Introduction 112
2 Cayley Graphs on Semigroups 113
3 Vosper's Theorem 116
References 117
Small Sumsets in Free Products of z/2z 
118 
1 Introduction 118
2 The Function kG(r,s) 
119 
3 Free products of groups 120
4 Proof of m G(r,s) k G(r,s) 
121 
5 Optimality 124
6 Proof of m G(r,s) k G(r,s) 
125 
References 126
A Combinatorial Approach to Sums of Two Squares and Related Problems 127
1 Introduction 127
1.1 The Sums of Two Squares Theorem 127
1.2 Zagier's Proof 130
1.3 Heath-Brown's Proof 
130 
1.4 Grace' Lattice Point Proof 131
1.5 Lucas' Work on Regular Satins 132
1.6 A Short Proof 132
1.6.1 The Long Version 132
1.6.2 A Short Version of the Proof 135
2 How Zagier's Involution can be Motivated 136
2.1 First Motivaton 136
2.2 Making the Proof Constructive 138
2.3 A Motivation Due to Dijkstra 139
2.4 Comparison 140
3 Generalization of the Method 141
3.1 d = 0 
143 
3.2 d = 1 
143 
3.3 d = 2 
143 
3.3.1 The Case p=x2 +2yz 143
3.3.2 Proof of Theorem 3 145
3.4 d = 3 
147 
3.4.1 The Case p = 3x2+4y2 
147 
3.4.2 Proof of Theorem 4 148
3.5 d = 4 
149 
4 On Infinite but Incomplete Mappings 
149 
References 151
A Note on Elkin's Improvement of Behrend's Construction 153
1 Introduction 153
2 The Proof 154
3 A Question of Graham 156
References 156
Distinct Matroid Base Weights and Additive Theory 157
1 Introduction 157
2 Terminology and Preliminaries 160
3 Proof of the Main Result 161
References 162
The Postage Stamp Problem and Essential Subsets in Integer Bases 164
1 Essential Subsets of Integer Bases 164
2 The Postage Stamp Problem 167
3 Proof of Theorem 1.1 170
4 Proof of Theorem 1.2 172
5 Discussion 179
References 179
A Universal Stein-Tomas Restriction Estimate for Measures in Three Dimensions 181
1 Introduction 181
2 Reduction to the Key Geometric Estimate 183
3 Proof of Theorem 1 and Corollary 1 184
4 Geometric Estimates: Proof of Corollary 2 185
References 188
On the Exact Order of Asymptotic Bases and Bases for Finite Cyclic Groups 189
1 Exact Asymptotic Bases 190
2 Subsets of Exact Asymptotic Bases 190
3 Exact Order of Asymptotic Bases 192
4 Postage Stamp Problem 194
5 Extremal Bases for Finite Cyclic Groups 197
6 Remarks and Open Problems 198
References 200
The Erdos-Turán Problem in Infinite Groups 
204 
1 The Background 205
2 The Results 205
3 The Proofs 206
References 211
A Tiling Problem and the Frobenius Number 212
1 Introduction 212
2 Tiling Tori 214
3 Tiling Rectangles 222
3.1 Cube Tiles 226
References 229
Sumsets and the Convex Hull 230
1 Introduction 230
2 A Simplicial Decomposition 232
3 The Case of a Simplex 233
4 The General Case 235
References 236
Explicit Constructions of Infinite Families of MSTD Sets 237
1 Introduction 238
2 Construction of Infinite Families of MSTD Sets 241
3 Lower Bounds for the Percentage of MSTDs 243
4 Concluding Remarks and Future Research 246
Appendix 1: Size of S( 
r) 248
Appendix 2:When Almost ALL Sets are not MSTD Sets 
249 
References 255
An Inverse Problem in Number Theory and Geometric Group Theory 257
1 From Compact Sets to Integers 257
2 The Inverse Problem 258
3 Relatively Prime Sets of Lattice Points 263
Appendix: The Fundamental Observation of Geometric 
 
264 
References 266
Cassels Bases 267
1 Additive Bases of Finite Order 267
2 A Lower Bound for Bases of Finite Order 269
3 Raikov-Stöhr Bases 270
4 Construction of Thin g-adic Bases of Order h 272
5 Asymptotically Polynomial Bases 276
6 Bases of Order 2 278
7 Bases of Order h 3 285
8 Notes 292
References 292
Asymptotics of Weighted Lattice Point Counts Inside Dilating Polygons 294
1 Introduction 294
2 The Algebraic Case 295
3 An Almost Everywhere Result 304
4 Concluding Remarks 307
References 307
Support Bases of Solutions of a Functional Equation Arising From Multiplication of Quantum Integers and the Twin Primes Conjecture 
309 
1 Introduction 309
2 Main Results 314
3 Proof of Main Results 314
References 322
Exponential Sums and Distinct Points on Arcs 324
1 Introduction 324
2 Three Theorems 325
3 Two Proofs of Freiman's Lemma 327
3.1 First Proof 327
3.2 Second Proof 328
4 Proof of Theorem 3 329
4.1 Notation 329
4.2 Arcs 329
4.3 Assumptions 329
4.4 Geometric Progressions 330
4.5 Compactness/Continuity 330
4.6 Dispersion 330
4.7 Perturbation 330
4.7.1 Case I 331
4.7.2 Case II 332
4.8 Primary Points 332
4.9 Secondary Points 333
5 Closing Remarks 333
References 335
New Vacca-Type Rational Series for Euler's Constant and Its ''Alternating'' Analog ln4 
336 
1 Introduction 336
2 Proofs 339
3 Open Problems 343
References 344
Mixed Sums of Primes and Other Terms 346
1 Introduction 346
2 Proofs of Theorems 1.3 and 1.9 351
3 Discussion of Conjecture 1.5 and Its Variants 354
References 357
Classes of Permutation Polynomials Based on Cyclotomy and an Additive Analogue 359
1 Introduction 359
2 Permutation Polynomials from Cyclotomy 360
3 Permutation Polynomials from Additive Cyclotomy 361
References 364