Results on polars, convexified packing, compression and symmetric forms, 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.

• Bipolar theorem — Lemma 1.1. For a symmetric convex body K in R^n, the polar is a symmetric convex body, the bipolar is K, and the gauge of each body is the support function of the other.
• From a matrix to a pair of bodies — Lemma 2.1. A finite matrix with rows pairwise 1-separated in the maximum norm, and M functions approximating every signed column combination of l1-norm at most 1 within eps, gives bodies K and L = cube with N(K, L) >= |X| and N(L°, (6 eps + 2t) K°) <= M.
• What a counterexample needs — Corollary 2.2. If log |X| > b log M and 6 eps + 2t <= 1/a, the bodies violate the right-hand duality inequality for a and b.
• Convex separation by functionals — Lemma 3.1. A sequence is B-convexly separated if and only if there are y_j in the polar of B with <y_j, x_j - x_i> >= 1 for all i < j.
• Duality for convexified packing (Artstein, Milman, Szarek, Tomczak-Jaegermann) — Theorem 3.2. For symmetric convex bodies K and B, the convexified packing number of K by B is at most the square of that of the polar of B by half the polar of K.
• Packing below covering — Lemma 3.3. The convexified packing number of T by B is at most the covering number of T by B/4.
• The logarithmic profile — Lemma 1.1. The profile is a weighted sum of indicators of distance balls, and enlarging every radius j to 3j + 2 adds at most log 3 / log(h + 1).
• Uniform compression — Proposition 2.1. Nonnegative column combinations of mass at most 1 have a list of Q functions approximating each within -3 theta and +theta, with log Q <= hs log q + C(h, theta, u), where q bounds the number of classes of each partition.
• Signed compression — Corollary 2.2. Signed column combinations of l1-norm at most 1 are approximated within 6 theta by a list of at most Q^2 functions.
• Zero bound (Schwartz, Zippel) — Lemma 1.1. A nonzero polynomial of total degree at most d over F_p vanishes at a uniformly random point with probability at most d/p.
• Robust directions — Proposition 2.1. For a prime p > h^2 u^(2h) there are t_1, ..., t_u in F_p^r such that every nonzero symmetric h-linear form is nonzero on all h-tuples from some T with |[u] \ T| <= theta u.
• Separated rows — Proposition 3.1. Contracting symmetric h-linear forms with the t_i gives partitions with at most p^(D_(h-1)) classes in whose graphs distinct forms are at distance greater than h for some T; the rows are 1-separated.
• Failure of the duality conjecture for metric entropy (OpenAI) — Theorem 4.1. For all a, b >= 1 there are n and a symmetric convex body K in R^n with log N(K, [-1,1]^n) > b log N(B_1^n, a^(-1) K°).
• The left-hand inequality — Corollary 4.3. For all a, b >= 1 there are n and a symmetric convex body L in R^n with log N(B_1^n, L) < (1/b) log N(L°, a [-1,1]^n).
• Covering against convexified packing — Corollary 4.4. For all alpha, beta >= 1 there are n and a symmetric convex body K in R^n with log N(K, [-1,1]^n) > beta log of the convexified packing number of K by alpha^(-1) [-1,1]^n.

Reading order

Read the lessons in order. The first reduces the counterexample to a matrix and proves the duality theorem for convexified packing. The second gives the approximation list. The third constructs the matrix over a finite field and proves the theorem.