# On the Descriptive Complexity of Color Coding +
## 3 Syntactic Properties Allowing Color Coding
### Formulas with Color Predicates
: _There is an \(n_{0}\in\mathbb{N}\) such that for all \(n\geq n_{0}\) and all subsets \(X\subseteq\{0,\ldots,n-1\}\) there exist a prime \(p<|X|^{2}\log_{2}n\) and a number \(q<p\) such that the function \(h_{p,q}(m)=(q\cdot m\bmod p)\bmod|X|^{2}\) is injective on \(X\)._  
As has already been observed by [PERSON] et al. [4], if we set \(k=|X|\) we can easily express the computation underlying \(h_{p,q}\colon\{0,\ldots,n-1\}\to\{0,\ldots,k^{2}-1\}\) using a fixed \(\operatorname{FO}[+,\times]\)-formula \(\rho(k,p,q,x,y)\). That is, if we encode the numbers \(k,p,q,x,y\in\{0,\ldots,n-1\}\) as corresponding elements of the universe with respect to the ordering of the universe, then \(\rho(k,p,q,x,y)\) holds if and only if \(h_{p,q}(x)=y\). Note that the \(p\) and \(q\) from the lemma could exceed \(n\) for very large \(X\) (they can reach up to \(n^{2}\log_{2}n\leq n^{3}\)), but, first, this situation will not arise in the following and, second, this could be fixed by using three variables to encode \(p\) and three variables to encode \(q\). Trivially, \(\rho(k,p,q,x,y)\) has some constant quantifier rank (the formula explicitly constructed by [PERSON] et al. has \(\operatorname{qr}(\rho)=9\), assuming \(k^{2}<n\)). Next, we will need the basic idea or \"trick\" of [PERSON] et al. 's [3] color coding technique: While for appropriate \(p\) and \(q\) the function \(h_{p,q}\) will \"just\" be injective on \(\{0,\ldots,k^{2}-1\}\), we actually want a function that maps each element \(x\in X\) to a specific element (\"the color of \(x\)\") of \(\{1,\ldots,k\}\). Fortunately, this is easy to achieve by concatenating \(h_{p,q}\) with an appropriate function \(g\colon\{0,\ldots,k^{2}-1\}\to\{1,\ldots,k\}\). In detail, to construct \(\phi^{\prime}\) from the claim of the theorem, we construct a family of formulas \(\phi^{g}(p,q)\) where \(p\) and \(q\) are new free variables and the formulas are indexed by all possible functions \(g\colon\{0,\ldots,k^{2}-1\}\to\{1,\ldots,k\}\): In \(\phi\), replace every occurrence of \(C_{i}x_{j}\) by the following formula \(\pi_{i}^{g}(p,q,x_{j})\):  
\[\bigvee_{y\in\{0,\ldots,k^{2}-1\},g(y)=i}\exists\hat{k}\exists\hat{g}\big{(} \textsc{SUCC}^{k}(0)=\hat{k}\wedge\textsc{SUCC}^{y}(0)=\hat{g}\wedge\rho(\hat {k},p,q,x_{j},\hat{g})\big{)}\]  
where \(\hat{k}\) and \(\hat{g}\) are fresh variables that we bind to the numbers \(k\) and \(y\) (if the universe is large enough). Note that the formula \(C_{i}x_{j}\) has \(x_{j}\) as a free variable, while \(\pi_{i}^{g}(p,q,x_{j})\) additionally has \(p\) and \(q\) as free variables. As an example, for the formula \(\phi=\exists x(C_{2}x\vee\exists yC_{5}y)\) we would have \(\phi^{g}=\exists x(\pi_{2}^{g}(p,q,x)\vee\exists y\pi_{5}^{g}(p,q,y))\). Clearly, each \(\phi^{g}\) has the property \(\mathrm{qr}(\phi^{g})=\mathrm{qr}(\phi)+O(1)\). The desired formula \(\phi^{\prime}\) is (almost) simply \(\bigvee_{g:\{0,\ldots,k^{2}-1\}\to\{1,\ldots,k\}}\exists p\exists q(\phi^{g}( p,q))\). The \"almost\" is due to the fact that this formula works only for structures with a sufficiently large universe--but by Lemma 1 it suffices to consider only this case. Let us prove that for every \(\sigma\)-structure \(\mathcal{A}\) with universe \(A=\{0,\ldots,n-1\}\) and \(n\geq c\) for some to-be-specified constant \(c\), the following two statements are equivalent:  
1. There is a \(k\)-coloring \(\mathcal{B}\) of \(\mathcal{A}\) with \(\mathcal{B}\models\phi\). 2. \(\mathcal{A}\models\bigvee_{g:\{0,\ldots,k^{2}-1\}\to\{1,\ldots,k\}}\exists p \exists q(\phi^{g}(p,q))\). Let us start with the implication of item 2 to 1. Suppose there is a function \(g\colon\{0,\ldots,\allowbreak k^{2}-1\}\to\{1,\ldots,k\}\) and elements \(p,q\in\{0,\ldots,n-1\}\) such that \(\mathcal{A}\models\phi^{g}(p,q)\). We define a partition \(A_{1}\cup\cdots\cup A_{k}=A\) by \(A_{i}=\{x\in A\mid g(h_{p,q}(x))=i\}\). In other words, \(A_{i}\) contains all elements of \(A\) that are first hashed to an element of \(\{0,\ldots,k^{2}-1\}\) that is then mapped to \(i\) by the function \(g\).