Non-Simple T-Prescriptions Yield T-Complexity Gains Infinitely Often

Technische Samenvatting: Niet-simpele T-prescripties Leveren Oneindig Vaak T-complexiteitswinsten Op

Probleemstelling
Het artikel behandelt een specifieke vraag met betrekking tot T-complexiteit, een deterministische complexiteitsmaatstaf voor eindige woorden gebaseerd op de recursieve constructie van T-codes. T-complexiteit wordt gedefinieerd via T-prescripties, wat sequenties zijn van T-augmentatiestappen. Elke stap selecteert een "kopieerpatroon" (een huidig codewoord) en een "kopieerfactor" $k \ge 1$. De T-complexiteit van een prescriptie $P$ is de som van $\log_2(k_i + 1)$ voor alle stappen.

Een prescriptie is simpel als alle kopieerfactoren 1 zijn; anders is zij niet-simpel. Titchener et al. [5] hebben eerder aangetoond dat er eindige voorbeelden bestaan waarbij niet-simpele prescripties een hogere T-complexiteit bereiken dan enige simpele prescriptie voor een gegeven maximale codewoordlengte. Zij vroegen expliciet of dit fenomeen oneindig vaak voorkomt voor elke vaste alfabetgrootte van minstens twee. Specifiek vraagt het probleem of er oneindig veel lengtes $N$ zijn waar de onbeperkte exacte-lengte maximale T-complexiteit, $C_T(N)$, strikt groter is dan de simpele exacte-lengte maximale, $C_T^{(1)}(N)$.

Methodologie
De auteur hanteert een elementaire bewijsstrategie gebaseerd op de structurele eigenschappen van T-augmentatie en de beperkingen opgelegd door de "geen recycling"-regel van kopieerpatronen. De methodologie verloopt als volgt:

1. Definities en Grenzen: Het artikel definieert $L_m$ als de minimale mogelijke maximale codewoordlengte die bereikt kan worden door een simpele prescriptie met exact $m$ stappen (ariteit $m$). Het definieert de increment $d_m = L_m - L_{m-1}$, wat de minimale lengtekosten vertegenwoordigt voor het toevoegen van de $m$-de stap aan een simpele prescriptie.
2. Analyse van Increments: Gebruikmakend van het feit dat een geldige T-prescriptie geen kopieerpatroon mag hergebruiken (Lemma 3), stelt de auteur vast dat een simpele prescriptie van ariteit $m$ $m$ verschillende niet-lege woorden moet gebruiken. Door de dichtheid van woorden over een eindig alfabet te analyseren, bewijst het artikel dat de gemiddelde lengte van deze verschillende woorden onbegrensd moet groeien naarmate $m$ toeneemt. Bijgevolg is de sequentie van increments $d_m$ onbegrensd.
3. Bestaan van Sprongen: De onbegrensdheid van $d_m$ impliceert dat er oneindig veel indices $m$ zijn waar de increment strikt toeneemt, oftewel $d_{m+1} > d_m$.
4. Constructie van Tegenvoorbeelden: Bij elke dergelijke index $m$ waar $d_{m+1} > d_m$, construeert de auteur een specifieke niet-simpele prescriptie $\hat{P}_m$. Dit gebeurt door een minimale simpele prescriptie $P_m$ van ariteit $m$ te nemen en de kopieerfactor van de laatste stap te veranderen van 1 naar 2.
   • De nieuwe maximale lengte $N_m$ van $\hat{P}_m$ is $L_m + |p_m|$, waarbij $|p_m|$ de lengte van het laatste patroon is.
   • Omdat $|p_m| \le d_m$ en $d_{m+1} > d_m$, voldoet de nieuwe lengte $N_m$ aan $N_m < L_{m+1}$.
   • Dit garandeert dat geen enkele simpele prescriptie met ariteit $m+1$ of groter een maximale lengte van $N_m$ of minder kan bereiken. Hierdoor heeft de beste simpele prescriptie voor lengte $N_m$ hoogstens $m$ stappen, wat een complexiteit oplevert van maximaal $m$.
   • De geconstrueerde niet-simpele prescriptie $\hat{P}_m$ heeft een complexiteit van $(m-1) + \log_2 3$, wat strikt groter is dan $m$.

Belangrijkste Bijdragen en Resultaten

• Bevestigend Antwoord: Het artikel bewijst dat voor elke alfabetgrootte $r \ge 2$, er oneindig veel maximale codewoordlengtes $N$ bestaan waarvoor $C_T(N) > C_T^{(1)}(N)$.
• Sterkere Bovenste Envelope Statement: Het resultaat wordt bewezen tegen de simpele bovenste envelope $C_T^{(1), \le}(N)$ (de maximale complexiteit van elke simpele prescriptie met lengte $\le N$), wat de strikte ongelijkheid voor het exacte-lengtegeval impliceert.
• Identificatie van het Mechanisme: Het artikel identificeert het mechanisme dat deze winsten aandrijft: de "geen recycling"-beperking dwingt simpele prescripties om steeds langere, verschillende woorden te gebruiken, wat leidt tot strikte opwaartse sprongen in de minimale lengtedrempels. Niet-simpele prescripties exploiteren deze gaten door de kopieerfactor van de laatste stap te verhogen, waardoor ze een complexiteitsboost van $\log_2 3 - 1$ verkrijgen zonder de volgende simpele drempel te overschrijden.
• Elementair Karakter: Het bewijs wordt beschreven als elementair, waarbij gebruik wordt gemaakt van telargumenten en de recursieve definitie van T-codes in plaats van complexe asymptotische analyse.

Betekenis en Beperkingen
Het artikel claimt relevantie door een definitief, elementair antwoord te bieden op een vraag over eindige lengtes die door Titchener et al. [5] open werd gelaten. Het demonstreert dat het voordeel van niet-simpele prescripties geen geïsoleerd fenomeen van korte lengtes is, maar oneindig vaak voorkomt.

De auteur merkt expliciet de bescheidenheid van het resultaat op met betrekking tot computationele efficiëntie en structuur:

• Het bewijs vertrouwt op een brute-force exhaustieve enumeratie om de sprongindices te identificeren; er wordt geen gesloten vorm van een sequentie van deze lengtes of een efficiënt algoritme verstrekt om de locaties te bepalen.
• De geconstrueerde niet-simpele prescripties zijn geldige getuigen van de ongelijkheid, maar er wordt niet beweerd dat zij de onbeperkte maximizers voor die lengtes zijn (hoewel de strikte ongelijkheid standhoudt omdat de onbeperkte maximum de alle geldige prescripties domineert).
• Het artikel behandelt niet de dichtheid van deze uitzonderlijke lengtes, de omvang van de grootste mogelijke winst, of de asymptotische distributie-eigenschappen, maar richt zich strikt op het bestaan van oneindig veel van dergelijke instanties.