# Verification report — OWR-16766-004 (Kadu–van Leeuwen Conjecture 1 on dual binary tomography)

Verification date: 2026-10-02.

**Verdict.** Conjecture 1 of Kadu and van Leeuwen is false for the dual approach as they define and test it, in the following precise sense.
In the noiseless case the exact optimum of their dual problem is ν* = Aᵀμ* = 0 for every instance, so the conjecture is a statement about
the numerically computed solution; the only pixels such a solution can certify are those fixed over the solution set Q of the box relaxation.
For rows, columns and diagonals there is a 5×5 image with six ones that has a unique binary solution while Q is a segment with a half-integral
endpoint and only 14 of 25 pixels are fixed (so part (i) fails, for every n ≥ 5 by padding); with four directions the first failure is at 6×6.
Part (ii) already fails inside the range tested by the authors: 448 of the 65536 images of size 4×4 (112 projection classes) with rows, columns and
diagonals. Real solvers (Clarabel, ECOS, PIQP and others behind CVXPY) do not return the 5×5 image in any of 61 runs. The note is unrefereed.
It does not question the identifiability of binary images; the unique solution is unique.
Two independent AI-assisted verification runs checked the claims with separate code; the second also ran the solvers with new scripts and re-ran this package from its source archive.

## Statement checked
- **Primary sources.**
  - A. Kadu (joint with T. van Leeuwen), "A convex formulation for binary tomography", Oberwolfach Reports 16 (2019), no. 1, Report 4/2019,
    abstract pp. 256–259, Conjecture 1 on p. 258, DOI 10.4171/OWR/2019/4. Crossref lists the DOI under the whole report
    "Tomographic Inverse Problems: Theory and Applications" (pp. 209–303; organizers M. Burger, B. Hahn, E. T. Quinto; issued 2020-02-26).
    The report text was read; it fixes neither a solver nor a threshold, and ends with the open questions on strong duality, a proof of the conjecture, and more than two grey levels.
  - A. Kadu, T. van Leeuwen, IEEE Trans. Comput. Imaging 6 (2020) 1–11, DOI 10.1109/TCI.2019.2898333, arXiv:1807.09196 (v3). Section IV: the dual problem (13)
    is solved with CVX, entries of the numerically computed dual solution below 1e-9 are set to zero, the output sign(Aᵀμ) lies in {−1,0,1}; Table I
    (n = 2,3,4; m = 2,3,4); starred cells (4,2): 58541/58634 and (4,3): 10813/11264 are attributed to CVX. LaTeX source read.
  - The authors' public script `test_tomo_cvx.m` (read anonymously): dependent rows removed (licols), A scaled by normest, `cvx_precision high`,
    solver Gurobi or SDPT3, threshold 1e-10 on Aᵀp.
  - Fishburn, Schwander, Shepp, Vanderbei, Discrete Appl. Math. 75 (1997) 39–61, DOI 10.1016/S0166-218X(96)00083-2 (copy on a co-author's web page): sets of uniqueness versus
    additive sets, Theorem 3 (an 11-point nonadditive set of uniqueness for the directions (1,0),(0,1),(1,1)), and the remark that interior-point methods return the centre of the optimal face.
- **Corpus record.** ulamai/UnsolvedMath, OWR-16766-004 (status `open`), with the duplicates OWR-16766-002, -003 and the conjecture part of -005.

## Readings
| Reading | Refuted? | Witness |
|---|---|---|
| literal: output sign(Aᵀμ*) of the exact optimum | yes, trivially (Aᵀμ* = 0 for every noiseless instance, even 2×2); not the claim made | Lemma 2.1 |
| fixed-pixel form (i′): unique ⟹ Q = {x} | yes | 5×5 image, six ones; all n ≥ 5 |
| fixed-pixel form (ii′): F = I | yes | 4×4, 112 classes, 448 images (rows, columns, diagonals) |
| numerical reading, interior-point codes (thresholded sign) | yes | Clarabel, ECOS, PIQP: the pattern of the fixed pixels (11 zeros) or a full sign pattern with a wrong sign (at (1,1)); 50- and 80-digit central paths never return the image |
| numerical reading, operator-splitting and active-set codes | yes | SCS, OSQP, HiGHS, DAQP: zeros or noise; the exact optimum is 0 |
| two directions, any grid | holds (fixed-pixel form) | totally unimodular, Q = conv S |
| 5×5, four directions; n ≤ 4, part (i) | holds (fixed-pixel form) | ternary circuits; exhaustive |

## Results in the paper
- **Lemma 2.1.** For y = Az with z in the box, the minimum of problem (13) is ½‖y‖², attained exactly on ker Aᵀ; hence Aᵀμ* = 0.
- **Proposition 2.2.** The optimal set of the box relaxation is Q(y); every z ∈ Q(y) witnesses the optimality of μ* = 0, so the optimality system can imply a value at a pixel only if the pixel is fixed.
- **Lemma 3.1.** The log-barrier central path of the dual QP (form (13); for full row rank, form (14)) is described by z(τ), the minimiser of ½‖Az−y‖² − τ Σ log(1−z_p²): ν_p = 2τ z_p/(1−z_p²) and AA†μ = y − Az (μ = y − Az for full row rank). Proved.
- **Proposition 3.2 (cited).** Limit at the analytic centre of Q, order √τ on fixed pixels, order τ on the others (Sonnevend, McLinden, Güler–Ye, Monteiro–Zhou, Monteiro–Tsuchiya; Goldman–Tucker for strict complementarity; the centre property for tomography LPs is stated by Fishburn et al.). Not re-proved; tested numerically.
- **Theorem 4.1.** Two directions: A is the incidence matrix of a bipartite graph, hence totally unimodular, Q = conv S, F = I.
- **Theorem 4.2.** The 5×5 example: unique solution (proof by a case split on one pixel); Q = {x + s c : 0 ≤ s ≤ 1} (integer potential f(i,j) = ρ_i + γ_j + δ_{j−i} certifies that the tangent cone is the ray R₊c);
  14 fixed pixels; analytic centre s* = (45 − √89)/44 with pixel (1,1) = (√89 − 23)/22 ≈ −0.617; minimum-norm point s = 6/7 with pixel (1,1) = −5/7.
- **Corollary 4.3.** Padding to every n ≥ 5 (n² − 11 fixed pixels).
- **Theorem 4.5.** Four directions: 6×6 example (nine ones, unique, Q a segment, 18 of 36 fixed), padding; 5×5 with four directions has 15 ternary circuits, so no counterexample.
- **Theorem 4.6.** n = 4, rows, columns, diagonals: 112 failing classes, 448 images, each class with 4 solutions; 64 classes with exactly one common non-fixed pixel, 48 with two. All 11 direction sets, n ≤ 4.
- **Theorem 4.7.** If all circuits of ker A are ternary, both halves hold in the fixed-pixel form (Rockafellar's conformal decomposition).
- **Counts.** 5×5: 1536 (rows, columns, diagonals; fewest ones 6) and 8064 (rows, diagonals, anti-diagonals; fewest ones 5); 6×6, four directions: 463872, fewest ones 9 (from the circuit/SAT procedure, reproduced by a second, separately written implementation; not an exhaustive scan of the 2³⁶ images).

## Computations (scripts and outputs in reproducibility/)
- **Exact** (`solvers/exact_core.py`): brute force over all 2²⁵ images and a depth-first search (one solution); exact integer and rational checks of Ac = 0, the endpoint, the potential f; kernel of A on supp(c) of dimension 1;
  LP cross-check of the 14 fixed pixels; closed forms with sympy; mirror image; padding to n = 6,7,8; the 6×6 example. `solvers/part2_example.py`: the 4×4 example with an exact rational point of Q.
- **Exhaustive classifications.** `solvers/classes_n.py` (n = 2,3,4); `author_scripts/small_n_exhaustive.py` (all 11 direction sets, n ≤ 4); `solvers/circuits_exact.py` (exact circuits).
- **Independent exhaustive counts.** `solvers/count_5x5_exhaustive_lp.py`: all 2²⁵ images, unique-solution detection by line-sum keys and one LP per orbit representative: 1536 and 8064 counterexamples (distribution by number of ones symmetric under complementation).
  `solvers/count_by_ones.py`: all 6×6 images with at most nine ones, four directions: none with ≤ 8 ones, exactly 56 with nine, the nine-ones images of the circuit/SAT list (`author_scripts/kernel_sat.py`, which gives 463872 in total).
- **Real solvers** (CVXPY 1.9.3): `solvers/real_solvers_5x5.py` (8 solvers, 68 runs, 61 returned a solution; the image is never returned under thresholds 1e-9, 1e-10 or none);
  `solvers/real_solvers_table1.py` (Table I of the TCI paper; Clarabel at tolerance 1e-10 reproduces every cell except (4,2): 58634/58634 and (4,3): 10816/11264; the number of failures at (4,3) is never below 448; at (4,2) failures depend on solver and tolerance: 0 at Clarabel 1e-10, 944 at its default);
  `solvers/real_solvers_n4_failing.py` (112 classes, 15 settings: the intersection is returned by no interior-point or active-set setting; one non-converged OSQP run matched it once);
  `solvers/central_path_mp.py` (80 digits, τ = 10⁰ … 10⁻⁴⁰: z₍₁,₁₎(τ) < 0 for all τ; limit −0.616637 = (√89 − 23)/22; |ν|/τ → 1.99 on the free pixel (1,1); |ν|/√τ → 0.8112 on fixed pixels; the fixed-pixel pattern appears exactly for 3.2e-18 ≤ τ ≤ 3.2e-10 at threshold 1e-9).
- **Own earlier code** (`author_scripts/`): Algorithm 2 of the paper and the smooth L-BFGS variant on the 5×5 image (wrong sign at (1,1); re-run reproduces the recorded output), Table I replication with an own interior-point code, MILP search.
- **Second independent run** (`independent_run_2/`, see its README): new exhaustive and exact checks (all 11 direction sets for n ≤ 4; counts 1536 and 8064 by line-sum keys and circuits; 5.57 million minors; 6×6 total 463872 by a separate SAT enumeration), the central path in 50 digits, an own primal–dual interior-point code, Algorithm 2 of the paper, own cvxpy runs reproducing Tables 1–3 of the note, the example of Fishburn et al. against the list printed there, and a re-run of the whole package from `source.zip` (all recorded outputs identical up to timings).
- **Limits.** MATLAB, CVX, SDPT3 and Gurobi were not available and were not run. A crossover (basic) solution returns μ = 0 and hence an all-zero output; this was not tested with Gurobi.

## Independent verification runs (AI-assisted)
Two independent verification runs wrote separate code from the problem statement: run 1 (`independent_runs/`) and run 2 (`independent_run_2/`, 2026-10-02). Both are AI-assisted verification runs, not peer review.

**Run 1.** Verdicts:

| Item | Verdict |
|---|---|
| Statement fidelity (OWR text, TCI paper, direction sets, Table I denominators) | CONFIRMED |
| Exact computations (2²⁵ search, fixed pixels, segment and endpoint, 6×6 example by DFS and SAT, unimodular kernel, 112 classes and 64/48 split) | CONFIRMED |
| Answer as intended | CONFIRMED with scoping (ν* = 0; numerical reading) |
| Real-solver confirmation | REQUIRED, then done with CVXPY (CVX/SDPT3/Gurobi not available) |
| Presentation | six required fixes, all applied (see below) |

Required fixes of run 1 and how they were applied:
1. Lead with the scoping (ν* = 0; numerical reading; only fixed pixels can be certified) — abstract, Section 1, Lemma 2.1, Proposition 2.2.
2. Confirm on a real solver stack, with and without crossover/high precision — Section 5 (Clarabel, ECOS, SCS, OSQP with and without polishing, HiGHS, CVXOPT, PIQP, DAQP; tolerances 1e-6 … 1e-14; forms (13) and (14); scaled and unscaled).
3. Prove or cite the central-path facts — Lemma 3.1 proved; Proposition 3.2 cited and tested (80-digit computation).
4. Fix imprecisions — 64/48 split of the failing classes; the half-integral point is an endpoint of Q; 451 versus 448 and the 93 failures at (4,2) are numerical.
5. Soften the novelty statement and add a literature check — see below; the published example of Fishburn et al. was found and is cited.
6. Define "the dual approach", the direction sets and the numerical reading — Sections 1 and 2.

**Run 2.** Verdicts (no fatal problem; the result is correct as stated; fifteen small corrections):

| Item | Verdict |
|---|---|
| Prior art (decisive point) | The overlap with Fishburn–Schwander–Shepp–Vanderbei (1997, read in full) is the phenomenon (unique but fractional) and the centre principle, not a refutation of the conjecture; 13 (OpenAlex) and 15 (Semantic Scholar) citing works examined, none addresses Conjecture 1; Fishburn–Shepp (1999) and Brunetti–Dulio–Peri (2013, 2014) on non-additive sets of uniqueness could not be accessed and are now cited as unread; claims restricted to the new parts |
| Statement fidelity | CONFIRMED again from the sources (OWR report pp. 256–259, Conjecture 1 on p. 258; TCI Section IV and equations (13), (14); the authors' script; the nine denominators of Table I recomputed) |
| Exact computations with new code | CONFIRMED: 5×5 example (2²⁵ search, potential, segment, closed forms, padding); n ≤ 4 for all eleven direction sets (112 classes, 448 images, 64/48, Table I denominators); 1536 and 8064 by a second exhaustive method; 6×6 example by DFS, SAT and MILP; unimodular kernel; two directions totally unimodular (5.57 million minors); the printed 4×4 example |
| 463872 | REPRODUCED by a separately written circuit/SAT implementation (29568 orbits; 56 with nine ones, none fewer; the images with ≤ 13 ones equal the earlier list); not an exhaustive scan — the provenance is now stated in the note |
| Real solvers | CONFIRMED with new scripts: 16 settings on the 5×5 image, Table I replication (Clarabel, ECOS, PIQP), the 112 classes; the recorded run table re-evaluated (68 runs, 61 with a solution, no run returns the image) |
| Central path and other codes | The 50-digit table is reproduced; general interior-point codes (own Mehrotra code, HiGHS) select other points of Q but never the image; Algorithm 2 as printed lacks a step size |
| Package re-run | `reproducibility/solvers` and `author_scripts` re-run from an extracted copy of `source.zip`, and `independent_run_2/run_all.sh` re-run completely from an extracted copy: all recorded outputs identical up to timings and the order of unordered items |
| References | all entries checked; no wrong entry; six entries added |

Corrections made after run 2: (1) Algorithm 2 — the printed pseudo-code omits the step size γ in front of A, and the limit depends slightly on the scaling of the rows; (2) Lemma 3.1 now covers general A (form (13)) and full row rank (form (14)); (3) "follow the central path" now says approximately, with other interior-point codes mentioned;
(4) the coordinates of the Fishburn et al. set are confirmed by their 13 printed triples (the count 13 alone is not a sufficient check); (5) the provenance of 463872 is stated; (6) software versions and citations for PIQP, DAQP and CVXOPT; (7) credit to Fishburn–Shepp and Brunetti–Dulio–Peri, small instances new "as far as we could check"; (8) the sentence on Kuske–Swoboda–Petra made neutral;
(9) the verification paragraph rewritten in house style; (10) scope remark on the polynomially solvable subclass; (11) the abstract and Section 5.1 describe the solver outputs more precisely and say that the authors' MATLAB stack was not used; (12) "assuming Proposition 3.2" added in Section 6; (13) the Kadu (2019) entry gives the whole-report title and page range; (14) this package updated; (15) reference counts updated.

## Relation to the literature, novelty and scope
- **Prior art for the phenomenon.** Fishburn, Schwander, Shepp and Vanderbei (1997) prove that a set is unique among fuzzy sets iff it is additive (Theorem 2), that nonadditive sets of uniqueness exist (Theorem 3: an 11-point set in a 49×70 box
  for the directions (1,0),(0,1),(1,1)), that for two directions uniqueness and additivity coincide (Theorem 4), and note that interior-point methods return the centre of the face of optimality. The 11-point set was re-checked here
  (`solvers/fssv97_example.py`: 13 extra points as stated, one binary solution on the 24-point support, 23 of 24 support points not fixed over Q); in an n×n grid with n ≥ 71 it is a counterexample to part (i′).
  So the unique-but-fractional phenomenon is published and the failure of part (i) for large n follows from it; the note says so. The paper does not mention Conjecture 1 (it is 22 years older).
- **What is new here (modest).** The explicit refutation of this published conjecture; the small instances (six ones on 5×5; first failures at n = 5 and n = 6; none at n ≤ 4 for part (i)); the failure of part (ii) at n = 4, inside the tested range, which accounts for the starred entry (4,3) of Table I up to 3 images;
  the exact reading of the dual optimum; the real-solver confirmation.
- **Searches.** arXiv API, Crossref, OpenAlex, zbMATH, Semantic Scholar (metadata, citations and citation contexts), and three web searches in all (one while the note was prepared, one in each verification run); all anonymous. No published refutation of Conjecture 1 and no later work addressing it were found; the works citing the TCI paper (13 in OpenAlex, 15 in Semantic Scholar, October 2026) concern applications and variants.
  Not read: Weber–Schnörr–Hornegger (2003), Gardner–Gritzmann–Prangenberg (1999), Hajdu–Tijdeman (2001; only the zbMATH review), Fishburn–Shepp (1999 survey chapter), Brunetti–Dulio–Peri (2013, 2014; the publisher pages were not accessible). Fishburn–Shepp and Brunetti–Dulio–Peri treat non-additive sets of uniqueness, so the small instances of this note are new only as far as we could check. Kuske–Swoboda–Petra (2017) was read in the arXiv version; it does not discuss sets of uniqueness.
  Russian- and Hungarian-language literature was not checked. A negative search is not a proof of priority.
- **References.** All 29 literature references (the 30th entry is the corpus record) were checked: 28 against Crossref (DOI records: authors, title, journal, volume, pages, year), zbMATH (four older proceedings chapters: Zbl numbers) or the arXiv API (CVXPY, Clarabel), the software entry CVXOPT and the corpus record by their web pages.
  Explained differences: Crossref spells the second author of Monteiro–Zhou (1998) "Zou"; zbMATH and the paper's own metadata give "Zhou", which is used; the DOI of the Oberwolfach report is registered for the whole report (pp. 209–303, issued 2020), the entry gives the abstract's pages 256–259 and the report year 2019; Crossref lacks volume or page data for some chapters (Kuske–Swoboda–Petra, Hajdu–Tijdeman, Sonnevend), which were taken from zbMATH or the proceedings.
- **Scope.** The note answers Conjecture 1 as stated in the report and tested in the TCI paper, for the direction sets of Table I and the numerical reading. It does not refute binary tomography identifiability, and it does not treat the other open questions of the report (strong duality in general; more than two grey levels), apart from a remark.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/