The minimal sum of squares over partitions with a nonnegative rank

2022/04/16 by Sela Fried, Fried, Sela
Engineering · Mathematics · #Advanced Mathematical Identities #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.2204.07873

17 pages, 4 figures, 1 table

arxiv created 2022/05/04 · arxiv updated 2022/05/05

Abstract

Motivated by a question of Defant and Propp (2020) regarding the connection between the degrees of noninvertibility of functions and those of their iterates, we address the combinatorial optimization problem of minimizing the sum of squares over partitions of n with a nonnegative rank. Denoting the sequence of the minima by (m_n)_n∈ℕ, we prove that m_n=Θ(n^4/3). Consequently, we improve by a factor of 2 the lower bound provided by Defant and Propp for iterates of order two.

Related

• Sums of Squares on the Hypercube
• Refined Asymptotics for Multigraded Sums of Squares
• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
• Tight Sum-of-Squares lower bounds for binary polynomial optimization problems
• An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization