Problem som involverar aritmetiska progressioner
Problem som involverar aritmetiska progressioner är av intresse i talteori , kombinatorik och datavetenskap , både ur teoretisk och tillämpad synvinkel.
Största progressionsfria delmängder
Hitta kardinaliteten (betecknad med A k ( m )) för den största delmängden av {1, 2, ..., m } som inte innehåller någon progression av k distinkta termer. Delarna i de förbjudna stegen behöver inte vara konsekutiva.
Till exempel, A 4 (10) = 8, eftersom {1, 2, 3, 5, 6, 8, 9, 10} inte har några aritmetiska fortgångar med längd 4, medan alla 9-elements delmängder av {1, 2, . .., 10} har en. Paul Erdős satte ett pris på $1000 för en fråga relaterad till detta nummer, insamlad av Endre Szemerédi för vad som har blivit känt som Szemerédis teorem .
Aritmetiska progressioner från primtal
Szemerédis sats säger att en uppsättning naturliga tal med en övre asymptotisk täthet som inte är noll innehåller ändliga aritmetiska progressioner, av godtycklig längd k .
Erdős gjorde en mer allmän gissning som det skulle följa av
- Sekvensen av primtal innehåller aritmetiska progressioner av valfri längd.
Detta resultat bevisades av Ben Green och Terence Tao 2004 och är nu känt som Green–Tao-teoremet .
Se även Dirichlets sats om aritmetiska progressioner .
Från och med 2020 har den längsta kända aritmetiska progressionen av primtal längd 27:
- 224584605939537911 + 81292139·23#· n , för n = 0 till 26. ( 23# = 223092870 )
Från och med 2011 har den längsta kända aritmetiska progressionen av på varandra följande primtal längd 10. Den hittades 1998. Progressionen börjar med ett 93-siffrigt tal
- 100 99697 24697 14247 63778 66555 87969 84032 95093 24689
- 19004 18036 03417 75890 43417 033258 97258 972 98
och har den gemensamma skillnaden 210.
Källa om Erdős-Turáns gissning från 1936:
- P. Erdős och P. Turán, On some sekvenser av heltal, J. London Math. Soc. 11 (1936), 261–264.
Primer i aritmetiska progressioner
Primtalssatsen för aritmetiska progressioner handlar om den asymptotiska fördelningen av primtal i en aritmetisk progression.
Täckning av och uppdelning i aritmetiska progressioner
- Hitta minimal l n så att varje uppsättning av n rester modulo p kan täckas av en aritmetisk progression av längden l n .
- För en given uppsättning S av heltal, hitta det minimala antalet aritmetiska progressioner som täcker S
- För en given uppsättning S av heltal, hitta det minimala antalet icke-överlappande aritmetiska progressioner som täcker S
- Hitta antalet sätt att partitionera {1, ..., n } i aritmetiska progressioner.
- Hitta antalet sätt att dela upp {1, ..., n } i aritmetiska progressioner med längden minst 2 med samma period.
- Se även Täcksystem
Se även
Anteckningar
- ^ Samuel S. Wagstaff, Jr. (1979). "Några frågor om aritmetiska progressioner". American Mathematical Monthly . Mathematical Association of America. 86 (7): 579–582. doi : 10.2307/2320590 . JSTOR 2320590 .
- ^ Conlon, David ; Fox, Jacob ; Zhao, Yufei (2014). "Grön-Tao-satsen: en utläggning". EMS-undersökningar i matematiska vetenskaper . 1 (2): 249–282. arXiv : 1403.2957 . doi : 10.4171/EMSS/6 . MR 3285854 . S2CID 119301206 .
- ^ Jens Kruse Andersen, Primes in Arithmetic Progression Records . Hämtad 2020-08-10.
- ^ H. Dubner; T. Forbes; N. Lygeros; M. Mizony; H. Nelson; P. Zimmermann, "Tio på varandra följande primtal i aritmetisk progression", Math. Comp. 71 (2002), 1323–1328.
- ^ Nio och tio primer projekterar
- ^ Vsevolod F. Lev (2000). "Samtidiga approximationer och täckning av aritmetiska progressioner över F p " . Journal of Combinatorial Theory . Serie A. 92 (2): 103–118. doi : 10.1006/jcta.1999.3034 .
- ^ Sloane, N. J. A. (red.). "Sekvens A053732 (Antal sätt att partitionera {1,...,n} i aritmetiska progressioner med längd >= 1)" . The On-Line Encyclopedia of Integer Sequences . Stiftelsen OEIS.
- ^ Sloane, N. J. A. (red.). "Sekvens A072255 (Antal sätt att partitionera {1,2,...,n} i aritmetiska progressioner...)" . The On-Line Encyclopedia of Integer Sequences . Stiftelsen OEIS.