Grothendieck inequality
In mathematics, the Grothendieck inequality states that there is a universal constant formula_1 with the following property. If "M" is an "n" × "n" (real or complex) matrix with for all (real or complex) numbers "s", "t" of absolute value at most 1, then for all vectors "S", "T" in the unit ball "B"("H") of a (real or complex) Hilbert space "H", the constant formula_1 being independent of "n". For a fixed Hilbert space of dimension "d", the smallest constant that satisfies this property for all "n" × "n" matrices is called a Grothendieck constant and denoted formula_5 . In fact, there are two Grothendieck constants, formula_6 and formula_7, depending on whether one works with real or complex numbers, respectively. The Grothendieck inequality and Grothendieck constants are named after Alexander Grothendieck, who proved the existence of the constants in a paper published in 1953. Motivation and the operator formulation. Let formula_8 be an formula_9 matrix. Then formula_10 defines a linear operator between the normed spaces formula_11 and formula_12 for formula_13. The formula_14-norm of formula_10 is the quantity formula_16 If formula_17, we denote the norm by formula_18. One can consider the following question: For what value of formula_19 and  formula_20 is formula_21 maximized? Since formula_10 is linear, then it suffices to consider formula_19 such that formula_24 contains as many points as possible, and also formula_20 such that formula_26 is as large as possible. By comparing formula_27 for formula_28, one sees that formula_29 for all formula_13. One way to compute formula_31 is by solving the following quadratic integer program: formula_32 To see this, note that formula_33, and taking the maximum over formula_34 gives formula_35. Then taking the maximum over formula_36 gives formula_31 by the convexity of formula_38 and by the triangle inequality. This quadratic integer program can be relaxed to  the following semidefinite program: formula_39 It is known that exactly computing formula_21 for formula_41 is NP-hard, while exacting computing formula_18 is NP-hard for formula_43. One can then ask the following natural question: How well does an optimal solution to the semidefinite program approximate formula_31? The Grothendieck inequality provides an answer to this question: There exists a fixed constant formula_45 such that, for any formula_46, for any formula_9 matrix formula_10, and for any Hilbert space formula_49, formula_50 Bounds on the constants. The sequences formula_6 and formula_7 are easily seen to be increasing, and Grothendieck's result states that they  are bounded, so they have limits. Grothendieck proved that formula_53 where formula_54 is defined to be formula_55. Grothendieck constant of order "d". Boris Tsirelson showed that the Grothendieck constants formula_6 play an essential role in the problem of quantum nonlocality: the Tsirelson bound of any full correlation bipartite Bell inequality for a quantum system of dimension "d" is upperbounded by formula_58. Lower bounds. Some historical data on best known lower bounds of formula_6 is summarized in the following table. Upper bounds. Some historical data on best known upper bounds of formula_6: Applications. Cut norm estimation. Given an formula_9 real matrix  formula_8, the cut norm of formula_10 is defined by formula_64 The notion of cut norm is essential in designing efficient approximation algorithms for dense graphs and matrices. More generally, the definition of cut norm can be generalized for symmetric measurable functions formula_65 so that the cut norm of formula_66 is defined by formula_67 This generalized definition of cut norm is crucial in the study of the space of graphons, and the two definitions of cut norm can be linked via the adjacency matrix of a graph. An application of the Grothendieck inequality is to give an efficient algorithm for approximating  the cut norm of a given real matrix formula_10; specifically, given an formula_9 real matrix, one can find a number formula_70 such that formula_71 where formula_72 is an absolute constant. This approximation algorithm uses semidefinite programming. We give a sketch of this approximation algorithm. Let formula_73 be formula_74 matrix defined by formula_75 One can verify that formula_76 by observing, if formula_77 form a maximizer for the cut norm of formula_78, then formula_79 form a maximizer for the cut norm of formula_10. Next, one can verify that formula_81, where formula_82 Although not important in this proof, formula_83 can be interpreted to  be the norm of formula_78 when viewed as a linear operator from formula_85 to formula_86. Now it suffices to design an efficient algorithm for approximating formula_31. We consider the following semidefinite program: formula_88 Then formula_89. The Grothedieck inequality implies that formula_90. Many algorithms (such as interior-point methods, first-order methods, the bundle method, the augmented Lagrangian method) are known to output the value of a semidefinite program up to an additive error formula_91 in time that is polynomial in the program description size and formula_92. Therefore, one can output formula_93 which satisfies formula_94 Szemerédi's regularity lemma. Szemerédi's  regularity lemma is a useful tool in graph theory, asserting (informally) that any graph can be partitioned into a controlled number of pieces that interact with each other in a pseudorandom way. Another application of the Grothendieck inequality is to produce a partition of the vertex set that satisfies the conclusion of Szemerédi's regularity lemma, via the cut norm estimation algorithm, in time that is polynomial in the upper bound of Szemerédi's regular partition size but independent of the number of vertices in the graph. It turns out that the main "bottleneck" of constructing a Szemeredi's regular  partition in polynomial time is to determine in polynomial time whether or not a given pair formula_95 is close to being formula_91-regular, meaning that for all formula_97 with formula_98, we have formula_99 where formula_100 for all formula_101 and formula_102 are the vertex and edge sets of the graph, respectively. To that end, we construct an formula_103 matrix formula_104, where formula_105, defined by formula_106 Then for all formula_97, formula_108 Hence, if formula_95 is not formula_91-regular, then formula_111. It follows that using the cut norm approximation algorithm together with the rounding technique, one can find in polynomial time formula_97 such  that formula_113 Then the algorithm for producing a Szemerédi's regular partition follows from the constructive argument of Alon et al. Variants of the Grothendieck inequality. Grothendieck inequality of a graph. The Grothendieck inequality of a graph states that for each formula_114 and for each graph formula_115 without self loops, there exists a universal constant formula_116 such that every formula_103 matrix formula_8 satisfies that formula_119 The Grothendieck constant of a graph formula_120, denoted formula_121, is defined to be the smallest constant formula_122 that satisfies the above property. The Grothendieck inequality of a graph is an extension of the Grothendieck inequality  because the former inequality is the special case of the latter inequality when formula_120 is a bipartite graph with two copies of formula_124 as its bipartition classes. Thus, formula_125 For formula_126, the formula_127-vertex complete graph, the Grothendieck inequality of formula_120 becomes formula_129 It turns out that formula_130. On one hand, we have formula_131. Indeed, the following inequality is true for any formula_103 matrix formula_8, which implies that formula_131 by the Cauchy-Schwarz inequality: formula_135 On the other hand, the matching lower bound formula_136 is due to Alon, Makarychev, Makarychev and Naor in 2006. The Grothendieck inequality formula_121 of a  graph formula_120 depends upon the structure of formula_120. It is known that formula_140 and formula_141 where formula_142 is the clique number of formula_120, i.e., the largest formula_144 such that there exists formula_145 with formula_146 such that formula_147 for all distinct formula_148, and formula_149 The parameter formula_150 is known as the Lovász theta function of the complement of formula_120. L^p Grothendieck inequality. In the application of the Grothendieck inequality for approximating the cut norm, we have seen that the Grothendieck inequality answers the following question: How well does an optimal solution to the semidefinite program formula_152 approximate formula_31, which can be  viewed as an optimization problem over the unit cube? More generally, we can ask similar questions over convex bodies other than the unit cube. For instance, the following inequality is due to Naor and Schechtman and independently due to Guruswami et al: For every formula_103 matrix formula_8 and every formula_156, formula_157 where formula_158 The constant formula_159 is sharp in the inequality. Stirling's formula implies that formula_160 as formula_161.