Return to Answer

UPDATE. Here is an alternative proof, due to Maxim Didin, of the more general fact:

Theorem 1. Let $(G,+)$ be a finite abelian group, and $f$, $g$ be two colorings (maps) from $G$ to a color set $C$ such that for every $k\in G$, $f(x)\not\equiv g(x+k)$ (in other words, $f$ is not a shifted $g$). Then there exists a coloring $h\colon G\to C$ such that $f(x)\ne h(x)$ for all $x\in G$, but for every $k$ there exists $x\in G$ such that $h(x)=g(x+k)$.

Denote $n=|G|$. For $k\in G$, denote by $g_k(x):=g(x+k)$ a shift of $g$ by $k$. Some shifts may coincide. Denote by $\Phi$ the set of all distinct shifts of $g$. The following strengthens Theorem 1.

Theorem 2. In above notations and under assumptions of Theorem 1, there exists an injection $\eta:\Phi\to G$ such that for all $\varphi\in \Phi$ we have $f(\eta(\varphi))\ne \varphi(\eta(\varphi))$.

(To deduce Theorem 1 from Theorem 2, define $h(\eta(\varphi)):=\varphi(\eta(\varphi))$ for $\varphi\in \Phi$, that is possible by injectivity of $\eta$; also define $h(x)=g(x)$ for $x\notin \eta(\Phi)$.)

To prove Theorem 2, we say that a shift $\varphi\in \Phi$ likes an element $x\in G$ if $f(x)\ne \varphi(x)$. Then by Hall marriage condition, to check the conclusion of Theorem 2 it is sufficient (and necessary) to prove that any set $M\subset \Phi$ of shifts of $g$ like in total at least $|M|$ elements $x\in G$. If $|M|=1$, this is true by our assumption. For $|M|>1$ this follows from the following

Proposition. For any set $M\subset \Phi$, $|M|>1$, there exist at least $|M|$ elements $x\in G$ such that $|\{\varphi(x)|\varphi\in M\}|\geqslant 2$.

(Obviously any such element $x$ is liked by some shift from $M$ that yields Hall's condition.) Proposition in turn follows from the key

Lemma. Let $A\subsetneq G$ be an arbitrary subset of $G$ which is not equal to $G$. Call a shift $g_k\in \Phi$ of the coloring $g$ $A$-appropriate if $g_k(x)=g(x)$ for all $x\in A$. Then there exist at most $n-|A|$ distinct $A$-appropriate shifts.

Proof of Lemma. If the only $A$-appropriate shift is $g_0(x)=g(x)$, we are done as $1\leqslant n-|A|$. So, assume that $g_k$ is $A$-appropriate but $g_k\not\equiv g$. For every $x\notin A$ define $P(x)$ as the maximal set of the form $\{x,x-k,x-2k,\ldots\}$ for which $x-k,x-2k,\ldots$ all belong to $A$ (it may happen that $P(x)=\{x\}$). Since $g_k$ is $k$-appropriate, the coloring $g$ is constant on each set $P(x)$. The whole $G$ is partitioned onto $n-|A|$ sets $P(x)$ and several orbits $\{a,a+k,a+2k,\ldots\}$ which are contained in $A$. Since $g_k\not\equiv g$, there exists an element $\alpha\in G$ such that $g(\alpha)\ne g(\alpha-k)$. Assume that $g_c\in \Phi$ is $A$-appropriate, that is, $g(x)=g(x+c)$ for all $x\in A$. If both $\alpha-c$, $\alpha-c-k$ belong to $A$, then $g(\alpha)=g(\alpha-c)=g(\alpha-c-k)=g(\alpha-k)$, a contradiction. Thus $\alpha-c$ must belong to some set $P(x)=\{x,x-k,x-2k,\ldots, x-(d-1)k\}$ for $x\notin A$. Also, either $\alpha-c=x$ or $\alpha-c=x-(d-1)k$. Let us show that for fixed $x$, at most one element of $P(x)$ may appear as $\alpha-c$ (when $c$ vary). Assume the contrary, then in particular $d>1$. If $\alpha-c=x$, we have $\alpha-c-k=x-k\in A$, thus $g(\alpha-k)=g(\alpha-c-k)=g(x)$. If $\alpha-c=\alpha-(d-1)k\in A$, then $g(\alpha)=g(\alpha-c)=g(x)$. Since both equations $g(\alpha-k)=g(x)$, $g(\alpha)=g(x)$ can not hold simultaneously, we see that at most one element of $P(x)$ may be equal to $\alpha-c$. Thus there exists at most $n-|A|$ possible $c$ for which $g_c$ is $A$-appropriate.

It remains to deduce Proposition from Lemma that is rather tautological.

Proof of Proposition. Without loss of generality $g_0=g\in M$. If the claim does not hold, there exist $n-k+1$ elements $x$ for which $|\{\varphi(x)|\varphi\in M\}|=1$, i.e., $\varphi(x)=g(x)$ for all $\varphi\in M$. But then by Lemma $|M|\leqslant k-1$, a contradiction.

We may identify $V$ with the field $\mathbb{F}_p$ of size $p$, then denoting $g_k(x):=g(x+k)$ for $k\in \mathbb{F}_p$ the questions reads as:

if $f(x)\not\equiv g_k(x)$ for each $k\in \mathbb{F}_p$, prove that there exists $h(x)$ such that $h(x)\ne f(x)$ for all $x$; but for each $k$ there exists $x(k)$ for which $h(x(k))=g_k(x(k))$.

If $g\equiv c$ is a constant coloring, we find a vertex $v\in \mathbb{F}_p$ for which $f(v)\ne c$ and put $h(v)=c$, and put $h(x)\in C\setminus \{f(x)\}$ for $v\ne x$ arbitrarily (this is possible since $|C|\geqslant |\{c,f(v)\}|=2$.)

If $g$ is not constant, we additionally require that $x(k)\colon \mathbb{F}_p\to \mathbb{F}_p$ is a bijection. Then we need $f(x(k))\ne g_k(x(k))$ for all $k$ (and $h$ is automatically defined by $h(x(k))=g_k(x(k))$). Consider the $p\times p$ matrix with both rows and columns indexed by $\mathbb{F}_p$ and put a star at the entry $(x,k)$ iff $f(x)\ne g(x+k)$. We want $p$ non-attacking rooks on the starred entries. Assume the contrary, then by Hall lemma (or Koenig theorem if you prefer) there exist sets $A,B\subset \mathbb{F}_p$ such that $|A|+|B|=p+1$ and $f(x)=g(x+k)$ for $x\in A$, $k\in B$.

If $|B|=1$, then $|A|=\mathbb{F}_p$ and $f(x)=g(x+k)$ for all $x$ where $B=\{k\}$. This contradicts to our assumption.

If $|A|=1$, then $B=\mathbb{F}_p$ and we get that $g$ is constant, which also is not the case.

So, assume hereafter that $1<|A|,|B|<p$. Then we may also assume without loss of generality that $g$ takes colors from the set $\mathbb{F}_p$. Replacing $f(x)$ to 0 for $x\notin A$, we get the same for $f$, and $f(x)=g(x+k)$ for $x\in A$, $k\in B$ still holds. Now the functions $f,g\colon \mathbb{F}_p\to \mathbb{F}_p$ are given by polynomials of degree at most $p-1$. Denote degree of $g$ by $d$, we have $d\geqslant 1$ since $g$ is not constant. Then we may write $d=d_1+d_2$ where $0\leqslant d_1<|A|$, $1\leqslant d_2<|B|$. Then the coefficient of $x^{d_1}k^{d_2}$ in the polynomial $h(x,k):=g(x+k)-f(x)$ is non-zero (it equals to a leading coefficient of $g$ times some non-zero binomial coefficient.) Any other monomial $x^a k^b$ in $h$ has either $a<d_1$ or $k<d_2$ (or both). Thus by generalized Combinatorial Nullstellensatz there exist $x\in A$, $k\in B$ with $h(x,k)\ne 0$, a contradiction.

Generalized Combinatorial Nullstellensatz is the following slight generalization of Alon's Combinatorial Nullstellensatz:

whenever $f(x_1,\ldots,x_k)$ is a polynomial with coefficients in the field $K$, the coefficient of the monomial $\prod x_i^{d_i}$ in $f$ is non-zero, and for each other monomial $\prod x_i^{c_i}$ in $f$ there exists at least one index $j$ such that $c_i<d_i$, then for arbitrary sets $A_i\subset K$ for which $|A_i|>d_i$ there exist $a_i\in A_i$ such that $f(a_1,\ldots,a_k)\ne 0$.

We may identify $V$ with the field $\mathbb{F}_p$ of size $p$, then denoting $g_k(x):=g(x+k)$ for $k\in \mathbb{F}_p$ the questions reads as:

if $f(x)\not\equiv g_k(x)$ for each $k\in \mathbb{F}_p$, prove that there exists $h(x)$ such that $h(x)\ne f(x)$ for all $x$; but for each $k$ there exists $x(k)$ for which $h(x(k))=g_k(x(k))$.

If $g\equiv c$ is a constant coloring, we find a vertex $v\in \mathbb{F}_p$ for which $f(v)\ne c$ and put $h(v)=c$, and put $h(x)\in C\setminus \{f(x)\}$ for $v\ne x$ arbitrarily (this is possible since $|C|\geqslant |\{c,f(v)\}|=2$.)

If $g$ is not constant, we additionally require that $x(k)\colon \mathbb{F}_p\to \mathbb{F}_p$ is a bijection. Then we need $f(x(k))\ne g_k(x(k))$ for all $k$ (and $h$ is automatically defined by $h(x(k))=g_k(x(k))$). Consider the $p\times p$ matrix with both rows and columns indexed by $\mathbb{F}_p$ and put a star at the entry $(x,k)$ iff $f(x)\ne g(x+k)$. We want $p$ non-attacking rooks on the starred entries. Assume the contrary, then by Hall lemma (or Koenig theorem if you prefer) there exist sets $A,B\subset \mathbb{F}_p$ such that $|A|+|B|=p+1$ and $f(x)=g(x+k)$ for $x\in A$, $k\in B$.

If $|B|=1$, then $|A|=\mathbb{F}_p$ and $f(x)=g(x+k)$ for all $x$ where $B=\{k\}$. This contradicts to our assumption.

If $|A|=1$, then $B=\mathbb{F}_p$ and we get that $g$ is constant, which also is not the case.

So, assume hereafter that $1<|A|,|B|<p$. Then we may also assume without loss of generality that $g$ takes colors from the set $\mathbb{F}_p$. Replacing $f(x)$ to 0 for $x\notin A$, we get the same for $f$, and $f(x)=g(x+k)$ for $x\in A$, $k\in B$ still holds. Now the functions $f,g\colon \mathbb{F}_p\to \mathbb{F}_p$ are given by polynomials of degree at most $p-1$. Denote degree of $g$ by $d$, we have $d\geqslant 1$ since $g$ is not constant. Then we may write $d=d_1+d_2$ where $0\leqslant d_1<|A|$, $1\leqslant d_2<|B|$. Then the coefficient of $x^{d_1}k^{d_2}$ in the polynomial $h(x,k):=g(x+k)-f(x)$ is non-zero (it equals to a leading coefficient of $g$ times some non-zero binomial coefficient.) Any other monomial $x^a k^b$ in $h$ has either $a<d_1$ or $b<d_2$ (or both). Thus by generalized Combinatorial Nullstellensatz there exist $x\in A$, $k\in B$ with $h(x,k)\ne 0$, a contradiction.

Generalized Combinatorial Nullstellensatz is the following slight generalization of Alon's Combinatorial Nullstellensatz:

whenever $f(x_1,\ldots,x_k)$ is a polynomial with coefficients in the field $K$, the coefficient of the monomial $\prod x_i^{d_i}$ in $f$ is non-zero, and for each other monomial $\prod x_i^{c_i}$ in $f$ there exists at least one index $j$ such that $c_i<d_i$, then for arbitrary sets $A_i\subset K$ for which $|A_i|>d_i$ there exist $a_i\in A_i$ such that $f(a_1,\ldots,a_k)\ne 0$.

We may identify $V$ with the field $\mathbb{F}_p$ of size $p$, then denoting $g_k(x):=g(x+k)$ for $k\in \mathbb{F}_p$ the questions reads as:

if $f(x)\not\equiv g_k(x)$ for each $k\in \mathbb{F}_p$, prove that there exists $h(x)$ such that $h(x)\ne f(x)$ for all $x$; but for each $k$ there exists $x(k)$ for which $h(x(k))=g_k(x(k))$.

If $g\equiv c$ is a constant coloring, we find a vertex $v\in \mathbb{F}_p$ for which $f(v)\ne c$ and put $h(v)=c$, and put $h(x)\in C\setminus \{f(x)\}$ for $v\ne x$ arbitrarily (this is possible since $|C|\geqslant |\{c,f(v)\}|=2$.)

If $g$ is not constant, we additionally require that $x(k)\colon \mathbb{F}_p\to \mathbb{F}_p$ is a bijection. Then we need $f(x(k))\ne g_k(x(k))$ for all $k$ (and $h$ is automatically defined by $h(x(k))=g_k(x(k))$). Consider the $p\times p$ matrix with both rows and columns indexed by $\mathbb{F}_p$ and put a star at the entry $(x,k)$ iff $f(x)\ne g(x+k)$. We want $p$ non-attacking rooks on the starred entries. Assume the contrary, then by Hall lemma (or Koenig theorem if you prefer) there exist sets $A,B\subset \mathbb{F}_p$ such that $|A|+|B|=p+1$ and $f(x)=g(x+k)$ for $x\in A$, $k\in B$.

If $|B|=1$, then $|A|=\mathbb{F}_p$ and $f(x)=g(x+k)$ for all $x$ where $B=\{k\}$. This contradicts to our assumption.

If $|A|=1$, then $B=\mathbb{F}_p$ and we get that $g$ is constant, which also is not the case.

So, assume hereafter that $1<|A|,|B|<p$. Then we may also assume without generality that $g$ takes colors from the set $\mathbb{F}_p$. Replacing $f(x)$ to 0 for $x\notin A$, we get the same for $f$, and $f(x)=g(x+k)$ for $x\in A$, $k\in B$ still holds. Now the functions $f,g\colon \mathbb{F}_p\to \mathbb{F}_p$ are given by polynomials of degree at most $p-1$. Denote degree of $g$ by $d$, we have $d\geqslant 1$ since $g$ is not constant. Then we may write $d=d_1+d_2$ where $0\leqslant d_1<|A|$, $1\leqslant d_2<|B|$. Then the coefficient of $x^{d_1}k^{d_2}$ in the polynomial $h(x,k):=g(x+k)-f(x)$ is non-zero (it equals to a leading coefficient of $g$ times some non-zero binomial coefficient.) Any other monomial $x^a k^b$ in $h$ has either $a<d_1$ or $k<d_2$ (or both). Thus by generalized Combinatorial Nullstellensatz there exist $x\in A$, $k\in B$ with $h(x,k)\ne 0$, a contradiction.

Generalized Combinatorial Nullstellensatz is the following slight generalization of Alon's Combinatorial Nullstellensatz:

whenever $f(x_1,\ldots,x_k)$ is a polynomial with coefficients in the field $K$, the coefficient of the monomial $\prod x_i^{d_i}$ in $f$ is non-zero, and for each other monomial $\prod x_i^{c_i}$ in $f$ there exists at least one index $j$ such that $c_i<d_i$, then for arbitrary sets $A_i\subset K$ for which $|A_i|>d_i$ there exist $a_i\in A_i$ such that $f(a_1,\ldots,a_k)\ne 0$.

We may identify $V$ with the field $\mathbb{F}_p$ of size $p$, then denoting $g_k(x):=g(x+k)$ for $k\in \mathbb{F}_p$ the questions reads as:

if $f(x)\not\equiv g_k(x)$ for each $k\in \mathbb{F}_p$, prove that there exists $h(x)$ such that $h(x)\ne f(x)$ for all $x$; but for each $k$ there exists $x(k)$ for which $h(x(k))=g_k(x(k))$.

If $g\equiv c$ is a constant coloring, we find a vertex $v\in \mathbb{F}_p$ for which $f(v)\ne c$ and put $h(v)=c$, and put $h(x)\in C\setminus \{f(x)\}$ for $v\ne x$ arbitrarily (this is possible since $|C|\geqslant |\{c,f(v)\}|=2$.)

If $g$ is not constant, we additionally require that $x(k)\colon \mathbb{F}_p\to \mathbb{F}_p$ is a bijection. Then we need $f(x(k))\ne g_k(x(k))$ for all $k$ (and $h$ is automatically defined by $h(x(k))=g_k(x(k))$). Consider the $p\times p$ matrix with both rows and columns indexed by $\mathbb{F}_p$ and put a star at the entry $(x,k)$ iff $f(x)\ne g(x+k)$. We want $p$ non-attacking rooks on the starred entries. Assume the contrary, then by Hall lemma (or Koenig theorem if you prefer) there exist sets $A,B\subset \mathbb{F}_p$ such that $|A|+|B|=p+1$ and $f(x)=g(x+k)$ for $x\in A$, $k\in B$.

If $|B|=1$, then $|A|=\mathbb{F}_p$ and $f(x)=g(x+k)$ for all $x$ where $B=\{k\}$. This contradicts to our assumption.

If $|A|=1$, then $B=\mathbb{F}_p$ and we get that $g$ is constant, which also is not the case.

So, assume hereafter that $1<|A|,|B|<p$. Then we may also assume without loss of generality that $g$ takes colors from the set $\mathbb{F}_p$. Replacing $f(x)$ to 0 for $x\notin A$, we get the same for $f$, and $f(x)=g(x+k)$ for $x\in A$, $k\in B$ still holds. Now the functions $f,g\colon \mathbb{F}_p\to \mathbb{F}_p$ are given by polynomials of degree at most $p-1$. Denote degree of $g$ by $d$, we have $d\geqslant 1$ since $g$ is not constant. Then we may write $d=d_1+d_2$ where $0\leqslant d_1<|A|$, $1\leqslant d_2<|B|$. Then the coefficient of $x^{d_1}k^{d_2}$ in the polynomial $h(x,k):=g(x+k)-f(x)$ is non-zero (it equals to a leading coefficient of $g$ times some non-zero binomial coefficient.) Any other monomial $x^a k^b$ in $h$ has either $a<d_1$ or $k<d_2$ (or both). Thus by generalized Combinatorial Nullstellensatz there exist $x\in A$, $k\in B$ with $h(x,k)\ne 0$, a contradiction.

Generalized Combinatorial Nullstellensatz is the following slight generalization of Alon's Combinatorial Nullstellensatz:

whenever $f(x_1,\ldots,x_k)$ is a polynomial with coefficients in the field $K$, the coefficient of the monomial $\prod x_i^{d_i}$ in $f$ is non-zero, and for each other monomial $\prod x_i^{c_i}$ in $f$ there exists at least one index $j$ such that $c_i<d_i$, then for arbitrary sets $A_i\subset K$ for which $|A_i|>d_i$ there exist $a_i\in A_i$ such that $f(a_1,\ldots,a_k)\ne 0$.