Random-Projector Quantum Diagnostics of Ramsey Numbers and A Prime-factor Heuristic for R(5, 5) = 45

After the introductory Section 1, Section 2 formalizes the Z₂ × Z₂–graded Majorana/paraparticle framework: it defines the degree–(0, 0) pair and clique projectors ΠijR/B\Pi _{ij}^{R/B} and the central forbidden–clique operator P_m,n on the charge–zero module M₀, and establishes the exact Klein recursion R_V4(m, n) = R_V4(m – 1, n) + R_V4(m, n – 1). Section 3 introduces two randomized spectral diagnostics acting on the reduced (d = 24) charge-zero module: a linear rank-1 deflation map P_lin and an exponential map P_exp(α). These witnesses parallel Erdős’s first-moment method and are used to single out n = 45 on the diagonal. We then propose a compact prime-sequence heuristic for diagonal values. Next, we show how both diagnostics admit few-qubit quantum realizations via block-encoding/qubitization and a Hermitian dilation surrogate, and we extend the study to R(6, 6) and R(7, 7). Finally, we discuss applications to ML where the same witnesses provide fast, high-confidence negative certificates under graded constraints. Technical proofs and numerical details are deferred to the Appendix.

In the classical approach there are two ways to reason about Ramsey numbers. The first one is the existence via probability, the first-moment (expectation) method counts the expected number of forbidden monochromatic cliques under a uniformly random two-coloring; if this expectation is < 1, then there exists a coloring with none of them (a lower bound). The second-moment method goes further by controlling fluctuations (variance) to show that such colorings occur with non-negligible probability. The Lovász Local Lemma (LLL) handles families of rare, mildly dependent “bad” events (e.g., many overlapping clique constraints) and guarantees existence when dependencies are local. Janson-type inequalities quantify how unlikely it is that none of a large, overlapping family of small subgraphs appear, often sharpening first/second-moment conclusions for sums of dependent indicators [7, 19–21]. The second way is based on constructive and recursive bounds. Explicit colorings (circulant/Paley/Mathon-type) [22–25] furnish strong lower bounds, while the classical Erdős recursion R(m, n) ≤ R(m–1, n) + R(m, n–1) supplies widely used upper bounds [8].

In our case, the random-projector maps we use are deliberately one-sided, a “first–moment–style” diagnostics: they test for the onset of unavoidable structure rather than constructing colorings. Algebraically, forbidden cliques become central operators acting on the reduced (charge-zero) module M₀; our linear deflation P_lin and exponential map P_exp(α) probe whether any survivor subspace remains. Under i.i.d. isotropic rank-1 tests in d dimensions, the chance to miss an r-dimensional survivor subspace obeys the familiar exponential tail P_miss ≤ e^–kr/d, so increasing k/d drives a rapid “no-survivor” decision, an analogue of the first-moment decay in the coin-flip view. In short: classical first/second moment, LLL, and Janson reason about counts and dependencies of bad subgraphs; our spectral surrogates reason about the rank that those constraints leave behind.

Position on R(5, 5) and resources. Our diagnostics are consistent with the classical window 43 ≤ R(5, 5) ≤ 46 and single out n = 45 as the threshold within the graded-module model. This complements (not replaces) constructive lower bounds (circulant/Paley/Mathon) and the recursion-based upper bounds above. Operationally, working in the reduced module of dimension d = 24 keeps the data width to ⌈ log2d ⌉=5\left\lceil {{{\log }_2}d} \right\rceil = 5 qubits (plus few ancillas), in stark contrast to direct edge-register encodings that would require one qubit per edge (e.g., 990 data qubits at n = 45). Our contribution is therefore a compact, algebraic–spectral surrogate that (i) acts entirely in the charge-zero module and (ii) trades explicit constructions for one-sided, high-confidence diagnostics aligned with the classical probabilistic intuition.

Let 𝒫₆ = {2,3,5,7,11,13} denote the first six primes. We call an integer q prime-sequence numbers of order k = 6(PS₆) if its prime factorisation involves only primes from 𝒫₆, i.e. q=∏p∈P6pvpq = \prod\nolimits_{p \in {{\cal P}_6}} {{p^{{v_p}}}} with v_p ∈ ℕ ∪ {0}. Starting from the exact values R(1, 1) = 1, R(2, 2) = 2, R(3, 3) = 6, R(4, 4) = 18 and the algebraic–spectral result R(5, 5) = 45 obtained in the main text, we impose two constraining axioms we use as basic assumptions.

Axiom I: Prime-sequence numbers of order k constraint: R(n,n)∈PSk3:={q∈ℕ∣q prime-sequencenumbers of order k}R(n,n) \in {\rm{PS}}_{\rm{k}}^3: = \{ q \in \mid q{\rm{ prime - sequence}}\;{\rm{numbers of order }}k{\rm{\} }}.

Axiom II: Moderate–growth corridor:

R(n,n)R(n−1,n)≤2{{R(n,n)} \over {R(n - 1,n)}} \le 2 for every n ≥ 2.

Since R(m, n) ≤ R(m – 1, n) + R(m, n – 1) for all m, n ∈ ℕ[1], the diagonal case is obtained setting m = n gives R(n, n) ≤ R(n – 1, n) + R(n, n – 1) and by symmetry R(n – 1, n) = R(n, n – 1) thus, the direct bound is R(n, n) ≤ 2R(n – 1, n).

For each n ≥ 2 define the off–diagonal ratio 20ρn:=R(n,n)R(n−1,n).{\rho _n}: = {{R(n,n)} \over {R(n - 1,n)}}.

Because Erdős’ recursion forces ρ_n ≤ 2, one can check whether the known data and rigorous bounds stay inside that “moderate–growth corridor’’ ρ_n ∈ [1, 2].

The first three diagonals are known exactly and satisfy ρ_n ≤ 2. (n = 2): R(2, 2) = 2, R(1, 2) = 1 ⇒ æ₂ = 2, (n = 3): R(3, 3) = 6, R(2, 3) = 3 ⇒ æ₃ = 2, (n = 4): R(4, 4) = 18, R(3, 4) = 9 ⇒ æ₄ = 2.

For n = 5 we know 43 ≤ R(5, 5) ≤ 46 and R(4, 5) = 25, 1.72=4325<ρ5≤4625=1.84.1.72 = {{43} \over {25}} &#x003C; {\rho _5} \le {{46} \over {25}} = 1.84. n = 6. Current bounds are 102 ≤ R(6, 6) ≤ 160 and 59 ≤ R(5, 6) ≤ 85 [11], whence 1.20=10285≤ρ6≤16059=2.71.1.20 = {{102} \over {85}} \le {\rho _6} \le {{160} \over {59}} = 2.71.

The extreme combination 160/59 would violate ρ₆ ≤ 2, but that pairing uses the loosest numerator with the loosest denominator. Matching either both lower or both upper bounds gives 102/59 = 1.73 and 160/85 = 1.88, so every empirically plausible value of ρ₆ lies below 2.

With n = 7 the limits are 205 ≤ R(7, 7) ≤ 492 and 115 ≤ R(6, 7) ≤ 270 [11, 29] and we obtain 0.76=205270≤ρ7≤492115=4.28,0.76 = {{205} \over {270}} \le {\rho _7} \le {{492} \over {115}} = 4.28, while the matched bounds 205/115 = 1.78 and 492/270 = 1.82 again fall well inside the corridor.

The exact ratios through n = 4 are all ρ_n = 2. For n = 5 the interval [1.72, 1.84] sits comfortably below 2. For n = 6, 7 the widest theoretical cross-bounds still allow a violation, but every combination that pairs consistent lower and upper estimates (e.g. 102/59, 160/85 for n = 6) yields ρ_n < 2.

These observations motivate Axiom II 4: ρ_n ≲ 2 (“moderate–growth corridor”). Under this axiom, Eq. (19) extends Erdős’ recursive upper bound into a working heuristic for the unknown diagonals R(6, 6) and R(7, 7) while remaining consistent with all currently published data.

Enforcing the prime-sequence numbers of order k factorization rules (no more than three distinct primes and no exponent above 3) under axioms I 4– II 4 the factorization with prime-sequence numbers of orders 5 ≤ k ≤ 13 are reported in Table 3.

There, each column uses the first k primes 𝒫_k = {2, 3, …, p_k} to build the sparsest admissible factorisation (at most three distinct primes, each exponent ≤ 3). Boldface marks the persistent values that remain unchanged from their first appearance up to the cut-off k = 2n – 1 (k = 11 for n = 6, k = 13 for n = 7).

Allowing more primes generally lowers the sparsest admissible R(6, 6) = 115 and R(7, 7) remains 209 in most schemes. A plateau indicates robust guesses. The criterion is persistence, we accept as the provisional diagonal value’ the integer that remains constant up to the largest admissible prime basis k_max(n) = 2n – 1. Anyway, as 45 already factors within the smallest prime basis 𝒫₅ = {2,3,5,7,11} and satisfies the sparsity rule (≤ 3 primes, maxV_p = 2), it would be still present in the table until 𝒫₉ where the prime 23 gets in defining 46 = 2 × 23. From our results the prime-sequence numbers of order k for a diagonal Ramsey number R(n, n) is limited by k < 2n – 1 and this disfavors the other value, 44 and 46 is controversial.

When cut-off rule k ≤ 2n – 1 applied to R(5, 5), for the diagonal n = 5 the prime basis is allowed to grow only up to k_max = 2n – 1 = 9. The prime-sequence numbers of order k criteria are fewest distinct primes, smaller numerical value. If we add also smallest maximal exponent we obtain the results in Table 4,

When the ninth prime 23 becomes available, the factorisation 46 = 2 × 23 has the same number of distinct primes as 44 and 45 but a strictly smaller maximal exponent (1 ≤ 2) gives also evidence to 46. Because k = 9 already saturates the cut-off, no larger prime basis may undo this choice.

The fact that R(6, 6) = 115 and R(7, 7) = 209 survive every prime basis from 𝒫₉ to 𝒫₁₁ suggests they are the most stable predictions of the prime-sequence numbers of order k framework. More in detail, for R(6, 6) the optimum sequence drops from 108 (prime set 𝒫₅) to 117 once 13, 17 are allowed and settles at 115 with the inclusion of 23; the next prime, 37, immediately produces 111 = 3 × 37, after which no further prime extension changes the result. The value R(6, 6) = 115 is stable for every prime set from k = 9 up to the cut-off k_max = 11. It only changes to 111 when k = 12 > k_max; hence R(6, 6) = 115 is the persistent choice.

For R(7, 7) the value moves from 225 → 221 → 209 as soon as 19 enters the basis, and then remains pinned at 209 = 11 × 19 for six consecutive prime sets (𝒫₈–𝒫₁₂); only the arrival of 41 in 𝒫₁₃ lowers the prediction to the window floor 205 = 5 × 41. The integer 209 persists throughout the entire plateau k = 8–12, but the cut-off for n = 7 is k_max = 13; at that very last step the sparser factorisation 205 = 5 × 41 appears and becomes the new stable value. Therefore R(7, 7) = 209 is selected.

Thus the persistence principle reproduces the same predicted diagonals derived earlier with the explicit k ≤ 2n – 1 cut-off suggesting R(5, 5) = 45, R(6, 6) = 115 and R(7, 7) = 209. All three numbers continue to satisfy the sparsity axiom (no more than three primes, each exponent ≤ 3) and the tightened growth corridor R(n, n) ≤ 2 R(n – 1, n) and are defined within their known ranges.

Any constructive colouring at v < 111 or v < 209 would falsify the present sparsity hypothesis, whereas exhaustive elimination of colourings at v = 111 or v = 205/209 would push the rigorous lower bounds upward and force a narrower theoretical window.

The prime-sequence numbers of order k framework suggests the reduction of the enormous search space to a tiny target set, beyond the value R(6, 6) = 117 giving 21R(6,6)∈{108,111,115},R(7,7)∈{205,209}.R(6, 6) \in \{ 108,111,115\} ,\quad R(7, 7) \in \{ 205,209\} .

Exhaustive two-coloring searches should therefore be concentrated on these vertex counts. If none of these candidates admit a valid coloring, then either the prime-sequence numbers of order k sparsity hypothesis, valid empirically for the known diagonal Ramsey numbers, (no more than three distinct primes with exponents ≤ 3) or the tightened growth corridor R(n, n) ≤ 2 R(n – 1, n) must be reconsidered or weakened.

Conversely, the discovery of a single explicit coloring with R(6, 6) < 111 or R(7, 7) < 209 would break the current sparsity barrier, indicating that even the lightest admissible diagonal values require either more than three primes or a prime exponent exceeding the number bound 3. If, instead, exhaustive computation rules out all admissible colorings at v = 111 and v = 209 (or 205), the rigorous lower bounds would rise, forcing a narrower theoretical window and further constraining the allowable growth corridor.

This therefore supplies a minimal, fully factorized scaffold for future constructive or computational attacks on R(6, 6) and R(7, 7): any refutation must either break the prime sequence numbers of order k condition in Axiom I or force a growth ratio outside the empirical corridor in Axiom II. We regard this as a heuristic scaffold for targeting constructive searches; it does not constitute a proof or bound by itself.

Ramsey numbers were evaluated with classical methods calculating the two scalar witnesses, the linear and exponential projectors P_lin and P_exp(α), with A=∑j=1kvjvj⊤A = \sum\nolimits_{j = 1}^k {{v_j}} v_j^ \top and declare v, as before, “critical” when Tr Plin peaks while T(α) := Tr P_exp(α) collapses. To translate these operations in the language of quantum computing we build the equivalents of the previous equations in terms of quantum circuits.

On a quantum device we reproduce the same scalars by two identities: first the Hutchinson identity E|r〉〈r|F|r〉=1d{_{|r\rangle }}\langle r|F|r\rangle = {1 \over d}{\mathop{\rm Tr}\nolimits} F Tr F, for any linear operator F ∈ ℂ^d×d on the data register M₀ with dimension d = 24 and a random quantum state |r〉 from a unitary 2-design, so that d 〈r|F|r〉 is an unbiased trace estimator; F can be either P_lin or P_exp. On hardware is applied a block-encoding U_F on data+ancillas with (〈0a|⊗I )UF(|0a〉⊗I)=F/α0\left. {\langle {0^a}| \otimes I} \right){U_F}\left( {\left| {{0^a}} \right\rangle \otimes I} \right) = F/{\alpha _0}, so the Hutchinson estimator averages 〈r|F|r〉=TrF/d(orTrF/(α0d))\langle r|F|r\rangle = {\mathop{\rm Tr}\nolimits} F/d\left( {{\mathop{\rm or}\nolimits} {\mathop{\rm Tr}\nolimits} F/\left( {{\alpha _0}d} \right)} \right). The Hermitian dilation H of Eq. (23), for which H² = diag(AA^†, A^†A) and σ(H)={ ±σi(A) }i=1d\sigma (H) = \left\{ { \pm {\sigma _i}(A)} \right\}_{i = 1}^d gives the second identity. Thus phase estimation on e^−itH accesses the singular spectrum of A, while Hadamard tests over a random |r〉 estimate Tr P_lin and T(α) coherently. In our d = 24 charge-zero module this uses the ceiling ⌈ log2d ⌉=5\left\lceil {{{\log }_2}d} \right\rceil = 5 data qubits plus few ancillas for R(5, 5).

Inputs. Fix (d, k, α, seed), reuse the same random unit directions { vj }j=1k⊂ℂd\left\{ {{v_j}} \right\}_{j = 1}^k \subset {^d} used classically to build the accumulator A=∑j=1kvjvj⊤A = \sum\nolimits_{j = 1}^k {{v_j}v_j^ \top } on M₀. We reuse the diagnostics defined earlier: P_exp(α) and P_lin in Eqs. (10)–(11).

Measurements. By the Hutchinson identity, for any implementable linear map F, E|r〉〈r|F|r〉=TrF/d{_{|r\rangle }}\langle r|F|r\rangle = {\mathop{\rm Tr}\nolimits} F/d when |r〉 is drawn from a unitary 2-design; we realize 〈r|F|r〉 by a Hadamard test and average over random |r〉’s (a more detailed discussion for the estimation of traces and spectra is written in Section 5.4). Amplitude estimation reduces the shot complexity from O(1/ϵ²) to O(1/ϵ) for additive error ϵ.

We estimate three quantities: (i) the scalar trace witness Tr P_lin, (ii) the exponential trace T(α) = Tr P_exp(α), and (iii) a spectral surrogate via the Hermitian dilation in Eq. (23).

Report (Tr P_lin, T(α), ρ(α)) with (d, k, α, seed) and the decision flag for each tested v.

We assume as decision rule the following: for a fixed d, k, α (and random seed), declare a vertex count v critical if: (i) Tr P_lin attains a local maximum at v; (ii) T(α) = Tr P_exp(α) collapses (numerically ≈ 0) at the same v; (iii) the spectral proxy (e.g. ‖A‖2=ρ(H)A{_2} = \rho (H) by phase estimation) is locally extremal at v; and an explicit AM-46 control remains non-critical under the same thresholds.

Track Q (qubitized block-encoding). Track Q uses qubitized block-encodings; Track M uses Majorana/matchgate Gaussian primitives to realize the degree (0, 0) projectors directly in M₀. Both tracks operate in the same d = 24 module. As A is generally complex-symmetric (not Hermitian) when built from vv^⊤, we embed A into the Hermitian dilation 23H=(0AA†0),‖A‖2=ρ(H),H = \left( {\matrix{ 0 & A \cr {{A^\dag }} & 0 \cr } } \right),\quad A{_2} = \rho (H), and access spectral surrogates by phase estimation on e^−itH. Because σ(H) = {±σ_i(A)}, a local maximum of the extracted ‖A‖2=ρ(H)A{_2} = \rho (H) at the same v that triggers (i)–(ii) is expected. Here ‖A‖2A{_2} is the spectral norm (largest singular value) and ρ(H) is the spectral radius of the Hermitian dilation H; since σ(H) = {±σ_i(A)}, we have ρ(H)=maxiσi(A)=‖A‖2\rho (H) = {\max _i}{\sigma _i}(A) = A{_2}. The hardware surrogate for e^−aA is so settled.

As A from vv^⊤ is typically non-normal, we implement functions of the dilation H (or of H²) via block-encoding/qubitization. Notably H² = diag(AA^†, A^†A) implies Tre−βH2=Tre−βAA†+Tre−βA†A=2Tre−βAA†.{\mathop{\rm Tr}\nolimits} {e^{ - \beta {H^2}}} = {\mathop{\rm Tr}\nolimits} {e^{ - \beta A{A^ + }}} + {\mathop{\rm Tr}\nolimits} {e^{ - \beta {A^ + }A}} = 2{\mathop{\rm Tr}\nolimits} {e^{ - \beta A{A^ + }}}.

Estimating Tr e^−βH2 therefore serves as a stable surrogate for the exponential witness T(α): both are monotone in the singular values of A and collapse precisely when the survivor subspace vanishes. This also gives a block-encoding of A enabling polynomial/Fourier approximants to f(A) ∈ {A, e^−αA}.

Operators used in Figure 1 (Phase Estimation on the Hermitian Dilation). Accumulator A:=∑j=1kvjvj⊤A: = \sum\limits_{j = 1}^k {{v_j}} v_j^ \top is the complex-symmetric rank-k sum built from the random directions v_j ∈ ℂ^d in the charge-zero module M₀ (with dimension d).

Figure 1.

Phase-estimation on the Hermitian dilation H (Eq. (23)) to estimate its extremal eigenphase(s), hence ρ(H)=‖A‖2\rho (H) = A{_2}. The “sig” (sign) qubit together with the data register realizes the 2d-dimensional space of the dilation; the PE register controls powers of e^−itH. A local maximum of the extracted ‖A‖2A{_2} at the critical v complements the linear/exponential diagnostics.

Hermitian dilation H (Eq. (23)); its spectrum is σ(H)={ ±σi(A) }i=1d\sigma (H) = \left\{ { \pm {\sigma _i}(A)} \right\}_{i = 1}^d, so ‖A‖2=ρ(H)A{_2} = \rho (H).

Controlled evolutions. The string c-e^−i2ℓtH denotes the standard phase-estimation controlled unitaries at time-steps 2^ℓt, followed by the inverse QFT on the PE register to read out the extremal eigenphase(s), hence ‖A‖2A{_2}. The prefix “c-” denotes a standard single–qubit controlled gate: c−U:=(|0〉〈0|)ctrl⊗Idata+(|1〉〈1|)ctrl⊗Udata′c - U: = (|0\rangle {\langle 0|)_{{\rm{ctrl}}}} \otimes {I_{{\rm{data}}}} + (|1\rangle {\langle 1|)_{{\rm{ctrl}}}} \otimes {U_{{\rm{data'}}}} so that c−e−i2ktH=(|0〉〈0|)k⊗I+(|1〉〈1|)k⊗e−i2ktH.c - {e^{ - i{2^k}tH}} = (|0\rangle {\langle 0|)_k} \otimes I + (|1\rangle {\langle 1|)_k} \otimes {e^{ - i{2^k}tH}}.

Acting on a basis state |c_m–1 … c₀〉_PE ⊗ |ψ〉_data (with c_k ∈ {0,1}), the whole product implements (∏k=0m−1c−e−i2ktH)(|c〉⊗|ψ〉)=|c〉⊗e−i(∑kck2k)tH|ψ〉,\left( {\prod\limits_{k = 0}^{m - 1} {\rm{c}} - {e^{ - i{2^k}tH}}} \right)(|c\rangle \otimes |\psi \rangle ) = |c\rangle \otimes {e^{ - i\left( {\sum\nolimits_k {{c_k}} {2^k}} \right)tH}}|\psi \rangle , i.e., a data–register evolution for a time proportional to the integer encoded by the control register. Because all factors are functions of the same H, they mutually commute on the data space, so their order is immaterial (though the circuit is usually drawn MSB→LSB to match the inverse QFT). Here m is the number of phase bits (PE precision) and t is the chosen base time step; in our setting H so that ρ(H)=‖A‖2\rho (H) = A{_2}, and these controlled evolutions are the core of the Hermitian-dilation phase–estimation block used as a spectral witness.

Registers. |0〉_sig is the dilation’s sign qubit; |0〉PE ⊗m|0\rangle _{{\rm{PE }}}^{ \otimes m} is the m-qubit phase-estimation register; |ψ〉_data is the d-dimensional data register (for R(5, 5), ⌈ log2d ⌉=5\left\lceil {{{\log }_2}d} \right\rceil = 5 data qubits). We reserve H_Had for the one-qubit Hadamard gate to avoid confusing it with the dilation H; where the symbol H appears inside W_j below it is the Hadamard gate.

Rank-1 LCU for A. We write the One-ancilla rank-1 in Figure 2, A=∑jwj|uj〉〈vj|A = \sum\nolimits_j {{w_j}} \left| {{u_j}} \right\rangle \left\langle {{v_j}} \right|, prepare |u_j〉, |v_j〉 with unitaries U_j, V_j. A 1-ancilla block for a term is obtained with 24Wj:=(|0〉〈0|⊗Uj+|1〉〈1|⊗Vj)(H⊗I),{W_j}: = \left( {|0\rangle \langle 0| \otimes {U_j} + |1\rangle \langle 1| \otimes {V_j}} \right)(H \otimes I), whose top-left block equals 12|uj〉〈vj|{1 \over 2}\left| {{u_j}} \right\rangle \langle {v_j}| (here H is the single-qubit Hadamard on the ancilla).

Figure 2.

One-ancilla rank-1 block-encoding gadget W_j implementing the top-left block 12|uj〉〈vj|{1 \over 2}\left| {{u_j}} \right\rangle \langle {v_j}| (see Eq. (24)). The multiplexor applies U_j when the ancilla is |0〉 and V_j when it is |1〉. Composing these gadgets with a single selector/index register and oblivious amplitude amplification yields an α₀–block-encoding of A/α0=∑jwj|uj〉〈vj|/α0A/{\alpha _0} = \sum\nolimits_j {{w_j}} \left| {{u_j}} \right\rangle \langle {v_j}|/{\alpha _0}.

Operators used in Figure 2 (Rank-1 LCU block-encoding gadget). State-prepunitaries. Uj|0〉=|uj〉,Vj|0〉=|vj*〉{U_j}|0\rangle = \left| {{u_j}} \right\rangle ,{V_j}|0\rangle = \left| {v_j^*} \right\rangle prepare the rank-one factors (“*” appears when the complex-symmetric vv^⊤ structure is used).

Multiplexor. MUX(Uj,Vj):=|0〉〈0|⊗Uj+|1〉〈1|⊗Vj{\mathop{\rm MUX}\nolimits} \left( {{U_j},{V_j}} \right): = |0\rangle \langle 0| \otimes {U_j} + |1\rangle \langle 1| \otimes {V_j}. This gate is a controlled selection, uniformly controlled unitary, that applies U_j to the data register when the one-qubit selector is |0〉, and V_j when the selector is |1〉:MUX(Uj,Vj)(|0〉⊗|ψ〉)=|0〉⊗Uj|ψ〉|1\rangle :{\mathop{\rm MUX}\nolimits} \left( {{U_j},{V_j}} \right)(|0\rangle \otimes |\psi \rangle ) = |0\rangle \otimes {U_j}|\psi \rangle and MUX(Uj,Vj)(|1〉⊗|ψ〉)=|1〉⊗Vj|ψ〉{\mathop{\rm MUX}\nolimits} \left( {{U_j},{V_j}} \right)(|1\rangle \otimes |\psi \rangle ) = |1\rangle \otimes {V_j}|\psi \rangle . In the selector computational basis it is block–diagonal, diag(U_j, V_j). A useful implementation identity is MUX(Uj,Vj)=(I⊗Uj)(c−(Uj†Vj)),{\mathop{\rm MUX}\nolimits} \left( {{U_j},{V_j}} \right) = \left( {I \otimes {U_j}} \right)\left( {{\rm{c}} - \left( {U_j^\dag {V_j}} \right)} \right), so the multiplexor can be built from one unconditional application of U_j on the data plus a single controlled unitary with target Uj†Vju_j^ + {V_j}. The definition extends to an m-qubit selector as MUX({ Us }s∈{0,1}m)=∑s∈{0,1}m|s〉〈s|⊗Us,{\mathop{\rm MUX}\nolimits} \left( {{{\left\{ {{U_s}} \right\}}_{s \in {{\{ 0,1\} }^m}}}} \right) = \sum\limits_{s \in {{\{ 0,1\} }^m}} | s\rangle \langle s| \otimes {U_{\rm{s}}}, which applies U_s conditioned on the selector string s. In our block–encoding gadget of Fig. 2, choosing state–preparations Uj|0〉=|uj〉{U_j}|0\rangle = \left| {{u_j}} \right\rangle and Vj|0〉=|vj〉{V_j}|0\rangle = \left| {{v_j}} \right\rangle and combining MUX(U_j, V_j) with Hadamards on the selector yields the desired rank-one ancilla block used to assemble the linear combination of terms in the accumulator.

Gadget. Wj:=(|0〉〈0|⊗Uj+|1〉〈1|⊗Vj)(HHad⊗I){W_j}: = \left( {|0\rangle \langle 0| \otimes {U_j} + |1\rangle \langle 1| \otimes {V_j}} \right)\left( {{H_{{\rm{Had}}}} \otimes I} \right) has top-left ancilla block 12|uj〉〈vj|{1 \over 2}\left| {{u_j}} \right\rangle \langle {v_j}|. From terms to A. With weights w_j, a single selector register plus oblivious amplitude amplification yields an α₀–block-encoding of A/α0=∑jwj|uj〉〈vj|/α0A/{\alpha _0} = \sum\nolimits_j {{w_j}} \left| {{u_j}} \right\rangle \langle {v_j}|/{\alpha _0}.

Functions of A. Using LCU/qubitization (or QSVT), polynomials/Fourier approximants realize f_lin(z) = z and f_exp(z) = e^−αz, giving P_lin and P_exp(α) coherently.

Operators used in Figure 2 (Rank-ILCU block-encoding gadget). State-prepunitaries. Uj|0〉=|uj〉,Vj|0〉=|vj*〉{U_j}|0\rangle = \left| {{u_j}} \right\rangle ,{V_j}|0\rangle = \left| {v_j^*} \right\rangle prepare the rank-one factors (“*” appears when the complex-symmetric vv^⊤ structure is used). Multiplexor. MUX(Uj,Vj):=|0〉〈0|⊗Uj+|1〉〈1|⊗Vj{\mathop{\rm MUX}\nolimits} \left( {{U_j},{V_j}} \right): = |0\rangle \langle 0| \otimes {U_j} + |1\rangle \langle 1| \otimes {V_j}. Gadget. Wj:=(|0〉〈0|⊗Uj+|1〉〈1|⊗Vj)(HHad⊗I){W_j}: = \left( {|0\rangle \langle 0| \otimes {U_j} + |1\rangle \langle 1| \otimes {V_j}} \right)\left( {{H_{{\rm{Had}}}} \otimes I} \right) has top-left ancilla block 12|uj〉〈vj|{1 \over 2}\left| {{u_j}} \right\rangle \langle {v_j}|. From terms to A. With weights w_j, a single selector register plus oblivious amplitude amplification yields an α₀–block-encoding of A/α0=∑jwj|uj〉〈vj|/α0A/{\alpha _0} = \sum\limits_j {{w_j}} \left| {{u_j}} \right\rangle \langle {v_j}|/{\alpha _0}.

Track M (Majorana-native). On the platforms that natively support Majorana bilinears (match–gate/fermionic – Gaussian hardware), all degree–(0, 0) pair and clique projectors reduce to even–parity checks on the data modes: each monochromatic pair projector ΠijR/B\Pi _{ij}^{R/B} and their products Π_R(S), Π_B(T) act entirely inside the charge–zero module M₀ and commute with total parity, hence can be realized as parity–preserving projectors built from quadratic Majorana terms. P_lin is then best read as a randomized mixture of parity checks: in the decomposition used in the text, P_lin, each rank–one deflation removes amplitude along a random degree–(0, 0) direction (a linear combination inside the span generated by pair/clique checks) within M₀, and the product effects the Hutchinson–style contraction that diagnoses the disappearance of survivors (Eq. (8)). By contrast, P_exp(α) is naturally implemented as repeated weak Gaussian projections in M₀: Trotterize exp(−δαvjvj⊤)\left( { - \delta \alpha {v_j}v_j^ \top } \right) for small δ_α and cycle j = 1, …, k, which preserves the even–parity sector by construction (Eq. (7)). Because all operators used by the diagnostics are degree–(0, 0), they act only on M₀ and are independent of the mixed (1, 1) sector projected out by the modeling axiom; thus the Majorana–native track realizes exactly the same witnesses as the generic qubit route while exploiting native parity checks. Cf. the definitions of the graded projectors, the M₀ restriction, and the linear/exponential maps in the main text.

Unbiased trace estimator (Hutchinson). For any implementable linear map F, random |r〉 from a unitary 2-design obeys 25E|r〉[〈r|F|r〉]=1dTrF,{_{|r\rangle }}[\langle r|F|r\rangle ] = {1 \over d}{\mathop{\rm Tr}\nolimits} F, so d〈r|F|r〉¯d\overline {\langle r|F|r\rangle } is an unbiased trace estimator; variance decreases as O(1/N) or O(1/N²) with amplitude estimation.

Operators used in Figure 3 (Hadamard-test realization of Hutchinson’s trace estimator). Random probe. |r〉 = C|0 ⋯ 0〉 where C is a unitary 2-design (e.g., a random Clifford) on the data register; C^† is undone at the end so the data returns to the computational frame. Block-encoding of the map. U_F is an (α₀, a) block-encoding of the (generally non-unitary) map F, i.e. (〈0a|⊗I)UF(|0a〉⊗I)=F/α0\left( {\langle {0^a}| \otimes I} \right){U_F}\left( {\left| {{0^a}} \right\rangle \otimes I} \right) = F/{\alpha _0}. In this section F ∈ { P_exp(α) = e^−αA, P_lin} (Eqs. (7)–(8)). Ancilla routine. The ancilla is prepared in |+〉, a Hadamard–U_F–Hadamard sequence is applied, and the Pauli-Z observable is measured on the ancilla. Averaging 〈Z〉 over independent random C’s (Hutchinson sampling) yields an unbiased estimate of Tr F/d; amplitude estimation can reduce shot complexity from O(1/ε²) to O(1/ε). Lyapunov decay proxy. We use the slope 26λL(α):=−ddαlogTrPexp(α)=Tr[ Ae−αA ]Tr[ e−αA ],{\lambda _L}(\alpha ): = - {d \over {d\alpha }}\log {\mathop{\rm Tr}\nolimits} {P_{\exp }}(\alpha ) = {{{\mathop{\rm Tr}\nolimits} \left[ {A{e^{ - \alpha A}}} \right]} \over {{\mathop{\rm Tr}\nolimits} \left[ {{e^{ - \alpha A}}} \right]}}, as a monotone indicator of contraction.

Figure 3.

Hadamard-test realization of the Hutchinson identity (Eq. (25)). A random |r〉 is prepared by a unitary 2-design C on the data register; U˜F{{\tilde U}_F} is a block-encoding of F (either F = P_exp (α) = e^−aA or F = P_lin). Averaging the ancilla’s 〈Z〉 over random |r〉 gives an unbiased estimate ofTr F/d; amplitude estimation can reduce shot complexity.

The observed signature at n = 45 and miss-probability are so obtained. On the d = 24 module with k ∈ [100,400] and α ∈ {20,40}, the diagnostics concur at n = 45: T(α) collapses while Tr P_lin peaks; the Angeltveit–McKay 46-vertex coloring (AM–46) [3] does not trigger. The false-negative risk under i.i.d. rank-1 directions obeys P_miss ≲ e^−kr/d for residual rank r, placing the operational risk < 10⁻³ for the reported settings and ~ 10⁻⁷ once r ≥ 12.

The resources and NISQ-friendly variant are the following. With d = 24, the data register is 5 qubits; a single ancilla suffices for block-encoding and one for overlap/phase estimation (7–8 qubits total). Depth scales as O˜(kCprep )\widetilde O\left( {k\;{C_{{\rm{prep }}}}} \right) for constant-precision exponentiation; phase estimation adds O(1/ϵ) controlled evolutions for precision ϵ. A shallow NISQ variant Hermitianizes A by replacing vv^⊤ with vv^†, keeping the qualitative signatures (peak / collapse) while simplifying circuits.

We recall that for integers m, n ≥ 1, the (two–color) Ramsey number R(m, n) is the least v such that every red/blue edge–coloring of the complete graph K_v contains a red K_m or a blue K_n. Ramsey’s theorem yields finiteness and the classical Erdős recursion. Exact values are known only at small parameters and diagonal cases grow notoriously fast. In this work we study these thresholds with a graded ℤ₂ × ℤ₂ Majorana algebra and two random–projector diagnostics that replace brute–force enumeration by spectral surrogates acting on a reduced (charge–zero) module.

Graded embedding and randomized spectral diagnostics is obtained through Klein–graded paraparticle algebra, from the Majorana modes γj(0),γj(1)\gamma _j^{(0)},\gamma _j^{(1)} with { γi(α),γj(β) }=2δijδαβ\left\{ {\gamma _i^{(\alpha )},\gamma _j^{(\beta )}} \right\} = 2{\delta _{ij}}{\delta _{\alpha \beta }}. Define aj=(γj(0)+γj(1))/2{a_j} = \left( {\gamma _j^{(0)} + \gamma _j^{(1)}} \right)/2 (red charge (1, 0)) and bj=(γj(0)−γj(1))/2{b_j} = \left( {\gamma _j^{(0)} - \gamma _j^{(1)}} \right)/2 (blue charge (0, 1)). A two–coloring lifts to the degree–(0, 0) edge operator of Eq. (4) which commutes with total Klein charge. Monochromatic pair and clique projectors ΠijR\Pi _{ij}^R, ΠijB\Pi _{ij}^B; ∏R(S)=∏i<j∈S∏ijR,∏B(T)=∏i<j∈T∏ijB{\prod _R}(S) = {\prod _{i &#x003C; j \in S}}\prod _{ij}^R,{\prod _B}\left( T \right) = {\prod _{i &#x003C; j \in T}}\prod _{ij}^B live in the charge–zero submodule M₀; the central obstruction to a good coloring is Eq. (6) and a coloring (or an entire symmetry class thereof) survivesiff P_m,n annihilates it. In this setting the Klein–compatible coproduct realizes the glue step v → v + 1 and yields an exact recursion for the graded numbers R_V4 (m, n) in Eq. (7).

To decide if any legal survivor subspace remains in M₀ ≃ ℝ^d, we use two families of randomized maps built from i.i.d. isotropic unit vectors v_j ∈ ℝ^d, the linear deflation of Eq. (11) and the exponential map (Eq. (10)). If a survivor subspace has rank r ≥ 1, then k random rank–1 tests miss it with probability P_miss, so P_lin rapidly kills survivors as k/d grows, while T(α) collapses once survivors vanish. For non–normal A we use the Hermitian dilation H, giving a stable spectral surrogate accessible by phase estimation (quantum) or power iteration (classical).

R(5, 5) case and resource contrast. On the diagonal, the reduced module has d = 24; both witnesses single out v = 45: T(40) ≈ 2.4 × 10⁻²⁸⁹ at (k, α) = (400, 40) while Tr P_lin peaks locally at v = 45; an explicit v = 46 control remains non–critical under the same thresholds. Under the i.i.d./isotropy model, Pr[pmiss] ≲ e^−100/24 ≈ 1.6 × 10⁻² at (100, 20) and ≲ e^−400/24 ≈ 5.7 × 10⁻⁸ at (400, 40). Crucially, these diagnostics act only on M₀, requiring ⌈log₂ d⌉ = 5 data qubits (plus few ancillas), versus (452)=990\left( \matrix{ 45 \cr 2 \cr} \right) = 990 data qubits for direct edge–encodings.

Ramsey theory formalizes “order amid chaos”: sufficiently large systems necessarily contain structured subconfigurations. This principle echoes throughout modern ML and suggests concrete tests and controls using the witnesses above.

Overparameterization and lottery tickets. Let 𝒩 be a (possibly overparameterized) network with parameters W ≈ ℝ^D. Define a graph on neurons where the edge {i, j} is colored red if a predicate P_ij(W) holds (e.g., |W_ij| > τ, or sign/gradient agreement, correlation above a threshold), blue otherwise.

Whenever the effective width v exceeds the relevant R(k, k), a monochromatic K_k is guaranteed, i.e. a small subnetwork obeying P coherently–akin to the Lottery–Ticket hypothesis. We can certify the continued existence (or disappearance) of such candidates by encoding Π_R (S) from the predicate and monitoring the collapse/peak of T(α) and Tr P_lin as pruning proceeds; the risk of a false “no–ticket” verdict is controlled by Eq. (16) through k/d.

Build the predicate graph on vertices [v] by coloring an edge {i, j} red when P_ij(W) = 1 and blue otherwise. A Ramsey k–lottery is a set S ⊂ [v] with |S| = k such that all edges inside S are red; this is a K_k fully coherent for P and can be read as a compact subnetwork (a “ticket”) already encoding the desired structure. Ramsey’s theorem implies that once v ≥ R(k, k) a monochromatic K_k must exist, so the search for a good ticket can be recast as the impossibility of avoiding such a red K_k. In the graded framework, encode the forbidden condition “no red K_k” by the central operator in Eq. (27) 27Qk(W):=∏|S|=k(I−ΠR(S)),ΠR(S)=∏i<j∈SΠijR( degree (0,0)),\matrix{ {{Q_k}(W): = \prod\limits_{|S| = k} {\left( {{\rm{I}} - {\Pi _R}(S)} \right)} ,} \hfill \cr {{\Pi _R}(S) = \prod\limits_{i &#x003C; j \in S} {\Pi _{ij}^R} ({\rm{ degree }}(0, 0)),} \hfill \cr } acting on the charge–zero module M₀. If Q_k(W) has no surviving support, then a red K_k is unavoidable and at least one lottery ticket exists.

Operationally we decide this by randomized witnesses on M₀: P_lin and P_exp(α) with T(α). Sharing the same random seed across widths v lets us track the critical scale where tickets become inevitable: the collapse of T(α) together with a local peak of Tr P_lin signals Q_k(W) has emptied out, hence a P–coherent K_k exists. Under i.i.d. isotropic rank–1 probes in M₀ of dimension d, the miss–probability that all tests avoid a surviving r–dimensional subspace obeys P_miss, so choosing k≳(d/r) ln(1/δ) controls the false “no–ticket” verdict at level δ. This provides a quantified version of the Lottery–Ticket intuition: overparameterization raises v, and once the Ramsey threshold is crossed, small performant subnetworks are not accidental–they are guaranteed, and the witnesses certify their inevitability.

Adversarial inevitabilities (worst–case geometry). Form a near–collision graph on inputs X = {x_i}, coloring {i, j} red if the margin |f(x_i) – f(x_j)| < δ (for a score f), blue otherwise. Beyond a threshold v, large monochromatic cliques are inevitable, certifying coherent clusters of mutually confusable points. Our central projector of Eq. (4) with (m, n) = (k, k) and the witnesses (P_lin, P_exp) give an early–warning signal: collapse of T(α) indicates that confusion–free assignments have been extinguished within the defended hypothesis class.

Given inputs X = {x₁, …, x_v} and a score f, form the near–collision graph by coloring {i, j} red if |f(x_i) – f(x_j)| < δ (or, for classifiers, if the logits differ by < δ in all attack directions), blue otherwise. Large red cliques are coherent confusion sets—mutually confusable points that any fixed defense struggles to separate. To detect when such sets are unavoidable at scale v, instantiate the central projector of Eq. (6) with (m, n) = (k, k) and run the same witnesses (P_lin, P_exp(α)) on M₀. A collapse of T(α) indicates that the hypothesis class (with the current defense/training recipe) cannot realize a coloring that avoids size–k coherent confusions–i.e., adversarially vulnerable patterns are now Ramsey–inevitable at this v. The Lyapunov slope λL(α):=−ddαlogT(α)=Tr(Ae−αA)Tr(e−αA){\lambda _L}(\alpha ): = - {d \over {d\alpha }}\log T(\alpha ) = {{{\mathop{\rm Tr}\nolimits} \left( {A{e^{ - \alpha A}}} \right)} \over {{\mathop{\rm Tr}\nolimits} \left( {{e^{ - \alpha A}}} \right)}} rises as survivors vanish and serves as an early–warning margin proxy. As above, the one–sided risk that random probes pmiss a surviving r–plane is bounded by e^−kr/d, so (k, d) can be chosen to target a confidence level δ and declare inevitability only when both collapse/peak and the risk budget agree.

Graph neural networks and motif search. GNN tasks often detect motifs (cliques/cycles); Ramsey theory guarantees that small monochromatic subgraphs occur in large graphs regardless of coloring. Instead of scanning exhaustively, run the witnesses on the reduced module induced by the motif’s pair projectors–focusing compute where structure must exist. On parity–preserving (matchgate/Majorana) hardware, these checks map to shallow circuits acting entirely in M₀.

Let G = (V, E) be a large graph and let H = (V_H, E_H) be a small motif (e.g., a k-clique, a c-cycle, or a domain motif) with |VH| = h. For a fixed color c ∈ {R, B} and an injective placement f : V_H ↪ V, define the motif projector at placement f by ΠH,c(f):=∏(u,v)∈EHΠf(u)f(v),c{\Pi _{H,c}}(f): = \prod\limits_{(u,v) \in {E_H}} {\Pi _{f(u)f(v),}^c} where Πijc\Pi _{ij}^c is the degree-(0, 0) pair projector (red or blue) from the graded construction. The disjunction over all placements can be encoded by the central forbidden-motif operator QH,c(V):=∏f:VH↪V injective (I−ΠH,c(f)),{Q_{H,c}}(V): = \prod\limits_{\scriptstyle f:{V_H} \to V \atop \scriptstyle {\rm{ injective }}} {\left( {{\rm{I}} - {\Pi _{H,c}}(f)} \right)} , which equals the identityiffG contains no monochromatic copy of H. In our framework all factors have degree (0, 0) and act on the reduced module M₀, so the existence of a motif is decided by whether Q_H,c leaves any survivor subspace in M₀. This directly leverages the Ramsey guarantee that for sufficiently large |V| certain small monochromatic subgraphs are unavoidable.

Ramsey-guided screening (pre- and post-processing for GNNs). Rather than scanning all (|V|h)\left( \matrix{ |V| \cr h \cr} \right) placements, assemble a basis {ℬ_s} for the span generated by {Π_H,c(f)}_f (or by their complements {I – Π_H,c(f)}_f), sample k i.i.d. isotropic directions v_j in that span (restricted to M₀), and build the witnesses P_lin, P_exp(α) and T(α). If no legal placement remains (i.e. Q_H,c has no survivors), then T(α) collapses as α grows and Tr P_lin exhibits a local peak at the critical scale; conversely, a non-collapse certifies that at least one placement survives. With ambient dimension d = dim M₀ and residual rank r ≥ 1, the probability that k random rank-1 probes pmiss all survivors obeys Eq. (16) so one can pick k≍drln(1/δ)k \asymp {d \over r}\ln (1/\delta ) to achieve a target risk δ. In practice this yields a Ramsey-informed front-end filter: run the witnesses locally (on h-hop ego-nets, or on batches) and trigger exact subgraph-isomorphism or GNN attention only where the witnesses indicate unavoidable structure.

Training-time integration (regularizers and layers). Motif biases can be injected by adding a differentiable penalty that softly forbids Q_H,c: ℒtotal =ℒtask +μTrPexp(H,c)(α){{\cal L}_{{\rm{total }}}} = {{\cal L}_{{\rm{task }}}} + \mu {\mathop{\rm Tr}\nolimits} P_{\exp }^{(H,c)}(\alpha ) or μλL(α),λL(α):=−ddαlogT(α),\mu {{\rm{\lambda }}_L}(\alpha ),\quad {{\rm{\lambda }}_L}(\alpha ): = - {d \over {d\alpha }}\log T(\alpha ), with Pexp(H,c)P_{\exp }^{(H,c)} built from the motif basis {ℬ_s}; decreasing T(α) shrinks the measure of “no-H” assignments, nudging message passing toward motif-consistent representations. A complementary architectural primitive is Ramsey-aware pooling/attention: use per-node (or per-edge) contributions to the trace estimator as scores that gate message aggregation, focusing compute where the witnesses predict imminent motif emergence.

Complexity and deployment. For large |V|, exhaustive motif enumeration is Θ((|V|h))\Theta \left( {\left( \matrix{ |V| \cr h \cr} \right)} \right), while a witness pass costs O(k C_apply) with C_apply the cost to apply a basis element ℬ_s (sparse and local for small H). The error is one-sided and tunable via e^−kr/d; in screening mode we favor high recall (large k/d), then hand off flagged regions to exact methods or to a specialized GNN head.

Majorana/matchgate realization (few-qubit or parity-preserving hardware). All operators above are degree-(0, 0) and commute with total parity, hence on matchgate/Majorana platforms each Πijc\Pi _{ij}^c and their products are even-parity checks realizable by shallow fermionic-Gaussian circuits acting entirely in M₀. The traces T(α) (and Tr P_lin) admit unbiased Hutchinson estimators, and spectral surrogates are accessed via the Hermitian dilation of the rank-k accumulator, enabling few-qubit diagnostics or accelerator kernels that interleave with classical GNN training/inference.

Learning theory: combinatorial capacity (VC). PAC (Probably Approximately Correct) learning is another potential application as in computational learning theory it is used to analyze the learnability of functions. PAC provides a probabilistic approach to understanding how well a machine learning algorithm can generalize from training data to unseen data exploring whether a learning algorithm can find a hypothesis that is both approximately correct and probably correct with respect to a given concept and distribution. With PAC sample complexity scales with VC–dimension that gives a measure of the complexity of a hypothesis space or the power of learning machine. Ramsey–type statements provide complementary unavoidability results: in large instance/hypothesis regimes, certain regular label patterns (e.g., constant/parity–coherent on dense subgraphs) must appear. Encoding “forbidden labelings” as P_m,n and tracking T(α) supplies fast, high–confidence negative certificates (“this configuration is no longer realizable”) with quantitative control via k/d.

Let ℋ ⊆ {–1, +1}^𝒳 be a binary hypothesis class. A finite set S = {x₁, …, x_m} ⊂ 𝒳 is shattered by ℋ if every labeling y ≈ {–1, +1}^m is realized by some h ∈ ℋ, i.e. ∀y ∃h ∈ ℋ with h(x_i) = y_i for all i. The VC-dimension VC(ℋ) is the largest m such that some S of size m is shattered. Writing the growth function Πℋ(m):=max|S|=m| { (h(x1),…,h(xm)):h∈ℋ } |,{\Pi _{\cal H}}(m): = \mathop {\max }\limits_{|S| = m} \left| {\left\{ {\left( {h\left( {{x_1}} \right), \ldots ,h\left( {{x_m}} \right)} \right):h \in {\cal H}} \right\}} \right|, the Sauer–Shelah lemma gives, for d = VC(ℋ) and m ≥ d, Πℋ(m)≤∑i=0d(mi)≤(emd)d,{\Pi _{\cal H}}(m) \le \sum\limits_{i = 0}^d {\left( \matrix{ m \cr i \cr} \right)} \le {\left( {{{em} \over d}} \right)^d}, so the number of distinct labelings realizable on m points grows polynomially once m > d. In PAC learning, these combinatorial bounds control sample complexity. In the realizable case (some h* ∈ ℋ attains zero risk), empirical risk minimization is consistent with m≳1ε(dlog1ε+log1δ)m \mathbin{\lower.3ex\hbox{\buildrel>\over {\smash{\scriptstyle\sim}\vphantom{_x}}}} {1 \over \varepsilon }\left( {d\log {1 \over \varepsilon } + \log {1 \over \delta }} \right) examples to achieve excess error ≤ ε with probability ≥ 1 – δ; in the agnostic case the dependence becomes m≳1ε2(d+log1δ)m \mathbin{\lower.3ex\hbox{\buildrel>\over {\smash{\scriptstyle\sim}\vphantom{_x}}}} {1 \over {{\varepsilon ^2}}}\left( {d + \log {1 \over \delta }} \right). Canonical examples: thresholds on ℝ have VC = 1; intervals on ℝ have VC = 2; axis-aligned rectangles in ℝ^d have VC = 2d; affine halfspaces in ℝ^d have VC = d+1.

Ramsey overlay and “unavoidability.” Ramsey theory adds a complementary, worst-case inevitability perspective: on sufficiently large instance sets, certain structured label patterns must occur. In our algebraic framework, a forbidden configuration (e.g. “no monochromatic K_m in red, none of size K_n in blue”) is encoded by the central projector P_m,n acting in the charge-zero module M₀. If P_m,n has no surviving support at size v, then no hypothesis consistent with those constraints can realize the corresponding label patterns on v examples—an unavoidability barrier. Operationally, we monitor T(α) and the product witness P_lin; collapse of T(α) together with a peak of Tr P_lin certifies that all labelings compatible with the constraint class have vanished at that scale, yielding a fast negative certificate (“this configuration is no longer realizable”).

From VC to Ramsey-constrained capacity. Let ℋ_m,n (v) denote the labelings of a v-point sample realizable by hypotheses that avoid the Ramsey-forbidden substructures encoded by P_m,n. By Ramsey’s principle, once v ≥ R(m, n) the set ℋ_m,n (v) is empty; hence the growth function of the constrained class satisfies Π_ℋm,n(v) = 0 for all v ≥ R(m, n). Thus the effective VC-dimension of ℋ_m,n is at most R(m, n)–1, and in practice can be (much) smaller due to additional algebraic symmetries. Our spectral witnesses make this transition detectable: when T(α) collapses at a given v, it implies Π_ℋm,n(v) = 0 under the modeling assumptions, delivering a data-driven ceiling on combinatorial capacity for the constrained hypothesis class.

Quantitative control via random projectors. Let d = dim M₀ and suppose the surviving feasible subspace (if any) has rank r ≥ 1. Drawing k isotropic rank-1 tests vjvj⊤{v_j}v_j^ \top , the probability to pmiss all survivors obeys Eq. (16) drives the false-negative risk below I. In practice: (i) choose d as large as possible without increasing the data–qubit count on hardware (e.g., d ≤ 24, 32, 48 map to 5 or 6 qubits); (ii) set a baseline pair (k, α) (e.g., (100, 20)) and a high–resolution pair (e.g., (400, 40)) to cross–validate decisions; (iii) declare a scale v critical when T(α) collapses, Tr P_lin peaks, and a spectral surrogate (e.g. the dilation norm ρ(H) = ∥A∥₂) is locally extremal under the same seeds. For example, with d = 24, r = 1, and target δ = 10⁻⁶, it suffices to use k ≤ 24ln(10⁶) ≈ 332; at (k,a) = (400, 40) the bound already yields Pr[pmiss] ≲ 5.7 × 10⁻⁸. Reporting (k, d, α) together with λ_L(α) and the explicit e^−kr/d risk converts Ramsey–style inevitability into a tunable, high–confidence negative certificate (“this configuration is no longer realizable”), complementing VC/sample–complexity upper bounds on the number of realizable labelings, what can be labeled or learned.