🔢 mathematics

Subsequence Sums in Permutations

Dieser Artikel zeigt, dass für hinreichend große $n$ jede Permutation von $\{1, 2, \ldots, n\}$ eine 2-additive Teilfolge beliebiger fester Länge $k \geq 3$ enthält, liefert polynomiale Schranken für das erforderliche $n$ , bestimmt den exakten Schwellenwert von $n=18$ für monotone 2-additive Teilfolgen der Länge drei und erweitert diese Ergebnisse auf Produkte und inverse Summen unter Verwendung von Techniken der arithmetischen Ramsey-Theorie.

Ursprüngliche Autoren: Collier Gaiser, Paul Horn

Veröffentlicht 2026-05-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Collier Gaiser, Paul Horn

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich ein Kartenspiel vor, das mit den Zahlen 1 bis $n$ beschriftet ist und in eine völlig zufällige Reihenfolge gemischt wurde. Dieses gemischte Deck ist das, was Mathematiker eine Permutation nennen.

Seit langem stellen Mathematiker eine spezifische Frage zu diesen gemischten Decks: Egal wie Sie sie mischen, wenn das Deck groß genug ist, werden Sie dann immer eine kleine Gruppe von Karten finden können, die in sich eine spezielle mathematische Regel befolgen?

Dieser Artikel, verfasst von Collier Gaiser und Paul Horn, sagt „Ja", aber mit einer Wendung. Sie haben eine neue Art von Regel entdeckt, die in ausreichend großen Decks immer auftritt, und sie haben genau herausgefunden, wie groß das Deck sein muss, um dies zu garantieren.

Hier ist die Aufschlüsselung ihrer Entdeckung mit einfachen Analogien:

1. Die „Verdoppeln-Sie-Ihr-Geld"-Regel

Die Autoren suchen nach einem spezifischen Muster, das sie eine 2-additive Teilfolge nennen.

Stellen Sie es sich wie einen Zaubertrick mit drei Zahlen vor: $A, B, C$ .

Wenn Sie sie alle addieren ( $A + B + C$ ), sollte die Summe genau das Doppelte der ersten Zahl ( $2 \times A$ ) ODER das Doppelte der letzten Zahl ( $2 \times C$ ) sein.

Die große Entdeckung:
Der Artikel beweist, dass Sie, wenn Sie ein Deck mit „hinreichend vielen" Karten haben (die genaue Größe hängt davon ab, wie viele Karten Sie in Ihrer Gruppe haben wollen), garantiert eine Gruppe von $k$ Karten finden werden, die dieser Regel folgt.

Der Haken: Die Karten müssen nicht direkt nebeneinander im Deck liegen. Sie müssen nur in der richtigen Reihenfolge von links nach rechts erscheinen.
Das Ergebnis: Für jede Gruppengröße $k$ (solange $k \ge 3$ ) gibt es eine „magische Zahl" $n$ . Wenn Ihr Deck mehr als $n$ Karten hat, können Sie sie nicht so mischen, dass Sie dieses Muster vermeiden. Es ist unvermeidbar.

2. Wie groß muss das Deck sein?

Die Autoren sagten nicht nur „es ist groß"; sie berechneten die Grenzen.

Die obere Schranke: Sie bewiesen, dass Sie, wenn Ihr Deck ungefähr proportional zu $k^5$ ist (eine polynomiale Größe), garantiert das Muster finden werden.
Die untere Schranke: Sie zeigten auch, dass, wenn das Deck zu klein ist (spezifisch kleiner als eine bestimmte Formel), Sie es tatsächlich mischen können, um das Muster zu vermeiden.

Ein spezifisches Beispiel (Die „magische Zahl" 18):
Der Artikel konzentriert sich auf die kleinstmögliche Gruppe: eine Gruppe von drei Karten ( $k=3$ ).

Sie fragten: „Was ist die kleinste Deckgröße, bei der Sie gezwungen sind, drei Karten zu finden, bei denen die Summe das Doppelte der ersten oder das Doppelte der letzten ist?"
Die Antwort: 18.
Wenn Sie ein Deck mit 17 Karten haben, können Sie es auf eine sehr spezifische, trickreiche Weise mischen, um dieses Muster zu vermeiden.
Aber sobald Sie die 18. Karte hinzufügen, werden Sie, egal wie Sie mischen, unvermeidlich drei Karten finden, die der Regel entsprechen.
Analogie: Stellen Sie sich vor, Sie versuchen, 17 Personen in einer Reihe so aufzustellen, dass keine drei von ihnen eine bestimmte Höhen-Summen-Regel erfüllen. Das können Sie schaffen. Aber wenn Sie eine 18. Person hinzufügen, wird es mathematisch unmöglich, sie so anzuordnen, dass dieses spezifische Trio nicht entsteht.

3. Der „Monotone"-Twist

Die Autoren betrachteten auch eine strengere Version des Spiels. Was, wenn die drei Karten, die Sie finden, auch monoton sein müssen?

Monoton bedeutet, dass sie entweder streng ansteigen (wie 2, 5, 8) oder streng abfallen (wie 9, 4, 1).
Sie bewiesen, dass selbst mit dieser strengeren Regel die magische Zahl immer noch 18 ist. Wenn Sie 18 Karten haben, können Sie nicht vermeiden, drei Karten zu finden, die sowohl in der richtigen Reihenfolge sind als auch der „Verdoppelungs-Summen"-Regel folgen.

4. Multiplikation und Inverse Summen

Der Artikel hört nicht bei der Addition auf. Die Autoren nutzten ihre Erkenntnisse, um zu zeigen, dass ähnliche Regeln für andere mathematische Operationen gelten:

Multiplikation: Wenn Sie nach einer Gruppe suchen, bei der das Produkt der Zahlen dem Quadrat der ersten oder letzten Zahl entspricht, gilt dieselbe Logik. Wenn das Deck groß genug ist, ist dieses Muster unvermeidbar.
Inverse Summen: Sie betrachteten auch das Addieren von Brüchen (wie $1/A + 1/B + 1/C$ ). Sie bewiesen, dass Sie, wenn das Deck groß genug ist, eine Gruppe finden werden, bei der die Summe der Brüche dem Doppelten des ersten oder letzten Bruchs entspricht.

5. Warum das wichtig ist (in mathematischen Begriffen)

Vor diesem Artikel wussten Mathematiker, dass man ein Deck mischen kann, um arithmetische Progressionen zu vermeiden (wie 2, 4, 6 oder 5, 10, 15). Man kann diese Muster verstecken.

Dieser Artikel zeigt jedoch, dass man, während man arithmetische Progressionen verstecken kann, diese „2-additiven" Muster nicht verstecken kann. Es ist, als würde man sagen: „Sie können eine gerade Linie in einem chaotischen Haufen Sand verstecken, aber Sie können keine spezifische Dreiecksform verstecken."

Zusammenfassung

Das Problem: Können Sie ein Deck von Zahlen so mischen, dass keine kleine Gruppe einer spezifischen mathematischen Regel folgt?
Die Antwort: Nein. Wenn das Deck groß genug ist, ist die Regel unvermeidbar.
Die Regel: Die Summe der Gruppe entspricht dem Doppelten der ersten oder letzten Zahl.
Die Schwelle: Für eine Gruppe von 3 benötigen Sie mindestens 18 Zahlen, um das Auftreten der Regel zu garantieren.
Die Erweiterung: Diese Logik funktioniert auch für Multiplikation und Brüche.

Der Artikel liefert das mathematische „Sicherheitsnetz", das beweist, dass diese Muster in ausreichend großen Sammlungen von Zahlen unvermeidlich sind, unabhängig davon, wie chaotisch die Anordnung erscheint.

Technische Zusammenfassung: Teilsummen in Permutationen

Problemstellung
Diese Arbeit untersucht das Vorhandensein spezifischer arithmetischer Teilfolgen innerhalb von Permutationen der Menge $\{1, 2, \dots, n\}$ . Während die klassische arithmetische Ramsey-Theorie (z. B. der Satz von van der Waerden) monochrome arithmetische Progressionen in hinreichend großen gefärbten Mengen garantiert, zeigten Entringer und Jackson (1973), dass Permutationen monotone arithmetische Progressionen mit drei Gliedern (3-APs) vermeiden können. Die Autoren fragen, ob andere arithmetische Eigenschaften, insbesondere „additive" Teilfolgen, in großen Permutationen unvermeidbar sind.

Eine Folge positiver ganzer Zahlen $(a_1, a_2, \dots, a_k)$ wird als $\ell$ -additiv definiert, wenn die Summe ihrer Glieder $\sum_{i=1}^k a_i = \ell a_1$ oder $\sum_{i=1}^k a_i = \ell a_k$ erfüllt. Der Hauptfokus liegt auf 2-additiven Teilfolgen (bei denen die Summe dem Doppelten des ersten oder letzten Gliedes entspricht) und deren monotonen Varianten. Die Arbeit behandelt zwei Hauptfragen:

Gibt es für eine feste Länge $k \ge 3$ ein $n$ , sodass jede Permutation von $\{1, \dots, n\}$ eine 2-additive Teilfolge der Länge $k$ enthält?
Was sind die genauen Schwellenwerte und Grenzen für das Vorhandensein solcher Teilfolgen, insbesondere wenn sie auf monotone Folgen beschränkt sind?

Methodik
Die Autoren verwenden eine Kombination aus kombinatorischen Argumenten, Fallunterscheidungen und Techniken der arithmetischen Ramsey-Theorie.

Kombinatorische Konstruktion und Widerspruch: Die Kernbeweise für die Existenz (Sätze 1.1 und 1.3) beruhen auf der Konstruktion spezifischer Teilmengen von Permutationen und der Anwendung des Beweises durch Widerspruch. Durch die Analyse der relativen Positionen von Elementen (unter Verwendung von $L_p(s)$ und $R_p(s)$ zur Bezeichnung der Elemente links bzw. rechts von $s$ in einer Permutation $p$ ) zeigen die Autoren, dass das Vermeiden einer 2-additiven Teilfolge einen strukturellen Widerspruch im Aufbau der Permutation erzwingt.
Abschätzungstechniken: Um obere Schranken für das kleinste $n$ (bezeichnet als $f(k, 2)$ ) zu etablieren, definieren die Autoren eine Menge „gefährlicher" Summen, die sich aus den ersten $2k-1$ Elementen einer Permutation ableiten. Sie verwenden das kleinste gemeinsame Vielfache (kgV) dieser Summen, um einen Schwellenwert $N_k$ zu bestimmen, ab dem eine 2-additive Teilfolge erzwungen wird.
Untere Schranken und Gegenbeispiele: Untere Schranken werden durch die explizite Konstruktion von Permutationen der Größe $n-1$ etabliert, die die gewünschten Teilfolgen nicht enthalten.
Asymptotische Analyse: Die Arbeit verwendet den Primzahlsatz (über Ergebnisse von Rosser), um untere Schranken für die Anzahl solcher Teilfolgen in großen Permutationen abzuleiten.
Transformationsargumente: Um die Ergebnisse auf Produkte und Inverssummen zu erweitern, verwenden die Autoren Standardtransformationen, die additive Eigenschaften in $\{1, \dots, n\}$ auf multiplikative Eigenschaften in $\{2^1, \dots, 2^n\}$ und invers-additive Eigenschaften in $\{L_n/1, \dots, L_n/n\}$ abbilden (wobei $L_n$ das kgV von $1$ bis $n$ ist).

Hauptbeiträge und Ergebnisse

Existenz 2-additiver Teilfolgen (Satz 1.1):
Für jedes feste $k \ge 3$ enthält, wenn $n$ hinreichend groß ist, jede Permutation von $\{1, \dots, n\}$ eine 2-additive Teilfolge der Länge $k$ .
- Schranken: Die Arbeit liefert polynomiale Schranken für das kleinste solche $n$ $n$ , bezeichnet als $f(k, 2)$ $f (k, 2)$ .
  - Untere Schranke: $f(k, 2) \ge (k-1)(3k-4)/2$ .
  - Obere Schranke: $f(k, 2) \le 9(k-2)(k^2-k)^2/4$ .
- Exakter Wert für $k=3$ : Die Autoren beweisen, dass $f(3, 2) = 5$ gilt. Jede Permutation von $\{1, \dots, 5\}$ enthält eine 2-additive Teilfolge der Länge 3, während für $n=4$ ein Gegenbeispiel existiert.
Monotone 2-additive Teilfolgen (Satz 1.3):
Die Arbeit behandelt die strengere Bedingung, dass die Teilfolge monoton sein muss.
- Ergebnis: Wenn $n \ge 18$ , enthält jede Permutation von $\{1, \dots, n\}$ eine monotone 2-additive Teilfolge der Länge 3.
- Schärfe: Der Wert 18 ist optimal; eine spezifische Permutation von $\{1, \dots, 17\}$ wird konstruiert, die solche Teilfolgen vermeidet.
- Offene Frage: Es bleibt unbekannt, ob dies für monotone 2-additive Teilfolgen der Länge $k \ge 4$ gilt.
Allgemeine $\ell$ -additive Teilfolgen:
- Wenn $k = \ell$ , enthält die Identitätspermutation $(1, 2, \dots, n)$ keine $\ell$ -additive Teilfolge der Länge $k$ .
- Die Arbeit löst zwei spezifische gemischte Fälle:
  - $f(4, 3) = 8$ (Jede Permutation von 8 Elementen hat eine 3-additive Teilfolge der Länge 4).
  - $f(3, 4) = 13$ (Jede Permutation von 13 Elementen hat eine 4-additive Teilfolge der Länge 3).
- Der allgemeine Fall für $k \neq \ell$ mit $k, \ell \ge 4$ bleibt als offene Frage zurück.
Zählen von Teilfolgen:
Die Autoren liefern Schranken für die Mindestanzahl von $\ell$ -additiven Teilfolgen der Länge $k$ in jeder Permutation der Größe $n$ :
- Obere Schranke: $O(n^{k-1})$ .
- Untere Schranke: $\Omega(n / \log n)$ (unter der Annahme, dass $f(k, \ell)$ existiert), abgeleitet unter Verwendung von Argumenten zur Primzahlverteilung.
- Spezifische Schranken für monotone 2-additive Teilfolgen der Länge 3 werden angegeben als $n/[18(\log n - \log 18 + 2)] - 6 \le G(3, 2, n) \le \frac{1}{18}n^2 + \frac{7}{6}n$ .
Erweiterungen auf Produkte und Inverssummen:
Unter Verwendung von Transformationen der arithmetischen Ramsey-Theorie erweitert die Arbeit die additiven Ergebnisse auf:
- Multiplikativ: Jede hinreichend große Permutation hat eine Teilfolge, bei der das Produkt das Quadrat des ersten oder letzten Gliedes ist (2-multiplikativ).
- Invers-additiv: Jede hinreichend große Permutation hat eine Teilfolge, bei der die Summe der Kehrwerte das Doppelte des Kehrwerts des ersten oder letzten Gliedes ist.
- Die Arbeit stellt fest, dass für monotone 2-multiplikative Teilfolgen der Länge 3 der Schwellenwert höchstens 32 beträgt (und genau 32 ist, da für $n=31$ ein Gegenbeispiel existiert).

Bedeutung und Behauptungen
Die Arbeit behauptet, die ersten Schur-Rado-artigen Ergebnisse speziell für Permutationen zu etablieren und zu zeigen, dass Permutationen zwar monotone arithmetische Progressionen (3-APs) vermeiden können, aber keine 2-additiven Teilfolgen beliebiger Länge vermeiden können. Die Arbeit liefert die ersten polynomialen Schranken für das Vorhandensein dieser Strukturen und bestimmt exakte Schwellenwerte für kleine Fälle ( $k=3$ ).

Die Autoren formulieren ihren Beitrag bescheiden als Grundlage für weitere Studien. Sie heben hervor, dass der allgemeine Fall für $k \neq \ell$ offen bleibt und das Verhalten monotoner 2-additiver Teilfolgen für Längen $k > 3$ unbekannt ist. Die Arbeit positioniert diese Erkenntnisse als einen Schritt zum Verständnis des Zusammenspiels zwischen Permutationsstruktur und arithmetischen Eigenschaften und schlägt zukünftige Richtungen in gewichteten Teilsummen sowie in der Verfeinerung von Schwellenwerten für multiplikative und invers-additive Varianten vor.