Let $V$ be the vertices of a regular $p$-agon in the plane, where $p$ is prime, and let $C$ be a set. Given two maps $f,g:V\rightarrow C,$ I believe it is true that either


(a) $f=g\circ r$ for some rotation $r:V\rightarrow V,$ or


(b) there is $h:V\rightarrow C$ such that for all $v\in V,$ $h(v)\neq f(v),$ but for all rotations $r:V\rightarrow V,$ there exists $v\in V$ (depending on $r$) such that $h(v)=g\circ r(v).$


Note these are mutually exclusive. (*Aside*: Calling the maps "colorings" of $V,$ I am saying if $f$ and $g$ are colorings, which are not just rotations of each other, then there is another coloring $h$ that doesn't match $f$ anywhere, but matches every rotation of $g$ somewhere. Perhaps this sounds more intuitive.)


My proof is of course elementary but involves some case by case analysis, so I would like to ask if it follows from known results, or has an easy proof that I have missed. I don't know if it's essential that $p$ be prime, but I need that for my proof.



A question about colorings of the vertices of a p-agon, where p is prime
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$.


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.


