Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erd\H{o}s Problem #272)

Technische Samenvatting: Exacte Waarden en Exacte Bovengrenzen voor Families van Hele Getallen met Arithmetische Progressie-intersecties

Probleemstelling
Het artikel behandelt Erdős Probleem #272, dat streeft naar het bepalen van de functie $t(N)$, gedefinieerd als het maximum aantal verschillende deelverzamelingen $A_1, \dots, A_t \subseteq \{1, \dots, N\}$ waarvoor de intersectie van elke twee verschillende verzamelingen $A_i \cap A_j$ een niet-lege arithmetische progressie (AP) is.

Historisch gezien hebben Simonovits en Sós vastgesteld dat $t(N) = O(N^2)$ en vermoedden zij dat het maximum wordt bereikt door de familie van alle deelverzamelingen van grootte maximaal 3 die een vast element bevatten, wat een grens oplevert van $\binom{N}{2} + 1$. Szabó weerlegde later deze exacte conjectuur door een familie te construeren die $t(N) \ge \binom{N}{2} + 1 + \lfloor (N-1)/4 \rfloor$ bereikt. Szabó stelde verder de asymptotische gedraging $t(N) = N^2/2 + O(N^{5/3}(\log N)^3)$ vast en stelde twee cruciale vragen: (i) of $t(N) = \binom{N}{2} + O(N)$, en (ii) de "kernel vraag", die vraagt of elke extreme familie (één die de maximale grootte bereikt) een gemeenschappelijk element moet bevatten dat door al zijn verzamelingen wordt gedeeld.

Methodologie
De auteurs hanteren een hybride benadering die exhaustieve computationele verificatie, structurele combinatoriek en analytische begrenzingstechnieken combineert:

1. Exacte Berekening: Voor kleine $N$ ($N \le 12$) wordt het probleem gemodelleerd als het vinden van de maximale clique in een graaf waarbij de knopen niet-lege deelverzamelingen van $[N]$ zijn en de zijden verbindingen vormen tussen verzamelingen met niet-lege AP-intersecties.
   • Voor $N \le 10$ werd een bit-parallel branch-and-bound solver met greedy coloring bounds gebruikt.
   • Voor $N=11$ en $12$ werd een beslissingszoektocht gebruikt met root decompositie, degeneracy ordering, core peeling en een rigoureuze "star pruning" stap om het niet-bestaan van grotere families te bewijzen.
2. Structurele Decompositie: Het bewijs voor de algemene bovengrens berust op de decompositie van een "gestarred" familie (één met een gemeenschappelijk element $m$) in deelverzamelingen van grootte $\le 2$, grootte $3$, en grootte $\ge 4$.
3. Defect-één Telling Ongelijkheid: Een centraal technisch instrument is een telling ongelijkheid voor "trappenregio's" (families van integer intervallen die 0 bevatten). De auteurs bewijzen dat voor elke dergelijke familie het aantal leden begrensd wordt door het aantal "slechte paren" (paren $\{u,v\}$ waarvoor $\{0,u,v\}$ geen AP is) die zij dekken, plus een kleine defect term. Dit wordt geverifieerd via een exacte dynamische programmering voor parameters tot 500 en een asymptotisch argument met behulp van positief-definiete kwadratische vormen voor grotere parameters.
4. Private-Pair Stelling: Een structurele stelling wordt gevestigd die aantoont dat elk "krom" lid (een verzameling van grootte $\ge 4$ die geen AP is) in een goed-intersecterende familie een "private bad pair" bevat—een paar elementen dat niet in enig ander lid van de familie wordt bevat. Dit voorkomt het delen van "kills" (slechte paren) tussen niet-AP leden, wat een nauwe telling mogelijk maakt.

Belangrijkste Bijdragen en Resultaten

• Exacte Waarden voor Kleine $N$: Het artikel bepaalt $t(N)$ exact voor $N = 3, \dots, 12$. De waarden zijn $4, 7, 12, 17, 23, 30, 39, 48, 58, 69$. In dit gehele bereik is de ondergrens van Szabó exact. De sequentie komt momenteel niet voor in de OEIS.
• Aangescherpte Conjectuur: Op basis van het computationele bewijs vermoeden de auteurs dat voor alle $N \ge 1$:
  $$t(N) = \binom{N}{2} + 1 + \left\lfloor \frac{N-1}{4} \right\rfloor$$
  Dit verfijnt de asymptotische vraag van Szabó naar een exacte formule.
• Exacte Bovengrens voor Gestarred Families: Het belangrijkste theoretische resultaat (Theorema 1.4) bewijst dat voor elke gestarred familie (waar alle verzamelingen een gemeenschappelijk element delen), de grootte begrensd wordt door de ondergrens van Szabó. Dit is de eerste exacte bovengrens van dit type die bekend is voor enige $N \ge 5$.
  • Het bewijs combineert de "defect-één" telling ongelijkheid met de "private-pair stelling" om niet-AP leden te behandelen.
• Reductie naar de Kernel Vraag: De auteurs tonen aan dat de aangescherpte conjectuur (dat de formule voor alle $N$ geldt) onmiddellijk volgt indien de kernel-conjectuur van Szabó waar is (d.w.z. als elke extreme familie gestarred is). Hiermee wordt het probleem van het exact bepalen van $t(N)$ gereduceerd tot het bewijzen dat extreme families een gemeenschappelijk element hebben.
• Structurele Beperkingen op Tegenvoorbeelden: Het artikel analyseert de hypothetische structuur van een niet-gestarred extreme familie (een tegenvoorbeeld voor de kernel-conjectuur). Het bewijst dat als een dergelijke familie bestaat, de triples een gemeenschappelijk element moeten delen, en dat leden die dit element vermijden lange arithmetische progressies met kleine verschillen moeten zijn. De auteurs beargumenteren dat dergelijke configuraties "zelf-limiterend" zijn en onwaarschijnlijk de geconjectureerde grens bereiken, hoewel een volledig bewijs open blijft.

Betekenis
Het artikel beweert de eerste exacte bepaling van $t(N)$ voor enige $N \ge 5$ (specifiek $N \le 12$) te bieden en stelt de eerste exacte bovengrens vast voor de beperkte klasse van gestarred families. Door te bewijzen dat de ondergrens exact is voor alle gestarred families, isoleert het werk de "kernel eigenschap" als het enige resterende obstakel om Erdős Probleem #272 volledig op te lossen. De auteurs merken op dat hun resultaten bevestigen dat de constructie van Szabó optimaal is binnen de klasse van families die een gemeenschappelijk element delen, en zij bieden de eerste rigoureuze structurele beperkingen op wat een potentiële niet-gestarred tegenvoorbeeld zou kunnen zijn. Het werk introduceert ook nieuwe combinatorische technieken, specifiek de defect-één telling ongelijkheid en de private-pair stelling, die toepasbaar kunnen zijn op andere intersectieproblemen.