Springer Proceedings in Mathematics & Statistics Melvyn B. Nathanson Editor Combinatorial and Additive Number Theory CANT 2011 and 2012 Springer Proceedings in Mathematics & Statistics Volume 101 Moreinformationaboutthisseriesathttp://www.springer.com/series/10533 Springer Proceedings in Mathematics & Statistics Thisbookseriesfeaturesvolumescomposedofselectcontributionsfromworkshops and conferences in all areas of current research in mathematics and statistics, includingORandoptimization.Inadditiontoanoverallevaluationoftheinterest, scientific quality, and timeliness of each proposal at the hands of the publisher, individual contributions are all refereed to the high quality standards of leading journals in the field. Thus, this series provides the research community with well-edited, authoritative reports on developments in the most exciting areas of mathematicalandstatisticalresearchtoday. Melvyn B. Nathanson Editor Combinatorial and Additive Number Theory CANT 2011 and 2012 123 Editor MelvynB.Nathanson DepartmentofMathematics LehmanCollege(CUNY) Bronx,NY,USA ISSN2194-1009 ISSN2194-1017(electronic) ISBN978-1-4939-1600-9 ISBN978-1-4939-1601-6(eBook) DOI10.1007/978-1-4939-1601-6 SpringerNewYorkHeidelbergDordrechtLondon LibraryofCongressControlNumber:2014950047 MathematicsSubjectClassification(2010):05-06,11-06,05A17,05A18,05A19,05C35,11B05,11B13, 11B30,11B75,20M05,20F69,20F65 ©SpringerScience+BusinessMediaNewYork2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface ThisvolumecontainsselectedpapersfromtworecentconferencesonCombinatorial andAdditiveNumberTheory(CANT2011andCANT2012). These meetings, which started in 2003, take place every year in May at the CUNYGraduateCenterinNewYork.Ithasbecometraditionaltoincludenotonly alargenumberofcontributedtalksbutalsoatleastoneseriesoftalksbyaninvited lecturer.Speakersareencouragednottopreparehighlytechnicaltalksintendedonly forthe“experts,”butto includeexpositoryandmotivationalmaterialandto tryto maketheirlecturescomprehensibletograduatestudentswhoarejustbeginningto think about research. For this reason, the conferences also include daily problem anddiscussionsessions. It is a pleasureto acknowledgethe supportof the NumberTheoryFoundation, which has, for many years, facilitated the participation of undergraduate and graduatestudentsintheseconferences. MelvynB.Nathanson v Contents GeneralizedRamanujanPrimes................................................ 1 NadineAmersi,OliviaBeckwith,StevenJ.Miller,RyanRonan, andJonathanSondow ArithmeticCongruenceMonoids:ASurvey.................................. 15 PaulBaginskiandScottChapman AShortProofofKneser’sAdditionTheoremforAbelianGroups......... 39 MattDeVos LowerandUpperClassesofNaturalNumbers............................... 43 L.HaddadandC.Helou TheProbabilityThatRandomPositiveIntegersAre3-Wise RelativelyPrime.................................................................. 55 JerryHu Sharpness ofFalconer’sEstimate andthe SingleDistance ProbleminZd .................................................................... 63 q AlexIosevichandStevenSenger FindingandCountingMSTDSets............................................. 79 GeoffreyIyer,OlegLazarev,StevenJ.Miller,andLiyangZhang DensityVersionsofPlünneckeInequality:Epsilon-DeltaApproach....... 99 RenlingJin ProblemsandResultsonIntersectiveSets .................................... 115 TháiHoàngLê PolynomialDifferencesinthePrimes.......................................... 129 NeilLyallandAlexRice vii viii Contents MostSubsetsAreBalancedinFiniteGroups................................. 147 StevenJ.MillerandKevinVissuet GaussianBehaviorinGeneralizedZeckendorfDecompositions............ 159 StevenJ.MillerandYinghuiWang Additive Number Theory and Linear Semigroups withIntermediateGrowth ...................................................... 175 MelvynB.Nathanson AdjoiningIdentitiesandZerostoSemigroups................................ 195 MelvynB.Nathanson On the Grothendieck Group Associated to Solutions of a Functional Equation Arising from Multiplication ofQuantumIntegers............................................................. 203 LanNguyen ThePlünnecke–RuzsaInequality:AnOverview ............................. 229 G.Petridis LerchQuotients,LerchPrimes,Fermat-WilsonQuotients, andtheWieferich-Non-WilsonPrimes2,3,14771........................... 243 JonathanSondow OnSumsRelatedtoCentralBinomialandTrinomialCoefficients ........ 257 Zhi-WeiSun Generalized Ramanujan Primes NadineAmersi,OliviaBeckwith,StevenJ.Miller,RyanRonan, andJonathanSondow Abstract In 1845, Bertrand conjectured that for all integers x (cid:2) 2, there exists at least one prime in .x=2;x(cid:2). This was proved by Chebyshev in 1860 and then generalized by Ramanujan in 1919. He showed that for any n (cid:2) 1, there is a (smallest) prime R such that (cid:3).x/ (cid:3) (cid:3).x=2/ (cid:2) n for all x (cid:2) R . In 2009 n n Sondow called R the nth Ramanujan prime and proved the asymptotic behavior n R (cid:4) p (where p is the mth prime). He and Laishram proved the bounds n 2n m p < R < p , respectively, for n > 1. In the present paper, we generalize 2n n 3n the intervalof interest by introducinga parameterc 2 .0;1/ and defining the nth c-Ramanujan prime as the smallest integer R such that for all x (cid:2) R , there c;n c;n are at least n primes in .cx;x(cid:2). Using consequences of strengthened versions of the Prime Number Theorem, we prove that R exists for all n and all c, that c;n Rc;n (cid:4) p n as n ! 1, and that the fraction of primeswhich are c-Ramanujan 1(cid:2)c convergesto1(cid:3)c.Wethenstudyfinerquestionsrelatedtotheirdistributionamong theprimesandseethatthec-Ramanujanprimesdisplaystrikingbehavior,deviating significantlyfromaprobabilisticmodelbasedonbiasedcoinflipping.Thismodel isrelatedtotheCramermodel,whichcorrectlypredictsmanypropertiesofprimes onlargescalesbuthasbeenshowntofailinsomeinstancesonsmallerscales. N.Amersi DepartmentofMathematics,UniversityCollegeLondon,GowerStreet, LondonWC1E6BT,UK e-mail:[email protected] O.Beckwith DepartmentofMathematics,EmoryUniversity,404DowmanDrive,Atlanta,GA30322 e-mail:[email protected] S.J.Miller((cid:2)) DepartmentofMathematicsandStatistics,WilliamsCollege,Williamstown,MA01267,USA e-mail:[email protected];[email protected] R.Ronan DepartmentofElectricalEngineering,CooperUnion,NewYork,NY10003,USA e-mail:[email protected] J.Sondow 209West97thStreet,NewYork,NY10025,USA e-mail:[email protected] ©SpringerScience+BusinessMediaNewYork2014 1 M.B.Nathanson(ed.),CombinatorialandAdditiveNumberTheory,Springer ProceedingsinMathematics&Statistics101,DOI10.1007/978-1-4939-1601-6__1