Disproving the quasi-uniformity of the Halton sequences and of some Halton-type sequences

In dit artikel wordt bewezen dat de Halton-sequentie en bepaalde verwante sequenties, waaronder de Faure-sequentie, niet quasi-uniform zijn in dimensies $d \ge 2$.

De kern

De Halton-reeks: Een perfecte rij die toch scheef staat

Stel je voor dat je een groot, vierkant veld hebt (zoals een grasveld of een muur) en je wilt er honderden vlaggen in planten. Je wilt dat deze vlaggen zo gelijkmatig mogelijk verspreid zijn. Ze mogen niet te dicht bij elkaar staan (want dan is het rommelig), maar ze mogen ook niet te ver uit elkaar staan (want dan zijn er gaten waar niemand staat).

In de wiskunde noemen we zo'n perfecte verdeling een "quasi-uniforme" verdeling. Het is als een dans waarbij elke danser precies de juiste afstand tot zijn buren houdt, overal op het podium.

Dit artikel van Goda, Hofer en Suzuki gaat over een beroemde manier om vlaggen te planten, genaamd de Halton-reeks. Wiskundigen houden van deze reeks omdat hij heel goed werkt voor het berekenen van ingewikkelde integralen (een soort wiskundig "opmeten" van oppervlakken). Maar de auteurs van dit artikel hebben een verrassend geheim ontdekt: de Halton-reeks is niet zo perfect als we dachten.

Hier is wat ze hebben gevonden, vertaald in alledaags taal:

1. Het probleem: De "kruipende" buren

De Halton-reeks is een slimme truc om getallen te genereren. Als je ze in een 2D-ruimte (een vierkant) plakt, lijken ze eerst heel mooi verspreid. Maar als je heel precies kijkt, zie je dat er soms twee vlaggen zijn die ongelooflijk dicht bij elkaar staan, veel dichter dan zou mogen voor een perfecte verdeling.

De auteurs gebruiken twee maatstaven:

• De dekking: Hoe groot is het grootste gat waar geen vlag staat? (De Halton-reeks is hier goed in: er zijn geen grote gaten).
• De scheiding: Hoe klein is de kleinste afstand tussen twee vlaggen? (Hier zit het probleem).

Bij een perfecte verdeling zou de kleinste afstand tussen twee vlaggen moeten afnemen op een voorspelbare manier naarmate je meer vlaggen plant. Maar bij de Halton-reeks blijken sommige vlaggen veel te snel naar elkaar toe te bewegen. Ze "kruipen" te dicht op elkaar.

2. De analogie: De dansvloer

Stel je een dansvloer voor waar mensen (de punten) binnenkomen.

• Een quasi-uniforme dansvloer is zoals een goed georganiseerd concert: iedereen heeft evenveel ruimte, en niemand staat op elkaars tenen.
• De Halton-reeks lijkt ook goed georganiseerd, maar de auteurs hebben ontdekt dat er op bepaalde momenten twee mensen zijn die plotseling tegen elkaar aan staan, alsof ze een geheime danspartner zijn.

In de wiskundige taal van het artikel zeggen ze: de separatiestraal (de kleinste afstand) wordt te klein, te snel. Dit betekent dat de verdeling niet "quasi-uniform" is. Het is alsof je een perfecte muur hebt gebouwd, maar op een paar plekken zijn de stenen zo dicht op elkaar geschoven dat de muur daar instabiel wordt.

3. Wat hebben ze bewezen?

De auteurs hebben wiskundig bewezen dat dit probleem altijd optreedt, zolang je in 2 of meer dimensies werkt (dus niet op een lijn, maar in een vlak of een ruimte).

• Ze hebben getoond dat er oneindig veel momenten zijn waarop twee punten in de Halton-reeks zo dicht bij elkaar staan dat de verdeling faalt als "perfect verspreid".
• Ze hebben ook gekeken naar andere soorten reeksen die op de Halton-reeks lijken (zoals de Faure-reeks en Sobol'-reeks). Ook deze blijken niet perfect te zijn. Ze hebben zelfs een nieuwe manier gevonden om dit te bewijzen voor de Faure-reeks, door te kijken naar polynomen (wiskundige uitdrukkingen) in plaats van alleen getallen.

4. Waarom maakt dit uit?

Je zou denken: "Maar de Halton-reeks werkt toch goed voor het berekenen van integralen?"
Ja, voor dat doel is hij nog steeds geweldig. Maar er is een ander gebied, namelijk het interpoleren van data (het voorspellen van waarden tussen bekende punten, zoals bij het modelleren van weerpatronen of het maken van 3D-modellen).

Voor die toepassingen is het cruciaal dat punten niet te dicht bij elkaar staan. Als ze te dicht bij elkaar staan, wordt de berekening onstabiel en kunnen kleine fouten enorme problemen veroorzaken.
Het artikel zegt dus eigenlijk: "Voor het berekenen van integralen is de Halton-reeks prima, maar als je punten nodig hebt voor 3D-modellen of data-interpolatie, moet je oppassen. De Halton-reeks heeft namelijk 'blinde vlekken' waar de punten te krap zitten."

Samenvatting in één zin

De auteurs hebben bewezen dat de beroemde Halton-reeks, die al decennia wordt gebruikt om dingen gelijkmatig te verdelen, eigenlijk niet zo gelijkmatig is als we hoopten: op bepaalde momenten staan de punten veel te dicht op elkaar, waardoor ze niet geschikt zijn voor toepassingen die een perfecte afstand tussen punten vereisen.

Het is een beetje zoals het ontdekken dat een auto die al 50 jaar als "de veiligste ter wereld" wordt geroemd, eigenlijk een klein, maar gevaarlijk ontwerpfoutje heeft bij het remmen op regenachtige dagen. Hij rijdt nog steeds goed, maar hij is niet perfect.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Disproving the Quasi-Uniformity of the Halton Sequences and of Some Halton-Type Sequences" in het Nederlands.

Titel: Het weerleggen van de quasi-uniformiteit van de Halton-sequenties en enkele Halton-achtige sequenties

Auteurs: Takashi Goda, Roswitha Hofer, en Kosuke Suzuki.

---

1. Probleemstelling en Context

De Halton-sequentie is een van de meest bekende lage-discrepantie-sequenties die worden gebruikt in numerieke integratie (Quasi-Monte Carlo methoden) en voor steekproefnemen in verspreide data-benadering (bijvoorbeeld bij radiale basisfuncties).

Hoewel het bekend is dat de Halton-sequentie een optimale dekkingradius (covering radius, $h(P_N)$) heeft die schaalt als $O(N^{-1/d})$, is de quasi-uniformiteit van deze sequentie onzeker gebleven. Een puntenset $P_N$ wordt quasi-uniform genoemd als de verhouding tussen de dekkingradius en de scheidingsradius (separation radius, $q(P_N)$) begrensd is door een constante $C$, onafhankelijk van $N$.
$$\frac{h(P_N)}{q(P_N)} \leq C$$
Omdat $h(P_N)$ al optimaal schaalt ($N^{-1/d}$), hangt quasi-uniformiteit volledig af van de scheidingsradius. Als $q(P_N)$ sneller daalt dan $N^{-1/d}$, is de sequentie niet quasi-uniform.

Het centrale probleem: Is de Halton-sequentie in dimensie $d \geq 2$ quasi-uniform? Numerieke experimenten suggererden dat de scheidingsradius sneller daalt dan $N^{-1/d}$, maar een theoretisch bewijs ontbrak in de literatuur.

2. Methodologie

De auteurs gebruiken een analytische benadering gebaseerd op de eigenschappen van de radicaal-inversie-functie ($\phi_b$) en de structuur van de getallen in verschillende bases.

• Analyse van de scheidingsradius: Het doel is om te bewijzen dat er oneindig veel paren punten $(x_n, x_m)$ in de Halton-sequentie bestaan die dichter bij elkaar liggen dan de optimale schaal $N^{-1/d}$.
• Constructie van specifieke indices: De auteurs construeren specifieke indices $n$ en $m$ (afhankelijk van parameters $k, \ell$ en de Euler-totientfunctie $\phi(b_1)$) waarbij de getallen $n$ en $m$ in hun basis-uitbreidingen overeenkomsten vertonen die leiden tot zeer kleine verschillen in de radicaal-inversiewaarden.
• Wiskundige hulpmiddelen:
  • Lemma 1: Een inductiebewijs dat toont dat als $p \equiv 1 \pmod q$, dan is $pq^k - 1$ deelbaar door $q^{k+1}$. Dit wordt gebruikt om de delingseigenschappen in de basis-uitbreidingen te analyseren.
  • Propositie 1 & 2: Deze stellen de bovengrenzen vast voor de verschillen $|\phi_{b_j}(n) - \phi_{b_j}(m)|$. De auteurs balanceren deze verschillen over alle dimensies zodat ze allemaal klein zijn, maar niet te klein voor de eerste dimensie, wat resulteert in een totale afstand die kleiner is dan $N^{-1/d}$.
  • Dirichlet's simultane benaderingstheorema: Gebruikt in Propositie 2 om de exponenten in de constructie van $n$ en $m$ zo te kiezen dat de afstanden in alle dimensies evenredig klein zijn.

Voor Halton-achtige sequenties (zoals de Faure-sequentie) gebruiken de auteurs een polynoom-analogie. In plaats van gehele getallen in een basis $b$, werken ze met polynomen over een eindig veld $\mathbb{F}_p$. Ze definiëren een radicaal-inversie-functie voor polynomen en gebruiken eigenschappen van Pascal-matrices en Lucas' stelling (in polynoomvorm) om dichte paren te construeren.

3. Belangrijkste Bijdragen en Resultaten

Hoofdstuk 2: Halton-sequenties

• Hoofdstelling (Theorema 1): Voor elke dimensie $d \geq 2$ en elke paarwijze onderling ondeelbare bases $b_1, \dots, b_d$, is de Halton-sequentie niet quasi-uniform.
• Kwantificering: De auteurs bewijzen dat er een constante $c > 0$ bestaat zodat voor oneindig veel $N$:
  $$q(P_N) \leq \frac{c}{N^{1/d} (\log N)^{1/(d(d-1))}}$$
  Omdat de scheidingsradius sneller daalt dan $N^{-1/d}$ (vanwege de logaritmische factor in de noemer), is de verhouding $h(P_N)/q(P_N)$ onbegrensd.
• Conclusie: De Halton-sequentie faalt in het behouden van een minimale scheidingsafstand in hogere dimensies, wat een theoretische beperking is voor toepassingen die afhankelijk zijn van de geometrische spreiding van punten (zoals RBF-interpolatie).

Hoofdstuk 3: Halton-achtige sequenties

De auteurs breiden hun resultaten uit naar sequenties gedefinieerd over polynomen (Hofer's definitie), waaronder de Faure-sequentie.

• Theorema 2: Ze bewijzen dat specifieke Halton-achtige sequenties ook niet quasi-uniform zijn, waaronder:
  1. Tweedimensionale projecties van de Faure-sequentie.
  2. De 3-dimensionale Sobol'-sequentie (geassocieerd met specifieke polynomen over $\mathbb{F}_2$).
  3. De $p$-dimensionale Faure-sequentie in basis $p$.
• Resultaat: Voor deze gevallen geldt een nog sterkere afname van de scheidingsradius:
  $$q(P_N) \leq \frac{c}{N^{1/(d-1)}}$$
  Dit is aanzienlijk sneller dan de optimale $N^{-1/d}$, wat de niet-quasi-uniformiteit bevestigt.
• Nieuwe Bewijsvoering: Voor de Faure-sequentie bieden ze een alternatief bewijs ten opzichte van eerdere werken (Dick et al.), gebaseerd op de structuur van de Halton-achtige constructie in plaats van alleen matrixeigenschappen.

4. Significatie en Implicaties

1. Theoretische Correctie: Dit artikel sluit een theoretische lacune door formeel te bewijzen dat de Halton-sequentie, ondanks zijn uitstekende discrepantie-eigenschappen, niet quasi-uniform is voor $d \geq 2$. Dit weerlegt de veronderstelling dat lage discrepantie automatisch quasi-uniformiteit impliceert.
2. Impact op Numerieke Methoden: Voor toepassingen zoals scattered data approximation (bijv. met Radiale Basis Functies) is de scheidingsradius cruciaal voor de stabiliteit en de foutgrenzen. De bevindingen waarschuwen dat Halton-sequenties in hogere dimensies mogelijk niet de beste keuze zijn voor deze specifieke toepassingen, omdat punten te dicht bij elkaar kunnen komen, wat leidt tot slechte conditionering van interpolatiematrices.
3. Verwante Sequenties: Het resultaat generaliseert naar andere populaire sequenties zoals de Faure- en Sobol'-sequenties, wat suggereert dat quasi-uniformiteit een zeldzame eigenschap is voor veel standaard lage-discrepantie-construkties in dimensies $d \geq 2$.
4. Open Vraag: Het artikel laat een open probleem over: of alle Halton-achtige sequenties voor $d \geq 2$ niet quasi-uniform zijn, en of er een algemene formule bestaat voor de indices die de dichte paren genereren.

Samenvattend: De auteurs leveren een rigoureus wiskundig bewijs dat de Halton-sequentie en verwante constructies falen in het behouden van een optimale scheidingsafstand in hogere dimensies, wat hun bruikbaarheid voor bepaalde geometrische toepassingen beperkt, ondanks hun superioriteit in numerieke integratie.