Tarihteki en ucuz matematik problemi
Giriş: Andrew ve Richard Guy'ın geçmişte eğlence için inceledikleri bazı üç boyutlu problemleri seçici olarak alıyorum. Sayısal sonuçlar gerçekten nefes kesici.
01.
Birkaç yıl önce, emekli bir matematikçi Allan MacLeod bir denkleme rastladı: Denklemin harikası nefes kesici. Dürüst olmak gerekirse, çok fazla rüzgar ve dalga gördüm, ancak bu kadar hassas bir Diophantine denklemini ilk kez görüyorum.
Not: Bir veya birkaç değişkenli integral katsayı denklemleri vardır ve bunların çözümleri yalnızca tamsayılar aralığındadır. Bu son kısıtlama, Diophantine denkleminin çözümünü, gerçek aralık denkleminin çözümünden temelde farklı kılar. Ayrıca belirsiz denklem olarak da adlandırılır.
Bu soruyla karşılaşmadan önce, birisi tarafından kötü niyetle internette yayınlanmış, popüler arkadaş çevresi kültürüne entegre edilmiş ve dürüst insanlarla ahlaksızca alay edilmişti. Karşılaştığım sorunun ne tür bir canavar olduğunu bile anlamadım. Şöyle görünüyor:
Arkadaş çevrenizde buna benzer pek çok resim görmüş olabilirsiniz.Genellikle başlık partisinin saçmalıkları: "MIT mezunlarının% 95'inin çözemediği bir sorun". Bu "soru" ya boş ya da hırsızlıktır. Konsepti değiştirmek ya önemsiz bir zeka oyunu.
Ancak bu soru başlık partisi değil. Bu resim kurnaz veya uğursuz bir tuzaktır. İnsanların yaklaşık% 99.999995'inin çözme şansı yok, hatta en iyi üniversitelerde sayı olmayan teori alanlarında çok sayıda matematikçi bile. Gerçekten çözülebilir, ama gerçekten çok zor.
Bu şekilde düşünebilirsiniz, tüm girişimler başarısız olursa, mucizeler yaratmak için bilgisayarı doğrudan da kullanabiliriz. Bu yıllarda, bu basit denklemi çözmek için bir bilgisayar programı yazmak o kadar kolay ki, bir cevabı olduğu sürece, bilgisayar sonunda bulacaktır. Ama üzgünüm, çok yanılmışım. Bilgisayar kaba kuvvet hesaplaması burada işe yaramaz.
Okuyucuların eliptik eğrilere başladığını düşünmezseniz, uygun bir cevap yazamayacağım. Burada yapabileceğim tek şey kısa bir genel bakış. Ana referans, 2014 yılında Annales Mathematicae et Informaticae'de (Annales Mathematicae et Informaticae) Bremmer ve MacLeod tarafından yakın zamanda yayınlanan "Sıradışı bir kübik temsil sorunu" başlıklı mükemmel bir makale.
Hadi başlayalım.
Kağıdın değişken isimlerine uyum sağlamak için elma, muz ve ananası modifiye ettim.
Herhangi bir denklem için yapmanız gereken ilk adım, problemin içeriğini denemek ve belirlemek. Bu ne tür bir soruna giriyor? Bizden bir tamsayı çözümü bulmamız isteniyor, yani bu bir sayı teorisi problemidir.
Problem söz konusu olduğunda, denklem rasyonel bir fonksiyonu içerir (bir polinomun bir polinomla bölünen fonksiyonel formu), ancak bir polinom fonksiyonuna dönüştürmek için genel bölme kaydırma terimi yöntemini kullanabileceğimiz açıktır, bu yüzden aslında bir Diophantine denklemini (Diophantine denklemi) çözeriz. ). Olumlu bir çözüme duyulan gereksinim biraz sıra dışı ve bu gereksinimin sorunu ne kadar zor hale getirebileceğini göreceğiz.
Şimdi, kaç değişkenimiz var? Bu soru aptalca görünüyor: a, b ve c olmak üzere üç değişkenimiz olduğu açık. Yavaşlayalım.
Bu, denklemin üç boyutlu gibi göründüğü anlamına gelir. Ama aslında sadece iki boyutu var. Geometride, bir yüzeye karşılık gelir (üç elemanlı bir denklem genellikle iki boyutlu bir yüzeyi tanımlar. Genel olarak konuşursak, k n-elemanlı denklemler d-boyutlu bir manifoldu tanımlar, d = n-k). Bu yüzey, kesilen tek düzlemle anlaşılabilen, orijinden geçen bir çizginin dönmesiyle oluşur. Bu yansıtmalı bir eğridir.
En temel dilde ifade edilen bu boyutsallık indirgemesi şu şekilde açıklanabilir: Çözüm ne olursa olsun, c = 0 durumu ve c 0 durumu olmak üzere iki kategoriye ayrılabiliriz. İlk tip sadece iki değişken içerir (bu yüzden doğal olarak iki boyutludur), ikinci tipte ise tüm çözümleri aynı anda c'ye bölebilir ve c = 1 ile bir çözüm elde edebiliriz (önceki paragrafta bunu açıkladık) Bir dizi çözüm de denklemlerin çözümleri olmalıdır).
Bu nedenle, a ve b'nin rasyonel sayı çözümlerini c = 1 olduğunda bulabiliriz, a, b ve c'nin pozitif çözümlerini elde etmek için sadece ortak bir payda ile çarpın. Genel olarak konuşursak, homojen bir denklemin tamsayı çözümü, bir boyut daha düşük homojen olmayan bir denklemin rasyonel sayı çözümüne karşılık gelir.
Sonraki soru şudur: Bu denklemin derecesi nedir? Sayı, her bir öğedeki en yüksek gücü ifade eder , Çarpılacak birden çok değişken içeren maddeler için güç, her bir değişkenin güçlerinin toplamıdır. Örneğin, bir öğe a2bc4 ise, bu öğenin numarası 7 = 2 + 1 + 4'tür.
Diophantine denklemleri, farklı zamanlarda zorluk bakımından tamamen farklıdır. Geniş anlamda:
- Bir zamanlar çok basit.
- İkincil de çok iyi anlaşılır ve genellikle nispeten basit yöntemlerle çözülebilir.
- Üç kez, dağlar ve denizlerle ve sayısız açık soruyla dolu ezoterik teorilerdir.
- Dört kez, gerçekten çok zor.
Denklemimiz kübiktir. neden? Paydaya gittikten sonra belli oluyor:
Benzer terimleri birleştirmeden bile, çarpma sayısının 3 olduğunu açıkça görebilirsiniz: üç değişkenin çarpımından fazlası yoktur ve sonunda a3, b2c, abc gibi terimler elde ederiz ve hiçbir güç 3'ü geçmez. Benzer terimleri birleştirdikten sonra denklem aşağıdaki gibi düzenlenir:
a3 + b3 + c33 (a2b + ab2 + a2c + ac2 + b2c + bc2) 5abc = 0
Böyle bir deformasyona itiraz edebilirsiniz: çünkü bu şekilde elde edilen çözüm, orijinal denklemi anlamsız hale getirerek 0'a eşit belirli bir paydayı yapabilir. Bu doğru, yeni denklemimizin bazı çözümleri orijinal denkleme uymuyor. Ama bu iyi bir şey. Bu polinom formu, işlenmesini kolaylaştırmak için orijinal denkleme bazı yamalar ekler; Bulduğumuz herhangi bir özel çözüm için, paydanın 0'a eşit olmadığını kontrol etmek için yalnızca orijinal denklemi değiştirmemiz gerekir.
Aslında, bir polinom denklemi için belirli bir çözüm bulmak kolaydır, örneğin, a = 1, b = 1, c = 0. Bu iyi bir şey: bir rasyonel sayı çözümümüz veya bir rasyonel noktamız var. Bu, katı denklemimizin (3 boyutlu) aslında eliptik bir eğri olduğu anlamına gelir.
Bu denklemin eliptik bir eğri olduğunu bulduğunuzda, çok sevinecek ve sonra üzüleceksiniz. Çünkü eliptik eğri probleminin bir canavar olduğunu görüyorsunuz (Pislik haykırıyor).
Not: Bu, bilinen konik bölümdeki bir elips değil, 1 cinsi ile düzgün bir projektif eğridir. Karakteristiği 2'ye eşit olmayan alan için afin denklemi şu şekilde yazılabilir: y2 = x3 + ax2 + bx + c. Karmaşık sayı alanındaki eliptik eğri, cins 1 ile bir Riemann yüzeyidir. Mordell, tüm alandaki eliptik eğrinin, ünlü BSD varsayımının ön koşulu olan, sonlu olarak oluşturulmuş bir değişmeli grup olduğunu kanıtladı. Abelian kümeleri, eliptik eğrilerin yüksek boyutlu uzantılarıdır. Baidu Encyclopedia tarafından.
Bu klasik denklem durumu bize eliptik eğri teorisinin gücüne bir göz atabilir ve bazı patlayıcı problemlere çözüm bulmak için kullanılabileceğini kanıtlayabilir.
03
Öncelikle, eliptik eğriyi Weilstrass formuna dönüştürmemiz gerekiyor.
Not: Weierstrass, en ünlü başarısının titiz analizin - dili olduğunu belirtti.
Bu, şuna benzeyen bir denklemdir:
y2 = x3 + ax + b
Ya da bazen dönüşüyor
y2 = x3 + ax + bx + c
Buna uzun Weilstrass formu denir. Kesinlikle gerekli değildir, ancak bazen biraz kolaylık sağlar.
Hepimizin bildiği gibi, herhangi bir eliptik eğri bu forma dönüştürülebilir (özellikle 2 veya 3 özellikli alan adlarına göre çok küçük özelliklere sahip alanlar üzerinde çalışıyorsanız, sonuç farklı olacaktır, burada tartışmayacağız). Eliptik eğrinin bu forma nasıl dönüştürüleceğini açıkça açıklamak isterseniz, bu uzun bir konuşmadır (öğrenme pisliği saçma düşünceler: İnanıyorum).
Sadece bu tür bir deformasyonun tamamen mekanik bir işlem olduğunu bilmelisiniz (anahtar, denklemde en az bir rasyonel nokta olması ve bir rasyonel nokta belirlememizdir). Bunu kolayca yapmanıza yardımcı olabilecek birkaç bilgisayar işlevi paketi vardır.
Bunun rastgele bir vudu hilesi gibi göründüğünü söylemeliyim, ama lütfen bana inanın öyle değil. Bu dönüşümleri tamamladığınızda, sıkıcı ama çok basit cebirsel hesaplamalar bunun doğru olduğunu kanıtlayabilir.
y2 = x3 + 109x2 + 224x
Bu denklem orijinal denkleme çok benzemese de, gerçekten değiştirilebilen güvenilir bir modeldir. İki gerçek parçadan oluşan klasik bir eliptik eğri olan görüntüde şu şekilde büyür:
Lütfen üçlerin (a: b: c) yansıtmalı eğri üzerinde anlaşıldığını unutmayın - bu denklemlerden hangi değeri alırsanız alın, onu istediğiniz bir sabitle çarpabilirsiniz.
Daha önce de belirtildiği gibi, ister a, b, c'den x'e, y'ye bir eşleme, ister ters bir eşleme olsun, bu iki denklemin sayı teorisi açısından eşdeğer olduğu kanıtlanabilir: Bir denklemin rasyonel sayı çözümü diğer denkleme yol açabilir Rasyonel sayı çözümü. Terim denir İki yönlü rasyonel eşdeğerlik (Birasyonel eşdeğerlik) ve bu kavram cebirsel geometride çok temeldir.
Yukarıda bahsedildiği gibi a + b, a + c veya b + c tam olarak 0'a eşit olduğunda, birbirine karşılık gelmeyen özel noktalar vardır. Bu, ikili rasyonel eşdeğerlik inşa etmek için gerekli fiyattır ve bunun için endişelenmenize gerek yoktur.
Elimizdeki bu örneğe bir göz atalım. Eliptik eğrisinin iyi bir rasyonel sayı noktası vardır: x = 100, y = 260. Bu noktayı bulmak kolay olmayabilir, ancak eğri üzerinde kontrol etmek çok basittir: Denklemin iki tarafının eşit olup olmadığını kontrol etmek için doğrudan orijinal denklemi değiştirin (Ben rastgele bir nokta değilim, ancak bu konuyu önemsemenize gerek yok). Basitçe a, b ve c'yi değiştirmenin sonuçlarını doğrulayabiliriz.
A = 2/7, b = 1 / 14, c = 11/14 elde ettik, çünkü ortak bir payda ile irade ile çarpabiliriz, sonra onu a = 4, b = 1, c = 11'e dönüştürebiliriz .
Aslında orijinal denklemin yerine geçecek olursak:
4 / (- 1 + 11) 1 / (4 + 11) + 11 / (41) = 4
Kolayca doğrulayabilirsiniz. Bu, orijinal denklemimizin basit bir tamsayı çözümüdür, ancak maalesef pozitif bir tamsayı çözümü değildir. Bu çözümü elle bulmak kolay değil ama biraz sabırlı bir bilgisayar olmadan da çok zor değil. Olumlu çözümün kökenini bulduğumuz yer olacak.
Şimdi, eliptik eğri üzerinde P (-100,260) gibi bir rasyonel sayı noktası bulduğunuzda, başka rasyonel sayı noktaları eklemek için akor kesme tekniğini kullanabilirsiniz (rasyonel sayıların eklenmesi kapalıdır, rasyonel sayı artı rasyonel sayı hala rasyonel sayıdır).
Her durumda, bir alandaki (gerçek sayı alanı R veya rasyonel sayı alanı Q) bir denklem verildiğinde, çözüm R2 veya Q2'de bulunan bir nokta olarak kabul edilebilir (R2 veya Q2'den projeksiyon) ve toplama yasası dizedir Teğet yapının dönüşümü: İki nokta P1 ve P2 eklemek için, önce iki noktadan geçen düz bir çizgi (akor) oluşturun.P1 ve P2 çakışırsa, bu düz çizgi eğrinin tanjantıdır.
Örnek: Eliptik eğri üzerindeki noktaların eklenmesi
Düz çizgi ile eğri arasındaki üçüncü kesişme noktası P'yi bulun, yukarıdaki işlemi O ve P için tekrarlayın, tekrar elde edilen kesişme noktası P1 + P2'dir. O noktası sonsuzda bir nokta olarak seçildiğinde (genellikle bu şekilde ele alınır), görüntü yukarıda gösterildiği gibidir.
Not: O noktasının ne olduğuna gelince, bu grup teorisini ve daha derin bir eliptik eğri bilgisini içerir.Eğer onu anlarsan, doğal olarak anlayacaksın, anlamazsan ben de anlamayacağım çünkü ben de anlamıyorum.
06
Başlangıçta P noktasına teğet yaparak ve eğriyle tekrar kesiştiği noktayı bularak P noktasının değerini artırabiliriz. Biraz korkutucu olduğu ortaya çıktı P + P = 2P = (8836/25, 950716 / 125).
Benzer şekilde, bu yeni nokta a, b ve c, (a, b, c) = (9499, 8784,5165) değerlerinin bir kümesine karşılık gelir.
Bu çözümün elle hesaplanması zordur, ancak bilgisayar kullanmak önemsizdir. Ancak henüz olumlu değil.
Elbette zorluklar bizi korkutamaz, 3P = 2P + P hesaplamaya devam ediyoruz, operasyon yöntemi eğri ile üçüncü kesişimi bulmak için P ve 2P'yi bağlamak ve ardından dördüncü kesişimi bulmak için O noktasına bağlanmaktır. Benzer şekilde, a, b, c'yi hesaplıyoruz, ancak aynı şekilde sonuç pozitif bir sayı değil. Benzetme yaparak, 4P, 5P ve benzerlerini hesaplayın. 9P'yi hesaplayana kadar.
9P = (- 66202368404229585264842409883878874707453676645038225 / 13514400292716288512070907945002943352692578000406921,58800835157308083307376751712593471813300856728502330737675171259347188895852648424098838700
Açıkçası bu bir insan hesabı değil, makineye verilmiş, bu 9 basit geometrik program yinelemesidir. A, b ve c'nin karşılık gelen değerleri de korkutucudur:
a = 154476802108746166441951315019919837485664325669565431700026634898253202035277999, b = 3687513179412999982719781156522547482549297996897197099628313747163722463405512777536
Bunlar 80 basamaklı! Kaba kuvvet hesaplamasıyla 80 basamaklı bir sayı bulamazsınız!
Not: Basit bir aritmetik problem, iki değişkenin bir tamsayı ve üçüncü değişkenin bir tamsayı olduğunu doğrulayan algoritmaya göre hesaplanır.Toplam kombinasyon sayısı 10160'tır. Sunway Taihu Light'ın en yüksek hesaplama gücü saniyede 1.25 milyar kez, bu da 1018 kereden azdır. / s, bu 10.134 yıl kadar yazılı bir daha şok edici bir yol 100 milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon milyon millionThe nextThe wayThe yolu bu olması, en az 10.142 saniye sürer
Ancak ne kadar inanılmaz görünürse görünsün, bu değerler aslında 4'e eşittir:
07
Teorinin kendisine geri dönelim ve onu tekrar tartışalım. Rasyonel bir sayı üzerinde tanımlanan bir eliptik eğrinin bir sıralaması vardır, bu, eğri üzerindeki tüm rasyonel noktaları bulmak için en azından kaç rasyonel noktayı akor-tanjant yöntemi ile bulmamız gerektiği anlamına gelir.
Eliptik eğrimizin sırası 1'e eşittir, bu da, üzerinde sonsuz sayıda rasyonel nokta olmasına rağmen, hepsinin tek bir rasyonel nokta tarafından üretildiği anlamına gelir.Söylemeye gerek yok, bu nokta bizim başlangıç noktamız P ( -100,260).
Sırayı hesaplamak ve böyle bir oluşturucu bulmak için kullanılan algoritma alışılmadık bir şeydir, ancak SageMath (şimdi CoCalc olarak adlandırılır) yalnızca birkaç satır kod ve tamamlanması 1 saniye sürer. Kodumu kontrol edebilirsiniz (burada), tüm çözümü en baştan yeniden üretir, elbette Sage'in yerleşik eliptik eğri işleme yöntemi vardır.
Bize göre, P noktası eğrinin eliptik kısmında yer alır ve diğer mP (m pozitif bir tam sayıdır) noktası aynıdır. Kademeli olarak elipsten geçecekler ve sonunda eğri boyunca eşit olarak dağılacaklar. Ve biz çok şanslıyız, çünkü sadece birkaç elips a, b ve c'nin pozitif çözümlerini üretebilir: bunlar aşağıdaki resmin kalın kısımlarıdır (Bremmer ve MacLeod'un yazısından alıntı).
P, 2P, vb. Siyah kalın kısımda değil, Ancak 9P orada olur, bu yüzden 80 bitlik pozitif tamsayı çözümü elde ederiz.
Bremmer ve MacLeod, denklemin sağ tarafındaki 4'ü başka bir şeyle değiştirirsek ne olacağını da inceledi. Çözümümüzün çok büyük olduğunu düşünüyorsanız, bunun nedeni 4'ü 178'e değiştirmenin sonucunu görmediniz. Sadece 80 bit değil, 398.605.460 bite ihtiyacınız var.
08
Yukarıda bahsedilen Diophantine denklemi, çok küçük katsayıları, ancak çok sayıda tamsayı çözümü olan korkunç bir durumdur. Bu sadece göz korkutucu bir sembol değil, aynı zamanda derin bir çalışmadır.
Hilbertin onuncu probleminin çürütücü ifadesi, katsayı kademeli olarak arttıkça, çözümün büyümesinin hesaplanamaz bir denklem olacağı anlamına gelir - çünkü hesaplanabilirse, bir çözüm bulabiliriz Diophantine denklemini açmak için basit bir algoritma - ama aslında basit ya da karmaşık bir şey yoktur (yani, Diophantine denklemini sonlu adımlarla çözmenin bir yolu yoktur).
Bu araştırma olumsuz bir ifadeye işaret ediyor: 4- > 80, 178- > Yüz milyonlarca, 896- > Trilyonlarca bit, o tuhaf, hesaplanamaz fonksiyona bir göz atalım. Denklemlerimizi biraz değiştirirsek, çözüm hızla büyüyerek "fakir" ve "küçücük" evrenimizdeki her şeyi kapsayacak.
Ne harika, ne alaycı küçük bir denklem!
Güncelleme: Çözümün hafife alınmasına ek olarak, birçok arkadaş şiddetli bir şekilde çözerken genellikle bir problemin doğruluğunu görmezden gelir. Programla birlikte gelen Double türünün hassasiyeti sınırlıdır.Çok uzun ondalık kısma sahip (büyük ondalık) bir sayı ile karşılaşıldığında, genellikle yanlış çözümler getirir veya doğru çözümleri kaçırır.
Örneğin, a = 688, b = 8600, c = 1599, bir hesap makinesi kullanabilirsiniz (elimde bilimsel bir hesap makinesi ile denedim) ve sonuç 4 oldu! Sorun çözüldü mü? Hayır, çünkü gerçek sonuç 4.0000000001800191239488843569645.
Çift değişkene bir değer atarsanız, bu çözüm seti çözülebilir (aslında çıktı da 4'tür, ancak dahili işlem (a / (b + c) + b / (a + c) + c / (a + b) == 4) yanlış olacaktır) -Ama sonraki üçlülerde ikili tipin hassasiyetini aşan bir sayı grubu olmayacağının garantisi yoktur (aslında, birçok grubun hassasiyeti aşması çok muhtemeldir, ancak benimki Bilgisayar bulunamadı) ve bir bilgisayarın gerçek çözüme ulaştığında doğruluk sorunları nedeniyle onu yok sayacağına dair bir garanti yoktur (çözümün 80 haneden fazla olmadığını varsayıyoruz).
Bu nedenle, kaba kuvvet kırma tamamen "şiddetli" olamaz.
Zuozhe: Alon Amit
Çevirmen: Mirror Civilization
Kaynak: Nanjing Üniversitesi Bilim Kurgu Hayranları Derneği (ID: njusfa)
