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$ Commented Oct 8, 2020 at 14:32
  • 1
    $\begingroup$ Do you mean order preserving or f(x)\leq x or what does decreasing Mean? $\endgroup$ Commented Oct 8, 2020 at 15:20
  • 1
    $\begingroup$ @Pietro Majer : can you develop ? Because $F(x)\leq x $ is not necessarly satisfied. $\endgroup$
    – Yoyo
    Commented Oct 8, 2020 at 15:26
  • 2
    $\begingroup$ Well $F$ is decreasing so, precisely, it switches the order. $\endgroup$
    – Yoyo
    Commented 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
    Commented 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
    Commented 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
    Commented Oct 8, 2020 at 16:30
  • $\begingroup$ Thx for your contribution.Have to think about it a bit more... $\endgroup$
    – Yoyo
    Commented 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
    Commented Oct 8, 2020 at 16:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .