{'fraction_non_alphanumeric': 0.06214318337519982, 'fraction_numerical': 0.013116579127654716, 'mean_word_length': 3.5914154652686765, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sphere packing bounds via rescaling

We study the relationship between local and global density for sphere packings, and in particular the convergence of packing densities in large, compact regions to the Euclidean limit. We axiomatize key properties of sphere packing bounds by the concept of a packing bound function, and we study the special case of sandwich functions, which give a framework for inequalities given by the Lov\'asz sandwich theorem. We show that every packing bound function tends to a Euclidean limit on rectifiable sets, generalizing the work of Borodachov, Hardin, and Saff. Linear and semidefinite programming bounds yield packing bound functions, and we develop a Lasserre hierarchy that converges to the optimal sphere packing density.

Aside from the case of packing convex, centrally symmetric bodies in at most two dimensions [19,Section 25], it is not known how to reduce the general packing problem to considering a bounded number of bodies, and there is little reason to believe such a reduction is always possible, especially in high dimensions. Instead, the global packing density can be obtained as a limit of the packing densities in bounded but increasingly large regions [23], and this limiting process seems to be essential. For packing of spheres and covering by bodies of bounded diameter, the first appearance of this sort of limit appears to be in a paper by Kolmogorov and Tikhomirov [33, Theorem IX], which proves a limit theorem for Jordan-measurable sets (see [32] for an English translation).
Borodachov, Hardin, and Saff [7] analyzed this limit in broad generality. To formulate their result, we need some notation. Given a bounded subset C of R d , let pack(C) be the largest possible size of a subset X of C such that all points in X are at distance at least 2 from each other. In other words, pack(C) is the maximum number of unit spheres that can be centered at points of C, if their interiors are not allowed to overlap. Borodachov, Hardin, and Saff work with subsets that may not be full-dimensional, such as the surface of a sphere in R d . Recall that a Borel subset of R d is called n-rectifiable if it is the image of a bounded Borel subset of R n under a Lipschitz function from R n to R d . Let H n denote n-dimensional Hausdorff measure on R d , let L d = H d denote d-dimensional Lebesgue measure, let B d r (x) be the open ball of radius r in R d centered at x, and let rC be C dilated by a factor of r.
The following theorem is a special case of Theorem 2.2 in [7], after rescaling: Theorem 1.1 (Borodachov, Hardin, and Saff [7]). Let 1 ≤ n ≤ d, and let C be a compact, n-rectifiable subset of R d with H n (C) > 0. Then the limit lim r→∞ pack(rC) H n (rC) H n (B n 1 ) exists and equals the sphere packing density in R n .
In this paper, we begin by extending Theorem 1.1 to a class of functions we call packing bound functions. The function pack defined above will be a packing bound function, as will various upper bounds for pack, including linear and semidefinite programming bounds. Our extension thus analyzes how these sphere packing bounds behave when applied to increasingly large regions of space. For comparison, Hardin, Saff, and Vlasiuk [29] analyze conditions on short-range interactions between particles that suffice to obtain fairly general asymptotics. Our approach differs conceptually in studying not just optimization problems over particle configurations, but also related quantities such as bounds.
To define packing bound functions, we use the following notation. Let d(x, y) = |x − y| be the standard 2 metric on R d (the two uses of d are not ambiguous in practice), and let C denote the closure of C. For two subsets C and C of R d , the distance d(C, C ) is the infimum over all distances d(x, x ) such that x ∈ C and x ∈ C (with d(C, C ) = ∞ if C or C is empty), and C(ε) = {x ∈ R d : d(x, C) < ε} is the ε-neighborhood of C. We say a function ψ : C → C is distance-increasing if d(ψ(x), ψ(y)) ≥ d(x, y) for all x, y ∈ C. Let B d be the set of all bounded Borel subsets of R d , and let B = d B d . Definition 1.2. A packing bound function is a map A from B to [0, ∞) such that the following axioms hold for all elements C and C of B and ε > 0: (1) (Sphere bound) If C is a nonempty set contained in the interior of a ball of radius 1, then A(C) = 1. (2) (Lipschitz inequality) If there exists a distance-increasing function ψ : C → C , then A(C) ≤ A(C ). (3) (Union axiom) If C and C are subsets of the same ambient space R d and d(C, C ) ≥ 2, then A(C ∪ C ) = A(C) + A(C ). (4) (Mesh axiom) If C ⊆ C (ε), then A( 1 1+ε C) ≤ A(C ). One example is the function pack. For another, let cov(C) be the size of the smallest covering of C by open balls of radius 1, with sphere centers not necessarily in C. In other words, for a subset C of R d , cov(C) is the infimum of |X| over subsets X ⊆ R d such that C ⊆ X(1). We will show that both pack and cov are packing bound functions, and that they are the extreme packing bound functions. More precisely, under the partial ordering A 1 ≤ A 2 defined by A 1 (C) ≤ A 2 (C) for all C, every packing bound function A satisfies pack ≤ A ≤ cov. The inequality pack ≤ A explains the name "packing bound function." Between pack and cov, we construct a range of packing bound functions, most notably the linear programming bound. Each of these functions can be viewed in two ways, as an upper bound for packings or as a lower bound for coverings, 1 and each packing bound function has consistent large-scale limiting behavior: Theorem 1.3. Let 1 ≤ n ≤ d, let C be a compact, n-rectifiable subset of R d with H n (C) > 0, and let A be any packing bound function. Then the limit lim r→∞ A(rC) H n (rC) exists and depends only on A and n, rather than the choice of C or d.
In fact, we will prove a somewhat more general result in Theorem 4.12, with the same hypotheses as Theorem 2.2 in [7]. For the special case of the function cov, we learned after completing this work that convergence was independently proved at the same time by Anderson, Reznikov, Vlasiuk, and White [3].
Because pack is the smallest packing bound function, the limit lim r→∞ A(rC) H n (rC) H n (B n 1 ) is always an upper bound for the sphere packing density in R n . One example is the linear programming bound of Cohn and Elkies [13], which we obtain as a limit of a Delsarte linear program for bounded regions. Our formulation of this limit appears to be new, although some of the techniques are related to work of Cohn, de Courcy-Ireland, and Zhao [16,12]. Semidefinite programming hierarchies are an important generalization of linear programming bounds, which give upper bounds for the size of the largest packing in any compact set by the work of de Laat and Vallentin [35]. Many of the best bounds known for spherical codes [5] and sphere packing [13,11] come from linear and semidefinite programming relaxations along these lines. To formulate these semidefinite programming hierarchies as packing bound functions, we will define a discrete Lasserre hierarchy. Unlike the topological Lasserre hierarchy from [35], the discrete hierarchy uses only the graph structure of distances in the space C ⊆ R d and not its topology. This construction yields a packing bound function, and thus abstractly, there must exist a Euclidean limit. We show that this Euclidean limit agrees with the limit of the topological approach from [35], and we formulate it as an optimization problem on Euclidean space. We also prove that as t → ∞, the t-th level of the hierarchy approaches the optimal density of sphere packing in Euclidean space.
Although 3-point bounds for spherical codes have been known since the work of Bachoc and Vallentin [5], obtaining 3-point bounds or other semidefinite programming bounds that refine the linear programming bound in R d has been a longstanding open problem. Formulating these refinements was one of the main motivations of the present work and will be used in subsequent work with David de Laat [15] to give new upper bounds on sphere packing in all dimensions up through 12 in which the exact answer is not known (i.e., not 1, 2, 3, or 8 dimensions).

Packing bound functions
In this section, A will denote an arbitrary packing bound function, and C and C will be elements of B. We begin by examining some of the consequences of Definition 1.2. The sphere bound, Lipschitz, and union axioms are quite natural, while the mesh axiom is a little more subtle. Intuitively, it says that a packing can be modified slightly so that the sphere centers are forced to live on a mesh if that mesh is sufficiently fine. Later, we will give some consequences of this axiom to packings when C is a dense subset as well as packings on a countable nested union. These applications use the following special case of the mesh axiom, which we refer to as the continuity property: Proof. First, by monotonicity we reduce to the case when C and C are disjoint. Now consider the union of copies of C and C placed very far apart (further than 2 plus the diameter of C ∪ C ), which we call D. Then the map from C ∪ C to D sending C to the copy of C in D and C to the copy of C in D is distance-increasing, and therefore A(C ∪ C ) ≤ A(D) = A(C) + A(C ) by the Lipschitz and union properties.
Proposition 2.6 (Density). If ε > 0 and C ⊆ C is dense, then Proof. Every dense subset C satisfies C ⊆ C (δ) for each δ > 0. By continuity, we can choose δ > 0 so that Consider the n-cube I n = [0, 1] n . By the union bound, A(2I n ) ≤ 2 n A(I n ), and so A(2 k I n )/2 kn is a weakly decreasing sequence in k. On the other hand, it is bounded below by 1/2 n because A(2 k I n ) ≥ pack(2 k I n ) ≥ (1 + 2 k−1 ) n when k ≥ 1 from using the subset X = 2 k I n ∩ 2Z n . Therefore, A(2 k I n )/2 kn must converge to some positive number.
Definition 2.7. For a packing bound function A, let δ A,n = lim k→∞ A(2 k I n )/2 kn . We say that a packing bound function satisfies the Euclidean bound if every bounded Borel subset C ⊆ R n satisfies A(C) ≥ δ A,n L n (C).
Because A ≥ pack, the quantity δ A,n L n (B n 1 ) is always an upper bound for the sphere packing density δ pack,n L n (B n 1 ) in R n . Similarly, the inequality A ≤ cov from Proposition 2.10 will imply that δ A,n L n (B n 1 ) is a lower bound for the sphere covering density δ cov,n L n (B n 1 ) in R n . Remark 2.8. By Proposition 2.6, it suffices to prove the Euclidean bound when C is compact. Specifically, if the Euclidean bound holds for C, then for every ε > 0, Because neighborhoods C(ε) of bounded Borel sets C are Jordan-measurable, 2 it further suffices to prove the Euclidean bound for Jordan-measurable sets. Specifically, by the mesh axiom, and lim ε→0 L n (C(ε)) = L n (C) when C is compact, by Theorem 3.2.39 in [18]. Moreover, one can show that the Euclidean bound for C is automatically satisfied if C is capable of tiling Euclidean space with overlap of measure 0.
2 To see why, notice that this amounts to the claim that the boundary of C(ε) has Lebesgue measure zero. The function x → d(x, C) is a Lipschitz function, and so it is differentiable almost everywhere by Rademacher's theorem. Thus, it suffices to show that the set of points x where x → d(x, C) is differentiable and d(x, C) = ε has measure zero. For such points, lim δ→0 Ln(C(ε) ∩ B n δ (x))/Ln(B n δ (x)) = 1/2, and the result follows by the Lebesgue density theorem.

2.1.
Packing and covering as packing bound functions. We say a packing in C is a subset X of C such that all points in X are at distance at least 2 from each other. Recall that pack(C) is the size of the largest packing in C.
Proposition 2.9. The function pack is a packing bound function that satisfies the Euclidean bound.
Proof. Among the axioms, the sphere bound, Lipschitz inequality, and union axiom are immediate. For the mesh axiom, suppose C ⊆ C (ε), and let X be a packing in 1 1+ε C. Then (1 + ε)X is a subset of C with all distances distance at least 2 + 2ε. Each x ∈ X is within ε of some point y(x) in C because C ⊆ C (ε), and so Y = {y(x) : x ∈ X} is a packing in C . It now follows that A(C ) ≥ |Y | by Corollary 2.3, and thus A(C ) ≥ A( 1 1+ε C), as desired. All that remains is to prove the Euclidean bound, for which we use an averaging argument. Let C ⊆ R n be a Borel set with C ⊆ [−r, r] n , and choose a packing X k in 2 k I n for each k such that lim k→∞ |X k | 2 kn = δ pack,n . We will obtain a lower bound for pack(C) by averaging over intersections of translates of C with X k . To do so, consider the cube R = [−r, 2 k +r] n containing 2 k I n . Because It follows that for some t ∈ R, and therefore Taking the limit as k → ∞ completes the proof.
Recall that cov(C) is the smallest covering of C by open balls of radius 1, with sphere centers not necessarily in C. That is, for C in the ambient space R d , cov(C) is the infimum of |X| over subsets X ⊆ R d such that C ⊆ X(1). This infimum is independent of the ambient space chosen: if C is contained in a proper subspace R d of R d , then the points in X can be orthogonally projected to R d . We call such sets X coverings of C with open balls of radius 1.
Proposition 2.10. The function cov is a packing bound function. It is the maximal packing bound function among all packing bound functions, and it does not satisfy the Euclidean bound.
Proof. First, we check the sphere bound, union axiom, and mesh axiom. The function cov trivially satisfies the sphere bound. For the union axiom, if C and C are separated by distance at least 2, then there is no open ball of radius 1 that intersects both C and C , and so covering C ∪ C is the same as covering C and C separately. For the mesh axiom, suppose C ⊆ C (ε), and let X be a covering of C with open balls of radius 1. Then (1 + ε)-balls centered at X cover C (ε), and so these (1 + ε)-balls cover C. Therefore 1 1+ε X gives a covering of 1 1+ε C by balls of radius 1.
The Lipschitz inequality requires a little more argument. Let ψ : C → C be a distance-increasing map, with C ⊆ R d and C ⊆ R d , and suppose X is a covering of C with open balls of radius 1. We would like to obtain a covering of C of the same size. To do so, note that the function ψ is injective, and its inverse ψ −1 on ψ(C) is a Lipschitz function with Lipschitz constant 1. By the Kirszbraun theorem, we can extend ψ −1 to a Lipschitz function ϕ : To see that cov is the largest packing bound function, suppose A is some other packing bound function, and write C ⊆ simply says that the sphere covering density in R d is strictly greater than 1, which holds because spheres cannot tile space when d > 1. (If the covering density were 1, then a compactness argument would show that closed unit balls cover space with only measure-zero overlap. However, a point in space can be on the boundary of at most two such balls, which does not yield a covering locally.)

2.2.
Consequences of uniform continuity. The idea of Proposition 2.1 can be restated as follows. If C is an arbitrary set, we can choose any sufficiently fine mesh C and stipulate that our sphere centers must live on C as long as we dilate the mesh by a small amount. In the remainder of this section, we give some consequences of this continuity property. Proposition 2.11 (Nested union). Let C 1 ⊆ C 2 ⊆ . . . be Borel sets such that i C i is bounded. Then for each ε > 0, there exists a j such that Proof. Choose δ as in Proposition 2.1. Then Because i C i is compact, it must be contained in C j (δ) for some j, which completes the proof.
We will use the normalized Hausdorff measure, by which we mean Recall that the n-dimensional Minkowski content M n (C) of a set C ⊆ R d with d ≥ n is defined by when this limit exists (we take L 0 (B 0 ε ) = 1 when n = d). The upper or lower Minkowski content, denoted M n or M n , is given by the lim sup or lim inf, respectively. For a compact n-rectifiable set C, [18, Theorem 3.2.39] tells us that H n (C) = M n (C). Proof. Because M n (C) < ∞, there is some constant M such that for δ sufficiently small, Consider the collection F of balls of radius δ at each point of C. By the Vitali covering lemma [39, Theorem 2.1], there is a subset F consisting of disjoint balls such that B∈F 5B contains B∈F B = C(δ). Because the balls in F are disjoint, . Now we let r = 1/(6δ). Because B∈F 5rB covers rC and the spheres have radius r5δ < 1, monotonicity and the union and sphere bounds imply that In particular, A(rC)/r n ≤ M /(rδ) n = M 6 n , and we conclude that lim sup r→∞ A(rC)/r n < ∞ because this bound holds whenever r = 1/(6δ) with δ sufficiently small.
We isolate a geometric lemma in preparation for Proposition 2.14.
Lemma 2.13. If C is any compact subset of C ⊆ R d with M n (C) and M n (C ) defined and ∞ > M n (C ) > M n (C) − ε, then there is a δ * such that for all δ ≤ δ * , there is a packing B of disjoint balls of radius δ/5 in C(δ) \ C (δ) containing at most M ε/δ n balls for some universal constant M depending on the dimensions n and d, such that B∈B 5B is a covering of C \ C (δ).
Proof. Since the Minkowski contents of C and C are within ε, for sufficiently small ). For every δ, consider the collection of balls F of radius exactly δ/5 at each point of C \ C (δ). By the Vitali covering lemma, there are disjoint balls B of radius δ/5 such that 5B contains the union of the balls in F. These balls are a sphere packing and are contained in C(δ) \ C (δ), and therefore ).
It follows that |B| ≤ M ε/δ n , where M depends only on n and d.
In the process of working with an arbitrary rectifiable set, we will need to pass from a set to a subset of the same Minkowski content that cuts out a bad subset. We need to show that this removal does not affect the first order asymptotics of packing. This result will also be used in working with compact sets without appealing to the Euclidean bound. The following proposition is an analogue of the "regularity lemma" in the Riesz energy setting [8,Lemma 8.6.9].
Proposition 2.14. For each n, bounded Borel set C ⊆ R d with M n (C) defined, and k ≥ 1, there is an ε * > 0 such that for any ε ≤ ε * , if C is any compact subset of C with M n (C ) defined and ∞ > M n (C ) > M n (C) − ε, then Proof. Choose δ * and M as in Lemma 2.13, and let δ = 1/(kr) ≤ δ * for sufficiently large r. By Lemma 2.13, there is a collection 5B of at most M ε/δ n open balls of radius δ that cover C \ C (δ). Because C ⊆ (C ∪ (C \ C (δ)))(δ), scaling by a factor of r shows that Finally, because rC \ rC (rδ) is covered with at most M ε/δ n open balls of radius δr = 1/k ≤ 1, the last term on the right side can be bounded by M εk n , while the left side is k k + 1 n lim sup r→∞ A(rC) r n , which is what we wanted to show. For the lim inf version, we instead use the inequality and conclude in the same way.

Packing bound functions via graphs
Consider the category G whose objects are (loopless, undirected) graphs G = (V, E) with finite chromatic number, and whose morphisms are graph homomorphisms. There is a natural operation of join, where the join of two graphs G and H, denoted G * H, is the graph with vertex set the disjoint union of the vertex sets V (G) and V (H) and edge set all edges in G and H together with all pairs (x, y) with x ∈ V (G) and y ∈ V (H). For simplicity, we denote the edge containing vertices x and y by xy, and the empty graph by ∅. The complement G of a graph G has the same vertex set and the complementary edge set.
By passing to complements, we can consider a related category which shows the connection to packing problems in discrete geometry more clearly. This category G has as its objects graphs with finite clique covering number, meaning there is a finite collection of cliques C 1 , . . . , C n such that V ⊆ n i=1 C i . Morphisms from G to G are maps f : V → V with the following two properties: (1) If (f (x), f (y)) ∈ E , then (x, y) ∈ E. That is, the preimage of any edge is an edge. (2) The preimage of each x ∈ V is a clique, possibly empty.
There is a natural operation of disjoint union graphs, which we denote . This is not a coproduct on the category. There is an isomorphism of categories G → G sending a graph to its complement, which sends disjoint unions to joins and vice versa.
In geometric terms, we think of graphs in G as follows: the vertices are points in a bounded Borel subset of R d , and the edges indicate which points are at distance less than 2 from each other. Equivalently, edges in G indicate which pairs of points are at distance at least 2, i.e., far enough away that they do not interact. We will use this category to construct sandwich functions (named after the Lovász sandwich theorem [31]), which describe the packing bound functions that depend only on the underlying graph structure, rather than the additional information supplied by the metric.
A sandwich function is a function Ψ from objects of G to nonnegative real numbers with the following properties: (1) (Sphere bound) Ψ(∅) = 0 and Ψ(G) = 1 if G consists of a single vertex.
(2) (Functoriality) If G → G is a morphism, then Ψ(G) ≤ Ψ(G ). That is, Ψ is a functor from G to the poset of nonnegative real numbers. Theorem 3.1. Every sandwich function Ψ gives a packing bound function A on bounded subsets of Euclidean spaces as follows. Given a bounded Borel subset C of R n , let G(C) be the graph whose vertex set is C and whose edge set is pairs x, y ∈ C such that |x − y| ≥ 2. Then A(C) = Φ(G(C)).
Proof. To prove that A is a packing bound function, we check the axioms: (1) (Sphere bound) If C is empty, then so is G(C), and therefore A(C) = Φ(G(C)) = 0. If C is contained in an open ball of radius 1, then G(C) has no edges and thus admits a morphism in G to a single point, so On the other hand, a single point admits a morphism to any nonempty graph by inclusion, and so Φ( Remark 3.2. Many packing bound functions, including packing and the discrete Lasserre and k-point bound hierarchies, come from sandwich functions on graphs using this theorem. However, sphere covering does not, as we will see below.
Proposition 3.3. The clique number ω and chromatic number χ are sandwich functions, and every sandwich function Φ satisfies the following Lovász sandwich theorem: Proof. To check that ω is a sandwich function, note that the image of a clique under a graph homomorphism remains a clique, while the union of two cliques in G 1 and G 2 becomes a clique in their join. For chromatic number, the preimage of an independent set under a graph homomorphism is independent, so an n-coloring pulls back to an n-coloring under a graph homomorphism. Moreover, the only way to color the join of two graphs is to color each part separately. Now suppose Φ is a sandwich function. Any clique is the iterated join of onepoint graphs, and its inclusion into the whole graph is a graph homomorphism, thus showing that if K n → G is the inclusion of a clique then n = Φ(K n ) ≤ Φ(G). By considering all such cliques, this shows ω(G) ≤ Φ(G).
On the other hand, n-colorings of G correspond to graph homomorphisms G → K n , with the color sets being the preimages of the vertices of K n . Thus, if G has an n-coloring, then Φ(G) ≤ Φ(K n ) = n. By considering all possible colorings, this shows Φ(G) ≤ χ(G). Proof. Let C be the vertices of an equilateral triangle of side length strictly between √ 3 and 2. This set cannot be covered by a single sphere, but its underlying graph G(C) is independent. Thus, χ(G(C)) is strictly smaller than the covering number, which would be impossible if covering came from a sandwich function.
Given a sandwich function Φ, we often identify Φ with the corresponding packing bound function notationally. For example, we write δ Φ,n in Definition 2.7.
Remark 3.5. The quantity δ χ,n /L n (B n 1 ) appeared in [33, Theorem IX] as a limit of their notion of ε-covering of Jordan-measurable sets by bodies of diameter at most 2ε (see [33,Definition 1]) as ε → 0 + .
It would be interesting to compare δ χ,n , the "clique cover" or "diameter cover" density of Euclidean space R n , with the density of the best sphere covering δ cov,n . Do these quantities coincide? This question was posed by Lenz and Heppes and is open even in the plane [9, Section 1.3, Conjecture 4].
The original Lovász sandwich theorem was proved for a graph invariant ϑ and used to give an upper bound for Shannon capacity. We will see that both of these quantities, as well as some generalizations, are sandwich functions.
Shannon capacity is defined in terms of the strong graph product. Recall that the strong graph product G · H is the graph whose vertex set is V (G) × V (H) and whose edge set consists of distinct pairs ( Let G n denote the n-fold strong product of G with itself. Shannon capacity, denoted Θ(G), is lim n→∞ α(G n ) 1/n , which exists for graphs whose complements have finite chromatic number; here α(G) denotes the independence number of G. Shannon capacity is not a sandwich function, because it is not additive under join, as shown by Alon [1].
We now define the Lovász theta number ϑ and its variants ϑ and ϑ + , first for finite graphs [38,Sections 4.2 and 4.4], and then in general. For finite graphs where the supremum ranges over all induced finite subgraphs of G, and similarly for ϑ and ϑ + .
Because we can extend a matrix by 0, ϑ(G) = sup H⊆G ϑ(H) holds for finite graphs G, showing that our definition is internally consistent. Moreover, there is no harm in requiring that our matrices M are symmetric, because we can average M with its transpose. We will assume symmetry as part of the definition of positive semidefiniteness.
It is known [38,Equation 69] that Moreover, Lovász showed that Θ(G) ≤ ϑ(G). For later use, it will be helpful to formulate the dual semidefinite programs defining ϑ, ϑ , and ϑ + . We will state the duals in terms of positive semidefinite kernels on G, that is, This is of course equivalent to positive semidefinite V (G) × V (G) matrices, but the language of kernels will be convenient.
is the minimum of t over all feasible K and t for ϑ (G) that additionally satisfy K(x, y) = −1 for xy ∈ E(G), and (3) ϑ + (G) is the minimum of t over all feasible K and t for ϑ (G) that additionally satisfy K(x, y) ≥ −1 for xy ∈ E(G).
For a proof, see [38,Sections 4.2 and 4.4]. We now are ready to prove that these give examples of sandwich functions.
To aid with the proof, we have the following general lemma.
where the supremum is over all induced finite subgraphs. If Φ satisfies the sandwich function axioms for all finite graphs, then Φ satisfies them for all graphs in G.
Proof. For a graph homomorphism f : G → H, where the suprema are over induced finite subgraphs F and F of G and H, respectively.
, so taking the supremum over such finite subgraphs gives the other inequality. Therefore Proof of Theorem 3.8. By the lemma, we reduce to working only with finite graphs. First, we will prove functoriality. Let f : We claim that if M is positive semidefinite, then f * M is positive semidefinite. We want to show that for arbitrary weights w x for x ∈ V (H), That holds because the sum equals which is nonnegative by the positive semidefiniteness of M .
To prove functoriality for ϑ + , we check as follows that if M is feasible for This shows that the matrix is indeed feasible. Now as desired.
The semidefinite program defining ϑ(G) is slightly more stringent, requiring M ij = 0 rather than just M ij ≤ 0 for ij ∈ E(G). Suppose M is feasible for ϑ(G). As a result Tr(f * M ) = 1, so we can ignore the normalizing factor (Tr(f * M )) −1 . By the same reasoning as before, (f * M ) xy = i∈f −1 (x),j∈f −1 (y) M ij = 0 for xy ∈ E(H), since the sum over i and j ranges over pairs such that ij ∈ E(G). This shows that f * M must be feasible for ϑ(H), and so this construction shows that ϑ(G) ≤ ϑ(H).
Finally, suppose M is feasible for ϑ (G). This imposes nonnegativity on its entries, and so f * M also has nonnegative entries and is feasible for ϑ (H). This construction therefore shows that ϑ (G) ≤ ϑ (H), and functoriality is proved for finite graphs in all cases.
What remains is to show the additivity under join, or from the perspective of the category G, additivity under taking disjoint unions of graphs. We break up this statement into two inequalities, which we prove separately.
First, we prove subadditivity, i.e., Ψ(G H) ≤ Ψ(G) + Ψ(H) when Ψ is ϑ, ϑ , or ϑ + . We prove the inequality using the dual formulation in terms of kernels K. Let K G and K H be positive semidefinite kernels that certify the values Ψ(G) and Ψ(H) in Proposition 3.7, with K G (x, x) = t G − 1 and K H (y, y) = t H − 1.
First, we let 1 S×T (x, y) be the function which is 1 for (x, y) ∈ S × T and 0 otherwise. We claim that for each α > 0, the kernel on G H is positive semidefinite. To see why, note that for weights w x , We combine the kernels K G and K H by setting which is again positive semidefinite on G H. In particular, we take and for y ∈ V (H), . This shows that feasibility for ϑ(G) and ϑ(H) implies feasibility of K for ϑ(G H). Finally, if We now prove the other direction of the inequality. Let M (G) and M (H) be symmetric positive semidefinite V (G) × V (G) and V (H) × V (H) matrices, respectively, used to establish lower bounds for Ψ(G) and We claim, first, that M (G H) is positive semidefinite. Let w x be arbitrary weights for x ∈ V (G) V (H). Then we want to show that The left side is equal to By Cauchy-Schwarz inequality, specifically, this is the Cauchy-Schwartz inequality w, Applying these inequalities shows that the left side is at least which is nonnegative. Next

Asymptotics of packing bound functions on rectifiable sets
Our main result is a convergence theorem for all packing bound functions and all (H n , n)-rectifiable sets C satisfying M n (C) = H n (C). This recovers a statement similar to best packing on rectifiable sets [7], which is in fact a little stronger than Theorem 1.3. The structure of the proof will mimic in several places the proof of the Poppy Seed Bagel Theorem [28]. First, we will show the results for Jordanmeasurable subsets of R n . As in Section 2, A will denote an arbitrary packing bound function, C and C will be elements of B, and I n will be the unit cube in R n . Proof. This follows from the union bounds together with the following geometric fact: for each ε > 0, there exist R and ε > 0 such that for all r > R, rC contains disjoint copies of the unit cube occupying at least a 1 − ε fraction of the volume of rC and separated by distance at least ε , and is contained in a cover by copies of the unit cube of total volume fraction at most 1 + ε.
Choosing k such that A(2 k I n )2 −kn is within ε the limit δ A,n and such that 2 k ε ≥ 2, and applying both union bounds, we find that Proposition 4.2. If C is Jordan-measurable, then lim r→∞ A(rC)/r n = δ A,n L n (C).
Let {C i } be a finite collection of disjoint, closed cubes contained in C such that Dividing by r n and passing to the limit infimum as r → ∞, we conclude that lim inf r→∞ A(rC) r n ≥ δ A,n (L n (C) − ε), which completes the proof.
Next we prove the result for all compact sets. Proof. For every ε, there is a Jordan-measurable set C containing D such that L n (C \ D) < ε (see Remark 2.8). By the Lipschitz inequality, A(rC) ≥ A(rD), and we conclude the result by dividing by r n and taking the lim sup.
For the other direction, we first prove a lemma on compact Jordan-measurable sets: Lemma 4.4. For each compact Jordan-measurable B ⊆ R n and ε > 0 fixed, there is an ε > 0 such that for any compact subset C ⊆ B with L n (C) ≥ L n (B) − ε , Proof. This is a consequence of Proposition 2.14, using the fact that Minkowski content is equal to Lebesgue measure for compact subsets of R n (see [18, Theorem 3.2.39]).
We will need the Besicovitch covering lemma (as in [8,Theorem 8.6.10]), which we state as follows: Lemma 4.5. Let µ be a Borel measure on R p , let A ⊆ R p be a set of finite µmeasure, and let F be a set of balls such that for all x ∈ A, the infimum of r over the set of balls B(x, r) in F is 0 (that is, F contains balls of arbitrarily small radius centered at all points of A). Then there is a countable subcollection of F that are pairwise disjoint and cover µ-almost all A.
We are now prepared to prove the complementary inequality to Lemma 4.3 for all compact sets. This argument adapts the proof of [8,Theorem 8.6.11].
Theorem 4.6. Let A be a packing bound function. For any compact set C in R n , lim r→∞ A(rC) r n = δ A,n L n (C). Proof. Let ε > 0 be fixed. It suffices to prove that This set satisfies L n (C * ) = L n (C) by the Lebesgue density theorem. Now to apply Besicovitch covering lemma, we let the set F consist of all closed balls B(x, r) around points x ∈ C * such that r < 1 and where ε > 0 can be taken to be arbitrarily small. By the Besicovitch covering lemma, we can choose a countable disjoint subcollection B i of closed balls whose union covers almost all of C * and hence almost all of C.
Then since the balls are compact sets, they are separated from each other, and we may find a δ > 0 such that d(B i , B j ) ≥ δ for all distinct i, j ≤ N . Now Lemma 4.4 tells us that if ε is small enough relative to ε, then For r ≥ 2δ −1 , we can apply the union axiom in the definition of a packing bound function to obtain Combining these inequalities yields where the last equality holds because B i is Jordan-measurable. Finally, we obtain a lower bound of as desired.
Remark 4.7. The above theorem can be proved much more easily if the Euclidean bound is available for A.
Proposition 2.6 automatically gives an extension to arbitrary subsets of R n that uses Minkowski content instead of Lebesgue measure. Proof. Let C be the closure of C, which is compact and n-rectifiable and hence satisfies M n (C) = M n (C) = L n (C). By density, this implies for any ε > 0, and after dividing by r n the left and right sides both converge to δ A,n L n (C)(1+O(ε)) as r → ∞. Now, we wish to extend the result to n-rectifiable sets, in fact, to a slightly more general setting. We need some notions from geometric measure theory. Definition 4.9. For a measure µ, a (µ, n)-rectifiable set is a bounded Borel subset E of R d such that there are Lipschitz maps ψ i : R n → R d and bounded Borel subsets We have the following lemma, which is [18, Lemma 3.2.18]: Lemma 4.10. Let C be an (H n , n)-rectifiable set. Then for every ε > 0, there are compact subsets C 1 , C 2 , . . . ⊆ R n and bi-Lipschitz maps ψ i : C i → C with Lipschitz constant 1 + ε (in both directions) such that the sets ψ i (C i ) are disjoint and We will also need [8, Lemma 8.7.2]: Lemma 4.11. If C is a compact (H n , n)-rectifiable set with M n (C) = H n (C), then every compact subset K of C is (H n , n)-rectifiable and satisfies M n (K) = H n (K). Now we can prove our main theorem: Theorem 4.12. Let C ⊆ R d be an (H n , n)-rectifiable set with closure C satisfying the property that M n (C) = H n (C) < ∞, and let A be a packing bound function. Then lim r→∞ A(rC) r n = δ A,n M n (C).
In particular, the above theorem holds for all compact smooth n-manifolds or compact subsets of smooth n-manifolds embedded in R d for some d. Since compact n-rectifiable sets are also (H n , n)-rectifiable and satisfy M n (C) = H n (C), Theorem 4.12 implies Theorem 1.3.
Proof. By using the density property of A, we see that A(rC) ≤ A(r(1 + ε)C) ≤ A(r(1 + ε)C), which reduces the goal to proving the statement for C. From now on we assume C is compact.
We first prove the ≥ direction. In the notation of Lemma 4.10, choose N so that where the last inequality follows from the Lipschitz property. Thus, .
Furthermore, H n (ψ i (C i )) ≤ (1 + ε) n H n (C i ) because ψ i has Lipschitz constant 1 + ε (this bound follows directly from the definition of H n ; see, for example, [2, Proposition 2.49(iv)]), and thus H n (ψ i (C i )) ≤ (1 + ε) 2n H n ((1 + ε) −1 C i ). We conclude that We note that i ψ i (C i ) is a compact subset of C, and since M n (C) = H n (C) and the complement of i ψ i (C i ) has measure 0 under H n , it follows that M n (C) = H n ( i ψ i (C i )) = M n ( i ψ i (C i )) by Lemma 4.11. So by Proposition 2.14, and it suffices to prove the corresponding bound for i ψ i (C i ).

Now by density,
By the nested union and Lipschitz properties, Dividing by r n and taking the limit as r → ∞, we find that Letting ε → 0 completes the result.
Remark 4.13. We do not know whether Theorem 4.12 generalizes to sets C with non-integral Hausdorff dimension n. The limit of A(rC)/r n at least makes sense, and the value δ A,n can also sometimes be generalized for non-integral n. For the linear programming bound, for example, the radial Fourier transform is used, which can be written in terms of a Bessel function J ν with ν = d/2 − 1. By taking ν to be any real number greater than −1/2, we can formally write down a linear program for non-integral dimensional Euclidean space, but it is not clear whether it has any relationship to the limit of A(rC)/r n . If there is indeed a generalization in this direction, that would give geometric meaning to the versions of the linear program when the dimension is not integral. Could this program even be sharp in some non-integral dimensions?
5. The Euclidean limits of ϑ , ϑ, and ϑ + In this section, we consider the Euclidean limits of the packing bound functions corresponding to the sandwich functions ϑ , ϑ, and ϑ + . It turns out that δ ϑ ,n L n (B n 1 ) is the Cohn-Elkies linear programming bound [13] for the sphere packing density in R n , which is the best bound known for large n. In addition, the Euclidean limits of ϑ and ϑ + can be computed exactly, and they are equal to L n (B n 1 ) −1 , where L n (B n 1 ) is the volume of an n-ball of radius 1. In other words, δ ϑ,n = δ ϑ + ,n = π − n 2 Γ n 2 + 1 , and the resulting density bounds for the sphere packing problem are trivial: δ ϑ,n L n (B n 1 ) = δ ϑ + ,n L n (B n 1 ) = 1. Despite the weakness of the corresponding sphere packing bounds, the Euclidean limits δ ϑ,n and δ ϑ + ,n involve interesting mathematics. These ideas originated in Siegel's proof of Minkowski's theorem via Poisson summation (see, for example, Section 2.11.4 in [17]). Minkowski's theorem can be interpreted as saying that the maximum lattice packing density of a convex, origin-symmetric body is 1, which Siegel proved by applying Poisson summation to the convolution of the indicator function of the convex body with itself. It is natural to ask whether another auxiliary function could prove a better bound than 1. Siegel showed that the answer is no under certain hypotheses [41], which amounts to computing the limits δ ϑ,n and δ ϑ + ,n , and Gorbachev [22] rediscovered this theorem with a different proof.
In this section and the next, we will first discuss how the Delsarte problem gives a packing bound function, and then we will generalize the results to the Lasserre hierarchy from [35]. We will denote the packing bound functions corresponding to ϑ, ϑ , and ϑ + under Theorems 3.1 and 3.8 by ϑ, ϑ , and ϑ + again; this is an abuse of notation, but it will not cause any actual ambiguity. We will also define topological variants ϑ top , ϑ ,top , and ϑ +,top below, which will impose continuity.
First, we need a few definitions. By a finite signed measure, we mean a signed Borel measure µ on R d such that −∞ < µ(A) < ∞ for every Borel set A (bounded or not). If µ and µ 1 , µ 2 , . . . are finite signed measures, we say µ n is weak- * convergent to µ if every bounded, continuous function f : A positive semidefinite kernel on a bounded Borel set C is a function K : C ×C → R such that K(x, y) = K(y, x) and for every finite subset S of C and function w : S → R,  for all continuous, positive semidefinite kernels K on C. For simplicity, we often will call ν positive semidefinite on C, rather than C × C. For finitely supported positive semidefinite measures ν, C×C K(x, y) dν(x, y) ≥ 0 for all positive semidefinite kernels K, even if K is not continuous.
Proof. This follows immediately by considering matrices as finitely supported signed measures on C × C. Every measure ν as above gives a feasible solution for the corresponding sandwich function ϑ + , ϑ, or ϑ over some induced finite subgraph. Conversely, any feasible solution over an induced finite subgraph gives a feasible ν.
Taking the supremum over feasible solutions on both sides yields the result.
Similarly, the dual semidefinite programs are as follows: (1) ϑ (C) * is the infimum of t over all positive semidefinite kernels K on finite subsets S of C such that K(x, x) = t − 1 for all x ∈ S and K(x, y) ≤ −1 when |x − y| ≥ 2, (2) ϑ(C) * is the infimum of t over all positive semidefinite kernels K on finite subsets S of C such that K(x, x) = t − 1 for all x ∈ S and K(x, y) = −1 when |x − y| ≥ 2, and (3) ϑ + (C) * is the infimum of t over all positive semidefinite kernels K on finite subsets S of C such that K(x, x) = t − 1 for all x ∈ S, K(x, y) ≥ −1 for all x, y ∈ S, and K(x, y) = −1 when |x − y| ≥ 2. It follows from Proposition 3.7 that ϑ (C) = ϑ (C) * , ϑ(C) = ϑ(C) * , and ϑ + (C) = ϑ + (C) * , and that we can take S = C in the dual programs when C is finite.
The description in terms of finitely supported signed measures suggests that we should consider the analogous problems using arbitrary finite signed measures instead. Such measures have the advantage that one can average feasible solutions over the action of a compact Lie group of isometries and arrive at invariant semidefinite programs for packing problems [4]. We will refer to these as the topological analogues of the discrete ϑ + , ϑ, and ϑ , and denote them by ϑ +,top , ϑ top , and ϑ ,top , respectively. In other words, (1) ϑ +,top (C) is the supremum of ν(C × C) over finite, positive semidefinite signed measures ν on C such that ν(∆(C)) = 1 and ν ≤ 0 on the set of pairs (x, y) such that 0 < |x − y| < 2, (2) ϑ top (C) is the supremum of ν(C × C) over finite, positive semidefinite signed measures ν on C such that ν(∆(C)) = 1 and ν = 0 for pairs (x, y) such that 0 < |x − y| < 2, and (3) ϑ ,top (C) is the supremum of ν(C × C) over finite, positive semidefinite signed measures ν on C such that ν(∆(C)) = 1, ν = 0 for pairs (x, y) such that 0 < |x − y| < 2, and ν ≥ 0 everywhere. The topological analogue of the dual semidefinite programs for ϑ + , ϑ, and ϑ uses continuous kernels. We define (1) ϑ ,top (C) * to be the infimum of t over all continuous, positive semidefinite kernels K on C such that K(x, x) ≤ t − 1 for all x and K(x, y) ≤ −1 when |x − y| ≥ 2, (2) ϑ top (C) * to be the infimum of t over all continuous, positive semidefinite kernels K on C such that such that K(x, x) ≤ t−1 for all x and K(x, y) = −1 when |x − y| ≥ 2, and (3) ϑ +,top (C) * to be the infimum of t over all continuous, positive semidefinite kernels K on C such that such that K(x, x) ≤ t − 1 for all x, K(x, y) = −1 when |x − y| ≥ 2, and K(x, y) ≥ −1 everywhere.
Note that here we require just K(x, x) ≤ t − 1, rather than K(x, x) = t − 1 as in the finite case (Proposition 3.7). That change makes no difference in the finite case, but it will be convenient in Proposition 5.3.
The following proposition is the topological analogue of Proposition 3.7.
Proposition 5.2 (Weak duality). For each bounded Borel set C, Proof. Let A be ϑ ,top , ϑ top , or ϑ +,top . In each case, the hypotheses on ν, t, and K in the definitions of A(C) and A(C) * show that as desired.
The following proposition clarifies the relationship between the topological and discrete invariants. Proposition 5.3. Let C ⊆ R d be compact, and let C(ε) denote an ε-neighborhood around C. Then ϑ ,top (C) = lim ε→0 + ϑ (C(ε)). In addition, for any ε > 0, We do not know whether there is any compact set C ⊆ R d for which ϑ (C) = ϑ ,top (C). This corollary follows directly from Proposition 5.3, and will be generalized to the Lasserre hierarchy in Theorem 6.10. We do not know whether strong duality holds for θ or θ + , but they are less significant as packing bounds.
The proof of Proposition 5.3 will use the following lemma, which allows us to reduce a problem on an infinite topological space to a problem on a finite simplicial complex.
Lemma 5.5. For every compact subset C ⊆ R d and ε > 0, there is a finite, pure simplicial d-complex Y embedded in R d such that C ⊆ Y ⊆ C(ε) and every simplex in Y has diameter less than ε.
Here, saying Y is finite means the complex is built from finitely many simplices in R d , not that its geometric realization is a finite set.
Proof. Given a triangulation of R d with simplices of diameter less than ε, let Y consist of the simplices that are contained in C(ε). To obtain such a triangulation, we can start with a decomposition of a cube of diameter less than ε into d! simplices whose vertices are vertices of the cube, and then extend the decomposition to R d via reflection across the faces of the cube.
Proof of Proposition 5.3. We first prove that lim sup Choose a sequence ε n → 0 and ε n > 0 and feasible solutions ν n for ϑ (C(ε n )). Since all these measures are nonnegative, their supports are bounded, and their total measures are bounded by ϑ (C(max n ε n )), there is a weak- * convergent subsequence. By passing to such a subsequence, we can assume that the entire sequence is weak- * convergent.
Let ν be the weak- * limit of ν n ; then ν is a nonnegative measure because each ν n is nonnegative. It must be supported on n C(ε n ), which is equal to C by the assumption that C ⊆ R d is compact. It must be positive semidefinite because every continuous function f on C can be extended to a continuous function f on R d with compact support, and ν(f ⊗ f ) = ν(f ⊗ f ), which is the limit of the sequence ν n (f ⊗ f ), each term of which is nonnegative. Finally, ν must be supported on Therefore ν is a feasible solution for ϑ ,top (C). We also note that the objective ν(C × C) = ν(R d × R d ) is a continuous functional for the weak- * topology (because it is the integral of the constant function 1). By taking ν n to satisfy ν n (R d × R d ) ≥ ϑ (C(ε n )) − δ for very small δ > 0, we can guarantee that lim sup The desired inequality follows. Let A = ϑ, ϑ + , or ϑ . It remains to prove that for each ε > 0. The first inequality follows immediately from the definitions, and the second by weak duality in Proposition 5.3, so we just need to show the last inequality. In fact, we will prove an upper bound of A((1 + ε)C(ε)). That bound looks a little weaker, but (1 + ε)C(ε) is contained in a neighborhood of C(ε) of radius ε sup x∈C(ε) |x| = ε 2 + ε sup x∈C |x|, and therefore A((1 + ε)C(ε)) ≤ A(C(δ)), where δ = ε(1 + ε + sup x∈C |x|). Thus, we can obtain the desired upper bound simply by decreasing ε, to make δ as small as we want. To prove the upper bound of A((1 + ε)C(ε)), we will use the dual semidefinite program given in Proposition 3.7, and we will relate it to A top (C) * by discretizing space using a suitable simplicial complex.
Let Y be a finite, pure simplicial d-complex such that C ⊆ Y ⊆ C(ε) and all simplices in Y have diameter less than ε, as in Lemma 5.5, and let Y 0 be the set of vertices of simplices in Y . Each point x in Y can be written using barycentric coordinates as x = i a i x i with {x i } d i=0 ⊆ Y 0 defining a top-dimensional simplex in Y , i a i = 1, and a i ≥ 0. Moreover, such an expression is unique in the sense that two such expressions for x yield simplices that intersect in a face containing x, and a i = 0 for vertices x i not contained in the closure of that face. Now given a positive semidefinite kernel K on Y 0 , define a kernel L on all of Y by setting given barycentric coordinates x = i a i x i and y = j b j y j as above. The uniqueness of these coordinates show that L is well defined and continuous. To show that L is positive semidefinite, we must show that m,n w m w n L(x m , x n ) ≥ 0 for each finite set of points x n in Y with weights w n . If we use barycentric coordinates which is indeed nonnegative because K is positive semidefinite. Thus, L is a continuous, positive semidefinite kernel on Y . The remaining argument will split into cases, depending on whether we are analyzing ϑ , ϑ, or ϑ + .
First, suppose K is a feasible solution for ϑ (Y 0 ) * , with K(x, x) = t − 1 for all x. Then L(x, y) is a convex combination of values K(x i , y j ) with max(|x−x i |, |y−y j |) ≤ ε and therefore L(x, y) ≤ −1 for |x − y| ≥ 2 + 2ε. Furthermore, K takes its maximum value on the diagonal, because it is a positive semidefinite kernel, and thus L(x, x) ≤ t − 1. This construction shows that where the rescaling by a factor of 1 + ε takes care of the ε in the inequality |x − y| ≥ 2 + 2ε above, and rescaling space implies that By restricting L to C, we conclude that ϑ ,top (C) * ≤ ϑ ((1+ε)C(ε)), which concludes the proof.
Our strategy for computing the Euclidean limits will be to compute the corresponding Euclidean limits of the topological analogues. Even though we do not know whether they are packing bound functions, their limits are still well defined. The following lemma shows that the Euclidean limits of the discrete and topological versions of a sandwich function are the same. Lemma 5.6. Let A be a packing bound function, and let A top be a real-valued function defined on compact subsets of Euclidean space and satisfying whenever ε > 0. Letting I n = [0, 1] n be the unit cube in R n as usual, Proof. This follows immediately by noting that We are ready for the main result of this section, an explicit description of the Euclidean limits of ϑ , ϑ, and ϑ + .
Theorem 5.7. The quantity L n (B n 1 )δ ϑ ,n is the linear programming bound for the sphere packing density in R n , while L n (B n 1 )δ ϑ,n = L n (B n 1 )δ ϑ + ,n = 1. The key step in the proof of the theorem is the following lemma. Recall that a function f : R n → R is positive semidefinite if the kernel K defined by K(x, y) = f (x − y) is positive semidefinite. In particular, f must be an even function.
Note that without loss of generality, we can assume these functions f are radial functions (by averaging over all rotations), because the constraints and objective functions are radially symmetric. Furthermore, we can assume that f has compact support; this is automatic for ϑ and ϑ + , and can be proved as follows for ϑ by mollifying a feasible function f . The convolution 1 B n R/2 (0) * 1 B n R/2 (0) is a continuous function supported in B n R (0), and it is positive semidefinite since its Fourier transform is 1 B n R/2 (0) 2 . If we normalize it by setting g R := 1 B n R/2 (0) * 1 B n R/2 (0) /L n (B n R/2 (0)) so that g R (0) = 1, then g R converges pointwise to 1 everywhere as R → ∞. In particular, the product f R := f · g R is continuous and supported in B n R (0), it is positive semidefinite by the Schur product theorem (Theorem 7.5.3 in [30]), and lim R→∞ f R (0) = f (0) by dominated convergence. By replacing f with f R , we can come arbitrarily close to the ratio f (0)/ f (0) using compactly supported functions.
Proof. We will apply Lemma 5.6 and Proposition 5.3 throughout. Let K be a continuous, positive semidefinite kernel on rI n ⊆ R n , such that K is a feasible solution for one of the dual topological bounds. We extend it by 0 to give a positive semidefinite kernel on R n . Define f : R n × R n → R by the formula f (x, y) = 1 r 2n R n K(x + z, y + z) + 1 rI n ×rI n (x + z, y + z) dz.
Then f is translation invariant (i.e., f (x+t, y+t) = f (x, y)) and compactly supported, and it is a continuous function because translating integrable functions is continuous under the L 1 norm. Thus, the function f : R n → R given by f (x, y) = f (x − y) is well defined and a continuous, compactly supported function. The function f is a positive semidefinite kernel because it is an integral of such kernels, and so f is positive semidefinite by definition. We have Now suppose K is feasible for ϑ ,top (rI n ) * . Then f (x, y) ≤ 0 for |x − y| ≥ 2, because the integrand defining f (x, y) cannot be positive in this case. Thus, the infimum over f satisfying the conditions in the lemma statement is bounded above by r −n ϑ ,top (rI n ) * .
Finally, suppose K is feasible for ϑ +,top (rI n ) * . Then f (x, y) ≥ 0 for |x − y| ≤ 2, because the integrand defining f (x, y) is nonnegative. Therefore, we conclude one inequality for each of the statements in the lemma.
For the other direction, suppose f : R n → R is continuous, positive semidefinite, and integrable, with f (0) > 0. As noted after the lemma statement, we can also assume that supp(f ) ⊆ B n R (0) for some R. It is not hard to show that lim r→∞ rI n ×rI n f (x − y) dx dy r n = f (0).
Fix ε > 0, and let r be large enough that (5.1) rI n ×rI n f (x − y) dx dy ≤ r n (1 + ε) f (0). and r > 2R. Let J n = [R, r − R] n ⊆ rI n , and define K : J n × J n → R by . We claim that K is positive semidefinite. Let S be a finite subset of J n , and let w x be real weights for x ∈ S. It suffices to show that (5.2) x,y∈S w x w y K(x, y) ≥ 0.
To do so, we define a signed measure ν by where δ x is a unit mass placed at the point x and µ r is the Lebesgue measure on rI n . Positive semidefiniteness of f implies such that f (x) ≥ 0 for |x| ≤ 2, f (x) = 0 for |x| ≥ 2, and f (0) > 0. These problems were solved by Gorbachev [22], and Siegel had given the same answer to essentially the same problems in [41]. For the convenience of the reader, we will sketch Gorbachev's proof.
The optimal function f is the convolution and the objective is f (0)/ f (0) = L n (B n 1 ) −1 . The proof of optimality is a consequence of the quadrature formula of Ben Ghanem and Frappier [6], which incidentally also shows that the Levenshtein bound is optimal among certain band-limited solutions to the linear programming bound problem [21,11]. Specifically, we use the p = 0 case of Lemma 4 in [6], under the minimal hypotheses established by Grozev and Rahman [24] (which are not stated explicitly for this identity in [6] but follow from the same proof). For any continuous, radial function f : R n → R supported on B n r (0) whose Fourier transform is integrable, the formula says that where the node points λ m are the positive roots of the Bessel function J n/2 and the coefficients α m are certain explicit quantities with α m > 0. Any feasible solution f to problems (1) or (2) above satisfies these hypotheses with r = 2 and has f ≥ 0 (see, for example, Corollary 1.26 in Chapter I of [43] for why f is integrable). Since the infinite sum is nonnegative, we conclude that Remark 5.9. In the one-dimensional case, 1 = L 1 (B 1 1 )δ pack,1 ≤ L 1 (B 1 1 )δ ϑ ,1 ≤ L 1 (B 1 1 )δ cov,1 = 1. In other words, the fact that sphere covering and sphere packing have the same density in R 1 implies that the linear programming bound must be sharp in that case. Of course this fact can be proved directly by exhibiting a closed-form auxiliary function, but it is interesting to prove it without the need to construct any explicit auxiliary function.
6. The Lasserre hierarchy for sphere packing The Lasserre hierarchy [36] is an important family of semidefinite relaxations of the independence number; this hierarchy starts with ϑ and extends it to successively stronger bounds, which converge to the exact independence number. Based on foundations laid by Laurent [37] and by de Laat and Vallentin [35], in this section we show that the Lasserre hierarchy consists of sandwich functions, and we write their Euclidean limits as optimization problems. The net result is a generalization of the linear programming bound to a hierarchy of bounds that converge to the exact sphere packing density. 6.1. Review of bounds for compact spaces. A topological packing graph is a graph and a Hausdorff topological space such that every finite clique is contained in an open clique. Equivalently, each vertex and each edge is contained in an open clique. Every graph is a topological packing graph with the discrete topology, and every compact topological packing graph has finite independence number (and furthermore finite clique covering number, which is an even stronger assertion). The edges in a topological packing graph indicate pairs of vertices that are too close together to appear in the same packing, and independent sets correspond to packings.
The Lasserre hierarchy on compact topological packing graphs was introduced by de Laat and Vallentin [35]. We begin by reviewing this hierarchy. Definition 6.1. We set the following notation: (1) For a topological space V , let C(V ) be the set of continuous functions from V to R, let C 0 (V ) ⊆ C(V ) consist of the functions that vanish at infinity, and let C c (V ) ⊆ C(V ) consist of those with compact support. We often write I t instead of I t,G when the context is clear. We can think of I t as a moduli space of packings on G by independent sets of size at most t, and we will often use the covariant functoriality of these moduli spaces for morphisms in the category G.
When G is a compact topological packing graph, the space I t is compact by Lemma 1 in [35], and we will make frequent use of the duality between C(I t ) and M ± (I t ). A key role will be played by an operator For f ∈ C(I t × I t ) and S ∈ I 2t , the function A t f is defined by We define the operator A * t : M ± (I 2t ) → M ± (I t × I t ) to be the adjoint of A t . Specifically, for µ ∈ M ± (I 2t ), the signed measure A * t µ is characterized by for all f ∈ C(I t × I t ).
We will use the following convergence property, where α(G) is the independence number of G (i.e., the size of the largest packing): Proposition 6.5 (de Laat and Vallentin [35]). Let G be a compact topological packing graph. Then Remark 6.6. The paper [35,Theorem 2] only gives the statement for las ,top α(G) (G), but their proof extends word for word to las top α(G) (G). The empty set is an isolated point in I t , and for some purposes it is useful to omit it. There is an equivalent formulation of las t without {∅} using the Schur complement. For µ a measure on I t \ {∅}, let (A =∅ t ) * µ be the restriction of A * t µ to I t \ {∅} × I t \ {∅}, and define the external tensor product µ ⊗ ν of two measures as the measure taking value µ(A)ν(B) on A × B. The following proposition follows from taking the Schur complement: Here µ ⊗ µ refers to a measure on I t \ {∅} × I t \ {∅}, so that it is comparable with (A =∅ t ) * µ. Proof. Define a new measure µ on I 2t that is equal to µ on I 2t \ {∅} and puts a mass of 1 on the point ∅. The version of the Schur complement in [35,Lemma 9] shows that if (A =∅ t ) * µ − µ ⊗ µ is positive semidefinite, then A * t µ is a positive semidefinite measure and so µ is a feasible measure for las ,top t (G).
Remark 6.8. One can consider a weakened hierarchy in which the positive semidefiniteness condition above is weakened to the conditions that (A =∅ t ) * µ is positive semidefinite and that This weakening was discussed briefly in [34, equation (3) in Section 2.1]. In particular, for the case t = 1, this weakening of the hierarchy is equivalent to ϑ ,top . Furthermore, de Laat and Vallentin [35] show that ϑ ,top is actually equivalent to las ,top 1 .
The convex dual of the optimization problem defining las ,top t (G) is as follows: Definition 6.9. For a compact topological packing graph G, we define las ,top t (G) * to be the infimum of K(∅, ∅) over continuous kernels K : By [35,Theorem 1], strong duality holds: Note that the proof of this theorem in the published version of [35] contains a minor gap, which is filled in the arXiv version.
6.2. The Lasserre hierarchy as sandwich functions. Definition 6.11. For a finite graph H and for A = las t or las t , define las t (G) = las top t (G) and las t (G) = las ,top t (G). For a discrete graph G, possibly infinite but with finite clique covering number, we define las t (G), resp. las t (G), to be the supremum over all induced finite subgraphs H ⊆ G of las t (H), resp. las t (H).
This definition coincides on finite graphs with las ,top t (G). We do not know whether they agree on all compact topological packing graphs, even for the case t = 1 (which is ϑ ). Using Theorem 6.13 below, for compact subsets of R n , this question can be reformulated purely in terms of las .
Theorem 6.12. The functions G → las t (G) and G → las t (G) are sandwich functions.
Proof of Theorem 6.12. Recall that Lemma 3.9 shows that we only need to check the statement on finite graphs. The case when G is a point is clear.
Consider a graph homomorphism from G to H, where G and H are finite graphs, and let f : V (G) → V (H) be the underlying map on vertex sets. Let us also use f for the induced map on independent sets f : I =k,G → I =k,H for each k. If µ is a measure on I t,G , we define the measure f * µ on I t,H via First, we show that if µ is feasible for las t (G), then f * µ is feasible for las t (H) with the same objective function value. If A * t µ is positive semidefinite on I t,G × I t,G , then A * t f * µ is positive semidefinite on I t,H × I t,H . To see why, we will use (6.1); for finite graphs, it says that Let w J be a set of real weights for J ∈ I t,H . If we set w K = w J for K ∈ I t,G with f (K) = J and w K = 0 otherwise, then This shows that las t (G) ≤ las t (H). Furthermore, if µ is nonnegative, then f * µ is nonnegative, and thus las t (G) ≤ las t (H) as well.
All the remains to check is the union axiom. Let G and H be disjoint graphs, and consider G H. We first want to show that las t (G H) ≥ las t (G) + las t (H) and similarly for las t (G H). Let µ G and µ H be measures on I 2t,G and I 2t,H . To define a measure µ on I 2t,G H , it suffices to define the measure of a singleton {S} with S ∈ I 2t,G H . We define this by Finally, we want to show that las t (G ∪ H) ≤ las t (G) + las t (H) and similarly for las t . Let µ be a measure on I 2t,G∪H and consider its restriction µ G to I 2t,G and restriction µ H to I 2t,H . We see that If µ is nonnegative, then µ G and µ H are, and if A * t µ is positive semidefinite, then A * t µ G and A * t µ H are (they correspond to submatrices of the positive semidefinite matrix for G H). Finally, By starting with a feasible point for las t (G H) that is arbitrarily close to the optimum, we conclude that las t (G ∪ H) ≤ las t (G) + las t (H), and similarly las t (G ∪ H) ≤ las t (G) + las t (H).
Because these functions are packing bounds functions, we can conclude that a Euclidean limit must exist. In the next section, we formulate the Euclidean limit of las t and las ,top t in terms of a semidefinite program.
6.3. The Euclidean limit of the Lasserre hierarchy. For any subset C ⊆ R n , consider the graph with vertex set C and edges consisting of pairs (x, y) with 0 < d(x, y) < 2. If C is bounded, we can obtain las t (C) by treating the graph as a discrete graph. If C is compact, then the graph is a compact topological packing graph and we can obtain las ,top t (C). For any C, we obtain a topological packing graph, and thus the collection I t,C of independent sets of size at most t has a topology, but it will not be compact in general. For example, I t,R n admits an action of R n by translation.
Much like the case of ϑ (C), we can interpret las t (C) as a supremum over finitely supported measures coming from finite subgraphs of C. From this point of view, the inequality las t (C) ≤ las ,top t (C) is immediate when C is compact. The following theorem gives a more precise relationship. Theorem 6.13. Let C be a compact subset of R d , and let C(ε) be the closure of C(ε), the ε-neighborhood of C. Then las ,top t (C) = lim ε→0 + las t (C(ε)) = lim ε→0 + las ,top t (C(ε)).
We will prove both inequalities separately. One inequality is immediate by inclusion of C ⊆ C(ε). For the other direction, since C(ε) is compact, there is a measure achieving the optimal value of las ,top t (C(ε)) for any ε. Take µ n achieving this for las ,top Using this notion of rounding, we define L(J, J ) as the expected value EK(r(J), r(J )) of K(r(J), r(J )) when we round each point in J ∪ J independently. Then L is a continuous function on I t,Y × I t,Y . To show that it is a positive semidefinite kernel, we must show that for all weights w J ∈ R for J ∈ I t,Y that vanish for all but finitely many J, J,J ∈I t,Y w J w J L(J, J ) ≥ 0.
To prove this inequality, consider randomly rounding the points of Y independently. Then J,J ∈I t,Y w J w J L(J, J ) = E J,J ∈I t,Y w J w J K(r(J), r(J )), which is nonnegative because K is a positive semidefinite kernel.
All the remains to check is the conditions on A t L for a feasible kernel. If A t K({x}) ≤ −1 for all x ∈ Y 0 , then A t L({x}) ≤ −1 for all x ∈ Y , because A t L({x}) = EA t K(r({x})). However, the case of A t L(S) with |S| ≥ 2 is slightly more subtle. The issue is that r(S) may not be an independent set even if S is. However, if the minimal distance between points in S is at least 2 + 2ε, then r(S) must always be an independent set. In that case, if A t K(S) ≤ 0. In other words, we obtain a feasible kernel for (1 + ε) −1 C, rather than C.
Corollary 6.14. Let I n be the unit cube in R n . Then Proof. This corollary follows from Theorem 6.13 together with the fact that I n (ε) embeds into (1 + 2ε)I n .
We are now ready to give the Euclidean limit of the Lasserre hierarchy. Let R n act on Radon measures on I 2t,R n by translation, and consider translation-invariant measures. Any translation-invariant measure µ will restrict to I =1,R n as some multiple of the Lebesgue measure, and we define µ(0) to be this multiple. That is, µ| I =1,R n (C) = µ(0)L n (C) for Borel sets C ⊆ R n . Definition 6.15. Let las t (R n ) be the supremum of µ(0) over all translation-invariant Radon measures µ on I 2t,R n such that (1) A * t µ is positive semidefinite as a measure on I t,R n × I t,R n , (2) µ is nonnegative, and (3) µ({∅}) = 1. We call such a measure µ a correlation measure of order 2t with center density µ(0).
Let P be a periodic packing in R n , i.e., the union of finitely many translates of a lattice Λ such that no two points of P are closer than distance 2 apart, and let D be a fundamental parallelotope for Λ. To obtain a correlation measure from P, we define µ P to be the Radon measure on I 2t,R n characterized by I 2t,R n f dµ P = 1 L n (D) D S⊆P+v |S|≤2t f (S) dv for compactly supported, continuous functions f : I 2t,R n → R. In other words, µ P | I =k is essential the correlation function of order k for P. The purpose of averaging over v ∈ D is to make µ P translation-invariant. The center density µ P (0) is the usual center density of the sphere packing P, i.e., N/L n (D) if P consists of N translates of Λ.
To show that µ P is a correlation measure, all that remains is to prove that A * t µ P is positive semidefinite. Let K : I t × I t → R be a continuous, positive semidefinite kernel with compact support. Then I t,R n ×I t,R n K dA * t µ P = I 2t,R n A t K dµ P The main result of this section is that the quantity las t (R n ) is the Euclidean limit of the packing bound function las t . Theorem 6.16. For each n and t, las t (R n ) = δ las t ,n .
Proof. Because of Corollary 6.14, it suffices to check that lim r→∞ las ,top t (rI n ) r n = las t (R n ).
If µ is a correlation measure of order 2t (i.e., feasible for las t (R n )), then restricting µ to I 2t,rI n gives a feasible measure for las ,top t (rI n ) with objective r n las t (R n ). This shows that las ,top t (rI n ) r n ≥ las t (R n ) for any r.
Definition 6.18. Let las t (R n ) * be the infimum of K(∅, ∅) over all continuous kernels K : I t,R n × I t,R n → R with compact support such that (1) K is positive semidefinite, (2) A t K(S) ≤ 0 whenever |S| > 1, and (3) I =1,R n A t K dL n ≤ −1, where we view Lebesgue measure L n as a measure on I =1,R n by identifying I =1,R n with R n . We call such a K an auxiliary function of order 2t.
Remark 6.19. One unsatisfying feature of the above optimization problem is that the kernel K cannot be made invariant under the action of R n , as that would require that K(∅, {x}) take a constant value, contradicting the third condition in the definition.
To formulate a dual problem in a way that allows for solutions invariant under the group action, one could use the Schur complement formulation discussed in Remark 6.8, at the cost of complicating the statement of the optimization problem.
Let µ be a correlation measure and K an auxiliary function, both of order 2t. Weak duality follows immediately from The relationship with las ,top t is simple. Given any correlation measure µ of order 2t for R n , restricting µ to I 2t,rI n gives a feasible measure for las ,top t (rI n ) with objective r n µ(0), and letting r → ∞ shows that las t (R n ) ≤ δ las t ,n by Corollary 6.14 (this argument is the first part of the proof of Theorem 6.16). Conversely, suppose K is any feasible kernel for las ,top t (rI n ) * . Then extending r −n K by zero gives a feasible kernel for las t (R n ) * with objective r −n K(∅, ∅), and thus las t (R n ) * ≤ δ las t ,n .
By combining these inequalities with Theorem 6.16, we obtain strong duality: Theorem 6.20. For each n and t, las t (R n ) = las t (R n ) * = δ las t ,n .
Note that the optimum in las t (R n ) * will generally not be achieved unless we broaden the class of auxiliary functions.
Remark 6.21. The Lasserre hierarchy bound las 1 (R n ) is equivalent to the linear programming bound, because las ,top 1 = ϑ ,top , as shown in [35,Theorem 3]. It is therefore sharp for n = 1, 8, and 24, and conjecturally for n = 2 (see [13,44,14]). For which other pairs (n, t) might there be a sharp bound? It is unclear whether these sharp bounds are a peculiar phenomenon for t = 1, or whether we can expect further cases with t > 1. It is even conceivable that for each dimension n, some finite value of t yields a sharp bound.
One hint that additional sharp bounds might be possible in Euclidean space comes from the case of binary codes of block length 20 and minimal distance 8. Gijswijt, Mittelmann, and Schrijver [20] obtained a sharp bound for the size of such a code using las 2 (see Section VIII of their paper for the reduction to las 2 ).