Towards discrete convex analysis over classical root systems
2026-08-17 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors extend discrete convex analysis (DCA), a tool originally designed to solve certain math problems on integer grids, to more complex structures derived from classical root systems. They define two types of discrete convex functions, called L-convex and M-convex, on these new mathematical domains, and show that finding a local best solution means finding a global best solution. Additionally, they prove that these two types of functions are closely linked through a special mathematical transformation called the discrete Fenchel–Legendre conjugate. This work expands the scope of DCA beyond its traditional setting, potentially enriching its applications.
Discrete Convex AnalysisClassical Root SystemsL-convex FunctionsM-convex FunctionsEuclidean Coxeter ComplexRoot LatticeDiscrete Fenchel–Legendre ConjugateIntegralityCombinatorial OptimizationPolyhedral Structures
Authors
Yuni Iwamasa
Abstract
Discrete Convex Analysis (DCA) is a discrete analog of continuous convex analysis, originally proposed as a unified theoretical framework for efficiently solvable combinatorial optimization problems. Recently, DCA has proven to be a powerful tool across diverse fields, ranging from operations research to economics and pure mathematics. Motivated by the broad applicability of DCA, this paper establishes a unified theory of discrete convex analysis over discrete structures arising from classical root systems, extending the usual setting of the integer lattice, which essentially corresponds to type A. We adopt the vertex set of the Euclidean Coxeter complex as the primal discrete domain for L-convexity, and the root lattice as the dual discrete domain for M-convexity. Using the associated polyhedral structures, we formulate L- and M-convex functions together with notions of integrality determined by the root system. We show that local optimality guarantees global optimality for these functions. Furthermore, we establish that integral L-convex functions and integral M-convex functions correspond one-to-one via the discrete Fenchel--Legendre conjugate, thereby extending the conjugacy in the original DCA from type A to all classical root systems.