Jakie są przypuszczenia TCS, które zostały udowodnione dla liczb pierwszych i małych wartości, ale okazały się fałszywe?

17

Czy są jakieś przypuszczenia w informatyce teoretycznej, które dotyczą jakiegoś parametru n i zostały udowodnione dla małych wartości n AND dla liczb pierwszych, ale później okazały się fałszywe?

W teorii liczb takie problemy istnieją, np. jak wskazuje Aaron Meyerowitz na temat współczynników wielomianów cyklotomicznych. Z TCS znam tylko takie przykłady, jak hipoteza wymijająca, które są nadal nierozstrzygnięte.

big-list primes

— domotorp
źródło

3

Uwaga: To bardziej przypomina komentarz rozszerzony niż odpowiedź.

Oto problem od kombinatoryki, której status jest podobny w smaku do hipotezy unikania:

Tło . Łaciński kwadrat rzędu jest macierzą , w której każdy element z {1,. . . , n} występuje dokładnie raz w każdym wierszu i kolumnie. Mówi się, że dwa łacińskie kwadraty rzędu są ortogonalne, jeśli uzyska się odrębnych uporządkowanych par, gdy się je nakłada. Mówi się, że zbiór kwadratów łacińskich jest wzajemnie ortogonalny, jeśli każda para z nich jest ortogonalna. Niech oznacza maksymalną liczbę wzajemnie prostopadłych kwadratów łacińskich rzędu . $n$ $n × n$ $n$ $n^2$ $N(n)$ $n$

$N(n)\leq n-1$ $n$ $n$ $N(n)=n-1$ $n$

— Jagadish
źródło

4

N (6) = 1

$N(6)=1$

N (n) \geq 2

$N(n) \geq 2$

n > 6

$n>6$

N (10) < 9

$N(10)<9$

1

Dzięki, Jagadish, problem polega na tym, że jest to coś, co można przypuszczać, że dotyczy to tylko liczb pierwszych (mocy). Szukam czegoś, co BYŁO przypuszczane, że jest prawdziwe dla wszystkich liczb, ale okazało się fałszywe.

— domotorp

@domotorp Tak, moja odpowiedź nie odpowiada dokładnie na pytanie. Ciekawe, czy ja sam mam takie przykłady, więc daj +1 za swoje pytanie.

— Jagadish,

3

$p-1$ $p$ $n$ $n=32$

— Lew Reyzin
źródło