Ein paar Big-O-Fragen zu einem Problem aus der Zahlentheorie

Question

Ein paar Big-O-Fragen zu einem Problem aus der Zahlentheorie

Asymptotik
Mathematik
Wettbewerb-Mathematik
Zahlentheorie

Benutzer75619

Ich gehe offizielle Lösungen für IMO'09-Probleme durch. Momentan bei Lösung 2 für N7 hängen geblieben. Ich kopiere Teile, die mich unten verwirren, aber wenn sich jemand für den Rest interessiert, ist dies ein Link zum vollständigen PDF.

Hier nun meine Fragen:

Vermietung $s_n=(ab)^n-\gamma_1\left(\frac{a}{b}\right)^n-\ldots-\gamma_k\left(\frac{a}{b^{2k-1}}\right)^n$ , ich verstehe nicht ganz, wie sie hergeleitet werden $z_n=s_n+O\left(\frac{b}{a}\right)^n$ . Wird die folgende Erklärung gut genug sein?

Wenn wir lassen $\alpha_n=z_n-s_n$ , Dann $(s_n+\alpha_n)^2=z_n^2\equiv z_n^2+0$ . Aus der Lösung $z_n^2+O(B^n)=\{s_n+O\left(\frac{b}{a}\right)^n\}^2$ , und da $0=O(B^n)$ , haben wir unbedingt $\alpha_n=O\left(\frac{b}{a}\right)^n$ . Ist es das?

Wenn Koeffizienten $\delta_i$ eingeführt werden, $\delta_0$ größer bestimmt wird als $0$ Weil $z_n>0$ . Wie? Liegt es daran, dass für große Werte von $n$ Begriff $(ab)^n$ dominiert, also muss sein Koeffizient positiv sein?
Nach der letzten zentrierten Formel leiten sie ab $a=b^{k-1}$ aus asymptotischen Berechnungen. Was sind diese Berechnungen und warum $a=b^{k-1}$ von ihnen folgen? Etwas wie das Folgende?

Wenn wir vergeben $\epsilon_n$ sein $O\left(\frac{A}{B^k}\right)^n$ , Dann $\epsilon_n\to0$ , Weil $A<B^k$ . Wenn wir in der letzten zentrierten Formel jetzt alles verschieben, außer $\epsilon_n$ , auf der linken Seite haben wir insbesondere $A^nB^n(1-\delta_0^2)$ Dort. Wenn $1-\delta_0^2\neq0$ Dieser Begriff dominiert für große $n$ und somit wird die linke Seite niemals dazu neigen $0$ , aber die rechte Seite neigt dazu $0$ , So $1-\delta_0^2=0$ . Und so weiter für $\delta_1$ und die anderen …

Ist es das?

Unmittelbar nach dem, was in 3. besprochen wird, schließen sie, dass es welche geben sollte $P\in\mathbb{Q}[x]$ wofür $(X-1)(X^{k-1}-1)=P(X)^2$ . Warum? Soweit ich sehen kann, wenn wir es zulassen $X=B^n$ , Dann $A^n=X^{k-1}$ und wir haben $(A^n-1)(B^n-1)=(X-1)(X^{k-1}-1)$ . Betrachten wir es jetzt als Polynom in Variable $X$ , von der Annahme, dass $(A^n-1)(B^n-1)$ ist ein perfekter Platz für alle $n$ Dieses Polynom bildet abzählbar unendlich viele ganze Zahlen auf perfekte Quadrate ab. Wie leiten wir nun ab, dass es notwendigerweise ein perfektes Quadrat eines Polynoms in sein muss $X$ ?

Danke schön.

Antworten (1)

Ein paar Big-O-Fragen zu einem Problem aus der Zahlentheorie

Ѕᴀᴀᴅ · Answer 1

$\def\peq{\mathrel{\phantom{=}}{}}$ Erstens gibt es einen Tippfehler in der Definition von $\{γ_n\}$ . Es sollte sein

2 γ_{1} = 1, γ_{N} = \sum_{J = 1}^{N - 1} γ_{J} γ_{N - J} . (N ⩾ 2)

$2γ_1 = 1, \quad γ_n = \sum_{j = 1}^{n - 1} γ_j γ_{n - j}. \quad (n \geqslant 2)$ Bei der ersten Frage gibt es in der offiziellen Antwort einen gewissen Missbrauch von Notationen. Eigentlich seit

0 < γ_{n} < 1

$0 < γ_n < 1$ für alle

n ⩾ 1

$n \geqslant 1$ Und

B^{k - 1} ⩽ A < B^{k}

$B^{k - 1} \leqslant A < B^k$ , Dann

\begin{aligned} S_{N}^{2} & = {((A B)^{N} - \sum_{J = 1}^{k} γ_{J} {(\frac{A}{B^{2 J - 1}})}^{N})}^{2} \\ = ((A B)^{N})^{2} - 2 (A B)^{N} \cdot \sum_{J = 1}^{k} γ_{J} {(\frac{A}{B^{2 J - 1}})}^{N} + {(\sum_{J = 1}^{k} γ_{J} {(\frac{A}{B^{2 k - 1}})}^{N})}^{2} \\ = (A B)^{N} - \sum_{J = 1}^{k} 2 γ_{J} {(\frac{A}{B^{J - 1}})}^{N} + \sum_{J = 2}^{k} \sum_{l = 1}^{J - 1} γ_{l} γ_{J - l} {(\frac{A}{B^{2 l - 1}})}^{N} {(\frac{A}{B^{2 (J - l) - 1}})}^{N} \\ + \sum_{\begin{matrix} 1 ⩽ J, l ⩽ k \\ J + l ⩾ k + 1 \end{matrix}} γ_{J} γ_{l} {(\frac{A}{B^{2 J - 1}})}^{N} {(\frac{A}{B^{2 l - 1}})}^{N} \\ = (A B)^{N} - \sum_{J = 1}^{k} 2 γ_{J} {(\frac{A}{B^{J - 1}})}^{N} + \sum_{J = 2}^{k} \sum_{l = 1}^{J - 1} γ_{l} γ_{J - l} {(\frac{A}{B^{J - 1}})}^{N} + Ö ({(\frac{A}{B^{k}})}^{N}) \\ = (A B)^{N} - 2 γ_{1} A^{N} - \sum_{J = 2}^{k} (2 γ_{J} - \sum_{l = 1}^{J - 1} γ_{l} γ_{J - l}) {(\frac{A}{B^{J - 1}})}^{N} + Ö ({(\frac{A}{B^{k}})}^{N}) \\ (1) & = (A B)^{N} - A^{N} + Ö ({(\frac{A}{B^{k}})}^{N}) = z_{N}^{2} + B^{N} - 1 + Ö (B^{N}) . \end{aligned}

$\begin{align*} s_n^2 &= \left( (ab)^n - \sum_{j = 1}^k γ_j \left( \frac{a}{b^{2j - 1}} \right)^n \right)^2\\ &= ((ab)^n)^2 - 2(ab)^n · \sum_{j = 1}^k γ_j \left( \frac{a}{b^{2j - 1}} \right)^n + \left( \sum_{j = 1}^k γ_j \left( \frac{a}{b^{2k - 1}} \right)^n \right)^2\\ &= (AB)^n - \sum_{j = 1}^k 2γ_j \left( \frac{A}{B^{j - 1}} \right)^n + \sum_{j = 2}^k \sum_{l = 1}^{j - 1} γ_l γ_{j - l} \left( \frac{a}{b^{2l - 1}} \right)^n \left( \frac{a}{b^{2(j - l) - 1}} \right)^n\\ &\peq + \sum_{\substack{1 \leqslant j, l \leqslant k\\j + l \geqslant k + 1}} γ_j γ_l \left( \frac{a}{b^{2j - 1}} \right)^n \left( \frac{a}{b^{2l - 1}} \right)^n\\ &= (AB)^n - \sum_{j = 1}^k 2γ_j \left( \frac{A}{B^{j - 1}} \right)^n + \sum_{j = 2}^k \sum_{l = 1}^{j - 1} γ_l γ_{j - l} \left( \frac{A}{B^{j - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right)\\ &= (AB)^n - 2γ_1 A^n - \sum_{j = 2}^k \left( 2γ_j - \sum_{l = 1}^{j - 1} γ_l γ_{j - l} \right) \left( \frac{A}{B^{j - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right)\\ &= (AB)^n - A^n + O\left( \left( \frac{A}{B^k} \right)^n \right) = z_n^2 + B^n - 1 + O(B^n). \tag{1} \end{align*}$ Beachten Sie, dass

z_{n} \sim (a b)^{n} (n \to \infty)

$z_n \sim (ab)^n\ (n → ∞)$ Und

a > b

$a > b$ , dann impliziert (1).

s_{n} \sim (a b)^{n} (n \to \infty)

$s_n \sim (ab)^n\ (n → ∞)$ Und

| z_{N} - S_{N} | = \frac{| z_{N}^{2} - S_{N}^{2} |}{z_{N} + S_{N}} \sim \frac{B^{N}}{2 (A B)^{N}} = 2 {(\frac{B}{A})}^{N}, N \to \infty

$|z_n - s_n| = \frac{|z_n^2 - s_n^2|}{z_n + s_n} \sim \frac{B^n}{2(ab)^n} = 2\left( \frac{b}{a} \right)^n, \quad n → ∞$ was impliziert

z_{n} = s_{n} + O ({(\frac{b}{a})}^{n})

$z_n = s_n + O\left( \left( \dfrac{b}{a} \right)^n \right)$ .

Bei der zweiten Frage ist Ihre Argumentation richtig.

Für die dritte Frage lässt sich analog zu (1) die für einige herleiten $N_0 \geqslant 1$ und alle $n \geqslant N_0$ ,

\begin{aligned} A^{N} B^{N} - A^{N} - B^{N} + 1 = z_{N}^{2} = {(δ_{0} (A B)^{N} - \sum_{J = 1}^{k} δ_{J} {(\frac{A}{B^{2 J - 1}})}^{N})}^{2} \\ (2) & = δ_{0}^{2} (A B)^{N} - 2 δ_{0} δ_{1} A^{N} - \sum_{J = 2}^{k} (2 δ_{0} δ_{J} - \sum_{l = 1}^{J - 1} δ_{l} δ_{J - l}) {(\frac{A}{B^{J - 1}})}^{N} + Ö ({(\frac{A}{B^{k}})}^{N}) . \end{aligned}

$\begin{align*} &\peq A^n B^n - A^n - B^n + 1 = z_n^2 = \left( δ_0 (ab)^n - \sum_{j = 1}^k δ_j \left( \frac{a}{b^{2j - 1}} \right)^n \right)^2\\ &= δ_0^2 (AB)^n - 2δ_0 δ_1 A^n - \sum_{j = 2}^k \left( 2δ_0 δ_j - \sum_{l = 1}^{j - 1} δ_l δ_{j - l} \right) \left( \frac{A}{B^{j - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right). \tag{2} \end{align*}$ Beachten Sie, dass

A > B

$A > B$ . Zuerst dividieren durch

(A B)^{n}

$(AB)^n$ auf beiden Seiten von (2) und Herstellung

n \to \infty

$n → ∞$ Erträge

δ_{0}^{2} = 1

$δ_0^2 = 1$ , daher

δ_{0} = 1

$δ_0 = 1$ . Als nächstes subtrahieren

(A B)^{n}

$(AB)^n$ von beiden Seiten von (2), dann dividieren durch

A^{n}

$A^n$ und machen

n \to \infty

$n → ∞$ Erträge

2 δ_{0} δ_{1} = 1

$2δ_0 δ_1 = 1$ , daher

δ_{1} = \frac{1}{2}

$δ_1 = \dfrac{1}{2}$ . Jetzt für

m = 2, \dots, k - 2

$m = 2, \cdots, k - 2$ , jedes Mal subtrahieren

(A B)^{N} - A^{N} - \sum_{J = 2}^{M - 1} (2 δ_{J} - \sum_{l = 1}^{J - 1} δ_{l} δ_{J - l}) {(\frac{A}{B^{J - 1}})}^{N}

$(AB)^n - A^n - \sum_{j = 2}^{m - 1} \left( 2δ_j - \sum_{l = 1}^{j - 1} δ_l δ_{j - l} \right) \left( \frac{A}{B^{j - 1}} \right)^n$ von beiden Seiten von (2), dann dividieren durch

{(\frac{A}{B^{m - 1}})}^{n}

$\left( \dfrac{A}{B^{m - 1}} \right)^n$ und machen

n \to \infty

$n → ∞$ Erträge

2 δ_{m} = \sum_{j = 1}^{m - 1} δ_{j} δ_{m - j}

$2δ_m = \sum\limits_{j = 1}^{m - 1} δ_j δ_{m - j}$ . Nun reduziert sich (2) auf

\begin{aligned} - B^{N} + 1 & = - (2 δ_{0} δ_{k - 1} - \sum_{l = 1}^{k - 2} δ_{l} δ_{k - 1 - l}) {(\frac{A}{B^{k - 2}})}^{N} \\ (3) & - (2 δ_{0} δ_{k} - \sum_{l = 1}^{k - 1} δ_{l} δ_{k - l}) {(\frac{A}{B^{k - 1}})}^{N} + Ö ({(\frac{A}{B^{k}})}^{N}) . \end{aligned}

$\begin{align*} -B^n + 1 &= - \left( 2δ_0 δ_{k - 1} - \sum_{l = 1}^{k - 2} δ_l δ_{k - 1 - l} \right) \left( \frac{A}{B^{k - 2}} \right)^n\\ &\peq - \left( 2δ_0 δ_k - \sum_{l = 1}^{k - 1} δ_l δ_{k - l} \right) \left( \frac{A}{B^{k - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right). \tag*{(3)} \end{align*}$ Vermuten

a > b^{k - 1}

$a > b^{k - 1}$ , Dann

A > B^{k - 1}

$A > B^{k - 1}$ und analog

2 δ_{k - 1} = \sum_{j = 1}^{k - 2} δ_{j} δ_{k - 1 - j}

$2δ_{k - 1} = \sum\limits_{j = 1}^{k - 2} δ_j δ_{k - 1 - j}$ . Dann wird (3) zu

- B^{N} + 1 = - (2 δ_{0} δ_{k} - \sum_{l = 1}^{k - 1} δ_{l} δ_{k - l}) {(\frac{A}{B^{k - 1}})}^{N} + Ö ({(\frac{A}{B^{k}})}^{N}),

$-B^n + 1 = -\left( 2δ_0 δ_k - \sum_{l = 1}^{k - 1} δ_l δ_{k - l} \right) \left( \frac{A}{B^{k - 1}} \right)^n + O\left( \left( \frac{A}{B^k} \right)^n \right),$ und Dividieren durch

B^{n}

$B^n$ und machen

n \to \infty

$n → ∞$ führt zu einem Widerspruch (Beachten Sie, dass

A < B^{k}

$A < B^k$ ). Daher,

a = b^{k - 1}

$a = b^{k - 1}$ Und

k ⩾ 3

$k \geqslant 3$ .

Für die letzte Frage verstehe ich die Logik in diesem Schritt nicht, aber hier ist ein Weg, ähnliche Ideen zu verwenden: Since $a = b^{k - 1}$ , Dann

(B^{2 N (k - 1)} - 1) (B^{2 N} - 1) = z_{N}^{2} = {(δ_{0} B^{N k} - \sum_{J = 1}^{k} δ_{J} B^{N (k - 2 J)})}^{2} ⟹ ((B^{N})^{2 (k - 1)} - 1) ((B^{N})^{2} - 1) (B^{N})^{2 k} = {(δ_{0} (B^{N})^{2 k} - \sum_{J = 1}^{k} δ_{J} (B^{N})^{2 (k - J)})}^{2} .

$(b^{2n(k - 1)} - 1)(b^{2n} - 1) = z_n^2 = \left( δ_0 b^{nk} - \sum_{j = 1}^k δ_j b^{n(k - 2j)} \right)^2\\ \Longrightarrow ((b^n)^{2(k - 1)} - 1)((b^n)^2 - 1)(b^n)^{2k} = \left( δ_0 (b^n)^{2k} - \sum_{j = 1}^k δ_j (b^n)^{2(k - j)} \right)^2.$ Daher,

(X^{2 (k - 1)} - 1) (X^{2} - 1) X^{2 k} = {(δ_{0} X^{2 k} - \sum_{J = 1}^{k} δ_{J} X^{2 (k - J)})}^{2} = (Q (X))^{2},

$(X^{2(k - 1)} - 1)(X^2 - 1)X^{2k} = \left( δ_0 X^{2k} - \sum_{j = 1}^k δ_j X^{2(k - j)} \right)^2 = (Q(X))^2,$ was da zum widerspruch führt

k ⩾ 3

$k \geqslant 3$ Und

\frac{X^{2 (k - 1)} - 1}{X^{2} - 1}

$\dfrac{X^{2(k - 1)} - 1}{X^2 - 1}$ hat keine mehrfachen Nullen.

Wenn Sie sagen, dass sie die Notation missbrauchen, meinen Sie, wir sollten es vorziehen, das große O nur auf einer Seite der Gleichung zu haben?
@ user75619 Eigentlich meine ich beim Schreiben ${((A B)^{N} - \sum_{J = 1}^{k} γ_{k} {(\frac{A}{B^{2 J - 1}})}^{N} + Ö ({(\frac{B}{A})}^{N}))}^{2} = A^{N} B^{N} - 2 γ_{1} A^{N} - \sum_{J = 2}^{k} (2 γ_{J} - \sum_{l = 1}^{J - 1} γ_{l} γ_{J - l}) {(\frac{A}{B^{J - 1}})}^{N} + Ö ({(\frac{A}{B^{k}})}^{N}) + Ö (B^{N}),$ $\left((ab)^n-\sum_{j=1}^kγ_k\left(\frac a{b^{2j-1}}\right)^n+O\left(\left(\frac ba\right)^n\right)\right)^2\\=A^nB^n-2γ_1A^n-\sum_{j=2}^k\left(2γ_j-\sum_{l=1}^{j-1}γ_lγ_{j-l}\right)\left(\frac A{B^{j-1}}\right)^n+O\left(\left(\frac A{B^k}\right)^n\right)+O(B^n),$ es ist wirklich schwer zu sagen, was dabei rauskommt $O\left(\left(\dfrac ba\right)^n\right)$ und was reinkommt $O\left(\left(\dfrac A{B^k}\right)^n\right)$ Und $O(B^n)$ .
Ich habe Ihre Erklärung in 1. erhalten, ich frage mich immer noch, ob ich recht hatte, als ich tat, was ich tat. Wenn wir den Notationsmissbrauch beseitigen und ihre Behauptung auf diese Weise umschreiben würden $Wenn (S_{N} + a_{N})^{2} = z_{N}^{2} + β_{N}, Dann$ $\text{ if }(s_n+\alpha_n)^2=z_n^2+\beta_n, \text{ then }$ $a_{N} = Ö {(\frac{B}{A})}^{N} \Rightarrow β_{N} = Ö (B^{N}) Und$ $\alpha_n=O\left(\frac{b}{a}\right)^n\Rightarrow\beta_n=O(B^n) \text { and }$ $β_{N} = Ö (B^{N}) \Rightarrow a_{N} = Ö {(\frac{B}{A})}^{N}$ $\beta_n=O(B^n)\Rightarrow\alpha_n=O\left(\frac{b}{a}\right)^n$ könnten wir das dann ableiten $\alpha_n=z_n-s_n$ ist unbedingt $O\left(\frac{b}{a}\right)^n$ , seit $z_n^2+0=(s_n+\alpha_n)^2$ Und $0=O(B^n)$ ?
@ user75619 Die Implikation in den neuen Behauptungen in den Kommentaren scheint nicht unbedingt wahr zu sein.
Dann verstehe ich wohl nicht ganz, wie groß O funktioniert, lol ... Mein Eindruck war dieser $(s_n+O\left(\frac{b}{a}\right)^n)^2=z_n^2+O(B^n)$ kann in beide Richtungen gelesen werden, und wenn es von rechts nach links gelesen wird, bedeutet dies, dass wir einige Zahlen addieren würden $\beta_n$ Zu $z_n^2$ dann wären da noch ein paar nummern $\alpha_n$ so dass $(s_n+\alpha_n)^2=z_n^2+\beta_n$ Und $\alpha_n$ wäre $O\left(\frac{b}{a}\right)^n$ , vorausgesetzt, nur das $\beta_n$ war $O(B^n)$ .
Das weiß ich... Aber ich hatte den Eindruck, dass da $0\leq M_2|B^n|$ es sollte implizieren, dass es eine Konstante geben musste $M_1>0$ so dass $|\alpha_n|\leq M_1\left|(b/a)^n\right|$ Und $(s_n+\alpha_n)^2=z_n^2$ .
@ user75619 Wie gesagt, diese Implikation ist nicht unbedingt wahr. Zumindest braucht es mehr Beweise.

Ein paar Big-O-Fragen zu einem Problem aus der Zahlentheorie

Benutzer75619

Antworten (1)

Ѕᴀᴀᴅ

Benutzer75619

Ѕᴀᴀᴅ

Benutzer75619

Ѕᴀᴀᴅ

Benutzer75619

Benutzer75619

Ѕᴀᴀᴅ

Benutzer75619

Anzahl der Ziffern in 8n8n8^n zur Basis 666

Existenz einer Teilmenge, so dass das Produkt seiner Elemente ein perfektes Quadrat ist

Beweisen Sie, dass es keine 5-stelligen EXTREME PRIMES gibt.

Anzahl der Zusammensetzungen von nnn, sodass jeder Term kleiner als gleich kkk ist

PRMO-Modellfrage: "Das kleinste LCM von 20 natürlichen Zahlen, die nicht unbedingt unterschiedlich sind und deren Summe 413 ist, ist _________"

Zeigen Sie, dass am Ende eine gerade ganze Zahl existiert

Zeigt, dass a2+b2+c2+d2+e2+65=abcdea2+b2+c2+d2+e2+65=abcdea^2+b^2+c^2+d^2+e^2+65=abcde hat ganzzahlige Lösungen größer als 201820182018?

Der Abstand zwischen Potenz von 3 und der größten Potenz von 2

Allseitig gegebene Trapezfläche: Warum ist dies ein olympisches Problem? [geschlossen]

Anwendungen des Exponentialintegrals?