[PDF] Tau Numbers: A Partial Proof of a Conjecture and Other Results

14273_6zelinsky9.pdf

2311Article 02.2.8Journal of Integer Sequences, Vol. 5 (2002),

2 3 6 1 47

TauNumbers:APartialProofofa

ConjectureandOtherResults

JoshuaZelinsky

TheHopkinsSchool

NewHaven,CT06515

USA

Email:Lord

Bern@hotmail.com

Abstract.Apositiveniscalledataunumberif¿(n)jn,where¿isthenumber-of- divisorsfunction.Coltonconjecturedthatthenumberoftaunumbers·nisatleast1

2¼(n).

InthispaperIshowthatColton'sconjectureistrueforallsu±cientlylargen.Ialsoprove variousotherresultsabouttaunumbersandtheirgeneralizations.

1Introduction

KennedyandCooper[

3]de¯nedapositiveintegertobeataunumberif¿(n)jn,where¿

isthenumber-of-divisorsfunction.The¯rstfewtaunumbersare

1;2;8;9;12;18;24;36;40;56;60;72;80;:::;

itisSloane'ssequence A033950.Amongotherthings,KennedyandCoopershowedthetau numbershavedensityzero. TheconceptoftaunumberwasrediscoveredbyColton,whocalledthesenumbersrefac- torable[

1].ThispaperisprimarilyconcernedwithtwoconjecturesmadebyColton.Colton

conjecturedthatthenumberoftaunumberslessthanorequaltoagivennwasatleasthalf thenumberofprimeslessthanorequalton.InthispaperIshowthatColton'sconjectureis trueforallsu±cientlylargenbyprovingageneralizedversionoftheconjecture.Icalculate anupperboundforcounterexamplesof7:42¢1013. ColtonalsoconjecturedthattherearenothreeconsecutivetaunumbersandIshowthis tobethecase.Otherresultsarealsogiven,includingthepropertiesofthetaunumbersas comparedtotheprimes.Variousgeneralizationsofthetaunumbersarealsodiscussed. 1

2Basicresults

De¯nitions.Let¼(n)bethenumberofprimeslessthanorequalton.LetT(n)bethe numberoftaunumberslessthanorequalton. Usingthisnotation,Colton'sconjecturebecomes:T(n)¸¼(n)=2foralln. Beforeweproveaslightlyweakerformofthisconjecture,wementionsomefollowing minorpropertiesofthetaunumbers.

Throughoutthispaper,thefollowingbasicresult[

2,Theorem273]isusedextensively:

Proposition1.Ifn=pa11pa22¢¢¢pakkthen¿(n)=(a1+1)(a2+1)(a3+1)¢¢¢(ak+1).

Thenext¯vetheoremsareallduetoColton.

Theorem2.Anyoddtaunumberisaperfectsquare.

Proof.Assumethatnisanoddtaunumber.Letn=pa11pa22¢¢¢pakk.ByProposition 1and thede¯nitionoftaunumber(a1+1)(a2+1)(a3+1):::(ak+1)jn.Thereforeforany

0 nisraisedtoanevenpower,nisaperfectsquare. Theorem3.Anoddintegernisataunumberi®2nisataunumber. Proof.Ifn=pa11pa22¢¢¢pakk,then¿(2n)=2(a1+1)(a2+1)(a3+1)¢¢¢(ak+1)=2¿(n).Since

¿(n)jni®2¿(n)j2n,theresultfollows.

Theorem4.Ifgcd(m;n)=1andm;narebothtaunumbers,thenmnisataunumber. Proof.Thisresultfollowsimmediatelyfrom¿(mn)=¿(m)¿(n)whengcd(m;n)=1.

Theorem5.Therearein¯nitelymanytaunumbers.

Therearemanypossiblewaystoprovethisresult.However,usinganelegantmapping Coltonprovedthefollowingmoregeneraltheoremfromwhichtheabovefollows. Theorem6.Foranygiven¯nitenonemptysetofprimes,therearein¯nitelymanytau numberswithexactlythoseprimesastheirdistinctprimedivisors.

Proof.Thisresultfollowsfromconsideringthemapping:

f(n)=f(pa11pa22¢¢¢pakk)=ppa11¡1

1ppa22¡1

2¢¢¢ppakk¡1

k: Itiseasytoseethatthemappingproducesonlytaunumbers.

Theorem7.Everytaunumberiscongruentto0,1,2or4mod8.

Proof.ThisfollowsimmediatelyfromTheorems

2and3.

2

3NewResults

Wenowturntothenewresultsofthispaper.

First,wehaveaminor,elementaryresultwhichissimilartoColton'saboveresults. Theorem8.Letnbeataunumberandletpbethesmallestprimefactorofn.Ifqisprime andqjnthenqp¡1jn. Proof.Letnbeataunumberandletpbethesmallestprimefactorofn.Letqbeaprime whichdividesnandletqkbethelargestpowerofqwhichdividesn.Sincenisataunumber, k+1jn.Butpisthesmallestnon-trivialdivisorofnsok+1¸p.Hencek¸p¡1and thusqp¡1jn. ToprovethatColton's¯rstconjectureistrueforallsu±cientlylargenweconstructa subsetofthetaunumberswhichismuchdenserthantheprimes. Lemma9.Foranydistinctprimesp;q>3,thenumber36pqisataunumber. Proof.Bythemultiplicativepropertyofthetaufunction,¿(36pq)=¿(4)¿(9)¿(p)¿(q)=

3¢3¢2¢2=36.

Lemma10.Letkbeaninteger¸1.Thenthenumberofintegers·noftheformkp,where pisprime,isasymptoticton=(klogn).Similary,forany¯xedintegera¸1thenumbers ofintegers·noftheformkpaisasymptoticto((n=k)1=a)=log(n). Proof.Boththeseformulasfolloweasilyfromtheprimenumbertheorem. Lemma11.Letkbeapositiveinteger.Thenthenumberofnumbers·noftheformkpq, wherep;qaredistinctprimes,isasymptoticto(nloglogn)=(klogn).

Proof.WeuseaTheoremofHardyandWright[

2,Thm.437],whichstatesthatthenumber

ofsquarefreenumberslessthannwithkprimefactors,k¸2isasymptoticton(loglogn)k¡1 (k¡1)!logn. Settingk=2andusingthesametechniquesasintheproofforLemma10yieldsthedesired result. Lemma12.Thenumbersoftaunumbers·noftheform36pqwithp;qdistinctprimes >3isasymptoticto(nloglogn)=(36logn).

Proof.ByLemma

11thenumberofpositiveintegers·noftheform36pqisasymptoticto

nloglogn

36logn(1)

Thenumberoftaunumbersoftheform36pqwithp;qprimenumbers>3isthenumberof numbersoftheform36pqminusthenumberofnumbersoftheform36¢2¢por36¢3¢p.

Thus,using

1,togetherwithLemma11thenumberofsuchnumbersisasymptotically

nloglogn

36logn¡n72logn¡n108logn¡(2)

whichisasymptotictothe¯rstterm. 3 Lemma13.Forany¯xedrealnumberr<1wehaveT(n)>rnloglogn36lognforallnsu±ciently large.

Proof.ThisinequalityfollowsfromLemmas

12and9.

Theorem14.ForanyrealnumberkwehaveT(n)>k¼(n)forallnsu±cientlylarge. Proof.Clearlyforanypositiver<1,andanyk,forallsu±cientlylargen, rnloglogn

36logn>kn=logn:(3)

Since¼(n)»n=logn,forallsu±cientlylargen,rnloglogn

36logn>k¼(n).ByapplyingLemma13,

weconcludethatforallsu±cientlylargen,T(n)>k¼(n).

Corollary15.

Foranyb>0thereareatmosta¯nitenumberofintegersnsuchthatT(n)>b¼(n).

Proof.ThisresultfollowsimmediatelyfromTheorem

14. Corollary16.Thereareatmosta¯nitenumberofintegersnsuchthatT(n)<:5¼(n).

Proof.Letb=:5intheabovecorollary.

Theorem14alsoimpliesthatT(n)>¼(n)forallsu±cientlylargen.Coltongaveatable ofT(n)showingthatT(107)isabout:59¼(n).SoT(n)mustnotdrasticallyexceed¼(n) untilnbecomesverylarge.Thisisagoodexampleofthelawofsmallnumbers.Infact,we canconstructanevenbetterexampleofthelawofsmallnumbers. De¯nition.Anintegernisrareif¿(n)jn,¿(n)jÁ(n)and¿(n)j¾(n),whereÁ(n)isthe numberofintegerslessthanorequaltonandrelativelyprimeton,and¾(n)isthesumof thedivisorsofn. LetR(n)bethenumberofrarenumbers·n.Wecanuseaconstructionsimilarto theoneabovetoshowthatifp;qaredistinctprimes,notequalto2,3or7,then672pqis rare.Usingsimilarlogictothatabove,wecanconcludeforanyk,forallsu±cientlylarge n,R(n)>k¼(n).Thus,althoughthereareonlytworarenumberslessthan100(namely,1 and56)andthereare25primeslessthan100,forallsu±cientlylargen,R(n)>¼(n). Itwouldbeinterestingtoestablishagoodupperboundbeyondwhichthisinequal- ityalwaysholds.Intheaboveconstruction,wehave"cheated"slightlysincensuchthat ¿(n)j¾(n)havedensity1.Notethatwecouldhaveproventau-primedensityresultresult provingthatallnumbersoftheformkpqforanykexceedsthedensityoftheprimesjust likethoseoftheform36pqandthenlookingatthesubsetoftaunumbersoftheform36pq. Thereareothersequencesoftaunumberthatcouldhavebeenusedtothesamee®ect,such 4 asthoseoftheform80pqrwherep,qandrandaredistinctoddprimesnotequalto5.It isnotdi±culttogeneralizetheabovetheoremtoshowthatforanyk, ((nloglogn)k)=logn=o(T(n)):(4) FindinganactualasymptoticformulaforT(n)ismoredi±cult.Wecanaddressthis issuewithcertainheuristics.Weknowthat¿(n)isofaverageorderlogn.Sincenisatau numberwhennmod¿(n)=0andnmod¿(n)canhave¿(n)values,wewouldexpectthe probabilityofarandomintegertobeataunumbertobe1=log(n).However,integrating thisyieldsn=lognastheasymptoticvalue,whichistoolowevenifwemultiplyitbya constant.However,almostallintegershaveaboutlognlog2divisors[

2,p.265],andafew

integerswithlargetauvaluesbringuptheaverage.Ifweusethesamelogicasaboveand notethatalmostalltaunumbersaredivisibleby4,itmakessensetotake1/4thofthe integralof(logn)¡log2.Thuswearriveatthefollowingconjecturedrelation:

Conjecture17.

T(x)»(1=4)Z

x 3 logu¡log2du:(5) Thisconjecturegivesanapproximatevaluesof42854forT(106)and381659forT(107). Colton'stablegivesT(106)=44705andT(107)=394240.Ourheuristicapproximation seemstoslightlyunderestimatetheactualvalues,being95:8%and96:8%oftheactual values,respectively.Thisunderestimateisexpectedsincetheintegralapproximationignores thetaunumberscongruentto1or2mod4.Infact,weconjecturethatforallsu±ciently largentheintegralunderestimatesT(n).Sincetherelationshipbetween¿(n)and(logn)log2 isweak,itseemsmuchsafertoconjecturetheweaker: logT(x)»logµ1 4Z x 3 (logu)¡log2du¶ :(6) Itispossible,usingtheknownboundsforthevariousasymptoticformulasheretoobtain anactualupperboundabovewhichColton'sconjecturemustbetrue.Itisnotdi±cult, althoughcomputationallyintensive,touseafewdi®erentgeneratorsalongwith36toobtain aboundof1037.However,usingamoregeneralmethoditispossibletolowertheboundto slightlyover7¢1013. Lemma18.2jn=¿(n)i®foranyprimepsuchthatpdoesnotdividen,npisataunumber. Example:2j8=¿(8)=8=4=2and8pisataunumberforalloddprimesp.Theproof islefttothereader. De¯nition.Ataunumbernsuchthatforanyprimep,ifpdoesnotdividenthennpisa taunumber,iscalledap-generator.Anytaunumberoftheformnpissaidtobep-generated byn. 5 Thus,intheexampleabove,8isap-generator.ThusLemma18canberestatedas follows:nisap-generatori®2jn=¿(n).Inwhatfollows,bothformsofthislemmaareused interchangeably. Notation.Let!(n)denotethenumberofdistinctprimefactorsofn.Letg(n)denotethe largestprimefactorofn.LetG(n)=n(n+1)=2.LetPndenotethenthprime,withP1=2. Lemma19.Letkbeap-generator.Thenumberoftaunumbers·noftheformkpisat least¼(n=k)¡!(n):

Proof.Lefttothereader.

Lemma20.Ifa1;a2;:::asarep-generators,thenforanynthenumberoftaunumbers·n p-generatedbyanyaiisatleast s X i=1¼(n=ai)¡¼(g(ai)):(7)

Proof.TheprooffollowsfromLemma

18whenweobservethatforanyai;ajwherek=

¼(g(ai))+1andm=¼(g(aj))+1,thesetsfaiPk;aiPk+1;aiPk+2;:::gandfajPm;ajPm+1;ajPm+2;:::g havenocommonelements. Lemma21.Ifa1;a2;a3;:::arep-generatorsthenforanynthenumberoftaunumbers·n p-generatedbyanyaiisatleastA¼(n)¡BwhereA=Pk i=11=aiandB=Pk i=1(¼(g(ai))+1).

Proof.ThisprooffollowsimmediatelyfromLemma

19sinceeachsummandinAintroduces

anerrorofatmost1. Theorem22.Foralln>7:42¢1013wehaveT(n)>¼(n)=2.

Proof.IthasbeenshownbyDusart[

6]thatforalln>598,theinequality

(n=logn))(1+:992=logn)<¼(n)<(n=logn)(1+1:2762=logn) holds.Weuseallthep-generatorslessthanorequalto28653696togetherwithLemma 21
toobtainalowerboundforthenumberoftaunumbers,andthendemonstratethatforalln greaterthan7:42¢1013,thisexceeds:5(n=logn)(1+1:2762=logn)andthusexceeds:5¼(n). Usingasimplecomputerprogram,itisnotdi±culttocalculatethatthereareexactly413980 p-generatorslessthan28653696.TheirAvalueasinLemma

21isover:508:Itisnotdi±cult

toseethat B598¢28653696,wehaveT(n)>:508(n=logn)(1+:992=logn)¡8694520815. Foralln>1013:87;508(n=logn)(1+:992=logn)¡8694520815>:5(n=logn)(1+1:2762=logn). Since1013:87<7:42¢1013weconcludethatforalln>7:42¢1013,wehaveT(n)>:5¼(n). 6 Thehighdensityofthetaunumbersandtheirrelationshiptotheprimesmotivatesthe comparisonofthetwotypesofintegers. Theorem23.Thesumofthereciprocalsofthetaunumbersdiverges. Proof.Theresultfollowsimmediatelybyobservingthat8isap-generatorandthatthesum ofthereciprocalsoftheprimesdiverges. Thereisafamousstillunsolvedconjecture,byPolignac,thatforanypositiveeven integerk,thereexistprimesp;qsuchthatk=p¡q[

4].Itseemsreasonabletomakean

identicalconjectureaboutthetaunumbers.Indeed,theexistenceofin¯nitelymanyodd taunumbersmakesonewonderwhethereverypositiveintegeristhedi®erenceoftwotau numbers.However,therearesomeoddintegerswhicharenotthedi®erenceoftwotau numbersdespitethefactthatthedensityofthetaunumbersismuchhigherthanthatof theprimes. Theorem24.Theredonotexiststaunumbersa;bsuchthata¡b=5. Proof.Suppose,contrarytowhatwewanttoprove,thatthereexisttaunumbersa;bsuch thata¡b=5.ByTheorem

7weknowthateverytaunumberiscongruentto0;1;2or4

(mod8).Thus,wehaveb´4(mod8)anda´1(mod8).Hence4isthehighestpowerof twowhichdividesb.Thus¿(4)=3j¿(b),andsince¿(b)jbwegetb´0(mod3).Then a´2(mod3),whichisimpossiblesinceaisanoddtaunumberandhenceasquare. Goldbachmadetwofamousconjecturesabouttheadditivepropertiesoftheprimes. Goldbach'sstrongconjectureisthatanyevenintegergreaterthan4isthesumoftwo primes.Goldbach'sweakconjectureisthateveryoddintegergreaterthan7isthesumof thethreeoddprimes.Itiseasytoseethattheweakconjecturefollowsfromthestrong conjecture[ 4].

However,Colton'scongruenceresultsofTheorem

7implythatanyn´7(mod8)cannot

bethesumoftwotaunumbers. ThefollowingtheoremsandthenextconjecturearethetauequivalentsofGoldbach's conjecture. Theorem25.(a)IfGoldbach'sweakconjectureistruethananypositiveintegercanbe expressedasthesumof6orfewertaunumbers. (b)IfGoldbach'sstrongconjectureistruethaneverypositiveintegeristhesumof5or fewertaunumbers. Proof.(a)AssumeGoldbach'sweakconjecture.LetAbethesetofintegersnsuchthat8n isataunumberorn=0.Considerx=8kforsomeoddk>7.Sinceeveryoddprimeisan elementofA;k=a1+a2+a3forsomea1;a2;a3elementA.So8k=8a1+8a2+8a3.Since

8k=8mod16,weconcludethatforanyx´8mod16,xisthesumofatmostthreetau

numbers.Itiseasytoseefromthisresultandthefactthat1;2;8;9;12arealltau,thatany 7 integergreaterthan56canbeexpressedasthesumof6orfewertaunumbers.Itiseasyto verifythateveryintegerunder56canbeexpressedasthesumof6orfewertaunumbers. Thus,ifGoldbach'sweakconjectureistruethaneveryintegeristhesumof6orfewertau numbers.

Case(b)followsbysimilarreasoning.

Theorem26.Forallsu±cientlylargen,ncanbeexpressedasthesumof6orfewertau numbers. Proof.ThisresultfollowsfromapplyingVinogradov'sfamousresultthateverysu±ciently largeoddintegerisexpressibleasthesumofthreeorfewerprimesandusingthesame techniquesasintheprevioustheorem. Thetechniquesintheprevioustheoremscanalsobeusedtoprovethefollowingcorollary. Corollary27.IfGoldbach'sweakconjectureistruethananypositiveintegernotcongruent to7mod8canbeexpressedasthesumof5orfewertaunumbers.IfGoldbach'sstrong conjectureistruethaneverypositiveintegernotcongruentto7mod8isthesumof4or fewertaunumbers.

NotethatsincethesetAintroducedintheproofofTheorem

25containsmanyelements

otherthantheprimes,evenifeithertheweakorthestrongGoldbachconjecturesfailto hold,itisstillverylikelythatallintegerscanbeexpressedasthesumofsixorfewertau numbers.

Wemakethefollowing

Conjecture28.Everypositiveintegerisexpressibleasthesumof4orfewertaunumbers. Itseemsthattheaboveconjecturecannotbeprovenbymethodssimilartothoseused inTheorem 25.
Foranyn,Bertrand'spostulatestatesthatthereisaprimebetweennand2n.The equivalentfortaunumbersisthenexttheorem: Theorem29.Foranyintegern>5thereisalwaysataunumberbetweennand2n. Proof.Thisresultfollowsimmediatelyfromthefactthat8isap-generator. Anotherunsolvedproblemaboutprimesiswhetherthereisalwaysaprimebetweenn2 and(n+1)2.Thefactthatthetaunumbershaveamuchhigherdensitythantheprimes motivatesthefollowingconjectures: Conjecture30.Foranysu±cientlylargeintegern,thereexistsataunumbertsuchthat n

2 Conjecture31.Foranyintegern,thereexistataunumbertsuchthatn2·t·(n+1)2. 8 Dirichlet'sTheoremstatesthatwhengcd(a;b)=1thenthesetfn:an+bisprimeg isin¯nite.Thistheoremisequivalenttotherebeinganin¯nitenumberofprimesinany arithmeticprogressionasidefromcertaintrivialcases.Fortaunumberstheequivalent problembecomes: Conjecture32.Anyarithmeticprogressionofpositiveintegerswhichcontainsataunumber containsin¯nitelymanytaunumbers. Formanyarithmeticprogressionsthathavenotermsdivisibleby4,itisofteneasyto seethattheydonotcontainanytaunumbers,sincethesequencescontainalloddnon- quadraticresiduesmodsomek,ortwicesuchresidues.Examplesincludetheprogressions

3;7;11;15:::and6;14;22;30:::Therearemanyotherarithmeticprogressionswhichfailto

containtaunumbersandtheproofsrequirealittlearithmetic.Thearithmeticprogression

4;28;52;76:::isoneexample.

Theorem33.Ifn´4(mod24),thennisnotataunumber.

Proof.Letnbeataunumberandn´4(mod24).Then4isthehighestpowerof2dividing n,so3jnwhichisimpossible.

Theconceptofp-generatorscanbebegeneralized.

De¯nition.Foralistofpositiveintegersa1;a2;a3:::ak,nisan(a1;a2;:::ak)-generatorif forallk-tuplesofdistinctprimes(p1;p2;:::;pk)whichdonotdividen,npa11pa22¢¢¢pakkisa taunumber.Suchtaunumbersaresaidtobegeneratedbyn. Note:Wheneverconvenient,weassumetheaiintheabovede¯nitionareinincreasing order.Theearlierideaofthep-generatornowbecomesa(1)-generator.Underthisnotation Lemma

9canbereexpressedasfollows:36isa(1;1)-generator.

De¯nition.Ataunumbernissaidtobeaprimitivetaunumberifnisnotgeneratedby anyk. De¯nition.missaidtobeanancestorofnifmgeneratesnormgeneratesanancestorof n.Itisnotdi±culttoseethatthisrecursivede¯nitioniswell-de¯ned. Example:9isanancestorof180since180isgeneratedby36and36isgeneratedby9. De¯nition.Leth(n)bethenumberdistinctsetsofpositiveintegersgreaterthanonesuch thattheproductofalltheelementsofthesetisn. Thefollowingtheoremsummarizesthebasicpropertiesofgenerators.Nopartisdi±cult toproveandtheproofsarelefttothereader. Theorem34.(a)Thereexistin¯nitelymanyprimitivetaunumbers. (b)Foranya1;a2;a3:::ak>0thereexistin¯nitelymanynsuchthatnisa(a1;a2:::ak)- generator. 9 (c)Foranytaunumbern>2thereexista1;a2;a3:::aksuchthatnisan(a1;a2;a3:::ak)- generator.Inparticular,nisa(n=¿(n)¡1)-generator. (d)ApartfromtheorderoftheexponentsanygiventaunumberhasP djn=¿(n)h(d)gener- ators. (e)Ifforsomea1;a2;:::aknisan(a1;a2;:::;ak)-generatorthenforany0Conjecture35.Foranyk;limn!1Tk(n)=T(n)=0.

Aproofoftheaboveconjectureforevennisnotdi¯cultandislefttothereader.

Conjecture36.limn!1PT(n)=T(n)=0.

Theorem

34(c)and(d)motivateaninvestigationintothepropertiesofthefunction

t(n):=n=¿(n).Clearlythisfunctionisanintegeri®nisataunumber.Noteverypositive integerisintherangeoft(n). Toprovethatnoteveryintegerisintherangeoftweneedafewlemmas.

Lemma37.¿(n)<2n1=2foralln¸1.

Proof.Clearly,foranydivisordofn,ifd¸n1=2thenn=djnandn=d·n1=2Thuswecan makepairsofallthedivisorsofnwitheachonenumberofeachpairlessthann1=2.Since thereareatmostn1=2pairs,weget¿(n))<2n1=2.

Lemma38.Foralln;t(n)>:5n1=2.

Proof.ThisfollowsimmediatelyfromLemma

37.
Lemma39.Foranyrealnumberr,ifn=¿(n)·rthenn·4r2. 10

Proof.ThisfollowsimmediatelyLemma38.

Thenextlemmaiseasytoproveandtheproofisomitted.

Lemma40.Foranyprimep,taunumbern,andintegerk¸1,ifppk¡1jn=¿(n)then p pkjn.

Theorem41.Theredoesnotexistnsuchthatt(n)=18.

Proof.ByLemma

39wemerelyneedtoverifytheclaimforn·1296.UsingLemma40we

needonlytocheckthemultiplesof108whichiseasytodo. KennedyandCooper'sresultthatthetaunumbershavedensity0[3],alongwithLemma39, motivatesthefollowingconjecture: Conjecture42.Thereexistin¯nitelymanypositiveintegersksuchthatforalln,t(n)6=k. Wecanproveamuchweakerresultthantheaboveconjecture.Weshowthatthereare integerswhicharenotintherangeoft(2n+1).Firstweneedtwolemmascorresponding totheearlierlemmas.

Lemma43.Foranyoddintegern;¿(n)·dn1=2e.

Proof.Thisfollowsfromamodi¯cationofLemma

21.

Lemma43leadsdirectlytoLemma44:

Lemma44.Foranyoddintegern,t(n)¸bn1=2c.

Proof.ThisfollowsfromLemma

43.
Theorem45.Thereexistin¯nitelymanyoddintegersksuchthatt(n)6=kforalloddn. Speci¯cally,wheneverkisanoddprimegreaterthan3,t(n)6=kforalloddn:

Proof.Assumethatforsomeprimep>3,t(n)=p.SobyLemma

44,p>bn1=2c.So

p+1>n1=2andthusp2+2p+1¸n.Nowsincenisanoddtau,nisaperfectsquare.So p

2jn.Butn·p2+2p+1.Thusn=p2whichisimpossible.

Usingasimilarmethodastheproofofthelasttheorem,wegetthefollowingslightly strongerresult: Theorem46.Letpbeaprime>3.Letnbeataunumbersuchthatt(n)=p.Then4jn. Notethatsincealmostalltaunumbersaredivisibleby4,theaboveresultisafarcry fromConjecture

42.Infact,foranyoddprimepwehavet(8p)=p.

Coltonalsohasmadetheconjecturethatforanyn>2,thenumbern!=3isalwaysatau number.Thefollowingheuristicsuggestsarelatedconjecture: 11 Conjecture47.Foranypositiveintegersa;bwithaodd,thereexistsanintegerksuchthat (a=b)n!isataunumberforalln>k. Wegiveaheuristicreasontobelievethisconjecture.Letaandbbeintegers.Consider somenmuchlargerthanaandb.Nowonaverage,forsomeprimep,itiseasytoseethat themeannumberoftimespappearsinthefactorizationofnisabout1=(p¡1).Forlarge n,thechangemadebyaandbinthenumberoffactorsissmall.Soforanyprimepinthe factorizationof(a=b)n!,pisraisedtoapowerapproximatelyequalton=(p¡1).andthere areaboutn=lognprimes·n.Hencethehighestpowerofpdividing¿((a=b)n!))isabout n=((p¡1)logn).Forallsu±cientlylargen,n=(p¡1)ismuchlargerthann=((p¡1)logn). Sinceeveryprimeexponentof¿((a=b)n!))islessthanthecorrespondingexponentfor(a=b)n! weconcludethat¿((a=b)n!))j(a=b)n!. Note:Thereasonamustbeoddintheaboveconjectureissubtle.Letn=2k.Itisnot di±culttoseethat2n¡1jn!.Thusifahassomepowerof2dividingitthanonecanforce thepowerof2inan!tobeslightlyovern,suchas2n+2,inwhichcase(2k)+3j¿(an!)and 2 k+3maybeprimein¯nitelyoften,inwhichcase¿(an!)doesnotdividean!foranysuch k.Examplesotherthan2k+3wouldalsosu±ce.Itiseasytoseethatthisproblemonly ariseswith2andnotanyotherprimefactor. Wecanprovealargeportionofthisconjecture.We¯rstrequireafewde¯nitions. De¯nition.Letºp(n)denotethelargestintegerksuchthatpkjn. Lemma48.nisataunumberi®foranyprimep;ºp(¿(n))·ºp(n). Proof.Thisfollowsimmediatelyfromthede¯nitionofL. Lemma49.bn=pc·ºp(n!)·dn=(p¡1)e.Furthermore,ºp(n!)»n=(p¡1).

Proof.Theproofislefttothereader.

Lemma50.Foranypositiveintegersaandb,andprimep;ºp((a=b)n!)»n=(p¡1). Proof.Letaandbbepositiveintegersandpprime.Withoutlossofgeneralityassume gcd(a;b)=1.Foralln,ºp(n!)¡ºp(b)·ºp((a=b)n!)·ºp(n!)+ºp(a).Nowapplying Lemma

49,andnotingthatºp(b)andºp(a)areconstantwithrespectton,weconcludethat

º p((a=b)n!)»n=(p¡1). Theorem51.Letaandbbepositiveintegers,andpprime.Forallsu±cientlylargenthe highestpowerofpthatdivides¿((a=b)n!)alsodivides(a=b)n!.Thatis,ºp(¿((a=b)n!))· º p((a=b)n!). Proof.Letaandbbepositiveintegersandletpbeaprime.Withoutlossofgenerality assumegcd(a;b)=1.Wethusneedto¯nd,forallsu±cientlylargen,anupperbound U p(n)forºp(¿((a=b)n!))andshowthatthereisaconstantk<1suchthatforallsu±ciently largen,theinequalityUp(n)=(n=p)2. 12 CaseI:p=2.Thusweneedto¯ndanupperboundU2(n)forº2(¿((a=b)n!))such thatU2(n)=(n=p)2(¿((a=b)n!)).Thus

º

2(¿(a=b))n!·¼(n=2)(log2n)+¼(n)¡¼(n=2)+A1;(8)

whereA1issomeconstantdependingsolelyona.Nowapplyingtheprimenumbertheorem yields,forany²>0andallsu±cientlylargen, º

2(¿((a=b)n!))<(1+²)(nlog2n)

2logn+(1+²)n2logn;(9)

which,whenallthelogarithmsaremadenatural,becomes:Forany²>0andallsu±ciently largen, º

2(¿((a=b)n!))·(1+²)n

2log2+(1+²)n2logn(10)

Now¯x²assomenumberlessthan2log2¡1andletsucharesultingfunctionbeU2(n).It iseasytoseethatthefunctionsatis¯esthedesiredinequality. CaseII:Letp>2.Usingsimilarlogictothatusedintheearliercaseweconcludethat forany²>0andallsu±cientlylargen º

2(¿((a=b)n!))·(1+²)(n+p)(logpn)

plog((n+p)=p)·(1+²)(n+p)plogp(11) Fixing²assomenumberlessthanplogp¡1andmakingtherightmostpartof(

11)equal

toUp(n)givesthedesiredresult. NotethatonecouldusetheearliercitedboundsofDusarttomaketheaboveproof constructive.

4Generalizations

Itispossibletogeneralizetheconceptoftaunumber.Firstconsiderthatthede¯nitionof taunumberisequivalenttonmod¿(n)=0.Wenowsaythatnisataunumberrelative tokifnmod¿(n)=k.Ofcourse,k=0givestheordinarytaunumbersanditiseasyto seethateveryoddprimeisataunumberrelativeto1.Alsoitiseasytoseethatanynisa taunumberrelativetok,forsomek.Themainresultaboutintegerswhicharetaunumbers relativetokisthefollowingtheorem: Theorem52.Foranyoddkthereexistsanin¯nitelymanynsuchthatnisataunumber relativetok. 13 Proof.Letkbeanoddinteger.Weclaimthatthereexistarbitrarilylargedistinctprimes, p,qandrsuchthatpr¡1qmod¿(pr¡1q)=k.Thisisequivalenttoshowingthatpr¡1q´k (mod2r).ByFermat'sLittleTheorem,pr¡1´1(modr).Thuswemerelyneedtoshowthat thereexistarbitrarilylargeprimesqsuchthatq´k(mod2r),whichfollowsimmediately fromDirichlet'stheoremaboutprimesinarithmeticprogressions.

Imakethefollowingconjecture.

Conjecture53.Foranyk,thereexistin¯nitelymanynsuchthatnisataunumberrelative tok. Itisnotdi±culttoprovemanyspecialcasesofthisconjecturekwheresomepisassumed nottodividek,asinTheorem

51.Infactweshallprovetheaboveconjecturebyexamining

alargergeneralization: LetQ(n)beapolynomialwithintegercoe±cients.Anintegernissaidtobeatau numberrelativetoQ(n)if¿(n)jQ(n).Inthisgeneralization,taunumbersarethecase whereQ(n)=n. Clearlytheaboveconjecturefollowsfromthenexttheorem: Theorem54.ForanyQ(n)withintegercoe±cients,thereexistin¯nitelymanynsuchthat

¿(n)jQ(n).

Proof.Withoutlossofgenerality,assumetheleadingcoe±cientofQ(n)ispositive.Ifthe constanttermis0thenanytaunumberisataunumberrelativetoQ(n).Soassumethe constanttermisnon-zero.ChosesomecsuchthatQ(c)¸1and(Q(c);c)=1.Nowby Dirichlet'stheoremthereexistin¯nitelymanyprimespsuchthatp´c(modQ(c)).For anysuchp,pQ(c)¡1isataunumberforQ(n)since¿(pQ(c)¡1)=Q(c)andQ(c)jQ(p). Ifnisataunumber,then¿(n)hasasimilaraspossibleafactorizationtoninsome sense.Taunumbersmaximizegcd(n;¿(n)).Thismotivatesthefollowingde¯nition: De¯nition.Thepositiveintegernissaidtobeananti-taunumberifgcd(n;¿(n))=1. Noteanintegernisataunumberi®lcm(n;¿(n))=n.Thusinsomesense,anintegern isataunumberiflcm(n;¿(n))isminimized.Now,ifgcd(n;¿(n))=1thenlcm(n;¿(n))= n¿(n).Thustheanti-taunumbersrepresentthenumbersthatmaximizelcm(n;¿(n)). Notethatiftwotaunumbersarerelativelyprimethentheirproductisataunumber. Butasthepairs(3,4),(3,5)and(13,4)demonstrate,theproductoftworelativelyprimeanti- taunumberscanbeataunumber,ananti-taunumber,orneither.ThefollowingTheorem summarizesthebasicpropertiesofanti-taunumbers. Theorem55.(a)Theonlytaunumberthatisalsoananti-taunumberis1. (b)Ifaisanevenanti-taunumber,thenaisaperfectsquare. (c)Fora;b>1,gcd(a;b)=1aisataunumberandbisananti-taunumberthenabis neitherataunorananti-taunumber. 14 (d)Anyoddsquare-freenumberisananti-taunumber. (e)ForanyconstantintegerC,whereprimesa1;a2:::akarealllessthanCandthenfor someprimesdistinctp1;p2;::::::pkallgreaterthanC,thenforanypositiveintegers, b

1;b2:::bkthenumber(apb11¡1

1)(apb22¡1

2)¢¢¢(apbkk¡1

k)isananti-taunumber. Part(b)oftheabovetheoremshowsthattheanti-taunumbersareunlikethetaunumbers inmorethanoneway,sinceacorrespondingruleexistsabouttheoddtaunumbers.Part (c)canbeconsideredacancellationlawofsorts.Parts(d)and(e)motivatesthefollowing conjecture.LetAT(n)denotethenumberofnumbers·nthatareanti-taunumbers. Conjecture56.Foralln>3,theinequalityT(n)Proof.ThisfollowsimmediatelyfromTheorem

55(d)andthefactthatthesquarefree

numbershavedensity6=¼2. Theorem58.Forallsu±cientlylargen,T(n)2+1=2y2andwasabletoproduceotherrestrictiononthenecessarypropertiesofthe triplebasedonthiswell-knownequation. Theorem59.Ifaisanoddintegersuchthata;a+1aretaunumbersthena=1. Proof.Bytheabovecomments,wereallyneedtolookattheDiophantineequationx2+1=

2y2.Nowitisawellknownresultthatanyodddivisorofx2+1mustbecongruentto1

(mod4)[

5].Soeveryodddivisorof2y2mustbecongruentto1(mod4).But2y2isatau

number,soeveryoddprimeinitsfactorizationmustberaisedtoanexponentdivisibleby4 sinceotherwise2y2wouldbedivisiblesomenumberoftheform3mod4.Thus2y2=2w4 15 forsomew.Sowereallyneedtosolvex2+1=2w4.ThisisaDiophantineequationwhich hasonlythesolutions(x;w)=(1;1)and(x;w)=(239;13)[

7].Thesecondsolutionfailsto

yieldataunumberandsox=1. Theknownproofsthatthesearetheonlypositivesolutionsofthis¯nalDiophantine equationarequitelengthyandinvolved.Itwouldbeinterestingto¯ndawayofprovingthe desiredresultwithoutrelyingontheequation,orpossibly,asimpleproofthat(1,1)isthe onlytausolutionoftheequation.

5Acknowledgments

Theauthorwouldliketothanktherefereeforusefulcomments. TheauthorwouldalsolikethankJe®reyShallit,StephenDavidMiller,SimonColton, DavidSpeyer,GlennStevens,AaronandNathanielZelinsky,AaronMargolis,MogsWright, DavidMcCord,KevinHartandtherestoftheeversupportivemathdepartmentofthe

HopkinsSchoolinNewHaven,Connecticut.

References

[1]SimonColton,Refactorablenumbers|amachineinvention,JournalofIntegerSe- quences2,Article99.1.2,http://www.math.uwaterloo.ca/JIS/colton/joisol.html. [2]G.H.HardyandE.M.Wright,AnIntroductiontotheTheoryofNumbers,Oxford

UniversityPress,1985.

[3]R.E.KennedyandC.N.Cooper,Taunumbers,naturaldensity,andHardyandWright's Theorem437,Internat.J.Math.Math.Sci.13(1990),383{386. [4]PauloRibenboim,Catalan'sConjecture,Amer.Math.Monthly103(1996),529{538. [5]ShaileshA.Shirali,Afamilyportraitoftheprimes|acasestudyindiscrimination,

Math.Mag.70(1997),263{272.

[6]P.Dusart,Thekthprimeisgreaterthank(lnk+lnlnk¡1)fork>2,Math.Comp.68 (1999),411{415. [7]RaySteinerandNikosTzanakis,SimplifyingthesolutionofLjunggren'sequationx2+1=

2y4,J.NumberTheory37(1991)123{132.

2000MathematicsSubjectClassi¯cation:Primary11B05;Secondary11A25.

Keywords:taunumber,number-of-divisorsfunction

16 (ConcernedwithsequenceA033950.) ReceivedAugust1,2002;revisedversionreceivedDecember15,2002.PublishedinJournal ofIntegerSequencesDecember16,2002.Corrections,February17,2003.

ReturntoJournalofIntegerSequenceshomepage.

17

Politique de confidentialité -Privacy policy