# Difficulty report - sos-certificate

Consolidated record of the measured difficulty evidence for this task. The
agent-trial data comes from SUBMISSION_SPEC.md section 5 and this task's own
Codex self-test record; the non-agent baselines come from `calibration.md`,
`baseline_outputs/baseline_report.json` and `build/calibration_sweep.json`.

## Summary

| evidence | shots | scores | result |
|---|---|---|---|
| Codex (GPT-5-based coding agent), local execution | 3 | 0.0, 0.0, 0.0 | 0/3 |

- Measured agent pass rate: **0 of 3 scored shots**. No shots were aborted or
  excluded, and no other model family was run on this task.
- ALE tier chip, taken from SUBMISSION_SPEC.md section 5: **`10-20%`**.
- 0/3 is an **upper bound from a three-shot sample, not a claim of a
  sub-1-percent pass rate**. Three shots cannot resolve a rate below roughly
  20 percent: a task a frontier agent clears 20 percent of the time still
  returns 0/3 about half the time. The `<1% (last-exam)` chip is therefore
  not claimed anywhere in this package.

## Trial protocol

- **Harness and isolation.** Codex, a GPT-5-based coding agent, run locally
  from an isolated copy of the task under `/private/tmp/agent_selftest`, with
  the solution, the reference output, the baseline output and the
  build/oracle artifacts excluded from the copy. The hidden reference was
  passed to the evaluator only after the submissions had been produced.
- **Shots.** Three, run 2026-08-08.
- **Grading.** Every shot was graded by the shipped exact verifier
  (`sos_common.grade_multi_submission`, reached through
  `tb-science/task/tests/test_outputs.py` or
  `agents-last-exam/upload/evaluate.py`). No hand-scoring and no partial
  credit outside the grader's own 0.0 / 0.5 / 1.0 scale.
- **Budget.** The task's agent budget is 7200 s
  (`tb-science/task/task.toml`, `[agent] timeout_sec = 7200`); both problem
  statements quote a 2 hour wall-clock budget on 4 vCPUs / 8 GB RAM. The
  verifier timeout is 600 s, against a measured verifier runtime well under
  1 s.
- **Not run.** No other model family or harness was evaluated on this task.

## Agent trial

Codex (GPT-5-based coding agent), 3 shots:

| shot | score |
|---|---|
| 1 | 0.0 |
| 2 | 0.0 |
| 3 | 0.0 |

Result: 0/3. What the attempts did, from the self-test record: the agent
produced naive rational matrix certificates, which failed immediately on the
exact monomial identity checks for all three instances. Because the verifier
decides acceptance in exact integer arithmetic, there is no tolerance buffer
that would let an approximate numerical SOS output through - a Gram matrix
that is right to twelve digits still violates the integer equations and
scores 0.0, exactly as measured for the non-agent baseline A below. The
self-test rated this task the hardest in its batch, on the grounds that a
passing submission requires exact rational positive-definite SOS certificates
*plus* tight rational witnesses for all three instances.

Wall times per shot were not recorded.

## Non-agent baselines

Measured naive-method failures, from `calibration.md` and
`baseline_outputs/baseline_report.json` (single-instance run, 8.84 s wall):

| attempt | measured result | score |
|---|---|---|
| A. round the optimal Gram matrix, no identity repair | 129 of 462 monomial equations violated | 0.0 |
| B. round + exact integer identity repair, at gamma* | 0 identity violations, exactly PD | 1.0 |
| C. retreat far (1e-2) to gain margin | valid certificate, bound misses the target | 0.5 |

Baseline A ran at den = 2^19 with numeric margin 2.2237556411934517e-08 and
gamma = -13.816625595092773; the rounded matrix is positive definite and
still scores 0.0, because the polynomial identity is broken. Baseline C
certified gamma = -13.826623916625977, a valid proof of a bound that misses
the target. A valid certificate submitted without a usable witness likewise
scores 0.5 rather than 1.0 (verified, `calibration.md`).

Denominator sweep (`calibration.md`, backed by
`build/calibration_sweep.json`; the repair step doubles the denominator, so a
sweep row recorded at 2^k verifies at 2^(k+1)):

| retreat from gamma* | margin | smallest denominator that still verifies |
|---|---|---|
| 0 | 2.4e-11 | 2^25 |
| 1e-6 | 4.7e-8 | 2^21 |
| 1e-5 | 5.0e-7 | 2^17 |
| 1e-3 | 6.4e-5 | 2^17 |

The shipped cap is den <= 2^20, so at the SOS optimum the degenerate route -
round on an arbitrarily fine grid - is closed by 5 bits.

Reference oracle, for contrast: 120.8 s for all three instances
(`build/solve_all.log`, `reference_outputs/solver_report_multi.json`),
certifying gamma_p1 = -13.8166275024, gamma_p2 = -86.6814155579,
gamma_p3 = -15.8317604065 with den = 2^20 and enclosure widths 2.65e-6,
2.58e-6 and 3.74e-6 against a permitted 1e-5.

## What makes it hard

Measured failure modes, not adjectives:

1. **No SDP solver in the allowed stack.** The environment is Python 3.11
   with numpy 1.26.4 and scipy 1.11.4 only, and SciPy has no semidefinite
   programming solver. The affine family of Gram matrices satisfying the
   identity has rank 462 with a 1134-dimensional null space (`calibration.md`;
   oracle log line "affine system rank 462, null-space dim 1134"), so the
   semidefinite step has to be written from scratch over 1134 free
   parameters.
2. **Floating point is worthless at the finish line.** Rounding the Gram
   matrix without the exact integer repair violates 129 of the 462 identity
   equations and scores 0.0 (baseline A) - and this is precisely the failure
   the Codex shots hit.
3. **A parity obstruction in the repair.** The repair adjusts one
   representative entry of Q per monomial; for an off-diagonal representative
   (i, j) the entry appears twice in a symmetric matrix, so it moves that
   monomial's coefficient by 2*delta and odd residuals are unreachable. The
   fix is to double den, G and Q, which is mathematically a no-op. The build
   log `build/sos.log` shows this obstruction being hit repeatedly ("parity
   obstruction in the repair step; trying next setting").
4. **The denominator cap forces a real trade-off.** With den <= 2^20 a
   certificate cannot be rounded at the optimum: the sweep above puts the
   smallest workable denominator at retreat 0 at 2^25. Tightness of gamma has
   to be traded deliberately against the spectral margin that survives
   rounding.
5. **The answer is two-sided.** Full credit needs both an SOS lower bound and
   a rational witness point with 0 <= p(x0) - gamma <= 1e-5, so global
   optimisation of a degree-6 polynomial in 5 variables sits alongside the
   semidefinite work. A solver that does only one of the two scores 0.5.
6. **Three structurally different instances, min-over-instances scoring.**
   `grade_multi_submission` returns 1.0 only when p1, p2 and p3 all score
   1.0, so a pipeline that gets lucky on one instance does not pass.

## Limits of this evidence

- **Sample size: three shots.** 0/3 bounds the pass rate from above; it does
  not establish that the rate is near zero. A task cleared 20 percent of the
  time returns 0/3 roughly half the time, so this evidence cannot distinguish
  "very hard" from "impossible", and the `<1% (last-exam)` chip is not
  claimed. The chip used everywhere in this package is `10-20%`.
- **One model family.** Only Codex (GPT-5-based) was run. Nothing is known
  from measurement about how other frontier families or harnesses behave on
  this task, and the benchmark's own evaluation models and harness may differ
  from ours.
- **One failure mode observed.** All three shots died at the same place - the
  exact monomial identity check - so we have no measurement of whether an
  agent that clears that hurdle would then be stopped by the denominator cap,
  the parity obstruction or the witness requirement.
- **No timing data.** Per-shot wall times were not recorded, so we cannot say
  whether the failures were budget-limited or method-limited.
- **Non-agent baselines cover one instance.** The 129/462 figure, the
  retreat/denominator sweep and the 8.84 s baseline run were measured on the
  single-instance (p1) version and have not been re-measured on p2 and p3.
  The three-instance oracle run (120.8 s) is the only end-to-end measurement
  covering all three.
- **Verifier soundness is not in question.** The acceptance decision contains
  no floating point at all, so difficulty here is a property of the task, not
  of a tolerance that could be tuned.

## Discrepancies found

Recorded per the package rule that `calibration.md` outranks the (now
deleted) `tb-science/proposal-airtable.md`; where the shipped grader code
disagrees with prose, the grader is what actually runs and is what the form
documents quote.

1. **Acceptance thresholds.** `calibration.md` states full credit at
   gamma >= -13.816635 and partial at gamma >= -13.9. The shipped grader
   `sos_common.py` uses per-instance targets p1 >= -13.816645,
   p2 >= -86.681433, p3 >= -15.831777 (each gamma*_k - 2e-5) and partials
   p1 >= -13.917, p2 >= -86.781, p3 >= -15.932 (each gamma*_k - 0.1). The
   `calibration.md` values are the earlier single-instance calibration; the
   form documents quote the grader.
2. **gamma* for p1.** `calibration.md` records gamma* = -13.8166248568
   (single-instance bisection, `reference_outputs/solver_report.json`); the
   three-instance oracle records gamma*_p1 = -13.8166248571
   (`reference_outputs/solver_report_multi.json`, `build/solve_all.log`), and
   `sos_common.py`'s comment repeats that value. The difference, 3e-10, is
   inside the bisection tolerance.
3. **Oracle runtime.** `calibration.md` gives 15 s (single instance;
   `solver_report.json` wall_seconds 15.087). The deleted proposal claimed
   "15 s per polynomial (~1 min total)", but the measured three-instance run
   is **120.8 s total** (`solver_report_multi.json` wall_seconds 120.836;
   `build/solve_all.log`: p1 at 33.4 s, p2 at 85.5 s, p3 at 120.8 s
   cumulative). The form documents use 120.8 s.
4. **Verifier runtime.** `calibration.md` and `task.toml` say about 2 s;
   `README.md` said 0.14 s. Re-measured 2026-08-08 against the shipped
   reference solution: pytest 0.16 s, `evaluate.py` 0.2 s. The form documents
   say "under 1 s" and quote the measured values.
5. **Expert time.** The deleted proposal said about 8 to 10 hours;
   `task.toml` records `expert_time_estimate_hours = 8`. Both are estimates,
   not measurements, and are labelled as estimates in the form document.
6. **ALE form vs grader (fixed here).** The previous
   `agents-last-exam/submission-form.md` described a single-polynomial task
   (short name `exact_sos_certificate_1`, `input/polynomial.json`, one
   certificate in `solution.json`, scored against -13.816635 / -13.9), while
   `upload/evaluate.py` grades three polynomials from
   `input/polynomials.json` with per-instance certificates and witnesses and
   min-over-instances scoring, and `upload/problem_spec.md` is the
   three-instance version. The form has been rewritten to match the grader
   and the stale single-instance upload files have been deleted.
7. **Reference output filename.** `evaluate.py` reads `solution.json` from
   the agent's output directory, while the shipped reference output is named
   `reference_outputs/solution_multi.json`. Nothing is broken - it is a
   reference copy, not an agent output - but the ALE form now states
   explicitly that this file is the expected content of
   `output/solution.json`.
8. **Harbor solution path vs verifier (found, then fixed).**
   `tb-science/task/solution/solve.sh` ran the single-instance
   `reference_solver.py`, which read `/app/polynomial.json` - a file the
   Dockerfile does not copy into the image - and wrote a certificate with no
   p1/p2/p3 keys and no witness, while `tests/test_outputs.py` grades three
   instances from `/app/solution.json`; the three-instance driver
   `solution/solve_all.py` wrote `solution_multi.json`. As shipped, the
   solution could not pass its own verifier. `solve.sh` now runs
   `solve_all.py` against `/app`, `solve_all.py` writes `/app/solution.json`
   in the verifier's schema and self-checks it with `grade_multi_submission`,
   and the dead single-instance driver was removed from the task copy of
   `reference_solver.py`. Measured after the fix (2026-08-08, dedicated
   scratch directory, only the files the Dockerfile copies): solution runs in
   118.9 s with self-check 1.0 on all three instances, and the shipped
   verifier passes it in 0.17 s with 1.0 per instance.
9. **Instance reproducibility (found, then fixed).**
   `build/generate_instance.py` previously reproduced only p1;
   no checked-in script generated p2 and p3. The generator now builds all
   three from the same construction - p1 (seed 20260821, top form
   3*sum x_i^6, lower-order coefficients in [-3, 3]), p2 (seed 20260822,
   top 1, [-5, 5]), p3 (seed 20260823, top 6, [-2, 2]) - and its output was
   verified byte-identical to the shipped `polynomials.json`,
   `polynomial.json` and `basis.json` with `cmp`. Its docstring said "4
   variables" where `sos_common.N_VARS` is 5; fixed.
10. **Trial evidence scope.** Earlier in-house trials by the agent lineage
   that built this task are excluded from every document in this package, per
   SUBMISSION_SPEC.md section 5; the Codex self-test is the only agent-trial
   evidence cited.