Merlin, który ma nieograniczone zasoby obliczeniowe, chce przekonać Arturowi, że

(Notacja, dla zgodności z wcześniejszymi wersjami tego pytania: Niech suma będzie równa $m\alpha$ ; wówczas pytanie brzmi, czy $\alpha$ jest liczbą całkowitą.)

Czy Merlin może przekonać Artura sznurkiem o długości $O(N)$ ? Jeśli nie, to czy uda mu się przekonać Artura interaktywnym dowodem (całkowita komunikacja oczywiście musi być $O(N)$ )? Jeśli tak, to czy Merlin mógłby zastosować ciąg o długości $o(N)$ ? Czy Arthur mógłby wykorzystać czas $o(N)$ ?

Artur nie ma dostępu do niedeterminizmu ani innych specjalnych narzędzi (metod kwantowych, wyroczni innych niż Merlin itp.), Ale w razie potrzeby ma przestrzeń $O(N)$ . Oczywiście, Artur nie musi obliczać sumy bezpośrednio, wystarczy jedynie przekonać, że dane potrójne (N, m, k) sprawiają, że równanie jest prawdziwe lub fałszywe.

Należy zauważyć, że z $k=0$ nie jest możliwy do obliczania sumy w czasie $O(N^{1/2+\varepsilon})$ stosując Lagarias-Odlyzko metody. Dla $k>0$ suma jest superliniowa i dlatego nie można jej zapisać bezpośrednio (bez np. Redukcji modułowej), ale nie jest jasne, czy istnieje szybki algorytm.

Byłbym także zainteresowany dowolnym algorytmem do obliczania sumy (modułowej lub innej) innej niż bezpośrednie zasilanie i dodawanie.

* liczby do obliczenia, czas lg k log N ( log log N ) 1 + o ( 1 ) = log N ( log log N ) 2 + o ( 1 ) dla każdego obliczenia.$N/\log N$$\lg k\log N(\log\log N)^{1+o(1)}=\log N(\log\log N)^{2+o(1)}$

Piszę to osobno od mojego wcześniejszego specjalnego przypadku, ponieważ uważam, że jest to inne podejście do problemu i ma niewielki związek z moją drugą odpowiedzią. To może nie być dokładnie to, czego szukasz, ale jest proste i zbliża się.

Istnieje dowód, który Arthur zawsze zaakceptuje, jeśli dowód jest poprawny, ale zostanie odrzucony z prawdopodobieństwem . Oto jak to działa: Merlin wysyła Arthur para(pI,ci=p k i  mod m)dla każdego głównegop≤N. Artur weryfikuje sumę (biorąc czasO(N/log(N))×O(log(N))=O(N$\frac{1}{(\log \log N)^{2+o(1)}}$$(p_i,c_i = p_i^k\mbox{ mod }m)$$p\leq N$$O(N/\log(N)) \times O(\log(N)) = O(N)$). Arthur sprawdza, czy odpowiednia liczba bodźców zostało zapewnione (przez obliczenia ), która jest sublinear w N . Wreszcie dla losowych par S N potwierdza, że p jest liczbą pierwszą i że p k i ≡ c i  mod  m . Wymaga to czasu S N O ( ( log log N ) 2 + o ( 1 ) ) . Biorąc S = ( log log N $\pi(N)$$N$$S N$$p$$p_i^k \equiv c_i \mbox{ mod }m$$SN~O((\log \log N)^{2+o(1)})$ , otrzymujemy liniowe skalowanie czasu. W ten sposób ułamekSwszystkich par jest weryfikowany. Jeśli któryś z nich zawiedzie, Arthur oczywiście odrzuci. Aby Arthur zaakceptował niepoprawny dowód, musi istnieć co najmniej jedna para, która nie przejdzie jednego z tych dwóch testów (lub liczba par musi być mniejsza niżπ(N),co zostało wcześniej sprawdzone). Stąd jako frakcjaSwszystkich par są kontrolowane, test nie powiedzie się do niewłaściwej dowodu z prawdopodobieństwa co najmniejS.$S = (\log \log N)^{-(2+o(1))}$$S$$\pi(N)$$S$$S$

Zauważ, że dla dużych jest to znacznie lepsze niż losowe zgadywanie, które kończy się prawdopodobieństwem $N$ .$\frac{1}{m} = \frac{1}{O(N)}$

To pełna odpowiedź na problem, który w ogóle nie korzysta z Merlina.

Deléglise-Dusart-Roblot [1] uzyskując algorytm, który określa liczbę bodźce się dla , które są przystające do l modulo K , w czasie O ( x 2 / 3 / log 2 x ) . Modyfikacja algorytmu Lagarias-Odlyzko [2] sposób ta sama być obliczona w czasie O ( x 1 / 2 + O ( 1 ) ) $x$$l$$k,$$O(x^{2/3}/\log^2x).$$O(x^{1/2+o(1)}).$

Korzystając z dowolnego algorytmu, znajdź liczbę liczb pierwszych we wszystkich klasach liczb pierwszych mod mod, aż ich iloczyn będzie większy niż Dla każdego głównego Q , ma całkowitą liczbę liczb pierwszych w każdej reszcie razy klasy tej klasy pozostałości w k -tej potęgi; daje to wartość ∑ p ≤ N p liczba  pierwsza p $m.$$q,$$k$

Skorzystaj z chińskiego twierdzenia o pozostałej wartości, aby określić wartość sumy mod $2\cdot3\cdots\log m.$

Przez liczby pierwsze twierdzenie największym prime potrzebne jest więc daje to sumę w czasie O ( N 1 / 2 + o, ( 1 ) ) $(1+o(1))\log m,$$O(N^{1/2+o(1)}).$

Bibliografia

[1] Marc Deléglise, Pierre Dusart i Xavier-François Roblot, Liczenie liczb pierwszych w klasach pozostałości , Mathematics of Computation 73 : 247 (2004), s. 1565-1575. doi 10.1.1.100.779

$\pi(x)$

[3] Charles, odpowiedź na MathOverflow . (Tak, to ta sama osoba. Zobacz inne odpowiedzi tam dla różnych podejść.)

$k$$k=x \phi(m)$$x$

$\phi(m)$$m$$N$$p^{x \phi(m)} \equiv 0 \mbox{ mod } m$$p|m$$p^{x \phi(m)} \equiv 1 \mbox{ mod } m$$k=x \phi(m)$$\sum_{p \leq N, p~prime} p^{k} \equiv \pi(N) - y \mbox{ mod } m$$y$$m$$\pi(N)$$N$

$1<N<m$$m\alpha$$1<\pi(N)<m$