[MIX][Analiza][Algebra] Pozdrowienia z UW

[Piotr Rutkowski]

Witam,

Tak jak w temacie, przesyłam Wam pozdrowienia. Jako że prawdopodobnie nie jesteście nimi zainteresowani, to przesyłam również niezwykle ciekawe zadanko (nie jest ono zbyt proste), które pojawiło się w tzw. międzyczasie. Jeżeli natknę się na jakieś inne równie ciekawe problemy, to będę je tu wrzucał Wszystkie pomysły są tu jak najbardziej mile widziane. Oczywiście innych "współplemieńców" również do tego zachęcam, w końcu inna grupa ćwiczeniowa ma z reguły dostęp do innych materiałów.

1. Zbieżność szeregu
Zbadać zbieżność szeregu \(\displaystyle{ \sum_{n=1}^{\infty}(-1)^{[n\sqrt{2}]}\frac{1}{n}}\)

[Maciej87]

Z jednej strony, problem jest związany z jednostajnym rozkładem \(\displaystyle{ \{n\cdot \frac{\sqrt{2}}{2} \}}\) w przedziale \(\displaystyle{ [0,1]}\). Ale porządnie:
żeby ogarnąć zmiany znaków, pierwsze co się narzuca to transformacja Abela. I tak, sprowadzamy zadanie do oszacowania sumy

\(\displaystyle{ S_n = \sum\limits_{k=1}^{n} (-1)^{\lfloor n \sqrt{2} \rfloor}}\)

Zdefiniujmy \(\displaystyle{ 1-}\) okresową funkcję
\(\displaystyle{ f(x) = \left\{
\begin{array}{cc}
1 & 0\leqslant x < \frac{1}{2} \\
-1 & \frac{1}{2} \leqslant x < 1
\end{array}
\right.}\)
Wtedy
\(\displaystyle{ S_n =\sum\limits_{k=1}^{n} f\left(k\alpha\right)}\)
z twierdzeń ergodycznych stosowanych do jednostajnie rozłożonego \(\displaystyle{ \{k\frac{\sqrt{2}}{2}\}}\), konkretnie twierdzenia Weyla, ta suma spełnia
\(\displaystyle{ \frac{S_n}{n} \to \int\limits_{[0,1]}f(t) \mbox{d}t}\).
Wiedząc że ciąg gęsto wypełnia przedział- co nieraz jest pokazywane jako sympatyczne zadanie, możemy już mieć intuicję, że takie średnie przypominają całkę.
Nie jest to zresztą trudne twierdzenie- na etapie wiedzy o aproksymacji wielomianami trygonometrycznymi.

Wynik który mamy to \(\displaystyle{ S_n = o(n)}\), po transformacji Abela i zniknięciu jednego składnika w granicy, sprowadza problem do zbieżności szeregu
\(\displaystyle{ \sum\limits_{n} \frac{1}{n^2}S_n}\)
i nie urządza nas.

Mocniejsze narzędzia polegają na subtelniejszym potraktowaniu wspomnianych przeze mnie sum trygonometrycznych, trochę takiej analizie Fourierowskiej. W szczególności, ze sławnego twierdzenia Erdosa-Turana otrzymać możemy, tak na oko, że
\(\displaystyle{ S_n = \mathcal{O}\left(n^{\delta}\right)}\)
przy dowolnym \(\displaystyle{ \delta > 0}\).
Wystarcza to do zbieżności naszego szeregu, są to jednak działa, które tutaj ciężko rozkręcić na kawałki, i obejrzeć mechanizm.

Powyższe oszacowanie prowadzi do hipotezy (nie konsultowałem tego wariantu z powyższymi technikami) że \(\displaystyle{ S_n = \mathcal{O}(\log n)}\).

Tak rzeczywiście jest, dowód jest na mathlinks, oparty o właściwości aproksymacji diofantycznej i poysłowość- może nie będę go na razie przepisywać, problem niech będzie dla zabawy, ja natomiast pomyślę nad napisaniem na forum krótkiego artykułu z dowodem nierówności Erodsa i zastosowaniami.
Zapewne pójdzie również z Erdosa.

Tak na intuicję, fakt że liczby generującej ciąg nie możemy zbyt dobrze aproksymować, może być dla nas korzystny, jako że funkcja nie przebywa w ten sposób w otoczeniu pewnych punktów. Można to wykorzystać do robienia jakichś poprawek, może to nie będzie mądre, ale niech tam:
dla \(\displaystyle{ \alpha = \frac{\sqrt{2}}{2}}\) twierdzenie Luivilla daje
\(\displaystyle{ \left|2n\alpha -m-1\right| > \frac{C_0}{2n}}\)
czyli
\(\displaystyle{ \left|n\alpha - \frac{1}{2}- m\right| > \frac{C}{n}}\)
a to oznacza, że w naszej sumie \(\displaystyle{ \sum\limits_{k=1}^{n} f\left(k\alpha\right)}\) ciąg pod funkcją nie przebywa w otoczeniu o promieniu \(\displaystyle{ \varepsilon \sim \frac{1}{n}}\) punktu \(\displaystyle{ \frac{1}{2}}\). Możemy więc, dla ustalonego \(\displaystyle{ n}\),zastąpić funkcję przez ciągłą- wygładzić skok, który akurat tam ma. To była jedna z moich luźnych idei, niestety, nie ma dobrych własności, na krótkim przedziale następuje gwałtowny wzrost funkcji.

-- 29 lis 2009, o 13:04 --

PS: suma szeregu jest równa \(\displaystyle{ \sigma = -0.5154\ldots}\)

[krl]

Maciej87 podał powyżej przybliżoną sumę szeregu. Nie wiem, czy jest to przybliżenie uzyskane przez wyliczenie przy pomocy komputera sumy częściowej dla dużego \(\displaystyle{ n}\) (a więc "przybliżenie inżynierskie"), czy też wynik matematyczny, za którym jest w szczególności dowód, że ten szereg jest zbieżny. W tym drugim przypadku chętnie zobaczyłbym jakieś szczegóły, w tym pierwszym zaś mam następującą uwagę (która odnosi się też trochę do drugiego przypadku):
Podejrzewam, że problem zbieżności tego szeregu jest trudny, może otwarty. Przypuszczam, że jeśli liczbę \(\displaystyle{ \frac{\sqrt{2}}{2}}\) zastąpimy w definicji szeregu dowolna liczbą \(\displaystyle{ a}\) z przedziału \(\displaystyle{ (0,1)}\), to
1. zbiór tych \(\displaystyle{ a}\), dla których szereg jest zbieżny, jest gęsty w \(\displaystyle{ (0,1)}\),
2. zbiór tych \(\displaystyle{ a}\), dla których szereg jest rozbieżny do \(\displaystyle{ +\infty}\), jest gęsty w \(\displaystyle{ (0,1)}\),
3. zbiór tych \(\displaystyle{ a}\), dla których szereg jest rozbieżny do \(\displaystyle{ -\infty}\), jest gęsty w \(\displaystyle{ (0,1)}\),
4. zbiór tych \(\displaystyle{ a}\), dla których szereg nie jest zbieżny w żadnym sensie, jest gęsty w \(\displaystyle{ (0,1)}\).

Ponadto, przedział \(\displaystyle{ (0,1)}\) w tych zdaniach można zastąpić przez \(\displaystyle{ (0,1)\cap\mathbb{IQ}}\). Jeśli powyższe przypuszczenia są słuszne, to kwestia czy szereg jest zbieżny dla \(\displaystyle{ a=\frac{\sqrt{2}}{2}}\) , zależy od rozwinięcia dziesiętnego liczby \(\displaystyle{ \frac{\sqrt{2}}{2}}\) (tzn. od sposobu, w jaki jest ona przybliżana przez liczby wymierne), a to (jak przypuszczam) może być trudny otwarty problem. Tak samo trudny, jak pytanie, jaka jest najmniejsza cyfra, która powtarza się nieskończenie wiele razy w rozwinięciu dziesiętnym liczby \(\displaystyle{ \pi}\).

[Piotr Rutkowski]

Wg niektórych osób istnieje całkowicie elementarny dowód... Jeśli zobaczę to się podzielę
Moje próby szły dwutorowo, raz tak jak u Macieja (wielkie dzieki za post), a raz przez dziwaczne konstrukcje geometryczne (budowałem kwadrat o boku 2n i obracałem o \(\displaystyle{ 45^{o}}\), następnie bawiłem sie wzorem Picka dla 3 kwadratów), ale nie dało to żadnego odpowiedniego rezultatu...

Anyway kontynuuję temacik. Wczoraj na korytarzu wpadłem na takie ciekawe zadanko:

2. Zbadać zbieżność szeregu:
\(\displaystyle{ \sum_{n=1}^{\infty}\frac{1}{p_{n}(p_{n+1}-p_{n})}}\)
Pozdrawiam

[Dumel]

wiesz misiu, myśle że nikt by się nie obraził gdybyś z tematyką zadań wyszedł też poza analizę

[Piotr Rutkowski]

wiesz misiu, myśle że nikt by się nie obraził gdybyś z tematyką zadań wyszedł też poza analizę

Wiesz, akurat moją ideą nie jest wstawianie zadań z konkretnych działów, tylko takich, które najzwyczajniej były (zdawały się być) bardzo trudne. Jak na razie biorę po prostu te, których sam nie mogę zrobić i, o których wiadomo, że na obecnym I roku również czekają na rozwiązanie...
Akurat tak się składa, że moja grupa z GAL nie jest zbyt płodna w wymiarze trudnych zadań. Ale spełniając Twoją prośbę znalazłem coś ciekawego (prawdopodobnie bardziej "robialne"):

3.
Ustalmy \(\displaystyle{ m,n \in \mathbb{N}}\). Dla macierzy \(\displaystyle{ A}\) o elementach rzeczywistych rozmiaru \(\displaystyle{ m\ x \n}\) zdefiniujmy \(\displaystyle{ e(A)}\) jako minimalną liczbę operacji elementarnych, które są potrzebne do sprowadzenia \(\displaystyle{ A}\) do postaci całkowicie zredukowanej. Znaleźć \(\displaystyle{ max \ e(A)}\)

Prawdopodobnie temat zaktywizuje się w II semestrze, bo wtedy będę miał dostępne materiały z grup *.
Pozdrawiam

[Maciej87]

Nie ma wyjścia, trza było poczytać o trygonometrycznej aproksymacji funkcji schodkowych, bo to się w naturalny sposób nam pojawiło. I to będzie raczej z naprawdę grubej rury.
Zatem, zakładam że zgadzamy się, że po zastosowaniu transformacji Abela i twierdzenia ergodycznego do wyłamującego się w nim jednego składnika, pozostaje nam oszacować sumę
\(\displaystyle{ \sum\limits_{k=1}^{n}f(k\alpha)}\)
Jak zasygnalizowałem, wzór całkowy dla granicy zgadza się dla funkcji \(\displaystyle{ e(kt)}\) gdzie \(\displaystyle{ e(s)=\exp(2\pi i s)}\). Będziemy więc używać szeregów Fouriera. I tak, ważny fakt:
Lemat o wielomianach Selberga
funkcję charakterystyczną przedziału można przybliżać wielomianem trygonometrycznym stopnia najwyżej \(\displaystyle{ m}\) od dołu i od góry z dokładnością \(\displaystyle{ \mathcal{O}\left(\frac{1}{m}\right)}\) w normie supremum.
Dowodu nie zrozumiałem
\(\displaystyle{ \blacksquare}\)
Biorąc stosowną kombinację takich wieomianów (nasza funkcja to kombinacja dwóch schodków) potrafimy przybliżyć z identyczną dokładnością, z dołu i z góry funkcję \(\displaystyle{ f}\).
W szczególności
\(\displaystyle{ f^{-} < f < f^{+}}\)
gdzie \(\displaystyle{ f^{-},f^{+}}\) są wielomianami trygonometrycznymi stopnia \(\displaystyle{ m}\), oraz
\(\displaystyle{ \int \left|f^{-}- f^{+} \right| = \left\|f^{-}- f^{+} \right\|_{L^{1}} = \mathcal{O}\left(\frac{1}{m}\right)}\)
No dobrze. Niech \(\displaystyle{ g(t) = \sum\limits_{k=-m}^{m}c_k e(kt)}\) będzie stopnia \(\displaystyle{ m}\).
Zastąpmy w badanej sumie \(\displaystyle{ f}\) przez \(\displaystyle{ g}\). Otrzymujemy
\(\displaystyle{ \sum\limits_{j=1}^{n}\sum\limits_{k=-m}^{m}c_k e(k j\alpha)}\)
zamieniając kolejność sumowania mamy
\(\displaystyle{ \sum\limits_{k=-m}^{m}c_k U_k}\)
gdzie ze wzoru na postęp geometryczny dla \(\displaystyle{ k\not = 0}\)
\(\displaystyle{ U_k = \sum\limits_{j=1}^{n}e(k j\alpha) = \frac{e(k(n+1)\alpha)-e(k\alpha)}{e(k\alpha)-1}}\)
jednakowoż oszacujemy to sobie dalej bo \(\displaystyle{ \left|U_k\right| \leqslant \frac{2}{|e(k\alpha)-1|}}\) a ponieważ \(\displaystyle{ |e(k\alpha)-1| = \sin|k\alpha \pi| > 2\left\| k\alpha \right\|}\), gdzie
\(\displaystyle{ \left\| s \right\| = \min_{n\in\mathbb{Z}} |s-n |}\)
jest odległością do najbliższej liczby całkowitej (pojechaliśmy po prostu sieczną pod łukiem sinusoidy)
Wprowadzenie tej metryki- odległości do najbliższej liczby całkowitej nie jest głupim pomysłem, gdyż z twierdzenia o aproksymacji
\(\displaystyle{ \left\| k\alpha \right\| > \frac{C}{k}}\)
stąd dostajemy w końcu
\(\displaystyle{ U_k = \mathcal{O}(k)}\) i \(\displaystyle{ U_0 = n}\)
Dla wielomianu trygonometrycznego, nasza suma jest więc równa
\(\displaystyle{ \sum\limits_{j=1}^{n}g(j\alpha) = \sum\limits_{k=-m}^{m} c_k U_k = \mathcal{O}\left(c_0n \right)+\mathcal{O}\left( \sum\limits_{0<|k|\leqslant m}^{m} k|c_k| \right)}\)
Zamiast \(\displaystyle{ g}\) użyjemy teraz wielomianów \(\displaystyle{ f^{-},f^{+}}\). Powiedzmy, że \(\displaystyle{ g=f^{+}}\). Oszacujmy współczyniki Fouriera. Niech \(\displaystyle{ d_k}\) będą współczynnikami \(\displaystyle{ f}\) to jest, poza punktami skoków
\(\displaystyle{ f(t) =\sum\limits_{k=-\infty}^{+\infty} d_k e(kt)}\)
Wtedy mamy, z nierówności modułu dla całki i z założeń o wielomianach aproksymujących
\(\displaystyle{ \left|c_k -d_k \right| \leqslant\left|f(t)e(-kt) -g(t)e(-kt) \right| \leqslant \left\|f-g \right\|_{L^{1}} = \mathcal{O}\left(\frac{1}{m} \right)}\)
Z kolei wiadomo (liczy się bardzo prosto, bo \(\displaystyle{ f}\) to funkcja dwoma kawałkami stała), że dla \(\displaystyle{ k\geqslant 1}\) jest \(\displaystyle{ d_k = \mathcal{O}\left( \frac{1}{k}\right)}\). Mamy więc razem
\(\displaystyle{ c_k = \mathcal{O}\left(\frac{1}{m} \right) + \mathcal{O}\left( \frac{1}{k}\right) = \mathcal{O}\left( \frac{1}{k}\right)}\)
Ponadto, mamy \(\displaystyle{ d_0=0}\) oraz \(\displaystyle{ c_0 = \mathcal{O}\left(\frac{1}{m} \right)}\).
Zatem możemy już oszacować całą sumę
\(\displaystyle{ \sum\limits_{j=1}^{n}f(j\alpha) < \sum\limits_{j=1}^{n}g(j\alpha) = \mathcal{O}\left(c_0n\right)+ \mathcal{O}\left( \sum\limits_{0 < |k| \leqslant m} k|c_k| \right) = \mathcal{O}\left(\frac{n}{m} \right) + \mathcal{O}(m) = \mathcal{O}\left( \sqrt{n}\right)}\)
I podobnie z dołu, czyli zrobione.
aczkolwiek jest tu jeszcze sporo do powalczenia. Najwięcej nabruździł współczynnik \(\displaystyle{ c_0}\).
Pomysł żeby wygładzić funkcję korzystając z aproksymacji, więc tego że omija pewne przedziały, podobno powinien to poprawić- ktoś tam gdzieś pisał, że metodami fourierowskimi ma wyjść \(\displaystyle{ n^{\epsilon}}\). W tym rozwiązaniu nie korzystamy z mocnej własności wielomianów Selberga- aproksymacji jednostajnej. Tak naprawdę wykorzystaliśmy aproksymację z góry i z dołu w \(\displaystyle{ L^{1}}\).
Inaczej mówiąc, wygładzając funkcję tak jak wspomniałem, powinniśmy (rzekomo) w miarę na palcach uzyskać podobne własności- tzn dobre przybliżenie szeregiem Fouriera, ale z uwzględnieniem że szybkiej zbieżności potrzebujemy tylko w punktach naszego ciągu \(\displaystyle{ \left\{k\alpha \right\}}\).
W szczególności, jeśli wyliczymy sobie taki wielomian o współczynniku \(\displaystyle{ c_0 = 0}\), to odpadnie nam składnik najwyższego rzędu i będzie git.

Problem faktycznie zależy od aproksymacji diofantycznej, a więc raczej ułamków łańcuchowych a nie dziesiętnych. I są stosowne twierdzenia, które szacują takie "ergodyczne" sumy.
Dostałem publikację na temat tego szeregu, która wylicza jego wartość z podaną dokładnością i korzysta właśnie z czegoś takiego odjechanego. Rozwiązanie zajmuje chyba ze stronę. Jak ktoś chce to kontakt na pw.

[abc666]

Aha o_O
Piotrze Rutkowski, kiedy poznasz ten elementarny dowód? Bardzo mnie (i na pewno nie tylko mnie) on ciekawi.

[Maciej87]

Rozwiązanie elementarne i oszacowanie najlepszego rzędu:

Niech \(\displaystyle{ \left\|x\right\| = \min_{n\in\mathbb{Z}}|x-n|}\) będzie najmniejszą odległością \(\displaystyle{ x}\) od liczb całkowitych. Jest to metryka, tzn ma dobre własności odległości, np. nierówność trójkąta.
Jeżeli mamy aproksymację diofantyczną taką że
\(\displaystyle{ 0 < a\sqrt{2}-b < \frac{1}{a}}\)
oraz
\(\displaystyle{ \left\|k\sqrt{2}\right\| \geqslant \frac{1}{a} \quad \star}\)
to wówczas

\(\displaystyle{ \lfloor k\sqrt{2} \rfloor = \lfloor (k-a)\sqrt{2} \rfloor + \lfloor a\sqrt{2} \rfloor}\)

Gdyby więc \(\displaystyle{ \lfloor a\sqrt{2}\rfloor}\) było nieparzyste, \(\displaystyle{ 2a<n}\) i dla wszystkich \(\displaystyle{ k = n-a+1,\ldots,n}\) zachodziło (*), to dostalibyśmy redukcję znaków na przedziale sumowania \(\displaystyle{ I = \left\{j: \,n-2a < j \leqslant n\right\}}\) i \(\displaystyle{ S_n = S_{n-2a}}\)

Pytanie 1: jak dobrać dobre \(\displaystyle{ a}\). Bierzemy dodatnie rozwiązanie równania Pella
\(\displaystyle{ 2a^2-b^2=1}\)
a to dlatego, że daje małą normę:
\(\displaystyle{ 0<a\sqrt{2}-b = \frac{1}{a\sqrt{2}+b} < \frac{1}{2a}}\) czyli \(\displaystyle{ 0<a\sqrt{2}-b < \frac{1}{2a}}\)
oraz \(\displaystyle{ b = \lfloor a\sqrt{2} \rfloor}\) jest nieparzyste, a ponadto aproksymacja liczbą całkowitą jest z lewej strony (tak jak chcemy)

Pytanie 2: ile liczb \(\displaystyle{ k}\) nie spełnia gwiazdki (mamy tam teraz trochę lepszą stałą w aproksymacji). Okazuje się, że takie liczby leżą względnie rzadko:
Weźmy dwie takie \(\displaystyle{ p,q}\), że \(\displaystyle{ \left\|p \right\|,\left\|q \right\| < \frac{1}{2a}}\) .
Z nierówności trójkąta mamy
\(\displaystyle{ \left\| (p-q) \sqrt{2} \right\| < \frac{1}{a}}\)
a z twierdzenia Liouvillea
\(\displaystyle{ \frac{1}{L}\cdot \frac{1}{|p-q|} < \left\| (p-q) \sqrt{2} \right\|}\)
stąd \(\displaystyle{ |p-q| > \frac{a}{L}}\)
Ale nasz przedział \(\displaystyle{ n-a < k \leqslant n}\)ma długość \(\displaystyle{ a}\) stąd też możemy znaleźć najwyżej \(\displaystyle{ L+1}\) takich liczb.

Ok, a więc mamy \(\displaystyle{ \left|S_n - S_{n-2a}\right\| < 2L+2}\)
Zauważmy, że jeśli \(\displaystyle{ a_m}\) jest ciągiem rozwiązań równania Pella, to
\(\displaystyle{ a_{m+1} < 3a_m}\)
Wynika to z faktu, że rozwiązania \(\displaystyle{ a-b\sqrt{2}}\) stanowią grupę elementów odwracalnych \(\displaystyle{ \mathbb{Z}[\sqrt{2}]}\) o której nietrudno pokazać (przez regresję) że jest generowana przez \(\displaystyle{ 1-\sqrt{2}}\). Wtedy \(\displaystyle{ a_m-b_m\sqrt{2} = (1-\sqrt{2})^{m}}\) i mamy rekurencję \(\displaystyle{ a_{m+1}-b_{m+1}\sqrt{2} = (a_m-b_m\sqrt{2})(1-\sqrt{2})}\)
Skoro tak, to wybierając do naszych potrzeb największe \(\displaystyle{ a}\) takie by \(\displaystyle{ n-2a > 0}\) mamy również \(\displaystyle{ n-6a < 0}\) skąd \(\displaystyle{ n-2a < \frac{2}{3}n}\)
Skracamy sumę o \(\displaystyle{ \frac{1}{3}}\) długości popełniając stały błąd- wynika już z tego natychmiast, że
\(\displaystyle{ S_n = \mathcal{O}(\log n)}\)

Stałą \(\displaystyle{ L}\) w przypadku \(\displaystyle{ \sqrt{2}}\) można też pewnie wyliczyć jakoś na palcach (niekoniecznie z konstruktywnej metody w twierdzeniu)

PS: przeedytowałem pod uwagę Piotra

[Piotr Rutkowski]

\(\displaystyle{ \lfloor k\sqrt{2} \rfloor = \lfloor (k-a)\sqrt{2} \rfloor + \lfloor a\sqrt{2} \rfloor}\)

Dlaczego? Dla \(\displaystyle{ a=12 \ k=15}\) zachodzą ww. warunki, ale \(\displaystyle{ [15\sqrt{2}]\neq [12\sqrt{2}]+[3\sqrt{2}]}\) ...

[Maciej87]

A tak, naściemniałem.
Jak to sobie rozpisałem, to żeby zapanować nad częściami ułamkowymi trzeba założyć jeszcze jeden warunek. Nie że obie liczby są bliskie \(\displaystyle{ \mathbb{Z}}\), ale że jedna ma dodatkowo małą część ułamkową (psuje się wtedy kiedy ma dużą- wtedy też norma jest mała)
Jeżeli \(\displaystyle{ \lfloor a\sqrt{2} \rfloor < a\sqrt{2} < \lfloor a\sqrt{2} \rfloor + \varepsilon}\)
oraz \(\displaystyle{ \left\|k\sqrt{2}\right\| > \varepsilon}\)
to ponieważ
\(\displaystyle{ \lfloor k\sqrt{2} \rfloor + \varepsilon < k\sqrt{2} < \lfloor k\sqrt{2} \rfloor + 1-\varepsilon}\)
mamy to co chcemy.

W dowodzie zamiast odejmować liczbę \(\displaystyle{ a}\) możemy też dodawać

[Piotr Rutkowski]

Skracamy sumę o \(\displaystyle{ \frac{1}{3}}\) długości popełniając stały błąd- wynika już z tego natychmiast, że
\(\displaystyle{ S_n = \mathcal{O}(\log n)}\)

Ciekawy fakcik, będę go musiał zapamiętać. Takie podejście wydaje się mieć więcej zastosowań. Cóż, nie powiem, bardzo mi się podoba to rozwiązanie Domyślam się jednak, że sam pomysł na rozwiązanie został zaczerpnięty z pierwotnych rozważań (to że powinno wyjść \(\displaystyle{ O(logn)}\) wcale takie oczywiste nie jest). Tak czy siak elegancko i zgrabnie to wygląda. Jeśli dostanę w swoje ręce coś bardziej elementarnego, to wklepię.
Pozdrawiam

[Maciej87]

Po pierwsze, pierwsze pomysł jest mój, drugi nie

Po drugie, niestety w pierwszym nie potrafię wykorzystać redukcji redukcji znaków.
Trygonometryczna aproksymacja schodka jest ok jeśli funkcja której sumy liczymy jest faktycznie schodkiem. To jest przypadek wspomnianego Twierdzenia Erdosa-Turana i jest podobne pomysłem w dowodzie.
Ale jeśli jest kombinacją... To robiąc rozkład na dwa schodki- w istocie każdy szacując osobno, pojawia się, jak w oryginalnym twierdzeniu, ten błąd \(\displaystyle{ \frac{m}{n}}\)
Żeby wykorzystać redukcję znaków, trzeba aproksymować koniecznie wielomianem o średniej (to jest problem wyrazu \(\displaystyle{ c_0}\)) bliższej \(\displaystyle{ 0}\), powiedzmy rzędu \(\displaystyle{ \mathcal{O}(n^{-1+\varepsilon})}\)

Popracuję jeszcze trochę nad ulepszeniem metody fourierowskiej, ale jak dla mnie rozwiązanie drugie jest jednak z całkiem innej beczki.

[Piotr Rutkowski]

Kolejne ciekawe zadanie. Tym razem nie jest ono bardzo wymagające (w końcu jakieś udało się zrobić ), ale jest kilka ciekawych faktów, które można z niego wydedukować.

4.
Mamy zadane dwa nierosnące ciągi \(\displaystyle{ \{a_{n}\}_{n=1}^{\infty} \ \{b_{n}\}_{n=1}^{\infty}}\), z których oba są zbieżne do zera. Ponadto szereg \(\displaystyle{ \sum_{n=1}^{\infty}a_{n}}\) jest zbieżny, natomiast szereg \(\displaystyle{ \sum_{n=1}^{\infty}b_{n}}\) jest rozbieżny. Czy istnieje \(\displaystyle{ N\in \mathbb{N}}\) takie, że \(\displaystyle{ \forall_{n\geq N} \ b_{n}\geq a_{n}}\)?

Pozdrawiam

[Wasilewski]

Skoro pojawiają się tu zadania, które nie doczekały się rozwiązania przez obecnych studentów pierwszego roku UW, to i ja pozwolę sobie dodać kolejny problem:
5.
Niech \(\displaystyle{ A}\) będzie macierzą rozmiaru \(\displaystyle{ 2\times 2}\) taką, że \(\displaystyle{ A^{n} = I}\) oraz \(\displaystyle{ A^{k} \neq I}\) dla \(\displaystyle{ k \in \{1,\ldots, n-1\}}\). Wyznaczyć wszystkie \(\displaystyle{ n\ge 3}\) takie, że A jest podobna do macierzy \(\displaystyle{ \begin{bmatrix} \cos t & \sin t \\ -\sin t & \cos t\end{bmatrix}}\) dla pewnego \(\displaystyle{ t \in \mathbb{R}}\).
Chodzi mi o rozwiązanie, które w ogóle nie wspomina o czymś takim, jak postać kanoniczna Jordana.