Degree Bounds for Putinar’s Positivstellensatz on the Hypercube

The Positivstellensätze of Putinar and Schmüdgen show that any polynomial [Formula: see text] positive on a compact semialgebraic set can be represented using sums of squares. Recently, there has been great interest in proving effective versions of these results, namely to show bounds on the required degree of the sums of squares in such representations. These effective Positivstellensätze have direct implications for the convergence rate of the celebrated moment-SOS hierarchy in polynomial optimization. In this paper, we restrict to the fundamental case of the hypercube [Formula: see text]. We show an upper degree bound for Putinar-type representations on [Formula: see text] of the order [Formula: see text], where [Formula: see text], [Formula: see text] are the maximum and minimum of [Formula: see text] on [Formula: see text], respectively. Previously, specialized results of this kind were available only for Schmüdgen-type representations and not for Putinar-type ones. Complementing this upper degree bound, we show a lower degree bound in [Formula: see text]. This is the first lower bound for Putinar-type representations on a semialgebraic set with nonempty interior described by a standard set of inequalities.