Die Vorzeichenachse

Der Auftrag gibt eine nach Grad geordnete Leiter vor: Vierkreis, Sechskreis, allgemeiner Kreis der Länge 2ℓ. Dem Anschein nach ist sie unendlich. Sie ist es nicht.

Drei Folgen, und jede erspart eine Messung:

• λ_min(A) = −3, exakt, für jede Instanz. S hat höchstens Rang n, bei m > n ist S·Sᵀ singulär. Der kleinste Eigenwert der Klauselmatrix ist keine Messgrösse, sondern eine Identität — beim Bau des Instruments gemessen, bevor er hergeleitet war.
• Das ganze Spektrum sitzt in der n×n-Matrix M. Ihre Diagonale ist die Gradfolge, alles Vorzeichenhafte sitzt daneben. Unter der Eichung geht M ↦ D·M·D — das Spektrum ist invariant, der einzelne Eintrag nicht.
• Die Stufe 4 der Leiter hat n Freiheitsgrade, nicht unendlich viele. Für jedes ℓ ist tr(A^ℓ) eine Funktion der n Eigenwerte von M. Das Frustrationsprofil über alle Kreislängen ist damit in einem Durchgang ausrechenbar.

Und der Punkt, auf den der Auftrag selbst zeigt: die Unwucht Σ_v(pos−neg)² ist die quadratische Form von A am festen Vektor 𝟙 — jedes Klauselpaar mit Gewicht eins.

Der Auftrag sagt: „Das Versagen der Unwucht widerlegt nicht den Grad 2. Es widerlegt die gleichmässige Gewichtung. Gesucht ist nicht eine neue Grösse, sondern das richtige Gewicht." Das richtige Gewicht ist μ_max(M) — und es ist gemessen. Siehe Abschnitt 05.

Nachgerechnet, zweifach. Die Voraussetzung ist bei α = 4,267 in allen geprüften Fällen erfüllt — n = 50, 100, 150, 200, je fünf Gerüste, keine einzige Variable mit mehr als einer Komponente. Und die Rekonstruktion ist explizit durchgeführt, aus A und H allein, und stimmt bei n = 60, 120 und 200 bis auf Eichung mit dem Original überein.

Gemessen wird bei festem Gerüst über viele Signaturen. Damit ist Σ_v grad(v)² konstant, ebenso paare2 und jede andere Gerüstgrösse: die Zentrierung innerhalb der Gerüste erledigt das Herausregressieren der Gradstreuung exakt statt näherungsweise. SAT und UNSAT werden nie zusammengeworfen.

Die dritte Probe ist zugleich der Rauschboden: dieselbe Formel unter Umbenennung ist nach der Eichsymmetrie dieselbe Aufgabe, was der Solver an Konflikten trotzdem anders zählt, ist sein Eigenrauschen. Es ist auf den beiden Seiten der Schwelle völlig verschieden — und das entscheidet, was überhaupt erklärbar ist.

Ein Nullbefund ohne funktionierende positive Kontrolle ist kein Befund. Drei Familien, aufsteigend nach Schärfe.

Jede gemessene Invariante ist zwischen SAT und UNSAT identisch — je Graph gepaart, Δ = 0,000 bei allen zehn und an beiden Grössen. Die Härte unterscheidet sich um elf Bit. Das Instrument ist deshalb nicht blind: die dritte Zeile zeigt, dass es auf demselben Gerüst zwischen Tseitin und einer fairen Signatur massiv unterscheidet. Es ist der Gegenstand, der so gebaut ist.

Damit ist tr(A^ℓ) für Tseitin durch n, m und den Grad allein festgelegt. Nachgerechnet und gemessen, beide Male: tr(A³) = 45·125 − 75·27 = 3 600 bei n = 45 und 4 800 bei n = 60. Das gesamte Kreisprofil ist dort entartet. Auch frust1, die einzige gemessene Grösse ohne Kreisträger, ist blind: in jeder Paritätsklasse haben genau zwei der vier Masken das Bit e gesetzt, also sind von den 16 Paaren je Kante immer genau 8 uneinig — frust1 = paare1/2, exakt, gemessen 480 von 960 und 360 von 720.

Zwei Saatbereiche zu je 40 Gerüsten mit 60 Signaturen, 4 800 Hauptzeilen und 640 Eichzeilen. Kein Lauf ins Konfliktbudget. Alles zentriert innerhalb der Gerüste, unerfüllbare Instanzen, Standardfehler von r unter der Nullhypothese je 0,029.

frust4 ist ein Treffer. Acht und 6,6 Standardabweichungen an zwei unabhängigen Saatbereichen, und mit dem vorhergesagten Vorzeichen: mehr frustrierte Vierkreise heisst mehr Resolventen der Breite 3 heisst leichter. Es ist die erste strukturelle Vorzeichengrösse dieses Projekts, die überhaupt etwas tut — und es ist nicht die Unwucht:

Die Stufen 3 und 4 tragen nichts Eigenes: tr(M²) korreliert mit frust4 zu −0,997 (das ist Satz V3, exakt), tr(M³) zu −0,976, tr(M⁶) noch zu −0,817. Sie sind frust4 in längeren Kreisen wiedergesehen, mit abnehmender Güte. Und μ_max(M) — das richtige Gewicht — trägt nichts. Das ist die schärfste Einzelaussage dieses Abschnitts, denn μ_max ist nach V2 genau die Grösse, nach der der Auftrag sucht.

Zu jeder Signatur die nächstgelegene Signatur desselben Gerüsts im zwölfdimensionalen Invariantenraum, mittlerer Abstand 2,2 σ. Wenn die Invarianten die Härte fassen, müssen solche Paare nahe beieinander liegen.

Der einzige Punkt des Auftrags, an dem eine kausale Kette vorliegt statt einer Korrelation. frust4 ist nicht ein Korrelat der Breite-3-Funken, sondern ihre exakte Anzahl: zwei Klauseln mit genau zwei gemeinsamen Variablen haben genau dann eine Resolvente der Breite 3, wenn sie sich über genau eine der beiden einig sind. Also — sagt frust4 vorher, ob der Abschluss der Breite 3 zündet?

Und keine andere Grösse tut es. Bei n = 53, innerhalb der Gerüste, gegen zündet: frust4 +0,308 — die Unwucht, die Grösse mit dem stärksten Zug auf die CDCL-Härte bei n = 200, liegt bei +0,006 bei N = 1 183. frust6 −0,020, frust1 +0,007, unwucht4 +0,013. Die beiden Richtungen der Vorzeichenachse gehören zu zwei verschiedenen Mechanismen.

Nebenbefund, ungeplant: p₃(53) = 0,527. Der Vorgängerbefund setzt den Übergang mit einer ganz anderen Messreihe auf n₅₀ = 52,9. Das Instrument reproduziert die Konstante, ohne dass sie irgendwo eingebaut wäre.

Der schärfste Einwand gegen jede Härtegrösse: sie verschiebt bloss α_c, und dann sitzt die Instanz tiefer in der unerfüllbaren Phase — und tief drin ist leicht zu widerlegen. Damit frust4 diese Prüfung bestehen kann, muss es als Stellschraube verfügbar sein. Es ist keine, also wird verworfen und neu gezogen, bis frust4 in einem vorgegebenen z-Fenster liegt. Das ist eine Bedingung, keine Impfung: frust4 ist eichinvariant, eine Bedingung darauf kann gar keine Belegung bevorzugen — anders als die Unwucht, die sich nur durch teilweises Planting erzeugen lässt.

Die Schwelle wandert wirklich, um −0,127 über einen Hebel von 6,5 Standardabweichungen — rund ein Drittel der Wucht der Gradstreuung, die um 0,347 verschiebt. Also wird jede Gruppe bei ihrem eigenen α_c plus festem Abstand neu gemessen, je 120 Instanzen. Die UNSAT-Anteile stimmen paarweise überein: die Gruppen sitzen wirklich an derselben Stelle des Phasendiagramms.

Der Scan liefert beide Gruppen auch bei gleichem α, nicht nur bei gleichem Schwellenabstand. Die Differenz der beiden Vergleiche ist genau das, was die Schwellenverschiebung einbringt — ohne Extrapolation, ohne Steigungsschätzung, ohne Modell.

Die Leiter des Auftrags ordnet Kreise. Das ist nicht der ganze Raum, den die Eichbedingung zulässt: sie verlangt geraden Grad nur an den Variablenknoten. Hat ein Träger auch an jedem Klauselknoten geraden Grad, ist er ein Kreis — sonst hat er eine gerade Zahl ungerader Klauselknoten, und der Fall zwei ist ein Weg im Inzidenzgraphen.

Genau die zählt A^k: (A^k)[c][c′] summiert die Wege der Länge k mit Grad 2 an jeder Zwischenklausel und Grad 1 an den Enden. Das kanonische Aggregat ist deshalb pfad(k) = 𝟙ᵀ·A^k·𝟙.

Das ist G4 in neuer Schreibweise, und es ordnet die Unwucht endgültig ein: sie ist der Anfang des Wegzweigs, kein Sonderfall. An den Daten geprüft: max |pfad(1) − (unwucht − 3m)| = 0 über alle 4 800 Instanzen.

Die längeren Wege sind die Unwucht in gestreckter Form — r zu ihr fällt von +0,893 bei k = 2 auf +0,559 bei k = 6, die Korrelation zur Härte bleicht mit. Ausserhalb der Stichprobe bringen alle fünf zusammen +0,0002 und +0,0078 über unwucht + frust4 hinaus. Damit sind beide Zweige der Klassifikation gemessen, gleich tief, und beide auf der UNSAT-Seite leer.

Die Gegenprobe ist hier schwieriger als bei frust4, weil r(unwucht, Varianz) = +0,898: ein Verwerfungsziehen auf die Varianz allein zöge das Mittel mit, und das ist nachweislich reine Schwelle. Der Hebel muss die Varianz bei festgehaltener Unwucht bewegen — je Gerüst eine Eichstichprobe von 4 000 Signaturen, darin die Regression pfad(2) ~ unwucht, dann verwerfen auf den Rest. Erreicht: 3,65 σ Varianzhebel bei 0,19 σ Unterschied in der Unwucht.

Erstens: ja, und zwar stark — fast so stark wie die Unwucht selbst, neunmal stärker als frust4, und mit umgekehrtem Vorzeichen zur Unwucht, mit der sie zu +0,90 korreliert.

Zweitens: aber nicht nur. Jede Gruppe bei ihrem eigenen α_c, je 250 Instanzen, beide Seiten der Schwelle:

Auf der UNSAT-Seite heben sich die beiden fast genau auf, auf der SAT-Seite addieren sie sich. Die Varianz ist keine SAT-Grösse — der UNSAT-Nullbefund war eine Auslöschung, kein Fehlen.

Ein Dichte-Artefakt ist ausgeschlossen: die Gruppen sitzen bei absoluten α, die um 0,29 auseinanderliegen. Ein reiner Dichteeffekt wirkte auf den beiden Seiten entgegengesetzt — mehr Klauseln machen UNSAT leichter und SAT schwerer. Gemessen ist die tiefe Gruppe auf beiden Seiten leichter. Was offen bleibt: die logistischen Steigungen der Gruppen unterscheiden sich um 7 %, „gleicher Abstand in α" ist also nicht ganz derselbe Abstand in Einheiten der Übergangsbreite. Der Vorzeichentest hängt daran nicht.

Null ungerade Klauselknoten sind die Kreise, zwei die Wege. Vier ist etwas Drittes, und die Form folgt aus der Eichbedingung: weil jede Variable geraden Grad braucht, kann ein Blatt des Trägers nur ein Klauselknoten sein — vier ungerade heisst also ein Klauselknoten mit drei oder vier Ästen.

Die ersten beiden sind Identitäten und laufen als Probe mit — an allen 4 800 Instanzen mit max |Δ| = 0. Ab k = 3 ist es neu, und nicht bloss formal: Σ_c x_c³ ist nicht 𝟙ᵀA³𝟙 (an einem Beispiel −2 074 gegen 17 360). Der Stern verzweigt an einer Klausel, der Weg läuft durch sie hindurch.

Die rohen Momente sind die Wege in anderer Schreibweise — für eine glockenförmige Verteilung ist m₃ ≈ 3μσ² + μ³, und gemessen ist r(Σx⁴, Varianz) = +0,95. Das Neue steckt in der Form, also in den standardisierten Momenten.

Die Gegenproben haben je einen eigenen Messaufbau gekostet. Es geht billiger: wer α_c verschiebt, muss bei festem Gerüst und festem α die Erfüllbarkeit vorhersagen. Die Kernmessung hat 4 800 solche Instanzen, je zur Hälfte SAT und UNSAT — der Test kostet nichts und misst alle Grössen auf einmal.

Der Test bestätigt beide teuren Gegenproben unabhängig — das Vorzeichen der Varianz kehrt sich bei festgehaltener Unwucht um (−0,28 roh, +0,29 partiell), passend zu dα_c/d(Varianz) = −0,150, und frust4 landet neunmal schwächer, genau wie dort gemessen.

Und er entscheidet über die Sterne. Die Schiefe von A²𝟙 sagt die Erfüllbarkeit nicht vorher — ihr Beitrag von +0,010 ist der erste auf der Vorzeichenachse, der ganz jenseits der Phasenlage liegt. Klein, aber sauber.

Ein Vorschlag von aussen: die Instanz zusätzlich mit allen Variablen negiert messen, und sie unter „alles wahr" und „alles falsch" durchgehen. Beide Teile haben eine kurze theoretische Antwort — und beide verdienen es, gezeigt statt behauptet zu werden. 280 Instanzen, vier Ansichten.

„Alle Variablen negiert" ist die Eichung g ≡ −1 und damit kein neuer Messpunkt, sondern derselbe Punkt mit anderem Namen. Gemessen: unwucht, frust4, tr(M³), gegen3 und Überschuss mit max |Δ| = 0 über alle vier Ansichten, Erfüllbarkeitsurteil in 280 von 280 Instanzen gleich.

„Alles wahr" zählt die rein negativen Klauseln — ein Träger mit Grad 1 an jeder Variablen, nach der Eichbedingung also keine Invariante:

Unter g ≡ −1 vertauschen sich die beiden Zahlen exakt, in 280 von 280 Instanzen. Unter der Mehrheitseichung kippen sie auf 51 gegen 194, während sich an der Formel nichts ändert.

Es gibt eine Fassung des Vorschlags, die doch invariant ist, und sie ist von anderer Bauart als die ganze Leiter: erst die Eichung kanonisch festlegen, dann messen. Mit s_v = sign(pos_v − neg_v) ist σ(c,v)·s_v invariant, obwohl beide Faktoren es nicht sind — und es ist kein Charakter, weil ein Vorzeichen einer Summe darin steckt. Gemessen wird, wieviele Literale je Klausel gegen ihre Mehrheit stehen (Gleichstand mit Gewicht ½, weil jeder Tiebreak sonst willkürlich wäre).

Die Summe ist alt — r(gegensumme, unwucht) = −0,91. Neu wäre die Ballung. Ausserhalb der Stichprobe liegt das Profil zwischen Basis und Placebo, und die beiden Richtungen widersprechen sich im Vorzeichen (−0,008 gegen +0,007). Genau daran erkennt man Rauschen: echtes Signal verbessert beide, wie die Sterne es tun. Leer.

Was der Versuch trotzdem geliefert hat: die Bestätigung der Eichneutralität auch unter gezielter Umbenennung — und eine Invariante anderer Bauart, die ebenfalls leer ist. Das engt den Raum weiter ein, in dem die restlichen 85 % noch sitzen können.

Dank Satz V1 liess sich die ganze Leiter in einem Durchgang messen statt in vieren. Verbundene Träger vor unverbundenen, kurze vor langen — die Ordnung, die der Auftrag selbst vorgibt.

Der Auftrag stellt einen Satz in Aussicht: ergeben die Stufen 1 bis 4 zusammen ausserhalb der Stichprobe keinen Beitrag jenseits des Rauschens, dann ist die Härte eine Funktion hohen Grades der Signatur, und keine lokale Vorzeichengrösse kann sie je vorhersagen.

Die Voraussetzung ist nicht erfüllt. Die Leiter liefert R² = 0,131 und 0,139, weit über jedem Rauschen. Der Satz wird deshalb nicht behauptet. Was stattdessen dasteht, ist schärfer, weil es genauer ist.

Dazu kommt die Varianz der 𝟙-gewichteten Spektraldichte (07b) und, klein aber sauber jenseits der Phasenlage, die Schiefe von A²𝟙 (07c). Alles andere ist eine dieser vier in anderer Schreibweise oder leer. Die Unwucht wirkt nur über die Erfüllbarkeitsschwelle; frust4 zur Hälfte. Die Gerüstachse verschiebt die Schwelle auch — und behält daneben einen Faktor 15, frust4 behält 1,2. Der Unterschied zwischen den beiden Achsen ist also quantitativ und gross, nicht qualitativ.

Nicht gemessen ist die Gesamtheit der Charaktere eines Grades; ihre Zahl ist astronomisch. Gemessen ist die Ordnung, die der Auftrag vorgibt, plus zwei Umgewichtungen, die eigens gesucht wurden — und beide sind leer.

• Nicht, dass die Vorzeichenachse leer ist. frust4 ist ein Treffer, an zwei Saatbereichen, ausserhalb der Stichprobe, mit dem vorhergesagten Vorzeichen und einer nachgewiesenen kausalen Kette.
• Nicht, dass keine lokale Vorzeichengrösse je etwas vorhersagen kann. Die Voraussetzung des Satzes ist nicht erfüllt, und der Satz wird nicht behauptet.
• Nicht, dass die gemessenen Grössen alle Charaktere ihres Grades erfassen. Ausgeschöpft ist die Ordnung, nicht der Raum.
• Nichts über andere Solver. Härte heisst hier: Konflikte des CDCL dieses Projekts. Die Zündprobe hängt dagegen an keinem Solver — der breitenbeschränkte Abschluss ist konfluent.
• Nichts über P gegen NP. Das ist eine Aussage über den schlimmsten Fall; zufälliges 3-SAT an der Schwelle ist dafür weder notwendig noch hinreichend.