# Fixed point for a map from $\{0,1\}^N$ to itself

Let $$N\geq2.$$ Let $$F$$ be a function from $$\left\{ 0,1\right\} ^{N}$$ to itself dreceasing for the product order defined by $$(x_1,x_2,\ldots,x_N)\leq (y_1,\ldots,y_N)\ \text{ if and only if for all }i,\ x_i\leq y_i$$

Here, $$F$$ being decreasing means $$x\leq y \Rightarrow F(y)\leq F(x)$$

Suppose moreover that the $$i^{th}$$ component of $$F$$ does not depend on the $$i^{th}$$ variable.

Is it true that $$F$$ has a unique fixed point ?

• This question looks interesting. Can you write more explicitly what you mean by "the i.th component does not depend on the i.th variable"? Commented Oct 8, 2020 at 14:32
• Do you mean order preserving or f(x)\leq x or what does decreasing Mean? Commented Oct 8, 2020 at 15:20
• @Pietro Majer : can you develop ? Because $F(x)\leq x$ is not necessarly satisfied.
– Yoyo
Commented Oct 8, 2020 at 15:26
• Well $F$ is decreasing so, precisely, it switches the order.
– Yoyo
Commented Oct 8, 2020 at 15:37
• @Jack L : for me, a decreasing function means : if $x\leq y$ then $F(x) \geq F(y)$.
– Yoyo
Commented Oct 8, 2020 at 15:39

For $$N = 3$$ there are exactly $$58$$ counterexamples.

$$54$$ of them have two fixed points. E.g.: $$\begin{eqnarray} 000 &\mapsto& 110\\ 100 &\mapsto& 100\\ 010 &\mapsto& 010\\ 110 &\mapsto& 000\\ 001 &\mapsto& 000\\ 101 &\mapsto& 000\\ 011 &\mapsto& 000\\ 111 &\mapsto& 000\\ \end{eqnarray}$$

$$2$$ of them have three fixed points. E.g.:

$$\begin{eqnarray} 000 &\mapsto& 111\\ 100 &\mapsto& 100\\ 010 &\mapsto& 010\\ 110 &\mapsto& 000\\ 001 &\mapsto& 001\\ 101 &\mapsto& 000\\ 011 &\mapsto& 000\\ 111 &\mapsto& 000\\ \end{eqnarray}$$

2 of them have zero fixed point. E.g.: $$\begin{eqnarray} 000 &\mapsto& 111\\ 100 &\mapsto& 101\\ 010 &\mapsto& 110\\ 110 &\mapsto& 100\\ 001 &\mapsto& 011\\ 101 &\mapsto& 001\\ 011 &\mapsto& 010\\ 111 &\mapsto& 000\\ \end{eqnarray}$$

• In fact, from the first four rows of your first counterexample we see that it's not true for $N = 2$ either. Commented Oct 8, 2020 at 16:29
• @lambda Yes, not sure whether I'm missing something, as the OP claims that it's true for $N = 2$. Commented Oct 8, 2020 at 16:30
• Thx for your contribution.Have to think about it a bit more...
– Yoyo
Commented Oct 8, 2020 at 16:41

No. Consider $$F(0)=7,\ F(1)=5,\ F(2)=3,\ F(3)=1$$ $$F(4)=6,\ F(5)=4,\ F(6)=2,\ F(7)=0$$ where a number represents its base-2 expansion, e.g. 6 represents $$(1,1,0)$$.

• I fixed the answer; now it is decreasing where before it was non-decreasing.
– user44143
Commented Oct 8, 2020 at 16:09