Benutzer:Jobu0101/±1-Folge

Eine ±1-Folge ist eine Abbildung $f:\mathbb {N} \to \{\pm 1\}$, also eine unendliche Folge der Zahlen $+1$ und $-1$.

Beispiele

• Ein einfaches Beispiel ist $f(n):=(-1)^{n}$. Es beschreibt die alternierende Folge $-1,+1,-1,+1,-1,+1,\dots$.
• Über die Signumfunktion kann jede reellwertige Folge in eine Folge der Zahlen -1, 0 und 1 umgewandelt werden. Ist die ursprüngliche Folge keine, die ab einem gewissen Punkt konstant 0 wird, erhält man so durch Weglassen der Nullen eine ±1-Folge.

Erdős' Diskrepanz-Problem

Um 1932 stellte Paul Erdős die Vermutung auf, für jede ±1-Folge $f$ sei

$\sup _{n,d\in \mathbb {N} }\left|\sum _{j=1}^{n}f(jd)\right|=\infty .$

Erst im Jahr 2015 gelang Terence Tao der Beweis, zuvor galt das Problem als ungelöst.

Äquivalent ausgedrückt bedeutet die Gleichung, dass man zu jeder ±1-Folge $f$ und jeder natürlichen Zahl $m$ zwei natürliche Zahlen $d$ und $n$ findet, so dass die Summe $f(d)+f(2d)+\dots +f(nd)$ betragsmäßig $m$ ist. Je größer $m$ ist, desto schwieriger ist es, solche Zahlen zu finden. So konnte erst im Februar 2014 mithilfe von Computern gezeigt werden, dass die längste endliche Folge, die diese Eigenschaft für $m=3$ nicht besitzt, eine Länge von $1160$ Gliedern hat. Ist eine unendliche Folge (wie im Erdős' Diskrepanz-Problem) gegeben, so kann man für $m=3$ also $d$ und $n$ immer so wählen, dass $dn\leq 1161$ gilt.

Beispiel

Betrachtet man die alternierende Folge $f(n):=(-1)^{n}$ von oben, so ist die Wahl $d=2$ gewinnbringend, denn

$\left|\sum _{j=1}^{n}f(2j)\right|=\left|\sum _{j=1}^{n}(-1)^{2j}\right|=\sum _{j=1}^{n}1=n.$

Das bedeutet, für ein gegebenes $m$ wählt man $n:=m$.

Längste endliche Folge für $m=2$

Ist das Bestimmen der längsten endlichen Folge, die die oben genannte Eigenschaft für $m=3$ nicht besitzt, sehr aufwändig und ein sehr aktuelles Resultat, so ist selbiges für $m=2$ eine Leichtigkeit: Dazu mache man sich klar, dass die folgenden beiden Regeln für eine solche Folge gelten müssen:

1. $f(2n)=-f(n)$,
2. $f(2n-1)=-f(2n)$.

Die erste Eigenschaft muss erfüllt sein, weil ansonsten $|f(n)+f(2n)|=2$ gilt. Um die zweite Eigenschaft einzusehen, mache man sich klar, dass die Summe der ersten $2n$ Glieder für jedes natürliche $n$ verschwinden muss. Das klappt aber nur, wenn $f(2n-1)$ durch $f(2n)$ ausgeglichen wird.

Diese beiden Eigenschaften bestimmen die Folge bereits vollständig, sofern der Wert von $f(1)$ festgelegt ist: Für gerade Werte gucke man bei der Hälfte und für ungerade Werte schaue man auf den folgenden geraden Wert. So ergibt sich mit $f(1)=1$:

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
$f(n)$	$+1$	$-1$	$-1$	$+1$	$-1$	$+1$	$+1$	$-1$	$-1$	$+1$	$+1$	$-1$

Wir erhalten $|f(3)+f(6)+f(9)+f(12)|=2$ und damit das erste Problem. Damit ist gezeigt, dass die längste Folge für $m=2$ elf Folgenglieder hat (die Wahl von $f(1)=-1$ dreht die Vorzeichen nur um), zwölf sind bereits zuviel. Weil nach dem Verzichten auf das zwölfte Glied jedoch nicht mehr $f(11)=-f(12)$ beachtet werden muss, kann $f(11)$ frei gewählt werden. Für einen gegebenen Startwert $f(1)$ gibt es also genau zwei Folgen maximaler Länge:

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$
$f(n)$	$+1$	$-1$	$-1$	$+1$	$-1$	$+1$	$+1$	$-1$	$-1$	$+1$	$+1$
$g(n)$	$+1$	$-1$	$-1$	$+1$	$-1$	$+1$	$+1$	$-1$	$-1$	$+1$	$-1$