Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,k)$ if and only if $i+j+k=0\mod n$. In general, there are "many" ways to do this.
Each such "attack-free" rook position can be colored with $c$ colors. When we fix an $i$, we can then count the colors in the matrix $(i,.,.)$, and can do similarly for each $j$ and $k$. Call this set of tuples of colors-counts the "color profile". For each color profile, there is either an even or odd number of colored rook positions that achieve it. I want to know the largest $c$ such that all color profiles have an even number of colored rook positions achieving it. In particular, I want to say that $c=\omega(n)$. This question came up in some complexity theory research, but the question seems interesting in its own right.
Formal Statement
Define $[n]$ to be the set ${1,\ldots, n}$, and define $[n]^3=[n]\times[n]\times[n]$. Define a $c$-coloring of a set $S\subseteq[n]^3$ to be a function $C:S\to[c]$. We can say that this is a $c$-coloring of $[n]^3$ with the convention that $C(i,j,k)=0$ for $(i,j,k)\notin S$. A $c$-coloring $C$ induces a color profile $P$, which is a function from $P:[n]\times[3]\times[c]\to[n]$, via the rules
$P(i,1,c)$ is the number of $(j,k)\in[n]^2$ such that $C(i,j,k)=c$.
$P(j,2,c)$ is the number of $(i,k)\in[n]^2$ such that $C(i,j,k)=c$.
$P(k,3,c)$ is the number of $(i,j)\in[n]^2$ such that $C(i,j,k)=c$.
where we keep in mind the convention above on $(i,j,k)\notin S$.
Call a set $S\subseteq [n]^3$ to be a rook set, if
for all $i,j\in[n]$, there is exactly one $k\in[n]$ such that $(i,j,k)\in S$
for all $j,k\in[n]$, there is exactly one $i\in[n]$ such that $(i,j,k)\in S$
for all $i,k\in[n]$, there is exactly one $j\in[n]$ such that $(i,j,k)\in S$
Let a colored rook set $C_S$ correspond the coloring $C$ of a rook set $S$.
Define $N(P)$ to be the number of colored rook sets $C_S$ that induce the color profile $P$.
The question is:
For each fixed $n$, what is the largest $c$ such that for all color profiles $P$, $N(P)\equiv 0\mod 2$? In particular, is the largest $c$ asymptotically $\omega(n)$?
What I know
It should be clear that this problem can be defined analogously in any dimension, and I'm interested in this more general question. I state it with $d\ge3$ because I can solve the $d=2$ case exactly. In particular
For each $n$, for any $c\le n-1$, and any color profile $P$ on grid $[n]^2$, $N(P)\equiv 0 \mod 2$. For $c\ge n$, there are profiles $P$ where $N(P)\equiv 1\mod 2$.
This can be proven by exhibiting a bijection between colored rook sets (which in d=2 are just permutation matrices). Specifically, using the pigeonhole principle $c\le n-1$ implies that there are two rooks with the same color. If they were at positions $(i,j)$ and $(i',j')$, then we replace them with the rooks of the same color at positions $(i,j')$ and $(i',j)$. (Of course, one needs to make this well-defined to ensure a bijection.)
Possible Methods
I see two possible methods of proof
generalize the above bijection proof to the 3-dimensional case
- I don't know how to use the pigeonhole principle to get such an extension, but it seems possible that there is a method to show that some motif exists in any colored rook set, and then argue that we can alter this motif to get the bijection
define a system of polynomials (over $\mathbb{F}_2$) such that the solution set corresponds to exactly the colored rook sets inducing a color profile $P$. Then try to apply the Chevalley-Warning theorem.
- I've tried this, but can't seem to get systems of polynomials where the sum of the total degrees is strictly less than the number of variables, so the C-W theorem does not apply.
- One can observe the the C-W theorem is an "iff" here: if $N(P)$ is even then there is a multilinear polynomial with degree strictly less than the number of variables, such that the solution set encodes those $C_S$'s that induce $P$.
Instead of using "rook sets", one can ask the question for other classes of subsets of $[n]^3$. I'd be happy with establishing $c=\omega(n)$ for any class of subsets (although I'd like to be able to compute at least one example of such a subset efficiently).
Are there other methods for counting modulo two that I missed?
