🔢 mathematics

Subsequence Sums in Permutations

Dit artikel stelt vast dat voor voldoende grote $n$ elke permutatie van $\{1, 2, \ldots, n\}$ een 2-additieve deelrij van elke vaste lengte $k \geq 3$ bevat, levert polynomiale grenzen voor de vereiste $n$ , bepaalt de exacte drempel van $n=18$ voor monotone 2-additieve deelrijen van lengte drie, en breidt deze resultaten uit tot producten en inverse sommen met behulp van technieken uit de rekenkundige Ramsey-theorie.

Oorspronkelijke auteurs: Collier Gaiser, Paul Horn

Gepubliceerd 2026-05-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Collier Gaiser, Paul Horn

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een kaartspel voor met kaarten genummerd van 1 tot $n$ , die volledig willekeurig zijn geschud. Dit geschudde spel is wat wiskundigen een permutatie noemen.

Al lang stellen wiskundigen een specifieke vraag over deze geschudde decks: Ongeacht hoe je ze schudt, als het deck groot genoeg is, kun je dan altijd een kleine groep kaarten vinden die verstopt zit en een speciale wiskundige regel volgt?

Dit artikel, geschreven door Collier Gaiser en Paul Horn, zegt "Ja", maar met een draai. Ze hebben een nieuw type regel ontdekt dat altijd voorkomt in decks die groot genoeg zijn, en ze hebben precies berekend hoe groot het deck moet zijn om te garanderen dat dit gebeurt.

Hier is de uiteenzetting van hun ontdekking met behulp van eenvoudige analogieën:

1. De "Verdubbel Je Geld"-Regel

De auteurs zoeken naar een specifiek patroon dat ze een 2-additieve subreeks noemen.

Denk eraan als een goocheltruc met drie getallen: $A, B, C$ .

Als je ze allemaal optelt ( $A + B + C$ ), moet het totaal precies twee keer het eerste getal ( $2 \times A$ ) OF twee keer het laatste getal ( $2 \times C$ ) zijn.

De Grote Ontdekking:
Het artikel bewijst dat als je een deck kaarten hebt dat "voldoende groot" is (de exacte grootte hangt af van hoeveel kaarten je in je groep wilt), je gegarandeerd een groep van $k$ kaarten vindt die deze regel volgt.

De Haken en Ogen: De kaarten hoeven niet naast elkaar in het deck te staan. Ze hoeven alleen maar in de juiste volgorde van links naar rechts te verschijnen.
Het Resultaat: Voor elke groepsgrootte $k$ (zolang $k \ge 3$ ), is er een "magisch getal" $n$ . Als je deck meer dan $n$ kaarten heeft, kun je ze niet schudden zonder dit patroon te vermijden. Het is onvermijdelijk.

2. Hoe Groot Moet Het Deck Zijn?

De auteurs zeiden niet zomaar "het is groot"; ze berekenden de grenzen.

De Bovenste Grens: Ze bewezen dat als je deck ongeveer evenredig is met $k^5$ (een polynoomgrootte), je gegarandeerd het patroon vindt.
De Onderste Grens: Ze toonden ook aan dat als het deck te klein is (specifiek kleiner dan een bepaalde formule), je het inderdaad zo kunt schudden dat je het patroon vermijdt.

Een Specifiek Voorbeeld (Het "Magische Getal" 18):
Het artikel zoomt in op de kleinste mogelijke groep: een groep van drie kaarten ( $k=3$ ).

Ze vroegen zich af: "Wat is de kleinste deckgrootte waarbij je gedwongen bent drie kaarten te vinden waarbij de som het dubbele is van het eerste of het dubbele van het laatste?"
Het Antwoord: 18.
Als je een deck van 17 kaarten hebt, kun je ze op een zeer specifieke, lastige manier schudden om dit patroon te vermijden.
Maar zodra je de 18e kaart toevoegt, zul je hoe je ook schudt, onvermijdelijk drie kaarten vinden die aan de regel voldoen.
Analogie: Stel je voor dat je probeert 17 mensen in een rij te zetten zodat geen drie van hen voldoen aan een specifieke hoogte-som regel. Dat kun je doen. Maar als je een 18e persoon toevoegt, wordt het wiskundig onmogelijk om ze te rangschikken zonder dat specifieke trio te creëren.

3. De "Monotone" Draai

De auteurs keken ook naar een strengere versie van het spel. Wat als de drie kaarten die je vindt ook monotoon moeten zijn?

Monotoon betekent dat ze ofwel strikt stijgend zijn (zoals 2, 5, 8) ofwel strikt dalend (zoals 9, 4, 1).
Ze bewezen dat zelfs met deze strengere regel, het magische getal nog steeds 18 is. Als je 18 kaarten hebt, kun je niet vermijden drie kaarten te vinden die zowel in de juiste volgorde zitten als de "verdubbelde som"-regel volgen.

4. Vermenigvuldiging en Omgekeerde Sommen

Het artikel houdt niet op bij optellen. De auteurs gebruikten hun bevindingen om te tonen dat vergelijkbare regels gelden voor andere wiskundige bewerkingen:

Vermenigvuldiging: Als je zoekt naar een groep waarbij het product van de getallen gelijk is aan het kwadraat van het eerste of laatste getal, geldt dezelfde logica. Als het deck groot genoeg is, is dit patroon onvermijdelijk.
Omgekeerde Sommen: Ze keken ook naar het optellen van breuken (zoals $1/A + 1/B + 1/C$ ). Ze bewezen dat als het deck groot genoeg is, je een groep vindt waarbij de som van de breuken gelijk is aan twee keer de eerste of twee keer de laatste breuk.

5. Waarom Dit Belangrijk Is (In Wiskundige Termen)

Voor dit artikel wisten wiskundigen dat je een deck kunt schudden om rekenkundige rijen te vermijden (zoals 2, 4, 6 of 5, 10, 15). Je kunt die patronen verstoppen.

Dit artikel toont echter aan dat terwijl je rekenkundige rijen kunt verstoppen, je deze "2-additieve" patronen niet kunt verstoppen. Het is alsof je zegt: "Je kunt een rechte lijn verstoppen in een rommelige hoop zand, maar je kunt een specifiek driehoeksvorm niet verstoppen."

Samenvatting

Het Probleem: Kun je een deck van getallen zo schudden dat geen enkele kleine groep een specifieke wiskundige regel volgt?
Het Antwoord: Nee. Als het deck groot genoeg is, is de regel onvermijdelijk.
De Regel: De som van de groep is gelijk aan twee keer het eerste of laatste getal.
De Drempel: Voor een groep van 3 heb je minimaal 18 getallen nodig om te garanderen dat de regel verschijnt.
De Uitbreiding: Deze logica werkt ook voor vermenigvuldiging en breuken.

Het artikel biedt het wiskundige "veiligheidsnet" dat bewijst dat deze patronen onvermijdelijk zijn in verzamelingen van getallen die groot genoeg zijn, ongeacht hoe chaotisch de rangschikking ook lijkt.

Technische Samenvatting: Sommen van Deelrijen in Permutaties

Probleemstelling
Dit artikel onderzoekt het bestaan van specifieke rekenkundige deelrijen binnen permutaties van de verzameling $\{1, 2, \dots, n\}$ . Waar de klassieke rekenkundige Ramsey-theorie (bijvoorbeeld de stelling van van der Waerden) monochromatische rekenkundige rijen garandeert in voldoende grote gekleurde verzamelingen, toonden Entringer en Jackson (1973) aan dat permutaties monotoon rekenkundige rijen van drie termen (3-AP's) kunnen vermijden. De auteurs vragen zich af of andere rekenkundige eigenschappen, specifiek "additieve" deelrijen, onvermijdelijk zijn in grote permutaties.

Een rij van positieve gehele getallen $(a_1, a_2, \dots, a_k)$ wordt gedefinieerd als $\ell$ -additief als de som van haar termen voldoet aan $\sum_{i=1}^k a_i = \ell a_1$ of $\sum_{i=1}^k a_i = \ell a_k$ . De primaire focus ligt op 2-additieve deelrijen (waarbij de som gelijk is aan het dubbele van de eerste of laatste term) en hun monotone varianten. Het artikel behandelt twee hoofdvragen:

Bestaat er voor een vaste lengte $k \ge 3$ een $n$ zodanig dat elke permutatie van $\{1, \dots, n\}$ een 2-additieve deelrij van lengte $k$ bevat?
Wat zijn de precieze drempels en grenzen voor het bestaan van dergelijke deelrijen, met name wanneer deze beperkt zijn tot monotone rijen?

Methodologie
De auteurs maken gebruik van een combinatie van combinatorische argumenten, casusanalyses en technieken uit de rekenkundige Ramsey-theorie.

Combinatorische Constructie en Contradictie: De kernbewijzen voor bestaan (Stellingen 1.1 en 1.3) vertrouwen op het construeren van specifieke deelverzamelingen van permutaties en het gebruik van bewijs door contradictie. Door de relatieve posities van elementen te analyseren (met $L_p(s)$ en $R_p(s)$ om elementen links en rechts van $s$ in een permutatie $p$ aan te duiden), tonen de auteurs aan dat het vermijden van een 2-additieve deelrij leidt tot een structurele contradictie in de lay-out van de permutatie.
Bepalingsmethoden voor Grenzen: Om bovengrenzen te vestigen voor het kleinste $n$ (aangeduid als $f(k, 2)$ ), definiëren de auteurs een verzameling "gevaarlijke" sommen afgeleid van de eerste $2k-1$ elementen van een permutatie. Zij maken gebruik van het kleinste gemene veelvoud (kgv) van deze sommen om een drempel $N_k$ te bepalen, waarboven een 2-additieve deelrij wordt afgedwongen.
Ondergrenzen en Tegenvoorbeelden: Ondergrenzen worden vastgesteld door expliciet permutaties van grootte $n-1$ te construeren die de gewenste deelrijen missen.
Asymptotische Analyse: Het artikel maakt gebruik van de priemgetalstelling (via resultaten van Rosser) om ondergrenzen af te leiden voor het aantal van dergelijke deelrijen in grote permutaties.
Transformatie-argumenten: Om resultaten uit te breiden tot producten en inverse sommen, gebruiken de auteurs standaardtransformaties die additieve eigenschappen in $\{1, \dots, n\}$ afbeelden op multiplicatieve eigenschappen in $\{2^1, \dots, 2^n\}$ en inverse-additieve eigenschappen in $\{L_n/1, \dots, L_n/n\}$ (waarbij $L_n$ het kgv is van 1 tot $n$ ).

Belangrijkste Bijdragen en Resultaten

Bestaan van 2-Additieve Deelrijen (Stelling 1.1):
Voor elke vaste $k \ge 3$ , als $n$ voldoende groot is, bevat elke permutatie van $\{1, \dots, n\}$ een 2-additieve deelrij van lengte $k$ .
- Grenzen: Het artikel biedt polynoomgrenzen voor het kleinste dergelijke $n$ $n$ , aangeduid als $f(k, 2)$ $f (k, 2)$ .
  - Ondergrens: $f(k, 2) \ge (k-1)(3k-4)/2$ .
  - Bovengrens: $f(k, 2) \le 9(k-2)(k^2-k)^2/4$ .
- Exacte Waarde voor $k=3$ : De auteurs bewijzen dat $f(3, 2) = 5$ . Elke permutatie van $\{1, \dots, 5\}$ bevat een 2-additieve deelrij van lengte 3, terwijl er een tegenvoorbeeld bestaat voor $n=4$ .
Monotone 2-Additieve Deelrijen (Stelling 1.3):
Het artikel behandelt de strengere voorwaarde waarbij de deelrij monotoon moet zijn.
- Resultaat: Als $n \ge 18$ , bevat elke permutatie van $\{1, \dots, n\}$ een monotoon 2-additieve deelrij van lengte 3.
- Scherpte: De waarde 18 is optimaal; er wordt een specifieke permutatie van $\{1, \dots, 17\}$ geconstrueerd die dergelijke deelrijen vermijdt.
- Open Vraag: Het blijft onbekend of dit geldt voor monotone 2-additieve deelrijen van lengte $k \ge 4$ .
Algemene $\ell$ -Additieve Deelrijen:
- Als $k = \ell$ , bevat de identiteitspermutatie $(1, 2, \dots, n)$ geen $\ell$ -additieve deelrij van lengte $k$ .
- Het artikel lost twee specifieke gemengde gevallen op:
  - $f(4, 3) = 8$ (Elke permutatie van 8 elementen heeft een 3-additieve deelrij van lengte 4).
  - $f(3, 4) = 13$ (Elke permutatie van 13 elementen heeft een 4-additieve deelrij van lengte 3).
- Het algemene geval voor $k \neq \ell$ met $k, \ell \ge 4$ blijft een open vraag.
Aantal Deelrijen:
De auteurs geven grenzen voor het minimumaantal $\ell$ -additieve deelrijen van lengte $k$ in elke permutatie van grootte $n$ :
- Bovengrens: $O(n^{k-1})$ .
- Ondergrens: $\Omega(n / \log n)$ (onder de aanname dat $f(k, \ell)$ bestaat), afgeleid met argumenten over de verdeling van priemgetallen.
- Specifieke grenzen voor monotone 2-additieve deelrijen van lengte 3 worden gegeven als $n/[18(\log n - \log 18 + 2)] - 6 \le G(3, 2, n) \le \frac{1}{18}n^2 + \frac{7}{6}n$ .
Uitbreidingen tot Producten en Inverse Sommen:
Met behulp van transformaties uit de rekenkundige Ramsey-theorie breidt het artikel de additieve resultaten uit tot:
- Multiplicatief: Elke voldoende grote permutatie heeft een deelrij waarbij het product het kwadraat is van de eerste of laatste term (2-multiplicatief).
- Inverse-Additief: Elke voldoende grote permutatie heeft een deelrij waarbij de som van de reciproke waarden het dubbele is van de reciproke waarde van de eerste of laatste term.
- Het artikel merkt op dat voor monotone 2-multiplicatieve deelrijen van lengte 3, de drempel maximaal 32 is (en exact 32, aangezien er een tegenvoorbeeld bestaat voor $n=31$ ).

Betekenis en Claims
Het artikel claimt de eerste Schur-Rado-achtige resultaten specifiek voor permutaties te vestigen, en toont aan dat terwijl permutaties monotoon rekenkundige rijen (3-AP's) kunnen vermijden, ze geen 2-additieve deelrijen van willekeurige lengte kunnen vermijden. Het werk biedt de eerste polynoomgrenzen voor het bestaan van deze structuren en bepaalt exacte drempels voor kleine gevallen ( $k=3$ ).

De auteurs presenteren hun bijdrage bescheiden als een fundament voor verder onderzoek. Zij benadrukken dat het algemene geval voor $k \neq \ell$ open blijft en dat het gedrag van monotone 2-additieve deelrijen voor lengten $k > 3$ onbekend is. Het artikel positioneert deze bevindingen als een stap naar het begrijpen van de wisselwerking tussen permutatiestructuur en rekenkundige eigenschappen, en suggereert toekomstige richtingen in gewogen sommen van deelrijen en de verfijning van drempels voor multiplicatieve en inverse-additieve varianten.