Results on convexity, sampling, electrical flows, Poisson sums and embeddings into l_p, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Caratheodory — Lemma 1.1. A point of the convex hull of a set in an affine subspace of dimension k is a convex combination of at most k+1 points of the set.
• Separation — Lemma 1.3. A point outside a compact convex set, or a disjoint compact convex set, is strictly separated by a linear functional.
• Barycenters — Lemma 1.4. The expectation of a random vector with values in a compact convex set lies in the set.
• Exact discretization (Ball) — Proposition 2.1. Every n-point subset of an L_p space embeds isometrically into l_p^(n choose 2), 1 <= p < infinity.
• Counting lower bound — Proposition 3.1. d_p(n, D) >= log n / log(1 + 2D).
• Disjoint supports — Lemma 4.2. For p != 2, the parallelogram identity holds for u, w in l_p^d exactly when u and w have disjoint supports.
• Exact embeddings need quadratically many coordinates (OpenAI) — Proposition 4.4. For p != 2 and n >= 9, d_p(n, 1) >= floor((n-1)/4)^2.
• Sums of bounded variables — Lemma 2.1. Averages of d independent copies of a variable in [0, R] deviate from the mean by more than epsilon with probability at most 2 exp(-d epsilon^2 / (2 R^2)).
• Weighted moment criterion (OpenAI) — Lemma 3.1. If for every positive weighting of the pairs a bounded random normalized gradient has weighted moment error at most eta b, the points embed with distortion ((1+3eta)/(1-3eta))^(1/p) in dimension O(K^(2p) log n / (eta^2 b^2)).
• Reduction of the upper bound — Proposition 4.1. Parameters b, K >= 1 with log K <= C (log n)^gamma for large n give the upper bound of the theorem.
• Projections as heat integrals — Lemma 1.1. The orthogonal projection onto the image of A is the integral of A exp(-t A^T A) A^T over t > 0.
• Heat kernel — Lemma 1.2. The heat kernel of a weighted connected graph is positive, conserves mass and tends to the constants.
• Localization of electrical flows (Gurel-Gurevich, Nachmias, Sachdeva) — Lemma 1.3. The entrywise absolute value of the transfer projection of a connected graph on n vertices has norm at most 2 log n.
• Weighted projection (OpenAI) — Lemma 2.1. For every positive weighting lambda there is sigma >= lambda/2 whose orthogonal projection onto normalized gradients has absolute row sums at most 4 log(2n).
• Homogeneous increments — Lemma 1.1. Under nu every normalized increment has nu(|v_e| > a) = a^-p and the same size density.
• Splitting of signed Poisson sums — Lemma 2.1. A signed Poisson sum on a disjoint union has the law of the sum of independent sums on the parts.
• Signed Poisson formulas — Lemma 2.2. Characteristic function, moment generating function, mean and variance of a signed Poisson sum.
• One law for all pairs (OpenAI) — Lemma 3.1. For 1 < p < 2 all coordinates of the heavy-tailed gradient Y have the same symmetric law mu_p.
• Tails of mu_p — Lemma 3.2. c a^-p <= mu_p(|y| > a) <= C a^-p for a >= 1.
• Parameters below two (OpenAI) — Proposition 4.2. For 1 < p < 2 the clipped projected gradient gives b, K with log K <= C (log n)^(2-p).
• Energy of the ramp — Lemma 1.1. The ramp of overlapping truncations has p-energy b = p log 2 (l^p + 2 sum_{j<l} j^p) on every pair.
• Projection error (OpenAI) — Lemma 2.1. The p-th power of the projection error of the ramp is at most C H^(p-2) (l+1).
• Nearly additive moments (OpenAI) — Lemma 3.1. For q > 2 the q-th moment of a signed Poisson sum lies between the integral of |h|^q and (1+epsilon) times it plus C times the q/2-th power of the integral of h^2.
• Parameters above two (OpenAI) — Proposition 5.1. For p > 2 the truncated Poisson sample of the projected ramp gives b, K with log K <= C (log n)^(1-2/p).
• Subpolynomial dimension reduction in L_p (OpenAI) — Theorem 5.1. For 1 < p < infinity, p != 2, D > 1: log n / log(1+2D) <= d_p(n, D) <= exp(C (log n)^gamma(p)); and floor((n-1)/4)^2 <= d_p(n, 1) <= n choose 2 for n >= 9.

Reading order

Read the lessons in order; each uses the notation and results of the previous ones.