A Negative Answer to the Kadu–van Leeuwen Conjecture on Dual Binary Tomography

Kadu and van Leeuwen proposed to reconstruct a binary image from line sums by solving the Lagrange dual of the least-squares problem and reading off the sign of its numerically computed solution, where zeros mark undetermined pixels. From exhaustive experiments with images of up to 4 × 4 pixels and two to four directions they conjectured, for noiseless data and every image size, that this retrieves the unique binary solution if there is one and the intersection of all binary solutions otherwise. We show that the conjecture is false. In the noiseless case the exact dual optimum is zero, so the conjecture is a statement about numerically computed solutions, and the only pixels such a solution can certify are those that take the same value on the whole solution set Q of the box relaxation. A 5 × 5 image with six ones has a unique binary solution for rows, columns and diagonals, but Q is a segment with a half-integral endpoint and only 14 of the 25 pixels are fixed on it. Padding gives such images for every n ≥ 5; with four directions the first failure is at 6 × 6. The second statement already fails inside the tested range, for exactly 448 of the 65536 images of size 4 × 4 with rows, columns and diagonals. In computations through CVXPY (not the authors' MATLAB and CVX stack), the interior-point solvers Clarabel, ECOS and PIQP return the pattern of the fixed pixels, with zeros elsewhere, or a full sign pattern with a wrong sign; of 61 solver runs (eight solvers) that returned a solution on the 5 × 5 image, none returns the image. Two directions give a totally unimodular system, and the fixed-pixel form of the conjecture holds for them at every size. That uniqueness among binary solutions does not imply uniqueness among fractional solutions is known from work of Fishburn, Schwander, Shepp and Vanderbei; what is new here is the explicit refutation of this conjecture. This is an unrefereed note.