7
$\begingroup$

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 ?

$\endgroup$
19
  • 4
    $\begingroup$ 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"? $\endgroup$ Oct 8, 2020 at 14:32
  • 1
    $\begingroup$ Do you mean order preserving or f(x)\leq x or what does decreasing Mean? $\endgroup$ Oct 8, 2020 at 15:20
  • 1
    $\begingroup$ @Pietro Majer : can you develop ? Because $F(x)\leq x $ is not necessarly satisfied. $\endgroup$
    – Yoyo
    Oct 8, 2020 at 15:26
  • 2
    $\begingroup$ Well $F$ is decreasing so, precisely, it switches the order. $\endgroup$
    – Yoyo
    Oct 8, 2020 at 15:37
  • 2
    $\begingroup$ @Jack L : for me, a decreasing function means : if $x\leq y$ then $F(x) \geq F(y)$. $\endgroup$
    – Yoyo
    Oct 8, 2020 at 15:39

2 Answers 2

6
$\begingroup$

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}

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

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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.