2015/10/14 by Michael Christ, Christ, Michael, James Demmel +7
Computer Science · Engineering · Mathematics · #11U05 #26D15 #Advanced Optimization Algorithms Research #Classical Analysis and ODEs (math.CA) #Computational Geometry and Mesh Generation #FOS: Mathematics #Geometric and Algebraic Topology #Limits and Structures in Graph Theory #Logic (math.LO) #Polynomial and algebraic computation #Topology Optimization in Engineering
paper · pdf · doi:10.48550/arxiv.1510.04190
openalex publication_date 2015/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
H "older-Brascamp-Lieb inequalities provide upper bounds for a class of\nmultilinear expressions, in terms of Lp norms of the functions involved.\nThey have been extensively studied for functions defined on Euclidean spaces.\nBennett-Carbery-Christ-Tao have initiated the study of these inequalities for\ndiscrete Abelian groups and, in terms of suitable data, have characterized the\nset of all tuples of exponents for which such an inequality holds for specified\ndata, as the convex polyhedron defined by a particular finite set of affine\ninequalities.\n In this paper we advance the theory of such inequalities for torsion-free\ndiscrete Abelian groups in three respects. The optimal constant in any such\ninequality is shown to equal 1 whenever it is finite. An algorithm that\ncomputes the admissible polyhedron of exponents is developed. It is shown that\nnonetheless, existence of an algorithm that computes the full list of\ninequalities in the Bennett-Carbery-Christ-Tao description of the admissible\npolyhedron for all data, is equivalent to an affirmative solution of Hilbert's\nTenth Problem over the rationals. That problem remains open.\n Applications to computer science will be explored in a forthcoming companion\npaper.\n