Timeline for Fixed point for a map from $\{0,1\}^N$ to itself
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 8, 2020 at 17:19 | comment | added | Benjamin Steinberg | I think order reversing is more common for this phenomenon. For order preserving you could use the Tarski fixed point theorem. | |
| Oct 8, 2020 at 16:33 | history | edited | Amir Sagiv |
relevant tags added
|
|
| Oct 8, 2020 at 16:24 | answer | added | WhatsUp | timeline score: 6 | |
| Oct 8, 2020 at 16:05 | history | edited | Yoyo | CC BY-SA 4.0 |
added 209 characters in body
|
| Oct 8, 2020 at 15:51 | comment | added | Jack L. | Okay, my attempt will be to endow $M:=\{0,1\}^N$ with a complete metric such that $F$ is a contraction (or, compact metric such that $F$ is a contractive map). Fixed point theorems due to Banach and Edelstein would then give you a unique fixed point (plus all iterates converging to it in the defined metric). | |
| Oct 8, 2020 at 15:48 | answer | added | user44143 | timeline score: 4 | |
| Oct 8, 2020 at 15:48 | comment | added | Yoyo | @PietroMajer : nice idea ! | |
| Oct 8, 2020 at 15:40 | comment | added | Pietro Majer | Ok, so at least $F^2$ is increasing, so it has a fixed point for the above argument, that is a period 2 point of F. Maybe one can show that $F^2$ has an odd number of fixed points, so one is also fixed for F | |
| Oct 8, 2020 at 15:39 | comment | added | Yoyo | @Jack L : for me, a decreasing function means : if $x\leq y$ then $F(x) \geq F(y)$. | |
| Oct 8, 2020 at 15:37 | comment | added | Yoyo | Well $F$ is decreasing so, precisely, it switches the order. | |
| Oct 8, 2020 at 15:36 | comment | added | Jack L. | @Yoyo: you claim that “$F(x)\le x$ is not necessarily satisfied”. If so, then what do you mean by “$F$ is decreasing for the product order” other than $F(x)\le x$ when you have explained that the product order $(x_1,\ldots,x_N)\le(y_1,\ldots,y_N)$ simply means $x_i\le y_i$ for all $i$!.....Adding a clear-cut example in the question could help. | |
| Oct 8, 2020 at 15:34 | comment | added | Pietro Majer | I see, I understood that $x^2=F(x^1)\le F(x^0)=x^1$ because $F$ respects the order of $x^1\le x^0$ | |
| Oct 8, 2020 at 15:31 | comment | added | Yoyo | Nope. $x^2\leq x^0$ because $(1,...1)$ is the max of the whole set but there is no need for $x^2$ to be smaller than $x^1$ | |
| Oct 8, 2020 at 15:29 | comment | added | Pietro Majer | But doesn't $x^1 \le x^0:=(1,\dots,1)$ imply $x^2\le x^1\le x^0$ etc? ($x^k:=F^{(k)}(x^0)$) | |
| Oct 8, 2020 at 15:26 | comment | added | Yoyo | @Pietro Majer : can you develop ? Because $F(x)\leq x $ is not necessarly satisfied. | |
| Oct 8, 2020 at 15:23 | comment | added | Pietro Majer | Iterating $F$ starting from $(1,\dots,1)$ one arrives in $\le 2^N$ iterations to a stationary point, or no? | |
| Oct 8, 2020 at 15:23 | comment | added | Yoyo | @Benjamin Steinberg : decreasing in the standard sense for the order product : if $x\leq y$ then $F(x)\geq F(y)$. | |
| Oct 8, 2020 at 15:21 | comment | added | Yoyo | Some others comments : if you remove one of the two hypothesis, the result is wrong even for $N=2$. Moreover, I have an algorithm that produces a lot of examples of such $F$ for which the proposition was always satisified. | |
| Oct 8, 2020 at 15:20 | comment | added | Benjamin Steinberg | Do you mean order preserving or f(x)\leq x or what does decreasing Mean? | |
| Oct 8, 2020 at 15:17 | comment | added | Yoyo | No, the order is the product order which is only a partial order: $$(x_1,x_2,\cdots,x_N)\leq(y_1,y_2,\cdots,y_N)$$ if and only $$x_i\leq y_i$$ for all i=1..N. Moreover, LSpice is correct. Thanks for your interest. | |
| Oct 8, 2020 at 15:02 | comment | added | LSpice | I.e., there is a function $F_i$ such that $F(x)_i = F_i(x_1, \dotsc, x_{i - 1}, \widehat{x_i}, x_{i + 1}, \dotsc, x_N)$? | |
| Oct 8, 2020 at 14:32 | comment | added | Dominic van der Zypen | 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"? | |
| Oct 8, 2020 at 13:50 | comment | added | Yoyo | It is for N=2. Just check all the possible $F$ | |
| Oct 8, 2020 at 13:49 | history | asked | Yoyo | CC BY-SA 4.0 |