Initial steps in the classification of maximal mediated sets

DOI10.1016/J.JSC.2020.07.013zbMATH Open1475.52023arXiv1910.00502OpenAlexW3040772724MaRDI QIDQ820977FDOQ820977

Authors: Jacob Hartzer, Olivia Röhrig, Timo de Wolff, Oğuzhan Yürük 

Publication date: 29 September 2021

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Maximal mediated sets (MMS), introduced by Reznick, are distinguished subsets of lattice points in integral polytopes with even vertices. MMS of Newton polytopes of AGI-forms and nonnegative circuit polynomials determine whether these polynomials are sums of squares. In this article, we take initial steps in classifying MMS both theoretically and practically. Theoretically, we show that MMS of simplices are isomorphic if and only if the simplices generate the same lattice up to permutations. Furthermore, we generalize a result of Iliman and the third author. Practically, we fully characterize the MMS for all simplices of sufficiently small dimensions and maximal 1-norms. In particular, we experimentally prove a conjecture by Reznick for 2 dimensional simplices up to maximal 1-norm 150 and provide indications on the distribution of the density of MMS.

Full work available at URL: https://arxiv.org/abs/1910.00502

Recommendations

• scientific article; zbMATH DE number 3970743
• scientific article; zbMATH DE number 3961591
• scientific article; zbMATH DE number 3968511
• On maximal weakly separated set-systems
• scientific article; zbMATH DE number 1308899
• The relationship between the generalized median and minimax sets: a correction
• Some results about maximal primitive sets
• Some properties of maximal sets
• Medians and majorities in semimodular posets
• Medians and majorities in semimodular posets

zbMATH Keywords

latticesums of squaresnonnegativitymaximal mediated setsum of nonnegative circuit polynomials

Mathematics Subject Classification ID

Convex programming (90C25) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Semialgebraic sets and related spaces (14P10) Sums of squares and representations by other particular quadratic forms (11E25) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Forms over real fields (11E10)

Cites Work

• polymake: a framework for analyzing convex polytopes
• Lattice polytopes with distinct pair-sums
• Title not available (Why is that?)
• Semidefinite Optimization and Convex Algebraic Geometry
• Forms derived from the arithmetic-geometric inequality
• Extremal positive semidefinite forms
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
• Positive polynomials and sums of squares
• Title not available (Why is that?)
• Relative entropy relaxations for signomial optimization
• Title not available (Why is that?)

Cited In (3)

• On minimal extended representations of generalized power cones
• SONC optimization and exact nonnegativity certificates via second-order cone programming
• Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation

Uses Software

• GNU parallel

This page was built for publication: Initial steps in the classification of maximal mediated sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820977)