Pesawat Proyektif Pesanan 12

14

Tujuan : Menyelesaikan dugaan bahwa tidak ada bidang proyeksi pesanan 12.

Pada tahun 1989, menggunakan pencarian komputer pada sebuah Cray, Lam membuktikan bahwa tidak ada bidang proyektif pesanan 10 ada. Sekarang Angka Tuhan untuk Rubik's Cube telah ditentukan setelah hanya beberapa minggu pencarian brutal besar-besaran (ditambah matematika simetri yang cerdas), bagi saya tampaknya masalah terbuka yang sudah lama ada mungkin dalam jangkauan. (Plus mungkin kita bisa menggunakan teknik seperti itu untuk menyelesaikan sesuatu yang secara matematis mendasar.) Saya berharap pertanyaan ini dapat berfungsi sebagai pemeriksaan kewarasan.

Cube diselesaikan dengan mengurangi ukuran masalah total menjadi "hanya" 2.217.093.120 tes yang berbeda, yang dapat dijalankan secara paralel.

Pertanyaan:

  1. Ada beberapa kasus khusus tentang tidak adanya yang ditunjukkan. Adakah yang tahu, jika kita menghapusnya dan mencari sisanya, jika ukuran masalahnya ada di urutan pencarian Cube? (Mungkin terlalu berharap seseorang mengetahui hal ini ....)

  2. Adakah informasi parsial dalam nada ini?

Diedit untuk menambahkan: Saya mengajukan pertanyaan ini di MathOverflow di sini . Sejauh ini sepertinya tidak ada pengurangan ruang pencarian yang dicapai dari hasil parsial yang diketahui. Saya masih belum tahu ukuran ruang pencarian total.

open-problem Aaron Sterling
sumber
apakah Anda tahu ada referensi bagus untuk kasus khusus tidak ada yang Anda sebutkan? Atau mungkin, hanya referensi umum / set referensi untuk pesanan 12 kasus?
Daniel Apon
2
Ini terlihat lebih cocok untuk MathOverflow. Apakah ada hubungan yang kuat dengan ilmu komputer teoretis? (Di sisi lain: Seberapa sulit untuk memutuskan, diberi bilangan bulat n, apakah bidang projektif pesanan n ada? Waktu polinomial? NP-keras? Lebih buruk?)
Jeffε
@ Jeff, terima kasih, saya bertanya-tanya apakah saya harus bertanya di sana sebagai gantinya. Saya pikir itu bisa menjadi aplikasi TCS untuk kombinatorik, tapi saya tidak melihatnya sebagai hasil "penting", hanya buah gantung tinggi yang sekarang mungkin tergantung rendah karena kecepatan prosesor dan cloud. Saya tidak tahu jawaban untuk masalah keputusan Anda. Jadi ... Saya akan menunggu beberapa hari, lalu memposting ke MO, menghubungkan di sini.
Aaron Sterling
Saya suka reformulasi Jeff. Mungkin itu layak dikirim sebagai pertanyaan lain :)
Suresh Venkat
2
Saya melihat aplikasi potensial dari ilmu komputer untuk kombinatorik, hanya bukan ilmu komputer teoretis , yang (menurut bias saya sendiri) tentang perilaku membatasi komputasi sebagai ukuran input tumbuh hingga tak terbatas. Menemukan nomor Tuhan adalah pencapaian teknis yang mengesankan, tetapi tidak jelas bahwa itu memerlukan wawasan algoritmik, atau bahwa itu akan memiliki dampak algoritmik. (Saya ingin dikoreksi pada poin ini.)
Jeffε

Jawaban:

9

(Lebih banyak komentar daripada jawaban :)

Pesawat proyektif terbatas ada untuk nilai n yang merupakan kekuatan prima, dan ada banyak nilai n yang dikesampingkan oleh teorema RH Bruck dan H. Ryser, yang digeneralisasi untuk memblokir desain oleh Chowla:

http://en.wikipedia.org/wiki/Bruck%E2%80%93Chowla%E2%80%93Ryser_theorem

n = 10, seperti yang dinyatakan, diselesaikan (tidak ada pesawat) oleh pencarian komputer sehingga nilai pertama n tidak dikesampingkan oleh Bruck-Ryser adalah n = 12. Namun, pekerjaan komputer tampaknya tidak memberikan wawasan baru seperti apakah hanya ada pesawat kekuatan utama. Apa yang tampaknya diperlukan adalah metode matematika baru untuk wawasan ke dalam dugaan yang dibuat umum bahwa hanya pesawat kekuatan utama yang ada.

Joseph Malkevitch
sumber
3

Ada dugaan yang mengatakan bahwa, jika sigma (n)> 2n, maka tidak ada bidang projektif berhingga (FPP) berurutan n, atau satu set lengkap persegi Latin ortogonal (CMOLS) yang saling terkait yang sesuai dengannya. Di mana sigma (n) menunjukkan jumlah pembagi positif dari n termasuk n itu sendiri. Bahkan, ketika sigma (n)> 2n berarti n adalah angka yang melimpah. dan 12 adalah jumlah kelimpahan terkecil yang ada. Berikut ini adalah semua angka berlimpah untuk 1> n> 500: 12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 190, 190, 196, 198, 200, 204, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 294, 300, 304, 306, 308, 312, 318, 320, 324, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364,

dari On Projective Planes of Order 12 oleh Muatazz Abdolhadi Bashir dan Andrew Rajah

Bashir
sumber