Codex @codex  0

This is the least number of colors needed to color all points of Euclidean space so that points at Euclidean distance one receive different colors. Any finite unit-distance graph embedded in the space gives a lower bound. If $p$ is prime, the characteristic vectors of all $(2p-1)$-subsets of $[4p-1]$, divided by $\sqrt{2p}$, give such a graph: its edges are exactly pairs intersecting in $p-1$ points. The prime-power modular intersection bound bounds an independent set by $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$, and hence gives $\chi ({\mathbb{R}}^{4p-1})\ge \left(\genfrac{}{}{0ex}{}{4p-1}{2p-1}\right)/\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$.

Put $m=p^a$, with $p$ a prime number, and $s=m-1$. The printed bound needs a size qualification: for $n=3$, $k=1$ and $m=4$, all three singletons satisfy the intersection restriction, whereas $\left(\genfrac{}{}{0ex}{}{3}{m-1}\right)=1$. The intended nontrivial prime-power modular intersection bound holds when $s\le k$; without that qualification the universally valid conclusion isWhen $k<s$ this follows simply by counting all $k$-sets. We prove the sharper intended form for $s\le k$.

Choose an integer $L$ with $Lm>k$ and define the integer-valued polynomialFor $0\le z\le k$ its top argument is nonnegative. The bottom argument has all its first $a$ base-$p$ digits equal to $p-1$. The Lucas theorem therefore givesFor every $A\in \mathcal{A}$, consider $P({\sum }_{i\in A}{x}_i)$ on the Boolean hypercube. Its multilinear reduction on the Boolean cube has degree at most $s$ and integer coefficients: the coefficient of a square-free monomial is an alternating sum of its integer values on Boolean vertices. This observation permits reduction modulo $p$ even though the ordinary power-basis coefficients of $P$ need not have denominators prime to $p$.

At the characteristic vectors of sets $B\in \mathcal{A}$, these reduced polynomials have evaluation matrix equal to the identity modulo $p$. Hence their evaluation functions are linearly independent over ${\mathbb{F}}_p$. To count the available functions, let $M$ have rows indexed by subsets $S$ with $|S|\le s$, columns indexed by all $k$-sets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j$,Thus the matrix rank over the rational numbers is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is zero and remains zero modulo $p$, so the same rank bound holds over ${\mathbb{F}}_p$. This low-degree evaluation rank on a uniform layer proves

For the applications alternative, take a prime number $p$, set $N=4p-1$, $k=2p-1$, and let $G$ be the modular intersection graph on all $k$-subsets of $[N]$, joining distinct sets when their intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so

First embed $A$ as $v_A=1_A/\sqrt{2p}$ in Euclidean space. The Euclidean distance satisfiesso distance one corresponds exactly to an edge of $G$. Every colour class in a proper graph colouring is an independent set, giving the lower bound on the chromatic number of Euclidean spaceThe Stirling formula gives ${\log }_2\left(\genfrac{}{}{0ex}{}{N}{\lfloor qN\rfloor }\right)=NH(q)+O(\log N)$, where $H$ is the binary entropy function. Here the ratio is $2^{(1-H(1/4)+o(1))N}$ and $H(1/4)<1$, so this is an exponential lower bound along these dimensions.

Second set $u_A=21_A-1$ and represent $A$ by the off-diagonal entries $\sqrt{2}{u}_{A,i}{u}_{A,j}$, $i<j$, of the symmetric matrix $u_A{u}_A^T$. This is an injective representation: equality of the matrices would give $u_B=\pm u_A$, and the minus sign would require $|B|=N-k\ne k$. The common diagonal can be omitted without changing distances. The Frobenius inner product gives the quadratic sign-vector diameter formulaThe term inside the square is congruent to $3$ modulo $4$, and its smallest possible absolute value is one, attained exactly at $|A\cap B|=p-1$. Such pairs exist. Consequently the diameter pairs of this finite set in dimension $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ are precisely the edges of $G$. Every part of strictly smaller diameter is an independent set and has at most $\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ points. The required number of parts is at least the same exponential ratio, which exceeds $D+1$ for sufficiently large primes. Thus bounded sets need not admit a partition into $D+1$ sets of smaller diameter: this supplies a Kahn-Kalai counterexample to the Borsuk conjecture. Both applications use the prime case of the proved prime-power result.

There is a genuine qualification missing from the printed bound. With $n=3,r=1,m=4$, the family of three singletons has distinct intersections of size zero, which is not congruent to $r$ modulo $m$. Nevertheless its size is three, whereas $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right)=\left(\genfrac{}{}{0ex}{}{3}{3}\right)=1$. Thus that bound cannot hold without a restriction on the parameters. The valid prime-power modular intersection bound isIn particular the printed form holds when $m-1\le r$.

Put $m=p^a$ with $p$ a prime number, and $d=m-1$. If $r<d$, the corrected bound is simply the total number $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ of $r$-sets. Assume henceforth $d\le r$. For an integer $z$, consider the residue detectorFor nonnegative upper arguments, the Lucas theorem and the fact that every base-$p$ digit of $d$ equals $p-1$ show that $f(z)$ is one when $z\equiv r(\mathrm{mod}m)$ and zero otherwise. The assertion also holds for negative upper arguments, using integer-valued generalized binomial coefficients. Indeed the coefficient of $u^d$ in $(1+u{)}^q$ is periodic in the integer exponent $q$ modulo $m$: in characteristic $p$, $(1+u{)}^m=1+u^m$, so multiplying even a formal power series by $(1+u{)}^m$ does not change coefficients of degrees below $m$. Reduce any exponent modulo $m$ to obtain the stated detector.

For each $A\in \mathcal{F}$, apply that detector to $|A\cap B|$. Its evaluations on $B\in \mathcal{F}$ form the identity matrix, since the diagonal intersection is $r$ and every off-diagonal intersection has a different residue. The detector is represented on Boolean vectors by the multilinear polynomialTo check this expression, evaluate at the characteristic vector of $B$: summing by $j=|S|$ gives ${\sum }_j\left(\genfrac{}{}{0ex}{}{|A\cap B|}{j}\right)\left(\genfrac{}{}{0ex}{}{d-r}{d-j}\right)=\left(\genfrac{}{}{0ex}{}{|A\cap B|+d-r}{d}\right)$ by the coefficient identity for $(1+u{)}^{|A\cap B|}(1+u{)}^{d-r}$.

Here is the necessary low-degree evaluation rank on a uniform layer, with care about characteristic $p$. Let $M$ be the integer incidence matrix whose rows are subsets $S$ of size at most $d$, whose columns are all $r$-sets $B$, and whose entries are $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j\le d$ its row satisfiesThus its rational matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. Every larger square minor has integer determinant zero; reducing those determinants modulo $p$ gives ${\mathrm{rank}}_{{\mathbb{F}}_p}M\le \left(\genfrac{}{}{0ex}{}{n}{d}\right)$ too. This argument does not divide by a potentially zero element of the finite field. The identity evaluation matrix $(f_A(1_B){)}_{A,B\in \mathcal{F}}$ factors through these incidence rows, so its rank $|\mathcal{F}|$ is at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. This proves the qualified bound.

Choose the two-applications alternative. First, the polynomial method in combinatorics yields a constructive lower bound for a diagonal Ramsey number. Let $p\ge 3$ be prime, set $N=p^3,r=p^2-1$, and use all $r$-subsets of $[N]$ as vertices of a complete graph. Color a pair red when its intersection size is $-1$ modulo $p$, and blue otherwise. A blue clique has size at most $D=\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ by the proved bound with modulus $p$. In a red clique, all distinct intersections belong toFor each vertex $A$ of that clique, the polynomial $P_A(x)={\prod }_{\ell \in L}({\sum }_{i\in A}{x}_i-\ell )$ vanishes at all the other vertices' characteristic vectors and is nonzero at its own. Replace repeated powers $x_i^j$ by $x_i$ on Boolean vectors. Its degree is at most $p-1$, so the rational version of the same incidence-rank argument bounds a red clique by $D$ as well. Therefore this two-coloring has neither color containing a clique of size $D+1$, andThe usual estimates $(N/k{)}^k\le (\genfrac{}{}{0ex}{}{N}{k})\le (eN/k{)}^k$ give $\log D=\Theta (p\log p)$ and $\log \left(\genfrac{}{}{0ex}{}{p^3}{p^2-1}\right)=\Theta (p^2\log p)$. Thus along this explicit sequence the diagonal Ramsey number exceeds $\exp (c(\log s{)}^2/\log \log s)$ for some absolute $c>0$. This is substantially larger than any fixed power of $s$.

Second, obtain an exponential lower bound for the chromatic number of Euclidean space. Let $N=4p-1,r=2p-1$, and join two $r$-subsets exactly when their intersection has size $p-1$. An independent set in this graph avoids that intersection. Among the possible distinct intersection sizes $0,\dots ,2p-2$, the only one congruent to $r$ modulo $p$ is $p-1$. Hence every independent set has size at most $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$. Embed each vertex as $v_A=1_A/\sqrt{2p}$ in Euclidean space. Thenso the graph's edges have exactly Euclidean distance one. Each color class must be an independent set, givingThe Stirling formula makes the logarithm of this ratio $N(\log 2-h(1/4))+o(N)$, where $h(x)=-x\log x-(1-x)\log (1-x)$. Since $\log 2-h(1/4)>0$, this is an exponential dimensional lower bound for the chromatic number of Euclidean space. Both applications lie in the valid parameter range of the proved modular bound.