I was able to get at least (I think) close to proving 2 using Sperner’s Lemma as follows:
You can map the continuous function f(x) to a path of the kind found in Question 1 of length n+1 by evaluating f(x) at x=0, x=1 and n-1 equally spaced divisions between these two points and setting a node as blue if f(x) < 0 else as green.
By Sperner’s Lemma there is an odd, and therefore non-zero number of b-g vertices. You can then take any b-g pair of nodes as the starting points for a new path and repeat the process. After k iterations you have two values of x—only one where f(x) is below zero—that are 1/(n^k) away from each other. We thus can find arbitrarily close points that straddle zero. By taking the sequence f(x) of initial nodes x we get a sequence that, by B-W, has a sub-sequence which converges to zero. By continuity we have proved the existence of an x such that f(x)=0.
We can be sure that the sub-sequence does in fact converge to zero, rather than any other value because if it converges to any number |a|>0, the gradient of f(x) would have to be arbitrarily high to dip back below/above 0 for a value of x arbitrarily close by and therefore would not be a continuous function.
Comments to tighten up/poke holes in the above appreciated :)
I’m having trouble understanding why we can’t just fix n=2 in your proof. Then at each iteration we bisect the interval, so we wouldn’t be using the “full power” of the 1-D Sperner’s lemma (we would just be using something close to the base case).
Also if we are only given that f is continuous, does it make sense to talk about the gradient?
“I’m having trouble understanding why we can’t just fix n=2 in your proof. Then at each iteration we bisect the interval, so we wouldn’t be using the “full power” of the 1-D Sperner’s lemma (we would just be using something close to the base case).”—You’re right, you can prove this without using the full power of Sperner’s lemma. I think it becomes more useful for the multi-dimensional case.
Yeah agreed, in fact I don’t think you even need to continually bisect, you can just increase n indefinitely. Iterating becomes more dangerous as you move to higher dimensions because an n dimensional simplex with n+1 colours that has been coloured according to analogous rules doesn’t necessarily contain the point that maps to zero.
On the second point, yes I’d been assuming that a bounded function had a bounded gradient, which certainly isn’t true for say sin(x^2), the final step needs more work, I like the way you did it in the proof below.
I hit that stumbling block as well. I handwaved it by saying “continue iterating until you have x(k,B) and x(k,G) such that f(xk,B)<0, f(xk,G)≥0, and f has no local maxima or local minima on the open interval (xk,B,xk,G)”, but that doesn’t work for the Weierstrass function, which will (I believe) never meet that criterion.
I was able to get at least (I think) close to proving 2 using Sperner’s Lemma as follows:
You can map the continuous function f(x) to a path of the kind found in Question 1 of length n+1
by evaluating f(x) at x=0, x=1 and n-1 equally spaced divisions between these two points and setting a node as blue if f(x) < 0 else as green.
By Sperner’s Lemma there is an odd, and therefore non-zero number of b-g vertices. You can then take any b-g pair of nodes as the starting points for a new path and repeat the process. After k iterations you have two values of x—only one where f(x) is below zero—that are 1/(n^k) away from each other. We thus can find arbitrarily close points that straddle zero. By taking the sequence f(x) of initial nodes x we get a sequence that, by B-W, has a sub-sequence which converges to zero. By continuity we have proved the existence of an x such that f(x)=0.
We can be sure that the sub-sequence does in fact converge to zero, rather than any other value because if it converges to any number |a|>0, the gradient of f(x) would have to be arbitrarily high to dip back below/above 0 for a value of x arbitrarily close by and therefore would not be a continuous function.
Comments to tighten up/poke holes in the above appreciated :)
I’m having trouble understanding why we can’t just fix n=2 in your proof. Then at each iteration we bisect the interval, so we wouldn’t be using the “full power” of the 1-D Sperner’s lemma (we would just be using something close to the base case).
Also if we are only given that f is continuous, does it make sense to talk about the gradient?
“I’m having trouble understanding why we can’t just fix n=2 in your proof. Then at each iteration we bisect the interval, so we wouldn’t be using the “full power” of the 1-D Sperner’s lemma (we would just be using something close to the base case).”—You’re right, you can prove this without using the full power of Sperner’s lemma. I think it becomes more useful for the multi-dimensional case.
Yeah agreed, in fact I don’t think you even need to continually bisect, you can just increase n indefinitely. Iterating becomes more dangerous as you move to higher dimensions because an n dimensional simplex with n+1 colours that has been coloured according to analogous rules doesn’t necessarily contain the point that maps to zero.
On the second point, yes I’d been assuming that a bounded function had a bounded gradient, which certainly isn’t true for say sin(x^2), the final step needs more work, I like the way you did it in the proof below.
I hit that stumbling block as well. I handwaved it by saying “continue iterating until you have x(k,B) and x(k,G) such that f(xk,B)<0, f(xk,G)≥0, and f has no local maxima or local minima on the open interval (xk,B,xk,G)”, but that doesn’t work for the Weierstrass function, which will (I believe) never meet that criterion.