🔢 mathematics

Monochromatic products in random integer sets

Dit artikel onderzoekt de drempelwaarschijnlijkheid waarbij een willekeurige deelverzameling van gehele getallen bijna zeker een monochromatische oplossing bevat voor de vergelijking $ab=c$ onder een 2-kleuring, waarbij grenzen tussen $n^{-1/9-o(1)}$ en $n^{-1/11}$ worden vastgesteld en wordt aangetoond dat het gedrag en de bewijstechnieken voor dergelijke niet-lineaire vergelijkingen wezenlijk verschillen van die van lineaire vergelijkingen.

Oorspronkelijke auteurs: Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

Gepubliceerd 2026-01-15

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

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 voor dat je een enorme zak met genummerde tegels hebt, van 1 tot $n$ . Je besluit een willekeurige handvol van deze tegels te houden door voor elke tegel een muntje op te gooien: kop, je houdt hem; munt, je gooit hem weg. De kans om een tegel te houden is $p$ .

Stel je nu voor dat je een emmer verf hebt met $r$ verschillende kleuren. Je wilt elke tegel in je willekeurige handvol een kleur geven. De grote vraag is: is het mogelijk om ze zo te schilderen dat je een "monochromatisch product" vermijdt?

Een "monochromatisch product" is een trio tegels $(a, b, c)$ die allemaal dezelfde kleur hebben, waarbij $a \times b = c$ . Bijvoorbeeld, als je de tegels 2, 3 en 6 hebt, en ze zijn allemaal rood geschilderd, dan heb je een "rood product" omdat $2 \times 3 = 6$ .

Dit artikel is een wiskundig detectives verhaal over het vinden van het exacte kantelpunt (de drempelwaarde) waar het onmogelijk wordt om dergelijke monochromatische trio's te vermijden, ongeacht hoe slim je ze schildert.

De Achtergrond: De Som versus Het Product

Wiskundigen weten al heel lang dat als je genoeg getallen hebt, je een "monochromatische som" (waarbij $a + b = c$ ) niet kunt vermijden. Dit is een beroemd resultaat genaamd Schur's Theorema.

In de jaren 90 vroegen onderzoekers zich af: "Wat als onze zak met getallen erg ijl is? Hoeveel getallen moeten we kiezen voordat we gegarandeerd een monochromatische som vinden?" Ze vonden het antwoord: als je getallen kiest met een waarschijnlijkheid die ongeveer gelijk is aan $1/\sqrt{n}$ , ben je gegarandeerd een som te vinden. Als je er minder kiest, kun je er meestal een vermijden.

Dit artikel stelt dezelfde vraag, maar dan voor producten ( $a \times b = c$ ) in plaats van sommen.

De Belangrijkste Ontdekking: Een Nieuw Kantelpunt

De auteurs ontdekten dat de regels voor producten heel anders zijn dan de regels voor sommen.

De "Som"-regel: Voor sommen is het kantelpunt rond $n^{-1/2}$ (1 over de wortel van $n$ ).
De "Product"-regel: Voor producten ligt het kantelpunt veel lager. De auteurs bewezen dat voor een willekeurige verzameling getallen om gegarandeerd een monochromatisch product te hebben, de waarschijnlijkheid van het kiezen van een getal ergens tussen $n^{-1/9}$ en $n^{-1/11}$ moet liggen.

De Analogie:
Denk aan het "Som"-probleem als het proberen te vinden van een specifieke vorm in een hoop zand. Je hebt een redelijke hoeveelheid zand nodig om zeker te weten dat de vorm er is.
Het "Product"-probleem is als het zoeken naar een zeer zeldzame kristalformatie. Omdat vermenigvuldigen zo snel groeit (2 keer 3 is 6, maar 10 keer 10 is 100), zijn de "kristallen" (de trio's $a, b, c$ ) veel moeilijker te vormen. Je hebt een veel dichtere verzameling getallen nodig (een hogere waarschijnlijkheid $p$ ) om te garanderen dat je er een vindt, maar paradoxaal genoeg is de drempelwaarde in termen van de exponent lager omdat de structuur van vermenigvuldiging zo ijl en onregelmatig is vergeleken met optellen.

Hoe Ze Het Oplosten: Een Tweeledige Aanval

Om deze drempelwaarde te vinden, moesten de auteurs twee dingen bewijzen:

1. Het "Slechte Nieuws" (De Ondergrens):
Ze toonden aan dat als je getallen te ijl kiest (onder $n^{-1/9}$ ), je ze bijna altijd met twee kleuren (bijvoorbeeld Rood en Blauw) kunt schilderen zodat er geen Rood trio en geen Blauw trio bestaat.

De Methode: Ze gebruikten een "Greedy Algoritme" (een hebzuchtig algoritme). Stel je voor dat je de getallen in volgorde schildert, van klein naar groot. Je probeert een getal Rood te schilderen. Als het Rood schilderen van een getal een Rood product zou creëren met getallen die je al eerder Rood hebt geschilderd, schilder je het in plaats daarvan Blauw. Als het Blauw schilderen van een getal een Blauw product zou creëren, zit je vast.
Het Resultaat: Ze bewezen dat als de verzameling ijl genoeg is, dit hebzuchtige schilderproces bijna nooit vastloopt. Je kunt de hele verzameling succesvol inkleuren zonder een monochromatisch product te maken.

2. Het "Goede Nieuws" (De Bovengrens):
Ze toonden aan dat als je getallen dicht genoeg kiest (boven $n^{-1/11}$ ), je gegarandeerd een monochromatisch product vindt, ongeacht hoe je ze schildert.

De Methode: In plaats van de hele verzameling te kleuren, zochten ze naar een piepklein, specifiek "valstrik"-patroon. Ze vonden een kleine collectie van 15 getallen die, als ze allemaal in je willekeurige verzameling voorkomen, niet gekleurd kunnen worden zonder een monochromatisch product te creëren. Het is als een wiskundige puzzel die geen oplossing heeft.
Het Resultaat: Ze bewezen dat als je waarschijnlijkheid $p$ hoog genoeg is, je willekeurige verzameling bijna zeker deze "valstrik"-patronen bevat. Zodra de valstrik aanwezig is, is een monochromatisch product onvermijdelijk.

Waarom Dit Belangrijk Is

Dit artikel is significant omdat het de bestaande kaders doorbreekt. Decennialang dachten wiskundigen dat de regels voor willekeurige verzamelingen met sommen en producten vergelijkbaar waren. Dit artikel laat zien dat ze fundamenteel verschillend zijn.

Sommen zijn regelmatig en voorspelbaar.
Producten zijn chaotisch en onregelmatig.

De instrumenten die wiskundigen gewoonlijk gebruiken om deze problemen op te lossen (die steunen op de regelmaat van sommen) faalden voor producten. De auteurs moesten nieuwe, creatievere manieren uitvinden om de mogelijkheden te tellen en hun "valstrikken" te bouwen.

De Multi-Color Twist

Het artikel keek ook naar wat er gebeurt als je 3, 4 of meer kleuren hebt.

Voor sommen verandert het aantal kleuren de drempelwaarde niet veel.
Voor producten verandert het aantal kleuren de drempelwaarde drastisch. Hoe meer kleuren je hebt, hoe moeilijker het is om een monochromatisch product af te dwingen, en de drempelwaarde verschuift aanzienlijk.

Samenvatting

Kortom, dit artikel vertelt ons dat als je willekeurig getallen uit een enorme lijst kiest, er een zeer specifieke "Goldilocks-zone" is voor de waarschijnlijkheid van het kiezen van deze getallen.

Als je er te weinig kiest, kun je de "productvalstrik" ontwijken door zorgvuldig te schilderen.
Als je er genoeg kiest, dwingt het universum een monochromatisch product tot stand te komen, ongeacht hoe je het probeert te vermijden.

De auteurs hebben deze zone nauw gedefinieerd binnen een specifiek bereik, waarmee ze aantonen dat de wereld van willekeurige vermenigvuldiging veel complexer en interessanter is dan de wereld van willekeurige optelling.

Technische Samenvatting: Monochromatische Producten in Willekeurige Gehele Getallenverzamelingen

Probleemstelling
Dit artikel onderzoekt de drempelwaarschijnlijkheid $p = p(n)$ waarbij de binomiale willekeurige deelverzameling $[n]_p$ (waarbij elk element van $\{1, \dots, n\}$ onafhankelijk met waarschijnlijkheid $p$ wordt opgenomen) bijna zeker (a.a.s.) de "product-Schur"-eigenschap bezit. Een verzameling $A$ wordt $r$ -product-Schur genoemd als elke $r$ -kleuring van $A$ een monochromatische oplossing oplevert voor de vergelijking $ab = c$ met $a, b, c \in A$ . Terwijl de drempels voor lineaire vergelijkingen (zoals de Schur-stelling voor $a+b=c$ ) goed begrepen zijn via de stelling van Rado en daaropvolgende transferprincipes, blijft het gedrag van niet-lineaire vergelijkingen zoals $ab=c$ in willekeurige verzamelingen grotendeels onverkend. De auteurs beogen de kritieke dichtheid $p^*$ te bepalen waar de willekeurige verzameling overgaat van bijna zeker niet product-Schur naar bijna zeker wel product-Schur.

Methodologie
Het artikel hanteert verschillende bewijsstrategieën voor de ondergrens (de $(0)$ -stelling) en de bovengrens (de $(1)$ -stelling), waarbij wordt opgemerkt dat standaardinstrumenten uit de willekeurige Ramsey-theorie onvoldoende zijn voor de niet-lineaire setting.

De $(0)$ -Stelling (Ondergrens):
Om aan te tonen dat $[n]_p$ niet product-Schur is voor een kleine $p$ , maken de auteurs gebruik van een greedy kleuralgoritme (hebzuchtig kleuralgoritme). Ze proberen de willekeurige verzameling te partitioneren in twee product-vrije verzamelingen (Rood en Blauw) door de elementen in oplopende volgorde te itereren. Een element krijgt een kleur toegewezen als het geen monochromatisch product vormt met eerder gekleurde elementen.
- Obstakelanalyse: Het algoritme faalt alleen als een specifieke "verboden configuratie" van gehele getallen aanwezig is binnen de willekeurige verzameling. Deze configuraties omvatten complexe multiplicatieve afhankelijkheden (bijv. $c = ab = def$, $a = xyz$, $b = uvw$).
- Telling-argument: De auteurs voeren een gedetailleerde casusanalyse uit van deze verboden configuraties, waarbij ze deze categoriseren op basis van het aantal verschillende elementen en herhalingen. Ze passen de union bound toe, waarbij ze gebruikmaken van divisor-bounds ( $D(n) = n^{o(1)}$ ) om aan te tonen dat voor $p \le n^{-1/9 - o(1)}$ de waarschijnlijkheid dat een dergelijke configuratie verschijnt $o(1)$ is.
De $(1)$ -Stelling (Bovengrens):
Om aan te tonen dat $[n]_p$ product-Schur is voor een grotere $p$ , construeren de auteurs een specifieke eindige product-Schur-patroon (een kleine verzameling gehele getallen die een monochromatische oplossing afdwingt, ongeacht de 2-kleuring).
- Patroonconstructie: Ze definiëren een verzameling $S_{a,b,c,d}$ bestaande uit 14 elementen gegenereerd door producten van vier basisgetallen. Ze bewijzen via casusanalyse dat elke 2-kleuring van deze verzameling een monochromatische oplossing voor $xy=z$ oplevert.
- Bestaanbewijs: Ze demonstreren dat als $p = \omega(n^{-1/11})$ , de willekeurige verzameling $[n]_p$ a.a.s. een kopie van dit patroon bevat. Dit wordt bereikt door de willekeurige verzameling in stadia te onthullen en aan te tonen dat de waarschijnlijkheid dat men de noodzakelijke basisgetallen ( $a, b, c, d$ ) en hun vereiste producten niet vindt, verwaarloosbaar is.
- Afwijking van Standaardmethoden: De auteurs merken expliciet op dat standaard transferprincipes en hypergraaf-container-methoden (die rusten op "supersaturatie"—de eigenschap dat dichte verzamelingen veel monochromatische oplossingen bevatten) hier falen. Voor producten bestaan er kleuringen waarbij slechts een verwaarloosbaar deel van de oplossingen monochromatisch is, waardoor supersaturatie-gebaseerde bewijzen ineffectief worden.
Extensie naar $r$ Kleuren:
Voor $r \ge 3$ generaliseren de auteurs de resultaten met behulp van Schur-getallen ( $S(r)$ ) en double-sum Schur-getallen ( $S'(r)$ ).
- Ondergrens: Ze construeren een kleuring gebaseerd op intervallen geschaald door $n^{1/S'(r)}$ , die monochromatische sommen en verschoven sommen vermijdt, wat vertaalt naar het vermijden van monochromatische producten.
- Bovengrens: Ze maken gebruik van de verzameling $U_x = \{x, x^2, \dots, x^{S(r)}\}$ , die niet $r$ -product-kleurbaar is door de definitie van $S(r)$ . Ze tonen aan dat voor $p = \omega(n^{-1/S(r)^2})$ , een dergelijke verzameling a.a.s. verschijnt.

Kernresultaten

Theorema 1.2 (Twee Kleuren): De drempel voor $[n]_p$ $[n]_{p}$ om product-Schur te zijn, ligt tussen $n^{-1/9 - o(1)}$ $n^{- 1/9 - o (1)}$ en $n^{-1/11}$ $n^{- 1/11}$ . Specifiek:
- Als $p \le n^{-1/9 - o(1)}$ , is $[n]_p$ a.a.s. niet product-Schur.
- Als $p \ge \omega(n^{-1/11})$ , is $[n]_p$ a.a.s. product-Schur.
Theorema 1.4 ( $r$ Kleuren): Voor $r \ge 2$ $r \geq 2$ voldoet de drempel $p^*_r$ $p_{r}^{*}$ aan:
- $p^*_r \le n^{-1/S'(r)}$ (Ondergrens op de drempel / Bovengrens op $p$ voor niet-bestaan).
- $p^*_r \ge n^{-1/S(r)^2}$ (Bovengrens op de drempel / Ondergrens op $p$ voor bestaan).
- Cruciaal is dat, in tegenstelling tot lineaire vergelijkingen waar de drempel onafhankelijk is van $r$ , de drempel voor producten afhangt van het aantal kleuren.

Betekenis en Claims
Het artikel claimt de eerste te zijn die de Ramsey-eigenschappen van willekeurige verzamelingen met betrekking tot niet-lineaire vergelijkingen, specif