Neural Computation: Optimal Pairwise-Max ReLU Representations

The maximum function offers a concrete benchmark for the cost of exact neural computation. For five and six inputs in the pairwise-max model of side size two (PM2), we prove the exact directional widths W*(5,2)=6 and W*(6,2)=33. The features are all pairwise maxima, including the input coordinates; each hinge applies a ReLU to the difference between two sums of two features, with repetitions allowed. We count distinct nonparallel hinge directions and allow a free feature-linear term. Explicit rational identities attain both bounds on all real inputs. Optimality holds for arbitrary coefficient signs and magnitudes, without symmetry assumptions. The lower bounds exploit cancellation: every kink introduced where the maximum is linear must disappear from the sum. This condition yields exact linear equations. Small dependencies among binary kink profiles settle the five-input case; a canonical reduction that never increases support and a complete analysis of local support costs settle the six-input case. Both rational optimality theorems are fully formalized in Lean. A separate rationalization argument gives the same minima for real coefficients in the fixed dictionary.