I am having trouble figuring out why #2 needs / benefits from Sperner’s Lemma.
But I keep going back to the proof that I’m comfortable with, which depends on connectedness, so I’m clearly missing an obvious alternative proof that doesn’t need topology.
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.
Let n≥1 be an integer. We are given that f(0/n)=f(0)≤0 and f(n/n)=f(1)≥0. Now consider the points 0/n,1/n,…,(n−1)/n,n/n in the interval [0,1]. By 1-D Sperner’s lemma, there are an odd number of j∈{0,…,n} such that f(j/n)≥0 and f((j−1)/n)≤0 (i.e. an odd number of “segments” that begin below zero and end up above zero). In particular, 0 is an even number, so there must be at least one such number j. Choose the smallest and call this number jn.
Now consider the sequence (jn/n)∞n=1. Since this sequence takes values in [0,1], it is bounded, and by the Bolzano–Weierstrass theorem there must be some subsequence (kn/n)∞n=1 that converges to some number x∈[0,1].
Consider the sequences (f((kn−1)/n))∞n=1 and (f(kn/n))∞n=1. We have f((kn−1)/n)≤0≤f(kn/n) for each n≥1. By the limit laws, (kn−1)/n→x as n→∞. Since f is continuous, we have f((kn−1)/n)→f(x) and f(kn/n)→f(x) as n→∞. Thus f(x)≤0 and f(x)≥0, showing that f(x)=0, as desired.
I am having trouble figuring out why #2 needs / benefits from Sperner’s Lemma.
But I keep going back to the proof that I’m comfortable with, which depends on connectedness, so I’m clearly missing an obvious alternative proof that doesn’t need topology.
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.
Here is my attempt, based on Hoagy’s proof.
Let n≥1 be an integer. We are given that f(0/n)=f(0)≤0 and f(n/n)=f(1)≥0. Now consider the points 0/n,1/n,…,(n−1)/n,n/n in the interval [0,1]. By 1-D Sperner’s lemma, there are an odd number of j∈{0,…,n} such that f(j/n)≥0 and f((j−1)/n)≤0 (i.e. an odd number of “segments” that begin below zero and end up above zero). In particular, 0 is an even number, so there must be at least one such number j. Choose the smallest and call this number jn.
Now consider the sequence (jn/n)∞n=1. Since this sequence takes values in [0,1], it is bounded, and by the Bolzano–Weierstrass theorem there must be some subsequence (kn/n)∞n=1 that converges to some number x∈[0,1].
Consider the sequences (f((kn−1)/n))∞n=1 and (f(kn/n))∞n=1. We have f((kn−1)/n)≤0≤f(kn/n) for each n≥1. By the limit laws, (kn−1)/n→x as n→∞. Since f is continuous, we have f((kn−1)/n)→f(x) and f(kn/n)→f(x) as n→∞. Thus f(x)≤0 and f(x)≥0, showing that f(x)=0, as desired.