FrontierMath open problem, verbatim: “Improve the exponent in the upper bound that degree has over sensitivity.” Assessed against a proposal to take the mean-field limit of the hypercube and replace an SOS certificate with an HJB viscosity solution.
Nothing on this page is claimed, certified, enclosed or proved. No kernel, no certificate, no falsifier, no ledger record. It assesses a direction and kills it, with the reason stated so the kill can itself be attacked.
Two independent structural objections, either of which is fatal on its own. The proposal
targets a bottleneck that is not the bottleneck, and its central mechanism dissolves the only object
the problem is about. Detail below. Under SCORING.json's rule — structural kills
survive a rescoring, occupancy kills do not — this one stays dead, in the same category as
rotor-trajectory.
The proposal states the obstacle as: “bounding degree against sensitivity typically requires constructing an explicit Sum-of-Squares certificate via Semidefinite Programming … without an SDP solver, generating exact rational certificates is blocked.”
The relationship was settled in 2019 and not by an SDP.
Huang proved the Sensitivity Conjecture — arXiv:1907.00847, “Induced
subgraphs of hypercubes and a proof of the Sensitivity Conjecture” — giving
deg(f) ≤ s(f)². The proof is a short spectral argument: a signed adjacency matrix
of the hypercube with eigenvalues ±√n, plus Cauchy interlacing. There is no
semidefinite program in it, and there is no SOS certificate to replace. A method whose entire
selling point is “bypasses SDP” bypasses something that is not in the way.
Sensitivity s(f) is defined by counting, at a specific input
x ∈ {0,1}ⁿ, how many single-coordinate flips change the value of
f. It is a maximum over points of a count over discrete neighbours.
In a mean-field limit there are no coordinates to flip. Passing to a
continuous measure space as n → ∞ replaces the hypercube's vertex-and-edge
structure with a density. The Hamming neighbour relation — the only structure
s(f) is defined against — is precisely what is quotiented away. The quantity the
problem asks about is not merely hard to compute in the limit; it is not definable there.
Worse for the proposal's actual goal. Improving an exponent in this area is done by extremal constructions at finite n — exhibiting specific functions whose degree is large and sensitivity small. Those constructions live entirely in the finite combinatorial structure the limit erases. The mechanism deletes the search space it was brought in to search.
FrontierMath's public listing gives only a one-line summary per problem; the individual problem page and its verifier were not readable in this pass. That leaves one requisite genuinely open, and it is the one that decides what the problem even asks.
Is the exponent 2 known to be tight? The scoping search returned a statement that it cannot be
improved below 2, attributed to a variant of the Chung–Füredi–Graham–Seymour example.
If that refers to deg versus s, then the exponent is optimal and the open
problem must concern the constant, or a neighbouring pair such as approximate degree
(arXiv:2010.12629 treats degree vs approximate degree and the quantum implications of
Huang's theorem). The search result may have conflated the two pairs. This report does not resolve
it and does not assert either reading.
Recording it rather than picking one is deliberate. The most expensive documented error in this tree came from two internal records disagreeing about one paper — both right, about different versions — and being repeated outward. An unresolved requisite named as unresolved costs nothing; a guessed one costs a correction in public.
Not reached. Novelty is not the binding constraint when the mechanism cannot represent the quantity. There is nothing to score.
LOW, and the one salvage is not recommended. A zero-dependency exact-rational verifier that
checks Huang's interlacing bound on explicit small-n functions would be re-runnable and
genuinely checkable — the shape this tree ships. But it verifies a short published proof on tiny
instances, which is a teaching exercise, not a contribution, and it does nothing at all for the open
exponent. Named so it is on the record as considered and declined, not overlooked.
A structural kill should still say what would break it, or it is just an opinion with a badge.
One thing would do it: a formulation in which sensitivity is recovered
exactly at finite n as the value of a variational problem — not approximated
in a limit, and not bounded above by one. If s(f) were the exact optimum of a finite
optimisation whose dual object this tree can enclose, both objections fall at once: the discrete
neighbour structure would be retained, and the certificate would have something to certify.
No such formulation is known to this report, and it is not obvious one exists. But it is decidable, someone else may already have it, and it is the only door left open.
Identifiers and titles confirmed at search level on 2026-07-31. No paper body was read; no MathSciNet, zbMATH or Scopus pass; the FrontierMath problem page itself returned only a one-line summary. This pass tested premises, not the mathematics. Anything repeated outward is citation-checked at source first.
| Reference | Used here for |
|---|---|
Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, arXiv:1907.00847 | Objection 1: the bound is deg(f) ≤ s(f)² and the proof is spectral, not an SDP |
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem, arXiv:2010.12629 | The open requisite: the neighbouring pair the search result may have conflated |
| Chung–Füredi–Graham–Seymour example (variant) | Cited by the search result as the tightness witness. Not verified at source. |