Results on the reduction from Label Cover, Lipschitz functions on tori, and alignment of lists

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.

• Label Cover instances with value one or small value — Theorem 2.1. Assume the hypotheses (PCP) and (PR). For every sigma > 0 there are finite answer sets and a polynomial-time map from 3-CNF formulas to Label Cover instances (a list of tests, each with a left question, a right question and a map of the answers) with value 1 if the formula is satisfiable and value at most sigma otherwise.
• The link distance — Lemma 3.2. The least total length of a sequence of links (sup circle distance inside a copy, length 0 between x and its pullback along a test) is symmetric, satisfies the triangle inequality, is at most the sup distance inside a copy, and is preserved by the half shift.
• The graph of a satisfiable instance has a proper coloring with three colors — Theorem 5.2. If all tests of the Label Cover instance can be satisfied, the first branch does not occur and the graph of the reduction has a proper coloring with three colors: the phase of the location at the satisfying answers changes by at least 3/8 along every edge.
• Odd Lipschitz extension from a finite set — Lemma 1.1. A function with values in [-1,1] on a finite subset of T^M that is invariant under the half shift, L-Lipschitz for the sup distance and odd, extends to a function on T^M with the same properties.
• Decomposition of a function by means over coordinates — Lemma 2.3. f is the sum of the pairwise orthogonal functions f_A (apply Q_i for i in A and E_i for i outside A); Q_i f is the sum of the f_A with i in A, and the mean over the coordinates outside S is the sum of the f_A with A inside S.
• Two bounds on influences that do not depend on the number of coordinates — Proposition 4.1. For L and eps there are beta > 0 and K such that every L-Lipschitz H: T^n -> [-1,1] (sup distance) with mean 0 and mean square > eps has a coordinate with influence at least beta, and at most K coordinates have influence at least beta/2; beta and K do not depend on n. The proof uses Austin's junta theorem, which is proved in the course Hypercontractivity on a torus and juntas for Lipschitz functions.
• The function of an independent set — Lemma 1.2. For an independent set with the set A of locations, f = e - e o T with e = (1 - 32 dist(., A))_+ has values in [-1,1], is odd, equals 1 on A, is constant across links of length 0 and is 64-Lipschitz inside every copy.
• Compatibility along a chain — Lemma 2.1. For the fixed odd 64-Lipschitz extensions F_i along a chain: |F_j(x) - F_i(x o pi_ij)| <= 64/D for i <= j and all x in T^(M_j).
• Bounded lists of a set of layers — Lemma 4.1. For a set I of at most s layers there are lists S_I^j of rotations with total size at most d = J(64s,gamma)(m+1)^s such that for every choice of coefficients the function h_(I,t) is within gamma in L^2 of a function of the listed rotations; the lists are determined by the tuple of the least layer and the maps to the other layers of I.
• Lists of separated sets of layers are disjoint with high probability — Lemma 5.1. If the value of the instance is at most sigma and max I < min J, the lists A_I and A_J in the last layer meet with probability at most d^2 sigma over the chain.
• The alignment theorem — Theorem 1.1. For s, d >= 1 and eta > 0 there are r >= s and a rational law on the s-subsets of [r] such that for every family of lists of size at most d, indexed by the nonempty sets of at most s elements of [r], with A_I and A_J disjoint whenever max I < min J, a random s-set B is bad with probability at most eta; B is not bad if every label can be given an element of B that lies in every I inside B on whose list the label stands. Proved in the following lesson.
• Alignment for s = 3 with an explicit law — Proposition 1.6. For s = 3 and r >= 4, at most d of the r - 2 sets {1,b,r} are bad for a family of lists that respects separation.
• The minimax theorem for finite matrix games — Theorem 3.2. For a real matrix b: the minimum over laws nu on the rows of the largest column mean equals the maximum over laws rho on the columns of the least row mean. Proved by separating 0 from a closed convex set.
• Ramsey's theorem for t-subsets — Theorem 4.1. For t, q, k there is R such that every coloring of the t-subsets of a totally ordered set with at least R elements with q colors has a homogeneous subset with k elements.
• Consistent laws of patterns if alignment fails — Proposition 5.1. If for some xi > 0 no r and no law keep the probability of a bad set at most xi for all patterns, there are laws P_t of patterns on [t], consistent under restriction to subsets and renaming in order, with the full set bad with probability at least xi under P_s.
• The common index — Theorem 2.4. In the random pattern on the rational numbers built from consistent laws, with probability 1 every label has an element that lies in all of its occurrence sets (its cut, the supremum of the minima of the occurrence sets); so no finite set is bad.
• Aligned pairs occur with high probability — Proposition 4.1. With r and the law of B from the alignment theorem for s, d and eps: a chain and a set B fail to be aligned with probability at most 4^r d^2 sigma + eps.
• The density bound at an aligned pair — Proposition 1.1. Assume the conditions (P1) to (P6) on the numbers. For an aligned pair of a chain and a set B, the vertex of the experiment lies in a given independent set with conditional probability less than 6 eps.
• Hardness of finding large independent sets in three-colorable graphs — Theorem 7.1. Assume the hypotheses (PCP) and (PR). For every 0 < delta < 1/3 there is a polynomial-time map from 3-CNF formulas to graphs: a satisfiable formula gives a graph with a proper coloring with three colors, and a formula that is not satisfiable gives a graph in which every independent set has fewer than delta |V| vertices.

Reading order

Six lessons with complete proofs, except for two theorems of the literature that are named hypotheses: the PCP theorem and the parallel repetition theorem, which enter through the Label Cover instances of the first lesson. A theorem of T. Austin on Lipschitz functions of many variables, stated in the second lesson, is proved in the course Hypercontractivity on a torus and juntas for Lipschitz functions. The first lesson builds the graph and proves the three-coloring. The second and third turn an independent set into Lipschitz functions and short lists of answers. The fourth and fifth prove the alignment theorem, a statement about families of lists that is independent of the rest. The sixth proves the bound for independent sets and the theorem. The constants of the reduction exist for every delta; the proof gives no bounds for them.