nach oben

Erschienen in:

2014 | OriginalPaper | Buchkapitel

Finding and Counting MSTD Sets

verfasst von : Geoffrey Iyer, Oleg Lazarev, Steven J. Miller, Liyang Zhang

Erschienen in: Combinatorial and Additive Number Theory

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We review the basic theory of more sums than differences (MSTD) sets, specifically their existence, simple constructions of infinite families, the proof that a positive percentage of sets under the uniform binomial model are MSTD but not if the probability that each element is chosen tends to zero, and “explicit” constructions of large families of MSTD sets. We conclude with some new constructions and results of generalized MSTD sets, including among other items results on a positive percentage of sets having a given linear combination greater than another linear combination, and a proof that a positive percentage of sets are k-generational sum-dominant (meaning A, A + A, \(\ldots\), \(kA = A + \cdots + A\) are each sum-dominant).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Sharpness of Falconer’s Estimate and the Single Distance Problem in

Nächstes Kapitel Density Versions of Plünnecke Inequality: Epsilon-Delta Approach

Note that \(A + A + A - A = -(A - A - A - A)\); thus we might as well assume any linear combination has at least as many sums of A as differences of A.

Requiring 0, 2n − 1 ∈ A is quite mild; we do this so that we know the first and last elements of A.

As before, requiring 0, 2n − 1 ∈ A is quite mild and is done so that we know the first and last elements of A.

[DETZ97]

J.M. Deshouillers, G. Effinger, H. Te Riele, D. Zinoviev, A complete Vinogradov 3-primes theorem under the Riemann hypothesis. Electron. Res. Announc. Am. Math. Soc. 3, 99–104 (1997)CrossRefMATH

[FP73]

G.A. Freiman, V.P. Pigarev, The relation between the invariants R and T. in Number Theoretic Studies in the Markov Spectrum and in the Structural Theory of Set Addition (Russian) (Kalinin Gos. University, Moscow, 1973), pp. 172–174

[He07]

P.V. Hegarty, Some explicit constructions of sets with more sums than differences. Acta Arithmetica 130(1), 61–77 (2007)MathSciNetCrossRefMATH

[HM09]

P.V. Hegarty, S.J. Miller, When almost all sets are difference dominated. Random Struct. Algorithms 35(1), 118–136 (2009)MathSciNetCrossRefMATH

[HM10]

P.V. Hegarty, S.J. Miller, Appendix 2 of explicit constructions of infinite families of MSTD sets (by S. J. Miller and D. Scheinerman), in Additive Number Theory: Festschrift in Honor of the Sixtieth Birthday of Melvyn B. Nathanson, ed. by D. Chudnovsky, G. Chudnovsky (Springer, New York, 2010)

[ILMZ12]

G. Iyer, O. Lazarev, S.J. Miller, L. Zhang, Generalized more sums than differences sets. J. Number Theory 132(5), 1054–1073 (2012)MathSciNetCrossRefMATH

[KV00]

J.H. Kim, V.H. Vu, Concentration of multivariate polynomials and its applications. Combinatorica 20, 417–434 (2000)MathSciNetCrossRefMATH

[Ma69]

J. Marica, On a conjecture of conway. Can. Math. Bull. 12, 233–234 (1969)MathSciNetCrossRefMATH

[MO06]

G. Martin, K. O’Bryant, Many sets have more sums than differences, in Additive Combinatorics. CRM Proceedings and Lecture Notes, vol. 43 (American Mathematical Society, Providence, 2007), pp. 287–305

[MOS09]

S.J. Miller, B. Orosz, D. Scheinerman, Explicit constructions of infinite families of MSTD sets. J. Number Theory 130, 1221–1233 (2010)MathSciNetCrossRefMATH

[MPR12]

S.J. Miller, S. Pegado, S.L. Robinson, Explicit constructions of large families of generalized more sums than differences sets. Integers 12, #A30 (2012)

[Na96]

M.B. Nathanson, Additive Number Theory: The Classical Bases. Graduate Texts in Mathematics (Springer, New York, 1996)

[Na06]

M.B. Nathanson, Problems in additive number theory I, in Additive Combinatorics. CRM Proceedings and Lecture Notes, vol. 43 (American Mathematical Society, Providence, 2007), pp. 263–270

[Na07]

M.B. Nathanson, Sets with more sums than differences. Integers Electron. J. Combin. Number Theory 7, Paper A5 (24 pp.) (2007)

[Ru76]

I.Z. Ruzsa, On the cardinality of A + A and A − A, in Combinatorics year (Keszthely, 1976). Coll. Math. Soc. J. Bolyai, vol. 18 (North-Holland-Bolyai T \(\grave{\mathrm{a}}\) rsulat, Budaset, 1978), pp. 933–938

[Ru84]

I.Z. Ruzsa, Sets of sums and differences, in S \(\acute{\mathrm{e}}\) minaire de Th \(\acute{\mathrm{e}}\) orie des Nombres de Paris 1982–1983 (Birkh \(\ddot{\mathrm{a}}\) user, Boston, 1984), pp. 267–273

[Ru92]

I.Z. Ruzsa, On the number of sums and differences. Acta Math. Sci. Hungar. 59, 439–447 (1992)MathSciNetCrossRefMATH

[Sc90]

M.F. Schilling, The longest run of heads. College Math. J. 21(3), 196–207 (1990)MathSciNetCrossRefMATH

[TW95]

R. Taylor, A. Wiles, Ring-theoretic properties of certain Hecke algebras. Ann. Math. 141, 553–572 (1995)MathSciNetCrossRefMATH

[Vu00]

V.H. Vu, New bounds on nearly perfect matchings of hypergraphs: higher codegrees do help. Random Struct. Algorithms 17, 29–63 (2000)MathSciNetCrossRefMATH

[Vu02]

V.H. Vu, Concentration of non-Lipschitz functions and applications. Random Struct. Algorithms 20(3), 262–316 (2002)MathSciNetCrossRefMATH

[Wi95]

A. Wiles, Modular elliptic curves and Fermat’s last theorem. Ann. Math. 141, 443–551 (1995)MathSciNetCrossRefMATH

[Zh10]

Y. Zhao, Constructing MSTD sets using bidirectional ballot sequences. J. Number Theory 130(5), 1212–1220 (2010)MathSciNetCrossRefMATH

[Zh11]

Y. Zhao, Sets characterized by missing sums and differences. J. Number Theory 131, 2107–2134 (2011)MathSciNetCrossRefMATH

Titel: Finding and Counting MSTD Sets
verfasst von: Geoffrey Iyer
Oleg Lazarev
Steven J. Miller
Liyang Zhang
Verlag: Springer New York
Buch: Combinatorial and Additive Number Theory
Print ISBN: 978-1-4939-1600-9

Electronic ISBN: 978-1-4939-1601-6

Copyright-Jahr: 2014
DOI: https://doi.org/10.1007/978-1-4939-1601-6_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"