\documentclass[11pt,letterpaper]{article} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools,mathrsfs} \usepackage{microtype} \usepackage{enumitem} \usepackage[hidelinks]{hyperref} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\T}{\mathbb T} \newcommand{\R}{\mathbb R} \newcommand{\Z}{\mathbb Z} \newcommand{\E}{\mathbb E} \newcommand{\eps}{\varepsilon} \newcommand{\X}{\mathscr X} \newcommand{\ind}{\mathbf 1} \newcommand{\NAE}{\mathrm{NAE}} \newcommand{\LO}{\mathrm{LO}} \DeclareMathOperator{\dist}{dist} \DeclareMathOperator{\val}{val} \DeclareMathOperator{\PCSP}{PCSP} \DeclareMathOperator{\PMMSNP}{PMMSNP} \setlength{\emergencystretch}{1.5em} \setlist[enumerate]{topsep=4pt,itemsep=3pt} \title{Circle configurations and the hardness of promise graph and hypergraph coloring} \author{Yuwen Zhou\\[2pt] \normalsize University of British Columbia Okanagan\\ \normalsize\texttt{zhouyw07@student.ubc.ca}} \date{November 2026} \begin{document} \maketitle \begin{abstract} In 2017 Brakensiek and Guruswami conjectured that promise graph homomorphism is NP-hard for every non-bipartite source and loopless target admitting a homomorphism from the source. At CCC 2016 they conjectured hardness of properly coloring a uniform hypergraph promised a strong coloring with one more color than its uniformity. We prove both conjectures by a configuration theorem on the circle. For any fixed finite configuration of distinct rational phases, the theorem gives a reduction whose satisfiable instances place every edge near a translate of the configuration and whose unsatisfiable instances have arbitrarily small independence ratio. An antipodal pair gives hardness for every odd cycle against every fixed clique of size at least three. A regular \(h\)-gon gives a strong \((h+1)\)-coloring and a rainbow \((h-1)\)-coloring of the same instance. A circle coloring built from single-coordinate changes gives hardness of \(\PCSP(R,\NAE_h^{(d)})\) for every nonempty symmetric reconfigurable relation \(R\) with \(R\to\NAE_h^{(d)}\), and the monochromatic-clique dichotomy of Banakh, Barsukov, and Nakajima without the Rich \(2\)-to-\(1\) Conjecture. For triples we obtain hardness of linearly ordered coloring for all fixed palettes \(3\le c\le d\). The proof subtracts an average of translated distance functions to detect an independent set, then uses conditional mean zero and a finite Ramsey alignment argument to decode a Label Cover assignment. \end{abstract} \section{Introduction} For finite relational structures \(A\to B\), the decision problem \(\PCSP(A,B)\) accepts inputs \(X\) with a homomorphism \(X\to A\) and rejects inputs \(X\) with \(X\nrightarrow B\). A homomorphism preserves every relation. For graphs it sends each edge to an edge. Taking \(A\) and \(B\) to be cliques gives approximate graph coloring. For a hypergraph \(H\), let \(\alpha(H)\) be the maximum size of a set containing no entire edge. A proper coloring partitions the vertices into independent sets. A strong coloring gives distinct colors to all vertices of each edge. A rainbow coloring requires every edge to see every color of the specified palette. We use finite simple hypergraphs. An edge of uniformity \(h\) is a set of \(h\) distinct vertices. Write \(\T=\R/\Z\) and give it the distance \(d_{\T}(a,b)=\min_{n\in\Z}|a-b-n|\), computed with real lifts. The phase map in the following theorem is one map on the entire vertex set. Only the translation and the ordering vary from edge to edge. \begin{theorem}[Configuration theorem]\label{th:config} Fix \(h\ge2\), distinct rational offsets \(u_0=0,u_1,\ldots,u_{h-1}\) in \(\T\), a rational \(\rho>0\) such that \[ 2\rho<\min_{i\ne j}d_{\T}(u_i,u_j), \] and a real \(\delta>0\). There is a deterministic polynomial-time reduction from \(3\mathrm{SAT}\) to nonempty \(h\)-uniform hypergraphs \(H\) with these properties. \begin{enumerate}[label=\textup{(\roman*)}] \item If the input is satisfiable, there is a map \(\varphi:V(H)\to\T\). Every edge has an ordering \(x_0,\ldots,x_{h-1}\) and a \(t\in\T\) for which \[ d_{\T}\bigl(\varphi(x_j),t+u_j\bigr)\le\rho \qquad(0\le j0\), a deterministic polynomial-time reduction from \(3\mathrm{SAT}\) produces an \(h\)-uniform hypergraph with a strong \((h+1)\)-coloring and a rainbow \((h-1)\)-coloring in the satisfiable case, and independence ratio below \(\delta\) in the unsatisfiable case. For all fixed \(k,c\ge2\) except \((k,c)=(2,2)\), it is NP-hard to find a proper \(c\)-coloring of a \(k\)-uniform hypergraph promised to be strongly \((k+1)\)-colorable. For \(k\ge3\) this also holds under the rainbow \((k-1)\)-coloring promise and under both promises together. \end{corollary} The strong-coloring assertion settles CCC 2016 Conjecture~1.2. The rainbow boundary was posed separately in the table on page~14:4 of the same paper~\cite{bg-color}. For a palette of size \(d\), let \(\NAE_h^{(d)}\) be the relation of nonconstant \(h\)-tuples. A relation is \emph{symmetric} if it is closed under coordinate permutations. It is \emph{reconfigurable} if any two of its tuples are joined inside the relation by a path whose steps change one coordinate. We identify a relation with its one-relation structure. Write \(\mathcal F_k^{(c)}\) for the family consisting of a monochromatic \(k\)-clique in each of \(c\) colors. An arrow \(\mathcal F_k^{(c)}\to\mathcal F_\ell^{(d)}\) means that a fixed map of palettes takes every coloring avoiding the first family to a coloring avoiding the second. The corresponding \(\PMMSNP\) problem accepts graphs admitting the first coloring and rejects graphs admitting no second coloring~\cite{bbn}. \begin{corollary}[Reconfigurable relations and monochromatic cliques] \label{cor:clique} Let \(R\subseteq A^h\) be a nonempty symmetric reconfigurable relation on a finite set, where \(h\ge2\). For every \(d\) with \(R\to\NAE_h^{(d)}\), the problem \(\PCSP(R,\NAE_h^{(d)})\) is NP-hard. Let \(c,d,k,\ell\) be positive integers with \(\mathcal F_k^{(c)}\to\mathcal F_\ell^{(d)}\). If \(\ell\ge c(k-1)\), then \(\PMMSNP(\mathcal F_k^{(c)},\mathcal F_\ell^{(d)})\) is solvable in polynomial time via affine integer programming. If \(\ell0\), there is an integer \(J(L,\tau)\ge1\) with the following property. For any \(n\) and any \(L\)-Lipschitz \(G:[0,1]^n\to[-1,1]\), there is a coordinate set \(S\), \(|S|\le J(L,\tau)\), such that \[ \|G-\E[G\mid x_S]\|_2<\tau . \] Indeed, apply Austin's Theorem~1.1 in arXiv version~4 to the uniform interval with modulus \(t\mapsto Lt\). Take the \(L^1\) error below \(\tau^2/2\). The pointwise difference has absolute value at most two, giving the stated \(L^2\) bound~\cite{austin}. The quotient map from the cube to the product of circles preserves uniform probability and is nonexpanding. The same approximation therefore holds on a product of circles. A function of the selected coordinates will be called a junta. For \(H\in L^2(\T^n)\), let \(E_i\) average coordinate \(i\) while retaining all others. Set \[ Q_i=1-E_i,\qquad D_i(H)=\|Q_iH\|_2 . \] Both \(E_i\) and \(Q_i\) are orthogonal projections. In particular, changing a function by \(\eta\) in \(L^2\) changes \(D_i\) by at most \(\eta\). \begin{lemma}[Influence detection and count]\label{le:influence} For every \(L<\infty\), \(L\ge0\), and \(\eps>0\), there are \(\beta>0\) and \(K\ge1\) independent of \(n\) such that every \(L\)-Lipschitz \(H:\T^n\to[-1,1]\) satisfies \[ \begin{aligned} \E H=0,\quad \E H^2>\eps &\quad\Longrightarrow\quad D_i(H)\ge\beta \text{ for some }i,\\ \#\{i:D_i(H)\ge\beta/2\}&\le K . \end{aligned} \] \end{lemma} \begin{proof} Set \(J_0=J(L,\sqrt{\eps}/2)\). Choose a set \(S\) of at most \(J_0\) coordinates so that \(G=\E[H\mid z_S]\) satisfies \(\|H-G\|_2<\sqrt{\eps}/2\). If \(H\) has mean zero and \(\|H\|_2>\sqrt{\eps}\), then \(G\) has mean zero and \(\|G\|_2>\sqrt{\eps}/2\). To bound this last norm, expand \(H\) using the commuting projections \(E_i,Q_i\). For \(A\subseteq[n]\), put \[ H_A=\left(\prod_{i\in A}Q_i\right) \left(\prod_{i\notin A}E_i\right)H . \] Their sum is \(H\), since \(Q_i+E_i=1\). Two distinct summands are orthogonal by averaging at a coordinate in their symmetric difference. Conditioning on \(z_S\) retains exactly the summands with \(A\subseteq S\). The constant summand vanishes. Consequently \[ \frac{\eps}{4}<\|G\|_2^2 =\sum_{\varnothing\ne A\subseteq S}\|H_A\|_2^2 \le\sum_{i\in S}\sum_{A\ni i}\|H_A\|_2^2 =\sum_{i\in S}D_i(H)^2 . \] Take \(\beta=\sqrt{\eps/(4J_0)}\). For the count, approximate \(H\) to error less than \(\beta/2\) by a junta \(G'\) on at most \(K=J(L,\beta/2)\) coordinates. Outside its coordinate set \(Q_iG'=0\), so \(D_i(H)\le\|H-G'\|_2<\beta/2\). This part holds for every mean. \end{proof} \clearpage \section{The reduction}\label{sec:reduction} Fix the configuration and density in Theorem~\ref{th:config}. The construction uses integers \(r\ge s\ge2\), \(m\ge1\), and \(P\ge1\). Take \(P\) divisible by the denominators of all the offsets. Other finite data are a rational number \(0<\lambda<1\) and a rational probability law \(\mu\) on \(\binom{[r]}s\). The choices in Section~\ref{sec:parameters} fix all these data before the input formula is read. Put \[ D=mP,\qquad \Gamma=(D^{-1}\Z)/\Z . \] We describe the reduction on the output of Theorem~\ref{th:lc}. \subsection{A space of phase assignments} At layer \(i\in[r]\), form all question tuples and the corresponding answer set \[ \mathbf q\in V^{i-1}\times U^{r-i}, \qquad M_i=\Sigma_R^{\,i-1}\times\Sigma_L^{\,r-i}. \] Both products have \(r-1\) positions. Occurrences of the same question at different positions remain separate positions. At adjacent layers \(i,i+1\), take all pairs of question tuples that agree off position \(i\). For each occurrence between their questions at position \(i\), impose the map \(M_i\to M_{i+1}\) applying its projection at that position and the identity elsewhere. Place a separate copy of \(\Gamma^{M_i}\) at each question tuple of layer \(i\). A grid point \(x\) is an assignment of a phase \(x_\kappa\) to every answer \(\kappa\) of that tuple. Let \(\X\) be the disjoint union of the grids. Define an undirected weighted link graph on \(\X\). Within a grid, link each pair with length its sup circle distance. For an imposed map \(\pi:M_i\to M_{i+1}\), link each point \(y\) of its target grid to \(y\circ\pi\) of its source grid with length zero. The direction of this pullback is opposite to the answer map. Let \(\dist\) be shortest-path distance in the link graph, with value infinity between components. It is an extended pseudometric. Different grid points can have distance zero. For \(u\in\Gamma\), let \(S_ux=x+u\mathbf1\) in each grid. Within-grid lengths are translation invariant. On a projection link, \[ (S_uy)\circ\pi=S_u(y\circ\pi). \] Thus \(S_u\) and its inverse take links to links of the same length. Each \(S_u\) is an isometry of \(\dist\). We use the same notation for arbitrary diagonal translations on a continuous product torus. \subsection{Configuration tests} Choose an integer \(q\ge h\) with \((h-1)/q<\delta\). Denote by \(K_q^{(h)}\) the hypergraph of all \(h\)-subsets of \([q]\). First test whether there exist \(w\in\X\) and \(i2\rho\). This excludes \eqref{eq:fallback}. Give vertex \(v\) the phase \(\varphi(x_v)\). For an edge with witness \(w\), nonexpansion in \eqref{eq:edge} gives the required inequalities with \(t=\varphi(w)\). \end{proof} \subsection{An antipodal pair} Use \(C_g\) on \(\Z/g\Z\) with edges of difference \(\pm1\). For two offsets \(0,1/2\), the two errors relative to a common translate give an error at most \(2\rho\) in the displacement. \begin{lemma}[Odd-cycle rounding]\label{le:odd} Let \(g=2k+1\ge3\). Suppose a graph has a phase map under which the displacement on every edge has circle distance at most \(1/(4g)\) from \(1/2\). Then the graph maps to \(C_g\). \end{lemma} \begin{proof} At a vertex with real phase lift \(u\), give the color \[ k^{-1}\lfloor gu\rfloor\pmod g . \] Here \(k^{-1}=-2\bmod g\). Changing the lift adds a multiple of \(g\) to the bin index. On an edge, choose the other lift \(v\) so that \[ g(v-u)\in[k+1/4,k+3/4]. \] Writing \(\{gu\}\) for the fractional part gives \[ \lfloor gv\rfloor-\lfloor gu\rfloor =\lfloor\{gu\}+g(v-u)\rfloor\in\{k,k+1\}. \] The interval includes its endpoints, and the floor assigns a boundary point to the bin starting there. Since \(k+1\equiv-k\bmod g\), the colors differ by \(1\) or \(-1\). \end{proof} \begin{remark} For \(g=3\), Open Mathematics Courses, Exercise~6.5, observes that the three-bin completeness argument works for any antipodal displacement cutoff strictly below \(1/6\)~\cite{course}. For the configuration theorem the displacement cutoff is twice the per-vertex radius. We use \(\rho=1/(8g)\). \end{remark} \subsection{A regular polygon} \begin{lemma}[Two partitions of the circle]\label{le:polygon} Use the offsets \(j/h\), \(0\le j1/(h+1)\). A bin of width \(1/(h+1)\) cannot contain two such points. Choose a lift \(t\) of the translation on an edge and write its lifts as \(t+j/h+e_j\), with \(|e_j|\le\rho\). Set \(e_h=e_0\) for the next copy of the first vertex. Every successive gap lies in \[ [1/h-2\rho,\,1/h+2\rho]\ \subset\ (0,1/(h-1)). \] The positive lower bound gives cyclic order, including the gap across the seam. If a lifted bin \([a,a+1/(h-1))\) were empty, the last lift before \(a\) would be strictly less than \(a\) and the next would be at least \(a+1/(h-1)\). The gap bound excludes this. Both partitions use the original phase map on all vertices. \end{proof} \subsection{A path of legal tuples} \begin{lemma}[Circle coloring for a relation]\label{le:path} Suppose a symmetric relation \(R\subseteq C^h\) contains \(a=(a_0,\ldots,a_{h-1})\) and a single-coordinate path in \(R\) from \(a\) to \((a_1,\ldots,a_{h-1},a_0)\). There are a rational \(0<\rho_*<1/(2h)\) and a map \(\chi:\T\to C\) such that \[ \bigl(\chi(t+j/h+e_j)\bigr)_{0\le j0\). For \(I\in\binom{[r]}{s-1}\) and a fixed coefficient vector \(t\in\mathcal T_m^I\), consider \begin{equation}\label{eq:junction} G_{I,t}(\theta)=F_{\min I}\bigl(X_I(t,\theta)\bigr), \qquad \theta\in\prod_{j\in I}[0,1]^{M_j}. \end{equation} The rotation entries now have continuous product law. In one coordinate of \(X_I\), each block contributes one scalar multiplied by a number in \([0,1]\). Hence changing the whole rotation array by sup distance \(\eta\) changes the phase vector by at most \((s-1)\eta\) in circle sup distance. This holds for all projection maps, including those with large fibers. The function \(G_{I,t}\) is therefore \((s-1)L\)-Lipschitz. \begin{lemma}[Local choice of lists]\label{le:lists} For each fixed chain and each \(I\in\binom{[r]}{s-1}\), there are sets \(S_I^j\subseteq M_j\), \(j\in I\), with \begin{equation}\label{eq:listsize} \sum_{j\in I}|S_I^j|\le d,\qquad d=J((s-1)L,\gamma)(m+1)^{s-1}. \end{equation} For every \(t\in\mathcal T_m^I\) there is a junta \(g_{I,t}\) on entries \((j,\ell)\) with \(\ell\in S_I^j\) such that \(\|G_{I,t}-g_{I,t}\|_2<\gamma\). The lists depend only on the tuples in \(I\), their fixed functions, and the projections between them. \end{lemma} \begin{proof} Apply the junta bound of Section~\ref{sec:inputs} to \eqref{eq:junction} at every coefficient vector. Order the scalar coordinates once and for all. Among the sets of size at most \(J((s-1)L,\gamma)\) whose coordinate conditional expectation has error less than \(\gamma\), choose the first in a fixed ordering. Use that conditional expectation as \(g_{I,t}\). Union the chosen indices within each block over the \((m+1)^{s-1}\) vectors \(t\). This proves the bound and the simultaneous approximation. The choice rule uses only the data defining \eqref{eq:junction}. It is part of the analysis and need not be run by the reduction. \end{proof} Project the lists to the answer set at the last layer: \begin{equation}\label{eq:terminal} A_I=\bigcup_{j\in I}\pi_{jr}(S_I^j) \ \subseteq M_r . \end{equation} Each \(A_I\) has size at most \(d\). The projection in this formula can use occurrences outside \(I\). We decode from the selected coordinates \emph{before} this terminal projection. \begin{lemma}[Decoding separated lists]\label{le:decode} If \(\val(\mathcal C)\le\sigma\) and \(I,J\in\binom{[r]}{s-1}\) satisfy \(\max I<\min J\), then \[ \Pr_{\rm chain}(A_I\cap A_J\ne\varnothing) \le d^2\sigma . \] \end{lemma} \begin{proof} Put \(k=\max I\), and condition on all occurrences except \(e_k\). Each tuple in \(I\) has left question \(p_k\) at position \(k\). Its remaining entries are fixed. All projections internal to that subchain use occurrences with indices below \(k\). The left list rule consequently depends on \(e_k\) only through \(p_k\). On \(J\), position \(k\) already has right question \(q_k\) and all internal projections avoid \(e_k\). Its list rule depends on \(e_k\) only through \(q_k\). The family of functions \(F_{\mathbf q}\) was fixed for the entire instance in Lemma~\ref{le:bump}. Looking up a function at a tuple respects these dependencies even for different occurrences with the same own question. On each side collect the entries at position \(k\) of all its selected answers. This gives at most \(d\) left candidates as a function of the left question and at most \(d\) right candidates as a function of the right question. Order and pad the lists to length \(d\) with arbitrary answers, allowing an initially empty list. For each pair of list indices, reading those entries at all own questions defines one labeling of the original instance. If the terminal lists intersect, two selected product answers have equal terminal images. At position \(k\), the left answer was acted on by exactly \(P_{e_k}\), and the right answer was unchanged. Thus one of the \(d^2\) labelings satisfies \(e_k\). Conditional on the background this occurrence still has its original uniform law. Each labeling satisfies it with probability at most \(\sigma\). A union bound and then averaging over the background prove the claim. \end{proof} \clearpage \section{Soundness II. Finite distributional alignment}\label{sec:align} For \(B\in\binom{[r]}s\) we seek a map \(a:M_r\to B\) such that \begin{equation}\label{eq:align} a(A_{B\setminus\{i\}})\subseteq B\setminus\{i\} \qquad(i\in B). \end{equation} In fact, \eqref{eq:align} is equivalent to the absence of a label common to all \(s\) deletion lists. For each label, one may assign any index whose deletion list omits it. Disjointness on separated subchains does not itself give this condition on a prescribed \(B\). For example, with \(s=3\) the same label can occur on all three pairs of a triple without occurring on two separated pairs. The distribution in the next lemma works for every list family. \begin{lemma}[Distributional alignment for deletions]\label{le:align} For integers \(s\ge2,d\ge1\) and every \(\eta>0\), there exist \(r\ge s\) and a rational probability law \(\mu\) on \(\binom{[r]}s\) with the following property. Let \(M\) be any set. For every \(I\in\binom{[r]}{s-1}\) give a list \(A_I\subseteq M\) of size at most \(d\). Assume \[ A_I\cap A_J=\varnothing\quad\text{if }\max I<\min J . \] With probability at least \(1-\eta\) over \(B\sim\mu\), a map \(a:M\to B\) satisfying \eqref{eq:align} exists. \end{lemma} \begin{proof} We may assume \(0<\eta<1\) by decreasing it. Order the entries in each list. A pattern consists of the occupied slots in these ordered lists and the equivalence relation recording equality of their labels. For a fixed \(r\) the number of allowed patterns is finite. Patterns can be realized using their equivalence classes as labels. Both the hypothesis and the desired conclusion depend only on the pattern. For a fixed pattern and an appearing label \(x\), define an index \[ p(x)=\max\{\min I:x\in A_I\}. \] Every occurrence \(x\in A_I\) satisfies \begin{equation}\label{eq:hull} \min I\le p(x)\le\max I. \end{equation} The lower bound follows from the definition. If the upper bound failed, a list attaining the maximum would be strictly to the right of \(I\) and would share \(x\) with it. This proves the upper bound. We will round this one index in the same way for every occurrence of \(x\). \smallskip \noindent\emph{A good set for any distribution of patterns.} Choose an integer \(n\) with \(sd/n<\eta/4\). By the finite Ramsey theorem take \(r\) large enough that every coloring of the \(s\)-subsets of \([r]\) in at most \((n+1)^{sd}\) colors has a homogeneous set of size \(2s-1\)~\cite{ramsey}. This choice precedes the distribution of patterns. Now give the allowed patterns any probability distribution \(\nu\). For an \(s\)-set \(U=\{v_1<\cdots\eps &\ \Longrightarrow\ D_i(t,\theta)\ge\beta\text{ for some }i\in B, \label{eq:detect}\\ \#\{i\in B:D_i(t,\theta)\ge\beta/2\}&\le K . \label{eq:count} \end{align} The count holds for all coefficient vectors. Its bound was fixed independently of \(s\). \subsection{Deleting a zero coefficient} Call a coefficient \emph{full} when it equals one and let \(\mathcal F\) be the event that at least one coefficient is full. By independence, \(\Pr(\mathcal F^c)=(1-p_m)^s\). \begin{lemma}\label{le:delete} Fix \(t\in\mathcal F\) and \(i\in B\) with \(t_i=0\). Then \[ \E_\theta D_i(t,\theta)^2<(2\gamma)^2 . \] \end{lemma} \begin{proof} Choose \(j\in B\) with \(t_j=1\). Then \(j\ne i\). Put \(I=B\setminus\{i\}\) and \(c=\min I\). In the rotation array on \(I\), modify only block \(j\) by setting \begin{equation}\label{eq:absorb} \theta'_{j,\ell} =\bigl\{\theta_{j,\ell}+z_{a(\pi_{jr}(\ell))}\bigr\}, \qquad \ell\in M_j . \end{equation} Here braces mean the representative in \([0,1)\) of a sum modulo one. Conditional on \(z\), these are fixed translations of the individual uniform coordinates. The joint rotation law remains product uniform, including when several entries receive the same shift. Let \(y=X_I(t|_I,\theta')\). Composition of the projections gives for every \(\kappa\in M_b\) \[ y_{\pi_{bc}(\kappa)}=Y(t,\theta,z)_\kappa . \] Indeed, the deleted term has coefficient zero. In the translated block, the added phase is \(z_{a(\pi_{jr}\pi_{bj}(\kappa))}=z_{a(\pi_{br}(\kappa))}\). The integer removed by taking the representative in \eqref{eq:absorb} disappears in the phase sum because \(t_j=1\). Consequently \eqref{eq:compat} gives the pointwise bound \[ |H(t,\theta;z)-G_{I,t|_I}(\theta')| =|F_b(y\circ\pi_{bc})-F_c(y)| \le 2L/D <\gamma . \] This also treats deletion of the minimum of \(B\). Take the junta \(g_{I,t|_I}\) from Lemma~\ref{le:lists}. Preservation of the rotation law at every fixed \(z\) gives \[ \|G_{I,t|_I}(\theta')-g_{I,t|_I}(\theta')\|_{L^2(\theta,z)} <\gamma . \] Only entries in block \(j\) can introduce dependence on \(z\) into this junta. Each such selected entry \(\ell\) has \(\pi_{jr}(\ell)\in A_I\), hence \(a(\pi_{jr}(\ell))\in I\) by alignment. Therefore \(g_{I,t|_I}(\theta')\) is independent of \(z_i\). Apply \(Q_i\), acting on \(z_i\) in the joint product space. It kills this junta and has norm at most one. We obtain \[ \bigl(\E_\theta D_i(t,\theta)^2\bigr)^{1/2} =\|Q_iH\|_{L^2(\theta,z)} \le\|H-g_{I,t|_I}(\theta')\|_{L^2(\theta,z)}<2\gamma . \] \end{proof} For each fixed \(t\in\mathcal F\), Markov's inequality and a union bound over its zero coefficients now apply. After averaging in \(t\), \begin{equation}\label{eq:zeroevent} \Pr\{\mathcal F,\ \exists i\in B:\ t_i=0,\ D_i(t,\theta)\ge\beta\} \le s(2\gamma)^2/\beta^2<\eps . \end{equation} \subsection{Lowering a positive coefficient} \begin{lemma}\label{le:lower} Under the product laws on \(t,\theta\), \[ \Pr\{\exists i\in B:\ t_i>0,\ D_i(t,\theta)\ge\beta\} \le\lambda K . \] \end{lemma} \begin{proof} Fix \(i\), the array \(\theta\), and the other coefficients. At level \(t_i=k/m\), denote \(H(t,\theta;\cdot)\) by \(H_k\) and its \(i\)-influence by \(d_k\). Moving down one level changes each phase coordinate by distance at most \(1/m\), since each rotation is in \([0,1)\). Hence \[ |d_k-d_{k-1}| \le\|Q_i(H_k-H_{k-1})\|_2 \le L/m<\beta/2\qquad(1\le k\le m). \] If \(d_k\ge\beta\), the preceding level has \(d_{k-1}\ge\beta/2\). Its probability is \(p_{k-1}=p_k/\lambda\). It follows that \[ \sum_{k=1}^m p_k\ind_{\{d_k\ge\beta\}} \le \lambda\sum_{k=0}^{m-1}p_k\ind_{\{d_k\ge\beta/2\}} \le \lambda\sum_{k=0}^{m}p_k\ind_{\{d_k\ge\beta/2\}}. \] Average over the fixed data, use the union bound over \(i\), and apply \eqref{eq:count}. The right side becomes at most \(\lambda\E\,\#\{i:D_i(t,\theta)\ge\beta/2\}\le\lambda K\). Lowering the only full coefficient is allowed because \eqref{eq:count} holds at the resulting vector as well. \end{proof} \subsection{Absorption and the discrete law} \begin{proposition}[Mean square on an aligned pair]\label{pr:square} Under \eqref{eq:bounds}, for every aligned chain and \(B\), \[ \E_{t,\widehat\theta} F_b\bigl(X_B(t,\widehat\theta)\bigr)^2<6\eps . \] \end{proposition} \begin{proof} By \eqref{eq:detect}, if \(V(t,\theta)>\eps\), then one of three events occurs. There is no full coefficient, a zero coefficient is influential in the presence of a full one, or a positive coefficient is influential. Their probabilities are bounded by \((1-p_m)^s\), \(s(2\gamma)^2/\beta^2\), and \(\lambda K\), respectively, by \eqref{eq:zeroevent} and Lemma~\ref{le:lower}. All three are less than \(\eps\). Since \(0\le V\le1\), \begin{equation}\label{eq:auxsquare} \E_{t,\theta,z}H(t,\theta;z)^2 =\E_{t,\theta}V(t,\theta) \le\eps+\Pr\{V>\eps\}<4\eps . \end{equation} To remove \(z\), fix \(t\in\mathcal F\) and choose any one full block \(j\). Translate its rotations by \eqref{eq:absorb}, now retaining all blocks. The same coordinate computation gives \(X_B(t,\theta')=Y(t,\theta,z)\). The conditional rotation law is unchanged for each \(z\), so \[ \E_{\theta,z}H(t,\theta;z)^2 =\E_{\theta}F_b\bigl(X_B(t,\theta)\bigr)^2 \qquad(t\in\mathcal F). \] Multiply by the probability of each such \(t\) and sum. The resulting contribution to the unshifted square is below \(4\eps\) by \eqref{eq:auxsquare}. On \(\mathcal F^c\) the square is at most one, which adds less than \(\eps\). Finally couple the discrete rotations by \(\widehat\theta_{j,\ell}=\lfloor P\theta_{j,\ell}\rfloor/P\). They have exactly the independent uniform law of the construction. Each phase coordinate in \eqref{eq:phasevector} moves by at most \(s/P\). Since \(|F_b|\le1\), the difference of the two squared function values is at most \[ 2L\,d_\infty(X_B(t,\theta),X_B(t,\widehat\theta)) \le 2Ls/P<\eps . \] Adding these contributions proves the proposition. \end{proof} \clearpage \section{Parameters and proof of the configuration theorem} \label{sec:parameters} First fix \(L=2/\rho\) and a rational \(\eps>0\) such that \[ (6h^2+2)\eps<\min\{\delta,1\}. \] The following order places the source alphabets after the list size and the number of layers. \begin{enumerate} \item Take \(\beta,K\) from Lemma~\ref{le:influence} for \(L,\eps\). Choose \(m\) with \(L/m<\beta/2\), then rational \(0<\lambda<1\) with \(\lambda K<\eps\). Equation~\eqref{eq:law} now fixes \(p_m>0\). \item Choose \(s\ge2\) with \((1-p_m)^s<\eps\). Choose \(\gamma>0\) with \(s(2\gamma)^2/\beta^2<\eps\). Take a positive multiple \(P\) of the offset denominators large enough that \[ 2L/(mP)<\gamma,\qquad 2Ls/P<\eps . \] Set \(D=mP\). This gives all of \eqref{eq:bounds}. \item Fix the integer \(d\) in \eqref{eq:listsize}. Apply Lemma~\ref{le:align} with \(s,d,\eta=\eps\) to obtain \(r,\mu\). Choose rational \(0<\sigma<1\) such that \(4^rd^2\sigma<\eps\). Only now take the alphabets of Theorem~\ref{th:lc}. \item Use any \(q\ge h\) with \((h-1)/q<\delta\) for the fallback. \end{enumerate} Every object used to construct the output is a fixed integer or a finite rational table, apart from the input Label Cover instance. In particular, the law \(\mu\) is independent of the terminal answer set and of the independent set later considered. The real functions, conditional expectations, and decoding maps occur only in the proof. For each fixed real \(\delta>0\) the strict inequalities above can be met with finite construction data. \begin{proof}[Proof of Theorem~\ref{th:config}] Apply Theorem~\ref{th:lc} at the chosen \(\sigma\), then use Section~\ref{sec:reduction}. Proposition~\ref{pr:encoding} gives a deterministic polynomial-time reduction in the binary input length. In the satisfiable case, Lemma~\ref{le:evaluation} gives the phase map and excludes the fallback. Suppose the input is unsatisfiable. The fallback has independence number \(h-1\), hence independence ratio less than \(\delta\). On the sampling branch, fix a nonempty independent set \(\mathcal A\). For every output vertex \(v\), with \(F\) the function on its location's grid, Lemma~\ref{le:bump} gives \begin{equation}\label{eq:indicator} \ind_{\mathcal A}(v)\le h^2 F(x_v)^2 . \end{equation} Indeed, a selected vertex has grid value at least \(1/h\). At an unselected vertex the inequality holds also when a different copy at the same location was selected. On an aligned pair, Proposition~\ref{pr:square} bounds the expected right side of \eqref{eq:indicator} by \(6h^2\eps\). On an unaligned pair bound the indicator itself by one. By \eqref{eq:bad} and the choice of \(\sigma\), the probability of the latter event is less than \(2\eps\). The vertex law is uniform by Proposition~\ref{pr:encoding}. Thus \[ \frac{|\mathcal A|}{|V(H)|} =\Pr\{v\in\mathcal A\} <6h^2\eps+2\eps<\delta . \] The empty independent set satisfies the strict inequality as well. Taking the maximum over independent sets proves soundness. \end{proof} \section{Proofs of the coloring corollaries}\label{sec:applications} \subsection{Graphs} \begin{proof}[Proof of Corollary~\ref{cor:graph}] In Theorem~\ref{th:config} take \(h=2\), offsets \(0,1/2\), and \(\rho=1/(8g)\). On every satisfiable edge, subtracting the two phases introduces error at most \(2\rho=1/(4g)\) relative to the half-turn. Lemma~\ref{le:odd} gives a homomorphism to \(C_g\). The unsatisfiable bound is the density assertion of the theorem. Every odd cycle maps to \(K_3\), hence to \(K_c\) for \(c\ge3\). Take \(0<\delta<\min\{1/3,1/c\}\). A proper \(c\)-coloring would have an independent class of density at least \(1/c\). This proves the odd-cycle versus clique gap and hardness of finding such a coloring under the odd-cycle promise, by checking the output of a proposed polynomial-time algorithm. For general \(A\to B\) as in the corollary, some component of \(A\) contains an odd cycle \(C_g\). Choose \(0<\delta<\min\{1/3,1/|V(B)|\}\). In the satisfiable case compose \(X\to C_g\to A\). A homomorphism \(X\to B\) in the unsatisfiable case would have an independent fiber of density at least \(1/|V(B)|\), since \(B\) is loopless. This is impossible. For completeness, the other finite undirected templates give polynomial-time problems. A loop at the target permits constant acceptance. A loop in the source forces a target loop. For a bipartite source with an edge, \(K_2\to A\to B\). Testing bipartiteness separates the promises. For a nonempty edgeless source, accept the edgeless inputs. For the empty source, accept only the empty input. \end{proof} \begin{remark}[Circular chromatic number]\label{re:circular} The circular clique \(K_{p/q}\) joins residues modulo \(p\) whose cyclic distance is at least \(q\), where \(p\ge2q\). For \(p=2k+1,q=k\) its steps are precisely \(\pm k\), so it is isomorphic to \(C_{2k+1}\). Given \(\xi>0\), take \(1/k\le\xi\). Corollary~\ref{cor:graph} then gives hardness of distinguishing \(\chi_c(X)\le2+\xi\) from independence ratio below any fixed \(0<\delta<\min\{1/3,1/(2+\xi)\}\). Indeed, \(q\) consecutive residues are independent in \(K_{p/q}\), so a uniformly translated such interval pulls back under any circular coloring to an independent set of expected density \(q/p\). Taking the supremum over admissible circular colorings gives independence ratio at least \(1/\chi_c(X)\) for graphs with an edge. Edgeless graphs have independence ratio one. \end{remark} \subsection{Strong, rainbow, and linearly ordered colorings} \begin{proof}[Proof of Corollary~\ref{cor:polygon}] Use the regular configuration \(u_j=j/h\) and rational \(0<\rho<1/(2h(h+1))\). Lemma~\ref{le:polygon} reads both colorings from the map supplied by Theorem~\ref{th:config}. For \(k=h\ge3\), take \(\delta<1/c\). The rainbow colors can be grouped into two nonempty parts to give a proper two-coloring, so the search problem on the simultaneous promise has a solution for every \(c\ge2\). A proper \(c\)-coloring on an unsatisfiable input would have an independent color class of density at least \(1/c\). Testing a returned coloring on every edge therefore distinguishes the cases. Hardness on instances satisfying both promises gives hardness under each promise separately. For \(k=2,c\ge3\), strong three-colorability is ordinary three-colorability. This is the case \(g=3\) of Corollary~\ref{cor:graph}. \end{proof} \begin{proof}[Proof of Corollary~\ref{cor:lo}] Take \(h=3\) in Corollary~\ref{cor:polygon} and \(\delta<1/d\). In the satisfiable case, Lemma~\ref{le:merge} gives an \(\LO_3\)-coloring. An increasing inclusion into the \(c\)-element palette preserves unique maxima. In the unsatisfiable case, each class of an \(\LO_d\)-coloring would be independent, as a monochromatic triple has three maxima. Its largest class would have density at least \(1/d\). \end{proof} \subsection{Reconfiguration and monochromatic cliques} \begin{proof}[Proof of Corollary~\ref{cor:clique}] For the first assertion choose the regular \(h\)-gon and the radius of Lemma~\ref{le:path} for \(R\). Apply Theorem~\ref{th:config} with \(\delta<1/d\). Make the output a relational structure by including every ordering of every hyperedge as a tuple of its \(h\)-ary relation. In the satisfiable case give vertex \(v\) the color \(\chi(\varphi(v))\). Lemma~\ref{le:path} puts the edge tuple in \(R\) in its witnessing order. Symmetry gives membership in every order. In the unsatisfiable case any homomorphism to \(\NAE_h^{(d)}\) would give a proper \(d\)-coloring, contrary to the density bound. For the second assertion, use the finite relations in the monochromatic-clique equivalence of Banakh, Barsukov, and Nakajima, Lemma~6~\cite{bbn}. Its source \(R_{k:\ell}^{(c)}\) consists of the length-\(\ell\) words on \(c\) colors in which each multiplicity is at most \(k-1\). Its target \(R_{\ell:\ell}^{(d)}\) is \(\NAE_\ell^{(d)}\). The palette map from the containment hypothesis sends source words to target words. Indeed, a legal word colors an \(\ell\)-clique without a monochromatic \(k\)-clique, so its recoloring cannot make the whole clique monochromatic. Containment implies \(k\le\ell\), since otherwise a monochromatic \(\ell\)-clique would itself contradict containment. Suppose first that \(\ell4\rho\). Include the fixed vertex at index zero and fill unused indices by their ideal phases. Lemma~\ref{le:path} sends the resulting \(\ell\)-tuple into \(R_{k:\ell}^{(c)}\). Thus the \(k\)-clique cannot be monochromatic. The coloring used on the graph is the single map \(\chi\circ\varphi\). In the unsatisfiable case, every hyperedge is an \(\ell\)-clique in the graph. A \(d\)-coloring avoiding monochromatic \(\ell\)-cliques would therefore be a proper \(d\)-coloring of the hypergraph. Choosing \(\delta<1/d\) excludes it. The graph construction is deterministic and polynomial. Finally suppose \(\ell\ge c(k-1)\). We spell out the affine integer argument of Banakh et al., Theorem~22~\cite{bbn}. In their relational formulation an input may contain loops, and a looped vertex carries a monochromatic image of every clique; reject such inputs first. On a simple graph, enumerate all \(\ell\)-cliques, which takes polynomial time for fixed \(\ell\). A source coloring gives a legal source word on each such clique. If \(\ell>c(k-1)\), no such word exists. Accept exactly when there are no \(\ell\)-cliques. The same test works when the target relation is empty, since a graph avoiding all \(\ell\)-cliques has a target coloring and containment excludes any \(\ell\)-clique in a yes instance. It remains to treat \(\ell=c(k-1)\) with nonempty target relation. Then \(d\ge2\) and \(0